机器学习：期末复习

本文为 SJTU-CS3612 机器学习课程的期末划重点.

要求说明：了解 < 知道 < 掌握 < 重点掌握.

Preliminary: Math

Covariance matrix

给定矩阵 $X_{n \times p}$，其中 $x_{ki}$ 表示第 $k$ 个样本的第 $i$ 维，那么其协方差矩阵(Covariance matrix) 为：$\Sigma = (c_{ij})_{p \times p}$，其中

$$c_{i j}=\mathbb{E}_k\left[\left(x_{k i}-\mathbb{E}_{k^{\prime}}\left[x_{k^\prime i}\right]\right)\left(x_{k j}-\mathbb{E}_{k^{\prime}}\left[x_{k^{\prime} j}\right]\right)\right]$$

对于两个随机向量 $X$ 和 $Y$，其协方差矩阵为：

$$\operatorname{Cov}(X, Y) = \mathbb{E}\left[(X - \mathbb{E}(X))(Y - \mathbb{E}(Y))^\top\right]$$

此处需要掌握协方差矩阵的定义和计算.

Matrix derivative

设 $Y = (y_i)_{m \times 1}, X = (x_j)_{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 = AX$，有

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

若 $Y = h(X)$ 且 $X = g(Z)$，那么由链式法则有

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

此处需要掌握基本的矩阵求导，会出现在反向传播推导及求梯度中.

Lecture 1: Linear Model

1.1 Linear regression

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

$$\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}$$

此处需要掌握线性模型的基本形式，并注意：

• 样本 $\mathbf{x}_i$ 默认是列向量；
• $\boldsymbol{\varepsilon}$ 是噪声项，而不是偏置项.

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{sigmoid}\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}}$$

此处需要掌握 $p_i$ 的表示以及 logit 和 sigmoid 函数的定义，即：

$$\operatorname{logit}\left(a\right) = \log \frac{a}{1-a}$$

$$\operatorname{sigmoid}\left(a\right) = \frac{e^a}{1+e^a} = \frac{1}{1+e^{-a}}$$

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

$$\operatorname{Pr}\left(y_i=y_i^* | X_i\right)=p_i^{y_i^*}\left(1-p_i\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 \operatorname{Pr}\left(y_i=y_i^* | X_i\right)=\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)$$

此处需要掌握 MLE 的连乘形式及取对数后的求和形式，会列式推导即可.

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}} = \operatorname{sigmoid}\left(y_i X_i^\top \beta\right)$$

此处需要掌握分类问题下 $y_i$ 的取值为 $\{+1, -1\}$，并会推导 $p(y_i)$ 的结果.

1.4 Perceptron

感知机可以表示为：

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

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

此处需要掌握感知机的基本形式.

1.5 Three models

机器学习模型分为三类：

• Generative models(生成式模型)：建模联合概率分布 $p_\theta(X, Y)$
• Discriminative models(判别式模型)：建模条件概率分布 $p_\theta(Y|X)$
• Descriptive models(描述式模型)：建模输入数据分布 $p_\theta(X)$

此处需要掌握三类模型的建模目标.

Softmax 函数用于计算分类为每一类的概率，即：

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

其中

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

此处需要掌握 softmax 函数的定义.

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)$ 是对每个训练样本的损失.

从最大化对数似然的角度，一种经典的损失函数设计是：

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

对于 logistic regression，其中 $y_i \in \{0, 1\}$，不难推出：

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

而对于 $y_i \in \{-1, 1\}$ 的分类问题，可以推出：

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

该损失被称为 logistic loss.

此处需要掌握将负对数似然作为损失函数的方法，以及了解 logistic loss 并不是 logistic regression 推出的损失函数.

MSE(Mean Square Error) loss 也是一种经典的损失函数：

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

Huber loss 是对 MSE 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}$$

而对于分类问题，几种经典的损失函数包括：

$$\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 }=\mathbf{1}\left(y_i X_i^{\top} \beta<0\right) \end{aligned}$$

此处需要掌握列出的几种损失函数的形式，其中 huber loss 了解即可.

1.8 Least Squares

对于线性模型 $Y = X\beta + \varepsilon$，最小二乘法的优化目标是：

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

可以解出：

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

此处需要掌握最小二乘回归的解的形式.

1.9 Kullback-Leibler divergence and cross entropy

对于一个分布 $p(x)$，其熵(Entropy) 的定义为：

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

对于两个分布 $p(x)$ 和 $q(x)$，其交叉熵(Cross entropy) 定义为：

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

定义 KL 散度(Kullback-Leibler divergence) 为交叉熵和熵的差，即：

$$\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)}$$

KL 散度衡量了两个分布之间的不相似度，即 KL 散度越小，两个分布的相似度越高.

此处需要重点掌握熵、交叉熵、KL 散度的定义.

1.10 Maximum likelihood

最大似然估计(MLE) 等价于最小化预测分布和真实数据分布的 KL 散度，即：

$$\max _\theta \sum_{i=1}^n \log p_\theta(y_i | X_i) \equiv \min _\theta \mathrm{KL}\left(P_{\text {data}}(y | X) | p_\theta(y | X)\right)$$

其中 $P_\text{data}$ 是真实数据分布.

此处需要掌握该结论即可，不要求公式及推导.

1.12 Stochastic gradient descent (SGD)

考虑使用梯度下降法(Gradient descent algorithm) 进行优化. 设模型参数为 $\theta$，先在所有样本上计算损失：

$$\mathscr{L}(\theta)=\frac{1}{n} \sum_{i=1}^n L_i(\theta)$$

再更新参数：

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

其中 $\eta_t$ 是第 $t$ 步时的学习率.

由于在所有样本上计算损失过于耗时，SGD(Stochastic gradient descent) 方法每次随机选取一个小批量(mini-batch)样本，在这些样本上计算损失并更新参数，即：

$$\theta_{t+1}=\theta_t-\eta_t \sum_{i \in \text {batch}\subset\text{allSamples }} L_i^{\prime}\left(\theta_t\right)$$

为了解决优化过程中的振荡问题(从而提高优化效率)，在 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$ 是动量.

此处需要掌握梯度下降法、SGD 及动量法.

1.13 Gradient of log-likelihood

对于判别式模型，设 softmax 层之前的网络输出为 $f_\theta(X)$，softmax 层的输出向量为 $p$，那么

$$\frac{\partial}{\partial \theta} \log p_\theta(y | X) =\frac{\partial}{\partial \theta} f_\theta(X)^{\top}(Y-p)$$

其中 $Y$ 是真实标签 $y$ 的 one-hot 形式. 由此可见，判别式模型从误差中学习(learn from errors).

对于描述式模型，设网络输出为 $f_\theta(X)$，那么

$$\frac{\partial}{\partial \theta} \log p_\theta(X) =\frac{\partial}{\partial \theta} f_\theta(X)-\mathbb{E}_\theta\left[\frac{\partial}{\partial \theta} f_\theta(X)\right]$$

可以理解为，模型的目标是：增大真实样本分数与从当前模型分布 $p_\theta$ (即”幻想“中的分布)中采样得到样本的平均分数之间的差距. 由此可见，描述式模型从梦中学习(learn from dream).

此处了解加粗的两句结论即可，不要求公式及推导.

特别地，对于 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$$

从而利用该梯度来更新 $\beta$：

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

此处需要掌握对数似然求梯度的推导过程.

1.14 Langevin

在梯度下降算法中，加入随机噪声扰动，有利于跳出局部最优解，这就是 Langevin dynamics. 以参数更新为例，引入噪声的更新公式变为：

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

此处需要知道：在梯度上加噪声可以防止陷入局部最小值.

1.17 Linear Discriminant Analysis (LDA)

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

设正类样本为 $\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)$

那么优化目标是最大化

$$S =\frac{\sigma_{\text {between }}^2}{\sigma_{\text {within }}^2} =\frac{\beta^{\top} S_B \beta}{\beta^{\top} S_W \beta}$$

其中

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

不妨设 $\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 乘子法，解得：

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

此处需要掌握 LDA 的目标函数和结论，不要求推导.

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$ 时分类正确，越大意味着对得越自信；当 $\gamma_i < 0$ 时分类错误，越小意味着错得越离谱.

对 $w$ 进行归一化，那么 margin 的定义变为：

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

此时，$\gamma_i$ 等于 $X_i$ 到分类面 $w^\top x+b = 0$ 的距离，且分类正确则距离为正，分类错误则距离为负.

此处需要掌握 margin 的定义、margin 值与分类正确的关系以及物理意义.

2.2 Margin classifier

由 SVM 的优化目标，可以解出：

$$w = \sum_{i:\alpha_i > 0} \alpha_i y_i X_i$$

通常将对应 $\alpha_i > 0$ 的样本 $X_i$ 称为支持向量，那么 $w$ 可以表示为支持向量的线性和.

此处需要掌握关于 $w$ 的重要结论，即可以表示为支持向量的线性和.

2.3 Kernel-based SVM

对于 SVM，其 inference 过程可以写为：

$$w^{\top} X_i+b = \sum_{j: \alpha_j>0} \alpha_j y_j\left\langle X_j, X_i\right\rangle+b$$

如果将 $x$ 换为 $\phi(x)$，那么有：

$$w^{\top} \phi\left(X_i\right)+b =\sum_{j: \alpha_j>0} \alpha_j y_j K\left(X_j, X_i\right)+b$$

其中

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

被称为核(Kernel). 这表明，我们只需要知道 $K(X_i, X_j)$，而不需要知道 $\phi(X_i)$，就可以得到分类值.

此处需要理解核函数的定义及作用，即：将 $w^{\top} \phi\left(X_i\right)+b$ 写成核函数的形式后，只需要得到 $K(X_i, X_j)$ 就可以得到分类值.

(Mercer 定理) $K$ 是核函数的充分必要条件是：

• 对称性：$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 核，即 Gaussian 核，其形式是：

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

此处需要掌握 RBF 核的定义.

2.5 With outliers

在不保证完全分类正确的情况下，SVM 的目标函数是：

$$\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 \underbrace{\max \left(0,1-y_i\left(w^{\top} X_i+b\right)\right)}_\text{Hinge loss}$$

其中，惩罚 $\Vert w \Vert$ 的目的是：最大化分类间隔，以增强泛化能力.

此处需要掌握 SVM 目标函数的两种形式，以及惩罚 $\Vert w \Vert$ 的目的.

由 KKT 条件，只有满足

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

的样本，才有

$$\alpha_i > 0$$

这包含了分类面上、分类面之间以及错误分类的样本. 其余样本均有 $\alpha_i = 0$.

此处需要掌握 $\alpha_i > 0$ 和 $\alpha_i = 0$ 对应的条件.

Lecture 3: Kernels and Regularized Learning

3.1 Over-fitting & under-fitting

过拟合(over-fitting) 是指模型在训练样本上表现很好，但在测试样本上泛化能力较差的现象.

此处需要掌握 over-fitting 的概念.

3.2 Ridge Regression

Ridge regression 引入惩罚项 $\lambda\|\beta\|^2$ ($\lambda > 0$)，损失函数是：

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

最终解得：

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

Ridge regression 的物理意义是：惩罚绝对值过大的参数权重，从而防止极少数特征维度主导预测结果，以提高模型的鲁棒性并防止过拟合.

此处需要掌握 Ridge regression 的损失函数、最终的解、物理意义.

3.3 Kernel Regression

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

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

从而在 inference 时，有：

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

此处需要掌握 $f(x)$ 在核函数形式下的表示公式.

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

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

不难证明，惩罚项 $c^{\top} K c = \|\beta\|^2$. 最终解得：

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

事实上，神经网络的输出就可以看作特征映射 $\phi(x)$，然后在该特征空间中进行分类. 而 weight decay 就是该方法神经网络中的应用，即对参数的 $L_2$ norm 进行惩罚，用于防止过拟合.

此处需要掌握 Kernel regression 的损失函数、最终的解，知道 Kernel regression 的本质是 Ridge regression 在核函数空间上的对应，知道 Kernel regression 在神经网络中的应用.

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$$

事实上，线性层和 ReLU 的级联网络，本质上是用分段线性函数进行拟合.

此处了解 Spline regression 的定义即可.

3.5 Lasso regression

Lasso regression 的目标是最小化

$$\ell(\beta) = \frac{1}{2}\|\mathbf{Y}-\mathbf{X} \beta\|_{\ell_2}^2+\lambda\|\beta\|_{\ell_1}$$

除 $p=1$ 情况外，$\beta$ 一般没有解析解.

Lasso regression 的物理意义是：学习稀疏的特征，使模型仅依赖少量真正重要的特征进行预测，从而提高模型的鲁棒性和泛化能力.

此处需要掌握 Lasso regression 的损失函数、是否存在解析解、物理意义.

当 $p = 1$ 时，Lasso regression 的解为：

$$\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$ 是最小二乘解. 可以看出，相比于最小二乘解，Lasso 会先将所有参数向 0 收缩(shrinkage)，再将较小的参数直接置零(selection).

此处需要掌握 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}$$

此处需要掌握 Lasso regression 的两种等价形式，不需要证明。

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}$$

此处了解 Lasso regression 的优化方法即可.

3.8 Bayesian regression

Ridge regression 可以从 Bayesian 公式的角度推导. 设 $\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$$

此处需要知道 Bayesian regression 的基本形式.

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$$

此处需要掌握加入了 Ridge loss 之后的解空间形式，不需要证明.

Lecture 4: Neural Networks

4.1 Neural networks

在神经网络中，非线性常常通过 ReLU 函数引入：

$$\operatorname{ReLU}(a) = \max(0, a)$$

此处需要掌握 ReLU 函数的定义.

对于一个简单的多层感知机(Multi-Layer Perceptron)，其结构一般是 (以三层感知机为例，FC 表示全连接层)：

$$x \to \mathrm{FC} \to \mathrm{ReLU/Sigmoid} \to \mathrm{FC} \to \mathrm{ReLU/Sigmoid} \to \mathrm{FC} \to \mathrm{Sigmoid/Softmax}$$

注意：

• 中间每层的激活函数可以选用 ReLU 或 Sigmoid，一般用 ReLU；
• 中间每层是 FC 和 ReLU/Sigmoid 交替出现，不可以连续两个 FC 或连续两个激活函数；
• 最后一层的分类头根据任务选择：Sigmoid 用于二分类，Softmax 用于多分类.

此处需要会设计浅层的神经网络，例如三层 Sigmoid 网络.

设一个多层感知机的结构如下：

• 第一层：$s = Wx + b$，其中 $x \in \mathbb{R}^{100}, s \in \mathbb{R}^{10}$
• 第二层：$h = \operatorname{ReLU}(s)$
• 第三层：$s' = W'h + b$，其中 $s'$ 是标量
• 第四层：$p(y=1) = \operatorname{sigmoid}(s')$，接着用 CrossEntropy Loss $L$ 训练两类别分类.

以该网络为例，推导反向传播公式：

首先，由于

$$L = -y \log p - (1-y) \log (1-p)$$

从而 $L$ 对 $p$ 的梯度为：

$$\frac{\partial L}{\partial p} = -\frac{y}{p} + \frac{1-y}{1-p}$$

又由于

$$\frac{\partial p}{\partial s'} = p(1-p)$$

$L$ 对 $s'$ 的梯度为：

$$\frac{\partial L}{\partial s'} = \frac{\partial L}{\partial p} \frac{\partial p}{\partial s'} = \left(-\frac{y}{p} + \frac{1-y}{1-p}\right)\cdot p(1-p) = p - y$$

接着，$L$ 对 $h$ 的梯度：

$$\frac{\partial L}{\partial h^\top} = \frac{\partial L}{\partial s'} \frac{\partial s'}{\partial h^\top} = (p-y) W'$$

$$\Longrightarrow \quad \frac{\partial L}{\partial h} = (W')^\top (p-y)$$

令 ReLU 函数的导数矩阵为：

$$f' = \frac{\partial h}{\partial s^\top} = \operatorname{diag}\left(\mathbf{1}(s_1 > 0), \dots, \mathbf{1}(s_{10} > 0)\right)$$

则 $L$ 对 $s$ 的梯度：

$$\frac{\partial L}{\partial s^\top} = \frac{\partial L}{\partial h^\top} \frac{\partial h}{\partial s^\top} = (p-y)W'f'$$

$$\Longrightarrow \quad \frac{\partial L}{\partial s} = f' (W')^\top (p-y)$$

设 $W_k$ 是 $W$ 的第 $k$ 行，$s_k$ 是 $s$ 的第 $k$ 个元素，则：

$$\frac{\partial L}{\partial W_k} = \frac{\partial L}{\partial s_k} \frac{\partial s_k}{\partial W_k} = \frac{\partial L}{\partial s_k} x^\top$$

从而 $L$ 对 $W$ 的梯度：

$$\frac{\partial L}{\partial W} = \frac{\partial L}{\partial s} x^\top = f' (W')^\top (p-y) x^\top$$

注意：

• 熟练基本的矩阵求导；
• 激活函数的导数均为对角阵，对于 Sigmoid 函数，每个元素是 $h_i(1-h_i)$；对于 ReLU 函数，每个元素是 $\mathbf{1}(s_i > 0)$.

此处需要掌握推导给定神经网络的反向传播，包含线性层、ReLU 层、Sigmoid 层、CrossEntropy.

4.2 Convolutional neural networks (CNN)

常见的 CNN 可能包含以下层：

• 卷积层(Conv)：
  • 输入与输出尺寸：设输入尺寸为 $H \times W \times C_{in}$，卷积核尺寸为 $R \times R \times C_{in}$，卷积核数量为 $C_{out}$，padding 为 $P$，stride 为 $S$，那么输出尺寸为 $H_{out} \times W_{out} \times C_{out}$，其中：

    $$H_{out} = \left\lfloor \frac{H - R + 2P}{S} + 1 \right\rfloor$$

    $$W_{out} = \left\lfloor \frac{W - R + 2P}{S} + 1 \right\rfloor$$

  • 超参数设置：
    • Kernel Size：多为 $3 \times 3$
    • Stride：即每一步移动几格，一般为 $1$ 或 $2$
    • Padding：即外侧补 0 的圈数，由期望的输出尺寸决定
  • 参数量：每个卷积核的参数量为 $R^2C_{in} + 1$，故总参数量为 $C_{out} (R^2C_{in} + 1)$（包含了 bias 项）
  • 计算量：每个输出元素的计算量为 $R^2 C_{in}$，故总计算量为 $H_{out}W_{out}C_{out} \cdot R^2C_{in}$
• Max/Average-Pooling 层：
  • 操作：设 Kernel Size 为 $R$，表示在每个 $R \times R$ 的区域内选取最大元素或求平均值
  • 输入输出尺寸：和卷积层类似(但通道数不变)，以 Kernel Size 和 Stride 均取 $2$ 为例，设输入尺寸为 $H \times W \times C$，则输出尺寸为 $H/2 \times W/2 \times C$
  • 参数量：0
  • 计算量：$H_{out}W_{out}C \cdot R^2$
• ReLU 层：
  • 输入输出尺寸：设输入尺寸为 $H \times W \times C$，由于逐元素运算，输出尺寸不变
  • 参数量：0
  • 计算量：$HWC$
• BatchNorm 层：
  • 输入输出尺寸：设输入尺寸为 $H \times W \times C$，输出尺寸不变
  • 参数量：在每个通道上有 $\gamma$ 和 $\beta$ 两个参数，故参数量为 $2C$
  • 计算量：$O(HWC)$
• Fully Connected 层：即 Linear 层
  • 输入输出尺寸：设输入尺寸为 $m$，输出尺寸为 $n$
  • 参数量：$(m+1)n$（包含了 bias 项）
  • 计算量：$mn$

关于卷积层应当注意：卷积核的尺寸是 $R \times R \times C_{in}$，而不是 $R \times R$，即每个输入通道使用不同的参数.

此处需要掌握 CNN 中输入输出张量尺寸、参数量及计算量的计算，以及 kernel size 和 padding 的设置.

对于一个简单的 CNN 网络，常见的结构一般是：

$$x \to \mathrm{Conv} \to \mathrm{ReLU} \to \mathrm{MaxPooling} \to \mathrm{Conv} \to \mathrm{ReLU} \to \mathrm{MaxPooling} \to \mathrm{FC} \to \mathrm{ReLU} \to \mathrm{FC} \to \mathrm{ReLU} \to \mathrm{FC} \to \mathrm{Softmax} \to \mathrm{CrossEntropy}$$

注意：

• FC 层之间要加 ReLU 层；
• Softmax 之前不可以加 ReLU 层；
• 不可以在 ReLU $\to$ MaxPooling 之后直接加 ReLU 层；
• 不可以连续两个卷积层 / FC 层 / ReLU 层；
• 不可以在卷积层后直接到 FC 层；
• 残差网络连接处之前不可以直接加 ReLU 层.

此处需要会设计简单的 CNN，注意以上的规则.

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$.

此处需要掌握 Batch normalization 的公式.

残差网络的基本结构是：

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

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

此处需要掌握残差网络的基本形式，以及简单残差网络的设计. 其中 $F$ 的结构不需要记忆，合理即可.

4.3 Recurrent neural networks

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，即短期记忆；$f$ 是 Sigmoid 函数.

• Forget gate：决定旧记忆 $c_{t-1}$ 保留多少
• Input gate：决定当前新信息 $\Delta c_t$ 写入多少
• Output gate：决定长期记忆 $c_t$ 输出多少给外界

此处需要知道每个门控函数的意义，不需要记忆 LSTM 的公式.

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}$$

• Update gate：决定保留多少旧记忆 $h_{t-1}$，写入多少新记忆 $\tilde{h}_t$
• Reset gate：决定计算新信息 $\tilde{h}_t$ 时参考多少历史信息 $h_{t-1}$

此处需要知道每个门控函数的意义，不需要记忆 GRU 的公式.

4.4 Generator and GAN

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

GAN 的训练目标是：

$$\min _G \max _D ~V(D, G)= \mathbb{E}_{P_{\text {data }}}[\log D(X)]+\mathbb{E}_{h \sim p(h)}[\log (1-D(G(h)))]$$

可以证明，该目标的本质是让生成分布 $p_\theta$ 尽可能接近真实数据分布 $P_\text{data}$，即最小化二者之间的 JSD(Jensen-Shannon Divergence).

此处需要掌握 GAN 的训练目标，知道本质是在最小化 JS 散度.

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(0, I)$. 第一项是 $q_\phi(h|X)$ 和 $N(0, I)$ 之间的 KL 散度，把 $h$ 的隐空间限制为标准正态分布，用于防止过拟合及便于作为生成器；第二项是 $p_\theta(X|h)$ 的重建误差，实质上是 $X$ 和 $p_\theta(X|h)$ 之间的平方损失.

可以证明，这等效于最大化

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

其中第一项是重建数据对真实数据的拟合，用于提高模型对真实数据的生成概率；第二项是生成的隐空间和 $N(0, I)$ 之间的 KL 散度，用于限制隐空间的结构.

此处需要掌握 VAE 的损失函数、ELBO 及其意义.

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

6.1 Principle component analysis (PCA)

PCA 的定义是：找到数据方差最大的几个主方向，并将数据投影到这些方向上实现降维.

设样本矩阵为 $\mathbf{X} \in \mathbb{R}^{n \times p}$，PCA 的计算步骤是：

• 第一步：去中心化，将样本点每个维度的均值平移到 0；
• 第二步：计算协方差矩阵，即

  $$\mathbf{\Sigma} = \frac{1}{n} \mathbf{X}^\top \mathbf{X}$$

• 第三步：求特征值与特征向量，即从

  $$\mathbf{\Sigma} \mathbf{w} = \lambda \mathbf{w}$$

  中求解特征值和特征向量. 设求得的特征值 $\lambda_1 > \lambda_2 > \dots > \lambda_p$，对应特征向量 $\mathbf{w}_{(1)}, \mathbf{w}_{(2)}, \dots, \mathbf{w}_{(p)}$，那么第一、第二、第三主成分分别是 $\mathbf{w}_{(1)}$、$\mathbf{w}_{(2)}$ 和 $\mathbf{w}_{(3)}$.

也就是说，$\mathbf{X}$ 的第 $k$ 主方向就是 $\mathbf{X}^\top \mathbf{X}$ 的第 $k$ 大特征值对应的特征向量.

如果要保留前 $k$ 个主成分，令

$$\mathbf{W} = [\mathbf{w}_{(1)}, \mathbf{w}_{(2)}, \dots, \mathbf{w}_{(k)}]$$

那么通过

$$\mathbf{T}=\mathbf{X W} \in \mathbb{R}^{n \times k}$$

就可以实现数据降维.

此处需要重点掌握 PCA 的定义和计算，以及降维方法.

6.2 Stochastic Neighbor Embedding (t-SNE)

$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)$$

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

此处需要掌握 t-SNE 的优化目标.

为了在降维时保留局部线性关系，我们将 $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$$

此处需要掌握 LLE 的优化目标.

6.3 The Expectation Maximization (EM) Algorithm

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

$$\begin{aligned} \max_\theta ~p(\mathbf{X} | \theta) & = \prod_{i=1}^n p(x_i | \theta) \\ & = \prod_{i=1}^n \sum_{z_i = 1}^k p(x_i, z_i | \theta) \\ & = \prod_{i=1}^n \sum_{z_i = 1}^k p(z_i) p(x_i | z_i, \theta) \end{aligned}$$

实际的求解过程分为两步：

• Expectation step (E step):

$$\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)] \\ &= \sum_{i=1}^n \mathbb{E}_{z_i \sim p(z_i | x_i, \theta^{(t)})}[\log p(x_i, z_i | \theta)] \\ &= \sum_{i=1}^n \sum_{z_i=1}^k p(z_i | x_i, \theta^{(t)}) \log p(x_i, z_i | \theta) \\ &= \sum_{i=1}^n \sum_{z_i=1}^k p(z_i | x_i, \theta^{(t)}) \left[ \log p(z_i) + \log p(x_i | z_i, \theta)\right] \end{aligned}$$

• Maximization step (M step):

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

此处需要掌握 EM 算法的优化目标(包含特殊分布下)，以及 $Q$ 函数的公式并会对 $\theta$ 求梯度.

希望大家考试取得好成绩！

参考资料

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