浅谈机器学习基础（上）

2017-02-18 本文已影响20968人我偏笑_NSNirvana

注：题中所指的『机器学习』不包括『深度学习』。本篇文章以理论推导为主，不涉及代码实现。

前些日子定下了未来三年左右的计划，其中很重要的一点是成为一名出色的人工智能产品经理，说是要每月至少读一本人工智能相关书籍，现在一个半月过去了，书读了一些，资料也看了不少，算是小有所成，所以希望分享一些内容出来，既是对自己的督促总结，将自己学到的东西整理妥当，也是希望把我在做的事情说出来，以期结识同好。

本篇文章在整理时主要参考了 Peter Harrington 的《机器学习实战》。

机器学习简介

Arthur Samuel非正式的定义过，机器学习是在不直接针对问题进行编程的情况下，赋予计算机学习能力的一个研究领域。

简单的来讲，我们给计算机足量的数据，这些数据可以是已标注过判定结果的（监督学习），也可以是没有经过标注的（无监督学习），计算机从这些数据中抽象出模型，也即可以看做发现这些数据的之间的规律与联系，然后当训练完成后，给予其训练集之外的数据（测试集），计算机就能『举一反三』，根据学习训练样本所得到的模型，去预测测试样本的相关属性。

我们根据训练样本以及所需解决问题的不同选择恰当的机器学习算法，建立恰当的模型，以求得到最好的预测效果。

这里我采用吴恩达博士的分法，将机器学习分为四类：监督学习、无监督学习、强化学习、迁移学习。

监督学习：是利用已知类别的样本（即有标记的样本 labeled sample，已知其相应的类别），调整分类器的参数，训练得到一个最优模型，使其达到所要求性能，再利用这个训练后的模型，将所有的输入映射为相应的输出，对输出进行简单的判断，从而实现分类的目的，这样，即可以对未知数据进行分类。
通俗的来讲，我们给计算机一堆选择题（训练样本），并同时提供了它们的标准答案，计算机努力调整自己的模型参数，希望自己推测的答案与标准答案越一致越好，使计算机学会怎么做这类题。然后再让计算机去帮我们做没有提供答案的选择题（测试样本）。

无监督学习：实现没有有标记的、已经分类好的样本，需要我们直接对输入数据集进行建模，例如聚类，最直接的例子就是我们常说的『人以群分，物以类聚』。我们只需要把相似度高的东西放在一起，对于新来的样本，计算相似度后，按照相似程度进行归类就好。
通俗的来讲，我们给计算机一堆选择题（训练样本），但是不提供标准答案，计算机尝试分析这些题目之间的关系，对题目进行分类，计算机也不知道这几堆题的答案分别是什么，但计算机认为每一个类别内的题的答案应该是相同的。

强化学习：所谓强化学习就是智能系统从环境到行为映射的学习，以使奖励信号(强化信号)函数值最大，强化学习不同于连接主义学习中的监督学习，主要表现在教师信号上，强化学习中由环境提供的强化信号是对产生动作的好坏作一种评价(通常为标量信号)，而不是告诉强化学习系统RLS(reinforcement learning system)如何去产生正确的动作。
通俗的来讲，我们给计算机一堆选择题（训练样本），但是不提供标准答案，计算机尝试去做这些题，我们作为老师批改计算机做的对不对，对的越多，奖励越多，则计算机努力调整自己的模型参数，希望自己推测的答案能够得到更多的奖励。不严谨的讲，可以理解为先无监督后有监督学习。

迁移学习：考虑到大部分数据或任务是存在相关性的，所以通过transfer learning我们可以将已经学到的parameter 分享给新模型从而加快并优化模型的学习不用像之前那样learn from zero。把已学训练好的模型参数迁移到新的模型来帮助新模型训练数据集。

深度学习是机器学习的一种，是一种『抽象出的模型』在结构上比较特殊（有深度且可以堆叠，比如各类神经网络）的机器学习方法。深度学习将在下一篇文章中详谈，本文将不会主要涉及。

监督学习

k-近邻（kNN）算法

一句话概要，将标注好类别的训练样本映射到X（选取的特征数）维的坐标系之中，同样将测试样本映射到X维的坐标系之中，选取距离该测试样本欧氏距离（两点间距离公式）最近的k个训练样本，其中哪个训练样本类别占比最大，我们就认为它是该测试样本所属的类别。kNN是监督学习算法。

kNN的缺点在于计算的时间空间复杂度都太高，首先内存中需要存储所有的训练样本点，而且每个新测试样本需要通过kNN算法分类，都要计算这个测试样本与所有训练样本点的欧式距离。

kNN可以处理数值型（从无限的数值集合中取值，如0.100，42.001等）和标称型（只在有限目标集中取值，如真与假）数据。一种特征对应一个维度，一种特征下的数据可以数值型的也可以是标称型的。

第一个例子，利用kNN来优化婚恋网站配对效果。

A是某婚恋网站的忠实会员，她在这个网站上约过很多很多人，她把这些人分为3类：不喜欢、感觉一般、很有好感。她希望在下次约会之前能够根据网站上已有的信息预测一下对方会不会是自己很有好感的类型。

她选出了3种特征（三个维度）：每年的飞行里程公里数、每周玩游戏所花费的小时数、每周吃掉的零食的斤数。

她过去约过1000个人，每个人相当于1个训练样本，这个训练样本有4个属性（3个特征值、1个类别），比如：
B: 4000公里、2小时、1.5斤、很有好感
C: 200公里、22小时、5斤、感觉一般

我们拿3种特征做成一个三维的坐标系，依照每个训练样本的各个特征值，把这1000个训练样本标到这个三维坐标系的对应位置（更高维度也同理）。也即完成了训练过程。

接着，A又认识了一个新人D：4800公里、1小时、0.5斤，A把D作为一个点标到了之前训练好的那个三维坐标系上，发现距离D最近（利用欧氏距离公式计算）的10个人（这里取k=10）当中，有8个人都是『很有好感』一类的，所以A觉得，D有很大可能性也会是『很有好感』一类。

上面的理论很简单，但是存在一个小问题，我们知道欧氏距离公式会极大地受到数值本身大小的影响，比如两个人的飞行里程可能很容易就相差2000，但吃掉的零食斤数最多可能也就差10，这样算出来的距离就几乎只受飞行里程影响，而对于A来说，3个特征是同等重要的。为了解决这个问题，我们需要对这三个特征的特征值进行归一化处理，使得它们的取值范围都落在0到1之间。比如用（当前值-最小值）/取值范围。

第二个例子，我们尝试用户kNN做手写数字（0到9）的图像识别。这看起来似乎比较难，但是所用的原理与上例相同。

手写数字的图片是32x32的，我们将它转成一个32x32的数字矩阵，留下笔迹的地方是1，空白的地方是0。

我们有2000张这样32x32的手写数字的数字矩阵，还有每张手写数字数字矩阵的类别，也即写的到底是几。

我们取32x32=1024个特征，每个特征只有两个值，0或1。我们把这2000张手写数字数字矩阵标进这个1024维的坐标系中（过高维度没办法实际去画图，只为了理解）。也即完成了训练过程。

接下来我们拿到了一张新的手写数字图片（32x32），把它转成一个32x32的数字矩阵，进而我们知道了它在这1024维度中，每个维度上的值。然后我们利用欧氏距离公式计算，离它最近的k个点中，出现次数最多的类别是什么，也即推测出了这张手写数字写的究竟是几。

决策树ID3算法

一句话概要，决策树算法的核心在于决策树的构建，每次选择让整体数据香农熵（描述数据的混乱程度）减小最多的特征，使用其特征值对数据进行划分，每次消耗一个特征，不断迭代分类，直到所有特征消耗完（选择剩下数据中出现次数最多的类别作为这堆数据的类别），或剩下的数据全为同一类别，不必继续划分，至此决策树构建完成，之后我们依照这颗决策树对新进数据进行分类。

决策树长什么样？

决策树示例

决策树算法较之于kNN算法一个很显著的不同在于，kNN算法需要持续使用全部的训练数据，而决策树算法经过训练构建出决策树之后，就不再需要将所有的训练样本保持在内存中了，这颗决策树就是在训练样本中抽象出来的模型。

香农（信息）熵用来描述数据的混乱度，混乱度越大熵越大，计算公式如下：

分类前整个数据集的熵

Pi指第i种数据在这个数据集中所占的比例。
定性理解，如果这个数据集中所包含的数据类别越少，它的熵也就越小（熵是正数，因为对数算出来的结果是负数）。
如果我们将这个数据集按照数据的某个特征（不是按数据类别分，因为我们做的是学习+预测，不是对训练样本分类）进行了分类，分成了多个小数据集，那整个数据集熵的计算公式如下：

按某种特征分类后整个数据集的熵

我们需要知道按照这个特征分类过后，整个数据集的熵减少了多少，也就是信息增益是多少，计算公式如下：

信息增益

信息增益越大，也就是我们对数据的分类越有效，整个数据集的熵减小的越多。

在整个数据集的基础上，挑选使熵减小最多的特征对数据集进行分类，将整个数据集按照上一步所选定的特征的特征值分成多个（可以超过2个）小数据集，然后对每个小数据集重复进行以上的操作，直到某个小数据集内部数据的数据类别全部相同，或者没有可以继续分类的特征了，这个时候我们把剩下的数据集里面出现最多的数据类别作为这个小数据集的类别。

然后我们就得到了一颗决策树，当需要处理新样本的时候，我们按照决策树对特征的使用顺序和新样本的各个特征值，逐步对这个样本进行分类，直到决策树的叶子节点处，最后这个叶子节点数据集的数据类别就是我们根据决策树算法所推断出来的新样本的数据类别。

朴素贝叶斯分类算法

一句话概要，朴素贝叶斯算法普遍用在文本处理中的垃圾邮件过滤，先计算联合概率分布，然后再利用贝叶斯公式计算给定某个样本数据后，被分到每个类别的概率分别是多少，然后取被分到概率最大的类别作为该样本数据的类别。朴素贝叶斯算法是生成方法，而前面讲过的两种算法是判别方法（后面会详细讲）。

朴素贝叶斯算法的『朴素』在于这样一个假设，每个单词（特征）出现的可能性是完全独立的，和其他单词是否出现、出现在哪无关。朴素贝叶斯算法的另一个假设在于，每个单词（特征）对于判定整条文档的类型同等重要。这两个假设都是有瑕疵的，某些单词就是大多同时出现，判断一条文档的基本类别也不需要阅读整条文档的每一个单词，但是即使这样，朴素贝叶斯算法在实际应用中的表现也是很好的。

什么是贝叶斯公式？

贝叶斯公式

贝叶斯公式是概率论中一定会讲到的内容，这里c和x均指『某种情况』，而p(c)、p(x)指发生这两种情况的概率，p(x|c)指在已知c情况发生的条件下x情况发生的概率，p(c|x)同理。

举个例子，我们有三个棋子、两个碗，第一个碗里一个黑子一个白子，第二个碗里只有一个白子，我们要计算已知取到白子的情况下，这个白子是在第一个碗里取出的概率，如果用贝叶斯公式计算，我们先算分母，取到白子的概率是3/4，再算分子，取到第一个碗的概率是1/2，在取到第一个碗的前提情况下，取到白子的概率是1/2，最后算出已知取到白子的情况下，这个白子是在第一个碗里取出的概率是1/3。想一想，是不是如果不断的抽棋，抽到的白子更多的来源于第二个碗，抽到第二个碗里的白子的情况已经占到所有情况的1/2了，剩下的1/2还要分一半给第一个碗里的黑子。

在朴素贝叶斯算法中，我们用到的贝叶斯公式是经过拓展的：

拓展后的贝叶斯公式

在朴素贝叶斯分类算法中，我们通常用c代指『文档属于某种类别』这种情况，用w向量代指这个文档本身，w0、w1···这些用来表示文档中是否含有（或含有几个，是否含叫做词集模型，含有几个叫做词袋模型）某特定单词（在朴素贝叶斯算法中，所有的训练文档中出现过的所有单词去重的数量，就是w所包含的维度个数，w相当于一个单词表）。

以垃圾邮件过滤举例讲整个朴素贝叶斯算法的流程。

首先是建立单词表（也就是建立w）和用单词表表示所有的训练文档。我们遍历所有的训练文档，把所有出现过的单词去重放进一个数组里面。然后用这个单词表w表示我们所有的训练文档，每条训练文档被表示成和单词表数组等长的一个数组，如果是词集模型，就用0、1分别表示对应位置的单词在这条文档里是否出现，如果是词袋模型，就用对应位置的数字表示对应位置单词的出现次数，这个数组叫做这条文档的词向量。同时我们的朴素贝叶斯算法是监督学习算法，我们还需要有一个标注数组，这个数组的大小和训练文档的条数相同，用于记录这些训练文档哪几条是垃圾邮件，是的标0，不是的标1。

我们用p(c0|w)和p(c1|w)分别代表这个词向量所对应的文档属于垃圾邮件或正常邮件的概率，如果p(c0|w) > p(c1|w)那我们就认定其为垃圾邮件。

当接到新文档后，先将其转化为词向量，然后代入贝叶斯公式计算，根据贝叶斯公式，需要求出p(c0|w)和p(c1|w)，因为分母p(w)对于该条文档来讲是个常数，与c取c0还是c1无关，所以可以不计算，只需要计算分子p(c)和p(w|c)。p(c0)、p(c1)分别代表文档是垃圾邮件和正常邮件的概率，这个很好算，用前面的标注数组就能算出，也就是用训练文档是垃圾邮件和正常邮件的概率来代替。

然后我们只需要计算这个新文档的p(w|c0)和p(w|c1)，也就是c0（垃圾邮件）和c1（正常邮件）中出现该文档的概率（即该文档所包含的每个单词出现概率的乘积，文档中几次出现该单词，就乘以几次这个单词的出现概率），即可根据p(w|c)乘p(c)的大小判定该样本的类别。

新样本的p(w|c0)和p(w|c1)如何计算？上面说了，是用两种邮件的训练样本中每个词（包含在新样本中的每个词）出现概率的乘积求出，那两种邮件的训练样本每个词出现的概率怎么求？我们把之前的训练文档按照垃圾邮件和正常邮件分开处理，用每个词的出现次数（这里用词袋模型）除以总词数，即可得出垃圾邮件和正常邮件训练样本中所有单词的出现概率，然后根据单词在新样本中的出现次数，将其出现概率相乘，得到新文档的p(w|c0)和p(w|c1)，然后分别乘以p(c0)、p(c1)，比较其大小，即可得出新样本的类别。

朴素贝叶斯分类算法的思想如上文所述，但还存在着一些特殊情况需要处理，比如我们上面说计算新文档的p(w|c0)和p(w|c1)时，要分别用到新文档中包含的单词分别在垃圾邮件样本和正常邮件样本中所出现的概率，但要是新文档中有个单词在垃圾邮件（或正常邮件）中从来都没出现过怎么办，那概率就是0，再乘以其他单词的在垃圾邮件（或正常邮件）中的出现概率，最终结果一定是0，也就是这条文档已经被宣判不可能是垃圾邮件（或正常邮件）了，这样太过武断，所以我们做一下修改，在训练时，让每个单词的初始出现次数都设置为1，总出现次数初始设置为2，以避免上面提到的问题。

那要是有些单词在新文档里面出现次数为0怎么办？那就不乘进去。

还有个小问题就是因为乘的数都小于1，乘的次数又那么多，所以会出现下溢出，最后的结果四舍五入都变成0了，所以我们采用自然对数函数来解决这个问题，乘变成了加，乘方变成了直接相乘，如果出现次数为0，那一项就为0，不加进去，也就相当于不乘进去了，这里不再详细讲。

还有一点，如果某个特征取值是连续的怎么办，就不适宜按照某个特定值计算概率了，上例中的特征都是单词的出现次数，都是离散的，但是如果我想再增加考虑比如邮件的发送时间，时间是连续的，如果不是同一秒发送的邮件就被认为不同，那对于分类几乎没有帮助（可以理解为上例中我们的单词表里又增加了许多单词，但是这些单词不论在垃圾邮件还是正常邮件里出现的概率都极低，对于分类没有帮助），解决方法是我们按时间段划分，比如分为上午、下午、傍晚、深夜，即相当于在单词表中添加了四个单词，不同的文档都会包含这四个单词中的其中一个，如果垃圾邮件的发送时间绝大多数都在深夜，那在使用垃圾邮件训练样本训练时，深夜这个单词的出现概率就会非常高，如果新文档也是在深夜发送，就会显著提高这条新文档被认为是垃圾邮件的概率。

另外还有一点就是最开始概要的时候所提到的生成方法和判别方法，生成方法和判别方法是对监督学习算法的分类，前面讲到的kNN和决策树是判别方法，而这部分讲的朴素贝叶斯分类算法是生成方法，由判别方法学到的模型叫做判别模型，由生成方法学到的模型叫做生成模型。

判别方法由数据直接学习决策函数Y=f(X)或者条件概率分布P(Y|X)作为预测的模型，即判别模型。基本思想是有限样本条件下建立判别函数，不考虑样本的产生模型，直接研究预测模型。典型的判别模型包括k近邻，感知机，决策树，支持向量机等。

生成方法由数据学习联合概率密度分布P(X,Y)，然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型：P(Y|X)= P(X,Y)/ P(X)。基本思想是首先建立样本的联合概率概率密度模型P(X,Y)，然后再得到后验概率P(Y|X)，再利用它进行分类。

判别方法更多的关注各个类别之间的区别，而生成方法更多关注各个类别内部的相似度。判别方法画一条线，明确这种差别，线左边是类别A，线右边是类别B；生成方法拿样本去比较两个类别的已有数据，看看这个样本生成自哪个类别的可能性更大。

由生成模型可以得到判别模型，但由判别模型得不到生成模型。

Logistic回归算法

一句话概要，我们被给予一堆X维的数据，我们希望通过一条直线将这堆数据正确的分为两类（不是所有的数据都能通过线性模型被正确分类）。我们建立了一个线性函数模型t=w*x，w与x均为X维的向量。先将w置为初始向量，输入训练数据x后，将得到的t带入Sigmoid函数，将0.5作为阈值，大于0.5的为一类，小于0.5的为另一类。训练过程为，先利用最大似然估计得到目标函数，再利用梯度上升算法优化目标函数，使得训练样本生成概率最大化。

虽然名字叫做Logistic回归算法，不过它和之前三个算法一样都是分类算法，它将给定数据划分到两个类别之一，并属于判定方法，监督学习算法。

Logistic回归算法的原理并不困难，但有几个点需要介绍，比如Sigmoid函数、梯度上升算法、随机梯度上升算法等，这些概念都广泛应用于深度学习之中。

什么是Sigmoid函数？

Sigmoid函数表达式

Sigmoid函数的图像是什么样的？

Sigmoid函数图像

我们可以看到Sigmoid函数是一个阶跃函数，不管输入什么样的值，输出的值都在0到1之间，在Logsitic回归算法之中，我们取0.5为阈值，大于0.5的为一类，小于0.5的为另一类（即属于某一类的概率大于0.5则归于这一类，小于0.5则归于另一类）。

我们通过Sigmoid函数得到数据类别，通过缩减其与标注结果的差距，来优化回归系数w的值（实际上是通过优化w的值来让模型输出与训练样本标注结果相同的概率尽可能大）。这个过程我们靠的是梯度上升算法，该算法与深度学习中使用广泛的梯度下降算法原理相同。

在介绍梯度上升算法之前，我们要先确定我们的目标函数是什么，用什么函数来表示Sigmoid函数输出与标注结果相同的概率，才能去优化它，让它尽可能大。

下面这段求目标函数的推导过程中，暂时用z代替t、θ代替w，原式t=w*x暂时写为z=θ*x，z=θ*x与下面的z=θTx意义相同，都是指θ与x的内积。这段内容是Logistic回归算法的推导核心。

Logistic本质上是一个基于条件概率的判别模型(DiscriminativeModel)。利用了Sigmoid函数值域在[0,1]这个特性。

我们将Sigmoid函数的表达式重写如下：

根据Sigmoid函数的特性，我们定义这两个式子：

上式即为在已知样本x和参数θ的情况下，样本x属于正类(y=1)和负类(y=0)的条件概率。

Sigmoid的函数的输出就是样本x属于正类(y=1)的概率，也就是前面提到的，如果该值大于0.5则认定样本x属于正类(y=1)，用1-该概率则是属于负类(y=0)的概率。

然后我们将这两个式子合成一个：

将y=0和y=1分别代入，结果就是上面的两个式子。既然概率出来了，那么最大似然估计也该出场了。假定样本与样本之间相互独立，那么整个样本集生成的概率即为所有样本生成概率的乘积：

其中，m为样本的总数，y(i)表示第i个样本的类别，x(i)表示第i个样本，需要注意的是θ是多维向量，x(i)也是多维向量。

为了简化问题，我们对整个表达式求对数（将指数问题对数化是处理数学问题常见的方法）：

这也就得出了我们的目标函数，我们希望优化θ的值，来让目标函数的值越大越好，也就是我们的模型能够生成训练样本的概率越大越好。

这里插入一个小问题，Logistic回归是判别方法，不是生成方法，但上面式子算样本生成概率的方法好像与前面朴素贝叶斯算法这种生成方法非常相似。这里我的理解是（可能有误），生成方法还是判别方法与目标函数，或者讲损失函数无关，Logistics最后判断类别的时候用的是Sigmoid函数的输出，然后定了个阈值，并没有先计算联合分布概率，所以Logistic回归是判别方法。

然后继续，我们怎样调整θ让目标函数的值增大呢，这里就要用到梯度上升算法了（之后θ替换回w）。

梯度上升（下降）算法要用到梯度的概念，梯度方向就是该函数函数值变化最快的方向，而梯度的概念源自偏导数，偏导数可以理解为该X维数据对总表达式的函数值在每个维度上的导数，即总X维函数曲面被每个维度面相切所得到的曲线的导数，而导数代表着变化的快慢，若其为正则意味着总函数值随着该维度下自变量的增大而增大，若为负则相反，导数绝对值越大，则意味着其变化速度越快、变化曲线越陡峭。如果我们想让总体函数的函数值增大，那我们在每个导数为正的维度增加自变量的值，在每个导数为负的维度减小自变量的值，也即选择了梯度上升的方向，总函数值增大最快的方向，梯度下降原理相同。

梯度上升算法参数向量的迭代式如下：

梯度上升算法迭代式

式中的w即为原线性函数模型中的参数向量，α在这里叫做步长，α后面的表达式就是包含各个维度下偏导数的向量，其维数自然与w的维数相同。依照上一段的原理，详细一些讲，对于w中的每个维度，因为式子中间是加号，α为正值，若其对应的偏导数为正，与α相乘后仍为正值，与w中该维度原有自变量值相加后，自变量是增大了，而又因为其在该维度此自变量值下的偏导数为正，总函数值当下随着这个维度自变量值的增大而增大，所以总函数值是会增大的，每个维度同理，所有维度的自变量都在朝着让总函数函数值增大的方向去改变自己，而且每次迭代后都会重新计算各个维度的偏导数值，保证各个维度自变量每次变化的方向均正确，而α作为乘在导数前面的系数，决定了每个维度按当前使函数值最大的方向移动的距离大小，即步长，如果步长过大，可能走过去了发现走过了，该维度该自变量值下偏导数为负了，需要减小自变量值，如果步长过小，则整个函数函数值改变的速度太慢，效率太低。

梯度下降算法原理完全相同，表达式上的区别在于中间的加号改为减号，即所有维度的自变量都朝着让总函数值减小的方向去改变自己，深度学习中应用梯度下降算法时，字母α通常用字母η代替，称其为学习速率。

接下来要介绍的是随机梯度上升算法，与前面讲的梯度上升算法原理基本相同，但区别在于梯度上升算法每次参数向量迭代要遍历所有的训练样本，运算量相当大，例如每个训练样本有2个特征，加上方便计算的特征w0，一共3个特征，若我们有100个训练样本，那每一次参数向量迭代就要计算300次，如果训练样本的数量不是100而是100万，总特征数是10个，那每迭代一次就要计算1000万次，而且我们还不知道要迭代多少次才能得到稳定的向量值。所以那我们想，如果我们不每次都拿所有的样本训练，每次按顺序从所有训练样本中抽出一个训练，抽完一轮再从头开始，那计算量是不是就大幅减小了？这就叫做随机梯度上升算法。

实验证明，使用随机梯度上升算法，参数向量达到较为稳定状态所需要的总迭代次数要少于原始的梯度上升算法。

随机梯度上升算法

我们可以看到，在训练参数向量时，当大的波动停止后，还有一些小的周期性波动，这是因为数据集中总是存在一些不能被线性模型分类的样本点，在每次迭代时会引发系数的剧烈波动，我们期望算法能够避免来回波动，从而收敛到某个值。

想要降低剧烈的周期性波动，首先是要使α随着迭代次数的增多而减小但永远不会减小到零，这会缓解数据的波动幅度，而又保证迭代多次后数据仍然具有一定的影响。其次是上面我们是按顺序抽取样本的，这里我们更换为随机抽取，以消除数据变化的周期性。

改进后的梯度上升算法

经过若干次随机梯度上升算法的优化迭代后，我们的参数向量w终于稳定下来，将w代入t=w*x所得到t，再将t代入Sigmoid函数，所分得的类别，与标注结果的误差稳定在一个较小的值上。

采用改进随机梯度上升算法的分类结果

Logistic回归这部分还有些其他的东西，例如，当处理现实数据的时候，我们往往会遇到数据缺失问题，比如每个样本应该有50个特征，但有些特征的特征值我们是没有的（可能因为机器上的某个传感器损坏），那我们这些数据还能用吗，难道因为缺少几个特征值就丢到整个数据，这是不合理的。我们这里通常的做法有下面几种：

使用可用特征值的均值来填补缺失值
使用特殊值来填补缺失值，比如-1
忽略有缺失值的样本
使用相似样本的均值填补缺失值
使用另外的机器学习算法预测缺失值

在Logistic回归之中，我们选择用实数0来替换所有缺失值，因为在Logistic回归中，若该特征值为零，则该特征值不会影响到系数w的迭代优化，如果某样本中的某特征值为0，那么该特征的系数将不做更新。

上面讲的是特征值缺失，如果缺失的不是特征值，而是类别标签，那么我们的简单做法是将该条数据丢弃，因为类别标签与特征值不同，很难采用某个合适的值来替换。

关于Logisitic回归还有一些拓展内容：二元的最大熵模型就是Logistic回归模型，多元的Logistic回归模型就是最大熵模型。另外，在计算概率时，Logistic回归也用到了朴素贝叶斯的假设，用概率图模型的语言来说，Maximum Entropy Model（或者说Logistic Regression）和Naive Bayes形成一个discriminative- generative pair，区别仅仅在于一个是生成模型一个判别模型，其他都一样。

支持向量机SVM

一句话概要，SVM希望通过N-1维的分隔超平面线性分开N维的数据，距离分隔超平面最近的点被叫做支持向量，我们利用SMO（SVM实现方法之一）最大化支持向量到分隔面的距离，这样当新样本点进来时，其被分类正确的概率也就更大。我们计算样本点到分隔超平面的函数间隔，函数间隔为正，分类正确，为负则分类错误。函数间隔的绝对值除以||w||就是几何间隔，几何间隔始终为正，可以理解为样本点到分隔超平面的几何距离。若数据不是线性可分的，那我们引入核函数的概念，从某个特征空间到另一个特征空间的映射是通过核函数来实现的，我们利用核函数将数据从低维空间映射到高维空间，低维空间的非线性问题在高维空间往往会成为线性问题，再利用N-1维分割超平面对数据分类。

什么叫分隔超平面？如果数据的N维的，分隔超平面就是N-1维的，比如给出的数据点分布在二维平面之中，那分割超平面就是一条直线，如果数据点分布在三维空间之中，那分割超平面就是个平面，更高维同理。

我们的目的是最大化离分隔超平面最近的点（支持向量）与分隔超平面的距离，因为我们的训练数据有限，所以希望能给出足够大的犯错空间，当新样本进来时也能将其正确分类，让我们的分类器足够健壮。

为了理解函数间隔和几何间隔，我们定义一个式子：

yf(x)就是我们说的函数间隔，这里y是提前提供的对样本的标注结果，不同于Logistic回归中用0和1作为分类标签，SVM中取-1和1，这样使函数间隔不至于为0，使我们可以用函数间隔的符号作为判断分类是否正确的依据，那为什么函数间隔的符号可以判断分类是否正确？f(x)有这样一个特质，分隔超平面两侧的样本点代入f(x)后，一侧的计算全为正值，一侧全为负值，如果计算出正值的那一侧的标注结果y的值为1，那函数间隔为正，分类正确，计算出负值的那一侧标注结果为-1，函数间隔也为正，分类正确；如果计算出正值的那一侧的点标注结果为-1，则函数间隔为负，分类错误，计算出负值的那一侧标注结果为1，则函数间隔为负，分类错误。所以，函数间隔为正，分类正确，函数间隔为负，分类错误。

|yf(x)|/||w||就是几何间隔，也就是样本点到分隔超平面的真实距离，距离越大，则几何间隔越大，||w||是向量w的2-范数，即向量w元素绝对值的平方和再开方。

我们要通过最大化支持向量与分隔超平面的距离来求得分隔超平面，又因为支持向量是距离分隔超平面最近的样本点，这就可以写作：

最大化支持向量与分隔超平面的距离

上式直接求解起来相当困难，我们利用拉格朗日乘子法以及引入松弛变量C来换一种更简单的方式表述我们要解决的问题，这里推导较为难理解，简要的讲，通过SVM的原始问题，构造拉格朗日函数，并通过对偶换算得出对偶问题，而对偶问题的KKT条件又与对偶问题等价。换句话说，就是只要找到对应的α满足了下列KKT条件，那么原始问题和对偶问题就都解决了，最终得到约束条件如下：

达到最终优化目标约束条件

通俗的来讲，常数C取得越大，就是对错分样本的惩罚越大，极端情况下，就是训练出来的分类器使得每个训练样本都正确分类。那么想象一下，在有噪声样本的情况下，这么做会导致过拟合。常数C取得越小，就会有越多的样本被训练出来的分类器错分，一些正常的样本也被当成噪声处理了。

α是我们需要不断优化选取的，优化目标是训练时让尽可能多的训练样本点被正确分类并且让支持向量与分隔超平面的间隔最大化，对于SVM我们要求解α，如果α的所有分量满足SVM对偶问题的KKT条件，那么这个问题的解就求出来了，我们SVM模型学习也就完成了。如果没有满足KKT，那么我们就在α中找两个分量αi和αj，其中αi是违反KKT条件最严重的分量，固定其它变量，增大其中一个同时减少另一个，针对这两个变量构建一个二次规划问题，使得αi和αj满足KKT条件，直到α的所有分量都满足KKT条件。而且这个计算过程是收敛的，因为每次计算出来的新的两个分量，使得对偶问题中要优化的目标函数值更小。至于为什么是收敛的，是因为，每次求解的那两个分量，是要优化问题在这两个分量上的极小值，所以每一次优化，都会使目标函数比上一次的优化结果的值变小。这里用到的方法就叫做SMO（序列最小优化），SMO的具体实现细节这里不详述。

我们上面讲的SVM只能处理线性可分的数据，但实际上生活中存在着大量线性不可分的数据，根据『低维空间的非线性问题在高维空间往往会成为线性问题』，我们利用核函数将低维度下的非线性可分的数据升维成高维度下线性可分的数据，再采用我们之前讲的方法去处理。

『低维空间的非线性问题在高维空间往往会成为线性问题』这句话可能很抽象，这里我举个例子：

我们看到图中有个圈，我们姑且认为圈里面都是蓝点，圈外面都是红点，那我们怎么用一条直线（图是2维平面，则分隔超平面为1维直线）把红点和蓝点分开呢？

答案是这样：

我们啪的一下一拍桌子，这些红点蓝点全部都飞了起来，然后我们找准时机，一刀划出一个平面把两种点分开，2维线性不可分的数据成为了3维线性可分的数据，3维条件下分隔超平面为2维的平面。

接下来我们讲核函数，核函数被用来实现从某个特征空间到另一个特征空间的映射，我们可以把核函数理解成类似于欧氏距离公式一样的距离计算的方法，只要是满足了Mercer条件的函数，都可以作为核函数，又因为SVM中所有的运算都可以写成内积的形式，我们可以直接把内积运算换成核函数，而不必做进一步的简化处理，核函数接受低维空间的输入值，却能算出高维空间的内积值。径向基核函数是SVM中常用的一个核函数，它采用向量作为自变量，能够基于向量距离运算输出一个标量。径向基核函数还有高斯版本，被称为高斯核函数，感兴趣的读者可以自己了解一下具体的推导和代码编写过程。

对于核函数，这里还需要提一点，其实只处理低维下线性可分问题的SVM也是用了核函数的，只是使用的核函数不具备将低维数据映射到高维的功能，被称为线性核函数（Linear Kernel）。

用SVM同样可以实现我们在讲解kNN算法时所实现的那个手写数字识别，SVM的优势在于，它不用保留所用的训练样本用于计算，而只用保留那几个支持向量就够了，极大地减小了内存的占用，而效果却不差。

此外SVM这里还有很重要的一个点需要提，就是SVM与上一节的Logistic回归的异同点。

首先是第一点，Kernel不是SVM专有的，Kernel Logistic Regression（KLR）也很常见。

从目的和方法的角度讲：
SVM只考虑支持向量，也就是和分类最相关的少数点，去训练分类器，然后希望最大化间隔与尽可能的正确分类样本点。而逻辑回归通过非线性映射Sigmoid函数，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重（Sigmoid函数的取值范围是(0,1)，对距离进行了压缩，距离非常大时，它在损失函数中的贡献不会随着距离的增大线性增加），目的也在于尽可能的正确分类样本点。

从使用场景的角度，Andrew NG讲：

如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM
如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel
如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况

从效率与效果的角度讲：
训练数据量不是太大的话，用SVM，SVM得到的结果要优于LR，如果数据量太大，用LR，LR的运行速度会比SVM快得多。

从损失函数的角度来讲（重要）：
SVM是用的是Hinge loss function，是需要最大化间隔的，而LR用的是最大似然估计，也就是log-likehood loss function（对数似然损失函数）。

Hinge loss 的标准形式

其实就是我们上面提到过的：

最大化支持向量与分隔超平面的距离

那损失函数是什么？损失函数衡量的是模型预测错误的程度，也就代表了模型预测结果与训练样本标注结果的差别，我们希望最小化损失函数的函数值，损失函数的函数值越小，就相当于我们的预测结果与真实结果越相近。通常而言，损失函数由损失项(loss term)和正则项(regularization term)组成。

常见的损失函数有0-1损失函数、绝对值损失函数、平方损失函数（最小二乘法）、hinge loss function（SVM）、log loss function（LR）、指数损失函数（AdaBoost）等，这些损失函数用到了的时候会分别讲。在逻辑回归模型中，我们最大化似然函数和最小化log损失函数实际上是等价的。

各类损失函数图像

对hinge loss，又可以细分出hinge loss（或简称L1 loss）和squared hinge loss（或简称L2 loss），这是因为其正则项的不同，正则项可分为L1正则项和L2正则项，简单来讲，添加正则项的意义在于防止过拟合（训练样本表现极好，而测试样本表现很差）。参数越多，模型越复杂，而越复杂的模型越容易过拟合。防止过拟合的方法在下一篇深度学习的topic里面会详细讲（包括L1、L2分别是什么以及除了添加正则项还有什么方法可以防止过拟合）。

AdaBoost元算法

一句话概要，AdaBoost（adaptive boosting）是元算法，通过组合多个弱分类器来构建一个强分类器。我们为训练数据中的每一个样本都赋予其一个权重，这些权重构成了向量D，一开始，这些权重都初始化成相等值，然后每次添加一个弱分类器对样本进行分类，从第二次分类开始，将上一次分错的样本的权重提高，分对的样本权重降低，持续迭代。此外，对于每个弱分类器而言，每个分类器也有自己的权重，取决于它分类的加权错误率，加权错误率越低，则这个分类器的权重值α越高，最后综合多个弱分类器的分类结果和其对应的权重α得到预测结果，AdaBoost是最好的监督学习分类方法之一。

前面已经介绍了五种不同的分类算法，它们各有优缺点，我们可以将其组合起来，元算法（meta-algorithm）或者叫集成方法（ensemble method）可以集成不同算法，也可以是同一算法在不同设置下的集成，还可以是被数据集不同部分训练过的相同或不同的分类器的集成。

boosting和bagging都是集成学习（ensemble learning）领域的基本算法，boosting和bagging使用的多个分类器的类型是一致的。

bagging也叫自举汇聚法（bootstrap aggregating），比如原数据集中有N个样本，我们每次从原数据集中有放回的抽取，抽取N次，就得到了一个新的有N个样本的数据集，然后我们抽取S个N次，就得到了S个有N个样本的新数据集，然后拿这S个数据集去训练S个分类器，之后应用这S个分类器进行分类，选择分类器投票最多的类别作为最后的分类结果。

boosting与bagging的区别在于：

bagging通过有放回的抽取得到了S个数据集，而boosting用的始终是原数据集，但是样本的权重会发生改变。
boosting对分类器的训练是串行的，每个新分类器的训练都会受到上一个分类器分类结果的影响。
bagging里面各个分类器的权重是相等的，但是boosting不是，每个分类器的权重代表的是其对应分类器在上一轮分类中的成功度。

AdaBoost是boosting方法中最流行的版本。

起始状态，所有样本的权重都是相同的，我们采用第一个弱分类器（我们对弱分类器的要求是只要二分类正确率高于50%就可以了，比瞎猜准一点就可以）对其进行分类，然后计算其分类加权错误率：

加权错误率

之后为第一个弱分类器赋予权重：

分类器权重计算

计算出α之后，要对样本权重D进行更新，如果该样本被正确分类，那我们降低其权重：

如果该样本被错误分类，那么我们提高其权重：

计算出新的权重之后，AdaBoost又开始进入下一轮迭代，不断重复迭代，直到训练的错误率为零或迭代次数达到用户的设置，当有新样本时，我们将所有分类器的分类结果与权重相乘后全部加和，如果结果大于0则是类别1，小于0则是类别-1（AdaBoost的类别标签为1和-1）。

如果要理解AdaBoost是怎么工作的，那看到这就够了，下面会讲一些深一点的内容，比如上面给定了分类器的权重计算公式，那这个权重公式是怎么推导出来的？还有AdaBoost的目标函数是什么？

这里我引用我自己总结的一个思考方法，对于一个机器学习算法：

它的优化目标是什么
它的目标函数/损失函数是什么
它用什么方法去优化目标函数的函数值
它是怎么对数据进行分类的

前面只是讲了『它用什么方法去优化目标函数的函数值』以及『它是怎么对数据进行分类的』，我们还不知道它的优化目标和AdaBoost的目标函数，我查阅了Wikipedia找到了AdaBoost的推导过程：

AdaBoost的优化目标，是使整个模型的加权错误率最小。

我们首先看一下这个式子：

AdaBoost递推公式

虽然这里的字母并没有全在前面出现过，但根据意思很容易理解，C是AdaBoost总分类器，m是迭代次数，x是样本、α是分类器权重、km是第m次迭代时所增加的那个分类器。

依照AdaBoost的优化目标，我们定义E为AdaBoost的指数损失函数：

AdaBoost损失函数

将我们提前定好的样本权重的更新规则代入（也即前面D的更新公式）（这里用w表示权重）：

第一次迭代所有样本权重均为1

第二次迭代之后，正例权重降低，反例权重升高

化简得到：

化简后的损失函数

然后我们就得到了AdaBoost的损失函数，然后我们希望对其优化，最小化其函数值，这里我们让E对α求偏导：

让其为零，则得到：

此时我们发现，如果我们代入之前对权重错误率ε的定义：

加权错误率

就得到了：

分类器权重计算

之后就按照前面讲过的流程，迭代更新样本权重以及确定新分类器的权重，优化模型，指导到达指定的迭代次数或错误率下降到零。然后根据模型输出是否大于零对样本进行分类。

AdaBoost是这篇文章里面讲的最后一个分类算法，在开始讲监督学习中的回归算法之前，还有一个问题需要讨论，就是非均衡分类问题。在前面的分类算法中，我们都假设所有类别的分类代价是一样的，但实际上并不是这样，就拿朴素贝叶斯算法的垃圾邮件过滤做例子，将垃圾邮件错分为正常邮件和将正常邮件错分为垃圾邮件的代价是不一样的。

这里我们介绍度量分类性能的相关知识：

首先是真阳（TP）、真阴（TN）、假阳（FP）、假阴（FN）。如果正例被判定为正例、反例被判定为反例则为真阳（TP）、真阴（TN）；如果正例被判定为反例则为假阴（FN）；如果反例被判定为正例则为假阳（FP）。

然后介绍正确率的概念，它等于TP/(TP+FP)，就是在所有被判定正例的样本里面，真正的正例有多少；召回率等于TP/(TP+FN)，就是在所有的正例里面，有多少被判定为正例了。

更形象一点讲：

上帝的模型

中间那条线是最理想的模型，100%正确的划分出了所有的正例和反例，左侧正例，右侧反例，但是这条线只有上帝知道，我们建出来的模型只能是这样的：

人类的模型

那条红线是我们建出来的模型，我们认为红线左侧是正例，右侧是反例，那怎么评价我们建模的好坏呢，用A/A+C就是正确率，用A/A+B就是召回率。在上帝模型里B和C都是不存在的，正确率与召回率都是100%。

同一个算法模型可以理解为一条斜率相同的线，我们可以上下移动它，往上移，召回率提高，正确率降低；往下移正确率提高，召回率降低。同一模型下一般不能同时提高正确率和召回率，但是可以根据实际情况调整到底是要更高的正确率还是更高的召回率。

另一个度量分类中的非均衡性的工具是ROC曲线：

ROC曲线示例

图中提到的真阳率与前面讲到的召回率相同，真阳/真阳+假阴，A/A+B。假阳率是FP/(FP+TN)，就是假阳/假阳+真阴，就是前面的图上C/C+空白部分。

再回到上面的图，看实线，同一个模型，如果假阳率为0，也就是前面图中C不存在，那么真阳率也很低，也就相当于前面图中的红线下移直到C不存在，B变得很大；如果真阳率为1，则相当于前面图中的红线上移直到B不存在，C变得很大，那么假阳率就很高，同时，正确率也就很低。

用来衡量不同模型好坏的一个指标是AUC，也就是ROC曲线右下部分的面积，一个完美分类器的AUC是1，真阳率1，没有B，假阳率0，没有C，100%正确分类；而瞎猜，也就是虚线，AUC为0.5。

还有一个是我们可以在机器学习中引入代价的概念，比如分出真阳和真阴的代价是0，甚至可以是负数，分出假阳和假阴的代价为正数，在实际应用中分错的代价越大，那它对应的正数值也就越大，将代价引入目标函数中一并优化，最后的目标是总代价最小。

另一点是欠抽样和过抽样，如果正例和反例的数量差距过于悬殊，我们倾向于对数量过多的类别进行欠抽样，只取其中一部分；而对数量过少的类别进行过抽样，比如复制样例或加入与样例相似的点。