资料来源参考： CS 229 Machine Learning Course Materials lecture notes 1

牛顿法、一般线性模型

牛顿法

我们知道，在逻辑回归我们曾经将 g(z) 作为sigmoid方程进行逻辑回归。现在，我们来介绍一个用于最大化l(θ)的不同于逻辑回归的算法。

引子

在开始之前，我们先来做一个假设：

假设我们有一个一元函数f(θ)，我们希望找到能够找到一个使f(θ)的值等于0的θ值。在这个假设中，θ是一个实数值。

我们可以假设这个函数的图像如下图所示：

那么，如果我们要用牛顿法来在这个函数图象中找到我们所期望的θ（即使f(θ)=0的横坐标），就可以先在函数的图像上随机的选取一个$θ^{(0)}$，然后作它的切线，如下图：

发现$θ^{(0)}$的切线与横轴交于某点，这个点我们称其为$θ^{(1)}$，然后再根据横坐标$θ^{(1)}$作切线：

得到新的点$θ^{(2)}$…以此类推，不断的用让θ逼近使f(θ)=0的点，让θ越来越接近我们所期望的θ。

这种方法，我们就称之为牛顿方法

推导

根据函数图像，我们假设$θ^{(n)}$与$θ^{(n+1)}$之间的水平距离为Δ，那么就有$\frac{f(θ)}{Δ}=k(切线的斜率)=f'(θ)$，因此，我们可以得到$\frac{f'(θ)}{f(θ)}=Δ=θ^{(n)}-θ^{(n+1)}$从而推出θ的更新规则

这里的牛顿方法给了我们一个求θ使得f(θ)=0的方法。如果，我们想用它来求如逻辑回归中的l(θ)的最大值，那么我们可以知道，如果l(θ)要取最大值，那么，它的导数l’(θ)就应该等于0.由此，当我们将f(θ)=l’(θ)带入牛顿方法的时候，就可以得到求最大化l(θ)的θ更新方法：

我们还可以思考一下，如果我们要求的是l(θ)的最小值，这个方法应该怎么变。（实际上并不会变，因为l(θ)不论是要取最大值还是最小值，它的要求都是l’(θ)=0，而l’‘(θ)会决定它究竟应该是最大值还是最小值）

当然，我们之前也说过了，这里的θ只是一个一维的变量，我们还需要将其推广到多维，也即是说，当θ是一个由多个特征组成的向量的时候，θ的更新方式会变成这样（这个更新方法也被称为Newton-Raphson method（牛顿-拉普森方法？））：

• $\nabla_θl(θ)$是与之前一样表示l(θ)关于向量θ的每一个分量θ_i的偏导数
• H是一个 n x n 的方阵（通常来说，如果我们算上截距项应该是 n+1 x n+1 方阵，这里的n是特征的数量），它被称为海森矩阵（Hessian matrix）。方阵的定义为：

为了便于记忆，我们可以将这个更新方法看作是一阶导数（向量）除以二阶导数（乘以方阵的逆）

牛顿方法的特殊在于它改变了梯度上升算法中θ的步长计算方式，在梯度上升中，我们用学习速度α控制θ的上升幅度，而在这里，牛顿方法的上升幅度会随着$θ^{(i)}$逼近期望的θ而越来越小，它的收敛速度属于“二次收敛”，这个速度会远大于梯度上升，在n不是那么大的情况下。因为显而易见的是，如果n过大，即特征数量过多的时候，对海森矩阵的每一次求逆运算都会开销巨大。当我们使用牛顿方法来求逻辑回归中l(θ)的最大值的时候，我们也称这个算法为Fisher scoring(费希尔计分法？)

一般线性模型(Generalized Linear Models)

目前为止，我们已经了解了回归问题的例子和分类问题的例子：

• 在回归问题中，我们有$y \mid x;θ \sim N(μ,σ^2)$
• 在分类问题中，我们有$y \mid x;θ \sim Bernoulli(Φ)$（伯努利分布）

这两个分布型都能对关于x和θ的函数给出合理的μ和Φ。接下来，我们会在这一节中看到，这两种假设都是一族算法模型中的特例，这一族算法模型就是我们曾经提到过的一般线性模型(GLMs)。我们还将了解别的GLM家族中的模型的推导方式，并且，我们还会将其应用于其他分类与回归问题中。

指数族(exponential family)

让我们先从定义指数分布族开始：

所有属于指数分布族的似然（或说概率）函数，都可以写成如下形式：

• 式中的η称为分布的自然参数(natural parameter)或规范参数(canonical parameter)
• T(y)称为充分统计量(sufficient statistic)（对于我们涉及的分布，通常称T(y)=y）
• a(η)称为对数配分函数(log partition function)
• $e^{-a(η)}$这个量起到标准化常量的作用，它使得p(y;η)求和（离散）或对y求积分（连续）的结果等于1

式中的T，a，b由我们来决定，通过调整这三个变量的内容，我们就能够获得由η参数化的一族（或者一个集合）分布，之后，我们通过改变η就能获得这一族分布中不同的分布函数。

例如接下来我们要展示的伯努利分布和高斯分布，其实都是指数分布中的特例。

伯努利分布的指数表现形式

期望为Φ的伯努利分布写作Bernoulli(Φ)，并且指定在y∈{0,1}上取值，所以有

通过改变变量Φ，我们就可以得到具有不同意义的伯努利分布。这些由Φ确定的伯努利分布就在指数分布族中，即将指数分布族的似然函数中的T，a，b确定下来后，式子就可以转化为伯努利分布类型的表达式。

我们将伯努利分布写为：

因此，我们可以将他与指数分布族的似然函数形式对比，得到自然参数$η=log\frac{Φ}{1-Φ}$，有趣的是，如果我们把这个方程转换成Φ关于η的函数，就可以得到$Φ=\frac{1}{1+e^{-η}}$，我们可以看见，这就是我们熟悉的逻辑回归中的sigmoid函数。当我们用一般线性模型的形式来表示逻辑回归时，我们还可以再一次看到这个现象。

为了将伯努利分布完全用指数分布的形式表达，我们给出其它关于指数分布族的参数：

这表明，当我们选择了合适的T,a,b的时候，伯努利分布是可以完美地由指数分布定义的似然函数形式表示出来。

高斯分布的指数表现形式

先在我们来讨论一下高斯分布的指数表现形式。首先我们需要先回忆一下，记得在对线性回归的似然函数求导的时候我们发现，属于高斯分布中的一个参数σ²是不影响我们求得$h_θ(x)$的参数θ的。因此，我们可以先选择一个方便运算的数字，来代替掉σ²。

这里我们选择σ²=1 。

因此对于高斯分布，我们有：

（实际上，即使我们将σ²以变量的形式留在概率密度函数中，高斯分布依然可以表达成指数分布族的形式，此时$η∈R^2$变为一个由μ和σ共同表示的向量。为了将带有σ²的高斯分布纳入GLM，我们还可以给出一个更一般的指数族定义：

上式中的τ称为离散参数（dispersion parameter），而高斯分布对应的$c(τ)=σ^2$。不过，对于我们简化的高斯分布，并不需要这种更一般的表达方式。）

于是，我们可以将高斯分布写为指数族的形式：

指数族当然还有很多别的成员，比如：

• 多项分布(multinomial)：这个我们将在后面介绍，它类似于伯努利分布，但不同的是，多项分布是对有K个结果的事件建模；
• 泊松分布(Poisson)，用于计数数据建模，比如样本中放射性元素衰变的数、某网站访客的数量、商店顾客的数量；
• 伽马分布和指数分布(the gamma and the exponential)，用于非负连续随机变量建模，如处理时间间隔，或是处理在等公交时发生的“下一辆车什么时候到”的问题；
• 贝塔分布和狄利克雷分布(the beta and the Dirichlet)，通常用于对分数进行建模，它是对概率分布进行建模的概率分布；
• Wishart分布，这是协方差矩阵的分布。

后面的课程还将介绍一种常规方法，来建立对于给定了x，θ的来自上述任意分布的y的模型。

一般线性模型

假设我们先在要建立一个用于估计每小时进入某商店的顾客的数目的模型，我们知道，这个数字的变化依赖于各种各样的特征：商店的促销活动、近期的广告投入、当地天气状况、给定时间是周几等等，将他们作为特征值x，那么我们也能知道泊松分布适合用来预测来访者的数量，那接下来，我们应该如何针对这个问题建立模型呢？幸运的是，泊松分布也属于指数分布族，因此，我们可以对其应用一般线性模型（GLM）。在这一节，我们将介绍如何针对类似模型建立一般线性模型。

一般的，对于想要预测的关于x的随机变量y的分类或回归问题，我们为了推导出关于问题的一般线性模型，模型需要遵守以下三条关于给定x下y的条件概率的假设：

1. $y \mid x;θ \sim ExponentialFamily(η)$,即对于给定的x，θ，分布y必须服从由某个η参数化的指数族分布；
2. 对于给定的x，我们的目标是求出对于条件x下T(y)的期望，即E[T(y)|x]。而在大多数情况下T(y)=y，所以我们希望学习算法得到的输出函数h满足$h(x)=E[y\mid x]$。（需要注意的是，这个假设不论是在逻辑回归还是线性回归的$h_θ(x)$的选择中都是成立的。例如，在逻辑回归中，我们有$h_θ(x)=p(y=1\mid x;θ)\\ =0·p(y=0\mid x;θ)+1·p(y=1\mid x;θ)\\ =E[y\mid x;θ]$ ）
3. 自然参数η和输入x满足线性关系：$η=θ^Tx$.(或者，如果η是一个向量，那么就有η_i=θ^T_i x)

第三条假设可以说是在这些假设中看起来最“不合理”的了，因为它看起来更像是构建一般线性模型的“设计决策”，而不是假设。这三条假设（或说，“设计决策”）可以让我们得到一类十分简洁的学习算法，也就是所谓的一般线性模型，并且该模型会具有良好的特性，比如，便于我们学习。 此外，所得模型通常对关于y的不同类型分布的建模都有良好的效果，比如我们接下来将介绍的一般线性模型既能推导出逻辑回归，也能推导出普通最小二乘。

普通最小二乘

为了证明普通最小二乘是一个GLM模型中的特例，我们需要考虑目标变量y（在一般线性模型术语中也称作响应变量（response variable））是连续的。我们使用高斯分布$N(μ,σ^2)$建立关于给定x下y的条件概率模型（μ可能与x有关）。 也就是说，让我们先令假设1中的ExponentialFamily(η)为高斯分布。正如在前面推导出的，将高斯分布写为指数分布族的公式中，有μ=η,因此，我们有：

这里是详细的推导证明：

从而得到模型$h_θ(x)=θ^Tx$

逻辑回归

先在我们来讨论逻辑回归的模型。我们这里主要讨论二元分类模型，因此$y∈\{0,1\}$。由于给定了y是一个二进制值，因此我们可以很自然地选择伯努利模型来作为指数分布族地分布模型。由之前地推导，我们可以得到：

此外，当我们得到：

的时候，同时也得到了 $E[y\mid x;θ]=Φ$.因此，类似于我们推导普通二乘那样，我们可以得到：

因此，我们建立了一个模型 $h_θ(x)=\frac{1}{1+e^{-θ^Tx}}$

因此，我们可以发现逻辑函数$\frac{1}{1+e^{-z}}$的来源就是就是这里： 也即是说，一旦我们假设对给定的x的y的条件概率服从伯努利分布，我们就可以推导出伯努利分布的指数分布族形式，进而得到一般线性模型的定义。

我们顺便再来引入一些术语，当我们有一个关于自然参数η的函数g给出了分布期望($g(η)=E[T(y);η]$)时，我们可以把这个函数称作正则响应函数(canonical response function)，其逆$g^{-1}$称作正则关联函数(canonical link function)。对于高斯分布，正则响应函数就是$g(η)=η$;对于伯努利分布就是逻辑函数（很多教材将g作为正则连接函数，而用$g^{-1}$来表示正则响应函数，但我们在这里的表示法沿用以往的机器学习课程，并将在后面的课程中继续使用这种记法。）

Softmax回归

再来看一个一般线性模型的例子：如果在分类问题中，y不再是1或0而是能够取k个值，即$y∈\{1,2,...,k\}$，也就是说，响应变量仍然是离散值，但是变成了两个以上的值的时候，我们就需要使用多项分布(multinomial distribution)。

要想建立这类问题的一般线性模型，我们首先需要将多项分布表达成指数分布族的形式。

为了参数化有k个可能取值的多项分布，我们使用k个参数$Φ_1,...,Φ_k$，用来表示每个可能的取值发生的概率。然而，这样设置参数有可能会有冗余（过度参数化，over-parameterized），换句话说，他们之间是线性相关的（如果我们知道任意k-1个$Φ_i$，都可以使用$\sum^k_{i=1}Φ_i=1$算出最后一个未知Φ的值（即$Φ_k=1-\sum^{k-1}_{i=1}Φ_i$））。 因此，我们设置有k-1个参数：

则

为了写起来方便，在后面的推导中，我们令$Φ_k=1-\sum^{k-1}_{i=1}Φ_i$，但我们要清楚，这并不是一个参数，它是由参数$Φ_1,...,Φ_{k-1}$计算而来的。

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

与之前不一样的是这里的$T(y)≠y$；并且，T(y)现在是一个 k-1 维的向量，而不是一个实数。我们用$(T(y))_i$来表示向量$T(y)$中的第i个元素。

我们再来引入一个非常有用的标记：指示函数(indicator function):

这个函数的意思是，如果它的参数值为真，则返回1，反之，返回0：

举个例子： $1\{2=3\}=0，1\{3=5-2\}=1$

我们可以用这个函数表示T(y)与y的关系：

也即是说，只有当$(T(y))_i$中的y与i取值相同（取到T(y)向量中的第y个值）时，指示函数输出值 $1$。

此外，我们还有

现在，我们要证明多项分布是指数分布族的一员了：

因此

这个过程完成了我们对多项分布属于指数分布族的推导。

正则连接函数（参数η关于期望Φ的函数）为：

为了表示方便，我们令$η_k=log\frac{Φ_k}{Φ_k}=0$，求正则响应函数（即正则连接函数的逆，期望Φ关于参数η的函数）：

第三个式子表明$Φ_k=\frac{1}{\sum^k_{i=1}e^{η_i}}$，代回第二个式子得到响应函数：

这个函数是由η到Φ的映射，也叫做softmax函数。

接下来我们要使用假设3，也就是$η_i$是输入变量x的线性函数，因此，我们有：$η_i=θ^T_ix,η∈R^{k-1},i=1,...,k-1$，这里θ仍旧是特征值x的系数，有$θ_1,...,θ_{k-1}∈R^{n+1}$(n是训练样本所取特征值的个数)。我们还要定义$θ_k=0$，因此，$η_k=θ^T_kx=0$，就像之前推导的一样。因此，我们的模型就表示在条件x已知的情况下求y的分布：

这个可以应用到$y∈\{1,...,k\}$的模型就叫做softmax 回归。是逻辑回归的一般形式。

接着，我们的输出函数就是：

换句话说，我们的输出函数会对$p(y=i\mid x;θ)$中$i=1,...,k$的每一个值做出概率估计（尽管$h_θ(x)$被定义在了 k-1 维上。因为显而易见的是，$p(y = k \mid x;θ)$可以被当作是 $1-\sum^{k-1}_{i=1}Φ_i$。）

最后，让我们求一下拟合参数。与普通最小二乘和逻辑回归中的推导方法相似，如果训练集中有m个训练样本$\{(x^{(i)},y^{(i)});i=1,...,m\}$，想通过学习算法得到$θ_i$，则需要同以前一样，先写出似然函数：

再对似然函数取对数：

在上面的推导中我们使用了(2)式给出的$p(y=i \mid x;θ)$的定义，剩下的就是计算l(θ)中参数的最大似然估计了，计算过程可以使用前面介绍的梯度上升或牛顿法。

我们可以把一般线性模型的建模过程概括为：

1. 根据训练集$x^{(i)}，y^{(i)}$选择概率分布模型，参数为Φ
2. 将该分布写为指数分布族的形式，参数为η
3. 求出正则响应函数$g(η)=E[T(y);η]$
4. 将$η=θ^Tx$带入正则响应函数，然后根据正则响应函数得到输出函数$h_θ(x)=E[T(y)\mid x]$
5. 根据模型的概率解释得到似然函数$L(θ)=p(y\mid x;θ)$（根据输出函数得到，这里要注意用合适的概率$p^{(i)}$的联合方式）
6. 取合适的θ使似然最大化。

最后，我还需要手动详细推导一遍，以连接这部分知识体系（我的个人推导并不一定完全正确，仅供参考）：