LoginSignup
34

More than 5 years have passed since last update.

【論文シリーズ】GoogleがCTRの予測プログラムを作った

Last updated at Posted at 2016-07-03

原文

広告クリック(率)の予測: (Ad Click Prediction: a View from the Trenches)
H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young (2013)

1. 要約/背景

  • Googleのリスティング広告(search advertising)のビッグデータを学習させて、広告のCTRを予測した。
  • メイン理論はよく研究されているので、より実践的な項目(メモリ節約、パフォーマンス評価方法、校正など)について調査した。

2. 骨子の理論 / 実践Tips

 入力次元に対応する広告関係のメタパラメータは残念ながら公表されない。
メインの学習手法は、NNを利用しているみたいだ。
論文では、重みと学習係数の更新の計算手法として、一般的なOGD(オンライン確率降下法)に代わってFTRL-Proximalアルゴリズムが提唱された。

(1)FTRL-Proximal (Follow The Regularized Leader- Proximal)

重みの更新の際、前エポックについて、下のパラメータを計算する。パラメータの最小値を記録した重み項を更新に採用するというアルゴリズムである。

{\bf w_{t+1}} = \arg\min_{{\bf w}}\Big({\bf g}_{1:t}・{\bf w} + \frac{1}{2}\sum_{s=1}^{t}\sigma_{s}||{\bf w}-{\bf w}_s||^2_2 + \lambda_1||{\bf w}||_1\Big)

この式の右辺は、L1, L2正則化を考慮して、次のように書き換えられる;

\Big({\bf g}_{1:t} - \sum_{s=1}^{t}\sigma_{s}{\bf w}_s\Big)・{\bf w}+ \frac{1}{\eta_t}||{\bf w}||^2_2 + \lambda_1||{\bf w}||_1 +(const)

$w$の係数項を$z$と置くと、$z$と$L1$項の係数$λ_1$の比較により、重みの更新を選ぶ;

\begin{eqnarray}
w_{t+1,i}=\left\{ \begin{array}{ll}
0 & \mbox{if} |z_{t,i}| \le \lambda_1 \\
-\eta_t(z_{t,i}-\mbox{sgn}(z_{t,i})\lambda_1 ) & \mbox{otherwise.} \\
\end{array} \right.
\end{eqnarray}

$L_2$正則化項の$\eta$は、次元ごとの勾配を利用して、更新される。そのため、Per-Coordinate Learningとよばれる。

\eta_{t,i} = \frac{\alpha}{\beta + \sqrt{\sum_{t}^{s=1}g_{s,t}^2}}

(2)メモリ節約アイディア

・確率分布の活用→出現率の低いデータセットに対して、ポアソン分布を使うなど
・2ビット論理値のような、メモリを食わないデータデザインをする。
・関連モデルの活用
・当てはめ
・学習係数の計算の近似→ポジティブデータとネガティブデータの比率に落としこむ

\begin{align}
\sum g_{t,i}^2 &= \sum_{\mbox{positive events}}(1 - p_t)^2 + \sum_{\mbox{negative events}}p_t^2 \\
&\approx P\Big(1-\frac{P}{N+P}\Big)^2 + N\Big( \frac{P}{N+P}\Big)^2\\
&= \frac{PN}{N+P}
\end{align}

(3)予測の評価

ROC曲線による評価が上げられている。

(4)予測の校正

実装したアルゴリズムが、(考慮していないファクターによって)実際のCTRとずれたCTRを叩きだしたとき、それを校正すると、パフォーマンスがよくなる。
筆者らは、NNに校正層(calibration layer)を導入して、学習の校正を試みた。
校正関数は、ポワソン回帰のそれを採用して、訓練データに当てはめる。

本モデル構築に際して、価値の出なかった手法を以下に挙げる

①特徴ベクトルの行き過ぎたHash化

一般に文字列データは処理が重く、ハッシュ化することで処理の高速化が期待できる。ところが、本論文の系で特徴量をハッシュ化しても、期待されるほどのRAMの節約(計算効率)にならなかった。

②Dropout

効きにくい原因として、入力データの質の違いを挙げている。
画像データのように、情報が密集しているデータは、次元間の相関が強いため、Dropoutによる間引きが頑健性に貢献しやすい。
一方で、スパース性(One-hotベクトルばかり)やノイズ性のあるデータについては、単に情報量を間引くだけになり、効果が得られにくい。

③アンサンブル学習(特徴包装: feature bagging)

アンサンブル学習は、バイアスの除去と平行学習に効果があるとされているが、このモデルでは、0.1~0.6%くらいの改善寄与しかなかった。

④特徴ベクトルの正規化

この系では、入力データの多様性が強いため、本来は正規化すべきと考えた。
しかし、結果として、次元学習と正則化に対し、有害な結果をもたらすに至った。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
34