旧ブログ

sambaiz.net に引っ越しました

モテる広告エンジニアが、バンディットアルゴリズムで調べた本当にイケてるクリスマススポットを教えるよ

この記事はCyberAgent エンジニア Advent Calendar 2015の23日目の記事です。

昨日はtaizoさんの Web系ポッドキャストを1年間やってみた話 で、明日は公式エンジニアブログです。


こんにちは。新卒1年目の@sambaizです。広告のエンジニアになりました。 広告のシステムは多数の要求を受け止め、気の利いた応答を返すものなのですが、 普段からこのようなことを意識している広告エンジニアは理論的にモテすぎて困るぐらいで、 実際に全くモテなかった僕が広告のエンジニアになってから1年もたたずにこのようなこともありました。

2016年もモテモテに拍車がかかるであろう新進気鋭のリア充、僕が 広告でも使われるバンディットアルゴリズムを使ってイケてるクリスマススポットを調査してみました。

バンディットアルゴリズムとは

スロットマシンってやったことありますか? 僕はロケットゲームコーナーでしかやったことがないのですが、 メダルを入れ、レバーを引くと回転し始めて、ある確率で報酬が得られる機械であることが分かれば十分です。 これからの話で登場するスロットマシンはこのレバー(以下”腕"といいます)が複数あり、レバーによって当選確率が違うものです。

このスロットマシンこそ、バンディットの名前の由来です。 メダルを入れ、適当なレバーを引き続けていると、いつのまにかプレイヤーのメダルは0枚、 もはやこのスロットマシンはメダル泥棒(bandit)ですね。 それに対してプレイヤーは、なるべくメダルを盗られるばかりにならないように対抗しなくてはいけません。 プレイヤーはどの腕を引くかを選ぶことができるのです。 では、次どの腕を引けば良いか、それを決めるのがバンディットアルゴリズムです。

探求と活用

さて、あなたは複数の腕を試すのに十分なメダルを持っています。 1回目に引く腕はどれにしましょうか。全く情報がないなかで選ぶ腕は完全にランダムです。

次に引く腕はどれにしましょうか。1回目の腕で報酬が得られなかった場合でも、それは単に運が悪かっただけなのかもしれませんし、 本当に出ない腕なのかもしれません。もう一度1回目の腕を引いたほうがいいか、他の腕を引いたほうがいいか、 この時点で判断するのは難しいです。より確かな情報を得るために、いずれかの腕を引かなくてはいけません。 この試しに引いてみる選択を探求といいます。

腕を何回か引いていくに従って、どの腕がどれくらい報酬を得られる腕なのかがなんとなく分かってきます。 明らかに良い結果の腕が分かれば、それを引き続けるといいような気がしますね。 この、探求によって分かった良い結果であろう腕を引く選択を活用といいます。

探求ばかりしていると、プレイヤーは損をします。 なぜなら、悪い結果だと思われる腕を引いてメダルを失うだけではなく、 良い結果だと思われる腕を引かないのは、それで得られたはずの報酬を得られないからです。

では、ある程度良い結果の腕が見つかれば、それ以上探求はせず活用に移るべきでしょうか。 もしかすると、他にもっと良い腕があるかもしれません。 もしそんな腕があったとしたら、長期的には探求しておいた方がいいでしょう。

どの腕を選択するかは、いくつかの方法が考えられています。今回はUCB1というのを使うことにしました。

UCB1

UCB1では、一回も選ばれていない腕があればそれを優先的に選び、 すべての腕が1回以上選ばれてからは、腕の報酬の平均値(この記事ではスコアと呼ぶことにします) とボーナス値を合わせたものが最大の腕を選ぶものです。

ボーナス値は以下の式の値です。

f:id:sambaiz:20151223163709p:plain

このボーナス値によって、UCB1は結果のよい腕を活用しながら、あまり選ばれていない腕も時々は探求することになります。

今回はオリジナルのスロットマシンで説明しましたが、実際はこの腕が、広告のクリエイティブだったり、 Webサイトのデザインだったりするわけです。その場合でも取れる選択肢は腕と呼ばれます。 バンディットアルゴリズムについてより詳細な情報を知りたい場合は、一番下の参考のところにオライリー本のリンクを貼っておいたので 読んでみてください。

作ったもの

f:id:sambaiz:20151223164648p:plain

まず、東京近辺の駅などを30箇所選びその半径2kmのエリアを1つのスポットとして、 Google Places APIでスポットごとに最大5枚無作為に選びました。 選んだスポットは以下の通りです。地方の人はごめんなさい。

新宿、渋谷、東京、池袋、豊洲、上野、田端、東京ドーム、汐留、品川、お台場、六本木、スカイツリー、
中野、田園調布、銀座、田町、中目黒、下北沢、三軒茶屋、四谷、二子玉川、国分寺、三鷹、聖蹟桜ケ丘、
亀有、浦安、荻窪、富士見台、競艇場前

この30スポット合計149枚の画像の中からバンディットアルゴリズムで1枚選び、 ユーザーに表示して評価してもらうWebアプリケーションを作りました。 30回を1セットとし、終わると最後にあなたのセンスは~点といったように得点が出るようになっています。 この得点はスコアが高い写真に"良い"を選ぶと高得点が得られ、低い写真に"だめ"を選ぶと高得点が得られるようになっています。 あからさまに変な回答をすると得点が低くなるはずなのですが、それほど低い点数も見受けられなかったので、 皆ちゃんと答えてくれたようです。

この評価は"良い"が1.0、"悪くない"が0.5、"だめ"が0.0の報酬に対応しています。この報酬の平均が写真のスコアとなります。 また、スポットに紐付いている写真のスコアのうち、最大のものをそのスポットのスコアとしました。 平均をとらなかったのは、バンディットアルゴリズムの特性として、評価が高い写真は何回も登場するので より信頼性のあるスコアが取れる一方で、評価がそこそこの写真はそれほど登場せず、そのスコアの信頼性が低いからです。

データを集めるために、東京の20~34歳男女に向けてFacebookで広告を打ってみました。

f:id:sambaiz:20151223171014p:plain

最初の方はなかなかリーチすらせず、予算消化しきれるのかなと思ったのですが、最終的に全予算を消化してくれました。 クリック率は106となっていますが、30回1セット終了までいったのはこのうち15%ぐらいです。 それ以外はほとんど1回も答えずに離脱していく傾向がありました。

f:id:sambaiz:20151223171511p:plain

これと併せて弊社のイケてる社員たちなどにもやってもらって、最終的に1040回分のデータが集まりました。

評価回数とスコアの関係は以下のようになっていて、スコアが高い写真は20回ほど評価されている一方で、 スコアが低い写真でも最低4回は評価されました。

f:id:sambaiz:20151223190214p:plain

結果発表

5位から発表したいのですが、奇しくも3位に3つのスポットが並ぶ結果となったので順位としては3位からです。 ちなみに、6位以下は、渋谷、お台場と続きます。これらが既にランク外なのは驚くべき結果ではないでしょうか。 では、それらを押しのけてランクインした本当にイケてるクリスマススポットを発表します!

3位(1) 聖蹟桜ヶ丘 0.73684 評価19回

f:id:sambaiz:20151223111412p:plain

(From a Google User)

3位一つ目は聖蹟桜ケ丘でした。もともとどういう所か知らなかったのですが、 名前がかっこいいのと、23区以外のものも含めたいということで、適当に追加してみたらまさかランクインするとは。 Wikipediaによるとジブリの「耳をすませば」などいくつかのアニメの舞台などになっているようです。

写真はル・ププランというケーキ屋さんです。有名なお店らしいです。 焼き菓子も美味しそうです。

3位(2) 三鷹 0.73684 評価19回

f:id:sambaiz:20151223112858p:plain

(From Kohta Uchikubo)

トトロだ!

www.ghibli-museum.jp

3位(3) 東京ドーム 0.73684 評価19回

ここでいう東京ドームは、東京ドームそのものではなく、周辺のエリアのことを指しています。

f:id:sambaiz:20151223132202g:plain

(From Mandarin Oriental, Tokyo)

写真はマンダリンオリエンタル 東京です。 半径2kmのエリアに入ってしまったので東京ドームに属してしまいましたが、駅でいうと三越前です。

2位 浦安 0.75000 評価20回

f:id:sambaiz:20151223133350p:plain

(From オリエンタルホテル東京ベイ)

浦安というと浦安鉄筋家族のイメージで選んで、 ここはないだろうなと思っていたのですが、ディズニーランドって浦安にあるんですね。

写真はオリエンタルホテル東京ベイです。 東京ディズニーリゾート・パートナーホテルで、公式ショップがあるみたいです。

1位 六本木 0.76190 評価21回

f:id:sambaiz:20151223134620p:plain

(From グランドハイアット東京)

ということで、本当にイケてるクリスマススポット1位はギロッポンこと六本木でした。 写真はグランドハイアット東京です。 最上階にはなんとプライベート温水プールがある部屋もあるみたいです。

まとめ

クリスマスはジブリかホテルがイケてる

参考

O'Reilly Japan - バンディットアルゴリズムによる最適化手法