经典机器学习算法推导汇总

目录

• 目录
• 前言
• MLE/MAP
  • 最大似然估计(MLE)
  • 最大后验概率估计(MAP)
• 线性回归/逻辑斯蒂回归
  • 线性回归
  • 逻辑斯蒂回归(LR)
• 朴素贝叶斯
• PCA/LDA
  • PCA
    • 计算步骤
    • 证明
  • LDA
    • 计算步骤
    • 证明
• EM/GMM
  • EM算法
  • GMM模型
• SVM
  • KKT条件
  • 核技巧
  • 分类问题
    • 线性可分
    • 线性不可分
  • 回归问题
  • 求解优化问题
• 聚类
  • 距离度量
  • KMeans
  • Spectral
• 决策树
  • ID3
  • C4.5
  • CART
  • RF

前言

本文只做复习使用，只给出关键算法描述和证明。

MLE/MAP

给定$N$个样本对$\{(X^{(i)}, y^{(i)}), i = 1, \cdots, N\}$，其中$y \in \{C_k, k = 1, \cdots, K\}$，要求估计参数模型$P(X | \theta)$的参数$\theta$，使之最能描述给定数据分布。

最大似然估计(MLE)

$$\begin{aligned} 优化目标：& \hat{\theta} = \arg \max P(D | \theta) \\ 定义：& L(D | \theta) = P(D | \theta) = \prod_i P(X^{(i)} | \theta) \\ 取对数：& \log L(D | \theta) = \sum_i \log P(X^{(i)} | \theta) \\ 求取极值：& \frac{\partial}{\partial \theta} \log L(D | \theta) = 0 \Rightarrow \hat{\theta} \end{aligned}$$

最大后验概率估计(MAP)

$$\begin{aligned} 优化目标：& \hat{\theta} = \arg \max P(\theta | D) \\ 其中：& P(\theta | D) = \frac{P(D | \theta) P(\theta)}{P(D)} \\ & P(\theta)为给定的参数先验概率分布 \\ 定义：& L(\theta | D) = P(D | \theta) P(\theta) = \prod_i P(X^{(i)} | \theta) \cdot P(\theta) \\ 取对数：& \log L(\theta | D) = \sum_i \log P(X^{(i)} | \theta) + \log P(\theta) \\ 求取极值：& \frac{\partial}{\partial \theta} \log L(\theta | D) = 0 \Rightarrow \hat{\theta} \end{aligned}$$

线性回归/逻辑斯蒂回归

给定$N$个样本对$\{(X^{(i)}, y^{(i)}), i = 1, \cdots, N\}$，记样本矩阵$X_{N \times n}$。

线性回归

$$\begin{aligned} 标签信息：& y \in \mathcal{R}^1， 定义模型：\hat{y}_{1\times 1} = w_{n \times 1}^T x_{n \times 1} + b \\ 增广后：& \hat{y}_{1\times 1} = w_{n \times 1}^T x_{n \times 1} \begin{cases} w_1 = b \\ x_1 = 1 \end{cases} \\ MSE作为损失，则总体损失：& L(\hat{y}, y) = \frac{1}{N} \sum_{i=1}^N \frac{1}{2} (\hat{y}^{(i)} - y^{(i)})^2 \\ 求取梯度：& \frac{\partial L}{\partial w_j} = \frac{1}{N} \sum_{i=1}^N (\hat{y}^{(i)} - y^{(i)}) \frac{\partial \hat{y}^{(i)}}{\partial w_j} = \frac{1}{N} \sum_{i=1}^N (\hat{y}^{(i)} - y^{(i)}) x^{(i)}_j \Rightarrow \\ 梯度下降：& w_j := w_j - \alpha \frac{\partial L}{\partial w_j} \end{aligned}$$

若描述为矩阵

$$\begin{aligned} \left.\begin{aligned} & 标签信息 Y \in R^{N} \\ 定义模型：& \hat{Y}_{N \times 1} = X_{N \times (n + 1)} w_{(n + 1) \times 1} \\ 总体损失：& L(\hat{Y}, Y) = \frac{1}{N} \cdot \frac{1}{2} || \hat{Y} - Y ||_2^2 = \frac{1}{N} \cdot \frac{1}{2} (\hat{Y} - Y)^T(\hat{Y} - Y) \end{aligned}\right\} \Rightarrow \\ L(\hat{Y}, Y) = \frac{1}{2 N} (w^T X^T X w - 2 Y^T X w + Y^T Y) \\ 求取梯度： \frac{\partial L}{\partial w} = \frac{1}{\cancel{2} N} (\cancel{2} X^T X w - \cancel{2} X^T Y) = 0 \Rightarrow \\ \begin{cases} 梯度下降：& w := w - \alpha \frac{\partial L}{\partial w} \\ 解析解：& \hat{w}^* = \underbrace{(X^T X + \lambda I)^{-1} X^T}_{X^+} Y \end{cases} \end{aligned}$$

逻辑斯蒂回归(LR)

$$\begin{aligned} 标签信息： y \in \{0, 1\} \\ 定义模型：& \begin{cases} \hat{y} = \sigma(z) \\ z = w^T X + b \end{cases} \\ & 其中 \sigma(z) = \frac{1}{1 + \exp(-z)} \\ 样本X服从0-1分布：& P(X) = (1 - \hat{y})^{1 - y} (\hat{y})^{y} (\hat{y}^{(i)}为直接待估参数) \\ MLE：& L(D | w) = \prod_i P(X^{(i)}) \Rightarrow \log L(D | w) = \sum_i \log P(X^{(i)}) \\ 优化目标：& \hat{w} = \arg \max L(D | w) = \arg \max \log L(D | w) \\ 求取极值：& \begin{aligned} \frac{\partial L}{\partial w_j} & = \frac{\partial}{\partial w_j} \sum_i \log P(X^{(i)}) \\ & = \frac{\partial}{\partial w_j} \sum_i \log (1 - \hat{y}^{(i)})^{1 - y^{(i)}} (\hat{y}^{(i)})^{y^{(i)}} \\ & = \frac{\partial}{\partial w_j} \sum_i (1 - y^{(i)}) \log (1 - \hat{y}^{(i)}) + \frac{\partial}{\partial w_j} \sum_i y^{(i)} \log \hat{y}^{(i)} \\ & = \sum_i (1 - y^{(i)}) \frac{1}{1 - \hat{y}^{(i)}} (- \frac{\partial y^{(i)}}{\partial w_j}) + \sum_i y^{(i)} \frac{1}{\hat{y}^{(i)}} (\frac{\partial y^{(i)}}{\partial w_j}) \end{aligned} \\ 其中：& \frac{\partial y^{(i)}}{\partial w_j} = \sigma'(z^{(i)}) \frac{\partial z^{(i)}}{\partial w_j} = \sigma(z^{(i)}) (1 - \sigma(z^{(i)})) x^{(i)}_j \Rightarrow \\ & \frac{\partial L}{\partial w_j} = \sum_i - (1 - \bcancel{y^{(i)}}) \frac{1}{\cancel{1 - \hat{y}^{(i)}}} \sigma(z^{(i)}) \cancel{(1 - \sigma(z^{(i)}))} x^{(i)}_j + \\ & \sum_i y^{(i)} \frac{1}{\cancel{\hat{y}^{(i)}}} \cancel{\sigma(z^{(i)})} (1 - \bcancel{\sigma(z^{(i)})}) x^{(i)}_j = \sum_i (y^{(i)} - \hat{y}^{(i)}) x^{(i)}_j \Rightarrow \\ 梯度下降：& w_j := w_j - \alpha \frac{\partial L}{\partial w_j} \end{aligned}$$

朴素贝叶斯

给定$N$个样本对$\{(X^{(i)}, y^{(i)}), i = 1, \cdots, N\}$，其中$y \in \{C_k, k = 1, \cdots, K\}$。

$$\begin{aligned} 定义模型为条件概率分布：& P(Y | X) \\ 由贝叶斯公式：& P(Y | X) = \frac{P(X | Y) P(Y)}{P(X)} \\ 称：& \begin{cases} 后验概率：& P(Y | X) \\ 似然函数：& P(X | Y) = \prod_{j=1}^n P(X_j | Y) (朴素贝叶斯)\\ 先验概率：& P(Y) \\ 证据因子：& P(X) = \sum_k P(X | Y = C_k) P(Y = C_k) \end{cases} \\ \hat{y} & = \max_k P(X | Y = C_k) P(Y = C_k) \\ & = \max_k \prod_{j=1}^n P(X_j | Y = C_k) P(Y = C_k) \end{aligned}$$

PCA/LDA

PCA

给定包含$M$个样本的$N$维数据集$\{X_{N \times 1}^{(i)}, i = 1, \cdots, M\}$构成样本矩阵$X_{N \times M} = \begin{bmatrix}X^{(1)} & X^{(2)} & \cdots X^{(M)}\end{bmatrix}$，现希望求取主分量$\beta_k, k = 1, \cdots, K$使得数据投影在各主分量上的散布最大/方差最大。

计算步骤

1. 计算维度间的协方差矩阵$\Sigma_{N \times N} = \frac{1}{M} \tilde{X} \tilde{X}^T$，其中$\tilde{X}^{(i)} = X^{(i)} - \overline{X}, \overline{X} = \frac{1}{M} \sum_{i=1}^{M} X^{(i)}$；
2. 求矩阵$\Sigma$的特征值分解，即$\Sigma \beta_k = \lambda_k \beta_k$；
3. 将特征对$(\lambda_k, \beta_k)$按特征值$\lambda_k$降序排序后，选取前$K$个主分量作为投影轴构成投影矩阵$B_{N \times K}$；
4. 投影：$S_{K \times M} = B_{N \times K}^T X_{N \times M}$；重建；$\hat{X} = B_{N \times K} S_{K \times M}$。

证明

1. 第$1$主成分
   优化目标为

   $$\begin{aligned} \beta_1 & = \arg \max ||S_1||_2^2 \\ s.t. & \quad ||\beta_1||_2^2 = 1 \end{aligned}$$

   那么

   $$\begin{aligned} \left. \begin{aligned} \left. \begin{aligned} ||S_1||_2^2 & = S_1^T S_1 \\ S_1 & = X^T \beta_1 \end{aligned} \right\} \Rightarrow ||S_1||_2^2 = \beta_1^T \underbrace{X X^T}_C \beta_1 \\ C = X X^T = W \Lambda W^T \end{aligned} \right\} \Rightarrow \\ \left. \begin{aligned} ||S_1||_2^2 = \beta_1^T W \Lambda \underbrace{W^T \beta_1}_{\alpha_1} = \sum_{i=1}^N \lambda_i \alpha_{1i} \leq \lambda_1 \sum_{i=1}^N \alpha_{1i} \\ \beta_1^T \beta_1 = \alpha_1^T W^T W \alpha = \alpha_1^T \alpha = \sum_{i=1}^N \alpha_{1i} = 1(单位约束) \end{aligned} \right\} \Rightarrow \\ ||S_1||_2^2 \leq \lambda_1 \quad 为使||S_1||_2^2极大化，取 \\ \begin{cases} \alpha_{11} = 1\\ \alpha_{1i} = 0, i = 2, 3, \cdots, N \end{cases} \Rightarrow \beta_1 = W \alpha_1 = w_1 \end{aligned}$$

2. 第$r(r>1)$主成分
   优化目标为

   $$\begin{aligned} \beta_r & = \arg \max ||S_r||_2^2 \\ s.t. & \quad \beta_r^T \beta_i = 0, i = 1, \cdots, r - 1 \\ & ||\beta_r||_2^2 = 1 \end{aligned}$$

   那么

   $$\begin{aligned} \left. \begin{aligned} \left. \begin{aligned} ||S_r||_2^2 = S_r^T S_r \\ S_r = X^T \beta_r \end{aligned} \right\} \Rightarrow ||S_r||_2^2 = \beta_r^T \underbrace{X X^T}_C \beta_r \\ C = X X^T = W \Lambda W^T \end{aligned} \right\} \Rightarrow \\ \left. \begin{aligned} ||S_r||_2^2 = \beta_r^T W \Lambda \underbrace{W^T \beta_r}_{\alpha_r} = \sum_{i=1}^N \lambda_i \alpha_{ri} \\ \beta_r^T \beta_i =(W \alpha_r)^T (w_i) = \alpha_{ri} = 0, i \neq r (正交约束) \\ \beta_r^T \beta_r = \alpha_r^T W^T W \alpha = \alpha_r^T \alpha = \sum_{i=1}^N \alpha_{1i} = 1(单位约束) \end{aligned} \right\} \Rightarrow \\ ||S_r||_2^2 = \lambda_r \alpha_{rr} \quad 为使||S_r||_2^2极大化，取 \\ \begin{cases} \alpha_{rr} = 1 \\ \alpha_{ri} = 0, i = \neq r \end{cases} \Rightarrow \beta_r = W \alpha_r = w_r \end{aligned}$$

LDA

给定$N$个样本对$\{(X^{(i)}, y^{(i)}), i = 1, \cdots, N\}$，其中$y \in \{C_k, k = 1, \cdots, K\}$，记样本矩阵$X_{N \times n}$。现利用类别信息求取投影主轴$u$，使得投影后类内散步小，类间散步大。

定义：

$$\begin{cases} 总样本均值： & \mu = \frac{1}{N} \sum_{i=1}^N X^{(i)} \\ 类别样本均值： & \mu_k = \frac{1}{N_k} \sum_{i=1}^{N_k} X^{(i)}, y^{(i)} = C_k \\ 类内离差阵： & S_{W, n \times n} = \sum_k \frac{N_k}{N} \left[ \frac{1}{N_k} \sum_i (X^{(i)} - \mu_k) (X^{(i)} - \mu_k)^T \right] \\ 类内离差阵： & S_{B, n \times n} = \sum_k \frac{N_k}{N} \left[ (\mu_k - \mu) (\mu_k - \mu)^T \right] \\ \end{cases}$$

计算步骤

1. 计算类内/类间离差阵$S_W/S_B$；
2. 计算矩阵$S_W^{-1}S_B$的特征对$(\lambda_i, u_i)$；
3. 将特征对按特征值降序排序，选取最大的特征值对应特征向量作为投影主轴，构成投影矩阵$U_{n \times m}$；
4. 投影到主轴上，$\hat{X}_{N \times m} = X_{N \times n} U_{n \times m}$。

证明

$$\begin{aligned} 将样本点X^{(i)}投影到第一主轴u_1上有 \quad \tilde{X}^{(i)} = u_1^T X^{(i)} \quad 在投影空间有 \\ \left.\begin{aligned} \tilde{X}^{(i)} & = u_1^T X^{(i)}, \tilde{\mu} = u_1^T \mu, \tilde{\mu}_k = u_1^T \mu_k \\ \tilde{S_W}_{1 \times 1} & = \sum_k \frac{N_k}{N} \left[ \frac{1}{N_k} \sum_i (\tilde{X}^{(i)} - \tilde{\mu}_k) (\tilde{X}^{(i)} - \tilde{\mu}_k)^T \right] \\ \tilde{S_B}_{1 \times 1} & = \sum_k \frac{N_k}{N} \left[ (\tilde{\mu}_k - \tilde{\mu}) (\tilde{\mu}_k - \tilde{\mu})^T \right] \end{aligned}\right\} \Rightarrow \begin{cases} \tilde{S_W} = u_1^T S_W u_1 \\ \tilde{S_B} = u_1^T S_B u_1 \end{cases} \\ 定义优化目标为：u_1 = \arg \min \frac{\tilde{S_W}}{\tilde{S_B}} = \arg \min \frac{u_1^T S_W u_1}{u_1^T S_B u_1} \\ 求取极值：\frac{\partial}{\partial u_1} \frac{u_1^T S_W u_1}{u_1^T S_B u_1} = \frac{(u_1^T S_B u_1)(2 S_W u_1) - (u_1^T S_W u_1)(2 S_B u_1)}{(u_1^T S_B u_1)^2} = 0 \Rightarrow \\ S_B u_1 = \underbrace{\frac{u_1^T S_B u_1}{u_1^T S_W u_1}}_{\lambda_1} S_W u_1，记\lambda_1 = \frac{u_1^T S_B u_1}{u_1^T S_W u_1} \end{aligned}$$

EM/GMM

EM算法

给定包含$N$对样本数据$\{(X^{(i)}, y^{(i)}), i = 1, \cdots, N\}$。设分类模型为概率模型$P(X | \theta)$，其中$\theta$待估。该模型包含$K$种隐藏变量状态$\{w_k, k = 1, \cdots, K\}$。那么证明过程总结如下

$$\begin{aligned} MLE \Rightarrow L(D | \theta) = \prod_i P(X^{(i)} | \theta) \Rightarrow \log L(D | \theta) = \sum_i \log P(X^{(i)} | \theta) \\ \Rightarrow 优化目标：\theta^{(t + 1)} = \arg \max \log L(D | \theta) \\ \\ \left. \begin{aligned} P(X^{(i)} | \theta) = \sum_k P(X^{(i)}, w^{(i)}_k | \theta) (引入隐变量w_k) \\ \frac{P(w^{(i)}_k | \theta^{(t)})}{P(w^{(i)}_k | \theta^{(t)})} = 1 (引入迭代变量\theta^{(t)}) \end{aligned} \right\} \Rightarrow \\ \left. \begin{aligned} \log L(D | \theta) = \sum_i \log \sum_k P(X^{(i)}, w^{(i)}_k | \theta) \frac{P(w^{(i)}_k | \theta^{(t)})}{P(w^{(i)}_k | \theta^{(t)})} \\ \begin{cases} \varphi(\cdot)下凸 \\ \sum_i w_i = 1 \end{cases} \Rightarrow \varphi(\sum_i w_i x_i) \leq \sum_i w_i \varphi(x_i) (Jensen不等式) \end{aligned} \right\} \Rightarrow \\ \log L(D | \theta) = \sum_i \sum_k P(w^{(i)}_k | \theta^{(t)}) \log \frac{P(X^{(i)}, w^{(i)}_k | \theta)}{P(w^{(i)}_k | \theta^{(t)})} \\ = \underbrace{ \sum_i \sum_k P(w^{(i)}_k | \theta^{(t)}) \log P(X^{(i)}, w^{(i)}_k | \theta)}_{E_w\left[ \log P(X^{(i)}, w^{(i)}_k | \theta) \right]} \\ \underbrace{- \sum_i \sum_k P(w^{(i)}_k | \theta^{(t)}) \log P(w^{(i)}_k | \theta^{(t)})}_{H\left[ P(w^{(i)}_k | \theta^{(t)}) \right]} \\ 记 \quad Q(\theta | \theta^{(t)}) = E_w\left[ \log P(X^{(i)}, w^{(i)}_k | \theta) \right] \\ \Rightarrow 优化目标：\theta^{(t + 1)} = \arg \max Q(\theta | \theta^{(t)}) \\ 对Q(\theta | \theta^{(t)})求极值求解\theta^{(t + 1)}。 \end{aligned}$$

GMM模型

高斯混合模型，具有如下概率形式

$$P(X | \mu, \Sigma) = \sum_{k=1}^K \pi_k N(X | \mu_k, \Sigma_k)$$

其中

$$\begin{cases} \sum_k \pi_k = 1 \\ N(X | \mu_k, \Sigma_k) = \frac{1}{(2\pi)^{d/2}|\Sigma|^{1/2}} \exp \left[ - \frac{1}{2} (X - \mu_k)^T \Sigma_k^{-1} (X - \mu_k) \right] \end{cases}$$

用EM算法对参数进行估计

$$\begin{aligned} \left. \begin{aligned} Q(\theta|\theta^{(t)}) = \sum_i \sum_k P(w_k^{(i)}|\theta^{(t)}) \log \underbrace{P(x^{(i)} | w_k^{(i)}, \theta) P(w_k^{(i)} | \theta)}_{P(x^{(i)}, w_k^{(i)} | \theta)} \\ \begin{cases} P(w_k^{(i)}|\theta^{(t)}) = \frac{\pi_k^{(t)} N(x^{(i)}|\mu_k^{(t)}, \Sigma_k^{(t)})} {\sum_j \pi_j^{(t)} N(x^{(i)}|\mu_j^{(t)}, \Sigma_j^{(t)})} = \gamma^{(i)(t)}_k \\ P(x^{(i)} | w_k^{(i)}, \theta) = N(x^{(i)}|\mu_k, \Sigma_k) \\ P(w_k^{(i)} | \theta) = \pi_k \end{cases} \end{aligned} \right\} \Rightarrow \\ Q(\theta|\theta^{(t)}) = \sum_i \sum_k \gamma^{(i)(t)}_k \log \pi_k N(x^{(i)}|\mu_k, \Sigma_k) \\ 求解Q函数极值 \Rightarrow \begin{cases} \mu_k^{(t+1)} = \frac{\sum_i \gamma^{(i)(t)}_k x^{(i)}}{\sum_i \gamma^{(i)(t)}_k} \\ \Sigma_k^{(t+1)} = \frac{\sum_i \gamma^{(i)(t)}_k (x^{(i)} - \mu_k) (x^{(i)} - \mu_k)^T}{\sum_i \gamma^{(i)(t)}_k} \\ \pi_k^{(t+1)} = \frac{\sum_i \gamma^{(i)(t)}_k}{N} \end{cases} \end{aligned}$$

SVM

KKT条件

$$\begin{aligned} \left.\begin{aligned} w = \arg \min f(w) \\ s.t. \quad h_j(w) = 0, j = 1, \cdots, m \\ g_j(w) \leq 0, j = 1, \cdots, p \end{aligned}\right\} \Rightarrow \\ L(w, \lambda, \mu) = f(w) + \sum_j \lambda_j h_j(w) + \sum_j \mu_j \left(g_j(w) + \epsilon^2 \right) \\ \Rightarrow \begin{cases} \frac{\partial}{\partial w} f(w) + \sum_j \lambda_j \frac{\partial}{\partial w} h_j(w) + \sum_j \mu_j \frac{\partial}{\partial w} g_j(w) = 0 \\ h_j(w) = 0, j = 1, \cdots, m \\ \left.\begin{aligned} \mu_j g_j(w) = 0 \\ \mu_j \geq 0 \end{aligned} \right\} j = 1, \cdots, p \end{cases} \end{aligned}$$

核技巧

设某函数$\Phi(x)$，可将$x$从$n$维空间映射到$n'$维空间，定义两个向量的核函数为$\kappa(x_i, x_j) = \Phi(x_i)^T \Phi(x_j)$，常用和函数有

$$\begin{cases} 线性核：& \kappa(x_i, x_j) = x_i^T x_j \\ 多项式核：& \kappa(x_i, x_j) = (\gamma x_i^T x_j + c)^n \\ sigmoid核：& \kappa(x_i, x_j) = \tanh (\gamma x_i^T x_j + c) \\ 拉普拉斯核：& \kappa(x_i, x_j) = \exp (- \gamma \frac{||x_i - x_j||}{\sigma}) \\ 高斯核：& \kappa(x_i, x_j) = \exp (- \gamma \frac{||x_i - x_j||^2}{2 \sigma^2}) \end{cases}$$

分类问题

给定$N$对样本$\{(X^{(i)}, y^{(i)}), i = 1, \cdots, N\}, y \in \{-1, 1\}$，求取超平面$w^T \Phi(x) + b = 0$使样本点落在该超平面两侧。

线性可分

$$\begin{aligned} \left.\begin{aligned} 记r_{+/-}为分类平面到支持向量x_{+/-}的距离，则r = r_+ + r_-，且r_{+/-} = \frac{|w^T \Phi(x_{+/-}) + b|}{||w||} = \frac{1}{||w||} \\ 正/负样本分别满足\begin{cases} w^T \Phi(x^{(i)}) + b > 1 & y^{(i)} > 0 \\ w^T \Phi(x^{(i)}) + b < -1 & y^{(i)} < 0 \end{cases} \Rightarrow y^{(i)} [w^T \Phi(x^{(i)}) + b] \geq 1(包括支持向量) \end{aligned}\right\} \Rightarrow \\ \end{aligned}$$

$$\begin{aligned} 优化目标：& \begin{aligned} w, b & = \arg \max r \\ s.t. & \quad y^{(i)} [w^T \Phi(x^{(i)}) + b] \geq 1 \end{aligned} \\ 即： & \begin{aligned} w, b & = \arg \min \frac{1}{2} ||w||^2 \\ s.t. & \quad y^{(i)} [w^T \Phi(x^{(i)}) + b] \geq 1 \end{aligned} \end{aligned}$$

线性不可分

在线性可分支持向量机基础上，对每个样本添加松弛变量$\epsilon^{(i)}$

$$\begin{aligned} 优化目标：\begin{aligned} w, b & = \arg \min \left[ \frac{1}{2} ||w||^2 + C \sum_i \epsilon^{(i)} \right] \\ s.t. & \quad y^{(i)} [w^T \Phi(x^{(i)}) + b] \geq 1 - \epsilon^{(i)} \\ & \epsilon^{(i)} \geq 0 \end{aligned} \end{aligned}$$

回归问题

给定$N$对样本$\{(X^{(i)}, y^{(i)}), i = 1, \cdots, N\}, y \in R$，求回归模型$\hat{y} = w^T \Phi(x) + b$，使得每个样本尽量拟合到该模型上，定义损失为

$$L^{(i)} = \begin{cases} |y^{(i)} - w^T \Phi(x^{(i)}) - b| - \epsilon & |y^{(i)} - w^T \Phi(x^{(i)}) - b| > \epsilon \\ 0 & otherwise \end{cases}$$

求解优化问题

以线性可分支持向量机为例，讲解参数$w， b$的优化方法

$$优化目标：\begin{aligned} w, b & = \arg \min \frac{1}{2} ||w||^2 \\ s.t. & \quad y^{(i)} [w^T \Phi(x^{(i)}) + b] \geq 1 \end{aligned}$$

$$\begin{aligned} 拉格朗日函数：L(w, b, \mu) = \frac{1}{2} ||w||^2 + \sum_i \mu^{(i)} \left\{ 1 - y^{(i)} [w^T \Phi(x^{(i)}) + b] \right\} \\ w, b, \mu = \arg \min_{w, b} \max_{\mu} L(w, b, \mu) \Rightarrow w, b, \mu = \arg \max_{\mu} \min_{w, b} L(w, b, \mu)(对偶问题) \\ 求解极值：\begin{cases} \begin{aligned} \frac{\partial}{\partial w_j} L(w, b, \mu) = \frac{1}{2} \frac{\partial}{\partial w_j} ||w||^2 + \sum_i \mu^{(i)} \left\{ - y^{(i)} \frac{\partial}{\partial w_j} w^T \Phi(x^{(i)}) \right\} = \\ w_j - \sum_i \mu^{(i)} y^{(i)} \Phi(x^{(i)})_j \end{aligned} \\ \begin{aligned} \frac{\partial}{\partial b} L(w, b, \mu) = \sum_i \mu^{(i)} \left\{ -y^{(i)} \frac{\partial}{\partial b} b \right\} = \\ - \sum_i \mu^{(i)} y^{(i)} \end{aligned} \end{cases} \\ 由K.K.T条件：\begin{cases} \left.\begin{aligned} \sum_i \mu^{(i)} y^{(i)} \Phi(x^{(i)})_j & = w_j \\ \sum_i \mu^{(i)} y^{(i)} & = 0 \end{aligned}\right\} (极值条件) \\ 1 - y^{(i)} [w^T \Phi(x^{(i)}) + b] \leq 0 (不等式约束) \\ \left.\begin{aligned} \mu^{(i)} \left\{ 1 - y^{(i)} [w^T \Phi(x^{(i)}) + b] \right\} = 0 \\ \mu^{(i)} > 0 \end{aligned} \right\} (优化目标取'='的必要条件) \end{cases} \end{aligned}$$

$拉格朗日函数展开后，将极值条件代入，有$

$$\begin{aligned} L(w, b, \mu) & = \frac{1}{2} ||w||^2 + \sum_i \mu^{(i)} \left\{ 1 - y^{(i)} [w^T \Phi(x^{(i)}) + b] \right\} \\ & = \frac{1}{2} w^T w + \sum_i \mu^{(i)} - \sum_i \mu^{(i)} y^{(i)} w^T \Phi(x^{(i)}) - \sum_i \mu^{(i)} y^{(i)} b \\ & = \frac{1}{2} w^T w + \sum_i \mu^{(i)} - \sum_i \mu^{(i)} y^{(i)} \underbrace{\left( \sum_j w_j \Phi(x^{(i)})_j \right)}_{w^T \Phi(x^{(i)})} - \cancel{\sum_i \mu^{(i)} y^{(i)} b} \\ & \left.\begin{aligned} = \frac{1}{2} w^T w + \sum_i \mu^{(i)} - \sum_j w_j \cdot \underbrace{\sum_i \mu^{(i)} y^{(i)} \Phi(x^{(i)})_j}_{w_i} = - \frac{1}{2} w^T w + \sum_i \mu^{(i)} \\ w^T w = \left( \sum_i \mu^{(i)} y^{(i)} \Phi(x^{(i)}) \right)^T \left( \sum_i \mu^{(i)} y^{(i)} \Phi(x^{(i)}) \right) = \\ \sum_i \sum_j \mu^{(i)} \mu^{(j)} y^{(i)} y^{(j)} \Phi(x^{(i)})^T \Phi(x^{(j)}) \end{aligned}\right\} \Rightarrow \\ L(\mu) & = - \frac{1}{2} \underbrace{\sum_i \sum_j \mu^{(i)} \mu^{(j)} y^{(i)} y^{(j)} \Phi(x^{(i)})^T \Phi(x^{(j)})}_{w^T w} + \sum_i \mu^{(i)} \end{aligned}$$

$那么现在的优化问题如下，用SMO进行求解$

$$\begin{aligned} \mu & = \arg \max_{\mu} L(\mu) \\ s.t. & \quad \mu^{(i)} \geq 0, \quad \sum_i \mu^{(i)} y^{(i)} = 0 \\ \Rightarrow & \mu^* \Rightarrow w^*, b^* \end{aligned}$$

聚类

仅介绍部分概念和算法步骤。给定样本集合$\{X^{(i)}, i = 1, \cdots, N\}$，指定划分类别$K$，要求利用样本分布，将样本划分为$K$个类别。

距离度量

定义两个$n$维向量$x, y$，有如下常用距离定义

$$\begin{aligned} 曼哈顿距离 & d = || x - y ||_1 = \sum_j |x_j - y_j| \\ 欧氏距离 & d = || x - y ||_2 = (\sum_j (x_j - y_j)^2)^{1 / 2} \\ 闵可夫斯基距离 & d = || x - y ||_p = (\sum_j |x_j - y_j|^p)^{1 / p} \\ 余弦距离 & d = || x - y ||_1 = \cos <x, y> = \frac{x^T y}{||x||\cdot||y||} \\ \end{aligned}$$

KMeans

1. 随机选取$K$个样本点作为初始中心点(初值敏感)；
2. 计算每个样本点到各中心点的距离($N \times K$)；
3. 将每个样本划分到距离最近的中心点指代的类别中；
4. 每个类别重新计算中心点，更新参数；
5. 重复2~4直至收敛。

Spectral

1. 构建相似矩阵$\begin{cases} S_{N \times N} = \begin{bmatrix} d_{ij} \end{bmatrix} \\ d_{ij} = ||x^{(i)} - x^{(j)}||_2^2 \end{cases}$；
2. 计算邻接矩阵

   $$\begin{cases} \epsilon近邻法：& w_{ij} = \begin{cases} \epsilon & d_{ij} \leq \epsilon \\ 0 & otherwise \end{cases} \\ K近邻法：& w_{ij} = \begin{cases} \exp(-\frac{d_{ij}}{2 \sigma^2}) & x^{(i)} \in \delta_K(x^{(j)}) \quad AND/OR \quad x^{(j)} \in \delta_K(x^{(i)}) \\ 0 & otherwise \end{cases} \\ & \delta_K(x)表示x的K邻域 \\ 全连接法：& w_{ij} = \exp(-\frac{d_{ij}}{2 \sigma^2}) \end{cases}$$

3. 求度矩阵$D_{N \times N} = \text{diag}\{\sum_j w_{ij}, i = 1, \cdots, N\}$，即$W$行和作为对角元素；
4. 求(正则)拉普拉斯矩阵$L = D - W$或$L = D^{-1}(D - W)$或$L = D^{-1/2}(D - W)D^{-1/2}$；
5. 求$L$的特征分解，选取$N'(N' \leq N)$个最小特征值对应的特征向量组成矩阵$F_{N \times N'}$；
6. 将矩阵$F$每行视作样本$f^{(i)}$，标准化后执行其他简单的聚类如KMeans，得到聚类结果。

决策树

给定包含$|D|$个样本的样本集$D = \{(X^{(i)}, y^{(i)}), i = 1, \cdots, |D|\}$，属于$K$个类别$y \in \{C_k, k = 1, \cdots, K\}$，设类别$C_k$的样本数目为$|D_{k}|$，设特征$A$有$|A|$个特征$\{A_a, a = 1, \cdots, |A|\}$，每个特征包含样本数目$|D_{a}|$，记特征为$A_a$的样本中属于类别$C_k$的样本数目为$|D_{ak}|$。

ID3

用信息增益作为准则选择当前最优划分属性：信息增益越大表示属性越优

$$\begin{aligned} g(D, A) = H(D) - H(D | A) \\ \left.\begin{aligned} H(D) & = - \sum_k \frac{|D_k|}{|D|} \log \frac{|D_k|}{|D|}(总样本的类别熵) \\ H(D | A) & = \sum_a \frac{|D_a|}{|D|} \underbrace{\left( - \sum_k \frac{|D_{ak}|}{|D_a|} \log \frac{|D_{ak}|}{|D_a|} \right)}_{H(D_a)} (特征A_a的类别熵的加权和) \end{aligned} \right\} \end{aligned}$$

C4.5

用信息增益比作为准则选择当前最优划分属性：信息增益比越大表示属性越优

• 以信息增益比(information gain ratio)作为特征选择的准则，克服ID3会优先选择有较多属性值的特征的缺点；
• 弥补不能处理特征属性值连续的问题。

$$\begin{aligned} g_R(D, A) & = \frac{g(D, A)}{H_A(D)} \\ H_A(D) & = - \sum_a \frac{|D_a|}{|D|} \log \frac{|D_a|}{|D|} (特征A的属性熵) \end{aligned}$$

CART

用信息增益比作为准则选择当前最优划分属性：信息增益比越大表示属性越优

$$\begin{aligned} g_G(D, A) = \text{Gini}(D) - \text{Gini}(D|A) \\ \left.\begin{aligned} \text{Gini}(D) & = 1 - \sum_k (\frac{|D_k|}{|D|})^2 (总样本的类别基尼系数) \\ \text{Gini}(D|A) & = \sum_a \frac{|D_a|}{|D|} \underbrace{\left( 1 - \sum_k (\frac{|D_{ak}|}{|D_a|})^2 \right)}_{\text{Gini}(D_a)} (特征A_a的类别基尼系数的加权和) \end{aligned}\right\} \end{aligned}$$

RF

随机森林是用Bagging策略，对包含$N$个样本的数据集进行$M$次的有放回的采样，每次随机取$N_m$个样本，得到$M$个样本数目为$N_m$的样本子集，对每个子集建立分类器。

Bootstrap采样：对于一个样本，它在某一次含$m$个样本的训练集的随机采样中，每次被采集到的概率是$1/m$。不被采集到的概率为$1−1/m$。如果$m$次采样都没有被采集中的概率是$(1−1/m)^m$。当$m→\infty$时，$\lim_{m \rightarrow \infty} (1−1/m)^m \approx 0.368$。也就是说，在bagging的每轮随机采样中，训练集中大约有36.8%的数据没有被采样集采集中。对于这部分大约$36.8\%$的没有被采样到的数据，我们常常称之为袋外数据(Out Of Bag, 简称OOB)。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。

随机森林在Bagging策略上进行训练：

1. 用Bootstrap策略随机采样$M$次；
2. 一棵树的生成时，仅从所有特征($K$个)中选取$k$个特征；
3. 生成$M$棵树进行投票表决，确定预测结果(分类可取众数、回归可取均值)。