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

Figure ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Nguyễn Đức Vinh PHÂN TÍCH CÂU HỎI TRONG HỆ THỐNG HỎI ĐÁP TIẾNG VIỆT KHỐ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ thơng tin HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Nguyễn Đức Vinh PHÂN TÍCH CÂU HỎI TRONG HỆ THỐNG HỎI ĐÁP TIẾNG VIỆT KHỐ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ thơng tin Cán bộ hướng dẫn: ThS. Trần Thị Oanh Cán bộ đồng hướng dẫn: ThS. Nguyễn Cẩm Tú HÀ NỘI - 2009 i Lời cảm ơn Trước tiên, tơi xin gửi lời cảm ơn và lịng biết ơn sâu sắc nhất tới Phĩ Giáo sư Tiến sĩ Hà Quang Thụy, Thạc sĩ Trần Thị Oanh, Thạc sĩ Nguyễn Cẩm Tú và Cử nhân Trần Mai Vũ – những người đã tận tình chỉ bảo và hướng dẫn tơi trong quá trình thực hiện khố luận tốt nghiệp. Tơi chân thành cảm ơn các thầy, cơ và cán bộ của trường Đại Học Cơng Nghệ đã tạo cho tơi những điều kiện thuận lợi để học tập và nghiên cứu. Tơi xin gửi lời cảm ơn chân thành tới cử nhân Nguyễn Minh Tuấn đã tận tình hỗ trợ về kiến thức chuyên mơn, giúp đỡ tơi hồn thành khĩa luận. Tơi cũng xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong phịng thí nghiệm Sislab đã giúp tơi rất nhiều trong việc thu thập và xử lý dữ liệu. 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, động viên tơi trong suốt quá trình thực hiện khĩa luận tốt nghiệp. Tơi xin chân thành cảm ơn ! Sinh viên Nguyễn Đức Vinh ii Tĩm tắt Trong mười năm gần đây, hệ thống hỏi đáp tự động đã nhận được sự quan tâm đặc biệt của các nhà nghiên cứu, các cơng ty (Yahoo, Google, Microsoft, IBM…), các hội nghị lớn về trích chọn thơng tin, xử lý ngơn ngữ tự nhiên (TREC, CLEF, ACL,..) và đã đạt được những kết quả nhất định. Tuy nhiên các nghiên cứu về hệ thống hỏi đáp cho tiếng Việt vẫn cịn rất nhiều hạn chế. Khĩa luận Phân tích câu hỏi trong hệ thống hỏi đáp tiếng Việt tập trung vào khảo sát các phương pháp được áp dụng cho xây dựng hệ thống hỏi đáp trên thế giới, đặc biệt tập trung nghiên cứu pha phân tích câu hỏi – pha đầu tiên trong hệ thống hỏi đáp, cĩ ý nghĩa đặc biệt quan trọng với hoạt động của cả hệ thống. Trên cơ sở các nghiên cứu đĩ và điều kiện thực tế của các cơng cụ xử lý ngơn ngữ tiếng Việt, khĩa luận tiến hành thực nghiệm việc phân tích câu hỏi tiếng Việt sử dụng phương pháp học máy thống kê và trích rút mẫu quan hệ. Các kết quả ban đầu đạt được khá khả quan. Bộ phân lớp câu hỏi cho hệ thống hỏi đáp miền mở đạt độ chính xác 81.49% khi sử dụng thuật tốn SVM, 81.14 % với mơ hình Entropy cực đại. Module phân tích câu hỏi sử dụng mẫu quan hệ cho hệ thống hỏi đáp trên miền du lịch đạt độ chính xác 89.7 %. iii Mục lục Tĩm tắt..................................................................................................................................i Mục lục .............................................................................................................................. iii Danh sách các bảng ............................................................................................................v Danh sách các hình............................................................................................................vi Lời mở đầu ..........................................................................................................................1 Chương 1. Giới thiệu về hệ thống hỏi đáp tự động .........................................................3 1.1. Hệ thống hỏi đáp tự động ..........................................................................................3 1.2. Phân loại hệ thống hỏi đáp tự động ...........................................................................5 1.2.1. Phân loại theo miền ứng dụng (domain).............................................................5 1.2.2. Phân loại theo khả năng trả lời câu hỏi ...............................................................6 1.2.3. Phân loại theo hướng tiếp cận:............................................................................7 1.3. Các bước chung của hệ thống hỏi đáp tự động..........................................................7 Chương 2. Phân tích câu hỏi ...........................................................................................10 2.1. Nội dung của phân tích câu hỏi ...............................................................................10 2.2. Khĩ khăn của phân tích câu hỏi...............................................................................10 2.3. Một số nội dung của xử lý ngơn ngữ tự nhiên trong phân tích câu hỏi...................11 2.4. Taxonomy câu hỏi ...................................................................................................14 2.4.1. Khái niệm về taxonomy ....................................................................................14 2.4.2. Taxonomy câu hỏi.............................................................................................15 2.5. Khảo sát các phương pháp phân tích câu hỏi cho các loại câu hỏi khác nhau ........19 2.5.1. Câu hỏi đơn giản (factual-base) ........................................................................19 2.5.2. Câu hỏi định nghĩa (definition question) ..........................................................21 2.5.3. Câu hỏi phức tạp, cĩ ràng buộc về thời gian.....................................................22 iv Chương 3. Các phương pháp xác định loại câu hỏi ......................................................24 3.1. Phương pháp phân lớp sử dụng học máy thống kê..................................................24 3.1.2. Các thuật tốn học máy thống kê cho việc phân lớp ........................................28 3.1.3. Xây dựng bộ phân lớp câu hỏi theo học máy thống kê.....................................37 3.2. Phương pháp xác định loại câu hỏi sử dụng kĩ thuật xử lý ngơn ngữ tự nhiên .......42 3.3. Phương pháp xác định loại câu hỏi sử dụng mẫu quan hệ ......................................45 Chương 4. Thực nghiệm phân tích câu hỏi tiếng Việt ..................................................47 4.1. Thực nghiệm với phân lớp câu hỏi sử dụng học máy thống kê...............................47 4.1.1. Dữ liệu và cơng cụ cho thực nghiệm ................................................................47 4.1.2. Kết quả bộ phân lớp sử dụng SVM và MEM ...................................................49 4.2. Thực nghiệm với xác định loại câu hỏi sử dụng mẫu quan hệ ................................51 4.2.1. Mơ hình thực nghiệm phân tích câu hỏi sử dụng mẫu quan hệ ........................51 4.2.2. Kết quả phân tích câu hỏi sử dụng mẫu quan hệ ..............................................55 Kết luận .............................................................................................................................58 Tài liệu tham khảo............................................................................................................60 v Danh sách các bảng Bảng 1. Taxonomy câu hỏi do Li và Roth đưa ra ..............................................................17 Bảng 2. Biểu diễn của TP, TN, FP, FN trong đánh giá phân lớp.......................................27 Bảng 3. Số lượng câu hỏi theo từng lớp cha ......................................................................48 Bảng 4. Kết quả bộ phân lớp MEM khi sử dụng unigram .................................................49 Bảng 5. Kết quả bộ phân lớp MEM khi sử dụng tách từ....................................................49 Bảng 6. Kết quả bộ phân lớp SVM sử dụng các đặc trưng khác nhau...............................50 Bảng 7. Danh sách các từ hỏi .............................................................................................50 Bảng 8. Tập seed tìm được cùng với mối quan hệ tương ứng ...........................................53 Bảng 9. Tập quan hệ cùng các mẫu tương ứng ..................................................................54 Bảng 10. Các quan hệ được thực nghiệm trong hệ thống ..................................................55 Bảng 11. Các cơng cụ sử dụng ...........................................................................................55 Bảng 12. Các thành phần chính của hệ thống Q&A trên miền du lịch ..............................56 Bảng 13. Kết quả phân tích câu hỏi trong hệ thống hỏi đáp trên miền du lịch ..................56 vi Danh sách các hình Hình 1. Xu hướng trong nghiên cứu về Q&A......................................................................6 Hình 2. Các bước chung của hệ thống Q&A........................................................................8 Hình 3. Kiến trúc cho xử lý các câu hỏi factual-base.........................................................19 Hình 4. Mối quan hệ giữa các siêu phẳng phân cách .........................................................30 Hình 5. Siêu phẳng tối ưu và biên. .....................................................................................31 Hình 6. Biến nới lỏng cho soft margin ...............................................................................33 Hình 7. Mơ hình bộ phân lớp đa cấp của Li và Roth .........................................................39 Hình 8. Xác định loại câu hỏi sử dụng kĩ thuật xử lý ngơn ngữ tự nhiên ..........................43 Hình 9. Ánh xạ từ trọng tâm vào Wordnet.........................................................................44 Hình 10. Mơ hình Snowball ...............................................................................................46 Hình 11. Mơ hình hệ thống hỏi đáp tiếng Việt sử dụng trích xuất mẫu quan hệ ...............52 Hình 12. Mơ hình xử lý cho pha phân tích câu hỏi và trích xuất câu trả lời ......................53 1 Lời mở đầu Nghiên cứu về hệ thống hỏi đáp tự động (Q&A) đã được quan tâm từ rất lâu trên thế giới. Ngay từ những năm 1960, các hệ thống hỏi đáp đầu tiên sử dụng cơ sở dữ liệu đã được ra đời. Đến những năm 1970-1980, rất nhiều dự án lớn hướng đến việc “hiểu văn bản” và xây dựng hệ thống hỏi đáp dựa trên các mơ hình ngơn ngữ thống kê. Cuối những năm 1990, World Wide Web ra đời và phát triển nhanh chĩng trở thành một kho ngữ liệu khổng lồ. Các nhà nghiên cứu về hệ thống hỏi đáp cũng bắt đầu khai thác web như là một nguồn dữ liệu cho việc tìm kiếm câu trả lời. Các kĩ thuật mới địi hỏi tốc độ cao, khả năng xử lý lượng dữ liệu web lớn đang rất được quan tâm. Tuy nhiên các nghiên cứu về xây dựng hệ thống hỏi đáp cho tiếng Việt vẫn cịn rất nhiều hạn chế. Một trong những lý do chính là chúng ta cịn thiếu các cơng cụ xử lý tiếng Việt, các tài nguyên ngơn ngữ học (Wordnet [28], ontology [30]…). Phân tích câu hỏi là pha đầu tiên trong kiến trúc chung của một hệ thống hỏi đáp, cĩ nhiệm vụ tìm ra các thơng tin cần thiết làm đầu vào cho quá trình xử lý của các pha sau (trích chọn tài liệu, trích xuất câu trả lời, …). Vì vậy phân tích câu hỏi cĩ vai trị hết sức quan trọng, ảnh hưởng trực tiếp đến hoạt động của tồn bộ hệ thống. Nếu phân tích câu hỏi khơng tốt thì sẽ khơng thể tìm ra được câu trả lời. Khĩa luận Phân tích câu hỏi trong hệ thống hỏi đáp tiếng Việt thực hiện khảo sát, nghiên cứu các phương pháp xây dựng hệ thống hỏi đáp và phân tích câu hỏi đang được quan tâm hiện nay, từ đĩ đưa ra phương pháp phân tích câu hỏi phù hợp nhất (trên cơ sở các nguồn tài nguyên ngơn ngữ sẵn cĩ) cho hệ thống hỏi đáp tiếng Việt. Những nghiên cứu trong khĩa luận cĩ thể coi là tiền đề cho các nghiên cứu tiếp theo để xây dựng một hệ thống hỏi đáp hồn thiện cho tiếng Việt. Khĩa luận được trình bày thành bốn chương, nội dung được trình bày sơ bộ như dưới dây: Chương 1. Giới thiệu về hệ thống hỏi đáp tự động trình bày những nội dụng cơ bản nhất về hệ thống hỏi đáp và đặt vấn đề cho phân tích câu hỏi. Chương 2. Phân tích câu hỏi trình bày một cách tổng quan các vấn đề xung quanh việc phân tích câu hỏi như: nội dung của phân tích câu hỏi, những khĩ khăn của phân tích 2 câu hỏi, các nội dung của xử lý ngơn ngữ tự nhiên trong phân tích câu hỏi, đồng thời khảo sát các phương pháp phân tích câu hỏi cho một số loại câu hỏi khác nhau. Trong chương này cũng chỉ ra tầm quan trọng của xác định loại câu hỏi trong phân tích câu hỏi. Chương 3. Các phương pháp xác định loại câu hỏi trình bày ba phương pháp để xác định loại câu hỏi, phân tích và chọn lựa hai phương pháp sẽ sử dụng cho phân tích câu hỏi tiếng Việt. Chương 4. Thực nghiệm phân tích câu hỏi tiếng Việt áp dụng các nghiên cứu trong chương 3 để phân tích câu hỏi trong hệ thống hỏi đáp tiếng Việt. Phần kết luận tổng kết, tĩm lược nội dung và kết quả đạt được của khĩa luận. 3 Chương 1. Giới thiệu về hệ thống hỏi đáp tự động 1.1. Hệ thống hỏi đáp tự động Hệ thống hỏi đáp tự động cĩ thể coi như một lựa chọn thứ hai bên cạnh hệ thống trích chọn thơng tin khi người dùng muốn tìm kiếm thơng tin họ cần. Hệ thống trích chọn thơng tin nhận đầu vào là các từ khĩa và trả về tập các tài liệu liên quan (cĩ chứa các từ khĩa đĩ). Kết quả mà hệ thống trích chọn thơng tin (máy tìm kiếm) trả lại cho người dùng là rất lớn, cĩ thể lên đến hàng nghìn trang web mà phần nhiều khơng chứa thơng tin người dùng mong muốn. Trong khi đĩ, hệ thống hỏi đáp nhận đầu vào là câu hỏi dưới dạng ngơn ngữ tự nhiên của người dùng, trả lại các đoạn văn bản ngắn (các snippet) chứa câu trả lời trực tiếp cho câu hỏi [38]. Nghiên cứu về hệ thống hỏi đáp tự động hiện đang thu hút sự quan tâm của rất nhiều các nhà nghiên cứu từ các trường đại học, các viện nghiên cứu và cả các doanh nghiệp lớn trong ngành cơng nghệ thơng tin, cĩ ý nghĩa khoa học lẫn ý nghĩa thực tế. Rất nhiều các hội nghị thường niên về khai phá dữ liệu, trích chọn thơng tin dành một chủ đề riêng cho các nghiên cứu về hệ thống hỏi đáp như TREC1, CLEF2… Bài tốn xây dựng hệ thống hỏi đáp là một bài tốn khĩ thuộc lĩnh vực xử lý ngơn ngữ tự nhiên. Chúng ta biết rằng ngơn ngữ tự nhiên vốn nhập nhằng, đa nghĩa, việc xác định được ngữ nghĩa của câu hỏi cũng như phát hiện ra câu trả lời là một thách thức khơng nhỏ. Khơng những vậy, giữa câu hỏi và câu trả lời cịn tồn tại các quan hệ “ngầm” hay phụ thuộc vào ngữ cảnh. Ví dụ câu hỏi “Ai là tác giả Nhật ký trong tù ?” Câu trả lời: “ Hồ Chí Minh viết Nhật ký trong tù trong thời gian Người bị chính quyền Tưởng Giới Thạch bắt giam và giải đi khắp các nhà giam ở Quảng Tây, Trung Quốc.” 1TREC: Text REtrieval Conference. 2 CLEF: The Cross-Language Evaluation Forum. 4 “Nhật ký trong tù, dịch tiếng Hán- Ngục trung nhật ký là một tập thơ của Hồ Chí Minh,…”. Hay câu hỏi “Mozart sinh năm nào ?” và câu trả lời “….Mozart (1751 – 1791)…”. Để tìm được câu trả lời trên cho câu hỏi, hệ thống cần cĩ cơ chế để biết được rằng “tác giả của một tập thơ là người viết tập thơ đĩ” hoặc cần học được các mẫu thường gặp của câu trả lời (các mẫu về ngày tháng năm sinh, về thời gian, địa chỉ….) tương ứng với từng loại câu hỏi. Các hệ thống Q&A trên thế giới hiện nay sử dụng rất nhiều các cơng cụ xử lý ngơn ngữ như: Bộ gán nhãn từ loại (POS Tagger), bộ nhận dạng tên thực thể (Named Entity Recognizer), bộ phân tích ngữ pháp (Parser)… và các tài nguyên ngơn ngữ như Wordnet [28], ontology [30] để phân tích câu hỏi và trích xuất câu trả lời. Năm 2000, Carbonell và các đồng nghiệp trong bài báo The Vision Statement to Guide Research in Question Answering and Text Summarization [13] đã đưa ra các tư tưởng chung cho việc nghiên cứu Q&A. Theo đĩ một hệ thống hỏi đáp được người dùng đánh giá là hữu ích nếu đáp ứng được các tiêu chuẩn: ™ Tính hợp lý về thời gian (Timeliness): Câu trả lời phải được đưa ra trong thời gian ngắn, ngay cả khi cĩ hàng ngàn người dùng cùng truy nhập hệ thống một lúc. Các nguồn dữ liệu mới cần phải được tích hợp vào hệ thống ngay khi chúng sẵn sàng để cĩ thế cung cấp cho người dùng câu trả lời cho những câu hỏi về các sự kiện cĩ tính thời sự. ™ Tính chính xác: Tính chính xác của hệ thống hỏi đáp tự động là cực kì quan trọng bởi việc đưa ra câu trả lời sai cịn tai hại hơn nhiều là khơng đưa ra câu trả lời. Nghiên cứu về Q&A cần tập trung vào việc đánh giá tính đúng đắn của câu trả lời đưa ra, bao gồm cả phương thức để phát hiện các trường hợp mà dữ liệu hiện thời khơng chứa câu trả lời cho câu hỏi. Các thơng tin mâu thuẫn trong dữ liệu cũng cần được tìm ra và các thơng tin này cần được xử lý theo một cách phù hợp, nhất quán. Để đạt được sự chính xác, hệ thống Q&A cần được tích hợp các nguồn tri thức (world knowledge ) và cơ chế “bắt chước” việc suy luận thơng thường (việc bắt chước cĩ thể hiểu như là một quá trình học). ™ Tính khả dụng: Hệ thống Q&A cần đáp ứng được các yêu cầu cụ thể của một người dùng. Các ontology trên từng miền cụ thể và ontology trên miền mở cần được tích hợp trong hệ thống. Hệ thống Q&A cần cĩ khả năng khai phá câu trả lời 5 từ bất kì dạng dữ liệu gì (văn bản, web, cơ sở dữ liệu, …) và đưa ra câu trả lời dưới định dạng mà người dùng mong muốn, cho phép người dùng miêu tả ngữ cảnh của câu hỏi và cung cấp các thơng tin giải thích, trích dẫn nguồn cho câu trả lời. ™ Tính hồn chỉnh: Câu trả lời hồn chỉnh cho câu hỏi của người dùng là điều mà các hệ thống Q&A hướng tới. Trong nhiều trường hợp (câu hỏi về danh sách, nguyên nhân, cách thức…), các phần của câu trả lời nằm rải rác trong một văn bản, thậm chí trong nhiều văn bản. Vì vậy cần phải hợp nhất các phần này dựa trên các thơng tin liên kết để tạo ra câu trả lời hồn chỉnh. ™ Tính thích hợp của câu trả lời: Trong ngơn ngữ tự nhiên, câu hỏi đưa ra luơn gắn với ngữ cảnh nào đĩ và câu trả lời cũng nằm trong một ngữ cảnh nhất định. Câu trả lời mà hệ thống Q&A đưa ra phải phù hợp ngữ cảnh với câu hỏi. Một hệ thống Q&A cĩ khả năng giao tiếp (interactive Q&A) là cần thiết trong nhiều trường hợp bởi chuỗi các câu hỏi liên quan đến một vấn đề sẽ giúp làm sáng tỏ thơng tin mà người dùng đang hỏi. Việc đánh giá một hệ thống Q&A cần hướng người dùng bởi ý kiến người dùng là đánh giá tốt nhất cho tính thích hợp của câu trả lời. Các tiêu chuẩn trên được đặt ra với mong muốn xây dựng được một hệ thống Q&A hồn chỉnh. Tuy nhiên, khơng phải hệ thống nào cũng cĩ khả năng thơng minh và hồn thiện như thế. Các nghiên cứu về Q&A hiện nay đang tập trung vào xây dựng hệ thống hỏi đáp cĩ tính chính xác cao và cĩ khả năng sử dụng nguồn dữ liệu web khổng lồ trên Internet. 1.2. Phân loại hệ thống hỏi đáp tự động Cĩ nhiều cách phân loại hệ thống hỏi đáp dựa trên các tiêu chí khác nhau như: phân loại theo miền ứng dụng, theo khả năng trả lời câu hỏi, theo cách tiếp cận giải quyết bài tốn… 1.2.1. Phân loại theo miền ứng dụng (domain) Hệ thống hỏi đáp miền mở (open domain Question answering): Hệ thống trả lời bất kỳ câu hỏi nào được đưa vào. Khĩ khăn cho hệ thống miền mở đĩ chính là việc xây dựng các tri thức nên cho việc trả lời cũng như phân tích câu hỏi, các phương pháp hiện nay thường sử dụng một số các ontology khái quát hay các mạng tri thức như: wikipedia, bách khoa từ điển... Tuy nhiên, dữ liệu cho việc trích rút câu trả lời là phong phú, dễ thu thập. 6 Hệ thống hỏi đáp miền đĩng (close domain Question answering): Hệ thống tập trung vào trả lời các câu hỏi liên quan đến một miền cụ thể (giáo dục, y tế, thể thao...). Xây dựng hệ thống hỏi đáp miền đĩng được coi là bài tốn dễ hơn so với xây dựng hệ thống hỏi đáp miền mở vì cĩ thể sử dụng các tri thức miền (thường là ontology của miền cụ thể). Hình 1. Xu hướng trong nghiên cứu về Q&A Các nghiên cứu hiện nay về Q&A đang tập trung vào xây dựng hệ thống hỏi đáp trên miền mở, sử dụng nguồn dữ liệu phi cấu trúc (kho văn bản lớn hay dữ liệu web) để tìm câu trả lời. Các nghiên cứu mới và cải tiến những phương pháp cũ để cĩ thể áp dụng cho nguồn dữ liệu web vốn đa dạng, nhiều “nhiễu” và trùng lặp đang rất được quan tâm [27] (Hình 1). 1.2.2. Phân loại theo khả năng trả lời câu hỏi Hệ thống cĩ khả năng trả lời các câu hỏi liên quan đến sự vật, hiện tượng,... dựa trên việc trích ra câu trả lời cĩ sẵn trong tập tài liệu. Câu trả lời là các chuỗi ký tự trong một tài liệu. Kỹ thuật chính được sử dụng là xử lý chuỗi và từ khĩa. Hệ thống hỏi đáp Miền đĩng Miền mở Dữ liệu cĩ cấu trúc Dữ liệu phi cấu trúc (text) Web Tập dữ liệu lớn Một văn bản đơn 7 Hệ thống cĩ cơ chế lập luận đơn giản: Trích xuất các câu trả lời cĩ sẵn trong tập tài liệu sau đĩ sử dụng các suy luận để tìm mối liên kết giữa câu trả lời và câu hỏi. Hệ thống sử dụng các nguồn tri thức như ontology về từng miền cụ thể và ontology chung. Hệ thống trả lời các câu hỏi yêu cầu khả năng tổng hợp: Các phần của câu trả lời được trích rút từ nhiều tài liệu sau đĩ được tổng hợp lại thành câu trả lời hồn chỉnh. Câu hỏi thường là về danh sách, về cách thức, nguyên nhân... Hệ thống cĩ khả năng giao tiếp với người dùng: Trả lời chuỗi các câu hỏi của người dùng về cùng một vấn đề. Ví dụ các câu hỏi của người dùng như: “Giáo sư A sinh năm nào? Ở đâu? Ơng ấy đang cơng tác ở đâu?”. Hệ thống cĩ khả năng lập luận tương tự: Cĩ thể trả lời các câu hỏi cĩ tính chất suy đốn, câu trả lời ẩn trong tập tài liệu. Hệ thống cần trích ra các luận chứng và sử dụng lập luận tương tự để tìm ra câu trả lời [19]. 1.2.3. Phân loại theo hướng tiếp cận: Hướng tiếp cận nơng (shalow): Nhiều phương pháp sử dụng trong Q&A dùng các kĩ thuật dựa trên từ khĩa để định vị các câu, đọan văn cĩ khả năng chứa câu trả lời từ các văn bản được trích chọn về. Sau đĩ giữ lại các câu, đoạn văn cĩ chứa chuỗi ký tự cùng loại với loại câu trả lời mong muốn (ví dụ các câu hỏi về tên người, địa danh, số lượng…). Hướng tiếp cận sâu (deep): Trong những trường hợp khi mà hướng tiếp cận bề mặt khơng thể tìm ra câu trả lời, những quá trình xử lý về ngữ pháp, ngữ nghĩa và ngữ cảnh là cần thiết để trích xuất hoặc tạo ra câu trả lời. Các kĩ thuật thường dùng như nhận dạng thực thể (named-entity recognition), trích xuất mối quan hệ, loại bỏ nhập nhằng ngữ nghĩa,… Hệ thống thường sử dụng các nguồn tri thức như Wordnet, ontology để làm giàu thêm khả năng lập luận thơng qua các định nghĩa và mối liên hệ ngữ nghĩa. Các hệ thống hỏi đáp dựa theo mơ hình ngơn ngữ thống kê cũng đang ngày càng phổ biến. 1.3. Các bước chung của hệ thống hỏi đáp tự động Một hệ thống hỏi đáp tự động thường gồm 3 bước chung sau: Bước1-Phân tích câu hỏi: Bước phân tích câu hỏi tạo truy vấn cho bước trích chọn tài liệu liên quan và tìm ra những thơng tin hữu ích cho bước trích xuất câu trả lời 8 Bước2-Trích chọn tài liệu liên quan: Bước này sử dụng câu truy vấn được tạo ra ở bước phân tích câu hỏi để tìm các tài liệu liên quan đến câu hỏi. Bước3-Trích xuất câu trả lời: Bước này phân tích tập tài liệu trả về từ bước 2 và sử dụng các thơng tin hữu ích do bước phân tích câu hỏi cung cấp để đưa ra câu trả lời chính xác nhất. Hình 2. Các bước chung của hệ thống Q&A Các hệ thống hỏi đáp tự động hiện nay cĩ kiến trúc rất đa dạng, tuy nhiên chúng đều bao gồm ba phần cơ bản như trên [15,18,27]. Sự khác nhau chính giữa các hệ thống là ở quá trình xử lý trong từng bước, đặc biệt là ở cách tiếp cận trong việc xác định câu trả lời. Cách tiếp cận theo trích chọn thơng tin thuần túy (pure IR) là: chia nhỏ một tài liệu trong tập dữ liệu thành chuỗi các tài liệu con, trích chọn các tài liệu con cĩ độ tương đồng lớn nhất với câu truy vấn (do bước phân tích câu hỏi tạo ra) và trả lại chúng cho người dùng.Thách thức lớn nhất ở đây là làm sao chia nhỏ được tài liệu thành các phần với kích cỡ tương ứng với kích cỡ của câu trả lời mà vẫn đủ lớn để cĩ thể đánh chỉ mục được (nếu chia quá nhỏ thì số lượng tài liệu để đánh chỉ mục sẽ rất lớn, gây gánh nặng cho hệ thống trích chọn thơng tin). Phân tích câu hỏi Trích chọn tài liệu liên Trích xuất câu trả lời Câu hỏi Câu trả lời 9 Cách tiếp cận theo xử lý ngơn ngữ tự nhiên (pure NLP) là: so khớp giữa biểu diễn ngữ pháp và (hoặc) biểu diễn ngữ nghĩa của câu hỏi với dạng biểu diễn ngữ pháp, ngữ nghĩa của các câu trong các tài liệu liên quan trả về. Khĩ khăn của cách tiếp cận này là hệ thống phải thực hiện việc phân tích ngữ pháp, ngữ nghĩa và so khớp đủ nhanh để đưa ra câu trả lời trong thời gian chấp nhận được, bởi số lượng các tài liệu cần xử lý là rất lớn trong khi các bước phân tích trên lại phức tạp và tốn nhiều thời gian. Sự khác nhau trong cách trích xuất câu trả lời dẫn đến việc phân tích câu hỏi cũng trở nên đa dạng. Trong hướng tiếp cận theo trích xuất thơng tin thuần túy, phân tích câu hỏi chỉ cần làm tốt việc tạo truy vấn, trong khi với hướng tiếp cận theo xử lý ngơn ngữ tự nhiên, câu hỏi cần được phân tích ngữ pháp, ngữ nghĩa một cách chính xác. Các hệ thống hiện nay thường là sự kết hợp giữa hai hướng tiếp cận, sử dụng hệ thống trích chọn thơng tin để thu hẹp khơng gian tìm kiếm câu trả lời, đồng thời phân tích câu hỏi để tìm ra các thơng tin về ngữ pháp, ngữ nghĩa nhằm tìm ra câu trả lời chính xác nhất. Kết quả của bước phân tích câu hỏi là đầu vào cho cả hai bước trích chọn tài liệu liên quan và trích xuất câu trả lời. Bước phân tích câu hỏi cĩ ý nghĩa rất quan trọng, bởi nĩ ảnh hưởng đến hoạt động của các bước sau và do đĩ quyết định đến hiệu quả của tồn hệ thống. Chương 2 trình bày chi tiết các nội dung liên quan đến phân tích câu hỏi. 10 Chương 2. Phân tích câu hỏi 2.1. Nội dung của phân tích câu hỏi Bài tốn phân tích câu hỏi: Phân tích câu hỏi nhận đầu vào là câu hỏi dưới dạng ngơn ngữ tự nhiên của người dùng, đưa ra câu truy vấn cho bước trích chọn tài liệu liên quan và các thơng tin cần thiết cho bước trích rút câu trả lời. Câu truy vấn là dạng tổ hợp của các từ khĩa quan trọng trong câu hỏi (và các từ khĩa mở rộng) với các phép tốn tập hợp AND, OR. Các kĩ thuật biến đổi câu hỏi thành câu truy vấn được trình bày trong phần 2.5.1. Các thơng tin cần thiết để trích xuất câu trả lời là rất đa dạng, tùy phuộc vào phương pháp trích xuất câu trả lời. Thơng thường các thơng tin đĩ là mục đích của câu hỏi (ví dụ mục đích hỏi để khẳng định một điều, để so sánh hay để tìm kiếm thơng tin, để hỏi về định nghĩa, cách thức…), loại câu trả lời mong đợi (question target hay answer type). Ví dụ câu hỏi “Dân số Việt Nam là bao nhiêu”, câu trả lời được mong đợi là một “con số” hay câu hỏi “Ai là tổng thống Mỹ” thì loại câu trả lời là một “tên người”. Một số thơng tin hữu ích cho trích xuất câu trả lời khác như định dạng của câu trả lời (người hỏi muốn câu trả lời là một dạng ngắn gọn như con số, tên người, địa chỉ hay là một đoạn văn bản dài về định nghĩa, mơ tả, nguyên nhân, …), dạng biểu diễn ngữ pháp, ngữ nghĩa của câu hỏi để so khớp (matching) và xếp hạng (ranking) các câu trả lời. 2.2. Khĩ khăn của phân tích câu hỏi Câu hỏi đầu vào của hệ thống hỏi đáp tự động là câu hỏi dưới dạng ngơn ngữ tự nhiên của người dùng. Vì vậy việc phân tích câu hỏi cũng gặp những khĩ khăn của xử lý ngơn ngữ tự nhiên. Theo Hồ Tú Bảo và Lương Chi Mai [1], cái khĩ nằm ở chỗ làm sao cho máy tính được hiểu ngơn ngữ con người, từ việc hiểu nghĩa từng từ trong mỗi hồn cảnh cụ thể, đến việc hiểu nghĩa của cả câu hỏi, hiểu câu hỏi đang hỏi về cái gì và người hỏi mong muốn cái gì. Mấu chốt ở đây là bản chất phức tạp của ngơn ngữ của con người, đặc biệt là sự đa nghĩa và nhập nhằng ngữ nghĩa của ngơn ngữ. Thêm nữa, cĩ một khác biệt sâu sắc là con người ngầm hiểu và dùng quá nhiều lẽ thường (common sense) trong ngơn ngữ, như khi hỏi về “thời tiết” thì tức là hỏi về “nhiệt độ, độ ẩm, mưa, nắng …”, hay 11 biết “sợi dây” thì dùng để kéo chứ khơng dùng để đẩy hay khều các vật, trong khi rất khĩ làm cho máy hiểu các lẽ thường này. Cùng hỏi về một thơng tin nhưng câu hỏi cĩ thể được diễn đạt theo nhiều cách khác nhau, sử dụng từ ngữ, cấu trúc câu khác nhau, lúc ở dạng nghi vấn, lúc lại ở dạng khẳng định. Vì vậy cần thiết phải cĩ một mơ hình ngữ nghĩa để hiểu và xử lý câu hỏi, cĩ khả năng nhận diện được các câu hỏi tương đương bất kể nĩ ở dạng khẳng định, nghi vấn hay các từ ngữ và quan hệ ngữ pháp giữa chúng khác nhau hoặc các dạng thành ngữ, tu từ. Mơ hình này cũng cần cĩ khả năng chuyển đổi các câu hỏi phức tạp thành chuỗi các câu hỏi đơn giản hơn, cĩ thể xác định được các nhập nhằng và xử lý chúng theo ngữ cảnh hoặc sử dụng cách thức giao tiếp với người dùng để làm rõ ngữ nghĩa. Xử lý câu hỏi cũng cần phải cĩ cơ chế để xử lý các câu hỏi tiếp sau liên quan đến cùng một vấn đề của câu hỏi trước, sử dụng các thơng tin thu được ở câu hỏi trước để làm sáng tỏ câu hỏi tiếp sau, cao hơn nữa là cĩ thể đối thoại với người dùng theo chuỗi các câu hỏi và câu trả lời. 2.3. Một số nội dung của xử lý ngơn ngữ tự nhiên trong phân tích câu hỏi Đầu vào của pha phân tích câu hỏi là câu hỏi dạng ngơn ngữ tự nghiên, do đĩ phân tích câu hỏi cĩ liên quan đến một số nội dung của xử lý ngơn ngữ tự nhiên. Theo [1] việc xử lý ngơn ngữ tự nhiên thường bao gồm các bước (tầng, layer) cơ bản sau: ™ Tầng hình thái (morphological layer): Nghiên cứu về các thành phần cĩ nghĩa của từ (word), như từ được tạo ra bởi các hình vị (morphemes) và từ được tách ra trong một câu thế nào. Thí dụ, từ “tiếng Việt” tạo thành từ “t-iế-ng V-iệ-t”, cịn ngữ (phrase) “xử lý tiếng Việt” tạo thành gồm hai từ “xử lý” và “tiếng Việt”. Trong tiếng Việt, một bài tốn quan trọng là phân tách từ (word segmentation). Một thí dụ quen thuộc là câu “Ơng già đi nhanh quá” cĩ thể phân tách thành (Ơng già) (đi) (nhanh quá) hoặc (Ơng) (già đi) (nhanh quá) hoặc những cách khác nữa. ™ Tầng ngữ pháp (syntactic layer): Nghiên cứu các quan hệ cấu trúc giữa các từ, xem các từ đi với nhau thế nào để tạo ra câu đúng. Quá trình này thường được cụ thể trong các bước cơ bản sau: 12 o Xác định từ loại (POS tagging): Xem mỗi từ trong câu là loại gì (danh từ, động từ, giới từ, …). Trong thí dụ trên, cĩ thể “Ơng già” là danh từ, “đi” là động từ, “nhanh” là trạng từ, và “quá” là thán từ. o Xác định cụm từ (chunking): Thí dụ “Ơng già” là cụm danh từ, “đi” là cụm động từ, “nhanh quá” là cụm trạng từ. Như vậy câu trên cĩ hai phân tích (Ơng già) (đi) (nhanh quá) hoặc (Ơng) (già đi) (nhanh quá). o Xác định quan hệ ngữ pháp(parsing): (Ơng già) (đi) (nhanh quá) là quan hệ chủ ngữ-vị ngữ-trạng ngữ. ™ Tầng ngữ nghĩa (semantic layer): Nghiên cứu xác định nghĩa của từng từ và tổ hợp của chúng để tạo nghĩa của câu. Thí dụ trong phân tích (Ơng già) (đi) (nhanh quá), động từ “đi” cĩ thể cĩ nghĩa “bước đi”, hay “chết” hay “điều khiển” (khi đánh cờ), … và tương ứng ta cĩ các nghĩa khác nhau của câu. ™ Tầng ngữ dụng (pragmatic layer): Nghiên cứu mối quan hệ giữa ngơn ngữ và ngữ cảnh sử dụng ngơn ngữ (context-of-use). Ngữ dụng nghiên cứu việc ngơn ngữ được dùng để nĩi về người và vật như thế nào. Việc phân tích câu hỏi ở các tầng từ tầng hình thái đến tầng ngữ pháp gọi là phân tích sơ bộ (shallow parsing). Nếu phân tích thêm cả tầng ngữ nghĩa ta sẽ cĩ phân tích đầy đủ (fully parsing). Phân tích câu hỏi đến tầng nào cũng tùy thuộc vào từng hệ thống, vào phương pháp trích xuất câu trả lời và các cơng cụ hỗ trợ phân tích ngơn ngữ đến đâu. Hệ thống AskMSR [8,12] đưa ra phương pháp phân tích câu hỏi và trích xuất câu trả lời rất đơn giản, chỉ phân tích câu hỏi ở tầng hình thái, sử dụng các từ vựng trong câu hỏi để tìm ra các câu trả lời ứng viên. Theo Michele Banko [8] thì đối với nhiều câu hỏi dạng đơn giản, hỏi về các sự vật, hiện tượng, … (factual-base question) thì dạng của câu hỏi và câu trả lời khá tương đồng nhau. Ví dụ với câu hỏi: “Where is the Louvre Museum located ?” câu trả lời thường cĩ dạng “…Louvre Museum is located at/in/near …” Hay câu hỏi: “What is search engine ?” thì câu trả lời cĩ dạng: “…search engine is …”. 13 Vì vậy bước phân tích câu hỏi trong AskMSR là viết lại câu hỏi dưới dạng truy vấn thích hợp cho module tìm kiếm tài liệu. Với câu hỏi đầu vào, hệ thống sẽ viết lại câu hỏi theo một số cách để sinh ra các chuỗi kí tự được cho là một phần của câu trả lời. Việc viết lại câu hỏi chỉ dựa vào xử lý chuỗi đơn giản, khơng sử dụng các bộ phân tích ngữ pháp hay gán nhãn từ loại mà dùng các luật và trọng số cho từng luật do con người tự làm. Ưu điểm của phương pháp này là đơn giản, tuy nhiên lại khơng thể áp dụng được với các câu hỏi phức tạp, hoặc khơng trích được câu trả lời trong tập dữ liệu do khơng cĩ tài liệu nào chứa câu trả lời cĩ dạng tương tự với câu hỏi. Hệ thống Webclopedia lại phân tích câu hỏi kĩ hơn tới mức ngữ pháp. Các bước chính của hệ thống bao gồm: ™ Phân tích ngữ pháp cho câu hỏi: sử dụng bộ phân tích cú pháp CONTEX ™ Tạo truy vấn: Tạo truy vấn bằng cách kết hợp các từ đơn và cụm từ trong câu hỏi, sử dụng Wordnet để mở rộng truy vấn. ™ Trích chọn thơng tin IR: Hệ IR trả về danh sách cĩ xếp hạng của 1000 tài liệu liên quan . ™ Phân đoạn: Mục đích nhằm giảm khối lượng dữ liệu cần xử lí. Các tài liệu được chia nhỏ thành các đoạn (segments) cĩ sự liên kết về ngữ nghĩa (các đoạn văn trong 1 tài liệu,…). ™ Xếp hạng các đoạn: Mỗi đoạn văn bản được đánh trọng số theo cơng thức về độ trùng lặp từ và cụm từ với câu hỏi và truy vấn mở rộng, theo đĩ các từ cĩ trong câu hỏi cĩ trọng số 2, từ đồng nghĩa cĩ trọng số 1, các từ khác cĩ trọng số 0. Sau đĩ các đoạn được sắp xếp theo trọng số giảm dần. ™ Phân tích ngữ pháp cho các đoạn: Sử dụng CONTEX để phân tích cú pháp cho các câu trong top 100 đoạn đã xếp hạng. ™ Xác định câu trả lời: Với mỗi câu, ba bước so khớp (matching) được thực hiện, trong đĩ hai bước thực hiện việc so sánh biểu diễn cú pháp của câu hỏi và câu, bước 3 thực hiện việc tính độ match trên mức từ và cụm từ bằng phương pháp cửa sổ trượt. ™ Xếp hạng câu trả lời: Các câu trả lời ứng viên (câu được phân tích ở bước trước) được sắp xếp theo độ match. Hệ thống trả về câu trả lời cĩ độ match tốt nhất. 14 Như đã nĩi ở phần trên, cĩ rất nhiều cách diễn đạt để hỏi về cùng một thơng tin, và cũng cĩ nhiều cách để đưa ra câu trả lời. Những dạng biến đổi này hình thành nên một lớp câu hỏi và lớp câu trả lời cĩ ngữ nghĩa tương đồng. Người dùng cĩ thể hỏi với bất kì dạng nào của câu hỏi và tập tài liệu cũng cĩ thể chứa bất kì dạng nào của câu trả lời, do đĩ hệ thống hỏi đáp cần cĩ khả năng gộp các loại câu hỏi và câu trả lời tương đồng với nhau [19]. Với một câu hỏi bất kì nếu xác định được loại câu hỏi thì cĩ thể biết được các dạng của câu trả lời do cĩ mỗi liên hệ mật thiết giữa loại câu hỏi và loại câu trả lời. Tuy nhiên sự tương đương ngữ nghĩa cũng khơng rõ ràng, kể cả các biến thể nhỏ cũng tạo ra sự khác biệt. Ví dụ với câu hỏi “Ai phát minh ra bĩng đèn điện ?”, câu trả lời cĩ thể chấp nhận là “Thomas Edison” hoặc “một nhà phát minh người Mỹ”. Trong khi câu hỏi “Tên người phát minh ra bĩng đèn điện?” thì chỉ chấp nhận câu trả lời “Thomas Edison”. Điều này dẫn đến việc tổ chức loại câu hỏi, loại câu trả lời dưới dạng phân cấp, cho phép câu trả lời cho lớp con cĩ thể trả lời được cho lớp cha, nhưng khơng thể cĩ chiều ngược lại. Như ví dụ trên thì cĩ thể coi câu hỏi thứ nhất là về “Con người” – PERSON , cịn câu hỏi thứ hai là về “Danh từ riêng chỉ người” – PROPER NAME và lớp PROPER NAME là lớp con của lớp PERSON. Nhiều nghiên cứu trước đây về Q&A đều cĩ sử dụng một cách phân loại câu hỏi nào đĩ. Cĩ hệ thống phân loại theo từ để hỏi (who, what, when …), cĩ hệ thống phân loại câu hỏi theo loại câu trả lời. Phần tiếp theo của khĩa luận khảo sát các các cách phân loại câu hỏi hay cịn gọi là taxonomy câu hỏi. 2.4. Taxonomy câu hỏi 2.4.1. Khái niệm về taxonomy Vào những năm 90 của thế kỉ XX, khái niệm taxonomy được sử dụng trong nhiều lĩnh vực khác nhau như tâm lý học, khoa học xã hội và cơng nghệ thơng tin... để thiết lập sự trùng hợp giữa thuật ngữ của người sử dụng và thuật ngữ của hệ thống. Các chuyên gia đầu tiên phát triển cấu trúc hệ thống Web đã dùng thuật ngữ taxonomy để nĩi về tổ chức nội dung các trang web. Và từ đĩ, khái niệm taxonomy được sử dụng rộng rãi với mục đích này. 15 Do được sử dụng trong nhiều lĩnh vực khác nhau, nên cĩ nhiều định nghĩa khác nhau về taxonomy. Từ năm 2000 đến năm 2005, cĩ khoảng 36 định nghĩa1 khác nhau về taxonomy trong các nguồn tài liệu. Trong lĩnh vực cơng nghệ thơng tin, taxonomy được định nghĩa như sau: Định nghĩa: Taxonomy là sự phân loại của tồ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. Một taxonomy thường được mơ tả với gốc ở trên cùng, mỗi nút của taxonomy – bao gồm cả gốc – là một thực thể thơng tin đại diện cho một thực thể trong thế giới thực. Giữa các nút trong taxonomy cĩ một mối quan hệ đặc biệt gọi là is subclassification of nếu hướng liên kết từ nút con lên nút cha hoặc là is superclassification of nếu hướng liên kết từ nút cha xuống nút con. Đơi khi những quan hệ này được xác định một cách chặt chẽ hơn là is subclass of hoặc is superclass of, nếu thực thể thơng tin là một lớp đối tượng. 2.4.2. Taxonomy câu hỏi Trong Q&A Roadmap [10] đã chỉ ra rằng taxonomy câu hỏi là rất cần thiết trong nghiên cứu về Q&A. Các nghiên cứu về taxonomy câu hỏi đã được nhiều nhà nghiên cứu quan tâm, trên các mặt về ngơn ngữ học, triết học, xã hội học, cĩ nền tảng lý thuyết lẫn thực nghiệm. Năm 1972, Robinson và Rackstraw đã nghiên cứu về cách sử dụng các từ để hỏi trong tiếng Anh, theo đĩ “the Five Ws” (Who, What, When, Where, Why, và How) là cách phân loại câu hỏi thơng thường và đơn giản nhất. Cĩ lẽ bởi “the Five Ws” là cách suy nghĩ rất tự nhiên khi đặt câu hỏi của người dùng tiếng Anh nên nĩ rất phổ biến trong các tài liệu và trong hỏi đáp thơng thường. Robinson và Rackstraw đã dành 2 tập sách [31,32] để khảo sát về wh-words, hình thức câu hỏi dựa vào wh-words và câu trả lời cho các câu hỏi này. Robinson và Rackstraw định nghĩa wh-words là “tập hồn tồn của các từ để hỏi về mặt từ vựng” (“the total set of lexically marked interrogative words”). (1972a). Họ đưa ra một taxonomy câu hỏi 7 lớp bao gồm:Who, Which, What, When, Where, Why, How. Cĩ hai vấn đề với taxonomy trên là: Câu hỏi khơng nhất thiết phải là câu cĩ sử dụng từ để hỏi wh-words và khơng phải câu nào cĩ sử dụng từ để hỏi wh-words cũng đều là 1 16 câu hỏi. Một câu hỏi cĩ dạng của một câu phát biểu nhưng cĩ thể được hiểu và chấp nhận như là một câu hỏi. Ví dụ câu “I’m looking for the name of the Secretary of State under Clinton” tương đương với câu “Who was the Secretary of State under Clinton?”. Các cách nĩi tu từ, biểu cảm rất hay sử dụng các từ wh-words ví dụ câu “What a beautiful car!” hay “Why me?” đều khơng phải là các câu cĩ mục đích hỏi. Một vài hệ thống Q&A trong hội nghị TREC sử dụng wh-words như là các tiêu chuẩn chính trong phân tích và biểu diễn logic của câu hỏi [18,29]. Một số hệ thống chia nhỏ các lớp câu hỏi wh-words thành các lớp con nhằm cho phép hệ thống Q&A cĩ thể nhận diện được “kiểu ngữ nghĩa (semantic types) của câu trả lời mong muốn”. Dan Moldovan và đồng nghiệp đưa ra một taxonomy phân loại câu hỏi phân cấp theo cả từ để hỏi lẫn loại câu trả lời mong muốn tương ứng [29]. Eduard Hovy [18] chỉ ra rằng việc phân lớp câu hỏi theo loại ngữ nghĩa của câu trả lời là rất quan trọng. Ví dụ câu hỏi “How tall is Mt. Everest?”, hệ thống Q&A chỉ cĩ thể trả lời được câu hỏi này được nếu nĩ biết rằng câu trả lời được mong đợi sẽ chứa một đại lượng về kích thước. Nhiều hệ Q&A sử dụng bộ nhận dạng thực thể (Named Entity Recognizer) cĩ khả năng nhận diện được tên người, tên tổ chức, con số, thời gian, địa điểm…để hỗ trợ việc tìm câu trả lời khi biết được loại câu trả lời là gì và thu được độ chính xác rất cao. Eduard Hovy trong [19] đã khảo sát 17384 câu hỏi và câu trả lời tương ứng được thu thập từ trang web answers.com và đưa ra taxonomy câu hỏi dựa trên loại ngữ nghĩa của câu trả lời với 94 nút trong đĩ cĩ 47 nút lá. Mỗi nút đều được chú thích bởi các câu hỏi, câu trả lời ví dụ và các mẫu câu hỏi, câu trả lời tiêu biểu của lớp. Cùng nghiên cứu về phân lớp câu hỏi theo loại câu trả lời, Li và Roth [25, 26] đã đưa ra taxonomy phân cấp theo sự phân loại ngữ nghĩa tự nhiên của câu trả lời cho các câu hỏi được khảo sát từ hội nghị TREC. Cấu trúc phân cấp bao gồm 6 lớp câu hỏi thơ (coarse classes) là 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ố). Mỗi lớp câu hỏi thơ lại được phân chia thành các lớp con (fine class). Taxonomy câu hỏi của Li và Roth được trình bày chi tiết trong bảng 1.Taxonomy này cùng bộ dữ liệu câu hỏi đã gán nhãn của Li và Roth được nhiều nhĩm nghiên cứu sử dụng lại bởi nĩ bao phủ được hầu hết các loại câu hỏi thường gặp trong thực tế. Trong thực nghiệm chương 4 chúng tơi cũng sử dụng taxonomy này cho phân lớp câu hỏi tiếng Việt. 17 Bảng 1. Taxonomy câu hỏi do Li và Roth đưa ra Nhãn lớp Định nghĩa ABBREVIATION Dạng viết tắt abb Dạng viết tắt exp ý nghĩa của từ viết tẳt ENTITY Thực thể animal Động vật body Các bộ phận cở thế color Màu sắc creative Phát minh, sách và các sáng tạo khác currency Tiền tệ dis.med. Bệnh tật và y học event Sự kiện food Đồ ăn instrument Dụng cụ âm nhạc lang Ngơn ngữ letter Chữ cái ( kí tự ) other Các thực thể khác plant Thực vật product Sản phẩm religion Tơn giáo, tín ngưỡng sport Thể thao substance Nguyên tố, vật chất symbol Biểu tượng, kí hiệu technique Kĩ thuật và phương pháp term Thuật ngữ tương đương vehicle Phương tiện giao thơng word Từ với tính chất đặc biệt DESCRIPTION Mơ tả và các khái niệm trừu tuộng definition Định nghĩa về một thú gì đĩ 18 description Mơ tả về một thứ gì đĩ manner Cách thức của hành động reason Lý do HUMAN Con người group Một nhĩm người hoặc một tổ chức ind Một cá nhân riêng lẻ title Tư cách, danh nghĩa, chức vụ của một người description Mơ tả về một người nào đĩ LOCATION Địa điểm city Thành phố country Đất nước mountain Núi other Các địa điểm khác state Bang, tỉnh thành NUMERIC Giá trị số code Mã thư tín và các mã khác count Số lượng của cái gì đĩ date Ngày tháng distance Khoẳng cách, đo lường tuyến tính money Giá cả order Thứ hạng other Các số khác period Khoảng thời gian percent Phần trăm speed Tốc độ temp Nhiệt độ size Kích thước, diện tích, thể tích weight Cân nặng 19 2.5. Khảo sát các phương pháp phân tích câu hỏi cho các loại câu hỏi khác nhau Trong hội nghị TREC, các câu hỏi được chia thành một số loại sau: câu hỏi đơn giản (factual-base question), câu hỏi định nghĩa (definition question), câu hỏi danh sách (list question), câu hỏi phức tạp (complex question),…. Mỗi loại câu hỏi cĩ những đặc trưng riêng và hướng tiếp cận khác nhau. 2.5.1. Câu hỏi đơn giản (factual-base) Câu hỏi factual-base là những câu hỏi về các sự vật, sự kiện đơn lẻ,.. cĩ câu trả lời là những đoạn văn bản ngắn nằm sẵn trong tài liệu. Kiến trúc thơng thường để xử lý loại câu hỏi này như sau (Hình 3): Câu hỏi đầu vào được phân lớp theo loại ngữ nghĩa của câu trả lời và biến đổi sang dạng truy vấn. Câu truy vấn được sử dụng để tìm kiếm các tài liệu cĩ liên quan đến câu hỏi, loại câu hỏi được sử dụng trong phần trích xuất câu trả lời nhằm thu hẹp khơng gian tìm kiếm và kiểm tra câu trả lời cĩ chính xác hay khơng [35]. Hình 3. Kiến trúc cho xử lý các câu hỏi factual-base Như vậy, hai cơng việc chính của pha xử lý câu hỏi với loại câu hỏi này là xác định loại câu hỏi và tạo truy vấn cho hệ IR (information retrieval) trích chọn tài liệu liên quan. Xác định loại câu hỏi Xác định loại câu hỏi cĩ ý nghĩa rất quan trọng trong phân tích các câu hỏi factual base, đặc biệt là việc phân loại câu hỏi theo loại ngữ nghĩa của câu trả lời (như mục 2.3 đã NER NER Kho tài liệu Phân tích câu hỏi Trích chọn tài liệu liên quan Trích xuất câu trả lời WordNet Parser WordNet Parser Truy vấn Tài liệu Loại câu hỏi Câu trả lời Câu hỏi 20 trình bày). Cĩ nhiều cách để xác định loại câu hỏi như: xây dựng bộ phân lớp câu hỏi sử dụng học máy thống kê, xác định câu hỏi sử dụng các kỹ thuật của xử lý ngơn ngữ tự nhiên, xác định loại câu hỏi dựa vào so khớp với các mẫu quan hệ cĩ sẵn. Nội dung chi tiết của các phương pháp này được trình bày ở chương 3. Tạo truy vấn từ câu hỏi Vấn đề của tạo truy vấn là lựa chọn các từ khĩa trong câu hỏi và kết hợp chúng để tạo ra câu truy vấn khơng quá chung chung, cũng khơng quá chi tiết. Chiến lược được sử dụng để trích ra các từ khĩa quan trọng là sử dụng độ ưu tiên: Độ ưu tiên cao nhất được gán cho các từ trong dấu nháy kép hoặc nháy đơn, tiếp đến là các cụm danh từ, danh từ, động từ, tính từ, trạng từ. Các từ dừng, giới từ, trợ động từ được bỏ qua. Nhiều hệ thống Q&A cĩ độ hồi tưởng (tỉ lệ câu trả lời đưa ra trên câu hỏi đầu vào) rất thấp. Một số nguyên nhân chính bao gồm: module phân tích câu hỏi khơng nhận diện được câu hỏi thuộc loại nào hoặc khơng tìm được các mẫu khớp với câu hỏi, module trích chọn thơng tin (IR) khơng tìm ra được các tài liệu cĩ chứa câu trả lời, module trích xuất câu trả lời khơng thể tìm ra câu trả lời thỏa đáng cho câu hỏi. Vì vậy với module trích chọn thơng tin trong hệ thống Q&A, độ hồi tưởng là quan trọng hơn so với độ chính xác bởi các module sau cĩ thể lọc ra các tài liệu khơng liên quan, nhưng khơng thể tìm ra được câu trả lời nếu các tài liệu chứa câu trả lời khơng được trả về từ IR [34] . Các nghiên cứu trước đây nhằm làm tăng độ hồi tưởng của IR đều tập trung vào việc thu nhỏ sự khác biệt về mặt hình thái, từ vựng và ngữ nghĩa giữa các từ xuất hiện trong truy vấn và trong tài liệu chứa câu trả lời. Về mặt hình thái, cĩ hai cách được sử dụng [9,34]: - Áp dụng kĩ thuật stemming cho tập dữ liệu được đánh chỉ mục và các từ trong truy vấn (stemming là chuyển tất cả các dạng biến thể của một từ thành từ gốc, ví dụ “expand”, “expanded”, “expansion”, “expandable”… đều được chuyển thành “expand”). - Đánh chỉ mục cho các từ trong tài liệu mà khơng sử dụng stemming. Sử dụng kĩ thuật mở rộng hình thái (morphological expansion – ví dụ từ “expands” được mở rộng thành {“expands”,“expand”, “expanded”, “expansion”, “expandable” , … } ) cho các từ khĩa trong câu hỏi khi tạo truy vấn. 21 Về mặt từ vựng và ngữ nghĩa, phương pháp hay được sử dụng đĩ là: các từ trong truy vấn được mở rộng bởi tập các từ đồng nghĩa, các khái niệm cĩ nghĩa khái quát hơn hoặc chuyên mơn hơn, chi tiết hơn hoặc bởi các từ liên quan. Phương pháp này địi hỏi phải cĩ các nguồn tri thức về ngơn ngữ, từ vựng như Wordnet hoặc Ontology. Moldovan trong [29] đã chỉ ra rằng từ trọng tâm của câu hỏi (question focus – xem trong phần 3.2) thường khơng xuất hiện trong tài liệu chứa câu hỏi. Với các câu hỏi cĩ từ trọng tâm là “tỉnh thành”, “thành phố”, “đất nước”, “ngày tháng”… thì câu trả lời sẽ chứa các thể hiện cụ thể của các từ này (ví dụ với “đất nước” thì sẽ là “Việt Nam”, “Trung Quốc”… chứ khơng nhất thiết phải là “đất nước Việt Nam”). Vì vậy các từ trọng tâm của câu hỏi thường khơng được sử dụng để làm từ khĩa tạo truy vấn. 2.5.2. Câu hỏi định nghĩa (definition question) Câu hỏi định nghĩa hỏi về định nghĩa hoặc mơ tả về một điều, một khái niệm gì đĩ. Các câu hỏi thường gặp cĩ dạng như “Máy tìm kiếm là gì”, “Định nghĩa khai phá dữ liệu”, “Bush là ai ?”… Câu trả lời cho loại câu hỏi này rất đa dạng, rất nhiều đoạn văn bản ngắn cĩ thể coi là câu trả lời chấp nhận được. Ví dụ với câu hỏi “Who is George W. Bush ?” thì các câu trả lời cĩ thể là: “… George W. Bush, the 43rd President of the United States…” “George W. Bush defeated Democratic incumbent Ann Richards to become the 46th Governor of the State of Texas…” …… Với loại câu hỏi định nghĩa, phương pháp thường hay được sử dụng là so khớp mẫu (pattern matching) [17]. Ví dụ về các mẫu câu hỏi và mẫu câu trả lời Mẫu câu hỏi What a ? Who ? là gì? là ai?.... Mẫu trả lời , the (a ) is a|the - - một loại là …. 22 Ưu điểm: Cĩ độ chính xác khá cao. Nhược điểm: Các mẫu khĩ cĩ thể bao quát được hết các trường hợp đa dạng của câu hỏi và câu trả lời. 2.5.3. Câu hỏi phức tạp, cĩ ràng buộc về thời gian Phương pháp trình bày trong phần 2.5.1 cĩ thể trả lời được các câu hỏi đơn giản factual base cĩ từ ngữ diễn đạt thời gian đơn giản như: “Hồ Chí Minh sinh năm nào” hoặc “Ai là thủ tướng Việt Nam năm 2009 ?”. Tuy nhiên nhiều câu hỏi phức tạp địi hỏi phải phát hiện ra các thuộc tính về thời gian hoặc thứ tự diễn ra của sự kiện. Ví dụ “Ai là tổng bí thư Đảng Cộng Sản Việt Nam trong chiến thắng lịch sử Điện Biên Phủ”. Câu hỏi liên quan đến thời gian được chia làm 4 loại [33]: Loại 1: Câu hỏi về một sự kiện đơn lẻ, khơng cĩ biểu đạt về thời gian (temporal expressions) “Đại học Cơng Nghệ thành lập khi nào ?”. Loại 2: Câu hỏi về một sự kiện đơn lẻ, cĩ biểu đạt về thời gian “Đội tuyển nào của Đại học cơng nghệ tham dự cuộc thi ACM quốc tế năm 2009” Ràng buộc thời gian: năm 2009. Loại 3: Câu hỏi cĩ nhiều sự kiện, cĩ biểu đạt về thời gian “Việt Nam đạt được những thành tựu gì sau khi chính sách mở cửa năm 1987 được thơng qua ? ” Tín hiệu thời gian: sau khi Ràng buộc thời gian: năm 1987 Loại 4: Câu hỏi cĩ nhiều sự kiện, khơng cĩ biểu đạt về thời gian “Dân số thế giới là bao nhiêu trước chiến tranh thế giới thứ 2” Tín hiệu thời gian: trước Các tín hiệu thời gian trong Tiếng Việt như: sau, sau khi, trước, trước khi, trong khi, khi, trong thời gian, …Các biểu đạt về thời gian là các từ về ngày, tháng, năm, thế kỉ,… 23 Phương pháp xử lý: Gồm 4 bước sau: - Phân tích câu hỏi thành các các câu hỏi factual-base đơn giản hơn. “Dân số thế giới là bao nhiêu trước chiến tranh thế giới thứ 2 ?” 1) “Dân số thế giới là bao nhiêu ?” 2) “Chiến tranh thế giới thứ 2 xảy ra khi nào ?” - Tìm câu trả lời cho câu hỏi thứ nhất - Tìm câu trả lời cho câu hỏi thứ hai - Đưa ra câu trả lời mà vừa trả lời câu hỏi thứ nhất, vừa cĩ giá trị thời gian thích hợp với câu trả lời cho câu hỏi thứ hai. 24 Chương 3. Các phương pháp xác định loại câu hỏi 3.1. Phương pháp phân lớp sử dụng học máy thống kê Theo [4] cĩ hai hướng tiếp cận được sử dụng rộng rãi trong việc phân lớp câu hỏi đĩ là hướng tiếp cận dựa trên luật (rule-base approach) và hướng tiếp cận dựa trên xác suất thống kê. Hướng tiếp cận dựa trên luật: Hướng tiếp cận này yêu cầu phải cĩ các chuyên gia ngơn ngữ cung cấp các luật, các biểu thức chính quy (regural expression), các từ khĩa cho từng lớp câu hỏi … để hệ thống hoạt động. Các hạn chế của hướng tiếp cận này được chỉ ra trong [38]: o Xây dựng mơ hình cho phương pháp này rất tốn thời gian và cơng sức, cần cĩ sự cộng tác của những chuyên gia trong lĩnh vực ngơn ngữ học khi xây dựng các mẫu câu hỏi và văn phạm cho từng loại câu hỏi đĩ. o Các luật ngữ pháp viết tay và văn phạm của từng loại câu hỏi rất cứng nhắc, khơng linh động. Khi một dạng câu hỏi mới xuất hiện, mơ hình theo hướng này khơng thể xử lý. Muốn xử lý được mơ hình cần phải được cung cấp những luật mới. o Vấn đề nhập nhằng của các văn phạm ngữ pháp rất khĩ xử lý, kiểm sốt và phụ thuộc vào đặc điểm của từng ngơn ngữ. o Khi tập câu trả lời được mở rộng hoặc thay đổi kéo theo việc phải viết lại hồn tồn các luật trước đĩ nên hệ thống rất khĩ mở rộng. Một số hệ thống hỏi đáp sử dụng luật để phân lớp câu hỏi như Webclopedia [18] và [39]. Hướng tiếp cận dựa trên xác suất thống kê: Được Jonathan Brown tổng hợp lại bao gồm hai cách tiếp cận chính đĩ là Phương pháp học máy: Sử dụng một tập đủ lớn các câu hỏi đã được gán nhãn lớp để huấn luyện một mơ hình cĩ thể tự động nắm bắt được các mẫu cĩ ích trong việc phân lớp câu hỏi. Cụ thể hơn, các thuật tốn của hướng tiếp cận này sẽ tính tốn xác suất phân 25 lớp cho câu hỏi dựa trên những đặc trưng hay những mối quan hệ của các từ trong câu hỏi đưa vào. Các thuật tốn thường được sử dụng là Support Vector Machines (SVM), láng giềng gần nhất (Near Neighbors – kNN), Nạve Bayes (NB), Entropy cực đại, …Ngồi ra, các phương pháp học máy bán giám sát [36] cũng được đưa ra để sử dụng các câu hỏi chưa được gán nhãn làm tăng cường thêm độ chính xác cho phân lớp câu hỏi. Phương pháp sử dụng mơ hình ngơn ngữ: Xây dựng một mơ hình ngơn ngữ thống kê để ước lượng được phân phối của ngơn ngữ tự nhiên chính xác nhất cĩ thể. Cụ thể với bài tốn phân lớp câu hỏi là việc ước lượng xác suất cĩ điều kiện p(a|b) của “loại câu hỏi” a xuất hiện trong “ngữ cảnh” câu hỏi tự nhiên b. Bài tốn đặt ra là chúng ta phải tìm một phương pháp ước lượng (cĩ thể tin tưởng được) mơ hình xác suất cĩ điều kiện p(a|b) [4]. Hướng tiếp cận dựa trên học máy thống kê hiện đang được rất nhiều nhà nghiên cứu quan tâm vì nĩ khơng chỉ tốn ít cơng sức của con người hơn (so với phương pháp dựa trên luật) mà cịn cĩ tính khả chuyển cao, dễ dàng áp dụng cho nhiều miền ứng dụng khác nhau. Tuy nhiên hướng tiếp cận này cũng gặp khĩ khăn khi số lượng lớp câu hỏi lớn. Trong phân lớp câu hỏi, người ta muốn phân câu hỏi vào các lớp càng nhỏ càng tốt nhằm thu hẹp khơng gian tìm kiếm câu trả lời. Các hệ thống hỏi đáp hiện nay thường cĩ số lượng lớp câu hỏi lớn (hệ thống của Li và Roth [25] cĩ 50 lớp, hệ thống trong [39] cĩ 54 lớp, trong [15] cĩ 68 lớp, Webclopedia [18] cĩ 122 lớp,…), trong khi các thuật tốn học máy sẽ giảm hiệu quả nếu số lớp tăng. Vì vập cần cải tiến mơ hình và thuật tốn để phù hợp với số lượng lớp lớn trong phân lớp câu hỏi. Phần 3.1 này sẽ trình bày các nội dung về học máy thống kê và mơ hình áp dụng cho phân lớp câu hỏi. 3.1.1. Bài tốn phân lớp trong khai phá dữ liệu Phân lớp là bài tốn điển hình trong khai phá dữ liệu. Mục đích của phân lớp là để dự đốn những nhãn lớp cho các bộ dữ liệu mới. • Đầu vào: một tập các mẫu dữ liệu huấn luyện, với một nhãn phân lớp cho mỗi mẫu dữ liệu. • Đầu ra: mơ hình (bộ phân lớp) dựa trên tập huấn luyện và những nhãn phân lớp. Phân lớp là quá trình gồm hai bước: Bước 1 (học mơ hình): một mơ hình sẽ được xây dựng dựa trên việc phân tích các đối tượng dữ liệu đã được gán nhãn từ trước. Tập các mẫu dữ liệu này cịn được gọi là tập 26 dữ liệu huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện được xác định bởi con người trước khi xây dựng mơ hình, vì vậy phương pháp này cịn được gọi là học cĩ giám sát (supervised learning). Trong bước này, chúng ta cịn phải tính độ chính xác của mơ hình, mà cần phải sử dụng một tập dữ liệu kiểm tra (test data set). Nếu độ chính xác là chấp nhận được (tức là cao), mơ hình sẽ được sử dụng để xác định nhãn lớp cho các dữ liệu khác mới trong tương lai. Bước 2 (sử dụng mơ hình): sử dụng mơ hình đã được xây dựng ở bước 1 để phân lớp dữ liệu mới. Đánh giá thuật tốn phân lớp [3] Độ hồi tưởng ρ và độ chính xác π được dùng để đánh giá chất lượng của thuật tốn phân lớp. Giả sử các tài liệu thuộc vào hai lớp và thuật tốn cần học một lớp trong hai lớp đĩ, khi đĩ các giá trị TP (true positives), TN (true negatives), FP (false positives), FN (false negatives) được xem xét: - TP: số lượng ví dụ dương (tài liệu thực sự thuộc lớp cần đốn nhận) được thuật tốn phân lớp cho giá trị đúng. - TN: số lượng ví dụ âm (tài liệu thực sự khơng thuộc lớp cần đốn nhận) những được thuật tốn phân lớp cho giá trị đúng. - FP: số lượng ví dụ dương được thuật tốn phân lớp cho giá trị sai. - FN: số lượng ví dụ âm được thuật tốn phân lớp cho giá trị sai. Đánh giá phân lớp đa lớp (thơng qua dữ liệu test Dtest) Bài tốn ban đầu: C gồm cĩ k lớp Đối với mỗi lớp Ci , cho thực hiện thuật tốn với các dữ liệu thuộc Dtest nhận được các đại lượng TPi, TFi, FPi, FNi (như bảng 2). 27 Bảng 2. Biểu diễn của TP, TN, FP, FN trong đánh giá phân lớp Giá trị thực Lớp Ci Thuộc lớp Ci Khơng thuộc lớp Ci Thuộc lớp Ci TPi TNi Giá trị qua bộ phân lớp đa lớp Khơng thuộc lớp Ci FPi FNi Khi đĩ, FPTP TP +=ρ và FNTP TP +=π Trong trường hợp phân lớp K lớp, các độ đo cực tiểu trung bình (microaveraging) và cực đại trung bình (macroaveraging) được sử dụng: )(1 1 ∑ ∑ = = += K c cc K c c FPTP TPµρ (microaveraging recall) )( )( 1 1 ∑ ∑ = = + += K c cc K c cc FNTP FPTPµπ (microaveraging precision) và ∑ = = K c c M K 1 1 ππ (macroaveraging recall) ∑ = = K c c M K 1 1 ρρ (macroaveraging precision) Các độ đo cực tiểu trung bình được đánh coi là các độ đo tốt để đánh giá chất lượng thuật tốn phân lớp tài liệu. 28 3.1.2. Các thuật tốn học máy thống kê cho việc phân lớp Cĩ nhiều thuật tốn khác nhau cho phân lớp như Nạve Bayes, K láng giềng gần nhất, cây quyết định (Decision Tree), Máy Vector hỗ trợ (Support Vector Machine), Mạng lọc thưa (Sparse Network of Winnows -SNoW), Mơ hình Entropy cực đại … Tuy nhiên phần tiếp theo của khĩa luận chỉ trình bày về máy Vector hỗ trợ và mơ hình Entropy cực đại - hai thuật tốn được sử dụng nhiều trong phân lớp câu hỏi và cũng sẽ được sử dụng trong phần thực nghiệm ở chương 4. 3.1.2.1. Máy Vector hỗ trợ - SVM a. Thuật tốn Theo [2], thuật tốn Support Vector Machines (máy vector hỗ trợ) được Corters và Vapnik giới thiệu vào năm 1995. SVM rất hiệu quả để giải quyết các bài tốn với dữ liệu cĩ số chiều lớn như các vector biểu diễn văn bản. Thuật tốn SVM ban đầu được thiết kế để giải quyết bài tốn phân lớp nhị phân (hai lớp). Cho tập dữ liệu học D ={(xi, yi), i = 1,…, n} với xi ∈ Rm và yi∈{-1,+1} là một số nguyên xác định xi là dữ liệu dương (+1) hay âm (-1). Một tài liệu xi được gọi là dữ liệu dương nếu nĩ thuộc lớp ci ; xi được gọi là dữ liệu âm nếu nĩ khơng thuộc lớp ci . Bộ phân lớp tuyến tính được xác định bằng siêu phẳng: {x : f(x) = wTx + w0 =0 } Trong đĩ w∈ Rm và w0∈R là các hệ số cĩ thể điều chỉnh đĩng vai trị là tham số của mơ hình. Hàm phân lớp nhị phân h: Rm → {0,1}, cĩ thể thu được bằng cách xác định dấu của f(x): { 0 (x) 1 0 (x) 0 >≤= f f h Như vậy việc học mơ hình phân lớp chính là việc xác định w và w0 từ dữ liệu. Với thuật tốn này, mỗi dữ liệu được xem là một điểm trong mặt phẳng. Dữ liệu học là tách rời tuyến tính (linearly separable) nếu tồn tại một siêu phẳng sao cho hàm phân lớp phù hợp với tất cả các nhãn, tức là yif(xi)>0 với mọi i = 1,...,n. Với giả thuyết này, Rosenblatt đã đưa ra một thuật tốn lặp đơn giản để xác định siêu phẳng: 29 Perceptron(D) Cĩ thể thấy rằng điều kiện đủ để tập ví dụ D tách rời tuyến tính là số dữ liệu học n = |D| nhỏ hơn hoặc bằng m+1. Điều này là thường đúng với bài tốn phân lớp văn bản, bởi vì số lượng từ mục cĩ thể lên tới hàng nghìn và lớn hơn nhiều lần so với số lượng dữ liệu học. Tuy nhiên thuật tốn Perceptron trên lại gặp vấn đề đĩ là overfitting1. Hình 4 đưa ra một ví dụ về overfitting. Giả sử rằng các dữ liệu mẫu thuộc lớp âm và lớp dương đều tuân theo luật phân bố chuẩn Gaussian, và được tạo ra với cùng một xác suất. Khi đĩ một siêu phẳng phân cách được gọi là lý tưởng nếu nĩ làm cực tiểu xác suất phân lớp sai cho một điểm dữ liệu mới. Với giả thuyết ở trên thì siêu phẳng phân cách lý tưởng sẽ trực giao với đoạn thẳng nối tâm của hai vùng cĩ mật độ xác suất lớn nhất. Rõ ràng các siêu phẳng được xây dựng nhằm phân cách các điểm dữ liệu mẫu theo thuật tốn Perceptron cĩ thể lệch đi rất nhiều so với siêu phẳng lý tưởng, do đĩ sẽ dẫn tới việc phân lớp khơng tốt trên dữ liệu mới sau này. Độ phức tạp của quá trình xác định siêu phẳng lý tưởng sẽ tăng theo số chiều của khơng gian dữ liệu đầu vào m, vì với một số lượng n các dữ liệu mẫu cố định, tập hợp các siêu phẳng sẽ tăng theo hàm mũ với lũy thừa m. Với bài tốn phân lớp trang văn bản, m thường rất lớn, khoảng vài ngàn hay thậm chí là hàng triệu từ. 1 Overfitting: 30 Hình 4. Mối quan hệ giữa các siêu phẳng phân cách Theo lý thuyết học thống kê được phát triển bởi Vapnik năm 1998 chỉ ra rằng cĩ thể xác định một siêu phẳng tối ưu thỏa mãn hai tính chất quan trọng (1) nĩ là duy nhất với mỗi tập dữ liệu học tách rời tuyến tính; (2) khả năng overfitting là nhỏ hơn so với các siêu phẳng khác. Định nghĩa biên M của bộ phân lớp là khoảng cách giữa các siêu phẳng và các dữ liệu học gần nhất. Siêu phẳng tối ưu nhất là siêu phẳng cĩ biên lớn nhất, điều đĩ cĩ nghĩa là chúng ta cần tìm siêu phẳng sao cho khoảng cách từ siêu phẳng đến những điểm gần nhất là lớn nhất (Hình 5). Vapnik cũng chứng minh rằng khả năng overfitting với siêu phẳng tối ưu nhỏ hơn so với các siêu phẳng khác. 31 Hình 5. Siêu phẳng tối ưu và biên. Khoảng cách từ một điểm x đến siêu phẳng là: Vì vậy siêu phẳng tối ưu cĩ thể thu được bằng ràng buộc tối ưu sau: 0w,w max M sao cho Ti i 0 1 y (w x w ) M,i 1,...n || w || + ≥ = Trong đĩ ràng buộc yêu cầu mọi tài liệu học (tương đương với các điểm) phải nằm trên nửa mặt phẳng của nĩ và khoảng cách tới siêu phẳng lớn hơn hoặc bằng M. Đặt 1w M= biểu thức trên được viết lại như sau 0w,w min W sao cho Ti i 0y (w x w ) M,i 1,...,n+ ≥ = Đưa về phương trình Lagrangian: ( )n2 Ti i 0 i 1 1L(D) || w || y w w 1 2 = ⎡ ⎤= − + α + −⎣ ⎦∑ 0|||| 1 wxw w T + 32 Sau đĩ tính đạo hàm của phương trình trên theo w,w0 ta được n T i i 1 1max 2α = − α Λα + α∑ thỏa mãn i 0,i 1,...,nα ≥ = Với Λ là ma trận n×n trong đĩ iα = yiyj jTi xx . Đây là bài tốn bậc hai, theo lý thuyết cĩ thể giải được bằng phương pháp chuẩn tối ưu. Với mỗi dữ liệu học i, cách giải phải thỏa mãn điều kiện: iα ( )[ ]1wwy 0Ti −+ =0 Và do đĩ hoặc iα = 0 hoặc )wxw(y 0iTi + =1. Nĩi cách khác, nếu iα >0 thì khoảng cách từ điểm xi đến mặt phẳng phân cách là M . Các điểm thỏa mãn iα >0 được gọi là các vector hỗ trợ. Hàm quyết định h(x) cĩ thể được tính qua cơng thức dấu của f(x) hoặc tương đương với dạng sau: i T i n 1i i xxxy(x) ∑ = =f Những kết quả trong phần trên chỉ áp dụng cho trường hợp các tập cĩ thể phân chia tuyến tính. Với các tập khơng thể phân chia tuyến tính, người ta đưa ra giải pháp “lề mềm” (soft margin) [5] . Hàm tối ưu trong trường hợp này là: ∑ = + n 1i C||w||min iww, ξ0 thỏa mãn ( )+ ≥ − = ≥ = ⎧⎪⎨⎪⎩ T i i 0 i i y w x w 1 ξ ,i 1,...,n ξ 0, i 1,...,n Ở đây, iξ gọi là biến nới lỏng (slack variables), hay các biến dương thể hiện mức độ chịu lỗi của bộ phân lớp (tolerances of misclassification). Thơng qua đĩ, các vector huấn luyện được phép rơi vào trong khoảng chịu lỗi dọc theo biên ngăn cách hai lớp như được mơ tả trong hình 6. 33 Hình 6. Biến nới lỏng cho soft margin Vấn đề này cĩ thể đưa về dạng: 1 1max 2 n T i iα α α α = − Λ +∑ thỏa mãn Cα0 i ≤≤ i=1,…,n Bộ phân lớp theo cách này được gọi là bộ phân lớp máy vector hỗ trợ – Support Vector Machine. Nếu dữ liệu học là khơng tách rời tuyến tính, độ chính xác của bộ phân lớp SVM sẽ rất thấp, ngay cả với siêu phẳng tuyến tính tốt nhất. Phương pháp trình bày ở trên cĩ thể mở rộng để phù hợp với dữ liệu khơng tách rời tuyến tính bằng cách sử dụng hàm nhân để ánh xạ mỗi điểm x ∈ Rm vào một khơng gian cĩ số chiều lớn hơn (cĩ thể là vơ hạn chiều) gọi là khơng gian đặc trưng mà ở trong khơng gian này dữ liệu là tách rời tuyến tính Phân lớp đa lớp với SVM Bài tốn phân lớp câu hỏi yêu cầu một bộ phân lớp đa lớp do đĩ cần cải tiến SVM cơ bản (phân lớp nhị phân) thành bộ phân lớp đa lớp. Một trong những phương pháp cải tiến đĩ là sử dụng thuật tốn 1-against-all [40]. Ý tưởng cơ bản là chuyển bài tốn phân lớp nhiều lớp thành nhiều bài tốn phân lớp nhị phân như sau: 34 - Giả sử tập dữ liệu mẫu (x1,y1), … ,(xm,ym) với xi là một vector n chiều và yi ∈Y là nhãn lớp được gán cho vector xi (cĩ m nhãn lớp khác nhau). - Biến đổi tập Y ban đầu thành m tập cĩ hai lớp con cĩ cấu trúc như sau. Zi ={yi , \ iY y } . - Áp dụng SVM phân lớp nhị phân cơ bản với m tập Zi để xây dựng siêu phẳng cho phân lớp này. - Bộ phân lớp với sự kết hợp của m bộ phân lớp trên được gọi là bộ phân lớp đa lớp mở rộng với SVM. 3.1.2.2. MEM Theo [4], đối với bài tốn phân lớp dữ liệu, Entropy cực đại là một kỹ thuật dùng để ước lượng xác suất các phân phối từ dữ liệu. Tư tưởng chủ đạo của nguyên lý Entropy cực đại là “mơ hình phân phối đối với mỗi tập dữ liệu và tập các ràng buộc đi cùng phải đạt được độ cân bằng đều nhất cĩ thể ” – (cĩ Entropy cực đại). Tập dữ liệu được học (đã được gán nhãn) được sử dụng để tìm ra các ràng buộc cho mơ hình - là cơ sở để ước lượng phân phối cho từng lớp cụ thể. Những ràng buộc này được thể hiện bởi các giá trị ước lượng được của các đặc trưng. Từ các ràng buộc sinh ra bởi tập dữ liệu này, mơ hình sẽ tiến hành tính tốn để cĩ được một phân phối với Entropy cực đại. Ví dụ về mơ hình Entropy cực đại: “Giả sử với bộ phân lớp bài báo của báo điện từ Vnexpress. Bốn lớp chính chỉ ra đĩ là pháp_luật, thể_thao, quốc_tế, văn_hĩa. Các thống kê trên tập dữ liệu mẫu chỉ ra rằng trung bình 70% các tài liệu trong lớp thể_thao cĩ chứa từ bĩng_đá. Như vậy một cách trực quan cĩ thể thấy rằng nếu một tài liệu D cĩ chứa từ bĩng_đá thì xác suất được phân vào lớp thể_thao là 70% và xác suất phân vào ba lớp cịn lại 10% ( bằng nhau giữa các lớp) và nếu D khơng chứa từ thể_thao thì xác suất phân phối của D là đều cho bốn lớp (mỗi lớp 25%).” Trong ví dụ trên “tài liệu chứa cụm bĩng_đá thì cĩ xác suất phân vào lớp thể_thao là 70%” là một ràng buộc của mơ hình. 35 a. Các ràng buộc và đặc trưng Đối với nguyên lý Entropy cực đại, các ràng buộc cho phân phối điều kiện sẽ được thiết lập dựa trên tập dữ liệu mẫu. Mỗi một ràng buộc biểu thị một đặc điểm của tập dữ liệu học. Một đặc trưng trong mơ hình Entropy cực đại được biểu hiện bởi một hàm fi(D;C). Nguyên lý cực đại Entropy cho phép chúng ta thu hẹp mơ hình phân phối để thu được giá trị kỳ vọng cân bằng cho từng đặc trưng của dữ liệu. Xác suất phân phối của dữ liệu D cho lớp C thỏa mãn phương trình sau: ( )( ) ( ) ( ) ( ) (*) cd,fd|cPdPdcd,f |D| 1 i cdDd i ∑∑∑ = ∈ Trong phương trình (*) D là tập dữ liệu và C là một lớp câu hỏi. Ở một khía cạnh khác, fi(D;C) cĩ thể được hiểu như: Nếu C là tập các lớp cĩ thể mà chúng ta muốn phân lớp và D là tập các ngữ cảnh ( ràng buộc) cĩ thể mà chúng ta quan sát được, thì mệnh đề biểu diễn thơng tin ngữ cảnh là một hàm cĩ dạng như sau: {0,1}DC :f →× Và được mơ tả như sau: 1 khi c=c′ và cp(d) = true 0 trong trường hợp cịn lại Trong đĩ cp(d) là một hàm cĩ dạng: cp: d→ {true, false} Hàm này trả về giá trị true hoặc false, phụ thuộc vào sự xuất hiện hoặc khơng xuất hiện của các thơng tin hữu ích trong một số ngữ cảnh d trong D. Ví dụ: - c' là lớp “thể_thao”, d là văn bản hiện tại. - cp = [ câu hiện tại chứa cụm từ “bĩng_đá” ]. thì hàm đặc điểm này sẽ trả về giá trị 1 nếu như lớp dự đốn a là “thể_thao” và mang giá trị 0 trong các trường hợp cịn lại. Bước đầu tiên khi sử dụng cự đại Entropy là phải xác định được tập hàm đặc trưng cho bộ phân lớp, sau đĩ đánh giá giá trị kỳ vọng của đặc trưng ấy trên tập dữ liệu học để biến hàm đặc trưng này thành một ràng buộc của phân lớp. fcp,c′ (c,d) = 36 b. Mơ hình Entropy cực đại Mơ hình xác suất Entropy cực đại cung cấp một cách đơn giản để kết hợp các đặc trưng của dữ liệu trong những ngữ cảnh khác nhau để ước lượng xác suất của một số lớp xuất hiện cùng với một số ngữ cảnh này. Trước tiên chúng ta sẽ mơ tả cách biểu diễn đặc trưng này và kết hợp nĩ vào một dạng riêng của mơ hình xác suất dưới các hình mẫu. Tư tưởng chủ đạo của phương pháp Entropy cực đại là tìm được một mơ hình cĩ phân phối xác suất thỏa mãn mọi ràng buộc quan sát được từ dữ liệu mà khơng đưa thêm bất kì một giả thiết nào khác. Theo nguyên lý Entropy cực đại, phân phối cần đáp ứng dữ liệu quan sát và làm cực đại độ đo Entropy cĩ điều kiện: ( ) ( ) ( ) ( ) , | log |≡ −∑ % c d H p p c p c d p d c ( )* argmax ∈ = p C p H p (p * là phân phối xác suất tối ưu) Mơ hình Entropy cực đại xây dựng các đặc trưng từ tập dữ liệu huấn luyện. Mỗi đặc trưng nhận hàm hai của câu hỏi và lớp, hàm này nhận một trong hai giá trị đúng hoặc sai. Tập các ràng buộc sẽ được thiết lập từ các đặc trưng này. Một ràng buộc là một điều kiện từ dữ liệu buộc mơ hình phải thỏa mãn. Mỗi đặc trưng fi được gán một trọng số iλ . Khi đĩ, bài tốn phân lớp đưa về bài tốn ước lượng xác suất cĩ điều kiện: ( ) ( )i i i 1P c | d exp f d,c Z(d) ⎛ ⎞= λ⎜ ⎟⎝ ⎠∑ trong đĩ Z(d) là biểu thức chuẩn hĩa để bảm bảo điều kiện ( ) 1d|cp =∑ , cĩ cơng thức như sau: Khi các đặc trưng được ước lượng từ tập dữ liệu mẫu, thì giải pháp cho mơ hình Entropy cực đại giống với giải pháp với bài tốn cực đại hĩa likelihood trên mơ hình mũ sau: ( ) ( )∑ ∑ ⎟⎠⎞⎜⎝⎛ λ= c ii i c,dfexpdZ 37 ( ) ( )∏ = = k 1i dc,f i iλ Z(d) 1d|cP ( )∑∏ = = c k 1i dc,f i iλZ(d) ( ) ( ) ( )~ c,d L P p c,d logp c|d=∑ Tức là p* arg max L(p) arg max H(p)= = . c. Thuật tốn uớc lượng tham số Ước lượng tập tham số { }1 n, ...,λ = λ λ để huấn luyện mơ hình Entropy đạt được cực đại. Trên thế giới hiện nay cĩ nhiều phương pháp để ước lượng tập tham số này như: thuật tốn GIS – Generalized Iterative Scaling, thuật tốn IIS – Improved Iterative Scaling là thuật tốn ước lượng tham số của mơ hình mũ do các thành viên trong nhĩm nghiên cứu tại IBM’s T. J. Watson Research Center đưa ra vào những năm đầu của thập kỉ 1990, thuật tốn L-BFGS – Limited memory BFGS – là phương pháp giới hạn bộ nhớ cho phương pháp quasi-Newton cho phép tối ưu hàng triệu tham số với tốc độ rất nhanh. 3.1.3. Xây dựng bộ phân lớp câu hỏi theo học máy thống kê Bài tốn phân lớp câu hỏi cũng cĩ thể coi là bài tốn phân lớp văn bản, trong đĩ mỗi câu hỏi được xem là một văn bản. Tuy nhiên phân lớp câu hỏi cĩ một số đặc trưng riêng so với phân lớp văn bản: - Số lượng từ trong một câu hỏi ít hơn nhiều trong một văn bản, do đĩ dữ liệu câu hỏi là rất rời rạc. Việc biểu diễn câu hỏi theo tần suất từ (TF, IDF) hầu như khơng tăng hiệu quả phân lớp vì các từ thường chỉ xuất hiện một lần trong câu hỏi. - Các từ dừng trong phân lớp văn bản là quan trọng với phân lớp câu hỏi. - Số lượng nhãn lớp thường rất lớn. Đối với các thuật tốn phân lớp, khi số lượng lớp tăng thì hiệu quả sẽ giảm [36]. Nhiều hệ thống Q&A đã áp dụng phân lớp đa cấp nhằm giảm số lượng lớp tại mỗi bộ phân lớp ở từng cấp. 38 3.1.3.1. Mơ hình phân lớp câu hỏi Phân lớp câu hỏi sử dụng học máy thống kê hiện đang nhận được sự chú ý của nhiều nhà nghiên cứu [20,25,36,41]. Li và Roth [25] xây dựng một bộ phân lớp câu hỏi phân cấp dựa trên một taxonomy câu hỏi 2 cấp thể hiện sự phân lớp ngữ nghĩa tự nhiên của câu trả lời. Cấu trúc phân cấp bao gồm 6 lớp câu hỏi thơ (coarse class) là 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ố). Mỗi lớp câu hỏi thơ lại được phân chia thành các lớp con (fine class). Taxonomy câu hỏi của Li và Roth được trình bày chi tiết trong bảng 1 (Mục 2.4). Theo Li và Roth thì phân lớp câu hỏi cĩ tính nhập nhằng, tức là một câu hỏi cĩ thể được phân vào nhiều lớp do khơng cĩ một ranh giới rõ ràng nào giữa các lớp. Ví dụ câu hỏi “Sử tử ăn gì ?” cĩ thể được phân vào lớp food (thức ăn), animal (động vật) hay câu hỏi “Đại học Cơng Nghệ ở đâu ?” cĩ thể được phân vào lớp country (đất nước), state (tỉnh)… Vì vậy bộ phân lớp thơ sẽ cho đầu ra là một số nhãn lớp thơ (phân lớp đa nhãn). Câu hỏi lần lượt được cho qua hai bộ phân lớp Coarse_Classifier và Fine_Classifier. Theo hình 7, câu hỏi ban đầu được phân lớp bởi bộ phân lớp thơ Coarse_Classifier cho ra một tập các lớp thơ. C1 = Coarse_Classifier(C) = { c1,c2,…cn} với |C1| <= 5, |C| = 6, C = {abbreviation, entity, description, human, location, numeric value} Sau đĩ các nhãn của lớp thơ c1,..cn được mở rộng bởi các nhãn lớp con tương ứng. Cụ thể hơn, mỗi nhãn thơ ci được ánh xạ vào một tập nhãn lớp con theo taxonomy phân cấp, Fci = { fi1,fi2,….fim} và được tổng hợp lại thành C2 = U Fci. Bộ phân lớp tinh Fine_Classifier sẽ xác định tập các nhãn lớp con C3 = Fine_Classifier(C2) với |C3| <=5. Kết quả đầu ra là hợp của C1 và C3 được sử dụng cho quá trình tìm câu trả lời. 39 Hình 7. Mơ hình bộ phân lớp đa cấp của Li và Roth Kết quả mà Li và Roth đạt được khá tốt, độ chính xác là 84.2% cho 50 lớp con và 91% cho 6 lớp cha với thuật tốn SnoW. Sử dụng taxonomy câu hỏi của Li và Roth, tiến sĩ Nguyễn Trí Thành [36] đã áp dụng học bán giám sát để tận dụng dữ liệu câu hỏi chưa gán nhãn nhằm tăng độ chính xác cho phân lớp câu hỏi và đề xuất hai cách thay đổi thuật tốn Tri-training để phù hợp với dữ liệu câu hỏi. 3.1.3.2. Trích chọn đặc trưng cho phân lớp câu hỏi Trích chọn đặc trưng cĩ ý nghĩa quan trọng, ảnh hưởng trực tiếp đến kết quả phân lớp. Các loại đặc trưng chính thường được sử dụng là tập từ (bag-of-word) và tập các cặp từ/nhãn từ loại (bag-of-word/POS tag). Việc phân loại câu hỏi cĩ điểm khác với phân loại văn bản đĩ là câu hỏi chỉ chứa một số ít từ trong khi văn bản cĩ số lượng từ rất lớn. Trọng số từ (TF – term frequency) gĩp phần quan trọng trong nâng cao độ chính xác của phân lớp văn bản, trong khi với câu hỏi các từ hầu như chỉ xuất hiện một lần duy nhất, do đĩ việc biểu diễn câu hỏi theo trọng số từ khơng cĩ ý nghĩa mấy trong phân lớp câu hỏi. Trong phân lớp văn bản các từ như “nào”, “gì”, “sao” thường được coi là từ dừng (stop word) và bị loại bỏ ở bước trích chọn đặc trưng. Việc này là rất quan trọng trong nâng cao hiệu quả của bộ phân lớp và đã được chứng minh trong [21]. Tuy nhiên những từ này lại cĩ ý nghĩa rất quan trọng trong phân lớp câu hỏi. Để cĩ thể giữ lại các từ này 40 mà vẫn giảm được số chiều của khơng gian biểu diễn dữ liệu, trong tiếng Anh kĩ thuật stemming thường được áp dụng. Ví dụ trong tiếng Anh, các động từ được chuyển về dạng nguyên thể (“was”, “were”, “is”, “are”, “am” được chuyển hết thành “be”), các danh từ số nhiều chuyển về dạng danh từ số ít (“children” thành “child”, “girls” thành “girl” …), các số từ đều được chuyển về cùng một giá trị (“2004”, “1.5”, “5” đều chuyển thành “100”) [36]. Ví dụ: “Thủ tướng Việt Nam năm 2007 là ai” Được chuyển thành: “Thủ tướng Việt Nam năm 100 là ai” Sau bước tiền xử lý này, một tập V các từ khác nhau xuất hiện trong tập câu hỏi ví dụ sẽ được trích ra (gọi là từ điển – dictionary). Gọi N là kích thước của từ điển, N chính là số chiều của khơng gian biểu diễn câu hỏi. Các câu hỏi sẽ được biểu diễn dưới dạng vector gồm N thành phần: qi= (w1,w2,…..,wN) trong đĩ wi = 1 nếu từ thứ i trong từ điển xuất hiện trong câu hỏi qi. 0 nếu từ thứ i trong từ điển khơng xuất hiện trong câu hỏi qi Các vector này là đầu vào cho bộ phân lớp. Với loại đặc trưng là tập các cặp từ/nhãn từ loại thì tập từ điển V sẽ khác một chút. Các cặp từ/nhãn từ loại là thành phần của từ điển. Một từ cĩ thể cĩ nhiều chức năng ngữ pháp, cĩ lúc đĩng vai trị là danh từ, cĩ lúc lại là động từ (ví dụ từ “đá”, “bị” …). Những từ này sẽ được chuyển thành “đá”- danh từ và “đá”-động từ và được tính là hai thành phần khác nhau của từ điển. Việc biểu diễn đặc trưng dưới dạng từ/nhãn từ loại sẽ giúp phân biệt được các từ này theo các nghĩa khác nhau. Trong tiếng Anh việc biểu diễn câu hỏi dưới dạng bag-of-word là khá đơn giản bởi đặc trưng của tiếng Anh là các từ phân cách nhau bởi khoảng trắng. Do đĩ việc sử dụng unigram cũng chính là bag-of-word. Trong khi với tiếng Việt, một từ cĩ thể được ghép lại từ nhiều âm tiết, do đĩ khơng thể dùng khoảng trắng làm ranh giới phân cách các từ. Cần thiết phải cĩ một cơng cụ tách từ hiệu quả cho tiếng Việt [37] . 41 Việc biểu diễn câu hỏi theo bag-of-word và bag-of-word/POS tag khơng giữ được các thơng tin về trật tự từ trong câu, do đĩ người ta sử dụng n-gram làm đặc trưng. Bag- of-ngrams là một kỹ thuật biểu diễn văn bản độc lập với ngơn ngữ. Nĩ chuyển đổi các văn bản/câu hỏi thành các vectơ đặc trưng đa chiều với mỗi đặc trưng tương đương với một chuỗi con liền kề nhau. Để nâng cao độ chính xác của bộ phân lớp, các đặc trưng ngữ nghĩa khác được xem xét. Li và Roth đã xây dựng bộ phân lớp câu hỏi sử dụng thuật tốn Sparse Network of Winnows – SnoW với các đặc trưng được sử dụng là: từ vựng (bag-of-word), nhãn từ loại (POS tag), cụm từ (các cụm khơng giao nhau - non-overlapping), cụm danh từ đầu tiên trong câu hỏi (head chunks) và tên thực thể (named entity). Bộ dữ liệu học bao gồm 5500 câu hỏi được thu thập từ các nguồn: 4.500 câu hỏi tiếng Anh cơng bố bởi USC1, 500 câu hỏi tự tạo cho một số lớp cĩ ít câu hỏi, 894 câu hỏi thu thập từ tập câu hỏi của TREC 8 và TREC 9 và 500 câu hỏi của TREC 10 cho dữ liệu kiểm tra. Độ chính xác mơ hình đạt được là 78,8% với 50 lớp con (phân lớp đa cấp với 6 lớp cha và 50 lớp con). Khi sử dụng danh sách các từ (được xây dựng bằng tay) liên quan đến một lớp câu hỏi thì độ chính xác đạt 84.2 %. Mỗi lớp câu hỏi cĩ một danh sách các từ liên quan, là các từ thường xuyên xuất hiện trong lớp câu hỏi đĩ. Ví dụ lớp câu hỏi về nguyên nhân cĩ danh sách các từ {“nguyên nhân” , “lí do”, “tại sao”, “vì sao”…}. Bộ dữ liệu do Li và Roth sử dụng đã được cơng bố và được nhiều nhĩm nghiên cứu sử dụng để so sánh kết quả khi thực nghiệm với các thuật tốn hoặc các đặc trưng mới để nâng cao kết quả đạt được của phân lớp câu hỏi. Hacioglu và Ward [14] sử dụng máy hỗ trợ vector (support vector machines - SVM) với đặc trưng là bigram và mã sửa lỗi đầu ra (error-correcting output code-ECOC ) đã đạt kết quả 80.2% và 82.0%. Zhang và Lee [41] sử dụng SVMs tuyến tính với đặc trưng là bag-of-word và bag-of-ngram đạt độ chính xác 79.2%. Năm 2006, Li và Roth đã sử dụng thêm các đặc trưng ngữ nghĩa gồm: tên thực thể, nghĩa của từ trong WordNet, danh sách từ liên quan đến lớp câu hỏi (xây dựng bằng tay), các từ cĩ độ tương đồng về mặt ngữ nghĩa (sinh tự động). Việc kết hợp các đặc trưng về ngữ nghĩa này với các đặc trưng về ngữ pháp (POS tag, cụm từ ..) họ đã đạt được độ chính xác 89.3% cho 50 lớp con khi huấn luyện mơ hình với 21.500 câu hỏi và kiểm thử với 1000 câu hỏi. Krishnan [24] sử dụng các chuỗi ngắn của câu hỏi (một đến 3 từ) làm 1 42 đặc trưng và đạt được độ chính xác 86.2% cho 50 lớp con khi tiến hành huấn luyện trên bộ dữ liệu 5500 câu hỏi do UIUC cơng bố và được ghi nhận là kết quả tốt nhất trên tập dữ liệu này. Theo Krishnan thì chỉ cần dựa vào một chuỗi ngắn các từ liên tục trong câu hỏi (gọi là informer span) đã cĩ thể nhận diện được câu hỏi thuộc lớp nào. Vì vậy họ đã sử dụng Conditional Random Field (CRF) để xác định informer span với độ chính xác 85%, sau đĩ xây dựng bộ phân lớp meta-classifier sử dụng SVM tuyến tính trên kết quả đầu ra của CRF. Hình thức của từ cũng được coi là một loại đặc trưng hữu ích. Đặc trưng hình thức từ bao gồm 5 đặc trưng: Viết hoa tất cả các kí tự trong từ, viết thường tất cả, dạng hỗn hợp (cĩ cả chữ thường lẫn chữ viết hoa), tất cả các kí tự là chữ số (0-9) và các hình thức khác. Các đặc trưng này rất cĩ ích, ví dụ nếu tất cả các kí tự của từ viết hoa thì thường thường đĩ là tên thực thể, hoặc một dạng viết tắt .., nếu tất cả các kí tự của từ là chữ số thì rất cĩ thể đĩ là con số, ngày tháng, mã số, điện thoại ….Các đặc trưng hình thức từ này gĩp phần làm tăng độ chính xác của phân lớp [20]. 3.2. Phương pháp xác định loại câu hỏi sử dụng kĩ thuật xử lý ngơn ngữ tự nhiên Bài báo [15] đã đưa ra một phương pháp tích hợp nhiều kĩ thuật trong xử lý ngơn ngữ tự nhiên dựa trên tri thức vào hệ thống hỏi đáp tự động và thu được kết quả rất tốt. Phương pháp xác định loại câu hỏi được tiến hành như sau (xem minh họa trong Hình 8): - Câu hỏi được phân tích ngữ pháp và biểu diễn dưới dạng cây cú pháp. - Các nút lá của cây được gán nhãn là các từ tương ứng và được chia làm hai loại: non-skip và skip. Các lá non-skip là lá mà nhãn là danh từ, động từ, tính từ, trạng từ. Các lá cịn lại thuộc loại skip. 43 Hình 8. Xác định loại câu hỏi sử dụng kĩ thuật xử lý ngơn ngữ tự nhiên - Duyệt cây theo thứ tự bottom-up, gán nhãn cho các nút cha theo nhãn của các nút con nonskip dựa theo các luật xác định. Một luật căn cứ vào nhãn ngữ pháp của nút cha để chọn ra một nút con thích hợp và lan truyền nhãn của nút con này lên mức kế tiếp của cây. Nút con được chọn được coi là nút cĩ mối liên hệ với các nút anh em nonskip khác. Quá trình lan truyền được thực hiện cho đến khi gốc của cây cú pháp được gán nhãn. Một đồ thị ngữ nghĩa cũng được tạo ra trong khi quá trình lan truyền nhãn và từ cĩ số lượng mối liên hệ nhiều nhất với các từ khác được xem là từ trọng tâm (focus word). - Để xác định loại câu hỏi, người ta sử dụng một cây phân cấp các loại câu hỏi dựa trên Wordnet. Loại câu hỏi là các nút cha (hypermym) của từ trọng tâm trong WordNet. 44 Hình 9. Ánh xạ từ trọng tâm vào Wordnet Trong ví dụ ở hình 9, từ researcher là từ trọng tâm, được ánh xạ vào tập subset về scientist, cĩ hypermym là PERSON. Vì vậy câu hỏi này được xác định là câu hỏi về người. Ưu điểm: - Rất mạnh mẽ, cĩ thể xử lý được nhiều loại câu hỏi khác nhau. Dễ dàng mở rộng các lớp do chỉ cần thêm các nhãn lớp vào trong tập synset của WordNet. Nhược điểm: -Việc ánh xạ từ loại câu hỏi vào các tập từ của WordNet phải làm hồn tồn bằng tay. - Khơng cĩ cơ chế khử nhập nhằng ngữ nghĩa của từ, nếu từ trọng tâm cĩ nhiều nghĩa trong WordNet thì sẽ chọn tập synset nào đại diện cho loại câu hỏi ? - Chưa xử lý với trường hợp từ trọng tâm khơng cĩ trong WordNet. - Phải cần tới các cơng cụ xử lý và các nguồn tài nguyên ngơn ngữ. researcher oceanographe chemist Scientist, man of science America islander, island- westerner inhabitant, dweller, denizen actor actress dancer performer, performing artist ballet dancer tragedian ERSONP What researcher discovered Hepatitis-B vaccine What researcher discovered the vaccine against Hepatitis-B? What is the name of the French oceanographer who owned Calypso? PERSO What oceanographer ownedCalypso name French PERSO 45 3.3. Phương pháp xác định loại câu hỏi sử dụng mẫu quan hệ Một phương pháp khác hay được sử dụng để xác định loại câu hỏi là dựa trên tập mẫu. Yếu tố quyết định hiệu quả của phương pháp này là cần cĩ một tập mẫu tốt, cĩ khả năng bao quát được các trường hợp đa dạng của câu hỏi. Ý tưởng chính của hướng tiếp cận này là “ Trong nhiều trường hợp, câu trả lời và câu hỏi thường cĩ sự tương đồng khá lớn, nhiều khi câu trả lời là sự sắp xếp lại các từ khĩa trong câu hỏi”. Ví dụ như câu hỏi “ X là gì” thì câu trả lời thường cĩ dạng “X là Y”. Một thơng tin trong ngơn ngữ tự nhiên cĩ thể được diễn đạt theo nhiều cách khác nhau. Vì vậy nếu chúng ta cĩ thể sử dụng nguồn dữ liệu phong phú, đa dạng, dư thừa và nhiều trùng lặp trên Web để học ra các mẫu trả lời của một loại câu hỏi thì khả năng tập mẫu này bao phủ được các trường hợp của câu hỏi là cao. Khĩ khăn của phương pháp này là cần cĩ một cơ chế đánh giá độ tin cậy của các mẫu sinh ra một cách hợp lý, tuy nhiên việc cài đặt là khá dễ dàng và chỉ tốn ít cơng sức làm dữ liệu mồi cho quá trình học boostraping. Phương pháp Snowball [7] là một phương pháp học boostraping dựa trên ý tưởng của phương pháp DIPRE [11] dùng để trích ra các mẫu quan hệ và tập dữ liệu cho một quan hệ từ một tập hạt giống nhỏ ban đầu. Bài tốn mà Snowball giải quết được phát biểu ngắn gọn như sau: Cho một mối quan hệ (ví dụ - “tổ chức A cĩ trụ sở tại địa điểm B” ) và một số thể hiện của quan hệ đĩ, gọi là tập hạt giống – seed. Ví dụ: Nhiệm vụ đặt ra là: Tìm các mẫu quan hệ biểu diễn mỗi quan hệ này, sau đĩ sử dụng các mẫu này để tự động tìm ra các thể hiện khác của quan hệ. Kết quả là một cơ sở dữ liệu lớn các thể hiện của quan hệ được sinh ra từ tập hạt giống nhỏ ban đầu. MICROSOFT REDMOND IBM ARMONK BOEING SEATTLE INTEL SANTA CLARA 46 Hình 10. Mơ hình Snowball Hình 10 mơ tả vịng lặp hoạt động của Snowball, trong đĩ hai bước sinh mẫu và sinh seed mới là quan trọng nhất. Vịng lặp này kết thúc khi lượng seed sinh ra đủ lớn hoặc khơng tìm thêm được seed mới. Snowball biểu diễn các mẫu quan hệ dưới dạng các vector từ cĩ trọng số. Vì vậy mẫu sẽ cĩ khả năng khái quát cao, dễ dàng nhận bắt được các biến thể đa dạng của mẫu. Đồng thời Snowball cũng đưa ra phương pháp tìm kiếm, trích chọn và đánh giá độ tin cậy của seed mới và mẫu mới được sinh ra. Từ đĩ cĩ thể trích rút ra được một bảng dữ liệu lớn với độ tin cậy từ tập seed mồi ban đầu rất nhỏ. Trong chương 4, chúng tơi cĩ tiến hành thực nghiệm việc phân tích câu hỏi dựa trên tập mẫu (được học bằng phương pháp Snowball) và tích hợp vào hệ thống hỏi đáp tiếng Việt, bước đầu cho kết quả khá tốt. Tag Entities Seed Tuples Find Occurrences of Seed Tuples Generate New Seed Tuples Generate Extraction Patterns Augment Tables 47 Chương 4. Thực nghiệm phân tích câu hỏi tiếng Việt Chương này tiến hành thực nghiệm phân tích câu hỏi trên hai loại hệ thống hỏi đáp khác nhau. Với hệ thống hỏi đáp miền mở, chúng tơi xây dựng bộ phân lớp câu hỏi sử dụng học máy thống kê. Chúng tơi thử nghiệm với hai thuật tốn SVM và MEM, đồng thời thử nghiệm với các đặc trưng khác nhau của câu hỏi để tìm ra phương án lựa chọn phù hợp nhất cho phân lớp câu hỏi tiếng Việt. Với hệ thống hỏi đáp miền đĩng (miền du lịch), chúng tơi thực nghiệm việc phân tích câu hỏi dựa trên việc trích rút các mẫu quan hệ ngữ nghĩa. 4.1. Thực nghiệm với phân lớp câu hỏi sử dụng học máy thống kê 4.1.1. Dữ liệu và cơng cụ cho thực nghiệm Dựa theo các kết quả nghiên cứu về phân lớp câu hỏi được trình bày trong III, chúng tơi xây dựng bộ phân lớp sử dụng học máy thống kê cho hệ thống hỏi đáp trên miền mở theo các nội dụng sau: ™ Taxonomy câu hỏi: Sử dụng taxonomy của Li và Roth (đã trình bày trong phần 2.4.2) bao gồm 6 lớp cha: 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ố) và 50 lớp con. Tập taxonomy câu hỏi theo loại ngữ nghĩa của câu trả lời này được xem là cĩ khả năng bao phủ hầu hết các trường hợp về ngữ nghĩa của câu trả lời. ™ Dữ liệu: Sử dụng tập 5500 câu hỏi tiếng Anh đã được cơng bố bởi UIUC1 (bộ dữ liệu đã được gán nhãn chuẩn), chúng tơi tiến hành dịch sang tiếng Việt. Quá trình dịch được tiến hành theo tiêu chí: hiểu nghĩa và phân lớp của câu tiếng Anh, từ đĩ đặt câu hỏi với nội dung tương tự trong tiếng Việt theo văn phong tự nhiên của người Việt, đảm bảo rằng khơng cĩ sự gượng ép hay ảnh hưởng của tiếng Anh, số lượng người làm dữ liệu câu hỏi là 5, đảm bảo tính đa dạng trong văn phong tiếng Việt. Số lượng câu hỏi đã dịch được là 1684 với phân phối trên từng lớp được trình bày chi tiết trong bảng 3: 1 48 Bảng 3. Số lượng câu hỏi theo từng lớp cha Lớp cha Số câu hỏi HUMAN 344 NUMERIC VALUE 313 LOCATION 278 ENTITY 317 DESCRIPTION 393 ABBREVIATION 39 ™ Thuật tốn áp dụng: Sử dụng Support Vector Machine và Maximun Entropy Model (hai thuật tốn được áp dụng nhiều trong phân lớp câu hỏi tiếng Anh) ™ Cơng cụ: o Trong thực nghiêm với SVM, khĩa luận sử dụng SVMmulticlass - Multi-Class Support Vector Machine của tác giả Thorsten Joachims [22, 23]. o Với thuật tốn Entropy cực đại, khĩa luận sử dụng thư viện của tác giả Phan Xuân Hiếu [16]. o Module xử lý dữ liệu: Khử nhiễu câu hỏi, trích chọn các đặc trưng từ câu hỏi (phần này do tác giả tự viết). ™ Trích chọn đặc trưng: Chúng tơi tiến hành thử nghiệm và đánh giá ảnh hưởng của các đặc trưng khác nhau của câu hỏi tới việc phân lớp. o Đặc trưng đầu tiên được sử dụng là bag-of-unigram và bag-of-word. Để sử dụng bag-of-word, chúng tơi sử dụng cơng cụ tách từ tiếng Việt JVnTextPro [37]. o Chúng tơi đề xuất đưa thêm đặc trưng từ để hỏi. Trong tiếng Việt, nhiều khi chỉ cần dựa trên các từ để hỏi như ở đâu, khi nào, ai,.. là cĩ thể xác định được câu hỏi thuộc loại nào. Vì vậy chúng tơi sử dụng một danh sách các từ để hỏi trong tiếng Việt (xem bảng 7) làm đặc trưng cho phân lớp câu hỏi. 49 4.1.2. Kết quả bộ phân lớp sử dụng SVM và MEM Do số lượng câu hỏi gán nhãn cịn hạn chế nên ban đầu chúng tơi mới chỉ tiến hành thực nghiệm xây dựng bộ phân lớp cho 6 lớp cha. 4.1.2.1. Với MEM Kết quả thu được khá khả quan, đạt độ chính xác cao nhất là 81.14 % khi sử dụng đặc trưng là bag-of-word cĩ sử dụng tách từ. Kết quả chi tiết cho từng lớp được liệt kê trong Bảng 4 và Bảng 5. Bảng 4. Kết quả bộ phân lớp MEM khi sử dụng unigram Class human model match Pre Rec F1 ENTY 112 104 71 68.27 63.39 65.74 DESC 127 133 107 80.45 84.25 82.31 ABBR 10 11 8 72.73 80.00 76.19 HUM 131 132 112 84.85 85.50 85.17 NUM 97 101 90 89.11 92.78 90.91 LOC 85 81 66 81.48 77.65 79.52 Avg.1 79.48 80.60 80.03 Avg.2 562 562 454 80.78 80.78 80.78 Bảng 5. Kết quả bộ phân lớp MEM khi sử dụng tách từ class human model match Pre Rec F1 ENTY 112 109 72 66.06 64.29 65.16 DESC 127 137 107 78.10 84.25 81.06 ABBR 10 8 7 87.50 70.00 77.78 HUM 131 116 104 89.66 79.39 84.21 NUM 97 104 92 88.46 94.85 91.54 LOC 85 88 74 84.09 87.06 85.55 Avg.1 82.31 79.97 81.12 Avg.2 562 562 456 81.14 81.14 81.14 50 4.1.2.2. Với SVM Thiết lập tham số: Sau khi thử nghiệm với nhiều giá trị khác nhau, chúng tơi đặt giá trị c = 10000 (c là tham số trade off giữa tỉ lệ sai của dữ liệu học và kích thước biên của bộ phân lớp SVM).Kết quả tốt nhất với SVM khi sử dụng đặc trưng unigram kết hợp từ để hỏi với độ chính xác là 81.49%. Kết quả chi tiết được liệt kê trong Bảng 6. Bảng 6. Kết quả bộ phân lớp SVM sử dụng các đặc trưng khác nhau Đặc trưng Độ chính xác Tỉ lệ lỗi Unigram 80.78% 108/562 = 19.22% Tách từ 79.72% 121/562 = 20.28% Unigram + từ hỏi 81.49% 104/562 = 18.51% Tách từ + từ hỏi 80.60% 109/562 = 19.40% Bảng 7. Danh sách các từ hỏi tại sao thế nào định nghĩa ra sao cĩ cách nào cái gì vì sao bằng cách nào là gì làm sao chỗ nào gì nghĩ sao nơi nào ở đâu thì sao lúc nào đi đâu thấy sao lý do nào nơi đâu sao nguyên nhân nào từ đâu bao nhiêu khi nào đâu bao giờ thời gian nào cĩ phải bao người nào là ai cĩ mấy nào ai mấy nguyên nhân thật khơng như thế nào lý do phải khơng 51 Nhận xét: - Hai thuật tốn SVM và MEM cĩ kết quả xấp xỉ nhau trong phân lớp câu hỏi tiếng Việt. Kết quả tốt nhất với SVM là 81.49% và với MEM là 81.14%. - Đặc trưng từ để hỏi cĩ tác dụng nâng cao độ chính xác của phân lớp câu hỏi. Khi áp dụng với SVM, đặc trưng từ để hỏi giúp tăng độ chính xác 0.71% và 0.88% tương ứng khi kết hợp với đặc trưng unigram và tách từ. Độ tăng này khơng lớn cĩ thể được giải thích như sau: Trong các đặc trưng bag-of-unigram và bag-of-word cũng đã xét đến các từ hỏi này với vai trị giống với các từ khác trong câu hỏi. Việc xuất hiện các từ hỏi này với tần suất lớn theo từng loại câu hỏi khác nhau cũng đã giúp SVM ngầm nhận diện được các từ này là từ quan trọng trong phân lớp. - Ảnh hưởng của tách từ trong phân lớp câu hỏi: Với MEM, tách từ giúp tăng độ chính xác của phân lớp, trong khi với SVM đặc trưng tách từ lại khơng tốt bằng việc dùng unigram. Cĩ thể giải thích như sau: theo nguyên lý cực đại Entropy, mơ hình tự tìm ra trong dữ liệu (tập câu hỏi mẫu) những ràng buộc và đặc trưng riêng cho từng phân lớp. Với SVM, dữ liệu được biểu diễn dưới dạng các điểm trong khơng gian đặc trưng, SVM cố gắng tìm ra các siêu phẳng ngăn cách dữ liệu của từng lớp câu hỏi. Việc tách từ cĩ thể đã ảnh hưởng tích cực với việc tìm các ràng buộc của mơ hình MEM, trong khi lại ảnh hưởng tiêu cực đến sự phân bố dữ liệu trong khơng gian, dẫn đến siêu phẳng phân cách các lớp khơng tốt như siêu phẳng tìm được khi dùng unigram. 4.2. Thực nghiệm với xác định loại câu hỏi sử dụng mẫu quan hệ 4.2.1. Mơ hình thực nghiệm phân tích câu hỏi sử dụng mẫu quan hệ Trong [6], chúng tơi xây dựng một hệ thống hỏi đáp dựa trên việc trích rút các mẫu quan hệ ngữ nghĩa, áp dụng cho lĩnh vực du lịch. Mục tiêu của hệ thống là trả lời các câu hỏi dạng đơn giản, liên quan đến quan hệ ngữ nghĩa hai ngơi, ví dụ như “Hội lim tổ chức ở đâu?” (quan hệ LỄ HỘI – tổ chức ở - ĐỊA ĐIỂM), “Hà tây cĩ chùa gì ?” (quan hệ CHÙA- ở - ĐỊA ĐIỂM),…. Dựa vào việc khảo sát dữ liệu thực tế, chúng tơi liệt kê 85 mối quan hệ được quan tâm nhiều nhất trong ngành du lịch, ví dụ: lễ hội – địa điểm, bãi biển – địa điểm, đặc sản – địa điểm, núi – chiều cao,… Bước đầu chúng tơi tiến hành thực nghiệm trên 10 mối quan hệ. Mơ hình của hệ thống được mơ tả trong hình 11. 52 Hình 11. Mơ hình hệ thống hỏi đáp tiếng Việt sử dụng trích xuất mẫu quan hệ Hệ thống gồm hai pha chính: Trích rút mẫu tổng quát và sinh seed mới: Pha này được tiến hành offline, mục đích là tạo ra cơ sở dữ liệu về mẫu và seed phục vụ cho pha phân tích câu hỏi và trích xuất câu trả lời sau này. Phương pháp được sử dụng là Snowball kết hợp với việc sử dụng máy tìm kiếm Google để khai thác thơng tin sẵn cĩ trên Internet (xem chi tiết trong [6]) Pha phân tích câu hỏi và trích xuất câu trả lời (Hình 12): Pha này sử dụng cơ sở dữ liệu mẫu và seed được sinh ra trong pha trước để phân tích câu hỏi và trích xuất câu trả lời. Bước phân tích câu hỏi cĩ nhiệm vụ xác định tên thực thể và quan hệ mà câu hỏi đang hướng tới. Bước trích xuất câu trả lời chỉ đơn giản là truy vấn cơ sở dữ liệu (dựa trên đầu ra của bước phân tích câu hỏi). Câu hỏi Câu trả lời Phân tích câu hỏi và trích xuất câu trả lời Trích xuất mẫu tổng quát và seed Data 53 Hình 12. Mơ hình xử lý cho pha phân tích câu hỏi và trích xuất câu trả lời Pha phân tích câu hỏi bao gồm các bước chính sau đây: Ví dụ với câu hỏi: Nam Định cĩ những bãi biển gì? Bước 1: Nhận dạng thực thể trong câu hỏi dựa trên cơ sở dữ liệu. Sử dụng phương pháp so khớp tất cả các chuỗi con của câu hỏi với các thành phần trong tập seed (tập dữ liệu quan hệ) để tìm ra tập S các seed cĩ chứa thực thể của câu hỏi. Dựa vào các seed này, xác định tập R các quan hệ tương ứng và tập P các mẫu trả lời tiềm năng. Ví dụ với câu hỏi trên, thực thể nhận dạng được là Nam Định với nhãn TỈNH- THANH PHỐ. Từ đĩ hệ thống xác định được một tập seed S cĩ chứa một thành phần là Nam Định (Bảng 8). Bảng 8. Tập seed tìm được cùng với mối quan hệ tương ứng Mối quan hệ Thành phần thứ nhất của seed Thành phần thứ hai của seed Bãi biển – Địa điểm Quất Lâm Nam Định Bãi biển – Địa điểm Hải Thịnh Nam Định Lễ hội – Địa điểm Hội phủ giầy Nam Định Câu trả lời Câu hỏi Phân tích câu hỏi Trích rút câu trả lời Cơ sở dữ liệu mẫu và seed Tên thực thể và quan hệ 54 Tập các mối quan hệ cĩ thể là {Bãi biển-Địa điểm, Lễ hội-Địa điểm} (Bảng 9). Bảng 9. Tập quan hệ cùng các mẫu tương ứng Mối quan hệ Mẫu tổng quát Bãi biển – Địa điểm bãi_biển thuộc Bãi biển – Địa điểm cĩ bãi_biển Bãi biển – Địa điểm … Lễ hội – Địa điểm khai_mạc tại Lễ hội – Địa điểm Hằng năm tổ_chức lễ_hội Lễ hội – Địa điểm … … …. Bước 2: Biểu diễn câu hỏi (đã loại bỏ từ dừng và tách từ bằng cơng cụ JVnTextPro) dưới dạng vector từ cĩ trọng số. Vector câu hỏi cĩ dạng: Bước 3: Tính độ tương đồng giữa vector câu hỏi với các mẫu tiềm năng trong P sử dụng độ đo Cosin. Chọn mẫu p cĩ độ tương đồng Simp cao nhất với câu hỏi. Hệ thống sử dụng một ngưỡng µ- độ tương đồng thấp nhất giữa câu hỏi và mẫu. Nếu Simp < µ thì hệ thống khơng đưa ra câu trả lời (do độ tin cậy quá thấp). Nếu Simp > µ thì quan hệ r mà mẫu p thuộc vào là quan hệ mà câu hỏi đang hướng tới. Độ đo cosin giữa hai vector s1và s2 là: Trong ví dụ trên mẫu cĩ độ tương đồng cao nhất với vector câu hỏi là: cĩ bãi_biển Như vậy, qua ba bước trên, pha phân tích câu hỏi tìm ra được tên thực thể TỈNH-THÀNH PHỐ là Nam Định trong mối quan hệ Lễ hội-Địa điểm. Từ hai thơng tin này cũng biết được rằng câu hỏi đang hỏi về Lễ hội. Việc cịn lại của pha trích xuất câu trả lời là truy vấn cơ sở dữ liệu để đưa ra các Lễ hội của Nam Định. ||||.|||| . 21 21 ss ssSs = 55 4.2.2. Kết quả phân tích câu hỏi sử dụng mẫu quan hệ Tập dữ liệu test: Chúng tơi xây dựng một bộ câu hỏi gồm 1000 câu hỏi đơn giản liên quan đến 10 mối quan hệ được chọn (Bảng 10). Bảng 10. Các quan hệ được thực nghiệm trong hệ thống Lễ hội-địa điểm Nhà hàng – địa điểm Bãi biển – địa điểm Khách sạn – địa điểm Chùa chiền – địa điểm Siêu thị - địa điểm Sơng – địa điểm Cơng viên – địa điểm Quán cafe – địa điểm Chợ - địa điểm Cơng cụ phần mềm (Bảng 11): Bảng 11. Các cơng cụ sử dụng Java SE JDK 6 eclipse-SDK-3.4.1-win32 MySql 5.0 JvnTextPro [37] 56 Các thành phần chính trong hệ thống (Bảng 12): Bảng 12. Các thành phần chính của hệ thống Q&A trên miền du lịch Tên package, class Chức năng package vqa.Datalayer.dao Kết nối với cơ sở dữ liệu MySql package vqa.Datalayer.data Cài đặt các lớp RefinedPattern, RoughPattern, Seed,… là thành phần chính trong việc trích rút mẫu và seed package vqa.util Các hàm tiện ích package vqa. SearchEngineIE Thu thập dữ liệu cho việc tạo mẫu và seed thơng qua Google package vqa. CharsetDetector Phát hiện và sửa lỗi font chữ các tài liệu được lấy về từ Google class PatternGenerator và SeedGenerator Thực hiện quá trình sinh mẫu và seed mới class QuestionProcessor Phân tích câu hỏi và đưa ra câu trả lời Lựa chọn ngưỡng µ-độ tương đồng thấp nhất: Hệ thống sử dụng một ngưỡng µ về độ tương đồng thấp nhất giữa câu hỏi và mẫu. Hệ thống chỉ đưa ra câu trả lời khi độ tương đồng giữa câu hỏi và mẫu vượt qua ngưỡng µ. Khi lựa chọn giá trị của µ cần cân nhắc đến sự cân bằng giữa khả năng trả lời câu hỏi chính xác nhất và khả năng trả lời được nhiều câu hỏi nhất. Nếu µ càng lớn, thì độ tương đồng giữa câu hỏi và mẫu càng cao do đĩ độ chính xác sẽ tăng, trong khi đĩ số lượng câu trả hỏi trả lời được sẽ giảm. Bảng 13 thể hiện độ tương quan giữa độ chính xác và khả năng trả lời phụ thuộc vào ngưỡng µ. Bảng 13. Kết quả phân tích câu hỏi trong hệ thống hỏi đáp trên miền du lịch µ Độ chính xác Khả năng đưa ra câu trả lời 0.4 85.5% 95,3% 0.5 89,7 % 91,4% 0.6 92,6% 80,3% 57 Kết quả đạt được khá tốt khi chọn µ = 0.5, độ chính xác là 89.7% và khả năng trả lời là 91,4%. Nhận xét: Một hệ thống hỏi đáp tốt là hệ thống cĩ khả năng đưa ra câu trả lời chính xác nhất và cĩ thể trả lời được nhiều câu hỏi nhất. Theo thực nghiệm chúng tơi nhận thấy, độ chính xác (số lượng câu trả lời đúng trên số câu trả lời hệ thống đưa ra) và khả năng đưa ra câu trả lời (số lượng câu trả lời trên tổng số câu hỏi đưa vào) của hệ thống cĩ quan hệ tỉ lệ nghịch với nhau. Chúng tơi chọn giá trị của µ = 0.5 để đảm bảo độ cân bằng giữa 2 tính chất này của hệ thống. Hệ thống hoạt động khá tốt với các câu hỏi đơn giản hỏi về quan hệ ngữ nghĩa hai ngơi xung quanh các quan hệ được quan tâm, đưa ra câu trả lời cĩ độ tin cậy cao. Việc học ra các mẫu tốt, chính xác, thể hiện được đặc trưng của từng quan hệ là rất quan trọng, ảnh hưởng lớn đến độ chính xác của hệ thống. Chúng tơi đánh giá hệ thống cĩ khả năng mở rộng dễ dàng. Chỉ cần làm tay một số seed ban đầu cho các quan hệ quan tâm là hệ thống cĩ thể tự học ra các mẫu để trả lời cho câu hỏi liên quan. Tuy nhiên hạn chế của hệ thống là chỉ trả lời được các câu hỏi liên quan đến các quan hệ cĩ trong hệ thống. Để đáp ứng nhu cầu thực sự của người dùng, hệ thống cần phải mở rộng thêm nhiều quan hệ khác. 58 Kết luận Hệ thống hỏi đáp tự động đang nhận được sự quan tâm đặc biệt của các nhà nghiên cứu và doanh ng