Note of Machine Learning 3

第3章　线性模型

3.1　基本形式

线性模型(linear model)试图学得一个通过属性的线性组合来进行预测的函数，即

$$f(x)=w_1x_1+w_2x_2+\dots+w_dx_d+b,　　　　　(3.1)$$

一般用向量形式写成

$$f(x)=w^Tx+b,　　　　　(3.2)$$

w和b学得之后模型得以确定。许多功能强大的非线性模型(nonlinear model)可在线性模型的基础上通过引入层级结构或高维映射而得。由于w直观表达了各属性在预测中的重要性，因此线性模型有很好的可解释性(comprehensibility) or 可理解性(understandability)。

3.2　线性回归

“线性回归”(linear regression)试图学得一个线性模型以尽可能准确地预测实值输出标记。

对离散属性，若属性值存在”序”(order)关系，可通过连续化将其转化为连续值；若属性值间不存在序关系，假设有k个属性值，则通常转化为k维向量。

线性回归试图学得

$$f(x_i)=wx_i+b,使得f(x_i)\simeq y_i.　　　　　(3.3)$$

2.3介绍过，均方误差(2.2)是回归任务中最常用的性能度量，可试图让均方误差最小化：

$$\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.　　　　　(3.4) \end{aligned}$$

均方误差的几何意义对应了”欧式距离”(Euclidean distance)。基于均方误差最小化来进行模型求解的方法称为”最小二乘法”(least square method)。求解并使$E{(w,b)}=\sum{i=1}^m(y_i-wx_i-b)^2$最小化的过程称为线性回归模型的最小二乘”参数估计”(parameter estimation)。可分别对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),　　　　　(3.5)\\ \frac{\partial E_{(w,b)}}{\partial b}=2(mb-\sum_{i=1}^m(y_i-wx_i)),　　　　　(3.6)$$

然后令式(3.5)和(3.6)为零可得到w和b最优解的闭式(closed-form)解

$$w=\frac{\sum_{i=1}^my_i(x_i-\bar{x})}{\sum_{i=1}^mx_i^2-\frac{1}{m}(\sum_{i=1}^mx_i)^2},　　　　　(3.7)\\ b=\frac{1}{m}\sum_{i=1}^m(y_i-wx_i),　　　　　(3.8)$$

其中$\bar{x}=\frac{1}{m}\sum_{i=1}^mx_i$为x的均值。

若数据集样本由d个属性描述，试图学得$f(x_i)=w^Tx_i+b,使得f(x_i)\simeq y_i,$这称为”多元线性回归”(multivariate linear regression)。

把w和b吸收入向量形式$\hat{w}=(w;b)$，把数据集D表示为一个$m\times(d+1)$的矩阵X，每行为一个示例，前d个元素为d个属性值，最后一个元素置1：

$$X= \left( \begin{matrix} x_{11}&x_{12}&\dots&x_{1d}&1\\ x_{21}&x_{22}&\dots&x_{2d}&1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ x_{m1}&x_{m2}&\dots&x_{md}&1 \end{matrix} \right)= \left( \begin{matrix} x_1^T&1\\ x_2^T&1\\ \vdots&\vdots\\ x_m^T&1 \end{matrix} \right),$$

再把标记也写成向量形式$y=(y_1;y_2;\dots;y_m)$，则类似于(3.4)有

$$\hat{w}^*={\arg\min}_{\hat{w}}(y-X\hat{w})^T(y-X\hat{w}).　　　　　(3.9)$$

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

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

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

当$X^TX$为满秩矩阵(full-rank matrix)或正定矩阵(positive definite matrix)时，令(3.10)为零可得

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

令$\hat{x}_i=(x_i;1)$,则最终学得的多元线性回归模型为

$$f(\hat{x}_i)=\hat{x}_i^T(X^TX)^{-1}X^Ty.　　　　　(3.12)$$

然而现实中矩阵往往不满秩，解出多个$\hat{w}$时常见做法是引入正则化(regularization)项。

将线性回归模型写为

$$\ln y=w^Tx+b.　　　　　(3.14)$$

这就是”对数线性回归”(log-linear regression)。更一般地，考虑单调可微函数$g(\cdot)$，令

$$y=g^{-1}(w^Tx+b),　　　　　(3.15)$$

这样得到的模型称为”广义线性模型”(generalized linear model)，其中函数$g(\cdot)$称为”联系函数”(link function)。

3.3　对数几率回归

若要做的是分类任务，只需找一个单调可微函数将分类任务的真实标记y与线性回归模型的预测值联系起来。考虑二分类任务，线性回归模型产生的预测值是实值，需将实值转换为0/1值。最理想的是”单位阶跃函数”(unit-step function)

$$y= \left\{ \begin{array}{} 0,　　z<0;\\ 0.5,　z=0;\\ 1,　　z>0, \end{array} \right.　　　　　(3.16)$$

但单位阶跃函数不连续，所以用对数几率函数(logistic function)作为其”替代函数”(surrogate function):

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

对数几率函数是一种”Sigmoid函数”，将其代入(3.15)得到

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

类似于(3.14),(3.18)可变化为

$$\ln\frac{y}{1-y}=w^T+b.　　　　　(3.19)$$

若将y视为样本x作为正例的可能性，则1-y是其反例可能性，两者的比值

$$\frac{y}{1-y}　　　　　(3.20)$$

称为”几率”(odds)，反映了x作为正例的相对可能性。对几率取对数则得到”对数几率”(log odds,logit)

$$\ln\frac{y}{1-y}.　　　　　(3.21)$$

此模型称为”对数几率回归”(logistic regression,logit regression)，实际上是一种分类学习方法。优点在于直接对分类可能性进行建模，避免了假设分布不准确所带来的问题。

若将(3.18)中的y视为类后验概率估计$p(y=1|x)$，则(3.19)重写为

$$\ln\frac{p(y=1|x)}{p(y=0|x)}=w^Tx+b.　　　　　(3.22)$$

显然有

$$p(y=1|x)=\frac{e^{w^Tx+b}}{1+e^{w^Tx+b}},　　　　　(3.23)\\ p(y=0|x)=\frac{1}{1+e^{w^Tx+b}},　　　　　(3.24)$$

可通过”极大似然法(maximum likelihood method)”来估计w和b。给定数据集，对率回归模型最大化”对数似然”(loglikehood)

$$\ell(w,b)=\sum_{i=1}^m\ln p(y_i|x_i;w,b),　　　　　(3.25)$$

令$\beta=(w;b),\hat{x}=(x;1)$，则$w^Tx+b$可简写为$\beta^T\hat{x}$。再令$p_1(\hat{x};\beta)=p(y=1|\hat{x};\beta),p_0(\hat{x};\beta)=p(y=0|\hat{x};\beta)=1-p_1(\hat{x};\beta)$，则(3.25)中的似然项可重写为

$$p(y_i|x_i;w,b)=y_ip_1(\hat{x}_i;\beta)+(1-y_i)p_0(\hat{x}_i;\beta).　　　　　(3.26)$$

将(3.26)代入(3.25)，并根据(3.23)和(3.24)可知，最大化(3.25)等价于最小化

$$\ell(\beta)=\sum_{i=1}^m(-y_i\beta^T\hat{x}_i+\ln(1+e^{\beta T\hat{x}_i})).　　　　　(3.27)$$

(3.27)是关于$\beta$的高阶可导连续凸函数，可有梯度下降法(gradient descent method)、牛顿法(Newton method)等求其最优解，得到

$$\beta^*={\arg\min}_\beta\ell(\beta).　　　　　(3.28)$$

以牛顿法为例，第t+1轮迭代解的更新公式为

$$\beta^{t+1}=\beta^t-(\frac{\partial^2\ell(\beta)}{\partial\beta\partial\beta^T})^{-1}\frac{\partial\ell(\beta)}{\partial\beta},　　　　　(3.29)$$

其中关于$\beta$的一阶、二阶导数分别为

$$\frac{\partial\ell(\beta)}{\partial\beta}=-\sum_{i=1}^m\hat{x}_i(y_i-p_1(\hat{x}_i;\beta)),　　　　　(3.30)\\ \frac{\partial^2\ell(\beta)}{\partial\beta\partial\beta^T}=\sum_{i=1}^m\hat{x}_i\hat{x}_i^Tp_1(\hat{x}_i;\beta)(1-p_1(\hat{x}_i;\beta)).　　　　　(3.31)$$

3.4　线性判别分析

线性判别分析(Linear Discriminant Analysis,简称LDA)，亦称”Fisher判别分析”。给定训练样例集，将样例投影到一条直线上，使同类样例投影点尽可能接近、异类样例投影点尽可能远离；在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别。

给定数据集$D={(xi,y_i)}{i=1}^m,y_i\in{0,1}​$，令$X_i、\mu_i、\Sigma_i​$分别表示第$i\in{0,1}​$类示例的集合、均值向量、协方差矩阵。两类样本的中心在直线上的投影分别为$w^T\mu_0​$和$w^T\mu_1​$；协方差分别为$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​$尽可能大。同时考虑二者得到欲最大化的目标

$$\begin{aligned} J&=\frac{||w^T\mu_0-w^T\mu_1||_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}.　　　　　(3.32) \end{aligned}$$

定义”类内散度矩阵”(within-class scatter matrix)

$$\begin{aligned} S_w&=\Sigma_0+\Sigma_1\\ &=\sum_{x\in X_0}(x-\mu_0)(x-\mu_0)^T+\sum_{x\in X_1}(x-\mu_1)(x-\mu_1)^T　　　　　(3.33) \end{aligned}$$

以及”类间散度矩阵”(between-class scatter matrix)

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

则(3.32)可重写为

$$J=\frac{w^TS_bw}{w^Ts_ww}.　　　　　(3.35)$$

这就是LDA欲最大化的目标，即$S_b​$与$S_w​$的”广义瑞利商”(generalized Rayleigh quotient)。令$w^TS_ww=1​$，则(3.35)等价于

$$\begin{aligned} &\min_w-w^TS_bw　　　　　(3.36)\\ &s.t.　w^TS_ww=1. \end{aligned}$$

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

$$S_bw=\lambda S_ww,　　　　　(3.37)$$

其中$\lambda$是拉格朗日乘子。注意到$S_bw$的方向恒为$\mu_0-\mu_1$，不妨令

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

代入(3.37)得

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

实践中通常使$S_w=U\Sigma V^T$进行奇异值分解，$\Sigma$是一个实对角矩阵，对角线上的元素是$S_w$的奇异值，再由$S_w^{-1}=V\Sigma^{-1}U^T$得到$S_w^{-1}$。

将LDA推广到多分类任务中。假定存在N个类，且第i类示例数为$m_i$。先定义”全局散度矩阵”

$$\begin{aligned} S_t&=S_b+S_w\\ &=\sum_{i=1}^m(x_i-\mu)(x_i-\mu)^T,　　　　　(3.40) \end{aligned}$$

$\mu$是所有示例的均值向量。将类内散度矩阵$S_w$重定义为每个类别的散度矩阵之和，即

$$S_w=\sum_{i=1}^NS_{w_i},　　　　　(3.41)$$

其中

$$S_{w_i}=\sum_{x\in X_i}(x-\mu_i)(x-\mu_i)^T.　　　　　(3.42)$$

由式(3.40)~(3.42)可得

$$\begin{aligned} S_b&=S_t-S_w\\ &=\sum_{i=1}^Nm_i(\mu_i-\mu)(\mu_i-\mu)^T.　　　　　(3.43) \end{aligned}$$

LDA可使用$S_b,S_w,S_t$中任意两个实现，常见的一种是采用优化目标

$$\max_W\frac{tr(W^TS_bW)}{tr(W^TS_wW)},　　　　　(3.44)$$

其中$W\in\mathbb{R}^{d\times(N-1)},tr(\cdot)$表示矩阵的迹(trace)。上式可通过如下广义特征值问题求解：

$$S_bW=\lambda S_wW.　　　　　(3.45)$$

W的闭式解则是$S_w^{-1}S_b$的d’个最大非零广义特征值所对应的特征向量组成的矩阵，$d’\leq N-1$。

若将$W$视为投影矩阵，则样本投影到d’维空间，d‘通常远小于原有属性数d，可通过这个投影来减小样本点的维数。

3.5　多分类学习

可利用二分类学习器解决多分类问题。多分类学习的基本思路是”拆解法”，将多分类任务拆为若干个二分类任务求解。最经典的拆分策略有三种：”一对一”(One vs. One,OvO)、”一对其余”(One vs. Rest,OvR)和”多对多”(Many vs.Many,MvM)。

给定数据集$D={(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)},y_i\in{C_1,C_2,\dots,C_N}$。OvO将N个类两两配对产生N(N-1)/2个二分类任务，OvR每次将一个类的样例作为正例、所有其他类的样例作为反例训练N个分类器。两者各有优劣。

MvM的正、反类构造不能随意选取。”纠错输出码”(Error Correcting Output Codes,ECOC)是将编码的思想引入类别拆分，并且在解码过程中具有容错性的MvM技术。主要分为两步：

类别划分通过”编码矩阵(coding matrix)”指定。常见的编码矩阵有二元码和三元码，前者将每个类别分别指定为正类和反类，后者还可指定”停用类”。

测试阶段ECOC编码对分类器的错误有一定的容忍和修正能力。

3.6　类别不平衡问题

类别不平衡(class-imbalance)就是指分类任务中不同类别的训练样例数目差别很大的情况。当训练集中正、反例的数目不同时，令$m^+$表示正例数目，$m^-$表示反例数目，则观测几率是$\frac{m^+}{m^-}$，由于通常假设训练集是真实样本总体的无偏采样，因此观测几率就代表了真实几率。于是

$$若\frac{y}{1-y}>\frac{m^+}{m^-}则预测为正例.　　　　　(3.47)$$

只需令

$$\frac{y'}{1-y'}=\frac{y}{1-y}\times\frac{m^-}{m^+}.　　　　　(3.48)$$

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

再缩放有三类做法：”欠采样”(undersampling)，去除一些反例；”过采样”(oversampling)，增加一些正例；直接基于原始训练集进行学习，在用分类器进行预测时，将(3.48)嵌入决策过程，称为”阀值移动”(threshold-moving)。

“再缩放”也是”代价敏感学习”(cost-sensitive learning)的基础。