Speeeエンジニアの義田@yoppiblogです。 最近はUZOUのレコメンドエンジンを作っています。
前回、UZOUというアドネットワークのプロダクトで運用している文書間類似度によるレコメンドシステムを紹介しました。 今回は、記事レコメンドではなく、UZOUにおける広告レコメンドにおけるアルゴリズムの紹介と実装及び適用した結果を紹介します。 アルゴリズムには、よく知られている「多腕バンディット問題」を採用しUZOUに適用できる形で解きました。
また、勉強会で発表したスライドも合わせて読んでいただくとイメージしやすい思います。 オレシカナイト#6にて発表した内容になります。
背景と問題
UZOUはアドネットワークなので、広告代理店さん（広告主さん）から広告が入稿されそれをUZOUが導入されているメディアさんに配信します。
記事レコメンド同様、 適当に 広告を選んで配信していたのではユーザに興味を持ってもらえず、ひいてはクリックされなくなり、UZOUの収益が落ちてしまいます。
そこで、何かしらの指標をもとに配信する広告を選ばなければなりません。
今回はその指標の軸として、
- 売上を向上する（eCPMを向上）
- 計算量を抑えることでより多くの広告を選択の対象にし、面に配信可能にする
を設定し、達成するために新しいレコメンドアルゴリズムの設計・実装・運用に至りました。
広告を配信する方法
そもそも、われわれアドネットワークが配信する広告を選ぶ方法は多岐に渡り、
- ターゲティング配信
- リターゲティング配信
- コンテンツベース配信
- 過去の成果に基づく配信（実際にはこの選び方+上記の3つのどれか、という組み合わせが一般的です）
など、よく見かけるものだけでもこれだけあります。
今回は、 過去の成果に基づく配信 を採用しています。アドネットワークにおいてはごく一般的な方法です。
成果、つまり一定期間その広告をその面で配信してみて、その面においてどれくらいクリックされたのか、そのクリックからコンバージョンに至ったのか、等をパラメータとして次の期間ではどの広告を配信するかを決定します。
たぶん、簡単に思いつく方法は 成果が良かった 順に広告をソートして順に配信する、という方法です。
しかし、そう問題は単純ではありません。選ぶ広告が常に一定で変化しない、というものであればしばらく配信してみて都度成果がよかった順に配信していればよいですが、アドネットワークは常に入稿される広告が増減し内容も変わっていくのです。そのため、新しく入稿された広告はいつまでたっても配信されません。
もし本当は成果が良かった場合、配信できないとなると機会損失を作っていることになります。
こういった問題を解消するために、多腕バンディット問題を広告選択に適用しました。
多腕バンディット問題
よく、多腕バンディット問題の解説としてスロットマシンの例があげられます。ここでもスロットマシンを例に説明したいと思います。
入稿される広告を各スロットマシンとみなして、どの広告を配信するかをそのスロットマシンでスロットする、と置き換えて考えます。 たくさんのスロットマシン（広告）がある中で、どれかのスロットマシンでスロット（配信）し報酬（eCPM）を最大化させる、ことが多腕バンディット問題のゴールとなります。
たとえば、4つスロットマシンが与えられ100回ひけるルールにおいて報酬を最大化するゲームに挑戦するとします。 どのスロットが成果が良いかは引いてみないとわかりません。 簡単に思いつく方法は、すべてのスロットを何回か引いてみて、その結果報酬が良かったスロットを引き続ける、という戦略です。
試しに、3回すべてのスロットマシンでスロットを回し、残りの回数をその引いた結果で良かったスロットを引き続ける戦略をとります。たった3回だともしかすると本当に報酬が良かったスロットマシンを見つけられない可能性があります。
今度は、3回より多い20回すべてのスロットマシンでスロットを回して本当に報酬が良いスロットマシンを見極めようと考えます。しかし、報酬が良いスロットマシンをひける回数がとても少なくなり、結果として報酬を最大化させることは難しいはずです。
この2つの例から
- もっと良い報酬が得られるスロットがあるのでは？と考えて探す回数を増やすと、結果として報酬を最大化できない
- このスロットが報酬が良いと考えて、特定のスロットを引き続けると、結果として報酬を最大化できない
というジレンマに陥っていることがわかると思います。
前者を 探索(exploration) 後者を 知識活用(exploitation) とバンディット問題では呼ばれ、探索と知識活用を「報酬最大化」になるように実行しなければ多腕バンディット問題を解くことができないわけです。
この探索と知識活用を実行することを 方策 と呼んでおり、これまでの研究から以下の方策が知られています。
- ε-greedy
- 単純な総当り結果から良かったものを引き続ける。今回の例題で使った方策です。とても単純なロジックなことから限定した用途では使われることもあります
- UCB
- 標本平均に補正項を加えたものをスコアとして腕を選ぶ。次のThompson Samplingより理論限界が低いことが知られています
- Thompson Sampling
- 過去に観測できた結果からベイズ統計で未来の期待値を予測する
今回は一番成果が良いと知られている「Thompson Sampling」を採用しました。
Thompson Sampling
Thompson Sampling とは、各腕の期待値を最大となる確率をもとにランダムで腕を選択する方策です。 これは、ベイズ推定に則るものです。 さきほどのスロットマシーンの例にもありましたが、何回か腕を選択した結果から報酬を観測することはできます。 これを事前分布として、これから事後分布（真の期待値）を求められます。 スロットマシーンを広告配信に置き換えると、ユーザが「クリックされた」「クリックされなかった」の二値に分類できます。 これはベルヌーイ試行を繰り返したことになり二項分布になります。 二項分布は平均・分散が存在することから中心極限定理により、事後分布を確率推定として使って良い、つまり事後分布を求めることで腕の期待値予測を可能にしています。
Thompson Sampling を採用した理由
Thompson Sampling を採用した理由として、
- バッチ更新に頑健である
- 計算量を少なくできる
- 多くのモデルで理論限界を達成できることが知られている
これらのメリットを享受できると考えたからです。
まず、バッチ更新に頑健である、というメリットについてです。 広告配信システムの制御において、production環境でのデータ量は膨大になり、データサイズからくる計算量の制約により期待値予測をリアルタイムで計算を実現することが難しいため、バッチ更新を採用することが多いです。 そのため、次回のバッチ実行時まで腕が偏ることが想定されるのですが、Thompson Samplingでは腕の選択時に「期待値最大となる腕をランダムで選択するため」成果の悪い腕に偏ることを防げます。
また、計算自体もとても平易で計算量が少ないことからシステムに負荷を与えず運用できます。 二項分布をそのまま計算するととても計算量が多くなるのですが、二項分布の共益事前分布によりBeta分布を計算するだけで良いことが知られています。そのため計算量を大幅に削減できます。
そして、多くのモデルでThompson Samplingは理論限界（理論上の報酬の最大値）を達成できることが知られています。
Thompson Sampling の擬似コード
では、Thompson Samplingの実装を以下の擬似コードで紹介します。
ここで、nが試行回数で、mが報酬を得た回数、iが腕の一つになります。 時間tにおいてfor文が一つ（時間計算量はO(N)）と実装はとてもシンプルです。Beta分布さえ計算できればどのプログラミング言語においても平易に実装できます。 詳細なロジックの流れは、
- 時間tにおいて、腕iにおける
と
からBeta分布により事後分布（期待値）
を求め
- 期待値集合、
から最大となる腕iを選び
- 期待値最大となる腕iを引いて報酬
を観測し
- 腕iにおける
となります。
時間tの間隔がバッチ実行の間隔となるため、間隔を短くすればするほどThompson Samplingでの予測がリアルタイムに近づいていきます。
UZOUへの適用
Thompson SamplingをUZOUに適用するには、先程の擬似コードを広告配信でのドメインで置き換えることになります。
各広告毎のimpressionとclickを初期値0として、
- ある時間tにおいて広告iにおける
と
からBeta分布により
を予測し
- 時間tにおける広告iの
からeCPMを算出したのち、eCPM最大となる広告iを選び
- 広告iをひいてクリックされたかされなかったかを観測し
- 広告iの
という流れになります。 ここで、先程の一般化されているロジックと異なる部分は、最大化するのはCTRではなく広告収益を最大化したいのでeCPM最大化したいので、eCPM最大となる広告iを選んでいます。
適用した結果
今回実装したThompson Samplingを適用した結果、UZOU全体のeCPMを20%ほど向上させることができました。 つまり、売上を20%増やせたということです💪💪💪 エンジニアはコードを書くことだけではなく、顧客への価値提供とともに製品の売上を向上させられるのです！
今後の課題
現在、思いついているアイデアとして、
- 事後分布を求めるときのBeta分布の
α+βの値をヒューリスティックに決めているので適切にハイパーパラメータを探索する - 腕の更新頻度はすべて固定にしているので、枠ごとに適切に腕を更新する
- 現在、CTRのみで事後分布を算出しているのでCVRも加味した予測をしたい（CPA最適化の文脈も含む）
があります。
まとめ
今回は、UZOUにおける広告配信アルゴリズムとして多腕バンディット問題を適用し、その実装を紹介しました。 適用した結果、UZOUのアドネットワーク全体のeCPMを20%向上できました。 技術がビジネスに直結するのがアドテクならではなので、とても面白いですし、事業へコミットできる感覚を養えると考えています。
