全栈工程师?
嗯.....目前并不是!

計算廣告中主要模塊、策略及其場景(上篇)

本文將會講述計算廣告(主要是DSP)中的主要模塊、用到的策略及其場景。筆者希望大家能和ta一樣,在了解廣告業務的同時,還能對策略的設計有一定了解,總結出一些通用的方法。


本文是我最近學習的一個總結,之前的文章多是和功能特別是廣告主界面有關,而本篇文章則是和策略有關。

本文分三個部分:

  1. 功能和策略,主講功能型產品和策略型產品的區別;
  2. 架構綜述,主講廣告系統的流程、模塊和技術架構;
  3. 算法和場景,主講各個模塊和場景中用到的算法。

一、功能和策略

先下個狹隘的定義,因為找不到比功能/策略更好的詞來描述,我在本文中把以UI/UE/人機視覺交互等主要交付物是具體產品形態的產品經理,狹隘的稱之為功能產品經理;把以策略/計算邏輯等等主要交付物不是具體產品形態的產品經理,狹隘的稱之為策略產品經理。

計算廣告中主要模塊、策略及其場景(上篇)

功能和策略不是非黑即白:

一定要注意:本文中的所謂功能和策略產品經理是狹隘的,只是為了方便大家理解和對比。

狹隘在於兩點:

  1. 對功能和策略的定義太狹隘,所謂視覺交互只是功能的一部分,所謂策略也不只是計算邏輯/算法等等,但為了便於理解就狹隘定義了;
  2. 對產品工作理解太狹隘,實際上策略和功能與活動、文案等都是滿足需求和解決問題。方案,產品工作中都會綜合運用各種手段去滿足需求,關鍵是滿足需求,而非或功能或策略的手段。

因為策略具有無直觀產品形態、達到某個目的、受多個因素影響、需根據因素變化隨時調整等特點,所以在發現問題-解決問題的產品經理基本工作流程,策略的實際內容與功能略有不同。

發現問題:

功能型面對的是場景相對聚焦的需求,重要的是抽象,把需求抽象成問題,把解決方案抽象成功能,抽象出來的多是實體或對象;策略型面對的是更多樣更小眾更有統計意義的需求,場景更豐富,抽象粒度比功能小,抽象出來的多是變量。

解決方案:

功能型產出的是收斂的解決方案,把需求調研和分析得到的結果收斂成較通用的方案,例如:微信的註冊登錄適用於每個用戶,每個用戶體驗到的交互也是一致的。

功能型產品通過路程、原型來表達產品實現效果;策略型產出的是發散的解決方案,把需求調研和分析得到的結果發散出多種場景和變量,例如:CTR預估中考慮來自廣告、用戶、場景等多方面的因素。策略型產品通過邏輯描述和效果示例表達產品實現效果。

開發跟進:

功能型在跟進開發中,更關注開發結果而非開發過程,過程頂多關心是否可實現和實現原理,面對開發結果是驗收的性質。

策略型在跟進開發中,更多參與過程,也可以說整個過程就是不斷評估測試效果再與RD一起發現各要素中的問題。當然,兩者都是要達到目標效果才能上線。

上線回歸:

功能型因為需求聚焦、方案收斂,能更快地達到理想態,關掉該feature的產品循環。而策略型很有可能會出現永無止境的產品循環,因為策略型需求簡單但場景複雜,而且受到很多因素影響,甚至人力都不一定能窮盡。策略要有較強的數據敏感度,擁抱不確定性。

總結一下:

功能型產品針對一個相對聚焦的需求,抽象出能夠滿足80%用戶的解決方案,而策略型產品針對一個受複雜因素影響的需求,策略需求比功能需求更長尾。

強調一點:在實際運用中,有時把功能和策略結合起來會用更好的效果,例如iPhone調節亮度中包含了手動調節功能和自動調節策略,不要自我設限,目標是解決問題,而不是用什麼方法。

二、架構綜述

1. 簡單架構

計算廣告中主要模塊、策略及其場景(上篇)

簡單架構

廣告系統主要解決一個問題:在給定展示場景、用戶的情況下,返回收益最大化的廣告。

上圖是一個最簡單的DSP廣告系統架構,1是收到一個廣告展示請求,8是發出針對此次請求的出價、廣告創意等。

其中,Router、排序模塊和檢索模塊是廣告系統的核心,特徵計算系統、計費系統和投放系統是用以輔助核心模塊的。

Router:對外提供HTTP服務,接收請求后,依次與特徵計算系統、檢索模塊、排序模塊交互,最後返回出價和廣告等,是樞紐。

檢索模塊:解決相關性問題,要檢索出與用戶相關性較高的廣告,相關性較低的會影響用戶體驗和廣告效果。檢索分兩步:首先是定向匹配,根據廣告主對廣告設定的定向條件,過濾出符合本次請求特點的廣告;然後是逐層召回,按多種定向策略或是相關性計算選擇與本次請求最相關的若干個廣告。

排序模塊:解決收益最大化問題,約束下最大化DSP利潤。排序也可分兩步——粗排和精排,粗排用到的特徵比精排少。由於檢索出來的候選廣告集較大,精排涉及到CTR預估和出價較複雜,通過粗排可做到快速擴率,選出前若干個進入精排,以節省計算時間和成本。

特徵計算系統:實時計算曝光場景(媒體、廣告位、上下文、設備等)、用戶的特徵,並向其他模塊提供實時查詢功能。

計費系統:實時處理曝光后媒體返回過來的曝光數據,以及其他點擊、轉化等數據,並計算廣告費用、剩餘預算等,也要包含反作弊。

投放系統:供廣告主使用,給廣告設置定向條件、創意等,是廣告主直接操作的界面。

2. 複雜架構

計算廣告中主要模塊、策略及其場景(上篇)

複雜架構

複雜架構相對於簡單架構而言,把系統中涉及到的具體模塊,都展示出來,並且區分了離線和在線。組成部分包括:分佈式計算平台、廣告投放機、流計算平台、數據高速公路。

其中,分佈式計算平台是離線數據,流計算平台是實時數據。分佈式計算平台會把輸出的行為定向、算法模型等通過海量內存管理系統(例如:Redis)暫存在內存中,方便在競價過程中快速調用,以滿足DSP在30ms內完成出價,整個競價過程在100ms以內。

分佈式計算平台:採用分佈式技術(例如:Hadoop),它輸出的數據、算法模型一方面提供給廣告投放機進行出價決策,另一方面提供給ETL,以數據倉庫為基礎向產品運營等人提供數據報表的支持,以便於商業決策。

廣告投放機:就是簡單架構中的router、檢索模塊和排序模塊,是DSP收到請求和返回出價廣告等的主邏輯,此處還包含了收益管理模塊。廣告排序得到的結果是局部最優,收益管理則是用分佈式計算平台中計算好的分配規劃來生成分配方案,以達到全局最優。

流計算平台:

是對實時數據(短時間內發生的用戶日誌和廣告日誌等數據)的處理,包括:反作弊、實時點擊反饋、計費、實時受眾定向。

  • 反作弊:是根據實時用戶行為識別作弊流量,並不納入計費;
  • 實時點擊反饋:會生成實時點擊率特徵,和離線特徵一起參與到基於CTR模型的廣告排序中;
  • 實時受眾定向:會把實時數據加工成實時用戶標籤,用以廣告檢索;
  • 計費:是實時計算廣告費用,把預算即將耗盡的廣告及時告知給實時索引以下線此廣告。

實時數據對廣告檢索、排序等效果提升很明顯,例如:前幾分鐘給用戶推了此廣告,而用戶有負反饋(點擊“不再看”),那就可以不再向此用戶推這個廣告。

計算廣告中主要模塊、策略及其場景(上篇)

數據流轉

上圖中可以看到兩條處理線,一條是廣告競價請求(投放日誌)的處理,另一條是廣告曝光、點擊等監測數據(跟蹤日誌)的處理,具體可看我在圖上的說明。

總結如下:

  1. 廣告跟蹤日誌和投放日誌接入數據高速公路,由數據高速公路把數據運到分佈式計算平台和流計算平台。
  2. 分佈式計算平台周期性以批處理的方式加工數據,得到數據和模型,存到內存中方便調用。
  3. 流計算平台以流處理的方式加工最近一小段時間的數據,得到數據也存到內存中方便調用。

3. 競價核心處理流程

接下來,看下競價核心的處理流程,分適配器(輸入器)、處理器、渲染器(輸出器)。

計算廣告中主要模塊、策略及其場景(上篇)

競價核心處理流程

一般來說一個DSP會對接多個ADX,因此請求會先到適配器,使用適配器設計模式,不同ADX平台接口會採用不同的適配器處理。

然後,填充Action數據輸入到處理器中。處理器中使用過濾器的設計模式,增加新業務時根據業務需要增加過濾器即可,因此整體的處理框架相對穩定,且具備十分強大的業務靈活性和高性能擴充性。

渲染器也是用適配器設計模式,Action根據不同ADX平台接口適配,最後輸出給ADX。

計算廣告中主要模塊、策略及其場景(上篇)

處理器

重點看下處理器,根據上圖處理器中包含索引匹配、廣告過濾、出價、出價過濾、決定勝出、曝光點擊地址生成、Bid/UnBid日誌等。

索引匹配是指根據媒體條件索引出匹配的廣告,廣告過濾指根據廣告條件過濾掉不合適的廣告。出價、出價過濾和決定勝出就是精排里的內容,粗排這裡沒說明。

三、算法和場景

本部分中會重點講解:主要模塊用到的算法策略和相關場景,包括檢索、粗排、CTR預估平台、CTR預估特徵和模型、出價和預算。其中CTR預估平台、CTR預估特徵和模型、出價是精排的部分。

1. 廣告檢索

廣告檢索就是解決相關性問題,要檢索出與用戶相關性較高的廣告,相關性較低的會影響用戶體驗和廣告效果。檢索分兩步,定向匹配和逐層召回。

定向匹配:

定向匹配要考慮廣告本身限制,也要考慮此次請求的用戶與廣告之間的匹配。廣告本身限制包括廣告設定的總/每日預算、投放日期、投放時間段、黑白名單、頻次控制等等。而用戶與廣告間的匹配可通過倒排索引實現。

計算廣告中主要模塊、策略及其場景(上篇)

定向匹配流程圖

一個定向請求包括userid和targetid,根據userid去取用戶標籤,根據targetid取廣告的定向包,把定向包解析成DNF的形式(建立倒排索引),與用戶標籤進行匹配。

一般採用DNF(析取範式)的形式存儲廣告的定向條件,例如:

  • DNF1:(30歲 男性)∪(25歲 女性)
  • DNF2:(非男性)∪(廣東 女性)∪(北京 喜歡美食 女性)

每個DNF可分解為一個或多個合取範式(CNF),例如:DNF1=C1∪C2,C1=(30歲 男性)。

每個CNF可分解為一個或多個條件的交,例如:C1=A1∩A2,A1=30歲,A2=男性。

每個條件可用一個賦值集來表示,例如:A1=30歲,表示為age∈{30}。(PS:一般年齡不會精確到幾歲,而是設計成25-30年齡段的格式。)

而且其中有兩個特點:

  1. 當某次廣告請求滿足某個CNF時,則包含此CNF的所有廣告均滿足條件,因此對CNF建立倒排索引,並加上CNF→AD的複製索引即可;
  2. 設廣告請求中的定向條件個數為n,而m表示某CNF中賦值集條件數,若n<m,則此CNF不滿足該次請求的條件。

此外,還要向廣告主提供定向的方法,包括地域定向、人口屬性定向、行為定向、上下文定向、重定向、lookalike等等。

這裡還比較考驗用戶標籤的設計,標籤類型可以用人口屬性、用戶分類、商業屬性、內容標籤、行為標籤等,其中除了最基礎以外,其他的都會用到標籤建模。因為絕大部分標籤都來源於數據挖掘而非直接的事實標籤,所以給每個標籤制定合理的計算標準,也要劃分標籤權重(標籤權重=時間衰減×權重×行為權重)。

對某種定向方法的評估可以從質和量兩個角度出發。

質是指定向的效果,該定向的流量eCPM、點擊率、轉化率等核心指標是否高於平均值;量是指定向的規模,該定向的流量佔整體廣告庫存流量的比重,從召回率和準確率上看覆蓋程度,從廣告主使用率看廣告主使用意向。

逐層召回:

由於通過定向匹配過濾出的廣告量級有時仍然較大,還會增加根據相關性設計的逐層召回——即根據相關性水平把廣告分層,然後從高到低逐層召回,直到足夠的廣告參與粗排。

思路就是在檢索階段引入某種評價函數,並以此函數的評價結果結果作為相關性分數。

評價函數設計有兩個要求:合理性,與最終排序時使用的評價函數相近;高效性,在檢索階段實現快速評價算法。

一般使用線性函數,變量為各標籤或關鍵詞,且各權重為正。

而具體選擇什麼變量作為相關性因素,則要根據場景、業務特點等進行自我調整,更是要結合對最終排序影響較大的變量。

以美團為例:美團中有推薦廣告、搜索廣告、站外廣告等多種廣告類型,有餐飲、外賣、酒店、婚紗攝影等多種業務類型。因此,美團會考慮多種相關性因素:查詢匹配模式、距離、星級評價等。

例如:針對Query匹配模式,廣告召回時會優先使用Query精確匹配模式召回,其次選擇模糊匹配模式,最後才嘗試採用語義匹配模式。針對距離因素,廣告召回會優先召回距離3公里內的商戶,其次選擇5公里內的商戶,最後嘗試全城召回。

此外,美團也會考慮到不同業務的特點,例如:距離的設置上,對於餐飲類流量,系統會優先召回3公里內的商戶。而對於距離相對不敏感的婚紗攝影類流量,系統則會放寬限制,優先召回10公里內的商戶,或者直接採用全城召回策略。

2. 粗排

粗排是指:用少量基礎特徵,快速過濾候選廣告,選出topN進入精排。

仍然以美團為例(美團資料較多):

美團DSP對接了多個站外ADX,有很多站外媒體流量,美團考慮到了流量因素(媒體、用戶數據)和非流量因素(LBS、天氣等),也考慮到不同流量所覆蓋的特徵不同——如有的流量包含大量豐富的用戶畫像,而有的流量無用戶畫像,但有標識性較為明顯的媒體特徵,如P2P、母嬰類媒體等。

因此對於不同流量,會使用不同的粗排策略,以更好地應用流量特徵。

美團對於不同場景下的廣告粗排會使用不同模型,最後匯總打分,匯總使用LR模型,不同廣告行業權重不同。廣告粗排定向場景包括基於用戶畫像、基於天氣特徵、基於關鍵詞特徵、基於上下文、基於重定向等等。

下面會對基於用戶畫像、基於天氣特徵、基於關鍵詞特徵做描述,注意在各個場景下中的數據準備、離線建模和在線使用。

(1)基於用戶畫像:

基於用戶畫像核心是標籤體系設計和數據挖掘生成標籤。

美團現有用戶標籤體系為樹狀結構,包括:商戶分類興趣體系、自然屬性、社會屬性、心理認知、自定義標籤等五大類。

用戶畫像工程每日例行運行一次,離線處理各數據源併合併產出設備ID粒度的標準化用戶標籤,然後導入Redis緩存,以供線上加載使用。

雖然這裡用到的美團用戶標籤體系是已經有的,但還是簡單講下用戶標籤體系的建模。

興趣體系是挖掘型,應用於搜索推薦廣告等大型算法場景,是用戶在某些分類下所有標籤的累加值。

自然屬性、社會屬性是統計、聚類型標籤,可把用戶填寫的資料作為樣本,用戶行為作為特徵,預估無資料的用戶。心理認知是挖掘、統計型標籤,例如消費水平要用到rfm模型(f消費頻次 m消費金額),用戶價值則要根據行為時間、消費頻率、消費金額等劃分。

策略目的:把用戶標籤中的興趣體系和商戶分類體系關聯起來,而廣告又都來源於這些商戶,就得到用戶標籤與廣告的關聯打分並用於粗排。

數據準備:抽取一段時間的用戶廣告行為數據,點擊、轉化、收藏等用戶行為有不同的行為權重,可把轉化等同於多次點擊(升採樣),然後使用Spark的ML庫進行頻繁集挖掘。

頻繁集挖掘:美團中使用了頻繁集挖掘方案,因為用戶標籤和商戶分類類似,規則收益可能好於模型;其次,頻繁集可挖掘出規則考慮不到的關聯關係;最後,可解釋性較強,人工干預方便。

離線建模:

由於廣告商戶分類分三級,每一條點擊記錄都拆分成多份,讓每一級的分類都能和用戶標籤關聯,保證每個層級都不會遺漏。

通過Spark的ML庫找出大量頻繁集以後,剔除掉僅包含廣告分類或用戶標籤的。並限制用戶標籤在頻繁項中的數據,不超過兩個,以保證覆蓋較多用戶。然後對廣告分類與興趣標籤的關係打分,廣告分類A與興趣標籤B的打分為:

計算廣告中主要模塊、策略及其場景(上篇)

並考慮到廣告展示量對點擊的影響,最後得到下表:

計算廣告中主要模塊、策略及其場景(上篇)

打分表:

共生次數來源於用戶廣告行為,得分=共生次數/該二級分類下廣告展現次數,可篩選出置頂標籤下關聯度較高的廣告二級分類。得到全部頻繁集及相應打分后,可線下進入人工篩選,提出不符合認知的,最終結果作為離線模型產出,寫入數據庫。

在線使用:每天定時加載一次離線結果到內存中,等某次請求的檢索召回完成後,對於有用戶畫像的請求根據離線模型產出,對廣告進行打分和排序。

計算廣告中主要模塊、策略及其場景(上篇)

整體應用框架:

FLOW分流,是指在請求進來之後會劃分一定百分比的流量作為實驗流量,用於用戶定向實驗。會分析一段時間的累計實驗結果,與base分流額作對比,以檢測用戶定向策略帶來的效果提升,並反饋給頻繁集模型,以干預調整離線產出模型。

(2)基於天氣:

在美團O2O業務中,天氣情況對用戶和業務都會有影響,例如:天氣會對外賣產生很大影響。

而不同行業受到的影響不同,有些行業對天氣敏感,例如餐飲、運動等,而有些行業對天氣不敏感;例如親子、結婚等,有些是因為轉化不發生在當下。因此,對不同廣告分類分別訓練,每個行業訓練一個模型。

策略目的:每個行業分別訓練一個離線模型,在線加載模型對廣告分類和天氣特徵的關係進行打分。

數據準備:

天氣基礎數據包括溫度、雨量、雪量、天氣現象(大雨、霧霾等)、風力等級等。線下模型訓練要使用歷史天氣數據,線上模型加載要使用當前天氣數據,但兩者的特徵要一致,否則會影響模型在線的效果。

美團配送團隊每日會提供未來72小時的天氣數據,同時保存了穩定的歷史數據,可直接使用。然後確定更新時間,因為天氣情況在短時間(一小時)內較穩定,而且第三方媒體對DSP的響應時間有嚴格限制。如果每次廣告請求都去請求天氣數據,會對性能造成較大影響,所以以小時粒度和城市粒度來保存天氣。

Gentle AdaBoost模型:

在模型上,選擇AdaBoost的改進版Gentle AdaBoost。AdaBoost模型可使用若干簡單的弱分類器訓練出一個強大的分類器,且較少出現過擬合現象。

AdaBoost、GBDT、XGBoost都是Boost(提升)一族的算法,可將弱學習器提升為強學習器。且線上檢索端不可太複雜,選用了AdaBoost常用的樹樁模型(即深度為1的決策樹)。在樹樁模型中,Gentle AdaBoost的效果好於傳統離散AdaBoost。

計算廣告中主要模塊、策略及其場景(上篇)

Gentle AdaBoost

數據處理:

要把準備好的數據(溫度、濕度、降水量、降雪量、天氣情況等)處理成適合決策樹分類的特徵,例如:溫度,作為連續變量處理,對於特徵為溫度的決策樹,訓練合適的分割點(分桶),將溫度歸類到合適的葉子節點。

對於僅有幾個取值(正常、一般惡劣、非常惡劣等)天氣情況,當做離散值對待,進行one-hot編碼,散列到有限的幾個數值上(如1、2、3)。若離散值較多,也可以連續值對待。

離線建模:

以轉化為目標,搜集一段時間的歷史點擊數據,對數據進行特徵化處理,最終訓練出合適的離線模型,每個行業訓練一個模型。

去掉了Gentle AdaBoost最後的感知器模型,直接使用回歸函數的和作為打分。而且,在每次迭代過程中,我們會保留當前錯誤率,當迭代達到一定次數,而錯誤率仍大於給定閾值時,則直接捨棄對該行業的訓練——即在天氣場景定向中,不對該行業的廣告打分,閾值可動態配置。

另外,考慮到線上加載迭代模型會犧牲性能,我們將迭代輪次控制在100次以內。最終結果會存在Tair緩存中,其中key為一級及二級行業,value即為AdaBoost模型的多輪迭代結果,同時保留了最後一輪迭代的錯誤率。

計算廣告中主要模塊、策略及其場景(上篇)

天氣粗排邏輯:

在線使用:廣告檢索端要從Tair讀取離線模型,來完成廣告打分。

因為AdaBoost迭代模型的特點,在線上加載較為耗時,有三個方面可以優化。模型緩存,對某條廣告打分后,將其對應的二級分類及相應模型加入緩存,後續同分類可直接使用緩存模型。

打分緩存,在指定小時,指定城市內,同二級分類的廣告打分一致,可對分類+城市的打分緩存處理,每個整點更新一次。犧牲部分廣告打分換取性能提升,使用動態配置的閾值來控制每次檢索請求中模型迭代的輪次。

舉個例子:閾值設為200次,在整點時刻,前五個召回廣告的行業各不相同,且使用的模型分別迭代80、90、60、60、30次結束,則本次請求中我們只對前三個廣告打分(80+90+60<200),並將廣告打分進行緩存。後續召回廣告,其二級分類若能命中緩存,則打分,否則不打分。

在第二次廣告請求過來時,同樣沿用這個策略,對已經緩存的廣告打分直接加載,否則迭代模型進行打分,直到達到迭代閾值200為止。

同時,通過打分緩存機制,可以保證前面犧牲掉的廣告行業被逐步打分。使用該優化策略,可以完全確保上線后的性能,通過調整迭代輪次的閾值,控制打分與性能的折中關係。

在本案例中,實際情況性能和打分之間的矛盾提現的淋漓盡致,要在理解策略和算法的特點之後,結合工程上的流程和約束,尋找優秀的解決方案。

(3)基於關鍵詞

基於關鍵詞特徵的方案,是指:通過對用戶近期搜索詞的分析,識別出用戶感興趣的店鋪及分類,以便於在站外為用戶投放相關廣告。

策略目的:構建搜索詞和店鋪分類的關係。

數據準備:用戶近期搜索詞,由於關鍵詞特徵對時效性要求較高,所以除了離線數據以外,實時數據也要參與進來。

TF-IDF模型:此模型常用於文章主題提取等——即文章和詞之間的相關程度,而文章-詞模型與詞-店鋪模型非常相似。因此TF-IDF模型也可用於計算詞-店鋪分類的關聯程度。

計算廣告中主要模塊、策略及其場景(上篇)

用於文章主題提取的TF-IDF模型

離線建模:以用戶搜索詞為“潮汕火鍋”為例,計算“美食/火鍋”的商家分類與該關鍵詞的相似程度,具體公式如下:

計算廣告中主要模塊、策略及其場景(上篇)

c1 = 搜索“潮汕火鍋”后的全部點擊數

c2 = 搜索“潮汕火鍋”後點擊“美食/火鍋”類目店鋪的全部點擊數

c3 = 搜索詞總數

c4 = 搜索點擊“美食/火鍋”類目的詞總數

由此計算出店鋪分類與關鍵詞的關係,取topN(根據存儲大小及不同店鋪對同一詞的TF-IDF差距擬定)個店鋪分類。

單店及商圈計算方法與此類似,它們的計算值會同時與店鋪分類的TF-IDF進行比較,不作區分。

(此處有一點需注意:如果用戶搜索“中山公園 火鍋”,可以預見店鋪分類與商圈會同等重要,則最終產出兩條獨立打分規則,分別掛在店鋪分類和商圈下面)

使用Spark來構建離線模型,提取用戶的搜索詞和搜索後點擊的店鋪及店鋪分類,運用上述方案來計算每個搜索詞的關聯店鋪及店鋪分類,設置閾值,保留分數較大的分類結果。

分詞用的是點評分詞系統,同時保存原始詞和切分后基礎詞的TF-IDF結果。結果也存在Tair中,以檢索詞為key,關聯店鋪分類和店鋪的TF-IDF打分作為value進行保存。

實時流計算:

因為關鍵詞的時效性,除了離線以外,也用實時流計算處理用戶行為,並把最後的結果保存在Tair集群。

首先,通過Kafka訂閱用戶行為實時流,以五分鐘為時間片處理用戶行為,查找用戶ID和搜索詞,如果搜索詞過長,則進行分詞,接着從Tair中查找出與該搜索詞相關的店鋪及店鋪分類和打分(離線模型給出)。

然後,在Tair中查找該用戶ID是否有歷史結果。若有,則讀出,對之前的打分進行衰減(衰減方案見下文),並與當前新的打分進行合併;否則,將新的數據及時間戳寫入Tair。該方案的流程圖如下:

計算廣告中主要模塊、策略及其場景(上篇)

此方案核心是新老數據的合併,如果新數據包含老數據中的分類&商圈,則用新數據中的權重;若未包含,則對老數據中的分類&商圈權重衰減,若衰減后小於閾值,則提出此分類&商圈。

衰減方案是根據時間衰減,使用牛頓冷卻定律,默認半衰期為72小時(不同的店鋪分類給予不同的半衰期)。

使用牛頓冷卻定律,參數計算公式為:0.5 = 1 × e-α*時間間隔 ,解出α,並帶入下面公式得到實際權重為:

計算廣告中主要模塊、策略及其場景(上篇)

其中,w為老權重,w’為新權重。

在線使用:

檢索端接收到廣告請求,根據當前獲取的用戶ID,從Tair中讀取用戶偏好的店鋪分類,與召回的廣告進行匹配,當廣告分類與召回廣告匹配成功,則順便將Tair讀出的分數進行時間衰減后,作為該廣告的關鍵詞打分。

檢索端採用與實時流同樣的時間衰減方案,以保證一致性。

示例:

用戶A在早上8:30有火鍋類搜索行為,Spark Streaming處理後進入Tair。假設此時最新時間戳為8:30,而該用戶在11:00搜索親子類商鋪,Spark Streaming處理該條記錄后,之前的火鍋權重需要衰減,同時時間戳更新為11:00。

假設此時立即有廣告檢索請求命中該用戶,則此時用戶火鍋類偏好權重為11:00時權重;假設下午16:00有ADX請求命中該用戶,則用戶火鍋類權重需要根據16:00到11:00的時間間隔繼續衰減。因為只有在此用戶廣告請求時才會計算權重。

在此案例中,針對關鍵詞時效性強的特點,綜合運用了離線計算和在線流計算兩種方案,並考慮廣告競價流程,直接在檢索召回階段順便讀出。此外,對tf-idf模型的用法,也有了更深刻的認識,基於上下文的定嚮應該也可以用這模型。

定向匯總:

此階段是把用戶畫像、天氣、關鍵詞、上下文、重定向等不同場景下的打分匯總起來。

美團對於不同場景下的廣告粗排會使用不同模型,最後匯總打分,匯總使用LR模型,不同廣告行業權重不同。分不同廣告行業,以點擊為樣本,轉化為模型,以各個場景下的前期打分為特徵,進行混合打分權重的離線建模。

公式如下:

計算廣告中主要模塊、策略及其場景(上篇)

其中θ是向量:

計算廣告中主要模塊、策略及其場景(上篇)

其中x0,x1……,xn是各個場景定向下的具體打分,打分分佈在[0,1]之間。

冷啟動時,對每個場景打分給予一個默認權重,積累一定量數據后,使用離線模型訓練出各個廣告行業下的θ向量,並在引擎端加載使用。引擎端加載各個場景的廣告打分,並根據廣告行業加載打分權重,最終完成每個廣告與當前的流量綜合打分。

總結:

從ABtest來看,場景化排序機制對點擊率和轉化率的提升都很明顯。之後還可豐富各類場景特徵、引入更多場景、嘗試不同模型等方法去提升粗排效果。

此次介紹了美團基於場景化的粗排機制,可很明顯感受到:在不同場景中,在當前架構、數據、流程等局限條件下,如何綜合運用數據處理、特徵工程、離線建模、實時流計算、緩存優化等手段以達到策略目的。從場景的拆分匯總到不同場景的不同策略,每一點都值得學習。

3. CTR預估特徵和模型

本節中會講特徵計算系統和模型,特徵計算系統為各個模型(主要是CTR預估)提供標準化的特徵。模型則會講解針對於CTR預估的LR、GBDT、FFM、PNN四大模型。

樣本中的信息在訓練是也可以學習到:但是高維度稀疏下對樣本量的要求也很大,就要從特徵表達上去突破。

在CTR預估中,LR one-hot之後導致特徵高維稀疏,FM使用隱向量的內積來建模組合特徵,FFM在此基礎上引入field的概念,針對不同的field上使用不同隱向量。

而DNN輸入往往是密集的,所以單純的DNN不能用於特徵高緯稀疏的CTR預估。如何表達特徵而且還能不缺失樣本中的信息,一直督促算法的發展。

此外,在實際情況下,還會綜合考慮ROI、場景特徵特點、上線優化瓶頸、latency、資源消耗、性能等因素以選擇合適的模型。

特徵計算系統:

特徵計算系統用以實時計算場景(媒體、上下文等)、廣告和用戶的特徵,並提供實時查詢功能。

(1)特徵挖掘

特徵有三個來源:場景、廣告和用戶。

人工設計特徵需要結合業務領域知識,分析實際業務數據分佈特點,尋找與點擊率變化相關的屬性。

特徵挖掘可從三個基本思路出發,擴展維度、維度及維度的組合、特徵時效性。

擴展維度,指:Tina就愛特徵集合中未包含的屬性維度,例如在廣告基本屬性基礎之上,加入創意中的圖像/文本上可利用的信息;或考慮到層級關係,廣告/廣告主/廣告行業越往上泛化性能越好,越往下越稀疏,但有更強個性化信息和精度。

基於維度及維度的組合,統計廣告行為相關的統計量,例如用戶在過去一段時間對某一類廣告的點擊率。

上面提到的特徵大部分屬於靜態特徵——即歷史上相對穩定的屬性,可以通過業務DB獲取同步到特徵庫,或者從流量日誌中離線挖掘得到,例如:廣告主,所屬行業,用戶的基礎畫像等。

而特徵時效性,就是指:挖掘用戶動態特徵,動態特徵實時在變化,例如實時挖掘用戶瀏覽/點擊行為,歷史信息和實時信息相互補充,也可以提升模型性能。粗排中的關鍵詞場景就是個很好的動態特徵案例。

(2)特徵計算流程

計算廣告中主要模塊、策略及其場景(上篇)

特徵計算流程

從上圖中可以看到:特徵挖掘分實時和離線兩種方式,實現邏輯基本一致,但是計算設施和時效性不同。

從特徵庫輸出的會用於離線的模型訓練和在線的預測,其中的特徵預處理實現邏輯也基本一致,因為訓練后的模型參數生成預估模型,用以預估服務。

離線方式中數據存儲在HDFS等分佈式存儲上,利用Hadoop/Spark等計算框架來處理海量數據。可以進行較多的實驗和迭代,嘗試不同的樣本採樣、樣本權重、特徵處理方法、特徵組合方法等,最終得到一個最優的方法,在離線評估得到好的結果后,最終將確定的方案在線上使用。

實時數據處理可以採用Storm/SparkStreaming等流式計算引擎,模型訓練則基於parameter server架構現online-learning,更快的更新模型,形成快速反饋的數據閉環,使得模型對於數據分佈的變化響應更及時。

模型預測即為線上預估服務,在線請求經過一定的預處理構造出特徵數據,而有些廣告請求本身不包含的特徵數據需要從外部系統獲取,通過關聯的方式補全,之後特徵處理方式基本與訓練時相同。

要注意時間短,對查找性能要求非常高,所以一般在線需要查詢的特徵存儲在redis緩存中。

(3)數據清洗

數據清洗在實時和離線中都要進行,主要任務是:數據類型檢查、特殊字符清理、異常值過濾、缺失值處理四類。

數據類型檢查,是指:檢查字段和值的數據類型是否一致,例如某個數值型字段出現了字符串類型的值,很明顯這就是異常值,需要處理掉。

特殊字符清理,是指:處理日誌中的特殊字符,數據字段分隔符標準化。

異常值過濾,或是數據範圍不合理,一般通過業務規則判斷,或者通過統計量分析。

常用統計量包括:最大值,最小值。

如果數據分佈服從正態分佈,則測量值如果與平均值的偏差超過3個標準差,則認為是異常。

缺失值處理中,缺失值一般處理為統一填充特殊值或者平均數、中位數、眾數等統計量。也可以通過預測模型利用不存在缺失值的屬性來預測缺失值,例如:性別就可用預測模型預測。

(4)特徵預處理

計算廣告中主要模塊、策略及其場景(上篇)

特徵預處理邏輯

特徵類型可分為:連續型特徵和離散型特徵,連續型特徵有無限值,離散型有有限的值。

特徵千奇八怪,要經過預處理才能輸入到模型中,不同模型對輸入特徵的要求略有差異。

歸一化,不同變量往往量綱不同,不同維度之間的取值範圍差異很大,歸一化可以消除量綱對最終結果的影響,使不同變量具有可比性,取值大的特徵不再佔有優勢。

同時,歸一化后加快了梯度下降求最優解的速度。

歸一化方式有:線性歸一化(映射到[0,1]範圍)、z-score標準化(均值為0,方差為1的數據集)、非線性歸一化(用log、指數函數等數學函數)。

數據平滑,主要起對數據修正作用,例如:拉普拉斯平滑,防止某個維度值沒有在樣本中出現過而出現0概率問題。具體平滑算法可以根據業務場景選擇。

離散化,是:對連續型特徵離散化,連續特徵理論上無窮多個,離散化能減少算法的時間和空間開銷。

離散化方法可分為:無監督和有監督。無監督包括等寬(值域等分為K個區間,前提數值要均勻分佈)、等頻率(每個區間的對象數目相等)、基於聚類(例如k-means聚類,需人工置頂區間數);有監督即考慮label分類信息下的離散化過程,可使用MDLP。

二值化,即:one-hot編碼。

二值特徵,主要是0/1特徵,即特徵只取兩種值:0或者1。

例如廣告id特徵:目前的id是否是某個特定廣告id。連續值處理為二值特徵方法:先將連續值離散化,再將離散化后的特徵切分為N個二元特徵(one-hot encoding),每個特徵代表是否在這個區間內。二值化同時也給LR這樣的線性模型引入了非線性。

二值化示例,例如:有運動特徵:[“足球”,”籃球”,”羽毛球”,”乒乓球”](這裡N=4)

足球 => 1000

籃球 => 0100

羽毛球 => 0010

乒乓球 => 0001

(5)特徵選擇

one-hot之後很容易導致特徵高維稀疏,從而出現維數災難問題,通過特徵選擇能夠大大緩解。特徵選擇方法是最優特徵子集搜索策略和評價標準的組合,與學習算法結合考慮。

特徵選擇方法有過濾式特徵選擇(Filter)、封裝式特徵選擇(Wrapper)、嵌入式特徵選擇(Embedded)。

過濾式特徵選擇(Filter)一般使用評價準則來增強特徵與類別的相關性,,削減特徵之間的相關性,通常選擇和類別相關度大的特徵或者特徵子集。

過濾式特徵選擇的評價標準分為四種,即:距離度量、信息度量、關聯度度量以及一致性度量。

目前我們有基於單特徵AUC,基於信息增益的評價工具等。

優點:算法的通用性強;省去了分類器的訓練步驟,算法複雜性低,因而適用於大規模數據集;可以快速去除大量不相關的特徵,作為特徵的預篩選器非常合適。

缺點:由於算法的評價標準獨立於特定的學習算法,所選的特徵子集在分類準確率方面通常低於Wrapper方法。

封裝式特徵選擇(Wrapper)是利用學習算法的目標函數(通常是預測效果評分)來評價特徵子集的優劣。

因此,對於一個待評價的特徵子集,Wrapper方法需要訓練一個分類器,根據分類器的性能對該特徵子集進行評價,可以基於模型的AUC來判斷。

優點:相對於Filter方法,Wrapper方法找到的特徵子集分類性能通常更好。

缺點:Wrapper方法選出的特徵通用性不強,當改變學習算法時,需要針對該學習算法重新進行特徵選擇;由於每次對子集的評價都要進行分類器的訓練和測試,所以算法計算複雜度很高,尤其對於大規模數據集來說,算法的執行時間很長。

在嵌入式特徵選擇(Embedded)中,特徵選擇算法本身作為組成部分嵌入到學習算法里,例如:GBDT,深度學習,在模型訓練過程中自動對特徵進行篩選。

另外一個標準的嵌入類方法是正則的方式,L1正則中,最後係數為0的特徵說明對模型貢獻很小,我們保留係數不為0的特徵即可,這樣就達到了特徵選擇的目的。

(6)特徵工程自動化

特徵工程自動化是指引入更複雜的模型來解決特徵總數增多的問題,通過模型自身自動捕獲特徵或者特徵組合的能力來減少人工特徵工程的部分工作。

相當於在CTR預估模型中就包含了特徵工程自動化的過程,例如:GBDT+LR,GBDT的路徑可直接作為LR輸入特徵使用,GBDT用來提取特徵,彌補LR模型在非線性上的不足,具體的可到模型階段講解。

(7)特徵質量控制

尋找到了恰當特徵之後,需要對特徵的數據質量進行監控,及時發現特徵層面的問題,保障模型訓練效果。

而且由於我們廣告數據流很複雜,一個廣告從發出請求到最終產生曝光/點擊並落地日誌數據經過了多個環節,可設計DataCheck系統檢查線上廣告請求(預測)與落地日誌(訓練)用到的特徵是否一致,以及各個特徵的分佈是否穩定。

計算廣告中主要模塊、策略及其場景(上篇)

線上線下數據流

如上圖所示,從線上真實業務環境copy廣告請求流量到sample server,按規則抽樣后將完整請求及特徵數據寫入HBASE中,包括:query信息以及訂單信息。

sample server和ctr server在特徵處理實現上保持一致。線下環境,基於storm實現針對曝光日誌的實時監控,從全量曝光日誌中抽取請求id與Hbase中匹配的記錄,檢測某個特徵緯度值是否一致,並同時統計關鍵特徵緯度分佈。

離線MR程序會統計全量日誌中的各特徵值分佈,特徵的一致性以及分佈統計會定時發送report,異常波動達到設置閾值則會觸發告警,提醒相關人員介入。

4. LR模型

計算廣告中主要模塊、策略及其場景(上篇)

Z是線性邊界表現形式,x是特徵工程得到的特徵向量(onehot后的特徵),w是每個特徵的權重值。

預測CTR採用二項邏輯回歸,則類別表示為點擊1,不點擊0,條件概率分佈函數則表示:

計算廣告中主要模塊、策略及其場景(上篇)

邏輯回歸的損失函數構成的模型,可能有些權重很大,有些權重很小,導致過擬合,使得模型的複雜度提高,泛化能力差。通過正則化方法來解決,可採用L2范數正則化,損失函數如下:

計算廣告中主要模塊、策略及其場景(上篇)

計算廣告中主要模塊、策略及其場景(上篇)

C是正則項係數,它的值越大,說明對模型的複雜度懲罰越大,對擬合數據的損失懲罰小,就不會過分擬合數據,在訓練數據上的偏差較大,在未知數據上的方差較小。

但是,可能出現欠擬合現象;如果它的值很小,說明比較注重對訓練數據的擬合,在訓練數據上的偏差會小,但是可能會導致過擬合。

損失函數的梯度表示:

計算廣告中主要模塊、策略及其場景(上篇)

求對數似然函數I(w)的極大值問題一般會轉為求極小值來解,乘以一個負的係數后,變成負對數似然函數。這個函數是個凸函數,可用梯度下降法、共軛梯度法、擬牛頓法、BFGS等算法求解。

LR模型求解得到的參數,作為離線模型的參數以快照形式提供給在線模型,在線模型加載參數快照,結合此次請求的特徵值,根據CTR預估公式即可計算出預估的CTR值。

LR模型簡單,可加很多很多特徵,而且容易debug,能根據模型和結果容易定位到是哪些特徵出了問題,並且可以馬上採取補救措施,例如:人工修改模型權重,以達到增強或者減弱某些特徵對結果的影響。

還有非常多的優化算法可選擇,還有些算法可以有效的產生稀疏模型並使得效果不損失,這對上線非常有利,也有利於減少線上響應時間。

缺點則只是個線性模型,不是對所有的數據都能很有效,不同的業務其數據分佈都不同,有些業務的數據可能還是需要非線性的模型來學習。

下篇將講解CTR預估GBDT、FFM、PNN模型、CTR預估平台、出價、預算等,敬請期待。

參考文獻

《計算廣告》劉鵬

《定向廣告系統結構》陳肖雅

https://zhuanlan.zhihu.com/p/50441627

《大型廣告系統架構 — 檢索模塊》公眾號:架構叢談

《DSP系統技術架構參考【技術類】》吳俊

https://www.jianshu.com/p/7774114e083a

《美團O2O廣告營銷中的機器學習技術》公眾號:美團技術團隊

《美團點評聯盟廣告的場景化定向排序機制》公眾號:美團技術團隊

《OMG廣告點擊率預估之特徵工程》公眾號:騰訊AMS廣平技術黑板報

《在線廣告DSP平台實時競價算法的研究與實現》 韓靜

#專欄作家#

Vency,公眾號:Vency不二,人人都是產品經理專欄作家。海外商業產品經理,關注海外、廣告、商業化、營銷等領域,追求用戶、技術、商業、社會價值的統一,喜好看書、逛館。

本文原創發佈於人人都是產品經理。未經許可,禁止轉載。

題圖來自 Unsplash,基於CC0協議。

版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《計算廣告中主要模塊、策略及其場景(上篇)》
文章链接:https://www.pmbear.com/%e8%a8%88%e7%ae%97%e5%bb%a3%e5%91%8a%e4%b8%ad%e4%b8%bb%e8%a6%81%e6%a8%a1%e5%a1%8a%e3%80%81%e7%ad%96%e7%95%a5%e5%8f%8a%e5%85%b6%e5%a0%b4%e6%99%af%ef%bc%88%e4%b8%8a%e7%af%87%ef%bc%89/
本站资源仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

大前端WP主题 更专业 更方便

联系我们联系我们