线性模型

线性模型

1. 基本形式

给定由\(d\)个属性描述的示例\(x=(x_1,x_2,\cdots,x_d)\),其中\(x_i\)\(x\)在第\(i\)个属性上的取值,线性模型(linear model)试图学得一个通过属性的线性组合来进行预测的函数,即 \[f(\pmb{x})=w_1x_1 + w_2x_2+ \cdots + w_dx_d + b\] 一般用向量形式写成 \[f(\pmb{x})=\pmb{w}^T \pmb{x} + b\] 其中\(w=(w_1,w_2,\cdots,w_d)\)\(w\)\(b\)学得之后,模型就得以确定。
线性模型形式简单、易于建模,许多功能强大的非线性模型(nonlinear model)可在线性模型的基础上通过引入层级结构或高维映射而得。此外,由于\(w\)直观表达了各属性在预测中的重要性,因此线性模型有很好的可解释性(comprehensibility)。

2. 线性回归

线性回归是一种监督学习下的线性模型,试图从给定数据集中学习一个线性模型来尽可能准确地预测实值输出标记。

2.1. 一元线性回归

一元线性回归指输入属性的数目只有一个,试图学得: \[f(x_i) = wx_i + b, \text{使得}f(x_i) \approx y_i.\] 确定公式中的\(w\)\(b\),关键在于如何衡量\(f(x)\)\(y\)之间的差别。均方误差是回归任务中最常用的性能度量,因此可以试图让均方误差最小化,即 \[\begin{align} (w^*,b^*) &= \arg \min_{(w,b)} \sum_{i=1}^m(f(x_i) - y_i)^2 \nonumber \\ &= \arg \min_{(w,b)} \sum_{i=1}^m(y_i - wx_i - b)^2 \nonumber \end{align}\] 均方误差有非常好的几何意义。它对应了常用的欧氏距离,基于均方误差最小化来进行模型求解的方法称为“最小二乘法”。在线性回归中,最小二乘法就是试图找到一条直线,是所有的样本到直线上的欧氏距离之和最小。
求解\(w\)\(b\)就是使\(E(w,b)=\sum_{i=1}^m(y_i-wx_i-b)^2\)最小化的过程,称为线性模型的最小二乘“参数估计”,可以将\(E(w,b)\)分别对\(w\)\(b\)求导,得到 \[\begin{align} \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) \nonumber \\ \frac{\partial E(w,b)}{\partial b} &= 2(mb - \sum_{i=1}^m (y_i-wx_i)) \nonumber \end{align}\] 然后令导数为0可得到\(w\)\(b\)最优解的闭式解: \[\begin{align} w &= \frac{\sum_{i=1}^m (y_i - \bar{y})x_i}{\sum_{i=1}^m x_i^2 - \frac{1}{m} (\sum_{i=1}^m x_i)^2} \nonumber \\ b &= \frac{1}{m} \sum_{i=1}^m (y_i - wx_i) \nonumber \end{align}\] 其中\(\bar{x} = \frac{1}{m} \sum_{i=1}^m x_i\)

2.2. 多元线性回归

多元线性回归指样本由多个属性描述,试图学得 \[f(\pmb{x}_i) = \pmb{w}^T \pmb{x}_i + b, \text{使得}f(\pmb{x}_i) \approx y_i\] 为了便于讨论,将\(w\)\(b\)吸收入向量形式\(\hat{w} = (w,b)\)中,把数据集\(D\)表示为一个\(m \times (d+1)\)大小的矩阵\(X\),即 \[\mathbf{X} = \left [ \begin{matrix} x_{11} & x_{12} & \cdots & x_{1d} & 1 \\ x_{21} & x_{22} & \cdots & x_{2d} & 1 \\ \vdots & \vdots & \cdots & \vdots & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{md} & 1\end{matrix} \right ] = \left [ \begin{matrix} \pmb{x}_1^T & 1 \\ \pmb{x}_2^T & 1 \\ \vdots & \vdots \\ \pmb{x}_m^T & 1 \end{matrix} \right ]\] 把标记也用向量的形式表示\(\pmb{y}= (y_1,y_2,\cdots,y_m)\),则有: \[\hat{\pmb{w}}^* = \arg \min_{\hat{\pmb{w}}} (\pmb{y} - \mathbf{X} \hat{\pmb{w}})^T (\pmb{y} - \mathbf{X} \hat{\pmb{w}})\]\(E_{\hat{\pmb{w}}} = (\pmb{y} - \mathbf{X} \hat{\pmb{w}})^T (\pmb{y} - \mathbf{X} \hat{\pmb{w}})\),对\(\hat{\pmb{w}}\)求导得到 \[\frac{\partial E_{\hat{\pmb{w}}}}{\partial \hat{\pmb{w}}} = 2 \mathbf{X}^T (\mathbf{X} \hat{\pmb{w}} - \pmb{y})\] 令上式为0求得\(\hat{\pmb{w}}\)最优解的闭式解,但由于涉及到矩阵的逆运算,所以要讨论\(\mathbf{X}^T \mathbf{X}\)是否满秩: (1)\(\mathbf{X}^T \mathbf{X}\)满秩
\(\mathbf{X}^T \mathbf{X}\)为满秩矩阵(full-rank matrix)或正定矩阵(positive definite matrix)时,令导数为0求得: \[\hat{\pmb{w}}^* = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T y\] 学得多元线性回归模型为 \[f(\hat{\pmb{x}_i}) = \hat{\pmb{x}}_i^T (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T y\] (2)\(\mathbf{X}^T \mathbf{X}\)不满秩
限时任务中\(\mathbf{X}^T \mathbf{X}\)往往不是满秩矩阵,数据的属性描述多于样例数,导致\(\mathbf{X}\)的列数多余行数,\(\mathbf{X}^T \mathbf{X}\)显然不满秩(方程组中因变量过多导致解出多组解),解出多个\(\hat{\pmb{w}}\)都能使均方误差最小化,选择哪一个作为输出将由学习算法的归纳偏好决定,常见的做法是引入正则化项。

3. logistic回归

3.1. logistic分布

\(X\)是连续随机变量,\(X\)服从logistic分布是指\(X\)具有下列分布函数和密度函数: \[\begin{align} F(x) &= P(X \leq x) = \frac{1}{1 + e^{-(x-\mu)/ \gamma}} \nonumber \\ f(x) &= F'(x) = \frac{e^{-(x-\mu)/ \gamma}}{\gamma(1+e^{-(x-\mu)/ \gamma})^2} \nonumber \end{align}\] 上式中,\(\mu\)为位置参数,\(\gamma > 0\)为形状参数。 分布函数属于logistic函数,其图形是一条S曲线(sigmoid curve),该曲线一点\((\mu, \frac{1}{2})\)为中心对称,即满足 \[F(-x + \mu) - \frac{1}{2} = -F(x + \mu) + \frac{1}{2}\]

3.2. 二项logistic回归模型

二项logistic回归模型(binomial logistic regression model)是一种分类模型,形式为参数化的logistic分布,有条件概率分布\(P(Y|X)\)表示,随机变量\(X\)取值为实数,随机变量\(Y\)取值为1或0。通过监督学习的方法估计模型参数。
二项logistic回归模型的条件概率分布: \[\begin{align} P(Y=1|\pmb{x}) &= \frac{\exp{(\pmb{w}· \pmb{x} + b)}}{1 + \exp{(\pmb{w}· \pmb{x} + b)}} \nonumber \\ P(Y=0|\pmb{x}) &= \frac{1}{1 + \exp{(\pmb{w}· \pmb{x} + b)}} \nonumber \end{align}\] logistic回归比较两个条件概率值的大小,将实例\(x\)分到概率值较大的那一类。
为了方便,将权值向量和输入向量加以扩充,仍记作\(\pmb{w}\)\(\pmb{x}\),即\(\pmb{w} = (w^{(1)},w^{(2)}, \cdots, w^{(n)}, b)^T\)\(\pmb{x} = (x^{(1)},x^{(2)}, \cdots, x^{(n)},1)^T\),此时logistic回归模型如下: \[\begin{align} P(Y=1|\pmb{x}) &= \frac{\exp{(\pmb{w}· \pmb{x})}}{1 + \exp{(\pmb{w}· \pmb{x})}} \nonumber \\ P(Y=0|\pmb{x}) &= \frac{1}{1 + \exp{(\pmb{w}· \pmb{x})}} \nonumber \end{align}\] 一个事件发生的几率(odds)是指该事件发生的概率与该事件不发生的概率的比值,如果事件发生的概率是\(p\),那么该事件的几率是\(\frac{p}{1-p}\),该事件的对数几率(log odds)或logit函数是 \[logit(p) = \log \frac{p}{1-p}\] 对logistic回归而言,对数几率为 \[\log \frac{P(Y=1|x)}{1 - P(Y=1|x)} = \pmb{w} · \pmb{x}\] 可以看出,在logistic回归模型中,输出\(Y=1\)的对数几率是输入\(x\)的线性函数。或者说,输出\(Y=1\)的对数几率是由输入\(x\)的线性函数表示的模型,即logistic回归模型。
logistic回归也称为对数几率回归

3.3. 模型参数估计

logistic回归模型学习时,对于给定的训练数据集\(T=\{(x_1,y_1), (x_2,y_2), \cdots, (x_N,y_N)\}\),其中,\(\pmb{x}_i \in \mathbf{R}^n\)\(y_i \in \{0,1\}\),应用极大似然估计法估计模型参数,从而得到logistic回归模型。
\(P(Y=1|\pmb{x}) = \pi(\pmb{x})\)\(P(Y=0|\pmb{x}) = 1 - \pi(\pmb{x})\): 似然函数为 \[\prod_{i=1}^N [\pi(\pmb{x}_i)]^{y_i}[1-\pi (\pmb{x}_i)]^{1-y_i}\] 对数似然函数为 \[\begin{align} L(\pmb{w}) &= \sum_{i=1}^N [y_i \log{\pi(\pmb{x}_i)} +(1-y_i) \log{(1-\pi(\pmb{x}_i))}] \nonumber \\ &= \sum_{i=1}^N[y_i \log{\frac{\pi(\pmb{x}_i)}{1 - \pi(\pmb{x}_i)}} + \log{(1 - \pi(\pmb{x}_i))}] \nonumber \\ &= \sum_{i=1}^N[y_i(\pmb{w}·\pmb{x}_i) - \log{(1 + \exp{(\pmb{w}·\pmb{x}_i)})}] \nonumber \end{align}\]\(L(\pmb{w})\)求极大值,得到\(\pmb{w}\)的估计值。问题变成了以对数似然函数为目标函数的最优化问题,通常采用的方法是梯度下降法及拟牛顿法。
假设\(\pmb{w}\)的极大似然估计是\(\hat{\pmb{w}}\),那么学到的logistic回归模型为 \[\begin{align} P(Y=1|\pmb{x}) &= \frac{\exp{(\hat{\pmb{w}}· \pmb{x})}}{1 + \exp{(\hat{\pmb{w}}· \pmb{x})}} \nonumber \\ P(Y=0|\pmb{x}) &= \frac{1}{1 + \exp{(\hat{\pmb{w}}· \pmb{x})}} \nonumber \end{align}\]

3.4. 多项logistic回归

上面介绍的二项logistic回归模型用于二类分类。可以将其推广为多项logistic回归模型(multi-nominal logistic regression model),用于多类分类。假设离散型随机变量\(Y\)的取值集合为\(\{1,2, \cdots, K\}\),那么多项logistic回归模型为 \[\begin{equation} P(Y=k|\pmb{x}) = \frac{\exp{(\pmb{w}_k · \pmb{x})}}{1 + \sum_{k=1}^{K-1} \exp{(\pmb{w}_k · \pmb{x})}}, k=1,2,\cdots,K-1 \nonumber \\ P(Y=K|\pmb{x}) = \frac{1}{1 + \sum_{k=1}^{K-1} \exp{(\pmb{w}_k · \pmb{x})}} \nonumber \end{equation}\] 式中,\(\pmb{x} \in \mathbf{R}^{n+1}\)\(w_k \in \mathbf{R}^{n+1}\)

4. 线性判别分析

线性判别分析(Linear Discriminant Analysis, LDA)是一种经典的线性学习方法。在二分类问题上最早由Fisher提出,也成为“Fisher判别分析”。

4.1. 二分类LDA

LDA的思想:给定训练样例集,设法将样例投影到一条直线上,使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离;在对新样本进行分类时,将其投影到同样的这条直线上,再根据投影点的位置类确定样本的类别。

设有数据集\(D=\{(x_i,y_i)\}_{i=1}^m\)\(y_i \in \{0,1\}\),\(X_i\)表示第\(i \in \{0,1\}\)类示例的集合,\(\mu_i\)表示均值向量,\(\Sigma_i\)表示协方差矩阵。将数据投影到直线\(y=\pmb{w}^T \pmb{x}\)上,两类样本的中心的投影分别为\(\pmb{w}^T \pmb{\mu}_0\)\(\pmb{w}^T \pmb{\mu}_1\),协方差为\(\pmb{w}^T \Sigma_0 \pmb{w}\)\(\pmb{w}^T \Sigma_1 \pmb{w}\),均为实数:
(1)投影后两类样本的中心:
\[m_j = \frac{1}{|C_j|} \sum_{x_i \in C_j} \pmb{w}^T \pmb{x}_i = \pmb{w}^T(\frac{1}{|C_j|} \sum_{x_i \in C_j} \pmb{x}_i) = \pmb{w}^T \pmb{\mu}_j\] (2)投影后两类样本的协方差: \[\begin{align} S_j^2 = \sum_{i \in C_j} (y_i-m_j)^2 &= \sum_{i \in C_j} (\pmb{w}^T (\pmb{x}_i - \mu_j))^2 \nonumber \\ &= \sum_{i \in C_j} (\pmb{w}^T (\pmb{x}_i - \pmb{\mu_j})) (\pmb{w}^T (\pmb{x}_i - \pmb{\mu_j}))^T \nonumber \\ &= \sum_{i \in C_j} \pmb{w}^T (\pmb{x}_i - \mu_j) (\pmb{x}_i - \mu_j)^T \pmb{w} \nonumber \\ &= \pmb{w}^T (\sum_{i \in C_j}(\pmb{x}_i - \mu_j) (\pmb{x}_i - \mu_j)^T) \pmb{w} \nonumber \\ &= \pmb{w}^T \Sigma_j \pmb{w} \nonumber \end{align}\] 欲使同类样例的投影点尽可能接近,异类样例的投影点尽可能远离,则可最大化目标: \[J = \frac{||\pmb{w}^T \mu_0 - \pmb{w}^T \mu_1||_2^2}{\pmb{w}^T \Sigma_0 \pmb{w} + \pmb{w}^T \Sigma_1 \pmb{w}} = \frac{\pmb{w}^T (\mu_0 - \mu_1) (\mu_0 - \mu_1)^T \pmb{w}}{\pmb{w}^T (\Sigma_0 - \Sigma_1) \pmb{w}}\]

类内散度矩阵: \[S_w = \Sigma_0 + \Sigma_1 = \sum_{\pmb{x} \in X_0} (\pmb{x} - \pmb{\mu}_0)(\pmb{x} - \pmb{\mu}_0)^T + \sum_{\pmb{x} \in X_1} (\pmb{x} - \pmb{\mu}_1)(\pmb{x} - \pmb{\mu}_1)^T\]

类间散度矩阵: \[S_b = (\pmb{\mu}_0 - \pmb{\mu}_1) (\pmb{\mu}_0 - \pmb{\mu}_1)^T\]

目标函数重写为: \[J = \frac{\pmb{w}^T S_b \pmb{w}}{\pmb{w}^T S_w \pmb{w}}\] 上式为LDA欲最大化的目标,即\(S_b\)\(S_w\)的广义瑞利商(其他博客中有介绍)。其中分子、分母都是关于\(\pmb{w}\)的二次项,因此上式的解与\(\pmb{w}\)的长度无关,只与其方向有关。不是一般性 ,令\(\pmb{w}^T S_w \pmb{w} = 1\),目标公式为: \[\begin{equation} \min_{\pmb{w}} - \pmb{w}^T S_b \pmb{w} \nonumber \\ s.t. \quad \pmb{w}^T S_w \pmb{w} = 1 \nonumber \end{equation}\] Lagrange函数: \[\begin{equation} L(\pmb{w}, \lambda) = - \pmb{w}^T S_b \pmb{w} + \lambda (\pmb{w}^T S_w \pmb{w} - 1) \nonumber \\ \frac{\partial L(\pmb{w}, \lambda)}{\partial \pmb{w}} = -S_b \pmb{w} + \lambda S_w \pmb{w} = 0 \nonumber \\ S_b \pmb{w} = \lambda S_w \pmb{w} \nonumber \end{equation}\] \(\lambda\)为拉格朗日乘子,因为\(S_b \pmb{w}\)的方向恒为\(\mu_0 - \mu_1\),令 \[S_b \pmb{w} = \lambda (\pmb{\mu}_0 - \pmb{\mu}_1)\] 带入式中求得: \[\pmb{w} = S_w^{-1} (\pmb{\mu}_0 - \pmb{\mu}_1)\] 考虑到数值稳定性,实践中通常采用奇异值分解的方法求\(S_w^{-1}\)\[\begin{equation} S_w = U \Sigma V^T \nonumber \\ S_w^{-1} = V \Sigma^{-1} U^T \nonumber \end{equation}\] \(\Sigma\)是一个是对角矩阵,其对角线上的元素是\(S_w\)的奇异值。
LDA还可以从贝叶斯决策理论的角度阐释,当两类数据同先验、满足高斯分布且协方差相等时,LDA可达到最优分类。

4.2. 多分类LDA

假设存在\(N\)个类,且第\(i\)类示例数为\(m_i\),定义全局散度矩阵\[S_t = S_b + S_w = \sum_{i=1}^m (\pmb{x}_i - \pmb{\mu}) (\pmb{x}_i - \pmb{\mu})^T\] 其中\(\mu\)是所有示例的均值向量,将类内散度矩阵\(S_w\)重定义为每个类别的类内散度矩阵之和,即: \[S_w = \sum_{i=1}^N S_{w_i}\] 其中 \[S_{w_i} = \sum_{\pmb{x} \in X_i} (\pmb{x}_i - \pmb{\mu}_i) (\pmb{x}_i - \pmb{\mu}_i)^T\] 由以上公式推得: \[S_b = S_t - S_w = \sum_{i=1}^N m_i (\pmb{\mu}_i - \pmb{\mu}) (\pmb{\mu}_i - \pmb{\mu})^T\] 多分类LDA可以有多种实现方法,使用\(S_b\)\(S_w\)\(S_t\)中任意两个即可,常见的一种实现是采用优化目标: \[\max_{\pmb{W}} \frac{tr(\pmb{W}^T S_b \pmb{W})}{tr(\pmb{W}^T S_w \pmb{W})}\] 式中\(\pmb{W} \in \pmb{R}^{d \times (N-1)}\)\(tr(·)\)表示矩阵的迹(trace),可通过广义特征值求解: \[S_b \pmb{W} = \lambda S_w \pmb{W}\] \(W\)的闭式解则是\(S_w^{-1} S_b\)\(d'\)个最大的非零广义特征值所对应的特征向量组成的矩阵,\(d' \leq N-1\)
若将\(W\)是为一个投影矩阵,则多分类LDA将样本投影到\(d'\)维空间,\(d'\)通常远小于数据原有的属性数\(d\)。可以通过这个投影来减小样本点的维数,并且投影过程中使用了类别信息,因此LDA也常被是为一种经典的监督降维方法。

5. 多分类学习

实践中常遇到多分类学习任务,有些二分类学习方法可直接推广到多分类,但在更多情形下,可以基于一些基本策略,利用二分类学习器来解决多分类问题。
多分类学习的基本思路是“拆解法”,即将多分类任务拆为若干个二分类任务求解。最经典的拆分策略有三种:一对一(One vs One,OvO)、一对其余(One vs Rest,OvR)和多对多(Many vs Many,MvM)。

5.1. 一对一

一对一将数据集\(D\)对应的类别\(y_i \in \{C_1,C_2, \cdots, C_N\}\)两两配对,产生\(N(N-1)/2\)个二分类任务。
例如训练区分\(C_i\)\(C_j\)的分类器,该分类器将\(D\)中的\(C_i\)类样例作为正例,\(C_j\)类样例作为反例。
在测试阶段,将新样本同时提交给所有分类器,将得到\(N(N-1)/2\)个分类结果,最终结果可通过投票产生。

5.2. 一对其余

一对其余是每次将一个类的样例作为正例、所有其他类的样例作为负例作为反例训练\(N\)个分类器,在测试时若只有一个分类器预测为正例,则对应的类别标记为最终结果。如果有多个分类器预测为正例,则需考虑各分类器的置信度。
通常,一对一的存储开销和测试时间开销比一对其余大。但在训练时,一对其余的每个分类器均使用全部的训练数据,而一对一只使用两类数据,所以类别很多时,一对一的训练时间开销通常比一对其余小。至于预测性能,取决于具体的数据分布,在多数情形下两者差不多。

5.3. 多对多

多对多每次将若干个类作为正类,若干个其他类作为反类,并且正类和反类构造必须有特殊的设计,不能随意选取,最常用的多对多的技术是“纠错输出码”(Error Correcting Output Codes,ECOC)。
ECOC是将编码的思想引入类别拆分,并尽可能在解码过程中具有容错性,工作过程主要分为两步:

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

6. 类别不平衡问题

前面的分类学习方法都有一个共同的基本假设,即不同类别的训练样本数目相当,通常不同类别的训练样例数目稍有差别影响不大,但是如果差别很大就会对学习过程造成困扰。
类别不平衡(class-imbalance)就是指分类任务中不同类别的训练样例数目差别很大的情况。现实的分类学习任务中经常遇到类别不平衡,例如通过拆分法解决多分类问题。
再用\(y=\pmb{w}^T \pmb{x} + b\)对新样本 \(\pmb{x}\)进行分类时,实际上再用预测出的\(y\)值与一个阈值进行比较,通常\(y \geq 0.5\)判为正例,否则为反例。\(y\)表达了正例的可能性,几率\(\frac{y}{1-y}\)则反映了正例可能性与反例可能性的比值,阈值设为0.5表明分类器认为正、反例可能性相同,即分类器决策规则为 \[若 \quad \frac{y}{1-y} > 1 \quad 则预测为正例\] 然而,当训练集中正、反例数目不同时,\(m^+\)表示正例数目,\(m^-\)表示反例数目,观测几率为\(\frac{m^+}{m^-}\),通常假设训练集是真实样本总体的无偏采样,因此观测几率代表了真实几率,所以预测几率大于观测几率应判为正例,即 \[若 \quad \frac{y}{1-y} > \frac{m^+}{m^-} \quad 则预测为正例\] 引出类别不平衡学习的一个基本策略——再缩放\[\frac{y'}{1-y'} = \frac{y}{1-y} \times \frac{m^-}{m^+}\] 通过将上式与1比较判别正、反例。再缩放是“代价敏感学习”的基础,其中用\(cost^+ / cost^-\)代替\(m^-/m^+\)。 实际中“训练集是真实样本总体的无偏采样”这个假设往往不成立,所以我们未必能有效地基于训练集观测几率来推断真实几率,现有技术有三类做法:

  1. 欠采样:去除训练集中的一些反例使得正、反例数目接近,然后进行学习。但是,如果随机丢弃反例,可能会丢失一些重要信息。代表算法EasyEnsemble,利用集成学习机制,将反例划分为若干个集合供不同学习器使用,对于每个学习器都进行了欠采样,从全局看却不会丢失信息;
  2. 过采样:在训练集中增加一些正例使得正、反例数目接近,再进行学习。过采样法不能简单地对初始正例样本进行重复采样,否则会导致过拟合。代表算法SMOTE,通过对训练集里的正例进行插值来产生额外的正例;
  3. 阈值移动:直接基于原始训练集进行学习,在用训练好的分类器进行预测时,使用“再缩放”的方法进行决策。