YouTubeの推薦アルゴリズムの変遷を追う〜深層学習から強化学習まで〜

Source: Deep Learning on Medium

3. Top-K Off-Policy Correction for a REINFORCE Recommender System

これまでの推薦アルゴリズムでは、ユーザーの視聴履歴を教師データとして、ユーザーが好みやすい動画の推薦を行っていました。一方で、その場その場で(短期的に)好みの動画を推薦するのではなく、ユーザーが長期的にYouTubeへのエンゲージメントを高めるような推薦はできないのでしょうか。この論文では、強化学習を用いることで、ユーザーの視聴時間の向上と推薦アイテムの多様化を実現しました。

強化学習によるこのようなアプローチは近年様々な業界で使われ初めており、タクシー配車のアルゴリズムでも使われています。例えば、タクシー配車プラットフォームの観点では、近場のお客さんを優先的に拾うよりも、長期的に拾えるお客さんの数や売上を上げるために別の場所に移動したほうがいい、というシチュエーションはありそうです。このような長期的な指標を最適化するために強化学習の活用が行われています。タクシーの事例は以前サーベイした資料があるので興味ある方はご覧ください。

この技術はゲームドメインでの活用も有名です。強化学習を使って訓練したAIが、囲碁MOBA(Multiplayer Online Battle Arena)において人間のトッププレイヤーを攻略した話題は記憶に新しいと思います。

このように、ある環境において長期的な収益の期待値を最大化するような行動系列を学習するのが強化学習の特徴です。学習には必ずしも人間による教示が必要ないという点も特筆すべきでしょう。

話をYouTubeに戻します。本論文では、ユーザーの視聴時間を報酬として、長期的にユーザーがよりYouTubeの動画を視聴するような推薦モデルを作ることを考えます。

システムの概要を大雑把に表したのが上図です。ある時刻tのユーザーに対して、推薦システムはどの動画を推薦するか選択します(行動a)。ユーザーはそれに対して反応して、推薦動画を視聴すればその視聴時間が報酬としてシステムに与えられ、同時にユーザーは次の状態に遷移します。

「状態」と言うと分かりづらいかもしれませんが、シリーズ動画のPart1を見たらユーザーはPart2を見る状態になっているでしょうし、その次はPart3を見る状態になりますよね。ここまで直接的でなくても、初めて出会うジャンルのミュージシャンを起点にして、そのジャンルをどんどん開拓していくようになる視聴行動もありますし、そうしたユーザーの時系列のコンテキストを抽象的に表現したものが「状態」だと思ってください。

推薦システムの仕事は、ユーザーの状態遷移モデルを学習しつつ、長期的な視聴時間の期待値を最大化するためにどのような推薦を行えばいいか学習することになります。この行動系列を生み出す確率分布を方策と呼び、システムは試行錯誤をしながら、より視聴が期待できる方向に方策をアップデートし続けるわけです。

この問題の設定は納得感の高いものですが、これを実現するためには非常に多くの困難に向き合わないといけません。

  • 行動空間の広さ:システムが推薦するアイテムは1Mを超えており、それだけの行動選択肢を持っています。試行錯誤しながら学習すると言っても、これだけ巨大な空間に対してどのように探索を行い、微かな報酬シグナルから学習していけばいいのでしょうか。
  • 様々な方策の同居:サービスに投入された推薦アルゴリズムは、学習対象となる強化学習エージェントだけではありません。新規ユーザーに対して決定論的に特定動画を推薦するロジックなど、エージェントのコントロール外にいるロジックもあります。自分の行動によって得られた結果から自分の方策を見直すだけであれば話は簡単ですが、今回は他人の行動結果からも学んでいかないといけません。
  • 学習の不安定さ:強化学習は実世界規模の問題ではとにかく不安定になることが活用のネックになっています。正解が与えられない状況下で試行錯誤をするためバリアンスは非常に大きく、かといってバリアンスを軽減するためにアルゴリズムを修正すると今度は不要なバイアスを持ち込んでしまう、というような状況が頻繁に発生します。
  • 複数アイテムの推薦:行動空間が広い、という話がありましたが、Top-1推薦であれば状況はまだマシで、YouTubeのように複数アイテムを同時に推薦するようなTop-K推薦の問題になると、探索空間は行動の組み合わせの数だけ広がり、簡単に爆発します。

このような多くの難しさはありますが、本論文がどのようにこれらの課題を対処しているか、一歩一歩見ていきましょう(なお、ここからは数式が多めになります)。

最初に、本論文で使われているREINFORCEアルゴリズムについて紹介します。

強化学習では、問題をマルコフ決定過程(MDP)として記述します。突然MDPが登場してきますが、上で描いた模式図に数学的な設定を与えているくらいの気持ちで読み進めてください。システム(エージェント)の目標は、期待収益を最大化するような方策を見つけ出すことです。

方策はθでパラメトライズすれば、上式のように勾配が計算できます。見た目はいかついですが、自身の方策によって得られた軌跡と報酬から、より期待収益が高くなる方向に勾配を計算しています。

さて、ここで複数方策が同居する問題が立ち上がります。YouTubeでは数時間ごとにデータを集めてパラメータ更新をするため、集められたデータは過去の様々な方策が混ざったものになります。また、先に紹介した通り決定論的な方策も同居しているため、ピュアに「現時点の方策の評価」ができません。

ただ、強化学習にはちゃんと対処法が用意されています。更新対象となる自分の現時点での方策を推定方策と呼びますが、推定方策とは別の方策(挙動方策と呼びます)からも学習を行うoff-policyという手法があります。自分の試行錯誤だけでなく、他人の試行錯誤のデータからも学習する、というイメージです。REINFORCEアルゴリズムはon-policyアルゴリズム(推定方策と挙動方策が一致するアルゴリズム)であるため、ここにoff-policy補正をかけて、他の方策の存在を考慮にいれましょう。

具体的には、推定方策とは別の方策βを仮定してあげて、軌跡のサンプリング自体はβから行い、πをアップデートする量は補正してあげる要領です(Importance Sampling)。ただしこの補正ではβが分母にくるため、到達確率が小さい軌跡が探索されている場合はβ→0となり、結果として大きなバリアンスを持ち込むことになります。特にβは多くの確率の掛け算に分解されるため、小さい値を取りやすくなります。

そのため、上式のように近似を行いましょう。2つ目の近似はなんだか強引に見えますが、この変換後もバリアンスの上界がある程度抑えられることが分かっています(Achiam et al. 2017)。

合わせて、Weight CappingNormalized Importance SamplingTrust Region Policy Optimizationといったバリアンス低減のテクニックが同時に使われていますが、長くなるので詳細は割愛します。これほど慎重にバリアンスに向き合わないと学習が進まない不安定さが伝わりますね。

論文のFigure.2を加工

off-policy補正による効果を簡単な実験で確かめてみましょう。推薦アイテム(行動)が10個ある場合を考え、それぞれの報酬はアイテムのインデックスで与えられるとします。つまり一番報酬が高いアイテムはa=10で、このアイテムを選択することが最適方策になる状況を考えます。挙動方策は上式のように、iが小さなアイテムほどたくさん選択される方策として与えてみます。

この設定で実験をすると、off-policy補正をかけた方策(右図)はa=10を集中的に選択し、最適に近い状態が実現できています。一方で、off-policy補正をかけない場合(左図)は、βが小さいaに偏っている影響で、πもそれに引きずられてしまってしまいます。これで補正が効いていることが確認できました。

off-policy補正を使った更新式まで求めたところで、次にアーキテクチャを見ていきましょう。ユーザー状態を表現するベクトルを推薦アイテムの埋め込みベクトルと一緒にRNNに入力し、そこで得られたユーザーの次状態をsoftmaxで表現されたπとして出力します。コンテキストには先ほどのLatent Crossが用いられており、TimeDelta・デバイス・ページといった情報が入力されます。

章の冒頭で複数の挙動方策が同居している、という問題に言及しましたが、本論文ではβを同じアーキテクチャ内で別パラメータθ’を使って学習しています。これによって、挙動方策群が全体平均としてどのような推薦を行うかが表現できるわけです。全体でならすことによって、β={0,1}のような出力が行われる決定論的な方策が同居していても勾配が計算しやすくなることも期待できます。βの学習がθの学習に影響を与えないよう、勾配の流れは分岐箇所で止めている点に注意してください。

このようにπとβが求まり報酬Rもデータから観測できるので、勾配を計算してより高い報酬が期待できる方策に近づけることができました。いよいよ最後の関門であるTop-K推薦に話題を進めましょう。

Top-K推薦をするにあたってすぐに思いつくのは行動空間の拡張です。一つのアイテム推薦を一行動として考えるのではなく、複数アイテムの組み合わせを行動とします。ただ、これは冒頭で言及したとおり行動空間の爆発を引き起こすので、なんとか計算を縮減しないと解けません。

そこで、問題を単純化して「複数アイテムの推薦はTop-1推薦を複数回繰り返す」と読み替えてしまいます。当然重複するアイテムも出てきますが、最終的に重複を除いた集合が得られればいいのでいったん許容します。

同様にREINFORCEアルゴリズムも上式のように拡張できます。新たに登場したαはあるアイテムaが推薦リストに含まれる確率を意味することになります。

勾配にoff-policy補正をして展開すると、Top-K推薦に拡張した勾配は、Top-1時の勾配に補正項λをつけただけの形に変形できます。このλをもう少し深堀ってみましょう。aが推薦されづらいアイテムだった場合(π→0)に報酬が発生すると、勾配は通常のK倍となってより大きく更新されます。一方で、既にaが推薦されやすい場合(π→1)には、λ→0に近づくため勾配の更新は抑制されることになります。

Top-K補正の影響を先ほどの実験で検証しましょう。今度は、a=1とa=2が高い報酬(r=10, 9)を持ち、他は全て報酬が低い(r=1)という状況を考えます。簡単のため挙動方策は一様分布としています。

結果を見ると、Top-K補正をかけない場合(左図)は、一番高い報酬を持つa=1を推薦し続ける方策が学習されています。ここにTop-K補正を入れると、二番手であるa=2も推薦されるようにりました(右図)。これは、a=2の推薦確率が低い時には、報酬発生時にK(=2)倍余計に勾配を考慮するのと、a=1がリストに入り始めると勾配が0に近づくことが相補的に影響していると考えられます。

長くなりましたが、ここまででTop-K off-policy補正の全体像の説明はおしまいです。最後に、実際のYouTube環境での実験結果を紹介します。

論文のFigure.5より

K=16の設定で実験したところ、最大0.8%程度の視聴時間の増加が見られました。上図はK=16をベースラインとした場合の比較ですが、Kを大きくしてもさほど視聴時間は変わらず、逆にKが小さすぎるとパフォーマンスが悪化することが確認されています。

論文のFigure.4より

視聴時間の他に影響があったのは推薦されるアイテム数です。上図は推薦動画をインプレッションの高い順に並べた時の累積分布を表していますが、コントロール群(青線)では人気の動画に推薦が集中している(分布が左に寄っている)一方で、今回のアルゴリズムを適用した実験群(緑線)ではよりランキングの低い動画が推薦される傾向が強くなっています。提案モデルによって、視聴時間や動画の多様性を増加させることができました。

最後に

この記事ではYouTubeの推薦アルゴリズムの変遷を追いながら、推薦システムへの ① 深層学習の導入、② RNNの導入とコンテキスト特徴の効率的な入力、③ 強化学習の導入、を紹介してきました。

特に3つ目の論文が面白かったので、夢中になって書いたら結構な長さになってしまいましたが、ここでは紹介しきれなかった話題や論文もたくさんあるので、また他の機会に紹介していきたいと思います。

最近は推薦×強化学習領域のサーベイをしていましたが、YouTubeに限らず、ECや他のドメインでも様々な導入事例があります。 社内だけに調査の情報を閉じてしまうのはもったいないので、勉強会や議論の場などあれば気軽に誘ってくださいませ。

最後に、eurekaではマッチングやレコメンド領域のAI技術に向き合っていきたいと思っています。興味のある方はぜひお声がけください。