はじめに

機械学習ではよく経験誤差を小さくするような関数(パラメータ)を学習することを目標にしますが，実際のところなぜ経験誤差を小さくしたいのかわかっていなかったり，そもそも経験誤差の定義を知らない人も多いかと思われます．実際，僕もその一人でした．

本記事はそんな僕が経験誤差や汎化誤差について理解するためのもので，経験誤差を小さくする気持ちについて書いています．誤り等ありましたら早急に連絡をよろしくお願いいたします．

注意

この記事は，Foundations of Machine Learning（聖書）を参考に書いています（ほとんど中身は同じです）． pdf版が無料で公開されているのでぜひそちらを参照してください．

Foundations of Machine Learning, second edition (Adaptive Computation and Machine Learning series)

作者:Mohri, Mehryar,Rostamizadeh, Afshin,Talwalkar, Ameet
発売日: 2018/12/25
メディア: ハードカバー

記号の定義

本題に入る前に，本記事で扱う記法をここで導入しておきます．

$\mathcal{X}$ ... データの空間．
$\mathcal{X}$ はユークリッド空間の部分集合である必要はありません．例えば画像データの場合は $\mathcal{X}$ が $\mathbb{R}^2$ や $\{0, 1, \ldots, 255\}$ であったり，テキストデータの場合は文字列全体の集合だったりします．
$\mathcal{Y}$ ... ラベルの空間．
例えば，本記事で挙げる分類問題においては， $\mathcal{Y} = \{0, 1, 2\}$ だったり， $\mathcal{Y} = \{\text{犬}, \text{猫}\}$ だったりとカテゴリを表すものだったりします．
$\mathcal{D}$ ... データとラベルの組の背後にある分布（ $\mathcal{X} \times \mathcal{Y}$ 上の分布）．
訓練データ，テストデータは独立に分布 $\mathcal{D}$ に従って得られると仮定します．
$\mathcal{H}$ ... 仮説集合， $\mathcal{H} \subseteq \left\{ h : \mathcal{X} \to \mathcal{Y} \right\}$ ．
言葉で表すと，データからラベルを予測する関数全体の集合の部分集合，と言えば伝わるでしょうか．

一般には，分布 $\mathcal D$ に従って得られた $(\boldsymbol{x}, y)$ を「データ」や「例」と呼ぶので，本記事でも特に断りがない限りはそう呼ぶことにします．また，「サンプル」という言葉は分布 $\mathcal D$ に独立に従って得られた訓練例の列を指すことにも注意してください（訓練例の「集合」ではなく訓練例の「列」と表現したのはランダムにとってきた結果同じものが得られた場合，「集合」だと重複を一つと見做すからです）．

機械学習では，「訓練データに対してのみ誤差（訓練誤差）を小さくすること」を目標にするのではなく，「未知のデータが来た場合にも間違える確率（汎化誤差）を小さくすること」を目標にします．

汎化誤差とは

仮説 $h \in \mathcal{H}$ とデータの背後にある分布 $\mathcal{D}$ が与えられたとき， $h$ の汎化誤差を次式で定義します．

$\displaystyle{ R(h) = \Pr\limits_{(\boldsymbol{x}, y) \sim \mathcal{D}} \left[ h(\boldsymbol{x}) \neq y \right] = \mathbb{E}_{(\boldsymbol{x}, y) \sim \mathcal{D}} \left[ 1_{h(\boldsymbol{x}) \neq y } \right] }$

ただし，

$\displaystyle{ 1_{\omega} = \begin{cases} 1 & \omega \text{ is True} \\ 0 & \omega \text{ is False} \end{cases} }$

としました．汎化誤差を言葉で説明すると，「分布 $\mathcal D$ に従ってデータを取ってきたときに間違える確率」となります．

機械学習では，多くの場合この汎化誤差を最小にする仮説を求めることを目標にします．しかし，現実にはデータの背後にある分布など得られるはずもありません．そこで代わりに 経験誤差 というものを考えます．

経験誤差とは

仮説 $h \in \mathcal{H}$ と訓練例の列 $S = ( x_1, \ldots, x_m ) \subseteq \mathcal{X} \times \mathcal{Y}$ が与えられたとき， $h$ の経験誤差を次式で定義します．

$\displaystyle{ \hat{R}_{S} (h) = \frac{1}{m} \sum_{i=1}^m 1_{h (\boldsymbol{x} _ i) \neq y_i} }$

経験誤差は汎化誤差の不偏推定量

示したいことは，以下の等式です．

$\displaystyle{ \mathbb{E}_{S \sim \mathcal{D}^m} \left[ \hat{R}_{S} (h) \right] = R(h) }$

期待値の線形性と，各訓練例は独立に分布 $\mathcal{D}$ に従って取ってくるという仮定から，

$\displaystyle{ \begin{eqnarray} \mathbb{E}_{S \sim \mathcal{D}^m} \left[ \hat{R}_{S} (h) \right] & = & \frac{1}{m} \sum_{i=1}^m \mathbb{E}_{S \sim \mathcal{D}^{m}} \left[ 1_{h (\boldsymbol{x} _ i) \neq y_i} \right] \\ & = & \frac{1}{m} \sum_{i=1}^m \mathbb{E}_{S \sim \mathcal{D}^{m}} \left[ 1_{h (\boldsymbol{x} _ i) \neq y_i} \right] \\ & = & \mathbb{E}_{S \sim \mathcal{D}^{m}} \left[ 1_{h (\boldsymbol{x}) \neq y} \right] \\ & = & \mathbb{E}_{(\boldsymbol{x}, y) \sim \mathcal{D}} \left[ 1_{h (\boldsymbol{x}) \neq y} \right] \\ & = & R(h) \end{eqnarray} }$

となって，求めたい等式が得られました．

おわりに

以上より，汎化誤差を計算するのは大変だから，汎化誤差を小さくする代わりに，その不偏推定量である経験誤差を小さくすることで汎化誤差を小さくできないかということになります．なるほど，妥当な感じがしますね．しかし，経験誤差を最小にする仮説が汎化誤差を最小にするとは限りません．この辺については追って書こうと思います．

次はPAC学習の記事かSVMの汎化誤差の記事を書きたいなと思っています．