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

phân lớp mịn sẽ xác định tập các nhãn lớp con 20 C3 = Fine_Classifier(C2) với |C3| 5 C1 và C3 là kết quả đầu ra được sử dụng cho quá trình tìm câu trả lời. Hình 1.5: Bộ phân lớp đa cấp của Li và Roth 1.6. Các đặc trƣng phân loại Trong phương pháp tiếp cận máy học, từ tập dữ liệu có sẵn ta rút ra những đặc trưng phân loại đề từ đó đưa ra huấn luyện. Các đặc trưng này đơn giản chỉ là một hoặc nhiều từ nằm đâu đó trong câu hỏi. Chúng không quyết định câu hỏi đó thuộc về phân loại nào, chỉ là cơ sở để qua qua trình học dự đoán một câu hỏi thuộc về một phân loại. Các đặc trưng trong phân loại câu hỏi có thể được chia thành 3 loại khác nhau: các đặc trưng về từ vựng, các đặc trưng về cú pháp và các đặc trưng về ngữ nghĩa. Sau đây là một số các đặc trưng được sử dụng phổ biến trong phân loại câu hỏ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: 21 { ( )} 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. Hãy cùng xem xét câu hỏi: “How many Grammys did Michael Jackson win in 1983 ?” được biểu diễn như trong (1.2) như sau: x= {(How, 1), (many, 1), (Grammys, 1), (did, 1), (Michael, 1), (Jackson, 1), (win, 1), (in, 1), (1983, 1), (?,1)} 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 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. Với ví dụ ở trên thì “How-many” là một đặc trưng bigram và có thể được thêm vào vector đặc trưng.Tất cả các đặc trưng về từ vựng, cú pháp và ngữ nghĩa có thể được thêm vào không gian đặc trưng và mở rộng vector đặc trưng trên. Trong thực tế các vector đặc trưng vẫn có thể được biểu diễn theo (1.2), trong khi các đặc trưng mới có thể được coi như từ loại mới. Chẳng hạn đặc trưng bigram “How-many” có thể được xem như là một từ loại mới và cặp {(How-many,1)} sẽ được thêm vào vector đặc trưng khi đặc trưng bigram được trích xuất. Tất nhiên điều này sẽ làm tăng kích thước của không gian đặc trưng và các câu hỏi sẽ được biểu diễn với số chiều cao. Ngoài ra, trong đặc trưng bigram cứ 2 từ liên tiếp trong tập dữ liệu được xem là đặc trưng, nhưng hầu hết trong đó lại dư thừa và không hiển thị trong dữ liệu.Vì vậy, chúng ta chỉ nên xem xét hai từ đầu tiên của một câu hỏi là đặc trưng bigram và như vậy, kích thước của không gian đặc trưng sẽ nhỏ hơn rất nhiều. Hãy cùng xem xét câu hỏi ví dụ “How many people in the world speak French?”, chỉ có ý nghĩa bigram trong câu hỏi này là “How-many” trong khi các phần còn lại là không hữu ích. Ngoài các đặc trưng trên, nhóm tác giả Huang đã giới thiệu đặc trưng từ hỏi wh- word.Đặc trưng wh-word được hiểu các câu hỏi bắt đầu bằng “wh”.Chẳng hạn wh- 22 word của câu hỏi “What is the longest river in the world?” là what. Đã có 8 loại wh- word được đưa ra [15]: what, which, when, where, who, how, why, và rest, với rest được hiểu là các loại câu hỏi còn lại không thuộc 8 loại trên. Ví dụ câu hỏi “Name a food high in zinc” là một câu hỏi thuộc loại rest. Nhóm tác giả Huang [15] còn giới thiệu một đặc trưng từ vựng khác là word shapes (khuôn dạng từ). Loại đặc trưng này dùng để chỉ tính chi tiết của các đơn từ. Đã có 5 loại đặc trưng word shapes được giới thiệu: all digits, all lower case, all upper case, mixed case and other. lunsom cùng các đồng nghiệp (2006) đã giới thiệu chiều dài của câu hỏi như là đặc trưng về từ vựng. Nó đơn giản là số từ trong một câu hỏi. Bảng 1.2 dưới đây là danh sách các đặc trưng từ vựng với câu hỏi “How many Grammys did Michael Jackson win in 1983 ?”. Các đặc trưng được biểu diễn giống công thức (1.2). Bảng 1.2: Danh sách các đặc trưng từ vựng của ví dụ Feature Space Features Unigram {(How,1) (many,1) (Grammys,1) (did,1) (Michael,1) ( Jackson,1) (win,1) (in,1) (1983,1) (?,1) } Bigram {(How-many, 1) (many-Grammys,1) (Grammys-did,1) (did- Michael,1) (Michael-Jackson,1) (Jackson-win,1) (win-in,1) (in-1983,1) (1983-?,1)} Trigram {(How-many-Grammys,1) (many-Grammys-did,1) (Grammys-did-Michael,1) (did-Michael-Jackson,1) (Michael- Jackson-win,1) (Jackson-win-in,1) (win-in-1983,1) (in-1983- ?,1)} Wh-word {(How,1)} Word-shapes {(lowercase,4) (mixed,4) (digit,1) (other,1)} Question-length {(question-len, 10)} 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ừ), Ví dụ câu hỏi sau “How can I 23 register my website in Yahoo for free ?” với POS tags của nó (Các nhãn từ loại ở đây theo hệ thống Penn Treebank): How_WRB can_MD I_PRP register_VB my_PRP$ website_NN in_IN Yahoo_NNP for_IN free_JJ ?_. 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. Một vài nghiên cứu trong phân loại câu hỏi thêm tất cả các POS tags của câu hỏi vào vectơ đặc trưng. Không gian đặc trưng này đôi khi được gọi như bag-of-POS tags. Các đặc trưng bag-of-POS tags của câu hỏi trên như sau: {(WRB,1), (MD,1), (PRP,1), (VB,1), (PRP$,1), (NN,1), (IN,1), (NNP,1), (IN,1), (JJ,1)} 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. Ví dụ trên được biểu diễn với các đặc trưng tagged unigram như sau: {(How_WRB,1), (can_MD,1), (I_PRP,1), (register_VB,1), (my_PRP$,1), (website_NN,1), (in_IN,1), (Yahoo_NNP,1), (for_IN,1), (free_JJ,1), (?_,1)} 1.6.2.2. Từ đầu (head word) Li và Roth đã sử dụng đặc trưng head chuck như là một đặc trưng cú pháp cho cách tiếp cận của mình. Head chuck được định nghĩa là cụm danh từ và cụm động từ đằng sau từ để hỏi. Ví dụ, head chuck của câu hỏi “What is the oldest city in Canada ?” là cụm danh từ “the oldest city in Canada”. Ngoài ra, Krishnan (2005) cũng sử dụng đặc trưng được gọi là informer span.Đặc trưng này có thể được hiểu là một cụm từ mà cung cấp đủ thông tin để giúp phân loại câu hỏi. Ví dụ với câu hỏi “What is the tallest mountain in the world ?” thì informer span được xác định là “tallest mountain”. Tuy nhiên, cả 2 cách tiếp cận này đều được chứng minh rằng chứa thông tin nhiễu [15]. Chẳng hạn, với câu hỏi “What is a group of turkeys called ?” thì head chuck và informer span của nó là “group of turkeys”, cụm từ này có thể hướng câu hỏi được phân vào loại HUMAN: group trong khi loại của chúng phải là ENTY: animal. Để giải quyết vấn đề này, nhóm tác giảHuang[15] đã đề xuất đặc trưng head word dựa trên ý tưởng một từ trong câu hỏi đại diện cho một đối tượng cần hỏi đến. Xác định chính xác từ đầu có thể cải thiện đáng kể độ chính xác của việc phân loại do 24 nó là từ chứa thông tin nhất trong câu hỏi. Ví dụ cho câu hỏi “What is the oldest city in Canada ?” từ đầu là “city”. Từ “city” trong câu hỏi này có thể có đóng góp cao cho bộ phân loại để phân loại câu hỏi này là LOC: city. Để 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à ngôn ngữ tiếng Anh, các luật ngữ pháp tiếng Anh được sử dụng để tạo ra cây cú pháp. Một số bộ phân tích cú pháp được giới thiệu như: Chaniak parser (Charniak and Johnson, 2005), Stanford parser (Klein and Manning, 2003) và Berkeley parser (Petrov and Klein, 2007). 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?”. Hình 1.6: 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 (Bảng 1.3), để 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. Bảng 1.3: Danh sách các luật của Collins Parent Direction Priority List S Left VP S FRAG SBAR ADJP SBARQ Left SQ S SINV SBARQ FRAG 25 SQ Left NP VP SQ NP NP Right by position NP NN NNP NNPS NNS NX PP Left WHNP NP WHADVP SBAR WHNP Left NP WHPP Right WHNP WHADVP NP SBAR Thuật toán 1: Thuật toán trích xuất từ đầu của câu hỏi procedure Extract-Question-Headword(tree, rules) if Terminal?(tree) then return tree else child ← Apply-Rules(tree, rules) return Extract-Question-Headword(child, rules) end if end procedure Áp dụng thuật toán với câu hỏi ở trên, ta tìm headword của nó như sau: bắt đầu từ đỉnh của cây phân tích, ta có S ARQ → WHNP SQ, theo luật Collins việc tìm kiếm được thực hiện từ trái qua phải, tìm con đầu tiên là một trong số SQ S SINV SBARQ FRAG, như vậy con đầu tiên sẽ là SQ. Tiếp tục tìm kiếm tương tự với SQ → V Z NP là NP. Theo luật Collins thì NP → NP JJ NN được tìm kiếm từ vị trí phải nhất, như vậy NN sẽ là nút terminal và từ “flower” sẽ là từ đầu của câu hỏi. Babak Loni [3] đã sửa đổi các luật Collins như trong bảng 1.4 sau: Bảng 1.4: Danh sách luật Collins sửa đổi Parent Direction Priority List ROOT Left by Category S, SBARQ S Left by Category VP, FRAG, SBAR, ADJP SBARQ Left by Category SQ, S, SINV, SBARQ, FRAG SQ Left by Category NP, VP, SQ NP Right by position NP, NN, NNP, NNPS, NNS, NX PP Left by Category WHNP, NP, WHADVP, SBAR 26 WHNP Left by Category NP, NN, NNP, NNPS, NNS, NX WHADVP Right NP, NN, NNP, NNPS, NNS, NX WHADJP Left by Category NP, NN, NNP, NNPS, NNS, NX WHPP Right by position WHNP, WHADVP, NP, SBAR VP Right by position NP, NN, NNP, NNPS, NNS, NX, SQ, PP SINV Left by Category NP NX Left by Category NP, NN, NNP, NNPS, NNS, NX, S Tuy nhiên, không phải với bất kỳ câu hỏi nào thì thuật toán trên cũng trích xuất được từ đầu chính xác. Hãy cùng xem xét cây phân tích của câu hỏi sau “Which country are Godiva chocolates from ?” Hình 1.7. Cây phân tích của câu hỏi “Which country are Godiva chocolates from ?” Nếu tuân theo quy tắc trên thì từ đầu được trích xuất là “chocolates” trong khi từ đầu chính xác góp phần để phân câu hỏi vào loại đúng phải là “country”. Để giải quyết vấn đề này, nhóm tác giả Silva[7] đã giới thiệu một luật có tên là non-trivial . Các luật này được mô tả như sau:  Nếu SBARQ chứa 1 con WHXP (WHXP gồm Wh-phrases: WHNP, WHPP, WHADJP, WHADVP) với con đó có ít nhất 2 con nữa thì cây con có đỉnh WHXP sẽ được trả về.  Sau khi áp dụng quy tắc trên, nếu kết quả trả về là WHNP có chứa 1 con NP với nút lá là một đại từ sở hữu (POS) thì cây con có đỉnh NP sẽ được xem xét. Áp dụng quy tắc này với câu hỏi “What country capital’s is Tirana”sẽ cho được kết quả từ đầu chính xác là “country”. 27  Một số trường hợp đặc biệt nếu head word của câu hỏi là một trong các từ “name”, “type”, “kind”, “part”, “genre”, “group”, và các node anh em của nó là PP thì cây con có đỉnh PP sẽ được trích xuất và thuật toán tiếp tục được tiến hành. Như vậy, với câu hỏi “What is the proper name for a female walrus” thì head word theo cách xác định ban đầu là từ “name” sẽ được xác định lại là từ “walrus” giúp phân loại câu hỏi vào loại ENTY: animal (Hình1.8 ). Hình 1.8: Cây phân tích cú pháp cho câu hỏi “What is the proper name for a female walrus” 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. 28 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. 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 Các đặc trưng ngữ nghĩa được trích rút dựa trên ngữ nghĩa của các từ trong câu hỏi.Chúng tôi trích rút các kiểu khác nhau của các đặc trưng ngữ nghĩa.Hầu hết các đặc trưng ngữ nghĩa đòi hỏi nguồn dữ liệu thứ 3 như là WordNet (Fellbaum, 1998), hoặc là một từ điển để trích rút thông tin ngữ nghĩa cho các câu hỏi. 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) 29 =>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) Hypernyms cho phép biểu diễn trừu tượng hơn các từ cụ thể, nó có thể là các đặc trưng hữu ích cho phân loại câu hỏi.Tuy nhiên trích rút hypernyms không phải dễ dàng. Có 4 thách thức cần phải được giải quyết để đạt được các đặc trưng hypernyms: 1. Từ(các từ) nào trong câu hỏi mà chúng ta nên tìm hypernyms? 2. Đối với các từ (các từ) ứng viên, thẻ từ loại nào nên được xem xét? 3. Đối với các từ ứng viên, tăng cường với thẻ từ loại của chúng có thể có ý nghĩa khác nhau trong WordNet. Vậy, nghĩa nào là nghĩa mà được sử dụng trong câu hỏi? 4. Để có kết quả hypernyms tốt nhất, nên xét độ sâu hypernyms là bao nhiêu? Có 2 kịch bản khác nhau được đưa ra để giải quyết thách thức đầu tiên: xem xét headword như là một ứng cử viên cho việc mở rộng từ hoặc mở rộng tất cả các từ trong câu hỏi. Cách tiếp cận thứ 2 đã được chứng minh gây nhiễu thông tin và như vậy, headword sẽ được giới thiệu như là một từ mà chúng ta nên tìm hypernyms. Vấn đề thứ 2 được giải quyết như sau: ánh xạ nhãn từ loại của từ đầu được đưa ra vào nhãn từ loại của nó trong Wordnet (các nhãn từ loại trong Wordnet gồm: POS.NOUN và POS.ADJECTIVE, POS.ADVERB và POS.VERB). Việc giải quyết câu hỏi thứ 3 thực chất là vấn đề định hướng ngữ nghĩa của từ (word sense disambiguation-WSD).Thuật toán Lesk (Lesk, 1986) là một thuật toán cổ điển sử dụng cho WSD. Thuật toán dựa trên giả định rằng: các từ trong bối cảnh có xu hướng chia sẻ một chủ để phổ biến nào đó. Nhóm tác giả Huang[15] đã giới thiệu thuật toán Lesk‟s WSD để xác định ngữ nghĩa đúng của từ. Với câu hỏi thứ 4, Huang[15] đã chứng minh được rằng việc mở rộng hypernyms của headword đạt kết quả tốt nhất ở mức thứ 6 của cây hypernyms. 30 Chƣơng 2: MỘT SỐ MÔ HÌNH HỌC MÁY TRONG PHÂN LOẠI CÂU HỎI Hiện nay có rất nhiều kỹ thuật học máy được áp dụng để giải quyết bài toán phân lớp như K láng giềng gần nhất(Nearest Neighbors - NN), Naïve Bayes (NB), cây quyết định (Decision Tree - DT), Mạng lọc thưa (Sparse Network of Winnows - SNoW) , Máy Vector hỗ trợ (Support Vector Machine - SVM), Mô hình entropy cực đại (Maximum Entropy Models) 2.1. Kiến trúc hệ thống Đưa ra một câu hỏi, bộ phân loại của chúng tôi trích rút ra các đặc trưng từ câu hỏi, kết hợp các đặc trưng và phân loại câu hỏi vào một trong các lớp đã được định nghĩa trước. Giả sử rằng không gian đặc trưng kết hợp là d chiều. Một câu hỏi có thể được biểu diễn như là x = (x1, x2, , xd), trong đó xi là đặc trưng thứ i trong không gian kết hợp. Bộ phân loại là một hàm trong đó ánh xạ một câu hỏi x tới một lớp ci từ một tập các lớp C = {c1, c2, ..., cm}. Hàm này được học trên một tập dữ liệu huấn luyện là các câu hỏi đã gán nhãn. Hình 2.1 minh họa kiến trúc tổng thể của hệ thống phân loại câu hỏi của chúng tôi. Đầu tiên hệ thống trích rút các tập đặc trưng khác nhau từ câu hỏi và sau đó kết hợp chúng lại. Kết hợp của các đặc trưng sẽ đưa vào bộ phân loại huấn luyện và nó dự báo nhãn lớp có khả năng nhất. Hình 2.1: Kiến trúc tổng quan của hệ thống phân loại câu hỏi có giám sát 2.2. Thuật toán Naïve Bayes 2.2.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 31 * 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 ayes 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 đó: * 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.2.2. Thuật toán Các bước thực hiện thuật toán Naïve ayes như sau: ướ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) ước 2: Xnew được gán vào lớp có giá trị lớn nhất theo công thức: 32 ∏ | Cùng xem xét một ví dụ sau: ví dụ dự đoán xem quyết định của người chơi có đi chơi tennis hay không với các điều kiện về thời tiết đã được biết trước. Trong ví dụ này, ta có một bảng dữ liệu huấn luyện như sau: Bảng 2.1: Bảng dữ liệu huấn luyện của ví dụ người chơi tennis Day Outlook Temp. Humidity Wind Playtennis D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Weak Yes D8 Sunny Mild High Weak No D9 Sunny Cold Normal Weak Yes D10 Rain Mild Normal Strong Yes D11 Sunny Mild Normal Strong Yes D12 Overcast Mild High Strong Yes D13 Overcast Hot Normal Weak Yes D14 Rain Mild High Strong No ước 1:  Tính các xác suất P(Ci) Với C1 = “yes” : P(C1) = P(“yes”) = 9/14 Với C2 = “no”: P(C2) = P(“no”) = 5/14  Tính các xác suất P(xk|Ci) - Với thuộc tính Outlook: có các giá trị sunny, overcast, rain P(sunny|yes) = 2/9 P(sunny|no) = 3/5 P(overcast|yes) = 4/9 33 P(overcast|no) = 0/5 P(rain|yes) = 3/9 P(rain|no) = 2/5 - Với thuộc tính Temp: có các giá trị Hot, Cold, Mild P(hot|yes) = 2/9 P(hot|no) = 2/5 P(cold|yes) = 3/9 P(cold|no) = 1/5 P(mild|yes) = 4/9 P(mild|no) = 2/5 - Với thuộc tính Humidity: có các giá trị Normal, High P(normal|yes) = 6/9 P(normal|no) = 1/5 P(high|yes) = 3/9 P(high|no) = 4/5 - Với thuộc tính Wind: có các giá trị Weak, Strong P(weak|yes) = 6/9 P(weak|no) = 2/5 P(strong|yes) = 3/9 P(strong|no) = 3/5 ước 2: Phân lớp Xnew = {sunny, cool, high, strong} Tính các xác suất: P(yes) * P(X new |yes) = 0.005 P(no) * P(X new |no) = 0.021 Vậy Xnew thuộc vào lớp “no” 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à 34 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: ( ) Thuật toán Naïve ayes đượ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.3. 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. 35 Ý 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 đó: - 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.4. 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. an đầ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. à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. 36 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 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: 37 { 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à: ‖ ‖ ‖ ‖ 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: 38 ∑ Để 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: ∑ ∑∑ 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: ( ) ∑ Áp dụng SVM vào phân loại câu hỏi Trước khi sử dụng bộ phân loại SVM, cần chuẩn bị dữ liệu như sau: (1) Thiết kế mô hình cây phân cấp cho tập lớp câu hỏi. (2) Xây dựng tập dữ liệu mẫu đã được gán nhãn cho từng loại câu hỏi. Trong bước này, cần lựa chọn đặc trưng để biểu diễn câu hỏi. Sau khi xây dựng được tập các lớp câu hỏi cùng với tập dữ liệu sẽ tiến hành “học”. Mô hình học như sau: 39 Hình2.3: Sơ đồ phân lớp câu hỏi với SVM 2.5. Một số thuật toán khác  Thuật toán cây quyết định (Decision Tree –DT): là phương pháp xấp xỉ giá trị các hàm mục tiêu rời rạc. Trong đó, hàm học của phương pháp này là một cây có bậc tùy ý. Cây quyết định bao gồm các lá và nhánh, mỗi lá là đại diện cho một lớp và các nhánh là các điều kiện, đặc trưng dẫn đến lớp ở đỉnh lá.  Thuật toán Mạng lọc thưa (Sparse Network of Winnows -SNoW): được sử dụngtrong việc học trên các tập dữ liệu có số lượng đặc trưng lớn. Ứng dụng nhiều trong các bài toán phân đa lớp. Thuật toán này dùng các hàm tuyến tính là các bộ lọc để cập nhật các tập luật. Nó thích hợp cho học trong miền khi các đặc trưng tiềm năng tạo các quyết định sai khác nhau mà không biết mức độ ưu tiên.  Thuật toán Maximum Entropy (ME): Đố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 để ướclượ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 [1]. 2.6. 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: Ngoài ra còn có hai số liệu hiệu suất lớp cụ thể: precision và recall, nó có thể được sử dụng trong vấn đề phân loại câu hỏi. Độ chính xác (precision) và độ hồi tưởng (recall) của một bộ phân loại trên một lớp cụ thể c được định nghĩa như sau: 40 Đối với các hệ thống trong đó một câu hỏi chỉ có thể thuộc về một lớp, một câu hỏi được phân loại đúng nếu như nhãn dự báo là tương tự như nhãn đúng.Nhưng đối với các hệ thống mà cho phép một câu hỏi được phân loại vào nhiều hơn một nhãn lớp, một câu hỏi được phân loại đúng nếu một trong các nhãn lớp dự đoán là tương tự với nhãn đúng. 2.7. Một số kết quả của các tác giả Có nhiều thuật toán khác nhau được sử dụng cho bài toán phân loại câu hỏi, Dell Zhang và Wee Sun Lee [14] đã tiến hành thử nghiệm năm thuật toán khác nhau theo hướng học máy khi xây dựng bộ phân lớp câu hỏi. Năm thuật toán được nhóm tác giả sử dụng thực nghiệm là: Nearest Neighbors (NN), Naïve Bayes (NB), Decision Tree (DT), Sparse Network of Winnows (SNoW) và Support Vector Machine (SVM). Thực nghiệm của nhóm tác giả cụ thể như sau:  Nguyên tắc phân loại được sử dụng trong thực nghiệm là nguyên tắc phân loại hai lớp bao gồm 6 lớp thô và 50 lớp mịn của Li và Roth đã được trình bày trong Bảng 1.1.  Tập dữ liệu huấn luyện và kiểm thử được cung cấp bởi USC, UIUC và TREC. Có khoảng 5.500 câu hỏi được dán nhãn phân chia ngẫu nhiên thành 5 tập dữ liệu huấn luyện có kích thước 1.000, 2.000, 3.000, 4.000 và 5.500 tương ứng. Tập dữ liệu này được gán nhãn thủ công. Mỗi một câu hỏi chỉ thuộc một lớp nhất định. Tập dữ liệu kiểm thử bao gồm 500 câu hỏi đã được gán nhãn.  Lựa chọn đặc trưng: các tác giả đã sử dụng hai đặc trưng là bag-of-words và bag-of-ngrams trong thực nghiệm của mình. Sau 5 lần thử nghiệm với 5 tập dữ liệu có số lượng câu hỏi khác nhau, kết quả thực nghiệm (độ chính xác) lớn nhất đạt được là 80.2% trên phân lớp mịn với đặc trưng được là bag-of-word (xem bảng 2.1). Bảng 2.1: Độ chính xác của phân loại câu hỏi sử dụng các thuật toán học máy khác nhau với đặc trưng bag-of-words trên lớp mịn Thuật toán 1000 2000 3000 4000 5500 41 NN 57.4% 62.8% 65.2% 67.2% 68.4% NB 48.8% 52.8% 56.5% 56.2% 58.4% DT 67.0% 70.0% 73.6% 75.4% 77.0% SNoW 42.2% 66.2% 69.0% 66.6% 74.0% SVM 68.0% 75.0% 77.2% 77.4% 80.2% Từ kết quả thực nghiệm ở trên, ta nhận thấy rằng:  Tập dữ liệu huấn luyện lớn sẽ cho ra kết quả phân loại tốt hơn.  Thuật toán SVM mang lại độ chính xác cao hơn so với các phương pháp còn lại. Đã có rất nhiều kết quả nghiên cứu phân loại câu hỏi trên các ngôn ngữ như Tiếng Anh hay Tiếng Pháp. Tuy nhiên, các nghiên cứu trên ngôn ngữ Tiếng Việt thì lại rất ít. Nhóm tác giả Phuong Le-Hong, Xuan-Hieu Phan, và Tien-Dung Nguyen [10] đã tiến hành thực nghiệm trên tập dữ liệu gồm 1000 câu hỏi, các câu hỏi chủ yếu hỏi về Tập đoàn FPT và được phân vào 13 phân loại thô như sau: ACTION (action), CONC (concept), DESC (description), DTIME (datetime), EVT (event), HUM (human), LOC (location), NET (internet), NUM (number), ORG (organization), OTHER (other), THG (thing), YESNO (yes/no). Thuật toán mà nhóm tác giả sử dụng là Naïve Bayes và Maximum Entropy cùng với lựa chọn sử dụng các đặc trưng: unigrams, wh-words, typed dependencies. Kết quả của thí nghiệm được trình bày trong bảng 2.2 dưới đây. Bảng 2.2: Độ chính xác khi thực nghiệm với bộ dữ liệu ngôn ngữ Tiếng Việt Đặc trƣng NB ME Wh-words 47.5% 51.5% Unigrams 57.6% 78.4% Wh-words + deps 59.7% 69.6% Unigrams + deps 58.8% 80.5% 42 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 LI SVM được áp dụng trong quá trình huấn luyện và kiểm thử. Lựa chọn các đặc trưng: Đã có rất nhiều các đặc trưng được giới thiệu, trong phần thực nghiệm này, trước mắt luận văn sử dụng đặc trưng unigram và bigram để tiến hành phân loại. 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 43 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 đị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. Hình 3.1: File chứa 5500 câu hỏi ban đầu Hình 3.2: File chứa 500 câu hỏi test Ví dụ của một dòng dữ liệu trong tập dữ liệu UIUC: 44 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 Như đã giải thích trong phần 1.4, câu hỏi được biểu diễn trong mô hình không gian vector. Các đặc trưng trích rút từ các câu hỏi sẽ được bổ sung vào vectơ đặc trưng với một cặp (đặc trưng, giá trị). Nếu chỉ trích rút các đặc trưng unigram, với câu hỏi “Who was the Pride of Yankees”, công thức (1.2) sẽ được chuyển sang hình thức sau: {(Who, 1)(was, 1)(the, 2)(Pride, 1)(of, 1)(Yankees, 1)(?, 1)} Tuy nhiên thay vì sử dụng chuỗi, mỗi phần tử (đặc trưng) sẽ được ánh xạ tới một số duy nhất, chỉ số đặc trưng.Hơn nữa tên của lớp cũng được ánh xạ tới một số duy nhất. Mẫu định dạng dưới đây là tương tự bộ dữ liệu TREC, nó được chuyển qua hình thức mà có thể được chấp nhận bởi thư viện LIBSVM. LIBSVM là một bộ thư viện đơn giản dễ sử dụng và hiệu quả dành cho bộ phân loại SVM. Đây là một mã nguồn mở cung cấp cho nhiều ngôn ngữ khác nhau : Java, Python, Perl, Ruby ... Để 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. 45 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. Ngôn ngữ Java được sử dụng để chuyển đổitừ dữ liệu ban đầu (Hình 3.1 và 3.2) sang thành định dạng có thể đọc được bởi LIBSVM. Đầu tiên, file dữ liệu tải về được tách thành 2 file: 1 file chứa nhãn và câu hỏi của tập thô, 1 file chứa nhãn và câu hỏi của tập mịn. Hình 3.3 và 3.4 là kết quả tách file của tập chứa 5500 câu hỏi. Thực hiện tương tự với file chứa dữ liệu test. Hình 3.3: File chứa 5500 nhãn và câu hỏi của tập thô 46 Hình 3.4: File chứa 5500 nhãn và câu hỏi của tập mịn Sau đó, từ file ở trên (dữ liệu thô hoặc dữ liệu mịn) sẽ được tách thành 2 file: 1 file chỉ chứa câu hỏi và 1 file chứa nhãn đã được đánh số. Hình 3.5 và 3.6 là kết quả tách file của tập dữ liệu huấn luyện. Thực hiện tương tự với tập dữ liệu test. Hình 3.5: File chứa 5500 câu hỏi huấn luyện 47 Hình 3.6: Nhãn tương ứng của 5500 câu hỏi Từ đó, với các file kết quả thu được, sử dụng các đặc trưng bag of word thực hiện đưa về định dạng đọc được bởi thư viện LIBSVM. Hình 3.7 và 3.8 là file kết quả sử dụng đặc trưngbigram trên tập mịncủa tập dữ liệu huấn luyện và tập dữ liệu test. Hình 3.7: File kết quả đưa về định dạng đọc được bởi thư viện LIBSVM sử dụng đặc trưng bigram trên tập mịn của tập train. 48 Hình 3.8: File kết quả đưa về định dạng đọc được bởi thư viện LIBSVM sử dụng đặc trưng bigram trên tập mịn của tập test. 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 : 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 49 - 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. 50 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. 51 TÀI LIỆU THAM KHẢO Tiếng Việt 1. Nguyễn Minh Tuấn (2008), Phân lớp câu hỏi hướng tới tìm kiếm ngữ nghĩa Tiếng Việt trong lĩnh vực y tế, Khóa luận tốt nghiệp đại học, Trường Đại học Công Nghệ, Đại học Quốc gia Hà Nội. 2. Nguyễn Đức Vinh (2009),Phân tích câu hỏi trong hệ thống hỏi đáp Tiếng Việt,Khóa luận tốt nghiệp đại học, Trường Đại học Công Nghệ, Đại học Quốc gia Hà Nội. Tiếng Anh 3. Babak Loni (2011),Enhanced Question Classification with Optimal Combination of Features,Department of Media and Knowledge Engineering Delft University of Technology. 4. Caixian Chen, Huijian Han, Zheng Liu (2014), KNN question classification method based on Apriori algorithm, 5. Donald Metzler and W. Bruce Croft (2004), Analysis of Statistical Question Classification for Fact-based Questions, University of Massachusetts, Amherst. 6. Håkan Sundblad (2007), Question Classification in Question Answering Systems, Linköping. 7. Jo˜ao Silva, Lu´ısa Coheur, Ana Mendes, and Andreas Wichert. From symbolic to subsymbolic information in question classification.Articial Intelligence Review, 35(2):137–154, February 2011. 8. LI Xin, HUANG Xuan-Jing, WU Li-de (2006), Question Classification by Ensemble Learning,Dep. of Computer Science and Engineering, FUDAN Univ., Shanghai, PRC. 9. Marcin Skowron and Kenji Araki (2005), “Effectiveness of Combined features for machine learning based question classification”, Journal of Natural Language Processing, Vol.12, No.6. 10. Phuong Le-Hong, Xuan-Hieu Phan, and Tien-Dung Nguyen (2014), Using Dependency Analysis to Improve Question Classification 11. Rishika Yadav, Megha Mishra (2013), “Question Classification Using Naïve ayes Machine Learning Approach”, International Journal of Engineering and Innovative Technology (IJEIT), Volume 2, Issue 8. 52 12. V.Vapnik (1995),The Nature of Statistical Learning Theory,NewYork. 13. Xin Li, Dan Roth (2002), Learning Question Classifiers, In Proceedings of the 19th international conference on Computational Linguistics, 1, Taipei, Taiwan, pp. 1–7. Association for Computational Linguistics. 14. Zhang, D. & Lee, W.S. (2003), Question Classification Using Support Vector Machines, In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Toronto, Canada, pp. 26-32. 15. Zhiheng Huang, Marcus Thint, Zengchang Qin (2008), Question Classification Using Head Words and Their Hypernyms, In Proceedings of the Conference on Empirical Methods in Natural Language Processing, Honolulu, Hawaii, Association for Computational Linguistics, pp. 927–936. 53 PHỤ LỤC Danh sách các nhãn từ loại trong hệ thống Penn Treebank ( spring15/readings/PennTreebankConstituents.html#Clause ) Clause Level STT Mệnh đề Giải thích 1 S Simple declarative clause, i.e. one that is not introduced by a (possible empty) subordinating conjunction or a wh-word and that does not exhibit subject-verb inversion. 2 SBAR Clause introduced by a (possibly empty) subordinating conjunction. 3 SBARQ Direct question introduced by a wh-word or a wh-phrase. Indirect questions and relative clauses should be bracketed as SBAR, not SBARQ 4 SINV Inverted declarative sentence, i.e. one in which the subject follows the tensed verb or modal. 5 SQ Inverted yes/no question, or main clause of a wh-question, following the wh-phrase in SBARQ. Phrase Level STT Mệnh đề Giải thích 1 ADJP Adjective Phrase. 2 ADVP Adverb Phrase. 3 CONJP Conjunction Phrase. 4 FRAG Fragment. 5 INTJ Interjection. Corresponds approximately to the part-of-speech tag UH. 6 LST List marker. Includes surrounding punctuation. 7 NAC Not a Constituent; used to show the scope of certain prenominal modifiers within an NP. 8 NP Noun Phrase. 9 NX Used within certain complex NPs to mark the head of the NP. Corresponds very roughly to N-bar level but used quite differently. 10 PP Prepositional Phrase. 11 PRN Parenthetical. 12 PRT Particle. Category for words that should be tagged RP. 13 QP Quantifier Phrase (i.e. complex measure/amount phrase); used 54 within NP. 14 RRC Reduced Relative Clause. 15 UCP Unlike Coordinated Phrase. 16 VP Vereb Phrase. 17 WHADJP Wh-adjective Phrase. Adjectival phrase containing a wh-adverb, as in how hot. 18 WHAVP Wh-adverb Phrase. Introduces a clause with an NP gap. May be null (containing the 0 complementizer) or lexical, containing a wh- adverb such as how or why. 19 WHNP Wh-noun Phrase. Introduces a clause with an NP gap. May be null (containing the 0 complementizer) or lexical, containing some wh- word, e.g. who, which book, whose daughter, none of which, orhow many leopards. Word Level STT Từ loại Giải thích 1. CC Coordinating conjunction 2. CD Cardinal number 3. DT Determiner 4. EX Existential there 5. FW Foreign word 6. IN Preposition or subordinating conjunction 7. JJ Adjective 8. JJR Adjective, comparative 9. JJS Adjective, superlative 10. LS List item marker 11. MD Modal 12. NN Noun, singular or mass 13. NNS Noun, plural 14. NP Proper noun, singular 15. NPS Proper noun, plural 16. PDT Predeterminer 17. POS Possessive ending 55 18. PP Personal pronoun 19. PP$ Possessive pronoun 20. RB Adverb 21. RBR Adverb, comparative 22. RBS Adverb, superlative 23. RP Particle 24. SYM Symbol 25. TO to 26. UH Interjection 27. VB Verb, base form 28. VBD Verb, past tense 29. VBG Verb, gerund or present participle 30. VBN Verb, past participle 31. VBP Verb, non-3rd person singular present 32. VBZ Verb, 3rd person singular present 33. WDT Wh-determiner 34. WP Wh-pronoun 35. WP$ Possessive wh-pronoun 36. WRB Wh-adverb