2.1 基础知识

2.1.1 二分类

二分类（Binary Classification）问题是将一组数据按照某个规则分为两类：用h（x）=1表示正类，用h（x）=-1表示负类。具体的二分类例子包括正射线、正间隔、一维感知器和二维感知器，具体介绍如下所示。

本章在证明机器学习是可行的同时，仅以二分类问题来举例。细心的读者可能会看出来，在上面的例子中，红心和绿圆正好是线性可分的，但是在有些情况下样例是线性不可分的，如下图所示。

左图所示的4种二分类问题根据其定义都不可能用一条直线把红心和绿圆分开，而我们感兴趣的是，对于每个二分类问题，在什么情况下n个样例能被线性对分？

2.1.2 对分

假设数据集中包含n个样例，每个样例可以被分为两类，n个样例就有2ⁿ种分类结果。例如，当n=2时，正类为红心，负类为绿圆，将两个点分别设为红心或绿圆，则一共有2²=4种分类结果。

假设之后经过某种操作H将红心和绿圆线性分开，则这种操作被定义为对分（Dichotomy）。如下图所示，对分操作可以被看成是用一条直线把红心和绿圆分开，两个样例的对分结果一共有4种。

因此，n个样例的对分结果最多有2ⁿ种，但是通常会少于2ⁿ种。

下面分析2.1.1节介绍的4种二分类问题的对分结果有多少种。这里将对分结果定义为d_H（n），其中H是某种对分操作，n是数据的个数。

下表中总结了各种二分类问题的对分结果种类d_H（n）。

2.1.3 增长函数

由于对分结果d_H（n）在固定为n个样例的情况下可能有多个值，比如在二维感知器有3个样例的情况下，d_H（3）等于6或8，这3个样例不同的分布情况如下图所示。

m_H(n)=max (d_H(n))

这样看来，在进行对分时有一点麻烦，因为对分不仅与样例的个数n有关，还与样例的分布情况有关。我们定义一个只与n有关的函数：增长函数（Growth Function），它取每个n在对分时的最大值。

增长函数值越大，则操作H的表示能力越强（后来我们把这个操作H定义成机器学习的假设空间H），其复杂度越高，模型学习任务的适应能力也越强。下表中总结了各种二分类问题对应的增长函数。

2.1.4 突破点

假设经过某种操作H，能实现数据集上所有数据的对分，则称此数据集能被这个操作H打散（Shatter）。既然能实现所有数据的对分，那么打散时对应的增长函数为2ⁿ。下图所示的就是一个将两个样例（点）打散的案例，这里实现了所有点的对分，增长函数为2²=4。

打散的概念固然重要，但理解“不打散”的概念更加重要。第一个没被打散的k点被称为突破点（Break Point）。下图中展示了各种二分类问题没有被打散的情况。

正射线：不能打散这样的两个点，因为红心一定要在绿圆右边，突破点k=2。

正间隔：不能打散这样的3个点，因为红心一定要在绿圆中间，突破点k=3。

一维感知器：不能打散这样的3个点，因为红心或绿圆一定要连在一起，突破点k=3。

二维感知器：不能打散这样的4个点，突破点k=4。

二维感知器在有3个点的情况下不是也不能被打散吗？为什么突破点不是3呢？因为也有3个点能被打散的情况，只要有一种情况能被打散就属于能被打散。而4个点在各种情况下都不能被打散，因此突破点是4。

下表中总结了各种二分类问题的突破点。

从上表中可以观察出增长函数m_H（n）是n阶多项式，而n小于k-1，比如，

● 正射线m_H（n）是一阶多项式，而突破点k=2，即k-1=1。

● 正间隔m_H（n）是二阶多项式，而突破点k=3，即k-1=2。

● 一维感知器m_H（n）是一阶多项式，而突破点k=3，即k-1=2≥1。

那么二维感知器的增长函数m_H（n）也是k-1阶多项式吗？