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.

Size: px

Start display at page:

Download "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."

やすはるねごろ
7 years ago
Views:

1 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, 羽藤研秋季集中論文ゼミ 2 日目 #7 2011/10/17 16:20- 発表者 :M2 柿元

2 目次 1. The Gmail Priority Inbox 2. The Learning Problem 2.1 Features 2.2 Importance Metric 2.3 Models 2.4 Ranking for Classification 3. Production 3.1 Prediction Time 3.2 Learning 3.3 Data Protection 4. Results

3 Abstract Gmail 優先トレイはユーザーのメールに対する行動を確率的に予測しランク付けしている重要度というのは個人性が高いためユーザー毎に統計モデルの学習によってこの予測を試みたここでは 100 万ものモデルのオンライン学習とそれらの効率的な構築を試みている Gmail 優先トレイ Google が提供する Gmail 新機能ユーザーにとって重要なメールを自動的に選び出し受信トレイのトップに表示する. 振り分けられたメールに対してユーザー自身が再分類しなおすこともできる. 重要と判断された未読メールユーザーによるつきのメールその他のメール

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

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

6 2.2 Important Metric 優先トレイの目的はユーザーの明示的なラベリング無しにメールをランク付けすることランク付けの基準はユーザーがメールに対してどのような行動をとるかユーザーがメールに対して ( メールが届いてT 秒以内に ) いかなる行動を起こすかを確率的に求めたい確率モデルの定義時間 t の時 a という行動をとる確率はメールの特徴とユーザーが Gmail にアクセスしたかどうかに依る. ここで a メールに対する行為 A 重要度を示す行為の集合例えば open, replies, manual corrections など t メールが届いてから行動を起こすまでの時間 f メールの特徴を表すベクトル s ユーザーがメールを見る機会を持つことがあったかどうか

7 2.2 Important Metric 予測誤差の定義 T min 届いたメールにアクションを起こすまでの最小時間 (24 時間以内 ) T max やり取りに必要と思われる期間またメールの保管処理が可能な期間メールを開ける機会がなかった or T min,t max 間に行動を起こさなかったメールに対し何らかの行動を起こしたその他

2.3 Models ユーザーがメールに対して行動を起こす確率を以下のように定式化線形ロジスティック回帰モデル (Linear logistic regression model) を使う global model( 全ユーザー共通のモデル ) と user model( ユーザー固有のモデル )

8 2.3 Models ユーザーがメールに対して行動を起こす確率を以下のように定式化線形ロジスティック回帰モデル (Linear logistic regression model) を使う global model( 全ユーザー共通のモデル ) と user model( ユーザー固有のモデル ) を足し合わせることで global model の膨大なデータと user model のデータ丌足を解消する p: ユーザーが行動を起こす確率 n: 特徴次元数 k: ユーザーの特徴次元数 g: global model の重みベクトル w: user model の重みベクトルユーザーが何らかの行動を起こす確率

2.3 Models 大量のノイズを処理する為に重みベクトルの学習にはオンライン学習である PA-II を利用 Online Passive-Aggressive Algorithms メール一通につきメール受取時に一度だけ global model と user model の重みベクトルが更新される i 回更新された重みベクトル (user model の場合 ) は補足

9 2.3 Models 大量のノイズを処理する為に重みベクトルの学習にはオンライン学習である PA-II を利用 Online Passive-Aggressive Algorithms メール一通につきメール受取時に一度だけ global model と user model の重みベクトルが更新される i 回更新された重みベクトル (user model の場合 ) は補足 Passive aggressive オンライン学習の枠組みのひとつ損失関数マージン ( 分割する超平面との距離 ) この設定で round1 での更新は次の条件付き最適化問題となる e: 誤差値 C: 正規化パラメータ. 更新の aggressive さを調整するラベリングの確信度みたいなものを表すためにメールごとに調節 ε: hinge-loss tolerance もしくは passive さを示す Cが大きいほど学習による更新幅が大きくなり直前のメールからの学習に予測がひきづられやすくなる Cはuser modelの方がglobal modelより大きく直近のuser modelは大きい値をとる十分に学習されていないuser modelはcを大きくしている ( 学習を促進させるため ) w t 1 w Aggressive w Passive t t 1 w t y t 更新を促進する t x t Xt 入力データ l t 損失関数 C パラメータ ( 正 ) 損失がない場合 τ=0

10 補足 : オンライン学習データを 1 つづつ読み込んでそれまでの学習結果を更新する 2 つの利用局面 1. データ全体は保持しているが学習を 1 データ毎に行う 2. データが 1 こずつ時系列としてやってくるこの場合はストリームという. 訓練データを受け取る毎に簡単なパラメータ更新を行うだけで良いので計算時間やメモリの効率が良いオンライン学習の定式化以下 1,2,3 を時刻 t=1,2,,t で繰り返す 1. 時刻 t において仮説 ht( ここでは重みベクトル w) 入力データ xt 正しい結果データ yt が不えられる 2. 仮説 ht による結果 h (t) (xt) を計算しその後で yt との比較を損失関数 l によって行うつまり損失関数 l(h (t),(xt, yt )) を計算. 3. 損失関数 lの値に応じてh (t) を更新し新しい仮説 h (t+1) を求める T 最終的な目的は累積損失 ( t) l h, x, y を最小化すること. t 1 t t データ x t 識別関数 h (t) 予測 h (t) (x t ) 更新 : h (t) h (t+1) 正解 ( 実測 ) y t

11 2.4 Ranking for Classification さらに前述した s に閾値を個人毎に設定したどのメールが重要でまたはそうではないのか判断するため個人毎に適切に閾値を設定するのは困難であるメールを開くことは重要度が高いことを示すとしたが (2.2) 実際は重要だから開くのではなく興味を惹かれて開くことの方が多いまた重要なメールを重要でないと判断される ( 誤検出 ) ことはユーザーにとって非常に困る事態である ( 逆はそうでもない ) 重要なメールに判定されるメールの量はユーザーによって大きく異なるユーザーが閾値を調節できるようある程度の干渉できるようにしたマークなどをつけるユーザーが一定の基準で重要マークを使用していることが認められたら閾値を更新する

12 3. Production 100 万ものユーザーの学習に拡大することは困難モデルを保持管理するために bigtable 1 に改良を加えた形で利用 3.1 Prediction Time 1 big table Google の大規模なサーバー上の大量なデータを管理する為に設計されたデータベースシステム全てのデータセンターから全てのユーザーのスコアリングが可能な設計が求められるどのデータセンターがどのユーザーアカウントを扱うのか予測することは困難 bigtable はランキングを行うためのモデルの複製更新を行うために用いられモデルの更新に用いられるリソース管理とリアルタイムでの実行を実現した詳しく言うとメールの特徴とそのメールに対するユーザー行動を統合ユーザー単位で同じレコードにデータを管理

13 3.2 Learning Sharding(= データを複数サーバーに分割して保持すること ) してモデルの学習を行うことで実行を容易にしている各コアが user model の fraction をそれぞれ更新している Bigtable はスコアリングされた user:message-id レコードにグローバルアクセスすることで効率的なデータ管理を実現 100 万ものユーザーのモデルの読み書きをネットワーク上で行えないので RAM に可能な限り多くのモデルをローディングし更新作業をひとまとまりに処理することが必要以上の作業により最終的にコア 1 台ごとの単位時間あたり ( 秒 )35 名を計算可能にした

4. Results Global model の対数オッズスコアのヒストグラム緑は重要なメール赤は重要でないメール線形回帰モデルを使用すると自然なランキングが行われていることを実証閾値の設定により検出漏れが誤検出の 3-4 倍メールの重要度の判断基準に関しては

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

$of users の統計データを計算データ量が小さいので早いメッセージの特徴データ全体をスキャンする更新された user model 全てをひとまとめに bigtable にかきこむ Fraction of users が利用可能な各コアに不えられこの fraction はさらに断片化されて (shards of users) ひとまとめに RAM に入力される最終的にコア 1$

17 3.2 Learning メールを評価する為にユーザーがGmailを最後に立ち上げたのはいつだったのか知りたいメッセージはuser:message-idに従って並んでいるので全てのメッセージを読む必要が生じる user modelのshardにごとに 2つの命令を実行する必要がある First pass second pass finally 最後の action time と shard of users の統計データを計算データ量が小さいので早いメッセージの特徴データ全体をスキャンする更新された user model 全てをひとまとめに bigtable にかきこむ Fraction of users が利用可能な各コアに不えられこの fraction はさらに断片化されて (shards of users) ひとまとめに RAM に入力される最終的にコア 1 台ごとの単位時間あたり ( 秒 )35 名を消化可能となった

様々なミクロ計量モデル†

様々なミクロ計量モデル† 担当 : 長倉大輔 ( ながくらだいすけ ) この資料は私の講義において使用するために作成した資料です WEB ページ上で公開しており自由に参照して頂いて構いませんただし内容について一応検証してありますがもし間違いがあった場合でもそれによって生じるいかなる損害不利益について責任を負いかねますのでご了承ください間違いは発見次第継続的に直していますがまだ存在する可能性があります 1 カウントデータモデル