Aberdeen, D., Pacovsky, O., and Slater, A., The Learning Behind Gmail
Priority Inbox, In LCCC: NIPS 2010 Workshop on Learning on Cores,
Clusters and Clouds, 2010.

Gmail優先トレイの学習アルゴリズムの話

1．Gmail優先トレイ
・Gmail優先トレイは，ユーザーの重要度に応じてメールを振り分けてくれる．
・このような順位づけのタスクは目新しいものではない．
・しかし，リアルタイムでの更新，日々数百万ものモデルを数秒単位で更新し続
  ける，といった事象でこのタスクが複雑化している．
  -ユーザーにとってそのメールが重要かどうか，判断基準がユーザーから明示
   的に得られない．
  -非定常でノイズの多い訓練データを取り扱うメソッドを構築すること
  -訓練データの制約を少なくするモデルを構築すること
  -Terabyteに上るユーザー毎の特徴データを保管し処理すること

2．学習上の問題
2.1．特徴量
・メールの特徴は以下の4カテゴリに分類できる．
  -Social features：メールの受信者・送信者間のやり取りに関する情報（例：
   メールの返信率）
  -Content features：ヘッダーや本文に関する情報
  -Thread features：スレッド情報
  -Label features：ユーザーが適用しているラベル情報（フィルターなどの使用）
・メールをランク付けするために特徴の評価値を計算し，その後の学習の為にこ
  れらの値を保管しておく．連続的な特徴は自動的に2値の特徴に分割される．
  Simple ID3 style algorithmで，特徴のヒストグラムに従い分割．

2.2．重要な測定基準
・優先トレイの目的はユーザーの明示的なラベリング無しにメールをランク付けすること．
  ランク付けの基準は，ユーザーがメールに対してどのような行動をとるか．
  -メールに気付いて何秒で[開封するか・返信するか・ゴミ箱に送るか]
【羽藤】7枚目：“その他”とは例えばどんな行動？
  →“メールを開ける機会がなかった”はログインしてなかったこと，“その他”
  はログインしてたけどメールを放置していたこと．

2.3．モデル
・線形ロジスティック回帰モデル
・global model（全ユーザー共通のモデル）とuser model（ユーザー固有のモデ
  ル）を足し合わせることで，global modelの膨大なデータとuser modelのデー
  タ不足を解消する．
・大量のノイズを処理する為に，重みベクトルの学習にはオンライン学習である
  PA-IIを利用．※Online Passive-Aggressive Algorithms
・予測と実測の差を損失関数として，更新の具合をaggressiveとpassiveで調整．
・C（正規化パラメータ，更新のaggressiveさを表す）が大きいと学習を促進さ
  せる．
【羽藤】：Cの更新周期が重要．時間間隔の問題がありそう．グローバルでの最
適化があるはず，今後出してくるかもしれない．

2.4．分類の評価
・メールを開くことは重要度が高いことを示すとしたが(2.2)，実際は「重要だ
  から」開くのではなく「興味を惹かれて」開くことの方が多い．
・また，重要なメールを重要でないと判断される（誤検出）ことは，ユーザーに
  とって非常に困る事態である．（逆はそうでもない）
・ユーザーが閾値を調節できるよう，ある程度の干渉できるようにした．（☆マー
  ク）

3．実用化
データセンターとデータベースシステムの関係．

4．結果
・線形回帰モデルを使用すると，自然なランキングが行われていることを実証．
・閾値の設定により，「検出漏れ」が「誤検出」の3-4倍．
・メールの重要度の判断基準に関しては，研究の余地が残される．
・Each user modelはglobal modelよりはるかに性能が良い．
・Google従業員による実験の結果．Gmail Priority Inboxを利用することで，メー
  ル処理に費やされる時間を6%短縮させることが出来た．重要でないメールに限
  ると，13%短縮させた．

≪捕捉など≫
【瀧口】：新しい人からメールがきたら，どうするんだろう．
  →ドメインとかみてるのではないか．
【斎藤】：東京2050の重要メール（“重要”と書かれたメール）がちゃんと重要
扱いされてなかった(笑) 内容は一切見ないで，メールに対しての反応をみてい
るのがわかった．
【池田】都市的にはこのようなアルゴリズムはどう生かせるのか．
  →人とか交通とかモノとか観測しクラウドサービスに展開する流れ大きくなっ
  てきているので，テキストマイニングしたりといった適用が可能．


---------------------------------------
■全体のまとめ
Gmail優先トレイは，ユーザーのメールに対する行動（開封するか・返信するか
・ゴミ箱に送るか）をもとにその重要度を確率的に予測し，ランク付けしている．
「重要度」というのは個人性が高いため，ユーザーごとにモデル化するのと全体
でのモデル化を合わせて，ユーザー毎の統計モデルの学習によってこの予測を試
みた．ここでは，100万ものモデルのオンライン学習とそれらの効率的な構築を
試みている．結果としては，メールを開くことは重要度が高いことを示すとした
が，実際は「重要だから」開くのではなく「興味を惹かれて」開くことの方が多
いとされるので，メールの重要度の判断基準に関しては研究の余地が残される．
都市の現象を観測するのに様々なデバイスが使われ，大量のデータから文脈を読
み取る必要が出てきているので，将来的な適用範囲など個人で考えていくのもお
もしろいのではないか．
---------------------------------------