間違いもあるかもしれません。 本当は復習じゃなくて 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、0か1をpの確率で出力するアーム、を用意します。今回はp=0.1, 0.2, 0.3, 0.5のアームを用いて実験。
実行結果
アームから得た累積報酬(cumulative reward)をアームを引いた回数で割った結果です。
0.5に近づくほど良いアームを引きに行けてます。ランダムな挙動が少なくなるε=.1
のケースが終盤で良いアームをたくさん引くことになるので一番良くなっているのが確認できます。
実験(ペナルティが大きいアームがあるケース)
アームの定義
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つのアームを指定。一つだけペナルティがなく、ランダムすぎるとペナルティをたくさん受けてしまう設定にした。
初めの方のランダムな探索ではどれもペナルティを受けてしまっているけど、εが少ない分ペナルティを避けていけていることがわかる。 ということで問題設定によってハイパーパラメータのチューニングが必要なのがεGreedy。
実験(アームの分布が時間によって変化する場合)
epsilon-Greedyを定常な分布に対して使用していたけど、分布が変化したら?というのを実験的に確認します。 論文たくさんあるけど..., とりあえず突然何かをきっかけにしてアームの分布が変化した場合。
'ε=.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を二回やったのは実験結果をわかりやすくするため焼きなましを遅くしただけで、通常はそんなことはしないはず。
実験結果
アニーリングなしだとεが小さすぎると頭打ち(探索が多すぎるため)してしまったりしていたところが修正されている様子がわかります。
次回:Softmax
参考文献
バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)
- 作者: 本多淳也,中村篤祥
- 出版社/メーカー: 講談社
- 発売日: 2016/08/25
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
アルゴリズムは Bandit Algorithms for Website Optimization: Developing, Deploying, and Debugging のコードを参考にしました。