パーソナライゼーションのためのマルチリービング
飯塚洸二郎氏（以下、飯塚）：本日は「パーソナライゼーションのためのマルチリービング」と題しまして紹介させていただきます。
まず発表の前に、弊社グノシーの推薦勉強会の紹介をさせていただきます。
勉強会の目的としましては、最新技術のキャッチアップとプロダクトへの応用や、論文書く人がいるので、その論文執筆のネタのために週1の論読会を実施しています。
参加者は、社内のメディア、または広告のロジックに関わる人、あとは研究開発の方です。対象の会議は有名なWWWや、WSDM、RecsysやKDDの論文も読みます。
それでは本日の発表を始めさせていただきます。
今回の発表は、オンライン評価について述べさせていただきます。まず、オンライン評価の有名どころであるA/Bテストについておさらいさせていただきます。A/Bテストは昔から行われているオンライン評価の手法の1つで、例えばアルゴリズムが2つあったときはユーザ群を2つに分けて、そのユーザ群に対して各アルゴリズムから生成されたランキングを別々に提示して、そのあとで何らかの評価行うという手法です。
今回紹介させていただくのはマルチリービングという手法で、このアプリケーションの方法から簡単に説明させていただきます。まず、上の図がトラディショナルなA/Bテスティングです。この図が表していることは、左上ランプ、これはアルゴリズムの周期です。やりたいことは、このランプがアルゴリズムの中から1番優れたアルゴリズムを1つ持ってきたい。
そのときに、通常でしたらA/Bテストを行います。しかしながらA/Bテストですと、対象のアルゴリズムが増えれば増えるほどユーザが必要になって、それに応じてテストの期間が長くなってしまい、素早くプロダクションにはアルゴリズムを持ってくることが困難になっていきます。
その中で、近年マルチリービングという手法が出てきました。それはA/Bテストを簡略化できる手法の1つです。簡単なイメージとしましては、下側の図です。これがマルチリービングで出来ることです。マルチリービングの場合もA/Bテストと同じで、たくさんのアルゴリズムの中から1つの正解を導きたいです。
ですが、通常のA/Bテストではたくさんのユーザが必要となってくる中で、マルチリービングではA/Bテストの前段階としてこの手法を用いると、優れているアルゴリズムの候補をいくつか取ってくることができます。
このように対象を絞ることでA/Bテストのユーザ数を減らして、最終的にテストに掛かる時間が大幅に削減できるということで、注目されている手法の1つです。
パーソナライゼーションにおけるアルゴリズム
それでは今回の発表の背景に触れていきます。
パーソナライゼーションはさまざまなサービスで使われていて、重要な役割を担っています。しかしながらアルゴリズムの良し悪しは、通常はA/Bテストで判断されることが多いです。先ほども申しました通り、A/Bテストは多くのサンプルサイズが必要です。そんな中で近年マルチリービングという手法が出てきて、この手法によって少ないユーザの数で良いアルゴリズムを取ってくることができるようになったのではないかと注目されてきました。
しかし、このパーソナライゼーションのための状況の下で、マルチリービングを適用したという事例は今までありませんでした。というのも、マルチリービングというのは、検索の文脈で出てきた技術でして、ユーザごとに違うランキングが出てくることを想定していませんでした。
今日の発表の概要です。まず、パーソナライゼーションの状況の下でマルチリービングを適用するための課題を整理しました。次に、課題を解決する手法の提案をします。最後、実システムにおいて包括的な検証を実施したので、その報告をさせていただきます。
最初にA/Bテストの説明をさせていただきましたが、右側が「Interleaving」というものです。ここでいきなりInterleavingという言葉が出てきたんですが、マルチリービングというのはこのInterleavingから派生した手法です。
Interleavingというのは、2つのランキングに対してどちらのランキングが優れているのかを計る手法なんですが、2つのランキングじゃなくて3つ以上のランキングに一般化したのがマルチリービングです。右側はInterleavingを使うと、ご覧いただいている通り2つのランキングを別々のユーザにA/Bテストを出すのではなくて、2つのランキングを1つに混ぜて、1つのランキングで同じユーザ群にランキングを出して評価をするというのがInterleavingの直感的な説明になります。
マルチリービングとは何か
続いて、マルチリービングの説明です。
マルチリービングはランキングのオンライン評価の手法の1つです。特徴は少ないサンプルサイズでのランキング評価できます。他のメリットとしましては、変なバイアスに作用されないというメリットがあります。
これはA/Bテストのようにユーザを2つに分けず、1つのユーザ群に対してランキングを提示して評価をする手法なので、仮にA/BテストでグループAに極端な振る舞いをするユーザがいた場合にはその極端なユーザに結果が左右されてしまいますが、Interleavingはそんなようなバイアスというのが起こりません。これがメリットの1つです。
しかしながら、マルチリービングは万能な手法ではありません。ランキングの間接的な影響はA/Bテストに比べて評価しにくいという点もあります。例えばユーザのサービス継続率や、広告の売り上げは、グノシーではマルチリービングを使わずに通常のA/Bテストで評価しています。
マルチリービングの既存の手法は大きな2つの手法がありまして、1つがチームドラフトマルチリービングと呼ばれているものです。これはTDMと略されることが多くて、手法としましてはランダムに優先度を付けてランキングを交互に混ぜる手法です。2つ目がオプティマイズマルチリービング、OMと呼ばれているものです。これは、いくつかの制約のもとで生成されるランキングの感度の期待値を、最大化にするのに確率を最適化する手法になります。
オプティマイズマルチリービングの定式化はこのようになっていて、直感的に言いますとバイアスというのがありまして、バイアスは各ランキングごとに提示されているもので、仮にバイアスがもし大きかったら本来差がないランキングに差が出てきてしまうという状況があります。なので、そのバイアスを最小化しつつ、感度を最大化するのが定式化の基本になります。
感度というのは何かと言いますと、ランキングごとの違いを判断する力になります。感度が大きければ大きいほど、少ないランキングの違いに対してもランキングの優越を付けることができるようになります。
この定式化の中でδが出てくるのですが、これがオプティマイズマルチリービングのキモの1つになっています。これはフィードバック関数になっています。このフィードバック関数は何かと言いますと、元のランキングに対して最終的な出力ランキングがクリックされたときのフィードバックを返す関数になります。これはランキングの逆数で代用されることが多いです。
マルチリービングのデメリットを克服する
マルチリービングのメリットについては述べた通りなのですが、パーソナライゼーションに対してマルチリービングを適用する際は、負荷がとても大きいという欠点があります。
また、パーソナライゼーションの性質としましては、近年のWebサービスはランキングの長さが長いという特徴があることや、パラメータの数がとても多いためアルゴリズム1つを取ってもさまざまなチューニングをする余地があります。
パーソナライゼーションなので、もちろんユーザごとにランキングが異なります。
さらに、例えばグノシーのニュースランキングに関しては、時系列でランキングが変化するという性質があります。以上の性質がある中で、マルチリービングを適用する際にリアルタイムでレスポンスを返さないと、ユーザにとって悪影響を及ぼしてしまうことがあります。
この課題を解決するためのアプローチとして、今回2つの変更を加えました。
1つ目の変更が、定式化の修正です。定式化の修正に関しましては、先ほどお見せした定式化の中で最適化する変数を除去することで高速化を図ります。また、フィードバック関数の逆関数を用いるのではなく、新たなフィードバック関数を設定して、ランキング長とランキングの種類に対して安定化させることを目指しました。
詳細の定式化はあのようになります。
従来の定式化では確率pが出てくるのですが、そのpを除くことでより高速に解を求めることを提案しています。
この方法は従来の方法と違って、パーソナライゼーションの文脈では各ユーザごとにランキングが異なります。なので、各ランキングでどれを出すのかがこの確率pなんですが、それを考慮する必要がなくて確率pを一気に除いてしまうことができます。
さらに、フィードバック関数の「Inverse Credit Function」ではなくて、パーソナライゼーション特有の関数を1つ定義しました。これは関数の逆数を使うのではなく、各ランキングごとの相対的な位置を使ってフィードバックを返す関数になります。
オフライン実験の結果
先ほどの提案手法の安定性を検証するためにオフライン実験を行いました。
この実験の設計は、ランキング長とランキングの種類を変化させたときの挙動を調査します。方法は、クリックのシミュレーションを実施しました。あるランキングのみクリックされやすい状況を設定して、そのバイアスをかけたランキングのクレジットが他のランキングよりも高くなる確率を計測しました。
ここでは、このランキングの確率はAccuracyと呼びます。
結果がこちらです。
図の見方としては、横軸はランキングの長さです。縦軸がランキングの評価の性能になります。グラフが3つあり、GOM-Iが新たに離散化した定式化で、かつ元々の逆数、Inverseクレジットを用いたものです。赤がGOM-Pで、これはパーソナライゼーションクレジットを用いたものです。緑がチームドラフトマルチリービングで、既存の手法になります。
これを見ますと、ランキングの長さを長くするほど青のGOM-Iの評価の確率が右肩下がりで下がっていることがわかります。一方で、パーソナライゼーションクレジットを用いると、ランキングの長さに対して伸ばすという結果がわかります。
次の図が、ランキングの種類に対する精度の比較です。横軸がランキングの種類で縦軸が同じく精度になります。今回の場合は、チームドラフトマルチリービングがランキングの種類を増やせば増やすほど精度が落ちていってることが確認できます。
一方で、パーソナライゼーションクレジットを用いると、ランキングの種類に対してもロバストになるという結果が見てわかります。
じゃあ、どうしてロバストになったかというのが、この図からわかります。
この図が何を表しているかと言いますと、z軸が感度を表しています。感度が高いという状況は、この状況だと感度が低い。このz軸が小さければ小さいほどバラつきの小さい差も検知できるという状況になります。
それに対してランキングの長さとランキングの種類を増やしたときに、Inverseクレジットとパーソナライゼーションクレジットを用いる場合で、感度がどう変わるかというのを可視化したのがこの図になります。
これを見ますと、パーソナライゼーションクレジットを用いることによって、感度が高くなります。
オンライン実験
その次にオンラインテストも行いました。オンラインテストを行ったモチベーションは、実際にA/Bテストをする場合とマルチリービングを行うときの結果がちゃんと一緒かを確認するのが主な目的です。
検証の仕方は、まずはランキングを生成するアルゴリズムを5つ用意しました。この場合、アルゴリズムAからEとおきます。事前にこの5つのアルゴリズムに対してA/Bテストを実施した結果、アルゴリズムA、B、C、D、Eの順に並んだという前提をおいておきます。このA/Bテストの詳細は、ランキングの優越と言っているんですが、この場合CTRと比較して、この場合CTRが1番高いのが良いということになります。
最後にマルチリービングを用いまして、ランキングのアルゴリズムに優越を付けるというものはマルチリービングでも整合性が取れているかを確認しました。
得られた結果が下の図です。
この図も見方が難しいですが、まずは3つの項目があります。これは先ほどと同様にGOM-I、GOM-P、TDMになります。
この図の表の値が示しているのが、クレジットの値です。例えば左上の-14,962というのはアルゴリズムBからアルゴリズムAのクレジットの値を引いた値になります。この図を見てみますと、GOM-PとTDMに関しましてはクレジットの差も正というのが両方とも制御できていると思います。
正になっているということは、このアルゴリズムAからBの優越が再現できているということになります。一方でInverseを用いてしまいますと負の値が出てしまいまして、それはA/Bテストとの結果が整合性を取れていないということになります。
また、A/Bテストとマルチリービングで効率性の違いについても検証しました。
横軸がユーザの数、縦軸がp値になります。もちろんp値なのでユーザ数を増やせば増やすほどpの値は落ちていくと思います。しかしながらこの場合ですと、GOM-PとTDMがA/Bテストと違ってマルチリービングを用いた結果になっていまして、A/Bテストに比べて少ないユーザの数で値が収束しているという過程が見えております。
今後の課題
最後にまとめと今後の課題です。
今回の発表では、パーソナライゼーションの状況のもとでマルチリービングを行う手法を提案しました。また、大規模な実験を実施してA/Bテストに比べて効率的に性能が評価できることを確認しました。
また、オフラインテストの結果を見ますと、ランキング長とランキングの種類に対してもパーソナライゼーションのフィードバック関数を用いることで結果が安定するということが分かりました。
今後は、NDCGの他の検索のメトリクスとの整合性を調査したりとか、今回はクレジット関数は純粋にクリックの数でアプローチしているものなので、ランキングのメトリクスを評価する整合性あたりが、なんとなく一致すると思います。また、ランキング学習への応用もマルチリービングでなされているので、その辺も深堀りしてみようかなぁと思います。
最後に、実験で使ったライブラリは公開していますので、よろしければそちらもぜひご覧いただければと思います。
以上で発表を終わりにします。ありがとうございました。
（会場拍手）
