基本形式

给定由d个属性描述的示例x=(x1; x2; …; xd)，其中xi是x在第i个属性上的取值，线性模型（linear model）试图学得一个通过属性的线性组合来进行预测的函数，即

image
写成向量形式即
image

• 确定w与b后模型即随之确定
• 非线性模型（nonlinear model）可在线性模型基础上通过引入层级结构或高维映射得到
• 线性模型具有很好的解释性（comprehensibility）

线性回归

线性回归（linear regression）目的即确定一个w和b，是的f(x)与y的均方误差最小化。

• 均方误差对应欧几里得距离即欧氏距离（Euclidean distance）
• 基于均方误差最小化进行模型求解的方法称最小二乘法（least square method）
• 最小二乘法即试图找到一条直线，使所有样本到直线上的欧氏距离之和最小

w和b最优解的闭式（closed-form）解为：

image

多元线性回归

更一般的情形是对于d个属性描述的变量，进行多元线性回归（multivariate linear regression）

image

为便于讨论，令w'=(w;b)，数据集D表示为一个m×(d+1)大小的矩阵X，器每一行对应一个示例，每行前d个元素对应于示例的d个属性值，最后一个元素恒置为1，即

image

标记向量为y，则有

image
令
image

并将其对w'求导得到：

image
令其为0可以得到w'的最优解的闭式解

• 若XTX为满秩矩阵（full-rank matrix）或正定矩阵（positive definite matrix）时，则求得

  
  image
  

  线性回归模型为

  
  image
• 若XTX不是满秩矩阵（往往不是），则会得到多个可行解，由归纳偏好选择哪一组解为输出，常见的做法为引入正则化（regularization）项

广义线性模型

广义线性模型（generalized linear model）即当f与x不是标准的线性关系时，可以选取一个恰当的单调可微函数g，令

image

得到广义线性模型，g称为联系函数（link function）

例如当g(·)=ln(·)时可以得到对数线性回归（log-linear regression）

image

对数几率回归

对于二分类任务，可以通过将输出标记y归到0或1，从而使用线性回归的方法，即将预测值转换成0/1值，可以使用单位阶跃函数（unit-step function）

image

但是由于其不连续，可以使用单位阶跃函数的替代函数（surrogate function）并希望其单调可微，从而可以选取对数几率函数（logistic function），一种Sigmoid函数（即形似S的函数）

image image

它可以将z值转换成一个0/1值，从而

image

将y视为样本x作为正例的可能性，则1-y是其反例可能性，两者的比值成为几率（odds），反映了x作为正例的相对可能性，对其取对数即对数几率（log odds，或logit）

确定w与b

通过极大似然法（maximum likelihood method）估计w和b，给定数据集(xi,yi)，对率回归模型最大化对数似然（log-likelihood）

image
上式最大化等价于最小化下式
image
该式是关于β的高阶可导连续凸函数，根据凸优化理论可以使用梯度下降法、牛顿法等求其最优解得到：
image

线性判别分析

线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的线性学习方法，适用于二分类问题。

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

image

• 类内散度矩阵（within-class scatter matrix）用于表示每一个类内的分散程度，希望其越小越好

  
  image

• 类间三度矩阵（between-class scatter matrix）用于表示类与类之间的分散程度，希望其越大越好

  
  image

LDA欲最大化的目标即Sb和Sw的广义瑞利商（generalized Rayleigh quotient）

image

求算方式：由于不失一般性（J式中分子和分母都是关于w的二次项，因此J的解与w的长度无关，只与其方向有关），可以设分母为1，等价于等式条件约束下的凸优化问题：

image

使用拉格朗日乘子可以求解其对偶问题，从而求解该优化问题，考虑到数值解的稳定性，一般会将Sw进行奇异值分解

• LDA可从贝叶斯决策理论的角度来阐释，并可证明，当两类数据同先验、满足高斯分布且协方差相等时，LDA可达到最优分类
• LDA可以推广到多分类任务中，需要定义全局散度矩阵
• LDA也常被视为一种经典的监督降维技术

多分类学习

多分类学习的基本思路是拆解法，即将多分类任务拆为若干个二分类任务求解。先对问题进行拆分，然后为拆出的每个二分类任务训练一个分类器；在测试时，对这些分类器的预测结果进行集成以获得最终的多分类结果。

经典的拆分策略有

• 一对一（One vs. One，OvO)
• 一对其余（One vs. Rest，OvR)
• 多对多（Many vs. Many，MvM）

一对一 与 一对其余

假设有N个类别。

• OvO将这N个类别两两配对，从而产生N(N-1)/2个二分类任务。在测试阶段，新样本将同时提交给所有分类器，于是将得到N(N-1)/2个分类结果，最终结果可通过投票产生：即把被预测得最多的类别作为最终分类结果。
• OvR每次将一个类的样例作为正例、所有其他类的样例作为反例来训练N个分类器。在测试时若仅有一个分类器预测为正类，则对应的类别标记作为最终分类结果。若有多个分类器预测为正类，则通常考虑各分类器的预测置信度,选择置信度最大的类别标记作为分类结果。

image

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

多对多

MvM是每次将若干个类作为正类，若干个其他类作为反类（OvO和OvR是MvM的特例）。MvM的正、反类构造可以使用最常用的纠错输出码（Error Correcting Output Codes，ECOC)技术。

ECOC是将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性。ECOC工作过程主要分为两步

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

常用的编码方式

• 二元码，每个类别分别指定为正类和反类
• 三元码，每个类别可以指定为正类、反类或者停用类

image

纠错输出码具有一定的容错能力

类别不平衡问题

类别不平衡（class-imbalance）指分类任务中不同类别的训练样例数目差别很大的情况。一般的应对方式是再缩放（rescaling）

• 直接对训练集里的多的一类样例进行欠采样（undersampling），即去除一些多的一类样例，使得正、反例数目接近，然后再进行学习
• 直接对训练集里的少的一类样例进行过采样（oversampling），即增加一些少的一类样例，使得正、反例数目接近，然后再进行学习

• 直接基于原始训练集进行学习，但在用训练好的分类器进行预测时，将样例数量比例嵌入决策过程，称为阙值移动（threshold-moving）

  
  image

注意！

• 欠采样法的时间开销通常远小于过采样法，因为前者丢弃了很多样例，使得分类器训练集远小于初始训练集，而过采样法增加了很多样例，其训练集大于初始训练集
• 过采样法不能简单地对初始样例进行重复采样，否则会招致严重的过拟合；过采样法的代表性算法SMOTE是通过对训练集里的一类样例进行插值来产生额外的样例
• 欠采样法若随机丢弃样例，可能丢失一些重要信息；欠采样法的代表性算法Easy Ensemble则是利用集成学习机制，将少的一类样例划分为若干个集合供不同学习器使用，这样对每个学习器来看都进行了欠采样，但在全局来看却不会丢失重要信息

全文参考：周志华 著 《机器学习》

---

转载请注明出处，本文永久更新链接：小天才的杂货铺-个人博客