最简单的一种模型，但也是很多非线性模型的基础，输入与输出之间的关系用多项式表征，有很好的可解释性
基本形式
给定由个属性描述的示例，其中是在第个属性上的取值，线性模型(linear
model)试图学得一个通过属性的线性组合来进行预测的函数，即： 一般用向量形式写成： 其中，和学得之后，模型就得以确定
许多功能更为强大的非线性模型(nonlinear
model)可在线性模型的基础上通过引入层级结构或高维映射而得
由于直观表达了各属性在预测中的重要性，故线性模型有很好的可解释性(comprehensibility)
线性回归
给定数据集，其中，线性回归(linear
regression)试图学得一个线性模型以尽可能准确地预测实值输出标记
简单情形
先讨论一种最简单的情形，输入属性的数目只有一个，即，若属性值之间存在序(order)关系，可通过连续化将其转化为连续值
线性回归试图学得： 欲确定和，关键在于如何衡量和之间的差别，由于均方误差是回归任务中最常用的性能度量，故可以试图让均方误差最小化，即：
均方误差有很好的几何意义，它对应了欧氏距离(Euclidean
distance)；基于均方误差最小化来进行模型求解的方法称为最小二乘法(least
square
method)；在线性回归中，最小二乘法就是试图找到一条直线，使得所有样本到直线上的欧氏距离之和最小
求解和使最小化的过程，称为线性回归模型的最小二乘参数估计(parameter
estimation)
将分别对和求导可得：
然后令式(5)和式(6)为零可得到和最优解的闭式(closed-form)解：
其中为的均值
一般情形
更一般的情形是形如本节开头的数据集，样本由个属性描述，此时线性回归试图学得： 这称为多元线性回归(multivariate linear
regression)
类似的，可以利用最小二乘法来对和进行估计；为了方便讨论，把和吸收入向量形式，相应的把数据集表示为一个大小的矩阵，其中每行对应一个示例，该行的前个元素对应于示例的个属性值，最后一个元素恒置为1，即：
再把标记也写成向量形式，则类似式(4)，有：
令，对求导可得： 令上式为零可得最优解的闭式解，由于涉及矩阵逆的计算，故下面做一个简单的讨论
当为满秩矩阵(full-rank
matrix)或正定矩阵(positive definite
matrix)时，零式(12)为零可得： 令，则最终学得的多元线性回归模型为： 回到现实情况，往往不是满秩矩阵，此时可解出多个，它们都能使均方误差最小化；选择哪一个解作为输出，将由学习算法的归纳偏好决定，常通过引入正则化(regularization)项来解决这一问题
线性模型虽简单，但有丰富的变化
对于样例，当我们希望线性模型的预测值逼近真实标记时，我们就得到了线性回归模型；为了便于观察，将线性回归模型简写为
当我们认为示例所对应的输出标记是在指数尺度上变化，则可以将输出标记的对数作为线性模型逼近的目标，即：
这就是对数线性回归(log-linear
regression)，它实质上是试图让逼近；式(15)形式上仍然是线性回归，但实质上已经是在求取输入空间到输出空间的非线性函数映射，如下图所示
更一般地，考虑单调可微函数，令： 这样得到的模型称为广义线性模型(generalized
linear model)，其中函数称为联系函数(link
function)；上述的对数线性回归是广义线性模型在时的特例
对数回归几率
若要做的是分类任务，只需在式(16)定义的广义线性模型中找一个单调可微函数，将分类任务的真是标记与线性回归模型的预测值联系起来
考虑二分类任务，其输出标记，而线性回归模型产生的预测值是实值，故需要将实值转换为0/1值；最理想的就是单位阶跃函数(unit-step
function)： 即若预测值大于零就判为正例，小于零则判为反例，预测值为临界值零则可任意判别，如下图所示
但单位阶跃函数并不连续，不能直接用作式(16)中的，于是希望找到一个在一定程度上近似单位阶跃函数的替代函数(surrogate
function)，并希望它单调可微，一个常用的替代函数就是对数几率函数(logistic
function)：
从上图可以看出，对数几率函数是一种Sigmoid函数，将对数几率函数作为带入式(16)中可得： 类似式(15)，可将式(19)化为： 若将视作样本为正例的可能性，则是其反例可能性，两者的比值称为几率(odds)，反映了作为正例的相对可能性，对几率取对数可得对数几率(log
odds, logit)：
由此可看出，式(19)实际上是用线性回归模型的预测结果去逼近真实标记的对数几率，故其对应的模型称为对数几率回归(logistic
regression, logit regression)
特别需注意，虽然它的名字是“回归”，但却是一种分类学习方法
欲确定式(19)中的和，将式(19)中的视为类后验概率估计，则式(20)可重写为： 显然有：
于是可通过极大似然法(maximum likelihood
method)来估计和；
给定数据集，对率回归模型最大化对数似然(log-likelihood)：
即令每个样本属于其真实标记的概率越大越好；
令，则可简写成；再令，则式(25)中的似然项可重写为：
将式(26)带入式(25)，并根据式(23)、(24)可知，最大化式(25)等价于最小化：
式(27)是关于的高阶可导连续凸函数，根据凸优化理论，经典的数值优化算法如梯度下降法(gradient
descent method)、牛顿法(Newton
method)等都可以求得其最优解，于是得到： 以牛顿法为例，其第轮迭代解的更新公式为： 其中关于的一阶、二阶导数分别为：
线性判别分析
线性判别分析(Linear Discriminant Analysis,
LDA)是一种经典的线性学习方法，亦称Fisher判别分析
二分类
LDA的思想：
- 给定训练样例集，设法将样例投影到一条直线上，使同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；
- 在对新样本进行分类时，将其投影到该直线上，根据投影点的位置来确定新样本的类别；
上图中“+”、“-”分别代表正例和反例，椭圆表示数据簇的外轮廓，虚线表示投影，红色实心圆和实心三角形分别表示两类样本投影后的中心点
给定数据集，令分别表示第类示例的集合、均值向量、协方差矩阵
- 若将数据投影到直线上，则两类样本的中心在直线上的投影分别为和；
- 若将所有样本点都投影到直线上，则两类样本的协方差分别为和；
由于直线是一维空间，因此、、和均为实数
- 欲使同类样例的投影点尽可能接近，则可以让同类样例投影点的协方差尽可能小，即尽可能小；
- 欲使一类样例的投影点尽可能远离，则可以让类中心之间的距离尽可能大，即尽可能大；
同时考虑二者，则可得到欲最大化的目标： 定义类内散度矩阵(within-class scatter
matrix)： 以及类间散度矩阵(between-class scatter
matrix)： 则式(32)可重写为： 式(35)即为LDA欲最大化的目标，即欲的广义瑞利商(generalized
Rayleigh quotient)
该式的分子分母都是关于的二次项，故式(35)的解与的长度无关，只与其方向有关；不失一般性，令，则式(35)等价于： 由拉格朗日乘子法，上式等价于： 其中是拉格朗日乘子
注意到的方向恒为，不妨令 带入式(37)得： 考虑到数值解的稳定性，在实践中通常是对进行奇异值分解，即，这里是一个实对角矩阵，其对角线上的元素是的奇异值，然后再由得到
LDA可从贝叶斯决策理论的角度来阐释，并可证明，当两类数据同先验、满足高斯分布且协方差相等时，LDA可达到最优分类
多分类
可以将LDA推广到多分类任务中；假设存在个类，且第类示例数为
定义全局散度矩阵： 其中是所有示例的均值向量
将类内散度矩阵重新定义为每个类别的散度矩阵之和，即： 其中 由式(40)~(42)可得： 显然，多分类LDA可以有多种实现方法：使用三者中的任何两个即可
常见的一种实现是采用优化目标： 其中，表示矩阵的迹；上式可通过如下广义特征值问题求解：
的闭式解则是的个最大广义特征值所对应的特征向量组成的矩阵
若将视为一个投影矩阵，则多分类LDA将样本投影到维空间，通常远小于数据原有的属性数；故可通过这个投影来减小样本点的维数，且投影过程中使用了类别信息，因此LDA也常被视为一种经典的监督降维技术
多分类学习
有些二分类学习方法可直接推广到多分类，但更多的情况是基于一些基本策略，利用二分类学习器来解决多分类问题
不失一般性，考虑个类别，多分类学习的基本思路是“拆解法”，即将多分类任务拆为若干个二分类任务求解；具体来说就是对问题进行拆分，为拆分出的每个二分类任务训练一个分类器，测试时对这些分类器预测的结果进行集成以获得最终的多分类结果
最经典的拆分策略：一对一(One vs. One,
OvO)、一对其余(One vs. Rest,
OvR)、多对多(Many vs. Many, MvM)
给定数据集
OvO与OvR
OvO将这个类别两两配对，从而产生个二分类任务；在测试阶段，新样本将同时提交给所有分类器，于是得到个分类结果，最终结果通过投票产生，即把被预测得最多的类别作为最终分类结果；
OvR则是每次将一个类的样例作为正例、所有其他类的样例作为反例来训练个分类器；在测试阶段，若仅有一个分类器预测为正类，则对应的类别标记作为最终分类结果；若有多个分类器预测为正类，则通常考虑各分类器的预测置信度，选择置信度最大的类别标记作为分类结果
MvM
MvM是每次将若干个类作为正类，若干个其他类作为反类；显然OvO和OvR是MvM的特例
MvM的正、反类构造必须有特殊的设计，不能随意选取；下面介绍一种最常用的MvM技术：纠错输出码(Error
Correcting Output, ECOC);
ECOC是将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性，工作过程主要分两步：
- 编码：对个类别做次划分，每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集；这样共产生个训练集，可训练出个分类器；
- 解码：个分类器分别对测试样本进行预测，这些预测标记组成一个编码；将该预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果；
类别划分通过编码矩阵(coding
matrix)指定；编码矩阵有多种形式，常见的有二元码和三元码
- 二元码：将每个类别分别指定为正类和反类；
- 三元码：除正、反类之外，还可指定“停用类”；
上图中“+1”，“-1”分别表示学习器将该类样本作为正、反例；三元码中“0”表示不使用该类样本
在测试阶段，ECOC编码对分类器的错误有一定的容忍和修正能力；
以上图中的(a)图为例，测试示例的正确预测编码应为，假设在预测时某分类器出错了，例如图中的，导致预测的编码为，但基于这个有错误的编码仍能产生正确的最终分类结果
一般来说，对同一个学习任务，ECOC编码越长，纠错能力越强；但编码越长意味着需要训练的分类器越多，另一方面，对有限类别数，可能的组合数是有限的，码长超过一定范围后就失去了意义
对于等长度的编码，理论上来说，任意两个类别之间的编码距离越远，则纠错能力越强
因此，在码长较小时可根据这个原则计算出理论最优编码；然而码长稍大一些就难以有效确定最优编码，这是NP难问题
不过通常我们并不需要获得理论最优编码，因为非最优编码在实践中往往已经能产生足够好的分类器
类别不平衡问题
类别不平衡(class-imbalance)是指分类任务中不同类别的训练样例数目差别很大的情况
从线性分类器的角度讨论，在用对新样本进行分类时，实际上是用预测出的值与一个阈值进行比较；
实际表达了正例的可能性，几率则反映了正例可能性与反例可能性之比，阈值设置为0.5则表明分类器认为真实正、反例可能性相同，即分类器决策规则为
但当训练集中正、反例的数目不同时，令分别表示正、反例数目，则观测几率是，由于我们通常假设训练集是真实样本的无偏采样，故观测几率就代表真实几率；于是，只要分类器的预测几率高于观测几率就判为正例，即
但分类器是基于式(46)进行决策的，故需对其预测值进行调整，令
这就是类别不平衡学习的一个基本策略——再缩放(rescaling)
由于在实际中，“训练集是真实样本总体的无偏采样”这个假设往往并不成立，也就是说，我们未必能有效地基于训练集观测几率来推断出真实几率
现有技术大体上有三类做法(假设正例少、反例多)：
- 欠采样(undersampling)：即去除一些反例，使得正、反例数目接近，然后再进行学习；
- 过采样(oversampling)：即增加一些正例，使得正、反例数目接近，然后再进行学习；
- 直接基于原始训练集学习：但在用训练好的分类器进行预测时，将式(48)嵌入其决策过程中，称为阈值移动(threshold-moving)
再缩放是代价敏感学习(cost-sensitive
learning)的基础，在代价敏感学习中将式(48)中的用代替即可，其中是将正例误分为反例的代价，是将反例误分为正例的代价
