我的人工智能之旅——梯度下降vs正规方程法

迷南。 2022-05-19 05:10 149阅读 0赞

本文将涉及以下知识点

（1）特征缩放

（2）均值归一化

（3）正规方程

# 优化梯度下降算法 #

在上一篇博文中，我们了解了梯度下降算法，它为解决线性回归问题提供了思路。但梯度下降的迭代推算过程，较为耗时。简单地说，整个算法是一个不断尝试收敛的过程。如果能够降低算法的尝试次数，以及每次迭代的算法复杂度，那么，便能更高效的解决线性回归问题。

影响梯度下降算法收敛速度的因素很多，例如样本集合大小，特种向量中某一元素的取值范围远大于其它元素，学习速率等。

样本集合越大，算法推算出的假设函数越精确。因此，不能通过减少样本来提高算法的运算速度，这将付出降低精确度的代价。

所以，只能在其它干扰因素上找突破口。

## 特征缩放 ##

还以房价预估为例，假设特征向量由面积![x\_1][x_1]，楼层![x\_2][x_2]，房龄![x\_3][x_3]，房间数量![x\_4][x_4]组成。取值范围依次为，面积![x\_1][x_1]：30~200![m^2][m_2]，楼层![x\_2][x_2]：1～35层，房龄![x\_3][x_3]：1～70年，房间数量![x\_4][x_4]：1～6间。由于面积![x\_1][x_1]的取值范围较其三者都大，因此，在相同学习速率下，对面积![x\_1][x_1]做偏导数的次数远高于其它三者。同样的问题，对于楼层![x\_2][x_2]和房龄![x\_3][x_3]也存在。

为了使得迭代次数（求偏导数的次数）更加均衡，提出了特征缩放（feature scaling）的概念。即，用![\\frac\{x\_i\}\{x\_i\_\{max\}-x\_i\_\{min\}\}][frac_x_i_x_i_max_-x_i_min]替代原有![x\_i][x_i]。

在特征缩放的过程中，为了让特征的取值范围更加规范化，即规定在-0.5～0.5内，进而提出了均值归一化（mean normalization）的概念，即用![\\frac\{x\_i-\\bar\{x\}\}\{x\_i\_\{max\}-x\_i\_\{min\}\}][frac_x_i-_bar_x_x_i_max_-x_i_min]替代![\\frac\{x\_i\}\{x\_i\_\{max\}-x\_i\_\{min\}\}][frac_x_i_x_i_max_-x_i_min]。

## 学习率 ##

在代价函数中，学习率也是一个重要的参数。学习率的大小，影响迭代幅度。学习率偏小时，迭代次数多。学习率偏大时，迭代次数少，但有可能造成不收敛的情况。那么如何选择一个合适的学习率呢？其实，也是通过多次尝试获取最佳学习率。

通常，我们选定一个学习率后，会画出代价函数![J(A^T)][J_A_T]与迭代次数n的关系图。一个较为合适的学习率，对应的代价函数与迭代次数的关系图应该是收敛的。如下图。

![70][]

若所画关系图未出现收敛，则说明学习率偏大。可以在保证收敛的前提下，尽量提升学习率，以减少迭代次数。

综上，虽然可以通过运用特征缩放和调节学习率的方式，提高梯度下降方法的收敛速度。但梯度下降方法还是摆脱不了“迭代”、“尝试”的口实。那么有没有方法，可以一次性得到代价函数的最小值呢？

# 正规方程法 #

我们还是以房价预估为例。![x\_0][x_0]默认为1，![x\_1,x\_2,x\_3][x_1_x_2_x_3]分别代表楼层，房龄，房间数量。房价为y，且假设房价与特征向量间存在线性关系，![a\_0+a\_1x\_1+a\_2x\_2+a\_3x\_3=y][a_0_a_1x_1_a_2x_2_a_3x_3_y]。

若，样本集合大小为m，则

![\\begin\{bmatrix\} 1&x\_1\_1&x\_1\_2&x\_1\_3\\\\ 1&x\_2\_1&x\_2\_2&x\_2\_3\\\\ ..&..&..&..\\\\ 1&x\_m\_1&x\_m\_2&x\_m\_3 \\end\{bmatrix\} \\begin\{bmatrix\} a\_0\\\\ a\_1\\\\ a\_2\\\\ a\_3 \\end\{bmatrix\} =\\begin\{bmatrix\} y\_1\\\\ y\_2\\\\ ..\\\\ y\_m\\\\ \\end\{bmatrix\}][begin_bmatrix_ 1_x_1_1_x_1_2_x_1_3_ 1_x_2_1_x_2_2_x_2_3_ .._.._.._.._ 1_x_m_1_x_m_2_x_m_3 _end_bmatrix_ _begin_bmatrix_ a_0_ a_1_ a_2_ a_3 _end_bmatrix_ _begin_bmatrix_ y_1_ y_2_ .._ y_m_ _end_bmatrix]

设![X=\\begin\{bmatrix\} 1&x\_1\_1&x\_1\_2&x\_1\_3\\\\ 1&x\_2\_1&x\_2\_2&x\_2\_3\\\\ ..&..&..&..\\\\ 1&x\_m\_1&x\_m\_2&x\_m\_3 \\end\{bmatrix\}][X_begin_bmatrix_ 1_x_1_1_x_1_2_x_1_3_ 1_x_2_1_x_2_2_x_2_3_ .._.._.._.._ 1_x_m_1_x_m_2_x_m_3 _end_bmatrix]，![A=\\begin\{bmatrix\} a\_0\\\\ a\_1\\\\ a\_2\\\\ a\_3 \\end\{bmatrix\}][A_begin_bmatrix_ a_0_ a_1_ a_2_ a_3 _end_bmatrix]，![Y=\\begin\{bmatrix\} y\_1\\\\ y\_2\\\\ ..\\\\ y\_m\\\\ \\end\{bmatrix\}][Y_begin_bmatrix_ y_1_ y_2_ .._ y_m_ _end_bmatrix]，

则![XA=Y][XA_Y]，

![X^\{T\}XA=X^\{T\}Y][X_T_XA_X_T_Y]

此时，![X^\{T\}X][X_T_X]为方阵，存在逆矩阵（注：也可能不存在，但MATLAB或OCTAVE会算出伪逆矩阵，因此，此处暂时认为，方阵都存在逆矩阵）。

因此，![(X^\{T\}X)^\{-1\}X^\{T\}XA=(X^\{T\}X)^\{-1\}X^\{T\}Y][X_T_X_-1_X_T_XA_X_T_X_-1_X_T_Y]

![EA=(X^\{T\}X)^\{-1\}X^\{T\}Y][EA_X_T_X_-1_X_T_Y]，其中E为单位矩阵

因此，![A=(X^\{T\}X)^\{-1\}X^\{T\}Y][A_X_T_X_-1_X_T_Y]。

有了这个推算结果，我们可以在MATLAB或OCTAVE中调用算法，得出相应的A。

# 对比与选择 #

与梯度下降算法相比，正规方程法不需要选择学习率，不需要迭代，更不需要画代价函数![J(A^T)][J_A_T]与迭代次数n的关系图，证明学习率对于收敛的影响。这使得正规方程法似乎有着压倒性的优势。但正规方程法，也存在缺陷。

当特征向量中的特征数量较大时（即X的列数n较大时），正规方程的时间复杂度为![O(n^3)][O_n_3]，因此，会非常耗时，速度不一定比梯度下降快。那么n多大算大呢？推荐值为10000，但仁者见仁，还得看硬件性能。

[x_1]: https://private.codecogs.com/gif.latex?x_1
[x_2]: https://private.codecogs.com/gif.latex?x_2
[x_3]: https://private.codecogs.com/gif.latex?x_3
[x_4]: https://private.codecogs.com/gif.latex?x_4
[m_2]: https://private.codecogs.com/gif.latex?m%5E2
[frac_x_i_x_i_max_-x_i_min]: https://private.codecogs.com/gif.latex?%5Cfrac%7Bx_i%7D%7Bx_i_%7Bmax%7D-x_i_%7Bmin%7D%7D
[x_i]: https://private.codecogs.com/gif.latex?x_i
[frac_x_i-_bar_x_x_i_max_-x_i_min]: https://private.codecogs.com/gif.latex?%5Cfrac%7Bx_i-%5Cbar%7Bx%7D%7D%7Bx_i_%7Bmax%7D-x_i_%7Bmin%7D%7D
[J_A_T]: https://private.codecogs.com/gif.latex?J%28A%5ET%29
[70]: /images/20220519/9e43cbadfd884493b1b36916b4fd011f.png
[x_0]: https://private.codecogs.com/gif.latex?x_0
[x_1_x_2_x_3]: https://private.codecogs.com/gif.latex?x_1%2Cx_2%2Cx_3
[a_0_a_1x_1_a_2x_2_a_3x_3_y]: https://private.codecogs.com/gif.latex?a_0&plus;a_1x_1&plus;a_2x_2&plus;a_3x_3%3Dy
[begin_bmatrix_ 1_x_1_1_x_1_2_x_1_3_ 1_x_2_1_x_2_2_x_2_3_ .._.._.._.._ 1_x_m_1_x_m_2_x_m_3 _end_bmatrix_ _begin_bmatrix_ a_0_ a_1_ a_2_ a_3 _end_bmatrix_ _begin_bmatrix_ y_1_ y_2_ .._ y_m_ _end_bmatrix]: https://private.codecogs.com/gif.latex?%5Cbegin%7Bbmatrix%7D%201%26x_1_1%26x_1_2%26x_1_3%5C%5C%201%26x_2_1%26x_2_2%26x_2_3%5C%5C%20..%26..%26..%26..%5C%5C%201%26x_m_1%26x_m_2%26x_m_3%20%5Cend%7Bbmatrix%7D%20%5Cbegin%7Bbmatrix%7D%20a_0%5C%5C%20a_1%5C%5C%20a_2%5C%5C%20a_3%20%5Cend%7Bbmatrix%7D%20%3D%5Cbegin%7Bbmatrix%7D%20y_1%5C%5C%20y_2%5C%5C%20..%5C%5C%20y_m%5C%5C%20%5Cend%7Bbmatrix%7D
[X_begin_bmatrix_ 1_x_1_1_x_1_2_x_1_3_ 1_x_2_1_x_2_2_x_2_3_ .._.._.._.._ 1_x_m_1_x_m_2_x_m_3 _end_bmatrix]: https://private.codecogs.com/gif.latex?X%3D%5Cbegin%7Bbmatrix%7D%201%26x_1_1%26x_1_2%26x_1_3%5C%5C%201%26x_2_1%26x_2_2%26x_2_3%5C%5C%20..%26..%26..%26..%5C%5C%201%26x_m_1%26x_m_2%26x_m_3%20%5Cend%7Bbmatrix%7D
[A_begin_bmatrix_ a_0_ a_1_ a_2_ a_3 _end_bmatrix]: https://private.codecogs.com/gif.latex?A%3D%5Cbegin%7Bbmatrix%7D%20a_0%5C%5C%20a_1%5C%5C%20a_2%5C%5C%20a_3%20%5Cend%7Bbmatrix%7D
[Y_begin_bmatrix_ y_1_ y_2_ .._ y_m_ _end_bmatrix]: https://private.codecogs.com/gif.latex?Y%3D%5Cbegin%7Bbmatrix%7D%20y_1%5C%5C%20y_2%5C%5C%20..%5C%5C%20y_m%5C%5C%20%5Cend%7Bbmatrix%7D
[XA_Y]: https://private.codecogs.com/gif.latex?XA%3DY
[X_T_XA_X_T_Y]: https://private.codecogs.com/gif.latex?X%5E%7BT%7DXA%3DX%5E%7BT%7DY
[X_T_X]: https://private.codecogs.com/gif.latex?X%5E%7BT%7DX
[X_T_X_-1_X_T_XA_X_T_X_-1_X_T_Y]: https://private.codecogs.com/gif.latex?%28X%5E%7BT%7DX%29%5E%7B-1%7DX%5E%7BT%7DXA%3D%28X%5E%7BT%7DX%29%5E%7B-1%7DX%5E%7BT%7DY
[EA_X_T_X_-1_X_T_Y]: https://private.codecogs.com/gif.latex?EA%3D%28X%5E%7BT%7DX%29%5E%7B-1%7DX%5E%7BT%7DY
[A_X_T_X_-1_X_T_Y]: https://private.codecogs.com/gif.latex?A%3D%28X%5E%7BT%7DX%29%5E%7B-1%7DX%5E%7BT%7DY
[O_n_3]: https://private.codecogs.com/gif.latex?O%28n%5E3%29