統計的学習理論

理論っぽいトピックを並べる

（出所：鈴木（2012）統計的学習理論チュートリアル: 基礎から応用まで）

理論の重要性：理論から考案されたアルゴリズムの例¶

SVM (Vapnik, 1998, Cortes and Vapnik, 1995): VC 次元
AdaBoost (Freund and Schapire, 1995): 弱学習器による学習可能性
- 弱学習器の集まりで任意の精度の学習器を作れる（Boosting仮説） → AdaBoost
Lasso (Tibshirani, 1996)
- 正則化は誤差のうちバリアンスを下げる技術（バイアスは増える）
AIC (Akaike, 1974)
Dirichlet process (Ferguson, 1973): 確率論，測度論

経験過程の理論¶

1933 Cantelli Glivenko-Catelli の定理 (一様大数の法則)
1933 Kolmogorov-Smirnov 検定 (収束レート，漸近分布)
1952 Donsker の定理 (一様中心極限定理)
1967 Dudley 積分
1968 VC 次元 (一様収束の必要十分条件)
1996 Talagrand の不等式

一様大数の法則（Glivenko-Catelli の定理）¶

経験分布関数は真の分布関数に収束する。

Dudley, R. M. (1999). Uniform central limit theorems (Vol. 142). Cambridge university press.

バイアス・バリアンス分解¶

汎化誤差の定義（ベイズ誤差を引くかどうか）や、バイアスと呼ぶかモデル誤差と呼ぶかなどの名称の違いでややバリエーションがある

バイアス・バリアンス分解

目的変数 $Y$ が回帰関数 $f(X)$ と誤差 $\varepsilon$ によって分解できる、すなわち $Y=f(X)+\varepsilon$ であるとする。ここで $\mathrm{E}(\varepsilon)=0, \ \mathrm{Var}(\varepsilon) = \sigma^2_{\varepsilon}$ である。

入力点 $X=x_0$ における学習した回帰関数 $\hat{f}(X)$ の二乗誤差の期待値は、 削減不能な誤差 (irreducible error) 、 バイアス（Bias） の二乗、 バリアンス（Variance） に分解できる。

\begin{aligned} \operatorname{Err}\left(x_0\right) &= \mathrm{E} \left[\left(Y-\hat{f}\left(x_0\right)\right)^2 \mid X=x_0\right] \\ & =\sigma_{\varepsilon}^2+\left[\mathrm{E} \hat{f}\left(x_0\right)-f\left(x_0\right)\right]^2+E\left[\hat{f}\left(x_0\right)-\mathrm{E} \hat{f}\left(x_0\right)\right]^2 \\ & =\sigma_{\varepsilon}^2+\operatorname{Bias}^2\left(\hat{f}\left(x_0\right)\right)+\operatorname{Var}\left(\hat{f}\left(x_0\right)\right) \\ & =\text { Irreducible Error }+\operatorname{Bias}^2+\text { Variance } \end{aligned}

(1)

ベイズ誤差（=削減不能な誤差 irreducible error） $\displaystyle \inf_{f: \text {可測関数}}L(f)$ を訓練済みモデルの誤差 $L(\hat{f})$ から引いたものを汎化誤差とする定義もある。こちらだとirreducible errorの項は残らない。

バイアス・バリアンス分解(2)

仮説集合を $\mathcal{F} := \{ f: \mathcal{X} \to \mathbb{R} \}$ 、モデルを $f\in\mathcal{F}$ とおく。訓練データにより訓練済みのモデルを $\hat{f}$ とおく。期待誤差（真の誤差）を $L(f) := E_{(X, Y)}[\ell(Y, f(X))]$ と定義する。

このとき、汎化誤差は次のように分解される

\begin{aligned} \text{汎化誤差} &= L(\hat{f}) - \inf _{f: \text {可測関数 }} L(f)\\ &=\underbrace{ L(\hat{f}) - \inf _{f \in \mathcal{F}} L(f)}_{ 推定誤差 Variance } + \underbrace{ \inf _{f \in \mathcal{F}} L(f) - \inf _{f: \text {可測関数 }} L(f) }_{モデル誤差・近似誤差・ Bias} \end{aligned}

(2)

推定誤差はVariance、モデル誤差は近似誤差やBiasとも呼ばれる。

言葉で説明すると、

訓練済みモデルの期待誤差 $L(\hat{f})$ と、仮説集合の中で最小の誤差 $\inf_{f \in \mathcal{F}} L(f)$ との差が推定誤差（Variance）
仮説集合の中で最小の誤差 $\displaystyle\inf_{f \in \mathcal{F}} L(f)$ と削減不能な誤差 $\displaystyle \inf_{f: \text {可測関数}}L(f)$ の差がモデル誤差（Bias）

推定誤差とモデル誤差にはトレードオフがある。仮説集合が広ければ推定誤差が大きくなる一方でモデル誤差は小さくなり、仮説集合が小さければ推定誤差が小さくなるがモデル誤差が大きくなる。

（出所：統計的学習の基礎）

（出所：4. Learnability and VC Dimension）

理論の重要性：理論から考案されたアルゴリズムの例¶

経験過程の理論¶

一様大数の法則（Glivenko-Catelli の定理）¶

バイアス・バリアンス分解¶

参考¶