机器学习基石笔记(1)

文章目录
  1. learning的概览
  2. learning是否可行?(Feasibility)
    1. learning是 impossible?
    2. Inferring Something Unknown与统计结合
    3. Bad Data 坏数据
  3. 总结

整理自台大林轩田老师的机器学习基石在线课程,以及参考了beader的文章,作为笔记。

一些机器学习入门的书籍大部分都是直接讲模型,却没有来龙去脉,感觉很虚。而林老师的第一部分是机器学习的基石,就是背后的东西,并没有直接去讲各种模型, 在第二部分机器学习技法才开始介绍模型。

课程前三节主要介绍了机器学习的一些基本概念(未知函数f, 学习算法A, 假设空间H等等),以及讲了一个最简单的线性分类器: 感知器模型(PLA). 相对简单,比较容易接受。 这节开始主要介绍一些算法背后的理论,比如为什么机器学习为什么可行,以及为什么训练数据集越大,训练结果就越好。

learning的概览

learning的流程图: learning-flow 下面仔细说明每个符号代表的意义: 当时看的时候,没搞透彻这几个符号,后面就很费劲了。

  • \(\mathcal{f}: \chi \to \gamma\)
    • \(\chi\) 表示输入空间,里面包含了很多组输入数据\(x_i\). 比如拿信用卡审核的例子来说,输入空间\(\chi\)可以是 (age, gender, annual salary, year in residence, year in job, current debt) 表示的六维的输入空间. (23, male, 10000,1,0.5, 20000)可能就是一组输入的数据。
    • \(\gamma\) 则代表的是输出空间。比如前面提到的PLA的输出空间是\(\{+1, -1\}^1\), 在信用卡例子中,可以用+1表示未来会违约,-1表示未来不会违约。
    • \(f\) 是很核心的概念,表示现实中未知的某个规律或者某个函数, 我们只能知道的是,把训练数据\(\mathcal{D}\)中的数据\(x_i\)作为输入,它会输出 \(y_i\).正因为它的未知,learning要做的事情就是找到一个函数\(\mathcal{g}\)能构接近\(\mathcal{f}\).接近的意思是指,\(\mathcal{g}\)对于训练数据\(\mathcal{D}\)中的运行情况与\(\mathcal{f}\)的运行情况类似。
  • \(\mathcal{D}: {(x_1, y_1), (x_2, y_2),..., (x_N, y_N)}\): 表示由输入空间\(\chi\)中的\(x\)以及输出空间\(gamma\)中的\(y\)组成的N条数据的训练数据集。
  • \(\mathcal{H}\): 表示假设空间,也就是一堆函数的集合:\(\{ h_1, h_2, ...\}\),我们要找的\(\mathcal{g}\)就在这里面寻找。
  • \(\mathcal{A}\):学习算法,通过\(\mathcal{A}\),我们才可以在\(\mathcal{H}\)中找到最接近\(f\)的那个\(h\). 因为\(\mathcal{H}\)的数量是未知的,因此我们必须把学习算法设计的合适,才可以高效的找到那个\(h\)
  • \(\mathcal{g}\):这个就是我们最后找到的hypothsis,就是通过学习算法\(\mathcal{A}\)找到的那个最接近f的函数。

有几个注意的点:

  • \(\mathcal{D}\)是一个训练数据集,后面会区分多个训练数据集。
  • \(f\) 一定是未知。learning的过程就是在\(\mathcal{H}\)里面找到在训练数据集\(\mathcal{D}\)表现接近f的那个hypothesis.

那么问题来了,假设我们找到了那个\(g\), 它在训练数据集上表现不错,但是在\(\mathcal{D}\)之外的其它数据表现也会跟\(f\)很接近吗? 我们关心的不是它在训练数据集上表现多好,而是在未知数据集上的结果是不是很好,那么如果一个hypothesis在训练数据集上接近f,那么是不是在测试数据上跟f也差不多呢。这就是检验learning是不是真正学到了东西。

learning是否可行?(Feasibility)

learning是 impossible?

我们经验上感觉g如果在\(\mathcal{D}\)上的表现好的话, 那么它就是一个好的hypothesis。但是事实是这样吗?有这么一个二分类的简单例子:看训练数据如下: binary-classify-sample

其中\(\chi \in \{ 0, 1\}^3, \gamma \in \{ o, X\}^1\).

举着个例子是因为很简单, 所有的数据以及\(\mathcal{H}\)里面所有的\(h\)都可以列举出来,如下: all-h-in-H

我们发现8个\(h\)\(\mathcal{D}\)上都等于 \(f\). 但是在\(\mathcal{D}\)之外,却各不相同,那么我们应该选择那个作为我们最终的\(g\)呢?这里看来,好像机器学习并不能学到东西,我们好像并不能保证在训练数据集之外\(g\)是否还能跟\(f\)很接近。 这个问题需要后面解释

Inferring Something Unknown与统计结合

我们在统计里面知道抽样的概念,使用样本估计总体,比如样本均值估计总体期望, 或者用样本构造一些统计量来估计总体分布的参数。 比如下面的摸球的例子,一个罐子里面有橙色的球和绿色的球,但是不知道各自所占的比例。这时候我们呢经常采用抽样的方式,在罐子中抽出N个球,看看橙色和绿色占的比例,依次作为总体的概率。 如下: sample

那我们可不可以使用 样本中的\(\nu\)来代替总体中的\(\mu\)呢? 似乎可以,但是好像仍有风险, 比如总体中,橙色,绿色占比例差不多,但是碰巧有一个Sample抽了10个都是绿色的(后面提到的BadData) , 那这个时候,我们不能使用\(\nu\)代替 \(mu\), 不过经验还告诉我们好像10个都是绿色的发生概率并不是很大,尤其是随着样本数目的增加。 在统计中的Hoeffdiing’s inequality 给出了具体的计算公式: \[P[\| \nu - \mu \| > \epsilon] \leq 2 exp \lgroup -2 \epsilon ^2 N \rgroup \]

称式子中的\(\epsilon\) 是允许误差的容忍度, 我们可以看到就是说 \(\nu\)\(\mu\)的差距由\(\epsilon, N\) 控制的。当\(N\)变大的时候,\(\mu, \nu\)的差距的上限会降低。当\(\mu, \nu\)的差距小到一定程度了, 可以说它俩是差不多一样(PAC, probably approximately correct)。

以上是基于统计的观点,使用样本估计总体。 那该怎么与我们的 learning 对应起来呢?我们假设那一罐子球是假设空间\(\chi\), 对于某个hypothesis h,开始抽样,作如下对应:

  • \(h(x_i) \neq f(x_i)\) 时, 对应球是橙色
  • $h(x_i) = f(x_i) $时, 对应球是绿色

有了这个对应之后,样本中橙色球的概率\(\nu\)就是当前hypothesis的错误率\(error\)。 总体中的橙色球概率\(\mu\)则是\(h\)在总体分布下的错误率。这里我们定义两个新的变量:

  • \(E_{in}(h) = \frac{1}{N} \sum_{n=1}^{N} \lVert h(x_n) \neq f(x_n) \rVert\), IN-SAMPLE-ERROR,h在训练集的错误率
  • \(E_{out}(h) = \epsilon_{x \sim P} \lVert h(x) \neq f(x) \rVert\), OUT-SAMPLE-ERROR,在总体中\(h\)的错误率

很容易可以知道: \[ \begin{align} \mu &= E_{out}\\ \nu &= E_{in} \end{align} \]

代入Hoeffdiing’s inequality 可以得到:

\[P[\| E_{in} - E_{out} \| > \epsilon] \leq 2 exp \lgroup -2 \epsilon ^2 N \rgroup\]

这就意味着,在不等式的上限在足够小的情况下,我们貌似可以说,\(E_{in}\)\(E_{out}\) 达到了 PAC, 也就是说 h 在训练集中的表现与在总体中的表现接近,即:用已知的\(E_{in}\)去推断未知的\(E_{out}\) 。 但现在还不可以说,\(h\)是一个好的learning, 因为我们的目的不是\(h\), 而是一个接近\(f\)\(g\), 因此我们需要的不仅仅\(E_{in}\)\(E_{out}\)接近,更需要他们尽可能小,这样才是一个最好的最接近真理\(f\)\(h\)

Bad Data 坏数据

前面说了,使用某个训练集或者说抽样的样本,然后找一个\(E_{in}\)尽可能小的\(h\), 作为我们的\(g\). 但是如果训练数据集有问题呢?尤其是当N小的时候,误差是不可避免的,或者说噪音数据集。比如说想知道硬币朝上的概率,然后连续扔了5次,都出现了正面,这种情况下,显然不能说硬币朝上的概率是1吧。因为这样的样本本身是有误差的,对于整体 来说: \(E_{in} = 0; E_{out} = \frac{1}{2}\).这样使\(E_{in}\)\(E_{out}\)差别很大的样本就称为BAD SAMPLE 说到learning, 对于某个 \(h\), 如果某个\(\mathcal{D}\)使得 \(E_{in}(h)\)\(E_{out}(h)\) 差别很大,比如说\(E_{in}(h)\)很小,也就说在训练数据中表现很好,结果我们的算法\(\mathcal{A}\)就选择了它, 但是没想到\(\mathcal{D}\)之外的数据表现很差,\(E_{out}(h)\)很大, 这样就称这个\(\mathcal{D}\)\(h\)来说是BAD DATA, 它会使得 \(\|E_{in} - E_{out}\| > \epsilon\)。那是不是机器学习啥也没学到呢? 白忙活了? 很显然,我们不希望遇见BAD DATA, 它对我们的learning很不好,那么出现BAD DATA的概率有多大呢? 首先只要某个\(\mathcal{D}_i\)\(h(h \in \mathcal{H})\) 是BAD DATA, 那么就称该\(\mathcal{D}\)是BAD DATA, 如下

bad-data

bad-data

那我们就需要计算: bad-data-prob 其中\(M = \| \mathcal{H} \|\), 从式子中我们可以看出,遇到BAD DATA的概率的上限 与\(N, M, \epsilon\)有关。 因而也可以看出如果训练数据N越大,也就更不容易遇见BAD DATA, 对应到硬币则是,连续投硬币10次均出现正面的概率 小于 连续投5次。同理如果 M 越小,BAD DATA概率越小。

总结

说完了\(P[\| E_{in}(h) - E_{out}(h) \| > \epsilon] \leq 2 exp \lgroup -2 \epsilon ^2 N \rgroup\), 我们知道\(E_{in}(h)\)\(E_{out}(h)\)可以很接近,我们就可以大胆的选择\(E_{in}\)最小的\(h\)来作为我们的\(g\)。但是BAD DATA又告诉我们群众里面有坏人,如果遇到了,那么会影响我们的\(\mathcal{A}\) 挑选\(h\). 幸好,Hoeffding’s Inequality 告诉我们 出现 BAD DATA的概率有个bound。 所以我们只要控制了BAD DATA出现的几率,还可以继续选择最小的\(E_{in}(h)\)了。 不过还有问题,\(M\) 如果很大了,比如在PAL中,\(\mathcal{H}\) 就是无穷多的直线,这时候,Hoeffding’s Inequality貌似也不能起作用了,这就是后面要讨论的问题了: 当\(\| \mathcal{H} \| \to infty\),我们该怎么办。