学習アルゴリズムの評価

学習アルゴリズムの評価#

損失関数#

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

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

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

予測損失#

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

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

と定義する。

経験損失#

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

\hat{R} (h) := \frac{1}{n} \sum_{i = 1}^{n} ℓ (h (X_{i}), Y_{i})

と定義する。

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

\hat{R} (h) := E_{(X, Y) \sim \hat{D}} [ℓ (h (X), Y)]

と表すことができる。

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

データ $(X_{i}, Y_{i})$ が同一の分布 $D$ に従うとき、経験損失の期待値は予測損失に一致する。実際、 $n$ 個の観測データの同時分布を $D^{n}$ とすると、

E_{D^{n}} [\hat{R} (h)] = \frac{1}{n} \sum_{i = 1}^{n} E_{D^{n}} [ℓ (h (X_{i}), Y_{i})] = \frac{1}{n} \sum_{i = 1}^{n} R (h) = R (h)

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

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

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

lim_{n \to \infty} \Pr_{D^{n}} (| \hat{R} (h) - R (h) | > ε) = 0

が成り立つ。ここで $\Pr_{D^{n}}$ は $D^{n}$ のもとでの確率。

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

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

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

参考：

ベイズ規則#

定義

損失関数 $ℓ$ を定めたとき、任意の可測関数 $h : X \to Y$ のもとでの予測損失の下限

inf_{h : 可測} R (h)

を損失関数 $ℓ$ のもとでの ベイズ誤差（Bayes error） という。下限を達成する仮説が存在するとき、その仮説を ベイズ規則（Bayes rule） という。

ベイズ規則が $h_{0} : X \to Y$ のとき、 $R (h_{0}) = inf_{h : 可測} R (h)$ が成り立つ。

条件付き期待値

E_{Y} [ℓ (h (x), Y) ∣ x] = \int_{Y} ℓ (h (x), y) d P (y ∣ x)

を用いると

R (h) = E_{X} [E_{Y} [ℓ (h (X), Y) ∣ X]]

であるため、 $E_{Y} [ℓ (h (x), Y) ∣ x]$ を最小にする仮説 $h$ を選べば予測誤差が最小になる

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

E_{Y} [ℓ (\hat{y}, Y)] = \int ℓ (\hat{y}, y) d P (y)

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

0-1損失のベイズ規則#

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

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

R (h) = E_{X} [E_{Y} [ℓ (y, h (X)) ∣ X]]

と変形できるので、入力 $X = x$ における条件付き期待値 $E_{Y} [ℓ (y, h (x)) ∣ X = x]$ で考える。 $Y$ が離散型確率変数とすると

\begin{array}{r} \begin{aligned} E_{Y} [ℓ (y, h (x)) ∣ X = x] & = \sum_{y \in Y} ℓ (y, \hat{y}) P (Y = y ∣ x) \end{aligned} \end{array}

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

\begin{array}{r} \begin{aligned} E_{Y} [ℓ (y, h (x)) ∣ X = x] & = \sum_{y \in Y} ℓ (y, \hat{y}) P (Y = y ∣ x) \\ = 1 - \underset{正 答 率}{\underset{⏟}{P (Y = h (x))}} \end{aligned} \end{array}

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

h_{0} (x) = \underset{y \in Y}{a r g m a x} P (Y = y | x)

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

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

二乗損失のベイズ規則#

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

\begin{array}{r} \begin{aligned} E_{Y} [ℓ (\hat{y}, Y)] & = E [(\hat{y} - Y)^{2}] \\ = E [(\hat{y} - E [Y] + E [Y] - Y)^{2}] (同 じ 数 を 足 し て 引 く) \\ = E [(\hat{y} - E [Y])^{2} + 2 (\hat{y} - E [Y]) (E [Y] - Y) + (E [Y] - y)^{2}] \\ = \underset{= (\hat{y} - E [Y])^{2}}{\underset{⏟}{E [(\hat{y} - E [Y])^{2}]}} + \underset{\begin{aligned} = 2 E [\hat{y} E [Y] - \hat{y} Y - E [Y]^{2} + E [Y] Y] \\ = 2 \hat{y} E [Y] - 2 \hat{y} E [Y] - 2 E [Y]^{2} + 2 E [Y]^{2} \\ = 0 \end{aligned}}{\underset{⏟}{2 E [(\hat{y} - E [Y]) (E [Y] - Y)]}} + E [(E [Y] - Y)^{2}] \\ = (\hat{y} - E [Y])^{2} + Var [Y] \end{aligned} \end{array}

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

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

h_{0} (x) = E [Y | x]

によって与えられる。

別の導出

\begin{array}{r} \begin{aligned} (Y - \hat{y})^{2} = & ((Y - E [Y ∣ X]) + (E [Y ∣ X] - \hat{y}))^{2} \\ = & (Y - E [Y ∣ X])^{2} \\ + 2 (E [Y ∣ X] - \hat{y}) (Y - E [Y ∣ X]) \\ + (E [Y ∣ X] - \hat{y})^{2} \end{aligned} \end{array}

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

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

\begin{array}{r} \begin{aligned} E [Y - E [Y ∣ X] ∣ X] \\ = E [Y ∣ X] - E [Y ∣ X] \\ = 0 \end{aligned} \end{array}

となり0になる。

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

ベイズ誤差 $R^{*}$ は

R^{*} = R (h_{0}) = E_{X} [V [Y ∣ X]] = E_{X} [\int (y - E [Y ∣ X])^{2} d P (y ∣ X)]

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

絶対誤差のベイズ規則#

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

h_{0} (x) = median (Y | X = x)

になる

アルゴリズムの評価#

観測したサンプル $S = {(X_{1}, Y_{1}), \dots, (X_{n}, Y_{n})}$ から得られる仮説を $h_{S}$ とする。

期待予測損失#

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

統計的一致性#

別の評価尺度として、 $R (h_{S})$ の分布に着目する方法もある。ベイズ誤差 $R^{*} = inf_{h} R (h)$ と $δ \in (0, 1)$ と $ε > 0$ に対して

\underset{S \sim D^{n}}{\Pr} (R (h_{S}) - R^{*} < ε) > 1 - δ

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

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

定義（統計的一致性）

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

lim_{n \to \infty} \underset{S \sim D^{n}}{\Pr} (R (h_{S}) \leq R^{*} + ε) = 0

が成り立つとき、学習アルゴリズム $S \mapsto h_{S}$ は 統計的一致性 (statistical consistency) をもつという。

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

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

H = {h_{1}, \dots, h_{T}}

を用いて学習を行う（なお、ベイズ規則が $H$ に含まれるとは限らない）。ある分布 $P$ に独立に従う学習データ $S = {(X_{1}, Y_{1}), \dots, (X_{n}, Y_{n})}$ が与えられたとき、経験判別誤差を最小にする仮説

h_{S} = \underset{h \in H}{argmin} \hat{R} (h)

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

仮説

$h_{0}$ ：ベイズ規則 $h_{0} = inf R (h)$
$h_{H}$ ： $H$ の中で予測誤差を最小にする仮説 $h_{H} = {argmin}_{h \in H} R (h)$
$h_{S}$ ：仮説集合とサンプルのもとで経験損失を最小化する仮説 $h_{S} = {argmin}_{h \in H} \hat{R} (h)$

の関係は、定義より

R (h_{0}) \leq R (h_{H}) \leq R (h_{S}), \hat{R} (h_{S}) \leq \hat{R} (h_{H})

となる。

差 $R (h_{S}) - R (h_{0})$ の上界を次のように評価する。

\begin{array}{r} \begin{aligned} R (h_{S}) - R (h_{0}) \\ = R (h_{S}) - \hat{R} (h_{S}) + \hat{R} (h_{S}) - R (h_{H}) + R (h_{H}) - R (h_{0}) \\ \leq R (h_{S}) - \hat{R} (h_{S}) + \hat{R} (h_{H}) - R (h_{H}) + R (h_{H}) - R (h_{0}) \\ \leq 2 max_{h \in H} | \hat{R} (h) - R (h) | + R (h_{H}) - R (h_{0}) \end{aligned} \end{array}

補題（ヘフディングの不等式 Hoeffding’s inequality）

確率変数 $Z$ は有界区間 $[0, 1]$ に値をとり、また確率変数 $Z_{1}, \dots, Z_{n}$ は独立に $Z$ と同じ分布にしたがうとする。このとき、任意の $ε > 0$ に対して

\Pr (| \frac{1}{n} \sum_{i = 1}^{n} Z_{i} - E [Z] | \geq ε) \leq 2 e^{- 2 n ε^{2}}

が成り立つ。

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

\begin{array}{r} \begin{aligned} \Pr (2 max_{h \in H} | \hat{R} (h) - R (h) | \geq ε) \\ \leq & \sum_{h \in H} \Pr (| \hat{R} (h) - R (h) | \geq ε / 2) \\ \leq & \sum_{h \in H} 2 e^{- 2 n (ε / 2)^{2}} = 2 | H | e^{- n ε^{2} / 2} \end{aligned} \end{array}

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

2 max_{h \in H} | R (h) - \hat{R} (h) | \leq \sqrt{\frac{2}{n} \log \frac{2 | H |}{δ}}

が成り立つ。よって

\begin{array}{r} \begin{aligned} R (h_{S}) - R (h_{0}) \\ \leq 2 max_{h \in H} | \hat{R} (h) - R (h) | + R (h_{H}) - R (h_{0}) \\ \leq \sqrt{\frac{2}{n} \log \frac{2 | H |}{δ}} + R (h_{H}) - R (h_{0}) \end{aligned} \end{array}

となる。

仮説集合 $H$ にベイズ規則 $h_{0}$ が含まれる場合、

R (h_{H}) - R (h_{0}) = 0

となるため、

\begin{array}{r} R (h_{S}) - R (h_{0}) \leq \sqrt{\frac{2}{n} \log \frac{2 | H |}{δ}} \\ ⟺ R (h_{S}) \leq R (h_{0}) + \sqrt{\frac{2}{n} \log \frac{2 | H |}{δ}} \end{array}

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

R (h_{S}) = R (h_{0}) + O_{P} (\sqrt{\frac{\log | H |}{n}})

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

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

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

R (h_{H}) - R (h_{0}) > 0

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

近似誤差 : ${b i a s}_{H} = R_{err} (h_{H}) - R_{err} (h_{0})$
推定誤差 : ${v a r}_{H} = \sqrt{\frac{2}{n} \log \frac{2 | H |}{δ}}$

このとき、

R (h_{S}) - R (h_{0}) \leq {b i a s}_{H} + {v a r}_{H}

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

近似誤差 ${b i a s}_{H}$ と推定誤差 ${v a r}_{H}$ の間にはトレードオフの関係がある。複数の有限の仮説集合 $H_{1}, H_{2}, \dots, H_{M}$ の関係が

H_{1} \subset H_{2} \subset \dots \subset H_{M}

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

\begin{array}{r} \begin{aligned} {bias}_{H_{1}} \geq {bias}_{H_{2}} \geq \dots \geq {bias}_{H_{M}} \\ {var}_{H_{1}} \leq {var}_{H_{2}} \leq \dots \leq {var}_{H_{M}} \end{aligned} \end{array}

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

\hat{m} = \underset{m}{argmin} {bias}_{H_{m}} + {var}_{H_{m}}

とするときの $H_{\hat{m}}$ を選べばよい。

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

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

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

Y = f (X) + ε

から成るとする。

データ点 $X = x_{0}$ における予測損失

E [{Y - \hat{f} (X)}^{2} ∣ X = x_{0}]

を考える。二乗損失は

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

と展開できる。

これに対して $X = x_{0}$ における条件付き期待値をとると

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

第2項 $ε^{2}$ は $E [ε] = 0$ であるので $E [ε^{2}] = E [ε^{2}] - E [ε]^{2} = V [ε] = σ^{2}$

第3項は $E [{E [\hat{f} (X)] - \hat{f} (X)}^{2} ∣ X = x_{0}] = V [\hat{f} (X) ∣ X = x_{0}] = V [\hat{f} (x_{0})]$

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

E [2 ε {f (X) - E [\hat{f} (X)]} ∣ X = x_{0}] = 2 {f (x_{0}) - E [\hat{f} (x_{0})]} E [ε] = 0

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

\begin{array}{r} E [2 ε {E [\hat{f} (X)] - \hat{f} (X)} ∣ X = x_{0}] \\ = 2 E [ε] \cdot E [{E [\hat{f} (X)] - \hat{f} (X)} ∣ X = x_{0}] = 0 \end{array}

最後の項は

\begin{array}{r} 2 E [{f (X) - E [\hat{f} (X)]} {E [\hat{f} (X)] - \hat{f} (X)} ∣ X = x_{0}] \\ = 2 {f (x_{0}) - E [\hat{f} (x_{0})]} {E [\hat{f} (x_{0})] - \hat{f} (x_{0})} = 0 \end{array}

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

\begin{array}{r} \begin{aligned} E [{Y - \hat{f} (X)}^{2} ∣ X = x_{0}] & = {f (x_{0}) - E [\hat{f} (x_{0})]}^{2} + V [\hat{f} (x_{0})] + σ^{2} \\ = {Bias}^{2} + Variance + irreducible error \end{aligned} \end{array}

参考：

正則化#

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

複数の仮説集合 $H_{1} \subset \dots \subset H_{M}$ を用いて学習を行うとする。仮説 $h$ に対するペナルティ $Φ : H_{M} \to R_{\geq 0}$ として、 $m_{1} < m_{2}$ に対して

h \in H_{m_{1}}, h^{'} \in H_{m_{2}} ∖ H_{m_{1}} ⟹ Φ (h) \leq Φ (h^{'})

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

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

min_{h \in H_{M}} \hat{R} (h) + λ \cdot Φ (h)

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

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

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