Cs229 4


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.

假装有打赏功能