Tóm tắt Luận văn Một số mô hình học máy trong phân loại câu hỏi

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ THỊ TUYẾN MỘT SỐ MÔ HÌNH HỌC MÁY TRONG PHÂN LOẠI CÂU HỎI Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 TÓM TẮT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội -2016 1 MỤC LỤC MỤC LỤC ....................................................................................................................... 1 LỜI MỞ ĐẦU ................................................................................................................. 3 Chương 1: TỔNG QUAN VỀ PHÂN LOẠI CÂU HỎI ................................................. 4 1.1. Tổng quan về hệ thống hỏi đáp ............................................................................ 4 1.1.1.Đặt vấn đề ....................................................................................................... 4 1.1.2. Hệ thống hỏi đáp (Question Answering System) .......................................... 4 1.1.2.1. Giới thiệu ................................................................................................ 4 1.1.2.2. Cấu trúc của một hệ thống hỏi đáp ......................................................... 4 1.1.2.3. Tại sao phải phân loại câu hỏi? .............................................................. 5 1.2. Bài toán phân loại câu hỏi .................................................................................... 6 1.2.1. Định nghĩa phân loại câu hỏi ......................................................................... 6 1.2.2. Phát biểu bài toán phân loại câu hỏi .............................................................. 6 1.3. Các cáchtiếp cận bài toán phân loại câu hỏi ......................................................... 6 1.3.1. Tiếp cận dựa trên luật .................................................................................... 6 1.3.2. Tiếp cận dựa trên học máy ............................................................................ 7 1.4. Biểu diễn câu hỏi .................................................................................................. 7 1.5. Taxonomy câu hỏi ................................................................................................ 7 1.5.1. Khái niệm về Taxonomy ............................................................................... 7 1.5.2. Các taxonomytheo kiểu câu trả lời ................................................................ 7 1.6. Các đặc trưng phân loại ........................................................................................ 8 1.6.1. Các đặc trưng về từ vựng .............................................................................. 8 1.6.2. Các đặc trưng về cú pháp .............................................................................. 9 1.6.2.1. POS Tags và Tagged Unigrams ............................................................. 9 1.6.2.2. Từ đầu (head word) ................................................................................ 9 1.6.2.3. Biểu thức chính quy .............................................................................. 10 1.6.3. Các đặc trưng ngữ nghĩa .............................................................................. 11 Chương 2: MỘT SỐ MÔ HÌNH HỌC MÁY TRONG PHÂN LOẠI CÂU HỎI ......... 12 2.1. Thuật toán Naïve Bayes ...................................................................................... 12 2.1.1. Định lý ......................................................................................................... 12 2.1.2. Thuật toán .................................................................................................... 13 2.2. Thuật toán k-láng giềng gần (k- Nearst Neighbours) ......................................... 14 2 2.3. Máy Vector hỗ trợ - SVM .................................................................................. 15 2.4. Hiệu suất trong phân loại câu hỏi ....................................................................... 18 Chương 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ ............................................................. 19 3.1. Lựa chọn bộ phân loại ........................................................................................ 19 3.2. Môi trường và công cụ sử dụng trong thực nghiệm ........................................... 19 3.3. Tập dữ liệu thử nghiệm ...................................................................................... 19 3.4. Xử lý dữ liệu ....................................................................................................... 20 3.5. Huấn luyện và kiểm thử với LibSVM ................................................................ 20 3.6. Kết quả thực nghiệm ........................................................................................... 21 3.7. Kết luận............................................................................................................... 21 TỔNG KẾT ................................................................................................................... 22 3 LỜI MỞ ĐẦU Ngày nay, với sự phát triển mạnh mẽ của Internet toàn cầu cùng với nhu cầu tìm kiếm thông tin ngày càng cao của con người đòi hỏi hệ thống hỏi đáp ngày một thông minh hơn.Những thắc mắc của người dùng dướidạng truy vấn cần được tìm kiếm và trả về một cách ngắn gọn, súc tích và chính xác nhất những gì mà họ mong muốn. Một trong những thành phần quan trọng ảnh hưởng trực tiếp đến kết quả tìm kiếm trong hệ thống hỏi đáp là giai đoạn phân loại câu hỏi.Một phân loại tốt sẽ giúp đưa ra câu trả lời chính xác hơn.Đã có nhiều phương pháp tiếp cận được đưa ra cho bài toán phân loại này, tuy nhiên phương pháp học máy là được áp dụng nhiều hơn cả. Chính vì lý do này mà tác giả chọn và nghiên cứu đề tài “Một số mô hình học máy trong phân loại câu hỏi”. Luận văn bao gồm 3 phần như sau: Chương 1: Tổng quan về phân loại câu hỏi Chương này trình bày tổng quan về phân loại câu hỏi, giới thiệu về hệ thống hỏi đáp, bài toán phân loại câu hỏi, cách tiếp cận giải quyết bài toán, tổng quan về các tiếp cận học máy như: biểu diễn câu hỏi, phân lớp câu hỏi, các đặc trưng câu hỏi. Chương 2: Một số mô hình học máy trong phân loại câu hỏi Chương này tập trung trình bày về 3 bộ phân loại thường được sử dụng: Naïve Bayes, K-láng giềng gần, Máy vector hỗ trợ và liệt kê một số bộ phân loại khác. So sánh hiệu suất phân loại của các bộ phân loại đó dựa trên kết quả tham khảo. Chương 3: Thực nghiệm và đánh giá Áp dụng bộ phân loại SVM thực hiện thí nghiệm trên tập dữ liệu UIUC, lựa chọn đặc trưng bag-of-word.Nhận xét kết quả trả về. 4 Chương 1: TỔNG QUAN VỀ PHÂN LOẠI CÂU HỎI 1.1. Tổng quan về hệ thống hỏi đáp 1.1.1.Đặt vấn đề Với số lượng ngày càng tăng nhanh chóng của tri thức trên Web, các máy tìm kiếm cần có nhiều trí thông minh hơn. Trong một vài trường hợp người sử dụng chỉ cần một phần chính xác của thông tin thay vì một danh sách các tài liệu.Thay vì bắt người sử dụng phải đọc toàn bộ tài liệu, nó thường được ưa chuộng hơn bằng cách đưa cho người sử dụng câu trả lời chính xác và ngắn gọn.Các hệ thống hỏi đáp (Question Answering systems-QA) phải cung cấp các phần thông tin chính xác cho các câu hỏi tương ứng. Một hệ thống hỏi đáp miền mở có thể trả lời được các câu hỏi viết bằng ngôn ngữ tự nhiên giống như con người. Một trong các thành phần đóng vai trò quan trọng trong hệ thống hỏi đáp là phân loại câu hỏi.Nhiệm vụ của phân loại câu hỏi như sau: Cho 1 câu hỏi, ánh xạ câu hỏi đó tới một trong k lớp, các lớp đó cung cấp một gợi ý ngữ nghĩa về câu trả lời sau khi được tìm kiếm. Mục đích của sự phân loại này là giảm thiểu các câu trả lời không có tiềm năng, giai đoạn này được xử lý tại quá trình hạ lưu để lựa chọn câu trả lời chính xác từ một lượng các câu trả lời có tiềm năng. 1.1.2. Hệ thống hỏi đáp (Question Answering System) 1.1.2.1. Giới thiệu QA system: là mộthệ thống đóng vai trò phổ biến trong việc tìm kiếm thông tin chính xác và hiệu quả. Nhiệm vụ của nó là đưa ra câu trả lời đầy đủ và chính xác ứng với yêu cầu của người dùng và câu trả lời được thể hiện bằng ngôn ngữ tự nhiên. Người dùng nhanh chóng lấy được thông tin cần thiết thay vì tìm kiếm thông tin trong một khối lượng lớn các văn bản. Có 2 loại hệ thống hỏi đáp:  Hệ thống hỏi đáp miền đóng (Closed-domain Question Answering): hệ thống này liên quan đến các câu hỏi trong một lĩnh vực cụ thế, chẳng hạn như lĩnh vực y học.  Hệ thống hỏi đáp miền mở (Open-domain Question Answering): hệ thống này liên quan đến các câu hỏi gần như về tất cả mọi thứ. 1.1.2.2. Cấu trúc của một hệ thống hỏi đáp Có nhiều hệ thống QA đã được đưa ra, nhưng hầu hết chúng đều tuân theo một khung làm việc chung. Thông thường, một hệ thống hỏi đáp xử lý 3 nhiệm vụ sau [6]: 5 xử lý câu hỏi, xử lý tài liệu và xử lý câu trả lời. Hình 1.1 dưới đây là kiến trúc tổng quan về một hệ thống hỏi đáp. Hình 1.1: Kiến trúc một hệ thống hỏi đáp 1.1.2.3. Tại sao phải phân loại câu hỏi? Về cơ bản có hai động cơ thúc đẩy chính về phân loại câu hỏi: xác định câu trả lời và lựa chọn chiến lược tìm kiếm. Xác định câu trả lời: biết được loại câu hỏi không chỉ có thể thu gọn được không gian tìm kiếm cần tìm câu trả lời, nó còn có thể tìm kiếm chính xác câu trả lời trong một tập lớn các ứng viên trả lời. Cho ví dụ biết được loại của câu hỏi “Who was the president of U.S. in 1934?” có kiểu là “human”, hệ thống trả lời có thể chỉ quan tâm đến các ứng viên là tên các thực thể có kiểu là “human” mà không cần phải kiểm tra toàn bộ các đoạn văn bản để tìm ở đâu có thể chứa câu trả lời hoặc không. Lựa chọn chiến lược tìm kiếm: lớp câu hỏi có thể được sử dụng để lựa chọn chiến lược tìm kiếm khi câu hỏi được viết dưới dạng một truy vấn để tìm kiếm trên máy tìm kiếm. Cho ví dụ đưa ra câu hỏi “What is a pyrotechnic display ?”. Xác định 6 được lớp của câu hỏi này là “definition”, mẫu tìm kiếm cho việc xác định câu trả lời có thể dùng như “pyrotechnic display is a ...” or “pyrotechnic displays are ...”, nó tốt hơn nhiều việc tìm kiếm đơn giản bởi các từ để hỏi. 1.2. Bài toán phân loại câu hỏi 1.2.1. Định nghĩa phân loại câu hỏi Có nhiều định nghĩa khác nhau về phân loại câu hỏi, áp dụng định nghĩa phân loại văn bản, Håkan Sundblad[6] đã đưa ra một định nghĩa phân loại câu hỏi như sau: Phân loại câu hỏi là nhiệm vụ gán một giá trị kiểu boolean cho mỗi cặp , trong đó Q là miền chứa các câu hỏi và { | |} là tập các phân loại cho trước. Cặp (qj,ci) được gán cho giá trị là T chỉ ra rằng câu hỏi qj thuộc phân loại ci và được gán cho giá trị là F nếu qj không thuộc phân loại ci. Trong bối cảnh học máy, nhiệm vụ của phân loại câu hỏi là làm cho hàm mục tiêu từ chưa rõ ràng ̂ trở nên gần đúng với hàm mục tiêu lý tưởng , như vậy ̂ và Ф trùng nhau càng nhiều càng tốt. 1.2.2. Phát biểu bài toán phân loại câu hỏi Bài toán phân loại câu hỏi có thể được phát biểu như sau: Input: - Cho trước một tập các câu hỏi - Tập các chủ đề (phân loại) được định nghĩa Output: - Nhãn ci của câu hỏi qj. 1.3. Các cáchtiếp cận bài toán phân loại câu hỏi Theo [3,6]có 2 cách tiếp cận để phân loại câu hỏi: dựa trên luật (rule-based)và dựa trên học máy (machine learning based). Ngoài ra, có một vài cách tiếp cận lai là sự kết hợp của tiếp cận dựa trên luật và học máy. 1.3.1. Tiếp cận dựa trên luật Đây là cách tiếp cận được cho là đơn giản nhất để phân loại câu hỏi. Trong cách tiếp cận này thì việc phân loại câu hỏi dựa vào các luật ngữ pháp viết tay. Các luật này có được là do đề xuất từ các chuyên gia. Đối với cách tiếp cận này, một loạt các biểu thức chính quy (regular expression) được tạo ra để so khớp với câu hỏi từ đó quyết định phân loại của câu hỏi và loại câu trả lời. 7 1.3.2. Tiếp cận dựa trên học máy Đây là cách tiếp cận được sử dụng phổ biến để giải quyết bài toán phân loại câu hỏi.Cách tiếp cận này sẽ thay thế các kiến thức chuyên môn bằng một tập lớn các câu hỏi được gán nhãn (tập dữ liệu mẫu).Sử dụng tập này, một bộ phân lớp sẽ được huấn luyện có giám sát. Một số thuật toán thường được sử dụng như là: Mạng nơ-ron (Neural NetWork), tính xác suất Naïve Bayes, Maximum Entropy , cây quyết định (decision Tree) , lân cận (Nearest-Neighbors), Mạng lọc thưa (Sparse Network of Winnows - SNoW), Máy Vector hỗ trợ (Support Vector machine-SVM) ... Cách tiếp cận bằng học máy đã giải quyết được các hạn chế trong cách tiếp cận dựa trên luật. 1.4. Biểu diễn câu hỏi Một trong những nhiệm vụ đầu tiên trong việc xử lý phân loại câu hỏi là chọn được một mô hình biểu diễn câu hỏi thích hợp. Tùy thuộc vào từng thuật toán phân loại khác nhau mà chúng ta có mô hình biểu diễn riêng. Một trong những mô hình đơn giản và thường được sử dụng là mô hình không gian vector. Trong mô hình này, các câu hỏi được thể hiện trong một không gian có số chiều lớn, trong đó mỗi chiều của không gian tương ứng với một từ trong câu hỏi. Phương pháp này có thể biểu diễn một cách hình tượng như sau: mỗi câu hỏi được biểu diễn dưới dạng ⃗ (vector đặc trưng của câu hỏi đó). Trong đó, ⃗ và n là số lượng đặc trưng hay số chiều của vector câu hỏi, là trọng số của đặc trưng thứ i với 1.5. Taxonomy câu hỏi 1.5.1. Khái niệm về Taxonomy Khái niệm tanonomy được sử dụng trong nhiều lĩnh vực khác nhau, vì vậy mà có rất nhiều định nghĩa khác nhau. Trong lĩnh vực công nghệ thông tin, taxonomy được định nghĩa như sau [2]: Định nghĩa: Taxonomy là sự phân loại của toàn bộ thông tin trong một hệ phân cấp theo một mối quan hệ có trước của các thực thể trong thế giới thực mà nó biểu diễn. 1.5.2. Các taxonomytheo kiểu câu trả lời Taxonomy theo kiểu câu trả lời có thể được chia thành 2 loại [6]: taxonomy phẳng (flat) và taxonomy phân cấp (hierarchical). Taxonomy phẳng chỉ có duy nhất một mức phân loại, do đó không phân loại theo đúng nghĩa của từ. Taxonomy phân cấp bao gồm các phân loại lớn và tập các phân loại nhỏ bên trong. 8 Hầu hết các tiếp cận dựa trên học máy gần đây đều sử dụng taxonomy được đề xuất bởi Li và Roth[13] từ khi các tác giả công bố một tập các giá trị là 6000 câu hỏi đã gán nhãn. Tập dữ liệu này bao gồm hai tập riêng rẽ là 5500 và 500 câu hỏi trong đó tập đầu tiên sử dụng như một tập dữ liệu huấn luyện và tập thứ hai sử dụng như một tập kiểm tra độc lập. Tập dữ liệu này được xuất bản lần đầu tiên ở University of Illinois Urbana-Champaign (UIUC), thường được gọi là tập dữ liệu UIUC và thỉnh thoảng được coi như là tập dữ liệu TREC kể từ khi nó được mở rộng sử dụng trong hội nghị về truy hồi thông tin (Text REtrieval Conference-TREC). Taxonomy câu hỏi do Li và Roth đưa ragồm 2 cấp theosự phân loại ngữ nghĩa tựnhiên của câu trả lời trong hội nghị TREC. Cấu trúc phân cấp bao gồm 6 lớp thô: ABBREVIATION (viết tắt), ENTITY (thực thể),DESCRIPTION (mô tả), HUMAN (con người), LOCATION (địa điểm) và NUMERIC VALUE (giá trị số) cùng với 50 lớp con (fine class). 1.6. Các đặc trưng phân loại 1.6.1. Các đặc trưng về từ vựng Các đặc trưng từ vựng của một câu hỏi thường được rút trích dựa trên ngữ cảnh của các từ của câu hỏi, nghĩa là, các từ đó xuất hiện trong một câu hỏi. Trong nhiệm vụ phân loại câu hỏi, một câu hỏi được biểu diễn giống như biểu diễn tài liệu trong mô hình không gian vectơ, tức là, một câu hỏi là một vectơ mà được mô tả bởi các từ bên trong nó. Do đó một câu hỏi x có thể được biểu diễn như sau: Trong đó: xi là tần số xuất hiện của từ i trong câu hỏi x và N là tổng số các từ. Do sự thưa thớt của các đặc trưng, chỉ các đặc trưng có giá trị khác không mới được giữ lại trong vectơ đặc trưng. Vì vậy đôi khi các câu hỏi cũng được biểu diễn dưới hình thức sau: { ( )} Trong đó: ti là từ thứ i trong câu hỏi x và fi là tần số xuất hiện của ti trong câu hỏi x. Không gian đặc trưng này được gọi là các đặc trưng bag-of-words và thứ tự của các từ trong câu hỏi là không quan trọng trong cách biểu diễn. Việc biểu diễn các câu hỏi theo công thức (1.2) làm cho kích thước của tập mẫu tương đối nhỏ mặc dù kích thước của không gian đặc trưng là rất lớn. Tần số xuất hiện của các từ trong câu hỏi (các giá trị của đặc trưng) có thể được xem như là giá trị trọng số, nó biểu thị cho tầm quan trọng của một từ trong câu hỏi. Không gian đặc trưng bag-of-word còn được gọi là unigram. Unigram là một trường hợp đặc biệt của các đặc trưng n-gram.Để trích xuất các đặc trưng n-gram, bất 9 kỳ n từ liên tiếp nhau trong một câu hỏi sẽ được xem như là một đặc trưng.Ngoài unigram, còn có thêm 2 loại n-gram thường được sử dụng là bigram, trigram. Cụ thể: + Bigram: lấy lần lượt 2 từ liên tiếp nhau trong câu. + Trigram : lấy lần lượt 3 từ liên tiếp nhau trong câu. 1.6.2. Các đặc trưng về cú pháp Một vài loại đặc trưng khác có thể được trích rút từ cấu trúc cú pháp của câu hỏi.Sau đây là các loại đặc trưng thường được sử dụng nhất. 1.6.2.1. POS Tags và Tagged Unigrams POS tags cho biết nhãn từ loại của mỗi từ trong câu hỏi như NN (Noun- danh từ), JJ (adjective- tính từ), RB (Adverb – trạng từ), Việc gán nhãn từ loại (POS tags) cũng đóng một vai trò quan trọng trong việc phân loại câu hỏi. Các danh từ trong câu hỏi đại diện cho các đối tượng hay các thực thể cần hỏi tới. Vì thế, ta cần xác định từ loại của các từ trong câu hỏi. Ngoài ra, còn có một đặc trưng khác tên là tagged unigram. Đặc trưng này đơn giản là unigrams tăng cường với POS tags. Xét tagged unigram thay vì unigrams bình thường có thể giúp bộ phân loại phân biệt một từ với các thẻ khác như là hai đặc trưng khác nhau. 1.6.2.2. Từ đầu (head word) Để trích xuất head word trong một câu hỏi, một bộ phân tích cú pháp được đưa ra. Nhiệm vụ của bộ phân tích cú pháp là phân tích một câu đưa vào thành các thành phần như chủ từ, động từ, chủ ngữ, động ngữ, .... Kết quả trả về của bộ phân tích cú pháp sẽ là một cây cú pháp có nút gốc là ROOT. Các nút khác là các thành phần trong câu như đã nói trên kèm theo đó là các nhãn từ loại. Mỗi từ trong câu đóng vai trò như một nút lá. Đối với một câu viết bằng ngôn ngữ tự nhiên là. Hình 1.6 dưới đây là cây phân tích cú pháp sử dụng bộ phân tích cú pháp Berkeley với câu hỏi “What is Australia’s national flower?”. 10 Hình 1.2: Cây phân tích cú pháp sử dụng bộ phân tích Berkeley Ý tưởng của việc trích rút từ đầu từ cây cú pháp đầu tiên được giới thiệu bởi Collins [6]. Ông đã đề xuất một vài luật, được biết như là luật Collins, để xác định từ đầu của một câu. Xem xét một luật ngữ pháp X → Y1...Yn trong đó X và Yi là non- terminal trong một cây cú pháp. Một thuật toán sử dụng tập các luật có sẵn để xác định Y1...Yn là từ đầu hoặc một cây con chứa nó. Quá trình này sẽ được lặp lại cho đến khi một head word được tìm thấy. 1.6.2.3. Biểu thức chính quy Trong thực tế, một số câu hỏi vốn không có từ đầu. Chẳng hạn như với câu hỏi “What is biosphere ?”, không có từ đầu nào phù hợp để góp phần phân loại như là “definition”. Vấn đề tương tự cũng xuất hiện trong câu hỏi “Why does the moon turn orange ?”, không có các từ nào trong câu hỏi này ngoại trừ từ để hỏi giúp bộ phân loại phân loại câu hỏi này là “reason”. Để định nghĩa một đặc trưng thay thế cho từ đầu của câu hỏi, nhóm tác giả Huang đã giới thiệu một vài mẫu biểu thức chính quy để ánh xạ các kiểu của câu hỏi tới một mẫu và sau đó sử dụng mẫu tương ứng như là đặc trưng. Danh sách các mẫu của Huang [15] như sau: DESC:def pattern 1 Các câu hỏi bắt đầu bằng what is/are, không bắt buộc theo sau nó là a, an, hoặc the và tiếp theo là 1 hoặc nhiều từ. DESC:def pattern 2 Các câu hỏi bắt đầu bằng what do/does và kết thúc là mean. ENTY:substance pattern Các câu hỏi bắt đầu là what is/are và kết thúc là composed of/made of/made out of. DESC:desc pattern Các câu hỏi bắt đầu với what does và kết thúc là do. ENTY:term Các câu hỏi bắt đầu là what do you call. DESC:reason pattern 1 Các câu hỏi bắt đầu là what causes/cause. 11 DESC:reason pattern 2 Các câu hỏi bắt đầu bằng What is/are và kết thúc là used for. ABBR:exp pattern Các câu hỏi bắt đầu bằng What does/do và kết thúc với stand for. HUM:desc pattern Các câu hỏi bắt đầu với Who is/was và theo sau nó là một từ bắt đầu là một kí tự viết hoa. Nếu một câu hỏi so khớp với một vài các luật trên thì đặc trưng tương ứng sẽ được sử dụng. Biểu diễn các đặc trưng tương tự công thức (2.2), do đó tên mẫu có thể được xem xét như là một phần tử và giá trị đặc trưng sẽ là 1 nếu câu hỏi so khớp với một mẫu. Ví dụ cho câu hỏi “What is biosphere ?”, các đặc trưng có thể được biểu diễn như sau: {(DESC:def-pattern1, 1)} 1.6.3. Các đặc trưng ngữ nghĩa WordNet là một kho từ vựng tiếng anh lớn, trong đó một tập hợp các từ đồng nghĩa được nhóm lại với nhau gọi là synset.WordNet là một công cụ hữu ích để phân tích ngữ nghĩa của từ và được sử dụng rộng rãi trong phân loại câu hỏi. Sử dụng WordNet để phân loại câu hỏi thông qua hypernyms: Y là một hypernyms của X nếu ý nghĩa của Y bao hàm ý nghĩa của một hoặc nhiều từ khác cùng loại của X. Ví dụ, hypernyms của từ “city” là “municipality”, hypernyms của “municipality” là “urban area” và cứ như vậy, cấu trúc đi từ nghĩa cụ thể đến nghĩa khái quát hơn. Ví dụ cho một cấu trúc hypernyms của từ “capital”: Capital -- (a seat of govement) =>seat -- (a center of authority (as a city from which authority is exercised)) =>center, centre, middle, heart, eye -- (an are that is approximantely central within some larger region) =>area, country -- (a particular geographical region of indefinite boundary) =>region -- (a large indefinite location on the surface of the Earth) =>location -- (a point or extent in space) =>object, physical object -- (a tangible and visible entity) =>physical entity -- (an entity that has physical existence) =>entity -- (that which is perceived or known or inferred to have its own distinct existence) 12 Chương 2: MỘT SỐ MÔ HÌNH HỌC MÁY TRONG PHÂN LOẠI CÂU HỎI 2.1. Thuật toán Naïve Bayes 2.1.1. Định lý Thuật toán Naïve Bayesdựa trên định lý Bayes được phát biểu như sau: | | Trong đó: * P(X): Xác suất của sự kiện X xảy ra, không quan tâm đến Y * P(Y): Xác suất của sự kiện Y xảy ra, không quan tâm đến X * P(X|Y): Xác suất (có điều kiện)của sự kiệnX xảy ra, nếu biết rằng sự kiệnY xảy ra * P(Y|X): Xác suất hậu nghiệm của Y nếu biết X Naïve Bayes classifer là một bộ phân loại xác suất dựa trên việc ứng dụng định lý Bayes với giả định độc lập bền vững [13]. Một Naïve Bayes classifer độc lập điều kiện giả định rằng sự hiện diện (hay không hiện diện) của một đặc trưng của một lớp học là không liên quan đến sự có mặt (hay thiếu vắng) của bất kỳ đặc trưng nào khác. Áp dụng cho bài toán phân loại, các dữ kiện cần có: * D: tập dữ liệu huấn luyện đã được vector hóa dưới dạng ⃗ * Ci: phân lớp i, với i={1,2,,m} * Các thuộc tính x1,x2,,xn độc lập điều kiện đôi một với nhau Theo định lý Bayes: | | Theo tính chất độc lập điều kiện: | ∏ | | | | Khi đó, luật phân lớp cho các tài liệu mới là: ∏ | Trong đó: 13 * P(Ci): được tính dựa trên tần suất xuất hiện tài liệu trong tập huấn luyện. * P(xk|Ci): được tính từ những tập thuộc tính đã được tính trong quá trình huấn luyện. 2.1.2. Thuật toán Các bước thực hiện thuật toán Naïve Bayes như sau: Bước 1: Huấn luyện Naïve Bayes dựa vào tập dữ liệu:  Tính xác suất P(Ci)  Tính xác suất P(xk|Ci) Bước 2: Xnew được gán vào lớp có giá trị lớn nhất theo công thức: ∏ | Thuật toán Naïve Bayes áp dụng cho bài toán phân loại câu hỏi như sau: Giai đoạn huấn luyện: Input: - Các vector đặc trưng của câu hỏi trong huấn luyện. - Tập nhãn/lớp cho từng vector đặc trưng của tập huấn luyện. Output: - Các giá trị xác suất và Giai đoạn phân lớp: Input: - Các vector đặc trưng của câu hỏi trong huấn luyện. - Các giá trị xác suất và ( ) Output: - Nhãn/phân loại của câu hỏi. Gọi P(ck|qj) là xác suất mà câu hỏi qj có khả năng thuộc vào loại ck. Theo định lý Bayes: ( ) 14 Thuật toán Naïve Bayes được tiến hành bằng cách tính trọng số của cácđặc trưng trong câu hỏi ứng với mỗi loại. Phương pháp entropy weighting được giới thiệu để tính toán trọng số như sau: ∑ Trong đó: ai là trọng số của từ i N là tổng số phân loại fit là tần số xuất hiện của từ i trong câu hỏi t ni là tổng số lần xuất hiện của từ i trong tất cả các câu hỏi Khi đó, phân loại cho một câu hỏi mới là: Với ck là loại có xác suất hậu nghiệm lớn nhất (xác suất mà câu hỏi qj có khả năng thuộc vào lớp ckđược tính ở công thức (2.5)) Phân lớp Naïve Bayes giả định độc lập điều kiệnP(qj|ck) như sau: ∏ ( ) 2.2. Thuật toán k-láng giềng gần (k- Nearst Neighbours) Thuật toán phân lớp k-NN là một phương pháp phân loại câu hỏi dựa trên mô hình không gian vector. Theo mô hình này, mỗi câu hỏi được biểu diễn thành một vector: . Mỗi chiều của vector là một từ riêng biệt của câu hỏi. Ý tưởng của thuật toán này như sau: Để phân loại một câu hỏi mới, thuật toán sẽ tính khoảng cách (có thể dựa vào các công thức tính khoảng cách như Euclide, Cosine, ) của câu hỏi này đến tất cả các câu hỏi trong tập huấn luyện để tìm ra k câu hỏi có khoảng cách gần nhất, gọi là k nearest neighbours (k láng giềng gần). Dùng khoảng cách này, đánh trọng số cho tất cả các chủ đề đã có.Khi đó, trọng số của một chủ đề sẽ được tính bằng tổng các khoảng cách từ câu hỏi cần phân loại đến các câu hỏi trong k láng giềng mà có cùng chủ đề đó.Chủ đề nào không xuất hiện trong tập k câu hỏi sẽ có trọng số bằng 0. Sau đó, các chủ đề được sắp xếp theo độ giảm dần của các trọng số và chủ đề có trọng số cao sẽ được chọn làm chủ đề của câu hỏi cần phân loại. Trọng số của chủ đề Ci đối với câu hỏi d được tính như sau: ∑ ( ) ( ) Trong đó: 15 - KNN(d) là k láng giềng gần nhất của câu hỏi d - ( )xác định câu hỏi djthuộc vào phân loại Ci với: ( ) { - sim(d,dj) là độ giống nhau giữa câu hỏi cần phân loại d và câu hỏi dj. Để tính khoảng cách này, người ta sử dụng độ đo cosin như sau: ∑ ∑ Trong đó: là trọng số của từ đặc trưng thứ i của câu hỏi d1 và d2. 2.3. Máy Vector hỗ trợ - SVM Giải thuật máy vector hỗ trợ SVM (Support Vector Machine) ra đời từ lý thuyết học thống kê do Vapnik và Chervonenkis xây dựng năm 1995 [2]. Đây là một giải thuật phân lớp có hiệu quả cao và đã được áp dụng nhiều trong lĩnh vực khai phá dữ liệu và nhận dạng. Ban đầu thuật toán SVM được thiết kế để giải quyết bài toán phân lớp nhị phân.Bài toán cơ bản như sau: Cho trước n điểm trong không gian d chiều (mỗi điểm thuộc vào một lớp kí hiệu là +1 hoặc -1), mục đích của giải thuật SVM là tìm một siêu phẳng (hyperplane) phân hoạch tối ưu cho phép chia các điểm này thành hai phần sao cho các điểm cùng một lớp nằm về một phía với siêu phẳng này.Hình 2.2 dưới đây minh họa một phân lớp với SVM trong mặt phẳng. Cho tập dữ liệu huấn luyện {( với và là một số nguyên xác định lớp của xi. Siêu phẳng tối ưu phân tập dữ liệu này thành hai lớp là siêu phẳng có thể tách rời dữ liệu thành hai lớp riêng biệt với lề lớn nhất. Mỗi siêu phẳng đều có thể được viết dưới dạng một tập hợp các điểm x thỏa mãn: Trong đó: w là một vector pháp tuyến của siêu phẳng và b đóng vai trò là tham số của mô hình. Để tìm được siêu phẳng phân cách có lề cực đại, xây dựng các vector hỗ trợ và các siêu phẳng H1, H2 song song với H và có cùng khoảng cách đến H. Khi đó, với mọi xi trong tập huấn luyện ta có 2 bất phương trình sau: w.xi + b +1 với yi = +1 w.xi + b -1 với yi = -1 16 Và được viết lại như sau: yi(w.xi + b) +1 hoặc yi(w.xi + b) - 1 0 Hình 2.2: Siêu phẳng với lề cực đại cho một SVM phân tách dữ liệu thuộc hai lớp. Lúc này, những support vector xi thỏa mãn phương trình w.xi + b -1 thì nằm trên siêu phẳng H1, và thỏa mãn phương trình w.xi + b +1 thì nằm trên siêu phẳng H2. Khoảng cách lề giữa siêu phẳng H1 và H2 được tính như sau: Gọi x0 là một điểm nằm trên siêu phẳng H và x1 là điểm nằm trên siêu phẳng H1. Như vậy, (x0-x1)vuông góc với 2 siêu phẳng này. Các điểm này thỏa mãn hệ phương trình sau: { Lấy hai đẳng thức của(2.12) trừ cho nhau, ta được: Vì vuông góc với siêu phẳng H và w cũng vuông góc với siêu phẳng H, do đó và w song song với nhau, như vậy một dữ liệu mới thêm vào thỏa mãn: | | ‖ ‖ ‖ ‖ Từ công thức (3.13) và (3.14) ta có được khoảng cách giữa siêu phẳng H và H1 là: ‖ ‖ ‖ ‖ 17 Tương tự như vậy, gọi x0 là một điểm nằm trên siêu phẳng H và x2 là điểm nằm trên siêu phẳng H2. Ta có hệ phương trình sau: { Như vậy, khoảng cách giữa siêu phẳng H và H2 là: ‖ ‖ ‖ ‖ Từ (2.15) và (2.17) suy ra, khoảng cách phân hoạch giữa siêu phẳng H1và H2là ‖ ‖. Do đó, để có biên lớn nhất thì ‖ ‖ phải nhỏ nhất hay nói cách khác là giải bài toán tối ưu tìm ‖ ‖ với ràng buộc gi(x)= yi(w.xi + b) 1 với i=1,2,,n. Để giải bài toán tối ưu tìm ‖ ‖ với ràng buộc gi(x)=yi(w.xi + b) 1 với i=1,2,,n. Ta đưa về phương trình Lagrange, bài toán trên trở thành: { ‖ ‖ ∑ } Trong đó 0} là các nhân tử Lagrange. Khi đó, tất cả các điểm không nằm trên lề nghĩa là đều không ảnh hưởng đến giá trị hàm mục tiêu vì ta có thể chọn . Áp dụng điều kiện Karush–Kuhn–Tucker, vector w được tính theo công thức sau: ∑ Để dữ liệu có thể tách rời tuyến tính, không gian đặc trưng nên được ánh xạ vào không gian nhiều chiều. Việc ánh xạ được thực hiện bởi một hàm hạt nhân. Cho hàm hạt nhân trong đó có 2 điểm từ không gian đầu vào và ánh xạ nó đến 1 số thực chỉ ra độ tương tự của nó. Với mọi điểm , hàm hạt nhân thỏa mãn: ( ) ⟨ ( )⟩ Trong đó được ánh xạ từ không gian đầu vào X đến một điểm dữ liệu của không gian đặc trưng H. Để ứng dụng hàm hạt nhân trong phân lớp SVM, công thức (2.18) được viết lại như sau: 18 ∑ ∑∑ Với là hạt nhân đo độ tương tự giữa . Công thức (2.21) có thể được viết lại dưới dạng sau: ∑ ∑∑ Có 4 loại hàm hạt nhân được giới thiệu: linear, popynomial, radial basis và sigmoid. Loại đơn giản nhất là hàm hạt nhân tuyến tính cho hai câu hỏi được xác định như sau: ( ) ∑ 2.4. Hiệu suất trong phân loại câu hỏi Thông thường hiệu suất của bộ phân loại câu hỏi được đo bằng việc tính toán chính xác trong đó phân loại vào một tập kiểm tra cụ thể. Độ chính xác của phân loại câu hỏi được định nghĩa như sau: 19 Chương 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ 3.1. Lựa chọn bộ phân loại Như đã trình bày trong phần 2.7, bộ phân loại SVM được chứng minh là vượt trội hơn so với các bộ phân loại khác.Chính vì vậy, khóa luận quyết định lựa chọn bộ phân loại SVM để thực hiện thực nghiệm và đánh giá.Để xây dựng bộ phân loại SVM, thư viện LIBSVM được áp dụng trong quá trình huấn luyện và kiểm thử. 3.2. Môi trường và công cụ sử dụng trong thực nghiệm Cấu hình phần cứng, phần mềm các gói đi kèm thực nghiệm được sử dụng trong luận văn được mô tả trong hai bảng sau đây: Bảng 3.1: Thông tin phần cứng STT Thành phần Chỉ số 1 CPU Intel Core i3 1.8GHZ 2 RAM 2GB 3 Hệ điều hành Windows Bảng 3.2: Các công cụ phần mềm được sử dụng STT Tên phần mềm Chức năng Nguồn 1 LIBSVM 3.21 Phân loại câu hỏi ~cjlin/libsvm/ 2 Eclipse Java EE Tạo môi trường để viết chương trình xây dựng tập tin huấn luyện nloads/index-helios.php 3 Python 2.7.12 Tạo môi trường để kiểm thử với LibSVM https://www.python.org/dow nloads/release/python-2712/ 3.3. Tập dữ liệu thử nghiệm Tập dữ liệu được sử dụng trong thực nghiệm được tạo ra bởi Li và Roth.Chúng cung cấp một tập dữ liệu các câu hỏi đã được sử dụng rộng rãi trong các nghiên cứu về phân loại câu hỏi và được biết như là tập dữ liệu UIUC hoặc tập dữ liệu TREC.Đối với tập dữ liệu TREC cung cấp các loại câu hỏi dưới dạng các tập tin theo định dạng giống như XML. Trên trang web của UIUC thì cung cấp tập tin danh sách các câu hỏi mà trong đó các câu hỏi đã được gán nhãn phân loại sẵn. Các tập tin được sắp xếp theo thứ tự 1000,2000, 3000, 4000 và 5500 câu hỏi đã được gán nhãn. Thêm vào đó, UIUC cung cấp một tập tin để kiểm tra gồm 500 câu hỏi trong TREC 10.Từ đó, em quyết 20 định chọn tập huấn luyện dựa trên kho dữ liệu câu hỏi UIUC cho quá trình thực nghiệm của mình. Ví dụ của một dòng dữ liệu trong tập dữ liệu UIUC: HUM:ind Who was The Pride of the Yankees ? Nguyên tắc phân loại đã được sử dụng để gán nhãn cho các câu hỏi là nguyên tắc phân loại đã được giải thích trong chương 1.Nó bao gồm 6 lớp thô và 50 lớp mịn. 3.4. Xử lý dữ liệu Để bắt đầu sử dụng với bộ thư viện này, ta cần phải xây dựng một tập tin huấn luyện theo đúng dịnh dạng. Định dạng của tập tin chứa dữ liệu huấn luyện và tập tin kiểm thử là: :: Trong đó: là giá trị đích của tập huấn luyện. Đối với việc phân loại, nó là một số nguyên xác định một lớp. là một số nguyên bắt đầu từ 1. Cụ thể trong bài toán phân loại nó đại diện cho các đặc trưng. là một số thực. Giá trị này thể hiện mức độ liên quan của đặc trưng đối với một phân loại nằm trong khoảng [-1,1]. Do các đặc trưng trong phân loại câu hỏi đều là đặc trưng nhị phân nên lúc huấn luyện giá trị này sẽ là 1. Câu hỏi “Who was the Pride of Yankees” sẽ được chuyển thành như sau: 44 1:1 15:2 24:2 98:1 235:1 1934:1 4376:1 ở đó số đầu tiên (44) cho biết số của lớp và các cặp còn lại (đặc trưng, giá trị) được phân cách bởi một khoảng trống trong khi trong mỗi cặp được phân cách bởi dấu hai chấm (:). Hơn nữa các cặp đặc trưng này nên được sắp xếp theo thứ tự tăng dần của số các đặc trưng. Khi tất cả các tập dữ liệu huấn luyện và kiểm tra được chuyển về định dạng như trên, sau đó thực hiện huấn luyện bộ phân loại với tập dữ liệu huấn luyện và kiểm tra lại nó trên tập dữ liệu kiểm tra độc lập. 3.5. Huấn luyện và kiểm thử với LibSVM Sau khi có file với định dạng được chấp nhận bởi thư viện LIBSVM, thực hiện huấn luyện và test. Trong giai đoạn này, khóa luận sử dụng ngôn ngữ lập trình Python để thực hiện vì tính đơn giản và tiện lợi. Cụ thể như sau: - Load thư viện Libsvm : 21 from svmutil import * - Đọc dữ liệu: Load dữ liệu huấn luyện: yTrain là tập nhãn lớp, xTrain sẽ là dữ liệu để train yTrain, xTrain = svm_read_problem('train_5000_fine_unigram.txt') Load dữ liệu test: yTest là tập nhãn lớp, xTest sẽ là dữ liệu để test yTest, xTest = svm_read_problem('TREC_10_fine_unigram.txt') - Xây dựng mô hình phân lớp: m = svm_train(yTrain, xTrain, '-t 0 -h 0') Ở đây, tham số „-t 0‟ chỉ loại hàm nhân được lựa chọn là tuyến tính (Linear), tham số „-h 0‟ tức là không dùng tính năng co lại khoảng cách giữa các lớp - Phân loại câu hỏi dựa trên dữ liệu test và mô hình thu được ở trên: p_label, p_acc, p_val = svm_predict(yTest, xTest, m) Kết quả thu được là p_label: danh sách các nhãn dự đoán của từng câu hỏi, p_acc là độ chính xác của phân lớp 3.6. Kết quả thực nghiệm Độ chính xác phân loại sau khi thử nghiệm với bộ phân loại SVM, lựa chọn đặc trưng unigram, bigram, sử dụng cách tính trọng số entropy như sau: Bảng 3.3: Độ chính xác phân loại trên tập thô với đặc trưng unigram và bigram Đặc trưng Độ chính xác Unigram 88,2% Bigram 85,6% Bảng 3.4: Độ chính xác phân loại trên tập mịn với đặc trưng unigram và bigram Đặc trưng Độ chính xác Unigram 80,2% Bigram 73,8% 3.7. Kết luận Như vậy, sau khi thực nghiệm đánh giá bộ phân loại SVM sử dụng 2 đặc trưng unigram và bigram, nhận thấy rằng kết quả phân loại đạt được với độ chính xác khá cao (80.2% trên tập mịn). Đặc trưng unigram cho kết quả phân loại cao hơn đặc trưng bigram. 22 TỔNG KẾT Phân loại câu hỏi là một vấn đề khó.Thực tế là máy cần phải hiểu được câu hỏi và phân loại nó vào loại chính xác.Điều này được thực hiện bởi một loạt các bước phức tạp.Luận văn này đã trình bày các kiến thức cơ bản của bài toán phân loại câu hỏi và giới thiệu một số thuật toán để giải quyết bài toán phân loại.Tuy nhiên, luận văn chỉ mang tính tìm hiểu và ứng dụng cái đã có, không có đề xuất hay cải tiến gì để làm tăng độ chính xác phân loại. Ngoài ra, luận văn chỉ thực nghiệm trên ngôn ngữ Tiếng Anh mà chưa mở rộng thực nghiệm sang ngôn ngữ Tiếng Việt. Trong tương lai gần, hướng phát triển trước mắt của luận văn là cần tìm hiểu và kết hợp các đặc trưng khác để làm tăng độ chính xác phân loại.Thực hiện phân loại trên nhiều ngôn ngữ hơn nữa.