Machine Learning và Real-Time Bidding

Real-Time Bidding
Real-Time Bidding

Real-Time Bidding (RTB) tạm dịch là “Đấu gía thời gian thực”. RTB là việc mua bán lượt hiển thị quảng cáo online thông qua cơ chế thời gian thực xảy ra vào lúc trang web đang tải. Những cuộc đấu giá diễn ra dễ dàng hơn bởi ad exchange, demand-side platforms và supply-side platforms (SSP).

RTB khác với các mô hình quảng cáo truyền thống như thế nào? Tại sao chúng ta cần RTB? RTB mang lại lợi ích gì cho các trang mạng (publishers) và các nhà quảng cáo (advertisers)? Machine learning áp dụng vào các hệ thống RTB như thế nào? Qua bài viết này, tôi sẽ trả lời các câu hỏi trên cũng như trình bày những thách thức về Big Data trong RTB và tình hình nghiên cứu hiện nay của Machine Learning vào RTB.

So sánh Real-Time Bidding (RTB) và mô hình quảng cáo truyền thống

Trước khi bắt đầu, ta hãy xem qua đoạn clip mô phỏng một hệ thống RTB như bên dưới

Lấy ví dụ trang mạng tin tức Vnexpress, ngoài phần nội dung tin tức ra, Vnexpress dành ra khá nhiều vị trí trên trang web của họ cho các mục (slot/spot) quảng cáo. Tùy theo kích thước và vị trí hiển thị sẽ có mức gía tương ứng. Thông qua bảng gía và tìm năng của trang web này, các nhà quảng cáo hay marketing sẽ liên hệ với Vnexpress để được đặt quảng cáo vào các vị trí này.

vnexpress ads slot
vnexpress ads slot
vnexpress ads cost
vnexpress ads cost

Ta có thể thấy hai điểm hạn chế ở đây:

  1. Đối với advertisers
    • Giá đặt quảng cáo quá cao (từ 11-100 triệu/tuần).
    • Các advertiser khác phải đợi một tuần mới tới lượt mình được hiển thị.
    • Không nhắm đúng khách hàng mục tiêu, gây ra lãng phí thời gian lẫn tiền bạc. Ví dụ, người đọc tin tức chỉ quan tâm đến quần áo thể thao nhưng toàn đăng tin quảng cáo về du lịch, ăn uống không liên quan.
  2. Đối với publishers
    • Rủi ro nhiều vị trí quảng cáo bị bỏ trống và không được khai thác.
    • Doanh thu không được cải thiện do giới hạn về số lượng slot và thời gian.

RTB dựa trên nguyên lý cung và cầu thông qua hình thức đấu gía. Đấu giá là một quá trình mua và bán bằng cách đưa ra món hàng cần đấu giá, ra giá và sau đó bán món hàng cho người ra giá cao nhất với gía của người đưa ra cao thứ hai. Ví dụ, gía khởi điểm cho slot banner là 20,000VNĐ, các advertiser A, B, C lần lượt đấu gía tương ứng là 25,000VNĐ, 30,000VNĐ, 27,000VNĐ. Khi chốt gía bán, advertiser B thắng phiên đấu gía với chi phí là 27,000VNĐ (gía cao thứ hai).

RTB mang lại lợi ích gì cho advertiser và publisher?

Supply and Demand
Supply and Demand

Tại sao lại có mức gía rẻ như vậy? Lý do lúc này Vnexpress đã cung (supply) vượt nhu cầu (demand) của các advertiser. Gỉa sử Vnexpress có 10 slots quảng cáo. Với mô hình truyền thống, supply lúc này là 10, demand lúc này có thể là 10-100 advertiser, như vậy gía của mỗi slot sẽ rất cao.

Ngược lại khi sử dụng RTB, đối với mỗi user truy cập vào Vnexpress, ta sẽ có một phiên đấu gía. Gỉa sử có 1000 truy cập của các user khác nhau, ta sẽ có 1000 phiên đấu gía, tương ứng với việc Vnexpress đã supply 10×1000 = 10,000 slots chỉ trong 100ms (thời gian trung bình load xong một trang web). Điều này dẫn đến việc giảm gía của các slot xuống 1000 lần. Không những thế, các advertiser còn có nhiều lựa chọn từ các trang mạng khác ngoài Vnexpress khiến cho giá các slot ngày càng cạnh tranh hơn.

Trong khi đó, Vnexpress cũng giải quyết được rủi ro các slot quảng cáo bị bỏ trống (bán được nhiều slot hơn do số lượng phiên đấu giá bằng số lượng lượt view) cùng với doanh thu từ quảng cáo tăng lên do không còn bị giới hạn về số lượng và thời gian treo quảng cáo.

Các thành phần và thông số của một hệ thống RTB cơ bản

RTB components
RTB components

Display impression/ Ad inventory: lượt hiển thị các slot quảng cáo.

Demand-side platforms (DSPs): hệ thống bên mua, giúp các advertiser quản lý chiến dịch marketing và tối ưu hóa gía mua theo thời gian thực.

Supply-side platforms (SSPs): hệ thống bên bán, giúp các publisher quản lý các ad slot và tối ưu hóa gía bán khởi điểm theo thời gian thực.

Ad exchanges: tương tự như sàn giao dịch chứng khoán, thành phần này giúp quản lý và khớp lệnh giao dịch giữa DSP và SSP theo thời gian thực.

Ad networks: các kênh quảng cáo như Google, Facebook, Yahoo,… giúp cho các publisher có thêm kênh quảng cáo để bán slot quảng cáo được nhiều hơn.

Cost per impression (CPI): chi phí cho việc hiển thị quảng cáo ở mỗi nghìn lượt view. Được tính bởi tỉ số giữa chi phí quảng cáo so với số lượng view.

Cost \;per \;impression(\$) = \frac{Advertising \;cost(\$)}{Number \;of \;impressions(\#)}

Cost Per Click (CPC): chi phí cho mỗi lần user click chuột vào link quảng cáo của bạn, còn được gọi là Pay Per Click (PPC) trong các chiến dịch marketing.

Click-through rate (CTR): tỉ số giữa số lượng click vào link quảng cáo so với số lượng phiên đấu gía thành công, cho biết hiệu qủa của đấu gía đến khách hàng mục tiêu.

CTR = \frac{Clicks}{Impressions} \times 100

Cost per action (CPA): còn được gọi là Pay Per Action (PPA) hay chi phí cho mỗi lần link quảng cáo hướng được người dùng tới trang trả tiền cho sản phẩm được rao bán hay các hành động cụ thể như hiển thị thành công link quảng cáo, hành động click, submit một form đăng ký, …

Conversion rate (CVR): tỉ số này được tính khi một người viếng thăm trang web được chuyển đổi thành khách hàng mua sản phẩm được rao bán.

Conversion \;rate = \frac{Goal \;achievement(\#)}{Visitors}

Áp dụng Machine learning để dự đoán RTB như thế nào?

How RTB works
How RTB works

Trong Real Time Bidding (RTB), câu hỏi cơ bản của những nhà quảng cáo đó là “Nên đăng quảng cáo nào cho khách hàng nào?” và “Lợi ích mang lại của chiến dịch quảng cáo này có nhiều hơn chi phí bỏ ra hay không?” (nghĩa là doanh thu có lớn hơn chi phí hay không?). Dựa vào hai câu hỏi này, ta có thể tổng quát hóa thuật toán tối ưu hóa giá đấu cho mỗi phiên đấu giá tại DSP như sau (toàn bộ quá trình này diễn ra chưa đến 100ms):

  • Đầu vào: file logs truy cập của người dùng, thông tin về impression và các thao tác của người dùng, bộ lọc (nhắm vào các publisher cụ thể, các trang web mà người dùng đã ghé qua, nội dung cụ thể trên các website), ngân sách của chiến dịch, dữ liệu internal/external của user (GPS, đặc điểm người dùng, lịch sử lướt web). Ở đây, ta giả định rằng tập dữ liệu đầu vào là iPinYou (5.87GB).
  • Hệ thống ra quyết định: ta có thể thực nghiệm các thuật toán Machine Learning từ đơn giản đến phức tạp như Gradient boosting regression, Decision tree, Neural networks hay Deep learning để đưa ra mức giá đấu tối ưu. Hệ thống này phải đảm bảo làm việc hiệu quả trên Big Data (hơn 200,000 quyết định được đưa ra mỗi giây, mỗi user chứa hơn 200 thông số) để có thể đưa ra mỗi quyết định chỉ trong vòng 10ms.
  • Đầu ra: xác định xem nên bid hay không bid và mức giá đấu tối ưu là bao nhiêu (effective Cost Per Impression (eCPM)) một cách tự động.

Dự đoán Click Through Rate (CTR) dựa vào Machine Learning

Supervised classification
Machine learning là gì

Mục tiêu. Ở hướng tiếp cận này, ta sẽ giải quyết bài toán “Bid hay không bid” thông qua Click Through Rate (CTR). Ta sẽ huấn luyện mô hình Logistic Regression bằng cách sử dụng dữ liệu thắng cuộc của các phiên đấu giá.

Chỉ số CTR của một chiến dịch quảng cáo được định nghĩa bằng tỉ lệ giữa số lần click so với số lần quảng cáo được đăng/hiển thị, và được biểu diễn ở dạng phần trăm.

CTR = \frac{Clicks}{Impressions} \times 100

Real Time Bidding Dashboard
Real Time Bidding Dashboard

Trên thực tế, mặc dù bạn đấu giá thành công 70,000 phiên nhưng chỉ có khoàng 50 cú click từ khách hàng (CTR = 0.07%). Như vậy, làm sao xác định được có nên đấu giá hay không là một bài toán cần thiết giúp tiết kiệm thời gian và chi phí của mỗi chiến dịch.

Đánh giá mô hình.

Training data gồm các features của user, query và ads candidate được thu thập trong vòng 1-3 tháng. Ta sẽ gán nhãn dự đoán y = 1, y = 0. 1 có nghĩa là click, 0 có nghĩa là không click. Ta dùng phương pháp holdout để đánh giá mô hình. Độ đo sử dụng là Mean Cross Entropy (MXE) được dùng để tối ưu hóa thuật toán. Mục tiêu của ta là giảm thiểu hóa hàm lỗi để thu được mô hình dự đoán tối ưu.

y\log p + (1 - y)\log (1 - p)

Trong công thức trên, y \in \{0, 1\} là nhãn của mẫu huấn luyện. Logistic function (pCTR) p = \frac{1}{1 - e^{-t}}, t = \sum w_jx_j là tổ hợp tuyến tính của các features x cùng với các trọng số w.

Tổng kết.

  • Điểm mạnh: dễ hiểu và dễ cài đặt.
  • Điểm yếu: chỉ đảm bảo tối ưu hóa cục bộ (tồn tại nhiều điểm cực trị trong quá trình tìm tham số tối ưu).

Tình hình nghiên cứu

CTR estimation performance
CTR estimation performance

Bảng đánh giá trên lấy từ bài báo Deep Learning over Multi-field Categorical Data: A Case Study on User Response Prediction của Weinan Zhang, Tianming Du, Jun Wang. ECIR 2016.

  • LR: Logistic regression
  • FM: Factorisation Machine
  • FNN: Factorisation-machine supported Neural Network (Deep Learning)
  • SNN: Sampling-based Neural Network

Qua bảng đánh giá trên, ta có thể thấy phương pháp Deep Learning áp dụng trên tập dữ liệu này chỉ cải thiện một phần độ chính xác ở một vài trường hợp so với phương pháp gốc (baseline) Logistic regression.

Ngoài ra, bạn có thể tham khảo thêm các tài liệu nghiên cứu về RTB ở link sau https://github.com/wnzhang/rtb-papers.

 

One thought on “Machine Learning và Real-Time Bidding

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s