従来のWebアプリの常識を変える! Service WorkerがもたらすWebの未来

<html><head></head><body>こんにちは、プレイドの@wikrshです。
プレイドが提供している<a href="https://karte.io/" target="_blank" rel="noreferrer">KARTE</a>では、サイトに来訪するユーザに応じて様々な接客アクションを行う機能を提供しています。
接客アクションのようなウェブサイト上の施作の効果を検証する方法としてはA/Bテストが有名だと思いますが、今回のエントリーではA/Bテスト以外の手法としてバンディットアルゴリズムをざっくりと紹介したいと思います。
<h3 id="A/Bテストとバンディットアルゴリズム">A/Bテストとバンディットアルゴリズム</h3>
バンディットアルゴリズムは、いくつかの施作を実験しながら実験中に得られる効果もできるだけ大きくしたい、という目的のためのアルゴリズムです。
例えばECサイトの商品画像としてAとBの2つの画像の内どちらを表示した方が購入確率が上がるかということを知りたい場合、ユーザによって画像をランダムに表示してどちらの画像を表示した方が購入確率が高いか(もしくは有意差がないか)を検証しますが、ある画像を表示した方が購入確率が高いのであればできるだけ多くその画像を表示した方が全体の購入確率は高くなります。
A/Bテストでは十分なサンプル数を集めるまであらかじめ決めた割合(例えば1:1)でランダムに表示することを繰り返すため劣っている案も一定数表示することが必要となりますが、劣っている案を表示することは結果的に（優れた案を表示するのと比較して）コストを払っているとも考えられます。 
バンディットアルゴリズムで対象としている問題はこのコストを小さくすることであり、その時点までに得られた結果の利用の仕方・次の案の表示のさせ方のアルゴリズムになっています。
<h3 id="Epsilon-Greedyアルゴリズム">Epsilon-Greedyアルゴリズム</h3>
ここでは具体的なアルゴリズムの例として、Epsilon-Greedyアルゴリズムを紹介します。
Epsilon-Greedyアルゴリズムは単純な動作のアルゴリズムになっていて以下のような動作となります。
<ul>
<li>ある割合(0 &lt; ε &lt; 1)で選択肢からランダムに選択する</li>
<li>1-εの割合でこれまでの結果が最も良い選択肢を選択する</li>
</ul>
例えばε=0.3とした場合、先の画像の例では以下のような動作となります。
<ul>
<li>画像A、Bをそれぞれ15%ずつの割合で表示</li>
<li>残り70%はその時点での結果が良い画像を表示</li>
</ul>
各画像は最低でも15%の確率で表示されるため、十分な回数繰り返せば各選択肢の効果を検証することが可能です。 
また、70%はその時点で最も良い結果の画像を表示するため、優れた案（最適な案）が正しく選択されれば全体の結果も向上する可能性があります。
このアルゴリズムについて簡易的な実装をしたのが以下のコードです。
<pre><code class="language-coffeescript hljs">_ = require 'lodash'

class EpsilonGreedyAlgorithm
 # @params {Number} nChoices 選択肢の数
 # @params {Number} epsilon ランダムに選択を行う割合
 constructor: (@nChoices, @epsilon) -&gt;
 @initialize()

 initialize: -&gt;
 @averages = _.fill Array(@nChoices), 0 # 選択肢ごとの得られた結果の平均値
 @counts = _.fill Array(@nChoices), 0 # 選択肢ごとの選択回数
 @nBest = 0 # 現状の最良の選択肢

 # 選択肢から一つ選択する
 select: () -&gt;
 if Math.random() &lt; @epsilon
 # 全ての選択肢からランダムに選択
 return Math.floor(Math.random() * @nChoices)
 else
 # その時点で最も良い結果の選択肢を選択
 return @nBest

 # 結果を受け取って状態を更新する
 # @params {Number} n 選択肢の番号(0..nChoices-1)
 # @params {Number} reward 得られた結果(報酬)
 update: (n, reward) -&gt;
 @counts[n] += 1
 c = @counts[n]
 @averages[n] = ((c - 1) / c) * @averages[n] + (reward / c)

 @nBest = n if @averages[n] &gt; @averages[@nBest]
</code></pre>
バンディットアルゴリズムはその時点の結果を元にいずれかの選択肢を選択するという動作となっているため、結果を受け取るためのメソッド(コード上の<code>update()</code>)と選択したものを返すメソッド(コード上の<code>select()</code>)を実装しています。
以下のような形で動作します。（A案を0、B案を1としています。）
<pre><code class="language-coffeescript hljs"># A案,B案の2つのみ、e = 0.3
ega = new EpsilonGreedyAlgorithm 2, 0.3
ega.select() # =&gt; 1 (B案を選択)
... # B案を表示して結果(例えばユーザが購入したかどうか)を得る
ega.update(1, 1) # B案を選択した結果、ユーザが購入を行った
ega.select() # =&gt; 0 (A案を選択)
... # A案を表示...
</code></pre>
<h3 id="動作の検証">動作の検証</h3>
バンディットアルゴリズムでは選んだ選択肢に対するフィードバックを受けて次の動作が決まっていくため、動作の検証のためにはシミュレーションが必要となります。
ここでは<a href="http://www.oreilly.co.jp/books/9784873116273/" target="_blank" rel="noreferrer">「バンディットアルゴリズムによる最適化手法」</a>を参考に、一回の試行の結果はランダムに決定し、シミュレーションを繰り返すことで動作を検証するという形でどのような動作になるのかを見ていきたいと思います。
例えばあるA案、B案の2つをコンバージョンレートで比較したい場合は、ある一回の試行の結果を0（コンバージョンしなかった）、1（コンバージョンした）で表すことでシミュレーションが行えます。
<pre><code class="language-coffeescript hljs">class ConversionSimulator
 constructor: (@cvr) -&gt;

 # 設定したコンバージョンレートでランダムに0 or 1の結果を返す
 get_result: () -&gt;
 if Math.random() &lt; @cvr
 return 1
 else
 return 0
</code></pre>
コンバージョンレートではなく購入金額で比較したい場合は、0/1ではなく購入金額を返すようにすればよさそうです。
<pre><code class="language-coffeescript hljs">class PurchasePriceSimulator
 constructor: (@cvr, @minPrice, @maxPrice) -&gt;

 get_result: () -&gt;
 if Math.random() &lt; @cvr
 return _.random @minPrice, @maxPrice
 else
 return 0
</code></pre>
コンバージョンレートでの比較を行う場合のシミュレーションとして、A案を提示した場合は5%のCVR、B案を提示した場合は10%のCVRが得られる状況のシミュレーションを行ってみます。
<pre><code class="language-coffeescript hljs"># A案は5%のCVR、B案は10%のCVR
cvrs = [0.05, 0.10]
choices = cvrs.map (cvr) -&gt;
 new ConversionSimulator(cvr)

algo = new EpsilonGreedyAlgorithm 2, 0.3
algo.initialize()

# 1000回A/B案の選択・提示を繰り返す
results = _.times 1000, -&gt;
 n = algo.select()
 reward = choices[n].get_result()
 algo.update(n, reward)
 return n
</code></pre>
このシミュレーションを1000回繰り返して、最適な案（B案)を提示した割合をプロットした結果が下の図です。（ε=0.3）
<img src="https://ik.imagekit.io/newt/61b151f921640c0018173598/75d53380-c2f0-4cb4-80a9-bdc0130e0eda/test-1.png" alt="">
コンバージョンレートの低いA案を最適と予想して始めているため、始めの方は最適な案を選んだ割合は低いですが、回数を増すごとに最適な案を選ぶ割合が増加していることがわかると思います。 
一方でEpsilon-Greedyアルゴリズムでは一定の割合でランダムに案を選びに行くため、回数が増加しても最適な手を選ぶ割合は85%付近で収束しています。
<h3 id="その他の方法">その他の方法</h3>
バンディットアルゴリズムは上で紹介したEpsilon-Greedyアルゴリズム以外にも多種多様なものが提案されており、詳細については割愛しますが代表的なものには
<ul>
<li>Softmaxアルゴリズム</li>
<li>UCBアルゴリズム</li>
<li>Randomized Probability Matching</li>
</ul>
などがあります。 
Epsilon-Greedyアルゴリズムよりは探索・活用を単純な動作で行っていますが、これらのアルゴリズムはこれまでの結果から優位性の程度を算出して探索・活用を行ったり、サンプル数の増加に合わせて活用の割合を下げていくなどの工夫が入っています。 
また、Epsilon-Greedyアルゴリズムのεのようなパラメータを試行回数に応じて切り替えていくことで、最適な案に最終的に収束させるような方法もあります。
<h3 id="所感">所感</h3>
バンディットアルゴリズムはA/Bテストと比較して魅力的な点がある反面、 
実際の導入時に考慮する必要がある点は多いと感じました。 
今回はバンディットアルゴリズムの中でも最も単純なEpsilon-Greedyアルゴリズムを紹介しましたが、実際に導入する場合は
<ul>
<li>結果として使用する値（コンバージョンや購入金額等）に対してどのような動作になるか</li>
<li>パフォーマンスの面から逐次更新ではなくバッチ更新とした場合にはどのような挙動となるか</li>
<li>パラメータの設定やテスト期間をどのように設定するか</li>
</ul>
などを検討していく必要があると思います。 
バッチでの更新方法については実際の導入例もあるようですので、今後はこの辺りを検討していきたいと思います。
<h3 id="最後に">最後に</h3>
ウェブ接客プラットフォーム「<a href="https://karte.io/" target="_blank" rel="noreferrer">KARTE</a>」を運営するプレイドでは、 
KARTEを支える技術に興味を持つエンジニア（インターンも！）を募集しています。
詳しくは<a href="https://www.wantedly.com/companies/plaid/projects" target="_blank" rel="noreferrer">こちら</a>（Wantedly）をご覧ください。 
もしくはこちらのボタンよりお気軽に「話を聞きに行きたい」と押してください！
<div class="wantedly-visit-button" data-visit-button-id="lyE_IgY4VF5ukBo_EUKZLg" data-width="300" data-height="60"></div>
<script>
 (function(d, s, id) {
 var js, fjs = d.getElementsByTagName(s)[0];
 if (d.getElementById(id)) return;
 js = d.createElement(s); js.id = id;
 js.src = "https://platform.wantedly.com/visit_buttons/script.js";
 fjs.parentNode.insertBefore(js, fjs);
 }(document, "script", "wantedly-visit-buttons-wjs"));
</script>
</body></html>

今回のエントリーではA/Bテスト以外の手法としてバンディットアルゴリズムをざっくりと紹介したいと思います。

A/Bテストより無駄なく最適化できる？バンディットアルゴリズムを試してみた