重点整理复习版

图片无法完全加载，请访问语雀文档

1 基础概念

1.1 什么是机器学习

通过数据训练的学习算法

1.2 监督，无监督，自监督，半监督

监督：利用大量标注数据（真实标签）训练模型
无监督：不依赖任何人工标注标签（聚类/降维/离散点检测）
自监督：标注来源于数据本身（对比学习）
半监督：深度学习领域…?

1.3 欠拟合和过拟合

过拟合：病态问题，学习能力强，过度计算导致模型泛化能力下降。在训练集上表现好（训练误差小），在测试集上表现差。
欠拟合：模型复杂度低，不能在训练集上实现足够低的误差，学习不到数据的规律。

1.4 评价学习算法的指标

混淆矩阵
列：预测为该类别的数目；行：实际为该类别的数目
【二分类】

	postive	negative
positive	TP	FN
negative	FP	TN

精度/准确率： $ACC = \frac{TP+TN}{TP+FP+FN+TN}$ （错误率：1-acc）
查准率： $Precision = \frac{TP}{TP+FP}$
查全率： $Recall = \frac{TP}{TP+FN}$
F1： $F1 = 2\frac{precision*recall}{precision+recall}$

1.5 没有免费的午餐

没有天生优越的学习器，只有相对好的建模，充分利用了与问题相关的先验知识模型才是最优的

1.6 距离度量的计算方式

1.6.1 曼哈顿距离

向量在每一维度上的相对距离和，即 $d = \Sigma_{k=1}^d|x_{ik}-x_{jk}|$
在二维平面上，两个点的曼哈顿距离表现为x方向上距离和y方向上距离的和

1.6.2 切比雪夫距离

各维度坐标数值差绝对值的最大值

1.6.3 马氏距离

$M$ 为协方差矩阵的逆矩阵，要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在
【如何计算协方差矩阵】

一行是一个样本，每一列是一个随机变量

1.6.4 闵可夫斯基距离

$d(x_i,x_j) = (\Sigma_{u=1}^n|x_{iu}-x_{ju}|^p)^{\frac{1}{p}}$
p = 1：曼哈顿距离
p = 2：欧氏距离
p = $\infin$ ：切比雪夫距离

2 KNN

k nearest neighbor classifier
懒惰学习算法，不需要学习成本，需要存储数据成本

2.1 算法流程

计算所有测试样本和所有训练样本的距离d
（距离升序排序？）
针对每一个测试样本，选择k个最近的训练样本
采用投票法为测试样本选定分类标签

（如果是回归：将 $\frac{1}{d}$ 作为权重，取k个近邻标签的加权平均）
测试阶段时间复杂度 $O(nd+nlogk)$ ：nlogk的解释，k个数的最小堆

2.2 k值影响

取奇数，避免平局
k较小，对噪声敏感，模型复杂，容易过拟合；k较大，对噪声不敏感，容易欠拟合

2.3 核平滑

核平滑方法是指使用核函数来计算测试样本的标签值（在回归中）

2.4 降低计算

2.4.1 维诺图

适合维度2-5：划分区块（维诺单元），每个维诺单元都是一个凸多面体
【2维维诺图】
计算维诺图： $O(nlogn)$ 算法决定
测试： $O(logn)$ 使用空间搜索树确定维诺单元（类似于平衡二叉树）

2.4.2 KD-Tree

适合特征维度6-30：相当于二叉树，用来划分空间

【构造】

计算x、y方向上的方差，选择方差大的轴进行划分
选取选定方向上数据的中位数进行划分
在划分出的新区域递归以上步骤

【测试】
kd树搜索

二叉搜索：从根节点开始，以递归的方式从树的顶端向下移动
当到达一个叶子节点，即得到最邻近的近似点，判断其是否为最优，并保存为“当前最优”
回溯：对整棵树进行递归，并对每个节点执行以下操作

如果当前节点比"当前最优"更近，替换为新的"当前最优"
判断分割平面的另一侧是否存在比"当前最优"更优的点。构造一个超球面，球心为查询点，半径为与当前最优的距离
- 如果超球面跟超平面相交，则有可能存在更优的点；按照相同的搜索过程从当前节点向下移动到树的另一个分支以寻找更近的点
- 如果超球面跟超平面不相交，则沿着树继续往上走，当前节点的另个分支则被排除

当算法为根节点完成整个过程时，算法结束

2.4.3 降维

参考降维

2.4.4 ANN 近似最近邻

搜索可能是近邻的数据项，牺牲精度

2.4.5 哈希

把任意长度输入映射成固定长度输出

3 聚类

聚类：数据对象的集合
聚类算法：根据给定的相似性评价标准将一个数据集合划分成几个聚类
相似性度量+聚类准则

3.1 聚类算法

3.1.1 试探法

凭借感觉/经验针对实际问题定义阈值 -> 最近邻规则（某种距离计算方式+对应阈值）
误差：与聚类中心（均值）距离平方和
初始点、样本次序和阈值都会影响
【最大最小距离法】
选择与确定的聚类中心最远的点作为新的中心，预先选定聚类中心
已经选定多个后添加新的中心：每一个样本，计算到所有中心的最小值，选择所有样本中的最大值，如果大于 $\theta ||z_1-z_2||$ 选定，否则选取过程结束

3.1.2 系统聚类

计算类之间的距离，合并新类
【类之间距离】

最短距离
最长距离
类平均距离

3.1.3 动态聚类法

3.1.3.1 K-means

确定聚类数量k
初始化k个聚类中心：随机选择k个样本点
对每个样本点计算最近聚类距离
更新聚类中心（平均值）
没有聚类中心移动：停止

【k-means++】

随机选1个样本点作为初始聚类中心
每一个样本点被选为下一个聚类中心的概率 $\frac{D(x)^2}{\Sigma D(x)^2}$ ， $D(x)$ 表示和所有中心的最短距离
使用轮盘法选择聚类中心

3.1.3.2 ISODATA

分裂+合并
根据样本到聚类中心分配样本，如果某一类样本数少于n，合并；类别数目小于K0/2，分裂；类别数目大于2K0，合并；
以平均中心作为聚类中心，更新中心后重复以上操作

3.2 如何评价聚类好坏

类内距离小，类间距离大

3.2.1 Compactness - CP

${CP_i} = \frac{1}{|\Omega_i|}\Sigma_{x_j \in \Omega_i}||x_i-w_i||$
$\Omega_i$ 表示某一个类， $w_i$ 表示聚类中心
紧密度计算类内距离：越小类内越紧凑

3.2.2 Separation - SP

间隔度越大越分散

3.2.3 Davies-Bouldin Index - DBI

戴维森堡丁指数/分类适确性指标

缺点：欧氏距离对于环状分布聚类评价很差

3.2.4 Dunn Validity Index - DVI

邓恩指数

对离散点聚类测评很高，对环状分布测评效果差

3.2.5 其他评价指标

4 树学习

4.1 符号学习

4.1.1 推理

推理（正向/反向）
归纳推理：前件为真，后件未必为真

4.1.2 概念学习

给定样例判断每个样例是否属于某个概念

4.1.2.1 实例空间与假设空间

【实例空间】所有可能样例集合
【假设空间】除了所有样例，还可能涉及到未知、空等情况

4.1.2.2 泛化和特化

样例 $h_i$ 和 $h_j$ 预测的类别相同， $h_j$ 包含的实例数更多
【泛化】 $h_j \ge_g h_k$
【特化】 $h_k \ge_s h_j$

4.1.2.3 Find-S

寻找极大特殊假设

满足：同一种结果，在这种属性上取值一致
【列表消除算法】
列出所有假设空间，消除不符合实例的假设（实际中不太可能）

4.2 变型空间

4.2.1 概念

【一致】一个假设和样例集合一致： $h(x) = c(x)$ ， $h(x)$ 表示假设函数， $c(x)$ 表示实例结果
变型空间定义：假设空间和样例集合一致的所有假设构成子集
【极大泛化】
【极大特化】

4.2.2 表示定理

h：其中一种假设（布尔函数）

4.2.3 候选消除算法

正例用于S泛化，搜索S集合；反例用于G特化，缩小G集合

有关find-s和候选消除算法讲解很细致易懂的博客概念学习和一般到特殊序 - WTSRUVF - 博客园

4.2.4 Find-S 与候选消除算法区别

find-s找到适合所有正例的假设，候选消除算法维护一组能够区分正例和负例的一致性假设
find-s从最特殊的假设开始进行泛化，候选消除算法从一般的泛化集合和最特殊的特化集合开始
find-s只考虑正例，不考虑负例；候选消除算法中正负例都会影响假设集合
find-s使用专门的搜索策略找到最特定的假设；候选消除算法搜索更全面

4.3 归纳偏置

某种形式的预先假定（前提）

4.4 决策树

归纳偏置：优先选择较小树
【优点】

容错能力好，健壮性高
可解释性强
不需要数据预处理
可以处理多维度输出分类问题

【缺点】

容易过拟合
样本改动会剧烈影响树结构
NP问题容易陷入局部最优

4.4.1 ID3算法

4.4.1.1 算法流程

创建root结点
如果所有样本属性一致，返回叶子节点；如果未划分的属性为空，选择所有样本中最普遍的标签（目标属性）；如果所有样本类别相同，返回叶子节点。【递归停止条件】
否则，选择分类样本能力最好的属性，依据属性的每个可能值划分样本递归执行

4.4.1.2 如何选择最佳属性

4.4.1.2.1 熵

目标属性为布尔值
$Entropy(S) = -p_+log(p_+)-p_-log(p_-)$

4.4.1.2.2 信息增益

使用A属性分割样例，导致期望熵降低（选择maxGain）
$G(S,A) = Entropy(S) - \Sigma_{v\in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v)$

4.4.1.3 特点

假设空间包含所有决策树，一次遍历，不进行回溯（局部最优）
对错误样例不敏感，不适用于增量处理
对可取值数目多的属性有偏好

4.4.2 奥卡姆剃刀原理

如果对同一现象有两种不同假说，应该采取比较简单的一种
优先选择拟合数据最简单的假设

4.4.3 C4.5算法

【信息增益比】
$GainRate(S,A) = \frac{Gain(S,A)}{Entropy_A(S)}$
$Entropy_A(S) = -\Sigma_{v\in Values(A)} \frac{|S_v|}{|S|} log(\frac{|S_v|}{|S|})$
除以属性的熵

4.4.4 CART算法

4.4.4.1 Gini系数

k个类中，样本属于第k类的概率为 $p_k = \frac{|C_k|}{|D|}$

二分类问题gini系数
gini系数代表模型的纯度，越小越好
【属性划分后计算基尼系数】

4.4.4.2 回归

对某一属性A，找到一个点s使得s左右两边数据集各自均方差（标准差？）相加最小
选择和最小的属性
s为经过排序后，某两个相邻样本的平均数
【回归输出】
采用叶子节点的均值或中位数作为预测结果

4.4.5 剪枝

4.4.5.1 后剪枝

从决策树底部剪去一些子树，在独立验证集上测试选择最优子树
剪去子树：变成占比高的叶子节点标签

4.4.5.2 最小化子树损失函数

5 集成学习

5.1 原理

多个分类器集成在一起以提高分类准确率
集成方法包括多数投票法等等

5.1.1 准确性计算

假设每个二分类器精度为p，且相互独立
继承后T个二分类器的分类器的精度为 $\Sigma_{k=\frac{T}{2}+1}^T C_T^k p^k(1-p)^{T-k}$
T足够大时近似二项分布，要求每个分类器的准确率要在50%以上

5.1.2 bias & variance tradeoff

5.1.3 基本策略

5.1.3.1 回归问题

简单平均
加权平均

5.1.3.2 分类问题

投票法

绝对多数
相对多数
加权投票

5.2 Bagging

bootstrap aggregating

5.2.1 基本原理

有放回的采样方法

5.2.2 优点&缺点

【优点】
并行式集成学习，降低分类器方差，改善泛化
【缺点】
基学习器高bias会影响集成后学习器的高bias
集成后损失可解释性

5.2.3 随机森林RF

有放回抽样 -> 生成随机树（随机抽取特征） -> 使用没有被抽到的样本进行测试（多数投票/平均）

【特点】

差异性：每棵树使用特征不同
缓解维度灾难：抽取一部分特征来生成决策树
可并行化
训练测试无需划分：有30%左右数据没有被采样
稳定：投票/平均

5.3 Boosting

5.3.1 基本原理

probably approximately correct(PAC) - 概率近似正确
【强可学习】如果存在一个多项式的学习算法能够学习，并且正确率很高
【弱可学习】多项式的学习算法，但是正确率仅比随机猜测略好
【PAC学习理论】强学习器和弱学习器是等价的，可以通过提升将弱学习器转化为强学习器

5.3.2 AdaBoost

Adaptive Boost，二分类学习算法

5.3.2.1 基本思想

改变训练数据的概率分布，反复学习，得到一系列的弱学习器组合形成一个强分类器
提高错误分类样本权值，降低正确分类权值
集成时加权投票：错误率小的分类器权重高，错误率大权重低

5.3.2.2 计算

第k个弱分类器 $G_k(x)$ 在训练集上加权分类的错误率为 $e_k = \Sigma_{i=1}^m w_{k,i}I(G_k(x_i) \neq y_i)$ ，其中 $w_{k,i}$ 表示第k个分类器输出i个样本权重
得到第k个分类器 $G_k(x)$ 投票权重系数 $\alpha_k = \frac{1}{2} log\frac{1-e_k}{e_k}$

【可视化表现】

5.3.2.3 解释

5.3.2.3.1 加法模型

损失函数可以写作 $L(y_i,f(x))$ ，f(x)为上述表达式，这个函数优化起来十分复杂，可以采用前向分步算法

5.3.2.3.2 前向分步算法

每一步只学习一个基函数及其系数

adaboost是前向分步算法的特例，损失函数是指数函数

5.3.2.3.3 分类器与损失函数

【最终分类器】
$f(x) = \Sigma_{k=1}^{K} \alpha_k G_k(x_i)$
【损失函数】
$L(y,f(x)) = exp(-yf(x))$

5.3.3 其他boosting算法

5.3.3.1 boosting tree

平方误差损失函数

5.3.3.2 GBDT

梯度提升树，使用损失函数和分类器分类结果的偏导求得梯度作为残差，拟合回归树

5.3.3.3 XGBoost

extreme gradient boosting
GBDT的高效实现，使用二阶泰勒展开做近似

5.4 Stacking

k-fold

6 概率学习

6.1 基本数学概念

6.1.1 张量tensor

一个泛化的实数构成的n维数组

6.1.2 带/不带约束的数学优化问题

6.1.2.1 带约束

比如拉格朗日（见SVM部分）

6.1.2.2 不带约束

**【最小二乘问题】**least-squares

6.1.3 凹凸函数

判断凹凸可以通过计算二阶导确定， $f''(x) \ge 0$ 是凸函数或hessian矩阵半正定： $\nabla^2f(x)\succcurlyeq 0$
【hessian矩阵-矩阵二阶导】

【jacob矩阵】

6.1.4 概率

6.1.4.1 概率函数

概率密度函数（PDF）：连续值取某个值的概率
概率质量函数（PMF）：离散值，正好等于某个值的概率

6.1.4.2 期望

6.1.5 jensen不等式

6.1.6 高斯分布/正态分布

$X \sim N(\mu,\sigma^2)$
概率密度函数： $p(x) = \frac{1}{\sigma \sqrt{2\pi}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$
$\mu = 0, \sigma = 1$ 是标准正态分布

【多变量高斯分布】

6.2 高斯混合模型GMM

多个高斯分布的加权和，利用此模型进行聚类，每一个子分布都是高斯分布

6.3 最大似然估计MLE

6.3.1 定义

maximum likelihood estimation，最大化似然函数以估计概率分布
【单高斯模型】
$L(\theta | X) = p (X | \theta) = \prod_{j=1}^M p(x_j|\theta)$
两边取对数

6.3.2 期望最大化算法EM

6.3.2.1 核心思想

M-step：使用最大似然估计得到更好的参数 $\theta$

7 SVM

找到能够最大化不同类别数据间隔的超平面，通过最大化决策边界和支持向量的距离提高模型的泛化能力，将数据映射到高维空间中实现线性可分

7.1 间隔与支持向量

【间隔】每个样本点到分界超平面的垂直距离
【支持向量】所有样本中拥有最小间隔的点
【SVM目标】最大化最小间隔

7.2 计算

7.2.1 点到法平面距离

f(x)>0是正类，反之负类。判断分类预测的正误可以使用yf(x)>0来确认，<0表示分类不统一，错误

7.2.2 优化

只需要方向，不需要大小，令 $||w||=1$
限制 $min(y_if(x_i)) = min(y_i (w^Tx_i+b)) = 1$ （最优解除以任意非0倍数依然是最优解），此时相当于最大化 $\frac{1}{||w||}$ ，即最小化 $\frac{1}{2}w^Tw$ （加1/2为了消除求导平方系数）

7.2.3 求解

7.2.3.1 KKT条件

7.2.3.2 对偶

引入拉格朗日乘子 $a_i$ 后，该乘子构成对偶空间

7.2.3.3 最优解

7.3 soft margin

惩罚：松弛变量

7.4 非线性SVM

映射到更高维的特征空间使得样本线性可分

7.4.1 kernel trick

7.4.2 Mercer’s condition

7.4.3 Kernel SVM

测试时间为O(nd)

7.4.3.1 线性核

$K(x,y) = x^T y$

7.4.3.2 RBF/Gaussian核

7.4.3.3 多项式核

【超参数】

7.5 多类SVM

7.5.1 1V1

转化为两类问题，构造 $C_n^2$ 个分类器
将一个样本得到的所有结果按照投票法做决定

7.5.2 1 V all

共n个类，设置n个分类器，每个分类器用类i做正类，其他所有类做负类
每个分类器采用实际值输出作为信心，选择信心最高类

8 神经元与感知机

8.1 Hebbian Theory赫布理论

连接强度的调整量和输入输出的乘积成正比，经常出现的模式将增强神经元之间的连接
又称长度增强机制（LTP：Long Term Potentiation）或神经可塑（Neural Plasticity）

8.2 MP神经元

8.2.1 基本工作原理

输入 -》权值 -》激活函数

8.2.2 局限

输入：线性求和
输出：单一输出值
更新：时钟同步更新

8.2.3 激活函数

【sigmoid】
饱和激活函数（tanh） $\lim_{n \to +\inf}h'(x) = \lim_{n\to-\inf}h'(x) = 0$ 饱和激活函数
导数始终小于1，在0周围变化，容易造成梯度消失问题
指数的计算代价大
【ReLU】
非饱和激活函数可以解决梯度消失问题，加快模型收敛速度