統計的学習理論は、有限個の標本から未知の確率分布に基づく予測関数を構成し、その汎化性能を理論的に評価する枠組みである。経験誤差最小化と汎化誤差の関係を中心に、仮説空間の複雑さと過学習のトレードオフを定量化する点に本質がある。
入力空間 $\mathcal{X}$、出力空間 $\mathcal{Y}$ を考え、確率分布 $P$ に従う独立同分布な標本が与えられているとする：
\[(\boldsymbol{x}_1, y_1), \dots, (\boldsymbol{x}_n, y_n) \sim P\]仮説空間（関数クラス）$\mathcal{H}$ の各要素 $f : \mathcal{X} \to \mathcal{Y}$ に対し、損失関数 $\ell(f(\boldsymbol{x}), y)$ を定義する。
関数 $f \in \mathcal{H}$ の期待リスク（汎化誤差）は
\[R(f) = \mathbb{E}_{(\boldsymbol{x}, y) \sim P}\bigl[\ell(f(\boldsymbol{x}), y)\bigr]\]標本に基づく経験リスクは
\[R_n(f) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(\boldsymbol{x}_i), y_i)\]で与えられる。
経験リスク最小化（ERM）は
\[\hat{f} = \arg\min_{f \in \mathcal{H}} R_n(f)\]により推定関数を定める方法である。
最適関数を
\[f^* = \arg\min_{f} R(f)\]とすると、過剰リスクは
\[R(\hat{f}) - R(f^*)\]であり、次のように分解される：
\[R(\hat{f}) - R(f^*)=\underbrace{\inf_{f \in \mathcal{H}} R(f) - R(f^*)}_{\text{近似誤差}}+\underbrace{R(\hat{f}) - \inf_{f \in \mathcal{H}} R(f)}_{\text{推定誤差}}\]統計的学習理論の中心問題は
\[\sup_{f \in \mathcal{H}} \bigl| R(f) - R_n(f) \bigr|\]を評価することである。
仮説空間（関数クラス）の表現能力、すなわちデータに対する分類の柔軟性を測る指標であるVC次元 $\mathrm{VC}(\mathcal{H})$ を用いると、確率 $1-\delta$ で
\[R(f)\leq R_n(f)+C \sqrt{\frac{\mathrm{VC}(\mathcal{H}) \log n + \log(1/\delta)}{n}}\]が成立する。
ラデマッハ複雑度は
\[\mathfrak{R}_n(\mathcal{H})=\mathbb{E}_{\boldsymbol{\sigma}}\left[\sup_{f \in \mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\sigma_i f(\boldsymbol{x}_i)\right]\]で定義され、汎化誤差の評価に用いられる。
正則化を導入すると
\[\hat{f}=\arg\min_{f \in \mathcal{H}}\left\{R_n(f) + \lambda \Omega(f)\right\}\]となる。
経験過程
\[\sqrt{n}\bigl(R_n(f) - R(f)\bigr)\]の収束解析により、一様収束が導かれる。
統計的学習理論は、期待リスクと経験リスクの差を制御することで汎化性能を保証する理論体系である。仮説空間の複雑さを定量化し、正則化と組み合わせることで過学習を抑制する枠組みを与える。
Mathematics is the language with which God has written the universe.