7.6 モデル選択の理論的基盤 - 最小記述長とVC次元

「良いモデルとは何か」を問い続けてきた旅の、理論的な深みへ。前章ではAIC・BICというパラメータ数に比例したペナルティで訓練誤差を補正する手法を学んだ。

このチャプターでは、全く異なる2つの視点からモデル選択の本質に迫る。 1つ目は情報理論の視点：データを「圧縮して送信する」発想からBICと同じ結論が導ける（最小記述長、MDL）。 2つ目は学習理論の視点：パラメータ数では測れない「本当の複雑さ」を定義する概念（VC次元）だ。どちらも、「シンプルなモデルが良い」という直感の深い理由を教えてくれる。

データを「圧縮して送る」という発想

突然だが、こんな状況を想像してほしい。

あなたは友人にデータを送りたい。ただし通信コストを最小にしたい。どうすればよいか？

答えは「パターンを見つけて、そのパターンを使って圧縮する」ことだ。例えば、「1, 2, 3, 4, 5, 6, 7, 8, 9, 10」という数列を送るとき、数字を全部送るより「1から10まで1ずつ増える」と送る方が短い。これがデータ圧縮の本質だ。

アニメーションが示す曲線は $-\log_2(p)$ の形をしている。横軸が確率、縦軸がコード長だ。確率が高いメッセージは曲線の右下（コストが低い）、確率が低いメッセージは曲線の左上（コストが高い）に位置する。

1948年にクロード・シャノンが示した情報理論の基本定理によれば、確率 $\Pr(z)$ で発生するメッセージ $$z$$ を送るには、最低でも $-\log_2 \Pr(z)$ ビット必要だ。

l_i = -\log_2 \Pr(z_i) \text{ ビット}

よく起こるメッセージ（確率が高い）は短いコードで送れる。めったに起こらないメッセージには長いコードが必要だ。これは直感的だ。日本語で「が」や「の」は頻繁に使われるので、短い符号を割り当てる。「醤」のような漢字は滅多に使わないので、長い符号でよい。

平均メッセージ長の下限は：

\mathrm{E}[\text{length}] \geq -\sum \Pr(z_i) \log_2(\Pr(z_i))

右辺は確率分布のエントロピーと呼ばれる。これが送信に必要な最小の情報量だ。エントロピーが大きい（不確かさが大きい）ほど、伝えるべき情報量が多い。

確率 $\Pr(z_i) = 1/2$ なら1ビット、 $$1/4$$ なら2ビット、 $$1/8$$ なら3ビット。確率が半分になるたびに1ビット増える、というシンプルな関係だ。

モデルでデータを圧縮する

さて、このアイデアをモデル選択に使おう。

データ $\mathbf{Z} = (\mathbf{X}, \mathbf{y})$ があるとする。友人にこのデータを送りたい。友人は $\mathbf{X}$ （入力）を知っているので、送るのは $\mathbf{y}$ （出力）だけでいい。

戦略：モデル $$M$$ とパラメータ $\theta$ を共有し、それを使って $\mathbf{y}$ を圧縮して送る。

送信に必要なコスト（メッセージ長）は：

\text{length} = -\log \Pr(\mathbf{y} | \theta, M, \mathbf{X}) - \log \Pr(\theta | M)

第1項は「モデルが予測を外した分の通信コスト」、第2項は「パラメータ $\theta$ 自体を送るコスト」だ。

アニメーションの3本の曲線を見てほしい。青い曲線（単調減少）は「第1項のコスト」——モデルが複雑になるほど、データにフィットしてコストが下がる。赤い直線（単調増加）は「第2項のコスト」——複雑なモデルほど、パラメータを送るのにコストがかかる。緑の曲線はその合計で、U字型になっている。この最小点が最適なモデルだ。

これが最小記述長（MDL）の原理だ：「メッセージ長が最小になるモデルを選べ」。

直感的に理解しよう：

シンプルなモデル → パラメータを送るのは安い（第2項が小さい）が、予測を外しやすい（第1項が大きい）
複雑なモデル → データにフィットしやすい（第1項が小さい）が、パラメータを送るのに大きなコスト（第2項が大きい）

このトレードオフを最小化する点が最適なモデルだ。

MDLとBICは同じだった

驚くべき事実がある。

実はMDLとBIC（ベイズ情報量規準）は数学的に同じ結論を与える。

アニメーションが示すように、左側の「情報圧縮（MDL）」の道と、右側の「ベイズ統計（BIC）」の道は、全く異なる出発点から、同じ中央の箱（共通の数式）に収束する。

具体例で確かめよう。正規分布モデル $y \sim N(\theta, \sigma^2)$ 、パラメータ $\theta \sim N(0, 1)$ を考えると：

\text{length} = \text{const} + \log \sigma + \frac{(y - \theta)^2}{2\sigma^2} + \frac{\theta^2}{2}

これを最小化することは、事後確率を最大化することと等価だ。対数の性質から「-log 尤度 = コスト」が対応するためだ。そしてBICはこの事後確率の対数近似として導かれる。

つまり：

BICは「ベイズ的な視点」から生まれた
MDLは「情報圧縮の視点」から生まれた
両者は全く異なる動機から出発したのに、同じ公式に到達した

これは偶然ではなく、深い数学的構造を反映している。「良いモデル」の定義は、どの角度から見ても収束するのだ。

AICとBICの比較（再確認）：

BICは「一致推定量」（データ量 $N \to \infty$ のとき、真のモデルを選ぶ確率が1に収束するという性質）
AICは $N \to \infty$ で複雑すぎるモデルを選ぶ傾向がある
一方、有限サンプルではBICはシンプルすぎるモデルを選ぶことがある（重いペナルティのため）

パラメータ数では測れない「複雑さ」

ここで根本的な疑問が生まれる。MDLもBICも、前提として「パラメータ数 $$d$$ 」をモデルの複雑さの物差しとして使っていた。しかし、この「パラメータ数」という指標は本当に正確なのか？

次の2つの関数を考えてほしい：

ここで $I(\cdot)$ は「条件が真なら1、偽なら0」を返す指示関数だ。

関数A： $f(x, \alpha_0, \alpha_1) = I(\alpha_0 + \alpha_1^T x > 0)$ （2次元の線形分類器）

パラメータ数： $$p + 1 = 2$$

関数B： $f(x, \alpha) = I(\sin(\alpha \cdot x) > 0)$ （正弦波分類器）

パラメータ数： $$1$$ （αだけ！）

アニメーションを見てほしい。最初はゆっくりした正弦波（αが小さい）だ。αを増やすにつれて、曲線は急速に振動し始める。上向きの黄色矢印はαの増加を示している。パラメータは1つだけなのに、αを大きくするだけで、驚くほど複雑なパターンが生まれる。

直感的には、Aの方が複雑に見える（次元が高い）。しかし実は逆だ。 αを大きくするだけで $\sin(\alpha x)$ は非常に複雑な振る舞いをする。周波数を上げれば、どんなデータセットも完璧に分類できてしまう。

これは重大な問題だ。パラメータ数は「本当の複雑さ」を測っていない。

VC次元（Vapnik-Chervonenkis次元）はこの問題を解決する。パラメータ数に依存しない、より根本的な複雑さの尺度だ。

Shattering（散らす）という概念

VC次元を理解するために、「散らす（shatter）」という概念を学ぼう。

$$n$$ 個の点があるとする。これらの点に対して、 2値のラベル（赤か青か）を割り当てる方法は $$2^n$$ 通りある。

関数クラス $\{f(x, \alpha)\}$ が $$n$$ 個の点を「散らせる」 とは、どんなラベルの割り当て方をしても、その割り当てを完全に再現できるメンバーが必ずクラスの中に存在することを言う。

アニメーションを見てほしい。左側に三角形配置の3点がある。パターン1（上が赤、下2点が青）では、緑の直線が2グループを見事に分離する。パターン2（右が赤、残り2点が青）でも、別の直線でうまく分離できる。 3点は全ての $$2^3 = 8$$ 通りのパターンに対応できる。つまり「散らせる」。

右側を見ると、菱形配置の4点がある。XORパターン（対角の点が同じ色）では、どんな直線でも赤と青を完全に分離できない。直線を動かすと必ずどちらかの色の点が混入する。 4点は「散らせない」のだ（少なくとも、このパターンが困難な配置が存在する）。

したがって、「平面上の直線クラス」は3点を散らせるが4点は散らせない。この「散らせる最大の点数」がVC次元だ。

VC次元の定義：関数クラス $\{f(x, \alpha)\}$ のVC次元とは、そのクラスのメンバーが「散らせる」最大の点数（ある配置が存在するという意味で）。

$$p$$ 次元の線形判別関数 $I(\alpha_0 + \alpha_1^T x > 0)$ の VC次元は $$p+1$$ 。これはパラメータ数と一致する。しかし $\sin(\alpha x)$ のVC次元は無限大だ（αを適切に選ぶことで任意の点集合を散らすことができる）。

VC次元と汎化誤差の境界

VC次元が計算できると、訓練誤差の楽観性（訓練誤差が真のエラーをどれだけ過小評価するか）に対する理論的な上界が得られる。

アニメーションの2つのグラフを見てほしい。上のグラフ：VC次元 $$h$$ が増えると、誤差の上界も増加する（赤い曲線）。下のグラフ：データ数 $$N$$ が増えると、誤差の上界は減少する（青い曲線）。複雑なモデルほど、また少ないデータほど、汎化の保証が弱くなるという直感を視覚化している。

まず記号を整理しよう：

$\overline{\text{err}}$ ：訓練データでのエラー率（楽観的な推定）
$\text{Err}_\mathcal{T}$ ：未知データでの真のエラー率（これが知りたい）

$$N$$ 個の訓練点を使い、VC次元が $$h$$ の関数クラスでフィットしたとき、確率 $1 - \eta$ 以上で：

\text{Err}_\mathcal{T} \leq \overline{\text{err}} + \frac{\epsilon}{2}\left(1 + \sqrt{1 + \frac{4 \cdot \overline{\text{err}}}{\epsilon}}\right)

ここで $\epsilon$ は（ $$a_1, a_2$$ は理論から定まる正の定数）：

\epsilon = a_1 \frac{h[\log(a_2 N/h) + 1] - \log(\eta/4)}{N}

これがVC不等式だ。この式は「真のエラーは訓練エラーより最大でこれだけ大きい」という保証を与える。直感的に読むと：

$$h$$ （VC次元）が大きい → $\epsilon$ が大きい → 汎化誤差の上界が大きい（複雑なモデルは汎化しにくい）
$$N$$ （データ数）が大きい → $\epsilon$ が小さい → 上界がタイト（データが多いほど安心）

さらにVapnikは構造的リスク最小化（SRM）を提案した。 VC次元が $h_1 < h_2 < \cdots$ と増加するモデルの入れ子列を考え、上界が最小になるモデルを選ぶ。

実用上の注意：VC不等式の上界はしばしば非常にゆるい（実際のエラーよりはるかに大きい）。ただし相対的な比較には有用で、特にサポートベクターマシン（第12章）でSRMが成功裏に適用されている。

まとめ - 「シンプルさ」の深い理由

このチャプターで学んだ2つの視点を振り返ろう。

アニメーションが示すように、左上の青い正方形（MDL）と右上の赤いV字形（VC次元）は、全く異なる出発点から、中央の黄色い円（シンプルさという原則）へ収束する。

最小記述長（MDL）の視点：「良いモデル」とは、データを最も効率よく圧縮できるモデルだ。

シンプルなモデルはパラメータの送信コストが低い
複雑なモデルは残差（予測の外れ）の送信コストが低い
最適なモデルは2つのコストのバランスを取る

VC次元の視点：「複雑さ」はパラメータ数では測れない。

VC次元は「散らせる最大の点数」= 本当の表現力の指標
VC次元が大きいほど汎化誤差の上界が大きくなる
シンプルなモデル（低VC次元）は汎化しやすい

どちらの視点も、同じ結論に至る：モデルの複雑さに対するペナルティは必然なのだ。

情報理論から見れば「複雑なモデルは記述コストが高い」から。学習理論から見れば「複雑なモデルは汎化の保証が弱い」から。

「Occam's Razor（オッカムの剃刀）」という哲学的原則がある：「必要以上に仮定を増やすな」。このチャプターで学んだ数学は、その直感が単なる好みではなく、情報理論と確率論によって深く正当化されることを示している。