Luận Văn Thạc Sĩ Khoa Học Máy Tính: Nghiên Cứu Về Tìm Kiếm Và Xếp Hạng Đối Tượng Trên Web

Luận văn thạc sĩ khoa học máy tính tập trung nghiên cứu phương pháp tìm kiếm và xếp hạng đối tượng trên web hiệu quả, ứng dụng công nghệ tiên tiến.

• Tác giả: Nguyễn Văn Trí
• Người hướng dẫn: PGS. Cao Hoàng Trụ
• Trường học: Đại học Bách Khoa - Đại học Quốc gia TP. HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Tìm kiếm và xếp hạng đối tượng trên web
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu đề tài

Luận văn thạc sĩ khoa học máy tính tập trung vào việc tìm kiếm và xếp hạng đối tượng trên web, một hướng nghiên cứu mới so với truy hồi tài liệu truyền thống. Tài nguyên web đã phát triển thành một kho dữ liệu phong phú, nhưng các công cụ tìm kiếm hiện tại vẫn chưa đáp ứng được nhu cầu tìm kiếm các đối tượng cụ thể. Luận văn đề xuất một mô hình tìm kiếm đối tượng, với đầu vào là lớp đối tượng và các từ khóa liên quan, nhằm trả về kết quả trực tiếp thay vì danh sách các liên kết.

1.1 Phát biểu bài toán

Các công cụ tìm kiếm hiện tại như Google, Yahoo, và Bing trả về danh sách các URL, yêu cầu người dùng duyệt qua để tìm thông tin mong muốn. Luận văn đề xuất một phương pháp tìm kiếm hiệu quả hơn, trả về kết quả trực tiếp liên quan đến đối tượng được tìm kiếm. Ví dụ, khi tìm kiếm giáo sư nghiên cứu về trí tuệ nhân tạo, kết quả trả về sẽ là danh sách các giáo sư thay vì các liên kết đến trang web.

1.2 Các công trình liên quan

Luận văn tham khảo các công trình nghiên cứu về rút trích thông tin và xếp hạng đối tượng trên web. Các hệ thống như KnowItAll, WebKnox, và SEAL đã được nghiên cứu để rút trích thực thể có tên và quan hệ giữa chúng. Các phương pháp xếp hạng đối tượng dựa trên đồ thị liên kết và độ tương đồng ngữ nghĩa cũng được đề cập.

II. Cơ sở lý thuyết

Luận văn trình bày các cơ sở lý thuyết về xếp hạng kết quả tìm kiếm và rút trích thực thể có tên. Xếp hạng đối tượng là quá trình sắp xếp các đối tượng theo độ phù hợp với tiêu chí tìm kiếm. Hàm tính hạng (Ranking Function) đóng vai trò quan trọng trong việc xác định thứ tự kết quả trả về. Các phương pháp như PageRank được sử dụng để tính toán độ quan trọng của các trang web dựa trên đồ thị liên kết.

2.1 Sắp xếp kết quả tìm kiếm

Xếp hạng đối tượng là việc sắp xếp các đối tượng theo độ phù hợp với tiêu chí tìm kiếm. Hàm tính hạng kết hợp độ tương tự giữa tài liệu và truy vấn với hạng trang để xác định thứ tự kết quả. Các công cụ tìm kiếm như Google sử dụng phương pháp PageRank để tính toán độ quan trọng của các trang web dựa trên đồ thị liên kết.

2.2 Rút trích thực thể có tên

Rút trích thực thể có tên là quá trình xác định và trích xuất các thực thể cụ thể từ dữ liệu web. Các phương pháp như học có giám sát, học bán giám sát, và học không giám sát được sử dụng để rút trích thực thể từ các tài liệu có cấu trúc và bán cấu trúc.

III. Mô hình EntityRank

Luận văn giới thiệu mô hình EntityRank, một hệ thống xếp hạng đối tượng dựa trên mô hình xác suất. EntityRank tích hợp thông tin cục bộ và toàn cục để xếp hạng các đối tượng trên web. Mô hình này được áp dụng để tìm kiếm và xếp hạng các giáo sư, cho thấy sự khả quan trong việc cải thiện hiệu quả tìm kiếm.

3.1 Động cơ tìm kiếm đối tượng

EntityRank là một hệ thống xếp hạng đối tượng dựa trên mô hình xác suất, tích hợp thông tin cục bộ và toàn cục để xếp hạng các đối tượng trên web. Mô hình này được thiết kế để trả về kết quả trực tiếp liên quan đến đối tượng được tìm kiếm, thay vì danh sách các liên kết.

3.2 Xếp hạng đối tượng

Xếp hạng đối tượng trong EntityRank dựa trên các độ đo xác suất, bao gồm xác suất tài liệu được chọn, xác suất truy vấn đúng trong tài liệu, và xác suất truy vấn trên mô hình ảo. Các độ đo này được kết hợp để xác định thứ tự kết quả trả về.

IV. Hệ thống tìm kiếm giáo sư

Luận văn trình bày việc xây dựng và hiện thực hệ thống tìm kiếm giáo sư dựa trên mô hình EntityRank. Hệ thống này được thiết kế để tìm kiếm và xếp hạng các giáo sư dựa trên các từ khóa liên quan đến lĩnh vực nghiên cứu. Kết quả thử nghiệm cho thấy sự khả quan của phương pháp tiếp cận này.

4.1 Kiến trúc hệ thống

Hệ thống tìm kiếm giáo sư được thiết kế với ba tầng chính: tầng truy nhập, tầng nhận dạng, và tầng đánh giá. Tầng truy nhập xác định xác suất tài liệu được chọn, tầng nhận dạng xác định xác suất truy vấn đúng trong tài liệu, và tầng đánh giá tính toán xác suất truy vấn trên mô hình ảo.

4.2 Hiện thực hệ thống

Hệ thống tìm kiếm giáo sư được hiện thực dựa trên mô hình EntityRank, với các giải thuật tìm kiếm và xếp hạng đối tượng được tối ưu hóa để cải thiện hiệu quả tìm kiếm. Kết quả thử nghiệm cho thấy hệ thống có khả năng trả về kết quả chính xác và nhanh chóng.

V. Kết quả thực nghiệm

Luận văn trình bày kết quả thực nghiệm của hệ thống tìm kiếm giáo sư dựa trên mô hình EntityRank. Các độ đo như Mean Reciprocal Rank (MRR) được sử dụng để đánh giá hiệu quả của hệ thống. Kết quả cho thấy hệ thống có khả năng trả về kết quả chính xác và nhanh chóng, đáp ứng được nhu cầu tìm kiếm đối tượng trên web.

5.1 Đánh giá kết quả

Kết quả thực nghiệm được đánh giá dựa trên các độ đo như Mean Reciprocal Rank (MRR), cho thấy hệ thống tìm kiếm giáo sư có khả năng trả về kết quả chính xác và nhanh chóng. Các kết quả được so sánh với các phương pháp tìm kiếm truyền thống để đánh giá hiệu quả.

5.2 Nhận xét kết quả

Kết quả thực nghiệm cho thấy hệ thống tìm kiếm giáo sư dựa trên mô hình EntityRank có khả năng cải thiện hiệu quả tìm kiếm đối tượng trên web. Hệ thống này có thể được mở rộng để áp dụng cho các loại đối tượng khác nhau, mang lại giá trị thực tiễn cao.

VI. Kết luận

Luận văn kết luận rằng mô hình EntityRank và hệ thống tìm kiếm giáo sư đã đạt được những kết quả khả quan trong việc tìm kiếm và xếp hạng đối tượng trên web. Hướng phát triển trong tương lai bao gồm việc mở rộng hệ thống để áp dụng cho các loại đối tượng khác nhau và cải thiện hiệu quả tìm kiếm thông qua các phương pháp học máy tiên tiến.

6.1 Kết quả đạt được

Luận văn đã đề xuất và hiện thực thành công mô hình EntityRank, một hệ thống xếp hạng đối tượng dựa trên mô hình xác suất. Hệ thống tìm kiếm giáo sư dựa trên mô hình này đã cho thấy sự khả quan trong việc cải thiện hiệu quả tìm kiếm đối tượng trên web.

6.2 Hướng phát triển

Hướng phát triển trong tương lai bao gồm việc mở rộng hệ thống để áp dụng cho các loại đối tượng khác nhau, cải thiện hiệu quả tìm kiếm thông qua các phương pháp học máy tiên tiến, và tích hợp thêm các nguồn dữ liệu đa dạng để nâng cao độ chính xác của kết quả tìm kiếm.

Trích đoạn nội dung tài liệu

Chương 1: Giới thiệu đề tài 1.1 Phát biểu bài toán Ngày nay, cách phổ biến để tìm kiếm thông tin là sử dụng các động cơ tìm kiếm như Google, Yahoo hay Bing. Tuy nhiên kết quả trả về của các động cơ tìm kiếm thông tin này chỉ là một danh sách các URL của các trang web. Người sử dụng phải duyệt qua các liên kết để tìm ra thông tin họ cần. Rõ ràng đây không phải là cách tốt nhất để tìm thông tin từ Internet.

Sẽ là tốt hơn, nếu động cơ tìm kiếm trả về kết quả trực tiếp liên quan đến câu truy vấn của người sử dụng, thay vì liên kết đến những tài liệu mà chúng có thể chứa kết quả. Chúng ta hãy xem kịch bản sau, Nam muốn theo học sau đại học ngành trí tuệ nhân tạo, vì vậy anh ta muốn biết những giáo sư nào đang nghiên cứu về lĩnh vực này để liên hệ. Bài toán đặt ra là làm thế nào Nam có thể tìm kiếm danh sách các giáo sư đang nghiên cứu về trí tuệ nhân tạo. Với các động cơ tìm kiếm hiện tại, bước 1, anh ta gõ vào “Artificial Intelligence Professor”.

Bước 2, từ kết quả trả về, anh ta cần duyệt qua các trang web để tìm tên các giáo sư. Anh ta cũng có thể duyệt qua trang chủ của khoa Khoa học máy tính của các trường với hi vọng sẽ có một trang liệt kê các giáo sư theo lĩnh vực nghiên cứu hoặc tìm qua từng trang chủ của các cán bộ giảng dạy. Điều này có thể là một quá trình khó nhọc. Từ những nhu cầu thực tế như thế này, ta thấy động cơ tìm kiếm tài liệu chưa đủ tốt.

Chúng ta muốn một phương pháp tìm kiếm hiệu quả hơn. Trong ví dụ trên, Professor là đối tượng trong câu truy vấn “Artificial Intelligence Professor”. Ta muốn rằng, sau khi gõ từ khóa (“Artificial Intelligence”) và tên đối tượng (“Professor”) vào động cơ tìm kiếm đối tượng, thì kết quả trả về là tên của các giáo sư, thay vì những liên kết đến các tài liệu mà chúng chứa từ khóa “Artificial”, “Intelligence”, và “Professor”. ~1~ Như ta thấy, câu truy vấn cho tìm kiếm đối tượng có hai phần: những từ khóa giống như tìm kiếm tài liệu, và những đối tượng.

Để phân biệt đối tượng và từ khóa, chúng tôi sử dụng ký hiệu # để chỉ đối tượng trong luận văn này. Ví dụ câu truy vấn trên được viết lại là (“Artificial Intelligence #Professor”). Tìm kiếm đối tượng làm giảm khoảng cách ngữ nghĩa giữa cái người sử dụng muốn và cái được biểu diễn bằng những từ khóa trong câu truy vấn. Ta có thể mô tả câu truy vấn dễ dàng hơn, chính xác hơn, và với việc trả về kết quả trực tiếp giúp ta tiết kiệm được thời gian.

Tìm kiếm đối tượng Gọi ES là một giải thuật tìm kiếm đối tượng. Giống như mô hình tìm kiếm tài liệu, đầu vào của giải thuật gồm có một tập các tài liệu D và câu truy vấn Q. , dn}, với di là một tài liệu giống như trong tìm kiếm tài liệu. Tuy nhiên, khác với câu truy vấn trong tìm kiếm tài liệu là một tập các từ khóa, câu truy vấn Q bao gồm hai phần: đối tượng mà người sử dụng muốn tìm kiếm và từ khóa trong cùng tài liệu với đối tượng.

Trong ví dụ trên, thì từ khóa là “Artificial Intelligence” và đối tượng là “Professor”. Những đối tượng này được định nghĩa trước cho động cơ tìm kiếm và chúng thể hiện những câu hỏi thông thường mà ta muốn truy vấn trên Web. Rank Professor Score Urls 1 George A Miller 113.edu/~rit/geo/ 2 John McCarthy 37.edu/jmc/ 3 Marvin Minsky 33.edu/~minsky/ 4 Tom Mitchell 28.edu/~tom/ … … … … Hình 1-1: Kết quả tìm kiếm đối tượng ~2~ Một cách hình thức, ta có Q = <E, K>, trong đó E là một tập các đối tượng và K là một tập các từ khóa. Kết quả trả về của ES là những thể hiện đối tượng thỏa tiêu chí tìm kiếm và những liên kết đến những tài liệu có chứa chúng.

Cũng như tìm kiếm tài liệu, kết quả cũng được xếp thứ tự theo sự phù hợp của đối tượng và câu truy vấn. Như thế ta có đầu ra O = {<E1, L1>, <E2, L2>,. , <En, Ln>}, trong đó Ei là một thể hiện đối tượng và Li là tập liên kết đến các tài liệu có chứa Ei. Hình 1-1 là một ví dụ kết quả tìm kiếm đối tượng.2 Các công trình liên quan Như một hệ thống truy hồi thông tin thông thường, hệ thống của chúng tôi cũng dựa trên kỹ thuật rút trích thông tin (Information Extraction - IE) để rút trích đối tượng (Named-Entity Extraction).

Để phù hợp với ngữ cảnh được đề cập, trong luận văn này, chúng tôi sử dụng thuật ngữ đối tượng và thực thể để thay thế lẫn nhau. Trong [18] chỉ ra ba loại tài liệu mà chúng ta thường rút trích thông tin trên đó, đó là: tài liệu có cấu trúc, tài liệu bán cấu trúc, và tài liệu văn bản. Dữ liệu Web được các tác giả xếp vào loại tài liệu bán cấu trúc. [18] cũng trình bày rất nhiều hệ thống rút trích thông tin trên nhiều loại tài liệu.

Tuy nhiên, theo sự phân loại của các tác giả thì có bốn loại hệ thống rút trích thông tin cơ bản là hệ thống dựa trên luật được xây dựng thủ công, hệ thống học có giám sát, hệ thống học bán giám sát, và hệ thống học không giám sát. Từ các nguyên lý này, mà các hệ thống rút trích đối tượng cũng có các kỹ thuật tương tự. Trên dữ liệu Web, chúng tôi nghiên cứu những hệ thống rút trích đối tượng tiên tiến gần đây, để từ đó lựa chọn phương pháp rút trích phù hợp cho từng loại bài toán. Etzioni và các cộng sự đã xây dựng hệ thống KnowItAll [11], [12], [21] để rút trích các thực thể có tên và quan hệ của chúng trên Web.

KnowItAll dựa trên kỹ thuật thông tin tương hỗ theo từng điểm (Pointwise Mutual Information) và truy hồi thông tin (PMI-IR) để đánh giá rằng một thực thể có tên có thể được phân vào một lớp nhất định. Urbansky và các cộng sự cũng đã xây dựng hệ thống WebKnox [14], [15] để rút trích sự kiện (Fact ~3~ Extraction) và các thực thể có tên trên web. WebKnox dựa trên ba kỹ thuật chính để rút trích thực thể: Phrase Extraction, Focused Crawl Extraction, và Seed Extraction. Phrase Extraction dựa trên ý tưởng của KnowItAll, chẳng hạn như “CONCEPTs such as”, “CONCEPTs like”, hay “CONCEPTs including”.

Focused Crawl Extraction và Seed Extraction sử dụng khái niệm XPath để tìm ra các thực thể. Wang và các giáo sư tại trường đại học Carnegie Mellon University đã xây dựng hệ thống Set Expander for Any Language (SEAL) [16] để thu thập các thực thể cùng loại với một tập nhỏ các thực thể đưa vào. Ví dụ khi ta đưa vào {“Ford”, “Nissan”, “Toyota”}, thì hệ thống trả về danh sách các nhà sản xuất xe hơi. SEAL xây dựng đồ thị gồm có các nút là các đối tượng: thực thể mẫu (seeds), các trang web (web pages), các biên (wrappers), và các thực thể đã được rút trích (extracted entity), và các cạnh là liên hệ giữa chúng.

SEAL sử dụng thuật toán bước trên đồ thị (Graph Walk) để xếp hạng danh sách các thực thể được rút trích. Giống như Wang, Dalvi và các giáo sư của mình xây dựng hệ thống WebSets [17] cũng để rút trích các thực thể. Tuy nhiên, WebSets có thể gôm cụm các thực thể trên Web thành một lớp mới mà ta chưa biết. Tồng quát hơn, Demartini và các cộng sự [28] đề ra hai kiến trúc để rút trích thực thể là dựa trên các động cơ tìm kiếm hiện tại và tự xây dựng hệ thống đánh chỉ mục thực thể.

Ngoài chức năng rút trích đối tượng, xếp hạng đối tượng là công việc chính của luận văn này. Vercoustre và các cộng sự đã tập trung vào xếp hạng thực thể trên Wikipedia [5]. Cách tiếp cận của họ là rút trích các thực thể từ các tài liệu XML trên Wikipedia và thiết lập các độ đo xếp hạng. Vercoustre chỉ tập trung vào truy hồi thông tin từ Wikipedia và do đó độ đo xếp hạng cũng bị giới hạn vào lĩnh vực cụ thể này.

Không chỉ có Vercoustre và các cộng sự [5] mà xếp hạng đối tượng thu hút được sự quan tâm của nhiều nhà khoa học với các nghiên cứu xếp hạng đối tượng trên các trang web của Wikipedia [40], [41], [42], [43], [44]. Đặc điểm dữ liệu Wikipedia là các trang web đều được xác định chủ đề/ thể loại (category) và trong mỗi trang có các khái niệm ~4~ (concept) được đánh dấu (tag) hay tạo liên kết tới các trang mô tả khái niệm đó. Do vậy, với cấu trúc web giàu ngữ nghĩa đó, việc xếp hạng các đối tượng trên Wikipedia thường dựa trên các liên kết giữa các đối tượng (hay các khái niệm), liên kết giữa các trang web, độ tương đồng ngữ nghĩa giữa các khái niệm như được đề cập trong [41]. Một ý tưởng khác là dựa trên sự tương đồng của cấu trúc tài liệu để tìm những thực thể khi có các trang mẫu.

[6] tìm kiếm đối tượng theo hướng ngữ nghĩa, từ một số tài liệu mẫu nó rút trích đối tượng mẫu và đi tìm những đối tượng tương tự trong những tài liệu có cấu trúc tương tự. Miền tìm kiếm còn hạn hẹp (tìm kiếm thông tin những vận động viên trong lĩnh vực bóng rổ, bóng đá, khúc côn cầu và gôn), và nó phụ thuộc vào cấu trúc tài liệu. Tìm quan hệ giữa các đối tượng là một cách tiếp cận khác, EntityEngine [33], [34] có thể trả lời những câu truy vấn như: tìm một danh sách các công ty và người sáng lập với điều kiện công ty ở thung lũng Silicon và người sáng lập tốt nghiệp trường Stanford. Thông tin trên một trang không thể trả lời câu truy vấn trên, bởi vì giả sử có một trang cho biết Jerry Yang là người sáng lập Yahoo, trong khi Yahoo là một công ty ở thung lũng Silicon và Jerry Yang tốt nghiệp trường Stanford được tìm thấy ở những trang khác.

Tuy nhiên họ mới chạy thử nghiệm trên Wikipedia và các bằng chứng (evidence) giữa các đối tượng chỉ xét trong một câu, điều này là một hạn chế trên Web. Trong [35], Li đã sử dụng năm đặc trưng để xếp hạng thực thể: kiểu thực thể, thời gian xuất hiện thực thể, số từ khóa của thực thể, chất lượng của trang chứa thực thể, và số lượng mỗi thực thể. Li cũng dùng phương pháp Support Vector Machines (SVM) để học hàm xếp hạng dựa trên năm đặc trưng này. Bởi vì mỗi đặc trưng có các trọng số khác nhau, nên phương pháp học xếp hạng chứng tỏ hiệu suất tốt hơn phương pháp xếp hạng thông thường.