はてなで合同論文読み会を開催しました

こんにちは。ウェブアプリケーションエンジニアのid:syou6162です。

はてな社内では機械学習や自然言語処理、情報検索/推薦に関する論文読み会を定期的に行なっています。

これまでははてな社内に閉じて読み会を行なっていましたが、機械学習や情報検索/推薦の話題は社外の人とも広くディスカッションするのも有益であるので、今回はLINEさんとリブセンスさんのエンジニアの方々を招待して開催しました。このエントリでは、読み会で紹介された論文を簡単にレポートしていきたいと思います。

IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models

  • 著者: Jun Wang (Yahoo! Labs), Lantao Yu, Weinan Zhang, Yu Gong, Yinghui Xu, Benyou Wang, Peng Zhang, Dell Zhang
  • 紹介者: 東山さん (LINE)
  • 論文PDF: https://arxiv.org/abs/1705.10513
  • 背景: 情報検索では生成モデル*1や識別モデル*2がの考え方が主流だが、それぞれメリットデメリットが存在する
    • 生成モデル: BM25やIDFなどのテキスト統計の素性モデルに成功しており理論的にも妥当であるが、それ以外のクリック数などの情報を取り込むことが難しい
    • 識別モデル: クリック数など様々な素性でスコア関数を学習できるが、テキスト情報量などラベルなしデータから有用な情報を得ることが難しい
  • この論文で解きたい問題: 生成モデルと識別モデルの両方を考慮して情報検索タスクの性能をさらに上げたい
  • 解いている方法: 生成モデルと識別モデルの両方をスコア関数に組み込んだGAN(Generative Adversarial Networks)を用いて情報検索に適用する
    • GANではGeneratorが生成モデル相当の役割を果たし、Discriminatorが識別モデル相当の役割を果たす
    • GeneratorとDiscriminatorで相互最適化を繰り返すが、画像のような連続量と異なり文書dは離散であるため、通常のGANのように勾配法が利用できない
    • 強化学習でいうところの方策勾配法(Policy Gradient Method)を用いて最適化を行なう
  • 解いた結果: 情報検索、情報推薦、Question Answeringなど幅広いタスクで適応可能で、既存の手法よりも高い性能を出すことができた
  • (はてな id:syou6162)所感:
    • GANというと画像生成などのイメージが強かったのですが、はてなでも取り扱うことが多い情報検索や情報推薦といったタスクでも高い性能を出せるということを今回の発表で知って興味が湧きました
    • IRGANをベースにGraphGANやCFGANといった発展形も登場、SIGIR2018のチュートリアルでも取り上げられるなどしているので、後続の研究についてもサーベイしたいと思います

Billion-scale similarity search with GPUs

speakerdeck.com

  • 著者: Jeff Johnson, Matthijs Douze, Hervé Jégou (Facebook AI Research)
  • 紹介者: id:takuya-a (はてな)
  • 論文PDF: https://arxiv.org/abs/1702.08734
  • 背景:
    • 画像特徴量や分散表現などの特徴ベクトルは、高次元（数十〜数百次元）になる
    • 高次元ベクトルの正確な近傍探索 (exact search) は、次元の呪いにより、線形探索と変わらない計算時間になってしまう
    • k-means などのクラスタリングでも近傍探索がボトルネックになりがち
  • この論文で解きたい問題:
    • 大量のベクトルの中から、クエリベクトルと最も近い k 個のベクトルを（近似的に）求める問題
    • Billion-scale の高次元ベクトルに対しての近傍探索を高速化したい
  • 解いている方法:
    • 近似近傍探索
    • 代表ベクトルを直積量子化 (PQ; Product Quantization) したもの (PQ code) をキーとした転置インデックスを使う
      • 代表ベクトルに近いベクトルを転置インデックスのリストに入れる
    • クエリベクトルと近い代表ベクトルを exact search（CPU で行う）
    • 転置インデックスのリストの中から近いベクトルを GPU で近似近傍探索
      • 距離を計算したあと、ソートして k 番目までのベクトルを取り出す (k-selection)
      • GPU のシャッフル命令をうまく使って複数のレーンで並列ソート
  • 解いた結果:
    • SIFT1B データセット（10億ベクトル、128次元）で GPU を使う既存手法に対して 8.5 倍速
    • DEEP1B データセット（10億ベクトル、96次元）で CPU (1 thread) を使う既存手法に対して 1500 倍速
  • 所感:
    • GPU を使ったアルゴリズムはまったく知らない世界だったので面白かったです
    • 近似近傍探索は、類似検索やクラスタリングだけでなく、レコメンドなどにも応用できそうなので今後もウォッチしていきます
    • Faiss はとにかく爆速らしくて、近傍探索においてはデファクトのライブラリになりつつあるようなので試していこうと思います

Pretraining Sentiment Classifiers with Unlabeled Dialog Data

  • 著者: Toru Shimizu (Yahoo! JAPAN Research), Hayato Kobayashi, Nobuyuki Shimizu
  • 紹介者: id:syou6162 (はてな)
  • 論文PDF: http://aclweb.org/anthology/P18-2121
  • 背景: Sentiment classificationにおいて、教師データを十分な量用意するのはコストがかかる
  • この論文で解きたい問題: タスクに関連するような教師なしデータをうまく活用することで、教師データが少ない状況でも高い分類性能が出せるようにしたい
  • 解いている方法: 既存手法ではLSTMをタスクに直接的に関係がない言語モデルを使ってpretrainingしているが、本研究ではよりタスクに関連している対話タスクでpretrainingする
    • より具体的には、twitterでのreplyのデータを使って元tweetからreplyを生成するようなencoder-decoderをpretrainingモデルとする
    • replyが付くtweetはより感情に結び付くものが多いため、sentiment classificationにより寄与するのではないかという仮説
  • 解いた結果:
    • 既存のpretrainingの手法よりも高い性能を出した
    • 教師データ数が少ない場合でも既存手法よりよい
  • 所感:
    • 提案手法はすごくシンプルで再現しやすそう
    • pretrainingするデータ量を変えた際にsentiment classificationタスクの精度がどれくらい変わってくるのかも知りたい
    • 個人ブログに詳しく紹介しています

Rank and Relevance in Novelty and Diversity Metrics for Recommender Systems

  • 著者: Vargas Saul, Castells Pablo
  • 紹介者: id:yubessyさん (リブセンス)
  • 論文PDF: http://ir.ii.uam.es/predict/pubs/recsys11-vargas.pdf
  • 背景: 推薦システムにおいて、推薦スコアだけを用いてランキングを生成すると、ランキング中に似たようなアイテムがたくさん含まれてしまう。このような問題に対する手法は多く提案されているが、手法とともに独自の評価指標が乱立し、手法同士を客観的に比較するのが困難であった
  • この論文で解きたい問題: 推薦システムの評価尺度としてのnoveltyやdiversityを統一的に扱うユーザ行動モデルを提案し、推薦システムの評価をより客観的かつ目的に即した設定で行うための指針を示した
  • 解いている方法: いくつかの独立性の仮定の元でユーザーの行動をDiscovery/Relevance/Choiceの3つに分割、それぞれをモデル化
    • 各モデルはシンプルで拡張の余地は大きい
  • 解いた結果:
    • Matrix Factorization/Content-Based Filtering/User-Based Collaborative Filteringなどを対象に提案指標を用いて評価。各アルゴリズムの特徴を捉えているような結果を得ることができた
    • メタ評価(評価指標の評価)なので、人手との一致率のような評価もあるとよさそうだねという議論がありました
  • (はてな id:syou6162)所感:
    • ユーザーの行動モデルから評価指標を導くという考え方は面白かったです
    • 評価指標の提案は他分野(例えば自然言語処理におけるBLEUやROUGE))でも存在し、それぞれの分野で評価指標がどのように進化しているかといった話を議論しました

Offline A/B testing for Recommender Systems

speakerdeck.com

  • 著者: Alexandre Gilotte, Clément Calauzènes, Thomas Nedelec, Alexandre Abraham, Simon Dollé (Criteo Research)
  • 紹介者: id:alpicola (はてな)
  • 論文PDF: https://arxiv.org/abs/1801.07030
  • 背景:
    • 推薦システムをオンラインでABテストするのは時間・コストがかかる
    • もしもログデータに基づいたオフラインABテストによりそれに近い評価ができるなら、アルゴリズムの改善のサイクルを高速化できる
    • しかし既存手法による結果ではバイアスまたはバリアンスが大きくなり評価に用いるのが難しかった
  • この論文で解きたい問題: オフラインABテストのバイアス・バリアンスのトレードオフの改善
  • 解いている方法:
    • 既存手法のcapped importance sampling (CIS) やnormalized capped importance sampling (NCIS) はバリアンスを抑えるために値のcappingを行うが、そこから生じるバイアスについて解析
    • NCISのバイアスが報酬とコンテキストの相関によって大きくなることに着目し、相関が小さくなることを期待してNCISの適用を局所化した拡張PieceNCISとPointNCISを提案
  • 解いた結果:
    • 大規模な推薦システムのログでオンラインABテストとオフラインABテスト (CIS, NCIS, PieceNCIS, PointNCIS) による評価
    • オンライン評価とオフライン評価の相関が0.25 (NCIS) から0.5 (PointnCIS) 程度に向上
    • テストしたい推薦ポリシーのパフォーマンスが現行のものより上かどうかを予測する問題として見た時には、特にrecallが向上
  • 所感:
    • CIS, NCISのバイアスの性質に関する議論に基づいて手法の改善を提案する流れが面白く思ったので紹介しました
    • 現行のポリシーとの差が小さいほど精度よくパフォーマンスを推定できる性質があるので、チューニングがしたい時、また小さいパフォーマンス改善でも利益が大きい時に特に有用ではないかといった議論をしました

まとめ・感想

今回の読み会では情報検索/情報推薦や自然言語処理に関する論文を取り扱いましたが、各社それぞれでどのような応用をしているか/していこうとしているかを議論できて大変盛り上がりました。1論文当たり紹介の時間を45-60分程度確保したので、じっくり議論できたのもよかったかなと思います。

*1:p(d | q)やp(q | d)。ここでdはdocument、qはクエリを表わす

*2:p(r | q, d)。ここでdはdocument、qはクエリ、rはそれらの関連度を表わす