The Learning Behind Gmail Priority Inbox読んだメモ
The Learning Behind Gmail Priority Inbox(pdf)
GmailにおけるPriority Inbox（日本語だと優先トレイ）に関する論文（というよりもメモ書き）。
Feature
Featureの量は多いがカテゴリ分類できる。
- Social features : 送信者と受信者間の交流（例：送信者のメールの何割を受信者が読んだか）
- Content features : 受信者のメールに対する行動に対応するようなヘッダーや最近の単語?(recent term)
- Thread features : ユーザがそのスレッドを始めたかどうかみたいな情報
- Label features : ユーザのフィルタによって付けられたラベルの情報を分析
これらfeatureを学習前に計算して保持しておく。連続値の特徴はそのfeatureのヒストグラムに対してID3で二値変換?
Importance Metric
「我々の目標はメールにランクをつけつつ、ユーザがメールが送られてからT秒で反応する確率を予測する事である」らしい。
モデル化に際してはを予測する。
aはメールに対して行われたアクション、Aはそのメールが重要であることを示すアクションの集合（例：読む、返信する、修正する）、tは受信からアクションまでの時間、はfeatureのベクトル、sはメールを見たユーザ。
はユーザがメールに対して行動するまでの時間であり、モデルのアップデート頻度でもある（正確にはモデルのアップデート頻度の最速時間だと思う。例えばこれが10分だったら少なくとも5分ごとにモデルが更新されることはない。）。これは24hより小さい。
はどの期間までを考慮すべきかという制約と、featureをどれぐらいの間まで利用可能な状態として保持すべきかの制約。なのでT_{max}以上かかって行われたアクションが訓練データには入らない。
予測誤差は次のようになる。
Models
ロジスティック回帰。trasnfer learning[1]を使うとか書いてある。
featureの数はn、ついでにk個のユーザ固有（パーソナルモデル）のfeatureを使う。グローバルモデルのパラメータgはパーソナルモデルがアップデートされるときは固定されている。wはパーソナルモデルのパラメータであり、グローバルモデルとの差分だけ持っておく。こうしておくと新しいfeatureが加わった時などに素早く対応できるらしい。
passive-aggressive update + PA-2 regression variant（らしい。全然判らないのでスルー）
メール一通ごとにグローバルモデルと受信者のパーソナルモデルをアップデートする。ユーザiのパーソナルモデルアップデートは次のようになる。
eは誤差、Cはアップデートの"aggressiveness"を調整する正則化パラメータ、はアップデートの"passiveness"を調整するhinge-lossのパラメータ。
実際にはユーザ固有のモデルで総じてCが大きいらしい。
Ranking for Classification
Priority Inboxは分類として解くよりランキング（というよりスコアに対してユーザごとに閾値を決めて判定する手法を指していると思われる）として解くほうがいいと考えているらしい。何故なら閾値の素早い調整はユーザのシステムに対する印象に非常に重要だから。
しかしユーザが幸せになれるような閾値を自動的に決めるのは難しい。例えば、メールを開くというアクションはメールの重要性を強く示すアクションだが、大抵のユーザがユーザはたくさんのメールを開くのは「重要だから」というより「興味を持ったから」という理由に基づいている。また、SPAM判定とは対照的に、ユーザはfalse negative（重要なメールがPriority Inboxに入らない事）よりもfalse positive（重要でないメールがPriority Inboxに入る）を好まないだろう。（この部分、一般的なSPAM判定におけるfalse positiveは「普通のメールがSPAMと判定されること」を指すと思うのだが、それだと文意と反するだろう。誰だってSPAMメールが正しく判定されない事より普通のメールがSPAM判定される方が困る）
大量のメールを使った実験から明らかになったのは、ユーザの嗜好の多様性、すなわち、重要なメールとの相関性を説明できないようなユーザのアクションだった（メールがnoisyである事を差し引いても学習が非常に難しかったのだと思われる）。よって、閾値を完全にアルゴリズム任せにするのではなく、ユーザにある程度修正してもらうことにした。ユーザがmarks messages in a consistent direction(ここよく分からなんですけどあの謎のマークか)したらリアルタイムで閾値を変化させる。
Prediction Time , Learning
bigtableとかの話。
