线性模型

基本形式

给定d个属性描述的示例$x=(x_1;x_2;…;x_d)$,其中$x_i$是x在第i个属性上的取值，线性模型试图学得一个通过属性的线性组合来进行预测的函数，即
$f(x)=w_1x_1+w_2x_2+….+w_dx_d+b$

线性回归

考虑一元线性回归的情况：

$f(x_i)=wx_i+b$ $(w^{* },b^* )=argmin_{(w,b)}\sum_{i=1}^m(f(x_i)-y_i)^2$

求解w和b使$E_{(w,b)}=\sum_{i=1}^m(y_i-wx_i-b)^2$最小化的过程，称为线性回归模型
我们呢可将$E_{(w,b)}$分别对w和b求导，得到

$\frac{\partial E_{(w,b)}}{\partial w}=2(w\sum_{i=1}^mx_i^2-\sum_{i=1}^m(y_i-b)x_i)$ $\frac{\partial E_{(w,b)}}{\partial b}=2(mb-\sum_{i=1}^m(y_i-wx_i))$

令上面两式为0，即可求出w和b

更一般的情形，多元线性回归

$f(x_i)=w^Tx_i+b$

类似的，可利用最小二乘法来对w和b进行估计

$X=\begin{bmatrix} x_{11}\ \ x_{12} \ ... \ \ x_{1d} \ \ 1\\ x_{21}\ \ x_{22} \ ... \ \ x_{2d} \ \ 1\\ .................\\ x_{m1}\ \ x_{m2} \ ... \ \ x_{md} \ \ 1\\ \end{bmatrix} =\begin{bmatrix} x_1^T \ \ 1\\ x_2^T \ \ 1\\ .......\\ x_m^T \ \ 1\\ \end{bmatrix}$

再把标记也写成向量形式$y=(y_1;y_2;…;y_m)$

$\hat{w}^* =argmin_{\hat{w}}(y-X\hat{w})^T(y-X\hat{w})$

令$E_{\hat{w}}=(y-X\hat{w})^T(y-X\hat{w})$
对w求导得到

$\frac{\partial E_{\hat{w}}}{\partial \hat{w}}=2X^T(X\hat{w}-y)$

令上式为0可得$\hat{w}$最优解的闭式解。

$\hat{w}^* =(X^TX)^{-1}X^Ty$

线性模型虽简单，却有丰富的变化。例如对于样例(x,y),y∈R,当我们希望线性模型的预测值逼近真实标记y时，就得到了线性回归模型。为便于观察，我们把线性回归模型简写成

$y=w^Tx+b$

可否令模型预测值逼近y的衍生物呢?譬如说，假设我们认为示例所对应的输出标记是在指数尺度上变化，那就可将输出标记的对数作为线性模型逼近的目标，即

$ln\ \ y=w^Tx+b$

这就是”对数线性回归”

对数几率回归(逻辑回归)

之前讨论的线性回归问题都是处理连续值，倘若要处理离散值得分类问题，则可考虑用广义的线性回归模型，在上述线性回归的基础之上进行修改。

考虑一个二分类的问题，其输出标记y∈{0,1},而线性回归模型产生的预测值z=$w^Tx+b$是实值。我们需要将实值z转换为0/1的值，最理想的是”单位阶跃函数”

$y=\begin{cases} 0 \ \ \ \ \ \ \ z＜0\\ 0.5 \ \ \ \ \ z=0\\ 1 \ \ \ \ \ \ \ \ z＞0\\ \end{cases}$

但存在一个问题，阶跃函数是不连续的，也就是说是不可微的，我们希望找到一个单调可微函数。对数几率函数正是这样一个常用的函数

$y=\frac{1}{1+e^{-z}}$

将z带入

$y=\frac{1}{1+e^{-(w^Tx+b)}}$

可以经过变换得到下列形式

$ln\frac{y}{1-y}=w^Tx+b$

尽管它叫对数几率回归，实则它解决的是分类问题。

线性判别分析(LDA)

LDA的思想非常朴素：给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；

给定数据集$D= \{(x_i,y_i)\}_{i=1} ^m$,令$X_i$、$\mu_i$、$\Sigma_i$分别表示第i∈{0,1}类示例的集合、均值向量、协方差矩阵。若将数据投影到直线w上则两类样本的中心在是线上的投影分别为$w^T\mu_0$和$w^T\mu_1$;若将所有样本点投影到w直线上，则两类样本的协方差分别为$w^T\Sigma_0w$和$w^T\Sigma_1w$

欲使同类样例的投影点尽可能接近，可以让同类样例的投影点的协方差尽可能小，即$w^T\Sigma_0w+w^T\Sigma_1w$尽可能小;而欲使异类样例的投影点尽可能远离,可以让类中心之间的距离尽可能大,即$||w^T\mu_0-w^T\mu_1||_ 2^2 $尽可能大，同时考虑二者，则可得到欲最大化的目标

$J=\frac{||w^T\mu_0-w^T\mu_1||_ 2^2}{w^T\Sigma_0w+w^T\Sigma_1w}$

定义”类内散度矩阵”

$S_w=\Sigma_0+\Sigma_1$

定义”类间散度矩阵”

$S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T$

目标函数可重写为:

$J=\frac{w^TS_bw}{w^TS_ww}$

如何确定w?
不失一般性，令$w^TS_ww=1$
上式等价于

$min -w^TS_bw$ $s.t. \ \ \ \ \ \ w^TS_ww=1$

用拉格朗日乘子法，上式等价于

$S_bw=\lambda S_ww$

并且可以注意到$S_bw$的方向恒为$\mu_0-\mu_1$,不妨令

$S_bw=\lambda(\mu_0-\mu_1)$

带入可得

$w=S_w^{-1}(\mu_0-\mu_1)$

显然我们上述操作是找一个投影矩阵W,用LDA将样本投影到N-1维空间。而且这个过程中使用了类别信息。

多分类学习

多分类学习的基本思路是”拆解法”，即将多分类任务拆为若干个二分类任务求解。
最经典的拆分策略有三种:”一对一”(One vs. One)、”一对其余”(one vs. Rest)和”多对多”(many vs. many)

最常用的Many to Many的技术是：“纠错输出码”(ECOC)

类别不平衡问题

类别不平衡就是指分类任务中不同类别的训练样例数目差别很大的情况。从线性分类器的角度讨论容易理解，在我们用$y=w^Tx+b$对新样本x进行分类时，事实上是在用预测出的y值与一个阈值进行比较，例如通常在y＞0.5时判别维正例,否则为负例。y实际表示正例的可能性，几率$\frac{y}{1-y}$则反映了正例可能性与反例可能性之比值，阈值设置为0.5恰表明分类器认为真实正、反样例可能性相同，即分类器决策规则为

$若\frac{y}{1-y}＞1则预测为正例$

然而，当训练集中正、反样例的数目不同时,令$m^+$表示正例数目，$m^-$表示负例数目，则观测几率为$\frac{m^+}{m^-}$，由于我们通常假设训练集是真实样本总体的无偏采样，因此观测几率就代表了真实几率，于是，只要分类器的预测几率高于观测几率就应该判定为正例，即

$若\frac{y}{1-y}＞\frac{m^+}{m^-}则预测为正例$

由此我们可以重新设定分类器的决策规则,设

$\frac{y'}{1-y'}=\frac{y}{1-y}×\frac{m^-}{m^+}$

由此可以比较$\frac{y’}{1-y’}$与1的关系，来预测样本为正例还是负例。这种方法是类别不平衡学习的一个基本策略——“再缩放”.

再缩放的思想虽简单，但实际操作却并不平凡,主要是因为”训练集是真实样本总体的无偏采样”这个假设往往并不成立，也就是说，我们未必能有效地基于训练集观测几率来推断出真实几率

现有技术大体上有三类做法:

直接对训练集里的样例进行欠采样，去除多余的样例，使正反样例数目接近
对训练集里的样例进行过采样，想办法生成较少类的样例。常用的算法SMOTE
直接基于原始训练集进行学习，但在用训练好的分类器进行预测时，将再缩放公式嵌入到其决策过程，称为”阈值移动”