机器学习 - 数学理论:迭代法统一论

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

必备的数学知识

导数和梯度

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

  • 一阶导数和梯度

例:
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 的时候。

迭代法

  1. 计数 k = 0
  2. 寻求搜索方向 dk
  3. f(xk + ak*dk) ak >= 0, X(k+1) = Xk + ak + dK
  4. 如果 ||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)


1
2
3
4
5
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)

学习资料

专业词汇

Contour(等值线)
Gradient vector(梯度)
Hessian 矩阵

资料

微积分-导数
线代-二次型
矩阵-二范数
泰勒公式

Gavin Liu wechat
欢迎您扫一扫上面的二维码,订阅我的微信公众号!