Presentation is loading. Please wait.

Presentation is loading. Please wait.

オンライン学習 Prediction Learning and Games Ch2

Similar presentations


Presentation on theme: "オンライン学習 Prediction Learning and Games Ch2"— Presentation transcript:

1 オンライン学習 Prediction Learning and Games Ch2
オンライン学習 Prediction Learning and Games Ch2. Prediction with Expert Advice

2 専門家の助言による予測

3 roundとは オンライン学習における1個のデータからの        推論1回分のこと
Cf. epoch とは、全データに対するroundを一回りすること このような状況における予測者の目標はroundあたりの regretをゼロにすること

4 予測者=専門家の予測を平均 時刻tにおける専門家の予測の重み付き平均

5 そこで、Ri,t-1の増加関数を、非負、凸、増加関数  の微分  を用い、         とする
よって Lemma2.1

6

7 Regret vectorの記法 時刻tのinstantaneous regret vector:
時刻Tまでの累積regret vector: potential function: 重み付き平均予測者:

8 Potential functionを用いた定理
Blackwell条件:Lemma2.1のΦによる表現 定理2.1: 予測者がpotential function             に対してBlackwell条件を満たしているとき

9 この項はBlackwell条件より≤0 なので
定理2.1の証明 この項はBlackwell条件より≤0 なので

10 ΨがConcaveなのでこの項  ≤0 だから

11 定理2.1の利用 Regret: Ri,nの上限を与える これに定理2.1を組み合わせれば

12 定理2.1の利用: 多項式重み平均予測者

13 Corolloary 2.1 損失関数lは凸(convex)で[0,1]区間の値をとり、最小値=0。このとき Proof.

14 =N

15 定理2.1の利用 指数重み平均予測者

16 Corolloary 2.2 損失関数lは凸(convex)で[0,1]区間の値をとり、最小値=0。η>0に対して Proof.

17

18 指数重み平均予測者の最適上限:定理2.2 最適上限は以下の式であり、3.7節でこれを改善することができないことが示される。
定理2.2は、以下の補題を使えば比較的簡単に証明できる。 Lemma2.2

19

20 ηの時間依存性を除く 定理2.3 Lemma 2.3

21 最も優秀=最少損失のexpertが知られている場合
半数以上が損失=0のexpertなら、多数決で半数ずつ損失≠0のexpertを排除していくことによってlogN回で収束する。 もう少し一般化すると 定理2.4

22

23 Colloary 2.4

24 損失の微分を用いる予測者 指数重み予測の重みwi,t-1の定義中に現れる累積損失を累積損失の勾配(微分)に置き換える

25 損失の微分を用いる予測者 指数重み予測の重みwi,t-1の定義中に現れる累積損失を累積損失の勾配(微分)に置き換える

26

27 スケール変換 損失関数がM倍されているので当然

28 payoff(利得)の最大化

29 Regretが減衰する場合 「現在の損失のほうが過去の損失より大切」というのはreasonable この考え方での累積損失を分析する

30 定理2.7 平均減衰累積regretの下限

31 定理2.8平均減衰累積regretの上限(多項式重みの予測者の場合)

32


Download ppt "オンライン学習 Prediction Learning and Games Ch2"

Similar presentations


Ads by Google