Mục lục
Lời mở đầu. 1
Chương 1. Khái quát vềquảng cáo trực tuyến. 3
1.1. Giới thiệu vềquảng cáo. 3
1.2. Quảng cáo trực tuyến. 4
1.2.1. Tốc độtăng trưởng và thịphần. 4
1.2.2. Các hình thức quảng cáo trực tuyến. 5
1.3. Quảng cáo trực tuyến ởViệt Nam. 6
1.3.1. Tổng quan vềquảng cáo trực tuyến ởViệt Nam. 7
1.3.2. Những tài nguyên chưa được khai thác và thịtrường quảng cáo trực tuyến. 10
1.4. Quảng cáo thông qua tìm kiếm. 13
Chương 2. Các phương pháp quảng cáo thông qua tìm kiếm. 16
2.1. Mô hình trích xuất từkhóa trong nội dung trang web. 16
2.2. Mô hình so khớp với tập từvựng mởrộng (impedance coupling). 17
2.3. Mô hình tối ưu xếp hạng với thuật toán di truyền (Genetic Programming). 18
2.4. Mô hình quảng cáo sửdụng phản hồi liên quan. 19
2.5. Mô hình ước lượng CTR (Click Through Rate). 21
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. 22
Chương 3. Hệthống quảng cáo trực tuyến sửdụng xếp hạng và chủ đề ẩn. 25
3.1 Xếp hạng. 25
3.1.1 Xếp hạng trong máy tìm kiếm. 25
3.1.2 Học xếp hạng và SVM Rank. 26
3.1.3 Các phương pháp đánh giá xếp hạng. 30
3.2 Chủ đề ẩn. 33
3.2.1 Latent Dirichlet Allocation (LDA). 34
3.2.2 Mô hình sinh trong LDA. 35
3.2.3 Ước lượng tham sốvà suy luận. 36
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. 39
3.3.1 Mô tảbài toán. 39
3.3.2 Mô hình tổng quan. 40
3.3.3 Xác định đặc trưng cho mô hình. 41
Chương 4. Thực nghiệm và đánh giá. 43
4.1. Dữliệu. 43
4.2. Môi trường thực nghiệm. 43
4.2.1 Cấu hình phần cứng. 43
4.2.2 Các công cụ được sửdụng. 44
4.3. Quá trình thực nghiệm. 45
4.3.1. Tiền xửlý dữliệu. 45
4.3.2. Thu thập thông tin từcác URL có được. 46
4.3.3. Véc tơhóa dữliệu. 47
4.3.4. Thiết kếthực nghiệm. 47
4.4. Kết quảthực nghiệm. 48
4.5. Đánh giá kết quảthực nghiệm. 50
Kết luận. 52
Tài liệu tham khảo. 53
65 trang |
Chia sẻ: maiphuongdc | Lượt xem: 1560 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Khóa luậ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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ấn dài bao gồm nhiều từ
khóa. Yih và các cộng sự [30] đã đề xuất một mô hình học giám sát cho phép trích xuất
các từ khóa trong nội dung trang web. Tiến hành học từ một tập các trang web đã được
định nghĩa các từ khóa từ trước, họ xây dựng một bộ phân lớp sử dụng học máy với thuật
toán hồi quy logic (logistic regression).
Để xác định những từ khóa và cụm từ mô tả chính xác nhất về trang web họ sử dụng
một vài phương pháp và tiến hành thực nghiệm để tìm ra phương pháp đem lại kết quả tốt
nhất. Ba phương pháp được đưa ra đó là: MoS, MoC và DeS. M (Monolithic) nghĩa là sử
dụng toàn bộ cụm từ trong trích chọn. D (Decomposed) xem mỗi từ trong cụm như một
cá thể riêng biệt. S (Separate) là coi mỗi từ hay cụm từ bất kể giống nhau hay khác nhau
như các cá thể riêng biệt, và C (Combined) kết hợp các từ, cụm từ giống nhau làm một.
Một điểm quan trọng trong công trình của họ đó là việc sử dụng 7.5 triệu truy vấn từ
query logs của MSN [36] như một đặc trưng cho quá trình trích chọn, cùng với đó là 11
16
đặc trưng khác như tần suất xuất hiện của từ khóa, đặc trưng thuộc về ngôn ngữ học (pos
tagging), đặc trưng kiểm tra từ có được viết hoa hay không, đặc trưng về siêu văn bản (từ
có nằm trong một liên kết hay không), tiêu đề trang, đặc trưng về độ dài các cụm từ, các
câu,…
Trong thực nghiệm, họ sử dụng 828 trang web được lấy từ Internet Archive [34] để
sử dụng cho quá trình học và kiểm thử hệ thống. Kết quả cho thấy hệ thống MoC (các
cụm từ tương đương được kết hợp làm một) đem lại kết quả tốt nhất, trong khi đó MoS
đem lại kết quả thấp nhất. Ngoài ra, hệ thống DeS (xem mỗi từ như một cá thể riêng biệt)
đem lại kết quả thấp hơn so với hệ thống Monolothic(xem mỗi cụm từ như một cá thể
riêng biệt). Độ chính xác của hệ thống tốt nhất là 30.06% và của hệ thống tồi nhất là
13.01% .
Để xác định sự đóng góp của mỗi đặc trưng, họ tiến hành thực nghiệm trên cùng
một hệ thống với các đặc trưng được thêm vào lần lượt. Kết quả chỉ ra rằng, đặc trưng
query log và tần xuất xuất hiện của từ khóa đóng vai trò quan trọng nhất.
Nghiên cứu của Yih và các cộng sự [30] cho thấy một hướng tiếp cận khác của
quảng cáo theo ngữ cảnh. Hệ thống của họ cho phép xếp hạng các quảng cáo dựa trên
những từ khóa trích xuất ra được từ trang web. Tuy nhiên độ phù hợp của các quảng cáo
dựa trên các từ khóa này vẫn chưa được kiểm chứng qua thực nghiệm.
2.2. Mô hình so khớp với tập từ vựng mở rộng (impedance coupling)
Một vấn đề của quảng cáo theo ngữ cảnh, đó là sự khác biệt về từ vựng giữa trang
web và các quảng cáo. Ribeiro Neto và các cộng sự [24] đã tập trung vào việc giải quyết
vấn đề này bằng cách mở rộng tập từ vựng của các trang web.
Nhìn chung, một quảng cáo thường ngắn, cô đọng và tập trung vào một chủ đề
chính. Tuy nhiên, một trang web lại có nội dung lớn hơn và thuộc một không gian ngữ
cảnh lớn hơn. Một trang web có thể nói về rất nhiều chủ đề và với các từ khóa khác nhau.
Vấn đề tìm kiếm những quảng cáo phù hợp với một trang web sử dụng những chủ đề có
trong nội dung trang đang là một vấn đề cần được quan tâm.
Ribeiro và các cộng sự [24] đã khảo sát 10 phương pháp so khớp các quảng cáo và
trang web. Họ tiến hành thực nghiệm với một cơ sở dữ liệu lớn trên 93 nghìn quảng cáo
và 100 trang web.
17
Với 5 phương pháp đầu tiên, họ so sánh các trang web và quảng cáo dựa vào mô
hình véc tơ. Hạng của mỗi quảng cáo được tính dựa trên độ tương đồng cosin giữa quảng
cáo và trang web. Các đặc trưng được sử dụng là tiêu đề, mô tả và các từ khóa quảng cáo.
Phương pháp tốt nhất trong những phương pháp này là AAK, “so khớp sử dụng các từ
khóa quảng cáo xuất hiện trong nội dung trang web”, kết quả của phương pháp này được
sử dụng để so sánh với các phương pháp “impedance coupling”.
Như đã giới thiệu ở trên, có một sự khác biệt lớn giữa tập từ vựng của trang web và
quảng cáo. Để giải quyết vấn đề này, Ribeiro và các cộng sự [24] mở rộng tập từ vựng
của trang web với những từ khóa lấy từ các trang web có nội dung tương tự sử dụng mô
hình Bayes. Những từ khóa mở rộng này có thể xuất hiện trong tập từ khóa của quảng cáo
và làm tăng hiệu quả của hệ thống. Họ sử dụng 5 phương pháp so khớp khác nhau gọi là
các phương pháp “impedance coupling”.
Trong thực nghiệm, họ sử dụng một cơ sở dữ liệu với 6 triệu trang web để phục vụ
cho việc mở rộng tập từ vựng. Kết quả thu được khi sử dụng các nội dung đã được mở
rộng tốt hơn so với phương pháp AAK ở trên. Phương pháp tốt nhất được đưa ra đó là so
khớp sử dụng nội dung trang web mở rộng và nội dung của trang web được quảng cáo trỏ
tới. Thực nghiệm của Ribeiro-Neto và các cộng sự đã chứng tỏ rằng, việc giảm sự khác
biệt về tập từ vựng giữa trang web và quảng cáo có thể hỗ trợ tốt cho việc tìm kiếm quảng
cáo phù hợp với ngữ cảnh.
2.3. Mô hình tối ưu xếp hạng với thuật toán di truyền (Genetic Programming)
Từ những nghiên cứu đã có được [24], Lacerda và các cộng sự [22] đã đưa ra một
hướng tiếp cận dựa trên thuật toán di truyền để tối ưu hàm xếp hạng. Sử dụng các đặc
trưng khác nhau như từ khóa, tần suất xuất hiện của từ, độ dài văn bản và kích thước tập
dữ liệu, bằng phương pháp học máy, họ xây dựng một hàm so khớp nhằm tối ưu độ phù
hợp giữa trang web và các quảng cáo. Hàm này được thể hiện dưới dạng cây với nút là
các phép toán và các đặc trưng là các lá. Sử dụng tập dữ liệu học và đánh giá tương tự
như ở [24], mô hình này đem lại kết quả tốt hơn so với phương pháp tốt nhất được mô tả
ở đó là 61.7%.
18
2.4. Mô hình quảng cáo sử dụng phản hồi liên quan
Dựa trên những nghiên cứu về xử lý truy vấn và mở rộng câu truy vấn, Andrei
Z.Broder và các cộng sự [11] đã đưa ra mô hình quảng cáo trên máy tìm kiếm sử dụng
phản hồi liên quan. Với một truy vấn đầu vào gọi là truy vấn gốc, Andrei Z.Broder tiến
hành tìm kiếm trên các máy tìm kiếm và thu thập một số kết quả trong danh sách các kết
quả đầu tiên. Từ truy vấn gốc và những kết quả đó, xây dựng một truy vấn mới gọi là truy
vấn quảng cáo - và tiến hành tìm kiếm trên tập quảng cáo đã có bằng truy vấn này. Cách
tiếp cận này cho phép khai thác những thông tin mở rộng thu được từ máy tìm kiếm nhằm
tạo ra những đặc trưng giàu thông tin hơn cho việc tìm kiếm. Hơn nữa, việc sử dụng
những đặc trưng mô tả toàn bộ quảng cáo tốt hơn so với việc chỉ sử dụng những từ khóa
riêng biệt của nó, điều này còn giúp cho người quảng cáo không phải xác định trước các
từ khóa của quảng cáo.
Truy vấn quảng cáo và các quảng cáo được họ biểu diễn thông quang 3 loại đặc
trưng chính: từ khóa, phân lớp và các cụm từ Prisma.
- Từ khóa: họ tập hợp tất cả các từ khóa riêng biệt có trong tập quảng cáo, lựa chọn
số từ khóa phù hợp, sử dụng mỗi từ khóa này như một đặc trưng sau đó tiến hành tính
trọng số cho các đặc trưng theo TF-IDF.
- Phân lớp: để tránh trường hợp một quảng cáo và một truy vấn có sự liên quan
lớn, nhưng chúng sử dụng các từ khác nhau để biểu diễn, ngoài các từ khóa, họ sử dụng
một đặc trưng ở mức cao hơn đó là phân lớp của truy vấn. Sử dụng một taxonomy lớn về
những chủ đề liên quan tới thương mại, xây dựng bộ phân lớp cho phép ánh xạ một đoạn
văn bản với một số lớp liên quan. Từ tập kết quả tìm được với truy vấn gốc, họ tiến hành
phân lớp với từng kết quả, sau đó chọn ra những lớp phù hợp nhất với truy vấn gốc. Các
lớp này sẽ được sử dụng như các đặc trưng của truy vấn quảng cáo, trọng số tại các đặc
trưng sẽ được xác định bằng độ tin cậy trả về từ bộ phân lớp.
- Cụm từ Prisma: sử dụng công cụ của Altavista’s Prisma, đây là một công cụ cho
phép trích chọn các cụm từ thường được sử dụng trên web, và một tập các cụm từ Prisma
cho tiếng anh gồm 10 triệu cụm từ, họ xác định các cụm từ Prisma xuất hiện trong tập kết
quả của truy vấn gốc, lựa chọn những cụm từ phù hợp nhất với truy vấn gốc và sử dụng
chúng như các đặc trưng cho truy vấn quảng cáo. Trọng số tại các đặc trưng được tính
theo TF-IDF.
19
Trong thực nghiệm Andrei Z.Broder và các cộng sự [11] thiết lập 4 hệ thống khác
nhau, với các tham số trộn giữa các loại đặc trưng là khác nhau trên mỗi hệ thống. Sử
dụng một tập 700 truy vấn, mỗi truy vấn được xây dựng như sau. Bắt đầu với tập tất cả
các truy vấn của Yahoo trong tuần từ 23-29, 2007. Chia 10 triệu truy vấn được tìm kiếm
nhiều nhất thành các nhóm theo tần suất tìm kiếm, lựa chọn ngẫu nhiên 50 truy vấn từ
mỗi nhóm. Ngoài ra, lấy ngẫu nhiên 200 truy vấn trong số những truy vấn còn lại (không
thuộc 10 triệu truy vấn nói trên). Với một truy vấn, tìm 3 quảng cáo đối với mỗi hệ thống
ở trên, tiến hành 9000 cặp truy vấn-quảng cáo như vậy. Một nhóm gồm 6 nhà phân tích,
tất cả đều có khả năng tốt về tiếng Anh, tiến hành đánh giá và phân chia mỗi kết quả vào
một trong các nhóm: Perfect, Certainly Attractive, Probably Attractive, Somewhat
Attractive, Probably Not Attractive, and Certainly Not Attractive. Để tính toán độ chính
xác và độ hồi tưởng, họ coi 4 nhóm đầu tiên là phù hợp, và hai nhóm cuối là không phù
hợp.
Kết quả thực nghiệm thu được được so sánh với mô hình không sử dụng truy vấn
mở rộng (chỉ sử dụng truy vấn ban đầu) và có độ chính xác vượt trội. Độ chính xác của
mô hình ở 4 hệ thống lần lượt là 35%, 40%, 42% và 45 % so với 16% của mô hình không
sử dụng việc mở rộng truy vấn. Hình 7 mô tả kiến trúc hệ thống của họ.
Hình 7. Kiến trúc hệ thống quảng cáo sử dụng phản hồi liên quan [11]
20
Mô hình quảng cáo sử dụng phản hồi liên quan của Andrei Z.Broder và các cộng sự
đã đưa ra được một phương pháp mở rộng câu truy vấn sử dụng các kết quả tìm kiếm. Họ
đã đề xuất một phương pháp xây dựng các đặc trưng dựa trên những tri thức mở rộng, mô
hình này giúp những người quảng cáo không nhất thiết phải định nghĩa rõ ràng những từ
khóa tương ứng với quảng cáo của họ.
2.5. Mô hình ước lượng CTR (Click Through Rate)
Dựa trên việc sử dụng CTR để xếp hạng các quảng cáo, Matthew Richardson và các
cộng sự [25] đã đưa ra một mô hình ước lượng CTR đối với những quảng cáo mới dựa
trên những thông tin đã có từ trước. Những quảng cáo với CTR cao sẽ được xếp hạng cao
hơn so với những quảng cáo có CTR thấp.
Matthew Richardson xem xét vấn đề ước lượng CTR với một tập các đặc trưng cho
trước như một bài toán hồi quy và sử dụng hồi quy logic (logistic regression) với đầu ra là
các xác suất tương ứng với các giá trị ước lượng nằm trong khoảng [0, 1]. Các đặc trưng
được sử dụng:
• Diện mạo quảng cáo: có bao nhiêu từ trong tiêu đề, trong nội dung, nội dung có
gồm nhiều kí hiệu, dấu câu hay không, sử dụng các từ ngắn hay dài….
• Mức độ thu hút: tiêu đề, nội dung quảng cáo có chứa những từ mô tả hành động
như “mua”, “tham gia”, “đăng ký” hay không…
• Danh tiếng: URL có kết thúc bởi .com, .net, .org… hay không, độ dài URL ra sao,
URL gồm nhiều đoạn hay ít đoạn, ví dụ: books.com sẽ tốt hơn so với
books.something.com. URL có chứa nhiều dấu sổ hay các con số hay không…
• Chất lượng trang web quảng cáo trỏ tới: liệu trang web có chứa flash hay không,
những phần nào được bao bởi ảnh, có sử dụng stylesheet hay không, có nhiều
quảng cáo trên trang web hay không.
• Độ phù hợp: liệ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
Các file đính kèm theo tài liệu này:
- Nguyen Huu Phuong_K50HTT_Khoa luan tot nghiep dai hoc.pdf