Stanford Machine Learning - 4 逻辑回归

逻辑回归

对于逻辑回归而言，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，其二维坐标下的曲线为:  我们先取 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))$$

梯度上升法求解逻辑回归

对于给定的逻辑回归函数，我们使用最小二乘法来推导出最大似然估计，假设:
$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 时会发现这并不是巧合，而是有更深层次的原因。

牛顿迭代法求解逻辑回归

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

牛顿迭代法简述

假设我们要求解方程 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)$$

迭代过程

求解 $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)})}$$

多维向量的牛顿迭代

对于多维向量 $\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}}$$

牛顿迭代法的特点

是否收敛

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

迭代速度

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

优缺点

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

Reference

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