机器学习：笔记整理

本文为 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_1 \\ \beta_2 \\ \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_{i1}, x_{i2}, \dots, x_{ip}, y_i\}_{i=1}^n$，其中标签 $y_i \in \{0, 1\}$。设

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

令

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

设每个样本的真实标签为 $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}}$$

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

$$\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\}$，那么可以认为

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

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

1. 先考虑增大 $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. 再考虑增大 $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(Y|X)$。设输入为 $X$，网络的输出为 $K$ 维向量 $f_\theta(X)$。经过 Softmax 层，有

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

Descriptive models

描述式模型建模输入数据分布 $p_\theta(X)$。可以计算为：

$$p_\theta(X)=\frac{\exp(f_\theta(X))}{\int \exp (f_\theta(x)) \mathrm{d} x}$$

1.6 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[\log \operatorname{Pr}(y_i | X_i, \beta)-\text {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

1.7 Least Squares

1.8 Kullback-Leibler divergence and cross entropy

1.9 Maximum likelihood

1.10 Kullback-Leibler of conditionals

1.11 Stochastic gradient descent (SGD)

1.12 Gradient of log-likelihood

1.13 Langevin

1.14 Non-linear and non-parametric functions

1.15 Kernel Regression

1.16 Linear Discriminant Analysis (LDA)

Lecture 2: Support Vector Machines

Lecture 3: Kernels and Regularized Learning

Lecture 4: Neural Networks

Lecture 5: Reinforcement Learning

Lecture 6: Visualization, EM Algorithm and Shapley Values

参考资料

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