🔥作者：FrigidWinter

🔥简介：主攻机器人与人工智能领域的理论研究和工程应用，业余丰富各种技术栈。主要涉足：【机器人(ROS)】【机器学习】【深度学习】【计算机视觉】

🔥专栏：

• 《机器人原理与技术》
• 计算机视觉教程
• “机器学习”
• “嵌入式系统”
• …

内容

• 1 引例
• 2 牛顿迭代算法求根
• 3 牛顿迭代优化
• 4 代码实战：Logistic回归

1 引例

给定如图所示的某个函数，如何计算函数零？

我们如何在数学上解决这个问题？

最简单的方法是解方程，还有代数中著名的零点确定定理

如果函数在区间上的图像是一条连续曲线，并且有，那么函数在区间内有零点，即至少有一个，所以，这个也是等式的根。

然而，数学方法不一定适用于工程应用。当函数形式很复杂时，例如超越函数形式；当非解析形式，如递推关系，一般难以进行精确的方程分析，因为代数还没有发展出任意形式的A求根公式。零点确定定理的求解效率也较低，需要不断试错。

因此，今天的话题——牛顿迭代法被引入为工程数值计算服务。

2 牛顿迭代算法求根

轮迭代后，自变量更新为，目标函数在Taylor中展开：

我们希望下一次迭代到根，忽略泰勒余数，让，然后

可以通过不断重复操作来接近根点。

从几何上看，上述过程实际上就是在处做处的切线，并找到切线的零点，工程上称为局部线性化。如图所示，如果在的左边，那么下一个迭代方向就是右边。

如果在的右侧，那么下一次迭代的方向是向左。

3 牛顿迭代优化

要将优化问题转化为寻找目标函数一阶导数零点的问题，可以使用上面提到的牛顿迭代法。

具体来说，经过轮的迭代，自变量更新为，目标函数在Taylor中展开：

两边推导

让，这样我们得到

对于向量，将上述迭代公式推广为

其中是Hessian矩阵，当其正定时可以保证牛顿优化算法往 减小的方向迭代

牛顿法的特点如下：

①以二阶速率收敛到最优点，迭代次数远小于梯度下降法，优化速度快；

梯度下降法的解析参考图文详解神秘的梯度下降算法原理(附Python代码)

②学习率为，包含更多关于函数本身的信息，迭代步长可以自动调整，可视为自适应梯度下降算法；

③ 耗费CPU计算资源多，每次迭代需要计算一次Hessian矩阵，且无法保证Hessian矩阵可逆且正定，因而无法保证一定向最优点收敛。

在实际应用中，牛顿迭代法一般不能直接使用，会引入改进来规避其缺陷，称为拟牛顿算法簇，其中包含大量不同的算法变种，例如共轭梯度法、DFP算法等等，今后都会介绍到。

4 代码实战：Logistic回归

import pandas as pd
import numpy as np
import os
import matplotlib.pyplot as plt
import matplotlib as mpl
from Logit import Logit

'''
* @breif: 从CSV中加载指定数据
* @param[in]: file -> 文件名
* @param[in]: colName -> 要加载的列名
* @param[in]: mode -> 加载模式, set: 列名与该列数据组成的字典, df: df类型
* @retval: mode模式下的返回值
'''
def loadCsvData(file, colName, mode='df'):
    assert mode in ('set', 'df')
    df = pd.read_csv(file, encoding='utf-8-sig', usecols=colName)
    if mode == 'df':
        return df
    if mode == 'set':
        res = {}
        for col in colName:
            res[col] = df[col].values
        return res

if __name__ == '__main__':
    # ============================
    # 读取CSV数据
    # ============================
    csvPath = os.path.abspath(os.path.join(__file__, "../../data/dataset3.0alpha.csv"))
    dataX = loadCsvData(csvPath, ["含糖率", "密度"], 'df')
    dataY = loadCsvData(csvPath, ["好瓜"], 'df')
    label = np.array([
        1 if i == "是" else 0
        for i in list(map(lambda s: s.strip(), list(dataY['好瓜'])))
    ])

    # ============================
    # 绘制样本点
    # ============================
    line_x = np.array([np.min(dataX['密度']), np.max(dataX['密度'])])
    mpl.rcParams['font.sans-serif'] = [u'SimHei']
    plt.title('对数几率回归模拟\nLogistic Regression Simulation')
    plt.xlabel('density')
    plt.ylabel('sugarRate')
    plt.scatter(dataX['密度'][label==0],
                dataX['含糖率'][label==0],
                marker='^',
                color='k',
                s=100,
                label='坏瓜')
    plt.scatter(dataX['密度'][label==1],
                dataX['含糖率'][label==1],
                marker='^',
                color='r',
                s=100,
                label='好瓜')

    # ============================
    # 实例化对数几率回归模型
    # ============================
    logit = Logit(dataX, label)

    # 采用牛顿迭代法
    logit.logitRegression(logit.newtomMethod)
    line_y = -logit.w[0, 0] / logit.w[1, 0] * line_x - logit.w[2, 0] / logit.w[1, 0]
    plt.plot(line_x, line_y, 'g-', label="牛顿迭代法")

    # 绘图
    plt.legend(loc='upper left')
    plt.show()

更新权重代码为

    '''
    * @breif: 牛顿迭代法更新权重
    * @param[in]: None
    * @retval: 优化参数的增量dw
    '''
    def newtomMethod(self):
        wTx = np.dot(self.w.T, self.X).reshape(-1, 1)
        p = Logit.sigmod(wTx)
        dw_1 = -self.X.dot(self.y - p)
        dw_2 = self.X.dot(np.diag((p * (1 - p)).reshape(self.N))).dot(self.X.T)
        dw = np.linalg.inv(dw_2).dot(dw_1)
        return dw