还有很多截图,懒得上传了
目录
展开
机器学习概述
掌握
- 基本概念
- 泛化误差 = 平均损失 = 平均期望下的 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}$$