Innovating Faster on Personalization Algorithms at Netflix Using Interleaving

[masatakashiwagi]

Innovating Faster on Personalization Algorithms at Netflix Using Interleaving

• Authors:

• Link: https://netflixtechblog.com/interleaving-in-online-experiments-at-netflix-a04ee392ec55

• Date: Nov 30, 2017

どのようなもの？

議論はあるか？

次に読むべき記事は？

備考

[masatakashiwagi]

For instance, the Top Picks row on the homepage makes recommendations based on a personalized ranking of videos, and the Trending Now row also incorporates recent popularity trends.

Netflixも実践しているように，トップピック（ピックアップ）では，パーソナライズしたものをレコメンドエンジンで提供し，トレンドでは，最近の人気を反映させる（比較的新しいコンテンツを対象にランキングを作るのが良さそう）

[masatakashiwagi]

Netflixでの開発プロセス:

1. 新しいランキングアルゴリズムを作成し，そのパフォーマンスをオフラインで評価する
2. A/Bテストを活用して，会員の満足度を最大化するというビジネス上の目的に沿ったコア評価指標のオンライン測定
   • 評価指標: 月々の契約維持率や会員のストリーミング時間などがある
   • 最適化されていくと，評価指標の勝敗を決める上で，大きなサンプルサイズと長い実験期間が必要

2段階のオンライン実験プロセスの考案:

• 第1段階: 多数のアイデアの中から，良いアルゴリズムを選択するために，高速なプルーニング（剪定）を行う
  • アプローチ: メンバーの好みをより正確に測定するためにInterleavingを使う
• 第2段階: 絞り込んだアルゴリズムを用いて従来のA/Bテストを行う

[masatakashiwagi]

• 第1段階は数日で終了し，最も有望なアルゴリズムの小さなグループが残る
• 第2段階では，これらのアルゴリズムのみを使用して，A/Bテストを行うが，従来のA/Bテストに比べて、実験全体に割り当てるメンバーの数を減らし，実験期間を短縮することができる
• 当たりをつけて，より高速に実験を行う

[masatakashiwagi]

Using a repeated measures design to determine preferences

• この方法では，母集団を無作為に分割するのではなく，各人にCokeとPepsiのどちらかを選択してもらう
• 実験の終了時には，一人一人のレベルでコーラとペプシのソーダ消費の割合を比較することができる
• このデザインでは，1）人口レベルでのソーダ消費習慣の幅広さによる不確実性を排除し，2）すべての人に同じ重みを与えることで，ソーダを大量に消費する人の不均衡によって測定結果が重大な影響を受ける可能性を低減することができる

[masatakashiwagi]

A/BテストとInterleavingの違い

• 従来のA/Bテストは，ランキングアルゴリズムAとBを2つのグループを選んで実験を行う
• Interleavingでは，1つのグループを選んでアルゴリズムAとBのランキングをブレンドして生成したランキングで実験を行う．これにより，ユーザーに選択肢を並べて提示し，ランキングアルゴリズムの好みを判断することができる→User Preferencesを見る
• ランキングアルゴリズムの勝敗は，どちらのアルゴリズムがより多くの時間を視聴したかを測定することで算出する
• どのアルゴリズムがどのコンテンツを出したかは把握できるようにしている

[masatakashiwagi]

ポジションバイアスの問題

• 2つのランキングアルゴリズムAとBからInterleaving setsを作る上で，ポジションバイアスの問題を考慮する必要がある
• ドラフト方式で順番に並べていく
• どちらのランキングアルゴリズムがリストの最初になるかはランダムに決定する

[masatakashiwagi]

Interleavingの感度を従来のA/Bテストと比較する

• 2段階のオンライン実験プロセスでinterleavingを使う意味は，かなり少ないサンプルサイズでより優れたランキングアルゴリズムを確実に特定する必要があるから
• これを評価するために，2つのランキングアルゴリズムAとBの相対的な良し悪しがわかっている場合を考える
• Interleavingの感度を従来のA/Bテストと比較するために，bootstrap subsamplingで様々なサンプルサイズでUser PreferencesとA/Bメトリクスを計算した
• アルゴリズムの良し悪しを95%で検出するために，より少ないサンプルサイズで閾値を超える指標は，より感度の高い指標と言える→100倍以上Interleavingの方が少ないサンプルサイズで済む

• We find that interleaving is very sensitive: it requires >100× fewer users than our most sensitive A／B metric to achieve 95％ power.

[masatakashiwagi]

interleavingメトリクスとA/Bメトリクスとの相関関係

• 図の各点は本番のアルゴリズムに対する異なるランキングアルゴリズムの測定値を示す
• interleavingメトリクスとA/Bメトリクスとの間で相関関係が見られるので，interleavingでのUser PreferencesがA/Bテストの成功を予測することができる

[masatakashiwagi]

Conclusion

• interleavingにより実験を加速させることができるが，フレームワークの実装にはかなりの手間がかかる．また，整合性チェックや問題の自動検出のための手間がかかる
• interleavingによって最良のアルゴリズムを素早く見つけることができるものの，あくまでユーザーの好みを相対的に測定するものであるため，retentionのようなメトリクスの変化を直接測定することはできない．これは2段階目のA/Bテストで見ていく必要がある

[masatakashiwagi]

コード

• https://github.com/mpkato/interleaving

[masatakashiwagi]

NOKIAの事例

• Improving Search Through Efficient A/B Testing

G-test

• カイ二乗検定は近似でG検定は対数尤度を直接計算する

結果

• 上記は以下の論文で，「サンプルが類似していて混同しやすい場合はインターリーブが有効で，アイテムがより明確な場合はブロック化が望ましい」とのこと
• A systematic review of interleaving as a concept learning strategy

This idea was supported by the findings of Carvalho and Goldstone (2014a) who found interleaving to be helpful if exemplars were similar and therefore easily confused, but blocking to be preferable if items were more distinct.

Putting category learning in order: Category structure and temporal arrangement affect the benefit of interleaved over blocked study, Memory & Cognition, 42, 481–495.