BUAA-ML

本文由AI根据课件生成。

1. 机器学习概述

1.1 什么是机器学习

机器学习是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身性能的学科。

• Tom Mitchell定义：一个计算机程序从经验E中学习，对于某类任务T和性能度量P，如果它在T上的性能（由P衡量）随着经验E的提高而提高，则称该程序从经验E中学习。

1.2 主要研究问题

按学习方式分类：

• 监督学习：训练数据带有标签，包括分类（离散输出）和回归（连续输出）
• 无监督学习：训练数据无标签，包括聚类和降维
• 半监督学习：同时使用少量有标记样本和大量未标记样本
• 强化学习：通过与环境交互学习策略

1.3 过拟合与欠拟合

• 欠拟合：模型复杂度低，无法拟合训练数据，训练误差和测试误差都很大（高偏差、低方差）
• 过拟合：模型复杂度高，过度拟合训练数据，训练误差小但测试误差大（低偏差、高方差）

泛化误差的偏差-方差分解：

$$E(f;D) = \text{noise}^2 + \text{bias}^2(x) + \text{var}(x)$$

缓解过拟合的方法：

• 增加训练样本数量
• 正则化：在对目标函数中加入对权值向量的惩罚项

  $$\tilde{E}(w) = \frac{1}{2}\sum_{n=1}^{N}(y(x_n,w)-t_n)^2 + \frac{\lambda}{2}\|w\|^2$$

---

2. 数学基础

2.1 概率统计基础

• 联合概率：A和B共同发生的概率 $P(A,B)$
• 条件概率：B已发生条件下A发生的概率

  $$P(A|B) = \frac{P(A,B)}{P(B)}$$

• 乘法公式：

  $$P(A_1A_2...A_n) = P(A_1)P(A_2|A_1)...P(A_n|A_1...A_{n-1})$$

• 全概率公式：设 $A_1,A_2,...,A_n$ 两两互不相容，则

  $$P(B) = \sum_{k=1}^{n}P(A_k)P(B|A_k)$$

• 贝叶斯公式：

  $$P(B|A) = \frac{P(B)P(A|B)}{P(A)} = \frac{P(B)P(A|B)}{\sum_{k}P(B_k)P(A|B_k)}$$

例题：某人外出旅游两天，第一天下雨概率0.6，第二天下雨概率0.3，两天都下雨概率0.1。
求：(1) 第一天下雨而第二天不下雨的概率；(2) 至少有一天下雨的概率。

解：设 $A_i$ 表示第i天下雨。

• (1) $P(A_1\bar{A}_2) = P(A_1) - P(A_1A_2) = 0.6 - 0.1 = 0.5$
• (2) $P(A_1 \cup A_2) = P(A_1) + P(A_2) - P(A_1A_2) = 0.6 + 0.3 - 0.1 = 0.8$

2.2 随机变量与分布

• 期望：$E(X) = \sum_{i}x_ip_i$（离散），$E(X) = \int_{-\infty}^{+\infty}xp(x)dx$（连续）
• 方差：$D(X) = E[(X-E(X))^2] = E(X^2) - [E(X)]^2$
• 协方差：$\text{cov}(X,Y) = E[(X-E(X))(Y-E(Y))]$
• 相关系数：$\rho_{XY} = \frac{\text{cov}(X,Y)}{\sqrt{D(X)}\sqrt{D(Y)}}$
• 高斯分布：

  $$p(x|\mu,\sigma^2) = \frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$$

2.3 概率密度函数估计

最大似然估计(MLE)：
假设样本 $X=\{x_1,...,x_N\}$ 独立同分布，似然函数：

$$l(\theta) = \prod_{i=1}^{N}p(x_i|\theta)$$

对数似然函数：

$$H(\theta) = \ln l(\theta) = \sum_{i=1}^{N}\ln p(x_i|\theta)$$

求解：$\frac{\partial H}{\partial \theta} = 0$

例题：单变量正态分布，已知 $\theta = [\mu, \sigma^2]$，求MLE。

解：

$$H(\mu,\sigma^2) = \sum_{i=1}^{N}\ln p(x_i|\mu,\sigma^2) = -\frac{N}{2}\ln(2\pi\sigma^2) - \frac{1}{2\sigma^2}\sum_{i=1}^{N}(x_i-\mu)^2$$

令偏导为0：

$$\frac{\partial H}{\partial \mu} = \frac{1}{\sigma^2}\sum_{i=1}^{N}(x_i-\mu) = 0 \Rightarrow \hat{\mu} = \frac{1}{N}\sum_{i=1}^{N}x_i$$

$$\frac{\partial H}{\partial \sigma^2} = -\frac{N}{2\sigma^2} + \frac{1}{2(\sigma^2)^2}\sum_{i=1}^{N}(x_i-\mu)^2 = 0 \Rightarrow \hat{\sigma}^2 = \frac{1}{N}\sum_{i=1}^{N}(x_i-\hat{\mu})^2$$

非参数估计-Parzen窗法：

$$\hat{p}(x) = \frac{1}{N}\sum_{i=1}^{N}\frac{1}{V_N}\varphi\left(\frac{x-x_i}{h_N}\right)$$

其中 $\varphi(\cdot)$ 为窗函数，$V_N = h_N^d$ 为窗体积。

2.4 矩阵基础

• 迹：$\text{tr}(A) = \sum_{i=1}^{n}a_{ii}$
• 常用求导公式：
  • $\frac{\partial (Ax)}{\partial x} = A^T$
  • $\frac{\partial (x^TAx)}{\partial x} = (A+A^T)x$

---

3. 模型评估与选择

3.1 数据集划分方法

• 留出法：随机划分为训练集和测试集
• k折交叉验证：将数据分为k个子集，轮流用k-1个训练，1个测试
• 留一法：k折交叉验证的特例，k等于样本总数
• 自助法：有放回抽样，约36.8%样本不被抽到作为测试集

3.2 性能度量

回归任务：

• 均方误差：$E(f;D) = \frac{1}{N}\sum_{i=1}^{N}(f(x_i)-y_i)^2$
• 平均绝对误差：$E(f;D) = \frac{1}{N}\sum_{i=1}^{N}|f(x_i)-y_i|$

分类任务：

• 错误率：$E(f;D) = \frac{1}{N}\sum_{i=1}^{N}\mathbb{I}(f(x_i) \neq y_i)$
• 准确率：$\text{acc}(f;D) = 1 - E(f;D)$

混淆矩阵：

真实\预测	正例	负例
正例	TP	FN
负例	FP	TN

• 查准率：$P = \frac{TP}{TP+FP}$
• 查全率：$R = \frac{TP}{TP+FN}$
• F1度量：$F1 = \frac{2 \times P \times R}{P+R}$
• F$\beta$度量：$F_\beta = \frac{(1+\beta^2) \times P \times R}{\beta^2 \times P + R}$

---

4. 贝叶斯决策理论

4.1 基本概念

• 先验概率 $P(\omega_i)$：由历史数据得到的概率
• 类条件概率密度 $p(x|\omega_i)$：已知类别下样本的分布
• 后验概率 $P(\omega_i|x)$：利用最新数据修正后的概率

贝叶斯公式：

$$P(\omega_i|x) = \frac{p(x|\omega_i)P(\omega_i)}{p(x)} = \frac{p(x|\omega_i)P(\omega_i)}{\sum_{j=1}^{c}p(x|\omega_j)P(\omega_j)}$$

4.2 最小错误率贝叶斯决策

目标：使平均错误率最小。

决策规则（多种等价形式）：

1. 若 $P(\omega_i|x) = \max_{j=1,...,c}P(\omega_j|x)$，则 $x \in \omega_i$
2. 似然比形式：若 $l(x) = \frac{p(x|\omega_1)}{p(x|\omega_2)} > \frac{P(\omega_2)}{P(\omega_1)}$，则 $x \in \omega_1$
3. 对数似然比形式：若 $h(x) = \ln l(x) > \ln\frac{P(\omega_2)}{P(\omega_1)}$，则 $x \in \omega_1$

例题：细胞分类诊断。正常细胞 $P(\omega_1)=0.9$，异常细胞 $P(\omega_2)=0.1$。某细胞观察值x满足 $p(x|\omega_1)=0.2$，$p(x|\omega_2)=0.4$。判断该细胞类型。

解：

$$P(\omega_1|x) = \frac{0.2 \times 0.9}{0.2 \times 0.9 + 0.4 \times 0.1} = \frac{0.18}{0.22} = 0.818$$

$$P(\omega_2|x) = \frac{0.4 \times 0.1}{0.22} = 0.182$$

因为 $P(\omega_1|x) > P(\omega_2|x)$，故判断为正常细胞。

4.3 最小风险贝叶斯决策

损失函数 $\lambda(\alpha_i, \omega_j)$ 表示将实际为 $\omega_j$ 的样本决策为 $\alpha_i$ 的损失。

条件风险：

$$R(\alpha_i|x) = \sum_{j=1}^{c}\lambda(\alpha_i, \omega_j)P(\omega_j|x)$$

决策规则：选择使条件风险最小的决策

$$\alpha^* = \arg\min_{i} R(\alpha_i|x)$$

例题：接上例，设损失函数表：

决策\状态	$\omega_1$	$\omega_2$
$\alpha_1$	0	6
$\alpha_2$	1	0

解：

$$R(\alpha_1|x) = \lambda(\alpha_1,\omega_1)P(\omega_1|x) + \lambda(\alpha_1,\omega_2)P(\omega_2|x) = 0 \times 0.818 + 6 \times 0.182 = 1.092$$

$$R(\alpha_2|x) = 1 \times 0.818 + 0 \times 0.182 = 0.818$$

因为 $R(\alpha_2|x) < R(\alpha_1|x)$，故决策为异常细胞（$\alpha_2$）。

关系：最小错误率贝叶斯决策是0-1损失函数条件下的最小风险贝叶斯决策。

4.4 朴素贝叶斯决策

属性条件独立性假设：对于已知类别，假设所有属性相互独立。

决策规则：

$$y = \arg\max_{c} P(y_c)\prod_{j=1}^{d}P(x_j|y_c)$$

先验概率估计：$\hat{P}(y_c) = \frac{|D_c|}{|D|}$

离散属性条件概率（拉普拉斯修正）：

$$\hat{P}(x_j|y_c) = \frac{|D_{c,x_j}|+1}{|D_c|+N_j}$$

连续属性：假设服从高斯分布 $p(x_j|y_c) \sim N(\mu_{c,j}, \sigma_{c,j}^2)$

---

5. 线性模型

5.1 线性回归

假设函数：$f(x) = w^Tx + b$，其中 $x_0=1$ 表示截距项。

目标函数（均方误差）：

$$J(w) = \frac{1}{2}\sum_{i=1}^{N}(f(x_i)-y_i)^2$$

标准方程组（解析解）：

$$w = (X^TX)^{-1}X^Ty$$

梯度下降法：

$$w := w - \alpha \nabla J(w)$$

其中梯度：$\nabla J(w) = X^T(Xw-y)$

• 批处理梯度下降(BGD)：每次用所有样本
• 随机梯度下降(SGD)：每次用一个样本

5.2 逻辑回归

本质：用线性回归预测真实标记的对数几率。

Sigmoid函数：

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

后验概率：

$$p(C_1|x) = \sigma(w^Tx) = \frac{1}{1+e^{-w^Tx}}$$

对数几率（logit）：

$$\ln\frac{p}{1-p} = w^Tx$$

交叉熵误差函数：

$$E(w) = -\sum_{n=1}^{N}\{t_n\ln y_n + (1-t_n)\ln(1-y_n)\}$$

梯度：

$$\nabla E(w) = \sum_{n=1}^{N}(y_n-t_n)x_n$$

多类问题Softmax函数：

$$p(C_k|x) = \frac{\exp(a_k)}{\sum_j\exp(a_j)}$$

5.3 线性判别函数

两类线性判别函数：$g(x) = w^Tx + w_0$

• 若 $g(x) > 0$，则 $x \in \omega_1$
• 若 $g(x) < 0$，则 $x \in \omega_2$

Fisher准则：
寻找投影方向w，使Fisher准则函数最大化：

$$J_F(w) = \frac{w^TS_bw}{w^TS_ww}$$

其中 $S_b$ 为类间散度矩阵，$S_w$ 为类内散度矩阵。

解：$w^* = S_w^{-1}(m_1-m_2)$

感知机准则：
对于线性可分问题，构造准则函数：

$$J_P(a) = \sum_{y \in Y_M}(-a^Ty)$$

其中 $Y_M$ 为被错分的样本集合。

梯度下降迭代公式：

$$a(k+1) = a(k) + \eta\sum_{y \in Y_M}y$$

最小二乘准则：
误差向量：$e = Ya - b$

平方误差准则函数：

$$J_s(a) = \|e\|^2 = \|Ya-b\|^2$$

伪逆解：

$$a^* = (Y^TY)^{-1}Y^Tb = Y^+b$$

---

6. 决策树

6.1 基本思想

采用自顶向下的递归方法，构造一棵由结点和有向边组成的树。

• 内部结点：表示一个属性或特征
• 叶结点：代表一种类别
• 目标：每个分支节点的样本尽可能属于同一类别（纯度越来越高）

6.2 信息论基础

信息熵：

$$H(D) = -\sum_{c=1}^{C}p_c\log_2 p_c$$

条件熵：

$$H(D|A) = \sum_{n=1}^{N}\frac{|D_n|}{|D|}H(D_n)$$

信息增益（ID3）：

$$G(D,A) = H(D) - H(D|A)$$

增益率（C4.5）：

$$G_{ratio}(D,A) = \frac{G(D,A)}{H(A)}$$

其中 $H(A) = -\sum_{n=1}^{N}\frac{|D_n|}{|D|}\log_2\frac{|D_n|}{|D|}$ 为属性A的固有值。

基尼指数（CART）：

$$\text{Gini}(D) = 1 - \sum_{c=1}^{C}p_c^2 = \sum_{c=1}^{C}\sum_{c' \neq c}p_cp_{c'}$$

属性A的基尼指数：

$$\text{Gini}(D,A) = \sum_{n=1}^{N}\frac{|D_n|}{|D|}\text{Gini}(D_n)$$

6.3 例题（西瓜分类）

数据集（部分）：

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
…	…	…	…	…	…	…	…
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否

计算信息熵：

$$H(D) = -(\frac{8}{17}\log_2\frac{8}{17} + \frac{9}{17}\log_2\frac{9}{17}) = 0.998$$

以属性"色泽"为例计算条件熵：

• 青绿6个（3好3坏）：$H(D^{青绿}) = -(\frac{3}{6}\log_2\frac{3}{6} + \frac{3}{6}\log_2\frac{3}{6}) = 1.000$
• 乌黑6个（4好2坏）：$H(D^{乌黑}) = 0.918$
• 浅白5个（1好4坏）：$H(D^{浅白}) = 0.722$

$$H(D|色泽) = \frac{6}{17} \times 1.000 + \frac{6}{17} \times 0.918 + \frac{5}{17} \times 0.722 = 0.889$$

信息增益：

$$G(D,色泽) = 0.998 - 0.889 = 0.109$$

类似计算：$G(D,纹理) = 0.381$（最大），故选择"纹理"作为根节点划分属性。

6.4 剪枝处理

• 预剪枝：生成过程中，若划分不能带来泛化性能提升则停止划分
  • 优势：降低过拟合风险，减少时间开销
  • 劣势：可能导致欠拟合
• 后剪枝：生成完全树后，自底向上考察，若替换为叶节点能提升泛化性能则剪枝
  • 优势：泛化性能一般优于预剪枝
  • 劣势：训练时间开销大

6.5 连续值处理

对连续属性a，将N个取值排序 $\{a^1, a^2, ..., a^N\}$，候选划分点集合：

$$T_a = \left\{\frac{a^i+a^{i+1}}{2} | 1 \leq i \leq N-1\right\}$$

选择使信息增益最大的划分点：

$$G(D,a) = \max_{t \in T_a} G(D,a,t)$$

---

7. 支持向量机(SVM)

7.1 基本思想

寻找最优分类超平面，使训练集中的点距离分类面尽可能远，即分类间隔(Margin)最大。

7.2 线性可分SVM

优化目标：

$$\min_{w,b} \frac{1}{2}\|w\|^2$$

$$\text{s.t.} \quad t_n(w^Tx_n+b) \geq 1, \quad n=1,...,N$$

拉格朗日函数：

$$L(w,b,a) = \frac{1}{2}\|w\|^2 - \sum_{n=1}^{N}a_n\{t_n(w^Tx_n+b)-1\}$$

对偶问题：

$$\max_a \sum_{n=1}^{N}a_n - \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N}a_na_mt_nt_mk(x_n,x_m)$$

$$\text{s.t.} \quad \sum_{n=1}^{N}a_nt_n = 0, \quad a_n \geq 0$$

KKT条件：$a_n \geq 0$，$t_ny(x_n)-1 \geq 0$，$a_n\{t_ny(x_n)-1\} = 0$

支持向量：$a_n > 0$ 对应的样本（位于间隔边界上）。

7.3 软间隔SVM

引入松弛变量 $\xi_n \geq 0$ 和惩罚参数C：

$$\min_{w,b,\xi} \frac{1}{2}\|w\|^2 + C\sum_{n=1}^{N}\xi_n$$

$$\text{s.t.} \quad t_n(w^Tx_n+b) \geq 1-\xi_n, \quad \xi_n \geq 0$$

7.4 核方法

将样本映射到高维特征空间 $\phi(x)$，核函数：

$$k(x,x') = \phi(x)^T\phi(x')$$

常用核函数：

• 多项式核：$k(x,x') = (x^Tx'+c)^d$
• 高斯(RBF)核：$k(x,x') = \exp(-\frac{\|x-x'\|^2}{2\sigma^2})$
• Sigmoid核：$k(x,x') = \tanh(\kappa x^Tx'+\theta)$

决策函数：

$$y(x) = \sum_{n=1}^{N}a_nt_nk(x,x_n)+b$$

---

8. 神经网络(1)

8.1 MP模型

第i个神经元的输出：

$$y_i = f\left(\sum_{j=1}^{d}w_{ij}x_j - \theta_i\right)$$

其中 $f(\cdot)$ 为激活函数，$\theta_i$ 为阈值。

8.2 激活函数

• 阶跃函数：$f(x) = \begin{cases} 1, & x \geq 0 \\ -1, & x < 0 \end{cases}$
• Sigmoid：$f(x) = \frac{1}{1+e^{-x}}$
• 双曲正切：$\tanh(x) = \frac{e^x-e^{-x}}{e^x+e^{-x}}$
• ReLU：$f(x) = \max(0,x)$

8.3 感知器

感知器学习规则（Hebb规则）：

$$\Delta w_{ij} = \eta x_j y_i$$

或对于监督学习：

$$\Delta w_{ij} = \eta(t_i-y_i)x_j$$

感知器收敛定理：若样本线性可分，感知器学习算法在有限次迭代后收敛。

异或问题：单层感知器无法解决，需要多层感知器（至少一个隐层）。

---

9. 深度学习(1)

9.1 卷积神经网络(CNN)

卷积层：

$$y_{i,j} = \sum_{m}\sum_{n}x_{i+m,j+n} \cdot w_{m,n} + b$$

池化层（以最大池化为例）：

$$y_{i,j} = \max_{m,n \in \text{window}} x_{i+m,j+n}$$

反向传播关键公式：

• 输出层误差：$\delta^L = \nabla_a C \odot \sigma'(z^L)$
• 隐藏层误差：$\delta^l = ((w^{l+1})^T\delta^{l+1}) \odot \sigma'(z^l)$
• 参数梯度：$\frac{\partial C}{\partial w^l} = \delta^l(a^{l-1})^T$，$\frac{\partial C}{\partial b^l} = \delta^l$

9.2 经典网络结构

• LeNet-5：卷积→池化→卷积→池化→全连接
• AlexNet：ReLU+Dropout+GPU并行，5层卷积+3层全连接
• VGGNet：连续3×3小卷积核堆叠，深度16-19层
• ResNet：残差块 $y = F(x,\{W_i\}) + x$，解决梯度消失，可训练上百层

---

10. 深度学习(2)

10.1 循环神经网络(RNN)

隐状态更新：

$$h_t = f(W_{hh}h_{t-1} + W_{xh}x_t + b_h)$$

输出：

$$y_t = g(W_{hy}h_t + b_y)$$

BPTT（基于时间的反向传播）：

$$\frac{\partial L}{\partial W} = \sum_{t=1}^{T}\frac{\partial L_t}{\partial W}$$

梯度问题：长序列下梯度消失/爆炸：

$$\frac{\partial h_T}{\partial h_1} = \prod_{t=2}^{T}W_{hh}^T \cdot \text{diag}(f'(z_t))$$

10.2 LSTM

门控机制：

• 遗忘门：$f_t = \sigma(W_f \cdot [h_{t-1}, x_t] + b_f)$
• 输入门：$i_t = \sigma(W_i \cdot [h_{t-1}, x_t] + b_i)$
• 候选状态：$\tilde{C}_t = \tanh(W_C \cdot [h_{t-1}, x_t] + b_C)$
• 状态更新：$C_t = f_t \odot C_{t-1} + i_t \odot \tilde{C}_t$
• 输出门：$o_t = \sigma(W_o \cdot [h_{t-1}, x_t] + b_o)$
• 输出：$h_t = o_t \odot \tanh(C_t)$

10.3 Transformer

缩放点积注意力：

$$\text{Attention}(Q,K,V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$

多头注意力：

$$\text{MultiHead}(Q,K,V) = \text{Concat}(\text{head}_1,...,\text{head}_h)W^O$$

其中 $\text{head}_i = \text{Attention}(QW_i^Q, KW_i^K, VW_i^V)$

位置编码（正弦余弦）：

$$PE_{(pos,2i)} = \sin(pos/10000^{2i/d_{model}})$$

$$PE_{(pos,2i+1)} = \cos(pos/10000^{2i/d_{model}})$$

前馈网络：

$$\text{FFN}(x) = \max(0, xW_1+b_1)W_2+b_2$$

10.4 自编码机(AutoEncoder)

编码：$h = f(W^{(1)}x + b^{(1)})$
解码：$\hat{x} = g(W^{(2)}h + b^{(2)})$

损失函数（MSE）：

$$L = \frac{1}{N}\sum_{i=1}^{N}\|\hat{x}_i - x_i\|^2$$

10.5 生成对抗网络(GAN)

• 生成器G：$z \sim p_z(z) \rightarrow G(z;\theta_g)$
• 判别器D：$D(x;\theta_d) \in [0,1]$

目标函数（Minimax）：

$$\min_G \max_D V(D,G) = E_{x \sim p_{data}(x)}[\ln D(x)] + E_{z \sim p_z(z)}[\ln(1-D(G(z)))]$$

训练过程：交替优化D和G。

---

11. 聚类

11.1 K均值算法(K-Means)

目标：最小化准则函数

$$J = \sum_{k=1}^{K}\sum_{x_i \in C_k}\|x_i - \mu_k\|^2$$

算法步骤：

1. 随机初始化K个簇中心 $\mu_k$
2. 分配步：$C_k = \{x_i : \|x_i-\mu_k\|^2 \leq \|x_i-\mu_j\|^2, \forall j\}$
3. 更新步：$\mu_k = \frac{1}{|C_k|}\sum_{x_i \in C_k}x_i$
4. 重复2-3直至收敛

K-means++：改进初始化，第n+1个中心选择概率与到已有中心距离平方成正比。

11.2 层次聚类(AGNES)

自底向上聚合：

1. 初始每个样本为一簇
2. 计算簇间距离矩阵
3. 合并距离最近的两个簇
4. 更新距离矩阵，重复2-3直至达到预设簇数

簇间距离度量：

• 最小距离（单链接）：$d_{min}(C_i,C_j) = \min_{x \in C_i, z \in C_j}\|x-z\|$
• 最大距离（全链接）：$d_{max}(C_i,C_j) = \max_{x \in C_i, z \in C_j}\|x-z\|$
• 平均距离：$d_{avg}(C_i,C_j) = \frac{1}{|C_i||C_j|}\sum_{x \in C_i}\sum_{z \in C_j}\|x-z\|$

---

12. 数据降维

12.1 主成分分析(PCA)

将D维数据投影到M维空间($M < D$)，投影方向为协方差矩阵S的特征向量。

最大方差思想：
投影后样本方差：$u_1^TSu_1$，约束 $u_1^Tu_1=1$

拉格朗日函数：$L = u_1^TSu_1 + \lambda_1(1-u_1^Tu_1)$

令偏导为0：$Su_1 = \lambda_1 u_1$

$u_1$ 为S最大特征值对应的特征向量，即第一主成分。

计算步骤：

1. 计算样本均值 $\bar{x}$ 和协方差矩阵 $S$
2. 计算S的特征值与特征向量
3. 将特征值从大到小排列，前M个特征值对应的特征向量构成投影矩阵 $U = [u_1,...,u_M]$
4. 降维：$z_i = U^T(x_i - \bar{x})$

高维数据PCA：当 $D \gg N$ 时，计算 $N \times N$ 矩阵而非 $D \times D$ 矩阵。

12.2 核主成分分析(Kernel PCA)

通过非线性映射 $\phi(x)$ 将数据映射到高维特征空间，再执行PCA。

核矩阵：$K_{ij} = k(x_i,x_j) = \phi(x_i)^T\phi(x_j)$

中心化核矩阵：

$$\tilde{K} = K - 1_NK - K1_N + 1_NK1_N$$

其中 $(1_N)_{ij} = \frac{1}{N}$

对 $\tilde{K}$ 进行特征值分解，取前M个特征值对应的特征向量。

12.3 等距映射(ISOMAP)

保持数据点内在几何性质（测地距离）。

算法步骤：

1. 构造邻域关系图（$\epsilon$邻域或K近邻）
2. 计算图中任意两点间最短路径（Dijkstra或Floyd算法），得到距离矩阵 $D_G$
3. 多尺度分析：将高维数据投影到低维空间，使投影前后距离矩阵相似度最大

12.4 局部线性嵌入(LLE)

保持数据点的原有流形结构。

算法步骤：

1. 寻找每个样本点的K近邻
2. 对每个点用K个近邻线性重建，求权值 $w_{ij}$ 使重构误差最小：

   $$\min_w \sum_{i=1}^{N}\|x_i - \sum_{j}w_{ij}x_j\|^2$$

   约束：$\sum_j w_{ij} = 1$
3. 在低维空间中保持权值不变，最小化：

   $$\min_Y \sum_{i=1}^{N}\|y_i - \sum_{j}w_{ij}y_j\|^2$$

---

13. 集成学习

13.1 多样性度量

对于二分类任务，分类器 $h_i$ 与 $h_j$ 的预测结果联立表：

	$h_i=+1$	$h_i=-1$
$h_j=+1$	a	b
$h_j=-1$	c	d

• 不合度量：$\text{dis}_{ij} = \frac{b+c}{a+b+c+d}$
• Q统计量：$Q_{ij} = \frac{ad-bc}{ad+bc}$
• Kappa统计量：$\kappa = \frac{p_1-p_2}{1-p_2}$
  其中 $p_1 = \frac{a+d}{a+b+c+d}$（一致概率），$p_2 = \frac{(a+b)(a+c)+(c+d)(b+d)}{(a+b+c+d)^2}$（偶然一致概率）

13.2 Boosting

AdaBoost算法：

初始化样本权值分布：$D_1(i) = \frac{1}{N}$

对于 $t=1,...,T$：

1. 基于分布 $D_t$ 训练学习器 $h_t$
2. 估计误差：$\epsilon_t = \sum_{i=1}^{N}D_t(i)\mathbb{I}(h_t(x_i) \neq y_i)$
3. 计算学习器权重：$\alpha_t = \frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}$
4. 更新样本分布：

   $$D_{t+1}(i) = \frac{D_t(i)\exp(-\alpha_t y_i h_t(x_i))}{Z_t}$$

最终分类器：

$$H(x) = \text{sign}\left(\sum_{t=1}^{T}\alpha_t h_t(x)\right)$$

13.3 Bagging与随机森林

Bagging：

1. 对数据集进行T次Bootstrap采样，得到T个训练集
2. 基于每个训练集训练基学习器
3. 分类任务：投票；回归任务：平均

随机森林：

• 以决策树为基学习器
• 样本扰动：Bootstrap采样
• 属性扰动：每个结点随机选择k个属性（推荐 $k=\log_2 d$）再选最优划分
• 最终：投票或平均

---

14. 半监督学习

14.1 基本假设

• 聚类假设：数据存在簇结构，同一簇样本属于同一类别
• 流形假设：数据分布在流形结构上，邻近样本有相似输出值

14.2 自训练(Self-Training)

1. 用已标记样本 $D_l$ 训练初始分类器 $f$
2. 用 $f$ 对未标记样本 $D_u$ 预测，将置信度高的样本及其伪标记加入 $D_l$
3. 重复直至 $D_u$ 为空

14.3 半监督SVM(S3VM)

标准SVM（软间隔）：

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

$$\text{s.t.} \quad y_i(w^Tx_i+b) \geq 1-\xi_i, \quad \xi_i \geq 0$$

S3VM（TSVM）：同时利用标记和未标记样本

$$\min_{w,b,\xi,\hat{y}} \frac{1}{2}\|w\|^2 + C_l\sum_{i=1}^{l}\xi_i + C_u\sum_{j=l+1}^{l+u}\xi_j$$

$$\text{s.t.} \quad y_i(w^Tx_i+b) \geq 1-\xi_i$$

$$\hat{y}_j(w^Tx_j+b) \geq 1-\xi_j, \quad \xi_i,\xi_j \geq 0$$

通过局部搜索迭代调整未标记样本的伪标记，使目标函数下降。

14.4 半监督聚类

约束K均值：

• 必连(must-link)：样本必属于同一簇
• 勿连(cannot-link)：样本必不属于同一簇
• 在聚类过程中确保约束得以满足

约束种子K均值：

• 利用少量有标记样本作为"种子"
• 用种子初始化K个聚类中心
• 迭代更新过程中不改变种子样本的簇隶属关系

---

15. 综合应用

15.1 语音识别

流程：语音波形 → DFT+CNN特征提取 → LSTM声学模型 → CTC/语言模型 → 文本

CTC（Connectionist Temporal Classification）：

• 引入空白字符 $\epsilon$ 处理输入输出长度不一
• 损失函数：所有可能对齐路径概率之和

  $$L = -\ln\sum_{\pi \in \mathcal{B}^{-1}(l)}P(\pi|x)$$

15.2 目标检测（遥感图像）

R-CNN流程：

1. 选择搜索(Selective Search)生成约2000个候选区域(RoI)
2. CNN提取每个RoI的特征向量
3. SVM分类（前景/背景 + 多类目标）
4. 边界框回归修正位置

边界框回归：预测偏移值 $(\Delta x, \Delta y, \Delta w, \Delta h)$

IoU（交并比）：

$$\text{IoU} = \frac{\text{Area of Intersection}}{\text{Area of Union}}$$

15.3 医学影像分析

前列腺癌分级：

• 输入：多分辨率组织切片影像（约1-10亿像素）
• 预处理：分块(256×256) → 有效像素筛选
• 模型：CNN/Transformer提取特征 → 全连接分类
• 集成：对N个块的预测结果投票

损失函数设计：

• 交叉熵 + 均方误差（考虑等级间有序关系）

  $$L = CE(\text{logits}, \text{label}) + \lambda MSE(\sum_i i \cdot \text{logits}[i], \text{label})$$

• 标签平滑(Label Smoothing)：

  $$\text{label}' = (1-\epsilon)\cdot\text{one-hot} + \epsilon / K$$

加权交叉熵（处理类别不平衡/不同风险）：

$$L = -\sum_i w_i \cdot y_i \cdot \ln(\hat{y}_i)$$

15.4 AI for Science

盘古气象大模型：

• 3D Transformer架构，同时捕捉时间、空间和变量维度特征
• 短期、中期天气预测首次全面超过传统NWP模型

分子结构生成(MolGAN)：

• 生成器：从潜在空间采样生成分子图
• 判别器：区分真实分子和生成分子
• 奖励网络：强化学习优化特定理化性质

---

附录：生成式模型 vs 判别式模型

维度	生成式模型	判别式模型
建模对象	联合分布 $p(x,y)$ 或 $p(x|y)p(y)$	后验概率 $p(y|x)$
优点	信息丰富、增量学习、可合成缺失数据	类间差异清晰、学习简单、性能较好
缺点	学习过程复杂、为分布牺牲分类性能	不能反映数据特性、需要全部数据
代表算法	Naive Bayes、GMM、HMM、GAN	逻辑回归、SVM、KNN、CRF、Boosting

关系：由生成模型可以得到判别模型，但由判别模型得不到生成模型。

$$p(y|x) = \frac{p(x|y)p(y)}{\sum_{y'}p(x|y')p(y')}$$