线性模型

回归任务

基于均方误差最小化来进行模型求解的方法称为"最小二乘法" (least square method). 在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧氏距离之和最小.

线性模型一般形式：

数据集 \(D=\{(\mathbf{x_1},y_1),...,(\mathbf{x_m},y_m)\}\)，样本由d个属性描述，即\(\mathbf{x_i}=(x_{i1},...,x_{id})\)

线性回归试图学得一个线性模型以尽可能准确地预测实值输出标记。 即学得f使得 \(f(x_i)\approx y_i\)

$ f(x)=w_1x_1+...+w_dx_d+b=\mathbf{w^Tx}+b $

这称为多元线性回归。 可用最小二乘法对w和b进行估计，为方便讨论，把w和b合并为一个向量 \(\hat{\mathbf{w}}=(\mathbf{w},b)\) 相应地把数据集D表示为一个 \(m\times (d+1)\) 的矩阵X，每行对应于一个示例，改行前d个元素对应示例的d个属性值，最后一个元素置1：

标记写为 \(\mathbf{y}=(y_1,\dots,y_m)\)，则

\[ \hat{\mathbf{w'}}=\text{arg min}_{\mathbf{\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). \]

• 当 \(X^TX\) 为满秩矩阵或正定矩阵时，令上式为0解得

\(\hat{w'}=(X^TX)^{-1}X^Ty\),

令 \(\hat{x_i}=(x_i,1)\)，则最终线性回归模型为

\(f(\hat{x_i})=\hat{x_i}^T\hat{w'}=\hat{x_i}^T(X^TX)^{-1}X^Ty\)

• 当 \(X^TX\) 不是满秩时，比如变量数（属性数）超过样例数，X的列数大于行数（此时 \(X^TX\) 大小为列数*列数，其秩不大于行数，所以不是满秩）， 此时可解出多个 \(\hat{w}\)，它们都能使均方误差最小化。选择哪个解作为输出，由学习算法的归纳偏好决定，常见做法是引入正则化项（regularization）

• 对数线性回归：输出标记的对数为线性模型逼近的目标：\(\text{ln}y=\hat{w}x + b\)

• 广义线性模型：\(y=g^{-1}(\mathbf{w^Tx}+b)\)
  • g(·)为联系函数，单调可微。对数线性回归g(·)=ln(·)

二分类任务

对数几率回归（LR）

单位越阶函数不连续，不可作联系函数g，用对数几率函数（logistic function）近似：

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

将对数几率函数作为 \(g^{-1}\) 代入z得

\[ y=\frac{1}{1+e^{-(w^Tx+b)}} \tag{1} \]

\[ ln\frac{y}{1-y}=\mathbf{w^Tx}+b \tag{2} \]

若将y作为样本x作为正例的可能性，则1-y是其反例可能性，两者比值 \(\frac{y}{1-y}\) 称为“几率”(odds)，反映了x作为正例的相对可能性， 对几率取对数则得到对数几率（log odds或称logit）

从式（2）可以看出，式（1）实际上是在用线性回归模型的预测结果去逼近真实标记的对数几率，对应模型称为“对数几率回归”

优势：

• 无需事先假设数据分布
• 可得到“类别”的近似概率预测
• 可直接应用现有数值优化算法求解最优解

极大似然法求w,b

现要确定（1）中的w和b。若将y视为类后验概率估计 \(p(y=1|x)\) ，则（2）可写为

\[ \text{ln}\frac{p(y=1|x)}{p(y=0|x)}=\mathbf{w^Tx}+b \]

求得

\[ p(y=1|x)=\frac{e^{w^T+b}}{1+e^{w^Tx+b}} \]

\[ p(y=0|x)=\frac{1}{1+e^{w^Tx+b}} \]

有了这两个概率的估计就可以通过“极大似然法”（maximum likelihood method）来估计w,b。给点数据集 \({(x_i,y_i)}^m_{i=1}\),对率回归模型最大化“对数似然”（log-likelyhood）

\[ \mathcal{l}(w,b)=\sum_{i=1}^m\text{ln}p(y_i|x_i;w,b) \tag{3} \]

即令每个样本属于其真实标记的概率越大越好。 令 \(\beta=(w,b)\), \(\hat{x}=(x,1)\),则 $\beta^T \hat{x}=\mathbf{w^Tx}+b $.
再令 \(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）式的似然项可重写为

\[ p(y_i|x_i;w,b)=y_ip_1(\hat{x_i},\beta)+(1-y_i)p_0(\hat{x_i},\beta) \]

\[ =\frac{y_ie^{\beta^T\hat{x}_i}+1-y_i}{1+e^{\beta^T\hat{x}_i}} \]

所以（3）变为

\[ l(w,b)=\sum_{i=1}^m (\text{ln}(y_ie^{\beta^T\hat{x}_i}+1-y_i)-\text{ln}(1+e^{\beta^T\hat{x}_i})) \]

最大化该式等价于最小化下式（因为 \(y_i\) 只有0、1两种取值）

\[\displaystyle l(\beta)=\sum_{i=1}^{m}(-y_i\beta^T\hat{x}_i +\text{ln}(1+e^{\beta^T\hat{x}_i})) \tag{4} \]

（4）式是关于 \(\beta\) 的高阶可导连续凸函数，根据凸优化理论，经典的数值优化算法如梯度下降法、牛顿法等都可求得其最优解，于是得到

\[ \beta'=\text{arg min}_\beta L(\beta) \]

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

\[ \beta^{t+1}=\beta^t-(\frac{\partial^2 l(\beta)}{\partial \beta \partial \beta^T})^-1 \frac{\partial l(\beta)}{\partial \beta} \]

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

\[ \frac{\partial l(\beta)}{\partial \beta} =-\sum_{i=1}^m \hat{x}_i(y_i-p_1(\hat{x}_i,\beta)) \]

\[ \frac{\partial^2 l(\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)) \]

LR总结

对数几率回归（logistic regression）的主要建模思想：

• 引入sigmod函数，建立离散标记和线性模型的关联。sigmod函数光滑，高阶可导，高度接近离散标记
• 得到类别的概率似然估计
• 构建极大似然目标函数
• 优化求解：梯度下降、牛顿法

主要优势：

• 可以具有类别的概率估计输出,辅助决策
• 可以自然扩展到到多类任务：SoftMax函数
• LR具有唯一最优解（凸函数）

线性判别分析（LDA）

LDA：Linear Discrimination Analysis

给定训练样例集，将样例投影到一条 直线上使得同类样例的投影点尽可能接近、 异类样例的投影点尽可能远离；在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定 样本的类别.

给定数据集 \(D={(x_i,y_i)}^m_{\{i=1\}},y_i\in\{0,1\}\)，令\(X_i, \mu_i,\Sigma_i\) 分别表示第 \(i\in\{0,1\}\) 类示例的集合、均值向量、协方差矩阵。 若将数据投影到直线 \(w\) 上，则两类样本的中心在直线上的投影分别为 \(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\)

同时考虑二者：

\[ J=\frac{|w_T\mu_0-w^T\mu_1|^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} \]

• 定义“类内散度矩阵”（within-class scatter matrix）

\[ S_w=\Sigma_0+\Sigma_1 \newline=\sum_{x\in X_0}(x-\mu_0)(x-\mu_0)^T+\sum_{x\in X_1}(x-\mu_1)(x-\mu_1)^T \]

• “类间散度矩阵”（between-class scatter matrix）：

\[ S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T \]

则

\[ J=\frac{w^TS_bw}{w^TS_ww} \]

J称为\(S_b\)和\(S_w\)的广义瑞利商

令 \(w^TS_ww=1\)，则上式等价于

\[ \text{min}_w -w^TS_bw \newline \text{s.t. } w^TS_ww=1 \]

使用拉格朗日乘子法可得 \(S_bw=\lambda S_ww\)

\[ w=\lambda^{-1}S_{w}^{-1}S_bw \newline=\lambda^{-1}S_w^{-1}(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw \]

取 \(\lambda=(\mu_0-\mu_1)^Tw\)，则

\[ w=S_w^{-1}(\mu_0-\mu_1) \]

考虑到数值解的稳定性，求解时可对 \(S_w\)进行奇异值分解：\(S_w=U\Sigma V^T\)

• LDA的贝叶斯决策论解释：两类数据同先验、满足高斯分布且协方差相等时,LDA达到最优分类

LDA推广——多分类任务

LDA总结

• 主要建模思想：寻找线性超平面，使得同类样例的投影点尽可能接近，异类样例的投影点尽可能远离
• 缺点：LDA能用于分类任务，但是因为其目标函数不直接对应经验风险,性能不如直接优化经验风险的方法
• 地位：因LDA投影点有效地得到类别区分方向,保留大量类别之前的判别信息,LDA成为数据降维最主流的方法之一

多分类任务

多分类常用技巧是利用二分类学习器解决多分类问题：

• 拆分问题为多个二分类任务，每个任务都训练一个分类器

• 对每个分类器的结果进行集成获得最终结果

• 拆分策略：

  • 一对一
  • 一对其余
  • 多对多

一对一

• 拆分：N个类别两两配对，共N(N-1)/2 个二类任务，N(N-1)/2个对应学习器
• 测试：
  • 新样本提交给所有分类器产生N(N-1)/2个分类结果
  • 投票产生最终分类结果
• 特点：
  • 训练N(N-1)/2个分类器，存储开销和测试时间大
  • 训练只用两个类的样例，训练时间短

一对其余

• 拆分：
  • 某一类作为正例，其他作为反例，N个二分类任务
  • 各个二分类任务学习分类器
• 测试：
  • 新样本提交给所有分类器预测得到N个结果
  • 比较各分类器预测置信度，置信度最大的类别作为最终类别
• 特点：
  • 训练N个分类器，存储开销和测试时间短
  • 训练用到全部训练样例，训练时间长

多对多

若干类作为正类，若干类作为反类

纠错输出码：

上图中\(f_i\)为分类器，\(C_j\) 为某个类，在M次划分下的编码（依据被化为正类还是反类取-1或1），海明距离表示两个编码之间不同位的个数。在图（a）中，该测试样例被分为了C3类。

• ECOC编码对分类器错误有容忍和修正能力,编码越长、纠错能力越强
• 对同等长度的编码,理论上来说,任意两个类别之间的编码距离越远,则纠错能力越强

类别不平衡问题

类别平衡时（正类预测阈值为0.5），当 \(y/(1-y) >1\) 时将样例预测为正例（y为样例是正例可能性）

不同类别训练样例数相差很大，用 \(m^+\) 表示正例数目， \(m^-\) 表示反例数目，观测为正例几率为 \(m^+/m^-\)， 假设训练集是真实样本总体的无偏采样,因此观测几率就代表了真实几率 此时若预测几率高于观测几率，即 \(y/(1-y) > m^+/m^-\)，则预测为正例，等价于

\[ \frac{y'}{1-y'} = \frac{y}{1-y}\times \frac{m^-}{m^+} \]

解决方法——再缩放（正类为小类）：

• 欠采样：去除反例
• 过采样：增加正例
• 阈值移动

Comments