前言

在實際項目或者刷競賽的時候，經常會遇到訓練數據非常大導致一些演算法實際上不能操作的問題。比如在廣告行業中，因為DSP的請求數據量特別大，一個星期的數據往往有上百G，這種級別的數據在訓練的時候，直接套用一些演算法框架是沒辦法訓練的，基本上在特徵工程的階段就一籌莫展。通常採用採樣、截斷的方式獲取更小的數據集，或者使用大數據集群的方式進行訓練，但是這兩種方式在作者看來目前存在兩個問題：

  • 採樣數據或者截斷數據的方式，非常的依賴前期的數據分析以及經驗。
  • 大數據集群的方式，目前spark原生支持的機器學習模型比較少；使用第三方的演算法模型的話，需要spark集群的2.3以上；而且spark訓練出來的模型往往比較複雜，實際線上運行的時候，對內存以及QPS的壓力比較大。

我自己以前在刷競賽的時候，看到別人使用過FM+FTRL的模型實現了一個CTR演算法，印象很深。自己使用的是DNN+Embedding的方式做的一個演算法模型，從理論上看embedding肯定比one-hot encoder的方式更加先進且能真實反饋特徵數據的相關性，但是實際效果看對方的FM_FRTL得到的AUC比我高近一個百分點，而且可以在10G的數據上一個多小時跑完，而我的DNN+Embedding演算法，因為沒有GPU主機，跑一次需要十二個小時，嚴重影響了調參的積極性，這也是我非常想掌握FTRL的出發點。

更重要的是，考慮到刷競賽與實際演算法是否可工程化的的角度，FTRL結合LR或者FM是一個非常好的方向，比Top1開源的代碼使用了PCA、NLP處理特徵以及多個模型stacking的技巧，更具有學習或者借鑒的價值。

本文主要根據谷歌給出的FTRL理論論文，以及FTRL+LR的工程化實現論文，從理論到工程化實現LR+FTRL的開發，任一後端開發人員都能根據文末給出的python代碼，簡單的開發就能實現一個簡單、高性能、高可靠的CTR預測模型。

LR

關鍵概念點：

1.logistic distribution
2.幾率
3.對數幾率
4.損失函數
5.參數估計
6.誤差計算
7.隨機梯度下降

LR數學原理

LR(logistic regression model)是一種分類模型，我們通常都知道：

LR = Line Regression + sigmod ag{1}

但是對其實際的數學原理卻不是很了解。logistics regression中的logistic指的是統計學中的logistic distribution:

標準logistic分布密度函數與分布函數

可以說LR是線性回歸模型通過logistic的分布函數，將預測結果映射到概率空間，進而預測不同分類的概率，其概率由條件概率P(Y|X)表示。

LR模型既可以做二分類也可以做多分類，因為從事的是廣告、營銷行業的模型預估，本文只針對二分類的LR模型(binary logistic regression model)做原理講解以及模型工程化實現。

二分類的LR模型是如下條件概率的分布：

P(Y=1|X) = frac{exp(wx +b)}{1+exp(wx + b)} ag{2}

P(Y=0|X) = frac{1}{1+exp(wx + b)} ag{3}

幾率：如果一個事件發生的概率是p，那麼該事件發生的幾率是發生的概率/不發生的概率:

odds = frac{p}{1-p} ag{4}

對數幾率：對幾率取對數。

logit(p) = log(odds) = log(frac{p}{1-p}) ag{5}

代入公式(2)和公式(3)得到:

log{frac{P(Y=1|X)}{1-P(Y=1|X)}} = w * x ag{6}

可以看出LR也可以認為是用線性回歸模型的預測結果來預測事件發生的對數幾率。

LR有很多優點，比如：

  • 作為統計模型與機器學習的結合點，具有較好的預測結果以及可解釋性。
  • 直接對分類的可能性建模，無需事先假設數據的分布，這就避免了假設分布不準確帶來的影響。
  • 不僅預測得到分類，還有分類對應的概率，這對很多需要使用概率輔助決策的任務很有用。
  • sigmod函數是高階可導的凸函數，具有很好的數學性質，很多數值優化的演算法都可以直接用於求解最優解。

參數估計

損失函數

邏輯回歸模型學習時，對於給定的訓練集，可以使用極大似然估計法估計模型參數（將權重向量w和輸入向量x擴充一位），設：

egin{align} P(Y=1|X) &=pi(x)= frac{exp(wx +b)}{1+exp(wx + b)} =frac{exp(wx)}{1+exp(wx)} ag{7} end{align}

egin{align} P(Y=0|X) = 1- pi(x) =frac{1}{1+exp(wx + b)}=frac{1}{1+exp(wx)} ag{8} end {align}

似然函數是：

prod_{i=1}^{n}[pi(x_i)]^{y_{i}}[1-pi(x_{i})]^{1-y_{i}} ag{9}

對數似然函數：

egin{align} L(W) =& sum_{i=1}^{N}[y_{i}log(pi(x_{i}))+(1-y_{i})log(1-pi(x_{i})]))\ =&sum_{i=1}^{N}[y_{i}logfrac{pi(x_{i})}{1-pi_{x_{i}}}+log(1-pi(x_{i}))]\ =&sum_{i=1}^{N}[y_{i}(wx)-log(1+exp(w*x))] ag{10}end{align}

這樣邏輯回歸的參數優化問題就變成了以對數似然函數為目標的最優化問題，也就是對公式10求最大值時的參數w；

實際應用中，通常是使用最小化損失函數的概念來尋找最佳參數空間，所以對公式10取負號得到邏輯回歸模型的損失函數：

egin{align} l(w) =& -sum_{i=1}^{N}[y_{i}log(pi(x_{i}))+(1-y_{i})log(1-pi(x_{i})]))\ =& -sum_{i=1}^{N}[y_{i}(wx)-log(1+exp(wx))] ag{11} end {align}

也就是我們常說的交叉熵損失函數，是一個高階可導連續凸函數。根據凸函數優化理論，可以使用梯度下降法、牛頓法、trust-region等方法進行優化。

以梯度下降法為例，計算l(w)的梯度為：

egin{align*} g_{j} =&frac{partial(l(w))}{partial(w)} \ =& -y_{i}*x + frac{exp(w*x)}{1+exp(w*x)}*x \ =& (pi(x^{i}) - y_{i}) * x^i_{j} ag{12} end{align*}

所以樣本第j個參數的優化方式為：

w^{i+1}{j} = w^{i}{j} - a * g_{j} ag{13}

所有樣本的第j個參數更新方式為：

w_{j} = w_{j} - alpha * sum_{i=1}^{N}(pi(x^{i})-y^{i})*x^{i}_{j} ag{14}

當樣本數據里N很大的時候，通常採用的是隨機梯度下降法，演算法如下所示：

while {
for i in range(0,m):
w_j = w_j + a * g_j
}

隨機梯度下降的好處是可以實現分散式並行化，具體計算流程是：

  1. 在每次迭代的時候，隨機抽樣一定比例的樣本作為當前迭代的計算樣本。
  2. 對計算樣本中的每一個樣本，分別計算不同特徵的計算梯度。
  3. 通過聚合函數，對所有計算樣本的特徵的梯度進行累加，得到每一個特徵的累積梯度以及損失。
  4. 最後根據最新的梯度以及之前的參數，對參數進行更新。
  5. 根據更新的參數計算損失函數誤差值，如果損失函數誤差值達到允許的範圍，那麼停止迭代，否則重複步驟1。

工程化實現思路

主要是需要實現參數更新計算以及損失函數計算。

FTRL

相關背景

廣告、營銷、推薦行業傳統的機器學習開發流程基本是以下步驟：

  1. 數據融合，獲取訓練以及評估數據集。
  2. 特徵工程。
  3. 構建模型，比如LR，FM等。
  4. 訓練模型，獲得最優解。
  5. 評估模型效果。
  6. 保存模型，並在線上使用訓練的有效模型進行訓練。

這種方式主要存在兩個瓶頸：

  1. 模型更新周期慢，不能有效反映線上的變化，最快小時級別，一般是天級別甚至周級別。
  2. 模型參數少，預測的效果差；模型參數多線上predict的時候需要內存大，QPS無法保證。

針對這兩個問題，一般而言有兩種解決方式：

  1. 對1採用On-line-learning的演算法。
  2. 對2採用一些優化的方法，在保證精度的前提下，盡量獲取稀疏解，從而降低模型參數的數量。

傳統的LR或者FM離線訓練方法中，通常使用L1正則化的方法獲取稀疏解；但是在線學習的時候，針對每一個樣本的梯度下降方向並不是全局的，而是一個隨機梯度下降的方式，簡單的使用L1正則化並不能獲得正確的稀疏解。

比較出名的在線最優化的方法有：

  • TG(Truncated Gradient)
  • FOBOS(Forward-Backward Splitting)
  • RDA(Regularized Dual Averaging)
  • FTRL(Follow the Regularized Leader)

其中TG截斷比較武斷；FOBOS能獲得較好的精度，但是稀疏性較差；RDA演算法會在犧牲一定的精度條件下，獲得較好的稀疏性；而FTRL演算法技能提高OGD（online-gradient-descent）的精確度，又能獲得更好的稀疏性。

FTRL與RDA、FOBOS對比

演算法原理

參數權重更新

FTRL演算法權重更新公式為： egin{align*} W^{t+1} &= operatorname*{argmin}_{W}{G^{(1:t)}W + lambda_{1}||W||_{1} + lambda_{2}||W||_{2} + frac{1}{2}sum_{s=1}^{t}sigma^{(s)}||W-W^{(s)}||_{2}^{2}}\ &= operatorname{argmin}_{W}{(G^{(1:t)}-sum_{s=1}^{t}sigma^{(s)}W^{(s)})W + lambda_{1}||W||_{1} + frac{1}{2}(lambda_2 + sum_{s=1}^{t}sigma^{(s)})||W||_2+frac{1}{2}sum_{s=1}^{t}sigma^{(s)}||W^{(s)}||_{2}^{2}} ag{15} end{align*}

由於 frac{1}{2}sum_{s=1}^{t}sigma^{(s)}||W^{(s)}||_{2}^{2} 相對於W來說是一個常數，並且令 :

Z^{(t)} = G^{(1:t)} - sum_{s=1}^{t}sigma^{(s)}W^{(s)}

公式15等價於：

egin{align*} W^{t+1} &= operatorname{argmin}_{W}{Z^{(t)}W + lambda_{1}||W||_{1} + frac{1}{2}(lambda_2 + sum_{s=1}^{t}sigma^{(s)})||W||_2 ag{16} end{align*}

針對特徵權重的各個維度將其拆解成N個單獨的標量最小化問題：

operatorname{min}_{W_{i}in{R}}{Z_{i}^{(t)}*w_{i} + lambda_{1}|w_{i}|+frac{1}{2}（lambda_{2}+sum_{s=1}^{t}sigma^{(s)})w_{i}^{2}} ag{17}

公式17是一個無約束的非平滑參數優化問題，其中第二項 ||w_{i}|| 在 w_{i} 處不可導。假設 w_{i}^{*} 是其最優解，並且定義 xiin{partial|w_{i}^{*}|} 是 |w_{i}| 在? w_{i}^{*} 的次導數，那麼有：

partial|w_{i}^{*}| = left{ egin{array}{ftrl} &{-1<xi<1} &if&w_{i}^{*}=0 \ &{1}&if&w_{i}^{*}>0\ &{-1}&if&w_{i}^{*}<0 end{array} ag{18} ight.

對公式17進行求導，並等於0，有：

Z_{i}^{(t)} + lambda_{1}xi+(lambda_{2}+sum_{s=1}^{t}sigma^{(s)})w_{i}=0 ag{19}

由於 lambda_{1},lambda_{2} 大於0，針對公式19分三種情況：

  1. 當 |Z_{i}^{(t)}|<lambda_{1}? 的時候：
    1. 如果 w_{i}^{*}=0? ，由公式19可以得到 xi=-Z_{i}^{(t)}/lambda_{1}? ,符合公式18的條件1.
    2. 如果 w_{i}^{*}>0? ，有公式18得到 xi=1? ，那麼 Z_{i}^{(t)} + lambda_{1}+(lambda_{2}+sum_{s=1}^{t}sigma^{(s)})w_{i}> Z_{i}^{(t)} + lambda_{1}>0? ，不滿足公式19.
    3. 如果 w_{i}^{*}<0 ，有公式18得到 xi=-1 ，那麼 Z_{i}^{(t)} -lambda_{1}+(lambda_{2}+sum_{s=1}^{t}sigma^{(s)})w_{i}< Z_{i}^{(t)} -lambda_{1}<0 ，不滿足公式19.
    4. 所以當 |Z_{i}^{(t)}|<lambda_{1}? 的時候， w_{i}^{*}=0? 。
  2. 當 Z_{i}^{(t)}>lambda_{1}? 的時候：
    1. 如果 w_{i}^{*}=0? ，由公式19可以得到 xi=-Z_{i}^{(t)}/lambda_{1}<-1? ,不符合符合公式18。
    2. 如果 w_{i}^{*}>0? ，有公式18得到$xi=1? xi=1? ，那麼 Z_{i}^{(t)} + lambda_{1}+(lambda_{2}+sum_{s=1}^{t}sigma^{(s)})w_{i}> Z_{i}^{(t)} + lambda_{1}>0? ，不滿足公式19.
    3. 如果 w_{i}^{*}<0? ，有公式18得到 xi=-1? ，那麼 Z_{i}^{(t)} -lambda_{1}+(lambda_{2}+sum_{s=1}^{t}sigma^{(s)})w_{i}=0? ，所以有：w_{i}^{*}=-(lambda_{2}+sum_{s=1}^{t}sigma^{(s)})^{-1}*(Z_{i}^{(t)} -lambda_{1})?
  3. 當Z_{i}^{(t)}<-lambda_{1}? 的時候：
    1. 如果 w_{i}^{*}=0? ，由公式19可以得到 xi=-Z_{i}^{(t)}/lambda_{1}<-1? ,不符合符合公式18。
    2. 如果 w_{i}^{*}>0? ，有公式18得到 xi=1? ，那麼 Z_{i}^{(t)} + lambda_{1}+(lambda_{2}+sum_{s=1}^{t}sigma^{(s)})w_{i}? ，所以有： w_{i}^{*}=-(lambda_{2}+sum_{s=1}^{t}sigma^{(s)})^{-1}*(Z_{i}^{(t)} + lambda_{1})?
    3. 如果 w_{i}^{*}<0? ，有公式18得到$xi=-1?$ xi=-1? ，那麼 Z_{i}^{(t)} - lambda_{1}+(lambda_{2}+sum_{s=1}^{t}sigma^{(s)})w_{i}<Z_{i}^{(t)} - lambda_{1}<-2lambda_{1}<0? ，不滿足公式19.

綜合上面的分析，可以得到FTRL特徵權重各個維度更新的公式為：

w_{i}^{(t+1)} = left{ egin{array}{ftrl} &0 &if&|z_{i}^{(t)}|<lambda_{1} \ &-(lambda_{2}+sum_{s=1}^{t}sigma{(s)})(z_{i}^{(t)}-lambda_{1}*sign(z_{i}^{(t)}))&otherwise\ end{array} ag{20} ight.

per-coordinate learning rates

在FTRL中，每個維度的學習率都是單獨考慮的。標準的OGD理論對每一個樣本都是使用的相同的學習率: eta_{t}=frac{1}{sqrt{t}}? 。

一個簡單的思維推理就能證明這種情況並不一定是最理想的：假如我們每一輪扔十個硬幣，然後使用LR去預估i個硬幣正面朝上的概率： P(heads|coin_{i}) 。假設使用相同的學習率 eta_{t}=frac{1}{sqrt{n_{t,i}}} ，其中 n_{t,i} 是 coin_{i} 正面朝上的次數。如果coin_{i} 比 coin_{j} 正面的次數更多，那麼 coin_{i} 的學習率應該比 coin_{j} 下降的更快，表現為coin_{i} 具有更多的數據。coin_{j} 的學習率保持的比較高，意味著對 coin_{j} 的新數據更敏感。

從另一個方面說，如果 coin_{i}? 從沒有投出正面，但是我們依舊在調低 coin_{i}? 的學習率，這明顯是不合理的。

因此，至少對於某些問題而言，使用per-coordinate learning rates是有好處的。谷歌使用以下的公式計算per-coordinate learning rates：

eta_{t,i}=frac{alpha}{eta+sqrt{sum_{s=1}^{t}(g_{i}^{(s)})^{2}}} ag{21}

其中 g_{i}^{(s)} 是第s個樣本計算的梯度向量 g^{s} 中 i^{th} coordinate gradient。

谷歌經驗表面， alpha 通常是要調節的， eta 取1就好，且在使用了per-coordinate learning rates之後，AUCLoss下降了11.2%，對於谷歌的廣告系統而言，1%的AUCLoss降低就被認為是很好的優化了。

工程實現思路

工程化實現偽代碼

谷歌給出了FTRL的工程化演算法偽碼，其中 sigma^{(1:t)}=sum_{s=1}^{t}sigma{(s)}=frac{1}{eta_{i}^{(t)}}=frac{eta+sqrt{sum_{s=1}^{t}(g_{i}^{(s)})^{2}}}{alpha}

egin{align*} hline &Large{ ext{Algorithm1 Per-Cordinate FTRL-Proximal with $L_{1}$ and}}\ &Large{ ext{$L_2$ Regularization for Logistic Regression}}\ hline &large{ ext{# With per-cordinate learning rates of Eq.(2)}}\ &largeold{Input:} ext{parameters $alpha$,$eta$,$lambda_{1}$,$lambda_{2}$}\ & ext{$forall{i}in{1,.....,d}$,initialize $z_{i}=0$ and $n_{i}=0$}\ &old{for} ext{ t=1 $old{to}$ T } old{do}\ &spacespacespacespace ext{Recieve feature vector $x_{t}$ and let $I={i|x_{i} eq{0}}$}\ &spacespacespacespace ext{For $iin{I}$ compute}\ &spacespacespacespacespacespacespacespace{w_{t,i}=left{ egin{array}{fm} &0 & ext{if $|z_{i}|$ < $lambda_{1}$}\ &-(frac{eta+sqrt{n_{i}}}{alpha}+lambda_{2})^{-1}(z_{i}-sgn(z_{i})lambda_{1}) & ext{otherwise.}\ end{array} ight.}\ &spacespacespacespace ext{Predict $P_t = sigma(x_{t}*w)$ using the $w_{t,i}$ compute above} \ &spacespacespacespace ext{Observe label $y_{t}in{0,1}$}\ &spacespacespacespace ext{$old{for}$ all $iin{I}$ do}\ &spacespacespacespacespacespacespacespace ext{$g_{i}=(p_{t}-y_{t})x_{i}$ #gradient of loss w.r.t. $w_{i}$}\ &spacespacespacespacespacespacespacespace ext{$sigma_{i}=frac{1}{alpha}(sqrt{n_{i}+g_{i}^2}-sqrt{n_{i}})$ # equal $frac{1}{eta_{t,i}}-frac{1}{eta_{t-1,i}}$}\ &spacespacespacespacespacespacespacespace ext{$z_{i}leftarrow{z_{i}}+g_{i}-sigma_{i}omega_{t,i}$}\ &spacespacespacespacespacespacespacespace ext{$n_{i}leftarrow{n_{i}}+g_{i}^2$}\ &spacespacespacespace ext{$old{endspace{for}}$}\ & ext{$old{endspace{for}}$}\ hline end{align*}

其它谷歌實現的FTRL工程化技巧

  • Per-coordinate learning rate
    • 原理如前面所述，從統計學上講就是有效數據越多，數據可信度越高，學習率就越低，優化效果明顯。
  • probabilistic feature inclusion
    • 每一個特徵根據泊松分布，以一定的概率p被保存，。
    • 使用布隆過濾器，當特徵數出現次數大於一個閾值的時候保存。
  • Encoding Values with Fewer Bits：減少存儲weight參數佔用的內存。
  • 訓練數據子採樣
    • 正樣本正常採樣。
    • 負樣本按照r比例採樣，在訓練的時候對每一個樣本乘以$frac{1}{r}?$的權重彌補負樣本的損失。

LR+FTRL工程化實現

根據前面的學習，可以使用LR作為基本學習器，使用FTRL作為在線最優化的方法來獲取LR的權重係數，從而達到在不損失精度的前提下獲得稀疏解的目標。

工程化實現的幾個核心點是：

  • 梯度計算代碼
  • 損失函數計算代碼
  • 權重更新計算代碼

演算法代碼實現如下所示，這裡只給出了核心部分代碼，主要做了以下優化:

  • 修復原代碼更新梯度時候的邏輯錯誤。
  • 支持pypy3加速，5.6G的訓練數據，使用Mac單機可以9分鐘跑完一個模型，一個epoch之後的logloss結果為0.3916；這對於刷競賽或者實際工程中模型訓練已經是比較理想的性能了。
  • 使用16位浮點數保存權重數據，降低模型文件大小。
  • 使用json保存模型非0參數w,z,n，進一步壓縮線上使用的時候佔據的內存空間，可以進一步考慮壓縮模型文件大小，比如使用bson編碼+gzip壓縮後保存等。

from datetime import datetime
from csv import DictReader
from math import exp, log, sqrt
import gzip
import random
import json
import argparse

class FTRLProximal(object):
"""
 FTRL Proximal engineer project with logistic regression
 Reference:
 https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/41159.pdf

 """

def __init__(self, alpha, beta, L1, L2, D,
interaction=False, dropout=1.0,
dayfeature=True,
device_counters=False):

# parameters
self.alpha = alpha
self.beta = beta
self.L1 = L1
self.L2 = L2
self.dayfeature = dayfeature
self.device_counters = device_counters

# feature related parameters
self.D = D
self.interaction = interaction
self.dropout = dropout

# model
self.n = [0.] * D
self.z = [0.] * D
self.w = [0.] * D

def _indices(self, x):

 A helper generator that yields the indices in x
 The purpose of this generator is to make the following
 code a bit cleaner when doing feature interaction.

for i in x:
yield i

if self.interaction:
D = self.D
L = len(x)
for i in range(1, L): # skip bias term, so we start at 1
for j in range(i + 1, L):
# one-hot encode interactions with hash trick
yield abs(hash(str(x[i]) + _ + str(x[j]))) % D

def predict(self, x, dropped=None):
"""
 use x and computed weight to get predict
 :param x:
 :param dropped:
 :return:
 """
# wTx is the inner product of w and x
wTx = 0.
for j, i in enumerate(self._indices(x)):

if dropped is not None and dropped[j]:
continue

wTx += self.w[i]

if dropped is not None:
wTx /= self.dropout

# bounded sigmoid function, this is the probability estimation
return 1. / (1. + exp(-max(min(wTx, 35.), -35.)))

def update(self, x, y):
"""
 update weight and coordinate learning rate based on x and y
 :param x:
 :param y:
 :return:
 """

ind = [i for i in self._indices(x)]

if self.dropout == 1:
dropped = None
else:
dropped = [random.random() > self.dropout for i in range(0, len(ind))]

p = self.predict(x, dropped)

# gradient under logloss
g = p - y

# update z and n
for j, i in enumerate(ind):

# implement dropout as overfitting prevention
if dropped is not None and dropped[j]:
continue

g_i = g * i
sigma = (sqrt(self.n[i] + g_i * g_i) - sqrt(self.n[i])) / self.alpha
self.z[i] += g_i - sigma * self.w[i]
self.n[i] += g_i * g_i

sign = -1. if self.z[i] < 0 else 1. # get sign of z[i]

# build w on the fly using z and n, hence the name - lazy weights -
if sign * self.z[i] <= self.L1:
# w[i] vanishes due to L1 regularization
self.w[i] = 0.
else:
# apply prediction time L1, L2 regularization to z and get
self.w[i] = (sign * self.L1 - self.z[i])
/ ((self.beta + sqrt(self.n[i])) / self.alpha + self.L2)

def save_model(self, save_file):
"""
 保存weight數據到本地
 :param save_file:
 :return:
 """
with open(save_file, "w") as f:
w = {k: v for k, v in enumerate(self.w) if v != 0}
z = {k: v for k, v in enumerate(self.z) if v != 0}
n = {k: v for k, v in enumerate(self.n) if v != 0}
data = {
w: w,
z: z,
n: n
}
json.dump(data, f)

def load_weight(self, model_file, D):
"""
 loada weight data
 :param model_file:
 :return:
 """
with open(model_file, "r") as f:
data = json.load(f)
self.w = data.get(w, [0.] * D)
self.z = data.get(z, [0.] * D)
self.n = data.get(n, [0.] * D)

@staticmethod
def loss(y, y_pred):
"""
 log loss for LR model
 :param y:
 :param y_pred:
 :return:
 """
p = max(min(y_pred, 1. - 10e-15), 10e-15)
return -log(p) if y == 1. else -log(1. - p)

def data(f_train, D, dayfilter=None, dayfeature=True, counters=False):
GENERATOR: Apply hash-trick to the original csv row
 and for simplicity, we one-hot-encode everything

 INPUT:
 path: path to training or testing file
 D: the max index that we can hash to

 YIELDS:
 ID: id of the instance, mainly useless
 x: a list of hashed and one-hot-encoded indices
 we only need the index since all values are either 0 or 1
 y: y = 1 if we have a click, else we have y = 0

device_ip_counter = {}
device_id_counter = {}

for t, row in enumerate(DictReader(f_train)):
# process id
ID = row[id]
del row[id]

# process clicks
y = 0.
if click in row:
if row[click] == 1:
y = 1.
del row[click]

# turn hour really into hour, it was originally YYMMDDHH

date = row[hour][0:6]
row[hour] = row[hour][6:]

if dayfilter != None and not date in dayfilter:
continue

if dayfeature:
# extract date
row[wd] = str(int(date) % 7)
row[wd_hour] = "%s_%s" % (row[wd], row[hour])

if counters:
d_ip = row[device_ip]
d_id = row["device_id"]
try:
device_ip_counter[d_ip] += 1
device_id_counter[d_id] += 1
except KeyError:
device_ip_counter[d_ip] = 1
device_id_counter[d_id] = 1
row["ipc"] = str(min(device_ip_counter[d_ip], 8))
row["idc"] = str(min(device_id_counter[d_id], 8))

# build x
x = [0] # 0 is the index of the bias term
for key in row:
value = row[key]
# one-hot encode everything with hash trick
index = abs(hash(key + _ + value)) % D
x.append(index)
yield t, ID, x, y

參考文獻

  • Follow-the-Regularized-Leader and Mirror Descent:Equivalence Theorems and L1 Regularization(Google, FTRL原理論文)
  • Ad Click Prediction: a View from the Trenches(Google，FTRL工程化文檔)
  • 在線最優化求解(馮楊，講在線最優化演算法非常好的一篇文檔)
  • 統計學習方法(李航)
  • spark MLlib機器學習(黃美玲)
  • 機器學習(周航)

推薦閱讀：

相关文章