机器为什么可以学习

机器学习、人工智能炙手可热，但是机器到底为什么可以学习呢？本文将从霍夫丁不等式讲到VC维，探究机器学习的原因所在。

• 机器怎么可能学习
• 机器确实可能会学习
• 机器为什么可以学习
  • 机器学习的一般模式
  • 多次试验与假设集
  • M从哪来
  • break point与VC维

• 机器什么时候可以学习
• 机器怎么学习
• 如何让机器学得更好
• 总结

本文的主要内容参考国立中国台湾大学的《机器学习基石》课程，作者在其基础上进行了部分提炼与整合。

机器怎么可能学习

机器学习乍听之下很厉害，这时候人就会想，这一个普普通通的死板的机器，怎么会学习呢？ 很容易地，人们举了个简单的问题（如下图）：x,y,g,fx,y,g,f分别表示：数据集、数据标签、预测模型、实际的模型。前5行的数据代表已知的，后三行的数据需要机器学习预测模型去预测。

悲催的是，符合已知的数据的预测模型最多有8种，这8种任选一种，都可以完全符合已知的数据，也都可以完全不符合未知的数据。这么看来，机器确实是学习不到东西的。

机器确实可能会学习

假定面前有一个箱子，箱子里面有绿球和黄球，已知黄球的比例是μ\mu，希望通过抽取NN个样本，学习样本中黄球的比例vv去逼近μ\mu。

μ,v\mu,v满足的关系如下，其中ϵ\epsilon代表误差限，下面的式子叫做Hoeffding不等式。

P(|v−μ|>ϵ)P(|Ein−Eout|>ϵ)P(BAD)≤2exp(−2ϵ2N)≤2exp(−2ϵ2N)≤2exp(−2ϵ2N)

\begin{split} &P(|v-\mu| > \epsilon) &\le 2\exp(-2\epsilon^2N) \\ &P(|E_{in}-E_{out}| > \epsilon) &\le 2\exp(-2\epsilon^2N) \\ &P(BAD) &\le 2\exp(-2\epsilon^2N) \end{split}

设定一定的误差容忍限ϵ\epsilon后，需要做到如下的事情机器才可能学习：

• 采样样本量NN足够大
• EinE_{in}足够小

有了Hoeffding不等式后，我们会想，机器如果有足够大的数据，是不是就可以学习到数据背后的模型，也就实现了机器学习？

机器为什么可以学习

机器学习的一般模式

在探讨机器为什么可以学习之前，先阐述下机器学习的一般模式。

一句话阐述如下：算法AA通过数据DD和假设集HH去学习实际模型ff的估计gg。

机器要学习，需要满足这两件事情：

• EinE_{in}小
• Ein≈EoutE_{in} \approx E_{out}

多次试验与假设集

上述的Hoeffding不等式只适用于单次实验，假定假设集是R2R^2上的直线，那么单次实验相当于确定直线为y=x+1y=x+1的时候，Ein,EoutE_{in},E_{out}的差值受Hoeffding不等式的限制。

可是，一般情况下，我们的假设集是很大的，R2R^2上的直线包含无限个假设gg。如果不断尝试假设gg，视比例vv为EinE_{in}，那么总会找到对应Ein很小的E_{in}很小的gg。对应计算盒子中黄球的比例vv很低，那么当取了非常非常多次后，非常大的可能会出现v=0v=0（也就是Ein=0E_{in}=0）的情况。可是，这种时候不能说μ=0\mu=0（也就是Eout=0E_{out}=0）。

同样的，当假设集的大小是MM时，P(BAD)P(BAD)的上限是MM个假设gg的P(BAD)P(BAD)的和，所以有：

P(|Ein−Eout|>ϵ)P(BAD)≤2Mexp(−2ϵ2N)≤2Mexp(−2ϵ2N)

\begin{split} &P(|E_{in}-E_{out}| > \epsilon) &\le 2M\exp(-2\epsilon^2N) \\ &P(BAD) &\le 2M\exp(-2\epsilon^2N) \end{split}

设定一定的误差容忍限ϵ\epsilon后，需要做到如下的事情机器才可能学习：

• 采样样本量NN足够大
• EinE_{in}足够小
• MM不能太大

这样一来，又一个问题接踵而来，很多假设集（比如R2R^2上直线）的MM都是无穷的啊，这样的话机器岂不是不能学习？

M从哪来

首先，先来分析下上面式子中的MM来源于哪里。 MM是假设集中所有gg的个数，但是以R2R^2上的直线为例，相当多的直线长得差不多，这样MM中的所有gg重叠了很大一部分，所以自然而然地引出了一个问题：

对于一个假设集HH，有效的MM是多少呢（揭露下，是mH(N)m_H(N)啦）？

break point与VC维

有效的假设集的个数，和假设集的break point关系很大。假设集的break point指的是：不能被假设集打散（shatter）的最小的点的个数。需要注意的是，这里不能被打散是指点的所有分布都不能被打散。

举个例子，R2R^2上的直线，3个点有可以打散的分布，也有不可以打散的分布；但是4个点的任何分布都是打不散的。所以R2R^2上的直线的break point是4。

常见的假设集及其break point如下：

break point求出之后，mH(n)=O(Nk−1)m_H(n) = O(N^{k-1})，其增长率受break point的限制。

VC维是break point-1的值，物理含义是自由参数。

通过前面的计算，得到了：

P(|Ein−Eout|>ϵ)P(BAD)≤2Mexp(−2ϵ2N)≤2Mexp(−2ϵ2N)

\begin{split} &P(|E_{in}-E_{out}| > \epsilon) &\le 2M\exp(-2\epsilon^2N) \\ &P(BAD) &\le 2M\exp(-2\epsilon^2N) \end{split}

稍作变换， 即得到：

P(|Ein−Eout|>ϵ)P(BAD)≤4(2N)dvcexp(−18ϵ2N)≤4(2N)dvcexp(−18ϵ2N)

\begin{split} &P(|E_{in}-E_{out}| > \epsilon) &\le 4(2N)^{d_{vc}}\exp(-\frac{1}{8}\epsilon^2N) \\ &P(BAD) &\le 4(2N)^{d_{vc}}\exp(-\frac{1}{8}\epsilon^2N) \end{split}

设定一定的误差容忍限ϵ\epsilon后，需要做到如下的事情机器才可能学习：

• 采样样本量NN足够大
• EinE_{in}足够小
• VC维不能太大

这样一来，选择合适的假设集，机器学习成为了可能。

机器什么时候可以学习

• 潜在的模式
• 没有明确的公式，不容易编程解决
• 有关于模式的数据

机器怎么学习

最简单的学习方法是PLA，其假设集是h(x)=sign(wTx)h(x) = sign(w^T x)。

其算法核心是：更正错误，迭代提高。

1. 找到在当前模型参数下wtw_t错误的数据(xn,yn)(x_n,y_n)，即sign(wTtxn)≠ynsign(w_t^T x_n) \neq y_n
2. 更正模型参数，wt+1=wt+ynxnw_{t+1} = w_t + y_n x_n

这样更正的依据是：让wTxy>0w^Txy>0，通过每次更正，保证了wTt+1xnyn≥wTtxnynw_{t+1}^T x_n y_n \ge w_t ^T x_n y_n。

PLA保证如果线性可分，那么最终模型收敛。

PLA如果线性不可分，则可设定迭代次数，每次获得新的模型，与先前模型比较，选择最优模型。

如何让机器学得更好

让机器学得更好，可参考如下几点：

• 数据预处理
• 合适假设集
• 特征变换
• 特征选择
• 处理过拟合
• 验证
• 核方法
• 集合模型
• 特征提取

总结