参考教材：《西瓜书》

决策树

划分选择

  1. 信息增益：

    1. 信息熵：对于样本集合 中的第k类样本所占比例为

    2. 假定离散属性a有V个可能的取值 ，设其中第v个分支节点包含D中所有在属性a上取值为 的样本，记为 ，则使用a进行划分所获得的信息增益为：

  2. 增益率：

  3. 基尼指数：代表的是一个子集的纯度，越小越好

剪枝处理

  1. 预剪枝 在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。
  2. 后剪枝 先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。

连续与缺失值

  1. 连续： 对于连续属性的值，可以选择相邻数值的中点做二分，看谁的信息增益最大 对于离散属性，仍然可以作为后代节点的划分属性

  2. 缺失值：

    1. 如何参与属性选择？ 可以对每个样本 赋予权重 （初始值设为1），并定义如下：

    2. 则信息增益为：

    3. 如何进行划分？

      1. 对于未缺失值的样本正常进行划分。
      2. 对于缺失值的样本，将其按照 所占比例大小对权重进行分配放进每一个部分。

集成学习

根据个体学习器的生成方式，集成学习方法可以分成两类：

  1. 个体学习器之间存在强依赖关系、必须串行生成的序列化方法：Boosting
  2. 个体学习器之间不存在强依赖关系：Bagging和随机森林

Boosting

先从初始训练集中训练出一个学习器，在根据学习器的表现对训练样本分布进行调整，使得先前的错误在后续受到更多关注。

  1. AdaBoost:
  2. Xgboost
  3. Lgbosst

Bagging

自主采样法，有放回的抽取m个样本，这样采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，进行组合。

  1. Bagging

    1. 训练过程
    2. 自助采样过程只使用了约63.2%的样本，剩下的样本可用作对泛化性能进行包外估计

  2. 随机森林（Random Forest） RF只是在Bagging基础上，进一步在决策树的训练过程中引入了随机属性选择，具体来说在选择属性时，先从该节点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分，k推荐为 . 这样就使得Bagging中学习器的多样性还来自属性波动。且训练效率也有所提升。

Stacking

  1. 平均法

    1. 简单平均法：加权平均法 的特例
    2. 加权平均法：在个体学习器性能相差较大的时候宜食用加权平均法

  2. 投票法

  3. 学习法

聚类简介

基于原型的聚类算法

  1. 基于原型的方法通常假设数据内在的分布结构可以通过一组原型来刻画

    • 这类方法通常对原型进行初始化，然后按照相应的策略和准则对原型进行更新迭代
    • 原型和原型的更新机制是原型的聚类算法的核心

  2. K-means 聚类算法：

    • 算法过程

      1. 选择K个样本点作为初始簇心
      2. 对每个 ，求的簇标记 ，将划分到中
      3. 对每个 ，更新其簇心为
      4. 重复2、3直到收敛

    • 均值运算对噪声和离群点比较敏感。

  3. 围绕中心点的划分算法(PAM)：简单说就是不断用样本点替换簇心，如果能得到更好的划分。

  4. 高斯混合聚合算法：

    • 算法假定不同簇的样本是根据不同的概率分布（高斯分布）生成的
    • 那么给定样本集，我们考虑对数似然函数

    • 不好直接求解，采用EM算法

      • E步，求期望：基于当前参数的估计值，计算对数似然函数关于隐变量Z的期望：
      • M步，极大化：通过极大化期望确定参数估计的更新 。
      • 重复上述步骤得到最优解。

层次聚类算法

  1. 层次聚类算法允许在聚类过程中对已有的簇进行合并或者分裂

    • 可以将所有样本看作是一个初始簇，采用自顶向下的分裂方式
    • 也可以将每个样本看作是一个初始簇，采用自底向上的聚合策略

  2. AGNES：自底向下，重复执行将当前簇中距离最近的两个簇进行合并的操作，直到收敛

  3. DIANA：自顶向下

基于密度的聚类算法

  1. 将簇看作数据空间中被稀疏区域分开的稠密区域，那么聚类就是发现并不断扩展稠密区域的过程。

    • 直观上我们可以从一个样本点的邻域入手，按照某种标准检查这个小区域是否是稠密的
    • 如果是稠密的，我们看看能否进行拓展

  2. DBSCAN算法：

    1. 引进邻域半径 和密度阈值MinPts > 0两个参数
    1. 核心对象：邻域内有MinPts个样本点
    2. 密度可达，位于核心对象的 邻域内，则我们称由直接密度可达；如果存在直接密度可达路径，则称为密度可达
    3. 密度相连：和是密度相连的如果，存在 ，都是由密度可达的。

  3. 簇：为样本子集 :

    1. 如果 ，则密度相连
    2. 对 ，如果和是密度可达，则
    3. 由核心对象出发，由其密度可达的所有样本点的集合正好构成一个簇。

隐马尔可夫模型

马尔可夫链

  1. 我们称 ，为转移概率，称矩阵 为马氏链的转移概率矩阵，简称转移矩阵

隐马尔可夫模型

  1. 在转移矩阵和初始概率分布 之外，再引进如下观测概率矩阵 ，因此用三元组 来表示一个隐马尔可夫模型，即

概率计算方法

  1. 隐马尔科夫模型 和观测序列 ，来计算

    • 如果遍历X的所有可能，计算效率过低

  2. 前向算法:

    • ，
    • ，从而可以向前递推得到

  3. 后向算法

维特比算法

  1. 解码问题，给定 和观测，找到最匹配的状态序列

  3. 考虑 ，则

    从而我们可以计算出，而

  4. 从上面的计算过程中我们就可以反向计算出每一步的最优状态序列

Baum-Welch算法

  1. 如何从观测数据中来学习隐马尔科夫模型的参数？由于马尔可夫链是隐藏的，考虑用EM算法来迭代求解，用 来表示马尔可夫模型参数的当前估计，则EM算法E步的Q函数为

    由于 ，从而

    则

  2. 分别使用拉格朗日乘子法即可

    • ：
    • ：先写成 ，对应的
    • ：类似于，先写成 ，对应的

神经网络学习之小批量梯度下降法

小批量梯度下降法：

  • 回归：平方损失

  • 二类分类：交叉熵损失

  • 多类分类：交叉熵损失

优化算

  1. 批量大小n的选择

    • n的大小不影响随机梯度的期望，但会影响其方差
    • n越大，方差越小，引入的噪声越小，训练越稳定，可设置较大的学习率

  2. 学习率 的调整：

    1. 过大，可能导致梯度下降法不收敛；过小，则收敛速度太慢；

    2. 调整办法：学习率衰减，预热，周期性学习率调整，自适应学习率调整

      1. 学习率衰减：初始时比较大，在收敛到最优点附近时采用小的学习率避免震荡。

        • 余弦衰减：
        • 指数衰减：

      2. 学习率预热：最初几轮先设置较小的学习率，等梯度下降到一定程度后再恢复初始学习率

        • 逐渐预热：

      3. 周期性学习率调整：帮助逃离鞍点或尖锐最小值的经验性方法

        • 当参数处于尖锐最小值附近时，增大学习率有助于参数逃离尖锐最小值
        • 三角循环学习率

      4. 自适应学习率的方法：

        • AdaGrad算法：

        • RMSprop算法：在AdaGrad基础上进行修改

        • AdaDelta算法：在RMSprop算法基础上修改

  3. 梯度估计修正

    1. 动量法：利用负梯度的移动平均来更新参数

      • 如果一段时间内梯度方向一致则加速收敛，如果不一致，则更新幅度变小，减速，增加稳定性

      • Nesterov加速梯度：将动量法的参数更新变成两步更新

    2. Adam算法：结合动量法和RMSprop算法

    1. 梯度截断：防止梯度消失和梯度爆炸

参数初始化

  1. 预训练初始化

  2. 固定值初始化：relu的神经元，将偏置设置为0.01

  3. 随机初始化：固定方差，方差缩放，正交初始化

    1. 固定方差：

    2. 方差缩放：参数初始化的区间应该根据神经元的性质进行差异化的设置

      • Xaiver初始化：输入输出的维度分别为n, m则考虑 ，令 即可
      • He初始化：对使用relu的神经元

    3. 正交初始化：希望避免梯度消失或爆炸 ，只需要为正交矩阵即可

数据预处理与逐层归一化

  1. 对于尺度敏感的模型，必须对样本进行预处理，将各维特征转化到相同的取值区间，并且消除不同特征之间的相关性

  2. 归一化：

    • batch norm：将每一个特征维度都归一到标准正态分布，然后进行缩放和平移变换。实践中一般在仿射变换之后，在激活函数之前。
    • layer norm：对样本维度进行归一化，讲一个样本的特征都归一化到正态分布，在进行缩放和平移变化
    • 权重归一化：将权重分解成长度和方向，分别进行优化

超参数优化与网络正则化

  1. 超参数优化：网络搜索与随机搜索，贝叶斯优化

  2. 网络正则化：

    1. 权重衰减正则化，在某些优化算法下，与正则化的等价
    2. dropout：按照概率1-p，随机丢弃一部分神经元，在推理的时候，不使用dropout，整体乘上p。在inverted dropout中，在训练的时候除以p保持整体均值不变，推理的时候就不做处理。
    3. 数据增强
    4. 标签平滑

PAC learnability

Empirical Risk Minimization

  1. 学习器

    1. 输入：

      • 实例空间 ，标签集
      • 训练集 ，其中
      • 数据生成模型： 按固定未知分布 采样，

    2. 输出：

    3. 误差：

      • 泛化误差：
      • 训练误差：

  2. 假设类 ：从 到 的函数集合

  3. ERM学习器：对给定 和训练集 ，选择训练误差最小的假设：

  4. 可实现性假设：Realizability Assumption

    • 存在 使得
    • 推论：以概率1有 ，从而

  5. 有限假设类的ERM保证 定理：设 为有限假设类， ， ，若

    则在可实现性假设下，以至少 的概率，对任意ERM假设 有：

    • 证明：
    1. 定义"坏"假设集合
    2. 对任意 ：
    3. 由union bound：

PAC learnability

Probably Approximately Correct

  1. 定义：假设类 是PAC可学习的，如果存在函数 和学习算法，使得：对任意 ，任意分布 ，任意满足可实现性假设的标记函数 ，当 时，算法以至少 的概率返回 满足：

    • Probably：置信参数 表示满足精度要求的可能性
    • Approximately Correct：精度参数 决定输出分类器与最优的距离
    • 样本复杂度：满足PAC学习要求的最小样本量

  2. 推论：每个有限假设类都是PAC可学习的，样本复杂度为：

Agnostic PAC learnability

  1. 动机：可实现性假设在实际中往往过强，需要放松

  2. 更现实的数据生成模型：

    • 为 上的联合分布（非确定性标记）
    • 包含边缘分布 和条件概率

  3. 修正的泛化误差：

  4. 贝叶斯最优预测器：对任意分类器 ，

  5. 定义：假设类 是agnostic PAC可学习的，如果存在 和学习算法，使得对任意 ，任意分布 ，当 时，以至少 的概率返回 满足：

  6. 一般损失函数的推广：

    • 损失函数 ，其中
    • 0-1损失：
    • 平方损失：
    • 风险：
    • 经验风险：

Uniform Convergence

  1. -representative 样本：训练集 称为 -representative 的，如果

  2. 引理：若 是 -representative 的，则任意ERM输出 满足：

    • 证明：

  3. 一致收敛性质： 具有一致收敛性质，如果存在 ，使得对任意 ，当 时，以至少 的概率 是 -representative 的

    • 若 有一致收敛性质，则 是agnostic PAC可学习的，样本复杂度

  4. 有限假设类的一致收敛：

    • Hoeffding不等式：
    • 对有限 ， ：
    • 从而agnostic PAC样本复杂度：

The Bias-Complexity Tradeoff

  1. No-Free-Lunch定理：设 为任意学习算法， ，则存在分布 使得：

    • 存在 满足
    • 以至少 的概率，

  2. 推论：设 为无限域， 为所有 的函数集合，则 不是PAC可学习的

  3. 误差分解：对ERM假设 ：

  4. 权衡：

    • 越大：近似误差 减小，但估计误差 增大（过拟合风险）
    • 越小：估计误差减小，但近似误差增大（欠拟合风险）
    • 学习理论研究：如何在保持合理估计误差的同时，使 尽可能丰富

  5. 备注：偏差方差分解

VC-Dimension

  1. 动机：有限假设类是PAC可学习的，但无限假设类是否可学习？有限性不是PAC可学习的充要条件

    • 例： ， ，是无限的但PAC可学习，样本复杂度

  2. 限制（Restriction）：设 ， 对 的限制为：

  3. 打散（Shattering）： 打散有限集 ，当且仅当 （即 上所有可能的标记都能被 中某个假设实现）

  4. VC维定义： 是能被 打散的最大集合的大小

    • 证明 ：

      1. 存在大小为 的集合被打散
      2. 任何大小为 的集合都不能被打散

    • 阈值函数 ：

    • 有限类：

  5. VC维与PAC可学习性的关系：

    • 若 ，则 不是PAC可学习的
    • 反之，有限VC维保证可学习性

  6. 推论（No-Free-Lunch的推广）：若存在大小为 的集合被 打散，则对任意学习算法 ，存在分布使得以至少 的概率

统计学习基本定理

The Fundamental Theorem of Statistical Learning 设 为 的函数类，损失为0-1损失，则以下等价：

  1. 具有一致收敛的性质
  2. 任何ERM规则都是 的成功agnostic PAC学习器
  3. 是agnostic PAC可学习的
  4. 是PAC可学习的
  5. 任何ERM规则都是 的成功PAC学习器
  6. 具有有限VC维

定量版本：设 ，存在绝对常数 使得：

  • 一致收敛样本复杂度：
  • Agnostic PAC样本复杂度：
  • PAC样本复杂度：

增长函数与Sauer引理

  1. 增长函数（Growth Function）：

    • 若 ，则

  2. Sauer-Shelah-Perles引理：若 ，则

    • 特别地，当 时： （多项式增长！）

  3. 定理6.11：以至少 的概率，

基本定理的证明思路：由Sauer引理， 时 ，代入定理6.11得到一致收敛界，从而当 时一致收敛成立。

非一致可学习性

Nonuniform Learnability

  1. 竞争性（Competitiveness）：假设 是 -competitive with ，如果以至少 的概率：

  2. 定义： 是非一致可学习的，如果存在算法 和函数 ，使得对任意 ，任意 ，当 时，以至少 的概率：

    • 与agnostic PAC的区别：样本复杂度可以依赖于具体的比较假设

  3. 刻画定理（Theorem 7.2）： 是非一致可学习的 可以写成可数个agnostic PAC可学习类的并：

  4. 非一致可学习是agnostic PAC的严格放松：

    • 例： = 次多项式分类器， （有限），每个 是agnostic PAC可学习的
    • 但 的 ，不是agnostic PAC可学习的
    • 仍然是非一致可学习的

结构风险最小化(SRM)

Structural Risk Minimization

  1. 先验知识： ，每个 有一致收敛性质；权重函数 ，

  2. 定义：

  3. SRM算法：

  4. 定理7.4：以至少 的概率，对所有 和 同时成立：

  5. 定理7.5：取 ，则 是非一致可学习的，样本复杂度：

    • SRM本质上是在经验风险和模型复杂度之间做权衡：选择的假设既要拟合数据，又不能来自过于复杂的子类

奇异值分解与主成分分析简介

奇异值分解

  1. 矩阵的四个基本子空间：对非零矩阵 ，其秩

    • 的值域： ，即 的列空间
    • 的零空间：
    • 的值域： ，即 的行空间
    • 的零空间：
    • 关系： ， ， ； ， ，

  2. 从谱分解到奇异值分解：

    1. 考虑实对称矩阵 ，设其特征值降序排列为 ，则

      • 可对角化： ，其中 为正交矩阵

    2. 将 分成两部分 ，其中 ，

      • 构成 （也是 ）的一组标准正交基

    3. 构造 ：

      • 验证正交性：
      • 是 的一组标准正交基
      • 设 为 的一组标准正交集，令

    4. 令 ，构造对角矩阵 ，由构造可知

  3. 奇异值分解：

    • 其中 是 阶正交矩阵， ； 是 阶正交矩阵，
    • 是由降序排列的非负的对角线元素组成的 矩形对角矩阵： ， ，且
    • 称为 的奇异值， 和 的列向量分别称为 的左、右奇异向量

  4. 紧奇异值分解与截断奇异值分解：

    • 紧奇异值分解： ，其中 ， ，
    • 截断奇异值分解：对 ， ，其中 ， ，

奇异值分解与矩阵近似

  1. Frobenius norm：

    • 若 是 阶正交矩阵，则
    • 若 是 阶正交矩阵，则

  2. 矩阵的最优近似：设 且 ，其奇异值分解为 ，设 为所有秩不超过 的矩阵集合， ，若秩为 的矩阵 满足 ，则：

    • 特别地，令 ，其中 ， ，则
    • 的紧奇异值分解是在费罗贝尼乌斯范数意义下 的无损压缩
    • 的秩为 的截断奇异值分解是 的有损压缩，通常 远小于 ，因此是由低秩矩阵实现了对 的压缩

  3. 矩阵的外积展开：

    • 的外积展开也可以看作矩阵的有序加权和

总体主成分分析

  1. 主成分变换：设 均值为 ，协方差矩阵为

    • 是半正定的，特征值降序排列为
    • 可对角化： ，其中 为正交矩阵
    • 主成分变换定义为：

    其中 为 的第 主成分

  2. TH1：主成分性质，设 ，则 满足：

    3. （各主成分不相关）
    5. （总方差守恒）

  3. TH2：不存在方差比 更大的标准线性组合

    • 证明： ，其中 ，约束 。最大化问题的最优解为 ，对应 ，正好是第一主成分

  4. TH3：如果标准线性组合 与 的前 个主成分都不相关，则 的方差当 是第 主成分时达到最大

  5. 方差贡献率：

    • 的第 主成分 的方差贡献率：
    • 前 个主成分的累计方差贡献率：
    • 累计方差贡献率反映了前 个主成分保留原有变量方差信息的比例，可作为选择 的标准（如使 达到80%以上）

  6. 因子负荷量：

    • 主成分变换 的逆变换为 ，即
    • 因子负荷量：第 主成分与变量 的相关系数，即 对 的贡献程度：
    • 性质： ；
    • 前 个主成分对原有变量 的贡献率：

样本主成分分析

  1. 设 是对 维随机向量 进行 次独立观测的样本，观测数据矩阵

    • 样本协方差矩阵 ，其中
    • 样本相关矩阵 ，其中
    • 规范化处理： ，规范化后样本协方差矩阵

  2. 样本主成分变换：设 的特征值为 ， 为属于 的单位特征向量，则：

    其中

    • 对应于 的样本方差
    • 样本前 主成分矩阵为

  3. 奇异值分解与主成分分析的联系：

    • 定义 ，则
    • 的右奇异向量就是 的单位特征向量

  4. 主成分分析算法：

    • 输入：规范化的样本矩阵 ；参数：主成分个数

      1. 构造
      2. 求 的 秩截断奇异值分解
      3. 样本前 主成分矩阵为