9/17 の内容
仮説の予測精度
— 統計的学習理論の基礎 —
• 仮説 h : X → {+1, −1} の予測誤差と学習誤差．
(以下，1[ · ] は定義関数)
• ベイズ誤差，ベイズルール
– 学習誤差 : !e(h) =
• 予測誤差の評価
– 予測誤差 :
– 仮説集合が有限集合のとき
– 仮説集合が無限集合のとき
∗ ラデマッハ複雑度
n
1"
1[ h(Xi) ̸= Yi ]
n i=1
e(h) = Pr(h(X) ̸= Y ) = E[1[h(X) ̸= Y ]]
(予測誤差は (X, Y ) の分布から定まる)
• SVM の統計的一致性
1/61
2/61
例：予測誤差の計算
• e(h) が小さな仮説 h がよい．
– 分布が未知：e(h) の厳密な値は計算不可
p(x, y) = p(x|y)p(y) とする
x ∈ R, y ∈ {1, −1},
⇒ !e(h) を小さくする h を選ぶ
0.4
根拠：各 h に対して !
e(h) −→ e(h), n → ∞, （大数の法則）
p
=⇒ [ e(h) を最小にする h ] ≃ [ e!(h) を最小にする h ]
• !e(h) の最小化は数値的に困難
h(x) = −1
h(x) = 1
e(h) = Pr(h(X) = −1, Y = 1)
+ Pr(h(X) = 1, Y = −1)
0.3
= Pr(h(X) = −1 | Y = 1) Pr(Y = 1)
0.2
– 計算しやすい他の方法が提案されている
−→ 代替損失 (ヒンジ損失など，後述)
+ Pr(h(X) = 1 | Y = −1) Pr(Y = −1)
p(x|y = 1)
p(x|y = −1)
= [■の面積] × Pr(Y = 1)
0.1
+ [■の面積] × Pr(Y = −1)
0.0
-4
3/61
-2
0
2
4
4/61
Bayes rule の導出
Bayes rule, Bayes error
定理 1. データの確率分布：p(x, y) = Pr(Y = y|x)p(x)．
• Bayes rule：誤り確率を最小にする仮説
e(h0) =
inf
h:任意の仮説
e(h)
−→
h0 は Bayes rule
Bayes rule h0(x) =
• e(h0) を Bayes error （ベイズ誤差）という：予測精度の下限
#
+1,
−1,
p(x, +1) ≥ p(x, −1),
p(x, −1) > p(x, +1).
確率の大きなラベルを選ぶほうが，誤り確率が小さい．
• 学習の目標：学習データから Bayes rule h0 を推定．
1.0
p(y = 1|x)
note: p(x, +1) ≥ p(x, −1)
⇐⇒ Pr(Y = +1|x) ≥ Pr(Y = −1|x)
p(y|x)
0.8
p(y = −1|x)
0.6
0.4
0.2
h0(x)
0.0
-4
-2
0
2
4
6
x
5/61
任意の仮説 h : X → {+1, −1} に対して
e(h) = Pr(h(X) ̸= Y )
$
$
=
p(x, −1)dx +
h(x)=1
6/61
h0 の定義から以下の関係が成り立つことに注意：
h0(x) = 1 ⇐⇒ p(x, +1) ≥ p(x, −1)
p(x, +1)dx
(1)
h(x)=−1
h0(x) = −1 ⇐⇒ p(x, +1) < p(x, −1)
ここで積分範囲を Bayes rule h0(x) の値にしたがって分ける：
R++ := {x ∈ X | h(x) = +1, h0(x) = +1}
R+− := {x ∈ X | h(x) = +1, h0(x) = −1}
R−+ := {x ∈ X | h(x) = −1, h0(x) = +1}
R−− := {x ∈ X | h(x) = −1, h0(x) = −1}
7/61
8/61
(1) =
$
+
≥
$
+
=
$
R++
$
$
p(x, +1)dx +
R−+
R++
$
p(x, −1)dx +
p(x, −1)dx +
R−+
R+−
$
p(x, +1)dx
= e(h0)
Bayes rule :
R+−
$
Bayes error :
p(x, +1)dx
$
[証明終了]
h0(x) = arg max p(x, y) = arg max Pr(Y = y|x)
y∈Y
R−−
p(x, −1)dx +
{x:h0 (x)=+1}
確率：p(x, y) = Pr(Y = y|x)p(x), y ∈ Y = {1, 2, . . . , G}
p(x, +1)dx
R−−
$
p(x, −1)dx +
多値判別の Bayes rule
p(x, −1)dx
y∈Y
e(h0) = 1 − EX [ max Pr(Y = y|x) ]
y∈Y
p(x, +1)dx
{x:h0 (x)=−1}
9/61
推定された仮説の精度
10/61
例 1.
目標：推定された仮説の予測誤差を評価．
• データ (X1, Y1), . . . , (Xn, Yn) ∼i .i .d . P ， ベイズルール h0(x)．
2 値判別を考える．多値でも同様．
• 推定方法：
h∈A
2
e!(h1) = ,
8
h1
– 仮説集合：A = {h1, . . . , hM },
– 推定方法：学習誤差の最小化
!
h = arg min e!(h)
A = {h1, h2},
e!(h2) =
3
8
=⇒ !
h = h1
h2
|A| = M < ∞．
[ A のなかで e!(h) を最小にする仮説 ]
• 推定量 !
h の予測誤差 e(!
h) を評価．
note: e(!
h) はデータに依存するので確率変数．
11/61
12/61
仮説集合と Bayes rule
✓
✏
仮説集合 A = {h1, . . . , hM } で Bayes rule h0 を推定
• 事前知識・計算しやすさなどを考慮して A を設定する
• 一般に h0 ̸∈ A
✒
h0
任意の仮説
!
h
✑
• hA := arg min e(h)
h∈A
e(h0) ≤ e(hA) ≤ e(!
h), e!(!
h) ≤ e!(hA)
仮説集合 A
ベイズ誤差と比較：
e(!
h) − e(h0) =
≥
%
%
& %
&
e(!
h) − e(hA) + e(hA) − e(h0)
推定誤差
e(hA) − e(h0)
近似誤差
&
近似誤差
• 推定誤差 (≥ 0)：観測データに依存．確率的に値をとる
!
h := arg minh∈A e!(h)
hA
推定方法の評価尺度
• 近似誤差 (≥ 0)：仮説集合 A と Bayes rule h0 から定まる定数
• 一般に h0 ̸= hA
13/61
✓
仮説集合 A を用いる推定量の誤差評価
推定誤差の評価式
'
Pr e(!
h) < ε + e(hA)
(
14/61
✏
Hoeffding’s inequality
補題 1 (Hoeffding’s inequality).
≥ 1−δ
となるような ε と δ の関係を調べる．
ε > 0, δ ∈ (0, 1) は小さな値．
✒
✑
Pr(· · · ) はデータ (X1, Y1), . . . , (Xn, Yn) に関する確率
• δ が与えられたとき，ε が小さいほど予測精度が高い．
以下のように書き換えられる：
'
(
Pr e(!
h) ≥ ε + e(hA) ≤ δ
Z1, . . . , Zn ∼i .i .d . P, 0 ≤ Zi ≤ 1, µ = E[Zi]
' "
(
n
2
1
=⇒ Pr
Zi − µ ≥ ε ≤ e−2nε .
n i=1
' "
(
n
2
1
Pr
Zi − µ ≤ −ε
≤ e−2nε
n i=1
note: 大数の法則より
n
1"
p
Zi −→ µ．
n i=1
• Hoeffding 不等式から収束スピードが分かる．
• Chebyshev 不等式より良い収束レート：Z の有界性
15/61
16/61
補題 2.
以下の不等式が成り立つ：
'
(
'
(
'
(
ε
ε
!
!
!
Pr e(h) − e(hA) ≥ ε ≤ Pr e(h) − e!(h) ≥
+ Pr e!(hA) − e(hA) ≥
2
2
Proof.
n
• e!(h) − e(h) =
Hoeffding 不等式 で Zi = 1[ h(Xi) ̸= Yi ] とすると
'
(i)
e(!
h) − e(hA) = (e(!
h) − e!(!
h)) + (!
e(!
h) − e!(hA)) + (!
e(hA) − e(hA))
≤ (e(!
h) − e!(!
h)) + (!
e(hA) − e(hA))
したがって e(!
h) − e(hA) ≥ ε が成立するとき，以下のどちらかが
成立する：
(i) e(!
h) − e!(!
h) ≥ ε/2,
(ii) e!(hA) − e(hA) ≥ ε/2
!
17/61
したがって以下が成立：
'
(
!
Pr e(h) − e(hA) ≥ ε
'
(
'
(
!
!
≤ Pr e!(h) − e(h) ≥ ε/2 + Pr e!(hA) − e(hA) ≥ ε/2
≤ (|A| + 1)e−nε
2
1"
1[ h(Xi) ̸= Yi ] − E[ 1[h(X) ̸= Y ] ]
n i=1
(ii)
≤
(
2
Pr e!(hA) − e(hA) ≥ ε/2 ≤ e−2n(ε/2) ,
(
'
(
' )
*
!
!
Pr e(h) − e!(h) ≥ ε/2 ≤ Pr
e(h) − e!(h) ≥ ε/2}
"
h∈A
'
Pr e(h) − e!(h) ≥ ε/2
≤ |A|e−nε
2
/2
h∈A
.
note: 1[ !
h(Xi) ̸= Yi ], i = 1, . . . , n は独立でない
確率 1 − δ 以上の確率で
%
&
e(!
h) < e(h0) + e(hA) − e(h0) +
%
&
≤ e(h0) + e(hA) − e(h0) +
/2
(
近似誤差
+
+
2
|A| + 1
log
n
δ
2 log(|A| + 1)
+
n
推定誤差
18/61
+
2 log(1/δ)
n
• 近似誤差： bA := e(hA) − e(h0)．
+
2 log(|A| + 1)
• 推定誤差： vA,n :=
．
n
= exp{−nε2/2 + log(|A| + 1)}.
ε > 0 に対して
e(!
h) ≥ ε + e(hA)
となる確率は exp{−nε2/2 + log(|A| + 1)} 以下．
δ = exp{−nε2/2 + log(|A| + 1)} として書き直すと・・・
19/61
20/61
複数の仮説集合 A1, A2, . . . , AK について次の包含関係を仮定：
♣ e(!
h) の上界 e(h0) + bA + vA,n が小さいほうがよい．
♣ 適切な仮説集合： min
A1 ⊂ A 2 ⊂ · · · ⊂ A K
k=1,...,K
bAk + vAk ,n を達成する Ak
2.0
以下が成立：
h∈AK
bA 1 ≥ bA 2 ≥ · · · ≥ bA K .
• 仮説集合：大
=⇒ 近似誤差：小，推定誤差：大．
• 和 bA + vA,n を小さくする
仮説集合を用いる．
• 推定誤差は増加：|A1| ≤ |A2| ≤ · · · ≤ |AK | より
0.5
h∈A2
0.0
h∈A1
prediction error
1.0
1.5
• 近似誤差は減少： min e(h) ≥ min e(h) ≥ · · · ≥ min e(h) より
bias+varialce
bias
variance
1e+01
1e+03
|H|
note: 上の考察は e(!
h) の確率的上界に基づいている．
!
期待値 E[e(h)] で考えても同様の結論が得られる
vA1,n ≤ vA2,n ≤ · · · ≤ vAK ,n.
21/61
22/61
仮説集合の複雑度
Rademacher 複雑度
+
参考文献：P. L. Bartlett,
2 log(|A| + 1)
n
−→ A の要素数が大きいほど，推定誤差が大きい．
• 仮説集合 A を用いたときの推定誤差：
1e+05
S. Mendelson, Rademacher and Gaussian
Complexities: Risk Bounds and Structural Results, JMLR, 2002.
Def 1. 関数集合 G ⊂ {g | g : Z → R} と S = {z1, . . . , zn} ⊂ Z に対
! S (G) を
して経験 Rademacher 複雑度 R
• A の要素数が ∞ のときは？
– 仮説集合の「本質的な複雑度」
– 複雑度と推定誤差との関連を調べる．
! S (G) = Eσ
R
,
n
1"
sup
σig(zi)
g∈G n i=1
-
と定義する．ここで σ1, . . . , σn は独立に確率分布 Pr(σi = +1) =
Pr(σi = −1) = 1/2 にしたがう確率変数，Eσ は σ1, . . . , σn に関す
る期待値を意味する．
また
23/61
! S (G)]
Rn(G) = ES [R
をラデマッハ複雑度とよぶ．
24/61
Rademacher 複雑度の解釈
Rademacher 複雑度の性質
以下は Rn(G) でも成立．
• ラベル σi を sign(g(xi)) で予測する．
! S (G1) ≤ R
! S (G2)
1. G1 ⊂ G2 =⇒ R
• ランダムに割り当てられるラベルに，
仮説集合 {sign(g(x))|g ∈ G} がどの程度対応できるか？
! S (cG) = |c|R
! S (G)．
2. c ∈ R に対して R
ここで cG = {cg : g ∈ G}．
! S (G)： G の「複雑度」
• R
! S (G) = R
! S (convG)．
3. G の凸包を convG とすると，R
4. φ : R → R はリプシッツ定数 L のリプシッツ連続関数のとき，
! S (φ ◦ G) ≤ L R
! S (G).
R
ここで φ ◦ G = {φ ◦ g : g ∈ G}．
25/61
Proof. 1. は自明．
2. c = 0 なら自明．c ̸= 0 のとき
26/61
3. 以下の式を σ1, . . . , σn について期待値を取れば，所望の式が得ら
れます．
/
/
.
m
m
"
"
1
1
! S (cA) = Eσ sup
R
σicg(zi) = Eσ sup
σi|c|sign(c)g(zi)
g∈A m i=1
g∈A m i=1
.
/
m
1 "
= |c|Eσ sup
σisign(c)g(zi)
g∈A m i=1
.
/
m
1 "
= |c|Eσ sup
σig(zi)
g∈A m i=1
.
最後の行：σi と σi sign(c) はどちらも確率 1/2 で ±1 の値をとる
ので分布は同じ．
!
sup
n
"
g∈convG i=1
σig(xi) =
=
sup
sup
n
"
g1,...,gk ∈G a!
1 ,...,ak ≥0 i=1
ℓ aℓ =1
sup
sup
k
"
g1,...,gk ∈G a!
1 ,...,ak ≥0 ℓ=1
ℓ aℓ =1
=
sup
max
n
"
g1,...,gk ∈G ℓ=1,...,k i=1
n
"
= sup
g∈G i=1
σi
k
"
aℓgℓ(xi)
n
"
σigℓ(xi)
ℓ=1
aℓ
i=1
σigℓ(xi)
σig(xi).
4．結果は重要．証明：Foundations of Machine Learning, Lemma4.2.
27/61
28/61
例 2 (RKHS モデルの Rademacher 複雑度). カーネル k に対応する
RKHS を H とする．また H の部分集合 HB を
HB = {f ∈ H : ∥f ∥H ≤ B}
とし，有界性 sup k(x, x) ≤ a2 を仮定する．このとき以下が成立：
x∈X
aB
Rn(HB ) ≤ √
n
Proof.
! S (HB ) = Eσ
R
%
n
n
& 1 %
1&
0 "
1"
σif (xi) = Eσ sup f,
σik(·, xi)
n
n
∥f ∥H ≤B
∥f ∥H ≤B
i=1
i=1
sup
n
n
"
2 & B %2 "
22 &1/2
B %2
Eσ 2
σik(·, xi)2H ≤ Eσ 2
σik(·, xi)2H
n
n
i=1
i=1
'"
(1/2
%
&
B
=
k(xi, xj )Eσ σiσj
n i,j
=
B
=
n
'"
n
k(xi, xi)
i=1
(1/2
aB
≤√
n
!
29/61
30/61
補題 3 (マサールの補題). A ⊂ Rn, |A| < ∞ とし，r = maxx∈A ∥x∥2
とおく．このとき
,
3
n
"
r 2 log |A|
1
Eσ
sup
σi xi ≤
n x∈A
n
例 3 (有限仮説集合の Rademacher 複雑度). 仮説集合 H ⊂ {h : Z →
{+1, −1}} を有限集合とする．
A = {(h(x1), . . . , h(xn)) : h ∈ H} にマサールの補題を適用する
√
と，r = n となるので
i=1
が成立．(xi は x ∈ R の第 i 成分)
n
31/61
Rn(H) ≤
3
2n log |H|
=
n
+
2 log |H|
n
32/61
G = {(x, y) 3→ 1[h(x) ̸= y] : h ∈ H} の Rademacher 複雑度：
1[h(x) ̸= y] =
1 − yh(x)
より
2
,
例 4 (決定株 (decision stump)). 深さ 1 の決定木からなる仮説集合．
x = (x1, . . . , xn) 3−→ h(x; s, k, z) = s · sign(xk − z) ∈ {+1, −1},
n
"
パラメータ :
-
1
σi1[h(xi) ̸= yi]
h∈H n i=1
,
n
1
1"
(−yiσi)h(xi)
= Eσ sup
2
h∈H n i=1
+
log |H|
≤
2n
RS (G) = Eσ sup
s = ±1, k ∈ {1, . . . , n}, z ∈ R.
*
4
決定株の仮説集合 : G = h(x; s, k, z) | s = ±1, k = 1, . . . , d, z ∈ R
.
/ +
n
"
1
2 log(2(n + 1)d)
!
RS (G) = Eσ sup
σih(xi; s, k, z) ≤
n
n
s,k,z i=1
最後の不等式はマサールの補題．
(演習問題) 決定株 G に対して A = {(g(x1), . . . , g(xn)) : g ∈ G} と
すると |A| ≤ 2(n + 1)d が成立．
33/61
Rademacher 複雑度による推定誤差の評価
一様大数の法則
✓
34/61
✏
• G ⊂ {g : Z → [a, b]}，
• Z に値をとる確率変数 Z1, . . . , Zn ∼i .i .d . P
1 − δ 以上の確率で以下が成立：
✒
+
5
5
n
"
5
5
1
log(2/δ)
sup 55E[g(Z)] −
g(Zi)55 ≤ 2Rn(G) + (b − a)
.
n
2n
g∈G
i=1
証明：Hoeffding’s を一般化した McDiarmid 不等式を使う．
補足：仮説集合 H ⊂ {h : Z → {+1, −1}}，|H| < ∞ のとき，
1 − δ 以上の確率で以下が成立：
+
+
5
5
2
log
|H|
log(2/δ)
h)5 ≤
max 5e(h) − e(!
+
.
h∈H
n
2n
reference．
✑
• Bartlett, P. L., Mendelson, S., Rademacher and Gaussian Complexities:
Risk Bounds and Structural Results, Journal of Machine Learning
Research, 2002.
• Mohri, M. et al., Foundations of Machine Learning, The MIT Press,
2012. (Chap. 3)
• 金森敬文著, “統計的学習理論”(2015) の付録 A．
35/61
36/61
SVM の予測精度
• 仮定：
1. カーネル関数の有界性： supx∈X k(x, x) ≤ a2．
• i.i.d. データ (x1, y1), . . . , (xn, yn) ∈ X × {+1, −1}
2. f ∗ ∈ H が
• ヒンジ損失を ℓ(z) = max{1 − z, 0} とおく．
RKHS H を用いて判別関数を学習．
SVM :
min
f ∈H
n
1"
n i=1
ℓ(yif (xi)) + λn∥f ∥2H −→ f! ∈ H
inf
f :任意の
(可測な) 関数
E[ℓ(Y f (X))] を達成，すなわち
E[ℓ(Y f ∗(X))] =
(2)
inf
f :任意の
(可測な) 関数
E[ℓ(Y f (X))]
– 正則化パラメータ λn はデータ数に依存してよい．
– 簡単のため，バイアス項 b は付けない．
37/61
代替損失と予測誤差
38/61
代替損失の例：
サポートベクターマシン： L(u) = max{1 − u, 0}
2 値判別 y ∈ {+1, −1}，仮説：h(x) = sign(f (x))
• 0-1 損失 1[u ≤ 0] の代わりに L(u) を使って推定．
ブースティング： L(u) = e−u
ロジスティック回帰： L(u) = log2(1 + e−u)
m
1 "
L(yif (xi)) [ +正則化項 ]
m i=1
5
0-1 マージン損失
ヒンジ損失
ロジスティック損失
マージン損失 φ(m)
4
• L(u) を 0-1 損失の代替損失 (surrogate loss) という．
• 代替損失最小化で Bayes rule を推定できるか？
指数損失
3
2
1
0
-4
-2
0
2
4
m
39/61
40/61
代替損失 L(u) は以下を満たすと仮定．
• L(u) = max{1 − u, 0}
1. 1[u ≤ 0] ≤ L(u), L(u) は R 上凸関数，
⇒
ΨL(s) = s, s ≥ 0
√
ΨL(s) = 1 − 1 − s2, s ≥ 0
6
7
1+s
1−s
• 一般に ΨL(s) = L(0) − inf
L(α) +
L(−α) , s ≥ 0.
α∈R
2
2
• L(u) = e−u
2. u = 0 で微分可能で L′(0) < 0
このとき判別関数 f : X → R に対して以下が成立：
ΨL ( e(sign ◦ f ) − e(h0) ) ≤ E[L(Y f (X))] − inf E[L(Y g(X))]
g
ここで ΨL は以下を満たす：
⇒
• 代替損失の理論：
Bartlett, P. L, et al., Convexity, Classification, and Risk Bounds,
(a) ΨL : R≥0 → R≥0 は L(·) から定まる凸関数
Journal of the American Statistical Association, 2006
(b) ΨL(0) = 0, z > 0 ⇒ ΨL(z) > 0．
(凸性と合わせると，端点で連続な狭義単調増加関数)
=⇒ 代替損失最小化を正当化
41/61
SVM の予測誤差の評価
補題：
√
SVM (2) に対して，データ数が n のとき ∥f!∥H ≤ 1/ λn となる．
証明：
n
n
1"
1"
λn∥f!∥2H ≤
ℓ(yif!(xi)) + λn∥f!∥2H ≤
ℓ(0) + λn∥0∥2H = 1.
n i=1
n i=1
√
よって ∥f!∥H ≤ 1/ λn.
42/61
8
3 9
Fn = f ∈ H : ∥f ∥H ≤ 1/ λn ,
*
4
An = (x, y) 3→ ℓ(yf (x)) : f ∈ Fn
ヒンジ損失 ℓ(z) = max{1 − z, 0} のリプシッツ定数は 1
なので以下が成立：
Rn(An) ≤ 1 · Rn(Fn) ≤ √
a
nλn
[ σi と yiσi が同じ分布にしたがうことも使う ]
43/61
44/61
ラデマッハ複雑度による推定誤差の評価式と以下の不等式より，
a
max ℓ(yf (x)) ≤ √ + 1
f ∈Fn
λn
x,y
(∥f ∥∞ と ∥f ∥H の関係)
Proof. f ∈ Fn に対して
sup |yf (x)| = sup |f (x)| = sup |⟨f, k(x, ·)⟩| ≤ ∥f ∥H sup
x,y
x
x
x
a
≤√ .
λn
3
k(x, x)
確率 1 − δ 以上で以下が成立：
5
5
n
"
5
5
1
sup 55E[ℓ(Y f (X))] −
ℓ(Yif (Xi))55
n i=1
f ∈Fn
+
log(2/δ)
≤ 2Rn(An) + max ℓ(yf (x)) ·
f ∈Fn
2n
x,y
'
(+
2a
a
log(2/δ)
≤√
+ √ +1
n
nλn
λn
√
√
ℓ(z) = max{1 − z, 0} より |z| ≤ a/ λn なら ℓ(z) ≤ a/ λn + 1．!
45/61
√
∥f ∗∥H ≤ 1/ λn となる n に対して，1 − δ 以上の確率で次が成立：
!
− E[ℓ(Y f ∗(x))] + E[ℓ(Y
f!(x))] + λn∥f!∥2H
!
≤ E[ℓ(Y f ∗(x))] + E[ℓ(Y f!(x))] − E[ℓ(Y
f!(x))]
!
− E[ℓ(Y f ∗(x))] + E[ℓ(Y
f ∗(x))] + λn∥f ∗∥2H
5
5
5
5
!
≤ E[ℓ(Y f ∗(X))] + 2 sup 5E[ℓ(Y f (X))] − E[ℓ(Y
f (X))]5
+
λn → 0, nλn → ∞ とすると，
p
E[ℓ(Y f!(x))] −→ E[ℓ(Y f ∗(X))]
!
E[ℓ(Y f!(x))] ≤ E[ℓ(Y f ∗(x))] + E[ℓ(Y f!(x))] − E[ℓ(Y
f!(x))]
λn∥f ∗∥2H
46/61
f ∈Fn
となることが分かる．
note: 上界のオーダを最小にする λn は λn = O(n−1/3)．
このとき
E[ℓ(Y f!(x))] = E[ℓ(Y f ∗(X))] + Op(n−1/3).
代替損失の理論より以下が成立：
p
e(sign ◦ f!) −→ Bayes error
47/61
(n → ∞)
48/61
補題 4 (ヘフディングの補題 (Hoeffding’s lemma)). 確率変数 X が E[X] = 0, a ≤
X ≤ b を満たすとき，任意の t > 0 に対して
E[etX ] ≤ et
2
(a−b)2 /8
.
Proof. 区間 [a, b] 上で指数関数 etx を１次式で上からバウンドすると，
付録：確率不等式
etx ≤
x − a tb b − x ta
e +
e
b−a
b−a
となります．したがって a ≤ X ≤ b と E[X] = 0 を満たす確率変数に対して
E[etX ] ≤
−a tb
b ta
e +
e
b−a
b−a
49/61
が成り立ちます．ここで p =
となります．テイラーの定理より，0 ≤ v ≤ u となる v が存在して
−a
(0 ≤ p ≤ 1), u = t(b − a) とおくと
b−a
φ(u) = φ(0) + uφ′(0) +
b ta
−a tb
e +
e = pe(1−p)u + (1 − p)e−pu
b−a
b−a
となるので (3) が成り立ちます．
となります．以下で，0 ≤ p ≤ 1 と任意の u ≥ 0 に対して
pe(1−p)u + (1 − p)e−pu ≤ eu
2
/8
50/61
u2 ′′
u2
φ (v) ≤
2
8
!
(3)
となることを示します．φ(u) = log[pe(1−p)u + (1 − p)e−pu] とおくと φ(0) =
0, φ′(0) = 0，
1−p
1 − p + peu
1−p
=
1 − p + peu
φ′′(u) =
peu
1 − p + peu
'
(
1−p
1
· 1−
≤
1 − p + peu
4
·
51/61
52/61
補題 5 (ヘフディングの不等式). 確率変数 X1, . . . , Xn は独立に同一の分布にした
:n
がい，Xi は確率 1 で有界区間 [ai, bi] に値をとるとします．S = i=1 Xi とす
ると，任意の ε > 0 に対して
6
7
2ε2
Pr(S − E[S] ≥ ε) ≤ exp − :n
,
2
i=1 (bi − ai )
6
7
2ε2
Pr(S − E[S] ≤ −ε) ≤ exp − :n
2
i=1 (bi − ai )
0 を導入して上界を以下のように導出します．
Pr(S − E[S] ≥ ε) = Pr(et(S−E[S]) ≥ etε)
(マルコフの不等式)
≤ e−tεE[et(S−E[S])]
= e−tε
≤e
が成り立ちます．
n
;
E[et(Xi−E[Xi])]
i=1
!n
−tε t2
e
2
i=1 (bi −ai ) /8
.
(ヘフディングの補題)
上の不等式は任意の
t > 0 で成り立つので，上界が最小になるように t =
:n
4ε/ i=1(bi − ai)2 > 0 とおくと
n
"
*
4
Pr(S − E[S] ≥ ε) ≤ exp − 2ε2/
(bi − ai)2
i=1
が得られます．2 番目の不等式も同様に得られます．
!
Proof. マルコフの不等式とヘフディングの補題を使います．正値パラメータ t >
53/61
54/61
補題 6 (マサートの補題). A ⊂ Rm を有限集合とし，∥x∥ を x ∈ Rm の 2-ノルム
(ユークリッドノルム) として r = maxx∈A ∥x∥ とおきます．また σ1, . . . , σm を独
立に {+1, −1} 上の一様分布にしたがう確率変数とします．このとき
が成り立ちます．最後の等式は σ1, . . . , σm の独立性を用いました．ヘフディング
の補題 (補題 4) を用いると
Eσ
,
-
m
"
r
1
sup
σi xi ≤
m x∈A i=1
3
2 log |A|
m
より (4) は |A|et
数を t で割ると
が成立します．ここで xi は x ∈ Rm の第 i 成分を表します．
.
exp Eσ t sup
m
"
x∈A i=1
σi xi
/7
.
6
≤ Eσ exp t sup
≤
=
"
x∈A
.
m
"
x∈A i=1
6 "
m
Eσ exp t
m
";
x∈A i=1
i=1
σi xi
σi xi
7/
で上から抑えられます．このようにして得られる上界の対
となり，
3
2 log |A|
t=
r
7/
%
*
4&
Eσi exp tσixi
r /2
.
/
m
"
tr2 log |A|
Eσ sup
σi xi ≤
+
2
t
x∈A i=1
Proof. 任意の t > 0 に対して，指数関数の凸性とイェンセンの不等式より，
6
2 2
%
*
4&
2
2
Eσi exp tσixi ≤ et (2xi) /8
(4)
55/61
56/61
を代入して
/
.
m
"
3
σixi ≤ r 2 log |A|
Eσ sup
x∈A i=1
が得られます．両辺を m で割って所望の不等式が得られます．
!
次にマクダミッドの不等式を導出します．そのために，まずアズマの不等式を導
出します．
補題 7 (アズマの不等式 (Azuma’s inequality)). 確率変数 Xi, Zi, Vi, i = 1, . . . , n に
対して，Vi は X1, . . . , Xi の関数として表すことができ，E[Vi|X1, . . . , Xi−1] = 0
が成り立つとします．また Zi は X1, . . . , Xi−1 の関数として表すことができ，定
数 c1, . . . , cn が存在して Zi ≤ Vi ≤ Zi + ci が成り立つとします．このとき任意の
ε > 0 に対して
Pr
Pr
が成り立ちます．
57/61
>
?
Pr Sn ≥ ε ≤ e−tεE[etSn ]
= e−2ε
i=1
n
"
i=1
Vi ≥ ε
Vi ≤ −ε
=
=
6
2ε2
≤ exp − :n
2
i=1 ci
6
2ε2
≤ exp − :n
2
i=1 ci
7
,
7
:k
Proof. 部分和 i=1 Vi を Sk とおきます．ヘフディングの不等式の証明と同様に，
:n
正値パラメータ t を導入して上界を求めます．以下で t = 4ε/ i=1 c2i > 0 とお
58/61
|f (x1, . . . , xi−1, xi, xi+1, . . . , xn) − f (x1, . . . , xi−1, x′i, xi+1, . . . , xn)| ≤ ci,
= e−tεEX1,...,Xn−1 [etSn−1 EXn [etVn |X1, . . . , Xn−1]]
≤ e−tεet
<
n
"
補題 8 (マクダミッドの不等式). 集合 X に値をとる独立な確率変数を X1, . . . , Xn
とします．また関数 f : X n → R に対して定数 c1, . . . , cn が存在して
くと
≤ e−tεEX1,...,Xn−1 [etSn−1 ]et
<
2 2
cn /8
i = 1, . . . , n
(ヘフディングの補題)
2 !n
2
i=1 ci /8
が任意の x1, . . . , xn, x′i ∈ X に対して成り立つとします．このとき次式が成り立
ちます．
2 !n
/ i=1 c2i
となります．同様にして 2 番目の不等式が得られます．
!
6
>
?
2ε2
Pr f (X1, . . . , Xn) − E[f (X1, . . . , Xn)] ≥ ε ≤ exp − :n
7
2
i=1 ci
7
2
6
>
?
2ε
Pr f (X1, . . . , Xn) − E[f (X1, . . . , Xn)] ≤ −ε ≤ exp − :n
2
i=1 ci
,
.
Proof. f (X1, . . . , Xn) を f (S) と表します．また V1, . . . , Vn を
Vk = E[f (S)|X1, . . . , Xk ] − E[f (S)|X1, . . . , Xk−1]
59/61
60/61
と定義します．ここで V1 は E[f (S)|X1] − E[f (S)] を表します．以下で，この Vk
が補題 7 の仮定を満たすことを示します．定義から Vk は X1, . . . , Xk の関数して
表せます．また条件付き期待値の性質から E[Vk |X1, . . . , Xk−1] = 0 を満たしま
す．さらに関数 f に対する仮定より
sup E[f (S)|X1, . . . , Xk−1, x] − inf′ E[f (S)|X1, . . . , Xk−1, x′]
x
x
= sup {E[f (S)|X1, . . . , Xk−1, x] − E[f (S)|X1, . . . , Xk−1, x′]} ≤ ci
x,x′
となります．したがって
Zk = inf E[f (S)|X1, . . . , Xk−1, x] − E[f (S)|X1, . . . , Xk−1]
x
とすれば:
Xk , Vk , Zk , k = 1, . . . , n が補題 7 の仮定を満たすことが分かります．以
n
上より， i=1 Vi = f (S) − E[f (S)] に対するアズマの不等式から定理の主張が得
られます．
!
61/61
© Copyright 2024 ExpyDoc
