第6章学習理論（機械学習の数理） | Lemma

この章の目標

PAC 学習の定義を、実現可能な場合と不可知の場合について正確に述べられる

ヘフディングの補題を含めてヘフディングの不等式を証明し、テストデータの大きさの見積もりに使える

有限仮説集合の汎化誤差上界を和集合上界で証明し、多くの候補から選ぶことの影響を見積もれる

VC 次元を定義して半直線・区間・半平面の VC 次元を証明でき、サウアーの補題と VC 次元による上界を正確に述べられる

ラデマッハ複雑度とノーフリーランチ定理の意味を説明し、過剰パラメータ化と二重降下について確立した事実と観察を区別できる

前提：第1章（リスク・経験リスク最小化・近似誤差と推定誤差）、22-statistics 第1章（独立性・マルコフの不等式）。6.1 節では 01-calculus 第4章のテイラーの定理と凸関数を、6.7 節では第2章の最小二乗法と特異値分解を使う。

訓練データでの誤り率が小さいモデルは、新しいデータでも誤り率が小さいと言えるだろうか。第1章の命題 1.15（近似誤差と推定誤差）によれば、経験リスク最小化（ERM）の推定誤差は、経験リスクとリスクの一様なずれ $\sup_{f \in \mathcal{F}}\lvert \hat{R}_S(f) - R(f) \rvert$ の 2 倍以下である。1 つの $f$ についてのずれは大数の法則で小さくなるが、 $\hat{f}_S$ はデータを見て選ばれるので、 $\mathcal{F}$ のすべての $f$ について同時にずれが小さいことが要る。本章では、それがどれだけのデータで成り立つかを、仮説集合の「大きさ」（要素の数、VC 次元、ラデマッハ複雑度）で表す。

得られる上界はどんな分布でも成り立つ代わりに、数値としては悲観的なことが多い。役に立つのは、必要なデータ数が何にどう依存するか（精度 $\varepsilon$ については $1/\varepsilon^2$ に、複雑さには比例し、確信度 $1 - \delta$ には $\log(1/\delta)$ でしか依存しない）を教える点と、「仮定なしにはどんな方法でも学習できない」という下界である。最後に、この古典的な理論では説明しきれない近年の観察を、確かなことと区別して紹介する。

設定. 特に断らない限り 2 値分類 $\mathcal{Y} = \lbrace 0, 1 \rbrace$ と 0-1 損失を考え、仮説集合 $\mathcal{F}$ は $\mathcal{X}$ から $\lbrace 0, 1 \rbrace$ への関数の集合とする。記号は第1章と同じで、 $R(f) = P(Y \neq f(X))$ 、 $\hat{R}_S(f)$ は大きさ $n$ の i.i.d. 訓練データ $S$ での誤り率、 $R_{\mathcal{F}} = \inf_{f \in \mathcal{F}}R(f)$ である。ERM の最小点が複数あるときはどれを選んでもよい（以下の結果は選び方によらない）。可測性の細部には立ち入らない。

6.1 ヘフディングの不等式

第1章の命題 1.22 では、テストデータでの誤り率のずれをチェビシェフの不等式で評価した。その上界はデータ数に反比例してしか小さくならず、多くの仮説について同時に評価するには足りない。値が有界な確率変数の和では、ずれの確率がデータ数について指数的に小さくなる。

補題 6.1（ヘフディングの補題, Hoeffding's lemma）確率変数 $X$ が $a \leq X \leq b$ 、 $E[X] = 0$ を満たすならば、任意の $s \in \mathbb{R}$ について $E[e^{sX}] \leq \exp(s^2(b - a)^2/8)$ である。

証明. $a = b$ なら $X = 0$ で明らかなので、 $a < b$ とする。 $E[X] = 0$ より $a \leq 0 \leq b$ である。 $x \mapsto e^{sx}$ は 2 階微分が $s^2e^{sx} \geq 0$ なので凸であり（01-calculus 第4章定理 4.30）、 $x \in [a, b]$ を $x = \frac{b - x}{b - a}a + \frac{x - a}{b - a}b$ と書くと $e^{sx} \leq \frac{b - x}{b - a}e^{sa} + \frac{x - a}{b - a}e^{sb}$ である。 $x = X$ として期待値をとり $E[X] = 0$ を使い、 $p = -a/(b - a) \in [0, 1]$ 、 $u = s(b - a)$ とおくと、 $sa = -pu$ より

E[e^{sX}] \leq (1 - p)e^{sa} + pe^{sb} = e^{-pu}(1 - p + pe^u) = e^{\psi(u)}, \qquad \psi(u) = -pu + \log(1 - p + pe^u)

である。 $q(u) = pe^u/(1 - p + pe^u) \in [0, 1]$ とおくと $\psi'(u) = -p + q(u)$ 、 $\psi''(u) = q(u)(1 - q(u)) \leq 1/4$ で、 $\psi(0) = \psi'(0) = 0$ 。テイラーの定理（01-calculus 第4章定理 4.19）より、 $u \neq 0$ なら $0$ と $u$ の間のある $c$ で $\psi(u) = \psi''(c)u^2/2 \leq u^2/8 = s^2(b - a)^2/8$ となる。 $\square$

定理 6.2（ヘフディングの不等式, Hoeffding's inequality） $X_1, \dots, X_n$ を独立な確率変数で $a_i \leq X_i \leq b_i$ （ $a_i < b_i$ となる $i$ がある）とし、 $S = \sum_{i=1}^{n}(X_i - E[X_i])$ とする。任意の $t > 0$ について
$P(S \geq t) \leq \exp\left(-\frac{2t^2}{\sum_{i=1}^{n}(b_i - a_i)^2}\right)$
であり、 $P(S \leq -t)$ も同じ式で抑えられ、 $P(\lvert S \rvert \geq t)$ はその 2 倍以下である。特に $X_i$ が $[0, 1]$ に値をとる i.i.d. で $E[X_i] = \mu$ ならば、標本平均 $\bar{X}$ について $P(\bar{X} - \mu \geq \varepsilon) \leq e^{-2n\varepsilon^2}$ 、 $P(\lvert \bar{X} - \mu \rvert \geq \varepsilon) \leq 2e^{-2n\varepsilon^2}$ である。

証明. $s > 0$ とし、 $C = \sum_i(b_i - a_i)^2$ とおく。マルコフの不等式（22-statistics 第1章定理 1.25）を $e^{sS} \geq 0$ に使うと $P(S \geq t) = P(e^{sS} \geq e^{st}) \leq e^{-st}E[e^{sS}]$ 。 $e^{s(X_i - E[X_i])}$ （ $i = 1, \dots, n$ ）は独立なので、期待値は積に分かれる（22-statistics 第1章の命題 1.4 の 3 と命題 1.6 の 3 を繰り返し使う）。 $X_i - E[X_i]$ は平均 $0$ で、幅 $b_i - a_i$ の区間 $[a_i - E[X_i], b_i - E[X_i]]$ に値をとるので、補題 6.1 より

P(S \geq t) \leq e^{-st}\prod_{i=1}^{n}E\left[e^{s(X_i - E[X_i])}\right] \leq \exp\left(-st + \frac{s^2C}{8}\right)

右辺の指数は $s = 4t/C$ で最小値 $-2t^2/C$ をとる。下側は $-X_i$ に同じ議論を使い、両側は 2 つの事象の和の確率がそれぞれの確率の和以下であることによる。最後の主張は $t = n\varepsilon$ 、 $C = n$ とした場合である。 $\square$

マルコフの不等式を $e^{sS}$ に使って $s$ を最適化するこの方法は、11-probability 第4章定理 4.24（クラメールの定理）の証明と同じ考え方（チェルノフ限界）である。

例 6.3（上界の比較）公正な硬貨を $n$ 回投げたときの表の割合 $\bar{X}$ について、 $P(\lvert \bar{X} - 1/2 \rvert \geq \varepsilon)$ の正確な値（二項分布から計算）と 2 つの上界を比べる（計算機で計算した値）。

$n$ , $\varepsilon$	正確な値	ヘフディング $2e^{-2n\varepsilon^2}$	チェビシェフ $1/(4n\varepsilon^2)$
$n = 100$ , $\varepsilon = 0.1$	$0.0569$	$0.271$	$0.25$
$n = 1000$ , $\varepsilon = 0.05$	$0.00173$	$0.0135$	$0.1$

$n\varepsilon^2$ が小さいとチェビシェフの上界のほうが良いこともあるが、 $n\varepsilon^2$ が大きくなると指数的に小さくなるヘフディングの上界が圧倒的に良い。どちらも分布によらない上界なので、正確な値よりかなり大きい。

系 6.4（テストデータの大きさ）予測関数 $f$ が、大きさ $m$ のテストデータ $T$ と独立に作られているとする。任意の $\delta \in (0, 1)$ について、確率 $1 - \delta$ 以上で
$\lvert \hat{R}_T(f) - R(f) \rvert \leq \sqrt{\frac{\log(2/\delta)}{2m}}$
である。したがって $m \geq \log(2/\delta)/(2\varepsilon^2)$ ならば、確率 $1 - \delta$ 以上でずれは $\varepsilon$ 以下である。

証明. $\mathbf{1}\lbrace y_j' \neq f(x_j') \rbrace$ は $[0, 1]$ に値をとる i.i.d. で平均 $R(f)$ なので、定理 6.2 で $2e^{-2m\varepsilon^2} = \delta$ となる $\varepsilon$ をとればよい。 $\square$

ヒント

実務では 系 6.4 は、テストデータの大きさを決めるときや、2 つのモデルの正解率の差に意味があるかを判断するときの目安になる。誤り率を $\pm 1$ ポイントの精度で確率 95% 以上保証するには $m \geq \log 40/(2 \cdot 0.01^2) \approx 18444.4$ 、すなわち 18445 件以上が要る（中心極限定理による正規近似で最悪の分散 $1/4$ を使うと約 9604 件。こちらは近似で、ヘフディングは保証だが保守的である）。1000 件なら幅は約 $\pm 4.3$ ポイントあり、0.5 ポイントの差は見分けられない。誤り率がもともと小さい（陽性がまれなど）ときは、分散を使うベルンシュタインの不等式などのほうがずっと狭い幅を与える。

6.2 PAC 学習

「学習できる」を、分布を知らなくても、十分なデータがあれば高い確率でほぼ正しい予測関数を出せること、として定式化する（ヴァリアント 1984）。

定義 6.5（PAC 学習可能, PAC learnable）仮説集合 $\mathcal{F}$ が PAC 学習可能 (probably approximately correct) であるとは、関数 $n_{\mathcal{F}}\colon (0, 1)^2 \to \mathbb{N}$ と学習アルゴリズム $A$ があって、次が成り立つことをいう。任意の $\varepsilon, \delta \in (0, 1)$ と、ある $f^{\ast} \in \mathcal{F}$ について $R(f^{\ast}) = 0$ となる（実現可能, realizable）任意の分布 $P$ について、 $n \geq n_{\mathcal{F}}(\varepsilon, \delta)$ ならば、大きさ $n$ の i.i.d. 訓練データ $S$ から $A$ が出力する $A(S)$ は、確率 $1 - \delta$ 以上で $R(A(S)) \leq \varepsilon$ を満たす。

定義 6.6（不可知 PAC 学習可能, agnostic PAC learnable）定義 6.5 で実現可能性の仮定を外し、 $\mathcal{X} \times \lbrace 0, 1 \rbrace$ 上の任意の分布 $P$ について、確率 $1 - \delta$ 以上で $R(A(S)) \leq R_{\mathcal{F}} + \varepsilon$ となることを要求したものを、不可知 PAC 学習可能という。

「ほぼ正しい」（誤差 $\varepsilon$ 以下）ことを「高い確率で」（ $1 - \delta$ 以上）保証し、必要なデータ数 $n_{\mathcal{F}}$ は分布 $P$ によってはいけない。実現可能な場合は、ラベルが $\mathcal{F}$ のある関数で雑音なく決まる場合で、不可知の場合は雑音があってもよく、 $\mathcal{F}$ の中で最良のものとの比較を求める。ここではデータ数だけを問題にし、計算時間は問わない（もとの定義は計算時間が多項式であることも要求する）。

6.3 有限仮説集合

定理 6.7（有限仮説集合・実現可能な場合） $\mathcal{F}$ を有限集合とし、 $P$ は実現可能とする。ERM の出力 $\hat{f}_S$ について、任意の $\varepsilon > 0$ で $P(R(\hat{f}_S) > \varepsilon) \leq \lvert \mathcal{F} \rvert e^{-n\varepsilon}$ である。したがって
$n \geq \frac{\log\lvert \mathcal{F} \rvert + \log(1/\delta)}{\varepsilon}$
ならば確率 $1 - \delta$ 以上で $R(\hat{f}_S) \leq \varepsilon$ であり、 $\mathcal{F}$ は PAC 学習可能である。

証明. $R(f^{\ast}) = 0$ なので確率 1 で $\hat{R}_S(f^{\ast}) = 0$ であり、ERM の出力も $\hat{R}_S(\hat{f}_S) = 0$ を満たす。 $\mathcal{F}_{\mathrm{bad}} = \lbrace f \in \mathcal{F} \mid R(f) > \varepsilon \rbrace$ とすると、 $R(\hat{f}_S) > \varepsilon$ ならば、ある $f \in \mathcal{F}_{\mathrm{bad}}$ で $\hat{R}_S(f) = 0$ となる。固定した $f \in \mathcal{F}_{\mathrm{bad}}$ について、 $n$ 個のデータがすべて正しく分類される確率は、独立性より $(1 - R(f))^n \leq (1 - \varepsilon)^n \leq e^{-n\varepsilon}$ （ $1 - \varepsilon \leq e^{-\varepsilon}$ ）。事象の和の確率は確率の和以下である（和集合上界, union bound）から、

P(R(\hat{f}_S) > \varepsilon) \leq \sum_{f \in \mathcal{F}_{\mathrm{bad}}}P(\hat{R}_S(f) = 0) \leq \lvert \mathcal{F} \rvert e^{-n\varepsilon}

右辺が $\delta$ 以下であることと $n$ の条件は同値である。 $\square$

定理 6.8（有限仮説集合の一様な上界） $\mathcal{F}$ を有限集合とする。任意の分布 $P$ と $\delta \in (0, 1)$ について、確率 $1 - \delta$ 以上で、すべての $f \in \mathcal{F}$ について同時に
$\lvert \hat{R}_S(f) - R(f) \rvert \leq \sqrt{\frac{\log(2\lvert \mathcal{F} \rvert/\delta)}{2n}}$
が成り立つ。このとき ERM の出力は $R(\hat{f}_S) \leq R_{\mathcal{F}} + 2\sqrt{\log(2\lvert \mathcal{F} \rvert/\delta)/(2n)}$ を満たし、 $n \geq 2\log(2\lvert \mathcal{F} \rvert/\delta)/\varepsilon^2$ ならば ERM によって $\mathcal{F}$ は不可知 PAC 学習可能である。

証明. 右辺を $\tau$ とおく。固定した $f$ について $\hat{R}_S(f)$ は $[0, 1]$ に値をとる i.i.d. の平均で、期待値は $R(f)$ なので、定理 6.2 より $P(\lvert \hat{R}_S(f) - R(f) \rvert > \tau) \leq 2e^{-2n\tau^2} = \delta/\lvert \mathcal{F} \rvert$ 。和集合上界より、ずれが $\tau$ を超える $f$ が存在する確率は $\delta$ 以下である。その余事象の上で、第1章の命題 1.15 より $R(\hat{f}_S) - R_{\mathcal{F}} \leq 2\tau$ であり、 $2\tau \leq \varepsilon$ と $n$ の条件は同値である。 $\square$

$\hat{f}_S$ は $S$ に依存するので、ヘフディングの不等式を $\hat{f}_S$ にそのまま使うことはできないが、すべての $f$ について同時に保証すれば、どれが選ばれてもよい。その代償は $\log\lvert \mathcal{F} \rvert$ で、候補の数の対数でしか増えない。

例 6.9（論理積の規則） 100 個の 2 値の特徴量 $x \in \lbrace 0, 1 \rbrace^{100}$ について、「 $x_3 = 1$ かつ $x_{17} = 0$ かつ…なら陽性」のような論理積の規則の全体を $\mathcal{F}$ とする。各特徴量は「 $= 1$ を要求」「 $= 0$ を要求」「使わない」の 3 通りなので、常に陰性の規則を加えても $\lvert \mathcal{F} \rvert \leq 3^{100} + 1$ 、 $\log\lvert \mathcal{F} \rvert \approx 109.9$ である。 $\varepsilon = \delta = 0.05$ とすると、実現可能な場合は定理 6.7 より $n \geq (\log(3^{100} + 1) + \log 20)/0.05 \approx 2257.1$ 、すなわち 2258 件以上で足りる。不可知の場合の定理 6.8 の条件は $n \geq 2(\log(3^{100} + 1) + \log 40)/0.05^2 \approx 90840.1$ 、すなわち 90841 件以上である。雑音のない場合の $1/\varepsilon$ と、ある場合の $1/\varepsilon^2$ の差が大きい。同じ考え方で、 $d$ 個のパラメータを 32 ビットの浮動小数点数で表すモデルは高々 $2^{32d}$ 通りなので $\log\lvert \mathcal{F} \rvert \leq 32d\log 2 \approx 22.2d$ であり、必要なデータ数はパラメータの数に比例する程度と見積もられる。

6.4 VC 次元

閾値 $t \in \mathbb{R}$ で分類する規則のように $\mathcal{F}$ が無限集合なら、定理 6.8 は使えない。しかし $n$ 個のデータの上で区別できるのは、そこでのラベルの付け方の数だけである。この考え方による複雑さの尺度が VC 次元である（ヴァプニク–チェルボネンキス 1971）。

定義 6.10（粉砕・成長関数・VC 次元）有限集合 $C = \lbrace x_1, \dots, x_m \rbrace \subset \mathcal{X}$ について、 $\mathcal{F}_C = \lbrace (f(x_1), \dots, f(x_m)) \mid f \in \mathcal{F} \rbrace \subset \lbrace 0, 1 \rbrace^m$ を $\mathcal{F}$ の $C$ への制限という。 $\lvert \mathcal{F}_C \rvert = 2^m$ （すべてのラベルの付け方が実現できる）とき、 $\mathcal{F}$ は $C$ を粉砕する (shatter) という。 $\Pi_{\mathcal{F}}(m) = \max_{\lvert C \rvert = m}\lvert \mathcal{F}_C \rvert$ を成長関数 (growth function) といい、 $\mathcal{F}$ が粉砕する集合の大きさの最大値を VC 次元 (Vapnik–Chervonenkis dimension) といって $\operatorname{VCdim}(\mathcal{F})$ と書く（いくらでも大きい集合を粉砕するなら $\infty$ ）。

粉砕される集合の部分集合も粉砕されるので、 $\operatorname{VCdim}(\mathcal{F}) = d$ を示すには、大きさ $d$ の集合で粉砕されるものを 1 つ挙げ、大きさ $d + 1$ のどの集合も粉砕されないことを示せばよい。

例 6.11（半直線） $\mathcal{X} = \mathbb{R}$ 、 $\mathcal{F} = \lbrace x \mapsto \mathbf{1}\lbrace x \geq t \rbrace \mid t \in \mathbb{R} \rbrace$ とする。 $\lbrace 0 \rbrace$ は $t = 0$ （ラベル $1$ ）と $t = 1$ （ラベル $0$ ）で粉砕される。 $x_1 < x_2$ ならば $x_1 \geq t$ から $x_2 \geq t$ が従うので、ラベル $(1, 0)$ は実現できない。よって $\operatorname{VCdim}(\mathcal{F}) = 1$ である。 $m$ 個の点 $x_1 < \cdots < x_m$ でのラベルは「左から何個が $0$ か」で決まるので、 $\Pi_{\mathcal{F}}(m) = m + 1$ である。

例 6.12（区間） $\mathcal{F} = \lbrace \mathbf{1}_{[a, b]} \mid a \leq b \rbrace$ とする。 $\lbrace 1, 2 \rbrace$ は $[1, 2], [1, 1], [2, 2], [3, 3]$ でラベル $(1, 1), (1, 0), (0, 1), (0, 0)$ を実現するので粉砕される。 $x_1 < x_2 < x_3$ で $x_1, x_3 \in [a, b]$ なら $x_2 \in [a, b]$ なので、ラベル $(1, 0, 1)$ は実現できない。よって $\operatorname{VCdim}(\mathcal{F}) = 2$ 。 $m$ 点でのラベルは「すべて $0$ 」か「連続する一続きだけ $1$ 」なので、 $\Pi_{\mathcal{F}}(m) = m(m + 1)/2 + 1$ である。

定理 6.13（半空間の VC 次元） $\mathbb{R}^d$ 上の線形分類器全体 $\mathcal{F} = \lbrace x \mapsto \mathbf{1}\lbrace w^{\top}x + b \geq 0 \rbrace \mid w \in \mathbb{R}^d, b \in \mathbb{R} \rbrace$ の VC 次元は $d + 1$ である。特に、平面上の半平面の VC 次元は 3 である。

証明. 粉砕できる $d + 1$ 点： $C = \lbrace 0, e_1, \dots, e_d \rbrace$ （ $e_i$ は単位ベクトル）とし、 $0$ のラベルを $y_0$ 、 $e_i$ のラベルを $y_i$ とする。 $b = y_0 - 1/2$ 、 $w_i = y_i - y_0$ とおくと、 $0$ では $b \geq 0 \iff y_0 = 1$ 、 $e_i$ では $w^{\top}e_i + b = y_i - 1/2 \geq 0 \iff y_i = 1$ なので、どのラベルも実現できる。

$d + 2$ 点は粉砕できない： $x_1, \dots, x_{d+2} \in \mathbb{R}^d$ とする。 $\mathbb{R}^{d+1}$ の $d + 2$ 個のベクトル $(x_i, 1)$ は 1 次従属なので、 $0$ でない $\lambda \in \mathbb{R}^{d+2}$ で $\sum_i\lambda_ix_i = 0$ 、 $\sum_i\lambda_i = 0$ となるものがある。 $\lambda \neq 0$ と $\sum_i\lambda_i = 0$ より $\lambda$ は正の成分も負の成分ももつ。 $I = \lbrace i \mid \lambda_i > 0 \rbrace$ 、 $J$ をその補集合とし、「 $I$ に $1$ 、 $J$ に $0$ 」のラベルが $(w, b)$ で実現できたとする。すると

0 = w^{\top}\left(\sum_i\lambda_ix_i\right) + b\sum_i\lambda_i = \sum_{i \in I}\lambda_i(w^{\top}x_i + b) + \sum_{j \in J}\lambda_j(w^{\top}x_j + b)

である。第 1 の和の各項は $\lambda_i > 0$ と $w^{\top}x_i + b \geq 0$ より $0$ 以上、第 2 の和の各項は $\lambda_j \leq 0$ と $w^{\top}x_j + b < 0$ より $0$ 以上で、 $\lambda_j < 0$ となる $j \in J$ の項は正である。よって右辺は正となり、矛盾する。 $\square$

この例では VC 次元はパラメータの数 $d + 1$ に等しいが、いつもそうではない。

例 6.14（パラメータ 1 個で VC 次元が無限） $\mathcal{F} = \lbrace x \mapsto \mathbf{1}\lbrace \sin(\theta x) > 0 \rbrace \mid \theta \in \mathbb{R} \rbrace$ は、任意の $m$ について $\lbrace 10^{-1}, 10^{-2}, \dots, 10^{-m} \rbrace$ を粉砕する。実際、ラベル $y_1, \dots, y_m$ に対して $\theta = \pi(1 + \sum_{i=1}^{m}(1 - y_i)10^i)$ とすると、 $x_j = 10^{-j}$ で

\frac{\theta x_j}{\pi} = \underbrace{10^{-j} + \sum_{i < j}(1 - y_i)10^{i-j}}_{c_j} + (1 - y_j) + \sum_{i > j}(1 - y_i)10^{i-j}

で、最後の和は偶数、 $0 < c_j \leq \sum_{k \geq 1}10^{-k} = 1/9$ である。よって $\theta x_j$ は $2\pi$ を法として、 $y_j = 1$ なら $\pi c_j \in (0, \pi)$ 、 $y_j = 0$ なら $\pi(1 + c_j) \in (\pi, 2\pi)$ に等しく、 $\sin(\theta x_j) > 0$ と $y_j = 1$ が同値になる（ $m \leq 6$ のすべてのラベルについて計算機でも確かめた）。

定理 6.15（サウアーの補題, Sauer's lemma） $\operatorname{VCdim}(\mathcal{F}) = d < \infty$ ならば、すべての $m$ について
$\Pi_{\mathcal{F}}(m) \leq \sum_{i=0}^{d}\binom{m}{i}$
であり、 $m \geq d \geq 1$ なら右辺は $(em/d)^d$ 以下である。

前半はサウアー（1972）とシェラハ（1972）が独立に示した（ヴァプニク–チェルボネンキスも同種の評価を得ている）。前半の証明は問題 6.8 で扱う。後半は、 $d/m \leq 1$ より

\left(\frac{d}{m}\right)^d\sum_{i=0}^{d}\binom{m}{i} \leq \sum_{i=0}^{d}\binom{m}{i}\left(\frac{d}{m}\right)^i \leq \sum_{i=0}^{m}\binom{m}{i}\left(\frac{d}{m}\right)^i = \left(1 + \frac{d}{m}\right)^m \leq e^d

による。成長関数は、VC 次元が無限ならすべての $m$ で $2^m$ であり、有限ならたかだか $m$ の $d$ 次式の程度で増える。半直線（ $\Pi = m + 1 = \binom{m}{0} + \binom{m}{1}$ ）と区間（ $\Pi = 1 + m + \binom{m}{2}$ ）では、サウアーの補題の等号が成り立っている。

定理 6.16（VC 次元による汎化誤差上界, 統計的学習の基本定理） $\mathcal{X}$ から $\lbrace 0, 1 \rbrace$ への関数の集合 $\mathcal{F}$ と 0-1 損失について、次が成り立つ。

次の条件は同値である：(a) $\operatorname{VCdim}(\mathcal{F}) < \infty$ 。(b) $\mathcal{F}$ は PAC 学習可能。(c) $\mathcal{F}$ は不可知 PAC 学習可能。(d) ERM は $\mathcal{F}$ の不可知 PAC 学習アルゴリズムである。(e) 任意の $\varepsilon, \delta \in (0, 1)$ に対し、分布によらない $n_0$ があって、 $n \geq n_0$ ならどんな分布でも確率 $1 - \delta$ 以上で $\sup_{f \in \mathcal{F}}\lvert \hat{R}_S(f) - R(f) \rvert \leq \varepsilon$ （一様収束）。

$\operatorname{VCdim}(\mathcal{F}) = d < \infty$ ならば、分布にも $\mathcal{F}$ にもよらない定数 $C_1, C_2 > 0$ があって、必要なデータ数 $n_{\mathcal{F}}(\varepsilon, \delta)$ （の最小値）は

$C_1\frac{d + \log(1/\delta)}{\varepsilon^2} \leq n_{\mathcal{F}}(\varepsilon, \delta) \leq C_2\frac{d + \log(1/\delta)}{\varepsilon^2} \quad (\text{不可知}), \qquad C_1\frac{d + \log(1/\delta)}{\varepsilon} \leq n_{\mathcal{F}}(\varepsilon, \delta) \leq C_2\frac{d\log(1/\varepsilon) + \log(1/\delta)}{\varepsilon} \quad (\text{実現可能})$
を満たし、上界は ERM で達成される。同じ形で、確率 $1 - \delta$ 以上ですべての $f \in \mathcal{F}$ について $\lvert \hat{R}_S(f) - R(f) \rvert \leq C\sqrt{(d + \log(1/\delta))/n}$ （ $C$ は定数）が成り立つ。

主張のみとする（Shalev-Shwartz–Ben-David の定理 6.7・6.8。定数の値は証明の方法によって異なるので書かない）。上界の証明の考え方は次のとおりである。訓練データと同じ大きさの架空のデータ $S'$ を考えると、 $R(f)$ との一様なずれは $S$ と $S'$ での誤り率の差で抑えられる（対称化）。この差は $\mathcal{F}$ の $S \cup S'$ の $2n$ 点への制限、すなわち高々 $\Pi_{\mathcal{F}}(2n)$ 個の関数だけで決まるので、定理 6.8 と同様に和集合上界とヘフディングの不等式を使うと、 $\log\lvert \mathcal{F} \rvert$ の代わりに $\log\Pi_{\mathcal{F}}(2n) \leq d\log(2en/d)$ が現れる。 $\log n$ の因子を除くにはさらに細かい議論が要る。下界は 6.6 節のノーフリーランチ定理と同じ考え方による。

たとえば $\mathbb{R}^d$ の線形分類器では、精度 $\varepsilon$ の保証に必要なデータ数は $(d + \log(1/\delta))/\varepsilon^2$ に比例する程度で、特徴量の数に比例する。一方、例 6.14 のように VC 次元が無限の $\mathcal{F}$ は、パラメータが 1 個でも PAC 学習できない。

6.5 ラデマッハ複雑度（紹介）

VC 次元は分布によらない量で、 $\lbrace 0, 1 \rbrace$ 値の関数にしか使えない。データの分布に合わせて、実数値の損失にも使える複雑さの尺度がラデマッハ複雑度である。

定義 6.17（ラデマッハ複雑度, Rademacher complexity） $\sigma_1, \dots, \sigma_n$ を独立で $P(\sigma_i = 1) = P(\sigma_i = -1) = 1/2$ の確率変数（ラデマッハ変数）とする。実数値関数の集合 $\mathcal{G}$ と点の列 $S = (z_1, \dots, z_n)$ について
$\hat{\mathfrak{R}}_S(\mathcal{G}) = E_\sigma\left[\sup_{g \in \mathcal{G}}\frac{1}{n}\sum_{i=1}^{n}\sigma_ig(z_i)\right]$
を経験ラデマッハ複雑度、 $S$ を i.i.d. 標本としてさらに期待値をとった $\mathfrak{R}_n(\mathcal{G}) = E_S[\hat{\mathfrak{R}}_S(\mathcal{G})]$ をラデマッハ複雑度という。

$\sigma_i$ はでたらめなラベルで、 $\hat{\mathfrak{R}}_S$ は「 $\mathcal{G}$ の関数で、でたらめなラベルにどれだけ合わせられるか」を測る。関数が 1 つだけなら $0$ 、 $n$ 個の相異なる点の上のすべての $\lbrace 0, 1 \rbrace$ 値関数なら $1/2$ である（問題 6.6）。

定理 6.18（ラデマッハ複雑度による上界） $\mathcal{G}$ を $[0, 1]$ に値をとる関数の集合、 $z_1, \dots, z_n$ を i.i.d. 標本とする。任意の $\delta \in (0, 1)$ について、確率 $1 - \delta$ 以上で、すべての $g \in \mathcal{G}$ について同時に
$E[g(Z)] \leq \frac{1}{n}\sum_{i=1}^{n}g(z_i) + 2\mathfrak{R}_n(\mathcal{G}) + \sqrt{\frac{\log(1/\delta)}{2n}}$

主張のみとする（Mohri–Rostamizadeh–Talwalkar の第 3 章。証明は対称化と、ヘフディングの不等式を一般化したマクダーミッドの不等式による）。損失が $[0, 1]$ に値をとるなら（0-1 損失など）、 $g(x, y) = \ell(y, f(x))$ とすれば、すべての $f \in \mathcal{F}$ についてリスクが経験リスクと損失の集合 $\lbrace (x, y) \mapsto \ell(y, f(x)) \mid f \in \mathcal{F} \rbrace$ のラデマッハ複雑度で抑えられる。 $\lbrace 0, 1 \rbrace$ 値の場合は $\hat{\mathfrak{R}}_S \leq \sqrt{2\log\Pi(n)/n}$ （マサールの補題）が成り立ち、サウアーの補題と合わせると VC 次元による評価に戻る。ラデマッハ複雑度の利点は、パラメータの数ではなくノルムの大きさで複雑さを測れることである。

命題 6.19（ノルムで制限した線形関数） $\mathcal{G} = \lbrace x \mapsto w^{\top}x \mid \lVert w \rVert \leq B \rbrace$ とし、点 $x_1, \dots, x_n \in \mathbb{R}^d$ は $\lVert x_i \rVert \leq X_{\max}$ を満たすとする。このとき $\hat{\mathfrak{R}}_S(\mathcal{G}) \leq BX_{\max}/\sqrt{n}$ であり、この上界は次元 $d$ によらない。

証明. $v = \sum_i\sigma_ix_i$ とおくと、コーシー–シュワルツの不等式より $\sup_{\lVert w \rVert \leq B}w^{\top}v/n = B\lVert v \rVert/n$ 。 $E[\lVert v \rVert] \leq \sqrt{E[\lVert v \rVert^2]}$ （分散が $0$ 以上であることから）で、 $i \neq j$ なら $E[\sigma_i\sigma_j] = 0$ なので $E[\lVert v \rVert^2] = \sum_{i,j}E[\sigma_i\sigma_j]x_i^{\top}x_j = \sum_i\lVert x_i \rVert^2 \leq nX_{\max}^2$ 。よって $\hat{\mathfrak{R}}_S(\mathcal{G}) \leq B\sqrt{n}X_{\max}/n$ 。 $\square$

マージンを使った損失と組み合わせると、 $\lVert w \rVert$ が小さい線形分類器は、特徴量の次元がデータ数より大きくても汎化誤差を評価できる。第2章 2.2 節のリッジ回帰や第4章のサポートベクターマシンがノルムを小さくする理由の 1 つである。

6.6 ノーフリーランチ定理

仮説集合を制限しなければ、どんな方法でも学習できない。まず簡単な形で確かめる。

命題 6.20（訓練データの外での平均） $\mathcal{X}$ を有限集合とし、学習アルゴリズム $A$ と訓練データの入力 $x_1, \dots, x_n$ を固定する。真のラベル関数 $f\colon \mathcal{X} \to \lbrace 0, 1 \rbrace$ を $2^{\lvert \mathcal{X} \rvert}$ 通りから一様にランダムに選び、 $S = ((x_i, f(x_i)))_{i=1}^{n}$ とすると、 $x_1, \dots, x_n$ のどれとも異なる任意の点 $x$ について $P(A(S)(x) \neq f(x)) = 1/2$ である。

証明. 一様に選んだ $f$ の値 $f(x')$ （ $x' \in \mathcal{X}$ ）は独立に確率 $1/2$ ずつ $0, 1$ をとる。 $S$ は $f(x_1), \dots, f(x_n)$ だけで決まるので、 $f(x)$ は $S$ （と $A$ が使う乱数）と独立である。 $S$ を固定すると $A(S)(x)$ は定まり（ $A$ が乱数を使うならその乱数も固定する）、 $f(x)$ がそれと異なる確率は $1/2$ である。 $\square$

すべてのラベルの付け方を同じ重みで平均すると、どんなアルゴリズムも訓練データにない点では硬貨投げと変わらない。学習には、真の関数についての何らかの仮定（仮説集合の制限、事前分布、滑らかさなど。帰納バイアス (inductive bias)）が必要である。次の定理は、これを 1 つの分布についての主張にしたものである。

定理 6.21（ノーフリーランチ定理, no-free-lunch theorem） $A$ を 0-1 損失の 2 値分類の任意の学習アルゴリズムとし、訓練データの大きさ $n$ は $\lvert \mathcal{X} \rvert/2$ より小さいとする。このとき $\mathcal{X} \times \lbrace 0, 1 \rbrace$ 上のある分布 $P$ で、次の 2 つを満たすものが存在する。

ある関数 $f\colon \mathcal{X} \to \lbrace 0, 1 \rbrace$ について $R(f) = 0$ 。

大きさ $n$ の i.i.d. 訓練データ $S$ について、確率 $1/7$ 以上で $R(A(S)) \geq 1/8$ 。

主張のみとする（Shalev-Shwartz–Ben-David の定理 5.1）。証明の方針：大きさ $2n$ の集合 $C \subset \mathcal{X}$ の上の一様分布と、 $C$ 上の $2^{2n}$ 通りのラベル関数を考える。訓練データは $C$ の高々半分しか含まないので、命題 6.20 と同じ議論でラベル関数について平均した誤り率の期待値は $1/4$ 以上になり、ある $f$ で $E[R(A(S))] \geq 1/4$ 。 $R \in [0, 1]$ なので $1/4 \leq E[R] \leq P(R \geq 1/8) + \frac{1}{8}(1 - P(R \geq 1/8))$ となり、 $P(R \geq 1/8) \geq 1/7$ を得る。

$\mathcal{X}$ が無限集合なら、すべての関数からなる仮説集合は PAC 学習可能でない（どんな $n$ でも定理 6.21 が使える）。同じ議論を大きさ $2n$ の粉砕される集合に使うと、VC 次元が無限の $\mathcal{F}$ も PAC 学習可能でないことがわかり、これが定理 6.16 の (b)⇒(a) である。

注意

ノーフリーランチ定理は「どの手法も実際には同じくらい良い」という意味ではない。現実のデータは「すべてのラベル関数が同じ確率で起こる」ような分布から来ているわけではなく、滑らかさや構造があるので、それに合った仮定をおく手法がうまくいく。定理が言うのは、(1) どんな問題にも最良の万能の手法は存在しない、(2) 学習の成功は手法の仮定が問題に合っているかで決まる、ということである。ある手法が多くのベンチマークで勝つことは、それらの問題の性質に合っていることを示すが、別の種類の問題での優位は保証しない。

6.7 過剰パラメータ化と二重降下（紹介）

画像分類などの深層学習では、パラメータの数が訓練データの数よりはるかに多いモデルを、訓練誤差がほぼ $0$ になるまで学習することが多い。それでも新しいデータでよく当たる。ここでは、確立した事実と経験的な観察を分けて述べる。

観察：でたらめなラベルも覚えられる. ジャンら（2017）は、画像分類の標準的なネットワークが、訓練データのラベルを完全にでたらめに付け替えても訓練誤差を $0$ にできること、同じネットワークが正しいラベルでは良く汎化することを実験で示した。でたらめなラベルに合わせられるということは、訓練データの入力の上で経験ラデマッハ複雑度がほぼ最大になるということである。したがって、仮説集合（ネットワークの構造）だけで決まる VC 次元やラデマッハ複雑度の上界は、このネットワークの汎化を説明できない。説明には、データの分布と学習の方法（勾配法がどの解を選ぶか）を考えに入れる必要がある。

事実：勾配法が選ぶ解. 線形回帰では次のことが証明できる。

命題 6.22（勾配降下法は最小ノルム解に収束する） $X$ を $n \times p$ 行列、 $\sigma_1$ をその最大特異値とし、 $J(w) = \frac{1}{2}\lVert y - Xw \rVert^2$ に $w_0 = 0$ から勾配降下法 $w_{k+1} = w_k - \eta X^{\top}(Xw_k - y)$ （ $0 < \eta < 2/\sigma_1^2$ ）を適用すると、 $w_k$ はノルム最小の最小二乗解 $w^{+} = X^{+}y$ に収束する。特に $\operatorname{rank}X = n$ （ $p \geq n$ ）ならば、極限は訓練データを完全に通る解（ $Xw = y$ ）のうちノルムが最小のものである。

証明. $w^{+}$ は正規方程式 $X^{\top}Xw^{+} = X^{\top}y$ を満たすので、 $e_k = w_k - w^{+}$ は $e_{k+1} = (I - \eta X^{\top}X)e_k$ を満たす。 $X = \sum_{i=1}^{r}\sigma_iu_iv_i^{\top}$ を特異値分解とすると（第2章 2.2 節の記法）、第2章の定理 2.6 より $w^{+} = \sum_{i \leq r}\sigma_i^{-1}(u_i^{\top}y)v_i$ は $v_1, \dots, v_r$ の張る空間 $V_r$ に属し、 $e_0 = -w^{+} \in V_r$ 。 $V_r$ の上で $I - \eta X^{\top}X$ は $v_i$ を $(1 - \eta\sigma_i^2)v_i$ に写し、 $0 < \eta\sigma_i^2 \leq \eta\sigma_1^2 < 2$ より $\lvert 1 - \eta\sigma_i^2 \rvert < 1$ なので、 $e_k = \sum_{i \leq r}(1 - \eta\sigma_i^2)^k(v_i^{\top}e_0)v_i \to 0$ 。 $\operatorname{rank}X = n$ なら $XX^{+} = I_n$ なので $Xw^{+} = y$ で、 $w^{+}$ は $Xw = y$ の解の中でノルム最小である（02-linear-algebra 第8章定理 8.26）。 $\square$

明示的な罰則を加えなくても、学習の方法そのものがノルムの小さい解を選ぶ（暗黙の正則化, implicit regularization）。6.5 節のとおり、ノルムが小さいことは複雑さが小さいことにつながる。ニューラルネットワークの勾配法がどんな解を選ぶかは、一部の単純な模型で解析されているが、一般には研究の途中である。

二重降下. モデルの大きさ（パラメータの数 $p$ ）を増やすと、テスト誤差は、はじめ U 字形（第1章 1.5 節のバイアスとバリアンスの釣り合い）を描き、 $p$ がデータ数 $n$ に近づくと急に大きくなり、 $p > n$ で補間解（訓練誤差 $0$ ）を選ぶと再び下がることがある。ベルキンら（2019）はこれを二重降下 (double descent) と名づけ、ニューラルネットワークなどで観察した。線形回帰とランダム特徴のモデルでは、特徴量が正規分布に従う場合などにこの曲線が理論的に導かれている。次のコードは、 $n = 40$ 件のデータで、200 個の特徴量（前のものほど強く効く）のうち最初の $p$ 個を使って最小ノルムの最小二乗解を求め、新しいデータでの二乗誤差の期待値の中央値を、200 回の試行について求める。

import numpy as np

rng = np.random.default_rng(0)
n, D, sigma = 40, 200, 0.5                  # データ数・特徴量の総数・雑音の標準偏差
beta = 1 / np.arange(1, D + 1)
beta /= np.linalg.norm(beta)                # 前の特徴量ほど強く効く
for p in [5, 10, 20, 30, 36, 40, 44, 50, 70, 100, 200]:
    errs = []
    for _ in range(200):
        X = rng.standard_normal((n, D))
        y = X @ beta + sigma * rng.standard_normal(n)
        w = np.linalg.pinv(X[:, :p]) @ y    # 最初の p 個の特徴量で最小ノルム解
        # 新しい x ~ N(0, I) に対する二乗誤差の期待値
        errs.append(sigma**2 + np.sum((beta[:p] - w) ** 2) + np.sum(beta[p:] ** 2))
    print(f"p = {p:3d}: テスト誤差の中央値 {np.median(errs):.3f}")

p =   5: テスト誤差の中央値 0.404
p =  10: テスト誤差の中央値 0.392
p =  20: テスト誤差の中央値 0.542
p =  30: テスト誤差の中央値 1.018
p =  36: テスト誤差の中央値 2.561
p =  40: テスト誤差の中央値 25.007
p =  44: テスト誤差の中央値 3.092
p =  50: テスト誤差の中央値 1.470
p =  70: テスト誤差の中央値 0.999
p = 100: テスト誤差の中央値 1.020
p = 200: テスト誤差の中央値 1.109

誤差は $p = 10$ 付近で最小になり、 $p = n = 40$ で山をつくり、 $p > n$ で再び下がる（ $p$ が $n$ に近いと誤差の裾が非常に重いので、平均ではなく中央値を示した）。山ができる理由は、最小ノルム解 $X^{+}y = \sum_i\sigma_i^{-1}(u_i^{\top}y)v_i$ が雑音を $1/\sigma_i$ 倍に拡大することにある。 $p$ が $n$ に近いと $X$ の最小特異値が $0$ に近くなりやすく、雑音が大きく拡大される。 $p$ が $n$ より十分大きいと最小特異値は大きくなり、余分な次元に雑音が薄く分散される。ただしこの例では、2 回目の降下の後の誤差（約 $1.0$ ）は、 $p \leq n$ での最小値（約 $0.39$ ）より大きい。すべての特徴量が同じ程度に弱く効く問題では逆に $p > n$ の補間解のほうが良くなることもあり、どちらになるかは問題による。

確立していることと、そうでないことを整理しておく。(1) 線形回帰などの模型では、二重降下の曲線や「補間しても汎化する」条件が数学的に証明されている。(2) 深層学習で二重降下が観察されることは多くの実験で報告されているが、いつでも起こるわけではなく、雑音の量・正則化・学習の長さに依存する（線形回帰でも、リッジの罰則を適切に選べば山は低くなる）。(3) 深いネットワークがなぜ汎化するのかを十分に説明する理論は、まだない。「パラメータは多いほど良い」は定理ではない。

ヒント

実務では モデルの大きさや学習の長さを変えて検証誤差を見るとき、 $p \approx n$ 付近の山（あるいは学習途中の一時的な悪化）を見て「これ以上大きくしても無駄」と早合点しないよう、ある程度広い範囲を試す。一方で、大きなモデルが良いのは検証データで確かめられた場合だけであり、理論はそれを保証しない。何十もの設定を検証データで比べて選んだなら、選んだモデルの検証誤差は楽観的になる（第1章の命題 1.23、6.3 節）ので、最後に別のテストデータで 1 回だけ評価する。

まとめ

PAC 学習：分布によらないデータ数で、確率 $1 - \delta$ 以上で誤差 $\varepsilon$ 以下（実現可能な場合）、または最良の仮説との差 $\varepsilon$ 以下（不可知の場合）を保証できること。
ヘフディングの不等式：独立で有界な確率変数の和のずれの確率は $\exp(-2t^2/\sum_i(b_i - a_i)^2)$ 以下。証明はヘフディングの補題とマルコフの不等式による。テストデータでの評価の精度は $\sqrt{\log(2/\delta)/(2m)}$ 程度である。
有限仮説集合では、和集合上界により、実現可能なら $(\log\lvert \mathcal{F} \rvert + \log(1/\delta))/\varepsilon$ 、不可知なら $2\log(2\lvert \mathcal{F} \rvert/\delta)/\varepsilon^2$ 個のデータで十分である。候補の数は対数でしか効かない。
VC 次元は粉砕できる集合の最大の大きさで、半直線は 1、区間は 2、 $\mathbb{R}^d$ の半空間は $d + 1$ 。パラメータの数とは一般に一致しない（ $\sin(\theta x)$ の例）。
サウアーの補題により、VC 次元 $d$ なら成長関数は $m \geq d$ で $(em/d)^d$ 以下で、必要なデータ数は $(d + \log(1/\delta))/\varepsilon^2$ に比例する程度である。VC 次元が有限であることと（不可知）PAC 学習可能であることは同値である。
ラデマッハ複雑度はでたらめなラベルへの合わせやすさで、ノルムで制限した線形関数では次元によらない $BX_{\max}/\sqrt{n}$ 以下になる。
ノーフリーランチ定理：仮定のない万能の学習法はない。学習には問題に合った帰納バイアスが要る。
過剰パラメータ化：勾配法は最小ノルムの補間解を選び（線形回帰で証明できる）、テスト誤差は $p \approx n$ で山をもつ二重降下を示しうる。深層学習の汎化の理論は未完成である。

演習問題

問題 6.1 ★ 分類器の誤り率を、確率 99% 以上で $\pm 2$ ポイント以内の精度で見積もりたい。系 6.4 による必要なテストデータの数と、チェビシェフの不等式（ $\operatorname{Var} \leq 1/4$ を使う）による数を比べよ。

解答

ヘフディング： $m \geq \log(2/0.01)/(2 \cdot 0.02^2) = \log 200/0.0008 \approx 6622.9$ なので 6623 件。チェビシェフ： $P(\lvert \hat{R}_T - R \rvert \geq \varepsilon) \leq 1/(4m\varepsilon^2) \leq 0.01$ より $m \geq 1/(4 \cdot 0.0004 \cdot 0.01) = 62500$ 件。高い確信度を求めるほど、 $\log(1/\delta)$ でしか増えないヘフディングの評価の有利さが大きい。

問題 6.2 ★ $P(X = 1) = P(X = -1) = 1/2$ のとき $E[e^{sX}] = \cosh s$ である。 $\cosh s \leq e^{s^2/2}$ を示し、補題 6.1 の上界と比べよ。

解答

$\cosh s = \sum_{k \geq 0}s^{2k}/(2k)!$ 、 $e^{s^2/2} = \sum_{k \geq 0}s^{2k}/(2^kk!)$ で、 $(2k)! = \prod_{j=1}^{k}(2j - 1)(2j) \geq \prod_{j=1}^{k}2j = 2^kk!$ なので項ごとに比べて $\cosh s \leq e^{s^2/2}$ 。補題 6.1 では $b - a = 2$ なので上界は $e^{4s^2/8} = e^{s^2/2}$ で、これと一致する。両辺とも $s = 0$ の近くで $1 + s^2/2 + O(s^4)$ なので、この分布では補題の指数の係数 $1/8$ は改良できない。

問題 6.3 ★ $\mathbb{R}$ 上で $\mathcal{F} = \lbrace x \mapsto \mathbf{1}\lbrace x \geq t \rbrace \rbrace \cup \lbrace x \mapsto \mathbf{1}\lbrace x \leq t \rbrace \rbrace$ （ $t \in \mathbb{R}$ 。向きも選べる半直線）の VC 次元を求めよ。

解答

2 である。 $\lbrace 1, 2 \rbrace$ のラベル $(0, 0), (1, 1), (0, 1), (1, 0)$ は、それぞれ $\mathbf{1}\lbrace x \geq 3 \rbrace$ 、 $\mathbf{1}\lbrace x \geq 0 \rbrace$ 、 $\mathbf{1}\lbrace x \geq 1.5 \rbrace$ 、 $\mathbf{1}\lbrace x \leq 1.5 \rbrace$ で実現できる。 $x_1 < x_2 < x_3$ では、 $\mathbf{1}\lbrace x \geq t \rbrace$ のラベルは左から右へ減らず、 $\mathbf{1}\lbrace x \leq t \rbrace$ のラベルは増えないので、 $(1, 0, 1)$ はどちらでも実現できない。

問題 6.4 ★★ ある分析者が、ハイパーパラメータの候補 500 個を 2000 件の検証データで比べ、検証誤差が最小の 0.180 だった候補を選んで「誤り率は 18.0% ± 1.0%」と報告した。(1) 候補が 1 個だけなら、系 6.4 で $\delta = 0.05$ とした幅はいくつか。(2) 500 個の候補すべてについて同時に成り立つ幅を、定理 6.8 の考え方で求めよ。(3) この報告の問題点と、正しい手順を述べよ。

解答

(1) $\sqrt{\log 40/4000} \approx 0.030$ 。(2) 和集合上界より $\sqrt{\log(2 \cdot 500/0.05)/4000} = \sqrt{\log 20000/4000} \approx 0.050$ で、確率 95% 以上で 500 個すべての検証誤差が真の誤り率から $\pm 0.050$ 以内にある。選ばれた候補 $\hat{k}$ についても $R(\hat{k}) \leq 0.180 + 0.050$ までしか保証できず、さらに $R(\hat{k}) \leq \min_kR(k) + 2 \cdot 0.050$ である。(3) 検証データで最小のものを選んだので、その検証誤差は楽観的に偏っている（第1章の命題 1.23「選択による楽観的な偏り」）。±1.0% という幅には根拠がなく（候補が 1 個でも系 6.4 の幅は約 ±3%）、選択の影響も無視している。選んだモデルを、選択に使っていない別のテストデータで 1 回だけ評価し、その誤り率と幅（たとえば系 6.4）を報告すべきである。

問題 6.5 ★★ 平面上の座標軸に平行な長方形 $[a_1, b_1] \times [a_2, b_2]$ （ $a_i \leq b_i$ ）の内側を $1$ とする分類器全体の VC 次元が 4 であることを示せ。

解答

4 点 $(1, 0), (-1, 0), (0, 1), (0, -1)$ を粉砕できる：ラベル $1$ をつけたい点の集合 $T$ が空でなければ、 $T$ を含む最小の長方形（各座標の最小値から最大値まで）をとる。 $T$ にない点は、 $T$ の点のどれよりも、ある座標でその点の方向に飛び出しているので、この長方形に入らない（たとえば $(1, 0) \notin T$ なら、 $T$ の点の第 1 座標は $0$ 以下）。 $T$ が空なら、4 点から離れた小さな長方形をとればよい。一方、5 点では、第 1 座標が最小の点・最大の点、第 2 座標が最小の点・最大の点を 1 つずつ選ぶ（重複してもよい）と高々 4 点で、選ばれなかった点 $q$ がある。選んだ点に $1$ 、 $q$ に $0$ をつけるラベルは実現できない。選んだ点を含む長方形は、各座標で 5 点全体の最小値から最大値までを含むので、 $q$ も含むからである。

問題 6.6 ★★ (1) 関数が 1 つだけの集合 $\mathcal{G} = \lbrace g \rbrace$ の経験ラデマッハ複雑度は $0$ であることを示せ。(2) 相異なる $n$ 点の上のすべての $\lbrace 0, 1 \rbrace$ 値関数の集合では $1/2$ であることを示せ。(3) 例 6.11 の半直線の集合について、2 点 $x_1 < x_2$ での経験ラデマッハ複雑度を求めよ。

解答

(1) $E_\sigma[\frac{1}{n}\sum_i\sigma_ig(z_i)] = \frac{1}{n}\sum_iE[\sigma_i]g(z_i) = 0$ 。(2) 各 $\sigma$ について、 $\sigma_i = 1$ の点で $g = 1$ 、それ以外で $g = 0$ とするのが最大で、値は $\frac{1}{n}\lvert \lbrace i \mid \sigma_i = 1 \rbrace \rvert$ 。その期待値は $1/2$ 。(3) 実現できるラベルは $(0, 0), (0, 1), (1, 1)$ である。 $\sigma = (1, 1), (1, -1), (-1, 1), (-1, -1)$ のときの $\max_g\frac{1}{2}(\sigma_1g_1 + \sigma_2g_2)$ は、それぞれ $1, 0, 1/2, 0$ なので、平均は $3/8$ で、(2) の $1/2$ より小さい。

問題 6.7 ★ 「新しい手法が 30 個の公開データセットのうち 25 個で既存の手法より良かった。しかしノーフリーランチ定理によれば、すべての手法は平均すれば同じなので、この結果に意味はない」という主張は正しいか。

解答

正しくない。ノーフリーランチ定理（命題 6.20・定理 6.21）は、すべてのラベル関数を同じ重みで平均した場合や、手法ごとに都合の悪い分布を選んだ場合の主張であり、現実のデータセットがそのように選ばれているわけではない。30 個のデータセットでの優位は、それらと似た性質の問題で新しい手法の仮定が合っていることの証拠になる（統計的な有意性や、データセットの選び方の偏りは別に検討が要る）。定理から言えるのは、この結果が性質の異なる種類の問題での優位を保証しないことである。

問題 6.8 ★★★（サウアーの補題の証明）有限集合 $C$ と、 $\mathcal{F}$ が粉砕する $C$ の部分集合の個数 $s(C) = \lvert \lbrace B \subset C \mid \mathcal{F} \text{ は } B \text{ を粉砕する} \rbrace \rvert$ について、 $\lvert \mathcal{F}_C \rvert \leq s(C)$ を示し、サウアーの補題の前半を導け（空集合は、 $\mathcal{F}$ が空でなければ粉砕されるとみなす）。

解答

$\lvert C \rvert = m$ についての帰納法で、すべての $\mathcal{F}$ について同時に示す。 $m = 0$ なら両辺は $1$ である（ $\mathcal{F}$ が空なら両辺とも $0$ ）。 $C = \lbrace c_1, \dots, c_m \rbrace$ 、 $C' = \lbrace c_2, \dots, c_m \rbrace$ とし、

Y_0 = \lbrace y \in \lbrace 0, 1 \rbrace^{m-1} \mid (0, y) \in \mathcal{F}_C \text{ または } (1, y) \in \mathcal{F}_C \rbrace, \qquad Y_1 = \lbrace y \mid (0, y) \in \mathcal{F}_C \text{ かつ } (1, y) \in \mathcal{F}_C \rbrace

とすると $\lvert \mathcal{F}_C \rvert = \lvert Y_0 \rvert + \lvert Y_1 \rvert$ である。 $Y_0 = \mathcal{F}_{C'}$ なので、帰納法の仮定より $\lvert Y_0 \rvert \leq s(C')$ で、これは $c_1$ を含まない、粉砕される $C$ の部分集合の個数である。次に $\mathcal{F}' = \lbrace f \in \mathcal{F} \mid c_1$ での値だけが異なり $C'$ では一致する $f' \in \mathcal{F}$ がある $\rbrace$ とすると $Y_1 = \mathcal{F}'_{C'}$ なので、帰納法の仮定より $\lvert Y_1 \rvert$ は $\mathcal{F}'$ が粉砕する $C'$ の部分集合 $B$ の個数以下である。 $\mathcal{F}'$ が $B$ を粉砕すれば、 $B$ の各ラベルを実現する $f \in \mathcal{F}'$ とその相手 $f'$ により $c_1$ の値も両方実現できるので、 $\mathcal{F}$ は $B \cup \lbrace c_1 \rbrace$ を粉砕する。よって $\lvert Y_1 \rvert$ は $c_1$ を含む、粉砕される $C$ の部分集合の個数以下で、合わせて $\lvert \mathcal{F}_C \rvert \leq s(C)$ を得る。 $\operatorname{VCdim}(\mathcal{F}) = d$ なら粉砕される集合の大きさは $d$ 以下なので $s(C) \leq \sum_{i=0}^{d}\binom{m}{i}$ で、 $C$ について最大をとればサウアーの補題の前半になる。