Khóa luận Phân tích câu hỏi trong hệ thống hỏi đáp tiếng Việt

ày tháng distance Khoẳng cách, đo lường tuyến tính money Giá cả order Thứ hạng other Các số khác period Khoảng thời gian percent Phần trăm speed Tốc độ temp Nhiệt độ size Kích thước, diện tích, thể tích weight Cân nặng 19 2.5. Khảo sát các phương pháp phân tích câu hỏi cho các loại câu hỏi khác nhau Trong hội nghị TREC, các câu hỏi được chia thành một số loại sau: câu hỏi đơn giản (factual-base question), câu hỏi định nghĩa (definition question), câu hỏi danh sách (list question), câu hỏi phức tạp (complex question),…. Mỗi loại câu hỏi có những đặc trưng riêng và hướng tiếp cận khác nhau. 2.5.1. Câu hỏi đơn giản (factual-base) Câu hỏi factual-base là những câu hỏi về các sự vật, sự kiện đơn lẻ,.. có câu trả lời là những đoạn văn bản ngắn nằm sẵn trong tài liệu. Kiến trúc thông thường để xử lý loại câu hỏi này như sau (Hình 3): Câu hỏi đầu vào được phân lớp theo loại ngữ nghĩa của câu trả lời và biến đổi sang dạng truy vấn. Câu truy vấn được sử dụng để tìm kiếm các tài liệu có liên quan đến câu hỏi, loại câu hỏi được sử dụng trong phần trích xuất câu trả lời nhằm thu hẹp không gian tìm kiếm và kiểm tra câu trả lời có chính xác hay không [35]. Hình 3. Kiến trúc cho xử lý các câu hỏi factual-base Như vậy, hai công việc chính của pha xử lý câu hỏi với loại câu hỏi này là xác định loại câu hỏi và tạo truy vấn cho hệ IR (information retrieval) trích chọn tài liệu liên quan. Xác định loại câu hỏi Xác định loại câu hỏi có ý nghĩa rất quan trọng trong phân tích các câu hỏi factual base, đặc biệt là việc phân loại câu hỏi theo loại ngữ nghĩa của câu trả lời (như mục 2.3 đã NER NER Kho tài liệu Phân tích câu hỏi Trích chọn tài liệu liên quan Trích xuất câu trả lời WordNet Parser WordNet Parser Truy vấn Tài liệu Loại câu hỏi Câu trả lời Câu hỏi 20 trình bày). Có nhiều cách để xác định loại câu hỏi như: xây dựng bộ phân lớp câu hỏi sử dụng học máy thống kê, xác định câu hỏi sử dụng các kỹ thuật của xử lý ngôn ngữ tự nhiên, xác định loại câu hỏi dựa vào so khớp với các mẫu quan hệ có sẵn. Nội dung chi tiết của các phương pháp này được trình bày ở chương 3. Tạo truy vấn từ câu hỏi Vấn đề của tạo truy vấn là lựa chọn các từ khóa trong câu hỏi và kết hợp chúng để tạo ra câu truy vấn không quá chung chung, cũng không quá chi tiết. Chiến lược được sử dụng để trích ra các từ khóa quan trọng là sử dụng độ ưu tiên: Độ ưu tiên cao nhất được gán cho các từ trong dấu nháy kép hoặc nháy đơn, tiếp đến là các cụm danh từ, danh từ, động từ, tính từ, trạng từ. Các từ dừng, giới từ, trợ động từ được bỏ qua. Nhiều hệ thống Q&A có độ hồi tưởng (tỉ lệ câu trả lời đưa ra trên câu hỏi đầu vào) rất thấp. Một số nguyên nhân chính bao gồm: module phân tích câu hỏi không nhận diện được câu hỏi thuộc loại nào hoặc không tìm được các mẫu khớp với câu hỏi, module trích chọn thông tin (IR) không tìm ra được các tài liệu có chứa câu trả lời, module trích xuất câu trả lời không thể tìm ra câu trả lời thỏa đáng cho câu hỏi. Vì vậy với module trích chọn thông tin trong hệ thống Q&A, độ hồi tưởng là quan trọng hơn so với độ chính xác bởi các module sau có thể lọc ra các tài liệu không liên quan, nhưng không thể tìm ra được câu trả lời nếu các tài liệu chứa câu trả lời không được trả về từ IR [34] . Các nghiên cứu trước đây nhằm làm tăng độ hồi tưởng của IR đều tập trung vào việc thu nhỏ sự khác biệt về mặt hình thái, từ vựng và ngữ nghĩa giữa các từ xuất hiện trong truy vấn và trong tài liệu chứa câu trả lời. Về mặt hình thái, có hai cách được sử dụng [9,34]: - Áp dụng kĩ thuật stemming cho tập dữ liệu được đánh chỉ mục và các từ trong truy vấn (stemming là chuyển tất cả các dạng biến thể của một từ thành từ gốc, ví dụ “expand”, “expanded”, “expansion”, “expandable”… đều được chuyển thành “expand”). - Đánh chỉ mục cho các từ trong tài liệu mà không sử dụng stemming. Sử dụng kĩ thuật mở rộng hình thái (morphological expansion – ví dụ từ “expands” được mở rộng thành {“expands”,“expand”, “expanded”, “expansion”, “expandable” , … } ) cho các từ khóa trong câu hỏi khi tạo truy vấn. 21 Về mặt từ vựng và ngữ nghĩa, phương pháp hay được sử dụng đó là: các từ trong truy vấn được mở rộng bởi tập các từ đồng nghĩa, các khái niệm có nghĩa khái quát hơn hoặc chuyên môn hơn, chi tiết hơn hoặc bởi các từ liên quan. Phương pháp này đòi hỏi phải có các nguồn tri thức về ngôn ngữ, từ vựng như Wordnet hoặc Ontology. Moldovan trong [29] đã chỉ ra rằng từ trọng tâm của câu hỏi (question focus – xem trong phần 3.2) thường không xuất hiện trong tài liệu chứa câu hỏi. Với các câu hỏi có từ trọng tâm là “tỉnh thành”, “thành phố”, “đất nước”, “ngày tháng”… thì câu trả lời sẽ chứa các thể hiện cụ thể của các từ này (ví dụ với “đất nước” thì sẽ là “Việt Nam”, “Trung Quốc”… chứ không nhất thiết phải là “đất nước Việt Nam”). Vì vậy các từ trọng tâm của câu hỏi thường không được sử dụng để làm từ khóa tạo truy vấn. 2.5.2. Câu hỏi định nghĩa (definition question) Câu hỏi định nghĩa hỏi về định nghĩa hoặc mô tả về một điều, một khái niệm gì đó. Các câu hỏi thường gặp có dạng như “Máy tìm kiếm là gì”, “Định nghĩa khai phá dữ liệu”, “Bush là ai ?”… Câu trả lời cho loại câu hỏi này rất đa dạng, rất nhiều đoạn văn bản ngắn có thể coi là câu trả lời chấp nhận được. Ví dụ với câu hỏi “Who is George W. Bush ?” thì các câu trả lời có thể là: “… George W. Bush, the 43rd President of the United States…” “George W. Bush defeated Democratic incumbent Ann Richards to become the 46th Governor of the State of Texas…” …… Với loại câu hỏi định nghĩa, phương pháp thường hay được sử dụng là so khớp mẫu (pattern matching) [17]. Ví dụ về các mẫu câu hỏi và mẫu câu trả lời Mẫu câu hỏi What a ? Who ? là gì? là ai?.... Mẫu trả lời , the (a ) is a|the - - một loại là …. 22 Ưu điểm: Có độ chính xác khá cao. Nhược điểm: Các mẫu khó có thể bao quát được hết các trường hợp đa dạng của câu hỏi và câu trả lời. 2.5.3. Câu hỏi phức tạp, có ràng buộc về thời gian Phương pháp trình bày trong phần 2.5.1 có thể trả lời được các câu hỏi đơn giản factual base có từ ngữ diễn đạt thời gian đơn giản như: “Hồ Chí Minh sinh năm nào” hoặc “Ai là thủ tướng Việt Nam năm 2009 ?”. Tuy nhiên nhiều câu hỏi phức tạp đòi hỏi phải phát hiện ra các thuộc tính về thời gian hoặc thứ tự diễn ra của sự kiện. Ví dụ “Ai là tổng bí thư Đảng Cộng Sản Việt Nam trong chiến thắng lịch sử Điện Biên Phủ”. Câu hỏi liên quan đến thời gian được chia làm 4 loại [33]: Loại 1: Câu hỏi về một sự kiện đơn lẻ, không có biểu đạt về thời gian (temporal expressions) “Đại học Công Nghệ thành lập khi nào ?”. Loại 2: Câu hỏi về một sự kiện đơn lẻ, có biểu đạt về thời gian “Đội tuyển nào của Đại học công nghệ tham dự cuộc thi ACM quốc tế năm 2009” Ràng buộc thời gian: năm 2009. Loại 3: Câu hỏi có nhiều sự kiện, có biểu đạt về thời gian “Việt Nam đạt được những thành tựu gì sau khi chính sách mở cửa năm 1987 được thông qua ? ” Tín hiệu thời gian: sau khi Ràng buộc thời gian: năm 1987 Loại 4: Câu hỏi có nhiều sự kiện, không có biểu đạt về thời gian “Dân số thế giới là bao nhiêu trước chiến tranh thế giới thứ 2” Tín hiệu thời gian: trước Các tín hiệu thời gian trong Tiếng Việt như: sau, sau khi, trước, trước khi, trong khi, khi, trong thời gian, …Các biểu đạt về thời gian là các từ về ngày, tháng, năm, thế kỉ,… 23 Phương pháp xử lý: Gồm 4 bước sau: - Phân tích câu hỏi thành các các câu hỏi factual-base đơn giản hơn. “Dân số thế giới là bao nhiêu trước chiến tranh thế giới thứ 2 ?” 1) “Dân số thế giới là bao nhiêu ?” 2) “Chiến tranh thế giới thứ 2 xảy ra khi nào ?” - Tìm câu trả lời cho câu hỏi thứ nhất - Tìm câu trả lời cho câu hỏi thứ hai - Đưa ra câu trả lời mà vừa trả lời câu hỏi thứ nhất, vừa có giá trị thời gian thích hợp với câu trả lời cho câu hỏi thứ hai. 24 Chương 3. Các phương pháp xác định loại câu hỏi 3.1. Phương pháp phân lớp sử dụng học máy thống kê Theo [4] có hai hướng tiếp cận được sử dụng rộng rãi trong việc phân lớp câu hỏi đó là hướng tiếp cận dựa trên luật (rule-base approach) và hướng tiếp cận dựa trên xác suất thống kê. Hướng tiếp cận dựa trên luật: Hướng tiếp cận này yêu cầu phải có các chuyên gia ngôn ngữ cung cấp các luật, các biểu thức chính quy (regural expression), các từ khóa cho từng lớp câu hỏi … để hệ thống hoạt động. Các hạn chế của hướng tiếp cận này được chỉ ra trong [38]: o Xây dựng mô hình cho phương pháp này rất tốn thời gian và công sức, cần có sự cộng tác của những chuyên gia trong lĩnh vực ngôn ngữ học khi xây dựng các mẫu câu hỏi và văn phạm cho từng loại câu hỏi đó. o Các luật ngữ pháp viết tay và văn phạm của từng loại câu hỏi rất cứng nhắc, không linh động. Khi một dạng câu hỏi mới xuất hiện, mô hình theo hướng này không thể xử lý. Muốn xử lý được mô hình cần phải được cung cấp những luật mới. o Vấn đề nhập nhằng của các văn phạm ngữ pháp rất khó xử lý, kiểm soát và phụ thuộc vào đặc điểm của từng ngôn ngữ. o Khi tập câu trả lời được mở rộng hoặc thay đổi kéo theo việc phải viết lại hoàn toàn các luật trước đó nên hệ thống rất khó mở rộng. Một số hệ thống hỏi đáp sử dụng luật để phân lớp câu hỏi như Webclopedia [18] và [39]. Hướng tiếp cận dựa trên xác suất thống kê: Được Jonathan Brown tổng hợp lại bao gồm hai cách tiếp cận chính đó là Phương pháp học máy: Sử dụng một tập đủ lớn các câu hỏi đã được gán nhãn lớp để huấn luyện một mô hình có thể tự động nắm bắt được các mẫu có ích trong việc phân lớp câu hỏi. Cụ thể hơn, các thuật toán của hướng tiếp cận này sẽ tính toán xác suất phân 25 lớp cho câu hỏi dựa trên những đặc trưng hay những mối quan hệ của các từ trong câu hỏi đưa vào. Các thuật toán thường được sử dụng là Support Vector Machines (SVM), láng giềng gần nhất (Near Neighbors – kNN), Naïve Bayes (NB), Entropy cực đại, …Ngoài ra, các phương pháp học máy bán giám sát [36] cũng được đưa ra để sử dụng các câu hỏi chưa được gán nhãn làm tăng cường thêm độ chính xác cho phân lớp câu hỏi. Phương pháp sử dụng mô hình ngôn ngữ: Xây dựng một mô hình ngôn ngữ thống kê để ước lượng được phân phối của ngôn ngữ tự nhiên chính xác nhất có thể. Cụ thể với bài toán phân lớp câu hỏi là việc ước lượng xác suất có điều kiện p(a|b) của “loại câu hỏi” a xuất hiện trong “ngữ cảnh” câu hỏi tự nhiên b. Bài toán đặt ra là chúng ta phải tìm một phương pháp ước lượng (có thể tin tưởng được) mô hình xác suất có điều kiện p(a|b) [4]. Hướng tiếp cận dựa trên học máy thống kê hiện đang được rất nhiều nhà nghiên cứu quan tâm vì nó không chỉ tốn ít công sức của con người hơn (so với phương pháp dựa trên luật) mà còn có tính khả chuyển cao, dễ dàng áp dụng cho nhiều miền ứng dụng khác nhau. Tuy nhiên hướng tiếp cận này cũng gặp khó khăn khi số lượng lớp câu hỏi lớn. Trong phân lớp câu hỏi, người ta muốn phân câu hỏi vào các lớp càng nhỏ càng tốt nhằm thu hẹp không gian tìm kiếm câu trả lời. Các hệ thống hỏi đáp hiện nay thường có số lượng lớp câu hỏi lớn (hệ thống của Li và Roth [25] có 50 lớp, hệ thống trong [39] có 54 lớp, trong [15] có 68 lớp, Webclopedia [18] có 122 lớp,…), trong khi các thuật toán học máy sẽ giảm hiệu quả nếu số lớp tăng. Vì vập cần cải tiến mô hình và thuật toán để phù hợp với số lượng lớp lớn trong phân lớp câu hỏi. Phần 3.1 này sẽ trình bày các nội dung về học máy thống kê và mô hình áp dụng cho phân lớp câu hỏi. 3.1.1. Bài toán phân lớp trong khai phá dữ liệu Phân lớp là bài toán điển hình trong khai phá dữ liệu. Mục đích của phân lớp là để dự đoán những nhãn lớp cho các bộ dữ liệu mới. • Đầu vào: một tập các mẫu dữ liệu huấn luyện, với một nhãn phân lớp cho mỗi mẫu dữ liệu. • Đầu ra: mô hình (bộ phân lớp) dựa trên tập huấn luyện và những nhãn phân lớp. Phân lớp là quá trình gồm hai bước: Bước 1 (học mô hình): một mô hình sẽ được xây dựng dựa trên việc phân tích các đối tượng dữ liệu đã được gán nhãn từ trước. Tập các mẫu dữ liệu này còn được gọi là tập 26 dữ liệu huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện được xác định bởi con người trước khi xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát (supervised learning). Trong bước này, chúng ta còn phải tính độ chính xác của mô hình, mà cần phải sử dụng một tập dữ liệu kiểm tra (test data set). Nếu độ chính xác là chấp nhận được (tức là cao), mô hình sẽ được sử dụng để xác định nhãn lớp cho các dữ liệu khác mới trong tương lai. Bước 2 (sử dụng mô hình): sử dụng mô hình đã được xây dựng ở bước 1 để phân lớp dữ liệu mới. Đánh giá thuật toán phân lớp [3] Độ hồi tưởng ρ và độ chính xác π được dùng để đánh giá chất lượng của thuật toán phân lớp. Giả sử các tài liệu thuộc vào hai lớp và thuật toán cần học một lớp trong hai lớp đó, khi đó các giá trị TP (true positives), TN (true negatives), FP (false positives), FN (false negatives) được xem xét: - TP: số lượng ví dụ dương (tài liệu thực sự thuộc lớp cần đoán nhận) được thuật toán phân lớp cho giá trị đúng. - TN: số lượng ví dụ âm (tài liệu thực sự không thuộc lớp cần đoán nhận) những được thuật toán phân lớp cho giá trị đúng. - FP: số lượng ví dụ dương được thuật toán phân lớp cho giá trị sai. - FN: số lượng ví dụ âm được thuật toán phân lớp cho giá trị sai. Đánh giá phân lớp đa lớp (thông qua dữ liệu test Dtest) Bài toán ban đầu: C gồm có k lớp Đối với mỗi lớp Ci , cho thực hiện thuật toán với các dữ liệu thuộc Dtest nhận được các đại lượng TPi, TFi, FPi, FNi (như bảng 2). 27 Bảng 2. Biểu diễn của TP, TN, FP, FN trong đánh giá phân lớp Giá trị thực Lớp Ci Thuộc lớp Ci Không thuộc lớp Ci Thuộc lớp Ci TPi TNi Giá trị qua bộ phân lớp đa lớp Không thuộc lớp Ci FPi FNi Khi đó, FPTP TP +=ρ và FNTP TP +=π Trong trường hợp phân lớp K lớp, các độ đo cực tiểu trung bình (microaveraging) và cực đại trung bình (macroaveraging) được sử dụng: )(1 1 ∑ ∑ = = += K c cc K c c FPTP TPµρ (microaveraging recall) )( )( 1 1 ∑ ∑ = = + += K c cc K c cc FNTP FPTPµπ (microaveraging precision) và ∑ = = K c c M K 1 1 ππ (macroaveraging recall) ∑ = = K c c M K 1 1 ρρ (macroaveraging precision) Các độ đo cực tiểu trung bình được đánh coi là các độ đo tốt để đánh giá chất lượng thuật toán phân lớp tài liệu. 28 3.1.2. Các thuật toán học máy thống kê cho việc phân lớp Có nhiều thuật toán khác nhau cho phân lớp như Naïve Bayes, K láng giềng gần nhất, cây quyết định (Decision Tree), Máy Vector hỗ trợ (Support Vector Machine), Mạng lọc thưa (Sparse Network of Winnows -SNoW), Mô hình Entropy cực đại … Tuy nhiên phần tiếp theo của khóa luận chỉ trình bày về máy Vector hỗ trợ và mô hình Entropy cực đại - hai thuật toán được sử dụng nhiều trong phân lớp câu hỏi và cũng sẽ được sử dụng trong phần thực nghiệm ở chương 4. 3.1.2.1. Máy Vector hỗ trợ - SVM a. Thuật toán Theo [2], thuật toán Support Vector Machines (máy vector hỗ trợ) được Corters và Vapnik giới thiệu vào năm 1995. SVM rất hiệu quả để giải quyết các bài toán với dữ liệu có số chiều lớn như các vector biểu diễn văn bản. Thuật toán SVM ban đầu được thiết kế để giải quyết bài toán phân lớp nhị phân (hai lớp). Cho tập dữ liệu học D ={(xi, yi), i = 1,…, n} với xi ∈ Rm và yi∈{-1,+1} là một số nguyên xác định xi là dữ liệu dương (+1) hay âm (-1). Một tài liệu xi được gọi là dữ liệu dương nếu nó thuộc lớp ci ; xi được gọi là dữ liệu âm nếu nó không thuộc lớp ci . Bộ phân lớp tuyến tính được xác định bằng siêu phẳng: {x : f(x) = wTx + w0 =0 } Trong đó w∈ Rm và w0∈R là các hệ số có thể điều chỉnh đóng vai trò là tham số của mô hình. Hàm phân lớp nhị phân h: Rm → {0,1}, có thể thu được bằng cách xác định dấu của f(x): { 0 (x) 1 0 (x) 0 >≤= f f h Như vậy việc học mô hình phân lớp chính là việc xác định w và w0 từ dữ liệu. Với thuật toán này, mỗi dữ liệu được xem là một điểm trong mặt phẳng. Dữ liệu học là tách rời tuyến tính (linearly separable) nếu tồn tại một siêu phẳng sao cho hàm phân lớp phù hợp với tất cả các nhãn, tức là yif(xi)>0 với mọi i = 1,...,n. Với giả thuyết này, Rosenblatt đã đưa ra một thuật toán lặp đơn giản để xác định siêu phẳng: 29 Perceptron(D) Có thể thấy rằng điều kiện đủ để tập ví dụ D tách rời tuyến tính là số dữ liệu học n = |D| nhỏ hơn hoặc bằng m+1. Điều này là thường đúng với bài toán phân lớp văn bản, bởi vì số lượng từ mục có thể lên tới hàng nghìn và lớn hơn nhiều lần so với số lượng dữ liệu học. Tuy nhiên thuật toán Perceptron trên lại gặp vấn đề đó là overfitting1. Hình 4 đưa ra một ví dụ về overfitting. Giả sử rằng các dữ liệu mẫu thuộc lớp âm và lớp dương đều tuân theo luật phân bố chuẩn Gaussian, và được tạo ra với cùng một xác suất. Khi đó một siêu phẳng phân cách được gọi là lý tưởng nếu nó làm cực tiểu xác suất phân lớp sai cho một điểm dữ liệu mới. Với giả thuyết ở trên thì siêu phẳng phân cách lý tưởng sẽ trực giao với đoạn thẳng nối tâm của hai vùng có mật độ xác suất lớn nhất. Rõ ràng các siêu phẳng được xây dựng nhằm phân cách các điểm dữ liệu mẫu theo thuật toán Perceptron có thể lệch đi rất nhiều so với siêu phẳng lý tưởng, do đó sẽ dẫn tới việc phân lớp không tốt trên dữ liệu mới sau này. Độ phức tạp của quá trình xác định siêu phẳng lý tưởng sẽ tăng theo số chiều của không gian dữ liệu đầu vào m, vì với một số lượng n các dữ liệu mẫu cố định, tập hợp các siêu phẳng sẽ tăng theo hàm mũ với lũy thừa m. Với bài toán phân lớp trang văn bản, m thường rất lớn, khoảng vài ngàn hay thậm chí là hàng triệu từ. 1 Overfitting: 30 Hình 4. Mối quan hệ giữa các siêu phẳng phân cách Theo lý thuyết học thống kê được phát triển bởi Vapnik năm 1998 chỉ ra rằng có thể xác định một siêu phẳng tối ưu thỏa mãn hai tính chất quan trọng (1) nó là duy nhất với mỗi tập dữ liệu học tách rời tuyến tính; (2) khả năng overfitting là nhỏ hơn so với các siêu phẳng khác. Định nghĩa biên M của bộ phân lớp là khoảng cách giữa các siêu phẳng và các dữ liệu học gần nhất. Siêu phẳng tối ưu nhất là siêu phẳng có biên lớn nhất, điều đó có nghĩa là chúng ta cần tìm siêu phẳng sao cho khoảng cách từ siêu phẳng đến những điểm gần nhất là lớn nhất (Hình 5). Vapnik cũng chứng minh rằng khả năng overfitting với siêu phẳng tối ưu nhỏ hơn so với các siêu phẳng khác. 31 Hình 5. Siêu phẳng tối ưu và biên. Khoảng cách từ một điểm x đến siêu phẳng là: Vì vậy siêu phẳng tối ưu có thể thu được bằng ràng buộc tối ưu sau: 0w,w max M sao cho Ti i 0 1 y (w x w ) M,i 1,...n || w || + ≥ = Trong đó ràng buộc yêu cầu mọi tài liệu học (tương đương với các điểm) phải nằm trên nửa mặt phẳng của nó và khoảng cách tới siêu phẳng lớn hơn hoặc bằng M. Đặt 1w M= biểu thức trên được viết lại như sau 0w,w min W sao cho Ti i 0y (w x w ) M,i 1,...,n+ ≥ = Đưa về phương trình Lagrangian: ( )n2 Ti i 0 i 1 1L(D) || w || y w w 1 2 = ⎡ ⎤= − + α + −⎣ ⎦∑ 0|||| 1 wxw w T + 32 Sau đó tính đạo hàm của phương trình trên theo w,w0 ta được n T i i 1 1max 2α = − α Λα + α∑ thỏa mãn i 0,i 1,...,nα ≥ = Với Λ là ma trận n×n trong đó iα = yiyj jTi xx . Đây là bài toán bậc hai, theo lý thuyết có thể giải được bằng phương pháp chuẩn tối ưu. Với mỗi dữ liệu học i, cách giải phải thỏa mãn điều kiện: iα ( )[ ]1wwy 0Ti −+ =0 Và do đó hoặc iα = 0 hoặc )wxw(y 0iTi + =1. Nói cách khác, nếu iα >0 thì khoảng cách từ điểm xi đến mặt phẳng phân cách là M . Các điểm thỏa mãn iα >0 được gọi là các vector hỗ trợ. Hàm quyết định h(x) có thể được tính qua công thức dấu của f(x) hoặc tương đương với dạng sau: i T i n 1i i xxxy(x) ∑ = =f Những kết quả trong phần trên chỉ áp dụng cho trường hợp các tập có thể phân chia tuyến tính. Với các tập không thể phân chia tuyến tính, người ta đưa ra giải pháp “lề mềm” (soft margin) [5] . Hàm tối ưu trong trường hợp này là: ∑ = + n 1i C||w||min iww, ξ0 thỏa mãn ( )+ ≥ − = ≥ = ⎧⎪⎨⎪⎩ T i i 0 i i y w x w 1 ξ ,i 1,...,n ξ 0, i 1,...,n Ở đây, iξ gọi là biến nới lỏng (slack variables), hay các biến dương thể hiện mức độ chịu lỗi của bộ phân lớp (tolerances of misclassification). Thông qua đó, các vector huấn luyện được phép rơi vào trong khoảng chịu lỗi dọc theo biên ngăn cách hai lớp như được mô tả trong hình 6. 33 Hình 6. Biến nới lỏng cho soft margin Vấn đề này có thể đưa về dạng: 1 1max 2 n T i iα α α α = − Λ +∑ thỏa mãn Cα0 i ≤≤ i=1,…,n Bộ phân lớp theo cách này được gọi là bộ phân lớp máy vector hỗ trợ – Support Vector Machine. Nếu dữ liệu học là không tách rời tuyến tính, độ chính xác của bộ phân lớp SVM sẽ rất thấp, ngay cả với siêu phẳng tuyến tính tốt nhất. Phương pháp trình bày ở trên có thể mở rộng để phù hợp với dữ liệu không tách rời tuyến tính bằng cách sử dụng hàm nhân để ánh xạ mỗi điểm x ∈ Rm vào một không gian có số chiều lớn hơn (có thể là vô hạn chiều) gọi là không gian đặc trưng mà ở trong không gian này dữ liệu là tách rời tuyến tính Phân lớp đa lớp với SVM Bài toán phân lớp câu hỏi yêu cầu một bộ phân lớp đa lớp do đó cần cải tiến SVM cơ bản (phân lớp nhị phân) thành bộ phân lớp đa lớp. Một trong những phương pháp cải tiến đó là sử dụng thuật toán 1-against-all [40]. Ý tưởng cơ bản là chuyển bài toán phân lớp nhiều lớp thành nhiều bài toán phân lớp nhị phân như sau: 34 - Giả sử tập dữ liệu mẫu (x1,y1), … ,(xm,ym) với xi là một vector n chiều và yi ∈Y là nhãn lớp được gán cho vector xi (có m nhãn lớp khác nhau). - Biến đổi tập Y ban đầu thành m tập có hai lớp con có cấu trúc như sau. Zi ={yi , \ iY y } . - Áp dụng SVM phân lớp nhị phân cơ bản với m tập Zi để xây dựng siêu phẳng cho phân lớp này. - Bộ phân lớp với sự kết hợp của m bộ phân lớp trên được gọi là bộ phân lớp đa lớp mở rộng với SVM. 3.1.2.2. MEM Theo [4], đối với bài toán phân lớp dữ liệu, Entropy cực đại là một kỹ thuật dùng để ước lượng xác suất các phân phối từ dữ liệu. Tư tưởng chủ đạo của nguyên lý Entropy cực đại là “mô hình phân phối đối với mỗi tập dữ liệu và tập các ràng buộc đi cùng phải đạt được độ cân bằng đều nhất có thể ” – (có Entropy cực đại). Tập dữ liệu được học (đã được gán nhãn) được sử dụng để tìm ra các ràng buộc cho mô hình - là cơ sở để ước lượng phân phối cho từng lớp cụ thể. Những ràng buộc này được thể hiện bởi các giá trị ước lượng được của các đặc trưng. Từ các ràng buộc sinh ra bởi tập dữ liệu này, mô hình sẽ tiến hành tính toán để có được một phân phối với Entropy cực đại. Ví dụ về mô hình Entropy cực đại: “Giả sử với bộ phân lớp bài báo của báo điện từ Vnexpress. Bốn lớp chính chỉ ra đó là pháp_luật, thể_thao, quốc_tế, văn_hóa. Các thống kê trên tập dữ liệu mẫu chỉ ra rằng trung bình 70% các tài liệu trong lớp thể_thao có chứa từ bóng_đá. Như vậy một cách trực quan có thể thấy rằng nếu một tài liệu D có chứa từ bóng_đá thì xác suất được phân vào lớp thể_thao là 70% và xác suất phân vào ba lớp còn lại 10% ( bằng nhau giữa các lớp) và nếu D không chứa từ thể_thao thì xác suất phân phối của D là đều cho bốn lớp (mỗi lớp 25%).” Trong ví dụ trên “tài liệu chứa cụm bóng_đá thì có xác suất phân vào lớp thể_thao là 70%” là một ràng buộc của mô hình. 35 a. Các ràng buộc và đặc trưng Đối với nguyên lý Entropy cực đại, các ràng buộc cho phân phối điều kiện sẽ được thiết lập dựa trên tập dữ liệu mẫu. Mỗi một ràng buộc biểu thị một đặc điểm của tập dữ liệu học. Một đặc trưng trong mô hình Entropy cực đại được biểu hiện bởi một hàm fi(D;C). Nguyên lý cực đại Entropy cho phép chúng ta thu hẹp mô hình phân phối để thu được giá trị kỳ vọng cân bằng cho từng đặc trưng của dữ liệu. Xác suất phân phối của dữ liệu D cho lớp C thỏa mãn phương trình sau: ( )( ) ( ) ( ) ( ) (*) cd,fd|cPdPdcd,f |D| 1 i cdDd i ∑∑∑ = ∈ Trong phương trình (*) D là tập dữ liệu và C là một lớp câu hỏi. Ở một khía cạnh khác, fi(D;C) có thể được hiểu như: Nếu C là tập các lớp có thể mà chúng ta muốn phân lớp và D là tập các ngữ cảnh ( ràng buộc) có thể mà chúng ta quan sát được, thì mệnh đề biểu diễn thông tin ngữ cảnh là một hàm có dạng như sau: {0,1}DC :f →× Và được mô tả như sau: 1 khi c=c′ và cp(d) = true 0 trong trường hợp còn lại Trong đó cp(d) là một hàm có dạng: cp: d→ {true, false} Hàm này trả về giá trị true hoặc false, phụ thuộc vào sự xuất hiện hoặc không xuất hiện của các thông tin hữu ích trong một số ngữ cảnh d trong D. Ví dụ: - c' là lớp “thể_thao”, d là văn bản hiện tại. - cp = [ câu hiện tại chứa cụm từ “bóng_đá” ]. thì hàm đặc điểm này sẽ trả về giá trị 1 nếu như lớp dự đoán a là “thể_thao” và mang giá trị 0 trong các trường hợp còn lại. Bước đầu tiên khi sử dụng cự đại Entropy là phải xác định được tập hàm đặc trưng cho bộ phân lớp, sau đó đánh giá giá trị kỳ vọng của đặc trưng ấy trên tập dữ liệu học để biến hàm đặc trưng này thành một ràng buộc của phân lớp. fc