Categories
程式開發

Bandit算法在攜程推薦系統中的應用與實踐


導讀:攜程作為全球領先的 OTA 服務平台,為用戶提供諸多推薦服務。下面我們介紹幾個在實際推薦場景中面臨的問題:

  • 假設一個用戶對不同類別的內容感興趣程度不同,那麼推薦系統初次遇到這個用戶時,如何快速地知道他對每類內容的感興趣程度呢?
  • 假設我們有若干廣告庫存,如何知道給每個用戶展示哪個廣告能獲得最大的點擊收益?如果每次都推薦效果最好的廣告,那麼新廣告何時才有出頭之日呢?
  • 如果只推薦已知用戶感興趣的物品,會導致馬太效應。例如,在實際的場景中,部分優質物品由於初始推薦策略 ( 如熱門推薦策略等 ) 被推薦的次數變多,這導致用戶購買或點擊的次數較多,形成的用戶購買軌跡也較多。這種策略會導致頭部物品得到大量曝光,而中長尾物品的曝光次數很少。如何才能科學地為用戶推荐一些新鮮的物品來平衡系統的準確性和多樣性呢?

Bandit 算法源於賭博學,一個賭徒去搖老虎機,一個老虎機共有 n 個外表一模一樣的臂,每個臂的中獎概率為 Pi,他不知道每個臂中獎的概率分佈,那麼每次選擇哪個臂可以做到收益最大化呢?這就是多臂賭博機 ( Multi-armed Bandit,MAB ) 問題。

將 MAB 問題進行抽象,假設老虎機共有 n 個臂,每個臂的中獎概率為 Pi,用戶可以對每個臂進行嘗試,每次嘗試若成功則中獎概率為 1,若失敗則中獎概率為 0。用戶不知道每個臂的中獎概率,需要調整嘗試策略,最終找到中獎概率最大的臂。

Bandit 算法能較好地平衡探索和利用問題 ( E&E 問題 ),無須事先積累大量數據就能 較好地處理冷啟動問題,避免 根據直接收益/展現實現權重計算而產生的 馬太效應,避免多數長尾、新品資源沒有任何展示機會。利用 Bandit 算法設計的推薦算法可以較好地解決上述問題。

01 Context-free Bandit 算法

1. 置信上限 ( Upper Confifidence Bound,UCB )

Context-free Bandit 算法的思想在於採用一種樂觀的態度,根據每個臂預期回報的不確定性的上界值進行選擇,確定每次選出的臂。每個臂嘗試的次數越多,預期回報的置信區間越窄;每個臂嘗試的次數越少,預期回報的置信區間越寬。對於某個臂 ai,計算相應的預期回報分數,即:

Bandit算法在攜程推薦系統中的應用與實踐 1

其中第一項:

Bandit算法在攜程推薦系統中的應用與實踐 2

為第i 個臂到當前時刻t 的平均回報,稱為利用項( Exploitation Term );後一項為置信度,即對第一項的回報估計的確信程度,稱為探索項( Exploration Term ), rs 為在 s 時刻觀察到的收益,ni,t 為第 i 個臂到當前時刻 t 的選擇次數,n 為總選擇次數。平衡選擇已有較好表現的物品和具有潛在貢獻的物品。如果物品的置信區間很寬 ( 被選次數很少,且不確定 ),那麼它會傾向於被多次選擇,即探索,這是算法冒風險的部分。如果物品的置信區間很窄 ( 備選次數很多,且能確定其好壞 ),那麼均值大的傾向於被多次選擇,即利用,這是算法保守穩妥的部分。

2. 湯姆森取樣 ( Thompson Sampling )

湯姆森取樣是一種通過貝葉斯後驗採樣 ( Bayesian Posterior Sampling ) 進行探索與利用的方法。採用貝葉斯思想,對獎賞分佈的參數假設一個先驗分佈,根據觀測到的獎賞更新後驗分佈,根據後驗分佈選擇臂。

對於臂的獎賞服從伯努力分佈,中獎概率 ( 被點擊的概率 ) 即平均獎賞 θk∈[0,1]。假設第 k 個臂的獎賞分佈固定但未知,即參數 θk 未知。在 Bernoulli Bandit 問題中,採用 Beta 分佈對第 k 個臂的中獎概率建模,因為 Beta 分佈是二項分佈的共軛分佈。如果先驗分佈為 Beta(α,β),在觀測到伯努力二元選擇 ( Bernoulli Trial ) 後,後驗分佈變為 Beta(α+1,β) 或 Beta(α,β+1)。

  • 如果候選物品被選中的次數很多,那麼 Beta 分佈隨著 αkk 的增大會變得更加集中,即這個候選物品的收益已經確定,用它產生的隨機數基本在分佈的中心位置附近,且接近這個分佈的平均收益。
  • 如果一個候選物品的 α+β 很大,且 α/(α+β) 也很大,那麼該候選物品是一個好的候選項,其平均收益也很好。
  • 如果一個候選物品的α+β 很小,且分佈很寬,即沒有給予充分的探索次數,無法確定好壞,那麼這個較寬的分佈有可能得到一個較大的隨機數,在排序時被優先輸出,並用給予次數進行探索。

Bandit算法在攜程推薦系統中的應用與實踐 3

02 Contextual Bandit 算法

Context-free Bandit 算法沒有充分利用實時推薦的上下文特徵 ( 用戶偏好特徵、場景特徵等 ),在某一時刻對所有用戶展示的物品 ( 本文案例中指創意文案 ) 是相同的。事實上,針對同一個文案,不同的用戶在不同的情境下的接受程度是不同的。而 Contextual Bandit 算法充分利用了這些特徵。

每個臂包含特定的隨時間變化的上下文特徵 xt,並且其回報 rt 和上下文特徵 xt 直接相關,即存在一個函數 f,使得 rt=f(xt),其中 xt 為實際應用中抽像出的輔助選擇每個臂的特徵。根據不同的互聯網推薦系統場景可以產生不同的用戶特徵和物品特徵,不同的有關函數 f 的假設會得到不同的模型,選擇最大化期望回報策略:

Bandit算法在攜程推薦系統中的應用與實踐 4

其中 Ex,r 為期望。對應 Context-free 的 Thompson Sampling 算法,算法3給出一種相應的 contextual bandit 算法:Linear Thompson Sampling 算法。

Bandit算法在攜程推薦系統中的應用與實踐 5

Bandit算法在攜程推薦系統中的應用與實踐 6

03 場景應用

1. 文案創意選擇

傳統的 Test-rollout 策略分為 Testing Period 和 Post-testing Period,它在給定的測試週期內分配等量流量,挑選出指標表現最優的文案並切換全流量。但其存在下述缺陷。

  • 在初始階段,一部分用戶會收到質量較低 ( 表現為 CTR 較低 ) 的文案,這會損害用戶體驗的效果,也會影響用戶的參與度。
  • 文案的表現會隨著場景信息 ( 時間、地點等 ) 的變化而變化,在測試週期內得到的結論不一定適用於文案的整個生命週期。

編輯人工撰寫的文案的質量有一定保證,利用 E&E 算法進行探索時不會嚴重地影響用戶體驗而導致用戶流失。我們可以將文案模板優化建模為多臂 Bandit 問題,並引入 Batched Thompson Sampling ( 成批的湯姆森採樣 ) 優化用戶體驗。在傳統的 Thompson Sampling 中,只要接收到用戶反饋就會更新模型參數。在實際應用中,高頻的模型更新會給系統帶來嚴重的計算負擔,同時由於日誌系統存在延遲問題而無法確保收到實時的點擊、轉化等數據,因此更理想的情況是處理一定時間段內批量的用戶反饋。相關研究表明,Thompson Sampling 通過對反饋引入隨機性,對數據延遲反饋和批量數據反饋相比其他 Bandit 算法更加準確。例如,UCB 是一種確定性算法,雖然可以處理較短的延遲,但是當延遲增大時,模型性能會急劇下降。 Beta 分佈的採樣利用:

org.apache.commons.math3.distribution.BetaDistribution

包快速實現。系統整體處理流程如圖 1 所示。

Bandit算法在攜程推薦系統中的應用與實踐 7

圖 1 系統整體處理流程

2. 更新機制

Thompson Sampling 假設第 i 個臂擁有先驗 Beta(1,1),Beta(1,1) 是 (0,1) 的均勻分佈。採用 Batched Thompson Sampling,每個臂的 Beta 分佈只在每批次的結尾更新。

對於傳統的 Bernoulli Bandits 的 Thompson Sampling 算法,如果觀測到點擊行為,被選擇臂的 Beta(α,β) 更新為 Beta(α+1,β),否則更新為 Beta(α,β+1)。

對於 Batched Thompson Sampling,採用兩種更新機制:求和更新與歸一化更新。

對於第 t 個批次內第 k 個臂的 Beta 分佈為 Beta(αktkt);Skt 和 Fkt 分別表示第 t 個批次中第 k 個臂的點擊次數和非點擊次數;Mt 表示總的曝光次數,K 表示臂的總數。

求和更新公式如下:

αkt+1kt+Skt
βkt+1kt+Fkt

歸一化更新公式如下:

Bandit算法在攜程推薦系統中的應用與實踐 8

Mt/K 的參數更新策略可以解決在每個數據流批次內不同臂之間的不平衡流量的分配問題。如果第 k 個臂在每個批次內有較少的點擊次數,可能是由於 θk 較小,或者分配到該臂的流量不足以產生足夠的點擊次數,這會降低算法對於噪聲的容忍度。較小的 K 會放大潛在噪聲。實踐表明,數據噪聲 ( Data Noise ) 相較於不平衡流量分配的副作用,對算法表現有更大的影響。因此,我們採用求和更新公式。

Bandit算法在攜程推薦系統中的應用與實踐 9

Bandit算法在攜程推薦系統中的應用與實踐 10

3. 採集無偏的數據

在推薦系統中經常面臨的一個問題是用戶對根據某些策略推薦的一部分物品感興趣並做出反饋,但是還有更多的物品實際上沒有展示機會。在理想狀態下,我們希望用戶遍歷推薦系統準備的產品列表全集。

基於這些用戶交互數據,後續採用傳統的有監督模型訓練並上線個性化排序,實際上學習得到的排序函數是有偏的,會給推薦系統引入較大的偏置。如何盡可能地收集無偏的用戶交互數據呢?傳統的做法是從物料池中隨機均勻採樣並展示。但是這種做法會影響用戶體驗,降低用戶的參與度,導致需要更長的時間來收集充分的用戶行為反饋。我們引入一種用戶友好的無偏數據收集框架來改進傳統的 E&E 算法,用於解決該問題。

現有的 E&E 算法本質上不是為了消除偏差,而是最大化期望回報。一旦在探索中從未得到展示機會的物品對於某個指標 ( 如 CTR ) 的貢獻被充分地利用,E&E 算法就會收斂於產生最大回報的物品。

在標準的 K-armed Bernoulli Bandit 問題中,每一輪只有一個物品會被選擇。一種常見的做法是將 Item-wise Bernoulli Bandit 擴展為 List-wise Bernoulli Bandit,並將所有物品的排列視為一個臂。一種直觀的做法是:從每個臂的後驗分佈進行採樣,並以確定性的方式從中選擇 top N 的臂,如算法5所示。

Bandit算法在攜程推薦系統中的應用與實踐 11

相比於傳統的 bandit 算法在每一輪確定性地選擇最優的臂 ( 在這裡表示為一個排序的 top N 列表 ),改為由每個 item 的參數構成的多項分佈隨機選擇這個臂。

Bandit算法在攜程推薦系統中的應用與實踐 12

Bandit算法在攜程推薦系統中的應用與實踐 13

更改 E&E 算法使得高質量的內容和低質量的內容能夠相伴產生,並且高質量的內容排在前面的概率更高,使用戶體驗的損失可控。

4. 策略評估

Bandit 算法離線評估方法如下:

RA(T)=G*(T)-GA(T)

在探索過程中,由於選擇一些次優的臂,因此會增大短期的累積遺憾 ( Regret )。但是對於每個臂獎賞的評估,獲取臂的平均獎賞信息可以優化算法,從而減少長期 Regret。

隨著迭代輪次增大而減少 Regret,即確保 RA(T)/T 隨著 T 增大而逐步減小,數學表達式如下:

Bandit算法在攜程推薦系統中的應用與實踐 14

在理想情況下,我們進行分桶實驗,劃分一小部分線上真實流量評估各類 Bandit 算法,這對於 Bandit 算法的離線評估十分重要。用於離線評估的數據格式為:用戶信息、展示的物品、用戶對該物品的反饋 ( 點擊或不點擊 ),這些數據是由其他推薦策略收集到的日誌信息。當 Bandit 算法的推薦與離線數據為不同的物品時,則無法獲取用戶反饋。這種 “Partial-label” 的天然特性用來評估 Bandit 算法與有監督算法之間的主要區別。

  • 使用歷史日誌數據 D={(x,a,ra)},要求每個臂以 1/K 概率被選擇,滿足獨立同分佈。
  • 獎賞的反事實性:當 Bandit 算法推選的臂不等於日誌中的 a 時,則無法觀測到獎賞 rπ(x)

實踐中我們採用 Li 等人在 “Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms” 中提出的 replay 評估方法和後續 Nicol 等人的改進方法 “Improving offline evaluation of contextual bandit algorithms via bootstrapping techniques”。

Bandit算法在攜程推薦系統中的應用與實踐 15

Bandit算法在攜程推薦系統中的應用與實踐 16

Bandit算法在攜程推薦系統中的應用與實踐 17

Bandit算法在攜程推薦系統中的應用與實踐 18

Bandit算法在攜程推薦系統中的應用與實踐 19

Jittering Technique:數據集中的每條記錄在每個擴展數據 SB 中出現了 K 次。為了防止潛在的過擬合風險,在 context 特徵上引入一小部分高斯噪聲 ( Gaussian Noise ),這也是一種在神經網絡領域中常用的技巧。

5. 實踐經驗

① 先驗的選擇十分重要。 K 個臂未知的點擊概率 (θ12,···θk) 採用均勻的 Beta 分佈。但是事實上,某些 θ 值應該比其他值更大,採用均勻先驗會損害模型,並且均勻先驗沒有考慮情境信息及歷史經驗知識。對於新上架的文案,我們並不打算直接採用均勻的 Beta 分佈,而是尋找與其類似的文案 ( 利用文本和圖像的相關性 ) 對其賦予先驗知識。

② 參數 α 和 β 可調整,從而可以控制採樣樣本的方差。 items 的先驗知識可以方便地融入這些參數中。在 α 和 β 中引入參數 γ,使得參數分別變為 α/γ 和 β/γ,對後驗分佈稍做調整,這樣不會改變後驗均值,但是方差會乘係數 γ2 。當 γ 值小於 1 時,會減少探索的次數,從而獲得較低的回報。

③ 解決探索問題,勢必要冒險,勢必要走向未知,而這顯然會傷害用戶的體驗,如明知道用戶肯定喜歡 A,還偏偏給他推薦某個小概率非 A。因此,我們需要保證用於探索的候選池物品本身的質量,即使用戶不感興趣,也不至於引起用戶反感,避免用戶流失。

④ 在線計算時,是否需要實時採樣取決於推薦服務是否要求每次 request 都進行實時響應。 對於某些場景,用戶不希望看到的內容在短時間內劇烈變化。在這種情況下,我們可以每隔幾分鐘採樣一次,然後將參數保存,在線計算時採用查表法。

6. 優化點

① θk 不隨時間變化,即靜態環境。 Non-stationary Bandit 問題即 θk 變化較大會使在生命週期內 k 個臂的 θk 順序劇烈變化。

② 採用相比於點擊更加複雜的回報。 例如,考慮停留時長的點擊,將回報轉換為 [0,1] 內的實數,從而可以有效避免作弊點擊的問題。

以上內容選自攜程技術團隊新作《攜程人工智能實踐》

本文來自 DataFunTalk

原文鏈接

https://mp.weixin.qq.com/s?__biz=MzU1NTMyOTI4Mw==&mid=2247499139&idx=1&sn=c187e0108e9bd55b69e48d0c8de1887d&chksm=fbd74fefcca0c6f9290da7221b0d4b02a1d6a84913cf4950052b2050cd73e52b906d489f824e&scene=27#wechat_redirect