CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 9 nhiều sự quan tâm của các nhà khoa học. Hướng tiếp cận bài toán học xếp hạng đã được giới thiệu trong chương này. Các chương sau tiếp tục làm rõ hơn về bài toán học xếp hạng và ứng dụng vào xếp hạng thực thể trong máy tìm kiếm thực thể, và bài toán gán nhãn cụm tài liệu.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2 Học xếp hạng 2.1 Giới thiệu Các nghiên cứu về học xếp hạng chủ yếu tập trung vào ứng dụng xếp hạng các tài liệu trả về từ máy tìm kiếm dựa theo truy vấn. Có tập các tài liệu D = {d1 , d2 , ., dn } và với truy vấn q, cần xác định hàm xếp hạng r để sắp xếp các tài liệu D theo độ phù hợp với truy vấn. Tổng quát bài toán xếp hạng đối tượng nói chung, ta có: tập các đối tượng X ⊂ Rn của các đối tượng x = (x1 , ., xn ) ∈ Rn , với n là số đặc trưng của đối tượng. Cần tìm hàm f (x) : X → R để sắp xếp các đối tượng x theo độ phù hợp.
Tùy từng ứng dụng, người dùng có cách xác định độ phù hợp khác nhau như: • Cần xác định đối tượng có phù hợp tiêu chí đặt ra hay không 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 2. HỌC XẾP HẠNG 11 • Đánh giá độ phù hợp của mối đối tượng với một số mức độ nhất định như rất tốt, tốt, trung bình, kém. • Đưa ra các so sánh độ phù hợp của từng cặp đối tượng. Do đó ta có các phương pháp học hàm f (x) tương ứng với các kiểu ràng buộc về xếp hạng khác nhau tùy theo cách đánh giá độ phù hợp như trên.
Các phương pháp học xếp hạng theo Chakrabarti [12] : Hồi quy (Regression): mỗi đối tượng x xác định giá trị y tương ứng về độ phù hợp. Cần học hàm f (x) thỏa mãn f (x) = y. Và khi giá trị y xác định thứ tự của đối tượng x thì phương pháp gọi là hồi quy có thứ tự. Tuy nhiên trong nhiều ứng dụng (ví dụ máy tìm kiếm), việc sắp xếp thứ tự tất cả các đối tượng là không khả thi, thì một thứ tự xếp hạng của K đối tượng đầu tiên được xác định, và tất cả các đối tượng khác đều có hạng cao hơn (phương pháp ListNet [10].
Một cách chi tiết hơn, Liu [36] chia các phương pháp học xếp hạng thành: Poinwise: tìm f (x) thỏa mãn với ∀x ∈ X có f (x) = y (tương ứng phương pháp hồi quy) Pairwise: f (x) thỏa mãn với ∀(xi , xj ): nếu xi ≺ xj thì f (xi ) < f (xj ) Listwise: có bộ thứ tự (x1 , .xk ) tìm f (x) thỏa mãn với ∀(xi , xj ): nếu i > j thì f (xi ) > f (xj ) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 2. HỌC XẾP HẠNG 12 2.2 Phương pháp học xếp hạng 2.1 Hồi quy có thứ tự vàPairwise Trong phương pháp hồi quy có thứ tự (ordinal regression, tập dữ dữ liệu học là các bộ S = {(xi , yi)}li=1 với yi ∈ 1, 2, .R là một tập sắp thứ tự, cần học hàm h(x) thỏa mãn: Với mọi cặp (xi , yi ) và (xj , yj ) thuộc S thì yi > yj ⇔ h(xi ) > h(xj ) Gọi P là tập hợp tất cả các cặp (i, j) mà nhãn của xi lớn hơn của xj : P = {(i, j) : yi > yj } và |P | = m. Herbrich [27] đã dựa vào phương pháp SVM của Joachims [30] đưa ra tối ưu trong hồi quy thứ tự gọi là ordinal regression SVM (OR-SVM): 1 T C X min w w+ ξij w,ξi,j ≥0 2 m (i,j)∈P Với ∀(i, j) ∈ P : (w T xi ) ≥ (w T xj ) + 1 − ξij Thuật toán SVM với tối ưu này tìm hàm h(x) tuyến tính tức tìm siêu phẳng tốt nhất mà làm cực tiểu số cặp dữ liệu học phải hoán đổi vị trí trong sắp xếp được ra. Mô tả ý tưởng như hình 2.
Viết lại ràng buộc của công thức tối ưu trên ta có ∀(i, j) ∈ P : w T (xi − xj ) ≥ 1 − ξij Công thức tương tự với công thức của ràng buộc trong tối ưu phân lớp SVM [30]. Do vậy mọi biến đổi tối ưu trên phân lớp SVM đều có thể được thực hiện đối với hồi quy thứ tự được Joachims [31]. Joachims đã biến đổi bài toán hồi quy có thứ tự về bài toán học phân lớp nhị phân, sử dụng phân lớp SVM để học được mô hình tham số w cho hồi quy tuyến tính. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 2.
HỌC XẾP HẠNG 13 Hình 2.1: Xếp hạng với SVM [31] Các tác giả như Michael Collins [19] cũng quan tâm học hồi quy và tìm cách chuyển bài toán học hồi quy thứ tự về bài toán phân lớp.2 Học xếp hạng danh sách Listwise Với các ứng dụng xếp hạng, như xếp hạng các trang web trả về cho người dùng trong máy tìm kiếm, người dùng nhận được danh sách các kết quả được sắp xếp theo thứ tự độ phù hợp giảm dần thay vì so sánh thứ hạng của mỗi cặp kết quả. Và do chỉ xét từng cặp đối tượng để so sánh nên phương pháp Pairwise không tối ưu các độ đo đánh giá chất lượng xếp hạng ví dụ như MAP. Do vậy thay vì chuyển bài toán xếp hạng về bài toán hồi quy và phần lớp, học xếp hạng từ danh sách sắp thứ hạng đã được các tác giả [58, 10, 9, 46] quan tâm. Phương pháp học xếp hạng trực tiếp từ danh sách xếp hạng do Yisong Yue và các tác giả đưa ra [58], sử dụng SVM để tìm tối ưu và ràng buộc về độ đo đánh giá MAP trên danh sách xếp hạng.
Phân lớp SVM học một siêu phẳng w, với dấu của w T w là nhãn dự LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 2. HỌC XẾP HẠNG 14 đoán. Hàm học tìm w để cực tiểu: N 1 T CX minw,ξi,j ≥0 w w + ξij 2 m i=1 P Với ∀i : yi .(w T xi ) ≥ 1 − ξi i ξi là tổng hệ số nới lỏng. Thêm các ràng buộc về đánh giá độ chính xác trung bình, với mỗi một nhãn y 0 sai đối với tài liệu x có: ∀y 0 6= y :T Ψ(y, x) ≥ w T Ψ(y 0, x) + ∆(y, y 0) − ξ P P Trong đó: Ψ(y 0 , x) = ( i : rel) 0 j:!rel yij .(xi − xj ) và ∆(y, y 0) = 1 − AP (y 0) Kết quả sau khi học w có dự đoán sắp xếp bởi w T xi.
Khi số lượng đối tượng được xếp hạng tăng thì số ràng buộc cũng tăng nhanh, do vậy cần tìm ràng buộc mà bị vi phạm nhiều nhất trong tập các ràng buộc và học mô hình thỏa mãn ràng buộc đó. Có nhiều các nhà nghiên cứu tập trung phương pháp học Listwise, như các phương pháp AdaRank [54], SoftRank [46], ListNet [10],. Tuy nhiên qua phân tích các kết quả trên Lector∗ cho thấy phương pháp SVM-MAP có chất lượng tốt nhất.3 Tổng kết chương Chương này đã giới thiệu chung về các phương pháp học xếp hạng hiện nay và hai phương pháp học xếp hạng SVM-MAP, RankSVM được đề cập. Đó là hai phương pháp được áp dụng vào hai ứng dụng học xếp hạng được trình bày ở chương sau.com/en-us/um/beijing/projects/letor/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 3 Xếp hạng trong máy tìm kiếm thực thể Các máy tìm kiếm thông dụng hiện nay như Google, Yahoo, MSN, truy vấn người dùng đưa vào là tập các từ khóa và kết quả trả về là danh sách các địa chỉ tới các trang web.
Do vậy để nhận được thông tin mong muốn, người dùng phải duyệt qua từng địa chỉ web đó, và có thể phải duyệt qua nhiều trang không có thông tin mong muốn. Với sự phát triển của các kỹ thuật rút trích thông tin (Information Extraction- IE) cụ thể là rút trích các thực thể, hướng phát triển máy tìm kiếm thực thể đã được Kevin Chang và các cộng sự [15, 16, 17] nghiên cứu, xây dựng. Truy vấn của người dùng trên máy tìm kiếm thực thể không đơn thuần là các từ khóa mà người dùng xác định rõ hơn về loại đối tượng dữ liệu đang muốn tìm và ngữ cảnh tìm kiếm. Kết quả trả về cho người dùng thay vì chỉ là các địa chỉ web, người dùng còn nhận được các thông tin cụ 15 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 3.
XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 16 thể về đối tượng mình mong muốn tìm kiếm. Cũng như với máy tìm kiếm thông thường xếp hạng là vấn đề quan trọng, xếp hạng thực thể là cốt lõi và quan trọng của máy tìm kiếm thực thể. Không chỉ các tác giả T. Đặc điểm dữ liệu wiki 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 (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 thực thể trên wikipedia thường dựa trên các liên kết giữa các thực thể (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 [20]. Song song với các nghiên cứu đó là các nghiên cứu xếp hạng thực thể dựa trên việc xây dựng đồ thị quan hệ giữa các thực thể, mạng xã hội các thực thể trên web [43, 13, 11, 2, 7]. Qua phân tích các nghiên cứu [47, 20, 21, 50, 43, 11, 13, 15, 16, 17], với định hướng xây dựng hệ tìm kiếm thực thể trên web nói chung, việc xếp hạng trong tìm kiếm thực thể của nhóm T.Cheng được quan tâm và phân tích.1 Máy tìm kiếm thực thể Người dùng thường tìm kiếm thông tin về đối tượng nào đó, ví dụ như khi sử dụng truy vấn "thuốc chống viêm", người dùng muốn tìm các thực thể thuốc mà có tác dụng chống viêm. Và các máy tìm kiếm hiện nay (như Google, Yahoo, MSN) bằng cách so sánh văn bản (text) trên từng trang web với truy vấn và trả về cho người dùng địa chỉ các trang mà có chứa từ khóa trong truy vấn.
Do vậy người dùng không trực tiếp nhận được thông tin mong muốn mà phải duyệt qua nội dung các trang web trả về đó và ∗ http://wikipedia.org LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 3. XẾP HẠNG TRONG MÁY TÌM KIẾM THỰC THỂ 17 không chắc chắn có được thông tin mong muốn ở những kết quả đầu tiên.