[机器学习西瓜书] 第03章 线性模型 笔记
@ZYX 写于2020年08月02日
第03章 线性模型
3.1 基本形式
- 数学表达
- 变量：x
- 示例$x=(x_{1};x_{2};\cdots;x_{d})$
- 由 $d$ 个属性描述
- $x_{i}$是 $x$ 在第 $i$ 个属性上的取值
- 线性模型(linear model)试图学得一个通过属性的线性组合来进行预测的函数
$f(x)=w_{1}x_{1}+w_{2}x_{2}+\cdots+w_{d}x_{d}+b$
- 一般用向量形式写成
$f(x)=w^{T}x+b$
- $w=(w_{1};w_{2};\cdots;w_{d})$
$w$ 和 $b$ 学得之后，模型就得以确定.
- 许多非线性模型(nonlinear model)，可在线性模型的基础上，通过引入层级结构或高维映射而得
- 由于$w$ 直观表达了各属性在预测中的重要性，因此线性模型有很好的可解释性(comprehensibility)
3.2 线性回归
- “线性回归” (linear regression)试图学得一个线性模型
- 数学表达
- 变量
- 数据集$D=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots, (x_{m},y_{m})\}$
- 其中$x_{i}=(x_{i1}; x_{i2}; \cdots; x_{id}), y_{i}\in \R$
- 简化为 $D=\{(x_{i},y_{i})\}^{m}_{i=1}$
- 对离散属性
- 若属性值间存在”序” (order)关系，可通过连续化将其转化为连续值
- 若属性值间不存在序关系，假定有 $k$ 个属性值，则通常转化为 $k$ 维向量
- 属性”瓜类”的取值”西瓜” “南瓜” “黄瓜”可转化为(0，0，1) ，(0，1，0)，(1，0，0)
- 线性回归试图学得
$f(x_{i})=wx_{i}+b$，使得 $f(x_{i})\simeq y_{i}$
- 确定 $w$ 和 $b$:
- 关键在于如何衡量 $f(x)$ 与 $y$ 之间的差别
- 均方误差是回归任务中最常用的性能度量
- 均方误差有非常好的几何意义
- 它对应了欧几里得距离或简称”欧氏距离” (Euclidean distance)
- 试图让均方误差最小化
$(w^{*},b^{*})\begin{aligned} &=\arg\min_{(w,b)}\sum^{m}_{i=1}(f(x_{i})-y_{i})^{2} \\ &=\arg\min_{(w,b)}\sum^{m}_{i=1}(y_{i}-wx_{i}-b)^{2} \end{aligned}$
- 基于均方误差最小化来进行模型求解的方法称为最小二乘法 (least square method)
- 最小二乘”参数估计” (parameter estimation)
- 求解 $w$ 和 $b$ 使 $E_{(w,b)}=\sum^{m}_{i=1}(y_{i}-wx_{i}-b)^{2}$ 最小化的过程，称为线性回归模型的最小二乘参数估计(parameter estimation)
- 可将 $E_{(w,b)}$ 分到对 $w$ 和 $b$ 求导
- $\frac{\partial E_{(w,b)}}{\partial w}=2(w\sum^{m}_{i=1}x_{i}^{2}-\sum^{m}_{i=1}(y_{i}-b)x_{i})$
- $\frac{\partial E_{(w,b)}}{\partial b}=2(mb-\sum^{m}_{i=1}(y_{i}-wx_{i}))$
- 令偏导为零，可得到 $w$ 和 $b$ 最优解的闭式(closed-form)解
- $w=\frac{\sum^{m}_{i=1}y_{i}(x_{i}-\bar{x})}{\sum^{m}_{i=1}x_{i}^{2}-\frac{1}{m}(\sum^{m}_{i=1}x_{i})^{2}}$
- $b=\frac{1}{m}\sum^{m}_{i=1}(y_{i}-wx_{i})$
- 多元线性回归(multivariate linear regression)
- 更一般的情形
$f(x_{i})=w^{T}x_{i}+b$，使$f(x_{i})\simeq y_{i}$
- 数学表达
- 令向量$\hat w=(w;b)$
- 把数据集 $D$ 表示为一个 $m \times (d+1)$ 大小的矩阵 $X$
- 每行对应于一个示例
- 每行前 $d$ 个元素对应于示例的 $d$ 个属性值，最后一个元素恒置为1
$X=\begin{pmatrix}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{pmatrix}=\begin{pmatrix} x^{T}_{1}&1 \\ x^{T}_{2}&1 \\ \vdots&\vdots \\ x^{T}_{m}&1 \end{pmatrix}$
- 把标记也写成向量形式 $y=(y_{1};y_{2};\dots;y_{m})$
- 有$\hat w^{*}=\arg\min_{\hat w}(y-X\hat w)^{T}(y-X\hat w)$
- 令 $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)$
- 令上式为零可得 $\hat w$ 最优解的闭式解
- 当 $X^{T}X$ 为满秩矩阵(full-rank matrix)或正定矩阵(positive definite matrix)时，可得
$\hat w^{*}=(X^{T}X)^{-1}X^{T}y$
- $(X^{T}X)^{-1}$ 是 $(X^{T}X)$ 的逆矩阵
- 令 $\hat x_{i}=(x_{i},1)$，得
$f(\hat x_{i})=\hat x^{T}_{i}(X^{T}X)^{-1}X^{T}y$
- 然而，现实任务中 $X^{T}X$ 往往不是满秩矩阵
- 此时可解出多个 $\hat w$ ，它们都能使均方误差最小化
- 选择哪一个解作为输出，将由学习算法的归纳偏好决定
- 常见的做法是引入正则化(regularization)项
- 线性模型虽简单，却有丰富的变化
- 对数线性回归(log-linear regression)
$\ln y=w^{T}x+b$
- 它实际上是在试图让 $e^{w^{T}x+b}$ 逼近 $y$
- 形式上仍是线性回归，但实质上已是在求取非线性函数映射
- 广义线性模型(generalized linear model)
- 更一般地，考虑单调可微函数 $g(\cdot)$
- 令 $y=g^{-1}(w^{T}x+b)$
- $g(\cdot)$ 称为联系函数(link function)
3.3 对数几率回归
- 若要做的是分类任务该怎么办?
- 找一个单调可微函数将分类任务的真实标记 $y$ 与线性回归模型的预测值联系起来
- 最理想的是单位阶跃函数(unit-step function)
$y = \begin{cases}0 &\text{, } z<0 \\\\ 0.5 &\text{, } z=0 \\\\ 1 &\text{, }z>0\end{cases}$
- 对数几率函数(logistic function)
$y=\frac{1}{1+e^{-z}}$
- 能在一定程度上近似单位阶跃函数的替代函数(surrogate function)
- 是一种Sigmoid函数
- 它将 $z$ 值转化为一个接近0或1的 $y$ 值
- 并且其输出值在z=0附近变化很陡
- Sigmoid函数即形似S的函数
- 代入广义线性模型
- $y=\frac{1}{1+e^{-(w^{T}x+b)}}$
- $\ln\frac{y}{1-y}=w^{T}x+b$
- 几率(odds)
若将y视为样本z作为正例的可能性，则1-y是其反例可能性，两者的比值$\frac{y}{1-y}$，称为”几率” (odds) ，反映了m 作为正例的相对可能性.
- 对几率取对数则得到”对数几率” (log odds ，亦称logit)
$\ln\frac{y}{1-y}$
- 这种方法实际上是在用线性回归模型的预测结果去逼近真实标记的对数几率，因此，其对应的模型称为”对数几率回归” (logistic regression，亦称logit regression)
- 对率函数是任意阶可导的凸函数
- 有很好的数学性质，现有的许多数值优化算法都可直接用于求取最优解
- 如何确定 $w$ 和 $b$
- 将 $y$ 视为类后验概率估计 $p(y=1|x)$
- 则有 $\ln\frac{p(y=1|x)}{p(y=0|x)}=w^{T}x+b$
- $p(y=1|x)=\frac{e^{w^{T}x+b}}{1+e^{w^{T}x+b}}$
- $p(y=0|x)=\frac{1}{1+e^{w^{T}x+b}}$
- 可通过极大似然法(maximum likelihood method)来估计$w$ 和 $b$
- 最大化”对数似然” (loglikelihood)
$\mathcal{l}(w,b)=\sum^{m}_{i=1}\ln p(y_{i}|x_{i};w,b)$
- 令 $\beta = (w;b), \hat x=(x;1)$
则 $w^{T}x+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)$
- 则有 $p(y_{i}|x_{i};w,b)=y_{i}p_{1}(\hat x_{i};\beta)+(1-y_{i})p_{0}(\hat x;\beta)$
- 得，最大化对数似然等价于最小化
$\mathcal{l}(\beta)=\sum^{m}_{i=1}(-y_{i}\beta^{T}\hat x_{i}+\ln(1+e^{\beta^{T}\hat x_{i}}))$
- 是关于β的高阶可导连续凸函数
- 根据凸优化理论，经典的数值优化算法如梯度下降法(gradient descent method) 、牛顿法(Newton method)等都可求得其最优解
- 得$\beta^{*}=\arg\min_{\beta}\mathcal{l}(\beta)$
3.4 线性判别分析
- 线性判别分析(Linear Discriminant Analysis，简称LDA)
- 亦称”Fisher判别分析”
- 给定训练样例集，设法将样例投影到一条直线上
- 使得同类样例的投影点尽可能接近
- 异类样例的投影点尽可能远离;
- 在对新样本进行分类时
- 将其投影到同样的这条直线上
- 再根据投影点的位置来确定新样本的类别
图3.3 LDA 的二维示意图
- 数学表达
- $X_{i}, \mu_{i}, \Sigma_{i}$分别表示第 $i \in \{0,1\}$ 类示例的集合、均值向量、协方差矩阵
- 若将数据投影到直线 $w$ 上
- 两类样本的中心在直线上的投影分别为 $w^{T}\mu_{0}$ 和 $w^{T}\mu_{1}$
- 若将所有样本点都投影到直线上，则两类样本的协方差分别为 $w^{T}\Sigma_{0}w$ 和 $w^{T}\Sigma_{1}w
- 由于直线是一维空间， $w^{T}\mu_{0}$ 、 $w^{T}\mu_{1}$ 、 $w^{T}\Sigma_{0}w$ 、 $w^{T}\Sigma_{1}w$ 都是实数
- 最优化
- 欲使同类样例的投影点尽可能接近，可以让同类样例投影点的协方差尽可能小
- 即 $w^{T}\Sigma_{0}w+w^{T}\Sigma_{1}w$ 尽可能小
- 欲使异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大
- 即 $||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_{0}w+w^{T}\Sigma_{1}w} \\ &=\frac{w^{T}(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}w}{w^{T}(\Sigma_{0}+\Sigma_{1})w} \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_{0}}(x-\mu_{1})(x-\mu_{1})^{T} \end{aligned}$
- 类间散度矩阵(between-class scatter matrix)
$S_{b}=(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}$
- 广义瑞利商
- $J$ 可重写为
$J=\frac{w^{T}S_{b}w}{w^{T}S_{w}w}$
- 这就是LDA 欲最大化的目标，即 $S_{b}$ 与 $S_{w}$的”广义瑞利商” (generalized Rayleigh quotient）
- 确定 $w$
- 广义瑞利商的分子和分母都是关于 $w$ 的二次项
- 步骤
- 令 $w^{T}S_{w}w=1$
- 则广义瑞利商等价于
$\min_{w} w^{T}S_{b}w \\ \text{s.t. } w^{T}S_{w}w=1$
- 由拉格朗日乘子法，上式等价于
$S_{b}w=\lambda S_{w}w$
- 因为 $S_{b}w$ 的方向恒为 $\mu_{0}-\mu_{1}$
- 令 $S_{b}w=\lambda (\mu_{0}-\mu_{1})$
- 带入前式，得 $w=S^{-1}_{w}(\mu_{0}-\mu_{1})$
- 考虑到数值解的稳定性，在实践中通常是对 $S_{w}$ 进行奇异值分解
即 $S=U\Sigma V^{T}$
- 然后再由 $S^{-1}_{w}=V\Sigma^{-1}U^{T}$ 得到 $S^{-1}_{w}$
- LDA可从贝叶斯决策理论的角度来阐释
- 并可证明，当两类数据同先验、满足高斯分布且协方差相等时， LDA可达到最优分类.
- 可以将LDA推广到多分类任务中
- 数学表达
- $N$ 个类别，第 $i$ 类示例数为 $m_{i}$
- 全局散度矩阵
$\begin{aligned} S_{t}&=S_{b}+S_{w} \\ &=\sum^{m}_{i=1}(x_{i}-\mu)(x_{i}-\mu)^{T} \end{aligned}$
- 将类内散度矩阵 $S_{w}$ 重定义为每个类别的散度矩阵之和，即
$S_{w}=\sum^{N}_{i=1}S_{w_{i}}$
- $S_{w_{i}}=\sum_{x\in X_{i}}(x-\mu_{i})(x-\mu_{i})^{T}$
- 可得
$\begin{aligned}S_{b}&=S_{t}-S_{w} \\ &=\sum^{N}_{i=1}m_{i}(\mu_{i}-\mu)(\mu_{i}-\mu)^{T} \end{aligned}$
- 多分类LDA 可以有多种实现方法:使用 $S_{b}, S_{w}, S_{t}$ 三者中的任何两个即可
- 常见的一种实现是采用优化目标
$\max_{W}\frac{\text{tr}(W^{T}S_{b}W)}{\text{tr}(W^{T}S_{w}W)}$
- $W \in \R^{d\times (N-1)}$
- $\text{tr}(\cdot)$ 表示矩阵的迹(trace)
- 可通过如下广义特征值问题求解:
$S_{b}W=\lambda S_{w}W$
- $W$ 的闭式解则是 $S^{-1}_{w}S_{b}$ 的N 一1 个最大广义特征值所对应的特征向量组成的矩阵.
- 若将 $W$ 视为一个投影矩阵，则多分类LDA将样本投影到 $N-1$ 维空间，$N-1$ 通常小于属性数
- 可通过这个投影来减小样本点的维数，且投影过程中使用了类别信息
- 因此LDA也常被视为一种经典的监督降维技术
3.5 多分类学习
- 数学表达
- $N$ 个类别 $C_{1},C_{2},\dots,C_{N}$
- $y_{i}\in \{C_{1},C_{2},\dots,C_{N}\}$
- 我们是基于一些基本策略，利用二分类学习器来解决多分类问题
- 基本思路是”拆解法”，即将多分类任务拆为若干个二分类任务求解
- 先对问题进行拆分
- 然后为拆出的每个二分类任务训练一个分类器
- 在测试时，对这些分类器的预测结果进行集成以获得最终的多分类结果
- 关键是如何对多分类任务进行拆分，以及如何对多个分类器进行集成
- 最经典的拆分策略有三种. “一对一” (One vs. One，简称OvO) 、”一对其余” (One vs. Rest ，简称OvR)和”多对多” (Many vs. Many，简称MvM)
- OvO
- 将这 $N$ 个类别两两配对，从而产生 $N(N-1)/2$ 个二分类任务
- 在测试阶段，新样本将同时提交给所有分类器，
- 于是我们将得到 $N(N-1)/2$ 个分类结果
- 最终结果可通过投票产生
即把被预测得最多的类别作为最终分类结果
- OvR
- 每次将一个类的样例作为正例、所有其他类的样例作为反例来训练 $N$ 个分类器
- OvR只需训练 $N$ 个分类器，而OvO需训练 $N(N-1)/2$ 个分类器
- 但在训练时，OvR的每个分类器均使用全部训练样例，而OvO的每个分类器仅用到两个类的样例
- MvM
- 每次将若干个类作为正类，若干个其他类作为反类
- MvM的正、反类构造必须有特殊的设计，不能随意选取
- 最常用的MvM技术：纠错输出码(Error Correcting Output Codes，简称ECOC)
- 将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性
- 步骤
- 编码
对 $N$ 个类别做 $M$ 次划分， 每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集
- 产生 $M$ 个训练集，可训练出 $M$ 个分类器.
- 解码
$M$ 个分类器分别对测试样本进行预测，这些预测标记组成一个编码
将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果
- 类别划分通过编码矩阵(coding matrix)指定
- 为什么称为”纠错输出码”?
- 因为在测试阶段， ECOC编码对分类器的错误有一定的容忍和修正能力
- 一般来说，对同一个学习任务， ECOC编码越长，纠错能力越强
- 编码越长，意味着所需训练的分类器越多，计算、存储开销都会增大
- 对有限类别数，可能的组合数目是有限的，码长超过一定范围后就失去了意义
- 对同等长度的编码，任意两个类别之间的编码距离越远，则纠错能力越强
- 在码长较小时计算出理论最优编码
- 码长稍大一些是NP难问题
3.6 类别不平衡问题
- 前面介绍的分类学习方法都有一个共同的基本假设： 不同类别的训练样例数目相当
- 类别不平衡(class imbalance)
- 指分类任务中不同类别的训练样例数目差别很大的情况
- 假设
- 在我们用$y=w^{T}x+b$ 对新样本 $m$ 进行分类时
- 事实上是在用预测出的 $y$ 值与一个阈值进行比较
- 通常在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} \times \frac{m^{+}}{m^{-}}$
- 这就是一个基本策略一再缩放(rescaling)
- 再缩放的实际操作却并不平凡
- 因为”训练集是真实样本总体的无偏采样“这个假设往往不成立
- 现有技术大体上有三类做法:
- 对训练集里的反类样例进行”欠采样” (undersampling)
- 去除一些反例使得正、反例数目接近， 然后再进行学习
- 随机丢弃反例可能丢失一些重要信息
- 代表性算法EasyEnsemble则是利用集成学习机制，将反例划分为若干个集合供不同学习器使用
- 这样对每个学习器来看都进行了欠采样，但在全局来看却不会丢失重要信息.
- 是对训练集里的正类样例进行”过采样” (oversampling)
- 增加一些正例使得正、反例数目接近，然后再进行学习
- 不能简单地对初始正例样本进行重复采样，否则会过拟合
- 代表性算法SMOTE是通过对训练集里的正例进行插值来产生额外的正例
- 阔值移动(threshold-moving)
- 直接基于原始训练集进行学习，但在用训练好的分类器进行预测时，将$\frac{y’}{1-y’}=\frac{y}{1-y} \times \frac{m^{+}}{m^{-}}$ 嵌入到其决策过程中
- 再缩放是代价敏感学习(cost-sensitive learning)的基础
- 在代价敏感学习中将 $\frac{y’}{1-y’}=\frac{y}{1-y} \times \frac{m^{+}}{m^{-}}$ 中的 $m^{+}/m^{-}$用$cost^{+}/cost^{-}$代替
- $cost^{+}$ 将正例误分为反倒的代价
- $cost^{-}$ 将反例误分为正例的代价
⇧