• [アーティクル]

February 2018

Volume 33 Number 2

テストの実行 - C# を使用した Thompson Sampling

James McCaffrey

James McCaffreyThompson Sampling は、多腕バンディット問題の解を求めるために使用できるアルゴリズムです。用語「多腕バンディット」は、ギャンブルに使われるスロットマシンの俗称が「one-armed bandit (片腕バンディット)」だったことに由来します。

ここに 3 台のスロットマシンがあるとします。3 台のうちの 1 台のハンドルを引くと、誰も知らない何らかの確率分布に従って、掛け金を失うか、1 ドルが払い戻されます。たとえば、あるスロットマシンから 1 ドルの払い戻しを受ける平均確率が 0.5 だとします。つまり、このスロットマシンのハンドルを 100 回引くと、約 50 回は掛け金を失い、約 50 回は 1 ドルの払い戻しを受けると期待されます。

今回の目標は、できる限り効率良く、最高のスロットマシンを見極めることです。今回説明する問題は、結果が 0 か 1 のどちらかになるため、ベルヌーイ バンディット問題の例です。バンディット問題には他にも種類があります。たとえば、各スロットマシンが鐘状のガウス分布に従って通常 0 ～ 1 ドル (55.0 セントなど) を払い戻す場合は、ガウス過程バンディット問題です。今回取り上げるのは、ベルヌーイ バンディット問題のみです。

最高のスロットマシンを見つけるアルゴリズムはいくつかあります。3 台のスロットマシンでハンドルを引く回数は合計 100 回に制限されているとします。各スロットマシンで 10 回ずつ引いて、それぞれの成績を追跡します。この 30 回の探索段階で払い戻し金額が最も高かったスロットマシンで、残りの 70 回分ハンドルを引きます。このアプローチが危険なのは、最高のマシンを見誤る恐れがあることです。しかし、探索段階でハンドルを引く回数を増やせば、挑戦段階で引く回数が少なくなります。

Thompson Sampling は、各スロットマシンの払い戻しの推定確率を継続的に調整する優れたアルゴリズムです。後ほど説明しますが、ベルヌーイ バンディット問題における Thompson Sampling の鍵は、数学上のベータ分布です。

上司にスロット マシンの分析を頼まれることはなさそうですが、多腕バンディット問題は実際にある多くの重要なシナリオで使えます。たとえば、製薬会社で新しいがんの試験薬が 4 種類開発され、どれが最も効果的であるかを、人間の被験者を用いた試験を最小限に抑えて証明したいといったケースです。あるいは、E コマース企業で働いており、複数の新しい広告キャンペーンの中でどれが一番成功しているかを判断したいと考えているケースです。  

今回の主旨を理解するには、図 1 のデモ プログラムを見るのが一番です。デモでは、払い戻し確率がそれぞれ (0.3, 0.5, 0.7) の 3 台のベルヌーイ スロットマシンを設定します。実際のシナリオではもちろん、確率は不明です。ハンドルは合計 10 回引くことができます。目標は、最高のスロットマシン (machine #3) を見極め、そのハンドルを最も多くの回数引くことです。

Thompson Sampling のデモ
図 1 Thompson Sampling のデモ

最初の試行では、3 台のスロットマシンすべての払い戻し確率を 0.5 と仮定します。デモではベータ分布を使用し、この仮定に基づいて 3 台の確率を生成します。こうして得られるランダムな確率は (0.7711, 0.1660, 0.1090) です。machine #1 に関連付けられる確率が最も高いため、machine #1 のハンドルを引きます。この場合、machine #1 は払い戻しを行いません。

このデモは、2 回目の試行では、最初のスロットマシンの払い戻し確率が 0.5 未満になると考えます。再度ベータ分布のサンプリングを用いると、今回の確率は (0.6696, 0.2250, 0.7654) になります。そこで machine #3 を選び、ハンドルを引きます。今回も払い戻しが行われたかどうかに応じて払い戻しの推定確率を調整します。

回数を重ねると共に、machine #3 の払い戻し確率が最も高くなり、他の 2 台よりも頻繁に払い戻しを受けるため、machine #3 が選択される可能性は高くなります。

10 回の試行の結果、machine #1 は 3 回ハンドルが引かれ、1 回だけ払い戻しが行われました。そのため、このシミュレーションの払い戻しの真の確率は約 1/3 = 0.33 と推測されます。machine #2 は 3 回ハンドルが引かれ、2 回払い戻しが行われました (推定確率 = 2/3 = .6667)。machine #3 は 4 回ハンドルが引かれ、3 回払い戻しが行われました (推定確率 = 3/4 = 0.7500)。そのため、少なくともこの例では、最高のスロットマシンが特定され、そのスロットマシンが最も多く使用されました。

今回は、中級以上のプログラミング スキルがあることを前提としますが、Thompson Sampling やベータ分布の知識は問いません。デモ プログラムは C# を使用してコーディングしていますが、必要に応じてコードを Visual Basic や Python などの別の言語にリファクタリングしても大きな問題は起きません。デモ プログラムのコードは本稿にすべて掲載していますが、付属のコード ダウンロードから入手することもできます。

ベータ分布について

ベルヌーイ バンディット問題の Thompson Sampling は、ベータ分布に基づきます。ベータ分布を理解するには、一般的な確率分布を理解しておく必要があります。確率分布には数多くの種類があり、それぞれにパラメーターが 1 つか 2 つかによって変わるバリエーションがあります。

一様分布についてはよくご存じかもしれまれん。一様分布には 2 つのパラメーターがあり、それらは min と max または単に a と b と呼ばれます。min = 0.0 で max = 1.0 の一様分布は、それぞれの値が同じ確率で起こり得る 0.0 ～ 1.0 の p-value を返します。そのため、一様分布から 1000 回サンプリングを行うと、0.00 ～ 0.10 の約 100 個の p-value が取得され、0.10 ～ 0.20 の約 100 個の p-value が取得されるといったように続き、最後に 0.90 ～ 1.00 の約 100 個の p-value が取得されます。結果をグラフにすると、すべてほぼ同じ高さの 10本の棒グラフになります。

正規分布 (ガウス分布) についてもご存じかもしれません。正規分布も、平均と標準偏差という 2 つのパラメーターによって特性が決まります。平均が 0.0 で標準偏差が 1.0 の正規分布から 1,000 回サンプリングを行うと、-0.5 ～ +0.5 の約 380 個の z-value、+0.5 ～ +1.5 (および -0.5 ～ -1.5) のそれぞれ約240 個の z-value、+1.5 ～ +2.5 (および -1.5 ～ -2.5) のそれぞれ約 60 個の z-value、+2.5 よりも大きい 10 個の z-value、-2.5 未満の 10 個の z-value が取得されます。結果をグラフにすると、鐘状の棒グラフになります。

ベータ分布は、通常アルファとベータと呼ばれる 2 つのパラメーターによって特性が決まります。このパラメーターは単に a、b と呼ばれることもあります。分布全体を表す "ベータ" と 2 つ目の分布パラメーターを表す "ベータ" があり、混乱する可能性があるので注意してください。

a = 1 で b = 1 のベータ分布からサンプリングを行うと、平均が 0.5 の一様分布からのサンプリングとまったく同じ結果が得られます。a と b の値が異なる場合、ベータ分布からサンプリングを行うと、平均 a / (a+b) の p-value が取得されます。たとえば、a = 3 および b = 1 でサンプリングを繰り返すと、0.0 ～ 1.0 の p-value が得られますが、p-value の平均は 3 / (3+1) = 0.75 になります。つまり、0.90 ～ 1.00 の p-value が最も多く、0.80 ～ 0.90 の p-value はそれよりもやや少ないといったように p-value の数は減少し続け、0.00 ～ 0.10 の p-value はごくわずかになります。図 2 に a = 3 で b = 1 のベータ分布からの 10,000 個のサンプルの結果を示します。

ベータ (3,1) 分布からのサンプリング
図 2 ベータ (3,1) 分布からのサンプリング

ベータ分布とベルヌーイ バンディット問題の関係性は非常にわかりにくいものです。簡潔に言うと、ベータ分布はベルヌーイ尤度関数の共役事前分布です。基盤となる数式は非常に複雑ですが、Thompson アルゴリズムの実装はさいわいにも (比較的) 単純です。

デモ プログラム

デモ プログラムを作成するには、Visual Studio を起動して、「Thompson」という名前の新しいコンソール アプリケーションを作成します。このデモ プログラムは .NET Framework との大きな依存関係がないため、どのバージョンの Visual Studio を使用しても問題ありません。テンプレート コードがエディター ウィンドウに読み込まれたら、Program.cs ファイルを右クリックし、名前を「ThompsonProgram.cs」というそれなりにわかりやすい名前に変更します。Program クラスの名前が Visual Studio によって自動的に変更されます。テンプレート コードの先頭にある不要な名前空間への参照をすべて削除し、最上位レベルの System 名前空間への参照のみを残します。

スペースを節約するために少し編集したプログラムの全体構造を図 3 に示します。制御ロジックはすべて Main メソッドに含めています。ベータ分布からのサンプリングは、プログラム定義の BetaSampler クラスを使用して実装します。スペースを節約するために通常のエラー チェックはすべて省略しています。

図 3 Thompson Sampling デモ プログラムの構造

using System;
namespace Thompson
{
  class ThompsonProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin Thompson sampling demo");
      int N = 3;
      double[] means = new double[] { 0.3, 0.5, 0.7 };
      double[] probs = new double[N];
      int[] S = new int[N];
      int[] F = new int[N];
      Random rnd = new Random(4);
      BetaSampler bs = new BetaSampler(2);
      for (int trial = 0; trial < 10; ++trial)
      {
        Console.WriteLine("Trial " + trial);
        for (int i = 0; i < N; ++i)
          probs[i] = bs.Sample(S[i] + 1.0, F[i] + 1.0);
        Console.Write("sampling probs = ");
        for (int i= 0; i < N; ++i)
          Console.Write(probs[i].ToString("F4") + " ");
        Console.WriteLine("");
        int machine = 0;
        double highProb = 0.0;
        for (int i = 0; i < N; ++i) {
          if (probs[i] > highProb) {
            highProb = probs[i];
            machine = i;
          }
        }
        Console.Write("Playing machine " + machine);
        double p = rnd.NextDouble();
        if (p < means[machine]) {
          Console.WriteLine(" -- win");
          ++S[machine];
        }
        else {
          Console.WriteLine(" -- lose");
          ++F[machine];
        }
      }
      Console.WriteLine("Final estimates of means: ");
      for (int i = 0; i < N; ++i)  {
        double u = (S[i] * 1.0) / (S[i] + F[i]);
        Console.WriteLine(u.ToString("F4") + "  ");
      }
      Console.WriteLine("Number times machine played:");
      for (int i = 0; i < N; ++i) {
        int ct = S[i] + F[i];
        Console.WriteLine(ct + "  ");
      }
      Console.WriteLine("End demo ");
      Console.ReadLine();
    }
  }
  public class BetaSampler
  {
    // ...
  }
}

最初に 4 個の配列を設定します。

Console.WriteLine("Begin Thompson sampling demo");
int N = 3;
double[] means = new double[] { 0.3, 0.5, 0.7 };
double[] probs = new double[N];
int[] S = new int[N];
int[] F = new int[N];

このデモでは 3 台のスロットマシンを使用しますが、Thompson Sampling はスロットマシンが何台でも機能します。払い戻しの平均確率はハードコーディングしています。平均確率が近いほど、問題は難しくなります。probs という名前の配列はベータ分布のサンプリングからの確率を保持します。この配列を使って、ハンドルを引くスロットマシンを特定します。S (「成功」) と F (「失敗」) という名前の配列は、各スロットマシンのハンドルを引いて払い戻しが行われた回数と行われなかった回数を累積して保持します。

デモでは、2 つの乱数生成オブジェクトを使用します。

Random rnd = new Random(4);
BetaSampler bs = new BetaSampler(2);

rnd オブジェクトは選択したスロットマシンが払い戻しを行うか行わないかを決定します。ここでは、払い戻しが行われると行われないと、成功と失敗を同じ意味で使用しています。bs オブジェクトはベータ分布をサンプリングするのに用います。使用するシードに 2 と 4 を指定しているのは、この値が代表的なデモの実行に使用されているためにすぎません。 

メイン シミュレーション ループを以下のように始めます。

for (int trial = 0; trial < 10; ++trial) {
  Console.WriteLine("Trial " + trial);
  for (int i = 0; i < N; ++i)
    probs[i] = bs.Sample(S[i] + 1.0, F[i] + 1.0);
...

Thompson Sampling がどれほどすばやく最適なマシンに照準を合わせるかを観察するために、試行回数を 1000 などの大きな数に設定することをお勧めします。デモ全体で重要なのが Sample メソッドの呼び出しです。成功と失敗の数をこのメソッドに渡します。ベータ分布ではパラメーター a と b が 0 より大きい必要があるため、その解決策として定数 1.0 を加算しています。スロットマシンの払い戻し確率が事前に分かっている場合は、その情報を反映するために定数を調整できます。

更新されたサンプリング確率を表示したら、デモはサンプリング確率が最も高いスロットマシンを選択します。

int machine = 0;
double highProb = 0.0;
for (int i = 0; i < N; ++i) {
  if (probs[i] > highProb) {
    highProb = probs[i];
    machine = i;
  }
}

確率はサンプリングされるため、スロットマシンが何回も払い戻しを行い、1 回も掛け金の回収を行わなくても、再度選択され、ハンドルが引かれる可能性があります。このメカニズムは、アルゴリズムの探索機能を向上します。

メインの反復ループは、選択したスロットマシンのハンドルを引いて終了します。

...
  Console.Write("Playing machine " + machine);
  double p = rnd.NextDouble();
  if (p < means[machine]) {
    Console.WriteLine("win"); ++S[machine];
  }
  else {
    Console.WriteLine("lose"); ++F[machine];
  }
}

NextDouble メソッドは 0.0 ～1.0 の一様乱数値を返し、ベルヌーイ過程の実装に使用します。デモは各スロットマシンの払い戻しの推定確率 (ゼロ除算の可能性はチェックしていません) と各スロットマシンのハンドルが引かれた回数を表示して終了します。

ベータ分布の実装

少し意外ですが、筆者が知っている限り、.NET Framework にはべータ分布からサンプリングするライブラリ メソッドはありません。今回は外部ライブラリを利用する代わりに、ゼロからライブラリを実装することにしました。ベータ分布のサンプルを生成するアルゴリズムは数多くあります。今回は「BA」アルゴリズムを用いました。このアルゴリズムは、1978 年に R.C.H.Cheng によって開発されたものです。図 4 にコード全体を示します。

図 4 プログラム定義のベータ分布サンプル

public class BetaSampler
{
  public Random rnd;
  public BetaSampler(int seed)
  {
    this.rnd = new Random(seed);
  }
  public double Sample(double a, double b)
  {
    double alpha = a + b;
    double beta = 0.0;
    double u1, u2, w, v = 0.0;
    if (Math.Min(a, b) <= 1.0)
      beta = Math.Max(1 / a, 1 / b);
    else
      beta = Math.Sqrt((alpha - 2.0) /
(2 * a * b - alpha));
    double gamma = a + 1 / beta;
    while (true) {
      u1 = this.rnd.NextDouble();
      u2 = this.rnd.NextDouble();
      v = beta * Math.Log(u1 / (1 - u1));
      w = a * Math.Exp(v);
      double tmp = Math.Log(alpha / (b + w));
      if (alpha * tmp + (gamma * v) - 1.3862944 >=
 Math.Log(u1 * u1 * u2))
        break;
    }
    double x = w / (b + w);
    return x;
  }
}

ベータ分布からのサンプリングは、それ自体が魅力的なトピックです。コードにざっと目を通すと、非実験的な優れた数式が含まれていることが分かります。この実装は、原典の研究論文に厳密に従っており、変数名なども同じです。無限ループの可能性に注意してください。これは研究の疑似コードではよくあることですが、運用コードでは絶対にやってはいけません。値がしきい値を超える場合は、ループ カウンター変数を追加して例外をスローすることをお勧めします。

まとめ

本稿とコードで、多腕ベルヌーイ問題に Thompson Sampling を用いる際に必要なすべての情報を説明しました。また、バンディット問題を他の種類の払い戻し関数でテストすることも可能です。たとえば、ポアソン分布の尤度関数に従って払い戻しを行うスロットマシンがある場合、ベータ分布を使用する代わりにポアソン分布の共役事前分布であるガンマ分布からサンプリングを行うことができます。

多腕バンディット問題は、強化学習 (RL) と呼ばれるものの例です。RL 機械学習では、既知の正しい答えを持つラベル付けされた予測システムを作成する代わりに、何らかの種類の報酬関数を使用して実行時に予測モデル生成することが可能です。RL は、機械学習研究の最先端分野です。

Dr.James McCaffrey は、ワシントン州レドモンドの Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。Dr.McCaffrey の連絡先は jammc@microsoft.com (英語のみ) です。

この記事のレビューに協力してくれたマイクロソフト技術スタッフの Chris Lee、Ricky Loynd、および Adith Swaminathan に心より感謝いたします。

この記事について MSDN マガジン フォーラムで議論する