Click-through rate, Computational Advertising hay là bài toán cơ bản của ngành công nghiệp Internet

Quảng cáo có lịch sử rất lâu đời. Người ta tìm thấy những mẫu quảng cáo được dùng năm 1806 ở Nhật hay mẫu quảng cáo Coca-cola rất cầu kì từ những năm 1890. Tại Việt Nam ta cũng thấy những thông điệp quảng cáo kiểu như “Chồng tôi mê gái chỉ vì tôi không đọc tờ Tuần báo đàn bà” hay là “Hynos phosphate, đánh răng sớm chiều, răng vững bền nhiều” ngay từ những năm đầu thế kỉ 20.

Quảng cáo kem đánh răng

Ngày nay, quảng cáo trên internet ngày càng có nhiều ưu thế so với quảng cáo truyền thống. Nếu như quảng cáo truyền thống có chi phí cao mà đại lí nhận quảng cáo lại không nhiều (quảng cáo trên báo, tạp chí, pano ngoài trời…), không có khả năng định hướng khách hàng tiềm năng và rất khó để đo mức độ hiệu quả; thì quảng cáo trực tuyến (online advertising) lại lấp đầy hoàn toàn những khiếm khuyết này: khả năng tùy biến cao, đại lí quảng cáo vô kể (số lượng website trên Internet chắc nhiều hơn số tờ báo, tạp chí… hiện có) và rất dễ đánh giá định lượng mức độ hiệu quả.

Thực tế, quảng cáo trực tuyến là nguồn thu lớn, đôi khi là quan trọng nhất, của các công ty dịch vụ trực tuyến, tất nhiên trừ một số ít công ty sống được bằng cách thu tiền dịch vụ. Có thể nói quảng cáo trực tuyến là xương sống của cả ngành công nghiệp internet.

Vậy nhưng nghiên cứu khoa học trong lĩnh vực này thì lại rất non trẻ. Thời gian đầu quảng cáo trên internet cũng chỉ là những banner trên các forum, website… với hình ảnh bắt mắt hay thậm chí tìm cách “lừa gạt” người dùng. Cho mãi đến vài năm gần đây, khi nhu cầu quảng cáo tùy biến dựa vào “sở thích” người dùng tăng cao, thì khái niệm Computational Advertising mới bắt đầu xuất hiện và được chấp nhận rộng rãi.

Một trong những sự kiện đánh dấu sự ra đời của khái niệm “Computational Advertising” là một tutorial của Andrei Border tại ACM-SIGIR 2010, và sau đó xuất hiện trên ACM Communications. Andrei Border là phó chủ tịch bộ phận Computational Advertising của Yahoo! research. Cũng chính Andrei sau đó đã dạy 2 lớp Computational Advertising tại Stanford vào mùa thu 2010 và 2011.

Microsoft cũng không đứng ngoài cuộc. Đội ngũ quản lí Bing đã tổ chức một cuộc thi cải tiến thuật toán xếp hạng quảng cáo cho Bing trong nhiều năm liền, và thuật toán thắng giải cuộc thi này trong nhiều năm liên tiếp sau đó được trình bày trong một bài báo ở ICML 2010. Thực tế từ mùa hè năm 2009, thuật toán này đã chính thức thay thế công cụ xếp hạng quảng cáo cũ của Bing. Ta sẽ trở lại với chi tiết bài báo này trong phần sau.

Nói như vậy để thấy rằng Computational Advertising là lĩnh vực đóng góp tiền của rất nhiều cho các công ty dot com, nhưng vẫn còn rất mới mẻ.

Vậy tóm lại Computational Advertising là gì? (trong khi ta đã có quá nhiều thứ “computational”: Computational photography, Computational Linguistics, Computational Economics, Computational Finance… blah blah…)

1. Computational Advertising

Theo Andrei, thách thức chủ yếu của Computational Advertising là:

Find the “best match” between a given user in a given context and a suitable advertisement.

Cho trước một context, và một user đang xem context đó, tìm nội dung quảng cáo phù hợp nhất. Quảng cáo đó không những phải phù hợp với sở thích của user, mà còn phải tối đa hóa lợi nhuận cho nhà quảng cáo. Có thể xem đây là một bài toán tối ưu mà trong đó thuật toán phải chọn mẫu quảng cáo để hiện thị (trong tất cả các nội dung quảng cáo được đăng kí) sao cho đồng thời tối đa hóa mức độ phù hợp của quảng cáo với người dùng và ngữ cảnh (tối đa hóa khả năng mà user sẽ click vào quảng cáo), đồng thời tối đa hóa lợi nhuận cho nhà quảng cáo nếu user click vào những mẫu quảng cáo đã hiển thị.

Tùy vào  “context” mà ta sẽ có các dạng quảng cáo khác nhau. Nếu context là website hiển thị nội dung thì gọi là quảng cáo theo ngữ cảnh, trong đó nội dung quảng cáo thường được chọn sao cho liên quan nhất đến nội dung của website. Nếu context là tìm kiếm (Google Search, Bing Search…) thì phải chọn quảng cáo cho phù hợp với những gì user đang muốn tìm (ta gọi mĩ miều là Sponsored Search). Nếu context là mạng xã hội (Facebook…) thì thông thường các mối quan hệ của user sẽ được khai thác triệt để. Ngoài ra còn có quảng cáo trên các thiết bị di động, quảng cáo trong video như youtube v.v…

Trong bài này ta tạm thời chỉ quan tâm đến  Sponsored Search.

2. Keyword Auction: mô hình kiếm tiền của các công ty kinh doanh Sponsored Search

Trong thực tế, các công ty kinh doanh quảng cáo trên kết quả tìm kiếm  (Google, Bing, Yahoo Search…) hoạt động theo mô hình Generalized Second Prize Auction, được mô tả trong paper (có tên rất kêu) này. Đại khái như sau: với một sản phẩm hay dịch vụ nào đó, người đi quảng cáo (advertiser) xác định một tập các từ khóa mà user có thể dùng khi muốn tìm sản phẩm của họ. Với mỗi từ khóa, advertiser xác định một khoản đấu thầu  (bid) mà họ muốn trả cho mỗi click của user (đương nhiên là trả cho công ty quảng cáo). Nói chung đây là việc “mua từ khóa”. Khi user tìm kiếm, search engine sẽ tìm các từ khóa phù hợp với query của user, xác định các mẩu quảng cáo được hiển thị. Sau đó search engine còn phải tính toán để xếp hạng thứ tự xuất hiện của mỗi mẫu quảng cáo được chọn, đồng thời xác định số tiền mà họ nhận được nếu user click vào mỗi mẩu quảng cáo, tại vị trí đã chọn (số tiền này gọi là payment). Quá trình xếp hạng và tính payment phải tối đa hóa lợi nhuận cho search engine. Quá trình này được gọi là Generalized Second Prize Auction (GSP).

Giả sử mẩu quảng cáo i được đấu thầu với giá là b_i, và xác suất để user click vào mẩu quảng cáo i (gọi là click-through rate – CTR) nếu nó xuất hiện tại vị trí đầu tiên là p_i. Vị trí xuất hiện của các mẩu quảng cáo được xác định dựa vào  rank score p_ib_i, một cách nôm na là số tiền search engine nhận được từ mẩu quảng cáo i nếu nó xuất hiện ở vị trí đầu tiên. Trên thực tế rank score có thể được tính dựa vào một số tiêu chí khác như mức độ liên quan của link quảng cáo… Như vậy quảng cáo thứ i được chọn sao cho với mọi i thì p_ib_i \geq p_{i+1}b_{i+1}. Nhưng nếu chỉ thế này thì các công ti đi quảng cáo  (advertiser) sẽ cố tình thay đổi giá cho các từ khóa  (chẳng hạn đấu giá thấp cho các từ khóa có khả năng xuất hiện cao) nhằm tối thiểu chi phí quảng cáo, nghĩa là làm cho search engine thất thu. Để tránh hành vi này, giá trị payment c_i của mẩu quảng cáo i được tính dựa vào giá trị của mẩu quảng cáo i+1, nghĩa là c_i = b_{i+1}p_{i+1}/p_i.

Một điểm mà ta chưa giải thích trong mô hình làm ăn này là click-through rate (CTR) p_i. CTR được định nghĩa là số lần một mẩu quảng cáo được click chia cho số lần nó được hiển thị. Như vậy trong mô hình trên, giá trị CTR đóng vai trò cực kì quan trọng trong việc xác định vị trí và payment cho mỗi mẩu quảng cáo. Nó cũng ảnh hưởng lớn đến trải nghiệm của người dùng và số tiền mà search engine nhận được, nói cách khác là ảnh hưởng đến doanh thu của toàn ngành quảng cáo Sponsored search. Với mỗi mẩu quảng cáo, search engine phải tìm cách dự đoán được xác suất  CTR. Tuy nhiên việc dự đoán CTR là vô cùng khó khăn vì phụ thuộc rất nhiều yếu tố: “sở thích” của người dùng, mức độ liên quan của quảng cáo tới sở thích đó v.v… Những tiêu chí này được gom lại thành các đặc trưng dễ định lượng hơn như: cụm từ khóa được đấu thầu, nội dung quảng cáo, link của quảng cáo, lĩnh vực hoạt động của công ty đặt quảng cáo  (thông thường được phân nhóm theo nhiều cấp), cụm từ khóa tìm kiếm của user, vị trí địa lí của user, history, cache, thời gian v.v…

Tóm lại việc dự đoán chính xác CTR là nhiệm vụ trung tâm của các bộ máy sponsored search. Thực tế cuộc thi của  Bing mà ta đề cập ở trên chỉ là tìm cách dự đoán CTR một cách chính xác nhất.

3. Kết luận

Tóm lại:

  • computational advertising là “Find the “best match” between a given user in a given context and a suitable advertisement
  • Trong ngữ cảnh tìm kiếm  (Sponsored search), khi sử dụng GSP Auction thì giá trị CTR đóng vai trò then chốt.

Hi vọng trong bài sau ta có thể trình bày về thuật toán dự đoán  CTR của  Bing.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s