第三章 线性模型

假设样本的属性有$d$d个，所有的样本为$x=(x_1;x_2;\cdots ;x_d)$x=(x1​;x2​;⋯;xd​)，则线性模型是学得一个通过属性的线性组合来进行预测的函数，即
$f(x)=w_1x_1+w_2x_2+\cdots +w_dx_d+b$f(x)=w1​x1​+w2​x2​+⋯+wd​xd​+b
用向量表示为：
$\hat{y}=f(\mathbf{x})=\mathbf{w}^T\mathbf{x}+b$y^​=f(x)=wTx+b

注意一个小细节，这是一个预测函数，输入值为一个向量，代表一条数据；输出值就只有1个，所以y和b为标量。

即学习到w和b之后，模型就可以确定了，线性模型简单且易于建模，很多功能强大的非线性模型也可在线性模型中引入层级结构或高维映射而得。

3.1 多元线性回归

线性回归是对连续性属性值操作的，若不是连续的呢？涉及两种情况：

1. 若有序，如身高的“高”，“中”，“低”可以使用(1.0 , 0.5 , 0.0)表示；
2. 如不是有序的，如瓜类取值”西瓜“、”南瓜“，“黄瓜”可以使用(0,0,1)、(0,1,1)、(1,0,0)表示。

3.1.1 最小二乘法处理一元线性回归

一元线性回归指的是属性特征只有一个，若采用均方误差来表示误差，则基于均方误差最小化来进行模型求解的方法称为“最小二乘法”。
线性回归试图学得：
$f(x_i)=w^Tx_i+b$f(xi​)=wTxi​+b，使得$f(x_i)\simeq y_i$f(xi​)≃yi​。
如何确定w和b呢？关键在于如何衡量f(x)和y之间的差别，此处使用均方误差，即：

$\begin{aligned} (w^*,b^*)&=arg min_{(w,b)}\sum _{i=1}^{m}(f(x_i)-y_i)^2 \\ &=arg min_{(w,b)}\sum _{i=1}^{m}(y_i-wx_i-b)^2 \end{aligned}$(w∗,b∗)​=argmin(w,b)​i=1∑m​(f(xi​)−yi​)2=argmin(w,b)​i=1∑m​(yi​−wxi​−b)2​
利用最小二乘法求解最佳参数，可以利用偏导等于0得到闭式解，求导过程如下：
$\begin{aligned} \frac {\partial E_{(w,b)}}{\partial w} &=2(w\sum _{i=1}^{m}x_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) ) \end{aligned}$∂w∂E(w,b)​​∂b∂E(w,b)​​​=2(wi=1∑m​xi2​−i=1∑m​(yi​−b)xi​)=2(mb−i=1∑m​(yi​−wxi​))​

最终求解得到：
$\begin{aligned} w&=\frac {\sum_{i=1}^{m}y_i(x_i-\bar{x})}{\sum_{i=1}^{m}x_i^2-\frac{1}{m}(\sum_{i=1}^{m}x_i)^2)}\\ b&=\frac {1}{m}\sum_{i=1}^{m}(y_i-wx_i) \end{aligned}$wb​=∑i=1m​xi2​−m1​(∑i=1m​xi​)2)∑i=1m​yi​(xi​−xˉ)​=m1​i=1∑m​(yi​−wxi​)​

其中，$\bar{x}=\frac {1}{m}\sum_{i=1}^{m}x_i$xˉ=m1​∑i=1m​xi​为x的均值，求解是注意w的等式中不能含b，应带入b的等式进一步化简。

3.1.2 多元线性回归

使用向量形式可以将多元线性回归表示为：
$f(\mathbf{x_i})=\mathbf{w}^T\mathbf{x_i}+b$f(xi​)=wTxi​+b
因为涉及到多个属性，多条数据，使用矩阵会更清晰，并且涉及到矩阵的运算，矩阵本身的特征会是一个求解的影响因素。

将b吸收入$\mathbf w$w向量中的话，那么可以将$\mathbf{\hat w}$w^表示为：
$\mathbf{\hat w}=(\mathbf{w};b)=(w_1,w_2,\cdots ,w_d,b)$w^=(w;b)=(w1​,w2​,⋯,wd​,b)，维度为d+1
数据的矩阵$\mathbf X$X也对应增加全为1的一列，正好可以增加偏置b项，表示为：
$\mathbf X=\begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1d} & 1\\ x_{21} & x_{22} & \cdots & x_{2d} & 1\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{md} & 1 \end{pmatrix}$X=⎝⎜⎜⎜⎛​x11​x21​⋮xm1​​x12​x22​⋮xm2​​⋯⋯⋱⋯​x1d​x2d​⋮xmd​​11⋮1​⎠⎟⎟⎟⎞​

标签的向量可以表示为$y=(y_1;y_2;\cdots;y_m)$y=(y1​;y2​;⋯;ym​)。
$\hat{y}=f(\mathbf{X})=\mathbf{X}\hat{w}$y^​=f(X)=Xw^

优化目标
$\mathbf{\hat w}=argmin_{\mathbf{\hat w}} (\mathbf{y}-\mathbf{X}\mathbf{\hat w})^T(\mathbf{y}-\mathbf{X}\mathbf{\hat w})$w^=argminw^​(y−Xw^)T(y−Xw^)

求解——最小二乘法
$\frac {\partial E_{\hat w}}{\partial \hat w} =2\mathbf{X}^T(\mathbf{X}\mathbf{\hat w}-\mathbf{y})$∂w^∂Ew^​​=2XT(Xw^−y)

第一种情况：$\mathbf{X}^T\mathbf{X}$XTX为满秩矩阵或正定矩阵时
令导数为0，即可求得：
$\mathbf{\hat w^* }=(\mathbf{X}^T\mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}$w^∗=(XTX)−1XTy

第二种情况：$\mathbf{X}^T\mathbf{X}$XTX不是满秩矩阵时
此时可以解出多个$\mathbf{\hat w}$w^，选择哪一个由归纳偏好决定，常见的做法是引入正则化项。

3.1.3 线性回归的一般形式

对于样例$(\mathbf{x},y)$(x,y)，线性回归模型可以简写为：
$y=\mathbf{w}^T\mathbf{x}+b$y=wTx+b
实际上不仅仅可以让模型逼近与y，还可以逼近与y的衍生物
$y=g^{-1}(\mathbf{w}^T\mathbf{x}+b)$y=g−1(wTx+b)
其中$g^{-1}(x)$g−1(x)表示单调可微函数，这样的模型称为广义线性模型，g(·)称为联系函数，当g(·)为ln(·)时，模型为逻辑回归。

3.2 对数几率回归

3.2.1 对数几率回归定义

对数几率回归（常被称之为逻辑回归）是一种广义线性模型，如何从线性回归的一般形式转化到分类模型呢？

答案是只需找一个单调可微函数将分类任务的真实标记y与线性回归模型的预测值联系起来。

$z=\mathbf{w}^T\mathbf{x}+b$z=wTx+b，即将输出值z和真实标记y联系起来。

最简单的想法就是使用一个“单位阶跃函数”，当预测值大于0就判断为正例，小于0就判断为反例，预测值为临界值（如刚好0.5）就随机判断一个类别。

但从上图中也可以看出单位阶跃函数并不连续，因此不能直接作为联系函数，于是我们希望能找到近似于单位阶跃函数的代替函数，对数几率回归常用的替代函数为Sigmoid函数，它可以将输出值转化为一个接近于0或1的值。

代替函数为：
$y=\frac {1}{1+e^{-z}}$y=1+e−z1​
带入线性回归得到适合用于分类函数：
$y=\frac {1}{1+e^{-(\mathbf{w}^T\mathbf{x}+b)}}$y=1+e−(wTx+b)1​

化简一下就可以得到：
$ln\frac {y}{1-y}=\mathbf{w}^T\mathbf{x}+b$ln1−yy​=wTx+b

其中$\frac {y}{1-y}$1−yy​称为“几率（odds）”，$ln\frac {y}{1-y}$ln1−yy​称为“对数几率（log odds，亦称logit）”。

实际上，此模型在使用线性回归模型的预测结果取逼近真实标记的对数几率，因此，其对应的模型称为“对数几率回归”。

它是直接对分类的可能性进行建模，无需事先假设数据分布，可以避免假设分布不准确带来的影响。
不仅可以预测类别，还可以得到近似概率预测。

3.2.1 对数几率回归参数确定

将y视为正类别的后验概率p(y=1|x)，则1-y就为负类别的后延概率p(y=0|x)，那我们就可以得到：
$ln\frac {p(y=1|x)}{p(y=0|x}=\mathbf{w}^T\mathbf{x}+b$lnp(y=0∣xp(y=1∣x)​=wTx+b
化简为：
$p(y=1|x)=\frac {e^{\mathbf{w}^T\mathbf{x}+b}}{1+e^{\mathbf{w}^T\mathbf{x}+b}}$p(y=1∣x)=1+ewTx+bewTx+b​
$p(y=1|x)=\frac {1}{1+e^{\mathbf{w}^T\mathbf{x}+b}}$p(y=1∣x)=1+ewTx+b1​

可以通过“最大似然法”来估计参数，对数几率回归模型最大化“对数似然”，似然函数如下：
$l(\mathbf{w},b)=\sum_{i=1}^{m}ln p(y_i |\mathbf{x_i};\mathbf{w},b )$l(w,b)=∑i=1m​lnp(yi​∣xi​;w,b)

即每个样本属于其真实标记的概率越大越好，令$\boldsymbol \beta=(\boldsymbol w ;b),\hat{\boldsymbol x}=(\boldsymbol x;1)$β=(w;b),x^=(x;1)，则$\boldsymbol {w^Tx}+b=\boldsymbol{\beta ^T \hat{ x} }$wTx+b=βTx^，似然项可以表示为：

$l(\beta)=\sum_{i=1}^{m}\ln\left(y_ip_1(\hat{\boldsymbol x}_i;\beta)+(1-y_i)p_0(\hat{\boldsymbol x}_i;\beta)\right)$l(β)=i=1∑m​ln(yi​p1​(x^i​;β)+(1−yi​)p0​(x^i​;β))

最大化上式可以转化为最小化下式：
$l(\beta)=\sum_{i=1}^{m}(-y_i\beta^T\hat{\boldsymbol x}_i+\ln(1+e^{\beta^T\hat{\boldsymbol x}_i}))$l(β)=i=1∑m​(−yi​βTx^i​+ln(1+eβTx^i​))

[推导]：

$l(\beta)=\sum_{i=1}^{m}\ln\left(y_ip_1(\hat{\boldsymbol x}_i;\beta)+(1-y_i)p_0(\hat{\boldsymbol x}_i;\beta)\right)$l(β)=i=1∑m​ln(yi​p1​(x^i​;β)+(1−yi​)p0​(x^i​;β))
其中$p_1(\hat{\boldsymbol x}_i;\beta)=\cfrac{e^{\beta^T\hat{\boldsymbol x}_i}}{1+e^{\beta^T\hat{\boldsymbol x}_i}},p_0(\hat{\boldsymbol x}_i;\beta)=\cfrac{1}{1+e^{\beta^T\hat{\boldsymbol x}i}}$p1​(x^i​;β)=1+eβTx^i​eβTx^i​​,p0​(x^i​;β)=1+eβTx^i1​
代入上式可得：
$\begin{aligned} l(\beta)&=\sum_{i=1}^{m}\ln\left(\cfrac{y_ie^{\beta^T\hat{\boldsymbol x}_i}+1-y_i}{1+e^{\beta^T\hat{\boldsymbol x}i}}\right) \\ &=\sum_{i=1}^{m}\left(\ln(y_ie^{\beta^T\hat{\boldsymbol x}_i}+1-y_i)-\ln(1+e^{\beta^T\hat{\boldsymbol x}i})\right) \end{aligned}$l(β)​=i=1∑m​ln(1+eβTx^iyi​eβTx^i​+1−yi​​)=i=1∑m​(ln(yi​eβTx^i​+1−yi​)−ln(1+eβTx^i))​
由于$ y_i $=0或1，则： $l(\beta) = \begin{cases} \sum{i=1}^{m}(-\ln(1+e^{\beta^T\hat{\boldsymbol x}i})), & y_i=0 \ \sum{i=1}^{m}(\beta^T\hat{\boldsymbol x}_i-\ln(1+e^{\beta^T\hat{\boldsymbol x}i})), & y_i=1 \end{cases}$l(β)={∑i=1m(−ln(1+eβTx^i)),​yi​=0 ∑i=1m(βTx^i​−ln(1+eβTx^i)),​yi​=1​
两式综合可得： $l(\beta)=\sum{i=1}^{m}\left(y_i\beta^T\hat{\boldsymbol x}_i-\ln(1+e^{\beta^T\hat{\boldsymbol x}_i})\right)$l(β)=∑i=1m(yi​βTx^i​−ln(1+eβTx^i​))

由于此式仍为极大似然估计的似然函数，所以最大化似然函数等价于最小化似然函数的相反数，也即在似然函数前添加负号即可得结果。

最终的得到式子是关于$\boldsymbol \beta$β的高阶可到连续凸函数，根据凸优化理论，经典的数值优化算法如梯度下降算法、牛顿法都可以求得其最优解，于是得到
$\begin{aligned}\boldsymbol {\beta ^*}=\mathop{arg min}\limits_{\boldsymbol \beta} l(\boldsymbol \beta)\end{aligned}$β∗=βargmin​l(β)​

3.3 线性判别分析

线性判别分析（Linear Discriminant Analysis, 以下简称LDA），在学习LDA之前，有必要将其自然语言处理领域的LDA区别开来，在自然语言处理领域， LDA是隐含狄利克雷分布（Latent Dirichlet Allocation，简称LDA），他是一种处理文档的主题模型。我们本文只讨论线性判别分析，因此后面所有的LDA均指线性判别分析。

LDA的思想可以用一句话概括，就是“投影后类内方差最小，类间方差最大”。什么意思呢？ 我们要将数据在低维度上进行投影。

如上图所示，这些数据特征是二维的，我们希望将这些数据投影到一维的一条直线，让每一种类别数据的投影点尽可能的接近，而红色和蓝色数据中心之间的距离尽可能的大。

哪一种能更好的满足我们的标准呢？从直观上可以看出，右图要比左图的投影效果好，因为右图的黑色数据和蓝色数据各个较为集中，且类别之间的距离明显。左图则在边界处数据混杂。以上就是LDA的主要思想了，当然在实际应用中，我们的数据是多个类别的，我们的原始数据一般也是超过二维的，投影后的也一般不是直线，而是一个低维的超平面。

原理推导：TODO

3.4 多分类学习

多分类学习的基本思路是“拆解法”，即将多分类任务拆为若干个二分类任务求解，具体分为两步：

1. 对问题进行拆分，并为每一个二分类任务训练一个分类器；
2. 测试时，对这些分类器的预测结果进行集成并获得最终结果。

最经典的拆分策略有三种：一对一（OvO），一对其余（OvR），多对多（MvM）。

一对一（OvO）
若有N个类别，则两两配对，则产生N(N-1)/2个二分类任务，在测试阶段将新样本同时提交给所有分类器，于是可以得到N(N-1)/2个分类结果，最终通过投票产生最终分类结果。

一对其余（OvR）
OvR则是每次将一个类的样例作为正例、所有其他类别样例作为反例来训练N个分类器，测试时若仅有一个分类器预测为正类，则是相应类别；若多个分类器预测为正类，通常选择置信度最大的类别标记作为分类结果。

多对多（MvM）
MvM是每次将多干个类作为正类，若干个其他类作为反类，正反类的构造需要有特殊的设计，不能随意选取，介绍一种最常用的MvM技术：“纠错输出码”EOOC。

• 编码:
  对 N 个类别做 M 次划分（类别划分通过"编码矩阵" (coding matrix)指定）， 每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集;这样一共产生 M 个训练集，可 训练出 M 个分类器.
• 解码:
  M 个分类器分别对测试样本进行预测，这些预测标记组成一个编码.将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小 的类别作为最终预测结果.

编码矩阵有多种形式， 常见的主要有二元码和三元码，前者将每个类别分别指定为正类和反类，后者在正、反类之外，还可指 定"停用类"，示意图如下：

在图 3.5(a)中，分类器 $f_2$f2​将$C_1$C1​类和$C_3$C3​类的样例作为正例， $C_2$C2​类和 $C_4$C4​ 类的样例作为反例;
在图 3.5(b)中，分类器$f_4$f4​将 $C_1$C1​类和 $C_4$C4​类的样例作为正例，$C_3$C3​类的样例作为反例.
在解码阶段，各分类器的预测结果联合起来形成了测试示例的编码，该编码与各类所对应的编码 进行比较?
将距离最小的编码所对应的类别作为预测结果.
例如在图 3.5(a) 中， 若基于欧式距离，预测结果将是 $C_3$C3​。

为什么称为"纠错输出码"呢?这是因为在测试阶段， ECOC 编码对分类器的错误有一定的容忍和修正能力。

例如图 3.5(a)中对测试示例的正确预测编 码是 (-1， +1，+1，-1， +1)，假设在预测时某个分类器出错了，例如 $f_{2}$f2​出错从而 导致了错误编码 (-1， -1，+1，-1， +1)，但基于这个编码仍能产生正确的最终分 类结果$C_3$C3​.

3.5 类别不平衡问题

类别不平衡就是指分类任务中不同类别的训练样例数目差别很大的情况。
例如通常在 y > 0.5 时判别为正例，否则为反例 ，几率$\frac {y}{1-y}$1−yy​则反映了正例可能性与反例可能性之比值，阔值设置为 0.5 恰表明分类器认为真实正、反例可能性相同，即分类器决策规则为:

若$\frac {y}{1-y}>1$1−yy​>1，则预测为正例。

但是，当训练集中正、反例不同时，令$m^+$m+表示正例数目，$m^-$m−表示反例数目，则观测几率为$\frac {m^+}{m^-}$m−m+​，通常假设训练集是真实样本总体的无偏采样，因此观测几率就是真实几率，于是，只要分类器的预测几率高于观测几率就可以判断为正例：

若$\frac {y}{1-y}>\frac {m^+}{m^-}$1−yy​>m−m+​，则预测为正例。

于是，对其预测值进行调整，便就可以像基本方法一样进行预测：

若$\frac {y}{1-y}\cdot \frac {m^-}{m^+}>1$1−yy​⋅m+m−​>1，则预测为正例。

这就是类别不平衡学习的一个基本策略一"再缩放" (rescaling).

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

目前的处理不平衡问题大致有3种方法：

1. 欠采样：去掉多的，集成学习方法等
2. 过采样：增加少的，SMOTE方法等
3. 阈值移动：决策过程考虑样本偏差。若$\frac {y}{1-y}\cdot \frac {m^-}{m^+}>1$1−yy​⋅m+m−​>1，则预测为正例。