基本形式

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

写成向量形式即

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

线性回归

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

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

w和b最优解的闭式(closed-form)解为:

多元线性回归

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

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

标记向量为y,则有

并将其对w’求导得到:

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

  • 若XTX为满秩矩阵(full-rank matrix)或正定矩阵(positive definite matrix)时,则求得
    线性回归模型为
  • 若XTX不是满秩矩阵(往往不是),则会得到多个可行解,由归纳偏好选择哪一组解为输出,常见的做法为引入正则化(regularization)项

广义线性模型

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

得到广义线性模型,g称为联系函数(link function)

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

对数几率回归

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

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

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

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

确定w与b

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

上式最大化等价于最小化下式

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

线性判别分析

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

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

  • 类内散度矩阵(within-class scatter matrix)用于表示每一个类内的分散程度,希望其越小越好
  • 类间三度矩阵(between-class scatter matrix)用于表示类与类之间的分散程度,希望其越大越好

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

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

使用拉格朗日乘子可以求解其对偶问题,从而求解该优化问题,考虑到数值解的稳定性,一般会将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个分类器。在测试时若仅有一个分类器预测为正类,则对应的类别标记作为最终分类结果。若有多个分类器预测为正类,则通常考虑各分类器的预测置信度,选择置信度最大的类别标记作为分类结果。
  • 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个分类器分别对测试样本进行预测,这些预测标记组成一个编码。将这个预测编码与每个类别各自的编码进行比较,返回其中距离最小的类别作为最终预测结果

常用的编码方式

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

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

类别不平衡问题

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

  • 直接对训练集里的多的一类样例进行欠采样(undersampling),即去除一些多的一类样例,使得正、反例数目接近,然后再进行学习
  • 直接对训练集里的少的一类样例进行过采样(oversampling),即增加一些少的一类样例,使得正、反例数目接近,然后再进行学习
  • 直接基于原始训练集进行学习,但在用训练好的分类器进行预测时,将样例数量比例嵌入决策过程,称为阙值移动(threshold-moving)

注意!

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

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