VC次元——パラメータ数では測れない複雑度

パラメータ数は複雑度ではない

機械学習で「複雑度」というと、つい「パラメータがいくつあるか」と数えたくなります。 線形モデルなら係数の数、ニューラルネットワークなら重みの数、というように。 AIC、BIC、MDLはどれもこの考え方の上に乗っています。

しかし、ここに恐ろしい反例があります。関数$f(x;\alpha) = \mathrm{sign}(\sin(\alpha x))$を考えてください。ここで $\mathrm{sign}(\cdot)$ は 中身が正なら+1、負なら−1を返すだけの単純な符号関数です。 この関数の パラメータはたった1個 のαだけ。

アニメーションが示すように、αを大きくしていくと sin 曲線は細かく振動し始め、 どんな符号パターン（青と赤の割り当て）にも合わせることができます。 αを十分大きく取れば、1次元上のどんな有限個の点に対しても、 +1と−1の 好きな割り当てを実現 してしまうのです。

αという 1個 のパラメータだけで、任意の点列の任意のラベル付けが実現できる—— これが衝撃のポイントです。つまり「パラメータ数=複雑度」という素朴な等式は壊れています。

本当に必要なのは、ある関数の集まりが どれだけ多様なラベル付けを実現できるか という、 もっと本質的な能力の測り方です。VC次元はまさにこの問いに答えます。 「点に+1/−1を割り当てる多様性」を直接数えにいく、という発想です。

Shattering（粉砕）という発想

VapnikとChervonenkisが採った戦略はこうです。「関数たちの複雑度を直接測るのは難しい。 だから、それらの関数が 点をどう分類できるか を観察しよう」。

ここで登場するのが shattering（粉砕） という概念です。 具体的なイメージを先に持つために、まず「直線分類器の集まり」—— 平面に1本の直線を引き、片側を+1、もう片側を−1とするルール全体——を念頭においてください。 この 関数たちの集まり のことを以降「関数クラス $\mathcal{F}$」と呼びます。

平面上に3点を一般の位置（一直線上にない）に置くと、その3点に対する$2^3 = 8$ 通りのラベル付けすべてを、ある直線で実現できます。 アニメーションが示すように、直線が移動することで8通りのどのパターンにも対応できる。 つまり 3点はshatterされる。

その上で定義です。関数クラス $\mathcal{F}$ が、 点の集合 $S = \{x_1, x_2, \ldots, x_n\}$ をshatterする とは、Sの点に対する $2^n$ 通りすべてのラベル付けについて、 それを完全に再現する関数が $\mathcal{F}$ の中に少なくとも1つ 存在すること、と定義されます。

この式の二段構えに注目してください。「すべて のラベル付け（$\forall$）に対して、 それを実現する関数が $\mathcal{F}$ の中に少なくとも1つ存在する（$\exists$）」という形になっています。 「すべて」と「少なくとも1つ」の組合せこそが、shatterの厳しさを生んでいます。

しかし4点になると話が変わります——次のセクションで確認しましょう。

4点はshatterできない——VC次元の確定

3点まではうまくいきました。では4点はどうでしょうか。

4点を平面上に「一般の位置」に置く方法は本質的に2通りあります。凸位置（4点が四角形をなす）と非凸位置（3点が三角形をなし、1点がその内部に入る）。 どちらの場合も、直線では実現できないラベル付けが存在します。

たとえば凸位置で、対角の2点を+1、もう一方の対角2点を−1とする「XORパターン」。 1本の直線でこの2組を分離することは不可能です。 直線の片側に+の2点を集めようとすると、必ず−のうち1点も同じ側に入ってしまう。 アニメーションで直線がどんな角度を試しても、赤いリングがついた誤分類点が消えないことを確認してください。

つまり、線形分類器のクラスは 3点はshatterできるが、4点はshatterできない。 このとき、

と書きます。これが VC次元 $h$ の定義です。

VC次元 = 関数クラスがshatterできる最大の点数。

ここで大切なのは「どこかに shatterできるn点配置が1つでも 見つかればOK」ということ。すべての n点配置でshatterできる必要はありません。 たとえば一直線上に並んだ3点は、線形分類器ではshatterできませんが、 一般の位置に置いた3点ならshatterできる。だから「3点shatter可」と認定されます。 あくまで「達成可能な最大点数」がVC次元なのです。

一般に、$\mathbb{R}^p$ 上の線形indicator関数$I(\beta_0 + \beta^\top x > 0)$ のVC次元は $p+1$ です。

VC次元の計算例

VC次元の感覚を掴むため、いくつかの関数クラスでその値を確認しましょう。

アニメーションの3つのパネルが示すように、関数クラスによってVC次元は大きく異なります。

例1: 区間indicator関数

例2: $\mathbb{R}^p$ 上の線形indicator

例3: 正弦関数の符号

この最後の例こそが「パラメータ数 ≠ 複雑度」の決定的証拠です。 VC次元はパラメータ数とは独立に、関数クラスの真の柔軟性を捉えます。

VC次元による汎化誤差の上界

VC次元が単なる「面白い概念」で終わらないのは、これが 汎化誤差の上界 を与えるからです。

訓練誤差 $\overline{\mathrm{err}}$ と 真の予測誤差 $\mathrm{Err}_{\mathcal{T}}$ の差は、 VC次元 $h$ とサンプル数 $N$ で抑えられます。 「失敗確率」を表す小さな数 $\eta$ を1つ決めておきます （たとえば $\eta=0.05$）。 すると 確率 $1-\eta$ 以上 で、次の不等式が成り立ちます：

ここで複雑度項 $\epsilon$ は：

$a_1, a_2$ は定数なので、形だけ見れば十分です。$\epsilon$ は VC次元 $h$ に比例して大きく、 サンプル数 $N$ が大きいほど小さく なります。 つまり「複雑なモデルほどペナルティが重く、データが多いほどペナルティが軽い」という直感そのものです。

アニメーションが示すように、訓練誤差（シアン）はVC次元が増えるほど下がりますが、 複雑度ペナルティ（赤）は急増します。その和である上界（黄）はU字型になり、 ある最適なVC次元で最小値を取ります。

ここから生まれるのが 構造的リスク最小化（SRM） の戦略です。 VC次元が $h_1 < h_2 < h_3 < \cdots$ となるネストされたモデル族を用意し、 訓練誤差 + 複雑度ペナルティが最小になるモデルを選ぶ。 AIC・BIC・MDLと似た形ですが、「パラメータ数」ではなく「VC次元」を使う点が本質的な違いです。

訓練誤差を下げるためにモデルを複雑にすると $h$ が増え、 ペナルティが膨らみます。バランスが取れる最適な複雑度を探すのがSRMの本質です。

VC次元の意義と限界

VC次元理論の威力と限界の両方を、最後に確認しておきましょう。

アニメーションが示すように、VC次元は 線形分類器からSVM、ニューラルネットワークまで、あらゆるモデルに適用できる「普遍的な物差し」です。

威力:

• パラメータ数に頼らず、関数クラスの本質的な複雑度を測れる
• 訓練誤差だけでなく汎化誤差を 理論的に保証 できる（確率的な上界）
• ニューラルネット、SVM、決定木など、現代の手法のVC次元解析が機械学習理論の中核となった

限界:

• VC次元の 正確な計算は多くのモデルで困難。たとえばニューラルネットのVC次元は、重みの個数だけでは決まらない
• 式7.46の上界は しばしば緩い。実際の汎化性能をピタリと当てる予測値にはなりにくい
• 「最悪ケース」を保証する理論なので、典型的なデータ分布のもとでの挙動とはズレる

それでも、VC次元は 「複雑度とは何か」を初めて数学的に定式化した という意味で、 機械学習理論の出発点となりました。AdaBoost、SVM、深層学習などの後の発展は、 すべてこのフレームの上で議論されています。

VC次元は、学習理論の中で「複雑度」という曖昧な概念に初めて明確な数学的意味を与えました。