めも

メモ.

バンディットアルゴリズムの復習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

参考文献

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

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

プライバシーポリシー

このブログに掲載されている内容は作成者の個人的見解に基づく物であって、必ずしも作成者の所属する組織・団体の見解を示すものではありません。また、記載が不正確であったことにより生じたいかなる損害に関しても、責任を負いかねますのでご了承ください。また、本サイトは、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。また、本サイトでは、第三者配信の広告サービス(Googleアドセンス、A8.net)を利用しており、ユーザーの興味に応じた商品やサービスの広告を表示するため、クッキー(Cookie)を使用しております。 クッキーを使用することで当サイトはお客様のコンピュータを識別できるようになりますが、お客様個人を特定できるものではありません。本サイトの管理者への問い合わせ、当ブログのプライバシーポリシーの詳細についてはこちらをご覧ください。