Contents
  1. 1. 1. 逻辑回归
  2. 2. 2. 梯度上升法求解逻辑回归
  3. 3. 3. 牛顿迭代法求解逻辑回归
    1. 3.1. 3.1 牛顿迭代法简述
    2. 3.2. 3.2 迭代过程
      1. 3.2.1. 从泰勒展开到牛顿迭代
    3. 3.3. 3.3 多维向量的牛顿迭代
    4. 3.4. 3.4 牛顿迭代法的特点
      1. 3.4.1. 是否收敛
      2. 3.4.2. 迭代速度
      3. 3.4.3. 优缺点
  4. 4. Reference

1. 逻辑回归

对于逻辑回归而言,y 的取值不是 0 就是 1,所以 $hθ(x)$ 可以写为
$$h
θ(x) = g(θ^{T}x)=\frac1{1+e^{-θ^{T}x}}$$

其中
$$g(z)=\frac1{1+e^{-z}}$$;

g(z) 被称为 logistic function 或 sigmoid function,其二维坐标下的曲线为:
sigmoid function

我们先取 g(z) 为 sigmoid function,如果有其他使得 y 值从 0 到 1 平滑递增的函数也可以使用。但由于一些列原因(在后续的一般化回归模型 GLM 中会谈到为什么选用这个函数),g(z) is a fairly natural one.

g(z) 的导数我们可以先进行推导:
$$g’(z)=\frac{d}{dz}\frac{1}{1+e^{-z}}= \frac{1}{(1+e^{-z})^2}(e^{-z})$$
$$= \frac{1}{1+e^{-z}}*(1 - \frac{1}{1+e^{-z}})= g(z)(1-g(z))$$

2. 梯度上升法求解逻辑回归

对于给定的逻辑回归函数,我们使用最小二乘法来推导出最大似然估计,假设:
$P(y=1|x;θ)=h_θ(x)$,代表对于给定的 θ,y 取值为 1 的概率。
$P(y=0|x;θ)=1-h_θ(x)$,代表对于给定的 θ,y 取值为 0 的概率。

以上两者可以合并为:
$$P(y|x;θ)=(h_θ(x))^y(1 − h_θ(x))^{(1−y)}$$

假设 m 个训练集是相互独立的,则似然估计为:
$$L(θ)=P(\overrightarrow{y}|X;θ)$$
$$= \prod^m_{i=1}P(y^i|x^i;θ)$$
$$= \prod^m_{i=1}{(h_θ(x^{(i)}))^{y^{(i)}}(1 − h_θ(x^{(i)}))^{(1−y^{(i)})}}$$

和之前一样,上式可以简化为:


$l(θ) = logL(θ)
= \sum_{m}^{i=1}{y^{(i)}}log{h(x^{(i)}) + {(1−y^{(i)})}log(1 − h(x^{(i)}))}$

那么,
如何去最大化似然函数呢,可以应用梯度上升法,因为我们要使 P 的取值足够大,也是就预测准确的概率最够大。

随机梯度上升的公式为:
$$θ:= θ + \alpha\Deltaθl(θ)$$

下面来求$\Deltaθl(θ)$的取值:

$$\frac\partial{\partial\theta_j}l(\theta)$$
$$= (y\frac1{g(\theta^Tx)} - (1-y)\frac1{1-g(\theta^Tx)})\frac\partial{\partial\theta_j}g(\theta^Tx)$$
$$= (y\frac1{g(\theta^Tx)} - (1-y)\frac1{1-g(\theta^Tx)}) g(\theta^Tx)(1-g(\theta^Tx))\frac\partial{\partial\theta_j}\theta^Tx$$
$$= ({y(1-g(\theta^Tx))-(1-y)g(\theta^Tx)})x_j$$
$$= (y - h_{\theta}(x))x_j$$

附上手写的推导过程:
手写推导过程

所以,最终随机梯度上升的公式为:
$$θ_j:=θ_j + \alpha\sum_{i=1}^{m}(y^{(i)} - h_{\theta}(x^{(i))})x_j^{(i)}$$

如何和线性回归的公式放在一起比较,

$$θ_j = θ_j - α \frac1m \sum_{i=1}^{m}{(h_θ(x^{(i)}) - y^{(i)})}x_j^{(i)}$$

会发现,这两者非常相似,实际上却不然,因为这里的 $(h_θ(x^{(i)})$ 定义的不是线性函数。后续我们谈到 GLM 时会发现这并不是巧合,而是有更深层次的原因。

3. 牛顿迭代法求解逻辑回归

牛顿迭代法可以利用到曲线本身的信息,比梯度下降法更容易收敛,即迭代更少次数。

3.1 牛顿迭代法简述

假设我们要求解方程 f(x)=0 的根,首先随便找一个初始值 x0,如果 x0 不是解,做一个经过 (x0,f(x0)) 这个点的切线,与 x 轴的交点为 x1。同样的道理,如果 x1 不是解,做一个经过 (x1,f(x1)) 这个点的切线,与 x 轴的交点为 x2。 以此类推。以这样的方式得到的 xi 会无限趋近于 f(x)=0 的解。

对于任意一点 $(x_n,y_n)$ 做切线,切线的斜率为 $f’(x_n)$,则有方程:
$$ y-f(x_n) = f’(x_n)(x-x_n) $$

3.2 迭代过程

求解 $f(\theta)$ = 0 时 $\theta$ 的取值。
设下一次迭代时 $\theta^{(t+1)}$ 的取值与前一次迭代 $\theta^{(t)}$ 的取值(在 x 轴)距离为 $\Delta$。

则 $\theta^{(t+1)} = \theta^{(t)} - \Delta$,且 $\Delta = \frac{f(\theta^{(t)})}{f’(\theta^{(t)})}$,
所以有:
$$\theta^{(t+1)} = \theta^{(t)} - \frac{f(\theta^{(t)})}{f’(\theta^{(t)})}$$

从泰勒展开到牛顿迭代

也可以由泰勒展开中推导牛顿迭代的公式。这次为了求解方程 f′=0 的根,把原函数 f(x) 的做泰勒展开,展开到二阶形式:
$$ f(x+\Delta x) = f(x)+f’(x)\Delta x+ \frac1{2}f’’(x)\Delta x^2 $$

当且仅当 $\Delta x$ 逼近 0 时,上式成立,此时忽略 1/2 系数的作用,所以有:
$$ f’(x)+ \frac1{2}f’’(x)\Delta x = 0 $$
故:
$$\Delta x = -\frac{f’(x)}{f’’(x)} $$

对函数求极大值的方法
>

  1. 将原函数y=f(x),对x求一次导数,得到dy/dx;
  2. 令dy/dx = 0,解得一次导函数的零点;
  3. 将原函数对x求二次导函数;
  4. 将解得的零点坐标的x值代入二次导函数,
    如果是正值,零点所在位置,就是极小值点,再将该x值代入原函数,得到极小值;
    如果是值值,零点所在位置,就是极大值点,再将该x值代入原函数,得到极大值;
    如果是0,零点所在位置,既不是极小值点,也不是极大值点,是拐点。

所以求 $l(\theta)$ 在极大值处 $\theta$ 的取值,则是求 $l’(\theta) = 0$ 时 $\theta$ 的值,应用牛顿迭代法则有:

$$\theta^{(t+1)} = \theta^{(t)} - \frac{l’(\theta^{(t)})}{l’’(\theta^{(t)})}$$

3.3 多维向量的牛顿迭代

对于多维向量 $\overrightarrow{X}$ 求解。
$$\theta := \theta - H^{-1} \nabla l(\theta)$$
其中
$\nabla l(\theta)$ 是对 $l(\theta)$ 求导的值。

H 是一个 n*n 的矩阵,n 是特征数量,元素的计算公式为:
$$H_ij= \frac{\partial^2{l({\theta)}}}{\partial{\theta_i}\partial{\theta_j}}$$

3.4 牛顿迭代法的特点

是否收敛

通常情况下是收敛的,但是需要满足一些条件,对于逻辑回归来讲,是收敛的。

迭代速度

每次迭代后,有解数字的误差是成平方倍减小的,是二次收敛函数。

优缺点

优点:收敛快
缺点:特征多(上千个)时,每次迭代成本大

Reference

http://blog.csdn.net/baimafujinji/article/details/51179381
http://blog.csdn.net/baimafujinji/article/details/51167852
如何通过牛顿方法解决Logistic回归问题

Contents
  1. 1. 1. 逻辑回归
  2. 2. 2. 梯度上升法求解逻辑回归
  3. 3. 3. 牛顿迭代法求解逻辑回归
    1. 3.1. 3.1 牛顿迭代法简述
    2. 3.2. 3.2 迭代过程
      1. 3.2.1. 从泰勒展开到牛顿迭代
    3. 3.3. 3.3 多维向量的牛顿迭代
    4. 3.4. 3.4 牛顿迭代法的特点
      1. 3.4.1. 是否收敛
      2. 3.4.2. 迭代速度
      3. 3.4.3. 优缺点
  4. 4. Reference