Đề tài Phân giải nhập nhằng thực thể có tên dựa trên các ontology đóng và mở

ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA Nguyễn Thanh Hiên PHÂN GIẢI NHẬP NHẰNG THỰC THỂ CĨ TÊN DỰA TRÊN CÁC ONTOLOGY ĐĨNG VÀ MỞ Chuyên ngành: Khoa học Máy tính Mã số: 62.48.01.01 LUẬN ÁN TIẾN SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. CAO HỒNG TRỤ TP. HCM - NĂM 2010 i LỜI CAM ĐOAN Tơi cam đoan rằng nội dung của luận án này là kết quả nghiên cứu của bản thân. Tất cả những tham khảo từ các nghiên cứu liên quan điều được nêu rõ nguồn gốc một cách rõ ràng từ danh mục tài liệu tham khảo được đề cập ở phần sau của luận án. Những đĩng gĩp trong luận án là kết quả nghiên cứu của tác giả đã được cơng bố trong các bài báo của tác giả ở phần sau của luận án và chưa được cơng bố trong bất kỳ cơng trình khoa học nào khác. Tác giả luận án Nguyễn Thanh Hiên ii LỜI CẢM ƠN Tơi muốn bày tỏ ở đây lời tri ân sâu sắc gởi đến thầy hướng dẫn của tơi, PGS. TS. Cao Hồng Trụ. Thầy đã tận tình chỉ bảo tơi từ những ngày đầu tiếp cận con đường khoa học. Thầy đã dạy tơi từ những việc tưởng chừng đơn giản như cách thức để thu thập các tài liệu liên quan, đến khả năng tư duy cĩ phê phán và sự hồi nghi cần thiết trong hoạt động nghiên cứu. Sự tận tình hướng dẫn, cộng với sự động viên, khích lệ thường xuyên của Thầy đã thật sự đánh thức trong tơi những khả năng tiềm ẩn, nếu khơng luận án này đã khơng thể hồn thành. Sự cẩn thận, tỉ mỉ, kiên nhẫn và nghiêm túc trong cơng việc là những đức tính mà Thầy luơn nhắc nhở tơi. Những gì Thầy dạy tơi đã ảnh hưởng sâu sắc đến cá nhân tơi, và sẽ cĩ tác động lâu dài đến cuộc sống, sự nghiệp và tương lai của tơi. Tơi tin rằng, bằng những lời lẽ thơng thường sẽ khơng đủ để chuyển tải hết lịng biết ơn với những gì Thầy đã dạy tơi. Dù vậy, tơi cũng muốn viết ra đây, và gởi đến Thầy, lời cảm ơn chân thành nhất. Em cảm ơn Thầy! Tơi cũng muốn bày tỏ lịng biết ơn đối với tập thể các thầy cơ Khoa Khoa học và Kỹ thuật máy tính, Trường Đại học Bách Khoa Tp. HCM, nơi tơi học tập và gắn bĩ hơn mười năm qua, tính cả thời gian tơi học đại học và làm luận văn thạc sĩ. Các thầy cơ luơn tạo điều kiện để tơi hồn thành tốt cơng việc của mình, và sự dạy dỗ của quí thầy cơ đã giúp tơi trưởng thành. Xin chân thành cảm ơn quí thầy cơ trong Khoa Khoa học và Kỹ thuật máy tính. Tơi cũng chân thành cảm ơn sự hỗ trợ và giúp đỡ nhiệt thành của Phịng Quản lý Sau Đại học, Trường Đại học Bách Khoa Tp. HCM trong thời gian tơi thực hiện luận án này. Cảm ơn Ban giám hiệu Trường Đại học Bách Khoa Tp. HCM, Phịng Khoa học Cơng nghệ & Dự án đã xét duyệt cho tơi thực hiện đề tài nghiên cứu cấp trường, hỗ trợ tài chính để trang trải một phần kinh phí học tập và nghiên cứu của tơi trong thời gian qua. Tơi chân thành cảm ơn Tiến sĩ Lê Vinh Danh, Hiệu trưởng Trường Đại học Tơn Đức Thắng, đã động viên và tạo mọi điều kiện thuận lợi cho tơi hồn thành luận án này. Cảm ơn các anh chị trong Phịng Điện tốn và Thơng tin tư liệu, Trường Đại học Tơn Đức Thắng, đã nhiệt tình giúp đỡ tơi trong thời gian vừa qua. Cuối cùng, chân thành cảm ơn người thân, bạn bè luơn bên cạnh động viên, hỗ trợ về mặt tinh thần để tơi vượt qua khĩ khăn và hồn thành tốt luận án. iii TĨM TẮT Thực thể cĩ tên là những thực thể cĩ thể được tham khảo đến bằng tên riêng, như con người, tổ chức, hoặc nơi chốn. Phân giải nhập nhằng thực thể cĩ tên là nhằm ánh xạ mỗi tên trong một văn bản vào một thực thể trong một nguồn tri thức cho trước. Nổi lên gần đây như là một bài tốn đầy thách thức, nhưng cĩ nhiều ý nghĩa trong việc hiện thực hĩa Web cĩ ngữ nghĩa, cũng như phát triển nâng cao các ứng dụng xử lý ngơn ngữ tự nhiên, phân giải nhập nhằng thực thể cĩ tên đã thu hút sự quan tâm của nhiều nhĩm nghiên cứu khắp thế giới. Luận án đề xuất ba phương pháp cho bài tốn này, trong đĩ nghiên cứu sâu ba yếu tố quan trọng ảnh hưởng đến hiệu quả phân giải nhập nhằng là các nguồn tri thức sử dụng, đặc trưng biểu diễn thực thể, và mơ hình phân giải nhập nhằng. Các nguồn tri thức được khai thác là các ontology đĩng và Wikipedia. Các ontology đĩng được xây dựng bởi các chuyên gia theo hướng tiếp cận từ trên xuống, với các khái niệm cĩ quan hệ thứ bậc dựa trên một tập từ vựng cĩ kiểm sốt và các ràng buộc chặt chẽ. Wikipedia, xem như một ontology mở, được xây dựng bởi những người tình nguyện theo hướng tiếp cận từ dưới lên, với các khái niệm được hình thành từ một tập từ vựng tự do và các thoả thuận mang tính cộng đồng. Các đặc trưng được nghiên cứu là tên của các thực thể đồng xuất hiện, định danh của các thực thể đã được xác định, và các từ cùng với các cụm từ xuất hiện xung quanh tên đang được xem xét và xung quanh các tên là đồng tham chiếu với tên đĩ trong văn bản. Ngồi ra luận án cũng khai thác vị trí xuất hiện, chiều dài của các tên, và tên thường dùng của các thực thể. Luận án đề xuất ba mơ hình phân giải nhập nhằng tương ứng với ba phương pháp nĩi trên là: (i) mơ hình dựa trên heuristic; (ii) mơ hình dựa trên thống kê; và (iii) mơ hình lai - kết hợp heuristic và thống kê. Điểm mới chung của ba phương pháp là phân giải nhập nhằng theo một quá trình lặp cải thiện dần, trong đĩ bao gồm một số bước lặp. Thực thể được xác định tại mỗi bước lặp sẽ được sử dụng để phân giải nhập nhằng các thực thể cịn lại ở các bước lặp tiếp theo. Các thí nghiệm được thực hiện để đánh giá và chứng tỏ tính hiệu quả của các phương pháp được đề xuất. Luận án cũng nghiên cứu xử lý các trường hợp khi mà các tên trong văn bản chỉ được nhận ra bán phần và thực thể được đề cập đến trong văn bản nằm ngồi nguồn tri thức sử dụng, đồng thời đề xuất các độ đo hiệu quả phân giải nhập nhằng mới tương ứng. iv Abstract Named entities are those that are referred to by names such as people, organizations, or locations. Named entity disambiguation is a problem that aims at mapping entity names in a text to the right referents in a given source of knowledge. Having been emerging in recent years as a challenging problem, but significant to realization of the semantic web, as well as advanced development of natural language processing applications, named entity disambiguation has attracted much attention by researchers all over the world. This thesis proposes three methods for disambiguating named entities, and rigoruously investigates the three important factors affecting disambiguation performance, namely, employed knowledge sources, named entity representation features, and disambiguation models. The knowledge sources exploited are close ontologies and Wikipedia. Close ontolo- gies are built by experts following a top-down approach, with a hierarchy of concepts based on a controlled vocabulary and strict constraints. Wikipedia, considered as an open ontology, is built by volunteers following a bottom-up approach, with concepts formed by a free vocabulary and community agreements. The investigated features are entity names, identifiers of resolved entities, and words together with phrases surrounding a target name and surrounding names that are coreferential with that target name. Besides, the thesis ex- ploits occurrence positions and lengths of names, and main alias of entities. This thesis proposes three models corresponding to the three above-mentioned methods: (i) a heuris- tic-based model; (ii) a statistical model; and (iii) a hybrid model, combining heuristics and statistics. The common novelty of the proposed methods is disambiguating named entities itera- tively and incrementally, including several iterative steps. Those named entities that are resolved in each iterative step will be used to disambiguate the remaining ones in the next iterative steps. Experiments are conducted to evaluate and show the advantages of the pro- posed methods. Besides, this thesis deals with the cases when entity names in text are par- tially recognized and entities referred to in text are outside an employed knowledge source, as well as proposes new corresponding disambiguation performance measures. v MỤC LỤC Lời cam đoan ............................................................................................................................ i  Lời cảm ơn ............................................................................................................................... ii  Tĩm tắt .................................................................................................................................... iii  Abstract................................................................................................................................... iv  Mục lục..................................................................................................................................... v  Danh mục các bảng ............................................................................................................... vii  Danh mục các hình ................................................................................................................ ix  Danh mục các giải thuật ......................................................................................................... x  Danh mục thuật ngữ viết tắt ................................................................................................. xi  Chương 1: GIỚI THIỆU ........................................................................................................ 1  1.1  Lịch sử và động cơ nghiên cứu ................................................................................. 1  1.2  Bài tốn và phạm vi ................................................................................................ 15  1.3  Phương pháp luận đề xuất ....................................................................................... 17  1.4  Những đĩng gĩp chính của luận án ........................................................................ 24  1.5  Cấu trúc của luận án................................................................................................ 26  Chương 2: NỀN TẢNG KIẾN THỨC ................................................................................ 28  2.1  Giới thiệu ................................................................................................................ 28  2.2  Ontology ................................................................................................................. 29  2.3  Wikipedia ................................................................................................................ 36  2.4  Mơ hình khơng gian véctơ ...................................................................................... 45  2.5  Nhận dạng thực thể cĩ tên ...................................................................................... 46  2.6  Phân giải đồng tham chiếu trong một văn bản........................................................ 51  2.7  Phân giải nhập nhằng .............................................................................................. 59  vi 2.8  Kết luận ................................................................................................................... 72  Chương 3: PHÂN GIẢI NHẬP NHẰNG DỰA TRÊN ONTOLOGY ............................. 74  3.1  Giới thiệu ................................................................................................................ 74  3.2  Phân hạng ứng viên dựa trên ontology ................................................................... 75  3.3  Các độ đo hiệu quả mới .......................................................................................... 80  3.4  Thí nghiệm và đánh giá .......................................................................................... 84  3.5  Kết luận ................................................................................................................... 91  Chương 4: PHÂN GIẢI NHẬP NHẰNG DỰA TRÊN ONTOLOGY ĐƯỢC LÀM GIÀU ...................................................................................................................................... 93  4.1  Giới thiệu ................................................................................................................ 93  4.2  Mơ hình phân hạng ứng viên dựa trên thống kê ..................................................... 95  4.3  Làm giàu ontology ................................................................................................ 106  4.4  Thí nghiệm và đánh giá ........................................................................................ 110  4.5  Kết luận ................................................................................................................. 111  Chương 5: PHÂN GIẢI NHẬP NHẰNG DỰA TRÊN WIKIPEDIA ............................ 113  5.1  Giới thiệu .............................................................................................................. 113  5.2  Phương pháp lai .................................................................................................... 116  5.3  Thí nghiệm và đánh giá ........................................................................................ 125  5.4  Kết luận ................................................................................................................. 130  Chương 6: TỔNG KẾT ...................................................................................................... 132  6.1  Tĩm tắt .................................................................................................................. 132  6.2  Hướng nghiên cứu mở rộng .................................................................................. 135  CÁC CƠNG TRÌNH CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN ........................... 137  TÀI LIỆU THAM KHẢO .................................................................................................. 138  vii DANH MỤC CÁC BẢNG Bảng 2.1: Số liệu thống kê về các trang, thể loại và liên kết của các trang trong Wikipedia ......................................................................................................... 45  Bảng 2.2: Các loại trả lời để đánh giá một hệ thống nhận dạng thực thể cĩ tên ............... 49  Bảng 2.3: Kết quả phân giải đồng tham chiếu tên riêng tiếng Việt .................................. 59  Bảng 2.4: Minh họa tập dữ liệu huấn luyện của Bunescu và Paşca (2006) ...................... 66  Bảng 2.5: Minh họa đánh giá hiệu quả phân giải nhập nhằng của một phương pháp phân giải nhập nhằng các vùng địa lý (Leidner, 2007). ................................... 71  Bảng 3.1: Định nghĩa một ánh xạ là đúng hoặc sai cho một tên trong văn bản ................ 82  Bảng 3.2: Minh hoạ cách tính độ chính xác, độ đầy đủ và độ F ánh xạ ........................... 84  Bảng 3.3: Số lần xuất hiện của (“Georgia”, Location) trong tập dữ liệu De1.................... 85  Bảng 3.4: Số lần xuất hiện của (“Smith”, Person) trong tập dữ liệu De1 .......................... 86  Bảng 3.5: Kết quả phân giải nhập nhằng cho (“Georgia”, Location) ............................... 86  Bảng 3.6: Kết quả phân giải nhập nhằng cho (“Smith”, Person) ...................................... 87  Bảng 3.7: Kết quả phân giải nhập nhằng của OntoNEON trên tập Dv sử dụng ontology của VN-KIM. .................................................................................... 87  Bảng 3.8: Độ chính xác và độ đầy đủ ánh xạ của VN-KIM và OntoNEON trên tập dữ liệu Dv. .............................................................................................................. 88  Bảng 4.1: Thơng tin về thực thể trong Wikipedia cĩ một trong các tên “John McCarthy”, “John Williams”, “Georgia”, hoặc “Columbia” và số lần được đề cập đến trong tập dữ liệu De2. .................................................................... 101  Bảng 4.2: Thơng tin về số lần xuất hiện của các tên đề cập đến các thực thể cĩ một trong bốn tên “John McCarthy”, “John Williams”, “Georgia”, hoặc “Columbia” và số lượng ánh xạ được thực hiện bởi phương pháp của chúng tơi. ................................................................................................................... 102  viii Bảng 4.3: Độ chính xác và độ đầy đủ ánh xạ được tính tốn cho các tên “John McCarthy” và “John Williams”. .................................................................... 103  Bảng 4.4: Độ chính xác và độ đầy đủ ánh xạ được tính tốn cho các tên “Georgia” và “Columbia”. .................................................................................................... 104  Bảng 4.5: Độ chính xác và độ đầy đủ ánh xạ được tính trung bình cho các tên “John McCarthy”, “John Williams”, “Georgia”, và “Columbia”. ............................ 105  Bảng 4.6: Thống kê lỗi khi khơng sử dụng và sử dụng định danh của các thực thể như các đặc trưng. ................................................................................................. 106  Bảng 4.7: Thơng tin về số lần xuất hiện của các tên đề cập đến các thực thể cĩ một trong hai tên “Georgia”, hoặc “Columbia” và số lượng ánh xạ được thực hiện bởi phương pháp NOW. ......................................................................... 110  Bảng 4.8: Kết quả thực hiện phân giải nhập nhằng của NOW trên tập dữ liệu với “Georgia” và “Columbia”. ............................................................................. 111  Bảng 5.1: Thơng tin về sự xuất hiện của các tên trong tập dữ liệu De3 ............................ 126  Bảng 5.2: Thơng tin về sự xuất hiện của các tên trong tập dữ liệu De31 .......................... 127  Bảng 5.3: Độ chính xác và độ đầy đủ ánh xạ sau khi thực thi Giải thuật 5.1 trên tập dữ liệu De32 .......................................................................................................... 128  Bảng 5.4: Độ chính xác và độ đầy đủ ánh xạ sau khi thực thi Giải thuật 5.1 trên tập dữ liệu De31 .......................................................................................................... 129  ix DANH MỤC CÁC HÌNH Hình 1.1: Một mơ hình phân giải nhập nhằng tiêu biểu ................................................... 13  Hình 1.2: Một ví dụ của phân giải nhập nhằng thực thể cĩ tên ........................................ 15  Hình 2.1: Một số lớp xử lý của một ứng dụng rút trích thơng tin ..................................... 28  Hình 2.2: VN-KIM xử lý và chú thích các thực thể cĩ tên trên một trang web tiếng Việt ................................................................................................................... 33  Hình 2.3: Chú thích ngữ nghĩa .......................................................................................... 33  Hình 2.4: RDF biểu diễn mối quan hệ giữa các thực thể trong cơ sở tri thức của VN- KIM .................................................................................................................. 34  Hình 2.5: Một mơ hình xử lý của một động cơ rút trích thơng tin dựa trên GATE .......... 35  Hình 2.6: Một trang thực thể trong Wikipedia tiếng Việt ................................................. 38  Hình 2.7: Minh họa các mối liên kết giữa các trang trong Wikipedia .............................. 39  Hình 2.8: Minh họa hệ thống thể loại của Wikipedia ....................................................... 40  Hình 2.9: Một phần đồ thị các thể loại của thực thể Anna Maria Mozart ............... 41  Hình 2.10: Biểu diễn thực thể China trong Wikipedia tiếng Anh .................................... 41  Hình 2.11: Minh họa một phần trang phân giải nhập nhằng cho tên “John McCarthy” .... 42  Hình 2.12: Luật nhận biết tên người bằng tiếng Anh được viết đảo ngược của GATE ..... 49  Hình 2.13: Minh họa các chuỗi đồng tham chiếu ............................................................... 51  Hình 5.1: Minh họa các đặc trưng rút trích được từ một đoạn văn bản mẫu ................... 117  Hình 5.2: Một phần trang phân giải nhập nhằng của tên “Atlanta”. ................................ 120  x DANH MỤC CÁC GIẢI THUẬT Giải thuật 1.1: Phân giải nhập nhằng lặp cải thiện dần ...................................................... 19  Giải thuật 2.1: Phân giải đồng tham chiếu tên tiếng Việt .................................................. 57  Giải thuật 3.1: Phân giải nhập nhằng dựa trên ontology (OntoNEON) ............................. 79  Giải thuật 4.1: Phân hạng ứng viên dựa trên thống kê ....................................................... 99  Giải thuật 4.2: Phân giải nhập nhằng lặp cải thiện dần dựa trên thống kê (NOW) ......... 100  Giải thuật 4.3: Làm giàu thơng tin mơ tả một thực thể trong một ontology ङ ................ 109  Giải thuật 5.1: Phân giải nhập nhằng kết hợp heuristic và thống kê (WIN) .................... 124  xi DANH MỤC THUẬT NGỮ VIẾT TẮT Thuật Diễn giải tiếng Anh Diễn giải tiếng Việt IE Information Extraction Rút trích thơng tin IR Information Retrieval Truy hồi thơng tin NLP Natural Language Processing Xử lý ngơn ngữ tự nhiên NE Named Entity Thực thể cĩ tên SW Semantic Web Web cĩ ngữ nghĩa KB Knowledge Base Cơ sở tri thức NER Named Entity Recognition Nhận dạng thực thể cĩ tên NED Named Entity Disambiguation Phân giải nhập nhằng thực thể cĩ tên WPS Web People Search Tìm kiếm con người trên Web WSD Word Sense Disambiguation Phân giải nhập nhằng ngữ nghĩa từ vựng TR Toponym Resolution Phân giải nhập nhằng các vùng địa lý SVM Suport Vector Machine Máy véctơ hỗ trợ MP Mapping-Precision Độ chính xác ánh xạ MR Mapping-Recall Độ đầy đủ ánh xạ MF Mapping-F-Measure Độ F ánh xạ EN Entity Name Tên thực thể LW Local Word Từ cục bộ CW Coreferential Word Từ đồng tham chiếu ID Identifier Định danh thực thể ET Title of Entity page Nhan đề trang thực thể RT Title of Redirect page Nhan đề trang đổi hướng CL Category Label Nhãn thể loại OL Outgoing link label Nhãn liên kết ra IL Ingoing link label Nhãn liên kết vào 1 Chương 1 GIỚI THIỆU 1.1 Lịch sử và động cơ nghiên cứu Internet ngày nay đã trở thành một trong những kênh lưu trữ và truyền tải thơng tin lớn nhất của nhân loại. Sự ra đời và phát triển nhanh chĩng của World Wide Web (gọi tắt là Web) đã tạo điều kiện thuận lợi cho việc phân phối và chia sẻ thơng tin trên Internet, do đĩ dẫn đến bùng nổ thơng tin cả về số lượng, chất lượng và các chủ đề thơng tin trên đĩ. Tuy nhiên, đa phần nội dung thơng tin trên các trang web đều được thể hiện dưới dạng ngơn ngữ tự nhiên và được định dạng theo ngơn ngữ HTML, một ngơn ngữ thiếu khả năng diễn đạt ngữ nghĩa về các khái niệm và các đối tượng được trình bày trong các trang web. Do vậy, phần lớn nội dung thơng tin trên các trang web hiện nay chỉ phù hợp cho con người đọc hiểu. Mục tiêu khai thác hiệu quả các nguồn thơng tin trên Web đã thúc đẩy sự phát triển các ứng dụng xử lý văn bản tự động, trong đĩ các chủ đề nghiên cứu như Rút trích thơng tin (Information Extraction – IE), Truy hồi thơng tin (Information Retrieval – IR), Hỏi đáp (Question Answering), Dịch máy (Machine Translation), Tĩm lược văn bản (Text Summarization), và Xử lý ngơn ngữ tự nhiên (Natural Language Processing - NLP) nĩi chung, đã thu hút sự quan tâm của nhiều nhà nghiên cứu. Để máy tính cĩ thể hiểu ngữ nghĩa của một văn bản, một tiếp cận hợp lý hiện nay là thay vì cố gắng hiểu một cách đầy đủ ngữ nghĩa của văn bản, chúng ta rút trích các thực thể và các khái niệm chính yếu xuất hiện trong đĩ dựa vào một nguồn tri thức về các thực 2 Chương 1.Giới thiệu thể và khái niệm phổ biến trong thế giới thực, ví dụ như Wikipedia1. Từ các thực thể và khái niệm rút trích được, các hệ thống khai thác dữ liệu cĩ thể được xây dựng để khai phá các lớp tri thức mới, ví dụ như mối quan hệ giữa các thực thể, nhằm hướng đến hiểu đầy đủ ngữ nghĩa của văn bản. Trong hơn một thập niên qua, cũng nhằm hướng đến giúp máy tính hiểu ngữ nghĩa của các văn bản, các chủ đề nghiên cứu lấy thực thể cĩ tên (Named Entity – NE) làm trung tâm, như nhận biết và phân lớp các thực thể cĩ tên (Nadeau và Sekine, 2007), phân giải nhập nhằng các thực thể cĩ tên (Bunescu và Paşca, 2006; Sarmento và CS2, 2009), rút trích tự động quan hệ của các thực thể cĩ tên (Bunescu, 2007), . . . đã nhận được sự quan tâm nghiên cứu rộng rãi. Thực thể cĩ tên là những thực thể cĩ thể được tham chiếu đến bằng tên, như con người, tổ chức, nơi chốn; kể cả biểu thức thời gian, biểu thức số, giá trị tiền tệ và phần trăm (Chinchor và Robinson, 1997). Những năm gần đây thực thể cĩ tên cũng đã trở thành đối tượng chính yếu trong việc nghiên cứu phát triển Web cĩ ngữ nghĩa (Berners- Lee và CS, 2001). Đĩ là bởi vì các thực thể cĩ tên rất phổ biến trên các trang web. Hơn nữa, thơng tin và ngữ nghĩa được chuyển tải trong nội dung của nhiều trang web tập trung xoay quanh các thực thể cĩ tên và các mối quan hệ ngữ nghĩa được diễn đạt tường minh hoặc ngầm định giữa chúng. Web cĩ ngữ nghĩa (Semantic Web – SW) là Web mà thơng tin trên đĩ khơng chỉ con người mới cĩ thể đọc hiểu mà máy tính cũng cĩ thể hiểu và xử lý chúng một cách tự động. Berners-Lee phác họa SW đầu tiên vào năm 1999 (Berners-Lee, 1999). Berners-Lee và CS (2001) trong một bài báo trên Scientific American đã mơ tả một sự tiến hĩa từ Web của các tài liệu (Web of documents) để con người đọc hiểu, sang Web của dữ liệu (Web of data) mà thơng tin trên đĩ đã được bổ sung ngữ nghĩa để máy cĩ thể hiểu và thao tác. Thật vậy, SW là một sự tiến hĩa mở rộng của Web hiện tại bằng cách cung cấp các cơ chế để thêm dữ liệu mơ tả ngữ nghĩa (semantic metadata) về các thực thể và các khái niệm trên các tài liệu web hiện tại, dưới dạng các chú thích ngữ nghĩa (semantic annotation), để máy tính cĩ thể tích hợp và chia sẻ thơng tin và dữ liệu giữa các ứng dụng một cách tự động. Trên tinh thần đĩ, xác định các thực thể cĩ tên trên các văn bản và thêm dữ liệu mơ 1 2 Chúng tơi dùng CS viết tắt cho cụm các cộng sự 1.1.Lịch sử và động cơ nghiên cứu 3 tả ngữ nghĩa về chúng trên chính các văn bản đĩ, sử dụng các ontology, hoặc các cơ sở tri thức (knowledge base – KB), đĩng một vai trị quan trọng trong việc đạt được mục tiêu phát triển web cĩ ngữ nghĩa. Hướng đến việc hiện thực các ứng dụng web cĩ ngữ nghĩa, SemTag là một trong những hệ thống đầu tiên thực hiện chú thích ngữ nghĩa cĩ qui mơ lớn cho các thực thể cĩ tên trên các trang web (Dill và CS, 2003). Các tác giả của SemTag đã trình bày một ví dụ cho thấy ý nghĩa của các chú thích ngữ nghĩa về các thực thể cĩ tên trong việc phát triển các ứng dụng web cĩ ngữ nghĩa. Ví dụ câu “The Chicago Bulls announced yesterday that Michael Jordan will . . .” xuất hiện với các chú thích ngữ nghĩa về các thực thể cĩ tên khi Chicago Bulls và Michael Jordan được xác định chính xác dựa trên ontology của TAP (Guha và McCool, 2003) như sau: “The Chicago Bullsannounced yesterday that <resource ref=""> Michael Jor- dan will...” Trong đĩ chú thích <resource ref=" _Michael"> Michael Jordan ngụ ý rằng “Michael Jordan” trong câu trên đề cập đến thực thể cĩ định danh (identifier) là _Michael trong ontology của TAP. Dựa trên định danh này máy tính cĩ thể xác định Mi- chael Jordan là vận động viên bĩng rổ người Mỹ, người sinh ngày 17 tháng 02 năm 1963 và đã về hưu. Một văn bản được bổ sung các chú thích ngữ nghĩa như thế sẽ cung cấp nhiều thơng tin hơn về các thực thể và các khái niệm được đề cập trong đĩ, giúp máy tính cĩ thể đọc hiểu một phần hoặc tồn bộ văn bản. Hiện nay người ta mong muốn rằng các trang web sẽ được bổ sung các chú thích ngữ nghĩa như thế để tạo tiền đề cho việc phát triển các ứng dụng web cĩ ngữ nghĩa, cũng như phát triển nâng cao các ứng dụng trong mảng xử lý ngơn ngữ tự nhiên nĩi chung. Thật vậy, cĩ thể hình dung một viễn cảnh là, một khi các trang web đã được bổ sung dữ liệu mơ tả ngữ nghĩa về các thực thể và các khái niệm, với một truy vấn về thành phố “Sài Gịn” sẽ nhận được các văn bản nĩi về Thành phố Sài Gịn và Thành phố HCM chứ khơng như các động cơ tìm kiếm hiện hành là trả về bất kì văn bản nào chứa cụm từ “Sài Gịn” mặc dù các văn bản đĩ cĩ thể đề cập đến Cơng ty Bánh kẹo Sài Gịn, Trường ĐHCN Sài Gịn, người Sài Gịn, . . . 4 Chương 1.Giới thiệu Trực quan cho thấy rằng các trang web được bổ sung dữ liệu mơ tả ngữ nghĩa như trên chưa xuất hiện rộng rãi trên Web hiện tại. Để dữ liệu mơ tả đĩ luơn sẵn sàng trên Web, một trong những cơng việc cần thiết là phải xác định đúng các thực thể cĩ tên xuất hiện trên đĩ. Nhận dạng thực thể cĩ tên, được biết đến rộng rãi với tên Named Entity Recognition (NER), là một cơng việc bước đầu hướng đến mục tiêu đĩ. Theo MUC-6 (Sixth Message Understanding Conference – MUC-6, 1995), NER là nhận biết và phân lớp (hoặc xác định thể loại) các thực thể cĩ tên (ví dụ: con người, tổ chức, nơi chốn), các biểu thức thời gian (ví dụ: “02/04/2006”, “1-12-97”, “10h:20’”, . . .) và các biểu thức số (ví dụ: 45%, 15m, 25kg, . . .). Trong hơn một thập niên qua đã cĩ nhiều nghiên cứu về nhận dạng thực thể cĩ tên (Nadeau và Sekine, 2007). Một số nghiên cứu tập trung vào việc nhận biết và phân lớp các NE vào các lớp ở mức cao như con người, tổ chức và nơi chốn (Bikel và CS, 1999; Tjong Kim Sang, 2002; Tjong Kim Sang và De Meulder, 2003). Trong khi đĩ một số nghiên cứu khác quan tâm việc nhận biết và phân lớp các thực thể vào các lớp mịn hơn, dựa trên một hệ thống phân cấp gồm hàng trăm lớp thực thể (Cimiano và Vưlker, 2005; Nadeau, 2007). Tuy nhiên, NER chỉ dừng lại ở việc xác định lớp của các thực thể, mà chưa xác định được định danh cụ thể của các thực thể. Do đĩ, việc tiến một bước xa hơn nhằm xác định định danh của các thực thể là thật sự cần thiết và cĩ ý nghĩa, như đã trình bày, trong việc thúc đẩy sự phát triển Web cĩ ngữ nghĩa và xử lý ngơn ngữ tự nhiên nĩi chung. Luận án này giải quyết bài tốn Phân giải nhập nhằng thực thể cĩ tên (Named Entity Disambiguation – NED), nhằm vào mục tiêu đĩ. Một thách thức lớn trong thực tế là, một thực thể cĩ thể cĩ nhiều tên. Ví dụ, “Ngân hàng Thương mại Cổ phần Á Châu”, “Ngân hàng Á Châu” và “ACB” là các tên của cùng một ngân hàng – Ngân hàng Thương mại Cổ phần Á Châu. Hơn nữa, các thực thể khác nhau cĩ thể trùng tên. Ví dụ, tên “Võ Thị Sáu” cùng là tên của một con người (anh hùng Võ Thị Sáu), một đường phố ở TP. HCM (đường Võ Thị Sáu), một trường trung học ở TP. HCM (trường PTTH Võ Thị Sáu, Đinh Tiên Hồng, phường 3, quận Bình Thạnh, TP. Hồ Chí Minh). Do đĩ, cùng một tên, nhưng trong các lần xuất hiện khác nhau, cĩ thể được dùng để đề cập đến các thực thể khác nhau. Ví dụ, “John McCarthy” cĩ thể được dùng để đề cập đến các thực thể khác nhau trong các ngữ cảnh khác nhau, như khoa học gia máy tính người Mỹ – nhà phát minh ngơn ngữ lập trình Lisp – hoặc nhà báo người Anh, người bị bắt cĩc bởi các phần tử Hồi giáo Jihad ở Li Băng năm 1986, hoặc nhà âm vị học người 1.1.Lịch sử và động cơ nghiên cứu 5 Mỹ – giáo sư ngơn ngữ học làm việc tại Đại học Massachusetts, Amherst. Hệ quả là, một tên xuất hiện trong văn bản đồng thời là tên của nhiều thực thể trong thế giới thực sẽ tạo ra sự nhập nhằng (ambiguity), và tên đĩ được gọi là tên nhập nhằng. Điều đĩ dẫn đến việc xác định đúng các thực thể được đề cập đến trong một văn bản là thật sự khĩ khăn và thách thức, và là nguyên nhân dẫn đến phân giải nhập nhằng thực thể cĩ tên đã và đang trở thành một chủ đề nghiên cứu quan trọng trong việc phát triển các ứng dụng web cĩ ngữ nghĩa, cũng như phát triển nâng cao các ứng dụng trong mảng xử lý ngơn ngữ tự nhiên nĩi chung. Phân giải nhập nhằng thực thể cĩ tên trước hết là nhằm xác định liệu hai lần xuất hiện của cùng một tên, hoặc các cách viết khác nhau của nĩ, trong các tài liệu khác nhau cĩ đề cập đến cùng một thực thể hay hai thực thể khác nhau. Ví dụ, NED là xác định hai lần xuất hiện của “John Smith” trên hai tài liệu khác nhau cùng đề cập đến một nguời hay đề cập đến hai người khác nhau cĩ cùng tên “John Smith”. Một ví dụ khác là xác định “J. Smith” và “John Smith” xuất hiện trong hai tài liệu khác nhau cĩ đề cập đến cùng một người hay hai người khác nhau. Cho đến nay, cĩ hai hướng nghiên cứu chính đối với NED (Sarmento và CS, 2009). Hướng nghiên cứu thứ nhất xem NED như là bài tốn gom cụm (clustering - Cardie và Wagstaff, 1999), trong đĩ mục tiêu là gom cụm các tên xuất hiện trong các tài liệu khác nhau thành các cụm khác nhau dựa trên thơng tin rút trích từ chính các tài liệu, mỗi cụm bao gồm các tên đề cập đến cùng một thực thể (Bagga và Baldwin, 1998b; Mann và Ya- rowsky, 2003; Han và CS, 2004; Bekkerman và McCallum, 2005; Chen và Martin, 2007; Mayfield và CS, 2009; Sarmento và CS, 2009). Bunescu (2007) xem hướng nghiên cứu này giải quyết bài tốn Phân biệt các thực thể cĩ tên (Named Entity Discrimination). Ví dụ, khi “John Smith” xuất hiện trong các tài liệu khác nhau, một phương pháp theo hướng này xác định các xuất hiện nào của “John Smith” đề cập đến cùng một thực thể, rồi gom thành một cụm. Một trường hợp đặc biệt của hướng nghiên cứu này là bài tốn Tìm kiếm con người trên Web (Web People Search - WebPS), với mục tiêu là gom cụm các tài liệu trong đĩ cĩ xuất hiện các tên đề cập đến cùng một người thay vì gom cụm chính các tên đĩ (Artiles và CS, 2007; Artiles và CS, 2009). Hướng nghiên cứu thứ hai xem NED như là bài tốn ánh xạ (mapping). Chúng tơi gọi hướng nghiên cứu này theo đúng tên gọi Phân giải nhập nhằng thực thể cĩ tên, với mục tiêu là ánh xạ một tên xuất hiện trong một văn bản vào một thực thể (đối tượng tham chiếu) 6 Chương 1.Giới thiệu trong một nguồn tri thức (bên ngồi) nào đĩ với một định danh duy nhất. Hướng nghiên cứu này khai thác các thơng tin khơng chỉ trên chính các tài liệu mà cịn dựa trên các nguồn tri thức bên ngồi các tài liệu, ví dụ như Wikipedia, để thực hiện việc phân giải nhập nhằng (Bunescu và Paşca, 2006; Cucerzan, 2007; Hassell và CS, 2006; Volz và CS, 2007; Buscaldi và Rosso, 2008; Overell, 2009). Khái niệm bên ngồi này hiểu theo nghĩa là khai thác tri thức và thơng tin khơng phải được rút trích trên chính các tài liệu. Ví dụ, khi “John McCarthy” xuất hiện trong một văn bản (đề cập đến khoa học gia máy tính, người phát minh ra ngơn ngữ lập trình LISP), một phương pháp theo hướng này (Cucerzan, 2007) thực hiện việc ánh xạ “John McCarthy” vào đúng thực thể John McCarthy (com- puter scientist) trong Wikipedia - thực thể được mơ tả bởi trang cĩ nhan đề “John McCarthy (computer scientist)”. Luận án này nghiên cứu và đề xuất các phương pháp phân giải nhập nhằng thực thể cĩ tên theo hướng tiếp cận thứ hai. Một bài tốn liên quan với NED là Liên kết bản ghi (Record Linkage) trong các cơ sở dữ liệu. Liên kết bản ghi là nhằm xác định các bản ghi trong cùng hoặc nhiều cơ sở dữ liệu cĩ chứa thơng tin về cùng một thực thể hay khơng, và sau đĩ liên kết hoặc hợp nhất chúng (Winkler, 2006; Elmagarmid và CS, 2007; Benjelloun và CS, 2009). Các phương pháp được đề xuất cho bài tốn Liên kết bản ghi thực hiện việc so trùng các bản ghi bằng việc tính tốn độ tương tự giữa các thuộc tính của các bản ghi. Các thuộc tính này được xác định dựa trên lược đồ của các cơ sở dữ liệu. Bởi vì các lược đồ cơ sở dữ liệu cĩ cấu trúc, nên cĩ thể dễ dàng xác định các thuộc tính của các bản ghi. Trong khi đĩ, NED thực hiện việc phân giải nhập nhằng các thực thể trên các tài liệu phi cấu trúc hoặc bán cấu trúc, trong đĩ thơng tin liên quan đến các thực thể đang được xem xét thay đổi tùy theo tài liệu. Nĩi một cách khác, NED khác Liên kết bản ghi ở chỗ: • Mặc dù khi một số thơng tin trên hai tài liệu là giống nhau, chúng ta vẫn chưa kết luận được hai lần xuất hiện của cùng một tên trên hai tài liệu đĩ cĩ cùng đề cập đến một thực thể hay khơng. Ví dụ, mặc dù khi trong cả hai tài liệu đều xuất hiện “John McCarthy” và cùng đề cập John McCarthy là cơng dân Mỹ, chúng ta vẫn chưa thể kết luận rằng hai lần xuất hiện của “John McCarthy” đề cập đến cùng một người. • Các tài liệu khác nhau chứa nhiều kiểu thơng tin đa dạng, dẫn đến việc phân tích ngữ cảnh để xác định các thực thể được đề cập đến trong tài liệu trở nên khĩ khăn. Ví dụ, Georgia (đề cập đến quốc gia Gruzia) trong một tài liệu cĩ thể cùng xuất 1.1.Lịch sử và động cơ nghiên cứu 7 hiện với Tbilisi, nhưng trong tài liệu khác cĩ thể cùng xuất hiện với Zviad Gam- sakhurdia (tổng thống dân cử đầu tiên của Gruzia). NED cĩ thể được xem như là một trường hợp đặc biệt của bài tốn Phân giải nhập nhằng ngữ nghĩa từ vựng (Word Sense Disambiguation – WSD, Ide và Véronis, 1998; Na- vigli, 2009). Mục tiêu của WSD là nhằm xác định nghĩa nào của một từ vựng được sử dụng trong một ngữ cảnh cụ thể, khi từ này cĩ nhiều nghĩa khác nhau. Các kỹ thuật phân giải nhập nhằng sử dụng các từ điển hoặc ontology (WordNet3 là một ví dụ) như là các kho ngữ nghĩa - định nghĩa các nghĩa cĩ thể của mỗi từ. Gần đây Mihalcea (2007) đã chứng tỏ rằng Wikipedia cĩ thể được sử dụng như một nguồn tri thức thay thế cho các từ điển. Theo chúng tơi, đặc thù của NED so với WSD là: • Thực thể cĩ tên khác với các từ về bản chất và ý nghĩa. Trong khi các thực thể cĩ tên, nĩi một cách nơm na, là các cá thể cụ thể trong thế giới thực, các từ diễn đạt các khái niệm tổng quát như kiểu, thuộc tính, quan hệ. Xử lý các từ do đĩ chỉ yêu cầu ngữ nghĩa từ vựng thơng thường, trong khi đĩ, xử lý các thực thể cĩ tên địi hỏi tri thức về một lĩnh vực cụ thể. • Việc phân giải nhập nhằng ngữ nghĩa của một từ cĩ thể dựa trên ngữ cảnh cục bộ của từ đĩ, bao gồm các từ đồng xuất hiện xung quanh nĩ trong một cửa sổ hẹp (thường là ba đến năm từ đứng trước và ba đến năm từ đứng sau nĩ). Trong khi đĩ, mỗi thực thể cĩ tên đều cĩ các thuộc tính riêng biệt và các mối quan hệ, được phát biểu tường minh hoặc khơng tường minh, với các thực thể khác đồng xuất hiện trong cùng văn bản. Các tính chất của một thực thể cĩ thể xuất hiện ở một vị trí bất kỳ trong văn bản, do đĩ, để phân giải nhập nhằng thực thể cĩ tên trong các văn bản phi cấu trúc hoặc bán cấu trúc cần phải phân tích ngữ cảnh ở một bình diện rộng hơn. • Các phương pháp đề xuất cho WSD chủ yếu tập trung phân giải nhập nhằng ngữ nghĩa của các từ vựng thơng thường (danh từ chung, động từ, tính từ), bỏ qua các danh từ riêng (hay tên riêng). Trong khi chỉ tồn tại một số lượng nhỏ các nghĩa cĩ 3 (Miller, 1995) 8 Chương 1.Giới thiệu thể của một từ vựng thơng thường, thực tế lại cho thấy rằng cĩ thể cĩ hàng trăm thực thể trùng tên. Ví dụ, theo Guha và Garg (2004), từ dữ liệu của cục dân số Mỹ, cĩ 90.000 tên được dùng để đặt tên cho 100 triệu người khác nhau. Quay lại với hướng nghiên cứu thứ nhất đối với NED tức là phân biệt các thực thể cĩ tên. Cơng trình đầu tiên theo hướng này là của Bagga và Baldwin (1998b). Từ đĩ cho đến nay, đã cĩ nhiều nghiên cứu theo hướng này như Mann và Yarowsky (2003), Gooi và Al- lan (2004), Malin (2005), Pedersen và CS (2005), Chen và Martin (2007), Mayfield và CS (2009), Sarmento và CS (2009). WebPS cũng thu hút sự quan tâm nghiên cứu rộng rãi và đã cĩ hai hội thảo được tổ chức vào các năm 2007 và 2009 là SemEval-2007 (Artiles và CS, 2007) và WebPS-2009 (Artiles và CS, 2009). Nhìn chung, một phương pháp phân giải nhập nhằng theo hướng này cĩ ba bước cơ bản như sau: (i) rút trích các đặc trưng (feature) để tạo các hồ sơ về các thực thể được đề cập đến trong các văn bản; (ii) tính tốn độ tương tự giữa các hồ sơ sử dụng một số độ đo tương tự, như cosine, sự phân kỳ Kullback-Leibler (Kullback-Leibler Divergence); và (iii) áp dụng các giải thuật gom cụm để gom các tên xuất hiện trong các tài liệu thành các nhĩm khác nhau, mỗi nhĩm bao gồm các tên cùng đề cập đến một thực thể. Một vấn đề quan trọng mà các phương pháp này cần phải giải quyết là thiết lập các điều kiện dừng (Pedersen và Kulkarni, 2006) cho các giải thuật gom cụm. Bởi vì tổng số cụm là khơng biết trước, nên các điều kiện dừng là rất cần thiết để bảo đảm các giải thuật gom cụm dừng với số cụm hợp lý nhất. Luận án này theo đuổi các phương pháp phân giải nhập nhằng thực thể cĩ tên theo hướng nghiên cứu thứ hai. Xuyên suốt phần cịn lại của luận án, khi đề cập đến NED, chúng tơi ngầm định hướng nghiên cứu thứ hai đối với NED, cịn khi đề cập đến hướng nghiên cứu thứ nhất chúng tơi sẽ nĩi rõ đĩ là bài tốn phân biệt các thực thể cĩ tên. Đối với NED, mỗi tên xuất hiện trong một văn bản được ánh xạ vào một thực thể được mơ tả trong một nguồn tri thức về các thực thể cĩ tên, do đĩ các điều kiện dừng như vừa được đề cập ở đoạn trên là khơng cần thiết. Khi một tên trong một văn bản cần được phân giải nhập nhằng, các thực thể trong một cơ sở tri thức mà cĩ tên trùng với nĩ được gọi là các thực thể ứng viên (candidate entity), hay nĩi vắn tắt là các ứng viên. Các nghiên cứu về NED thời kì đầu tập trung chủ yếu vào phân giải nhập nhằng các vùng địa lý, và được biết đến rộng rãi với tên Toponym Resolution (TR). Mục tiêu của bài tốn này là xác định liệu một tên trong một văn bản cĩ phải là tên của một nơi chốn hay 1.1.Lịch sử và động cơ nghiên cứu 9 khơng, sau đĩ ánh xạ tên này vào một tọa độ duy nhất trong một mơ hình khơng gian (Leidner và CS, 2003) hoặc một định danh xác định duy nhất một vùng địa lý trong một cơ sở tri thức về các vùng địa lý (Overell, 2009). Các nghiên cứu về phân giải nhập nhằng các vùng địa lý bắt đầu từ những năm 90 của thế kỷ trước và phổ biến từ đầu thập niên này (Leidner và CS, 2003; Li và CS, 2003; Zong và CS, 2005; Overell và Rüger, 2006; Volz và CS, 2007; Andogah và CS, 2008; Buscaldi và Rosso, 2008; Overell và Rüger, 2008). Các phương pháp phân giải nhập nhằng các vùng địa lý về cơ bản gồm cĩ hai bước. Bước thứ nhất là thực hiện xác định các tên trong một văn bản đề cập đến một vùng địa lý nào đĩ. Ví dụ, xác định liệu “Paris” trong một văn bản đề cập đến một vùng địa lý (ví dụ như thủ đơ nước Pháp) hay một con người (ví dụ như Paris Hilton), vì trong thực tế “Par- is”4 cĩ thể được dùng để đề cập đến nhiều thực thể thuộc nhiều thể loại khác nhau. Bước thứ hai, sau khi đã xác định các tên nào trong văn bản đề cập đến các vùng địa lý, các phương pháp này thực hiện một bước xa hơn là ánh xạ các tên đã được xác định vào đúng thực thể trong một mơ hình khơng gian hoặc một cơ sở tri thức về các vùng địa lý. Ví dụ, sau khi xác định “Paris” đề cập đến một vùng địa lý, các phương pháp này thực hiện một bước xa hơn là quyết định ánh xạ “Paris” vào Paris thủ đơ nước Pháp, hay thành phố Paris ở bang Texas, Mỹ, hoặc một vùng địa lý khác được mơ tả trong Wikipedia. Hai luận án tiến sĩ gần đây của Leidner (2007) và Overell (2009) đã khái quát đầy đủ các phương pháp phân giải nhập nhằng các vùng địa lý. Trong đĩ, phần lớn các phương pháp sử dụng các heuristic. Một khảo sát đầy đủ về các phương pháp sử dụng heuristic đến đầu năm 2007 được trình bày trong Leidner (2007). Các phương pháp phân giải nhập nhằng sử dụng heuristic hiệu quả nhất khai thác ngữ cảnh gồm ±2 đến ±5 từ xung quanh các tên nhập nhằng. Volz và CS (2007), Buscaldi và Rosso (2008) cũng đề xuất các heuristic để phân giải nhập nhằng. Các heuristic áp dụng cho phân giải nhập nhằng các vùng địa lý sử dụng các đặc trưng mang tính đặc thù chỉ cĩ đối với các vùng địa lý, do vậy khĩ điều chỉnh cho các thực thể thuộc thể loại khác, như con người hoặc các tổ chức. Garbin và Mani (2005) đề xuất mơ hình học bán giám sát (semi-supervised learning) để phân giải nhập nhằng các vùng địa lý. Phương pháp này phân lớp các vùng địa lý trong văn bản vào ba lớp là vùng hành 4 Kiểm tra tại: 10 Chương 1.Giới thiệu chính/dân sự, thủ đơ của các quốc gia, và khu dân cư. Việc xác định đúng lớp trong nhiều trường hợp chắc chắn giúp xác định đúng thực thể. Ví dụ như nếu biết rằng “Victoria” đề cập đến một thành phố hoặc một tiểu bang sẽ đủ để phân biệt giữa thủ phủ của tỉnh British Columbia của Canada, và tiểu bang Victoria của Australia. Tuy nhiên điều này khơng phải luơn luơn đúng, như trong trường hợp “Paris”, “Paris” cĩ thể là tên của một số thành phố thuộc các tiểu bang của Mỹ như thuộc các tiểu bang Idaho, Illinois, Kentucky, hoặc Maine. Overell và Rüger (2008) khai thác Wikipedia để xây dựng mơ hình đồng xuất hiện, phục vụ như là một tập huấn luyện, sau đĩ triển khai một mơ hình học cĩ giám sát (supervised learning) để thực hiện phân giải nhập nhằng. Các tác giả khai thác ngữ cảnh bao gồm ±10 tên của các vùng địa lý xung quanh tên nhập nhằng đang được xem xét, khơng quan tâm đến các từ khơng là một phần của các tên này. SemTag (Dill và CS, 2003) thực hiện chú thích ngữ nghĩa về các thực thể cĩ tên thuộc nhiều thể loại khác nhau cho 250 triệu trang web dựa trên ontology của TAP. Để chú thích ngữ nghĩa chính xác, SemTag cũng bao hàm việc phân giải nhập nhằng các thực thể cĩ tên. Với mỗi tên cần phân giải nhập nhằng, SemTag trích ngữ cảnh gồm ±10 từ xung quanh nĩ, và so sánh với ngữ cảnh của các thực thể trong ontology của TAP để chọn thực thể phù hợp cho việc tạo chú thích ngữ nghĩa. Tuy nhiên, bởi vì ưu tiên độ chính xác, SemTag chỉ tạo ra 450 triệu chú thích ngữ nghĩa, trung bình chưa đến 2 chú thích cho một trang web. Do đĩ, tỉ lệ các chú thích tạo ra trên một tài liệu là khơng nhiều. Hơn nữa, khơng cĩ nhiều thực thể trong ontology của TAP cĩ cùng tên (Kyriakov và CS, 2005), cho nên việc phân giải nhập nhằng của SemTag là khá đơn giản. Từ năm 2006 bắt đầu xuất hiện các nghiên cứu phân giải nhập nhằng các thực thể cĩ tên, khơng chỉ tập trung vào các thực thể là các nơi chốn, với mật độ chú thích ngữ nghĩa cao hơn SemTag (Hassell và CS, 2006; Bunescu và Paşca, 2006; Cucerzan, 2007; Fernan- dez và CS, 2007; Mihalcea và Csomai, 2007; Medelyan và CS, 2008; Milne và Witten, 2008; Fader và CS, 2009; Kulkarni và CS, 2009). Hassell và CS (2006) đề xuất phương pháp nhận biết chính xác các ủy viên hội đồng phản biện trên các trang web hội nghị khoa học. Phương pháp của Fernandez và CS (2007) nhận biết các thực thể cĩ tên trên các văn bản trong lĩnh vực tin tức. Phương pháp này là bán tự động, bởi vì kết quả phân giải nhập nhằng sẽ được hiển thị cho người sử dụng điều chỉnh kết quả nếu cần và cập nhật kết quả đã được điều chỉnh vào một cơ sở dữ liệu suy diễn phục vụ như là một tập huấn luyện. 1.1.Lịch sử và động cơ nghiên cứu 11 Nổi lên gần đây như là một từ điển bách khoa trực tuyến lớn nhất và được sử dụng rộng rãi nhất trên Internet, Wikipedia được khai thác để giải quyết nhiều bài tốn trong mảng xử lý ngơn ngữ tự nhiên và xây dựng các ontology (Medelyan và CS, 2009). Chúng tơi sẽ trình bày chi tiết Wikipedia trong Chương 2, tuy nhiên ở đây chúng tơi khái quát vài nguồn thơng tin quan trọng trên đĩ mà một số phương pháp phân giải nhập nhằng đã khai thác. Wikipedia là từ điển bách khoa trực tuyến nội dung mở, được đĩng gĩp bởi hàng trăm nghìn tình nguyện viên. Thành phần cơ bản của Wikipedia là các trang (page hay ar- ticle). Cĩ nhiều loại trang trên Wikipedia như trang thực thể (entity page), trang đổi hướng (redirect page), trang phân giải nhập nhằng (disambiguation page), trang thể loại (catego- ry page) . . . Mỗi trang thực thể định nghĩa duy nhất một thực thể hoặc một khái niệm, và được xác định duy nhất bởi nhan đề (title) của nĩ. Mỗi trang thực thể thuộc một hoặc nhiều thể loại, và cĩ các trang đổi hướng tương ứng. Mỗi trang thực thể cũng cĩ nhiều liên kết vào (in- coming link) và nhiều liên kết ra (outgoing link). Các trang thể loại được tạo cho các thể loại trong hệ thống phân loại của Wikipedia. Mỗi trang đổi hướng chỉ chứa duy nhất một liên kết đến trang thực thể tương ứng và nhan đề của nĩ chứa một tên khác của thực thể này. Mỗi liên kết ra trỏ đến một trang khác trong Wikipedia, và nhãn của liên kết chính là nhan đề của trang đĩ. Một số nghiên cứu xem các liên kết ra như các nhãn ngữ nghĩa, và xem tập các trang thực thể trong Wikipedia như là một tập huấn luyện, với mỗi trang thực thể là một tài liệu đã được gán nhãn (Mihalcea và Csomai, 2007; Milne và Witten, 2008). Trang phân giải nhập nhằng được tạo cho các tên nhập nhằng trong Wikipedia. Từ các trang này chúng ta cĩ thể xác định các thực thể cĩ cùng tên trong Wikipedia. Từ năm 2006, Wikipedia đã được khai thác để phân giải nhập nhằng các thực thể cĩ tên. Bunescu và Paşca (2006) khai thác các nguồn thơng tin nêu trên của Wikipedia để phân giải nhập nhằng. Các véctơ đặc trưng của các thực thể trong Wikipedia được xây dựng sử dụng các từ xuất hiện trong cửa sổ gồm 55 từ xung quanh mỗi tên thực thể. Cosine được sử dụng để tính tốn độ tương tự và phân hạng các ứng viên. Nhiều trường hợp co- sine cĩ giá trị quá thấp, nên ngữ cảnh được mở rộng bao gồm các từ xuất hiện trong nhãn thể loại của các thực thể nhằm khai thác mối tương quan giữa các từ trong văn bản và các nhãn thể loại (ví dụ: “concert” cĩ tương quan với nhãn của thể loại “Musicians” mạnh hơn so với nhãn của thể loại “Professional Wrestlers”), sử dụng mơ hình máy véctơ hỗ trợ (Su- port Vector Machine - SVM). Cucerzan (2007) cũng khai thác các nguồn thơng tin nêu trên 12 Chương 1.Giới thiệu của Wikipedia như Bunescu và Paşca (2006). Thay vì phân giải nhập nhằng từng tên trong văn bản, phương pháp của Cucerzan phân giải nhập nhằng cho tất cả các tên cùng lúc, dẫn đến bài tốn tối ưu cùng lúc các ánh xạ, là một bài tốn NP-khĩ (NP-hard)(Kulkarni và CS, 2009; Pilz và CS, 2009). Milhacea (2007) đã chứng tỏ rằng Wikipedia cĩ thể được sử dụng như là một kho ngữ nghĩa cho việc phân giải nhập nhằng ngữ nghĩa từ vựng hiệu quả. Mihalcea và Csomai (2007) đã hiện thực và đánh giá hai giải thuật phân giải nhập nhằng từ vựng khác nhau nhằm ánh xạ các từ khĩa, bao gồm cả tên riêng, xuất hiện trong văn bản vào đúng các thực thể hoặc các khái niệm trong Wikipedia. Các tác giả cho thấy mơ hình học cĩ giám sát, trong đĩ các trang trong Wikipedia mà các từ khĩa xuất hiện trong đĩ đã được gán nhãn, được sử dụng như là tập huấn luyện, cho hiệu quả tốt nhất. Medelyan và CS (2008) phát triển phương pháp phân giải nhập nhằng các từ khĩa dựa trên mơ hình của Mihalcea và Csomai, trong đĩ xác suất tiên nghiệm của các khái niệm trong Wikipedia và các từ khĩa đã được phân giải nhập nhằng được khai thác để phân giải nhập nhằng. Với mỗi ứng viên, số lượng trùng lắp giữa nhãn các liên kết ra của nĩ, và các từ khĩa đã được xác định trong văn bản sẽ được tính tốn, sau đĩ nhân với xác suất tiên nghiệm của ứng viên. Ứng viên cĩ tích số lớn nhất sẽ được chọn. Xác suất tiên nghiệm phản ánh mức độ phổ biến (thơng qua tần suất xuất hiện) của một khái niệm trong tập huấn luyện, được tính tốn thơng qua tổng số liên kết vào của chính khái niệm đĩ trên tổng số liên kết vào của tất cả các ứng viên. Milne và Witten (2008) mở rộng nghiên cứu của Mihalcea và Csomai (2007) và Me- delyan và CS (2008) bằng cách khai thác mối quan hệ ngữ nghĩa (semantic relatedness), được tính tốn dựa trên các liên kết vào, của một từ khĩa với các từ khĩa đã được xác định xuất hiện xung quanh nĩ. Ngồi ra, các tác giả cũng khai thác mức độ phổ biến như trong Medelyan và CS (2008). Kulkarni và CS (2009) đề xuất phương pháp tương tự như Milne và Witten (2008) với sự khác biệt là các tác giả tối ưu đồng thời các ánh xạ và giải bài tốn NP-khĩ bằng hai phương pháp tối ưu là qui hoạch nguyên và chiến lược leo đồi. Phương pháp của Fader và CS (2009) lấy ý tưởng từ Bunescu và Paşca (2006), Cucerzan (2007) và Medelyan và CS (2008). Hình 1.1 trình bày một mơ hình phân giải nhập nhằng phổ quát cho nhiều phương pháp phân giải nhập nhằng. Trong đĩ phần nhận dạng thực thể cĩ tên cĩ thể chỉ dừng lại ở việc xác định các cụm từ đề cập đến các thực thể trong một ontology, hoặc cĩ phân lớp các thực thể vào các lớp ở mức cao như con người, tổ chức, nơi chốn, hoặc phân lớp các thực 1.1.Lịch sử và động cơ nghiên cứu 13 thể vào các lớp mịn hơn dựa trên hệ thống phân cấp các lớp của một ontology. Phần tiền xử lý của nhận dạng thực thể cĩ tên khơng được thể hiện trong mơ hình. Mơ hình cho thấy Nhận dạng thực thể cĩ tên và Phân giải đồng tham chiếu tên riêng là phần tiền xử lý của Phân giải nhập nhằng thực thể cĩ tên. Hình 1.1: Một mơ hình phân giải nhập nhằng phổ biến Nhìn chung, NED mới nổi lên khoảng một thập niên trở lại đây như là một vấn đề đầy thách thức và cĩ nhiều ý nghĩa trong nhiều ứng dụng xử lý ngơn ngữ tự nhiên, đặc biệt là đối với các ứng dụng web cĩ ngữ nghĩa. Để cĩ thể đánh giá và so sánh các phương pháp phân giải nhập nhằng khác nhau, cần cĩ một nền chung. Cụ thể là phần tiền xử lý, nguồn tri thức được sử dụng, và tập dữ liệu dùng cho các thí nghiệm phải giống nhau. Tuy nhiên, hiện nay chưa cĩ một tập dữ liệu thí nghiệm chung cĩ thể chia sẻ được, và các phương pháp đã cơng bố đều triển khai các mơ hình tiền xử lý khác nhau. Do vậy, các cơng trình nghiên cứu cho đến thời điểm hiện tại đều tạo các tập dữ liệu thí nghiệm riêng và việc so sánh trực tiếp các phương pháp là khĩ thực hiện (Kulkarni và CS, 2009). Chúng tơi bắt đầu cơng việc nghiên cứu về NED từ giữa năm 2006, và đến cuối năm 2006 đã đề xuất ý tưởng khai thác mối quan hệ ngữ nghĩa của các ứng viên với các thực thể đã được xác định trong tài liệu để phân giải nhập nhằng các thực thể cĩ tên dựa trên một ontology (Nguyen và Cao, 2007a). Ý tưởng này tiếp tục được phát triển trong Nguyen Nguồn tri thức về các thực thể cĩ tên (ontology hoặc cơ sở tri thức) Phân giải nhập nhằng thực thể cĩ tên Tài liệu thơ Nhận dạng thực thể cĩ tên Phân giải đồng tham chiếu tên riêng Tiền xử lý Phân giải nhập nhằng Tài liệu với các tên (thực thể) đã được chú giải Luồng xử lý Nguồn tri thức cung cấp thơng tin cho các mơđun xử lý Các ánh xạ đến các thực thể trong nguồn tri thức 14 Chương 1.Giới thiệu và Cao (2007b) và Nguyễn Thanh Hiên và Cao Hồng Trụ (2008). Đến giữa năm 2008, Medelyan và CS (2008) phát triển ý tưởng tương tự, tức là cũng khai thác các thực thể đã được xác định, áp dụng để phân giải nhập nhằng các từ khĩa (bao gồm tên riêng) xuất hiện trong các văn bản sử dụng Wikipedia. Milne và Witten (2008) tiếp tục hồn thiện cơng trình của Medelyan và CS (2008) bằng cách cải thiện cơng thức phân hạng các ứng viên, và phân giải nhập nhằng sử dụng một mơ hình học cĩ giám sát. Kulkarni và CS (2009) cải tiến cơng việc của Milne và Witten (2008) ở chỗ giải quyết bài tốn tối ưu đồng thời các ánh xạ bằng cách giải quyết bài tốn NP-khĩ lần lượt bằng hai phương pháp tối ưu là qui hoạch nguyên và chiến lược leo đồi. Tương tự như chúng tơi, Medelyan và CS (2008) xem các thực thể đã được xác định như là một tập các hạt giống, nhưng cĩ sự khác biệt là tập các hạt giống của chúng tơi thay đổi tăng dần về số lượng theo diễn tiến của quá trình phân giải nhập nhằng, trong khi đĩ tập các hạt giống trong các cơng trình vừa nêu ở trên thì cố định trong quá trình phân giải nhập nhằng. Nĩi một cách khác, chúng tơi thực hiện phân giải nhập nhằng bằng một quá trình lặp cải thiện dần (incremental), khởi đầu với một tập các hạt giống. Khi một tên cần được phân giải nhập nhằng, các hạt giống sẽ được khai thác để xác định đúng thực thể mà tên đĩ đề cập đến. Chính thực thể sau khi đã được xác định sẽ được bổ sung vào tập các hạt giống để phân giải nhập nhằng cho các trường hợp cịn lại. Cứ thế, quá trình phân giải nhập nhằng lặp đi lặp lại cho đến khi nào tất cả các thực thể được đề cập đến trong một văn bản được xác định hoặc khi số thực thể được xác định sau mỗi lần lặp khơng thay đổi so với lần lặp trước. Trong quá trình phân giải nhập nhằng đĩ, một hạt giống nào đĩ cĩ thể bị thay thế bằng một đối tượng mới. Như vậy, với việc đề xuất ý tưởng phân giải nhập nhằng theo một quá trình lặp cải thiện dần, chúng tơi đã xác lập được một hướng đi riêng kể từ đầu năm 2007 (Nguyen và Cao, 2007a). Ý tưởng này tiếp tục được phát triển trong các phương pháp phân giải nhập nhằng dựa trên thống kê (Nguyen và Cao, 2010a, 2010b), và phương pháp lai – kết hợp giữa một mơ hình thống kê và các heuristic (Nguyen và Cao, 2008b). Chúng tơi sẽ trình bày chi tiết các phương pháp phân giải nhập nhằng được đề xuất trong luận án này lần lượt trong Chương 3, Chương 4, và Chương 5. 1.2. Bài tốn và phạm vi 15 1.2 Bài tốn và phạm vi Luận án này giải quyết bài tốn phân giải nhập nhằng thực thể cĩ tên bằng cách ánh xạ các tên xuất hiện trong các văn bản vào đúng các thực thể đã biết, ví dụ như các thực thể trong một ontology hoặc một cơ sở tri thức, mà các tên đĩ thật sự đề cập đến. Ví dụ, cho đoạn văn bản “the computer scientist John McCarthy coined the term artificial intelligence in the late 1950's”, ánh xạ đúng là “John McCarthy” với thực thể John McCarthy (computer scientist) trong Wikipedia. Hình 1.2 minh họa các ánh xạ từ mỗi tên xuất hiện trong một đoạn văn bản vào đúng thực thể mà nĩ đề cập; trong đĩ các tên được gạch dưới. Văn bản Cơ sở tri thức Thế giới thực Hình 1.2: Một ví dụ của phân giải nhập nhằng thực thể cĩ tên Brazilian legend Pele has made comments that are sure to generate massive controversy in the footballing world, after he indicated that Ronaldo and Robinho took drugs at a private event in Sao Paulo with businessmen in the tourist sector. (goal.com) • Ronaldinho • Ronaldo • Robinho • Cristiano Ronaldo • Pele • Sao Paulo 16 Chương 1.Giới thiệu Wacholder và CS (1997) đã chỉ ra một số mức độ nhập nhằng về thực thể cĩ tên. Thứ nhất là nhập nhằng giữa thực thể cĩ tên và các khái niệm chung, khi tên của một thực thể cĩ tên trùng với một khái niệm chung. Ví dụ như “Apple” là tên của một tổ chức, khác với “apple” (trong tiếng Anh) cĩ nghĩa là quả táo. Mức độ nhập nhằng thứ hai xảy ra khi cấu trúc của các tên là nhập nhằng, và được gọi là nhập nhằng về cấu trúc. Ví dụ, “Victoria and Albert Museum” trong một ngữ cảnh là tên của một bảo tàng, trong đĩ and là một phần của tên này. Tuy nhiên, cũng cùng cấu trúc như vậy, and trong cụm từ “IBM and Bell Laboratories” trong một văn bản tiếng Anh là liên từ nối tên của hai cơng ty khác nhau. Mức độ nhập nhằng tiếp theo là nhập nhằng về lớp thực thể, khi một tên cĩ thể dùng để đề cập đến các thực thể thuộc các lớp khác nhau trong các ngữ cảnh khác nhau. Ví dụ, “Tơn Đức Thắng” trong một ngữ cảnh cĩ thể đề cập đến một con người, chẳng hạn như đề cập đến Bác Tơn, nhưng trong ngữ cảnh khác cĩ thể đề cập đến một trường đại học (là một tổ chức), chẳng hạn như đề cập đến Trường Đại học Tơn Đức Thắng. Cuối cùng là nhập nhằng về đối tượng được tham chiếu, xảy ra khi một tên trong thực tế được dùng để đề cập đến các thực thể khác nhau. Ví dụ, “Paris” cĩ thể dùng đề cập đến thủ đơ của nước Pháp, một thành phố ở tiểu bang Texas của Mỹ hoặc cơ đào Paris Hilton nổi tiếng. Luận án này đề xuất các phương pháp phân giải nhập nhằng mức độ lớp và đối tượng được tham chiếu. Việc giải quyết các mức độ nhập nhằng cịn lại nằm ngồi phạm vi của luận án. Chúng tơi khơng đề xuất giải pháp cho phần tiền xử lý (Nhận dạng thực thể cĩ tên và Phân giải đồng tham chiếu tên riêng), mà sử dụng lại các phương pháp đã cĩ. Phương pháp phân giải nhập nhằng của chúng tơi khơng khai thác các yếu tố mang tính đặc thù của ngơn ngữ. Do đĩ, khi xử lý cho tiếng Anh, chúng tơi dùng các phần tiền xử lý áp dụng cho tiếng Anh, và khi xử lý cho tiếng Việt, các phần tiền xử lý áp dụng cho tiếng Việt sẽ được áp dụng. Như vậy, đầu vào cho phương pháp của chúng tơi là phụ thuộc ngơn ngữ, nhưng quá trình phân giải nhập nhằng thì khơng phụ thuộc ngơn ngữ. Do vậy, phương pháp phân giải nhập nhằng của chúng tơi cĩ thể điều chỉnh cho một ngơn ngữ bất kì. Khi áp dụng phương pháp của chúng tơi cho ngơn ngữ nào, thì phần tiền xử lý cho ngơn ngữ đĩ sẽ được triển khai. Phương pháp phân giải nhập nhằng của chúng tơi chấp nhận nhiễu ở đầu vào – lỗi do phần tiền xử lý tạo ra. Luận án nghiên cứu phân giải nhập nhằng các thực thể cĩ tên trong các văn bản phi cấu trúc, tập trung vào các văn bản thuộc lĩnh vực tin tức. Các tập dữ liệu thí nghiệm được thu thập từ các tờ báo điện tử trực tuyến. 1.3.Phương pháp luận đề xuất 17 1.3 Phương pháp luận đề xuất Luận án này đề xuất một phương pháp luận mới áp dụng cho phân giải nhập nhằng thực thể cĩ tên. Ý tưởng chủ đạo của phương pháp luận này là dựa vào định danh của các thực thể đã được xác định để phân giải nhập nhằng cho các trường hợp cịn lại bằng một quá trình lặp cải thiện dần. Dựa trên phương pháp luận đĩ, chúng tơi đề xuất ba phương pháp phân giải nhập nhằng thực thể cĩ tên. Phương pháp thứ nhất, đặt tên là OntoNEON, sử dụng một số heuristic, khai thác mối quan hệ ngữ nghĩa giữa các ứng viên với các thực thể đã được xác định trong văn bản, để phân giải nhập nhằng dựa trên một ontology. Phương pháp thứ hai, đặt tên là NOW, sử dụng phương pháp thống kê để phân giải nhập nhằng dựa trên một ontology được làm giàu. Phương pháp thứ ba, đặt tên là WIN, là một phương pháp lai (hybrid), kết hợp việc sử dụng các heuristic với một mơ hình thống kê để phân giải nhập nhằng dựa trên Wikipedia. Trong phần này chúng tơi lần lượt trình bày mơ hình phân giải nhập nhằng lặp cải thiện dần, các nguồn tri thức về thực thể, và các đặc trưng để biểu diễn thực thể mà luận án đề xuất. Mơ hình phân giải nhập nhằng Ý tưởng chung của các phương pháp được đề xuất trong luận án này là tiến hành phân giải nhập nhằng theo một quá trình lặp cải thiện dần, dựa trên phương pháp luận đã nêu ở trên. Quá trình đĩ bao gồm nhiều vịng lặp, các thực thể sau khi được xác định tại mỗi vịng lặp sẽ được sử dụng cho việc phân giải nhập nhằng ở các vịng lặp tiếp theo. Tức là việc phân giải nhập nhằng cho mỗi trường hợp sẽ dựa vào định danh của các thực thể đã được xác định trước đĩ. Mỗi thực thể sau khi được xác định, đến lượt mình, định danh của nĩ, cùng với định danh của các thực thể đã được xác định trước nĩ, sẽ được dùng để phân giải nhập nhằng cho những trường hợp cịn lại. Quá trình này sẽ diễn tiến cho đến khi nào xác định được định danh của tất cả các thực thể được đề cập đến trong văn bản hoặc khi giữa hai vịng lặp khơng cĩ thêm bất kì thực thể nào được xác định. Với các ngơn ngữ, thứ tự đọc phổ biến nhất là từ trái sang phải và từ trên xuống dưới, như với tiếng Anh và tiếng Việt. Do đĩ, một cách mặc định, các phương pháp của chúng tơi thực hiện phân giải nhập nhằng cho các thực thể theo thứ tự này; ngoại trừ trường hợp các tên xuất hiện trong phần tiêu đề của văn bản, bởi vì các tên này thường khơng phải là 18 Chương 1.Giới thiệu tên thường dùng của thực thể được đề cập, nên được phân giải nhập nhằng sau các tên khác. Nếu một ngơn ngữ nào cĩ thứ tự đọc khác, thì thứ tự phân giải sẽ được điều chỉnh cho phù hợp. Giải thuật 1.1 trình bày ý tưởng phân giải nhập nhằng lặp cải thiện dần. Đầu vào của giải thuật được cung cấp từ phần tiền xử lý – mơ tả trong Hình 1.1; bao gồm danh sách các tên và thơng tin bổ trợ về tên trích rút từ văn bản (các từ xuất hiện xung quanh các tên và mối quan hệ đồng tham chiếu giữa chúng), và nguồn tri thức được sử dụng. Đầu ra là ánh xạ các tên vào các thực thể trong nguồn tri thức đĩ. Trong phần thân của giải thuật, đầu tiên là xây dựng tập các “hạt giống”, sau đĩ mới tiến hành phân giải. Mỗi hạt giống là một sự kết hợp giữa một tên n trong văn bản và một thực thể e trong nguồn tri thức một khi n đã được ánh xạ vào e; khi đĩ, thực thể mà n tham chiếu đến đã được xác định, khơng cịn nhập nhằng nữa. Tập các hạt giống cĩ thể là tập rỗng hoặc là tập các kết hợp giữa một số tên trong văn bản với các ứng viên duy nhất của chúng. Tùy theo phương pháp phân giải nhập nhằng được đề xuất trong luận án mà tập các hạt giống được thiết lập phù hợp. Vịng lặp ở dịng 3 kết thúc khi tất cả các tên trong văn bản đã được thiết lập các ánh xạ tương ứng hoặc giữa hai vịng lặp khơng cĩ bất kì thực thể nào mới được xác định so với vịng lặp trước. Tại Dịng 6, Γ cho mỗi tên là tập các thực thể trong cơ sở tri thức cĩ tên trùng hồn tồn với tên đĩ. Dịng 8 cho thấy ứng viên nào cĩ số điểm cao nhất sẽ được chọn để thực hiện ánh xạ, trong đĩ score[i] là số điểm của ứng viên i. Việc cho điểm các ứng viên phụ thuộc vào mơ hình phân hạng các ứng viên được triển khai, trong đĩ các thực thể đã được xác định sẽ được khai thác. Trong luận án, chúng tơi đề xuất hai mơ hình phân hạng các ứng viên; một mơ hình phân hạng các ứng viên dựa vào mối quan hệ ngữ nghĩa của mỗi ứng viên với các thực thể đã được xác định xung quanh, và một mơ hình phân hạng các ứng viên dựa trên thống kê. Chi tiết về các mơ hình phân hạng ứng viên sẽ được trình bày trong Chương 3 và Chương 4. Dịng 10 cho thấy các thực thể sau khi được xác định sẽ được bổ sung vào tập các hạt giống. Hàm revised thực thi tại dịng 10 sẽ thực hiện điều chỉnh tập E dựa vào mối quan hệ đồng tham chiếu của tên đang xét với các tên khác trong cùng văn bản. Ví dụ, giả sử “George Bush” và “Bush” cùng xuất hiện trong một văn bản và là đồng tham chiếu, “George Bush” là tên đang được xem xét để phân giải nhập nhằng, “Bush” trước đĩ đã được ánh xạ vào một thực thể A nào đĩ. Nếu sau khi phân giải nhập nhằng “George Bush” 1.3.Phương pháp luận đề xuất 19 được ánh xạ vào một thực thể B, thì dựa vào mối quan hệ đồng tham chiếu giữa “George Bush” và “Bush”, ánh xạ “Bush” vào A sẽ được điều chỉnh thành “Bush” ánh xạ vào B. Giải thuật 1.1: Phân giải nhập nhằng lặp cải thiện dần Đầu vào: Tập các tên घ, các thơng tin bổ trợ về các tên trong văn bản (các từ xung quanh, quan hệ đồng tham chiếu), và nguồn tri thức được sử dụng. Đầu ra: Ánh xạ các tên vào các thực thể trong nguồn tri thức. 1: E ← tập các hạt giống 2: flag ← false 3 : loop until घ rỗng hoặc flag = true 4: घ’ ← घ 5 : for each n ∈घ’ do 6: Г ← tập các ứng viên của n 7: if Г khơng rỗng then 8: γ* ← ][ ∈ γscore Γγ maxarg 9: ánh xạ n vào γ* 10: E ← revised(E ∪ {}) /* hàm revised điều chỉnh tập E dựa trên quan hệ đồng tham chiếu của n với các tên khác */ 11: xĩa n khỏi घ 12:        end if 13: end for 14: if tập E khơng thay đổi so với vịng lặp trước then flag = true 15: end loop 20 Chương 1.Giới thiệu Nguồn tri thức Mục tiêu của các phương pháp được đề xuất trong luận án là ánh xạ các tên trong văn bản vào đúng thực thể trong một nguồn tri thức mà các tên đĩ đề cập đến. Do vậy, việc khảo sát các nguồn tri thức khác nhau, chọn lựa nguồn tri thức phù hợp, và đề xuất cách thức khai thác chúng nhằm phục vụ cơng việc phân giải nhập nhằng là thật sự cần thiết. Hiện nay, cĩ nhiều nguồn tri thức sẵn cĩ trên Internet để khai thác cho việc phân giải nhập nhằng, như Cyc (Lenat, 1995) hoặc Wikipedia. Các nguồn tri thức đĩ cĩ thể chia thành ba nhĩm. Nhĩm thứ nhất là các nguồn tri thức được xây dựng thủ cơng bởi một nhĩm nhỏ các chuyên gia, như WordNet hoặc ontology của KIM (Kiryakov và CS, 2005). Nội dung thơng tin trong các nguồn tri thức này được đầu tư bài bản và kiểm duyệt kỹ lưỡng, do đĩ cĩ độ tin cậy cao. Các nguồn tri thức đĩ mặc dù tốn nhiều thời gian và cơng sức để xây dựng, nhưng giới hạn về kích thước và mức độ bao phủ các chủ đề thơng tin. Tần suất cập nhật thơng tin trong các nguồn tri thức nhĩm thứ nhất cũng khơng cao. Lấy một ví dụ về Cyc ontology, theo Matuszek và CS (2006), sau 22 năm xây dựng, Cyc ontology chỉ chứa thơng tin mơ tả cho 250.000 thực thể và khái niệm5. Nhĩm thứ hai là các nguồn tri thức được xây dựng tự động, ví dụ như YAGO (Suchanek và CS, 2007), DBpedia (Auer và CS, 2007). Các nguồn tri thức được phát triển tự động khơng tốn nhiều cơng sức, tuy nhiên thơng tin được sinh tự động như thế cĩ độ tin cậy khơng sánh bằng với những thơng tin được tạo bởi các chuyên gia. Nhĩm thứ ba là các nguồn tri thức nội dung mở, mọi người đều cĩ thể tham gia đĩng gĩp nội dung thơng tin. Điển hình của nhĩm này là từ điển bách khoa nội dung mở Wikipedia, từ điển được sử dụng rộng rãi nhất hiện nay trên Internet. Các ontology cũng được chia thành ba nhĩm (Syed và CS, 2008). Nhĩm thứ nhất bao gồm các ontology “đĩng và cứng” với một bộ từ vựng được kiểm sốt (controlled vocabu- lary), được xây dựng bài bản bởi các chuyên gia, và thơng tin trong đĩ được kiểm duyệt kỹ lưỡng với độ tin cậy cao, như ontology của KIM (Kiryakov và CS, 2005). Bộ từ vựng đĩ được sử dụng để đề cập đến các khái niệm cĩ quan hệ thứ bậc dựa trên các ràng buộc chặt chẽ. Nhĩm thứ hai bao gồm các ontology “mở” với bộ từ vựng được phát triển tự do, khơng tuân thủ một thể thức cụ thể nào, ngoại trừ các thoả thuận mang tính cộng đồng (nếu cĩ) xuất phát từ người dùng. Các ontology mở như thế cĩ hệ thống các khái niệm 5 Matuszek và CS gọi chung bằng thuật ngữ term 1.3.Phương pháp luận đề xuất 21 phẳng (khơng cĩ thứ bậc), được xây dựng dựa trên sự cộng tác bởi cộng đồng đơng đảo các tình nguyện viên, cũng chính là cộng đồng người sử dụng. Nhĩm thứ ba bao gồm các ontology “mở” cĩ những tính chất pha trộn giữa nhĩm thứ nhất và nhĩm thứ hai. Điển hình cho nhĩm này là từ điển bách khoa Wikipedia. Hệ thống phân loại của Wikipedia vừa cĩ thứ bậc, vừa là hệ thống mở, được xây dựng và phát triển bởi cộng đồng đơng đảo các tình nguyện viên. Luận án này khai thác các ontology đĩng và Wikipedia như là các nguồn tri thức để phân giải nhập nhằng các thực thể cĩ tên. Wikipedia là kho tri thức đa ngơn ngữ lớn nhất hiện nay và đang lớn mạnh về cả số lượng lẫn chất lượng. Nội dung của Wikipedia được tạo ra bởi hàng trăm nghìn tình nguyện viên. Tính đến 31 tháng 10 năm 2009, Wikipedia cĩ hơn 14,4 triệu mục tin cho 269 ngơn ngữ khác nhau (Wikimedia, 2009); và mỗi mục tin chứa thơng tin mơ tả về một thực thể hoặc một khái niệm. Theo Angwin và Fowler (2009), trang Wikipedia.org là trang web phổ biến đứng thứ 5 trên thế giới, với hơn 325 triệu lượt truy cập hàng tháng. Các số liệu vừa nêu cho thấy Wikipedia là từ điển bách khoa lớn nhất và được truy cập rộng rãi nhất hiện nay. Mặc dù được xây dựng từ cộng đồng đơng đảo các tình nguyện viên, nội dụng trên Wikipedia lại cĩ chất lượng và độ tin cậy cao. Một nghiên cứu của Giles (2005) chứng minh rằng các bài viết về khoa học trên Wikipedia đạt gần tới mức chính xác như các bài viết với mục đích tương tự trên từ điển bách khoa tồn thư Britannica6 - bộ bách khoa tồn thư tiếng Anh lâu đời nhất và được nhiều người cho là cĩ uy tín nhất. Kết quả nghiên cứu cho thấy, tính bình quân, mỗi bài viết trên Wikipedia cĩ 3,86 lỗi (162 lỗi trên 42 bài viết), so với mức 2,92 lỗi (123 lỗi trong 42 bài viết) trong mỗi bài viết trên Britannica. Chính vì đạt được độ tin cậy khá cao như vậy cho nên cĩ rất nhiều nghiên cứu khai thác Wikipedia để phát triển các ứng dụng trong các mảng truy hồi thơng tin, rút trích thơng tin, xây dựng ontology, phân loại văn bản, và xử lý ngơn ngữ tự nhiên nĩi chung. Một khảo sát của Me- delyan và CS (2009) minh chứng điều đĩ. Hơn nữa, Wikipedia khơng chỉ được sử dụng rộng rãi như một từ điển mà cịn được khai thác như một cơ sở tri thức trong nhiều cơng trình nghiên cứu về các hệ thống trí tuệ nhân tạo và thơng tin thơng minh7. 6 7 Tham khảo tại: 22 Chương 1.Giới thiệu Đặc trưng Để đạt được hiệu quả cao trong việc ánh xạ các tên trong một văn bản vào đúng thực thể mà nĩ đề cập, một vấn đề quan trọng được đặt ra là ngữ cảnh của văn bản được khai thác như thế nào và các đặc trưng nào được rút trích để biểu diễn các thực thể được đề cập đến trong văn bản, cũng như các thực thể trong nguồn tri thức được sử dụng. Luận án này chủ trương khai thác các đặc trưng diễn đạt các tính chất (property) của các thực thể. Tính chất của các thực thể được thể hiện qua các thuộc tính (ví dụ: họ tên, ngày sinh, nghề nghiệp, sở thích, . . .) và mối quan hệ của chúng (ví dụ: Hillary Rodham Clinton là_vợ_của Bill Clinton, Việt Nam cĩ_thủ_đơ_là Hà Nội, Texas là_tiểu_bang_của Mỹ, . . .). Chúng tơi tập trung vào các văn bản trong lĩnh vực tin tức, ở đĩ NE xuất hiện rộng khắp và đĩng một vai trị quan trọng trong việc hiểu ngữ nghĩa của văn bản. Trong lĩnh vực này, các văn bản thường được tổ chức theo cấu trúc kim tự tháp và bao gồm ba phần chính đĩ là phần tiêu đề (headline), phần đầu (the lead) và phần thân (body). Theo đĩ, tầm quan trọng của thơng tin sẽ giảm dần khi văn bản được phát triển theo chiều từ trên xuống. Thơng thường các phần văn bản trong một bản tin sẽ cố gắng trả lời hầu hết các câu hỏi trong chuỗi các câu hỏi cơ bản 5’W (what, where, when, who và why) và H (how)8. Phần tiêu đề cho biết văn bản đề cập đến vấn đề gì. Tiêu đề nằm ở trên cùng của văn bản, thu hút sự quan tâm của người đọc và liên quan chặt chẽ với chủ đề của bản tin tương ứng. Phần đầu là phần tĩm tắt và thường là câu đầu tiên của văn bản. Sau khi đọc phần đầu, người đọc nhiều khả năng sẽ nắm bắt được nội dung chính yếu của bản tin. Phần thân triển khai chi tiết nội dung bản tin. Trong các văn bản, các thực thể đồng xuất hiện thường cĩ mối liên hệ với nhau. Mối liên hệ đĩ cĩ thể được phát biểu tường minh hoặc khơng tường minh trong văn bản. Hơn nữa, định danh của một thực thể cĩ thể được xác định nhờ vào các thực thể bên cạnh và các thực thể đã được xác định trước đĩ. Ví dụ, khi “Atlanta” xuất hiện bên cạnh “Georgia”, “Georgia” nhiều khả năng là đề cập đến tiểu bang Georgia của Mỹ hơn là đề cập đến quốc gia Gruzia. Trong khi đĩ nếu “Georgia” xuất hiện cùng với “Tbilisi”, như trong“TBILISI (CNN) -- Most Russian troops have withdrawn from eastern and western Georgia”, thì chính “Tbilisi” giúp xác định “Georgia” đề cập đến quốc gia nằm kế nước Nga. Trực quan 8 1.3.Phương pháp luận đề xuất 23 cũng cho thấy rằng, các từ xuất hiện xung quanh các tên thực thể nhiều khả năng sẽ diễn đạt các thuộc tính của các thực thể mà chúng đề cập đến. Nếu định vị và rút trích được các từ này, tên nhập nhằng nhiều khả năng sẽ được phân giải chính xác. Ví dụ, trong đoạn văn bản “John McCarthy, 'great man' of computer science, wins major award”, cụm từ “com- puter science” giúp phân biệt John McCarthy được đề cập là giáo sư làm việc tại Stanford University thay vì trọng tài John McCarthy (làm việc tại Ultimate Fighting Championship, Mỹ), hoặc nhà âm vị học người Mỹ (giáo sư ngơn ngữ học làm việc tại Đại học Massachu- setts, Amherst). Khi phân tích các văn bản, chúng tơi quan sát thấy rằng, lần đầu tiên đề cập đến một thực thể, thơng thường các tác giả giới thiệu thực thể đĩ theo một cách tường minh hoặc khơng tường minh sao cho khơng gây ra nhập nhằng cho người đọc, bằng cách sử dụng tên thường dùng của nĩ hoặc chuyển tải thêm thơng tin bên cạnh để người đọc hiểu đĩ là thực thể nào. Ví dụ, trong bản tin cĩ tiêu đề “U.S. on Palestinian government: Hamas is sticking point” trên CNN (ngày 04 tháng 03 năm 2009) cĩ phần đầu “JERUSALEM (CNN) -- U.S. Secretary of State Hillary Clinton on Tuesday ruled out working with any Palestinian unity government that includes Hamas if Hamas does not agree to recognize Israel”, tác giả đề cập đến ngoại trưởng của Mỹ một cách rõ ràng bằng cụm từ “U.S. Secretary of State Hil- lary Clinton”. Sau đĩ trong phần thân của bản tin tác giả viết “Clinton said Hamas must do what the Palestine Liberation Organization has done”, trong đĩ “Clinton” đề cập đến ngoại trưởng Mỹ, mà khơng cần thêm thơng tin để phân biệt với cựu tổng thống Mỹ Bill Clinton. Tuy nhiên, với các thực thể là các vùng địa lý được biết đến rộng rãi, thậm chí nếu tên của nĩ là nhập nhằng, tác giả các văn bản thường đặt các tên đĩ đứng một mình. Trong khi đĩ, đối với các vùng địa lý ít phổ biến hơn, nĩ thường đứng cạnh các thực thể cĩ liên quan. Ví dụ, khi sử dụng “Oxford” để đề cập đến một thành phố ở tiểu bang Mississippi của nước Mỹ, một tác giả cĩ thể viết “Oxford, Mississippi”, ngược lại, khi dùng nĩ để đề cập đến thành phố Oxford ở vùng đơng nam nước Anh, tác giả đĩ chỉ viết “Oxford”. Từ những phân tích nêu trên, chúng tơi quyết định dựa vào các thực thể đồng xuất hiện và các từ xuất hiện xung quanh các tên để rút trích các đặc trưng biểu diễn cho các thực thể mà chúng đề cập (nĩi khác đi là để biểu diễn các tên này). Cụ thể là, khi xem xét phân giải nhập nhằng cho một tên cụ thể trong văn bản, các đặc trưng được khai thác là định danh của các thực thể đã được xác định, các tên xuất hiện trong tồn bộ văn bản, các 24 Chương 1.Giới thiệu từ cùng với các cụm từ xuất hiện xung quanh tên đang xét và xung quanh các tên là đồng tham chiếu với tên đang xét. Đối với các thực thể trong một ontology đĩng, chúng tơi dựa vào các tính chất của chúng, được định nghĩa bởi ontology, để trích các đặc trưng. Đối với các thực thể trong Wikipedia, chúng tơi khai thác nhan đề các trang thực thể, nhan đề các trang đổi hướng, thể loại, các liên kết vào và liên kết ra của các thực thể đĩ để trích các đặc trưng. Qua phân tích các văn bản, chúng tơi nhận thấy rằng vị trí xuất hiện và chiều dài của các tên, cùng với tên thường dùng của các thực thể cũng là các thơng tin quan trọng, giúp xác định đúng thực thể đang được đề cập. Luận án này khai thác các thơng tin vừa nêu để phân giải nhập nhằng. Chúng tơi trình bày chi tiết các cách mà các đặc trưng được sử dụng để phân giải nhập nhằng các thực thể cĩ tên lần lượt trong Chương 3, Chương 4, và Chương 5. 1.4 Những đĩng gĩp chính của luận án Sau đây là những đĩng gĩp chính của luận án này. 1. Đề xuất phương pháp luận phân giải nhập nhằng lặp cải thiện dần. Theo đĩ quá trình phân giải nhập nhằng gồm nhiều vịng lặp. Tại mỗi vịng lặp, định danh của các thực thể đã được xác định sẽ được sử dụng để phân giải nhập nhằng cho các trường hợp cịn lại. Như vậy, một thực thể sau khi được xác định, định danh của nĩ, cùng với định danh của các thực thể đã được xác định trước nĩ, sẽ được dùng để phân giải nhập nhằng cho những trường hợp cịn lại. Quá trình này sẽ diễn tiến cho đến khi nào xác định được định danh của tất cả các thực thể được đề cập đến trong văn bản hoặc giữa hai lần lặp khơng cĩ thêm một ánh xạ mới nào được thực hiện. Cho đến thời điểm hiện tại, theo sự hiểu biết của chúng tơi, đây là đề xuất đầu tiên và duy nhất về phân giải nhập nhằng các thực thể cĩ tên theo một quá trình lặp cải thiện dần. 2. Đề xuất phương pháp phân hạng các thực thể ứng viên dựa trên một ontology. Các ứng viên của một tên nhập nhằng sẽ được phân hạng dựa vào các mối quan hệ ngữ nghĩa của chúng với các thực thể đã được xác định xung quanh tên đĩ. Việc cĩ hay khơng cĩ mối quan hệ giữa hai thực thể được xác định dựa trên một ontology cụ thể. Theo hiểu biết của chúng tơi, khi được xuất bản, phương pháp phân hạng các 1.4.Những đĩng gĩp chính của luận án 25 ứng viên của chúng tơi là phương pháp đầu tiên khai thác các mối quan hệ ngữ nghĩa giữa các thực thể trong một ontology để phân giải nhập nhằng thực thể cĩ tên. 3. Đề xuất một mơ hình phân hạng các ứng viên dựa trên thống kê. Các đặc trưng sẽ được rút trích để hình thành nên các hồ sơ về các thực thể ứng viên từ một nguồn tri thức. Với một tên cần phân giải nhập nhằng, các đặc trưng trên văn bản sẽ được rút trích để hình thành hồ sơ về thực thể được đề cập. Sau đĩ các ứng viên sẽ được phân hạng dựa vào độ tương tự giữa hồ sơ của chúng với hồ sơ của thực thể được đề cập trong văn bản. Chúng tơi sử dụng mơ hình phân hạng này để khai phá các đặc trưng, rút trích từ văn bản, một ontology và Wikipedia, bằng cách đánh giá các kết hợp khác nhau giữa chúng, và phân tích cho thấy rằng các đặc trưng nào là thực sự cĩ ý nghĩa đối với việc phân giải nhập nhằng. Các đặc trưng tốt nhất từ Wikipe- dia sẽ được sử dụng để làm giàu thơng tin mơ tả về các thực thể trong một ontology khác. Sau đĩ, mơ hình phân hạng này cũng được triển khai để phân giải nhập nhằng dựa trên ontology đã được làm giàu. Trong mơ hình phân hạng các ứng viên dựa trên thống kê chúng tơi khai thác các đặc trưng hồn tồn mới so với các nghiên cứu trước là các từ xuất hiện xung quanh các tên đồng tham chiếu với tên đang xét. Hơn nữa, việc khai phá và đánh giá các kết hợp khác nhau giữa các đặc trưng trích từ văn bản và trích từ một ontology cũng chưa được các nghiên cứu trước đề cập đến. 4. Đề xuất một mơ hình lai, kết hợp các heuristic và một mơ hình thống kê, để thực hiện việc phân giải nhập nhằng sử dụng Wikipedia. Việc phân giải nhập nhằng được thực hiện bằng hai giai đoạn. Giai đoạn thứ nhất sử dụng các heuristic để thu giảm các ứng viên, và chọn đúng thực thể nếu cĩ thể, bằng một quá trình lặp cải thiện dần. Giai đoạn hai triển khai một mơ hình phân hạng các ứng viên dựa trên thống kê để phân giải nhập nhằng cho các trường hợp cịn lại. Quá trình phân giải nhập nhằng trong giai đoạn hai cũng là lặp cải thiện dần. Ý tưởng kết hợp các heu- ristic và một mơ hình thống kê để phân giải nhập nhằng các thực thể cĩ tên bằng các quá trình lặp cải thiện dần được chúng tơi đề xuất là đầu tiên và duy nhất cho đến thời điểm hiện tại. 26 Chương 1.Giới thiệu 5. Đề xuất các độ đo mới, để đánh giá hiệu quả phân giải nhập nhằng, phù hợp cả cho các trường hợp khi mà các tên trong văn bản được nhận ra bán phần, và các thực thể được đề cập khơng tồn tại trong nguồn tri thức sử dụng. Các cơng trình khác khơng xem xét đến các trường hợp này. 1.5 Cấu trúc của luận án Mục tiêu của chương này là giới thiệu lịch sử và động cơ nghiên cứu, phát biểu bài tốn, khái quát các phương pháp, trình bày một phương pháp luận hồn tồn mới mà luận án đề xuất áp dụng để phân giải nhập nhằng thực thể cĩ tên và nêu các đĩng gĩp chính của luận án. Các chương cịn lại được tổ chức như sau. Chương 2 – Nền tảng kiến thức Chương này trình bày các kiến thức nền tảng được sử dụng trong luận án. Trước tiên chúng tơi trình bày khái niệm ontology, giới thiệu sơ lược về hệ thống KIM, hệ thống VN- KIM và các ontology của các hệ thống này. Tiếp theo chúng tơi giới thiệu cấu trúc của Wikipedia, các nguồn thơng tin trên Wikipedia mà chúng tơi khai thác để thực hiện việc phân giải nhập nhằng. Sau đĩ, chúng tơi giới thiệu hai cơng việc thuộc phần tiền xử lý của bài tốn NED là nhận dạng thực thể cĩ tên và phân giải đồng tham chiếu tên riêng. Cuối cùng chúng tơi khảo sát các phương pháp luận và phương pháp giải quyết bài tốn NED trong các nghiên cứu về NED cho đến thời điểm hiện tại, trong đĩ phân tích những điểm tương phản và những điểm mới nổi bật của luận án so với các nghiên cứu đĩ. Chương 3 – Phân giải nhập nhằng dựa trên ontology Chương này giới thiệu phương pháp phân hạng các ứng viên dựa trên một ontology mà luận án đề xuất. Với mỗi tên cần phân giải nhập nhằng, phương pháp này dựa vào mối quan hệ ngữ nghĩa của mỗi thực thể ứng viên với các thực thể khác đã được xác định để phân hạng các ứng viên, ứng viên cĩ hạng cao nhất sẽ được chọn như là thực thể đúng. Mối quan hệ đồng tham chiếu giữa các tên xuất hiện trong cùng văn bản cũng được khai thác để phân giải nhập nhằng. Trong chương này chúng tơi cũng trình bày các độ đo mới để đánh giá hiệu quả của các phương pháp phân giải nhập nhằng. Các độ đo mới này phù hợp cả cho các trường hợp khi mà các tên trong văn bản được nhận ra bán phần, và các thực thể được đề cập khơng tồn tại trong ontology hoặc cơ sở tri thức được sử dụng. Các 1.5.Cấu trúc của luận án 27 tập dữ liệu thí nghiệm, và các kết quả đánh giá phương pháp phân hạng các ứng viên dựa trên ontology, sử dụng ontology của KIM trên tập dữ liệu tiếng Anh, và ontology của VN- KIM trên tập dữ liệu tiếng Việt, cũng được trình bày. Nội dung của chương này dựa trên Nguyen và Cao (2007a), Nguyen và Cao (2007b), và Nguyễn Thanh Hiên và Cao Hồng Trụ (2008). Chương 4 – Phân giải nhập nhằng dựa trên ontology được làm giàu Chương này trình bày một mơ hình phân hạng các thực thể ứng viên dựa trên thống kê mà luận án nghiên cứu và đề xuất. Chúng tơi khai phá và đánh giá các đặc trưng rút trích từ văn bản và từ Wikipedia, bằng cách kết hợp chúng theo nhiều cách khác nhau, và chọn lựa các đặc trưng cho kết quả phân giải nhập nhằng tốt nhất. Các đặc trưng trích từ Wikipedia, được xem là gĩp phần quan trọng vào việc nâng cao hiệu quả phân giải nhập nhằng, sẽ được sử dụng để làm giàu thơng tin mơ tả về các thực thể trong một ontology khác. Sau đĩ, mơ hình phân hạng các thực thể ứng viên dựa trên thống kê được triển khai để ánh xạ lần lượt mỗi tên trong một văn bản vào đúng thực thể mà nĩ đề cập đến trong ontology đã được làm giàu. Chúng tơi cũng trình bày tập dữ liệu thí nghiệm, các kết quả đánh giá phương pháp phân giải nhập nhằng dựa trên ontology của KIM được làm giàu bởi Wikipedia. Nội dung chương này dựa trên Nguyen và Cao (2008a), Nguyen và Cao (2010a), Nguyen và Cao (2010b), Nguyễn Thanh Hiên và Cao Hồng Trụ (2010). Chương 5 – Phân giải nhập nhằng dựa trên Wikipedia Chương này trình bày phương pháp lai để phân giải nhập nhằng dựa trên Wikipedia mà chúng tơi nghiên cứu và đề xuất trong luận án. Trong đĩ Wikipedia vừa được sử dụng như là một nguồn cung cấp các đặc trưng phục vụ việc phân giải nhập nhằng, vừa là nguồn thực thể ứng viên mà phương pháp này ánh xạ lần lượt mỗi tên xuất hiện trong một văn bản vào. Quá trình phân giải nhập nhằng gồm hai giai đoạn, một giai đoạn dùng heuristic và một giai đoạn dùng thống kê. Mỗi giai đoạn đều lặp cải thiện dần. Tập dữ liệu thí nghiệm và các kết quả đánh giá cũng được chúng tơi trình bày. Nội dung chương này dựa trên Nguyen và Cao (2008b). Chương 6 – Tổng kết Chương này tĩm lược nội dung của luận án, các đĩng gĩp của luận án, và đề nghị các hướng nghiên cứu trong tương lai dựa trên các kết quả đạt được. 28 Chương 2 NỀN TẢNG KIẾN THỨC 2.1 Giới thiệu Phân giải nhập nhằng thực thể cĩ tên đĩng vai trị quan trọng trong nhiều ứng dụng khác nhau như đã được trình bày trong Phần 1.1. Trong luận án này, chúng tơi trình bày phân giải nhập nhằng thực thể cĩ tên trong ngữ cảnh của một ứng dụng rút trích thơng tin. Rút trích thơng tin là cơng việc phân tích các nguồn dữ liệu phi cấu trúc hoặc bán cấu trúc để tự động rút trích các thơng tin cĩ cấu trúc như các thực thể, mối quan hệ giữa các thực thể, thuộc tính mơ tả các thực thể (Sarawagi, 2008). Hình 2.1: Một số lớp xử lý của một ứng dụng rút trích thơng tin Các lớp xử lý Tách câu Gán nhãn từ loại Tách token Nhận dạng thực thể cĩ tên Phân giải đồng tham chiếu Phân giải nhập nhằng thực thể cĩ tên MUC CoNLL ACE ACE, MUC Tổ chức đánh giá 2.2.Ontology 29 Trong hai thập niên qua, phạm vi của rút trích thơng tin chịu sự tác động chính bởi chuỗi các hội nghị Message Understanding Conference – MUC (Sundheim, 1991; Grishman và Sundheim, 1996; Chinchor, 1998) và ACE (Doddington và CS 2004; NIST 2008). Hình 2.1 trình bày một số lớp xử lý của một ứng dụng rút trích thơng tin, trong đĩ phân giải nhập nhằng là một lớp đắp thêm vào sau nhận dạng thực thể cĩ tên và phân giải đồng tham chiếu. Nhận dạng thực thể cĩ tên và phân giải đồng tham chiếu được xem như là phần tiền xử lý của phân giải nhập nhằng thực thể cĩ tên. Trong chương này, chúng tơi trình bày những kiến thức cơ bản được sử dụng trong luận án. Phần 2.2 trình bày khái niệm ontology. Phần 2.3 trình bày cấu trúc của Wikipedia, các nguồn thơng tin trong đĩ mà chúng tơi rút trích để phân giải nhập nhằng. Phần 2.4 trình bày cơ bản về mơ hình khơng gian véctơ. Phần 2.5 trình bày vấn đề nhận dạng thực thể cĩ tên, tổng quan về các phương pháp giải quyết vấn đề này, và các độ đo dùng để đánh giá hiệu quả của các hệ thống nhận dạng thực thể cĩ tên. Phần 2.6 trình bày cơ bản về phân giải đồng tham chiếu tên riêng và phương pháp phân giải đồng tham chiếu tên riêng áp dụng cho tiếng Việt. Phần 2.7 trình bày tổng quan các phương pháp phân giải nhập nhằng cho đến thời điểm hiện tại. Cuối cùng Phần 2.8 tĩm lược những vấn đề đã được trình bày trong chương này. 2.2 Ontology Thuật ngữ ontology bắt nguồn từ triết học. Trong ngữ cảnh của triết học, ontology là tên của một mảng nghiên cứu về bản chất của sự tồn tại vạn vật trong tự nhiên, một nhánh của siêu hình học, quan tâm xác định các loại sự vật nào là thật sự tồn tại và bằng cách nào mơ tả chúng. Chẳng hạn như quan sát thế giới thực được hình thành từ những sự vật cụ thể mà cĩ thể nhĩm chúng thành các lớp trừu tượng dựa trên các tính chất chung của chúng (Antoniou và Van Harmelen, 2004). Những năm gần đây, ontology được biết đến rộng rãi trong lĩnh vực khoa học máy tính. Cùng với sự nổi lên của Web cĩ ngữ nghĩa, ontology vừa được xem là “linh hồn” của Web cĩ ngữ nghĩa, vừa mang một ý nghĩa khác xa so với nghĩa ban đầu của nĩ. Thật vậy, một định nghĩa của các ontology được chấp nhận rộng rãi trong cộng đồng khoa học máy tính hiện nay là: “một ontology là đặc tả của một sự khái niệm hĩa” (Gruber, 1995; Guarino, 1998). Một “sự khái niệm hĩa” (conceptualization) là một gĩc nhìn đơn giản hĩa về thế giới (world) mà ta mong muốn biểu diễn nhằm một mục 30 Chương 2.Nền tảng kiến thức đích nào đĩ (Gruber, 1995). Sự đặc tả (specification) là tường minh và hình thức. Đặc tả tường minh nghĩa là các khái niệm và các ràng buộc về ngữ nghĩa và quan hệ giữa các khái niệm được định nghĩa cụ thể và rõ ràng. Đặc tả hình thức là nhằm cho máy tính hiểu và suy diễn. Luận án này sử dụng ontology theo nghĩa của cộng đồng khoa học máy tính. Theo nghĩa đĩ, ontology là một danh từ đếm được và được sử dụng để đề cập đến một sản phẩm kỹ nghệ, bao gồm một bộ từ vựng được sử dụng để mơ tả một thực tại nào đĩ và một tập các giả định tường minh về ý nghĩa của các từ trong bộ từ vựng (Guarino, 1998). Tập từ vựng và giả định đĩ hình thành nên các khái niệm và quan hệ giữa các khái niệm trong ontology. Nĩi một cách khác, một ontology là một sự biểu diễn khơng nhập nhằng của các khái niệm và mối quan hệ giữa các khái niệm (Hepp và CS, 2006). Biểu diễn khơng nhập nhằng hiểu theo nghĩa là sự biểu diễn đĩ vừa giúp cho con người nắm bắt một cách chính xác ý nghĩa của các khái niệm, vừa cĩ ngữ nghĩa hình thức để máy cĩ thể nắm bắt và suy diễn. Như vậy, ontology định nghĩa khung tổng quát để mơ tả các thực thể, các thuộc tính và mối quan hệ cụ thể giữa chúng (gọi chung là các tính chất). Khung tổng quát đĩ bao gồm các khái niệm (các lớp và các tính chất)9, và các tiên đề thiết lập các ràng buộc cho các tính chất và biểu diễn mối quan hệ giữa các lớp. Hiện nay cĩ nhiều quan niệm khác nhau về ontology. Một quan niệm cho rằng một ontology định nghĩa khung tổng quát để mơ tả các thực thể, và tập các thực thể cùng với các tính chất của chúng được xây dựng dựa trên ontology đĩ hình thành nên một cơ sở tri thức (Noy và McGuinness, 2001; Kirya- kov và CS, 2005); nghĩa là ontology và cơ sở tri thức là tách biệt. Cơ sở tri thức theo cách hiểu của các tác giả vừa nêu là bao gồm cả khung tổng quát, các thực thể, cùng với thuộc tính và quan hệ cụ thể giữa các thực thể này. Tuy nhiên, Noy và McGuinness (2001) cũng thừa nhận rằng ranh giới giữa ontology và cơ sở tri thức là mờ nhạt. Trong khi đĩ, cĩ một quan niệm khác cho rằng ontology bao gồm một lược đồ và một cơ sở tri thức (Dill và CS, 2003; Antoniou và Harmelen, 2004; Aleman-Meza và CS, 2006; Suchanek và CS, 2007; Bizer và CS, 2009). Lược đồ định nghĩa khung tổng quát như trên. Cơ sở tri thức chứa các thực thể, các thuộc tính và mối quan hệ giữa chúng. Như vậy, trên thực tế cĩ nhiều tài liệu sử dụng thuật ngữ ontology hoặc cơ sở tri thức với ý nghĩa bao 9 Một số nghiên cứu xem các khái niệm trong một ontology chính là các lớp 2.2.Ontology 31 gồm cả khung tổng quát, các thực thể, cùng với thuộc tính và quan hệ cụ thể giữa các thực thể này. Do đĩ, trong luận án, để đơn giản, nếu khơng cần phân biệt và khơng gây mập mờ, chúng tơi sử dụng hai thuật ngữ này thay thế cho nhau. Theo cách tiếp cận truyền thống, một ontology được xây dựng từ trên xuống (top- down) bởi các chuyên gia. Nghĩa là, trước tiên các khái niệm được định nghĩa từ một bộ từ vựng cĩ kiểm sốt (controlled vocabulary) với các ràng buộc giữa các khái niệm được xác định rõ ràng. Tiếp theo, một hệ thống thứ bậc giữa các khái niệm được xây dựng dựa trên mối quan hệ chuyên biệt hĩa (specialization) và tổng quát hĩa (generalization) giữa các khái niệm. Nĩi một cách khác, khi xây dựng một ontology theo tiếp cận truyền thống khung tổng quát được định nghĩa trước. Sau đĩ, khi cĩ một thực thể cần được mơ tả, các khái niệm sẽ được sử dụng. Chúng tơi gọi các ontology được xây dựng theo cách tiếp cận đĩ là các ontology “đĩng”, theo nghĩa là người dùng khơng được phép can thiệp để thay đổi bộ từ vựng, cũng như là các lớp và các tính chất được định nghĩa trong ontology. Các ontology đĩng thường được xây dựng bởi các chuyên gia, chất lượng và độ tin cậy cao, tuy nhiên hạn chế về số lớp và các tính chất được định nghĩa để mơ tả các thực thể. Những năm gần đây, trào lưu Web xã hội (Social Web) đã hình thành các “ontology” chung của cộng đồng người sử dụng. Các ontology này mặc dù khơng thỏa một số các ràng buộc chặt chẽ như các ontology nêu ở trên, nhưng trào lưu Web 2.0 đã củng cố cho khái niệm ontology chung mang tính cộng đồng (Syed và CS, 2009). Các ontology mang tính cộng đồng như thế được xây dựng theo cách tiếp cận từ dưới lên (bottom-up). Nghĩa là khi cần định nghĩa và phân loại một thực thể mới, nếu các khái niệm hiện tại của ontology khơng đủ để mơ tả thực thể, người dùng cĩ thể định nghĩa một khái niệm mới. Ý nghĩa của khái niệm mới đĩ cĩ thể được điều chỉnh sau đĩ dựa trên sự thoả thuận của cộng đồng người dùng. Ontology được xây dựng cĩ tính cộng đồng như vậy cĩ tính “mở”, với bộ từ vựng được phát triển tự do. Chúng tơi gọi các ontology này là các ontology “mở”, hiểu theo nghĩa là người sử dụng cĩ thể dễ dàng thêm vào các khái niệm khi cần. Ngữ nghĩa của các khái niệm đĩ được hình thành từ các thoả thuận mang tính cộng đồng hơn là được định nghĩa bởi một nhĩm chuyên gia. Trong luận án này, chúng tơi khai thác cả các ontology đĩng và mở để phân giải nhập nhằng thực thể cĩ tên. Thơng tin của các ontology đĩng được kiểm sốt kỹ lưỡng, cĩ độ tin cậy cao, nhưng cĩ tần suất cập nhật thấp, hạn chế về mức độ bao phủ các chủ đề thơng tin. Một số định nghĩa hình thức về ontology đĩng cĩ thể tham khảo trong Bloehdorn và CS 32 Chương 2.Nền tảng kiến thức (2005) và Volz và CS (2007). Trong khi đĩ nội dung thơng tin của các ontology mở do cộng đồng người sử dụng tạo nên, cĩ tần suất cập nhật cao, đa dạng về chủ đề thơng tin, nhưng mức độ tin cậy của thơng tin trên các ontology đĩ cịn nhiều tranh cãi. Ontology mở mà chúng tơi sử dụng là Wikipedia. Mặc dù được xây dựng từ cộng đồng đơng đảo các tình nguyện viên, nhưng nội dung thơng tin trên Wikipedia lại cĩ độ tin cậy cao (Giles, 2005). Sau đây chúng tơi giới thiệu các hệ thống mà chúng tơi sử dụng trong các thí nghiệm của luận án này, đĩ là các hệ thống KIM, VN-KIM10 và các ontology của chúng. Cấu trúc và các nguồn thơng tin của Wikipedia sẽ được giới thiệu trong Phần 2.3. Hệ thống KIM và VN-KIM Trong số các hệ thống hướng đến web cĩ ngữ nghĩa hiện nay, KIM và VN-KIM là các hệ thống được nghiên cứu phát triển một cách bài bản và hiệu quả. KIM là một hệ thống quản lý thơng tin và tri thức, dựa trên tri thức về các thực thể cĩ tên phổ biến trên thế giới, và được phát triển cho tiếng Anh. VN-KIM là hệ thống tương tự như KIM, và được phát triển cho tiếng Việt. Trong KIM và VN-KIM, các ontology chứa định nghĩa các lớp thực thể, các thuộc tính và mối quan hệ, các cơ sở tri thức lưu trữ các thơng tin mơ tả về các thực thể và các mối quan hệ giữa chúng dựa trên ontology tương ứng. Các hệ thống này rút trích tự động các lớp thực thể trên các trang web và chú thích lại trên chính các trang web đĩ. Hình 2.2 minh họa VN-KIM nhận diện các thực thể cĩ tên xuất hiện trên web Việt, làm nổi bật và liên kết đến mơ tả ngữ nghĩa của chúng trong cơ sở tri thức của VN-KIM. Nĩi một cách khác là các hệ thống KIM và VN-KIM thêm siêu dữ liệu dưới dạng các chú thích ngữ nghĩa cho các thực thể cĩ tên trên các trang web, như được minh họa trong Hình 2.3. Các trang web được mở rộng ngữ nghĩa như thế sẽ được lưu trữ nhằm tìm kiếm hiệu quả hơn so với các động cơ tìm kiếm hiện hành. Ví dụ, truy vấn các thơng tin về thành phố “Sài Gịn” sẽ nhận được các văn bản nĩi về Thành phố Sài Gịn và Thành phố HCM chứ khơng như các động cơ tìm kiếm hiện hành là trả về bất kì văn bản nào chứa cụm từ “Sài Gịn” mặc dù các văn bản đĩ cĩ thể là nĩi về Cơng ty Bánh kẹo Sài Gịn, Trường ĐHCN Sài Gịn, người Sài Gịn, . . . 10 2.2.Ontology 33 Hình 2.2: VN-KIM xử lý và chú thích các thực thể cĩ tên trên một trang web tiếng Việt Hình 2.3: Chú thích ngữ nghĩa Cơng_ty FPT Hà Nội Việt Nam Thủ_đơ Nơi_chốn Quốc_gia lớp lớp lớp lớp cha lớp cha Nguồn tri thức được_định_vị_ở Cty FPT cĩ kế hoạch thành lập trường đại học FPT để đào tạo nguồn nhân lực cơng nghệ thơng tin cho chính cơng ty và đồng thời cung cấp nguồn nhân lực chất lượng cao cho thị trường lao động Việt Nam được_định_vị_ở 34 Chương 2.Nền tảng kiến thức Ontology của KIM - phiên bản miễn phí được sử dụng trong luận án này để phân giải nhập nhằng thực thể cĩ tên trên các văn bản tiếng Anh - chứa 250 lớp, 100 thuộc tính và quan hệ, cùng với 40.000 thực thể cĩ tên được lưu trữ trong cơ sở tri thức của nĩ. Ontology của VN-KIM - phiên bản được sử dụng trong luận án này để phân giải nhập nhằng thực thể cĩ tên trên các văn bản tiếng Việt - chứa 370 lớp, 115 thuộc tính và quan hệ, cùng với hơn 120.000 thực thể cĩ tên phổ biến được lưu trữ trong cơ sở tri thức của nĩ. Hình 2.4 trình bày một ví dụ minh họa cơ sở tri thức của VN-KIM dưới dạng RDF11. Ví dụ cho thấy thực thể “Quận 8” được định vị ở thực thể cĩ định danh /vnkim/vnkimkb.rdf#Thành_phố_cấp_một_41 (TP. Hồ Chí Minh). Hình 2.4: RDF biểu diễn mối quan hệ giữa các thực thể trong cơ sở tri thức của VN-KIM Động cơ rút trích thơng tin của KIM và VN-KIM dựa trên GATE (Cunmingham và CS, 2002) - một kiến trúc tổng quát để phát triển các ứng dụng xử lý ngơn ngữ tự nhiên. GATE cĩ thể xử lý các tài liệu cĩ các định dạng khác nhau như HTML, XML, RTF, hay SGML. Hình 2.5 minh họa một mơ hình xử lý của một động cơ rút trích thơng tin dựa trên GATE, cho thấy sau khi thực thi mơđun So trùng cụm từ các thực thể sẽ được nhận dạng và phân lớp dựa trên nguồn tri thức sử dụng. Các mơđun theo sau đĩ cĩ thể cĩ hoặc khơng cĩ, và thứ tự xử lý cĩ thể thay đổi tùy theo hệ thống. Một số mơđun cơ bản là: • Tách từ: tách văn bản thành các từ cĩ nghĩa, các con số, các kí tự đặc biệt. 11 Định danh của thực thể Tên thực thể Mối quan hệ 2.2.Ontology 35 • So trùng cụm từ: thực hiện so trùng chính xác các từ (hoặc cụm từ) trong văn bản với các tên khác nhau của các thực thể trong nguồn tri thức sử dụng và sinh ra các chú thích ngữ nghĩa tạm thời. Mỗi chú thích này cĩ thể chứa thơng tin về lớp và định danh của thực thể tương ứng. • Tách câu: thực hiện cơng việc tách văn bản thành các câu. Mỗi câu sẽ được xử lý tách biệt bởi các mơđun phía sau. • Gán nhãn từ loại: xác định loại từ (ví dụ: danh từ, động từ, tính từ, . . .) nhằm cung cấp các thơng tin về các từ xuất hiện xung quanh các tên thực thể. • So trùng mẫu: dựa trên một tập các luật viết dựa trên văn phạm JAPE (Cunming- ham và CS, 2000) được sử dụng để hiệu chỉnh lại các thơng tin rút trích được bởi thành phần so trùng cụm từ và nhận dạng thêm các thực thể cĩ tên chưa cĩ trong cơ sở tri thức. Hình 2.5: Một mơ hình xử lý của một động cơ rút trích thơng tin dựa trên GATE Tách từ Tách câu …… … …….. So trùng cụm từ So trùng mẫu Văn bản đã được chú thích ngữ nghĩa Nội dung văn bả