騰訊廣告X中科院計算所WWW2021論文：在線廣告中的探索與優化

• 2021 年 5 月 19 日
• AI

01

​讓人頭疼的賭博機

未來的某一天，疫情終於結束了，大家都開開心心地出門旅遊。如果你是去澳門和拉斯維加斯的賭場，一定會看到這樣的成排的老虎機。

每台老虎機都可以投幣，按下按鈕或者拉一下拉杆之後屏幕上的幾列圖案就會滾動起來，如果停下來的時候剛好對齊了一列一樣的圖案，你就能贏走一小把硬幣。但每台老虎機也不完全一樣，除了機器的外觀、滾動的圖案不一樣，對齊圖案讓你贏錢的概率也不一樣大。

也許一個區域的十幾台老虎機里贏錢概率有高有低都不一樣，試過三四台以後我們就會遇到這樣的狀況：已經差不多知道前面這幾台里哪一台最容易贏錢了，但還沒試的里不知道有沒有更容易的，要是有，再找一陣子也值得；要是沒有更容易的，那我在已經找到的機子上玩就好，繼續試後面的反而浪費時間浪費幣了。

但很可惜，我們沒辦法知道後面的機子的情況，賭場的工作人員是無論如何都不會告訴你的。而越是我們時間不多、不想浪費錢，就越難抉擇要不要繼續試更多的機子。

02

推薦系統也受E&E 問題的困擾

剛才這樣的老虎機難題可以總結得更普遍一點：在「更多地進行嘗試、獲取更全面的信息之後再重新決策」和「利用當前已有的部分信息和經驗做決策」之間做平衡，探索帶來的好處是以後可能能做出更好的決策，壞處是需要犧牲當下的收益。這就是探索&利用 exploration & exploitation，E&E 問題。而且越是資源有限的時候，這樣的問題就越難解決。

E&E 問題在較為貼近實際的機器學習任務中出現的時候往往會更複雜。我們都知道如今各個網絡購物平台都有推薦算法，根據每個用戶的購買記錄、瀏覽記錄、搜索記錄推薦最有可能感興趣（最有可能購買）的商品給他。購物平台會不斷有新的商品加入，既有已有品類的新款式，比如新款的衣服、包包、手機，也可能連品類都是全新的，比如沖牙器、新風空調、掃地機械人、外賣料理包。新商品應該選用怎樣的推薦策略就是一個典型的E&E 問題，直接用現有的類似商品的推薦策略基本上不會銷量很差，但誰也沒法確定嘗試新的策略以後會不會更好、具體哪種新策略最好。平台都希望能有一些好的算法，在沿用已有策略（利用）和嘗試新的策略（探索）之間取得平衡，得到更高的總體收益。

學術界嘗試提出過一些方法體系化的方法來處理E&E 問題，一類方法是貝葉斯方法 ，相當於根據廣告推薦後的用戶反饋的結果猜測他可能本來喜歡的是什麼，逐步尋找根本因素、逐步優化推薦結果。貝葉斯方法的主要缺點是，只有推薦模型比較簡單的時候才能用明確的公式表示出推薦所需的後驗概率，在如今規模的數據量和模型規模下很難求解。而且，一些人類可以用邏輯判斷推理出的結論，通過算法來學習推斷可能非常困難，比如對於新風空調這個新品類，它和空調類似，我們人類可以用邏輯判斷出需要新風的人實際需要更好的空氣質量，購買人群可能和空氣凈化器比較接近；但想要通過算法完全從商品信息和歷史數據中得到這樣的結論、並且把符合程度量化就非常困難。即便用一些近似辦法求解，計算過程也代價高、速度慢，沒法用在在線廣告推薦中。

另一類方法是非貝葉斯方法，比如重採樣+集成，從全部的訓練數據（用戶行為數據）抽取出幾個有所不同的子集，在每個子集上分別訓練推薦模型，可以得到幾個各有不同的模型，對於同樣的新商品可以得出不同的策略；最後綜合使用這幾個模型，每次都隨機選用其中的一個推薦結果，可以達到一定的探索效果。但同貝葉斯方法相比，這種方法缺乏理論保證、缺乏引導性，每個分出來的模型仍然分別存在E&E 問題，也仍然無法改善從很少的數據開始的冷啟動問題。

03

用GuideBoot解決E&E 問題

今年，在線廣告推薦任務中的E&E 問題迎來了一種新的解決思路。騰訊廣告和中科院計算所合作的論文《GuideBoot: Guided Bootstrap for Deep Contextual Bandits in Online Advertising》創新型地提出了一種探索與利用算法GuideBoot，在廣告推薦場景下相比於主流算法取得了更好的探索與利用效果，並被WWW2021會議接收。

WWW（The International Conference of World Wide Web）會議是互聯網和數據挖掘交叉領域的頂級會議，有悠久歷史，在計算機科學的學術界和工業界中都有重大影響力，中國計算機學會（CCF）也把它評為A級會議。WWW2021、也是第30屆WWW會議即將於4月在線上召開，主會從4月19日到4月23日，會議在1736 篇投稿中共接收 357 篇論文，接受率僅為 20.6%。

和傳統的重採樣+集成方法類似，GuideBoot算法也會分出不同的數據、訓練多個不同的推薦模型，然後在需要輸出結果的時候從其中隨機選用一個。不同之處在於，GuideBoot增加了明確的引導性，會根據不確定性程度以一定的概率生成一小部分帶有隨機偽標籤的數據樣本，把它們也用於這些模型的訓練。

根據作者們的設計，隨機偽樣本可以有效地引導改善E&E 問題。隨機偽樣本的來源實際上是真實數據換了標籤，比如某用戶實際上買了某商品，但這裡變成沒買。在模型訓練過程中會持續計算模型對不同樣本的不確定性，這個不確定性越高，就會讓訓練數據中隨機偽樣本的比例越高，明確地引導模型有針對性地探索，多嘗試和之前不同的推薦策略；反過來，不確定性低時，模型很可能已經找到了一個不錯的推薦策略，就減小隨機樣本比例，鼓勵算法更多地利用好當前模型的預測。這種設計為不同的模型之間增加了更多的隨機性，從而可以引導進行有針對性的探索，可以降低模型對不充足數據的過擬合程度。

根據不確定性選擇訓練方向的這個設計和貝葉斯方法有不少的聯繫，都考慮到了不確定度對模型的影響。作者們也做了理論分析，表明這個設計是一種貝葉斯方法的近似，從理論角度說明了方法的可靠性。而實際的運行中，本來的貝葉斯方法即便在模型部署之後也需要在每次預測（廣告推薦）之後都計算不確定性，而且計算的開銷通常較大，GuideBoot算法只需要在訓練時執行這個操作，模型預測和在線決策時代價小、速度快，非常適用於高吞吐量、低延遲的廣告在線推薦場景。

可以說，GuideBoot兼具了兩種傳統方法的優點，而且還方便用於實際應用。

作者們進行了充分的實驗，用數據展現GuideBoot的優勢。首先為了驗證算法在理論上的正確性和效果，作者在經典的生成數據環境中進行了測試。生成數據上常用的評價指標是「平均遺憾值「，即算法做出的選擇和理論上最佳選擇之間收益期望的差距。總體的平均遺憾值越小說明算法做出的選擇越好。在生成數據的測試中，GuideBoot（圖中黑線）取得了最少的遺憾值，體現了算法高效的探索能力和對探索利用平衡的準確把握。

針對於廣告推薦場景，作者也在基於騰訊廣告真實業務場景下的數據進行了測試，評價指標為總體平均收益。GuideBoot（表格最後一行）在測試中取得了最高的平均收益，且重複實驗表明算法收益本身的波動較小，其效果能得到穩定的提升。

04

在線版本的GuideBoot

除了標準的訓練、測試流程之外，作者們還花了功夫對GuideBoot做了衍生改進。

在真實的在線廣告推薦中，數據是持續產生的，廣告推薦策略也是需要持續優化的。比如騰訊廣告的業務規模已經達到了每天都有百億級的曝光、億級的點擊轉化，廣告推薦系統最好能夠緊跟變化、持續地利用新增數據優化推薦策略。但這樣規模的數據是傳統的批處理式訓練解決不了的。

所以如果想要在真實業務中使用GuideBoot，就必須做一些改進，讓它更多地採取在線學習的訓練方式，以便對應百億級數據、秒級延遲持續產生的數據流。

針對在線學習改進的Online GuideBoot，主要區別在於把實時的數據流存成一包包的緩存，然後打亂、隨機分割，交給不同的模型學習。由於在訓練過程中，該改進版本不再能對所有的歷史數據進行採樣，而只能使用實時的數據流，在經典的生成數據環境下Online GuideBoot（圖中紅線）效果不如原版的 GuideBoot（圖中黑線），但其表現仍超過了其他主流的方法。

而在騰訊廣告數據的測試顯示，由於 online 版本能更好地緊跟在線環境的變化，在真實的在線數據中，online 版本能取得更好的效果，而且也同樣相比其他方法能獲得穩定的效果提升。

結束語

在論文《GuideBoot: Guided Bootstrap for Deep Contextual Bandits in Online Advertising》中，作者們提出了一種針對廣告推薦系統中的探索與利用問題的新方法，並且設計了適用於大規模在線學習下的衍生版算法實現，在經典生成數據環境和廣告推薦真實業務數據上測試都取得了穩定的提升效果。除了在線廣告推薦之外，GuideBoot算法也可以廣泛用於解決各種研究領域和行業應用中的探索-利用問題。

目前騰訊廣告正在熱招廣告策略算法高級工程師，歡迎點擊「閱讀原文」踴躍投遞簡歷

廣告策略算法高級工程師（深圳）

崗位職責：

參與以下一到多項工作：
1. 廣告競價排序機制的設計與優化， 包括但不限於粗選召回策略優化、精選排序公式和auction機制設計、排序全鏈路目標一致性等工作；
2. 設計適用於廣告業務線上場景，滿足高精度、高吞吐量、低延遲約束的大規模點擊率/轉化率粗選模型；
3. 廣告冷啟動機制設計；以及相關算法策略如模型冷啟動預估/Explore-Exploit算法設計等工作;
4. 設計可以幫助廣告主更好度過冷啟動的起量、拿量產品工具；
5. 以廣告系統全鏈路視角，解決廣告主在投放效果、體驗上的其他問題，比如穩定性、成本達成;建設排序問題分析系統，解決各種疑難雜症;

我們希望你：

1. 有紮實的編程功底，掌握算法/數據結構等基本知識，能熟練使用C/C++/Java/Python中至少一門語言，熟悉linux開發環境
2. 深入掌握兩種以上機器學習算法(包括但不限於邏輯回歸，FM, 決策樹，svm，最大熵，神經網絡)， 具備相應的數學功底；
3. 有強大的自驅力、有激情；能主動思考，解決問題；
4. 有良好的團隊合作意識；
5. 有強烈的業務導向意識，以業務目標引導技術優化；
6. 有推薦/廣告/搜索系統排序相關，點擊/轉化率模型預估，大規模機器學習系統等工作經驗優先

封面圖來自 rstudiogstock – //www.freepik.com