2018 年 2 月

第 33 卷,第 2 期

本文章是由機器翻譯。

測試回合 - 使用 C# 進行湯普森取樣

James McCaffrey

James McCaffreyThompson 取樣是一種演算法可以用來尋找多武裝的強盜問題的解決方案詞彙,衍生自事實的賭博上插槽機器非正式地稱為 「 one-armed 強盜。 」

假設您長久以來的前面三個位置的電腦。當您在其中一部機器上 pull arm 時,它將支付給您零 (美元) 或一個貨幣根據某些機率分佈的未知給您。例如,電腦可能支付平均機率為 0.5,讓您提取控制代碼在該電腦上 100 次,如果您希望支付零 (美元) 大約 50 次和一個金額大約 50 次。

您的目標是盡可能有效率地找出最佳的電腦。上述的問題是白努利強盜問題的範例,因為結果為 0 或 1。沒有強盜問題的其他型別。例如,如果每個機器付費 out 值,通常介於零和一個貨幣 (例如 55.0 美分),根據鐘形高斯分佈進行分佈,您必須高斯程序強盜問題。本文只白努利強盜問題。

有數種演算法可以用於嘗試尋找最佳的電腦。假設您是限制為總計 100 提取三部機器上。您可以嘗試 10 提取每個在電腦上,呈現每一台電腦執行追蹤。然後您可以使用剩餘的 70 提取支付 30 提取瀏覽階段期間的大部分 money 某部電腦上。這種方法的危險是您可能不正確地識別最佳的電腦。如果您使用瀏覽階段期間的許多提取時,就不需要許多左利用階段。

Thompson 取樣是聰明的演算法會持續進行調整的每部電腦的支付額估計的機率。您稍後將會看到 Thompson 關鍵取樣白努利強盜問題數學 beta 分配。

也不太可能,系統會分析插槽機器詢問由主管,但在許多重要,實際的情況下會出現多武裝的強盜問題。例如,假設您藥物製造商的工作。您剛建立四個新實驗提倡毒品 cancer 的而且您想要建立四個提倡毒品何者最有效,並至少加裝測試即時的主題。或可能是您用於電子商務公司,而且您想要決定哪一個數個新的廣告宣傳點子最成功。  

若要查看示範程式中是好的方法,請參閱這篇文章會向其中圖 1。示範分別設定三個白努利機器機率分別為支付額 (0.3、 0.5、 0.7)。在非示範案例中,機率為未知,當然。允許您總共 10 提取。目標是要判斷最佳的電腦 (機器 #3) 及大多數時候提取其控制代碼。

Thompson 取樣示範
圖 1 Thompson 取樣示範

在第一次的試用版,您會假設所有三個機器已支付額機率為 0.5。示範使用 beta 分配產生三種根據該假設的機率。這些隨機的機率是 0.7711、 0.1660 (0.1090)。由於機器 #1 相關聯的機率最高時,提取其 arm。在此情況下,機器 #1 不未支付。

在第二個的試用版,在幕後,示範會認為,第一部機器現在會有支付額機率小於 0.5。使用 beta 取樣,而這次機率 0.6696、 0.2250 (0.7654),讓電腦 #3 是選取播放,並根據是否機器付款或不調整的支付額估計的機率。

經過一段時間,因為機器 #3 中具有最高機率的支付額,它會比其他兩部電腦,通常 win 而且未支付每次電腦 #3,將予以的可能性會選取增加。

10 次之後, 電腦 #1 已播放三次,並支付一次,因此模擬猜測,則為 true 的支付額機率是約 1/3 = 0.33。機器 #2 已播放三次並支付兩次 (估計 p = 2/3 =.6667 上機器 #3 已播放四次並支付三次 (估計 p = 3/4 = 0.7500)。因此,在此範例中至少,最佳的電腦已識別出,已最常播放。

本文假設您有中繼或更好的程式設計技巧,但不會假設您知道 Thompson 取樣 」 或 「 beta 分佈。使用 C# 程式碼示範程式,但您不應該有太多無法將重構程式碼以另一種語言,例如 Visual Basic 或 Python,如果您想。示範程式的程式碼所示的本文中,將整個以及也會提供隨附的檔案下載。

了解 Beta 分配

Thompson 取樣白努利強盜問題取決於 beta 分配。若要了解 beta 分配中,您必須瞭解機率分佈執行一般。有許多種機率分佈,每一個都有一或兩個參數而定的變化。

您可能熟悉統一分佈,有兩個參數,呼叫 min 和 max,或有時候只和 b。最小值與平均分佈 = 0.0,最大值 = 1.0 會傳回 p 值介於 0.0 到 1.0 之間的每個值所在可能性相等。因此,如果您從統一分佈取樣 1,000 次,您會預期 0.90 之間 1.00 的 100 p 值的相關以取得有關 0.00 之間 0.10,100 p-介於 0.10 與 0.20,依此類推,相關的 100 p 值。如果您以繪製結果,您會看到所有關於相同高度的 10 個橫條的橫條圖。

您可能也會熟悉常態 (也稱為高斯) 分佈。常態分佈亦可依兩個參數、 平均和標準差。如果您從常態分佈,與平均取樣 1,000 次 = 0.0 和標準差 = 1.0,您應該會取得介於-0.5 和 +0.5; 的 380 z 值相關關於 240 z 值 +0.5 與 1.5 之間 (以及-0.5 之間-1.5);約 60 z 值 1.5 和 +2.5 (以及之間也-1.5 和-2.5 之間)。和 10 z 值大於 +2.5 (和 10-2.5 大於或等於)。如果您以繪製您會看到鐘形橫條圖的結果。

Beta 分佈是特色為兩個參數,通常稱為 alpha 和 beta,或有時候 a 和 b。請注意代表整個分佈,"beta"和"beta,"代表秒鐘的兩個的分佈參數之間可能的混淆。

如果您從與 beta 分配取樣 = 1,b = 1,您得到的確切相同結果為統一分佈與平均值 = 0.5。如果 a 和 b 會有不同的值,當您從 beta 分配,取得要平均的 p 值取樣 / (a + b)。例如,如果 = 3,b = 1,並重複範例,您會取得介於 0.0 到 1.0 之間的 p 值但 p 值的平均值會是 3 / (3 + 1) = 0.75。這表示 0.90 之間 1.00 的 p 值會是最常見的。0.80 之間 0.90 的 p 值將會稍微較不常見。等等,向 0.00 之間 0.10 很少 p 值。圖形中的圖 2顯示從與 beta 分配 10000 範例的結果 = 3,b = 1。

從 Beta(3,1) 發佈取樣
圖 2 取樣從 Beta(3,1) 發佈

Beta 分配和白努利強盜問題之間的連線是很難以察覺的。簡言之,beta 分配是為結合先前的白努利可能性函式。雖然基礎數學很深,Thompson 演算法實作的是,幸運的是,簡單 (相對)。

示範程式

若要建立示範程式我啟動 Visual Studio,並建立新的主控台應用程式,名為 Thompson。示範有沒有顯著的.NET Framework 相依性,因此是正常的任何版本的 Visual Studio。範本程式碼載入到編輯器視窗之後,我 Program.cs 檔案上以滑鼠右鍵按一下並重新將它命名為稍微更具描述性的 ThompsonProgram.cs,而允許 Visual Studio 會自動為我重新命名類別程式。在範本的程式碼頂端,我刪除不必要的命名空間的所有參考留下只最上層系統命名空間的參考。

中會顯示整體的程式結構,以節省空間,少數稍加編輯圖 3。控制邏輯是 Main 方法中。從 beta 分配取樣的程式定義 BetaSampler 類別實作。所有一般錯誤檢查會移除以節省空間。

圖 3 Thompson 取樣示範程式結構

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
  {
    // ...
  }
}

示範一開始會設定四個陣列:

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];

示範會使用三部機器,但 Thompson 取樣可以使用任何數目的電腦。平均支出的機率是硬式編碼。越接近的平均機率是彼此,更加困難的問題。名為 probs 陣列會保存從 beta 分配,取樣會決定哪部電腦播放的機率。名為 S (「 成功 」) 和 F (「 失敗 」) 的陣列會保存每一部機器支出和未支付,播放時的累加次數。

示範會使用兩個隨機號碼產生物件:

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

Rnd 物件用來判斷是否在選取的機器 wins,或遺失。請注意,我使用條款 win 和遺失、 支付不付出的金額,並成功和失敗,交換使用。Bs 物件用來範例 beta 分配。指定種子,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);
...

要設定為大數值,例如 1000,觀察速度次數 Thompson 取樣零最佳的電腦上。整個示範的關鍵在於範例方法的呼叫。成功和失敗的數字會傳遞至方法。常數 1.0 會新增為可回復的項目,因為需要 beta 分配 a 和 b 參數必須大於 0。如果您的機器支付額機率的某些事先知道,您無法調整以反映該資訊的常數。

顯示更新的取樣機率之後, 示範,請選取具有最大取樣機率的機器:

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

機率會取樣,即使電腦具有零 wins 和許多失敗,因為它可能仍可以選取來播放。這項機制增強了瀏覽功能的演算法。

主要的反覆項目迴圈結束時,會播放選取的機器:

...
  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 之間,用來實作白努利程序。示範結束時,會顯示估計的機率的支付額 (不終究至可能檢查除數為零),每一台電腦和每台機器已播放的次數。

實作 Beta 分配

有些出乎意料,最好我所知的.NET Framework 不需要程式庫方法範例從 beta 分配。而不是您可以採用 [相依性的外部程式庫,我決定實作從頭的其中一項。有許多的演算法,以產生測試範例。我使用開發 R C."BA"演算法H.Cheng 1978 中。整個程式碼所示圖 4

圖 4 程式定義 Beta 分配取樣

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;
  }
}

從 beta 分配取樣是一個有趣的主題,好似它本身。程式碼的快速掃描應該說服您沒有所涉及的一些聰明、 非試用版的運算。實作密切遵循來源研究,相同的變數名稱,依此類推。請注意可能無限的迴圈,而在參考資料的虛擬程式碼,但在實際執行程式碼中的明確 no-no 中很常見。您可能想要新增迴圈計數器變數,並擲回例外狀況,如果其值超過某些臨界值。

總結

這份文件和其程式碼應可提供您要試驗 Thompson 取樣多武裝白努利問題的所有資訊。它也可讓您瀏覽其他種類的支付額函式的強盜問題。例如,如果您有根據可能性函式氏支付的機器,而不是使用 beta 分配您會從取樣伽瑪分配波氏先前的共軛。

多重武裝的強盜問題是所謂的增援學習 (RL) 的範例。在 RL machine learning 中,而不是建立預測系統使用加上標籤的資料,有已知正確的答案,您會產生預測模型上作業,使用某種報酬函式。RL 是機器的學習參考資料。


Dr。James McCaffrey適用於 Microsoft Research Redmond,Wash.他已投入許多 Microsoft 產品,包括 Internet Explorer 和 Bing。Dr。在可到達 McCaffrey jamccaff@microsoft.com

非常感謝下列 Microsoft 技術專家已檢閱本文章:Chris Lee、 Ricky Loynd、 Adith Swaminathan


MSDN Magazine 論壇中的這篇文章的討論