計算廣告丨《網際網路廣告算法和系統實踐》讀書筆記

引言

這是我閱讀《網際網路廣告算法和系統實踐》的筆記，作者王勇睿，在百度閱讀上可以購買，書的篇幅很短，一天就能看完。

本書主要介紹了搜尋廣告算法、非搜尋（定向）廣告算法和實時競價廣告算法，為讀者梳理了廣告中的常用概念如CTR、ECPM，一個廣告系統如何組成，實踐中還會考慮什麼問題，沒有涉及多的數學和算法模型。本書适合入門，但作為小白，很多内容讀完後沒有具體的案例消化，了解深度上有所欠缺。我想當具備了一定的實踐經驗後再來翻閱此書，才能融會貫通。之後的計劃是繼續閱讀劉鵬老師的《計算廣告學》。

網際網路廣告算法和系統實踐

第一部分 網際網路廣告簡介

1.1 廣告簡介

• 廣告是由已确定的出資人通過各種媒介進行的有關産品（商品、服務和觀點）的、有償的、有組織的、綜合的、勸服性的非人員的資訊傳播活動。
• 傳統廣告業務包括三方角色：廣告主、媒體、普通閱聽人
• 廣告曆史

1.2 網際網路廣告

• 顯示廣告、合約廣告、定向廣告、閱聽人定向技術
• 擔保式投放
• 競價廣告、廣義二階拍賣GSP、廣義一階拍賣GSP
• 搜尋廣告、上下文廣告、實時競價
• 廣告交易平台、需求方平台、提供方平台
• 計費方式：點選付費CPC、銷售付費CPS、千次展現付費CPM

1.3 網際網路廣告類型

• 條幅廣告
• 郵件直接營銷廣告
• 富媒體廣告
• 視訊廣告
• 文字鍊廣告
• 社交廣告
• 移動端廣告

1.4 有效性模型

• 曝光：位置很重要。
• 關注：廣告創意吸引人，借助算法定向精準投放
• 了解：讓使用者迅速了解廣告
• 資訊接受：研究人群行為，還要借助心理學
• 保持：追求中長期轉化
• 購買：最終決策，給使用者提供更多更好的選擇

好創意不但能吸引人（提升CTR），而且能夠抓住人（提升ROI）。

1.5 計費模式

• CPM：Cost Per Mile，按照千次展現計費，展現之後的效果廣告平台不保證。适合品牌廣告。
• CPT：Cost Per Time，按照機關時間計費。為了增加曝光度。
• CPC：Cost Per Click，按照千次點選計費，廣告系統要負責對點選率CTR預估；廣告主可以參與競價。關注點選率，但不關注廣告實際成交情況，風險由廣告主承擔。
• CPS：Cost Per Sale，關注轉化率，對廣告主有利。

對廣告主，風險從大到小：CPM/CPT、CPC、CPS

廣告系統收益名額：若千次展現的期望收益CPM值eCPM。

1.6 機制設計

1.6.1 廣告位拍賣

• n個廣告A，m個廣告位S，m＜n，廣告位拍賣從A中選取m條廣告，依次放置到S中。
• 拍賣競争除了展現機會，還包括S中排序位置。
• 廣告位拍賣過程分為廣告排序和廣告扣費。廣告排序考慮展現哪些廣告，廣告扣費考慮收取多少費用。
• 廣告拍賣是多次重複博弈，納什均衡點、本地無嫉妒均衡、占優政策、激烈相容

1.6.2 廣義一階價格GFP

• 廣告展現不扣費
• 一階價格是指廣告主本身出價。
• 不存在納什均衡點，競價機器人導緻廣告系統收益大大降低。

1.6.3 廣義二階價格GSP

• 對應第i位廣告，若發生點選，GSP收取第i位廣告主，第i+1位廣告競價加上一個貨币最小值。
• 若廣告主降低競價，其展現位置不變時，不會降低收費。下家沒有降低競價行為，導緻上家付出更多點選費用。存在本地無嫉妒均衡。
• 均衡報價：n個廣告A，每條廣告價值V，m個廣告位S，每個位置點選率X，每個位置目前競價P。對于任意廣告位i上獲得位置的廣告j有\((v_j-p_i)x_i\ge(v_j-p_{i-1})x_{i-1}\)
• 均衡點不唯一，不是激勵相容。
• 現實中廣告扣費要考慮點選率因素。對于廣告i，廣告系統預估i在目前場景點選率ai，結合競價bi，計算每千次展現期望收益\(ecpm_i=a_ib_i\)，随後将廣告集合按照\(ecpm\)排序，排序靠前若幹條用于展現。計費時，若第i個廣告被點選，從廣告主扣除費用為\(\frac{a_{i+1}b_{i+1}}{a_i}+最小貨币機關\)
  • 若廣告點選率越高，廣告主扣除費用越少，激勵使用者優化廣告品質提高廣告點選率。

1.6.4 VCG機制

• 目标為最大化社會價值
• 有n個廣告A，廣告競價為V，廣告平台提供S廣告位，每個位置點選率X，每條廣告真實價格V。當廣告i不參與關鍵字拍賣，排在i後的廣告主i+1,...,m可獲得的預期總收益為

\[x_iv_{i+1}+x_{i+1}v_{i+2}+...+x_mv_{m+1}

\]

• 由于\(a_i\)參與，廣告獲得價值為

\[x_{i+1}v_{i+1}+x_{i+2}v_{i+2}+...+x_mv_{m}+x_{m+1}v_{m+1}

\]

• 通常隻有m個廣告位，是以\(x_{m+1}=0\)，如果\(a_i\)被點選，那麼它要付出代價是給社會其他個體帶來的利益損失

\[(x_i-x_{i+1})v_{i+1}+(x_{i+1}-x{i+2})v_{i+2}+...+(x_{m-1}-x_m)v_m+(x_m-x_{m+1})v_{m+1}

\]

• VCG相比GSP優勢
  1. VCG激烈相容，按照真實估價出價是最優選擇
  2. VCG機制最大化社會價值，有利于廣告主
  3. VCG存在納什均衡，均衡點唯一
• 缺點
  1. 計算困難，可解釋性差
  2. 相同競價情況VCG扣費低于GSP機制，廣告系統不願意降低收入

1.7 技術課題

• 優化目标
  • 計算廣告學：找到使用者、上下文和合适廣告間最佳比對。
  • 網際網路廣告算法核心問題：根據使用者、環境、廣告全部有效消息，找到最合适的投放政策和模型，兼顧浏覽者、廣告主、廣告平台的最大利益，并不斷調整。
  • 使用者U、環境C、廣告A，算法目标函數為\(F(U,C,A)\)
    • 對于廣告主，關注投資回報率ROI，\(F=\frac{\sum_iReturn_i}{\sum_iInvest_i}\)
    • 對于使用者，\(F=\frac{\sum_iClick_i}{\sum_iImpression_i}\)
    • 對于廣告系統，\(F=CTR*PPC*Discount\)，\(CTR\)是點選率，\(PPC\)是點選收費，\(Discount\)業務因子。
• 搜尋引擎技術
  • 廣告系統和搜尋引擎相似，廣告系統沒有爬蟲子產品，通過規範化步驟擷取。
• 存儲技術和實時計算技術
  • 需要一個适合大規模讀寫的存儲系統，需要實時計算系統。
• 推薦技術
• 點選率預估CTR Prediction
• 廣告主工具
  • 對廣告主，廣告系統提供推廣工具和統計工具。
• 系統架構簡介
  • 前端引擎：接受網頁發來廣告請求，初步處理發給後端，拿到結果拼接傳回請求者，這是線上部分Online
  • 檢索引擎：關注效率和性能，Online
  • 實時點選率預估服務：對廣告打分，一維、二維分數，Online
  • 廣告主操作消息更新服務：廣告主有權随時更改廣告競價，Online
  • 使用者行為資料收集和更新系統：一般是Online
  • 特征提取和行為分析：一般用Hadoop平台，Offline
  • 反作弊系統：Offine和Online
  • 廣告主背景：Offline和Online
  • 存儲系統：存儲任務<key,value>形式，有Offline和Online
  • 計算系統：資訊挖掘，一般采取Hadoop作資料挖掘和特征提取計算，采取MPI架構做模型訓練。

第二部分 搜尋廣告

2.1 搜尋廣告架構

• 搜尋廣告：搜尋過程中搜尋引擎推送的網際網路廣告。
• 當使用者輸入查詢後，廣告系統會經過：廣告檢索、廣告排序、流量配置設定三個子產品為使用者提供廣告。
• 廣告檢索：以目前查詢關鍵字為基礎+使用者自身資訊，從數以萬計的廣告集合中粗選出合适的廣告。可分為廣告索引和廣告比對子子產品。
  • 廣告索引：将廣告建成\(<key：使用者競價詞, value：關聯的廣告清單>\)的索引形式。
  • 廣告比對：将使用者查詢分解成相關競價詞，從建好的索引中提取廣告。
• 廣告排序：計算檢索到廣告的品質分數并排序。
• 流量配置設定：根據廣告排序分數，決定目前情況給使用者出哪些廣告。

2.2 廣告檢索

• 根據使用者關鍵字，選出相關廣告，實際設定粗選和精選兩個步驟：
  • 粗選：用資訊檢索，選取和查詢關鍵字相關的一批廣告。
  • 精選：精确的預估廣告的點選率，進行排序。
• 廣告檢索經過三步驟：廣告分析，關鍵字分析和相關性比對。
  • 廣告分析：對廣告進行處理，擷取廣告相關資訊。
  • 關鍵字分析：根據使用者輸入，判斷是否出廣告，出什麼廣告。
  • 相關性比對：根據關鍵字分析結果，去索引庫中檢索廣告。

2.2.1 廣告分析

• 兩個目的：
  • 将廣告組織成反向索引形式\(<key：競價詞-value：廣告id連結清單>\)
  • 從廣告中抽取特征。
• 廣告主建立廣告會選擇相關的競價詞，容易造成常見詞嚴重傾斜，解決問題的方法包括競價詞生成和模糊比對。
  • 競價詞生成：廣告系統通過分析廣告主的landing page，幫助廣告主選取競價詞。
  • 模糊比對：使用者選擇一個通股出價，按照出價，廣告系統自己選擇跟廣告相關的競價詞。

2.2.2 查詢分析

• 長串：語義資訊豐富，展現量不足，總量大，存儲壓力大。提取關鍵詞彙很重要。
• 短串：語義資訊不明确，根據使用者個性化資訊或上下文資訊消除歧義。
• 重要名額：擴大召回。

2.2.3 相關性比對

• 精确比對：關鍵字嚴格包含某個競價詞才觸發廣告。
• 模糊比對

2.3 廣告排序

• 廣告系統按照ECPM降序排列廣告候選集，将排序靠前廣告展現出來。
  • \(ECPM=廣告競拍價*廣告CTR*1000\)
  • 廣告競拍價：廣告主提供；CTR：廣告系統利用機器學習準确預估；
• 基于點選模型的CTR預估方法
  • 點選率模組化為$$P(click)=P(click|Seen)P(Seen)$$，進而計算\(P(click|Seen)\)
• 基于機器學習的CTR預估算法

2.3.1 邏輯回歸模型

• 函數形式\(y=\frac{1}{(1+e^{-w^Tx})}\)
  • \(x輸入特征向量，y預測目标，w學習特征權重\)
  • 輸入x，類别為1的條件機率

    

    ；輸入x，類别為0的條件機率

    

• 采用極大似然估計學習特征權重\(w\)

  

  • 最大化似然函數的對數

    

  • 邏輯回歸求解屬于無限制優化問題，目标函數負對數似然函數恰好是凸函數，可以采用梯度下降等方法求解\(w\)。
  • 尋找負對數似然函數的梯度方向

    

  • 疊代公式

    

• 防止過拟合
  • L2正則\(NLL(w)+\lambda w^Tw\)
  • L1正則\(NLL(w)+\lambda\|w\|_1\)
• 漂移，線上學習：邏輯回歸的對數似然函數具有樣本可加性。
  • 随機梯度下降

    

2.3.2 特征處理方式

• 将人的先驗知識，表示成機器學習算法能夠接受的方式。
• 常用特征
  • 廣告和查詢關鍵字的相似度：廣告本身特征、查詢本身特征、相似廣告的特征、相似查詢的特征。
  • 廣告的樹形結構資訊：廣告主-廣告賬戶-廣告計劃-廣告組-廣告創意，同一個廣告主的其他廣告創意的CTR能幫助目前廣告創意的CTR。

2.3.3 算法評估

• CTR預估模型效果是否好：全流量-小流量實驗-離線名額驗證
• 衡量預估CTR和真實CTR之間差異，使用AUC衡量CTR預估精度。AUC是ROC曲線下的面積。
  • ROC是二維平面上的曲線，橫坐标是FPR，縱坐标是TPR。調節分類器參數，使得ROC曲線形成一條從(0,0)到(1,1)的曲線，AUC就是ROC曲線下面積之和。
  • 網際網路廣告系統計算AUC：AUC等價于正樣本score大于負樣本score的機率。若正負樣本score值相同，則按0.5正樣本score大于負樣本score對計算。
• 假設正樣本數M，負樣本數N，計算AUC開銷是M*N，通過排序減少AUC時間複雜度。
  • 将樣本按照score大小從高到低排序，score第一大樣本獲得n=M+N的rank值；第二大樣本獲得rank值為n-1。對rank為r的正樣本i，組成正樣本score大于負樣本score的樣本對個數為 r-排在i後的正樣本數。
  • 是以AUC可如下方式計算

    

2.4 廣告主推薦工具

2.4.1 投放要素

• 廣告主注冊一個推廣賬戶Account，包含多個推廣計劃Campaign，每個計劃包含多個推廣單元Group，設定Group主要需要競價詞Bidword和廣告創意Creative。

  

• 一個Group完整投放需求和政策清單

  

• 搜尋廣告系統需要幫助廣告主”充分表達自己投放需求”，給廣告主提供投放基本元素。

  

  • 推薦重點在于競價詞Bidword。

2.4.2 競價詞推薦方式

• 競價詞的推薦方式
  • 主動推薦：不用廣告主參加
  • 被動推薦：廣告主主動建立一些搜尋詞
• 競價詞的比對方式
  • 精确比對：精确命中廣告主所競價的詞
  • 模糊比對：廣告系統對競價詞進行一定程度的擴充
• 推薦工具實際上找到“一座橋梁“

  

  1. 廣告主到中間節點邊歸一化權重，中間節點到候選詞邊故意話權重，文本相關性。
  2. 根據中間節點出度、入度資訊，計算中間節點調整系數，結合第一步相關性，計算出：\(<廣告主1，中間節點，候選詞>\)的分數
  3. 根據\(<廣告主1，中間節點，候選詞>\)的資料，固定一個候選詞，綜合所有中間節點，計算所有\(廣告主1，候選詞1>\)分數，循環計算，獲得\(<廣告主1，候選詞>\)打分清單。
  4. 根據分數排序，擷取前N個詞。

2.4. 3 其他工具

• 投放前後，廣告主需要一些資料幫助決策或者回報，如下

2.5 實踐一：線上學習前沿

• 為了讓模型特征量縮減，可以将邏輯回歸目标函數修改成，模型将傾向于學習稀疏的\(w\)權重。

  \[NLL(w)+\lambda\|w\|_1

  \]

• 随機梯度下降法簡單易行，但往往難以得到特征向量稀疏的結果，Google提出FTRL-Proximal方法可以得到稀疏性更好的訓練結果，其更新公式為：

  

  

  

• 海量資料下，模型存儲量過大給并發查詢時效性帶來很大挑戰。
  • 降低模型特征維數，泊松選擇法
  • 降低每一維特征存儲量，float是4個位元組，Google提出q2.13編碼方式，用2個位元組。

第三部分 定向廣告

定向廣告即非搜尋廣告

3.1 上下文定向

• 根據投放頁面内容，推送相關廣告。關鍵問題對頁面内容的刻畫：
  • 内容提供商自定義：廣告平台預先人工定義一些網頁的類型标簽，内容提供商自己選擇網頁類型。
  • 頁面關鍵字提取：爬蟲抽取網頁中内容，進行一定内容分析，從中抽取可以精确比對上的競價詞，然後到廣告庫中檢索廣告。
  • 網頁聚類：使用爬蟲抽取網頁内容，然後對網頁庫進行文本聚類。

3.2 閱聽人定向

• 給目前使用者流量打标簽的過程
  • 顯示标簽應用：按照标簽售賣流量
  • 隐式應用：不按照使用者标簽顯示售賣流量
• 閱聽人定向方法：
  • 使用者背景資料調查、行為定向

3.2.1 監督行為定向

• 線性泊松回歸模型

  

  ，其中\(\lambda=w^tx\)，W為預估參數，x為特征向量，y為事件發生頻次。
  • 給定資料集\(T={(x_i,y_i)}\)，有對數似然函數

    

  • 其對w的對每一項梯度值為

    

• 通過上面的線性泊松回歸求出使用者對該興趣點的浏覽頻次的期望\(\lambda_{view}\)和點選頻次的期望\(\lambda_{click}\)，使用者i對類别k的CTR計算方法

  

3.2.2 非監督行為定向

• 将使用者向量化表示
  • 基于item的向量表示法、基于query的向量表示法
  • 向量化後，行為定向問題模組化成經典的聚類問題。

3.3 行為定向

• 按照使用者的曆史行為，進行廣告推薦。使用者的行為在不同類型的廣告系統中有不同定義。

3.4 推薦系統

3.4.1 基于使用者的協同過濾算法

• 想知道使用者n對電影m的評分，需要參考與使用者n相似的其他使用者，用他們對m的評分來拟合n對m的評分\(r_{nm}\)。對于給定使用者\(n\)，他打過分的電影集合是\(M_n\)，那麼\(n\)的平均得分是\(r_n=\frac{1}{|M_n|}\sum_i^{\in}r_{ni}\)，使用者n對電影m的評分可以通過如下公式計算，

  

  • \(U_n\)表示與n相似的使用者集合，\(s_{uv}\)表示使用者u和v之間的相似度，\(z_n\)是相似度平滑因子，\(z_n=\sum_i^{\in}|s_{uv}|\)。
  • 如何定義與n相似的使用者集合，用什麼方法衡量使用者之間相似度，根據具體應用不斷調試。

3.4.2 基于單品的協同過濾算法

• 用相似單品的得分來計算\(r_{nm}\)，計算方法如下

• \(s_{im}\)表示電影i同電影m的相似度，與基于使用者的協同過濾算法相同，該相似度也需要根據具體應用不斷調試。該算法需要使用者有充足行為，當使用者行為比較稀疏，難以給出準确預估結果。

3.4.3 奇異值分解SVD

• 希望将資料次元降低，實作某種程度上的聚合。
• 将資料聚內建K個隐藏類，原始矩陣R可被分解成兩個矩陣乘積形式\(R_{nm}=W_{nk}V_{km}\)，\(w_{nk}\)表示使用者n對k類型電影的興趣度，\(v_{km}\)表示電影m屬于k類型電影的隸屬度。
• 線性代數中，任何一個實矩陣R可分解為\(R=U\sum P^T\)
  • \(\sum\)是K*K的對角線矩陣，\(K\)為矩陣R的秩，對角線上每個元素為\(RR^T\)矩陣特征值的平方根。
  • U是N*K的矩陣，每一列是矩陣\(RR^T\)的特征向量。
  • \(P^T\)為K*M的矩陣，P中每一列是矩陣\(A^TA\)的特征向量。
• 去除\(\sum\)中絕對值較小的特征值，并在U和P中除去其對于的特征向量使得

  

  ，進而達到降維目的，使得R計算高效。
• 實際推薦系統，除了使用SVD方法求得W和V以外，另一種方法令\(\hat{R}=WV\)，最小化\(\hat{R}\)和R的差異，求解出最優W和V。損失函數是

  

  • 

3.5 定向排序

• 定向廣告排序和搜尋廣告排序機制基本相同，cpc收費下，兩者按照ecpm進行排序。計算ecpm最重要因素是對廣告進行ctr預估。
• 搜尋廣告的ctr預估一般是單模态模型，而定向ctr預估可看作是多模态模型，如何融合不同定向方式也是多模态學習的難點。

3.6 實踐一：定向廣告算法架構

• 定向廣告解決“這樣一個人”應該配"什麼樣的廣告"？
• 定向廣告要素

  

• 第一步根據使用者曆史行為，標明一批使用者的意圖，并找到對應的廣告。
  • 推薦系統（利用使用者曆史行為）
  • 利用使用者屬性方法（人口統計學）
  • 利用标簽方法
• 第二步根據這些廣告，進行排序。
  • 如果考慮點選率就是做\(<user,ad>\)點選率預估，獲得打分。
  • 采用ecpm進行排序\(ecpm=ctr*bidprice\)

  

3.7 實踐二：定向廣告的平衡之道

• 關于使用者疲勞
  • 針對頻繁通路的使用者
  • 針對通路次數稀疏，興趣點轉換很慢的使用者
  • “一次性”的類型興趣
  • “連續型”的類型興趣
• 關于多樣性
  • 給使用者選擇的餘地
  • 首先保證召回率，然後根據候選集進行進一步選擇，保證底線。
• 關于多目标
  • 除了CTR，還有ROI、CVR
  • 多名額線性融合\(rankscore=ctr*roi*bidprice\)
  • 對ROI好的創意篩選再利用\(rankscore=ctr*bidprice\)
• 關于E&E（搜尋和探索）
  • 如何給新加入的廣告和冷廣告展現的機會。

第四部分 實時廣告競價

• 實時廣告競價：建立一種流量交換的協定，使得媒體和廣告聯盟向全網範圍的廣告主提供尚未出售的流量，廣告主和廣告聯盟實作合作共赢。

4.1 基本概念

• 技術核心
  • 将實時産生的展示廣告流量及相關特征如客戶資訊、廣告位資訊推送給每個感興趣的購買者，并且搜尋出回報協定。
  • 對推送流量的價值進行實時評價并給出具體CPM出價的方法。
• 三類角色
  • 廣告交易市場AdExchange：實時廣告競價中流量進行實時交易的平台。
  • 需求方平台DSP：廣告交易市場中的買方。
  • 供應方平台SSP：廣告交易市場中的賣方。

  

4.2 廣告交易市場

4.2.1 曆史與現狀

• Mike Walrath創辦Right Media，與Double Click、AdECN三足鼎立，随後被Yahoo收購。
• 2007年廣告交易市場元年
• 2009年，實時廣告競價
• 2011年9月，阿裡巴巴TANX平台

4.2.2 實時廣告競價

• 線下部分：競價交易各參與者之間實作使用者ID互相轉換和對應，即Cookie Mapping。
• 線上部分：處理廣告請求到來時的競價和投放過程。

  

4.2.3 Cookie Mapping

• 使用cookie累計使用者再網際網路上的行為資料。
• 實時競價時，使用者資訊不能共享給第三方，于是隻将使用者辨別再競價請求中提供給流量需求方。Cookie Mapping是解決各網際網路公司辨別不一緻的标準方案。

4.2.4 實踐1 典型的廣告交易市場架構

• 圍繞核心的流量交換引擎，有三個重要子系統：
  • 業務系統：為需求方和供給方提供接入共給交易市場的接口。
  • 财務系統：提供安全、高效的财務結算功能
  • 資料系統：對交易過程中産生的資料進行記錄、處理
  • 流量交換引擎：實時廣告競價體系的核心。

第五部分 廣告系統架構及挑戰

5.1 廣告系統的特點

1. 高性能
2. 海量資料和存儲
3. 可運維性

5.2 功能職責劃分

1. 廣告業務系統
2. 廣告投放引擎
3. 廣告效果檢測系統
4. 廣告防作弊和結算
5. 資料平台和算法

5.3 大型廣告系統采用的技術

1. 高性能廣告投放引擎
2. 基于Hadoop的資料平台：分布式計算架構
3. CDN
4. 關系資料庫
5. J2EE或LAMP應用開發架構
6. 負載均衡
7. 服務化
8. 消息中間件

後記

• 資料管理平台DMP：Data Management Platform

  

• DMP在4個階段保證資料安全性

• DMP允許外部資料挖掘引擎接入，産生不同的資料分析結果，供不同的應用方使用