3 线性模型

3.1 基本形式

• 给定有d个属性描述的示例$x=(x_1;x_2;...;x_d)$。线性模型试图学得一个通过属性的线性组合来进行预测的函数，即：

$$f(x)=\sum _{i=1}^d{w}_i{x}_i+b$$

一般使用向量形式，记为$f(x)={\mathbf{w}}^T\mathbf{x}+b$（即$f(x)=\overrightarrow{w}\cdot \overrightarrow{x}+b$），其中$\overrightarrow{w}=(w_1,w_2,\dots ,w_d)$。

• 线性模型中 f(x) 可以是各种“尺度”上的函数，例如：

f(x)为实数域上的实值函数	线性回归模型
f(x)为离散的值	线性多分类模型
f(x)为对数	对数线性模式
f(x)进行sigmoid非线性变换	对数几率回归

3.2 线性回归

概念

• 线性回归问题就是试图学到一个线性模型尽可能准确地预测新样本的输出值，在这类问题中，往往我们会先得到一系列的有标记数据；有但输入的情形，也有多输入的情形。

• 有时这些输入的属性值并不能直接被我们的学习模型所用，需要进行相应的处理，对于连续值的属性，一般都可以被学习器所用，有时会根据具体的情形作相应的预处理，例如：归一化等；对于离散值的属性，可作下面的处理：

  • 若属性值之间存在“序关系”，则可以将其转化为连续值，例如：身高属性分为“高”“中等”“矮”，可转化为数值：{1, 0.5, 0}。
  • 若属性值之间不存在“序关系”，则通常将其转化为向量的形式，例如：性别属性分为“男”“女”，可转化为二维向量：{（1，0），（0，1）}。

线性回归（输入属性只有一个时适用）

• 欧几里得距离：即“欧氏距离”，为

$$D(x,y)=\sqrt{\sum _{i=1}^n(x_i^2-y_i^2)}$$

• 最小二乘法(Least Square Method, LSM)：基于均方误差最小化来进行模型求解的方法称为最小二乘法。在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧氏距离之和最小。按照这一原则，有

$$\begin{array}{rl}(w\ast ,b\ast )& =\arg \underset{(w,b)}{min}\sum _{i=1}^m(f(x_i)-y_i{)}^2\\ & =\arg \underset{(w,b)}{min}\sum _{i=1}^m(y_i-w{x}_i-b{)}^2\end{array}$$

• 参数估计(parameter estimation)：求解w, b使得$E_{(}e,b)=\sum _{i=1}^m(y_i-w{x}_i+b{)}^2$的过程，，称为线性回归模型的最小二乘“参数估计”。

$$\begin{array}{rl}\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-w{x}_i))\end{array}$$

令上式为0，得到w，b的闭式(Closed-form)解：

$$\begin{array}{rl}w=& \frac{\sum _{i=1}^m{y}_i(x_i-\overline{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-w{x}_i)\end{array}$$

多元线性回归（输入属性有多个时使用）

• 当输入属性有多个的时候，例如对于一个样本有d个属性{(x1,x2...xd), y}，则$y=wx+b$需要写成

  $$y_i=\sum _{k=1}^d{w}_k{x}_{ik}+b$$

• 通常对于多元问题，常常使用矩阵的形式来表示数据。

  在本问题中，将具有m个样本的数据集表示成矩阵X，将系数w与b合并成一个列向量，这样每个样本的预测值以及所有样本的均方误差最小化就可以写成下面的形式：

$$\mathbf{X}\cdot \hat{\omega }=\left(\begin{array}{ccccc}{x}_{11}& x_{12}& \cdots & x_{1d}& 1\\ x_{21}& x_{22}& \cdots & x_{2d}& 1\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ x_{m1}& x_{m2}& \cdots & x_{md}& 1\end{array}\right)\cdot \left(\begin{array}{c}{\omega }_1\\ {\omega }_2\\ ⋮\\ {\omega }_d\\ b\end{array}\right)=\left(\begin{array}{c}f(x_1)\\ f(x_2)\\ ⋮\\ f(x_m)\end{array}\right)$$

其中，$f(x_i)=\sum _{k=1}^d{\omega }_k{x}_{ik}+b$，$i\in [1,m]$。

$${\hat{\omega }}^{\ast }=\arg \underset{\hat{\omega }}{min}(\mathbf{y}-\mathbf{X}\hat{\omega }{)}^T(\mathbf{y}-\mathbf{X}\hat{\omega })$$

同样地，我们使用最小二乘法对w和b进行估计，令均方误差的求导等于0，需要注意的是，当一个矩阵的行列式不等于0时，我们才可能对其求逆，因此对于下式，我们需要考虑矩阵（X的转置*X）的行列式是否为0，若不为0，则可以求出其解，若为0，则需要使用其它的方法进行计算，书中提到了引入正则化，此处不进行深入。

对数线性回归

1. 有时像上面这种原始的线性回归可能并不能满足需求，例如：y值并不是线性变化，而是在指数尺度上变化。这时我们可以采用线性模型来逼近y的衍生物，如$\ln y$，这时衍生的线性模型如下所示，实际上就是相当于将指数曲线投影在一条直线上，如下图所示：

   

2. 广义线性模型(Generalized Linear Model)：更一般地，考虑单调可微函数$g(\cdots )$，令

$$y=g^{-1}({\mathbf{w}}^T\mathbf{x}+b),$$

此时得到的模型称为“广义线性模型"，其中，函数$g(\cdot )$称为“联系函数”(Linked Function)。则对数线性回归是广义线性模型的特例。

3.3 对数几率回归

引入

1. 3.2节的线性回归模型适合于回归任务。若要做分类任务，则需要使用广义线性模型$y=g^{-1}({\mathbf{w}}^T\mathbf{x}+b)$。

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

2. 考虑二分类问题：其输出标志为$y\in \{0,1\}$，而线性回归模型产生的预测值$z\in \mathbb{R}$。找到一种映射$f:\mathbb{R}\to \{0,1\}$，且$f(\cdot )$单调可微。（即找到一个Sigmoid函数）

3. Sigmoid函数：Sigmoid函数即形似S的函数。其中，对数几率函数是一种常见的Sigmoid函数。

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

对数几率和对率回归

• 对数几率(Log Odds或Logit)：若将对数几率函数作为$g^{-}(\cdot )$并代入广义线性模型函数，有

$$\begin{array}{r}y=\frac{1}{1+e^{-({\mathbf{w}}^T\mathbf{x}+b)}}\\ \ln \frac{y}{1-y}={\mathbf{w}}^T\mathbf{x}+b\end{array}$$

• 若将y看做样本为正例的概率，（1-y）看做样本为反例的概率，则上式实际上使用线性回归模型的预测结果器逼近真实标记的对数几率。因此这个模型称为“对数几率回归”（logistic regression），也有一些书籍称之为“逻辑回归”。

• 对率回归实际上是一种分类学习方法。它的优点有：

  1. 直接对分类可能性进行建模，无需事先假设数据分布，这样就避免了假设分布不准确所带来的问题。
  2. 不是仅预测出“类别”，而是可得到近似概率预测，这对许多需利用概率辅助决策的任务很有用。
  3. 对率函数是任意阶可导的凸函数，有很好的数学性质，现有的许多数值优化算法都可直接用于求取最优解。

• 如何确定w和b？若将y视作类后验概率估计$$p(y=1\mid x)$$，则

$$\ln \frac{p(y=1\mid x)}{p(y=0\mid x)}={\mathbf{w}}^T\mathbf{x}+b$$

其中，

$$\begin{array}{r}p(y=1\mid x)=\frac{e^{-({\mathbf{w}}^T\mathbf{x}+b)}}{1+e^{-({\mathbf{w}}^T\mathbf{x}+b)}}\\ p(y=0\mid x)=\frac{1}{1+e^{-({\mathbf{w}}^T\mathbf{x}+b)}}\end{array}$$

我们可通过“极大似然法”(maximum likelihood method)来估计w,b。即，给定数据集$D=\{({\mathbf{x}}_1,y_1),({\mathbf{x}}_2,y_2),\dots ,({\mathbf{x}}_N,y_N)\}$，假设这些样本是独立同分布的，我们可写出似然函数：

$$\begin{array}{rl}l(\mathbf{w},b)& =\sum _{i=1}^N\ln p(y_i\mid {\mathbf{x}}_i;\mathbf{w},b)\end{array}$$

即令令每个样本属于其真实标记的概率越大越好。令$\beta =(\mathbf{w},b),\hat{x}=(\mathbf{x};1)$，再令$p_1(\hat{x};\beta )=p(y=1\mid \hat{x},\beta )$$，$$p_0(\hat{x};\beta )=1-p_1(\hat{x};\beta )$，则

$$\begin{array}{rl}l(\beta )& =\sum _{i=1}^N(-y_i{\beta }^T{\hat{x}}_i+\ln (1+e^{{\beta }^T{\hat{x}}_i}))\end{array}$$

这是关于$\beta$的凸函数，可通过梯度下降法等方法求解。

3.4 线性判别分析

线性判别分析（Linear Discriminant Analysis，简称LDA）,其基本思想是：将训练样本投影到一条直线上，使得同类的样例尽可能近，不同类的样例尽可能远。如图所示：

想让同类样本点的投影点尽可能接近，不同类样本点投影之间尽可能远，即：让各类的协方差之和尽可能小，不用类之间中心的距离尽可能大。基于这样的考虑，LDA定义了两个散度矩阵。

• 类内散度矩阵（within-class scatter matrix）

• 类间散度矩阵(between-class scaltter matrix)

因此得到了LDA的最大化目标：“广义瑞利商”（generalized Rayleigh quotient）。

从而分类问题转化为最优化求解w的问题，当求解出w后，对新的样本进行分类时，只需将该样本点投影到这条直线上，根据与各个类别的中心值进行比较，从而判定出新样本与哪个类别距离最近。求解w的方法如下所示，使用的方法为λ乘子。

若将w看做一个投影矩阵，类似PCA的思想，则LDA可将样本投影到N-1维空间（N为类簇数），投影的过程使用了类别信息（标记信息），因此LDA也常被视为一种经典的监督降维技术。

3.5 多分类学习

1. 现实中我们经常遇到不只两个类别的分类问题，即多分类问题，在这种情形下，我们常常运用“拆分”的策略，通过多个二分类学习器来解决多分类问题，即将多分类问题拆解为多个二分类问题，训练出多个二分类学习器，最后将多个分类结果进行集成得出结论。

2. 最为经典的拆分策略有三种：“一对一”（OvO）、“一对其余”（OvR）和“多对多”（MvM），核心思想与示意图如下所示。

   • OvO：给定数据集D，假定其中有N个真实类别，将这N个类别进行两两配对（一个正类/一个反类），从而产生N（N-1）/2个二分类学习器，在测试阶段，将新样本放入所有的二分类学习器中测试，得出N（N-1）个结果，最终通过投票产生最终的分类结果。

   • OvR：给定数据集D，假定其中有N个真实类别，每次取出一个类作为正类，剩余的所有类别作为一个新的反类，从而产生N个二分类学习器，在测试阶段，得出N个结果，若仅有一个学习器预测为正类，则对应的类标作为最终分类结果。

     

   OvR只需要训练N个分类器，而OvO需要训练$N(N-1)/2$个训练器。因此，OvO的存储开销和测试时间开销通常比OvR更大。但是，在训练时，OvR的每个分类器均使用全部训练样例，而OvO的每个分类器仅用到两个类的样例。因此，在类别很多时，OvO的训练时间开销通常比OvR更小。

   • MvM：给定数据集D，假定其中有N个真实类别，每次取若干个类作为正类，若干个类作为反类（通过ECOC码给出，编码），若进行了M次划分，则生成了M个二分类学习器，在测试阶段（解码），得出M个结果组成一个新的码，最终通过计算海明/欧式距离选择距离最小的类别作为最终分类结果。

3. 纠错输出码(Error Correcting Output Codes, ECOC)：它是一种最常用的MvM技术。它将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性。ECOC工作过程主要分为两步：

   1. 编码：对N个类别做M次划分，每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集；这样一共产生M 个训练集，可训练出M个分类器。
   2. 解码：M 个分类器分别对测试样本进行预测，这些预测标记组成一个编码。将这个预测编码与每个类别各自的编码进行比较。返回其中距离最小的类别作为最终预测结果。

4. 海明距离(Hamming Distance)：用于测量两个等长字符串之间的差异，也就是说，它是两个字符串对应位置的不同字符的个数。
5. 欧氏距离(Euclid Distance)：最常见的距离，就是指两点间连线的距离。

3.6 类别不平衡问题

类别不平衡（class-imbanlance）就是指分类问题中不同类别的训练样本相差悬殊的情况，例如正例有900个，而反例只有100个，这个时候我们就需要进行相应的处理来平衡这个问题。常见的做法有三种：

1. 在训练样本较多的类别中进行“欠采样”（undersampling）,比如从正例中采出100个，常见的算法有：EasyEnsemble。
2. 在训练样本较少的类别中进行“过采样”（oversampling）,例如通过对反例中的数据进行插值，来产生额外的反例，常见的算法有SMOTE。
3. 直接基于原数据集进行学习，对预测值进行“再缩放”处理。其中再缩放也是代价敏感学习的基础。