## Preface 当第一次接触黑盒的时候，你的脑子就会变成黑盒。 第一次学这些东西的时候，应该还是 Andrew Ng 在 coursera 那一个非常通俗的 ML，没有微积分基础，也没有什么概率论的基础，故而对大部分算法的理解存在于：我有一个多元函数，参数未知，遂变成最大似然估计问题。剩下的都是技巧了。 于是如果不懂，当作一个黑盒了解起输入输出和功能即可。不可置否的是，这种方法对于快速学习新东西非常有效果。但一旦深入，该补的功课还是一样都少不了。 已经是彻彻底底的 Midterm 了，再不 review 之前的内容，期末等着挂科吧。 ## 3-Supervised Learning I ### 3.1 Logistic Regression 任务：**分类（Classification）**。接下来首先讨论二分类。 实际上模型通过 activation function输出的是一个概率，比如说 Sigmoid: $$ \sigma(x) = P(y=1|x;\theta) = \frac{1}{1 + e^{-\theta^T}x} $$ - **决策边界（Decision Boundary）**：当 $\theta^Tx = 0$ 时分割两类。 #### 设计 loss function 当我们要衡量预测好不好时，理想的损失函数也应该与**概率预测**相匹配，而不是MSE。如果用 MSE 的话，例如：$J(\theta) = \frac{1}{2m} \sum (h_{\theta}(x_i) - y_i)^2$，存在的问题是： - Sigmoid 是非线性的，导致 **损失函数非凸（non-convex）**，优化时容易卡在局部最小值。 - 从概率角度看，它也不是在最大化正确分类的概率。 因此，我们要设计一个新的 loss function。从概率建模角度出发，我们希望模型能最大化样本出现的概率（最大似然估计）： $$ L(\theta) = \prod_{i=1}^{m} P(y_i|x_i;\theta) $$ 取 log： $$ \log L(\theta) = \sum_{i=1}^{m} [y_i \log h_{\theta}(x_i) + (1 - y_i) \log (1 - h_{\theta}(x_i))] $$ 最大化这个“对数似然”就等价于最小化它的负数： $$ J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} [y_i \log h_{\theta}(x_i) + (1 - y_i) \log (1 - h_{\theta}(x_i))] $$ 这就是 **Cross Entropy Loss（交叉熵损失）**。 #### Multiclass classification - **One-vs-All** 策略：对每个类别分别训练一个分类器。 - 预测时选择概率最大的类别。 #### ### Regularization - 目的：**防止过拟合**。 - 在代价函数中加入惩罚项, *i.e.*： $$ J(\theta) = J(\theta) + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2 $$ - 调节参数 $\lambda$ 的大小可平衡**偏差（Bias）\**与\**方差（Variance）**。 注意，此时梯度更新公式也要加上这一项： $$ \theta_j := \theta_j - \alpha \frac{\partial J(\theta)}{\partial \theta_j} - \alpha \frac{\lambda}{m}\theta_j $$ ### 3.2 Suppor vector machine 这个之前真没学过，因此详细写一下 #### Motivation  分类任务也可以视为找到一个“面”，可以把各个类隔离开。具体地，这个“面”： > Hyperplane，超平面，是n维欧氏空间中，[余维度](https://zh.wikipedia.org/wiki/餘維數)为1的[子空间](https://zh.wikipedia.org/wiki/子空間)[[1\]](https://zh.wikipedia.org/wiki/超平面#cite_note-1)。即超平面是 $n$ 维空间中的 $n-1$维的子空间。 具体的，SVM的目标是：找到一个能把两类样本分开的**最优超平面**，并使得两类之间的“间隔（margin）”最大。 - 直觉上：它不像逻辑回归那样关心“概率”，而是关心“边界离样本多远”。 - 只有**最靠近边界的样本点**（即“支持向量”）对模型有影响。 假如我们有 Training data: $\{(\vec{x_1}, y_1) \dots (\vec{x_n}, y_n)\}$，我们的目标是找到一个 Hyperplane: $w^Tx + b = 0$ 满足： $$ \begin{align} w^Tx_i+b \geq 1, & y_i = +1 \\ w^Tx_i+b \leq -1, & y_i = -1 \\ \end{align} $$ 合并写成： $$ y_i(w^Tx_i + b) \geq 1 $$ ### Design 超平面定义： $$ \mathcal{H} = \{x \mid w^T x + b = 0\} $$ 对于任意一个点 **x**，它到超平面 **H** 的距离为： $$ d = \frac{|w^T x + b|}{\|w\|} $$ 个最靠近超平面的点（各一类）之间的距离就是“间隔”： $$ \gamma(w, b) = \min_{x \in D} \frac{2|w^T x + b|}{\|w\|} $$ 注意到有 scale invariance: $$ \gamma(\beta w, \beta b) = \gamma(w, b) $$ 所以直接可以令：$2|w^Tx+b| = 1$，故有： $$ \gamma = \frac{2}{||w||} $$ 要让间隔最大化，相当于让$||w||$ 最小化。约束：$\forall i, y_i(w^Tx_i+b) \geq 1$ 所以目标函数： $$ \min_{w,b} \frac{1}{2} ||w||^2 $$ 可用拉格朗日乘数法解，具体结果见另附说明。 ## 3.3 Support Vector Machine II ### Soft Margin 目的：让 SVM 能处理非线性可分或含噪声的数据。 引入“松弛变量”（Slack Variable） $\xi_i$，允许部分样本违背约束： $$ y_i(w^T x_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0 $$ 新目标函数： $$ \min_{w, b, \xi} \ \frac{1}{2}\|w\|^2 + C \sum_i \xi_i $$ 其中 $C$：平衡项，用于控制“间隔大小”与“误分类惩罚”。 - $C \uparrow$：重视分类准确率； - $C \downarrow$：重视大间隔、容忍误差。 等价于使用 Hinge Loss： $$ l_{\text{hinge}}(z) = \max(0, 1 - z) $$ #### 软间隔的拉格朗日函数 引入拉格朗日乘子 $\alpha_i \ge 0$，$\mu_i \ge 0$，构造拉格朗日函数： $$ \mathcal{L}(w, b, \xi, \alpha, \mu) = \frac{1}{2}\|w\|^2 + C \sum_i \xi_i - \sum_i \alpha_i [y_i(w^T x_i + b) - 1 + \xi_i] - \sum_i \mu_i \xi_i $$ 1. 原始约束： $$y_i(w^T x_i + b) - 1 + \xi_i \le 1, \quad \xi_i \ge 0$$ 2. 乘子非负： $$\alpha_i \ge 0, \quad \mu_i \ge 0$$ 3. 互补松弛性： $$\alpha_i [y_i(w^T x_i + b) - 1 + \xi_i - 1] = 0, \quad \mu_i \xi_i = 0$$ 4. 梯度为零： $$ \frac{\partial \mathcal{L}}{\partial w} = 0 \Rightarrow w = \sum_i \alpha_i y_i x_i $$ $$ \frac{\partial \mathcal{L}}{\partial b} = 0 \Rightarrow \sum_i \alpha_i y_i = 0 $$ $$ \frac{\partial \mathcal{L}}{\partial \xi_i} = 0 \Rightarrow C - \alpha_i - \mu_i = 0 $$ #### 软间隔的对偶问题 将 $w = \sum_i \alpha_i y_i x_i$ 和 $\sum_i \alpha_i y_i = 0$ 代入拉格朗日函数，得到对偶问题： $$ \max_{\alpha} \ W(\alpha) = \sum_i \alpha_i - \frac{1}{2}\sum_i\sum_j \alpha_i \alpha_j y_i y_j (x_i^T x_j) $$ 约束： $$ 0 \le \alpha_i \le C, \quad \sum_i \alpha_i y_i = 0 $$ #### 软间隔的支持向量 - 若 $0 < \alpha_i < C$：样本在间隔边界上，是支持向量； - 若 $\alpha_i = 0$：样本满足原始约束，不在间隔边界上； - 若 $\alpha_i = C$：样本不满足原始约束，是误分类或在间隔内部的点。 #### 软间隔的分类器 分类函数为： $$ f(x) = \text{sign}(w^{*T}x + b^*) $$ 其中 $w^* = \sum_i \alpha_i^* y_i x_i$，$b^*$ 可通过支持向量求得： $$ b^* = y_j - \sum_i \alpha_i^* y_i (x_i^T x_j) $$ ### Kernel Trick #### Motivation 核技巧让 SVM（以及任何只依赖“内积”的算法）在**高维特征空间**里学习一个**线性分类器**，但**无需显式计算高维映射**，只要把所有的内积 $x_i^\top x_j$ 换成一个核函数 $K(x_i,x_j)$ 就行。这样我们在原空间做“**低成本的高维学习**”。 * 把原始样本 $x$ 通过非线性映射 $\phi(x)$ 送到高维甚至无限维空间，让原本**线性不可分**的数据**线性可分**（见“Feature Mapping”示意图，页 15）。 * 但直接算 $\phi(x)$ 的维度可能爆炸。核技巧用 $$ K(x,z)=\langle \phi(x),\phi(z)\rangle $$ **间接**完成高维内积计算（页 17–21）。 #### Formula SVM 的对偶问题里，训练与预测都只出现样本间内积： $$ \max_\alpha \sum_i \alpha_i-\frac{1}{2}\sum_i\sum_j \alpha_i\alpha_j y_i y_j \,\underbrace{x_i^\top x_j}_{\text{只出现内积}} $$ 预测： $$ h(x)=\operatorname{sign}\left(\sum_i \alpha_i y_i\, \underbrace{x_i^\top x}_{\text{只出现内积}}+b\right) $$ 把所有内积统一替换为核函数 $K(x_i,x_j)$ 与 $K(x_i,x)$： $$ \begin{aligned} \max_\alpha~& \sum_i \alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\, K(x_i,x_j) \\ h(x)=&~\operatorname{sign}\Big(\sum_i \alpha_i y_i K(x_i,x)+b\Big) \end{aligned} $$ 这就是核化后的 SVM（页 20–21）。 #### Kernel 的选择 | 核 | 形式 | 何时用 | | ----------------- | ---------------------------------------------------------- | ----------------------------------------------------- | | 线性 Linear | $K(x,z)=x^\top z$ | 特征很多、基本线性可分；大 $n$、小 $m$（页 27、29）。 | | 多项式 Polynomial | $K(x,z)=(x^\top z+c)^d$ | 引入特征交互/曲线边界，$d$ 为次数（页 22–23）。 | | 高斯/RBF | $K(x,z)=\exp(-\|x-z\|^2/2\sigma^2)=\exp(-\gamma\|x-z\|^2)$ | 通用首选；可形成复杂非线性边界（页 25、27）。 | | Sigmoid | $\tanh(\beta x^\top z+\theta)$ | 类神经网络，实践中较少做标准 SVM 的默认。 | **经验法则（页 29）**： * $n$ 大（特征多）→ 线性核； * $n$ 小、$m$ 中等 → RBF； * $n$ 小、$m$ 很大 → 先造特征再用线性模型。 **一个函数是不是合法核？** 必要且充分条件：对任意有限样本集 $\{x_i\}$，构造核矩阵 $K_{ij}=K(x_i,x_j)$，它必须**对称半正定**（页 26）。实际中通常直接用“现成的”核族。 多项式核 $K(x,z)=(x^\top z+c)^d$ 等价于在 $O(n^d)$ 维空间做线性内积，但**计算核仍是 $O(n)$** 核化后的 SVM 一般配合 **软间隔**： $$ \min \tfrac12\|w\|^2 + C\sum_i\xi_i \quad\text{s.t.}\quad y_i(w^\top \phi(x_i)+b)\ge 1-\xi_i $$ 对偶里出现 $0\le \alpha_i\le C$ 与核 $K(\cdot,\cdot)$（页 7–12, 20）。 ## 4.1 Ensemble Learning ### Intro **集成学习** 通过组合多个基学习器（base learners）来获得更强的泛化能力（最终使用多数投票或加权平均）。它之所以有效：不同模型的误差模式互补，组合后能降低方差/偏差，稳定性能提升（页 31–34、35 的投票示意图）。 常见组合方式： - **Voting / Averaging**：多模型独立训练后，分类取多数、回归取均值（页 35）。 - **Stacking**：把各模型的预测当作“特征”，再训练一个二级模型融合（页 36，示意图展示 Level 1→Level 2）。 ### **Bagging（Bootstrap Aggregation）** #### Motivation **Bagging** 的核心是：对训练集**自助采样（bootstrap, 有放回）**，得到多份“不同但同分布”的数据子集，分别训练多个基学习器，最后**分类投票/回归平均**。这样能显著**降低方差**、提升稳定性（不改偏差）。 * 自助采样性质：样本量为 $m$ 时，某个样本**至少出现一次**的概率约 **0.632**；因此每个子集中约有 63.2% 的独立样本出现（另一部分是重复样本）。推导：未出现概率 $\lim_{m\to\infty}(1-\tfrac1m)^m\approx e^{-1}\approx 0.368$。 * “平均降方差”直觉：独立同分布情形下，$K$ 次测量的**均值方差**约为 $\sigma^2/K$（课件给出期望与方差公式）。 #### Formula * **分类（多数投票）**： $$ H(x)=\arg\max_{y\in\{\text{classes}\}}\sum_{t=1}^{T}\mathbf{1}\big(y=h_t(x)\big). $$ 这里 $h_t$ 是第 $t$ 个基学习器，$T$ 是模型数。 * **回归（平均）**：用各模型输出的算术平均（课件概念性说明）。 #### Pseudo Code **输入**：训练集 $D$，基学习算法 $\mathcal{L}$，轮数 $T$。 **循环** $t=1\ldots T$： 1. $D_t \leftarrow \text{Bootstrap}(D)$（有放回采样，大小与 $D$ 相同） 2. $h_t \leftarrow \mathcal{L}(D_t)$ **输出**：分类用多数投票的 $H(x)$（如上式）。 #### 何时有用 * **主要降低**：方差（把“对训练集很敏感”的不稳定模型平均掉）。 * **通常不改变**：偏差（模型系统性误差不变）。 * **最适合**：高方差基学习器（如未剪枝的决策树）。若基模型本身**高偏差**、对数据扰动不敏感，Bagging 收益有限（课件结论）。 #### Random Forest **随机森林 = 决策树的 Bagging + 结点级特征子采样**： * 对样本做 **bootstrap**（与 Bagging 一样）； * **每个结点**仅在随机选取的少量特征上寻找最优切分（课件示例：给定 $d$ 个特征，每个结点使用 $\log|d|$ 个特征），进一步**去相关化**各棵树，提高集成增益；预测阶段通过投票/平均融合。 ### Boosting #### Intro **Boosting** 用很多个“弱学习器”（略好于随机猜）串行地训练： 每一轮根据上轮的错误**提高难样本的权重**，迫使下一轮更关注这些样本；最后把所有弱学习器加权投票/加权求和，得到一个强模型（第 47 页）。 与 Bagging 的关键差异：**Boosting 是串行、降低偏差为主**，而 Bagging 并行、降低方差为主（第 58 页）。 #### AdaBoost 设训练集 $\{(x_i,y_i)\}_{i=1}^m$，二分类 $y_i\in\{-1,+1\}$。 * **初始化权重**：$D_1(i)=1/m$（第 48–51 页）。 * **第 $t$ 轮**： 1. 在分布 $D_t$ 上训练弱分类器 $h_t(x)$。 2. 计算带权错误率 $\displaystyle \epsilon_t=\sum_i D_t(i)\,\mathbf{1}[y_i\neq h_t(x_i)]$（第 51 页）。 3. 设置该弱分类器的**重要性系数** $\displaystyle \alpha_t=\tfrac12\log\frac{1-\epsilon_t}{\epsilon_t}$（第 51 页）。 4. **更新样本分布** $$ D_{t+1}(i)=\frac{D_t(i)\exp\big(-\alpha_t y_i h_t(x_i)\big)}{Z_t}, $$ 其中 $Z_t$ 为归一化常数（第 51 页）。 * **最终模型**（加权投票）： $$ H(x)=\operatorname{sign}\!\Big(\sum_{t=1}^T \alpha_t\, h_t(x)\Big) \quad\text{（第 49、51 页）。} $$ 为什么 work： 课件指出：Boosting（以 AdaBoost 为例）等价于在最小化**指数损失** $$ \sum_{i=1}^m \exp\!\big(-y_i\,H(x_i)\big),\quad H(x)=\sum_t \alpha_t h_t(x), $$ 因此它会**逐轮降低偏差（bias）**（第 57 页）。 直觉：被分错的样本有 $y_i H(x_i)<0$，损失被指数函数**放大**，下一轮权重更高→后续模型更“盯”难点。 * **偏差**：Boosting 通过逐轮拟合难样本，通常能显著**降偏差**（第 57–58 页）。 * **方差**：组合多个弱模型也有助于稳定，但主效应仍在降偏差。 * **噪声/离群点**：因会持续提升“分错样本”的权重，Boosting **更易受噪声影响**；Bagging 对噪声更稳（第 58 页总结）。 一些 formula： * $\epsilon_t=\sum_i D_t(i)\mathbf{1}[y_i\neq h_t(x_i)]$（带权错率） * $\alpha_t=\tfrac12\log\frac{1-\epsilon_t}{\epsilon_t}$（弱学习器权重） * $D_{t+1}(i)\propto D_t(i)\exp(-\alpha_t y_i h_t(x_i))$（样本权重更新） * $H(x)=\operatorname{sign}(\sum_t \alpha_t h_t(x))$（最终分类器） ## 5 Neural Network 咕咕咕 Loading... ## Preface 当第一次接触黑盒的时候，你的脑子就会变成黑盒。 第一次学这些东西的时候，应该还是 Andrew Ng 在 coursera 那一个非常通俗的 ML，没有微积分基础，也没有什么概率论的基础，故而对大部分算法的理解存在于：我有一个多元函数，参数未知，遂变成最大似然估计问题。剩下的都是技巧了。 于是如果不懂，当作一个黑盒了解起输入输出和功能即可。不可置否的是，这种方法对于快速学习新东西非常有效果。但一旦深入，该补的功课还是一样都少不了。 已经是彻彻底底的 Midterm 了，再不 review 之前的内容，期末等着挂科吧。 ## 3-Supervised Learning I ### 3.1 Logistic Regression 任务：**分类（Classification）**。接下来首先讨论二分类。 实际上模型通过 activation function输出的是一个概率，比如说 Sigmoid: $$ \sigma(x) = P(y=1|x;\theta) = \frac{1}{1 + e^{-\theta^T}x} $$ - **决策边界（Decision Boundary）**：当 $\theta^Tx = 0$ 时分割两类。 #### 设计 loss function 当我们要衡量预测好不好时，理想的损失函数也应该与**概率预测**相匹配，而不是MSE。如果用 MSE 的话，例如：$J(\theta) = \frac{1}{2m} \sum (h_{\theta}(x_i) - y_i)^2$，存在的问题是： - Sigmoid 是非线性的，导致 **损失函数非凸（non-convex）**，优化时容易卡在局部最小值。 - 从概率角度看，它也不是在最大化正确分类的概率。 因此，我们要设计一个新的 loss function。从概率建模角度出发，我们希望模型能最大化样本出现的概率（最大似然估计）： $$ L(\theta) = \prod_{i=1}^{m} P(y_i|x_i;\theta) $$ 取 log： $$ \log L(\theta) = \sum_{i=1}^{m} [y_i \log h_{\theta}(x_i) + (1 - y_i) \log (1 - h_{\theta}(x_i))] $$ 最大化这个“对数似然”就等价于最小化它的负数： $$ J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} [y_i \log h_{\theta}(x_i) + (1 - y_i) \log (1 - h_{\theta}(x_i))] $$ 这就是 **Cross Entropy Loss（交叉熵损失）**。 #### Multiclass classification - **One-vs-All** 策略：对每个类别分别训练一个分类器。 - 预测时选择概率最大的类别。 #### ### Regularization - 目的：**防止过拟合**。 - 在代价函数中加入惩罚项, *i.e.*： $$ J(\theta) = J(\theta) + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2 $$ - 调节参数 $\lambda$ 的大小可平衡**偏差（Bias）\**与\**方差（Variance）**。 注意，此时梯度更新公式也要加上这一项： $$ \theta_j := \theta_j - \alpha \frac{\partial J(\theta)}{\partial \theta_j} - \alpha \frac{\lambda}{m}\theta_j $$ ### 3.2 Suppor vector machine 这个之前真没学过，因此详细写一下 #### Motivation  分类任务也可以视为找到一个“面”，可以把各个类隔离开。具体地，这个“面”： > Hyperplane，超平面，是n维欧氏空间中，[余维度](https://zh.wikipedia.org/wiki/餘維數)为1的[子空间](https://zh.wikipedia.org/wiki/子空間)[[1\]](https://zh.wikipedia.org/wiki/超平面#cite_note-1)。即超平面是 $n$ 维空间中的 $n-1$维的子空间。 具体的，SVM的目标是：找到一个能把两类样本分开的**最优超平面**，并使得两类之间的“间隔（margin）”最大。 - 直觉上：它不像逻辑回归那样关心“概率”，而是关心“边界离样本多远”。 - 只有**最靠近边界的样本点**（即“支持向量”）对模型有影响。 假如我们有 Training data: $\{(\vec{x_1}, y_1) \dots (\vec{x_n}, y_n)\}$，我们的目标是找到一个 Hyperplane: $w^Tx + b = 0$ 满足： $$ \begin{align} w^Tx_i+b \geq 1, & y_i = +1 \\ w^Tx_i+b \leq -1, & y_i = -1 \\ \end{align} $$ 合并写成： $$ y_i(w^Tx_i + b) \geq 1 $$ ### Design 超平面定义： $$ \mathcal{H} = \{x \mid w^T x + b = 0\} $$ 对于任意一个点 **x**，它到超平面 **H** 的距离为： $$ d = \frac{|w^T x + b|}{\|w\|} $$ 个最靠近超平面的点（各一类）之间的距离就是“间隔”： $$ \gamma(w, b) = \min_{x \in D} \frac{2|w^T x + b|}{\|w\|} $$ 注意到有 scale invariance: $$ \gamma(\beta w, \beta b) = \gamma(w, b) $$ 所以直接可以令：$2|w^Tx+b| = 1$，故有： $$ \gamma = \frac{2}{||w||} $$ 要让间隔最大化，相当于让$||w||$ 最小化。约束：$\forall i, y_i(w^Tx_i+b) \geq 1$ 所以目标函数： $$ \min_{w,b} \frac{1}{2} ||w||^2 $$ 可用拉格朗日乘数法解，具体结果见另附说明。 ## 3.3 Support Vector Machine II ### Soft Margin 目的：让 SVM 能处理非线性可分或含噪声的数据。 引入“松弛变量”（Slack Variable） $\xi_i$，允许部分样本违背约束： $$ y_i(w^T x_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0 $$ 新目标函数： $$ \min_{w, b, \xi} \ \frac{1}{2}\|w\|^2 + C \sum_i \xi_i $$ 其中 $C$：平衡项，用于控制“间隔大小”与“误分类惩罚”。 - $C \uparrow$：重视分类准确率； - $C \downarrow$：重视大间隔、容忍误差。 等价于使用 Hinge Loss： $$ l_{\text{hinge}}(z) = \max(0, 1 - z) $$ #### 软间隔的拉格朗日函数 引入拉格朗日乘子 $\alpha_i \ge 0$，$\mu_i \ge 0$，构造拉格朗日函数： $$ \mathcal{L}(w, b, \xi, \alpha, \mu) = \frac{1}{2}\|w\|^2 + C \sum_i \xi_i - \sum_i \alpha_i [y_i(w^T x_i + b) - 1 + \xi_i] - \sum_i \mu_i \xi_i $$ 1. 原始约束： $$y_i(w^T x_i + b) - 1 + \xi_i \le 1, \quad \xi_i \ge 0$$ 2. 乘子非负： $$\alpha_i \ge 0, \quad \mu_i \ge 0$$ 3. 互补松弛性： $$\alpha_i [y_i(w^T x_i + b) - 1 + \xi_i - 1] = 0, \quad \mu_i \xi_i = 0$$ 4. 梯度为零： $$ \frac{\partial \mathcal{L}}{\partial w} = 0 \Rightarrow w = \sum_i \alpha_i y_i x_i $$ $$ \frac{\partial \mathcal{L}}{\partial b} = 0 \Rightarrow \sum_i \alpha_i y_i = 0 $$ $$ \frac{\partial \mathcal{L}}{\partial \xi_i} = 0 \Rightarrow C - \alpha_i - \mu_i = 0 $$ #### 软间隔的对偶问题 将 $w = \sum_i \alpha_i y_i x_i$ 和 $\sum_i \alpha_i y_i = 0$ 代入拉格朗日函数，得到对偶问题： $$ \max_{\alpha} \ W(\alpha) = \sum_i \alpha_i - \frac{1}{2}\sum_i\sum_j \alpha_i \alpha_j y_i y_j (x_i^T x_j) $$ 约束： $$ 0 \le \alpha_i \le C, \quad \sum_i \alpha_i y_i = 0 $$ #### 软间隔的支持向量 - 若 $0 < \alpha_i < C$：样本在间隔边界上，是支持向量； - 若 $\alpha_i = 0$：样本满足原始约束，不在间隔边界上； - 若 $\alpha_i = C$：样本不满足原始约束，是误分类或在间隔内部的点。 #### 软间隔的分类器 分类函数为： $$ f(x) = \text{sign}(w^{*T}x + b^*) $$ 其中 $w^* = \sum_i \alpha_i^* y_i x_i$，$b^*$ 可通过支持向量求得： $$ b^* = y_j - \sum_i \alpha_i^* y_i (x_i^T x_j) $$ ### Kernel Trick #### Motivation 核技巧让 SVM（以及任何只依赖“内积”的算法）在**高维特征空间**里学习一个**线性分类器**，但**无需显式计算高维映射**，只要把所有的内积 $x_i^\top x_j$ 换成一个核函数 $K(x_i,x_j)$ 就行。这样我们在原空间做“**低成本的高维学习**”。 * 把原始样本 $x$ 通过非线性映射 $\phi(x)$ 送到高维甚至无限维空间，让原本**线性不可分**的数据**线性可分**（见“Feature Mapping”示意图，页 15）。 * 但直接算 $\phi(x)$ 的维度可能爆炸。核技巧用 $$ K(x,z)=\langle \phi(x),\phi(z)\rangle $$ **间接**完成高维内积计算（页 17–21）。 #### Formula SVM 的对偶问题里，训练与预测都只出现样本间内积： $$ \max_\alpha \sum_i \alpha_i-\frac{1}{2}\sum_i\sum_j \alpha_i\alpha_j y_i y_j \,\underbrace{x_i^\top x_j}_{\text{只出现内积}} $$ 预测： $$ h(x)=\operatorname{sign}\left(\sum_i \alpha_i y_i\, \underbrace{x_i^\top x}_{\text{只出现内积}}+b\right) $$ 把所有内积统一替换为核函数 $K(x_i,x_j)$ 与 $K(x_i,x)$： $$ \begin{aligned} \max_\alpha~& \sum_i \alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\, K(x_i,x_j) \\ h(x)=&~\operatorname{sign}\Big(\sum_i \alpha_i y_i K(x_i,x)+b\Big) \end{aligned} $$ 这就是核化后的 SVM（页 20–21）。 #### Kernel 的选择 | 核 | 形式 | 何时用 | | ----------------- | ---------------------------------------------------------- | ----------------------------------------------------- | | 线性 Linear | $K(x,z)=x^\top z$ | 特征很多、基本线性可分；大 $n$、小 $m$（页 27、29）。 | | 多项式 Polynomial | $K(x,z)=(x^\top z+c)^d$ | 引入特征交互/曲线边界，$d$ 为次数（页 22–23）。 | | 高斯/RBF | $K(x,z)=\exp(-\|x-z\|^2/2\sigma^2)=\exp(-\gamma\|x-z\|^2)$ | 通用首选；可形成复杂非线性边界（页 25、27）。 | | Sigmoid | $\tanh(\beta x^\top z+\theta)$ | 类神经网络，实践中较少做标准 SVM 的默认。 | **经验法则（页 29）**： * $n$ 大（特征多）→ 线性核； * $n$ 小、$m$ 中等 → RBF； * $n$ 小、$m$ 很大 → 先造特征再用线性模型。 **一个函数是不是合法核？** 必要且充分条件：对任意有限样本集 $\{x_i\}$，构造核矩阵 $K_{ij}=K(x_i,x_j)$，它必须**对称半正定**（页 26）。实际中通常直接用“现成的”核族。 多项式核 $K(x,z)=(x^\top z+c)^d$ 等价于在 $O(n^d)$ 维空间做线性内积，但**计算核仍是 $O(n)$** 核化后的 SVM 一般配合 **软间隔**： $$ \min \tfrac12\|w\|^2 + C\sum_i\xi_i \quad\text{s.t.}\quad y_i(w^\top \phi(x_i)+b)\ge 1-\xi_i $$ 对偶里出现 $0\le \alpha_i\le C$ 与核 $K(\cdot,\cdot)$（页 7–12, 20）。 ## 4.1 Ensemble Learning ### Intro **集成学习** 通过组合多个基学习器（base learners）来获得更强的泛化能力（最终使用多数投票或加权平均）。它之所以有效：不同模型的误差模式互补，组合后能降低方差/偏差，稳定性能提升（页 31–34、35 的投票示意图）。 常见组合方式： - **Voting / Averaging**：多模型独立训练后，分类取多数、回归取均值（页 35）。 - **Stacking**：把各模型的预测当作“特征”，再训练一个二级模型融合（页 36，示意图展示 Level 1→Level 2）。 ### **Bagging（Bootstrap Aggregation）** #### Motivation **Bagging** 的核心是：对训练集**自助采样（bootstrap, 有放回）**，得到多份“不同但同分布”的数据子集，分别训练多个基学习器，最后**分类投票/回归平均**。这样能显著**降低方差**、提升稳定性（不改偏差）。 * 自助采样性质：样本量为 $m$ 时，某个样本**至少出现一次**的概率约 **0.632**；因此每个子集中约有 63.2% 的独立样本出现（另一部分是重复样本）。推导：未出现概率 $\lim_{m\to\infty}(1-\tfrac1m)^m\approx e^{-1}\approx 0.368$。 * “平均降方差”直觉：独立同分布情形下，$K$ 次测量的**均值方差**约为 $\sigma^2/K$（课件给出期望与方差公式）。 #### Formula * **分类（多数投票）**： $$ H(x)=\arg\max_{y\in\{\text{classes}\}}\sum_{t=1}^{T}\mathbf{1}\big(y=h_t(x)\big). $$ 这里 $h_t$ 是第 $t$ 个基学习器，$T$ 是模型数。 * **回归（平均）**：用各模型输出的算术平均（课件概念性说明）。 #### Pseudo Code **输入**：训练集 $D$，基学习算法 $\mathcal{L}$，轮数 $T$。 **循环** $t=1\ldots T$： 1. $D_t \leftarrow \text{Bootstrap}(D)$（有放回采样，大小与 $D$ 相同） 2. $h_t \leftarrow \mathcal{L}(D_t)$ **输出**：分类用多数投票的 $H(x)$（如上式）。 #### 何时有用 * **主要降低**：方差（把“对训练集很敏感”的不稳定模型平均掉）。 * **通常不改变**：偏差（模型系统性误差不变）。 * **最适合**：高方差基学习器（如未剪枝的决策树）。若基模型本身**高偏差**、对数据扰动不敏感，Bagging 收益有限（课件结论）。 #### Random Forest **随机森林 = 决策树的 Bagging + 结点级特征子采样**： * 对样本做 **bootstrap**（与 Bagging 一样）； * **每个结点**仅在随机选取的少量特征上寻找最优切分（课件示例：给定 $d$ 个特征，每个结点使用 $\log|d|$ 个特征），进一步**去相关化**各棵树，提高集成增益；预测阶段通过投票/平均融合。 ### Boosting #### Intro **Boosting** 用很多个“弱学习器”（略好于随机猜）串行地训练： 每一轮根据上轮的错误**提高难样本的权重**，迫使下一轮更关注这些样本；最后把所有弱学习器加权投票/加权求和，得到一个强模型（第 47 页）。 与 Bagging 的关键差异：**Boosting 是串行、降低偏差为主**，而 Bagging 并行、降低方差为主（第 58 页）。 #### AdaBoost 设训练集 $\{(x_i,y_i)\}_{i=1}^m$，二分类 $y_i\in\{-1,+1\}$。 * **初始化权重**：$D_1(i)=1/m$（第 48–51 页）。 * **第 $t$ 轮**： 1. 在分布 $D_t$ 上训练弱分类器 $h_t(x)$。 2. 计算带权错误率 $\displaystyle \epsilon_t=\sum_i D_t(i)\,\mathbf{1}[y_i\neq h_t(x_i)]$（第 51 页）。 3. 设置该弱分类器的**重要性系数** $\displaystyle \alpha_t=\tfrac12\log\frac{1-\epsilon_t}{\epsilon_t}$（第 51 页）。 4. **更新样本分布** $$ D_{t+1}(i)=\frac{D_t(i)\exp\big(-\alpha_t y_i h_t(x_i)\big)}{Z_t}, $$ 其中 $Z_t$ 为归一化常数（第 51 页）。 * **最终模型**（加权投票）： $$ H(x)=\operatorname{sign}\!\Big(\sum_{t=1}^T \alpha_t\, h_t(x)\Big) \quad\text{（第 49、51 页）。} $$ 为什么 work： 课件指出：Boosting（以 AdaBoost 为例）等价于在最小化**指数损失** $$ \sum_{i=1}^m \exp\!\big(-y_i\,H(x_i)\big),\quad H(x)=\sum_t \alpha_t h_t(x), $$ 因此它会**逐轮降低偏差（bias）**（第 57 页）。 直觉：被分错的样本有 $y_i H(x_i)<0$，损失被指数函数**放大**，下一轮权重更高→后续模型更“盯”难点。 * **偏差**：Boosting 通过逐轮拟合难样本，通常能显著**降偏差**（第 57–58 页）。 * **方差**：组合多个弱模型也有助于稳定，但主效应仍在降偏差。 * **噪声/离群点**：因会持续提升“分错样本”的权重，Boosting **更易受噪声影响**；Bagging 对噪声更稳（第 58 页总结）。 一些 formula： * $\epsilon_t=\sum_i D_t(i)\mathbf{1}[y_i\neq h_t(x_i)]$（带权错率） * $\alpha_t=\tfrac12\log\frac{1-\epsilon_t}{\epsilon_t}$（弱学习器权重） * $D_{t+1}(i)\propto D_t(i)\exp(-\alpha_t y_i h_t(x_i))$（样本权重更新） * $H(x)=\operatorname{sign}(\sum_t \alpha_t h_t(x))$（最终分类器） ## 5 Neural Network 咕咕咕 最后修改：2025 年 11 月 01 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
