线性模型

基本形式

线性模型是通过一个属性的线性组合进行预测的函数： \[ f(x) = w_1x_1 + w_2x_2 + ... + w_dx_d + b = w^Tx + b \]

许多非线性模型可以通过在线性模型的基础上引入层级结构或者高维映射形成；
另外，向量w直观地表达了各个属性在预测中的重要性；

线性回归

给定数据集$D={(x_1, y_1), (x_2, y_2),...,(x_m, y_m)}$，其中向量$x_i=(x_{i1};x_{i2};...;x_{id})$。而线性回归就是希望找到一个线性模型能够准确地预测出值。也就是试图学习得： \[ f(x) == w^Tx + b，使得f(x_i)\approx{y_i} \] 那么这里的关键要确定w和b，也就是保证f(x)和y之间最小的时候获得w和b，从几何的角度来看，就是找到一条直线使得所有样本到直线上的欧氏距离之和最小。

假设有 \[ X= \begin{bmatrix} x_{11} & x_{12} & x_{13} & \dots & x_{1d} \\ x_{21} & x_{22} & x_{23} & \dots & x_{2d} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{m1} & x_{m2} & x_{m3} & \dots & x_{md} \end{bmatrix} \]

\[ y = (y_1; y_2;...;y_m) \]

令$E_w = (y-Xw)^T (y-Xw)$，对$w$求导，得 \[ \frac{\alpha{E_w}}{\alpha{w}} = 2X^T(Xw-y) \] 当$X^TX$为正定矩阵或者满秩矩阵，令导数为0可得： \[ 2X^T(Xw-y) = 0 \\ X^TXw = X^Ty \\ w = (X^TX)^{-1}X^Ty \] 假如我们认为对应的输入会导致在指数尺度上发生变化，可以转换成对数线性回归： \[ ln y = w^T+b \]

对数几率回归

上面提及的是利用线性模型做回归学习，如果面对分类任务应该怎么做呢？

考虑二分类问题，则$y\in({0, 1})$，我们需要将线性回归模型产生的值转换为0/1值。则

当z<0，y = 0;

当z=0，y = 0.5;

当z>0，y = 1

因此我们可以sigmoid函数代替，$y = \frac{1}{1+e^{-z}}$，图像如下：

带入上式，可以得到： \[ y = \frac{1}{1+e^{-{(w^Tx+b)}}} \\ ln \frac{y}{1-y} = w^Tx+b \] 若把y视为样本x作为正例的可能性，1-y为其反例可能性，那么$ln $就是对数几率。这个方法不仅仅可以预测出类别，更可以得到近似概率的预测，提高决策效果。

当要确定w和b的时候，可以使用极大似然法来估计，目的是使得每个样本属于真实样本的可能性越大越好： \[ \iota(w, b) = \sum_{i=1}^{m}ln p(y_i|x_i;w,n) \] 其中似然项可以写成： \[ p(y_i|x_i;w, b) = y_ip(y=1|x,w;b) + (1-y_i)p(y=0|x,w;b) \] 带入上式之后，使用梯度下降可以求得最优解。

关于极大似然法，可以参考

线性判别分析

linear discriminant analysis(LDA)是一种经典的线性学习方法，可用作分类，也可以为后续的分类做降维操作。

LDA的思想：设法将样本投影到这样的一条直线上：同类的样例的投影点尽可能相近，异类样例的投影点尽可能远离，这样就可以根据投影点的位置来确定新样本的类别。

https://i.stack.imgur.com/9k7iT.png

令$X_i, \mu_i, \Sigma_{i}$分别表示第i类实例的集合、均值向量和协方差矩阵。在将样本值投影到直线之后，两个样本的协方差分别为$w_T\Sigma_0w$和$w_T\Sigma_1w$，而样本中心的投影则是$w_T\mu_0$和$w_T\mu_1$。因此，为了使得同类样例的投影点尽可能接近，异类样例的投影中心尽可能大，则需要最大化目标函数： \[ J = \frac{\Arrowvert w^T\mu_0-w^T\mu_1\Arrowvert^2_2}{w_T\Sigma_0w+w_T\Sigma_1w} \\ = \frac{w_T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w_T(\Sigma_0+\Sigma_1)w} \] 分子$\Arrowvert w^T\mu_0-w^T\mu_1\Arrowvert^2_2$尽可能大，保证类中心之间距离尽可能大。分母$w_T\Sigma_0w+w_T\Sigma_1w$尽可能小，使得同样例的投影点的协方差尽可能小。

多分类学习

多分类学习的任务，可以基于二分类学习进行推广，即将多分类任务拆分为若干个二分类任务进行求解。有三种拆分策略：

一对一：OvO；
一对其余：OvR；
多对多：MvM；

一对一

假设有N个类别，我们分别进行两两配对，那么就会产生N(N-1)/2个二分类任务，则有N(N-1)/2个分类器。那么在测试的时候，对于测试样本就会产生N(N-1)/2个结果。最终结果可以通过投票产生，被预测得最多的类别作为最终分类结果。

一对其余

OvR的主要思路是每次将一个类别作为正例，其余所有类的样例作为反例，产生N个分类器。在测试的时候，若仅有一个分类器预测为正类，则对应的类别标记为最终结果；若有多个分类器预测为正类，则需要考虑分类器的预测置信度，选择置信度最大的作为分类结果。

多对多

多对多的思路是每次选取若干个类作为正类，若干个其它类作为反类，显然OvO和OvR都是MvM的特例，这里介绍一种最常见的MvM技术：纠错输出码(ECOC)。

ECOC主要分为两个过程：

编码：对N个类别做M次划分，每次将一部分类别作为正类，一部分作为反类。这样就形成了M个训练集和M个分类器。
解码：M个分类器分别对测试样本进行预测，这些预测标记组成一个新的编码，将这个编码与各个类别的编码进行比较，返回其中距离最短的类别作为最终结构。

类别的划分通过编码矩阵来指定，常见形式有二元码和三元码：

三元码的0表示$f_i$分类器不使用该类样本。

纠错输出码对分类器的错误有一定的容忍和纠正能力，假设某个分类器出现了错误，基于这个编码仍能产生正确的分类的结果。另外ECOC编码越长，或者任意两个类别之间的编码距离越远，它的纠错能力就越强。

类别不平衡问题

前面几章介绍的分类学习方法都有一个基本的前提，那就是不同类别的训练样本树木相当。但假设反例有998个，正例有2个，那么学习方法只要每次都返回一个永远将样本预测设为反例的学习器，那么精确度就有99.8%。但显然，这种学习没有意义。

线性分类时，当我们用$y = w^Tx+b$对新样本x进行分类时，事实上是用y跟一个阈值进行比较。实际上y代表了正例的可能性，那么几率$\frac{y}{1-y}$代表了正例与反例的可能性比值，则： \[ 若\frac{y}{1-y} > 1，预测为正例 \] 然而当训练集正反例数目不等时，令$m^+$为正例数目，$m^-$为反例数目，那么观测几率就是$\frac{m^+}{m^-}$，这是基于真实样本是无偏差采样的。因此，我们可以对类别平衡的样本进行一次“再缩放”。 \[ \frac{y}{1-y} = \frac{y}{1-y} \times \frac{m^+}{m^-} \] 现有技术对于这种类别平衡问题有三种做法：

欠采样：去掉一些反例，使得正反例数目接近；
过采样：增加一些正例，使得正反例数目接近；
阈值移动：就是刚刚的那个再缩放；