机器学习入门科普

本文由 我的分享 PPT 整理而来,由于图片的表达能力更强,因此强烈建议结合 PPT 进行阅读。

这是我根据自己短短两周的学习总结出来的文章,优点非常明显:我也是初学者,因此更能理解初学者的困惑,更能站在初学者的角度解释问题。但缺点也很明显,并不保证内容 100% 的准确,欢迎交流讨论。文章尽量不提公式,但出于表达的需要,难免会有一些。个人认为只要有简单的数学基础,都能读懂。如果实在读不懂,也不会影响阅读文章。

序言

自从电脑诞生之日起,人类对人工智能的追求就没有停止过。电影里那种既有强大计算能力,又有人类情感的人工智能一般被称为强人工智能,遗憾的是当下并没有能力实现强人工智能,也就是基于统计学得出结论,只不过这个结论比较合理,看起来像人类的思考结果一样,这也被称为弱人工智能

机器学习是一种实现人工智能的方法, 本文的目的就是帮助毫无机器学习基础的读者了解最基本的名词和概念,掌握最基本的算法及其原理,以及最重要的——破除对机器学习的迷信,防止被忽悠。

机器学习的基本流程

机器学习是一类算法的统称,比如这两年很火的深度学习(深度神经网络),以及很早就出现的决策树、贝叶斯分类等。这类算法普遍具有一个特征,即:仿照人类的学习过程

再厉害的大神,一开始也是啥都不会的小白。经过做题,核对答案,改正错误,最后才能学会一个知识点。而考试则是对知识点掌握程度的考察,在考场上,学生根据已经掌握的知识回答题目。如果平时学得好,最后就能考满分。

机器学习的过程也是类似的,首先需要收集大量的数据给机器训练,这个过程对应人类做题学知识的过程,训练以后得到的结果叫做“模型”,对应到人类世界就是学生掌握的知识。当接收到新的数据时,这个数据会输入到模型中,从而预测出结果。

可以看到,从历史数据到训练出模型,以及利用模型预测新数据,这两件事是互相独立的。因此一种很常见的做法是服务端训练模型,下发并存储在客户端,当有新的数据时直接应用。这样做的好处是避免了上行数据的网络耗时,不过需要注意下模型在客户的占用的内存、增加的包大小,耗电量,以及最重要的:“模型的安全性”,模型是精心学习后的知识,如果泄露出去,就像是所有人都能和学神一样考试得满分。

在接下来的文章里,我会简单介绍模型的训练和应用的过程,作为读者的你也会理解为什么模型训练可以放在服务端,而一台小小的手机就可以应用模型。

基本概念

我们先从一个老生常谈的例子开始,假设房子面积和价格的关系如下表所示:

面积(平米) 价格(万)
10 120
20 180
30 320
40 380
50 510
60 590
70 ???
80 800

那么 70 平的房子大约是多少钱呢?作为人类,我们很容易发现价格在面积的十倍上下浮动,所以最合理的预测是 70 平的房子价格大约是 700。同理,100 平的价格大约是 1000W……

如果我们写一个 C 语言函数,输入参数 n 表示面积,输出 n * 10 表示价格,一个最简单的人工智能程序就写完了。它满足我们之前的定义: 基于统计学得出符合人类逻辑的结论,上面的表格就是数据,n * 10 是我们的模型,70 平是新的输入,700W 则是基于模型的预测结果。

这里先抛出几个问题供读者思考,问题虽然简单,但问题背后的逻辑却一点都不简单。

  1. 凭什么就预测价格是 700W 呢,如果我就是喜欢抬杠,我偏说价格是 750W 你们服不服?
  2. 为什么我们从直觉上就觉得房价和面积是线性的关系,为什么不去猜一个二次函数?
  3. 怎么证明这个预测结果是合理的?

误差函数

假设我们有多条数据,第 $i$ 条数据记为 $(x_i, y_i)$,其中 $x_i$ 是输入数据,它可以是单个变量,比如上面例子中的面积,也可以是由一组变量构成的向量。$y_i$ 则是对数据的标记,比如上面例子中的房价。

我们的模型其实是一个函数 $f(x)$,对于每一个输入 $x_i$,都会产出一个预测结果 $f(x_i)$。虽然我们希望预测结果和真实的标记尽可能一致,也就是 $f(x_i) = y_i$,但终究还是存在误差的,为了量化这个误差,假设有如下函数:

$$
\frac 1 m\sum_{x=1}^m(f(x_i) - y_i)^2
$$

它其实就是对真实值和预测值的平方和求平均数,我们称之为误差函数。误差函数不是随便写的,比如直接对误差求和就不行,因为正负误差会互相抵消。我们暂时不考虑这个函数是怎么得出的,因为它涉及到统计学的模型,不过常用的误差函数就那么多,可以枚举出来,并不是无穷无尽的,不同场景下会选择不同的误差函数,主要看它能不能合理的评价误差。

我们假设房价和面积成正比,也就是说误差函数可以具体化为:

$$
\sum_{x=1}^m(kx_i + b - y_i)^2
$$

现在公式看上去比较复杂了,有很多变量,一会儿 $k$、$b$,一会儿 $x$, $y$,但理解公式最重要的一点就是搞清哪些是变量,哪些是已知量。比如上面式子中只有 $k$ 和 $b$ 是变量,其它字母都是已有的数据,比如 m 的值是 7,$(x_i, y_i)$ 的值都列在表中。

现在误差已经被精确地量化了,我们只要找到一组 $(k, b)$ 让上面的公式取得最小值就可以了。这种寻找一条曲线去尽量靠近各个点的做法叫做 拟合。最简单的方式就是分别对 $k$ 和 $b$ 求导,导数为 0 的地方会取得极值。但这种做法并不具备普适性,对于复杂的模型,我们可以考虑一些最小二乘法和梯度下降法。

最小二乘法

我们假设有 $m$ 组数据,每组数据都有 $d$ 个维度,每个维度对应一个参数 $w$,以及一个常数 $b$,因此预测结果可以表达为:

$$
Xw =
\begin{Bmatrix}
x_{11} & x_{12} & x_{13}& \cdots &x_{1d} & 1 \\
x_{21} & x_{22} & x_{23}& \cdots &x_{2d} & 1 \\
\vdots & \vdots & \vdots & \ddots & \vdots & 1\\
x_{m1} & x_{m2} & x_{m3}& \cdots &x_{md} & 1 \\
\end{Bmatrix}
·
\begin{Bmatrix}
w_1 \\
w_2 \\
\vdots \\
w_1d \\
b \\
\end{Bmatrix}
$$

矩阵 $X$ 的最后一列都是 1,这样的好处是和矩阵 $w$ 相乘时参数 $b$ 能起作用。上面式子的结果是一个 $m$ 列的的矩阵,每一列都是一个预测值,套用一下之前的误差函数,要让误差最小,也就是要使得这个式子取最小值:

$$min(Y-Xw)^T(Y-Xw)$$

对矩阵 $w$ 求导可以得到导数为零的值为:

$$
w^* = (X^TX)^{-1}X^TY
$$

虽然公式很简单,但是矩阵求逆并不简单,它的复杂度是 $O(n^3)$,比较难以接受。这是因为最小二乘法本质上还是一种数学方法,利用公式得出的结论或许很优雅,但并不一定利于计算。

梯度下降

考虑一座山的高度是位置的函数,即 $h = f(x, y)$,找到一组 $(x, y)$ 使得 $h$ 取最小值,实际上就是找到山谷处的坐标。为了简化计算量,我们希望能尽快的找到这个位置,否则把所有的 $(x, y)$ 可能的取值都遍历一遍,肯定能找到最小值,但这种做法毫无意义。假设我们站在山顶上,尽快找到山谷实际上就要求我们以最快的方式下山,我们都知道,选择最陡峭的路下山是最快的,如图所示:

梯度下降

梯度下降

陡峭是生活中对事物的形容,而数学中对应的概念则是梯度。梯度是函数最陡峭的方向,所以沿着负梯度的方向下降就是最快的。因此只要设好步长,每次沿着负梯度方向前进这个步长,再重新计算梯度、重新移动即可。经过一段时间的移动,就会走到山谷,如上图中黑色折线所示。

梯度下降的效果受到很多因素的影响,比如步长太小时下降速度太慢,补偿太大又会导致不够精确,错过最小值。再比如出发点的选择对最终结果也会有影响,比如上图中如果从右侧最高峰开始下降,极大概率会走到右侧淡蓝色的谷底。这是局部最小值,却不是全剧最小值。因此梯度下降在实际应用中会根据问题的特点略作一些调整,但总体思路是不变的。

数据划分与评价

就像学生既要学习,也要考试一样,在实际机器学习的过程中,不仅需要通过学习大量数据来得出模型,还需要一些数据来检验模型的好坏。我们把用于训练的那部分数据统称为训练集,用来验证的那部分数据则称为测试集。

有些无良老师在自己的辅导班里泄漏考试题目,导致交钱上过辅导班的学生考试成绩好,没上辅导班的学生成绩相对不好,正好成为老师威逼利诱他们上辅导班的理由。这种情况在机器学习中要避免发生,因此一般来说,一条数据不能既用来训练模型,又用来检测模型,否则根据这个数据训练出来的模型,必然在验证时取得比较好的成绩。

划分策略

一种常见的划分思路就是把原始数据按照一定的比例划分为训练集和测试集。比如一共有 100 条数据,80条用于训练,20 条用于验证。注意训练集不能过大,否则测试集太小会导致结果不准确。就像一个考卷一般都是 100 分一样,如果就一条选择题,偶然性就会非常高。但训练集也不能太小,否则模型并不一定训练充分,就像一个学生不能只做十道题就去期末考试一样。这个比例一般选择在75% - 80% 会比较合适。

另一种思路是把数据均匀的分成 $n$ 份,每次都用 $n-1$ 份训练,剩下的 1 份测试。这样做的好处是在数据不够的情况下提高了利用率。

还有一种思路是把每条数据想象成一个球,每次都有放回的取出一条数据作为测试集,有多少条数据就重复多少次。这样有的数据会被选中多次,也有的数据一次都不被选中,这也是一种比较公平、随机的方法。

小结

至此,我们解答了第一个问题,为什么 700W 这个预测更合理,这是因为我们根据误差函数的定义,找到了使误差函数取最小值的参数。基于这些参数得出了具体的模型,并将这个模型应用于新的数据上,得出了合理的结论。而模型的好坏则是通过训练集来验证的,避免了自问自答的不准确性。

超参数

模型由模型中的参数决定,一旦参数都确定下来,模型也就确定了。而确定参数的过程就是学习的过程,也是把误差函数最小化的过程。这个过程通常也有参数控制,比如梯度下降法中的步长和初始值。对于不同的步长和初始值,得到的模型肯定是不一样的。所以像步长和初始值这样的参数,其实是最终参数的参数,我们叫它超参数。

对于一个复杂的模型来说,参数的个数可以非常多。少的有成千上万,像一些大公司的核心产品,参数上亿也不是什么稀奇的事。但超参数的个数一定是有限的,因为超参数往往意味着人工调整。

理解了超参数,就可以回答第二个问题,为什么模型是线性的。实际上,线性模型可以是基于常识得出的,也可以是学习出来的。我们完全可以假设房价和面积是一个 $n$ 次多项式的关系,这样就需要多引入一些参数。只要数据足够,利用梯度下降总是可以学习出各个参数的值的。有极大的概率会发现高次项的系数都是 0,只有一次项系数和常数项不为零,这样模型就退化成了线性的。

特征

如果某个变量会影响问题的结果,我们就把这个变量称为问题的一个特征。比如对于房价来说,面积显然就是一个特征。对于彩票的开奖结果来说,日期肯定不是特征。

在解决一个现实中的机器学习问题时,肯定不像通过面积预测房价那么简单。很多时候第一步要做的就是从纷繁复杂的因素中找到问题的特征。这涉及到两个步骤,一是要确定特征的提取方式,而是判断某个因素到底有没有资格算得上特征。

在之前介绍梯度下降算法时,我们用函数的梯度来刻画陡峭程度,这种用数学公式来描述现实特性的做法在机器学习中非常常见,也非常重要。比如本节就会介绍如何使用简单优雅的函数来判断一个因素算不算特征,甚至是有多算特征。

特征搜索

提取特征时有几种常见的思路:

  1. 前向搜索:指的是从诸多因素中提取特征
  2. 后向搜索:指的是从诸多因素中排除特征
  3. 双向搜索:混合了前两者策略,既提取大概率是特征的因素,也排除小概率是特征的因素

需要注意的是,无论哪种策略都是贪心的,也就是说只能找到局部最优而不是全局最优。比如我们首先提取特征 $t_1$,接下来发现 $t2$ 比 $t_3$ 更像是特征。我们当然会选择 $t2$,但也许 $t1, t3, t4$ 才是真正的全局最优特征。但没有开启上帝视角的我们,在选择第二个特征时,是不可能知道这一点的。

信息熵

在判断一个因素是不是特征之前,我们需要掌握 信息熵 这个背景知识。我们都知道熵是用来表示混乱程度的,信息熵表示的就是信息的混乱程度。对于某个集合,不同元素出现的次数各不一样,它的信息熵定义如下:

$$Ent(D) = \sum_{k=1}^{|Y|}p_klog_2 \frac 1 {p_k}$$

这个公式的含义是计算每个元素出现的概率 $p_k$,和概率的倒数的对数,然后对所有的乘积求和。这样解释依然不够直观,我们举个例子来看。

假设一袋球里面有 5 个红球,5 个黄球,那它们出现的概率都是 0.5,根据公式,这袋球的信息熵是 $0.5log_22 + 0.5log_22$,刚好是 $1$。

假设另一袋球也有十个,不过是 9 个红球和 1 个黄球。根据公式,这袋球的信息熵是 $0.1 log_2 10 + 0.9log_2 1.1111$。我们知道 2 的四次方是 16,所以 $log_210 < 4$,以及 $2^{0.5} = 1.414...$,所以 $log_21.11111 < 0.5$,简单的计算就会发现这个式子的结果小于 $0.14+ 0.90.5 = 0.85$

可见九个红球一个黄球的信息熵更小。实际上,集合内元素分布得越平均,集合的信息熵就越大;元素分布越单一,信息熵就越小,如果集合内元素完全相同,则信息熵为 0。

信息增益

当一个集合拆成若干个子集后,子集的信息熵的平均是可能是降低的。这就像我们收拾物品,都会分门别类的摆放,摆放好以后房间就变得整齐了,这实际上就是利用划分子集来降低信息熵。

在某种划分方式下,集合的信息熵和子集的平均信息熵之间的差值被称为:这种划分方式下的信息增益,也就是这种划分方式能把信息熵降低多少,用公式来表达就是:

$$G(A) = Ent(D) - \sum_{v=1}^V \frac {|D^V|} {|D|} Ent(D^V)$$

这里的 $G(A)$ 表示集合 $D$ 在划分方式 $A$ 下的信息增益,$|D|$ 表示集合 $D$ 中的元素个数,因此减号右边的式子其实就是子集信息熵的加权平均数。

显然信息增益越大的划分方式越好,如果以某个因素为划分方式带来的信息增益最大,那么这个因素最有可能是一个特征。

特征权重

我们都知道,如果同类的数据都具备某个特点,这类数据的特征权重就非常高。比如大房子都贵,小房子都便宜,那么 面积 这个特征的权重就高。但晴天买彩票可能中奖,雨天买彩票也会中奖,因此天气就是彩票中奖的一个权重非常小的特征,因为它无法有效的区分是否中奖。因此,如果不同类的数据都具备某个特点,这类数据的特征权重就非常低。

我们假设 $x_i^j$ 是第 $i$ 组数据的第 $j$ 个特征,$x_{i, nh}^j$ 表示和 $x_i$ 最近的某个同类数据。如果 $x_i^j$ 和 $x_{i, nh}^j$ 的第 $j$ 个特征相同,$same(x_i^j, x_{i, nh}^j)$ 函数取 1,否则取 0。类似的,$x_{i, nm}^j$ 表示和 $x_i$ 最近的某个不同类数据。基于上述定义,第 $j$ 个特征的权重可以表达为

$$W_j = \sum_i same(x_i^j, x_{i, nh}^j)^2 - same(x_i^j, x_{i, nm}^j)^2$$

可以看到,如果同类数据的特征类似,减号前面的表达式值就大,特征权重就高。如果不同类数据的特征都类似,减号后面的表达式值就大,特征权重就低。计算出特征权重后,可以划一个阈值,所有高于阈值的特征都采纳,或者所有低于阈值的特征都抛弃,亦或者只采纳权重最高的前 $n$ 个特征。

过拟合

如果之前预测房价时,我们用的数据不是面积,而是买房者的年龄,还能不能得出模型呢?从直觉上讲,肯定不行,因为常识告诉我们房价和买房年龄没有关系,有年轻的富二代一掷千金买豪宅别墅,也有辛苦了一辈子的无产阶级掏出毕生积蓄买一套蜗居。对应到图形上来说,如果横轴换成买房者年龄,纵轴还是房价,数据所对应的点应该是均匀的分布在平面内的,不会成一条明显的直线。

但如果我们用机器学习的算法去学习,必然会得到答案,这是因为用大量的数据去拟合一条低维曲线非常容易。虽然均匀分布的点无法用直线去拟合,但逐渐增加维度,一次的直线不行就用二次的抛物线,抛物线不行就用三次、四次……函数,随着维度的增加,曲线会越来越曲折、不平滑,但对数据的拟合效果是在增加的。如下图最右所示:

但这种拟合是没有意义的,因为尽管它对训练数据的拟合效果非常好,如果我们用 switch ... case 去写甚至能做到 100% 的准确率,但在测试集的表现是非常糟糕的,因为它完全没有学习到影响房价的特征。这样的拟合被称为过拟合

需要注意的是,过拟合不仅仅在选择了错误的特征时会出现,正确的特征如果不对学习过程做一些控制和干预,也会过拟合。比如我们用白色的天鹅图片去训练模型,最终模型很可能认为天鹅都是白的,导致不认识黑色的天鹅。总的来说,过拟合通常由于学习到与问题无关的噪音特征导致。

小结

为了解释开篇提到的三个问题,我们介绍了很多概念和公式。至此,这三个问题应该已经有比较明确的概念了,如果下面的解释你觉得难以理解,恐怕得回去找到对应的章节再阅读一遍了,因为这些都是最基本的概念。

  1. 凭什么就预测价格是 700W 呢,如果我就是喜欢抬杠,我偏说价格是 750W 你们服不服?
    首先,我们让误差函数最小化,得出了模型,并且利用模型计算出了 70 平这个新数据的预测结果,而且这个模型的优劣可以用训练集数据来验证。这样得出的结论显然比随口报的数更准确,更有说服力。

  2. 为什么我们从直觉上就觉得房价和面积是线性的关系,为什么不去猜一个二次函数?
    尽管是从直觉上猜测,但也可以假设不是线性的关系,只需要把模型的参数设计的复杂一些就可以。最终都会学习出相似的结果。

  3. 怎么证明这个预测结果是合理的?
    我们从正反两方面解释了结果的合理性。首先通过信息增益和特征权重的概念证明了面积是房价的特征,只要找到问题的特征就可以基于统计学去学习。其次,过拟合的例子解释了为什么对不是特征的因素进行学习是没有意义的。

因此,如果这篇文章只能让你记住一句话,我希望是下面这句

机器学习只能从数据中提取客观存在的规律,不能凭空创造规律。

这就是为什么机器学习可以预测房价,但不能用历史开奖结果去预测下一次中奖号码。

机器学习的分类

在通过面积预测房价这个例子中,我们把房价称为标记,它类似于学生做题时的参考答案。标记用来和预测结果做比对,从而驱使我们优化模型。但并不是所有机器学习都需要标记,比如我给出一千篇文章,需要对它们做分类。计算机可能会把他们分为体育类、财经类、时政类……,但这并不要求计算机知道体育、财经的具体含义,它只需要知道某些文章是属于同一类的即可,至于这个类型是否具备人类可理解的含义,这并不重要。

如果训练数据是有标记的,我们把对它的学习称为 有监督学习,反之则是 无监督学习。就像学生做题需要比对参考答案一样,无监督学习 一般比 有监督学习更难一些。无监督学习主要涉及聚类算法,在后面的章节中我会简单介绍一些。

还是在预测房价这个例子中,我们用连续的曲线去拟合离散的点,这种做法叫做回归。监督学习还有一类常见的问题是分类问题,比如给一些西瓜的数据和标记,问一个青绿色、薄皮、敲击声音响的西瓜是不是好瓜?

可见如果预测结果是连续的,这就是回归问题;如果预测结果是离散的,这就是分类问题,分类问题和回归问题一般是可以互相转化的, 比如求某个西瓜是好瓜的比例,这就成了回归问题。

回归模型的好坏可以用误差函数来评价,分类问题也有类似的评价方式,比较常用的是查全率查准率 的概念。

分类性能衡量

我们简化一下问题的模型,假设某个数据需要预测真假。当然,它实际上一定是真的或者假的。这样就会出现四种可能的情况:

  1. 模型预测是真的,实际上也是真的,记为 A
  2. 模型预测是假的,实际上确是真的,记为 B
  3. 模型预测是真的,实际上确是假的,记为 C
  4. 模型预测是假的,实际上也是假的,记为 D

在实际预测时,会出现两类问题。比如明明某个数据是真的,但被模型预测成了假的,这对应第 2 种情况。为了衡量我们的模型查找有多全面,也就是所有真的结果中有多少被找出来了,可以定义查全率 R(Recall):

$$R=\frac A {A+B}$$

还有时候,明明某个数据是假的,但被模型预测成了真的,这对应第 3 种情况。为了衡量我们的模型正确率有多高,也就是找出来的结果中有多少是正确的,可以定义查准率 P(Percision):

$$P = \frac {A} {A+C}$$

PR 曲线

一般来说,查全率和查准率是互相矛盾的,对一者的提高往往意味着降低另外一者。这很好理解,俗话说做得多错的多,啥都不做就肯定不会犯错。为了衡量某个模型的好坏,我们需要综合考虑查全率和查准率,于是就有了 PR 图:

Alt text

Alt text

图中的 A、B、C 三条曲线分别对应了三种模型,一般来说如果某个模型(比如图中的 A)的 PR 曲线完全包围了另一个模型(比如图中的 C)的 PR 曲线,我们就称这个模型(A)好于另一个模型 (C)。这是因为在查全率相同的情况下 A 的查准率高于 C,在查准率相同的情况下 A 的查全率也高于 C。

但模型 A 和 B 就属于各有千秋,不是很容易比较了。这时候我们可以选择两种最简单的策略。一种是计算曲线和 XY 轴围成的区域的面积(AUC:Area Under Curve),也就是对 PR 曲线求积分,谁的积分大谁就更优。另一种策略是计算平衡点的坐标,平衡点是指 $P = R$ 的点,也就是 $y = x$ 这条直线和 PR 曲线的交点,交点更靠外的模型被认为更优秀。

当然,在实际工作中,查全率和查准率的权重并不总是相同的。比如推荐系统,更看重查准率,也就是说推荐得东西少了不要紧,但一定要是用户感兴趣的,否则体验就很差。但对于图像识别逃犯的系统来说,查准率并不重要,因为可以人工排查,但漏过了犯罪分子就是不可接受的。所以我们还会基于查全率和查准率,定义更复杂的公式来衡量模型的好坏。

常见应用

对机器学习名词和概念的介绍就到此为止了,为了避免纸上谈兵,也为了让读者对实际的机器学习过程有更直接的感受,下面介绍一些常见的机器学习算法及其应用场景。

决策树

作为有着二十多年吃瓜经验的专业吃瓜群众,假设我们去买西瓜。可能上来就先敲一敲,声音响亮的是好瓜的概率比较大, 然后再看颜色,最后看形状。这种挑选西瓜的过程可以用决策树来表示,根节点是对敲击声音的判断,第二层判断颜色,第三层看形状,最后得到多个叶子节点,标记了瓜的好坏。

但这种做法有两个小问题:

  1. 凭什么先听敲击声音而不是看颜色或者形状?
  2. 上述决策树很简单,但如果影响西瓜好坏的因素比较多,叶子节点的数量是以指数形式增加的。而且我们上面的决策树其实是枚举了所有的可能性,只是一种 switch ... case,貌似和机器学习没啥关系。

第一个问题很好回答,从直觉上讲,敲击声能更好、更有效的判断西瓜的好坏。这种直觉用数学公式来衡量就是上文提到过的信息增益,往往决策树越上层的分类,带来的信息增益越高。

随着决策树的向下延伸,信息增益减少意味着区分度不是很高,此时我们可以考虑用剪枝来简化树的结构,减少复杂度,同时还能避免过拟合。剪枝策略分为两种,一种叫预剪枝,另一种则是后剪枝

假设西瓜已经分为了敲击声响亮和沉闷两种类型,我们接着对敲击声响亮的西瓜根据颜色来分类。首先可以假设敲击声响亮的西瓜都是好瓜,当然,这种假设肯定是不准确的,经过测试集的验证可以得出一个准确率 $p_1$。接下来我们根据颜色来把西瓜分为若干类并给每类假设一个结果,好瓜或者坏瓜。这种假设当然也是不完全准确的,甚至可能比之前更不准确。我们用测试集再验证一次,得出概率 $p_2$,如果细分后得出的准确率 $p_2$ 并不高于不细分时的概率 $p_1$,就说明细分的意义不大,分支可以被减掉。或者准确的说,没必要生成。这就是预剪枝

我们还可以先根据已有数据生成决策树,然后自底部向顶部遍历,对比每一颗子树减掉前后的概率。如果概率能提高,就进行剪枝。这就是后剪枝

如果剪枝前后的概率一致,预剪枝更倾向于剪枝,而后剪枝更倾向于保留。所以预剪枝一般比较快,剪枝结果比较简单,但容易欠拟合,缺少分支条件。而后剪枝则恰好相反,速度慢,结果比较复杂全面,容易过拟合。

支持向量机

考虑下图中用正负号标记的两组数据,如果要选择一条直线把他们划分开

显然虚线范围内的任何一条线都满足要求。但这两条虚线并不是最好的划分方式,因为他们的泛化能力很弱,或者说鲁棒性不够好,也许来了一个新的数据就不能正确划分了。

为了描述划分方式的泛化能力,我们计算样本到直线的距离,并想办法让距离最大。因为距离越大,意味着容错能力越强,正确处理新数据的几率也就越高。最好的划分方式如下图所示:

超平面

我们把这条直线称为二维数据的超平面。对于二维的数据来说,它的超平面是一维的直线。三维空间里的超平面则是二维的平面,拓展到 $n$ 维空间,它的超平面是一个 $n-1$ 维的空间,把原来 $n$ 维的空间刚好分成两部分。

支持向量与间隔

上图中虽然两类数据各有很多个,但是绝大多数远离直线的数据并不会对直线的选择产生任何影响。只有少数几个靠近直线的数据才会起作用,比如图中标红的点,我们把它叫做 支持向量

支持向量到超平面的距离被称为间隔,或者严格来说,叫硬间隔,硬间隔一个很大的问题是对噪声特别敏感。试想一下,假设我们新增一条数据,位置靠近白色实线,此时重新计算超平面,位置一定会发生较大幅度的变化。

但实际上,偶尔一两条数据位置比较奇怪的数据可以被当做噪声忽略掉,不需要影响到最终的结果。如果我们允许一定比例的数据落在间隔以内,这样的间隔就被称为 软间隔

核函数

超平面希望能够把数据所在的空间一分为二,但有时候是做不到的。比如异或,它的数据分布就无法用一条直线来分割。此时我们可以考虑找一种映射关系,把低维不可分的数据转换为高维可分的数据,如下图所示:

这种转化方式被称为 核函数(严格意义上的核函数并不是映射关系,而是经过处理和计算后的某个表达式,但这并不重要)。

贝叶斯分类

如果说决策树和支持向量机还比较抽象,那么希望读者能认真理解贝叶斯分类算法,因为它既通俗易懂,也容易实现。

后验概率

很多教程上都会提到后验概率这个名词,和它相对的就是先验概率。先验概率非常好理解,比如我扔出一个色子,六点朝上的概率就是 $\frac 1 6$,有时候天气预报说明天下雨的概率是 $50\%$,这些都是先验概率。

先验概率指的是根据经验或者已有的数据观察出的概率,而后验概率则是指当某件事发生后,求可能影响结果的某个因素的发生概率。比如袋子里有 3 个红球和 2 个白球,每次摸出一个球并且不放回。已知第二次摸到的是红球,请问第一次也是红球的概率。这就是后验概率。

我们首先感性的认识一下后验概率的意义,也就是为什么第二次拿出求的颜色会影响第一次拿出红球的概率呢?实际上,第一次取出的球有 5 种可能,每一种情况下第二次取球又有 4 种可能,所以样本容量是 20。如果只考虑第一次取出红球的概率,那么第二次取出的颜色不重要,也就是说第一次取出的各种可能,权重是相同的,因此取出红球的概率是 $\frac 3 5$。但如果限制了第二次取出的是红球,样本空间的大小就不是 20 了,简单的计算一下发现满足要求的样本一共有 12 个,其中六个样本第一次取出的是红球,因此概率变成了 $\frac 1 2$。

top Created with Sketch.