原文 http://www.cnblogs.com/dudi00/p/4056451.html

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

极限（limit）

直观定义

当函数 y=f(x)y=f(x) 在 x0x0 的某个去心邻域内有定义，若当 xx “无限趋近于” x0x0 时，其对应的函数值 f(x)f(x) “无限趋于”
一个确定的常数 AA ，则称 AA 是当 xx 趋于 x0x0 时函数 y=f(x)y=f(x) 的极限，记作 limx→x0f(x)=Alimx→x0f(x)=A。这里所说的“直观定义”主要指“无限趋于”，是一种直观的说法，并没有给出确切的数学定义。

精确定义

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

设 f(x)f(x) 定义在 x0x0 的某个去心领域 N∗(x0)N∗(x0) ，若存在常数 AA ，对于任意给定的 ε>0ε>0 ，存在 δ>0δ>0 ，使得对于任意的 x∈N∗(x0,δ)x∈N∗(x0,δ)，即当 0<|x−x0|<δ0<|x−x0|<δ 时，恒有 |f(x)−A|<ε|f(x)−A|<ε，则称 AA 为 f(x)f(x) 当 x→x0x→x0 时的极限，记作limx→x0f(x)=Alimx→x0f(x)=A。

常数 ee

limx→0(1+x)1x=elimx→0(1+x)1x=e

有很多人写过关于这个常数的博客，都把这个常数跟银行利息挂钩了，其中比较有意思的一篇是 http://www.ruanyifeng.com/blog/2011/07/mathematical_constant_e.html

导数（derivative）

设函数 y=f(x)y=f(x) 在点 x0x0 的某邻域内有定义，如果极限 limΔx→0f(x0+Δx)−f(x0)ΔxlimΔx→0f(x0+Δx)−f(x0)Δx 存在，则称函数 f(x)f(x) 在 x0x0 可导，并且称这个极限值为函数 f(x)f(x) 在点 x0x0 处的导数，记作 f′(x0)f′(x0) 或者 dfdx|x=x0dfdx|x=x0。

微分（differential）

设函数 y=f(x)y=f(x) 在点 x0x0 的某邻域内有定义，ΔxΔx 是自变量 xx 在 x0x0 处的增量，如果存在一个与 ΔxΔx 无关的常数 aa，使得 Δy=f(x0+Δx)−f(x0)=aΔx+o(Δx)Δy=f(x0+Δx)−f(x0)=aΔx+o(Δx)，则称函数 f(x)f(x) 在点 x0x0 出可微（differentiable），关于 ΔxΔx 的线性部分 aΔxaΔx 是函数 f(x)f(x) 在点 x0x0 处的微分。记作 df(x0)df(x0)。显然有 f′(x0)=af′(x0)=a。

导数的四则运算

设函数 f(x)f(x)，g(x)g(x)，在 xx 处可导，则：

(f(x)+g(x))′=f′(x)+g′(x)(f(x)+g(x))′=f′(x)+g′(x)

(f(x)⋅g(x))′=f′(x)g(x)+f(x)g′(x)(f(x)⋅g(x))′=f′(x)g(x)+f(x)g′(x)

(f(x)g(x))′=f′(x)g(x)−f(x)g′(x)g2(x)(f(x)g(x))′=f′(x)g(x)−f(x)g′(x)g2(x)

复合函数求导

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

dydx=dydududxdydx=dydududx。

偏导数

设二元函数 f(x,y)f(x,y) 在点 P0=(x0,y0)P0=(x0,y0) 的某个邻域有定义，固定 y=y0y=y0，将函数 f(x,y0)f(x,y0) 看作 xx的一元函数，并在 x0x0求导， limΔx→0f(x0+Δx,y0)−f(x0,y0)ΔxlimΔx→0f(x0+Δx,y0)−f(x0,y0)Δx，如果这个导数存在，则称其为二元函数f(x,y)f(x,y)在点 P0=(x0,y0)P0=(x0,y0)关于xx的偏导数，记作∂f(x0,y0)∂x∂f(x0,y0)∂x。同理可以定义∂f(x0,y0)∂y∂f(x0,y0)∂y。可以将二元函数扩展到 nn 元函数。

海森矩阵（Hesse Matrix）

多元函数 f(x1,x2,…,xd)f(x1,x2,…,xd) 在 x0=(x10,x20,…,xd0)x0=(x10,x20,…,xd0)的所有二阶偏导数构成的矩阵
：

⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢∂2f∂x21∂2f∂x2∂x1⋮∂2f∂xd∂x1∂2f∂x1∂x2∂2f∂x22⋮∂2f∂xd∂x2………∂2f∂x1∂xd∂2f∂x2∂xd⋮∂2f∂x2d⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥[∂2f∂x12∂2f∂x1∂x2…∂2f∂x1∂xd∂2f∂x2∂x1∂2f∂x22…∂2f∂x2∂xd⋮⋮⋮∂2f∂xd∂x1∂2f∂xd∂x2…∂2f∂xd2]

称为函数f(x1,x2,…,xd)f(x1,x2,…,xd) 在 x=(x10,x20,…,xd0)x=(x10,x20,…,xd0) 的海森矩阵，记作 Hf(x0)Hf(x0)。

梯度

设二元函数 f(x,y)f(x,y) 在点 (x0,y0)(x0,y0) 可微，称向量(∂f(x0,y0)∂x,∂f(x0,y0)∂y)T(∂f(x0,y0)∂x,∂f(x0,y0)∂y)T 为f(x,y)f(x,y) 在点 (x0,y0)(x0,y0)的梯度。如果梯度是非零向量，则梯度方向是函数值增长最快的方向，负梯度是函数值下降最快的方向，这点在后面会经常用到。同样二元函数也可以很容易扩展到nn元函数。

泰勒展开（Taylor's expansion）

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

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

f(x)=f(x0)+f′(x0)1!(x−x0)+f′′(x0)2!(x−x0)2+f3(x0)3!(x−x0)3+…f(x)=f(x0)+f′(x0)1!(x−x0)+f′′(x0)2!(x−x0)2+f3(x0)3!(x−x0)3+…

exex 在 x=0x=0 处的展式为：

ex=∑∞n=0xnn!=1+x+x22!+x33!+…ex=∑n=0∞xnn!=1+x+x22!+x33!+…

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

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

f(x)=∑nk=0fk(x0)k!(x−x0)k+o((x−x0)n)f(x)=∑k=0nfk(x0)k!(x−x0)k+o((x−x0)n)

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

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

f(x)=∑nk=0fk(x0)k!(x−x0)k+fn+1(ε)(n+1)!(x−x0)n+1f(x)=∑k=0nfk(x0)k!(x−x0)k+fn+1(ε)(n+1)!(x−x0)n+1

其中 εε介于xx 与 x0x0之间，最后一项成为拉格朗日余项。

多元函数 f(x1,x2,…,xd)f(x1,x2,…,xd) 在 x=(x10,x20,…,xd0)x=(x10,x20,…,xd0) 处的展开式为：

f(x1,x2,…,xd)=f(x10,x20,…,xd0)+∑di=1∂f(x10,x20,…,xd0)∂xi(xi−xi0)+12!∑di=1∑j=1d∂f(x10,x20,…,xd0)∂xi∂xj(xi−xi0)(xj−xj0)+…f(x1,x2,…,xd)=f(x10,x20,…,xd0)+∑i=1d∂f(x10,x20,…,xd0)∂xi(xi−xi0)+12!∑i=1d∑j=1d∂f(x10,x20,…,xd0)∂xi∂xj(xi−xi0)(xj−xj0)+…

原函数

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

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

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

∫baf(x)dx=F(x)|ba=F(b)−F(a)∫abf(x)dx=F(x)|ab=F(b)−F(a)

一元函数极值

必要条件

如果函数 y=f(x)y=f(x) 在点 x0x0 处取得极值（极大值或极小值），且在该点可导，则导数f′(x0)=0f′(x0)=0。

充分条件

如果函数 y=f(x)y=f(x)在x0x0的某个邻域内有一阶导数，并且f′(x0)=0f′(x0)=0，又设f′′(x0)f′′(x0) 存在，则有：

（1）如果f′′(x0)>0f′′(x0)>0，则f(x)f(x)在x0x0取得极小值；

（2）如果如果f′′(x0)<0f′′(x0)<0，则f(x)f(x)在x0x0取得极大值；

多元函数极值

必要条件

设多元函数 f(x1,x2,…,xd)f(x1,x2,…,xd)在x0=(x10,x20,…,xd0)x0=(x10,x20,…,xd0)取得极值，如果 f(x)f(x) 在点 x0x0 处存在偏导数 ∂f∂xi∂f∂xi，则有∂f∂xi=0∂f∂xi=0(i=1,2,3...d)。

充分条件

设多元函数 f(x1,x2,…,xd)f(x1,x2,…,xd) 在 x0=(x10,x20,…,xd0)x0=(x10,x20,…,xd0)及其附近有连续二阶偏导数，而且 gradf(x0)=0gradf(x0)=0，则：

（1）Hf(x0)Hf(x0)正定时，x0x0 是极小值点；

（2）Hf(x0)Hf(x0)负定时，x0x0 是极大值点；

（3）Hf(x0)Hf(x0)不定时，x0x0 不是极值点； 

 无约束优化

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

minx∈Rnf(x)minx∈Rnf(x)

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

xk+1=xk+λkdkxk+1=xk+λkdk

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

梯度下降法（Gradient Descent）

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

xk+1=xk−λk▽f(xk)xk+1=xk−λk▽f(xk)

其中▽f(xk)▽f(xk)为f(x)f(x)在xkxk的梯度，记为gkgk。

算法：梯度下降法

1.给定初值x0x0和精度阈值εε，并令k
：=0

2.计算f(xk)f(xk)

3.计算 gkgk，如果||gk||<ε||gk||<ε，停止迭代，令x∗=xkx∗=xk；否则求步长 λkλk

4.计算新的迭代点xk+1=xk−λkgkxk+1=xk−λkgk，计算f(xk+1)f(xk+1)，如果||f(xk+1)−f(xk)||<ε||f(xk+1)−f(xk)||<ε或者||xk+1−xk||||xk+1−xk||，停止迭代，令x∗=xk+1x∗=xk+1

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

牛顿法（Newton's method）

将函数f(x)f(x)在xkxk附近做二阶泰勒展开：

f(x)=f(xk)+gk(x−xk)+12(x−xk)TH(xk)(x−xk)f(x)=f(xk)+gk(x−xk)+12(x−xk)TH(xk)(x−xk)

其中 gkgk是f(x)f(x)在xkxk处的梯度值，H(xk)H(xk)为海森矩阵在xkxk处的值。

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

▽f(x)=gk+Hk(x−xk)▽f(x)=gk+Hk(x−xk)

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

 ▽f(xk+1)=0▽f(xk+1)=0

 将x=xk+1x=xk+1代入整理得到：

gk+Hk(xk+1−xk)=0gk+Hk(xk+1−xk)=0

所以：

xk+1=xk+(−H−1kgk)xk+1=xk+(−Hk−1gk)

其中−H−1k)gk−Hk−1)gk称为牛顿方向，如果也引入一个步长 λkλk，则：

算法牛顿法

1.给定初值x0x0和精度阈值εε，并令k：=0

2.计算 gkgk，HkHk

3.如果||gk||<ε||gk||<ε，停止迭代；否则确定牛顿方向 dk=−H−1kgkdk=−Hk−1gk，计算步长 λkλk

4.计算新的迭代点 xk+1=xk+λkdkxk+1=xk+λkdk

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

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

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

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

约束优化

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

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

令：

f(x1,x2,…,xn)=x1x2…xnf(x1,x2,…,xn)=x1x2…xn

g(x1,x2,…,xn)=x1+x2+…+xn−ag(x1,x2,…,xn)=x1+x2+…+xn−a

构造辅助函数：

L(x1,x2,…,xn)=x1x2…xn−λ(x1+x2+…+xn−a)L(x1,x2,…,xn)=x1x2…xn−λ(x1+x2+…+xn−a)

∂L∂x1=∂f∂x1+λ∂g∂x1=x2x3…xn−λ=0∂L∂x1=∂f∂x1+λ∂g∂x1=x2x3…xn−λ=0

……

∂L∂xn=∂f∂xn+λ∂g∂xn=x1x2…xn−1−λ=0∂L∂xn=∂f∂xn+λ∂g∂xn=x1x2…xn−1−λ=0

∂L∂λ=a−(x1+x2+…+xn)=0∂L∂λ=a−(x1+x2+…+xn)=0

解方程组组得到：

x1=x2=…=xn=anx1=x2=…=xn=an

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

原始问题

设f(x)f(x), ci(x)ci(x), hj(x)hj(x) 是定义在 RnRn上的连续可微函数，考虑约束优化问题：

minx∈Rnf(x)minx∈Rnf(x)

s.t.ci(x)≤0,i=1,2,…,ks.t.ci(x)≤0,i=1,2,…,k

hj(x)=0,j=1,2,…,lhj(x)=0,j=1,2,…,l

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

引进广义拉格朗日函数：

L(x,α,β)=f(x)+∑ki=1αici(x)+∑lj=1βjhj(x)L(x,α,β)=f(x)+∑i=1kαici(x)+∑j=1lβjhj(x)

其中 αiαi, betajbetaj 是拉格朗日乘子，并且αi≥0αi≥0。

考虑x的函数：

ΘP(x)=maxα,β:αi≥0L(x,α,β)ΘP(x)=maxα,β:αi≥0L(x,α,β)

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

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

minxΘP(x)=minxmaxα,β:αi≥0L(x,α,β)minxΘP(x)=minxmaxα,β:αi≥0L(x,α,β)

显然该问题的解与原始问题的解释等价的，即他们有相同的解。问提minxmaxα,β:αi≥0L(x,α,β)minxmaxα,β:αi≥0L(x,α,β)称为广义拉格朗日函数的极小极大问题。定义原始问题的的最优值为：

p∗=minxΘP(x)p∗=minxΘP(x)

对偶问题

定义αα, ββ的函数：

ΘD(α,β)=minxL(x,α,β)ΘD(α,β)=minxL(x,α,β)

再考虑极大化问题：

maxα,β:αi≥0ΘD(α,β)=maxα,β:αi≥0minxL(x,α,β)maxα,β:αi≥0ΘD(α,β)=maxα,β:αi≥0minxL(x,α,β)

问题 maxα,β:αi≥0minxL(x,α,β)maxα,β:αi≥0minxL(x,α,β) 称为广义拉格朗日函数的极大极小问题。

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

maxα,βΘD(α,β)=maxα,βminxL(x,α,β)maxα,βΘD(α,β)=maxα,βminxL(x,α,β)

s.t.αi≥0,i=1,2,…,ks.t.αi≥0,i=1,2,…,k

称为原始问题的对偶问题。定义对偶问题的最优值为：

d∗=maxα,β:αi≥0ΘD(α,β)d∗=maxα,β:αi≥0ΘD(α,β)

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

如果原始问题和对偶问题都有最优值，则有 d∗≤p∗d∗≤p∗。

假设f(x)f(x), ci(x)ci(x)是凸函数，hj(x)hj(x)是仿射函数，并且不等式约束 ci(x)ci(x)严格可行（即存在x，对所有的c(x)<0），则x∗x∗, α∗α∗, β∗β∗分别是原始问题和对偶问题的解的充要条件是x∗x∗, α∗α∗, β∗β∗满足KKT（Karush-Kuhn-Tucker）条件：

∇xL(x∗,α∗,β∗)=0∇xL(x∗,α∗,β∗)=0

∇αL(x∗,α∗,β∗)=0∇αL(x∗,α∗,β∗)=0

∇βL(x∗,α∗,β∗)=0∇βL(x∗,α∗,β∗)=0

α∗ici(x∗)=0,i=1,2,…,kαi∗ci(x∗)=0,i=1,2,…,k

ci(x∗)≤0,i=1,2,…,kci(x∗)≤0,i=1,2,…,k

αi≥0,i=1,2,…,kαi≥0,i=1,2,…,k

hj(x∗)≥0,i=1,2,…,lhj(x∗)≥0,i=1,2,…,l

练习题

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

http://www.cs.cmu.edu/~aarti/Class/10701_Spring14/Intro_ML_Self_Evaluation.pdf

参考资料

http://en.wikipedia.org/wiki/Taylor_series

http://en.wikipedia.org/wiki/Newton's_method_in_optimization

统计学习方法 李航著

微积分 清华大学出版社

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