CS229 Lesson 4 牛顿方法

课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了牛顿法以及广义线性模型。

7.另一种最大化$ℓ(θ)$的算法

回到logistic回归，其中$g(z)​$是sigmoid函数，现在让我们讨论一种最大化$ℓ(θ)​$的不同算法。

​ 为了让我们开始，让我们考虑牛顿法来找到一个函数的零点。 具体来说，假设我们有某个函数$f:\mathbb R\to \mathbb R​$，我们希望找到$θ​$的值，使得$f(θ)= 0​$。这里，$θ\in \mathbb R​$是实数。 牛顿法执行以下更新：

$$\theta: =\theta -\frac{f(\theta)}{f'(\theta)}$$

这种方法有一个自然的解释，我们可以把它想象为通过一个线性函数近似函数$f$，该函数与当前猜测点$θ$处的$f$相切，求解线性函数等于零的位置，并让下一个$\theta$的猜测为线性函数为零的地方。

​ 在最左边的图中，我们看到函数$f$与直线$y = 0$一起绘制。我们试图找到$θ$使得$f(θ)= 0$；达到此目的的$\theta $值约为$1.3$。 假设我们用$θ= 4.5$初始化算法。 牛顿的方法在$θ= 4.5$处拟合与$f$相切的直线，并求解该线的零点。（中图。）这给出了$θ$的下一个猜测，即$2.8$。 最右边的图显示了再运行一次迭代的结果，其中将$θ$更新为$1.8$。 经过几次迭代后，我们快速接近$θ= 1.3​$。

​ 牛顿方法给出了一种求解$f(θ)= 0$的方法。如果我们想用它来最大化某些函数$ℓ$该怎么做？ $ℓ$的最大值对应于其一阶导数$ℓ’(\theta)$为零的点。 因此，通过令$f(\theta)=ℓ’(\theta)$，我们可以使用相同的算法来最大化$ℓ$，并且我们获得更新规则：

$$\theta : =\theta -\frac{ℓ'(\theta)}{ℓ''(\theta)}$$

（最小化$ℓ $也是使用上述更新规则。）

​ 最后，在我们的logistic回归情形中，$θ​$是向量，因此我们需要将牛顿方法推广到此情形。 牛顿方法对这种多维情形（也称为Newton-Raphson方法）的推广由下式给出：

$$\theta : =\theta -H^{-1} \nabla_{\theta}ℓ(\theta)$$

在这里，$ \nabla_{\theta}ℓ(\theta)$和往常一样，是$ℓ(\theta)$关于$\theta_i$的偏导数的向量。 和$H$是一个$n\times n$矩阵（实际上是$(n+1)\times (n+1)$，假设我们包括截距项）称为Hessian，矩阵的每一项由下式给出：

$$H_{ij} =\frac{\partial^2 ℓ(\theta)}{\partial \theta_i\partial \theta_j}$$

​ 牛顿法通常比（批量）梯度下降更快收敛，并且需要更少的迭代就能非常接近最小值。 然而，牛顿法的一次迭代可能比一次梯度下降迭代计算量更大，因为它需要找到对$n\times n$的Hessian求逆；但只要$n$不是太大，整体通常要快得多。 当牛顿方法应用于最大化logistic回归对数似然函数$ℓ(\theta )$时，得到的方法也称为Fisher评分。

​

Part III 广义线性模型

到目前为止，我们已经看到了回归样例和分类样例。 在回归样例中，我们有$y|x; θ\sim \mathcal N（μ，σ^2）$，在分类中，$y|x; θ\sim \text{Bernoulli}(\phi)$，$μ$和$\phi$定义为$x$和$θ$的函数。 在本节中，我们将展示这两种方法都是更广泛的模型族的特例，称为广义线性模型（GLM）。我们还将展示如何推导GLM族中的其他模型并将其应用于其他分类和回归问题。

8.指数族

为了完成GLM，我们将首先定义指数族分布。我们说一类分布属于指数族，如果它们可以表达为如下形式：

$$\begin{eqnarray*} p(y;\eta) =b(y)\exp \big( \eta^T T(y)-a(\eta) \big) \tag{6} \end{eqnarray*}$$

在这里，$\eta​$称为分布的自然参数（也称为规范参数）; $T(y)​$是充分统计量（对于我们考虑的分布，通常是$T(y)= y​$）的情况；$a(\eta)​$是对数分区函数(log partition function)。 $e^{-a(\eta)}​$起归一化常数的作用，这确保分布$p(y;\eta)​$关于$y​$的积分为$1​$。

​ 定义分布族的$T,a,b$由$η$参数化；当我们改变$η$时，我们在这个族中会获得不同的分布。

​ 我们现在说明伯努利和高斯分布是指数族分布的实例。 均值为$\phi$的伯努利分布记$\text{Bernoulli}(\phi)$，伯努利定义了$y∈\{0,1\}$上的分布，因此$p(y = 1;φ)=\phi; p(y = 0;φ)= 1 - \phi$。 当我们改变$\phi$时，我们获得不同均值的伯努利分布。 我们现在表明，这类伯努利分布，即通过变化$\phi$获得的分布，是指数族; 即，可以选择$T,a,b$，使得等式（6）恰好成为伯努利分布。

​ 我们将伯努利分布改写为：

$$\begin{aligned} p(y;\eta)&=\phi^y(1-\phi)^{1-y} \\ &=\exp \big( y\log \phi +(1-y)\log(1-\phi) \big)\\ &=\exp \Big( \Big( \log\Big(\frac{\phi}{1-\phi}\Big) \Big)y+\log(1-\phi) \Big) \end{aligned}$$

因此，自然参数由$\eta =\log(\phi/(1-\phi))​$给出。有趣的是，如果我们求解$\phi​$，我们得到$\phi =1/(1+e^{-\eta})​$。 这是熟悉的sigmoid函数！当我们将逻辑回归推导为GLM时，这将再次出现。 为了完成伯努利分布作为指数族分布的公式，我们有

$$\begin{aligned} T(y)&= y \\ a(\eta)&= -\log(1-\phi) \\ &=\log(1+e^\eta)\\ b(y)&=1 \end{aligned}$$

这表明伯努利分布可以选择合适的$T,a,b $以等式（6）的形式写出。

​ 现在让我们继续考虑高斯分布。 回顾一下，当推导出线性回归时，$\sigma^2$的值对$θ$和$h(x)$的最终选择没有影响。 因此，我们可以选择任意值的$\sigma^2$而不改变任何东西。 为了简化下面的推导，让我们令$\sigma^2=1$，然后我们有：

$$\begin{aligned} p(y;\mu) &=\frac 1{\sqrt{2\pi}} \exp \Big( -\frac 12 (y-\mu)^2 \Big) \\ &=\frac 1{\sqrt{2\pi}} \exp\Big( -\frac 1 2 y^2 \Big). \exp \Big( \mu y-\frac 1 2 \mu^2 \Big) \end{aligned}$$

因此，我们看到高斯分布是指数族，且有

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

​ 还有许多其他分布是指数族的成员：多项分布（我们将在后面看到），泊松分布（用于建模计数数据）; 伽玛和指数分布（用于建模连续的，非负的随机变量，如时间间隔）; beta和Dirichlet（用于建模概率的分布）；还有很多。 在下一节中，我们将描述构建模型的一般“配方”，其中$y$（给定$x$和$θ$）来自任何这些分布。

9.构造GLM

假设您想建立一个模型，根据商店促销，近期广告，天气等特定特征$x​$，估算在任何给定时间内到达您商店的客户数量（或您网站上的网页浏览量） 我们知道Poisson分布通常为访客数量提供了一个很好的模型。 知道了这一点，我们怎样才能为我们的问题找到一个模型？ 幸运的是，Poisson是一个指数族分布，因此我们可以应用广义线性模型（GLM）。 在本节中，我们将描述为这些问题构建GLM模型的方法。

​ 更一般地，考虑一个分类或回归问题，我们希望将某个随机变量$y​$的值预测为$x​$的函数。 为了得到这个问题的GLM，我们将对给定$x​$和关于我们的模型的$y​$的条件分布做出以下三个假设：

1. $y|x;\theta\sim \text{ExponentialFamily}(\eta)​$。即，给定$x​$和$θ​$，$y​$服从某个指数族分布，且参数为$η​$。

2. 给定$x$，我们的目标是预测给定$x$的$T(y)$的期望值。在我们的大多数例子中，我们有$T(y)= y$，所以这意味着我们希望我们的预测$h(x)$满足$h(x)= \mathbb E [y | x]$。 （注意，在logistic回归和线性回归的$h(x)$选择中都满足这个假设。例如，在logistic回归中，我们得到

   $$h_{\theta}(x) = p(y = 1|x; θ) = 0 · p(y =0|x; θ) + 1 · p(y = 1|x; θ) = \mathbb E[y|x; θ]$$

   ）

3. 自然参数$η$和输入$x$线性相关：$η=θ^Tx$。 （或者，如果$η$是向量，那么$η_i=θ^T_ix$。）

​ 这些假设中的第三个看起来似乎是最不合理的假设，在我们构建GLM的方法中可能更好地将其视为“设计选择”，而不是作为假设本身。 这三个假设/设计选择将使我们能够得到一种非常优雅的学习算法，即GLM，它具有许多理想的属性，如易于学习。 此外，得到的模型通常非常有效地用于对$y​$上的不同类型的分布进行建模；例如，我们将很快显示logistic回归和普通最小二乘都可以作为GLM导出。

9.1 普通最小二乘

为了表明普通最小二乘是GLM模型族的特例，考虑目标变量$y​$（也称为GLM术语中的响应变量）是连续的情形，并且我们将给定$x​$的$y​$的条件分布建模为高斯分布$\mathcal N(μ，σ^2)​$。 （这里，$\mu​$可能依赖于$x​$。）因此，我们让上面的$\text{ExponentialFamily}(\eta)​$分布为高斯分布。 如前所述，在高斯分布作为指数族分布的公式中，我们得到$μ=η​$。 所以，我们有

$$\begin{aligned} h_\theta(x) &=\mathbb E[y|x; θ]\\ &= \mu \\ &= \eta \\ &= θ^T x \end{aligned}$$

第一个等号来自上面的假设2；第二个等号是因为$y | x; θ\sim \mathcal N(\mu，\sigma^2)​$，其期望由$\mu​$给出；第三个等号来自假设1（以及我们之前的推导，表明在高斯分布以$μ=η​$作为指数族分布）; 最后的等号来自假设3。

9.2 Logistic回归

我们现在考虑Logistic回归。 这里我们对二元分类问题感兴趣，所以$y\in \{0,1\}​$。 鉴于$y​$是二值的，因此选择伯努利分布族来模拟给定$x​$，$y​$的条件分布似乎是自然的。 在我们将伯努利分布表示为指数族分布时，我们得到$\phi =1/(1+e^{-\eta})​$。 此外，请注意，如果$y|x; θ \sim \text{Bernoulli}(\phi)​$，因此$\mathbb E[y|x; θ]=\phi​$。 因此，遵循与普通最小二乘法相似的推导，我们得到：

$$\begin{aligned} h_{\theta}(x) &= \mathbb E[y|x; θ]\\ &=\phi \\ &=1/(1+e^{-\eta})\\ &=1/(1+e^{-\theta^T x}) \end{aligned}$$

因此，这给出了形如$h_{\theta}=1/(1+e^{-\theta^T x})$的假设函数。 如果你以前想知道我们如何提出logistic函数$1/(1+e^{-z})$的形式，这给出了一个答案：一旦我们假设以$y$关于$x$的分布是伯努利分布，它就是GLM和指数族分布产生的结果。

​ 为了介绍更多的术语，给定分布的均值作为自然参数的函数$g​$（$g(η) = \mathbb E[T(y); η]​$）被称为正则响应函数。 它的逆$g^{-1}​$称为正则关联函数。 因此，高斯族的正则响应函数是单位函数；伯努利的正则响应函数是logistic函数。

9.3 Softmax回归

让我们看一下GLM的另一个例子。 考虑一个分类问题，其中响应变量$y​$可以取$k​$个值中的任何一个，因此$y∈\{1,2,…,k\}​$。 例如，我们可能希望将电子邮件分类为垃圾邮件，个人邮件和工作相关邮件等三类，而不是将电子邮件分类为垃圾邮件或非垃圾邮件这两类。 响应变量仍然是离散的，但现在可以采用两个以上的值。 因此，我们将根据多项分布对其进行建模。

​ 让我们推导一个GLM来建模这种多类别分类问题。 为此，我们将首先将多项分布表示为指数族分布。

​ 为了在$k$个可能的结果上参数化多项分布，我们可以使用$k$个参数$\phi_1，…，\phi_k$指定每个结果的概率。 然而，这些参数将是冗余的，或者更正式地，它们将不是独立的（因为知道$\phi_i$的任何$k-1$个值可以唯一地确定最后一个，因为它们必须满足$\sum_{i=1}^k \phi_i=1$）。 因此，我们将仅使用$k -1$个参数，$\phi_1，…，\phi_{k-1}$来参数化多项分布，其中$\phi_i= p(y = i;φ)$，并且$p(y = k;φ)=1-\sum_{i=1}^{k-1}p(y = i;φ)$。 为了方便起见，我们令$\phi_k=1-\sum_{i=1}^{k-1}\phi_i$，但我们应该记住，这不是一个参数，而是由$\phi_1，…，\phi_{k-1}$完全确定。

​ 为了将多项分布表示为指数族分布，我们将$T(y)\in \mathbb R^{k-1}$定义如下：

$$T(1)= \left[ \begin{matrix}1\\ 0\\ 0\\ \vdots \\ 0 \end{matrix} \right] , T(2)= \left[ \begin{matrix}0\\ 1\\ 0\\ \vdots \\ 0 \end{matrix} \right], T(3)= \left[ \begin{matrix}0\\ 0\\ 1\\ \vdots \\ 0 \end{matrix} \right], ..., T(k-1)= \left[ \begin{matrix}0\\ 0\\ 0\\ \vdots \\ 1 \end{matrix} \right], T(k)= \left[ \begin{matrix}0\\ 0\\ 0\\ \vdots \\ 0 \end{matrix} \right]$$

与我们之前的例子不同，这里我们没有$T(y)=y$; 此外，$T(y)$现在是$k-1$维向量，而不是实数。 我们将用$(T(y))_i$来表示向量$T(y)$的第$i​$个元素。

​ 我们介绍一个非常有用的符号。 如果参数为真，则示性函数$1 \{·\}$的值为$1$，否则为$0$，即

$$1\{\text{True} \} = 1,1 \{\text{False} \}= 0$$

例如，$1 \{2 = 3\} = 0$，并且$1 \{3 = 5 - 2\} = 1$。因此，我们也可以将$T(y)$和$y$之间的关系写为$(T(y))_i=1\{y=i \}$。此外，我们有$\mathbb [(T(y))_i]=P(y=i)= \phi_i$。

​ 我们现在准备证明多项式是指数族的成员。 我们有：

$$\begin{aligned} p(y:\phi) &= \phi_1^{1\{y=1\}}\phi_2^{1\{y=2\}}...\phi_k^{1\{y=k\}}\\ &=\phi_1^{1\{y=1\}}\phi_2^{1\{y=2\}}...\phi_k^{1-\sum_{i=1}^{k-1}1\{y=i\}} \\ &=\phi_1^{(T(y))_1}\phi_2^{(T(y))_2}...\phi_k^{1-\sum_{i=1}^{k-1}(T(y))_i} \\ &= \exp \big( (T(y))_1 \log(\phi_1)+(T(y))_2 \log(\phi_2)+ ...+\Big( 1-\sum_{i=1}^{k-1}(T(y))_i\Big) \log(\phi_k) \big) \\ &=\exp \big( (T(y))_1 \log(\phi_1/\phi_k)+(T(y))_2 \log(\phi_2/\phi_k)+... (T(y))_{k-1} \log(\phi_{k-1}/\phi_k)+ \log(\phi_k) \big)\\ &=b(y) \exp\big( \eta^T T(y)-a(\eta) \big) \end{aligned}$$

其中

$$\begin{aligned} \eta &= \left[ \begin{matrix} \log(\phi_1/\phi_k)\\ \log(\phi_2/\phi_k) \\ \vdots \\ \log(\phi_{k-1}/\phi_k) \end{matrix} \right] \\ a(\eta)&= -\log(\phi_k)\\ b(y)&=1 \end{aligned}$$

​ 关联函数（对于$i = 1,…,k​$）由下式给出

$$\eta_i =\log \frac{\phi_i} {\phi_k}$$

为方便起见，我们还定义了$η_k= \log(\phi_k/\phi_k)= 0$。反转关联函数并导出响应函数，我们得到

$$\begin{eqnarray*} e^{\eta_i} &&= \frac{\phi_i}{\phi_k} \\ \phi_k e^{\eta_i}&&= \phi_i \tag 7 \\ \phi_k \sum_{i=1}^k e^{\eta_i}&&= \sum_{i=1}^k \phi_i =1 \end{eqnarray*}$$

这意味着$\phi_k =1/\sum_{i=1}^k e^{\eta_i}$，可以将其代入等式（7）以给出响应函数

$$\phi_i =\frac{e^{\eta_i}}{\sum_{j=1}^k e^{\eta_j}}$$

从$η$到$\phi $的映射函数称为softmax函数。

​ 为了完成我们的模型，我们使用前面给出的假设3，即$η_i$与$x$线性相关。 因此，有$η_i=θ_i^Tx$（对于$i = 1,…,k-1$）其中$θ_1,…,θ_{k-1}\in \mathbb R^{n+ 1}$是我们模型的参数。 为了符号方便，我们还可以定义$θ_k= 0$，所以$η_k=θ_k^Tx = 0$，如之前所述。 因此，我们的模型假设给定$x$，$y$的条件分布由下式给出

$$\begin{eqnarray*} p(y=i|x;\theta) &&=\phi_i \\ &&=\frac{e^{\eta_i}}{\sum_{j=1}^k e^{\eta_j}} \\ &&=\frac{e^{\theta_i^T x}}{\sum_{j=1}^k e^{\theta_j^T x}} \tag 8 \end{eqnarray*}$$

该模型适用于分类问题，其中$y∈\{1,…,k\}​$，称为softmax回归。它是logistic回归的推广。

​ 我们的假设将输出

$$\begin{aligned} h_{\theta}(x) &=\mathbb E[T(y)|x;\theta]\\ &=\mathbb E\left[ \begin{array}{c|c} 1\{y=1\} \\ 1\{y=2\} \\ \vdots& x;\theta \\ 1\{y=k-1\} \end{array} \right] \\ &=\left[ \begin{array}{c|c} \phi_1 \\ \phi_2\\ \vdots \\ \phi_{k-1} \end{array} \right] \\ &=\left[ \begin{array}{c|c} \frac{e^{\theta_1^T x}}{\sum_{j=1}^k e^{\theta_j^T x}} \\ \frac{e^{\theta_2^T x}}{\sum_{j=1}^k e^{\theta_j^T x}}\\ \vdots \\ \frac{e^{\theta_{k-1}^T x}}{\sum_{j=1}^k e^{\theta_j^T x}} \end{array} \right] \end{aligned}$$

换句话说，对于$i = 1,…,k$的每个值，我们的假设将输出$p(y = i | x;θ)$的概率估计值。（尽管如上定义的$h(x)$仅为$k-1$维，但由$1-\sum_{i=1}^{k-1}\phi_i$显然可以得到$p(y = k | x;θ)$。）

​ 最后，让我们讨论参数拟合。 类似于我们对普通最小二乘和logistic回归的原始推导，如果我们有一个训练集，它有$m​$个训练样本$\{(x^{(i)},y^{(i)});i=1,…,m\}​$并且想要学习这个模型的参数$\theta_i​$，我们首先写下对数似然

$$\begin{aligned} ℓ(θ) & =\sum_{i=1}^m \log p(y^{(i)}|x^{(i)};\theta) \\ &=\sum_{i=1}^m \log \prod_{l=1}^k \Big( \frac{e^{\theta_l^T x}}{\sum_{j=1}^k e^{\theta_j^T x}} \Big)^{1\{y^{(i)}=l\}} \end{aligned}$$

为了获得上面的第二行，我们使用等式（8）中给出的$p(y|x;\theta)​$的定义。 我们现在可以通过使用诸如梯度上升或牛顿法之类的方法，关于$θ​$来最大化$ℓ(θ)​$，从而获得参数的最大似然估计。