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

lxyuma BLOG

開発関係のメモ

Bandit algorithmsのまとめ

ruby 機械学習

最近、A/B testingの文脈で出て来るBandit algorithmsのまとめ。

Bandit Algorithms

Bandit Algorithmsは、

機械学習の中の ②強化学習の中の ③n腕バンディット問題に対する④Algorithm。

  • 機械学習
    • 人間の学習行為を自動化して実現する方法の事。
  • ②強化学習
    • 現在の状態を参考にして、行動を決定する方法の事。
  • ③n腕バンディット問題(Multi Armed Bandit Problem)
    • 複数のスロットマシンが有った時、利益を最大化するにはどうしたら良いか?という問題
  • ④bandit algorithm
    • 既存の状態の観測結果を「活用」して最適な選択をしつつ、(強化学習的な所)
    • 一方で、新しい観測結果を導くために「探求」をする(ここがbanditに特有な所)

具体的に言うと、例えば、スロットマシンの前でコインを投げて、

  • 表が出たら、過去の経験から、
    • 今迄最大の報酬が出たスロットマシンを使う。(これが「活用」)
  • 裏が出たら、今後より多くの報酬を得れるか確かめるために、
    • 複数のスロットマシンから、適当にスロットマシンを選ぶ。(これが「探求」)

※これは後述のEpsilon-Greedyアルゴリズムの例。他にも幾つか考え方がある。

活用と探求

  • なぜ、探求が必要なのか?

今、回してるスロットマシンより、もっと沢山報酬を得られる可能性の高い

別のスロットマシンがあるかもしれないから。

利用のシチュエーション

よく、A/B testingに埋め込まれて使われる。

普通のA/B testingをrandomにAとBを出す実験だとすると、

それと比べて、Bandit Algorithmsは、

  • 実験(探求)をして結果を取りながら、

  • 既知の情報を「活用している」所が違っていて、

A/B testingより優れているとされる。

(要するに、途中で明らかにAが優れてる事が分かったらAばっかり出す所が良い。)

情報源

用語について

ここから、algorithmについて概説していくが、基本用語を整理する。

  • 腕(arm)

    • 選択肢の事。それぞれ、何回選択されたか?カウントを取る
  • 報酬(reward)

    • ある腕が選択された時に与えられる指標

algorithmについて

オライリー本を読むと、代表的な3種類のalgorithmsが書かれている

  • Epsilon-Greedy
  • softmax
  • UCB1

幾つか共通点があるので、先に概説。

共通点

arm選択メソッド(select_arm)

複数の選択肢から1つ選択する

この中身のロジックは、それぞれ違う。

パラメータが要るもの(Epsilon-Greedy/softmax)と要らない物(UCB1)がある。

報酬を更新するメソッド(update)

これは共通。

毎回、報酬の累計を積み上げて行く。

なので、image的には、ある腕を選択した回数をnとすると、


累計の報酬=過去(n-1回目)の報酬+新しい(n回目)の報酬。

※あくまで式のイメージ

ただ、このままだと、累計の報酬がふくれあがるので、n回の回数で割って平均を出す。


報酬の累計の平均 = ( ( ( n - 1) / n ) * 過去の報酬の累計の平均) + ( (1 / n) * 今の報酬 )

Epsilion-Greedyアルゴリズム

  • Greedy=貪欲に、現地点で最適な行動を選択する=>活用

  • 一方でEpsilionの確率で多くの選択肢からrandomに選択する=>探求

BanditBookのgithubサイトにsampleコードがあるのだが、

日本人皆大好きなruby!版が色々おかしいので、直した。

(多分、書くだけ書いて、実行されてなかったっぽい。整理したら、pull req出しておきます!)

# -*- coding:utf-8
class EpsilonGreedy
  def initialize(e, n_arms)
    @epsilon = e
    @counts = Array.new(n_arms, 0)
    @values = Array.new(n_arms, 0.0)
  end

  def reset(n_arms)
    @counts = Array.new(n_arms, 0)
    @values = Array.new(n_arms, 0.0)
  end

  def select_arm
    if rand() > @epsilon
      @values.index(@values.max)
    else
      rand(@values.size)
    end
  end

  def update(chosen_arm, reward)
    n = @counts[chosen_arm] += 1
    value = @values[chosen_arm]
    if n == 0
      @values[chosen_arm] = reward
    else
      new_value = ((n - 1) / n.to_f) * value + (1 / n.to_f) * reward
      @values[chosen_arm] = new_value
    end
    return
  end
end

この使い方もちょっと面倒くさいのだが、rewardを準備して上げる必要がある。

ベルヌーリ腕というのを使うとこんな感じ。

class BernoulliArm
  def initialize(p)
    @p = p
  end

  def draw
    if rand() > @p
      0.0
    else
      1.0
    end
  end
end

arm = BernoulliArm.new(0.2) # 0.2の確率で1のrewardを与える

epsilon = 0.1
n_arms = 3
e = EpsilonGreedy.new(epsilon, n_arms)
10000.times do
  selected = e.select_arm
  reward = arm.draw()
  e.update(selected, reward)
end

puts "腕が選択された回数 " + e.instance_variable_get(:@counts).to_s
puts "報酬の累計の平均 " + e.instance_variable_get(:@values).to_s

これを実行すると、3本の腕の選択された回数と報酬の累計の平均が出て来る。

基本はこういう形。

他のアルゴリズムは、initializeのパラメータと、select_armのロジックが違う。

後で、残り2つのアルゴリズムもrubyソース付きで追記しておく。とりあえずここまで。