机器学习 cheatsheet

还有很多截图,懒得上传了

机器学习概述

掌握

  • 基本概念
    • 泛化误差 = 平均损失 = 平均期望下的 loss = $R(h) = e_{x\sim\mathcal{D}}[L(h(x),c(x))]$
    • 经验风险 = 数据集上的平均 loss = $\hat{R}(h) = \frac{1}{N}\sum_{i=1}^N L(h(x),c(x))$
    • 经验风险 = 训练误差 = train 上的经验风险 = $\hat{R}(h_T)$
    • 测试误差 $\hat{R}_{test}(h_T)$
    • tp, fp, tn, fn:AB 预测出的 B 是 A 的
    • p = tp / p
    • r = tp / (tp + fn)
    • f = 2pr / (p + r)
  • val:to find $\lambda$ for regularization
    • hold out: split train/dev/test
    • k-fold
      • leave one out: train n times
    • bootstrapping

了解

  • 泛化误差 = 偏差 + 方差 + 噪声
    • 偏差:偏差越小,学习算法能力越强
    • 方差:方差越小,学习算法对数据扰动的容忍能力越强
    • 模型过于简单时,偏差占大头;过于复杂时,过拟合大方差

感知机与支持向量机

掌握

  • 线性可分,不可分
  • svm 🍔
    • 原始问题 $$\begin{aligned} \min_{w,b}&;\frac{1}{2}|w|^2 \ \text{s.t.}&;y_i(w\cdot x_i + b)\ge 1,\quad i = 1,2,…,N \ \end{aligned}$$
    • 求对偶:
      • $$L(w,b,\alpha) = \frac{1}{2}\|w\|^2 + \sum_{i=1}^N\alpha_i – \sum_{i=1}^N \alpha_i y_i(w\cdot x_i + b)$$
      • w, b 偏导 = 0;带入 L;得到对偶问题
    • 对偶问题
    $$\begin{aligned}\max_{\alpha}&\;\sum_{i=1}^N\alpha_i – \frac{1}{2}\sum_{i,j = 1}^N\alpha_i \alpha_j y_i y_j x_i \cdot x_j \\\text{s.t.}&\;\sum_{i=1}^N \alpha_iy_i = 0 \\&\; \alpha_i \ge 0,\quad i = 1,2,…,N\end{aligned}$$
    • 求解:KKT,$\exist \alpha_j > 0$
    • 解的表达形式:
      • $b = y_j – \sum_{i,j=1}^N\alpha_iy_ix_i\cdot x_j$
      • $\|w\| = \sqrt{\sum_{j=1}^N\alpha_j}$
  • soft margin svm 🍔
    • $y_i(w\cdot x_i + b) + \xi_i\ge 1$
    • primal:
    • dual:
    $$\begin{aligned}\min_{w,b,\xi}&\;\frac{1}{2}\|w\|^2 + C\sum_{i=1}^N \xi_i\\\text{s.t.}&\;y_i(w\cdot x_i + b)\ge 1 – \xi_i,\quad i = 1,2,…,N \\&\;\xi_i \ge 0,\quad i = 1,2,…,N \\\end{aligned}$$$$\begin{aligned}\max_{\alpha}&\;\sum_{i=1}^N\alpha_i – \frac{1}{2}\sum_{i,j = 1}^N\alpha_i \alpha_j y_i y_j x_i \cdot x_j \\\text{s.t.}&\;\sum_{i=1}^N \alpha_iy_i = 0 \\&\; 0 \le \alpha_i \le C,\quad i = 1,2,…,N\end{aligned}$$
  • 核函数
    • $K(x_i,x_j) = \phi(x_i)\cdot \phi(x_i)$
    • 多项式核函数:$K(x,x’) = (x\cdot x’ + c)^d$
    • 高斯核:$K(x,x’) = \exp(-\frac{\|x – x’\|^2}{2\sigma^2})$

了解

  • 序列最小:每次只更新两个拉格朗日乘子,可求解析解

决策树

掌握

  • 指标
    • 熵 $H(X) = -\sum_{i=1}^np_i\log p_i$(底是 2,用计算器算完别忘了再除以 log2!)
    • 条件熵 $H(Y|X) = \sum_{i=1}^n H(Y|X = x_i)P(X = x_i)$
    • 信息增益 $g(D,A) = H(D) – H(D|A)$ 
    • 分裂信息 $\text{Splitinfo}_A(D) = -\sum_{i=1}^n\frac{|D_i|}{|D|}\log(\frac{|D_i|}{|D|})$
    • 信息增益率 $g_R(D, A) = g(D,A) / \text{Splitinfo}_A(D)$
    • ppt 5-20 例题计算过程 🍔
    • 基尼指数,(课件上的一张表)  
  • ID3 信息增益
  • C4.5 信息增益比
  • CART 树
    • 二叉树,递归二分每个特征
    • 分类:基尼指数最小化
      • $Gini(p) = \sum_{k=1}^Kp_k(1-p_k) = 1-\sum_{k=1}^Kp_k^2$ 二分类 $=2p(1-p)$
      • $Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$
    • 回归:平方误差 $\sum(y_i – f(x_i))^2$ 最小化
      • 选择切分点:$\hat{c}$ 表示集合均值,枚举 $j,s$ 找最小的变量 j 对应的最好的二分点 s
      $$\min_{j,s}\bigg[\min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i – \hat{c}_1)^2 + \min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i – \hat{c}_2)^2\bigg]$$

了解

  • 剪枝$$C_\alpha(T) = -\sum_{t=1}^{|T|}\sum_{k=1}^K N_{tk} \log\frac{N_{tk}}{N_t} + \alpha|T|$$

基于后验概率最大化

掌握

  • 后验概率最大化的含义:
    • $$\hat{y} = \arg\max_{c_i}P(Y = c_i|x)$$
    • 判别式模型:直接从训练集学出后验概率
    • 生成式模型:先学出联合概率分布 $P(Y = c_i,x)$,然后 $P(Y = c_i|x) = \frac{P(Y = c_i,x)}{P(x)}$
  • 二项逻辑斯蒂 🍔
    • 模型
    • 分类
    • 似然函数 $L(\theta) = \prod_{i=1}^N p(x_i;\theta)^{y_i}(1-p(x_i;\theta))^{1-y_i}$
    $$\begin{aligned}P(Y = c_1|x) &= \frac{\exp(xw+b)}{1 + \exp(xw+b)} \\P(Y = c_2|x) &= \frac{1}{1 + \exp(xw+b)}\end{aligned}$$$$y = \begin{cases}c_1,\;\text{if } P(Y = c_1|x) > P(Y = c_1|x)\\c_2, \; \text{others}\end{cases}$$ $$y = \begin{cases}c_1,\;\text{if } wx+b>0\\c_2, \; \text{others}\end{cases}$$
  • bayes$$P(Y = c_i|x) = \frac{P(x|Y = c_i)P(Y=c_i)}{\sum_{k=1}^KP(x|Y = c_k)P(Y=c_k)}$$
    • 训练集学得先验分布 $P(Y)$ 和条件分布 $P(X|Y)$
  • naive bayes
    • 独立同分布 
    • $\lambda=0$ 极大似然估计 $\lambda=1$ laplace 平滑
  • 参数估计:⻉叶斯估计会手算 🍔,最大似然不要求
  • 对数线性模型知道最后的形式就行(二项逻辑斯蒂拓展到多项)
  • 最大熵模型 

集成学习

掌握

  • 提升方法
    • adaboost
      • 基分类器投票权重 $\alpha_t = 0.5 * \ln \frac{1-e_t}{e_t}$($s_T$ 为样本集的分类错误率)
      • 数据权值分布 $W_{i,t+1} = \frac{W_{i,t}}{Z_t}\exp(-\alpha_ty_if_t(x_i))$
      • $G(x) = \sum_{i=1}^N\alpha_tf_t(x)$
     
  • 提升树,知道每一步如何提升
    • 前向分步算法 $f_m = f_{m-1} + T(x,\Theta_m)$
    • $\Theta_m = \arg\min_\Theta\sum_{i=1}^N L(y_i,f_{m-1}(x_i) + T(x_i;\Theta))$
    • 回归树 平方损失:$\Theta_m = \arg\min_\Theta\sum_{i=1}^N[y_i – (f_{m-1}(x_i) + T(x_i;\Theta))]^2$
    • 提升树算法每轮基学习器的学习就是在拟合当前模型的残差
  • bagging 

不要求

随机森林

EM

掌握

  • E 步:求期望,计算 Q 函数 $Q(\theta, \theta^{(i)}) = E_z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]$
  • M 步:求 max

不要求

推导

SVD和PCA

掌握 基本结论定义

SVD

  • SVD的三部分分别指什么
    • $A = U\Sigma V^T,\quad A\in\mathbb{R}^{m\times n},U\in\mathbb{R}^{m\times m},V\in\mathbb{R}^{n\times n},U,V$ 均为正交矩阵
    • 任意一个实矩阵,其奇异值分解一定存在
    • $\Sigma_{i,i} = \sigma_i = \sqrt{\lambda_i}, \lambda_i$ 为 $W = A^TA$ 的特征值
    • $V$ 为单位化的特征向量
    • $U$ 前 rank(A) 个:$u_j = \frac{1}{\sigma_j}Av_j$,后面的:$A^T$ 零空间的一组标准正交基($A^Tx=0$)
    • 书 P282
  • 紧的 SVD:$r = rank(A), A=U_r\Sigma_rV_r^T$
  • 截断 SVD:$A\approx U_k\Sigma_kV_k^T \quad U\in\mathbb{R}^{m\times k},V\in\mathbb{R}^{k\times n}$,分别是前 k 行/列
    • 误差
  • F 范数
    • $\|A\|_F = (\sigma_1^2 + \sigma_2^2 + … + \sigma_n^2)^{\frac{1}{2}}$
    • $\|A – A’\|_F = (\sigma_{k+1}^2 + \sigma_{k+2}^2 + … + \sigma_n^2)^{\frac{1}{2}}$
  • 外积展开式:$A = \sigma_1u_1v_1^T + \sigma_2u_2v_2^T +… + \sigma_nu_nv_n^T$

PCA

  • 方差之和最大的为第一主成分
  • 样本的 PCA 中 SVD 与 PCA 相联系的部分 P313,316
    • 方差矩阵进行特征值分解,特征值最大的就是主成分的维度
    • $S = \frac{1}{n}XH^TX$
    • 累计方差贡献率 $\sum\lambda/\sum\lambda$
    • 对数据中心化后的矩阵,进行奇异值分解 P316
      • $S = X^THX = V\Sigma ^2 V^T$ 得到方向(主成分),由 $HX\cdot V$ 得到坐标
      • $T = HXX^TH = U\Sigma^2 U^T$ 直接得到坐标(主坐标分析 PCoA)
  • 主成分变换,标准线性组合,线性无关
  • 信息损失

聚类

掌握

  • 数据对象间的相似性,数据集间的相似性
  • 数据集的类标记,e g多数占优
  • 基于近邻,K均值,学习向量量化代表点的修正,找最近的点,移动的作用等
  • 层次聚类的思想,距离矩阵的修正

隐⻢尔可夫模型

掌握

  • 前项算法

$$\begin{aligned}\alpha_1(i) &= \phi_i b_i(o_1) \\\alpha_{t+1}(i) &= (\sum_{j=1}^N \alpha_t(j)\cdot a_{ji})b_i(o_{t+1}) \\P(O|\lambda) &= \sum_{i=1}^N\alpha_T(i)\end{aligned}$$

  • 后向算法

$$\begin{aligned}\beta_T(i) &= 1 \\\beta_{t}(i) &= \sum_{j = 1}^N a_{ij}\beta_{t+1}(j)b_j(o_{t+1}) \\P(O|\lambda) &= \sum_{i=1}^N \phi_ib_i(o_1)\beta_1(i)\end{aligned}$$

发表评论