ここで問題

あなたの会社ではマーケティングチームがたくさんの広告バーナーを作り出しました。どれも素晴らしいものです。
これから広告代理店を依頼するつもりですが、どういう風に最適に最もハイリターンを得られるか考える必要がありますね。
ハイリターンというのは短時間に効果的に正しいものが選べることです。もちろんA/Bテストをやってもいいのですが、そうしたら探索と活用を別々に行われ、費用と時間が膨大されます。なので全て広告は探索と活用が同時に行うことにしました。それで、今日は有効な２つのアルゴリズムをご紹介いたします。UCBとThompson samplingです。

検証用データ

横軸は広告バーナーのインデックスで縦軸は展開する回数（ユーザー数）です。上から下まで展開する際ユーザーがその広告にクリックするかどうかの判定は0と1です。この例だと２行目８つの広告を同時に展開したら広告１と広告５しかクリックされていないということです。あくまで検証のためなので、キャンペーンが終わったらわかるデータなのです。このデータが最初にはわかりません。ミッションはやっていくうちに最適な広告が選ベることです。

UCBアルゴリズム

UpperConfidenceBound.py

# Upper Confidence Bound

# ライブラリーをインポートする
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

# 検証用広告のデータをインポートする
dataset = pd.read_csv('data.csv')

# UCBを実証する
import math
N = 10000
d = 8
ads_selected = []
NumbersOfSelections = [0] * d
SumsOfRewards = [0] * d
total_reward = 0
for n in range(0, N):
    ad = 0
    max_upper_bound = 0
    for i in range(0, d):
        if (NumbersOfSelections[i] > 0):
            average_reward = SumsOfRewards[i] / NumbersOfSelections[i] # 期待値
            delta_i = math.sqrt(3/2 * math.log(n + 1) / NumbersOfSelections[i]) # ボーナス値
            upper_bound = average_reward + delta_i #評価値広告i=期待値＋ボーナス値
        else:
            upper_bound = 1e400
        if upper_bound > max_upper_bound:
            max_upper_bound = upper_bound
            ad = i
    ads_selected.append(ad)
    NumbersOfSelections[ad] = NumbersOfSelections[ad] + 1
    reward = dataset.values[n, ad]
    SumsOfRewards[ad] = SumsOfRewards[ad] + reward
    total_reward = total_reward + reward

# 結果を可視化する
plt.hist(ads_selected)
plt.title('Histogram of ads selections')
plt.xlabel('Ads')
plt.ylabel('Number of times each ad was selected')
plt.show()

Thompson samplingアルゴリズム

Uthompsonsampling.py

# Thompson Sampling

# ライブラリーをインポートする
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

# 検証用広告のデータをインポートする
dataset = pd.read_csv('data.csv')

# Thompson Samplingを実証する
import random
N = 10000
d = 8
ads_selected = []
numbers_of_rewards_1 = [0] * d
numbers_of_rewards_0 = [0] * d
total_reward = 0
for n in range(0, N):
    ad = 0
    max_rand = 0
    for i in range(0, d):
        rand_beta = random.betavariate(numbers_of_rewards_1[i] + 1, numbers_of_rewards_0[i] + 1)
        if rand_beta > max_rand:
            max_rand = rand_beta
            ad = i
    ads_selected.append(ad)
    reward = dataset.values[n, ad]
    if reward == 1:
        numbers_of_rewards_1[ad] = numbers_of_rewards_1[ad] + 1
    else:
        numbers_of_rewards_0[ad] = numbers_of_rewards_0[ad] + 1
    total_reward = total_reward + reward

# 結果を可視化する
plt.hist(ads_selected)
plt.title('Histogram of ads selections')
plt.xlabel('Ads')
plt.ylabel('Number of times each ad was selected')
plt.show()

　結果を比較する

UCBのtotal_reward（クリック数）=2361
Thompson Samplingのtotal_reward（クリック数）=2628
毎回広告をランダンム選ぶ場合（クリック数）1045
Thompson Samplingは最も効果な方法だとわかります
広告だけでなく以下のような問題も解決できる
動的価格設定：利益または収益の観点から最適な価格が選択できます。
推奨システム：どの製品が最もユーザーがきになるかを提案する。
ファイナンス：最も収益性の高い株が選択できます。
臨床試験：最小のダメージを与え、最良の治療法が選択できます。