常用符号表

nndl

线性代数

基变换

二维空间中的向量有它的坐标，例如向量的坐标是[32]\left[\begin{array}{l}3 \\ 2\end{array}\right]，它代表着从起点到向量的末端，需要向右移动三个单位，并向上移动两个单位。或者代表缩放三倍的向量ii，和两倍的向量jj，而它们的和就是坐标所描述的向量。

可以把这两个向量看做这个坐标的隐含假设，它们是标量缩放的对象，是标准坐标系的基向量。现在我们要讨论的是选取另一组基向量，比如Jennifer选择另一组向量b1b_{1}和b2b_{2}，则她得到的坐标[5/31/3]\left[\begin{array}{l}5 / 3 \\ 1 / 3\end{array}\right]，就与标准坐标系不同。

在我们的坐标系中，Jennifer的基向量的坐标分别是[21]\left[\begin{array}{l}2 \\ 1\end{array}\right]， [−11]\left[\begin{array}{c}-1 \\ 1\end{array}\right] ，但在她自己的坐标系中，基向量的坐标是 [10]\left[\begin{array}{l}1 \\ 0\end{array}\right]，[01]\left[\begin{array}{l}0 \\ 1\end{array}\right]。她坐标轴的原点与我们相重合，但是网格的尺寸和方向，依赖于对基向量的选择。那么我们如何在不同的坐标系中进行转变呢？

例如，求Jennifer坐标系下的向量[−12]\left[\begin{array}{c}-1 \\ 2\end{array}\right]，在我们的坐标系（标准坐标系）下的坐标。这过程就是用某个向量的特定坐标与他的基向量数乘，然后将结果相加−1[21]+2[−11]=[−41]-1\left[\begin{array}{l}2 \\ 1\end{array}\right]+2\left[\begin{array}{c}-1 \\ 1\end{array}\right]=\left[\begin{array}{c}-4 \\ 1\end{array}\right] ，这就是矩阵向量乘法 [2−111][−12]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right]\left[\begin{array}{c}-1 \\ 2\end{array}\right]。矩阵的列向量就是在我们坐标系下所表达的Jennifer的基向量。

作者在这里一顿描述，最后归结为这个矩阵，“把我们误解Jennifer的向量，变成Jennifer真正所想的向量。”

我是这么记的，[2−111][−onetwo]=[−41]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right]\left[\begin{array}{c}-\text {one} \\ \text {two}\end{array}\right]=\left[\begin{array}{c}-4 \\ 1\end{array}\right]，说英文的是Jennifer，数字都是我们坐标系下的坐标，列向量线性组合起来得到的也是我们坐标系下的坐标。输入的是Jennifer的 [−onetwo]\left[\begin{array}{c}-\text {one} \\ \text {two}\end{array}\right]，输出就是我们坐标系下的[−41]\left[\begin{array}{c}-4 \\ 1\end{array}\right]，Jennifer来我们的坐标系说事，翻译是我们出的，翻译内容就是她的单词在我们这边是啥意思，即她的基向量在我们这里是啥坐标，[2−111]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right] 。没有误解，只有交流。

那么反过来如何操作呢，我们坐标系下的 [32]\left[\begin{array}{l}3 \\ 2\end{array}\right]如何能够变成Jennifer坐标系下的[5/31/3]\left[\begin{array}{l}5 / 3 \\ 1 / 3\end{array}\right] ？答案是取逆矩阵[2−111]−1=[1/31/3−1/32/3]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right]^{-1}=\left[\begin{array}{cc}1 / 3 & 1 / 3 \\ -1 / 3 & 2 / 3\end{array}\right]，它意味着一个反向变换。我们坐标系下的 [32]\left[\begin{array}{l}3 \\ 2\end{array}\right]，即为Jennifer坐标系下的[5/31/3]\left[\begin{array}{l}5 / 3 \\ 1 / 3\end{array}\right] 。

[1/31/3−1/32/3]\left[\begin{array}{cc}1 / 3 & 1 / 3 \\ -1 / 3 & 2 / 3\end{array}\right]就是我们的基向量在Jennifer坐标系下的坐标，即我们的单词在她那啥意思。
在线性变换过程中，例如90度逆时针旋转，我们追踪基向量ii 和jj 在线性变换之后的坐标，得到矩阵[0−110]\left[\begin{array}{cc}0 & -1 \\ 1 & 0\end{array}\right]，这是用我们的坐标系记录的结果。Jennifer如果要描述90度逆时针旋转，她会追踪她的基向量经过线性变化后的坐标，并且这个坐标是在她的坐标系中记录的。

例如，对于Jennifer坐标系下的向量 [−12]\left[\begin{array}{c}-1 \\ 2\end{array}\right]，首先翻译成我们坐标系下的坐标 [2−111][−12]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right]\left[\begin{array}{c}-1 \\ 2\end{array}\right] ，然后对这个向量施加逆时针旋转[0−110][2−111][−12]\left[\begin{array}{cc}0 & -1 \\ 1 & 0\end{array}\right]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right]\left[\begin{array}{c}-1 \\ 2\end{array}\right]，最后再翻译回到Jennifer的语言中,[2−111]−1[0−110][2−111][−12]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right]^{-1}\left[\begin{array}{cc}0 & -1 \\ 1 & 0\end{array}\right]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right]\left[\begin{array}{c}-1 \\ 2\end{array}\right] 。

则三个矩阵的复合就是Jennifer坐标体系下的线性变换矩阵：

[2−111]−1[0−110][2−111]=[1/3−2/35/3−1/3]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right]^{-1}\left[\begin{array}{cc}0 & -1 \\ 1 & 0\end{array}\right]\left[\begin{array}{cc}2 & -1 \\ 1 & 1\end{array}\right]=\left[\begin{array}{cc}1 / 3 & -2 / 3 \\ 5 / 3 & -1 / 3\end{array}\right]

表达式 A−1MA\boldsymbol{A}^{-1} \boldsymbol{M} \boldsymbol{A} 暗示着一种数学上的转移作用，中间的矩阵是已了解的一种线性变换，而两侧的矩阵代表着转移作用，也就是视角的转化，三者乘积仍旧代表这种线性变换，但是是从别人的视角。

特征值与特征向量

对一个𝑁 × 𝑁的矩阵𝑨，如果存在一个标量𝜆和一个非零向量𝒗满足Av=λvA \boldsymbol{v}=\lambda \boldsymbol{v}，则𝜆和𝒗分别称为矩阵𝑨的特征值（Eigenvalue）和特征向量（Eigenvector）

当用矩阵𝑨对它的特征向量𝒗进行线性映射时，得到的新向量只是在𝒗的长度上缩放𝜆倍．给定一个矩阵的特征值，其对应的特征向量的数量是无限多的．令𝒖和𝒗是矩阵𝑨的特征值𝜆对应的特征向量，则𝛼𝒖和𝒖+𝒗也是特征值𝜆对应的特征向量

如果矩阵𝑨是一个𝑁 × 𝑁的实对称矩阵，则存在实数λ1,⋯ ,λN\lambda_{1}, \cdots, \lambda_{N}，以及𝑁个互相正交的单位向量v1,⋯ ,vN\boldsymbol{v}_{1}, \cdots, \boldsymbol{v}_{N}，使得vn\boldsymbol{v}_{n}为矩阵𝑨的特征值为λn\lambda_{n}的特征向量（1 ≤ 𝑛 ≤ 𝑁）

二维空间中的一个线性变换将基向量ii 变换为[30]\left[\begin{array}{l}3 \\ 0\end{array}\right]，基向量jj变换为[12]\left[\begin{array}{l}1 \\ 2\end{array}\right] 。如果用矩阵来表达的话就是[3102]\left[\begin{array}{ll}3 & 1 \\ 0 & 2\end{array}\right]。考虑一个特殊的向量以及这个向量张成的一维空间——直线，大部分向量在变换中都会离开了自己张成的空间，而如果向量经过变换后仍能落在这条直线上，就意味着线性变换对它的作用，仅仅是拉伸或者压缩，就如同一个标量一样。

在本例中，向量ii所在的方向就是这样一个特殊的方向，它张成的空间是xx轴。矩阵对它的线性变换作用，使得向量ii变成了原来的三倍，但仍然在xx轴上。x轴上的其他向量也都只是被拉伸为原来的三倍。

另一个略显隐蔽的向量是[−11]\left[\begin{array}{c}-1 \\ 1\end{array}\right]，他在变换后也留在自己张成的空间里，被拉伸为原长的两倍。

以上就是所有拥有“留在自己张成的空间”这个性质的特殊向量。其他的向量，在变换中都有或多或少的旋转。

这些向量就被称为这个线性变换的特征向量，衡量特征向量在变换中拉伸或压缩的比例因子就是它对应的特征值。如果特征向量为负值，比如-1/2，意味着这个向量被反向，并且压缩到原来的1/2。但它仍旧停留在自身张成的直线上，没有发生旋转。

考虑一个三维空间中的旋转变换。如果能找到该变换的特征向量，那你找到的就是旋转轴。把一个三维旋转看成绕某个轴旋转一定角度，比考虑相应的3×3矩阵直观得多。在这种旋转变换中，特征值为1，因为空间只发生旋转，并不发生拉伸和压缩。

线性变换对应的矩阵，其列向量就是基向量变换后的坐标。但是理解线性变换作用的关键，往往较少依赖于特定的坐标系。最好的方法是求出它的特征向量和特征值。

矩阵、特征向量和特征值的关系为Av=λvA v=\lambda v，AA是矩阵，v\mathcal{v}是特征向量，λ\lambda是该特征向量对应的特征值。特征向量经过矩阵变换后方向不变但被伸缩了λ\lambda倍。求解特征值和特征向量就是求解满足于上式的解。

(A−λI)v=0(A-\lambda I) v=0,我们的目标变成寻找一个非零的向量v\mathcal{v}，使得这个新矩阵与之相乘的结果为零向量。当且仅当这个新矩阵所代表的线性变换将空间压缩到更低维度的时候，这个方程有非零解。而这个矩阵所对应的行列式等于0。求解的过程就变为找到一个λ\lambda使得行列式det⁡(A−λI)=0\operatorname{det}(A-\lambda I)=0。

例如前面提到的矩阵[3102]\left[\begin{array}{ll}3 & 1 \\ 0 & 2\end{array}\right]，求解其特征值，则转变为求解行列式方程det⁡([3−λ102−λ])=(3−λ)(2−λ)=0\operatorname{det}\left(\left[\begin{array}{cc}3-\lambda & 1 \\ 0 & 2-\lambda\end{array}\right]\right)=(3-\lambda)(2-\lambda)=0，求得λ\lambda=2,3，代入可求得特征向量，例如代入λ\lambda=2，[3−2102−2][xy]=[00]\left[\begin{array}{cc}3-2 & 1 \\ 0 & 2-2\end{array}\right]\left[\begin{array}{l}x \\ y\end{array}\right]=\left[\begin{array}{l}0 \\ 0\end{array}\right]，求解得到特征向量[−11]\left[\begin{array}{c}-1 \\ 1\end{array}\right] 。

二维线性变换不一定有特征值，比如90度逆时针旋转变换，所有的向量都发生了旋转，没有向量能够保持在其张成空间。逆时针旋转对应矩阵为[0−110]\left[\begin{array}{cc}0 & -1 \\ 1 & 0\end{array}\right]，代入计算特征值可得det⁡([−λ−11−λ])=λ2+1=0\operatorname{det}\left(\left[\begin{array}{cc}-\lambda & -1 \\ 1 & -\lambda\end{array}\right]\right)=\lambda^{2}+1=0，方程的解只有虚数ii和−i-i。

剪切变换对应的矩阵为[1101]\left[\begin{array}{ll}1 & 1 \\ 0 & 1\end{array}\right]，行列式方程det⁡([1−λ−111−λ])=(1−λ)2=0\operatorname{det}\left(\left[\begin{array}{cc}1-\lambda & -1 \\ 1 & 1-\lambda\end{array}\right]\right)=(1-\lambda)^{2}=0，得唯一解λ\lambda=1，这与几何上相一致，只有xx轴未发生方向变化，同时缩放比为1。

有时候只有一个特征值，但特征向量不止在一条直线上。例如，拉伸变换[2002]\left[\begin{array}{ll}2 & 0 \\ 0 & 2\end{array}\right]，唯一的特征值为2，但平面内的向量都是其特征向量。

如果基向量是特征向量会发生什么？

比如，向量ii变换变为原来的（-1）倍，而向量jj变为原来的两倍，则变换对应的矩阵是[−1002]\left[\begin{array}{cc}-1 & 0 \\ 0 & 2\end{array}\right] ，它们变换的倍数就是特征值-1和2，这个矩阵是一个对角阵。

除了对角元素，其它元素均为0的矩阵被称为对角阵。对于对角阵，所有的基向量就是其特征向量，而对角元素就是它们所属的特征值。对角阵有很多特点，例如矩阵方幂很容易计算，
[3002]100[xy]=[3100002100][xy]\left[\begin{array}{ll}3 & 0 \\ 0 & 2\end{array}\right]^{100}\left[\begin{array}{l}x \\ y\end{array}\right]=\left[\begin{array}{cc}3^{100} & 0 \\ 0 & 2^{100}\end{array}\right]\left[\begin{array}{l}x \\ y\end{array}\right]

如果矩阵的特征向量足够多，可以张成整个空间，那么可以通过变换坐标系，使得这些特征向量成为基向量。

矩阵[3102]\left[\begin{array}{ll}3 & 1 \\ 0 & 2\end{array}\right]，取其特征向量作为列向量，构建基变换矩阵[1−101]\left[\begin{array}{cc}1 & -1 \\ 0 & 1\end{array}\right]，在原矩阵右侧乘上基变换矩阵，左侧乘上逆矩阵，[1−101]−1[3102][1−101]\left[\begin{array}{cc}1 & -1 \\ 0 & 1\end{array}\right]^{-1}\left[\begin{array}{ll}3 & 1 \\ 0 & 2\end{array}\right]\left[\begin{array}{cc}1 & -1 \\ 0 & 1\end{array}\right]。这个矩阵仍旧描述的是同一个线性变换，但是是从新的基向量构成的坐标系的角度来看的。

这样做的意义在于，这个矩阵会是对角阵，且对角元就是对应的特征值。
[1−101]−1[3102][1−101]=[3002]\left[\begin{array}{cc}1 & -1 \\ 0 & 1\end{array}\right]^{-1}\left[\begin{array}{cc}3 & 1 \\ 0 & 2\end{array}\right]\left[\begin{array}{cc}1 & -1 \\ 0 & 1\end{array}\right]=\left[\begin{array}{cc}3 & 0 \\ 0 & 2\end{array}\right]
它所处的坐标系的基向量在该线性变换中只进行了缩放。

一组特征向量构成的基向量的集合，称为一组“特征基”。计算矩阵[3102]\left[\begin{array}{ll}3 & 1 \\ 0 & 2\end{array}\right]的100次幂，可以先变换到特征基，在那个坐标系中对对角阵计算100次幂，然后再转换回标准坐标系。

并不是所有的变换都可以完成以上过程，例如剪切变换，它的特征向量不够多，不能张成整个空间。

线性变换

线性映射（Linear Mapping）线性映射也称为线性变换．是指从线性空间𝒳到线性空间𝒴的一个映射函数𝑓 ∶ 𝒳 → 𝒴，并满足：对于𝒳中任何两个向量𝒖和𝒗以及任何标量𝑐，有

  1. 𝑓(𝒖 + 𝒗) = 𝑓(𝒖) + 𝑓(𝒗)
  2. 𝑓(𝑐𝒗) = 𝑐𝑓(𝒗)

两个有限维欧氏空间的映射函数f:RN→RMf: \mathbb{R}^{N} \rightarrow \mathbb{R}^{M}可以表示为:

y=Ax≜[a11x1+a12x2+⋯+a1NxNa21x1+a22x2+⋯+a2NxN⋮aM1x1+aM2x2+⋯+aMNxN]y=A x \triangleq\left[\begin{array}{c}a_{11} x_{1}+a_{12} x_{2}+\cdots+a_{1 N} x_{N} \\ a_{21} x_{1}+a_{22} x_{2}+\cdots+a_{2 N} x_{N} \\ \vdots \\ a_{M 1} x_{1}+a_{M 2} x_{2}+\cdots+a_{M N} x_{N}\end{array}\right]

其中𝑨是一个由𝑀行𝑁列个元素排列成的矩形阵列，称为𝑀 × 𝑁的矩阵（Ma-trix）：

A=[a11a12⋯a1Na21a22⋯a2N⋮⋮⋱⋮aM1aM2⋯aMN]\boldsymbol{A}=\left[\begin{array}{cccc}a_{11} & a_{12} & \cdots & a_{1 N} \\ a_{21} & a_{22} & \cdots & a_{2 N} \\ \vdots & \vdots & \ddots & \vdots \\ a_{M 1} & a_{M 2} & \cdots & a_{M N}\end{array}\right]

向量x∈RN\boldsymbol{x} \in \mathbb{R}^{N}和y∈RMy \in \mathbb{R}^{M}为两个空间中的向量．𝒙和𝒚可以分别表示为𝑁 × 1的矩阵和𝑀 × 1的矩阵：

x=[x1x2⋮xN],y=[y1y2⋮yM]\boldsymbol{x}=\left[\begin{array}{c}x_{1} \\ x_{2} \\ \vdots \\ x_{N}\end{array}\right], \quad \boldsymbol{y}=\left[\begin{array}{c}y_{1} \\ y_{2} \\ \vdots \\ y_{M}\end{array}\right]

矩阵A∈RM×N\boldsymbol{A} \in \mathbb{R}^{M \times N}定义了一个从空间RN\mathbb{R}^{N}到空间RM\mathbb{R}^{M}的线性映射

仿射变换

仿射变换（Affine Transformation）是指通过一个线性变换和一个平移，将一个向量空间变换成另一个向量空间的过程．

令A∈RN×N\boldsymbol{A} \in \mathbb{R}^{N \times N}为𝑁 × 𝑁的实数矩阵，x∈RN\boldsymbol{x} \in \mathbb{R}^{N}是𝑁维向量空间中的点，仿射变换可以表示为

y=Ax+by=A x+b

其中y=Ax+by=A x+b为平移项．当𝒃 = 0时，仿射变换就退化为线性变换．

仿射变换可以实现线性空间中的旋转、平移、缩放变换．仿射变换不改变原始空间的相对位置关系，具有以下性质．

  1. 共线性（Collinearity）不变：在同一条直线上的三个或三个以上的点，在变换后依然在一条直线上；
  2. 比例不变：不同点之间的距离比例在变换后不变；
  3. 平行性不变：两条平行线在转换后依然平行；
  4. 凸性不变：一个凸集（Convex Set）在转换后依然是凸的．

矩阵运算

Hadamard积

矩阵𝑨和矩阵𝑩的Hadamard积（Hadamard Product）也称为逐点乘积，为𝑨和𝑩中对应的元素相乘．
[A⊙B]mn=amnbmn[\boldsymbol{A} \odot \boldsymbol{B}]_{m n}=a_{m n} b_{m n}

Kronecker积

如果𝑨是𝑀×𝑁的矩阵，𝑩是𝑆×𝑇的矩阵，那么它们的Kronecker积（Kronecker Product）是一个𝑀𝑆 × 𝑁𝑇的矩阵

[A⊗B]=[a11Ba12B⋯a1NBa21Ba22B⋯a2NB⋮⋮⋱⋮aM1BaM2B⋯aMNB][\boldsymbol{A} \otimes \boldsymbol{B}]=\left[\begin{array}{cccc}a_{11} \boldsymbol{B} & a_{12} \boldsymbol{B} & \cdots & a_{1 N} \boldsymbol{B} \\ a_{21} \boldsymbol{B} & a_{22} \boldsymbol{B} & \cdots & a_{2 N} \boldsymbol{B} \\ \vdots & \vdots & \ddots & \vdots \\ a_{M 1} \boldsymbol{B} & a_{M 2} \boldsymbol{B} & \cdots & a_{M N} \boldsymbol{B}\end{array}\right]

外积

两个向量a∈RM\boldsymbol{a} \in \mathbb{R}^{M}和b∈RN\boldsymbol{b} \in \mathbb{R}^{N}的外积（Outer Product）是一个𝑀 × 𝑁的矩阵，定义为
a⊗b=[a1b1a1b2…a1bNa2b1a2b2…a2bN⋮⋮⋱⋮aMb1aMb2…aMbN]=ab⊤\boldsymbol{a} \otimes \boldsymbol{b}=\left[\begin{array}{cccc}a_{1} b_{1} & a_{1} b_{2} & \dots & a_{1} b_{N} \\ a_{2} b_{1} & a_{2} b_{2} & \dots & a_{2} b_{N} \\ \vdots & \vdots & \ddots & \vdots \\ a_{M} b_{1} & a_{M} b_{2} & \dots & a_{M} b_{N}\end{array}\right]=\boldsymbol{a} \boldsymbol{b}^{\top}

其中[a⊗b]mn=ambr[\boldsymbol{a} \otimes \boldsymbol{b}]_{m n}=a_{m} b_{r}

外积通常看作矩阵的Kronecker积的一种特例，但两者并不等价．⊗既可以表示Kro-necker积，也可以表示外积，其具体含义不同一般需要在上下文中说明．

迹

方块矩阵𝑨的对角线元素之和称为它的迹（Trace），记为𝑡𝑟(𝑨)．尽管矩阵的乘法不满足交换律，但它们的迹相同，即𝑡𝑟(𝑨𝑩) = 𝑡𝑟(𝑩𝑨)．

行列式

方块矩阵𝑨的行列式是一个将其映射到标量的函数，记作det(𝑨)或|𝑨|．行列式可以看作有向面积或体积的概念在欧氏空间中的推广．在𝑁维欧氏空间中，行列式描述的是一个线性变换对“体积”所造成的影响．

秩

一个矩阵𝑨的列秩是𝑨的线性无关的列向量数量，行秩是𝑨的线性无关的行向量数量．一个矩阵的列秩和行秩总是相等的，简称为秩（Rank）．一个𝑀 × 𝑁的矩阵𝑨的秩最大为min(𝑀,𝑁)．若
rank⁡(A)=min⁡(M,N)\operatorname{rank}(\boldsymbol{A})=\min (M, N)，则称矩阵为满秩的．如果一个矩阵不满秩，说明其包含线性相关的列向量或行向量，其行列式为0．两个矩阵的乘积𝑨𝑩的秩rank⁡(AB)≤min⁡(rank⁡(A),rank⁡(B))\operatorname{rank}(\boldsymbol{A B}) \leq \min (\operatorname{rank}(\boldsymbol{A}), \operatorname{rank}(\boldsymbol{B}))

范数

矩阵的范数有很多种形式，其中常用的ℓ𝑝范数定义为

∥A∥p=(∑m=1M∑n=1N∣amn∣p)1/p\|\boldsymbol{A}\|_{p}=\left(\sum_{m=1}^{M} \sum_{n=1}^{N}\left|a_{m n}\right|^{p}\right)^{1 / p}

有时候我们可能也希望衡量矩阵的大小。在深度学习中，最常见的做法是使用 Frobenius 范数（Frobenius norm）：

∥A∥F=∑i,jAi,j2\|\boldsymbol{A}\|_{F}=\sqrt{\sum_{i, j} A_{i, j}^{2}}

其类似于向量的L2L^{2}范数。

矩阵求导

如果ff是一元函数，则

其逐元向量函数为： (x→)=(f(x1),f(x2),⋯ ,f(xn))T(\overrightarrow{\mathrm{x}})=\left(f\left(x_{1}\right), f\left(x_{2}\right), \cdots, f\left(x_{n}\right)\right)^{T}

其逐矩阵函数为：

f(X)=[f(x1,1)f(x1,2)⋯f(x1,n)f(x2,1)f(x2,2)⋯f(x2,n)⋮⋮⋱⋮f(xm,1)f(xm,2)⋯f(xm,n)]f(\mathbf{X})=\left[\begin{array}{cccc}f\left(x_{1,1}\right) & f\left(x_{1,2}\right) & \cdots & f\left(x_{1, n}\right) \\ f\left(x_{2,1}\right) & f\left(x_{2,2}\right) & \cdots & f\left(x_{2, n}\right) \\ \vdots & \vdots & \ddots & \vdots \\ f\left(x_{m, 1}\right) & f\left(x_{m, 2}\right) & \cdots & f\left(x_{m, n}\right)\end{array}\right]

其逐元导数分别为：

f′(x→)=(f′(x1),f′(x2),⋯ ,f′(xn))Tf^{\prime}(\overrightarrow{\mathbf{x}})=\left(f^{\prime}(x 1), f^{\prime}(x 2), \cdots, f^{\prime}\left(x_{n}\right)\right)^{T}

f′(X)=[f′(x1,1)f′(x1,2)⋯f′(x1,n)f′(x2,1)f′(x2,2)⋯f′(x2,n)⋮⋮⋱⋮f′(xm,1)f′(xm,2)⋯f′(xm,n)]f^{\prime}(\mathbf{X})=\left[\begin{array}{cccc}f^{\prime}\left(x_{1,1}\right) & f^{\prime}\left(x_{1,2}\right) & \cdots & f^{\prime}\left(x_{1, n}\right) \\ f^{\prime}\left(x_{2,1}\right) & f^{\prime}\left(x_{2,2}\right) & \cdots & f^{\prime}\left(x_{2, n}\right) \\ \vdots & \vdots & \ddots & \vdots \\ f^{\prime}\left(x_{m, 1}\right) & f^{\prime}\left(x_{m, 2}\right) & \cdots & f^{\prime}\left(x_{m, n}\right)\end{array}\right]

各种类型的偏导数：

标量对向量（nn维向量）的偏导数 ：

∂u∂v→=(∂u∂v1,∂u∂v2,⋯ ,∂u∂vn)T\frac{\partial u}{\partial \overrightarrow{\mathbf{v}}}=\left(\frac{\partial u}{\partial v_{1}}, \frac{\partial u}{\partial v_{2}}, \cdots, \frac{\partial u}{\partial v_{n}}\right)^{T}

对于𝑀维向量x∈RM\boldsymbol{x} \in \mathbb{R}^{M}和函数𝑦 = 𝑓(𝒙) ∈ ℝ，则𝑦关于𝒙的偏导数为:

∂y∂x=[∂y∂x1,⋯ ,∂y∂xM]⊤\frac{\partial y}{\partial x}=\left[\frac{\partial y}{\partial x_{1}}, \cdots, \frac{\partial y}{\partial x_{M}}\right]^{\top}

标量对矩阵(m×nm×n阶矩阵)的偏导数：

∂u∂V=[∂u∂V1,1∂u∂V1,2⋯∂u∂V1,n∂u∂V2,1∂u∂V2,2⋯∂u∂V2,n⋮⋮⋱⋮∂u∂Vm,1∂u∂Vm,2⋯∂u∂Vm,n]\frac{\partial u}{\partial \mathbf{V}}=\left[\begin{array}{cccc}\frac{\partial u}{\partial V_{1,1}} & \frac{\partial u}{\partial V_{1,2}} & \cdots & \frac{\partial u}{\partial V_{1, n}} \\ \frac{\partial u}{\partial V_{2,1}} & \frac{\partial u}{\partial V_{2,2}} & \cdots & \frac{\partial u}{\partial V_{2, n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial u}{\partial V_{m, 1}} & \frac{\partial u}{\partial V_{m, 2}} & \cdots & \frac{\partial u}{\partial V_{m, n}}\end{array}\right]

也即∂f∂X=[∂f∂Xij]\frac{\partial f}{\partial X}=\left[\frac{\partial f}{\partial X_{i j}}\right],即ff对XX逐元素求导排成与XX尺寸相同的矩阵.

向量（mm维向量）对标量的偏导数:

∂u→∂v=(∂u1∂v,∂u2∂v,⋯ ,∂um∂v)T\frac{\partial \overrightarrow{\mathbf{u}}}{\partial v}=\left(\frac{\partial u_{1}}{\partial v}, \frac{\partial u_{2}}{\partial v}, \cdots, \frac{\partial u_{m}}{\partial v}\right)^{T}

对于标量x∈Rx \in \mathbb{R}和函数y=f(x)∈RN\boldsymbol{y}=f(x) \in \mathbb{R}^{N}，则𝒚关于𝑥的偏导数为

∂y∂x=[∂y1∂x,⋯ ,∂yN∂x]\frac{\partial y}{\partial x}=\left[\frac{\partial y_{1}}{\partial x}, \cdots, \frac{\partial y_{N}}{\partial x}\right]

向量（mm维向量）对向量 (nn维向量) 的偏导数（雅可比矩阵）

∂u→∂v→=[∂u1∂v1∂u1∂v2⋯∂u1∂vn∂u2∂v1∂u2∂v2⋯∂u2∂vn⋮⋮⋱⋮∂um∂v1∂um∂v2⋯∂um∂vn]\frac{\partial \overrightarrow{\mathbf{u}}}{\partial \overrightarrow{\mathbf{v}}}=\left[\begin{array}{cccc}\frac{\partial u_{1}}{\partial v_{1}} & \frac{\partial u_{1}}{\partial v_{2}} & \cdots & \frac{\partial u_{1}}{\partial v_{n}} \\ \frac{\partial u_{2}}{\partial v_{1}} & \frac{\partial u_{2}}{\partial v_{2}} & \cdots & \frac{\partial u_{2}}{\partial v_{n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial u_{m}}{\partial v_{1}} & \frac{\partial u_{m}}{\partial v_{2}} & \cdots & \frac{\partial u_{m}}{\partial v_{n}}\end{array}\right]

对于𝑀维向量x∈RM\boldsymbol{x} \in \mathbb{R}^{M}和函数y=f(x)∈RN\boldsymbol{y}=f(\boldsymbol{x}) \in \mathbb{R}^{N}，则𝑓(𝒙)关于𝒙的偏导数（分母布局）为

∂f(x)∂x=[∂y1∂x1⋯∂yN∂x1⋮⋱⋮∂y1∂xM⋯∂yN∂xM]∈RM×N\frac{\partial f(\boldsymbol{x})}{\partial \boldsymbol{x}}=\left[\begin{array}{ccc}\frac{\partial y_{1}}{\partial x_{1}} & \cdots & \frac{\partial y_{N}}{\partial x_{1}} \\ \vdots & \ddots & \vdots \\ \frac{\partial y_{1}}{\partial x_{M}} & \cdots & \frac{\partial y_{N}}{\partial x_{M}}\end{array}\right] \in \mathbb{R}^{M \times N}

称为函数𝑓(𝒙)的雅可比矩阵（Jacobian Matrix）的转置．

对于𝑀维向量x∈RM\boldsymbol{x} \in \mathbb{R}^{M}和函数y=f(x)∈Ry=f(x) \in \mathbb{R}，则𝑓(𝒙)关于𝒙的二阶偏导数（分母布局）为

H=∂2f(x)∂x2=[∂2y∂x12⋯∂2y∂x1∂xM⋮⋱⋮∂2y∂xM∂x1⋯∂2y∂xM2]∈RM×M\boldsymbol{H}=\frac{\partial^{2} f(\boldsymbol{x})}{\partial \boldsymbol{x}^{2}}=\left[\begin{array}{ccc}\frac{\partial^{2} y}{\partial x_{1}^{2}} & \cdots & \frac{\partial^{2} y}{\partial x_{1} \partial x_{M}} \\ \vdots & \ddots & \vdots \\ \frac{\partial^{2} y}{\partial x_{M} \partial x_{1}} & \cdots & \frac{\partial^{2} y}{\partial x_{M}^{2}}\end{array}\right] \in \mathbb{R}^{M \times M}

称为函数𝑓(𝒙)的Hessian矩阵，也写作∇2f(x)\nabla^{2} f(\boldsymbol{x}),其中第𝑚,𝑛个元素为∂2y∂xm∂xn\frac{\partial^{2} y}{\partial x_{m} \partial x_{n}}

矩阵(m×nm×n阶矩阵)对标量的偏导数

∂U∂v=[∂U1,1∂v∂U1,2∂v⋯∂U1,n∂v∂U2,1∂v∂U2,2∂v⋯∂U2,n∂v⋮⋮⋱⋮∂Um,1∂v∂Um,2∂v⋯∂Um,n∂v]\frac{\partial \mathbf{U}}{\partial v}=\left[\begin{array}{cccc}\frac{\partial U_{1,1}}{\partial v} & \frac{\partial U_{1,2}}{\partial v} & \cdots & \frac{\partial U_{1, n}}{\partial v} \\ \frac{\partial U_{2,1}}{\partial v} & \frac{\partial U_{2,2}}{\partial v} & \cdots & \frac{\partial U_{2, n}}{\partial v} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial U_{m, 1}}{\partial v} & \frac{\partial U_{m, 2}}{\partial v} & \cdots & \frac{\partial U_{m, n}}{\partial v}\end{array}\right]

dAdB=[dA1dx1dA2dx2dA1dy1dA2dy2dA1dz1dA2dz2]\frac{\mathrm{d} A}{\mathrm{d} B}=\left[\begin{array}{ll}\frac{\mathrm{d} A 1}{\mathrm{d} x 1} & \frac{\mathrm{d} A 2}{\mathrm{d} x 2} \\ \frac{\mathrm{d} A 1}{\mathrm{d} y 1} & \frac{\mathrm{d} A 2}{\mathrm{d} y 2} \\ \frac{\mathrm{d} A 1}{\mathrm{d} z 1} & \frac{\mathrm{d} A 2}{\mathrm{d} z 2}\end{array}\right]

对于向量A=[sin⁡x−ysin⁡3x−4y]A=\left[\begin{array}{c}\sin x-y \\ \sin 3 x-4 y\end{array}\right]，可以对xx求导,得到另一个向量，dAdx=[cos⁡x3cos⁡3x]\frac{\mathrm{d} A}{\mathrm{d} x}=\left[\begin{array}{c}\cos x \\ 3 \cos 3 x\end{array}\right],如果AA要对另一个向量求导，会得到一个矩阵。比如，另一个向量B=[xyz]B=\left[\begin{array}{l}x \\ y \\ z\end{array}\right],如果AA（一个2×1的向量）要对BB（一个3×1的向量）求导，会得到如下3×2 的矩阵：

dAdB=[cos⁡x3cos⁡3x−1−400]\frac{\mathrm{d} A}{\mathrm{d} B}=\left[\begin{array}{cc}\cos x & 3 \cos 3 x \\ -1 & -4 \\ 0 & 0\end{array}\right]

加法，乘法法则

若x∈RM,y=f(x)∈RN,z=g(x)∈RN\boldsymbol{x} \in \mathbb{R}^{M}, \boldsymbol{y}=f(\boldsymbol{x}) \in \mathbb{R}^{N}, \boldsymbol{z}=g(\boldsymbol{x}) \in \mathbb{R}^{N}，则：

∂(y+z)∂x=∂y∂x+∂z∂x∈RM×N\frac{\partial(y+z)}{\partial x}=\frac{\partial y}{\partial x}+\frac{\partial z}{\partial x} \in \mathbb{R}^{M \times N}

若x∈RM,y=f(x)∈RN,z=g(x)∈RN\boldsymbol{x} \in \mathbb{R}^{M}, \boldsymbol{y}=f(\boldsymbol{x}) \in \mathbb{R}^{N}, \boldsymbol{z}=g(\boldsymbol{x}) \in \mathbb{R}^{N}，则：

∂y⊤Az∂x=∂y∂xAz+∂z∂xA⊤y∈RM\frac{\partial \boldsymbol{y}^{\top} \boldsymbol{A} \boldsymbol{z}}{\partial \boldsymbol{x}}=\frac{\partial \boldsymbol{y}}{\partial \boldsymbol{x}} \boldsymbol{A} \boldsymbol{z}+\frac{\partial \boldsymbol{z}}{\partial \boldsymbol{x}} \boldsymbol{A}^{\top} \boldsymbol{y} \quad \in \mathbb{R}^{M}

若x∈RM,y=f(x)∈RS,z=g(x)∈RT,A∈RS×T\boldsymbol{x} \in \mathbb{R}^{M}, \boldsymbol{y}=f(\boldsymbol{x}) \in \mathbb{R}^{S}, \boldsymbol{z}=g(\boldsymbol{x}) \in \mathbb{R}^{T}, \boldsymbol{A} \in \mathbb{R}^{S \times T} 和x无关，则

∂y⊤Az∂x=∂y∂xAz+∂z∂xA⊤y∈RM\frac{\partial \boldsymbol{y}^{\top} \boldsymbol{A} \boldsymbol{z}}{\partial \boldsymbol{x}}=\frac{\partial \boldsymbol{y}}{\partial \boldsymbol{x}} \boldsymbol{A} \boldsymbol{z}+\frac{\partial \boldsymbol{z}}{\partial \boldsymbol{x}} \boldsymbol{A}^{\top} \boldsymbol{y} \quad \in \mathbb{R}^{M}

若x∈RM,y=f(x)∈R,z=g(x)∈RN\boldsymbol{x} \in \mathbb{R}^{M}, y=f(\boldsymbol{x}) \in \mathbb{R}, \boldsymbol{z}=g(\boldsymbol{x}) \in \mathbb{R}^{N}，则

∂yz∂x=y∂z∂x+∂y∂xz⊤∈RM×N\frac{\partial y z}{\partial x}=y \frac{\partial z}{\partial x}+\frac{\partial y}{\partial x} z^{\top} \quad \in \mathbb{R}^{M \times N}

链式法则

若x∈R,y=g(x)∈RM,z=f(y)∈RNx \in \mathbb{R}, \boldsymbol{y}=g(x) \in \mathbb{R}^{M}, \boldsymbol{z}=f(\boldsymbol{y}) \in \mathbb{R}^{N}，则

∂z∂x=∂y∂x∂z∂y∈R1×N\frac{\partial z}{\partial x}=\frac{\partial y}{\partial x} \frac{\partial z}{\partial y} \in \mathbb{R}^{1 \times N}

若x∈RM,y=g(x)∈RK,z=f(y)∈RN\boldsymbol{x} \in \mathbb{R}^{M}, \boldsymbol{y}=g(\boldsymbol{x}) \in \mathbb{R}^{K}, \boldsymbol{z}=f(\boldsymbol{y}) \in \mathbb{R}^{N}，则：

∂z∂x=∂y∂x∂z∂y∈RM×N\frac{\partial z}{\partial x}=\frac{\partial y}{\partial x} \frac{\partial z}{\partial y} \in \mathbb{R}^{M \times N}

若X∈RM×N⋙ZEP,y=g(X)∈RK,z=f(y)∈R\boldsymbol{X} \in \mathbb{R}^{M \times N} \ggg \mathbb{Z E} \mathbb{P} \not, \boldsymbol{y}=g(\boldsymbol{X}) \in \mathbb{R}^{K}, z=f(\boldsymbol{y}) \in \mathbb{R}，则

∂z∂xij=∂y∂xij∂z∂y∈R\frac{\partial z}{\partial x_{i j}}=\frac{\partial y}{\partial x_{i j}} \frac{\partial z}{\partial y} \in \mathbb{R}

向量函数及其导数

对一个向量xx有：
∂x∂x=I\frac{\partial x}{\partial x}=I

∂∥x∥2∂x=2x\frac{\partial\|\boldsymbol{x}\|^{2}}{\partial \boldsymbol{x}}=2 \boldsymbol{x}

∂Ax∂x=A⊤\frac{\partial \boldsymbol{A} \boldsymbol{x}}{\partial \boldsymbol{x}}=\boldsymbol{A}^{\top}

∂x⊤A∂x=A\frac{\partial \boldsymbol{x}^{\top} \boldsymbol{A}}{\partial \boldsymbol{x}}=\boldsymbol{A}

向量和矩阵的导数满足乘法法则：

∂xTa∂x=∂aTx∂x=a∂AB∂x=∂A∂xB+A∂B∂x\begin{aligned} \frac{\partial \boldsymbol{x}^{\mathrm{T}} \boldsymbol{a}}{\partial \boldsymbol{x}} &=\frac{\partial \boldsymbol{a}^{\mathrm{T}} \boldsymbol{x}}{\partial \boldsymbol{x}}=\boldsymbol{a} \\ \frac{\partial \mathbf{A} \mathbf{B}}{\partial \boldsymbol{x}}=& \frac{\partial \mathbf{A}}{\partial \boldsymbol{x}} \mathbf{B}+\mathbf{A} \frac{\partial \mathbf{B}}{\partial \boldsymbol{x}} \end{aligned}

按位计算的向量函数及其导数

假设一个函数𝑓(𝑥)的输入是标量𝑥．对于一组𝐾个标量x1,⋯ ,xKx_{1}, \cdots, x_{K}，我们可以通过𝑓(𝑥)得到另外一组𝐾个标量z1,⋯ ,zKz_{1}, \cdots, z_{K}:

zk=f(xk)z_{k}=f\left(x_{k}\right),∀k=1,⋯ ,K\forall k=1, \cdots, K

为了简便起见，我们定义x=[x1,⋯ ,xK]⊤\boldsymbol{x}=\left[x_{1}, \cdots, x_{K}\right]^{\top}，z=[z1,⋯ ,zK]⊤z=\left[z_{1}, \cdots, z_{K}\right]^{\top}

z=f(x)z=f(x)

其中𝑓(𝒙)是按位运算的，即[f(x)]k=f(xk)[f(\boldsymbol{x})]_{k}=f\left(x_{k}\right)

当𝑥为标量时，𝑓(𝑥)的导数记为𝑓′(𝑥)．当输入为𝐾维向量x=[x1,⋯ ,xK]⊤\boldsymbol{x}=\left[x_{1}, \cdots, x_{K}\right]^{\top}，其导数为一个对角矩阵．

∂f(x)∂x=[∂f(xj)∂xi]K×K=[f′(x1)0⋯00f′(x2)⋯0⋮⋮⋱⋮00⋯f′(xK)]=diag⁡(f′(x))\begin{aligned} \frac{\partial f(\boldsymbol{x})}{\partial \boldsymbol{x}} &=\left[\frac{\partial f\left(x_{j}\right)}{\partial x_{i}}\right]_{K \times K} \\ &=\left[\begin{array}{ccccc}f^{\prime}\left(x_{1}\right) & 0 & \cdots & 0 \\ 0 & f^{\prime}\left(x_{2}\right) & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & f^{\prime}\left(x_{K}\right)\end{array}\right] \\ &=\operatorname{diag}\left(f^{\prime}(\boldsymbol{x})\right) \end{aligned}

Logistic函数

Logistic函数定义为

logistic⁡(x)=L1+exp⁡(−K(x−x0))\operatorname{logistic}(x)=\frac{L}{1+\exp \left(-K\left(x-x_{0}\right)\right)}

其中exp(⋅)函数表示自然对数，x0x_{0}是中心点，𝐿是最大值，𝐾是曲线的倾斜度．下图给出了几种不同参数的Logistic函数曲线．当𝑥趋向于−∞时，logistic(𝑥)接近于0；当𝑥趋向于+∞时，logistic(𝑥)接近于𝐿

当参数为(𝑘 = 1,x0=0x_{0}=0= 0,𝐿 = 1)时，Logistic函数称为标准Logistic函数，记为𝜎(𝑥)

σ(x)=11+exp⁡(−x)\sigma(x)=\frac{1}{1+\exp (-x)}

标准Logistic函数在机器学习中使用得非常广泛，经常用来将一个实数空间的数映射到(0,1)区间

标准Logistic函数的导数为σ′(x)=σ(x)(1−σ(x))\sigma^{\prime}(x)=\sigma(x)(1-\sigma(x)),当输入为𝐾维向量x=[x1,⋯ ,xK]⊤\boldsymbol{x}=\left[x_{1}, \cdots, x_{K}\right]^{\top}，其导数为σ′(x)=diag⁡(σ(x)⊙(1−σ(x)))\sigma^{\prime}(\boldsymbol{x})=\operatorname{diag}(\sigma(\boldsymbol{x}) \odot(1-\sigma(\boldsymbol{x})))

Softmax函数

Softmax函数可以将多个标量映射为一个概率分布．对于𝐾个标量x1,⋯ ,xKx_{1}, \cdots, x_{K}，Softmax函数定义为zk=softmax⁡(xk)=exp⁡(xk)∑i=1Kexp⁡(xi)z_{k}=\operatorname{softmax}\left(x_{k}\right)=\frac{\exp \left(x_{k}\right)}{\sum_{i=1}^{K} \exp \left(x_{i}\right)}

这样，我们可以将𝐾个标量x1,⋯ ,xKx_{1}, \cdots, x_{K}转换为一个分布：z1,⋯ ,zKz_{1}, \cdots, z_{K}，满足

zk∈(0,1)z_{k} \in(0,1)

∑k=1Kzk=1\sum_{k=1}^{K} z_{k}=1

为了简便起见，用𝐾维向量x=[x1;⋯ ;xK]\boldsymbol{x}=\left[x_{1} ; \cdots ; x_{K}\right]来表示Softmax函数的输入,Softmax函数可以简写为:

z^=softmax⁡(x)=1∑k=1Kexp⁡(xk)[exp⁡(x1)⋮exp⁡(xK)]=exp⁡(x)∑k=1Kexp⁡(xk)=exp⁡(x)1K⊤exp⁡(x)\begin{aligned} \hat{z} &=\operatorname{softmax}(x) \\ &=\frac{1}{\sum_{k=1}^{K} \exp \left(x_{k}\right)}\left[\begin{array}{c}\exp \left(x_{1}\right) \\ \vdots \\ \exp \left(x_{K}\right)\end{array}\right] \\ &=\frac{\exp (x)}{\sum_{k=1}^{K} \exp \left(x_{k}\right)} \\ &=\frac{\exp (x)}{1_{K}^{\top} \exp (x)} \end{aligned}

其中1K=[1,⋯ ,1]K×1\mathbf{1}_{K}=[1, \cdots, 1]_{K \times 1},是𝐾维的全1向量.

Softmax函数的导数为

∂softmax⁡(x)∂x=∂(exp⁡(x)1K⊤exp⁡(x))∂x\frac{\partial \operatorname{softmax}(\boldsymbol{x})}{\partial \boldsymbol{x}}=\frac{\partial\left(\frac{\exp (x)}{1_{K}^{\top} \exp (x)}\right)}{\partial \boldsymbol{x}}
=11K⊤exp⁡(x)∂exp⁡(x)∂x+∂(11K⊤exp⁡(x))∂x(exp⁡(x))⊤=\frac{1}{\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})} \frac{\partial \exp (\boldsymbol{x})}{\partial \boldsymbol{x}}+\frac{\partial\left(\frac{1}{1_{K}^{\top} \exp (x)}\right)}{\partial \boldsymbol{x}}(\exp (\boldsymbol{x}))^{\top}
=diag⁡(exp⁡(x))1K⊤exp⁡(x)−(1(1K⊤exp⁡(x))2)∂(1K⊤exp⁡(x))∂x(exp⁡(x))⊤=\frac{\operatorname{diag}(\exp (\boldsymbol{x}))}{\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})}-\left(\frac{1}{\left(\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})\right)^{2}}\right) \frac{\partial\left(\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})\right)}{\partial \boldsymbol{x}}(\exp (\boldsymbol{x}))^{\top}
=diag⁡(exp⁡(x))1K⊤exp⁡(x)−(1(1K⊤exp⁡(x))2)diag⁡(exp⁡(x))1K(exp⁡(x))⊤=\frac{\operatorname{diag}(\exp (\boldsymbol{x}))}{\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})}-\left(\frac{1}{\left(\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})\right)^{2}}\right) \operatorname{diag}(\exp (\boldsymbol{x})) \mathbf{1}_{K}(\exp (\boldsymbol{x}))^{\top}
=diag⁡(exp⁡(x))1K⊤exp⁡(x)−(1(1K⊤exp⁡(x))2)exp⁡(x)(exp⁡(x))⊤=\frac{\operatorname{diag}(\exp (\boldsymbol{x}))}{\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})}-\left(\frac{1}{\left(\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})\right)^{2}}\right) \exp (\boldsymbol{x})(\exp (\boldsymbol{x}))^{\top}
=diag⁡(exp⁡(x)1K⊤exp⁡(x))−exp⁡(x)1K⊤exp⁡(x)(exp⁡(x))⊤1K⊤exp⁡(x)=\operatorname{diag}\left(\frac{\exp (\boldsymbol{x})}{\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})}\right)-\frac{\exp (\boldsymbol{x})}{\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})} \frac{(\exp (\boldsymbol{x}))^{\top}}{\mathbf{1}_{K}^{\top} \exp (\boldsymbol{x})}
=diag⁡(softmax⁡(x))−softmax⁡(x)softmax⁡(x)⊤=\operatorname{diag}(\operatorname{softmax}(\boldsymbol{x}))-\operatorname{softmax}(\boldsymbol{x}) \operatorname{softmax}(\boldsymbol{x})^{\top}

矩阵类型

对角矩阵

一个𝑁 × 𝑁的对角矩阵𝑨也可以记为diag(𝒂)，𝒂为一个𝑁维向量，并满足[A]nn=an[\boldsymbol{A}]_{n n}=a_{n}

𝑁 × 𝑁的对角矩阵𝑨 =diag(𝒂)和𝑁维向量𝒃的乘积为一个𝑁维向量Ab=diag⁡(a)b=a⊙bA b=\operatorname{diag}(a) b=a \odot b

正交矩阵

如果一个𝑁 × 𝑁的方块矩阵𝑨的逆矩阵等于其转置矩阵，即A⊤=A−1\boldsymbol{A}^{\top}=\boldsymbol{A}^{-1}，则𝑨为正交矩阵（Orthogonal Matrix）

正交矩阵满足A⊤A=AA⊤=IN\boldsymbol{A}^{\top} \boldsymbol{A}=\boldsymbol{A} \boldsymbol{A}^{\top}=\boldsymbol{I}_{N}，即正交矩阵的每一行（列）向量和自身的内积为1，和其他行（列）向量的内积为0．

Gram矩阵

向量空间中一组向量a1,a2,⋯ ,aN\boldsymbol{a}_{1}, \boldsymbol{a}_{2}, \cdots, \boldsymbol{a}_{N}的Gram矩阵（Gram Matrix）𝑮是内积的对称矩阵，其元素[G]mn=am⊤an[\boldsymbol{G}]_{m n}=\boldsymbol{a}_{m}^{\top} \boldsymbol{a}_{n}

矩阵分解

一个矩阵通常可以用一些比较“简单”的矩阵来表示，称为矩阵分解（Ma-trix Decomposition, or Matrix Factorization）

特征分解

一个𝑁 × 𝑁的方块矩阵𝑨的特征分解（Eigendecomposition）定义为A=QΛQ−1\boldsymbol{A}=\boldsymbol{Q} \mathbf{\Lambda} \boldsymbol{Q}^{-1},其中𝑸为𝑁 × 𝑁的方块矩阵，其每一列都为𝑨的特征向量，𝚲为对角矩阵，其每一个对角元素分别为𝑨的一个特征值．

如果𝑨为实对称矩阵，那么其不同特征值对应的特征向量相互正交．𝑨可以被分解为A=QΛQ⊤\boldsymbol{A}=\boldsymbol{Q} \boldsymbol{\Lambda} \boldsymbol{Q}^{\top},其中𝑸为正交矩阵

奇异值分解

一个𝑀 ×𝑁的矩阵𝑨的奇异值分解（Singular Value Decomposition，SVD）定义为A=UΣV⊤\boldsymbol{A}=\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top},其中𝑼和𝑽分别为𝑀 × 𝑀和𝑁 × 𝑁的正交矩阵，𝚺为𝑀 × 𝑁的矩形对角矩阵．𝚺对角线上的元素称为奇异值（Singular Value），一般按从大到小排列.

根据上述公式,AA⊤=UΣV⊤VΣU⊤=UΣ2U⊤\boldsymbol{A A}^{\top}=\boldsymbol{U \Sigma V}^{\top} \boldsymbol{V} \boldsymbol{\Sigma} \boldsymbol{U}^{\top}=\boldsymbol{U \Sigma}^{2} \boldsymbol{U}^{\top},A⊤A=VΣU⊤UΣV⊤\boldsymbol{A}^{\top} \boldsymbol{A}=\boldsymbol{V} \boldsymbol{\Sigma} \boldsymbol{U}^{\top} \boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}=VΣ2V⊤\boldsymbol{V} \boldsymbol{\Sigma}^{2} \boldsymbol{V}^{\top}，因此，𝑼和𝑽分别为AA⊤\boldsymbol{A A}^{\top}和A⊤A\boldsymbol{A}^{\top} \boldsymbol{A}的特征向量，𝑨的非零奇异值为AA⊤\boldsymbol{A} \boldsymbol{A}^{\top}或A⊤A\boldsymbol{A}^{\top} \boldsymbol{A}的非零特征值的平方根．

一个向量x∈RN\boldsymbol{x} \in \mathbb{R}^{N}左乘一个正交矩阵RN×N\mathbb{R}^{N \times N}，可以看作对𝒙进行坐标旋转，即𝑼中的行向量构成一组正交基向量．

由于一个大小为𝑀 × 𝑁的矩阵𝑨可以表示空间RN\mathbb{R}^{N}到空间RM\mathbb{R}^{M}的一种线性映射，因此奇异值分解相当于将这个线性映射分解为3个简单操作．

  1. 先使用𝑽在原始空间中进行坐标旋转．
  2. 用𝚺对旋转后的每一维进行缩放．如果𝑀 > 𝑁，则补𝑀 − 𝑁个0；相反，如果𝑀 < 𝑁，则舍去最后的𝑁 − 𝑀维．
  3. 使用𝑼进行再一次的坐标旋转．

矩阵的基本子空间

向量空间的子空间

若SS是向量空间VV的非空子集，且SS满足以下条件:

  1. 对任意实数aa,若x∈Sx \in S,则ax∈Sa x \in S
  2. 若x∈Sx \in S且y∈Sy \in S,则x+y∈Sx+y \in S

则SS称为VV的子空间

设v1,v2,⋯ ,vnv_{1}, v_{2}, \cdots, v_{n}为向量空间VV中的向量，则其线性组合a1v1+a2v2+⋯+anvna_{1} v_{1}+a_{2} v_{2}+\cdots+a_{n} v_{n}构成VV的子空间，称为v1,v2,⋯ ,vnv_{1}, v_{2}, \cdots, v_{n}张成(span)的子空间，记作span⁡(v1,v2,⋯ ,vn)\operatorname{span}\left(v_{1}, v_{2}, \cdots, v_{n}\right),如果span⁡{v1,v2,⋯ ,vn}=V\operatorname{span}\left\{v_{1}, v_{2}, \cdots, v_{n}\right\}=V,就说v1,v2,⋯ ,vnv_{1}, v_{2}, \cdots, v_{n}张成VV.

向量空间的基和维数

向量空间VV中的向量v1,v2,⋯ ,vnv_{1}, v_{2}, \cdots, v_{n}称为空间VV的基，如果满足条件

  1. v1,v2,⋯ ,vnv_{1}, v_{2}, \cdots, v_{n} 线性无关
  2. v1,v2,⋯ ,vnv_{1}, v_{2}, \cdots, v_{n} 张成VV

矩阵的行空间和列空间

设AA为一m×nm \times n矩阵，AA的每一行可看作是Rn\mathbf{R}^{n}中的一个向量，称为AA的行向量，类似的，AA的每一列可以看作是Rm\mathbf{R}^{m}中的一个向量，称为AA的列向量。

设AA为一m×nm \times n矩阵，则由AA的行向量张成的Rn\mathbf{R}^{n}子空间，称为AA的行空间。由AA的列向量张成的Rm\mathbf{R}^{m}子空间，称为AA的列空间。

矩阵AA的行空间的维数等于列空间的维数。3

一个矩阵行空间的维数等于矩阵的秩。

矩阵的零空间

设AA为m×nm \times n矩阵，令N(A)N(A)为齐次方程组Ax=0A x=0的所有解的集合，则N(A)N(A)为Rn\mathbf{R}^{n}的一个子空间，称为AA的零空间，即N(A)={x∈Rn∣Ax=0}N(A)=\left\{x \in R^{n} | A x=0\right\}。

一个矩阵的零空间的维数称为矩阵的零度。

秩-零度定理。设AA为一m×nm \times n矩阵，则AA的秩与AA的零度之和为%n%.

子空间的正交补

设XX和YY的为Rn\mathbf{R}^{n}的子空间，若对每一x∈Xx \in X和y∈Yy \in Y都满足xTy=0x^{\mathrm{T}} y=0，则称XX和YY是正交的，记作X⊥YX \perp Y

令YY为Rn\mathbf{R}^{n}的子空间，RnR^{n}中与YY中的每一向量正交的向量集合记作Y⊥Y^{\perp}，即Y⊥={x∈Rn∣xTy=0,∀y∈Y}Y^{\perp}=\left\{x \in \mathbf{R}^{n} | x^{\mathrm{T}} y=0, \forall y \in Y\right\},集合Y⊥Y^{\perp}称为YY的正交补。

若YY为Rn\mathbf{R}^{n}的子空间，则Y⊥Y^{\perp}也是Rn\mathbf{R}^{n}的子空间。

矩阵的基本子空间

设AA为一m×nm \times n矩阵，可以将AA看成是将Rn\mathbf{R}^{n}映射到Rm\mathbf{R}^{m}的线性变换，一个向量z∈Rmz \in \mathbf{R}^{m}在AA的列空间的充要条件是存在x∈Rnx \in \mathbf{R}^{n}，使得z=Axz=A x，这样AA的列空间和AA的值域是相同的，记AA的值域为R(A)R(A)，则R(A)={z∈Rm∣∃x∈Rn,z=Ax}R(A)=\left\{z \in \mathbf{R}^{m} | \exists x \in \mathbf{R}^{n}, z=A x\right\}=AA的列空间。

一个向量y∈Rny \in \mathbf{R}^{n}在AA的行空间的充要条件是存在x∈Rmx \in \mathbf{R}^{m}，使得y=ATxy=A^{\mathrm{T}} x，这样AA的行空间和ATA^{\mathrm{T}}的值域R(AT)R\left(A^{\mathrm{T}}\right)是相同的，则R(AT)={y∈Rn∣∃x∈Rm,y=ATx}R\left(A^{\mathrm{T}}\right)=\left\{y \in \mathbf{R}^{n} | \exists x \in \mathbf{R}^{m}, y=A^{\mathrm{T}} x\right\}=AA的行空间。

矩阵AA有四个基本子空间：列空间，行空间，零空间，AA的转置零空间(左零空间)。有下面的定理成立。

若AA为一m×nm \times n矩阵，则N(A)=R(AT)⊥N(A)=R\left(A^{\mathrm{T}}\right)^{\perp}，且N(AT)=R(A)⊥N\left(A^{\mathrm{T}}\right)=R(A)^{\perp}

数学分析

泰勒公式

如果函数𝑓(𝑥)在𝑎点处𝑛次可导（𝑛 ≥ 1），在一个包含点𝑎的区间上的任意𝑥，都有：

f(x)=f(a)+11!f′(a)(x−a)+12!f(2)(a)(x−a)2+⋯+1n!f(n)(a)(x−a)n+Rn(x)\begin{aligned} f(x)=f(a)+& \frac{1}{1 !} f^{\prime}(a)(x-a)+\frac{1}{2 !} f^{(2)}(a)(x-a)^{2}+\cdots \\ &+\frac{1}{n !} f^{(n)}(a)(x-a)^{n}+R_{n}(x) \end{aligned}

其中f(n)(a)f^{(n)}(a)表示函数𝑓(𝑥)在点𝑎的𝑛阶导数，公式中的多项式部分称为函数𝑓(𝑥)在𝑎处的𝑛阶泰勒展开式，剩余的Rn(x)R_{n}(x)是泰勒公式的余项，是(x−a)n(x-a)^{n}的高阶无穷小．

概率论

事件和概率

随机变量

离散随机变量

伯努利分布：在一次试验中，事件AA出现的概率为𝜇，不出现的概率为1 − 𝜇．若用变量𝑋表示事件𝑨出现的次数，则𝑋的取值为0和1，其相应的分布为p(x)=μx(1−μ)(1−x)p(x)=\mu^{x}(1-\mu)^{(1-x)},又名两点分布或者0-1分布.

二项分布：在NN次伯努利试验中，若以变量𝑋表示事件AA出现的次数，则𝑋的取值为{0,⋯,𝑁}，其相应的分布为二项分布（Binomial Distribution）,P(X=k)=(Nk)μk(1−μ)N−k,k=0,⋯ ,NP(X=k)=\left(\begin{array}{l}N \\ k\end{array}\right) \mu^{k}(1-\mu)^{N-k}, \quad k=0, \cdots, N,其中(Nk)\left(\begin{array}{l}N \\ k\end{array}\right)为二项式系数，表示从𝑁个元素中取出𝑘个元素而不考虑其顺序的组合的总数

排列组合是组合学最基本的概念．排列是指从给定个数的元素中取出指定个数的元素进行排序．𝑁个不同的元素可以有N!N !种不同的排列方式，即𝑁的阶乘．N!≜N×(N−1)×⋯×3×2×1N ! \triangleq N \times(N-1) \times \cdots \times 3 \times 2 \times 1.如果从𝑁个元素中取出𝑘个元素，这𝑘个元素的排列总数为PNk≜N×(N−1)×⋯×(N−k+1)=N!(N−k)!P_{N}^{k} \triangleq N \times(N-1) \times \cdots \times(N-k+1)=\frac{N !}{(N-k) !},组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序．从𝑁个元素中取出𝑘个元素，这𝑘个元素可能出现的组合数为CNk≜(Nk)=PNkk!=N!k!(N−k)!C_{N}^{k} \triangleq\left(\begin{array}{c}N \\ k\end{array}\right)=\frac{P_{N}^{k}}{k !}=\frac{N !}{k !(N-k) !}

连续随机变量

正态分布（Normal Distribution），又名高斯分布（Gaussian Distri-bution），是自然界最常见的一种分布，并且具有很多良好的性质，在很多领域都有非常重要的影响力，其概率密度函数为p(x)=12πσexp⁡(−(x−μ)22σ2)p(x)=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{(x-\mu)^{2}}{2 \sigma^{2}}\right)，其中𝜎 > 0，𝜇和𝜎均为常数．若随机变量𝑋服从一个参数为𝜇和𝜎的概率分布，简记为X∼N(μ,σ2)X \sim \mathcal{N}\left(\mu, \sigma^{2}\right)，当𝜇 = 0，𝜎 = 1时，称为标准正态分布。

采用正态分布在很多应用中都是一个明智的选择。当我们由于缺乏关于某个实数上分布的先验知识而不知道该选择怎样的形式时，正态分布是默认的比较好的选
择，其中有两个原因。

第一，我们想要建模的很多分布的真实情况是比较接近正态分布的。 中心极限定理（central limit theorem）说明很多独立随机变量的和近似服从正态分布。这意味着在实际中，很多复杂系统都可以被成功地建模成正态分布的噪声，即使系统可以被分解成一些更结构化的部分。

第二，在具有相同方差的所有可能的概率分布中，正态分布在实数上具有最大的不确定性。因此，我们可以认为正态分布是对模型加入的先验知识量最少的分布。

累积分布函数

对于一个随机变量𝑋，其累积分布函数（Cumulative Distribution Func-tion，CDF）是随机变量𝑋的取值小于等于𝑥的概率cdf⁡(x)=P(X≤x)\operatorname{cdf}(x)=P(X \leq x)，以连续随机变量𝑋为例，累积分布函数定义为cdf⁡(x)=∫−∞xp(t)dt\operatorname{cdf}(x)=\int_{-\infty}^{x} p(t) \mathrm{d} t，其中𝑝(𝑥)为概率密度函数。

随机向量

随机向量是指一组随机变量构成的向量．如果X1,X2,⋯ ,XKX_{1}, X_{2}, \cdots, X_{K}为𝐾个随机变量,那么称X=[X1,X2,⋯ ,XK]\boldsymbol{X}=\left[X_{1}, X_{2}, \cdots, X_{K}\right]为一个𝐾维随机向量．一维随机向量即随机变量．随机向量也分为离散随机向量和连续随机向量。

离散随机向量

离散随机向量的联合概率分布（Joint Probability Distribution）为P(X1=x1,X2=x2,⋯ ,XK=xK)=p(x1,x2,⋯ ,xK)P\left(X_{1}=x_{1}, X_{2}=x_{2}, \cdots, X_{K}=x_{K}\right)=p\left(x_{1}, x_{2}, \cdots, x_{K}\right)，其中xk∈Ωkx_{k} \in \Omega_{k}为变量XkX_{k}的取值，Ωk\Omega_{k}为变量XkX_{k}的样本空间

和离散随机变量类似，离散随机向量的概率分布满足

p(x1,x2,⋯ ,xK)≥0,∀x1∈Ω1,x2∈Ω2,⋯ ,xK∈ΩKp\left(x_{1}, x_{2}, \cdots, x_{K}\right) \geq 0, \quad \forall x_{1} \in \Omega_{1}, x_{2} \in \Omega_{2}, \cdots, x_{K} \in \Omega_{K}

∑x1∈Ω1∑x2∈Ω2⋯∑xK∈ΩKp(x1,x2,⋯ ,xK)=1\sum_{x_{1} \in \Omega_{1}} \sum_{x_{2} \in \Omega_{2}} \cdots \sum_{x_{K} \in \Omega_{K}} p\left(x_{1}, x_{2}, \cdots, x_{K}\right)=1

一个最常见的离散向量概率分布为多项分布（Multinomial Distri-bution）．多项分布是二项分布在随机向量的推广．假设一个袋子中装了很多球，总共有𝐾个不同的颜色．我们从袋子中取出𝑁个球．每次取出一个球时，就在袋子中放入一个同样颜色的球．这样保证同一颜色的球在不同试验中被取出的概率是相等的．令𝑿为一个𝐾维随机向量，每个元素Xk(k=1,⋯ ,K)X_{k}(k=1, \cdots, K)为取出的𝑁个球中颜色为𝑘的球的数量，则𝑋服从多项分布，其概率分布为

p(x1,…,xK∣μ)=N!x1!⋯xK!μ1x1⋯μKxKp\left(x_{1}, \ldots, x_{K} | \mu\right)=\frac{N !}{x_{1} ! \cdots x_{K} !} \mu_{1}^{x_{1}} \cdots \mu_{K}^{x_{K}}

其中μ=[μ1,⋯ ,μK]⊤\mu=\left[\mu_{1}, \cdots, \mu_{K}\right]^{\top}，分别为每次抽取的球的颜色为1,⋯,𝐾的概率，x1,⋯ ,xKx_{1}, \cdots, x_{K}为非负整数，并且满足∑k=1Kxk=N\sum_{k=1}^{K} x_{k}=N。

多项分布的概率分布也可以用gamma函数表示：

p(x1,⋯ ,xK∣μ)=Γ(∑kxk+1)∏kΓ(xk+1)∏k=1Kμkxkp\left(x_{1}, \cdots, x_{K} | \mu\right)=\frac{\Gamma\left(\sum_{k} x_{k}+1\right)}{\prod_{k} \Gamma\left(x_{k}+1\right)} \prod_{k=1}^{K} \mu_{k}^{x_{k}}

其中Γ(z)=∫0∞tz−1exp⁡(t)dt\Gamma(z)=\int_{0}^{\infty} \frac{t^{z-1}}{\exp (t)} \mathrm{d} t为gamma函数，这种表示形式和狄利克雷分布类似，而狄利克雷分布可以作为多项分布的共轭先验。

连续随机向量

一个𝐾维连续随机向量𝑿的联合概率密度函数（Joint Probability DensityFunction）满足

p(x)=p(x1,⋯ ,xK)≥0p(\boldsymbol{x})=p\left(x_{1}, \cdots, x_{K}\right) \geq 0

∫−∞+∞⋯∫−∞+∞p(x1,⋯ ,xK)dx1⋯dxK=1\int_{-\infty}^{+\infty} \cdots \int_{-\infty}^{+\infty} p\left(x_{1}, \cdots, x_{K}\right) \mathrm{d} x_{1} \cdots \mathrm{d} x_{K}=1

使用最广泛的连续随机向量分布为多元正态分布（MultivariateNormal Distribution），也称为多元高斯分布（Multivariate Gaussian Distribu-tion）．若𝐾维随机向量X=[X1,…,XK]⊤\boldsymbol{X}=\left[X_{1}, \ldots, X_{K}\right]^{\top}服从𝐾元正态分布，其密度函数为

p(x)=1(2π)K/2∣Σ∣1/2exp⁡(−12(x−μ)⊤Σ−1(x−μ))p(\boldsymbol{x})=\frac{1}{(2 \pi)^{K / 2}|\mathbf{\Sigma}|^{1 / 2}} \exp \left(-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu})^{\top} \mathbf{\Sigma}^{-1}(\boldsymbol{x}-\boldsymbol{\mu})\right)

其中μ∈RK\mu \in \mathbb{R}^{K}为多元正态分布的均值向量,Σ∈RK×K\mathbf{\Sigma} \in \mathbb{R}^{K \times K}为多元正态分布的协方差矩阵，|𝚺|表示𝚺的行列式

如果一个多元高斯分布的协方差矩阵简化为Σ=σ2I\mathbf{\Sigma}=\sigma^{2} \mathbf{I}，即每一个维随机变量都独立并且方差相同，那么这个多元高斯分布称为各向同性高斯分布（Isotropic Gaussian Distribution）。

如果一个𝐾维随机向量𝑿服从狄利克雷分布（Dirichlet Distri-bution），其密度函数为

p(x∣α)=Γ(α0)Γ(α1)⋯Γ(αK)∏k=1Kxkαk−1p(\boldsymbol{x} | \boldsymbol{\alpha})=\frac{\Gamma\left(\alpha_{0}\right)}{\Gamma\left(\alpha_{1}\right) \cdots \Gamma\left(\alpha_{K}\right)} \prod_{k=1}^{K} x_{k}^{\alpha_{k}-1}

其中α=[α1,…,αK]⊤\boldsymbol{\alpha}=\left[\alpha_{1}, \ldots, \alpha_{K}\right]^{\top}为狄利克雷分布的参数。

共轭分布

假设变量xx服从分布P(x∣Θ)P(x | \Theta)，其中Θ\Theta为参数，X={x1,x2,…,xm}X=\left\{x_{1}, x_{2}, \ldots, x_{m}\right\}，为变量xx的观测样本，假设参数Θ\Theta服从先验分布Π(Θ)\Pi(\Theta),r若由先验分布Π(Θ)\Pi(\Theta)和抽样分布P(x∣Θ)P(x | \Theta)决定的后验分布F(Θ∣X)F(\Theta | X)与Π(Θ)\Pi(\Theta)是同种类型的分布，则称先验分布Π(Θ)\Pi(\Theta)为分布P(x∣Θ)P(x | \Theta)或P(X∣Θ)P(X | \Theta)的共轭分布。

先验分布反映了某种先验信息，后验分布既反映了先验分布提供的信息、又反映了样本提供的信息。当先验分布与抽样分布共轭时，后验分布与先验分布属于同种类型，这意味着先验信息与样本提供的信息具有某种同一性。于是，若使用后验分布作为进一步抽样的先验分布，则新的后验分布仍将属于同种类型。因此，共轭分布在不少情形下会使问题得以简化。

边际分布

对于二维离散随机向量(𝑋,𝑌)，假设𝑋取值空间为Ωx\Omega_{x}，𝑌取值空间为Ωy\Omega_{y}，其联合概率分布满足：

p(x,y)≥0,∑x∈Ωx∑y∈Ωyp(x,y)=1p(x, y) \geq 0, \quad \sum_{x \in \Omega_{x}} \sum_{y \in \Omega_{y}} p(x, y)=1

对于联合概率分布𝑝(𝑥,𝑦)，我们可以分别对𝑥和𝑦进行求和

对于固定的𝑥

∑y∈Ωyp(x,y)=p(x)\sum_{y \in \Omega_{y}} p(x, y)=p(x)

对于固定的𝑦

∑x∈Ωxp(x,y)=p(y)\sum_{x \in \Omega_{x}} p(x, y)=p(y)

由离散随机向量(𝑋,𝑌)的联合概率分布，对𝑌的所有取值进行求和得到𝑋的概率分布；而对𝑋的所有取值进行求和得到𝑌的概率分布．这里𝑝(𝑥)和𝑝(𝑦)就称为𝑝(𝑥,𝑦)的边际分布（Marginal Distribution）

对于二维连续随机向量(𝑋,𝑌)，其边际分布为

p(x)=∫−∞+∞p(x,y)dyp(x)=\int_{-\infty}^{+\infty} p(x, y) \mathrm{d} y

p(y)=∫−∞+∞p(x,y)dxp(y)=\int_{-\infty}^{+\infty} p(x, y) \mathrm{d} x

一个二元正态分布的边际分布仍为正态分布。

条件概率分布

对于离散随机向量(𝑋,𝑌)，已知𝑋 = 𝑥的条件下，随机变量𝑌 = 𝑦的条件概率（Conditional Probability）为p(y∣x)≜P(Y=y∣X=x)=p(x,y)p(x)p(y | x) \triangleq P(Y=y | X=x)=\frac{p(x, y)}{p(x)},这个公式定义了随机变量𝑌关于随机变量𝑋的条件概率分布（ConditionalProb-ability Distribution），简称条件分布.

对于二维连续随机向量(𝑋,𝑌)，已知𝑋 = 𝑥的条件下，随机变量𝑌 = 𝑦的条件概率密度函数（Conditional Probability Density Function）为p(y∣x)=p(x,y)p(x)p(y | x)=\frac{p(x, y)}{p(x)},同理，已知𝑌 = 𝑦的条件下，随机变量𝑋 = 𝑥的条件概率密度函数为p(x∣y)=p(x,y)p(y)p(x | y)=\frac{p(x, y)}{p(y)}

贝叶斯定理

两个条件概率𝑝(𝑦|𝑥)和𝑝(𝑥|𝑦)之间的关系为p(y∣x)=p(x∣y)p(y)p(x)p(y | x)=\frac{p(x | y) p(y)}{p(x)}

独立与条件独立

对于两个离散（或连续）随机变量𝑋和𝑌，如果其联合概率（或联合概率密度函数）𝑝(𝑥,𝑦)满足p(x,y)=p(x)p(y)p(x, y)=p(x) p(y)，则称𝑋和𝑌互相独立（Independence），记为𝑋⟂⟂𝑌

对于三个离散（或连续）随机变量𝑋、𝑌和𝑍，如果条件概率（或联合概率密度函数）𝑝(𝑥,𝑦|𝑧)满足p(x,y∣z)=p(x∣z)p(y∣z)p(x, y | z)=p(x | z) p(y | z)，则称在给定变量𝑍时，𝑋和𝑌条件独立（Conditional Independence），记为𝑋⟂⟂𝑌|𝑍

期望和方差

随机变量𝑋的方差（Variance）用来定义它的概率分布的离散程度：

var⁡(X)=E[(X−E[X])2]\operatorname{var}(X)=\mathbb{E}\left[(X-\mathbb{E}[X])^{2}\right]

随机变量𝑋的方差也称为它的二阶矩。var⁡(X)\sqrt{\operatorname{var}(X)}则称为𝑋的根方差或标准差。

两个连续随机变量𝑋和𝑌的协方差（Covariance）用来衡量两个随机变量的分布之间的总体变化性，定义为

cov⁡(X,Y)=E[(X−E[X])(Y−E[Y])]\operatorname{cov}(X, Y)=\mathbb{E}[(X-\mathbb{E}[X])(Y-\mathbb{E}[Y])]

协方差经常也用来衡量两个随机变量之间的线性相关性．如果两个随机变量的协方差为0，那么称这两个随机变量是线性不相关．这里的线性相关和线性代数中的线性相关含义不同．两个随机变量之间没有线性相关性，并非表示它们之间是独立的，可能存在某种非线性的函数关系．反之，如果𝑋与𝑌是统计独立的，那么它们之间的协方差一定为0．

协方差的绝对值如果很大则意味着变量值变化很大并且它们同时距离各自的均值很远。如果协方差是正的，那么两个变量都倾向于同时取得相对较大的值。如果协方差是负的，那么其中一个变量倾向于取得相对较大的值的同时，另一个变量倾向于取得相对较小的值，反之亦然。

两个𝑀和𝑁维的连续随机向量𝑿和𝒀，它们的协方差（Covari-ance）为𝑀 × 𝑁的矩阵，定义为

cov⁡(X,Y)=E[(X−E[X])(Y−E[Y])⊤]\operatorname{cov}(\boldsymbol{X}, \boldsymbol{Y})=\mathbb{E}\left[(\boldsymbol{X}-\mathbb{E}[\boldsymbol{X}])(\boldsymbol{Y}-\mathbb{E}[\boldsymbol{Y}])^{\top}\right]

协方差矩阵cov(𝑿,𝒀)的第(𝑚,𝑛)个元素等于随机变量XmX_{m}和YnY_{n}的协方差．两个随机向量的协方差cov(𝑿,𝒀)与cov(𝒀,𝑿)互为转置关系．

如果两个随机向量的协方差矩阵为对角矩阵，那么称这两个随机向量是无关的。

单个随机向量𝑿的协方差矩阵定义为

cov⁡(X)=cov⁡(X,X)\operatorname{cov}(\boldsymbol{X})=\operatorname{cov}(\boldsymbol{X}, \boldsymbol{X})

Jensen不等式

如果𝑋是随机变量，𝑔是凸函数，则g(E[X])≤E[g(X)]g(\mathbb{E}[X]) \leq \mathbb{E}[g(X)]，等式当且仅当𝑋是一个常数或𝑔是线性时成立，这个性质称为Jensen不等式。特别地，对于凸函数𝑔定义域上的任意两点x1,x2x_{1}, x_{2}和一个标量λ∈[0,1]\lambda \in[0,1]，有

g(λx1+(1−λ)x2)≤λg(x1)+(1−λ)g(x2)g\left(\lambda x_{1}+(1-\lambda) x_{2}\right) \leq \lambda g\left(x_{1}\right)+(1-\lambda) g\left(x_{2}\right)

即凸函数𝑔上的任意两点的连线位于这两点之间函数曲线的上方。

大数定律

大数定律（Law of Large Numbers）是指𝑁个样本X1,⋯ ,XNX_{1}, \cdots, X_{N}是独立同分布的，即E[X1]=⋯=E[XN]=μ\mathbb{E}\left[X_{1}\right]=\cdots=\mathbb{E}\left[X_{N}\right]=\mu，那么其均值XˉN=1N(X1+⋯+XN)\bar{X}_{N}=\frac{1}{N}\left(X_{1}+\cdots+X_{N}\right)收敛于期望值𝜇，即XˉN→μ\bar{X}_{N} \rightarrow \mu \quad for N→∞\quad N \rightarrow \infty

中心极限定理

设随机变量X1,X2,⋯ ,Xn,⋯X_{1}, X_{2}, \cdots, X_{n}, \cdots相互独立，服从同一分布，且具有数学期望和方差：E(Xk)=μ,D(Xk)=σ2>0(k=E\left(X_{k}\right)=\mu, D\left(X_{k}\right)=\sigma^{2}>0(k=1,2,⋯ )1,2, \cdots)，则随机变量之和∑k=1nXk\sum_{k=1}^{n} X_{k}的标准化变量：

Yn=∑k=1nXk−E(∑k=1nXk)D(∑k=1nXk)=∑k=1nXk−nμnσY_{n}=\frac{\sum_{k=1}^{n} X_{k}-E\left(\sum_{k=1}^{n} X_{k}\right)}{\sqrt{D\left(\sum_{k=1}^{n} X_{k}\right)}}=\frac{\sum_{k=1}^{n} X_{k}-n \mu}{\sqrt{n} \sigma}

的分布函数Fn(x)F_{n}(x)对于任意xx满足lim⁡n→∞Fn(x)=lim⁡n→∞P{∑k=1nXk−nμnσ⩽x}=∫−∞x12πe−ı/2dt=Φ(x)\begin{aligned} \lim _{n \rightarrow \infty} F_{n}(x) &=\lim _{n \rightarrow \infty} P\left\{\frac{\sum_{k=1}^{n} X_{k}-n \mu}{\sqrt{n} \sigma} \leqslant x\right\} \\ &=\int_{-\infty}^{x} \frac{1}{\sqrt{2 \pi}} \mathrm{e}^{-\imath / 2} \mathrm{d} t=\Phi(x) \end{aligned}

这就是说，均值为μ\mu，方差为σ2>0\sigma^{2}>0的独立同分布的随机变量X1,X2,⋯ ,XnX_{1}, X_{2}, \cdots, X_{n}∑k=1nXk\sum_{k=1}^{n} X_{k}的标准化变量，当nn充分大时，有

∑k=1nXk−nμnσ\frac{\sum_{k=1}^{n} X_{k}-n \mu}{\sqrt{n} \sigma}~N(0,1)N(0,1)。

上式左端改写成1n∑k=1nXk−μσ/n=Xˉ−μσ/n\frac{\frac{1}{n} \sum_{k=1}^{n} X_{k}-\mu}{\sigma / \sqrt{n}}=\frac{\bar{X}-\mu}{\sigma / \sqrt{n}}，上述结果可写成，当nn充分大时，Xˉ−μσ/n\frac{\bar{X}-\mu}{\sigma / \sqrt{n}}$N(0,1)$或$\bar{X}$N(μ,σ2/n)N\left(\mu, \sigma^{2} / n\right)

这就是说，均值为μ\mu，方差为σ2>0\sigma^{2}>0的独立同分布随机变量，X1,X2,⋯ ,XnX_{1}, X_{2}, \cdots, X_{n}的算术平均Xˉ=1n∑k=1nXk\bar{X}=\frac{1}{n} \sum_{k=1}^{n} X_{k}，当nn充分大时，近似地服从均值为μ\mu，方差为σ2/n\sigma^{2} / n的正态分布。

随机过程

随机过程（Stochastic Process）是一组随机变量XtX_{t}的集合，其中𝑡属于一个索引（index）集合𝒯．索引集合𝒯可以定义在时间域或者空间域，但一般为时间域，以实数或正数表示．当𝑡为实数时，随机过程为连续随机过程；当𝑡为整数时，为离散随机过程．日常生活中的很多例子包括股票的波动、语音信号、身高的变化等都可以看作随机过程．常见的和时间相关的随机过程模型包括伯努利过程、随机游走（Random Walk）、马尔可夫过程等．和空间相关的随机过程通常称为随机场（Random Field）．比如一张二维的图片，每个像素点（变量）通过空间的位置进行索引，这些像素就组成了一个随机过程。

马尔可夫过程

在随机过程中，马尔可夫性质（Markov Property）是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态．以离散随机过程为例，假设随机变量X0,X1,⋯ ,XTX_{0}, X_{1}, \cdots, X_{T}构成一个随机过程．这些随机变量的所有可能取值的集合被称为状态空间（State Space）．如果Xt+1X_{t+1}对于过去状态的条件概率分布仅是XtX_{t}的一个函数，则

P(Xt+1=xt+1∣X0:t=x0:t)=P(Xt+1=xt+1∣Xt=xt)P\left(X_{t+1}=x_{t+1} | X_{0: t}=x_{0: t}\right)=P\left(X_{t+1}=x_{t+1} | X_{t}=x_{t}\right)

其中X0:tX_{0}: t表示变量集合X0,X1,⋯ ,Xt,x0:tX_{0}, X_{1}, \cdots, X_{t}, x_{0: t}为在状态空间中的状态序列。

马尔可夫性质也可以描述为给定当前状态时，将来的状态与过去状态是条件独立的。

马尔可夫链

离散时间的马尔可夫过程也称为马尔可夫链（Markov Chain）．如果一个马尔可夫链的条件概率P(Xt+1=s∣Xt=s′)=mss′P\left(X_{t+1}=s | X_{t}=s^{\prime}\right)=m_{s s^{\prime}}，只和状态𝑠和𝑠′相关，和时间𝑡无关，则称为时间同质的马尔可夫链（Time-Homogeneous Markov Chain），其中mSS′m_{S S^{\prime}}称为状态转移概率．如果状态空间大小𝐾是有限的，状态转移概率可以用一个矩阵M∈RK×K\boldsymbol{M} \in \mathbb{R}^{K \times K}表示，称为状态转移矩阵（Transition Matrix），其中元素mijm_{i j}表示状态Si\mathbf{S}_{i}转移到状态SjS_{j}的概率。

假设状态空间大小为𝐾，向量π=[π1,⋯ ,πK]⊤\boldsymbol{\pi}=\left[\pi_{1}, \cdots, \pi_{K}\right]^{\top}为状态空间中的一个分布，满足0≤πk≤10 \leq \pi_{k} \leq 1和∑k=1Kπk=1\sum_{k=1}^{K} \pi_{k}=1。

对于状态转移矩阵为𝑴的时间同质的马尔可夫链，若存在一个分布𝝅满足π=Mπ\pi=M \pi，则称分布𝝅为该马尔可夫链的平稳分布（Stationary Distribution）．根据特征向量的定义可知，𝝅为矩阵𝑴的（归一化）的对应特征值为1的特征向量。

如果一个马尔可夫链的状态转移矩阵𝑴满足所有状态可遍历性以及非周期性，那么对于任意一个初始状态分布π(0)\pi^{(0)}，在经过一定时间的状态转移之后，都会收敛到平稳分布，即π=lim⁡T→∞MTπ(0)\pi=\lim _{T \rightarrow \infty} \boldsymbol{M}^{T} \boldsymbol{\pi}^{(0)}。

细致平稳条件（Detailed Balance Condition）：给定一个状态空间中的分布π∈[0,1]K\pi \in[0,1]^{K}，如果一个状态转移矩阵为M∈RK×K\boldsymbol{M} \in \mathbb{R}^{K \times K}的马尔可夫链满足πimij=πjmji,∀1≤i,j≤K\pi_{i} m_{i j}=\pi_{j} m_{j i}, \quad \forall 1 \leq i, j \leq K，则该马尔可夫链经过一定时间的状态转移后一定会收敛到分布𝝅．细致平稳条件只是马尔可夫链收敛的充分条件，不是必要条件．细致平稳条件保证了从状态𝑖转移到状态𝑗的数量和从状态𝑗转移到状态𝑖的数量相一致，互相抵消，所以数量不发生改变．

高斯过程

高斯过程（Gaussian Process）也是一种应用广泛的随机过程模型．假设有一组连续随机变量X0,X1,⋯ ,XTX_{0}, X_{1}, \cdots, X_{T}，如果由这组随机变量构成的任一有限集合Xt1,⋯ ,tN=[Xt1,⋯ ,XtN]⊤,1≤N≤TX_{t_{1}, \cdots, t_{N}}=\left[X_{t_{1}}, \cdots, X_{t_{N}}\right]^{\top}, \quad 1 \leq N \leq T都服从一个多元正态分布，那么这组随机变量为一个随机过程．高斯过程也可以定义为：如果Xt1,⋯ ,tNX_{t_{1}, \cdots, t_{N}}的任一线性组合都服从一元正态分布，那么这组随机变量为一个随机过程．

高斯过程回归（Gaussian Process Regression）是利用高斯过程来对一个函数分布进行建模．和机器学习中参数化建模（比如贝叶斯线性回归）相比，高斯过程是一种非参数模型，可以拟合一个黑盒函数，并给出拟合结果的置信度。

假设一个未知函数𝑓(𝒙)服从高斯过程，且为平滑函数．如果两个样本x1,x2\boldsymbol{x}_{1}, \boldsymbol{x}_{2}比较接近，那么对应的f(x1),f(x2)f\left(x_{1}\right), f\left(x_{2}\right)也比较接近．假设从函数𝑓(𝒙)中采样有限个样本X=[x1,x2,⋯ ,xN]\boldsymbol{X}=\left[\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \cdots, \boldsymbol{x}_{N}\right]，这𝑁个点服从一个多元正态分布，
[f(x1),f(x2),⋯ ,f(xN)]⊤∼N(μ(X),K(X,X))\left[f\left(x_{1}\right), f\left(x_{2}\right), \cdots, f\left(x_{N}\right)\right]^{\top} \sim \mathcal{N}(\mu(X), K(X, X))

其中μ(X)=[μ(x1),μ(x2),⋯ ,μ(xN)]⊤\mu(\boldsymbol{X})=\left[\mu\left(\boldsymbol{x}_{1}\right), \mu\left(\boldsymbol{x}_{2}\right), \cdots, \mu\left(\boldsymbol{x}_{N}\right)\right]^{\top}是均值向量，K(X,X)=[k(xi,xj)]N×N\boldsymbol{K}(\boldsymbol{X}, \boldsymbol{X})=\left[k\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)\right]_{N \times N}是协方差矩阵，k(xi,xj)k\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)为核函数，可以衡量两个样本的相似度。

在高斯过程回归中，一个常用的核函数是平方指数（Squared Exponential）核函数：

k(xi,xj)=exp⁡(−∥xi−xj∥22l2)k\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(\frac{-\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}}{2 l^{2}}\right)

其中𝑙为超参数．当xi\boldsymbol{x}_{\boldsymbol{i}}和xj\boldsymbol{x}_{\boldsymbol{j}}越接近，其函数值越大，表明f(xi)f\left(x_{i}\right)和f(xj)f\left(x_{j}\right)越相关．

信息论

自信息和熵

自信息（Self Information）表示一个随机事件所包含的信息量．一个随机事件发生的概率越高，其自信息越低．如果一个事件必然发生，其自信息为0

对于一个随机变量𝑋（取值集合为𝒳，概率分布为𝑝(𝑥),𝑥 ∈ 𝒳），当𝑋 = 𝑥时的自信息𝐼(𝑥)定义为I(x)=−log⁡p(x)I(x)=-\log p(x)，对于分布为𝑝(𝑥)的随机变量𝑋，其自信息的数学期望，即熵𝐻(𝑋)定义为(𝐻(𝑋)也 经 常 写 作𝐻(𝑝))：

H(X)=EX[I(x)]=EX[−log⁡p(x)]=−∑x∈Xp(x)log⁡p(x)\begin{aligned} H(X) &=\mathbb{E}_{X}[I(x)] \\ &=\mathbb{E}_{X}[-\log p(x)] \\ &=-\sum_{x \in \mathcal{X}} p(x) \log p(x) \end{aligned}

熵越高，则随机变量的信息越多；熵越低，则随机变量的信息越少．如果变量𝑋当且仅当在𝑥时𝑝(𝑥) = 1，则熵为0．也就是说，对于一个确定的信息，其熵为0，信息量也为0．如果其概率分布为一个均匀分布，则熵最大．

假设一个随机变量𝑋有三种可能值x1,x2,x3x_{1}, x_{2}, x_{3},不同概率分布对应的熵如下:

熵编码

在对分布𝑝(𝑥)的符号进行编码时，熵𝐻(𝑝)也是理论上最优的平均编码长度，这种编码方式称为熵编码（Entropy Encoding）

联合熵和条件熵

对于两个离散随机变量𝑋和𝑌，假设𝑋取值集合为𝒳；𝑌取值集合为𝒴，其联合概率分布满足为𝑝(𝑥,𝑦)，则𝑋和𝑌的联合熵（Joint Entropy）为

H(X,Y)=−∑x∈x∑y∈yp(x,y)log⁡p(x,y)H(X, Y)=-\sum_{x \in x} \sum_{y \in y} p(x, y) \log p(x, y)

𝑋和𝑌的条件熵（Conditional Entropy）为:

H(X∣Y)=−∑x∈x∑y∈Yp(x,y)log⁡p(x∣y)=−∑x∈X∑y∈Yp(x,y)log⁡p(x,y)p(y)\begin{aligned} H(X | Y) &=-\sum_{x \in x} \sum_{y \in \mathcal{Y}} p(x, y) \log p(x | y) \\ &=-\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x, y) \log \frac{p(x, y)}{p(y)} \end{aligned}

根据其定义，条件熵也可以写为H(X∣Y)=H(X,Y)−H(Y)H(X | Y)=H(X, Y)-H(Y)

互信息

互信息（Mutual Information）是衡量已知一个变量时，另一个变量不确定性的减少程度．两个离散随机变量𝑋和𝑌的互信息定义为

I(X;Y)=∑x∈x∑y∈yp(x,y)log⁡p(x,y)p(x)p(y)I(X ; Y)=\sum_{x \in x} \sum_{y \in y} p(x, y) \log \frac{p(x, y)}{p(x) p(y)}

互信息的一个性质为:

I(X;Y)=H(X)−H(X∣Y)=H(Y)−H(Y∣X)\begin{aligned} I(X ; Y) &=H(X)-H(X | Y) \\ &=H(Y)-H(Y | X) \end{aligned}

如果变量𝑋和𝑌互相独立，它们的互信息为零．

交叉熵和散度

交叉熵

对于分布为𝑝(𝑥)的随机变量，熵𝐻(𝑝)表示其最优编码长度．交叉熵（CrossEntropy）是按照概率分布𝑞的最优编码对真实分布为𝑝的信息进行编码的长度，定义为H(p,q)=Ep[−log⁡q(x)]=−∑xp(x)log⁡q(x)\begin{aligned} H(p, q) &=\mathbb{E}_{p}[-\log q(x)] \\ &=-\sum_{x} p(x) \log q(x) \end{aligned}

在给定𝑝的情况下，如果𝑞和𝑝越接近，交叉熵越小；如果𝑞和𝑝越远，交叉熵就越大．

KL散度

KL散度（Kullback-Leibler Divergence），也叫KL距离或相对熵(RelativeEntropy)，是用概率分布𝑞来近似𝑝时所造成的信息损失量．KL散度是按照概率分布𝑞的最优编码对真实分布为𝑝的信息进行编码，其平均编码长度（即交叉熵）𝐻(𝑝,𝑞)和𝑝的最优平均编码长度（即熵）𝐻(𝑝)之间的差异．对于离散概率分布𝑝和𝑞，从𝑞到𝑝的KL散度定义为

KL(p,q)=H(p,q)−H(p)=∑xp(x)log⁡p(x)q(x)\begin{aligned} \mathrm{KL}(p, q) &=H(p, q)-H(p) \\ &=\sum_{x} p(x) \log \frac{p(x)}{q(x)} \end{aligned}

其中为了保证连续性，定义0log⁡00=0,0log⁡0q=00 \log \frac{0}{0}=0,0 \log \frac{0}{q}=0。

KL散度总是非负的，KL(𝑝,𝑞) ≥ 0，可以衡量两个概率分布之间的距离．KL散度只有当𝑝 = 𝑞时，KL(𝑝,𝑞) = 0．如果两个分布越接近，KL散度越小；如果两个分布越远，KL散度就越大．但KL散度并不是一个真正的度量或距离，一是KL散度不满足距离的对称性，二是KL散度不满足距离的三角不等式性质

JS散度

JS散度（Jensen-Shannon Divergence）是一种对称的衡量两个分布相似度的度量方式，定义为JS(p,q)=12KL(p,m)+12KL(q,m)\mathrm{JS}(p, q)=\frac{1}{2} \mathrm{KL}(p, m)+\frac{1}{2} \mathrm{KL}(q, m)，
其中m=12(p+q)m=\frac{1}{2}(p+q)。

JS散度是KL散度一种改进．但两种散度都存在一个问题，即如果两个分布𝑝,𝑞没有重叠或者重叠非常少时，KL散度和JS散度都很难衡量两个分布的距离。

Wasserstein距离

Wasserstein距离（Wasserstein Distance）也用于衡量两个分布之间的距离．对于两个分布q1,q2q_{1}, q_{2}，pth p^{\text {th }} -Wasserstein距离定义为
Wp(q1,q2)=(inf⁡γ(x,y)∈Γ(q1,q2)E(x,y)∼γ(x,y)[d(x,y)p])1pW_{p}\left(q_{1}, q_{2}\right)=\left(\begin{array}{c}\inf \\ \gamma(x, y) \in \Gamma\left(q_{1}, q_{2}\right)\end{array} \mathbb{E}_{(x, y) \sim \gamma(x, y)}\left[d(x, y)^{p}\right]\right)^{\frac{1}{p}}

其中Γ(q1,q2)\Gamma\left(q_{1}, q_{2}\right)是边际分布为q1和q2q_{1}和q_{2}的所有可能的联合分布集合，d(x,y)d(x, y)为𝑥和𝑦的距离，比如ℓp\ell_{p}距离等。

如果将两个分布看作两个土堆，联合分布γ(x,y)\gamma(x, y)看作从土堆q1q_{1}的位置𝑥到土堆q2q_{2}的位置𝑦的搬运土的数量

∑xγ(x,y)=q2(y)\sum_{x} \gamma(x, y)=q_{2}(y)

∑yγ(x,y)=q1(x)\sum_{y} \gamma(x, y)=q_{1}(x)

q1q_{1}和q2q_{2}为γ(x,y)\gamma(x, y)的两个边际分布。

E(x,y)∼γ(x,y)[d(x,y)p]\mathbb{E}_{(x, y) \sim \gamma(x, y)}\left[d(x, y)^{p}\right]可以理解为在联合分布𝛾(𝑥,𝑦)下把形状为q1q_{1}，的土堆搬运到形状为q2q_{2}的工作量，

E(x,y)∼γ(x,y)[d(x,y)p]=∑(x,y)γ(x,y)d(x,y)p\mathbb{E}_{(x, y) \sim \gamma(x, y)}\left[d(x, y)^{p}\right]=\sum_{(x, y)} \gamma(x, y) d(x, y)^{p}

其中从土堆q1q_{1}中的点𝑥到土堆q2q_{2}中的点𝑦的移动土的数量和距离分别为𝛾(𝑥,𝑦)和d(x,y)pd(x, y)^{p}因此，Wasserstein距离可以理解为搬运土堆的最小工作量，也称为推土机距离（Earth-Mover’s Distance，EMD），图E.1给出了两个离散变量分布的Wasserstein距离示例．图E.1c中同颜色方块表示在分布q1q_{1}中为相同位置。


Wasserstein距离相比KL散度和JS散度的优势在于：即使两个分布没有重叠或者重叠非常少，Wasserstein距离仍然能反映两个分布的远近．

对于RD\mathbb{R}^{D}空间中的两个高斯分布p=N(μ1,Σ1)p=\mathcal{N}\left(\mu_{1}, \mathbf{\Sigma}_{1}\right)和q=N(μ2,Σ2)q=\mathcal{N}\left(\mu_{2}, \mathbf{\Sigma}_{2}\right)，它们的2nd 2^{\text {nd }} -Wasserstein，W2(p,q)=∥μ1−μ2∥22+tr⁡(Σ1+Σ2−2(Σ21/2Σ1Σ21/2)1/2)W_{2}(p, q)=\left\|\mu_{1}-\mu_{2}\right\|_{2}^{2}+\operatorname{tr}\left(\Sigma_{1}+\Sigma_{2}-2\left(\Sigma_{2}^{1 / 2} \Sigma_{1} \Sigma_{2}^{1 / 2}\right)^{1 / 2}\right)。

当两个分布的方差为0时，2nd−2^{\mathrm{nd}}- Wasserstein距离等价于欧氏距离。

最优化

如果目标函数或任何一个约束函数为非线性函数，则该问题为非线性规划（Nonlinear Programming）问题。

在非线性优化问题中，有一类比较特殊的问题是凸优化（Convex Optimiza-tion）问题．在凸优化问题中，变量𝒙的可行域为凸集（Convex Set），即对于集合中任意两点，它们的连线全部位于集合内部．目标函数𝑓也必须为凸函数，即满足

f(αx+(1−α)y)≤αf(x)+(1−α)f(y),∀α∈[0,1]f(\alpha x+(1-\alpha) y) \leq \alpha f(x)+(1-\alpha) f(y), \forall \alpha \in[0,1]

凸优化问题是一种特殊的约束优化问题，需满足目标函数为凸函数，并且等式约束函数为线性函数，不等式约束函数为凸函数．

优化算法

优化问题一般都可以通过迭代的方式来求解：通过猜测一个初始的估计x0\boldsymbol{x}_{0}，然后不断迭代产生新的估计x1,x2,⋯xt\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \cdots \boldsymbol{x}_{t}，希望xt\boldsymbol{x}_{t}最终收敛到期望的最优解x∗\boldsymbol{x}^{*}，一个好的优化算法应该是在一定的时间或空间复杂度下能够快速准确地找到最优解．同时，好的优化算法受初始猜测点的影响较小，通过迭代能稳定地找到最优解x∗\boldsymbol{x}^{*}，然后迅速收敛于x∗x^{*}。

优化算法中常用的迭代方法有线性搜索和置信域方法等．线性搜索的策略是寻找方向和步长，具体算法有梯度下降法、牛顿法、共轭梯度法等

全局最小解和局部最小解

对于很多非线性优化问题，会存在若干个局部最小值（Local Minima），其对应的解称为局部最小解（Local Minimizer）．局部最小解也称为局部最小值点，或更一般性地称为局部最优解．局部最小解x∗x^{*}定义为：存在一个𝛿 > 0，对于所有的满足∥x−x∗∥≤δ\left\|x-x^{*}\right\| \leq \delta的𝒙，都有f(x∗)≤f(x)f\left(x^{*}\right) \leq f(x)．也就是说，在x∗x^{*}的邻域内，所有的函数值都大于或者等于f(x∗)f\left(x^{*}\right)。

对于所有的x∈Dx \in \mathcal{D}，都有f(x∗)≤f(x)f\left(\boldsymbol{x}^{*}\right) \leq f(\boldsymbol{x})成立，则x∗x^{*}为全局最小解（GlobalMinimizer）

求局部最小解一般是比较容易的，但很难保证其为全局最小解．对于线性规划或凸优化问题，局部最小解就是全局最小解．

要确认一个点x∗x^{*}是否为局部最小解，通过比较它的邻域内有没有更小的函数值是不现实的．如果函数f(x)f(x)是二次连续可微的，我们可以通过检查目标函数在点x∗x^{*}和Hessian矩阵∇2f(x∗)\nabla^{2} f\left(\boldsymbol{x}^{*}\right)来判断。

局部最小解的一阶必要条件：如果x∗x^{*}为局部最小解并且函数𝑓在x∗\boldsymbol{x}^{*}的邻域内一阶可微，则在∇f(x∗)=0\nabla f\left(x^{*}\right)=0。

函数𝑓(𝒙)的一阶偏导数为0的点也称为驻点（Stationary Point）或临界点（Critical Point）．驻点不一定为局部最小解．

局部最小解的二阶必要条件：如果x∗x^{*}为局部最小解并且函数𝑓在x∗x^{*}的邻域内二阶可微，则在∇f(x∗)=0,∇2f(x∗)\nabla f\left(x^{*}\right)=0, \nabla^{2} f\left(x^{*}\right)为半正定矩阵．

梯度下降法

对于函数𝑓(𝒙)，如果𝑓(𝒙)在点𝒙𝑡附近是连续可微的，那么𝑓(𝒙)下降最快的方向是𝑓(𝒙)在xt\boldsymbol{x}_{t}点的梯度方法的反方向
根据泰勒一阶展开公式，有

f(xt+1)=f(xt+Δx)≈f(xt)+Δx⊤∇f(xt)f\left(x_{t+1}\right)=f\left(x_{t}+\Delta x\right) \approx f\left(x_{t}\right)+\Delta x^{\top} \nabla f\left(x_{t}\right)

要使得f(xt+1)<f(xt)f\left(x_{t+1}\right)<f\left(x_{t}\right)，就得使Δx⊤∇f(xt)<0\Delta x^{\top} \nabla f\left(x_{t}\right)<0，我们取Δx=−α∇f(xt)\Delta x=-\alpha \nabla f\left(x_{t}\right)。如果𝛼 > 0为一个够小数值时，那么f(xt+1)<f(xt)f\left(x_{t+1}\right)<f\left(x_{t}\right)成立，这样我们就可以从一个初始值x0\boldsymbol{x}_{0}出发，通过迭代公式xt+1=xt−αt∇f(xt),t≥0\boldsymbol{x}_{t+1}=\boldsymbol{x}_{t}-\alpha_{t} \nabla f\left(\boldsymbol{x}_{t}\right), t \geq 0，生成序列x0,x1,x2,…\boldsymbol{x}_{0}, \boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \dots，使得f(x0)≥f(x1)≥f(x2)≥⋯f\left(x_{0}\right) \geq f\left(x_{1}\right) \geq f\left(x_{2}\right) \geq \cdots

如果顺利的话，序列(xn)\left(\boldsymbol{x}_{n}\right)收敛到局部最小解x∗\boldsymbol{x}^{*}，注意，每次迭代步长𝛼可以改变，但其取值必须合适，如果过大就不会收敛，如果过小则收敛速度太慢．

梯度下降法的过程如图C.1所示．曲线是等高线（水平集），即函数𝑓为不同常数的集合构成的曲线．红色的箭头指向该点梯度的反方向（梯度方向与通过该点的等高线垂直）．沿着梯度下降方向，将最终到达函数𝑓值的局部最小解．

梯度下降法为一阶收敛算法，当靠近局部最小解时梯度变小，收敛速度会变慢，并且可能以“之字形”的方式下降．如果目标函数为二阶连续可微，我们可以采用牛顿法．牛顿法（Newton’s method）为二阶收敛算法，收敛速度更快，但是每次迭代需要计算Hessian矩阵的逆矩阵，复杂度较高．

梯度下降法步骤：

输入：目标函数f(x)f(x)，梯度函数g(x)=∇f(x)g(x)=\nabla f(x)，计算精度ε\varepsilon

输出：f(x)f(x)的极小点，x∗x^{*}

  1. 取初始值x(0)∈Rnx^{(0)} \in \mathbf{R}^{n}，置k=0k=0。
  2. 计算f(x(k))f\left(x^{(k)}\right)
  3. 计算梯度gk=g(x(k))g_{k}=g\left(x^{(k)}\right)，当∥gk∥<ε\left\|g_{k}\right\|<\varepsilon时，停止迭代，令x∗=x(k)x^{*}=x^{(k)}，否则，令pk=−g(x(k))p_{k}=-g\left(x^{(k)}\right)，求λk\lambda_{k}，使f(x(k)+λkpk)=min⁡λ⩾0f(x(k)+λpk)f\left(x^{(k)}+\lambda_{k} p_{k}\right)=\min _{\lambda \geqslant 0} f\left(x^{(k)}+\lambda p_{k}\right)
  4. 置x(k+1)=x(k)+λkpkx^{(k+1)}=x^{(k)}+\lambda_{k} p_{k}，计算f(x(k+1))f\left(x^{(k+1)}\right)，当∥f(x(k+1))−f(x(k))∥<ε\left\|f\left(x^{(k+1)}\right)-f\left(x^{(k)}\right)\right\|<\varepsilon或∥x(k+1)−x(k)∥<ε\left\|x^{(k+1)}-x^{(k)}\right\|<\varepsilon时，停止迭代，令x∗=x^{*}=x(k+1)x^{(k+1)}。
  5. 否则，置k=k+1k=k+1，转3.

牛顿法

考虑无约束最优化问题，min⁡x∈Rnf(x)\min _{x \in \mathbf{R}^{n}} f(x)，其中x∗x^{*}为目标函数的极小点。
假设f(x)f(x)具有二阶连续偏导数，若第kk次送代值为x(k)x^{(k)}，则可将f(x)f(x)在x(k)x^{(k)}附近进行二阶泰勒展开：

f(x)=f(x(k))+gkT(x−x(k))+12(x−x(k))TH(x(k))(x−x(k))f(x)=f\left(x^{(k)}\right)+g_{k}^{\mathrm{T}}\left(x-x^{(k)}\right)+\frac{1}{2}\left(x-x^{(k)}\right)^{\mathrm{T}} H\left(x^{(k)}\right)\left(x-x^{(k)}\right)

这里，gk=g(x(k))=∇f(x(k))g_{k}=g\left(x^{(k)}\right)=\nabla f\left(x^{(k)}\right)是f(x)f(x)的梯度向量在点x(k)x^{(k)}的值，H(x(k))H\left(x^{(k)}\right)是f(x)f(x)的海森矩阵：

H(x)=[∂2f∂xi∂xj]n×nH(x)=\left[\frac{\partial^{2} f}{\partial x_{i} \partial x_{j}}\right]_{n \times n}

在点x(k)x^{(k)}的值。函数f(x)f(x)s有极值的必要条件是在极值点处一阶导数为 0, 即梯度向量为 0。特别是当H(x(k))H\left(x^{(k)}\right)是正定矩阵时，函数f(x)f(x)的极值为极小值。

牛顿法利用极小点的必要条件∇f(x)=0\nabla f(x)=0，每次迭代中从点x(k)x^{(k)}开始，求目标函数的极小点，作为第k+1k+1次迭代值x(k+1)x^{(k+1)}，具体地，假设x(k+1)x^{(k+1)}满足∇f(x(k+1))=0\nabla f\left(x^{(k+1)}\right)=0，，又有∇f(x)=gk+Hk(x−x(k))\nabla f(x)=g_{k}+H_{k}\left(x-x^{(k)}\right)，其中Hk=H(x(k))H_{k}=H\left(x^{(k)}\right)，得

gk+Hk(x(k+1)−x(k))=0g_{k}+H_{k}\left(x^{(k+1)}-x^{(k)}\right)=0

x(k+1)=x(k)−Hk−1gkx^{(k+1)}=x^{(k)}-H_{k}^{-1} g_{k}

算法步骤：

输入：目标函数f(x)f(x)，梯度g(x)=∇f(x)g(x)=\nabla f(x)，海森矩阵H(x)H(x)，精度要求ε\varepsilon

输出：f(x)f(x)的极小点，x∗x^{*}

  1. 取初始点x(0)x^{(0)}，置k=0k=0
  2. 计算gk=g(x(k))g_{k}=g\left(x^{(k)}\right)
  3. 若∥gk∥<ε\left\|g_{k}\right\|<\varepsilon，则停止计算，得近似解x∗=x(k)x^{*}=x^{(k)}
  4. 计算Hk=H(x(k))H_{k}=H\left(x^{(k)}\right)，并求pkp_{k}，Hkpk=−gkH_{k} p_{k}=-g_{k}
  5. 置x(k+1)=x(k)+pkx^{(k+1)}=x^{(k)}+p_{k}
  6. 置k=k+1k=k+1，转2

步骤4求pkp_{k}，pk=−Hk−1gkp_{k}=-H_{k}^{-1} g_{k}，要求Hk−1H_{k}^{-1}，计算较复杂，固有其他解决方法，如拟牛顿法。

拉格朗日乘数法与KKT条件(nndl)

拉格朗日乘数法（Lagrange Multiplier）以数学家约瑟夫·拉格朗日命名．是一种有效求解约束优化问题的优化方法，约束优化问题可以表示为：

min⁡xf(x)\min _{x} f(x)

s.t. hm(x)=0,m=1,…,M\quad h_{m}(\boldsymbol{x})=0, \quad m=1, \ldots, M
gn(x)≤0,n=1,…,Ng_{n}(\boldsymbol{x}) \leq 0, \quad n=1, \ldots, N

其中hm(x)h_{m}(\boldsymbol{x})为等式约束函数，gn(x)g_{n}(\boldsymbol{x})为不等式约束函数．𝒙的可行域为

D=dom⁡(f)∩⋂m=1Mdom⁡(hm)∩⋂n=1Ndom⁡(gn)⊆RD\mathcal{D}=\operatorname{dom}(f) \cap \bigcap_{m=1}^{M} \operatorname{dom}\left(h_{m}\right) \cap \bigcap_{n=1}^{N} \operatorname{dom}\left(g_{n}\right) \subseteq \mathbb{R}^{D}

其中dom⁡(f)\operatorname{dom}(f)是函数𝑓的定义域。

等式约束优化问题

如果公式中只有等式约束，我们可以构造一个拉格朗日函数Λ(x,λ)\Lambda(\boldsymbol{x}, \lambda):

Λ(x,λ)=f(x)+∑m=1Mλmhm(x)\Lambda(\boldsymbol{x}, \lambda)=f(\boldsymbol{x})+\sum_{m=1}^{M} \lambda_{m} h_{m}(\boldsymbol{x})

其中𝜆为拉格朗日乘数，可以是正数或负数．如果f(x∗)f\left(x^{*}\right)是原始约束优化问题的局部最优值，那么存在一个λ∗\lambda^{*}使得(x∗,λ∗)\left(x^{*}, \lambda^{*}\right)为拉格朗日函数Λ(x,λ)\Lambda(x, \lambda)的驻点，．因此，只需要令∂Λ(x,λ)∂x=0\frac{\partial \Lambda(x, \lambda)}{\partial x}=0和∂Λ(x,λ)∂λ=0\frac{\partial \Lambda(x, \lambda)}{\partial \lambda}=0，得到：

∇f(x)+∑m=1Mλm∇hm(x)=0\nabla f(\boldsymbol{x})+\sum_{m=1}^{M} \lambda_{m} \nabla h_{m}(\boldsymbol{x})=0
hm(x)=0,∀m=1,⋯ ,Mh_{m}(\boldsymbol{x})=0, \quad \forall m=1, \cdots, M

上面方程组的解即为原始问题的可能解．因为驻点不一定是最小解，所以在实际应用中需根据具体问题来验证是否为最小解。

拉格朗日乘数法是将一个有𝐷个变量和𝑀个等式约束条件的最优化问题转换为一个有𝐷 + 𝑀个变量的函数求驻点的问题．拉格朗日乘数法所得的驻点会包含原问题的所有最小解，但并不保证每个驻点都是原问题的最小解。

不等式约束优化问题

对于公式中定义的一般约束优化问题，其拉格朗日函数为：

Λ(x,a,b)=f(x)+∑m=1Mamhm(x)+∑n=1Nbngn(x)\Lambda(\boldsymbol{x}, \boldsymbol{a}, \boldsymbol{b})=f(\boldsymbol{x})+\sum_{m=1}^{M} a_{m} h_{m}(\boldsymbol{x})+\sum_{n=1}^{N} b_{n} g_{n}(\boldsymbol{x})

其中a=[a1,⋯ ,aM]⊤\boldsymbol{a}=\left[a_{1}, \cdots, a_{M}\right]^{\top}为等式约束的拉格朗日乘数，b=[b1,⋯ ,bN]⊤\boldsymbol{b}=\left[b_{1}, \cdots, b_{N}\right]^{\top}为不等式约束的拉格朗日乘数。

不等式约束优化问题中的拉格朗日乘数也称为KKT乘数。

当约束条件不满足时，有max⁡a,bΛ(x,a,b)=∞\max _{a, b} \Lambda(x, a, b)=\infty，当约束条件满足时并且b≥0b \geq 0时，max⁡a,bΛ(x,a,b)=f(x)\max _{a, b} \Lambda(x, a, b)=f(x)，因此，原始约束优化问题等价于：

min⁡xmax⁡a,bΛ(x,a,b) s.t. b≥0\begin{array}{cl}\min _{x} \max _{a, b} & \Lambda(x, a, b) \\ \quad \text { s.t. } & b \geq 0\end{array}

这个min-max优化问题称为主问题

主问题的优化一般比较困难，我们可以通过交换min-max的顺序来简化．定义拉格朗日对偶函数为

Γ(a,b)=inf⁡x∈DΛ(x,a,b)\Gamma(\boldsymbol{a}, \boldsymbol{b})=\inf _{x \in \mathcal{D}} \Lambda(\boldsymbol{x}, \boldsymbol{a}, \boldsymbol{b})

Γ(𝒂,𝒃)是一个凹函数，即使𝑓(𝒙)是非凸的。

当𝒃 ≥ 0时，对于任意的x~∈D\tilde{\boldsymbol{x}} \in \mathcal{D}，有

Γ(a,b)=inf⁡x∈DΛ(x,a,b)≤Λ(x~,a,b)≤f(x~)\Gamma(\boldsymbol{a}, \boldsymbol{b})=\inf _{\boldsymbol{x} \in \mathcal{D}} \Lambda(\boldsymbol{x}, \boldsymbol{a}, \boldsymbol{b}) \leq \Lambda(\tilde{\boldsymbol{x}}, \boldsymbol{a}, \boldsymbol{b}) \leq f(\tilde{\boldsymbol{x}})

令p∗\boldsymbol{p}^{*}是原问题的最优值，则有：

Γ(a,b)≤p∗\Gamma(\boldsymbol{a}, \boldsymbol{b}) \leq \boldsymbol{p}^{*}

即拉格朗日对偶函数Γ(𝒂,𝒃)为原问题最优值的下界。

优化拉格朗日对偶函数Γ(𝒂,𝒃)并得到原问题的最优下界，称为拉格朗日对偶问题（Lagrange Dual Problem）

max⁡a,bΓ(a,b)\max _{\boldsymbol{a}, \boldsymbol{b}} \Gamma(\boldsymbol{a}, \boldsymbol{b})
s.t. b≥0\quad \boldsymbol{b} \geq 0

拉格朗日对偶函数为凹函数，因此拉格朗日对偶问题为凸优化问题．

令d∗\boldsymbol{d}^{*}表示拉格朗日对偶问题的最优值，则有d∗≤p∗\boldsymbol{d}^{*} \leq \boldsymbol{p}^{*}，这个性质称为弱对偶性（Weak Duality）．如果d∗=p∗\boldsymbol{d}^{*}=\boldsymbol{p}^{*}，这个性质称为强对偶性（Strong Duality）。

当强对偶性成立时，令x∗\boldsymbol{x}^{*}和a∗,b∗\boldsymbol{a}^{*}, \boldsymbol{b}^{*}分别是原问题和对偶问题的最优解，那么它们满足以下条件：

∇f(x∗)+∑m=1Mam∗∇hm(x∗)+∑n=1Nbn∗∇gn(x∗)=0hm(x∗)=0,m=1,⋯ ,Mgn(x∗)≤0,n=1,⋯ ,Nbn∗gn(x∗)=0,n=1,⋯ ,Nbn∗≥0,n=1,⋯ ,N\begin{aligned} \nabla f\left(\boldsymbol{x}^{*}\right)+& \sum_{m=1}^{M} a_{m}^{*} \nabla h_{m}\left(\boldsymbol{x}^{*}\right)+\sum_{n=1}^{N} b_{n}^{*} \nabla g_{n}\left(\boldsymbol{x}^{*}\right)=0 \\ h_{m}\left(\boldsymbol{x}^{*}\right) &=0, \quad m=1, \cdots, M \\ g_{n}\left(\boldsymbol{x}^{*}\right) & \leq 0, \quad n=1, \cdots, N \\ b_{n}^{*} g_{n}\left(\boldsymbol{x}^{*}\right) &=0, \quad n=1, \cdots, N \\ b_{n}^{*} & \geq 0, \quad n=1, \cdots, N \end{aligned}

这5个条件称为不等式约束优化问题的KKT条件（Karush-Kuhn-Tucker Con-dition）．KKT条件是拉格朗日乘数法在不等式约束优化问题上的泛化．当原问题是凸优化问题时，满足KKT条件的解也是原问题和对偶问题的最优解．

在KKT条件中，需要关注的是公式bn∗gn(x∗)=0,n=1,⋯ ,Nb_{n}^{*} g_{n}\left(\boldsymbol{x}^{*}\right)=0, \quad n=1, \cdots, N，称为互补松弛（ComplementarySlackness）条件．如果最优解x∗x^{*}出现在不等式约束的边界上gn(x)=0g_{n}(x)=0，则bn∗>0b_{n}^{*}>0。如果最优解x∗\boldsymbol{x}^{*}出现在不等式约束的内部gn(x)<0g_{n}(\boldsymbol{x})<0，则bn∗=0b_{n}^{*}=0．互补松弛条件说明当最优解出现在不等式约束的内部，则约束失效．

拉格朗日乘数法与KKT条件(统计学习方法)

原始问题

假设f(x),ci(x),hj(x)f(x), c_{i}(x), h_{j}(x)是定义在Rn\mathbf{R}^{n}上的连续可微函数。考虑约束最优化问题：

min⁡x∈Rnf(x)\min _{x \in \mathbf{R}^{n}} f(x)
s.t. ci(x)⩽0,i=1,2,⋯ ,k\quad c_{i}(x) \leqslant 0, \quad i=1,2, \cdots, k
hj(x)=0,j=1,2,⋯ ,lh_{j}(x)=0, \quad j=1,2, \cdots, l

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

首先，引进广义拉格朗日函数(generalized Lagrange function)

L(x,α,β)=f(x)+∑i=1kαici(x)+∑j=1lβjhj(x)L(x, \alpha, \beta)=f(x)+\sum_{i=1}^{k} \alpha_{i} c_{i}(x)+\sum_{j=1}^{l} \beta_{j} h_{j}(x)

这里，x=(x(1),x(2),⋯ ,x(n))T∈Rnx=\left(x^{(1)}, x^{(2)}, \cdots, x^{(n)}\right)^{\mathrm{T}} \in \mathbf{R}^{n}，αi,βj\alpha_{i}, \beta_{j}是拉格朗日乘子，αi⩾0\alpha_{i} \geqslant 0,考虑xx的函数：

θP(x)=max⁡α,β:αi⩾0L(x,α,β)\theta_{P}(x)=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)

这里，下标PP表示原始问题。

假设给定某个xx。如果xx违反原始问题的约束条件，即存在某个ii使得ci(x)>0c_{i}(x)>0或者存在某个jj使得hj(x)≠0h_{j}(x) \neq 0, 那么就有

θP(x)=max⁡α,β:αi⩾0[f(x)+∑i=1kαici(x)+∑j=1lβjhj(x)]=+∞\theta_{P}(x)=\max _{\alpha, \beta: \alpha_{i} \geqslant 0}\left[f(x)+\sum_{i=1}^{k} \alpha_{i} c_{i}(x)+\sum_{j=1}^{l} \beta_{j} h_{j}(x)\right]=+\infty

因为若某个ii使约束ci(x)>0c_{i}(x)>0,则可令αi→+∞\alpha_{i} \rightarrow+\infty，若某个jj使hj(x)≠0h_{j}(x) \neq 0，则可令βj\beta_{j}使βjhj(x)→+∞\beta_{j} h_{j}(x) \rightarrow+\infty，而将其余各αi,βj\alpha_{i}, \beta_{j}均取为0.

相反地，如果满足约束条件式，则有：

θP(x)={f(x)，x满足原始问题约束+∞\theta_{P}(x)=\left\{\begin{array}{l}f(x)，x满足原始问题约束 \\ +\infty\end{array}\right.

所以如果考虑极小化问题，

min⁡xθP(x)=min⁡xmax⁡α,β:αi⩾0L(x,α,β)\min _{x} \theta_{P}(x)=\min _{x} \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)

它是与原始最优化问题等价的，即它们有相同的解。问题min⁡xmax⁡α,β:αi⩾0L(x,α,β)\min _{x} \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)称为广义拉格朗日函数的极小极大问题。这样一来，就把原始最优化问题表示为广义拉格朗日函数的极小极大问题。为了方便，定义原始问题的最优值：

p∗=min⁡xθP(x)p^{*}=\min _{x} \theta_{P}(x)

称为原始问题的值。

对偶问题

定义θD(α,β)=min⁡xL(x,α,β)\theta_{D}(\alpha, \beta)=\min _{x} L(x, \alpha, \beta)再考虑极大化θD(α,β)=min⁡xL(x,α,β)\theta_{D}(\alpha, \beta)=\min _{x} L(x, \alpha, \beta)，即max⁡α,β:αi⩾0θD(α,β)=max⁡α,β:αi⩾0min⁡xL(x,α,β)\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \theta_{D}(\alpha, \beta)=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \min _{x} L(x, \alpha, \beta)

问题max⁡α,β:αi⩾0min⁡xL(x,α,β)\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \min _{x} L(x, \alpha, \beta)称为广义拉格朗日函数的极大极小问题。

可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题：

max⁡α,βθD(α,β)=max⁡α,βmin⁡xL(x,α,β) s.t. αi⩾0,i=1,2,⋯ ,k\begin{aligned} \max _{\alpha, \beta} \theta_{D}(\alpha, \beta)=& \max _{\alpha, \beta} \min _{x} L(x, \alpha, \beta) \\ \text { s.t. } & \alpha_{i} \geqslant 0, \quad i=1,2, \cdots, k \end{aligned}

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

d∗=max⁡α,β:αi⩾0θD(α,β)d^{*}=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \theta_{D}(\alpha, \beta)

称为对偶问题的值。

原始问题和对偶问题的值

定理一：若原始问题和对偶问题都有最优值，则

d∗=max⁡α,β:αi⩾0min⁡xL(x,α,β)⩽min⁡xmax⁡α,β:αi⩾0L(x,α,β)=p∗d^{*}=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \min _{x} L(x, \alpha, \beta) \leqslant \min _{x} \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)=p^{*}

证明：由max⁡α,βθD(α,β)=max⁡α,βmin⁡xL(x,α,β)\max _{\alpha, \beta} \theta_{D}(\alpha, \beta)=\max _{\alpha, \beta} \min _{x} L(x, \alpha, \beta)和θP(x)=max⁡α,β:αi⩾0L(x,α,β)\theta_{P}(x)=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)，对任意的α,β\alpha, \beta和xx,有

θD(α,β)=min⁡xL(x,α,β)⩽L(x,α,β)⩽max⁡α,β:αi⩾0L(x,α,β)=θP(x)\theta_{D}(\alpha, \beta)=\min _{x} L(x, \alpha, \beta) \leqslant L(x, \alpha, \beta) \leqslant \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)=\theta_{P}(x)，即

θD(α,β)⩽θP(x)\theta_{D}(\alpha, \beta) \leqslant \theta_{P}(x)，

由于原始问题和对偶问题均有最优值，所以，max⁡α,β:αi⩾0θD(α,β)⩽min⁡xθP(x)\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \theta_{D}(\alpha, \beta) \leqslant \min _{x} \theta_{P}(x)

即d∗=max⁡α,β:αi⩾0min⁡xL(x,α,β)⩽min⁡xmax⁡α,β:αi⩾0L(x,α,β)=p∗d^{*}=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \min _{x} L(x, \alpha, \beta) \leqslant \min _{x} \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)=p^{*}

推论:设x∗x^{*}和α∗,β∗\alpha^{*}, \beta^{*}分别是原始问题和对偶问题的可行解，并且d∗=p∗d^{*}=p^{*}，则x∗x^{*}和α∗,β∗\alpha^{*}, \beta^{*}分别是原始问题和对偶问题的最优解。

定理二：考虑原始问题和对偶问题，假设函数f(x)f(x)和ci(x)c_{i}(x)是凸函数，hj(x)h_{j}(x)是仿射函数，并且假设不等式约束ci(x)c_{i}(x)是严格可行的，即存在xx，对所有ii有ci(x)<0c_{i}(x)<0，则存在x∗,α∗,β∗x^{*}, \alpha^{*}, \beta^{*}，使x∗x^{*}是原始问题的解，α∗,β∗\alpha^{*}, \beta^{*}是对偶问题的解，并且：

p∗=d∗=L(x∗,α∗,β∗)p^{*}=d^{*}=L\left(x^{*}, \alpha^{*}, \beta^{*}\right)

定理三：考虑原始问题和对偶问题，假设函数f(x)f(x)和ci(x)c_{i}(x)是凸函数，hj(x)h_{j}(x)是仿射函数，并且不等式约束ci(x)c_{i}(x)是严格可行的，则x∗x^{*}和α∗,β∗\alpha^{*}, \beta^{*}分别是原始问题和对偶问题的解的充分必要条件是x∗,α∗,β∗x^{*}, \alpha^{*}, \beta^{*}满足下面的KKT条件：

∇xL(x∗,α∗,β∗)=0\nabla_{x} L\left(x^{*}, \alpha^{*}, \beta^{*}\right)=0
αi∗ci(x∗)=0,i=1,2,⋯ ,k\alpha_{i}^{*} c_{i}\left(x^{*}\right)=0, \quad i=1,2, \cdots, k
ci(x∗)⩽0,i=1,2,⋯ ,kc_{i}\left(x^{*}\right) \leqslant 0, \quad i=1,2, \cdots, k
αi∗⩾0,i=1,2,⋯ ,k\alpha_{i}^{*} \geqslant 0, \quad i=1,2, \cdots, k
hj(x∗)=0j=1,2,⋯ ,lh_{j}\left(x^{*}\right)=0 \quad j=1,2, \cdots, l

αi∗ci(x∗)=0,i=1,2,⋯ ,k\alpha_{i}^{*} c_{i}\left(x^{*}\right)=0, \quad i=1,2, \cdots, k称为KKT的对偶互补条件，由此条件可知，若αi∗>0\alpha_{i}^{*}>0，则ci(x∗)=0c_{i}\left(x^{*}\right)=0。