計算廣告中主要模塊、策略及其場景(上)
本文將會講述計算廣告(主要是DSP)中的主要模塊、用到的策略及其場景。筆者希望大家能和ta一樣,在了解廣告業(yè)務的同時,還能對策略的設計有一定了解,總結出一些通用的方法。
本文是我最近學習的一個總結,之前的文章多是和功能特別是廣告主界面有關,而本篇文章則是和策略有關。
本文分三個部分:
- 功能和策略,主講功能型產品和策略型產品的區(qū)別;
- 架構綜述,主講廣告系統(tǒng)的流程、模塊和技術架構;
- 算法和場景,主講各個模塊和場景中用到的算法。
一、功能和策略
先下個狹隘的定義,因為找不到比功能/策略更好的詞來描述,我在本文中把以UI/UE/人機視覺交互等主要交付物是具體產品形態(tài)的產品經理,狹隘的稱之為功能產品經理;把以策略/計算邏輯等等主要交付物不是具體產品形態(tài)的產品經理,狹隘的稱之為策略產品經理。
功能和策略不是非黑即白:
一定要注意:本文中的所謂功能和策略產品經理是狹隘的,只是為了方便大家理解和對比。
狹隘在于兩點:
- 對功能和策略的定義太狹隘,所謂視覺交互只是功能的一部分,所謂策略也不只是計算邏輯/算法等等,但為了便于理解就狹隘定義了;
- 對產品工作理解太狹隘,實際上策略和功能與活動、文案等都是滿足需求和解決問題。方案,產品工作中都會綜合運用各種手段去滿足需求,關鍵是滿足需求,而非或功能或策略的手段。
因為策略具有無直觀產品形態(tài)、達到某個目的、受多個因素影響、需根據(jù)因素變化隨時調整等特點,所以在發(fā)現(xiàn)問題-解決問題的產品經理基本工作流程,策略的實際內容與功能略有不同。
發(fā)現(xiàn)問題:
功能型面對的是場景相對聚焦的需求,重要的是抽象,把需求抽象成問題,把解決方案抽象成功能,抽象出來的多是實體或對象;策略型面對的是更多樣更小眾更有統(tǒng)計意義的需求,場景更豐富,抽象粒度比功能小,抽象出來的多是變量。
解決方案:
功能型產出的是收斂的解決方案,把需求調研和分析得到的結果收斂成較通用的方案,例如:微信的注冊登錄適用于每個用戶,每個用戶體驗到的交互也是一致的。
功能型產品通過路程、原型來表達產品實現(xiàn)效果;策略型產出的是發(fā)散的解決方案,把需求調研和分析得到的結果發(fā)散出多種場景和變量,例如:CTR預估中考慮來自廣告、用戶、場景等多方面的因素。策略型產品通過邏輯描述和效果示例表達產品實現(xiàn)效果。
開發(fā)跟進:
功能型在跟進開發(fā)中,更關注開發(fā)結果而非開發(fā)過程,過程頂多關心是否可實現(xiàn)和實現(xiàn)原理,面對開發(fā)結果是驗收的性質。
策略型在跟進開發(fā)中,更多參與過程,也可以說整個過程就是不斷評估測試效果再與RD一起發(fā)現(xiàn)各要素中的問題。當然,兩者都是要達到目標效果才能上線。
上線回歸:
功能型因為需求聚焦、方案收斂,能更快地達到理想態(tài),關掉該feature的產品循環(huán)。而策略型很有可能會出現(xiàn)永無止境的產品循環(huán),因為策略型需求簡單但場景復雜,而且受到很多因素影響,甚至人力都不一定能窮盡。策略要有較強的數(shù)據(jù)敏感度,擁抱不確定性。
總結一下:
功能型產品針對一個相對聚焦的需求,抽象出能夠滿足80%用戶的解決方案,而策略型產品針對一個受復雜因素影響的需求,策略需求比功能需求更長尾。
強調一點:在實際運用中,有時把功能和策略結合起來會用更好的效果,例如iPhone調節(jié)亮度中包含了手動調節(jié)功能和自動調節(jié)策略,不要自我設限,目標是解決問題,而不是用什么方法。
二、架構綜述
1. 簡單架構
簡單架構
廣告系統(tǒng)主要解決一個問題:在給定展示場景、用戶的情況下,返回收益最大化的廣告。
上圖是一個最簡單的DSP廣告系統(tǒng)架構,1是收到一個廣告展示請求,8是發(fā)出針對此次請求的出價、廣告創(chuàng)意等。
其中,Router、排序模塊和檢索模塊是廣告系統(tǒng)的核心,特征計算系統(tǒng)、計費系統(tǒng)和投放系統(tǒng)是用以輔助核心模塊的。
Router:對外提供HTTP服務,接收請求后,依次與特征計算系統(tǒng)、檢索模塊、排序模塊交互,最后返回出價和廣告等,是樞紐。
檢索模塊:解決相關性問題,要檢索出與用戶相關性較高的廣告,相關性較低的會影響用戶體驗和廣告效果。檢索分兩步:首先是定向匹配,根據(jù)廣告主對廣告設定的定向條件,過濾出符合本次請求特點的廣告;然后是逐層召回,按多種定向策略或是相關性計算選擇與本次請求最相關的若干個廣告。
排序模塊:解決收益最大化問題,約束下最大化DSP利潤。排序也可分兩步——粗排和精排,粗排用到的特征比精排少。由于檢索出來的候選廣告集較大,精排涉及到CTR預估和出價較復雜,通過粗排可做到快速擴率,選出前若干個進入精排,以節(jié)省計算時間和成本。
特征計算系統(tǒng):實時計算曝光場景(媒體、廣告位、上下文、設備等)、用戶的特征,并向其他模塊提供實時查詢功能。
計費系統(tǒng):實時處理曝光后媒體返回過來的曝光數(shù)據(jù),以及其他點擊、轉化等數(shù)據(jù),并計算廣告費用、剩余預算等,也要包含反作弊。
投放系統(tǒng):供廣告主使用,給廣告設置定向條件、創(chuàng)意等,是廣告主直接操作的界面。
2. 復雜架構
復雜架構
復雜架構相對于簡單架構而言,把系統(tǒng)中涉及到的具體模塊,都展示出來,并且區(qū)分了離線和在線。組成部分包括:分布式計算平臺、廣告投放機、流計算平臺、數(shù)據(jù)高速公路。
其中,分布式計算平臺是離線數(shù)據(jù),流計算平臺是實時數(shù)據(jù)。分布式計算平臺會把輸出的行為定向、算法模型等通過海量內存管理系統(tǒng)(例如:Redis)暫存在內存中,方便在競價過程中快速調用,以滿足DSP在30ms內完成出價,整個競價過程在100ms以內。
分布式計算平臺:采用分布式技術(例如:Hadoop),它輸出的數(shù)據(jù)、算法模型一方面提供給廣告投放機進行出價決策,另一方面提供給ETL,以數(shù)據(jù)倉庫為基礎向產品運營等人提供數(shù)據(jù)報表的支持,以便于商業(yè)決策。
廣告投放機:就是簡單架構中的router、檢索模塊和排序模塊,是DSP收到請求和返回出價廣告等的主邏輯,此處還包含了收益管理模塊。廣告排序得到的結果是局部最優(yōu),收益管理則是用分布式計算平臺中計算好的分配規(guī)劃來生成分配方案,以達到全局最優(yōu)。
流計算平臺:
是對實時數(shù)據(jù)(短時間內發(fā)生的用戶日志和廣告日志等數(shù)據(jù))的處理,包括:反作弊、實時點擊反饋、計費、實時受眾定向。
- 反作弊:是根據(jù)實時用戶行為識別作弊流量,并不納入計費;
- 實時點擊反饋:會生成實時點擊率特征,和離線特征一起參與到基于CTR模型的廣告排序中;
- 實時受眾定向:會把實時數(shù)據(jù)加工成實時用戶標簽,用以廣告檢索;
- 計費:是實時計算廣告費用,把預算即將耗盡的廣告及時告知給實時索引以下線此廣告。
實時數(shù)據(jù)對廣告檢索、排序等效果提升很明顯,例如:前幾分鐘給用戶推了此廣告,而用戶有負反饋(點擊“不再看”),那就可以不再向此用戶推這個廣告。
數(shù)據(jù)流轉
上圖中可以看到兩條處理線,一條是廣告競價請求(投放日志)的處理,另一條是廣告曝光、點擊等監(jiān)測數(shù)據(jù)(跟蹤日志)的處理,具體可看我在圖上的說明。
總結如下:
- 廣告跟蹤日志和投放日志接入數(shù)據(jù)高速公路,由數(shù)據(jù)高速公路把數(shù)據(jù)運到分布式計算平臺和流計算平臺。
- 分布式計算平臺周期性以批處理的方式加工數(shù)據(jù),得到數(shù)據(jù)和模型,存到內存中方便調用。
- 流計算平臺以流處理的方式加工最近一小段時間的數(shù)據(jù),得到數(shù)據(jù)也存到內存中方便調用。
3. 競價核心處理流程
接下來,看下競價核心的處理流程,分適配器(輸入器)、處理器、渲染器(輸出器)。
競價核心處理流程
一般來說一個DSP會對接多個ADX,因此請求會先到適配器,使用適配器設計模式,不同ADX平臺接口會采用不同的適配器處理。
然后,填充Action數(shù)據(jù)輸入到處理器中。處理器中使用過濾器的設計模式,增加新業(yè)務時根據(jù)業(yè)務需要增加過濾器即可,因此整體的處理框架相對穩(wěn)定,且具備十分強大的業(yè)務靈活性和高性能擴充性。
渲染器也是用適配器設計模式,Action根據(jù)不同ADX平臺接口適配,最后輸出給ADX。
處理器
重點看下處理器,根據(jù)上圖處理器中包含索引匹配、廣告過濾、出價、出價過濾、決定勝出、曝光點擊地址生成、Bid/UnBid日志等。
索引匹配是指根據(jù)媒體條件索引出匹配的廣告,廣告過濾指根據(jù)廣告條件過濾掉不合適的廣告。出價、出價過濾和決定勝出就是精排里的內容,粗排這里沒說明。
三、算法和場景
本部分中會重點講解:主要模塊用到的算法策略和相關場景,包括檢索、粗排、CTR預估平臺、CTR預估特征和模型、出價和預算。其中CTR預估平臺、CTR預估特征和模型、出價是精排的部分。
1. 廣告檢索
廣告檢索就是解決相關性問題,要檢索出與用戶相關性較高的廣告,相關性較低的會影響用戶體驗和廣告效果。檢索分兩步,定向匹配和逐層召回。
定向匹配:
定向匹配要考慮廣告本身限制,也要考慮此次請求的用戶與廣告之間的匹配。廣告本身限制包括廣告設定的總/每日預算、投放日期、投放時間段、黑白名單、頻次控制等等。而用戶與廣告間的匹配可通過倒排索引實現(xiàn)。
定向匹配流程圖
一個定向請求包括userid和targetid,根據(jù)userid去取用戶標簽,根據(jù)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年齡段的格式。)
而且其中有兩個特點:
- 當某次廣告請求滿足某個CNF時,則包含此CNF的所有廣告均滿足條件,因此對CNF建立倒排索引,并加上CNF→AD的復制索引即可;
- 設廣告請求中的定向條件個數(shù)為n,而m表示某CNF中賦值集條件數(shù),若n<m,則此CNF不滿足該次請求的條件。
此外,還要向廣告主提供定向的方法,包括地域定向、人口屬性定向、行為定向、上下文定向、重定向、lookalike等等。
這里還比較考驗用戶標簽的設計,標簽類型可以用人口屬性、用戶分類、商業(yè)屬性、內容標簽、行為標簽等,其中除了最基礎以外,其他的都會用到標簽建模。因為絕大部分標簽都來源于數(shù)據(jù)挖掘而非直接的事實標簽,所以給每個標簽制定合理的計算標準,也要劃分標簽權重(標簽權重=時間衰減×權重×行為權重)。
對某種定向方法的評估可以從質和量兩個角度出發(fā)。
質是指定向的效果,該定向的流量eCPM、點擊率、轉化率等核心指標是否高于平均值;量是指定向的規(guī)模,該定向的流量占整體廣告庫存流量的比重,從召回率和準確率上看覆蓋程度,從廣告主使用率看廣告主使用意向。
逐層召回:
由于通過定向匹配過濾出的廣告量級有時仍然較大,還會增加根據(jù)相關性設計的逐層召回——即根據(jù)相關性水平把廣告分層,然后從高到低逐層召回,直到足夠的廣告參與粗排。
思路就是在檢索階段引入某種評價函數(shù),并以此函數(shù)的評價結果結果作為相關性分數(shù)。
評價函數(shù)設計有兩個要求:合理性,與最終排序時使用的評價函數(shù)相近;高效性,在檢索階段實現(xiàn)快速評價算法。
一般使用線性函數(shù),變量為各標簽或關鍵詞,且各權重為正。
而具體選擇什么變量作為相關性因素,則要根據(jù)場景、業(yè)務特點等進行自我調整,更是要結合對最終排序影響較大的變量。
以美團為例:美團中有推薦廣告、搜索廣告、站外廣告等多種廣告類型,有餐飲、外賣、酒店、婚紗攝影等多種業(yè)務類型。因此,美團會考慮多種相關性因素:查詢匹配模式、距離、星級評價等。
例如:針對Query匹配模式,廣告召回時會優(yōu)先使用Query精確匹配模式召回,其次選擇模糊匹配模式,最后才嘗試采用語義匹配模式。針對距離因素,廣告召回會優(yōu)先召回距離3公里內的商戶,其次選擇5公里內的商戶,最后嘗試全城召回。
此外,美團也會考慮到不同業(yè)務的特點,例如:距離的設置上,對于餐飲類流量,系統(tǒng)會優(yōu)先召回3公里內的商戶。而對于距離相對不敏感的婚紗攝影類流量,系統(tǒng)則會放寬限制,優(yōu)先召回10公里內的商戶,或者直接采用全城召回策略。
2. 粗排
粗排是指:用少量基礎特征,快速過濾候選廣告,選出topN進入精排。
仍然以美團為例(美團資料較多):
美團DSP對接了多個站外ADX,有很多站外媒體流量,美團考慮到了流量因素(媒體、用戶數(shù)據(jù))和非流量因素(LBS、天氣等),也考慮到不同流量所覆蓋的特征不同——如有的流量包含大量豐富的用戶畫像,而有的流量無用戶畫像,但有標識性較為明顯的媒體特征,如P2P、母嬰類媒體等。
因此對于不同流量,會使用不同的粗排策略,以更好地應用流量特征。
美團對于不同場景下的廣告粗排會使用不同模型,最后匯總打分,匯總使用LR模型,不同廣告行業(yè)權重不同。廣告粗排定向場景包括基于用戶畫像、基于天氣特征、基于關鍵詞特征、基于上下文、基于重定向等等。
下面會對基于用戶畫像、基于天氣特征、基于關鍵詞特征做描述,注意在各個場景下中的數(shù)據(jù)準備、離線建模和在線使用。
(1)基于用戶畫像:
基于用戶畫像核心是標簽體系設計和數(shù)據(jù)挖掘生成標簽。
美團現(xiàn)有用戶標簽體系為樹狀結構,包括:商戶分類興趣體系、自然屬性、社會屬性、心理認知、自定義標簽等五大類。
用戶畫像工程每日例行運行一次,離線處理各數(shù)據(jù)源并合并產出設備ID粒度的標準化用戶標簽,然后導入Redis緩存,以供線上加載使用。
雖然這里用到的美團用戶標簽體系是已經有的,但還是簡單講下用戶標簽體系的建模。
興趣體系是挖掘型,應用于搜索推薦廣告等大型算法場景,是用戶在某些分類下所有標簽的累加值。
自然屬性、社會屬性是統(tǒng)計、聚類型標簽,可把用戶填寫的資料作為樣本,用戶行為作為特征,預估無資料的用戶。心理認知是挖掘、統(tǒng)計型標簽,例如消費水平要用到rfm模型(f消費頻次 m消費金額),用戶價值則要根據(jù)行為時間、消費頻率、消費金額等劃分。
策略目的:把用戶標簽中的興趣體系和商戶分類體系關聯(lián)起來,而廣告又都來源于這些商戶,就得到用戶標簽與廣告的關聯(lián)打分并用于粗排。
數(shù)據(jù)準備:抽取一段時間的用戶廣告行為數(shù)據(jù),點擊、轉化、收藏等用戶行為有不同的行為權重,可把轉化等同于多次點擊(升采樣),然后使用Spark的ML庫進行頻繁集挖掘。
頻繁集挖掘:美團中使用了頻繁集挖掘方案,因為用戶標簽和商戶分類類似,規(guī)則收益可能好于模型;其次,頻繁集可挖掘出規(guī)則考慮不到的關聯(lián)關系;最后,可解釋性較強,人工干預方便。
離線建模:
由于廣告商戶分類分三級,每一條點擊記錄都拆分成多份,讓每一級的分類都能和用戶標簽關聯(lián),保證每個層級都不會遺漏。
通過Spark的ML庫找出大量頻繁集以后,剔除掉僅包含廣告分類或用戶標簽的。并限制用戶標簽在頻繁項中的數(shù)據(jù),不超過兩個,以保證覆蓋較多用戶。然后對廣告分類與興趣標簽的關系打分,廣告分類A與興趣標簽B的打分為:
并考慮到廣告展示量對點擊的影響,最后得到下表:
打分表:
共生次數(shù)來源于用戶廣告行為,得分=共生次數(shù)/該二級分類下廣告展現(xiàn)次數(shù),可篩選出置頂標簽下關聯(lián)度較高的廣告二級分類。得到全部頻繁集及相應打分后,可線下進入人工篩選,提出不符合認知的,最終結果作為離線模型產出,寫入數(shù)據(jù)庫。
在線使用:每天定時加載一次離線結果到內存中,等某次請求的檢索召回完成后,對于有用戶畫像的請求根據(jù)離線模型產出,對廣告進行打分和排序。
整體應用框架:
FLOW分流,是指在請求進來之后會劃分一定百分比的流量作為實驗流量,用于用戶定向實驗。會分析一段時間的累計實驗結果,與base分流額作對比,以檢測用戶定向策略帶來的效果提升,并反饋給頻繁集模型,以干預調整離線產出模型。
(2)基于天氣:
在美團O2O業(yè)務中,天氣情況對用戶和業(yè)務都會有影響,例如:天氣會對外賣產生很大影響。
而不同行業(yè)受到的影響不同,有些行業(yè)對天氣敏感,例如餐飲、運動等,而有些行業(yè)對天氣不敏感;例如親子、結婚等,有些是因為轉化不發(fā)生在當下。因此,對不同廣告分類分別訓練,每個行業(yè)訓練一個模型。
策略目的:每個行業(yè)分別訓練一個離線模型,在線加載模型對廣告分類和天氣特征的關系進行打分。
數(shù)據(jù)準備:
天氣基礎數(shù)據(jù)包括溫度、雨量、雪量、天氣現(xiàn)象(大雨、霧霾等)、風力等級等。線下模型訓練要使用歷史天氣數(shù)據(jù),線上模型加載要使用當前天氣數(shù)據(jù),但兩者的特征要一致,否則會影響模型在線的效果。
美團配送團隊每日會提供未來72小時的天氣數(shù)據(jù),同時保存了穩(wěn)定的歷史數(shù)據(jù),可直接使用。然后確定更新時間,因為天氣情況在短時間(一小時)內較穩(wěn)定,而且第三方媒體對DSP的響應時間有嚴格限制。如果每次廣告請求都去請求天氣數(shù)據(jù),會對性能造成較大影響,所以以小時粒度和城市粒度來保存天氣。
Gentle AdaBoost模型:
在模型上,選擇AdaBoost的改進版Gentle AdaBoost。AdaBoost模型可使用若干簡單的弱分類器訓練出一個強大的分類器,且較少出現(xiàn)過擬合現(xiàn)象。
AdaBoost、GBDT、XGBoost都是Boost(提升)一族的算法,可將弱學習器提升為強學習器。且線上檢索端不可太復雜,選用了AdaBoost常用的樹樁模型(即深度為1的決策樹)。在樹樁模型中,Gentle AdaBoost的效果好于傳統(tǒng)離散AdaBoost。
Gentle AdaBoost
數(shù)據(jù)處理:
要把準備好的數(shù)據(jù)(溫度、濕度、降水量、降雪量、天氣情況等)處理成適合決策樹分類的特征,例如:溫度,作為連續(xù)變量處理,對于特征為溫度的決策樹,訓練合適的分割點(分桶),將溫度歸類到合適的葉子節(jié)點。
對于僅有幾個取值(正常、一般惡劣、非常惡劣等)天氣情況,當做離散值對待,進行one-hot編碼,散列到有限的幾個數(shù)值上(如1、2、3)。若離散值較多,也可以連續(xù)值對待。
離線建模:
以轉化為目標,搜集一段時間的歷史點擊數(shù)據(jù),對數(shù)據(jù)進行特征化處理,最終訓練出合適的離線模型,每個行業(yè)訓練一個模型。
去掉了Gentle AdaBoost最后的感知器模型,直接使用回歸函數(shù)的和作為打分。而且,在每次迭代過程中,我們會保留當前錯誤率,當?shù)_到一定次數(shù),而錯誤率仍大于給定閾值時,則直接舍棄對該行業(yè)的訓練——即在天氣場景定向中,不對該行業(yè)的廣告打分,閾值可動態(tài)配置。
另外,考慮到線上加載迭代模型會犧牲性能,我們將迭代輪次控制在100次以內。最終結果會存在Tair緩存中,其中key為一級及二級行業(yè),value即為AdaBoost模型的多輪迭代結果,同時保留了最后一輪迭代的錯誤率。
天氣粗排邏輯:
在線使用:廣告檢索端要從Tair讀取離線模型,來完成廣告打分。
因為AdaBoost迭代模型的特點,在線上加載較為耗時,有三個方面可以優(yōu)化。模型緩存,對某條廣告打分后,將其對應的二級分類及相應模型加入緩存,后續(xù)同分類可直接使用緩存模型。
打分緩存,在指定小時,指定城市內,同二級分類的廣告打分一致,可對分類+城市的打分緩存處理,每個整點更新一次。犧牲部分廣告打分換取性能提升,使用動態(tài)配置的閾值來控制每次檢索請求中模型迭代的輪次。
舉個例子:閾值設為200次,在整點時刻,前五個召回廣告的行業(yè)各不相同,且使用的模型分別迭代80、90、60、60、30次結束,則本次請求中我們只對前三個廣告打分(80+90+60<200),并將廣告打分進行緩存。后續(xù)召回廣告,其二級分類若能命中緩存,則打分,否則不打分。
在第二次廣告請求過來時,同樣沿用這個策略,對已經緩存的廣告打分直接加載,否則迭代模型進行打分,直到達到迭代閾值200為止。
同時,通過打分緩存機制,可以保證前面犧牲掉的廣告行業(yè)被逐步打分。使用該優(yōu)化策略,可以完全確保上線后的性能,通過調整迭代輪次的閾值,控制打分與性能的折中關系。
在本案例中,實際情況性能和打分之間的矛盾提現(xiàn)的淋漓盡致,要在理解策略和算法的特點之后,結合工程上的流程和約束,尋找優(yōu)秀的解決方案。
(3)基于關鍵詞
基于關鍵詞特征的方案,是指:通過對用戶近期搜索詞的分析,識別出用戶感興趣的店鋪及分類,以便于在站外為用戶投放相關廣告。
策略目的:構建搜索詞和店鋪分類的關系。
數(shù)據(jù)準備:用戶近期搜索詞,由于關鍵詞特征對時效性要求較高,所以除了離線數(shù)據(jù)以外,實時數(shù)據(jù)也要參與進來。
TF-IDF模型:此模型常用于文章主題提取等——即文章和詞之間的相關程度,而文章-詞模型與詞-店鋪模型非常相似。因此TF-IDF模型也可用于計算詞-店鋪分類的關聯(lián)程度。
用于文章主題提取的TF-IDF模型
離線建模:以用戶搜索詞為“潮汕火鍋”為例,計算“美食/火鍋”的商家分類與該關鍵詞的相似程度,具體公式如下:
c1 = 搜索“潮汕火鍋”后的全部點擊數(shù)
c2 = 搜索“潮汕火鍋”后點擊“美食/火鍋”類目店鋪的全部點擊數(shù)
c3 = 搜索詞總數(shù)
c4 = 搜索點擊“美食/火鍋”類目的詞總數(shù)
由此計算出店鋪分類與關鍵詞的關系,取topN(根據(jù)存儲大小及不同店鋪對同一詞的TF-IDF差距擬定)個店鋪分類。
單店及商圈計算方法與此類似,它們的計算值會同時與店鋪分類的TF-IDF進行比較,不作區(qū)分。
(此處有一點需注意:如果用戶搜索“中山公園 火鍋”,可以預見店鋪分類與商圈會同等重要,則最終產出兩條獨立打分規(guī)則,分別掛在店鋪分類和商圈下面)
使用Spark來構建離線模型,提取用戶的搜索詞和搜索后點擊的店鋪及店鋪分類,運用上述方案來計算每個搜索詞的關聯(lián)店鋪及店鋪分類,設置閾值,保留分數(shù)較大的分類結果。
分詞用的是點評分詞系統(tǒng),同時保存原始詞和切分后基礎詞的TF-IDF結果。結果也存在Tair中,以檢索詞為key,關聯(lián)店鋪分類和店鋪的TF-IDF打分作為value進行保存。
實時流計算:
因為關鍵詞的時效性,除了離線以外,也用實時流計算處理用戶行為,并把最后的結果保存在Tair集群。
首先,通過Kafka訂閱用戶行為實時流,以五分鐘為時間片處理用戶行為,查找用戶ID和搜索詞,如果搜索詞過長,則進行分詞,接著從Tair中查找出與該搜索詞相關的店鋪及店鋪分類和打分(離線模型給出)。
然后,在Tair中查找該用戶ID是否有歷史結果。若有,則讀出,對之前的打分進行衰減(衰減方案見下文),并與當前新的打分進行合并;否則,將新的數(shù)據(jù)及時間戳寫入Tair。該方案的流程圖如下:
此方案核心是新老數(shù)據(jù)的合并,如果新數(shù)據(jù)包含老數(shù)據(jù)中的分類&商圈,則用新數(shù)據(jù)中的權重;若未包含,則對老數(shù)據(jù)中的分類&商圈權重衰減,若衰減后小于閾值,則提出此分類&商圈。
衰減方案是根據(jù)時間衰減,使用牛頓冷卻定律,默認半衰期為72小時(不同的店鋪分類給予不同的半衰期)。
使用牛頓冷卻定律,參數(shù)計算公式為:0.5 = 1 × e-α*時間間隔 ,解出α,并帶入下面公式得到實際權重為:
其中,w為老權重,w’為新權重。
在線使用:
檢索端接收到廣告請求,根據(jù)當前獲取的用戶ID,從Tair中讀取用戶偏好的店鋪分類,與召回的廣告進行匹配,當廣告分類與召回廣告匹配成功,則順便將Tair讀出的分數(shù)進行時間衰減后,作為該廣告的關鍵詞打分。
檢索端采用與實時流同樣的時間衰減方案,以保證一致性。
示例:
用戶A在早上8:30有火鍋類搜索行為,Spark Streaming處理后進入Tair。假設此時最新時間戳為8:30,而該用戶在11:00搜索親子類商鋪,Spark Streaming處理該條記錄后,之前的火鍋權重需要衰減,同時時間戳更新為11:00。
假設此時立即有廣告檢索請求命中該用戶,則此時用戶火鍋類偏好權重為11:00時權重;假設下午16:00有ADX請求命中該用戶,則用戶火鍋類權重需要根據(jù)16:00到11:00的時間間隔繼續(xù)衰減。因為只有在此用戶廣告請求時才會計算權重。
在此案例中,針對關鍵詞時效性強的特點,綜合運用了離線計算和在線流計算兩種方案,并考慮廣告競價流程,直接在檢索召回階段順便讀出。此外,對tf-idf模型的用法,也有了更深刻的認識,基于上下文的定向應該也可以用這模型。
定向匯總:
此階段是把用戶畫像、天氣、關鍵詞、上下文、重定向等不同場景下的打分匯總起來。
美團對于不同場景下的廣告粗排會使用不同模型,最后匯總打分,匯總使用LR模型,不同廣告行業(yè)權重不同。分不同廣告行業(yè),以點擊為樣本,轉化為模型,以各個場景下的前期打分為特征,進行混合打分權重的離線建模。
公式如下:
其中θ是向量:
其中x0,x1……,xn是各個場景定向下的具體打分,打分分布在[0,1]之間。
冷啟動時,對每個場景打分給予一個默認權重,積累一定量數(shù)據(jù)后,使用離線模型訓練出各個廣告行業(yè)下的θ向量,并在引擎端加載使用。引擎端加載各個場景的廣告打分,并根據(jù)廣告行業(yè)加載打分權重,最終完成每個廣告與當前的流量綜合打分。
總結:
從ABtest來看,場景化排序機制對點擊率和轉化率的提升都很明顯。之后還可豐富各類場景特征、引入更多場景、嘗試不同模型等方法去提升粗排效果。
此次介紹了美團基于場景化的粗排機制,可很明顯感受到:在不同場景中,在當前架構、數(shù)據(jù)、流程等局限條件下,如何綜合運用數(shù)據(jù)處理、特征工程、離線建模、實時流計算、緩存優(yōu)化等手段以達到策略目的。從場景的拆分匯總到不同場景的不同策略,每一點都值得學習。
3. CTR預估特征和模型
本節(jié)中會講特征計算系統(tǒng)和模型,特征計算系統(tǒng)為各個模型(主要是CTR預估)提供標準化的特征。模型則會講解針對于CTR預估的LR、GBDT、FFM、PNN四大模型。
樣本中的信息在訓練是也可以學習到:但是高維度稀疏下對樣本量的要求也很大,就要從特征表達上去突破。
在CTR預估中,LR one-hot之后導致特征高維稀疏,F(xiàn)M使用隱向量的內積來建模組合特征,F(xiàn)FM在此基礎上引入field的概念,針對不同的field上使用不同隱向量。
而DNN輸入往往是密集的,所以單純的DNN不能用于特征高緯稀疏的CTR預估。如何表達特征而且還能不缺失樣本中的信息,一直督促算法的發(fā)展。
此外,在實際情況下,還會綜合考慮ROI、場景特征特點、上線優(yōu)化瓶頸、latency、資源消耗、性能等因素以選擇合適的模型。
特征計算系統(tǒng):
特征計算系統(tǒng)用以實時計算場景(媒體、上下文等)、廣告和用戶的特征,并提供實時查詢功能。
(1)特征挖掘
特征有三個來源:場景、廣告和用戶。
人工設計特征需要結合業(yè)務領域知識,分析實際業(yè)務數(shù)據(jù)分布特點,尋找與點擊率變化相關的屬性。
特征挖掘可從三個基本思路出發(fā),擴展維度、維度及維度的組合、特征時效性。
擴展維度,指:Tina就愛特征集合中未包含的屬性維度,例如在廣告基本屬性基礎之上,加入創(chuàng)意中的圖像/文本上可利用的信息;或考慮到層級關系,廣告/廣告主/廣告行業(yè)越往上泛化性能越好,越往下越稀疏,但有更強個性化信息和精度。
基于維度及維度的組合,統(tǒng)計廣告行為相關的統(tǒng)計量,例如用戶在過去一段時間對某一類廣告的點擊率。
上面提到的特征大部分屬于靜態(tài)特征——即歷史上相對穩(wěn)定的屬性,可以通過業(yè)務DB獲取同步到特征庫,或者從流量日志中離線挖掘得到,例如:廣告主,所屬行業(yè),用戶的基礎畫像等。
而特征時效性,就是指:挖掘用戶動態(tài)特征,動態(tài)特征實時在變化,例如實時挖掘用戶瀏覽/點擊行為,歷史信息和實時信息相互補充,也可以提升模型性能。粗排中的關鍵詞場景就是個很好的動態(tài)特征案例。
(2)特征計算流程
特征計算流程
從上圖中可以看到:特征挖掘分實時和離線兩種方式,實現(xiàn)邏輯基本一致,但是計算設施和時效性不同。
從特征庫輸出的會用于離線的模型訓練和在線的預測,其中的特征預處理實現(xiàn)邏輯也基本一致,因為訓練后的模型參數(shù)生成預估模型,用以預估服務。
離線方式中數(shù)據(jù)存儲在HDFS等分布式存儲上,利用Hadoop/Spark等計算框架來處理海量數(shù)據(jù)。可以進行較多的實驗和迭代,嘗試不同的樣本采樣、樣本權重、特征處理方法、特征組合方法等,最終得到一個最優(yōu)的方法,在離線評估得到好的結果后,最終將確定的方案在線上使用。
實時數(shù)據(jù)處理可以采用Storm/SparkStreaming等流式計算引擎,模型訓練則基于parameter server架構現(xiàn)online-learning,更快的更新模型,形成快速反饋的數(shù)據(jù)閉環(huán),使得模型對于數(shù)據(jù)分布的變化響應更及時。
模型預測即為線上預估服務,在線請求經過一定的預處理構造出特征數(shù)據(jù),而有些廣告請求本身不包含的特征數(shù)據(jù)需要從外部系統(tǒng)獲取,通過關聯(lián)的方式補全,之后特征處理方式基本與訓練時相同。
要注意時間短,對查找性能要求非常高,所以一般在線需要查詢的特征存儲在redis緩存中。
(3)數(shù)據(jù)清洗
數(shù)據(jù)清洗在實時和離線中都要進行,主要任務是:數(shù)據(jù)類型檢查、特殊字符清理、異常值過濾、缺失值處理四類。
數(shù)據(jù)類型檢查,是指:檢查字段和值的數(shù)據(jù)類型是否一致,例如某個數(shù)值型字段出現(xiàn)了字符串類型的值,很明顯這就是異常值,需要處理掉。
特殊字符清理,是指:處理日志中的特殊字符,數(shù)據(jù)字段分隔符標準化。
異常值過濾,或是數(shù)據(jù)范圍不合理,一般通過業(yè)務規(guī)則判斷,或者通過統(tǒng)計量分析。
常用統(tǒng)計量包括:最大值,最小值。
如果數(shù)據(jù)分布服從正態(tài)分布,則測量值如果與平均值的偏差超過3個標準差,則認為是異常。
缺失值處理中,缺失值一般處理為統(tǒng)一填充特殊值或者平均數(shù)、中位數(shù)、眾數(shù)等統(tǒng)計量。也可以通過預測模型利用不存在缺失值的屬性來預測缺失值,例如:性別就可用預測模型預測。
(4)特征預處理
特征預處理邏輯
特征類型可分為:連續(xù)型特征和離散型特征,連續(xù)型特征有無限值,離散型有有限的值。
特征千奇八怪,要經過預處理才能輸入到模型中,不同模型對輸入特征的要求略有差異。
歸一化,不同變量往往量綱不同,不同維度之間的取值范圍差異很大,歸一化可以消除量綱對最終結果的影響,使不同變量具有可比性,取值大的特征不再占有優(yōu)勢。
同時,歸一化后加快了梯度下降求最優(yōu)解的速度。
歸一化方式有:線性歸一化(映射到[0,1]范圍)、z-score標準化(均值為0,方差為1的數(shù)據(jù)集)、非線性歸一化(用log、指數(shù)函數(shù)等數(shù)學函數(shù))。
數(shù)據(jù)平滑,主要起對數(shù)據(jù)修正作用,例如:拉普拉斯平滑,防止某個維度值沒有在樣本中出現(xiàn)過而出現(xiàn)0概率問題。具體平滑算法可以根據(jù)業(yè)務場景選擇。
離散化,是:對連續(xù)型特征離散化,連續(xù)特征理論上無窮多個,離散化能減少算法的時間和空間開銷。
離散化方法可分為:無監(jiān)督和有監(jiān)督。無監(jiān)督包括等寬(值域等分為K個區(qū)間,前提數(shù)值要均勻分布)、等頻率(每個區(qū)間的對象數(shù)目相等)、基于聚類(例如k-means聚類,需人工置頂區(qū)間數(shù));有監(jiān)督即考慮label分類信息下的離散化過程,可使用MDLP。
二值化,即:one-hot編碼。
二值特征,主要是0/1特征,即特征只取兩種值:0或者1。
例如廣告id特征:目前的id是否是某個特定廣告id。連續(xù)值處理為二值特征方法:先將連續(xù)值離散化,再將離散化后的特征切分為N個二元特征(one-hot encoding),每個特征代表是否在這個區(qū)間內。二值化同時也給LR這樣的線性模型引入了非線性。
二值化示例,例如:有運動特征:[“足球”,”籃球”,”羽毛球”,”乒乓球”](這里N=4)
足球 => 1000
籃球 => 0100
羽毛球 => 0010
乒乓球 => 0001
(5)特征選擇
one-hot之后很容易導致特征高維稀疏,從而出現(xiàn)維數(shù)災難問題,通過特征選擇能夠大大緩解。特征選擇方法是最優(yōu)特征子集搜索策略和評價標準的組合,與學習算法結合考慮。
特征選擇方法有過濾式特征選擇(Filter)、封裝式特征選擇(Wrapper)、嵌入式特征選擇(Embedded)。
過濾式特征選擇(Filter)一般使用評價準則來增強特征與類別的相關性,,削減特征之間的相關性,通常選擇和類別相關度大的特征或者特征子集。
過濾式特征選擇的評價標準分為四種,即:距離度量、信息度量、關聯(lián)度度量以及一致性度量。
目前我們有基于單特征AUC,基于信息增益的評價工具等。
優(yōu)點:算法的通用性強;省去了分類器的訓練步驟,算法復雜性低,因而適用于大規(guī)模數(shù)據(jù)集;可以快速去除大量不相關的特征,作為特征的預篩選器非常合適。
缺點:由于算法的評價標準獨立于特定的學習算法,所選的特征子集在分類準確率方面通常低于Wrapper方法。
封裝式特征選擇(Wrapper)是利用學習算法的目標函數(shù)(通常是預測效果評分)來評價特征子集的優(yōu)劣。
因此,對于一個待評價的特征子集,Wrapper方法需要訓練一個分類器,根據(jù)分類器的性能對該特征子集進行評價,可以基于模型的AUC來判斷。
優(yōu)點:相對于Filter方法,Wrapper方法找到的特征子集分類性能通常更好。
缺點:Wrapper方法選出的特征通用性不強,當改變學習算法時,需要針對該學習算法重新進行特征選擇;由于每次對子集的評價都要進行分類器的訓練和測試,所以算法計算復雜度很高,尤其對于大規(guī)模數(shù)據(jù)集來說,算法的執(zhí)行時間很長。
在嵌入式特征選擇(Embedded)中,特征選擇算法本身作為組成部分嵌入到學習算法里,例如:GBDT,深度學習,在模型訓練過程中自動對特征進行篩選。
另外一個標準的嵌入類方法是正則的方式,L1正則中,最后系數(shù)為0的特征說明對模型貢獻很小,我們保留系數(shù)不為0的特征即可,這樣就達到了特征選擇的目的。
(6)特征工程自動化
特征工程自動化是指引入更復雜的模型來解決特征總數(shù)增多的問題,通過模型自身自動捕獲特征或者特征組合的能力來減少人工特征工程的部分工作。
相當于在CTR預估模型中就包含了特征工程自動化的過程,例如:GBDT+LR,GBDT的路徑可直接作為LR輸入特征使用,GBDT用來提取特征,彌補LR模型在非線性上的不足,具體的可到模型階段講解。
(7)特征質量控制
尋找到了恰當特征之后,需要對特征的數(shù)據(jù)質量進行監(jiān)控,及時發(fā)現(xiàn)特征層面的問題,保障模型訓練效果。
而且由于我們廣告數(shù)據(jù)流很復雜,一個廣告從發(fā)出請求到最終產生曝光/點擊并落地日志數(shù)據(jù)經過了多個環(huán)節(jié),可設計DataCheck系統(tǒng)檢查線上廣告請求(預測)與落地日志(訓練)用到的特征是否一致,以及各個特征的分布是否穩(wěn)定。
線上線下數(shù)據(jù)流
如上圖所示,從線上真實業(yè)務環(huán)境copy廣告請求流量到sample server,按規(guī)則抽樣后將完整請求及特征數(shù)據(jù)寫入HBASE中,包括:query信息以及訂單信息。
sample server和ctr server在特征處理實現(xiàn)上保持一致。線下環(huán)境,基于storm實現(xiàn)針對曝光日志的實時監(jiān)控,從全量曝光日志中抽取請求id與Hbase中匹配的記錄,檢測某個特征緯度值是否一致,并同時統(tǒng)計關鍵特征緯度分布。
離線MR程序會統(tǒng)計全量日志中的各特征值分布,特征的一致性以及分布統(tǒng)計會定時發(fā)送report,異常波動達到設置閾值則會觸發(fā)告警,提醒相關人員介入。
4. LR模型
Z是線性邊界表現(xiàn)形式,x是特征工程得到的特征向量(onehot后的特征),w是每個特征的權重值。
預測CTR采用二項邏輯回歸,則類別表示為點擊1,不點擊0,條件概率分布函數(shù)則表示:
邏輯回歸的損失函數(shù)構成的模型,可能有些權重很大,有些權重很小,導致過擬合,使得模型的復雜度提高,泛化能力差。通過正則化方法來解決,可采用L2范數(shù)正則化,損失函數(shù)如下:
C是正則項系數(shù),它的值越大,說明對模型的復雜度懲罰越大,對擬合數(shù)據(jù)的損失懲罰小,就不會過分擬合數(shù)據(jù),在訓練數(shù)據(jù)上的偏差較大,在未知數(shù)據(jù)上的方差較小。
但是,可能出現(xiàn)欠擬合現(xiàn)象;如果它的值很小,說明比較注重對訓練數(shù)據(jù)的擬合,在訓練數(shù)據(jù)上的偏差會小,但是可能會導致過擬合。
損失函數(shù)的梯度表示:
求對數(shù)似然函數(shù)I(w)的極大值問題一般會轉為求極小值來解,乘以一個負的系數(shù)后,變成負對數(shù)似然函數(shù)。這個函數(shù)是個凸函數(shù),可用梯度下降法、共軛梯度法、擬牛頓法、BFGS等算法求解。
LR模型求解得到的參數(shù),作為離線模型的參數(shù)以快照形式提供給在線模型,在線模型加載參數(shù)快照,結合此次請求的特征值,根據(jù)CTR預估公式即可計算出預估的CTR值。
LR模型簡單,可加很多很多特征,而且容易debug,能根據(jù)模型和結果容易定位到是哪些特征出了問題,并且可以馬上采取補救措施,例如:人工修改模型權重,以達到增強或者減弱某些特征對結果的影響。
還有非常多的優(yōu)化算法可選擇,還有些算法可以有效的產生稀疏模型并使得效果不損失,這對上線非常有利,也有利于減少線上響應時間。
缺點則只是個線性模型,不是對所有的數(shù)據(jù)都能很有效,不同的業(yè)務其數(shù)據(jù)分布都不同,有些業(yè)務的數(shù)據(jù)可能還是需要非線性的模型來學習。
參考文獻
《計算廣告》劉鵬
《定向廣告系統(tǒng)結構》陳肖雅
https://zhuanlan.zhihu.com/p/50441627
《大型廣告系統(tǒng)架構 — 檢索模塊》公眾號:架構叢談
《DSP系統(tǒng)技術架構參考【技術類】》吳俊
https://www.jianshu.com/p/7774114e083a
《美團O2O廣告營銷中的機器學習技術》公眾號:美團技術團隊
《美團點評聯(lián)盟廣告的場景化定向排序機制》公眾號:美團技術團隊
《OMG廣告點擊率預估之特征工程》公眾號:騰訊AMS廣平技術黑板報
《在線廣告DSP平臺實時競價算法的研究與實現(xiàn)》 韓靜
#專欄作家#
Vency,公眾號:Vency不二,人人都是產品經理專欄作家。海外商業(yè)產品經理,關注海外、廣告、商業(yè)化、營銷等領域,追求用戶、技術、商業(yè)、社會價值的統(tǒng)一,喜好看書、逛館。
本文原創(chuàng)發(fā)布于人人都是產品經理。未經許可,禁止轉載。
題圖來自 Unsplash,基于CC0協(xié)議。
看了一小半,發(fā)現(xiàn)是從美團公開文檔中洗出來的,部分內容有些牽強,推薦直接去看原文比較合適
不只是美團,具體文章可以看參考文獻
感謝啊,太棒了
太干貨了,謝謝分享
專專專專專專專專專專專專專專專專專專專專專專專專專專業(yè)
受教了,感謝??