The Epsilon-Greedy Algorithm
ε-greedyは機械学習においてよく使われる方法であり、そんなに理解に苦しいアルゴリズムではない。
Exploit のみを続けることに対するリスクを緩和する方法である。
僕が理解できれば、みんな余裕ってわけよ！
例えば、今目の前に３台のスロットマシンがあるとしよう（k=3)。
さらにそれぞれのマシンは、それぞれ違う確率で当たりが出るとし、合計100回チャレンジできるとする。
この時、どのマシンをどのくらい使えば、もっとも高い利益を出せるかという考え方については、前回触れたこちらの通りである。
ε-greedyは先に述べたようにそこまで複雑ではない。
マシンをプレイする時、それぞれのマシンがどのような結果を出していくかを皆追うと思う。そのとき、
で現在もっともスコアの高いマシンを選択し、
で、ハイスコア出ないマシンを選択する。
この時、εは0.1とか、そういう小さい値である。
最初の12回の試合の後、マシン1を4回まわし、$ 1を2回、$ 0を2回獲得したとしよう。 このとき、マシン1の平均は$ 2/4 = $ 0.50である。
そしてマシン2を5回まわし、$ 1を3回、$ 0を2回獲得したとしよう。 マシン2の平均支払いは$ 3/5 = $ 0.60である。
そしてマシン3を3回まわし、$ 1を1回、$ 0を2回獲得したとしよう。 マシン3の平均支払いは$ 1/3 = $ 0.33である。
そして、試行13で再生するマシンを選択する必要があるが、このとき乱数pを0.0から1.0まで生成する。
また、ε= 0.10と設定したとする。
p> 0.10の場合は、現在の最高平均支払い額があるため、マシン2を選択する。
しかし、p <0.10の場合、ランダムなマシンを選択するので、各マシンは1/3の確率で選択される。
注意することは、すべてのマシンからランダムに選択するため、マシン2が選択される可能性があるということだ。
時間がたつにつれて、もっとも良いマシンはより頻繁にプレーされるため、より頻繁にプレイされる。
要するに、ε-greedy手段は、ほとんどの場合、現在の最良の選択肢を選ぶが、
ときどき小さな ε 確率でランダムなオプションを選ぶことがある。
簡単に Bandit Algorithm Basic
What is Bandit Algorithm....
スロットマシンをする時、気になるのは、「どのマシンが一番当たりを出しやすいか」である。
今、目の前にスロットマジンが５台あるとして、５０回遊べるだけのお金を持っているとしよう。
今現在の状況として、
目的：当たる確率を最大にしたい
マシン：５種類それぞれ違う当たる確率
遊べる回数：５０回
この場合、どのマシンをどのように遊べばもっとも良い結果になるのだろうか。
考えられる戦略として、
１、それぞれ均等に遊ぶ（１０回ずつ）
２、一つの台で遊び続ける
３、あたりの多かった台を集中的に選ぶ
Bandit Algorithmの目的は、
限られた試行回数の中で、もっとも良い選択をする
ということだ。
例えば、旅行の時の宿選び、合コンでの恋人選び、ランチのメニュー選びなど、
世の中には腐る程選択肢が溢れている。
ビジネスについてならば、
広告のクリエイティブはどうれが良い、メールのポイント、
たくさん思い浮かばれる。
しかし、これらを１００％予測して行動することは不可能に近く、
思考を繰り返しながら経験値をして蓄え、次のチョイスをするのがベストになってくる。
条件も限られており、予算がいくらだ、期限はいつまでだと、
選択をより困難にしてくる。
そこで、ダメな選択肢をできる限り選ばないで、ベストな結果を出したい、
という時に有効なのがBandit Algorithmである。
このアルゴリズムは２フェーズに別れており、
現在知っている情報以外の情報を得るためのExplore（例：行ってないレストランに行ってみる）と、
持ってる情報の中で利益を最大化することのExploit（例：行きつけのレストランでいつものメニューを頼む）
である。
この二つのトレードオフとして、
良い選択肢がわかっているのに、Exploreばかりしていると、効率の無駄使いになるし、
良い選択肢がまだわからないのに、Exploitばかりしていても効率的でない。
そこのバランスが重要になってくる。
このトレードオフを解決するのに使われるのが、
Algorithm Basicであり、
ExploreとExploitを効率的に行い、一定期間で最大の利益を出すメソッドである。
Python code is here.
A/B test with python (Bandit)
In this article, I am going to write a Bayesian Bandit algorithm.
import matplotlib.pyplot as plt import numpy as np from scipy.stats import beta NUM_TRIALS = 2000 BANDIT_PROBABILITIES = [0.2, 0.5, 0.75]
Bandit probabilities are divided into three value just in case. Quick favorite.
Trial number is 2000.
So, I am going to define a class called Bandit.
class Bandit: def __init__(self, p): self.p = p self.a = 1 self.b = 1 def pull(self): # arm of slot machine return np.random.random() < self.p def sample(self): # sample from current beta distribution return np.random.beta(self.a, self.b) def update(self, x): self.a += x self.b += 1 - x
This works like slot machine.
a, b are the beta parameters defined a uniform distribution in the beginning and p is the probability of winning.
This class should have a ability to pull the slot machine defined definition pull() returns the random number and we can get also sample from its current distribution.
Lastly, we have also update function. x is either 0 or 1.
def plot(bandits, trial): x = np.linspace(0, 1, 200) for b in bandits: y = beta.pdf(x, b.a, b.b) plt.plot(x, y, label="real p: %.4f" % b.p) plt.title("Bandit distributions after %s trials" % trial) plt.legend() plt.show()
This is just going to plot PDF of each bandit and we can compare it on the same chart.
OK. Then, we need to run a actual experiment.
def experiment(): bandits = [Bandit(p) for p in BANDIT_PROBABILITIES] sample_points = [5, 10, 20, 50, 100, 200, 500, 1000, 1500, 1999] for i in range(NUM_TRIALS): bestb = None maxsample = -1 allsamples = [] for b in bandits: sample = b.sample() allsamples.append("%.4f" % sample) if sample > maxsample: maxsample = sample bestb = b if i in sample_points: print("Current samples: %s" % allsamples) plot(bandits, i) x = bestb.pull() bestb.update(x) if __name__ == '__main__': experiment()
Bandit should be initialize at first.
Sample points are where we want to reasonably show a plot. Any values are ok.
We also keep track of the maximum sample and best will be.
