西瓜书扩展_学习理论

2020-03-18 本文已影响0人我_7

概念 $c$ =未知目标函数 $f$

样本集大小 $m=N$

“不可知PLA可学习” $f \notin \mathcal{H}$

二分类问题，0-1损失函数（0-1 loss function） $\ell_{h}(x,y)\ =\ I(y\neq h(x))$

泛化误差（generalization error）也称期望损失（expected loss） $E_{out}(h)=E(h)=\mathbb{E}_{\mathcal{P}}[\ell_{h}(x,y)]$

经验误差（empirical error）也称经验损失（empirical loss） $E_{in}(h)=\hat{E}(h)=\frac{1}{N}\sum_{i=1}^{N}\ell_{h} (x_{i},y_{i})$

由于数据集D是 $\mathcal{P}$ 独立同分布的采样，因此 $h$ 的经验误差期望等于其泛化误差，带入霍夫丁不等式（Hoeffding Inequality）

上面说到期望就是平均数随样本趋于无穷的极限，那么这句话是什么意思呢？

我们还是以上面的掷骰子为例子：

如果我们掷了无数次的骰子，然后将其中的点数进行相加，然后除以他们掷骰子的次数得到均值，这个有无数次样本得出的均值就趋向于期望。

个人理解：均值为多个随机变量的和再除以个数，相当于还是一个随机变量，当数量足够多的时候，这个随机变量会收敛，这个收敛的值为期望

$\delta=2\exp(-2N\epsilon^2)$ ， $\epsilon =\sqrt{\frac{\ln\frac{2}{\delta}}{2N}}$

$P(|E_{in}-E_{out} |\geq \epsilon )\leq \delta$

$P(|E_{in}-E_{out} |\leq \epsilon )\geq 1-\delta$

$=P\Big( (E_{in}-\epsilon) \leq E_{out}\leq (E_{in}+\epsilon) \Big)\geq 1-\delta$

$=P\Big( (E_{in}-\sqrt{\frac{\ln\frac{2}{\delta}}{2N}}) \leq E_{out}\leq (E_{in}+\sqrt{\frac{\ln\frac{2}{\delta}}{2N}}) \Big)\geq 1-\delta$

泛化误差上界（generalization error bound） $E_{out}\leq (E_{in}+\epsilon)$

联合约束（Union Bound）

$P(\exists h\in \mathcal{H}:|E_{in}-E_{out} |\geq \epsilon )$

$=P\Big(\ |E_{in}(h_{1})-E_{out}(h_{1}) |\geq \epsilon \quad \mathbf{or} \ ...\ \mathbf{or} \quad |E_{in}(h_{|\mathcal{H}|})-E_{out}(h_{|\mathcal{H}|}) |\geq \epsilon \ \Big)$

$\leq \sum_{h\in \mathcal{H}}^{} P(|E_{in}-E_{out} |\geq \epsilon )$

$\leq \sum_{h\in \mathcal{H}}^{} 2\exp(-2N\epsilon^2)=2|\mathcal{H}|\exp(-2N\epsilon^2)=\delta$ ， $\epsilon=\sqrt{\frac{\ln|\mathcal{H}|+\ln\frac{2}{\delta}}{2N}}$

$P(|E_{in}-E_{out} |\geq \epsilon )\leq \delta$

$=P\Big( (E_{in}-\sqrt{\frac{\ln|\mathcal{H}|+\ln\frac{2}{\delta}}{2N}}) \leq E_{out}\leq (E_{in}+\sqrt{\frac{\ln|\mathcal{H}|+\ln\frac{2}{\delta}}{2N}}) \Big)\geq 1-\delta$

对分（dichotomy） $h_{|D}=\{(h(x_1),...,h(x_{N}))\ |\ h\in \mathcal{H}\}$

增长函数（growth function） $\Pi_ \mathcal{H}(N)=\max |h_{|D}| \leq 2^N$ ，max表示最大

打散（shattering） $\Pi_ \mathcal{H}(N)= 2^N$ ，N个样本点的集合能被H给打碎，或者说H 能打碎N个样本点的集合

突破点（break point） $k=\min\ |\Pi_ \mathcal{H}(N)< 2^N|$ ，N个样本点的集合不能被H给打碎

vc维（VC Dimension） $d=k-1=\max\{ N\ |\ \Pi_ \mathcal{H}(N)= 2^N\}$ ，max表示最大

一个数据点呈圆形分布的凸集，这时找不到任何突破点（break point），此时vc维趋于无穷。

Sauer 引理

$Q=\{x_{1}, x_{2},x_{3},x_{4}\}$

$S=Q ∪\{x_5\} =\{x_{1}, x_{2},x_{3},x_{4},x_{5}\}$

如果一个集合 $Q$ 被 $\mathcal{H}_{|D^1}$ 打碎，那么它也能被 $\mathcal{H}_{|D}$ 打碎，因为 $\mathcal{H}_{|D^1}$ 中包含 $\mathcal{H}_{|D}$ 所有在 $Q$ 上不重复的函数。

此外，如果一个集合 $Q$ 被 $\mathcal{H}_{|D^1|D}$ 打碎，集合 $S$ 也将被 $\mathcal{H}_{|D}$ 打碎，因为对 $\mathcal{H}_{|D^1|D}$ 中的所有函数， $\mathcal{H}_{|D}$ 都包含另外一个函数，它仅在 $x_5$ 上的输出和前一个函数不同。

递归

递归：大雄在房里，用时光电视看着未来的情况。电视画面中的那个时候，他正在用时光电视，看着未来的情况。电视画面中的那个时候，他正在用时光电视，看着未来的情况……

当 $N \geq 2, d \geq 2$ 的时候， $\Pi_ \mathcal{H}(N) \leq \sum_{i=0}^{d}\binom{N}{i} \leq N^d \cdot (\frac{e}{d})^d$

$P(|E_{in}-E_{out} |> \epsilon )\ \leq\ 4 N^d \cdot (\frac{e}{d})^d\exp(-\frac{N\epsilon^2}{8})$

基于vc维得到的泛化边界（model complexity） $\epsilon =\sqrt{\frac{8d\ln\frac{2Ne}{d}+8\ln\frac{4}{\delta}}{N}}$

不是一味的追求经验误差最小化

未知目标分布 P(y|x) 包含 f(x)+noise

对于不同的学习任务（分类，回归，..）使用不同的损失函数（loss function）才能正确的解答。

X的样本数量为N

$h(X)=(Xw)=y$

$(Xw)=y \overset{X \ \mathrm{invertible}}{\Leftrightarrow} w=X^{-1}y$

打散（shattering）就是我们给它任何一种ooxx组合 $y$ ，都要能够做到 $(Xw)=y$ 也就是一条直线正确分类。

只要 $X$ 可以求逆就能求出与之相对应的 $w$ ，全部的 $2^{N}$ 种组合都可以使用这种做法。

西瓜书扩展_学习理论

猜你喜欢

热点阅读