以西瓜书为主线，以其他书籍作为参考进行补充，例如《统计学习方法》，《PRML》等

第一章 绪论

1.2 基本术语

• 所有的可能的模型组合成为一个假设空间 H

• 预测分为两类任务：

  • 分类任务： 预测的结果是离散值
    • 二分类任务，其中标签为(0/1 或者 +1/-1 代表 正例/负例)
    • 多分类任务，类别数目 k > 2
  • 回归任务： 预测的结果是连续值

• 同时另一种任务是 聚类：事先不知道数据的规律，同时没有标签，属于无监督学习

• 建立模型/学习 的目的

  • 找到一个从输入空间 X -> 输出 Y的函数映射
  • 使得学习到的模型能够很好的拟合“新数据”，即具有很好的泛化能力

• 通常假设样本数据服从独立同分布（i.i.d），而服从的分布是未知的，我们需要做的就是找出这个分布规律

• 归纳偏好 可以理解为对不同特征的重视程度

• 任何一个有效的机器学习算法必有相应的归纳偏好，因为能够拟合有限数据的曲线并不唯一，因此需要设定归纳偏好，使得泛化能力得到保证

• 通常使用 奥卡姆剃刀 原则作为一般性的归纳偏好原则，但是很遗憾原则中 “简单” 的含义针对不同的模型并不唯一，需要借助其他机制才能完成判断

• NFL (No Free Lunch Theorem) 指出，必须结合具体的学习问题去讨论算法的优劣性

• 需要注意学习算法自身的偏好与问题是否匹配，不同的数据集有不同的“特点”，需要不同的“偏好”去拟合具体的数据集

第二章 模型评估与选择

2.1 经验误差与过拟合

• 误差分为两类：

  • 经验误差： 数据集上的误差
  • 泛化误差： 新样本上的误差

• 过拟合的理解：

  • 学习到了数据集中不够 general 的特性
  • 把训练集自身的某些特性当做整体的特性
  • 过拟合是无法避免的

2.2 评估方法

• 模型选择中存在两个问题：
  • 泛化误差我们无从知晓
  • 训练误差不靠谱(存在过拟合的情况）

因此提出不同的评估方法

• 需要一个 “测试集” ，通过 “测试集” 上的测试误差作为泛化误差的估计

• 测试集尽量不在训练集中出现，即二者尽量互斥

测试集的划分方法

1. 留出法

   将数据集划分为两个互斥的集合，同时保留类别比例(即进行分层抽样)

   一般采用确定分层比例后，在层的大小内进行若干次随机划分、重复进行后取平均值作为最终结果

2. 交叉验证法

   与留出法相似，将数据集A分为 k 个互斥的集合

       for i in k:
   
           将 A - k_i 作为训练集
           将 k_i 作为测试集
           记录 测试误差 err_i
   
       return 测试误差的平均数
   

   • p次k折交叉验证：通常重复 p 次进行，取 p 次结果的均值
   • 目的: 为了减少样本划分不同而引入的误差

3. 留一法

   k 折交叉验证法的特殊情况
   当 k = m , 此时称为 留一法

4. 自助法

   在 数据集较小、很难划分 训练集/ 测试集 的时候很有效

   但是，此方法产生的数据改变了出事数据集的分布，会引入估计偏差

   具体方法：
   假设数据集 D 有 m 个样本

   1. 每次从数据集 D 中采出一个样本，放入 D‘ 中，再将样本放回 D
   2. 重复进行 m 次采样操作
   3. 用 D’ 作为训练集， D / D{`} 作为测试集

   可证明，测试集中度数据占 D 中的 1/3 ， 且均未出现过在 D‘ 中

   自助法在集成学习中的 Bagging 模型中还会用到（抽样方法）

验证集

• 我们将数据集划分为训练集和验证集，在验证集上进行模型选择和调参

  注意！！！
  在模型选择调节完毕之后，还应将整个数据集 D 再完整训练一遍！

2.3 性能度量

• 不同的性能度量导致不同的评判结果
• 不能仅仅依赖评判结果，不同的任务需求和数据需要不同的模型和性能度量

2.3.1 错误率与精度

分类任务中最常用的性能度量，可用于 二分类 及 多分类

2.3.2 查准率、查全率与 F1

查准率 也叫 准确率（Precision）
查全率 也叫 召回率（Recall）

Precision 和 Recall 定义为：

{P} = TP \over {TP + FP}

{R} = TP \over {TP + FN}

• Precision 很高往往导致 Recall 较低，可以理解为谨小慎微，需要很大的确信度才会做决定
• Recall 很高往往导致 Precision 较低，可以理解为宁可错杀一万，也不会放过一个

P-R 曲线

1. 绘制具体步骤

   参考ROC曲线的绘制过程，将预测结果排序，依次将预测结果设置为阈值然后计算相应的 Precision 和 Recall

2. 若分类器的 A 的 P-R 曲线完全被另一个分类器B “包住” ,则 B 的性能优于 A

3. 平衡点（BEP）

   是当 Precision = Recall 时的取值，BEP 大的分类器更优

F1 Score

比算术平均、几何平均更加重视较小值

{F_1} = \frac {2 \times P \times R}{P + R}

Fβ Score

针对对于查准率和查全率重视程度不一样的情况
比算术平均、几何平均更加重视较小值

{F_\beta} = \frac {(1 + {\beta}^2) \times P \times R}{({\beta}^2 \times P) + R}

macro F1 Score

亦称 宏F1
直接计算，再求平均

{macro-P} = {1 \over n} \sum_{i=1}^{n}P_i

同理可得 macro-R，利用 macro-P、macro-R 和 F1 计算公式最后可得macro-F1

micro F1 Score
亦称 微F1，同理macro-F1，记为micro-F1，先对 TP、TN、FP、FN 求平均，再计利用平均值计算F1 Score

2.3.3 ROC与AUC

• ROC - 受试者工作特征
• 横轴： TPR ； 纵轴： FPR

• AUC - 曲线下面积
• 面积的大小代表预测的准确性
• 绘制步骤
  • 对每个测试样例进行预测，得到预测结果
  • 对预测结果进行排序
  • 将分类阈值一次设置为每一个预测值即将每个样例设置为正例）
  • 设置好阈值之后，循环其他样例，若样例为真正例，则纵坐标加1 \over m^+
  • AUC中坐标 x 代表 该点之前的反例所占比，因为每遇到一个反例横坐标扩大一个百分点（1 \over m^-），同理，y 代表 该点之前的正例所占比
  • AUC的范围是 [0.5, 1]

2.3.4 代价敏感错误率与代价曲线

敏感代价错误率

E(f;D;cost) = \frac{1}{m} (\sum_{x \in {D^+}}I(f(x_i)\not=y_i) \times cost_{01} + \sum_{x_i \in D^-}I(f(x_i)\not=y_i) \times cost_{10})

• 为了权衡不同类型的错误造成的代价
• 使用 代价矩阵(cost_{01}，cost_{10}...)刻画不同的代价
• 使用 比值 刻画代价之间的重要程度

2.4 比较检验

• 使用假设检验的方法，进行误差的假设检验
• 后期进行二项检验、t检验的具体笔记

2.5 偏差与方差

• 针对回归问题，期望泛化误差可以分解为 偏差、方差、噪声之和
• 分解结果：

E(f;D) = bias^2(x) + var(x) + \epsilon^2

• 具体分解过程见书 P45页
• 偏差与方差的关系
  • 偏差与方差是 准 与 确 的关系
  • 偏差 ：刻画预测结果的 确 的程度，即算法本身的拟合能力
  • 方差 ：刻画预测结果的 准 的程度，也提现算法抗数据扰动的能力
  • 噪声 ： 刻画算法达到期望泛化误差的下界，即学习问题本身的难度
  • 学习初期， 偏差 主导泛化错误率，体现为 欠拟合
  • 学习后期，欠拟合问题逐渐解决， 方差 主导泛化错误率，体现为 过拟合 ，在学习器学习过程中，会渐渐学习到数据中的 干扰数据，从而导致学习器的抗干扰能力下降，也即方差增加

偏差与方差的经典关系图：

image

• Min-Max规范化和z-score规范化的区别

第3章 线性模型

3.1 基本形式

• 试图用 属性 的 线性组合 进行预测
• 基本形式：

f(x) = \omega^Tx + b = \omega_1x_1 + \omega_2x_2 + \cdots + \omega_dx_d + b

• \omega 代表了各属性的 重要性， 因此线性模型具有很好的 可解释性

3.2 线性回归

回归模型的变量通常是连续值，因此当属性是离散值时，可以进行 连续化

• 当属性件存在 “序” 的关系，通过对离散值进行排序，然后转换为相应大小的连续值
• 当属性间不存在 “序” 的关系，可以通过使用 OneHot 编码方法进行离散值的转换
• 无序属性进行连续化会不恰当的引入 “序” 的关系

损失函数：

• 使用 均方误差(MSE) 进行性能度量

MSE = \sum_{i=1}^{m}{(f(x_i) - y_i)}^2 = \sum_{i=1}^{m}{(\omega x_i + b - y_i)}^2

求解方法：

• 最小二乘法 - 找到一条直线使所有的样本到直线的欧氏距离最小
• 最大似然估计 - 求出使所有出现的结果值的概率最大的概率模型参数

3.3 对数几率回归

也叫逻辑回归（Logistic Regression），虽然叫回归，但是其实是 分类 算法

起源

• 希望使用 线性模型 进行 分类预测任务
• 因此输出结果需要是 离散的 类别标签，二分类为例： y = {0,1}
• 但是线性模型的预测结果是连续值，因此我们需要找到一个函数将连续的结果值映射为离散的类别标签
• 因此，单位阶跃函数 是理想的映射函数，但是单位阶跃函数并不单调可微，这样就引入了 对数几率函数 作为替代函数
• 预测的结果其实是 对率几率，定义如下：

\omega x^T + b = ln \frac {y}{1-y}

• 而 y 才是概率
• 去除 ln 有 几率 的定义，反映 x 作为正例的相对可能性
• 直接对 分类可能性 建模，无需实现假设数据分布，避免假设分布不准确引入的问题

3.4 线性判别分析

核心思想：

• 异类点的投影点尽可能的远离，同类点之间的协方差尽可能的小(即同类点之间尽可能的靠近)

优化目标

J = \frac{w^TS_bw}{w^TS_ww}

• 二维情况详细推导可以参考 https://www.cnblogs.com/engineerLF/p/5393119.html
• 其中可以用“广义瑞利商”的性质得出最优w ,详细性质推导见 https://www.cnblogs.com/pinard/p/6244265.html

最大化方法

• 添加负号，变为最小化问题
• 使用拉格朗日乘子法，

求解结果

• 在一般的实践中，S_w^{-1} 使用SVD进行奇异值分解，通过 S^{-1}_w = V{\Sigma}^{-1}U^T 得到 {S_w}^{-1}

KLDA

• 在LDA中引入核函数，应对非线性可分问题，具体推导见西瓜书P137

3.5 多分类学习

• 三种拆分策略：

  • 一对一（OvO）
  • 一对其余（OvR）
  • 多对多（MvM）

• 一对一 将类别两两配对生成 \frac {N(N-2)}{2} 个分类器

• 一对其余 每次将一个类别视为正例，其余视为反例，因此一共会生成 N 个分类器

• 但是，一对一的 训练开销 通常小于 一对其余，因为一对一只用到了两个类的训练数据

多对多分类

• 常用纠错输出码（ECOC）
• 常见编码矩阵：二元码，三元码（加上停用类，不带入计算）
• 将类别进行随机拆分，拆分为两类：正例和反例，形成很多个二分类器
• 任意两个分类器越 ”不相同“，训练结果越好，思想类似于 Bagging，训练多个高多样性的分类器
• 最后这些分类器对同一个样本预测，将预测结果分别计算编码距离（海明距离 / 欧式距离），将编码距离最小的类作为最终结果
• 同一个分类任务， ECOC编码越长，分类器之间的相似性就会越小，因此容错能力越好
• 同等长度的编码， 任意两个类别的编码距离越大，容错能力越好

3.6 类别不平衡问题

“再缩放” 思想

在对分类任务进行预测时，y 是代表正例的概率，通常将阈值设置为 0.5，即 y > 0.5 ,将结果判定为正例，否则判定为负例

言外之意：

若 y > 0.5， 预测为正例， 即若 \frac{y}{1-y} > 1, 预测为正例

但是，注意这样做的原因：
0.5 代表的其实是 观测几率, 即我们在数据集中能观测到正例的几率（我们 假设 两个类别的数据集是一样大的，因此观测几率是 0.5）所以当 y > 0.5 代表预测正例的概率大于观测概率，当然应该判定为正例。

而现在，不同的类别对应的数据量不同了，不再是 1 ： 1，我们的阈值就不应该设置为 0.5， 而是应该当：

若 \frac {y}{1-y} > \frac{m^+}{m^-}，预测为正例， 解出 y ，就是我们新的阈值

欠采样、过采样思想

欠采样

• 减少数据集的数目，使得所有类别的数据相同
• 代表算法： EasyEnsemble，即分割负例为不同的数据集，以供多个学习器使用，利用了集成的思想

过采样

• 增加数据集的数目，使得所有类别的数据相同
• 需要注意增加数据集的方法，单纯的 重复采样 会导致严重的 过拟合
• 代表算法： SMOTE

3.7 相关思考

• 线性回归推导中的最小二乘和极大似然的关系

  • 是因为极大似然中假设 误差服从正态分布 所以才会有推导结果与最小二乘是一样的，正态分布中刚好有二次项

  • 另一种说法是最小二乘选择使用平方的原因是推导极大似然的推导结果就是最小二乘，所以说最小二乘是极大似然估计的结果

第4章 决策树

4.1 决策树模型与学习

优点

• 模型具有可读性，分类速度快

概念

• 损失函数使用 正则化的极大似然函数
• 学习的策略是 最小化损失函数
• 使用启发式方法求解决策树，求解的结果是次优的
• 结点有两种类型：内部结点(非叶子结点）表示一个特征或属性， 叶子结点代表一个类
• 还表示给定特征条件下的概率分布

决策树的学习算法包括：

• 特征选择（划分选择）
• 决策树的生成，只考虑局部最优
• 决策树的剪枝，考虑全局最优

注意两种情况：

1. 当属性集为空或所有样本在属性集上的取值相同，将类别标记为 D 中最多的类别，使用的是当前结点的 后验分布
2. 当当前结点包含的样本集为空，同样将类别标记为 D 中最多的类别，但是是利用的当前结点的 先验分布

4.2 特征选择（划分选择）

基于 信息熵 进行特征选择

• 表示随机变量不确定性的度量

• 同时也可以从另一个角度理解： 表示了解一件事情所需要花费的信息代价（数学之美）

常用 3 种指标选择应作为划分的特征

• 信息增益
  • 对 可取数目较多 的特征(属性)有所偏好
• 增益率
  • 对 可取数目较少 的特征(属性)有所偏好

所以通常采用一种折中的方法： 先找出高于平均水平的 信息增益， 再找出其中 信息增益率 最大的特征(属性)

• 基尼系数

4.3 决策树的生成

常用的 3 种生成算法：

• ID3， 使用 信息增益 进行特征选择
• C4.5， 使用 增益率 进行特征选择
• CART， 使用 基尼系数 进行特征选择

ID3相当于用极大似然法进行概率模型的选择 理解

决策树模型的参数估计就是基于特征空间怎样划分使得样本出现的概率最大,而寻找怎样划分的过程即求解概率模型参数的过程

4.4 CART 的生成

CART回归树的生成

对于回归问题，CART 采用与决策树相同的思想，还是 对输入空间进行划分，每一个划分R_m对应一个固定的输出值c_i，生成的回归模型表示为：

f(x)=\sum_{m=1}^Mc_mI(x\in{R_m})

固定的输出值 c_i 为划分空间R_m中y_i的均值

CART回归树的损失函数

CART回归树采用 平方误差 \sum_{x_i\in{R_m}}(y_i-f(x_i))^2

CART回归树的划分

依次对划分空间R_m中的每一个样本进行如下的操作：

• 依次将当前样本的每一个 特征/属性 值，作为一个切分点s，而当前变量就是切分变量j
• 使用当前切分变量的切分点将当前划分空间R_m划分为两个子区域 R_1={x|{x^{(j)} \req s}}, R_2={x|{x^{(j)} > s}}
• 然后计算 R_1 和 R_2 的固定输出值 c_{1i}, c_{2i}
• 计算c_{1i}, c_{2i} 下的平方误差和 r_{js} = r_{js1} + r_{js2}

比较所有的r_{js}, 找到 最小的 r_{js}下的最优切分变量 j，最优切分点 s

再对划分好的两个子区域进行上述划分，直到满足停止条件

CART分类树的生成

CART分类树使用 基尼系数 为划分依据，剩下的生成方式与决策树的生成方式一样

算法停止的条件可以是：

• 结点中的样本个数少于阈值
• 结点上的基尼指数小于阈值(基本属于同一类)
• 或者没有更多特征

CART分类树的剪枝

4.5 决策树的剪枝

剪枝策略

• 预剪枝
• 后剪枝

由 4.3 中 ID3相当于用极大似然法进行概率模型的选择 的概念， 决策树的剪枝也可以看做是正则化的极大似然估计，正则化项就是决策树的叶结点个数

预剪枝

• 在划分结点前估计，若划分结点后不能提升泛化性能，则停止划分
• 使用贪心的策略，有可能陷入局部最优
• 带来欠拟合的风险

后剪枝

• 等决策树完全生成好之后，再从下而上的进行剪枝
• 剪枝策略：
  • 将结点的子树替换为叶节点，观察泛化性能是否提升，如果提升则将子树替换为叶节点，否则不进行剪枝
  • 根据奥卡姆剃刀原则，如果泛化性能不变依然应该选择剪枝，形成更简单的决策树
• 可以较好的防止过拟合，但是时间开销很大

这里的泛化性能评估标准可以是 精度

4.6 连续与缺失值

4.6.1 连续值的处理

假设属性 A 为连续值属性， A 属性共有 N 个不同的值

• 将这 N 个不同的值进行排序
• 依次选取划分点 t，大于划分点 t 的记为 D_t^+, 同理，小于 t 的记为 D_t^-
• 这样，可以将每一个取值都作为一次划分点，然后计算 信息增益, 最后可以得到属性 A 的信息增益
• 后续就跟离散值的做法一样了

4.6.2 缺失值的处理

当计算属性 A 的信息增益时，如果发现有样本有缺失值：

• 初始将所有样本赋予 1 的 权值
• 计算 属性a 上的三个概率（主要都是针对不含有缺失值的样本）
  • 无缺失样本所占总体数据比例
  • 无缺失样本中第k类所占比例
  • 属性 a 上无缺失样本中取值为a^v所占比例
• 利用这三个概率计算每一个属性 a 的信息增益

Gain(D,a) = \rho \times (Ent(D^n) - \sum_{v=1}^{V}{r_v}^~Ent({D_v}^n))

• 更新含有缺失值的样本的权值，并划入每一个结点
  • 将划入的数据权值更新为 {r^n}_v * w_x, 相当于将数据依概率进行划分
• 后续与普通的操作相同

注意：

• 更新权值相当于以不同的概率将样本划分进每一个结点
• 因为含有缺失值的样本可能接下来还要参加其他属性的信息增益的计算，而计算中会涉及权值，所以 权值 相当于对带有缺失值的样本的 影响力

4.7 多变量决策树

相当于对特征进行了一个线性的组合，之前的特征是单变量，组合之后单个结点相当于一个 线性的分类器

4.8 习题思考

1. 以“最小训练误差”作为划分选择的缺点

• 由于训练集总会与模型之间存在误差，如果选择最小误差，则会很大程度的拟合为符合训练集的决策树，从而导致严重的过拟合

2. 对比使用递归、栈（非递归）、队列（非递归）三种结构生成决策树的优缺点

• 缺点：

  • 使用递归的方法会保存大量的参数信息，而在参数中有大量的数据信息，从而会导致内存溢出
  • 如果使用栈的结构，不能完成以MaxNode的约束，会生成畸形的决策树（只有一边），只能完成以MaxDepth的约束
  • 如果使用队列的结构，只能完成BFS即以MaxNode的约束

• 优点：

  • 使用递归的方法代码更加简洁，易读
  • 使用栈的结构有利于后剪枝
  • 使用队列的结构，由于入队之前必须进行划分，如果是用预剪枝则会很方便，因为可以比较划分与否的验证集精度，而栈则做不到

当数据属性相对较多，属性不同取值相对较少时，树会比较宽，此时深度优先所需内存较小，反之宽度优先较小。

第5章 神经网络

后续再写

第6章 支持向量机

支持向量机内容顺序主要根据《统计学习方法》中的章节来安排，主要内容也由《统计学习方法》展开，其中穿插入西瓜书的知识点

6.1 概念

• SVM是一种 二分类 模型
• 学习算法是 求解凸二次规划的最优化算法
• 模型分类三类
  • 线性可分支持向量机：当数据集线性可分（硬间隔支持向量机）
  • 线性支持向量机：当数据集近似线性可分（软间隔支持向量机）
  • 非线性支持向量机：使用核技巧
• 核函数
  • 表示将输入从输入空间映射到特征空间得到的特征向量之间的内积

6.2 线性可分支持向量机

• 输入空间
  • 输入的数据向量所在的空间
• 特征空间
  • 特征向量所在的空间

支持向量机的学习是在特征空间中进行的，线性可分SVM将输入空间中的输入线性映射为特征空间中的特征向量，非线性可分SVM将输入非线性映射为特征向量

• 算法思想
  • 利用间隔最大化求最优分离超平面，解是唯一的
  • 能够正确划分训练数据集并且 几何间隔 最大

学习到的分离超平面：

w^* * x + b^* = 0

最终的分离决策函数使用符号函数

6.2.1 函数间隔和几何间隔

• 函数间隔

\hat{\gamma}_i = y_i(w*x_i+b)

其中 y_i 用来表示分类预测的正确性, w*x_i+b 用来表示分类的确信度（换言之就是点到分类超平面的距离）

定义超平面的函数间隔为数据集D中所有样本的函数间隔中的最小值，即：

\hat{\gamma} = \min_{i=1,...,N}\hat{\gamma}_i

• 几何间隔

由于成倍缩放w,b会导致函数间隔成倍缩放，所以 w 加上约束，如约束为：\Vert{w}\Vert = 1， 可以导出几何间隔

• 函数间隔与几何间隔的关系

\gamma = \frac{\hat{\gamma}}{\Vert{w}\Vert}

6.2.2 间隔最大化

• 直观解释
  • 使得分离有足够的确信度 [ 使得（离分离超平面 最近 的数据点）离超平面 足够远 ]

可以得到求解式：

\max{\frac{\hat{\gamma}}{\Vert{w}\Vert}}_{w,b}

s.t. y_i(w*x_i+b) \geq \hat{\gamma}, i = i,2,...,N

令 \hat{\gamma} = 1,得到 线性可分支持向量机的最优化问题(凸二次优化问题), 具体推导见《方法》P97：

\min_{w,b} \frac{1}{2}{\Vert{w}\Vert}^2

s.t. y_i(w*x_x+b) - 1 \geq 0, i=1,2,...,N

6.2.3 学习的对偶算法

求解 线性可分支持向量机的最优化问题 使用 拉格朗日对偶性，令原式为原始问题，通过求解对偶问题得到原始问题的最优解

• 优点
  • 对偶问题更容易求解
  • 自然引入核函数（在对偶式中出现了内积）

推导过程见 《统计学习方法》 P103

其中几个重要的点：

• 支持向量是 {\alpha_i}^* > 0 的点
• 对偶学习问题的KKT条件

image

• KKT的对偶互补条件

{\alpha}^* \geq 0

• 实际应用中b的求解
  • 理论上使用任意一个数据x_j就能算出 b
  • 在实际应用中，采用更加鲁棒的做法:使用所有 支持向量 求解的平均值,S代表支持向量的集合

b = \frac{1}{S}\sum_{s\in{S}}(\frac{1}{y_s} - \sum_{i\in{S}}\alpha_iy_ix_i^Tx_s)

6.3 线性支持向量机与软间隔最大化

6.3.1 线性支持向量机

• 引入

  • 大部分数据并不满足完全线性可分，存在一部分数据非线性可分，因此对每一个数据引入一个松弛变量 \xi \geq 0,使得那些不满足线性可分的数据点加上 \xi 变得线性可分

• 线性支持向量机的原始问题：

\min_{w,b,\xi} \frac{1}{2}{\Vert{w}\Vert}^2+C\sum_{i=1}^N{\xi}_i
s.t. y_i(w*x_i+b) \geq 1 - {\xi}_i, i = 1,2,...N
{\xi}_i \geq 0, i=1,2,...N

• 原始问题的对偶问题

  • 同线性可分的推导相同，先求\min_{w,b,{\xi}}(即分别对w,b,\xi求导，并令导数等于零，求出相应的表达式，代回原式，得到\min_{w,b,{\xi}}L(w,b,\xi,\alpha,\mu))
  • 再求出\max_{\alpha}\min_{w,b,{\xi}}L(w,b,\xi,\alpha,\mu)

• 原始问题满足的KKT条件

image

6.3.2 支持向量

• 若{\alpha_i}^* < C, 则\xi_i = 0,支持向量恰好落在间隔边界上
• 若{\alpha_i}^* = C，0<\xi_i<1,则此时分类正确，x_i 在分类超平面与间隔边界之间
• 若{\alpha_i}^* = C，\xi_i = 1，则 x_i 在分离超平面上
• 若{\alpha_i}^* = C，\xi_i > 1, 则 x_i 位于分类错误的一侧

6.3.3 合页损失函数

• 定义

image

• 原始问题也等价于含有合页函数作为损失函数的目标函数
• 也即将 \xi_i 换成了{[1-y_i(w*x_i+b)]}_+

{\sum_{i=1}^N}{[1 - y_i(w*x_i+b)]}_+ + \lambda{\Vert{w}\Vert}^2

• 相比感知机的损失函数和0-1损失函数，合页损失函数有更高的要求

[图片上传失败...(image-b1fd0d-1532507004505)]

6.4 支持向量回归

• 思想
  • 不同于传统回归模型，SVR对偏差有一定的容忍，形成一个以容忍度/宽度2\epsilon为间隔带，误差不超过\epsilon的样本都认为预测正确
  • SVR也可以引入核函数
  • SVR引入了 \epsilon-不敏感损失

l_\epsilon(z) = \begin{cases} 0, & \text{if $|z| \leq \epsilon$} \\[2ex] |z| - \epsilon, & \text{otherwise} \end{cases}

• 原始问题
  • SVR考虑预测模型两侧的情况，所以约束条件分为两个

f(x_i) - y_i \leq \epsilon + \xi_i, 上侧

y_i - f(x_i) \leq \epsilon + \hat{\xi_i}, 下侧

6.5 核函数

6.5.1 核技巧

非线性分类问题

• 对于不能线性分类的数据，也就不能用一个超平面将数据分开，但如果能用一个 超曲面 将数据集分开，那么这个问题就是一个非线性可分问题
• 注意：是 非线性的 但是是 可分的问题

求解思想

• 使用一个变换将原空间的数据映射到新空间，而这个新空间也就是 特征空间
• 在 新空间\特征空间 上用 线性分类的学习方法 学习分类模型

核函数定义

K(x,z) = \phi(x)*\phi(z)

其中，\phi{x} 为 映射函数

表示定理

• 对于一般的损失函数和正则化项，优化问题都能表示为核函数的线性组合

h^*(x) = \sum_{i=1}^m\alpha_ik(x,x_i)

核函数在SVM中的应用

• 将SVM对偶问题中的内积 x_i*x_j 变换为特征空间中的内积 \phi(x_i)*\phi(x_j)
• 当映射函数是 非线性函数 时，学习到的核函数SVM是 非线性分类模型

使用核函数的支持向量机最优化问题

6.6 习题思考

• 为什么高斯核会把原始维度映射到无穷多维？
  • 定义多项式核函数 k(x,y) = {(x^Ty)}^p
  • 然后考虑高斯核函数k(x,y) = exp(-{\Vert{x-y}\Vert}^2)
  • 展开后得到： k(x,y) = exp(-{\Vert{x}\Vert}^2)exp(-{\Vert{y}\Vert}^2)exp(2xy)
  • 由泰勒展开公式：

指数函数： e^x = \sum_{n=0}^\infty{\frac{x^n}{n!}}

可以得到：

k(x,y) = exp(-{\Vert{x}\Vert}^2)exp(-{\Vert{y}\Vert}^2){\sum_{n=0}^\infty}{\frac{(2x^Ty)^n}{n!}}

可以看出，高斯核其实被展开为无穷项多项式核函数的和，而这其中也包括了无限维的多项式核，因此高斯核会把原始维度映射到无穷多维

第七章 贝叶斯分类器

7.1 贝叶斯决策论

概念

• 贝叶斯决策论是建立在 概率 和 损失 之上的,以概率为基石辅以损失函数

二者结合形成了在样本上的 “条件风险” 函数

R(c_i|x) = \sum_{j=1}^N\lambda_{ij}P(c_j|x)

\lambda_{ij} 是将真实标记为 c_j 的标记预测为 c_i 的损失，可以为任意的损失函数

P(c_i|x) 是 可从数据中获得 样本分类为 c_i 的 后验概率

我们需要找到一个判定准则 h , 来 最小化总体风险, 即 使得预测结果类 c^* 是使得上面提到的损失最小的类 c

因此最优的判定准则为：

h(x^*) = \mathop{argmin}_{c\in{Y}}R(c|x)

现在，就我们就只需要考虑如何求得所有的 R(c|x), 当损失函数是 0-1损失 时有：

R(c|x) = 1 - P(c|x)

注意！ 上式只在 损失函数 是 0-1损失 时成立！！！

于是，我们可以得到贝叶斯最优分类器：

h^*(x) = \mathop{argmax}_{c\in{Y}}P(c|x)

后验概率的求解

现在的任务变为了求解 P(c|x), 主要有 判别式模型 和 生成式模型

• 生成式模型
  • 通过直接建立模型来预测 c
  • 代表：决策树、BP神经网络、支持向量机

• 判别式模型
  • 通过对概率分布 P(c|x) 建模
  • 代表： 贝叶斯模型
  • 求解公式,基于贝叶斯公式：

P(c|x) = \frac{P(c)P(x|c)}{P(x)}

而对于所有的训练数据，P(x) 是相同的，不影响求解最优，由此，贝叶斯最优分类器的公式可以更改为：

$h^*(x) = \mathop{argmax}_{c\in{Y}}P(c)P(x|c)$$

7.2 朴素贝叶斯分类器

由于通常数据的特征/维度会有很多，同时每一个特征的取值也有很多，例如一共有K个特征，而每一个特征是一个二值特征，那么整个数据空间将会达到 2^K 的规模，因此与测试时很有可能该数据在训练样本中没有出现过，导致 P(x|c) = 0，这显然不对，没有出现过并不等价于概率为零

因此引入 朴素贝叶斯分类器

而在朴素贝叶斯方法中，学习 指的就是 P(c) 和 P(x|c) 的 估计

概念

• 假设每个属性 独立 的对分类结果产生影响

P(c|x)=\frac{P(c)P(x|c)}{P{x}}=\frac{P(c)}{P(x)}\prod_{i=1}^dP(x_i|c)

其中 d 为属性数目， x_i 为 x 在第 i 个 属性上的 取值

计算

• 先验概率

令 D_c 表示训练集 D 中第 c 类样本组成的集合

P(c) = \frac{|D_c|}{|D|}

• 后验概率

对于离散属性,令 D_{c,x_i} 表示 D_c 上在第 i 个属性上取值为 x_i 的样本组成的集合

P(x_i|c)=\frac{|D_{c,x_i}|}{D_c}

对于连续属性，考虑概率密度函数，假设服从正态分布 N(\mu_{c,i},\sigma_{c,i}^2), 其中 \mu_{c,i}, \sigma_{c,i}^2表示第 c 类样本在第 i 个属性上取值的 均值 和 方差

p(x_i|c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}}exp(-\frac{(x_i - \mu_{c,i})^2}{2\sigma_{c,i}^2})

上面三个式子就是基于 极大似然估计 的结果

贝叶斯估计\平滑

贝叶斯估计就是加上 平滑 的极大似然估计

目的

为了避免某些属性值在计算时没有在训练数据中出现，导致概率为零最后导致连乘最后的结果为零，对上面离散情况的计算式子进行修正

\hat{P}(c) = \frac{|D_c| + \lambda}{|D| + \lambda{N}}

\hat{P}(x_i|c) = \frac{|D_{c,x_i}| + \lambda}{|D_c| + \lambda{N_i}}

常用 拉普拉斯修正, 即上式中 \lambda = 1

第八章 EM算法

8.1 概念

期望最⼤化算法，或者EM算法，是寻找具有 潜在变量 的概率模型的 最⼤似然 解的⼀种通⽤的⽅法（PRML）

但是当 Z 是连续变量或者离散变量与连续变量的组合时，⽅法是完全相同的，只需把求和换成适当的积分即可（PRML）

• 为什么EM算法需要先给定一个先验的参数 \theta？

因为在求解最大化对数似然 log\sum_z{P(Y,Z|\theta)} 的过程中引入了一个 常数，而这个常数是一个已知了参数 \theta 和Y的关于隐变量 z 的概率值，因为需要提前已知参数 \theta 分布函数才是确定的，然后带入 Y 才能利用分布函数求出当前隐变量 z 的概率值

• 每次 M步 最大化的是什么？

最大化的是期望，而这个期望是对数似然的期望，其中对数似然的分布函数已经是给定了的（其中分布函数是有关\theta的）

• 每次 E步 求的是什么？

求的是 M步最大化需要用到的提前给定的 对数似然的分布函数， 利用提前给的 \theta 进行求解

8.2 算法步骤

• 输入模型参数的初值 \theta^{(0)}
• E步： 利用已知的参数\theta^i 计算函数 Q(\theta,\theta^{(i)}) = \sum_zlogP(Z|Y,\theta^{(i)})P(Y,Z|\theta)
  • 其中函数 Q(\theta,\theta^{(i)}) 就代表对数似然的期望
  • 需要计算的就是 P(Z|Y,\theta^{(i)})
  • 其中含有 M步需要最大化的参数\theta
• M步： 最大化E步求出的 Q(\theta,\theta^{(i)}) 中的参数 \theta
• 将 M步 求出的最大的 \theta 作为E步中已知的参数\theta^i，迭代进行计算，直到参数 \theta 收敛（变化很小）

8.3 算法是怎么来的 + 坐标上升###

• 思想

  • 最大化观测数据的对数似然函数 logP(Y|\theta)
  • 找到一个对数似然函数的下界函数 Q(\theta)
  • 找到下界函数 Q(Z) 的最大值 \theta^*
  • 下界函数利用 Jensen不等式 得到（提示：log函数是一个凹函数）求得，其中需要引入一个使用 \theta^{(i)} 的先验分布 Q(z^{(i)})

• 如何求得需要引入的先验分布 Q(z^{(i)})？

  • 从 Jensen不等式入手，由于Jensen 表示： E[f(x)] \leq f[E(x)], 当x为常数c的时候，左右式相等，此时取到等号
  • 此时求得 Q(z^{(i)}) = P(z^{(i)}|Y,\theta)

EM算法是一个迭代计算的算法，思想就是每次固定一个变量

• 首先固定住 \theta, 调整先验分布函数Q(z^i)取到等号
• 然后固定住先验分布函数Q(z^{(i)})，调整\theta，使先验分布函数Q(z^{(i)})取得最大值，得到\theta^{new}
• 再固定住\theta，此时使用刚计算出的\theta^{new} ，调整先验分布函数Q(z^i)取到等号....
• 直到对数似然函数收敛到最大值\theta^*

因此，EM算法可以看做利用 坐标上升 进行优化的算法

image

第九章 集成学习

Boosting方法

主要关注 降低偏差

AdaBoost

核心思想

弱分类器的线性组合

组成元素

• 弱分类器 G_m(x)
• 弱分类器系数 \alpha_m
• 第 m 轮中，第 i 个样本的系数 w_{m,i}
• 弱分类器在 加权数据集 上的分类误差率 e_m，是被G_m(x)误分类的样本的权值之和

算法步骤

• 将样本的权值先给定为均值，在此基础上学习出基本分类器 G_1(x)
• 反复学习基分类器，执行以下步骤：
  • 使用当前权值分布的数据集学习得到基本分类器 G_m(x)
  • 计算基本分类器在当前 加权数据集 上的分类误差率 e_m
  • 根据 e_m 调整基本分类器 G_m(x) 的系数 \alpha_m，分类误差率 越小 的基本分类器，其系数 越大，即在最终分类器中的作用越大
  • 根据基本分类器 G_m(x) 的系数 \alpha_m，更新下一个基本分类器 G_{m+1}(x) 训练的数据集的权值分布 w_{m+1,i}

另一种解释

AdaBoost 还可以看做是 前向分步加法算法 的特例，是由基本分类器组成的 加法模型， 损失函数是 指数函数

前向分步算法

• 学习的是 加法模型
• 从前向后，每次只学习一个基分类器及其系数

提升树

以 分类树 或 回归树 为 基分类器 的提升方法

对分类问题，采用 二叉分类树，对回归问题， 采用 二叉回归树

采用 加法模型 + 前向分布算法 + 决策树为基函数 且基函数为决策树桩（最简单的决策树）

之所以采用二叉树，是因为二叉树是所谓的 决策树桩, 足够简单，同时也能避免 过拟合

提升树算法

不同问题的提升树算法区别在于： 损失函数不同

• 分类问题： 指数损失函数
• 回归问题：平方误差损失函数
• 一般决策问题： 一般损失函数

分类问题提升树

分类问题提升树与Adaboost差别不大

其中，对于二分类问题，与 AdaBoost 算法步骤相同，只不过将基分类器固定为 二叉分类树，即二分类问题的提升树算法是 AdaBoost算法的特殊情况

回归问题提升树

回归问题提升树采用 前向分步算法 + 平方损失函数，学习方法就是不断地拟合 残差

• 计算当前残差 r_{mi} = y_i - f_{m-1}(x_i)
• 训练一个拟合当前残差 r_{mi} 的回归树 f_{m}
• 将学习到的回归树与之前的回归树进行加和，求得最终的回归提升树

梯度提升树（Gradient Boosing Decision Tree）####

核心思想

• 在 提升树 的基础上加入了 梯度 的概念,利用 负梯度在当前模型的值 作为回归问题提升树中的残差的 近似值

GBDT基分类器的选择

• 服从 低方差和高偏差，算法框架服从 boosting框架 即可

• 由于是 拟合残差(连续值)，所以GBDT中的基分类器选择的基本都是 CART回归树

算法步骤

大部分在提升树中的步骤不变，加入了 用损失函数的负梯度作为残差的近似值

• 使用 原始数据集作为训练集, 利用 CART回归树 训练出第一个回归树 f_0(x)
• 计算损失函数的 负梯度 当回归树 f_{m-1} 下的值 r_{mi}, 后面有举例怎么计算
• 对 r_{mi} 拟合一颗 CART回归树 f_r(x), 拟合的过程参考:CART回归树的生成
• 更新 f_m(x) 为 f_{m-1}(x) 与 f_r(x) 的和
• 重复执行以上步骤，直到达到停止条件

计算负梯度的例子

对于 平方损失函数，它就是残差，对于一般损失函数，它是残差的近似值

image

logloss的推导如下：

image

不同的问题下选择的损失函数不同，后面会看到，例如多分类问题下的GBDT选择的就是logloss

GBDT的各种扩展

对于不同的问题GBDT采用不同的处理方法，而这些方法的不同之处只在于 损失函数的不同

同时，应该注意，不同的损失函数下，算法的初始化方法也不同！！！！

• GBDT处理回归问题

  • 采用 平方损失函数, L(y_i,F(x_i))=\frac{1}{2} * (y_i-F(x_i))^2
  • 算法步骤：
  • 初始化：使用样本的均值
  • image
  • 参考：https://blog.csdn.net/qq_22238533/article/details/79185969

• GBDT处理二分类问题

  • 采用 logloss损失函数，推导上图有
  • 算法步骤：
  • 初始化： F_0(x) = 0.5 * log(\frac{\sum_{i=1}^Ny_i}{\sum_{i=1}^N(1-y_i)}), log中的式子表示 正样本数目/负样本数目
  • image
  • 参考：https://blog.csdn.net/qq_22238533/article/details/79192579
  • 相比回归任务，由于二分类任务最终预测的是类别，而模型输出的是连续值，因此我们还需要将预测的分值F_m(x)转换为类别
  • 对于采用 logloss损失函数的情况：P_i^+ = \frac{1}{1+e^{-F_m(x_i)}}, 代表正样本的概率
  • 对于采用 指数损失函数 的情况： P_i^+ = \frac{1}{1+e^{-2F_m(x_i)}}, 代表正样本的概率

• GBDT处理多分类问题

  • 采用一对多的策略，即每个类别分开训练树
  • 必须K个类别都训练好了第一棵树，然后再继续训练第二棵树
  • 算法步骤：
  • 初始化：原文中初始化为0，sklearn中实现的是初始化为数据先验概率（就是各类别的占比）
  • image
  • 参考：https://blog.csdn.net/qq_22238533/article/details/79199605

Adaboost 和 GBDT 的区别

• AdaBoost 是通过提升错分数据点的权重来定位模型的不足，
• AdaBoost 是以指数损失函数为损失函数

而

• Gradient Boosting 是通过算梯度（gradient）来定位模型的不足

Shrinkage

同时GDBT还使用了 shrinkage 的方法

即每一次训练出 对残差的拟合的回归树的时候，我们再乘上一个系数 \mu, 意味着每一次我们只学习残差的一小部分

在GBDT的原文中指出，每次一小步一小步的学习有足够的信心比一大步一大步的学习更容易避免过拟合

即Shrinkage仍然以残差作为学习目标，但对于残差学习出来的结果，只累加一小部分（step*残差）逐步逼近目标，step一般都比较小，如0.01~0.001（注意该step 不是 gradient的step），导致各个树的残差是渐变的而不是陡变的。直觉上这也很好理解，不像直接用残差一步修复误差，而是只修复一点点，其实就是把大步切成了很多小步。本质上，Shrinkage为每棵树设置了一个weight，累加时要乘以这个weight，但和Gradient并没有关系。这个weight就是step。就像Adaboost一样，Shrinkage能减少过拟合发生也是经验证明的，目前还没有看到从理论的证明。

Bagging方法

基础的 Bagging 方法

核心思想

使用 自助采样法 获得初始训练集中约 63.2% 的样本，如此重复M次采样，获得M个不同的数据集，根据这M个不同的数据集分别训练出M个不同的分类器

结合算法

由于一共有M个不同的分类器，需要将这M个分类器的结果合并为一个最终的结果

• 回归问题：采用简单平均法
• 分类问题：采用简单投票法

Bagging 不同于 AdaBoost，可以不加修改的应用于回归和多分类任务

Bagging 主要关注 降低方差，因此不易受到样本的扰动

随机森林

核心思想

在 Bagging方法 的基础上加上了 对特征的随机选择，每次训练时先随机选择 k 个特征作为训练的特征，推荐值： log_2d

优点

• 因为随机森林加入了对特征的随机选择（随机扰动） + 样本的随机扰动（自助采样法），所以 随机森林的 泛化性能 比Bagging更好
• 随机森林比Bagging训练效率更加高，因为每次训练的特征更少，需要判断最佳分类特征的时间更短

结合策略

平均法

• 简单平均法
• 加权平均法

面对个体学习器性能相差较大时，选用 加权平均法， 个体学习器性能相近时选用 简单平均法，因为加权平均法要学习的权重更多，更容易 过拟合

投票法

• 绝对多数投票法：若某标记得票数 超过半数 则预测为该标记
• 相对多数投票法：选取得到投票数最多的类别，若多个投票数相同，随机选择一个
• 加权投票法： 与加权平均法相似，权重是分类器的权重，同时要求权重之和为1

多样性增强

• 数据样本扰动
• 输入属性扰动
• 输入表示扰动
• 算法参数扰动

第十章 聚类

概念

聚类任务大部分是针对有未知类别(无标记)的数据（当然也可以是含有标签的数据），试图将数据划分为若干个 不相交 的子集

划分子集的过程可以看做是虚招数据内部 分布结构 的过程

聚类可以作为单独的学习任务，也可以与其他学习任务一起工作：将聚类好的子集作为数据源支撑逻辑回归预测

距离计算

在进行聚类任务的时候，经常会涉及到距离的计算，不同的算法会使用不同的距离度量方式

最常用的是 闵可夫斯基距离

dist_{mk}(x_i,x_j)=(\sum_{u=1}^n{|x_{iu}-x_{ju}|})^{\frac{1}{p}}

p=2时，就是常见的欧氏距离，p=1时，就是曼哈顿距离

对于 连续属性，有序离散属性 可以采用上面的公式计算距离，但对于 无序离散属性 采用VDM距离

VDM_P(a,b)=\sum_{i=1}^k{|\frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}}|}^p

其中，m_{u,a} 表示属性 u 上取值为 a 的样本的个数， m_{u,a,i} 表示在第 i 个样本簇中在属性 u 上取值为 a 的样本的个数

原型聚类

算法思想

先对原型进行初始化，然后对原型进行迭代更新求解

K均值算法

需要预先指定聚类簇数 K

算法步骤

• 需要预先从数据集中选择 K 个样本作为初始均值向量进行初始化
• 对每一个样本对每一个初始均值向量计算距离，将样本划入 最近 的均值向量代表的簇中
• 划分完毕后重新计算均值向量，重复以上步骤，直到数据所属类别不再变化

学习向量量化（LVQ）####

此时LVQ的数据是 含有标签 的数据

高斯混合聚类

具体参考 EM算法 中在高斯混合模型中的应用

密度聚类

假设样本的内部结构可以根据样本分布的 紧密程度 确定

DBSCAN

算法参数

• 邻域距离： \epsilon
• 邻域大小： MinPts

邻域距离： \epsilon - 邻域 包含样本集中与 x_j 距离不大于 \epsilon 的样本（决定了每一步 会 划多大的圆）

邻域大小： 作为能够扩展的要求，即\epsilon-邻域内必须至少包含MinPts个样本才能成为核心对象，拥有继续扩展的权利（决定了下一步 继续扩展的要求）

层次聚类

AGNES

采用 自底向上 的思想，先将每一个样本看做是一个簇，然后 合并 距离最近的两个簇，直到达到预设的聚类个数

距离的计算有以下三种：

• 最小距离：两个簇中的样本间的最近的距离
• 最大距离：两个簇中的样本间的最远的距离
• 平均距离：两个样本的距离的均值