本文介绍机器学习算法中的概率方法。概率方法会对数据的分布进行假设，对概率密度函数进行估计，并使用这个概率密度函数进行决策。本文介绍四种最常用的概率方法：线性回归(用于回归任务)、对数几率回归(用于二分类任务)、Softmax回归(用于多分类任务)和朴素贝叶斯分类器(用于多分类任务)。*前三种方法属于判别式模型，而朴素贝叶斯分类器属于生成式模型。（*严格来说，前三者兼有多种解释，既可以看做是概率方法，又可以看做是非概率方法。）
1准备知识
本节给出概率方法的基本流程，后续要介绍的不同的概率方法都遵循这一基本流程。
1.1概率方法的建模流程
(1).对p(y|x;θ)进行概率假设。我们假定p(y|x;θ)具有某种确定的概率分布形式，其形式被参数向量θ唯一地确定。
(2).对参数θ进行最大后验估计。基于训练样例对概率分布的参数θ进行最大后验估计(maximumaposteriori,MAP)，得到需要优化的损失函数。
最大后验估计是指
其在最大化时考虑如下两项：
参数的先验分布p(θ)。最大后验估计认为参数θ未知并且是一个随机变量，其本身服从一个先验分布p(θ)。这个先验分布蕴含了我们关于参数的领域知识。
基于观测数据得到的似然(likelihood)p(D|θ)。最大化似然是在θ的所有可能的取值中，找到一个能使样本属于其真实标记的概率最大的值。
最大后验估计是在考虑先验分布p(θ)时最大化基于观测数据得到的似然(likelihood)p(D|θ)。
参数估计的两个不同学派的基本观点是什么这实际上是参数估计(parameterestimation)过程，统计学中的频率主义学派(frequentist)和贝叶斯学派(Bayesian)提供了不同的解决方案[3,9]。频率主义学派认为参数虽然未知，但却是客观存在的固定值，因此通常使用极大似然估计来确定参数值。贝叶斯学派则认为参数是未观察到的随机变量，其本身也可有分布，因此，可假定参数服从一个先验分布，然后基于观察到的数据来计算参数的后验分布。
定理1.最大后验估计的结果是优化如下形式的损失函数
Proof.利用样例的独立同分布假设，
经验风险和结构风险的含义L(θ)的第一项称为经验风险(empiricalrisk)，用于描述模型与训练数据的契合程度。第二项称为结构风险(structuralrisk)或正则化项(regularizationterm)，源于模型的先验概率，表述了我们希望获得何种性质的模型(例如希望获得复杂度较小的模型)。λ称为正则化常数，对两者进行折中。
结构风险的作用(1).为引入领域知识和用户意图提供了途径。(2).有助于削减假设空间，从而降低了最小化训练误差的过拟合风险。这也可理解为一种“罚函数法”，即对不希望得到的结果施以惩罚，从而使得优化过程趋向于希望目标。p范数是常用的正则化项。
其中先验分布的参数转化为正则化常数λ。
为什么最常假设参数的先验分布是高斯分布(或最常使用正则化)这是因为高斯分布N(;Σ)是所有均值和熵存在且协方差矩阵是Σ的分布中熵最大的分布。最大熵分布是在特定约束下具有最大不确定性的分布。在没有更多信息的情况下，那些不确定的部分都是“等可能的”。在设计先验分布p(θ)时，除了我们对参数的认知(例如均值和值域)外，我们不想引入任何其余的偏见(bias)。因此最大熵先验(对应正则化)常被使用。除高斯先验外，还可以使用不提供信息的先验(uninformativeprior)，其在一定范围内均匀分布，对应的损失函数中没有结构风险这一项。
(3).对损失函数L(θ)进行梯度下降优化。
梯度下降的细节留在下一节介绍。
概率方法的优缺点各是什么优点:这种参数化的概率方法使参数估计变得相对简单。缺点:参数估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布。在现实应用中，欲做出能较好地接近潜在真实分布的假设，往往需在一定程度利用关于应用任务本身的经验知识，否则仅凭“猜测”来假设概率分布形式，很可能产生误导性的结果。我们不一定非要概率式地解释这个世界，在不考虑概率的情况下，直接找到分类边界，也被称为判别函数(discriminantfunction)，有时甚至能比判别式模型产生更好的结果。
1.2梯度下降
我们的目标是求解下列无约束的优化问题。
其中L(θ)是连续可微函数。梯度下降是一种一阶(frstorder)优化方法，是求解无约束优化问题最简单、最经典的求解方法之一。
梯度下降的基本思路梯度下降贪心地迭代式地最小化L(θ)。梯度下降希望找到一个方向(单位向量)v使得L在这个方向下降最快，并在这个方向前进α的距离
定理3.梯度下降的更新规则是公式5。重复这个过程，可收敛到局部极小点。
Proof.我们需要找到下降最快的方向v和前进的距离α。
(1).下降最快的方向v。利用泰勒展开
的一阶近似，
即下降最快的方向是损失函数的负梯度方向。
(2).前进的距离α。我们希望在开始的时候前进距离大一些以使得收敛比较快，而在接近最小值时前进距离小一些以不错过最小值点。因此，我们设前进距离为损失函数梯度的一个倍数
其中η被称为学习率(learningrate)。
向公式7代入最优的和后即得。
则称f为区间[a,b]上的凸函数(convexfunction)。当<成立时，称为严格凸函数(strictconvexfunction)。U形曲线的函数如通常是凸函数。
2线性回归
2.1建模流程
线性回归(linearregression)回归问题。其建模方法包括如下三步(参见第1.1节)。
(1).对p(y|x;θ)进行概率假设。
我们假设
被称为误差项，捕获了(a)。特征向量x中没有包含的因素.
(b).随机噪声。对不同的样本是独立同分布地从中进行采样得到的。
线性回归的假设函数是
为了书写方便，我们记
那么公式12等价于
在本文其余部分我们将沿用这一简化记号。因此，
(2).对参数θ进行最大后验估计。
定理7.假设参数θ服从高斯先验，对参数θ进行最大后验估计等价于最小化如下损失函数
其中
被称为平方损失(squareloss)。在线性回归中，平方损失就是试图找到一个超平面，使所有样本到该超平面的欧式距离(Euclideandistance)之和最小。
Proof
其中，最后一行只是为了数学计算上方便，下文推导对数几率回归和Softmax回归时的最后一步亦然。
可以容易地得到损失函数对参数的偏导数
2.2线性回归的闭式解
线性回归对应的平方损失的函数形式比较简单，可以通过求直接得到最优解。
定理8.线性回归的闭式解为
Proof.L(θ)可等价地写作
令
那么
求解
即得。
mλI，即使不可逆，+mλI仍是可逆的。
2.3其他正则化回归模型
事实上，上文介绍的线性回归模型是岭回归(ridgeregression)。根据正则化项的不同，有三种常用的线性回归模型，见表1。
基于0、1和2范数正则化的效果2范数倾向于w的分量取值尽量均衡，即非零分量个数尽量稠密。而0“范数”和1范数则倾向于w的分量尽量稀疏，即非零分量个数尽量少，优化结果得到了仅采用一部分属性的模型。也就是说，基于0“范数”和1范数正则化的学习方法是一种嵌入式(embedding)特征选择方法，其特征选择过程和学习器训练过程融为一体，两者在同一个优化过程中完成。事实上，对w施加稀疏约束最自然的是使用0“范数”。但0“范数”不连续，难以优化求解。因此常采用1范数来近似。
为什么1正则化比2正则化更易于获得稀疏解？假设，则。我们绘制出平方损失项、1范数和2范数的等值线(取值相同的点的连线)，如图1所示。LASSO的解要在平方损失项和正则化项之间折中，即出现在图中平方误差项等值线和正则化项等值线的相交处。从图中可以看出，采用1正则化时交点常出现在坐标轴上(w2=0),而采用2正则化时交点常出现在某个象限中(w1，w2均不为0)。
Figure1:1正则化(红色)比2正则化(黑色)更易于获得稀疏解。本图源于[17]。
考虑一般的带有1正则化的优化目标
若(θ)满足L-Lipschitz条件，即
优化通常使用近端梯度下降(proximalgradientdescent,PGD)[1]。PGD也是一种贪心地迭代式地最小化策略，能快速地求解基于1范数最小化的方法。
定理9.假设当前参数是，PGD的更新准则是
Proof.在附近将(θ)进行二阶泰勒展开近似
由于θ各维互不影响(不存在交叉项)，因此可以独立求解各维。
在LASSO的基础上进一步发展出考虑特征分组结构的GroupLASSO[14]、考虑特征序结构的FusedLASSO[11]等变体。由于凸性不严格，LASSO类方法可能产生多个解，该问题通过弹性网(elasticnet)得以解决[16].
2.4存在异常点数据的线性回归
一旦数据中存在异常点(outlier)，由于平方损失计算的是样本点到超平面距离的平方，远离超平面的点会对回归结果产生更大的影响，如图2所示。平方损失对应于假设噪声服从高斯分布，一种应对异常点的方法是取代高斯分布为其他更加重尾(heavytail)的分布，使其对异常点的容忍能力更强，例如使用拉普拉斯分布，如图3所示。
Figure2：存在异常点(图下方的三个点)时普通线性回归(红色)和稳健线性回归(蓝色)。本图源于[7]。
定义2(拉普拉斯分布(Laplacedistribution)Lap(,b))，又称为双边指数分布(doublesidedexponentialdistribution)，具有如下的概率密度函数
该分布均值为，方差为
定理10.假设参数服从高斯先验，
对参数θ进行最大后验估计等价于最小化如下损失函数
由于绝对值函数不光滑，不便基于梯度下降对公式33进行优化。通过分离变量技巧，可将其转化为二次规划(quadraticprogramming)问题，随后调用现有的软件包进行求解。我们在下一章形式化SVR时还会再使用这个技巧。
定理11.最小化公式33等价于如下二次规划问题，其包含d+1+2m个变量，3m个约束：
此外，为了结合高斯分布(对应平凡损失)容易优化和拉普拉斯分布(对应1损失)可以应对异常值的优点，Huber损失[5]在误差接近0时为平方损失，在误差比较大时接近1损失，如图4所示。
Huber损失处处可微，使用基于梯度的方法对Huber损失进行优化会比使用拉普拉斯分布更快。
Figure4:2损失(红色)、1损失(蓝色)和Huber损失(绿色)。本图源于[7]。
2.5广义线性模型
线性回归利用属性的线性组合进行预测。除了直接利用逼近y外，还可以使模型的预测值逼近y的衍生物。考虑单调可微函数g，令
这样得到的模型称为广义线性模型(generalizedlinearmodel)，其中函数g被称为联系函数(linkfunction)。本文介绍的线性回归、对数几率回归和Softmax回归都属于广义线性模型，如表2所示。
广义线性模型的优点(1).形式简单、易于建模。(2).很好的可解释性。直观表达了各属性在预测中的重要性。
如何利用广义线性模型解决非线性问题(1).引入层级结构。例如深度学习是对样本x进行逐层加工，将初始的低层表示转化为高层特征表示后使用线性分类器。(2).高维映射。例如核方法将x映射到一个高维空间(x)后使用线性分类器。
3对数几率回归
3.1建模流程
对数几率回归(logisticregression)应对二分类问题。其建模方法包括如下三步(参见第1.1节)。
(1).对p(y|x,θ)进行概率假设。
对二分类任务，标记，而产生的是实数值，于是，我们需要找到一个单调可微函数g将转化为。最理想的是用单位阶跃函数
当大于0时输出1，小于0时输出0。但是，单位阶跃函数不连续不可微，无法利用梯度下降方法进行优化。因此，我们希望找到一个能在一定程度上近似单位阶跃函数并单调可微的替代函数(surrogatefunction)。
Figure5:单位阶跃函数(红色)与对数几率函数(黑色)。本图源于[17]。
如图5所示，对数几率函数(sigmoidfunction)正是这样一个常用的替代函数
我们将其视为后验概率估计，即
两者可以合并写作
也就是说，y|x,θ服从伯努利分布Ber(sigm)。
定理12.假设参数θ服从高斯先验，对参数θ进行最大后验估计等价于最小化如下损失函数
称为对数几率损失(logisticloss)。
注意到
因此
3.2与广义线性模型的关系
对数几率回归的假设函数等价于，其中被称为几率(odds)，反映x作为正例的相对可能性。被称为对数几率(logodds,logit)，公式50实际上在用线性回归模型的预测结果逼近真实标记的对数几率，这是对数几率回归名称的由来。
对数几率回归的优点(1).直接对分类的可能性进行建模(假设p(y|x,θ)服从伯努利分布)，无需事先假设样本x的分布，这样避免了假设分布不准确所带来的问题。(2).不仅能预测出类别，还可以得到近似概率预测，对许多需要概率辅助决策的任务很有用。(3).对数几率的目标函数是凸函数，有很好的数学性质。
引理13.对数几率损失函数是凸函数。
Proof.在的基础上，进一步可求得是一个半正定矩阵。
3.3的对数几率回归
为了概率假设方便，我们令二分类问题的标记。有时，我们需要处理形式的分类问题。对数几率损失函数需要进行相应的改动。
定理14.假设参数θ服从高斯先验，对参数θ进行最大后验估计等价于最小化如下损失函数
4Softmax回归
4.1建模流程
Softmax回归应对多分类问题，它是对数几率回归向多分类问题的推广。其建模方法包括如下三步(参见第1.1节)。
对数几率回归假设p(y|x,θ)服从伯努利分布，Softmax回归假设p(y|x,θ)服从如下分布
假设函数可以写成矩阵的形式
定理15.假设参数θ服从高斯先验，对参数θ进行最大后验估计等价于最小化如下损失函数
称为交叉熵损失(cross-entropyloss)。
损失函数对应于类别k的参数的导数是
写成矩阵的形式是
其中的第k个元素是1，其余元素均为0。对比公式20、49和67，损失函数的梯度有相同的数学形式
区别在于假设函数的形式不同。事实上，所有的广义线性模型都有类似于公式68的更新准则。
4.2交叉熵
定义由训练集观察得到的分布，称为经验分布(empiricaldistribution)。经验分布对应于第i个样例，定义。另一方面，是由模型估计出的概率。
定理16.交叉熵损失旨在最小化经验分布和学得分布之间的交叉熵。这等价于最小化和之间的KL散度，迫使估计的分布近似目标分布。
5朴素贝叶斯分类器
朴素贝叶斯分类器(naiveBayesclassifer)也是一种概率方法，但它是一种生成式模型。在本节，我们首先回顾生成式模型，之后介绍朴素贝叶斯分类器的建模流程。
5.1生成式模型
判别式模型和生成式模型各是什么判别式模型(discriminantmodel)直接对p(y|x)进行建模，生成式模型(generativemodel)先对联合分布p(x,y)=p(x|y)p(y)进行建模，然后再得到
其中，p(y)是类先验(prior)概率，表达了样本空间中各类样本所占的比例。p(x|y)称为似然(likelihood)。p(x)是用于归一化的证据(evidence)。由于其和类标记无关，该项不影响p(y|x)的估计
如何对类先验概率和似然进行估计根据大数定律，当训练集包含充足的独立同分布样本时，p(y)可通过各类样本出现的频率来进行估计
而对似然p(x|y)，由于其涉及x所有属性的联合概率，如果基于有限训练样本直接估计联合概率，(1).在计算上将会遭遇组合爆炸问题。(2).在数据上将会遭遇样本稀疏问题，很多样本取值在训练集中根本没有出现，而“未被观测到”与“出现概率为零”通常是不同的。直接按样本出现的频率来估计会有严重的困难，属性数越多，困难越严重。
判别式模型和生成式模型的优缺点优缺点对比如表3所示。
5.2建模流程
(1).对p(x|y,θ)进行概率假设。
生成式模型的主要困难在于,类条件概率p(x|y)是所有属性的联合概率，难以从有限的训练样本直接估计而得。为避开这个障碍，朴素贝叶斯分类器采用了属性条件独立性假设：对已知类别，假设所有属性相互独立。也就是说，假设每个属性独立地对分类结果发生影响
此外，对连续属性，进一步假设
因此，朴素贝叶斯分类器的假设函数是
(2).对参数θ进行最大后验估计。参数θ包括了第c类样本在第j个属性上的高斯分布的均值和方差。
定理17.假设参数θ服从不提供信息的先验，对参数θ进行最大后验估计的结果是
Proof.代入公式76
5.3离散属性的参数估计
朴素贝叶斯分类器可以很容易地处理离散属性。可估计为
然而，若某个属性值在训练集中没有与某个类同时出现过，则根据公式82估计得到0。代入公式75得到-1。因此，无论该样本的其他属性是什么，分类结果都不会是y=c，这显然不太合理。
为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行平滑(smoothing)，常用拉普拉斯修正(Laplaciancorrection)。具体的说，令K表示训练集D中可能的类别数，nj表示第j个属性可能的取值数，则概率估计修正为
拉普拉斯修正实际上假设了属性值与类别均匀分布，这是在朴素贝叶斯学习中额外引入的关于数据的先验。在训练集变大时，修正过程所引入的先验的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值。
在现实任务中朴素贝叶斯有多种实现方式。例如，若任务对预测速度要求较高，则对给定训练集，可将朴素贝叶斯分类器涉及的所有概率估值事先计算好存储起来，这样在进行预测时只需查表即可进行判别。若任务数据更替频繁，则可采用懒惰学习方式，先不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值。若数据不断增加，则可在现有估值基础上，仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习。
定义4(增量学习(incrementallearning))。在学得模型后，再接收到训练样例时，仅需根据新样例对模型进行更新，不必重新训练整个模型，并且先前学得的有效信息不会被“冲掉”。
5.4朴素贝叶斯分类器的推广
朴素贝叶斯分类器采用了属性条件独立性假设，但在现实任务中这个假设往往很难成立。于是，人们尝试对属性条件独立性假设进行一定程度的放松，适当考虑一部分属性间的相互依赖关系，这样既不需要进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系，由此产生一类半朴素贝叶斯分类器(semi-naiveBayesclassifers)的学习方法。
能否通过考虑属性间高阶依赖进一步提升泛化性能相比ODE,kDE考虑最多k个父属性。随着依赖的属性个数k的增加，准确进行概率估计所需的训练样本数量将以指数级增加。因此，若训练数据非常充分，泛化性能有可能提升。但在有限样本条件下，则又陷入高阶联合概率的泥沼。
更进一步，贝叶斯网(Bayesiannetwork)，也称为信念网(beliefnetwork)，能表示任意属性间的依赖性。贝叶斯网是一种概率图模型，借助有向无环图刻画属性间的依赖关系。
事实上，虽然朴素贝叶斯的属性条件独立假设在现实应用中往往很难成立，但在很多情形下都能获得相当好的性能[2,8]。一种解释是对分类任务来说，只需各类别的条件概率排序正确，无须精准概率值即可导致正确分类结果[2]。另一种解释是，若属性间依赖对所有类别影响相同，或依赖关系能相互抵消，则属性条件独立性假设在降低计算开销的同时不会对性能产生负面影响[15]。朴素贝叶斯分类器在信息检索领域尤为常用[6]。
6快问快答
随机梯度下降和标准梯度下降的优缺点各是什么
参数更新速度。标准梯度下降需要遍历整个训练集才能计算出梯度，更新较慢。随机梯度下降只需要一个训练样例即可计算出梯度，更新较快。
冗余计算。当训练集样本存在冗余时，随机梯度下降能避免在相似样例上计算梯度的冗余。
梯度中的随机因素/噪声。标准梯度下降计算得到的梯度没有随机因素，一旦陷入局部极小将无法跳出。随机梯度下降计算得到的梯度有随机因素，有机会跳出局部极小继续优化。
实际应用时，常采用随机梯度下降和标准梯度下降的折中，即使用一部分样例进行小批量梯度下降。此外，相比随机梯度下降，小批量梯度下降还可以更好利用矩阵的向量化计算的优势。
梯度下降和牛顿法的优缺点各是什么
导数阶数。梯度下降只需要计算一阶导数，而牛顿法需要计算二阶导数。一阶导数提供了方向信息(下降最快的方向)，二阶导数还提供了函数的形状信息。
计算和存储开销。牛顿法在参数更新时需要计算Hessian矩阵的逆，计算和存储开销比梯度下降更高。
学习率。梯度下降对学习率很敏感，而标准的牛顿法不需要设置学习率。
收敛速度。牛顿法的收敛速度比梯度下降更快。
牛顿法不适合小批量或随机样本。
实际应用时，有许多拟牛顿法旨在以较低的计算和存储开销近似Hessian矩阵。
线性回归的损失函数及梯度推导。
答案见上文。
为什么要使用正则化，1和2正则化各自对应什么分布，各有什么作用
对数几率回归的损失函数及梯度推导。
线性分类器如何扩展为非线性分类器
判别式模型和生成式模型各是什么，各自优缺点是什么，常见算法中哪些是判别式模型，哪些是生成式模型
贝叶斯定理各项的含义
朴素贝叶斯为什么叫“朴素”贝叶斯
为了避开从有限的训练样本直接估计p(x|y)的障碍，朴素贝叶斯做出了属性条件独立假设，该假设在现实应用中往往很难成立。
References
[1]P.L.CombettesandV.R.Wajs.Signalrecoverybyproximalforward-backwardsplitting.MultiscaleModeling&Simulation,4(4):1168–1200,2005.5
[2]P.M.DomingosandM.J.Pazzani.Ontheoptimalityofthesimplebayesianclassiferunderzero-oneloss.MachineLearning,29(2-3):103–130,1997.12
[3]B.Efron.Bayesians,frequentists,andscientists.JournaloftheAmericanStatisticalAssociation,100(469):1–5,2005.1
[4]N.Friedman,D.Geiger,andM.Goldszmidt.Bayesiannetworkclassifers.MachineLearning,29(2-3):131–163,1997.12
[5]P.J.Huber.Robustestimationofalocationparameter.AnnalsofStatistics,53(1):492–518,1964.6
[6]D.D.Lewis.Naive(bayes)atforty:Theindependenceassumptionininformationretrieval.InProceedingsofthe10thEuropeanConferenceonMachineLearning(ECML),pages4–15,1998.13
[7]K.P.Murphy.MachineLearning:AProbabilisticPerspective.MITPress,2012.5,6
[8]A.Y.NgandM.I.Jordan.Ondiscriminativevs.generativeclassifers:Acomparisonoflogisticregressionandnaivebayes.InAdvancesinNeuralInformationProcessingSystems14(NIPS),pages841–848,2001.12
[9]F.J.Samaniegos.AComparisonoftheBayesianandFrequentistApproachestoEstimation.SpringerScience&BusinessMedia,2010.1
[10]R.Tibshirani.RegressionshrinkageandselectionviatheLASSO.JournaloftheRoyalStatisticalSociety.SeriesB(Methodological),pages267–288,1996.4
[11]R.Tibshirani,M.Saunders,S.Rosset,J.Zhu,andK.Knight.Sparsityandsmoothnessviathefusedlasso.JournaloftheRoyalStatisticalSociety:SeriesB(StatisticalMethodology),67(1):91–108,2005.5
[12]A.N.TikhonovandV.I.Arsenin.SolutionsofIll-posedProblems.Winston,1977.4
[13]G.I.Webb,J.R.Boughton,andZ.Wang.Notsonaivebayes:Aggregatingone-dependenceestimators.MachineLearning,58(1):5–24,2005.12
[14]M.YuanandY.Lin.Modelselectionandestimationinregressionwithgroupedvariables.JournaloftheRoyalStatisticalSociety:SeriesB(StatisticalMethodology),68(1):49–67,2006.5
[15]H.Zhang.Theoptimalityofnaivebayes.InProceedingsoftheSeventeenthInternationalFloridaArtifcialIntelligenceResearchSocietyConference(FLAIRS),pages562–567,2004.13
[16]H.ZouandT.Hastie.Regularizationandvariableselectionviatheelasticnet.JournaloftheRoyalStatisticalSociety:SeriesB(StatisticalMethodology),67(2):301–320,2005.5