机器学习的可行性

Contents

笔记整理：以罐抓小球为例，推广到机器学习问题，并分为有限的H和无限的H两种情况。

本文基于以下内容整理：

主要在于抓住脉络，即：

以罐抓小球为例，推广到机器学习问题，并分为有限的H和无限的H两种情况。

以罐抓小球为例

对某一固定罐子，其中有橙色、绿色的小球，要估算其中橙色小球的比例（$u$）。可以通过抽样一部分样本，计算橙色的比例（$v$）来估算。

当抽样数量$N$足够大时，$v\rightarrow u$，根据Hoeffding’s Inequality，有$P(|v-u|>\epsilon)\leq 2\exp(-2\epsilon^2N)$ 。

对某一固定$h$，当$N$足够大且$x_n$独立同分布时，有$P[h(\vec x_n)=y_n]\rightarrow P[h(\vec x)=f(\vec x)]$。同时$P[h(\vec x_n)=y_n]$越大越好。

也就是$P[h(\vec x_n)\neq y_n]\rightarrow P[h(\vec x)\neq f(\vec x)]$。两者的差距要越小越好，用一个上界可以限制。同时$P[h(\vec x_n)\neq y_n]$越小越好。

再分别用 $E_{in}(h)=\frac{1}{N}\sum^N_{n=1}[h(\vec x_n)\neq y_n]$ 和 $E_{out}(h)=E_{\vec x\sim P}[h(\vec x)\neq f(\vec x)]$ 替换掉。

另外，$A$还要能自由选择$h$。

综上，要令$E_{in}(h)$和$E_{out}(h)$接近，差距可以用上界控制，且$E_{in}(h)$很小。

$E_{in}(h)$和$E_{out}(h)$的差距会受$D$的影响。如果样本糟糕，可能令多个$h$的$|E_{in}(h)-E_{out}(h)|$偏差。

$|E_{in}(h)-E_{out}(h)|>\epsilon \Leftrightarrow \text{Bad Sample for } h$

对有限的$H$，$N$足够大，由union bound，设$M=|H|$，使得
$$P|E_{in}(h)-E_{out}(h)|>\epsilon)=P( \text{Bad Sample for } h) \leq 2M\exp(-2\epsilon^2N)$$成立，也就是用上界限制住了。

因此，对有限的$H$，$N$足够大，成立。

(1) 对无限的$H$，union bound无效，考虑替换$M$。

$h$作用于$N$个样本，产生的判定结果（0或1）最多有$2^N$种，这个不能做上界。实际上，结果常常没有$2^N$种。

$N$个样本的每一种结果称为一个dichotomy，dichotomy集合为$H(\vec x_1,\vec x_2,\ldots,\vec x_N)$，与具体的$\vec x_1,\vec x_2,\ldots,\vec x_N$有关。

shatter指对$N$个样本，存在一组$\vec x_1,\vec x_2,\ldots,\vec x_N$，使得$H(\vec x_1,\vec x_2,\ldots,\vec x_N)$可以包括样本的所有情况$2^N$。也就是最多种结果=$2^N$。

用成长函数表示最多有多少种结果，定义为

$$
m_H(N)=max_{\vec x_1,\vec x_2,\ldots,\vec x_N\in X}|H(\vec x_1,\vec x_2,\ldots,\vec x_N)|,
$$

与具体的$\vec x_1,\vec x_2,\ldots,\vec x_N$无关。shatter就是$m_H(N)=2^N$。

猜测可以用$m_H(N)$替换$M$，找$m_H(N)$的上界。

对$N$个样本，如$H$不能shatter，则$N$就是break point。已知存在$k$为break point，
$$
m_H(N)\leq B(N,k)=\sum_{i=0}^{k-1}C^i_n\leq N^{k-1}.
$$

VC维定义为$d_{vc}=k-1$，$m_H(N)\leq N^{d_{vc}}$。
改动$m_H(N)$可替换$M$。
$$
P|E_{in}(h)-E_{out}(h)|>\epsilon)=P( \text{Bad Sample for } h) \leq 4(2N)^{d_{vc}} \exp(-1/8 \epsilon^2 N)
.$$

因此，对无限的$H$，$N$足够大，且$m_H(N)$有break point时，成立。