Khóa luận Phân lớp câu hỏi hướng tới tìm kiếm ngữ nghĩa tiếng Việt trong lĩnh vực y tế

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Nguyễn Minh Tuấn PHÂN LỚP CÂU HỎI HƯỚNG TỚI TÌM KIẾM NGỮ NGHĨA TIẾNG VIỆT TRONG LĨNH VỰC Y TẾ KHỐ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ thơng tin HÀ NỘI - 2008 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Nguyễn Minh Tuấn PHÂN LỚP CÂU HỎI HƯỚNG TỚI TÌM KIẾM NGỮ NGHĨA TIẾNG VIỆT TRONG LĨNH VỰC Y TẾ KHỐ 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: PGS. TS. Hà Quang Thụy Cán bộ đồng hướng dẫn: Th.S Nguyễn Việt Cường HÀ NỘI - 2008 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 và Thạc sỹ Nguyễn Việt Cường, người đã tận tình chỉ bảo và hướng dẫn tơi trong suốt 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ơ đã 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 trường Đại Học Cơng Nghệ. Tơi xin gửi lời cảm ơn chân thành tới Thạc Sỹ Nguyễn Cẩm Tú và Cử Nhân Nguyễn Thu Trang những đã 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 nhĩm “Khai phá dữ liệu” đã 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 vơ hạn tới gia đình và bạn bè, những người thân yêu luơn bên cạnh và độ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 Minh Tuấn i Tĩm tắt Cùng với sự ra đời của Web ngữ nghĩa và các Ontology, nhu cầu tìm kiếm ngữ nghĩa ngày càng nhận được nhiều sự quan tâm trong cộng đồng nghiên cứu về khai phá dữ liệu Web/Text. Mặt khác, phân lớp câu hỏi là một trong những thành phần cơ bản nhưng quan trọng nhất trong kiến trúc tổng thể của hầu hết các máy tìm kiếm ngữ nghĩa. Đây cũng là thành phần chịu nhiều sự ảnh hưởng của các đặc trưng ngơn ngữ và giữ vai trị nền tảng cho các bước xử lý nhằm hướng tới tìm kiếm ngữ nghĩa. Khĩa luận này tập trung nghiên cứu phương pháp phân loại câu hỏi trong lĩnh vực y tế tiếng Việt dựa trên hướng tiếp cận cực đại hĩa Entropy (maxent). Dựa trên việc khảo sát các đặc trưng tiếng Việt và các hướng tiếp cận trong phân lớp câu hỏi trên tiếng Anh, khĩa luận đã tích hợp các đặc trưng này vào quá trình phân lớp với Maxent và thu được kết quả khả quan. Những nội dung này cĩ thể coi là những nghiên cứu đầu tiên trong vấn đề này trên tiếng Việt. ii Mục lục Tĩm tắt...................................................................................................................................i Mục lục .................................................................................................................................ii Danh sách các bảng .............................................................................................................iv Danh sách các hình...............................................................................................................v Lời mở đầu............................................................................................................................1 Chương I. Tổng quan về tìm kiếm ngữ nghĩa ......................................................................2 1.1. Nhu cầu về máy tìm kiếm ngữ nghĩa.....................................................................2 1.2. Cấu trúc tổng thể của một máy tìm kiếm ngữ nghĩa .............................................2 1.2.1. Nền tảng cho tìm kiếm ngữ nghĩa ..................................................................2 1.2.2.1. Web ngữ nghĩa........................................................................................3 1.2.2.2. Ontology .................................................................................................4 1.2.2. Kiến trúc cơ bản của một máy tìm kiếm ngữ nghĩa .......................................9 1.2.2.3. Giao diện người dùng ...........................................................................10 1.2.2.4. Kiến trúc bên trong ...............................................................................10 Chương 2. Tìm kiếm ngữ nghĩa trong tiếng Việt ...............................................................14 2.1. Tổng quan về cơ sở cho tìm kiếm ngữ nghĩa tiếng Việt......................................14 2.2. Một số đặc trưng của tiếng Việt ..........................................................................15 2.2.1 Đặc điểm ngữ âm .........................................................................................15 2.2.2 Đặc điểm từ vựng: ........................................................................................15 2.2.3 Đặc điểm ngữ pháp.......................................................................................16 2.3. Tìm kiếm ngữ nghĩa trong lĩnh vực y tế ..............................................................16 2.3.1. Ontology Y tế trong tiếng Việt.....................................................................16 2.3.2. Bộ phân lớp câu hỏi Y tế trong tiếng Việt ...................................................18 Chương 3. Các phương pháp phân lớp câu hỏi ..................................................................19 3.1. Giới thiệu về phân lớp câu hỏi.............................................................................19 3.2. Các phương pháp phân lớp câu hỏi .....................................................................19 3.3. Hướng tiếp cận dựa trên xác suất ........................................................................20 3.3.2 Các hướng tiếp cận theo phương pháp học máy ..........................................21 iii 3.3.1.1 Support Vector Machines (SVM).............................................................21 3.3.1.2 Một số phương pháp khác ........................................................................27 3.3.1.3 Thực nghiệm khi tiến hành phân lớp câu hỏi ...........................................28 3.3.3 Hướng tiếp cận dựa trên mơ hình hình ngơn ngữ ........................................31 3.3.3.1 Hướng tiếp cận Entropy cực đại ...............................................................33 Chương 4. Thực nghiệm và đánh giá .................................................................................37 4.1 Dữ liệu của thực nghiệm...........................................................................................37 4.2 Thiết kế thử nghiệm..................................................................................................38 4.3 Kết quả thực nghiệm.................................................................................................39 4.4 Đánh giá kết quả thực nghiệm ..................................................................................43 Kết luận...............................................................................................................................45 Tài liệu tham khảo ..............................................................................................................46 Tiếng Việt .......................................................................................................................46 Tiếng Anh .......................................................................................................................46 iv Danh sách các bảng Bảng 1: taxonomy của tập lớp câu hỏi thử nghiệm của Zhang .........................................28 Bảng 2. Độ chính xác trên năm phân lớp Cha với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-words. ...................................................................29 Bảng 3. Độ chính xác trên năm phân lớp Cha với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-Ngrams..................................................................30 Bảng 4. Độ chính xác trên các phân lớp con với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-words. ..................................................................30 Bảng 5. Độ chính xác trên các phân lớp con với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-Ngrams.................................................................31 Bảng 6.Tập dữ liệu huấn luyện ..........................................................................................37 Bảng 7. Tập dữ liệu kiểm tra..............................................................................................38 Bảng 8. Tham số huấn luyện mơ hình SVM .......................................................................39 Bảng 9. Tham số huấn luyện mơ hình Entropy cực đại .....................................................39 Bảng 10. kết quả huấn luyện với SVM ...............................................................................39 Bảng 11. Kết quả 10 lần huấn luyện với Entropy cực đại ................................................40 Bảng 12. Kết quả của bước lặp thứ 6 ................................................................................41 v Danh sách các hình Hình 1. Ví dụ về Web ngữ nghĩa .........................................................................................3 Hình 2. Ví dụ về Ontology Y tế ............................................................................................6 Hình 3. Sơ đồ của máy tìm kiếm ngữ nghĩa .........................................................................9 Hình 5. Mối quan hệ giữa các siêu phẳng phân cách .......................................................23 Hình 6. Siêu phẳng tối ưu và biên. ....................................................................................24 Hình 7. Sơ đồ phân lớp câu hỏi với SVM ..........................................................................26 Hình 8. Đồ thị biểu diễn sự phụ thuộc của F1 vào số lần lặp ...........................................42 Hình 9. Tổng hợp độ đo 10 lần huấn luyện .......................................................................42 1 Lời mở đầu Sự ra đời của Web ngữ nghĩa và các Ontology dẫn tới sự ra đời của các hệ thống tìm kiếm với sự hộ trợ của dạng thơng tin mới này – hệ thống tìm kiếm ngữ nghĩa. Một hệ thống tìm kiếm ngữ nghĩa thơng thường được xây dựng trên một miền và ngơn ngữ cụ thể. Cấu trúc nội tại của một hệ thống tìm kiếm ngữ nghĩa điển hình bao gồm hai thành phần quan trọng mang đặc trưng ngơn ngữ đĩ là: (1) phân lớp câu hỏi và (2) cơ sở dữ liệu tri thứ (mạng ngữ nghĩa). Trong vài năm gần đây nhiều cơng trình nghiên cứu giải quyết bài tốn phân lớp câu hỏi đã được cơng bố [16], [15], [19], [36], [42]. Ta cĩ thể chia các thuật tốn phân lớp câu hỏi thành hai hướng tiếp cận chính: (1) hướng tiếp cận theo regular expression (biểu thức chính qui) [35] và (2) hướng tiếp cận dựa trên xác suất [16], [15], [19], [36], [42]. Mỗi hướng tiếp cận cĩ những ưu và nhược điểm riêng và sẽ được xem xét trong các phần sau đây. Khĩa luận này tiến hành phân tích cấu trúc tổng thể của một máy tìm kiếm ngữ nghĩa. Qua đĩ chỉ ra các module ảnh hưởng bởi đặc trưng ngơn ngữ và tiến hành khảo sát các phương pháp giải quyết bài tốn phân lớp câu hỏi phổ biến hiện nay. Từ đĩ đề xuất giải pháp thích hợp khi áp dụng vào tiếng Việt . Khĩa luận gồm bốn chương nội dung được mơ tả sơ bộ dưới đây: Chương 1. Tổng quan về tìm kiếm ngữ nghĩa giới thiệu những thành phần cơ bản về một hệ thống tìm kiếm ngữ nghĩa: nhu cầu về tìm kiếm ngữ nghĩa và các nền tảng cho tìm kiếm ngữ nghĩa hình thành. Đồng thời, chương này cũng giới thiệu kiến trúc tổng thể của một hệ thống tìm kiếm ngữ nghĩa và chỉ ra các module chịu ảnh hưởng bởi đặc trưng của ngơn ngữ. Chương 2. Tìm kiếm ngữ nghĩa trong tiếng Việt trình bày về hiện trạng của tìm kiếm ngữ nghĩa trong tiếng Việt hiện nay. Qua đĩ, chỉ ra những cơ sở cần thiết để xây dựng một hệ thống tìm kiếm ngữ nghĩa trong tiếng Việt. Đồng thời, chương này cũng giới thiệu quá trình phân tích và xây dựng hai module mang đặc trưng ngơn ngữ, tạo tiền đề xây dựng mộ hệ thống tìm kiếm ngữ nghĩa trong lĩnh vực Y tế tiếng Việt. Chương 3. Các phương pháp phân lớp câu hỏi khảo sát và phân tích kỹ lưỡng các thuật tốn cho bài tốn phân lớp câu hỏi, chỉ ra ưu nhược điểm của từng phương pháp. Qua đĩ lựa, chọn phương pháp tốt nhất để thử nghiệm trong tiếng Việt. Chương 4. Thực nghiệm và đánh giá hai thuật tốn Support Vector Machine và nguyên lý Entropy cực đại trên tập dữ liệu câu hỏi Y tế tiếng Việt. Kết quả thử nghiệm cho thấy hiệu của của từng phương pháp và chỉ rõ phương pháp nào thích hơn khi áp dụng cho tiếng Việt. Phần kết luận tổng kết và tĩm lược nội dung chính của khĩa luận. 2 Chương I. Tổng quan về tìm kiếm ngữ nghĩa 1.1. Nhu cầu về máy tìm kiếm ngữ nghĩa Lượng thơng tin khổng lồ và phát triển mạnh mẽ theo từng ngày trên World Wide Web (thường được gọi tắt là Web) đưa ra thách thức để khai thác được thơng tin trên Web một cách hiệu quả. Các máy tìm kiếm như Google, Yahoo… ra đời nhằm hỗ trợ người dùngtrong quá trình tìm kiếm và sử dụng thơng tin. Tuy kết quả trả về của các máy tìm kiếm này ngày càng được cải thiện về chất và lượng nhưng vẫn đơn thuần là danh sách các tài liệu chứa những từ xuất hiện trong câu truy vấn. Những thơng tin từ các kết quả trả về này chỉ được hiểu bởi con người, máy tính khơng thể “hiểu” được, điều này gây những khĩ khăn cho quá trình xử lý thơng tin tìm kiếm được về sau. Sự ra đời của Web ngữ nghĩa (hay Semantic Web được W3C (The World Wide Web Consortium) giới thiệu trong [40]) đã mở ra một bước tiến của cơng nghệ Web những thơng tin trong Web ngữ nghĩa cĩ cấu trúc hồn chỉnh và mang ngữ nghĩa mà máy tính cĩ thể “hiểu” được. Những thơng tin này, cĩ thể được sử dụng lại mà khơng cần qua các bước tiền xử lý. Khi sử dụng các máy tìm kiếm thơng thường (Google, Yahoo…), tìm kiếm thơng tin trên Web ngữ nghĩa sẽ khơng tận dụng được những ưu điểm vượt trội của Web ngữ nghĩa, kết quả trả về khơng cĩ sự thay đổi. Nĩi theo một cách khác thì với các máy tìm kiếm hiện tại Web ngữ nghĩa hay Web thơng thường chỉ là một. Do vậy, cần thiết cĩ một hệ thống tìm kiếm ngữ nghĩa (Semantic Search) tìm kiếm trên Web ngữ nghĩa hay trên một mạng tri thức mang ngữ nghĩa, kết quả trả về là các thơng tin cĩ cấu trúc hồn chỉnh mà máy tính cĩ thể “hiểu” được, nhờ đĩ việc sử dụng hay xử lý thơng tin trở nên dễ dàng hơn[27][29]. Ngồi ra, việc xây dựng được một hệ thống tìm kiếm ngữ nghĩa cụ thể sẽ tạo tiền đề cho việc mở rộng xây dựng các hệ thống hỏi đáp tự động trên từng lĩnh vực cụ thể như : Y tế, văn hĩa … điều này mang một ý nghĩa thiết thực trong đời sống. 1.2. Cấu trúc tổng thể của một máy tìm kiếm ngữ nghĩa Máy tìm kiếm ngữ nghĩa được xây dựng dựa trên những cơng nghệ, kỹ thuật mới của khoa học. Mỗi cơng nghệ phát triển trên những nền tảng nhất định. Do vậy để mơ tả cấu trúc của một máy tìm kiếm ngữ nghĩa một cách chi tiết nhất, trước tiên cần đề cập các nền tảng cho tìm kiếm ngữ nghĩa. 1.2.1. Nền tảng cho tìm kiếm ngữ nghĩa Cĩ hai nền tảng cho tìm kiếm ngữ nghĩa đĩ là: (1) Web ngữ nghĩa : là sự phát triển mở rộng của Web hiện tại. (2) Ontology : dùng để mơ tả các tài nguyên thơng tin cĩ ngữ nghĩa. 3 1.2.2.1. Web ngữ nghĩa Web ngữ nghĩa hay cịn gọi là Semantic Web theo Tim Berners-Lee [34] là bước phát triển mở rộng của cơng nghệ Word Wide Web hiện tại, chứa các thơng tin được định nghĩa rõ ràng sao cho con người và máy tính làm việc với nhau hiệu quả hơn. Mục tiêu của Web ngữ nghĩa là phát triển dựa trên những chuẩn và cơng nghệ chung, cho phép máy tính cĩ thể hiểu thơng tin chứa trong các trang Web nhiều hơn nhằm hỗ trợ tốt con người trong khai phá dữ liệu, tổng hợp thơng tin, hay trong việc xây dựng các hệ thống tự động khác… Khơng giống như cơng nghệ Web thơng thường, nội dung chỉ bao hàm các tài nguyên văn bản, liên kết, hình ảnh, video mà Web ngữ nghĩa cĩ thể bao gồm những tài nguyên thơng tin trừu tượng hơn như: địa điểm, con người, tổ chức… thậm chí là một sự kiện trong cuộc sống. Ngồi ra, liên kết trong Web ngữ nghĩa khơng chỉ đơn thuần là các siêu liên kết (hyperlink) giữa các tài nguyên mà cịn chứa nhiều loại liên kết, quan hệ khác. Những đặc điểm này khiến nội dung của Web ngữ nghĩa đa dạng hơn, chi tiết và đầy đủ hơn. Đồng thời, những thơng tin chứa trong Web ngữ nghĩa cĩ một mối liên hệ chặt chẽ với nhau. Với sự chặt chẽ này, người dùng dễ dàng hơn trong việc sử dụng, và tìm kiếm thơng tin. Đây cũng là ưu điểm lớn nhất của Web ngữ nghĩa so với cơng nghệ Web thơng thường. Hình 1. Ví dụ về Web ngữ nghĩa [27] Hình 1 là một ví dụ mơ tả về một trang Web ngữ nghĩa chứa thơng tin của một người tên là Yo-Yo Ma. Trang Web cĩ cấu trúc như một đồ thị cĩ hướng mang trọng số, mà mỗi đỉnh của đồ thị mơ tả một kiểu tài nguyên chứa trong trang Web. Các cạnh của đồ thị thể hiện một kiểu liên kết (hay cịn gọi là thuộc tính của tài nguyên) giữa các tài nguyên, trọng số của các liên kết đĩ thể hiện tên của liên kết (tên của thuộc tính) đĩ. Cụ thể ta thấy Yo-Yo Ma cĩ thuộc tính ngày sinh là “10/07/55” cĩ nơi sinh ở “Paris, France”, “Paris, France” cĩ nhiệt độ là “62 F” … 4 Như vậy, mỗi tài nguyên được mơ tả trong Web ngữ nghĩa là một đối tượng. Đối tượng này cĩ tên gọi, thuộc tính, giá trị của thuộc tính (giá trị cĩ thể là một đối tượng khác) và liên kết với các tài nguyên (đối tượng) khác (nếu cĩ). Để xây dựng được một trang Web ngữ nghĩa cần phải cĩ tập dữ liệu đầy đủ, nĩi một cách khác là cần phải xây dựng một tập các đối tượng mơ tả tài nguyên cho Web ngữ nghĩa. Các đối cĩ quan hệ với nhau hình thành một mạng liên kết rộng, được gọi là mạng ngữ nghĩa. Mạng ngữ nghĩa được chia sẻ rộng khắp do vậy các đối tượng trong một mạng ngữ nghĩa cần phải mơ tả theo một chuẩn chung nhất. Ontology [25][23] được sử dụng để mơ tả về đối tượng, tài nguyên cho Web ngữ nghĩa. 1.2.2.2. Ontology Trong những năm gần đây, thuật ngữ “Ontology” khơng chỉ được sử dụng ở trong các phịng thì nghiệm trên lĩnh vực trí tuệ nhân tạo mà đã trở nên phổ biến đối với nhiều miền lĩnh vực trong đời sống. Đứng trên quan điểm của ngành trí tuệ nhân tạo, một Ontology là sự mơt tả về những khái niệm và những quan hệ của các khái niệm đĩ nhằm mục đích thể hiện một gĩc nhìn về thế giới. Trên miền ứng dụng khác của khoa học, một Ontology bao gồm tập các từ vựng cơ bản hay một tài nguyên trên một miền lĩnh vực cụ thể, nhờ đĩ những nhà nghiên cứu cĩ thể lưu trữ, quản lý và trao đổi tri thức cho nhau theo một cách tiện lợi nhất [25]. a. Khái niệm và cấu trúc của Ontology Hiện nay tồn tại nhiều khái niệm về Ontology, trong đĩ cĩ nhiều khái niệm mâu thuẫn với các khác niệm khác, khĩa luận này chỉ giới thiệu một định nghĩa mang tính khái quát và được sử dụng khá phổ biến được Kincho H. Law đưa ra: “Ontology là biểu hiện một tập các khái niệm (đối tượng), trong một miền cụ thể và những mối quan hệ giữa các khái niệm này” [18]. Một Ontology cĩ bốn thành phần chính: cá thể (individuals), lớp (classes), thuộc tính (attributes) và các mối quan hệ (relationships). Với cấu trúc này, Ontology được sử dụng rộng rãi như một mơ hình phân lớp thơng tin trong việc phát triển thơng tin trên Web. Ngồi ra một Taxonomy [33] cĩ thể được coi như là một Ontology khuyết (khơng cĩ thành phần thuộc tính, tính chất trong mơ tả). Cụ thể hơn về cấu trúc của một Ontology được mơ tả thơng qua các thành phần của nĩ như sau: • Cá thể (individuals): là một thể hiện (hay đối tượng) cụ thể của Ontology, bao gồm đầy đủ các thuộc tính, liên kết của Ontology. Một cá thể là một đối tượng thực như con người, xe cộ, động vật … nhưng cũng cĩ thể là một khái niệm trừu tượng như chữ số, sự kiện … Về mặt lý thuyết, một Ontology cĩ thể khơng cĩ một thể hiện nào, nhưng một trong những mục đích của Ontology là cung cấp ngữ nghĩa cho những lớp cá thể riêng biệt, vì vậy thể hiện của một Ontology là cần thiết. 5 • Lớp (classes): hay cịn được gọi là khái niệm, kiểu hay loại, là một nhĩm trừu tượng của các đối tượng. Một lớp cĩ thể bao gồm các thể hiện của lớp đĩ hay bao gồm một lớp con khác. Ví dụ về một lớp Ontology như: Person (lớp mơ tả về con người) , Vehicle (lớp mơ tả về các phương tiện vận chuyển)… • Thuộc tính (Attributes): Các thể hiện trong một Ontology cĩ thể được gán cho chúng những thuộc tính riêng, nhằm biểu thị các đặc trưng riêng và phân biệt với các thể hiện khác. Mỗi một thuộc tính của Ontology đều cĩ hai thành phần gồm tên của thuộc tính và giá trị được gán cho thuộc tính đĩ. Ví dụ cá thể cĩ tên là K49HTTT cĩ các thuộc tính sau: o Tên : K49HTTT o Số lượng sinh viên : 56 o Chủ nhiệm : lecturer.NguyenNgocHoa Các thuộc tính của một Ontolgy được thiết kế phù hợp với các đặc điểm của đối tượng được mơ tả ở ngồi thực tế. Giá trị của một thuộc tính cĩ thể là một kiểu phức hợp (kết hợp nhiều kiểu dữ liệu khác nhau) hoặc cĩ thể là một lớp khác của Ontology. • Quan hệ (relationships): Được thể hiện bằng các thuộc tính của Ontology. Một quan hệ được hình thành khi giá trị của một thuộc tính là một cá thể của một Ontology. Các mối quan hệ này thể hiện sự liên kết giữa các đối tượng trong Ontology. Mối quan hệ “xếp gộp” (Subsumption) là một liên kết chủ đạo trong các Ontology, thể hiện các kiểu quan hệ: là lớp cha (is_superclass_of), là (is_a), là lớp con (is_subclass_of). Với liên kết “xếp gộp” Ontology sẽ cĩ cấu trúc như một cây phân cấp. Ngồi liên kết chủ đạo trên, một Ontology cụ thể cĩ thể cĩ nhiều liên kết khác. 6 Hình 2. Ví dụ về Ontology Y tế [1] Trong hình 2, phần bên trái mơ tả cấu trúc phân cấp của Ontology Y tế, thể hiện tên các lớp và mối quan hệ “xếp gộp” của các lớp đĩ. Lớp Thing là lớp cha (is_superclass_of) của tất cả các lớp cịn lại như: Bệnh, Chất_hĩa_học, Nguyên_nhân, Thuốc… Các lớp con (is_subclass_of) của Thing cũng cĩ thể cĩ nhiều lớp con khác ví dụ như lớp Thuốc bao gồm hai lớp con: Đơng_y, Tây_y… Phần bên phải thể hiện các thuộc tính hoặc liên kết cĩ trong Ontology Y tế, ví dụ như liên kết biến_chứng thể hiện liên kết của một cá thể thuộc lớp Bệnh với một cá thể khác cũng thuộc lớp Bệnh, hay liên kết gây_ra mơ tả một quan hệ giữa lớp Nguyên_nhân và lớp Bệnh… Trong ví dụ trên chưa cĩ sự hiện diện cụ thể của các cá thể (thể hiện) trong các lớp, nhưng những thể hiện cụ thể của các lớp cĩ thể được thêm vào bởi các chuyên gia trên lĩnh vực Y tế (ví dụ như Chuột gây_ra dịch_hạch …). b. Ngơn ngữ mơ tả tài nguyên Web ngữ nghĩa và Ontology Một Ontology cần được mơ tả bằng một cấu trúc chặt chẽ và theo những chuẩn chung nhất để người sử dụng cĩ thể chia sẻ (với người sử dụng khác) hoặc sử dụng lại 7 những Ontology đã cĩ sẵn. Trong phần này trình bày về RDF (Resource Description Framework )[30] một framework cho việc mơ hình hĩa, mơ tả tài nguyên trên Web và OWL [38] (Web Ontology Language) đang được sử dụng rộng rãi hiện nay. • RDF – Resouce Description Framework : là một mơ hình được W3C đề xuất là mở rộng của cơng nghệ XML [37] với mục tiêu đưa đưa ra một chuẩn chung trong việc mơ hình hĩa và mơ tả các tài nguyên trên Web. Ngồi ra RDF cịn là một cấu trúc để thể hiện dữ liệu. RDF cĩ tập các từ khĩa, tập ngữ pháp và tập luật riêng được giới thiệu cụ thể ở [39]. Ví dụ mơ tả về tài nguyên bằng RDF như sau: • OWL (Web Ontology Language) : là một ngơn ngữ biểu diễn tri thức dựa trên RDF, được xây dựng để mơ tả Web ngữ nghĩa. OWL cĩ những đặc điểm sau: o OWL là một chuẩn của Web. o OWL được viết dưới dạng XML. o OWL dùng để xử lý thơng tin trên Web. o OWL là một ngơn ngữ được thơng dịch bởi máy tính. Về cơ bản OWL và RDF cĩ nhiều đặc điểm giống nhau, tuy nhiên OWL cĩ tập từ vựng (từ khĩa) lớn hơn RDF, và là một ngơn ngữ được máy tính thơng dịch tốt hơn RDF. OWL được chia thành ba loại khác nhau, đáp ứng với từng nhu cầu sử dụng cụ thể: (1) OWL lite: Đây là phiên bản đơn giản nhất của OWL, dành cho những người dùng chỉ cĩ nhu cầu về tách lớp các tài nguyên riêng rẽ và giữa các tài nguyên cĩ những ràng buộc hay quan hệ đơn giản. Ví dụ : về ràng buộc lực lượng, với OWL lite số lực lượng này chỉ cĩ thể mang giá trị 0 hoặc 1. (2) OWL DL: Dành cho những người sử dụng địi hỏi những tính năng phức tạp trong tính tốn và xử lý thơng tin với những ràng buộc chặt chẽ: Các bước xử lý, suy luận đều được tối ưu và thực hiện trong thời gian giới hạn … OWL được tích hợp với logic mơ tả (description logic [9]). Tuy nhiên OWL DL vẫn cĩ một số hạn chế như : Một class cĩ thể được thừa kế bởi nhiều class khác nhưng, class này khơng thể là một thể hiện của class khác… ITLab, Vietnam National University, Hanoi 8 (3) OWL full : Hướng tới những người dùng địi hỏi tối đa những tính năng của OWL mà khơng bị ràng buộc bởi cấu trúc ngữ pháp phức tạp. OWL full cĩ cấu trúc lỏng lẻo như RDF, ví dụ : một lớp trong OWL full cĩ thể đồng thời được coi như là một tập các thể hiện hoặc là một thể hiện của chính lớp đĩ. Giữa ba loại của ngơn ngữ OWL cĩ quan hệ bao hàm nhau. Tức là: tất các các qui tắc cấu trúc hợp lệ của OWL lite thì đều hợp lệ với OWL dl, và mọi qui tắc, cấu trúc hợp lệ của OWL dl thì đều hợp lệ với OWL full. Một ví dụ về OWL lite: Với OWL việc truy xuất, xử lý và chia sẻ Ontology giữa những người sử dụng trở nên dễ dàng hơn. Nhờ đĩ giảm bớt những khĩ khăn khi xây dựng cơ sở tri thức và nguồn tài nguyên cho Web ngữ nghĩa, tạo tiền đề cho Web ngữ nghĩa phát triển. Version 0.1 Countries Ontology, Created by Jenz & Partner GmbH, Version 0.1, 28-FEB-2004 9 1.2.2. Kiến trúc cơ bản của một máy tìm kiếm ngữ nghĩa Xét về cơ bản, một máy tìm kiếm ngữ nghĩa cĩ cấu trúc tương tự với một máy tìm kiếm thơng thường cũng bao gồm hai thành phần chính: (1) Phần giao diện người dùng (front end) cĩ hai chức năng chính: - Giao diện truy vấn: cho phép người dùng nhập câu hỏi, truy vấn. - Hiển thị câu trả lời, kết quả. (2) Phần kiến trúc bên trong (back end) là phần hạt nhân của máy tìm kiếm bao gồm ba thành phần chính đĩ là: - Phân tích câu hỏi - Tìm kiếm kết quả cho truy vấn hay câu hỏi - Tập tài liệu, dữ liệu tìm kiếm/ mạng ngữ nghĩa. Sự khác biệt trong cấu trúc của máy tìm kiếm ngữ nghĩa so với máy tìm kiếm thơng thường nằm ở phần kiến trúc bên trong, cụ thể ở hai thành phần: phân tích câu hỏi và tập dữ liệu tìm kiếm. Về cơ bản, một máy tìm kiếm cĩ kiến trúc như sau: Hình 3. Sơ đồ của máy tìm kiếm ngữ nghĩa Mạng ngữ nghĩa Semantic Web/Ontology Search Services 1.Nhập truy vấn 5.Kết quả trả về 2.Phân lớp câu hỏi 3.Biển đổi dạng câu hỏi 4.Tìm kiếm 10 1.2.2.3. Giao diện người dùng Như đã giới thiệu ở trên, giao diện người dùng cĩ hai chức năng đĩ là cho phép người dùng nhập câu hỏi hoặc truy vấn tìm kiếm và hiện thị kết quả trả về. So với các máy tìm kiếm thơng thường thì phần này khơng cĩ sự khác biệt lớn và cĩ thể tùy biến, thay đổi dễ dàng. Tuy vậy, để phục vụ cho mục đích là tìm kiếm ngữ nghĩa, phía giao diện người dùng cần cung cấp cho người sử dụng những lựa chọn khi tìm kiếm: • Cung cấp lựa chọn tìm kiếm theo từng miền lĩnh vực cụ thể, nếu một máy tìm kiếm ngữ nghĩa cĩ cơ sở tìm kiếm ngữ nghĩa bao gồm nhiều lĩnh vực • Gợi ý các từ để hỏi ví dụ như (what, where, when…) khi người dùng nhập câu hỏi. Điều này giúp ích cho việc phân lớp câu hỏi và giới hạn được loại câu trả lời phù hợp cho truy vấn người dùng đưa vào, tiết kiệm thời gian tìm kiếm. 1.2.2.4. Kiến trúc bên trong Như mơ tả ở hình 3, các thành phần của kiến trúc bên trong bao gồm bốn module chính: phân lớp câu hỏi, biến đổi dạng câu hỏi, tìm kiếm và mạng ngữ nghĩa. Các bước xử lý một câu hỏi/truy vấn của người dùng như sau: - Bước (1) người dùng nhập câu hỏi/ truy vấn của mình ở giao diện. - Bước (2) câu hỏi/ truy vấn ở (1) đưa qua bộ phân tích câu hỏi để xác định câu hỏi thuộc về lĩnh vực miền nào và thuộc về phần nào trong lĩnh vực đĩ. Ví dụ câu hỏi “Bệnh Lao phổi chữa như thế nào?” được phân về domain Y tế. - Bước (3) câu hỏi được biển đổi về dạng chuẩn (biểu thức logic) để cĩ thể tiến hành tìm kiếm. - Bước (4) câu hỏi/truy vấn được tìm kiếm trên mạng ngữ nghĩa của máy tìm kiếm. - Bước (5) hiện thị kết quả trả về của câu hỏi/truy vấn đưa vào. Một máy tìm kiếm ngữ nghĩa sẽ xử lý câu hỏi của người dùng qua năm bước cơ bản như trên. Và tùy thuộc vào từng đặc điểm của loại máy tìm kiếm định xây dựng, mà cĩ thể cĩ thêm những module khác. Ví dụ một số máy tìm kiếm cĩ cĩ phần lựa chọn câu trả lời thích hợp nhất do người dùng lựa chọn nhằm xây dựng tập câu trả lời mẫu . a. Phân lớp câu hỏi Phân lớp câu hỏi là một trong hai thành phần quan trọng nhất của một máy tìm kiếm ngữ nghĩa. Phần này đảm nhiệm vai trị phân loại câu hỏi theo chủ đề và lĩnh vực. Quá trình phân lớp cĩ thể tiến hành qua hai bước: (1) Phân lớp xác định miền câu hỏi: Yêu cầu này xuất phát từ cơ sở dữ liệu của máy tìm kiếm ngữ nghĩa (mạng ngữ nghĩa). Các mạng này về cơ bản được xây dựng từ các Ontology, mà Ontology được xây dựng theo từng miền lĩnh vực riêng rẽ. Do vậy cần tiến hành phân loại truy vấn theo miền câu hỏi nhằm xác định miền 11 Ontology của câu hỏi để giới hạn khơng gian tìm kiếm, giảm thời gian tìm kiếm. Phân lớp miền câu hỏi cĩ ảnh hưởng quyết định tới chất lượng của kết quả trả về.. Một ví dụ minh chứng cho điều này: Giả sử người dùng đưa vào câu hỏi : “bệnh sởi cĩ chữa được khơng” và cơ sở mạng ngữ nghĩa trong máy tìm kiếm bao gồm 4 miền : Y tế, Du lịch, Văn hĩa và Chính trị. Qua bộ phân lớp miền câu hỏi, nếu kết quả trả về là thuộc miền Y tế thì máy tìm kiếm sẽ đưa ra kết quả trả lời phù hợp hơn, cịn nếu xác định một miền miền khác khơng phải Y tế thì sẽ khơng cĩ kết quả trả hoặc sai về mặt ý nghĩa. (2) Phân loại loại câu hỏi trong một miền: cấu trúc nội tại của một Ontology cĩ sự phân cấp rất lớn: một Ontogy được chia thành nhiều phần, nhiều tầng, lớp bao hàm nhau, mỗi tầng của Ontology cũng cĩ thể coi là một miền nhỏ bao hàm một miền tri thức nhỏ cĩ mối quan hệ mật thiết với nhau. Do đĩ để cĩ thể tối ưu tìm kiếm cịn cần phân lớp trên nội tại một miền. Bước này tiến hành phân lớp câu hỏi trên nội tại một miền, phân lớp câu hỏi theo những lĩnh vực khác nhau của một miền. Chúng ta coi Ontology là một cây cĩ cấu trúc phân tầng, mỗi lớp trong Ontology sẽ thuộc một tầng nhất định, và trong mỗi tầng các đối tượng cĩ độ liên quan đến nhau lớn, và độ liên quan này giảm đi khi các đối tượng ở những tầng khác nhau. Tiến hành phần loại nội miền chính là việc chỉ ra câu hỏi người dùng đưa vào thuộc tầng nào hoặc cụm nào của Ontology. Bước này làm giới hạn tối đa khơng gian tìm kiếm, mang lại kết quả chính xác hơn và nhanh hơn. Sự khác biết giữa phân loại miền câu hỏi và phân loại nội miền chỉ ở khơng gian phân loại. Trong khi phân loại miền câu hỏi khơng gian là tồn bộ tập Ontology của mạng ngữ nghĩa,thì phân loại nội miền tiến hành trên một miền Ontology cụ thể, cịn về thuật tốn tiến hành phân loại thì như nhau. Phụ thuộc vào máy tìm kiếm ngữ nghĩa cần xây dựng, mà một trong hai bước phân loại câu hỏi trên cĩ thể được bỏ qua. Ví dụ: khi xây dựng một hệ thống tìm kiếm ngữ nghĩa cho một miền cụ thể (hệ thống hỏi đáp) thì việc phân loại miền câu hỏi là khơng cần thiết, chỉ cần thiết phân loại nội miền. Hiện nay đã cĩ nhiều phương pháp để phân lớp câu hỏi trong đĩ nổi bật là hai hướng tiếp cận: dựa vào biểu thức chính qui (regular expression) và hướng tiếp cận dựa trên xác suất. Mỗi phương pháp cĩ những ưu và nhược điểm riêng. Với hướng tiếp cận biểu thức chính qui, câu hỏi đưa vào được so sánh các mẫu câu hỏi cĩ sẵn, do đĩ phương pháp này địi hỏi các chuyên gia khi xây dựng bộ câu hỏi mẫu và thường khĩ xác định hết được các trường hợp nhập nhằng nên kết quả phân lớp câu hỏi thường khơng được như ý muốn… Cụ thể về các phương pháp sẽ được trình bày ở chương 3. 12 b. Biến đổi dạng câu hỏi Theo Maria Vargas-Vera, Enrico Motta và John Domingue [21], sau khi qua bộ phân lớp câu hỏi truy vấn của người dung được chuyển từ dạng ngơn ngữ tự nhiên sang dạng ngơn ngữ lo-gic (Question Logic Language - QLL). QLL là một ngơn ngữ thể hiện câu hỏi/ truy vấn thuộc ngơn ngữ tự nhiên theo dạng logic học. Mỗi một câu thuộc QLL chứa các terms (biểu thức, biến, thủ tục…) của ngơn ngữ Prolog , nĩi một các khác QLL là một ngơn ngữ con của Prolog [5]. Theo [21] cĩ một số qui tắc khi chuyển đổi từ một câu S1 ở dạng ngơn ngữ tự nhiên sang câu S2 thuộc QLL như sau: (1) Một danh từ đơn (theo đơn vị từ) của S1 sẽ tạo nên một vị từ đơn trong S2. Ví dụ: S1 “ Hà Nội là thành phố vì hịa bình”, thì trong S2 sẽ chứa vị từ sau thành_phố(Hà Nội). (2) Cụm danh từ của S1 tạo nên một vị phức trong S2 với số tham số bằng số lượng từ đơn chứa trong cụm danh từ của S1 cộng thêm 1. Ví dụ S1 “Số lượng sinh viên của Trường Đại học Cơng nghệ là bao nhiêu?”. Tạo ra một vị từ phức trong S2 là số_lượng_sinh_viên(đại_học_cơng_nghệ, X) ở đây X là số lượng sinh viên. (3) Một động từ của S1 sẽ tạo nên một vị từ phức với một hoặc nhiều tham số, tham số đầu tiên là chủ ngữ của S1, tham số thứ hai là vị ngữ chính của S1, tham số thứ ba là vị ngữ phụ của S1 (nếu cĩ), tham số thứ tư là các bổ ngữ (nếu cĩ)… Ví dụ: S1 “Torres ghi bàn vào lưới ManU”, thì S2 sẽ chứa vị từ ghi_bàn(Torres, ManU). (4) Một giới từ trong S1 tạo nên một vị từ phức với hai tham số là hai từ được nối bởi giới từ đĩ. Ví dụ S1 “Cái bút nằm trên bàn học”, S2 sẽ chứa vị từ nằm_trên(bút,bàn_học). (5) Một tính từ định tính cĩ thể tạo nên một vị từ với một hoặc hai tham số. Ví dụ S1 “diện tích của Hà nội là bao nhiêu?” trong S2 sẽ chứa vị từ diện_tích(Hà_Nội, X) – X là diện tích. Với 5 qui tắc biến đổi trên, một câu hỏi bất kỳ đều được chuyển sang dạng QLL, với lợi thế về suy luận và tối ưu xử lý, câu hỏi dưới dạng QLL sẽ mang lại tốc độ tốt hơn và mang đặc thù ngữ nghĩa nhiều hơn. c. Tìm kiếm câu trả lời. Sau khi câu hỏi/truy vấn của người dùng được chuyển sang dạng QLL, hệ thống tiến hành tìm kiếm câu trả lời sẽ được thực hiện qua các phép tốn logic với dữ liệu là các Ontology (mạng ngữ nghĩa) được xây dựng từ trước. Giả sử S2 là một câu truy vấn dạng QLL, hệ thống cần tìm ra câu trả lời cho S2. Chiến lược giải quyết như sau: 13 (1) Với mỗi một vị từ trong S2, xác định Ontology để tìm kiếm (sử dụng kết quả từ bước phân lớp câu hỏi ở trên), tìm ra đối tượng chứa câu trả lời từ tập các đối tượng thuộc miền Ontology đã chỉ ra, trong đĩ: o Đối tượng chứa câu trả lời phải cĩ một thuộc tính cĩ độ tương đồng với một trong các tham số của vị từ. Ví dụ: với vị từ diện_tích(Hà_Nơi), trong Ontology về địa lý đối tượng chứa câu trả lời sẽ là thành_phố.Hà_Nội - ở đây cĩ sự tương đồng về tên của đối tượng với tham số của vị từ. o Thơng tin trả lời cho vị từ hoặc thơng tin về vị từ được mơ tả bằng tên gọi của lớp hay bằng thuộc tính của một lớp cĩ trong Ontology. Ví dụ : với vị từ diện_tích (Hà_Nội) thì câu trả lời được chứa trong một thuộc tính của đối tượng thành_phố.Hà_Nội. (2) Lặp lại bước (1) cho đến khi tìm được đối tượng chứa thơng tin trả lời, hoặc đã tìm qua tất cả các đối tượng mà khơng cĩ câu trả lời. Vị từ nào khơng đưa lại kết quả (khơng xác định được giá trị) sẽ được loại bỏ ra khỏi S2. Câu trả lời của truy vấn sẽ là phép tính tổ hợp giá trị của các vị từ. Thay vì đưa ra câu trả lời chính xác hoặc khi khơng tìm được câu trả lời chính xác cho câu hỏi đưa vào, hệ thống cĩ thể trả về thơng tin của đối tượng được xác định là cĩ thể trả lời cho câu hỏi. d. Mạng ngữ nghĩa. Mạng ngữ nghĩa là cơ sở dữ liệu cho hệ thống tìm kiếm ngữ nghĩa. Về cơ bản, một mạng ngữ được hình thành từ một tập các thơng tin mang ngữ nghĩa cĩ quan hệ với nhau cĩ thể là tập các Ontology hay tập các trang Web ngữ nghĩa. Với các máy tìm kiếm thơng thường, cơ sở dữ liệu cho tìm kiếm được thu thập tự động từ các trang Web hiện cĩ trên internet. Và quá trình xử lý các thơng tin của các trang Web lấy về khơng gặp nhiều khĩ khăn. Trái lại, đối với máy tìm kiếm ngữ nghĩa thì cơng việc xây cơ sở cho tìm kiếm khơng đơn giản bởi hai nguyên nhân sau: • Số lượng các trang Web ngữ nghĩa cịn hạn chế. • Việc xây dựng Ontology cho từng miền địi hỏi sự hợp tác của nhiều chuyên gia miền trong thời gian lớn. Hiện nay cĩ một số cơng cụ hỗ trợ việc xây dựng Ontology như: Protégé hay GATE… 1 2 3 14 Chương 2. Tìm kiếm ngữ nghĩa trong tiếng Việt 2.1. Tổng quan về cơ sở cho tìm kiếm ngữ nghĩa tiếng Việt Từ cấu trúc cơ bản của một hệ thống tìm kiếm ngữ nghĩa đã được trình bày ở trên cho thấy để xây dựng được một hệ thống tìm kiếm ngữ nghĩa trong tiếng Việt trước tiên phải giải quyết hai bai tốn: (1) Xây dựng bộ phân lớp câu hỏi tiếng Việt (2) Xây dựng một mạng ngữ nghĩa tiếng Việt Hai bài tốn trên đều chịu sự chi phối của yếu tố ngơn ngữ. Tiếng Việt cĩ những đặc trưng riêng biệt về: chữ viết – chính tả, âm tiết và từ … do vậy đối với bài tốn (1) và (2) phải tích hợp được những đặc trưng này. Hiện nay chưa cĩ hệ thống tìm kiếm ngữ nghĩa tiếng Việt nào được cơng bố. Nguyên nhân chính là do tập cơ sở dữ liệu về ngữ nghĩa tiếng Việt cịn ít khơng như tiếng Anh, Pháp… Trên thế giới cĩ rất nhiều tổ chức, viện nghiên cứu, trường đại học đã đưa ra các Ontology trong những miền lĩnh vực khác nhau, cĩ thể kể đến như: • Miền Y tế cĩ các Ontology như : Semantic Mining1 một Ontology về khai phá dữ liệu trong Y tế, hay Disease Ontology là Ontology về các từ khĩa chuyên ngành y khoa được phát triển bởi khoa Tin sinh tại Center for Genetic Medicine2 ... • Miền thương mại, kinh doanh: điển hình là Ontology-Based Business Process Management được nghiên cứu và phát triển bởi Jenz & Partner GmbH [16]. • Miền khoa học phổ thơng: cĩ Ontology về vật lý (Physical-Concepts được phát triển bởi Laboratory for Applied Ontology3) … • Và nhiều miền lĩnh vực khác. Cĩ một số ít Ontolgy được cơng bố, điển hình là Ontology VN–KIM [4]. Ontology này bao gồm 347 lớp thực thể và 114 quan hệ và thuộc tính. Cơ sở tri thức của VN-KIM là một tập hợp các thực thể cĩ tên phổ biến ở Việt Nam và Quốc tế, các thực thể chủ yếu thuộc các miền như: - Con người (Các nhà lãnh đạo quốc gia, giám đốc cơng ty, bác sỹ, nhà giáo, văn nghệ sỹ…) - Tổ chức, cơng ty (Các tổ chức xã hội, giáo dục, cơng ty…) 15 - Đơn vị hành chính (các tỉnh, thành phố, quận, huyện, phường, xã ở Việt Nam và các thành phố lớn trên thế giới) - Sơng, núi (các sơng, núi lớn ở Việt Nam và trên thế giới) - Đường (các đường ở TPHCM, Hà Nội, các tỉnh lộ, quốc lộ) Điều này cho thấy, tập các Ontology miền trong Tiếng Việt cịn ít, đây là một trong những khĩ khăn cần giải quyết để sớm, tạo tiền đề phát triển những hệ thống mang ngữ nghĩa. 2.2. Một số đặc trưng của tiếng Việt Tiếng Việt thuộc ngơn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm tách rời nhau và được thể hiện bằng một chữ viết. Đặc điểm này thể hiện rõ rệt ở tất cả các mặt ngữ âm, từ vựng, ngữ pháp. Dưới đây trình bày một số đặc điểm của tiếng Việt theo các tác giả ở Trung tâm ngơn ngữ học Việt Nam đã trình bày [3]. 2.2.1 Đặc điểm ngữ âm Tiếng Việt cĩ một loại đơn vị đặc biệt gọi là "tiếng", về mặt ngữ âm, mỗi tiếng là một âm tiết. Hệ thống âm vị tiếng Việt phong phú và cĩ tính cân đối, tạo ra tiềm năng của ngữ âm tiếng Việt trong việc thể hiện các đơn vị cĩ nghĩa. Nhiều từ tượng hình, tượng thanh cĩ giá trị gợi tả đặc sắc. Khi tạo câu, tạo lời, người Việt rất chú ý đến sự hài hồ về ngữ âm, đến nhạc điệu của câu văn. 2.2.2 Đặc điểm từ vựng: Mỗi tiếng nĩi chung là một yếu tố cĩ nghĩa. Tiếng là đơn vị cơ sở của hệ thống các đơn vị cĩ nghĩa của tiếng Việt. Từ tiếng, người ta tạo ra các đơn vị từ vựng khác để định danh sự vật, hiện tượng..., chủ yếu nhờ phương thức ghép và phương thức láy. Việc tạo ra các đơn vị từ vựng ở phương thức ghép luơn chịu sự chi phối của quy luật kết hợp ngữ nghĩa, ví dụ: đất nước, máy bay, nhà lầu xe hơi, nhà tan cửa nát... Hiện nay, đây là phương thức chủ yếu để sản sinh ra các đơn vị từ vựng. Theo phương thức này, tiếng Việt triệt để sử dụng các yếu tố cấu tạo từ thuần Việt hay vay mượn từ các ngơn ngữ khác để tạo ra các từ, ngữ mới, ví dụ như tiếp thị, karaoke, thư điện tử (e-mail), thư thoại (voice mail), phiên bản (version), xa lộ thơng tin, siêu liên kết văn bản, truy cập ngẫu nhiên, v.v. Việc tạo ra các đơn vị từ vựng ở phương thức láy thì quy luật phối hợp ngữ âm chi phối chủ yếu việc tạo ra các đơn vị từ vựng, chẳng hạn như chơm chỉa, chỏng chơ, đỏng đa đỏng đảnh, thơ thẩn, lúng lá lúng liếng, v.v. Vốn từ vựng tối thiểu của tiếng Việt phần lớn là các từ đơn tiết (một âm tiết, một tiếng). Sự linh hoạt trong sử dụng, việc tạo ra các từ ngữ mới một cách dễ dàng đã tạo điều kiện thuận lợi cho sự phát triển vốn từ, vừa phong phú về số lượng, vừa đa dạng trong hoạt động. Cùng một sự vật, hiện tượng, một hoạt động hay một đặc trưng, cĩ thể cĩ nhiều từ ngữ khác nhau biểu thị. Tiềm năng của vốn từ ngữ tiếng Việt được phát huy cao độ trong các phong cách chức năng ngơn ngữ, đặc biệt là trong phong cách ngơn ngữ 16 nghệ thuật. Hiện nay, do sự phát triển vượt bậc của khoa học-kĩ thuật, đặc biệt là cơng nghệ thơng tin, thì tiềm năng đĩ cịn được phát huy mạnh mẽ hơn. 2.2.3 Đặc điểm ngữ pháp: Từ của tiếng Việt khơng biến đổi hình thái. Đặc điểm này sẽ chi phối các đặc điểm ngữ pháp khác. Khi từ kết hợp từ thành các kết cấu như ngữ, câu, tiếng Việt rất coi trọng phương thức trật tự từ và hư từ. Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các quan hệ cú pháp. Trong tiếng Việt khi nĩi “Anh ta lại đến” là khác với “Lại đến anh ta”. Khi các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước giữ vai trị chính, từ đứng sau giữ vai trị phụ. Nhờ trật tự kết hợp của từ mà "củ cải" khác với "cải củ", "tình cảm" khác với "cảm tình". Trật tự chủ ngữ đứng trước, vị ngữ đứng sau là trật tự phổ biến của kết cấu câu tiếng Việt. Phương thức hư từ cũng là phương thức ngữ pháp chủ yếu của tiếng Việt. Nhờ hư từ mà tổ hợp “anh của em” khác với tổ hợp “anh và em”, “anh vì em”. Hư từ cùng với trật tự từ cho phép tiếng Việt tạo ra nhiều câu cùng cĩ nội dung thơng báo cơ bản như nhau nhưng khác nhau về sắc thái biểu cảm. Ví dụ, so sánh các câu sau đây: - Ơng ấy khơng hút thuốc. - Thuốc, ơng ấy khơng hút. - Thuốc, ơng ấy cũng khơng hút. Ngồi trật tự từ và hư từ, tiếng Việt cịn sử dụng phương thức ngữ điệu. Ngữ điệu giữ vai trị trong việc biểu hiện quan hệ cú pháp của các yếu tố trong câu, nhờ đĩ nhằm đưa ra nội dung muốn thơng báo. Trên văn bản, ngữ điệu thường được biểu hiện bằng dấu câu. Sự khác nhau trong nội dung thơng báo được nhận biệt khi so sánh hai câu sau: - Đêm hơm qua, cầu gãy. - Đêm hơm, qua cầu gãy. Qua một số đặc điểm nổi bật vừa nêu trên đây, chúng ta cĩ thể hình dung được phần nào bản sắc và tiềm năng của tiếng Việt 2.3. Tìm kiếm ngữ nghĩa trong lĩnh vực y tế Trong phần này, khĩa luận sẽ trình bày những bước đầu của việc xây dựng một máy tìm kiếm ngữ nghĩa trên lĩnh vực Y tế cho tiếng Việt. 2.3.1. Ontology Y tế trong tiếng Việt Với các dữ liệu về y tế thu thập được từ các trang Web và Ontology BioCaster [1], tiến hành liệt kê các thuật ngữ (term) quan trọng nhằm cĩ thể nêu định nghĩa cho người dùng với hướng nghiên cứu tiếp theo là tự động liên kết đến các định nghĩa cĩ sẵn trên 17 trang wikipedia. Từ các thuật ngữ trên, sẽ định nghĩa các thuộc tính của chúng. Việc xây dựng Ontology là một quá trình lặp lại được bắt đầu bằng việc định nghĩa các khái niệm trong hệ thống lớp và mơ tả thuộc tính của các khái niệm đĩ. Qua khảo sát Ontology BioCaster với các thuật ngữ trong tiếng Việt, cùng với một số luợng lớn các trang Web về y tế hiện nay ở Việt Nam, chúng tơi đã xây dựng nên một tập các thuật ngữ, các mối quan hệ cơ bản nhất để từ đĩ để xuất ra Ontology thử nghiệm ban đầu, với những khái niệm cơ bản sau: - Thuốc: bao gồm hai loại Đơng y và Tây y. Ví dụ, thuốc 5-Fluorouracil Ebewe chống ung thư (ung thư đại trực tràng, vú, thực quản, dạ dày), hay là thuốc Ciloxan sát trùng, chống nhiễm khuẩn ở mắt. Thuốc đơng y ngũ gia bì chữa bệnh phong thấp, tráng gân cốt … - Bệnh, hội chứng: Các loại bệnh như cúm gà, viêm loét dạ dày, các hội chứng mất ngủ, suy tim … - Triệu chứng : Ví dụ như triệu chứng của cúm H5N1 là sốt cao, nhức đầu, đau mỏi tồn thân,... - Nguyên nhân: Tác nhân (virut, vi khuẩn..muỗi, gà, chim..), và các nguyên khác như là thiếu ngủ, lười tập thể dục, hút thuốc lá thụ động … - Thực phẩm: Bao gồm các mĩn ăn cĩ lợi hoặc gây hại cho sức khỏe con nguời cũng như phù hợp với một số loại bệnh nào đĩ. - Người: Bao gồm bác sỹ, giáo sư mà người bệnh cĩ thể tìm kiếm để khám bênh, xin giúp đỡ khi mắc bệnh. - Tổ chức: Bệnh viện, phịng khám, hiệu thuốc … là các địa điểm để bệnh nhân cĩ thể tìm đến khi mắc bệnh. - Địa điểm: Địa chỉ của một tổ chức nào đĩ mà bệnh nhân cĩ thể tìm đến, các nơi dịch đang phát sinh và lan rộng. - Cơ thể người: Là tất cả các bộ phận cơ thể người cĩ thể thể bị nhiễm bệnh: mắt, mũi, gan, tim … - Hoạt động: Chẩn trị, xét nghiệm, hồi cứu, hơ hấp nhân tạo, phịng tránh, tiêm phịng ... - Hĩa chất: Vitamin, khống chất …gây tác động xấu, tốt đến cơ thể con người, ví dụ vitamin A cĩ lợi cho mắt, Vitamin C, E làm giảm các nguy cơ bệnh tim… Giữa các khái niệm cơ bản trên cĩ các mỗi quan hệ như sau: - Sự tương tác thuốc – thuốc : Thuốc này cĩ thể gây tác dụng phụ cho thuốc kia, hay cĩ thể kết hợp các loại thuốc với nhau để chữa bệnh. Ví dụ thuốc chống ung 18 thư Alexan khơng nên dùng chung với methotrexate hay 5-fluorouracil - Thực phẩm tác động xấu, tốt đến bệnh, cơ thể người: Ví dụ như uống xơđa nhiêu cĩ rủi ro mắc các bệnh rối loạn trao đổi chất, tăng vịng bụng, tăng huyết áp… - Quan hệ bệnh – thuốc: () - Quan hệ nguyên nhân gây ra bệnh, hay bệnh cĩ nguyên nhân: () - Quan hệ bệnh – triệu chứng: () - Quan hệ bệnh biến chứng thành bệnh khác: - Các hoạt động tác động lên bệnh: - Bệnh được phát hiện, chữa trị ở tổ chức: - Người làm việc trong một tổ chức tại địa điểm nào đĩ: Ví dụ minh họa thể hiện Mơ hình của Ontology Y tế này ở hình 2. 2.3.2. Bộ phân lớp câu hỏi Y tế trong tiếng Việt Với Ontology Y tế giới thiệu ở phần trên, để giải quyết được hai bài tốn mang đặc trưng của tiếng Việt cần xây dựng một bộ phân lớp câu hỏi Y tế trong tiếng Việt. Bộ phân lớp câu hỏi này là bộ phân lớp nội miền (trong miền Ontology Y tế), tức là với các câu hỏi/truy vấn của người dùng đưa vào, bộ phân lớp phải xác định chúng thuộc về các khái niệm nào. Chương 3 sẽ cụ thể hĩa các phương pháp phân lớp câu hỏi. 19 Chương 3. Các phương pháp phân lớp câu hỏi 3.1. Giới thiệu về phân lớp câu hỏi. Trong hầu hết các hệ thống tìm kiếm ngữ nghĩa, bước đầu tiên là xử lý câu hỏi nhằm xác định câu hỏi đĩ hỏi về cái gì? Phân chia truy vấn của người dùng ra thành một số lớp định nghĩa trước như hỏi địa điểm (ở đâu ?), thời gian (khi nào ?)… Thơng thường ở phần lớn các trường hợp để xác định được điều này, hệ thống thường sử dụng một số thơng tin hay đặc trưng của câu hỏi để xác định kiểu của câu trả lời. Ví dụ với câu hỏi “ai là người phát hiện ra vacxin phịng bệnh dại?” thì mục đích của câu hỏi là muốn tìm hiểu thơng tin về một người. Hệ thống cần xác định được kiểu của câu trả lời (trong ví dụ này là thơng tin về một người) để cĩ thể trả về thong tin mong muốn cho người dùng. Trong các hệ thống tìm kiếm ngữ nghĩa, đối tượng được tìm kiếm là các thơng tin mang ngữ nghĩa, do vậy việc phân lớp câu hỏi cịn được gọi là phân lớp ngữ nghĩa cho câu hỏi (semantic question classification) cĩ hai vai trị quan trọng sau đây: (1) Giảm khơng gian tìm kiếm, chẳng hạn với câu hỏi “thuốc nào chữa bệnh viêm họng?” hệ thống chỉ cần tìm kiếm trên các lớp thuốc của miền Y tế để cĩ câu trả lời, thay vì tìm kiếm trên tồn bộ cơ sở dữ liệu. (2) Nâng cao độ chính xác của câu trả lời. Đối với các hệ thống tìm kiếm ngữ nghĩa lớn tìm kiếm trên nhiều miền Ontology, thường cĩ bộ phân lớp câu hỏi kép gồm : (1) phân lớp để xác định miền Ontology của câu hỏi (phân lớp nội miền) (2) phân lớp để xác định câu hỏi thuộc lĩnh vực nào (lớp nào) trong miền Ontology đã xác định ở phân lớp nội miền. Ngược lại đối với các máy tìm kiếm ngữ nghĩa trên một miền Ontology, chỉ cần xây dựng bộ phân lớp đơn (2). 3.2. Các phương pháp phân lớp câu hỏi Hiện nay, cĩ một số nghiên cứu tập trung vào hướng tiếp cận biểu thức chính qui dựa vào những luật ngữ pháp viết tay (hand-written grammar rulers) để xác định lớp của câu hỏi đầu vào như các tác giả B., Huang, Y., Kupsc, A. và Nyberg, E năm 2003 [35] giới thiệu. Mặc dù hướng tiếp cận này cũng đạt được những thành cơng đáng kể, nhưng vẫn cĩ những hạn chế mà đã được Li, Roth 2002[19] và Hacioglu, Ward 2003[16] chỉ ra. 20 Cụ thể, các tác giả [14] đã chỉ ra bốn hạn chế của hướng tiếp cận này: (1) 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 đĩ. (2) 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. (3) 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ữ. (4) 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. Với các hạn chế như trên dẫn đến số lớp của bộ phân lớp theo hướng này là nhỏ (khoảng 8-10 lớp) khơng thích hợp khi tích hợp vào một hệ thống tìm kiếm ngữ nghĩa cĩ qui mơ lớn. Một hướng tiếp cận khác để giải quyết bài tốn phân lớp câu hỏi là theo hướng tiếp cận xác suất được Jonathan Brown năm 2004 tổng hợp lại [15], bao gồm hai cách tiếp cận chính đĩ là: (1) Tiếp cận theo hướng học máy (machine learning) (2) Tiếp cận theo mơ hình ngơn ngữ (language modeling) Khơng giống như hướng tiếp cận biểu thức chính quy (thực hiện việc so sánh mẫu), các phương pháp theo hướng tiếp cận dựa trên xác suất sẽ xây dựng một mơ hình phân lớp tự động từ tập dữ liệu học cho trước. 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 lớp cho câu hỏi vào 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/truy vấn đưa vào. Nhờ đĩ phương pháp này khắc phục những nhược điểm của hướng tiếp cận biểu thức chính quy [15]. Do vậy, hướng tiếp cận này khơng những phù hợp với các hệ thống tìm kiếm ngữ nghĩa lớn mà cịn phù hợp với các hệ thống nhỏ hơn (do khả năng linh hoạt cao dễ dàng mở rộng tập dữ liệu và số phân lớp). Khĩa luận sẽ tập trung trình bày các phương pháp phân lớp câu hỏi dựa trên hướng tiếp cận xác suất để xây dựng bộ phân lớp câu hỏi trong Tiếng Việt. 3.3. Hướng tiếp cận dựa trên xác suất Bên cạnh hướng tiếp cận dựa trên biểu thức chính quy thì hướng tiếp cận dựa trên xác suất cũng là một hướng tiếp cận được nhiều nhà khoa học lựa chọn khi nghiên cứu về phân lớp câu hỏi. Như đã được giới thiệu, hướng tiếp cận dựa trên xác suất bao gồm hai hướng con là hướng học máy và hướng dựa trên mơ hình ngơn ngữ [15]. Hướng tiếp cận học máy sử dụng những thuật tốn và kỹ thuật cho phép máy tính cĩ thể “học” 1 được. Cụ thể, trong bài tốn phân lớp câu hỏi hướng tiếp cận học máy sử dụng các thuật tốn như : Support Vector Machines (SVM), láng giềng gần nhất (Nearest 21 Neighbors – kNN), Nạve Bayes (NB)…v.v để học trên tập câu hỏi mẫu đã được gán nhãn từ đĩ xây dựng mơ hình phân lớp câu hỏi. Trong khi đĩ, tiếp cận dựa trên mơ hình ngơn ngữ xây dựng một mơ hình ngơn ngữ thống kê cĩ thể ước lượng được phân phối của ngơn ngữ tự nhiên chính xác nhất cĩ thể. Ví dụ, với một xâu S = “Bệnh đau dạ dày chữa ở đâu?” thì mơ hình ngơn ngữ cho xâu S chính là xác suất P(S), sao cho xác suất này ánh xạ với tần suất mà xâu S trở được xuất hiện như một câu nĩi trong ngơn ngữ tự nhiên (ví dụ tiếng Việt). Khi áp dụng phương pháp này cho bài tốn phân lớp câu hỏi, tức là xây dựng một mơ hình ngơn ngữ cho từng câu hỏi. Mơ hình này sẽ cho biết xác suất câu hỏi được phân vào lớp nào là hợp lý nhất (lớn nhất). Cả hai phương pháp trên đều cĩ độ chính xác khác nhau phụ thuộc vào ngơn ngữ áp dụng. Để lựa chọn hướng tiếp cận tốt nhất khi xây dựng bộ phân lớp câu hỏi cho tiếng Việt, phần tiếp theo của khĩa luận sẽ trình bày những khảo sát về cả hai hướng tiếp cận trên 3.3.2 Các hướng tiếp cận theo phương pháp học máy Trong hướng tiếp học máy thuật tốn được sử dụng chủ yếu để giải quyết bài tốn phân lớp câu hỏi là Support Vector Machines (được sử dụng trong các tài liệu [19, 20, 22], ngồi ra các thuật tốn khác cũng được sử dụng như Nearest Neighbors (NN), Nạve Bayes (NB), Decision Tree (DT) và Sparse Network of Winnows (SNoW) [42]. Đưới đây trình bày sơ lược về nội dung một số thuật tốn học máy. 3.3.1.1 Support Vector Machines (SVM) a. Thuật tốn [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 chỉ được thiết kế để giải quyết bài tốn phân lớp nhị phân tức là số lớp hạn chế là hai lớp. Hiện nay, SVM được đánh giá là bộ phân lớp chính xác nhất cho bài tốn phân lớp văn bản [31] bởi vì đĩ là bộ phân lớp tốc độ rất nhanh và hiệu quả đối với bài tốn phân lớp văn bản. Cho tập dữ liệu học D ={(xi, yi), i = 1,…, n} với xi ∈ Rm và yi∈{0,1} là một số là một số nguyên xác định xi là dữ liệu dương hay âm. 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) = WT + w0 =0} Trong đĩ W∈ Rm và w0∈R đĩ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 22 Học bộ phân lớp của mơ hình bao gồm 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 đơn giản để xác định siêu phẳng : 1. w ←0 2. w0←0 3. repeat 4. e←0 5. for i←1,…,n 6. do s←sign(yi(wTxi +w0) 7. if s<0 8. then w ←w + yixi 9. w0←w0 + yixi 10. e←e+1 11. util e=0 12. return (w,w0) Điều kiện cần để 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. 23 Hình 4. Mối quan hệ giữa các siêu phẳng phân cách Trong Hình 4, 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 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 đầu vào m, vì với một số lượng các dữ liệu mẫu cố định, tập hợp các siêu phẳng thực tế 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ừ. 24 Hình 5. Siêu phẳng tối ưu và biên. Theo lý thuyết 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 thoả mãn hai tính chất quan trong (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 [26]. Đị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. 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 || + ≥ = 0 T ww ||w|| 1 + 25 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ểm 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 = ⎡ ⎤= − + α + −⎣ ⎦∑ 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α = − α Λα + α∑ thoả 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 thoả 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 thoả 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 Nếu dữ liệu học khơng tách rời tuyến tính, thêm biến ξi và thay phương trình trên bằng phương trình: ∑ = + 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 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. 26 b. 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[20]. Ý tưởng cơ bản như sau: - 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 . - Chia tập Y thành m tập 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. c. Áp dụng SVM vào phân lớp câu hỏi Tuy mục tiêu ban đầu của SVM là dùng cho phân lớp nhị phân, nhưng hiện nay đã được cải tiến cho phân lớp đa lớp, phiên bản phân lớp đa lớp này sẽ được sử dụng cho bài tốn phân lớp câu hỏi. Hai quá trình chuẩn bị dữ liệu khi xây dựng được mơ hình phân lớp câu hỏi dựa trên SVM như sau: (1) Thiết kế mơ hình cây phân cấp (taxonomy) cho tập lớp câu hỏi. Miền ứng dụng của câu hỏi sẽ quyết định độ phức tạp (phân cấp) của taxonomy (2) Xây dựng tập dữ liệu mẫu (corpus) đã được gán nhãn cho từng lớp câu hỏi. Trong bước này, cách lựa chọn đặc trưng để biểu diễn câu hỏi cĩ vai trị quan trọng. Phụ thuộc vào đặc điểm của từng ngơn ngữ mà tập các đặc trưng được lựa chọn khác nhau. Ví dụ với tiếng Anh thì tập đặc trưng của nĩ là các từ. Sau khi xây dựng được tập các lớp câu hỏi cùng với tập dữ liệu sẽ tiến hành “học”: Mơ hình học như sau: Hình 6. Sơ đồ phân lớp câu hỏi với SVM Trong Hình 6, bước tiền xử lý thực hiện chức năng làm tinh dữ liệu: loại bỏ từ dừng (stopword) …sau đĩ câu hỏi được trích trọn các đặc trưng (các đặc trưng được lựa chọn từ trước), dữ liệu đầu vào của bộ phân lớp SVM sẽ là tập các vector đặc trưng. 27 3.3.1.2 Một số phương pháp khác Ngồi SVM và K láng giềng gần nhất, trong bài tốn phân lớp câu hỏi một số phương pháp khác được giới thiệu ở [42] như: • Thuật tốn Nạve Bayes (NB) [32]là một thuật tốn phổ biến trong học máy. Được McCallum [22] và Yang [41] đánh giá là một trong những phương pháp cĩ hiệu năng cao nhất khi thực hiện phân lớp văn bản. Tư tưởng chủ đạo của thuật tốn Nạve Bayes là ước lượng các thơng số của đa thức sinh cho của thể hiện (văn bản, câu …). Sau đĩ lựa chọn lớp thích hợp nhất cho từng thể hiện dựa vào các luật Bayes và giả thiết Bayes (giả thiết độc lập - sự xuất hiện của đặc trưng này là tự nhiên, khơng phụ thuộc vào sự xuất hiện các đặc trưng khác) • Thuật tốn cây quyết định (Decision Tree –DT) [32] là phương pháp xấp xỉ giá trị các hàm mục tiêu rời rạc. Trong đĩ, hàm học của phương pháp này là một cây cĩ bậc tùy ý. Cây quyết định bao gồm các lá và nhánh, mỗi là là đại diện cho một lớp và các nhánh là các điều kiện, đặc trưng dẫn đến lớp ở đỉnh lá. • Thuật tốn Mạng lọc thưa (Sparse Network of Winnows -SNoW) [6] được thiết kế để học trên những tập dữ liệu cĩ số lượng đặc trưng lớn. Được sử dụng rộng rãi trong các bài tốn phân lớp đa lớp. SNoW là một mạng thưa dùng các hàm tuyến tính là các bộ lọc để cập nhật tập luật. Phương pháp này thích hợp cho học trong miền khi các đặc trưng tiềm năng tạo các quyết định sai khác nhau mà khơng biết mức độ ưu tiên. • Bộ phân lớp dựa trên thuật tốn K người láng giềng gần nhất là một bộ phân lớp dựa trên bộ nhớ, đơn giản vì nĩ được xây dựng bằng cách lưu trữ tất cả các đối tượng trong tập huấn luyện. Để phân lớp cho một điểm dữ liệu mới x, trước hết bộ phân lớp sẽ tính khoảng cách từ điểm x đến tất cả các điểm dữ liệu trong tập huấn luyện. Qua đĩ tìm được tập N(x, D, k) gồm k điểm dữ liệu mẫu cĩ khoảng cách đến x là gần nhất. Ví dụ nếu các dữ liệu mẫu được biểu diễn bởi khơng gian vector thì chúng ta cĩ thể sử dụng khoảng cách Euclian để tính khoảng cách giữa các điểm dữ liệu với nhau. Sau khi xác định được tập N(x, D, k), bộ phân lớp sẽ gán nhãn cho điểm dữ liệu x bằng lớp chiếm đại đa số trong tập N(x, D, k). Mặc dù rất đơn giản, nhưng thuật tốn K người láng giềng gần nhất đã cho kết quả tốt trong nhiều ứng dụng thực tế. Để áp dụng thuật tốn k-NN vào tài liệu văn bản, chúng ta sử dụng hàm tính trọng số cho mỗi lớp theo biểu thức (1.1) (Trong cơng thức, ( )kD,x,Nc là tập con chỉ chứa các đối tượng thuộc lớp c của tập): ( ) ( )∑∈= kD,x,Ncx' )x'cos(x,x|cScore (1.1) Khi đĩ tài liệu x sẽ được phân vào lớp c0 nếu: ( ) ( ){ }Cc,x|cscoreMaxx|cScore 0 ∈= 28 3.3.1.3 Thực nghiệm khi tiến hành phân lớp câu hỏi Với sự phong phú của các thuật tốn trong học máy dẫn đến việc phải cân nhắc khi lựa chọn thuật giải nào đại diện cho hướng học máy áp dụng vào bài tốn phân lớp câu hỏi trong tiếng Việt. Zhang [42] đã tiến hành thử nghiệm năm thuật tốn khác nhau trong hướng học máy khi xây dựng bộ phân lớp câu hỏi. Dựa trên kết thực nghiệm này, sẽ quyết định thuật tốn sử dụng trong hướng học máy. Thực nghiệm của Zhang như sau: a. Taxonomy của lớp câu hỏi Lớp cha Các lớp con ABBR Tĩm tắt, sự khai triển DESC Định nghĩa, mơ tả, lý do ENTY Động vật, cơ thể, màu sắc, sang tác, tiền tệ, ngơn ngữ, chữ viết, loại khác, thực vật, bệnh /thuốc, sự kiện, thực phẩm, ngơn ngữ, cơng cụ - phương tiện, sản phẩm, tơn giáo, thể thao, vật chất, ký hiệu, kỹ thuật, thuật ngữ, xe cộ, từ. HUM Nhĩm, cá thể, tên, tư cách LOC Thành phố, đất nước, núi, bang, loại khác NUM Mã, đếm, ngày, khoảng cách, tiền, thứ tự, khác, phần trăm-tỉ lệ, thời kỳ, tốc độ, nhiệt độ, kích cỡ, cân nặng Bảng 1. Taxonomy của tập lớp câu hỏi thử nghiệm của Zhang Bảng trên mơ tả tầng cao nhất của taxonomy câu hỏi, mỗi một lớp thuộc cột “chi tiết” mơ tả một loại câu hỏi riêng biệt. b. Tập câu hỏi cho taxonomy trên bao gồm các câu hỏi đã được gán nhãn được cung cấp bởi USC [11], UIUC [42] và TREC [14][13] [12]. Tập dữ liệu này được gán nhãn thủ cơng. Mỗi một câu hỏi chỉ thuộc một lớp nhất định. Tập đặc trưng lựa chọn bao gồm hai loại đặc trưng: (1) bag-of-words: biểu diễn văn bản/câu hỏi độc lập với ngơn ngữ và ngữ pháp. Mỗi một văn bản/câu hỏi được biểu diễn bẳng một tập các từ, tập từ này khơng xếp thứ tự. 29 (2) 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-grams là các ký tự liền kề nhau (chuỗi con) bắt đầu từ mẫu tự A. Vì vậy, khoảng cách n-grams trong văn bản ít hơn hoặc bằng |A|n. Đều này cho thấy số chiều của vectơ đặc trưng n- grams cĩ thể rất lớn thậm chí khi n cĩ giá trị vừa phải. Vector đặc trưng trích trọn được với mỗi câu hỏi thường là vector cĩ giạ trị nhị phân (các chiều thường mang giá trị 0 hoặc 1 – xuất hiện hoặc khơng xuất hiện) khi sử dụng hai kiểu đặc trưng trên. c. Kết quả của thí nghiệm Sau năm lần thí nghiệm với 5 tập dữ liệu cĩ số lượng câu hỏi khác nhau : 1.000, 2.000, 3.000, 4.000 và 5.500 câu. Kết quả thực nghiệm như sau (về độ chính xác): • Thí nghiệm trên tập lớp cha (năm lớp cha như ở bảng 1.0) o Khi chọn vector đặc trưng là bag-of-words Bảng 2. Độ chính xác trên năm phân lớp cha với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-words. Thuật tốn 1000 2000 3000 4000 5000 Láng giềng gần nhất 70.0% 73.6% 74.8% 74.8% 75.6% Nạve Bayes 53.8% 60.4% 74.2% 76.0% 77.4% Cây quyết định 78.8% 79.8% 82.0% 83.4% 84.2% SNoW 71.8% 73.4% 74.2% 78.2% 66.8% SVM 76.8% 83.4% 87.2% 87.4% 85.8% 30 o Khi sử dụng vertor đặc trưng là bag-of-Ngrams Bảng 3. Độ chính xác trên năm phân lớp Cha với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-Ngrams • Thí nghiệm trên tập lớp chi tiết (trong bảng 1.0) o Khi chọn vector đặc trưng là bag-of-words Bảng 4. Độ chính xác trên các phân lớp con với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-words. Thuật tốn 1000 2000 3000 4000 5000 Láng giềng gần nhất 72.0% 81.0% 79.8% 80.8% 79.8% Nạve Bayes 73.0% 79.2% 80.0% 81.8% 83.2% Cây quyết định 73.8% 82.6% 83.0% 84.6% 84.2% SNoW 59.8% 85.2% 80.6% 87.0% 86.6% SVM 77.6% 82.6% 84.8% 84.8% 87.4% Thuật tốn 1000 2000 3000 4000 5000 Láng giềng gần nhất 57.4% 62.8% 65.2% 67.2% 68.4% Nạve Bayes 48.8% 52.8% 56.6% 56.2% 58.4% Cây quyết định 67.0% 70.0% 73.6% 75.4% 77.0% SNoW 42.2% 66.2% 69.0% 66.6% 74.0% SVM 68.0% 75.0% 77.2% 77.4% 80.2% 31 o Khi sử dụng vertor đặc trưng là bag-of-Ngrams Bảng 5. Độ chính xác trên các phân lớp con với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-Ngrams Từ kết quả thực nghiệm trên, nhận thấy rằng: • Độ chính xác của phân lớp tỉ lệ với tập dữ liệu học • SVM mang lại độ chính xác cao hơn so với các phương pháp cịn lại. Đối với SVM độ chênh lệnh khi sử dụng tập đặc trưng là bag-of-words và tập đặc trưng bag-of-ngrams là khơng lớn. Như vậy, dựa trên kết quả thực nghiêm trên và một số thực nghiệm khác của Hacioglu [16] và Li [19]cĩ thể kết luận rằng đối với phân lớp câu hỏi theo phương pháp SVM là lựa chọn khá tốt so với các thuật tốn khác trong học máy. Phần thực nghiệm sử dụng SVM cho tập dữ liệu tiếng Việt sẽ được tình bày cụ thể ở Chương 4. 3.3.3 Hướng tiếp cận dựa trên mơ hình hình ngơn ngữ Chúng ta cĩ thể xem xét rất nhiều bài tốn trong lĩnh vực xử lý ngơn ngữ tự nhiên (Natural Language Processing - NLP) dưới dạng các bài tốn phân lớp với nhiệm vụ là ước lượng xác suất cĩ điều kiện p(a|b) của “lớp” a xuất hiện trong “ngữ cảnh” (context) b, hay nĩi cách khác là, ước lượng xác suất xuất hiện của a với điều kiện b. Ngữ cảnh trong các bài tốn xử lý ngơn ngữ tự nhiên thường bao gồm các từ và việc chọn ra ngữ cảnh phụ thuộc theo bài tốn đặt ra. Đối với một số bài tốn thì ngữ cảnh b cĩ thể là một từ đơn lẻ nhưng đối với một số bài tốn khác thì ngữ cảnh b cĩ thể chứa một số từ xung Thuật tốn 1000 2000 3000 4000 5000 Láng giềng gần nhất 59.4% 64.6% 67.2% 67.4% 68.6% Nạve Bayes 54.4% 58.4% 63.0% 65.0% 67.8% Cây quyết định 62.8% 72.2% 72.6% 73.0% 77.0% SNoW 44.0% 67.0% 75.0% 55.8% 75.8% SVM 65.0% 74.0% 74.8% 77.4% 79.2% 32 quanh hoặc các từ cùng với các nhãn cú pháp tương ứng. 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) . Hướng tiếp cận này là tiếp cận theo mơ hình ngơn ngữ LM. Ý tưởng cơ bản nhất của LM là : • Các phần của văn bản đều được sinh ra từ một mơ hình ngơn ngữ • Giữa hai phần văn bản bất kỳ, cĩ một độ đo thể hiện xác suất chúng cùng được sinh ra bởi một mơ hình ngơn ngữ. Trong phân lớp câu hỏi LM được sử dụng để tính xác suất của phân lớp câu hỏi C xuất hiện trong ngữ cảnh câu hỏi Q. Giả sử truy vấn Q là tập hợp của n từ w1,w2, …,wn. Xác suất Q và lớp C được sinh ra bởi cùng một mơ hình ngơn ngữ được tính theo cơng thức: ( ) 1 2| ( | ) ( | ) *...* ( | )nP Q C P w C P w C P w C= ∗ (*) Một mơ hình ngơn ngữ sẽ được tạo ra cho mỗi một lớp câu hỏi Ci (i=1,…,n). Mơ hình này xây dựng từ tập hợp các câu hỏi thuộc lớp C. Khi một câu hỏi Q tới, xác suất P(Q|Ci) sẽ được tính với tất cả các lớp câu hỏi Ci , Q sẽ được phân vào lớp Ci cĩ xác suất P(Q|Ci) lớn nhất. Thơng thường, để khi sử dụng mơ hình ngơn ngữ để tiến hành phân lớp các mẫu n-gram (chủ yếu là unigram và bigram) được sử dụng . Cơng thức (*) là dạng biểu diễn unigram. Bigram cĩ dạng biểu diễn như sau: ( ) 1 2 1 1| ( | ) ( | , w ) *...* ( | , )n nP Q C P w C P w C P w C w −= ∗ (**) Để xác định được xác suất ở (*) hoặc (**) phải tính được giá trị của từng xác suất thành phần ở vế phải: P(wi|C) (với i=1,…,n), một cách trực quan thì xác suất này phải tỉ lệ với số lần từ wi xuất hiện trong C. Ngồi ra, khi áp dụng LM phải cĩ biện pháp loại bỏ trường hợp xác suất P(Q|C) bằng khơng. Để loại bỏ tình trạng này cần áp dụng những kỹ thuật làm mịn các xác suất thành phần P(wi|C) sao cho minP(wi|C)>0. Các phương pháp làm mịn được tác giả Wei Li giới thiệu cụ thể trong tài liệu [36]. Sử dụng kỹ thuật LM cho phân lớp câu hỏi Wei Li[36] đạt được kết quả khá khả quan (độ chính xác khoảng 80%) khi sử dụng kết hợp hai mẫu unigram và bigram. Một kỹ thuật để nâng cao hiệu suất của LM đĩ là các mơ hình khi xây dựng được tích hợp với bộ phận nhận dạng thực thể tên (Named entity recognition-NE), bộ phận này sẽ nhận diện các thực thể thuộc: tên người, địa danh, số … một từ wi nếu được NE nhận diện, nĩ sẽ bị thay thể bằng tên dại diện cho lớp thực thể đĩ. Ví dụ với câu hỏi “Ai là 33 Ronaldo?” nếu “Ronaldo” được nhận dạng thuộc lớp bởi NE, thì câu hỏi sẽ chuyển thành dạnh “ai là ” theo đĩ, độ chính xác của LM sẽ được nâng cao . 3.3.3.1 Hướng tiếp cận Entropy cực đại Đố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) (được giới thiệu ở tài liệu [17] và [24]) 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 thì “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. 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. 34 Ở 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: ( ) { khi c c' và cp(d) true1cp,c ' 0 otherwisef c,d = == 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 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. 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 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 thoả 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) 35 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 thoả 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 chứng minh ở [28]): ( ) ( )∏ = = 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 – được đưa ra trong [7]; Thuật tốn IIS – Improved Iterative Scaling – được đưa ra trong [8] 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 ( ) ( )∑ ∑ ⎟⎠⎞⎜⎝⎛ λ= c ii i c,dfexpdZ 36 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. L-BFGS là thuật tốn sử dụng trong phần thử nghiệm với nguyên lý Entropy cực đại ở Chương 4. 37 Chương 4. Thực nghiệm và đánh giá 4.1 Dữ liệu của thực nghiệm Dữ liệu dùng để thử nghiệm cho bộ phân lớp câu hỏi Y tế tiếng Việt là các câu hỏi được lấy từ các trang sau Web: . Tập dữ liệu kiểm tra lấy từ báo và Tồn bộ dữ liệu của thử nghiệm đều được gán nhãn bằng tay. Các phân lớp của dữ liệu được thiết kế dựa trên Ontology Y tế đã được giới thiệu ở chương 2, mục 2.3 bao gồm 8 lớp như sau: STT Phân lớp Ký hiệu Số lượng câu hỏi 1 Benh B 413 2 dia_diem DD 43 3 Nguyen_nhan NN 114 4 trieu_chung TC 42 5 hoat_dong HD 314 6 thuc_pham TP 105 7 Thuoc TH 96 8 thoi_gian T 23 Tổng số 1150 Bảng 6.Tập dữ liệu huấn luyện Dữ liệu dùng cho huấn luyện cùng số lượng câu hỏi được mơ tả trong Bảng 6 bao gồm 1144 câu hỏi được lấy cân bằng theo các lớp, tuy nhiên cĩ một số lớp cĩ sự chênh lệch lớn là do chúng tơi nhận thấy rằng số lượng từ chuyên mơn của lớp đĩ và nhu cầu hỏi 38 trong lớp đấy khơng nhiều như các lớp khác nên khơng cần phải sử dụng một lượng câu hỏi quá lớn. Tập dữ liệu dùng để kiểm tra được mơ tả trong bảng 7, số lượng câu hỏi của mỗi lớp tỉ lệ với số lượng câu hỏi trong tập dữ liệu dùng để huấn luyện. STT Phân lớp Ký hiệu Số lượng câu hỏi 1 benh B 48 2 dia_diem DD 9 3 nguyen_nhan NN 20 4 trieu_chung TC 13 5 hoat_dong HD 38 6 thuc_pham TP 29 7 thuoc TH 31 8 thoi_gian T 6 Tổng số 194 Bảng 7. Tập dữ liệu kiểm tra 4.2 Thiết kế thử nghiệm Khĩa luận thử nghiệm theo hai thuật tốn Support Vector Machines và nguyên lý Entropy cực đại. a. Thiết lập thơng số cho SVM 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 [44], địi hỏi thiết lập một số thơng số cho chương trình, các thơng số này được lựa chọn qua nhiều lần thử nghiệm. Chi tiết các thơng số được trình bày trong bảng 8. 39 Tham số Giá trị Mơ tả -c 1.0 Giá trị chuyển đổi giữa lỗi của tập huấn luyện và độ lệch chuẩn -t 0 Loại hàm nhân của , 0 là lựa chọn hàm tuyến tính -w 3 Cấu trúc của thuật tốn học, 3 là lựa chọn thuật tốn nối ràng buộc đơi. Bảng 8. Tham số huấn luyện mơ hình SVM b. Thiết lập thơng số cho Entropy cực đại 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, X.H [43], việc sử dụng cũng địi hỏi thiết lập một số thơng số cho mơ hình. Các thơng số này cũng được lựa chọn qua nhiều lần thử nghiệm, chi tiết được mơ tả ở bảng 9. Tham số Giá trị Mơ tả numIterations 10 Số bước lặp trong quá trình huấn luyện cpRareThreshold 0 Các đặc trưng xuất hiện nhiều hơn số này thì sẽ khơng bị loại bỏ khỏi tập dữ liệu huấn luyện. fRareThreshold 0 Các mệnh đề mơ tả thơng tin ngữ cảnh phải xuất hiện nhiều hơn số này thì sẽ được dùng để xây dựng các đặc trưng. Bảng 9. Tham số huấn luyện mơ hình Entropy cực đại 4.3 Kết quả thực nghiệm a. Kết quả thực nghiệm với SVM Với SVM khi tiến hành thử nghiệm với tập dữ liệu tiếng Việt, sử dụng độ đo TF-IDF trên mẫu unigram, trong thời gian 1.56 giây cho kết quả khá thấp. Chi tiết kêt quả mơ tả ở bảng 10. Thuật tốn Thời gian Độ chính xác Tỉ lệ lỗi SVM 1.56 26% 58/148 Bảng 10. kết quả huấn luyện với SVM 40 b. Kết quả thực nghiệm với Entropy cực đại Tiến hành thử nghiệm trên tập dữ liệu huấn luyện với số lượng bước lặp là 10. Các kết quả thu được khá khả quan với thời gian khoảng 0.15giây/lần và được mơ tả trong một số bảng biểu và đồ thị được biểu diễn sau đây. Độ chính xác Độ hồi tưởng F1 Bước lặp Thời gian Avg1 Avg2 Avg1 Avg2 Avg1 Avg2 1 0.26 46.54 55.15 38.81 55.15 42.32 55.15 2 0.22 49.24 60.82 45.37 60.82 47.22 60.82 3 0.127 63.99 63.92 51.83 63.92 57.27 63.92 4 0.11 71.40 65.98 59.80 65.98 65.09 65.98 5 0.132 73.56 67.53 63.15 67.53 67.95 67.53 6 0.133 73.54 69.07 64.64 69.07 68.80 69.07 7 0.117 72.93 67.01 62.83 67.01 67.51 67.01 8 0.135 69.13 64.95 60.55 64.95 64.56 64.95 9 0.153 70.24 63.92 59.93 63.92 64.67 63.92 10 0.106 79.25 65.46 61.85 65.46 69.47 65.46 Trung bình 0.1493 66.982 64.381 56.876 64.381 61.486 64.381 Bảng 11. Kết quả 10 lần huấn luyện với Entropy cực đại Qua bảng trên, chúng tơi thấy kết quả khả quan nhất là ở bước lặp thứ 6 với độ đo F1 đạt 69.07% chi tiết về bước lặp này như sau: 41 Nhãn Độ chính xác Độ hồi tưởng F1 benh 65.57 83.33 73.39 hoat_dong 62.22 73.68 67.47 dia_diem 50.00 23.08 31.58 nguyen_nhan 80.00 88.89 84.21 thoi_gian 88.24 75.00 81.08 trieu_chung 100.00 50.00 66.67 thuoc 76.92 64.52 70.18 thuc_pham 65.38 58.62 61.82 Avg1 73.54 64.64 68.80 Avg2 69.07 69.07 69.07 Bảng 12. Kết quả của bước lặp thứ 6 Trong bảng kết quả trên thì kết quả của phân lớp địa_điểm rất kém với độ đo chính xác là 31.58% và tốt nhất là phân lớp nguyên_nhân với độ chính xác là 84.21%. 42 0 10 20 30 40 50 60 70 80 1 2 3 4 5 6 7 8 9 10 Bước lặp Đ ộ đo F 1 F1-Avg2 F1-Avg1 Hình 7. Đồ thị biểu diễn sự phụ thuộc của F1 vào số lần lặp 0 10 20 30 40 50 60 70 80 90 1 2 3 4 5 6 7 8 9 10 Bước lặp Đ ộ ch ín h xá c củ a ph ân lo ại Độ chính xác Độ hồi tưởng F1 Hình 8. Tổng hợp độ đo 10 lần huấn luyện 43 4.4 Đánh giá kết quả thực nghiệm Kết quả thực nghiệm thu được cho thấy cĩ sự chênh lệch rất lớn giữa hai phương pháp SVM và Entropy cực đại (SVM cĩ độ chính xác là 25% và Entropy cực đại là 70%) khi sử dụng cho bộ phân lớp câu hỏi tiếng Việt. Đâu là nguyên nhân dẫn đến sự chênh lệch này? a. Đối với thuật tốn SVM SVM khi áp dụng vào bộ phân lớp câu hỏi tiếng Anh cĩ độ chính xác rất cao (khoảng 80% – như trong các bài báo [16] và [42] cơng bố) nhưng khi sử dụng thuật tốn này cho bộ dữ liệu tiếng Việt độ chính xác bị giảm đáng kể. Nguyên nhân của sự sụt giảm này cĩ thể được lý giải theo cảm tính như sau: (1) Khĩa luận sử dụng tập dữ liệu khác so với tập dữ liệu của các tác giả Hacioglu [16] và Zhang [42] (2) Số lượng dữ liệu học chưa đủ lớn (1150 câu hỏi) chưa thể hiện hết được các đặc trưng của từng lớp câu hỏi. Khi tập dữ liệu dùng để huấn luyện tăng lên độ chính xác của thuật tốn cũng được nâng lên. (3) Cĩ sự khác biệt về vector đặc trưng sử dụng khi biểu diễn câu hỏi; nguyên nhân này cĩ thể là thứ yếu vì trong bài báo [42], tác giả Zhang cũng sử dụng TF IDF và mơ hình unigram để làm vector đặc trưng cho từng câu hỏi. b. Đối với nguyên lý Entropy cực đại Đối với tập dữ liệu học là 1150 câu hỏi cho 8 phân lớp cho kết quả khá khả quan về độ đo F1 là 69.07%. Mặt khác, do số lượng câu hỏi huấn luyện cho từng phân lớp cĩ sự chênh lệch dẫn đến khả năng đốn nhẫn của từng phân lớp cũng khác nhau. Ví dụ như lớp Bệnh cĩ số lượng câu hỏi là 413 trong khi lớp thời_gian cĩ số lượng câu hỏi là 23. Lý do của việc này là khi xảy ra sự mất cân bằng trong số lượng dữ liệu dùng để huấn luyện, trọng số của các đặc trưng cĩ ích chuyên biệt cho từng lớp sẽ khơng cao do đĩ mơ hình rất dễ đốn nhận nhầm. Để đảm bảo khả năng đốn nhận của các phân lớp cần bằng với nhau và khả năng đốn nhận tốt thì số lượng câu hỏi mẫu cho từng lớp cần phải tương đương nhau về mặt số lượng. Song song với đĩ là tập câu hỏi huấn luyện cần gia tăng thêm về số lượng, đảm bảo cung cấp đầu đủ các ràng buộc từ dữ liệu cho mơ hình. Như trong mục 3.3.3 đã trình bày, tư tưởng chủ đạo của nguyên lý cực đại Entropy là thay vì thêm vào các ràng buộc mới, 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. Điều này là khác với 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. Cho nên khi tập liệu khơng cĩ số lượng quá lớn và mỗi một tài liệu chỉ chứa ít đặc trưng (như câu hỏi) làm cho sự phân lớp của SVM bị giảm sút trong khi mơ hình của phân lớp của nguyên lý cực đại Entropy vấn được bảo đảm. 44 Từ những kết quả thực nghiệm trên cho thấy khi xây dựng bộ phân lớp câu hỏi tiếng Việt thuật tốn nguyên lý Entropy cực đại tỏ ra thích hợp hơn so với các thuật tốn khác. 45 Kết luận Nhu cầu xây dựng một hệ thống tìm kiếm ngữ nghĩa cho từng lĩnh vực trong đời sống ngày càng trở cấp thiết, trong đĩ vấn đề xây dựng hai module phân lớp câu hỏi và mạng ngữ nghĩa chịu ảnh hưởng bởi đặc trưng riêng của từng ngơn ngữ là phần quan trong trong quá trình xây dựng một hệ thống tìm kiếm ngữ nghĩa . Sự đa dạng của các thuật tốn phân loại dữ liệu nĩi chung và phân lớp câu hỏi nĩi riêng khiến cho việc lựa chọn thuật tốn để xây dựng module phân lớp câu hỏi cho từng ngơn ngữ tở nên khĩ khăn hơn. Khĩa luận này tiếp cận các vấn đề nĩi trên và nghiên cứu các thuật tốn phổ biến hiện nay cho phân lớp câu hỏi, từ đĩ đưa ra phương pháp và thuật tốn áp dụng vào tiếng Việt . Khĩa luận đã đạt được những kết quả: • Phân tích các vấn đề xung quanh bài tốn xây dựng một hệ thống tìm kiếm ngữ nghĩa • Chỉ ra các module chịu ảnh hưởng bởi đặc trưng ngơn ngữ và phân tích phương pháp xây dựng các module này. • Khảo sát các thuật tốn phân lớp câu hỏi và lựa chọn thuật tốn tốt nhất khi áp dụng cho tiếng Việt • Xây dựng module phân lớp câu hỏi Y tế trong tiếng Việt. Do giới hạn về thời gian cũng như kiến thức của tác giả cho nên hiệu quả module phân lớp câu hỏi cho tiếng Việt chưa thực sự cao. Hạn chế này cần được tiếp tục nghiên cứu và cải tiến qua đĩ để khẳng định tính hiệu quả của phương pháp chỉ ra. 46 Tài liệu tham khảo Tiếng Việt [1] Lê Diệu Thu, Trần Thị Ngân, “Xây dựng Ontology nhằm hỗ trợ tìm kiếm ngữ nghĩa trong lĩnh vực Y tế”, Cơng trình sinh viên nghiên cứu khoa học, Đại học Cơng nghệ, ĐHQGHN, 2008. [2] Nguyễn Thị Hương Thảo, “Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng”, Khĩa luận tốt nghiệp đại học, Đại học Cơng nghệ, ĐHQGHN, 2006. [3] Trung tâm ngơn ngữ học Việt Nam. “Đặc điểm tiếng Việt”, [4] VN-KIM , Đại học Bách khoa, ĐHQG Thành Phố Hồ chí Minh Tiếng Anh [5] Clocksin W. F. and Mellish C. S., “Programming in Prolog”, Springer-Verlag, 1981. [6] D. Roth. “Learning to Resolve Natural Language Ambiguities: A Unified Approach.” Proceedings of AAAI'98: 806-813, Madison, WI, USA, Jul 1998. [7] Darroch, J. and Ratcliff, D. “Generalized iterative scaling for log-linear models”. Annals Mathematical Statistics, 43(5):1470–1480, 1972. [8] Della Pietra, S., Della Pietra, V. and Lafferty, J. “Inducing features of random fields”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):380–393, 1997. [9] Description logic, [10] Dieter E. Jenz “Ontology-Based Business Process Management: The Vision Statement”, White Paper, Jenz and Partner GmbH, 2003 [11] E. Hovy, L. Gerber, U. Hermjakob, C. Lin, and D. Ravichandran. “Towards Semantics-based Answer Pinpointing”. Proceedings of the DARPA Human Language Technology conference (HLT), San Diego, CA,1999 [12] E. Voorhees. “Overview of the TREC 2001 Question Answering Track”. Proceedings of the 10th Text Retrieval Conference (TREC10): 157-165, NIST, Gaithersburg, MD, 2001. [13] E. Voorhees. Overview of the TREC-9 Question Answering Track. Proceedings of the 9th Text Retrieval Conference (TREC9): 71-80, NIST, Gaithersburg, MD, 2000. [14] E. Voorhees. The TREC-8 Question Answering Track Report. Proceedings of the 8th Text Retrieval Conference (TREC8): 77-82, NIST, Gaithersburg, MD, 1999. 47 [15] Jonathan Brown, “Entity-Tagged Language Models for Question Classification in a QA System”, IR Lab project, 2004. 743s04/jonbrown/Brown-IRLab.pdf [16] Kadri Hacioglu and Wayne Ward. "Question Classification with Support Vector Machines and Error Correcting Codes". Proceedings of HLT-NAACL 2003:28-30, Edmonton, Alberta, Canada, May 2003. [17] K. Nigam, J. Lafferty, and A. McCallum, "Using maximunm Entropy for text classification", Proceeding of the 16th International Joint Conference Workshop on Machine Learning for Information Filtering: 61-67 Stockholm, Sweden, 1999. [18] Kincho H. Law, “Ontology: Basic Definitions and a Brief Introduction”, TN-2007- 03. NEESit – Workshops 2007. [19] Li, X. & Roth, D. “Learning Question Classifiers”, Proceedings of the 19th International Conference on Computational Linguistics (COLING):556–562, 2002. [20] LIU Yi, ZHENG Y F. “One-against-all multi-Class SVM classification using reliability measures”.Proceedings of the 2005 International Joint Conference on Neural Networks Montreal,Canada, 2005. [21] Maria Vargas-Vera, Enrico Motta, John Domingue: “AQUA: An Ontology-Driven Question Answering System”, New Directions in Question Answering:53-57, 2003. [22] McCallum and K. Nigam. “A Comparison of Event Models for Nạve Bayes Text Classification”, AAAI-98Workshop on Learning for Text Categorization, 1998. [23] N. Guarino (ed.), “Formal Ontology in Information Systems”. Proceedings of FOIS’98:3-15, Trento, Italy, 6-8 June 1998. Amsterdam, IOS Press. [24] Nguyen Viet Cuong, Nguyen Thi Thuy Linh Ha, Quang Thuy and Phan Xuan Hieu (2006). A Maximum Entropy Model for Text Classification. The International Conference on Internet Information Retrieval 2006:134-139, Hankuk Aviation University, December 6, 2006, Goyang-si, Korea. [25] Noy, N.F., and McGuinness, D.L. “Ontology Development 101: A Guide to Creating Your First Ontology SMI”, Technical report SMI-2001-0880 (2001), Stanford University. [26] Pierre Baldi, Paolo Frasconi, Padhraic Smyth. “Modeling the Internet and the Web: Probabilistic Methods and Algorithms”, John Wiley and Sons, 2003. [27] R.Guha, Rob McCool, Eric Miller. “Semantic Search”, 48 [28] Ratnaparkhi, A. “A simple introduction to maximum Entropy models for natural language processing”. Technical Report 97-08, Institute for Research in Cognitive Science, University of Pennsylvania, 1997. [29] S.Cohen , Mamou, J., Kanza, Y., Sagiv, Y.: “ Xsearch: A semantic search engine for xml”. In: Proceedings of of the 29th VLDB Conference, Berlin, Germany. (2003) [30] S Decker, F van Harmelen, J Broekstra, M Erdmann, Dieter Fensel, Ian Horrocks, Michel Klein, Sergey Melnik. “The Semantic Web - on the respective Roles of XML and RDF”, IEEE Internet Computing, 4(5):63-74, 2000. [31] Soumen Chakrabarti. “Mining the Web: discovering knowledge from hypertext data”, Morgan Kaufmann Publishers, 2003. [32] T. Mitchell. “Machine Learning”, McGraw Hill, New York,1997. [33] “Taxonomy”, [34] Tim Berners-Lee, “Semantic Web Road map”, [35] Van Durme, B., Huang, Y., Kupsc, A. and Nyberg, E. "Towards Light Semantic Processing for Question Answering", HLT/NAACL Workshop on Text Meaning, 2003, [36] W Li “Question Classification Using Language Modeling” – Technical report Center for Intelligent Information Retrieval Department of Computer Science University of Massachusetts, Amherst, MA 01003, 2002 [37] W3C, Extensible Markup Language [38] W3C, OWL Web Ontology Language Overview, features/ [39] W3C, Abstract Syntax (Normative) RDF concepts/#section-Graph-syntax [40] W3C, Semantic Web Activity [41] Y. Yang and X. Liu. A Re-examination of Text Categorization Methods. In Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’99), trang 42-49, 1999. [42] Zhang, D. and Lee, W.S. “Question Classification using Support Vector Machines” , In Proceedings of SIGIR 2003. [43] Phan, X.H, “JTextPro: A Java-based Text Processing Toolkit”, [44] Thorsten Joachims, SVM multiclass Multi-Class Support Vector Machine, Cornell University Department of Computer Science.