logistic回归与牛顿法

1. 梯度下降法的缺点

由于处理的数据有不同的量纲和量纲单位，导致不同维度的数据之间尺度差异很大，如下图（左）所示，目标函数的等高线是椭圆形的。这样在通过最小化目标函数寻找最优解的过程中，梯度下降法所走的路线是锯齿状的，需要经过的迭代次数过多，严重影响了算法的效率。
这里写图片描述
为了解决这个问题，可以对数据进行归一化，例如采用min-max标准化将输入数据范围统一到[0,1]之间：

x = x m i n m a x m i n

处理后的结果如上图（右）所示，经过很少次数的迭代就可以达到目标函数的最低点，极大提高算法的执行效率。

2. 牛顿法

数据归一化是从数据预处理的角度解决梯度下降法迭代次数过多这个问题的，若从目标函数优化的角度去思考，可以用牛顿法替代梯度下降法，从而提高参数最优值的求解速度。
有n个变量的函数J(θ)的一阶导数为：

J θ = [J θ 1, J θ 2, . . ., J θ n]

二阶导数（也称为Hessian矩阵）为：

目标函数J(θ)的包含二阶导数的泰勒展开式为：

J (θ + Δ θ) = J (θ) + Δ θ T J ( θ ) θ + 1 2 Δ θ T 2 J ( θ ) θ 2 Δ θ

将J(θ+Δθ)看做Δθ的函数的话，其最小值在其偏导数等于0处取得：

Δ θ = (2 J ( θ ) θ 2) 1 J ( θ ) θ = H (θ) 1 J ( θ ) θ

θ+Δθ是对目标函数取得最小值时参数的一个较好的估计，在牛顿法中会在Δθ的基础上乘以一个步长α（取值小于1，比如0.001）。使用牛顿法迭代过程为：

θ = θ + α Δ θ = θ α H (θ) 1 J ( θ ) θ

3. 牛顿法与梯度下降法的比较

使用梯度下降法参数迭代过程为：

θ = θ α J ( θ ) θ

对比这两中方法的参数更新公式可以发现，两种方法不同在于牛顿法中多了一项二阶导数，这项二阶导数对参数更新的影响主要体现在改变参数更新方向上。如下图所示，红色是牛顿法参数更新的方向，绿色为梯度下降法参数更新方向，因为牛顿法考虑了二阶导数，因而可以找到更优的参数更新方向，在每次更新的步幅相同的情况下，可以比梯度下降法节省很多的迭代次数。

4. logistic回归中使用牛顿法

由上节可知，logistic回归的目标函数为：

J (θ) = [1 m \sum i = 1 m (y i l n (h θ (x)) + (1 y i) l n (1 h θ (x)))] + 1 2 λ | | θ | | 2

暂时不考虑正则化项，推导的一阶导数公式：

J ( θ ) θ = 1 m X (h θ (X) y)

可推得二阶导数公式：

2 J ( θ ) θ 2 = H (θ) = 1 m X d i a g {(1 h θ (x)) h θ (x)} m, m X T

将正则化项考虑在内，完整的牛顿法的迭代过程表示为：

θ = θ α (H (θ) 1 J ( θ ) θ + λ θ)

python代码：

for i in xrange(0, num_passes):

        # newton's method
        Jprime = X_expand.T.dot(sigmoid(X_expand.dot(theta))-y.reshape(X.shape[0],1))
        for j in xrange(0, num_examples):
            H_theta = sigmoid(X_expand[j,:].dot(theta))
            A[j,j] = H_theta*(1-H_theta) + 0.0001
        Jprime2 = X_expand.T.dot(A).dot(X_expand)
        delta_theta = np.linalg.solve(Jprime2,Jprime)
        delta_theta += reg_lambda*theta

        # newton's method parameter update
        theta += -alpha*delta_theta

    return theta

给定下面类别数为2，包含200个样本的数据库：

使用sklearn.linear_model.LogisticRegressionCV()得到的训练结果如下图（左）所示，本文牛顿法的实验结果如下图（右）所示：
这里写图片描述
上节logistic回归中使用批量梯度下降法迭代10000次左右可以得到较小的分类误差。本节使用牛顿法在使用相同参数的情况下，仅需要迭代500次左右即可以得到接近批量梯度下降法分类误差的结果，极大降低了参数迭代的次数，从而提高了参数求解效率。

logistic回归与牛顿法

1. 梯度下降法的缺点

2. 牛顿法

3. 牛顿法与梯度下降法的比较

4. logistic回归中使用牛顿法

浏览过的版块