読者です 読者をやめる 読者になる 読者になる

バンディットアルゴリズムの復習2:softmax

前回

ε-Greedyについてやった。

Softmax

Softmaxによるアーム選択

ε-Greedyの問題点はランダムな挙動をする時、つまり期待値が最高のアーム以外を引くと決定した時、にそれらのアームを同列に扱ってしまうこと。つまりランダムな挙動をする場合は良さそうなアームも悪そうなアームも全て (1/(ε*(アームの数-1))) で扱ってしまう。実際には高い報酬が期待できそうなアームを優先的に引いたほうが、新しい良いアームを発見できる可能性が高そうに見える。

tempertureパラメータを導入して、tempertureが高ければ探索をして tempertureが低いと活用をします。

Boltzmann分布(Gibbs 分布)

熱平衡状態にある温度 t の系 が エネルギー e を取る確率を示した分布で P(e) = (1/Z) exp(- e/ t) と書ける。zが確率として扱うための正規化定数。 softmaxの文脈ではアームからの期待報酬をエネルギーとみなして、温度が低く報酬が高いほど活用の際に引かれることになる。

z = sum([math.exp(v / self.temperature) for v in self.values])
p_e = [math.exp(v / self.temperature) / z for v in self.values]

Softmaxのコード

アーム選択部分

Boltzmann分布を考慮して作り変えます。

class Softmax():
    def select_arm(self):
        z = sum([exp(v / self.temperature) for v in self.values])
        p_e = [exp(v / self.temperature) / z for v in self.values]
        return self.draw_arm(probs)

実験

300回引くシミュレーションを何回か行い、各時点での報酬の平均値を求めます。高いほど良いです。

アームの定義

前回に引き続き2つのアームを使用。

Arm0: ベルヌーイ

pの確率で0か1を出すアーム。 p = 0.1 ~ 0.9を適当に10本並べます。

class Arm0():
    def __init__(self, p):
        self.p = p

    def draw(self):
        if random.random() > self.p:
            return 0.0
        else:
            return 1.0

arms = [Arm0(p) for p in np.linspace(0.1, 0.9, 10)]

Arm1: 適当に作った分布

p,qに従って 0, 0.5, 1を出すアームが適当に4本並べました。

class Arm1():
    def __init__(self, p, q):
        self.p = p
        self.q = q

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

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

実験結果

どちらもハイパーパラメータt(emperture)の選択によって結果がかなり違うことが伺えます。

Arm0: ベルヌーイの場合

f:id:misos:20161204203807p:plain

Arm1: 適当に作った分布の場合

f:id:misos:20161204202756p:plain

次回:UCB

参考文献

バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)

バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)