机器为什么可以学习

机器学习、人工智能炙手可热,但是机器到底为什么可以学习呢?本文将从霍夫丁不等式讲到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

positive ray

2

positive intervals

3

convex sets

no

2D perceptrons

4

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如果线性不可分,则可设定迭代次数,每次获得新的模型,与先前模型比较,选择最优模型。

如何让机器学得更好

让机器学得更好,可参考如下几点:

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

总结

理论

适用范围

公式

Hoeffding

单假设集

P(BAD)≤2exp(−2ϵ2N)P(BAD) \le 2\exp(-2\epsilon^2N)

Multi-Bin Hoeffding

MM个假设集

P(BAD)≤2Mexp(−2ϵ2N)P(BAD) \le 2M\exp(-2\epsilon^2N)

VC

假设集集合HH

P(BAD)≤4(2N)dvcexp(−18ϵ2N)P(BAD) \le 4(2N)^{d_{vc}}\exp(-\frac{1}{8}\epsilon^2N)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数值分析与有限元编程

共旋坐标法( 三 ) 算例

为计算方便,根据对称性取半结构,且刻意将初始刚度设为1,便于观察。取半结构之后,自由度只有一个,用Excel也能算了。当外荷载较小时,不会出现“跳跃”...

1311
来自专栏PPV课数据科学社区

【学习】数据挖掘中分类算法小结

数据仓库,数据库或者其它信息库中隐藏着许多可以为商业、科研等活动的决策提供所需要的知识。分类与预测是两种数据分析形式,它们可以用来抽取能够描述重要数据集...

31611
来自专栏机器人网

10 个常见机器学习案例:了解机器学习中的线性代数

它是机器学习的重要基础,从描述算法操作的符号到代码中算法的实现,都属于该学科的研究范围。

1063
来自专栏专知

【深度学习进阶模型详解】概率图模型/深度生成模型/深度强化学习,复旦邱锡鹏老师《神经网络与深度学习》教程分享05(附pdf下载)

【导读】复旦大学副教授、博士生导师、开源自然语言处理工具FudanNLP的主要开发者邱锡鹏(http://nlp.fudan.edu.cn/xpqiu/)老师撰...

6486
来自专栏SIGAI学习与实践平台

【SIGAI综述】行人检测算法

行人检测是计算机视觉中的经典问题,也是长期以来难以解决的问题。和人脸检测问题相比,由于人体的姿态复杂,变形更大,附着物和遮挡等问题更严重,因此准确的检测处于各种...

2262
来自专栏钱塘大数据

2018AI学习清单丨150个最好的机器学习和Python教程

机器学习的发展可以追溯到1959年,有着丰富的历史。这个领域也正在以前所未有的速度进化。在今年秋季,开始准备博士项目的时候,精选了一些有关机器学习和NLP的优质...

4627
来自专栏PPV课数据科学社区

常见面试之机器学习算法思想简单梳理

前言:   找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习/数据...

3364
来自专栏人工智能头条

实时翻译的发动机:矢量语义(斯坦福大学课程解读)

GraphDB 最近刚刚升级到 8.7 版本,此次特别更新了矢量语义包,直接以插件形式整合到程序中。

562
来自专栏肖力涛的专栏

马里奥 AI 实现方式探索 :神经网络+增强学习(上)

如果能够在游戏自动化测试、智能 AI 中应用这些有趣的算法,想想还是有点小激动哒。

8784
来自专栏机器之心

资源 | 从变分边界到进化策略,一文读懂机器学习变换技巧

32210

扫码关注云+社区