HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------
Đỗ Việt Phương
MÔ HÌNH KEYWORD-TOPIC CHO QUẢNG CÁO
DỰA TRÊN NGỮ CẢNH
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60.48.15
TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2013
Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: PGS.TS Từ Minh Phương
Phản biện 1: ……………………………………………………………………………
Phản biện 2: …………………………………………………………………………..
Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công
nghệ Bưu chính Viễn thông
Vào lúc:
....... giờ ....... ngày ....... tháng ....... .. năm ...............
Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông
1
MỤC LỤC
MỤC LỤC .................................................................................................................. 1
MỞ ĐẦU .................................................................................................................... 3
CHƢƠNG 1.
TỔNG QUAN VỀ QUẢNG CÁO TRỰC TUYẾN ........................ 5
1.1 Giới thiệu về các loại hình quảng cáo trực tuyến .............................................. 5
1.1.1 Tổng quan về quảng cáo trực tuyến ........................................................... 5
1.1.2
Tốc độ tăng trƣởng và thị phần .................................................................. 5
1.1.3
Các hình thức quảng cáo trực tuyến ........................................................... 5
1.1.4
Quảng cáo dựa trên ngữ cảnh ..................................................................... 6
1.2 Các phƣơng pháp tiếp cận đã triển khai ............................................................ 6
1.2.1 Mô hình trích xuất từ khóa trong nội dung trang Web ............................... 6
1.2.2
Mô hình so độ tƣơng đồng với tập từ vựng mở rộng ................................. 7
1.2.3
Mô hình tối ƣu xếp hạng với thuật toán di truyền ...................................... 7
1.2.4
Phƣơng pháp so sánh dựa trên ngữ nghĩa ................................................... 7
1.2.5
Chủ đề ẩn .................................................................................................... 8
CHƢƠNG 2.
MÔ HÌNH KEYWORD-TOPIC...................................................... 9
2.1 Phƣơng pháp cơ bản .......................................................................................... 9
2.1.1 Khái niệm và những thành phần chính ....................................................... 9
2.1.2
Phƣơng pháp cơ bản ................................................................................... 9
2.2 LDA (Latent Dirichlet Allocation) .................................................................. 11
2.2.1 Nguyên lý ................................................................................................. 11
2.2.2
Mô hình sinh cho tài liệu .......................................................................... 11
2.3 Mô hình từ khóa-chủ đề ( keyword-topic) ...................................................... 12
2.3.1 Mô hình dùng cho bài toán ....................................................................... 13
2.3.2
Sử dụng mô hình từ khóa-chủ đề.............................................................. 13
2.3.3
Biểu diễn quảng cáo và trang Web ........................................................... 16
2.3.4
Kết hợp các phƣơng pháp biểu diễn ......................................................... 17
CHƢƠNG 3.
KẾT QUẢ THỰC NGHIỆM ......................................................... 18
3.1 Tập dữ liệu và tiền xử lý ................................................................................. 18
3.1.1 Tập dữ liệu thực nghiệm ........................................................................... 18
3.1.2
Tiền xử lý dữ liệu ..................................................................................... 18
3.2 Cài đặt thử nghiệm .......................................................................................... 19
3.2.1 Công cụ sử dụng ....................................................................................... 19
2
3.2.2
Phƣơng pháp sử dụng để đánh giá ............................................................ 19
3.2.3
Các phƣơng pháp cài đặt để so sánh......................................................... 20
3.2.4
Kết quả thực nghiệm................................................................................. 21
3.2.5
Phân tích và đánh giá mô hình KT ........................................................... 22
TÀI LIỆU THAM KHẢO ........................................................................................ 26
3
MỞ ĐẦU
Mục tiêu của đề tài luận văn là nghiên cứu kỹ thuật hỗ trợ quảng cáo theo ngữ
cảnh – một dạng quảng cáo trực tuyến trên Web. Thông thƣờng, quảng cáo trên Web
đƣợc chia thành hai loại chính, đó là Quảng cáo tìm kiếm đƣợc tài trợ (Sponsored
Search) và Quảng cáo dựa trên ngữ cảnh (Contextual advertising). Hình thức quảng
cáo tìm kiếm đƣợc tài trợ hiển thị quảng cáo trên các trang kết quả đƣợc trả về bởi
công cụ tìm kiếm chẳng hạn nhƣ Google hay Yahoo. Trong trƣờng hợp này, các công
cụ tìm kiếm đóng vai trò nhƣ một đại lý phân phối quảng cáo. Ngƣợc lại, quảng cáo
dựa trên ngữ cảnh hay còn đƣợc gọi là Quảng cáo dựa trên nội dung đặt một lƣợng nhỏ
các quảng cáo lên các trang Web có nội dung mà ngƣời dùng đang xem. Lợi ích của
việc Quảng cáo dựa trên ngữ cảnh là hỗ trợ nhiều nhà xuất bản nội dung khác nhau
nhƣ một trang Web hay một blog so với hình thức Quảng cáo tìm kiếm đƣợc tài trợ.
Một hệ thống Quảng cáo ngữ cảnh điển hình bao gồm bốn bên tham gia, đó là
nhà xuất bản, nhà quảng cáo, hệ thống phân phối và ngƣời sử dụng. Nhà xuất bản là
chủ sở hữu các trang Web mà quảng cáo hiển thị. Các nhà quảng cáo cung cấp các nội
dung quảng cáo để quảng bá sản phẩm và dịch vụ của họ. Các mạng quảng cáo hoạt
động nhƣ một chiếc cầu nối giữa nhà quảng cáo và nhà xuất bản, nó lựa chọn các
quảng cáo tốt nhất để đặt vào trong nội dung của một trang Web. Ngƣời sử dụng là
ngƣời xem nội dung trên các trang Web. Quảng cáo đƣợc lựa chọn trên trang đích có
nội dung ít nhiều liên quan đến nội dung của trang Web. Khi một ngƣời sử dụng mở
một trang Web, họ có thể trông thấy các quảng cáo thông qua một đoạn văn bản mô tả
và một đƣờng liên kết. Khi ngƣời dùng nhấp chuột vào đƣờng liên kết này, nó sẽ đƣa
ngƣời dùng đến với trang đích quảng cáo. Mô hình định giá đƣợc sử dụng rộng rãi
ngày nay đó là mô hình PPC (Pay- per-click). Nhà tạo quảng cáo trả một số tiền nhất
định cho mỗi lần nhấp chuột vào liên kết quảng cáo, ngoài ra nhà tạo quảng cáo cũng
có thể lựa chọn các hình thức khác nhƣ PPI (Pay-per-Impression) hay PPA (Pay-peraction).
Đƣợc trình bày bởi các nghiên cứu trƣớc đây [6] về hành vi ngƣời dùng, để tăng
trải nghiệm ngƣời dùng cũng nhƣ tăng khả năng nhấp chuột vào một quảng cáo cần
lựa chọn hiển thị những quảng cáo có nội dung phù hợp với trang Web mà ngƣời dùng
đang xem. Bằng việc sử dụng các phƣơng pháp truyền thống, điều này có thể thực hiện
4
bằng việc tính toán độ liên quan giữa quảng cáo và nội dung trang Web. Do các quảng
cáo thƣờng sử dụng ngôn ngữ đặc biệt để gây ấn tƣợng cho ngƣời đọc, việc so sánh
nội dung các từ trong quảng cáo với các từ trong trang Web thƣờng không thể hiện
chính xác sự liên quan về nội dung. Trong nhiều trƣờng hợp, biểu diễn của một quảng
cáo có thể không chứa bất kì từ nào trong nội dung của một trang Web mặc dù hai văn
bản này có liên quan đến nhau. Vấn đề này đã từng đƣợc biết đến nhƣ là “rào cản về
từ vựng” trong nghiên cứu của Ribeiro-Neto et al.[14]. Một khó khăn khác đó là sự
hiện diện của từ đa nghĩa và đồng nghĩa làm giảm độ chính xác của quá trình so khớp.
Với thực tế và những vấn đề đƣợc trình bày ở trên, luận văn tiến hành nghiên
cứu và đề xuất mô hình tính toán và so khớp giữa nội dung quảng cáo và trang hiển thị
thông qua đề tài “Mô hình Keyword-Topic cho quảng cáo dựa trên ngữ cảnh” để
cải thiện chất lƣợng của bài toán so khớp quảng cáo với nội dung trang đối với ngôn
ngữ là Tiếng Việt trong thị trƣờng quảng cáo tại Việt Nam. Luận văn đã đề xuất việc
kết hợp các mô hình xử lý ngôn ngữ đã đƣợc công bố, với các biểu diễn đặc trƣng áp
dụng cho bài toán quảng cáo để cải thiện độ chính xác lên tới khoảng 90%. Kết quả
bƣớc đầu đạt đƣợc tƣơng đối khả quan, đã đƣợc ứng dụng thực tế tại công ty Vccorp,
và có khả năng phát triển thành một giải pháp tổng thể trong quảng cáo ngữ cảnh.
Kết quả nghiên cứu trong phạm vi luận văn đã đƣợc công bố tại Hội nghị quốc
tế SoICT 2012 [22].
Luận văn đƣợc chia thành các phần sau.
5
CHƢƠNG 1.
TỔNG QUAN VỀ QUẢNG CÁO TRỰC TUYẾN
Giới thiệu về các loại hình quảng cáo trực tuyến
1.1
1.1.1
Tổng quan về quảng cáo trực tuyến
Quảng cáo là hình thức tuyên truyền, giới thiệu hàng hoá, dịch vụ nhằm tạo sự
hấp dẫn và kích thích ngƣời mua để đẩy mạnh việc bán hàng cũng nhƣ thực hiện dịch
vụ. Các hình thức này có tác dụng tức thời, đập ngay vào mắt, tai ngƣời xem.
Quảng cáo trực tuyến là một loại hình quảng cáo được thể hiện trên Internet và
đặc biệt là các trang Web. Việc sử dụng Internet và World Wide Web ngày càng trở
nên phổ biến, do vậy Internet đã trở thành một trong những phƣơng tiện quảng cáo
quan trọng nhất ngày nay.
1.1.2
Tốc độ tăng trưởng và thị phần
a) Thị trƣờng quảng cáo quốc tế
b) Thị trƣờng quảng cáo tại Việt Nam
Việt Nam hiện giờ là một trong những quốc gia có tốc độ tăng trƣởng số lƣợng
ngƣời dùng đứng đầu thế giới. Theo số liệu của Tổng cục Thống kê tháng 7/2010, số
ngƣời sử dụng Internet tại thời điểm cuối tháng 7/2010 đạt 25,1 triệu ngƣời. Theo kế
hoạch quốc gia, Internet sẽ phủ đến khoảng 70% dân số đất nƣớc vào năm 2015, có
nghĩa là tại thời điểm đó số lƣợng ngƣời sử dụng Internet sẽ vào khoảng 40 triệu
ngƣời. Ngoài ra, Việt Nam có nhiều doanh nghiệp nhỏ và vừa, đối tƣợng phù hợp nhất
với quảng cáo trực tuyến.
1.1.3
Các hình thức quảng cáo trực tuyến
Quảng cáo trực tuyến rất đa dạng về hình thức cũng nhƣ loại hình. Nhƣng chủ
yếu đƣợc phân ra thành hai loại chính đó là “hợp pháp” thƣờng thông qua các mạng
quảng cáo và “không hợp pháp”. Hiện nay quảng cáo “hợp pháp” đƣợc chuộng hơn cả
bao gồm các hình thức quảng cáo theo số lần nhấp chuột (CPC) hay theo số lần hiển
thị (CPM). Và hiện nay, CPC vẫn đang sử dụng hình thứ quảng cáo theo ngữ cảnh để
tăng hiệu quả của quảng cáo.
6
1.1.4
Quảng cáo dựa trên ngữ cảnh
Hình 1.1 Kiến trúc tổng quan cho mô hình quảng cáo dựa trên ngữ cảnh
Khác với loại quảng cáo đƣợc tài trợ đƣợc đặt bên cạnh kết quả tìm kiếm liên
quan đến truy vấn của ngƣời dùng, thì các quảng cáo ngữ cảnh đƣợc hiển thị lên các
trang Web có nội dung liên quan với quảng cáo.
Nhiệm vụ chính của một hệ thống quảng cáo thông qua ngữ cảnh là quyết định
xem quảng cáo nào sẽ đƣợc hiển thị và thứ tự hiển thị của chúng theo mức độ phù hợp
với nội dung trang Web (ngữ cảnh). Do vậy, bài toán phù hợp nội dung hay còn gọi là
phù hợp về ngữ cảnh đã và đang đƣợc áp dụng rộng rãi trong quảng cáo trực tuyến.
1.2
1.2.1
Các phƣơng pháp tiếp cận đã triển khai
Mô hình trích xuất từ khóa trong nội dung trang Web
Đây là một mô hình của quảng cáo theo ngữ cảnh. Dựa trên tƣ tƣởng của quảng
cáo trên máy tìm kiếm, ta có thể coi trang Web hiện tại nhƣ một truy vấn dài bao gồm
nhiều từ khóa. Yih và các cộng sự [21] đã đề xuất mô hình học giám sát bằng cách
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).
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, hơn thế nữa, nhƣ đã đề cập từ trƣớc vấn đề giao
nhau giữa bộ từ vựng của quảng cáo và nội dung khá khác nhau. Ngoài ra, việc thực
hiện một “truy vấn dài” cũng gây lên hiện tƣợng thiếu chính xác do gặp phải nhiều từ
7
vựng gây nhiễu trong truy vấn do vậy kết quả của các phƣơng pháp áp dụng cũng
không đƣợc cao.
1.2.2
Mô hình so độ tương đồng với tập từ vựng mở rộng
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ủa các quảng cáo. Tập từ vựng của các trang Web thì đa dạng và phong
phú, trong khi đó, tập từ vựng của quảng cáo thì đặc thù đến một vài lĩnh vực cụ thể.
Ribeiro Neto và các cộng sự [14] đã 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.
Tuy nhiên, phƣơng pháp trên vẫn chƣa giải quyết đƣợc vấn đề ngữ nghĩa cụ
thể là từ “đồng nghĩa” và “đa nghĩa”. Không chỉ riêng ngôn ngữ nói, từ vựng trong
quảng cáo đều sử dụng nhiều từ khác nhau để cùng nói đến một vấn đề. Nếu chỉ dùng
riêng đặc trƣng về “từ khóa” sẽ dẫn đến vấn đề thiếu chính xác về ngữ nghĩa khi so
khớp các văn bản với nhau.
1.2.3
Mô hình tối ưu xếp hạng với thuật toán di truyền
Từ những nghiên cứu đã có đƣợc, Lacerda và các cộng sự [8] đã đƣ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. Tuy nhiên mô hình này vẫn sử dụng đặc
trƣng tƣơng tự nhƣ mô hình của Ribeiro [14], mặc dù đã cải thiện về thuật toán, nhƣng
cũng chƣa giải quyết đƣợc vấn đề về ngữ nghĩa do vậy kết quả về độ chính xác cũng
chƣa đƣợc cao.
1.2.4
Phương pháp so sánh dựa trên ngữ nghĩa
Phƣơng pháp dựa trên việc tách chọn các từ khóa còn gặp phải vấn đề đó là
“ngữ nghĩa”. Một quảng cáo về “sản phẩm dƣỡng da” sẽ không phù hợp đối với trang
Web có nội dung về “da giày xuất nhập khẩu”. Một phƣơng pháp do Andrei Broder
[4] đề xuất đó là việc so sánh độ phù hợp dựa trên cả 2 yếu tố ngữ nghĩa và cấu trúc.
Đối với yếu tố ngữ nghĩa, tác giả đã phân loại cả các trang Web lẫn dữ liệu
quảng cáo vào cùng một bộ phân loại lớn gồm 6000 nút. Mỗi một nút chứa một tập các
8
câu truy vấn. Mô hình huấn luyện sử dụng nhiều phƣơng pháp phân loại nhƣ SVN,
log-regression , K-means.
Đối với yếu tố cấu trúc, tác giả dùng chỉ số tf-idf để tính trọng số cho mỗi thuật
ngữ (term) của trang Web hay các quảng cáo. Phƣơng pháp này bổ sung thêm yếu tố
phân loại về độ liên quan, khi quảng cáo và nội dung trang Web nằm ở 2 node càng xa
nhau, độ liên quan càng giảm dần.
Phƣơng pháp của tác giả khá tốt khi đã giải quyết đƣợc hầu hết các vấn đề về
bài toán so khớp, nhƣng việc xây dựng 6000 nút nhƣ trong cách làm là không khả thi ở
Việt Nam khi mà tập dữ liệu của bài báo đƣợc thu thập từ một một công ty có dịch vụ
lớn nhƣ Yahoo. Ngoài ra, việc xây dựng hệ thống để lƣu trữ các nút và dữ liệu truy
vấn nhƣ vậy là khá tốn kém về công sức cũng nhƣ về tiền bạc và điều này đi ngƣợc lại
với mục đích ban đầu của luận văn.
1.2.5
Chủ đề ẩn
Tác giả Hieu X.P và cộng sự [13] sử dụng phƣơng pháp LDA để tự động phân
loại các chủ đề để giải quyết bài toán xếp hạng và so khớp. Phƣơng pháp này giải
quyết đƣợc vấn đề về ngữ nghĩa cũng nhƣ cấu trúc. Tác giả cũng đƣa ra phƣơng pháp
để giải quyết vấn đề về kho từ vựng bằng việc tạo một kho dữ liệu từ vựng đủ lớn để
bao phủ từ vựng của quảng cáo lẫn trang Web. Tác giả thu thập dữ liệu này từ trang
báo lớn là Vnexpress sau đó dùng dữ liệu làm tập huấn luyện cho mô hình LDA. Đối
với mỗi quảng cáo hay nội dung trang Web, thông qua mô hình này, đƣợc biểu diễn
dƣới dạng các vector đặc trƣng về chủ đề. Kết hợp vector đặc trƣng về chủ đề với
trọng số là xác suất của các chủ đề với biểu diễn “bag-of-words”. Sau đó, chúng để so
khớp với nhau.
Với cách làm này, tác giả đạt đƣợc độ chính xác khoảng 80% so với tập dữ liệu
thực nghiệm. Phƣơng pháp này có một điểm khá tƣơng đồng với phƣơng pháp đề xuất
của em trong đó sử dụng cả hai mô hình chủ đề. Sự khác biệt là cách thức chọn mô
hình và dữ liệu huấn luyện. Ngoài ra, phƣơng pháp này còn chƣa tận dụng hết các đặc
trƣng của quảng cáo tại Việt Nam nhƣ việc kết hợp các từ khóa/chuyên mục đƣợc gán
bởi ngƣời dùng cho từng quảng cáo.
9
CHƢƠNG 2. MÔ HÌNH KEYWORD-TOPIC
2.1
Phƣơng pháp cơ bản
Khái niệm và những thành phần chính
2.1.1
Cho một trang Web p và một tập gồm n quảng cáo A = {a1, …, an}, nhiệm vụ
là phải xếp hạng theo thứ tự giảm dần về độ tương đồng với nội dung của p. Sau đó
hệ thống sẽ lựa chọn một vài quảng cáo có độ xếp hạng cao nhất để hiện thị trên
trang quảng cáo.
Giả sử rằng, trang Web đƣợc biểu diễn chỉ bằng nội dung văn bản, ví dụ nhƣ là
các từ hay các ký tự. Với mỗi một quảng cáo, giả sử rằng, em lấy đƣợc những thông tin
về tiêu đề, mô tả và nội dung của trang đích mà quảng cáo điều hƣớng tới (landing
page) và những chuyên mục hay từ khóa mà ngƣời tạo quảng cáo gán cho nó. Một vài
hệ thống quảng cáo thƣờng định nghĩa trƣớc một tập các chuyên mục (thông thƣờng tổ
chức theo dạng cây). Khi một quảng cáo đƣợc tạo trong hệ thống quảng cáo này, ngƣời
tạo quảng cáo đƣợc yêu cầu mô tả rõ ràng một hoặc nhiều chuyên mục phù hợp với
nội dung quảng cáo mà họ chọn. Một vài hệ thống quảng cáo khác chỉ yêu cầu ngƣời
tạo quảng cáo mô tả những “từ khóa” để tóm tắt quảng cáo. Khi đó tên của một chuyên
mục có thể đƣợc hiểu một cách tƣơng tự nhƣ một “từ khóa”, trong phạm vi luận văn,
giả sử rằng em đều có đƣợc thông tin về từ khóa của quảng cáo đƣợc cung cấp bởi
ngƣời tạo quảng cáo. Xuyên suốt đồ án, em sử dụng “từ khóa” và “chuyên mục” thay
cho nhau.
2.1.2
Phương pháp cơ bản
Nhƣ những hệ thống thu thập thông tin khác, chúng ta có thể đánh giá độ tƣơng
đồng giữa một trang Web và một quảng cáo bằng việc biểu diễn chúng dƣới dạng các
vector thuộc tính, sau đó sử dụng các hàm tính điểm tƣơng đồng nhƣ khoảng cách
Euclidean, hay Cosine để tính toán những biểu diễn vector gần nhau nhất [15].
Mô hình không gian vector cơ bản nhất là mô hình “bag-of-words”, trong đó mỗi một
văn bản d đƣợc biểu diễn nhƣ là một vector Fbof trong không gian V-chiều với V là
kích thƣớc của bộ từ vựng:
Fbof (d ) (d1 , d 2 ,..., dV )
(2.1)
10
Mỗi một phần tử vector di chứa trọng số tƣơng ứng với từ, và trọng số đƣợc
tính toán dựa trên vị trí của những từ này trong một văn bản. Trong đồ án, em sử dụng
mô hình tf-idf [mô hình ir] để tính toán những trọng số này (khi tính toán biểu diễn
“bag-of-words” cho một quảng cáo, em gộp tiêu đề, mô tả và nội dung văn bản của
trang đích “landing page” nhƣ một dạng tập hợp của các từ). Chi tiết đƣợc mô tả nhƣ
sau.
Tính toán Tần suất khái niệm/ Tần suất nghịch đảo tài liệu thông qua công thức
Tần suất khái niệm (Term Frequency -TF):
tfi, j
ni, j
k nk , j
(2.2)
Trong đó: ni,j là tần suất xuất hiện của từ khóa ti trong tài liệu j
Tần suất đảo nghịch văn bản(Inverse Document Frequency -IDF):
idfi log
D
d : ti d
(2.3)
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ó:
(tf idf )i, j tfi, j idfi
(2.4)
Độ tƣơng tự giữa một trang p và một quảng cáo a đƣợc tính toán bằng công thức
Cosine giữa các vector đặc trƣng của chúng:
sim( p, a) cos(F ( p), F (a))
F ( p) F (a)
| F ( p) | | F (a) |
(2.5)
Ý tƣởng chính của mô hình “bag-of-words” coi tất cả các kí tự (token) của một
văn bản có vai trò tƣơng tự nhau. Tuy nhiên, trong một vài nghiên cứu trƣớc đây [14],
Ribeiro-Neto et al. chỉ ra rằng những phần tử của quảng cáo có độ quan trọng hơn khi
so sánh độ tƣơng đồng, do vậy những thành phần này cần đƣợc ƣu tiên hơn. Thông
thƣờng, ngoài những trƣờng hợp đặc biệt, hầu hết kết quả chính xác thu đƣợc trong mô
hình so khớp đều đạt đƣợc đƣợc do sử dụng những “từ khóa” quan trọng. Mô hình
này tập trung vào những “từ khóa” của quảng cáo với từ khóa xuất hiện trên nội dung
của một trang Web nhƣ là một “điều kiện bắt buộc” để quyết định xem một quảng cáo
có đƣợc coi là tƣơng tự đối với một trang Web hay không. Trong mô hình này, viết tắt
là AAK [15], độ tƣơng đồng giữa trang p và một quảng cáo a đƣợc tính toán nhƣ sau:
11
sim( p, a k )
AAK ( p, a)
0
if k p
,
otherwise
(2.6)
Trong đó k là tập các “từ khóa” của quảng cáo a. Trong phần tiếp theo, em sẽ giới
thiệu cơ sở và nền tảng của phƣơng pháp biểu diễn văn bản LDA, sau đó đƣa ra mô
hình đề xuất cho luận văn.
2.2
2.2.1
LDA (Latent Dirichlet Allocation)
Nguyên lý
Mô tả đặc tính của một tài liệu là một vấn đề tiêu chuẩn trong các bài toán về
thu thập thông tin, thống kê và xử lý ngôn ngữ tự nhiên, học máy. Biểu diễn nội dung
của một tài liệu có thể đƣợc dùng để tổ chức, phân loại hoặc tìm kiếm một tập các tài
liệu. Gần đây, mô hình sinh các tài liệu đã bắt đầu đƣợc dùng để khai phá các chủ đề
dựa trên các nội dung mà chúng đại diện, bằng việc mô hình hóa các tài liệu nhƣ một
hỗn hợp xác suất các chủ đề. (eg. Blei, Ng và Jodan 2003) [3]. Ở đây, Blei Ng và các
cộng sự đã sử dụng hƣớng tiếp cận này và đã giải quyết đƣợc các vấn đề về trích chọn,
tìm kiếm khi tập dữ liệu ngày càng lớn và gia 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 của các mô hình cũ. Tiếp theo em sẽ mô tả rõ hơn về mô hình LDA
2.2.2
Mô hình sinh cho tài liệu
LDA là một mô hình sinh cho dữ liệu văn bản hoặc dữ liệu rời rạc khác. Khi áp
dụng nó cho văn bản, ý tƣởng chính của nó là coi một tài liệu nhƣ là một phân phối
xác suất của các chủ đề ẩn, trong đó mỗi một chủ đề lại là một phân phối xác suất của
các từ. LDA giải thiết văn bản là một “bag-of-words” và không quan tâm đến thứ tự
các từ của chúng. Cho một tài liệu, nếu 2 phân phối trên đƣợc biết, chúng ta có thể sử
dụng quá trình sau để tạo ra một tài liệu mới. Đối với mỗi một từ, ta chọn ngẫu nhiên
một chủ đề trong phân phối chủ đề của tài liệu. Một khi chủ đề nào đƣợc chọn, chúng
ta chọn một từ thông qua phân phối từ của chủ đề.
Quá trình ngƣợc lại đƣợc thực hiện nhƣ sau: cho một tập hợp tài liệu, chúng ta
có thể tính toán 2 ma trận tham số chính của mô hình LDA, đó là ma trận phân phối tài
liệu- chủ đề và chủ đề-từ. Quá trình ngƣợc lại này có thể đƣợc coi là giai đoạn huấn
luyện. Trong quá trình trích chọn thông tin, phân phối chủ đề của một văn bản có thể
12
đƣợc sử dụng nhƣ một vector đặc trƣng mới để biểu diễn văn bản. Biểu diễn này có
chiều kích thƣớc nhỏ hơn nhiều so với mô hình “bag-of-words” truyền thống và cũng
mạnh mẽ hơn để biểu diễn việc đồng nghĩa hay đa nghĩa của một từ trong văn bản
[18].
Một cách đơn giản của việc áp dụng LDA đối với quảng cáo trực tuyến dựa trên
ngữ cảnh là việc sử dụng một tập hợp các trang Web và quảng cáo để huấn luyện mô
hình và sau đó sử dụng mô hình này để biểu diễn trang Web và quảng cáo theo phân
phối xác suất các chủ đề. Một cách tiếp cận tốt hơn là sử dụng một lƣợng lớn tài liệu
mở rộng làm đầu vào cho quá trình huấn luyện, do đó nâng cao độ che phủ của từ
vựng, xem chi tiết phƣơng pháp tại [13], tuy nhiên phƣơng pháp này đối xử với tất cả
các thành phần quảng cáo là nhƣ nhau, mà không thể hiện đƣợc tính đặc trƣng của mỗi
loại quảng cáo. Mở rộng phƣơng pháp trên, em sử dụng thêm một số thông tin đặc
trƣng của quảng cáo đó là các từ khóa (hay là chuyên mục) của quảng cáo đƣợc tạo bởi
ngƣời dùng. Bằng việc áp dụng mô hình tƣơng tự nhƣ mô hình chủ đề -tác giả [16],
qua thực nghiệm, em thấy đặc trƣng này giúp cải thiện rõ rệt kết quả hiển thị của
quảng cáo tƣơng đồng.
2.3
Mô hình từ khóa-chủ đề ( keyword-topic)
Em đặt tên mô hình này là mô hình từ khóa-chủ đề ( keyword-topic viết tắt là
KT), nó là sự kết hợp mỗi “từ khóa” hay “chuyên mục” với phân phối xác suất các
“chủ đề”, trong đó mỗi “chủ đề” là một phân phối xác suất thông qua các từ. Nếu một
quảng cáo chứa nhiều từ khóa, quảng cáo đƣợc biểu diễn nhƣ là một hỗn hợp xác suất
các chủ đề tƣơng ứng với các từ khóa. Ta có thể thấy rằng những chủ đề này cung cấp
một mức độ chi tiết hơn khi biểu diễn một tài liệu hơn là việc từ khóa hay chuyên mục
có thể làm đƣợc. Trong thực tế, một từ khóa thƣờng đƣợc kết hợp với một vài chủ đề
ẩn, chẳng hạn, từ khóa “máy ảnh” có thể đƣợc kết hợp với các chủ đề “nhiếp ảnh”,
“thiết bị số”, “thiết bị giám sát”. Bởi vậy, việc sử dụng từ khóa/ chuyên mục trong mô
hình chủ đề, chúng ta đã thêm một mức độ biểu diễn và cùng một lúc có thể phục hồi
chủ đề ẩn chỉnh xác hơn bởi những từ khóa đƣợc thiết lập bởi chính ngƣời tạo quảng
cáo.
Trong luận văn này, mô hình từ khóa-chủ đề đƣợc mô tả ở đây giống hệt với
mô hình chủ đề-tác giả (author-topic) đƣợc đề xuất bởi Grifith el al. [16], trong đó
13
thành phần từ khóa đƣợc thay thế bởi tác giả. Mô hình chủ đề-tác giả đƣợc giới thiệu
cho một mục đích hoàn toàn khác nhƣng trong luận văn này, nó đƣợc chỉ ra rằng có
thể thích hợp cho việc cài đặt quảng cáo dựa trên ngữ cảnh.
2.3.1
Mô hình dùng cho bài toán
Hệ thống sử dụng mô hình từ khóa-chủ đề bao gồm các bƣớc sau:
Thu thập một tập dữ liệu quảng cáo và sử dụng nó để huấn luyện mô hình từ
khóa-chủ đề (keyword-topic).
Ứng với mỗi nội dung trang Web hay quảng cáo mới, áp dụng mô hình đã đƣợc
huấn luyện trên để suy diễn ra phân phối xác suất chủ đề và từ khóa của chúng;
sử dụng các phân phối xác suất nhƣ một vector đặc trƣng đƣợc thêm vào để
biểu diễn trang Web/quảng cáo.
Kết hợp biểu diễn “bag-of-words” với biểu diễn chủ đề ẩn và từ khóa đƣợc suy
diễn ra từ bƣớc trƣớc và sau đó thực hiện bƣớc so sánh độ phù hợp giữa quảng
cáo và trang Web.
Tập quảng cáo
huấn luyện
Mô
Mô hình
hình huấn
huấn luyện
luyện
Keyword_Topic
Keyword_Topic
Trang web
Quảng cáo
Mô hình KT
Đặc trưng
Trang web
SUY DIỄN
CHỦ ĐỀ
So khớp
SUY DIỄN
TỪ KHÓA
Xếp hạng
quảng cáo
Đặc trưng
Quảng cáo
Hình 2.1 Mô hình tổng quan áp dụng phƣơng pháp từ khóa-chủ đề cho
quảng cáo dựa trên ngữ cảnh
2.3.2
Sử dụng mô hình từ khóa-chủ đề
Giả sử rằng, em có một tập lớn dữ liệu các quảng cáo, em gọi nó là tập dữ liệu
huấn luyện. Để thuận tiện hơn, ứng với mỗi quảng cáo em hợp nội dung của quảng cáo
bao gồm các thành phần sau : văn bản của trang đích quảng cáo điều hƣớng (landing
14
page) và mô tả quảng cáo thành một dạng gọi là văn bản quảng cáo. Quá trình sinh của
một tập văn bản đƣợc bắt đầu bởi việc lấy mẫu phân phối từ t một cách độc lập cho
mỗi chủ đề ẩn T từ một phân phối Dirichlet Dir(). Sau đó, đối với mỗi văn bản d với
một tập từ khóa kd đƣợc sinh ra nhƣ sau.
Với mỗi từ i trong tài liệu d:
o Lựa chọn ngẫu nhiên một từ khóa xi từ kd .
o Với mỗi từ khóa xi : lấy mẫu một phân phối thông qua các chủ đề từ
phân phối Dirichlet: xi ~ Dir()
Chọn một chủ đề ngẫu nhiên zi từ phân phối xác suất xi : zi ~ xi
Chọn một “từ” từ phân phối Dirichlet: wi ~ zi.
Em sử dụng mô hình kí hiệu đƣợc biểu diễn trong Hình 2.2. Các kí hiệu mờ và
rõ lần lƣợt tƣơng ứng với những biến quan sát đƣợc và không quan sát đƣợc, và khung
hình chữ nhật biểu diễn cho các vòng lặp lấy mẫu. Mỗi một xi, đƣợc chọn từ tập các từ
khóa, đƣợc kết hợp với một phân phối đa thức thông qua những chủ đề . Một từ đƣợc
lấy mẫu từ phân phối tƣơng ứng với chủ đề chịu trách nhiệm cho từ. Cả và
đƣợc vẽ từ phân phối Dirichlet với một siêu thông số lần lƣợt là và (trong một hệ
đối xứng, tất cả tham số đều có những giá trị nhƣ nhau, do vậy, cả và đều vô
hƣớng).
Keyword-Topic
kd
x
Z
β
W
T
Nd
D
Hình 2.2 Mô hình từ khóa-chủ đề.
Ƣớc lƣợng hai ma trận tham số và cho chúng ta thông tin về những chủ đề
nào thƣờng kết hợp với những từ khóa nào, hay thông tin bằng cách nào những văn
15
bản đƣợc biểu diễn bằng các thuật ngữ của những chủ đề này. Điều này cho phép so
sánh độ phù hợp biểu diễn chủ đề của những “từ khóa” thay vì so sánh bản thân các từ
khóa.
Thực tế nhận ra rằng, chúng ta không thể nội suy mô hình này một cách chính
xác mà thay vào đó là sử dụng mô hình xấp xỉ. Theo [17], trong luận văn này, em sử
dụng mô hình lấy mẫu Gibbs - một trƣờng hợp đặc biệt của mô hình chuỗi Markov
Monte Carlt - cho việc suy luận và ƣớc lƣợng tham số với mô hình KT. Tiếp theo, em
sẽ mô tả một cách ngắn ngọn thuật toán lấy lẫu Gibbs cho ngƣời đọc hiểu hơn về thuật
toán. Ngƣời đọc có thể xem lại tại mục 2.2.2 hoặc tham khảo thêm tại [17][16] để biết
thêm chi tiết.
Nhắc lại tham số z, em biểu diễn sự gán của những từ riêng lẻ tới những chủ đề.
Phƣơng pháp đầu tiên sử dụng lấy mẫu Gibbs để đánh giá z và sau đó sử dụng giá trị
của z để suy diễn ra và . Trong lấy mẫu Gibbs, các biến đƣợc lấy mẫu từ những
phân phối của chúng, có điều kiện trên tất cả các biến còn lại của mô hình. Trong
trƣờng hợp của em, phần tử của z đƣợc lấy mẫu lặp đi lặp lại từ phân phối của nó và
toàn cục trên mọi biến khác, và sự phụ thuộc trên và đƣợc tích hợp. Khi có hai tập
hợp các biến ẩn trong mô hình KT: z và k; thuật toán lấy mẫu cả cặp (zi, ki), điều kiện
trên tất cả các biến còn lại:
C KT
CWT
mj
kj
P( zi j, ki l | wi m, z i , k i , w i )
WT
WT
C ' V C ' T
m
j
m'
j ' kj
(2.8)
Ở đây zi = j, và ki = l lần lƣợt biểu diễn việc gán của từ thứ i của tài liệu tới chủ
đề j, và lần lƣợt từ khóa l; wi = m có nghĩa là từ thứ i có thứ tự là m trong từ điển; z-i,
k-i biểu diễn toàn bộ từ khóa và chủ đề gán bởi từ thứ i.
cho chủ đề j, bao gồm cả từ hiện thời. Tƣơng tự nhƣ vậy,
WT
C mj
C kjKT
là số lần từ m đƣợc gán
là số lần từ k đƣợc gán
cho chủ đề j, bao gồm từ hiện thời. V và T lần lƣợt là kích thƣớc tập từ vựng và chủ đề.
Một lần lấy mẫu của z đƣợc thực hiện, nó đƣợc dùng để đánh giá và nhƣ
dƣới đây.
CWT
mj
mj
WT
C ' V
m' m j
16
C KT
kj
kj
WT
C ' T
j ' kj
2.3.3
(2.9)
Biểu diễn quảng cáo và trang Web
Sau khi mô hình KT đƣợc huấn luyện, em sử dụng nó để suy diễn ra những chủ
đề và “từ khóa” của những văn bản mới (ở đây là những trang Web hay là quảng cáo).
Với mỗi tài liệu mới, thủ tục lấy mẫu Gibbs thực hiện chỉ với những từ trong tài liệu
mới. Quá trình bắt đầu bằng việc gán một cách ngẫu nhiên từ khóa và chủ đề tới các
“ký tự”. Sau đó chỉ lấy mẫu z và k mới cho những từ trong văn bản mới, sử dụng
phƣơng trình (2.8). Quá trình này thông thƣờng hội tụ rất nhanh (thông thƣờng sau
khoảng từ 10 đến 15 vòng lặp trong hầu hết quá trình tính toán) và sau đó kết quả z và
k đƣợc lƣu lại.
Chủ đề gán vector z cung cấp thông tin về những chủ đề nào đƣợc kết hợp với
một đoạn văn bản (quảng cáo hay nội dung trang Web), và do vậy cung cấp cho chúng
ta một cách biểu diễn văn bản theo các chủ đề. Với mỗi một văn bản mới d, em đếm số
lần một từ đƣợc gán cho mỗi chủ đề. Sau đó, em chuẩn hóa vector của việc gán theo
dạng phân bố xác suất và sử dụng nó nhƣ là biểu diễn dựa trên chủ đề Ft của tài liệu d:
Ft (d ) (t1 ,..., tT ),
(2.10)
Trong đó t1,…,tT lần lƣợt là tần suất gán các từ tới các chủ đề 1,…,T trong văn
bản d. Cũng giống nhƣ vậy, em đếm số lần một từ đƣợc gán cho một “từ khóa” trong
một văn bản d mới bằng việc sử dụng k và biểu diễn chúng dƣới dạng dựa trên từ khóa
Fk cho văn bản d:
Fk (d ) (k1 ,..., kT ),
(2.11)
Trong đó k1,…,kT lần lƣợt là tần suất gán của các từ tới “từ khóa” 1,…,K trong
văn bản d. Một điểm chú ý ở đây đó là với mỗi quảng cáo mới đều đƣợc gán “từ khóa”
bởi ngƣời tạo quảng cáo. Bằng việc bỏ qua những từ khóa gốc và sử dụng từ khóa
đƣợc suy diễn bởi mô hình KT, em nhận đƣợc những “từ khóa” mịn hơn biểu diễn
quảng cáo. Quá trình thực nghiệm chỉ ra rằng, trong hầu hết các trƣờng hợp, từ khóa
đƣợc gán bởi mô hình có một sự nhất quán với những từ khóa gán bởi ngƣời dùng và
cho kết quá hội tụ tốt hơn.
17
2.3.4
Kết hợp các phương pháp biểu diễn
Để tính toán độ tƣơng đồng giữa nội dung quảng cáo và các trang Web, em tính
toán cosine giữa các vector đặc trƣng của chúng, sử dụng tất cả 3 kiểu biểu diễn đƣợc
giới thiệu ở các phần trƣớc cụ thể là : “bag-of-words” tf-idf, biểu diễn “chủ đề” và
biểu diễn “từ khóa” bởi mô hình KT. Có một vài cách đề kết hợp các biểu diễn trong
việc tính toán điểm tƣơng đồng từ việc kết hợp các vector đặc trƣng lại với nhau [13]
tới việc học đa nhân phức tạp [2]. Trong luận văn này, em chỉ đơn giản kết hợp tuyến
tính cosine của 3 biểu diễn vector. Công thức cho Web page p và quảng cáo a, độ
tƣơng đồng simKT giữa p và a đƣợc tính toán thông qua công thức :
simKT ( p, a)
w1 cos( Fbow( p), Fbow(a)) w2 cos( Ft ( p), Ft (a)) w3 cos( Fk ( p), Fk (a))
,
w1 w2 w3
(2.12)
Trong đó w1, w2, và w3 là các trọng số điều chỉnh độ quan trọng của mỗi kiểu
biểu diễn trong việc tính toán độ tƣơng đồng. Trong thực nghiệm, em sử dụng các
trọng số ngang hàng nhau, việc điều chỉnh các trọng số để dành cho công việc sau này.
18
CHƢƠNG 3. KẾT QUẢ THỰC NGHIỆM
3.1 Tập dữ liệu và tiền xử lý
3.1.1 Tập dữ liệu thực nghiệm
Trong luận văn này, em sử dụng tập dữ liệu các trang Web và quảng cáo từ các
trang Web đến từ Việt Nam để làm tập dữ liệu đánh giá và kiểm thử. Đối với dữ liệu
Web, em sử dụng 100 bài báo từ http://dantri.com – một trong những tờ báo mạng nổi
tiếng hàng đầu Việt Nam. Số lƣợng 100 trang đủ nhỏ để có thể đánh giá đƣợc kết quả
thực nghiệm bằng con ngƣời, con số này cũng đã đƣợc sử dụng trong các nghiên cứu
trƣớc đây [4][13][14]. Các trang đƣợc lựa chọn đều trải rộng trong các lĩnh vực nhƣ
văn hóa, kinh doanh, điện tử, khoa học/ công nghệ. vvv. Để tạo bộ dữ liệu quảng cáo,
em thu thập 32.000 quảng cáo từ Admarket (http://admarket.admicro.vn) một công ty
quảng cáo trực tuyến tại Việt Nam. Từ dữ liệu đó, em lấy ra 30.000 quảng cáo cho
việc huấn luyện và 2000 quảng cáo cho việc đánh giá.
3.1.2 Tiền xử lý dữ liệu
Em áp dụng các thủ tục sau để tiền xử lý dữ liệu cho cả trang Web và quảng cáo
-
Trích xuất nội dung văn bản của trang, mô tả quảng cáo và trang đích của quảng
cáo sử dụng Jsoup (http://jsoup.org/).
-
Khôi phục dấu tiếng Việt và kiểm tra chính tả. Tiếng Việt là ngôn ngữ có dấu,
nhƣng một phần nhỏ dữ liệu đƣợc viết mà không có dấu. Do vậy em sử dụng
phần mềm VietMarker 1 để khôi phục lại dấu với mục đích để tăng độ chính xác
cho tính toán sau này. Ngoài ra, em còn sử dụng ViCheckSpelling2 để tìm và sửa
chính tả viết sai cho tiếng Việt.
-
Loại bỏ những “stopwords”, em sử dụng vnTokenizer 4.1.1c3. Những ký tự hay
từ xuất hiện ít hơn 5 lần trong tập văn bản cũng đƣợc loại bỏ.
1
http//www.4shared.com/file/155848296/3e0453c0/VietMarker.htm
2
http://sourceforge.net/projects/vicheckcode/
3
http://www.loria.fr/~lehong/tools/vnTokenizer.php
- Xem thêm -