Linking Entity

Xử lý ngôn ngữ tự nhiên (Natural Language Processing) ở thời điểm hiện tại có thể coi là một trong những lĩnh vực đang rất được quan tâm ở Việt Nam nói riêng và trên thế giới nói chung. Các bài toán xử lý ngôn ngữ tự nhiên khá thú vị và hữu ích khi đưa vào sử dụng trong các hệ thống hay các ứng dungj hiện đại. Linking Entity cũng là một trong những bài toán gây được sự chú ý với những hiệu quả nó mang lại. Ở bài viết này, mình sẽ giới thiệu sơ lược về bài toán này.

I. Linking Entity là gì?

Để hình dung một cách đơn giản, ta sẽ xét câu nói sau: "Paris là thủ đô của Pháp". Khi câu này xuất hiện trên một văn bản, bạn có thể biết ngay "Paris" ở đây là một thành phố của Pháp, chứ không phải cô diễn viên xinh đẹp người Mỹ - Paris Hilton hay bất kỳ thực thể nào khác có thể được gọi là "Paris". Vậy làm sao ta có thể xác định một thực thể tương tự như vậy trong bất kì một văn bản nào là ai, công ty, trường học, hay vật thể nào. Đó chính là công việc cần thực hiện trong bài toán này. Hay nói một cách hoa mỹ hơn, Linking Entity (thực thể liên kết) là việc xác định danh tính của các thực thể được đề cập trong văn bản.

II. Các vấn đề cơ bản trong bài toán Linking Entity

  • Khó khăn:

Việc xác định danh tính của một thực thể nghe qua có vẻ dễ dàng, nhưng thực chất nó là một bầu trời mênh mông kiến thức để biết được thực thể đó chính xác là gì. Ta cs thể thấy số lượng dữ liệu Web hằng năm tăng lên theo cấp số nhân và đây là một trong những kho dữ liệu lớn nhất của thế giới. Một trong những hệ quả của việc đó chính là ự mơ hồ trong việc xác định thực thể số lượng thực thể tăng cao khiến sự trùng lặp tên gọi là điều không thể tránh khỏi. Khi bạn gõ tên của một thực thể nào đó lên google, có thể có hàng trăm các thực thể khác nhau sẽ hiện ra trước mắt bạn. Chưa kể đến việc một thực thể có nhiều tên gọi khác nhau: tên đầy đủ, tên từng phần, bí danh, chữ viết tắt, và cách viết khác,… Với tất cả các loại tên gọi đó, ta đều cần phải xử lí chúng.

  • Thuận lợi:

Khó khăn là vậy, nhưng ta có thể nhìn thấy mặt tích cực của cộng đồng chia sẻ kiến thức và khai thác thông tin ngày càng phát triển, tạo điều kiện cho việc xây dựng tự động các cơ sở tri thức có quy mô lớn như Wikipedia, Dbpedia, YAGO, Freebase,… Đây chính là những nguồn tài nguyên kiến thức vô giá cho nhân loại, phục vụ cho bài toán Linking Entity.

III. Tóm tắt bài toán

  • Bài toán: Cho một cơ sở tri thức có chứa một tập hợp các thực thể E và một tập các văn bản mà trong đó có một tập hợp các thực thể được đề cập M được xác định trước.
  • Yêu cầu bài toán:
    • Xây dựng liên kết cho mỗi thực thể văn bản đề cập đến m ∈ M đến thực thể tương ứng e ∈ E trong cơ sở tri thức.
    • Đối với những thực thể được đề cập mà không có thực thể tương ứng trong cơ sở tri thức (còn gọi là “unlinkable”), chúng sẽ được gán nhãn là “NIL”.

IV. Các module của một hệ thống Linking Entity

Một hệ thống Linking Entity sẽ gồm 3 module chính sau:

  • Candidate Entity Generation
  • Candidate Entity Ranking
  • Unlinkable Mention Prediction

Mỗi module sẽ thực hiện một công việc khác nhau. Sau đây ta sẽ đi vào từng module:

1. Candidate Entity Generation

Trong module này, với mỗi thực thể được đề cập m ∈ M, hệ thống sẽ cố gắng gom các thực thể có khả năng được m tham chiếu đến thành một tập các “thực thể ứng cử viên” Em (the set of candidate entities Em)

Các phương pháp tiếp cận chủ yếu dựa trên việc so sánh chuỗi giữa hình thức của đề cập đến thực thể và tên của thực thể tồn tại trong cơ sở tri thức. Một số cách tiếp cận như Name Dictionary Based Techniques, Surface Form Expansion From The Local Document, Methods Based on Search Engines,...

Mình sẽ giới thiệu qua về Name Dictionary Based Techniques để các bạn có cái nhìn dễ dàng hơn về việc xây dựng nên một bộ từ điển các thực thể (hay nói cách khác là bộ tri thức) để ứng dụng trong module này. Hiểu đơn giản là tạo ra một từ điển mà có thể tạo các tham chiếu giữa thực thể được đề cập với thực thể trong cơ sở tri thức. Một từ điển gồm 2 cột: cột k (key) và k.value như sau:

Chúng ta có thể xây dựng một từ điển tên D offline dựa vào các tính năng mà Wikipedia cung cấp:

  • Entity pages (Trang thực thể): Mỗi trang thực thể trong Wikipedia mô tả một thực thể đơn lẻ và chứa thông tin tập trung vào thực thể này. Nói chung, tiêu đề của mỗi trang là tên phổ biến nhất cho đối tượng được mô tả trong trang này. Do đó, tiêu đề của trang thực thể được thêm vào cột chính trong D như là một tên k, và thực thể được mô tả trong trang này được thêm vào dưới dạng k.value.
  • Redirect pages (Trang điều hướng): Trang chuyển hướng tồn tại cho mỗi tên thay thế có thể được sử dụng để chỉ một thực thể hiện có trong Wikipedia. Ví dụ: bài viết có tiêu đề "Microsoft Corporation" là tên đầy đủ của Microsoft có chứa một con trỏ tới bài viết của tổ chức Microsoft. Các trang chuyển hướng thường chỉ các từ đồng nghĩa, chữ viết tắt, hoặc các biến thể khác của các thực thể đã được chỉ định. Do đó, tiêu đề của trang chuyển hướng được thêm vào cột chính trong D như là một tên k, và thực thể được chỉ ra là k.value
  • Disambiguation pages (Trang định hướng): Khi nhiều thực thể trong Wikipedia có thể được đặt cùng tên, một trang định hướng được tạo ra để tách chúng và chứa một danh sách các tham chiếu đến các thực thể đó. Đối với mỗi trang định hướng, tiêu đề của trang này được thêm vào cột chính trong D như là một tên k, và các thực thể được liệt kê trong trang này được thêm vào dưới dạng k.value.
  • Bold phrases from the first paragraphs (Cụm từ in đậm từ các đoạn văn đầu tiên): Nói chung, đoạn văn đầu tiên của bài viết Wikipedia là một bản tóm tắt của toàn bộ bài viết. Nó đôi khi có chứa một vài cụm từ viết bằng in đậm. Những cụm từ đậm này luôn là biệt danh, bí danh hoặc tên đầy đủ của thực thể được mô tả trong bài viết này. Do đó, đối với mỗi cụm từ đậm trong đoạn đầu của mỗi trang Wikipedia, nó được thêm vào cột chính trong D như một cái tên k, và thực thể được mô tả trong trang này được thêm vào như là k.value
  • Hyperlinks in Wikipedia articles (Các siêu liên kết trong các bài viết): Một bài viết trên Wikipedia thường chứa các siêu liên kết liên kết đến các trang của các thực thể được đề cập trong bài báo này. Đoạn text của siêu liên kết đc thêm vào cột k, thực thể được trỏ tới là cột k.value.

Có 2 cách để sử dụng từ điển tên để thực hiện module Candidate Entity Generation:

  • Exact Matching (kết nối chính xác): Khi thực thể được đề cập m trùng với tên k thì tập các thực thể trong k.value sẽ được thêm vào tập “thực thể ứng cử viên” Em
  • Partial Matching (kết nối một phần): Với mỗi thực thể được đề cập m, những tên k mà thỏa mãn một trong các luật sau thì k.value sẽ được thêm vào tập “thực thể ứng viên” Em:
    • Tên thực thể chứa thực thể được đề cập (m là chuỗi con của k)
    • Tên thực thể khớp chính xác với chữ cái đầu tiên của tất cả các từ trong thực thể được đề cập (k là tên viết tắt của m)
    • Tên thực thể chia sẻ một số từ thông dụng với thực thể được đề cập.
    • Tên thực thể có một chuỗi tương tự mạnh mẽ với thực thể được đề cập (dựa vào kĩ thuật so sánh chuỗi)

2. Candidate Entity Ranking

Thông thường, tập Em thu được sẽ có kích thước lớn hơn 1. Vì vậy cần phải xếp hạng các thực thể trong Em để tìm ra thực thể “ứng cử viên” phù hợp nhất với thực thể được đề cập m. Đây là module quan trọng nhất của hệ thống.

Ta có thể chia thành 2 loại:

  • Supervided ranking methods (Các phương pháp xếp hạng giám sát): Cách tiếp cận này bao gồm các phương pháp phân lớp nhị phân, các phương pháp xác suất, và cách tiếp cận dựa trên đồ thị.
  • Unsupervided ranking methods (Các phương pháp xấp hạng không giám sát): Các phương pháp tiếp cận này bao gồm phương pháp dựa trên mô hình không gian vector (VSM) và các phương pháp lấy thông tin.

Một số đặc tính hữu ích trong việc xếp hạng:

  • Context-Independent Features (Tính độc lập với ngữ cảnh): Chỉ dựa vào hình thức bề mặt của thực thể được đề cập và kiến thức về thực thể ứng cử viên, mà không liên quan đến bối cảnh nơi đề cập đến thực thể xuất hiện.
    • Name String Comparison (So sánh chuỗi tên): Khi so sánh các choỗi, ta có thể dựa vào một số tiêu chí để đánh giá và cho điểm:
      • Chính xác hoàn toàn
      • Thực thể ứng cử viên bao hàm thực thể được đề cập
      • Số lượng từ bằng nhau
      • Các từ xuất hiện trong thực thể được đề cập có thứ tự giống với thực thể ứng cử viên
    • Entity Popularity (Độ phổ biến của thực thể): Khi một thực thể được đề cập đến có cùng lúc nhiều thực thể ứng cử viên, ta có thể dựa vào độ phổ biến của thực thể. Ví dụ: Khi nhắc đến NewYork thì khả năng nhắc đến “NewYork City” sẽ cao hơn là “NewYork (film)”.
    • Entity Type (Loại thực thể)
  • Context-Dependent Features (Tính phụ thuộc vào ngữ cảnh): Dựa trên ngữ cảnh mà thực thể được đề cập xuất hiện. Ở đây, ngữ cảnh có nghĩa là không chỉ bối cảnh văn bản xung quanh đề cập đến thực thể mà còn các thực thể được đề cập khác cần được liên kết trong cùng một tài liệu.
    • Textual Context (Ngữ cảnh văn bản): So sánh ngữ cảnh xuất hiện xoay quanh thực thể được đề cập đến và thực thể ứng cử viên
    • Coherence Between Mapping Entities (Sự liên kết giữa các thực thể được nối)

Một số các phương pháp có thể áp dụng cho module này:

  • Supervided ranking methods:
    • Binary Classification Methods (Phương pháp phân lớp nhị phân)
    • Learning to Rank Methods (Phương pháp học để xếp hạng)
    • Probabilistic Methods (Phương pháp xác suất)
    • Graph Based Approaches (Cách tiếp cận dựa vào đồ thị)
    • Model Combination (Kết hợp các mô hình)
    • Training Data Generation
  • Unsupervided ranking methods:
    • VSM Based Methods (Phương pháp dựa vào VSM)
    • Information Retrieval Based Methods (Phương pháp dựa vào trích rút thông tin)

3. Unlinkable Mention Prediction

Nếu đối tượng ứng cử thiết là rỗng, hệ thống dự đoán m là không thể liên kết với tập Em đã được tạo ra bởi mô đun Candidate Entity Generation và trả lại NIL cho m.

Một số hệ thống đặt ra ngưỡng điểm để đánh giá thực thể được liên kết có phù hợp với thực thể được đề cập hay không. Nếu kết quả tốt nhất vẫn nhỏ hơn ngưỡng điểm đó thì cũng trả về NIL.

Kết luận

Như vậy là chúng ra đã tìm hiểu một cách ngắn gọn và sơ lược về bài toán Linking Entity cũng như các thành phần chính của một hệ thống Linking Entity. Mong rằng bài viết có thể giúp ích được bạn đọc ở một khía cạnh nào đó. Thanks for reading!

Link tham khảo: http://dbgroup.cs.tsinghua.edu.cn/wangjy/papers/TKDE14-entitylinking.pdf