MachineLearning

机器学习与模式识别

前言

学科地位：

主讲教师	学分配额	学科类别
杨琬琪	3	专业课

成绩组成：

理论课：

作业+课堂	课堂测验（2次）	期末（闭卷）
30%	20%	50%

实验课：

19次实验（五级制）
100%

教材情况：

课程名称	选用教材	版次	作者	出版社	ISBN号
机器学习与模式识别	《机器学习与模式识别》	–	周志华	清华大学出版社	978-7-302-42328-7

学习资源：

• 🍉 西瓜书 📺 视频、PPT 资源：机器学习初步、PPT - 百度网盘链接
• 🍉 西瓜书 📖 电子资源：Machine_Learning/机器学习_周志华.pdf
• 🎃 南瓜书 📺 视频资源：《机器学习公式详解》（南瓜书）与西瓜书公式推导直播合集
• 🎃 南瓜书 📖 电子资源：《机器学习》（西瓜书）公式详解

实验平台：

• AI Studio：https://aistudio.baidu.com/index

本地路径：

• 🍉 西瓜书电子书：[机器学习_周志华](D:\华为云盘\2. Score\4. 机器学习与模式识别\机器学习_周志华.pdf)
• 🎃 南瓜书电子书：[pumpkin_book](D:\华为云盘\2. Score\4. 机器学习与模式识别\pumpkin-book\pdf\pumpkin_book_1.9.9.pdf)
• 📃 上课 PPT by 周志华：[机器学习_课件_周志华](D:\华为云盘\2. Score\4. 机器学习与模式识别\机器学习_课件_周志华)
• 📃 上课 PPT by 杨琬琪：[机器学习_课件_杨琬琪](D:\华为云盘\2. Score\4. 机器学习与模式识别\机器学习_课件_杨琬琪)

第1章 绪论

1.1 引言

pass

1.2 基本术语

Name	Introduction
机器学习定义	利用经验改善系统自身性能，主要研究智能数据分析的理论和方法。
计算学习理论	最重要的理论模型是 PAC(Probably Approximately Correct, 概率近似正确) learning model，即以很高的概率得到很好的模型 $P(
P 问题	在多项式时间内计算出答案的解
NP 问题	在多项式时间内检验解的正确性
特征（属性）	–
特征（属性）值	连续 or 离散
样本维度	特征（属性）个数
特征（属性、输入）空间	特征张成的空间
标记（输出）空间	标记张成的空间
样本	<x>
样例	<x,y>
预测任务	监督学习、无监督学习、半监督学习、噪音标记学习、多标记学习
泛化能力	应对未来未见的测试样本的能力
独立同分布假设	历史和未来的数据来自相同的分布

1.3 假设空间

假设空间：所有可能的样本组合构成的集合空间

版本空间：根据已知的训练集，将假设空间中与正例不同的、反例一致的样本全部删掉，剩下的样本组合构成的集合空间

1.4 归纳偏好

No Free Launch 理论，没有很好的算法，只有适合的算法。好的算法来自于对数据的好假设、好偏执，大胆假设，小心求证

1.5 发展历程

pass

1.6 应用现状

pass

第2章 模型评估与选择

2.1 经验误差与过拟合

概念辨析

• 错误率：针对测试数据而言，分错的样本数 $a$ 占总样本数 $m$ 的比例 $E=\frac{a}{m}$
• 经验误差：针对训练数据而言，随着训练轮数或模型的复杂度越高，经验误差越小

▶

误差训练曲线

过拟合解决方法

• Early Stopping (当发现有过拟合现象就停止训练)

• Penalizing Large Weight (在经验风险上加一个正则化项)

  ▶

  正则化概念补充

  在后面的学习中经常会和正则化打交道，因此此处补充一下相关的概念。

  在目标函数中添加正则化到底有什么好处？给几个解释:

  1. 防止过拟合。为什么可以防止过拟合？其实可以形象化的将添加的正则化项理解为一个可以调节的「累赘」，为了让原始问题尽可能的最优，我让累赘愈发拖累目标函数的取值，这样原始问题就不得不更优以此来抵消累赘带来的拖累。
  2. 可以进行特征选择。个人认为属于第一点的衍生意义，为什么这么说？同样用累赘来比喻正则化项。当原始问题的某些变量为了代偿拖累导致系数都接近于零了，那么这个变量也就没有存在的意义了，于是对应的特征也就被筛选掉了，也就是所谓的特征选择了。常常添加 L1 正则化项来进行所谓的特征选择。
  3. 提升计算效率。同样可以理解为第三点的衍生意义，为什么这么说？因为你都把变量筛掉了，那么对应的解空间是不是就相应的大幅度减少了，于是最优解的搜索也就更加快速了。

  当然正则化项并非万能的万金油，在整个目标函数中正则化项有这举足轻重的意义，一旦正则化项的系数发生了微小的变动，对于整个模型的影响都是巨大的。因此有时添加正则化项并不一定可以带来泛化性能的提升。

  正则化有以下形式：

  1. 一般式：

     $$||\mathbf{x}||_p^k = \left ( \left ( \sum_{i=1}^{m}|x_i|^{p} \right)^{\frac{1}{p}} \right)^k$$

  2. L1 正则化：

     $$||\mathbf{x}||_1 = \sum_{i=1}^m |x_i|$$

  3. L2 正则化：

     $$\begin{aligned}||\mathbf{x}||_2^2 &= \left ( \left ( \sum_{i=1}^{m}|x_i|^{2} \right)^{\frac{1}{2}} \right)^2 \\&= \sum_{i=1}^{m}|x_i|^{2}\end{aligned}$$

• Bagging 思想 (对同一样本用多个模型投票产生结果)

• Boosting 思想 (多个弱分类器增强分类能力，降低偏差)

• Dropconnection (神经网络全连接层中减少过拟合的发生)

欠拟合解决方法

• 决策树：拓展分支

• 神经网络：增加训练轮数

2.2 评估方法

• 留出法（hold-out）：将数据集分为三个部分，分别为训练集、验证集、测试集。测试集对于训练是完全未知的，我们划分出测试集是为了模拟未来未知的数据，因此当下的任务就是利用训练集和验证集训练出合理的模型来尽可能好的拟合测试集。那么如何使用划分出的训练集和验证集来训练、评估模型呢？就是根据模型的复杂度 or 模型训练的轮数，根据上图的曲线情况来选择模型。

• 交叉验证法（cross validation）：一般方法为 p 次 k 折交叉验证，即 p 次将训练数据随机划分为 k 个大小相似的互斥子集。将其中 $k-1$ 份作为训练数据，$1$ 份作为验证数据，每轮执行 $k$ 次获得平均误差。执行 p 次划分主要是为了减小划分方法带来的误差。

• 自助法（bootstrapping）：有放回采样获得训练集。每轮从数据集 $D$ 中（共 $m$ 个样本）有放回的采样 $m$ 次，这 $m$ 个抽出来的样本集合 $D'$ 大约占数据集的 $\frac{2}{3}$，于是就可以将抽出的样本集合 $D'$ 作为训练集，$D-D'$ 作为测试集即可

  ▶

  测试集占比 1/3 证明过程

  

2.3 性能度量

2.3.1 回归任务

均方误差：$\displaystyle MSE=\frac{1}{m} \sum_{i=1}^m(f(x_i) - y_i)^2$

均方根误差：$\displaystyle RMSE=\sqrt{\frac{1}{m} \sum_{i=1}^m(f(x_i) - y_i)^2}$

$R^2$ 分数：$\displaystyle R^2 = 1 - \frac{\sum_{i=1}^m(f(x_i)-y_i)^2}{\sum_{i=1}^m(\bar{y} - y_i)^2},\quad \bar{y} = \frac{1}{m}\sum_{i=1}^m y_i$

▶

R-square 个人理解

首先理解各部分的含义。减数的分子表示预测数据的平方差，减数的分母表示真实数据的平方差。而平方差是用来描述数据离散程度的统计量。

为了保证回归拟合的结果尽可能不受数据离散性的影响，我们通过相除来判断预测的数据是否离散。如果和原始数据离散性差不多，那么商就接近1，R方就接近0，表示性能较差，反之如果比原始数据离散性小，那么商就接近0，R方就接近1，表示性能较优。

2.3.2 分类任务

混淆矩阵

▶

图例

• 准确率（accuracy）：$\displaystyle P=\frac{TP+TN}{TP+FN+FP+TN}$

• 查准率/精度（precision）：$\displaystyle P = \frac{TP}{TP+FP}$ - 适用场景：商品搜索推荐（尽可能推荐出适当的商品即可，至于商品数量无所谓）

• 查全率/召回率（recall）：$\displaystyle R = \frac{TP}{TP+FN}$ - 适用场景：逃犯、病例检测（尽可能将正例检测出来，至于查准率无所谓）

• F1 度量（F1-score）：$\displaystyle F_1 = \frac{2\times P \times R}{P + R}$​ - 用于综合查准率和查全率的指标

• 对于多分类问题，我们可以将该问题分解为多个二分类问题（ps：假设为 n 个）。从而可以获得多个上述的混淆矩阵，那么也就获得了多个 $P_i$、$R_i$ 以及全局均值 $\overline{TP}$、$\overline{FP}$、$\overline{FN}$，进而衍生出两个新的概念

  • 宏

    • 宏查准率：$\displaystyle macroP = \frac{1}{n} \sum_{i=1}^n P_i$
    • 宏查全率：$\displaystyle macroR = \frac{1}{n} \sum_{i=1}^n R_i$
    • 宏 $F1$：$\displaystyle macroF_1 = \frac{2 \times macroP \times macroR}{macroP+macroR}$

  • 微

    • 微查准率：$\displaystyle microP = \frac{\overline{TP}}{\overline{TP}+\overline{FP}}$
    • 微查全率：$\displaystyle microR = \frac{\overline{TP}}{\overline{TP}+\overline{FN}}$
    • 微 $F1$：$\displaystyle microF_1 = \frac{2 \times microP \times microR}{microP+microR}$

P-R 曲线

▶

图例

• 横纵坐标：横坐标为查全率（Recall），纵坐标为查准率（Precision）

• 如何产生？我们根据学习器对于每一个样本的预测值（正例性的概率）进行降序排序，然后调整截断点将预测后的样本进行二分类，将截断点之前的所有数据全部认为预测正例，截断点之后的所有数据全部认为预测反例。然后计算两个指标进行绘图。

  ▶

  什么分类任务中的是预测值？

  我们知道学习器得到最终的结果一般不是一个绝对的二值，如 0,1。往往是一个连续的值，比如 [0,1]，也就是“正例性的概率”。因此我们才可以选择合适的截断点将所有的样本数据划分为两类。

• 趋势解读：随着截断点的值不断下降，很显然查全率 $R$ 会不断上升，查准率 $P$ 会不断下降

• 不同曲线对应学习器的性能度量：曲线与横纵坐标围成的面积衡量了样本预测排序的质量。因此上图中 A 曲线的预测质量比 C 曲线的预测质量高。但是我们往往会遇到比较 A 与 B 的预测质量的情况，由于曲线与坐标轴围成的面积难以计算，因此我们引入了平衡点的概念。平衡点就是查准率与查询率相等的曲线，即 $P=R$ 的曲线。平衡点越往右上，学习器的预测性能越好。

ROC 曲线与 AUC ⭐

▶

图例

• 横纵坐标：横坐标为假正例率 $\displaystyle FPR = \frac{FP}{FP+TN}$，纵坐标为真正例率 $\displaystyle TPR = \frac{TP}{TP+FN}$

• 如何产生？与 P-R 图的产生类似，只不过计算横纵坐标的规则不同，不再赘述。

• 趋势解读：随着截断点的值不断下降，真正例率与假正例率均会不断上升，因为分子都是从 0 开始逐渐增加的

• 不同曲线对应学习器的性能度量：AUC 衡量了样本预测的排序质量。AUC 即 ROC 曲线右下方的面积，面积越大则对应的预测质量更高，学习器性能更好。不同于上述引入平衡点的概念，此处的面积我们可以直接计算，甚至 1-AUC 也可以直接计算。

  我们定义 $\text{AUC}$ 的计算公式为：（其实就是每一块梯形的面积求和，ps：矩形也可以用梯形面积计算公式代替）

  $$\sum _{i=1}^{m-1} \frac{(y_{i}+y_{i+1}) \cdot (x_{i+1} - x_i)}{2}$$

  我们定义损失函数（$loss$） $l_{rank} = 1-AUC$ 的计算公式为：（ps：感觉下述公式不是很准，因为正反例预测值相等的比例比不一定就是一比一）

  

2.4 比较检验

理论依据：统计假设检验（hypothesis test）

两个学习器性能比较：

• 交叉验证 t 检验：对于 k 折两个学习期产生的 k 个误差之差，求得其均值 $\mu$ 个方差 $\sigma ^2$，若变量 $\Gamma_t$ 小于临界值，则表明学习器没有显著差异，其中变量 $\Gamma_t$ 为

  $$\Gamma_t = |\frac{\sqrt{k}\mu}{\sigma}|$$

• McNemar 检验：对于二分类问题，我们可以得到下方的列联表

  

  若变量 $\Gamma_{\chi ^2}$ 小于临界值，则表明学习器没有显著差异，其中变量 $\Gamma_{\chi ^2}$ 为

  $$\Gamma_{\chi ^2} = \frac{(|e_{01} - e_{10}| - 1)^2}{e_{01}+e_{10}}$$

2.5 偏差与方差

现在我们得到了学习算法的泛化性能，我们还想知道为什么会有这样的泛化性能，即我们应该如何理论的解释这样的泛化性能呢？我们引入 偏差-方差分解 的概念来从理论的角度解释期望泛化误差。那么这个方法一定是完美解释的吗？也有一定的缺点，因此我们还会引入 偏差-方差窘境 的概念来解释偏差和方差对于泛化误差的贡献。

在此之前我们需要知道偏差、方差和噪声的基本定义：

• 偏差：学习算法的期望输出与真实结果的偏离程度，刻画算法本身的拟合能力。
• 方差：使用同规模的不同训练集进行训练时带来的性能变化，刻画数据扰动带来的影响。
• 噪声：当前任务上任何算法所能达到的期望泛化误差的下界（即不可能有算法取得更小的误差），刻画问题本身的难度。

2.5.1 偏差-方差分解

我们定义以下符号：$x$ 为测试样本，$y_D$ 为 $x$ 在数据集中的标记，$y$ 为 $x$ 的真实标记，$f(x;D)$ 为模型在训练集 $D$ 上学习后的预测输出。

我们以回归任务为例：（下面的全部变量均为在所有相同规模的训练集下得到的期望结果）

• 输出：$\overline{f}(x) = E_D[f(x;D)]$
• 方差：$var(x) = E_D[(\overline{f}(x) - f(x;D))^2]$
• 偏差：$bias^2(x) = (\overline{f}(x) - y)^2$
• 噪声：$\epsilon ^2 = E_D[(y_D - y)^2]$

偏差-方差分解的结论：

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

▶

推导

解释说明：泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度共同决定的。因此给定一个学习任务，我们可以从偏差和方差两个角度入手进行优化，即需要使偏差较小（充分拟合数据），且需要使方差较小（使数据扰动产生的影响小）

2.5.2 偏差-方差窘境

其实偏差和方差是有冲突的，这被称为偏差-方差窘境（bias-variance-dilemma）。对于以下的示意图我们可以知道：对于给定的学习任务。一开始拟合能力较差，学习器对于不同的训练数据不够敏感，此时泛化错误率主要来自偏差；随着训练的不断进行，学习器的拟合能力逐渐增强，对于数据的扰动更加敏感，使得方差主导了泛化错误率；在训练充分以后，数据的轻微扰动都可能导致预测输出发生显著的变化，此时方差就几乎完全主导了泛化错误率。

▶

图例

第3章 线性模型

本章介绍机器学习模型之线性模型，将从学习任务展开。学习任务分别为：

• 回归（最小二乘法、岭回归）
• 二分类（对数几率（逻辑）回归、线性判别分析）
• 多分类（一对一、一对其余、多对多）

3.1 基本形式

$$\begin{aligned} f(x_i) &= w^T x_i + b \\ w &= (w_1; w_2; \cdots; w_d), w \in R^d, b \in R \end{aligned}$$

线性模型的优点：形式简单、易于建模、高可解释性、非线性模型的基础

线性模型的缺点：线性不可分

3.2 线性回归

预测式已经在 3.1 中标明了，现在的问题就是，如何获得 $w$ 和 $b$ 使得预测值 $f(x)$ 与真实值 $y$ 尽可能的接近，也就是误差 $\epsilon = ||f(x) - y||$ 尽可能的小？在前面的 2.3 节性能度量中，我们知道对于一般的回归任务而言，可以通过均方误差来评判一个回归模型的性能。借鉴该思想，线性回归也采用均方误差理论，求解的目标函数就是使均方误差最小化。

在正式开始介绍求解参数 $w$ 和 $b$ 之前，我们先直观的理解一下均方误差。我们知道，均方误差对应了欧氏距离，即两点之间的欧几里得距离。于是在线性回归任务重，就是寻找一条直线使得所有的样本点距离该直线的距离之和尽可能的小。

基于均方误差最小化的模型求解方法被称为 最小二乘法 (least squre method)。而求解 $w$ 和 $b$ 使得目标函数 $E_{(w,b)} = \sum_{i=1}^{m}(y_i - f(x_i))$ 最小化的过程，被称为线性回归模型的 最小二乘“参数估计” (parameter estimation)。

于是问题就转化为了无约束的最优化问题求解。接下来我们将从一元线性回归引入，进而推广到多维线性回归的参数求解，最后补充广义的线性回归与其他线性回归的例子。

3.2.1 一元线性回归

现在假设只有一个属性 x，对应一维输出 y。现在我们试图根据已知的 <x,y> 样本数据学习出一个模型 $f(x_i) = wx_i+b$ 使得尽可能准确的预测未来的数据。那么此时如何求解模型中当目标函数取最小值时的参数 w 和 b 呢？很显然我们可以使用无约束优化问题的一阶必要条件求解。

▶

参数 w 和 b 的求解推导（式 3.7、式 3.8）

前置说明：在机器学习中，很少有闭式解（解析解），但是线性回归是特例，可以解出闭式解。

闭式解推导过程：

3.2.2 多元线性回归

现在我们保持输出不变，即 $y$ 仍然是一维，将输入的样本特征从一维扩展到 $d$ 维。现在同样适用最小二乘法，来计算 $w$ 和 $b$ 使得均方误差最小。只不过现在的 $w$ 是一个一维向量 $w = (w_1,w_2, \cdots , w_d)$

现在我们按照原来的方法进行求解。在求解之前我们采用向量的方式简化一下数据的表示，$X$ 为修改后的样本特征矩阵，$\hat w$ 为修改后的参数矩阵，$y$ 为样本标记值，$f(x)$ 为模型学习结果：

$$X = \begin{bmatrix} x_{11} & x_{12} & \cdots & x_{1d} & 1 \\ x_{21} & x_{22} & \cdots & x_{2d} & 1 \\ \vdots & \vdots & & \vdots & 1 \\ x_{m1} & x_{m2} & \cdots & x_{md} & 1 \end{bmatrix} , \hat w = (w;b) = \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_d \\ b \end{bmatrix} , y = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_m \end{bmatrix} , f(x) = \begin{bmatrix} f(x_1) \\ f(x_2) \\ \vdots \\ f(x_m) \end{bmatrix} = \begin{bmatrix} x_1 ^ T \hat w \\ x_2 ^ T \hat w \\ \vdots \\ x_d ^ T \hat w \end{bmatrix}$$

于是损失函数 $E_{\hat w}$ 就定义为：

$$E_{\hat w} = (y - X \hat w) ^T (y - X \hat w)$$

我们用同样的方法求解其闭式解：

▶

参数 w 的求解推导（式 3.10，非岭回归+岭回归）

我们不能直接等式两边同 $\times$ 矩阵 $X^TX$ 的逆，因为不清楚其是否可逆，于是进行下面的两种分类讨论：

1. $X^T X$​ 可逆：则参数 $\hat w ^* = (X^TX)^{-1}X^Ty$，令样本 $\hat x_i = (x_i,1)$，则线性回归模型为：

   $$f(x_i) = \hat x_i ^T \hat w^*$$

2. $X^T X$ 不可逆：我们引入 $L_2$ 正则化项 $\alpha || \hat w ||^2$，此时就是所谓的「岭回归」算法：

   现在的损失函数就定义为：

   $$E_{\hat w} = (y - X \hat w) ^T (y - X \hat w) + \alpha || \hat w ||^2$$

   同样将损失函数对参数向量 $\hat w$ 求偏导，得：

   $$\begin{aligned}\frac{\partial E_{\hat w}}{\partial \hat w} &= \cdots \\&= 2X^TX\hat w - 2 X^T y + 2 \alpha \hat w \\&= 2 X ^T(X \hat w - y) + 2 \alpha \hat w\end{aligned}$$

   我们令其为零，得参数向量 $\hat w$ 为：

   $$\hat w = (X^T X + \alpha I)^{-1} X^T y$$

3.2.3 广义线性回归

可否令模型的预测值 $w^Tx+b$ 逼近 $y$ 的衍生物？我们以对数线性回归为例，令：

$$\ln y = w^Tx+b$$

本质上我们训练的线性模型 $\ln y = w^Tx+b$ 现在可以拟合非线性数据 $y = e^{w^Tx+b}$。更广义的来说，就是让训练的线性模型去拟合：

$$y = g^{-1}(w^Tx+b)$$

此时得到的线性模型 $g(y) = w^Tx +b$ 被称为广义线性模型，要求非线性函数 $g(\cdot)$ 是单调可微的。而此处的对数线性回归其实就是广义线性模型在 $g(\cdot) = \ln (\cdot)$ 时的特例

▶

线性模型拟合非线性数据图例：对数线性回归

3.2.4 其他线性回归

• 支持向量机回归

• 决策树回归

• 随机森林回归

• LASSO 回归：增加 $L_1$ 正则化项

  

• ElasticNet 回归：增加 $L_1$ 和 $L_2$ 正则化项

  

• XGBoost 回归

3.3 对数几率回归

对数几率回归准确来说应该叫逻辑回归，并且不是回归的学习任务，而是二分类的学习任务。本目将从阈值函数的选择和模型参数的求解两个维度展开讲解。

3.3.1 阈值函数的选择

对于二分类任务。我们可以将线性模型的输出结果 $z=w^Tx+b$ 通过阈值函数 $g(\cdot)$ 进行映射，然后根据映射结果 $y=g(z)$ 进行二分类。那么什么样的非线性函数可以胜任阈值函数一职呢？

1. 最简单的一种阈值函数就是单位阶跃函数。映射关系如下。但是有一个问题就是单位阶跃函数不是单调可微函数，因此不可取

   ▶

   为什么阈值函数需要单调可微呢？

   一直有一个疑问，单位跃阶函数已经可以将线性模型的进行二值映射了，干嘛还要求阈值函数的反函数呢？

   其实是因为知道的太片面了。我们的终极目的是为了通过训练数据，学习出线性模型中的 $w$ 和 $b$ 参数。在《最优化方法》课程中我们知道，优化问题是需要进行迭代的，在迭代寻找最优解（此处就是寻找最优参数）的过程中，我们需要不断的检验当前解，以及计算修正量。仅仅知道线性模型 $z=w^Tx+b$ 关于阈值函数 $g(\cdot)$ 的映射结果 $y=g(z)$ 是完全不够的，因为我们在检验解、计算修正量时，采用梯度下降等算法来计算损失函数关于参数 $w$ 和 $b$ 的导数时，需要进行求导操作，比如上述损失函数 $E_{(w,b)} = \sum_{i=1}^m (y_i - g(x_i))^2$，如果其中的 $g(\cdot)$ 不可导，自然也就没法继续计算损失函数关于参数的导数了。

   至此疑问解决！让我们畅快的学习单调可微的阈值函数吧！

   $$y = \begin{cases} 0, &z < 0 \\ 0.5,& z=0 \\ 1, & z>0 \end{cases}$$

2. 常用的一种阈值函数是对数几率函数，也叫逻辑函数（$\text{logistic function}$）。映射关系如下：

   $$y = \frac{1}{1+e^{-z}}$$

3.3.2 模型参数的求解

现在我们站在前人的肩膀上学习到了一种阈值函数：逻辑函数（$\text{logistic function}$）。在开始讲解参数 $w$ 和 $b$ 的求解过程之前，我们先解决一个疑问：为什么英文名是 $\text{logistic}$​，中文翻译却成了 对数几率 函数呢？

▶

“对数几率”名称解读

这就要从逻辑函数的实际意义出发了。对于逻辑函数，我们代入线性模型，并做以下转化：

$$\begin{aligned}& y = \frac{1}{1 + e^{-z}} \\& y = \frac{1}{1 + e^{-(w^Tx+b)}} \\& \ln \frac{y}{1 - y} = w^Tx+b \\\end{aligned}$$

若我们定义 $y$ 为样本 $x$ 是正例的可能性，则 $1-y$ 显然就是反例的可能性。两者比值 $\frac{y}{1-y}$ 就是几率，取对数 $\ln{\frac{y}{1-y}}$ 就是对数几率。

知道了逻辑函数的实际意义是真实标记的对数几率以后，接下来我们实际意义出发，讲解模型参数 $w$ 和 $b$​ 的推导过程。

▶

推导

若我们将 $y$ 视作类后验概率 $p(y=1 \ | \ x)$​，则有

$$\ln \frac{p(y=1 \ | \ x)}{p(y=0 \ | \ x)} = w^Tx+b$$

同时，显然有

$$\begin{aligned}p(y=1 \ | \ x) = \frac{1}{1 + e^{-(w^Tx+b)}} = \frac{e^{w^Tx+b}}{1 + e^{w^Tx+b}} \\p(y=0 \ | \ x) = \frac{e^{-(w^Tx+b)}}{1 + e^{-(w^Tx+b)}} = \frac{1}{1 + e^{w^Tx+b}}\end{aligned}$$

于是我们可以确定目标函数了。我们取当前目标函数为对数似然函数：

$$\arg \max_{w,b} l(w,b) = \sum_{i=1}^m \ln p(y_i\ | \ x_i;w,b)$$

显然的，当上述目标函数取最大值时，得到的参数 $w$ 和 $b$​ 即为所求。因为目标函数尽可能大就对应样本属于真实标记的概率尽可能大，也就是所谓的最大化类后验概率。

我们将变量进行一定的变形：

$$\begin{aligned}\begin{cases}\beta = (w;b) \\\hat x = (x;1) \\\end{cases}&\to w^Tx + b = \beta^T\hat x \\\begin{cases}p_1(\hat x; \beta) = p(y = 1 \ | \ \hat x; \beta) \\p_0(\hat x; \beta) = p(y = 0 \ | \ \hat x; \beta) \\\end{cases}&\to p(y_i\ | \ x_i;w,b) = y_i p_1(\hat x; \beta) + (1 - y_i) p_0(\hat x; \beta)\end{aligned}$$

于是上述对数似然函数就可以进行以下转化：

$$\begin{aligned}l(w,b) &= l(\beta) \\&= \sum_{i=1}^m \ln \left [y_i p_1(\hat x; \beta) + (1 - y_i) p_0(\hat x; \beta) \right ] \\&= \sum_{i=1}^m \ln \left [y_i p(y = 1 \ | \ \hat x; \beta) + (1 - y_i) p(y = 0 \ | \ \hat x; \beta) \right ] \\&= \sum_{i=1}^m \ln \left [ y_i \frac{e^{\beta^T\hat x}}{1 + e^{\beta^T\hat x}} + (1-y_i) \frac{1}{1 + e^{\beta^T\hat x}} \right ] \\&= \sum_{i=1}^m \ln \left [ \frac{y_i \beta^T\hat x +1 -y_i}{1 + e^{\beta^T\hat x}} \right ] \\&= \begin{cases}\sum_{i=1}^m \ln \left ( \frac{1}{1 + e^{\beta^T\hat x}} \right ), & y_i=0 \\\sum_{i=1}^m \ln \left ( \frac{e^{\beta^T\hat x}}{1 + e^{\beta^T\hat x}} \right ), & y_i=1\\\end{cases}\\&= \sum_{i=1}^m \ln \left ( \frac{\left(e^{\beta^T\hat x}\right)^{y_i}}{1 + e^{\beta^T\hat x}} \right ) \\&= \sum_{i=1}^m \left( y_i e^{\beta^T\hat x} - \ln({1 + e^{\beta^T\hat x}})\right )\end{aligned}$$

进而从极大似然估计转化为：求解「极小化负的上述目标函数时」参数 $\beta$ 的值：

$$\arg \min_{\beta} l(\beta) = \sum_{i=1}^m \left(- y_i e^{\beta^T\hat x} + \ln({1 + e^{\beta^T\hat x}})\right )$$

由于上式是关于 $\beta$ 的高阶可导连续凸函数，因此我们有很多数值优化算法可以求得最优解时的参数值，比如梯度下降法、拟牛顿法等等。我们以牛顿法（Newton Method）为例：

目标函数：

$$\beta ^* = \arg \min_{\beta} l(\beta)$$

第 $t+1$​ 轮迭代解的更新公式：

$$\beta ^{t+1} = \beta^t - \left( \frac{\partial^2{l(\beta)}}{\partial{\beta} \partial{\beta^T}} \right)^{-1} \frac{\partial{l(\beta)}}{\partial{\beta}}$$

其中 $l(\beta)$ 关于 $\beta$ 的一阶导、二阶导的推导过程如下：

3.4 线性判别分析

线性判别分析的原理是：对于给定的训练集，设法将样本投影到一条直线上，使得同类的投影点尽可能接近，异类样本的投影点尽可能远离；在对新样本进行分类时，将其投影到这条直线上，再根据投影点的位置来确定新样本的类别。

3.5 多分类学习

我们一般采用多分类+集成的策略来解决多分类的学习任务。具体的学习任务大概是：将多分类任务拆分为多个二分类任务，每一个二分类任务训练一个学习器；在测试数据时，将所有的分类器进行集成以获得最终的分类结果。这里有两个关键点：如何拆分多分类任务？如何集成二分类学习器？集成策略见第 8 章，本目主要介绍多分类学习任务的拆分。主要有三种拆分策略：一对多、一对其余、多对多。对于 N 个类别而言：

3.5.1 一对一

▶

图例

• 名称：One vs. One，简称 OvO
• 训练：需要对 N 个类别进行 $\frac{N(N-1)}{2}$ 次训练，得到 $\frac{N(N-1)}{2}$ 个二分类学习器
• 测试：对于一个样本进行分类预测时，需要用 $\frac{N(N-1)}{2}$ 个学习器分别进行分类，最终分得的结果种类最多的类别就是样本的预测类别
• 特点：类别较少时，时间和内存开销往往更大；类别较多时，时间开销往往较小

3.5.2 一对其余

▶

图例

• 名称：One vs. Rest，简称 OvR
• 训练：需要对 N 个类别进行 $N$ 次训练，得到 $N$ 个二分类学习器。每次将目标类别作为正例，其余所有类别均为反例
• 测试：对于一个样本进行分类预测时，需要用 $N$ 个学习器分别进行分类，每一个学习器显然只会输出二值，假定为正负。正表示当前样例属于该学习器的正类，反之属于反类。若 $N$ 个学习器输出了多个正类标签，则还需通过执行度选择最终的类别。

3.5.3 多对多

▶

图例

• 名称：Many vs. Many，简称 MvM
• 训练（编码）：对于 N 个类别数据，我们自定义 M 次划分。每次选择若干个类别作为正类，其余类作为反类。每一个样本在 M 个二分类学习器中都有一个分类结果，也就可以看做一个 M 维的向量。m 个样本也就构成了 m 个在 M 维空间的点阵。
• 测试（解码）：对于测试样本，对于 M 个学习器同样也会有 M 个类别标记构成的向量，我们计算当前样本与训练集构造的 m 个样本的海明距离、欧氏距离，距离当前测试样本最近的点属于的类别，我们就认为是当前测试样本的类别。

3.5.4 softmax

类似于 M-P 神经元，目的是为了将当前测试样本属于各个类别的概率之和约束为 1。

3.6 类别不平衡问题

在分类任务的数据集中，往往会出现类别不平衡的问题，即使在类别的样本数量相近时，在使用一对其余等算法进行多分类时，也会出现类比不平衡的问题，因此解决类比不平衡问题十分关键。

3.6.1 阈值移动

常规而言，对于二分类任务。我们假设 $y$ 为样本属于正例的概率，则 $p=\frac{y}{1-y}$ 就是正确划分类别的概率。在假定类别数量相近时，我们用下式表示预测为正例的情况：

$$\frac{y}{1-y}>1$$

但是显然，上述假设不总是成立，我们令 $m^+$ 为样本正例数量，$m^-$ 为样本反例数量。我们用下式表示预测为正例的情况：

$$\frac{y}{1-y} > \frac{m^+}{m^-}$$

根本初衷是为了让 $\frac{m^+}{m^-}$ 表示数据类别的真实比例。但是由于训练数据往往不能遵循独立分布同分布原则，也就导致我们观测的 $\frac{m^+}{m^-}$ 其实不能准确代表数据的真实比例。那还有别的解决类别不平衡问题的策略吗？答案是有的！

3.6.2 欠采样

即去除过多的样本使得正反例的数量近似，再进行学习。

• 优点：训练的时间开销小
• 缺点：可能会丢失重要信息

典型的算法是：EasyEnsemble

3.6.3 过采样

即对训练集中类别数量较少的样本进行重复采样，再进行学习。

• 缺点：简单的重复采样会导致模型过拟合数据，缺少泛化能力。

典型的算法是：SMOTE

第4章 决策树

4.1 基本流程

决策树算法遵循自顶向下、分而治之的思想。

决策树结构解读：

▶

图例

1. 非叶子结点：属性
2. 边：属性值
3. 叶子结点：分类结果

决策树生成过程：

▶

伪代码

1. 生成结点：选择最优的属性作为当前结点决策信息
2. 产生分支：根据结点属性，为测试数据所有可能的属性值生成一个分支
3. 生成子结点：按照上述分支属性对当前训练样本进行划分
4. 不断递归：不断重复上述 1-3 步直到递归终点
5. 递归终点：共三种（存疑）
   1. 当前结点的训练样本类别均属于某个类别。则将当前结点设定为叶子结点，并标记当前叶子结点对应的类别为当前结点同属的类别
   2. 当前结点的训练样本数为 $0$。则将当前结点为设定为叶子结点，并标记当前叶子结点对应的类别为父结点中最多类别数量对应的类别
   3. 当前结点的训练样本的所有属性值都相同。则将当前结点设定为叶子结点，并标记当前叶子结点对应的类别为当前训练样本中最多类别数量对应的类别

4.2 划分选择

现在我们解决 4.1 节留下的坑，到底如何选择出当前局面下的最优属性呢？我们从“希望当前结点的所包含的样本尽可能属于同一类”的根本目的出发，讨论三种最优属性选择策略。

4.2.1 信息增益

第一个问题：如何度量结点中样本的纯度？ 我们引入 信息熵 (information entropy) 的概念。显然，信息熵越小，分支结点的纯度越高；信息熵越大，分支结点的纯度越低。假设当前样本集合中含有 $t$ 个类别，第 $k$ 个类别所占样本集合比例为 $p_k$，则当前样本集合的信息熵 $\text{Ent}(D)$ 为：

$$\text{Ent}(D) = -\sum _{k=1}^t p_k \log_2(p_k)$$

第二个问题：如何利用结点纯度选择最优属性进行划分？ 我们引入 信息增益 (Information gain) 的概念。显然，我们需要计算每一个属性对应的信息增益，然后取信息增益最大的属性作为当前结点的最优划分属性。假设当前结点对应的训练数据集为 $D$，可供选择的属性列表为 $a,b,\cdots,\gamma$。我们以 $a$ 为例给出信息增益的表达式。假设属性 $a$ 共有 $V$ 个属性值，即 $a=\{a^1,a^2,\cdots.a^V\}$，于是便可以将当前结点对应的训练数据集 $D$ 划分为 $V$ 个子结点的训练数据 $D=\{D^1,D^2,\cdots.D^V\}$，由于每一个子结点划到的训练数据量不同，引入权重理念，得到最终的信息增益表达式为：

$$\text{Gain}(D,a)=\text{Ent}(D) - \sum_{i=1}^V \frac{|D^i|}{|D|} \text{Ent}(D^i)$$

代表算法：ID3

▶

信息增益解读

为了更好的理解信息增益的表达式，我们从终极目标考虑问题。我们知道，决策树划分的终极目的是尽可能使得子结点中的样本纯度尽可能高。对于当前已知的结点，信息熵已经是一个定值了，只有通过合理的划分子结点才能使得整体的熵减小，因此我们从划分后熵减的理念出发，得到了信息增益的表达式。并且得出熵减的结果（信息增益）越大，对应的属性越优。

4.2.2 增益率

由于信息增益会在属性的取值较多时有偏好，因此我们引入 增益率 (Gain ratio) 的概念来减轻这种偏好。显然，增益率越大越好

我们定义增益率为：

$$\text{Gain}\_\text{ratio}(D,a) = \frac{\text{Gain}(D,a)}{\text{IV}(a)}$$

可以看到就是将信息增益除上了一个值 $\text{IV}(a)$，我们定义属性 $a$ 的固有值 $\text{IV}(a)$ 为：

$$\text{IV}(a) = -\sum_{i=1}^V \frac{|D^i|}{|D|} \log_2 \frac{|D^i|}{|D|}$$

一般而言，属性的属性取值越多，信息增益越大，对应的 $\text{IV}(a)$ 的值也越大，这样就可以在一定程度上抵消过大的信息增益

代表算法：C4.5

4.2.3 基尼指数

最后引入一种最优划分策略：使用 基尼指数 (Gini index) 来划分。基尼指数越小越好。假设当前样本集合中含有 $t$ 个类别，第 $k$ 个类别所占样本集合比例为 $p_k$，则当前样本集合 $D$ 的基尼值 $\text{Gini(D)}$ 定义为：

$$\text{Gini(D)} = 1 - \sum_{k=1}^{t}p_k^2$$

于是属性 $a$ 的基尼指数 $\text{Gini}\_\text{index}(D,a)$ 定义为：

$$\text{Gini}\_\text{index}(D,a) = \sum_{i=1}^V \frac{|D^i|}{|D|} \text{Gini}(D^i)$$

代表算法：CART

4.3 剪枝处理

处理过拟合的策略：剪枝。

4.3.1 预剪枝

基于贪心的思想，决策每次划分是否需要进行。我们知道最佳属性的选择是基于信息增益等关于结点纯度的算法策略，而是否进行子结点的生成需要我们进行性能评估，即从测试精度的角度来考虑。因此决策划分是否进行取决于子结点生成前后在验证集上的测试精度，如果可以得到提升则进行生成，反之则不生成子结点，也就是预剪枝的逻辑。

4.3.2 后剪枝

同样是预剪枝的精度决策标准。我们在一个决策树完整生成以后，从深度最大的分支结点开始讨论是否可以作为叶子结点，也就是是否删除该分支的子结点。决策的依据是删除子结点前后在测试集上的精度是否有提升，如果有则删除子结点，反之不变。

4.3.3 区别与联系（补）

预剪枝是基于贪心，也就是说没有考虑到全局的情况，可能出现当前结点划分后测试精度下降，但是后续结点继续划分会得到性能提升，从而导致预剪枝的决策树泛化性能下降。

后剪枝就可以规避贪心导致的局部最优。但是代价就是时间开销更大。

4.4 连续与缺失值

4.4.1 连续值处理

这里讲解二分法 (bi-partition)。主要就是在计算信息增益时增加了一步，将属性的取值情况划分为了两类。那么如何划分呢？关键在于划分点的取值。假设当前属性 a 的取值是连续值，去重排序后得到 n 个数值，我们取这 n 个数值的 n-1 个间隔的中值作为划分点集合，枚举其中的每一个划分点计算最大信息增益，对应的划分点就是当前连续取值的属性的二分划分点。时间复杂度极高！也不知道 C4.5 算法怎么想的

4.4.2 缺失值处理

当然我们可以直接删除含有缺失信息的样本，但是这对数据信息过于浪费，尤其是当数据量不大时，如何解决这个问题呢？我们需要解决两个问题：

1. 在选择最优划分属性时，如何计算含有缺失值的属性对应的信息增益呢？
2. 在得到最优划分属性时，如何将属性值缺失的样本划分到合理的叶子结点呢？

对于第一个问题：只计算属性值没有缺失的样本，然后放缩到原始的数据集合大小即可

对于第二个问题：对于已知属性值的样本，我们可以计算出每一个属性值的样本数量，从而计算出一个集合比例，这样对于未知属性值的样本，只需要按照前面计算出来的集合，按照概率划分到对应的子结点即可

4.5 多变量决策树

很好，本目就是来解决上述连续值处理的过高时间复杂度的问题的。现在对于一个结点，不是选择最优划分属性，而是对建一个合适的线性分类器，如图：

第5章 神经网络

5.1 神经元模型

我们介绍 M-P 神经元模型。该神经元模型必须具备以下三个特征：

1. 输入：来自其他连接的神经元传递过来的输入信号
2. 处理：输入信号通过带权重的连接进行传递，神经元接受到所有输入值的总和，再与神经元的阈值进行比较
3. 输出：通过激活函数的处理以得到输出

激活函数可以参考 3.3 中的逻辑函数（logistic function），此处将其声明为 sigmoid 函数，同样不采用不。连续光滑的分段函数。

5.2 感知机与多层网络

本目从无隐藏层的感知机出发，介绍神经网络在简单的线性可分问题上的应用；接着介绍含有一层隐藏层的多层感知机，及其对于简单的非线性可分问题上的应用；最后引入多层前馈神经网络模型的概念。

5.2.1 感知机

感知机（Perceptron）由两层神经元组成。第一层是输入层，第二层是输出层。其中只有输出层的神经元为功能神经元，也即 M-P 神经元。先不谈如何训练得到上面的 $w_1,w_2,\theta$，我们先看看上面的感知机训练出来以后可以有什么功能？

通过单层的感知机，我们可以实现简单的线性可分的分类任务，比如逻辑运算中的 与、或、非 运算，下面演示一下如何使用单层感知机实现上述三种逻辑运算：

▶

使用单层感知机实现线性可分任务：与、或、非三种逻辑运算

与运算、或运算是二维线性可分任务，一定可以找到一条直线将其划分为两个类别：

非运算是一维线性可分任务，同样也可以找到一条直线将其划分为两个类别：

5.2.2 多层感知机

所谓的多层感知机其实就是增加了一个隐藏层，则神经网络模型就变为三层，含有一个输入层，一个隐藏层，和一个输出层，更准确的说应该是“单隐层网络”。其中隐藏层和输出层中的所有神经元均为功能神经元。

为了学习出网络中的连接权 $w_i$ 以及所有功能神经元中的阈值 $\theta_j$，我们需要通过每一次迭代的结果进行参数的修正，对于连接权 $w_i$ 而言，我们假设当前感知机的输出为 $\hat y$，则连接权 $w_i$ 应做以下调整。其中 $\eta$ 为学习率。

$$\begin{aligned} w_i \leftarrow w_i + \Delta w_i \\ \Delta_i = \eta (y - \hat y) x_i \end{aligned}$$

▶

使用多层感知机实现异或逻辑运算

5.2.3 多层前馈神经网络

所谓多层前馈神经网络，定义就是各层神经元之间不会跨层连接，也不存在同层连接，其中：

• 输入层仅仅接受外界输入，没有函数处理功能
• 隐藏层和输出层进行函数处理

5.3 误差逆传播算法

多层网络的学习能力比感知机的学习能力强很多。想要训练一个多层网络模型，仅仅通过感知机的参数学习规则是不够的，我们需要一个全新的、更强大的学习规则。这其中最优秀的就是误差逆传播算法（errorBackPropagation，简称 BP），往往用它来训练多层前馈神经网络。下面我们来了解一下 BP 算法的内容、参数推导与算法流程。

5.3.1 模型参数

我们对着神经网络图，从输入到输出进行介绍与理解：

• 隐层：对于隐层的第 $h$ 个神经元
  • 输入：$\alpha_h = \sum_{i=1}^dx_i v_{ih}$
  • 输出：$b_h = f(\alpha_h - \gamma_h)$
• 输出层：对于输出层的第 $j$ 个神经元
  • 输入：$\beta_j=\sum_{h=1}^q b_h w_{hj}$
  • 输出：$\hat y_j = f(\beta j - \theta_j)$

现在给定一个训练集学习一个分类器。其中每一个样本都含有 $d$ 个特征，$l$ 个输出。现在使用标准 BP 神经网络模型，每输入一个样本都迭代一次。对于单隐层神经网络而言，一共有 4 种参数，即：

• 输入层到隐层的 $d \times q$ 个权值 $v_{ih}(i=1,2,\cdots,d,\ h=1,2,\cdots,q)$
• 隐层的 $q$ 个 M-P 神经元的阈值 $\gamma_h(h=1,2,\cdots,q)$​
• 隐层到输出层的 $q\times l$ 个权值 $w_{hj}(h=1,2,\cdots,q,\ j=1,2,\cdots,l)$
• 输出层的 $l$ 个 M-P 神经元的阈值 $\theta_j(j=1,2,\cdots,l)$

5.3.2 参数推导

确定损失函数。

• 对于上述 4 种参数，我们均采用梯度下降策略。以损失函数的负梯度方向对参数进行调整。每次输入一个训练样本，都会进行一次参数迭代更新，这叫标准 BP 算法。

• 根本目标是使损失函数尽可能小，我们定义损失函数 $E$ 为当前样本的均方误差，并为了求导计算方便添加一个常量 $\frac{1}{2}$，对于第 $k$ 个训练样本，有如下损失函数：

$$E_k = \frac{1}{2} \sum _{j=1}^l (\hat y_j^k - y_j^k)^2$$

确定迭代修正量。

• 假定当前学习率为 $\eta$，对于上述 4 种参数的迭代公式为：

  $$\begin{aligned} w_{hj} &\leftarrow w_{hj}+\Delta w_{hj} \\ \theta_{j} &\leftarrow \theta_{j}+\Delta \theta_{j} \\ v_{ih} &\leftarrow v_{ih}+\Delta v_{ih} \\ \gamma_{h} &\leftarrow \gamma_{h}+\Delta \gamma_{h} \\ \end{aligned}$$

• 其中，修正量分别为：

  $$\begin{aligned} \Delta w_{hj} &= \eta g_j b_h \\ \Delta \theta_{j} &= -\eta g_j \\ \Delta v_{ih} &= \eta e_h x_i \\ \Delta \gamma_{h} &= -\eta e_h \\ \end{aligned}$$

▶

修正量推导 - 链式法则

公式表示：

隐层到输出层的权重、输出神经元的阈值：

输入层到隐层的权重、隐层神经元的阈值：

5.3.3 算法流程

对于当前样本的输出损失 $E_k$ 和学习率 $\eta$，我们进行以下迭代过程：

还有一种 BP 神经网络方法就是累计 BP 神经网络算法，基本思路就是对于全局训练样本计算累计误差，从而更新参数。在实际应用过程中，一般先采用累计 BP 算法，再采用标准 BP 算法。还有一种思路就是使用随机 BP 算法，即每次随机选择一个训练样本进行参数更新。

第6章 支持向量机

依然是分类学习任务。我们希望找到一个超平面将训练集中样本划分开来，那么如何寻找这个超平面呢？下面开始介绍。

本章知识点逻辑链：

6.1 间隔与支持向量

对于只有两个特征，输出只有两种状态的训练集而言，很显然我们得到如下图所示的超平面，并且显然应该选择最中间的泛化能力最强的那一个超平面：

我们定义超平面为：

$$w^Tx+b=0$$

定义支持向量机为满足下式的样例：

$$\begin{aligned} w^T+b&=1 \\ w^T+b&=-1 \end{aligned}$$

很显然，为了求得这“最中间”的超平面，就是让异类支持向量机之间的距离尽可能的大，根据两条平行线距离的计算公式，可知间隔为：

$$\gamma = \frac{2}{|| w ||}$$

于是最优化目标函数就是：

$$\max_{w,b} \frac{2}{||w||}$$

可以等价转化为：

$$\begin{aligned} &\min_{w,b} \frac{1}{2} ||w||^2 \\ &s.t. \quad y_i(w^Tx_i+b) \ge 1 \quad(i=1,2,\cdots,m) \end{aligned}$$

这就是 SVM（support vector machine）的基本型

6.2 对偶问题

将上述 SVM 基本型转化为对偶问题，从而可以更高效的求解该最优化问题。

▶

对偶转化推导

于是模型 $f(x)$​ 就是：

$$\begin{aligned}f(x) &= w^Tx+b \\&= \sum_{i=1}^m\alpha_iy_ix_i^Tx+b\end{aligned}$$

其中参数 b 的求解可通过支持向量得到：

$$y_if(x_i) = 1 \to y_i\left(\sum_{i=1}^m\alpha_iy_ix_i^Tx+b \right)=1$$

由于原问题含有不等式约束，因此还需要满足 KKT 条件：

$$\begin{cases}\alpha_i \ge 0&,\text{对偶可行性} \\y_if(x_i) \ge 1&,\text{原始可行性} \\\alpha_i(y_if(x_i)-1) = 0&,\text{互补松弛性}\end{cases}$$

对于上述互补松弛性：

• 若 $\alpha_i > 0$，则 $y_if(x_i)=1$，表示支持向量，需要保留
• 若 $y_if(x_i)>1$，则 $\alpha_i = 0$​，表示非支持向量，不用保留

现在得到的对偶问题其实是一个二次规划问题，我们可以采用 SMO（Sequential Minimal Optimization） 算法求解。具体略。

6.3 核函数

对原始样本进行升维，即 $x_i \to \phi(x_i)$，新的问题出现了，计算内积 $\phi(x_i)^T \phi(x_i)$ 变得很困难，我们尝试解决这个内积的计算，即使用一个函数（核函数）来近似代替上述内积的计算结果，常用的核函数如下：

表格中的高斯核也就是所谓的径向基函数核 $\text{(Radial Basis Function Kernel, 简称 RBF 核)}$，其中的参数 $\gamma=\frac{1}{2\sigma^2}$，因此 RBF 核的表达式也可以写成：

$$\kappa(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)$$

• 当 $\gamma$ 较大时，$\exp(-\gamma \|x_i - x_j\|^2)$ 的衰减速度会很快。这意味着只有非常接近的样本点才会有较高的相似度。此时，模型会更关注局部特征。并且会导致模型具有较高的复杂度，因为模型会更容易拟合训练数据中的细节和噪声，从而可能导致过拟合。
• 当 $\gamma$ 较小时，$\exp(-\gamma \|x_i - x_j\|^2)$ 的衰减速度会变慢。较远的样本点之间也可能会有较高的相似度。此时，模型会更关注全局特征。但此时模型的复杂度较低，容易忽略训练数据中的细节，从而可能导致欠拟合

6.4 软间隔与正则化

对于超平面的选择，其实并不是那么容易，并且即使训练出了一个超平面，我们也不知道是不是过拟合产生的，因此我们需要稍微减轻约束条件的强度，因此引入软间隔的概念。

我们定义软间隔为：某些样本可以不严格满足约束条件 $y_i(w^Tx+b) \ge 1$ 从而需要尽可能减少不满足的样本个数，因此引入新的优化项：替代损失函数

$$l_{\text{option}}$$

常见的平滑连续的替代损失函数为：

我们引入松弛变量 $\xi_i$ 得到原始问题的最终形式：

$$\min_{w,b,\xi_i} \quad \frac{1}{2}||w||^2+C\sum_{i=1}^m \xi_i$$

6.5 支持向量回归

支持向量回归（Support Vector Regression，简称 SVR）与传统的回归任务不同，传统的回归任务需要计算每一个样本的误差，而支持向量回归允许有一定的误差，即，仅仅计算落在隔离带外面的样本损失。

原始问题：

对偶问题：

KKT 条件：

预测模型：

6.6 核方法

通过上述：支持向量基本型、支持向量软间隔化、支持向量回归，三个模型的学习，可以发现最终的预测模型都是关于核函数与拉格朗日乘子的线性组合，那么这是巧合吗？并不是巧合，这其中其实有一个表示定理：

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

第7章 贝叶斯分类器

7.1 贝叶斯决策论

pass

7.2 极大似然估计

根本任务：寻找合适的参数 $\hat \theta$ 使得「当前的样本情况发生的概率」最大。又由于假设每一个样本相互独立，因此可以用连乘的形式表示上述概率，当然由于概率较小导致连乘容易出现浮点数精度损失，因此尝尝采用取对数的方式来避免「下溢」问题。也就是所谓的「对数似然估计」方法。

我们定义对数似然 $\text{(log-likelihood)}$ 估计函数如下：

$$\begin{aligned} LL(\theta_c) &= \log P(D_c\ |\ \theta_c) \\ &= \sum_{x \in D_c} \log P(x\ |\ \theta_c) \end{aligned}$$

此时参数 $\hat \theta$ 的极大似然估计就是：

$$\hat \theta_c = \arg \max_{\theta_c} LL(\theta_c)$$

7.3 朴素贝叶斯分类器

我们定义当前类别为 $c$，则 $P(c)$ 称为类先验概率，$P(x\ |\ c)$ 称为类条件概率。最终的贝叶斯判定准则为：

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

现在假设各属性之间相互独立，则对于拥有 d 个属性的训练集，在利用贝叶斯定理时，可以通过连乘的形式计算类条件概率 $P(x \ | \ c)$，于是上式变为：

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

注意点：

• 对于离散数据。上述类条件概率的计算方法很好计算，直接统计即可
• 对于连续数据。我们就没法直接统计数据数量了，替换方法是使用高斯函数。我们根据已有数据计算得到一个对于当前属性的高斯函数，后续计算测试样例对应属性的条件概率，代入求得的高斯函数即可。
• 对于类条件概率为 0 的情况。我们采用拉普拉斯修正。即让所有属性的样本个数 $+1$，于是总样本数就需要 $+d$ 来确保总概率仍然为 $1$。这是额外引入的 bias

7.4 半朴素贝叶斯分类器

朴素贝叶斯的问题是假设过于强，现实不可能所有的属性都相互独立。半朴素贝叶斯弱化了朴素贝叶斯的假设。现在假设每一个属性最多只依赖一个其他属性。即独依赖估计 $(\text{One-Dependent Estimator, 简称 ODE})$，于是就有了下面的贝叶斯判定准测：

$$P(c\ |\ x) \propto P(c) \prod _{i=1}^d P(x_i\ |\ c, pa_i)$$

如何寻找依赖关系？我们从属性依赖图出发

如上图所示：

• 朴素贝叶斯算法中：假设所有属性相互独立，因此各属性之间没有连边
• SPODE 确定属性父属性算法中：假设所有属性都只依赖于一个属性（超父），我们只需要找到超父即可
• TAN 确定属性父属性算法中：我们需要计算每一个属性之间的互信息，最后得到一个以互信息为边权的完全图。最终选择最大的一些边构成一个最大带权生成树
• AODE 确定属性父属性算法中：采用集成的思想，以每一个属性作为超父属性，最后选择最优即可

7.5 贝叶斯网

构造一个关于属性之间的 DAG 图，从而进行后续类条件概率的计算。三种典型依赖关系：

同父结构	V型结构	顺序结构
在已知 $x_1$ 的情况下 $x_3,x_4$ 独立	若 $x_4$ 未知则 $x_1,x_2$ 独立，反之不独立	在已知 $x$ 的情况下 $y,z$ 独立

概率计算公式参考：超详细讲解贝叶斯网络(Bayesian network)

7.6 EM 算法

现在我们需要解决含有隐变量 $Z$ 的情况。如何在已知数据集含有隐变量的情况下计算出模型的所有参数？我们引入 EM 算法。EM 迭代型算法共两步

• E-step：首先利用观测数据 $X$ 和参数 $\Theta_t$ 得到关于隐变量的期望 $Z^t$
• M-step：接着对 $X$ 和 $Z^t$ 使用极大似然函数来估计新的最优参数 $\Theta_{t+1}$​

有两个问题：哪来的参数？什么时候迭代终止？

• 对于第一个问题：我们随机化初始得到参数 $\Theta_0$
• 对于第二个问题：相邻两次迭代结果中参数差值的范数小于阈值 $(|| \theta^{(i+1)} - \theta^{(i)}) || < \epsilon_1)$ 或隐变量条件分布期望差值的范数小于阈值 $(|| Q(\theta^{(i+1)} , \theta^{(i)})) - Q(\theta^{(i)} , \theta^{(i)}) || < \epsilon_2)$

第8章 集成学习

8.1 个体与集成

集成学习由多个不同的组件学习器组合而成。学习器不能太坏并且学习器之间需要有差异。如何产生并结合“好而不同”的个体学习器是集成学习研究的核心。集成学习示意图如下：

根据个体学习器的生成方式，目前集成学习可分为两类，代表作如下：

1. 个体学习器直接存在强依赖关系，必须串行生成的序列化方法：Boosting
2. 个体学习器间不存在强依赖关系，可以同时生成的并行化方法：Bagging 和 随机森林 (Random Forest)

8.2 Boosting

Boosting 算法族的逻辑：

1. 个体学习器之间存在强依赖关系
2. 串行生成每一个个体学习器
3. 每生成一个新的个体学习器都要调整样本分布

以 AdaBoost 算法为例，问题式逐步深入算法实现：

1. 如何计算最终集成的结果？利用加性模型 (additive model)，假定第 $i$ 个学习器的输出为 $h(x)$，第 $i$ 个学习器的权重为 $\alpha_i$，则集成输出 $H(x)$ 为：

   $$H(x) = \text{sign} \left(\sum_{i=1}^T \alpha_i h_i(x)\right)$$

2. 如何确定每一个学习器的权重 $\alpha_i$ ？我们定义 $\displaystyle \alpha_i=\frac{1}{2}\ln (\frac{1-\epsilon_i}{\epsilon_i})$

3. 如何调整样本分布？我们对样本进行赋权。学习第一个学习器时，所有的样本权重相等，后续学习时的样本权重变化规则取决于上一个学习器的分类情况。上一个分类正确的样本权重减小，上一个分类错误的样本权重增加，即：

   $$D_{i+1}(x) = \frac{D_i(x)}{Z_i} \times \begin{cases} e^{-\alpha_i}&,h_i(x)=f(x) \\ e^{\alpha_i}&,h_i(x)\ne f(x) \end{cases}$$

代表算法：AdaBoost、GBDT、XGBoost

8.3 Bagging 与 随机森林

在指定学习器个数 $T$ 的情况下，并行训练 $T$ 个相互之间没有依赖的基学习器。最著名的并行式集成学习策略是 Bagging，随机森林是其的一个扩展变种。

8.3.1 Bagging

问题式逐步深入 Bagging 算法实现：

1. 如何计算最终集成的结果？直接进行大数投票即可，注意每一个学习器都是等权重的
2. 如何选择每一个训练器的训练样本？顾名思义，就是进行 $T$ 次自助采样法
3. 如何选择基学习器？往往采用决策树 or 神经网络

8.3.2 随机森林

问题式逐步深入随机森林 (Random Forest，简称 RF) 算法实现：

1. 如何计算最终集成的结果？直接进行大数投票即可，注意每一个学习器都是等权重的
2. 为什么叫森林？每一个基学习器都是「单层」决策树
3. 随机在哪？首先每一个学习器对应的训练样本都是随机的，其次每一个基学习器的属性都是随机的 $k(k \in [1,V])$​ 个（由于基学习器是决策树，并且属性是不完整的，故这些决策树都被称为弱决策树）

8.3.3 区别与联系（补）

区别：随机森林与 Bagging 相比，多增加了一个属性随机，进而提升了不同学习器之间的差异度，进而提升了模型性能，效果如下：

联系：两者均采用自助采样法。优势在于，不仅解决了训练样本不足的问题，同时 T 个学习器的训练样本之间是有交集的，这也就可以减小测试的方差。

8.4 区别与联系（补）

区别：

• 序列化基学习器最终的集成结果往往采用加权投票
• 并行化基学习器最终的集成结果往往采用平权投票

联系：

• 序列化减小偏差。即可以增加拟合性，降低欠拟合
• 并行化减小方差。即可以减少数据扰动带来的误差

8.5 结合策略

基学习器有了，如何确定最终模型的集成输出呢？我们假设每一个基学习器对于当前样本 $x$ 的输出为 $h_i(x),i=1,2,\cdots,T$，结合以后的输出结果为 $H(x)$

8.5.1 平均法

对于数值型输出 $h_i(x) \in R$，常见的结合策略采是平均法。分为两种：

1. 简单平均法：$H(x) = \displaystyle \frac{1}{T} \sum_{i =1}^T h_i(x)$
2. 加权平均法：$H(x) = \displaystyle\sum_{i=1}^T w_i h_i(x),\quad w_i \ge 0, \sum_{i=1}^Tw_i = 1$

显然简单平均法是加权平均法的特殊。一般而言，当个体学习器性能差距较大时采用加权平均法，相近时采用简单平均法。

8.5.2 投票法

对于分类型输出 $h_i(x) = [h_i^1(x), h_i^2(x), \cdots, h_i^N(x)]$，即每一个基学习器都会输出一个 $N$ 维的标记向量，其中只有一个打上了标记。常见的结合策略是投票法。分为三种：

1. 绝对多数投票法：选择超过半数的，如果没有则拒绝投票
2. 相对多数投票法：选择票数最多的，如果有多个相同票数的则随机取一个
3. 加权投票法：每一个基学习器有一个权重，从而进行投票

8.5.3 学习法

其实就是将所有基学习器的输出作为训练数据，重新训练一个模型对输出结果进行预测。其中，基学习器称为“初级学习器”，输出映射学习器称为“次级学习器”或”元学习器” $\text{(meta-learner)}$。对于当前样本 $(x,y)$，$n$ 个基学习器的输出为 $y_1 = h_1(x),y_2 = h_2(x),\cdots,y_n = h_n(x)$，则最终输出 $H(x)$ 为：

$$H(x) = G(y_1, y_2, \cdots, y_n)$$

其中 $G$ 就是次级学习器。关于次级学习器的学习算法，大约有以下几种：

1. Stacking
2. 多响应线性回归 $\text{(Mutil-response linear regression, 简称 MLR)}$
3. 贝叶斯模型平均 $\text{(Bayes Model Averaging, 简称 BMA)}$​

经过验证，Stacking 的泛化能力往往比 BMA 更优。

8.6 多样性

8.6.1 误差-分歧分解

根据「回归」任务的推导可得下式。其中 $E$ 表示集成的泛化误差、$\overline{E}$ 表示个体学习器泛化误差的加权均值、$\overline{A}$ 表示个体学习器的加权分歧值

$$E = \overline{E} - \overline{A}$$

8.6.2 多样性度量

如何估算个体学习器的多样化程度呢？典型做法是考虑两两学习器的相似性。所有指标都是从两个学习器的分类结果展开，以两个学习器 $h_i,h_j$ 进行二分类为例，有如下预测结果列联表：

显然 $a+b+c+d=m$。基于此有以下常见的多样性度量指标：

• 不合度量
• 相关系数
• Q-统计量
• $\kappa$​-统计量

以「$\kappa$-统计量」为例进行说明。两个学习器的卡帕结果越接近1，则越相似。可以分析出：

• 串行的基学习器多样性较并行的基学习器更高
• 串行的基学习器误差较并行的基学习器也更高

8.6.3 多样性增强

为了训练出多样性大的个体学习器，我们引入随机性。介绍几种扰动策略：

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

第9章 聚类

9.1 聚类任务

典型的无监督学习方法。即将众多无标签数据进行分类。在开始介绍几类经典的聚类学习方法之前，我们先讨论聚类算法涉及到的两个基本问题：性能度量和距离计算。

9.2 性能度量

一来是进行聚类的评估，二来也可以作为聚类的优化目标。分为两种，分别是外部指标和内部指标。

9.2.1 外部指标

所谓外部指标就是已经有一个“参考模型”存在了，将当前模型与参考模型的比对结果作为指标。我们考虑两两样本的聚类结果，定义下面的变量：

显然 $a+b+c+d=m(m-1)/2$，常见的外部指标如下：

• JC 指数：$\displaystyle JC = \frac{a}{a+b+c}$
• FM 指数：$\displaystyle \sqrt{\frac{a}{a+b} \cdot \frac{a}{a+c}}$
• RI 指数：$\displaystyle \frac{2(a+d)}{m(m-1)}$

上述指数取值均在 $[0,1]$ 之间，且越大越好。

9.2.2 内部指标

所谓内部指标就是仅仅考虑当前模型的聚类结果。同样考虑两两样本的聚类结果，定义下面的变量：

常见的外部指标如下：

• DB 指数
• Dunn 指数

9.3 距离计算

有序属性：闵可夫斯基距离

无序属性：VDM 距离

9.4 原型聚类

9.4.1 k 均值算法

算法流程大体上可以归纳为三步：

1. 初始化 k 个聚类中心
2. 枚举所有样本并将其划分到欧氏距离最近的中心
3. 更新 k 个簇中心

重复上述迭代过程直到聚类中心不再发生变化，当然为了防止迭代时间过久，可以弱化迭代终止条件，比如增设：最大迭代论述或对聚类中心的变化增加一个阈值而非绝对的零变化。k 均值算法伪代码如下：

9.4.2 学习向量量化算法

9.4.3 高斯混合聚类算法

9.5 密度聚类

DBSCAN 算法

适用于簇的大小不定，距离不定的情况。大概就是多源有向bfs的过程。定义每一源为“核心对象”，每次以核心对象为起始进行bfs，将每一个符合“范围约束”的近邻点纳入当前簇，不断寻找知道所有核心对象都访问过为止。

9.6 层次聚类

AGNES 算法

适用于可选簇大小、可选簇数量的情况。

第10章 降维与度量学习

本章我们通过 k 近邻监督学习方法引入「降维」和「度量学习」的概念。

• 对于降维算法：根本原因是样本往往十分稀疏，需要我们对样本的属性进行降维，从而达到合适的密度进而可以进行基于距离的邻居选择相关算法。我们将重点讨论以下几个降维算法：MDS 多维缩放、PCA 主成分分析、等度量映射
• 对于度量学习：上述降维的根本目的是选择合适的维度，确保一定可以通过某个距离计算表达式计算得到每一个样本的 k 个邻居。而度量学习直接从目的出发，尝试直接学习样本之间的距离计算公式。我们将重点讨论以下几个度量学习算法：近邻成分分析、LMNN

10.1 k 近邻学习

k 近邻（k-Nearest Neighbor，简称 KNN）是一种监督学习方法。一句话概括就是「近朱者赤近墨者黑」，每一个测试样本的分类或回归结果取决于在某种距离度量下的最近的 k 个邻居的性质。不需要训练，可以根据检测样本实时预测，即懒惰学习。为了实现上述监督学习的效果，我们需要解决以下两个问题：

• 如何确定「距离度量」的准则？就那么几种，一个一个试即可。
• 如何定义「分类结果」的标签？分类任务是 k 个邻居中最多类别的标签，回归任务是 k 个邻居中最多类别标签的均值。

上述学习方法有什么问题呢？对于每一个测试样例，我们需要确保能够通过合适的距离度量准则选择出 k 个邻居出来，这就需要保证数据集足够大。在距离计算时，每一个属性都需要考虑，于是所需的样本空间会呈指数级别的增长，这被称为「维数灾难」。这是几乎不可能获得的数据量同时在进行矩阵运算时时间的开销也是巨大的。由此引入本章的关键内容之一：降维。

为什么能降维？我们假设学习任务仅仅是高维空间的一个低维嵌入。

10.2 多维缩放降维

「多维缩放（MDS）降维算法」的原则：对于任意的两个样本，降维后两个样本之间的距离保持不变。

基于此思想，可以得到以下降维流程：我们定义 $b_{ij}$ 为降维后任意两个样本之间的内积，$dist_{ij}$ 表示任意两个样本的原始距离，$Z \in R^{d'\times m},d' \le d$ 为降维后数据集的属性值矩阵。

内积计算：

新属性值计算：特征值分解法。其中 $B = V \Lambda V^T$

10.3 主成分分析降维

「主成分分析（Principal Component Analysis，简称 PCA）降维算法」的两个原则：

• 样本到超平面的距离都尽可能近
• 样本在超平面的投影都尽可能分开

基于此思想可以得到 PCA 的算法流程：

▶

3 个样本 2 个特征降维到 1 个特征的算例

假设我们有一个简单的数据集 $D$，包括以下三个样本点：

$$x_1 = \begin{pmatrix} 2 \\ 3 \end{pmatrix}, \quad x_2 = \begin{pmatrix} 3 \\ 4 \end{pmatrix}, \quad x_3 = \begin{pmatrix} 4 \\ 5 \end{pmatrix}$$

我们希望将这些样本从二维空间降维到一维空间（即 $d' = 1$ ）。

步骤 1: 样本中心化

首先计算样本的均值向量：

$$\mu = \frac{1}{3} (x_1 + x_2 + x_3) = \frac{1}{3} \begin{pmatrix} 2 \\ 3 \end{pmatrix} + \frac{1}{3} \begin{pmatrix} 3 \\ 4 \end{pmatrix} + \frac{1}{3} \begin{pmatrix} 4 \\ 5 \end{pmatrix} = \begin{pmatrix} 3 \\ 4 \end{pmatrix}$$

然后对所有样本进行中心化：

$$\tilde{x}_1 = x_1 - \mu = \begin{pmatrix} 2 \\ 3 \end{pmatrix} - \begin{pmatrix} 3 \\ 4 \end{pmatrix} = \begin{pmatrix} -1 \\ -1 \end{pmatrix}$$

$$\tilde{x}_2 = x_2 - \mu = \begin{pmatrix} 3 \\ 4 \end{pmatrix} - \begin{pmatrix} 3 \\ 4 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$$

$$\tilde{x}_3 = x_3 - \mu = \begin{pmatrix} 4 \\ 5 \end{pmatrix} - \begin{pmatrix} 3 \\ 4 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$$

步骤 2: 计算协方差矩阵

样本的协方差矩阵为：

$$\begin{aligned}XX^T &= \frac{1}{m} \sum_{i=1}^m \tilde{x}_i \tilde{x}_i^T \\&= \frac{1}{3} \left( \begin{pmatrix} -1 \\ -1 \end{pmatrix} \begin{pmatrix} -1 & -1 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \end{pmatrix} \begin{pmatrix} 0 & 0 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \end{pmatrix} \right)\\&= \frac{1}{3} \left( \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} + \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix} + \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \right) \\&= \frac{1}{3} \begin{pmatrix} 2 & 2 \\ 2 & 2 \end{pmatrix} \\&= \begin{pmatrix} \frac{2}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{2}{3} \end{pmatrix}\end{aligned}$$

步骤 3: 对协方差矩阵进行特征值分解

协方差矩阵的特征值分解：

$$\begin{pmatrix} \frac{2}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{2}{3} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} \frac{4}{3} & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}$$

特征值为 $\lambda_1 = \frac{4}{3}$ 和 $\lambda_2 = 0$，对应的特征向量分别为：

$$w_1 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \quad w_2 = \begin{pmatrix} -1 \\ 1 \end{pmatrix}$$

步骤 4: 取最大的 $d'$ 个特征值对应的特征向量

我们选择最大的特征值对应的特征向量 $w_1 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$ 作为最终的投影矩阵。

10.4 核化线性降维

「核化线性降维算法」的原则：pass

10.5 流形学习降维

假定数据满足流形结构。

10.5.1 等度量映射

流形样本中，直接计算两个样本之间的欧式距离是无效的。我们引入「等度量映射」理念。根本算法逻辑是：利用最短路算法计算任意两个样本之间的「测地线距离」得到 $dist_{ij}$，接着套用上述 10.2 中的 MDS 算法即可进行降维得到最终的属性值矩阵 $Z \in R^{d'\times m},d' \le d$

10.5.2 局部线性嵌入

pass

10.6 度量学习

降维的本质是寻找一种合适的距离度量方法，与其降维为什么不直接学习一种距离计算方法呢？我们引入「度量学习」的理念。

为了“有参可学”，我们需要定义距离计算表达式中的超参，我们定义如下「马氏距离」：

为什么用所谓的马氏距离呢？欧氏距离不行吗？我们有以下结论：

• 欧式距离具有旋转不变性和平移不变性，在低维和属性直接相互独立时是最佳实践。但是当属性之间有相关性并且尺度相差较大时，直接用欧式距离计算会丢失重要的特征之间的信息；
• 马氏距离具有尺度不变性，在高维和属性之间有关系且尺度不同时是最佳实践。缺点在于需要计算协方差矩阵导致计算量远大于欧氏距离的计算量。

下面介绍两种度量学习算法来学习上述 M 矩阵，也就是数据集的「协方差矩阵的逆」中的参数。准确的说是学习一个矩阵来近似代替协方差矩阵的逆矩阵。

10.6.1 近邻成分分析

近邻成分分析 $\text{(Neighborhood Component Analysis, 简称 NCA)}$，目标函数是：最小化所有数据点的对数似然函数的负值。

10.6.2 LMNN

大间隔最近邻 $\text{(Large Margin Nearest Neighbor, 简称 LMNN)}$，目标函数是：最小化同一个类别中最近邻点的距离，同时最大化不同类别中最近邻点的距离。

paper: Distance Metric Learning for Large Margin Nearest Neighbor Classification

explain: 【LMNN】浅析"从距离测量到基于Margin的邻近分类问题"

第13章 半监督学习

半监督学习的根本目标：同时利用有标记和未标记样本的数据进行学习，提升模型泛化能力。主要分为三种：

1. 主动学习
2. 纯半监督学习
3. 直推学习

13.1 未标记样本

对未标记数据的分布进行假设，两种假设：

1. 簇状分布
2. 流形分布

13.2 生成式方法

分别介绍「生成式方法」和「判别式方法」及其区别和联系。

生成式方法：核心思想就是用联合分布 $p(x,y)$ 进行建模，即对特征分布 $p(x)$ 进行建模，十分关心数据是怎么来（生成）的。生成式方法需要对数据的分布进行合理的假设，这通常需要计算类先验概率 $p(y)$ 和特征条件概率 $p(x\ |\ y)$，之后再在所有假设之上进行利用贝叶斯定理计算后验概率 $p(y\ |\ x)$。典型的例子如：

• 朴素贝叶斯
• 高斯混合聚类
• 马尔科夫模型

判别式方法：核心思想就是用条件分布 $p(y\ |\ x)$ 进行建模，不对特征分布 $p(x)$ 进行建模，完全不管数据是怎么来（生成）的。即直接学一个模型 $p(y\ |\ x)$ 来对后续的输入进行预测。不需要对数据分布进行过多的假设。典型的例子如：

• 线性回归
• 逻辑回归
• 决策树
• 神经网络
• 支持向量机
• 条件随机场

自监督训练（补）

根本思想就是利用有标记数据进行模型训练，然后对未标记数据进行预测，选择置信度较高的一些样本加入训练集重新训练模型，不断迭代进行直到最终训练出来一个利用大量未标记数据训练出来的模型。

如何定义置信度高？我们利用信息熵的概念，即对于每一个测试样本都有一个预测向量，信息熵越大表明模型对其的预测结果越模糊，因此置信度高正比于信息熵小，将信息熵较小的测试样本打上「伪标记」加入训练集。

13.3 半监督 SVM

以经典 S3VM 中的经典算法 TSVM 为例。给出优化函数、算法图例、算法伪代码：

13.4 图半监督学习

同样解决分类问题，以「迭代式标记传播算法」为例。

二分类，可以直接求出闭式解。

算法逻辑。每一个样本对应图中的一个结点，两个结点会连上一个边，边权正比于两结点样本的相似性。最终根据图中已知的某些结点进行传播标记即可。与基于密度的聚类算法类似，区别在于此处不同的簇 cluster 可能会对应同一个类别 class。

如何进行连边？不会计算每一个样本的所有近邻，一般采用局部近邻选择连边的点，可以 k 近邻，也可以范围近邻。

优化函数。定义图矩阵的能量损失函数为图中每一个结点与所有结点的能量损失和，目标就是最小化能量损失和：

多分类，无法直接求出闭式解，只能进行迭代式计算。

新增变量。我们定义标记矩阵 F，其形状为 $(l+u) \times d$，学习该矩阵对应的值，最终每一个未标记样本 $x_i$ 就是 $\arg \max F_i$：

13.5 基于分歧的方法

多学习器协同训练。

第14章 概率图模型

为了分析变量之间的关系，我们建立概率图模型。按照图中边的性质可将概率图模型分为两类：

• 有向图模型，也称贝叶斯网
• 无向图模型，也称马尔可夫网

14.1 隐马尔可夫模型

隐马尔可夫模型 $\text{(Hidden Markov Model, 简称 HMM)}$ 是结构最简单的动态贝叶斯网。是为了研究变量之间的关系而存在的，因此是生成式方法。

需要解决三个问题：

1. 如何评估建立的网络模型和实际观测数据的匹配程度？
2. 如果上面第一个问题中匹配程度不好，如何调整模型参数来提升模型和实际观测数据的匹配程度呢？
3. 如何根据实际的观测数据利用网络推断出有价值的隐藏状态？

14.2 马尔科夫随机场

马尔科夫随机场 $\text{(Markov Random Field, 简称 MRF)}$ 是典型的马尔科夫网。同样是为了研究变量之间的关系而存在的，因此也是生成式方法。

联合概率计算逻辑按照势函数和团展开。其中团可以理解为完全子图；极大团就是结点最多的完全子图，即在当前的完全子图中继续添加子图之外的点就无法构成新的完全子图；势函数就是一个关于团的函数。

14.3 条件随机场

判别式方法。

14.4 学习和推断

精确推断。

14.5 近似推断

近似推断。降低计算时间开销。

• 采样法：蒙特卡洛采样法
• 变分推断：考虑近似分布

考试大纲

• 单选 10 * 3'：单选直接一个单刀咆哮。注意审题、注意一些绝对性的语句；
• 简答 4 * 5'：想拿满分就需要写出理论对应的具体公式；
• 计算 3 * 10'：老老实实写每一个计算过程，不要跳步骤；
• 论述 2 * 10'：没考过，大约是简答题加强版。注意逻辑一定要清晰。