Tài liệu Luận văn cntt 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 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội -2016 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 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TS LÊ HỒNG PHƢƠNG Hà Nội -2016 i LỜI CẢM ƠN Trước tiên, tôi xin được gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Thầy giáo, TS.Lê Hồng Phương đã tận tình chỉ bảo, hướng dẫn, động viên và giúp đỡ tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Tôi xin gửi lời cảm ơn tới các thầy cô trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội – những người đã tận tình giúp đỡ, cổ vũ, và góp ý cho tôi trong suốt thời gian tôi học tập và nghiên cứu tại trường. Tôi xin gửi lời cảm ơn tới các anh chị, các bạn học viên cùng học tập nghiên cứu tại Trường Đại học Công nghệ đã hỗ trợ tôi rất nhiều trong quá trình học tập cũng như thực hiện luận văn. Cuối cùng, tôi muốn gửi lời cảm ơn tới gia đình và bạn bè, những người thân yêu luôn bên cạnh, quan tâm, động viên tôi trong suốt quá trình học tập và thực hiện luận văn tốt nghiệp này. Tôi xin chân thành cảm ơn! Hà Nội, tháng 10 năm 2016 Học viên Vũ Thị Tuyến ii LỜI CAM ĐOAN Tôi xin cam đoan nội dung được trình bày trong luận văn “Một số mô hình học máy trong phân loại câu hỏi” do tôi thực hiện dưới sự hướng dẫn của TS. Lê Hồng Phương. Tôi đã trích dẫn đầy đủ các tài liệu tham khảo, công trình nghiên cứu liên quan ở trong nước và quốc tế. Tất cả những tham khảo từ các nghiên cứu liên quan đều được nêu nguồn gốc một cách rõ ràng từ danh mục tài liệu tham khảo trong luận văn. Hà Nội, tháng 10 năm 2016 Học viên Vũ Thị Tuyến 1 MỤC LỤC LỜI CẢM ƠN ...................................................................................................................i LỜI CAM ĐOAN ........................................................................................................... ii MỤC LỤC ....................................................................................................................... 1 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ..................................................... 3 DANH MỤC CÁC HÌNH ............................................................................................... 4 DANH MỤC CÁC BẢNG .............................................................................................. 5 LỜI MỞ ĐẦU ................................................................................................................. 6 Chương 1: TỔNG QUAN VỀ PHÂN LOẠI CÂU HỎI ................................................. 7 1.1. Tổng quan về hệ thống hỏi đáp ............................................................................ 7 1.1.1. Đặt vấn đề ...................................................................................................... 7 1.1.2. Hệ thống hỏi đáp (Question Answering System) .......................................... 8 1.1.2.1. Giới thiệu ................................................................................................ 8 1.1.2.2. Cấu trúc của một hệ thống hỏi đáp ......................................................... 9 1.1.2.3. Tại sao phải phân loại câu hỏi? ............................................................ 10 1.2. Bài toán phân loại câu hỏi .................................................................................. 11 1.2.1. Định nghĩa phân loại câu hỏi ....................................................................... 11 1.2.2. Phát biểu bài toán phân loại câu hỏi ............................................................ 11 1.3. Các cách tiếp cận bài toán phân loại câu hỏi ...................................................... 12 1.3.1. Tiếp cận dựa trên luật .................................................................................. 12 1.3.2. Tiếp cận dựa trên học máy .......................................................................... 13 1.4. Biểu diễn câu hỏi ................................................................................................ 15 1.5. Taxonomy câu hỏi .............................................................................................. 16 1.5.1. Khái niệm về Taxonomy ............................................................................. 16 1.5.2. Các taxonomy theo kiểu câu trả lời ............................................................. 16 1.5.3. Phân lớp đa cấp............................................................................................ 19 1.6. Các đặc trưng phân loại ...................................................................................... 20 1.6.1. Các đặc trưng về từ vựng ............................................................................ 20 1.6.2. Các đặc trưng về cú pháp ............................................................................ 22 1.6.2.1. POS Tags và Tagged Unigrams ........................................................... 22 1.6.2.2. Từ đầu (head word) .............................................................................. 23 1.6.2.3. Biểu thức chính quy.............................................................................. 27 2 1.6.3. Các đặc trưng ngữ nghĩa .............................................................................. 28 Chương 2: MỘT SỐ MÔ HÌNH HỌC MÁY TRONG PHÂN LOẠI CÂU HỎI ......... 30 2.1. Kiến trúc hệ thống .............................................................................................. 30 2.2. Thuật toán Naïve Bayes...................................................................................... 30 2.2.1. Định lý ......................................................................................................... 30 2.2.2. Thuật toán .................................................................................................... 31 2.3. Thuật toán k-láng giềng gần (k- Nearst Neighbours) ......................................... 34 2.4. Máy Vector hỗ trợ - SVM .................................................................................. 35 2.5. Một số thuật toán khác ....................................................................................... 39 2.6. Hiệu suất trong phân loại câu hỏi ....................................................................... 39 2.7. Một số kết quả của các tác giả ............................................................................ 40 Chương 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ ............................................................. 42 3.1. Lựa chọn bộ phân loại ........................................................................................ 42 3.2. Môi trường và công cụ sử dụng trong thực nghiệm ........................................... 42 3.3. Tập dữ liệu thử nghiệm ...................................................................................... 42 3.4. Xử lý dữ liệu ....................................................................................................... 44 3.5. Huấn luyện và kiểm thử với LibSVM ................................................................ 48 3.6. Kết quả thực nghiệm........................................................................................... 49 3.7. Kết luận............................................................................................................... 49 TỔNG KẾT ................................................................................................................... 50 TÀI LIỆU THAM KHẢO ............................................................................................. 51 PHỤ LỤC ...................................................................................................................... 53 3 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT STT Ký hiệu, viết tắt Tiếng anh Chú giải 1 QA Question Answering systems Hệ thống hỏi đáp 2 IR Information Retrieval Truy hồi thông tin 3 TREC Text REtrieval Conference 4 UIUC University of Illinois UrbanaChampaign 5 MUC Message Understanding Conference 6 POS Part – Of - Speech 7 WSD Word Sense Disambiguation 8 NN Nearest Neighbors 9 NB Naïve Bayes 10 DT Decision Tree Cây quyết định 11 SNoW Sparse Network of Winnows Mạng lọc thưa 12 SVM Support Vector Machine Máy vector hỗ trợ 13 ME Maximum Entropy Entropy cực đại Láng giềng gần 4 DANH MỤC CÁC HÌNH Hình 1.1: Kiến trúc một hệ thống hỏi đáp ..................................................................... 10 Hình 1.2: Mô hình giai đoạn huấn luyện ....................................................................... 14 Hình 1.3: Chi tiết giai đoạn huấn luyện ......................................................................... 15 Hình 1.4: Mô hình giai đoạn phân lớp........................................................................... 15 Hình 1.6: Cây phân tích cú pháp sử dụng bộ phân tích Berkeley ................................. 24 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” .......................................................................................................................... 27 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 .................. 30 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. ... 36 Hình 2.3: Sơ đồ phân lớp câu hỏi với SVM .................................................................. 39 Hình 3.1: File chứa 5500 câu hỏi ban đầu ..................................................................... 43 Hình 3.2: File chứa 500 câu hỏi test .............................................................................. 43 Hình 3.4: File chứa 5500 nhãn và câu hỏi của tập mịn ................................................. 46 Hình 3.6: Nhãn tương ứng của 5500 câu hỏi ................................................................ 47 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. ........................................................................ 47 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. .......................................................................... 48 5 DANH MỤC CÁC BẢNG Bảng 1.1: Taxonomy câu hỏi của Li và Roth ................................................................ 17 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 .............................................................. 40 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 ............ 41 Bảng 3.1: Thông tin phần cứng ..................................................................................... 42 Bảng 3.2: Các công cụ phần mềm được sử dụng .......................................................... 42 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 ........ 49 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 ....... 49 6 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ề. 7 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ớisố 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. Phân loại câu hỏi trong hệ thống hỏi đáp có 2 yêu cầu chính [13]. Thứ nhất , nó cung cấp các gợi ý về loại câu trả lời mà cho phép tiếp tục xử lý để xác định vị trí chính xác và xác minh câu trả lời. Thứ hai, nó cung cấp thông tin trong quá trình xử lý hạ lưu được sử dụng để lựa chọn các chiến lược cho từng câu trả lời cụ thể. Ví dụ như với câu hỏi: Who was the first woman killed in the Vietnam War?, các nhà nghiên cứu không muốn kiểm tra mọi cụm danh từ trong tài liệu để xem liệu có nó cung cấp một câu trả lời hay không. Mà ít nhất họ muốn biết rằng mục đích của câu trả lời này là về “person”, do đó mà làm giảm thiểu đáng kể không gian các câu trả lời tiềm năng. Chúng ta cùng xem xét một số ví dụ tiếp theo được lấy từ bộ câu hỏi TREC 100, thể hiện một số khía cạnh của quan điểm này. Q:What is a prism? Câu hỏi này xác định rằng, mục đích mà nó hướng tới là “định nghĩa” (definition), chiến lược cụ thể cho các “definitions” (chẳng hạn như sử dụng các mẫu câu định sẵn: Prism is… hoặc Prism is defined as…) có thể trở nên hữu ích. Tương tự như vậy, trong câu hỏi Q: Why is the sun yellow?Xác định rằng câu hỏi này hỏi về loại “lí do” (reason), câu trả lời được hướng tới sẽ là loại “reason”. 8 Các ví dụ trên cho thấy rằng, các loại câu trả lời khác nhau được đưa ra tương ứng với câu hỏi có thể được tìm kiếm sử dụng nhiều chiến lược khác nhau, một phân loại tốt có thể giúp tìm ra câu trả lời tốt trong nhiệm vụ hỏi đáp. Hơn nữa, việc xác định loại ngữ nghĩa cụ thể của câu trả lời cũng có thể giúp ích trong việc tìm ra câu trả lời. Ví dụ với 2 câu hỏi: What Canadian city has the largest population?vàWhich country gave New York the Statue of Liberty? ta biết rằng mục tiêu là loại “city” hoặc “country” sẽ hữu ích hơn là chỉ biết chúng thuộc loại “localtions”. Như vậy, mục đích của phân loại câu hỏi là giảm thiểu không gian tìm kiếm, giúp ta xác định được kiểu câu trả lời khi đã biết phân loại của nó. 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. Nghiên cứu để xây dựng một hệ thống trả lời được các câu hỏi biết bởi ngôn ngữ tự nhiên đã được thực hiện từ những năm 1960. Hệ thống hỏi đáp đầu tiên là BASEBALL được phát triển năm 1961 do nhóm tác giả Green, Chomsky, và Laughery. Hệ thống này dùng để trả lời các câu hỏi viết bằng ngôn ngữ tự nhiên trong một lĩnh vực đặc biệt là về trò chơi bóng chày trong ở giải đấu của Mỹ trong một mùa giải. Đây là một hệ thống cơ sở dữ liệu đơn giản dùng để dịch một câu hỏi trong ngôn ngữ tự nhiên thành một câu truy vấn tương ứng trong cơ sở dữ liệu. Hầu hết các nghiên cứu trước đây chủ yếu là các hệ thống hỏi đáp trong một lĩnh vực đặc biệt hoặc là có sự giới hạn trong việc hỏi đáp. Do thiếu kiến thức để cung cấp câu trả lời cho câu hỏi miền mở, các nghiên cứu về hệ thống hỏi đáp nằm im trong vài thập kỷ cho đến khi sự xuất hiện của các trang web. Với số lượng lớn của các dữ liệu trên web, cần phải thực hiện các truy vấn web, do đó các nhiệm vụ về hỏi đáp lại được tập trung nghiên cứu. Sự tập trung nghiên cứu về hỏi đáp đặc biệt tăng khi hội nghị truy hồi văn bản (Text REtrieval Conference-Trec) bắt đầu một chủ để về hỏi đáp vào năm 1990. Một vài kĩ thuật từ truy hồi thông tin, xử lý ngôn ngữ tự nhiên và học máy đã được dùng trong các hệ thống hỏi đáp. Các nghiên cứu gần đây trên các hệ thống hỏi đáp miền mở điển hình thường dựa trên các kĩ thuật truy hồi thông tin (Information Retrieval-IR). Các hệ thống hỏi đáp dựa trên truy hồi thông tin cố gắng tìm kiếm câu 9 trả lời cho câu hỏi bằng cách xử lý các tài liệu, thường từ web và tìm kiếm một phần của văn bản đó có thể là câu trả lời cho câu hỏi. 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]: 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.  Xử lý câu hỏi: nhiệm vụ xử lý câu hỏi thông thường bao gồm các công việc như biểu diễn câu hỏi, dẫn xuất đến loại câu trả lời mong đợi và trích xuất từ khóa. Phân tích được thực hiện để xây dựng cấu trúc biểu diễn câu hỏi. Thông thường, câu trúc biểu diễn câu hỏi là một cây cú pháp hoặc một cây phụ thuộc. Sau đó cấu trúc này được sử dụng để xác định vị trí và xác minh các câu trả lời trong các tài liệu và đoạn văn đã được trích xuất.  Xử lý tài liệu: giai đoạn này bao gồm mở rộng từ khóa, trích chọn tài liệu, và xác định đoạn văn liên quan. Mở rộng từ khóa là sử dụng các từ khóa được trích xuất trong giai đoạn xử lý câu hỏi ở trên và tìm kiếm chúng trong một từ điển đồng nghĩa hoặc các tài nguyên khác, và thêm các điều kiện tìm kiếm để lấy ra càng nhiều tài liệu liên quan càng tốt. Ví dụ từ khóa “kill” có thể được mở rộng thành “murder” và “assassinate”. Các tài liệu được trích chọn dựa trên các từ khóa mở rộng. Từ đó, một đoạn hoặc một phần của mỗi tài liệu này có chứa câu trả lời tiềm năng sẽ được xác định. Phân loại câu hỏi được sử dụng ở đây: nó có thể xác định chiến lược tìm kiếm để tìm kiếm các ứng viên đúng. Tùy thuộc vào các lớp câu hỏi, truy vấn tìm kiếm có thể được chuyển đổi thành một hình thức mà là thích hợp nhất cho việc tìm kiếm câu trả lời. 10 Hình 1.1: Kiến trúc một hệ thống hỏi đáp  Xử lý câu trả lời: nhiệm vụ cuối cùng của hệ thống hỏi đáp là xử lý các ứng viên đúng và trích xuất các cụm từ giống như là câu trả lời của câu hỏi. Phân loại câu hỏi lại được dùng ở đây. Các ứng cử viên câu trả lời được xếp hạng theo khả năng của mình trong việc trong cùng một lớp như lớp câu hỏi và câu trả lời xếp hạng cao nhất sẽ được coi là câu trả lời cuối cùng của câu hỏi. 1.1.2.3. Tại sao phải phân loại câu hỏi? Như đã nói ở trên, mặc dù các kiểu khác nhau của các hệ thống hỏi đáp tự động có các kiến trúc khác nhau, hầu hết trong số chúng làm theo một khuôn khổ trong đó phân loại câu hỏi giữ một vai trò quan trọng. Hơn nữa, nó có được chứng minh rằng hiệu suất của phân loại câu hỏi có ảnh hưởng đáng kể trên hiệu suất tổng thể của hệ thống hỏi đáp. 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. 11 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 đượ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. 12 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. Nhóm tác giả Singhal (1999) dựa trên các quy tắc hoạt động của từ đã giới thiệu một số luật như sau [6]:  Truy vấn bắt đầu bằng “Who” hoặc “Whom” được đưa đến loại “person”.  Truy vấn bắt đầu bằng “Where”, “Whence”, hoặc “Whither” được đưa về loại “location”.  Truy vấn bắt đầu với “How few”, “How great”, “How little”, “How many” hoặc “How much” được đưa về loại “quantity”.  Truy vấn bắt đầu bằng “Which” hoặc “What” thì tìm kiếm danh từ chính (head noun) trong từ điển để xác định loại câu trả lời. Tuy nhiên, cách tiếp nàythể hiện một số hạn chế như sau:  Sự phân loại dựa trên các luật viết gặp nhiều khó khăn và tốn nhiều thời gian xử lý, do dựa trên kiến thức chủ quan của con người trên một tập dữ liệu câu hỏi .  Có sự giới hạn về mức độ bao quát và phức tạp trong việc mở rộng phạm vi của các loại câu trả lời .  Khi một phân loại mới xuất hiện, nhiều quy tắc trước đó phải được sửa đổi hoặc viết mới hoàn toàn. Li và Roth đã cung cấp ví dụ để chỉ ra khó khăn của cách tiếp cận dựa trên luật.Tất cả các câu hỏi dưới đây đều có cùng một câu trả lời nhưng chúng được viết trong những định dạng cú pháp khác nhau. - What tourist attractions are there in Reims? - What are the names of the tourist attractions in Reims? - What do most tourist visit in Reims? - What attracts tourists to Reims? 13 - What is worth seeing in Reims? Tất cả các câu hỏi trên cùng đề cập đến một lớp trong khi chúng có định dạng cú pháp khác nhau và do đó chúng cần so khớp với các luật khác nhau. Vì vậy với sự giới hạn về số lượng các luật dẫn đến việckhó để phân loại. 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. Những thuận lợi trong cách tiếp cận này bao gồm:  Thời gian tạo dựng ngắn vì không phải tốn thời gian đề ra các luật.  ộ phân loại được tạo ra tự động thông qua việc học từ một tập dữ liệu huấn luyện, việc cung cấp các luật giờ không cần thiết nữa.  Độ bao phủ rộng hơn, và có thể mở rộng độ bao phủ bằng cách thu được từ các ví dụ huấn luyện.  Nếu có yêu cầu , bộ phân loại có thể tái cấu trúc lại (học lại) một cách linh hoạt để phù hợp với quy luật mới. Trong cuộc hội nghị TREC các nhà nghiên cứu đã phát triển một phương pháp học máy tiếp cận để phân loại câu hỏi. Mục đích của phương pháp này là phân loại các câu hỏi vào trong các lớp ngữ nghĩa khác nhau mà đã được gợi ý về khả năng trả lời, để chúng có thể được sử dụng trong các giai đoạn sau của hệ thống hỏi đáp. Một trong những giai đoạn quan trọng trong tiến trình này là việc phân tích câu hỏi đến một cấp độ cho phép xác định “loại” câu trả lời sau khi được tìm kiếm . Ví dụ, khi xem xét câu hỏi: What Canadian city has the largest population?, thì mong muốn rằng phân loại câu hỏi này vào kiểu câu trả lời là location (city), điều này ngụ ý rằng chỉ xét đến các câu trả lời có kiểu là thành phố mới cần được xem xét.Tương tự như vậy với câu hỏi: Who discovered x-rays?nên xếp vào loại human (individual). Như vậy, việc phân loại các câu hỏi sẽ giúp thu hẹp không gian tìm kiếm dẫn đến việc đưa ra câu trả lời chính xác. Cách tiếp cận bài toán phân loại câu hỏi theo phương pháp học máy được sử dụng phổ biến hơn cả. Vấn đề phân loại câu hỏi theo phương pháp thống kê dựa trên 14 kiểu học có giám sát được đặc tả bao gồm 2 giai đoạn : giai đoạn huấn luyện và giai đoạn phân lớp. Giai đoạn huấn luyện: Đầu vào: tập dữ liệu huấn luyện và thuật toán huấn luyện. Đầu ra: mô hình phân loại (bộ phân loại – classifier) Tập dữ liệu Tập huấn luyện Bộ học có giám sát Mô hình phân lớp Hình 1.2: Mô hình giai đoạn huấn luyện Chi tiết giai đoạn huấn luyện bộ phân loại như sau (Hình 1.3): - Tập dữ liệu huấn luyện: một tập dữ liệu huấn luyện được thu thập từ nhiều nguồn khác nhau. - Tiền xử lý: chuyển đổi các dữ liệu trong tập huấn luyện thành một hình thức phù hợp để phân loại. - Vector hóa: các câu hỏi trong tập dữ liệu cần được mã hóa bởi mô hình không gian vector. - Trích chọn đặc trưng: loại bỏ những từ (đặc trưng) không mang ý nghĩa thông tin nhằm nâng cao hiệu suất phân loại và giảm độ phức tạp của thuật toán huấn luyện. - Thuật toán huấn luyện: Sử dụng thuật toán huấn luyện bộ phân loại để tìm ra họ các tham số tối ưu. ước này có thể được thực thi lặp lại nhiều lần để tìm họ các tham số tối ưu sau mỗi lần lặp. - Đánh giá: bước này đánh giá hiệu suất (chất lượng) của bộ phân loại. 15 Tập dữ liệu huấn luyện Tiền xử lý Vector hóa Đánh giá Áp dụng thuật toán huấn luyện Trích chọn đặc trưng Hình 1.3: Chi tiết giai đoạn huấn luyện Giai đoạn phân lớp: Sau khi đã hoàn thành giai đoạn huấn luyện, mô hình phân lớp sẽ được áp dụng cho các văn bản mới cần phân loại. Mô hình phân lớp Câu hỏi cần phân loại Bộ phân loại Câu hỏi đã được phân loại Hình 1.4: Mô hình giai đoạn phân lớp Đầu vào: các vector đặc trưng của câu hỏi và mô hình phân loại được sử dụng. Đầu ra: nhãn/phân loại của câu hỏi 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ố 16 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. Một số hệ thống (Srihari & Li 1999) sử dụng các taxonomy bắt nguồn từ các loại được sử dụng trong các đánh giá tại Message Understanding Conference (MUC).MUC đã phân biệt giữa các thực thể đặt tên (organization, person, và location), biểu thức thời gian (date và time), và các biểu thức số (money và percentage). Một giải pháp khác được sử dụng để xây dựng các taxonomy đó là sử dụng WordNet (Fellbaum 1998).Nhóm tác giả Kim (2000) đã sử dụng cách tiếp cận này để xây dựng một taxonomy cho 46 phân loại khác nhau về ngữ nghĩa khác nhau. Ngoài ra còn có các taxonomy câu hỏi nổi tiếng khác sử dụng để phân loại câu hỏi.Taxonomy được đề xuất bởi Hermjakob (2002) bao gồm 180 lớp, đó cũng là nguyên tắc phân loại câu hỏi rộng nhất được đề xuất đến bây giờ. 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