CTR預估[三]: Algorithm-LR and Regularization

01-25

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

時間：2017年11月

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

在<上一篇>中，我們簡單介紹了Naive LR。在工業界，單純使用Naive LR從效果上來說經常會顯得力不從心，而regularization的加入大大提升了LR的效果和應用範圍。本節我們將深入regularization的內涵和外延。

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

1.1.4 Naive LR and Regularization

1.1.4.1 Regularization

正則化（regularization）是對過大權重的一種懲罰。它的目的是避免某些權重有特別高的幅度，在模型中佔據完全的主導地位。

從貝葉斯學派的角度看，正則化等價於對模型的參數設定一個先驗（Prior）：

$egin{split} ~~~~~~~~~~~~~~~~~~~~argmax_w P(w|x,y) &= argmax_w P(y|x;w) · P(w) \ &propto argmax_w underbrace{prod_i P(y^{(i)}|x^{(i)};w)}_{likelihood} · underbrace{e^{-C||w-w_0||_k}}_{regularization}\ &propto argmax_w underbrace{sum_i log P(y^{(i)}|x^{(i)};w)}_{log\_likelihood} -underbrace{C||w-w_0||_k}_{regularization} end{split}$

加入正則項的loss function可以看做「likelihood項」和「正則項」的競爭：

正則項將特徵 $omega$ 拉向某個初始值 $w_0$ （通常是0）；
likelihood項儘可能使特徵擬合訓練數據。

模型擬合的結果，是對兩者的一種權衡（trade-off）。

注意：不同的資料中對於likelihood/fitting項，loss項和regularization項的描述會混用：
$egin{split}~~~~~~~~~~~~~~~~~~~~ &~~~~argmax_w P(w|x,y) \ &propto argmax_w log\_likelihood &- regularization\ &= argmin_w loss &+ regularization\ end{split}$
loss項一般是「負」log_likelihood項，需要注意正則項的符號。

likelihood項和樣本量是有關係的，但正則項和樣本是沒有關係的。因此，樣本量小的時候(<C)，正則項的作用更明顯。這和直觀理解是一致的：樣本量小的時候，更傾向於使用先驗，而樣本量大的時候更傾向於使用樣本擬合後驗。

俗話說凡事過猶不及。當正則化項過大之後，特徵的表達力會不足，training error & test error 都會提高。因此，需要仔細設計正則項的參數。

注意，有些地方使用拉格朗日問題
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~min Loss ~~~ s.t. ||w|| <= eta$
來替代原問題
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~min Loss + C||w||$
這是因為滿足KKT條件的原問題和拉格朗日問題的解一致，且 $eta$ 為定值。

1.1.4.2 L1-Norm, L2-Norm and Elastic Net

最常見的正則化是L1和L2正則。如果同時存在L1-Norm和L2-Norm則稱作Elastic Net：

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~hat{w} = arg min_w f(x;w) + lambda_1 ||w||_1 + lambda_2 ||w||^2$

$lambda_1 、lambda_2$ 分別為L1-Norm和L2-Norm的正則係數。

1.1.4.2.1 正則的直觀理解

上圖中以兩個特徵的LR模型為例，兩個特徵的參數分別是 $w_1$ 和 $w_2$ 。藍色線表示Loss的等高線，一圈代表相同的一個loss值，圓心就是樣本觀測值（假設一個樣本），半徑就是誤差值，受限條件就是紅色邊界（就是正則化部分）。

由於正則項是一個定值，紅色邊界在單次優化過程中固定不變；目標是最小化loss，也就是希望最優點 $w^*$ 到藍色等高線的中心的半徑最小。這種情況下，紅圈和藍圈交界處為最優解。注意到L1的最優參數(相比L2)更可能在坐標軸上，因此就會出現某個參數權重為0，最終使得模型稀疏。

隨著正則係數的變化，會出現什麼情況呢？

我們先來看L1正則，圖中的藍色contour依然是loss等高線，這裡只畫出了L1正則的第二象限，剩下三個象限的情況和上圖是一致的，只是簡練起見省掉了；在正則係數較小的時候，相當於正則形成的平面較大，loss和正則形成的平衡點在正則的「邊」上，如下圖最外側線上的紅點；隨著正則係數的增大，正則形成的平面越來越小，loss和正則形成的平衡點則會落在「角"上；正則係數進一步增大，loss和正則形成的平衡點依然在「角」上；

這裡演示的是一個2維的情形，此時只有4個角，當維度升高時候，菱形的正則平面變成一個高維的「菱形」，有非常多的角，因此有更多的更高的概率，會有特徵的權重為0；

隨著正則係數的增大，有更多的係數變為0；不同特徵係數和正則係數的關係叫做「pathway」(註：實際橫軸並非正則係數，而是正則係數的變形，但並不因影響序的關係而影響結論),如下圖；

上圖為L1的pathway樣例，左側的正則係數最大，右側的正則係數最小；最右側相當於沒有正則，隨著正則係數的增大，更多的權重被正則為0；

但L2正則的情形則不同，隨著正則係數的增加，最優點只會在loss contour的圓心和坐標原點的連線上移動，如下圖中，從外側的紅點逐漸過渡到內側的紅點，但並不會改變原先係數的稀疏性

Elastic Net的情況介於L1和L2之間：

註：上圖中的elastic net圖示需 $lambda_1 == lambda_2$ 。

正則的「尖角」和「圓角」

從上圖我們觀察到，L1正則和坐標軸的交接點是一個連續不可導的「尖角」，而L2正則則是一個圓弧狀的「圓角」。

在比較「尖角」和「圓角」前，先看下不同norm階的圖示：

Elastic Net也是有「尖角」的，如何理解呢？如果只有一個參數 $omega$ :

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~reg = lambda_2||w||^2 + lambda_1||w||_1=left{ egin{split} lambda_2w^2 + lambda_1w ~~~~ if ~w geq 0 \ lambda_2w^2 - lambda_1w ~~~~ if ~w < 0 end{split} ight.$

從幾何上相當於兩個拋物線在0點相交，因此其交角是一個「尖角」。

我們再看下和elastic net長相非常相似的L1.2：

雖然相似，但elastic net是尖角，L1.2是圓角。

尖角和圓角可以認為正則性質的直觀展示：

對於稀疏性（sparsity），尖角是必須的；
對於聚組性（grouping），需要嚴格凸的邊保證權重「連續」，從而保證相似的feature獲得相似的權重。

1.1.4.2.2 正則的先驗分布理解

上一節提到，正則化等價於給參數加了一個先驗prior：

L1-Norm等價於假設先驗分布為拉普拉斯分布： $p(W) sim Laplace$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~w sim mathcal{C}e^{-lambda|mathbf{w}|}$

L2-Norm等價於假設先驗分布為高斯分布： $p(W) sim Gaussian$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~w sim mathcal{N}(0, alpha I)$

Elastic Net則等價於設置複雜先驗：

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~w sim mathcal{C}(lambda, alpha)e^{-lambda|mathbf{w}|_1+ alpha|mathbf{w}|_2}$

（事實上，三個先驗中exp前面的係數並不需要關心。）

這種等價性可以推導。以L1為例：

$egin{split}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ p(w) &= prod_{j=1}^n frac1{2b} exp left( - frac{ |w^{(j)})| }{b} ight)\ &= left(frac1{2b} ight)^n exp left( - frac{ sum_{j=1}^n |w^{(j)})| }{b} ight)\ &propto exp left( - frac{1}{b} ||w||_1 ight) end{split}$

與上一節的公式進行比較，可以發現這裡的 $frac{1}{b}$ 和上一節中的 $C$ 表示相同的意思，只是換了一個符號。對於L2-Norm和Elastic Net的推導是類似的，原先prior的係數被另外的正則係數 $lambda_1 、lambda_2$ 取代。

總結並對比一下L1和L2正則，如下表：

注意：無論是哪一種regularization, 對於LR，都是不對bias項 $omega_0$ 進行正則的。
直觀理解：如果 $w_0$ 也進入正則，則正則係數的選取會影響y的真實分布擬合。
事實上，如果不考慮映射變換 $sigma(·)$ ， $w^Tx$ 這組參數構成的線性平面是在擬合 $y -b$ 這個線性平面。

bias項的用處很多，後面章節我們再展開。

1.1.4.3 L1, L2, Elastic Net 針對冗餘特徵處理的區別

這裡我們來舉個例子，說明共線性特徵在L1, L2正則下的區別。

假設用三個特徵去擬合 $y$ ,即 $y = w_1x_1 + w_2x_2 + w_3x_3$ ，其中 $x_3 = kx_2$ , $|x_1|= |x_2| = 1$ ; $k$ 為係數且 $kgeq1$ ：

圖中明顯縱向只能用 $x_1$ 擬合，即 $w_1=1$ ；橫向的需要 $x_2, x_3$ 兩個來共同擬合，即 $w_2+kw_3=1$ 。我們知道最終目標是 min regularization，即

如果L1正則：

$egin{split} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~reg &= |w_2| + |w_3| \ &= |w_2| + frac1k |1-w_2| end{split}$
最優值 $w_2=0; w_3=frac1k$ ; 最優 $reg=frac1k$

如果L2正則：

$egin{split}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ reg &= w_2^2 + w_3^2 \ &= w_2^2 + (frac{1-w_2}k )^2\ &= frac1{k^2}left[(k^2+1)w_2^2-2w_2+1 ight] end{split}$
最優值 $w_2=frac1{k^2+1}; w_3=frac{k}{k^2+1}$ ; 最優 $reg=frac1{k^2+1}$

從數據對比我們發現：

L1正則產生稀疏解，並且優先保留權重更小的feature；可以引申，如果兩個特徵完全相同，會隨機保留一個；
L2正則會保留特徵權重的共線性，也就是共線性的特徵根據本身的特徵強度而被「加權平分」了。

這個性質在什麼時候有用呢？我們看下面的例子：

利用基因檢測是否會罹患白血病。樣本總數 sample = 60，基因特徵數 #(gene feature) = 1W；這是典型的樣本數(n)<<特徵數(p)問題。

針對 n << p 問題，L1和L2正則分別會得到什麼結果？

L1 會從高相關性的feature group中選一個。

這會帶來可解釋性問題，相同pathway的feature只會保留一個，其餘特徵權重會置為0。
如果n << p，最多只會保留n個feature。

L2 會聚合高相關性的feature group -- 相似的特徵獲得相似的權重，稱作 grouping effect；

但沒有L1的稀疏解；幾乎所有有效特徵都會擁有非0權重。

可以看到，兩者各有優勢。而Elastic Net的出現結合了兩者的優勢。

Elastic Net目的：解決高相關性feature選擇問題。其優勢在於：

保留了L1正則的稀疏性；
保留了L2正則的二次項penalty：

去掉了L1正則中選擇n == p的限制；
保留了grouping effect；
比L1正則穩定。

附上三種正則方法的pathway比較：

其中

橫軸為正則係數大小。向左正則項越強，向右越弱；
縱軸為coefficient。在LR中即為模型給予某個特徵的權重；
紅色垂線為調參最優的正則係數。

1.1.4.4 Naive LR and regularization

Hastie曾經提出稀疏性問題中的「Bat on sparsity」原則：

Use a procedure that does well in sparse problems, since no procedure does well in dense problems.

理論上，在有的問題中用L2正則可能更好，但沒有足夠的數據可以供演算法學出極大量的非0係數；而在L1正則中，沒有那麼多的係數需要學習，很多的係數已經是0了。

對於工業界而言，L1-LR是最常用的組合手段。在線上CTR系統中，user等信息one-hot編碼之後會產生巨量特徵，而其中大部分特徵並沒有很強的表達能力。加入L1正則事實上起到了feature selection的作用。

另外，解更稀疏意味著模型更小，更小的模型意味著線上serving時會有更快的計算，以及可以支持更高的QPS。這也是線上模型設計的一個重要考慮因素。

當然，為了提升模型效果，有時也可選用Elastic Net；但僅使用L2正則的情況較少。

下節預告：
本節我們介紹了Naive LR和LR的正則化，包括L1正則、L2正則和Elastic Net的定義、區別和適用場景。在CTR預估中，有另外一個點運用較多：偏差項（bias，b），下一節，主要來說偏差項bias對於預估的高估/低估的影響，以及對於CTR預估中的校準應用。
敬請期待：CTR預估[四]: Algorithm-LR Bias和Q分布

系列目錄傳送門見 -- CTR預估系列一覽表
LR相關章節關係和傳送門如下：

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