本記事は総研大アドベントカレンダー2025 & 統計科学コースアドベントカレンダー2025、6日目の記事です。
私は総研大統計科学コースの5年一貫制博士課程の1年生（いわゆるM1）です。
輪読している本にVC次元が登場し、その値を考えることにパズル的な楽しさがあったので、共有しようと思います。定義を解説した後に、例や問題をいくつか載せるので、ぜひ考えてみてください！
前提知識はほとんどありません。数学にある程度親しみがあれば高校生でも取り組めると思います！
VC次元とは？
背景
※背景に興味がなければ読む必要はありません。次節から読めば問題が解けるようになります。
VC次元は、機械学習の理論で「モデルの複雑さ」を測るために使われる指標です。与えられた入力 $x$ に対して、2つのラベルのうちどちらをつけるか、という問題（2値判別問題）を考えます。具体的な設定としては、例えば
- $x$: メール、ラベル: スパムか、そうでないか
- $x$: 医療画像、ラベル: 疾患があるか、ないか
などが考えられます。
入力が取りうる値全体を $\mathcal{X}$、ラベルを $0,1$ で表すことにします。機械学習の目的は、既知のデータ $\{(x_i,t_i)\}_{i=1,\dots,n}$（$x_i \in \mathcal{X}$、$t_i \in \{0,1\}$）から学習して、未知の入力に対してもうまく分類してくれるような判別機 $h:\mathcal{X} \to \{0,1\}$ を作ることです。現実的には、判別機の候補を予め決めておいて、その中から最も優れたものを選びます。判別機の候補全体を $\mathcal{H}$ で表して、「仮説クラス」などと呼びます。
それでは、どのような $\mathcal{H}$ を用意するのが良いのでしょうか？直感的には用意する判別機の候補は多ければ多いほど良いように思えます。それだけ表現できるラベルの付け方が増えるからです。しかしそこには「過学習」という危険性が潜んでいるのです。というのも、現実に得られる既知のデータは有限です。そのため、判別機の候補があまりにも多いと、「そのデータにだけ異常によく当てはまる」ものを選んでしまうかも知れません。そうした判別機は、未知のデータにはうまく対応できないことがあります。
以上の考察から、$\mathcal{H}$ は"程よく"大きいものを選ぶべし、という洞察が得られました。これを実践するためには $\mathcal{H}$ の「大きさ」あるいは「複雑さ」のようなものを定量的に測る指標が必要です。VC次元は、その評価指標の一つです。
VC次元の定義
あらためて、数学的な設定は次のとおりです:
- 入力値全体: $\mathcal{X}$
- ラベル: $\{0,1\}$
- 判別機とは、関数 $h: \mathcal{X} \to \{0,1\}$ のこと
- 判別機の候補全体（仮説クラス）: $\mathcal{H}$
VC次元の定義をするために、用語の準備をします。
【定義】shatter
点列 $X = \{x_1,\dots,x_n\} \subset \mathcal{X}$ が $\mathcal{H}$ によってshatterされるとは、任意のラベル $(t_1,\dots,t_n) \in \{0,1\}^n$ について、$h(x_i) = t_i$ をみたす $h \in \mathcal{H}$ が存在すること。
解説
わかりやすさのために $n = 3$ としましょう。点列 $X = \{x_1,x_2,x_3\}$ を考えます。このとき、この3点に対するラベルの付け方は $2^3 = 8$ 通りあります: $$ (0,0,0), \, (0,0,1), \, (0,1,0),\, (1,0,0),\, (0,1,1),\, (1,0,1),\, (1,1,0),\, (1,1,1). $$ 仮説クラス $\mathcal{H}$ がこの3点集合 $X$ をshatterするとは、上で列挙した8通りすべてのラベル付けに対して、そのラベル付けを実現するような $h \in \mathcal{H}$ が存在することに他なりません。例えばラベル $(t_1,t_2,t_3) = (1,0,1)$ に対しては、$h_{(101)} \in \mathcal{H}$ という判別機が存在して、 $$ h_{(101)}(x_1) = 1, \quad h_{(101)}(x_2) = 0, \quad h_{(101)}(x_3) = 1 $$ をみたす、という具合です。言葉で説明するなら、$\mathcal{H}$ が $X = \{x_1,\dots,x_n\}$ をshatterできることは「この $n$ 個の点については、$\mathcal{H}$ はどんなラベルの付け方も表現できる」ということです。このため、ある集合をshatterできるか否かを $\mathcal{H}$ の表現力を測る指標として使うことが考えられます。
【定義】VC次元
$\mathcal{H}$ のVC次元 $V(\mathcal{H})$ とは、shatterすることのできる点列 $X \subset \mathcal{X}$ の元の数の最大値。
解説
$\mathcal{H}$ が要素数が $n$ の「ある」点列をshatterできれば、$n \leq V(\mathcal{H})$ です。逆に、要素数が $m$ の「すべての」点列をshatterできないなら、$V(\mathcal{H}) < m$ となります。少し抽象的な話が続きましたが、以上で準備は終了です！shatter/VC次元という概念を理解するには、以下の例や問題を通じて慣れていくのが近道かもしれません。
チュートリアル
例題（自明な例1）
$\mathcal{X}$: 任意の集合、$\mathcal{H} = \{1 \,(\text{定数関数})\}$ のときの $V(\mathcal{H})$ は？
解答
$V(\mathcal{H}) = 0$。要素数1の点列 $\{x_1\}$ について、あり得るラベルは $t_1 = 0,1$ の2通りですが、$t_1 = 0$ を実現できません。例題（自明な例2）
$\mathcal{X}$: 任意の集合、$\mathcal{H} = \{0, 1\, (\text{定数関数})\}$ のときの $V(\mathcal{H})$ は？
解答
$V(\mathcal{H}) = 1$。要素数1の点列 $\{x_1\}$ について、あり得るラベルの $t_1 = 0,1$ のどちらも、それぞれに対応する定数関数によって実現できます。一方、要素数2の点列に対するラベルのうち、表現できるのは $(t_1,t_2) = (0,0),(1,1)$ のみであり、$(1,0),(0,1)$ は表現できません。
例題（1次元のステップ関数）
$\mathcal{X} = \mathbb{R}$、$\mathcal{H} = \{h_\theta(x) = 1\{\theta \leq x\} \mid \theta \in \mathbb{R}\}$ のときの $V(\mathcal{H})$ は？
ただし、$1\{\theta \leq x\}$ は、$\theta \leq x$ のとき1、それ以外で0という指示関数とします（以降もこのような記法を用います）。
解答
$V(\mathcal{H}) = 1$。まず、要素数1の点列 $\{ x_1 \}$ について、あり得るラベルの $t_1 = 0$ は $h_{x_1+1} (x_1) = 0$、$t_1 = 1$ は $h_{x_1 - 1}(x_1) = 1$ のようにして実現できます。一方、$\mathcal{H}$ はどんな要素数2の点列 $\{ x_1,x_2 \}$（$x_1 < x_2$）もshatterできません。あり得るラベルのうち、$(t_1,t_2) = (1,0)$ を表せないからです（図を参照）。実際、$h_\theta (x_1) = 1$ のためには $\theta \leq x_1$ でなければいけませんが、$\theta \leq x_1 < x_2$ なので、必然的に $h_\theta(x_2) = 1$ となってしまいます。
最後の例のように、適当に $n$ 個の点列を配置し、色々な $h \in \mathcal{H}$ によって空間 $\mathcal{X}$ を $h$ が $1$ を返す部分と $0$ を返す部分で分割して、$2^n$ 個のラベルづけを実現できるか、を考えてみるとわかりやすいかもしれません。
VC次元クイズ
チュートリアルが終わったところで、いよいよ問題です！大体これくらいかな？と目星をつけるところまででも、ぜひ考えてみてください！
問題1（区間）：難易度☆
$\mathcal{X} = \mathbb{R}$、$\mathcal{H} = \{h_{l,r}(x) = 1\{l \leq x \leq r\} \mid l \leq r,\, l, r \in \mathbb{R} \}$ のときの $V(\mathcal{H})$ は？
解答
$V(\mathcal{H}) = 2$（図を参照）。
要素数3の集合はshatterできないことを示します。$X=\{x_1,x_2,x_3\}$（$x_1 < x_2 < x_3$）とします。このとき、ラベル $(t_1,t_2,t_3) = (1,0,1)$ を実現できません。なぜなら、$t_1=1$ のためには $l \leq x_1$、$t_3 = 1$ のためには $x_3 \leq r$ が必要ですが、このとき $l \leq x_2 \leq r$ で、$h_{l,r}(x_2) = 1$ となってしまいます。
問題2（2次元平面上の半無限矩形）：難易度☆☆
$\mathcal{X} = \mathbb{R}^2$、$\mathcal{H} = \{h_{x_0,y_0}(x,y) = 1\{x \leq x_0, \, y\leq y_0\} \mid (x_0,y_0) \in \mathbb{R}^2 \}$ のときの $V(\mathcal{H})$ は？
解答
$V(\mathcal{H}) = 2$（図を参照）。
要素数3の集合はshatterできないことを示します。3点のうち、$x$ 座標が最大の点と、$y$ 座標が最大の点の他に、少なくとも1点、そのどちらでもない点 $(x_j,y_j)$ が存在します。この点を0、その他の点を1とするラベルは実現できません。なぜなら、このとき $x_\max \leq x_0$、$y_\max \leq y_0$ である必要がありますが、$x_j \leq x_\max$、$y_j \leq y_\max$ であるため、$x_j \leq x_0$ かつ $y_j \leq y_0$ となって、必然的にラベルは1になってしまいます。
問題3（2次元平面上の矩形）：難易度☆☆+α
$\mathcal{X} = \mathbb{R}^2$、$\mathcal{H} = \{h_{l_x,r_x,l_y,r_y}(x,y) = 1\{l_x \leq x \leq r_x, \, l_y \leq y \leq r_y\} \mid l_x,l_y,r_x,r_y \in \mathbb{R} \}$ のときの $V(\mathcal{H})$ は？
解答
$V(\mathcal{H}) = 4$（要素数4の集合は、例えば十字状に4点を配置するとshatterできます）。要素数5の集合はshatterできないことを示します。といっても、考え方は前の問題と同じです。5点のうち、$x$ 座標最小・最大、$y$ 座標最小・最大の点の他に、少なくとも一点そのどれでもない点 $(x_j,y_j)$ が存在します。この点を0、その他の点を1とするラベルは実現できません。問題4（2次元平面上の直線）：難易度☆☆☆
$\mathcal{X} = \mathbb{R}^2$、$\mathcal{H} = \{h_{\boldsymbol{w},b}(\boldsymbol{x}) = 1\{\boldsymbol{w}^\top \boldsymbol{x} + b \geq 0\} \mid \boldsymbol{w} \in \mathbb{R}^2,\, b \in \mathbb{R} \}$ のときの $V(\mathcal{H})$ は？
解答
$V(\mathcal{H}) = 3$。要素数4の集合はshatterできないことを示します。判別機である直線（$\boldsymbol{w}^\top \boldsymbol{x} + b = 0$ で表される直線）のことを $l$ と呼びます。まず、重要な考察として、
- 2点A, Bに同じラベルをつけるとき、$l$ は線分ABの内部（ABから端点を除いたもの）と1点では交わらない
- 2点A, Bに違うラベルをつけるとき、$l$ は線分ABと1点で交わる
ことがわかります。
さて、2次元平面上の4点の配置は、次のように場合分けできます:
① 3点以上が直線上にある
② 4点が凸四角形をなす
③ 3点がなす三角形の内部に1点がある
まず①の場合、点A, B, Cが同一直線上にあり、$x$ 座標の値がこの順であるとします（対称性から一般性を失いません）。このとき、A, Cに1、Bに0をつけるようなラベルは実現できません。なぜなら、A, Bに異なるラベルをつけるためには、$l$ はABと1点で交わらなければいけませんが、A, Cには同じラベルをつけるため、ACの内部とは1点で交われません。したがって $l$ はAと一点で接するしかありませんが、このときB, Cは同じラベルになります。
②の場合、凸四角形の頂点を反時計回りにABCDとします。向かい合う頂点A, Cに1、B, Dに0とつけるようなラベルは実現できません。ラベルが同じ頂点の制約から、$l$ は線分AC、BDの内部と1点で交われないため、結果として $l$ は凸四角形ABCDの内部と交われません。一方ラベルが異なる頂点の制約から、$l$ はAと接して、かつCと接する必要がありますが、これは不可能です。
③の場合、三角形をABC、内部の点をDとします。A, B, Cに1、Dに0とつけるようなラベルは実現できません。②の考察と同様にして $l$ はABCの内部と交われず、一方でA, B, Cと接する必要があるのですが、もちろんこれは不可能です。
まとめ
VC次元クイズ、楽しんでいただけたでしょうか？
本当はもっと色々な問題を紹介したかったのですが、想像以上に分量が増えてしまい、今回はここまでとしました。物足りないようでしたら、ぜひ応用編として自分だけのVC次元クイズを作ってみてください！
参考文献など
- [1] A. W. van der Vaart, Asymptotic Statistics, Cambridge University Press, 1998.
- 19章で、uniform covering numberという概念を用いる具体例としてVC index（この記事とは少し定義が違います）が登場しました。定義の直接的な参照先はここです。
- [2] 鈴木大慈, 統計的学習理論とその深層学習への応用, 応用数理, 28(4): 28-33, 2018. https://www.jstage.jst.go.jp/article/bjsiam/28/4/28_28/_article/-char/ja, (参照:2025-12-02)
- VC次元の背景〜定義を書くために参考にしました。