03 机器学习

01 机器学习基本概念

目标：

从原始数据中提取特征
学习映射函数 f
通过映射函数 f 将原始数据映射到语义任务空间
- 即寻找数据和任务目标之间的关系

监督学习

监督学习：

标注数据：学习过程的输入，由明确标记了正确输出类别或值的数据点组成
1. 通过提供“真实值”来决定“学什么”
学习模型：从标注数据中学习模式的算法或结构
1. 定义了机器将如何获得自我学习能力，即“如何学”
损失函数：量化了模型预测与真实标签之间的差异
1. 通过提供可衡量的学习结果指标来回答“学到否”的问题

在训练过程中，映射函数 f（学习模型）的主要目标是最小化整个训练数据集上的累积“损失”。 这可以表示为：

m i n \sum_{i = 1}^{n} ​ L o s s (f (x_{i} ​), y_{i} ​)

训练数据与测试数据：

经验风险 empirical risk 与期望风险 expected risk

经验风险是训练集中数据产生的损失
期望风险是当测试集中存在无穷多数据时产生的损失

“过学习 (over-fitting)”与“欠学习 (under-fitting)”

Over-fitting：经验风险小而期望风险大
Under-fitting：经验风险大且期望风险大

结构风险最小化 structural risk minimization

经验风险最小化：仅反映了局部数据
期望风险最小化：无法得到全量数据
为了防止过拟合，在经验风险上加上表示模型复杂度的正则化项 (regulatizer) 或惩罚项 (penalty term )
在最小化经验风险与降低模型复杂度之间寻找平衡

min_{f \in Φ} \frac{1}{n} \sum_{i = 1}^{n} L o s s (y_{i}, f (x_{i})) + λ J (f)

监督学习方法

判别方法 discriminative approach
- 判别方法直接学习判别函数 $f (X)$ 或者条件概率分布 $P (Y | X)$ 作为预测的模型，即判别模型
- 判别模型关心在给定输入数据下，预测该数据的输出是什么
- 不考虑样本的产生模型，直接研究预测模型
- 典型判别模型包括回归模型、神经网络、支持向量机和 Ada boosting 等
生成方法 generative approach
- 生成模型从数据中学习联合概率分布 $P (X, Y)$ (通过似然概率 $P (X | Y)$ 和类概率 $P (Y)$ 的乘积来求取)
$P (Y | X) = \frac{P (X, Y)}{P (X)} 或者 P (Y | X) = \frac{P (X | Y) \times P (Y)}{P (X)}$
- 典型方法为贝叶斯方法、隐马尔可夫链
- 联合分布概率 $P (X, Y)$ 或似然概率 $P (X | Y)$ 求取很困难

02 回归分析

分析不同变量之间存在关系的研究叫回归分析，刻画不同变量之间关系的模型被称为回归模型

一元线性回归

回归模型参数求取: $y_{i} = a x_{i} + b (1 \leq i \leq n)$

记在当前参数下第 $i$ 个训练样本 $x_{i}$ 的预测值为 ${\hat{y}}_{i}$
$x_{i}$ 的标注值（实际值） $y_{i}$ 与预测值 ${\hat{y}}_{i}$ 之差记为 $(y_{i} - {\hat{y}}_{i})^{2}$
训练集中 $n$ 个样本所产生误差总和为: $L (a, b) = \sum_{i = 1}^{n} (y_{i} - a \times x_{i} - b)^{2}$

目标: 寻找一组 $a$ 和 $b$ ，使得误差总和 $L (a, b)$ 值最小。在线性回归中，解决如此目标的方法叫最小二乘法

一般而言，要使函数具有最小值，可对 $L (a, b)$ 参数 $a$ 和 $b$ 分别求导，令其导数值为零，再求取参数 $a$ 和 $b$ 的取值

多元线性回归

多维数据特征中线性回归的问题定义如下：假设总共有 $m$ 个训练数据 ${(x_{i}, y_{i})}_{i = 1}^{m}$ , 其中 $x_{i} = [x_{i, 1}, x_{i, 2}, . . ., x_{i, D}] \in R^{D}$ , $D$ 为数据特征的维度，线性回归就是要找到一组参数 $a = [a_{0}, a_{1}, . . ., a_{D}]$ , 使得线性函数：

f (x_{i}) = a_{0} + \sum_{j = 1}^{D} a_{j} x_{i, j} = a_{0} + a^{T} x_{i}

最小化均方误差函数:

J_{m} = \frac{1}{m} \sum_{i = 1}^{m} {(y_{i} - f (x_{i}))}^{2}

为了方便，使用矩阵来表示所有的训练数据和数据标签。

X = [x_{1}, \dots, x_{m}], y = [y_{1}, \dots, y_{m}]

其中每一个数据 $x_{i}$ 会扩展一个维度，其值为 1，对应参数 $a_{0}$

均方误差函数

均方误差函数可以表示为:

J_{m} (a) = (y - X^{T} a)^{T} (y - X^{T} a)

均方误差函数 $J_{n} (a)$ 对所有参数 $a$ 求导可得:

\nabla J (a) = - 2 X (y - X^{T} a)

因为均方误差函数 $J_{n} (a)$ 是一个二次的凸函数，所以函数只存在一个极小值点，也同样是最小值点，所以令 $\nabla J (a) = 0$ 可得

X X^{T} a = X y

a = {(X X^{T})}^{- 1} X y

逻辑斯蒂回归/对数几率回归

线性回归一个明显的问题是对离群点非常敏感，导致模型建模不稳定，使结果有偏

逻辑斯蒂回归 (logistic regression) 就是在回归模型中引入 sigmoid 函数的一种非线性回归模型。Logistic 回归模型可如下表示：

y = \frac{1}{1 + e^{- z}} = \frac{1}{1 + e^{- (w^{T} x + b)}}, 其中 y \in (0, 1), z = w^{T} x + b

这里 $\frac{1}{1 + e^{- z}}$ 是 sigmoid 函数、 $x \in R^{d}$ 是输入数据、 $w \in R^{d}$ 和 $b \in R$ 是回归函数的参数。

Sigmoid 函数性质

函数是单调递增的，其值域为 (0,1), 可用作概率值
对输入 z 没有取值范围限制，但当 z 大于 (小于) 一定数值后，函数输出无限逼近 1 (0), 当 z 等于 0 时，函数输出为 0.5
z 取值在 0 附近时，函数输出值变化比较大，且是非线性变化，但 z 取值很大或很小时，函数输出值几乎不变

逻辑斯蒂回归函数的输出具有概率意义，更多用于二分类问题（y=1 表示输入数据𝒙属于正例，y=0 表示输入数据𝒙属于负例）

y = \frac{1}{1 + e^{- (w^{T} x + b)}}

可用来计算输入数据 $x$ 属于正例概率，这里 $y$ 理解为输入数据 $x$ 为正例的概率，即 $p (y = 1 | x)$ ， $1 - y$ 理解为输入数据 $x$ 为负例的概率，即 $p (y = 0 | x)$

logistic 回归本质上是一个线性模型

我们现在对比值 $\frac{p}{1 - p}$ 取对数 (即 $\log (\frac{p}{1 - p})$ ) 来表示输入数据 $x$ 属于正例概率。 $\frac{p}{1 - p}$ 被称为几率 (odds)，反映了输入数据 $x$ 作为正例的相对可能性。 $\frac{p}{1 - p}$ 的对数几率 (log odds) 或 logit 函数可表示为 $\log (\frac{p}{1 - p})$

显然，可以得到 $p (y = 1 | x) = h_{θ} (x) = \frac{1}{1 + e^{- (w^{T} x + b)}}$ 和 $p (y = 0 | x) = 1 - h_{θ} (x) = \frac{e^{- (w^{T} x + b)}}{1 + e^{- (w^{T} x + b)}}$ 。 $θ$ 表示模型参数 $(θ = {w, b})$ 。于是有：

logit (p (y = 1 | x)) = \log (\frac{p (y = 1 | x)}{p (y = 0 | x)}) = \log (\frac{p}{1 - p}) = w^{T} x + b

如果输入数据 $x$ 属于正例的概率大于其属于负例的概率，即 $p (y = 1 | x) > 0.5$ ，则输入数据 $x$ 可被判断属于正例。这一结果等价于 $\frac{p (y = 1 | x)}{p (y = 0 | x)} > 1$ ，即 $\log (\frac{p (y = 1 | x)}{p (y = 0 | x)}) > \log 1 = 0$ ，也就是 $w^{T} x + b > 0$ 成立
从这里可以看出，logistic 回归本质上是一个线性模型。在预测时，可以计算线性函数 $w^{T} x + b$ 取值是否大于 0 来判断输入数据 $x$ 的类别归属

03 决策树

非叶子节点：对分类目标某一属性的判断
叶子节点：分类结果

属性划分方法：

信息增益
增益率
基尼指数

信息增益

信息熵（entropy）是度量样本集合纯度最常用的一种指标

假设有 $K$ 个信息 (类别), 其组成了集合样本 $D$ , 记第 $k$ 个信息 (类别) 发生的概率为 $p_{k} (1 \leq k \leq K)$ 。如下定义这 $K$ 个信息的信息熵：

E n t (D) = - \sum_{k = 1}^{K} p_{k} \log_{2} p_{k}

$E n t (D)$ 值越小，表示 $D$ 包含的信息越确定，也称 $D$ 的纯度越高
所有 $p_{k}$ 累加起来的和为 1
约定：若 $p_{k} = 0$ , 则 $p_{k} \log_{2} p_{k} = 0$

构建决策树时划分属性的顺序选择是重要的。性能好的决策树随着划分不断进行，决策树分支结点样本集的“纯度”会越来越高，即其所包含样本尽可能属于相同类别。

信息增益的计算：

G a i n (D, A) = E n t (D) - \sum_{i = 1}^{n} \frac{| D_{i} |}{| D |} E n t (D_{i})

通过比较样本的属性信息增益的高低来选择最佳属性（信息增益最大的属性）对原样本集进行划分，得到最大的“纯度”
如果划分后的不同子样本集都只存在同类样本 (类别标签一致)，那么停止划分

Example

Pasted image 20250606125647.png|350

信息增益对可取值数目较多的属性有所偏好

存在的问题：若把“编号”也作为一个候选划分属性，则其信息增益一般远大于其他属性。显然，这样的决策树不具有泛化能力，无法对新样本进行有效预测

因为一个编号对应一个结果，决策树就会直接学习到编号和标签之间的结论，但这个是无意义的

增益率和基尼系数

Info 和 Gain-ratio（增益率）计算公式如下：

i n f o = - \sum_{i = 1}^{n} \frac{| D_{i} |}{| D |} \log_{2} \frac{| D_{i} |}{| D |}

G a i n - r a t i o = G a i n (D, A) / i n f o

增益率准则对可取数目较少的属性有所偏好

一个启发式：

先从候选划分属性中找出信息增益高于平均水平的属性
再从中选取增益率最高的

更简的度量指标是如下的 Gini 指数（基尼指数）：

G i n i (D) = 1 - \sum_{k = 1}^{K} p_{k}^{2}

相对于信息熵的计算 $E (D) = - \sum_{k = 1}^{K} p_{k} \log_{2} p_{k}$ ，不用计算对数 log，计算更为简易

连续属性离散化（二分法）

第一步：假定连续属性 $a$ 在样本集 $D$ 上出现 $n$ 个不同的取值，从小到大排列，记为 $a^{1}, a^{2}, . . . A^{n}$ , 基于划分点 $t$ , 可将 $D$ 分为子集 $D_{t}^{-}$ 和 $D_{t}^{+}$ , 其中 $D_{t}^{-}$ 包含那些在属性 $a$ 上取值不大于 $t$ 的样本， $D_{t}^{+}$ 包含那些在属性 $a$ 上取值大于 $t$ 的样本。考虑包含 $n - 1$ 个元素的候选划分点集合

T_{a} = {\frac{a^{i} + a^{i + 1}}{2} ∣ 1 \leq i \leq n - 1}

即把区间 $[a^{i}, a^{i + 1})$ 的中位点 $\frac{a^{i} + a^{i + 1}}{2}$ 作为候选划分点

第二步：采用离散属性值方法，考察这些划分点，选取最优的划分点进行样本集合的划分

\begin{aligned} Gain (D, a) & = max_{t \in T_{a}} Gain (D, a, t) \\ = max_{t \in T_{a}} Ent (D) - \sum_{λ \in {-, +}} \frac{| D_{t}^{λ} |}{| D |} Ent (D_{t}^{λ}) \end{aligned}

其中 Gain $(D, a, t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益，于是，就可选择使 Gain $(D, a, t)$ 最大化的划分点

剪枝处理

对付“过拟合”：避免因决策分支过多，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合

留出法：预留一部分数据用作“验证集”以进行性能评估

预剪枝
- 对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点记为叶结点，其类别标记为训练样例数最多的类别
- 缺点：欠拟合风险
后剪枝
- 先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点
- 缺点：训练开销大

多变量决策

决策边界：
- 单变量决策：轴平行
- 多变量决策： $w^{T} x > t$
  - 非线性函数 (SVM)
单变量 V.S. 多变量
- 复杂度
- 可解释性

背景的 + 和 − 是两类样本
红线表示理想的决策边界（可能是非线性的，例如 SVM 拟合结果）
黑色阶梯状线 是传统决策树的单变量分割方式（横向或纵向切）
多变量决策的边界可能是斜的、更光滑（图中未直接画出）

04 线性区别分析 LDA

线性判别分析 (linear discriminant analysis， LDA)
也称为 Fisher 线性判别分析（fisher'sdiscriminant analysis，FDA) [Fisher 1936]

在低维空间中同一类别样本尽可能靠近，不同类别样本尽可能彼此远离

4.1 符号定义

样本集为 $D = (x ₁, y ₁), (x ₂, y ₂), (x ₃, y ₃), . . ., (x ₙ, y ₙ)$
样本 $x_{i} \in ℝ^{d}$ 的类别标签为 $y_{i}$
$y_{i}$ 的取值范围是 $C ₁, C ₂, . . ., C_{K}$ ，即一共有 K 类样本

定义 X 为所有样本构成集合、 $N_{i}$ 为第 i 个类别所包含样本个数、 $X_{i}$ 为第 i 类样本的集合、m 为所有样本的均值向量、 $m_{i}$ 为第 i 类样本的均值向量。 $Σ_{i}$ 为第 i 类样本的协方差矩阵，其定义为：

Σ_{i} = \sum_{x \in X_{i}} (x - m_{i}) (x - m_{i})^{T}

Σ_{i} = \sum_{x \in X_{i}} (\begin{matrix} (x_{1} - m_{i 1})^{2} & (x_{1} - m_{i 1}) (x_{2} - m_{i 2}) & \dots & (x_{1} - m_{i 1}) (x_{d} - m_{i d}) \\ (x_{2} - m_{i 2}) (x_{1} - m_{i 1}) & (x_{2} - m_{i 2})^{2} & \dots & (x_{2} - m_{i 2}) (x_{d} - m_{i d}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ (x_{d} - m_{i d}) (x_{1} - m_{i 1}) & (x_{d} - m_{i d}) (x_{2} - m_{i 2}) & \dots & (x_{d} - m_{i d})^{2} \end{matrix})

协方差矩阵，衡量的是原始 $x = (x_{1}, x_{2}, . . ., x_{d})$ 各个维度 $x_{1}, . . ., x_{d}$ 之间的关联性

4.2 二分类问题

即 K = 2 的情况

在二分类问题中，训练样本归属于 $C_{1}$ 或 $C_{2}$ 两个类别，并通过如下的线性函数投影到一维空间上：

y (x) = w^{T} x (w \in R^{d})

通过一个 d 维的参数，将原始数据 x 降到一维空间

投影之后类别 $C_{1}$ 的协方差矩阵 $s_{1}$ 为：

s_{1} = \sum_{x \in C_{1}} {(w^{T} x - w^{T} m_{1})}^{2} = w^{T} \sum_{x \in C_{1}} [(x - m_{1}) (x - m_{1})^{T}] w

为了使得归属于同一类别的样本数据在投影后的空间中尽可能靠近，需要最小化 s 1+s 2 取值（类内方差小）
为了使得归属于不同类别的样本数据在投影后空间中尽可能彼此远离，需要最大化过 $∥ m_{2} - m_{1} ∥_{2}^{2}$ 取值 (类间间隔大)

同时考虑上面两点，就得到了需要最大化的目标 $J (w)$ , 定义如下：

J (w) = \frac{∥ m_{2} - m_{1} ∥_{2}^{2}}{s_{1} + s_{2}}

J (w) = \frac{{‖ w^{T} (m_{2} - m_{1}) ‖}^{2}}{w^{T} Σ_{1} w + w^{T} Σ_{2} w} = \frac{w^{T} (m_{2} - m_{1}) (m_{2} - m_{1})^{T} w}{w^{T} (Σ_{1} + Σ_{2}) w} = \frac{w^{T} S_{b} w}{w^{T} S_{w} w}

$S_{b}$ 称为类间散度矩阵 (between-class scatter matrix)，衡量两个类别均值点之间的“分离”程度，可定义如下：

S_{b} = (m_{2} - m_{1}) (m_{2} - m_{1})^{T}

$S_{w}$ 则称为类内散度矩阵 (within-class scatter matrix)，衡量每个类别中数据点的“分离”程度，可定义如下：

S_{w} = Σ_{1} + Σ_{2}

矩阵求导

向量化矩阵：按列将矩阵表示为向量，展开

如何求解

J (w)

？

由于 $J (w)$ 的分子和分母都是关于 $w$ 的二项式，因此最后的解只与 $w$ 的方向有关，与 $w$ 的长度无关，因此可令分母 $w^{T} S_{w} w = 1$ ，然后用拉格朗日乘子法来求解这个问题。

对应拉格朗日函数为:

L (w) = w^{T} S_{b} w - λ (w^{T} S_{w} w - 1)

2 S_{b} w = 2 λ S_{w} w \Rightarrow S_{w}^{- 1} S_{b} w = λ w

对 $w$ 求偏导并使其求导结果为零，可得 $S_{w}^{- 1} S_{b} w = λ w$ 。由此可见， $λ$ 和 $w$ 分别是 $S_{w}^{- 1} S_{b}$ 的特征根和特征向量， $S_{w}^{- 1} S_{b} w = λ w$ 也被称为 Fisher 线性判别（Fisher linear discrimination）。
因为 $S_{b} w = (m_{2} - m_{1}) (m_{2} - m_{1})^{T} w$ ，其中 $(m_{2} - m_{1})^{T} w$ 是个实数，不妨令 $(m_{2} - m_{1})^{T} w = λ_{w}$ ，则:

S_{w}^{- 1} S_{b} w = S_{w}^{- 1} (m_{2} - m_{1}) \times λ_{w} = λ w

由于对 $w$ 的放大和缩小操作不影响结果，因此可约去上式中的未知数 $λ$ 和 $λ_{w}$ ，得到: $w = S_{w}^{- 1} (m_{2} - m_{1})$
$w \propto S_{w}^{- 1} (m_{2} - m_{1})$

4.3 多分类问题

考试不作要求

假设 n 个原始高维 (d 维) 数据所构成的类别种类为 K、每个原始数据被投影映射到低维空间中的维度为 r
令投影矩阵 $W = (w_{1}, w_{2}, . . ., w_{r})$ ，可知 W 是一个 $d \times r$ 矩阵

$W^{T} m_{i}$ 为第 i 类样本数据中心在低维空间的投影结果
$W^{T} Σ_{i} W$ 为第 i 类样本数据协方差在低维空间的投影结果

类内散度矩阵 $S_{W}$ 重新定义如下：

S_{W} = Σ_{i = 1}^{K} Σ_{i}

其中 $Σ_{i} = Σ_{x \in c l a s s_{i}} (x - m_{i}) (x - m_{i})^{T}$
在上式中， $m_{i}$ 是第 i 个类别中所包含样本数据的均值

类间散度矩阵 $S_{b}$ 重新定义如下：

S_{b} = \sum_{i = 1}^{K} \frac{N_{i}}{N} (m_{i} - m) (m_{i} - m)^{T}

“类内方差小、类间间隔大”

Quote

逻辑上理解，每一个 $1 \times d$ 的参数向量 $w$ 都将 $d \times 1$ 的向量映射到了一个维度上，所以 r 个参数向量能够将 $d \times 1$ 的向量映射到一个 r 维度上的空间

如何求解

J (W)

将多类 LDA 映射投影方向的优化目标 J (W) 改为:

J (W) = \frac{\prod_{d i a g} W^{T} S_{b} W}{\prod_{d i a g} W^{T} S_{w} W}

其中， $\prod_{d i a g} A$ 为矩阵 $A$ 主对角元素的乘积。
继续对 J (W) 进行变形:

J (W) = \frac{\prod_{d i a g} W^{T} S_{b} W}{\prod_{d i a g} W^{T} S_{w} W} = \frac{\prod_{i = 1}^{r} w_{i}^{T} S_{b} w_{i}}{\prod_{i = 1}^{r} w_{i}^{T} S_{w} w_{i}} = \prod_{i = 1}^{r} \frac{w_{i}^{T} S_{b} w_{i}}{w_{i}^{T} S_{w} w_{i}}

显然需要使乘积式子中每个 $\frac{w_{i}^{T} S_{b} w_{i}}{w_{i}^{T} S_{w} w_{i}}$ 取值最大，这就是二分类问题的求解目标，即每一个 $w_{i}$ 都是 $S_{w}^{- 1} S_{b} W = λ W$ 的一个解。

4.4 降维步骤

计算数据样本集中每个类别样本的均值
计算类内散度矩阵 $S_{w}$ 和类间散度矩阵 $S_{b}$
根据 $S_{w}^{- 1} S_{b} W = λ W$ 来求解 $S_{w}^{- 1} S_{b}$ 所对应前 $r$ 个最大特征值所对应特征向量 $(w_{1}, w_{2}, . . ., w_{r})$ ，构成矩阵 $W$
通过矩阵 $W$ 将每个样本映射到低维空间，实现特征降维

05 Ada Boosting

考试不作要求

核心思想：对于一个复杂的分类任务，可以将其分解为若干子任务，然后将若干子任务完成方法综合，最终完成该复杂任务

5.1 计算学习理论

可计算：什么任务是可以计算的？图灵可停机
可学习：什么任务是可以被学习的、从而被学习模型来完成？
- 图片/人脸识别
- 文本主题分类

概率近似正确 (probably approximately correct, PAC)

如果得到完成该任务的若干“弱模型”，是否可以将这些弱模型组合起来，形成一个“强模型”，该“强模型” 产生误差很小呢？这就是概率近似正确（PAC）要回答的问题

5.2 思路描述

核心问题：

在每个弱分类器学习过程中，如何改变训练数据的权重：提高在上一轮中分类错误样本的权重
如何将一系列弱分类器组合成强分类器：
- 通过加权多数表决方法来提高分类误差小的弱分类器的权重让其在最终分类中起到更大作用
- 同时减少分类误差大的弱分类器的权重，让其在最终分类中仅起到较小作用

和投票集成思路比较像

给定包含 N 个标注数据的训练集合Γ， $Γ = (x ₁, y ₁), \dots, (x_{N}, y_{N})$ $x ᵢ (1 \leq i \leq N) \in X \subseteq R^{n} ， y ᵢ \in Y = {- 1, 1}$

初始化每个训练样本的权重 $D_{1} = (w_{11}, \dots, w_{1 i}, \dots, w_{1 N}), 其中 w_{1 i} = \frac{1}{N} (1 \leq i \leq N)$
第 m 个弱分类器的训练：对 $m = 1, 2, \dots, M$
1. 使用具有分布权重 $D_{m}$ 的训练数据来学习得到第 $m$ 个基分类器（弱分类器） $G_{m}$ ：
$G_{m} (x) : X \to {- 1, 1}$
1. 计算 $G_{m} (x)$ 在训练数据集上的分类误差
$e r r_{m} = \sum_{i = 1}^{N} w_{m, i} I (G_{m} (x_{i}) \neq y_{i})$ 这里：如果 $G_{m} (x_{i}) \neq y_{i}$ ， $I (\cdot) = 1$ ；否则为 0
3) 计算弱分类器 $G_{m} (x)$ 的权重：
$$\alpha_m = \frac{1}{2} \ln \frac{1 - err_m}{err_m}$$
权重 $α_{m}$ 随 $e r r_{m}$ 减少而增大，错误率越小的弱分类器会赋予更大的权重
4) 更新训练样本数据的分布权重： $D_{m + 1} = (w_{m + 1, 1}, \dots, w_{m + 1, i}, \dots, w_{m + 1, N})$ ， $w_{m + 1, i} = \frac{w_{m, i}}{Z_{m}} e^{- α_{m} y_{i} G_{m} (x_{i})}$ ，其中 $Z_{m}$ 是归一化因子以使得 $D_{m + 1}$ 为概率分布， $Z_{m} = \sum_{i = 1}^{N} w_{m, i} e^{- α_{m} y_{i} G_{m} (x_{i})}$ $w_{m + 1, i} = {\begin{cases} \frac{w_{m, i}}{Z_{m}} e^{- α_{m}}, & G_{m} (x_{i}) = y_{i} \\ \frac{w_{m, i}}{Z_{m}} e^{α_{m}}, & G_{m} (x_{i}) \neq y_{i} \end{cases}$ 也就是说，在开始训练第 m+1 个弱分类器 $G_{m + 1} (x)$ 之前，会对训练数据集中的数据权重进行调整，被错误分类的样本会被'重点关注'
以线性加权形式来组合弱分类器 $f (x)$ : 弱分类器构造强分类器 $f (x) = \sum_{i = 1}^{M} α_{m} G_{m} (x)$ 得到强分类器 $G (x)$ $G (x) = sign (f (x)) = sign (\sum_{i = 1}^{M} α_{m} G_{m} (x))$

Example

Pasted image 20250523144554.png|400
根据表 4.8 所给出的数据，要构造若干个弱分类器，然后将这些弱分类器组合为一个强分类器，完成表 4.8 所示数据的分类任务

这里定义每个弱分类器 $G$ 为一种分段函数，由一个阈值 $ε$ 构成，形式如下：

G (x_{i}) = {\begin{matrix} - 1 & x_{i} < ε \\ 1 & x_{i} > ε \end{matrix} 或 G (x_{i}) = {\begin{matrix} 1 & x_{i} < ε \\ - 1 & x_{i} > ε \end{matrix}

当然，在实际中，可根据需要使用其他的弱分类器

(1) 样本权重初始化

\begin{aligned} D_{1} = (\begin{array}{c} w_{1, 1}, . . ., w_{1, i}, . . ., w_{1, 10} \end{array}), 其中 w_{1, i} = \frac{1}{10} (1 \leq i \leq 10) \end{aligned}

下面用图来辅助说明算法流程。图中圆圈所代表数据点标签为-1、五角星所代表数据点标签为 1，每个形状的颜色深浅代表这些数据被当前所学习得到 (组合) 分类器给出标签预测值大小，颜色越深表示越接近标签值-1、颜色越浅表示越接近标签值 1。
Pasted image 20250523144751.png|450

(2) 分别训练 M 个基分类器 (弱分类器)

对 m = 1

使用具有分布权重 $D_{1}$ 的训练数据来学习得到第 m=1 个基分类器 $G_{1}$ 。不难看出，当阈值ε=6 时，基分类器 $G_{1}$ 具有最小错误率。 $G_{1}$ 分类器如下表示：
- $G_{1} (x_{i}) =$ ${\begin{cases} - 1 & x_{i} < 6 \\ 1 & x_{i} > 6 \end{cases}$
计算 $G_{1} (x)$ 在训练数据集上的分类误差，样例 3、4 被错误分类，因此 $G_{1}$ 的分类误差为 $e r r_{1} =$ $\sum_{i = 1}^{N} w_{1, i} I (G_{1} (x_{i}) \neq y_{i}) = 0.1 + 0.1 = 0.2$
根据分类误差计算弱分类器 $G_{1} (x)$ 的权重： $α_{1} = \frac{1}{2} \ln \frac{1 - e r r_{1}}{e r r_{1}} = 0.6931$
更新下一轮第 m=2 个分类器训练时第 i 个训练样本的权重： $D_{2} =$ ${w_{2, i}}_{0}^{10}$ , $w_{2, i} = \frac{w_{1, i}}{Z_{1}} e^{- α_{1} y_{i} G_{1} (x_{i})}$ , 可得到数据样本新的权重:
$D_{2} = (0.0625, 0.0625, 0.25, 0.25, 0.0625, 0.0625, 0.0625, 0.0625, 0.0625, 0.0625)$
通过加权线性组合得到当前的分类器 $f_{1} (x) =$ $\sum_{i = 1}^{M} α_{m} G_{m} (x) = 0.6931 G_{1} (x)$
在下图中，被分类错误数据样本的形状尺寸比其它数据样本形状稍大，以表示被分类错误的样本数据权重增大。

对 m = 2

对于具有分布权重为 $D_{2}$ 的训练数据，当阈值 $ε = - 6$ 时，如下表示：基分类器 $G_{2}$ 具有最小的错误率。 $G_{2}$ 分类器
- $G_{2} (x_{i}) = {\begin{cases} - 1 & x_{i} < - 6 \\ 1 & x_{i} > - 6 \end{cases}$
分类误差 $e r r_{2} = \sum_{i = 1}^{N} w_{2, i} I (G_{2} (x_{i}) \neq y_{i}) = 0.25 (0.0625 * 4)$
弱分类器 $G_{2} (x)$ 的权重 $α_{2} = \frac{1}{2} \ln \frac{1 - e r r_{2}}{e r r_{2}} = 0.5439$
当进行下一轮分类器训练时，样本权重更新如下： $D_{3} = (0.04166667, 0.04166667, 0.16666667, 0.16666667, 0.125, 0.125, 0.125, 0.125, 0.04166667, 0.04166667)$
通过加权线性组合得到当前的分类器 $f_{2} (x) = 0.6931 G_{1} (x) + 0.5439 G_{2} (x)$

对 m = 3

对于具有分布权重为 $D_{3}$ 的训练样本数据，当阈值 $ε = - 2$ 时，基分类器 $G_{3}$ 具有最小的错误率。 $G_{3}$ 分类器表示如下： $G_{3} (x_{i}) =$

-1 & x_i > -2 \ &
1 & x_i < -2 &
\end{cases}$$

分类误差 $e r r_{3} = \sum_{i = 1}^{N} w_{3, i} I (G_{3} (x_{i}) \neq y_{i}) = 0.1667 (0.04166667 * 4)$
弱分类器 $G_{3} (x)$ 的权重 $α_{3} = \frac{1}{2} \ln \frac{1 - e r r_{3}}{e r r_{3}} = 0.8047$
下一轮弱分类器训练时，训练数据样本的权重更新如下： $D_{4} = (0.125, 0.125, 0.1, 0.1, 0.075, 0.075, 0.075, 0.075, 0.125, 0.125)$
通过加权线性组合得到当前的分类器 $f_{3} (x) = 0.6931 G_{1} (x) + 0.5439 G_{2} (x) + 0.8047 G_{3} (x)$
在 $f_{3} (x)$ 的基础上，构造强分类器 $G (x) = sign (f_{3} (x)) = sign (0.6931 G_{1} (x) + 0.5439 G_{2} (x) + 0.8047 G_{3} (x))$ 。
这里 $sign (\cdot)$ 是符号函数，其输入值大于 0 时，符号函数输出为 1，反之为 -1。由于 $G (x)$ 在训练样本上分类错误率为 0，算法终止，得到最终的强分类器。

5.3 回看霍夫丁不等式

假设有个弱分类器 (1≤m≤M)，则 M 个弱分类器线性组合所产生误差满足如下条件：

P (\sum_{i = 1}^{M} G_{m} (x) \neq ζ (x)) \leq e^{- \frac{1}{2} M (1 - 2 ϵ)^{2}}

ζ(x) 是真实分类函数、ε ∈ (0,1)
上式表明，如果所“组合”弱分类器越多，则学习分类误差呈指数级下降，直至为零
上述不等式成立有两个前提条件：
1. 每个弱分类器产生的误差相互独立
2. 每个弱分类器的误差率小于 50%
因为每个弱分类器均是在同一个训练集上产生，条件 1）难以满足。也就是说，“准确性（对分类结果而言）”和“差异性（对每个弱分类器而言）”难以同时满足
Ada Boosting 采取了序列化学习机制，即一个分类器学习完成之后才会进行下一个分类器的学习，后一个分类器的学习受到前面分类器学习的影像。有些学习策略，如 Bagging 的集成学习方法，采用的是并行学习策略，不同分类器的学习互不影响

06 支持向量机

考试不作要求

期望风险（即真实风险） $R$ 与经验风险 $R_{e m p}$ 之间是有差别的，这个差别项被称为置信风险

与训练样本个数和模型复杂度都有密切的关系
- 即与分类器的 VC 维有关
结构风险最小化：用复杂度高的模型去拟合小样本，往往会导致过拟合，因此需要给经验风险 $R_{e m p}$ 加上一个惩罚项或者正则化项

VC 维：是对假设空间 H 复杂度的一种度量

一般地，在 r 维空间中，线性决策面的 VC 维为 r+1
当样本数 n 固定时，如果 VC 维越高，则算法模型的复杂性越高
VC 维越大，通常推广能力越差，置信风险会变大

线性可分支持向量机

寻找一个最优的超平面，其方程为 $w^{T} x + b = 0$ 。这里 $w =$ $(w_{1}, w_{2}, . . ., w_{d})$ 为超平面的法向量，与超平面的方向有关

B 为偏置项，是一个标量，其决定了超平面与原点之间的距离

支持向量机学习算法会去寻找一个最佳超平面，使得每个类别中距离超平面最近的样本点到超平面的最小距离最大

松弛变量，软间隔与 hinge 损失函数

硬间隔：存在一个线性超平面能将不同类别样本完全隔开
软间隔：允许部分错分给定的训练样本

核函数

将线性不可分样本从原始空间映射到一个更加高维的特征空间中去，使得样本在这个特征空间中高概率线性可分

如果原始空间是有限维，那么一定存在一个高维特征空间使样本可分

常见核函数：

线性	$κ (x_{i}, x_{j}) = x_{i} x_{j}$
多项式	$κ (x_{i}, x_{j}) = (γ x_{i} x_{j} + c)^{n}$
Radial basis function	$$\kappa (x_{i}, x_{j})=e^{-\frac{\left\Vert x_{i}-x_{j}\right\Vert^{2}}{2\sigma^{2}}}$$
Sigmoid	$κ (x_{i}, x_{j}) = \tanh (x_{i}, x_{j} - γ)$

07 生成学习模型

考试不作要求

生成模型旨在学习“数据是如何生成的”，通过建模联合概率分布 P (X, Y) 来实现
生成学习方法从数据中学习联合概率分布 P (X, Y)，然后求出条件概率分布 P (Y∣X) 作为预测模型，即 P (Y∣X)=P (X, Y) / P (X) 。

P (x, c_{i}) = \underset{似然概率}{\underset{⏟}{P (x | c_{i})}} \times \underset{先验概率}{\underset{⏟}{P (c_{i})}}

\underset{后验概率}{\underset{⏟}{P (c_{i} | x)}} = \frac{\underset{联合概率}{\underset{⏟}{P (x, c_{i})}}}{P (x)} = \frac{\underset{似然概率}{\underset{⏟}{P (x | c_{i})}} \times \underset{先验概率}{\underset{⏟}{P (c_{i})}}}{P (x)}

Example

Pasted image 20250529180743.png|475
如果基于生成方法进行学习：
Pasted image 20250529180805.png|450
如果基于判别方法进行学习：
Pasted image 20250529180826.png|475