机器学习

看的教材是统计学习方法第二版，这里尽可能用自己的话进行转述来加强记忆

有监督学习

1. 泛化误差是关于f的期望风险；注意区分期望风险与经验风险，一般用经验风险来估计期望风险，其误差就是泛化误差，泛化误差的上界由训练误差（经验风险）+一个参数组成，以Hoeffding不等式在损失函数取值[0，1]时推导
2. 生成模型学习数据整体的规律，需要的数据量大，还原联合概率P(X,Y)收敛更快，判别模型直接学习某个特征，提取特征进行判别。
3. 分类问题（输出为离散），标注问题（输出为序列，根据语义标注标签），回归问题（预测输入与输出的关系）。分类为核心，其他为分类的推广。
4. 精确率是预测对的正类/所有正类预测，召回率是预测对的正类/样本中实际的正类。（关注的类为正类，其他为负类）

感知机

• 原始形式：假设数据集是线性可分，进行划分$y=wx+b$，目标是得到一个能够将正负实例点完全正确分开的超平面。（若线性可分一定可以得到收敛的结果）（初值w,b可以选择不同的值，解也会不同）
• 损失函数选择真实数据值与模型输出值相乘，即$y_i*(wx_i+b)$,分别针对w与b求偏导得到其损失函数的梯度，用学习率×梯度来使损失函数不断变小
• 对偶形式：将w和b用实例$x_i$与$y_i$来的线性组合来求解系数
• Garm矩阵$G = [x_i \cdot x_j]_{N \times N}$

k近邻算法

• 对于新的输入实例，在数据集中选择与之最邻近的k个实例，将这k个实例的多数属于的类别判定为该输入实例的类别（多类表决规则）。
• 距离一般采用欧氏距离度量
• k近邻算法的实现：构造kd树，以二叉树为划分进行选择

朴素贝叶斯法

贝叶斯公式：$P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$用来得到后验概率

• 朴素贝叶斯法的基本方法：假设X的各个用于分类的特征之间是具有独立性的，将后验概率最大的类作为x的输出。即求$X=x$的条件下各种y的结果的概率，选择最大的作为其概率。

• 可以用极大似然估计来估计需要的先验概率（实际计算时，用样本中出现的频率估计为真实条件概率）。但可能出现概率为0的情况，在计算时频数上加一个固定的非负数来计算。该值为0时，就是极大似然估计，为1时，成为拉普拉斯平滑。

决策树

• 通常包括特征选择，决策树的生成、决策树的修剪

特征选择

• 决策树对训练数据集的特征进行划分，提取互斥的特征，使之对应数据的某一类。直至所有训练子集的数据被分类或没有合适的可以提取的特征（如果特征数量较多可以先进行特征的选择）

• 遵循损失函数最小化的目标进行学习与训练

• 熵与条件熵中的概率由数据估计得到时，分别成为经验熵、经验条件熵。

• 信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。等价于$g(Y,X)=H(Y)-H(Y|X)$

  其中，Y表示最终分类的结果，X表示选取的一个特征

• 计算各个特征的信息增益，选择最大的为最优特征

• 信息增益比：$g_R(Y,X)=g(Y,X)/H_x(Y)$其中，$H_x$中的$p_x$为符合$x$特征的数据集的数量比总数据集的数量

决策树的生成

• ID3算法：选择信息增益最大的作为根节点，再用剩下的样本继续按照同样方式构建子节点的根节点。（容易过拟合）如：假设为二分类，A特征信息增益最大：A特征为根结点，符合A特征且为正类的，直接为叶结点，不符合A特征的一侧，继续选择剩下的信息增益最大的特征B，判断是否符合B以及属于哪一类，直至正负类分完。
• C4.5生成算法：当信息增益比大于等于阈值（阈值自定义）时，选择信息增益比最大的特征进行分类

决策树的剪枝

• 在已生成的树上裁剪子树或枝，将其根节点或父节点作为新的叶结点。剪枝是为了减轻过拟合的问题。

• 损失函数为要剪掉部分的节点的经验熵+模型复杂度*$\alpha$,同时控制模型与训练数据的拟合程度与模型的复杂度，利用损失函数最小进行剪枝`，当裁剪后的树的损失函数值低于裁剪前，就进行裁剪。

• 分类与回归树模型（CART）：假设决策树是二叉树，左是右否来构建二叉树。其生成就是构建二叉决策树的过程。回归树用平方误差最小化准则，分类树用基尼指数最小化准则。这两个准则都是用来找最优切分变量和最优切分点。这两个值也是损失函数的取值。

• 回归树采用启发式的方法，选择某个变量和值作为切分变量和切分点，然后不断寻找最优切分变量和最优切分点，对每个区域不断进行划分。这样的树叫最小二乘回归树。（遍历所有，局部最优）

• 基尼指数：对于某集合D的基尼指数，其为1-((所有对应的D的子集合与D的比值)的平方的求和));某条件下的基尼指数，就是被某条件分割的两个集合的基尼指数分别按照其占总集合比例的和。

• CART剪枝：将$\alpha$逐渐增大划分区域，如果结点更少且损失函数值相同，就进行剪枝得到一个子树。将所有的子树序列交叉验证，损失函数值最小的被认定为最优的决策树。

logstic回归与最大熵模型

logstic

• logsitc分布是一种密度函数图形为S形曲线，对（u,1/2）中心对称的分布。

• 主要是关于内积w*x+b的计算，w为权值向量，b为偏置（因为是求内积，有时候会把b写进w的参数，此时x对应项为1）。二项logstic回归：

  $p(y=1|x)=\frac{exp(w\cdot x+b)}{1+exp(w\cdot x+b)}$

• 用极大似然估计法来估计模型参数，得到w的估计值。可拓展为多项logistic来进行多组的分类

最大熵

• 在满足约束条件的情况下选择熵最大的模型，在满足约束条件下尽可能选择等概率

• 最大熵模型：如果x、y符合某一事实，则f(x,y)=1，反之为0，用数据集求出p(x),p(x,y)的经验概率分布，分别计算f(x,y)关于经验分布P(x,y)的期望与f(x,y)关于模型P(y|x)与经验分布p(x)的期望，二者相等时，其中熵最大的模型称之为最大熵模型

• 最大熵模型的学习：通过求解约束最优化问题所得的解就是最大熵模型学习的解。先求拉格朗日函数，定义算子w0、w1，分别对各个值求偏导，令偏导为0，得到关于各个取值与w1、w0的关系；再对w0、w1求偏导并令其为0，从而得到要求的概率分布。

• 最大熵模型的学习中的对偶函数的极大化等价于对数似然函数极大化。

• 无约束最优化问题的求解算法有改进的迭代尺度法，梯度下降法、拟牛顿法

支持向量机

• 希尔波特空间：无限维但仍然可以用长度和角度来描述坐标的空间

• 支持向量机要找分类间隔最大的超平面，即最优超平面，只有一个结果，而感知机可以得到多种结果的超平面

• 核函数用来升维

• 数据集如果线性可分，采用硬间隔，要求所有样本被正确分类到间隔边界之外；如果近似线性可分，采用软间隔，允许一定样本的越界；如果线性不可分，用核函数升维后，用软间隔来找超平面。距离超平面越远，执行难度越高

• 函数间隔：距离超平面的距离；几何间隔：将间隔归一化，使得间隔不因为参数的线性变化而变化。

• 支持向量：距离超平面距离最近的样本点的实例

• 若线性可分，则最优超平面存在且唯一，此时为线性可分支持向量机，求解凸优化问题（约束最优化问题），w，b唯一；若线性不可分，引进松弛变量，设立惩罚参数，此时为线性支持向量机，求解凸二次规划问题得到最优超平面，但w唯一，b可能不唯一。若非线性，通过核函数与软间隔最大化，得到的分类决策函数，非线性支持向量机。

• 线性支持向量机的学习也可以转化为合页损失函数的无约束最小化问题

• 核函数是映射后的变量的内积，核技巧就是只定义核函数，而不显示地定义映射函数，由于支持向量机中的计算只涉及内积运算，因此都可以用核函数来替换，学习隐式地在特征空间进行。实际应用中往往根据领域知识经验来直接选择核函数，但需要通过实验验证其有效性。

• 通常核函数指正定核函数，其次还有多项式核函数、高斯核函数、字符串核函数等

• 序列最小优化算法（SMO）：用于高效地实现支持向量机学习的算法，不断将原二次规划问题分解为只有两个变量的二次分解问题。

提升方法

• 提升方法应用广泛且有效，它解决了单一模型预测精度不足和对复杂数据适应性差的问题。

• 提升方法本质上是采用加法模型（基函数的线性组合）与前向分布算法（每步只学习一个基函数和参数，使其逐渐逼近最佳函数）

• 强可学习：在概率近似正确学习的框架下，存在一个多项式的学习算法能够学习一个类，且正确率很高，则该类强可学习

• 弱可学习：正确率仅比随即猜测策略好，但二者被证明其实可以是等价的

• AdaBoost算法，先利用训练数据学习一系列弱分类器（分类规则较为粗糙的），再将弱分类器线性组合成一个强分类器（这是前向分布加法算法的特例）

• 提升树：以分类树或回归树为基本分类器的方法，提升树被认为统计学习中性能最好的方法之一。即以决策树作为基函数的提升方法。

• 梯度提升算法：利用损失函数的负梯度在当前模型的值作为回归问题提升树中算法残差的近似值，拟合一个回归树，从而降低一般损失函数的优化难度。

EM算法

• 概率模型中既含有观测变量，又有隐变量或潜在变量时，不能直接用极大似然估计或者贝叶斯估计来估计模型参数，em算法来解决这种情况下的极大似然估计值

• 应用场景：有三枚不同硬币，第一枚硬币决定选择后面的哪枚硬币，取第二枚硬币的结果为最终结果。但只能观测到最后的结果，不知道是哪枚硬币，估计三枚硬币同时正面的概率

• em算法：先定参数初值，计算该概率下的某种情况的概率，然后计算新估计值，不断迭代直至模型参数的值收敛。（注意最终结果受到初值的影响）同时，只能保证收敛到稳定点，而不能保证收敛到极大值点，需要选择多个不同初值迭代并将最终结果比较。

• EM算法也可用于生成模型的无监督学习中，即有时候训练数据只有输入没有对应的输出。

• EM算法用处广泛，还可用于高斯混合模型和隐马尔可夫模型等

• 高斯混合模型假设所有的数据点都是由多个不同的高斯分布（正态分布）混合叠加产生的。

隐马尔可夫模型

• 定义：关于时序的概率模型，用于标注问题，属于生成模型，用于语音识别、自然语言处理、生物信息、模式识别等领域。该模型由初始概率分布、状态转移概率分布、观测概率分布组成。前两者生成不可观测的状态序列，后者确定如何从状态生成观测，三者联合确定如何生成观测序列
• 隐藏的马尔可夫链任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻t无关
• 任意时刻的观测只依赖于该时刻的马尔可夫链状态，与其他观测状态无关。

概率计算的方式

• 直接计算法（理论上）按照概率公式列举所有可能长度为T的状态序列，求其与观测序列的联合概率，再对所有可能的状态序列求和，得到模型参数下的观测序列的概率。实际计算量太大，不可行。

• 前向学习：在某一时刻的指定状态下，从开始到该时刻的观测序列的概率为前向概率，递推求得前向概率和观测序列概率。本质是基于状态序列的路径结构递推计算，每一次计算直接引用前一个时刻的计算结果

• 后向学习：在某一时刻的指定状态下，从下一时刻到结束时刻T的观测序列的概率为后向概率，递推求后向概率与观测序列

计算方法

• 监督学习下：用极大似然估计的方法来估计隐马尔可夫模型的参数
• 无监督学习下：只包含观测序列而没有对应的状态序列，采用Baum-Welch算法，将隐马尔可夫模型看作一个含有隐变量的概率模型，参数用EM算法实现

预测算法

• 近似算法：某个时刻t选择最用可能出现的状态，从而得到状态序列。计算简单但是不能保证其整题是最有可能的序列。
• 维特比算法：采用动态规划求最优路径，每个路径对应一个状态序列。

条件随机场

• 条件随机场是一组输入变量X的条件下，输出一组随机变量Y的条件概率分布模型，可用于不同的预测问题。它假设输出变量之间的来拟合概率分布构成概率无向图模型，即马尔可夫随机场。

• 成对马尔可夫性：指定随机变量组的条件下，另外两个随机变量是条件独立的；局部马尔可夫性：指定随机变量组条件下，随机变量与另一个随机变量组是独立的。全局马尔可夫性：指定随机变量组条件下，另外两个随机变量组是独立的。

• 概率无向图模型（马尔可夫随机场）：联合概率分布满足某一种马尔可夫性

• 概率计算：递归构造前向-后向向量，然后用其计算联合分布与条件分布的数学期望。

• 参数学习的方法：极大似然估计，改进的迭代尺度法，拟牛顿法。

• 预测算法：维特比算法

无监督学习

• 无监督学习是从无标注的数据进行学习，主要包括聚类、降维、概率估计。为了探寻数据中的规律，它通常需要大量的数据。其基本思想是对给定数据进行某种压缩

基本问题

• 聚类：硬聚类每种数据只属于一类；软聚类每种数据属于多类
• 降维：高维数据转为低维数据，降维的过程就是学习降维模型的过程，用于发现高维数据中的统计规律。
• 概率模型估计：假设数据由概率模型生成，目标是找到最有可能生成数据的结构和参数
• 话题分析：发现文本集中每个文本的话题
• 图分析

聚类方法

• 聚类将针对的样本按照其相似度或距离进行归类
• 聚类分为层次聚类和k均值聚类。层次聚类有自上而下（分裂）（将整体作为一类逐渐分开）和自下而上（聚合）

相似度或距离

相似度或距离用来评估数据之间的关系

• 闵可夫斯基距离：

  $d_{ij} = \left( \sum_{k=1}^{m} |x_{ki} - x_{kj}|^p \right)^{\frac{1}{p}}$

  p为1时是曼哈顿距离，p为2时是欧氏距离，p为无穷时是切比雪夫距离。

• 马哈拉诺比斯距离：也称马氏距离，与各个分量的相关性有关，该距离越大相似度越小

• 相关系数，绝对值越接近1越相似

• 夹角余弦：越接近1越相似

• 类或簇是样本的子集，任意两个样本的距离小于指定正数，则为一类。

层次聚类

• 层次聚类将每个样本分到一个类，然后按照一定规则，进行合并，直到满足结束条件或合成为1类。它需要满足以下三个要素：距离或相似度、合并规则、停止条件。
• 分裂聚类与层次聚类相反

k均值聚类

• 选定k个中心点，找距离最近的地方聚类，然后取每类的样本的均值作为新的中心，直至收敛。
• 这是个迭代算法，不能保证全局最优，不同初始中心点会导致不同的结果，k值也需要不断尝试

奇异值分解（SVD）（推导定理略）

• 矩阵的奇异值分解是指将mxn的实矩阵A分解为一个m阶正交矩阵、n阶正交矩阵、mxn阶的对角矩阵。任意实矩阵一定存在奇异值分解。
• 奇异值分解包括紧奇异值分解（秩与原矩阵相同）和截断奇异值（秩比原矩阵低）分解。
• 奇异值分解对应一次旋转变换、一次缩放变换、一次旋转变换。
• 矩阵的截断奇异值分解可以得到平方损失意义下的矩阵最优近似

主成分分析(PCA)

• 主要用于降维，构造出线性无关的变量来表示数据集中线性相关的变量，从而达到降维的效果。
• 根据降维后的方差贡献量来决定降低的维数，贡献量越高，损失的信息越少。
• 样本总成分分析与总体主成分分析的差距只有协方差矩阵，计算方法一致
• 采用特征值分解可以计算主成分分析，不过奇异值分解更优

潜在语义分析（LSA）

• 潜在语义分析用于文本的话题分析，使用非概率的话题分析模型，将文本集合表示为单词-文本矩阵，奇异值分解得到话题向量空间。

• 单词向量空间：对于一个文本，用一个向量表示该文本的语义，向量的每一维代表一个单词，值是频数或权值。向量空间的度量如内积表示文本之间的语义相似度。（简单，速度快，消耗少，但由于存在一词多义或多词一义，导致计算存在不精确）

• 话题向量空间：利用奇异值分解，将单词向量空间的矩阵进行分解，第一个正交矩阵为话题空间，第二个矩阵与第三个矩阵的结合为文本在话题空间中的表示

• 非负矩阵分解：如果一个矩阵的所有元素非负，则称该矩阵为非负矩阵。将一个非负矩阵近似分解为两个非负矩阵的乘积，为非负矩阵分解。分解后的第一个矩阵表示话题空间，第二个矩阵是文本在话题空间的表示。

概率潜在语义分析(PLSA)

• 概率潜在语义分析利用概率模型对文本集合进行话题分析，学习通常采用EM算法，通过迭代学习模型的参数
• 它有生成模型（文本生成话题、话题生成单词）、共现模型（描述单词-文本对的生成概率）。二者概率公式意义上是等价的，但是性质不同

马尔可夫链蒙特卡罗方法(MCMC)

• 定义：构建马尔可夫链产生样本序列，再用样本序列进行近似数值的计算。常用于概率分布的估计、定积分的近似计算、最优化问题的近似求解。

蒙特卡洛法

• 通过抽样的随机样本来对概率分布的特征进行推断，即用抽样得到的随机样本样本的特征来估计整体。一般蒙特拉洛法有直接抽样、接受拒绝抽样、重要性抽样等
• 接受-拒绝抽样：找一个直接抽样分布作为建议分布，按照原随机变量的概率密度与一个常数*直接抽样分布的概率密度函数的比例决定是否接受
• 求数学期望：用样本均值估计整体均值
• 积分计算：先转化为求某个函数的数学期望的形式，在用样本均值近似计算积分

马尔可夫链

• 定义：一个随机变量序列里每个时刻的随机变量的取值集合相同，称为状态空间。如果某时刻的随机变量值依赖于上一时刻，而不依赖任何其他变量，则称为具有马尔可夫性，具有马尔可夫性的随机序列称为马尔可夫链。

• 离散型马尔可夫链根据转移概率矩阵随时间而产生状态序列

• 平稳分布：存在状态空间上的一个分布，状态转移矩阵与该分布乘积仍是该分布，即以这个分布作为初始分布进行转移时，以后的每个时刻的状态分布都是该分布。

• 连续状态马尔可夫链由转移核来表示转移概率分布。

• 不可约性：从一个状态出发，一定能到达任意的另一个状态。如果不满足，则称该马尔可夫链可约

• 周期性：从一个状态出发到返回这个状态所用时间成一定的周期性

• 正常返：任意一个状态从其他状态出发，时间趋于无穷时，首次转移到这个状态的概率不为0

• 遍历定理：不可约、非周期、正常返的马克可夫链有唯一一个平稳分布

• 可逆马尔可夫链：任意状态任意时刻的两个不同状态，在彼此作为条件的情况下发生的概率与当前时刻的乘积相等。该马尔可夫链一定有唯一的平稳分布

马尔可夫链蒙特卡罗法

• 更适用于多元随机变量、密度函数非标准、随机变量各分量不独立。

• 过程：在随机变量的状态空间定义一个满足遍历定理的马尔可夫链，每个时刻随机游走得到一个样本，取其函数均值作为要计算的数学期望，这个遍历计算的时刻成为燃烧期。

• 它可以用于观测数据和模型都很复杂时的数学期望的计算

Metropolis-Hastings算法

• 转移核的游走方法：按建议分布抽样产生候选状态，按照接受分布决定是否接受该状态。
• 建议分布：对称分布、独立抽样等方式
• 满条件分布：条件概率分布中，除了当前变量之外，其他变量都作为条件出现，这种概率分布称为满条件概率分布
• 单分量Metropolis-Hastings算法：对多元变量的每一变量的条件分布分别进行抽样。

吉布斯抽样

• Metropolis-Hastings算法的特殊情况，但是更容易实现，被广泛使用
• 该抽样用于多元变量联合概率分布的抽象和估计，定义满条件概率分布，依次对进行抽样，得到样本的序列，它不断进行迭代，从抽到第一个样本开始，每一次迭代都得到联合分布的一个样本，最终得到序列样本。
• 可以利用概率分布的性质来提高抽样的效率，通过依赖条件概率分布的乘积的抽样来进行，从而大幅减少抽样的复杂度。

潜在迪利克雷分配（LDA)

• 该模型是潜在语义分析的扩展，用于文本数据挖掘、图像处理、生物信息处理等领域
• 过程：先随机生成一个文本的话题分布，在该文本的每个位置，依据话题分布生成话题，依据该话题的单词分布随机生成一个单词，直至最后一个位置生成整个文本

迪利克雷分布

• 多项分布：二项分布的扩展，每次独立实验可能出现的结果有k种，状态空间为k-1维。（二项分布的状态空间只有一维，记录成功或失败）
• 迪利克雷分布：多元连续随机变量的概率分布，常作为多项分布的先验分布使用。
• 共轭分布：若先验分布与后验分布属于同类，则称为共轭分布，好处是可以从先验分布计算后验分布

潜在迪利克雷分配模型（LDA）

• 这是概率图模型，以迪利克雷分布为多项分布的先验分布，学习就是给定文本集合，通过后验概率分布的估计推断所有模型的参数。即给定文本集合，学习每个文本的话题分布，以及每个话题的单词分布。
• 可以认为该模型是概率潜在语义分析的扩展。它的优点是使用了先验概率分布，防止学习过程中产生过拟合。
• 生成过程：给定单词集合、文本集合、话题集合、迪利克雷分布的超参数，先生成话题的单词分布，再生成文本的话题分布，最后生成话题作为单词对应的话题，然后生成单词。

LDA的吉布斯抽样算法

• LDA的学习（参数估计）是一个复杂的最优化问题，可以采用收缩的吉布斯抽样方法，将问题转化为后验概率分布，该分布表示在所有文本的单词序列给定条件下所有可能的话题序列的条件概率。
• 过程：对给定的所有单词序列随机指派一个话题，整体构成所有文本的话题序列，然后循环执行：每个位置上计算该位置的话题上的满条件概率分布，随机抽样得到该位置的新话题，分配给这个位置。迭代燃烧完毕后得到条件概率分布的样本，根据该样本计算模型参数

LDA的变分EM算法

• 变分推理：通过解析的方法计算模型的后验概率的近似值。过程为定义变分分布，推导其证据下界表达，用最优化方法对证据下界进行优化，得到最优分布作为后验分布的近似。

• 变分推理可以用迭代的方法最大化证据下界，该算法是em算法的推广，称为变分em算法

PageRank算法

• 在有向图上定义随机游走模型，沿有向图随机访问各个节点，极限情况下访问每个结点的概率收敛到平稳分布。
• 由于可能存在孤立的点，实际扩展到一般定义，转移矩阵一部分按照某结点连接出的所有结点的概率相等，另一部分是完全随机，到各个结点的概率一样。经过每一次与转移矩阵计算的迭代，得到收敛的值，这个值称为pagerank值，表示结点的相对重要度。可采用迭代、幂值（也是迭代并规范化结果向量）、代数的方式计算（矩阵求逆）