Luận văn Học xếp hạng trong tính hạng đối tượng và tạo nhãn cụm tài liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THU TRANG HỌC XẾP HẠNG TRONG TÍNH HẠNG ĐỐI TƯỢNG VÀ TẠO NHÃN CỤM TÀI LIỆU Ngành: Công nghệ Thông tin Chuyên ngành: Hệ thống Thông tin Mã số: 60 48 05 luận văn thạc sĩ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Hà Quang Thụy Hà Nội - 2008 Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của bản thân. Các số liệu, kết quả trình bày trong luận văn này là trung thực và chưa từng được ai công bố trong bất kỳ công trình luận văn nào trước đây. Học Viên Nguyễn Thu Trang ii Lời cảm ơn Trước tiên, em muốn gửi lời cảm ơn sâu sắc nhất đến PGS.TS Hà Quang Thụy - Người thầy kính yêu, người hướng dẫn, chỉ bảo em tận tình từ những bước nghiên cứu đầu tiên và hoàn thành luận văn. Tôi chân thành cảm ơn các thầy cô trong bộ môn Các Hệ Thống Thông Tin, và phòng thí nghiệm SISLAB, nhóm xemina Data Mining và đặc biệt gửi lời cảm ơn tới ThS.Nguyễn Cẩm Tú đã giúp đỡ, hỗ trợ tôi trong quá trình nghiên cứu, hoàn thành đề tài. Tôi cảm ơn các thầy cô và các cán bộ của trường Công nghệ đã tạo cho tôi những điều kiện thuận lợi để học tập và nghiên cứu. Cuối cùng, xin gửi lời cảm ơn tới gia đình, GB và bạn bè nguồn động viên tinh thần to lớn với tôi, luôn cổ vũ và tin tưởng tôi. Nguyễn Thu Trang iii Mục lục MỞ ĐẦU 1 1 Xếp hạng đối tượng 2 1.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Phương pháp PageRank . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Xếp hạng đối tượng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Phương pháp đánh giá xếp hạng . . . . . . . . . . . . . . . . . . . . . 6 1.5 Tổng kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Học xếp hạng 9 2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Phương pháp học xếp hạng . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 Hồi quy có thứ tự và Pairwise . . . . . . . . . . . . . . . . . . 11 2.2.2 Học xếp hạng danh sách Listwise . . . . . . . . . . . . . . . . 13 2.3 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Xếp hạng trong máy tìm kiếm thực thể 16 3.1 Máy tìm kiếm thực thể . . . . . . . . . . . . . . . . . . . . . . . . . . 17 iv MỤC LỤC v 3.2 Xếp hạng thực thể . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.1 Mô hình Impression . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.2 Nhận xét, đánh giá mô hình Impression . . . . . . . . . . . . . 27 3.2.3 Mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.1 Công cụ sử dụng . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.2 Dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.3 Kết quả và đánh giá . . . . . . . . . . . . . . . . . . . . . . . 34 3.4 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4 Tạo nhãn cụm tài liệu 37 4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Phương pháp lựa chọn nhãn . . . . . . . . . . . . . . . . . . . . . . . 39 4.3 Học xếp hạng nhãn cụm . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3.1 Các đặc trưng . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3.2 Học hàm tính hạng . . . . . . . . . . . . . . . . . . . . . . . . 44 4.4 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4.1 Nguồn dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4.2 Dữ liệu học . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.4.3 Kết quả và đánh giá . . . . . . . . . . . . . . . . . . . . . . . 47 4.5 Tổng kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Kết luận 49 Tài liệu tham khảo 51 A Dữ liệu 59 MỤC LỤC vi A.1 Dữ liệu tìm kiếm thuốc . . . . . . . . . . . . . . . . . . . . . . . . . . 59 A.2 Cây wiki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Danh sách hình vẽ 62 Danh sách bảng 63 Bảng ký hiệu và từ viết tắt Từ viết tắt Mô tả Trang định nghĩa IR Information Retrieval 6 SVM Suport Vector Machine 2 LTR Learning To Rank 1 MAP Mean Average Precision 7 OR Ordinal Regression 10 vii MỞ ĐẦU Xếp hạng các đối tượng (trang Web, tác giả, chủ đề, trường đại học, công ty...) có ý nghĩa quan trọng trong lĩnh vực khai phá dữ liệu, là trung tâm của nhiều ứng dụng - điển hình là máy tìm kiếm. Các phương pháp tính hạng được nghiên cứu và phát triển từ rất nhiều năm trước, nhưng khoảng 3 năm trở lại đây, hướng tiếp cận sử dụng phương pháp học máy để xếp hạng đối tượng trở thành một vấn đề thu hút được rất nhiều sự quan tâm như trong SIGIR 2007 và SIGIR 2008 đã tổ chức hội thảo chuyên đề về học xếp hạng (learning to rank: LTR)[49]. Học xếp hạng đang được nhiều nhà khoa học trên thế giới quan tâm nghiên cứu và ứng dụng, như cải tiến hàm tính hạng trong máy tìm kiếm của nhóm Yuehua Xu tại ICML năm 2007 [59], mô hình tính hạng thực thể trong máy tìm kiếm thực thể của nhóm các tác giả Tao Cheng, Kevin Chang trong [17, 18, 19], và sử dụng học xếp hạng để đánh giá trọng số của các cụm từ [65, 53]. Luận văn Học xếp hạng trong tính hạng đối tượng và tạo nhãn cụm tài liệu thực hiện khảo sát, phân tích các phương pháp học xếp hạng đang được quan tâm hiện nay và từ đó đưa ra mô hình xếp hạng thực thể áp dụng vào máy tìm kiếm thực thể trong tiếng Việt, cụ thể là tìm kiếm thực thể thuốc và học xếp hạng để tạo nhãn cho cụm tài liệu. Qua đó cho thấy ứng dụng to lớn và ý nghĩa quan trọng của bài toán học xếp hạng. Luận văn này gồm bốn chương, nội dung được mô tả như dưới đây. Chương 1. Tổng quan về xếp hạng đối tượng giới thiệu những nội dung cơ bản nhất về bài toán xếp hạng và đặt vấn đề học xếp hạng đối tượng. 1 MỞ ĐẦU 2 Chương 2. Học xếp hạng đối tượng trình bày hai phương pháp học xếp hạng cơ bản. Đồng thời, chương này cũng giới thiệu thuật toán học được sử dụng nhiều trong học xếp hạng là máy véc-tơ hỗ trợ (SVM) và hồi quy tuyến tính. Chương 3. Học xếp hạng trong máy tìm kiếm thực thể đưa ra mô hình học xếp hạng đối tượng và thực nghiệm tính hạng thực thể thuốc trong máy tìm kiếm thực thể. Chương 4. Gán nhãn cụm tài liệu phân tích, áp dụng và báo cáo kết quả thực nghiệm học xếp hạng từ/cụm từ để tạo nhãn cho các cụm tài liệu. Phần kết luận tổng kết và tóm lược nội dung chính của luận văn. C h ư ơ n g 1 Xếp hạng đối tượng 1.1 Giới thiệu Trong nhiều ứng dụng cần xếp hạng các đối tượng theo tiêu chí nào đó, đơn giản như việc xếp hạng học sinh trong một lớp theo điểm trung bình, hay xếp hạng các trường đại học,.. và đặc biệt là việc xếp hạng các kết quả trả về của máy 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ùy vào từng ứng dụng cụ thể. Do đó cần xác định hàm tính giá trị về độ phù hợp để sắp xếp của các đối tượng theo tiêu chí đã đặt ra, và hàm đó được gọi là hàm tính hạng (ranking function: RF). Mỗi khi nói tới xếp hạng đối tượng chúng ta quan tâm tới hàm tính hạng. Một điển hình của bài toán xếp hạng là việc xếp hạng các kết quả trả về của máy tìm kiếm. Trong máy tìm kiếm thông thường (như Google, Yahoo) độ quan trọng hay còn gọi hạng trang là đại lượng cơ sở để xếp hạng. Giá trị này được xác định dựa vào việc phân tích đồ thị liên kết giữa các trang web. Với tập các tài liệu D = d1, ..dn, khi có truy vấn q của người dùng máy tìm kiếm cần tìm những tài liệu 2 CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 3 trong D phù hợp với truy vấn q, và sau đó sắp xếp các tài liệu theo độ phù hợp với truy vấn và độ quan trọng giảm dần. Đó là quá trình xếp hạng và hàm tính hạng là hàm kết hợp của giá trị độ tương tự giữa tài liệu với truy vấn similarity(q, di) và hạng trang thành chỉ số xếp hạng được Arvind Arasu và các tác giả đề cập tới trong [6]. Việc xác định hàm tính hạng đóng vai trò quan trọng và quyết định đối với chất lượng của máy tìm kiếm. Từ những năm 98, Cohen [21] đã đưa ra nhận định rằng có nhiều ứng dụng cần sắp xếp các đối tượng hơn là cần phân lớp chúng. Mọi ứng dụng mà kết quả trả về cho người dùng là một danh sách các đối tượng cần được sắp xếp, xếp hạng giúp người dùng nhanh chóng tiếp cận với kết quả gần với yêu cầu của mình nhất có thể. Thực tế chúng ta gặp rất nhiều các bảng xếp hạng như ví dụ ở trên. Điều đó cho thấy, xếp hạng là một bài toán quan trọng và có ý nghĩa. Tuy nhiên khái niệm xếp hạng (ranking) ra đời ban đầu với định hướng xếp hạng các đối tượng trên Web - cụ thể là các trang web. Các trang web cần được sắp xếp theo độ quan trọng giảm dần. Giá trị độ quan trọng đó gọi là hạng trang và PageRank [43] là phương pháp tính hạng đầu tiên, tính hạng trang các trang web dựa vào phân tích mối liên kết giữa các trang web trong đồ thị Web. 1.2 Phương pháp PageRank Page và các đồng tác giả [43] đã đưa ra ý tưởng: độ quan trọng của một trang chịu ảnh hưởng của độ quan trọng từ các trang liên kết đến nó. Và công thức tính PageRank cho một trang u, gọi là piu được tính như sau: piu = ∑ i∈BI (i) pii Ni (1.1) Với BI(i) là tập hợp các trang có liên kết đến trang i và Ni là số trang liên kết ra từ trang i. Biểu diễn đồ thị Web bởi ma trận chuyển P , khi đó phương trình 1.1 được viết lại dưới dạng ma trận: pi = piP (1.2) CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 4 Trong đó: pi = (pi1, pi2, . . . pin) là véc-tơ hạng các trang web, với thành phần pii là hạng của trang i. Từ 1.2 cho thấy véc-tơ hạng trang pi chính là véc-tơ riêng của ma trận chuyển P tương ứng với giá trị riêng λ = 1. Do tính chất của chuỗi Markov, để tính véc-tơ riêng của P thuật toán giả thiết rằng đồ thị trang web là liên thông, tức với cặp hai trang web i, j bất kì luôn có đường đi từ i tới j và ngược lại. Tuy nhiên thực tế trên World Wide Web (WWW) vẫn tồn tại không ít các trang web không có liên kết đến hoặc liên kết ra nên việc giả thiết đồ thị Web liên thông là không hợp lý. Và trong ma trận P vẫn tồn tại hàng chỉ toàn số 0, nên không tồn tại một phân phối xác suất dừng ổn định của P hay chính là véc-tơ hạng trang. Vì vậy cần phải biến đổi ma trận P thành P ′ sao cho phù hợp. Định nghĩa véc-tơ v, được chuẩn hóa ‖v‖ = 1, xác định xác suất phân phối với vi là xác suất trang web i được gọi đến ở lần duyệt web đầu tiên. véc-tơ v có vai trò trong việc hướng kết quả PageRank theo chủ đề, lĩnh vực mong muốn. Khi không xét đến ngữ cảnh đó có thể chọn vi = 1n với ∀i = 1, 2..n . Gọi d là véc-tơ n× 1 xác định các trang không có liên kết ra (dangling nút trên đồ thị Web): di = { 1 nếu N(i) = 0 0 ngược lại Ma trận P ′ được xác định: P ′ = P + dv (1.3) Khi thay đổi ma trận P như vậy tức thêm các liên kết ảo từ các dangling nút tới tất cả các nút khác trong đồ thị Web theo phân phối xác suất v. Điều đó giúp tránh việc khi duyệt các trang không có liên kết ra sẽ không duyệt tiếp được. Để đảm bảo phân phối dừng ổn định (duy nhất), chuỗi Markov tương ứng với quá trình duyệt Web của người dùng cần có tính chất ergodic, tức từ một trang web người dùng có thể chuyển tới một trang bất kì khác. Do vậy ma trận Markov P˜ được xác định như sau: P˜ = αP ′ + (1− α) J (1.4) CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 5 Với: J = [1]n×1 v và α: là hệ số hãm α thường được chọn giá trị 0.85, với ý nghĩa tại mỗi bước duyệt Web người dùng có thể chuyển tới một trang trong các liên kết ra từ trang hiện tại với xác suất α và chuyển tới các trang khác trong đồ thị Web với xác suất (1− α) theo phân phối v. Khi đó, thay vì tính vector riêng của ma trận P ta tính vector riêng pi của ma trận P˜ : pi = piP˜ . Theo tính chất của chuỗi Markov, tổng các thành phần của véc-tơ pi bằng 1:∑n i=1 pii = 1 Vậy véc-tơ hạng trang chính là véc-tơ riêng của ma trận P˜ . 1.3 Xếp hạng đối tượng Hạng trang PageRank là độ đo đầu tiên để xếp hạng các trang web. Và vì vậy, có thể coi hạng trang là hàm xếp hạng các đối tượng - cụ thể đối tượng trong trường hợp này là các trang web. Và ngày càng có nhiều các nghiên cứu về xếp hạng không chỉ là các trang web như xếp hạng các trường đại học [4, 3, 55], xếp hạng các nhà khoa học, bài báo [48]... Với những xếp hạng đơn giản như xếp hạng học sinh theo điểm trung bình, xếp hạng các doanh nghiệp theo doanh thu năm...có một tiêu chí xếp hạng rõ ràng và hàm tính hạng "dễ dàng" xác định. Tuy nhiên trong nhiều ứng dụng như xếp hạng các trường đại học, xếp hạng các nhà khoa học, xếp hạng các kết quả trả về của máy tìm kiếm,...mỗi loại đối tượng cần xếp hạng có nhiều đặc trưng khác nhau, cần tìm ra mối quan hệ về độ quan trọng của các đặc trưng đó. Và từ đó kết hợp các đặc trưng thành một hàm gọi l hàm tính hạng để xếp hạng các đối tượng. Đối tượng có giá trị hạng càng cao thì có thứ hạng càng cao (thứ hạng cao nhất là 1, và lần lượt giảm dần 2, 3 ..) Ví dụ, vấn đề xếp hạng các trường đại học đang nhận được nhiều sự quan tâm. Webometric [55, 4] là một phương pháp xếp hạng trường đại học dựa vào các thông tin trên web với có 4 chỉ số đặc trưng được xác định. Hàm xếp hạng các trường là CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 6 một hàm tuyến tính của 4 chỉ số đó và Webometric cũng đưa ra hệ số cụ thể cho từng chỉ số. Việc xếp hạng các trường đại với độ đo Webometric vẫn đang được các nhà khoa học quan tâm nghiên cứu [55, 4] với các nghiên cứu về các chỉ số và xác định hàm xếp hạng. Học xếp hạng được Joachims [36, 49] đánh giá là lĩnh vực nổi lên với sự phát triển lớn mạnh trong các nghiên cứu về truy tìm thông tin (information retrieval)và học máy (machine learning). Nói một cách khác, học hàm tính hạng hiện đang là vấn đề được quan tâm trong lĩnh vực học máy và có nhiều ứng dụng trong truy tìm thông tin, theo [61]. Học xếp hạng là học hàm của các đặc trưng để sắp xếp các đối tượng theo độ phù hợp, ưu tiên hay độ quan trọng...tùy vào từng ứng dụng cụ thể. Hiện nay nghiên cứu các phương pháp học tính hạng đang được nhiều nhà khoa học trên thế giới quan tâm [8, 12, 16, 26, 37, 44, 46, 45, 50], có nhiều phương pháp học xếp hạng được đưa ra như RankSVM [34], SVM-MAP [62].. Chương sau sẽ giới thiệu cụ thể các phương pháp học xếp hạng hiện nay. 1.4 Phương pháp đánh giá xếp hạng Để đánh giá chất lượng một xếp hạng, các độ đo thông dụng trong học máy như độ chính xác (precision), độ hồi tưởng (recall), độ đo F không sử dụng. Xếp hạng yêu cầu các đối tượng "đúng" (phù hợp tiêu chí) cần được xếp ở các vị trí đầu tiên của bảng xếp hạng càng tốt. Giả sử 6 đối tượng tương ứng là: a, b, c, d, e Trong đó a, b, c là các đối tượng phù hợp và d, e là các đối tượng không phù hợp. Một xếp hạng của các đối tượng cần đánh giá là: c, a, d, b, e. Các độ đo về độ chính xác của xếp hạng thường được sử dụng: CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 7 Độ chính xác mức K: P@K Độ chính xác xếp hạng ở mức K - Precision@K (P@K): độ chính xác của K đối tượng đầu bảng xếp hạng. Xác định số đối tượng đúng ở K vị trí đầu tiên của xếp hạng và gọi là Match@K, và độ chính xác mức K: P@K = Match@K K Với ví dụ trên ta có: P@3 = 2/3 ; P@4 = 3/4; P@5 = 3/5; Độ chính xác trung bình: MAP Độ chính xác trung bình là giá trị trung bình của các P@K tại các mức K có đối tượng đúng. Gọi I(K) là hàm xác định đối tượng ở vị trí hạng K nếu đúng I(K) =1 và ngược lại I(K) = 0. Độ chính xác trung bình: AP = ∑n K=1 P@K × I(K)∑n j=1 I(j) Với n là số đối tượng được xét. Giá trị trung bình trên m xếp hạng (với bài toán tìm kiếm thì đó là giá trị trung bình của AP trên các truy vấn): MAP = ∑m i=1 APi m Ví dụ trên có: MAP = 1 3 .( 1 1 + 2 2 + 3 4 ) Trung bình nghịch đảo thứ hạng: MRR Xác định vị trí hạng của đối tượng đúng đầu tiên trong bảng xếp hạng: r, khi đó nghịch đảo hạng: RR = 1/r. Với ví dụ trên, ta có RR = 1/1. Trung bình nghịch đảo thứ hạng là giá trị trung bình nghịch đảo thứ hạng RR của tất cả các truy vấn/hay xếp hạng đang xét. MRR = ∑m i=1 RRi m CHƯƠNG 1. XẾP HẠNG ĐỐI TƯỢNG 8 Một số độ đo khác Các độ đo ít được sử dụng hơn như: • Số đối tượng đúng ở mức K: Match@K. • Trung bình tổng nghịch đảo thứ hạng của các đối tượng đúng (MTRR): Với giá trị tổng nghịch đảo được xác định: TRR = n∑ i=1 ( 1 i × I(i)) Trong ví dụ ta có TRR = 1/1 + 1/2 1.5 Tổng kết Xếp hạng là một bài toán phổ biến, có ý nghĩa quan trọng và có nhiều ứng dụng trong thực tế. Vấn đề học xếp hạng là vấn đề thời sự đang nhận được 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. C h ư ơ n g 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 X ⊂ Rn của các đối tượng x = (x1, .., xn) ∈ Rn, với n là số đặc trưng của mỗi đối tượng. Cần tìm hàm h(x) : X → R để sắp xếp các đối tượng x theo độ phù hợp. Dữ liệu học S là xếp hạng đúng của một tập các đối tượng X ′ ⊂ X được đưa ra để học hàm h(x). Tùy từng ứng dụng mà người dùng có các mức yêu cầu khác nhau về sắp xếp thứ hạng đúng và có các kiểu dữ liệu học: 1. Xác định giá trị độ phù hợp y cụ thể của từng đối tượng trong S. Do trong ứng dụng xếp hạng, người dùng quan tâm nhiều tới thứ tự thay vì giá trị xếp 9 CHƯƠNG 2. HỌC XẾP HẠNG 10 hạng (độ phù hợp) nên y thường được xác định: • Hai giá trị tương ứng xếp hạng phù hợp (releval) và không phù hợp (inreleval). Người dùng chỉ quan tâm các đối tượng có phù hợp tiêu chí đặt ra hay không (2 hạng). • N giá trị xác định tương ứng N hạng nhất định, ví dụ: rất phù hợp, phù hợp, có thể phù hợp, không phù hợp. 2. Đưa ra các so sánh độ phù hợp của từng cặp đối tượng. 3. Danh sách sắp thứ tự đúng của "tất cả" các đối tượng theo độ phù hợp. Với mỗi kiểu dữ liệu trên, xác định các kiểu ràng buộc xếp hạng khác nhau và có các phương pháp học xếp hạng tương ứng. Các phương pháp học xếp hạng theo Soumen Chakrabarti [14] và Tie-Yan Liu [40]: Hồi quy (Regression): Có S = {(xi, yi)} mỗi đối tượng xi xác định giá trị yi tương ứng về độ phù hợp. Học hàm h(x) thỏa mãn: h(xi) = yi với ∀x ∈ X ′ Trong học xếp hạng, khi giá trị yi xác định thứ hạng của đối tượng xi thì phương pháp gọi là hồi quy có thứ tự (Ordinal Regression). Cặp thứ tự (Pairwise): Có S = {(xi, xj)} là tập các cặp đối tượng được sắp thứ tự, với mỗi cặp (xi, xj) có nghĩa xi có thứ hạng cao hơn xj (xi phù hợp hơn xj : xi  xj). Tìm h(x): ∀(xi, xj) ∈ S có xi  xj thì h(xi) > h(xj) Danh sách sắp xếp (Listwise): Một thứ tự sắp xếp của tất cả các đối tượng được xác định [62]. Tuy nhiên trong nhiều ứng dụng (ví dụ máy tìm kiếm), việc sắp thứ tự của tất cả các đối tượng là không khả thi, thì mộ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 thấp hơn [12] Có S = {x1, x2, ..., xm} với xi ∈ X ′ là một sắp thứ tự (x1  x2  ...  xm) tìm hàm h(x) sao cho: h(x1) > h(x2) > ... > h(xm) CHƯƠNG 2. HỌC XẾP HẠNG 11 2.2 Phương pháp học xếp hạng 2.2.1 Hồi quy có thứ tự và Pairwise Học xếp hạng với phương pháp hồi quy có thứ tự: tập dữ dữ liệu học S = {(xi, yi)}li=1vớ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à thứ hạng của xi cao hơn của xj (xi  xj) trong S: P = {(i, j) : yi > yj} và |P | = m. Do vậy có thể phát biểu lại bài toán: có các cặp so sánh thứ tự S ′ = {(xi, xj) ∣∣xi  xj}, tìm h(x) thỏa mãn: ∀(xi, xj) ∈ S ′ có xi  xj thì h(xi) > h(xj) Như vậy, từ bài toán hồi quy có thứ tự đã được chuyển về bài toán Pairwise. Ví dụ có tập sắp thứ tự S = {(d1, 2), (d2, 1), (d3, 1)} khi đó có các cặp so sánh thứ tự S ′ = {(d2, d1), (d3, d1)}. Với ví dụ này có d2 và d3 không xác định thứ tự so sánh (cùng thứ hạng trong S). Để giải quyết bài