静觅：超全总结！一文囊括李航《统计学习方法》几乎所有的知识点

当前位置博文首页 > 静觅：超全总结！一文囊括李航《统计学习方法》几乎所有的知识点

最大化缩小

静觅：超全总结！一文囊括李航《统计学习方法》几乎所有的知识点

作者：[db:作者] 时间：2021-06-14 12:41

如果大家对机器学习算法有所涉猎的话，想必你一定看过《统计学习方法》这本书，里面介绍了统计学中的一些基本算法和知识点，本文进行了详细的总结。

转载来源

公众号：机器学习算法与自然语言处理

“

阅读本文大概需要 19 分钟。

”

阅读目录：

1. 知识点
2. 感知机
3. k 近邻法
4. 朴素贝叶斯
5. 决策树
6. logistic 回归和最大熵模型
7. 支持向量机
8. 提升方法
9. EM 算法
10. 隐马尔可夫模型 ( HMM )
11. 统计学习方法总结
12. 神经网络
13. K-Means
14. Bagging
15. Apriori
16. 降维方法
17. 引用

因为要准备面试，本文以李航的《统计学习方法》为主，结合西瓜书等其他资料对机器学习知识做一个整理。

一、知识点

进程和线程：进程和线程都是一个时间段的描述，是 CPU 工作时间段的描述，不过是颗粒大小不同。进程就是包换上下文切换的程序执行时间总和 = CPU 加载上下文 + CPU 执行 + CPU 保存上下文。线程是共享了进程的上下文环境的更为细小的 CPU 时间段。
判别式模型和生成式模型：

判别式模型直接学习决策函数 f(X) 或条件概率分布 P(Y|X) 作为预测的模型。往往准确率更高，并且可以简化学习问题。如 k 近邻法/感知机/决策树/最大熵模型/ Logistic 回归/线性判别分析 ( LDA ) /支持向量机 ( SVM ) / Boosting /条件随机场算法 ( CRF ) /线性回归/神经网络
生成式模型由数据学习联合概率分布 P(X，Y)，然后由 P(Y|X)=P(X，Y)/P(X) 求出条件概率分布作为预测的模型,即生成模型。当存在隐变量时只能用生成方法学习。如混合高斯模型和其他混合模型/隐马尔可夫模型 ( HMM ) /朴素贝叶斯/依赖贝叶斯 ( AODE ) / LDA 文档主题生成模型。

概率质量函数，概率密度函数，累积分布函数：

概率质量函数 ( probability mass function，PMF ) 是离散随机变量在各特定取值上的概率。
概率密度函数 ( probability density function，PDF ) 是对?连续随机变量?定义的，本身不是概率，只有对连续随机变量的取值进行积分后才是概率。
累积分布函数 ( cumulative distribution function，CDF ) 能完整描述一个实数随机变量 X 的概率分布，是概率密度函数的积分。对於所有实数 x，与 pdf 相对。

极大似然估计：已知某个参数能使这个样本出现的概率最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。
最小二乘法：二乘的英文是 least?square，找一个 ( 组 ) 估计值，使得实际值与估计值之差的平方加总之后的最小。求解方式是对参数求偏导，令偏导为0即可。样本量小时速度快。
梯度下降法：负梯度方向是函数值下降最快的方向，每次更新值都等于原值加学习率 ( 步长 ) 乘损失函数的梯度。每次都试一个步长看会不会下降一定的程度，如果没有的话就按比例减小步长。不断应用该公式直到收敛，可以得到局部最小值。初始值的不同组合可以得到不同局部最小值，在最优点时会有震荡。

批量梯度下降 ( BGD )：每次都使用所有的 m 个样本来更新，容易找到全局最优解，但是 m 较大时速度较慢。
随机梯度下降 ( SGD )：每次只使用一个样本来更新，训练速度快，但是噪音较多，不容易找到全局最优解，以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。注意控制步长缩小，减少震荡。
小批量梯度下降 ( MBGD )：每次使用一部分样本来更新。

牛顿法：牛顿法是二次收敛，因此收敛速度快。从几何上看是每次用一个二次曲面来拟合当前所处位置的局部曲面，而梯度下降法是用一个平面来拟合。
红色的是牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。牛顿法起始点不能离极小点太远，否则很可能不会拟合。

黑塞矩阵是由目标函数 f(x) 在点 X 处的二阶偏导数组成的 n*n 阶对称矩阵。
牛顿法：将 f(x) 在 x(k) 附近进行二阶泰勒展开：
其中，gk 是 f(x) 的梯度向量在 x(k) 的值，H(x(k)) 是 f(x) 的黑塞矩阵在点 x(k) 的值。牛顿法利用极小点的必要条件 f(x) 处的梯度为0，每次迭代中从点 x(k) 开始，假设，对二阶泰勒展开求偏导有，代入得到，即，以此为迭代公式就是牛顿法。

拟牛顿法：用一个 n 阶正定矩阵 Gk=G(x(k)) 来近似代替黑塞矩阵的逆矩阵就是拟牛顿法的基本思想。在牛顿法中黑塞矩阵满足的条件如下：，令，则有，称为拟牛顿条件。根据选择 Gk 方法的不同有多种具体实现方法。

DFP 算法：假设每一步，为使 Gk+1 满足拟牛顿条件，可使 Pk 和 Qk 满足，，例如取，，就得到迭代公式
BFGS 算法：最流行的拟牛顿算法。考虑用 Bk 逼近黑塞矩阵，此时相应的拟牛顿条件是，假设每一步，则 Pk 和 Qk 满足，，类似得到迭代公式

先验概率和后验概率：

先验概率就是事情发生前的预测概率。
后验概率是一种条件概率，它限定了事件为隐变量取值，而条件为观测结果。一般的条件概率，条件和事件可以是任意的。
贝叶斯公式 P(y|x) = ( P(x|y) * P(y) ) / P(x) 中，P(y|x) 是后验概率，P(x|y) 是条件概率，P(y) 是先验概率。

偏差，方差，噪声：

偏差：度量了学习算法的期望预测和真实结果偏离程度。
方差：度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响。
噪声：可以认为是数据自身的波动性，表达了目前任何学习算法所能达到泛化误差的下限。
泛化误差可以分解为偏差、方差与噪声之和。

对偶原理：一个优化问题可以从主问题和对偶问题两个方面考虑。在推导对偶问题时，通过将拉格朗日函数对 x 求导并使导数为0来获得对偶函数。对偶函数给出了主问题最优解的下界，因此对偶问题一般是凸问题，那么只需求解对偶函数的最优解就可以了。
KKT 条件：通常我们要求解的最优化条件有如下三种：

无约束优化问题：通常使用求导，使导数为零，求解候选最优值。
有等式约束的优化问题：通常使用拉格朗日乘子法，即把等式约束用拉格朗日乘子和优化问题合并为一个式子，通过对各个变量求导使其为零，求解候选最优值。拉格朗日乘数法其实是 KKT 条件在等式约束优化问题的简化版。
有不等式约束的优化问题：通常使用 KKT 条件。即把不等式约束，等式约束和优化问题合并为一个式子。假设有多个等式约束 h(x) 和不等式约束 g(x)
则不等式约束引入的KKT条件如下：
实质是最优解在 g(x)<0 区域内时，约束条件不起作用，等价于对 μ 置零然后对原函数的偏导数置零；当 g(x)=0 时与情况2相近。结合两种情况，那么只需要使 L 对 x 求导为零，使 h(x) 为零，使 μg(x) 为零三式即可求解候选最优值。

性能度量：

准确度，最常用，但在数据集不平衡的情况下不好。
Precision ( 精确度/查准率 )：P=TP/(TP+FP)
Recall ( 召回率/查全率 )：R=TP/(TP+FN)
Fβ 度量：，当 β=1 时退化为 F1 度量，是精确率和召回率的调和均值。
TPR ( 真正例率 )：TPR=TP/(TP+FN)
FPR ( 假正例率 )：FPR=FP/(TN+FP)
PR 曲线：纵轴为 Precision，横轴为 Recall，一般使用平衡点 ( BEP，即 Precsion=Recall 的点 ) 作为衡量标准。
ROC ( 接受者操作特征 ) 曲线：纵轴为 TRP，横轴为 FPR，在绘图时将分类阈值依次设为每个样例的预测值,再连接各点。ROC 曲线围住的面积称为 AOC，AOC 越大则学习器性能越好。

损失函数和风险函数：

损失函数度量模型一次预测的好坏。常用的损失函数有：0-1损失函数，平方损失函数，绝对损失函数，对数似然损失函数。
损失函数的期望是理论上模型关于联合分布 P(X，Y) 的平均意义下的损失，称为风险函数，也叫期望风险。但是联合分布是未知的，期望风险不能直接计算。
当样本容量 N 趋于无穷时经验风险趋于期望风险，但现实中训练样本数目有限。

经验风险最小化和结构风险最小化：

模型关于训练数据集的平均损失称为经验风险。经验风险最小化的策略就是最小化经验风险。当样本数量足够大时学习效果较好。比如当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。但是当样本容量很小时会出现过拟合。
结构风险最小化等于正则化。结构风险在经验风险上加上表示模型复杂度的正则化项。比如当模型是条件概率分布，损失函数是对数损失函数，模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计。

过拟合是指学习时选择的模型所包含的参数过多，以致于对已知数据预测得很好，但对未知数据预测很差的现象。模型选择旨在避免过拟合并提高模型的预测能力。
正则化是模型选择的典型方法。正则化项一般是模型复杂度的单调递增函数，比如模型参数向量的范数。
交叉验证是另一常用的模型选择方法，可分为简单交叉验证，K 折交叉验证，留一交叉验证等。

二、感知机

感知机是二类分类的线性模型，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面。是神经网络和支持向量机的基础。

模型：，w 叫作权值向量，b 叫做偏置，sign 是符号函数。
感知机的几何解释：wx+b 对应于特征空间中的一个分离超平面 S，其中 w 是 S 的法向量，b 是 S 的截距。S 将特征空间划分为两个部分，位于两个部分的点分别被分为正负两类。
策略：假设训练数据集是线性可分的，感知机的损失函数是误分类点到超平面 S 的总距离。因为误分类点到超平面S的距离是，且对于误分类的数据来说，总有成立，因此不考虑 1/||w||，就得到感知机的损失函数：，其中 M 是误分类点的集合。感知机学习的策略就是选取使损失函数最小的模型参数。
算法：感知机的最优化方法采用随机梯度下降法。首先任意选取一个超平面 w0，b0，然后不断地极小化目标函数。在极小化过程中一次随机选取一个误分类点更新 w，b，直到损失函数为0。
其中 η 表示步长。该算法的直观解释是：当一个点被误分类，就调整 w，b 使分离超平面向该误分类点接近。感知机的解可以不同。
对偶形式：假设原始形式中的 w0 和 b0 均为0，设逐步修改 w 和 b 共 n 次，令 a=nη，最后学习到的 w，b 可以表示为
那么对偶算法就变为设初始 a 和 b 均为0，每次选取数据更新 a 和 b 直至没有误分类点为止。对偶形式的意义在于可以将训练集中实例间的内积计算出来，存在 Gram 矩阵中，可以大大加快训练速度。

三、k 近邻法

k 近邻法根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。k 值的选择，距离度量及分类决策规则是 k 近邻法的三个基本要素。当 k=1 时称为最近邻算法。

模型：当训练集，距离度量，k 值以及分类决策规则确定后，特征空间已经根据这些要素被划分为一些子空间，且子空间里每个点所属的类也已被确定。
策略：

距离：特征空间中两个实例点的距离是相似程度的反映，k 近邻算法一般使用欧氏距离，也可以使用更一般的 Lp 距离或 Minkowski 距离。
k 值：k 值较小时，整体模型变得复杂，容易发生过拟合。k 值较大时，整体模型变得简单。在应用中 k 一般取较小的值，通过交叉验证法选取最优的 k 。
分类决策规则：k 近邻中的分类决策规则往往是多数表决，多数表决规则等价于经验风险最小化。

算法：根据给定的距离度量，在训练集中找出与 x 最邻近的 k 个点，根据分类规则决定 x 的类别 y 。
kd 树：

kd 树就是一种对 k 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd 树更适用于训练实例数远大于空间维数时的 k 近邻搜索。
构造，可以通过如下递归实现：在超矩形区域上选择一个坐标轴和此坐标轴上的一个切分点，确定一个超平面，该超平面将当前超矩形区域切分为两个子区域。在子区域上重复切分直到子区域内没有实例时终止。通常依次选择坐标轴和选定坐标轴上的中位数点为切分点，这样可以得到平衡 kd 树。
搜索：从根节点出发，若目标点 x 当前维的坐标小于切分点的坐标则移动到左子结点，否则移动到右子结点，直到子结点为叶结点为止。以此叶结点为 " 当前最近点 "，递归地向上回退，在每个结点：(a) 如果该结点比当前最近点距离目标点更近，则以该结点为 " 当前最近点 " ( b ) " 当前最近点 " 一定存在于该结点一个子结点对应的区域,检查该结点的另一子结点对应的区域是否与以目标点为球心，以目标点与 " 当前最近点 " 间的距离为半径的超球体相交。如果相交，移动到另一个子结点，如果不相交，向上回退。持续这个过程直到回退到根结点，最后的 " 当前最近点 " 即为最近邻点。