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.
164 trang |
Chia sẻ: vietpd | Lượt xem: 1361 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Đề 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ở, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ĐẠ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 ..................