Luận văn -Quảng cáo trực tuyến hướng câu truy vấn với sự giúp đỡ của phân tích chủ đề và kỹ thuật tính hạng

iệu từ khóa (bid-term) có xuất hiện trong tiêu đề, trong nội dung hay không, trong phần nào của nội dung… Với 5 loại đặc trưng nói trên, họ sử dụng 81 đặc trưng. Ngoài ra còn sử dụng các đặc trưng sau: 21 • Các từ xuất hiện trong tập quảng cáo: lấy ra 10000 từ phổ biến nhất trong tập quảng cáo, thêm một đặc trưng với giá trị 1 nếu từ xuất hiện trong quảng cáo đang xét, ngược lại là giá trị 0. • CTR: sử dụng CTR của những quảng cáo khác có chung từ khóa (keywords, bid term). Ngoài ra, số lượng các quảng cáo có cùng từ khóa với quảng cáo đang xét cũng được sử dụng như một đặc trưng. • Bên cạnh những quảng cáo có từ khóa chung, CTR của những quảng cáo có từ khóa liên quan cũng được sử dụng. Ví dụ từ khóa “red shoes” và “buy red shoes” là những từ khóa có liên quan và CTR của quảng cáo ứng với “buy red shoes” có thể được sử dụng trong việc ước lượng CTR của quảng cáo ứng với “red shoes”. Về dữ liệu, họ sử dụng một tập các quảng cáo của máy tìm kiếm MSN, mỗi quảng cáo có các thông tin như: URL, các từ khóa tương ứng với quảng cáo, tiêu đề, nội dung và đặc biệt là tổng số lần quảng cáo đã được click và tổng số lần quảng cáo đc xem kể từ khi được đưa vào hệ thống. Tập dữ liệu được chia làm ba phần: 70% cho việc training, 10% cho việc kiểm định và 20% cho việc test. Trong thực nghiệm, họ sử dụng độ trung bình KL-divergence [20] được tính bởi kết quả ước lượng CTR của mô hình và CTR thực sự của quảng cáo trong tập test. Xây dựng 1 số hệ thống với các đặc trưng khác nhau, tiến hành so sánh với mô hình ước lượng CTR chỉ sử dụng tập train một cách đơn giản (sử dụng một đặc trưng duy nhất CTR của chính quảng cáo), được gọi là baseline. Kết quả thu được là khá tốt, mức độ cải tiến so với baseline từ 13.28% tới 19.67%. 2.6. Mô hình tìm kiếm và xếp hạng sử dụng chủ đề ẩn trong quảng cáo theo ngữ cảnh Dựa trên ý tưởng mở rộng nội dung trang web và quảng cáo sẽ hỗ trợ tốt hơn cho việc tìm kiếm và xếp hạng quảng cáo. Lê Diệu Thu [27] đã đề xuất một hướng tiếp cận trong quảng cáo theo ngữ cảnh, tập trung vào phân tích chủ đề ẩn nhằm làm giàu nội dung trang web cũng như quảng cáo bằng những từ khóa mở rộng. Để khái quát hóa ngữ cảnh của các trang web và quảng cáo, tác giả tiến hành xây dựng một mô hình phân tích chủ đề ẩn trên một tập dữ liệu lớn, từ đó phát hiện những chủ đề và các mối quan hệ giữa chủ đề với từ hay giữa từ với từ. Mô hình này còn cho phép xác định phân bố xác suất của các 22 chủ đề trên từng trang web hay quảng cáo, từ đó làm giàu nội dung của chúng với những từ khóa của các chủ đề có liên quan. Lê Diệu Thu xây dựng một bộ dữ liệu với kích thước lớn, gọi là Universal Dataset, và sử dụng bộ dữ liệu này cho quá trình phân tích chủ đề ẩn. Bộ dữ liệu được thu thập từ VnExpress [7], một trong những trang báo điện tử lớn nhất của Việt Nam, bao gồm các chủ đề khác nhau như: xã hội, tin tức thế giới, đời sống, văn hóa, thể thao, khoa học… Hơn 220 Megabyte dữ liệu gồm khoảng 40 nghìn trang web được thu thập sử dụng Nutch [37] và được tiền xử lý bằng cách loại bỏ các thẻ HTML, phân tách câu, tách từ, loại bỏ những từ không thích hợp. Sau khi xử lý, thu được bộ dữ liệu 53 Megabyte với 40,268 tài liệu.Tiến hành phân tích chủ đề ẩn trên bộ dữ liệu thu được sử dụng GibbsLDA [16], một ứng dụng của mô hình LDA và Gibb Sampling. Để tiến hành thực nghiệm, tác giả sử dụng một tập 100 trang web và 2607 quảng cáo khác nhau. Các trang web được lựa chọn ngẫu nhiên từ tập 27,763 trang web thu thập được từ báo điện tử VnExpress, các trang web được chọn từ các chủ đề: ẩm thực, mua bán, dược phẩm, nhà đất, thị trường chứng khoán, việc làm… Các quảng cáo được thu thập bằng cách sử dụng các tiêu đề, mô tả và từ khóa của các trang web trên danh bạ website Việt Nam [5]. Để đánh giá ảnh hưởng của các từ khóa trong tìm kiếm theo ngữ cảnh, Lê Diệu Thu cài đặt hai phương pháp tìm kiếm theo hướng tiếp cận của Ribeiro-Neto [24]. Phương pháp thứ nhất gọi là AD, chỉ sử dụng tiêu đề và mô tả của quảng cáo trong tìm kiếm. Phương pháp thứ hai là AD_KW, tìm kiếm quảng cáo sử dụng cả tiêu đề, mô tả của quảng cáo lẫn các từ khóa. Để đánh giá ảnh hưởng của chủ đề ẩn, tác giả tiến hành 6 thực nghiệm khác nhau. Trong mỗi thực nghiệm, sử dụng một mô hình chủ đề ẩn khác nhau với các tham số khác nhau. Các mô hình chủ đề ẩn được sử dụng lần lượt là mô hình với 60, 120 và 200 chủ đề. Sau khi suy luận chủ đề ẩn cho tất cả các trang web và quảng cáo, tiến hành mở rộng tập từ vựng của chúng theo các chủ đề liên quan. Kết quả thực nghiệm cho thấy, việc sử dụng chủ đề ẩn làm tăng độ chính xác của mô hình từ 64% lên 72%. Nghiên cứu của Lê Diệu Thu [27] đã đưa ra một mô hình nhằm giải quyết bài toán tìm kiếm và xếp hạng quảng cáo trong quảng cáo theo ngữ cảnh. Chỉ ra những ảnh hưởng tích cực của việc sử dụng chủ đề ẩn nhằm mở rộng tập từ khóa của trang web cũng như 23 quảng cáo. Kết quả đạt được rất khả quan, mô hình khắc phục được vấn đề so khớp giữa quảng cáo và trang web có tập từ vựng khác nhau bằng việc khai thác mối quang hệ ngữ nghĩa ẩn trong nội dung của chúng. Cách tiếp cận này có thể được mở rộng và sử dụng một cách hiệu quả trong quảng cáo trên máy tìm kiếm. 24 Chương 3. Hệ thống quảng cáo trực tuyến sử dụng xếp hạng và chủ đề ẩn 3.1 Xếp hạng Trong nhiều ứng dụng cần sắp xếp các đối tượng theo một tiêu chí nào đó, ví dụ sắp xếp danh sách các nhân viên trong công ty theo tên, tuổi,... hay sắp xếp danh sách học sinh trong một lớp theo điểm trung bình. Công việc như vậy gọi là xếp hạng. Kết quả xếp hạng là một danh sách các đối tượng được sắp thứ tự mà ở đó một đối tượng được xếp trên một đối tượng khác khi nó thỏa mãn một yêu cầu nào đó [2]. Ta nói, đối tượng A có hạng cao hơn đối tượng B khi A có độ phù hợp với tiêu chí đặt ra lớn hơn so với B. Việc xếp hạng có thể được tiến hành theo các tiêu chí khác nhau, ta cần tính độ phù hợp của các đối tượng với tiêu chí đặt ra, hàm tính độ phù hợp được gọi là hàm tính hạng (ranking function). 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 số vấn đề nổi trội về xếp hạng đó là: xếp hạng các trang web theo thứ tự độ quan trọng, xếp hạng các trường đại học theo quy mô và đặc biệt là xếp hạng các kết quả trong máy tìm kiếm theo mức độ phù hợp với truy vấn. Trên thực tế, xếp hạng được thực hiện ở rất nhiều lĩnh vực. Việc xếp hạng giúp ta có một cái nhìn tổng quan, tiếp cận được những đối tượng phù hợp nhất với yêu cầu đưa ra một cách nhanh nhất, có thể so sánh các đối tượng với nhau một cách dễ dàng. Điều đó cho thấy, xếp hạng là một bài toán rất quan trọng và có ý nghĩa. 3.1.1 Xếp hạng trong máy tìm kiếm Tốc độ phát triển nhanh chóng của World Wide Web (www) dẫn đến nhu cầu tìm kiếm các tài liệu trên internet trở nên rất lớn, máy tìm kiếm được sử dụng để phục vụ cho nhu cầu này của con người. Từ yêu cầu của người dùng, thường là một truy vấn, máy tìm kiếm sẽ tìm kiếm và đưa ra các tài liệu phù hợp với yêu cầu đó. Tuy nhiên số lượng kết quả phù hợp với truy vấn có thể là rất lớn, lên tới hàng trăm hay hàng nghìn, người dùng không thể lần lượt duyệt từng kết quả này để xác định đâu là tài liệu mình muốn tìm. Do vậy, bài toán đặt ra là phải tiến hành xếp hạng các tài liệu trả về từ máy tìm kiếm theo thứ tự giảm dần về độ phù hợp với truy vấn đầu vào. Việc xếp hạng sẽ giúp người dùng nhanh chóng tiếp cận với kết quả mong muốn, tiết kiệm được rất nhiều thời gian. 25 Bài toán xếp hạng có ý nghĩa rất quan trọng trong máy tìm kiếm. Khác 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 nhân viên theo số lượng công việc hoàn thành… có một tiêu chí xếp hàng rõ ràng và hàm tính dạng có thể dễ xác định. Việc xếp hạng các kết quả trả về từ máy tìm kiếm là rất phức tạp, mỗi tài liệu có nhiều đặc trưng khác nhau, cần tìm ra mối quan hệ giữa các đặc trưng đó.Và từ đó kết hợp các đặc trưng lại để xây dựng hàm tính hạng phù hợp. Có rất nhiều thuật toán được đưa ra như: HITS, PageRank, TrustRank… mỗi thuật toán đều có những ưu, nhược điểm riêng. [21]Học xếp hạng được Joachims đá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ề tìm kiế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 tìm kiếm thông tin. 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. Dưới đây là thuật toán SVM-Rank, một trong những thuật toán học tính hạng phổ biến. 3.1.2 Học xếp hạng và SVM Rank 3.1.2.1 Học xếp hạng 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ó các tập 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 h(x): D → R để sắp xếp các tài liệu D theo độ phù hợp với truy vấn [2]. Dữ liệu học S là xếp hạng đúng của một tập các tài liệu D’ Є D được đưa ra để học hàm h(x). Tùy từng ứng dụng mà có các mức yêu cầu khác nhau về sắp xếp thứ hạng đúng của dữ liệu: 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 hạng nên y thường được xác định: 26 • Hai giá trị tương ứng với xếp hạng phù hợp (relevant) hay không phù hợp (irrelevant). 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. • 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. Các phương pháp học xếp hạng theo Sounmen Chakrabarti [13] và Tie-Yan Liu [23] là: - Hồi quy (Regression): Có S = {(xi, hi)} 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) = y(i) với mọ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ó hạng cao hơn xj (xi phù hợp với điều kiện hơn xj) Tìm h(x): ׊(xi, xj) א S có xi > xj thì h(xi) > h(xj) SVM-Rank là một trong những thuật toán thuộc phương pháp này. - 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. Tuy nhiên, điều này không khả thi trong một vài ứng dụng, ví dụ máy tìm kiếm. Ta có S = {x1, x2, ..., xm với xi Є X’ là một sắp thứ tự (x1 > x2 > ... > xm) Cần tìm hàm h(x) sao cho h(x1) > h(x2) > ... > h(xm) 3.1.2.2 SVM-Rank SVM-Rank là một thuật toán được xây dựng nhằm giải quyết vấn đề xếp hạng các tài liệu bằng việc sử dụng thuật toán học giám sát SVM. Giả sử dữ liệu đầu vào là tập tài liệu nằm trong không gian n chiều X € Rn với n là số đặc trưng của tài liệu. Tồn tại một kết quả xếp hạng Y = {r1 , r2 ,..., rq } với q là số 27 lượng các hạng có thể. Giả sử tồn tại một thứ tự giữa các hạng rq › rq-1 › ... › r1 trong đó "›" thể hiện quan hệ ưu tiên giữa các tài liệu [29]. Tồn tại một tập các hàm xếp hạng f € F mà mỗi hàm f có thể quyết định quan hệ ưu tiên giữa các tài liệu: xi › xj ↔ f(xi) > f(xj) (1) Giả sử ta có một tập các tài liệu đã được xếp hạng: S = {( xi , yi )} i =1,t từ không gian X × Y. Nhiệm vụ đặt ra là phải lựa chọn hàm f* tốt nhất từ F sao cho cực tiểu hóa độ sai lệch (loss value) với một hàm tính độ sai lệch cho trước (lost function) trên tập dữ liệu đã cho. [14]Herbrich đã chuẩn hóa vấn đề học ở trên thành việc học cho phân lớp trên các cặp tài liệu. Giả sử f là một hàm tuyến tính: Fw(x) = (2) Trong đó w là véc tơ trọng số và là ký hiệu của tích trong. Từ (1) và (2) ta có: xi › xj ↔ > 0 (3) Khi này, quan hệ giữa xi và xj: xi › xj được thể hiện bởi véc tơ xi - xj. Tiếp đó, ta lấy tất cả các cặp tài liệu và quan hệ giữa chúng để tạo nên một véc tơ mới và một nhãn mới. Kí hiệu x(1) và x(2) lần lượt là tài liệu thứ nhất và tài liệu thứ 2, y(1) và y(2) là hạng của chúng. Ta có: ݔԦሺଵሻ െ ݔԦሺଶሻ, ݖ ൌ ቊ ൅1 ݕሺଵሻ ൐ ݕሺଶሻ െ1 ݕሺଶሻ ൐ ݕሺଵሻ (4) Từ tập dữ liệu train S ta tạo ra một tập dữ liệu train khác S' với l véc tơ đã được gán nhãn: S’ = {xi(1) – xi(2), zi} i = 1,n (5) Sử dụng S' làm dữ liệu cho phân lớp và xây dựng một mô hình SVM cho phép xác định nhãn z là âm hay dương z = +1 hay z = -1 với mỗi véc tơ x(1) - x(2) Việc xây dựng mô hình SVM tương đương với việc giải bài toán: 28 min௪ሬሬԦ ܯሺݓሬሬԦሻ ൌ ଵ ଶ ԡݓሬሬԦԡ ൅ ܥ ∑ ߦ௜௟௜ୀଵ ݏݑܾ݆݁ܿݐ ݐ݋ ߦ௜ ൒ 0, ݖ௜ ۃݓሬ ଶ ሬԦ, ݔపሬሬሬԦ ሺଵሻ െ ݔపሬሬሬԦ ሺଶሻۄ ൒ 1 െ ߦ௜ ݅ ൌ 1,… , ݈ (6) Việc tối ưu (6 n ơ ớ) tươ g đư ng v i tối ưu (7) khi λ = 1/2C: min௪ሬሬԦ ∑ ቂ1 െ ݖ௜ ۃݓሬሬԦ, ݔపሬሬሬԦ ሺଵሻ െ ݔపሬሬሬԦ ሺଶሻۄቃ ା ௟ ௜ୀଵ ൅ ߣԡݓሬሬԦԡଶ (7) Giả sủ w* là véc tơ trọng số của mô hình SVM. Về mặt hình học, w* sẽ vuông góc với siêu phẳng của Ranking SVM. Ta sử dụng w* để xây dựng hàm ranking fw* cho việc xếp hạng các tài liệu: fw*(x) = (8) Khi áp dụng SVM, mỗi vectơ đặc trưng được tạo ra từ một cặp tài liệu. Mỗi đặc trưng được định nghĩa như một hàm của truy vấn và tài liệu.Ví dụ đặc trưng tần suất xuất hiện của từ khóa được tính bằng số lần xuất hiện của các từ khóa trong câu truy vấn trên tài liệu. Tất cả các kết quả từ tất cả các truy vấn được sử dụng trong quá trình training. Không có sự khác biệt giữa các tài liệu từ các truy vấn khác nhau. Hơn nữa, không có sự khác biệt giữa các cặp tài liệu thuộc các hạng khác nhau, trong khi trên thực tế, ảnh hưởng của việc xếp hạng sai giữa những tài liệu có hạng cao với tài liệu có hạng thấp là lớn hơn so với việc xếp hạng sai giữa những tài liệu có hạng thấp với nhau . Đây chính là hai vấn đề có thể gây ra sự thiếu chính xác của Ranking SVM. Để giải quyết hai vấn đề được nêu ở trên, ta có thể định nghĩa một hàm loss mới dựa trên cơ sở của Hinge Loss [29]. Loss function Trong loss function ở (9) ta thêm một tham số hạng τ để điều chỉnh độ lệch giữa các cặp hạng, thêm tham số μ để điều chỉnh độ lệch giữa các truy vấn. Ta phát biểu lại bài toán của Ranking SVM với mục tiêu là cực tiểu hóa loss function sau: min ௪ሬሬԦ ܮሺݓሬሬԦሻ ൌ෍߬௞ሺ௜ሻߤ௤ሺ௜ሻ ቂ1 െ ݖ௜ ۃݓሬሬԦ, ݔపሬሬሬԦ ሺଵሻ െ ݔపሬሬሬԦ ሺଶሻۄቃ ା ௟ ௜ୀଵ ൅ ߣԡݓሬሬԦԡଶ (9) Trong đó k(i) là hạng của cặp tài liệu i, τk(i) là tham số hạng của k(i), q(i) ứng với truy vấn của cặp tài liệu i, μq(i) là tham số của truy vấn q(i). Độ vi phạm nhận được từ cặp thứ i được quyết định bởi tích của τk(i) và μq(i): τk(i) μq(i) 29 Xác định giá trị các tham số Ta phải xác định làm thế nào để tính giá trị của τ và μ. Với τ, ta sử dụng một phương pháp Heuristic để ước lượng các tham biến dựa trên mô hình cơ sở. Giả sử NDCG được sử dụng để đánh giá (có thể sử dụng các độ đo khác). Thuật toán được mô tả như sau: Hình 8. Thuật toán ước lượng tham biến τ [29] Với μ ta tính như s :au ߤ௤ሺ௜ሻ ൌ ௠௔௫ೕஷሼ୬୦ữ୬୥ ୡặ୮ ୲à୧ ୪୧ệ୳ ứ୬୥ ୴ớ୧ ୯ሺ୨ሻሽ ஷሼ୬୦ữ୬୥ ୡặ୮ ୲à୧ ୪୧ệ୳ ứ୬୥ ୴ớ୧ ୯ሺ୧ሻሽ (10) 3.1.3 Các 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 được sử dụng. Xếp hạng yêu cầu các đối tượng “đúng” (phù hợp với tiêu chí) được xếp ở các vị trí đầu tiên của bảng xếp hạng càng tốt. Dưới đây là một số độ đo đánh giá mức hiệu quả của xếp hạng: 30 3.1.3.1 MAP Độ chính xác mức K: P@K – Precision@K là độ 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 ܲ@ܭ ൌ ܯܽݐ݄ܿ@ܭ ܭ [19]. Ta có: Độ chính xác trung bình (AP): 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 h: trung bìn ܣܲ ൌ ∑ ܲ@ܭ ݔ ܫሺܭሻ௡௄ୀଵ ∑ ܫሺ݆ሻ௡௝ୀଵ Giá trị trung bình trên tất cả các truy vấ Average Precision): n (Mean ܯܣܲ ൌ ∑ ܣ ௜ܲ ௠ ௜ୀଵ ݉ Trong đó m là tổng số truy vấn. Ví dụ: Giả sử có 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. Khi đó ta có: p@1 = 1; P@2 =1; P@3 = 2/3; P@4 = 3/4; P@5 = 3/5. AP(1) = 1; AP(2) = 1; AP(3) = 1; AP(4) = (1 + 1 + 3/4) / 3 3.1.3.2 NDCG (Normalized Discounted cumulative gain) DCG (Discounted cumulative gain) là một độ đo mức hiệu quả của các thuật toán trên hệ thống máy tìm kiếm hay những ứng dụng tương tự, và thường được sử dụng trong tìm kiếm thông tin (Information Retrieval). Sử dụng một độ đo tính phù hợp của các tài liệu trong tập kết quả trả về bởi máy tìm kiếm, DCG đo sự hiệu quả của một tài liệu dựa trên vị trí của nó trong danh sách. Con số này được tính tính lũy từ đầu tới cuối danh sách kết quả và giảm dần ở những vị trí thấp hơn[19]. 31 Hai giả thiết được đưa ra trong việc sử dụng DCG và những phép đo có liên quan: o Sẽ tốt hơn nếu những tài liệu có độ phù hợp cao xuất hiện sớm trong danh sách kết quả của máy tìm kiếm (có rank cao hơn) o Những tài liệu có độ phù hợp cao thường hữu ích hơn so với những tài liệu có độ phù hợp thấp, và những tài liệu này lại hữu ích hơn so với những tài liệu không phù hợp. DCG được hình thành từ một độ đo nguyên thủy hơn, đó là CG (Cumulative Gain). Cumulative Gain: độ đo CG không quan tâm tới vị trí của kết quả trong tính toán, nó tính tổng độ phù hợp của tất cả các tài liệu trong danh sách kết quả. Độ đo CG tại một vị trí p được tính như sau: ܥܩ௣ ൌ෍ݎ݈݁௜ ௣ ௜ୀଵ Trong đó reli là mức độ phù hợp của kết quả tại vị trí thứ i. Độ đo CG không bị ảnh hưởng bởi thứ tự sắp xếp các kết quả trong danh sách. Việc chuyển tài liệu có độ phù hợp cao xuống vị trí thấp không làm thay đổi giá trị CG. Dựa vào hai giả thiết ở trên về mức hiệu quả của kết quả tìm kiếm, DCG được sử dụng để đem lại hiệu quả cao hơn. Discounted cumulative gain: tiền đề của DCG là những tài liệu có độ phù hợp cao hơn nhưng lại xuất hiện ở những vị trí thấp hơn sẽ dẫn tới một mức “phạt” (penalty) bằng cách giảm độ phù hợp của tài liệu đi một lượng bằng logarit của vị trí trong kết quả. DCG tại vị trí p được tính như sau: ܦܥܩ௣ ൌ ݎ݈݁ଵ ൅෍ ݎ݈݁௜ logଶ ݅ ௣ ௜ୀଶ Ngoài ra DCG còn được tính theo công th c: ứ ܦܥܩ௣ ൌ෍ 2௥௘௟೔ െ 1 logଶሺ1 ൅ ݅ሻ ௣ ௜ୀଶ 32 ݊ܦܥܩ௣ ൌ ܦܥܩ௣ ܫܦܥܩ௣ Normalized DCG: Trong đó: IDCGp (Ideal Discounted cumulative gain) là giá trị DCG trong trường hợp kết quả đưa ra là hoàn hảo, nhận được khi tất cả các tài liệu đều được xếp đúng vị trí tương ứng với độ phù hợp của chúng. Ví dụ: Giả sử có 6 tài liêu a, b, c, d, e, f với các độ phù hợp lần lượt là: 3, 3, 2, 2, 1, 0. Một kết quả xếp hạng được đưa ra như sau: b, c, a, f, e, d. Ta có: CG6 = 3 + 2 + 3 + 0 + 1 + 2 = 11 DCG6 = 3 + (2 + 1.887 + 0 + 0.431 + 0.772) = 8.09 IDCG = 3 + (3 + 2/1.59 + 2/2 + 1/2.32 + 0) = 8.693 nDCG6 = DCG6/IDCG6 = 8.09/8.693 = 0.9306 Ngoài hai độ đo trên, một số độ đo khác cũng được sử dụng như: trung bình nghịch đảo thứ hạng (MRR), 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) [2]. Tuy nhiên NDCG và MAP là hai độ đo khá phổ biến và được sử dụng trong rất nhiều công trình như [11], [19], [29]. 3.2 Chủ đề ẩn Vấn đề biểu diễn dữ liệu một cách hiệu quả để khai thác mối quan hệ giữa các dữ liệu ngày càng trở nên tinh vi và phức tạp hơn. Đã có rất nhiều nghiên cứu nhằm giải quyết về vấn đề này. Các mô hình chủ đề ẩn [10] là một bước tiến quan trọng trong việc i reli log2i reli/log2i 1 3 N/A N/A 2 2 1 2 3 3 1.59 1.887 4 0 2.0 0 5 1 2.32 0.431 6 2 2.59 0.772 33 mô hình quá dữ liệu văn bản. Chúng được dựa trên ý tưởng rằng mỗi tài liệu có một xác suất phân phối vào các chủ đề, và mỗi chủ đề là sự phân phối kết hợp giữa các từ. Biểu diễn các từ và tài liệu dưới dạng phân phối xác suất có lợi ích rất lớn so với mô hình không gian véc tơ thông thường. Một ý tưởng của các mô hình chủ đề ẩn là xây dựng những tài liệu mới dựa theo phân phối xác suất. Trước hết, để tạo ra một tài liệu mới, ta cần chọn ra một phân phối những chủ đề cho tài liệu đó, điều này có nghĩa tài liệu được tạo nên từ những chủ đề khác nhau, với những phân phối khác nhau. Tiếp đó, để sinh các từ cho tài liệu ta có thể lựa chọn ngẫu nhiên các từ dựa vào phân phối xác suất của các từ trên các chủ đề. Một cách hoàn toàn ngược lại, cho một tập các tài liệu, ta có thể xác định một tập các chủ đề ẩn cho mỗi tài liệu và phân phối xác suất của các từ trên từng chủ đề. Hai ví dụ về phân tích chủ đề sử dụng mô hình ẩn là Probabilistic Latent Semantic Analysis (pLSA) and Latent Dirichlet Allocation (LDA). PLSA là một kĩ thuật thống kê nhằm phân tích những dữ liệu xuất hiện đồng thời [17]. Nó được phát triển dựa trên LSA kết hợp với một mô hình xác suất. Tuy nhiên, theo phân tích của Blei và các cộng sự (2003) [10], mặc dù LPSA là một bước quan trọng trong việc mô hình hóa dữ liệu văn bản, tuy nhiên nó vẫn còn chưa hoàn thiện ở chỗ chưa xây dựng được một mô hình xác suất tốt ở mức độ tài liệu. Điều đó dẫn đến vấn đề gặp phải khi phân phối xác suất cho một tài liệu nằm ngoài tập dữ liệu học, ngoài ra số lượng các tham số có thể tăng lên một cách tuyến tính khi kích thước của tập dữ liệu tăng. LDA, là một mô hình hoàn thiện hơn so với PLSA và có thể khắc phục được những nhược điểm ở trên. Mô hình chủ đề ẩn này sẽ được sử dụng trong việc xây dựng hệ thống của chúng tôi. 3.2.1 Latent Dirichlet Allocation (LDA) Latent Dirichlet Allocation (LDA) là một mô hình sinh xác suất cho tập dữ liệu rời rạc như text corpora. LDA dựa trên ý tưởng: mỗi tài liệu là sự trộn lẫn của nhiều chủ đề (topic). Về bản chất, LDA là một mô hình Bayesian 3 cấp (three-level hierarchical Bayes model: corpus level, document level, word level) trong đó mỗi phần của mô hình được coi như một mô hình trộn hữu hạn trên cơ sở tập các xác suất chủ đề [27]. 34 3.2.2 Mô hình sinh trong LDA Cho một corpus của M tài liệu biểu diễn bởi D={d1,d2, …, dM}, trong đó, mỗi tài liệu m trong corpus bao gồm Nm từ wi rút từ một tập từ vựng của các mục từ {t1, …, tv}, V là số lượng các mục từ t trong tập từ vựng. LDA cung cấp một mô hình sinh đầy đủ chỉ ra kết quả tốt hơn các phương pháp trước. Quá trình sinh ra văn bản như sau: Hình 9. Mô hình biểu diễn của LDA[15] Các khối vuông trong (Hình 9) biểu diễn các quá trình lặp. Tham số đầu vào: α và β (corpus-level parameter) α: Dirichlet prior on (theta) mϑ r β: Dirichlet prior on kϕr r r mϑ (theta): phân phối của topic trong document thứ m (document-level parameter). biểu diễn tham số cho p(z|d=m), thành phần trộn topic cho tài liệu m. Một tỷ lệ cho mỗi tài liệu, mϑ { } matrix) K(M Mmm ×=Θ =1ϑr zm,n: topic index (word n của văn bản m) wm,n: word n của văn bản m chỉ bởi zm,n (word-level variable, observed word) kϕr : Phân phối của các từ được sinh từ topic zm,n . kϕr biểu diễn tham số cho p(t|z=k), thành phần trộn của topic k. Một tỷ lệ cho mỗi topic, { } matrix) V(K Kkk ×=Φ =1ϕr M: số lượng các tài liệu. 35 Nm: số lượng các từ trong tài liệu thứ m (hay còn gọi là độ dài của văn bản) K: số lượng các topic ẩn. LDA sinh một tập các từ wm,n cho các văn bản md r bằng cách: • Với mỗi văn bản m, sinh ra phân phối topic mϑ r cho văn bản. • Với mỗi từ, zm,n được lấy mẫu dựa vào phân phối topic trên. • Với mỗi topic index zm,n, dựa vào phân phối từ kϕr , được sinh ra. nmw , • kϕr được lấy mẫu một lần cho toàn bộ corpus. Mô hình sinh đầy đủ (đã chú giải) được biểu diễn trong Hình 10. Hình 10. Mô hình sinh đầy đủ cho LDA [28]. Ở đây, Dir, Poiss and Mult lần lượt là các phân phối Dirichlet, Poisson, Multinomial. (Lấy mẫu theo phân phối Dirichlet, Poisson, Multinomial). 3.2.3 Ước lượng tham số và suy luận Cho trước một tập các văn bản, yêu cầu của quá trình này là tìm xem topic model ( , ) nào đã sinh ra tập các văn bản trên. Quá trình ước lượng tham số cho LDA với kỹ thuật Gibbs Sampling gồm các bước: kϕr mϑ r 36 Khởi tạo: lấy mẫu lần đầu. Dưới đây là mã giả của quá trình khởi tạo lấy mẫu lần đầu: ( )t zn ( )z mnzero all count variables, , ,mn , zn [ ]Mm ,1∈for all documents do [ ]mNn ,1∈ for all words in document do m sample topic index ~Mult(1/K) nmz , ( ) 1+smn increment document-topic count: 1+mn increment document-topic sum: ( ) 1+tsn increment topic-term count: 1+zn increment topic-term sum: end for end for Trong đó: : số topic z trong văn bản m ( )zmn : tổng số topic trong văn bản m mn : số term t trong topic z ( )tzn : tổng số term trong topic z zn Mỗi lần lấy mẫu cho một từ, các tham số đối với từng term và topic trên lần lượt được tăng lên. Giai đoạn burn-in: quá trình lấy mẫu lại cho đến khi đạt được một độ chính xác nhất định. Mã giả của quá trình này: while not finished do [ ]Mm ,1∈ for all documents do for all words in document do [ mNn ,1∈ ] m - for the current assignment of to a term t for word : z nmw , 37 ( ) 1−tzn( ) 1−zmn decrement counts and sums: ; 1−mn ; ; 1−zn - multinomial sampling acc. (decrements from previous step): ( )wzzpz ii rr ,|~~ − sample topic index - use the new assignment of to the term t for word to: z nmw , ( ) 1+zm r ; ; n 1+znr1+tzn r increment counts and sums: end for end for Trong mỗi lần lấy mẫu lại: các tham số tương ứng với các topic và term cũ giảm đi 1, các tham số tương ứng với các topic và term mới tăng lên 1. Kiểm tra sự hội tụ và đọc ra các tham số: Quá trình kết thúc, đọc các tham số đầu ra Φvà . Mã giả của quá trình đọc các tham số đầu ra: Θ if converged and L sampling iterations since last read out then - the different parameters read outs are averaged read out parameter set Φacc. to Eq. kϕr read out parameter set Θ acc. to Eq. mϑ r end if end while 2 phân phối ẩn kϕr và được tính như sau: mϑ r ( ) ( ) v V v v k t t k tk n n β βϕ + += ∑ =1 , ( ) ( ) z K z z m k k m km n n α αϑ + += ∑ =1 , Với mô hình ước lượng LDA đã cho, có thể suy luận chủ đề cho các tài liệu mới bằng các thủ tục lấy mẫu tương tự. 38 3.3 Mô hình quảng cáo trực tuyến hướng câu truy vấn với sự giúp đỡ của phân tích chủ đề và kỹ thuật tính hạng Như đã trình bày ở những chương trước, một bài toán quan trọng của quảng cáo trên máy tìm kiếm đó là việc xếp hạng các quảng cáo theo độ phù hợp với truy vấn của người dùng. Từ những phương pháp được trình bày ở Chương II, cho thấy việc lựa chọn các đặc trưng cho việc biểu diễn quảng cáo là hết sức quan trọng. Có những trường hợp giữa quảng cáo và từ khóa có sự phù hợp lớn, tuy nhiên tập từ vựng sử dụng trong quảng cáo và truy vấn là khác nhau. Do vậy, bên cạnh các đặc trưng về từ khóa, việc sử dụng một số đặc trưng ở mức trừu tượng cao hơn là rất cần thiết. Những nghiên cứu của Andrei và các cộng sự [11] đã cho thấy, việc sử dụng các đặc trưng mở rộng như phân lớp truy vấn, cụm từ Prisma đem lại những kết quả khả quan. Đặc biệt là nghiên cứu của Lê Diệu Thu [27] đã chỉ ra rằng, việc sử dụng chủ đề ẩn trong quảng cáo theo ngữ cảnh nhằm mở rộng tập từ vựng của quảng cáo cũng như trang web đem lại kết quả rất khả quan. Trong phần này, ta sẽ trình bày một mô hình quảng cáo trực tuyến trên máy tìm kiếm sử dụng kĩ thuật phân tích chủ đề ẩn và tính hạng. Khác với mô hình đã được xây dựng bởi Lê Diệu Thu [27], mô hình của chúng ta được xây dựng nhằm mục đích xếp hạng quảng cáo trên máy tìm kiếm theo truy vấn của người dùng. Kĩ thuật chủ đề ẩn được sử dụng trong việc xây dựng những đặc trưng mới để biểu diễn quảng cáo. Ngoài ra, mô hình còn khai thác một lượng lớn các query logs nhằm xây dựng tập dữ liệu học. 3.3.1 Mô tả bài toán Bài toán được mô tả như sau: Từ truy vấn của người dùng và một tập các quảng cáo đã có sẵn, yêu cầu đưa ra K quảng cáo phù hợp nhất với truy vấn. Input: - Truy vấn q - Tập quảng cáo A = {a1, a2, ..., an} Output: - K quảng cáo R = {ar1, ar2, ..., ark} Để giải quyết bài toán, chúng ta xây dựng hàm ranking F như sau: F: {Q}x{A} Æ [0,1] 39 Với F(q, a) trả về độ phù hợp của quảng cáo a đối với truy vấn q, độ phù hợp càng lớn quảng cáo sẽ được xếp hạng càng cao. Zeng [29] và Xu [29] đã chỉ ra rằng, sử dụng thuật toán SVM ranking đem lại kết quả tốt trong việc xếp hạng cũng như phân cụm kết quả tìm kiếm, khi sử dụng cả truy vấn, title và snippet (nội dung tóm tắt) trong quá trình học. Trong mô hình này, SVM rank sẽ được sử dụng để xây dựng hàm xếp hạng F như trên. 3.3.2 Mô hình tổng quan Từ những nghiên cứu đã được đề cập ở trên, chúng tôi đề xuất hệ thống quảng cáo trên máy tìm kiếm sử dụng phân tích chủ đề ẩn và kĩ thuật tính hạng. Hệ thống được mô tả một cách tổng quan như sau. Model estimation (2) Estimated Model Topic inference (6) Key word Matching (5) Ads Relevant Ads New Training data (3) Learn to rank model (4) Ranking function (7) Relevant Ads Ranking Training data (1) Hình 11. Mô hình tổng quan hệ thống quảng cáo sử dụng chủ đề ẩn Mô hình gồm các bước chính sau: 1) Xây dựng tập dữ liệu học. Tập dữ liệu học được xây dựng bằng cách phân tích các query logs, thu thập các tiêu đề, mô tả của trang web và coi chúng như một quảng cáo (tài liệu). 40 2) Xây dựng mô hình chủ đề ẩn, xác định các chủ đề và phân phối xác suất của các chủ đề trên từng tài liệu. 3) Xây dựng tập dữ liệu học với đặc trưng mới, các đặc trưng ở đây gồm có tần suất xuất hiện của từ khóa và xác suất để mỗi tài liệu thuộc vào một chủ đề. 4) Xây dựng hàm xếp hạng từ tập dữ liệu học thu được. Hàm xếp hạng được xây dựng sử dụng thuật toán SVM-Rank. 5) Tìm kiếm các quảng cáo phù hợp với truy vấn. 6) Xác định chủ đề ẩn của quảng cáo và biểu diễn quảng cáo theo đặc trưng mới. 7) Xếp hạng các quảng cáo sử dụng hàm xếp hạng đã được xây dựng từ tập dữ liệu học. 3.3.3 Xác định đặc trưng cho mô hình Trong mô hình này, chúng ta coi mỗi quảng cáo (bao gồm nội dung, tiêu đề) là một tài liệu. Coi các snippet (tiêu đề và mô tả) của trang web là một tài liệu. Giả sử tập tài liệu của chúng ta là D = {d1, d2, …, dm}. Chúng ta sử dụng các đặc trưng sau trong quá trình xây dựng hàm ranking nhờ thuật toán SVM-Rank: Term Frequency / Inverse Document Frequency: ݐ ௜݂,௝ ൌ ݊௜,௝ ∑ ݊௞,௝௞ Term Frequency (TF): Trong đó: ni,j là tần suất xuất hiện của từ khóa ti trong tài liệu j Inverse Document F u IDFreq ency ( ): ݅݀ ௜݂ ൌ log |ܦ| |ሼ݀: ݐ௜ א ݀ሽ| Trong đó: |D| là số lượng tài liệu trong tập D |{d: ti Є d}| là số lượng tài liệu mà từ khóa ti xuất hiện. ሺݐ݂ െ ݂݅݀ሻ௜,௝ ൌ ݐ ௜݂,௝ ݔ ݅݀ ௜݂ Chúng ta có: 41 Hidden Topic: Giả sử chúng ta xác định được K topic từ tập dữ liệu học. Với mỗi tài liệu d, chúng ta tính các xác suất để tài liệu d thuộc vào topic i là pd(i), với i = 1,k. Từ đó xác định được véc tơ topic của tài liệu d: T(d) = [pd1, pd2, …, pdk] Từ hai đặc trưng trên, chúng ta xây dựng được véc tơ đại diện tài liệu V(d): V(d) = [tfidf(t1, d), tfidf(t2, d),…,tfidf(tm, d), pd1, pd2, …, pdk] 42 Chương 4. Thực nghiệm và đánh giá 4.1. Dữ liệu Mô hình sử dụng query log để xây dựng bộ dữ liệu trong quá trình học. Query log là một phần quan trọng của máy tìm kiếm. Nó ghi lại các hành vi của người dùng trong khi tìm kiếm, cũng như những mối quan tâm của người dùng đối với mỗi truy vấn. Query log không chứa các quảng cáo hiển thị ra với người dùng, tuy nhiên nó chứa các truy vấn được nhập vào, cũng như những kết quả tìm kiếm được người dùng click. Quảng cáo, thực chất là những tài liệu với tựa đề và phần mô tả cho trang web mà quảng cáo trỏ tới. Do vậy, chúng ta có thể xem tựa đề và những tóm tắt của trang web (thường được đặt trong các thẻ meta) như một nội dung quảng cáo và sử dụng trong quá trình học. Việc sử dụng query log sẽ giúp khai thác rất nhiều thông tin hữu ích từ những hành vi của người dùng trong khi tìm kiếm. Chúng tôi sử dụng 1Gb query logs được lấy từ máy tìm kiếm MSN [36] với14 triệu query & url được click. Các query đều bằng tiếng Anh. Mỗi query log gồm các thông tin như sau: - QueryID: số hiệu của query, những query log có cùng số hiệu thì cùng thuộc một phiên làm việc. - Query: nội dung query, đây là nội dung query được người dùng nhập vào. - Time: thời điểm người dùng click vào URL. - URL: URL được người dùng click. - Position: vị trí của url được click trong danh sách kết quả trả về. 4.2. Môi trường thực nghiệm 4.2.1 Cấu hình phần cứng Quá trình thực nghiệm được tiến hành trên máy tính có cấu hình phần cứng như sau: 43 Bảng 2 Cấu hình phần cứng sử dụng trong thực nghiệm Thành phần Chỉ số CPU 1 Pentium IV 3.06 GHz RAM 1.5 GB OS WindowsXP Service Pack 2 Bộ nhớ ngoài 240GB 4.2.2 Các công cụ được sử dụng Dưới đây là các công cụ mã nguồn mở được sử dụng trong quá trình thực nghiệm: Bảng 3. Danh sách các phần mềm mã nguồn mở được sử dụng STT Tên phần mềm Tác giả Nguồn 1 SVM-Rank Joachims 2 GibbsLDA++ Phan Xuân Hiếu Ngoài các cộng cụ kể trên, chúng tôi xây dựng các module xử lý bằng ngôn ngữ Python như sau: • Module filter: lọc trong 14 triệu query logs, lấy ra 1 triệu query log đầu tiên. Gom nhóm tất cả các url được trả về bởi cùng một query, tính điểm cho mỗi URL trên từng phiên làm việc và tổng hợp điểm cho mỗi URL trên tất cả các phiên làm việc. Sắp xếp các URL theo thứ tự giảm dần về điểm. • Module crawl: từ các URL thu được bởi module filter, tiến hành crawl nội dung trang web, phân tích và lấy ra tiêu đề, mô tả của trang web. Chúng ta coi mô tả và tiêu đề của một trang web là một tài liệu trong bộ dữ liệu học. • Module normalize: Chuẩn hóa các nội dung thu được bởi module crawl như loại bỏ từ dừng, các kí hiệu vô nghĩa, các nội dung trống. 44 • Module tfidf: Véc tơ hóa các tài liệu đã thu được theo đặc trưng về tần suất xuất hiện của từ khóa, TF-IDF. • Module tfidf_lda: Véc tơ hóa các tài liệu thu được theo đặc trưng về tần suất xuất hiện của từ khóa, TF-IDF và đặc trưng về xác suất xuất hiện của tài liệu trong từng chủ đề ẩn. • Module test: Từ các quảng cáo đã được sắp xếp theo ý kiến người dùng, tiến hành véc tơ hóa các quảng cáo theo đặc trưng về tần suất xuất hiện các từ khóa, sau đó xếp hạng các kết quả này bằng hàm xếp hạng. Kết quả trả về sẽ được so sánh với kết quả người dùng đưa ra và tính toán các độ đo NDCG, MAP. • Module test_lda: Từ các quảng cáo đã được sắp xếp theo ý kiến người dùng, tiến hành suy luận các chủ đề ẩn mà mỗi quảng cáo có thể thuộc vào. Véc tơ hóa mỗi quảng cáo theo đặc trưng tần suất xuất hiện của từ hóa và đặc trưng xác suất mỗi quảng cáo thuộc vào các chủ đề ẩn. Xếp hạng các kết quả này bằng hàm xếp hạng. Kết quả trả về sẽ được so sánh với kết quả người dùng đưa ra và tính toán các độ đo NDCG, MAP. 4.3. Quá trình thực nghiệm Quá trình thực nghiệm gồm các bước chính sau đây • Xử lý dữ liệu: tiền xử lý dữ liệu, xây dựng tập tài liệu học cho mô hình, véc tơ hóa dữ liệu. • Xây dựng hàm xếp hạng: tiến hành training trên tập dữ liệu đã có bằng thuật toán SVM-Rank. • Xây dựng tập test: thu thập các quảng cáo trên máy tìm kiếm MSN. • Đánh giá kết quả mô hình: thu thập ý kiến người dùng và so sánh với kết quả mô hình đưa ra. 4.3.1. Tiền xử lý dữ liệu Lấy về một triệu query log đầu tiên, trong số query log này, chọn ra tất cả các query có số click của người dùng lớn hơn 4. Kết quả thu được gồm 30,372 query. Một query có 45 thể được nhiều người dùng nhập vào tại các thời điểm khác nhau. Chúng ta tiến hành tính điểm cho mỗi URL đối với một query như sau: o Trong một phiên làm việc, liệt kê các URL được người dùng click vào. o Gán điểm cho mỗi URL giảm dần từ 100 theo thứ tự click của người dùng. Ví dụ: với từ khóa yahoo, có 4 url trả về và lần lượt được click theo thứ tự: Khi đó điểm lần lượt cho 4 URL trong phiên làm việc đó là 100, 90, 80, 70. o Tính tổng điểm cho tất cả các URL đối với một query trên các phiên làm việc khác nhau. o Với mỗi query, sắp xếp các URL được người dùng click theo thứ tự giảm dần về điểm. Nếu hai URL có điểm bằng nhau, chúng ta xét đến vị trí (position) của URL trong số các URL trả về. Kết quả này sẽ được sử dụng trong bước xử lý tiếp theo. Cách tính điểm như trên có các đặc điểm sau: o Những URL được click nhiều sẽ có điểm cao hơn những URL được click ít. o Những URL trong một phiên làm việc được click trước sẽ có điểm cao hơn những URL được click sau. Với cách tính điểm đó, chúng ta khai thác được mối quan tâm của người dùng đối với một truy vấn. 4.3.2. Thu thập thông tin từ các URL có được Từ danh sách các URL đã được sắp xếp theo điểm thu được ở trên. Chúng ta tiến hành lấy về tiêu đề và mô tả của các trang web tương ứng với mỗi URL. Tại bước này, có thể gặp những trang web đã chết hoặc URL bị hỏng và cần được loại bỏ. Kết hợp nội dung tiêu đề và mô tả của trang web lại, chúng ta có dữ liệu cho quá trình học. Tiến hành loại bỏ những URL mà nội dung thu được là rỗng, từ đó chỉ giữ lại những query có từ 4 nội dung kết quả trở lên. Kết thúc bước này thu được danh sách gồm 16,534 query và 83,312 nội dung (tóm tắt) các trang web tương ứng với query đó. 46 Việc sử dụng tiêu đề và mô tả (description) của trang web không hẳn là phương pháp tối ưu để xây dựng tập dữ liệu học, tuy nhiên nó có thể tốt hơn việc sử dụng toàn bộ nội dung trang web, điều mà có thể gây nhiễu lớn trong quá trình học. 4.3.3. Véc tơ hóa dữ liệu Việc véc tơ hóa dữ liệu sẽ được thực hiện trong quá trình trích chọn các đặc trưng sau: a) TF-IDF Tiến hành loại bỏ từ dừng, các kí hiệu, kí tự không có nghĩa, chúng ta thu được danh sách các từ khóa trong tập dữ liệu. Mỗi từ khóa sẽ được xem như một đặc trưng của dữ liệu. Tính toán trọng số cho các dữ liệu tại các đặc trưng theo TF-IDF chúng ta thu được véc tơ trọng số tf-idf: D(d) = (tfidf(d, 1), tfidf(d,2), ..., tfidf(d, n)) Với n là số lượng các từ khóa riêng biệt. b) Chủ đề ẩn Từ tập dữ liệu đã có, sử dụng công cụ GibbsLDA++ [16] chúng ta thu được danh sách các chủ đề ẩn và xác suất để một dữ liệu thuộc vào một chủ đề. Chọn số chủ đề là 100. Chúng ta xác định được véc tơ đặc trưng cho chủ đề ẩn đối với mỗi dữ liệu . H(d) = (pd1, pd2, ..., pd50) Kết hợp hai véc tơ H(d) và D(d) ở trên, chúng ta thu được véc tơ đại diện dữ liệu V(d). 4.3.4. Thiết kế thực nghiệm Để đánh giá sự ảnh hưởng của chủ đề ẩn đối với kết quả xếp hạng chúng ta tiến hành cài đặt 2 hệ thống xếp hạng như sau: • Hệ thống thứ nhất sử dụng SVM-Rank chỉ với các đặc trưng về tần suất xuất hiện của từ khóa trong tài liệu (TF-IDF). Hệ thống này được gọi là RTF. 47 • Hê thống thứ hai sử dụng SVM-Rank với các đặc trưng về tần suất xuất hiện của từ khóa và các xác suất để tài liệu thuộc vào các chủ đề ẩn. Hệ thống này gọi là RHT. Chọn môt số truy vấn, tiến hành tìm kiếm bằng tay trên một vài máy tím kiếm như MSN, Yahoo, Google. Tổng số truy vấn được sử dụng là 40 truy vấn, về các lĩnh vực khác nhau như: computer, sport, medicine… Từ các trang kết quả, lấy về 5 quảng cáo cho mỗi truy vấn. Việc đánh giá mô hình được tiến hành theo hai bước: • Từ các quảng cáo thu được, tiến hành loại bỏ từ dừng, các kí tự, kí hiệu không có ý nghĩa. Xác định chủ đề ẩn cho mỗi quảng cáo, tính phân phối xác suất của mỗi chủ đề trên quảng cáo. Xây dựng véc tơ quảng cáo từ các xác suất thu được và tần suất xuất hiện của từ khóa trong quảng cáo. Sử dụng công cụ SVM-Rank với mô hình thu được trong quá trình học để xếp hạng các kết quả. • Lấy ý kiến đánh giá của người dùng đối với danh sách kết quả thu được theo truy vấn. Tiến hành lấy ý kiến 5 người dùng, đưa ra cho họ một yêu cầu như: “với truy vấn như trên, bạn hãy lần lượt click vào các link sau theo thứ tự phù hợp”. Ý kiến của mỗi người dùng sẽ được sử dụng để xác định một số độ đo cho mô hình, cuối cùng chúng ta tính kết quả cuối cùng bằng cách lấy trung bình các độ đo. 4.4. Kết quả thực nghiệm Trước hết chúng ta so sánh trung bình các độ đo trên toàn bộ các truy vấn. Kết quả cho thấy hệ thống RHT với việc sử dụng chủ đề ẩn đem lại kết quả trung bình cao hơn so với RTF. Tại các độ đo MAP và NDCG@5 kết quả của RHT lần lượt là 0.75 và 0.84 (Hình 12). 48 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 RTF RHT MAP NDCG@1 NDCG@3 NDCG@5 T vấn kh H thống là 0.84 Hình 12. Trung bình các độ đo trên tất cả các truy vấn iến hành s ác nhau. o sánh trung bình các độ đo NDCG@5 và MAP trên từng số lượng truy 0.805 0.81 0.815 0.82 0.825 0.83 0.835 0.84 0.845 0.85 0.855 Hình 13. T ình 13 ch RTF. Giá tại số truy rung bình o thấy trun trị cực đại đ vấn 40. 10 độ đo NDC g bình độ đ ạt được là 20 49 G@5 tại o NDCG@ 0.85 tại số 30 các sô lượn 5 của hệ t truy vấn 1 4 g truy vấn hống RHT 0 và giá trị 0 RTF RHT khác nhau cao hơn so cựu tiểu đ với hệ ạt được 0.7 0.71 0.72 0.73 0.74 0.75 0.76 0.77 0.78 0.79 0.8 10 20 30 40 RTF RHT Hình 14. Trung bình độ đo MAP tại các số lượng truy vấn khác nhau Hình 14 cho thấy trung bình độ đo MAP của RHT cao hơn so với hệ thống RTF. Giá trị cực đại đạt được là 0.79 tại số truy vấn 10 và cực tiểu là 0.75 tại số truy vấn 40. Dưới đây là bảng giá trị các độ đo tại một số truy vấn khác nhau trên hệ thống RHT. Bảng 4. Giá trị các độ đo tại một số truy vấn khác nhau. Truy vấn MAP NDCG@1 NDCG@3 NDCG@5 paint colors for bedrooms 0.91 0.93 0.82 0.91 tennis equipment 0.77 0.79 0.68 0.85 baseball bats 0.86 1.0 0.77 0.88 shirt deign 0.75 0.87 0.68 0.87 4.5. Đánh giá kết quả thực nghiệm Thực nghiệm cho thấy mô hình xếp hạng quảng cáo đã được xây dựng đem lại kết quả khá tốt. Giá trị trung bình các độ đo NDCG@5 vào khoảng 0.82-0.84 và độ đo MAP vào khoảng 0.73-0.75. 50 Một số nguyên nhân có thể ảnh hưởng tới kết quả này: • Việc sử dụng ý kiến người dùng để đánh giá kết quả: mỗi người dùng, đối với mỗi truy vấn có thể có những mục đích tìm kiếm cũng như mối quan tâm khác nhau. Điều này dẫn tới việc các kết quả có sự khác biệt lớn giữa đánh giá của các người dùng. • Việc sử dụng tiêu đề và mô tả trang web làm dữ liệu học: nội dung tiêu đề và mô tả của trang web thường có tác dụng cho chúng ta một cái nhìn tổng quan về trang web đó. Tuy nhiên, với một số trang web được xây dựng không tốt, không theo tiêu chuẩn, tiêu đề và mô tả của trang web đó có thể không có hoặc nội dung không liên quan tới nội dung trang web. Mặt khác, thực nghiệm cũng đưa ra sự so sánh giữa việc sử dụng và không sử dụng chủ đề ẩn trong việc xếp hạng quảng cáo. Việc sử dụng chủ đề ẩn đem lại kết quả khá khả quan, trung bình độ đo NDCG@5 tăng 0.2 và MAP tăng 0.2 so với việc không sử dụng chủ đề ẩn. Từ những kết quả trên, ta thấy việc sử dụng mô hình chủ đề ẩn nhằm xây dựng các đặc trưng mới để biểu diễn quảng cáo có tác dụng tốt trong việc xếp hạng quảng cáo theo truy vấn của người dùng. Ngoài ra, việc khai thác các query logs để xây dựng tập dữ liệu học giúp mô hình khai thác được mối quan tâm của người dùng đối với từng truy vấn tìm kiếm. 51 Kết luận Với tốc độ phát triển nhanh chóng của internet và máy tìm kiếm, việc giải quyết các vấn đề được đặt ra trong quảng cáo trực tuyến ngày càng trở nên cấp thiết. Bài toán xếp hạng quảng cáo trên máy tìm kiếm theo truy vấn của người dùng là một vấn đề đang nhận được nhiều sự quan tâm ngày nay. Mục đích chính của khóa luận này nhằm đưa ra một phương pháp giải quyết cho bài toán nếu trên theo hướng tiếp cận sử dụng mô hình chủ đề ẩn. Khóa luận đã đạt được những kết quả: • Giới thiệu khái quát về quảng cáo trực tuyến, tình hình quảng cáo trực tuyến trên thế giới cũng như ở Việt Nam. • Phân tích một số phương pháp và mô hình đã được sử dụng trong quảng cáo trực tuyến. • Đưa ra mô hình quảng cáo trực tuyến hướng câu truy vấn với sự giúp đỡ của chủ đề ẩn và kỹ thuật xếp hạng. Phương pháp khai thác query logs nhằm mục đích xây dựng tập dữ liệu học. • Thực nghiệm và đánh giá kết quả của mô hình được đưa ra. Kết quả cho thấy trong một số trường hợp mô hình cải tiến độ chính xác tới 0.2. Do giới hạn về thời gian cũng như kiến thức của tác giả nên khóa luận còn có một số điểm hạn chế, đó là chưa xây dựng được tập dữ liệu quảng cáo và module tìm kiếm quảng cáo theo truy vấn của người dùng. Những hạn chế này cần được tiếp tục nghiên cứu để xây dựng một hệ thống hoàn thiện hơn, có thể áp dụng cho các máy tìm kiếm ở Việt Nam. 52 Tài liệu tham khảo Tiếng Việt [1] Bộ Công Thương, Báo cáo thương mại điện tử Việt Nam năm 2008, [2] 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”. Luận văn thạc sĩ, Đại học công nghệ, ĐHQGHN, 2008. [3] Dân Trí, Báo điện tử Dân Trí [4] Hiệp hội quảng cáo Việt Nam VAA, [5] Thư viện thông tin Zing Directory, 2008. [6] Từ điển Bách khoa toàn thư Việt Nam [7] VnExpress. Báo điện tử trực tuyến Việt Nam, Tiếng Anh [8] Advertising Educational Foundation. Advertising & Society Review, Volume 6, Issue 1. E-ISSN 1154-7311, 2005. [9] Kevin Amos, director-product development at search-engine marketing firm Impaqt Oser, 2004. [10] D. Blei, A. Ng, and M. Jordan. Latent Dirichlet Allocation. Journal of Machine Learning Research, 3:993-1022, January 2003. [11] Andrei Z. Broder; Ciccolo, P.; Fontoura, M.; Gabrilovich, E.; Josifovski, V.; Riedel, L. Search advertising using web relevance feedback. In Proceeding of the 17th ACM conference on Information and knowledge management, 2008. Pages 1013-1022 . [12] Yunbo Cao, Jun Xu, Tie-yan Liu, Hang Li, Yalou Huang, Hsiao-wuen Hon. Adapting ranking SVM to document retrieval. In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2006. 53 [13] Chakrabarti, S. “Learning to rank in vector spaces and social networks”. Tutorial - 16th international conference on World Wide Web(2007). [14] R. Herbrich, T. Graepel, and K. Obermayer. Large Margin Rank Boundaries for Ordinal Regression. Advances in Large Margin Classifiers, pages 115-132, 2000. [15] Phan Xuan Hieu, Susumu Horiguchi, Nguyen Le Minh (2008). Learning to Classify Short and Sparse Text & Web with Hidden Topics from Large-scale Data Collections, In Proc. of The 17th International World Wide Web Conference, 2008. [16] Phan Xuan Hieu, “GibbsLDA++: A C/C++ and Gibbs Sampling based Implementation of Latent Dirichlet Allocation (LDA)”, 2007. [17] T. Hofmann. Probabilistic LSA. Proc. UAI, 1999. [18] Ms. Duong Thu Huong, Public Relations & Operations Manager at IDG Ventures Vietnam based in Ho Chi Minh City, VietnamNet e-newspaper, [19] K. Jarvelin and J. Kekalainen. IR evaluation methods for retrieving highly relevant documents. Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, pages 41-48, 2000. [20] Kalervo Järvelin & Jaana Kekäläinen University of Tampere Department of Information Studies Finland. IR evaluation methods for retrieving highly relevant documents.. 2000. [21] Joachims, T., Li, H., Liu, T.-Y., and Zhai, C. Learning to rank for information retrieval (lr4ir 2007). SIGIR Forum 41, 2 (2007), 58- 62. [22] A. Lacerda, M.Cristo, M.Andre; G., W.Fan, N.Ziviani, and B.Ribeiro-Neto. Learning to Advertise. In SIGIR06, ACM: Proc.of the 29th annual intl. ACMSIGIRconf., pages 8. CONCLUSION 549556, NewYork, NY, 2006. [23] Liu, T.-Y. “Learning to rank in information retrieval”. In WWW '08: Tutorial - 17th international conference on World Wide Web (2008). 54 [24] B.Ribeiro-Neto, M.Cristo,P.B.Golgher, and E.S. de Moura. Impedance Coupling in Content-targeted Advertising. In SIGIR05, ACM: Proc. Of the 28th annual intl. ACMSIGIR conf., pages 496503, New York, NY, 2005. [25] M.Richardson, E. Dominowska, R. Ragno. Predicting Clicks: Estimating the Click-Through Rate for New Ads. January 2007 In Proceedings of the 16th International World Wide Web Conference Pages: 521 - 530. [26] G. Salton, A. Wong, C.S. Yang. A Vector Space Model for Automatic Indexing, Communication of the ACM, Volum 18, Number 11, 1975. [27] Le Dieu Thu, On the analysis of large-scale datasets towards online contextual advertising, thesis in Coltech of Technology, Viet Nam National University, Ha Noi, Viet Nam, 2008. [28] Nguyen Cam Tu, (2008). Hidden Topic Discovery Toward Classification And Clustering In Vietnamese Web Documents. MSc. thesis in Coltech of Technology, Viet Nam National University, Ha Noi, Viet Nam, 2008. [29] Jun Xu, Yunbo Cao, Hang Li, Yalou Huang. Cost-sensitive learning of SVM for ranking. In ECML , 2006. [30] W.Yih, J.Goodman, andV.R.Carvalho. Finding advertising keywords on web pages. In WWW06, ACM: Proc. Of the 15th intl. conf. on World Wide Web, pages 213222, NewYork, NY, 2006. [31] H. J. Zeng, Q. C. He, Z. Chen, W. Y. Ma, J. Ma.Learning to Cluster Web Search Results.. In Proceedings of the ACM SIGIR Conference, 2004. [32] CIA Advertising, www.ciaadvertising.org. [33] Interactive Advertising Bureau (IAB) and Price Water House Coopers (PWC), Internet Advertising Revenue Report, [34] Internet Archive, [35] Joachims SVM-Rank toolkit [36] Microsoft Social Network MSN, [37] Nutch: an open-source search engine, 55 56 [38] Online Advertising, news and quality online advertising information, [39] Wikipedia, The Free Encyclopedia