Stanford大学机器学习公开课（四）：牛顿法、指数分布族、广义线性模型

（一）牛顿法解最大似然估计

牛顿方法（Newton's Method）与梯度下降（Gradient Descent）方法的功能一样，都是对解空间进行搜索的方法。其基本思想如下：

对于一个函数f(x)，如果我们要求函数值为0时的x，如图所示：

我们先随机选一个点，然后求出该点的切线，即导数，延长它使之与x轴相交，以相交时的x的值作为下一次迭代的值。

更新规则为：

那么如何将牛顿方法应用到机器学习问题求解中呢？

对于机器学习问题，我们优化的目标函数为极大似然估计L，当极大似然估计函数取得最大时，其导数为0，这样就和上面的函数f取0的问题一致了。所以将应用于上式中，得

上面是当参数θ为实数时的情况，当参数为向量时，更新规则变为如下所示：

其中，H是一个n*n的矩阵，n为参数向量的长度，亦即特征的数目，H是函数的二次导数矩阵，被称为Hessian矩阵，其某个元素Hij计算公式如下： 即为，这里有点类似于用一阶导数除以二阶导数；所以，用一个表示一阶导数的向量乘上一个表示二阶导数的矩阵的逆。

牛顿方法相对于梯度下降的优点是收敛速度快，通常十几次迭代就可以收敛。它也被称为二次收敛，因为当迭代到距离收敛值比较近的时候，每次迭代都能使误差变为原来的平方。缺点是当参数向量较大时，每次迭代都需要计算一次Hessian矩阵的逆，比较耗时。

如果目标函数求得的是最小值的，那么更新规则不会改变。如何判断得到的参数使目标函数达到极大值还是极小值呢？可以通过判断二阶导数的值来确定，当二阶导数小于0时，即为最大值；当二阶导数大于0时，即为最小值。

 

（二）指数分布族

 

指数分布族是指可以表示为指数形式的概率分布。指数分布的形式如下：
其中，η称为分布的自然参数（nature parameter）；T(y)是充分统计量（sufficient statistic），通常T(y)=y。当参数a、b、T都固定时，就定义了一个以η为参数的函数族。

实际上，大多数概率分布都可以表示成上式的形式。比如：

1）伯努利分布：对0、1问题进行建模；

2）多项式分布：多有K个离散结果的事件的建模；

3）泊松分布：对计数过程进行建模，比如网站访问量的计数问题，放射性衰变的数目，商店 顾客数量等问题；

4）伽马分布与指数分布：对有间隔的正数进行建模，比如公交车的到站时间问题；

5）β分布：对小数建模；

6）Dirichlet分布：对概率分布建模；

7）Wishart分布：协方差矩阵的分布；

8）高斯分布；

 

现在，我们将高斯分布与伯努利分布表示称为指数分布族的形式。

伯努利分布是对0,1问题进行建模的分布，它可以用如下形式表示：
将其转换形式，推导如下：

通过上式，就将伯努利分布表示成了指数分布的形式；其中：
可以看到，η的形式与之前提及的logistic函数一致，这是因为logistic模型对问题的前置概率估计是伯努利分布的缘故。

由高斯分布可以推导出线性模型，由线性模型的假设函数可知，高斯分布的方差与假设函数无关，因而为了简便计算，这里将方差设为1。所以高斯分布转换为指数分布族形式的推导过程如下：

由上式可知：
推导的关键在于将指数内部的纯y项移到外面，纯非y项作为函数a，混杂项为。

 

 

（三）广义线性模型

定义了指数分布族后有什么用呢？我们可以通过指数分布族引出广义线性模型（Generalized Linear Model,GLM）。在伯努利分布表示成指数分布族的形式的公式中，η与参数φ的关系是logistic函数，再通过推导可以得到逻辑回归（推导过程在下面）；在高斯分布表示成指数分布族的形式的公式中，η与正太分布的参数μ的关系是相等，我们可以推导出最小二乘模型（Ordinary Least Squares）。通过这两个例子，我们大致可以得到结论，η以不同的映射函数与其它概率分布函数中的参数发生联系，从而得到不同的模型，广义线性模型正式将指数分布族中的所有成员（每个成员正好有一个这样的联系）都作为线性模型的扩展，通过各种非线性的连接函数将线性函数映射到其它空间从而大大扩大了线性模型可解决的问题。

 

下面看GLM的形式化定义，GLM有三个假设：

1）y|x;θ~ExpFamily(η);给定样本x与参数θ，样本分类y服从指数分布族中的某个分布；

 

2）给定一个x，需要的目标函数为

 

3）

依据这三个假设，我们可以推导出ogistic模型与最小二乘模型。Logistic模型的推导过程如下： 上式中，第一行是伯努利分布的性质，第二行由假设二与假设三推出。
同样的，对于最小二乘模型，推导过程如下：
其中，将η与原始概率分布中的参数联系起来的函数称为正则响应函数（canonical response function），如即是正则响应函数。正则响应函数的逆称为正则关联函数（canonical link function）。

所以，对于广义线性模型，需要决策的是选用什么样的分布，当选取高斯分布时，我们就得到最小二乘模型，当选取伯努利分布时，我们得到logistic模型，这里所说的模型是假设函数h的形式。

总结一下，广义线性模型通过假设一个概率分布，得到不同的模型，而之前所讨论的梯度下降，牛顿方法都是为了求取模型中的线性部分的参数θ。

 

（四）GLM举例——多项式分布

多项式分布推导出的GLM可以解决多分类问题，是logistic模型的扩展。应用的问题比如邮件分类、预测病人患的什么病等。

多项式分布的目标值yε{1,2,3,...,k}；其概率分布为：

其中，因为，所以我们可以只保留k-1个参数，使得：

为了使多项式分布能够写成指数分布族的形式，首先定义T(y),如下所示：

这样，我们还可以引入指示函数I，使得 这样，T(y)向量中的某个元素还可以表示成： 举例来说，当y=2时，。根据上式，我们还可以得到： 于是，二项分布转变为指数分布族的推导如下：

概率分布P(y;φ)写成φ的指数连乘的形式，φ的指数为指示函数的值，所以非0即1，φi表示的是分为i类时的概率，所以φi与指数的组合表示：其结果要么为φi，要么为1；写成连乘的形式，当其中某个元素为1时，对最后的连乘结果是没有影响的。所以，多项式概率分布写成这种形式，是有它的道理的。

上式中，首先进行指数对数变换；接着将对数内的乘积变为对数外的相加；然后将‘+’号后面的部分并入‘+’号前面；最后将连加和转变为向量相乘的形式，此时T(y)表示一个(k-1)*(k-1)的向量
上式中最后一步的各个分量分别如下：

由η表达式可知：
为了表示方便，再定义： 于是，可以得到：
代入，得到：

从而，我们就得到了连接函数，有了连接函数后，就可以把多项式分布的概率表达出来，即将上式代入

得：

注意到，上式中的每个参数η都是一个可用线性向量表示出来的，因而这里的θ其实是一个二维矩阵。

于是，可以得到假设函数h如下：
那么如何根据假设函数h求得参数θ，当然还是最大似然函数的方法，最大似然函数如下：

对上式取对数，得到如下最大似然函数：
然后，将

代入上式即可得到最大似然函数的对数，依次使用梯度下降算法或者牛顿方法求得参数后，使用假设函数h对新的样例进行预测，即可完成多分类任务。这种多分类问题的解法被称为softmax regression。