Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

学習アルゴリズムの評価

損失関数

損失関数をℓ(y^,y)\ell(\hat{y}, y)とする。

例えば、分類問題での代表的な損失関数は 0-1損失 (0-1 loss) ℓ(y^,y)=1[y^≠y]\ell(\hat{y}, y) = \mathbf{1}[\hat{y} \neq y] である。

また回帰問題で使われる代表的な損失関数は 二乗損失 (squared loss) ℓ(y^,y)=(y^−y)2\ell(\hat{y}, y) = (\hat{y} - y)^2 である。

予測損失

仮説hhの 予測損失（predictive loss） R(h)R(h)を、予測値h(X)h(X)の損失のテストデータ(X,Y)(X,Y)の分布上の期待値

R(h):=E(X,Y)∼D[ℓ(h(X),Y)]R(h) := E_{(X,Y) \sim D}[\ell(h(X), Y)]
(1)

と定義する。

経験損失

経験損失（empirical loss） を、観測値に基づく損失の平均値

R^(h):=1n∑i=1nℓ(h(Xi),Yi)\hat{R}(h) := \frac{1}{n} \sum_{i=1}^n \ell\left(h\left(X_i\right), Y_i\right)
(2)

と定義する。

経験損失は別の表現もできる。データ数がnnのとき確率1/n1/nで(Xi,Yi)(X_i,Y_i)に値を取る確率変数を(X,Y)(X,Y)とし、これが従う分布（経験分布）をD^\hat{D}とする。このとき経験損失は

R^(h):=E(X,Y)∼D^[ℓ(h(X),Y)]\hat{R}(h) := E_{(X,Y) \sim \hat{D}}[\ell(h(X), Y)]
(3)

と表すことができる。

経験損失は予測損失の不偏推定量

データ(Xi,Yi)(X_i,Y_i)が同一の分布DDに従うとき、経験損失の期待値は予測損失に一致する。 実際、nn個の観測データの同時分布をDnD^nとすると、

EDn[R^(h)]=1n∑i=1nEDn[ℓ(h(Xi),Yi)]=1n∑i=1nR(h)=R(h)\mathbb{E}_{D^n}[\hat{R}(h)] =\frac{1}{n} \sum_{i=1}^n \mathbb{E}_{D^n}[\ell(h(X_i), Y_i)] =\frac{1}{n} \sum_{i=1}^n R(h)=R(h)
(4)

となる。したがって経験損失は予測損失の不偏推定量である。

経験損失は予測損失の一致推定量

観測データが独立に同一の分布DDに従うとき、R^(h)\hat{R}(h)はR(h)R(h)に確率収束する。分布DnD^nのもとで任意のε>0\varepsilon > 0に対して

lim⁡n→∞Pr⁡Dn(∣R^(h)−R(h)∣>ε)=0\lim _{n \rightarrow \infty} \operatorname{Pr}_{D^n} \left(\left| \widehat{R}(h)-R(h)\right| > \varepsilon \right) = 0
(5)

が成り立つ。ここでPr⁡Dn\operatorname{Pr}_{D^n}はDnD^nのもとでの確率。

標準的な問題設定ではテストデータと訓練データの分布は同一だが、実応用においては両者の分布が異なることもある。

例えば特徴量の分布が異なるという 共変量シフト（covariate shift） では、分布の違いを比として誤差関数に重みをつける推定方法がある。

またログデータを用いた推薦システムの学習（Off-Policy Learning）においても、ログデータ（訓練データ）が「従来の推薦モデルのもとでの観測データ」であり、実運用時のデータ（テストデータ）とは分布が異なるという似た問題がある。

参考：

ベイズ規則

ベイズ規則がh0:X→Yh_0: \mathcal{X} \rightarrow \mathcal{Y}のとき、R(h0)=inf⁡h: 可測 R(h)R(h_0) = \inf _{h: \text { 可測 }} R(h)が成り立つ。

条件付き期待値

EY[ℓ(h(x),Y)∣x]=∫Yℓ(h(x),y) dP(y∣x)\mathbb{E}_Y[\ell(h(x), Y) \mid x] = \int_{\mathcal{Y}} \ell(h(x), y) ~ d P(y \mid x)
(7)

を用いると

R(h)=EX[EY[ℓ(h(X),Y)∣X]]R(h)=\mathbb{E}_X [\mathbb{E}_Y[\ell(h(X), Y) \mid X]]
(8)

であるため、EY[ℓ(h(x),Y)∣x]\mathbb{E}_Y[\ell(h(x), Y) \mid x]を最小にする仮説hhを選べば予測誤差が最小になる

簡単のためy^=h(x)\hat{y}=h(x)とし、XXを省略して、

EY[ℓ(y^,Y)]=∫ℓ(y^,y) dP(y)\mathbb{E}_Y[\ell(\hat{y}, Y)] = \int \ell(\hat{y}, y) ~ d P(y)
(9)

を最小にするy^∈Y\hat{y} \in \mathcal{Y}を求める問題を考える

0-1損失のベイズ規則

損失関数として0-1損失 ℓ(y^,y)=1[y^≠y]\ell(\hat{y}, y) = \mathbf{1}[\hat{y} \neq y]を想定する。

予測損失R(h)R(h)は繰り返し期待値の法則により

R(h)=EX[EY[ℓ(y,h(X))∣X]]R(h) = \mathbb{E}_X \big[ \mathbb{E}_Y[\ell(y, h(X)) \mid X] \big]
(10)

と変形できるので、入力X=xX=xにおける条件付き期待値EY[ℓ(y,h(x))∣X=x]\mathbb{E}_Y[\ell(y, h(x)) \mid X=x]で考える。 YYが離散型確率変数とすると

EY[ℓ(y,h(x))∣X=x]=∑y∈Yℓ(y,y^)P(Y=y∣x)\begin{aligned} \mathbb{E}_Y[\ell(y, h(x)) \mid X=x] &= \sum_{y\in\mathcal{Y}} \ell(y, \hat{y}) P(Y=y \mid x)\\ \end{aligned}
(11)

となる。 また、0-1損失の期待値は誤って予測した割合（誤答率）に相当するため、1-正答率 の形に整理できる。

EY[ℓ(y,h(x))∣X=x]=∑y∈Yℓ(y,y^)P(Y=y∣x)=1−P(Y=h(x))⏟正答率\begin{aligned} \mathbb{E}_Y[\ell(y, h(x)) \mid X=x] &= \sum_{y\in\mathcal{Y}} \ell(y, \hat{y}) P(Y=y \mid x)\\ &= 1 - \underbrace{ P(Y = h(x)) }_{正答率} \end{aligned}
(12)

そのため、P(Y=h(x))P(Y = h(x))を最大化するようなh(x)∈Yh(x)\in\mathcal{Y}、つまり

h0(x)=arg maxy∈YP(Y=y∣x)h_0(x) = \mathop{\rm arg~max}\limits_{y\in\mathcal{Y}} P(Y = y | x)
(13)

が予測誤差を最小とする。これが0-1損失におけるベイズ規則になる。

# TODO: 確率の話も含める。PRML

二乗損失のベイズ規則

損失関数として二乗損失 ℓ(y^,y)=(y^−y)2\ell(\hat{y}, y) = (\hat{y} - y)^2を利用するとき、

EY[ℓ(y^,Y)]=E[(y^−Y)2]=E[(y^−E[Y]+E[Y]−Y)2](同じ数を足して引く)=E[(y^−E[Y])2+2(y^−E[Y])(E[Y]−Y)+(E[Y]−y)2]=E[(y^−E[Y])2]⏟=(y^−E[Y])2+2E[(y^−E[Y])(E[Y]−Y)]⏟=2E[y^E[Y]−y^Y−E[Y]2+E[Y]Y]=2y^E[Y]−2y^E[Y]−2E[Y]2+2E[Y]2=0+E[(E[Y]−Y)2]=(y^−E[Y])2+Var⁡[Y]\begin{aligned} \mathbb{E}_Y[\ell(\hat{y}, Y)] &= \mathbb{E}[(\hat{y} - Y)^2]\\ &= \mathbb{E}[(\hat{y} - \mathbb{E}[Y] + \mathbb{E}[Y] - Y)^2] \quad (同じ数を足して引く)\\ &= \mathbb{E}[ (\hat{y} - \mathbb{E}[Y])^2 + 2(\hat{y} - \mathbb{E}[Y])(\mathbb{E}[Y] - Y) + (\mathbb{E}[Y] - y)^2]\\ &= \underbrace{ \mathbb{E}[(\hat{y} - \mathbb{E}[Y])^2] }_{=(\hat{y} - \mathbb{E}[Y])^2} + \underbrace{ 2 \mathbb{E}[(\hat{y} - \mathbb{E}[Y])(\mathbb{E}[Y] - Y)] }_{ \begin{aligned} &=2 \mathbb{E}[\hat{y}\mathbb{E}[Y] - \hat{y}Y - \mathbb{E}[Y]^2 + \mathbb{E}[Y]Y]\\ &=2 \hat{y}\mathbb{E}[Y] - 2\hat{y}\mathbb{E}[Y] - 2\mathbb{E}[Y]^2 + 2\mathbb{E}[Y]^2\\ &=0 \end{aligned} } + \mathbb{E}[(\mathbb{E}[Y] - Y)^2]\\ &= (\hat{y} - \mathbb{E}[Y])^2 + \operatorname{Var}[Y]\\ \end{aligned}
(14)

となる。よってy^=E[Y]\hat{y}=\mathbb{E}[Y]とすれば予測誤差が最小になる。

条件付き期待値に戻って考えると、ベイズ規則は

h0(x)=E[Y∣x]h_0(x) = \mathbb{E}[Y|x]
(15)

によって与えられる。

別の導出
(Y−y^)2= ((Y−E[Y∣X])+(E[Y∣X]−y^))2= (Y−E[Y∣X])2+2(E[Y∣X]−y^)(Y−E[Y∣X])+(E[Y∣X]−y^)2\begin{aligned} (Y-\hat{y})^2 = ~& ((Y-\mathbb{E}[Y \mid X])+(\mathbb{E}[Y \mid X]-\hat{y}))^2 \\ = ~& (Y-\mathbb{E}[Y \mid X])^2\\ & + 2(\mathbb{E}[Y \mid X]-\hat{y}) (Y-\mathbb{E}[Y \mid X]) \\ & + (\mathbb{E}[Y \mid X]-\hat{y})^2 \end{aligned}
(16)

第1項はy^\hat{y}が含まれないため、最適化には関係がない。

第2項は最終的に(Y−y^)2(Y-\hat{y})^2の期待値をとってE[(Y−y^)2∣X]\mathbb{E}[(Y-\hat{y})^2\mid X]にしたとき、Y−E[Y∣X]Y-\mathbb{E}[Y \mid X]が

E[Y−E[Y∣X]∣X]=E[Y∣X]−E[Y∣X]=0\begin{aligned} &\mathbb{E}[Y-\mathbb{E}[Y \mid X] \mid X]\\ &= \mathbb{E}[Y \mid X] - \mathbb{E}[Y \mid X]\\ &= 0 \end{aligned}
(17)

となり0になる。

第3項のE[Y∣X]−y^\mathbb{E}[Y \mid X]-\hat{y} は y^=E[Y∣X]\hat{y} = \mathbb{E}[Y \mid X]のとき0になり予測誤差が最小化される。よって二乗損失のベイズ規則は条件付き期待値E[Y∣X]\mathbb{E}[Y \mid X]となる。

ベイズ誤差R∗R^*は

R∗=R(h0)=EX[V[Y∣X]]=EX[∫(y−E[Y∣X])2dP(y∣X)]R^* = R\left(h_0\right) =\mathbb{E}_X[V[Y \mid X]] =\mathbb{E}_X\left[\int(y-E[Y \mid X])^2 d P(y \mid X)\right]
(18)

となる。条件付き分散V[Y∣x]V[Y|x]が入力によらず一定の値σ2\sigma^2をとるとき、ベイズ誤差はσ2\sigma^2となる。

絶対誤差のベイズ規則

損失関数ℓ(y,y^)\ell(y, \hat{y})を絶対誤差∣y−y^∣|y - \hat{y}|とするとき、ベイズ規則は条件付き中央値

h0(x)=median⁡(Y∣X=x)h_0(x) = \operatorname{median}(Y|X=x)
(19)

になる

絶対誤差の最適解

誤差関数ℓ(y,y^)\ell(y, \hat{y})を絶対誤差∣y−y^∣|y - \hat{y}|とする。予測損失（期待予測誤差）は

R(y^)=EY[ℓ(y,y^)]=∫−∞∞∣y−y^∣f(y)dy\begin{aligned} R(\hat{y}) &= \mathbb{E}_Y[\ell(y, \hat{y})]\\ &= \int_{-\infty}^{\infty} |y - \hat{y}| f(y) dy\\ \end{aligned}
(20)

絶対値の中身の符号で場合分けすると

R(y^)=∫−∞∞∣y−y^∣f(y)dy=∫y^∞(y−y^)f(y)dy+∫−∞y^(y^−y)f(y)dy(絶対値を符号ごとに場合分けした)=∫y^∞yf(y)dy−y^∫y^∞f(y)dy+y^∫−∞y^f(y)dy−∫−∞y^yf(y)dy(∵積分の線形性)\begin{aligned} R(\hat{y}) &= \int_{-\infty}^{\infty} |y - \hat{y}| f(y) dy\\ &= \int_{\hat{y}}^{\infty} (y - \hat{y}) f(y) dy + \int_{-\infty}^{\hat{y}} (\hat{y} - y) f(y) dy \quad (絶対値を符号ごとに場合分けした)\\ &= \int_{\hat{y}}^{\infty} y f(y) dy - \hat{y} \int_{\hat{y}}^{\infty} f(y) dy + \hat{y} \int_{-\infty}^{\hat{y}} f(y) dy - \int_{-\infty}^{\hat{y}} y f(y) dy \quad (\because 積分の線形性) \end{aligned}
(21)

予測損失を微分するとそれぞれの項は

ddy^∫y^∞yf(y)dy=−y^f(y^)ddy^(−y^⋅∫y^∞f(y)dy)=ddy^(−y^)∫y^∞f(y)dy+(−y^)ddy^(∫y^∞f(y)dy)(積の微分)=−1⋅∫y^∞f(y)dy−y^⋅−f(y^)=−∫y^∞f(y)dy+y^f(y^)ddy^(y^⋅∫−∞y^f(y)dy)=ddy^y^⋅∫−∞y^f(y)dy+y^⋅ddy^∫−∞y^f(y)dy(積の微分)=∫−∞y^f(y)dy+y^⋅f(y^)ddy^(−∫−∞y^yf(y)dy)=−y^f(y^)\begin{aligned} \frac{d}{d \hat{y}} \int_{\hat{y}}^{\infty} y f(y) dy &= - \hat{y} f(\hat{y}) \\ \frac{d}{d \hat{y}} \left( - \hat{y} \cdot \int_{\hat{y}}^{\infty} f(y) dy \right) &= \frac{d}{d \hat{y}} \left( - \hat{y} \right) \int_{\hat{y}}^{\infty} f(y) dy + (- \hat{y}) \frac{d}{d \hat{y}} \left( \int_{\hat{y}}^{\infty} f(y) dy \right) \quad (積の微分)\\ &= -1 \cdot \int_{\hat{y}}^{\infty} f(y) dy - \hat{y} \cdot - f(\hat{y})\\ &= -\int_{\hat{y}}^{\infty} f(y) dy + \hat{y} f(\hat{y}) \\ \frac{d}{d \hat{y}} \left( \hat{y} \cdot \int_{-\infty}^{\hat{y}} f(y) dy \right) &= \frac{d}{d \hat{y}} \hat{y} \cdot \int_{-\infty}^{\hat{y}} f(y) dy + \hat{y} \cdot \frac{d}{d \hat{y}} \int_{-\infty}^{\hat{y}} f(y) dy \quad (積の微分)\\ &= \int_{-\infty}^{\hat{y}} f(y) dy + \hat{y} \cdot f(\hat{y}) \\ \frac{d}{d \hat{y}} \left( - \int_{-\infty}^{\hat{y}} y f(y) dy \right) &= - \hat{y} f(\hat{y}) \end{aligned}
(22)

よって

dR(y^)dy^=−y^f(y^)−∫y^∞f(y)dy+y^f(y^)+∫−∞y^f(y)dy+y^f(y^)−y^f(y^)=−∫y^∞f(y)dy+∫−∞y^f(y)dy\begin{aligned} \frac{d R(\hat{y})}{d \hat{y}} &= - \hat{y} f(\hat{y}) -\int_{\hat{y}}^{\infty} f(y) dy + \hat{y} f(\hat{y}) + \int_{-\infty}^{\hat{y}} f(y) dy + \hat{y} f(\hat{y}) - \hat{y} f(\hat{y})\\ &= -\int_{\hat{y}}^{\infty} f(y) dy + \int_{-\infty}^{\hat{y}} f(y) dy \end{aligned}
(23)

となる。dR(y^)dy^=0\frac{d R(\hat{y})}{d \hat{y}}=0とおいて整理すれば

∫y^∞f(y)dy=∫−∞y^f(y)dy\int_{\hat{y}}^{\infty} f(y) dy = \int_{-\infty}^{\hat{y}} f(y) dy
(24)

となる点が予測損失を極小化することがわかる。これはy^\hat{y}が中央値となるときである。

f(y)f(y)は確率密度関数なので、∫−∞∞f(y)dy=1\int_{-\infty}^{\infty} f(y) dy=1になる。−∞-\inftyからy^\hat{y}への積分とy^\hat{y}から∞\inftyへの積分が等しくなるのはその半分、すなわち

∫−∞y^f(y)dy=12\int_{-\infty}^{\hat{y}} f(y) dy = \frac{1}{2}
(25)

である。これは累積分布関数P(y^)\mathrm{P}(\hat{y})に等しい。よってy^\hat{y}は中央値である。

参考：定積分の微分

定積分の定義

∫axf(t)dt=F(x)−F(a)\int_a^x f(t) d t=F(x)-F(a)
(26)

より、この導関数は

F′(x)−0=f(x)F'(x)-0 = f(x)
(27)

アルゴリズムの評価

観測したサンプルS={(X1,Y1),…,(Xn,Yn)}S=\{(X_1, Y_1), \dots, (X_n, Y_n)\}から得られる仮説をhSh_Sとする。

期待予測損失

学習された仮説hSh_Sの評価尺度の1つとして、観測データSSの分布DnD^nに関する予測損失の期待値ES∼Dn[R(hS)]\mathbb{E}_{S \sim D^n}[R(h_S)]が考えられる。これは 期待予測損失 と呼ばれる。

統計的一致性

別の評価尺度として、R(hS)R(h_S)の分布に着目する方法もある。ベイズ誤差R∗=inf⁡hR(h)R^* = \inf_h R(h)とδ∈(0,1)\delta\in(0,1)とε>0\varepsilon>0に対して

Pr⁡S∼Dn(R(hS)−R∗<ε)>1−δ\operatorname*{Pr}_{S \sim D^n}\left(R(h_S) - R^* < \varepsilon \right)>1-\delta
(28)

が成り立つとし、1−δ1-\deltaに対してε\varepsilonがどのような値になるかを調べることで学習アルゴリズムの性能を評価する。

ベイズ誤差に近い予測損失を達成する仮説が得られる場合、統計的一致性をもつ学習アルゴリズムと呼ばれる

有限な仮説集合を用いた学習

仮説集合が有限集合の場合の予測損失の評価について。2値判別問題で考え、入力空間X\mathcal{X}から2値ラベル{+1,−1}\{+1,-1\}への関数hhの有限な仮説集合

H={h1,…,hT}\mathcal{H}=\left\{h_1, \ldots, h_T\right\}
(30)

を用いて学習を行う（なお、ベイズ規則がH\mathcal{H}に含まれるとは限らない）。ある分布PPに独立に従う学習データS={(X1,Y1),…,(Xn,Yn)}S=\{(X_1, Y_1), \dots, (X_n, Y_n)\}が与えられたとき、経験判別誤差を最小にする仮説

hS=argmin⁡h∈HR^(h)h_S=\operatorname*{argmin}_{h \in \mathcal{H}} \hat{R}(h)
(31)

を出力する学習アルゴリズムを考える。また、H\mathcal{H}の中で予測誤差を最小にする仮説をhHh_\mathcal{H}とする。

仮説

  • h0h_0：ベイズ規則h0=inf⁡R(h)h_0 = \inf R(h)

  • hHh_\mathcal{H}：H\mathcal{H}の中で予測誤差を最小にする仮説hH=argmin⁡h∈HR(h)h_\mathcal{H}=\operatorname*{argmin}_{h \in \mathcal{H}} R(h)

  • hSh_S：仮説集合とサンプルのもとで経験損失を最小化する仮説 hS=argmin⁡h∈HR^(h)h_S=\operatorname*{argmin}_{h \in \mathcal{H}} \hat{R}(h)

の関係は、定義より

R(h0)≤R(hH)≤R(hS),R^(hS)≤R^(hH)R(h_0) \leq R(h_\mathcal{H}) \leq R(h_S), \quad \hat{R}(h_S) \leq \hat{R}(h_\mathcal{H})
(32)

となる。

差 R(hS)−R(h0)R(h_S) - R(h_0) の上界を次のように評価する。

R(hS)−R(h0)=R(hS)−R^(hS)+R^(hS)−R(hH)+R(hH)−R(h0)≤R(hS)−R^(hS)+R^(hH)−R(hH)+R(hH)−R(h0)≤2max⁡h∈H∣R^(h)−R(h)∣+R(hH)−R(h0)\begin{aligned} &R(h_S) - R(h_0)\\ &= R(h_S) - \hat{R}(h_S) + \hat{R}(h_S) - R(h_\mathcal{H}) + R(h_\mathcal{H}) - R(h_0)\\ &\leq R(h_S) - \hat{R}(h_S) + \hat{R}(h_\mathcal{H}) - R(h_\mathcal{H}) + R(h_\mathcal{H}) - R(h_0)\\ &\leq 2 \max_{h\in \mathcal{H}} | \hat{R}(h) - R(h) | + R(h_\mathcal{H}) - R(h_0)\\ \end{aligned}
(33)

Z=1[h(X)≠Y]Z = \mathbf{1}[h(X)\neq Y]として、2max⁡h∈H∣R^(h)−R(h)∣2 \max_{h\in \mathcal{H}} | \hat{R}(h) - R(h) | にヘフディングの不等式を用いると

Pr⁡(2max⁡h∈H∣R^(h)−R(h)∣≥ε)≤∑h∈HPr⁡(∣R^(h)−R(h)∣≥ε/2)≤∑h∈H2e−2n(ε/2)2=2∣H∣e−nε2/2\begin{aligned} & \operatorname{Pr}\left(2 \max _{h \in \mathcal{H}}\left|\hat{R}(h) - R(h)\right| \geq \varepsilon\right) \\ \leq & \sum_{h \in \mathcal{H}} \operatorname{Pr}\left(\left|\hat{R}(h) - R(h)\right| \geq \varepsilon / 2\right) \\ \leq & \sum_{h \in \mathcal{H}} 2 e^{-2 n(\varepsilon / 2)^2} =2|\mathcal{H}| e^{-n \varepsilon^2 / 2} \end{aligned}
(35)

となり、δ=2∣H∣e−nε2/2\delta = 2|\mathcal{H}| e^{-n \varepsilon^2 / 2}とおくと、学習データの分布のもとで確率1−δ1-\delta以上で

2max⁡h∈H∣R(h)−R^(h)∣≤2nlog⁡2∣H∣δ2 \max _{h \in \mathcal{H}}\left|R(h)-\hat{R}(h)\right| \leq \sqrt{\frac{2}{n} \log \frac{2|\mathcal{H}|}{\delta}}
(36)

が成り立つ。よって

R(hS)−R(h0)≤2max⁡h∈H∣R^(h)−R(h)∣+R(hH)−R(h0)≤2nlog⁡2∣H∣δ+R(hH)−R(h0)\begin{aligned} &R(h_S) - R(h_0)\\ &\leq 2 \max_{h\in \mathcal{H}} | \hat{R}(h) - R(h) | + R(h_\mathcal{H}) - R(h_0)\\ &\leq \sqrt{\frac{2}{n} \log \frac{2|\mathcal{H}|}{\delta}} + R(h_\mathcal{H}) - R(h_0)\\ \end{aligned}
(37)

となる。

仮説集合H\mathcal{H}にベイズ規則h0h_0が含まれる場合、

R(hH)−R(h0)=0R(h_\mathcal{H}) - R(h_0) = 0
(38)

となるため、

R(hS)−R(h0)≤2nlog⁡2∣H∣δ  ⟺  R(hS)≤R(h0)+2nlog⁡2∣H∣δR(h_S) - R(h_0) \leq \sqrt{\frac{2}{n} \log \frac{2|\mathcal{H}|}{\delta}}\\ \iff R(h_S) \leq R(h_0) + \sqrt{\frac{2}{n} \log \frac{2|\mathcal{H}|}{\delta}}
(39)

となり、データ数nnが十分大きければ仮説hSh_Sの誤差はベイズ誤差に収束し、その確率オーダーは

R(hS)=R(h0)+OP(log⁡∣H∣n)R(h_S) = R(h_0) + O_P\left( \sqrt{\frac{\log |\mathcal{H}|}{n} } \right)
(40)

となる。このオーダーは最悪評価であり、問題設定によってはより速い収束レートが達成できる場合もある。

近似誤差と推定誤差のトレードオフ

一般には仮説集合H\mathcal{H}にベイズ規則h0h_0が含まれるとは仮定できず、

R(hH)−R(h0)>0R(h_\mathcal{H}) - R(h_0) > 0
(41)

となる。近似誤差（approximation error）と推定誤差（estimation error）を次のように定義する

  • 近似誤差 : biasH=Rerr(hH)−Rerr(h0)\rm{bias}_{\mathcal{H}}=R_{\mathrm{err}}\left(h_{\mathcal{H}}\right)-R_{\mathrm{err}}\left(h_0\right)

  • 推定誤差 : varH=2nlog⁡2∣H∣δ\rm{var}_{\mathcal{H}}=\sqrt{\frac{2}{n} \log \frac{2|\mathcal{H}|}{\delta}}

このとき、

R(hS)−R(h0)≤biasH+varHR(h_S) - R(h_0) \leq \rm{bias}_{\mathcal{H}} + \rm{var}_{\mathcal{H}}
(42)

となり、仮説集合を適切に設定することでhSh_Sの予測誤差を小さくできる。

近似誤差 biasH\rm{bias}_{\mathcal{H}}と推定誤差varH\rm{var}_{\mathcal{H}}の間にはトレードオフの関係がある。複数の有限の仮説集合H1,H2,…,HM\mathcal{H}_1, \mathcal{H}_2, \ldots, \mathcal{H}_Mの関係が

H1⊂H2⊂⋯⊂HM\mathcal{H}_1 \subset \mathcal{H}_2 \subset \cdots \subset \mathcal{H}_M
(43)

を満たすとする。定義より近似誤差と推定誤差は

bias⁡H1≥bias⁡H2≥⋯≥bias⁡HMvar⁡H1≤var⁡H2≤⋯≤var⁡HM\begin{aligned} & \operatorname{bias}_{\mathcal{H}_1} \geq \operatorname{bias}_{\mathcal{H}_2} \geq \cdots \geq \operatorname{bias}_{\mathcal{H}_M} \\ & \operatorname{var}_{\mathcal{H}_1} \leq \operatorname{var}_{\mathcal{H}_2} \leq \cdots \leq \operatorname{var}_{\mathcal{H}_M} \end{aligned}
(44)

となる。仮説集合が大きいほど近似誤差は小さくなるが、推定誤差は大きくなる。 なので最適な仮説集合を選ぶには、これらの和を小さくする仮説集合、すなわち

m^=argmin⁡mbias⁡Hm+var⁡Hm\hat{m}=\underset{m}{\operatorname{argmin}} \operatorname{bias}_{\mathcal{H}_m}+\operatorname{var}_{\mathcal{H}_m}
(45)

とするときの\mathcal{H}_\hat{m}を選べばよい。

適切な仮説集合はデータの分布やデータ数などによって変わる。推定誤差は1n\sqrt{\frac{1}{n}}が含まれるためデータ数nnが大きくなれば小さくなる。データ数が少ないときは近似誤差と推定誤差のバランスを考えて仮説集合のサイズを決める必要がある。 実用的な方法として正則化法がある。

二乗損失のバイアス・バリアンス分解

入力変数XXと出力変数YYの関係が、関数f(X)f(X)と説明しきれなかった誤差ε\varepsilonに分かれる、つまり

Y=f(X)+εY=f(X)+\varepsilon
(46)

から成るとする。

データ点X=x0X=x_0における予測損失

E[{Y−f^(X)}2∣X=x0]E\left[\{Y-\hat{f}(X)\}^2 \mid X=x_0\right]
(47)

を考える。二乗損失は

{Y−f^(X)}2={f(X)+ε−E[f^(X)]+E[f^(X)]−f^(X)}2={f(X)−E[f^(X)]}2+ε2+{E[f^(X)]−f^(X)}2+2ε{f(X)−E[f^(X)]}+2ε{E[f^(X)]−f^(X)}+2{f(X)−E[f^(X)]}{E[f^(X)]−f^(X)}\begin{aligned} \{Y-\hat{f}(X)\}^2= & \{f(X)+\varepsilon-E[\hat{f}(X)]+E[\hat{f}(X)]-\hat{f}(X)\}^2 \\ = & \{f(X)-E[\hat{f}(X)]\}^2 + \varepsilon^2 + \{E[\hat{f}(X)] - \hat{f}(X)\}^2 \\ & +2 \varepsilon\{f(X)-E[\hat{f}(X)]\}+2 \varepsilon\{E[\hat{f}(X)]-\hat{f}(X)\} \\ & +2\{f(X)-E[\hat{f}(X)]\}\{E[\hat{f}(X)]-\hat{f}(X)\} \end{aligned}
(48)

と展開できる。

これに対してX=x0X=x_0における条件付き期待値をとると

第1項 {f(X)−E[f^(X)]}2\{f(X)-E[\hat{f}(X)]\}^2 は確率変数ではないため期待値の外に出せて {f(x0)−E[f^(x0)]}2\{f(x_0)-E[\hat{f}(x_0)]\}^2 となる

第2項 ε2\varepsilon^2 は E[ε]=0E[\varepsilon] = 0 であるので E[ε2]=E[ε2]−E[ε]2=V[ε]=σ2E[\varepsilon^2] = E[\varepsilon^2] - E[\varepsilon]^2 = V[\varepsilon] = \sigma^2

第3項 は E[{E[f^(X)]−f^(X)}2∣X=x0]=V[f^(X)∣X=x0]=V[f^(x0)]E\big[ \{E[\hat{f}(X)] - \hat{f}(X)\}^2 \mid X=x_0 \big] = V[\hat{f}(X) \mid X = x_0 ] = V[\hat{f}(x_0)]

第4項は f(X)−E[f^(X)]f(X)-E[\hat{f}(X)] が確率変数ではないため期待値の外にでて

E[2ε{f(X)−E[f^(X)]}∣X=x0]=2{f(x0)−E[f^(x0)]}E[ε]=0E[ 2 \varepsilon \{f(X)-E[\hat{f}(X)]\} \mid X=x_0 ] = 2 \{f(x_0) - E[\hat{f}(x_0)]\} E[ \varepsilon ] = 0
(49)

第5項は f^(X)\hat{f}(X)とε\varepsilonが独立であるため

E[2ε{E[f^(X)]−f^(X)}∣X=x0]=2E[ε]⋅E[{E[f^(X)]−f^(X)}∣X=x0]=0E\big[ 2 \varepsilon\{E[\hat{f}(X)]-\hat{f}(X)\} \mid X=x_0 \big]\\ = 2 E[\varepsilon] \cdot E\big[ \{E[\hat{f}(X)]-\hat{f}(X)\} \mid X=x_0 \big] = 0
(50)

最後の項は

2E[{f(X)−E[f^(X)]}{E[f^(X)]−f^(X)}∣X=x0]=2{f(x0)−E[f^(x0)]}{E[f^(x0)]−f^(x0)}=02 E \big[ \{f(X)-E[\hat{f}(X)]\}\{E[\hat{f}(X)]-\hat{f}(X)\} \mid X=x_0 \big]\\ = 2 \{f(x_0) - E[\hat{f}(x_0)]\}\{E[\hat{f}(x_0)]-\hat{f}(x_0)\} = 0
(51)

となる。よって期待二乗損失は以下のように分解される

E[{Y−f^(X)}2∣X=x0]={f(x0)−E[f^(x0)]}2+V[f^(x0)]+σ2=Bias2+Variance+irreducible error\begin{aligned} E[\{Y-\hat{f}(X)\}^2 \mid X=x_0] &= \{ f(x_0)-E[\hat{f}(x_0)] \}^2 + V[\hat{f}(x_0)] + \sigma^2 \\ &= \text{Bias}^2 + \text{Variance} + \text{irreducible error} \end{aligned}
(52)

参考：

正則化

正則化 (regularization) は適切な大きさの仮説集合を学習するための代表的な方法。小さな仮説集合で対応できるデータに対して、大きな仮説集合から仮説を選ぶことに対してペナルティを掛ける。

複数の仮説集合 H1⊂⋯⊂HM\mathcal{H}_1 \subset \cdots \subset \mathcal{H}_M を用いて学習を行うとする。仮説 hh に対するペナルティ Φ:HM→R≥0\Phi: \mathcal{H}_M \rightarrow \mathbb{R}_{\geq 0} として、 m1<m2m_1<m_2 に対して

h∈Hm1,h′∈Hm2\Hm1⟹Φ(h)≤Φ(h′)h \in \mathcal{H}_{m_1}, \quad h^{\prime} \in \mathcal{H}_{m_2} \backslash \mathcal{H}_{m_1} \Longrightarrow \Phi(h) \leq \Phi\left(h^{\prime}\right)
(53)

を満たすような関数 Φ\Phi を考えると、 大きな仮説集合に含まれるほうがより大きなペナルティが課されることになる。

仮説の探索範囲は経験損失R^(h)\hat{R}(h)を小さくするように学習する

min⁡h∈HMR^(h)+λ⋅Φ(h)\min_{h \in \mathcal{H}_M} \hat{R}(h) + \lambda \cdot \Phi(h)
(54)

正則化パラメータλ≥0\lambda \geq 0を求める方法は様々なものが提案されている。

「データ数が十分大きいときは、大きな仮説集合を用いても予測誤差があまり大きくならない」という性質があるため、正則化パラメータをデータ数に依存するように定義して適切なオーダーでλ→0 (n→∞)\lambda \to 0 ~ (n \to \infty) とする方法が提案されている。この方法は予測誤差を理論的に評価しやすいという利点がある。

しかし実用上は交差検証法（Cross-Validation）を用いて決める方法が有用である。

機械学習
統計的学習理論
機械学習
二乗誤差の分解