这次Lecture总结比较了已经学习的三种模型优缺点，引入SGD来优化Logistic Regression，讲解了Multiclass Classification中的OVA和OVO方法。

Linear Models for Binary Classification

之前三种线性模型都是对样本特征x的加权运算，我们引入一个线性得分函数（linear scoring function）s：。

对比一下这三种模型：

• Linear Classification：模型假设hypothesis的结果，采用0/1 error作为误差衡量，是离散的，也就是除非输入x是线性可分的，该方程的最优解法是一个NP-hard问题，复杂度非常高。
• Linear Regression：模型假设hypothesis的结果，采用squared error作为误差衡量，是一个开口向上的二次曲线，其解是closed-form的，可以通过一次矩阵运算求出。
• Logistic Regression： 模型假设hypothesis的结果，采用cross-entropy error作为误差衡量，是平滑的“s”型凸曲线，可以使用梯度下降算法求解最小值。

那么我们能否将LinReg和LogReg两种模型进行调整，使其适用于Linear Regression的用途呢？如果可以的话，就能够大大减小二分分类的复杂度了。

我们看到，LinReg和LogReg输出都是一个实数，并且都有最小解。我们可以将三个模型作如下的调整，由于，这三个式子的变换分别都是等价的。

其中，引入作为分类正确度得分（classification correctness score）， 三个error function的值都与之相关，那么我们用图形来看具体关系（左图）。

引入Scaled Cross-Entropy Error Function（SCE）有 ，这样能使SCE一直在0/1的图线之上，仅作换底操作不会影响最优化的过程，但是能让LogReg的分类能力上接近Linear Classification，也就是让低的时候，也低。（右图）

于是，我们能得到如下的三个性质：

• 
• 
• 

由VC理论可得

从而我们就能够把 LinReg和LogReg 作为Linear Classification的上界，也就是如果使用或来衡量一个模型分类分得好不好的时候，如果他们认为分得好，那么如果使用，它也会认为分得好。

以下是处理分类问题时，PLA、LinReg、LogReg三者的优缺点——

而由于LinReg训练速度快，又在较大下能得到宽松上界，所以常可以使用LinReg得到的作为其他模型的，这样可以加快其他模型的最优化速度。

同时，由于多数数据是线性不可分的，常使用LogReg而不是PLA+Pocket。

Stochastic Gradient Descent

之前介绍的PLA和LogReg两个算法，在求解最小值的时候都是通过迭代的方式。PLA每次迭代只要选取当前点，时间复杂度是；LogReg则是每次迭代将N个点都计算一遍，时间复杂度是。那么随机梯度下降算法（Stochastic Gradient Descent）就是提高LogReg中Gradient Descent的速度的。

之前的内容中已经将过了LogReg的迭代方式

 可不可以不要这个先求和再取平均数的部分呢？随即选取一个点n，它对梯度的“贡献”为，这就是随机梯度，而真实的梯度则可以认为是随机抽出一个点的梯度的期望。
因此，可以把随机梯度当作是在真实梯度上加一个均值为0的noise：

从单次迭代上来看，好像确实会对每一步找到正确的梯度方向有影响，但是从整体期望值来看，与真实的梯度方向没有差太多，同样能找到差不多好的位置。

这种方法就是随机梯度下降，Stochastic Gradient Descent (SGD)：

SGD算法有以下优缺点

• 优点：复杂度大大减小，支持大数据计算；由于按点来迭代，就支持在线学习（online learning）。
• 缺点：在noise比较大的时候，会较不稳定。

我们看到SGD logistic regression和PLA有非常相似的地方，都是对当前的与进行修正，可把SGD logistic regression称之为’soft’ PLA。另外，当且足够大的时候，PLA近似于SGD。

关于SGD算法林老师有两点经验（rule-of-thumb）：

• SGD的终止迭代条件一般是让迭代次数足够多；
• 更新速度是根据实际情况来决定的，一般就可以了。

Multiclass via Logistic Regression

之后两节讲的是多分类（Multiclass）的情况。假设平面上有四个类（正方形、菱形、三角形、星形），如何进行分类模型训练呢？

容易想到的就是，一次分出一个类，然后将四个类依次进行这个操作（如上图下侧的四幅图），最后合起来我们就能够得到一个分类的图（如上图上侧的右图）。但这么做有一个问题就在于会有交叉和空白的区域，这部分区域如何来进行分类呢？显然简单的binary classification就不能解决。

这时候就可以采用LogReg这样的‘soft’ classification，只要让各个分类器都输出是否为自己类别的概率值，然后选择概率值最高的那个分类器所对应的类别，作为最终的输出就可以。结果图类似下面。

这种多分类的处理方式，我们称之为One-Versus-All(OVA) Decomposition。

• 优点是简单高效，并且可以和Logistic Regression的方法搭配使用；
• 缺点是当数据类别K很大时，那么二分的正类和负类的数量差别就很大，数据不平衡unbalance，这样就不容易得出正确结果。
• 另外，在选取某一类概率最大时，所有类别的概率之和不一定为1，虽然实际中影响不大，但统计上有更加严谨的方法——multinomial logistic regression。有兴趣可以看一下WikiPedia的解释。

Multiclass via Binary Classification

对于上面OVA的K较大unbalanced的问题，可以将K个类别两两进行比较，一共只要进行次binary classification就可以完成训练，在进行判断的时候只要像单循环赛一样，取得分高的那一个分类。k = 4，就像在下图中只要在6个分类器中选出符合最多的那个就可以。

 这种区别于OVA的多分类方法叫做One-Versus-One(OVO)。

• 优点是更加高效，因为虽然需要进行的分类次数增加了，但是每次只需要进行两个类别的比较，也就是说单次分类的数量减少了；而且一般不会出现数据unbalanced的情况，比较稳定；可以和任何的binary classification方法搭配使用。
• 缺点是分类次数增加到，时间复杂度和空间复杂度可能都比较高。

总之，OVA和OVO是两个多类别分类方法，都是非常不错的多类别分类算法，在k不大的时候比较推荐OVO，减少分类次数。