机器学习——监督学习¶

机器学习的目标是从原始数据中提取特征，学习一个映射函数 f 将上述特征（或原始数据）映射到语义空间，寻找数据和任务目标之间的关系。

监督学习

给定带有标签信息的训练集合，学习从输入到输出的映射

一般被应用在回归或分类的任务中

无监督学习

最大特点是数据无标签

一般被应用在聚类或若干降维任务中

半监督学习依赖于部分被标注的数据

强化学习

一种序列数据决策学习方法

从与环境交互中学习，通过回报值（reward）让智能体（agent）学习到在不同状态（state）下如何选择行为方式（action）

监督学习一般包含三个部分内容：

从训练数据集中学习得到映射函数 f
在测试数据集上测试映射函数 f
在未知数据集上测试映射函数 f（投入使用）

训练及中产生的损失一般称为经验风险（empirical risk），越小对训练集拟合效果越好；

测试集中加入从真实数据分布采样的样本时，测试集上的损失会不断逼近期望风险（expected risk），越小模型越好；

机器学习的目标是追求期望风险最小化。

损失函数¶

训练集中一共有 $n$ 个标注数据，第 $i$ 个标注数据记为 $(x_i, y_i)$，其中第 $i$ 个样本数据为 $x_i$，$y_i$ 是 $x_i$ 的标注信息。

从训练数据中学习得到的映射函数记为 $f$，$f$ 对 $x_i$ 的预测结果记为 $f(x_i)$。损失函数就是用来计算 $x_i$ 真实值 $y_i$ 与预测值 $f(x_i)$ 之间差值的函数。

很显然，在训练过程中希望映射函数在训练数据集上得到“损失”之和最小，即：

\[ \min \sum_{i=1}^{n} \text{Loss}(f(x_i), y_i) \]

损失函数名称	损失函数定义
0-1 损失函数	$$ \text{Loss}(y_i, f(x_i)) = [f(x_i) = y_i] $$
平方损失函数	$$ \text{Loss}(y_i, f(x_i)) = (y_i - f(x_i))^2 $$
绝对损失函数	$$ \text{Loss}(y_i, f(x_i)) = \|y_i - f(x_i)\| $$
对数损失函数/对数似然损失	$$ \text{Loss}(y_i, P(y_i\|x_i)) = -\log(P(y_i\|x_i)) $$

过学习和欠学习¶

经验风险（训练集上表现）	期望风险（测试集上表现）	描述
小	小	泛化能力强
小	大	过学习（模型过于复杂）
大	大	欠学习
大	小	“神仙算法”或“黄梁美梦”

结构风险最小化（structural risk minimization）：防止过学习，基于过学习时参数值通常都较大这一发现，在经验风险上加上表示模型复杂度的正则化项（regularizer）或惩罚项（penalty term），在最小化经验风险与降低模型复杂度之间寻找平衡

监督学习方法¶

判别方法¶

判别方法直接对条件概率 $P(Y|X)$ 进行建模，即给定输入 $X$，预测输出 $Y$。

优点：

通常计算效率较高，因为直接学习分类边界。
在分类任务中表现通常更好，尤其是当训练数据充足时。

缺点：

无法生成新的数据样本，因为不建模数据的分布。
对数据的分布假设较少，可能对噪声敏感。

常见算法：回归模型、神经网络、支持向量机和 Ada boosting.

生成方法¶

生成方法对联合概率 $P(X, Y)$ 进行建模，即同时学习输入 $X$ 和输出 $Y$ 的分布，生成方法的目标是理解数据的生成过程。

优点：

可以生成新的数据样本（如生成图像、文本，即可以搞出新的 $X$）。
对数据的分布有更全面的理解，适合小样本学习。

缺点：

计算复杂度较高，因为需要建模整个数据的分布。
联合分布概率 $P(X,Y)$ 或似然概率 $P(X|Y)$ 求取很困难。
在分类任务中，性能可能不如判别方法。

常见算法：贝叶斯方法、隐马尔可夫链。

线性回归¶

一元线性回归¶

\[ \begin{align*} h_\theta(x) &= \theta_0 + \theta_1 x \\ J(\theta_0, \theta_1) &= \frac{1}{2m} \sum_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)})^2 \end{align*} \]

梯度下降法¶

即：

\[ \begin{align*} \text{temp0} &:= \theta_{0} - \alpha \frac{\partial}{\partial \theta_{0}} J(\theta_{0}, \theta_{1}) \\ \text{temp1} &:= \theta_{1} - \alpha \frac{\partial}{\partial \theta_{1}} J(\theta_{0}, \theta_{1}) \\ \theta_{0} &:= \text{temp0} \\ \theta_{1} &:= \text{temp1} \end{align*} \]

其中 $\alpha$ 是学习率，控制步幅。

最小二乘法¶

回归模型：$y_i = ax_i + b \ (1 \leq i \leq n)$

通过最小化目标函数：

\[ L(a, b) = \sum_{i=1}^n (y_i - ax_i - b)^2 \]

对 $a$ 和 $b$ 求偏导并令其为 0，可得到：

\[ \frac{\partial L(a, b)}{\partial a} = \sum_{i=1}^n 2(y_i - ax_i - b)(-x_i) = 0 \]

\[ \frac{\partial L(a, b)}{\partial b} = \sum_{i=1}^n 2(y_i - ax_i - b)(-1) = 0 \]

将 $b = \bar{y} - a\bar{x}$（其中 $\bar{x} = \frac{\sum_{i=1}^n x_i}{n}$, $\bar{y} = \frac{\sum_{i=1}^n y_i}{n}$）代入整理，得到斜率 $a$ 的解：

\[ a = \frac{\sum_{i=1}^n x_i y_i - n\bar{x}\bar{y}}{\sum_{i=1}^n x_i x_i - n\bar{x}^2} \]

截距 $b$ 可通过：

\[ b = \bar{y} - a\bar{x} \]

多元线性回归¶

多元线性回归模型用于描述因变量 $y$ 与多个自变量 $x_1, x_2, \dots, x_n$ 之间的线性关系，其数学模型为：

\[ y = a_0 + a_1 x_1 + a_2 x_2 + \dots + a_n x_n \]

可以写成矩阵形式：

\[ y = X^T a \]

其中：

$X = [x_1, x_2, \dots, x_m]$ 是包含所有自变量的设计矩阵（扩展后每行加一列常数项 1）；
$a = [a_0, a_1, \dots, a_n]^T$ 是回归系数的列向量；
$y = [y_1, y_2, \dots, y_m]^T$ 是目标变量的列向量。

最小化均方误差¶

为找到最优的回归系数向量 $a$，我们使用均方误差 (MSE) 作为目标函数：

\[ J_m = \frac{1}{m} \sum_{i=1}^m (y_i - f(x_i))^2 \]

将其写成矩阵形式：

\[ J_m(a) = \frac{1}{m} (y - X^T a)^T (y - X^T a) \]

梯度计算与求解¶

通过对目标函数 $J_m(a)$ 求导并令其为 0，可以得到回归系数 $a$ 的解析解：

\[ \nabla J(a) = -2 X (y - X^T a) \]

令 $\nabla J(a) = 0$，得到：

\[ X X^T a = X y \]

求解上式可得到回归系数向量：

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

结论¶

最终，多元线性回归模型的参数 $a$ 可以通过以上公式计算得到：

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

这是一种基于最小二乘法的解析解，适用于中小规模数据集，能够快速计算回归系数。

逻辑回归¶

逻辑回归是一种广泛用于分类任务的模型，适合二分类问题（如正类和负类）。虽然名字中带有“回归”，但其目标是预测一个样本属于某一类的概率，而非连续值。

逻辑回归模型假设目标变量 $y \in \{0, 1\}$，并通过如下模型定义：

\[ h_\theta(x) = \sigma(\theta^T x) \]

其中：

$h_\theta(x)$ 表示样本属于正类的概率；
$\sigma(z)$ 是 Sigmoid 函数，定义为：

\[ \sigma(z) = \frac{1}{1 + e^{-z}} \]

Sigmoid 函数将线性回归模型 $\theta^T x$ 的输出映射到 $(0, 1)$ 区间，便于解释为概率。

损失函数¶

为了训练逻辑回归模型，最小化以下的对数损失函数：

\[ J(\theta) = -\frac{1}{m} \sum_{i=1}^m \big[ y^{(i)} \log h_\theta(x^{(i)}) + (1 - y^{(i)}) \log (1 - h_\theta(x^{(i)}) ) \big] \]

优化方法¶

使用梯度下降法优化参数 $\theta$，更新规则为：

\[ \theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta) \]

应用场景¶

逻辑回归广泛用于金融风控（如用户是否违约）、医疗诊断（如疾病预测）以及各种分类问题中，具有简单、快速、可解释的特点。

决策树¶

什么是决策树？¶

决策树是一种树形结构的分类和回归方法，能够通过属性的分割将数据集划分为不同类别。其主要特征包括：

节点与分支：
- 每个非叶子节点表示对某个属性的判断。
- 每个分支代表基于该属性值的决策。
- 每个叶子节点代表分类或预测的最终结果。
决策树通过将复杂问题分解为多个简单的基于单个信息的推理任务，利用树状结构逐步完成决策过程。

决策树的相关系数¶

在构建决策树的过程中，我们需要选择最优的属性来分割数据。选择依据通常是属性的“纯度”。衡量纯度的两个重要概念是熵（Entropy）和信息增益（Information Gain）。

熵用来衡量样本集合的不确定性程度，熵越高，说明集合的不确定性越大，纯度越低。给定一个样本集合 $D$，其熵定义为： $$ H(D) = - \sum_{k=1}^K p_k \log_2 p_k $$

其中：

$K$ 是类别的数量；
$p_k$ 是样本属于第 $k$ 类的概率。

信息增益表示选择某个属性后，样本集合的不确定性减少的程度。某属性 $A$ 对样本集合 $D$ 的信息增益定义为： $$ IG(D, A) = H(D) - \sum_{v \in \text{Values}(A)} \frac{|D_v|}{|D|} H(D_v) $$

其中：

$\text{Values}(A)$ 表示属性 $A$ 的可能取值；
$D_v$ 是样本集合 $D$ 中属性 $A$ 取值为 $v$ 的子集。

信息增益越大，表示该属性对分类越有帮助。

增益率定义为信息增益与分裂信息的比值： $$ \text{Gain Ratio}(D, A) = \frac{\text{Gain}(D, A)}{\text{info}(D)} $$ 但是存在的问题是如果我们以增益率为标准分裂，系统会偏向于选择信息较少的部分。

基尼系数是一种简单高效的纯度衡量指标，与熵相比，基尼系数无需计算对数，计算更为简单。 $$ \text{Gini}(D) = 1 - \sum_{k=1}^K p_k^2 $$ 当样本全属于一个类别时，基尼系数为 0，表示纯度最高；当样本均匀分布于各类别时，基尼系数最大。

决策树的构建¶

构建决策树的过程主要包括以下步骤：

选择最优属性：
- 计算所有属性的信息增益；
- 选择信息增益 / 增益率 / 基尼系数最大的属性作为当前节点的分裂属性。
分割样本集：
- 根据选择的分裂属性，将样本集划分为若干子集，每个子集对应一个分支。
递归构建子树：
- 对每个子集重复上述过程，直到满足停止条件：
  - 子集纯度达到100%（大家都长一样）；
  - 或者样本集属性为空；
  - 或者样本数量不足以继续分裂。

连续属性离散化¶

有些时候，一些特征可能是连续的，我们需要运用离散化的方法，便于分类分支。

属性排序：
- 假设连续属性 $a$ 在样本集 $D$ 中出现 $n$ 个不同的取值，按从小到大的顺序排列，记为 $a^1, a^2, \dots, a^n$。
候选分割点：
- 基于分割点 $t$，可以将样本集 $D$ 分为两个子集：
  - $D_t^- = \{x \in D | a(x) \leq t\}$，即属性 $a$ 的值不大于分割点 $t$ 的样本集；
  - $D_t^+ = \{x \in D | a(x) > t\}$，即属性 $a$ 的值大于分割点 $t$ 的样本集。
分割点集合：
- 考虑所有相邻取值的中位点作为候选分割点集合：
  
  \[ T_a = \left\{ \frac{a^i + a^{i+1}}{2} \ \middle|\ 1 \leq i \leq n-1 \right\} \]
- 这里，$\frac{a^i + a^{i+1}}{2}$ 是相邻取值 $a^i$ 和 $a^{i+1}$ 的中点。
选取最优划分点： 分割完毕以后，选取最优的划分点，对集合进行二分。

剪枝（Pruning）¶

为了防止过拟合，决策树模型通常会进行剪枝。剪枝分为两种方式：

预剪枝：
- 在构建过程中提前停止分裂，避免生成过深的树。
- 通过设定条件（如节点样本数、信息增益阈值）判断是否继续分裂。
后剪枝：
- 在决策树生成后，评估子树对整体模型性能的影响，并选择性地合并节点。

线性判别分析¶

线性判别分析 (LDA) 是一种基于监督学习的降维方法，也称为 Fisher 线性判别分析 (FDA)。它利用数据中不同类别的标注信息，通过寻找一种映射方式，将数据从高维空间投影到低维空间中，使得投影后的数据尽可能地分离（类内样本更紧凑，类间样本更远离），从而实现分类或降维的目的。

LDA 既是一种分类方法，也是降维方法，尤其在带有标注数据的降维任务中表现突出。

LDA 的核心思想¶

LDA 的目标是通过线性投影，将样本点从高维空间投影到低维空间中，使得：

类内差异最小化：同一类别的样本在投影后尽可能聚集；
类间隔离最大化：不同类别的样本在投影后尽可能远离。

通过上述两个目标，LDA 能够确保投影后的低维空间中，不同类别的数据点更容易分开，从而提升分类的准确性。

LDA 的基本步骤¶

LDA 的降维可以通过以下步骤实现：

计算类别均值向量：对于每一类样本，计算其均值向量 $m_1, m_2, \dots, m_k$，其中 $k$ 是类别的数量。 $$ m_i = \frac{1}{N_i} \sum_{x \in D_i} x $$ 其中，$D_i$ 是第 $i$ 类的数据集，$N_i$ 是该类别中样本的数量。
计算类内散度矩阵：类内散度矩阵 $S_w$ 衡量同一类别的样本之间的离散程度，其定义为： $$ S_w = \sum_{i=1}^k S_i = \sum_{i=1}^k \sum_{x \in D_i} (x - m_i)(x - m_i)^T $$ 其中，$S_i$ 是第 $i$ 类的散度矩阵。
计算类间散度矩阵：类间散度矩阵 $S_b$ 衡量不同类别之间的均值差异，其定义为： $$ S_b = \sum_{i=1}^k N_i (m_i - m)(m_i - m)^T $$ 其中，$m$ 是所有样本的全局均值向量。
优化目标： LDA 通过最大化类间散度和类内散度的比值，找到最优投影方向。具体目标是最大化如下目标函数： $$ J(W) = \frac{|W^T S_b W|}{|W^T S_w W|} $$ 其中，$W$ 是投影矩阵。
求解最优投影矩阵：通过解广义特征值问题（找最大的投影，就是找最长的投影轴）： $$ S_w^{-1} S_b W = \lambda W $$ 选取对应的前 $r$ 个最大特征值的特征向量，构成投影矩阵 $W$。
投影降维：使用投影矩阵 $W$，将样本点从原始空间投影到低维空间： $$ y = W^T x $$

AdaBoosting（自适应提升）¶

AdaBoosting（Adaptive Boosting）是一种基于集成学习（ensemble learning）的提升算法，主要用于提升分类器的性能。其核心思想是将多个弱分类器（weak classifiers）组合成一个强分类器（strong classifier），从而解决复杂的分类任务。

核心思想¶

任务分解：

对于一个复杂的分类任务，AdaBoosting 将其分解为多个子任务。
每个子任务由一个弱分类器完成，而弱分类器是指在分类精度上仅略优于随机猜测的模型。

集成弱分类器：

将多个弱分类器通过加权组合，形成一个强分类器，从而提升分类性能。

自适应权重调整：

在每一轮迭代中，增加对被错误分类样本的关注度（权重增大），以便下一轮的弱分类器能够更好地分类这些样本。
对表现较好的弱分类器赋予更高的权重，减少表现较差的弱分类器的影响。

可学习理论¶

AdaBoosting 的理论基础来自可学习理论（computational learning theory）。以下是相关背景：

可计算学习理论：

关心什么样的问题可以被计算。
如果一个任务是图灵可停机的，那么该任务是可计算的。

可学习理论：

研究什么样的任务可以被模型习得。

包括：
- 如何知道学习所得的假设（hypothesis）是正确的？
- 为了接近真实假设，所需的训练数据量是多少？
- 假设空间的复杂度如何度量和选择？
PAC 学习（Probably Approximately Correct Learning）：

概率近似正确的学习假设：
- 弱可学习模型：分类准确率略高于随机猜测（大于 0.5），但无法很好地完成分类任务。
- 强可学习模型：能够以较高精度对绝大多数样本进行分类。
等价性：强可学习和弱可学习是等价的，通过 AdaBoosting 可以将弱分类器提升为强分类器。

AdaBoosting 算法步骤¶

核心目标¶

提高被错误分类样本的权重：聚焦尚未被正确分类的样本。
组合弱分类器：给误差小的弱分类器赋予更高的权重，减少误差大的弱分类器的权重。

算法流程¶

因为本质上所有的分类都可以从二分开始，所以我们介绍的都是二分分类。

初始化样本权重：

给每个样本分配一个初始权重： $$ w_1(i) = \frac{1}{N} $$ 其中 $N$ 是样本的总数。
迭代训练弱分类器：

对于每轮迭代 $m$：

a. 训练一个弱分类器 $G_m$，使其在样本权重 $w_m$ 下最小化分类误差。

b. 计算分类误差： $$ \epsilon_m = \frac{\sum_{i=1}^N w_m(i) \cdot I(G_m(x_i) \neq y_i)}{\sum_{i=1}^N w_m(i)} $$ 其中，$I$ 为指示函数，当分类错误时为 1，否则为 0，相当于计算有多少比例的数据拟合成功。

c. 计算弱分类器的权重： $$ \alpha_m = \frac{1}{2} \ln\left(\frac{1 - \epsilon_m}{\epsilon_m}\right) $$ 以 $\dfrac{1}{2}$ 为界，比随机还差的赋予很差的权重，比随机好的赋予较高的权重。

d. 更新样本权重： $$ w_{m+1}(i) = w_m(i) \cdot e^{-\alpha_m y_i G_m(x_i)} $$ 并进行归一化，使得 $\sum w_{m+1}(i) = 1$。
构建强分类器：

将所有弱分类器按照其权重 $\alpha_m$ 组合成强分类器： $$ H(x) = \text{sign} \left( \sum_{m=1}^M \alpha_m G_m(x) \right) $$

这里 $\text{sign}$ 就是根据更靠近 0 还是更靠近 1 来进行 01 分类。

直观理解¶

AdaBoosting 是一个序列化学习算法：

每一轮学习的新分类器都依赖于上一轮的结果。
错误分类的样本会在下一轮中被重点关注。

AdaBoosting 与 Bagging 的对比¶

特性	AdaBoosting	Bagging
学习机制	序列化学习，后续分类器依赖于前序分类器	并行学习，所有分类器独立训练
样本权重调整	动态调整样本权重	不调整样本权重，随机采样生成子集
对异常值的敏感性	对异常值敏感	对异常值不敏感
常见模型	基于弱分类器	随机森林等基于并行弱分类器的模型

学习生成模型¶

生成模型是指通过学习数据的联合概率分布 $ P(X, Y) $，从而完成预测任务的模型。与判别模型不同，生成模型不仅可以用于分类，还可以生成新的数据样本。

核心思想¶

联合概率分布：学习生成模型的核心是构建输入 $ X $ 和输出 $ Y $ 的联合概率分布 $ P(X, Y) $。
分解联合概率：根据概率论中的链式法则，可以将联合概率分布分解为条件概率 $ P(Y|X) $ 和先验概率 $ P(X) $：

$$ P(X, Y) = P(Y) P(X|Y) $$ 生成模型先通过 $ P(Y) $ 和 $ P(X|Y) $ 来估计 $ P(X, Y) $，再通过贝叶斯公式计算条件概率 $ P(Y|X) $ 来完成分类任务。

为什么不直接计算联合分布？

Y 的取值一般很少，X 的取值一般很多，如果直接联合分布，那么总共有 $|X|^{|Y|}$ 个情况，太多了。
如果用条件概率，只需要 $|Y|*|X|+|Y|$ 即可。

朴素贝叶斯分类器¶

朴素贝叶斯分类器是一种典型的生成模型，它基于贝叶斯定理和“特征条件独立”假设。朴素贝叶斯分类器以简单、快速、高效著称，适用于许多分类任务。

核心思想¶

贝叶斯公式：根据贝叶斯公式：

$$ P(Y|X) = \frac{P(X|Y) P(Y)}{P(X)} $$

$ P(Y|X) $：后验概率，表示给定输入 $ X $ 属于类别 $ Y $ 的概率；
$ P(X|Y) $：似然概率，表示类别 $ Y $ 下观察到输入 $ X $ 的概率；
$ P(Y) $：先验概率，表示类别 $ Y $ 的先验分布；
$ P(X) $：归一化常数，表示所有类别的联合概率和。

朴素假设：

假设输入特征 $ X $ 的每个维度 $ X_i $ 在给定类别 $ Y $ 的条件下是独立的： $$ P(X|Y) = \prod_{i=1}^n P(X_i|Y) $$
这一“朴素”假设大幅简化了计算复杂度，使得模型可以在高维特征空间中快速计算。

分类规则：对于一个新样本 $ X $，朴素贝叶斯分类器通过计算后验概率 $ P(Y|X) $，选择后验概率最大的类别作为分类结果： $$ Y = \arg\max_{Y} P(Y) \prod_{i=1}^n P(X_i|Y) $$

参数估计¶

先验概率：先验概率 $ P(Y) $ 通常通过样本频率估计： $$ P(Y = y_k) = \frac{\text{样本中属于 } y_k \text{ 的数量}}{\text{样本总数}} $$
条件概率：条件概率 $ P(X_i|Y) $ 的计算方法取决于输入特征的类型：

离散型特征：使用极大似然估计： $$ P(X_i = x|Y = y_k) = \frac{\text{样本中 } X_i = x \text{ 且 } Y = y_k \text{ 的数量}}{\text{样本中 } Y = y_k \text{ 的数量}} $$
连续型特征：通常假设特征服从高斯分布，计算条件概率： $$ P(X_i|Y = y_k) = \frac{1}{\sqrt{2\pi \sigma_k^2}} e^{-\frac{(X_i - \mu_k)^2}{2\sigma_k^2}} $$ 其中 $ \mu_k $ 和 $ \sigma_k^2 $ 分别为类别 $ y_k $ 下特征 $ X_i $ 的均值和方差。

归一化：$ P(X) $ 作为归一化常数，通过对所有可能的 $ Y $ 计算 $ P(X, Y) $ 的和得到： $$ P(X) = \sum_{k=1}^K P(X|Y = y_k) P(Y = y_k) $$

优点与缺点¶

优点：

简单高效：计算简单，特别适合高维数据；
鲁棒性强：对小数据集和噪声不敏感；
解释性强：直观易懂，能够清晰表达每个特征对分类的贡献。

缺点：

特征独立性假设：

在实际数据中，特征往往是相关的，这一假设可能不成立；
特征相关性强时，模型性能可能下降。

参数估计限制：

条件概率估计依赖于样本数量，数据稀疏时可能存在问题；
对连续特征的高斯分布假设未必适用。