分类问题的⽬标是将输⼊变量分到个离散的类别中的某⼀类，通常类别之间是互不相交的，也就会将输入空间划分为不同的决策区域，区域的边界通常称为决策边界，或决策面。
现在我们先探讨分类的线性模型：指决策⾯是输⼊向量的线性函数，因此被定义为维输⼊空间中的维超平⾯。如果数据集可以被线性决策⾯精确地分类，那么我们说这个数据集是线性可分的。
对于回归问题来说，⽬标向量就是⼀个实数向量，它的值是我们想要预测的。在分类问题中，使⽤⽬标值的⽅式来表⽰类别标签有许多不同的⽅式。根据类别的多少，可分为二分类问题和多分类问题，前者常用0/1二元表示法，后者常用”1-of-K”的方式来表示目标向量。
为了实现分类，一个“简单”的思路就是借助之前介绍的线性回归模型，将输出进行一个二次映射，使其能输出离散的分类变量

其中被称为激活函数，通常是非线性函数。而决策面对应于，其中为常数，由于输入与输出是一一映射的，此时必然有，为常数，所以决策面是输入变量的线性函数。但模型本身由于激活函数的非线性变换作用，不再是参数的线性模型了，仅称为推广的线性模型。

1 判别函数

判别函数是⼀个以向量为输⼊，把它分配到个类别中的某⼀个类别（记作）的函数。我们先集中讨论线性判别函数——决策⾯是超平⾯的判别函数。

1.1 判别目标

1.1.1 二分类

线性判别函数的最简单的形式是

称为权向量。由于决策平面是输入变量的常数，为了方便，我们将决策面记为，其中偏置称为阈值，因为如果输入项则输入被分类到中，否则为类。
显然对于使用线性判别函数的二分类问题而言，就是要找一个唯一的超平面，将的输入空间一分为二，接下来我们就探讨线性判别函数中各个参数对决策面的影响。

• 权重参数

考虑决策面上任意两个不同的点和，由于决策面为常数，所以有

所以与决策面内任何向量都正交，因此是垂直于决策超平面的法向量。如果位于决策面的区域，那么我们知道对于从指向的向量与参数向量的内积满足
因此法向量总是指向的区域的。

• 偏置参数

对于决策平面内任意一点，我们知道对应向量的模即为该点到原点的距离，而该向量在法向量方向上的投影即为原点到决策平面的垂直距离。令为与的夹角，由于，得

因此可以说：确定决策面的方向，确定决策面的位置。

另外，对于空间中任意的输入点，线性判别函数所表示的物理意义？考虑在决策面上的投影点，我们有

其中r表示点到决策面的垂直距离，等式两侧同乘，由于决策面上的点满足，可知

这说明二分类的判别函数的值给出了点到决策⾯的垂直距离r的⼀个有符号的度量！给定判别函数时即决策面随之确定为某个超平面，此时为常数，故而越大则该点距离决策面的垂直距离r也越大。

1.1.2 多分类

将线性判别函数推广到个类别中，即为多分类问题。容易想到的一种方法是设置多个二分类器，比如：

• 个二分类器：每个分类器的目标是区分一个输入是否属于类，称为“1对其他”（one-vs-the-rest）分类器；
• 个二分类器：对类别进行两两判别，称为“1对1”（one-vs-one）分类器。K个类别中任取两个类别进行二分类，每个类别都需要和其余的个类别进行二分类，所以共需要个分类器，最后根据所有分类器的“总投票得分”选取最高的一个类；

对于严格进行0/1输出的简单的线性二分类器，这两种方案都存在大量的“平局”情况，会产生如下图所示的无法分类区域

从另一个角度看线性判别函数，不考虑阈值，而将看作“打分函数”，其输出变量则为“得分”。我们可以通过引入K个这样的打分函数
每个给出当前输入属于类别的可能性得分，这样就能通过取得分最高的对应的类别来对当前输入进行分类了。这种情况下任意两个类别和间的决策面为
这种方法能够避开无法按分类区域的原因是因为其决策面有良好的几何性质——单连通、凸多面体。

1.2 线性判别函数参数学习方法

接下来主要介绍三种学习线性判别函数的参数的⽅法，主要区别在于参数估计时的“目标”不同。需要注意的是至今我们都仅使用了线性判别函数，未对其输出进行非线性的激活函数映射，因此这里讨论的都仅仅是关于线性判别函数的参数估计方法。

1.2.1 最小平方方法

从线性回归模型“借鉴”最小化平方误差函数作为目标。直接考虑一个一般的K分类问题，其中目标向量使用“1-of-K”的二元表示方式。每个类别都对应一个线性模型，我们令，，均为D+1维的向量，使用矩阵对K个模型进行整体表示

最终的分类结果对应输出的K维向量中最大的类别。考虑一个大小为N的训练集，接下来我们进行平方和误差的表示。令输入矩阵和目标值矩阵，平方和误差函数可写成
同样，最大似然估计等价于最小化该误差函数，令，可得解析解

最⼩平⽅⽅法对于判别函数的参数给出了精确的解析解。但是它仍然有很严重的问题，如图所示，问题主要表现在两个方面：

• 对于离群点缺少鲁棒性；
• 决策面的选择较差；

实际原因是：最⼩平⽅⽅法对应于⾼斯条件分布假设下的最⼤似然法，⽽⼆值⽬标向量的概率分布显然不是⾼斯分布。

1.2.2 Fisher线性判别函数

之前我们也曾提到过分类问题的关键在于找到决策面，正确划分决策空间。

最⼩平⽅⽅法中确定线性判别函数的⽬标是使模型的预测尽可能地与⽬标值接近，但这对于分类问题来说可能发生“过度反应”，因为对于分类问题我们追求的是所有点都能被划分到正确的类别空间中，而不是数据集的“平均预测距离误差”最小，所以说这可能更多是一个不恰当的目标。
Fisher判别准则就是一种更适合分类问题的“决策面挑选标准”，其⽬标是最大化输出空间的类别间区分度。

a. 二分类Fisher判别函数

一个思路是找到类别空间的中心点（代表点）——，将这两个点的距离最大化。之前的二分类线性判别函数里提到过线性判别函数输出值的一个物理意义为：“输入点到决策⾯的垂直距离的⼀个有符号的度量”，而越大则距离决策面的垂直距离越大，由于是有符号距离，对于不同类别的点而言会分列决策面两边，越大则两点距离决策面垂直距离越远，此时的值也随之增大。
另一种角度是从映射（投影）来看待线性判别函数，将D维的输入映射为1维的输出，由于决策面上的点满足，因此映射后均为原点，而对于非决策面上的点，由于是该点到决策面的有符号度量，如下图所示，距离决策面越远对应映射后的距离也越远。

对于如何选择这个类别中心，一种最为简单的⽅式就是类别均值投影——Fisher判别函数的思路就是利用样本之间的均值向量代表类别的“中心点”：

我们的判别函数要使得下式取得最大值

但是通过增⼤，这个表达式可以任意⼤。为解决这个问题可将限制为单位长度，即，再使⽤拉格朗⽇乘数法来进⾏有约束的最优化求解。

这个⽅法还有⼀个问题，如图所⽰。这幅图中的两个类别在原始⼆维空间中可以完美地被分开，但是当投影到连接它们的均值的直线上时，就有了⼀定程度的重叠。如果类概率分布的协⽅差矩阵与对⾓化矩阵差距较⼤，这种问题就会出现 TODO。
Fisher准则根据类间方差与类内方差的比值来定义模型参数的学习目标。首先定义类内方差，对于属于某个类别内部的方差，有

对于二分类问题，整个数据集总的类内方差定义为，因此类间方差与类内方差的比值为

为了显式表达这个比值与模型参数的关系，可进行如下表示

其中为类间协方差矩阵，为类内协方差矩阵，得

对上式关于模型参数求导，可得其取得最大值的条件

这个结果就被定义为Fisher线性判别函数了，虽然严格来说并非一个判别函数，而是数据向一维投影的方向上的选择方式，但是通过使用投影将输入空间中的数据点映射都一维过程中，不同类别的点被“分离”开了，因此在一维空间中根据类间的分离位置设定一个阈值，用于分类。

b. 多分类Fisher判别函数

同样可以扩展到一般的多分类问题中。

1.2.3 感知器算法

不同于前面的线性判别，感知器算法属于推广的线性判别模型，引入不连续的非线性激活函数，其形式为
模型输出的+1与-1可直接对应二分类问题中的正负两个类别。引入非线性激活函数后，为了便于模型参数的求解？，感知器算法中使用了额外的误差函数，当前的非线性激活函数相当于是线性基函数模型的符号函数sign，当模型输出与实际目标值不一致时有，考虑预测结果中误分类的样本集的求和作为误差函数

可以理解为对于输入空间中各个区域，如果某样本位于正确分类的区域，那么其对于误差函数的贡献为0，如果当前的样本属于错误分类区域，之前提到过点到线性模型决策⾯的垂直距离为，所以样本点距离当前决策面距离越远，则其分类错误时对于误差函数中的贡献也越大。关于是分段线性的，使用随机梯度下降算法代替梯度解析解，的更新公式为

其中为学习率，t表示更新的轮数（每轮中依次使用误分类集合中的每个样本进行参数的梯度更新）。如果将参数的学习速率设为1，有，也就是参数的更新为方式为：对于二分类中被错误分类的正样本，我们把向量样本输入向量加到当前对于权向量的估计值上，⽽对于负样本，我们从 中减去向量。过程如下图所示

直观上来说，参数向量作为法向量时与区域内的样本点的内积为负（夹角小于90°），反之在对应区域内的点则夹角大于90°。使用错分的正样本（）按参数更新公式进行更新时，即是对与求和，也就是对进行旋转，使得更新后的与二者的夹角变小。错分的负样本的更新过程同理。

感知器收敛定理表明，如果训练数据线性可分，那么感知器算法可以保证在有限步骤内找到⼀个精确解。但即使数据集是线性可分的，也可能有多个解，并且最终哪个解会被找到依赖于参数的初始化以及数据点出现的顺序。而对于线性不可分的数据集，感知器算法永远不会收敛。
实际应用中数据在给定的基函数下经常是线性不可分的，或者收敛步骤过大，需要设定步骤的上限或是误差的下限，方便得到一个可用的近似解。
TODO

2 概率生成式模型

之前提到过：判别式模型对后验概率分布建模，特点是可直接用于样本分类预测。而生成式模型的特点是对联合概率分布建模，或者等价地对类条件概率密度与类先验进行建模，再通过贝叶斯定理来计算后验概率密度。

2.1 分类问题中的sigmoid函数

2.1.1 二分类问题

使用类条件概率密度和类先验表示后验概率分布时有

其中

形似的函数称为logistic sigmoid函数，定义为

其函数图像如下，“sigmoid”的意思是“S形”。这种函数有时被称为“挤压函数”，因为它把整个实数轴映射到了⼀个有限的区间中，这个函数在许多分类算法中都有着重要的作⽤。

2.1.2 多分类的情况

sigmoid函数对于多分类的推广如下

其中。这被称为归一化指数或者softmax函数，因为它表示“max”函数的⼀个平滑版本。

2.1.3 sigmoid函数特性

a. 对称性

b. 反函数的概率性

上式为logistic sigmoid函数的反函数，称为logit函数，也称为log odds，因为一个事件发生的几率（odds）是指该事件发生的概率p与不发生的概率1-p的比值。注意到其分子分母之和为1，所以sigmoid的输出进行概率化解释是很方便的。

c. 单调性

**

2.2 连续输入

2.2.1 分类模型中的sigmoid函数

同样以高斯噪声为背景，假定类条件概率密度呈高斯分布，并假定所有类别下的协方差矩阵相同，有

其中

我们发现高斯类条件分类假设下，后验概率可明确表示为“输入的线性函数 + sigmoid激活函数”的形式，由于sigmoid函数关于输入是单调增的，因此后验概率为常数的分类阈值，对应在输入空间时的决策面也是线性的，而先验概率函数仅出现在偏置参数中，而偏置参数影响的是决策面到输入空间原点的距离，先验概率分布的改变将使得最终的决策超平面产生“平移”。下图给出了二维输入空间下的效果示例。

对于多分类的情况也有类似的情况。最终的分类结果可使用最⼩错误分类率时的决策方式，选择后验概率最大的类别进行输出。而决策面对应了后验概率最⼤的两个类别在概率相等时输入空间的位置。因此通过向一般的简单的线性模型加入sigmoid激活函数，我们期望线性模型的输出，这样我们就能得到一个可以概率化解释的推广的线性模型。这种模型有着不错的“解释性”，因为我们可以将模型的输出解释为，也就是之前提过的log odd形式——表示事件发生/不发生的概率比值。
如果我们不假设各个类别的协⽅差矩阵相同，允许每个类条件概率密度有⾃⼰的协⽅差矩阵，那么后验概率式中的⼆次项不会被消去，从⽽引出了⼆次判别函数。下图给出了线性决策边界和⼆次决策边界的一个示例。

*2.2.2 高斯输入下的最大似然解

2.3 离散输入

对于离散输入的情况，我们以二元特征为例，假设输入是D维的，则离散概率分布共包含种可能取值，一般情况下只能用类似表格的形式一一表示。若我们假设其服从朴素贝叶斯假设——特征之间相互独立，那么就可以使用伯努利分布的连乘形式对类条件概率分布进行简洁表达

代入多分类下后验概率的softmax函数表达式，其中

和之前类似，仍然是输入变量的线性函数，因此在离散输入的朴素贝叶斯假设下，后验类概率密度仍可表示为线性函数模型中加入logistic sigmoid/softmax激活函数变换的形式。

2.4 指数族分布

正如我们已经看到的，⽆论是服从⾼斯分布的输⼊，还是离散的输⼊，后验类概率密度都是由⼀般的线性模型和logistic sigmoid（K=2个类别）或者softmax（K≥2个类别）激活函数给出。通过假定类条件概率密度是指数族分布的成员，可以看到上述结果都是更⼀般的结果的特例。

3 概率判别式模型

在概率生成式模型中，为了求后验类概率，需要确定类条件概率密度的具体选择，先使⽤最⼤似然⽅法估计的参数以及类先验概率，然后使⽤贝叶斯定理就可以求出后验类概率了。但这类方法需要预先对类条件概率密度进行假设，才能得到似然函数的具体形式，进而利用MLE求解。
另⼀种⽅法是显示地使⽤⼀般的线性模型的函数形式，然后使⽤最⼤似然法直接确定它的参数，这种⽅法属于判别式训练的⼀种形式。判别式⽅法的主要优点是需要确定的可调节参数通常更少，并且不需要对类条件概率密度进行假设，就能得到不错的模型表现。

3.1 固定基函数的使用

⽬前为⽌，我们已经考虑了直接对输⼊向量进⾏分类的分类模型。但如果我们⾸先使⽤⼀个基函数向量 对输⼊变量进⾏⼀个固定的⾮线性变换，以上这些算法仍然适⽤，区别在于最终的决策边界在特征空间φ中是线性的，可能在的原始输入空间对应非线性的决策边界。如图下图所示，在特征空间线性可分的类别未必在原始的观测空间中线性可分。

对于许多实际问题来说，类条件概率密度之间有着相当⼤的重叠，也就是说对于某些，可能有在多个类别下都存在不为0的后验概率，比如下图的绿框部分。

在这种情况下，获取最优解还需要使⽤到之前讨论过的决策论。需要注意的是，⾮线性变换并不保证能消除这些重叠。而且有些变换会增加重叠的程度，或者在原始观测空间中不存在重叠的地⽅产⽣出新的重叠，但恰当地进行⾮线性变换确实能让后验概率的建模过程更简单。

3.2 Logistic回归（二分类）

之前讨论过，在⼀般的假设条件下，对于二分类问题，类别的后验概率可以写成作⽤在输入向量的线性函数上的logistic sigmoid函数形式，这里我们将输入替换为特征向量，同样也有

且，这个模型被称为logistic回归（注意这是一个分类模型）。
对于⼀个M维特征空间，使用logistic回归模型时共有M个可调节参数。如果我们使⽤之前提到的基于⾼斯类条件概率密度假设的最⼤似然⽅法，那么我们需要2M个参数来描述均值，以及个参数来描述共享的协⽅差矩阵，再算上类先验，参数总数共，这随着M的增长⽽呈⼆次⽅增长，因此对于⼤的特征维度值，直接使⽤logistic回归模型有着很明显的优势。

3.2.1 logisitic回归的MLE

首先给出logisitic sigmoid函数的导数，其可用sigmoid函数形式进行表示

以二分类问题为例，对一个大小为N的数据集，，似然函数为

通过取负对数似然定义一个误差函数，称为交叉熵（cross-entropy）误差函数，如下

其中，关于模型参数求导得

不难发现这与线性回归问题中使用平方和误差函数后的梯度函数形式是一致的。这个式子可理解为数据点n对梯度的贡献为⽬标值和模型预测值之间的“误差”与基函数向量的乘积。（损失函数）

但此时我们无法求得解析解，而需要使用梯度下降或类似的方法（如后边介绍的拟牛顿法）会更为方便

需要引起注意的是，最⼤似然⽅法对于线性可分的数据集会产⽣严重的过拟合现象。这是由于最⼤似然解出现在超平⾯对应于的情况，它等价于。最⼤似然解把数据集分成了两类，并且的⼤⼩可趋向于⽆穷⼤。这种情况下logistic sigmoid函数在特征空间中会非常陡峭，接近于⼀个阶跃函数， 从概率上看，这使得每⼀个来⾃类别的训练数据后验概率无限逼近1，即。并且最⼤似然⽅法⽆法区分某个解优于另⼀个解，在实际应⽤中哪个解被找到将会依赖于优化算法的选择和参数的初始化，即使相比于模型的参数，数据点的数量很多，只要数据是线性可分的这个问题就可能出现。但也可以通过引⼊先验概率，然后使用最大后验估计MAP求解，或者等价地给误差函数增加⼀个正则化项，以避免这种奇异性。TODO

3.3 迭代重加权最小平方

对于logistic回归来说，由于其似然函数，或者交叉熵误差函数不再有解析解了，因此我们需要另寻迭代⽅法求出最⼩值或其近似。多数方程不存在求根公式，因此求精确根非常困难，甚至不可解，从而寻找方程的近似根就显得特别重要。
常见的迭代方法使用函数的泰勒级数前面几项来寻找方程的根，牛顿迭代法（或称Newton-Raphson迭代）是求方程根的重要方法之一，其最大优点是在方程的单根附近具有平方收敛。该方法使⽤了对数似然函数的局部⼆次近似，其权值的更新形式如下

其中是一个Hessian矩阵，其矩阵元素由的二阶导数构成（详见）。

3.3.1 牛顿法应用于线性回归

我们先以线性回归问题为例，探讨牛顿法的高效性。由于线性回归模型的解就是最小化平方和误差函数的解，我们对其梯度使用Newton-Raphson迭代法

代入权值更新式得到

这与最小二乘法的解完全一致，这是因为为常量矩阵且正定（函数的Hessian矩阵正定则说明当前为凸函数，可以找到全局最小值点），并且误差函数是二次的，对于二次函数，泰勒展开的二阶展开式可以“完美近似”，没有高于二阶的偏导项，因此牛顿法只用一步就给出了精确解！

如果Hessian矩阵半正定就表示存在支撑超平面，从而函数是凸的；反过来如果函数是凸的，Hessian阵一定半正定，反证：假设Hessian矩阵不是半正定的，则存在负特征值和相应的特征向量，沿该特征向量移动一小段距离就会走到当前位置的切平面以下。详细证明可参考

3.3.2 牛顿法应用于logistic回归

我们将类似的求解步骤引入logistic回归中

是N×N的对角矩阵，其第n行的对角元素。此时Hessian矩阵不再为常量，但由于为对称矩阵，且其二次型，故是正定矩阵，误差函数是关于的凸函数，有唯一的最小值，通过参数迭代更新可逼近该极值点

我们看到更新公式的形式为⼀组加权的最⼩平⽅问题的法⽅程解，权重来自对角矩阵，且依赖于参数向量 ，因此我们必须迭代使用法⽅程，每次使⽤新的权向量计算⼀个修正的权矩阵。因此这个算法被称为迭代重加权最⼩平⽅（IRLS）。与加权的最⼩平⽅问题⼀样， 对角矩阵可以看成⽅差。

3.4 多分类Logistic回归

同样，我们将Logistic回归推广到的多分类问题中，我们知道多分类问题中后验概率由特征变量的线性组合再加入softmax变换给出，即

这里的即为第k类对应的线性模型的输出。为了使用最大似然直接确定各个模型的参数，我们需要写出似然函数，使用“1-of-K”进行输出表达较为容易，即目标向量是一个二元向量，当该目标向量指向多分类中的第k类时，则其第k个元素为1，剩余元素为0，后边也会看到这样表示得到的似然函数易于求解。可得似然函数

因此负对数似然函数为

这被称为多分类交叉熵误差函数。其中，那么误差函数关于多分类logistic模型中K个权值参数中任意一个的梯度为

这里，我们再一次看到了这种形式的梯度函数——误差与基函数的乘积，与线性回归模型的平方和误差函数以及二分类的logistic回归模型的误差函数中一样。这种简洁形式的梯度在进行数值计算的时候是十分方便的，且不用考虑数值溢出的问题。同样可使用Newton-Raphson迭代构成对应的IRLS算法。

*3.5 Probit回归

我们已经看到，对于由指数族分布描述的⼀⼤类的类条件概率分布，最终求出的后验类概率为作⽤在特征变量的线性函数上的logistic（或者softmax）变换，其中的线性函数部分依赖于指数族分布自身的性质。
然⽽并非所有的类条件概率密度都有这样简单的后验概率函数形式，假设类条件概率分布未知且无法由指数族分布进行描述，我们希望仍能找到合适的判别式概率模型。以二分类问题为前提，对于一般的（推广）线性模型，我们表示为
其中，且为激活函数。对于每个输入，先计算出线性模型的输出，然后使用如下的函数进行“非线性激活”映射，得到目标的预测值

也就是噪声阈值模型，一旦我们对阈值的概率密度进行了假设，那么对应的激活函数就能由累积分布函数给出

若我们假设是零均值、单位方差的高斯概率密度函数，对应的累积分布为

这被称为逆probit函数（这里probit的含义是自变量对累积标准正态分布函数的逆作用？），如下图所示，其累积分布函数也为sigmoid形

我们仍然可以使⽤最⼤似然法来确定模型的参数，使⽤probit回归得到的结果倾向于与logistic回归得到的结果类似。
在实际应⽤中经常出现的⼀个问题是离群点，它可能由输⼊向量的测量误差产⽣，或者由⽬标值的错误标记产⽣。由于这些点可以位于错误的⼀侧中距离理想决策边界相当远的位置上，因此他们会严重地⼲扰分类器。注意，在这⼀点上，logistic回归模型与probit回归模型的表现不同， 因为对于，logistic sigmoid函数的渐进衰减接近于，⽽probit激活函数的衰减接近于，因此probit模型对于离群点会更加敏感。

*3.6 标准链接函数

如果假设⽬标变量的条件分布来⾃于指数族分布，对应的激活函数选为标准链接函数是⼀个普遍情况。

*4 拉普拉斯近似 & 贝叶斯Logistic回归