机器学习复习

ML 期末突击

方差与偏差

靶心与飞镖：一个绝佳的比喻

想象一下你正在玩射飞镖，目标是靶心（Bullseye）。靶心就是我们想要预测的真实值。你射出的每一支飞镖，都是一次模型的预测。

我们用不同的训练数据子集训练出的不同模型，就像你一次次地投掷飞镖。

1. 低偏差，低方差 (Low Bias, Low Variance) - 理想情况

   • 表现：所有的飞镖都紧密地集中在靶心周围。
   • 解读：模型既准确（低偏差）又稳定（低方差）。每次训练出的模型都能准确预测。这是我们的终极目标。

2. 高偏差，低方差 (High Bias, Low Variance) - 欠拟合

   • 表现：所有的飞镖都紧密地聚集在一起，但离靶心很远。
   • 解读：模型很稳定，每次预测的结果都差不多（低方差），但它系统性地出错了，离真实值很远（高偏差）。模型太简单了，比如用一条直线去拟合一个二次曲线的数据。

3. 低偏差，高方差 (Low Bias, High Variance) - 过拟合

   • 表现：飞镖围绕着靶心散布得很开，没有聚集在一起。
   • 解读：平均来看，预测是围绕真实值的（低偏差），但每次预测的结果都非常不稳定（高方差）。模型学到了太多训练数据里的“噪声”，导致换一点数据，预测结果就天差地别。它在训练集上表现完美，但在测试集上一塌糊涂。

4. 高偏差，高方差 (High Bias, High Variance) - 最差情况

   • 表现：飞镖散布得到处都是，而且离靶心很远。
   • 解读：模型既不准确，也不稳定。这通常是一个设计得很差的模型，完全没有学到任何规律。

数据取样

1. 保持法（留出法）
   将给定数据随机地划分到两个集合中（即训练集和测试集）
   • 优点：简单
   • 缺点：训练效果受到划分影响很大
2. 随机子采样（保持法变种）
   使用k次保持法，然后准确率取k次的平均值
   • 但是每个数据用于训练的次数不是确定的
3. k折交叉验证
   将总的数据均分为k份，然后验证k次，每次使用不同的1折充当测试集，其余全部充当训练集
4. 留一法
   k折交叉验证的特殊情况，k值取为总的数据集中的样本数
   • 优点：训练集只比数据集少一个样本，训练较准确
   • 缺点：对于数据集较大的情况，计算量较大，分的次数也多

5. 自助法
   对于大小为$|D|$的数据集，随机有放回的均匀采样$|D|$次，余下没有选中的样本构成测试集

   • 优点：从少量数据中产生了多种多样的样本分布，对集成学习的好处很大
   • 缺点：改变了样本的分布，会产生偏差

混淆矩阵

     |__预测P__|__预测N__|
真实P |   TP   |   FN   |
真实N |   FP   |   TN   |

• TP: 真实为P，预测也为P，意为真阳性
• TN: 真实为N，预测也为N，意为真阴性
• FN: 真实为P，预测却为N，意为假阴性
• FP: 真实为N，预测却为P，意为假阳性

查全与查准

• Precison: 预测为阳性的例子中有多少是真实阳性
  • $precison = \frac{TP}{TP + FP}$
• Recall: 真实为阳性的例子中有多少被预测出来
  • $recall = \frac{TP}{TP + FN}$

度量单位

• $F_1$度量
  • 调和平均数度量
  • $\frac{1}{F_1} = \frac{1}{2}\times(\frac{1}{precison} + \frac{1}{recall})$
• $F_\beta$度量
  • $\beta$调和平均
  • $\frac{1}{F_\beta} =\frac{1}{\beta^2 + 1}\times\frac{1}{precison} + \frac{\beta^2}{\beta^2 + 1}\times\frac{1}{recall}$
    • $\beta = 1$, 调和平均
    • $\beta > 1$, 查全率影响更大，系统倾向于宁杀错不放过（不漏报）
    • $\beta < 1$, 查准率影响更大，系统倾向于无罪推定（不误报）

代价矩阵

• 同理对于代价矩阵
  • $Cost_{FN} > Cost_{FP}$，对于相同情况下错误率，则要求查全率高
  • $Cost_{FP} > Cost_{FN}$，对于相同情况下错误率，则要求查准率高

往年考题

1. TP、TN、FP、FN的概念
2. 准确率($\frac{TP}{TP+FP}$)与召回率($\frac{TP}{TP+FN}$)
3. F1度量的概念

贝叶斯决策

对于所有n种可能需要判别的情况$\omega_1 … \omega_n$，若给定某种场景（分布）x,请你判别当前的情况$\omega$为哪种？

对于任意一种可能情况$p(\omega_i\mid x) = \frac{p(x\mid\omega_i)\times p(\omega_i)}{p(x)}$, 或者写为$\frac{p(x\mid\omega_i)\times p(\omega_i)}{\sum_{j=1}^n{p(x\mid\omega_j)\times p(\omega_j)}}$

最小错误率贝叶斯

$\omega = \omega_i$,当且仅当$p(\omega_i\mid x) = \max_{j=1}^n{p(\omega_j\mid x)}$，这样就能保证在每个x点错误率都是最小的，总体而言错误率就最小了

实现方案

• 对于每个$\omega_i$，通过上面公式计算得到$p(\omega_i\mid x)$，取最大值对应的$i$值

最小损失贝叶斯

已知有n种决策（一般与情况是一一对应的），且第i中决策中第j中情况带来的风险为$\lambda(\alpha_i, \omega_j)$，那么我们永远选择风险较低的一种决策

且一般情况下，我们构造损失函数时，某种决策$\alpha_i$必然对应着某种情况$\omega_j$，使得$\lambda(\alpha_i, \omega_j) = 0$，此时我们认为该决策与该情况是一一对应的

实现方案

• 对于每种决策$\alpha_i$, 我们计算其期望风险$R(\alpha_i\mid x) = \sum_{j=1}^n{\lambda(\alpha_i, \omega_j)\times p(\omega_j\mid x)}$
• 取期望风险最小的$i$值

朴素贝叶斯

对于已有的样本空间$D$，对于一种抽样$x$，我们认为其是若干独立同分布的特征构成的，记为$x_i$,故$p(x) = p(x_1)\times p(x_2)\times … p(x_n)$，每种抽样与对应唯一一种情况$\omega_i$，即$x_1x_2x_3…x_n -> \omega_i$，我们通过样本空间的频率估计$p(w_i)$与$p(x_i\mid \omega_i)$

此时出现某种新的取样分布，记为$x_{new}$，我们同样将其拆解为上面的特征$x_1x_2…$，此时计算$p(\omega_i\mid x_{new})$即转化为$p(\omega_i)\times\frac{p(x_1\mid \omega_i)\times p(x_2\mid \omega_i)…}{p(x_1)\times p(x_2)…}$，随后运用最小错误率贝叶斯做出决策

由于最先给定的样本空间是确定的，我们可以适当化简为$\omega_i = p(\omega_i) \times \prod_{j=1}^n{p(x_j\mid \omega_i)}$

对于某种情况$\omega_i$，不存在对应$x_j$特征，即$p(x_j\mid \omega_i) = 0$,我们可以采取各种平滑方式，例如拉普拉斯平滑

往年考题

我们有一个数据集，包含三个类别：A、B、C。已知以下信息：

1. 类别的先验概率：

   • P(A) = 0.3
   • P(B) = 0.5
   • P(C) = 0.2

2. 给定类别下特征 X 的条件概率：

   • P(X|A) = 0.4
   • P(X|B) = 0.2
   • P(X|C) = 0.4

3. 决策风险矩阵（损失矩阵）：

   | 决策 \ 真实 | A | B | C |
   |——————-|——-|——-|——-|
   | A | 0 | 5 | 2 |
   | B | 4 | 0 | 4 |
   | C | 1 | 4 | 0 |

需要解决的问题：

1. 基于最小错误率准则的贝叶斯决策。
2. 基于最小风险准则的贝叶斯决策。

1.最小错误率准则的贝叶斯决策

最小错误率准则的目标是选择后验概率最大的类别。后验概率可以通过贝叶斯公式计算：

$ P(\text{class}|X) = \frac{P(X|\text{class}) \cdot P(\text{class})}{P(X)} $

由于 $ P(X) $ 对所有类别是相同的，因此可以忽略，只需比较分子部分：

$ P(\text{class}|X) \propto P(X|\text{class}) \cdot P(\text{class}) $

计算每一类的后验概率（未归一化）：

• 对于类别 A：
  $ P(A|X) \propto P(X|A) \cdot P(A) = 0.4 \times 0.3 = 0.12 $

• 对于类别 B：
  $ P(B|X) \propto P(X|B) \cdot P(B) = 0.2 \times 0.5 = 0.10 $

• 对于类别 C：
  $ P(C|X) \propto P(X|C) \cdot P(C) = 0.4 \times 0.2 = 0.08 $

比较三个值：

• $ P(A|X) \propto 0.12 $
• $ P(B|X) \propto 0.10 $
• $ P(C|X) \propto 0.08 $

最大的后验概率对应类别 A，因此基于最小错误率准则的决策是选择类别 A。

2.最小风险准则的贝叶斯决策

最小风险准则的目标是选择期望风险最小的类别。期望风险的计算公式为：

$ R(\alpha_i|X) = \sum_{j} \lambda(\alpha_i|\omega_j) \cdot P(\omega_j|X) $

首先需要计算归一化的后验概率。前面已经计算出未归一化的后验概率：

$ P(A|X) \propto 0.12 $
$ P(B|X) \propto 0.10 $
$ P(C|X) \propto 0.08 $

归一化因子 $ P(X) $ 为：

$ P(X) = P(X|A)P(A) + P(X|B)P(B) + P(X|C)P(C) = 0.12 + 0.10 + 0.08 = 0.30 $

因此，归一化的后验概率：

$ P(A|X) = \frac{0.12}{0.30} = 0.4 $
$ P(B|X) = \frac{0.10}{0.30} \approx 0.333 $
$ P(C|X) = \frac{0.08}{0.30} \approx 0.267 $

接下来计算每个决策的期望风险：

1. 决策为 A：
   $ R(A|X) = \lambda(A|A)P(A|X) + \lambda(A|B)P(B|X) + \lambda(A|C)P(C|X) $
   $ R(A|X) = 0 \times 0.4 + 5 \times 0.333 + 2 \times 0.267 $
   $ R(A|X) = 0 + 1.665 + 0.534 = 2.199 $

2. 决策为 B：
   $ R(B|X) = \lambda(B|A)P(A|X) + \lambda(B|B)P(B|X) + \lambda(B|C)P(C|X) $
   $ R(B|X) = 4 \times 0.4 + 0 \times 0.333 + 4 \times 0.267 $
   $ R(B|X) = 1.6 + 0 + 1.068 = 2.668 $

3. 决策为 C：
   $ R(C|X) = \lambda(C|A)P(A|X) + \lambda(C|B)P(B|X) + \lambda(C|C)P(C|X) $
   $ R(C|X) = 1 \times 0.4 + 4 \times 0.333 + 0 \times 0.267 $
   $ R(C|X) = 0.4 + 1.332 + 0 = 1.732 $

比较三个期望风险：

• $ R(A|X) = 2.199 $
• $ R(B|X) = 2.668 $
• $ R(C|X) = 1.732 $

最小的期望风险对应类别 C，因此基于最小风险准则的决策是选择类别 C。

1. 最小错误率准则的贝叶斯决策：选择类别 A。
2. 最小风险准则的贝叶斯决策：选择类别 C。

线性模型

对于一种回归模型，满足$y_i = \sum x_{ij} * w_j$，则称$j$维向量$\omega = [\omega_1, \omega_2 … \omega_j]^T$称为线性系数，即$y_i = \omega^T X_i$,若同时提供有n组如此的样本，则可以一同写为一个方程组$X\omega = Y$, $X = [X_1, X_2 … X_n]^T$, $Y = [y_1, y_2, … y_n]^T$

对于大部分线性方程，我们i难以获得精确解，由某个近似解$\omega_i$可以得到一个近似的向量，该向量不属于与$Y$同一个线性空间，$\hat{Y} = X\omega_i$。通过两个向量的距离，我们得到相应的损失结果
$J(\omega_i) = (\hat{Y} - Y)^T(\hat{Y} - Y)$

我们要求损失的结果最小，可以采用两种方法，直接法省略，即通过求导直接找出$\omega_i$

梯度下降法

使用迭代更新的方法，知道$\omega$逐渐收敛至特定值
$\omega$<-$ \omega - \alpha\nabla J(\omega)$

线性分类器

对于若干样本，$x_1, … x_n$,我们通过线性参数$\omega$将其映射为$y_1, … y_n$，即$y = \omega^T x + \omega_0$，也可以写为标准形式$\hat{x} = \left[\begin{matrix} 1\\x_1\\x_2\\ …\\x_n \end{matrix}\right]$，$\hat{\omega} = \left[\begin{matrix}\omega_0\\ \omega_1\\ \omega_2 \\ …\\ \omega_n \end{matrix}\right]$，由此得到$y = \hat{\omega}^T\hat{x}$

对于二分类问题，我们规定一个$y_0$，若对于某个$x$，其值$\hat{\omega}^T\hat{x}$
而对于使用线性模型做分类问题，我们同样引入准则函数$J(\omega)$，要求该损失最小

Fisher准则

对于分类类内集中，类间分散。对于类别$\omega_1, …, \omega_n$，则可以定义

• 类内散度矩阵$S_i = \sum_{x_i\in\omega_i} (x_i - \overline{x_i})(x_i - \overline{x_i})^T$
• 类间散度矩阵$S_b = \sum_{i\not ={j}} (\overline{x_i} - \overline{x_j})(\overline{x_i} - \overline{x_j})^T$
• 总类散度矩阵为$S_\omega = \sum S_i$或者$\sum p(\omega_i)\times S_i$
• $\hat{S_i} = \sum_{y_i, x_i\in\omega_i} (y_i - \overline{y_i})(y_i - \overline{y_i})^T$
• $\hat{S_\omega} = \sum \hat{S_i}$

同理我们可以定义$J(\omega) = \frac{\sum (\overline{y_i} - \overline{y_j})^2}{\hat{S_\omega}}$

通过化简我们可以得到$J(\omega) = \frac{\omega^TS_b\omega}{\omega^TS_\omega\omega}$

得到$\omega^* = S_\omega^{-1}(\overline{x_i} - \overline{x_j})$（对于二分类）

感知机准则

对于若干样本$y_1, …, y_n$, 存在$a$, 对于类别$\omega_1$中的样本有$a^Ty > 0$,对于$\omega_2$中类别有$a^Ty < 0$
构建规范化样本$y^{‘} = \begin{cases}y, a^Ty > 0\\ -y, a^Ty < 0\end{cases}$ ，则满足了$a^Ty^{‘} > 0$，此时我们进行迭代训练

定义$J(a) = \sum_{a^Ty^{‘} < 0} -a^Ty^{‘}$，则我们需要循环对a进行更新$a^{k+1} = \begin{cases}a^{k}, {a^{k}}^{T}y^{‘} >0\\ a^{k} - \nabla J(a^k), {a^{k}}^Ty^{‘} < 0\end{cases}$
每次迭代我们只使用一个样本$y_i^{‘}$，则可以将$\nabla J(a^k) = \sum -y^{‘} = -y_i^{‘}$

则$a^{k+1} = a^{k} + y_i$

给定训练集，和初始$a_0$，我们按照类将样本化为增广样本，随后规范化，（不规范化其实也行，理论上线性可分的情况下感知机是会收敛的）

最小二乘准则

同理我们对于样本进行规范化处理，最好的投影方向依然是$a^Ty^{‘} > 0$的情况，但是此时我们不再使用迭代的方式寻找收敛，而是假设某一个全是正数的列向量$b = \left[\begin{matrix}b_1 \\ b_2 \\ … \\ b_n\end{matrix}\right]$，且要求$a^Ty_i^{‘} = b_i$有解（或是近似解），写为矩阵形式$Ya = b$,$Y = \left[\begin{matrix}{y_1^{‘}}^T\\ {y_2^{‘}}^T\\ …\\ {y_n^{‘}}^T\end{matrix}\right]$

该方程组一般而言是没有准确解的，所以我们使用最小二乘法找近似解即$J(a) = (Ya - b)^T(Ya - b)$
即$2Y^T(Ya - b) = 0$，解的$a = (Y^TY)^{-1}Y^Tb$
或者使用迭代，如下

往年考题

感知机准则

1. 规范化增广向量：

   • Class 1（直接使用）：
     • $ y_1 = \begin{pmatrix} 1 \\ -2 \\ 2 \end{pmatrix} $
     • $ y_2 = \begin{pmatrix} 1 \\ -2 \\ -2 \end{pmatrix} $
   • Class 2（取反）：
     • $ y_3 = \begin{pmatrix} -1 \\ -2 \\ -1 \end{pmatrix} $
     • $ y_4 = \begin{pmatrix} -1 \\ -2 \\ 1 \end{pmatrix} $

2. 初始化权重：
   $ a(1) = \begin{pmatrix} 0 \\ 2 \\ 1 \end{pmatrix} $

3. 迭代过程：

   • 第一次迭代：
     • $ a(1)^T y_1 = -2 \leq 0 $ → 更新：
       $ a(2) = a(1) + y_1 = \begin{pmatrix} 1 \\ 0 \\ 3 \end{pmatrix} $
     • $ a(2)^T y_2 = -5 \leq 0 $ → 更新：
       $ a(3) = a(2) + y_2 = \begin{pmatrix} 2 \\ -2 \\ 1 \end{pmatrix} $
   • 验证：
     • $ a(3)^T y_3 = 1 > 0 $
     • $ a(3)^T y_4 = 3 > 0 $
     • $ a(3)^T y_1 = 8 > 0 $
     • $ a(3)^T y_2 = 4 > 0 $
     • 所有样本分类正确，停止。

概念

1. Fisher、感知机、最小二乘准则基本思想
   • Fisher准则通过投影（降维）去寻找一个超平面或者直线，使得样本中所有的点投影后达到，类内散度小、类间散度大。Fisher准则最大化它们的比值来实现最优分类
   • 感知机是一个在线算法，每次根据一个样本来决定是否调整边界（即向着能将该样本分类正确的方向调整），直到所有样本都被分类正确。感知机准则收敛的前提是样本本身线性可分
   • 最小二乘准则将回归的问题应用于分类，对于一个分类问题，我们不仅要求该线能够将样本集合分开（某类大于0、某类小于0），我们还要求其得到的值尽可能靠近我们预设的目标值
2. SVM与线性模型的区别
   • SVM集中考虑到的是距离决策边界较近的“最难区分”的点，对于其他点不予关心；而线性模型追求全局的拟合，每一个点都会对决策边界造成影响
   • SVM集中考虑的是支持向量的损失，较远的非支持向量对决策边界完全不起作用，贡献的Loss为0；而线性模型一般而言考虑的是全局的点，即便是离决策边界远且被分类正确的点，也会贡献微小的Loss
   • SVM对于离群点和噪声的容忍度也更好
   • （非线性SVM），采用了核函数的SVM理论上可以拟合任意决策边界；而线性模型一般只能做线性决策边界
3. 感知机与SVM异同
   • 感知机强调可分，其最终任务只是找到一个可以完成分类的决策边界
   • SVM则强调分的最开、最好，其最终任务是找到一个线性决策边界使得该边界距离两类最远，也即分得最开

支持向量机

硬间隔

对于若干样本组成的集合，我们不仅要分类，还需要分的最好，也就是将它们分的最开
假设目前有若干样本$x_1, x_2, …, x_n$，且假设它们是线性可分的，我们可以得到某个线性参数的集合

$$<w_1, b_1>, <w_2, b_2> ...$$

且满足

$$\begin{cases}w^Tx + b > 0, x \in w_1 \\ w^Tx+b < 0, x\in w_2\end{cases}$$

可以看到该集合中的任何一个组合都可以看成是对原样本集合的线性分割

现在我们不妨对线性参数进行规范化,即同乘$t_n, t_n=\begin{cases}1, w^Tx_n+b>0 \\ -1, w^Tx_n+b<0\end{cases}$，已知某点到超平面的距离写为$\frac{t(w^Tx_n+b)}{||w||}$，我们需要使得该间隔最大，我们不妨假设距离该超平面距离最短的点$x_i, t_i(w^Tx_i + b)= 1$，则原式写为$max \frac{1}{||w||}, t(w^Tx+b)\ge1$,即也可以写为$min \frac{1}{2}||w||^2$

使用拉格朗日乘子法，将该问题变为

$$L(w,b,a) = \frac{1}{2}||w||^2 - \sum a_n(t_n(w^Tx_n + b) - 1), \frac{d(L(w, b ,a))}{dw} = 0, \frac{d(L(w, b, a))}{db} = 0$$

条件化为$\sum a_nt_nx_n = w, \sum a_nt_n = 0$
代入化简获得其对偶问题

$$L(w, b, a) = max( \sum a_n - \frac{1}{2}\sum_i\sum_j a_ia_jt_it_jx_i^Tx_j), a_n\ge 0,\sum a_nt_n = 0$$

进行求解后，可以获得$a_1, a_2, …, a_n$的解，最后进行验证，由于对偶问题等价性需要满足一定条件，最后条件是

$$a_n(t_n(w^Tx_n + b) - 1) = 0$$

对于支持向量，也即$t_nw^Tx_n - 1 = 0$的点，$a_n > 0$
对于非支持向量，也即$t_nw^Tx_n - 1 > 0$的点，$a_n = 0$
也就是该边界只与距离它最近的点（支持向量）有关！

例题如下

1. 由其拉格朗日对偶问题为$max (\sum a_n - \sum\sum a_ia_jt_it_jx_i^Tx_j)$
2. 代入所有点，变个号后得到

$$\min_{\alpha} \frac{1}{2} (18\alpha_1^2 + 25\alpha_2^2 + 2\alpha_3^2 + 42\alpha_1\alpha_2 - 12\alpha_1\alpha_3 - 14\alpha_2\alpha_3) - (\alpha_1 + \alpha_2 + \alpha_3)$$

1. 使用$\sum a_nt_n =0条件$

$$s(\alpha_1, \alpha_2) = 4\alpha_1^2 + \frac{13}{2}\alpha_2^2 + 10\alpha_1\alpha_2 - 2\alpha_1 - 2\alpha_2$$

1. 求偏导解最小值，发现极值点不满足约束$\alpha_i \ge 0$
2. 寻找可行域内解
   如果 α₁ = 0，s(0, α₂) = (13/2)α₂² - 2α₂，在 α₂ = 2/13 时取最小值 -2/13。
   如果 α₂ = 0，s(α₁, 0) = 4α₁² - 2α₁，在 α₁ = 1/4 时取最小值 -1/4
3. 求得所有 α值
4. 通过非0，使用支持向量计算 b

软间隔

由于硬间隔只能划分完全可分的样本，对噪声响应过于敏感，于是我们可以采取某种方式减少离群点对模型的影响。
假设目前存在若干近似可分参数,采取类似硬间隔的方案，我们知道规定容忍变量$\xi_n = |t_n - (w^Tx_n + b)|$

• $\xi_n =0$, 即这是我们选取的边界（该点是硬分隔的支持向量）
• $0\lt \xi_n \lt 1$，边界附近（认为包含绝大多数点）
• $\xi_n \gt 1$, 离群点，对其惩罚力度大
  则目前问题变为

$$min(\frac{1}{2}||w||^2 + C\sum\xi_i), t_n(w^Tx_n+b)\ge 1-\xi_n$$ $$L(w,b,a,\mu) = \frac{1}{2}||w||^2 - \sum a_n(t_n(w^Tx_n+n)-1+\xi_n) + C\sum\xi_n - \sum\mu_n\xi_n$$

最后的互补条件为

$$a_n(t_n(w^Tx_n+b) -1 + \xi_n) = 0$$ $$\mu_n\xi_n = 0$$

此时支持向量不再只有硬边界上的点，还包括硬边界中的所有点、错分的点

非线性问题

将某些线性不可分问题进行升维，然后再运用线性分类器

例如某映射$\phi: m \rightarrow n, m\lt n$，则对样本$x_1, x_2, …$的分类问题可以转为$\phi(x_1), \phi(x_2), … \phi(x_n)$的分类问题

$$y = w^Tx+b \rightarrow y = w^T\phi(x)+b$$ $$y = \sum a_nt_nx_i^Tx+b\rightarrow y = \sum a_nt_nk(x_i, x)+b$$ $$k(x_i,x) = \phi(x_i)^T\phi(x)$$

一些常用的核函数例如

$$k(x_1, x_2) = x_1^Tx_2\text{，线性核}$$ $$k(x_1, x_2) = (<x_1, x_2> + R)^d\text{，多项式核}$$ $$k(x_1, x_2) = \exp{-\frac{||x_1-x_2||^2}{\sigma^2}}\text{，高斯核}$$ $$k(x_1, x_2) = tanh(\beta_1x_1^Tx_2+\beta_0)\text{，sigmod核}$$

往年考题

概念

1. SVM的基本原理
   • 即找到某个决策边界，将两类样本分得最开（距离决策边界最远），不仅要成功地将数据分开，而且要尽可能“漂亮地”分开，找到那个最鲁棒、最安全的分类边界
2. SVM模型表达式
   • 前面对于$w$的表达式
3. 核函数的作用
   • 将低维空间的样本映射到高维空间，使得在低维空间线性不可分的样本在高维空间变得线性可分；由此间接地解决非线性决策边界的分类问题
4. 如何处理离群点和噪声
   • 引入松弛变量$\xi = |t_n - w^Tx-b|$惩罚某些样本违背决策边界，对于错分的样本给予适当的惩罚，而不是硬区分
   • 使用鲁棒性较强的核函数（RBF高斯核等）进行映射，将线性不可分问题转化为高维空间的线性可分问题，由此间接地去除或减少噪声和离群点的影响
5. 如何解决非线性问题
   • 通过核函数，将低维线性不可分的样本转化为高维空间的线性可分样本
6. 与决策树比较优缺点
   • 优点
     • 泛化能力强：通过最大化间隔降低了过拟合的风险，尤其适合小样本数据
     • 非线性处理：通过核技巧可以隐式地映射到高维空间，一般可以处理复杂的非线性决策问题
   • 缺点
     • 难解释：对于分类问题的解释不如决策树直观容易理解
     • 计算开销大：对于大数据集的性能不如决策树
     • 对于缺失值和参数敏感，而决策树可以通过分裂准则进行自动特征选择

决策树

ID3

基于信息熵增益最大的部分分支
信息量

• 表示x事件发生的信息量
• $I(x) = -log_2p(x)$

信息熵

• 事件集合中信息量的均值
• $H(x) = \sum_i h(x_i) = \sum_ip(x_i)I(x_i)$

经验信息熵

• 样本D中共有c类，每类的占比为$p_c$(频率代替概率)，则样本集合D的经验信息熵，熵值越低则该样本集越纯
• $H(D) = \sum_i-p_c log_2p_c$

条件信息熵

• H(Y|X)表示在X已知的情况下Y的不确定性
• $H(Y | X) = \sum_ip_iH(Y | X=x_i)$

经验条件熵

• 假设当前样本集合D 共有c类，每一类有$D_c$个样本，属性a有不同的取值$\{a_1, a_2,…, a_n\}$，每一类中属性为n的样本数为$D_c^n$，则D的经验条件熵定义为

$$H(D | a) = \sum_{i=1}^n \frac{|D^n|}{|D|}H(D^n)$$

信息增益

• 若目前样本存在一个属性a，则a对于样本D的信息增益$G(D,a) = H(D) - H(D | a)$
  

C4.5

定义增益率为

$$G_{ratio}(D, a)=\frac{H(D | a)}{H(a)}$$ $$H(a) = \sum_i^n -p_ilog_2p_i$$

• $H(a)$称为a属性的固有值

CART

基尼指数

• 直观反映了从数据集中随机抽取两个样本，其类别不一致的概率；因此，Gini(D)越小，则数据集D的纯度越高
• $Gini(D) = 1 - \sum (\frac{|D_c|}{|D|})^2$

对属性a的基尼指数

• $Gini(D,a) = \sum_{i=1}^n p_i Gini(D^n)$

剪枝

预剪枝

• 决策树生成过程中，对每个节点在划分前进行估计，若划分不能带来决策树泛化性能提升，则停止划分，并将该节点设为叶节点
• 优点：降低了过拟合的风险，并且显著减少了决策树的训练时间开销和测试时间开销
• 缺点：有欠拟合的风险

后剪枝

• 先利用训练集生成决策树，自底向上对非叶节点进行考察，若将该叶节点对应子树替换为叶节点能带来泛化性能提升，则将该子树替换为叶节点
• 优点：测试了所有分支，比预剪枝决策树保留了更多分支，降低了欠拟合的风险，泛化性能一般优于预剪枝决策树
• 缺点：训练开销大

泛化性能

• 使用当前决策树对于某个样本进行考察，判断分类正确的成功率（一般也可以直接采用整个训练集）

预剪枝训练步骤

• 不划分：标记为目前集合中类别最多的类
• 划分：依据属性进行分叉
• 通过整个训练集比较两种方式的泛化性能

后剪枝训练步骤

• 训练一颗决策树
• 从底部非叶节点开始考察，比较泛化性能

连续变量决策

• 对于某个可以连续取值的属性a，我们采取二分的方法
• 假设该属性在训练集上有n个取值，我们将其从小到大排列$a_1, a_2, …, a_n$，并设置n-1个划分点$t_i = \frac{a_i + a_{i+1}}{2}$
• 同时$G(D,a) = max G(D,a,t_i) = max (H(D) - H(D | a, t_i))$，我们选取能够最大增益的划分点$t_i$

缺失值处理

• 无缺失属性集合$\hat{D}$
• 每个样本对应的权重$\omega_i$
• 无缺失属性占有率$\rho = \frac{\sum_{x_i\in\hat{D}}\omega_i}{\sum_{x_i\in D}\omega_i}$
• 无缺失样本c类比例$\hat{p_c} = \frac{\sum_{x_i\in\hat{D_c}}\omega_i}{\sum_{x_i\in\hat{D}}\omega_i}$
• 无缺失样本中$a_n$取值为n比例$\hat{r_{n}} = \frac{\sum_{x_i\in\hat{D^n}}\omega_i}{\sum_{x_i\in\hat{D}}\omega_i}$

信息增益

• $G(D,a) = \rho\times G(\hat{D}, a) = \rho\times(H(\hat{D})-\sum\hat{r_n}H(\hat{D^n}))$
• $H(D) = \sum -\hat{p_c}log_2{\hat{p_c}}$

步骤

• 若样本x在属性a上的取值已知：则将x划入与其取值对应的子节点，且样本权值保持$\omega_i$
• 若样本x在属性a上的取值未知：则将x划入所有子节点，且其在与属性值对应的子节点中的权值根据属性a上已知的样本的比例调整为$\hat{r_n}\omega_i$

  往年考题

  计算

  

1. ID3决策树计算

   概念

2. 防止决策树过拟合的两个方法
   • 预剪枝，在决策树决定是否因为某个属性而“分叉”形成子树时，考察其泛化性能是否变得更好，如果没有改变甚至变得更差则直接设置为叶子节点
   • 后剪枝，建成完整的一颗决策树后，自叶子节点向上考察，同样是比较形成子树是否对泛化性能有提升，如果没有则设置为叶子节点
3. ID3算法缺陷以及解决方案
   • 信息增益偏好取值多的属性：改用信息熵增益比来代替
   • 无法处理连续值：C4.5采用二分法
   • 无法处理缺失值：C4.5采用概率分配的方法
   • 容易过拟合：采用剪枝或者C4.5
4. id3和c4.5的区别
   • ID3采用信息增益，而C4.5采用信息增益比。消除了信息增益偏好取值多的属性
   • C4.5采用二分法支持连续值，而ID3不支持连续值
   • C4.5采用概率分配的方式支持缺失值，而ID3不支持缺失值
   • C4.5采用额外的悲观剪枝，而ID3没哟剪枝操作
   • C4.5运算效率较低，ID3的运算效率较高

神经网络

逻辑回归

名为逻辑回归，实则也是分类问题。由于回归问题得到的信息量天生比分类问题多，我们可以采取适当的方式对回归问题的值进行阐释得到离散值，这样就可以解决分类问题了。逻辑回归则通过$\sigma$函数($Softmax$函数)对线性回归的结果进行映射，以达到应对复杂概率形式的目的

不妨假设当前样本集是一个多分类问题，若有$\omega_1, \omega_2, …, \omega_n$类，目前我们观测到该样本集有$s_i$个$\omega_i$

那么通过贝叶斯进行分析，对于目前某种情况$x$，我们将其分为$\omega_i$类的概率为

$$p(\omega_i| x) = \frac{p(x|\omega_i)\times p(\omega_i)}{\sum p(x|\omega_j)\times p(\omega_j)}$$

我们将其化为对称形式

$$p_i = \frac{e^{a_i}}{\sum e^{a_j}}$$ $$a_i = ln(p(x|\omega_i)\times p(\omega_i))$$

接下来我们做$n$次线性回归拟合$a_i$，即

$$a_i = w_i^Tx, x\in\omega_i$$

同时对于$\omega_i$中所有的样本，出现该情况的概率采用最大似然估计则为

$$\prod_{x_i\in\omega_i}{\hat{p_i}^{||\omega_i||}}$$ $$\hat{p_i} = \frac{e^{w_i^Tx_i}}{\sum e^{w_i^Tx_i}}$$

则对于样本集同理有

$$t_{ij} = \begin{cases}1, x_i\in\omega_j\\ 0, x_i\notin\omega_j\end{cases}$$ $$L(\omega_1, ...\omega_n) = \prod_{x_i}{\prod_{j}{\hat{p_i}^{t_{ij}}}}$$

最后我们最大化似然概率即我们得到我们需要的所有$\omega$

其中我们采用的$p_i = \frac{e^{a_i}}{\sum e^{a_j}}$为$Softmax$函数，即处理输出为概率的函数
对于二元问题我们有更加优化的方案$sigmoid$函数

$$p_i = \frac{e^{a_i}}{\sum e^{a_j}}$$ $$p_i = \frac{1}{1 + e^{a}}, a = ln\frac{a_i}{a_j}$$

所以我们实际上只需要求一元线性回归问题就可以完成二元的逻辑回归了

感知器

一个感知器接收多个输入$x_1, …, x_n$，每个输入对应一个权重$\omega_1, …,\omega_n$，感知器接收到的总输入为$\omega^Tx$，每个感知器有一个阈值$\theta$，感知器的状态$a = \sum_{i=1}^n\omega^Tx_i - \theta$,若使用增广向量的写法则为$\hat{x} = \left[\begin{matrix}\theta\\x_1\\x_2\\ …\\x_n\end{matrix}\right], \hat{\omega} = \left[\begin{matrix}-1\\ \omega_1\\ \omega_2\\ …\\ \omega_n\end{matrix}\right]$

多输出感知器，对于上述例子，只有一个计算层计算，此时我们通过一组输入也可以得到多组输出例如

上述感知器实际上还是在解决线性可分问题，对于线性不可分问题，我们可以通过叠加感知器的层数来拟合曲线？（理论上任意多层任意多输出的感知器，可以拟合一个任意曲面、进行任意地分类）

BP反向传播

不妨对于简单的三层神经网络（输入层、隐层、输出层），我们分别将其记为 Layer 0, Layer 1, Layer 2。

• $a_j^{(l)}$: 第 $l$ 层第 $j$ 个神经元的状态。
• $y_j^{(l)}$: 第 $l$ 层第 $j$ 个神经元的激活输出。
• $w_{ji}^{(1)}$: 从 Layer 0 (输入层) 的第 $i$ 个神经元到 Layer 1 (隐层) 的第 $j$ 个神经元的权重。
• $w_{kj}^{(2)}$: 从 Layer 1 (隐层) 的第 $j$ 个神经元到 Layer 2 (输出层) 的第 $k$ 个神经元的权重。
• $h(\cdot)$ 代表隐层的激活函数。
• $\sigma(\cdot)$ 代表输出层的激活函数。

正向传递

对于输入层，每个输入我们设为 $\mathbf{x} = [x_0, x_1, …, x_{N_i}]^T$ (增广形式，其中 $x_0=1$) 。我们视其为第0层的输出，即 $y_i^{(0)} = x_i$。

对于隐层 (Layer 1) 的第 $j$ 个神经元：

$$a_j^{(1)} = \sum_{i=0}^{N_i} w_{ji}^{(1)} y_i^{(0)}$$ $$y_j^{(1)} = h(a_j^{(1)})$$

对于输出层 (Layer 2) 的第 $k$ 个神经元：
(为简化，我们假设隐层输出 $y^{(1)}$ 也被增广，增加一个 $y_0^{(1)}=1$ 的偏置项)

$$a_k^{(2)} = \sum_{j=0}^{N_j} w_{kj}^{(2)} y_j^{(1)}$$ $$y_k^{(2)} = \sigma(a_k^{(2)})$$

由于隐层的输出是输出层的输入，我们可以写为：

$$y_k^{(2)} = \sigma\left(\sum_{j=0}^{N_j} w_{kj}^{(2)} h\left(\sum_{i=0}^{N_i} w_{ji}^{(1)} y_i^{(0)}\right)\right)$$

这是正向传播的计算视角，展示了信号如何从多个隐层神经元汇集到一个输出层神经元：

现在我们假设对单个样本的误差 $E = \frac{1}{2}\sum_{k=1}^{N_k} (y_k^{(2)} - t_k)^2$，其中 $t_k$ 代表输出层第 $k$ 个神经元的真实值。

反向传播

接下来使用梯度下降的方法依次反向传播。

我们记 $\delta_k^{(2)} = \frac{\partial E}{\partial a_k^{(2)}}$ 为输出层的误差信号。
同理对于隐层我们记 $\delta_j^{(1)} = \frac{\partial E}{\partial a_j^{(1)}}$ 为隐层的误差信号。

计算隐层的误差信号 $\delta_j^{(1)}$:

$$\delta_j^{(1)} = \frac{\partial E}{\partial a_j^{(1)}} = \left( \sum_{k=1}^{N_k} \frac{\partial E}{\partial a_k^{(2)}} \frac{\partial a_k^{(2)}}{\partial y_j^{(1)}} \right) \frac{\partial y_j^{(1)}}{\partial a_j^{(1)}}$$

这里的 $\frac{\partial a_k^{(2)}}{\partial y_j^{(1)}} = w_{kj}^{(2)}$。代入后得到：

$$\delta_j^{(1)} = \left( \sum_{k=1}^{N_k} \delta_k^{(2)} w_{kj}^{(2)} \right) h'(a_j^{(1)})$$

它表明，隐层 (Layer 1) 的误差 $\delta_j^{(1)}$ 是由所有来自输出层 (Layer 2) 的误差 $\delta_k^{(2)}$ 通过它们之间的连接权重 $w_{kj}^{(2)}$ 加权求和得到的，也即多个输出层神经元指向一个隐层神经元

这是反向传播的计算视角，展示了误差如何从所有输出层神经元被收集回一个隐层神经元：

梯度计算

对于输出层 (Layer 2) 的权重 $w_{kj}^{(2)}$ 的梯度为：

$$\frac{\partial E}{\partial w_{kj}^{(2)}} = \frac{\partial E}{\partial a_k^{(2)}} \frac{\partial a_k^{(2)}}{\partial w_{kj}^{(2)}}$$ $$= \delta_k^{(2)} y_j^{(1)}$$

将 $\delta_k^{(2)}$ 展开：

$$= (y_k^{(2)} - t_k) \sigma'(a_k^{(2)}) y_j^{(1)}$$

对于隐层 (Layer 1) 的权重 $w_{ji}^{(1)}$ 的梯度为：

$$\frac{\partial E}{\partial w_{ji}^{(1)}} = \frac{\partial E}{\partial a_j^{(1)}} \frac{\partial a_j^{(1)}}{\partial w_{ji}^{(1)}}$$ $$= \delta_j^{(1)} y_i^{(0)}$$

将 $\delta_j^{(1)}$ 展开：

$$= \left( \sum_{k=1}^{N_k} \delta_k^{(2)} w_{kj}^{(2)} \right) h'(a_j^{(1)}) y_i^{(0)}$$

当然，对于多个隐层的情况，隐层的$\delta$表达式是递归的，且几乎是完全一致的

往年考题

BP反向传播推导

深度学习

CNN

卷积神经网络，与传统的FNN不同，神经元的概念被隐藏在每个层内

• 以该二维输入为例，我们通过哈达玛积得到一个结果$\left[\begin{matrix}1,0,0\\ 0,0,0\\ 0,0,0\end{matrix}\right]$，求和后，接下来经过阈值和激活函数得到特征图的某个像素点
• 通过多次卷积操作，逐步提取高级特征。通过反向传播从高到低修正

梯度下降方法

• SGN（随机梯度下降），每次选取一个样本
  • 缺点：引起梯度震荡；相似样本造成冗余运算
• BGN（批处理梯度下降），每次选取所有样本
  • 缺点：计算量达；容易陷入局部最优
• MBGN（小批处理梯度下降），每次选取样本中的部分
  • 高效；收敛稳定

步频

• 自适应学习率
  • $\eta^k = \alpha\eta^{k-1}$
  • $\eta^k = \eta^{0} e^{-kt}$
• Adagrad
  • 对于以往更新的频繁的参数，其可能已经接近最优值附近了，我们采用小步长；而对于以往更新稀疏的参数，我们加大其学习的步长，鼓励其探索附近的随机值
  • $\eta^{\tau} = \frac{1}{\sqrt{\sum_{t=1}^\tau\Delta E^2(w^t) + \epsilon}}\eta^{0}$
• Adadelta
  • 对Adagrad的一个优化，防止最后的梯度的更新近似于0，只记录最近一段时间的梯度变化和
  • $\eta^{\tau} = \frac{\sqrt{w^{\tau -1} + \epsilon}}{\sqrt{\sum_{t=1}^\tau\Delta E^2(w^t) + \epsilon}}\eta^{0}$
• Momentum
  • 吸取物理学中的动量概念，每次更新的方向还继承了上一次的方向，使得其保持了一种“惯性”
• Adam
  • Adagrad+Momentum
    

梯度

• 如果每层的梯度都小于1，连乘后梯度会迅速趋近于0，这就是梯度消失 (Vanishing Gradients)。导致靠近输入的浅层网络几乎学不到东西
• 如果每层的梯度都大于1，连乘后梯度会变得极其巨大，这就是梯度爆炸 (Exploding Gradients)。导致训练不稳定，直接崩溃
• ReLU激活函数
  • f(x) = max(0, x)。它在正区间的导数恒为1。这意味着在激活的神经元上，梯度可以畅通无阻地向后传播，不会因为连乘而衰减，极大地缓解了梯度消失问题。
• Batch Normalization (BN)
  • 在每一层的激活函数之前，强行将该层的输出（送入激活函数前的数据）进行归一化，使其均值为0，方差为1
  • 稳定数据分布：确保每一层的输入都处于一个比较理想的范围内，极大地加速了训练收敛
  • 缓解梯度问题：通过稳定数据分布，间接抑制了梯度消失和爆炸
  • 自带正则化效果：由于归一化是基于mini-batch的统计量，给训练带来了噪声，类似于Dropout
• 残差网络 (ResNet)
  • 引入“捷径连接 (Shortcut Connection)”。允许信息（和梯度）可以“跳过”一层或多层，直接从前层流向后层。
  • 梯度有了一条“高速公路”可以直接传回浅层，从根本上解决了深度网络中的梯度消失问题，使得训练成百上千层的网络成为可能。

正则化

• Dropout
  • 在训练的每一步，随机地“关闭”（使其输出为0）网络中的一部分神经元
  • 强制网络学习冗余表示：因为任何一个神经元都可能随时“消失”，网络不能依赖于任何一个特定的神经元，必须学会用多种方式、多种特征组合来做出判断，从而变得更加鲁棒
  • 模型集成：可以看作是每次都在训练一个不同的、更小的子网络，最后将这些成千上万个子网络的结果进行平均，是一种非常高效的模型集成方法
• 数据增强 (Data Augmentation)
  • 通过对原始训练图片进行旋转、裁剪、缩放、色彩抖动等操作，无中生有地创造出更多样化的训练数据。这是最直接、最有效的防止过拟合的方法之一
• L1/L2 正则化 (权重衰减)：在损失函数中加入权重的范数作为惩罚项，限制权重值不要过大
• 早停 (Early Stop)：在训练过程中监控验证集的性能，当验证集性能不再提升时就停止训练

RNN

通过记录状态，来处理序列化数据,这类数据的特点是，元素之间有明确的先后顺序，并且当前元素可能依赖于前面的元素

RNN的隐状态是一个动态更新的、高维的数字指纹。它不存储人类可读的标签，而是将序列中对完成最终任务有用的所有句法、语义和上下文信息，压缩编码成一个数学向量，为最终的决策提供了一个全面而丰富的“状态总结”

长期依赖

• RNN的训练算法叫做通过时间的反向传播 (Backpropagation Through Time, BPTT)。可以把它想象成：先把RNN按时间步完全“展开”成一个非常深的、权重共享的FNN，然后在这个展开的网络上执行标准的反向传播
• 也是由于RNN“展开”得到的FNN层数过多，且对于时间跨度大的层，其展开包含的权重是相同的。一旦该权重过大或者过小就会发生梯度爆炸或者梯度消失的问题

LSTM

通过细胞单元的状态记录序列数据，同时通过细胞状态这一单独的数据进行反向传播，解决了长期依赖的问题

• “遗忘门”
• 先前输出（即隐藏状态）的信息和来自当前输入的信息经sigmoid函数激活，输出介于0-1之间。越接近0意味着越容易被忘记，越接近1则越容易被保留
• $f_t = \sigma(W_f\cdot[h_{t-1}, x_t] + b_f)$

• “输入门”
• 决定哪些新信息应该被存放到细胞状态，将先前输出和当前输入经sigmoid函数，计算出哪些值更重要；同时，把先前输出和当前输入给tanh函数，生成候选状态；
• $i_t = \sigma(W_i\cdot[h_{t-1}, x_t] + b_i)$
• $\hat{C_t} = tanh(W_C\cdot[h_{t-1}, x_t] + b_C)$

• “状态更新”
• 先前cell状态和遗忘门输出的向量点乘，由于越不重要的值越接近0，
  原隐藏状态中不重要的信息被丢弃；新的输出，与当前cell的候选状态相加，输出更新后的cell状态
• $C_t = f_t\otimes C_{t-1} + i_t\otimes\hat{C_{t}}$

• “输出门”
• 先前输出与当前输入经过sigmod，决定哪一部分cell状态需要被输出; 状态经过tanh后，与输出门相乘，只输出想要输出的。
• $h_t = o_t\otimes tanh(C_t)$
• $o_t = \sigma(W\cdot[h_{t-1}, x_t]+b_o)$

更多深度学习框架

Transformer

完全摒弃RNN的循环结构，也抛弃CNN的卷积结构，整个模型完全基于一种叫做“注意力机制 (Attention Mechanism)”的模块来构建，注意力机制可以直接计算序列中任意两个位置之间的依赖关系，无论它们相距多远。一个词可以直接“关注”到句子开头的另一个词，距离不再是障碍

• 查询 (Query, Q)：代表当前我们正在处理的这个词，它要去“查询”与其他词的关系。
• 键 (Key, K)：代表序列中所有其他的词，它们是“被查询”的对象，用来和Query进行匹配。
• 值 (Value, V)：也代表序列中所有其他的词。它包含了这些词自身的真正信息。通常K和V是成对出现的。
• 自注意力机制：Query, Key, 和 Value 都来自同一个输入序列。这意味着，序列中的每个词都会去计算与 自己所在序列中所有其他词（包括自己） 的注意力关系。这使得模型能够捕捉到句子内部复杂的语法和语义依赖，比如代词指代、主谓关系等

Transformer模型在宏观上沿用了经典的编码器-解码器 (Encoder-Decoder) 架构
….

AutoEncoder

(to be continued…)

GAN

(to be continued…)

聚类

对于m个元素$x_1, x_2, …, x_m$，我们将其分为k类$C_1, C_2, …, C_k$，同时获得聚类的簇标记向量$\lambda = \left[\lambda_1, \lambda_2, …, \lambda_m\right], \lambda_i\in\left[1,2,…,k\right], x_i\in C_{\lambda_i}$

外部指标

• 与标准模型划分的聚类进行比较，若标准模型化为 $$C_1^{*}, C_2^{*}, ..., C_k^{*}$$ $$\lambda^*= \left[\lambda_1^*,\lambda_2^*, ..., \lambda_m^*\right], \lambda_i^*\in\left[1,2,...,k\right], x_i\in C_{\lambda_i^*}^*$$

首先我们定义

$$a = |SS|, SS = \{(x_i, x_j), \lambda_i=\lambda_j, \lambda_i^*=\lambda_j^* \}$$ $$b = |SD|, SD = \{(x_i, x_j), \lambda_i=\lambda_j, \lambda_i^*\not =\lambda_j^* \}$$ $$c = |DS|, DS = \{(x_i, x_j), \lambda_i\not =\lambda_j, \lambda_i^*=\lambda_j^* \}$$ $$d = |DD|, DD = \{(x_i, x_j), \lambda_i\not =\lambda_j, \lambda_i^*\not =\lambda_j^* \}$$

内部指标

• 模型内自己比较，不与外部模型比较
  首先我们定义

$$avg(C) = \frac{2}{|C|(|C|-1)}\sum_{1\le i\le j\le |C|}dist(x_i, x_j)$$ $$diam(C) = \max_{1\le i\le j\le |C|} dist(x_i, x_j)$$ $$d_{min}(C) = \max_{x_i\in C_i, x_j\in C_j} dist(x_i, x_j)$$ $$d_{cen}(C) = dist(\mu_i, \mu_j), \mu = \frac{1}{|C|}\sum_{1\le i\le |C|}x_i$$

K-means

通过最小化$E=\sum_{i=1}^k{\sum_{j=1}^{|C_i|}}{|x_j-\mu_i|^2}$来划分数据集，伪代码如下

K-means++

假设已选取了n个初始聚类中心，在选取第n+1个中心时：距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心，即聚类中心离得越远越好

Kernel K-means

采用和SVM一样的核函数机制，将当前样本先映射到高维空间在采用K-means进行切分

ISODATA

同样是在K-means算法的基础上的改进，增加了类的“合并”与“分裂”。例如，当两类中心差小于某阈值则合并为一类；一个类中标准差或者样本数量大于某阈值则分裂为两类；一个类中的样本数量小于某阈值则取消该类

AGNES

自底而上的层次聚类算法，初始时将样本集中的每个样本都看成是一个簇，随后每次合并选择两个距离最近的簇合并

$$d_{min}(C_i, C_j) = min_{x_i\in C_i, x_j\in C_j}{dist(x_i,x_j)}$$ $$d_{max}(C_i, C_j) = max_{x_i\in C_i, x_j\in C_j}{dist(x_i,x_j)}$$ $$d_{avg}(C_i, C_j) = \frac{1}{|C_i||C_j|}\sum_{x_i\in C_i}\sum_{x_j\in C_j}{dist(x_i,x_j)}$$

EM

(to be continued…)

往年考题

概念

1. K-means算法流程
   • 先从样本集合中随机选取k个节点作为初始值，随后对于每个未被分类的样本，我们将其归纳进距离中心点欧式距离最近的一类，并重新更新中心点，直到所有样本都已经被分类成功
2. 使用K-means解决实际聚类问题
   • 略
3. K-means算法及其不足
   • 需要预先指定K
   • 对于初始中心选择敏感
   • 仅使用与凸状簇
4. K-means与GMM高斯模型的异同
5. 简述EM算法的执行流程
6. em算法e步和m步分别对应流程里的哪一步

降维

PCA

最大化方差思想

• 即通过投影使得样本之间的方差最大（方差大则保留了信息，方差小的部分维度可能是噪声，所以需要去除方差小的维度）

以降到一维距离为例，使用的降维向量为$\mu$,$\mu^T\mu=1$，可知降维后的方差为$\frac{1}{N}\sum |\mu^Tx_i - \mu^T\overline{x}|^2$，化简可得

$$\mu^T S\mu, S=\frac{1}{N}\sum (x_i - \overline{x})(x_i - \overline{x})^T$$

原式即求$max{\mu^T S\mu}, \mu^T\mu=1$，由拉格朗日乘子

$$L(\mu, \lambda) = \mu^T S\mu + \lambda(1 - \mu^T\mu)$$

求导后可得$S\mu = \lambda\mu$，带回则求$max{\lambda}$
故可知$\lambda$是协方差矩阵最大的特征值

降至m维同理，降维向量为$\mu_1, \mu_2, …\mu_m$，我们使用贪心策略，先找到投影到一维的最优向量$\mu_1$同上，然后在与$\mu_1$无关的空间中继续第二个维度$\mu_2$，以此类推找到第m维

最小化均方误差思想

• 即使降维后的数据在原空间的重建与原数据的均方误差最小

以降低至m维为例，我们首先做基变换，使用另一套正交基底$\mu_1, \mu_2, …\mu_d$, $\mu_i\mu_j=\delta_{ij}$，并从中选取m个基底作为我们降维使用的向量，由基底变换公式知

$$x = \mu z, \mu = \left[\begin{matrix}\mu_1, \mu_2, ...\mu_d\end{matrix}\right]$$ $$z^T = x^T\mu$$ $$x = \sum(x^T\mu_i)\mu_i$$

由于重建我们仅有特异的m个方向，对于剩余d-m个方向我们不妨使用相同的数量

$$\hat{x_n} = \sum_{i=1}^{m}{z_{ni}\mu_i} + \sum_{i=m+1}^{d}{b_i\mu_i}$$

则我们准则为

$$J(\mu) = \sum|x_n - \hat{x_n}|^2$$

关于$z_{ni}, b{i}$导数置零得

$$z_{ni} = x_n^T\mu_i$$ $$b_{i} = \overline{x}^T\mu_i$$

原式化简为

$$|x_n-\hat{x_n}| = \sum_{i=m+1}^d((x_n^T -\overline{x_n}^T)\mu_i)\mu_i$$ $$J(\mu) = \frac{1}{N}\sum_{n=1}^{N}\sum_{i=m+1}^d{|(x_n^T-\overline{x}^T)\mu_i\mu_i}|^2, \mu_i^T\mu_i = 1$$ $$J(\mu) = \sum\mu_i^T S \mu_i$$

同上得$\mu_i$取最小的d-m个特征值对应的特征向量。
故我们映射的子空间，取最大的m个特征值对应的特征向量，与最大方差思想相同

PCA高维数据处理

解决维度灾难问题，若d维空间极大，标准PCA需要先计算协方差矩阵dxd维，对于计算和存储都是灾难

对于d维空间数据，我们有n个样本（n << d），则我们定义nxd维的矩阵$X = \left[\begin{matrix}x_1-\overline{x}, x_2-\overline{x}….\end{matrix}\right]^T$,则原矩阵$S = n^{-1}X^TX$
则原问题转化为

$$n^{-1}X^TX\mu = \lambda\mu$$ $$n^{-1}XX^T\nu = \lambda\nu, \nu = X\mu$$

则问题转变为求$XX^T$该nxn维矩阵的特征值，维度降低

$$\mu = \frac{1}{\sqrt{n\times\lambda}}X^T\nu$$

IsoMap

基于流形假设的降维

• 在高维空间中，样本点可能分布在一个弯曲的流形上，我们应该用它们在流形上的“真实”距离（测地距离），而不是空间中的直线距离（欧氏距离）来进行降维。

1. 构造邻近关系图

   • 目标：构建一个能近似表示数据点所在流形结构的图 G = (V, E)。
   • 方法：对每一个数据点 xᵢ，找到它的“邻居”。连接方式有两种：
     • ε-邻域：将 xᵢ 与其欧氏距离小于 ε 的所有点相连。
     • K-近邻 (KNN)：将 xᵢ 与其距离最近的 K 个点相连（这是更常用的方法）。
       边的权重：如果两个点是邻居，它们之间边的权重就是它们的欧氏距离 d(xᵢ, xⱼ)；如果不是邻居，则距离为无穷大。

2. 计算最短路径

   • 目标：估算任意两点之间的测地距离。Isomap假设，在邻近关系图上，任意两点之间的最短路径长度可以很好地近似它们在流形上的测地距离。
   • 方法：使用经典的图算法，如 Dijkstra 或 Floyd-Warshall 算法，计算图中所有点对之间的最短路径，从而得到一个包含所有点对测地距离的矩阵 D_G。

3. 多维尺度分析

   • 目标：找到一个低维空间，使得数据点在该空间中的欧氏距离与我们上一步计算出的测地距离 D_G 尽可能地保持一致。
   • 方法：这一步本质上是应用了经典的多维尺度分析（MDS）技术。它通过对距离矩阵 D_G 进行特征分解（PPT第36页的公式），找到一个能最好地保留这些距离关系的低维坐标表示。
     

LLE

基于流形假设的降维

• “局部线性，全局非线性”。它假设每个数据点都可以由其近邻点线性重构出来，并且这个线性重构关系（权重）在降维后应该保持不

1. 寻找邻居并计算重构权重

   • 前提假设：数据所在的低维流形在局部是线性的
   • 步骤：
     • 对每个数据点 xᵢ，找到它的 K 个最近邻点
     • 计算一组重构权重 Wᵢⱼ，使得 xᵢ 可以被其邻居 xᵢⱼ 线性表示，并且重构误差 ||xᵢ - Σⱼ Wᵢⱼ xᵢⱼ||² 最小。同时，权重和必须为1 (Σⱼ Wᵢⱼ = 1)
     • 关键：这个权重 W 矩阵描述了数据在高维空间中的局部几何结构

2. 在低维空间中保持权重并求解

   • 学习目标：找到每个数据点在低维空间中的坐标 yᵢ，同时保持第一步中得到的局部线性关系不变。
   • 方法：最小化在低维空间中的重构误差 Σᵢ ||yᵢ - Σⱼ Wᵢⱼ yᵢⱼ||²。这里的权重 W 是已知的（上一步已求出），未知的是低维坐标 Y。
   • 求解：这个问题可以转化为一个特征值分解问题。最终的低维坐标由特定矩阵 M 的最小的几个非零特征值对应的特征向量构成。

往年考题

PCA & LDA

PCA与LDA的基本思想，它们之间的联系与区别

1. PCA（主成分分析）

• 核心思想：
  通过正交变换将原始数据投影到一组新的基（主成分）上，使得投影后的数据方差最大化，从而保留最重要的信息。
• 数学本质：
  对数据的协方差矩阵进行特征值分解，选择前 $ k $ 个最大特征值对应的特征向量作为主成分方向。
• 目标：
  无监督降维，去除冗余特征，保留数据的主要变化模式。

2. LDA（线性判别分析）

• 核心思想：
  在投影时，最大化类间距离（不同类别中心的分离度），同时最小化类内距离（同一类别数据的紧凑性）。
• 数学本质：
  通过广义特征分解优化类间散度矩阵 $ S_b $ 和类内散度矩阵 $ S_w $ 的比值（Fisher准则）。
• 目标：
  有监督分类，找到能最好区分类别的投影方向。

联系

1. 均为线性降维方法：通过投影变换将数据映射到低维空间。
2. 均依赖特征分解：PCA分解协方差矩阵，LDA分解 $ S_w^{-1}S_b $。
3. 可结合使用：例如先通过PCA降维去噪，再用LDA优化分类。

区别
| 维度 | PCA | LDA |
|—————————|—————————————————|—————————————————|
| 监督性 | 无监督（无需标签） | 有监督（依赖标签） |
| 优化目标 | 最大化方差 | 最大化类间/类内散度比 |
| 降维限制 | 可自由选择维度 | 最多降至 $ C-1 $ 维（$ C $ 为类别数） |
| 适用场景 | 通用降维、可视化 | 分类任务的特征提取 |
| 数据假设 | 对数据分布无严格要求 | 假设各类服从高斯分布且同协方差 |

PCA推导

1. 最大方差推导
2. 最小均方误差推导

PCA使用

给定五个二维点，将其降至一维

• A: (2, 3)
• B: (3, 5)
• C: (4, 4)
• D: (5, 6)
• E: (6, 7)

1. 中心化数据：

• 计算均值：$ \mu_x = 4 $, $ \mu_y = 5 $
• 中心化后：
  • A’: (-2, -2)
  • B’: (-1, 0)
  • C’: (0, -1)
  • D’: (1, 1)
  • E’: (2, 2)

2. 计算协方差矩阵：(这里采用了统计学的无偏估计，除以n-1而不是n，但是没区别)
$ \text{Cov} = \begin{bmatrix} 2.5 & 2.25 \\ 2.25 & 2.5\end{bmatrix} $

3. 计算特征值和特征向量：

• 特征值：$ \lambda_1 = 0.25 $, $ \lambda_2 = 4.75 $
• 主成分方向（对应 $ \lambda_2 $）：
  $ \mathbf{v} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} $

4. 投影到主成分方向：
$ \text{Projection} = X_{\text{centered}}^T \mathbf{v} $

• A: $-2\sqrt{2}$
• B: $-\frac{\sqrt{2}}{2}$
• C: $-\frac{\sqrt{2}}{2}$
• D: $\sqrt{2}$

• E: $2\sqrt{2}$

• A: $-2\sqrt{2}$ ≈ -2.828

• B: $-\frac{\sqrt{2}}{2}$ ≈ -0.707
• C: $-\frac{\sqrt{2}}{2}$ ≈ -0.707
• D: $\sqrt{2}$ ≈ 1.414
• E: $2\sqrt{2}$ ≈ 2.828

  集成学习

考虑二分类问题$y\in \{-1, +1\}$，以及各个学习器$h_i$，若每个学习器的错误率都为$\epsilon$,若各个学习器的错误率一致且采用voting方式决出是否正确，即

$$P(h_i(x) \not ={f(x)}) = \epsilon$$ $$H(x) = sgn(\sum h_i(x))$$

同理，得到整个集成学习器的失误率

$$P(H(x)\not ={f(x)}) = \sum_{k=0}^{\lfloor\frac{T}{2}\rfloor}{\left(\begin{matrix}T \\ k\end{matrix}\right)(1-\epsilon)^k\epsilon^{T-k}}$$ $$\le exp(-\frac{1}{2}T(1-2\epsilon)^2)$$

多样性

$m = a+b+c+d$
不合度量

• 展示不一致的指标$d = \frac{b+c}{m}$

相关系数

• $\rho_{ij} = \frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}}$

Q-统计量

• $Q_{ij} = \frac{ad-bc}{ad+bc}$

k-统计量

• $\kappa = \frac{p_1-p_2}{1-p_2}$
• $p_1$一致概率
  • $p(h_i=h_j)$
  • $p_1 = \frac{a+d}{m}$
• $p_2$偶然一致概率
  • $p(h_i=1)p(h_j=1)+p(h_i=-1)p(h_j=-1)$
  • $p_2 = \frac{(a+b)(a+c)+(c+d)(b+d)}{m^2}$

数据样本扰动(采样)

输入属性扰动(随机子空间)

输出表示扰动

• 通过改变标记（输出），使得机器整个学习目标发生了一定的变化
  

串行化方法(Boosting)

AdaBoost

• 自适应调整样本的属性(例如权重等)
  

并行化方法(Bagging)

Bagging算法

• 通过自助取样取样达到改变训练集特征，由此降低方差
  
  
  RF算法（Bagging变体）
• 选取多棵决策树，对于每棵决策树，训练过程中属性集合选取为原来的随机子集（部分属性作为冗余信息暂时忽略），由此得到的各个决策树都大不相同，随机森林泛化性能强
  

往年考题

概念

1. 随机森林算法的原理与特点
   • 随机森林是一种基于Bagging (Bootstrap Aggregating) 思想的集成学习 (Ensemble Learning) 方法，其核心是构建一个由多棵决策树组成的“森林”，并通过集体投票来决定最终的分类结果。它的“随机性”体现在两个层面，这也是它与普通Bagging方法的关键区别。
     • 样本扰动 (行抽样) -> 构建不同数据集
       • 这是通过 自助采样法 (Bootstrap Sampling) 实现的。假设原始训练集有 N 个样本，我们进行 N 次有放回的随机抽样，构建出一个大小为 N 的新样本子集。这个过程重复 T 次（T 是森林中树的数量），我们就得到了 T 个不同的样本子集。
     • 属性扰动 (列抽样) -> 构建不同决策树
       • 在决策树的每个节点需要进行分裂时，不是从全部 m 个特征中寻找最优分裂点，而是先从这 m 个特征中随机选择一个大小为 k 的子集 (k < m)，然后再从这个子集中选择最优的特征进行分裂。
   • 特点
     • 同时通过属性扰动和样本扰动
     • 算法简单，逻辑清晰
     • 性能强大
2. 简述两种个体学习器的集成方法（Boosting、Bagging、Stacking）
   • Bagging：通过并行训练多个模型，并将其结果组合起来
     • 采样：自助采样，获得多种分布不一的数据集，有利于降低整体的方差
     • 并行训练，对于每个数据集并行地训练一个学习器
     • 结合：采用硬投票或者软投票的方式
   • Boosting：串行训练一系列学习器，每个学习器在前一个基础上更加完善，降低偏差
     • 采样：序列采样，通过重赋值或者重采样的方案，每次训练学习器都集中前面的错误，使得降低了整体的偏差
     • 串行训练，每次训练完学习器后，通过调整采样，再训练下一个学习器
     • 结合：通过加权结合，越优秀的学习器权重越大
3. 集成学习的原理
   • 通过结合多个不同的学习器，达到比个体更好的泛化性能。这依赖于两个基石————个体学习器的准确性与个体学习器的多样性。准确性只不能比随机猜测的学习器性能还要差；多样性指各个学习器需要存在差异
4. 介绍AdaBoost和Random Forest的串行与并行
   • 类似Boosting和Bagging的区别，同2
5. 两种方法Boosting和Bagging，模型的采样，结构，输出是什么样的
   • 同2