还有很多截图，懒得上传了
目录
展开
机器学习概述
掌握
- 基本概念
- 泛化误差 = 平均损失 = 平均期望下的 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；得到对偶问题
- 对偶问题
- 求解：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:
- 核函数
- $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
了解
- 剪枝$$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}$
- 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)$
- adaboost
- 提升树，知道每一步如何提升
- 前向分步算法 $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}$$