StanFord 机器学习公开课笔记(3):牛顿方法和广义线性模

2019-11-02 本文已影响0人 v1gor

本讲视频及讲义链接

牛顿方法

牛顿方法是一种比梯度下降更快的找到极值的算法。

过程及原理

在前一章的讲解中已经知道了拟合的本质是在给定x和 $\theta$ 的条件下出现y的概率的极大似然估计，最终通过对极大似然函数的对数使用梯度上升法来迭代求出极大值（可能是最大值）。

那么现在我们换种思路来求极大似然函数的局部最大值，我们知道极值点的导数（如果存在）都为0，因此我们只需要求出使得 $l'(\theta) = 0$ 的 $\theta$ 即可。

而牛顿方法是用来求一个函数的零点的方法，所谓牛顿方法就是通过某些步骤求出 $l'(\theta)$ 的零点，从而得到 $\theta$ 的过程：

某个函数 $f(x)$ 的图像如下：
{% asset_img markdown-img-paste-20180214170331655.png %}

由图可知 $f'(x_1) = \frac{f(x_1)}{\Delta} \rightarrow \Delta = \frac{f(x_1)}{f'(x_1)}$ ，因此 $x_2 = x_1 - \Delta = x_1 -\frac{f(x_1)}{f'(x_1)}$ y以此类推可以得到一个递推公式：

$x_{t+1} = x_t - \Delta = x_t -\frac{f(x_t)}{f'(x_t)}$

按这个公式进行迭代，最终能够得到这个函数 $f(x)$ 的零点。

上面就是牛顿法求函数零点的方法，现在我们用它来寻找 $l’(\theta)$ 的零点：

$\theta_{t+1} = \theta_t - \frac{l'(\theta)}{l''(\theta)}$

函数导数的零点就是函数的可能极值点。

牛顿法迭代的特点

初始值影响不大(一般初始化为全零即可)

这是Andrew的原话，但是我觉得如果函数导数有多个零点，则初始点的选取是能够直接影响得到的结果的，不知道老师为什么要这么说。
收敛速度快。这个方法的收敛速度是“二次收敛”，即每次迭代结果和最终结果之间的误差指数级减小。
这个方法不是对所有函数都适用，适用的函数有复杂的限制，这里不讲。
当参数 $\theta$ 是高维的情况下：

$\theta^{(t+1)} = \theta^{t} - H^{-1}\nabla_\theta l$

其中H是Hessian矩阵： $H_{ij} = \frac{\partial ^{2}l}{\partial \theta_{i}\partial\theta_{j}}$

牛顿方法相比于梯度上升发的缺点是每次迭代都需要计算Hessian矩阵的逆矩阵，这是一个 $n+1$ 维的矩阵，因此一般只在特征较少时(十几个)使用牛顿法。

广义线性模型(Global Linear Model)

之前的课程中了解了两类模型:

线性回归：

$y \in R^n$ 且符合高斯分布（正态分布）<- 线性函数
logistic回归：

$y \in R^n$ 且符合伯努利分布（0-1分布）<- sigmod函数（或logistic函数）： $y = \frac{1}{1+e^{-x}}$

上一份笔记的末尾留了一个问题：为什么选择logistic函数来建模伯努利分布呢？为什么线性回归和logistic回归使用的函数不同，迭代过程却十分相似呢？

这是因为它们两个都是指数分布族的特殊情况。

指数分布族（Exponential Family）

$\begin{align} P(y;&\eta) = b(y)exp(\eta^TT(y)-a(\eta))\\ & \eta \rightarrow natural \; paramater\\ & T(y) \rightarrow sufficient\;statistic\;value \end{align}$
一般 $T(y) = y$ 。

伯努利分布还原为指数分布族形式

$\begin{align} B(\phi) & =\phi^y(1-\phi)^{(1-y)}\\ & = exp(ln(\phi^y(1-\phi)^{(1-y)}))\\ & = exp(yln\phi + (1-y)ln(1-\phi))\\ & = exp(ln\frac{\phi}{1-\phi}y+ln(1-\phi)) \end{align}$

从上面的结果可以看出，伯努利分布是指数分布族在

$\begin{align} & \eta = ln\frac{\phi}{1-\phi}\\ & a(\eta) = -log(1-\phi)\\ & b(y) = 1\\ & T(y) = y \end{align}$

时的特殊情况。可以将 $\phi$ 用 $\eta$ 表示出来再代入 $a(\eta)$ 的表达式，这样就可以得到变量统一的 $a(\eta)$ ：
$\begin{align} & \eta = ln(\frac{\phi}{1-\phi}) \rightarrow \phi = \frac{1}{1+e^{-\eta}}\\ & a(\eta) = -log(1-\phi) \rightarrow a(\eta) = log(1+e^{\eta})\\ \end{align}$

高斯分布还原为为指数分布族形式

高斯分布： $N(\mu,\sigma^2)$ .

因为在之前高斯分布的参数拟合（梯度下降迭代）过程中，我们发现参数 $\sigma$ 的值并不影响迭代过程，也就不影响最终拟合出来的参数，因此为了简化推导过程，我们设 $\sigma = 1$ 。

$\begin{align} N(\mu,\sigma^2) & = \frac{1}{\sqrt{2\pi}}exp(-\frac{1}{2}(y-\mu)^2)\\ & = \frac{1}{\sqrt{2\pi}}exp(-\frac{1}{2}y^2)exp(\mu y-\frac{1}{2}\mu ^2) \end{align}$

因此，高斯分布是指数分布族在

$\begin{align} & \eta = \mu\\ & a(\eta) = -\frac{1}{2}\mu^2\\ & b(y) = \frac{1}{\sqrt{2\pi}}exp(-\frac{1}{2}y^2)\\ & T(y) = y \end{align}$

时的特殊情况。

不仅是高斯分布和伯努利分布，伽马分布、泊松分布都能够写成指数分布族的形式。

构建广义线性模型

广义线性模型符合下述三个假设：

$y|x;\theta \sim Exponential\;Family$
给定 $x$ ，目的是输出一个期望 $E[T(y)|x]$ 使得 $h(x)=E[T(y)|x]$ 最大。
$\eta=\theta^T x$ ，即 $x$ 和 $\eta$ 之间是线性关系。更一般的情况下( $\eta$ 是向量)则： $\eta_i = \theta^T_i x$ .

第三个假设，其实更准确地说是我们在设计GLMs时的一种设计选择（design choice）。有了这些假设和设计选择，我们才能够推导出优美的、具有许多有优良性质的学习算法，也就是GLMs。

在GLMs的基础上，我们如何从概率模型构造出数学函数呢？下面以之前讲过的两个模型为例：

构造出线性回归问题的函数

我们已经分析过，线性回归问题中的目标变量 $y$ （学术上称 $y$ 为“响应变量”）符合高斯分布,那么仅仅知道这一点，我们如何将这个概率模型具体化为某个函数来模拟参数呢？下面用GLMs来做到这一点：

之前已经证明高斯分布是指数分布族的特殊情况。即 $y|x;\theta \sim Exponential \; Family$
对于给定的 $x$ ，算法预测 $T(y)$ （此处 $T(y) = y$ ），因此输出的是 $E[y|x;\theta] = \mu = \eta$
$\eta = \theta^Tx \rightarrow h_\theta(x) = \theta^Tx$

构造出二分类问题中使用的logistic函数

下面使用GLMs从伯努利概率分布函数自然地推导出logistic函数：

$y|x;\theta \sim Exponential \; Family$ 。这个之前已经推导过。
对于给定的 $x,\theta$ ，目标是预测一个 $T(y)$ ，而在大多数情况下 $T(y) = y$ 。因此算法输出 $h_\theta(x) = E[y|x;\theta] = P(y=1|x;\theta) = \phi = \frac{1}{1+e^{-\eta}}$
$\eta = \theta^Tx \rightarrow h_\theta(x) = \frac{1}{1+e^{-\theta^Tx}}$