第1章学習の枠組み

この章の目標

• 教師あり学習をリスク最小化として定式化し、損失・リスク・経験リスクを区別して使える
• 二乗損失では条件付き期待値が、0-1 損失では事後確率が最大のクラスを選ぶ分類器がベイズ最適であることを証明できる
• 経験リスク最小化の誤差を近似誤差と推定誤差に分け、仮説集合の大きさとの関係を説明できる
• どの期待値をとるかを明示してバイアス–バリアンス分解を証明し、過学習と正則化を式で説明できる
• 交差検証が何を推定しているかを説明し、データ漏洩が評価を歪める理由を指摘できる

前提：22-statistics 第1章（確率変数・期待値・条件付き分布）。1.5 節の例では 02-linear-algebra 第7章 の直交射影と最小二乗法を使う。推定量のバイアス–バリアンス分解（22-statistics 第3章 定理 3.3）と比べるとよい。

商品の翌日の販売数を予測する、迷惑メールを判定する、製品の画像から傷を見つける――機械学習の多くの場面は、入力 $x$ から出力 $y$ を当てる規則 $f$ を、過去の例 $(x_1, y_1), \dots, (x_n, y_n)$ から作るという同じ形をしている。目標は過去の例をよく説明することではなく、これから来る新しい例でよく当てることである。過去の例を丸暗記すれば過去の例はすべて当たるが、将来の予測の役には立たない。

本章では、データが同じ未知の確率分布から独立に生まれると仮定して「よく当たる」を損失の期待値（リスク）で定式化し、最良の予測（1.3 節）、データでの平均を小さくする方法（1.4 節）、誤差の構造と過学習・正則化（1.5・1.6 節）、性能の正直な見積もり方（1.7 節）、その前提が崩れるデータ漏洩（1.8 節）を順に扱う。以後の章はすべてこの枠組みの上に立つ。

1.1 学習問題の設定

定義 1.1（教師あり学習, supervised learning）$\mathcal{X}$ を入力の集合、$\mathcal{Y}$ を出力の集合とし、$\mathcal{X} \times \mathcal{Y}$ 上の未知の確率分布 $P$（データ生成分布）を考える。訓練データ (training data) $S = ((x_1, y_1), \dots, (x_n, y_n))$ は、$P$ に従う独立同分布（i.i.d.）の確率変数 $(X_1, Y_1), \dots, (X_n, Y_n)$ の実現値である。写像 $f\colon \mathcal{X} \to \hat{\mathcal{Y}}$ を予測関数（仮説, hypothesis）といい、$S$ から予測関数 $\hat{f}_S$ を作る規則を学習アルゴリズムという。$\mathcal{Y} = \mathbb{R}$ のとき回帰 (regression)、$\mathcal{Y}$ が有限集合のとき分類 (classification) という。

$\hat{\mathcal{Y}}$ は予測値の集合で、多くの場合 $\mathcal{Y}$ と同じである。訓練データを確率変数とみるときも同じ記号 $S$ を使う。入力がベクトル $x \in \mathbb{R}^d$ のとき、その成分を特徴量 (feature) という。需要予測は回帰、迷惑メールの判定は 2 値分類、画像の分類は多クラス分類である。

教師なし学習 (unsupervised learning) では出力がなく、$x_1, \dots, x_n$ だけから構造を見つける（クラスタリング・次元削減は第3章、密度推定は第7章）。これらも多くは損失の期待値の最小化として書け、例えば $k$ 平均法は $E[\min_j \lVert X - \mu_j \rVert^2]$ を中心 $\mu_1, \dots, \mu_k$ について、密度推定は $E[-\log q(X)]$ を密度 $q$ について小さくする。

確率は 22-statistics 第1章 の範囲で扱う。$(X, Y)$ は同時密度 $p(x, y)$ をもつとし、$Y$ が離散値のとき（分類）は $y$ についての積分を和と読む。現れる期待値はすべて存在するとし、可測性などの細部には立ち入らない（厳密な扱いは 11-probability）。

1.2 損失関数とリスク

定義 1.2（損失・リスク・経験リスク）関数 $\ell\colon \mathcal{Y} \times \hat{\mathcal{Y}} \to [0, \infty)$ を損失関数 (loss function) という。$\ell(y, \hat{y})$ は、正解が $y$ のときに $\hat{y}$ と予測した損失である。予測関数 $f$ のリスク (risk) と、訓練データ $S$ での経験リスク (empirical risk) を

$$R(f) = E[\ell(Y, f(X))], \qquad \hat{R}_S(f) = \frac{1}{n}\sum_{i=1}^{n} \ell(y_i, f(x_i))$$

で定める（$(X, Y) \sim P$）。$R(f)$ を汎化誤差 (generalization error)、$\hat{R}_S(f)$ を訓練誤差 (training error) ともいう。

例 1.3（代表的な損失関数）回帰では二乗損失 $(y - \hat{y})^2$ や外れ値に強い絶対損失 $\lvert y - \hat{y} \rvert$ を使う。分類の0-1 損失 $\mathbf{1}\lbrace y \neq \hat{y} \rbrace$ では $R(f) = P(Y \neq f(X))$ が誤分類率、$1 - R(f)$ が正解率 (accuracy) である。誤りの種類で損得が違うなら、見逃しの損失 $c_{\mathrm{FN}}$ と誤警報の損失 $c_{\mathrm{FP}}$ を別に置く（問題 1.1）。交差エントロピー損失は第2章、ヒンジ損失は第4章で扱う。

命題 1.4（経験リスクの不偏性）予測関数 $f$ が訓練データ $S$ によらずに定まっているとき、$E[\hat{R}_S(f)] = R(f)$ である。さらに $v = \operatorname{Var}(\ell(Y, f(X))) < \infty$ ならば $\operatorname{Var}(\hat{R}_S(f)) = v/n$ であり、任意の $\varepsilon > 0$ について $P(\lvert \hat{R}_S(f) - R(f) \rvert \geq \varepsilon) \leq v/(n\varepsilon^2)$。

証明. $Z_i = \ell(Y_i, f(X_i))$ は i.i.d. で、$E[Z_i] = R(f)$、$\operatorname{Var}(Z_i) = v$ である。期待値の線形性と、独立な確率変数の和の分散が分散の和であることから最初の 2 つが従い、最後はチェビシェフの不等式（22-statistics 第1章 定理 1.25）である。$\square$

1.3 ベイズ最適な予測

分布 $P$ が完全にわかっていたら、どの予測が最良だろうか。答えは損失関数によって変わる。

定義 1.5（条件付き期待値・条件付きリスク）$p_X(x) = \int p(x, y)\ dy > 0$ となる $x$ について、条件付き密度 $p(y \mid x) = p(x, y)/p_X(x)$ により $E[g(X, Y) \mid X = x] = \int g(x, y)p(y \mid x)\ dy$ と定める。$m(x) = E[Y \mid X = x]$ を条件付き期待値、$v(x) = E[(Y - m(x))^2 \mid X = x]$ を条件付き分散、$r(c \mid x) = E[\ell(Y, c) \mid X = x]$ を条件付きリスクという。

命題 1.6（全期待値の公式）$h(x) = E[g(X, Y) \mid X = x]$ とおくと $E[g(X, Y)] = E[h(X)]$。特に任意の $f$ について $R(f) = E[r(f(X) \mid X)]$。

証明. 積分の順序を交換して（フビニの定理）

$g(x, y) = \ell(y, f(x))$ とすれば後半を得る（$g(x, y) = y$ の場合が 22-statistics 第1章 命題 1.12 の前半である）。$\square$

定義 1.7（ベイズ最適）$R^{\ast} = \inf_f R(f)$（すべての予測関数についての下限）をベイズリスクといい、$R(f^{\ast}) = R^{\ast}$ となる $f^{\ast}$ をベイズ最適 (Bayes optimal) な予測関数という。分類ではベイズ分類器 (Bayes classifier)、$R^{\ast}$ をベイズ誤り率という。

補題 1.8（各点での最小化）各 $x$ について $f^{\ast}(x)$ が $c \mapsto r(c \mid x)$ の最小点ならば、$f^{\ast}$ はベイズ最適であり、任意の $f$ について $R(f) - R(f^{\ast}) = E[r(f(X) \mid X) - r(f^{\ast}(X) \mid X)] \geq 0$。

証明. 命題 1.6 から等式が従い、期待値の中身は各 $x$ で $0$ 以上である。$\square$

定理 1.9（二乗損失のベイズ最適予測）$E[Y^2] < \infty$ とする。$E[f(X)^2] < \infty$ を満たす任意の $f$ について

$$E[(Y - f(X))^2] = E[v(X)] + E[(f(X) - m(X))^2]$$

が成り立つ。したがって条件付き期待値 $m$ はベイズ最適で、$R^{\ast} = E[v(X)]$ である。$f$ がベイズ最適であることと $E[(f(X) - m(X))^2] = 0$ は同値である。

証明. $x$ と $c \in \mathbb{R}$ を固定すると、$E[Y - m(x) \mid X = x] = 0$ だから

$c = f(x)$ とおいて命題 1.6 を使えばよい（$c = 0$ の場合から $E[Y^2] = E[v(X)] + E[m(X)^2]$ なので各項は有限である）。$\square$

$m(X)$ は $Y$ を「$X$ の 2 乗可積分な関数全体」へ直交射影したものである（測度論での一般形は 11-probability 第5章 定理 5.3）。例えば $Y = g(X) + \varepsilon$ で雑音 $\varepsilon$ が $X$ と独立、平均 $0$、分散 $\sigma^2$ なら、$m = g$、$R^{\ast} = \sigma^2$ であり、真の関数がわかっていても雑音の分の誤差は残る。同じ計算は、二乗損失のベイズ推定量が事後平均であること（22-statistics 第7章 定理 7.10）にも現れる。

定理 1.10（0-1 損失のベイズ分類器）$\mathcal{Y} = \hat{\mathcal{Y}} = \lbrace 1, \dots, K \rbrace$、$\ell$ を 0-1 損失とし、$\eta_k(x) = P(Y = k \mid X = x)$ とおく。各 $x$ で $\eta_{f^{\ast}(x)}(x) = \max_k \eta_k(x)$ となる（事後確率が最大のクラスを選ぶ）$f^{\ast}$ はベイズ最適であり、$R^{\ast} = 1 - E[\max_k \eta_k(X)]$ である。

証明. $r(c \mid x) = P(Y \neq c \mid X = x) = 1 - \eta_c(x)$ は $\eta_c(x)$ が最大の $c$ で最小になる。補題 1.8 と命題 1.6 から従う。$\square$

系 1.11（2 値分類）$\mathcal{Y} = \lbrace 0, 1 \rbrace$、$\eta(x) = P(Y = 1 \mid X = x)$ とする。$f^{\ast}(x) = \mathbf{1}\lbrace \eta(x) > 1/2 \rbrace$ はベイズ分類器で、$R^{\ast} = E[\min(\eta(X), 1 - \eta(X))]$。さらに任意の $f\colon \mathcal{X} \to \lbrace 0, 1 \rbrace$ について

$$R(f) - R^{\ast} = E\left[\lvert 2\eta(X) - 1 \rvert\, \mathbf{1}\lbrace f(X) \neq f^{\ast}(X) \rbrace\right]$$

証明. $r(0 \mid x) = \eta(x)$、$r(1 \mid x) = 1 - \eta(x)$ なので $r(f^{\ast}(x) \mid x) = \min(\eta(x), 1 - \eta(x))$ で、$f(x) \neq f^{\ast}(x)$ ならその差は $\max - \min = \lvert 2\eta(x) - 1 \rvert$、$f(x) = f^{\ast}(x)$ なら $0$ である。補題 1.8 から従う。$\square$

系 1.11 の等式は、$\eta(x)$ が $1/2$ に近い（本当に紛らわしい）点での誤りはほとんど損にならないことを示している。

例 1.12（2 つの正規分布）$P(Y = 0) = P(Y = 1) = 1/2$ とし、$X$ の条件付き分布を $Y = 0$ のとき $N(0, 1)$、$Y = 1$ のとき $N(2, 1)$ とする。$\varphi(t) = e^{-t^2/2}/\sqrt{2\pi}$ とおくと、ベイズの定理より

なので、ベイズ分類器は「$x > 1$ なら $1$」である。標準正規分布の分布関数を $\Phi$ とすると、$R^{\ast} = \frac{1}{2}P(X > 1 \mid Y = 0) + \frac{1}{2}P(X \leq 1 \mid Y = 1) = \Phi(-1) \approx 0.1587$。分布が重なっているので、最良の分類器でも約 16% は誤る。$\eta(x)$ が「$x$ の 1 次式をロジスティック関数に入れた形」であること（共分散行列が共通の多変量正規分布でも同様：問題 1.3）は、第2章のロジスティック回帰の動機になる。

1.4 経験リスク最小化

$P$ は未知なので $m$ や $\eta_k$ は計算できない。そこでリスクの代わりに経験リスクを小さくする。ただし、どんな関数でもよいとすると意味がない。

例 1.13（丸暗記）$x_1, \dots, x_n$ が相異なるとき、$\hat{f}_S(x_i) = y_i$、それ以外では $\hat{f}_S(x) = 0$ とすると $\hat{R}_S(\hat{f}_S) = 0$ だが、$X$ が密度をもてば $P(X \in \lbrace x_1, \dots, x_n \rbrace) = 0$ なので $R(\hat{f}_S) = E[\ell(Y, 0)]$ であり、常に $0$ と予測するのと変わらない。

定義 1.14（経験リスク最小化）予測関数の集合 $\mathcal{F}$ を仮説集合 (hypothesis class) またはモデルという。$\hat{R}_S$ を $\mathcal{F}$ 上で最小にする $\hat{f}_S \in \mathcal{F}$ を選ぶ方法を経験リスク最小化 (empirical risk minimization, ERM) という（最小点が存在する場合）。

例えば $\mathcal{F} = \lbrace x \mapsto w^{\top}x + b \rbrace$ と二乗損失の ERM は線形回帰の最小二乗法である（第2章。$A^{\top}$ は転置で、02-linear-algebra の ${}^tA$ と同じもの）。確率モデル $q_\theta(y \mid x)$ について損失を $-\log q_\theta(y \mid x)$ とした ERM は最尤推定である（22-statistics 第3章 定義 3.9。本科目の第7章でも扱う）。0-1 損失の ERM は、線形分類器（超平面による分類）に限っても計算が難しい。訓練データが線形分離できる場合は線形計画法で解けるが、線形分離できるとは限らないデータで誤分類の数を最小にする超平面を求める問題は、次元 $d$ も入力の大きさに含めると NP 困難であることが知られている（参考文献の Shalev-Shwartz–Ben-David 第9章。NP 困難の意味は 23-optimization 第7章）。0-1 損失は凸でもない。そこで凸な代わりの損失（第2章のロジスティック損失、第4章のヒンジ損失）を使う。

$R_{\mathcal{F}} = \inf_{f \in \mathcal{F}} R(f)$ とおく。

命題 1.15（近似誤差と推定誤差） ERM の出力 $\hat{f}_S$ について、$R(\hat{f}_S) - R^{\ast} = (R(\hat{f}_S) - R_{\mathcal{F}}) + (R_{\mathcal{F}} - R^{\ast})$ の第 1 項を推定誤差、第 2 項を近似誤差という。推定誤差は次を満たす。

$$0 \leq R(\hat{f}_S) - R_{\mathcal{F}} \leq 2\sup_{f \in \mathcal{F}}\lvert \hat{R}_S(f) - R(f) \rvert$$

証明. $\hat{f}_S \in \mathcal{F}$ より左の不等式が成り立つ。右辺の上限を $2\Delta$ とおく。任意の $f \in \mathcal{F}$ について $\hat{R}_S(\hat{f}_S) \leq \hat{R}_S(f)$（ERM）だから

$f$ について上限をとればよい。$\square$

近似誤差は $\mathcal{F}$ を大きくするほど小さくなるが、一様なずれ $\Delta$ は $\mathcal{F}$ が大きいほど大きくなりやすい（例 1.13 はその極端な場合）。$\Delta$ を $\mathcal{F}$ の複雑さ（要素の数や VC 次元）で評価するのが第6章の学習理論である。

1.5 汎化誤差とバイアス–バリアンス分解

$R(\hat{f}_S)$ は、$S$ を固定して $S$ と独立な新しい $(X, Y) \sim P$ について損失の期待値をとったもので、$S$ によって変わる確率変数である。訓練データについての期待値を $E_S$ と書くと、$E_S[R(\hat{f}_S)]$ は「この学習アルゴリズムで $n$ 個から学習したときの平均的な汎化誤差」であり、二乗損失では 3 つに分けられる。

定理 1.16（バイアス–バリアンス分解, bias–variance decomposition）二乗損失を考える。入力 $x$ を固定し、$Y_x$ を「$X = x$ のときの $Y$ の条件付き分布」に従い訓練データ $S$ と独立な確率変数（$x$ での新しい観測）とする。$E[Y_x^2] < \infty$、$E_S[\hat{f}_S(x)^2] < \infty$ とし、$m(x) = E[Y_x]$、$v(x) = \operatorname{Var}(Y_x)$、$\bar{f}(x) = E_S[\hat{f}_S(x)]$ とおくと、$Y_x$ と $S$ の両方について期待値をとって

$$E\left[(Y_x - \hat{f}_S(x))^2\right] = \underbrace{v(x)}_{\text{雑音}} + \underbrace{(\bar{f}(x) - m(x))^2}_{\text{バイアスの 2 乗}} + \underbrace{E_S\left[(\hat{f}_S(x) - \bar{f}(x))^2\right]}_{\text{バリアンス}}$$

証明. $A = Y_x - m(x)$、$B = m(x) - \bar{f}(x)$、$C = \bar{f}(x) - \hat{f}_S(x)$ とおくと $Y_x - \hat{f}_S(x) = A + B + C$ で、$B$ は定数、$E[A] = E[C] = 0$。$A$ は $Y_x$ だけの、$C$ は $S$ だけの関数で両者は独立だから $E[AC] = E[A]E[C] = 0$。$E[AB] = BE[A] = 0$、$E[BC] = BE[C] = 0$ なので $E[(A + B + C)^2] = E[A^2] + B^2 + E[C^2]$。$\square$

系 1.17 テスト点 $(X, Y) \sim P$ が $S$ と独立ならば、$X$ の周辺分布についての期待値を $E_X$、$\operatorname{Var}_S(\hat{f}_S(x)) = E_S[(\hat{f}_S(x) - \bar{f}(x))^2]$ として

$$E_S[R(\hat{f}_S)] = E_X[v(X)] + E_X\left[(\bar{f}(X) - m(X))^2\right] + E_X\left[\operatorname{Var}_S(\hat{f}_S(X))\right]$$

証明. 独立性より、$X = x$ のもとでの $(Y, S)$ の条件付き分布は「$Y_x$ の分布と $S$ の分布の積」なので、$E[(Y - \hat{f}_S(X))^2 \mid X = x]$ は定理 1.16 の左辺に等しい。命題 1.6（$Y$ の代わりに組 $(Y, S)$ を考える）から従う。$\square$

入力を固定すると、バイアスとバリアンスを正確に計算できる。入力 $x_1, \dots, x_n$ を固定して $y_i = m(x_i) + \varepsilon_i$（$\varepsilon_i$ は独立で平均 $0$、分散 $\sigma^2$）とし、第 $i$ 行が特徴量 $\phi(x_i)^{\top} \in \mathbb{R}^p$（例えば $\phi(x) = (1, x, \dots, x^k)$）の行列 $\Phi$（$\operatorname{rank}\Phi = p$）で最小二乗法を行うと、当てはめ値は $\hat{y} = Hy$、$H = \Phi(\Phi^{\top}\Phi)^{-1}\Phi^{\top}$ である（02-linear-algebra 第7章 定理 7.19）。$m = (m(x_1), \dots, m(x_n))^{\top}$ と書く。

命題 1.18（最小二乗法の訓練誤差の楽観性）$y' = m + \varepsilon'$（$\varepsilon'$ は $\varepsilon$ と独立で同じ分布。同じ入力での新しい観測）とすると

$$E\left[\tfrac{1}{n}\lVert y - \hat{y} \rVert^2\right] = \tfrac{1}{n}\lVert (I - H)m \rVert^2 + \sigma^2\,\tfrac{n - p}{n}, \qquad E\left[\tfrac{1}{n}\lVert y' - \hat{y} \rVert^2\right] = \sigma^2 + \tfrac{1}{n}\lVert (I - H)m \rVert^2 + \sigma^2\,\tfrac{p}{n}$$

である。特に、新しい観測に対する誤差の期待値は、訓練誤差の期待値より $2\sigma^2 p/n$ だけ大きい。

証明. $H$ は $\Phi$ の列空間への直交射影なので $H^{\top} = H = H^2$（02-linear-algebra 第7章 命題 7.24）、$\operatorname{tr}H = \operatorname{tr}((\Phi^{\top}\Phi)^{-1}\Phi^{\top}\Phi) = p$ である。また $n$ 次正方行列 $A$ について $E[\varepsilon^{\top}A\varepsilon] = \sum_{i, j}A_{ij}E[\varepsilon_i\varepsilon_j] = \sigma^2\operatorname{tr}A$。$y - \hat{y} = (I - H)m + (I - H)\varepsilon$ で、$(I - H)^{\top}(I - H) = I - H$、交差項の期待値は $0$ なので、$E\lVert y - \hat{y} \rVert^2 = \lVert (I - H)m \rVert^2 + \sigma^2(n - p)$。同様に $y' - \hat{y} = (I - H)m + \varepsilon' - H\varepsilon$ で、独立性から交差項の期待値は $0$ なので、$E\lVert y' - \hat{y} \rVert^2 = \lVert (I - H)m \rVert^2 + n\sigma^2 + \sigma^2\operatorname{tr}(H^{\top}H) = \lVert (I - H)m \rVert^2 + n\sigma^2 + \sigma^2 p$。$\square$

第 2 式は定理 1.16 をテスト入力が $x_1, \dots, x_n$ から一様に選ばれる場合に計算したもので、$\sigma^2$ が雑音、$\frac{1}{n}\lVert (I - H)m \rVert^2$ がバイアスの 2 乗の平均（$\bar{f}(x_i) = (Hm)_i$）、$\sigma^2 p/n$ がバリアンスの平均（$\hat{y}$ の共分散行列 $\sigma^2 H$ の対角成分の平均）である。

命題 1.18 で使った仮定は、新しい観測も同じ入力でとること（固定計画）、雑音が独立で等分散であること、使う特徴量 $\Phi$ がデータを見る前に決まっていること（$H$ が $y$ によらないこと）である。モデルが正しいこと（$m$ が $\Phi$ の列空間に入ること）は使っていない。新しい入力で予測するとき（ランダム計画）は、モデルが正しい場合でも訓練誤差との差は $2\sigma^2 p/n$ 以上になり、ふつうはそれより大きい（証明は省く）。特徴量を同じデータで選んだときは $H$ が $y$ によるので、この式はそのままでは使えない。同じ計算は 22-statistics 第6章 命題 6.12 にもあり、マローズの $C_p$ や AIC の出発点になっている。

例 1.19（多項式の次数）$n = 20$、$x_i = (i - 1/2)/20$、$m(x) = \sin(2\pi x)$、$\sigma = 0.3$ とし、次数 $k$ の多項式（$p = k + 1$）を当てはめると、命題 1.18 の各項は次のとおりである（誤差の 2 列は期待値。計算機で計算した値）。

（$k = 5$ のバイアスの 2 乗は約 $1.3 \times 10^{-5}$。）次数を上げるとバイアスは減り、バリアンスは $p$ に比例して増え、新しい観測での誤差は $k = 3$ で最小になる。訓練誤差は単調に減り、$k = 19$（$p = n$）では $H = I$ となってデータを完全に通るので、訓練誤差だけを見るとつねに最も高い次数を選んでしまう。表は訓練データと同じ入力点での誤差であり、点と点の間では高い次数の多項式は大きく振動して、誤差はさらに大きくなりうる。

誤差がパラメータの数に対して U 字形になるのは典型的な振る舞いだが、定理ではない。パラメータの数 $p$ がデータの数 $n$ を超える領域でノルム最小の補間解（第2章の $X^{+}y$）を選ぶと、$p \approx n$ の付近で大きくなった誤差が、$p$ を増やすにつれて再び下がることがある（二重降下, double descent）。これは多くの実験で観察されており、線形回帰などの単純なモデルでは、どんな条件のもとで起こるか（いつでも起こるわけではない）が理論的にも解析されている（第6章）。

1.6 過学習と正則化

訓練誤差は小さいのに汎化誤差が大きい状態を過学習 (overfitting)、モデルが単純すぎて両方とも大きい状態を未学習 (underfitting) という。例 1.19 の $k = 19$ は前者、$k = 0, 1$ は後者である。過学習はバリアンスが大きい（訓練データの偶然のゆらぎに予測が引きずられる）ときに起こり、仮説集合を小さくするか、複雑な予測関数に罰則を課すことで抑える。

定義 1.20（正則化, regularization）関数 $\Omega\colon \mathcal{F} \to [0, \infty)$ と $\lambda > 0$ に対し、$\hat{R}_S(f) + \lambda\Omega(f)$ を $\mathcal{F}$ 上で最小にする $\hat{f}_\lambda$ を選ぶ方法を正則化といい、$\Omega$ を正則化項（罰則項）、$\lambda$ を正則化パラメータという。

線形モデル $f(x) = w^{\top}x$ で $\Omega = \lVert w \rVert^2$ ならリッジ回帰、$\Omega = \lVert w \rVert_1 = \sum_j\lvert w_j \rvert$ ならラッソである（第2章）。ニューラルネットワークの重み減衰（第5章）、再生核ヒルベルト空間のノルムによる正則化（第4章）も同じ形をしている。

命題 1.21（正則化パラメータの役割）$\hat{f}_\lambda$ を定義 1.20 の最小点とする。

1. $t = \Omega(\hat{f}_\lambda)$ とおくと、$\hat{f}_\lambda$ は「$f \in \mathcal{F}$、$\Omega(f) \leq t$ のもとで $\hat{R}_S(f)$ を最小にする」問題の最小点でもある。
2. $0 < \lambda < \mu$ ならば $\Omega(\hat{f}_\lambda) \geq \Omega(\hat{f}_\mu)$ かつ $\hat{R}_S(\hat{f}_\lambda) \leq \hat{R}_S(\hat{f}_\mu)$。

証明. (1) $\Omega(f) \leq t$ なら、最小性より $\hat{R}_S(f) \geq \hat{R}_S(\hat{f}_\lambda) + \lambda(t - \Omega(f)) \geq \hat{R}_S(\hat{f}_\lambda)$。(2) 最小性より $\hat{R}_S(\hat{f}_\lambda) + \lambda\Omega(\hat{f}_\lambda) \leq \hat{R}_S(\hat{f}_\mu) + \lambda\Omega(\hat{f}_\mu)$ と、$\lambda$ と $\mu$ を入れ替えた不等式が成り立つ。足すと $(\mu - \lambda)(\Omega(\hat{f}_\mu) - \Omega(\hat{f}_\lambda)) \leq 0$ で、これを第 1 式に戻すと $\hat{R}_S(\hat{f}_\lambda) \leq \hat{R}_S(\hat{f}_\mu)$。$\square$

$\lambda$ を大きくするほど $\Omega$ の小さい「単純な」予測関数が選ばれ、訓練誤差は大きくなる。(1) の逆向き（制約つき問題の解が、ある $\lambda \geq 0$ の罰則つき問題の解になること）は、凸な問題ではスレーター条件などのもとでラグランジュ双対性から従う（23-optimization 第4章 定理 4.15）。正則化がバリアンスを減らすしくみは第2章で計算する。$\lambda$ のように学習の前に決める量をハイパーパラメータという。

1.7 訓練・検証・テストと交差検証

汎化誤差は、学習に使っていないデータで損失を測って見積もる。

命題 1.22（テストデータによる評価）予測関数 $f$ が、$P$ から i.i.d. にとったテストデータ $T = ((x_j', y_j'))_{j=1}^{m}$ と独立に作られているとし、$f$ を作ったデータを固定して考える。損失が $[0, 1]$ に値をとるなら（0-1 損失など）、テスト誤差 $\hat{R}_T(f) = \frac{1}{m}\sum_j \ell(y_j', f(x_j'))$ は $E[\hat{R}_T(f)] = R(f)$、$\operatorname{Var}(\hat{R}_T(f)) \leq \frac{1}{4m}$ を満たし、$P(\lvert \hat{R}_T(f) - R(f) \rvert \geq \varepsilon) \leq \frac{1}{4m\varepsilon^2}$。

証明. $f$ は $T$ によらないので命題 1.4 が使える。$[0, 1]$ に値をとる $Z$ は $Z^2 \leq Z$ より $\operatorname{Var}(Z) \leq E[Z](1 - E[Z]) \leq 1/4$。$\square$

$m = 1000$ なら標準偏差は $0.016$ 以下で、$0.05$ 以上ずれる確率は $0.1$ 以下である（第6章のヘフディングの不等式なら $2e^{-2m\varepsilon^2} \approx 0.013$ 以下）。1000 件のテストデータで正解率が 0.5 ポイント違うだけのモデルは、この誤差に埋もれて見分けられないことが多い。

命題 1.23（選択による楽観的な偏り）$f_1, \dots, f_K$ をテストデータ $T$ と独立に作られた予測関数とすると、$E[\min_k \hat{R}_T(f_k)] \leq \min_k R(f_k)$。

証明. 各 $j$ について $\min_k \hat{R}_T(f_k) \leq \hat{R}_T(f_j)$ で、右辺の期待値は $R(f_j)$（命題 1.22）。$j$ について最小をとればよい。$\square$

例えば、予測を硬貨投げで決める（真の正解率が $0.5$ の）分類器 100 個をテストデータ 100 件で評価すると、各正解数は独立に二項分布 $B(100, 1/2)$ に従い、最良の正解率の期待値は約 $0.625$、それが $0.6$ 以上になる確率は約 $0.94$ である（計算機で計算した値）。そこでデータを 3 つに分ける：訓練データで各候補（モデルの種類やハイパーパラメータ）を学習し、検証データ (validation data) で候補を比べて 1 つを選び、テストデータ (test data) で選んだモデルの汎化誤差を最後に 1 回だけ見積もる。データが少なければ、検証データの代わりに交差検証を使う。

定義 1.24（$K$ 分割交差検証, $K$-fold cross-validation）添字の集合 $\lbrace 1, \dots, n \rbrace$ を、データの値によらずに（例えば無作為に）互いに素な $I_1, \dots, I_K$ に分け、$I_k$ 以外のデータ $S^{(-k)}$ で学習した予測関数を $\hat{f}^{(-k)}$ として、$\mathrm{CV}_K = \frac{1}{n}\sum_{k=1}^{K}\sum_{i \in I_k} \ell(y_i, \hat{f}^{(-k)}(x_i))$ とおく。$K = n$ の場合を一つ抜き交差検証 (leave-one-out cross-validation) という。

命題 1.25（交差検証が推定しているもの）訓練データが i.i.d. で各 $I_k$ の大きさが $n/K$ ならば、$S'$ を大きさ $n - n/K$ の i.i.d. 標本として $E[\mathrm{CV}_K] = E_{S'}[R(\hat{f}_{S'})]$。すなわち $\mathrm{CV}_K$ は「この学習アルゴリズムで $n - n/K$ 個から学習したときの汎化誤差の期待値」の不偏推定量である。

証明. $i \in I_k$ とする。$(X_i, Y_i)$ は $S^{(-k)}$ と独立に $P$ に従い、$S^{(-k)}$ は大きさ $n - n/K$ の i.i.d. 標本である。$S^{(-k)}$ を固定すると $\hat{f}^{(-k)}$ は $(X_i, Y_i)$ によらないので、$(X_i, Y_i)$ についての期待値は $R(\hat{f}^{(-k)})$（命題 1.4 で $n = 1$）。さらに $S^{(-k)}$ について期待値をとり、$i$ について平均すればよい。$\square$