【机器学习】（4）：监督式学习

     机器学习中监督式学习是非常重要的一类，因为ML的主要出发点是利用获得的数据来补偿未知的知识，所以从训练集出发学习数据中的模式规律就是最为自然的一类 情况。今天开始自己决定利用两周左右的时间，来记录整理自己学习机器学习的笔记，主要的参考资料是Ethen Alpaydin的《机器学习导论》，如有错误或疏漏，还请各位童鞋批评指正。今天主要来宏观地谈谈监督学习，大致的要点如下：

1. 一个监督式学习实例；

2. 监督式学习算法的维；

3. 学习算法的能力--VC维；

4. 学习算法样本量的确定--概率逼近；

      好了，长话短说，下面我们来介绍机器学习中的监督式学习。

一、一个监督式学习实例

      从一个例子着手是最为形象最为容易理解的，比如现在我们有一个判断“家用汽车”的任务，具体根据汽车价格和发动机功率两个特征进行判断，实际中也许有更多 的因素，在这里为了简单起见我们暂且只考虑这两个特征。算法的任务是通过训练集的学习，能够对一个新的样本进行判断是否是“家用汽车”。我们可以将认为是 家用汽车的标记为正例（Positive Example），其他的都被标记为负例（Negative Example），类学习就是要找到一个包含所有正例但是不包含任何负例的描述。

      上面的公式描述了我们这个实例，向量x的两个分量分别表示汽车价格和发动机的功率，而向量r则表示输出，当为正例时输出1，负例时输出0；第一个集合表示N个样本训练集，每个元素都由样本特征x和标准判断r组成。我们现在的目标是可以找到一个算法，可以通过训练集找到某个分类方法，适用于所有的训练集（包含所有正例但是不包含任何负例），然后利用这个分类方法去预测判断新的样本。

      这里在具体实现的时候，人们往往首先要有一个假设类（Hypothesis class），比如可以采用一个矩形集合（假定位于某个价格区间且同时位于某个发动机功率区间的汽车为家用汽车，即一个判别式），来包含所有的正例，同时 却不包含任何的负例。符合这样条件的矩形可能有多个，因此存在一个最小的矩形，即最特殊的假设（most specific hypothesis），比如S，再小就会有一个正例不包含在假设中；同时也存在一个最一般的假设（most general hypothesis），比如G，再大的假设就会包含一个或多个负例。因此我们寻找的假设应该位于S与G之间。一般认为可以选在S与G的中间，因为这样可 以获得较大的边缘（margin），所谓边缘就是边界和它最近的实例之间的距离。

      由于在S与G之间存在多个可用的假设，但是不同的假设对于新的样本可能做出不同的预测和判断，因此这便引出了泛化（generalization）的问题，即我们的假设对不在训练集中的未来实例的分类的准确率如何。

二、监督式学习算法的维度

      监督式学习简单来说就是通过训练集让计算机学习数据间的规律和模式，然后以此进行分类和回归预测。训练集的表示就如同上面的结合X， 其中样本应当是独立同分布的，对于分类而言，两类学习输出就是0和1，而K类学习就是一个K维向量，其中只有一个分量为1，其余分量均为0，这个要求也就 是说任何一样本最多只能属于一个类别。对于回归而言，输出是一个实数值。可以这样简单地来区分分类和回归问题：分类输出是离散值，而回归输出是连续值。下 面我们来看看监督式学习的维度， 也就是监督学习的基本步骤。

1. 确定假设类，比如假设了函数模型G(x,A)，A表示一个参数向量，而x表示我们的样本输入，我们通过训练集学习确定最好的A，使得假设可以对新的样本进行判断；

2. 满足训练集的假设可能会有很多，因此我们要选择最合适的那个，标准就是一个损失函数L（Loss Function），比如L是x与G(x, A)的平方差或者绝对值，用于表示我们的假设与训练集的差异，我们寻求最小的那个。当然，损失函数还可以有其他的定义，但是基本思想都是用来表示假设与训练集数据的差异；

3. 有了损失函数L，接下来我们就进入了最优化过程，即使得L最小，这一步有多种方法可以实现，比如将L对所有的特征分量求偏导数，确定极小值；或者使用梯度下降、模拟退火以及遗传算法等。

      不同的机器学习方法的之间的区别，要么是假设类不同（假设模型或归纳偏倚），要么是所使用的损失函数不同，再者就是使用的最优化过程不同。可以说，假设模型、损失度量和最优化过程是机器学习的三个基本维度。

三、学习算法的能力--VC维

      学习算法的能力通过VC维度来度量，即一个假设类散列的数据点的个数。假定一个数据集中有N个数据点，对于正例和负例的判断而言，就有2的N次方种不同的学习问题，如果对于这些学习问题中的任何一个都可以找到假设类H中的一个假设h可以将正例和负例分开，我们就称该假设类H散列这N个点。因此VC维度量假设类的学习能力。

四、学习算法样本量的确定--概率逼近

      概率逼近主要用于针对特定的假设类，确定最少需要多少样本量就可以保证学习的结果获得一定的置信率，其实也就是说如果我们想达到一个较好的假设，那么最少需要多大的训练集呢？根据我们期望的置信率和不同的假设，我们可以计算其概率逼近的最小样本量。

      好了，今天的基本概念就到这里，明天继续！

Refer：

《机器学习导论》，Ethen Alpaydin（土耳其），机械工业出版社