李航老师的《统计学习方法》是机器学习入门的必读书籍，结构逻辑清晰，这篇文章是总结的读书笔记。

文章作者：

Limitlessun

阅读目录：

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

一、知识点
  1. 判别式模型直接学习决策函数 f(X) 或条件概率分布 P(Y|X) 作为预测的模型。往往准确率更高，并且可以简化学习问题。如 k 近邻法/感知机/决策树/最大熵模型/ Logistic 回归/线性判别分析 ( LDA ) /支持向量机 ( SVM ) / Boosting /条件随机场算法 ( CRF ) /线性回归/神经网络
  2. 生成式模型由数据学习联合概率分布 P(X，Y)，然后由 P(Y|X)=P(X，Y)/P(X) 求出条件概率分布作为预测的模型,即生成模型。当存在隐变量时只能用生成方法学习。如混合高斯模型和其他混合模型/隐马尔可夫模型 ( HMM ) /朴素贝叶斯/依赖贝叶斯 ( AODE ) / LDA 文档主题生成模型。
  1. 概率质量函数 ( probability mass function，PMF ) 是离散随机变量在各特定取值上的概率。
  2. 概率密度函数 ( probability density function，PDF ) 是对 连续随机变量 定义的，本身不是概率，只有对连续随机变量的取值进行积分后才是概率。
  3. 累积分布函数 ( cumulative distribution function，CDF ) 能完整描述一个实数随机变量 X 的概率分布，是概率密度函数的积分。对於所有实数 x，与 pdf 相对。
  1. 批量梯度下降 ( BGD )：每次都使用所有的 m 个样本来更新，容易找到全局最优解，但是 m 较大时速度较慢。
  3. 随机梯度下降 ( SGD )：每次只使用一个样本来更新，训练速度快，但是噪音较多，不容易找到全局最优解，以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。注意控制步长缩小，减少震荡。
  5. 小批量梯度下降 ( MBGD )：每次使用一部分样本来更新。
  1. 黑塞矩阵是由目标函数 f(x) 在点 X 处的二阶偏导数组成的 n*n 阶对称矩阵。
  2. 牛顿法：将 f(x) 在 x(k) 附近进行二阶泰勒展开：
  4. 其中，gk 是 f(x) 的梯度向量在 x(k) 的值，H(x(k)) 是 f(x) 的黑塞矩阵在点 x(k) 的值。牛顿法利用极小点的必要条件 f(x) 处的梯度为0，每次迭代中从点 x(k) 开始，假设，对二阶泰勒展开求偏导有，代入得到，即，以此为迭代公式就是牛顿法。
  1. DFP 算法：假设每一步，为使 Gk 1 满足拟牛顿条件，可使 Pk 和 Qk 满足，，例如取，，就得到迭代公式
  2. BFGS 算法：最流行的拟牛顿算法。考虑用 Bk 逼近黑塞矩阵，此时相应的拟牛顿条件是，假设每一步，则 Pk 和 Qk 满足，，类似得到迭代公式
  1. 先验概率就是事情发生前的预测概率。
  2. 后验概率是一种条件概率，它限定了事件为隐变量取值，而条件为观测结果。一般的条件概率，条件和事件可以是任意的。
  3. 贝叶斯公式 P(y|x) = ( P(x|y) * P(y) ) / P(x) 中，P(y|x) 是后验概率，P(x|y) 是条件概率，P(y) 是先验概率。
  1. 偏差：度量了学习算法的期望预测和真实结果偏离程度。
  2. 方差：度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响。
  3. 噪声：可以认为是数据自身的波动性，表达了目前任何学习算法所能达到泛化误差的下限。
  4. 泛化误差可以分解为偏差、方差与噪声之和。
  1. 无约束优化问题：通常使用求导，使导数为零，求解候选最优值。
  2. 有等式约束的优化问题：通常使用拉格朗日乘子法，即把等式约束用拉格朗日乘子和优化问题合并为一个式子，通过对各个变量求导使其为零，求解候选最优值。拉格朗日乘数法其实是 KKT 条件在等式约束优化问题的简化版。
  3. 有不等式约束的优化问题：通常使用 KKT 条件。即把不等式约束，等式约束和优化问题合并为一个式子。假设有多个等式约束 h(x) 和不等式约束 g(x)
  5. 则不等式约束引入的KKT条件如下：
  7. 实质是最优解在 g(x)<0 区域内时，约束条件不起作用，等价于对 μ 置零然后对原函数的偏导数置零；当 g(x)=0 时与情况2相近。结合两种情况，那么只需要使 L 对 x 求导为零，使 h(x) 为零，使 μg(x) 为零三式即可求解候选最优值。
  1. 准确度，最常用，但在数据集不平衡的情况下不好。
  2. Precision ( 精确度/查准率 )：P=TP/(TP FP)
  3. Recall ( 召回率/查全率 )：R=TP/(TP FN)
  4. Fβ 度量：，当 β=1 时退化为 F1 度量，是精确率和召回率的调和均值。
  5. TPR ( 真正例率 )：TPR=TP/(TP FN)
  6. FPR ( 假正例率 )：FPR=FP/(TN FP)
  7. PR 曲线：纵轴为 Precision，横轴为 Recall，一般使用平衡点 ( BEP，即 Precsion=Recall 的点 ) 作为衡量标准。
  8. ROC ( 接受者操作特征 ) 曲线：纵轴为 TRP，横轴为 FPR，在绘图时将分类阈值依次设为每个样例的预测值,再连接各点。ROC 曲线围住的面积称为 AOC，AOC 越大则学习器性能越好。
  1. 损失函数度量模型一次预测的好坏。常用的损失函数有：0-1损失函数，平方损失函数，绝对损失函数，对数似然损失函数。
  2. 损失函数的期望是理论上模型关于联合分布 P(X，Y) 的平均意义下的损失，称为风险函数，也叫期望风险。但是联合分布是未知的，期望风险不能直接计算。
  3. 当样本容量 N 趋于无穷时经验风险趋于期望风险，但现实中训练样本数目有限。
  1. 模型关于训练数据集的平均损失称为经验风险。经验风险最小化的策略就是最小化经验风险。当样本数量足够大时学习效果较好。比如当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。但是当样本容量很小时会出现过拟合。
  2. 结构风险最小化等于正则化。结构风险在经验风险上加上表示模型复杂度的正则化项。比如当模型是条件概率分布，损失函数是对数损失函数，模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计。
二、感知机

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

三、k 近邻法

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

  1. 距离：特征空间中两个实例点的距离是相似程度的反映，k 近邻算法一般使用欧氏距离，也可以使用更一般的 Lp 距离或 Minkowski 距离。
  2. k 值：k 值较小时，整体模型变得复杂，容易发生过拟合。k 值较大时，整体模型变得简单。在应用中 k 一般取较小的值，通过交叉验证法选取最优的 k 。
  3. 分类决策规则：k 近邻中的分类决策规则往往是多数表决，多数表决规则等价于经验风险最小化。
  1. kd 树就是一种对 k 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd 树更适用于训练实例数远大于空间维数时的 k 近邻搜索。
  2. 构造，可以通过如下递归实现：在超矩形区域上选择一个坐标轴和此坐标轴上的一个切分点，确定一个超平面，该超平面将当前超矩形区域切分为两个子区域。在子区域上重复切分直到子区域内没有实例时终止。通常依次选择坐标轴和选定坐标轴上的中位数点为切分点，这样可以得到平衡 kd 树。
  3. 搜索：从根节点出发，若目标点 x 当前维的坐标小于切分点的坐标则移动到左子结点，否则移动到右子结点，直到子结点为叶结点为止。以此叶结点为 " 当前最近点 "，递归地向上回退，在每个结点：(a) 如果该结点比当前最近点距离目标点更近，则以该结点为 " 当前最近点 " ( b ) " 当前最近点 " 一定存在于该结点一个子结点对应的区域,检查该结点的另一子结点对应的区域是否与以目标点为球心，以目标点与 " 当前最近点 " 间的距离为半径的超球体相交。如果相交，移动到另一个子结点，如果不相交，向上回退。持续这个过程直到回退到根结点，最后的 " 当前最近点 " 即为最近邻点。
四、朴素贝叶斯

朴素贝叶斯是基于贝叶斯定理和特征条件独立假设的分类方法。首先学习输入/输出的联合概率分布，然后基于此模型，对给定的输入 x，利用贝叶斯定理求出后验概率最大的输出 y。属于生成模型。

五、决策树

决策树是一种基本的分类与回归方法。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。主要优点是模型具有可读性,分类速度快。

  1. 信息熵：熵是衡量随机变量不确定性的度量。熵越大，随机变量的不确定性就越大。信息熵是信息量的期望。条件熵表示在已知随机变量X的条件下随机变量Y的不确定性。
  2. 信息增益：表示得知特征 X 的信息而使得类 Y 的信息的不确定性减少的程度。定义为集合 D 的经验熵与特征 A 在给定条件下 D 的经验条件熵之差，也就是训练数据集中类与特征的互信息。
  3. 信息增益算法：计算数据集 D 的经验熵，计算特征 A 对数据集 D 的经验条件熵，计算信息增益,选取信息增益最大的特征。
  4. 信息增益比：信息增益值的大小是相对于训练数据集而言的,并无绝对意义。使用信息增益比可以对这一问题进行校正。
  1. ID3 算法：核心是在决策树各个结点上应用信息增益准则选择信息增益最大且大于阈值的特征,递归地构建决策树。ID3 相当于用极大似然法进行概率模型的选择。由于算法只有树的生成，所以容易产生过拟合。
  2. C4.5 算法：C4.5 算法与 ID3 算法相似，改用信息增益比来选择特征。
  1. 在学习时过多考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，产生过拟合现象。解决方法是对已生成的决策树进行简化，称为剪枝。
  2. 设树的叶结点个数为 |T|，每个叶结点有 Nt 个样本点，其中 k 类样本点有 Ntk 个，剪枝往往通过极小化决策树整体的损失函数来实现，其中经验熵。剪枝通过加入 a|T| 项来考虑模型复杂度，实际上就是用正则化的极大似然估计进行模型选择。
  3. 剪枝算法：剪去某一子结点，如果生成的新的整体树的损失函数值小于原树，则进行剪枝，直到不能继续为止。具体可以由动态规划实现。
  1. CART 既可以用于分类也可以用于回归。它假设决策树是二叉树，内部结点特征的取值为 " 是 " 和 " 否 " 。递归地构建二叉树，对回归树用平方误差最小化准则，对分类数用基尼指数最小化准则。
  2. 回归树的生成：在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域。选择第 j 个变量和它取的值 s 作为切分变量和切分点，并定义两个区域，遍历变量 j，对固定的 j 扫描切分点 s，求解。用选定的对 ( j，s ) 划分区域并决定相应的输出值直到满足停止条件。
  3. 基尼指数：假设有 K 个类，样本属于第 k 类的概率为 pk，则概率分布的基尼指数为，表示不确定性。在特征 A 的条件下集合 D 的基尼指数定义为，表示分割后集合 D 的不确定性。基尼指数越大，样本集合的不确定性也就越大。
  4. 分类树的生成：从根结点开始，递归进行以下操作：设结点的训练数据集为 D，对每个特征 A 和其可能取的每个值 a，计算 A=a 时的基尼指数，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点，生成两个子结点，直至满足停止条件。停止条件一般是结点中的样本个数小于阈值，或样本集的基尼指数小于阈值，或没有更多特征。
  5. CART 剪枝:
  6. Tt 表示以 t 为根结点的子树，|Tt| 是 Tt 的叶结点个数。可以证明当时，Tt 与 t 有相同的损失函数值，且t的结点少，因此 t 比 Tt 更可取，对 Tt 进行剪枝。自下而上地对各内部结点 t 计算，并令 a=min(g(t))，自上而下地访问内部节点 t，如果有 g(t)=a，进行剪枝，并对 t 以多数表决法决定其类，得到子树 T，如此循环地生成一串子树序列，直到新生成的 T 是由根结点单独构成的树为止。利用交叉验证法在子树序列中选取最优子树。
六、logistic 回归和最大熵模型
  1. 改进的迭代尺度法 ( IIS )：假设当前的参数向量是 w，如果能找到一种方法 w->w δ 使对数似然函数值变大，就可以重复使用这一方法，直到找到最大值。
  2. 逻辑斯谛回归常应用梯度下降法，牛顿法或拟牛顿法。
七、支持向量机
  1. 当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。利用间隔最大化得到唯一最优分离超平面和相应的分类决策函数称为线性可分支持向量机。
  2. 函数间隔：一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面确定的情况下，|wx b| 能够相对地表示点x距离超平面的远近，而 wx b 与 y 的符号是否一致能够表示分类是否正确。所以可用来表示分类的正确性及确信度，这就是函数间隔。注意到即使超平面不变，函数间隔仍会受 w 和 b 的绝对大小影响。
  3. 几何间隔：一般地，当样本点被超平面正确分类时，点 x 与超平面的距离是，其中 ||w|| 是 w 的 l2 范数。这就是几何间隔的定义。定义超平面关于训练数据集 T 的几何间隔为超平面关于 T 中所有样本点的几何间隔之最小值。可知，当 ||w||=1 时几何间隔和函数间隔相等。
  4. 硬间隔最大化：对线性可分的训练集而言，这里的间隔最大化又称为硬间隔最大化。直观解释是对训练集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。求最大间隔分离超平面即约束最优化问题：
  5. 将几何间隔用函数间隔表示
  6. 并且注意到函数间隔的取值并不影响最优化问题的解，不妨令函数间隔=1，并让最大化 1/||w|| 等价为最小化 ||w||^2/2，问题变为凸二次规划问题
  7. 支持向量和间隔边界：与分离超平面距离最近的样本点的实例称为支持向量。支持向量是使最优化问题中的约束条件等号成立的点。因此对 y= 1 的正例点和 y=-1 的负例点，支持向量分别在超平面 H1：wx b= 1 和 H2：wx b=-1 。H1 和 H2 平行，两者之间形成一条长带，长带的宽度 称为间隔，H1 和 H2 称为间隔边界。在决定分离超平面时只有支持向量起作用，所以支持向量机是由很少的"重要的"训练样本确定的。由对偶问题同样可以得到支持向量一定在间隔边界上。
  8. 对偶算法：引进拉格朗日乘子，定义拉格朗日函数
  1. 根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题：
  2. 先求对 w，b 的极小值。将 L(w，b，a) 分别对 w，b 求偏导数并令其等于0，得
  3. 代入拉格朗日函数得
  4. 这就是极小值。
  5. 接下来对极小值求对 a 的极大，即是对偶问题
  6. 将求极大转换为求极小
  7. 由KKT条件成立得到
  8. 其中 j 为使 aj*>0 的下标之一。所以问题就变为求对偶问题的解 a*，再求得原始问题的解 w*，b*，从而得分离超平面及分类决策函数可以看出 w* 和 b* 都只依赖训练数据中 ai*>0 的样本点 (xi，yi)，这些实例点 xi 被称为支持向量。
  1. 如果训练数据是线性不可分的，那么上述方法中的不等式约束并不能都成立，需要修改硬间隔最大化，使其成为软间隔最大化。
  2. 线性不可分意味着某些特异点不能满足函数间隔大于等于1的约束条件，可以对每个样本点引进一个松弛变量，使函数间隔加上松弛变量大于等于1，约束条件变为，同时对每个松弛变量，支付一个代价，目标函数变为，其中 C>0 称为惩罚参数，C 值越大对误分类的惩罚也越大。新目标函数包含了两层含义：使间隔尽量大，同时使误分类点的个数尽量小。
  3. 软间隔最大化，学习问题变成如下凸二次规划问题：
  4. 可以证明 w 的解是唯一的，但 b 的解存在一个区间。线性支持向量机包含线性可分支持向量机，因此适用性更广。
  5. 对偶算法：原始问题的对偶问题是,构造拉格朗日函数
  6. 先求对 w，b，ξ 的极小值，分别求偏导并令导数为0，得
  7. 代入原函数，再对极小值求 a 的极大值，得到
  8. 利用后三条约束消去 μ，再将求极大转换为求极小，得到对偶问题
  9. 由 KKT 条件成立可以得到
  10. j 是满足 0<aj*<C 的下标之一。问题就变为选择惩罚参数 C>0，求得对偶问题 ( 凸二次规划问题 ) 的最优解 a*，代入计算 w* 和 b*，求得分离超平面和分类决策函数。因为 b 的解并不唯一，所以实际计算 b* 时可以取所有样本点上的平均值。
  1. 支持向量：在线性不可分的情况下，将对应与 ai*>0 的样本点 (xi，yi) 的实例点xi称为支持向量。软间隔的支持向量或者在间隔边界上，或者在间隔边界与分类超平面之间，或者再分离超平面误分一侧。
  2. 合页损失函数：可以认为是0-1损失函数的上界，而线性支持向量机可以认为是优化合页损失函数构成的目标函数。
  1. 如果分类问题是非线性的，就要使用非线性支持向量机。主要特点是使用核技巧。
  2. 非线性分类问题，用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间，然后在新空间里用线性分类学习方法从训练数据中学习分类模型。
  3. 核函数：设 X 是输入空间(欧式空间的子集或离散集合)，H 为特征空间(希尔伯特空间)，一般是高维甚至无穷维的。如果存在一个从 X 到 H 的映射使得对所有 x，z 属于 X，函数 K(x,z) 满足条件，点乘代表内积，则称 K(x，z) 为核函数。
  4. 核技巧：基本思想是通过一个非线性变换将输入空间对应于一个特征空间，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型 ( 支持向量机 ) 。在学习和预测中只定义核函数 K(x，z)，而不显式地定义映射函数。对于给定的核 K(x，z)，特征空间和映射函数的取法并不唯一。注意到在线性支持向量机的对偶问题中，目标函数和决策函数都只涉及输入实例与实例之间的内积，xi`xj 可以用核函数 K(xi，xj)=Ф(xi)`Ф(xj) 来代替。当映射函数是非线性函数时，学习到的含有核函数的支持向量机是非线性分类模型。在实际应用中，往往依赖领域知识直接选择核函数。
  5. 正定核：通常所说的核函数是指正定核函数。只要满足正定核的充要条件，那么给定的函数 K(x，z) 就是正定核函数。设K是定义在 X*X 上的对称函数，如果任意 xi 属于 X，K(x，z) 对应的 Gram 矩阵是半正定矩阵，则称 K(x，z) 是正定核。这一定义在构造核函数时很有用，但要验证一个具体函数是否为正定核函数并不容易，所以在实际问题中往往应用已有的核函数。
  6. 算法：选取适当的核函数 K(x，z) 和适当的参数 C，将线性支持向量机对偶形式中的内积换成核函数，构造并求解最优化问题
  7. 选择最优解 a* 的一个正分量 0<aj*<C 计算，构造决策函数
  1. 多项式核函数 ( polynomial kernel function )：
  2. 对应的支持向量机是一个 p 次多项式分类器，分类决策函数为
  3. 高斯核函数 ( Gaussian krenel function )：
  4. 对应的支持向量机是高斯径向基函数 ( RBF ) 分类器。分类决策函数为
  5. 字符串核函数 ( string kernel function )：
  6. 核函数不仅可以定义在欧氏空间上，还可以定义在离散数据的集合上。字符串核函数给出了字符串中长度等于 n 的所有子串组成的特征向量的余弦相似度。
  1. SMO 是一种快速求解凸二次规划问题
  2. 的算法。
  3. 基本思路是：如果所有变量都满足此优化问题的 KKT 条件，那么解就得到了。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。不断地将原问题分解为子问题并对子问题求解，就可以求解原问题。注意子问题两个变量中只有一个是自由变量，另一个由等式约束确定。
  4. 两个变量二次规划的求解方法：假设选择的两个变量是 a1，a2，其他变量是固定的，于是得到子问题
  5. ε 是常数，目标函数式省略了不含 a1，a2 的常数项。考虑不等式约束和等式约束，要求的是目标函数在一条平行于对角线的线段上的最优值
  6. 问题变为单变量的最优化问题。假设初始可行解为 aold，最优解为 anew，考虑沿着约束方向未经剪辑的最优解 anew，unc ( 即未考虑不等式约束 ) 。对该问题求偏导数，并令导数为0，代入原式，令
  7. 得到，经剪辑后 a2 的解是
  8. L 与 H 是 a2new 所在的对角线段端点的界。
  9. 变量的选择方法：在每个子问题中选择两个变量优化，其中至少一个变量是违反 KKT 条件的。第一个变量的选取标准是违反 KKT 条件最严重的样本点，第二个变量的选取标准是希望能使该变量有足够大的变化，一般可以选取使对应的 |E1-E2| 最大的点。在每次选取完点后，更新阈值 b 和差值 Ei 。
八、提升方法

提升 ( boosting ) 是一种常用的统计学习方法，是集成学习的一种。它通过改变训练样本的权重 ( 概率分布 )，学习多个弱分类器 ( 基本分类器 )，并将这些分类器线性组合来构成一个强分类器提高分类的性能。

  1. AdaBoost 提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。然后采取加权多数表决的方法组合弱分类器。
  2. 算法：首先假设训练数据集具有均匀的权值分布 D1，使用具有权值分布 Dm 的训练数据集学习得到基本分类器 Gm(x)，计算分类误差率和 Gm(x) 的系数，更新训练数据集的权值分布其中
  3. Zm 是使 Dm 1 成为概率分布的规范化因子
  4. 重复上述操作 M 次后得到 M 个弱分类器，构建线性组合得到最终分类器
  5. AdaBoost 算法也可以理解成模型为加法模型，损失函数为指数函数，学习算法为前向分步算法的二类分类学习方法。
  1. 提升树是模型为加法模型，算法为前向分布算法，基函数为决策树的提升方法。第 m 步的模型是，通过经验风险极小化确定下一棵决策树的参数。不同问题的提升树学习算法主要区别在于使用的损失函数不同。
  2. 二类分类问题：只需将 AdaBoost 算法中的基本分类器限制为二类分类数即可。
  3. 回归问题：如果将输入空间划分为J个互不相交的区域，并且在每个区域上确定输出的常量 Cj，那么树可表示为，
  4. 其中
  5. 提升树采用前向分步算法：
  6. 当采用平方误差损失函数时，损失变为
  7. 其中r是当前模型拟合数据的残差。每一步都只需拟合残差学习一个回归树即可。
  8. 梯度提升树 ( GBDT )：利用最速下降法的近似方法来实现每一步的优化，关键在于用损失函数的负梯度在当前模型的值作为回归问题中提升树算法中的残差的近似值,每一步以此来估计回归树叶结点区域以拟合残差的近似值，并利用线性搜索估计叶结点区域的值使损失函数最小化，然后更新回归树即可。
  1. 在优化时用到了二阶导数信息。
  2. 在代价函数里加入了正则项。
  3. 每次迭代后都将叶子结点的权重乘上一个系数，削弱每棵树的影响。
  4. 列抽样。
  5. 在训练前对数据进行排序，保存为 block 结构，并行地对各个特征进行增益计算。
九、EM 算法EM 算法是一种迭代算法，用于含有隐变量的概率模型参数的极大似然估计。每次迭代由两步组成：E 步，求期望 ( expectation )，M 步，求极大值 ( maximization )，直至收敛为止。
  1. 选择参数的初始值 θ(0)，开始迭代。注意 EM 算法对初值是敏感的。
  2. E 步：θ(i) 为第 i 次迭代参数θ的估计值，在第 i 1 次迭代的E步，计算
  3. P(Z|Y，θ(i)) 是在给定观测数据 Y 和当前参数估计 θ(i) 下隐变量数据Z的条件概率分布。
  4. M 步：求使 Q(θ，θ(i)) 极大化的 θ，确定第 i 1 次迭代的参数的估计值
  5. 重复2和3直到收敛，一般是对较小的正数 ε1 和 ε2 满足
  6. 则停止迭代。
  1. 取参数的初始值开始迭代
  2. E 步：计算分模型k对观测数据 yj 的响应度
  3. M 步：计算新一轮迭代的模型参数
  4. 重复2和3直到对数似然函数
  5. 收敛。
十、隐马尔可夫模型 ( HMM )

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态序列，再由各个状态生成一个观测而产生观测随机序列的过程。

设 Q 是所有可能的状态的集合，V 是所有可能的观测的集合

数据分析需要懂算法吗（超全干货2万字全文）(1)

，I 是长度为T的状态序列，O 是对应的观测序列

数据分析需要懂算法吗（超全干货2万字全文）(2)

，A 是状态转移概率矩阵

数据分析需要懂算法吗（超全干货2万字全文）(3)

，aij 表示在时刻t处于状态 qi 的条件下在时刻 t 1 转移到状态 qj 的概率。B 是观测概率矩阵

数据分析需要懂算法吗（超全干货2万字全文）(4)

，bij 是在时刻 t 处于状态 qj 的条件下生成观测 vk 的概率。π 是初始状态概率向量

数据分析需要懂算法吗（超全干货2万字全文）(5)

，πi 表示时刻 t=1 处于状态 qi 的概率。隐马尔可夫模型由初始状态概率向量 π，状态转移概率矩阵 A 以及观测概率矩阵 B 确定。π 和 A 决定即隐藏的马尔可夫链，生成不可观测的状态序列。B 决定如何从状态生成观测，与状态序列综合确定了观测序列。因此，隐马尔可夫模型可以用三元符号表示

数据分析需要懂算法吗（超全干货2万字全文）(6)

。

  1. 齐次马尔可夫性假设：假设隐藏的马尔可夫链在任意时刻 t 的状态只依赖于其前一时刻的状态。
  2. 观测独立性假设：假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态。
  1. 直接计算法：最直接的方法是列举所有可能长度为 T 的状态序列，求各个状态序列I与观测序列 O 的联合概率，但计算量太大，实际操作不可行。
  2. 前向算法：定义到时刻 t 部分观测序列为 o1~ot 且状态为 qi 的概率为前向概率，记作初始化前向概率，递推，对 t=1~T-1，得到减少计算量的原因在于每一次计算直接引用前一个时刻的计算结果，避免重复计算。
  3. 后向算法：定义在时刻 t 状态为qi的条件下，从 t 1 到 T 的部分观测序列为 oi 1~oT 的概率为后向概率，记作初始化后向概率，递推，对 t=T-1~1，，得到
  1. 监督学习：估计转移概率
  2. 和观测概率
  3. 初始状态概率 πi 的估计为 S 个样本中初始状态为 qi 的频率。
  4. 非监督学习 ( Baum-Welch 算法 )：将观测序列数据看作观测数据 O，状态序列数据看作不可观测的隐数据 I。首先确定完全数据的对数似然函数求 Q 函数
  5. 用拉格朗日乘子法极大化Q函数求模型参数
  1. 近似算法：在每个时刻t选择在该时刻最有可能出现的状态 it*，从而得到一个状态序列作为预测的结果。优点是计算简单，缺点是不能保证状态序列整体是最有可能的状态序列。
  2. 维特比算法：用动态规划求概率最大路径，这一条路径对应着一个状态序列。从 t=1 开始，递推地计算在时刻t状态为i的各条部分路径的最大概率，直至得到时刻 t=T 状态为i的各条路径的最大概率。时刻 t=T 的最大概率即为最优路径的概率 P*，最优路径的终结点it*也同时得到，之后从终结点开始由后向前逐步求得结点，得到最优路径。
十一、统计学习方法总结

数据分析需要懂算法吗（超全干货2万字全文）(7)

--- 以下内容并非出自《统计学习方法》---

十二、神经网络

神经元 ( 感知器 ) 接收到来自 n 个其他神经元传递过来的输入信号，这些输入信号通过带权重的连接进行传递，神经元将接收到的总输入值与神经元的阈值进行比较,然后通过激活函数处理以产生神经元的输出。把许多个这样的神经元按一定的层次结构连接起来就得到了神经网络。一般使用反向传播 ( BP ) 算法来进行训练。

  1. 前向传播：将训练集数据输入，经过隐藏层，到达输出层并输出结果。
  2. 计算估计值与实际值之间的误差，并将该误差从输出层向输入层反向传播。
  3. 在反向传播的过程中，根据误差使用梯度下降与链式法则调整各种参数的值。
  4. 不断迭代直至收敛。
十三、K-Means

K-Means 是无监督的聚类算法。思想是对于给定的样本集，按照样本之间的距离大小将样本集划分为 K 个簇，让簇内的点尽量紧密地连在一起，而让簇间的距离尽量的大。

  1. 用先验知识或交叉验证选择一个合适的 k 值。
  2. 随机选择 k 个样本作为初始的质心。注意初始化质心的选择对最后的聚类结果和运行时间都有很大的影响。
  3. 计算每个样本点和各个质心的距离，将样本点标记为距离最小的质心所对应的簇。
  4. 重新计算每个簇的质心，取该簇中每个点位置的平均值。
  5. 重复2，3，4步直到 k 个质心都没有发生变化为止。
  1. 从输入样本点中随机选择一个点作为第一个质心。
  2. 计算每一个样本点到已选择的质心中最近质心的距离 D(x)。
  3. 选择一个新的样本点作为新的质心，选择原则是 D(x) 越大的点被选中的概率越大。
  4. 重复2和3直到选出 k 个质心。
十四、Bagging

Bagging 的弱学习器之间没有 boosting 那样的联系，它的特点在于 " 随机采样 "，也就是有放回采样。因此泛化能力很强。一般会随机采集和训练集样本数一样个数的样本。假设有 m 个样本，且采集 m 次，当 m 趋向无穷大时不被采集到的数据占 1/e，也就是36.8%，称为袋外数据，可以用来检测模型的泛化能力。Bagging 对于弱学习器没有限制，一般采用决策树和神经网络。

  1. 对于 t=1~T，对训练数据进行第 t 次随机采样，共采集 m 次，得到包含 m 个样本的采样集 Dm 。
  2. 用采样集 Dm 训练第 m 个弱学习器 Gm(x) 。
  3. 如果是分类，则用简单投票法。如果是回归，则取 T 个弱学习器结果的平均值。
十五、Apriori

Apriori 是常用的挖掘出数据关联规则的算法，用于找出数据值中频繁出现的数据集合。一般使用支持度或者支持度与置信度的组合作为评估标准。

十六、降维方法十七、引用
  1. 如何理解神经网络里面的反向传播算法？- 陈唯源的回答 - 知乎
  2. https://www.zhihu.com/question/24827633/answer/91489990
  3. 刘建平Pinard-博客园
  4. https://www.cnblogs.com/pinard/category/894694.html

十八、原文地址

https://www.cnblogs.com/limitlessun/p/8611103.html

,