Gmail優先トレイ論文メモ

研究

元論文

“The Learning Behind Gmail Priority Inbox”, Douglas Aberdeen, Ondrey Pacovsky, Andrew Slater, LCCC : NIPS 2010 Workshop on Learning on Cores, Clusters and Clouds.
http://research.google.com/pubs/archive/36955.pdf
Gmail Priority InboxにはPAが利用されていると話題になっているので，読んでみました．

簡単にまとめ

  • PA + transfer learning + logistic model
  • ランキング学習では，thresholdが非常に重要な働きを持つ
  • Gmail Priority Inboxはあなたのメール処理の時間を6%短縮してくれます

1.The Gmail Priority Inbox

  • メールの重要度による順位付けはそれほど目新しいタスクではない．
  • ただし，以下の事象がこのタスクを複雑化させている．
    • リアルタイム性
      • 新しい情報は即座に反映させたい
    • 明示的なラベルの欠如
      • あるユーザーにとってこのメールが重要かどうかは多くの場合，明示的に分からない
    • 非定常かつノイズが多く，制限の少ない訓練集合
    • terabyte規模での学習
    • 分散学習可能かつフォールトトレラントな構成

2.The Learning Problem

2.1 Features
  • 連続値の特徴は，2値の特徴に分割される
  • 特徴は，以下の4カテゴリーに分類可能
    • Social features
      • メールの受信者・送信者間のやり取りに関する情報（Ex.メール返信率）
    • Content features
      • ヘッダーやメール本文に関する情報
    • Thread features
      • スレッド情報
    • Label features
      • ユーザーが適用しているラベル情報
2.2 Important Metric
  • 優先トレイがやりたいのは，ユーザーからの明示的なラベリング無しでメールのランキングをすること
    • ランキングの基準は，ユーザーがメールに対してどのような行動を起こすか
  • つまり，各メールに対していかなる行動を起こすかを確率的に求めたい
  • 確率モデルと予測誤差の定義
    • 数式略
2.3 Model
  • ユーザーがメールに対して行動を起こす確率を以下のように定式化

s = \sum_{i=1}^n f_i g_i + \sum_{i=1}^{n+k} f_i w_i \quad \quad p = \frac{1}{1 + \exp^{-s}}

  • p : ユーザーが行動を起こす(ex.メールを返信する)確率
  • \mathbf{g} : Global Model（全ユーザー共通のモデル）の重みベクトル
  • \mathbf{w} : User Model（ユーザー固有のモデル）の重みベクトル
  • n : 特徴次元数, s : User Modelにのみ存在する特徴次元数
    • Global ModelとUser Modelを併用することで，User Modelのコンパクト化とGlobal Modelによる学習の効率化を実現
    • こういうのを転移学習っていうんでしょうかね…？
  • 重みベクトルの学習にはPA-IIを利用
    • PAの中でも一番ノイズに頑健なPA-IIを使用し，大量のノイズ情報に対処
  • メール1通につき，Global ModelとUser Modelの重みベクトルがそれぞれ1度ずつ更新される
  • 以下の式で，重みベクトルの更新(User iのUser Modelの更新の場合)

w_i \leftarrow w_i + f_i \frac{sgn(e) max(|e| - \epsilon, 0)}{\|\mathbf{f} \| ^2 + \frac{1}{2C}}

  • e : 誤差値． ユーザーが行動を起こす場合1,起こさない場合0となるパラメータaを用いて， e = a - pと定式化可能
    • この定義は正確ではないので，詳細を知りたい方は2.2章を読んでください
  • C : 更新の"Agressive"さを調節する正則化パラメータ, \epsilon : hinge-loss torelance
  • 正則化パラメータCの調節が重要である．
  • Cが大きいほど学習による更新幅が大きくなり，直近のメールからの学習に予測が引きづられることになる．
    • 十分に学習されていないUser Model等はCを大きくしている
    • 基本的に，User ModelのCをGlobal ModelのCよりも大きくしている
2.4 Ranking for Classification
  • さらに，上記のsにthresholdを課す
    • sがある一定値を超えていない限り，メールが重要かどうかを判断出来ないこととする
    • thresholdの値は，ユーザーによるランキングの評価へ重大な影響を与える
  • ただし，thresholdの調節は非常に困難
    • 多くの人は，メールを重要だから開くのではなく面白いから開くことがある
    • 重要なメールを重要でないと判断されるのは，非常に困る
    • 逆はそうでもない
    • 重要なメールに判定される量の好みは人によって異なる
  • thresholdの調節には，ユーザーがある程度干渉できるようにした
    • ユーザーが重要マークを一定の基準で使っていることが判断されたら，thresholdを更新する

3.Production

  • ユーザー数の増加にスケールさせることは困難
  • BigTableを改良を加えた形で利用
3.1 Prediction Time
  • 全てのデータセンターから，全てのユーザーのスコアリングが可能な設計が求められる
    • どのデータセンターが，どのユーザーアカウントを扱うのか，予測することは困難
  • BigTableは，ランキングを行うためのモデルの複製・更新を行うために用いられ，下記の操作に伴うリソース管理とリアルタイムでの実行を実現
    • 入力情報（メールの特徴量）と出力情報（その後のユーザー行動）を統合
    • 同時に，ユーザー単位で同じレコードにデータを管理
    • 全てのデータセンターから学習に用いるデータが利用可能
3.2 Learning
  • Shardingでの学習について
    • 力尽きました…，原文を当たって下さい
3.3 Data Protection
  • 本機能は，Googleのprivacy policyに則って実装
    • 学習後，メールの特徴量は削除
  • モデルのチューニングやデバッグには，チームメンバーのアカウントのみを利用

4.Result

  • 「どのメールが重要か」を判定する基準には，まだまだ研究の余地がある．
    • ユーザーが個々のメールの重要性を評価できる仕組みがあるとよいのかも？
  • Each User ModelはGlobal Modelよりも遥かに性能が良い．
  • Google従業員による実験の結果，Gmail Priority Inboxを利用することで，メール処理に費やされる時間を6%短縮させることが出来た．
    • 非重要なメールに限れば13%短縮させた．