はじめに

こんにちは。メディアデータ分析部の飯塚(@zr_4)です。

弊社では現在、複数のニュース形式のアプリケーションを運用しており、各プロダクトでユーザーの趣向にあうような記事リストのパーソナライズを行っています。

f:id:zer4:20181011121613p:image:w150 — 左から：LUCRA、ニュースパス、グノシー

f:id:zer4:20181011135231p:image:w150 — 左から：LUCRA、ニュースパス、グノシー

そのため、記事のランキングに関するA/Bテストをする機会が多々あり「少数のユーザーで高速に有力なパラメータを探したい」というニーズがありました。

今回は上記ニーズを満たすべく、グノシーの本番環境に導入したインターリービングを紹介します。

インターリービングとは

概要

インターリービングは高感度なランキング評価手法です。実験的に、10倍から100倍従来のA/Bテストよりも効率的であることが知られています。*1

従来のA/Bテストにおいて、2つのランキングリストを評価する際は、ユーザを2つの群に分け各々に別々のランキングリストを提示し性能を評価することと思います。

一方で、インタリービングでは、2つのランキングリストを混ぜることで新たなランキングを作成し、同一のユーザー群にそのランキングを提示し性能を評価します。同一のユーザー群で評価することで、極端な振る舞いをする少数のヘビーユーザーの行動に結果が左右されなくなるメリットもあります。*2

f:id:zer4:20181011150941j:plain

ランキングリストの混ぜ方によって、それぞれ名前がついています。代表的なものでは「Balanced Interleaving」「Team Draft Interleaving」「Probabilistic Interleaving」「Optimized Interleaving」があります。なお、2つのランキングリストを1つに混ぜる手法はインターリービングと呼ばれ、3つ以上のランキングリストを混ぜる手法はマルチリービングと呼ばれます。

具体例

各々の手法の詳細は他に譲り、ここでは、Team Draft Interleavingを例に説明します。チームドラフトは名前の通り、プロ野球のドラフト会議と同じような仕組みです。各チームの監督は、欲しい選手に対して以下の選好ランキングを持つと仮定します。

指名順位	監督1	監督2
1	選手A	選手C
2	選手B	選手B
3	選手C	選手D
4	選手D	選手A

ドラフト一巡目では、各チームの監督は抽選(ランダム)によって選手を選ぶ優先度が決まります。ここでは監督1 < 監督2とします。

一巡目
監督2: 選手C
監督1: 選手A

二巡目でも同様に、抽選によって選手を選ぶ優先度を決めます。ここでは、監督1 > 監督2とします。選手Bを両監督が指名するため、優先度が高い監督1が選手Bを獲得し、監督2は次に欲しい選手である選手Dを獲得します。

二巡目
監督1: 選手B
監督2: 選手D

一巡目、二巡目の結果をまとめると以下のようなリストが得られます。

混合ランキング
監督2: 選手C
監督1: 選手A
監督1: 選手B
監督2: 選手D

このように各巡目でランダムに優先度をつけ、選好リストからアイテムを選択していく手法がTeam Draft Interleavingです。実際の推薦システムでは、各監督がテスト対象のアルゴリズムに相当し、選手がニュース記事に当たります。ユーザーのリクエストの度に混合ランキングを生成します。

解釈

なぜインターリービング（マルチリービング）が通常のA/Bテストよりも感度が高くなるかというと、私は以下2つの性質が効いていると解釈しています。

1人のユーザーが何度も複数の選考リストを評価することになる

一方、通常のA/Bテストだと1人のユーザーが評価する選考リストは1つとなります。

指名された選手はどこか1つのチームにしか属さない

インターリービングでは1人スター選手がいた際に、その選手は指名されたある1つのチームの戦力になります（もちろんランキング上位でスター選手を複数チームが指名するケースもあります）。そのため、よりCTRの高い記事がランキング上位になるロジックが強く評価されやすいと理解しています。一方で、通常のA/Bテストではスター選手が二チームに所属することになり、戦力は相殺されてしまいます。

グノシーにおけるインターリービング

インターリービングを導入する際には、ユーザー体験を損なわないようユーザーに50msec以内にレスポンスを返すという制約がありました。今回の導入では計算量が少ないTDM(Team draft Multi-leaving)を採用しました。 TDMは取得するランキング長をnとした時にO(n)で複数のランキングを1つに混ぜることができます。幸いにもグノシーでは記事リストを返すAPIにGolangを採用しており、比較的容易に並行処理を行い複数のランキングリストを取得し、50msec以内にレスポンスを返すことができました。

実装のイメージは以下のようになります。チームで使用しているインターリービングのライブラリは公開されています。

github.com

var wg sync.WaitGroup
const paramTuningLen = 3
var rankings [paramTuningLen]Ranking

for i := 0; i < paramTuningLen; i++ {
    wg.Add(1)
    go func(i int) {
        defer wg.Done()
        ranking := getRankingFromParam(param[i])
        rankings[i] = ranking
    }(i)
}
wg.Wait()

TDM := &tdm.TeamDraftMultileaving{}
var res []intergo.Res
// 混合ランキングを取得
res, err = TDM.GetInterleavedRanking(
    len(rankings[0]),
    rankings[0], rankings[1], rankings[2]
)

集計ではprestoを用いてパラメータごとに評価を行っています。有力なパラメータがある程度絞れた後で、継続率や売上など詳細なメトリクスを計測する際は、通常のA/Bテストを行います。

実験

設定

性能実験では、通常のA/Bテストとインタリービングの感度差を調査しました。ユーザーのN%のうちN/2%の2つをA/BテストのA/Bのバケットに割りあて、N%をインタリービングに割り当てました(Nは同じ値)。パラメータは実験用に2つ用意しました。

結果

f:id:zer4:20181010151835p:plain p値は記事表示回数、記事閲覧回数を元に算出しています。インターリービングでは、ユーザー数1300人程度、通常のA/Bテストでは5000人程度のところでp値が0.01を下回りました。今回の実験では通常のA/Bテストでも比較的少人数でp値が収束したため、100倍効率的とまではいきませんでしたが確かにインターリービングの方が感度が高いことが確認できました。

おわりに

今回はグノシーに導入した高感度ランキング評価手法であるインターリービングを紹介しました。

株式会社Gunosyではデータとアルゴリズムを駆使して問題解決を行いたいエンジニア並びにデータサイエンティストを絶賛募集しています。興味がある方は下記の募集要項から是非ご応募ください。

*1:https://qiita.com/mpkato/items/99bd55cc17387844fd62

*2:https://medium.com/netflix-techblog/interleaving-in-online-experiments-at-netflix-a04ee392ec55

Gunosyデータ分析ブログ

Gunosyで働くデータエンジニアが知見を共有するブログです。

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

はじめに

インターリービングとは

概要

具体例

解釈

グノシーにおけるインターリービング

実験

設定

結果

おわりに