by netflix blog

Innovating Faster on Personalization Algorithms at Netflix Using Interleaving

と

Under the Hood of Wantedly’s Recommender System - 推薦システムの評価の裏側

を参考にさせていただきました。

まず

interleavingというのは、

複数のロジックをごちゃまぜにして全員に出しちゃう手法です。

従来ABテストはユーザーの5%には新しいロジック、残りは従来のロジックというものでした。

これで、p値の収束が10倍とか速いらしいです。

よさそうですよね！

デメリは

interleavingを実現するためのエンジニアコストはあるようです。

さらに、テストが短い故に測れないretentionとか、全員にだすので、あまりに悪いロジックの退散とか、計測とか

この辺は課題な匂いがします。

といったところです。

あらためてinterleavingとは？

interleavingについて

interleavingとは、新しいアルゴリズムと古いアルゴリズムを同時に交互に出し、どちらが良い反応するかを評価することです。
推薦システムを評価する上で、interleavingは非常に有効な手法になります。
私は、Netflixのブログで手法を知り、ウォンテッドリーに導入したところ、非常に効果があり、現在は全ての推薦の一次評価で利用するようになっています。導入したアルゴリズムは、Team draft interleavingです。およそA/Bテストよりも10倍早く評価することができます。

p値収束までの時間が速いので、試したいロジックが山積みな会社は検討したいですね。

逆に、月に一回程度なら従来でも十分って感じでしょうね。

netflixでは二段階の手法を使っており、素早くロジックを選定、枝刈りするのにinterleavingをそして、じっくり評価するために

従来のABtestを、長期的な評価軸(metric)でテストしているそうです。そういう使い分けをしているんですね。

最大の特徴はinterleavingだとユーザー全員に出すわけです。ユーザーを分割しないので、

分割の際に生じ得る不公平さがなくなります。ABテストやっているとどうしてもヘビーユーザーが偏っている

のではないか？だから5回平均と取るとか、そもそもヘビーユーザーを弾くなどの措置とかをとったりしますが、

不十分な気がしてきます。それを解消してくれるのがinterleavingです。

As an alternative to traditional A/B testing, we can use a repeated measures design for measuring preference for Coke or Pepsi. In this approach, the population would not be randomly split. Rather, each person would have the option of either Coke or Pepsi (with neither brand having identifiable labels but yet still being visually distinguishable). At the conclusion of the experiment, we could compare, at the level of a person, the fraction of soda consumption for Coke or Pepsi. In this design, 1) we remove the uncertainty contributed by the wide range in population-level soda-consumption habits, and 2) by giving every person equal weight, we reduce the possibility that the measurement is materially affected by an imbalance in heavy soda consumers.　　　　　　https://netflixtechblog.com/interleaving-in-online-experiments-at-netflix-a04ee392ec55

で、肝心なのは、アルゴリズムを混ぜるときの混ぜ方で

netflixでも一覧行の中で左のものは当然、目立つしよくクリックされるわけで

うまいこと混ぜないといけないのです。ゆえに

For interleaving to yield valid measurements, we must ensure that at any given position in a row, a video is equally likely to have come from ranking algorithmAorB.

といって、混ぜ方が肝になってきて、その実装がinterleavingの真髄で、とっても難しくないです。

野球のドラフトみたいな感じです。

中身のteam draftとかの手法を知るには

A/Bテストよりすごい？はじめてのインターリービング(gunosy)

A/Bテストより10~100倍効率的なランキング評価手法　インターリービング（Interleaving）のまとめと実践

あとは、ちゃんとトラッキングできるようにするだけですね。

なので、この混ぜ方を実装するのと、従来のトラッキングタグをつけること

あとは、（ついでに野球にちなませて）コールド負け判定、システムとして組み込みくらいですね。

これだけで、

・サンプル数が圧倒的に少なくて済む！

・p値の収束期間が10倍から100倍！

という恩恵が得られるのであればやりたいですよね！

さらに、

netflixはもともち、短期的なquickな評価方法を探していて

その評価方法で得られたmetricは、長期のABTestでもそれなりの違いがでないこと！というような評価方法を

さがしていました。

実際、interleaving結果とabtest結果の間には強い相関があると、結論づいていますので、

短くinterleavingやった結果が、ほとんどの場合、abtestでも似通った結果が得られる

ということになりますね。

評価の方法はこちらをすばらしくまとめられています。(レコメンドつれづれ　～第3回 レコメンド精度の評価方法を学ぶ～)

以上です