統計的学習理論読み Chapter 3

MLPシリーズ『統計的学習理論』（金森敬文著）Chapter 3 の解説

Transcript

1. 統計的学習理論読み（Chapter 3） 松井孝太 名古屋大学大学院医学系研究科 生物統計学分野 matsui.k@med.nagoya-u.ac.jp
2. Table of contents 1. 判別適合的損失 1.1 マージン損失 1.2 判別適合的損失 1.3 凸マージン損失 1.4 判別適合性定理: 一般のマージン損失 1
3. 導入 本スライドは [4] の第 3 章のまとめである. ▶ 判別問題においてサロゲート損失を用いることの正当化 ▶ 理論的に良いサロゲート損失とは何か？ がメイントピック 2
4. Table of contents 1. 判別適合的損失 3
5. 判別適合的損失 4
6. 判別適合的損失 マージン損失 5
7. マージン損失 ▶ X : input space, Y = {+1, −1} binary label ▶ G ⊂ {g : X → R} a set of classification functions ▶ H = {sign ◦ g | g ∈ G} : hypothesis set Definition 1 (margin, margin loss) 判別関数 g ∈ G と data (x, y) ∈ X × Y に対して yg(x) を margin という. また, 非負値関数 ϕ : R → R≥0 に対して g の margin loss を ϕ(yg(x)) で定 義する. Example 1 (0-1 margin loss) m ∈ R に対して ϕerr : m → 1[m ≤ 0] で定義される margin loss を考える. 0-1 loss ℓerr (sign(g(x)), y) = +1 if sign(g(x)) = y 0 otherwise に対して, ℓerr (sign(g(x)), y) = ϕerr (yg(x)) if g(x) = 0 ≤ ϕerr (0) = 1 if g(x) = 0 が成立. 6
8. 経験 · 予測 ϕ-損失 I Definition 2 (経験 · 予測 ϕ-損失) 判別関数 g に対して, ˆ Rϕ (g) := 1 n n i=1 ϕ(yi g(xi )) (empirical ϕ-loss) Rϕ (g) := E[ϕ(Y g(X))] (predictive ϕ-loss) 特に, ˆ Rerr (g) := 1 n n i=1 1[sign(g(xi )) = y] (empirical classification error) Rerr (g) := E[1[sign(g(X)) = Y ]] (predictive classification error) と定義 7
9. 経験 · 予測 ϕ-損失 II Remark 1 ∀m ∈ R, ϕerr (m) ≤ ϕ(m) のとき, ˆ Rerr (g) ≤ ˆ Rϕ (g) Rerr (g) ≤ Rϕ (g) が成立 (ϕ-損失は判別誤差の上界を与える). Notation ▶ R∗ ϕ := inf g:measurable Rϕ (g) ▶ R∗ err := inf g:measurable Rerr (g) これから考えること 上界が小さければ ˆ Rerr , Rerr も小さい (ので上界で surrogate する) −→ Rϕ (g) − R∗ ϕ と Rerr (g) − R∗ err の関係を評価する 8
10. Surrogate loss Definition 3 (surrogate loss) ▶ hinge loss (SVM) ϕ(m) := max{0, 1 − m} ▶ exponential loss (boosting) ϕ(m) := e−m ▶ logistic loss (logistic regression) ϕ(m) := log(1 + e−m) これらは全て単調非増加な凸関数 ▶ ˆ Rϕ (g) の最小化によりデータ上でマージン yg(x) が大きくなり, 多く の学習データで sign(g(x)) = y の成立が期待される. ▶ 凸性から最適化計算が効率的に実行できる. 9
11. 判別適合的損失 判別適合的損失 10
12. 予測 ϕ-損失と予測判別誤差との関係 Rϕ (g) と Rerr (g) との関係を調べる. まず定義から, Rϕ (g) = E[ϕ(Y g(X))] = EX [EY [ϕ(Y g(X)) | X]] と書ける (条件付き期待値の条件に関する期待値). 関数 Cη (α) を Cη (α) := ηϕ(α) + (1 − η)ϕ(−α) とおくと, 内部の期待値は以下のように書ける: EY [ϕ(Y g(X)) | X] =Pr(Y = +1 | X)ϕ(g(X)) + (1 − Pr(Y = +1 | X)) =Pr(Y =−1 | X) ϕ(−g(X)) =Cη (g(X)) ここで, η = Pr(Y = +1 | X) とおいた. 11
13. 予測 ϕ-損失と予測判別誤差との関係 II Cη と Bayes rule との関係 Rerr を最小にする Bayes rule h0 は, h0 (x) = arg max y∈{+1,−1} Pr(Y = y | X = x) で与えられる. η = Pr(Y = +1 | X) の言葉で書くと, η > 1 2 =⇒ ˆ y = +1 η < 1 2 =⇒ ˆ y = −1 Proposition 1 sign ◦ g∗ (g∗ = arg min Cη (g(X))) が Bayes rule ⇐⇒ ∀η ∈ [0, 1]\{1 2 } に対して, inf g:g(X)(η− 1 2 )≤0 Cη (g(X)) > inf g Cη (g(X)) 12
14. 予測 ϕ-損失と予測判別誤差との関係 III (Prop の説明) 判別器 g について, 以下が成立していてほしい: sign(g(x)) = sign(α) = sign(η − 1 2 ) Bayes rule すなわち, α η − 1 2 ≥ 0. (1) いま, 上記を満たさない領域で Cη を最小化し, その最適解を ˆ α とおく: ˆ α = arg min α:α(η− 1 2 )≤0 Cη (α) もし, ˆ α ≤ infα∈R Cη (α) であれば, ˆ α に対応する判別関数 ˆ g から構成される 仮説 sign ◦ ˆ g は Bayes rule とはならない ((1) が満たされないから). 13
15. Classification calibrated loss Definition 4 (classification calibrated loss) H(η) = inf α∈R Cη (α), H−(η) = inf α(η− 1 2 )≤0 Cη (α) とおく. ∀η ∈ [0, 1]\{1 2 } に対して, H−(η) > H(η) が成立するとき, マージン損失 ϕ を classification-calibrated loss (CC-loss) と呼ぶ. Remark 2 CC-loss ϕ を採用したとき, 予測 ϕ-損失 Rϕ (g) を最小にする判別関数 g は Bayes rule を与える. 14
16. Classification calibrated loss II θ ∈ [−1, 1] に対して, ψ0 を以下で定義 ψ0 (θ) := H− 1 + θ 2 − H 1 + θ 2 Proposition 2 マージン損失 ϕ が CC-loss ⇐⇒ ∀θ = 0, ψ0 (θ) > 0 (∵) (⇒) ϕ が CC-loss とすると, ∀η ∈ [0, 1]\{1 2 } に対して H−(η) > H(η) が成 立. ここで, θ ∈ [−1, 1]\{0} に対して 1 + θ 2 ∈ [0, 1]\ 1 2 を η とおけば, ψ0 (θ) = H−(η) − H(η) > 0 が言える. (⇐) は以上を逆にたどれば良い. 2 15
17. Classification calibrated loss III ψ0 に対して, 以下の条件を満たす凸関数 ψ を考える (ψ0 の凸包と呼ぶ) 1. ψ0 ≥ ψ 2. ∀ ˜ ψ : convex, ψ0 ≥ ˜ ψ ⇒ ψ ≥ ˜ ψ Proposition 3 ψ(θ) = sup ˜ ψ ˜ ψ(θ) | ∀ ˜ ψ : cvx s.t. ψ0 ≥ ˜ ψ (∵) 1, 2, 及び Prop B6 の 3 より 2 Prop B6-3 ∀I : index set, {fi }i∈I : convex family に対して, f(x) = supi∈I fi (x) は convex function 16
18. Classification calibrated loss IV Lemma 1 (3.3) 1. ψ0 (θ) の convex-hull ψ(θ) は (−1, 1) 上連続関数かつ ψ(0) = 0 2. ψ0 , ψ は共に [−1, 1] 上の偶関数 (proof) (1) convex-hull ψ は [−1, 1] 上の凸関数だから, Thm B7 より (−1, 1) 上で連続. Thm B7 (凸関数の連続性) 凸関数 f に対して int(dom(f)) = ∅ のとき, f は int(dom(f)) 上で連続 θ = 0 のとき, H 1 2 = inf α C1/2 (α) = H− 1 2 となる (η − 1/2 = 0 なので H− における α の制約はなくなる). よって ψ0 (1 2 ) = 0. 17
19. Classification calibrated loss V (proof つづき) ▶ ϕ が CC-loss のとき, H−(η) − H(η) > 0, ∀η = 1 2 であるから, 上の事実 と合わせると ψ0 ≥ 0 (非負関数) であることが分かる. ▶ ˜ ψ = 0 (定値関数) とすると, ψ0 の convex-hull ψ に対して定義より ψ ≥ 0 が成立 以上より, 0 = ψ0 (0) ≥ ψ(0) ≥ 0 だから, ψ = 0 が成立 (真中の不等式は ψ の定義の (1) より). 偶関数であること 定義より Cη (α) = C1−η (−α) なので, H(η) = H(1 − η) が成立 (α の前の符号は inf で吸収される) 18
20. Classification calibrated loss VI (proof つづき) また, α(2η − 1) ≥ 0 ⇐⇒ − α(2(1 − η) − 1) ≥ 0 なので, H−(η) = inf α(2η−1)≤0 Cη (α) = inf −α(2(1−η)−1)≤0 C1−η (−α) = H−(1 − η) よって, ψ0 (θ) = H− 1 + θ 2 − H 1 + θ 2 = H− 1 − 1 + θ 2 − H 1 − 1 + θ 2 = H− 1 − θ 2 − H 1 − θ 2 = ψ0 (−θ) だから, ψ0 は偶関数. いま, ∀ ˜ ψ s.t. ψ0 ≥ ˜ ψ に対して ψ(θ) = max{ ˜ ψ(θ), ˜ ψ(−θ)} とおくと, ψ は偶関数で, ψ0 ≥ ψ ≥ ˜ ψ となるので, ψ は ψ0 の convex-hull. 2 19
21. Classification calibrated loss VII Theorem 2 (3.4 予測 ϕ-loss と予測判別誤差の関係) ∀ϕ : margin loss, ∀f : classifier, ∀D : distribution, ψ(Rerr (f) − R∗ err ) ≤ Rϕ (f) − R∗ ϕ i.e. expected risk の上界の expected ϕ-risk が与える. (proof) η(X) = Pr(Y = +1|X) とおく. このとき, Bayes rule は η(X) − 1 2 > 0 =⇒ y = +1 η(X) − 1 2 < 0 =⇒ y = −1 よって, Rerr (f) − R∗ err =EX [EY [1sign(f(X))̸=Y |X]] − EX [EY [1sign(η(X)− 1 2 )̸=Y |X]] =EX [EY [1sign(f(X))̸=Y − 1sign(η(X)− 1 2 )̸=Y |X]] 20
22. Classification calibrated loss VIII さらに, EY [1sign(f(X))̸=Y − 1sign(η(X)− 1 2 )̸=Y |X] = 1sign(f(X))̸=+1 − 1sign(η(X)− 1 2 )̸=+1 η(X) + 1sign(f(X))̸=−1 − 1sign(η(X)− 1 2 )̸=−1 (1 − η(X)) ここで, sign(f(X)) = +1 かつ sign(η(X) − 1 2 ) = −1 のとき, r.h.s = (0 − 1)η(X) + (1 − 0)(1 − η(X)) = 1 − 2η(X) また, sign(f(X)) = −1 かつ sign(η(X) − 1 2 ) = +1 のとき, r.h.s. = (1 − 0)η(X) + (0 − 1)(1 − η(X)) = 2η(X) − 1 以上を合わせると, r.h.s. = 1sign(f(X))̸=sign(η(X)− 1 2 ) × |2η(X) − 1| 21
23. Classification calibrated loss !X よって, ψ(Rerr (f) − R∗ err ) (Jensen →) ≤E[ψ(1sign(f(X))̸=sign(η(X)− 1 2 ) × |2η(X) − 1|)] =E[1sign(f(X))̸=sign(η(X)− 1 2 ) × ψ(|2η(X) − 1|)] ≤E[1sign(f(X))̸=sign(η(X)− 1 2 ) × ψ0 (|2η(X) − 1|)] ▶ 真中の = は, 1 = 1 or 0 より, ψ(1 × x) = 1 × ψ(x) if 1 = 1 ψ(1 × x) = 0 = 1 × ψ(x) if 1 = 0 から従う. ▶ 最後の ≤ は, ψ0 ≥ ψ から従う. 22
24. Classification calibrated loss X また, ψ0 (|2η(X) − 1|) =H− 1 + |2η(X) − 1| 2 − H 1 + |2η(X) − 1| 2 = H−(η(X)) − H(η(X)) if 2η(X) − 1 > 0 H−(1 − η(X)) − H(1 − η(X)) otherwise かつ H−(η) = H−(1 − η), H(η) = H(1 − η) より, E[{·} × ψ0 (|2η(X) − 1|)] = E[{·} × (H−(η(X)) − H(η(X)))] ≤ E[{·} × (Cη(X) (f(X)) − H(η(X)))] (∵)H−(η(X)) = inf f(X) Cη(X) (f(X)) ≤ E[Cη(X) (f(X)) − H(η(X))] = Rϕ (f) − R∗ ϕ 以上より, ψ(Rerr (f) − R∗ err ) ≤ Rϕ (f) − R∗ ϕ 2 23
25. 判別適合的損失 凸マージン損失 24
26. Convex Margin Loss convex function ϕ に対して ϕ-margin loss が C.C. かどうかを判定する Theorem 3 (3.5 C.C. Theorem for convex margin loss) ϕ が convex, differentiable, ϕ′(0) < 0 のとき, 以下が成立 1. ϕ-margin loss は C.C. 2. ψ(θ) = ϕ(0) − H 1+θ 2 3. ∀{fi } : measurable functions, ∀D : distribution on X × {±1} Rϕ (fi ) → R∗ ϕ =⇒ Rerr (fi ) → R∗ err Remark 予測 ϕ 損失が小さい ⇒ 予測判別誤差 ≈ Bayes error よって ˆ g = arg min g ˆ Rϕ (g) に対して, Rϕ (ˆ g) が小さい ⇒ Rerr (ˆ g) ≈ R∗ err 3 の証明は 3.4 節の定理 3.6 で一般の margin loss について行う 25
27. Convex Margin Loss II (proof) 1 の証明 η > 1 2 のとき, Cη (α) = ηϕ(α) + (1 − η)ϕ(α) が α ≤ 0 で最小値をとらないこ とを示す (η > 1 2 のときも同様のことが α ≥ 0 に対して示せる) これが言えると H(η) = inf α∈R Cη (α), H−(η) = inf α(2η−1)≤0 Cη (α) に対して, η > 1 2 のとき, α(2η − 1) ≥ 0 ⇐⇒ α ≤ 0 だから, Cη (α) が α ≤ 0 で 最小値を取らなければ H−(η) > H(η) が成立. 一方, η < 1 2 のとき, α(2η − 1) ≥ 0 ⇐⇒ α ≥ 0 だから, Cη (α) が α ≥ 0 で最小値を取らなければ, 同様に H−(η) > H(η) が成立. 両者を合わせると, Def 3.2 より ϕ が C.C. であると言える. 26
28. Convex Margin Loss III (proof) 1 の証明つづき Cη (α) を α = 0 で微分すると, C′ η (0) = d dα Cη (α) α=0 = ηϕ′(0) − (1 − η)ϕ′(0) = (2η − 1)ϕ′(0) ϕ′(0) < 0 より, η > 1 2 に対して, C′ η (0) < 0 が成立. このとき以下が成立 ∃α0 > 0 s.t. Cη (α0 ) − Cη (0) α0 < C′ η (0) 2 < 0 (3.5) (∵) def より, ∀ε > 0, ∃δ > 0 s.t. ∀α with |α| < δ, Cη(α)−Cη(0) α − C′ η (0) < ε で あり, C′ η (0) < 0 より, C′ η (0) 2 > C′ η (0) が成立. 一方実数の連続性から次が成 立: ∀ε > 0, ∃α0 s.t. Cη (α0 ) − Cη (0) α0 < C′ η (0) + ε 特に, C′ η (0) + ε < C′ η (0) 2 となるように ε をとれば良い. 27
29. Convex Margin Loss IV (proof) 1 の証明つづき 一方, Cη (α) は convex (ϕ が convex なので) だから, ∀α ∈ R, Cη (α) ≥ Cη (0) + C′ η (0)(α − 0) が成立 (convex function の特徴付け). よって, α ≤ α0 2 なる任意の α ∈ R で, Cη (α) ≥ Cη (0) + αC′ η (0) ≥ Cη (0) + α0 2 C′ η (0) by (3.5) → > Cη (α0 ) が成立. 以上より, Cη (α) は α ≤ 0 では最小値をとらない. Remark 赤字の部分は, 恐らく “∀α ≤ 0 で” で良い 28
30. Convex Margin Loss V (proof) 2 の証明 ϕ(0) = ηϕ(0) + (1 − η)ϕ(0) = Cη (0) ≥ inf α(2η−1)≤0 Cη (α) = H−(η) が成立. また, ϕ の convexity から, ∀α ∈ R, ϕ(α) ≥ ϕ(0) + αϕ′(0). よって, ϕ(0) ≥ inf α(2η−1)≤0 ηϕ(α) + (1 − η)ϕ(−α) ≥ inf α(2η−1)≤0 η(ϕ(0) + αϕ′(0)) + (1 − η)(ϕ(0) − αϕ′(0)) = ϕ(0) + inf α(2η−1)≤0 α(2η − 1)ϕ′(0) = ϕ(0) ▶ 最後の等号は, ϕ′(0) < 0 より, α(2η − 1)ϕ′(0) ≥ 0 なので, 第 2 項が 0 と なることから従う. 29
31. Convex Margin Loss VI (proof) 2 の証明つづき 従って ϕ(0) = H−(η) が言えるので, ψ0 (θ) = ϕ(0) − H 1 = θ 2 を得る. いま, α∗ = arg inf C1+θ 2 (α) とすると, H 1 + θ 2 = inf α∈R C1+θ 2 (α) = 1 + θ 2 ϕ(α∗) + 1 − θ 2 ϕ(−α∗) = ϕ(α∗) − ϕ(−α∗) 2 θ + ϕ(α∗) − ϕ(−α∗) 2 より, H 1+θ 2 は θ に関して線形 (特に, concave). よって, ψ0 は convex - concave = convex + convex = convex だから, ψ0 (θ) = ψ(θ) 2 30
32. Convex Margin Loss VII Remark 定理 3.5 の逆も成立つ. i.e. convex margin loss ϕ が C.C. =⇒ ϕ(α) は α = 0 で微分可能で ϕ′(0) < 0 31
33. Example : Exponential Loss I ϕ(m) = e−m とすると, ▶ ϕ は m = 0 で微分可能 ▶ ϕ′(0) = −1 < 0 だから, 定理 3.5 の仮定を満たす. よって ϕ は C.C. loss また, Cη (α) = ηϕ(α) + (1 − η)ϕ(−α) = ηe−α + (1 − η)eα, d dα Cη (α) = −ηe−α + (1 − η)eα = 0 ⇐⇒ log η + log e−α = log(1 − η) + log eα より, Cη (α) は α = 1 2 log η 1−η で最小値をとる. 32
34. Example : Exponential Loss II よって, H(η) = Cη 1 2 log η 1 − η = η exp − 1 2 log η 1 − η + (1 − η) exp 1 2 log η 1 − η = η η 1 − η −1/2 + (1 − η) η 1 − η 1/2 = η × 1 − η η + (1 − η) × η 1 − η = 2 η(1 − η) となり, ψ(θ) = ϕ(0) − H 1 + θ 2 = 1 − 1 − θ2 を得る ([0, 1] 上 strictly monotone increase) 33
35. Example : Logistic Loss I ϕ(m) = log(1 + e−m) とすると, ▶ ϕ は m = 0 で微分可能 ▶ ϕ′(0) = −1 2 < 0 だから, 定理 3.5 の仮定を満たす. よって ϕ は C.C. loss また, Cη (α) = η log(1 + e−α) + (1 − η)(1 + eα), d dα Cη (α) = −ηe−α 1 + e−α + (1 − η)eα 1 + eα = 0 ⇐⇒ (1 − η)eα = η(e−α + 1) 1 + e−α = η 34
36. Example : Logistic Loss II よって, H(η) = Cη log η 1 − η = η log 1 + exp − log η 1 − η + (1 − η) log 1 + exp log η 1 − η = η 1 + 1 − η η + (1 − η) 1 + η 1 − η = η × log 1 η + (1 − η) × log 1 1 − η = −η log η − (1 − η) log(1 − η) となり, これは binary random variable に対する entropy に相当する. また, ψ(θ) = ϕ(0) − H 1 + θ 2 = log 2 + 1 + θ 2 log 1 + θ 2 + 1 − θ 2 log 1 − θ 2 を得る ([0, 1] 上 strictly monotone increase) 35
37. Example : Hinge Loss I ϕ(m) = max{1 − m, 0} とすると, ▶ ϕ は m = 0 で微分可能 ▶ ϕ′(0) = −1 < 0 だから, 定理 3.5 の仮定を満たす. よって ϕ は C.C. loss. また, Cη (α) = η max{1 − α, 0} + (1 − η) max{1 + α, 0} =        η(1 − α) if α ≤ −1 (1 − 2η)α + 1 if − 1 < α ≤ 1 (1 − η)(1 + α) if 1 < α より, min Cη (α) =        2η at α = −1 if 0 ≤ η < 1 2 2(1 − η) at α = 1 if 1 2 < η ≤ 1 1 if η = 1 2 36
38. Example : Hinge Loss II よって, ψ(θ) = ϕ(0) − H 1 + θ 2 = 1 +        1 + θ if − 1 < θ < 0 1 if θ = 0 1 − θ if 0 < θ ≤ 1 =        −θ if − 1 < θ < 0 0 if θ = 0 1 if 0 < θ < 1 = |θ| を得る ([0, 1] 上 strictly monotone increase) 37
39. Example : Squared Hinge Loss I ϕ(m) = (max{1 − m, 0})2 とすると, ▶ ϕ は m = 0 で微分可能 ▶ ϕ′(0) = −2 < 0 だから, 定理 3.5 の仮定を満たす. よって ϕ は C.C. loss. また, Cη (α) = η(max{1 − α, 0})2 + (1 − η)(max{1 + α, 0})2, d dα Cη (α) = −2η max{1 − α, 0} + 2(1 − η) max{1 + α, 0} = 0 ⇐⇒ α = 2η − 1 (∵) ▶ α ≤ −1 とすると, −2η(1 − α) = 0 ⇔ α = 1 となり矛盾 ▶ α ≥ 1 とすると, 2(1 − η)(1 + α) = 0 ⇔ α = −1 となり矛盾 ▶ −1 < α < 1 とすると, −2η(1 − α) + 2(1 − η)(1 + α) = 0 ⇔ α = 2η − 1 38
40. Example : Squared Hinge Loss II よって, H(η) = Cη (2η − 1) = η(max{1 − 2η + 1, 0})2 + (1 − η)(max{1 + 2η − 1, 0})2 = η(4 − 8η + η2) + 4(1 − η)η2 = 4η(1 − η) となるので, H 1 + θ 2 = 4 × 1 + θ 2 × 1 − θ 2 = (1 + θ)(1 − θ) = 1 − θ2 より, ψ(θ) = ϕ(0) − H 1 + θ 2 = 1 − 1 + θ2 = θ2 を得る ([0, 1] 上 strictly monotone increase) 39
41. Example : Non Classification Calibrated Loss I ϕ(m) = max{0, −m} とすると, ϕ は m = 0 で微分不可能． Cη (α) = ηϕ(α) + (1 − η)ϕ(−α) = η max{−α, 0} + (1 − η) max{α, 0} = −ηα if α ≤ 0 (1 − η)α if α ≥ 0 なので, ∀η ∈ [0, 1], Cη (α) ≥ 0 だから, α = 0 で最小値 Cη (0) = 0 をとる. よって, H−(η) = H(η) = 0 となり, ϕ は C.C. loss ではない. また, ψ0 (θ) = ψ(θ) = 0 となる (constant function). 40
42. Example : Non Classification Calibrated Loss II このとき, ψ(Rerr (f) − R∗ err ) = 0 ≤ Rϕ (f) − R∗ ϕ であり, 定理 3.5 の 3 が成り 立たないので, Rϕ (f) → R∗ ϕ =⇒ Rerr (f) → R∗ err は保証されない. 実際, R∗ ϕ = infg Rϕ (g) = infg E[ϕ(Y g(X))] = 0 であり, f(x) = c なる constant function に対して, Rϕ (f) = Pr(Y = +1)ϕ(c) + Pr(Y = −1)ϕ(−c) = Pr(Y = −sign(c))|c| より, Rϕ (f) → R∗ ϕ as c → 0 が成立. 一方, Rerr (f) = Pr(Y = −sign(c)) より, Rerr (f) → Pr(Y = −1) = R∗ err as c 0 となる. 41
43. 判別適合的損失 判別適合性定理: 一般のマージン損失 42
44. Classification Calibration Theorem convex とは限らない margin loss に関する性質 Theorem 4 (3.6 C.C. Theorem) 次の 1, 2 は同値 1. ϕ-margin loss が classification calibrated 2. ∀{fi } : measurable functions, ∀P : distribution on X × {±1} に対して Rϕ (fi ) → R∗ ϕ as i → ∞ =⇒ Rerr (fi ) → R∗ err as i → ∞ Lemma 5 (3.7) ϕ-margin loss から定義される H(η), H−(η), ψ(θ) に対して以下が成立. 1. H(η) と H−(η) は [1 2 , 1] 上 concave かつ (1 2 , 1] 上 continuous 2. ϕ が C.C. loss のとき, ∀θ ∈ (0, 1], ψ(θ) > 0 43
45. Classification Calibration Theorem II (proof of Theorem 3.6) 1 ⇒ 2 ϕ を C.C. loss とする. このとき, ψ(θ) は, ▶ convex (by definition) ▶ [−1, 1] 上偶関数かつ ψ(0) = 0 かつ (0, 1] 上連続 (by Lemma 3.3) ▶ ∀θ ∈ (0, 1], ψ(θ) > 0 (by Lemma 3.7) を満たす. このような ψ は [0, 1] 上狭義単調増加 (∵) 0 ≤ θ1 < θ2 ≤ 1 として, 0 ≤ α1 に対して θ1 = αθ2 とおくと, ψ(θ1 ) ≤ (1 − α)ψ(0) + αψ(θ2 ) = αψ(θ2 ) < ψ(θ2 ) となる. ここで, 最初の不等号は凸性, 真中の等号は ψ(0) = 0 であること, 最 後の不等号は α < 1 であることをそれぞれ用いた. 44
46. Classification Calibration Theorem III (proof of Theorem 3.6) 1 ⇒ 2 つづき よって, 正数列 {θi } ⊂ [0, 1] に対して, ψ(θi ) → 0 =⇒ θi → 0 が成立. 定理 3.4 より, Rϕ (fi ) → R∗ ϕ =⇒ ψ(Rerr (fi ) − R∗ err ) → 0 が成立つから, 上と合わせると, Rϕ (fi ) → R∗ ϕ =⇒ Rerr (fi ) → R∗ err を得る. 45
47. Classification Calibration Theorem III (proof of Theorem 3.6) 1 でない ⇒ 2 でない ϕ が C.C. でないとする. このとき, ∃η = 1 2 , ∃{αi } s.t. αi (2η − 1) ≤ 0, Cη (αi ) → H(η) が成立つ. Remark ∀η = 1 2 で H−(η) > H(η) となるのが C.C. loss の定義であるが, 上の条件は ある η = 1 2 で H−(η) = H(η) となることを意味する. ここで, x0 ∈ X に対して, Pr(X = x0 ) = 1, Pr(Y = +1|X = x0 ) = η なる確率分布を考える. また, 関数列 {fi } は constant function fi (x) = αi , ∀x ∈ X からなるとする. 46
48. Classification Calibration Theorem IV (proof of Theorem 3.6) 1 でない ⇒ 2 でないつづき このとき, η = 1 2 , αi (2η − 1) ≤ 0 より, 以下が成立: lim i→∞ Rerr (fi ) = lim i→∞ E[1sign(fi(X))̸=Y ] > 1 − EX max y∈{±1} Pr(Y = y|X) = R∗ err . (∵) EX maxy∈{±1} Pr(Y = y|X) = max{η, 1 − η} と書ける. 一方, E[1sign(fi(X))̸=Y ] = E[1sign(αi)̸=Y ] だから, η > 1 2 とすると, 右辺 =1 − η, 左辺 =E[1Y =+1 ] = η より, 左辺 > 右辺 となる. η < 1 2 の場合も同様. 他方, Cη (αi ) → H(η) だから, Rϕ (g) = EX [Cη (g(X))] より limi→∞ Rϕ (fi ) = R∗ ϕ が成立. これは, 2 の不成立を意味する. 2 47
49. Example : Ramp Loss I ϕ(m) = min{1, max{1 − m, 0}} は non-convex な margin loss なので, 定理 3.5 は使えない. Cη (α) =              η if α ≤ −1 (1 − η)α + 1 if − 1 < α ≤ 0 −ηα + 1 if 0 < α < 1 1 − η if 1 ≤ α H(η) = η if 0 ≤ η ≤ 1 2 1 − η if 1 2 < η < 1 H−(η) = 1 − η if 0 ≤ η ≤ 1 2 η if 1 2 < η < 1 なので, θ ∈ [0, 1] に対して, ψ0 (θ) = H− 1 + θ 2 − H 1 + θ 2 = 1 + θ 2 − 1 − 1 + θ 2 = θ 48
50. Example : Ramp Loss II ψ0 (θ) > 0 (θ > 0) であるから, 特に η > 1 2 に対して, H−(η) > H(η) となるので, ϕ は C.C. loss である. [−1, 1] 上では, ψ0 (θ) = |θ| であり, 特に ψ(θ) = |θ| であるから, ψ(Rerr (f) − R∗ err ) = Rerr (f) − R∗ err ≤ Rϕ (f) − R∗ ϕ が成立 (hinge loss の評価と同じ) Remark non-convex な margin loss は, 0 で微分不可能でも C.C. となる場合がある. 49
51. References [1] Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. In Advanced lectures on machine learning, pages 169–207. Springer, 2004. [2] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2012. [3] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. [4] 金森敬文. 統計的学習理論 (機械学習プロフェッショナルシリーズ). 講談社, 2015. 50