jz_trunkの日記

日記.できるだけ毎日書こうとしている.

Online Decision Problem(文章の練習1回目)

最近,オンライン最適化やその周辺のことを調べていて技術的なことを書く練習という意味も兼ねて まとめてみようと思っていたが,勉強中に迷子になった.ので,少しずつまとめてみる

日本語ではオンライン決定問題,だろうか.しかし,調べてみると日本語の資料ではオンライン予測問題という名前の方が多いようだ. よく出てくる問題の例はエキスパートのアドバイスをもとに,次の予測を行うというもの. 具体例として,クイズを考えてみると,次のようになる.

 t\ (t=1, 2, 3, \ldots T) 問目のクイズの問題に対して

  1.  n 人のエキスパートからその問題の回答の意見  b_i (i=1, 2, \ldots ,n) が得られる
  2. 回答者はエキスパートの意見をもとに,クイズの回答  x_t を決定
  3. クイズの答えが明かされ,自分の回答および各エキスパートの意見に対するコスト  f_t(x_t), f_t(b_i) がわかる.

ここで,回答者としては2の回答を決める部分だけ,変更ができる.最も正答率を高くするにはどのようにエキスパートの意見を利用するのが良いだろうか, という問題である.

簡単な場合を考えるために,ここで2つの仮定を置く.

  1. クイズはマルバツ問題,つまり  b_i, x_i\in\{0, 1\}
  2. エキスパートの中に少なくとも1人,全問正解するエキスパートがいる.

これらの仮定のもとでは,各時刻  t において,これまで誤答がないエキスパートの意見を多数決で採用,という単純なアルゴリズムが考えられる. このアルゴリズムはMajority Algorithmと呼ばれている. このアルゴリズムは最大でも  \lfloor \log_2(n)\rfloor 回の間違いしか起こさないことが証明できる. 厳密な証明は書かないけれど.このアルゴリズムが誤答する場合,エキスパートの少なくとも半数が誤答している. なので,1回の誤答により,次から多数決に参加するエキスパートの数は最も減りが少ない場合でも半分になる. 最悪でも  \lfloor \log_2(n)\rfloor 回エキスパートの人数を半分にしていくと,必ず常に正解するエキスパート1人が絞り込めてしまうので, あとはもう誤答は起こらない.

ただし,このシンプルな例は明らかに非現実的である. なぜならば,エキスパートの中に少なくとも1人,全問正解するエキスパートがいるという仮定が強すぎるからだ.

しかし,このアルゴリズムを次のように修正すれば,全問正解するエキスパートの存在を仮定しなくても,誤答回数を上から抑えることができる. 次のアルゴリズムをWeight Majority Algorithmという.疑似コードを参考にした資料より引っ張ってきた. Majority Algorithmとの違いは,エキスパートが誤答をした場合でも,信用度  w_i を減少させたうえで, それ以降の予測にアドバイスを利用する点である. \varepsilonがパラメータで,これに依存して, 誤り回数  M が \begin{equation} M < \left(\frac{2}{1-\varepsilon}\right)m + \left(\frac{2}{\varepsilon}\right)\mathrm{ln}(n). \end{equation} と抑えられる.証明はpdfを参照.

f:id:jz_trunk:20161021230745p:plain http://www.cs.cornell.edu/courses/cs683/2007sp/lecnotes/week1.pdf

他にも毎回1人のエキスパートを選んでそのアドバイスを採用するアルゴリズム(Hedge Algorithm)もある.

一般的な枠組みにすると,

 t (t=1, 2, \ldots ,T) において

  1. 意思決定を行う(過去の誤りなどを考慮)
  2. 意思決定後にコストが計測される

ということをずっと繰り返していく問題になっている.

長々と語ってきたは良いのだが,機械学習ではここまで広い枠組みではなくて, 意思決定の際に,凸集合からパラメータベクトルを選択するということが多い. 例えば,パーセプトロンSVMのオンライン更新則はそちらのOnline Convex Optimizationという 問題に属しているようだ.そっちはそっちでまた書けたら良いかな.

文章の練習終わり,疲れた. 見返してみると,たったこれだけのことに時間をかけすぎた.もう少しライトに書いた方が良いかもしれない. でも書く気で調べると,知識を定着させようという思いが生まれるという効果は感じられたので, もう少しバランスを見ながらやっていこうとおもう.