読者です 読者をやめる 読者になる 読者になる

Sauer-Shelah Lemma

Vapnik-Chervonekis-Sauer-Shelah Lemmaともいう.いわゆる極値組合せ論の定理.機械学習のVC次元等に応用がある(らしい).

集合 $E$ の部分集合族 $\mathcal{F}$ が集合 $S \subseteq E$ を shutter するとは,任意の $X \subseteq S$ に対して $S \cap F = X$ となる $F \in \mathcal{F}$ が存在するときにいう.

Vapnik-Chervonekis-Sauer-Shelah Lemma

$\mathcal{F}$ が $|\mathcal{F}| > \binom{n}{0} + \dots + \binom{n}{k} $ を満たすならば,$\mathcal{F}$ にshutterされる $S$ で $|S| \geq k+1$ となるものが存在する.

[証明] すこしだけ強い次の主張(Pajorによる)を示す:

Claim: 任意の集合族 $\mathcal{F}$ は 少なくとも $|\mathcal{F}|$ 個の集合をshutterする.

これは $n=|E|$ に関する帰納法で示せる.$n=1$のときは自明.$n > 1$ とし,$e \in E$ を任意に固定する.
\begin{align}
\mathcal{F}_1 &:= \{F \in \mathcal{F} : e \notin F\}, \\
\mathcal{F}_2 &:= \{F\setminus e : F \in \mathcal{F}, e \in F\}
\end{align}
とする.すると,帰納法の仮定から $\mathcal{F}_i$ は少なくとも $|\mathcal{F}_i|$ 個の $E\setminus e$の部分集合をshutterする.

また,$\mathcal{F}_1$と$\mathcal{F}_2$の両方にshutterされる $S \subseteq E \setminus e$ を考えると,$\mathcal{F}$ は $S \cup e$ をshutterすることが確認できる.よって,数え上げの議論によって $\mathcal{F}$ は少なくとも $|\mathcal{F}_1| + |\mathcal{F}_2| = |\mathcal{F}|$ 個の集合をshutterする.■

参考: