数学基础之微积分

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

直观定义

当函数 $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$。这里所说的”直观定义”主要指”无限趋于”，是一种直观的说法，并没有给出确切的数学定义。

精确定义

直观定义中的”无限趋近”是个含糊不清的概念，为了更精准的用数学语言表达这个概念，很多数学家都做了努力，包括法国数学家朗贝尔（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

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

设函数 $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}$。

设函数 $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$。

设函数 $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)$

$\large \left( \frac {f(x)}{g(x)} \right)^\prime = \frac {f^\prime (x)g(x) – f(x)g^\prime (x)} {g^2(x)} $

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

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

设二元函数 $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$ 元函数。

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

$\Large \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=(x_{10},x_{20},\ldots , x_{d0})$ 的海森矩阵，记作 $H_f(x_0)$。

设二元函数 $f(x,y)$ 在点 $(x_0,y_0)$ 可微，称向量$ \large \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$元函数。

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

一元函数 $f(x)$ 在 $x=x_0$ 处的展开式为：

$\large 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$ 处的展式为：

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

常见的泰勒展开公式有两种，一种带佩亚诺（Piano）余项，一种带拉格朗日（lagrange）余项。

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

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

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

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

$\large 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=(x_{10},x_{20},\ldots , x_{d0})$ 处的展开式为：

$\large 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 $

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

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

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

必要条件

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

充分条件

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

（1）如果$f^{\prime \prime} (x_0)>0$，则$f(x)$在$x_0$取得极小值；

（2）如果如果$f^{\prime \prime} (x_0)

必要条件

设多元函数 $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)。

充分条件

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

（1）$H_f(x_0)$正定时，$x_0$ 是极小值点；

（2）$H_f(x_0)$负定时，$x_0$ 是极大值点；

（3）$H_f(x_0)$不定时，$x_0$ 不是极值点；

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

$\large 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的值。不同的迭代算法的区别主要在搜索方向的确定上，而如何确定步长是另一个问题，这里不打算介绍。

梯度下降法（Gradient Descent）

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

$x^{k+1}=x^k – \lambda_k \bigtriangledown f(x^k)$

其中$\bigtriangledown f(x^k)$为$f(x)$在$x^k$的梯度，记为$g_k$。

算法：梯度下降法

1.给定初值$x^0$和精度阈值$\varepsilon$，并令k ：=0

2.计算$f(x^k)$

3.计算 $g_k$，如果$||g_k||

4.计算新的迭代点$x^{k+1}=x^k – \lambda_k g_k$，计算$f(x^{k+1})$，如果$||f(x^{k+1}) – f(x^k)||

5.否则，令k：=k+1，转步骤3

牛顿法（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$处的值。

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

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

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

$\bigtriangledown 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$，则：

算法牛顿法

1.给定初值$x^0$和精度阈值$\varepsilon$，并令k：=0

2.计算 $g_k$，$H_k$

3.如果$||g_k||

4.计算新的迭代点 $x^{k+1} = x^k + \lambda_k d_k$

5.令k：=k+1，转步骤2

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

拟牛顿法（Quasi-Newton’s method）

将在逻辑回归或者最大熵模型的时候介绍和推导

在约束优化中，常常利用拉格朗日对偶性将原始问题转换成对偶问题，通过解对偶问题得到原始问题的解，在最大熵和支持向量机模型中，都用到了该方法。先看个例子：

将正数a分成n个正数之和，如何使乘积最大？

$\large f(x_1,x_2,\ldots,x_n) = x_1 x_2 \ldots x_n $

$\large g(x_1,x_2,\ldots,x_n) = x_1 + x_2 + \ldots + x_n – a $

构造辅助函数：

$\large L(x_1,x_2,\ldots,x_n) = x_1 x_2 \ldots x_n – \lambda (x_1 + x_2 + \ldots + x_n – a) $

$\large \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 $

$\large \ldots $

$\large \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 $

$\large \frac {\partial L}{\partial \lambda} = a – (x_1 + x_2 + \ldots + x_n) = 0 $

解方程组组得到：

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

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

原始问题

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

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

$s.t. \qquad c_i(x) \leq 0, i=1,2, \ldots, k $

$ \qquad \qquad h_j(x)=0, j=1,2, \ldots, l $

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

引进广义拉格朗日函数：

$\large 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的函数：

$\large \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) 无穷大。如果考虑极小化问题：

$\large 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)$

对偶问题

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

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

再考虑极大化问题：

$\large 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)$ 称为广义拉格朗日函数的极大极小问题。

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

$\large 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) $

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

如果原始问题和对偶问题都有最优值，则有 $d^ \leq p^$。

假设$f(x)$, $c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束 $c_i(x)$严格可行（即存在x，对所有的c(x)

$\nabla_x L(x^,\alpha^,\beta^*)=0$

$\nabla_{\alpha} L(x^,\alpha^,\beta^*)=0$

$\nabla_{\beta} L(x^,\alpha^,\beta^*)=0$

$\alpha_{i}^{}c_i(x^)=0, i=1,2,\ldots,k$

$c_i(x^*) \leq 0, i=1,2,\ldots,k$

$\alpha_{i}\geq 0, i=1,2,\ldots,k$

$h_{j}(x^*)\geq 0, i=1,2,\ldots,l$

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

统计学习方法 李航著

微积分 清华大学出版社

大学数学实验 高等教育出版社

转载 http://www.cnblogs.com/dudi00/p/4056451.html

Original: https://www.cnblogs.com/chenying99/p/5027983.html
Author: 刺猬的温驯
Title: 数学基础之微积分