FreeWheel 基於 2000 萬訂閱家庭的電視廣告庫存預測
在本文中，作者將介紹 Freewheel 如何在面對 2000 萬用戶訂閱的條件下，利用機器學習技術爲客戶構建廣告投放方案，並在有效觸達的同時從整體上降低成本，提升廣告預算利用率。
寫在前面
在計算廣告領域，雖然互聯網數字廣告勢不可擋，但到目前爲止，傳統電視廣告仍與之分庭抗禮、不分伯仲。康卡斯特（Comcast）在全美範圍內爲 2000 萬訂閱家庭提供有線電視接入服務，併爲數以千、萬計廣告主提供廣告投放業務。傳統電視廣告投放相對刻板，在社區範圍內，同一時間同一頻道所有住戶觀看的都是同樣的廣告創意，這與互聯網數字廣告基於千人千面的個性化投放有着天壤之別。在電視廣告個性化投放方面，康卡斯特走在行業前列。基於 Freewheel 全局優化廣告投放引擎，康卡斯特旨在爲家庭用戶提供差別化的觀看體驗，爲廣告主提供更加精準的受衆定向服務，在有效觸達的同時從整體上降低成本，提升廣告預算利用率。
廣告投放全局優化的基礎，是穩健地預測未來一段時間，有多少當量的廣告庫存可供投放。基於現有的投放需求與未來的庫存情況，從全局上對供需進行分配，才能更好地指導投放引擎的執行策略。在這樣的業務背景下，我們基於 2000 萬訂閱家庭的投放歷史，構建機器學習模型，以小時爲粒度預測未來 90 天康卡斯特全網電視廣告庫存。
Freewheel 業務遍佈歐美，每天的電視廣告投放請求達到 10 億級規模。爲符合 MRC（Media Rating Council）與 GDPR（General Data Protection Regulations）數據安全相關標準，與用戶有關的數據只保留脫敏後的 ID 編號。同樣，爲符合相關法律法規，與地區、頻道相關的信息也只保留脫敏後的 ID 信息。雖然投放歷史數據量巨大，但是貧瘠的字段信息對於機器學習的模型構建來說無疑是個艱難的挑戰。
爲彌補屬性特徵的不足，我們從特徵生成和時序特徵兩個角度出發來豐富特徵向量，儘可能地讓模型挖掘、捕捉用戶的觀看模式和廣告庫存的分佈。在電視廣告場景中，廣告庫存主要取決於兩個方面，一方面是相對固定的電視臺節目安排，術語叫作 CBP（Commercial Break Pattern），也即一個時段中在哪些時間點提供多少廣告位；另一方面取決於用戶的觀看習慣，用戶的觀看習慣（在不同地區、不同頻道的觀看歷史）決定哪些廣告更容易曝光，哪些廣告還沒來得及曝光用戶就已經切換頻道。因此用戶的觀看歷史時序蘊含豐富的庫存分佈信息，這些信息對於模型的擬合來說至關重要。
時序特徵的引入需要我們採用時序預測模型來對樣本進行擬合。我們的業務目標是在不同維度組合上預測未來 90 天的廣告庫存，具體來說，模型應該有能力預測未來 90 天每個地區在所有頻道上每個小時的廣告庫存。康卡斯特在全美有大約 600 個地區，提供約 40 個頻道的接入服務。一種模型選型是我們爲所有這些維度組合（600 * 40）都提供一個獨立的時序預測模型。這種方法的優點是簡單、直接，模型比較純粹，只需要訓練時序特徵，因歷史數據量足夠大，不用擔心擬合問題。
同時模型受到的數據干擾較小，模型不會因爲不同維度組合之間數據分佈方差較大而傾向於平均化、折中化，只需負責擬合一份相對穩定的數據分佈即可。另外，每種組合訓練一個模型，當預測結果變動較大時，對於業務的可解釋性也更友好。然而這種方法的缺點也很明顯，前期工程開發與後期產品維度的成本都很高，因此我們需要一種可以同時考慮靜態屬性特徵和時序特徵的模型結構。
結合之前的工作經驗，同時受機器學習推薦場景的啓發，我們嘗試採用 Wide&Deep 的網絡結構來構建一個統一的模型來捕捉所有維度組合下的時序規律，在降低工程實現成本的同時，保證模型的整體性能。
特徵工程
我們首先以小時粒度把數據源按照維度組合進行聚合，統計每個維度組合上每個小時的廣告庫存。
模型的特徵向量主要由三部分構成，ID 類屬性特徵，生成特徵和時序特徵。屬性特徵和生成特徵交給 Wide 部分學習，時序特徵交由 Deep 部分擬合。屬性特徵如圖中的地區 ID、頻道 ID、電視臺 ID；生成特徵是指由“廣告曝光時間戳”衍生出的相關時間特徵，如小時、時段（美國將一天劃分爲多個不同的時段，如晚間黃金時段，早間新聞時段等）、周幾、是否週末。時序特徵是指不同維度組合過去 30 天的以小時爲粒度順序排序的庫存序列。預測標的則是未來 90 天以小時爲粒度順序排序的庫存序列。
需要指出的是，生產系統中保存的是廣告曝光數據，以 [地區 x 頻道 x 小時] 爲粒度對不同廣告位的曝光量進行彙總，並不能保證該劃分粒度在時間上能構成連續時間序列，也即 24 小時中，有些小時是缺失的。缺失的小時意味着在那段時間內，沒有廣告曝光，曝光量爲零。因此，我們需要做負樣本補齊工作（正負樣本比在 1：75 左右），從而在之前的劃分粒度上形成完整的時間序列。這意味着，我們需要根據 [地區 x 頻道 x 小時] 最細粒度的關聯鍵將正負樣本關聯。
因兩份樣本數據量巨大，我們採用分佈式計算引擎 Spark 進行數據處理。如果不採取任何優化措施，Spark 默認採用 Shuffle Join 來關聯正負樣本表，這會引入大量的網絡 IO 與磁盤 IO，需要 4 個小時才能完成數據的關聯。給定正樣本是負樣本的 1/75，很容易想到採用 Broadcast Join 來避免 Shuffle 過程，避免數據分發帶來的網絡開銷和磁盤開銷。但我們的正樣本數據量過大，廣播變量（2G）無法容納，一種辦法是強行修改廣播變量大小，讓其可容納全部正樣本，但是這種“強扭的瓜”會帶來新的問題。
Spark 採用點對點（Peer to peer）的方式實現廣播變量的分發，如果廣播變量過大，在分發的過程中網絡開銷會呈指數級增長，並不比 Shuffle 帶來的網絡開銷更小，因此強行修改廣播變量參數不可行。唯一可行的思路是把正樣本“變小”，讓它可以放進廣播變量。我們仔細觀察數據模式，發現大部分字段都是關聯鍵，只有庫存量是需要關聯在一起的字段。由此可見，正樣本中的大部分存儲空間都被關聯鍵佔據，但我們真正關心的是關聯表 Payload，也即我們場景中的庫存量。受 Hash Join 實現原理的啓發，我們將 7 個 Join keys 拼接在一起並計算其哈希值作爲新的 Join key，並將新的 Join key 與 Payload 拼接在一起形成新的樣本表，原始的 Join keys 在新的樣本表中被拋棄。
新樣本表與原樣本表相比，所需存儲空間降低一個數量級，足以放入廣播變量中。在負樣本表中對 Join keys 做同樣的操作，生成與新的正樣本表對應的 md5 哈希關聯鍵，用於與正樣本表關聯。與正樣本表不同的是，負樣本表需要保留原始的 Join keys，用於後續的特徵工程（索引化、向量化等）。值得注意的是，用 md5 哈希值替代原始的 7 個 Join keys，在數據量較大時，需要考慮可能的哈希衝突問題，不過我們在 10 億級樣本的場景下，經過多次試驗驗證，未發現哈希衝突的情況。將 Shuffle Join 轉化爲 Broadcast Join 之後，執行時間從 4 小時降低至 20 分鐘左右。
模型選型與調優
最終版模型網絡結構如上圖所示，左側 Wide 部分承載屬性特徵與生成特徵，Deep 部分的設計用來捕捉用戶觀看習慣。模型的演進經歷多次 Deep 部分的調整與改進。對於時序預測，通常想到的算法簇是 RNN/LSTM/GRU，因此在第一版模型的 Deep 部分，我們用 MLP 結合 LSTM 的方式來學習時序數據中的規律與特徵表示，最終與 Wide 部分拼接對未來 90 天庫存進行預測。對於模型效果，一方面採用 MAE、MSE 等機器學習指標來衡量，另一方面採用基於不同維度（如基於地區、基於頻道或基於時間）的統計 MAPE 等業務指標來衡量。
第一版模型效果與對比基準四周中位數相比稍好，但因數據量較大且 LSTM 串行計算，模型訓練時間過長，在 10 臺 ml.c5.4xlarge 配置的 AWS SageMaker 中，需要運行 2 天。在我們的場景中，時間步長爲 672（28 天 * 24 小時），過長的時間序列會增加梯度在 BPTT（Back Propagation Through Time）反向傳播中消失的概率，進而導致收斂速度變慢，進一步從整體上拖慢執行時間。
爲大幅降低模型訓練時間，在第二版模型中，我們採用“截斷序列”的方式進行改進，也即對於 672 步長的時間序列，我們只截取就近幾個（超參數）步長的序列作爲 LSTM 層輸入。經過多次對比試驗，我們發現截取 168（7 天 * 24 小時）個步長時，能夠在模型效果（平均 MAPE=30%）與訓練速度（10 小時）之間達到平衡。但這與我們的目標相差甚遠，我們期望平均 MAPE 能控制在 10% 左右。“截斷序列”雖然可以有效降低訓練時長，但同時也帶來嚴重的信息損失，這也是模型效果無法進一步提升的根本原因。
不過，第二版“截斷序列”的實驗給我們更多啓發，即在不考慮突發事件和大型節日的情況下，用戶觀看電視的習慣是相對穩定的。對於互聯網平臺上的視頻內容，用戶有主動權和選擇權；但在電視視頻中，用戶看到的節目內容都是事先編排好的，用戶對於視頻內容的消費是被動的。對於某個用戶來說，可選擇、感興趣的頻道與時段，很可能是相當有限的，因而觀看習慣相對穩定。
我們假設周與周之間的觀看模式是相對固定的，那麼就可以想辦法將 28 天的時間序列以周爲單位進行摺疊，從而在不損失信息的前提下將時間序列變短。參考行業中將 CNN（卷積神經網絡）應用到時序預測場景的案例，我們在第三版改進中加入一維空洞卷積，用於對時間序列進行轉換，將（672 步長，1 維）的時間序轉換爲（168 步長，4 維）時間序，再輸入到 LSTM 層。改進的初衷是在不損失時序信息的前提下，降低執行時間的同時提升模型效果。因爲訓練時間較長，較難通過描繪訓練損失與驗證損失之間的關係來判斷模型欠擬合或過擬合，我們採用早停法（Early Stopping）讓框架幫我們決定最佳的收斂位置，在多次試驗後，模型平均 MAPE 控制在 15% 左右。
第三版模型性能的提升驗證了我們的假設，即電視觀看行爲是相對穩定的。在這個假設成立的基礎上，我們可以引入梯度提升算法的思想來進一步優化模型。梯度提升算法的核心思想之一，是以步進、階段式的方式，通過擬合真值與上一個弱預測模型之間的殘差，來完成當前一輪迭代中預測模型的構建。既然我們已經驗證電視觀看行爲是相對穩定的，那麼我們是否可以嘗試預測實際觀看行爲與穩定模式之間的殘差，來改進模型的預測效果。基於這樣的構思，我們將 Wide&Deep 網絡調整爲上圖中的結構。注意網絡結構中最右側的分支，該分支主要負責捕捉平均的、穩定的電視觀看行爲。除最右側分支以外的其他網絡結構，沿用第三版模型的網絡設計。
模型在輸出之前，將第三版模型輸出與穩定的觀看行爲按元素相加，然後通過激活函數計算得到最終的預測序列。很顯然，在最終版模型中，我們嘗試構建 Wide&Deep 網絡結構來學習實際觀看行爲與穩定觀看模式之間的殘差，通過將殘差最小化來提升模型的預測性能。殘差是期望爲零的分佈、有正有負，RELU 激活函數會將負值歸零，這會導致負殘差的梯度爲零從而無法訓練，因此我們用 PRELU 替換 RELU，讓模型有能力將負方向的殘差也降到最低。對第四版模型多次試驗後，平均 MAPE 降低至 10% 左右，基本達到最初的預期。
隨着效果的提升，模型的複雜度也越來越高，相關超參數越來越多。如何合理有效地選擇超參，一直是算法同學需要攻克的問題。一般來說，我們基於對業務、數據和算法的理解，對每個超參給定一個搜索範圍，然後隨機生成幾種組合，針對對比基準，分別進行對比試驗，最終採用效果最好的超參組合來構建網絡。
比如對於學習率來說，通常在 1e-1 到 1e-5 範圍進行搜索。但通常我們需要調整的超參數量較多，而且超參的值域相差較大，如剛剛提的學習率、學習率衰減係數、優化器的選擇、激活函數的選擇、MLP 層數的選擇、神經元數量、卷積核個數、LSTM 神經元等等。僅憑藉算法同學隨機選取超參組合是不夠的，因此我們需要一些方法來輔助我們自動選擇可能帶來更高性能的超參組合。常見的方法有網格搜索和隨機搜索，但這些方法效率低下。當訓練時間較長，比如在我們的場景中，一次全量訓練需要至少 10 個小時，很難在較短的時間內找到效果更好的組合。網格搜索和隨機搜索更多地是提供一種工程上自動化的方法，免去算法同學每次隨機選擇超參後都需要重新啓動任務的麻煩。
從算法的角度看，網格與隨機搜索並不比算法同學更明智，這些方法把每一次嘗試都看作獨立事件，並不會利用已有經驗去尋找更優解。與之相對，Bayes 優化用機器學習算法來對每次嘗試（超參組合採樣點）進行擬合，通過後驗概率不斷調整先驗分佈
（基於高斯過程的 Bayes 優化），使用可以保證“探索”與“利用”平衡的採樣函數（Acquisition Function）來選擇下一次嘗試的超參組合，如此往復迭代。樣本越多，高斯過程越逼近真實分佈，採樣函數有更大的概率採樣到更好的超參組合。
我們採用基於高斯隨機過程的 Bayes 優化作爲對人選超參的補充，將人選超參作爲初始值，調用 Bayes 優化來訓練模型。不過在 12 輪迭代後，令人失望的是，Bayes 優化並沒有給出比人選超參更好的超參組合。因爲時間的原因我們沒有再增大迭代次數，雖然 Bayes 優化沒有給出更好的結果，但使用 Bayes 優化的初衷之一是增強我們對於人選超參的信心。換個角度來看，在我們的實驗中，Bayes 機選超參與人選超參還有一定差距，在 Auto Machine Learning（特徵工程自動化，模型選型自動化，超參調優自動化）蓬勃發展的當下，算法同學暫時還不會被 Auto Machine Learning 取代而失業，這倒不失爲一個好消息。
深度模型的優化難點在於，各個維度方向二階曲率的巨大差異，造成深度模型的成本函數空間異常複雜。在經典算法中，優化主要圍繞如何繞開局部極小點；而在深度模型中，優化圍繞在如何跳過“鞍點”、“盆地”，避免因不同維度方向二階曲率差異過大導致的在梯度下降過程中反覆震盪的問題，如此種種。一些一階優化算法，如帶動量加速的 Momentum，能夠很好地跳過“鞍點”；根據二階曲率對不同方向梯度下降學習率進行調整的算法如 RMSPROP，ADAM，能夠很好地解決反覆震盪的問題。但是對於成本函數空間中的“盆地”、“懸崖”等複雜“地形”，這些算法依然無能爲力。爲了讓模型的預測性能更穩定，我們引入 Polyak 平均（指數衰減平均）來計算最終的模型權重。通過早停法（Early Stopping）得到的權重，往往是圍繞某個局部極小點震盪多次之後的權重向量，很難完全收斂到梯度爲零的權重向量。Polyak 平均的思路簡單、直接，通過求取早停之前所有權重的指數衰減平均，來構建最終的深度模型。採用 Polyak 平均後，我們的深度模型能夠穩定地將平均 MAPE 維持在 10% 以下。
我們的預測標的是未來 90 天以小時爲粒度的庫存，如果採用 Tensorflow 默認的成本函數如 MSE，會對 2160 個小時（90 天 * 24 小時）的預測值、真實值作爲整體計算 MSE，這與我們的預期不符。我們需要模型將未來 90 天的每個小時區別對待，儘可能都預測的足夠準確。如果基於整體計算 MSE，在反向傳播過程中每個小時都乘以同一個誤差初始值，很顯然這是不科學的。每個小時的反向傳播，應該只依賴於該小時的預測誤差，爲此，我們設計基於 Element-wise 的 MSE，也即每次前饋計算的誤差也是一個 2160 維的向量，而不是基於整體計算 MSE 的單一值。
工程部署
Freewheel 現有業務都已雲化，我們的端到端部署均採用雲原生組件（S3，Presto，Databricks，Amazon SageMaker），如上圖所示。Presto 分佈式集羣用於從 S3 獲取數據源，得到 2000 萬訂閱家庭的觀看歷史並存儲於 S3。Spark 集羣用來進行數據處理、特徵工程以及樣本工程，最終生成可供 Wide&Deep 模型訓練、驗證的訓練樣本。SageMaker 是 AWS 在 2017 年 re:Invent 大會推出的雲原生分佈式模型訓練與服務平臺，支持多種主流機器學習框架如 Tensorflow、MxNet、PyTorch、Caffe 等。
Freewheel 採用 Keras/Tensorflow 進行開發，通過 SageMaker 分佈式集羣部署機器學習應用，完成模型的分佈式訓練與預測。每個分佈式組件都以 S3 數據的方式對上個組件構成依賴關係，爲方便維護分佈式任務之間的依賴關係以及更流暢的任務調度（啓動條件、執行狀態、重試機制等），整條 DAG（有向無環圖）工作流交由 Airflow 進行調度、維護和管理。工作流的輸出結果是存儲在 S3 的未來 90 天庫存預測，不同於傳統以模型爲接口的離線、線上耦合方式，在我們的場景中，離線訓練、預測以預測文件爲接口和下游服務進行對接。一方面是因爲下游服務以天爲粒度進行全局優化，實時性要求相對較低；另一方面以文件爲接口的方式大大降低系統的耦合度，使得下游系統在實現上更加靈活，如下游系統既可以直接訪問 S3 獲取預測結果，也可以將外部表與 S3 數據關聯，通過數據倉庫在前端 UI 對預測結果、趨勢進行展示，方便客戶查看。
用戶觀看電視的行爲模式相對穩定，因此我們不需要頻繁地全量訓練模型，但同時爲保證模型能夠捕捉最新的行爲變化，我們採用遷移學習的思路來迭代模型。即用全量數據完成一次模型初始化，隨後每天用新增數據對模型參數微調，保證模型性能的同時提升工程效率。與全量數據相比，每天新增數據大幅減少，增量訓練只需 10 分鐘即可完成。因此我們在 Airflow 中建立兩套 DAG，一套用於全量訓練，冷啓動模型，屬於一次性任務，爲模型性能打下基礎；另一套用於每天以新增數據更新模型權重，屬於定時任務，保證模型性能同時，大幅降低系統端到端執行時間。系統在部署之初，運行第一套 DAG，一旦完成，啓動第二套 DAG 每天定時執行增量訓練任務。
一些“失敗”的嘗試
在介紹數據源的時候提到，我們的數據模式比較貧瘠，比如頻道特徵，除 ID 本身沒有其他的屬性信息（如頻道的類別），良好的屬性特徵能夠幫助模型更好地區分不同頻道之間的差異。受推薦場景的啓發我們想到，用戶與頻道的交互關係（用戶傾向於觀看哪些頻道，厭惡哪些頻道），實際上和推薦領域中用戶與物品之間的關係如出一轍。基於矩陣分解的協同過濾算法被廣泛應用於搜索、排序、推薦等業務場景中，矩陣分解產生的隱式用戶矩陣和隱式物品矩陣，一方面可以用來直接計算相似度從而用於推薦，一方面隱式特徵向量本身可以作爲用戶或物品的 Embedding 特徵，用來擴充模型的特徵向量。
我們用 Spark 統計過去一個月用戶與頻道的交互歷史，並使用 Spark 內置的 ALS（最小交叉二乘協同過濾）算法計算隱式用戶矩陣和隱式頻道矩陣。將每個頻道的 Embedding 隱式向量作爲生成特徵輸入到 Deep&Wide 網絡結構之中，從而豐富特徵向量。但在多次試驗後，發現頻道 Embedding 隱式向量的引入，並沒有給模型性能帶來可觀的提升，反而加重了整體工程實現的複雜度和耦合度。因此在最終版模型中，我們並沒有納入頻道的隱式特性。但我們想要強調的是，機器學習領域中很多方法都是相通的，可以在不同的場景中互相借鑑。
在我們的案例中，Wide&Deep 與協同過濾均誕生於推薦領域，但這些方法在時序預測場景也能夠發揮重要作用。尤其是 Wide&Deep 思想，在大幅降低工程複雜度的同時，能夠保持模型良好的預測性能。反過來，時序預測場景中的流行算法如 RNN、LSTM、Attention 機制，同樣被大量應用於推薦領域、NLP 領域，甚至是計算機視覺領域。因此，算法同學應該有意識地學習、掌握不同場景下的經典算法與思想，從而在應對不同場景的業務需求時，能夠更加遊刃有餘。
作者簡介
吳磊，Freewheel 機器學習團隊負責人，負責計算廣告業務中機器學習應用的實踐、落地以及推廣。曾任職於 IBM、聯想研究院、新浪微博，具備豐富的數據庫、數據倉庫、大數據開發與調優經驗，主導基於海量數據的大規模機器學習框架的設計與實現。
