# 統計的学習理論
読書会のためのノート

## 1章

### 定義1.2 統計的一致性
テキストp.14

任意の分布$D$と任意の$\epsilon>0$に対して

\begin{eqnarray}
\lim_{n\rightarrow\infty}{\rm Pr}_{S\sim D^n}
\left(
R(h_S)\leq R^* +\epsilon
\right) = 0
\end{eqnarray}

が成り立つとき, 学習アルゴリズム$S\rightarrow h_S$は統計的一致性を持つという.
* $R^*=\inf_{h}R(h)$はベイズ誤差

## 2章 仮説集合の複雑度

### 定義2.4 経験ラデマッハ複雑度
テキストp.25

\begin{eqnarray}
\hat{\mathfrak{R}}_S({\cal G}) =
{\mathbb E}_{\sigma}\left[\sup_{g\in{\cal G}}\frac{1}{n}\sum_{i=1}^n \sigma_i g(x_i)\right]
\end{eqnarray}
* $S=\{x_1,\cdots,x_n\}\in{\cal X}$
* $\sigma_i$: +1と-1を等確率でとる独立な確率変数

### 定義2.5 ラデマッハ複雑度
テキストp.26

\begin{eqnarray}
\mathfrak{R}_n({\cal G}) = {\mathbb E}_{S\sim D}\left[{\hat{\mathfrak R}}({\cal G})\right]
\end{eqnarray}
* $D$: 入力空間${\cal X}$上の確率分布

### 定理2.7 一様大数の法則
テキストp.32

${\cal G}\subset\{f:{\cal Z}\rightarrow [a,b]\}$, $Z\sim D$, $Z_i\sim D$ $(i=1,\cdots,n)$を確率変数とする. このとき任意の$\delta\in(0,1)$に対して分布$D^n$のもとで$1-\delta$以上の確率で次式が成り立つ：

\begin{eqnarray}
\sup_{g\in{\cal G}}\left\{
{\mathbb E}[g(Z)] - \frac{1}{n}\sum_{i=1}^n g(Z_i)
\right\}
\leq
2{\mathfrak{R}}_n({\cal G})+(b-a)\sqrt{\frac{\log(1/\delta)}{2n}}
\end{eqnarray}

同等の不等式が $\sup_{g\in{\cal G}}\frac{1}{n}\{{\sum_{i=1}^n g(Z_i)} - {\mathbb E}[g(Z)]\}$ についても成立. したがって次式が成立：

\begin{eqnarray}
\sup_{g\in{\cal G}}\left|
{\mathbb E}[g(Z)] - \frac{1}{n}\sum_{i=1}^n g(Z_i)
\right|
\leq
2{\mathfrak{R}}_n({\cal G})+(b-a)\sqrt{\frac{\log(2/\delta)}{2n}}
\end{eqnarray}
注：右辺の$\log$の中の係数2は確率の定義に立ち戻って考えると分かる.

## 4章 カーネル法の基礎

### 定理4.11
p.71

${\cal X}$上のRKHS $({\cal H},\langle\cdot,\cdot\rangle)$, 対応する再生核$k:{\cal X}^2\rightarrow{\mathbb R}$, ${\cal G}\subset\{f\in{\cal H}|\|f\|_{\cal H}\leq a\}$（$a$は適当な正数）を満たす関数集合${\cal G}$について, 入力点集合$S=\{x_1,\cdots,x_m\}\subset{\cal X}$に対する経験ラデマッハ複雑度について次式が成り立つ：
\begin{eqnarray}
\hat{\mathfrak R}_{S}({\cal G})
\leq
\frac{a}{m}\left(\sum_{i=1}^{m}k(x_i,x_i)\right)^{1/2}.
\end{eqnarray}

## 5章 サポートベクトルマシン

### 5.3 C-サポートベクトルマシン

### 5.3.4 予測判別誤差の上界
* 誤差解析のためランプ損失を用いる：
\begin{eqnarray}
\phi_{\rm ramp}(m) = \min\{\max\{1-m,0\},1\} = \min\{\phi_{\rm hinge}(m),1\}
\end{eqnarray}

* 式(5.6)
\begin{eqnarray}
{\bf 1}[m\leq 0] \leq \phi_{\rm ramp}(m) \leq \phi_{\rm hinge}(m)
\end{eqnarray}

* 式(5.7), この節で解析する学習法
* 正則化項の代わりにノルムに制約条件を課している
\begin{eqnarray}
\min_{f\in{\cal H},b\in{\mathbb R}} \frac{1}{n}\sum_{i=1}^{n} \phi_{\rm hinge}(y_i(f(x_i)+b)),
\text{ subject to }\|f\|_{\cal H}\leq a
\end{eqnarray}

### 補題5.3
p.89

再生核ヒルベルト空間${\cal H}$に対応するカーネル関数が
\begin{eqnarray}
\sup_{x\in{\cal X}}k(x,x)\leq\Lambda^2
\end{eqnarray}
を満たすとき,
\begin{eqnarray}
|\hat{b}| \leq a\Lambda + 1
\end{eqnarray}
を満たす(5.7)の最適解 $\hat{f}(x)+\hat{b}$ が存在する.

証明 表現定理より$f(x_i)=\sum_{i=1}^{n}\alpha_{i}k(x_i,x)$の範囲のみ考えれば十分. 式(5.7)の制約条件より$\alpha K\alpha\leq a^2$. 次式が成り立つ：

\begin{eqnarray}
|f(x_i)| = |\langle f,k(x_i,\cdot)\rangle_{\cal H}|
\leq \|f\|_{\cal H}\|k(x_i,\cdot)\|_{\cal H} \leq a\Lambda
\end{eqnarray}
最初の等式は再生性, 二つ目の不等式はCS不等式, 最後の不等式は(5.7)の制約条件と補題の仮定より来る.

制約を満たす$f\in{\cal H}$に対して$\zeta$を次式で定義：
\begin{eqnarray}
\zeta(b) &=& \sum_{i=1}^{n}\phi_{\rm hinge}(y_i(f(x_i)+b)) \\
&=& \sum_{i:y_i=+1}\phi_{\rm hinge}(f(x_i)+b) +
\sum_{i:y_i=-1}\phi_{\rm hinge}(-f(x_i)-b)
\end{eqnarray}
第1項のヒンジ損失は各$i$について$b>a\Lambda+1$の範囲で非減少（常に0）. 同様に第2項のヒンジ損失は各$i$について$b<-a\Lambda-1$の範囲で非増加（常に0）. よって$\hat{b}$の範囲に関して題意が成立.

### 定理5.4
p.90

補題5.3の条件を仮定. (5.7)の最適解を$\hat{h}(x)={\rm sign}(\hat{f}(x)+\hat{b})$とする. データ分布を$D^n$, 学習データを$\{(x_i,y_i)|i=1,\cdots,n\}$とする. このとき$1-\delta$以上の確率で

\begin{eqnarray}
R_{\rm err}(\hat{h}) \leq \frac{1}{n}\sum_{i=1}^n \phi_{\rm hinge}(y_i(\hat{f}(x)+\hat{b})) +
\frac{2(3a\Lambda +2)}{\sqrt{n}} + \sqrt{\frac{\log(1/\delta)}{2n}}
\end{eqnarray}

が成り立つ. これより経験ヒンジ損失が同じなら$a$の値が小さい方が予測判別誤差が小さくなる傾向がある.

証明　集合$\phi_{\rm ramp}\circ{\cal G}$を次のように定義する：

\begin{eqnarray}
\phi_{\rm ramp}\circ{\cal G}
& = &
\{(x,y)\mapsto\phi_{\rm ramp}(y(f(x)+b))|(f,b)\in{\cal G}\}
\end{eqnarray}

ランプ損失のリプシッツ定数は1なので定理2.6（p.26）より経験ラデマッハ複雑度について

\begin{eqnarray}
\hat{\mathfrak R}_{S}(\phi_{\rm ramp}\circ{\cal G})
\leq
\hat{\mathfrak R}_{S}
\leq
\frac{3a\Lambda+2}{\sqrt{n}}
\end{eqnarray}

となる. 2番目の不等式は定理5.5. ラデマッハ複雑度${\mathfrak R}(\phi_{\rm ramp}\circ{\cal G})$についても同じ上界が得られる. ランプ関数の定義より$\phi_{\rm ramp}(y(f(x)+b))\in[0,1]$が成り立つので, 一様大数の法則（定理2.7）より学習データの分布について$1-\delta$以上の確率で

\begin{eqnarray}
\sup_{(f,b)\in{\cal G}}\left\{
{\mathbb E}[\phi_{\rm ramp}(Y(f(X)+b))] - \sum_{i=1}^{n}\phi_{\rm ramp}(y_i(f(x_i)+b))
\right\}
\leq
\frac{2(3a\Lambda+2)}{\sqrt{n}} + \sqrt{\frac{\log(1/\delta)}{2n}}
\end{eqnarray}

が成り立つ. したがって, $h(x)=f(x)+b$に対して$1-\delta$以上の確率で

\begin{eqnarray}
R_{\rm err}(h) & \leq & {\mathbb E}[\phi_{\rm ramp}(Y(f(X)+b))] \\
& \leq &
\sum_{i=1}^{n}\phi_{\rm ramp}(y_i(f(x_i)+b)) + \frac{2(3a\Lambda+2)}{\sqrt{n}} + \sqrt{\frac{\log(1/\delta)}{2n}}\\
& \leq &
\sum_{i=1}^{n}\phi_{\rm hinge}(y_i(f(x_i)+b)) + \frac{2(3a\Lambda+2)}{\sqrt{n}} + \sqrt{\frac{\log(1/\delta)}{2n}}
\end{eqnarray}

が成り立つ（最初の不等式は式(5.6)より）.

### 定理5.5
p.91

集合${\cal G}=\{(f,b)\in{\cal H}\times{\mathbb R}:\|f\|_{\cal H}\leq a,|b|\leq a\Lambda+1\}$の経験ラデマッハ複雑度について次式が成り立つ：

\begin{eqnarray}
\hat{\mathfrak R}_{S}({\cal G}) \leq \frac{3a\Lambda + 2}{\sqrt{n}}
\end{eqnarray}

証明　次式が成り立つ.

\begin{eqnarray}
\hat{\mathfrak R}_{S}({\cal G}) & = &
\frac{1}{n}{\mathbb E}_{\sigma}
\left[
\sup_{(f,b)\in{\cal G}} \sum_{i=1}^{n}\sigma_i(f(x_i)+b)
\right] \\
& \leq &
\frac{1}{n}{\mathbb E}_{\sigma}
\left[
\sup_{\|f\|_{\cal H}\leq a} \sum_{i=1}^{n}\sigma_{i}f(x_i)
\right] +
\frac{1}{n}{\mathbb E}_{\sigma}
\left[
\sup_{|b|\leq a\Lambda+1} \sum_{i=1}^{n}\sigma_{i}b
\right]
\end{eqnarray}

定理4.11と系4.12より第1項は$a\Lambda/\sqrt{n}$で抑えられる. 第2項の上界は$\sum_i\sigma_i$が正なら$b=a\Lambda+1$, 負なら$b=-a\Lambda-1$で達成される. したがって$A=\{\pm(a\Lambda+1){\bf 1}\}\in{\mathbb R}^n$と置くとマサールの補題（補題A.3）より

\begin{eqnarray}
\frac{1}{n}{\mathbb E}_{\sigma}
\left[ \sup_{|b|\leq a\Lambda+1} \sum_{i=1}^{n}\sigma_{i}b \right]
& = &
\frac{1}{n}{\mathbb E}_{\sigma}
\left[ \sup_{z\in A} \sum_{i=1}^{n}\sigma_{i}z_i \right] \\
& \leq &
\frac{\sqrt{2\log 2}(a\Lambda+1)}{\sqrt{n}} \leq \frac{2(a\Lambda+1)}{\sqrt{n}}
\end{eqnarray}

が成り立つ. 第1項と合わせて定理が成り立つ. 入力分布に関して期待値をとることでラデマッハ複雑度についても同じ上界が成り立つ（はず）.

### 5.3.5 統計的一致性
* 式(5.8)　$C$-サポートベクトルマシンを次のように書き換える：

\begin{eqnarray}
\min_{f,b}\frac{1}{n}\sum_{i=1}^{n}\phi_{\rm hinge}(y_i(f(x_i)+b))+\lambda_{n}\|f\|^{2}_{\cal H} \\
\text{subject to }f\in{\cal H}, b\in{\mathbb R}
\end{eqnarray}

* (5.8)は(5.7)と違いノルムの制約がない

### 定理5.6
p.93

${\cal H}$を普遍カーネル$k$に対応するRKHSとし, $\sup_{x\in{\cal X}}k(x,x)\leq\Lambda^2$を仮定. $\lambda_n>0$を$\lambda_n\rightarrow 0$, $n\lambda_{n}\rightarrow\infty$となるように選び, (5.8)から得られる判別関数を$\hat{f}(x)+\hat{b}$とする. このとき$|\hat{b}|\leq\Lambda/\sqrt{\lambda_n}+1$となる解が存在し, 予測判別誤差$R_{\rm err}(\hat{f}+b)$は$n\rightarrow\infty$でベイズ誤差$R^*_{\rm err}$に確率収束する.

### 補題5.7
p.93

$\sup_{x\in{\cal X}}k(x,x)\leq\Lambda^2$を仮定. このとき

\begin{eqnarray}
{\cal G}_{n} = \{
(f,b)\in{\cal H}\times{\mathbb R}\mid \|f\|^2_{\cal H}\leq 1/\lambda_n,
|b|\leq\Lambda/\sqrt{\lambda_n}+1
\}
\end{eqnarray}

に含まれる(5.8)の最適解が存在する.

証明　グラム行列を$K_ij$とする. 表現定理より$f(x)=\sum_{i=1}^{n}\alpha_{i}k(x_i,x)$と表すことができる. $B\subset{\mathbb R}^{n+1}$を

\begin{eqnarray}
B=\{
(\alpha,b)\in({\rm ker}K^{\perp})\times{\mathbb R}
\mid
\alpha^{T}K\alpha\leq 1/\lambda_n, |b|\leq\Lambda/\sqrt{\lambda_n}+1
\}
\end{eqnarray}

と定義. 集合$B$上の最適値よりも損失関数の値が小さくなる $(\tilde{\alpha},\tilde{b})\notin B$ が存在すると仮定する. $\tilde{\alpha}\notin({\rm ker}K^{\perp})$ として一般性は失わない. $(\alpha=0, b=0)\in B$ なので次式が成り立つ（1行目右辺はヒンジ損失の非負性より, 2行目は$(\tilde{\alpha},\tilde{b})$の最適性の仮定より）.

\begin{eqnarray}
\lambda_n\tilde{\alpha}^{T}K\tilde{\alpha}
& \leq &
\frac{1}{n}\sum_{i=1}^{n}\phi_{\rm hinge}(y_i(\sum_{j}K_{ij}\tilde{\alpha}_{j}+\tilde{b})) +
\lambda_n\tilde{\alpha}^{T}K\tilde{\alpha} \\
& < &
\frac{1}{n}\sum_{n=1}^{n}\phi_{\rm hinge}(0) = 1
\end{eqnarray}

よって$\tilde{\alpha}^{T}K\tilde{\alpha}\leq 1/\lambda_{n}$. 一方, 補題5.3と同様にして$|\tilde{b}|\leq\Lambda/\sqrt{\lambda_n}+1$を満たすことが分かる.