CTR預估[二]: Algorithm-Naive Logistic Regression

01-25

作者：@三瘋蘭尼斯特 && @Ainika Peng

時間：2017年11月

出處：https://zhuanlan.zhihu.com/p/31503716

CTR 預估模型側最簡單也是最常作為baseline的模型是Logistic Regression；常規說起來，LR是一個非常基礎且簡單的模型 -- 目標定義優雅，從幾率直接可推；但筆者工作這麼些年，見到很多做演算法的同學，對於LR理解深度不夠。很多策略運用、工程優化都是和LR的基礎理論息息相關的，所以筆者在此試圖把LR的內涵和外延盡量講清楚。能力有限之處，各位多多海涵。

在<上一篇>中，我們簡單介紹了CTR預估的概況以及主要求解思路，並提到了基礎的線性模型Linear Regression。下面我們基於這個模型進行一些拓展。

LR預計會講四個部分：

相關章節鏈接如下：

基礎的LR推導以及LR和統計的關係
正則化
Bias運用
到LR的Model擴展-MLR

系列目錄傳送門見 -- CTR預估系列一覽表

1.1 Logistic Regression

Logistic Regression與Linear Regression兩者本質上是一致的，都是用線性 $w^Tx$ 來逼近目標。但它們所逼近的目標不同：

$egin{split} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~y ~~~~~&= ~w^Tx &~~~~Linear~Regression \ logfrac{y}{1-y}~ &= ~w^Tx &~~~~Logistic~Regression end{split}$

如果說Linear Regression使用線性項 $w^Tx$ 逼近 $y$ ，那Logistic Regression就是用線性項 $w^Tx$ 逼近 $log(y/(1-y))$ 。或者換句話說

Logistic Regression 本質上是逼近真實正負比例的對數幾率（Log Odds）。

1.1.1 從Odds到Naive LR

舉一個例子：假設我們需要考慮暴露在某種環境中（exposed）這個因素對於罹患疾病（disease）這一觀察結果的影響。下表描述了是否暴露和是否得病之間的樣本關係：

定義Odds，即幾率，為一個事件發生概率和不發生概率的比例。對於exposed的odds為：

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~O_+ = frac{P[disease | exposed]}{1-P[disease | exposed]} = frac{p_1}{1-p_1} = frac{frac{a}{a+b}}{frac{b}{a+b}} = frac{a}{b}=2.5$

對於unexposed的odd為：

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~O_- = frac{P[disease | unexposed]}{1-P[disease | unexposed]} = frac{p_0}{1-p_0} = frac{frac{c}{c+d}}{frac{d}{c+d}} = frac{c}{d}=0.77$

然後定義exposed的Odds Ratio，幾率比：

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~OR=frac{frac{p_1}{1-p_1}}{frac{p_0}{1-p_0}}=3.25$

物理上的解釋為：exposed條件下相對於unexposed條件下獲得disease的「相對危險程度」達3.25倍。

在CTR預估場景中，我們如上相似地定義 $O_+$ ，即

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~O_+ = frac{P[click ~|~ impression]}{1-P[click ~|~ impression]} = frac{frac{|clk|}{|clk|+|not\_clk|}}{frac{|not\_clk|}{|clk|+|not\_clk|}} = frac{|clk|}{|not\_clk|}$

如果我們用線性項 $w^Tx$ 逼近它，得到的演算法稱之為Na?ve LR：

$egin{split} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~w^Tx &= log O_+ \ &= log frac{P[click ~|~ impression]}{1-P[click ~|~ impression]} \ &= log frac{|clk|}{|not\_clk|} end{split}$

而如果使用 $w^Tx$ 逼近的是y的Log Odds，得到的演算法則稱之為Logistic Regression。在這種演算法中，我們等價於使用 $w^Tx$ 的一個sigmoid函數映射來逼近 $y$ 。比起直接使用 $w^Tx$ 逼近 $y$ 來說，這樣做的好處是：對於大樣本量，Log Odds具有更好的漸進性 。換句話解釋，在 $w^Tx$ 很小或很大的時候， $y$ 隨 $w^Tx$ 的變化而變化的程度不大。

總結如下：

Naive LR可以理解為使用線性項 $w^Tx$ 逼近 $O_+$ ；
sigmoid函數可以理解為線性項 $w^Tx$ 和正樣本概率的關聯。

1.1.2 LR: Objective and Loss

一般而言，一個模型主要包括兩部分：

優化目標：即定義問題；也稱作Objective。與之強相關的概念是損失函數 Loss；
優化方法：即求解問題；一般機器學習中的問題會試圖轉化為凸函數求解。

本節我們基於LR模型，討論優化目標Objective。

LR的Objective基於如下建模方式，目的在於儘可能正確地使用樣本來預測label：

$egin{split} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~P(y=1~|~x;w) &= P[click ~~~~~~~~|~ impression] = f_w(x) = frac{e^{w^Tx}}{1+e^{w^Tx}} \ P(y=0~|~x;w) &= P[not\_click ~|~ impression] = 1 - f_w(x) = frac{1}{1+e^{w^Tx}} end{split}$

其中， $w$ 為權重， $(x^{(i)},y^{(i)})$ 為一條樣本的特徵和label。

我們將其合併，得到等價表示：

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~P(y~|~x;w) = left(f_w(x) ight)^yleft(1-f_w(x) ight)^{1-y}$

我們定義似然函數（likelihood）為取某一個 $w$ 時，使用 $x$ 作為輸入能得到 $y$ 的概率：

$egin{split} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~L(w) &= prod_{i=1}^m P(y^{(i)}~|~x^{(i)};w) \ &= prod_{i=1}^m left(f_w(x^{(i)}) ight)^{y^{(i)}}left(1-f_w(x^{(i)}) ight)^{1-y^{(i)}} end{split}$

由於我們拿到了一些樣本，我們的目標自然可以定為：尋找參數 $w$ ，使得對於輸入的特徵 $x$ 而言，出現輸入的label $y$ 的概率最大；即：真實情況發生的概率最高。在這裡我們基於的是頻率學派的假設，即參數 $w$ 是一個待被發現的確定值，而非一個隨機變數。

對似然函數兩邊取對數，得到對數似然函數（log-likelihood）為：

$egin{split}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ l(w) &= log L(w) \ &= sum_{i=1}^m {y^{(i)}} log f_w(x^{(i)}) + (1-y^{(i)}) log left(1-f_w(x^{(i)}) ight) end{split}$

LR的目標函數Objective即為最大化log-likelihood：

$egin{split} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Obj &= max_w L(w) \ &propto max_w l(w) \ &= max_w sum_{i=1}^m {y^{(i)}} log f_w(x^{(i)}) + (1-y^{(i)}) log left(1-f_w(x^{(i)}) ight) \ &= min_w sum_{i=1}^m - {y^{(i)}} log f_w(x^{(i)}) - (1-y^{(i)}) log left(1-f_w(x^{(i)}) ight) end{split}$

對應地，損失函數Loss為：

$egin{split} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Lossleft( f_w(x^{(i)}), y^{(i)} ight) &= - {y^{(i)}} log f_w(x^{(i)}) - (1-y^{(i)}) log left(1-f_w(x^{(i)}) ight) \ &= left{ egin{aligned} - log f_w(x^{(i)}) ~~~ if ~ y =1\ - log (1-f_w(x^{(i)})) ~~~ if ~ y =0 end{aligned} ight. end{split}$

畫成圖示即下圖。可以看到，在樣本對label判斷錯誤之後，loss急速增加。

1.1.3 Naive LR和統計的關係

舉一個CTR預估場景中的例子：3個素材ad展示在2個位置pos上。下左圖表示只考慮位置pos作為特徵的情況，下右圖表示同時考慮pos和ad_id作為特徵的情況。

如果只考慮pos作為特徵，pos=1的樣本和pos=2的樣本並無什麼關係。如果用Naive LR建模，和直接統計本質上沒有區別：如果數據量充分，則後驗統計：

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~poCTR_{pos1} = sigma(w_{pos1} + b )$

如果假設bias項為0，那統計值和LR權重之間，只差一個logit變換。

如果同時考慮pos和ad_id兩個特徵，類似用上右圖進行訓練。假設有新的ad_id=4在pos=1展示，則新的ad_id=4的權重可以類比於條件概率：

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~p(ad\_id=4) = frac{p(ad\_id=4, pos=1)}{p(pos=1)}$

LR的訓練可以類比這個過程，即考慮特徵之間的correlation。

下表為統計做法和單field計算Na?ve LR的做法比較：

可以看出，歷史統計poCTR本質上等價於單特徵類field作為特徵計算LR：

但單純統計poCTR或者單field做LR沒有考慮feature之間的correlation：

Na?ve LR可以理解為使用線性項特徵的統計方法。進一步地，全局計算LR的weight就是考慮全特徵correlation的embedding方法。

下節預告：

本節主要介紹Naive LR。對於工業界來說，LR系的演算法提供了很好的baseline，但單純使用Naive LR從效果上來說有時會顯得力不從心。Regularization的加入大大提升了LR的效果和應用範圍。下面一節我們將深入regularization的內涵和外延：

敬請期待：CTR預估[三]: Algorithm-LR and Regularization