froglog

プログラミングや統計の話など

レコメンデーションシステムのオフライン評価、どうやるんですか

カエルなので分かりません、誰か教えてください。

レコメンデーションシステムのオフライン評価について調べてました。 そのメモ的なエントリです。

ここでいうレコメンデーションシステムについてはよくある EC サイトの商品推薦のようなものをイメージしていただければと。 また、オフライン評価とは "一般的な A/B テストのように実運用に影響のある方法" ではなく、過去ログ等を用いてローカル環境でバッチ的に行える評価のことです。

尺度

尺度については以下によくまとまってます。

ここに挙げられている中で個人的に有用そうだと思ったものを列挙。

順序を考慮した精度的な尺度

  • MAP (mean average precision)
  • nDCG (normalized discounted cumulative gain)
  • nDPM (normalized distance performance measure)
  • AUC (Area Under the ROC Curve)

レコメンデーションシステムは複数のアイテムによるリストをユーザに提示することが多いかと思います。 なので単なる再現率や適合率だけでなく、アイテムが表示される順序も考慮されてる方が直感に合います。 これらの尺度ではユーザの嗜好が強いアイテムが上位に来た方が良いとされます。*1

どのくらいのユーザに出るかの尺度

  • user coverage (fraction of users who get recommendations)

どんなに高精度なロジックでも1%のユーザにしか出せないのであれば残念なものになります。 一方でアイテム被覆率は私としてはそんなに重要だとは思ってません。*2 アイテム被覆率見るなら、出方の偏りを見るためのジニ係数的なものまで見るべきでは。

その他尺度について思うところ

  • serendipity は大事なのはわかるけど計測できるのだろうか…
  • diversity はアイテム間の類似度があれば定義できる*3

オフライン評価のバイアス問題

バイアスについて

そういった尺度を使ってオフライン評価したいわけなんですが、私の頭でぱっと考えると以下のような流れになります。

  1. 実運用でログデータを集める
    • どのユーザに
    • どのアイテムが表示され
    • どのアイテムにアクション(クリック、購買等)があったか
  2. 学習データと評価データに分ける
  3. 評価対象のロジックで学習データを学習し、ログに含まれるユーザへの推薦リストを生成
  4. 推薦リストに含まれるアイテムと評価データ中でアクションのあったアイテムを比較し、何らかの尺度を計算

ただしこれだと実運用時にユーザが何を見せられているかによるバイアスがかかってしまいます。 例えばユーザが推薦ロジック X を見てアクションしたことにより得られたログであった場合、アクションのあったアイテム、つまり推薦で当てたいアイテムは当然 X の出力に含まれるアイテムとなり、おそらく X に近いロジックが良いロジックであると評価されやすくなります。

また、過去のログを学習するようなアルゴリズムであればたまっているログの状態が推薦結果に影響し、推薦結果がその後のログの状態に影響するのでバイアスが避けられない。 ログと見せ方(アルゴリズム)は表裏一体ってことですかね。

offline replay

このあたり扱っている論文はいくつかあるみたいですが、bandit algorithm 系でよく見るのがこちらの offline replay という方法。

    1. Li, W. Chu, J. Langford, and X. Wang. Unbiased offline evaluation of contextual-banditbased news article recommendation algorithms. In Proceedings of the fourth ACM international conference on Web search and data mining, pages 297–306, 2011.

すごく乱暴に解説すると、まず一様乱数でアイテム選択するというロジックで実運用ログデータを作ります。 オフラインでログデータに含まれるユーザに対して評価対象ロジックでアイテムを提示し、アイテムが一様乱数から表示されたものと一致しなければ無視、一致したらそのデータだけを用い尺度を得るという方法です。 もともとは bandit algorithm のために考えられたものですが、レコメンデーションにも応用可能です。

が、bandit でいうところの腕の数が多いと精度が下がるため、腕の数にあたるものはレコメンデーションではアイテム数ということになって商品数の多い EC サイトとかだときびしそう。 というのと一様乱数でログを作らないといけないのもネック。

最近の研究

最近の研究ではどうなってるのかと RecSys 2015 の発表で web で PDF で読めるものの評価実験のところを2, 3読んでみましたが、バイアスはあまり気にしてないような実験になってました。 気にしなくていいのか…

とりあえずのまとめ

ここまでで、データがあるのであればオンラインの A/B テスト CTR やら CVR やら見るのがいいのではって気がやっぱりしてきます。

とはいえオフライン評価したいときもあります。 ハイパーパラメータの最適値をだーっと探したりしたいときもあるし、オンラインの評価しかできないのであれば評価対象のアルゴリズムをいきなりプロダクトコードで実装しないといけないかもしれませんし。*4

  • 基本的にオンライン A/B テストで評価する
  • パラメータ調整など比較対象が多いときはバイアス覚悟でオフライン評価をする

というのが現実的な落とし所なのではというのが今のところの結論ですね。 レコメンデーションシステムを扱ってる他の皆さんはどうやってるんだろうか。

*1:並び順でユーザの嗜好が強い順が良いとされる場合が多いが、当て馬を入れた方が良くなるという文脈効果、リストの先頭と末尾が大事だとする初頭性/近親性効果などもある

*2:でもクライアントは気にする

*3:Ziegler, C.N., McNee, S.M., Konstan, J.A., Lausen, G.: Improving recommendation lists through topic diversification. In: WWW 2005, pp. 22-32 (2005)

*4:レコメンデーションシステムの作り方にもよる