多腕バンディットによる表示コンテンツの最適化

こんにちは。技術部検索グループの原島です。

f:id:jharashima:20141029104449p:plain

上の画像は、スマートフォン(ブラウザ版)で見たクックパッドの検索結果ページです。レシピだけでなく、ニュースも表示されていますね。献立や掲示板のスレッドなどが表示されることもあります。

クックパッドでは、検索結果ページに表示するコンテンツをクエリなどに応じて最適化しています。最適化は、膨大なログデータと最新の機械学習を用いることで、実現しています。このエントリでは、クックパッドにおけるコンテンツ最適化の裏側を紹介します。

最適化の背景

スマートフォンの普及に伴って、ユーザが利用するプラットフォームは PC からモバイルにシフトしつつあります。クックパッドにおけるモバイル利用者の割合も、ここ 2 年で 10% 以上増加しました。最近では、60% 以上のユーザがモバイルからアクセスしています。

ユーザの利用形態が変化すれば、検索結果ページもその変化に対応しなければなりません。PC とモバイルの違いは沢山ありますが、最大の違いは画面のサイズではないでしょうか。モバイルは画面が小さく、大きなものでも、せいぜい 6 インチ程度しかありません。

画面が小さいと、UI をシンプルに保つのが難しくなります。あれもこれもとコンテンツを表示すると、UI が煩雑になってしまうのです。そのため、あらゆるコンテンツを検索結果ページに表示するわけにはいきません。

そこで、クックパッドでは、表示コンテンツを最適化するという解決策に行き着きました。クエリなどに応じて最適なコンテンツだけを表示すれば、UI を煩雑にすることなく、必要な情報をユーザに提供できるのではないでしょうか。

このような背景で、コンテンツ最適化の取り組みは始まりました。

多腕バンディット問題

では、どうすれば最適化を実現できるでしょうか。クックパッドでは、機械学習の一つである多腕バンディット問題に注目しました。多腕バンディット問題は、「探索」と「活用」という二種類の行動を使い分けて報酬を最大化する問題です。

よく題材として挙げられるのが、スロットマシンです。複数のスロットマシンがあった時、得られる報酬を最大化したいとします。ただし、使えるお金には制限があります。以下、「腕」という言葉を多用しますが、これはスロットマシンのレバーを指します。

f:id:jharashima:20141029105437p:plain

まず、当たりやすいマシンを見極めたいというのが自然な発想です。そして、各マシンに少しずつ投資すれば、これを見極められそうです。このように、情報を収集するために腕を選択するのが探索です。

当たりやすいマシンを見極められれば、こちらのものです。そのマシンに集中的に投資することで、報酬を最大化できそうです。このように、収集した情報に基づいて腕を選択するのが活用です。

ポイントは、探索と活用がトレードオフということです。探索への投資を増やせば、当たりやすいマシンが分かってきますが、活用の機会が減ってしまいます。一方、探索への投資を減らせば、当たりやすいマシンが分からないので、活用が一か八かになってしまいます。

報酬を最大化するには、探索と活用のバランスを取る必要があります。バンディット問題は古くから研究されており、沢山のアルゴリズムが提案されてきました。epsilon-greedy や softmax、UCB などのアルゴリズムを用いることで両者のバランスを取ることができます。

また、ここ数年、コンテキスト付きバンディット問題が注目を集めています。これは、コンテキストごとに最適な腕が異なる題材で報酬を最大化する問題です。クエリやユーザに応じて最適な腕を推定できるため、広告の配信などへの応用が期待されています。

最適化の仕組み

クックパッドでは、バンディット問題(コンテキスト付き)を用いて、コンテキストごとに最適なコンテンツを表示しています。具体的には、コンテンツを腕、CTR を報酬、クエリなどをコンテキストとみなして、報酬が最大となるように腕を選択しています。

下図に最適化の全体像を示します。最適化を行うための処理はオンラインの処理とオフラインの処理に大別されます。まず、オンラインで探索と活用を行います。具体的な処理は以下の通りです。

  1. 一部の検索 PV を探索に、その他の PV を活用に割り当てます。
  2. 探索に割り当てた PV では a を、活用に割り当てた PV では b を行います。
    1. ニュースや献立などのコンテンツからランダムに一つを選択して、検索結果に表示します。また、コンテンツがクリックされたかどうかという情報をロギングします。
    2. 前日までに収集した情報に基づいてコンテンツを選択し、検索結果に表示します。

f:id:jharashima:20141027185122p:plain

オフラインでは学習と推定を行います。具体的な処理は以下の通りです。

  1. 前日のログを整理して、訓練データとテストデータを構築します。
  2. 直近 N 日の訓練データに基づいてバンディットの学習モデルを構築します(上図では N = 3)。どのコンテキストに対してどのコンテンツを表示するかが学習されます。
  3. 学習されたモデルを直近 M 日のテストデータに適用します(上図では M = 1)。翌日に訪れそうなコンテキストに対して表示すべきコンテンツが推定されます。

オフラインの処理が終われば、コンテキストごとに CTR がもっとも高くなると推定されたコンテンツがデータベースに保持されます。翌日の活用時には、これを参照して、コンテンツを表示しています。同時に探索も行われ、その情報は次の日の学習に利用されます。

結果

以下に、最適化の例を示します。それぞれ「ポトフ」と「おでん」の検索結果ページ(10 月 28 日の新着順)です。献立と掲示板のスレッドが表示されていますね。これらは、それまでのログから CTR がもっとも高くなると推定されたコンテンツです。

f:id:jharashima:20141029104917p:plain     f:id:jharashima:20141029105111p:plain

では、実際、CTR はどうなったのでしょうか。探索時の CTR との対比で、活用時の CTR は 160% 以上になりました。このことから、上で紹介した仕組みによって、よりユーザが求めるコンテンツを表示できていることが分かります。

まとめ

モバイルは画面が小さいため、なんでもかんでも表示するわけにはいきません。UI をシンプルに保つため、必要最小限のコンテンツだけを表示することが望まれます。

クックパッドでは、これを実現するため、多腕バンディット問題を導入しました。日々蓄積されるログデータを活用して、コンテキストに応じて最適なコンテンツを推定しています。

結果、CTR が高くなるコンテンツだけを検索結果に表示できるようになりました。今後は、さらなる最適化を目指して、コンテンツやコンテキストを拡大していく予定です。