VC次元
概要
VC次元（VC dimension）とは、集合 $X$ の部分集合の族 $\mathcal F$ について、$\mathcal F$ との共通部分としてすべての部分集合を切り出せる（打ち砕かれる）有限集合の元の個数の最大値である。実数直線の半直線の族は $1$、区間の族は $2$、平面の半平面の族は $3$、$\mathbb{R}^n$ の半空間の族は $n+1$ で、平面の凸集合の族は無限である。VC 次元が有限なら、$n$ 点の上に現れる跡の個数は $n$ の多項式で抑えられ（Sauer–Shelah の補題）、ランダムに選んだ少数の点が ε-ネットになること（Haussler–Welzl）、0-1 損失での PAC 学習可能性と一様収束性が同値であることの鍵になる。
平面に 3 点をとる。3 点が一直線上になければ、8 通りあるどの部分集合も「ある半平面に入る点の全体」として切り出せる。ところが 4 点になると、どう置いても切り出せない部分集合が必ずある。集合の族が有限集合を「どこまで細かく切り分けられるか」を 1 つの整数で測るのが VC 次元（Vapnik–Chervonenkis dimension）である。この量は Vapnik と Chervonenkis による、事象の相対頻度が確率に一様に近づくための条件の研究に始まり（HW87 pp. 131、133）、計算幾何学の ε-ネット、統計的学習理論の PAC 学習、モデル理論の NIP 理論で、それぞれ中心的な役割を果たしている。
この記事では、打ち砕くことと VC 次元を定義し、半直線・区間・半平面・軸に平行な長方形の VC 次元を求め、平面の凸集合の族の VC 次元が無限であることを示す。そのうえで、VC 次元が有限なら成長関数が多項式で抑えられること、ε-ネット定理（Haussler–Welzl）、学習理論の基本定理の主張と所在を述べる。
定義
$X$ を集合、$\mathcal F$ を $X$ の部分集合からなる空でない族とする。$A\subset X$ について
$$
\mathcal F|_A:=\{A\cap F\mid F\in\mathcal F\}
$$
を $\mathcal F$ の $A$ への 跡（trace）という。
- 有限集合 $A\subset X$ が $\mathcal F|_A=2^A$（$A$ の 冪集合）をみたすとき、$\mathcal F$ は $A$ を 打ち砕く（shatter）という。すなわち、$A$ のどの部分集合 $B$ にも、$A\cap F=B$ となる $F\in\mathcal F$ がある。
- $\mathcal F$ が打ち砕く有限集合の元の個数の最大値を $\mathcal F$ の VC 次元 といい、$\operatorname{VC}(\mathcal F)$ と書く。いくらでも大きい有限集合を打ち砕くときは $\operatorname{VC}(\mathcal F)=\infty$ とする。
- 自然数 $n$ について $\pi_{\mathcal F}(n):=\max\{\lvert\mathcal F|_A\rvert\mid A\subset X,\ \lvert A\rvert=n\}$ を $\mathcal F$ の 成長関数（shatter function）という（$\lvert X\rvert\ge n$ のときに考える）。
空集合はつねに打ち砕かれるので $\operatorname{VC}(\mathcal F)\ge0$ である。「打ち砕く」は「粉砕する」ともいう。定義は HW87 §3（p. 131）の range space $(X,\mathcal R)$ の次元と同じである。$\operatorname{VC}(\mathcal F)=d$ を示すには、$d$ 元の集合で打ち砕かれるものを 1 つ挙げ、$d+1$ 元の集合はどれも打ち砕かれないことを示せばよい。
- $\mathcal F$ が $A$ を打ち砕けば、$A$ の部分集合もすべて打ち砕く。
- $\mathcal F\subset\mathcal G$ なら $\operatorname{VC}(\mathcal F)\le\operatorname{VC}(\mathcal G)$ である。
- $\mathcal F$ が有限なら $\operatorname{VC}(\mathcal F)\le\log_2\lvert\mathcal F\rvert$ である。
- 補集合の族 $\mathcal F^c:=\{X\setminus F\mid F\in\mathcal F\}$ について $\operatorname{VC}(\mathcal F^c)=\operatorname{VC}(\mathcal F)$ である。
- $\operatorname{VC}(\mathcal F)$ は、有限集合 $A$ を動かしたときの $\operatorname{VC}(\mathcal F|_A)$（$\mathcal F|_A$ は $A$ の部分集合の族）の最大値に等しい。
1：$B\subset A$、$C\subset B$ とする。$A\cap F=C$ となる $F$ をとれば $B\cap F=C$ である。2：$\mathcal F$ が打ち砕く集合は $\mathcal G$ も打ち砕く。3：$d$ 元の集合を打ち砕くには、跡が $2^d$ 個の異なる集合になるので $\mathcal F$ に $2^d$ 個以上の元が要る。4：$A\cap(X\setminus F)=A\setminus(A\cap F)$ なので、$B\mapsto A\setminus B$ により $\mathcal F|_A$ と $\mathcal F^c|_A$ は 1 対 1 に対応し、$\mathcal F$ が $A$ を打ち砕くことと $\mathcal F^c$ が $A$ を打ち砕くことは同値である。5：$B\subset A$ について $(\mathcal F|_A)|_B=\mathcal F|_B$ なので、$\mathcal F|_A$ が打ち砕く集合は、$A$ に含まれる集合のうち $\mathcal F$ が打ち砕くものにほかならない。$\square$
例
| $X$ | $\mathcal F$ | $\operatorname{VC}(\mathcal F)$ | 根拠 |
|---|---|---|---|
| $\mathbb R$ | 半直線 $(-\infty,t]$ の全体 | $1$ | ex-vc-line |
| $\mathbb R$ | 有界閉区間 $[a,b]$ の全体 | $2$ | ex-vc-line |
| $\mathbb R$ | $k$ 個以下の有界閉区間の和集合の全体 | $2k$ | ex-vc-k-intervals |
| $\mathbb R^2$ | 閉半平面の全体 | $3$ | ex-vc-halfplane |
| $\mathbb R^n$ | 閉半空間の全体 | $n+1$ | ex-vc-halfplane |
| $\mathbb R^2$ | 辺が座標軸に平行な閉長方形の全体 | $4$ | ex-vc-rectangle |
| $\mathbb R^2$ | 凸集合の全体 | $\infty$ | ex-vc-convex |
| 無限集合 | 有限部分集合の全体 | $\infty$ | 任意の有限集合 $A$ について $A\cap B=B$（$B\subset A$） |
$\mathbb R$ の半直線 $(-\infty,t]$ の族の VC 次元は $1$、有界閉区間の族の VC 次元は $2$ である。
半直線：$\{x\}$ は $t=x$ と $t=x-1$ で打ち砕かれる。$x< y$ のとき、$y\le t$ なら $x\le t$ なので、跡が $\{y\}$ になる半直線はない。
区間：$x< y$ の 2 点は、$[x-2,x-1]$、$[x,x]$、$[y,y]$、$[x,y]$ で打ち砕かれる。$x< y< z$ のとき、$x,z\in[a,b]$ なら $y\in[a,b]$ なので、跡が $\{x,z\}$ になる区間はない。
$k\ge1$ とし、$\mathcal F_k$ を $k$ 個以下の有界閉区間の和集合の全体とすると $\operatorname{VC}(\mathcal F_k)=2k$ である（$\{1,\dots,s\}$ の上での同じ計算が HW87 Theorem 3.8 の証明（p. 137）にある）。
要点：$2k$ 点のどの部分集合も「連続する塊」が $k$ 個以下になり、$2k+1$ 点の 1 つおきの $k+1$ 点は塊が $k+1$ 個になる。
詳しい証明を開く
$x_1< \cdots< x_{2k}$ とし、$B\subset\{x_1,\dots,x_{2k}\}$ をとる。$B$ を、添字が連続する極大な塊 $\{x_p,x_{p+1},\dots,x_q\}$ に分ける。塊が $r$ 個あれば、塊と塊の間に $B$ に入らない点が少なくとも 1 つずつあるので $r+(r-1)\le 2k$、すなわち $r\le k$ である。各塊 $\{x_p,\dots,x_q\}$ を区間 $[x_p,x_q]$ で覆えば、和集合の跡は $B$ になる（$B=\emptyset$ なら $x_1$ より左の区間を 1 つとる）。よって $2k$ 点は打ち砕かれる。
逆に $x_1< \cdots< x_{2k+1}$ とし、$B:=\{x_1,x_3,\dots,x_{2k+1}\}$（$k+1$ 点）とする。区間 $I$ が $x_{2i-1}$ と $x_{2j-1}$（$i< j$）をともに含めば $x_{2i}$ も含む。よって跡が $B$ になる和集合では、各区間は $B$ の点を高々 1 つしか含まず、$k+1$ 個以上の区間が要る。$\square$
$\mathbb R^n$ の閉半空間 $\{x\mid a\cdot x\le b\}$（$a\ne0$）の族の VC 次元は $n+1$ である。とくに平面の閉半平面の族の VC 次元は $3$ である。
実際、Radonの定理(凸幾何) の命題「半空間による切り分け」により、$n+1$ 個のアフィン独立な点はどの分け方も半空間で切り分けられるので打ち砕かれ、$n+2$ 個以上の点には半空間で切り分けられない分け方（Radon 分割）があるので打ち砕かれない。平面では、一直線上にない 3 点は打ち砕かれるが、一直線上の 3 点は打ち砕かれない（真ん中の点を除いた 2 点は、凸集合である半平面に入れば真ん中の点も入る）。VC 次元は「打ち砕かれる集合が 1 つある」ことで決まるので、これは $\operatorname{VC}=3$ と矛盾しない。
辺が座標軸に平行な閉長方形 $[a,b]\times[c,d]$ の族の VC 次元は $4$ である。
要点：菱形の 4 頂点は打ち砕かれ、5 点では、上下左右の端の点だけを含む長方形が残りの点も含んでしまう。
詳しい証明を開く
$P:=\{(1,0),(-1,0),(0,1),(0,-1)\}$ とし、$B\subset P$ をとる。$B$ の点の $x$ 座標の最小・最大を $a,b$、$y$ 座標の最小・最大を $c,d$ とすると、長方形 $[a,b]\times[c,d]$ は $B$ を含む。$P\setminus B$ の点、たとえば $(1,0)\notin B$ なら、$B\subset\{(-1,0),(0,\pm1)\}$ なので $b\le0< 1$ となり、$(1,0)$ は含まれない。ほかの 3 点も同様なので、跡はちょうど $B$ である（$B=\emptyset$ なら遠くの長方形をとる）。
5 点の集合 $Q$ をとる。$x$ 座標が最小・最大の点、$y$ 座標が最小・最大の点を 1 つずつ選び、その集合を $E$（4 点以下）とすると、$E$ に入らない $q\in Q$ がある。$E$ を含む長方形は、$Q$ の $x$ 座標と $y$ 座標の最小値から最大値までを含むので $q$ も含む。よって跡が $E$ になる長方形はなく、$Q$ は打ち砕かれない。$\square$
平面の凸集合の族の VC 次元は $\infty$ である（HW87 Example 4、p. 132）。円周上に相異なる $n$ 点 $A$ をとり、$B\subset A$ に $B$ の凸包 $\operatorname{conv}B$ を対応させる。$p\in A\setminus B$ とし、$p$ での接線を境界とする開半平面のうち円の中心を含むものを $H$ とすると、周を含む円板から $p$ を除いた部分は $H$ に含まれる。$B\subset H$ で $H$ は凸なので $\operatorname{conv}B\subset H$ であり、$p\notin H$ だから $p\notin\operatorname{conv}B$ である。よって $A\cap\operatorname{conv}B=B$ で、$A$ は打ち砕かれる。
成長関数の二分法
$\Phi_d(n):=\sum_{i=0}^{d}\binom ni$ と書く（$\binom ni$ は二項係数、$i>n$ では $0$）。
$\mathcal F$ を集合 $X$ の部分集合の空でない族とする。
- $\operatorname{VC}(\mathcal F)=\infty$ なら、すべての $n$ について $\pi_{\mathcal F}(n)=2^n$ である。
- $\operatorname{VC}(\mathcal F)=d< \infty$ なら、すべての $n$ について $\pi_{\mathcal F}(n)\le\Phi_d(n)$ であり、$n\ge d\ge1$ では $\pi_{\mathcal F}(n)\le(en/d)^d$ である。
1：どの $n$ にも打ち砕かれる $n$ 元集合 $A$ があり、$\lvert\mathcal F|_A\rvert=2^n$ である。2：$\lvert A\rvert=n$ とすると、prop-vc-basic の 5 により $\mathcal F|_A$ は $A$ の部分集合の族で VC 次元が $d$ 以下なので、Sauer–Shelahの補題 の定理「Sauer–Shelah の補題」により $\lvert\mathcal F|_A\rvert\le\Phi_d(n)$ である。後半は同じ記事の命題「二項係数の和の評価」による。$\square$
VC 次元が有限な族では、$n$ 点の上に現れる跡の個数が $2^n$ ではなく $n$ の多項式の程度にとどまる。区間の族では $\pi(n)=\Phi_2(n)=1+n+\binom n2$ となって等号が成り立つ（Sauer–Shelahの補題 の例「等号の例」）。ε-ネット定理と学習理論の基本定理は、どちらもこの多項式の増え方を確率の評価と組み合わせて証明される。
ε-ネット定理
$A\subset X$ を空でない有限集合、$0< \varepsilon< 1$ とする。$N\subset A$ が、$\lvert A\cap F\rvert>\varepsilon\lvert A\rvert$ をみたすすべての $F\in\mathcal F$ と交わるとき、$N$ を $A$ の $\mathcal F$ についての ε-ネット という（HW87 §3、p. 134）。
ε-ネットは「大きい集合を必ず突き刺す少数の点」である。$A$ 自身はつねに ε-ネットなので、問題は $\lvert A\rvert$ によらない大きさの ε-ネットがあるかどうかである。
$A\subset\mathbb R$ を $n$ 点の集合とし、$\mathcal F$ を有界閉区間の族とすると、$A$ には $1/\varepsilon$ 個未満の点からなる ε-ネットがある。
$A=\{a_1< \cdots< a_n\}$、$k:=\lfloor\varepsilon n\rfloor+1$ とし、$N:=\{a_k,a_{2k},a_{3k},\dots\}$ とする。区間 $I$ が $A$ の点を $\varepsilon n$ 個より多く、したがって $k$ 個以上含めば、それらは添字の連続する $k$ 個の点 $a_p,\dots,a_{p+k-1}$ を含み、その中に $k$ の倍数の添字が 1 つあるので $I$ は $N$ と交わる。$\lvert N\rvert=\lfloor n/k\rfloor\le n/k< n/(\varepsilon n)=1/\varepsilon$ である。$\square$
区間の族の VC 次元は $2$ なので、これは次の定理の特別な場合の、より良い評価にあたる。一般の場合は無作為に点を選ぶ。
$\operatorname{VC}(\mathcal F)=d$（$1\le d< \infty$）、$A\subset X$ を空でない有限集合、$0< \varepsilon,\delta< 1$ とする。$A$ から一様に、独立に、重複を許して
$$
m\ge\max\Bigl(\frac4\varepsilon\log_2\frac2\delta,\ \frac{8d}\varepsilon\log_2\frac{8d}\varepsilon\Bigr)
$$
回選んだ点の集合 $N$ は、確率 $1-\delta$ 以上で $A$ の $\mathcal F$ についての ε-ネットである。とくに $A$ には $\lceil(8d/\varepsilon)\log_2(8d/\varepsilon)\rceil$ 個以下の点からなる ε-ネットがある。
HW87 Corollary 3.7（p. 136）と Theorem 3.8（p. 137）である（同論文の対数は底 $2$、p. 130。この記事では証明しない）。証明は、選んだ $m$ 点のほかに $m$ 点を選び直し、「最初の $m$ 点を避ける大きい集合」の事象を $2m$ 点の並べ替えの数え上げに移して、跡の個数を thm-vc-dichotomy の $\Phi_d(2m)$ で抑えるものである（同 Lemma 3.4・3.5、Theorem 3.6）。大きさの上界は $\lvert A\rvert$ によらない。同じ Theorem 3.8 は逆向きの評価として、VC 次元 $d$ の族と有限集合 $A$ で、ε-ネットに $\lfloor d/2\rfloor/\varepsilon-1$ 個以上の点が要るものがあることも示している。その証明は ex-vc-k-intervals の族を有限集合の上で使う。
VC 次元が無限なら、大きさが $\lvert A\rvert$ によらない ε-ネットは一般にない。円周上の $n$ 点 $A$ と凸集合の族では、$N\subset A$ に対して $\operatorname{conv}(A\setminus N)$ は $A$ の点を $n-\lvert N\rvert$ 個含み $N$ と交わらない（ex-vc-convex）。よって ε-ネットは $\lvert N\rvert\ge(1-\varepsilon)n$ をみたさなければならない。
学習理論での一様収束
$X$ を集合、$\mathcal H$ を関数 $X\to\{0,1\}$ の族（仮説の族）とし、$\operatorname{VC}(\mathcal H)$ は rem-vc-functions の意味で考える。$X\times\{0,1\}$ 上の確率分布 $D$ について、$h$ の誤り率を $L_D(h):=D(\{(x,y)\mid h(x)\ne y\})$ とする。$D$ から独立に選んだ標本 $S=((x_1,y_1),\dots,(x_m,y_m))$ について、標本上の誤り率を $L_S(h):=\frac1m\lvert\{i\mid h(x_i)\ne y_i\}\rvert$ とする。すべての $h\in\mathcal H$ で $\lvert L_S(h)-L_D(h)\rvert\le\varepsilon$ となる標本を ε-代表的（ε-representative）という。$L_S$ を最小にする $h\in\mathcal H$ を返す規則を 経験リスク最小化（ERM）という。
- $\mathcal H$ が 一様収束性 をもつとは、関数 $m_{\mathrm{UC}}\colon(0,1)^2\to\mathbb N$ があって、任意の $\varepsilon,\delta\in(0,1)$ と $X\times\{0,1\}$ 上の任意の確率分布 $D$ について、$m\ge m_{\mathrm{UC}}(\varepsilon,\delta)$ 個の独立な標本が確率 $1-\delta$ 以上で ε-代表的になることをいう。
- $\mathcal H$ が 不可知 PAC 学習可能（agnostic PAC learnable）とは、関数 $m_{\mathcal H}\colon(0,1)^2\to\mathbb N$ と、標本から $X\to\{0,1\}$ の関数を返す手続き $\mathcal A$ があって、任意の $\varepsilon,\delta$ と任意の $D$ について、$m\ge m_{\mathcal H}(\varepsilon,\delta)$ 個の独立な標本 $S$ に対し確率 $1-\delta$ 以上で $L_D(\mathcal A(S))\le\inf_{h\in\mathcal H}L_D(h)+\varepsilon$ となることをいう。
- 2 の条件を、ある $h\in\mathcal H$ について $L_D(h)=0$ となる $D$（実現可能な場合）に限って要求したものを PAC 学習可能 という。
これは SSBD14 Definition 3.1、3.3、4.1、4.3 を確率分布の言葉でまとめたものである（同書は事象の可測性を仮定して議論する。Remark 3.1）。
標本 $S$ が $\varepsilon/2$-代表的なら、ERM の出力 $h_S$ は $L_D(h_S)\le\inf_{h\in\mathcal H}L_D(h)+\varepsilon$ をみたす。とくに一様収束性をもつ $\mathcal H$ は、ERM によって不可知 PAC 学習可能である。
任意の $h\in\mathcal H$ について、代表性、$h_S$ が $L_S$ を最小にすること、代表性をこの順に使うと
$$
L_D(h_S)\le L_S(h_S)+\tfrac\varepsilon2\le L_S(h)+\tfrac\varepsilon2\le L_D(h)+\varepsilon
$$
である。$h$ について下限をとればよい。後半は $m_{\mathcal H}(\varepsilon,\delta):=m_{\mathrm{UC}}(\varepsilon/2,\delta)$ とおけばよい。$\square$
誤り率を上のとおり $0$-$1$ 損失で測るとき、$X\to\{0,1\}$ の関数の族 $\mathcal H$ について次は同値である。
- $\mathcal H$ は一様収束性をもつ。
- ERM の規則はどれも $\mathcal H$ の不可知 PAC 学習の手続きになる。
- $\mathcal H$ は不可知 PAC 学習可能である。
- $\mathcal H$ は PAC 学習可能である。
- ERM の規則はどれも $\mathcal H$ の PAC 学習の手続きになる。
- $\operatorname{VC}(\mathcal H)< \infty$ である。
さらに $\operatorname{VC}(\mathcal H)=d< \infty$ なら、$\mathcal H$ によらない定数 $C_1,C_2>0$ があって、1 と 3 に必要な最小の標本数 $m(\varepsilon,\delta)$ はどちらも
$$ C_1\,\frac{d+\log(1/\delta)}{\varepsilon^2}\le m(\varepsilon,\delta)\le C_2\,\frac{d+\log(1/\delta)}{\varepsilon^2} $$
をみたし、4 に必要な最小の標本数は $C_1\frac{d+\log(1/\delta)}{\varepsilon}$ 以上、$C_2\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}$ 以下である。
SSBD14 Theorem 6.7 と Theorem 6.8（§6.4）である（この記事では証明しない）。$1\Rightarrow2$ は lem-vc-erm、$2\Rightarrow3\Rightarrow4$ と $2\Rightarrow5$ は定義から従う。$4\Rightarrow6$ と $5\Rightarrow6$ は、$\mathcal H$ が $2m$ 点を打ち砕けば、$m$ 個の標本ではどの手続きも、ある実現可能な分布で確率 $1/7$ 以上、誤り率が $1/8$ 以上になる（同 Corollary 6.4、Theorem 6.6）ことによる。難しいのは $6\Rightarrow1$ で、thm-vc-dichotomy の多項式の評価に確率の評価を組み合わせて示される（同 §6.5）。
反例：条件を外すと成り立たない
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-vc-epsilon-net の「VC 次元が有限」 | 平面の凸集合の族と円周上の $n$ 点 | ε-ネットの大きさが $\lvert A\rvert$ によらないこと（$(1-\varepsilon)n$ 点以上が要る） |
| thm-vc-fundamental の 6（VC 次元が有限） | 平面の凸集合の指示関数の族 | PAC 学習可能であること（SSBD14 Theorem 6.6） |
| prop-vc-basic の 3 の「$\mathcal F$ が有限」 | 無限集合の有限部分集合の全体 | VC 次元が有限であること |
関連項目
- 前提: 集合族, 冪集合, 有限集合
- 直後に読む: Sauer–Shelahの補題
- 例: Radonの定理(凸幾何), 凸包
- 比較: 大数の法則, 安定性理論
- 発展: 組合せ幾何学, 組合せ論
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
