Posted on

title: “【CS229-4】牛顿方法” layout: post excerpt: “本讲主要涉及的知识点有；Logistic回归——牛顿方法／指数分布族／广义线性模型。” last_modified_at: 2012-02-05T10:27:01-05:00 tags:

  • CS229
  • ML
  • GLM categories: 做笔记 —

本讲主要涉及的知识点有；Logistic回归——牛顿方法／指数分布族／广义线性模型

牛顿方法(Newton Method)，在专业所学的《工程数学 计算方法》中，也称为“牛顿下山法”，是用于改进算法收敛速度的典型方法。

指数分布族(Exponential Family)，用于解释算法的一般化理论。

广义线性模型(Generalized Linear Models)，以指数分布族理论为基础，建立的模型推动计算的过程。

一、牛顿方法(Newton Method)

回顾上一节的极大似然估计：

img

除了前面讲过的批梯度上升和随机梯度上升外，我们可以用另一种算法来使l(θ)最大化，称之为牛顿方法。

牛顿方法的计算过程：

给定一个初始值θ0，求出f(θ0)；

过(θ0,f(θ0))，作函数在该点的切线，将其与x轴的交点记为θ1；

令 delta = θ0-θ1, 因为 f ‘(θ0) = f(θ0)/delta, 所以delta = f(θ0)/f ‘(θ0);

所以θ1 = θ0 – delta = θ0 – f(θ0)/f ‘(θ0);

一般地，我们有：θ(t+1) = θ(t) – f(θ(t))/f ‘(θ(t)).

对前面的l(θ)，为了使l(θ)最大化，则对l(θ)求导，并令导数l ‘(θ) = 0,利用牛顿方法找到极值：

θ(i+1) = θ(i) – l ‘(θ(t))/l ”(θ(t))

示意图：

img

课堂Q&A:

Q1:该方法是否对任何函数都有效？

A1:对Logistic函数和GLMs都是很有效的，其他函数的问题归纳起来比较复杂。

Q2:θ的初值选择影响大吗？

A2:通常会将θ(0)初始化为0（或0向量），通常情况下算法会工作的很好，这并不是个大问题。

Q3:这个算法一定能保证收敛吗？

A3:通常情况下可以，除非你选择了一个斜率很大的函数或其他原因。

* 算法收敛速度比较

牛顿方法在最优解附近是“二次收敛”的。对于几十个或上百个特征的问题，Newton方法通常在迭代十几次后收敛。

当θ是一个向量时，上面的公式应该写成：

img

其中，

img

对Logistic回归来说，该算法优点是迭代次数少，缺点是每次计算都需要计算H的逆，计算代价大（对于特征数目较合理的问题，该算法很适用）。

二、指数分布族(Exponential Family)

回顾两个算法：

高斯分布->最小二乘法

伯努利分布->Logistic回归

为什么我们会得到Logistic函数呢？

因为上述两种算法是广义线性模型(GLM)的特例(GLM将在第三部分讲述)。

1.伯努利分布

Bernoulli(Φ)，即P(y=1;Φ) =Φ, 改变Φ时，这是一类概率分布；同理，N(μ,σ^2)也是一类概率分布。它们均属于指数分布族，形式如下：

img

其中，η是自然参数，T(y)是充分统计量（通常，T(y)=y，对高斯分布和伯努利分布均是如此）；

若固定a、b、T，则得到了一个概率分布集（以η为参数）

例如，伯努利分布可以写成：

img

因为η是标量，所以将转置符号去掉以后，把η看成自变量，Φ看作函数，得到：

Φ = 1/(1+e^(-η))，a(η),b(y),T(y)如下：

img

2.高斯分布

与伯努利分布类似，高斯分布也可以转化成指数分布族的标准形式。这里为了计算简洁且不影响正确性，令σ^2 = 1。

img

根据形式，观察出a,b,T,η结果如下：

img

* 指数分布族还有其他例子，比如多元正态分布／伯努利分布／多项式分布／泊松分布／伽马分布／指数分布

三、广义线性模型(Generalized Linear Model)

假设：

  • y x; θ~ExpFamily(η)
  • 给定x，输出y的期望值 E[T(y) x], 并希望h(x) = E[T(y) x]
  • η = θT x (若η是向量，则ηi =θiT x.)

例：多项式分布(Multinomial)

y∈{1,2,…,k} (有很多决策问题是超过两个分支的)

学习算法将三类或更多类的数据分开。

参数：Φ1, Φ2, … , Φk

且P(y = i) = Φi

由于Φk = 1-Φ1-Φ2-…-Φ(k-1)，所以Φk是冗余的，我们将参数置为Φ1, Φ2, … , Φ(k-1).

则T(y)∈R(k-1)如下定义：

img

  • 指示函数 1{True} = 1, 1{False} = 0. 如1{2=3}=0,1{1+1=2}=1, 指示函数用于标示括号中命题的真假。

设 T(y)i 表示 T(y) 中的第i个元素，由定义知：T(y)i = 1{y = i}

下面将多项式分布写成指数分布族的形式：

img

其中：

img

将η和Φ倒过来：

img

h(θ)推导过程如下：

img

上述算法被称为softmax回归，被认为是Logistic回归的推广。

（End）

本讲从数学模型上逐渐加深，需要仔细体会方法的核心和精髓，理解每一步数学推导的过程。

更新讲义的速度越来越慢了..可能以后不会写的这么详细了，拣重点做记录，把更多的时间用在实践上。

End.

Read more »