間違いもあるかもしれません。本当は復習じゃなくて jupyter lab 使いたかっただけ。

A/B テスト

アドテクやウェブデザインの最適化に使われる。A, B, Cのデザインがあったとしてどれが一番コンバーションが大きいか？を調べたい時に最もシンプルな方法は A, B, Cをランダムに表示してそれぞれのコンバーションを計測するという方法。そしてこれが A/Bテストの一種。つまりインターネットマーケティングにおける何か判断するための手法を俗にA/B テストと言うらしい。

epsilon-Greedy アルゴリズム

説明

ざっくりと、バンディットアルゴリズムのアーム選択を貪欲(Greedy)に行っていくと、探索をしないと決めた選択にもっといい選択があるかもしれないからεの確率でランダムに選択を行うのがepsilon-Greedy。ランダムな探索が多すぎると、最終的な累積報酬(cumulative reward)が減ってしまういわゆる「探索・活用のジレンマ」に陥ってしまいます。実験は繰り返し3000回シミュレーションを行った平均の値を用います。

epsilon-Greedy アルゴリズムコード

""" εGreedy """
class EpsilonGreedy():
    def __init__(self, epsilon, counts, values):
        self.epsilon = epsilon
        self.counts = counts
        self.values = values
        return

    """ 初期化 """
    def init_arm(self, n_arms):
        self.counts = np.zeros(n_arms)
        self.values = np.zeros(n_arms)
        return

    """ アーム選択のルール """
    def select_arm(self):
        if random.random() > self.epsilon:
            # ε以上ならもっとも期待値が高いアームを選択
            return np.argmax(self.values)
        else:
            # ε以下ならばランダムに選択
            return r(0, len(self.values))

    """ アームの期待値を更新 """
    def update(self, chosen_arm, reward):
        self.counts[chosen_arm] = self.counts[chosen_arm] + 1
        n = self.counts[chosen_arm]
        
        # 期待値を更新
        new_value = ((n-1) / float(n)) * self.values[chosen_arm] + (1 / float(n)) * reward
        self.values[chosen_arm] = new_value
        return

実験(ベルヌーイ分布のアーム)

アームの定義

BernoulliArm、０か１をpの確率で出力するアーム、を用意します。今回はp=0.1, 0.2, 0.3, 0.5のアームを用いて実験。

実行結果

アームから得た累積報酬(cumulative reward)をアームを引いた回数で割った結果です。 0.5に近づくほど良いアームを引きに行けてます。ランダムな挙動が少なくなるε=.1のケースが終盤で良いアームをたくさん引くことになるので一番良くなっているのが確認できます。

f:id:misos:20161204154916p:plain

実験(ペナルティが大きいアームがあるケース)

アームの定義

p以下の確率でペナルティを大きく受けるように指定。 Web最適化とかの設定だとアームは時間が経過するにつれて分布も変わっていく、という仮定などが必要だと思うのでその第一歩として適当にp, qで決まる分布を設定してみる。

""" アーム """
class Arm():
    def __init__(self, p, q):
        self.p = p
        self.q = q

    def draw(self):
        rnd = random.random()
        if self.p > rnd:
            return -1.0
        elif self.q > rnd > self.p:
            return 0.5
        else:
            return 1.0

実験結果

arms = [Arm(0.0, 0.5), Arm(0.1, 0.5), Arm(0.2, 0.5), Arm(0.3, 0.5)]

と4つのアームを指定。一つだけペナルティがなく、ランダムすぎるとペナルティをたくさん受けてしまう設定にした。

f:id:misos:20161204160900p:plain

初めの方のランダムな探索ではどれもペナルティを受けてしまっているけど、εが少ない分ペナルティを避けていけていることがわかる。ということで問題設定によってハイパーパラメータのチューニングが必要なのがεGreedy。

実験(アームの分布が時間によって変化する場合)

epsilon-Greedyを定常な分布に対して使用していたけど、分布が変化したら？というのを実験的に確認します。論文たくさんあるけど..., とりあえず突然何かをきっかけにしてアームの分布が変化した場合。

f:id:misos:20161204164516p:plain

'ε=.1'のケースはアームの分布が変わっても過去の経験から良いアームを信じてランダムな挙動で探索しないため、分布が変わった途端に最悪になってしまいました。

Annealing(焼きなまし) の導入

アームを引いた回数が多くなるにつれて、探索の割合を少なくしていくように明示的に導入。

アームの定義

これまでのε-Greedyと同様のままアームの選択箇所を修正。

    def select_arm(self):
        t = sum(self.counts) + 1
        delta = 0.0000001
        epsilon = self.epsilon / (abs(math.log(math.log(t + delta)+1+delta)))

        if random.random() > epsilon:
            return np.argmax(self.values)
        else:
            return random.randrange(len(self.values))

epsilon = self.epsilon / (abs(math.log(math.log(t + delta)+1+delta)))の箇所が時間によって探索を減らしていく部分。他ブログで”アニーリングしたらε関係なく同じ結果になった”というのがあったけど、多分オライリーの本のコードを持ってきてそのまま実験したからだと思う（その本では例として ε = 1 / math.log(t + 0.0000001) としていてつまるところεに初期値は関係ない）。

※logを二回やったのは実験結果をわかりやすくするため焼きなましを遅くしただけで、通常はそんなことはしないはず。