机器学习基石---Linear Models for Classification

  

三种线性模型的比较

  先对比Linear Classification、Linear Regression、Logistic Regression:

1. Linear Classification模型
  * 输出结果是评分结果s的符号
  * 误差衡量为0/1 error
  * cost function 是NP-hard问题
2. Linear Regression模型
  * 输出结果是评分结果s
  * 误差衡量为square error
  * cost function 是凸函数，令一阶导为0，可以通过矩阵运算直接求解
3. Logistic Regression模型
  * 输出结果是对评分结果s进行sigmod变换
  * 误差衡量为cross-entropy
  * cost function 是凸函数，可以使用gradient descent的方式求最佳解
Linear Regression和Logistic Regression的输出是一个实数，而不是一个Binary的值，他们能用来解分类问题吗？可以，只要定一个阈值，高于阈值的输出+1，低于阈值的输出-1就好。例如Logistic Regression常用的阈值就是0.5。那么可以取代Linear Classification吗？
  这三种模型主要的区别在于误差的衡量。具体如下：

其中ys又称为分类的正确性得分，得分越高越好。可以想象得分越高，两类数据的区分越好。所以我们希望ys小的时候，cost function较大。ys较大时，cost function较小。为了方便比较，以ys为横轴，error为纵轴，画出三个error function 的函数：

看红色的sqr函数曲线，ys较小时，error较大；ys较大时，error也较大；这一点并不符合我们的希望。但是如果我们能够找到较小的squre error，此时0/1 error通常也很小。而对于ce，需要做换底的运算。

做了换底的运算之后，scaled ce可以作为0/1 error的bound。这样一来，如果我们找到一个w使得squre error或者cross-entropy error较小时，0-1 error通常也都是很小的。这样一来，我们可以用Linear Regression和Logistic Regression代替Linear Classification。
对于Linear Regression而言，在ys很大或很小时，这个bound是很宽松的，不能保证0/1 error很小。而Logistic Regression，在ys很小时，bound也宽松。所以通常使用Linear Regresion得到的w作为PLA/Logistic Regression的w0。

Stochastic Gradient Descent

  之前总结过，这里不重复写了。

Multiclass Classification

  可以使用二分类的方法解决多分类问题。主要有OVA和OVO两种方式。

OVA

  先看OVA(One vs. ALL)，假设类别共有4种，每一次把其中一种作为一类，其余三种作为另一类，这样共有四个分类器。做预测时，对于同一个点or样本，四个分类器会输出四个结果，取概率最大的类别作为该点的预测类别。

但是当类别较多时，对于每一个二元分类器都会出现类别不平衡问题，这时，可以采用下面的策略。

OVO

  OVO(One vs. One)同样的，假设类别共有4种，任取其中两个类别的样本，做二元分类，共有C24，6个分类器。做预测时，对于同一个点or样本，六个分类器会输出六个结果，选取频数最多的那一类作为该点的类别，类似与投票算法。

OVO相比较OVA，分类的次数增加了，即分类器更多，但是每一次分类的数据减少了。并且一般不会出现数据不平衡的情况。

Summary

  这节课主要内容，对线性分类、线性回归、逻辑回归做比较，提出随机梯度下降方法求解逻辑回归参数，以及多元分类的两种策略。

                                           2018-02-06 于杭州