yangliang @ Maan Coffee

離開(kāi)人人時(shí)，寫(xiě)過(guò)2篇文章，工作總結(jié) 以及 LR算法 的總結(jié)。這個(gè)周末和占空溝通了下LR，覺(jué)得有一些新的東西自己之前不知道，有必要再次總結(jié)下，于是有了這篇文章。

文章會(huì)詳細(xì)介紹LR算法在廣告點(diǎn)擊率預(yù)估上的使用，包括線下數(shù)據(jù)處理，模型訓(xùn)練，線上服務(wù)等。我們就先從DSP背景講起。

0 DSP背景介紹

幫助中小廣告主投放廣告，對(duì)接Ad Exchange獲取流量，參與實(shí)時(shí)競(jìng)價(jià)，從中賺取差價(jià)。

廣告引擎負(fù)責(zé)直接對(duì)接Ad Exchange，并從廣告庫(kù)初步挑選廣告列表。然后實(shí)時(shí)問(wèn)詢(xún)策略組各廣告競(jìng)價(jià)價(jià)格。

策略組根據(jù)用戶(hù)信息、廣告信息、上下文場(chǎng)景信息來(lái)出價(jià)。出價(jià)主要涉及2個(gè)方面：競(jìng)價(jià)策略和CTR預(yù)估，這次我們主要討論的就是CTR預(yù)估。

1 數(shù)據(jù)／特征提取

1.1 數(shù)據(jù)準(zhǔn)備

原始數(shù)據(jù)：請(qǐng)求／競(jìng)價(jià)／展示／點(diǎn)擊／轉(zhuǎn)化等數(shù)據(jù)

數(shù)據(jù)clean／merge：臟數(shù)據(jù)的clean／以及數(shù)據(jù)鏈條的merge，依據(jù)某些id字段(cookie mapping等技術(shù))

1.2 特征提?。▎翁卣鳎M合特征／轉(zhuǎn)化特征）

單特征示范：用戶(hù)性別
組合特征示范：廣告id＋廣告位id
轉(zhuǎn)化特征示范：url轉(zhuǎn)域名；年紀(jì)特征分段

關(guān)于特征離散化／組合／轉(zhuǎn)化的原因如下[知乎參考url]

特征組合／轉(zhuǎn)化原因：LR模型是線性模型，為刻畫(huà)y(CTR)和x變量的非線性關(guān)系，需對(duì)x做一些組合／轉(zhuǎn)化等。至于如何組合和轉(zhuǎn)化，這就是所謂的特征工程的事情。

特征離散化
－ 異常數(shù)據(jù)有很強(qiáng)的魯棒性，模型會(huì)更穩(wěn)定：比如一個(gè)特征是年齡>30是1，否則0。如果特征沒(méi)有離散化，一個(gè)異常數(shù)據(jù)“年齡300歲”會(huì)給模型造成很大的干擾；
－ 運(yùn)算快稀疏向量?jī)?nèi)積乘法運(yùn)算速度快，計(jì)算結(jié)果方便存儲(chǔ)，容易擴(kuò)展
－ 為模型引入了非線性，能夠提升模型表達(dá)能力，加大擬合

特征＋模型的權(quán)衡
李沐曾經(jīng)說(shuō)過(guò)：模型是使用離散特征還是連續(xù)特征，其實(shí)是一個(gè)“海量離散特征+簡(jiǎn)單模型” 同 “少量連續(xù)特征+復(fù)雜模型”的權(quán)衡。既可以離散化用線性模型，也可以用連續(xù)特征加深度學(xué)習(xí)。就看是喜歡折騰特征還是折騰模型了。通常來(lái)說(shuō)，前者容易，而且可以n個(gè)人一起并行做，有成功經(jīng)驗(yàn)
https://www.zhihu.com/question/31989952/answer/54184582

1.3 采樣

按照時(shí)間重采樣：近距離時(shí)間點(diǎn)數(shù)據(jù)重采樣

實(shí)踐中的數(shù)據(jù)規(guī)模

數(shù)據(jù)：七天pv/click＋當(dāng)天小時(shí)級(jí)數(shù)據(jù)
特征：十多個(gè)特征簇（憑經(jīng)驗(yàn)選擇：操作系統(tǒng)／瀏覽器／IP；廣告id／廣告素材等；廣告位id）
實(shí)際點(diǎn)擊率：千分1/2個(gè)點(diǎn)；較高的5-8個(gè)點(diǎn)
click每天w級(jí)別；pv每天kw級(jí)別；bind請(qǐng)求：十億級(jí)別

2 特征選擇

特征選擇評(píng)估指標(biāo)：模型AUC

常見(jiàn)特征選擇方法

• L1正則
• 計(jì)算皮爾遜系數(shù)和互信息系數(shù)（信息增益）
• 訓(xùn)練能對(duì)特征打分的預(yù)選模型：RandomForest和Logistic Regression等都能對(duì)模型的特征打分，通過(guò)打分獲得相關(guān)性后再訓(xùn)練最終模型；
  https://www.zhihu.com/question/28641663

之前我們采取的方法：前項(xiàng)特征簇選擇

3 LR算法

3.1 LR模型建立

極大似然建立模型；得到最優(yōu)化目標(biāo)函數(shù)
誤差滿(mǎn)足高斯分布的前提：極大似然 等價(jià) 最小二乘法

3.2 LR模型求解

LR模型的目標(biāo)函數(shù)是一個(gè)凸函數(shù)，求解凸問(wèn)題有很多通用的方法。針對(duì)大規(guī)模的LR，也有針對(duì)性的算法。

各種優(yōu)化算法的基本思路都是：尋找搜索方向以及計(jì)算最佳步長(zhǎng)。梯度法；牛頓法；BFGS／L-BFGS；OWLQN(LR帶L1正則)
梯度法：利用梯度信息尋找最速下降方向。利用平面去逼近原函數(shù)，一階收斂
牛頓法：利用Hessian矩陣尋找下降方向。利用二次曲面去逼近原函數(shù)，二階收斂。－Hessian逆矩陣，計(jì)算代價(jià)大
BFGS(最好的擬牛頓算法)：根據(jù)迭代的最近k步信息（函數(shù)值，梯度信息）來(lái)構(gòu)造Hessian矩陣的逆
L-BFGS：BFGS的空間復(fù)雜度是o(n^2)，此算法將空間復(fù)雜度降為o(n*k)
OWLQN(LR帶L1正則)：L1沒(méi)有梯度，于是提出次梯度的概念

擬牛頓法：采用一定的方法來(lái)構(gòu)造與Hessian矩陣相似的正定矩陣，而這個(gè)構(gòu)造方法計(jì)算量比牛頓法小

5 L1/L2正則深入理解

1. 好處：防止過(guò)擬合；L1產(chǎn)生稀疏解

2. 含義
似然函數(shù)一般是p（y|x,w)，在此基礎(chǔ)上乘上p(w)，就得到加入先驗(yàn)的模型，降低模型復(fù)雜度
L(w) ＝ p(y|X;w) * p(w)

假設(shè)原模型是殘差符合高斯分布的線性回歸
如果假設(shè)w符合高斯分布 -> L2范數(shù)
如果假設(shè)w符合拉普拉斯分布-> L1范數(shù)

先說(shuō)結(jié)論：誤差服從高斯分布的情況下， 最小二乘法等價(jià)于極大似然估計(jì)

從概率論的角度：
Least Square 的解析解可以用 Gaussian 分布以及最大似然估計(jì)求得
Ridge 回歸可以用 Gaussian 分布和最大后驗(yàn)估計(jì)解釋
LASSO 回歸可以用 Laplace 分布和最大后驗(yàn)估計(jì)解釋
https://www.zhihu.com/question/35322351

為什么 LR 模型要使用 sigmoid 函數(shù)？
滿(mǎn)足一些大前提條件下熵最大的解，有paper從最大熵角度證明。
這個(gè)和信息論中信息定義函數(shù)很相似，可以通過(guò)定義好的信息熵性質(zhì)求解得到信息的定義函數(shù)。
https://www.zhihu.com/question/35322351

6 其他

1. log loss損失函數(shù)／auc 表示含義
logloss更關(guān)注和觀察數(shù)據(jù)的吻合程度，AUC更關(guān)注rank order
https://www.zhihu.com/question/54009615

AUC：從排序的角度評(píng)估模型預(yù)估效果；
MAE（Mean Absolute Error）/MSE（Mean Squared Error），從準(zhǔn)確率的角度評(píng)估模型預(yù)估效果；
Loss：從擬合訓(xùn)練數(shù)據(jù)的角度評(píng)估模型預(yù)估效果；
http://www.flickering.cn/uncategorized/2014/10/%E8%BD%AC%E5%8C%96%E7%8E%87%E9%A2%84%E4%BC%B0-2%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92%E6%8A%80%E6%9C%AF/


2. 模型過(guò)擬合/模型矯正
特征層面：廣告id：高頻／低頻廣告(分類(lèi))
模型矯正－ctr預(yù)估矯正
分桶矯正
保順回歸

3.其他模型：FM／NB／SVM
LR和NB分別作為Discriminative and Generative Algorithm的代表，雖屬不同派系，但在一定假設(shè)條件下，卻有一定內(nèi)在聯(lián)系。從這個(gè)聯(lián)系的推倒過(guò)程也可以看到LR模型的可解釋性，LR模型求出來(lái)的權(quán)重實(shí)際代表這個(gè)特征在正負(fù)樣本中的均值差異大小。
符號(hào)：和預(yù)估值的正負(fù)相關(guān)性
大?。禾卣鞯闹匾潭龋ň挡町惖拇笮。?常數(shù)項(xiàng)含義：即含有普通權(quán)重的信息，同時(shí)也包含正負(fù)樣本比信息

Ref