PRML读书笔记:数学基础


这是一些PRML相关的数学基础。

线性代数

行列式

行列式的定义

$$ \begin{aligned} D &= \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} \\ &= \sum (-1)^t a_{1p_1}a_{2p_2}\cdots a_{np_n} \end{aligned} $$

其中$t$为排列$a_{1p_1}a_{2p_2}\cdots a_{np_n}$的逆序数。

这个定义没什么用。

行列式的性质

  1. 如果互换矩阵$A$的两列得到的矩阵为$B$,则$|B| = - |A|$
  2. 如果矩阵$A$的某一列乘以常数$c$得到矩阵$B$,则$|B| = c|A|$
  3. 如果$B$是$A$初等列变换的结果,则$|B|=|A|$

特征值与特征向量

定义:设$A$是$nm$矩阵,如果存在一个数$\lambda$及非零的$n$维列向量$\boldsymbol{u}$,使得

$$
A\boldsymbol{u} = \lambda\boldsymbol{u}
$$

成立,则称$\lambda$是矩阵$A$的一个特征值,非零向量$\boldsymbol{u}$是矩阵$A$属于特征值$\lambda$的一个特征向量。

// 此处应有更多PRML附录里的内容

概率论与数理统计

伯努利分布

如果随机变量$X$只取0和1两个值,且相应的概率为$P(X=1)=p$,$p(X=0)=1-p$,$0<p<1$,则称随机变量$X$服从参数为$p$的伯努利分布,$X$的概率密度函数为

$$ p(x) = \begin{cases} p^x (1-p)^{1-x} & x=0,1\\ 0 & x \neq 0, 1 \end{cases} $$

高斯分布

高斯分布$X \sim N(\mu, \sigma^2)$的概率密度函数为

$$
p(x) = \frac{1}{\sqrt{2\pi}\sigma} \exp{\left[ -\frac{(x-\mu)^2}{2\sigma^2} \right]}
$$

多元高斯分布

对于多元高斯分布$\boldsymbol{X} \sim \mathcal{N}(\boldsymbol{\mu}, \boldsymbol{\Sigma})$,它的概率密度函数为:

$$
p(\boldsymbol{X}) =
\frac{1}{(2\pi)^{\frac{n}{2}} |\Sigma|^{\frac{1}{2}}}
\exp{\left[ -\frac{1}{2} (\boldsymbol{X}-\boldsymbol{\mu})^T \Sigma^{-1} (\boldsymbol{X}-\boldsymbol{\mu}) \right]}
$$

其中:

  • $\boldsymbol{X}$是一个随机向量,它是一个列向量
  • $n$是向量$\boldsymbol{X}$的维数
  • $\boldsymbol{\mu}$是均值,它是一个列向量
  • $\boldsymbol{\Sigma}$是协方差矩阵,它是一个方阵

导数

$p(\boldsymbol{X})$关于$\boldsymbol{\mu}$的偏导是

$$ \frac{\partial \mathcal{N}(\boldsymbol{X} | \boldsymbol{\mu}, \boldsymbol{\Sigma})}{\partial \boldsymbol{\mu}} = \mathcal{N}(\boldsymbol{X} | \boldsymbol{\mu}, \boldsymbol{\Sigma})\boldsymbol{\Sigma}^{-1} (\boldsymbol{X} - \boldsymbol{\mu}) $$

$p(\boldsymbol{X})$关于$\boldsymbol{\Sigma}$的偏导是

$$ \frac{\partial \mathcal{N}(\boldsymbol{X} | \boldsymbol{\mu}, \boldsymbol{\Sigma})}{\partial \boldsymbol{\Sigma}} = \frac{1}{2}\mathcal{N}(\boldsymbol{X} | \boldsymbol{\mu}, \boldsymbol{\Sigma}) (\boldsymbol{\Sigma}^{-1}(\boldsymbol{X} - \boldsymbol{\mu})(\boldsymbol{X} - \boldsymbol{\mu})^T\boldsymbol{\Sigma}^{-1} - \boldsymbol{\Sigma}^{-1}) $$

推导过程见Derivative of multivariate normal distribution wrt mean and covariance

拉格朗日乘数法

拉格朗日乘数法(Lagrange multiplier)的用途是寻找多元变量在一个或多个限制条件下的驻点。

等式限制下的拉格朗日乘数法

考虑一个$D$维变量$\boldsymbol{x}$和一个限制方程$g(\boldsymbol{x})=0$,最大化函数$f(\boldsymbol{x})$。

限制方程$g(\boldsymbol{x})=0$表示空间中的一个$D-1$维曲面。在曲面上的任意点处,$g$的梯度$\nabla g(\boldsymbol{x})$都正交于曲面。

限制曲面上使得$f(\boldsymbol{x})$最大的一个点$\boldsymbol{x}^ * $必然满足$\nabla f(\boldsymbol{x}^ * )$也正交于限制曲面,否则可以沿着限制曲面移动一个较短的距离以使$f(\boldsymbol{x})$增大,如下图所示。

f和g的梯度

因此$\nabla f$和$\nabla g$是平行的向量,一定存在一个参数$\lambda$使得

$$
\nabla f+\lambda \nabla g=0
$$

因此定义拉格朗日函数如下:

$$
L(\boldsymbol{x}, \lambda) \equiv f(\boldsymbol{x})+\lambda g(\boldsymbol{x})
$$

将$L$分别对$\boldsymbol{x}$和$\lambda$求偏导,可以分别得到驻点和限制方程的条件:

$$ \begin{aligned} \nabla_{\boldsymbol{x}}L &= \nabla f+\lambda \nabla g = 0 \\ \frac{\partial L}{\partial \lambda} &= g(\boldsymbol{x}) = 0 \end{aligned} $$

对于一个$D$维向量$\boldsymbol{x}$,上式给出了$D+1$个方程确定驻点$\boldsymbol{x}^*$和$\lambda$的值。

一个简单的例子

令$f(x_1, x_2) = 1 - x_1^2 - x_2^2$,$g(x_1, x_2) = x_1 + x_2 - 1 = 0$,则对应的拉格朗日函数为

$$
L(\boldsymbol{x}, \lambda)=1-x_{1}^{2}-x_{2}^{2}+\lambda\left(x_{1}+x_{2}-1\right)
$$

求偏导得到

$$ \begin{aligned} \frac{\partial L}{\partial x_1} &= -2x_1 + \lambda = 0 \\ \frac{\partial L}{\partial x_2} &= -2x_2 + \lambda = 0 \\ \frac{\partial L}{\partial \lambda} &= x_1 + x_2 - 1 = 0 \end{aligned} $$

求得驻点为$\boldsymbol{x}^* = (\frac{1}{2}, \frac{1}{2})$,对应的拉格朗日乘数为1。

不等式限制下的拉格朗日乘数法

下面考虑形式为$g(\boldsymbol{x}) \ge 0$的不等式限制下的最大化问题。可以按驻点的位置分成两种情况:

  1. 驻点位于$g(\boldsymbol{x}) > 0$的区域中,称限制条件无效(inactive),此时函数$g(\boldsymbol{x})$不起作用,但拉格朗日方程仍然成立,此时$\lambda = 0$。
  2. 驻点位于$g(\boldsymbol{x}) = 0$的边界上,称限制条件有效(active),这类似于等式限制的情形,$g(\boldsymbol{x}) = 0$。但由于最优解取在边界上,因此梯度$\nabla f$(函数$f$在点$\boldsymbol{x}$的最陡上升方向)应该指向可行域$g(\boldsymbol{x}) > 0$的外部,但$\nabla g$必然指向可行域$g(\boldsymbol{x}) > 0$的内部,考虑到$\nabla f+\lambda \nabla g=0$,必然有$\lambda > 0$。

将以上两种情况综合起来,可以得到Karush-Kuhn-Tucker(KKT)条件:

$$ \begin{aligned} g(\boldsymbol{x}) & \ge 0 \\ \lambda & \ge 0 \\ \lambda g(\boldsymbol{x}) &= 0 \end{aligned} $$

如果想在不等式限制$g(\boldsymbol{x}) \ge 0$下最小化函数$f(\boldsymbol{x})$,那么需要关于$\boldsymbol{x}$最小化拉格朗日函数$L(\boldsymbol{x}, \lambda) = f(\boldsymbol{x})-\lambda g(\boldsymbol{x})$,限制条件为$\lambda \ge 0$。

多个等式和不等式限制

令限制条件为

$$ g_{j}(\boldsymbol{x})=0, \, j=1, \ldots, J \\ h_{k}(\boldsymbol{x}) \geq 0, \, k=1, \ldots, K $$

引入拉格朗日乘数${\lambda_j}$和${\mu_k}$,最优化下列拉格朗日函数:

$$ L(\boldsymbol{x},\left\{\lambda_{j}\right\},\left\{\mu_{k}\right\})=f(\boldsymbol{x})+\sum_{j=1}^{J} \lambda_{j} g_{j}(\boldsymbol{x})+\sum_{k=1}^{K} \mu_{k} h_{k}(\boldsymbol{x}) $$

限制条件为

$$ \mu_k \ge 0 \\ \mu_k h_{k}(\boldsymbol{x}) = 0, \, k = 1, \ldots, K $$

 评论