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ở

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 

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 

pdf164 trang | Chia sẻ: netpro | Lượt xem: 1696 | Lượt tải: 8download
Bạn đang xem trước 20 trang tài liệu 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ở, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CS (2003), Rough và CS (2003), Pouliquen và CS (2004), Andogah và CS (2008) chọn vùng địa lý có dân số đông nhất. Schilder và CS (2004) thiết lập mặc định cho các ứng viên là thủ đô, hoặc thủ phủ của một vùng khi chỉ có một ứng viên thuộc các lớp này. Buscaldi và Rosso (2008) đề xuất và đánh giá hai phương pháp phân giải nhập nhằng; một phương pháp dựa trên bản đồ và một phương pháp dựa trên ontology (cụ thể là WordNet). Đối với phương pháp dựa trên bản đồ, ứng viên của một tên nhập nhằng sẽ được chọn nếu khoảng cách của nó đến trọng tâm của tài liệu là nhỏ nhất. Đối với phương pháp dựa trên ontology, ứng viên của một tên nhập nhằng sẽ được chọn nếu mật độ khái niệm (conceptual density) của nó là lớn nhất. Nhìn chung các phương pháp dựa trên luật khai thác các đặc trưng đặc thù đối với các vùng địa lý, do đó khó điều chỉnh để áp dụng cho các thực thể thuộc các lớp khác như con người hay tổ chức. Nhóm thứ hai là nhóm các phuơng pháp áp dụng các kỹ thuật học máy (Smith và Mann, 2003; Garbin và Mani, 2005; Overell và Rüger, 2008). Smith và Mann (2003) xây dựng một tập huấn luyện tự động dựa trên các mẫu như “Nashville, Tenn.” hoặc “Springfield, MA”. Một bộ phân lớp Naive Bayes được huấn luyện dựa trên tập huấn luyện này, và sau đó được áp dụng để phân giải nhập nhằng cho các vùng địa lý trong một tài liệu mới. Garbin và Mani (2005) cũng xây dựng tự động tập huấn luyện bằng cách khai thác các từ xuất hiện trong cửa sổ ngữ cảnh ±5 từ xung quanh tên nhập nhằng. SVM sau đó được triển khai để học một bộ phân lớp, trong đó ±3 (hoặc ±20) token xung quanh các tên nhập nhằng được khai thác như là các đặc trưng. Overell và Rüger (2008) khai thác Wikipedia để phân giải nhập nhằng các vùng địa lý. Các tác giả xem tập các vùng địa lý trong Wikipedia như là tập huấn luyện, trong đó mỗi thực thể được biểu diễn bởi các thông tin rút trích từ infobox của thực thể đó. SVM được triển khai để 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. Trong số các phương pháp học máy áp dụng cho các 2.7.Phân giải nhập nhằng 65 vùng địa lý thì phương pháp của Overell và Rüger (2008) là khả chuyển, và có thể điều chỉnh để áp dụng cho các thực thể khác các vùng địa lý. Mặc dù đã được quan tâm nghiên cứu từ cuối những năm 90, cho đến nay vẫn chưa có một tập dữ liệu mẫu chung để đánh giá và so sánh các phương pháp phân giải nhập nhằng các vùng địa lý khác nhau (Overell, 2009). Hơn nữa, do chỉ tập trung vào các vùng địa lý, các phương pháp chỉ quan tâm đến mối quan hệ giữa các vùng địa lý, bỏ qua mối quan hệ giữa các vùng địa lý với các thực thể khác các vùng địa lý. Theo chúng tôi thì các mối quan hệ này là thật sự có ý nghĩa đối với việc phân giải nhập nhằng các vùng địa lý. Ví dụ, khi “Mikhail Saakashvili” đứng bên cạnh “Georgia”, thì “Georgia” nhiều khả năng là đề cập đến quốc gia Gruzia hơn là tiểu bang Georgia của Mỹ. Phân giải nhập nhằng thực thể có tên Các nghiên cứu phân giải nhập nhằng thực thể có tên tập trung vào các thực thể khác các vùng địa lý cũng thu hút được nhiều sự quan tâm. Hassell và CS (2006) đề xuất phương pháp nhận dạng và ánh xạ từng tên của từng ủy viên hội đồng phản biện trên các trang web hội nghị khoa học vào đúng thực thể mà mỗi tên đó đề cập đến trong một ontology. Các tác giả khai thác tên của tổ chức nơi một người làm việc; mảng nghiên cứu của các ủy viên như web có ngữ nghĩa, cơ sở dữ liệu, . . .; quan hệ đồng tác giả; và số lượng ấn phẩm xuất bản của một người để phân hạng các thực thể ứng viên. Tuy nhiên, các đặc trưng mà nghiên cứu này khai thác là đặc thù đối với các trang web hội nghị khoa học, do đó khó điều chỉnh cho các văn bản thuộc các lĩnh vực khác. Fernandez và CS (2007) đặt mục tiêu nhận dạng các thực thể có tên trên các văn bản trong lĩnh vực tin tức, và ánh xạ chúng vào đúng các thực thể được đề cập đến trong một ontology. Các tác giả khai thác tần suất đồng xuất hiện của các thực thể trong quá khứ, tần suất xuất hiện của các thực thể trong 7 ngày, và tần suất xuất hiện của các thực thể trong 17 chủ đề ở mức cao của các bản tin để phân hạng và chọn các thực thể ứng viên có hạng cao nhất. Phương pháp được đề xuất trong Fernandez và CS (2007) là bán tự động, vì quá trình phân giải nhập nhằng có sự kết hợp giữa người và máy. Điều đó thể hiện ở chỗ, 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 tập dữ liệu huấn luyện sử dụng các kết quả vừa điều chỉnh. Bunescu và Paşca (2006) khai thác Wikipedia để phân giải nhập nhằng. Cụ thể là các tác giả khai thác các nguồn thông tin bao gồm: các trang thực thể, các trang đổi hướng, các 66 Chương 2.Nền tảng kiến thức trang phân giải nhập nhằng, thể loại của các trang thực thể, các liên kết trong các trang thực thể. Các tác giả trước tiên xây dựng một từ điển các thực thể có tên, bằng cách sử dụng một số heuristic để loại đi các trang mô tả đến các khái niệm chung chung, không phải các thực thể có tên. Kết quả thu được một từ điển, mà mỗi mục là một tên xuất hiện trong Wikipedia, và các “nghĩa” của nó là các thực thể có tên trùng với mục đó. Hay nói cách khác là mỗi mục của từ điển liên kết với các ứng viên mà tên tương ứng đề cập đến trong Wikipedia. Ví dụ, với mục “John Williams”, “nghĩa” của nó gồm có các thực thể được mô tả bởi các trang thực thể có nhan đề “John Williams (composer)”, “John Williams (wrestler)”, “John Williams (VC)”, . . . Các liên kết trong các trang của Wikipedia được khai thác để xây dựng tập dữ liệu huấn luyện. Cụ thể là, 55 từ xung quanh một liên kết sẽ được rút trích để xây dựng tập dữ liệu huấn luyện. Bảng 2.4 trình bày một ví dụ minh họa về tập mẫu mà Bunescu và Paşca (2006) xây dựng dựa vào các liên kết, trong đóδ nhận giá trị 1 khi thực thể là câu trả lời đúng của truy vấn, ngược lại δ nhận giá trị 0. Bảng 2.4: Minh họa tập dữ liệu huấn luyện của Bunescu và Paşca (2006) δ Truy vấn Thực thể 1 Boston Pops conduct ... John Williams (composer) 0 Boston Pops conduct ... John Williams (wrestler) 0 Boston Pops conduct ... John Williams (VC) 1 lost Taipei match ... John Williams (composer) 0 lost Taipei match ... John Williams (wrestler) 0 lost Taipei match ... John Williams (VC) 1 won Victoria Cross ... John Williams (composer) 0 won Victoria Cross ... John Williams (wrestler) 0 won Victoria Cross ... John Williams (VC) Các truy vấn trong tập dữ liệu huấn luyện được biểu diễn bởi các véctơ, và các thực thể trong Wikipedia cũng được biểu diễn bởi các véctơ, với mỗi chiều của một véctơ (véctơ truy vấn hoặc véctơ thực thể) tương ứng với một từ trong tập các từ trích từ tất cả các trang thực thể trong Wikipedia. Mô hình học có giám sát SVM được triển khai để phân hạng các ứng viên dựa trên hai yếu tố là cosine giữa véctơ truy vấn và véctơ thực thể, và 2.7.Phân giải nhập nhằng 67 mức độ tương quan giữa các từ trong truy vấn và các từ xuất hiện trong nhãn thể loại của thực thể tương ứng (ví dụ: “concert” có tương quan với nhãn thể loại “Musicians” mạnh hơn so với nhãn thể loại “Professional Wrestlers”). Cucerzan (2007) cũng đề xuất phương pháp phân giải nhập nhằng thực thể có tên dựa trên Wikipedia, khai thác các nguồn thông tin trên Wikipedia như trong Bunescu và Paşca (2006). Tác giả dựa vào nhan đề của các trang thực thể, nhan đề của các trang đổi hướng, nhãn của các liên kết trong các trang phân giải nhập nhằng, nhãn của các thể loại của các trang thực thể, và nhãn của các liên kết trong các trang thực thể để xây dựng một cơ sở dữ liệu về các thực thể có tên trong Wikipedia. Cơ sở dữ liệu này lưu trữ mối quan hệ nhiều- nhiều giữa các tên và các thực thể, cho thấy một tên đề cập đến bao nhiêu thực thể khác nhau, một thực thể có bao nhiêu tên khác nhau, và các đặc trưng biểu diễn các thực thể đó. Cụ thể, tác giả trích hai loại đặc trưng sau để biểu diễn mỗi thực thể: • Nhãn của tất cả các thể loại của thực thể; • Ngữ cảnh của thực thể. Ngữ cảnh của một thực thể, theo Cucerzan (2007), bao gồm nhãn của các liên kết ra xuất hiện trong đoạn đầu tiên của trang thực thể tương ứng, và phần văn bản phân giải nhập nhằng trên nhan đề của các trang thực thể (ví dụ: “TV series” được xem là một đặc trưng thuộc ngữ cảnh của thực thể được mô tả bởi trang có nhan đề “Texas (TV series)”. Mỗi đặc trưng được tác giả xem là một ngữ cảnh. Cucerzan (2007) thực hiện phân giải nhập nhằng đồng thời cho tất cả tên xuất hiện ở các vị trí khác nhau trong văn bản, bằng cách tính toán để chọn một bộ các ứng viên phù hợp cho tất cả các tên, thông qua việc cực đại sự hòa hợp giữa thể loại của các ứng viên được chọn và cực đại độ tương tự giữa ngữ cảnh của văn bản và ngữ cảnh của các ứng viên được chọn. Lưu ý là phương pháp của Cucerzan (2007) mở rộng ngữ cảnh của văn bản sử dụng thể loại của tất cả các ứng viên. Cách phân giải đồng thời tất cả các tên trong một văn bản như thế sẽ dẫn đến giải bài toán NP-khó (Kulkarni và CS, 2009; Pilz và CS, 2009). Fader và CS (2009) dựa trên ý tưởng của Bunescu và Paşca (2006), Cucerzan (2007), và Medelyan và CS (2008). Chúng tôi (Nguyen và Cao, 2008a, 2008b) không xây dựng mô hình đồng thời cho các tên, mà xây dựng từng mô hình riêng rẽ cho từng tên một. Cả Bunescu và Paşca (2006) và Cucerzan (2007) đều xây dựng các véctơ với số chiều lớn. Số chiều của mỗi véctơ trong 68 Chương 2.Nền tảng kiến thức phương pháp của Bunescu và Paşca (2006) bằng tổng các từ trích từ các trang thực thể trong Wikipedia. Số chiều của mỗi véctơ trong phương pháp của Cucerzan (2007) bằng tổng số nhãn các thể loại trong hệ thống phân loại của Wikipedia và các ngữ cảnh của các thực thể. Trong khi đó, bởi vì số ứng viên có thể dễ dàng xác định được thông qua bước truy hồi ứng viên, do đó các phương pháp của chúng tôi xây dựng mô hình không gian véctơ cho mỗi tên dựa vào các đặc trưng rút trích để biểu diễn các ứng viên của tên đó; điều này giúp thu giảm đáng kể số chiều của các véctơ. Phân giải nhập nhằng các từ khóa Vài năm gần đây, một số công trình nghiên cứu đã thực hiện rút trích các từ khóa quan trọng trong một văn bản, bao gồm cả tên riêng, sau đó ánh xạ chúng vào đúng trang mô tả ngữ nghĩa của từ khóa đó trong Wikipedia. Các phương pháp đề xuất bao gồm hai bước chính đó là rút trích các từ khóa (hay các cụm từ đặc trưng) trong một văn bản và phân giải nhập nhằng khi từ khóa này có nhiều nghĩa được tìm thấy trong Wikipedia. Ở bước thứ nhất, trước tiên các n-gram (cụm từ có n token) sẽ được xác định, sau đó các n-gram được xem là ít quan trọng đối với văn bản sẽ bị loại bỏ. Thường thì các n-gram bị loại là các n-gram khi bị thay đổi sẽ không làm ảnh hưởng đến ngữ nghĩa của văn bản. Như vậy, vấn đề ở bước thứ nhất là làm sao biết các cụm từ nào là các từ khóa quan trọng đối với một văn bản. Một số phương pháp sử dụng độ đo sự đặc trưng của một cụm (keyp- hraseness) để xác định mức độ quan trọng của một cụm từ đối với một văn bản. Các cụm từ nào có giá trị độ đo sự đặc trưng vượt qua một ngưỡng thực nghiệm sẽ được chọn như là các từ khóa của văn bản. Mihalcea và Csomai (2007) đề xuất độ đo sự đặc trưng của một cụm bằng cách tính xác suất để một n-gram xuất hiện như là một liên kết trong Wikipedia. Mức độ đặc trưng của một n-gram a được tính bằng tỉ lệ giữa số trang trong Wikipedia mà có chứa a là nhãn của một liên kết và tổng số trang có xuất hiện a. Medelyan và CS (2008) mở rộng phương pháp đo mức độ đặc trưng của Frank và CS (1999) áp dụng cho Wikipe- dia. Milne và Witten (2008) khai thác ngữ cảnh xung quanh các liên kết trong Wikipedia để học các khái niệm nên hay không nên ánh xạ một n-gram vào một trang trong Wikipe- dia. Bước thứ hai là thực hiện phân giải nhập nhằng cho các từ khóa có nhiều nghĩa trong Wikipedia. Mihalcea và Csomai (2007) đề xuất hai phương pháp, một phương pháp dựa trên tri thức (Lesk, 1986) và một phương pháp học có giám sát (Mihalcea, 2007). Các tác 2.7.Phân giải nhập nhằng 69 giả xem Wikipedia như là một tập dữ liệu huấn luyện, mỗi trang thực thể trong Wikipedia là một tài liệu với các liên kết là các nhãn. Từ đang xét, 3 từ đứng trước và 3 từ đứng sau nó, cùng với từ loại của chúng được sử dụng như là các đặc trưng. Medelyan và CS (2008) phân hạng các ứng viên (các nghĩa có thể) của một từ khóa bằng cách khai thác mối quan hệ ngữ nghĩa giữa một từ khóa với ngữ cảnh xuất hiện xung quanh nó và mức độ phổ biến (commonness) của ứng viên đó trong Wikipedia. Mối quan hệ ngữ nghĩa được tính toán dựa trên sự trùng lắp ngữ cảnh giữa các từ khóa đã được xác định trong văn bản và các liên kết vào của các ứng viên. Các tác giả xem một thực thể a là phổ biến hơn thực thể b trong Wikipedia nếu a có nhiều liên kết vào hơn b. Milne và Witten (2008) mở rộng nghiên cứu của Medelyan và CS (2008) bằng cách điều chỉnh công thức phân hạng ứng viên và triển khai một mô hình học SVM để phân giải nhập nhằng. Cụ thể, các tác giả triển khai mô hình học có giám sát SVM sử dụng mức độ phổ biến và mối quan hệ ngữ nghĩa để học một bộ phân lớp dựa trên tập huấn luyện là các trang thực thể trong Wikipedia, như trong Mihalcea và Csomai (2007), sau đó sử dụng bộ phân lớp này để phân giải nhập nhằng cho các từ khóa trong một tài liệu mới. 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 toá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. Trong Nguyen và Cao (2007a, 2007b) chúng tôi đã đề xuất phương pháp dựa trên mối quan hệ ngữ nghĩa của một ứng viên với ngữ cảnh xuất hiện xung quanh nó để phân hạng ứng viên đó. Mối quan hệ ngữ nghĩa được tính toán dựa vào mối quan hệ dựa trên ontology của ứng viên với các thực thể đã được xác định trong văn bản. Hàm tính toán mối quan hệ ngữ nghĩa của hai thực thể x và y bất kì của chúng tôi chỉ nhận giá trị 0 hoặc 1, cho biết giữa x và y có mối quan hệ hay không. Trong đó mối quan hệ có thể là từ x vào y, từ y vào x, hoặc cả hai chiều. Nhìn chung, khi so sánh với các công trình liên quan đã có, ngoài các điểm tương phản cụ thể như đã phân tích ở trên, điểm nổi bật nhất của luận án là phương pháp luận phân giải nhập nhằng lặp cải thiện dần dựa trên các thực thể đã được xác định. Ý tưởng này chưa được đề cập trong các công trình liên quan. 70 Chương 2.Nền tảng kiến thức Các độ đo hiệu quả phân giải nhập nhằng Để đánh giá hiệu quả của một phương pháp phân giải nhập nhằng thực thể có tên sử dụng một cơ sở tri thức, cần phải có một tập dữ liệu mẫu, trong đó các ánh xạ từ các tên trong các văn bản đến đúng các thực thể trong nguồn tri thức sử dụng được thực hiện thủ công bởi con người. Sau đó cần định nghĩa một ánh xạ được thực hiện bởi một phương pháp phân giải nhập nhằng nào đó là đúng hay sai so với ánh xạ tương ứng do con người thực hiện. Điều này được thực hiện bằng cách so sánh ánh xạ của phương pháp với ánh xạ tương ứng trong tập dữ liệu mẫu. Cuối cùng, cần định nghĩa các độ đo để đánh giá sự sai lệch giữa các ánh xạ thực hiện bởi một phương pháp phân giải nhập nhằng và các ánh xạ chuẩn vàng. Các độ đo độ chính xác, độ đầy đủ và độ F đã được sử dụng rộng rãi để đánh giá hiệu quả nhận dạng thực thể có tên, truy hồi tài liệu, phân giải nhập nhằng ngữ nghĩa từ vựng, phân giải nhập nhằng thực thể có tên, . . . Các công thức tính toán độ chính xác, độ đầy đủ và độ F đã được trình bày trong Phần 2.5, trong ngữ cảnh bài toán nhận dạng thực thể có tên. Các độ đo này cũng được áp dụng để đánh giá hiệu quả của các phương pháp phân giải nhập nhằng thực thể có tên. Khi đánh giá hiệu quả của một phương pháp phân giải nhập nhằng thực thể có tên, các nghiên cứu liên quan tập trung vào các tên đề cập đến các thực thể thật sự tồn tại trong một cơ sở tri thức cụ thể, không quan tâm đến các thực thể nằm ngoài cơ sở tri thức đó. Do đó, một kết quả phân giải nhập nhằng được xem là đúng nếu và chỉ nếu tên tương ứng được ánh xạ vào đúng thực thể trong một cơ sở tri thức; ngược lại kết quả phân giải nhập nhằng được xem là sai. Các nghiên cứu liên quan cũng không xem xét các trường hợp khi các tên xuất hiện trong văn bản được nhận ra bán phần. Sau đây chúng tôi trình bày các độ đo được sử dụng rộng rãi để đánh giá hiệu quả phân giải nhập nhằng trong các nghiên cứu liên quan. Gọi Tall là số ánh xạ chuẩn vàng trên một tập dữ liệu, TC là số ánh xạ thực hiện đúng, TI là số ánh xạ thực hiện không đúng của một phương pháp phân giải nhập nhằng, và TR là tổng của TC và TI. Leidner (2007) đã điều chỉnh các độ đo như được trình bày trong các phương trình (2.1), (2.2) và (2.4) để đánh giá hiệu quả phân giải nhập nhằng thực thể có tên, giới hạn trong các vùng địa lý, trong đó mỗi ánh xạ trả về bởi một hệ thống phân giải nhập nhằng được xem là một response và một ánh xạ chuẩn vàng được xem là một key. Các độ đo được định nghĩa như sau: 2.7.Phân giải nhập nhằng 71 Định nghĩa 2.1: Độ chính xác Độ chính xác P là tỉ lệ giữa tổng số ánh xạ được thực hiện đúng và tổng số ánh xạ được thực hiện bởi một hệ thống phân giải nhập nhằng thực thể có tên. P = R C IC C T T TT T =+ (2.7) Định nghĩa 2.2: Độ đầy đủ Độ đầy đủ R là tỉ lệ giữa số ánh xạ được thực hiện đúng bởi một hệ thống phân giải nhập nhằng thực thể có tên và tổng số ánh xạ chuẩn vàng. R = all C T T (2.8) 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). Tên Ánh xạ đúng (TC) Ánh xạ sai (TI) Tổng số ánh xạ thực hiện (TR) London • • Ontario • • Paris • • Paris • • Buffalo New York Tổng: 3 1 4 P = 13 3 + = 0.75; R = 6 3 =0.50; F = 500750 5007502 .. .x.x + = 0.6 Định nghĩa 2.3: Độ Fβ Cho độ chính xác P và độ đầy đủ R, độ Fβ được định nghĩa như sau: Fβ = RPβ PRβ + )+( 2 2 1 (2.9) 72 Chương 2.Nền tảng kiến thức Định nghĩa 2.4: Độ F (Fβ với β bằng 1) F = RP PR + 2 (2.10) Bảng 2.5 trình bày một ví dụ của Leidner (2007), trong đó các độ đo được sử dụng để đánh giá hiệu quả của một phương pháp phân giải nhập nhằng các vùng địa lý. Số liệu trong Bảng 2.5 cho thấy tổng số ánh xạ thực hiện thủ công là 6, tổng số ánh xạ thực hiện đúng là 3, tổng số ánh xạ sai là 1, và tổng số ánh xạ được thực hiện bởi hệ thống là 4. Độ chính xác và độ đầy đủ là các độ đo bù nhau (hoặc bổ sung cho nhau). Một hệ thống đạt được độ chính xác càng cao thì tỉ lệ giữa các ánh xạ được thực hiện đúng và tổng số ánh xạ được thực hiện bởi hệ thống càng cao, thậm chí hệ thống có thể không thực hiện ánh xạ cho một số tên xuất hiện trong văn bản. Ví dụ, giả sử có năm trường hợp cần thực hiện ánh xạ, nếu hệ thống thực hiện ánh xạ cho hai trường hợp, trong đó có một trường hợp đúng, thì độ chính xác là 1/2 = 50% bất kể ba trường hợp còn lại không được ánh xạ. Ngược lại, một hệ thống đạt được độ đầy đủ càng cao sẽ có tỉ lệ giữa các ánh xạ được thực hiện đúng và các ánh xạ chuẩn vàng càng cao, mà không quan tâm hệ thống thật sự thực hiện bao nhiêu ánh xạ. Lấy lại ví dụ vừa trình bày, độ đầy đủ sẽ là 1/5 = 25%, không quan tâm đến tổng số ánh xạ được thực hiện bởi hệ thống. Như đã giới thiệu ở Phần 2.5, để có một độ đo chung giữa độ chính xác và độ đầy đủ, độ Fβ đã được giới thiệu (van Rijsbergen, 1979), với tham số β là trọng số xác định ảnh hưởng của độ chính xác và độ đầy đủ trong độ đo chung này. Khi trọng số gán cho độ chính xác và độ đầy đủ bằng nhau, độ Fβ trở thành trung bình điều hòa giữa độ chính xác và độ đầy đủ và được định nghĩa như trong phương trình 2.10. Trong thực tế, khi muốn sử dụng độ đo chung giữa độ chính xác và độ đầy đủ, người ta thường dùng độ F (Fβ với β bằng 1) hơn là Fβ với một giá trị β nào đó. 2.8 Kết luận Trong chương này chúng tôi trình bày các kiến thức nền tảng được sử dụng trong luận án, và khảo sát các nghiên cứu về phân giải nhập nhằng thực thể có tên cho đến thời điểm hiện tại. Cụ thể là chúng tôi trình bày định nghĩa một ontology tổng quát, cấu trúc và các nguồn thông tin trên Wikipedia; phân tích ưu và nhược điểm của việc sử dụng ontology đóng và 2.8.Kết luận 73 Wikipedia trong phân giải nhập nhằng. Phần tiền xử lý của các phương pháp được đề xuất trong luận án, bao gồm nhận dạng thực thể có tên và phân giải đồng tham chiếu tên riêng, cũng được trình bày. Hơn nữa, bài toán liên kết bản ghi và phân biệt các thực thể có tên cũng được mô tả khái quát. Trong chương này, chúng tôi đã phác họa một bức tranh toàn cảnh về phân giải nhập nhằng thực thể có tên cho đến thời điểm hiện tại; trong đó, chúng tôi tóm lược ba yếu tố quan trọng đối với một phương pháp phân giải nhập nhằng là nguồn tri thức sử dụng, các đặc trưng được sử dụng để biểu diễn các thực thể, và mô hình phân giải nhập nhằng. Trong quá trình trình bày các nghiên cứu liên quan, chúng tôi có chỉ ra một số điểm mới và sự khác biệt nổi bật trong các phương pháp của chúng tôi so với các phương pháp khác. 74 Chương 3 PHÂN GIẢI NHẬP NHẰNG DỰA TRÊN ONTOLOGY 3.1 Giới thiệu Trong chương này chúng tôi giới thiệu phương pháp phân giải nhập nhằng dựa trên ontol- ogy, được đặt tên là OntoNEON (Ontology-based Named Entity DisambiguatiON). Ý tưởng chủ đạo của phương pháp này là khai thác các thực thể đã được xác định trong văn bản để phân giải nhập nhằng cho các thực thể khác, bằng một quá trình lặp cải thiện dần. Nội dung của chương dựa trên Nguyen và Cao (2007a, 2007b) và Nguyễn Thanh Hiên và Cao Hoàng Trụ (2008). Đóng góp chính của chương này là ý tưởng phân giải nhập nhằng lặp cải thiện dần và mô hình phân hạng các ứng viên dựa trên 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 văn bản. Giả thuyết mà phương pháp OntoNEON dựa trên đó để thực hiện phân giải nhập nhằng là trong một văn bản luôn tồn tại một số thực thể có thể dễ dàng được xác định, tức là tên của chúng không nhập nhằng. Tập các thực thể đó được xem là tập các hạt giống, khởi đầu từ đó, bằng một quá trình lặp cải thiện dần, các thực thể khác được đề cập đến trong văn bản sẽ được xác định. Trong quá trình phân giải nhập nhằng, tập các hạt giống sẽ thay đổi, thể hiện ở chỗ một khi có một thực thể mới được xác định, ngay lập tức nó được bổ sung vào tập các hạt giống, và cứ thế quá trình đó diễn tiến cho đến khi nào tất cả các thực thể được đề cập đến trong văn bản được xác định hoặc giữa hai lần lặp không xác định thêm được thực thể nào. 3.2.Phân hạng ứng viên dựa trên ontology 75 Phần còn lại của chương này được tổ chức như sau. Phần 3.2 trình bày phương pháp phân hạng các ứng viên. Phần 3.3 trình bày các độ đo để đánh giá hiệu quả các phương pháp phân giải nhập nhằng thực thể có tên nói chung. Các độ đo này áp dụng đượ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à thực thể được đề cập trong một văn bản không tồn tại trong cơ sở tri thức được sử dụng. Phần 3.4 trình bày các tập dữ liệu thí nghiệm và các kết quả đánh giá phương pháp được đề xuất. Phần cuối cùng là tổng kết chương. 3.2 Phân hạng ứng viên dựa trên ontology Phần này trình bày phương pháp phân hạng các ứng viên dựa trên mối quan hệ ngữ nghĩa của chúng với ngữ cảnh xung quanh. Với mỗi tên nhập nhằng, chúng tôi áp dụng các heuristic sau để phân hạng các thực thể ứng viên, và chọn ứng viên phù hợp. H1. Phân hạng dựa trên ontology Nếu một ứng viên có nhiều mối quan hệ ngữ nghĩa nhất với các thực thể đã được xác định trong toàn bộ văn bản, thì ứng viên đó được xem là đúng thực thể mà tên đang xét đề cập đến. Ý tưởng là, với một tên cần phân giải nhập nhằng trong một văn bản, giả sử có hai thực thể ứng viên, ứng viên được chọn là ứng viên có tổng số thực thể đã được xác định có mối quan hệ ngữ nghĩa với ứng viên đó nhiều hơn so với tổng số thực thể đã được xác định có mối quan hệ với ứng viên còn lại. Mối quan hệ ngữ nghĩa giữa các thực thể được xác định dựa vào một ontology. Nói cách khác là chúng tôi dựa trên mức độ trùng lắp các thực thể đã được xác định trong văn bản và các thực thể có mối quan hệ với một ứng viên trong ontology để thực hiện việc phân giải nhập nhằng. Ví dụ, giả sử có một con đường ở Hà Nội và một con đường ở Tp. HCM có cùng tên là “Trần Hưng Đạo”. Trong một ontology có chứa thông tin về cả hai con đường này, một có mối quan hệ với Tp. HCM, và một có mối quan hệ với Hà Nội, ngoài ra hai con đường đó không có mối quan hệ nào khác với các thực thể trong cùng ontology. Nếu trong một văn bản mà “Trần Hưng Đạo” xuất hiện cùng với “Tp. HCM”, dựa trên heuristic trên, giải thuật của chúng tôi xác định đây là một con đường ở Tp. HCM. 76 Chương 3.Phân giải nhập nhằng dựa trên ontology Heuristic H1 sử dụng một

Các file đính kèm theo tài liệu này:

  • pdfLuận án tiến sĩ kỹ thuật - Phân giải nhập nhằng thực thể có tên dựa trên các ontology đóng và mở.pdf