オンライン学習 Prediction Learning and Games Ch2 オンライン学習 Prediction Learning and Games Ch2. Prediction with Expert Advice
専門家の助言による予測
roundとは オンライン学習における１個のデータからの 推論１回分のこと Cf. epoch とは、全データに対するroundを一回りすること このような状況における予測者の目標はroundあたりの regretをゼロにすること
予測者＝専門家の予測を平均 時刻tにおける専門家の予測の重み付き平均
そこで、Ri,t-1の増加関数を、非負、凸、増加関数 の微分 を用い、 とする よって Lemma2.1
Regret vectorの記法 時刻tのinstantaneous regret vector: 時刻Tまでの累積regret vector: potential function: 重み付き平均予測者：
Potential functionを用いた定理 Blackwell条件：Lemma2.1のΦによる表現 定理2.1: 予測者がpotential function に対してBlackwell条件を満たしているとき
この項はBlackwell条件より≤０ なので 定理2.1の証明 この項はBlackwell条件より≤０ なので
ΨがConcaveなのでこの項 ≤０ だから
定理2.1の利用 Regret: Ri,nの上限を与える これに定理2.1を組み合わせれば
定理2.1の利用： 多項式重み平均予測者
Corolloary 2.1 損失関数lは凸（convex)で[0,1]区間の値をとり、最小値＝０。このとき Proof.
=N
定理2.1の利用 指数重み平均予測者
Corolloary 2.2 損失関数lは凸（convex)で[0,1]区間の値をとり、最小値＝０。η>0に対して Proof.
指数重み平均予測者の最適上限：定理2.2 最適上限は以下の式であり、3.7節でこれを改善することができないことが示される。 定理2.2は、以下の補題を使えば比較的簡単に証明できる。 Lemma2.2
ηの時間依存性を除く 定理2.3 Lemma 2.3
最も優秀＝最少損失のexpertが知られている場合 半数以上が損失＝０のexpertなら、多数決で半数ずつ損失≠0のexpertを排除していくことによってlogN回で収束する。 もう少し一般化すると 定理2.4
Colloary 2.4
損失の微分を用いる予測者 指数重み予測の重みwi,t-1の定義中に現れる累積損失を累積損失の勾配（微分）に置き換える
損失の微分を用いる予測者 指数重み予測の重みwi,t-1の定義中に現れる累積損失を累積損失の勾配（微分）に置き換える
スケール変換 損失関数がM倍されているので当然
payoff（利得）の最大化
Regretが減衰する場合 「現在の損失のほうが過去の損失より大切」というのはreasonable この考え方での累積損失を分析する
定理2.7 平均減衰累積regretの下限
定理2.8平均減衰累積regretの上限（多項式重みの予測者の場合）