算法或理论 | 用到的数学知识点 |
---|---|
贝叶斯分类器 | 随机变量,贝叶斯公式,随机变量独立性,正态分布,最大似然估计 |
决策树 | 概率,熵,Gini系数 |
KNN算法 | 距离函数 |
主成分分析 | 协方差矩阵,散布矩阵,拉格朗日乘数法,特征值与特征向量 |
流形学习 | 流形,最优化,测地线,测地距离,图,特征值与特征向量 |
线性判别分析 | 散度矩阵,逆矩阵,拉格朗日乘数法,特征值与特征向量 |
支持向量机 | 点到平面的距离,Slater条件,强对偶,拉格朗日对偶,KKT条件,凸优化,核函数,Mercer条件 |
logistic回归 | 概率,随机变量,最大似然估计,梯度下降法,凸优化,牛顿法 |
随机森林 | 抽样,方差 |
AdaBoost算法 | 概率,随机变量,极值定理,数学期望,牛顿法 |
隐马尔可夫模型 | 概率,离散型随机变量,条件概率,随机变量独立性,拉格朗日乘数法,最大似然估计 |
条件随机场 | 条件概率,数学期望,最大似然估计 |
高斯混合模型 | 正态分布,最大似然估计,Jensen不等式 |
人工神经网络 | 梯度下降法,链式法则 |
卷积神经网络 | 梯度下降法,链式法则 |
循环神经网络 | 梯度下降法,链式法则 |
生成对抗网络 | 梯度下降法,链式法则,极值定理,Kullback-Leibler散度,Jensen-Shannon散度,测地距离,条件分步,互信息 |
K-means算法 | 距离函数 |
强化学习 | 数学期望,贝尔曼方程 |
贝叶斯网络 | 条件概率,贝叶斯公式,图 |
VC维 | Hoeffding不等式 |
导数几何意义:切线斜率;物理意义:速度
一阶导数在机器学习中用处:求极值–导函数为0;神经网络中的激活函数中求导,为了求极值。
导数与函数单调性的关系:一阶大于0为增
极值定理
导数与函数凹凸性的关系:二阶大于0位凹函数
一元函数泰勒展开:
f
(
x
)
=
f
(
x
0
)
+
f
‘
(
x
0
)
(
x
−
x
0
)
+
f
‘
‘
(
x
0
)
2
!
(
x
−
x
0
)
2
+
.
.
.
+
f
n
(
x
0
)
n
!
(
x
−
x
0
)
n
+
R
n
(
x
)
f(x)=f(x_0)+f^`(x_0)(x-x_0)+\frac{f^{``}(x_0)}{2!}(x-x_0)^2+...+\frac{f^{n}(x_0)}{n!}(x-x_0)^n+R_n(x)
f(x)=f(x0)+f‘(x0)(x−x0)+2!f‘‘(x0)(x−x0)2+...+n!fn(x0)(x−x0)n+Rn(x)
其中R(x)为拉格朗日余项。
R
n
(
x
)
=
f
n
+
1
(
ξ
)
(
n
+
1
)
!
(
x
−
x
0
)
n
+
1
,
ξ
为
x
0
与
x
之间的某个值。
R_n(x)=\frac{f^{n+1}(\xi)}{(n+1)!}(x-x_0)^{n+1},\xi为x_0与x之间的某个值。
Rn(x)=(n+1)!fn+1(ξ)(x−x0)n+1,ξ为x0与x之间的某个值。
在机器学习中用来求函数的极值。有时函数f(x)比较复杂,它的所有的导数都存在,不便于处理算它的极值,可以做它的近似:例如在梯度下降法中将函数展开成一次位置,忽略二次和二次以上的项,将其看成线性函数来近似代替f(x)。在牛顿法中,将函数展开到二次位置,用二次函数代替。
向量几何意义:空间中的一个点;物理意义:速度或者力的矢量
n维行向量可以看做1 X n矩阵。(机器学习中向量一般写成行向量)
向量的内积
设有n维向量
x
=
(
x
1
,
x
2
,
.
.
.
,
x
n
)
T
,
y
=
(
y
1
,
y
2
,
.
.
.
,
y
n
)
T
,
令
[
x
,
y
]
=
x
T
y
=
x
1
y
1
+
x
2
y
2
+
.
.
.
+
x
n
y
n
x=(x_1,x_2,...,x_n)^T,y=(y_1,y_2,...,y_n)^T, 令[x,y]=x^Ty=x_1y_1+x_2y_2+...+x_ny_n
x=(x1,x2,...,xn)T,y=(y1,y2,...,yn)T,令[x,y]=xTy=x1y1+x2y2+...+xnyn
[x,y]称为向量x和向量y的内积。
当[x,y]=0时,向量x和向量y正交。即n维向量的夹角为九十度。
向量的范数
将一个向量变成一个标量。
L
p
=
∣
∣
x
∣
∣
p
=
(
∑
i
=
1
n
∣
x
i
∣
p
)
1
/
p
L_p=||x||_p=(\sum_{i=1}^n|x_i|^p)^{1/p}
Lp=∣∣x∣∣p=(i=1∑n∣xi∣p)1/p
L 1 = ∣ ∣ x ∣ ∣ 1 = ∑ i = 1 n ∣ x i ∣ L_1=||x||_1=\sum_{i=1}^n|x_i| L1=∣∣x∣∣1=i=1∑n∣xi∣
L 2 = ∣ ∣ x ∣ ∣ 2 = ∑ i = 1 n ∣ x i ∣ 2 注: L 2 为向量的模,即长度。 L_2=||x||_2=\sqrt{\sum_{i=1}^n|x_i|^2} 注:L_2为向量的模,即长度。 L2=∣∣x∣∣2=i=1∑n∣xi∣2 注:L2为向量的模,即长度。
当向量的长度为1时,称x为单位向量。
若
x
≠
0
,则称
1
∣
∣
x
∣
∣
x
为
x
的单位向量。
若x\neq0,则称\frac{1}{||x||}x为x的单位向量。
若x=0,则称∣∣x∣∣1x为x的单位向量。
在解析几何中,曾引进向量的数量积x·y=|x||y|cos A,A为x,y的夹角
当 ∣ ∣ x ∣ ∣ ≠ 0 , ∣ ∣ y ∣ ∣ ≠ 0 , 规定 Θ = a r c c o s [ x , y ] ∣ ∣ x ∣ ∣ ∣ ∣ y ∣ ∣ ( 0 ≤ Θ ≤ π ) , 称为 n 维向量 x 与 y 的夹角。 当||x||\neq0,||y||\neq0,规定\Theta=arccos\frac{[x,y]}{||x||||y||} (0\leq\Theta\leq\pi),称为n维向量x与y的夹角。 当∣∣x∣∣=0,∣∣y∣∣=0,规定Θ=arccos∣∣x∣∣∣∣y∣∣[x,y](0≤Θ≤π),称为n维向量x与y的夹角。
施密特(Schmidt)正交化过程
设
n
维向量
e
1
,
e
2
,
.
.
.
,
e
r
,
两两正交,且都是单位向量,则称
e
1
,
e
2
,
.
.
.
,
e
r
是一个标准正交向量组。
设n维向量e_1,e_2,...,e_r,两两正交,且都是单位向量,则称e_1,e_2,...,e_r是一个标准正交向量组。
设n维向量e1,e2,...,er,两两正交,且都是单位向量,则称e1,e2,...,er是一个标准正交向量组。
设 n 维向量组 α 1 , α 2 , . . . , α r 是线性无关向量组,将其化为标准正交向量组 e i , 且 e i 与 α i 等价。 设n维向量组\alpha_1,\alpha_2,...,\alpha_r是线性无关向量组,将其化为标准正交向量组e_i,且e_i与\alpha_i等价。 设n维向量组α1,α2,...,αr是线性无关向量组,将其化为标准正交向量组ei,且ei与αi等价。
过程:取 β 1 = α 1 ; 过程: 取 \beta_1=\alpha_1; 过程:取β1=α1;
β 2 = α 2 − [ β 1 , α 2 ] [ β 1 , β 1 ] β 1 ; . . . . . . . . . . \beta_2=\alpha_2-\frac{[\beta_1,\alpha_2]}{[\beta_1,\beta_1]}\beta_1;.......... β2=α2−[β1,β1][β1,α2]β1;..........
β r = α r − [ β 1 , α r ] [ β 1 , β 1 ] β 1 − [ β 2 , α r ] [ β 2 , β 2 ] β 2 − . . . − [ β r − 1 , α r ] [ β r − 1 , β r − 1 ] β r − 1 ; \beta_r=\alpha_r-\frac{[\beta_1,\alpha_r]}{[\beta_1,\beta_1]}\beta_1-\frac{[\beta_2,\alpha_r]}{[\beta_2,\beta_2]}\beta_2-...-\frac{[\beta_{r-1},\alpha_r]}{[\beta_{r-1},\beta_{r-1}]}\beta_{r-1}; βr=αr−[β1,β1][β1,αr]β1−[β2,β2][β2,αr]β2−...−[βr−1,βr−1][βr−1,αr]βr−1;
将其单位化
e
1
=
1
∣
∣
β
1
∣
∣
β
1
,
e
2
=
1
∣
∣
β
2
∣
∣
β
2
,
.
.
.
,
e
r
=
1
∣
∣
β
r
∣
∣
β
r
e_1=\frac{1}{||\beta_1||}\beta_1,e_2=\frac{1}{||\beta_2||}\beta_2,...,e_r=\frac{1}{||\beta_r||}\beta_r
e1=∣∣β1∣∣1β1,e2=∣∣β2∣∣1β2,...,er=∣∣βr∣∣1βr
从而为标准正交向量组。
对角矩阵:主对角线元素外其余元素全为0的方阵为对角矩阵,记为
Λ
=
d
i
a
g
(
λ
1
,
λ
2
,
.
.
.
,
λ
n
)
\Lambda=diag(\lambda_1,\lambda_2,...,\lambda_n)
Λ=diag(λ1,λ2,...,λn)
单位矩阵:主对角线上元素全为1的对角阵。
转置矩阵:将矩阵A的每一行换成同序数的列得到的新矩阵,称为A的转置矩阵。
(
A
T
)
T
=
A
;
(
A
+
B
)
T
=
A
T
+
B
T
;
(
λ
A
)
T
=
λ
A
T
;
(
A
B
)
T
=
B
T
A
T
(A^T)^T=A;(A+B)^T=A^T+B^T;(\lambda A)^T=\lambda A^T;(AB)^T=B^TA^T
(AT)T=A;(A+B)T=AT+BT;(λA)T=λAT;(AB)T=BTAT
可逆矩阵:对于给定的n阶方阵A,若存在一个n阶方阵B,满足AB=BA=E,则称矩阵A可逆,并称矩阵B为矩阵A的逆矩阵。
若矩阵A是可逆的,则A的逆矩阵唯一。
A
−
1
=
A
∗
∣
A
∣
;
(
A
−
1
)
−
1
=
A
;
(
λ
A
)
−
1
=
1
λ
A
−
1
;
(
A
B
)
−
1
=
B
−
1
A
−
1
;
(
A
T
)
−
1
=
(
A
−
1
)
T
A^{-1}=\frac{A^*}{|A|};(A^{-1})^{-1}=A;(\lambda A)^{-1}=\frac{1}{\lambda}A^{-1};(AB)^{-1}=B^{-1}A^{-1};(A^T)^{-1}=(A^{-1})^T
A−1=∣A∣A∗;(A−1)−1=A;(λA)−1=λ1A−1;(AB)−1=B−1A−1;(AT)−1=(A−1)T
相似矩阵:对于n阶方阵A,B,若存在可逆矩阵P,使
P
−
1
A
P
=
B
,
(
进行
n
次初等行变换与
B
相等
)
P^{-1}AP=B,(进行n次初等行变换与B相等)
P−1AP=B,(进行n次初等行变换与B相等)
则称B是A的相似矩阵,或者称矩阵A与矩阵B相似。
相似矩阵必等价;相似矩阵秩相同;相似矩阵有相同的行列式。
正交矩阵:若n阶方阵A满足
A
T
A
=
E
(
即
A
—
1
=
A
T
)
,
则称
A
为正交阵。
A^TA=E(即A^{—1}=A^T),则称A为正交阵。
ATA=E(即A—1=AT),则称A为正交阵。
若P为正交阵,则线性变换y=Px称为正交变换。
正交变换保持长度不变(即||y||=||x||)
∣ A ∣ = ∑ σ ∈ S n s g n ( σ ) ∏ i = 1 n a i , σ ( i ) , 其中 s g n ( ) 为逆序数。 |A|=\sum_{\sigma \in S_n}sgn(\sigma)\prod_{i=1}^{n}a_{i,\sigma(i)} ,其中sgn()为逆序数。 ∣A∣=σ∈Sn∑sgn(σ)i=1∏nai,σ(i),其中sgn()为逆序数。
∣ A B ∣ = ∣ A ∣ ∣ B ∣ ; ∣ A − 1 ∣ = ∣ A ∣ − 1 ; ∣ α A ∣ = α n ∣ A ∣ |AB|=|A||B|;|A^{-1}|=|A|^{-1};|\alpha A|=\alpha ^n|A| ∣AB∣=∣A∣∣B∣;∣A−1∣=∣A∣−1;∣αA∣=αn∣A∣
偏导数反映的是函数沿坐标轴方向的变化率。
f
x
i
‘
=
δ
f
δ
x
i
=
lim
Δ
x
→
0
f
(
x
1
,
.
.
.
,
x
i
+
Δ
x
i
,
.
.
.
,
x
n
)
f
(
x
1
,
.
.
,
x
i
,
.
.
.
,
x
n
)
f^`_{x_i}=\frac{\delta f}{\delta x_i}=\lim_{\Delta x\rightarrow 0}\frac{f(x_1,...,x_i+\Delta x_i,...,x_n)}{f(x_1,..,x_i,...,x_n)}
fxi‘=δxiδf=Δx→0limf(x1,..,xi,...,xn)f(x1,...,xi+Δxi,...,xn)
高阶偏导数与求导次序无关
δ
δ
y
(
δ
z
δ
x
)
=
δ
2
z
δ
x
δ
y
=
f
x
y
(
x
,
y
)
\frac{\delta}{\delta y}(\frac{\delta z}{\delta x})=\frac{\delta ^2 z}{\delta x\delta y}=f_{xy}(x,y)
δyδ(δxδz)=δxδyδ2z=fxy(x,y)
方向导数就是函数f在点p沿方向L的变化率。当L为坐标轴时,为特殊的方向导数,即偏导数。
∇
f
(
x
)
=
(
δ
f
δ
x
1
,
δ
f
δ
x
2
,
.
.
.
,
δ
f
δ
x
n
)
T
一般写成列向量,故写成转置形式。
\nabla f(x)=(\frac{\delta f}{\delta x_1},\frac{\delta f}{\delta x_2},...,\frac{\delta f}{\delta x_n})^T\\ 一般写成列向量,故写成转置形式。
∇f(x)=(δx1δf,δx2δf,...,δxnδf)T一般写成列向量,故写成转置形式。
应用于梯度下降法和牛顿法等。
梯度可以看成一元函数,它的导数对多元函数的推广。
对于多元函数,它的自变量有n个,它的梯度就是一个向量:它是f对其n个自变量x的偏导数构成的向量叫做梯度。一般表示为列向量。
梯度与方向向量的夹角a,
当a=0时,方向向量与梯度方向相同,函数f增长最快,此时,函数在这个方向的方向导数达到最大值,这个最大值就是梯度的模。
当a=PI,即方向向量与梯度方向相反,函数f减少最快,函数在这个方向的方向导数达到最小值。
当a=PI/2,方向向量与梯度方向正交,函数的变化率为0。
一阶偏导数构成的矩阵。简化求导公式:简化对多元函数的求导。
应用于人工神经网络反向传播算法推导过程中。
y
=
f
(
x
)
;
y
i
=
f
i
(
x
)
;
x
为
n
维向量,
y
为
m
维向量
y=f(x);\quad y_i=f_i(x);\quad x为n维向量,y为m维向量
y=f(x);yi=fi(x);x为n维向量,y为m维向量
[ δ y 1 δ x 1 δ y 1 δ x 2 . . . δ y 1 δ x n δ y 2 δ x 1 δ y 2 δ x 2 . . . δ y 2 δ x n . . . . . . . . . . . . δ y m δ x 1 δ y m δ x 2 . . . δ y m δ x n ] \left[\begin{matrix}\frac{\delta y_1}{\delta x_1}\quad \frac{\delta y_1}{\delta x_2}\quad...\quad\frac{\delta y_1}{\delta x_n}\\\\\frac{\delta y_2}{\delta x_1}\quad \frac{\delta y_2}{\delta x_2}\quad...\quad\frac{\delta y_2}{\delta x_n}\\\\...\quad...\quad...\quad...\\\\\frac{\delta y_m}{\delta x_1}\quad \frac{\delta y_m}{\delta x_2}\quad...\quad\frac{\delta y_m}{\delta x_n}\end{matrix}\right] ⎣ ⎡δx1δy1δx2δy1...δxnδy1δx1δy2δx2δy2...δxnδy2............δx1δymδx2δym...δxnδym⎦ ⎤
例: u = x 2 + 2 x y + z v = x − y 2 + z 2 例:u=x^2+2xy+z\quad v=x-y^2+z^2\quad 例:u=x2+2xy+zv=x−y2+z2
[ u v ] [ x y z ] \left[\begin{matrix}u\\v\end{matrix}\right]\quad \left[\begin{matrix}x\\y\\z\end{matrix}\right] [uv]⎣ ⎡xyz⎦ ⎤
[ 2 x + 2 y 2 x 1 1 − 2 y 2 z ] \left[\begin{matrix}2x+2y\quad 2x \quad 1\\\quad1\quad\quad -2y\quad 2z\end{matrix}\right] [2x+2y2x11−2y2z]
是一个对称矩阵
针对多元函数来说,作用相当于一元函数的二阶导数。
[
δ
2
f
δ
x
1
δ
x
1
δ
2
f
δ
x
1
δ
x
2
.
.
.
δ
2
f
δ
x
1
δ
x
n
δ
2
f
δ
x
2
δ
x
1
δ
2
f
δ
x
2
δ
x
2
.
.
.
δ
2
f
δ
x
2
δ
x
n
.
.
.
.
.
.
.
.
.
.
.
.
δ
2
f
δ
x
n
δ
x
1
δ
2
f
δ
x
n
δ
x
2
.
.
.
δ
2
f
δ
x
n
δ
x
n
]
\left[\begin{matrix}\frac{\delta^2 f}{\delta x_1\delta x_1}\quad \frac{\delta^2 f}{\delta x_1\delta x_2}\quad...\quad\frac{\delta^2 f}{\delta x_1\delta x_n}\\\\\frac{\delta^2 f}{\delta x_2\delta x_1}\quad \frac{\delta^2 f}{\delta x_2\delta x_2}\quad...\quad\frac{\delta^2 f}{\delta x_2\delta x_n}\\\\...\quad...\quad...\quad...\\\\\frac{\delta^2 f}{\delta x_n\delta x_1}\quad \frac{\delta^2 f}{\delta x_n\delta x_2}\quad...\quad\frac{\delta^2 f}{\delta x_n\delta x_n}\end{matrix}\right]
⎣
⎡δx1δx1δ2fδx1δx2δ2f...δx1δxnδ2fδx2δx1δ2fδx2δx2δ2f...δx2δxnδ2f............δxnδx1δ2fδxnδx2δ2f...δxnδxnδ2f⎦
⎤
例: f ( x , y , z ) = 2 x 2 − x y + y 3 − 3 z 2 例:f(x,y,z)=2x^2-xy+y^3-3z^2 例:f(x,y,z)=2x2−xy+y3−3z2
[ 4 − 1 0 − 1 2 0 0 0 − 6 ] \left[\begin{matrix}4\quad\quad-1\quad0\\-1\quad\quad2\quad\quad0\\\quad\quad0\quad\quad0\quad-6\end{matrix}\right] ⎣ ⎡4−10−12000−6⎦ ⎤
Hessian矩阵与多元函数的凹凸性:正定为下凸函数,负定为上凸函数。
实二次型 f = x T A x , x ≠ 0 , f > 0 , 则 f 为正定二次型,对称矩阵 A 为正定矩阵。 实二次型f=x^TAx,x\neq0,f>0,则f为正定二次型,对称矩阵A为正定矩阵。 实二次型f=xTAx,x=0,f>0,则f为正定二次型,对称矩阵A为正定矩阵。
矩阵合同于单位矩阵则为正定矩阵。
对于对称矩阵A,A的特征值全为正,则为正定矩阵;
如果A的各阶顺序主子式都为正,则为正定矩阵。
若技术阶顺序主子式为负,偶数阶顺序注意事项为正,则为负定矩阵。
导数与函数单调性的关系
极值定理
导数与函数凹凸性关系
如果Hessian矩阵正定,相当于二阶导数>0,函数在该点有极小值;
如果Hessian矩阵负定,相当于二阶导数<0,函数在该点有极大值;
如果Hessian矩阵不定,还需看更高阶的导数。
f = x T A x , 矩阵 A 为对称矩阵, x 为列向量。 f=x^TAx,\quad 矩阵A为对称矩阵,x为列向量。 f=xTAx,矩阵A为对称矩阵,x为列向量。
注:在知识向量机、逻辑线性回归等算法中,写表达式时常用二次型表示。
对 n 阶方阵 A ,若存在数 λ 和 n 维非零向量 x ,使得 A x = λ x 成立,则 λ 为方阵 A 的特征值,非零向量 x 为 A 的对应于特征值 λ 的特征向量。 对n阶方阵A,若存在数\lambda 和n维非零向量x,使得Ax=\lambda x成立,则\lambda 为方阵A的特征值,非零向量x为A的对应于特征值\lambda 的特征向量。 对n阶方阵A,若存在数λ和n维非零向量x,使得Ax=λx成立,则λ为方阵A的特征值,非零向量x为A的对应于特征值λ的特征向量。
( 1 ) λ 1 + λ 2 + λ 3 + . . . + λ n = a 11 + a 22 + . . . + a n n (1) \lambda_1+\lambda_2+\lambda_3+...+\lambda_n=a_{11}+a_{22}+...+a_{nn} (1)λ1+λ2+λ3+...+λn=a11+a22+...+ann
( 2 ) λ 1 λ 2 . . . λ n = ∣ A ∣ (2) \lambda_1\lambda_2...\lambda_n=|A| (2)λ1λ2...λn=∣A∣
( 3 ) ( A − λ E ) x = 0 (3) (A-\lambda E)x=0 (3)(A−λE)x=0
应用于主成分分析、流形学习、线性判别分析等。
( 1 ) 若 λ 1 , λ 2 是实对称矩阵 A 的两个特征值, p 1 , p 2 是对应的特征向量,若 λ 1 ≠ λ 2 , 则 p 1 与 p 2 正交。 (1) 若\lambda_1,\lambda_2是实对称矩阵A的两个特征值,p_1,p_2是对应的特征向量,若\lambda_1\neq\lambda_2,则p_1与p_2正交。 (1)若λ1,λ2是实对称矩阵A的两个特征值,p1,p2是对应的特征向量,若λ1=λ2,则p1与p2正交。
( 2 ) 对于 n 阶实对称矩阵 A ,必存在正交阵 P ,使 P − 1 A P = Λ , 其中 Λ 是以 A 的 n 个特征值为对角元素的对角阵, P 是由 λ 对应的特征向量正交单位化后组成的。 (2) 对于n阶实对称矩阵A,必存在正交阵P,使P^{-1}AP=\Lambda,其中\Lambda是以A的n个特征值为对角元素的对角阵,\\ P是由\lambda对应的特征向量正交单位化后组成的。 (2)对于n阶实对称矩阵A,必存在正交阵P,使P−1AP=Λ,其中Λ是以A的n个特征值为对角元素的对角阵,P是由λ对应的特征向量正交单位化后组成的。
P Λ P − 1 = A P\Lambda P^{-1}=A PΛP−1=A
二元函数在点(x_k,y_k)处的泰勒展开式为:
f
(
x
,
y
)
=
f
(
x
k
,
y
k
)
+
(
x
−
x
k
)
f
‘
x
(
x
k
,
y
k
)
+
(
y
−
y
k
)
f
‘
y
(
x
k
,
y
k
)
+
1
2
!
(
x
−
x
k
)
2
f
‘
‘
x
x
(
x
k
,
y
k
)
+
1
2
!
(
x
−
x
k
)
(
y
−
y
k
)
f
‘
‘
x
y
(
x
k
,
y
k
)
+
1
2
!
(
x
−
x
k
)
(
y
−
y
k
)
f
‘
‘
y
x
(
x
k
,
y
k
)
+
1
2
!
(
y
−
y
k
)
2
f
‘
‘
y
y
(
x
k
,
y
k
)
+
o
n
f(x,y)=f(x_k,y_k)+(x-x_k)f`_x(x_k,y_k)+(y-y_k)f`_y(x_k,y_k)+\frac{1}{2!}(x-x_k)^2f``_{xx}(x_k,y_k)+\frac{1}{2!}(x-x_k)(y-y_k)f``_{xy}(x_k,y_k)\\ +\frac{1}{2!}(x-x_k)(y-y_k)f``_{yx}(x_k,y_k)+\frac{1}{2!}(y-y_k)^2f``_{yy}(x_k,y_k)+o^n
f(x,y)=f(xk,yk)+(x−xk)f‘x(xk,yk)+(y−yk)f‘y(xk,yk)+2!1(x−xk)2f‘‘xx(xk,yk)+2!1(x−xk)(y−yk)f‘‘xy(xk,yk)+2!1(x−xk)(y−yk)f‘‘yx(xk,yk)+2!1(y−yk)2f‘‘yy(xk,yk)+on
多元函数在点x_k处的泰勒展开式为:
f
(
x
1
,
x
2
,
.
.
.
,
x
n
)
=
f
(
x
k
1
,
x
k
2
,
.
.
.
,
x
k
n
)
+
∑
i
=
1
n
(
x
i
−
x
k
i
)
f
‘
x
i
(
x
k
1
,
x
k
2
,
.
.
.
,
x
k
n
)
+
1
2
!
∑
i
,
j
=
1
n
(
x
i
−
x
k
i
)
(
x
j
−
x
k
j
)
f
‘
‘
i
j
(
x
k
1
,
x
k
2
,
.
.
.
,
x
k
n
)
+
o
n
f(x^1,x^2,...,x^n)=f(x^1_k,x^2_k,...,x^n_k)+\sum_{i=1}^n(x^i-x^i_k)f`_{x^i}(x^1_k,x^2_k,...,x^n_k)+\frac{1}{2!}\sum^n_{i,j=1}(x^i-x_k^i)(x^j-x_k^j)f``_{ij}(x^1_k,x^2_k,...,x^n_k)+o^n
f(x1,x2,...,xn)=f(xk1,xk2,...,xkn)+i=1∑n(xi−xki)f‘xi(xk1,xk2,...,xkn)+2!1i,j=1∑n(xi−xki)(xj−xkj)f‘‘ij(xk1,xk2,...,xkn)+on
矩阵形式:
f
(
x
)
=
f
(
x
k
)
+
(
∇
f
(
x
k
)
)
T
(
x
−
x
k
)
+
1
2
!
(
x
−
x
k
)
T
H
(
x
k
)
(
x
−
x
k
)
+
o
(
∣
∣
x
−
x
0
∣
∣
2
)
f(x)=f(x_k)+(\nabla f(x_k))^T(x-x_k)+\frac{1}{2!}(x-x_k)^TH(x_k)(x-x_k)+o(||x-x_0||^2)
f(x)=f(xk)+(∇f(xk))T(x−xk)+2!1(x−xk)TH(xk)(x−xk)+o(∣∣x−x0∣∣2)
其中: H ( x k ) = [ δ 2 f ( x k ) δ x 1 δ x 1 δ 2 f ( x k ) δ x 1 δ x 2 . . . δ 2 f ( x k ) δ x 1 δ x n δ 2 f ( x k ) δ x 2 δ x 1 δ 2 f ( x k ) δ x 2 δ x 2 . . . δ 2 f ( x k ) δ x 2 δ x n . . . . . . . . . . . . δ 2 f ( x k ) δ x n δ x 1 δ 2 f ( x k ) δ x n δ x 2 . . . δ 2 f ( x k ) δ x n δ x n ] H 为 H e s s i a n 矩阵 其中:H(x_k)=\left[\begin{matrix}\frac{\delta^2 f(x_k)}{\delta x_1\delta x_1}\quad \frac{\delta^2 f(x_k)}{\delta x_1\delta x_2}\quad...\quad\frac{\delta^2 f(x_k)}{\delta x_1\delta x_n}\\\\\frac{\delta^2 f(x_k)}{\delta x_2\delta x_1}\quad \frac{\delta^2 f(x_k)}{\delta x_2\delta x_2}\quad...\quad\frac{\delta^2 f(x_k)}{\delta x_2\delta x_n}\\\\...\quad...\quad...\quad...\\\\\frac{\delta^2 f(x_k)}{\delta x_n\delta x_1}\quad \frac{\delta^2 f(x_k)}{\delta x_n\delta x_2}\quad...\quad\frac{\delta^2 f(x_k)}{\delta x_n\delta x_n}\end{matrix}\right]\quad H为Hessian矩阵 其中:H(xk)=⎣ ⎡δx1δx1δ2f(xk)δx1δx2δ2f(xk)...δx1δxnδ2f(xk)δx2δx1δ2f(xk)δx2δx2δ2f(xk)...δx2δxnδ2f(xk)............δxnδx1δ2f(xk)δxnδx2δ2f(xk)...δxnδxnδ2f(xk)⎦ ⎤H为Hessian矩阵
∇ w T x = w 两个向量做内积求梯度等于本身。 w T x = ∑ i = 1 n w i x i \nabla w^Tx=w\quad 两个向量做内积求梯度等于本身。w^Tx=\sum_{i=1}^nw_ix_i ∇wTx=w两个向量做内积求梯度等于本身。wTx=i=1∑nwixi
∇ x T A x = ( A + A T ) x 二次型 x T A x = ∑ i = 1 n ∑ j = 1 n a i j x i x j \nabla x^TAx=(A+A^T)x\quad 二次型\quad x^TAx=\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j ∇xTAx=(A+AT)x二次型xTAx=i=1∑nj=1∑naijxixj
∇ 2 x T A x = A + A T ∇ 2 为求 H e s s i a n 矩阵 \nabla^2 x^TAx=A+A^T\quad \nabla^2为求Hessian矩阵 ∇2xTAx=A+AT∇2为求Hessian矩阵
A为m x n的矩阵,可以分解为三个矩阵的乘积
A
=
U
Σ
V
T
,
U
、
V
为正交矩阵,
Σ
为对角矩阵。
A=U\Sigma V^T\quad,U、V为正交矩阵,\Sigma为对角矩阵。
A=UΣVT,U、V为正交矩阵,Σ为对角矩阵。
Σ 是 m × n 的矩阵,主对角线元素为非零,其他地方为 1 。 \Sigma是m\times n的矩阵,主对角线元素为非零,其他地方为1。 Σ是m×n的矩阵,主对角线元素为非零,其他地方为1。
U 是 A A T 的正交化的特征向量所构成的矩阵。 A 是 m × n 的矩阵, U 是 m × m 的矩阵。 U是AA^T的正交化的特征向量所构成的矩阵。A是m\times n的矩阵,U是m\times m 的矩阵。 U是AAT的正交化的特征向量所构成的矩阵。A是m×n的矩阵,U是m×m的矩阵。
V 是 A T A 的正交化的特征向量所构成的矩阵。 A 是 m × n 的矩阵, V 是 n × n 的矩阵。 V是A^TA的正交化的特征向量所构成的矩阵。A是m\times n的矩阵,V是 n\times n 的矩阵。 V是ATA的正交化的特征向量所构成的矩阵。A是m×n的矩阵,V是n×n的矩阵。
应用于:推荐系统、自然语言处理中的主题分析中。
条件概率:两个事件 a 和 b , a 发生的前提下 b 发生的概率为 p ( b ∣ a ) = p ( a , b ) p ( a ) 条件概率:两个事件a和b,a发生的前提下b发生的概率为\quad p(b|a)=\frac{p(a,b)}{p(a)} 条件概率:两个事件a和b,a发生的前提下b发生的概率为p(b∣a)=p(a)p(a,b)
先验概率为 p ( b ∣ a ) , 后验概率为 p ( a ∣ b ) , 则贝叶斯公式: p ( a ∣ b ) = p ( a ) p ( b ∣ a ) p ( b ) 先验概率为p(b|a),后验概率为p(a|b),则贝叶斯公式:p(a|b)=\frac{p(a)p(b|a)}{p(b)} 先验概率为p(b∣a),后验概率为p(a∣b),则贝叶斯公式:p(a∣b)=p(b)p(a)p(b∣a)
注:在机器学习、深度学习中经常使用一种最大化后验概率的思想。
p ( b ∣ a ) = p ( b ) p(b|a)=p(b) p(b∣a)=p(b)
p ( a 1 , . . . , a n ) = ∏ i = 1 n p ( a i ) p(a_1,...,a_n)=\prod_{i=1}^n p(a_i) p(a1,...,an)=i=1∏np(ai)
设X是一个随机变量,x是任意实数,函数
F
(
x
)
=
P
X
≤
x
,
称为
X
的分布函数。
F(x)=P{X\leq x},\quad 称为X的分布函数。
F(x)=PX≤x,称为X的分布函数。
注:(1)分布函数主要研究随机变量在某一区间内取值的概率情况。
(2)分布函数F(x)是x的一个普通实函数。
(3)分布函数F(x)是一个不减函数。
P
{
x
1
<
X
≤
x
2
}
=
P
{
X
≤
x
2
}
−
P
{
X
≤
x
1
}
=
F
(
x
2
)
−
F
(
x
1
)
P{\{x_1<X\leq x_2}\}=P{\{X\leq x_2}\}-P{\{X\leq x_1}\}=F(x_2)-F(x_1)
P{x1<X≤x2}=P{X≤x2}−P{X≤x1}=F(x2)−F(x1)
P { x 1 ≤ X ≤ x 2 } = P { X ≤ x 2 } − P { X ≤ x 1 } + P { X = x 1 } = F ( x 2 ) − F ( x 1 ) + P { X = x 1 } P{\{x_1\leq X\leq x_2}\}=P{\{X\leq x_2}\}-P{\{X\leq x_1}\}+P{\{X=x_1}\}=F(x_2)-F(x_1)+P{\{X=x_1}\} P{x1≤X≤x2}=P{X≤x2}−P{X≤x1}+P{X=x1}=F(x2)−F(x1)+P{X=x1}
随机变量分为离散型和连续型(取值为无限不可列个)。
连续型随机变量:一般地,对于随机变量X的分布函数F(x),若存在非负函数f(x),使对于任意实数x有
F
(
x
)
=
∫
−
∞
x
f
(
t
)
d
t
,
F(x)=\int^x_{-\infty}f(t)dt,
F(x)=∫−∞xf(t)dt,
则称X为连续型随机变量,其中函数f(x)称为X的概率密度函数,简称概率密度。
方差表达了X的取值与其数学期望的偏离程度,是衡量X取值分散程度的一个尺度。
E
(
x
)
=
∑
x
i
p
(
x
i
)
E
(
x
)
=
∫
−
∞
+
∞
x
f
(
x
)
d
x
D
(
x
)
=
∑
(
x
i
−
E
(
x
)
)
2
p
(
x
i
)
D
(
x
)
=
∫
−
∞
+
∞
(
x
−
E
(
x
)
)
2
f
(
x
)
d
x
E(x)=\sum x_ip(x_i)\\E(x)=\int_{-\infty}^{+\infty}xf(x)dx\\D(x)=\sum(x_i-E(x))^2p(x_i)\\D(x)=\int_{-\infty}^{+\infty}(x-E(x))^2f(x)dx
E(x)=∑xip(xi)E(x)=∫−∞+∞xf(x)dxD(x)=∑(xi−E(x))2p(xi)D(x)=∫−∞+∞(x−E(x))2f(x)dx
二项分布:X~B(n,p),当n=1时,就是(0—1)分布。
P
{
X
=
k
}
=
C
n
k
p
k
(
1
−
p
)
n
−
k
,
k
=
0
,
1
,
2
,
.
.
.
,
n
.
P{\{X=k}\}=C_n^kp^k(1-p)^{n-k},k=0,1,2,...,n.
P{X=k}=Cnkpk(1−p)n−k,k=0,1,2,...,n.
当n很大、p很小时,二项分布的泊松逼近。
C
n
k
p
k
(
1
−
p
)
n
−
k
=
λ
k
e
−
λ
k
!
C_n^kp^k(1-p)^{n-k}=\frac{\lambda^ke^{-\lambda}}{k!}
Cnkpk(1−p)n−k=k!λke−λ
泊松定理:
设
λ
>
0
是一个常数,
n
是任意正整数,设
n
p
n
=
λ
,则对于任一固定的非负整数
k
,有
lim
n
→
+
∞
C
n
k
p
n
k
(
1
−
p
n
)
n
−
k
=
λ
k
e
−
λ
k
!
设\lambda>0是一个常数,n是任意正整数,设np_n=\lambda,则对于任一固定的非负整数k,有\\ \lim_{n\rightarrow+\infty}C_n^kp_n^k(1-p_n)^{n-k}=\frac{\lambda^ke^{-\lambda}}{k!}
设λ>0是一个常数,n是任意正整数,设npn=λ,则对于任一固定的非负整数k,有n→+∞limCnkpnk(1−pn)n−k=k!λke−λ
泊松分布:
设随机变量
X
所有可能取值为
0
,
1
,
2
,
.
.
.
,而取各个值的概率为
P
{
X
=
k
}
=
λ
k
e
−
λ
k
!
,
k
=
0
,
1
,
.
.
.
,
其中
λ
>
0
是常数,则称
X
服从参数为
λ
的泊松分布,记为
X
∼
π
(
λ
)
设随机变量X所有可能取值为0,1,2,...,而取各个值的概率为\\ P{\{X=k}\}=\frac{\lambda^ke^{-\lambda}}{k!},k=0,1,...,\\ 其中\lambda>0是常数,则称X服从参数为\lambda的泊松分布,记为X\sim \pi(\lambda)
设随机变量X所有可能取值为0,1,2,...,而取各个值的概率为P{X=k}=k!λke−λ,k=0,1,...,其中λ>0是常数,则称X服从参数为λ的泊松分布,记为X∼π(λ)
均匀分布:X~U(a,b)
KaTeX parse error: Can't use function '$' in math mode at position 78: …x>b \end{cases}$̲
正态分布:
设连续型随机变量
X
的概率密度为
f
(
x
)
=
1
2
π
σ
e
−
(
x
−
μ
)
2
2
σ
2
,
−
∞
<
x
<
+
∞
,
其中
μ
,
σ
(
σ
>
0
)
为常数,则称
X
服从参数为
μ
,
σ
的正态分布或高斯
(
G
a
u
s
s
)
分布,记为
X
N
˜
(
μ
,
σ
2
)
.
当
x
=
μ
时,
f
(
x
)
取最大值为
1
2
π
σ
μ
为位置参数,
μ
为期望,
σ
为标准差。
σ
改变,图形形状高低改变,
σ
越小,最高点越高,
f
越大。
设连续型随机变量X的概率密度为\\ f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}},-\infty<x<+\infty,\\ 其中\mu,\sigma(\sigma>0)为常数,则称X服从参数为\mu,\sigma的正态分布或高斯(Gauss)分布,记为X\~N(\mu,\sigma^2).\\ 当x=\mu时,f(x)取最大值为\frac{1}{\sqrt{2\pi}\sigma}\\ \mu为位置参数,\mu为期望,\sigma为标准差。\\ \sigma改变,图形形状高低改变,\sigma越小,最高点越高,f越大。
设连续型随机变量X的概率密度为f(x)=2π
σ1e−2σ2(x−μ)2,−∞<x<+∞,其中μ,σ(σ>0)为常数,则称X服从参数为μ,σ的正态分布或高斯(Gauss)分布,记为XN˜(μ,σ2).当x=μ时,f(x)取最大值为2π
σ1μ为位置参数,μ为期望,σ为标准差。σ改变,图形形状高低改变,σ越小,最高点越高,f越大。
X 的分布函数为 F ( x ) = 1 2 π σ ∫ − ∞ x e − ( t − μ ) 2 2 σ 2 d t X的分布函数为F(x)=\frac{1}{\sqrt{2\pi}\sigma}\int_{-\infty}^xe^{-\frac{(t-\mu)^2}{2\sigma^2}}dt X的分布函数为F(x)=2π σ1∫−∞xe−2σ2(t−μ)2dt
标准正态分布:X~N(0,1)
当
μ
=
0
,
σ
=
1
时称
X
服从标准正态分布,其概率密度和分布函数分别用
φ
(
x
)
和
Φ
(
x
)
表示,即有:
φ
(
x
)
=
1
2
π
e
−
x
2
2
Φ
(
x
)
=
1
2
π
∫
−
∞
x
e
−
t
2
2
d
t
易知:
Φ
(
−
x
)
=
1
−
Φ
(
x
)
一般正态分布化成标准正态分布:
Z
=
X
−
μ
σ
∼
N
(
0
,
1
)
当\mu=0,\sigma=1时称X服从标准正态分布,其概率密度和分布函数分别用\varphi(x)和\Phi(x)表示,即有:\\ \varphi(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}\\ \Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^xe^{-\frac{t^2}{2}}dt\\ 易知:\Phi(-x)=1-\Phi(x)\\ 一般正态分布化成标准正态分布:Z=\frac{X-\mu}{\sigma}\sim N(0,1)
当μ=0,σ=1时称X服从标准正态分布,其概率密度和分布函数分别用φ(x)和Φ(x)表示,即有:φ(x)=2π
1e−2x2Φ(x)=2π
1∫−∞xe−2t2dt易知:Φ(−x)=1−Φ(x)一般正态分布化成标准正态分布:Z=σX−μ∼N(0,1)
设(X,Y)是二维随机变量,对于任意的实数x,y,二元函数
F
(
x
,
y
)
=
P
{
(
X
≤
x
)
⋂
(
Y
≤
y
)
}
=
P
{
X
≤
x
,
Y
≤
y
}
F(x,y)=P{\{(X\leq x)\bigcap(Y\leq y)\}}=P{\{X\leq x,Y\leq y\}}
F(x,y)=P{(X≤x)⋂(Y≤y)}=P{X≤x,Y≤y}
称为二维随机变量(X,Y)的分布函数,或称为随机变量X和Y的联合分布函数。
F x ( x ) = P { X ≤ x } = P { X ≤ x , Y < + ∞ } = F ( x , + ∞ ) 即 F x ( x ) = F ( x , + ∞ ) 只要在函数 F ( x , y ) 中令 y → + ∞ 就能得到 F x ( x ) . F_x(x)=P{\{X\leq x\}}=P{\{X\leq x,Y<+\infty\}}=F(x,+\infty)\\ 即 F_x(x)=F(x,+\infty)\\ 只要在函数F(x,y)中令y\rightarrow+\infty就能得到F_x(x). Fx(x)=P{X≤x}=P{X≤x,Y<+∞}=F(x,+∞)即Fx(x)=F(x,+∞)只要在函数F(x,y)中令y→+∞就能得到Fx(x).
离散型:
F
x
(
x
)
=
F
(
x
,
+
∞
)
=
∑
x
i
≤
x
∑
j
=
1
+
∞
p
i
j
由
X
分布函数定义知
X
的分布律为
P
i
⋅
=
P
{
X
=
x
i
}
=
∑
j
=
1
+
∞
p
i
j
,
j
=
1
,
2
,
.
.
.
F_x(x)=F(x,+\infty)=\sum_{x_i\leq x}\sum_{j=1}^{+\infty}p_{ij}\\ 由X分布函数定义知X的分布律为\\ P_{i·}=P{\{X=x_i\}}=\sum_{j=1}^{+\infty}p_{ij},j=1,2,...
Fx(x)=F(x,+∞)=xi≤x∑j=1∑+∞pij由X分布函数定义知X的分布律为Pi⋅=P{X=xi}=j=1∑+∞pij,j=1,2,...
连续型:
对于连续型随机变量
(
X
,
Y
)
,
设它的概率密度为
f
(
x
,
y
)
,
由
F
x
(
x
)
=
F
(
x
,
+
∞
)
=
∫
−
∞
x
[
∫
−
∞
+
∞
f
(
x
,
y
)
d
y
]
d
x
知道,
X
是一个连续型随机变量,且其概率密度为
f
X
(
x
)
=
∫
−
∞
+
∞
f
(
x
,
y
)
d
y
,
同样,
Y
也是一个连续型随机变量,且其概率密度为
f
Y
(
y
)
=
∫
−
∞
+
∞
f
(
x
,
y
)
d
x
分别称
f
X
(
x
)
,
f
Y
(
y
)
为
(
X
,
Y
)
关于
X
和
Y
的边缘概率密度。
对于连续型随机变量(X,Y),设它的概率密度为f(x,y),由\\ F_x(x)=F(x,+\infty)=\int_{-\infty}^x{[\int_{-\infty}^{+\infty}f(x,y)dy]}dx\\ 知道,X是一个连续型随机变量,且其概率密度为\\ f_X(x)=\int_{-\infty}^{+\infty}f(x,y)dy,\\ 同样,Y也是一个连续型随机变量,且其概率密度为\\ f_Y(y)=\int_{-\infty}^{+\infty}f(x,y)dx\\ 分别称f_X(x),f_Y(y)为(X,Y)关于X和Y的边缘概率密度。
对于连续型随机变量(X,Y),设它的概率密度为f(x,y),由Fx(x)=F(x,+∞)=∫−∞x[∫−∞+∞f(x,y)dy]dx知道,X是一个连续型随机变量,且其概率密度为fX(x)=∫−∞+∞f(x,y)dy,同样,Y也是一个连续型随机变量,且其概率密度为fY(y)=∫−∞+∞f(x,y)dx分别称fX(x),fY(y)为(X,Y)关于X和Y的边缘概率密度。
条件密度:
f
(
x
1
∣
x
2
)
=
f
(
x
1
,
x
2
)
f
(
x
2
)
f(x_1|x_2)=\frac{f(x_1,x_2)}{f(x_2)}
f(x1∣x2)=f(x2)f(x1,x2)
f ( x 1 , x 2 ) = f ( x 1 ) f ( x 2 ) f(x_1,x_2)=f(x_1)f(x_2) f(x1,x2)=f(x1)f(x2)
表征X与Y之间相互关系的数字特征。
如果两个变量X与Y是相互独立的,则Cov(X,Y)=0
量
E
{
[
X
−
E
(
X
)
]
[
Y
−
E
(
Y
)
]
}
称为随机变量
X
与
Y
的协方差,记为
C
o
v
(
X
,
Y
)
,
即
C
o
v
(
X
,
Y
)
=
E
{
[
X
−
E
(
X
)
]
[
Y
−
E
(
Y
)
]
}
,
而
ρ
X
Y
=
C
o
v
(
X
,
Y
)
D
(
X
)
D
(
Y
)
称为随机变量
X
与
Y
的相关系数。
ρ
X
Y
是一个无量纲的量。
对于任意两个随机变量
X
和
Y
:
D
(
X
+
Y
)
=
D
(
X
)
+
D
(
Y
)
+
2
C
o
v
(
X
,
Y
)
,
C
o
v
(
X
,
Y
)
=
E
(
X
,
Y
)
−
E
(
X
)
E
(
Y
)
量E{\{[X-E(X)][Y-E(Y)]\}}称为随机变量X与Y的协方差,记为Cov(X,Y),即\\ Cov(X,Y)=E{\{[X-E(X)][Y-E(Y)]\}},\\ 而\rho_{XY}=\frac{Cov(X,Y)}{\sqrt{D(X)}\sqrt{D(Y)}}\\ 称为随机变量X与Y的相关系数。\\ \rho_{XY}是一个无量纲的量。\\ 对于任意两个随机变量X和Y:D(X+Y)=D(X)+D(Y)+2Cov(X,Y),\\ Cov(X,Y)=E(X,Y)-E(X)E(Y)
量E{[X−E(X)][Y−E(Y)]}称为随机变量X与Y的协方差,记为Cov(X,Y),即Cov(X,Y)=E{[X−E(X)][Y−E(Y)]},而ρXY=D(X)
D(Y)
Cov(X,Y)称为随机变量X与Y的相关系数。ρXY是一个无量纲的量。对于任意两个随机变量X和Y:D(X+Y)=D(X)+D(Y)+2Cov(X,Y),Cov(X,Y)=E(X,Y)−E(X)E(Y)
设 n 维随机变量 ( X 1 , X 2 , . . . , X n ) 的二阶混合中心距 C i j = C o v ( X i , X j ) = E { [ X i − E ( X i ) ] [ X j − E ( X j ) ] } , i , j = 1 , 2 , . . . , n 都存在,则称矩阵 C = [ C 11 C 12 . . . C 1 n C 21 C 22 . . . C 2 n . . . . . . . . . . . . C n 1 C n 2 . . . C n n ] 为 n 维随机变量 ( X 1 , X 2 , . . . , X n ) 的协方差矩阵。 ( 由于 C i j = C j i ,所以是对称矩阵 ) 设n维随机变量(X_1,X_2,...,X_n)的二阶混合中心距\\ C_{ij}=Cov(X_i,X_j)=E{\{[X_i-E(X_i)][X_j-E(X_j)]\}},i,j=1,2,...,n\\ 都存在,则称矩阵\\ C=\left[\begin{matrix}C_{11}\quad C_{12}\quad ...\quad C_{1n}\\C_{21}\quad C_{22}\quad ...\quad C_{2n}\\...\quad ...\quad ...\quad...\\C_{n1}\quad C_{n2}\quad ...\quad C_{nn}\end{matrix}\right]\\ 为n维随机变量(X_1,X_2,...,X_n)的协方差矩阵。(由于C_{ij}=C_{ji},所以是对称矩阵) 设n维随机变量(X1,X2,...,Xn)的二阶混合中心距Cij=Cov(Xi,Xj)=E{[Xi−E(Xi)][Xj−E(Xj)]},i,j=1,2,...,n都存在,则称矩阵C=⎣ ⎡C11C12...C1nC21C22...C2n............Cn1Cn2...Cnn⎦ ⎤为n维随机变量(X1,X2,...,Xn)的协方差矩阵。(由于Cij=Cji,所以是对称矩阵)
多元正态分布: n 维正态随机变量 ( X 1 , X 2 , . . . , X n ) 的概率密度定义为 f ( x 1 , x 2 , . . . , x n ) = 1 ( 2 π ) 2 ∣ C ∣ 1 / 2 e [ − 1 2 ( X − μ ) T C − 1 ( X − μ ) ] 其中 C 是 ( X 1 , X 2 , . . . , X n ) 的协方差矩阵。 多元正态分布:n维正态随机变量(X_1,X_2,...,X_n)的概率密度定义为\\ f(x_1,x_2,...,x_n)=\frac{1}{(2\pi)^2|C|^{1/2}}e^{[-\frac{1}{2}(X-\mu)^TC^{-1}(X-\mu)]}\\ 其中C是(X_1,X_2,...,X_n)的协方差矩阵。 多元正态分布:n维正态随机变量(X1,X2,...,Xn)的概率密度定义为f(x1,x2,...,xn)=(2π)2∣C∣1/21e[−21(X−μ)TC−1(X−μ)]其中C是(X1,X2,...,Xn)的协方差矩阵。
解决一个概率密度函数参数问题。
极大似然的思想是,根据使样本出现的概率最大的原则来判断总体中的参数。
若总体
X
的分辨率为
P
{
X
=
x
}
=
p
(
x
,
θ
)
(
或密度函数为
f
(
x
i
;
θ
)
)
,
其中
θ
=
(
θ
1
,
θ
2
,
.
.
.
,
θ
k
)
为待估参数。设
X
1
,
X
2
,
.
.
.
,
X
n
是来自总体
X
的一个样本,
x
1
,
x
2
,
.
.
.
,
x
n
是相应于样本的样本值,则样本
X
1
,
X
2
,
.
.
.
,
X
n
取到观测值
x
1
,
x
2
,
.
.
.
,
x
n
的概率为
p
=
P
{
X
1
=
x
1
,
X
2
=
x
2
,
.
.
.
,
X
n
=
x
n
}
=
∏
i
=
1
n
p
(
x
i
;
θ
)
,
或者样本
X
1
,
X
2
,
.
.
.
,
X
n
在点
x
1
,
x
2
,
.
.
.
,
x
n
的领域
(
边长分别为
d
x
1
,
d
x
2
,
.
.
.
,
d
x
n
的
n
维立方体
)
内取值的概率近似地为
p
=
∏
i
=
1
π
f
(
x
i
;
θ
)
d
x
i
.
令
L
(
θ
)
=
L
(
x
1
,
x
2
,
.
.
.
,
x
n
;
θ
)
=
∏
i
=
1
n
p
(
x
i
;
θ
)
,
或
L
(
θ
)
=
L
(
x
1
,
x
2
,
.
.
.
,
x
n
;
θ
)
=
∏
i
=
1
n
f
(
x
i
;
θ
)
,
则概率
p
随
θ
的取值而变化,它是
θ
函数,
L
(
θ
)
称为样本的似然函数。
如果已知当
θ
=
θ
0
时使
L
(
θ
)
取最大值,
θ
0
作为未知参数
θ
的估计合理值。
若总体X的分辨率为P{\{X=x}\}=p(x,\theta)(或密度函数为\\ f(x_i;\theta)),其中\theta=(\theta_1,\theta_2,...,\theta_k)为待估参数。设X_1,X_2,...,X_n是来自总体X的一个样本,\\ x_1,x_2,...,x_n是相应于样本的样本值,则样本X_1,X_2,...,X_n取到观测值x_1,x_2,...,x_n的概率为\\ p=P{\{X_1=x_1,X_2=x_2,...,X_n=x_n}\}=\prod_{i=1}^{n}p(x_i;\theta),\\ 或者样本X_1,X_2,...,X_n在点x_1,x_2,...,x_n的领域\\ (边长分别为dx_1,dx_2,...,dx_n的n维立方体)内取值的概率近似地为\\ p=\prod_{i=1}^{\pi}f(x_i;\theta)dx_i.\\ 令L(\theta)=L(x_1,x_2,...,x_n;\theta)=\prod_{i=1}^np(x_i;\theta),\\ 或L(\theta)=L(x_1,x_2,...,x_n;\theta)=\prod_{i=1}^nf(x_i;\theta),\\ 则概率p随\theta的取值而变化,它是\theta函数,L(\theta)称为样本的似然函数。\\如果已知当\theta=\theta_0时使L(\theta)取最大值,\theta_0作为未知参数\theta的估计合理值。
若总体X的分辨率为P{X=x}=p(x,θ)(或密度函数为f(xi;θ)),其中θ=(θ1,θ2,...,θk)为待估参数。设X1,X2,...,Xn是来自总体X的一个样本,x1,x2,...,xn是相应于样本的样本值,则样本X1,X2,...,Xn取到观测值x1,x2,...,xn的概率为p=P{X1=x1,X2=x2,...,Xn=xn}=i=1∏np(xi;θ),或者样本X1,X2,...,Xn在点x1,x2,...,xn的领域(边长分别为dx1,dx2,...,dxn的n维立方体)内取值的概率近似地为p=i=1∏πf(xi;θ)dxi.令L(θ)=L(x1,x2,...,xn;θ)=i=1∏np(xi;θ),或L(θ)=L(x1,x2,...,xn;θ)=i=1∏nf(xi;θ),则概率p随θ的取值而变化,它是θ函数,L(θ)称为样本的似然函数。如果已知当θ=θ0时使L(θ)取最大值,θ0作为未知参数θ的估计合理值。
求法:若 θ 可微,取对数。对数似然函数: l n L ( θ ) = ∑ i = 1 n l n f ( x i ; θ ) (或 ∑ i = 1 n l n p ( x i ; θ ) ) 若 p ( x ; θ ) 和 f ( x ; θ ) 关于 θ 不可微时,需利用求极值方法讨论。 求法:若\theta可微,取对数。对数似然函数:\\ lnL(\theta)=\sum_{i=1}^{n}lnf(x_i;\theta)(或\sum_{i=1}^nlnp(x_i;\theta))\\ 若p(x;\theta)和f(x;\theta)关于\theta不可微时,需利用求极值方法讨论。 求法:若θ可微,取对数。对数似然函数:lnL(θ)=i=1∑nlnf(xi;θ)(或i=1∑nlnp(xi;θ))若p(x;θ)和f(x;θ)关于θ不可微时,需利用求极值方法讨论。
目标函数
优化变量
可行域
等式约束
不等式约束
局部极小值
全局极小值
一般转化为线性函数
X
k
+
1
=
X
k
−
γ
∇
f
(
X
k
)
γ
在程序中为步长当
∣
∣
∇
f
(
X
k
)
∣
∣
≤
σ
,
σ
无限接近
0
时终止迭代。
X_{k+1}=X_k-\gamma\nabla f(X_k)\\ \gamma在程序中为步长 当||\nabla f(X_k)||\leq\sigma,\sigma无限接近0时终止迭代。
Xk+1=Xk−γ∇f(Xk)γ在程序中为步长当∣∣∇f(Xk)∣∣≤σ,σ无限接近0时终止迭代。
实现过程:实现细节问题
初始值的设定
步长的选择
迭代的次序防止陷入循环
迭代终止的判定规则
一般转化为二次函数
找梯度为0的点
X
k
+
1
=
X
k
−
H
k
−
1
g
k
g
k
为
f
(
X
k
)
的梯度
当
H
−
1
不存在,即
H
不可逆时,无法使用这个方法。可以使用拟牛顿法。
X_{k+1}=X_k-H_k^{-1}g_k\\ g_k为f(X_k)的梯度\\ 当H^{-1}不存在,即H不可逆时,无法使用这个方法。可以使用拟牛顿法。
Xk+1=Xk−Hk−1gkgk为f(Xk)的梯度当H−1不存在,即H不可逆时,无法使用这个方法。可以使用拟牛顿法。
实现细节问题:初始值的设定
步长的选择
迭代终止的判定规则
分治法的思想:当有多个自变量时,选一个变量,其余的都固定,将多元函数极值问题转化为一元函数极值问题;接着继续优化下一个变量…繁复优化。
在知识向量机SVM中采用SHO算法就是利用该思想。
m
i
n
f
(
x
)
,
x
=
(
x
1
,
x
2
,
.
.
.
,
x
n
)
m
i
n
x
i
f
(
x
)
minf(x),x=(x_1,x_2,...,xn)\\ min_{x_i}f(x)
minf(x),x=(x1,x2,...,xn)minxif(x)
局部极值问题
鞍点问题(在该点出它的Hessian矩阵是不定的:既不正定也不负定)
m i n f ( x ) h i ( x ) = 0 , i = 1 , 2 , . . . , p L ( x , λ ) = f ( x ) + ∑ i = 1 p λ i h i ( x ) ∇ X f + ∑ i = 1 p λ i ∇ X h i = 0 h i ( x ) = 0 minf(x)\\ h_i(x)=0,i=1,2,...,p\\ L(x,\lambda)=f(x)+\sum_{i=1}^p\lambda_ih_i(x)\\ \nabla_Xf+\sum_{i=1}^p\lambda_i\nabla_Xh_i=0\\ h_i(x)=0 minf(x)hi(x)=0,i=1,2,...,pL(x,λ)=f(x)+i=1∑pλihi(x)∇Xf+i=1∑pλi∇Xhi=0hi(x)=0
要找函数z=f(x,y)在附加条件h(x,y)=0下的肯能极值点,可以先作拉格朗日函数
L
(
x
,
y
)
=
f
(
x
,
y
)
+
λ
h
(
x
,
y
)
,其中
λ
为参数,
L(x,y)=f(x,y)+\lambda h(x,y),其中\lambda为参数,
L(x,y)=f(x,y)+λh(x,y),其中λ为参数,
求其对x与y的一阶偏导数,并使之为零,然后与约束方程h(x,y)联立起来:
{
f
x
(
x
,
y
)
+
λ
h
x
(
x
,
y
)
=
0
f
y
(
x
,
y
)
+
λ
h
y
(
x
,
y
)
=
0
h
(
x
,
y
)
=
0
\begin{cases}f_x(x,y)+\lambda h_x(x,y)=0\\f_y(x,y)+\lambda h_y(x,y)=0\\h(x,y)=0\end{cases}
⎩
⎨
⎧fx(x,y)+λhx(x,y)=0fy(x,y)+λhy(x,y)=0h(x,y)=0
得到的(x,y)就是函数f(x,y)在附加条件h(x,y)=0下的可能极值点。
当对优化问题进行限定,就可避免局部极值问题和鞍点问题了。即凸优化问题。
凸优化两个限定:一:可行域为一个凸集。二:约束函数是一个凸函数。
定义:在一个集合C中,有任意两点x,y属于C,两者两线上所有的点都在C中。
x
,
y
连线上点的表达式为
(
与定比分点公式类似
)
:
θ
x
+
(
1
−
θ
)
y
∈
C
θ
∈
[
0
,
1
]
θ
=
0
,
1
是
x
,
y
两点。使用上述表达式进行证明某集合是否为凸集。
x,y连线上点的表达式为(与定比分点公式类似):\theta x+(1-\theta)y\in C\\ \theta\in[0,1]\\ \theta=0,1是x,y两点。 使用上述表达式进行证明某集合是否为凸集。
x,y连线上点的表达式为(与定比分点公式类似):θx+(1−θ)y∈Cθ∈[0,1]θ=0,1是x,y两点。使用上述表达式进行证明某集合是否为凸集。
典型的凸集: R n { x ∈ R n ; A x = b } { x ∈ R n ; A x ≤ b } ⋂ i = 1 k C i 典型的凸集:\\ R^n\\ {\{x\in R^n;Ax=b\}}\\ {\{x\in R^n;Ax\leq b\}}\\ \bigcap_{i=1}^k C_i 典型的凸集:Rn{x∈Rn;Ax=b}{x∈Rn;Ax≤b}i=1⋂kCi
凸函数的定义:在函数上任意找两点,它们的连线(割线)上的值要比函数对应的值大。
f
(
θ
x
+
(
1
−
θ
)
y
)
<
θ
f
(
x
)
+
(
1
−
θ
)
f
(
y
)
f(\theta x+(1-\theta)y)<\theta f(x)+(1-\theta)f(y)
f(θx+(1−θ)y)<θf(x)+(1−θ)f(y)
证明方法:一:定义法
二:一阶判别法
三:二阶判别法
一阶判别法:
一元函数:
f
(
y
)
≥
f
(
x
)
+
f
‘
(
x
)
(
y
−
x
)
多元函数:
f
(
y
)
≥
f
(
x
)
+
∇
f
(
x
)
(
y
−
x
)
二阶判别法:
一元函数:
f
‘
‘
(
x
)
≥
0
多元函数:
H
e
s
s
i
a
n
矩阵为半正定,即
H
≥
0
一阶判别法:\\ 一元函数:f(y)\geq f(x)+f`(x)(y-x)\\ 多元函数:f(y)\geq f(x)+\nabla f(x)(y-x)\\ 二阶判别法:\\ 一元函数:f``(x)\geq 0\\ 多元函数:Hessian矩阵为半正定,即H\geq0
一阶判别法:一元函数:f(y)≥f(x)+f‘(x)(y−x)多元函数:f(y)≥f(x)+∇f(x)(y−x)二阶判别法:一元函数:f‘‘(x)≥0多元函数:Hessian矩阵为半正定,即H≥0
性质:局部最优解一定是全局最优解。
利用反证法可以证明。
证明:假设一点
x
为局部极小值不是全局最小值,这时有一点
y
满足
f
(
y
)
<
f
(
x
)
,
在
x
点附近存在
δ
邻域,在这个邻域内所有的点的值都比
f
(
x
)
大。
在
x
的邻域内找一点
z
,根据凸函数的定义使得
f
(
x
)
>
f
(
z
)
,
则
f
(
x
)
就不是局部最小值。
点
z
满足:
z
=
θ
y
+
(
1
−
θ
)
x
,
θ
满足
θ
=
δ
2
∣
∣
x
−
y
∣
∣
2
;
二范数代表两点距离
接下来计算
x
与
z
的距离是否在
δ
邻域内:
∣
∣
x
−
z
∣
∣
2
=
∣
∣
x
−
(
δ
2
∣
∣
x
−
y
∣
∣
2
y
+
(
1
−
δ
2
∣
∣
x
−
y
∣
∣
2
)
x
)
∣
∣
2
=
∣
∣
δ
2
∣
∣
x
−
y
∣
∣
2
(
x
−
y
)
∣
∣
2
=
δ
2
≤
δ
z
在
δ
邻域内。
z
的函数值为:
f
(
z
)
=
f
(
θ
y
+
(
1
−
θ
)
x
)
≤
θ
f
(
y
)
+
(
1
−
θ
)
f
(
x
)
<
f
(
x
)
与
f
(
x
)
为局部极小值相矛盾。所以
x
不是局部极小值。
所以局部最优解一定是全局最优解。
证明:假设一点x为局部极小值不是全局最小值,这时有一点y满足f(y)<f(x),\\在x点附近存在\delta邻域,在这个邻域内所有的点的值都比f(x)大。\\在x的邻域内找一点z,根据凸函数的定义使得f(x)>f(z),则f(x)就不是局部最小值。\\ 点z满足:z=\theta y+(1-\theta)x,\theta满足\theta=\frac{\delta}{2||x-y||_2};二范数代表两点距离\\ 接下来计算x与z的距离是否在\delta邻域内:\\ ||x-z||_2=||x-(\frac{\delta}{2||x-y||_2}y+(1-\frac{\delta}{2||x-y||_2})x)||_2\\=||\frac{\delta}{2||x-y||_2}(x-y)||_2\\=\frac{\delta}{2}\leq\delta\\z在\delta邻域内。\\ z的函数值为: f(z)=f(\theta y+(1-\theta)x)\leq\theta f(y)+(1-\theta)f(x)<f(x)\\ 与f(x)为局部极小值相矛盾。所以x不是局部极小值。\\ 所以局部最优解一定是全局最优解。
证明:假设一点x为局部极小值不是全局最小值,这时有一点y满足f(y)<f(x),在x点附近存在δ邻域,在这个邻域内所有的点的值都比f(x)大。在x的邻域内找一点z,根据凸函数的定义使得f(x)>f(z),则f(x)就不是局部最小值。点z满足:z=θy+(1−θ)x,θ满足θ=2∣∣x−y∣∣2δ;二范数代表两点距离接下来计算x与z的距离是否在δ邻域内:∣∣x−z∣∣2=∣∣x−(2∣∣x−y∣∣2δy+(1−2∣∣x−y∣∣2δ)x)∣∣2=∣∣2∣∣x−y∣∣2δ(x−y)∣∣2=2δ≤δz在δ邻域内。z的函数值为:f(z)=f(θy+(1−θ)x)≤θf(y)+(1−θ)f(x)<f(x)与f(x)为局部极小值相矛盾。所以x不是局部极小值。所以局部最优解一定是全局最优解。
在机器学习中,证明SVM、logistics、线性回归等中的问题是凸优化问题,只需证明它的可行域为凸集,函数为凸函数即可。
原始问题: m i n f ( x ) g i ( x ) ≤ 0 , i = 1 , 2 , . . . , m h i ( x ) = 0 , i = 1 , 2 , . . . , p L ( x , λ , μ ) = f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ i = 1 p μ i h i ( x ) 原始问题:\\ minf(x)\\ g_i(x)\leq0,\quad i=1,2,...,m\\ h_i(x)=0,\quad i=1,2,...,p\\ \quad\\ L(x,\lambda,\mu)=f(x)+\sum_{i=1}^m\lambda_ig_i(x)+\sum_{i=1}^p\mu_ih_i(x) 原始问题:minf(x)gi(x)≤0,i=1,2,...,mhi(x)=0,i=1,2,...,pL(x,λ,μ)=f(x)+i=1∑mλigi(x)+i=1∑pμihi(x)
原问题: 第一步:固定 x , 操作 λ 和 μ , 然后让拉格朗日函数取极大值,之后就可将 λ 和 μ 消去。 第二步:操作 x ,让函数取极小值。 p ∗ = m i n x m a x λ , μ , λ i ≥ 0 L ( x , λ , μ ) = m i n x θ p ( x ) m i n x θ p ( x ) = m i n x m a x λ , μ , λ i ≥ 0 L ( x , λ , μ ) 原问题:\\ 第一步:固定x,操作\lambda和\mu,然后让拉格朗日函数取极大值,之后就可将\lambda和\mu消去。\\第二步:操作x,让函数取极小值。\\p^*=min_xmax_{\lambda,\mu,\lambda_i\geq0}L(x,\lambda,\mu)\\ =min_x\theta_p(x)\\ min_x\theta_p(x)=min_xmax_{\lambda,\mu,\lambda_i\geq0}L(x,\lambda,\mu) 原问题:第一步:固定x,操作λ和μ,然后让拉格朗日函数取极大值,之后就可将λ和μ消去。第二步:操作x,让函数取极小值。p∗=minxmaxλ,μ,λi≥0L(x,λ,μ)=minxθp(x)minxθp(x)=minxmaxλ,μ,λi≥0L(x,λ,μ)
注:原问题等价于我们要求解的问题。(原问题和原始问题是等价的。)
对偶问题:
d
∗
=
m
a
x
λ
,
μ
,
λ
i
≥
0
m
i
n
x
L
(
x
,
λ
,
μ
)
=
m
a
x
λ
,
μ
,
λ
i
≥
0
θ
D
(
λ
,
μ
)
弱对偶:
d
∗
=
m
a
x
λ
,
μ
,
λ
i
≥
0
m
i
n
x
L
(
x
,
λ
,
μ
)
≤
m
i
n
x
m
a
x
λ
,
μ
,
λ
i
≥
0
L
(
x
,
λ
,
μ
)
=
p
∗
对偶间隙:
p
∗
−
d
∗
;当为
0
时,原问题与对偶问题等价。
S
l
a
t
e
r
条件:一:凸优化问题;
二:至少存在一个可行点
x
使得不等式约束严格满足条件
<
0
。
S
l
a
t
e
r
条件是强对偶成立的充分条件。
强对偶:
S
l
a
t
e
r
成立可以推出强对偶。
对偶问题:\\ d^*=max_{\lambda,\mu,\lambda_i\geq0}min_xL(x,\lambda,\mu)=max_{\lambda,\mu,\lambda_i\geq0}\theta_D(\lambda,\mu)\\ 弱对偶:\\ d^*=max_{\lambda,\mu,\lambda_i\geq0}min_xL(x,\lambda,\mu)\leq min_xmax_{\lambda,\mu,\lambda_i\geq0}L(x,\lambda,\mu)=p^* \\对偶间隙:p^*-d^*;当为0时,原问题与对偶问题等价。\\ Slater条件:一:凸优化问题;\\二:至少存在一个可行点x使得不等式约束严格满足条件<0。\\ Slater条件是强对偶成立的充分条件。\\ 强对偶:Slater成立可以推出强对偶。
对偶问题:d∗=maxλ,μ,λi≥0minxL(x,λ,μ)=maxλ,μ,λi≥0θD(λ,μ)弱对偶:d∗=maxλ,μ,λi≥0minxL(x,λ,μ)≤minxmaxλ,μ,λi≥0L(x,λ,μ)=p∗对偶间隙:p∗−d∗;当为0时,原问题与对偶问题等价。Slater条件:一:凸优化问题;二:至少存在一个可行点x使得不等式约束严格满足条件<0。Slater条件是强对偶成立的充分条件。强对偶:Slater成立可以推出强对偶。
m i n f ( x ) g i ( x ) ≤ 0 i = 1 , 2 , . . . , q h i ( x ) = 0 i = 1 , 2 , . . . , p L ( x , λ , μ ) = f ( x ) + ∑ j = 1 p λ j h j ( x ) + ∑ k = 1 q μ k g k ( x ) { ∇ x L ( x ∗ ) = 0 μ k ≥ 0 μ k g k ( x ∗ ) = 0 h j ( x ∗ ) = 0 g k ( x ∗ ) ≤ 0 minf(x)\\ g_i(x)\leq0\quad i=1,2,...,q\\ h_i(x)=0\quad i=1,2,...,p\\ \quad\\ L(x,\lambda,\mu)=f(x)+\sum_{j=1}^p\lambda_jh_j(x)+\sum_{k=1}^q\mu_kg_k(x)\\ \quad\\ \begin{cases}\nabla_xL(x^*)=0\\ \mu_k\geq0\\ \mu_kg_k(x^*)=0\\ h_j(x^*)=0\\ g_k(x^*)\leq0 \end{cases} minf(x)gi(x)≤0i=1,2,...,qhi(x)=0i=1,2,...,pL(x,λ,μ)=f(x)+j=1∑pλjhj(x)+k=1∑qμkgk(x)⎩ ⎨ ⎧∇xL(x∗)=0μk≥0μkgk(x∗)=0hj(x∗)=0gk(x∗)≤0