机器学习基石-Linear Models for Classification

Linear Models for Classification

回顾

lecture10中我们介绍了一个重要的演算法logistic regression，我们通过极大似然的方式得到其损失函数，然后通过梯度下降算法研究得到目的的hypothesis，本节课我们对我们学习的linear model做一个总结和推广。

Linear Models for Binary Classification

首先，我们对我们学习的三个线性模型做一个总结，我们发现三者都用到了一个scoring function，然后我们知道线性分类是一个比较难的问题，于是我们思考是否可以使用linear regression或者logistic regression中的方法来帮助简化我们的线性分类问题。

现在我们这样来思考，我们将输出空间限制为+1和-1，然后整理三个模型的error function，我们可以得到下面的结果：

这样，我们将三类模型的损失函数用类似的形式统一起来了，其中y对应分类的正确度，s对应score，二者均是有一定物理意义的。

然后我们可以将三类损失函数都画在同一个图像上，我们可以得到上面的结果。

接下来，我们做相关公式推导，容易知道logistic regression/linear regression 的Ein是binary classification的Ein的一个上界，所以如果我们能把潜在的Ein做得比较小，那么相应的方法可以用来做linear classification。

将上面提到的方法用于binary classification的方式被我们称为regression for classification，我们将输出空间固定为+1和-1然后跑相关的regression过程，最后返回相应的g(x），几种方法会有计算上的优势，但是不可避免的是错误上界的放大。

实物上，我们如果要做binary classification，我们总结了以下两点建议：1、在我们使用PLA/pocket/logistic regression时，我们使用linear regression设置初始w,来加速模型进程。2、实物上我们更多使用logistic regression而非pocket。

Stochastic Gradient Descent

我们比较PLA和logistic regression的计算过程，我们会发现，后者的计算量是非常大的，后者需要将资料集D中的所有资料都纳入计算过程。这个大的计算量不是我们想看到的，我们思考能否实现类似PLA的使用一笔资料进行更新的过程。

我们回到LR中w的更新公式，我们的目的是每次选取一个点进行更新，我们将求和平均看成是一个随机过程的平均，随机抽取一个点来达到我们使用全量资料的目的，理论上我们随机抽取一个点与我们将所有的资料点求和再取平均是比较接近的。

这样我们的到的梯度被称为stochastic gradient，这个这个随机的梯度可以看成是真实梯度的一个期望。

实际上，我们可以将随机梯度视为真实梯度加上一些杂讯，于是相应得我们可以将真实梯度替换成随机梯度可以得到随机梯度下降算法，这个演算法更简单计算量更小，但是同时这个演算法不那么稳定。

我们将PLA和SGD LR的公式放在一起，通过比较我们可以发现：1、可以将SGD的logistic regression看成是soft PLA；2、在分数很大的情形下，PLA和SGD基本上是一致的。

最后，需要强调的是：1、SGD没有停止的条件，经验上一般我们跑足够的次数就停止；2、经验上η取0.1能取得不错的效果。

Multiclass via Logistic Regression

接下来，我们看看怎么做多元分类的问题，比如现在有四个选项，我们需要做区分。我们这样来思考，我们分别对四个类别做四个二元分类器，在四个分类器独立的区域分类没有问题，但是重叠的区域分类没法确定，于是这个时候我们考虑用logistic regression做分类。

我们使用logistic regression做四个soft 二元分类器(这个分类器不再是预测一定是哪个分类，而是给出某个点是某个分类的概率)，然后我们选取几个分类器中概率最大的那个类别作为分类结果。

我们将这样的建立多个分类器的方法叫做OVA，这个方法很有效率并可以配合类似LR演算法使用，但是当类别个数K较大时会有不平衡数据集的问题。

Multiclass via Binary Classification

上部分内容我们提到OVA中如果某个类别的数据量过小会导致unbalance的问题，一对多可能存在问题，于是我们采用一对一的方式来解决这个问题。

于是我们可以采用OVO的方式对四个类别建立6个分类器，最后我们根据6个分类器的分类结果进行投票，得票最高的选项即为分类结果，我们总结这个方式及其优缺点如下：

小结

本节课，我们首先总结了三个linear models的特点，并指出三个model都是能用来做binary classification的，接着拓展了SGD的方法来做logistic regression，最后我们介绍了两种做多类别分类的方法。