2.5 梯度下降和最小二乘法

本节笔记主要记录梯度下降算法和最小二乘法的相同点和不同点，为了简单的理解和推导，我们暂只讨论一元线性回归下的梯度下降算法和最小二乘。从实现++代码上的最大不同就是梯度下降采用了迭代算法---预先给一个参数设置初始值，然后通过迭代和学习率实现线性方程直线的无限靠近理想函数。最小二乘采用了高中数学求凸函数（下凹）的最小值---即求导数为零的参数方程。

• Edit By Porter, 积水成渊,蛟龙生焉。

梯度下降和最小二乘发的相同点和不同点如下：

第一部分、最小二乘法

1.1 狭义的最小二乘法：

指的是在线性回归下采用最小二乘准则（或者说叫做最小平方），进行线性拟合参数求解的、矩阵形式的公式方法，是线性假设下的一种有闭式解的参数求解方法，最终结果为全局最优；

1.2 广义的最小二乘法：

是最小二乘准则，本质上是一种evaluation rule或者说objective funcion。是一种对于偏差程度的评估准则。

• 梯度下降法，是假设条件更为广泛（无约束）的，一种通过迭代更新来逐步进行的参数优化方法，最终结果为局部最优；

1.3 最小二乘与极大似然的区别

• 二乘法：即观测值与实际数据误差平方和最小，其没有假设，几何意义上就是距离最小

• 最大似然估计：估计参数可能值，使样本发生概率最大

1.4 对于回归问题，两者对于最优参数的不同解法

假设一元回归方程为

$$f(x_i)=\omega x_i +b$$

实际中我们会采样得到关于[x,y]的很多样本，此时我们会通过损失函数loss，来求最优$\omega , b$的最优解。

$$loss = (\omega x + b -y)^2$$

假设$E(\omega, b)=loss(\omega, b)$,于是：

为求得最优的$\omega ， b$,即求解$E(\omega, b)=\sum{i=1}^{m} (y_i - \omega x_i -b)^2$的最小取值下的$\omega ， b$ 最优解。

• 注意此时的$E_(\omega, b)$是一个凸函数，注意也就是对应国内教材下凹函数曲线。

1.5 最小二乘法的求解最优的$\omega ， b$的方法

直接通过对$E_(\omega, b)$ 对$\omega ， b$ 分别求偏导，并将偏导设为0，求取凸函数取得最小值下的对应$\omega ， b$ 参数。

1.6 最小二乘法的局限性和适用场景

从上面可以看出，最小二乘法适用简洁高效，比梯度下降这样的迭代法似乎方便很多。但是这里我们就聊聊最小二乘法的局限性。

首先，最小二乘法需要计算的逆矩阵，有可能它的逆矩阵不存在，这样就没有办法直接用最小二乘法了，此时梯度下降法仍然可以使用。当然，我们可以通过对样本数据进行整理，去掉冗余特征。让的行列式不为0，然后继续使用最小二乘法。

第二，当样本特征n非常的大的时候，计算的逆矩阵是一个非常耗时的工作（nxn的矩阵求逆），甚至不可行。此时以梯度下降为代表的迭代法仍然可以使用。那这个n到底多大就不适合最小二乘法呢？如果你没有很多的分布式大数据计算资源，建议超过10000个特征就用迭代法吧。或者通过主成分分析降低特征的维度后再用最小二乘法。

第三，如果拟合函数不是线性的，这时无法使用最小二乘法，需要通过一些技巧转化为线性才能使用，此时梯度下降仍然可以用。

第四，讲一些特殊情况。当样本量m很少，小于特征数n的时候，这时拟合方程是欠定的，常用的优化方法都无法去拟合数据。当样本量m等于特征说n的时候，用方程组求解就可以了。当m大于n时，拟合方程是超定的，也就是我们常用与最小二乘法的场景了。

原文地址：http://www.cnblogs.com/pinard/p/5976811.html

第二部分、梯度下降算法

2.1 梯度下降算法的求解最优的$\omega ， b$的方法

同样，梯度下降算法也是要求最小损失函数

$$loss = (\omega x + b -y)^2$$

但是方法不一样了，梯度下降算法，在上面的基础上设定一个学习率的参数，假设为:$lr$

对于待求解的参数$\omega ， b$ 则转化为 --> 求最终待求的$\omega ' ， b'$ 关于前一时刻的$\omega ， b$ 的函数，如下

$$\frac{\bigtriangledown loss}{\bigtriangledown \omega} = \frac{2(\omega x+b-y)*x}{N}$$

$$\frac{\bigtriangledown loss}{\bigtriangledown b} = \frac{2(\omega x+b-y)}{N}$$

2.2 梯度下降算法的算法核心公式

对于$\omega$和$b$ , 算法的核心在于如何更新这两个参数，这两个参数的更新不是能用公式可以简单的推到的，但是可以用下面的举例进行理解

$\omega$和$b$ 参数更新的理解，首先我们需要的是最小化这个loss代价函数，这个代价函数是一个下凸函数，所以我们按照凸函数的特点来理解，类似于一个山，人闭着眼往山下走小碎步(这个小碎步就是学习率乘梯度，如下公式)

$lr * \frac{\bigtriangledown loss}{\bigtriangledown \omega}$

我们要求解的是，找这个loss的局部最优解，由于我们是针对线性一元的，所以loss是只有一个极小值点，也就是局部解就是最优解，所以接下来理解。

人要走到山下，那么问题来了，我怎么怎么确保我们一直是朝向山谷走的呢，(比如人走在山谷的左边,应该接着忘右边走，才能到达山谷；又如，我们走超了，小碎步跨大了，跨到山谷的左边去了，我们应该要要朝山谷的左边走才能到山谷)，这里就需要个方向，这个在局部最优点的左边还是右边的方向由$\frac{\bigtriangledown loss}{\bigtriangledown \omega}$ 确定。

第三个问题是，人走小碎步时，要的方向是朝着局部最优点(山谷)走的,即loss数值(代价函数)减少的方向，所以我们要在小碎步前乘以负数，来确保，取(点，人)在(山)左边时(左边时梯度=斜率，就是loss的导数为负数,负数乘以负数，就为正数)我们要确保我们需要预测的$\omega , b$所确定的

$f(x; \omega , b)= \omega * x+b$

接近原数据y,所以对于价值函数，人在左边时 $\omega$, 我们要确保人是往loss梯度下降(loss减少)的方向移动, 此时$\omega$ 就可以看作走碎步的人，方向都已确定

$-lr * \frac{\bigtriangledown loss}{\bigtriangledown \omega}$

,现在就是在前一步$\omega{0}$ 的基础上，走下一步得到 $\omega{1}$即有

$$\omega_{1} = \omega_{0}+(-lr*\frac{\bigtriangledown loss}{\bigtriangledown \omega})$$

进一步简化为

$\omega '=\omega - lr * \frac{\bigtriangledown loss}{\bigtriangledown \omega}$

同理：

人，走碎步(小碎步的步长是$- lr * \frac{\bigtriangledown loss}{\bigtriangledown b}$)，上一步是b, 方向是$\frac{\bigtriangledown loss}{\bigtriangledown \omega}$ ,走到的下一步就是$b^{'}$ ,即得到

$b '=b - lr * \frac{\bigtriangledown loss}{\bigtriangledown b}$

• 根据上面的式子，假设学习率lr的初始值为0，然后通过for循环进行迭代，此时求解的关于$\omega ， b$ 的曲线会随着迭代的次数增加，一步步无限的靠近最优的解，理论上会求解到最优的$\omega ， b$ 。

这里我相信题主对梯度下降法的整体理念是认可的，只是不清楚这个更新公式的实质含义。首先这个梯度更新公式确实不是推导而是创造出来的，所以只能从概念上去理解。设想下有个函数，你的目标是：找到一个参数 使得它的值 最小。但它很复杂，你无法找到这个参数的解析解，所以你希望通过梯度下降法去猜这个参数。 问题是怎么猜？对于多数有连续性的函数来说，显然不可能把每个 都试一遍。所以只能先随机取一个 ，然后看看怎么调整它最有可能使得 变小。把这个过程重复n遍，自然最后得到的 的估值会越来越小。

作者：老董 链接：https://www.zhihu.com/question/57747902/answer/240695458 来源：知乎

针对上面的一元回归梯度下降算法的代码实现，如下：

import numpy as np


# y = wx + b
def compute_error_for_line_given_points(b, w, points):
    totalError = 0
    for i in range(0, len(points)):
        x = points[i, 0]
        y = points[i, 1]
        totalError += (y - (w * x + b)) ** 2
    return totalError / float(len(points))


def step_gradient(b_current, w_current, points, learningRate):
    b_gradient = 0
    w_gradient = 0
    N = float(len(points))
    for i in range(0, len(points)):
        x = points[i, 0]
        y = points[i, 1]
        b_gradient += -(2/N) * (y - ((w_current * x) + b_current))
        w_gradient += -(2/N) * x * (y - ((w_current * x) + b_current))
    new_b = b_current - (learningRate * b_gradient)
    new_m = w_current - (learningRate * w_gradient)
    return [new_b, new_m]


def gradient_descent_runner(points, starting_b, starting_m, learning_rate, num_iterations):
    b = starting_b
    m = starting_m
    for i in range(num_iterations):
        b, m = step_gradient(b, m, np.array(points), learning_rate)
    return [b, m]


def run():
    points = np.genfromtxt("data.csv", delimiter=",")
    learning_rate = 0.0001
    initial_b = 0 # initial y-intercept guess
    initial_m = 0 # initial slope guess
    num_iterations = 1000
    print("Starting gradient descent at b = {0}, m = {1}, error = {2}"
          .format(initial_b, initial_m,
                  compute_error_for_line_given_points(initial_b, initial_m, points))
          )
    print("Running...")
    [b, m] = gradient_descent_runner(points, initial_b, initial_m, learning_rate, num_iterations)
    print("After {0} iterations b = {1}, m = {2}, error = {3}".
          format(num_iterations, b, m,
                 compute_error_for_line_given_points(b, m, points))
          )


if __name__ == '__main__':
    run()

对应的数据集如下(data.csv)：

32.502345269453031,31.70700584656992
53.426804033275019,68.77759598163891
61.530358025636438,62.562382297945803
47.475639634786098,71.546632233567777
59.813207869512318,87.230925133687393
55.142188413943821,78.211518270799232
52.211796692214001,79.64197304980874
39.299566694317065,59.171489321869508
48.10504169176825,75.331242297063056
52.550014442733818,71.300879886850353
45.419730144973755,55.165677145959123
54.351634881228918,82.478846757497919
44.164049496773352,62.008923245725825
58.16847071685779,75.392870425994957
56.727208057096611,81.43619215887864
48.955888566093719,60.723602440673965
44.687196231480904,82.892503731453715
60.297326851333466,97.379896862166078
45.618643772955828,48.847153317355072
38.816817537445637,56.877213186268506
66.189816606752601,83.878564664602763
65.41605174513407,118.59121730252249
47.48120860786787,57.251819462268969
41.57564261748702,51.391744079832307
51.84518690563943,75.380651665312357
59.370822011089523,74.765564032151374
57.31000343834809,95.455052922574737
63.615561251453308,95.229366017555307
46.737619407976972,79.052406169565586
50.556760148547767,83.432071421323712
52.223996085553047,63.358790317497878
35.567830047746632,41.412885303700563
42.436476944055642,76.617341280074044
58.16454011019286,96.769566426108199
57.504447615341789,74.084130116602523
45.440530725319981,66.588144414228594
61.89622268029126,77.768482417793024
33.093831736163963,50.719588912312084
36.436009511386871,62.124570818071781
37.675654860850742,60.810246649902211
44.555608383275356,52.682983366387781
43.318282631865721,58.569824717692867
50.073145632289034,82.905981485070512
43.870612645218372,61.424709804339123
62.997480747553091,115.24415280079529
32.669043763467187,45.570588823376085
40.166899008703702,54.084054796223612
53.575077531673656,87.994452758110413
33.864214971778239,52.725494375900425
64.707138666121296,93.576118692658241
38.119824026822805,80.166275447370964
44.502538064645101,65.101711570560326
40.599538384552318,65.562301260400375
41.720676356341293,65.280886920822823
51.088634678336796,73.434641546324301
55.078095904923202,71.13972785861894
41.377726534895203,79.102829683549857
62.494697427269791,86.520538440347153
49.203887540826003,84.742697807826218
41.102685187349664,59.358850248624933
41.182016105169822,61.684037524833627
50.186389494880601,69.847604158249183
52.378446219236217,86.098291205774103
50.135485486286122,59.108839267699643
33.644706006191782,69.89968164362763
39.557901222906828,44.862490711164398
56.130388816875467,85.498067778840223
57.362052133238237,95.536686846467219
60.269214393997906,70.251934419771587
35.678093889410732,52.721734964774988
31.588116998132829,50.392670135079896
53.66093226167304,63.642398775657753
46.682228649471917,72.247251068662365
43.107820219102464,57.812512976181402
70.34607561504933,104.25710158543822
44.492855880854073,86.642020318822006
57.50453330326841,91.486778000110135
36.930076609191808,55.231660886212836
55.805733357942742,79.550436678507609
38.954769073377065,44.847124242467601
56.901214702247074,80.207523139682763
56.868900661384046,83.14274979204346
34.33312470421609,55.723489260543914
59.04974121466681,77.634182511677864
57.788223993230673,99.051414841748269
54.282328705967409,79.120646274680027
51.088719898979143,69.588897851118475
50.282836348230731,69.510503311494389
44.211741752090113,73.687564318317285
38.005488008060688,61.366904537240131
32.940479942618296,67.170655768995118
53.691639571070056,85.668203145001542
68.76573426962166,114.85387123391394
46.230966498310252,90.123572069967423
68.319360818255362,97.919821035242848
50.030174340312143,81.536990783015028
49.239765342753763,72.111832469615663
50.039575939875988,85.232007342325673
48.149858891028863,66.224957888054632
25.128484647772304,53.454394214850524

总结

以上就是关于简单的一元回归的关于梯度下降和最小二乘的区别，对于代码中，的迭代的实现下一小节中会有详细的介绍，会通过代码来直观例说迭代算法和递归算法的差异和原理。

无聊时刻看部综艺：