Gmail の優先トレイの論文を読んだ

最近、会社のグループウェアの通知がやたらと多い。人によっては全ての通知を見ているらしいんだけど、自分の場合は自分宛て通知はみるけど、それ以外の通知は一部しか読んでない。どうせ一部しか読まないのであれば、できるだけ価値のある通知を読みたいので、通知の中から読む価値の高い上位 $n$ 件をフィルタしてくれるプログラムを書きたい。

そういうわけで、偉大な先駆者である Gmail の優先トレイのアルゴリズムに関する論文『The Learning Behind Gmail Priority Inbox』を読んでみた。

Gmail 優先トレイ

優先トレイは、ユーザーごとの統計モデルを用いて、メールを重要度でランキングすることにより、information overload を軽減する試みである。
チャレンジ:
- メールの重要度をユーザーの明示的なラベリングなしに推定する
- 非定常的かつノイジーな訓練データを扱える訓練手法を探す
- 訓練データの要件を減らすモデルを作る
- per-user かつテラバイト級のデータを保存・処理する
- 分散かつ障害耐性を備えた予測プログラムを書く
考え方は Gmail のスパム検出と共通するものが多いが、何を重要と見做すかがユーザーによって大きく異なるため、重要度のランキングはスパム検出よりも困難であり、高度なパーソナライゼーションが要求される。

素性

Gmail では数百もの素性を使っているが、それらは少数のカテゴリに分類できる。
Social features
- 送信者と受信者の間のインタラクションの度合いに基づく素性
- 例: その人が送ったメールのうち、その受信者によって読まれたメールの割合
Content features
- 受信者がそのメールに対して行うアクションに強く相関するヘッダや recent term に基づく素性
- 例: サブジェクトに含まれるある recent term の割合
- (recent term に限定しているのは何でなんだろう？)
Thread features
- その時点において、そのユーザーがそのスレッドに対して行ったインタラクションに基づく素性
- 例: そのユーザーがあるスレッドを始めたか否か
Label features
- ユーザーがメールにフィルタを用いて付与したラベルに基づく素性

重要度

ユーザーとメールが与えられたときに、そのユーザーがそのメールを見てから $T$ 秒以内にアクション（開く、返事を書く、アーカイブする等）を起こす確率を、重要度として用いる。

モデル

ロジスティック回帰モデルを用いる。
パーソナライズされたユーザーモデルを学習するためのデータは少ないため、グローバルモデルとユーザーモデルの対数オッズの和を使って予測を行う。
メールの重要度を表す確率 $p$ を以下の式でモデル化する。

ただし
- $n$ はグローバルモデルの素性の数
- $k$ はグローバルモデルに存在しない、ユーザーモデル固有の素性の数
- $\vec{f}$ は素性ベクトル
- $\vec{g}$ はグローバルモデルの重みベクトル
- $\vec{w}$ はユーザーモデルの重みベクトル
重みベクトルは、passive-aggressive を使って更新する。
- 訓練集合に含まれる大量のノイズに耐えるため、PA-II regression variant を用いた。
各メールは、グローバルモデルの更新するために１回利用され、そのメールの受信者のユーザーモデルを更新するためにもう１回利用される。
$i$ 番目のユーザーモデルの重みは以下の式で更新される。