机器学习：笔记整理

本文为 SJTU-CS3612 机器学习课程的笔记整理，主要聚焦于公式及其推导过程。

Lecture 1: Linear Model

1.1 Linear regression

假设有 $n$ 个样本的数据集 $\{x_{i1}, x_{i2}, \dots, x_{ip}, y_i\}_{i=1}^n$，则线性模型可以表示为：

$$y_i = \beta_0 1+\beta_1 x_{i 1}+\beta_2 x_{i 2} +\cdots+\beta_p x_{i p}+\varepsilon_i =\sum_{j=0}^p x_{i j} \beta_j+\varepsilon_i$$

或者表示为矩阵形式：

$$\mathbf{y}=\mathbf{X}^{\top} \boldsymbol{\beta}+\boldsymbol{\varepsilon}$$

其中

$$\mathbf{X}^\top =\begin{bmatrix} \mathbf{x}_1^{\top} \\ \mathbf{x}_2^{\top} \\ \vdots \\ \mathbf{x}_n^{\top} \end{bmatrix}=\begin{bmatrix} 1 & x_{11} & \cdots & x_{1 p} \\ 1 & x_{21} & \cdots & x_{2 p} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n 1} & \cdots & x_{n p} \end{bmatrix}, \quad \mathbf{y}=\begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}, \quad \boldsymbol{\beta}=\begin{bmatrix} \beta_0 \\ \beta_1 \\ \vdots \\ \beta_p \end{bmatrix}, \quad \boldsymbol{\varepsilon}=\begin{bmatrix} \varepsilon_1 \\ \varepsilon_2 \\ \vdots \\ \varepsilon_n \end{bmatrix}$$

1.2 Logistic regression

假设有 $n$ 个样本的数据集 $\{(X_i, y_i)\}_{i=1}^n$，其中标签 $y_i \in \{0, 1\}$. 设模型对样本 $X_i$ 的预测概率

$$\operatorname{Pr}(y_i = 1|X_i) = p_i, \quad \operatorname{Pr}(y_i = 0|X_i) = 1 - p_i$$

Logistic regression 的分类公式是：

$$\operatorname{logit}\left(p_i\right)=\log \frac{p_i}{1-p_i}=X_i^{\top} \beta$$

从而

$$p_i=\operatorname{s igmoid}\left(X_i^{\top} \beta\right)=\frac{e^{X_i^{\top} \beta}}{1+e^{X_i^{\top} \beta}}=\frac{1}{1+e^{-X_i^{\top} \beta}}$$

设每个样本的真实标签为 $y_i^*$，那么预测正确的概率为

$$\operatorname{Pr}\left(y_i=y_i^* | X_i\right)=p_i^{y_i^*}\left(1-p_i\right)^{1-y_i^*}=\left(\frac{e^{X_i^{\top} \beta}}{1+e^{X_i^{\top} \beta}}\right)^{y_i^*}\left(1-\frac{e^{X_i^{\top} \beta}}{1+e^{X_i^{\top} \beta}}\right)^{1-y_i^*}=\frac{e^{y_i^* X_i^{\top} \beta}}{1+e^{X_i^{\top} \beta}}$$

采用最大似然估计(MLE)，目标是所有样本全部预测正确的概率最大，即

$$\operatorname{Pr}(\beta)=\prod_{i=1}^n p_i^{y_i^*}\left(1-p_i\right)^{1-y_i^*}=\prod_{i=1}^n \frac{e^{y_i^* X_i^{\top} \beta}}{1+e^{X_i^{\top} \beta}}$$

取对数，得

$$\log \operatorname{Pr}(\beta)=\sum_{i=1}^n\left[y_i^* X_i^{\top} \beta-\log \left(1+\exp X_i^{\top} \beta\right)\right]$$

即优化目标变为

$$\argmax_\beta \operatorname{Pr}(\beta) \equiv \argmax_\beta \log \operatorname{Pr}(\beta)$$

1.3 Classification

如果分类标签 $y_i \in \{+1, -1\}$，那么 logistic regression 变为：

$$\operatorname{Pr}(y_i = +1|X_i) = \frac{1}{1+e^{-X_i^{\top} \beta}}, \quad \operatorname{Pr}(y_i = -1|X_i) = \frac{1}{1+e^{X_i^{\top} \beta}}$$

合并起来，得到

$$p\left(y_i\right)=\frac{1}{1+e^{-y_iX_i^{\top} \beta}}$$

1.4 Perceptron

一个基础的感知机，可以表示为：

$$y_i=\operatorname{sign}\left(X_i^{\top} \beta\right)$$

其中 $\operatorname{sign}(\cdot)$ 是符号函数.

1.5 Three models

Generative models

给定观测变量 $X$ 和目标变量 $Y$，生成式模型建模联合概率 $p_\theta(X, Y)$。用生成式模型做分类时，使用条件概率公式：

$$p_\theta(Y | X)=\frac{p_\theta(X, Y)}{p_\theta(X)}=\frac{p_\theta(X, Y)}{\sum_{Y^{\prime}} p_\theta\left(X, Y^{\prime}\right)}$$

假设 $g_\theta$ 是一个生成式网络，给定输入

$$h \sim \mathrm{N}(0, I)$$

期望的输出为：

$$X = g_\theta(h) + \varepsilon$$

输出 $X$ 的概率为：

$$p_\theta(X)=\int p(h) p_\theta(X | h) \mathrm{d} h$$

要增大 $\log p_\theta(X)$，就是要增大 $\log p(h)$ 和 $\log p_\theta(X | h)$.

1. $\log p(h)$：由于 $h \sim N(0, I)$，即

   $$p(h) = \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}\| h \|^2\right)$$

   从而

   $$\log p(h)=-\frac{1}{2}\|h\|^2+\mathrm{constant}$$

2. $\log p_\theta(X | h)$：假设

   $$X-g_\theta(h)=\varepsilon \sim \mathrm{N}\left(0, \sigma^2 \mathbf{I}\right)$$

   那么

   $$X | h \sim \mathrm{N}\left(g_\theta(h), \sigma^2 \mathbf{I}\right)$$

   从而

   $$\log p_\theta(X | h)=-\frac{\left\|X-g_\theta(h)\right\|^2}{2 \sigma^2}+\mathrm{constant}$$

Discriminative models

给定观测变量 $X$ 和目标变量 $Y$，判别式模型建模条件概率 $p_\theta(Y|X)$. 设输入为 $X$，网络的输出为 $K$ 维向量 $f_\theta(X)$. 最后经过 Softmax 层，得到分类为每一类的概率：

$$p_\theta(y=k | X)= p_k = \frac{1}{Z(\theta)} \exp (f_\theta^{(k)}(X))$$

其中

$$Z(\theta) = \sum_k \exp (f_\theta^{(k)}(X))$$

Descriptive models

描述式模型建模输入数据分布 $p_\theta(X)$. 可以表示为：

$$p_\theta(X)=\frac{1}{Z(\theta)} \exp(f_\theta(X))$$

其中

$$Z(\theta) = \int \exp (f_\theta(x)) \mathrm{d} x$$

1.7 Loss functions

为了从数据集 $\left\{\left(X_i, y_i\right)\right\}_{i=1}^n$ 中学习 $\beta$，我们最小化损失函数

$$\mathscr{L}(\beta)=\sum_{i=1}^n L\left(y_i, X_i^{\top} \beta\right)$$

其中 $L\left(y_i, X_i^{\top} \beta\right)$ 是对每个训练样本的损失.

Loss function for least squares regression

在线性回归中，我们常使用最小平方损失：

$$L(y_i, X_i^{\top} \beta)=\left(y_i-X_i^{\top} \beta\right)^2$$

这一损失函数同样可以从最大似然估计中得到. 先假设误差服从正态 分布，即

$$y_i-X_i^{\top} \beta=\varepsilon_i \sim \mathrm{N}(0,\sigma^2I)$$

那么有

$$y_i|X_i \sim \mathrm{N}(X_i^\top \beta, \sigma^2I)$$

即

$$\mathrm{Pr}(y_i|X_i, \beta) = \frac{1}{\sqrt{2\pi} \sigma} \exp\left[-\frac{(y_i - X_i^\top \beta)^2}{2\sigma^2}\right]$$

取负对数似然为损失函数，有：

$$L(y_i, X_i^{\top} \beta)= -\log \operatorname{Pr}(y_i |X_i, \beta) = \frac{(y_i-X_i^{\top} \beta)^2}{2\sigma^2}+\mathrm{constant}$$

从而

$$\mathscr{L}(\beta)=\sum_{i=1}^n L(y_i, X_i^{\top} \beta)=2\sigma^2 \sum_{i=1}^n\left[\frac{(y_i-X_i^{\top} \beta)^2}{2\sigma^2}+\mathrm{constant}\right]=\sum_{i=1}^n(y_i-X_i^{\top} \beta)^2$$

因此，最小二乘法的本质是最大似然估计.

Loss function for robust linear regression

考虑到最小平方损失对 outliers 较为敏感，可以将损失函数中的平方换为绝对值，即：

$$L(y_i, X_i^{\top} \beta)=| y_i-X_i^{\top} \beta |$$

将两种损失结合，得到 Huber loss：

$$L(y_i, X_i^{\top} \beta)= \begin{cases}\frac{1}{2}(y_i-X_i^{\top} \beta)^2, & \text { if }|y_i-X_i^{\top} \beta| \leq \delta \\ \delta|y_i-X_i^{\top} \beta|-\frac{\delta^2}{2}, & \text { otherwise }\end{cases}$$

其中 $\delta$ 是选取的截断值，在 $\delta$ 之外采用绝对值损失.

Loss function for logistic regression with 0/1 responses

前面推导过，当标签 $y_i \in \{0, 1\}$ 时，

$$\operatorname{Pr}\left(y_i | X_i, \beta\right) =\frac{\exp (y_i X_i^\top \beta)}{1+\exp (X_i^{\top} \beta)}$$

为了最大化这一概率，取负对数似然为损失函数：

$$L(y_i, X_i^{\top} \beta)= -\log \operatorname{Pr}(y_i |X_i, \beta) = -\left[y_i X_i^{\top} \beta-\log (1+\exp (X_i^{\top} \beta))\right]$$

Loss function for logistic regression with $\pm$ responses

前面推导过，当标签 $y_i \in \{+1, -1\}$ 时，

$$\operatorname{Pr}\left(y_i | X_i, \beta\right) =\frac{1}{1+\exp (-y_i X_i^{\top} \beta)}$$

同样取负对数似然为损失函数，有：

$$L(y_i, X_i^{\top} \beta)= -\log \operatorname{Pr}(y_i |X_i, \beta) = \log \left[1+\exp \left(-y_i X_i^{\top} \beta\right)\right]$$

该损失被称为 logistic loss.

Loss functions for classification

对于 $y_i \in \{+1, -1\}$ 的分类问题，除了 logistic loss，还有其他的损失函数可以选择：

$$\begin{aligned} & \text { Logistic loss }=\log \left(1+\exp \left(-y_i X_i^{\top} \beta\right)\right), \\ & \text { Exponential loss }=\exp \left(-y_i X_i^{\top} \beta\right), \\ & \text { Hinge loss }=\max \left(0,1-y_i X_i^{\top} \beta\right), \\ & \text { Zero-one loss }=1\left(y_i X_i^{\top} \beta<0\right) \end{aligned}$$

图中横轴表示 $m_i = y_iX_i^\top\beta$（称为 margin），纵轴表示 $L(y_i, X_i^\top\beta)$. 当 $y_i$ 和 $X_i^\top\beta$ 同号时，表明分类正确，所以当 $y_i = +1$ 时，我们希望 $X_i^\top\beta$ 是越正越好；当 $y_i = -1$ 时，我们希望 $X_i^\top\beta$ 是越负越好. 也就是说，我们希望 $m_i = y_iX_i^\top\beta$ 越大越好，即 $m_i$ 越小，损失函数越大.

1.8 Least Squares

考虑线性模型 $Y = X\beta + \varepsilon$，优化目标是：

$$\hat{\beta}=\argmin_\beta L(\beta) = \argmin_\beta\Vert Y-X \beta\Vert^2$$

考虑到 $L(\beta)$ 为凸函数，在 $\beta = \hat{\beta}$ 处有一阶条件：

$$\frac{\partial}{\partial \beta} L(\beta) = 0$$

下面对 $L(\beta)$ 求导. 展开得：

$$\begin{aligned} L(\beta) & = (Y - X\beta)^\top(Y - X\beta) \\ & = Y^{\top} Y-Y^{\top} X \beta-\beta^{\top} X^{\top} Y+\beta^{\top} X^{\top} X \beta \\ \end{aligned}$$

考虑到 $\beta^{\top} X^{\top} Y$ 是标量，有 $\beta^{\top} X^{\top} Y=Y^{\top} X \beta$，从而

$$L(\beta) = Y^{\top} Y-2 Y^{\top} X \beta+\beta^{\top} X^{\top} X \beta$$

▶

矩阵求导复习

假设 $A$ 是对称矩阵，那么有：

$$\frac{\partial}{\partial \beta}\left(\beta^{\top} A \beta\right)=2 A \beta$$

$$\frac{\partial}{\partial \beta}\left(b^{\top} \beta\right)=b$$

根据矩阵求导法则，有：

$$\frac{\partial L}{\partial \beta}=-2 X^{\top} Y+2 X^{\top} X \beta$$

令 $\dfrac{\partial L}{\partial \beta} = 0$，得：

$$\begin{equation} 2 X^\top(Y-X \beta)=0 \end{equation}$$

如果 $X$ 列满秩，那么 $X^\top X$ 可逆，解得：

$$\hat{\beta}=\left(X^\top X\right)^{-1} X^\top Y$$

因此，

$$\hat{Y}=X \hat{\beta}=X\left(X^\top X\right)^{-1} X^\top Y$$

可以看出，最小二乘法的实质是将 $Y$ 投影到 $X$ 的列空间上，其投影为 $X\hat{\beta}$；而误差 $\varepsilon = Y - X\beta$ 和列空间正交，这可以从 (1) 式中看出。

Distribution of $\hat{\beta}$

下面讨论训练得到的参数 $\hat{\beta}$ 的稳定性. 设用无穷个样本得到的参数为 $\beta_\text{true}$，那么我们有：

$$\begin{aligned} \hat{\beta} & =(X^\top X)^{-1} X^\top Y \\ & =(X^\top X)^{-1} X^\top(X \beta_{\text {true}}+\varepsilon) \\ & =\beta_{\text {true}}+(X^\top X)^{-1} X^\top \varepsilon \end{aligned}$$

可以看出，$\hat{\beta}$ 服从正态分布，其均值为：

$$\mathbb{E}[\hat{\beta}]=\beta_{\text {true}}$$

协方差矩阵为：

$$\begin{aligned} \mathrm{Var}(\hat{\beta}) & = \mathbb{E}\left[(\hat{\beta} - \mathbb{E}[\hat{\beta}])(\hat{\beta} - \mathbb{E}[\hat{\beta}])^\top\right] \\ & = \mathbb{E}\left[((X^\top X)^{-1} X^\top \varepsilon )((X^\top X)^{-1} X^\top \varepsilon)^\top\right] \\ & = (X^\top X)^{-1} X^\top \mathbb{E}[\varepsilon \varepsilon^\top] X (X^\top X)^{-1, \top} \\ & = (X^\top X)^{-1} X^\top \cdot \sigma^2 I \cdot X (X^\top X)^{-1} \\ & = \sigma^2 (X^\top X)^{-1} \end{aligned}$$

因此，

$$\hat{\beta} \sim N\left(\beta_\text{true}, \sigma^2 (X^\top X)^{-1}\right)$$

1.9 Kullback-Leibler divergence and cross entropy

Coding and entropy

一个分布 $p(x)$ 的不确定性用熵来衡量：

$$H(p)=\mathbb{E}_p[-\log p(X)]=\sum_x p(x)[-\log p(x)]$$

熵等于用 $-\log p(x)$ 长度来编码达到的最短编码长度.

Kullback-Leibler divergence and cross entropy

交叉熵，是对于分布 $p(x)$，使用另一个分布 $q(x)$ 的 $-\log q(x)$ 长度进行编码，所得到的编码长度，即：

$$\mathrm{CE}(p | q) = \mathbb{E}_p[-\log q(X)]=-\sum_x p(x) \log q(x)$$

不难得到，交叉熵不小于熵，即：

$$\mathrm{CE}(p | q) \ge H(p)$$

当且仅当 $p(x) = q(x)$，即两个分布相等时，等号成立.

定义 KL 散度为交叉熵和熵的差，即：

$$\mathrm{KL}(p | q) = \mathrm{CE}(p | q) - H(p) = \mathbb{E}_p\left[\log \frac{p(X)}{q(X)}\right] = \sum_x p(x) \log \frac{p(x)}{q(x)} \ge 0$$

当且仅当 $p(x) = q(x)$时，等号成立. 一般来说，$p(x)$ 表示真实分布，$q(x)$ 表示模型输出的预测分布. KL 散度衡量了两个分布之间的距离，但是 KL 散度不对称，即：

$$\operatorname{KL}(p | q) \neq \operatorname{KL}(q | p)$$

对于条件概率分布，KL 散度的定义是：

$$\operatorname{KL}(p(y | x) | q(y | x)) \stackrel{\text { def }}{=} \mathbb{E}_{p(x, y)}\left[\log \frac{p(Y | X)}{q(Y | X)}\right] = \mathbb{E}_{p(x)} \mathbb{E}_{p(y | x)}\left[\log \frac{p(Y | X)}{q(Y | X)}\right]$$

对于多变量分布，KL 散度为：

$$\begin{equation} \operatorname{KL}(p(x, y) | q(x, y))=\operatorname{KL}(p(x) | q(x))+\operatorname{KL}(p(y | x) | q(y | x)) \end{equation}$$

1.10 Maximum likelihood

下面证明最大似然估计的正确性. 优化目标是：

$$\mathscr{L}(\theta)=\frac{1}{n} \sum_{i=1}^n \log p_\theta(y_i | X_i)$$

设 $P_\text{data}(X, y)$ 是样本分布，则有：

$$\begin{aligned} \max_\theta \mathscr{L}(\theta) & = \max _\theta \frac{1}{n} \sum_{i=1}^n \log p_\theta(y_i | X_i) \\ & = \max _\theta \mathbb{E}_{P_{\text {data}}}\left[\log p_\theta(y | X)\right] \\ & = \min _\theta\left\{-\mathbb{E}_{P_{\text {data}}}\left[\log p_\theta(y | X)\right]\right\} \\ \end{aligned}$$

由于 $\mathbb{E}_{P_{\text {data}}}\left[\log P_{\text {data}}(y | X)\right]$ 是与 $\theta$ 无关的常数，

$$\begin{aligned} \max_\theta \mathscr{L}(\theta) & = \min _\theta \mathbb{E}_{P_{\text {data }}}\left[\log P_{\text {data}}(y | X)\right]-\mathbb{E}_{P_{\text {data}}}\left[\log p_\theta(y | X)\right] \\ & = \min _\theta \mathrm{KL}\left(P_{\text {data}}(y | X) | p_\theta(y | X)\right) \end{aligned}$$

可以看出，最大似然估计的实质是：最小化预测分布和真实数据分布的 KL 散度，即让预测分布尽可能接近真实数据分布.

1.11 Kullback-Leibler of conditionals

下面证明多变量分布的 KL 散度公式，即式 (2).

$$\begin{aligned} \mathrm{KL}(p(x, y) | q(x, y)) & =\mathbb{E}_p\left[\log \frac{p(x, y)}{q(x, y)}\right] \\ & =\mathbb{E}_p\left[\log \frac{p(x) p(y | x)}{q(x) q(y | x)}\right] \\ & =\mathbb{E}_p\left[\log \frac{p(x)}{q(x)}\right]+\mathbb{E}_p\left[\log \frac{p(y | x)}{q(y | x)}\right] \\ & =\mathrm{KL}(p(x) | q(x))+\mathrm{KL}(p(y | x) | q(y | x)) \end{aligned}$$

1.13 Gradient of log-likelihood

Discriminative model

前面提到过，判别式模型的输出为：

$$p_\theta(y=k | X)=p_k=\frac{1}{Z(\theta)} \exp (f_\theta^{(k)}(X))$$

其中

$$Z(\theta)=\sum_k \exp (f_\theta^{(k)}(X))$$

对对数概率求梯度，有：

$$\begin{aligned} \frac{\partial}{\partial \theta} \log p_\theta(y | X) & =\frac{\partial}{\partial \theta} f_\theta^{(k)}(X)-\frac{\partial}{\partial \theta} \log Z(\theta) \\ & =\frac{\partial}{\partial \theta} f_\theta^{(k)}(X)-\frac{1}{Z(\theta)} \frac{\partial}{\partial \theta} Z(\theta) \\ & =\frac{\partial}{\partial \theta} f_\theta^{(k)}(X)-\frac{1}{Z(\theta)} \frac{\partial}{\partial \theta}\left[\sum_{k^{\prime}} \exp (f_\theta^{(k^{\prime})}(X))\right] \\ & =\frac{\partial}{\partial \theta} f_\theta^{(k)}(X)-\left[\sum_{k^{\prime}} \frac{\exp (f_\theta^{(k^{\prime})}(X))}{Z(\theta)} \frac{\partial}{\partial \theta} f_\theta^{(k^{\prime})}(X)\right] \\ & =\frac{\partial}{\partial \theta} f_\theta^{(k)}(X)-\left[\sum_{k^{\prime}} p_{k^{\prime}} \frac{\partial}{\partial \theta} f_\theta^{(k^{\prime})}(X)\right] \\ & =\sum_{k^{\prime}}\left(1(y=k^{\prime})-p_{k^{\prime}}\right) \frac{\partial}{\partial \theta} f_\theta^{(k^{\prime})}(X) \\ & =\frac{\partial}{\partial \theta} f_\theta(X)^{\top}(Y-p) \\ & =\frac{\partial}{\partial \theta} f_\theta(X)^{\top}\left(Y-\mathbb{E}_\theta(Y | X)\right) \end{aligned}$$

其中 $Y$ 是 $y$ 的独热形式，即：

$$Y=\left[Y_1, Y_2, \ldots, Y_n\right], \quad Y_{k^{\prime}}=\left\{\begin{array}{cc} 1, & k^{\prime}=k \\ 0, & k^{\prime} \neq k \end{array}\right.$$

由此可见，判别式模型从误差中学习(learn from errors).

Descriptive model

前面提到，描述式模型建模数据分布，即：

$$p_\theta(X)=\frac{1}{Z(\theta)} \exp (f_\theta(X))$$

其中

$$Z(\theta)=\int \exp (f_\theta(x)) \mathrm{d} x$$

对对数概率求导，有：

$$\begin{aligned} \frac{\partial}{\partial \theta} \log p_\theta(X) & =\frac{\partial}{\partial \theta} f_\theta(X)-\frac{\partial}{\partial \theta} \log Z(\theta) \\ & =\frac{\partial}{\partial \theta} f_\theta(X)-\frac{1}{Z(\theta)} \frac{\partial}{\partial \theta} Z(\theta) \\ & =\frac{\partial}{\partial \theta} f_\theta(X)-\frac{1}{Z(\theta)} \int \exp (f_\theta(X)) \frac{\partial}{\partial \theta} f_\theta(X) \mathrm{d} x \\ & =\frac{\partial}{\partial \theta} f_\theta(X)-\int \frac{1}{Z(\theta)} \exp \left(f_\theta(X)\right) \frac{\partial}{\partial \theta} f_\theta(X) \mathrm{d} x \\ & =\frac{\partial}{\partial \theta} f_\theta(X)-\sum_X p_\theta(X) \frac{\partial}{\partial \theta} f_\theta(X) \\ & =\frac{\partial}{\partial \theta} f_\theta(X)-\mathbb{E}_\theta\left[\frac{\partial}{\partial \theta} f_\theta(X)\right] \end{aligned}$$

Generative model

对于生成式模型 $p_\theta(h, X)$，有：

$$\begin{aligned} \frac{\partial}{\partial \theta} \log p_\theta(X) & =\frac{1}{p_\theta(X)} \frac{\partial}{\partial \theta} \int p_\theta(h, X) \mathrm{d} h \\ & =\frac{1}{p_\theta(X)} \int\left[\frac{\partial}{\partial \theta} p_\theta(h, X)\right] \mathrm{d} h \\ & =\frac{1}{p_\theta(X)} \int\left[\frac{\partial}{\partial \theta} \log p_\theta(h, X)\right] p_\theta(h, X) \mathrm{d} h \\ & =\int\left[\frac{\partial}{\partial \theta} \log p_\theta(h, X)\right] \frac{p_\theta(h, X)}{p_\theta(X)} \mathrm{d} h \\ & =\int\left[\frac{\partial}{\partial \theta} \log p_\theta(h, X)\right] p_\theta(h | X) \mathrm{d} h \\ & =\mathbb{E}_{p_\theta(h | X)}\left[\frac{\partial}{\partial \theta} \log p_\theta(h, X)\right] \end{aligned}$$

其中

$$p_\theta(h, X) = p(h) \cdot p_\theta(X | h) = \mathrm{N}(h | \mathbf{0}, \mathbf{I}) \cdot \mathrm{N}\left(X | g_\theta(h), \sigma^2 \mathbf{I}\right)$$

$$\log p_\theta\left(h, X\right)=-\frac{1}{2 \sigma^2}\left\|X-g_\theta\left(h\right)\right\|^2-\frac{1}{2}\left\|h\right\|^2+\mathrm{constant}$$

Optimizing logistic regression via gradient ascent

在 logistic regression 中，对数似然函数是：

$$l(\beta)=\log L(\beta)=\sum_{i=1}^n\left[y_i X_i^{\top} \beta-\log \left(1+\exp X_i^{\top} \beta\right)\right]$$

为了最大化 $l(\beta)$，计算梯度：

$$l^{\prime}(\beta)=\sum_{i=1}^n\left[y_i X_i-\frac{e^{X_i^{\top} \beta}}{1+e^{X_i^{\top} \beta}} X_i\right]=\sum_{i=1}^n\left(y_i-p_i\right) X_i$$

其中

$$p_i=\frac{e^{X_i^{\top} \beta}}{1+e^{X_i^{\top} \beta}}=\frac{1}{1+e^{-X_i^{\top} \beta}}$$

我们用这个梯度更新 $\beta$ 以最大化 $l(\beta)$：

$$\beta^{(t+1)}=\beta^{(t)}+\gamma_t \sum_{i=1}^n\left(y_i-p_i\right) X_i$$

可以看出，该算法从错误 $y_i - p_i$ 中学习.

1.14 Langevin

在梯度下降算法中，加入随机噪声扰动，有利于跳出局部最优解，这就是 Langevin 动力学.

Brownian motion, $\sqrt{\Delta t}$ notation, second order Taylor expansion

设 $X_t$ 是 $t$ 时刻粒子的位置，对应线性模型中的参数 $\beta$. 在布朗运动中，我们有：

$$X_{t+\Delta t}=X_t+\sigma \varepsilon_t \sqrt{\Delta t}$$

其中 $\varepsilon_t \sim N(0, 1)$. 设初始位置 $X_0 = x$，并将时间 $[0, t]$ 平均分成 $n$ 段，即 $\Delta t = t / n$，那么有：

$$X_t=x+\sum_{i=1}^n \sigma \varepsilon_i \sqrt{\frac{t}{n}}=x+\sigma \sqrt{t} \frac{1}{\sqrt{n}} \sum_{i=1}^n \varepsilon_i \sim \mathrm{~N}\left(x, \sigma^2 t \mathbf{I}\right)$$

Langevin: energy and entropy

对于描述式模型，我们采样 $p_\theta(X)$ 可以用：

$$X^{(t+1)} = X^{(t)} + \eta \cdot \frac{\partial}{\partial X} f_\theta(X) + \lambda \varepsilon$$

对于生成式模型，我们采样从 $p_\theta(h_i | X_i)$ 中采样 $h_i$ 可以用：

$$h^{(t+1)} = h^{(t)} + \eta \cdot \frac{\partial}{\partial h} p_\theta(h, X_i) + \lambda \varepsilon$$

1.17 Linear Discriminant Analysis (LDA)

LDA 的目标是学习一个线性分类器，将 $X_i$ 投影到 $z = X_i^\top \beta$，使得类间方差最大化、类内方差最小化.

设所有样本为 $\Omega$，其中正类样本为 $\Omega^+$，负类样本为 $\Omega^-$，且：

• $\forall X_i \in \Omega^{+}, p\left(X_i | y=+1\right) \sim \mathrm{N}\left(\mu^{+}, \Sigma^{+}\right)$
• $\forall X_i \in \Omega^{-}, p\left(X_i | y=-1\right) \sim \mathrm{N}\left(\mu^{-}, \Sigma^{-}\right)$

那么类间方差为：

$$\begin{aligned} \sigma_{\text {between }}^2 & =\left(\mathbb{E}_{i \in \Omega^{+}}[X_i^{\top} \beta]-\mathbb{E}_{i \in \Omega^{-}}[X_i^{\top} \beta]\right)^2 \\ & =\left(\mathbb{E}_{i \in \Omega^{+}}[X_i^{\top}] \beta-\mathbb{E}_{i \in \Omega^{-}}[X_i^{\top}] \beta\right)^2 \\ & =((\mu^{+})^{\top} \beta-(\mu^{-})^{\top} \beta)^2 \\ & =\left[(\mu^{+}-\mu^{-})^{\top} \beta\right]^2 \end{aligned}$$

类内方差为：

$$\begin{aligned} \sigma_{\text {within }}^2 & =n_{\text {pos }} \sigma_{\text {pos }}^2+n_{\text {neg }} \sigma_{\text {neg }}^2, \quad n_{\text {pos }}=\left|\Omega^{+}\right|, n_{\text {neg }}=\left|\Omega^{-}\right| \\ \sigma_{\text {pos }}^2 & =\mathbb{E}_{i \in \Omega^{+}}\left[\left(X_i^{\top} \beta-\mathbb{E}_{i^{\prime} \in \Omega^{+}}[X_{i^{\prime}}^{\top} \beta]\right)^2\right] \\ & =\mathbb{E}_{i \in \Omega^{+}}\left[\left(\beta^{\top} X_i-\mathbb{E}_{i^{\prime} \in \Omega^{+}}[\beta^{\top} X_{i^{\prime}}]\right)\left(X_i^{\top} \beta-\mathbb{E}_{i^{\prime} \in \Omega^{+}}[X_{i^{\prime}}^{\top} \beta]\right)\right] \\ & =\mathbb{E}_{i \in \Omega^{+}}\left[\beta^{\top}\left(X_i-\mathbb{E}_{i^{\prime} \in \Omega^{+}}[X_{i^{\prime}}]\right)\left(X_i^{\top}-\mathbb{E}_{i^{\prime} \in \Omega^{+}}[X_{i^{\prime}}^{\top}]\right) \beta\right] \\ & =\beta^{\top} \mathbb{E}_{i \in \Omega^{+}}\left[\left(X_i-\mathbb{E}_{i^{\prime} \in \Omega^{+}}[X_{i^{\prime}}]\right)\left(X_i^{\top}-\mathbb{E}_{i^{\prime} \in \Omega^{+}}[X_{i^{\prime}}^{\top}\right]\right)] \beta \\ & =\beta^{\top} \Sigma^{+} \beta \\ \sigma_{\text {neg }}^2 & =\beta^{\top} \Sigma^{-} \beta \end{aligned}$$

从而优化目标是最大化

$$\begin{aligned} S & =\frac{\sigma_{\text {between }}^2}{\sigma_{\text {within }}^2} \\ & =\frac{[(\mu^{+}-\mu^{-})^{\top} \beta]^2}{n_{\mathrm{pos}} \beta^{\top} \Sigma^{+} \beta+n_{\mathrm{neg}} \beta^{\top} \Sigma^{-} \beta} \\ & =\frac{(\beta^{\top}(\mu^{+}-\mu^{-}))((\mu^{+}-\mu^{-})^{\top} \beta)}{\beta^{\top}(n_{\mathrm{pos}} \Sigma^{+}+n_{\mathrm{neg}} \Sigma^{-}) \beta} \\ & =\frac{\beta^{\top} S_B \beta}{\beta^{\top} S_W \beta} \end{aligned}$$

其中

$$\begin{aligned} S_B & =(\mu^{+}-\mu^{-})(\mu^{+}-\mu^{-})^{\top} \\ S_W & =n_{\mathrm{pos}} \Sigma^{+}+n_{\mathrm{neg}} \Sigma^{-} \end{aligned}$$

由于我们只关心 $\beta$ 的方向，不妨设 $\beta^\top S_W \beta = 1$，从而目标变为：

$$\max _\beta \beta^{\top} S_B \beta, \quad \text { s.t. } \quad \beta^{\top} S_W \beta=1$$

使用 Lagrange 乘子法：

$$\begin{aligned} & L=-\beta^{\top} S_B \beta+\lambda(\beta^{\top} S_W \beta-1) \\ \Rightarrow \quad & \frac{\partial L}{\partial \beta}=-2 S_B \beta+2 \lambda S_W \beta=0 \\ \Rightarrow \quad & S_B \beta=\lambda S_W \beta \\ \Rightarrow \quad & S_W^{-1} S_B \beta=\lambda \beta \end{aligned}$$

由此看出，$\beta$ 是 $S_W^{-1} S_B$ 的特征向量. 代入 $S_B$，可以解出：

$$\beta \propto S_W^{-1}(\mu^{+}-\mu^{-})$$

Lecture 2: Support Vector Machines

2.1 Margin and support vectors

考虑分类问题 $y_i \in\{-1,+1\}$，使用分类器

$$\hat{y}=\operatorname{sign}(w^{\top} x+b)= \begin{cases}+1, & w^{\top} x+b \geq 0 \\ -1, & w^{\top} x+b<0\end{cases}$$

定义 margin：

$$\gamma_i=y_i(w^{\top} x_i+b)$$

$\gamma_i$ 表示了分类质量，当 $\gamma_i > 0$ 时分类正确，且越大意味着越自信. 因此，目标函数可以表示为：

$$\max_{w, b}\min_{i=1, \dots, n} \gamma_i$$

但是，考虑到 $\gamma_i$ 随 $w$ 和 $b$ 的增大而增大，我们约束 $\Vert w \Vert = 1$，即 margin 的定义变为：

$$\gamma_i=\frac{y_i(w^{\top} X_i+b)}{\|w\|}= y_i\left[\left(\frac{w}{\|w\|}\right)^{\top} X_i+\frac{b}{\|w\|}\right]$$

事实上，在分类正确的情况下，$\gamma_i$ 等于 $X_i$ 到 $w^\top x+b = 0$ 的距离. 可以验证，将 $X_i$ 向分类面推动 $\gamma_i$ 距离得到的点 $X_i-\gamma_i \dfrac{w}{\|w\|} y_i$ 恰好在分类面上，即：

$$w^{\top}\left(X_i-\gamma_i \frac{w}{\|w\|} y_i\right)+b=\left(w^{\top} X_i+b\right)-y_i^2 \frac{w^{\top}\left(w^{\top} X_i+b\right) w}{\|w\|^2}=\left(w^{\top} X_i+b\right)-\left(w^{\top} X_i+b\right)=0$$

2.2 Margin classifier

假设所有样本都能分类正确. 为了最大化 margin，优化目标是：

$$\begin{aligned} & \max _{\tau, w, b} \, \tau \\ \text { s.t. } \quad & \forall i, y_i(w^{\top} X_i+b) \geq \tau \\ & \|w\|=1 \end{aligned}$$

为了简化计算，将目标重写为：

$$\begin{aligned} & \max _{\tau, w, b} \frac{\tau}{\|w\|} \\ \text { s.t. } \quad & \forall i, y_i\left(w^{\top} X_i+b\right) \geq \tau \end{aligned}$$

这时，由于我们可以缩放 $w$ 和 $b$ 而不改变超平面，不妨固定 $\tau = 1$，得到的优化目标等价为：

$$\begin{aligned} & \min _{w, b} \frac{1}{2}\|w\|^2 \\ \text { s.t. } \quad & \forall i, y_i\left(w^{\top} X_i+b\right) \geq 1 \end{aligned}$$

Lagrange multipliers

考虑带等式约束的优化问题：

$$\begin{aligned} & \min _w f(w) \\ \text { s.t. } \quad & h_k(w)=0, k=1,2, \ldots, K \end{aligned}$$

我们可以最小化

$$L(w, \lambda)=f(w)+\sum_{k=1}^K \lambda_k h_k(w)$$

从而要求

$$\frac{\partial L}{\partial w}=0, \quad \forall k, \frac{\partial L}{\partial \lambda_k}=0$$

加入不等式约束，即考虑一般的优化问题：

$$\begin{aligned} & \min _w f(w) \\ \text { s.t. } \quad & g_k(w) \leq 0, k=1,2, \ldots, K \\ & h_l(w)=0, l=1,2, \ldots, L \end{aligned}$$

令

$$L(w, \alpha, \beta)=f(w)+\sum_{k=1}^K \alpha_k g_k(w)+\sum_{l=1}^L \beta_l h_l(w)$$

当满足

$$\min _w \max _{\alpha, \beta: \alpha_k \geq 0} L(w, \alpha, \beta)=\max _{\alpha, \beta: \alpha_k \geq 0} \min _w L(w, \alpha, \beta)$$

时，有 KKT 条件：

$$\begin{aligned} \forall p, \quad \frac{\partial}{\partial w_p} L(w, \alpha, \beta) & =0 \\ \forall l, \quad \frac{\partial}{\partial \beta_l} L(w, \alpha, \beta) & =0 \\ \forall k, \quad \alpha_k g_k(w) & =0 \\ \forall k, \quad g_k(w) & \leq 0 \\ \forall k, \quad \alpha_k & \geq 0 \end{aligned}$$

Learning and support vectors

之前已经推出，SVM 的优化目标是：

$$\begin{aligned} & \min _{w, b} \frac{1}{2}\|w\|^2 \\ \text { s.t. } \quad & \forall i,-y_i\left(w^{\top} X_i+b\right)+1 \leq 0 \end{aligned}$$

根据 KKT 条件，对于

$$-y_i\left(w^{\top} X_i+b\right)+1=0$$

的样本，才可能有

$$\alpha_i > 0$$

这些样本被称为 support vectors（支持向量）.

Optimization

SVM 的 Lagrangian 是：

$$L(w, b, \alpha)=\frac{1}{2}\|w\|^2-\sum_{i=1}^n \alpha_i\left[y_i\left(w^{\top} X_i+b\right)-1\right]$$

由 KKT 条件，有：

$$\begin{aligned} \frac{\partial L(w, b, \alpha)}{\partial w}&=w-\sum_{i=1}^n \alpha_i y_i X_i = 0 \\ \frac{\partial L(w, b, \alpha)}{\partial b}&=-\sum_{i=1}^n \alpha_i y_i = 0 \end{aligned}$$

从而有

$$\left\{ \begin{aligned} & \quad w=\sum_{i=1}^n \alpha_i y_i X_i \\ & \quad \sum_{i=1}^n \alpha_i y_i=0 \end{aligned}\right.$$

代入 $L(w, b, \alpha)$，得：

$$\begin{aligned} L(w, b, \alpha) & =\frac{1}{2}\|w\|^2-\sum_{i=1}^n \alpha_i\left[y_i\left(w^{\top} X_i+b\right)-1\right] \\ & =\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n y_i y_j \alpha_i \alpha_j X_i^{\top} X_j-\sum_{i=1}^n \sum_{j=1}^n y_i y_j \alpha_i \alpha_j X_i^{\top} X_j-b \sum_{i=1}^n \alpha_i y_i+\sum_{i=1}^n \alpha_i \\ & =\sum_{i=1}^n \alpha_i-\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n y_i y_j \alpha_i \alpha_j X_i^{\top} X_j-b \sum_{i=1}^n \alpha_i y_i \\ & =\sum_{i=1}^n \alpha_i-\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n y_i y_j \alpha_i \alpha_j X_i^{\top} X_j \end{aligned}$$

进而，我们可以用下式优化出 $\alpha$：

$$\begin{aligned} \max _\alpha W(\alpha), \quad W(\alpha)= & \sum_{i=1}^n \alpha_i-\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n y_i y_j \alpha_i \alpha_j\left\langle X_i, X_j\right\rangle \\ \text { s.t. } \quad & \forall i, \alpha_i \geq 0 \\ & \sum_{i=1}^n \alpha_i y_i=0 \end{aligned}$$

接着可以求出 $w$，以及 $b$：

$$b=-\frac{1}{2}\left(\min _{i: y_i=+1} w^{\top} X_i+\max _{i: y_i=-1} w^{\top} X_i\right)$$

从而，inference 过程可以写为：

$$\begin{aligned} w^{\top} X_i+b= & \left(\sum_{j=1}^n \alpha_j y_j X_j\right)^\top X_i+b \\ = & \sum_{j=1}^n \alpha_j y_j\left\langle X_j, X_i\right\rangle+b \\ = & \sum_{j: \alpha_j>0} \alpha_j y_j\left\langle X_j, X_i\right\rangle+b \\ = & \left\langle \sum_{j: \alpha_j>0} \alpha_j y_j X_j, X_i\right\rangle+b \end{aligned}$$

也就是说，只有支持向量对 $w$ 有贡献.

2.3 Kernel-based SVM

考虑非线性分类问题，$\phi(x)$ 是 $x$ 的高维特征向量. 对于推理过程，有：

$$\begin{aligned} w^{\top} \phi\left(X_i\right)+b & =\left(\sum_{j=1}^n \alpha_j y_j \phi\left(X_j\right)\right)^{\top} \phi\left(X_i\right)+b \\ & =\sum_{j=1}^n \alpha_j y_j\left\langle\phi\left(X_j\right), \phi\left(X_i\right)\right\rangle+b \\ & =\sum_{j: \alpha_j>0} \alpha_j y_j\left\langle\phi\left(X_j\right), \phi\left(X_i\right)\right\rangle+b \\ & =\sum_{j: \alpha_j>0} \alpha_j y_j K\left(X_j, X_i\right)+b \end{aligned}$$

其中

$$K\left(X_i, X_j\right) \stackrel{\text { def }}{=} \phi\left(X_i\right)^{\top} \phi\left(X_j\right)$$

被称为核（Kernel）. 也就是说，对之前求解的 SVM 结果，只要将 $\left\langle X_i, X_j\right\rangle$ 替换为 $K(X_i, X_j)$ 即可.

有时，$K\left(X_i, X_j\right)$ 相对 $\phi\left(X_i\right)$ 更好求. 事实上，我们只需要计算 $K(X_i, X_j)$ 而不用关心 $\phi(X_i)$ 的计算.

$K(X_i, X_j)$ 是核函数的充分必要条件是，同时满足：

• 对称性：$K\left(X_i, X_j\right)=K\left(X_j, X_i\right)$

• 半正定：设核矩阵 $K$，其中 $K_{ij} = K(X_i, X_j)$，那么 $\forall z, z^\top K z \ge 0$

2.4 Common kernels

• RBF kernel：即 Gaussian kernel

  $$K\left(X_i, X_j\right)=\exp \left(-\frac{\left\|X_i-X_j\right\|^2}{2 \sigma^2}\right)$$

  • 衡量了 $X_i$ 和 $X_j$ 的相似度

• Simple polynomial kernel：

  $$K\left(X_i, X_j\right)=\left(X_i^{\top} X_j\right)^d$$

• Cosine similarity kernel：

  $$K\left(X_i, X_j\right)=\frac{X_i^{\top} X_j}{\left\|X_i\right\|\left\|X_j\right\|}$$

• Sigmoid kernel：

  $$K\left(X_i, X_j\right)=\tanh \left(\alpha X_i^{\top} X_j+c\right)$$

2.5 With outliers

在现实生活中，我们不能保证全部正确分类. 此时的优化目标是：

$$\begin{aligned} \min _{\xi, w, b} \quad& \frac{1}{2}\|w\|^2+C \sum_{i=1}^n \xi_i \\ \text { s.t. } \quad & y_i\left(w^{\top} X_i+b\right) \geq 1-\xi_i, \quad i=1,2, \ldots, n \\ & \xi_i \geq 0, \quad i=1,2, \ldots, n \end{aligned}$$

这等价于

$$\min _{\xi, w, b} \quad \frac{1}{2}\|w\|^2+C \sum_{i=1}^n \max \left(0,1-y_i\left(w^{\top} X_i+b\right)\right)$$

注意到，$\max \left(0,1-y_i\left(w^{\top} X_i+b\right)\right)$ 就是 hinge loss.

此时的 Lagrangian 是：

$$L(w, b, \xi, \alpha, \beta)=\frac{1}{2}\|w\|^2+C \sum_{i=1}^n \xi_i-\sum_{i=1}^n \alpha_i\left[y_i\left(w^{\top} X_i+b\right)-1+\xi_i\right]-\sum_{i=1}^n \beta_i \xi_i$$

目标是：

$$\min _{w, b, \xi: \xi_i \geq 0} \max _{\alpha, \beta: \alpha_i \geq 0, \beta_i \geq 0} L(w, b, \xi, \alpha, \beta)$$

由

$$\frac{\partial L(w, b, \xi, \alpha, \beta)}{\partial w}=0, \quad\frac{\partial L(w, b, \xi, \alpha, \beta)}{\partial b}=0$$

可以得到优化 $\alpha$ 的目标：

$$\begin{aligned} \max _\alpha W(\alpha), \quad W(\alpha)= & \sum_{i=1}^n \alpha_i-\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n y_i y_j \alpha_i \alpha_j\left\langle X_i, X_j\right\rangle \\ \text { s.t. } \quad & \forall i, 0 \leq \alpha_i \leq C \\ & \sum_{i=1}^n \alpha_i y_i=0 \end{aligned}$$

KKT 条件是：

$$\begin{aligned} \alpha_i=0 & \Rightarrow y_i\left(w^{\top} X_i+b\right)>1 \\ \alpha_i=C & \Rightarrow y_i\left(w^{\top} X_i+b\right)<1 \\ 0<\alpha_i<C & \Rightarrow y_i\left(w^{\top} X_i+b\right)=1 \end{aligned}$$

Lecture 3: Kernels and Regularized Learning

3.1 Over-fitting & under-fitting

training set	validation set	Performance
error too large	irrelevant	Underfitting
error small	error too large	Overfitting
error small	error small	Ideal (Good generalization)

3.2 Ridge Regression

为了防止过拟合，Ridge regression 引入惩罚项 $\lambda\|\beta\|^2$，其中 $\lambda > 0$，即损失函数是：

$$\ell(\beta)=\|Y-X \beta\|^2+\lambda\|\beta\|^2$$

对损失求导，有：

$$\ell(\beta)=\|Y-X \beta\|^2+\lambda\|\beta\|^2=(Y-X \beta)^{\top}(Y-X \beta)+\lambda \beta^{\top} \beta$$

$$0=\left.\frac{\partial \ell(\beta)}{\partial \beta}\right|_{\beta=\hat{\beta}_\lambda}=-2 X^{\top}\left(Y-X \hat{\beta}_\lambda\right)+2 \lambda \hat{\beta}_\lambda$$

从而得到 $\beta$ 的解析解为：

$$\hat{\beta}_\lambda=\left(X^{\top} X+\lambda I_p\right)^{-1} X^{\top} Y$$

3.3 Kernel Regression

将 Ridge regression 中的 $x$ 换成 $\phi(x)$，并定义核 $K(x, x_i) = \phi(x)^\top \phi(x_i)$，就可以得到 kernel regression.

在 inference 时，有：

$$f(x) = \phi(x)^\top \beta$$

可以证明（见 3.11 节），

$$\beta=\sum_i c_i \phi\left(x_i\right)$$

从而

$$f(x)=\sum_{i=1}^n c_i K\left(x, x_i\right)$$

因此，目标就是要最小化：

$$l(c) = \sum_{i=1}^n\|y_i-\sum_{j=1}^n c_j K\left(x_i, x_j\right)\|^2+\lambda \sum_{i, j} c_i c_j K\left(x_i, x_j\right)$$

令 $K_{ij} = K(x_i, x_j)$，那么损失函数可以写作：

$$\ell(c)=\sum_{i=1}^n\|y_i-\sum_{j=1}^n c_j K_{i j}\|^2+\lambda \sum_{i, j} c_i c_j K_{i j}=\|Y-K c\|^2+\lambda c^{\top} K c$$

其中惩罚项：

$$\begin{aligned} c^{\top} K c & =\sum_{i, j} c_i c_j K\left(x_i, x_j\right) \\ & =\sum_{i, j} c_i c_j \phi\left(x_i\right)^{\top} \phi\left(x_j\right) \\ & =\left(\sum_i c_i \phi\left(x_i\right)\right)^{\top}\left(\sum_i c_i \phi\left(x_i\right)\right) \\ & =\|\beta\|^2 \end{aligned}$$

对损失求导，有：

$$\begin{gathered} \ell(c)=\|Y-K c\|^2+\lambda c^{\top} K c=(Y-K c)^{\top}(Y-K c)+\lambda c^{\top} K c \\ 0=\left.\frac{\partial \ell(c)}{\partial c}\right|_{c=\hat{c}_\lambda}=-2 K^{\top}\left(Y-K \hat{c}_\lambda\right)+2 \lambda K \hat{c}_\lambda \end{gathered}$$

从而得到 $c$ 的解析解为：

$$\hat{c}_\lambda=\left(K+\lambda I_n\right)^{-1} Y$$

3.4 Spline Regression

设 $x \in \mathbb{R}$，线性样条函数的形式是：

$$f(x)=\alpha_0+\sum_{j=1}^p \alpha_j \max \left(0, x-k_j\right)$$

从而最小化的目标是：

$$\sum_{i=1}^n\|y_i-\alpha_0-\sum_{j=1}^p \alpha_j \max \left(0, x_i-k_j\right)\|^2+\lambda \sum_{j=1}^p \alpha_j^2$$

也可将拟合误差写成：

$$y_i-\alpha_0-\sum_{j=1}^p \alpha_j \max \left(0, x_i-k_j\right)=y_i-\left[1, \max \left(0, x_i-k_1\right), \max \left(0, x_i-k_2\right), \ldots, \max \left(0, x_i-k_p\right)\right] \alpha$$

其中

$$\alpha=\left[\alpha_0, \alpha_1, \alpha_2, \ldots, \alpha_p\right]^{\top}.$$

Relations to the Ridge regression

令

$$\begin{aligned} \widetilde{X}_{i j} & =\max \left(0, x_i-k_j\right) \\ Z & =\left[1_n ~ \widetilde{X}\right] \\ D & =\operatorname{diag}(0,1, \ldots, 1) \end{aligned}$$

那么目标函数可以写作：

$$\ell(\alpha)=\|Y-Z \alpha\|^2+\lambda\|D \alpha\|^2$$

解得 $\alpha$ 的解析解为：

$$\hat{\alpha}_\lambda=\left(Z^{\top} Z+\lambda D\right)^{-1} Z^{\top} Y$$

Relations to the Kernel regression

将 $k_j$ 替换为 $x_j$，令 $K\left(x_i, x_j\right)=\max \left(0, x_i-x_j\right)$，那么有：

$$\hat{f}(x)=\sum_{j=1}^n \hat{\alpha}_j\left\langle x, x_j\right\rangle=\sum_{j=1}^n \hat{\alpha}_j K\left(x, x_j\right)$$

3.5 Lasso regression

Lasso regression 的目标是优化

$$\hat{\beta}_\lambda=\argmin_\beta\left[\frac{1}{2}\|\mathbf{Y}-\mathbf{X} \beta\|_{\ell_2}^2+\lambda\|\beta\|_{\ell_1}\right]$$

其中

$$\|\beta\|_{\ell_1}=\sum_{j=1}^p | \beta_j |$$

对于一般的 $p$，没有解析解，但对于 $p = 1$，存在解析解：

$$\hat{\beta}_\lambda= \begin{cases}(\langle\mathbf{Y}, \mathbf{X}\rangle-\lambda) /\|\mathbf{X}\|_{\ell_2}^2, & \text { if }\langle\mathbf{Y}, \mathbf{X}\rangle>\lambda \\ (\langle\mathbf{Y}, \mathbf{X}\rangle+\lambda) /\|\mathbf{X}\|_{\ell_2}^2, & \text { if }\langle\mathbf{Y}, \mathbf{X}\rangle<-\lambda \\ 0 & \text { if }|\langle\mathbf{Y}, \mathbf{X}\rangle| \leq \lambda\end{cases}$$

即

$$\hat{\beta}_\lambda=\operatorname{sign}(\hat{\gamma}) \max \left(0,|\hat{\gamma}|-\lambda /\|\mathbf{X}\|_{\ell_2}^2\right)$$

其中

$$\hat{\gamma}=\langle\mathbf{Y}, \mathbf{X}\rangle /\|\mathbf{X}\|_{\ell_2}^2$$

Ridge regression 希望没有主导特征，而 Lasso regression 希望特征稀疏.

3.6 Primal form of Lasso

Lasso regression 有两种等价形式：

• Primal form of Lasso：

$$\min ~ \|\mathbf{Y}-\mathbf{X} \beta\|_{\ell_2}^2 / 2 \quad \text{ subject to } \quad \|\beta\|_{\ell_1} \leq t$$

• Dual form of Lasso：

$$\min ~ \|\mathbf{Y}-\mathbf{X} \beta\|_{\ell_2}^2 / 2+\lambda\|\beta\|_{\ell_1}$$

接下来证明两种形式等价. 设两个式子有不相等的解：

$$\hat{\beta}_\lambda=\operatorname{argmin}\|\mathbf{Y}-\mathbf{X} \beta\|_{\ell_2}^2 / 2+\lambda\|\beta\|_{\ell_1}$$

$$\hat{\beta}=\underset{\beta}{\operatorname{argmin}}\|\mathbf{Y}-\mathbf{X} \beta\|_{\ell_2}^2 / 2 \quad \text { s.t. } \quad\|\beta\|_{\ell_1} \leq t$$

令 $t=\|\hat{\beta}_\lambda\|_{\ell_1}$，那么有

$$\|\mathbf{Y}-\mathbf{X} \hat{\beta}\|_{\ell_2}^2 / 2<\|\mathbf{Y}-\mathbf{X} \hat{\beta}_\lambda\|_{\ell_2}^2 / 2, \quad\|\hat{\beta}\|_{\ell_1} \leq\|\hat{\beta}_\lambda\|_{\ell_1}$$

从而

$$\|\mathbf{Y}-\mathbf{X} \hat{\beta}\|_{\ell_2}^2 / 2+\lambda\|\hat{\beta}\|_{\ell_1}<\|\mathbf{Y}-\mathbf{X} \hat{\beta}_\lambda\|_{\ell_2}^2 / 2+\lambda\|\hat{\beta}_\lambda\|_{\ell_1}$$

这与第一个式子矛盾，因此 $\hat{\beta}_\lambda = \hat{\beta}$.

3.7 Coordinate descent for Lasso solution path

高维 Lasso regression 的求解思路是：将每一个特征维度看作一维的 Lasso regression，从而用以下算法求解.

$$\begin{aligned} &\textbf { for } ~\lambda=10^a, 10^{a-\Delta}, 10^{a-2 \Delta}, 10^{a-3 \Delta}, \ldots, 10^b \textbf{ ~do }\\ &\quad \textbf { for } \text{~Feature dimension } j=1,2, \ldots, p \textbf{ ~do }\\ &\quad \quad \text { Compute the residual, } \textstyle \mathbf{R}_j=\mathbf{Y}-\sum_{k \neq j} \mathbf{X}_k \beta_k \text {; }\\ &\quad \quad \text { Update the parameter of the } j \text {-th dimension, } \beta_j=\operatorname{sign}\left(\hat{\gamma}_j\right) \max \left(0,\left|\hat{\gamma}_j\right|-\lambda /\|\mathbf{X}\|_{\ell_2}^2\right) \text {, where } \hat{\gamma}_j=\left\langle\mathbf{R}_j, \mathbf{X}_j\right\rangle /\left\|\mathbf{X}_j\right\|_{\ell_2}^2\\ &\quad \textbf{ end }\\ &\textbf{ end } \end{aligned}$$

3.8 Bayesian regression

考虑最大似然估计

$$\begin{aligned} P(\beta | \mathbf{X}, \mathbf{Y}) & = \frac{P(\beta | \mathbf{X}) P(\mathbf{Y} | \mathbf{X}, \beta)}{P(\mathbf{Y} | \mathbf{X})} \\ & = P(\beta)P(\mathbf{Y} | \mathbf{X}, \beta) \cdot C \end{aligned}$$

从而

$$\log P(\beta | \mathbf{X}, \mathbf{Y}) = \log P(\beta) + \log P(\mathbf{Y} | \mathbf{X}, \beta) + C$$

设

$$\beta \sim \mathrm{N}\left(0, \tau^2 \mathbf{I}_p\right)$$

$$\mathbf{Y} \sim \mathrm{N}(\mathbf{X}\beta, \sigma^2\mathbf{I})$$

那么

$$\log P(\beta | \mathbf{X}, \mathbf{Y})=-\frac{1}{2 \sigma^2}\|\mathbf{Y}-\mathbf{X} \beta\|_{\ell_2}^2-\frac{1}{2 \tau^2}\|\beta\|_{\ell_2}^2+C$$

要使似然函数最大，得到：

$$\hat{\beta}=\left(\mathbf{X}^{\top} \mathbf{X}+\frac{\sigma^2}{\tau^2} \mathbf{I}_p\right)^{-1} \mathbf{X}^{\top} \mathbf{Y}$$

对应 $\lambda=\sigma^2 / \tau^2$ 的 Ridge regression.

3.9 SVM and ridge logistic regression

考虑 SVM 的损失函数

$$\operatorname{loss}(\beta)=\sum_{i=1}^n \max \left(0,1-y_i X_i^{\top} \beta\right)+\frac{\lambda}{2}\|\beta\|^2$$

求梯度，得：

$$\operatorname{loss}^{\prime}(\beta)=-\sum_{i=1}^n 1\left(y_i X_i^{\top} \beta<1\right) y_i X_i+\lambda \beta$$

该损失函数与 Ridge logistic regression 的形式类似，即：

$$\operatorname{loss}(\beta)=\sum_{i=1}^n \log \left[1+\exp \left(-y_i X_i^{\top} \beta\right)\right]+\frac{\lambda}{2}\|\beta\|^2$$

其梯度为：

$$\operatorname{loss}^{\prime}(\beta)=-\sum_{i=1}^n \operatorname{sigmoid}\left(-y_i X_i^{\top} \beta\right) y_i X_i+\lambda \beta$$

3.10 Linear Version

若优化目标可以写作

$$\sum_{i=1}^n L\left(y_i ; x_i^{\top} \beta\right)+\lambda\|\beta\|^2$$

那么解空间的形式为：

$$\hat{\beta}=\sum_{i=1}^n \alpha_i x_i$$

采用反证法，设最优解

$$\tilde{\beta}=\sum_{i=1}^n \alpha_i x_i+\sum_{k=1}^K \kappa_k x_k$$

其中 $x_k \perp x_i$，那么

$$\begin{aligned} x_i^T \tilde{\beta} & =x_i^T\left(\sum_{j=1}^n \alpha_j x_j+\sum_{k=1}^K \kappa_k x_k\right) \\ & =\sum_{j=1}^n \alpha_j x_i^T x_j+\sum_{k=1}^K \kappa_k x_i^T x_k \\ & =\sum_{j=1}^n \alpha_j x_i^T x_j+\sum_{k=1}^K \kappa_k 0 \\ & =\sum_{j=1}^n \alpha_j x_i^T x_j \\ & =x_i^T \hat{\beta} \end{aligned}$$

从而

$$\sum_{i=1}^n L(y_i ; x_i^{\top} \hat{\beta})+\lambda\|\hat{\beta}\|^2 \leq \sum_{i=1}^n L(y_i ; x_i^{\top} \tilde{\beta})+\lambda\|\tilde{\beta}\|^2$$

因此，$\hat{\beta}$ 才是最优解.

3.11 Feature version

若优化目标可以写作

$$\sum_{i=1}^n L(y_i ; \phi(x_i)^{\top} \beta)+\lambda\|\beta\|^2$$

那么解空间的形式为：

$$\hat{\beta}=\sum_{i=1}^n \alpha_i \phi(x_i)$$

证明过程与 3.10 中类似，在此省略.

3.12 Gaussian Process and Bayesian Estimation

Linear version

对于 $Y=X \beta+\epsilon$，其中 $\beta \sim \mathrm{N}\left(0, \tau^2 I_p\right), \epsilon \sim \mathrm{N}\left(0, \sigma^2 I_n\right)$，且 $\beta$ 和 $\epsilon$ 相互独立. 为了考察 $\beta$ 的稳定性，我们希望得到后验分布 $\operatorname{Pr}[\beta | Y, X]$.

• 引理：设 $X_1$ 和 $X_2$ 是两个多维随机变量，且

  $$\begin{bmatrix} X_1 \\ X_2 \end{bmatrix} \sim N\left(\begin{bmatrix} \mu_1 \\ \mu_2 \end{bmatrix},\begin{bmatrix} \Sigma_{11} & \Sigma_{12} \\ \Sigma_{21} & \Sigma_{22} \end{bmatrix}\right)$$

  则

  $$\operatorname{Pr}\left[X_2 | X_1\right] \sim N\left(\mu_2+\Sigma_{21} \Sigma_{11}^{-1}\left(X_1-\mu_1\right), \Sigma_{22}-\Sigma_{21} \Sigma_{11}^{-1} \Sigma_{12}\right]$$

首先，求解 $Y = X\beta + \epsilon$ 的分布. 其均值为：

$$\operatorname{E}[Y]=X \operatorname{E}[\beta]+\operatorname{E}[\epsilon]=0$$

方差为：

$$\begin{aligned} \operatorname{Var}[Y] & =\operatorname{Var}[X \beta]+\operatorname{Var}[\epsilon] \\ & =X \operatorname{Var}[\beta] X^\top+\sigma^2 I_n \\ & =\tau^2 X X^\top+\sigma^2 I_n \end{aligned}$$

因此，$Y$ 的分布是：

$$Y \sim N\left(0, \tau^2 X X^\top+\sigma^2 I_n\right)$$

再求 $Y$ 和 $\beta$ 的协方差：

$$\begin{aligned} \operatorname{Cov}(Y, \beta) & =E_i\left[\left(Y_i-E_j\left[Y_j\right]\right)\left(\beta_i-E_j\left[\beta_j\right]\right)^{\top}\right] \\ & =E_i\left[\left(X \beta_i+\epsilon_i-E_j\left[X \beta_j+\epsilon_j\right]\right)\left(\beta_i-E_j\left[\beta_j\right]\right)^{\top}\right] \\ & =E_i\left[\left(X \beta_i+\epsilon_i-E_j\left[X \beta_j\right]-E_j\left[\epsilon_j\right]\right)\left(\beta_i\right)^{\top}\right] \\ & =E_i\left[\left(X \beta_i+\epsilon_i-E_j\left[X \beta_j\right]\right) \beta_i^{\top}\right] \\ & =E_i\left[X \beta_i \beta_i^{\top}\right]+E_i\left[\epsilon_i \beta_i^{\top}\right]-E_i\left[E_j\left[X \beta_j\right] \beta_i^{\top}\right] \\ & =E_i\left[X \beta_i \beta_i^{\top}\right]+0-E_i\left[0 \beta_i^{\top}\right] \\ & =X E_i\left[\beta_i \beta_i^{\top}\right] \\ & =X\left(\tau^2 I_p\right) \\ & =\tau^2 X \end{aligned}$$

因此，

$$\begin{bmatrix} Y \\ \beta \end{bmatrix} \sim N\left(\begin{bmatrix} 0 \\ 0 \end{bmatrix},\begin{bmatrix} \tau^2 X X^T+\sigma^2 I_n & \tau^2 X \\ \tau^2 X^T & \tau^2 I_p \end{bmatrix}\right)$$

从而

$$\begin{equation} \operatorname{Pr}[\beta | Y, X]=N\left(\tau^2 X^T\left(\tau^2 X X^T+\sigma^2 I_n\right)^{-1} Y, \tau^2 I_p-\tau^2 X^T\left(\tau^2 X X^T+\sigma^2 I_n\right)^{-1} \tau^2 X\right) \end{equation}$$

可以验证，该后验的均值与 $\lambda=\sigma^2 / \tau^2$ 的 Ridge regression 的求解结果相等. 因此，Ridge regression 可以看作最大化 $\beta$ 的后验概率.

Feature version

对于 $y_i=\phi\left(x_i\right)^{\top} \beta+\epsilon_i$，我们同样求解后验分布 $\operatorname{Pr}[\beta | Y, X]$. 设

$$\phi(X)=\begin{bmatrix} \phi\left(x_1\right)^{\top} \\ \phi\left(x_2\right)^{\top} \\ \ldots \\ \phi\left(x_n\right)^{\top} \end{bmatrix}_{n \times d}$$

那么只需要将 (3) 式中的 $X$ 替换为 $\phi(X)$ 即可，得到：

$$\operatorname{Pr}[\beta | Y, X]=N\left(\tau^2 \phi(X)^T\left(\tau^2 \phi(X) \phi(X)^T+\sigma^2 I_n\right)^{-1} Y, V\right)$$

其中

$$V=\tau^2 I_p-\tau^2 \phi(X)^T\left(\tau^2 \phi(X) \phi(X)^T+\sigma^2 I_n\right)^{-1} \tau^2 \phi(X)$$

不难发现，$V$ 中不含有 $Y$. 这表明 $\beta$ 的稳定性只和当前特征 $\phi(x)$ 有关，和高层任务 $Y$ 无关.

Kernel version

设 $f(x)=\phi(x)^{\top} \beta$，那么

$$Y=\begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}=\begin{bmatrix} f\left(x_1\right) \\ f\left(x_2\right) \\ \vdots \\ f\left(x_n\right) \end{bmatrix}+\epsilon$$

由于

$$\operatorname{Cov}\left(f(x), f\left(x^{\prime}\right)\right)=\operatorname{Cov}\left(\phi(x)^T \beta, \phi\left(x^{\prime}\right)^T \beta\right)=\tau^2 \phi(x)^T \phi\left(x^{\prime}\right)$$

令

$$K\left(x, x^{\prime}\right) = \tau^2 \phi(x)^T \phi\left(x^{\prime}\right)$$

那么 $Y$ 的分布可以写作：

$$Y \sim N\left(\mathbf{0}, \boldsymbol{K}+\sigma^2 \boldsymbol{I}_{\boldsymbol{n}}\right)$$

即

$$Y \sim N\left(\begin{bmatrix} 0 \\ \vdots \\ 0 \end{bmatrix},\begin{bmatrix} \tau^2 \phi\left(x_1\right)^T \phi\left(x_1\right)+\sigma^2 & \dots & \tau^2 \phi\left(x_1\right)^T \phi\left(x_n\right) \\ \vdots & \ddots & \vdots \\ \tau^2 \phi\left(x_n\right)^T \phi\left(x_1\right) & \ldots & \tau^2 \phi\left(x_n\right)^T \phi\left(x_n\right)+\sigma^2 \end{bmatrix}\right)$$

从而

$$\begin{bmatrix} Y \\ f\left(x_0\right) \end{bmatrix}=N\left(\begin{bmatrix} \mathbf{0} \\ 0 \end{bmatrix},\begin{bmatrix} \boldsymbol{K}+\sigma^2 \boldsymbol{I}_{\boldsymbol{n}} & \boldsymbol{K}\left(\boldsymbol{x}, x_0\right) \\ \boldsymbol{K}\left(x_0, \boldsymbol{x}\right) & K\left(x_0, x_0\right) \end{bmatrix}_{(n+1) \times(n+1)}\right)$$

因此，

$$\operatorname{Pr}\left[f\left(x_0\right) | Y, X\right] \sim N\left(K\left(x_0, x\right)\left(K+\sigma^2 I_n\right)^{-1} Y, K\left(x_0, x_0\right)-K\left(x_0, x\right)\left(K+\sigma^2 I_n\right)^{-1} K\left(x_0, x\right)^T\right)$$

该方差表明了在测试样本 $x_0$ 上的拟合误差大小，即该样本是否适用于这个网络.

Marginal likelihood

我们已经推出，$Y$ 的边缘分布为：

$$Y \sim \mathrm{N}\left(0, K_\gamma+\sigma^2 I_n\right)$$

其中 $\gamma$ 是高斯核参数. 使用最大似然估计，我们希望得到使得真实的 $Y$ 出现概率最大的参数 $\gamma$. 似然函数为：

$$\frac{1}{(2 \pi)^{n / 2}\left|\Sigma_\gamma\right|^{1 / 2}} \exp \left(-\frac{1}{2} Y^T \Sigma_\gamma^{-1} Y\right)$$

其中 $\Sigma_\gamma=K_\gamma+\sigma^2 I_n$. 取对数，得：

$$l=-\frac{1}{2} Y^T \Sigma_\gamma^{-1} Y-\frac{1}{2} \log \left(\left|\Sigma_\gamma\right|\right)-\frac{n}{2} \log (2 \pi)$$

接着由最大化 $l$ 即可解出 $\gamma$.

Lecture 4: Neural Networks

4.1 Neural networks

4.1.1 Two-layer perceptron

设双层感知机的输出 $y_i \in \{0, 1\}$ 由 $h_i=\left(h_{i k}, k=1, \ldots, d\right)^{\top}$ 经过 logistic regression 得到，而每个 $h_{ik}$ 由 $X_i=\left(x_{i j}, j=1, \ldots, p\right)^{\top}$ 经过 logistic regression 得到，即：

$$\begin{aligned} & y_i \sim \operatorname{Bernoulli}\left(p_i\right), \\ & p_i=\operatorname{sigmoid}\left(h_i^{\top} \beta\right)=\operatorname{sigmoid}\left(\sum_{k=1}^d \beta_k h_{i k}\right), \\ & h_{i k}=\operatorname{sigmoid}\left(X_i^{\top} \alpha_k\right)=\operatorname{sigmoid}\left(\sum_{j=1}^p \alpha_{k j} x_{i j}\right) . \end{aligned}$$

Back-propagation

我们使用最大似然估计，所有样本分类正确的概率为：

$$\begin{aligned} & P=\prod_{i=1}^n p_i^{y_i}\left(1-p_i\right)^{1-y_i} \\ \Longrightarrow \quad & \log P=\sum_{i=1}^n \left[y_i \log p_i+\left(1-y_i\right) \log \left(1-p_i\right)\right] \\ \Longrightarrow \quad & \log P=\sum_{i=1}^n\left\{y_i\{A-\log [1+\exp (A)]\}+\left(1-y_i\right)\{\log 1-\log [1+\exp (A)]\}\right\} \quad \text { where } \quad A=\sum_{k=1}^d \beta_k h_{i k} \\ \Longrightarrow \quad & \log P=\sum_{i=1}^n\left\{y_i A-\log [1+\exp (A)]\right\} \quad \text { where } \quad A=\sum_{k=1}^d \beta_k h_{i k} \end{aligned}$$

即对数似然为：

$$\mathscr{L}(\beta, \alpha)=\sum_{i=1}^n\left\{y_i \sum_{k=1}^d \beta_k h_{i k}-\log \left[1+\exp \left(\sum_{k=1}^d \beta_k h_{i k}\right)\right]\right\}$$

求梯度，得：

$$\begin{aligned} & \frac{\partial \mathscr{L}}{\partial \beta}=\sum_{i=1}^n\left(y_i-p_i\right) h_i \\ & \frac{\partial \mathscr{L}}{\partial \alpha_k}=\frac{\partial \mathscr{L}}{\partial h_k} \frac{\partial h_k}{\partial \alpha_k}=\sum_{i=1}^n \frac{\partial \mathscr{L}}{\partial h_{i k}} \frac{\partial h_{i k}}{\partial \alpha_k}=\sum_{i=1}^n\left(y_i-p_i\right) \beta_k h_{i k}\left(1-h_{i k}\right) X_i \end{aligned}$$

其中

$$\begin{aligned} \frac{\partial \mathscr{L}}{\partial h_{i k}} & =\frac{\partial}{\partial h_{i k}} \sum_{i=1}^n\left\{y_i \sum_{k=1}^d \beta_k h_{i k}-\log \left[1+\exp \left(\sum_{k=1}^d \beta_k h_{i k}\right)\right]\right\} \\ & =y_i \beta_k-\frac{\exp \left(\sum_{k=1}^d \beta_k h_{i k}\right) \beta_k}{1+\exp \left(\sum_{k=1}^d \beta_k h_{i k}\right)} \\ & =\left\{y_i-\frac{\exp \left(\sum_{k=1}^d \beta_k h_{i k}\right)}{1+\exp \left(\sum_{k=1}^d \beta_k h_{i k}\right)}\right\} \beta_k \\ & =\left\{y_i-\frac{1}{1+\exp \left(-\sum_{k=1}^d \beta_k h_{i k}\right)}\right\} \beta_k \\ & =\left(y_i-p_i\right) \beta_k \\ \frac{\partial h_{i k}}{\partial \alpha_k} & =\frac{\partial}{\partial \alpha_k}\left(\frac{1}{1+\exp \left(-\alpha_k^{\top} X_i\right)}\right) \\ & =\frac{\exp \left(-\alpha_k^{\top} X_i\right) X_i}{\left[1+\exp \left(-\alpha_k^{\top} X_i\right)\right]^2} \\ & =\left(\frac{1}{1+\exp \left(-\alpha_k^{\top} X_i\right)}\right)\left(\frac{\exp \left(-\alpha_k^{\top} X_i\right)}{1+\exp \left(-\alpha_k^{\top} X_i\right)}\right) X_i \\ & =h_{i k}\left(1-h_{i k}\right) X_i \end{aligned}$$

Rectified linear unit (ReLU)

在神经网络中，非线性常常通过 ReLU 函数 $\max(0, a)$ 引入. 例如：

$$\begin{aligned} & y_i \sim \operatorname{Bernoulli}\left(p_i\right), \\ & p_i=\operatorname{sigmoid}\left(h_i^{\top} \beta\right)=\operatorname{sigmoid}\left(\sum_{k=1}^d \beta_k h_{i k}\right), \\ & h_{i k}=\max \left(X_i^{\top} \alpha_k, 0\right)=\max \left(\sum_{j=1}^p \alpha_{k j} x_{i j}, 0\right) . \end{aligned}$$

对于 ReLU 函数的反向传播，有：

$$\frac{\partial h_{i k}}{\partial \alpha_k}=\mathbf{1}\left(\alpha_k^{\top} X_i>0\right) \cdot X_i=\mathbf{1}\left(h_{i k}>0\right) \cdot X_i$$

4.1.2 Multi-layer network

设多层感知机的每一层为：

$$\begin{aligned} h_l & =f_l\left(s_l\right) \\ s_l & =W_l h_{l-1}+b_l \end{aligned}$$

其中层数 $l=1, \ldots, L$，$h_0 = X$ 是输入向量，$h_L$ 用于预测 $Y$.

Chain rule in matrix form

为了推导反向传播，我们先回顾向量的求导法则. 设 $Y=\left(y_i\right)_{m \times 1}, X=\left(x_j\right)_{n \times 1}$. 如果 $Y=h(X)$，那么

$$\frac{\partial Y}{\partial X^{\top}}=\left(\frac{\partial y_i}{\partial x_j}\right)_{m \times n}.$$

如果 $Y=h(X)$ 且 $X=g(Z)$，那么

$$\frac{\partial y_i}{\partial z_j}=\sum_k \frac{\partial y_i}{\partial x_k} \frac{\partial x_k}{\partial z_j}$$

即

$$\frac{\partial Y}{\partial Z^{\top}}=\frac{\partial Y}{\partial X^{\top}} \frac{\partial X}{\partial Z^{\top}}$$

• 若$Y=A X$，那么 $y_i=\sum_k a_{i k} x_k$，从而 $\partial y_i / \partial x_j=a_{i j}$. 因此，$\partial Y / \partial X^{\top}=A$.
• 若 $Y=X^{\top} S X$，其中 $S$ 是对称矩阵，那么 $\partial Y / \partial X=2 S X$.
• 若 $S=I, Y=\|X\|^2$，那么 $\partial Y / \partial X=2 X$.

Multi-layer back-propagation

对于多层感知机，链式法则可以写为：

$$\begin{gathered} \frac{\partial L}{\partial s_l^{\top}}=\frac{\partial L}{\partial h_l^{\top}} \frac{\partial h_l}{\partial s_l^{\top}}=\frac{\partial L}{\partial h_l^{\top}} f_l^{\prime} \\ \frac{\partial L}{\partial h_{l-1}^{\top}}=\frac{\partial L}{\partial h_l^{\top}} \frac{\partial h_l}{\partial s_l^{\top}} \frac{\partial s_l}{\partial h_{l-1}^{\top}}=\frac{\partial L}{\partial h_l^{\top}} f_l^{\prime} W_l \end{gathered}$$

其中

$$\begin{gathered} W_l=\frac{\partial s_l}{\partial h_{l-1}^{\top}}=\begin{bmatrix} \frac{\partial s_{l, 1}}{\partial h_{l-1,1}} & \frac{\partial s_{l, 1}}{\partial h_{l-1,2}} & \frac{\partial s_{l, 1}}{\partial h_{l-1,3}} & \frac{\partial s_{l, 1}}{\partial h_{l-1,4}} & \frac{\partial s_{l, 1}}{\partial h_{l-1,5}} \\ \frac{\partial s_{l, 2}}{\partial h_{l-1,1}} & \frac{\partial s_{l, 2}}{\partial h_{l-1,2}} & \frac{\partial s_{l, 2}}{\partial h_{l-1,3}} & \frac{\partial s_{l, 2}}{\partial h_{l-1,4}} & \frac{\partial s_{l, 2}}{\partial h_{l-1,5}} \\ \frac{\partial s_{l, 3}}{\partial h_{l-1,1}} & \frac{\partial s_{l, 3}}{\partial h_{l-1,2}} & \frac{\partial s_{l, 3}}{\partial h_{l-1,3}} & \frac{\partial s_{l, 3}}{\partial h_{l-1,4}} & \frac{\partial s_{l, 3}}{\partial h_{l-1,5}} \\ \frac{\partial s_{l, 4}}{\partial h_{l-1,1}} & \frac{\partial s_{l, 4}}{\partial h_{l-1,2}} & \frac{\partial s_{l, 4}}{\partial h_{l-1,3}} & \frac{\partial s_{l, 4}}{\partial h_{l-1,4}} & \frac{\partial s_{l, 4}}{\partial h_{l-1,5}} \\ \frac{\partial s_{l, 5}}{\partial h_{l-1,1}} & \frac{\partial s_{l, 5}}{\partial h_{l-1,2}} & \frac{\partial s_{l, 5}}{\partial h_{l-1,3}} & \frac{\partial s_{l, 5}}{\partial h_{l-1,4}} & \frac{\partial s_{l, 5}}{\partial h_{l-1,5}} \end{bmatrix} \\ f_l^{\prime}=\frac{\partial h_l}{\partial s_l^{\top}}=\begin{bmatrix} \frac{\partial h_{l 1}}{\partial s_{l 1}} & 0 & 0 & 0 & 0 \\ 0 & \frac{\partial h_{l 2}}{\partial s_{l 2}} & 0 & 0 & 0 \\ 0 & 0 & \frac{\partial h_{l 3}}{\partial s_{l 3}} & 0 & 0 \\ 0 & 0 & 0 & \frac{\partial h_{l 4}}{\partial s_{l 4}} & 0 \\ 0 & 0 & 0 & 0 & \frac{\partial h_{l 5}}{\partial s_{l 5}} \end{bmatrix} \end{gathered}$$

如果 $f$ 是 Sigmoid 函数，对角线元素 $\partial h_{l k} / \partial s_{l k}$ 的值为 $h_{l k}\left(1-h_{l k}\right)$；如果 $f$ 是 ReLU 函数，$\partial h_{l k} / \partial s_{l k}$ 的值为 $1\left(h_{l k}>0\right)$.

对 $\partial L/\partial h_{l-1}^{\top}$ 转置，得：

$$\frac{\partial L}{\partial h_{l-1}}=W_l^{\top} f_l^{\prime} \frac{\partial L}{\partial h_l} .$$

接着，推导 $\partial L / \partial W_l$. 首先，对 $W_l$ 的第 $k$ 行求梯度：

$$\left(\frac{\partial L}{\partial W_{l k}}\right)_{1 \times K}=\left(\frac{\partial L}{\partial s_{l k}}\right)_{1 \times 1}\left(\frac{\partial s_{l k}}{\partial W_{l k}}\right)_{1 \times K}=\left(\frac{\partial L}{\partial s_{l k}}\right)_{1 \times 1}\left(h_{l-1}^{\top}\right)_{1 \times K} .$$

再将所有行的结果整合，得到：

$$\left(\frac{\partial L}{\partial W_l}\right)_{K \times K}=\left(\frac{\partial L}{\partial s_l}\right)_{K \times 1}\left(h_{l-1}^{\top}\right)_{1 \times K}=\left(f_l^{\prime}\right)_{K \times K}\left(\frac{\partial L}{\partial h_l}\right)_{K \times 1}\left(h_{l-1}^{\top}\right)_{1 \times K}$$

同理，

$$\frac{\partial L}{\partial b_l}= f_l^{\prime} \frac{\partial L}{\partial h_l} .$$

令

$$\Delta h_l=\frac{\partial L}{\partial h_l}, \Delta W_l=\frac{\partial L}{\partial W_l}, D_l=f_l^{\prime},$$

那么之前的结果可以写为：

$$\begin{aligned} & \Delta h_{l-1}=W_l^{\top} D_l \Delta h_l, \\ & \Delta W_l=D_l \Delta h_l h_{l-1}^{\top}, \end{aligned}$$

加入 $b_l$ 可以写为：

$$\left(\Delta W_l, \Delta b_l\right)=\Delta\left(W_l, b_l\right)=D_l \Delta h_l\left(h_{l-1}^{\top}, 1\right) .$$

4.1.3 Stochastic gradient descent (SGD)

Mini-batch

使用在小批量上的梯度下降法. 设 $\mathscr{L}(\theta)=\frac{1}{n} \sum_{i=1}^n L_i(\theta)$ 是在一个小批量上的平均损失，那么 SGD 的公式为：

$$\theta_{t+1}=\theta_t-\eta_t \mathscr{L}^{\prime}\left(\theta_t\right).$$

Momentum, Adagrad, RMSprop, Adam

为了解决优化过程中的振荡问题，我们在 SGD 中引入动量 (Momentum)，其更新公式为：

$$\begin{aligned} & v_t=\gamma v_{t-1}+\eta_t g_t \\ & \theta_t=\theta_{t-1}-v_t \end{aligned}$$

其中 $g_t$ 是当前小批量上的平均梯度，$v_t$ 是动量.

在另一个方向上，为了解决不同维度梯度尺度不一致的问题，有 Adagrad 方法：

$$\begin{aligned} & G_t=G_{t-1}+g_t^2 \\ & \theta_{t+1}=\theta_t-\eta_t \frac{g_t}{\sqrt{G_t+\varepsilon}} \end{aligned}$$

这一方法使得高频维度学习率降低，稀疏维度保持大学习率. 但 Adagrad 存在学习率越来越小的问题，因此 RMSProp 对该方法作了改进：

$$G_t=\beta G_{t-1}+(1-\beta) g_t^2$$

Adam 方法是对 RMSProp 和 Momentum 方法的结合，即：

$$\begin{aligned} & v_t=\gamma v_{t-1}+(1-\gamma) g_t, \\ & G_t=\beta G_{t-1}+(1-\beta) g_t^2, \\ & v_t \leftarrow v_t /(1-\gamma^t), G_t \leftarrow G_t /(1-\beta^t), \\ & \theta_{t+1}=\theta_t-\eta_t \frac{v_t}{\sqrt{G_t+\varepsilon}} . \end{aligned}$$

4.2 Convolutional neural networks (CNN)

4.2.1 Convolution, kernels, filters

基本的卷积神经网络可以表示为：

$$\begin{aligned} s & =W \otimes h+b \\ s_{u v w} & =\sum_{i=1}^R \sum_{j=1}^R \sum_{k=1}^C W_{i j k}^w h_{t(u-1)-p+i, t(v-1)-p+j, k}+b^w \end{aligned}$$

其中卷积核尺寸为 $R \times R \times C$，$W_{i j k}^w$ 表示第 $w$ 个卷积核的 $(i, j, k)$ 位置；$t$ 表示 stride，即每一步移动几格；$p$ 表示 padding，即外侧补 0 的圈数.

注意：每个卷积核的参数数量是 $R \times R \times C + 1$；卷积核的第三个维度应等于输入通道数，卷积核的数量等于输出通道数. 要会计算卷积核的参数量，以及输入和输出的尺寸大小.

输出的尺寸为：

$$\left\lfloor \frac{W - F + 2P}{S} + 1 \right\rfloor$$

其中 $W$ 是原始尺寸（长宽），$F$ 是卷积核尺寸，$P$ 是 padding，$S$ 是 stride.

接着通过 ReLU 层：

$$\begin{array}{ll} & h=\max \{s, \mathbf{0}\} \\ \text { i.e. } & h_{i j k}=\max \left\{s_{i j k}, 0\right\} \end{array}$$

然后作最大池化（Max-Pooling）或平均池化（Average-Pooling）. 该操作也有 kernel size $R$、stride 和 padding 参数，表示在每个 $R \times R$ 的区域内选取最大元素或求平均值.

4.2.2 Softmax layer for classification

经典的 CNN 结构是：x $\to$ Conv $\to$ ReLU $\to$ Max-Pooling $\to$ Conv $\to$ ReLU $\to$ Max-Pooling $\to$ FC $\to$ ReLU $\to$ FC $\to$ ReLU $\to$ FC $\to$ Softmax $\to$ CrossEntropy.

4.2.3 Alex net, VGG net, inception net

VGG16 的结构是 x $\to$ (Conv $\to$ ReLU $\to$ Conv $\to$ ReLU $\to$ Max-Pooling) * 2 $\to$ (Conv $\to$ ReLU $\to$ Conv $\to$ ReLU $\to$ Conv $\to$ ReLU $\to$ Max-Pooling) * 3 $\to$ FC $\to$ ReLU $\to$ FC $\to$ ReLU $\to$ FC $\to$ Softmax $\to$ CrossEntropy.

4.2.4 Batch normalization layer

Batch normalization 是在通道维度上做归一化，即对每个通道单独做归一化.

$$\begin{aligned} \mu_d & =\frac{1}{n} \sum_{i=1}^n x_{i d} ; \quad \text { with channels } d=1,2, \ldots, D \\ \sigma_d^2 & =\frac{1}{n} \sum_{i=1}^n\left(x_{i d}-\mu_d\right)^2 \\ \hat{x}_{i d} & =\frac{x_{i d}-\mu_d}{\sigma_d} \\ y_{i d} & =\beta_d+\gamma_d \hat{x}_{i d} \end{aligned}$$

例如，设输入尺寸为 $(N, H, W, C)$，那么对第 $c$ 个通道，使用 $N \times H \times W$ 个位置统计 $\mu_c$ 和 $\sigma_c$.

4.2.5 Residual net

残差网络的基本结构是：

$$x_{l+1}=x_l+F\left(x_l\right)$$

其中 $F$ 包含的结构是 BN $\to$ ReLU $\to$ Conv $\to$ BN $\to$ ReLU $\to$ Conv.

相比于级联网络，残差网络性能更好、收敛更快. 一种解释是，$n$ 层残差网络等效于并联 $2^n$ 个深度不等的级联模块，从而在训练初期可以先用浅层的模块进行拟合，优化更简单.

4.3 Recurrent neural networks

4.3.1 RNN

基本的 RNN 结构是：

$$\begin{aligned} & s_t=f\left(U x_t+W s_{t-1}\right) \\ & o_t=g\left(V s_t\right) \end{aligned}$$

其中 $x_t$、$o_t$ 和 $s_t$ 分别是 $t$ 时刻的输入、输出和状态.

4.3.2 LSTM

LSTM 的基本结构是：

$$\begin{aligned} & \Delta c_t=f\left(W_c\left(h_{t-1}, x_t\right)\right), \quad \text { Representation of input information } \\ & i_t=f\left(W_i\left(h_{t-1}, x_t\right)\right), \quad \text { Input gate } \\ & f_t=f\left(W_f\left(h_{t-1}, x_t\right)\right), \quad \text { Forget gate } \\ & c_t=c_{t-1} f_t+\Delta c_t i_t, \quad \text { Cell state vector } \\ & o_t=f\left(W_o\left(h_{t-1}, x_t\right)\right), \quad \text { Output gate } \\ & h_t=o_t f\left(c_t\right), \quad \text { Hidden state vector } \\ & y_t=f\left(W h_t\right) . \end{aligned}$$

其中 $c_t$ 是 $t$ 时刻的 cell states，即长期记忆；$h_t$ 是 $t$ 时刻的 hidden states，即短期记忆.

4. 3.3 GRU

GRU 是对 LSTM 的简化，其基本结构是：

$$\begin{aligned} & z_t=f\left(W_z\left(h_{t-1}, x_t\right)\right), \quad \text { Update gate } \\ & r_t=f\left(W_r\left(h_{t-1}, x_t\right)\right), \quad \text { Reset gate } \\ & \tilde{h}_t=f\left(W\left(x_t, r_t h_{t-1}\right)\right), \quad \text { New information from the input } \\ & h_t=\left(1-z_t\right) h_{t-1}+z_t \tilde{h}_t, \quad \text { Hidden state } \\ & y_t=f\left(W_h h_t\right) . \end{aligned}$$

4.4 Generator and GAN

4.4.2 Supervised decoder

考虑用 Encode-Decoder 架构进行图像重建：Encoder(参数 $\phi$) 将输入图像 $I$ 进行压缩，再经过 Decoder(参数 $\theta$) 对其进行重建，即

$$\begin{gathered} f = \operatorname{Encoder}_\phi (I) \\ \hat{I} = \operatorname{Decoder}_\theta(f) \end{gathered}$$

优化目标是：

$$\min_{\phi, \theta} ~ \Vert I - \hat{I} \Vert^2$$

4.4.3 GAN

GAN 中有一个判别器 $D$ 和一个生成器 $G$. 输入 $h \sim N(0, \sigma^2 I)$，$G_\theta$ 输出 $\hat{x}$，再用 $D_\phi$ 判断 $\hat{x}$ 或 $x^*$ 是否是真实样本，即 $D(X)$ 是真实图像的概率.

设 $h \sim p(h)$ 下 $G(h)$ 的分布是 $p_\theta$，那么

$$V(D, G)= \mathbb{E}_{P_{\text {data }}}[\log D(X)]+\mathbb{E}_{p_\theta}[\log (1-D(X))] = \mathbb{E}_{P_{\text {data }}}[\log D(X)]+\mathbb{E}_{h \sim p(h)}[\log (1-D(G(h)))]$$

从而 GAN 的训练目标是：

$$\min _G \max _D V(D, G)$$

对于理想的判别器，有：

$$\begin{aligned} & \frac{\partial V}{\partial D}=0 \\ \Rightarrow ~ & \frac{P_{\text {data }}(X)}{D(X)}-\frac{p_\theta(X)}{1-D(X)}=0 \\ \Rightarrow ~ & -p_\theta(X) D(X)+P_{\text {data }}(X)-P_{\text {data }}(X) D(X)=0 \\ \Rightarrow ~ & D(X)=\frac{P_{\text {data }}(X)}{p_\theta(X)+P_{\text {data }}(X)} \end{aligned}$$

对于理想的生成器，$\theta$ 要最小化 $P_{\text {data }}$ 和 $p_\theta$ 之间的 JS 散度（一种具有对称性的 KL 散度变体）. 令 $p_{\operatorname{mix}}=\left(P_{\mathrm{data}}+p_\theta\right) / 2$，那么有：

$$\begin{aligned} \operatorname{JSD}\left(P_{\text {data }} | p_\theta\right) & =\operatorname{KL}\left(p_\theta | p_{\text {mix }}\right)+\operatorname{KL}\left(P_{\text {data }} | p_{\text {mix }}\right) \\ & =\sum_X\left[p_\theta(X) \log \frac{p_\theta(X)}{p_{\text {mix }}(X)}+P_{\text {data }}(X) \log \frac{P_{\text {data }}(X)}{p_{\text {mix }}(X)}\right] \\ & =-H\left(p_\theta\right)-H\left(P_{\text {data }}\right)-\sum_X\left[p_\theta(X) \log p_{\text {mix }}(X)+P_{\text {data }}(X) \log p_{\text {mix }}(X)\right] \\ & =-H\left(p_\theta\right)-H\left(P_{\text {data }}\right)-\sum_X\left[p_\theta(X) \log \frac{p_\theta(X)}{2(1-D(X))}+P_{\text {data }}(X) \log \frac{P_{\text {data }}(X)}{2 D(X)}\right] \\ & =-H\left(p_\theta\right)-H\left(P_{\text {data }}\right)+H\left(p_\theta\right)+H\left(P_{\text {data }}\right)+\sum_X\left[p_\theta(X) \log [2(1-D(X))]+P_{\text {data }}(X) \log (2 D(X))\right] \\ & =\sum_X\left[p_\theta(X) \log 2+P_{\text {data }}(X) \log 2\right]+\sum_X\left[p_\theta(X) \log (1-D(X))+P_{\text {data }}(X) \log (D(X))\right] \\ & =2 \log 2+V(D, G) \end{aligned}$$

由此可见，降低 $V(D, G)$ 的本质就是使得 $p_\theta$ 和 $P_\text{data}$ 两个分布尽可能接近.

4.4.4 Geometry of VAE

VAE 分为 Encoder 和 Decoder 两部分. 输入 $x$ 经过 Encoder $q_\phi$ 压缩为低维向量 $h$，再通过 Decoder $p_\theta$ 重建为 $\hat{x}$. 优化目标是 $\Vert x - \hat{x} \Vert^2$ 尽可能小.

VAE 的损失函数是：

$$L(\phi, \theta, X)=\mathrm{KL}\left(q_\phi(h | X) | p_\theta(h | X)\right)-\mathbb{E}_{q_\phi(h | X)}\left(\log p_\theta(X | h)\right)$$

其中 $p_\theta(h|X)$ 可以认为是 $N(\mathbf{0}, \mathbf{I})$. 第一项是 $q_\phi(h|X)$ 和 $N(\mathbf{0}, \mathbf{I})$ 之间的 KL 散度，限制了 $h$ 的分布，用于防止过拟合及便于作为生成器；第二项是 $p_\theta(X|h)$ 的重建误差，实质上是 $X$ 和 $p_\theta(X|h)$ 之间的平方损失.

该损失函数也可以写作

$$\operatorname{KL}\left(P_{\text {data}}(X) | p_\theta(X)\right)+\operatorname{KL}\left(q_\phi(h | X) | p_\theta(h | X)\right)=\operatorname{KL}\left(P_{\text {data}}(X) q_\phi(h | X) | p_\theta(h, X)\right)$$

可以看出，VAE 的目标是让 Encoder 和 Decoder 建模的联合概率分布尽可能接近.

下面证明两个损失函数等价：

$$\begin{aligned} \frac{\partial}{\partial \theta} \mathrm{KL}\left(P_{\text {data }}(X) | p_\theta(X)\right) & =\frac{\partial}{\partial \theta} \mathbb{E}_{P_{\text {data }}(X)}\left(-\log \sum_h p_\theta(h, X)\right)-\frac{\partial}{\partial \theta} H\left(P_{\text {data }}(X)\right) \\ & =\frac{\partial}{\partial \theta} \mathbb{E}_{P_{\text {data }}(X)}\left(-\log \sum_h p_\theta(h, X)\right) \\ & =-\mathbb{E}_{P_{\text {data }}(X)} \sum_h \frac{p(h, X)}{\sum_{h^{\prime}} p\left(h^{\prime}, X\right)} \frac{1}{p_\theta(h, X)} \frac{\partial}{\partial \theta} p_\theta(h, X) \\ & =-\mathbb{E}_{P_{\text {data }}(X)} \sum_h p(h | X) \frac{\partial}{\partial \theta} \log p_\theta(h, X) \\ & =-\mathbb{E}_{P_{\text {data }}(X)} \mathbb{E}_{q_\phi(h | X)} \frac{\partial}{\partial \theta}\left(\log p_\theta(X | h)+\log p(h)\right) \quad \text { where } p(h | X) \leftarrow q_\phi(h | X) \\ & =-\mathbb{E}_{P_{\text {data }}(X)} \mathbb{E}_{q_\phi(h | X)} \frac{\partial}{\partial \theta} \log p_\theta(X | h) \\ & =\frac{\partial}{\partial \theta} \mathbb{E}_{P_{\text {data }}(X)}\left[-\mathbb{E}_{q_\phi(h | X)} \log p_\theta(X | h)\right] \end{aligned}$$

4.4.5 ELBO

VAE 的优化目标是：

$$\operatorname{KL}\left(P_{\text {data }}(X) | p_\theta(X)\right)+\operatorname{KL}\left(q_\phi(h | X) | p_\theta(h | X)\right) =\mathbb{E}_{P_{\text {data }}}\left[\log P_{\text {data }}(X)\right]-\mathbb{E}_{P_{\text {data }}}\left[\log p_\theta(X)\right]+\operatorname{KL}\left(q_\phi(h | X) | p_\theta(h | X)\right)$$

因此等效于最大化

$$\mathbb{E}_{P_{\text {data }}}\left[\log p_\theta(X)\right]-\mathrm{KL}\left(q_\phi(h | X) | p_\theta(h | X)\right)=\frac{1}{n} \sum_{i=1}^n\left[\log p_\theta\left(X_i\right)-\mathrm{KL}\left(q_\phi\left(h_i | X_i\right) | p_\theta\left(h_i | X_i\right)\right)\right]$$

这被称为证据下界(ELBO).

Lecture 6: Clustering, Expectation-Maximization, Gaussian Mixture Model, Feature Visualization, and Machine Learning Theories

6.1 Principle component analysis (PCA)

PCA 的作用是：找到数据分布的主方向，从而实现降维.

将每一个样本 $\mathbf{x}_{(i)}$ 投影到 $\mathbf{w}_{(k)}$ 方向上，其投影长度为：

$$t_{k(i)}=\left\langle\mathbf{x}_{(i)}, \mathbf{w}_{(k)}\right\rangle \quad \text { for } \quad i=1, \ldots, n \quad k=1, \ldots, l$$

6.1.1 First component

我们希望找到一个方向，来最大化 $t_{1(i)}$ 的方差，即：

$$\mathbf{w}_{(1)}=\underset{\|\mathbf{w}\|=1}{\operatorname{argmax}} \operatorname{Var}_i\left(t_1\right)=\underset{\|\mathbf{w}\|=1}{\operatorname{argmax}}\left\{\sum_i\left(t_{1(i)}-\mathbb{E}_j\left[t_{1(j)}\right]\right)^2\right\}=\underset{\|\mathbf{w}\|=1}{\operatorname{argmax}}\left\{\sum_i\left(t_{1(i)}-0\right)^2\right\}=\underset{\|\mathbf{w}\|=1}{\operatorname{argmax}}\left\{\sum_i\left\langle\mathbf{x}_{(i)}, \mathbf{w}\right\rangle^2\right\}$$

进而写成矩阵形式：

$$\mathbf{w}_{(1)}=\underset{\|\mathbf{w}\|=1}{\operatorname{argmax}}\left\{\|\mathbf{X} \mathbf{w}\|^2\right\}=\underset{\|\mathbf{w}\|=1}{\operatorname{argmax}}\left\{\mathbf{w}^{\top} \mathbf{X}^{\top} \mathbf{X} \mathbf{w}\right\}$$

这等价为：

$$\mathbf{w}_{(1)}=\operatorname{argmax}_{\mathbf{w}}\left\{\frac{\mathbf{w}^{\top} \mathbf{X}^{\top} \mathbf{X} \mathbf{w}}{\mathbf{w}^{\top} \mathbf{w}}\right\}$$

使用 Lagrange 乘子法，得到：

$$\begin{aligned} & 0=\dfrac{\partial}{\partial \mathbf{w}}\left[\mathbf{w}^{\top} \mathbf{X}^{\top} \mathbf{X} \mathbf{w}-\lambda \mathbf{w}^{\top} \mathbf{w}\right]=2 \mathbf{X}^{\top} \mathbf{X} \mathbf{w}-2 \lambda \mathbf{w} \\ \Longrightarrow \quad & \mathbf{X}^{\top} \mathbf{X} \mathbf{w}=\lambda \mathbf{w} \end{aligned}$$

此时，目标函数值为 $\lambda$. 因此，$\mathbf{w}$ 是 $\mathbf{X}^{\top} \mathbf{X}$ 的最大特征值对应的特征向量.

6.1.2 Further components

求解第 $k$ 个主方向，可以先从 $\mathbf{X}$ 中减去前 $k-1$ 个主方向：

$$\hat{\mathbf{X}}_k=\mathbf{X}-\sum_{s=1}^{k-1} \mathbf{X} \mathbf{w}_{(s)} \mathbf{w}_{(s)}^{\top}$$

再求解第一主方向，即：

$$\mathbf{w}_{(k)}=\underset{\|\mathbf{w}\|=1}{\operatorname{argmax}}\left\{\|\hat{\mathbf{X}}_k \mathbf{w}\|^2\right\}=\operatorname{argmax}_{\mathbf{w}}\left\{\frac{\mathbf{w}^{\top} \hat{\mathbf{X}}_k^{\top} \hat{\mathbf{X}}_k \mathbf{w}}{\mathbf{w}^{\top} \mathbf{w}}\right\}$$

可以证明，$\mathbf{X}$ 的第 $k$ 个主方向就是 $\mathbf{X}^{\top} \mathbf{X}$ 的第 $k$ 大特征值对应的特征向量.

令 $\mathbf{W}$ 的每一列是 $\mathbf{X}$ 的主方向，那么通过

$$\mathbf{T}=\mathbf{X W}$$

就可以实现数据降维.

6.2 Stochastic Neighbor Embedding (t-SNE) (in order to visualize the data distribution)

$x_i$ 通常是一个高维特征，我们想要将 $x_i$ 投影到低维空间（通常是二维）$h_i$ 中，来进行特征的可视化. 为了使得更相似的样本离得更近，我们首先需要定义样本 $x_j$ 和 $x_i$ 之间的相似度：

$$P_{i j} =P\left(x_j | x_i\right) =\frac{e^{-\left|x_j-x_i\right|^2 / 2 \sigma_i^2}}{\sum_{m=1}^n e^{-\left|x_m-x_i\right|^2 / 2 \sigma_i^2}}$$

再定义投影后 $h_j$ 和 $h_i$ 之间的相似度：

$$q_{i j} =P\left(h_j | h_i\right) =\frac{\left(1+\left|h_j-h_i\right|^2\right)^{-1}}{\sum_{m=1}^n\left(1+\left|h_m-h_i\right|^2\right)^{-1}}$$

从而 t-SNE 的优化目标是：

$$\min_{\left\{h_i\right\}} ~ \mathrm{KL}(P \| Q)=\sum_{i, j} P_{i j} \log \left(\frac{P_{i j}}{q_{i j}}\right)$$

这意味着高维空间中的邻近关系在降维后得到了保留.

6.2.1 Local Linear Embedding

为了在降维时保留局部线性关系，我们将 $x_i$ 表示为：

$$x_i \approx \sum_{j \in N_i} w_{i j} x_j$$

其中 $N_i$ 表示 $i$ 的邻居. 通过 least-squares 可以求解 $w$，即

$$\min _{\left\{w_{i j}\right\}}|x_i-\sum_{j \in N_i} w_{i j} x_j|^2$$

进而求解出 $h_i$：

$$\min _{\left\{h_i\right\}}|h_i-\sum_{j \in N_i} w_{i j} h_j|^2$$

6.3 The Expectation Maximization (EM) Algorithm

EM 算法的目标，是建模所有样本 $\mathbf{X}$ 的潜在分布. 以聚类问题为例，设想我们要对样本 $\mathbf{X} = (x_1, x_2, \dots, x_n)$ 进行聚类，那么要识别出 $k$ 个 cluster，其参数 $\theta = (\mu_1, \sigma_1^2, \mu_2, \sigma_2^2, \dots, \mu_k, \sigma_k^2)$，并给每个 $x_i$ 一个类别标签 $z_i$，即 $\mathbf{Z} = (z_1, z_2, \dots, z_n)$，其中 $z_i = j$ 表示判断为第 $j$ 类. 故优化目标为：

$$\max _\theta L(\theta, \mathbf{X}), \quad L(\theta, \mathbf{X}) \stackrel{\text { def }}{=} p(\mathbf{X} | \theta)=\int_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z} | \theta) d \mathbf{Z}$$

• Expectation step (E step):

$$Q(\theta | \theta^{(t)})=\mathbb{E}_{\mathbf{Z} \sim p(\mathbf{Z} | \mathbf{X}, \theta^{(t)})}[\log p(\mathbf{X}, \mathbf{Z} | \theta)]$$

• Maximization step (M step):

$$\theta^{(t+1)}=\argmax_\theta Q(\theta | \theta^{(t)})$$

为了更好地计算 $Q(\theta | \theta^{(t)})$，我们在实际使用中对其化简：

$$\begin{aligned} Q(\theta | \theta^{(t)}) & = \mathbb{E}_{\mathbf{Z} \sim p(\mathbf{Z} | \mathbf{X}, \theta^{(t)})}[\log p(\mathbf{X}, \mathbf{Z} | \theta)] \\ & = \mathbb{E}_{\mathbf{Z} \sim p(\mathbf{Z} | \mathbf{X}, \theta^{(t)})}\left[\sum_{i=1}^n \log p(x_i, z_i | \theta)\right] \\ & = \sum_{i=1}^n \mathbb{E}_{\mathbf{Z} \sim p(\mathbf{Z} | \mathbf{X}, \theta^{(t)})}\left[ \log p(x_i, z_i | \theta)\right] \\ & = \sum_{i=1}^n \mathbb{E}_{z_i \sim p(z_i | x_i, \theta^{(t)})}\left[ \log p(x_i, z_i | \theta)\right] \\ & = \sum_{i=1}^n \mathbb{E}_{z_i \sim p(z_i | x_i, \theta^{(t)})}\left[ \log p(z_i) + \log p(x_i | z_i, \theta)\right] \end{aligned}$$

接下来，我们推导 $Q(\theta | \theta^{(t)})$ 为何等效于我们的优化目标.

$$\begin{aligned} \frac{\partial}{\partial \theta} \log p(\mathbf{X} | \theta) & =\frac{1}{p(\mathbf{X} | \theta)} \frac{\partial}{\partial \theta} p(\mathbf{X} | \theta) \\ & =\frac{1}{p(\mathbf{X} | \theta)} \frac{\partial}{\partial \theta} \sum_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z} | \theta) \\ & =\frac{1}{p(\mathbf{X} | \theta)} \sum_{\mathbf{Z}} \frac{\partial}{\partial \theta} p(\mathbf{X}, \mathbf{Z} | \theta) \\ & =\frac{1}{p(\mathbf{X} | \theta)} \sum_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z} | \theta) \frac{\partial}{\partial \theta} \log p(\mathbf{X}, \mathbf{Z} | \theta) \\ & =\sum_{\mathbf{Z}} \frac{p(\mathbf{X}, \mathbf{Z} | \theta)}{p(\mathbf{X} | \theta)} \frac{\partial}{\partial \theta} \log p(\mathbf{X}, \mathbf{Z} | \theta) \\ & =\sum_{\mathbf{Z}} p(\mathbf{Z} | \mathbf{X}, \theta) \frac{\partial}{\partial \theta} \log p(\mathbf{X}, \mathbf{Z} | \theta) \\ & \approx \sum_{\mathbf{Z}} p(\mathbf{Z} | \mathbf{X}, \theta^{(t)}) \frac{\partial}{\partial \theta} \log p(\mathbf{X}, \mathbf{Z} | \theta), \quad \text { here we use } \theta^{(t)} \text { instead of } \theta . \\ & =\frac{\partial}{\partial \theta} \sum_{\mathbf{Z}} p(\mathbf{Z} | \mathbf{X}, \theta^{(t)}) \log p(\mathbf{X}, \mathbf{Z} | \theta) \\ & =\frac{\partial}{\partial \theta} \mathbb{E}_{\mathbf{Z} \sim p(\mathbf{Z} | \mathbf{X}, \theta^{(t)})}[\log p(\mathbf{X}, \mathbf{Z} | \theta)] \end{aligned}$$

因此，最大化 $Q(\theta | \theta^{(t)})$ 近似等效为最大化 $\log p(\mathbf{X} | \theta)$.

6.3.1 Proof of the correctness

接下来，证明增大 $Q(\theta | \theta^{(t)})$ 就一定能增大 $\log p(\mathbf{X} | \theta)$.

由

$$\log p(\mathbf{X} | \theta)=\log p(\mathbf{X}, \mathbf{Z} | \theta)-\log p(\mathbf{Z} | \mathbf{X}, \theta)$$

有

$$\begin{aligned} \log p(\mathbf{X} | \theta) & =\left[\sum_{\mathbf{Z}} p(\mathbf{Z} | \mathbf{X}, \theta^{(t)})\right] \log p(\mathbf{X}, \mathbf{Z} | \theta)-\left[\sum_{\mathbf{Z}} p(\mathbf{Z} | \mathbf{X}, \theta^{(t)})\right] \log p(\mathbf{Z} | \mathbf{X}, \theta), \quad \text { because } \sum_{\mathbf{Z}} p(\mathbf{Z} | \mathbf{X}, \theta^{(t)})=1 \\ & =Q(\theta | \theta^{(t)})+H(\theta | \theta^{(t)}) \end{aligned}$$

其中 $H(\theta | \theta^{(t)}) = \mathrm{CE}\left(p(\mathbf{Z} | \mathbf{X}, \theta^{(t)}) | p(\mathbf{Z} | \mathbf{X}, \theta)\right)$.
令 $\theta = \theta^{(t)}$，得：

$$\log p(\mathbf{X} | \theta^{(t)})=Q(\theta^{(t)} | \theta^{(t)})+H(\theta^{(t)} | \theta^{(t)})$$

两式相减，得：

$$\log p(\mathbf{X} | \theta)-\log p(\mathbf{X} | \theta^{(t)})=Q(\theta | \theta^{(t)})-Q(\theta^{(t)} | \theta^{(t)})+H(\theta | \theta^{(t)})-H(\theta^{(t)} | \theta^{(t)})$$

由熵的性质知 $H\left(\theta | \theta^{(t)}\right) \geq H\left(\theta^{(t)} | \theta^{(t)}\right)$，从而

$$\log p(\mathbf{X} | \theta)-\log p(\mathbf{X} | \theta^{(t)}) \geq Q(\theta | \theta^{(t)})-Q(\theta^{(t)} | \theta^{(t)})$$

因此，优化过程中 $\log p(\mathbf{X} | \theta)$ 的增加量不小于 $Q(\theta | \theta^{(t)})$ 的增加量.

6.3.2 Mixture of Gaussians, EM, K-means

K-means 聚类的算法如下：

• 初始化 $k$ 个类别的中心点 $\mu_1, \mu_2, \dots, \mu_k$
• 对每个样本 $x_i$，找到距离最近的中心点 $z_i = \argmin_k |x_i - \mu_k|$
• 更新中心点坐标：$\mu_k = \mathbb{E}_{i:z_i=k}[x_i]$
• 重复以上两步操作

K-means 算法是 EM 算法的一种变体：其分布采样是确定性的、不优化方差、目标函数中丢弃了 $\log p(z_i)$.

参考资料

本文参考上海交通大学《机器学习》课程 CS3612 张拳石老师的 PDF 讲义整理。