バンディットアルゴリズム入門

背景

• ウェブ最適化ではじめる機械学習を読んでいる
• 本書ではcontextual bandit algorithmの代表的な手法であるLinUCBが紹介されているが、理解を深めるため、直接は実装がないアルゴリズムも実装してみる

概要

• (A)Contextual Banditの一つであるLinTS（linear thompson sampling）を実装し、単純なThompson Samplingと比較する
  • 書籍ではLinUCBとUCBの比較がおこなわれている
• (B)尤度分布として適切な分布を選んだ場合と選ばなかった場合で、精度にどのような差が表れるかを確認する

課題設定

• 下記のダミーデータを想定する
• ある洗濯機のWebプロモーション画像を展開する際に2x2の4種類のプロモーションを検討している
  • 訴求内容(x_1)：利便性を強調(0)／低価格を強調(1)
  • スタイル(x_2)：芸能人の画像を使用しない(0)／芸能人の画像を使用する(1)
• どれがクリック率を最大化するか特定したい
• 真のデータ生成モデルは下記になっているとする
• 低価格を強調し、芸能人の画像を使用しない[1,0]が最もクリック率が高くなるという設定
  $$
  \begin{aligned}
  \theta& = \mathrm{logistic}(-1 + 0.4x_1+0.6x_2 -0.6x_1x_2)\\
  y&\sim \mathrm{Bernouli}(p)
  \end{aligned}
  $$

検証内容

• (A)特徴量を考慮することによる改善の検証
  • 単純に各アームの報酬の期待値を独立として推定する場合（TS）と、$x_1,x_2$といった特徴量を考慮してモデリングした場合(LinTS)で、方策の選択がどのように改善するかを比較する
• (B)適切な尤度分布の選定による改善の検証
  • 目的変数であがクリック有無である、というドメイン知識基づいた場合（事前分布にベータ分布、尤度に多項分布）と、特に基づかない場合（正規分布）で、どのような差が生まれるかを試す

比較にもちいるAgent

• NormalTSAgent：4つの選択肢の報酬がそれぞれ独立した正規分布に従うと仮定
• LinTSAgent：報酬の期待値は、訴求内容($x_1$), スタイル($x_2$), それらの交互作用($x_1,x_2$), 定数項によって決まると仮定
• BernouliTSAgent：事前分布にベータ分布、尤度にベルヌーイ分布を仮定したモデル。4つの選択肢の報酬それぞれの期待値がベータ分布に従うと仮定。

class BaseTSAgent(object):
  def __init__(self):
    self.counts = [0 for _ in range(n_arms)]
    self.wins = [0 for _ in range(n_arms)]

  def sample(self, arm, reward):
    self.counts[arm] = self.counts[arm] + 1
    self.wins[arm] = self.wins[arm] + reward


class BernouliTSAgent(BaseTSAgent):
  def get_arm(self):
    beta = lambda N, a: np.random.beta(a + 1, N - a + 1)
    result = [beta(self.counts[i], self.wins[i]) for i in range(n_arms)]
    arm = result.index(max(result))
    return arm


class NormalTSAgent(BaseTSAgent):
  def get_arm(self):
    normal = lambda mu, sigma: np.random.normal(mu, sigma)
    result = [
      normal(
        self.wins[i] / self.counts[i] if self.counts[i] > 0 else 0.0,
        np.sqrt((self.wins[i]/ self.counts[i]) * (1 - self.wins[i]/self.counts[i]) / self.counts[i]) if self.counts[i] > 0 else 1.0
      ) for i in range(n_arms)
    ]
    arm = result.index(max(result))
    return arm


class LinTSAgent(object):
  def __init__(self):
    self.phis = np.array([[arm[0], arm[1], 1] for arm in arms]).T
    self.alpha = 1
    self.sigma = 1
    self.inv_A = np.identity(self.phis.shape[0])
    self.b = np.zeros((self.phis.shape[0], 1))

  def get_arm(self):
    post_mean = self.inv_A.dot(self.b)
    post_var = self.inv_A
    pred_mean = self.phis.T.dot(post_mean)
    pred_var = self.phis.T.dot(post_var).dot(self.phis)
    result = [np.random.normal(pred_mean[i], 
                                self.alpha * np.sqrt(pred_var[i, i])) 
              for i in range(n_arms)]
    arm = np.argmax(result)
    return arm

  def sample(self, arm_index, reward):
    phi = self.phis[:, [arm_index]]
    iAppTiA = self.inv_A.dot(phi).dot(phi.T).dot(self.inv_A)
    s2_pTiAp = self.sigma ** 2 + phi.T.dot(self.inv_A).dot(phi)
    self.inv_A = self.inv_A - iAppTiA / s2_pTiAp
    self.b = self.b + (self.sigma ** 2) * reward * phi

結果

• BernouliTSAgentが、正解である[1,0]をもっとも多く選択できていた
• LinTSとNormalTSだと、明らかにLinTSがよい。NormalTSだけ明らかに正解率が低い
  

解釈

• 目的変数の性質を踏まえた適切な事前分布・尤度分布の選定が重要
  • クリック有無は2値であるので、ベルヌーイ分布などがよい
  • 母比率の検定などでは、Nが十分多い状況で、二項分布も近似的に正規分布に従うとして実施することがある。ただBandit問題では、Nが少ない初期での判断を適切にするには、正しい尤度分布の選定は必要
• 誤って正規分布を仮定していた場合でも、特徴量を使い報酬をモデリングして自由度を減らす（選択肢4つ→x1,x2と定数項の3つ）ことで、暗黙の仮定をとりこみ、それが正しければ精度は改善されそう