Luận á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ở

ĐẠ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 HOÀ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 Hoà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ự hoà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ể hoà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 hoà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 hoàn thành luận án này. Cảm ơn các anh chị trong Phòng Điện toá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à hoà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 toá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 toá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 soá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. Ngoà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 ngoà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 toá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 toá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 toá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 ..................