LoginSignup
13
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@KAKY(Takayuki Sakai)

GoogleのCTR予測手法についての論文要約

Posted at

原論文

Ad Click Prediction: a View from the Trenches
H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young (2013)
（恐らく著者は全て当時のGoogleエンジニア）

本論文に関するその他の日本語記事

概要

  • FTRL-Proximal というオンライン最適化手法の提案
    • 既存の手法よりスパースなモデルが作れる
  • 普通の機械学習論文では触れられない，現実のプロダクトで直面する課題
    • 使用メモリ削減
    • モデルの性能の評価・可視化
    • 予測の不確かさ（自信）の推定方法
    • 予測値のキャリブレーション
    • 特徴量の管理を自動化

1章・2章

  • 割愛
  • 検索連動型（リスティング）広告を想定してこの論文は書かれているようだが，実際読んでみるとその他のバナー広告やネイティブ広告，動画広告でも適用できる話しか書いていないように思える

3章: オンライン学習とスパースさ（Sparsity）

本論文の要，FTRLについて書いてある章．

前置き

  • ロジスティック回帰のようなオンライン線形回帰モデルは，ビッグデータの学習に向いている

    • 学習データを1回舐めるだけでいい
    • XGBoostなんかだと，何回も学習データを舐めなければならない

  • ビッグデータの機械学習において問題になるのはモデルの大きさ

    • OGD（≒SGD?）は学習は速いが，小さい（≒スパースな）モデルを作るのは苦手
    • L1正則化をかけても，重み $w_i$ が0になることは稀
    • FOBOSやRDAのようなスパースなモデルを作るのが得意のモデルは，性能の劣化が気になる

=> FTRLを使うことでモデルのスパース化と高性能化を両立

FTRLのざっくりした説明

普通のロジスティック回帰では特徴量ごとの重み $w_i$ と学習率 $\sigma_i$ を更新していく．
FTRLでは重みの代替表現 $z_i$ と今までのgradientの二乗の総和 $n_i$ を更新していく．

重み $w_i$ は以下の式で計算できる．
ハイパーパラメター: $\alpha$, $\beta$, $\lambda_1$, $\lambda_2$

w_i = \begin{cases}
  0 & if |z_i| \le \lambda_1 \\
  -(\frac{\beta + \sqrt n_i}{\alpha} + \lambda_2)^{-1} (z_i - sgn(z_i)\lambda_1) & otherwise.
\end{cases}

上の式から分かるように，正則化パラメータの $\lambda_1$ より小さい $z_i$ の時は，重み $w_i$ は0になる．
このためFTRLではスパースなモデルが得られる．

先行研究のモデルFOBOSやRDAと比べても，同じ性能になるように調整した時によりスパースなモデルが得られた実験結果がTable1で示されている．

3.1章: 特徴量ごとの学習率

教科書通りのOGDを行う場合，全ての特徴量に対して一つの学習率（グローバル学習率）のみを使うことになっている．
しかし，以下の理由からビッグデータではこれは適していない．

  • 特徴量ごとに出現回数が大きく異なる
    • 稀な特徴量が初めて出現した時にはグローバル学習率はすでに収束してしまっていて，その特徴量の学習が進まない

この問題は特徴量ごとに一つ学習率 $\sigma_i$ を割り振ってやり，特徴量 $f_i$ が出現した時のみ　 $\sigma_i$ を更新することで解決できる．

4章: ビッグデータにおけるメモリ削減手法

4.1章: 特徴量の確率的取り込み

ビッグデータにおいては，全学習データの中で数回しか現れない特徴量が非常に多い．（Googleのデータでは半分の特徴量が1回しか現れないこともあるとか．）

こうした問題の簡単な解決策として，未知の特徴量については今までの出現回数を覚えておいて，ある閾値 $k$ を超える回数現れたらモデルに取り込むというのがある．
ただ，未知の全ての特徴量の出現回数を覚えてくのはメモリ効率が良くないので，以下のような手法を提案している．

  • Poisson Inclusion
    • 未知の特徴量が現れた場合，$p$ の確率でそれをモデルに取り込む
    • 一度取り込んだ特徴量は，既知の特徴量として以後その重みが出現するたびに更新していく
  • Bloom Filter Inclusion
    • Bloom Filterとは: 「ある要素が集合のメンバである可能性があるか，それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造
    • これを使うことで，n回以上現れた特徴量は確実に取り込むことができる
    • n回現れていない特徴量も取り込んでしまう（False positives）可能性はある
    • その代わりメモリ効率は良い

実験結果によると，Bloom Filter Inclusionの方が少し性能が良かったらしい．

4.2章: 省メモリな数値型

ほとんどの重み $w_i$は $(-2, +2)$ の範囲に収まるので，Double（8Bytes）やFloat（4Bytes）ほどの精度はいらない．
符号部(1bit），指数部（2bits），仮数部（13bits)の数値型（2Bytes)を使うのがちょうど良いらしい．

ただ，これだけbitが少ないと丸め処理で値が更新されなくなることがあるので，丸め処理の時に確率的に切り上げ・切り捨てを決めるようにする．

4.3章: 似たモデルの同時学習

ハイパーパラメターだけが異なるモデルは同時に学習することで以下のリソースが節約できる．

  • 学習データを取得のためのアクセス数
    • どうせ同じ学習データを使うので
  • 学習率の更新のための計算リソース
    • ハイパーパラメターが異なっても学習率の更新は同一
  • モデルの重みを保持するメモリリソース
    • 一つのHashTableに入れることで無駄を減らせる

4.4章: 複数モデルで重みを共有

4.3章より更に進んで，違うモデルで重みまで共有してしまう．
重み更新の際は，モデルごとに一旦次の重みを計算するがその後平均をとって一つの値にしてしまう．

4.5章: 回数を使った学習率の近似

FTRLの章で述べたように，gradientの二乗の総和を保存しておく必要がある．
しかし，1（正例）と0（負例）の数を数えるだけで近似できる，という話．

4.6章: 学習データのサンプリング

CTR予測のようなデータの場合，目的ラベルの1と0の出現回数が著しく偏っている．
そこで，0（負例）のデータのみサンプリングして減らしてやることで，ほとんど精度を落とさず学習データを小さくすることができる．

しかし，これにより学習データ内の0と1の比率が変わるので，それを補正するように重みの更新式を修正する必要がある．

5章: モデルの性能評価

モデルの評価指標には色々あるが，モデルの変化に対する反応具合は評価指標ごとに異なる．
そのためいくつかの評価指標にまたがって見るべきである．

5.1章: 学習しながら評価する

  • どの最適化手法においても基本的に学習時に予測値を計算する必要がある
    • => その値を使って同時に評価も行ってしまう
  • 直前のデータを使って学習したモデルで評価することになる
    • => 本番での予測精度に近い
  • 全ての学習データを使って精度ができる
    • => 信頼性が高い

また，評価指標の絶対値を使って比較するのは正しくないことが多い．
例えばLogLossなどはテストデータの0と1の偏りによって取りうる値の幅が大きく変わってしまう．

なので，常にベースラインモデルと比較した相対値による比較を行うべき．

5.2章: 可視化による深い分析

ビッグデータのモデル評価における落とし穴として，テストデータ全体における評価では，一部セグメントにおける性能改善を捉えられないことがある．
そこでGoogleではセグメントごとにおける評価指標の改善具合を確認できる可視化ツールを自作して，この問題を解決した．

6章: 予測結果に対する不確かさ（自信）推定

広告プロダクトにおいてはCTRの予測結果だけではなく，その予測結果がどれくらい正しそうか，というのも重要である．
例えば，まだあまり情報のない広告を試しに出してみるかどうか，のような意思決定に使われる．

本論文で提案されている手法は，以下の式で計算される uncertainty score という指標である．

u(\vec{x}) = \alpha \vec{n}\cdot\vec{x}

これは普通の予測 $\sigma(\vec{w}\cdot\vec{x})$ と同じ計算量で導出でき，とても効率が良い．

またこの uncertainty score と実際のデータにおける予測のバラつきをグラフにしてみたところ，強い相関が見られたとのこと．

7章: 予測値の補正

どんなモデルを使っても，予測値にバイアスがかかることは避けられない．
そのため機械学習モデルによる予測の後に，補正（キャリブレーション）層を挟むことを提案している．

本章で提案されている補正手法の一例として，学習データ群 $d$ ごとにポアソン回帰式 $\tau(p) = \gamma p^\kappa$ へのフィッティングにより $\gamma$ と $\kappa$ を学習することである．

8章: 特徴量の管理を自動化

大規模なプロダクトになると，特徴量の元となるデータ（以下，Signal）を作る開発者と，それを使う開発者は大抵の場合異なる．
Signalはシステムの設定や実装の変更によって，ある日突然性質が変わってしまうこともある．

このような状況では安定した機械学習システムを運用することは難しいので，Signalに手動・自動でインデックスを割り振ることでこの問題に対処する．
例えば，あるSignalがdeprecated（削除予定）になった時は，そのSignalを用いている利用している部分にアラートがあげられる．また，あるSignalの新しいバージョンが出た時には，それを使った新しいモデルを試すように通知がなされる．

9章: 上手くいかなかった手法

9.1章: 積極的なFeature Hashing

近年，モデルを小さくする手法としてFeature Hashingがよく紹介されるが，本論文の著者が試したところ，性能の劣化が大きく許容できるものではなかった．

9.2章: Dropout

深層学習での正則化手法として有名なDropoutであるが，モデルの性能を劣化させるだけであった．
なぜこうなったかの推測として，画像認識などの深層学習タスクでは非常に密（dense）なモデルになりがちであるが，CTR予測においては非常にスパースなモデルとなるため上手くいかなかったのでは，とのこと．

9.3章: Feature Bagging

決定木系アルゴリズムでよく使われるFeature Baggingであるが，CTR予測においては性能劣化を招くだけであった．

9.4章: 特徴量ベクトルの正規化

機械学習において一般によく行われる手法ではあるが，CTR予測においては上手くいかなかった．

感想

3章のFTRLや4.1章の確率的な特徴量の取り込みなんかは小さい広告企業でも使えそうだと思った．
一方で，4.2〜4.6章や5.2章・8章などはGoogleレベルの規模にならないととても取り組めるものではないように感じた．

13
14
0

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
Sign upLogin
13
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?