小米品牌廣告引擎與演算法實踐

本文整理自

12/2-3日在北京舉辦的ArchSummit全球架構師峰會上主題為「小米品牌廣告引擎與演算法實踐」的演講。

品牌廣告是小米商業化的重大戰略方向，在小米視頻、音樂、瀏覽器等多個媒體廣泛投放，廣告樣式也越來越多樣，開屏、視頻、信息流等。品牌廣告主對投放的需求也日益複雜和多樣化，精準定向、頻控、跨媒體投放、預算平滑等使得品牌廣告投放引擎和演算法面臨著諸多挑戰，包括流量預估、庫存分配和在線投放演算法等。本次分享重點介紹了小米品牌廣告引擎與演算法實踐，包括系統架構和各種離線和在線演算法。

小米大概是從2014年中開始廣告平台的研發，一開始主要是效果廣告，從去年開始大力發展品牌廣告。

什麼是品牌廣告？這個說法一般是相對效果廣告來說的。我們知道，效果廣告的目的是追求立即的轉化和效果，比如搜索廣告，手機上的應用分發等。而品牌廣告一般是為了品牌認知度，也就是brand awareness。當然品牌和效果的界限並不是這麼嚴格，廣告主很多時候也會追求品效合一。

目前，品牌廣告在小米手機和電視全系資源都有投放，包括小米瀏覽器、視頻、音樂、新聞資訊、天氣、日曆等系統app，還有小米電視和盒子等。廣告形式也是非常豐富，基本上主流的產品形態都支持，包括開屏、鎖屏、電視畫報、信息流、橫幅、貼片，甚至一些非標的廣告形態比如換膚等。從業務規模來說，小米一共有20多款日活過千萬的系統app，每天的廣告曝光已經接近百億，年收入規模也是達到了好幾十億。

品牌廣告從售賣方式來看，一般是CPT或者CPM，提前一段時間下單。另外，品牌廣告訂單是合約式的，需要保量，如果違約，比如沒有完成約定的投放量，一般都需要補量或者賠償。提前下單意味著需要進行流量預估，違約補償意味著分配演算法需要有明確的優化目標，這都是接下來想重點討論的話題。

品牌廣告的第二個重要特點是定向。定向是每個廣告平台必備的功能，各家平台在定向維度上有一些差別，但大體上的類別是相似的。比如用戶屬性的定向，包括人口屬性：年齡性別學歷，地域屬性，興趣屬性等。另外，時間定向，支持小時級的定向。設備定向，支持不同手機型號，電視盒子型號的定向。內容定向，主要是針對視頻/音樂等內容的分類，劇集，CP等，比如你可以定向投放綜藝、動漫、體育視頻，也可以定向投放某一部劇比如太陽的後裔等。人群包定向，包含或者排除指定的人群包。特殊定向，比如針對天氣狀況：下雨還是天晴、溫度、PM2.5的情況等等都可以進行定向。

頻控是品牌廣告另一個重要的特點，也是品牌庫存分配的核心技術挑戰，後面會詳細展開討論。目前我們系統支持按照小時/日/周/月級別的頻控。

最後一點，品牌廣告的投放一般都需要支持第三方監測，目前我們系統支持秒針/admaster/double click等主流的第三方監測。

整個系統架構包含三大塊，首先是廣告檢索，左上的部分。其次是廣告售賣，左下部分。最後是數據處理，右邊灰色的部分。

我們先來看廣告檢索系統，手機和電視的流量通過SSP接入我們的廣告平台，SSP是我們的流量方管理平台，負責流量的接入。MAX是小米的廣告交易系統AD EXCHANGE。MAX後面對接了很多個DSP，其中效果服務和品牌服務，是我們自己的DSP，分別對應我們的效果廣告和品牌廣告。除了我們自己的DSP，我們還對接了很多外部的DSP和廣告平台，包括騰訊廣點通、百度聯盟、京東、阿里、品友等。效果服務的內部實現，這裡沒有詳細講，主要包括廣告的檢索、過濾、CTR/CVR預估、排序等。而品牌服務和效果服務也有很多相似的地方，包括廣告檢索、過濾、定向、平滑等。但品牌服務和效果服務最大的不同是，品牌服務沒有CTR/CVR預估，對應的是在線投放模塊。這是品牌DSP非常核心的一塊。

我們再來看看廣告售賣系統，也就是我們的排期系統。排期系統提供了一整套的訂單管理和庫存分配的功能，包括定量、尋量、刪量、改量等。其中庫存分配又依賴於流量預估模塊。

最後一塊是數據處理，右邊灰色的部分，包括日誌服務、離線數據處理、實時數據處理等。離線數據處理的結果會用於流量預估，而實時數據處理則用於在線投放的實時反饋。

整個系統架構中和品牌廣告最相關也是最核心的部分，就是土黃色的這三塊：在線投放，庫存分配，流量預估。其中流量預估是基礎，在線投放和庫存分配都依賴於流量預估。

我們來看一個例子，廣告主打算購買12/25日這一天在小米視頻首頁焦點圖這個廣告位，北京男性用戶的流量。這個需求可以分解成三部分：日期/廣告位/定向條件。日期可以是一天，也可以是多天。如果想買一天內的流量，則是通過時間定向。定向條件：廣告主可以指定任意維度的定向。

這樣一個需求，背後有什麼技術挑戰呢？首先是定向預估，我們系統中支持的定向維度非常多，而廣告主一般會任意組合，所以組合維度更多。在組合維度爆炸的情況下想要精準預估每一個維度是件非常困難的事情。第二個挑戰是總量預估，流量一般隨時間和季節變化。比如小米視頻，一般來說周末的流量比工作日的流量高。還有寒暑假，雙11，米粉節，這些都是需要考慮的因素。

流量預估系統的衡量指標，最主要是看預估的準確性，我們一般是用rmse作為衡量指標，也會更進一步計算高估率和低估率等。

流量預估的系統架構分為離線和在線兩部分，主要的工作都是離線的部分，在線部分提供了數據的查詢介面。離線部分又可以分為三大塊，一塊是總量數據處理，一塊是定向數據處理，還有就是演算法評估。總量數據依賴於請求日誌，先進行數據求和，然後採用holt-winters演算法進行總量預估。定向數據也是依賴於請求日誌，取決於後續的預估演算法，定向數據的處理和存儲可能會略有差別。我們系統中實現了兩套獨立的預估演算法，下一頁PPT會詳細講。其中bitmap演算法需要對請求日誌進行採樣，結果以bitmap的形式直接放到內存中查詢。而正交演算法不需要做採樣，定向數據經過處理之後存儲到了mysql供查詢。最後，演算法評估模塊，主要就是RMSE，高估率，低估率等指標的計算。

我們系統中實現了兩套預估演算法，早期我們用的是比較簡單的正交演算法，後來引入了點陣圖演算法，同時也保留了正交演算法作為對比。

正交演算法的基本思想是，假定各維度之間是相互獨立，相互正交的。所以流量預估就轉化成了三個步驟，首先是總量預估，這一塊主要是用holt-winters演算法，根據過去90天的數據來預估未來的數據。Holt-winters是比較成熟的時間序列的預測演算法，我就不詳細展開講了。Holt-winters相對於移動平均演算法的優勢是可以很好的刻畫流量隨季節和時間的變化和趨勢。第二步是分別計算每一個維度的分佈，比如地域，我們算出來北京用戶佔5%，上海用戶佔3%。然後性別，男性用戶佔75%，女性用戶佔25%。最後就是正交求解，假定地域和性別這兩個維度是相互獨立相互正交的，那麼北京男性用戶的預估就是把兩個維度的分佈給乘起來。但是這個演算法的假定是不成立的，比如拿北京的用戶來說，可能男性用戶的比例比整個大盤要高，這樣對組合維度的預估就不夠精確。但是單維度的定向預估會比較準確。

第二種演算法是點陣圖演算法，基本思路是把請求日誌映射成點陣圖的形式。其中橫軸是請求，縱軸是定向維度，取值就是0或者1。比如第一個請求，刻畫的就是一個上海/男性/喜歡體育的用戶，而第二個請求則是一個北京/女性/也是喜歡體育的用戶。有了這個bitmap之後，如果想要查詢北京/男性的比例，就把北京和男性這兩行的數據進行按位與的操作。如果要查詢北京或者上海用戶的比例，則是把北京和上海兩行的數據進行按位或的操作。所以這個演算法的計算非常簡單，同時多維度的預估也非常精準，但是由於請求量很大，全部放到內存中不太現實，所以我們需要進行數據採樣。那採樣當然就可能引起預測的不夠精準。

下面我們來看一下對兩個演算法的一個對比和評估。首先，正交演算法的優點是：簡單，單維度的預估會比較準確。其實不要小看這個簡單的演算法，他可以解決大部分的預估問題，因為廣告主的訂單大部分還是單維度的定向。但是，正交演算法的缺點是：組合維度的預估不夠精確，這個比較好理解，因為正交演算法假定維度之間是獨立的，但實際情況是不可能完全獨立的。

點陣圖演算法的優點：計算簡單，只需要做簡單的位操作，按位與或。組合維度的預估會比較準確。缺點是內存佔用較大，必要的時候需要進行數據採樣。

最後我們來看一下兩種演算法的一個實驗數據，看這個圖，藍色是真實流量，黃色是正交演算法，灰色是點陣圖演算法。可以看到從總體趨勢來看，點陣圖演算法更貼近於真實流量，正交演算法的預估一開始偏高，後來又偏低。

我們先來看一個例子，首先是庫存情況，這個圖畫了5個格子，每個格子代表一個CPM的流量，按照地域和性別兩個定向維度來組織。從地域這個維度來看，北京有3個庫存，其中2個男性1個女性。上海有2個庫存，1個男性1個女性。然後我們系統中有兩個訂單，訂單1的定向條件是北京，2個CPM，訂單2的定向條件是女，也是2個CPM。我們一般把庫存叫做supply或者叫做供給，訂單叫做demand或者叫做需求。在這樣的供需情況下，如何進行庫存分配呢？

我們來看這裡給出了兩種分配方案，其中方案一把右上角綠色的兩個北京的庫存分配給了訂單1，其中1個男性1個女性。這樣的話訂單2就無法滿足了，因為整個庫存只剩下一個女性用戶的流量（黃色的格子）。好，那麼方案二呢，把左上角綠色的兩個北京男性的庫存分配給了訂單1，把右面兩個黃色的格子分配給了訂單2，這樣兩個訂單都能滿足。

這只是一個非常簡單的例子，實際情況中訂單量會非常大，每天上百個訂單是很普遍的情況。每個訂單的定向條件也比較多樣化，多個訂單之間會出現衝突和競爭搶量的情況。尤其是在一些熱門的節日，比如雙11，米粉節等，庫存的售賣率會非常高。在這種情況下，庫存分配是一件非常有挑戰的事情。

庫存分配的衡量指標，主要是庫存的利用率。在排期系統中，我們的目標肯定是讓儘可能多的訂單進來，這一點和後面要討論的在線投放的優化目標是不一致的。這也導致了離線分配和在線分配在實現細節上會略有不同。庫存分配從技術上還需要考慮的是分配演算法的求解速度，這會直接影響客戶下單的效率和用戶體驗。

庫存分配可以轉化為一個帶約束的最優化問題求解。還是拿上一頁的例子來講，根據供需情況可以構造出這麼一個二分圖，左邊的圓圈是流量節點，右邊的方框是訂單節點。如果流量和訂單之間是有關聯的，則通過邊進行連接，邊上面的數字xij代表第個流量節點對第個訂單的分配比例，也就是庫存分配演算法最終需要求解的目標值。

優化目標，這裡給出的了一個例子，這個公式我不會展開來講，大體意思，前半部分代表播放的平衡程度，後半部分代表缺量損失。整個優化目標就是最小化這兩個取值的和。

約束條件主要有三個，需求約束，這個公式的含義是說每個訂單的分配量不少於預定量。供給約束，這個公式的含義是指每個流量節點分配的流量不能超過自身能夠提供的量。非負約束指的是各個分配因子都需要>=0。

庫存分配的數學建模非常重要，是整個庫存分配演算法的核心，庫存分配的求解演算法反而不是最關鍵的，業界已經有比較成熟的兩種求解演算法, HWM和SHALE，由於牽涉比較複雜的數學公式的推導，我這裡就不展開來講了，感興趣的同學可以搜索相關的論文。

庫存分配的數學建模需要解決兩個核心問題：首先：如何構造二分圖，目標是使得二分圖的節點最小化，這樣問題的求解才能更快。其次：根據不同的業務場景需要制定不同的優化目標和約束條件，比如後面我們會講到，如果廣告主指定了頻控，那麼約束條件會有所不同。

首先是根據請求日誌進行流量預估，這一塊前面已經講過了，然後是根據訂單數據生成最小化定向條件，這一塊牽涉定向條件的合併。接下來根據流量預估和訂單數據生成二分圖，然後是分配演算法，最後的輸出是分配結果xij。接下來我們重點把紅色的這三塊展開來講。

這一步的目標是生成最小規模的流量節點，以簡化分配演算法。具體來講，我們需要為每個維度生成最小互斥的散列集合，然後再進行維度組合。

舉一個例子，假設我們系統中有三個訂單，訂單1的定向條件是北京上海深圳這三個城市，訂單2的定向條件是北京廣州深圳這三個城市，同時要求是女性用戶。訂單3的定向條件是女性用戶。這3個訂單牽涉了2個定向維度，地域和性別。首先，我們假定地域的取值就是北上廣深這四個城市，性別的取值就男和女。那麼，在地域維度，我們可以生成的最小互斥的散列集合就是這三個，北京和深圳在一起，上海單獨一個值，廣州也是單獨一個散列值。整個分拆和合併的過程一定要滿足最小和互斥這兩個條件。什麼是互斥，舉個例子，北京上海，和北京廣州，這兩個值就不是互斥的。同樣，在性別維度我們得到兩個散列值，男和女。

最後一步，生成候選節點，基本上就是把維度的散列值集合進行笛卡爾乘積，比如剛才這個例子，地域維度有3個散列值，性別維度有2個散列值，最後生成的候選節點就是3*2一個6個節點。

這個步驟相對比較簡單，遍歷每一個候選節點，檢查是否被某一個訂單節點包含。如果不被任何訂單包含，則丟棄。如果被某一個訂單包含，則通過一條邊來記錄流量和訂單之間的關聯。在上一頁PPT中，我們一共生成了6個候選節點，其中「廣州，男」這個節點是不被任何訂單包含的，所以最終生成的二分圖一共只有5個流量節點，3個訂單節點。

二分圖的密度是一個很重要的指標，計算方式是二分圖邊的總數除以流量節點和訂單節點的乘積，在這個例子中，一共有9條邊，所以二分圖的密度就是9/15=60%。二分圖的密度很大程度會影響庫存分配演算法的求解速度。

下面我們再來看一個建模的例子，用戶的興趣屬性。這也是用戶畫像非常重要的組成部分。但是用戶的興趣屬性和人口屬性有一個區別，人口屬性的取值是唯一的，比如性別只能是男或者女，但是興趣屬性的取值是不唯一的，一個人可能有多個興趣屬性，比如既喜歡體育又喜歡財經。對於興趣屬性，如何進行數學建模呢？我們來看一個例子。

假設系統中有兩個訂單，訂單1的定向條件是體育，訂單2的定向條件是財經。如果按照前面的建模方式，構造出來的二分圖如左下圖所示，兩個流量節點，分別是體育和財經。體育有4個CPM，財經有3個CPM，但是其實上面表格裡面一共只有5個CPM，中間省略的部分不計的話，多出來2個CPM，為啥呢？因為體育和財經這兩個維度不是正交的，有兩個用戶被重複分配到兩個流量節點了。

正確的建模方法是右邊這個，需要對興趣屬性的取值做一個排列組合，生成一個完整的組合列表，比如在這個例子中，體育和財經可以組合出三個節點：喜歡體育並且喜歡財經，喜歡體育不喜歡財經，不喜歡體育喜歡財經。這三個節點之間就是完全正交互斥的。這個時候再進行二分圖的構造就對了。

頻控是庫存分配的一個重要的議題，也是一個難題。頻控的分配和不帶頻控的分配，最大的區別在於流量節點的拆分。前面講的不帶頻控的分配，本質上是對PV的拆分。而帶頻控的分配，則需要對UV進行拆分。

來看一個例子，有兩個訂單，定向條件一樣，但是頻控不一樣。訂單1的頻控是1，訂單2的頻控是2。如果不考慮頻控，由於兩個訂單的定向條件一樣，只需要生成一個流量節點。如果考慮頻控，我們就需要按照頻控對同一個定向節點進行拆分。比如這個例子中，我們拆分成出了3個節點，節點旁邊標註了UV和PV，比如第一個節點UV=100，PV也是100，因為這個節點代表的就是每天只有一次訪問的用戶。同樣，第二個節點，UV=100，PV=200，代表每天有兩次訪問的用戶，依次類推。

同樣，對於約束條件來說，我們需要引入一個頻控約束，如右圖紅色所示的公式，這個約束的含義是什麼呢，意思就是說每個流量節點可以提供的量，不能超過廣告主限制的頻次乘以這個流量節點的UV。還是拿左邊的例子來說，對於第二個流量節點和第一個訂單，最多可分配的流量只有100PV，而不是200PV。為啥是100？因為流量節點的UV=100，訂單節點的頻控約束是1。 100*1=100PV。同樣對於第三個流量節點和第二個訂單，最大可分配的流量是200PV，而不是300PV。

前面講的都是問題的建模，核心就是構造二分圖，制定合適的優化目標和約束條件。那接下來就是問題的求解了。前面我大概提了一下，業界已經有比較成熟的求解演算法，比如HWM和SHALE，我們的離線分配演算法和HWM很類似（在線分配演算法是採用的SHALE），因為離線分配的優化目標是庫存的利用率，分配演算法依賴於訂單優先順序，採用啟髮式的演算法進行求解。我們在訂單的優先順序方面嘗試了多種不同的優先順序，比如傳統的按照訂單可用流量進行排序，或者按照訂單時間進行排序等。

這裡舉了一個例子，左邊是二分圖，我就不詳細講了，大家應該可以看懂。如果使用訂單的可用流量作為訂單的優先順序。訂單的可用流量等於訂單連接的所有流量節點的總和，那麼訂單1的可用流量=150，而訂單2的可用流量是100。訂單2的優先順序更高，優先進行分配，這種情況下訂單1就沒法得到滿足了。因為s1這個流量節點有一半的流量也就是25個CPM分給了訂單2，剩下的流量已經不夠訂單1要求的150個CPM了。如果我們訂單的時間作為優先順序，由於訂單1先到有限分配，這種情況下兩個訂單都能滿足。

剛剛我們講的庫存分配其實是離線分配，接下來我們再來看看在線分配。離線分配是為了下單用，在線分配則是為了完成訂單。離線分配的優化目標是庫存的利用率，讓儘可能多的訂單進來，在線分配的優化目標則是訂單的完成率和播放的平滑程度。

在線分配的核心技術挑戰是實時反饋，當實際流量和訂單完成率偏離預期時，如何快速修正。沒有實時反饋，再好的分配演算法也沒用，因為流量預估總是會有偏差的，演算法總是會有缺陷的。

實時反饋包括兩個方面：實時流量預估的修正，實時訂單完成率的反饋。技術實現上，主要是依賴我們的一個實時計算平台。通過實時反饋拿到最新的流量數據和訂單完成率數據，再通過小時級的模型訓練更新，不斷修正模型，最終提高訂單的完成率。

實時反饋主要是通過我們的實時計算平台，收集到實時的數據，反饋給線上的模型進行重新訓練。當然我們的實時計算平台不僅服務於在線分配，還有很多其他的廣告業務，比如實時報表統計等。

我們的實時計算平台分為4層，首先是數據接入層，接收來自客戶端上報的請求和曝光日誌。然後消息隊列我們用的是kafka，接下來的實時計算採用的是storm框架（最近也開始在嘗試用spark streaming），最後數據存儲用的是德魯伊（Druid）。這裡稍微提一下德魯伊，德魯伊是一個實時的多維數據分析工具，可以支持很多維度和很多指標的實時統計和分析，還可以進行互動式查詢，並且是低延遲高可用。

分流量實驗在效果廣告中使用的比較多，比如CTR/CVR預估等。品牌廣告的A/B實驗和效果廣告有一些相似，但也有一些不同。

首先，在線分配是按照「訂單_X_實驗」進行保量控制。比如我們想實驗兩個分配演算法，流量比例各50%，那麼每個演算法只需要完成預定量的一半即可。

另外，離線分配的演算法訓練可以在全流量進行，不需要分流量。這也比較好理解，流量節點和訂單節點的量如果按照同比例增加或者減少，對於模型的輸出是沒有影響的。

最後一點，品牌廣告的A/B實驗需要按天進行，所以無法動態調整流量。這一點確實是很大的局限，我們也沒找到更好的辦法。

這裡有一個截圖，對比了不同分配演算法一整天的完成率情況。可以看到，有的分配演算法出現了超投，有的分配演算法的平衡程度不夠好，最好的演算法應該是綠色這個。

最後簡單介紹一下我們的分析平台，先說一下背景，不管我們的流量預估演算法和庫存分配演算法做的有多好，我們總是會面臨各種各樣的問題，可能是系統問題，可能是演算法問題，可能是數據問題，但現象都是一個，訂單的預定量沒有完成。當出現這種問題的時候，我們如何快速定位問題的根源？這很關鍵，所以說分析平台很重要。

我們這個分析平台可以支持實時和歷史問題的排查。對於實時問題，一般是通過發送debug廣告請求，獲取到廣告投放每一個關鍵步驟的信息，可以很清晰的看到廣告最終是否返回，如果沒有，是在哪個步驟被幹掉了等等。

對於歷史問題，我們提供了分階段詳細的counting信息，比如這個截圖，我們可以看到這個廣告每個小時的分階段數據統計，總的請求，有多少次被平滑過濾，有多少次被在線分配演算法過濾等等。有了這些數據，我們至少可以很清楚的知道這是一個預估問題還是分配問題。

簡單總結一下，本次分享一開始介紹了小米品牌廣告的業務情況以及系統架構。接下來重點介紹了流量預估的系統架構和演算法實現，庫存分配的數學建模和問題求解，在線分配的實時反饋和分析平台等。時間有限，每一塊講的都不算太深入，感興趣的同學可以進一步交流。

宋強，10多年的資深老碼農，做過後端開發，玩過大數據，略懂機器學習演算法。目前在小米商業產品部負責廣告業務研發，包括小米自有流量和移動網盟業務的變現。之前在微軟STC從事搜索廣告、反作弊相關工作。再之前，在IBM從事資料庫和查詢優化相關的工作。

在大數據領域裡，區塊鏈能如何影響到你目前的軟體架構？