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)
回顾上一节的极大似然估计：
除了前面讲过的批梯度上升和随机梯度上升外，我们可以用另一种算法来使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))
示意图：
课堂Q&A:
Q1:该方法是否对任何函数都有效？
A1:对Logistic函数和GLMs都是很有效的，其他函数的问题归纳起来比较复杂。
Q2:θ的初值选择影响大吗？
A2:通常会将θ(0)初始化为0（或0向量），通常情况下算法会工作的很好，这并不是个大问题。
Q3:这个算法一定能保证收敛吗？
A3:通常情况下可以，除非你选择了一个斜率很大的函数或其他原因。
* 算法收敛速度比较
牛顿方法在最优解附近是“二次收敛”的。对于几十个或上百个特征的问题，Newton方法通常在迭代十几次后收敛。
当θ是一个向量时，上面的公式应该写成：
其中，
对Logistic回归来说，该算法优点是迭代次数少，缺点是每次计算都需要计算H的逆，计算代价大（对于特征数目较合理的问题，该算法很适用）。
二、指数分布族(Exponential Family)
回顾两个算法：
高斯分布->最小二乘法
伯努利分布->Logistic回归
为什么我们会得到Logistic函数呢？
因为上述两种算法是广义线性模型(GLM)的特例(GLM将在第三部分讲述)。
1.伯努利分布
Bernoulli(Φ)，即P(y=1;Φ) =Φ, 改变Φ时，这是一类概率分布；同理，N(μ,σ^2)也是一类概率分布。它们均属于指数分布族，形式如下：
其中，η是自然参数，T(y)是充分统计量（通常，T(y)=y，对高斯分布和伯努利分布均是如此）；
若固定a、b、T，则得到了一个概率分布集（以η为参数）
例如，伯努利分布可以写成：
因为η是标量，所以将转置符号去掉以后，把η看成自变量，Φ看作函数，得到：
Φ = 1/(1+e^(-η))，a(η),b(y),T(y)如下：
2.高斯分布
与伯努利分布类似，高斯分布也可以转化成指数分布族的标准形式。这里为了计算简洁且不影响正确性，令σ^2 = 1。
根据形式，观察出a,b,T,η结果如下：
* 指数分布族还有其他例子，比如多元正态分布／伯努利分布／多项式分布／泊松分布／伽马分布／指数分布
三、广义线性模型(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)如下定义：
- 指示函数 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}
下面将多项式分布写成指数分布族的形式：
其中：
将η和Φ倒过来：
h(θ)推导过程如下：
上述算法被称为softmax回归，被认为是Logistic回归的推广。
（End）
本讲从数学模型上逐渐加深，需要仔细体会方法的核心和精髓，理解每一步数学推导的过程。
更新讲义的速度越来越慢了..可能以后不会写的这么详细了，拣重点做记录，把更多的时间用在实践上。
End.