社内で国際会議論文読み会を開催しました

こんにちは。ウェブアプリケーションエンジニアのid:syou6162です。はてな社内では機械学習や自然言語処理に関する論文読み会を定期的に行なっています。

これまでは最新の話題を追うという意図でその年に出た論文を読んでいましたが、今回は趣向を変えて「最新の論文に限定せず、業界内でディファクト/ベースラインとして使われる手法/論文/ツールを紹介しよう」というテーマで開催しました。このエントリでは、読み会で紹介された論文を簡単にレポートしていきたいと思います。

A contextual-bandit approach to personalized news article recommendation

  • 著者: Lihong Li (Yahooo! Labs), Wei Chu, John Langford, Robert E. Schapire
  • 紹介者: id:syou6162
  • 論文PDF: http://rob.schapire.net/papers/www10.pdf
  • 背景:
    • 情報推薦ではCTRの高いアイテム(この論文ではニュース記事)を重点的に提示していきたい
    • どのアイテムがCTRが高くなるか分からない状況で、よいアイテム(最終的にCTRが高い)を提示したい。代表的な手法として多腕バンディットアルゴリズムがある
    • 多腕バンディットアルゴリズムでは以下の2つのトレードオフを考慮しながらアイテムを選択する
      • 1: CTRの低いアイテムよりも高いアイテムを多く出したい(exploit)
      • 2: 初期はどのアイテムのCTRが高いか分からないので、色々なアイテムを試しに出してみる必要がある(explore)
    • 多腕バンディットの基本的なアルゴリズムにはEpsilon-GreedyやUCBがある
      • UCBは期待利得だけでなく、各アイテムについてどれだけ情報が得られているかも考慮してアイテムを選択する
      • 具体的にはUpper Confidenceが一番大きいアイテムを選択する
  • この論文で解きたい問題:
    • UCBではアイテムに関する特徴(例: 記事のカテゴリ)や提示するユーザーに関する特徴(例: 性別/年齢)を考慮することができない
    • これらの特徴のことを論文ではコンテキストと呼ぶ
    • コンテキストを考慮すれば、よりCTRが高くなるアイテムの提示ができるのでは
  • 解いている方法:
    • コンテキストを考慮した多腕バンディットアルゴリズムを提案
    • UCBを基本として、期待報酬をコンテキストで線形回帰で予測
    • 報酬がクリックされた/されていないといった0/1で表現される場合、線形回帰でなくロジステック回帰でやる方法も提案されている
  • 解いた結果:
    • UCBなど既存手法よりも高いCTRを達成、特にチューニングのデータ数が少ない場合に既存手法との差が顕著
    • オフラインで評価する方法も提案
  • 所感:
    • これまで馴染がなかった多腕バンディットで何をやっているか分かってよかった
    • クリックされた/されないのように報酬が比較的すぐ得られるのとは違う問題設定(例: 旅館の広告を提示して、実際の予約が発生するまでに一ヶ月かかる)の論文も紹介しました
    • アイテム数が多い場合にどう対応していくかといった問題を今後調べてみたい

LightGBM: A Highly Efficient Gradient Boosting Decision Tree

  • 著者: Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu
  • 紹介者: id:alpicola
  • 論文PDF: https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree
  • 背景:
    • 勾配ブースティング木で、データサイズが大きいまたは特徴量数が多い問題設定でも効率よく解けるようにしたい
    • 勾配ブースティング木で一番時間がかかるパートは、決定木の学習の中で良い分岐を見つけるところ
      • 一つのノードの分岐を決めるのに、素朴なやり方だとO(n_\text{feature}n_\text{data}\log(n_\text{data}))
      • 前もって特徴量ごとのヒストグラムをO(n_\text{feature}n_\text{data})で作成しておくことで、一回の分岐はO(n_\text{feature}n_\text{bin})にできる (n_\text{bin} はヒストグラムのビン数)
        • なおビン単位での分岐を行うので最適な分岐になるとは限らない
  • 提案手法:
    • ヒストグラムベースのアルゴリズムを下記の2つのテクニックを用いて高速化する
      • Gradient-based One-Sided Sampling (GOSS)
        • 勾配が小さくなってるデータポイントに対しては、すでによく学習できていると考えられる
        • 勾配が大きいデータポイントを中心に学習して、考慮するデータ数を減らしたい
        • 勾配が小さいデータをそのまま無視してしまうと、データの本来の分布と変わってしまって精度に影響があるので、サンプリングするようにして、サンプリング率の分だけ分岐の利得計算での重みを増やす
        • 精度をあまり犠牲にすることなくデータ数を減らせる
      • Exclusive Feature Bundling (EFB)
        • 高次元のデータは一般にスパース
          • 個々の特徴量が同時に非ゼロの値を取らない (exclusive) ものが多い
        • Exclusiveな特徴量なら一つにまとめて (bundle) しまって構わない
          • それぞれの特徴量のヒストグラムを横に並べて一つとみなす
        • Exclusiveな特徴量をまとめるのは、グラフの彩色問題と等価でNP hardだが、greedyなアルゴリズムでそこそこうまくいく
        • 完全にはexclusiveでない (同時に非ゼロになる時が稀にある) 場合も、まとめてしまっても精度に影響がないことが多い
        • O(n_\text{feature}n_\text{data})な計算をO(n_\text{bundle}n_\text{data})にできる
  • 結果:
    • XGBoostや確率的勾配法と比較
    • GOSSやEFBは近似を含んでいるが、XGBoostや確率的勾配法と比べて精度の悪化はなかった
    • GOSSを有効にした場合に学習時間に対する予測のパフォーマンスが、有効にしない場合やXGBoostと比べてとてもよい
    • EFBのみでも、XGBoostでメモリを使い切ってしまうような巨大なデータセットに対する学習ができる
  • 所感:
    • 読み会では勾配ブースティングの原論文やscikit-learnでの実装、XGBoostの実装も軽く紹介
    • パフォーマンスのボトルネックになるところを真正面から改善する手法が提案されていてよい
    • 一方ドキュメントやコードベースにあたってみると、GOSSはデフォルトオフだったり、FEBもそんな大きい扱いではなかったり
      • 他にもいろんなところを頑張っていそうで、理論的な結果とセットで出しやすいのがこの2つだったのかも

The learning behind gmail priority inbox

  • 著者: Aberdeen, Douglas, Ondrej Pacovsky, and Andrew Slater.
  • 紹介者: id:tanishiking24
  • 論文PDF: https://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/36955.pdf
  • 背景:
    • Gmail のユーザーは日々多くのメールを受け取っている。
    • 自動的にユーザーにとって重要なメールを選び出すことは、情報過多に溺れるユーザーにとって有用。
  • この論文で解きたい問題:
    • メールの重要度の予測というタスク自体は珍しいものではないが、Gmailの抱える多くのユーザー一人ひとりに適した予測モデルを構築し、さらに日々オンライン学習によりモデルを更新するという非常な大規模な処理を行うために、シンプルなモデルやシステムの構築を行う。
    • bigtableを用いた分散機械学習システムの構築の話も少し記載されていたが、今回は学習モデルの評価のみを紹介した。
  • 解いている方法:
    • 各ユーザー/メールから抽出できる特徴量として以下のものが挙げられる。
      • Social feature メール送信者とメール受信者の関係性を表す特徴量
      • Content feature ユーザー行動と大きな相関を持つメールヘッダや含まれる単語など
      • Thread feature メールのやりとりに関する特徴
      • Label feature ユーザーによって手動でメールに対してつけられラベル(重要ラベルなど)を用いた特徴量
    • ユーザーにとってメールの重要度として、「ユーザーがあるメールを受け取ってT秒以内に、そのメールに対してある行動aを起こす確率」を予測する。
      • ここで「ある行動a」は、メールを開く/返信する/ラベルをつける など
    • グローバルなモデルと各ユーザーごとにパーソナライズされたモデルの和を用いたロジスティック回帰により予測を行う。
      • グローバルなモデルとパーソナライズされたモデルを組み合わせることで精度の向上が見込める。
    • オンライン学習アルゴリズムには Passive-Agressive(PA-Ⅱ) を用いてモデルの重みを更新する。
      • PA-Ⅱ を用いることで激しいノイズに対して頑健なモデルの更新・ユーザーのアクションごとにどれくらい重みを大きく更新するかを分別できる。
      • 例えば以下のような感じ
        • メールを開くというアクションは、そのメールが重要であるという根拠として弱いため、重みの更新は控えめに行いつつ
        • メールに重要ラベルを付与するというようなアクションは、そのメールが重要だという根拠として強いので、自信を持って大きく重みを更新
    • 最終的に予測した重要度が閾値よりも大きい場合、そのメールに重要ラベルを付与する。
    • メールの重要度予測を分類タスクではなくスコアリングとして落とし込んだのは、最終的に重要ラベルをつけるかどうかを閾値の変更により素早く調整するため
      • 閾値の調整を完全にアルゴリズム任せにするのは難しくユーザーの行動によって閾値を調整するとのこと。詳しい方法は論文には記載されていなかった。
  • 解いた結果:
    • 実験では80±5%のaccuracyで重要なメールを予測することが出来た
    • また重要なメールの予測では、false negative(重要なメールに重要ラベルがつかない)が、false positive(重要でないメールに重要ラベルがついてしまう)よりも大きくなって欲しいのだが、閾値の調整によりfalse negative の値が false positive の3~4倍にまで調整することが出来た。
  • 所感:
    • gmailのような大規模なサービスにおける、ユーザーごとに提供されるリコメンドシステム(計算コストがばかにならないはず)がどのようなモデルによって実現しているのか気になり読んでみることにした。
    • メールの重要度として、受信からアクションを起こすまでの時間を用いるのは面白い
    • PA-Ⅱ を用いたオンラインでのモデルの更新はシステムの特性をうまく活かしているなと感じた。
    • かなり古い論文なので、現在のpriority inboxのアルゴリズムがどのようになっているのか気になるところ

まとめ・感想

古典的な論文や比較的使われるようになったツールに関する論文を読みましたが、気が付くと3時間ノンストップでディスカッションしており読み会は大変盛り上がりました。はてなでは今後も国内外の学会の論文読み会を定期的に行なっていこうと思います。