数学基础之微积分

本文主要介绍学习机器学习过程中涉及到的一些微积分的基本概念,也包括部分数值分析,优化求解的概念.


1 极限(limit)

1.1 直观定义

当函数 的某个去心邻域内有定义,若当 “无限趋近于” 时,其对应的函数值“无限趋于” 一个确定的常数 ,则称 是当 趋于 时函数 的极限,记作.这里所说的”直观定义”主要指”无限趋于”,是一种直观的说法,并没有给出确切的数学定义.

1.2 精确定义

直观定义中的”无限趋近”是个含糊不清的概念,为了更精准的用数学语言表达这个概念,很多数学家都做了努力,包括法国数学家朗贝尔(D’ Alembert),法国数学家柯西(Cauchy),但最终系统的引入 语言的是德国数学家魏尔斯得拉斯(Weierstrass).

定义在 的某个去心领域 ,若存在常数 ,对于任意给定的 ,存在 ,使得对于任意的 ,即当 时,恒有 ,则称 时的极限,记作.

2 常数

有很多人写过关于这个常数的博客,都把这个常数跟银行利息挂钩了,其中比较有意思的一篇在这里.

3 导数(derivative)

设函数 在点 的某邻域内有定义,如果极限

存在,则称函数 可导,并且称这个极限值为函数 在点 处的导数,记作 或者 .

4 微分(differential)

设函数 在点 的某邻域内有定义, 是自变量 处的增量,如果存在一个与 无关的常数 ,使得 ,则称函数 在点 出可微(differentiable),关于 的线性部分 是函数 在点 处的微分.记作 .显然有 .

5 导数的四则运算

设函数 ,,在 处可导,则:

6 复合函数求导

设复合函数 ,函数 在点 可导,函数在点可导,则复合函数在点 可导,并且:

7 偏导数

设二元函数 在点 的某个邻域有定义,固定 ,将函数 看作 的一元函数,并在 求导,,如果这个导数存在,则称其为二元函数在点 关于的偏导数,记作.同理可以定义.可以将二元函数扩展到 元函数.

8 海森矩阵(Hesse Matrix)

多元函数 的所有二阶偏导数构成的矩阵:

称为函数 的海森矩阵,记作 .

9 梯度

设二元函数 在点 可微,称向量 在点 的梯度.如果梯度是非零向量,则梯度方向是函数值增长最快的方向,负梯度是函数值下降最快的方向,这点在后面会经常用到.同样二元函数也可以很容易扩展到元函数.

10 泰勒展开(Taylor’s expansion)

泰勒展开主要是为了用多项式函数来近似地表示一个函数,以研究一些比较复杂的函数性质,用途非常广泛. 一元函数 处的展开式为:

处的展式为:

常见的泰勒展开公式有两种,一种带佩亚诺(Piano)余项,一种带拉格朗日(lagrange)余项.

11 带佩亚诺余项的泰勒展开

最后一项称为佩亚诺余项.

12 带拉格朗日余项的泰勒展开

其中 介于之间,最后一项成为拉格朗日余项.

多元函数 处的展开式为:

13 原函数

如果在区间 上存在一个可导函数,使得,恒有 ,则称 上的一个原函数.注意原函数有无穷多个,他们之间相差一个常数.

14 牛顿莱布尼茨(Newton-Leibniz)公式

上连续,上的一个原函数,则:

15 一元函数极值

15.1 必要条件

如果函数 在点 处取得极值(极大值或极小值),且在该点可导,则导数.

15.2 充分条件

如果函数 的某个邻域内有一阶导数,并且,又设 存在,则:

  • 如果,则取得极小值.
  • 如果如果,则取得极大值.

16 多元函数极值

16.1 必要条件

设多元函数 取得极值,如果 在点 处存在偏导数 ,则有.

16.2 充分条件

设多元函数 及其附近有连续二阶偏导数,而且 ,则:

  • 正定时, 是极小值点.
  • 负定时, 是极大值点.
  • 不定时, 不是极值点.

17 无约束优化

假设函数 上具有二阶连续偏导数的函数,考虑无约束优化问题:

表示目标函数的极小点.解无约束优化问题一般常用迭代算法,常用的迭代算法有梯度下降法,牛顿法和拟牛顿法.迭代公式为:

其中称为搜索方向,称为步长,为第k次迭代后x的值.不同的迭代算法的区别主要在搜索方向的确定上,而如何确定步长是另一个问题,这里不打算介绍.

17.1 梯度下降法(Gradient Descent)

梯度下降法是一种迭代算法.选取适当的初值,不断迭代,更新的值,直到收敛.由于梯度方向是函数值增长最快的方向,负梯度方向是函数值下降最快的方向,所以梯度下降法很自然的选择了负梯度方向为搜索方向.所以迭代公式变为:

其中的梯度,记为.

梯度下降法

  • 给定初值和精度阈值, 并令k: = 0
  • 计算 , 如果, 停止迭代, 令. 否则求步长
  • 计算新的迭代点, 计算, 如果 或者 , 停止迭代, 令
  • 否则, 令k: =k+1, 转步骤3
17.2 牛顿法(Newton’s method)

将函数附近做二阶泰勒展开:

其中 处的梯度值,为海森矩阵在处的值.

对上面的二阶泰勒展开式两边求导得到:

由前面提到的多元函数极值的必要条件得知,如果函数在处取得极值,必有:

代入整理得到:

所以:

其中称为牛顿方向,如果也引入一个步长 ,则迭代公式变成:

牛顿法

  • 给定初值和精度阈值, 并令k: =0
  • 计算 , , 如果 , 停止迭代.否则确定牛顿方向 , 计算步长
  • 计算新的迭代点
  • 令k: =k+1,转步骤2

Wikipedia上的一张图(绿色的线代表梯度下降法,红色的线代表牛顿法),很形象的说明了梯度下降和牛顿法的区别,梯度下降仅仅考虑了当前函数值在迭代点附近的变化,而牛顿法还考虑了函数值变化的趋势(会往等高线越来越密的方向靠),也就是二阶导数,梯度下降相当于用一个平面不断逼近,而牛顿法师用一个曲面不断逼近,所以牛顿法收敛得更快.

17.3 拟牛顿法(Quasi-Newton’s method)

请参考逻辑回归关于这部分的内容.

18 约束优化

在约束优化中,常常利用拉格朗日对偶性将原始问题转换成对偶问题,通过解对偶问题得到原始问题的解,在最大熵和支持向量机模型中,都用到了该方法.先看个例子: 将正数a分成n个正数之和,如何使乘积最大?

令:

构造辅助函数:

解方程组组得到:

但一般实际问题中遇到的问题比这个要复杂得多,不太好直接求解,往往会将这个问题转化成另外一个等价的问题,这就是所谓的拉格朗日对偶问题.

18.1 原始问题

,, 是定义在 上的连续可微函数,考虑约束优化问题:

称此约束最优化问题为原始最优化问题或者原始问题.

引进广义拉格朗日函数

其中 , 是拉格朗日乘子,并且. 考虑x的函数:

下标P表示原始问题.注意这是关于 x 的函数,, 只是约束.

如果$x$ 都能满足原始约束条件的话,显然有 ,如果存在$x$不满足条件,一定可以找到合适的 , 让$f(x)$无穷大.如果考虑极小化问题:

显然该问题的解与原始问题的解释等价的,即他们有相同的解.问提称为广义拉格朗日函数的极小极大问题.定义原始问题的的最优值为:

18.2 对偶问题

定义,的函数:

再考虑极大化问题:

问题 称为广义拉格朗日函数的极大极小问题.

将这个极大极小问题表示称约束最优化问题:

称为原始问题的对偶问题.定义对偶问题的最优值为:

18.3 原始问题与对偶问题的关系

如果原始问题和对偶问题都有最优值,则有 .假设,是凸函数,是仿射函数,并且不等式约束 严格可行(即存在,对所有的),则 分别是原始问题和对偶问题的解的充要条件是 满足KKT(Karush-Kuhn-Tucker)条件:

19 练习题

最后附上CMU的一套简单测试题,可以用来你是否具备学习机器学习入门的数学基础.

20 参考资料

  1. 统计学习方法 李航著
  2. 微积分 清华大学出版社
  3. 大学数学实验 高等教育出版社
  4. http://en.wikipedia.org/wiki/Taylor_series
  5. http://en.wikipedia.org/wiki/Newton's_method_in_optimization