點擊率預估是廣告技術的核心演算法之一，它是很多廣告演算法工程師喜愛的戰場。一直想介紹一下點擊率預估，但是涉及公式和模型理論太多，怕說不清楚，讀者也不明白。所以，這段時間花了一些時間整理點擊率預估的知識，希望在盡量不使用數據公式的情況下，把大道理講清楚，給一些不願意看公式的同學一個Cook Book。
點擊率預測是什麼？
- 點擊率預測是對每次廣告的點擊情況做出預測，可以判定這次為點擊或不點擊，也可以給出點擊的概率，有時也稱作pClick。
點擊率預測和推薦演算法的不同？
- 廣告中點擊率預估需要給出精準的點擊概率，A點擊率0.3% , B點擊率0.13%等，需要結合出價用於排序使用；推薦演算法很多時候只需要得出一個最優的次序A>B>C即可；
搜索和非搜索廣告點擊率預測的區別
- 搜索中有強搜索信號-「查詢詞(Query)」，查詢詞和廣告內容的匹配程度很大程度影響了點擊概率； 點擊率也高，PC搜索能到達百分之幾的點擊率。
- 非搜索廣告（例如展示廣告，資訊流廣告），點擊率的計算很多來源於用戶的興趣和廣告特徵，上下文環境；移動資訊流廣告的螢幕比較大，用戶關注度也比較集中，好位置也能到百分之幾的點擊率。對於很多文章底部的廣告，點擊率非常低，用戶關注度也不高，常常是千分之幾，甚至更低；
如何衡量點擊率預測的準確性？
AUC是常常被用於衡量點擊率預估的準確性的方法；理解AUC之前，需要理解一下Precision/Recall；對於一個分類器，我們通常將結果分為：TP,TN,FP,FN。
本來用Precision=TP/(TP+FP)，Recall=TP/P，也可以用於評估點擊率演算法的好壞，畢竟這是一種監督學習，每一次預測都有正確答案。但是，這種方法對於測試數據樣本的依賴性非常大，稍微不同的測試數據集合，結果差異非常大。那麼，既然無法使用簡單的單點Precision/Recall來描述，我們可以考慮使用一系列的點來描述準確性。做法如下：
- 找到一系列的測試數據，點擊率預估分別會對每個測試數據給出點擊/不點擊，和Confidence Score。
- 按照給出的Score進行排序，那麼考慮如果將Score作為一個Thresholds的話，考慮這個時候所有數據的 TP Rate 和 FP Rate； 當Thresholds分數非常高時，例如0.9，TP數很小，NP數很大，因此TP率不會太高；
4. 當選用不同Threshold時候，畫出來的ROC曲線，以及下方AUC面積。
5. 
6.
7. 我們計算這個曲線下面的面積就是所謂的AUC值；AUC值越大，預測約準確。
為什麼要使用AUC曲線
既然已經這麼多評價標準，為什麼還要使用ROC和AUC呢？因為ROC曲線有個很好的特性：當測試集中的正負樣本的分佈變化的時候，ROC曲線能夠保持不變。在實際的數據集中經常會出現類不平衡（class imbalance）現象，即負樣本比正樣本多很多（或者相反），而且測試數據中的正負樣本的分佈也可能隨著時間變化。AUC對樣本的比例變化有一定的容忍性。AUC的值通常在0.6-0.85之間。
如何來進行點擊率預測？
點擊率預測可以考慮為一個黑盒，輸入一堆信號，輸出點擊的概率。這些信號就包括如下信號
**廣告：**歷史點擊率，文字，格式，圖片等等
**環境：**手機型號，時間媒體，位置，尺寸，曝光時間，網路IP，上網方式，代理等
**用戶：**基礎屬性（男女，年齡等），興趣屬性（遊戲，旅遊等），歷史瀏覽，點擊行為，電商行為
信號的粒度：
Low Level : 數據來自一些原始訪問行為的記錄，例如用戶是否點擊過Landing Page，流量IP等。這些特徵可以用於粗選，模型簡單，
High Level: 特徵來自一些可解釋的數據，例如興趣標籤，性別等
特徵編碼Feature Encoding：
- **特徵離散化：**把連續的數字，變成離散化，例如溫度值可以辦成多個溫度區間。
- 特徵交叉： 把多個特徵進行叫交叉的出的值，用於訓練，這種值可以表示一些非線性的關係。例如，點擊率預估中應用最多的就是廣告跟用戶的交叉特徵、廣告跟性別的交叉特徵，廣告跟年齡的交叉特徵，廣告跟手機平台的交叉特徵，廣告跟地域的交叉特徵等等。
特徵選取（Feature Selection）：
特徵選擇就是選擇那些靠譜的Feature，去掉冗余的Feature，對於搜索廣告Query和廣告的匹配程度很關鍵；對於展示廣告，廣告本身的歷史表現，往往是最重要的Feature。
獨熱編碼（One-Hot encoding）
假設有三組特徵，分別表示年齡，城市，設備；
[“男”, “女”]
[“北京”, “上海”, “廣州”]
[“蘋果”, “小米”, “華為”, “微軟”]
傳統變化： 對每一組特徵，使用枚舉類型，從0開始；
["男「，」上海「，」小米「]=[ 0,1,1]
["女「，」北京「，」蘋果「] =[1,0,0]
傳統變化后的數據不是連續的，而是隨機分配的，不容易應用在分類器中。
熱獨編碼是一種經典編碼，是使用N位狀態寄存器來對N個狀態進行編碼，每個狀態都由他獨立的寄存器位，並且在任意時候，其中只有一位有效。
["男「，」上海「，」小米「]=[ 1,0,0,1,0,0,1,0,0]
["女「，」北京「，」蘋果「] =[0,1,1,0,0,1,0,0,0]
經過熱獨編碼，數據會變成稀疏的，方便分類器處理。
點擊率預估整理過程：
三個基本過程：特徵工程，模型訓練，線上服務
特徵工程：準備各種特徵，編碼，去掉冗余特徵（用PCA等）
模型訓練：選定訓練，測試等數據集，計算AUC，如果AUC有提升，通常可以在進一步在線上分流實驗。
線上服務：線上服務，需要即時計算CTR，即時計算相關特徵和利用模型計算CTR，對於不同來源的CTR，可能需要一個Calibration的服務。
點擊率預測的演算法
-邏輯回歸(Logic Regression)：
Logistic回歸是點擊率預估必須入門的一種方法，使用簡單，理論容易理解，甚至有些問題可以進行Debug，了解問題原因。它的核心想法就是通過Sigmooid函數，將Y值轉化成0-1；其基本公式如下：
LR_SGD(隨機梯度下降):
LR的模型有了，在訓練過程中，為了提高訓練的速度，常用的是SGD的優化方法。 SGD解決了梯度下降的兩個問題： 收斂速度慢和陷入局部最優。梯度下降是一種常規的優化方法，但是SGD的S表示一定的隨機性；梯度下降是每次都朝著全局優化方向前進，而SGD卻由於隨機性，有一定的曲折后，可能達到全局最優，也可能深陷於局部最優，但SGD的運行性能確實出色。
LR-FTRL
Google點擊率預估在在線學習(Online Learning)積累好多年的經驗，所謂在線學習就是通過線上即時處理數據而進行模型訓練，而不是傳統模式，把所有數據都放到一起處理(Batch Learning)，得到離線的最優解。
LR-FTRL (Follow-the-regularized-Leader)，Google在10年就提出了一些理論基礎，在13年給出了Paper，並且帶有FTRL的實現偽程式碼，在此之後，FTRL才大規模應用在工業界。
-FM(Factorization Machines)：
Steffen Rendle于2010年提出Factorization Machines（FM），併發布開放原始碼工具libFM。憑借這單個模型，他在KDD Cup 2012上，取得Track1的第2名和Track2的第3名。在Kaggle的主流的點擊率比賽中和實際廣告系統的經驗，factorization machine的效果完勝LR。FM的內核和LR也非常類似，但是多增加了一部分引入特徵之間的交互因素，所以FM是非線性函數內核，它非常類似我們在特徵工程中採用的特徵交叉，但是FM是通過訓練找到那些有用的特徵叉值。
深度學習DNN
深度學習採用神經網路技術也在不斷影響點擊率技術的發展。特別是DNN的開發平台，更多的廣告和用戶數據，更大的計算資源（包括GPU），這都給深度學習解決點擊率預估的問題，奠定了好的基礎。
Google、百度等搜索引擎公司以 Logistic Regression（LR）作為預估模型。而從 2012 年開始，百度開始意識到模型的結構對廣告 CTR 預估的重要性：使用扁平結構的 LR 嚴重限制了模型學習與抽象特徵的能力。為了突破這樣的限制，百度嘗試將 DNN 作用於搜索廣告，而這其中最大的挑戰在於當前的計算能力還無法接受 10^11 級別的原始廣告特徵作為輸入。作為解決，在百度的 DNN 系統里，特徵數從10^11 數量級被降到了10^3，從而能被 DNN 正常地學習。這套深度學習系統已於 2013 年 5 月開始上線服務於百度搜索廣告系統，初期與LR並存，後期通過組合方法共同提升點擊準確率。
現在越來越多的深度學習的平台，例如Google的TensorFlow，使用起來也非常方便，大部分工程師1-2星期就可以上手實驗，對於特徵工程的要求沒有LR高，DNN能夠對特徵進行自主的優取，但是對於大規模的計算，能夠直接匹敵LR演算法的，還需要一段長長的時間。
整合學習（Ensemble Learning）
整合學習通過訓練多個分類器，然後把這些分類器組合起來使用，以達到更好效果。整合學習演算法主要有Boosting和Bagging兩種類型。
Boosting：通過疊代地訓練一系列的分類器，每個分類器採用的樣本的選擇方式都和上一輪的學習結果有關。比如在一個年齡的預測器，第一個分類器的結果和真正答案間的距離（殘差），這個殘差的預測可以訓練一個新的預測器進行預測。XGBoost是非常出色的Boosting工具，支持DT的快速實現。
Bagging：每個分類器的樣本按這樣的方式產生，每個分類器都隨機從原樣本中做有放回的採樣，然後分別在這些採樣后的樣本上訓練分類器，然後再把這些分類器組合起來。簡單的多數投票一般就可以。這個類別有個非常著名的演算法叫Random Forest,它的每個基分類器都是一棵決策樹，最後用組合投票的方法獲得最後的結果。
各大公司的一些點擊率預估的演算法：
- **微軟 ：**微軟在２０１０年曾經有一篇文章是關於使用《Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft』s Bing Search Engine 》，但這並不代表這是微軟現在的技術，據說現在的技術也是Online-learning和一些組合技術的融合，另外也在嘗試DNN的解決方案。
- **Google：**Google是比較開放的公司，LR-FTRL對整個行業的online-learning都有整體的促進作用。《Ad Click Prediction: a View from the Trenches》，Google內部也在不斷嘗試引入深度學習方法解決點擊率問題，也包括展示廣告的點擊率預估。
-
Facebook:
Facebook廣告大部分情況下是沒有關鍵詞的，因此Facebook的點擊率預估，其實是非常更難的問題。Facebook有一篇文章，《Practical Lessons from Predicting Clicks on Ads at Facebook》，其仲介紹Facebook結合GBDT訓練出一些feature，然後再傳入LR進行分類；
**百度：**基本全面使用DNN的訓練和之前的一些LR；
**小米：**小米使用過多種方法，包括LR-SGD, LR-FTRL, FM等，同時也在通過組合的方式提升綜合效果，另外也在積極探索DNN的解決方案。
點擊率預測的成功要素
點擊率預估的成功來源於兩面：一面是實力，一面是運氣，加油和好運！
作者簡介：
歐陽辰，互聯網廣告技術老兵，小米MIUI架構師/主管，負責廣告平台架構和數據分析平台，曾負責微軟移動Contexual Ads廣告平台，參與Bing搜索引擎IndexServe的核心模塊研發
數據分析
廣告技術