数学基础之微积分

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

---

1 极限(limit)

1.1 直观定义

当函数 $y=f(x)$ 在 $x_0$ 的某个去心邻域内有定义,若当 $x$ “无限趋近于” $x_0$ 时,其对应的函数值$f(x)$“无限趋于” 一个确定的常数 $A$ ,则称 $A$ 是当 $x$ 趋于 $x_0$ 时函数 $y=f(x)$ 的极限,记作$\lim_{x\to x_0}f(x)=A$.这里所说的”直观定义”主要指”无限趋于”,是一种直观的说法,并没有给出确切的数学定义.

1.2 精确定义

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

设 $f(x)$ 定义在 $x_0$ 的某个去心领域 $N(x_0)$ ,若存在常数 $A$ ,对于任意给定的 $\varepsilon>0$ ,存在 $\delta>0$ ,使得对于任意的 $x\in N(x_0,\delta)$,即当 $0<\|x-x_0\|<\delta$ 时,恒有 $\|f(x)-A\|<\varepsilon$,则称 $A$ 为 $f(x)$ 当 $x\to x_0$ 时的极限,记作$\lim_{x\to x_0}f(x)=A$.

2 常数 $e$

$$\lim_{x \to 0}(1+x)^{\frac {1}{x}}=e$$

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

3 导数(derivative)

设函数 $y=f(x)$ 在点 $x_0$ 的某邻域内有定义,如果极限

$$\lim_{\Delta x \to 0}\frac {f(x_0 + \Delta x) - f(x_0)}{\Delta x}$$

存在,则称函数 $f(x)$ 在 $x_0$ 可导,并且称这个极限值为函数 $f(x)$ 在点 $x_0$ 处的导数,记作 $f^\prime (x_0)$ 或者 $\frac {df}{dx}\|_{x=x_0}$.

4 微分(differential)

设函数 $y=f(x)$ 在点 $x_0$ 的某邻域内有定义,$\Delta x$ 是自变量 $x$ 在 $x_0$ 处的增量,如果存在一个与 $\Delta x$ 无关的常数 $a$,使得 $\Delta y=f(x_0 + \Delta x) - f(x_0) = a \Delta x + o(\Delta x)$,则称函数 $f(x)$ 在点 $x_0$ 出可微(differentiable),关于 $\Delta x$ 的线性部分 $a\Delta x$ 是函数 $f(x)$ 在点 $x_0$ 处的微分.记作 $df(x_0)$.显然有 $f^\prime(x_0)=a$.

5 导数的四则运算

设函数 $f(x)$,$g(x)$,在 $x$ 处可导,则:

$$(f(x)+g(x))^\prime =f^\prime (x) + g^\prime (x) \\ (f(x) \cdot g(x))^\prime = f^\prime (x)g(x) + f(x)g^\prime (x) \\ \left( \frac {f(x)}{g(x)} \right)^\prime = \frac {f^\prime (x)g(x) - f(x)g^\prime (x)} {g^2(x)}$$

6 复合函数求导

设复合函数 $y=f(g(x))$,函数 $g(x)$ 在点 $x$ 可导,函数$f(u)$在点$u=g(x)$可导,则复合函数$y=f(g(x))$在点 $x$ 可导,并且:

$$\frac {dy}{dx}=\frac {dy}{du} \frac {du}{dx}$$

7 偏导数

设二元函数 $f(x,y)$ 在点 $P_0=(x_0,y_0)$ 的某个邻域有定义,固定 $y=y_0$,将函数 $f(x,y_0)$ 看作 $x$的一元函数,并在 $x_0$求导,$\lim_{\Delta x \to 0} \frac {f(x_0+\Delta x,y_0) - f(x_0,y_0) }{\Delta x}$,如果这个导数存在,则称其为二元函数$f(x,y)$在点 $P_0=(x_0,y_0)$关于$x$的偏导数,记作$\frac {\partial f(x_0,y_0)}{\partial x}$.同理可以定义$\frac {\partial f(x_0,y_0)}{\partial y}$.可以将二元函数扩展到 $n$ 元函数.

8 海森矩阵(Hesse Matrix)

多元函数 $f(x_1,x_2,\ldots,x_d)$ 在 $x_0=(x_{10},x_{20},\ldots ,x_{d0})$ 的所有二阶偏导数构成的矩阵:

$$\displaystyle \left[ \begin{matrix} \frac {\partial ^ {2} f}{\partial x_1^2} & \frac {\partial ^ {2} f}{\partial x_1 \partial x_2} & \ldots & \frac {\partial ^ {2} f}{\partial x_1 \partial x_d} \\ \frac {\partial ^ {2} f}{\partial x_2 \partial x_1} & \frac {\partial ^ {2} f}{\partial x_2^2} & \ldots & \frac {\partial ^ {2} f}{\partial x_2 \partial x_d} \\ \vdots & \vdots & & \vdots \\ \frac {\partial ^ {2} f}{\partial x_d \partial x_1} & \frac {\partial ^ {2} f}{\partial x_d \partial x_2} & \ldots & \frac {\partial ^ {2} f}{\partial x_d^2} \end{matrix} \right]$$

称为函数$f(x_1,x_2,\ldots,x_d)$ 在 $x_0=(x_{10},x_{20},\ldots ,x_{d0})$ 的海森矩阵,记作 $H_f(x_0)$.

9 梯度

设二元函数 $f(x,y)$ 在点 $(x_0,y_0)$ 可微,称向量$\left( \frac {\partial f(x_0,y_0)}{\partial x},\frac {\partial f(x_0,y_0)}{\partial y} \right)^T$ 为$f(x,y)$ 在点 $(x_0,y_0)$的梯度.如果梯度是非零向量,则梯度方向是函数值增长最快的方向,负梯度是函数值下降最快的方向,这点在后面会经常用到.同样二元函数也可以很容易扩展到$n$元函数.

10 泰勒展开(Taylor’s expansion)

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

$$f(x)=f(x_0)+\frac {f^\prime (x_0)}{1!}(x-x_0)+\frac {f^{\prime \prime} (x_0)}{2!}(x-x_0)^2+ \\ \frac {f^3(x_0)}{3!}(x-x_0)^3+\ldots$$

$e^x$ 在 $x=0$ 处的展式为:

$$e^x=\sum_{n=0}^\infty \frac {x^n} {n!}=1+x+\frac {x^2}{2!}+\frac {x^3}{3!}+\ldots$$

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

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

$$f(x) = \sum_{k=0}^{n}\frac {f^{k}(x_0)}{k!}(x-x_0)^k+o((x-x_0)^n)$$

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

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

$$f(x) = \sum_{k=0}^{n}\frac {f^{k}(x_0)}{k!}(x-x_0)^k + \frac {f^{n+1}(\varepsilon)}{(n+1)!}(x-x_0)^{n+1}$$

其中 $\varepsilon$介于$x$ 与 $x_0$之间,最后一项成为拉格朗日余项.

多元函数 $f(x_1,x_2,\ldots,x_d)$ 在 $x_0=(x_{10},x_{20},\ldots ,x_{d0})$ 处的展开式为:

$$\displaystyle f(x_1,x_2,\ldots,x_d)=f(x_{10},x_{20},\ldots ,x_{d0})+ \\ \sum_{i=1}^{d} \frac {\partial f(x_{10},x_{20},\ldots ,x_{d0})}{\partial x_i}(x_i-x_{i0}) + \\ \frac {1}{2!} \sum_{i=1}^{d} \sum_{j=1}^{d}\frac {\partial f(x_{10},x_{20},\ldots ,x_{d0})}{\partial x_i \partial x_j}(x_i-x_{i0})(x_j-x_{j0}) + \ldots$$

13 原函数

如果在区间 $I$ 上存在一个可导函数$F(x)$,使得$\forall x \in I$,恒有 $F^\prime (x) = f(x)$,则称$F(x)$为$f(x)$在 $I$ 上的一个原函数.注意原函数有无穷多个,他们之间相差一个常数.

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

设$f(x)$在$[a,b]$上连续,$F(x)$是$f(x)$在$[a,b]$上的一个原函数,则:

$$\int_{a}^{b} f(x)dx = F(x)|_{a}^{b} = F(b) - F(a)$$

15 一元函数极值

15.1 必要条件

如果函数 $y=f(x)$ 在点 $x_0$ 处取得极值(极大值或极小值),且在该点可导,则导数$f^\prime (x_0)=0$.

15.2 充分条件

如果函数 $y=f(x)$在$x_0$的某个邻域内有一阶导数,并且$f^\prime (x_0)=0$,又设$f^{\prime \prime} (x_0)$ 存在,则:

• 如果$f^{\prime \prime} (x_0)>0$,则$f(x)$在$x_0$取得极小值.
• 如果如果$f^{\prime \prime} (x_0)<0$,则$f(x)$在$x_0$取得极大值.

16 多元函数极值

16.1 必要条件

设多元函数 $f(x_1,x_2,\ldots,x_d)$在 $x_0=(x_{10},x_{20},\ldots ,x_{d0})$ 取得极值,如果 $f(x)$ 在点 $x_0$ 处存在偏导数 $\frac {\partial f}{\partial x_i}$,则有$\frac {\partial f}{\partial x_i}=0(i=1,2,3...d)$.

16.2 充分条件

设多元函数 $f(x_1,x_2,\ldots,x_d)$ 在 $x_0=(x_{10},x_{20},\ldots ,x_{d0})$ 及其附近有连续二阶偏导数,而且 $gradf(x_0)=0$,则:

• $H_f(x_0)$正定时,$x_0$ 是极小值点.
• $H_f(x_0)$负定时,$x_0$ 是极大值点.
• $H_f(x_0)$不定时,$x_0$ 不是极值点.

17 无约束优化

假设函数 $f(x)$是 $R^n$上具有二阶连续偏导数的函数,考虑无约束优化问题:

$$min_{x \in R^n}f(x)$$

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

$$x^{k+1}=x^k +\lambda_k d_k$$

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

17.1 梯度下降法(Gradient Descent)

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

$$x^{k+1}=x^k - \lambda_k \nabla f(x^k)$$

其中$\nabla f(x^k)$为$f(x)$在$x^k$的梯度,记为$g_k$.

梯度下降法

• 给定初值$x^0$和精度阈值$\varepsilon$, 并令k: = 0
• 计算 $g_k$, 如果$\|g_k\|<\varepsilon$, 停止迭代, 令$x^*=x^k$. 否则求步长 $\lambda_k$
• 计算新的迭代点$x^{k+1}=x^k - \lambda_k g_k$, 计算$f(x^k)$ 和 $f(x^{k+1})$, 如果$\|f(x^{k+1}) - f(x^k)\|<\varepsilon$ 或者 $\|x^{k+1} - x^k\| < \varepsilon$, 停止迭代, 令$x^*=x^{k+1}$
• 否则, 令k: =k+1, 转步骤3

17.2 牛顿法(Newton’s method)

将函数$f(x)$在$x^k$附近做二阶泰勒展开:

$$f(x)=f(x^k)+g_k(x-x^k)+\frac {1}{2}(x-x^k)^T H(x^k) (x-x^k)$$

其中 $g_k$是$f(x)$在$x^k$处的梯度值,$H(x^k)$为海森矩阵在$x^k$处的值.

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

$$\nabla f(x) = g_k + H_k(x-x^k)$$

由前面提到的多元函数极值的必要条件得知,如果函数在$x=x^{k+1}$处取得极值,必有:

$$\nabla f(x^{k+1}) = 0$$

将$x=x^{k+1}$代入整理得到:

$$g_k + H_k(x^{k+1}-x^k) = 0$$

所以:

$$x^{k+1} = x^k + (-H^{-1}_k g_k)$$

其中$-H^{-1}_k g_k$称为牛顿方向,如果也引入一个步长 $\lambda_k$,则迭代公式变成:

$$x^{k+1} = x^k + \lambda_k (-H^{-1}_k g_k)$$

牛顿法

• 给定初值$x^0$和精度阈值$\varepsilon$, 并令k: =0
• 计算 $g_k$, $H_k$, 如果 $\|g_k\|<\varepsilon$, 停止迭代.否则确定牛顿方向 $d_k=-H^{-1}_k g_k$, 计算步长 $\lambda_k$
• 计算新的迭代点 $x^{k+1} = x^k + \lambda_k d_k$
• 令k: =k+1,转步骤2

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

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

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

18 约束优化

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

令:

$$f(x_1,x_2,\ldots,x_n) = x_1 x_2 \ldots x_n \\ g(x_1,x_2,\ldots,x_n) = x_1 + x_2 + \ldots + x_n - a$$

构造辅助函数:

$$L(x_1,x_2,\ldots,x_n) = x_1 x_2 \ldots x_n - \lambda (x_1 + x_2 + \ldots + x_n - a) \\ \frac {\partial L}{\partial x_1} = \frac {\partial f}{\partial x_1} + \lambda \frac {\partial g}{\partial x_1} =x_2 x_3 \ldots x_n - \lambda = 0 \\ \ldots \\ \frac {\partial L}{\partial x_n} = \frac {\partial f}{\partial x_n} + \lambda \frac {\partial g}{\partial x_n} =x_1 x_2 \ldots x_{n-1} - \lambda = 0 \\ \frac {\partial L}{\partial \lambda} = a - (x_1 + x_2 + \ldots + x_n) = 0 \\$$

解方程组组得到:

$$x_1=x_2=\ldots=x_n=\frac {a}{n}$$

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

18.1 原始问题

设$f(x)$,$c_i(x)$,$h_j(x)$ 是定义在 $\textbf {R}^n$上的连续可微函数,考虑约束优化问题:

$$\begin{equation*} \begin{split} & min_{x \in R^n} f(x) \\ s.t. & c_i(x) \leq 0,i=1,2,\ldots,k \\ & h_j(x)=0,j=1,2,\ldots,l \end{split} \end{equation*}$$

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

引进广义拉格朗日函数

$$L(x,\alpha,\beta) = f(x) + \sum_{i=1}^{k}\alpha_i c_i(x) + \sum_{j=1}^{l}\beta_j h_j(x)$$

其中 $\alpha_i$,$\beta_j$ 是拉格朗日乘子,并且$\alpha_i \geq 0$. 考虑x的函数:

$$\Theta_P(x) = max_{\alpha,\beta : \alpha_i \geq 0}L(x,\alpha,\beta)$$

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

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

$$min_x \Theta_P(x) = min_x max_{\alpha,\beta : \alpha_i \geq 0}L(x,\alpha,\beta)$$

显然该问题的解与原始问题的解释等价的,即他们有相同的解.问提$min_x max_{\alpha,\beta : \alpha_i \geq 0}L(x,\alpha,\beta)$称为广义拉格朗日函数的极小极大问题.定义原始问题的的最优值为:

$$p^*=min_x \Theta_P(x)$$

18.2 对偶问题

定义$\alpha$,$\beta$的函数:

$$\Theta_D(\alpha,\beta) = min_x L(x,\alpha,\beta)$$

再考虑极大化问题:

$$max_{\alpha,\beta : \alpha_i \geq 0}\Theta_D(\alpha,\beta) = max_{\alpha,\beta : \alpha_i \geq 0}min_x L(x,\alpha,\beta)$$

问题 $max_{\alpha,\beta : \alpha_i \geq 0}min_x L(x,\alpha,\beta)$ 称为广义拉格朗日函数的极大极小问题.

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

$$max_{\alpha,\beta}\Theta_D(\alpha,\beta) = max_{\alpha,\beta}min_x L(x,\alpha,\beta) \\ s.t.\alpha_i \geq 0,i=1,2,\ldots,k$$

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

$$d^* = max_{\alpha,\beta : \alpha_i \geq 0}\Theta_D(\alpha,\beta)$$

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

如果原始问题和对偶问题都有最优值,则有 $d^* \leq p^*$.假设$f(x)$,$c_i(x)$是凸函数,$h_j(x)$是仿射函数,并且不等式约束 $c_i(x)$严格可行(即存在$x$,对所有的$c(x)<0$),则 $x^*,\alpha^*,\beta^*$ 分别是原始问题和对偶问题的解的充要条件是 $x^*,\alpha^*,\beta^*$ 满足KKT(Karush-Kuhn-Tucker)条件:

$$\begin{equation*} \begin{split} \displaystyle & \nabla_x L(x^*,\alpha^*,\beta^*) = 0 \\ \displaystyle & \nabla_{\alpha} L(x^*,\alpha^*,\beta^*) = 0 \\ \displaystyle & \nabla_{\beta} L(x^*,\alpha^*,\beta^*) = 0 \\ \displaystyle & \alpha_{i}^{*}c_i(x^*) = 0,i=1,2,\ldots,k \\ \displaystyle & c_i(x^*) \leq 0,i=1,2,\ldots,k \\ \displaystyle & \alpha_{i} \geq 0,i=1,2,\ldots,k \\ \displaystyle & h_{j}(x^*) \geq 0,i=1,2,\ldots,l \end{split} \end{equation*}$$

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

---