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​$是实数。 牛顿法执行以下更新:

这种方法有一个自然的解释,我们可以把它想象为通过一个线性函数近似函数$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)$,我们可以使用相同的算法来最大化$ℓ$,并且我们获得更新规则:

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

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

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

​ 牛顿法通常比(批量)梯度下降更快收敛,并且需要更少的迭代就能非常接近最小值。 然而,牛顿法的一次迭代可能比一次梯度下降迭代计算量更大,因为它需要找到对$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,我们将首先定义指数族分布。我们说一类分布属于指数族,如果它们可以表达为如下形式:

在这里,$\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)恰好成为伯努利分布。

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

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

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

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

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

​ 还有许多其他分布是指数族的成员:多项分布(我们将在后面看到),泊松分布(用于建模计数数据); 伽玛和指数分布(用于建模连续的,非负的随机变量,如时间间隔); 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回归中,我们得到

  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)​$分布为高斯分布。 如前所述,在高斯分布作为指数族分布的公式中,我们得到$μ=η​$。 所以,我们有

第一个等号来自上面的假设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​$。 因此,遵循与普通最小二乘法相似的推导,我们得到:

因此,这给出了形如$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(y)=y$; 此外,$T(y)$现在是$k-1$维向量,而不是实数。 我们将用$(T(y))_i$来表示向量$T(y)$的第$i​$个元素。

​ 我们介绍一个非常有用的符号。 如果参数为真,则示性函数$1 \{·\}$的值为$1$,否则为$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$。

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

其中

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

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

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

从$η$到$\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$的条件分布由下式给出

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

​ 我们的假设将输出

换句话说,对于$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​$,我们首先写下对数似然

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

本文标题:CS229 Lesson 4 牛顿方法

文章作者:Doraemonzzz

发布时间:2019年02月15日 - 13:39:00

最后更新:2019年02月28日 - 15:10:34

原始链接:http://doraemonzzz.com/2019/02/15/CS229 Lesson 4 牛顿方法/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。