机器学习 | 数学理论：迭代法统一论 | Gavin Liu

迭代法，其实是计算机软件中很常用的方法，机器学习中的工程运用也用到了迭代法，这篇学习笔记主要是理清 梯度下降法 的背后的数学基本原理。

必备的数学知识

导数和梯度

多元函数求导，实际上就是梯度。

一阶导数和梯度

例：
f(x) = x^2 -> f’(x) = 2
Z = x^2 + y^2 求梯度就等于 Z’ = [2x, 2y]

注：一元函数求导数 f'(x)，在多元函数就是对每个变量求偏导，然后写成列向量。梯度都是向量的形式。

二阶导数和 Hessian 矩阵

例：
Z’ = [2x, 2y] 求 Z’’
可以看成 2x ， 2y 是个独立的函数，再分别求偏导。
(2x)’ > [2, 0] ; (2y)’ > [0, 2]
最终等于一个矩阵：
| 2, 0 |
| 0, 2 |

这个矩阵就叫 Hessian 矩阵，它是一个对称矩阵。

二次型

f(x) = x1^2 + x2^2 + x3^2 的二次型为：

1
2
3

             [1, 0, 0] [x1]
[x1, x2, x3] [0, 1, 0] [x2]
             [0, 0, 0] [x3]

二次型的通俗意义就是判定举证的正负。

例如 x√2x | x != 0，那么就肯定大于 0 的，同理：xTAx。

最小二乘

||Ax - b||^2

其实就是二范数的平方。

泰勒级数展开

一元的情况

1	f(xk + δ) ≈ f(xk) + f'(xk)δ + f''(xk)δ^2/2!

向量的情况

1
2
3

f(xk + δ) ≈ f(xk) + f'(xk)δ + f''(xk)δ^2/2!
f(xk + δ) ≈ f(xk) + gT(xk)δ + gTH(xk)δ^2/2!
因为二阶导数其实就是 Hessian 矩阵

极值

其实就是要让 f(xk + δ) > f(xk)，进一步推导

f(xk) + f’(xk)δ > f(xk) 其实就是要 f’(xk)δ >= 0

向量的情况的话就是：

1	f(xk + δ) ≈ f(xk) + gT(xk)δ + gTH(xk)δ^2/2!

让 梯度 = 0，然后 Hessian 矩阵 > 0，这个时候就是最小值

用一元情况举例

1	y = x^2 极值就是让 y' = 2x = 0 那么就是 x=0 的时候。

迭代法

计数 k = 0
寻求搜索方向 dk
f(xk + ak*dk) ak >= 0, X(k+1) = Xk + ak + dK
如果 ||dk|| < s，就停止搜索，解出 X(k+1)，否则 loop 步骤 2 。

其中 s 是根据经验得出来的一个比较小的值，10e－5 之类的。

dk 如何取值？

梯度下降法

dk = -g(xk)

1	f(xk + dk) ≈ f(xk) + gT(xk)*dk

要让 f(xk + dk) > f(xk) , 那么就是要让 gT(xk)*dk 为负数，且为最大负数。那么 dk 就应该等于 -g(xk)

向量夹角，a * b = aTb = |a||b|cos(θ)

牛顿法

dk = -H^-1(xk)*g(xk)

f(xk + dk) ≈ f(xk) + gT(xk)*dk + gTH(xk)*dk^2/2!

g(xk) + H(xk)*dk = 0

dk = -H^-1(xk)*g(xk)

机器学习 | 数学理论：迭代法统一论