Skip to content

Latest commit

 

History

History
183 lines (108 loc) · 8.01 KB

06.vc-dimension.md

File metadata and controls

183 lines (108 loc) · 8.01 KB
Raw

VC Dimension

Target: Geometric Sampling and Approximation.

[toc]

Some Definitions

Range Space / Set System

由 $\Sigma=(X, R)$ 构成, $X$ 是一个有限/无限集合, 称为 points, $R$ 是一族有限/无限的 $X$ 的子集, 称为 ranges.

本 lecture 中考虑的是 $X\in R^n$, 而 $R$ 为一些几何形状和 $X$ 的交集(矩形, 球形, 半空间等)

对于任意 $Y\subseteq X$, 定义 $P_R(Y)={r\cap Y|r\in R}$ 为 $R$ 在 $Y$ 上的投影. 上述 几何形状 即此处所述 $Y$.

VC Dimension

Shatter

若 $P_R(Y)$ 包含了所有 $Y$ 的子集, 则称 $Y$ 被 $R$ 打散

若 $Y$ 有限, 则等价于 $|P_R(Y)|=2^{|Y|}$,

而 VC Dimension ($VC(\Sigma)$)即为能被 $R$ 打散的最大的 $X$ 的子集的大小, 它可以是无穷大的.

下图是一个 VC 维为 3 的半平面 range 示意图:

An example for halfplane.
The VC Dimension is 3, 4 points can't be shattered with a halfplane

举例

  • r: 平面上的圆; $Y$: $R^2$ 上的 3 个点; $Y$ 有 $2^3$ 个子集, 易知 $R={平面上的圆}$ 可以 shatter 平面上的 3 个点.
  • $VC((R^2, 圆))=3$, $VC((R^2,多边形))=+\infty$, $VC((R^d, 球))=d+1$

Sauer's Lemma

若 $(X,R)$ 是一个 range space, 且其 VC 维是 d, $|X|=n$, 那么 $|R|\le g(d,n)=\sum\limits_{i=0}^dC_n^i$

这里 $|R|$ 看起来像是说能被几何图形划分的情况数

证明: 归纳法证明. 假设对于 (d, n-1) 和 (d-1, n-1) 时, 引理成立.

任取一个点 $x\in X$, 定义 $$R_x={r\backslash{x} | x\notin r, r\cup {x} \in R }$$ 这里 $R_x$ 可以理解为是 ((不包含 $x$) 但 (存在仅仅多包含 x 的 Range) 的) Range r.

由于 $R_x$ 的每个元素都与 $R$ 中的某个成对(称为 twins), 因此 $R_x$ 的 VC 维就是 d-1, 故依据归纳假设有, $$|R_x|\le g(d-1,n-1)$$

剩下的则称为 singles, 则考虑 $R\backslash x={r\backslash {x} | x\in R}$, 显然 $|R\backslash x|\le g(d,n-1)$ (不等于是因为只能确保其 VC 维 $< d$)

对于每个 single 在 $R\backslash x$ 中计数了恰 1 次; 对于每个 twins, 包含 $x$ 的那个在 $R\backslash x$ 中计数了恰 1 次, 而不包含的那个则在 $R_x$ 中被计数. 故 $$|R|=|R\backslash x|+|R_x|\le g(d,n-1)+g(d-1,n-1)=g(d,n)$$

重要结论

若 $VC((X, R)) = d$, 令 $$R^{\cup k}={R 中 k 个 range 的并}$$ $$R^{\cap k}={R 中 k 个 range 的交}$$ $\Sigma_1=(X,R^{\cup k}), \Sigma_2=(X,R^{\cap k})$, 则有: $$dk \le VC(\Sigma_1), VC(\Sigma_2) \le dk\log k$$

两个采样相关的定理

$\epsilon$-Nets and $\epsilon$-Sample

  • $\epsilon$-Nets: $Q\subseteq X$ 是 $\Sigma=(X,R)$ 的 $\epsilon$-net, 如果 $\forall r\in R$, $$\frac{|X\cap r|}{|X|}>\epsilon \Rightarrow Q\cap r\not= \varnothing$$

  • $\epsilon$-Sample: $Q\subseteq X$ 是 $\Sigma=(X,R)$ 的 $\epsilon$-sample, 如果 $\forall r\in R$, $$\left| \frac{|X\cap r|}{|X|}-\frac{|Q\cap r|}{|Q|} \right| < \epsilon$$

显然 $\epsilon$-sample 必为 $\epsilon$-net.

定理

  • 若 $\Sigma=(X,R)$ 的 VC-Dimension 为 $d$, $Q$ 是 $X$ 的均匀采样, $\epsilon, \delta \in (0,1)$, 且 $$|Q|\ge\max\left{\frac{4}{\epsilon}\log\frac{2}{\delta},\frac{8d}{\epsilon}\log\frac{8d}{\epsilon}\right}\approx \Theta\left(\frac{d}{\epsilon}\right)$$ 则 $Q$ 是 $\epsilon$-net 的概率 $\ge 1-\delta$

  • 若 $\Sigma=(X,R)$ 的 VC-Dimension 为 $d$, $Q$ 是 $X$ 的均匀采样, $\epsilon, \delta \in (0,1)$, 且 $$|Q|=\Theta\left( \frac{1}{\epsilon^2}\left( d\log\frac{d}{\epsilon}+\log\frac{1}{\delta} \right) \right) \approx \tilde{\Theta}\left(\frac{1}{\epsilon^2}d\right)$$ 则 $Q$ 是 $\epsilon$-sample 的概率 $\ge 1-\delta$

应用

  • $\epsilon$-sample: range counting ???
  • $\epsilon$-net: SVM (超平面即定义了一种 range)

计算点集的最小包含球(MEB)

方法

使用 PAC(Probably Approximately Correct, 概率近似正确) 的方法, 可以先从点集 $|P|=n$ 中均匀采样出子集 $S$, 其中 $|S|=\widetilde{O}(\frac{d}{\epsilon^2})$, 然后求子集 $S$ 的最小包含球即可.

可靠性

这种方法下, $$\sharp覆盖到的点 \ge (1-\epsilon)n$$

证明如下: 由于 $|S|=\widetilde{O}(\frac{d}{\epsilon^2})$, 可以认为是一个 $\epsilon$-sample, 那么就有 $\forall r \in R$, $$\left|\frac{|X\cap r|}{|X|} - \frac{|S\cap r|}{|S|} \right| < \epsilon$$

进而可知 $$\frac{|X\cap r|}{|X|} > -\epsilon + \frac{|S\cap r|}{|S|}$$

因为取了一个能覆盖 $S$ 的 $r$, 因此这时 $S\cap r = S$, 所以上式即 $$|X\cap r|> (-\epsilon + 1)|X|=(1-\epsilon)n$$ $\square$

若计算 S 时也是近似算法

不妨设近似比为 $\alpha$, 那么就有 $r_S\le \alpha \widetilde{r}_S$

MEB $\Rightarrow$ k-center

此时, 是 $k$ 个球的并, 其 VC-dimension $\le kd\log k$, 要抽样的数量也变成 $$|S|=\widetilde{O}\left(\frac{kd\log k}{\epsilon^2}\right)$$

k-means

此为 HW2.2, TODO

Set Cover

问题定义: 给定 range space $\Sigma=(X,R)$, $|X|=n$, 要找出最小子集 $R'$, s.t. $$\bigcup\limits_{r\in R'}(r\cap X)=X$$ 当然, 这里首先要满足 $\bigcup\limits_{r\in R}(r\cap X)=X$

贪心算法

不断找能在 X 多覆盖最多的 ranger, 直到全覆盖.

贪心算法近似比

是 $\Theta(\log n)$. 证明如下:

定义一组 ${(X_i,R_i)}$, $(X_i,R_i)$ 为第 $i$ 轮中的 $(X,R)$, $i$ 从 0 开始. 假设 $H_i$ 为 $(X_i,R_i)$ 的最佳 set cover, 我们要求的即是 $H_0$, 假设 $|H_0|=k$. 那么有以下结论:

  1. $|H_i|\ge|H_{i+1}|$ 令 $r$ 是第 $i$ 轮选取的 range, 若 $r \in H_i$, 那么 $H_i={r}\cup H_{i+1}$ 若 $r\notin H_i$, 则 $H_i$ 是 $R_{i+1}$ 中覆盖 $X_i$ 的最佳 cover set
  2. $|X_{i+1}|\le(1-\frac{1}{k})|X_i|$ 由 1 知 $|H_i|\le k$, 若 $r$ 是第 $i$ 轮选取的 range, $|r\cap X_i|\ge\frac{1}{|H_i|}|X_i|\ge\frac{1}{k}|X_i|$, 从而 $|X_{i+1}|\le(1-\frac{1}{k})|X_i|$
  3. $|X_t|\le (1-\frac{1}{K})^t|X_0|$

假设 $|X_t|=1$, 则 $1\le(1-\frac{1}{k})^k\cdot n$, 因此 $t\le\frac{\log\frac{1}{n}}{\log (1-\frac{1}{k})}\approx k\log n$

Hitting Set

给定 $\Sigma=(X,R)$, $|X|=n$, 目标是找 $X$ 的一个最小子集 $Y$, s.t. $\forall r\in R, r\cap Y\not= \varnothing$. 这是一个 $0$-net ????

Cover Set 和 Hitting Set 的关系

构造一个新的 range space $\Sigma^=(R,X^)$, $\forall x \in X, r_x={r|x\in r}\subseteq R$, 即 $r_x$ 是所有包含 $x$ 的 range 集合. 令 $X^={r_x|x\in X}$. 则 $\Sigma^=(R,X^*)$ 可以看作是 $\Sigma=(X,R)$ 的对偶空间.

由此有结论: $\Sigma$ 的 set cover $\Leftrightarrow$ $\Sigma^$ 的 Hitting set $\widetilde{R}$ 是 $\Sigma$ 的 set cover $\Leftrightarrow$ $\widetilde{R}$ 是 $\Sigma^$ 的 Hitting set

若 $\widetilde{R}$ 是 $\Sigma$ 的 set cover, 则 $\bigcup\limits_{r\in\widetilde{R}} (r\cap X)=X$ $\Leftrightarrow$ $\forall x\in X, \exists r\in \widetilde{R}$, s.t. $x\in r $ $\Leftrightarrow \forall r_x\in X^*$, $r_x\cap \widetilde{R}\not=\varnothing$, 满足 hitting set 定义

进一步, $\forall \alpha-approx$ Set Cover of $\Sigma$ $\Leftrightarrow$ $\alpha-approx$ Hitting Set of $\Sigma^*$

求解 Hitting Set 的算法

$\epsilon$-net 均匀采样 $\widetilde{\Theta}(\frac{d}{\epsilon})$. 可以是 adaptive/uniform sampling.(addaptive思想如 k-means++).

  • 输入: $\Sigma^=(R,X^)$
  • 过程: 重复以下步骤直到获得一个 set hit 所有 $\Sigma^*$ 的 ranges. $\forall r \in R$, 初始化权重 $weight=1$
    1. 取 $\Sigma^*$ 的一个 $\frac{1}{2k}$-net
    2. 从 $r_x\in X^*$ 取一个未被已取的 net 之并所 hit 的, 使之权重翻倍.
  • 结论:
    • 以上算法迭代次数 $\le 4k\log\frac{n}{k}$ ($n$ 是 $|X|$),
    • 得到的 hitting set 大小 $\le \Theta(dk\log(dk))$
    • 近似比为 $\Theta(d\log (dk)) \approx \Theta(\log k)$ 若 $d=(\Theta(1))\ll \Theta(\log n)$

TODO