機械学習プロフェッショナルシリーズ 「バンディット問題の理論とアルゴリズム」 読書メモ

機械学習プロフェッショナルシリーズ 「バンディット問題の理論とアルゴリズム」 読書メモ

バンディット問題とは、確率的な報酬を持つ複数の選択肢の中から、最適な選択肢を選び出す問題のを指し、名称は、カジノのスロットマシン（一つ腕の強盗とも呼ばれる）を想定した際に、どのスロットマシンを選ぶべきかという問題に由来する。バンディット問題は、意思決定の問題を数理的にモデル化する一般的なフレームワークであり、機械学習や強化学習などの分野で広く研究されており、応用先としては、広告配信の最適化、医療診断の最適化、資金配分の最適化などがある。

ここではこのバンディット問題に対して機械学習プロフェッショナルシリーズ “バンディット問題の理論とアルゴリズム“をベースに述べる。

バンディット問題は、「探索」と「活用」のトレードオフを考えることが基本であり、エージェントが未知の選択肢について情報を収集するための「探索」を行い、一方で既知の選択肢についての知識を活用して最適な選択を行うために「活用」を行う。バンディット問題を解くためのアルゴリズムには、ε-greedy法、UCB（Upper Confidence Bound）、Thompson Samplingなどがある。今回は読書メモを記載する。

序章

後悔のない選択肢をあぶり出せ！　 方策やリグレット解析などの基礎理論を丁寧に解説。 最適腕識別や連続腕バンディットはもちろんのこと、 モンテカルロ木探索やインターネット広告などのより具体的な状況への対応も紹介。
まえがき
“後悔のない(without regret)”選択のためには 「探索」と「知識利用」のバランスが重要
例
ユーザーに対して、最もクリック率が高いニュースや広告を配信するためには?
現在の推定クリック率が低くても配信回数が少ないものは、 真のクリック率がより高い可能性があるために、 配信回数が多いものに比べてより積極的に配信し ユーザーの反応を観察する(探索を行う)必要がある
全体のクリック数を増やすためには 推定クリック率が高いニュースや広告を 多く発信する(知識利用を行う)必要がある
新薬の治験への応用
多腕バンディッド問題は、探索と知識利用のバランスを最適化する問題

第1章　バンディット問題とは

1.1 はじめに
バンディット問題 (bandit problem)
選択肢の集合から一つの要素を選択し、 その要素に対する報酬を得るが 他の選択肢の報酬情報は得られない、 というプロセスを繰り返す設定において
報酬和の最大化を目指す逐次決定問題
例
スロットマシンがK-5台ある
客はどのアームでも引ける
1回ごとにアームを選んで合計100回引く
どのアームが当たりやすいかの情報は無い
アームをn回引いて、最も当たりの多かったアームを残りの(100-5n)回引く
Nの値をどうすれば良いか
1腕バンディッド (one-armed bandit)
1つのアームがついた古典的なスロットマシン
多腕バンディッド問題 (multi-armed bandit problem)
K台のスロットマシンから1台のスロットマシンを選んでアームをひくことを繰り返して儲けの最大化を目指す
1.2 バンディット問題の例
バンディッド問題の例
治験 (critical trial)
次々と訪れるある病気の患者に対して、K個の治療法のどれを施すかを逐次的に決定し、治療に失敗する患者数の最小化を目指す
インターネット広告 (internet advertisting
あるwebページまたはあるキーワードに対する検索結果のページに、Kこの広告のうちいくつかの広告を選んで表示することを繰り返し、表示された広告のうちクリックされる広告の数(またはそれによる利益)の最大化を目指す
推薦システム (recommender system)
Webにおけるサービスサイトにおいて、過去の購買履歴に基づいて各ユーザーの訪問時に全商品の中からいくつかの商品を推薦し、それらのうち実際に購入される商品数(またはされによる利益)の最大化を目指す
ゲーム木検索 (game tree search)
ゲームにおいて次の候補手K通りの中から最善手を探すために、各候補の評価値としてそこから到達しうる最終盤面のランダムサンプルの平均勝率を用いる
オンライン経路制御 (online routing)
ある場所から別の場所にネットワークを介してデータを繰り返し転送する場合、いくつかあるルートのうちの一つのルートを決定し、データ遅延累積の最小化を目指す
1.3 確率的バンディットと敵対的バンディット
バンディッド問題大きく分けて、 各アームからの報酬を決めるのが、確率的なのか、 プレイヤーの方策を知っている敵対者なのかの2つの分けられる
確率的バンディット (stochastic bandit)
各アームからの報酬が何らかの確率分布に従って生成される
敵対的バンディット (adversarial bandit)
プレイヤーの方策を知っている敵対者が報酬を決める場合を想定する
最悪の場合でもうまくいく方策を考える
敵対者のタイプ
忘却型敵対者 (oblivious adversary)
プレイヤーの過去の選択に依存せず報酬を決める
適応型敵対者 (Adaptive adversary)
プレイヤーの過去の選択に依存して次の報酬を決める
1.4 プレイヤー方策の評価法
1.5 バンディット問題の歴史
1.6 関連分野
1.7 本書の構成

第2章　確率的バンディット問題の基礎知識

はじめに
確率的バンディッドニオイテ根幹をなす理論である大偏差原理の考え方について解説
中心曲限定りとの違いについて説明する
2.1 中心極限定理による確率近似
確率的バンディッド問題において考えることになる主要問題
ある広告の現在のクリック率μが5%以下である時、その真のクリック率が実はμ=10%である可能性はどれくらいか?
統計の言葉で一般的に書くと
真のクリック率がμである時、その標本平均があるx∈[0,1]に対してμ’≤xとなる確率(尤度)はどれくらいか?
標本平均μnの確率分布で、サンプル数nが大きい場合に、一般的に用いられる近似方法
中心極限定理
この近似を使ったとしても、 ある程度サンプル数が大きい場合に無条件で 「精度のよい」近似ができるとは限らない
この定理からわかることは
誤差ε以内で確率の近似をしたい場合に
εから決まるサンプル数nε以上が確保できていれば 正規分布での近似が許されるということに過ぎない
真の生起確率が0.01%である事象の確率を(絶対)誤差ε=1%で近似したとしても
その臍帯誤差は100梅にのぼり
絶対誤差が小さいからと言って近似の精度が良いとは実用上必ずしも言えない
低確率で起こる事象を生起近似により小さな相対誤差で評価するには膨大なサンプルが必要になる
ベリー・エッセンの定理
中心極限定理による近侍はε=O(1/√n)程度の誤差がある
誤差εで確率の近似を行うにはO(1/ε2)という大きなサンプル数が必要になる
2.2 裾確率の評価
中心極限定理は比較的高確率で起こる事象の確率を近似するのには便利
「標本平均が期待値から大幅にずれる確率(裾確率)」 と言ったような低頻度で起こる事象の確率を 小さな相対誤差で評価するには適していない
裾確率の評価式で最も単純なもの
定理
この不等式から、表法平均μnが真の平均μから∆以上ずれる確率は指数関数的に減少することがわかる
またこの指数2∆2はXiの分布およびμに依存しない量としてはこれ以上改善できない
これらの依存性を許した場合にはより精度の良い評価が可能
チェルノフ・ヘフディングの不等式 (Chernoff-Hoeffding’s inequality)
2.3 大偏差原理

第3章　確率的バンディット問題の方策

はじめに
確率的バンディッドにおける最も基本的な設定について説明する
達成可能な理論限界について議論する
UCB方策やトンプソン抽出といった理論限界を 達成可能な代表的な奉賛について紹介し、 その直感的な解釈について説明する
3.1 定式化
3.2 理論限界
3.3 -貪欲法
3.4 尤度に基づく方策
3.4.1 UCB方策
3.4.2 MED方策
3.5 確率一致法とトンプソン抽出
3.5.1 確率一致法の特徴と解釈
3.5.2 トンプソン抽出
3.5.3 トンプソン抽出と UCB 方策の関係
3.6 最悪時の評価
3.6.1 最悪時の評価例
3.6.2 最悪時での最適方策

第4章　確率的バンディット問題のリグレット解析

はじめに
確率的バンディッド問題におけるアルゴリズムの性能評価を行う一般的な枠組みを紹介
それによって「良い」ばっくアルゴリズムが満たすべき条件について説明する
また、この枠組みに基づき、前章で紹介したアルゴリズムのリグレット上界を与える
4.1 リグレットの分解
4.1.1 収束後の挙動
4.1.2 収束前の挙動
4.2 累積分布関数と期待値
4.3 UCB方策の性能解析
4.4 トンプソン抽出の性能解析
4.4.1 事後分布の裾確率
4.4.2 リグレット解析

第5章　敵対的バンディット問題

はじめに
敵対的バンディットにおける設定について説明する
計算論的学習理論における全情報設定のオンライン学習アルゴリズムである Hedgeアルゴリズムのバンディット版として Exp3豊作およびその変形であるExp3.O方策を紹介する
擬リグレットおよび高確率(で成り立つ)リグレット上界を証明する
擬リグレットの下界を証明し
下界と同じオーダーの擬リグレットを達成するPolyINF方策を紹介する
5.1 問題設定
5.2 オンライン学習理論とHedgeアルゴリズム
5.3 Exp3方策
5.4 Exp3.P方策
5.5 敵対的多腕バンディット問題のリグレット下界
5.6 最適オーダーの方策

第6章　最適腕識別とA/Bテスト

はじめに
これまでの章で述べたバンディット問題
各スロットマシンの期待値を推定(探索)しつつ 適切な頻度で現時点で期待値最大と推定される マシンを選択(知識利用)することで
累積報酬を最大化することを目的とした
実用上の場面では
探索の期間が明確に区別されていて
その期間中で期待値最大のスロットマシンを高確率で識別したい
本章では、このような純粋な探索の問題における効率的な方策について議論する
6.1 定式化
6.1.1 累積報酬最大化との違い
6.1.2 -最適腕識別
6.1.3 単純リグレット
6.2 標本複雑度
6.3 最適腕識別の方策
6.3.1 一様選択に基づく方法
6.3.2 スコアに基づく方法
6.4 固定予算の設定

第7章　線形モデル上のバンディット問題

はじめに
これまでの設定では
あるスロットマシンからの報酬が 別のマシンに関する情報を一切持たない場合を考えた
実際の応用では
それぞれのスロットマシンが何らかの特徴呂によって関連づけられていて
それを用いることであるスロットマシンからの報酬から 別のマシンの報酬の性質を推定できる場合が数多くある
本章では
そのような設定の代表的な定式化として
報酬期待値が特徴量に関する線形モデルにより表される場合を考える
時刻ごとにスロットマシンの特徴が変化する 文脈付きバンディットも同様の枠組みで定式化することができる
7.1 線形バンディット
7.2 文脈付きバンディット
7.3 LinUCB方策
7.4 線形モデル上のトンプソン抽出
7.4.1 正規分布モデルでの事後確率の計算
7.4.2 多変量正規分布からの乱数生成
7.4.3 誤差項が正規分布でない場合
7.5 ロジスティック回帰モデル上のバンディット

第8章　連続腕バンディットとベイズ最適化

はじめに
本章では
学習パラメータの調整などプレイヤーのとりうる行動の候補が 膨大あるいは連続的な場合のバンディット問題の定式化と方策について紹介する
報酬がガウス過程によって生成されているとするベイズ最適化についても合わせて説明する
8.1 定式化と観測モデル
8.2 リグレットの設定
8.3 期待値関数のクラス
8.3.1 滑らかさの制約
8.3.2 ベイズ最適化
8.4 連続腕バンディットの方策
8.4.1 GP-UCB方策
8.4.2 トンプソン抽出
8.4.3 期待改善量方策
8.4.4 多項式時間で実行可能な方策
8.5 共分散関数のパラメータ推定

第9章　バンディット問題の拡張

はじめに
バンディット問題には線形バンディットの他にも
様々な拡張や一般化がある
本章ではそれらのうち実用上重要 あるいは最近注目されているものを紹介する
9.1 時間変化のあるバンディット問題
9.1.1 文脈付きバンディットに基づく方法
9.1.2 敵対的バンディットに基づく方法
9.1.3 有限回の時間変化がある場合
9.1.4 その他の手法
9.2 比較バンディット
9.2.1 定式化
9.2.2 比較バンディットの方策
9.3 部分観測問題
9.3.1 部分観測問題の例
9.3.2 分類と理論限界
9.3.3 部分観測問題の方策
9.4 その他の拡張

第10章　バンディット手法の応用

はじめに
本章ではゲーム木探索、インターネット広告配信、推薦システムの3つの分野について
どのような問題がバンディット問題として扱うことができるのかを説明する
そこで使われている手法について紹介する
10.1 モンテカルロ木探索
将棋や囲碁などのゲームをプレイするAIプログラムは
できるだけ良い次の一手を見つけるために大規模な検索を行う
将棋や囲碁はゲーム理論において
二人零和完全情報ゲーム(two-player zero-sum perfect information game)
現在の局面を接点で表し
そこから一手で遷移可能な局面を子接点として枝で結び
そのそれぞれの局面からさらに一手で遷移可能な子接点を選ぶ
上記を繰り返すことで作られる木(ゲーム木game-tree)として表現することが可能
木の葉に相当するゲームの最終局面では勝ち負けがはっきりするため、 それに基づいて現在の手番のプレイヤーから見た曲面の良さを 評価値として与えることができる
ゲーム木の全ての接点の評価値を計算することにより、最善手を探す探索
三目並べのゲーム木
ミニマックス探索は全ての接点の 評価値を計算する全探索を行う
不要な部分を枝刈りする
ゲーム木を最終局面まで展開せず
何手か先で打ち切ったところまで展開し
展開を途中で打ち切った木の葉に対応する局面に ゲームの知識を用いてヒューリスティックに評価をつける
囲碁のように最終局面にかなり近くならないと 適切な評価値をつけることが難しいゲームへの適用
ブルークマンによるモンテカルロ法 (Monte Carlo method)の適用
評価したい局面から最終局面まで 乱数を使ってランダムにプレイさせる プレイアウト(playout)を行い
到達可能な最終局面の評価値をランダム抽出し
それにより得られた標本の平均をその局面の評価値と比較する
展開を途中で打ち切ったゲーム木の探索において 葉接点の評価に、モンテカルロ法を用いる探索
クーロンが開発した囲碁プレイヤープログラム(CrazyStone)
一般的なモンテカルロ木探索の処理
1. 木Tの葉接点vtの選択
2. 木Tの拡張(葉接点vtに子接点v’を追加し、それを新たなvtとする)
3. プレイアウトによる、葉接点vtから到達可能な最終局面の評価値のランダム抽出
4. ランダム抽出された評価値の葉接点vtから葉接点v0への逆伝搬
モンテカルロ木は、 上記の4つの処理にどのような方策を用いるかで 多くのバリエーションがある
UCTアルゴリズム
10.2 インターネット広告
Webページの一部を広告スペースとして借与
広告主が、広告配信会社にお金を払い
広告スホペース提供者はそこから仲介料を除いた金額を報酬として受け取る
様々な課金・報酬の方式がある
クリックごとに課金・報酬を行う方式
どの広告が最もクリック数が高いかは
実際にある程度配信してみないと クリック数を精度よく推定することはできない
探索(現時点までの配信数が少ないた目にクリック数の推定精度が低いものを配信する)と 知識利用(現時点までのクリック数が最大のものを配信する)をバランスよく行う バンディット問題の方策が有効
クリック率が最大のものを推定して配信する方式では
人気広告(どのページに出してもクリック率が高い広告)ばかりが配信されてしまいそう
実際には広告主の良村があるため、人気広告でも予算内の回数しか配信されない
人気広告でなくても、ページとの相性があり、相性の良いページに配信するとクリックりつが高くなる
オークション型広告配信設計アルゴリズム
10.3 推薦システム
サイトにおけるユーザーの購買履歴や閲覧履歴に基づいて、 各個人にあった商品などを推薦するシステム
推薦システムは情報フィルタリング(information filetring)と呼ばれる研究分野で使われている
何の情報を用いるかにより
ユーザーの人口統計的属性(性別、年齢、居住地域、収入、職業、学齢)
コンテンツ属性を用いる
閲覧履歴や購買履歴が似ているユーザーの評価値を用いる
一般的には、訓練データを用いて 線形パラメータを学習する手法が用いられる
新規ユーザーの評価として、探索と俊樹利用のバランスをとった バンディット手法による推薦が有効

付録 A 逆行列の更新
付録 B ベータ分布の裾確率