F@N Ad-Tech Blog

株式会社ファンコミュニケーションズ nend・nex8のエンジニア・技術ブログ

CTR予測とAdaGrad

こんにちはデータサイエンティストのt_sakaiです。

前にCTR予測についての概論・評価方法についての記事を書きましたので、今回はさらに踏み込んだ内容についてまとめてみたいと思います。

この記事を読むには以下を理解している必要があります

  • ロジスティック回帰の目的関数
  • 勾配降下法

目的関数と最適化アルゴリズム

基本ですが機械学習は、達成したい目的を数値化した目的関数と、目的関数を最小(or 最大)にするための最適化アルゴリズムの2ステップに分けられます。

1つ目のステップの目的関数は、CTR予測においてはロジスティック回帰がデファクトスタンダードになっています。(参考: GoogleのCTR予測についての論文

(kaggleにおけるCriteoのCTR予測コンペでは、特徴量抽出のためにGBDTを使ったり、特徴量の掛け合わせを考慮するためにFFMを使ったりすることにより良い精度が出ることが主張されていますが、モデルの単純さや学習・予測の速度を含めて考えるとまだまだロジスティック回帰は有力だと言えそうです。)

2つ目のステップの最適化アルゴリズムについてですが、CTR予測のような学習データが非常に大きい場合にはSGD(確率的勾配降下法)を使うのが一般的です。

本記事ではSGDの発展形であるAdaGradについて、そのアルゴリズムとなぜそれがCTR予測に向いているのか解説します。

前提

これからScalaによるサンプルコードを交えながらそれぞれの最適化アルゴリズムについての説明します。 そのサンプルコードで使われる変数・関数をここで定義しておきます。

また問題を単純にするため、全ての特徴量は質的変数であるとします。

val D = 10000 // 特徴量次元(ハッシュトリックなどにより恣意的に決定)
val w = Array.fill[Double](D)(0.0) // モデル
val data: Iterator[(Set[Int], Int)] = ...省略 // 学習データ、例: Iterator( (Set(0, 1, 8), 0), (Set(0, 4, 11), 1), ...)

def getP(x: Int): Double = { 省略 } // その学習データにおけるy=1である確率を計算する関数
def update(x: Set[Int], y: Int) // 学習データを1つ取って、モデルを更新する関数

data foreach { case (x, y) => update(x, y) } // 全ての学習データを使ってモデルを計算

以下では、上記のScalaスクリプトで未定義となっているupdate関数の実装を載せることで、それぞれのアルゴリズムの特徴を表現したいと思います。

SGD基本形

  • グローバルな学習率を1つだけもつ
  • 学習が進むにつれて学習率を小さくする
var eta = 1.0 // 学習率(初期値)

def update(x: Set[Int], y: Int) {
  val g = getP(x) - y // 勾配
  x foreach { i =>
    w(i) -= eta * g
  }
  eta *= 0.9 // 毎回学習率を小さくする
}

学習率を小さくする方法は上記のように定率で小さくする以外にもいくつも存在しますが、ここでは紹介を省きます。

SGDの特徴

CTR予測のように学習データが大規模スパースデータの場合、モデルの次元が非常に大きくなり更新にかかる計算量が大きくなります。

上のupdate関数を見て気づいて欲しいのが、ロジスティック回帰のモデルをSGDで更新する場合、出現した特徴量の重みのみが更新されるということです。

この性質のため、SGDではCTR予測のような非常にスパースなデータに対して高速に学習することができるのです。

問題点

ただ、実はこの手法だとCTR予測に適用するには問題があります。それは、出現頻度が少ない特徴量の学習が進まないことです。 全ての特徴量に同じ学習率を適用するため、珍しい特徴量が現れたときにはすでに学習率が収束してしまっているのです。

Scikit Learnに入っているトイデータだと、ダミー変数が少ないため「出現頻度が少ない特徴量」はほぼなく、このことは問題にはなりませんでした。 しかし、CTR予測のようなめったに現れない特徴量(広告IDやサイトIDなど)が大半を占める場合、これは大きな問題となります。

AdaGrad

  • 特徴量ごとに学習率を1つもつ
  • その特徴量の更新にはそれに対応した学習率を使う
  • 学習率の更新はそれに対応した特徴量が出現したときのみ行う
val eta = Array.fill[Double](D)(1.0) // モデルと同じ大きさの学習率の配列

def update(x: Set[Int], y: Int) {
  val g = getP(x) - y
  x foreach { i =>
    w(i) -= eta(i) * g
    eta(i) *= 0.9 // その特徴量に対応する学習率のみを小さくする
  }
}

(実際にはAdaGradで学習率を小さくする式はもっと複雑なのですが、ここでは簡略化しています。)

このようにAdaGradでは出現頻度が非常に少ない特徴量であっても、学習率が小さくなり過ぎずうまく学習することができます。

実際にAdaGradを用いて弊社のデータでCTR予測を行ったところ、普通のSGDに比べて精度が大きく向上することが確認できました。

その他のSGD発展形

SGDの発展形のアルゴリズムは山のようにあります。以下の英語の記事にgif動画つきで解説されているので、さらに知りたい方は是非読んでみてください。

sebastianruder.com

最後に

ファンコミュニケーションズでは機械学習エンジニアを募集しています。

主な開発言語はScala, PHPですが、分析作業においてはPythonやRも多用しています。 また分析環境としてTreasure Dataを導入しているため、SQLによって学習データの作成・機械学習をシームレスに行うことができ、データクレンジングなどの雑務に追われることなく非常に大きなデータを扱える環境が整っています。

興味がある方は以下のページをご覧ください。(Webアプリケーションエンジニアと書いてありますが、機械学習エンジニアも含んでいますので安心してください。)

www.fancs.com