下面这份笔记严格以你上传的 83 页课件为主线整理。课件内部标题为 Chapter 6. Classification: Basic Concepts，内容从分类问题定义开始，依次覆盖决策树、Bayes/Naïve Bayes、Lazy Learning/kNN、线性模型与 Logistic Regression、模型评估、集成学习与类别不平衡问题。

我用以下重要度标记：

★★★：期末高概率核心，公式、算法步骤、计算题必须掌握
★★☆：重要概念/比较题，应能解释
★☆☆：了解型细节、优缺点、应用背景

Chapter 6 Classification: Basic Concepts 完整复习笔记

0. 本章到底要解决什么问题？——先看“进化树”

本章的核心问题不是“学很多分类器”，而是：

已知一批带标签的数据，怎样学习一个规则，使其能够对从未见过的新样本做出可靠的类别判断？并进一步回答：怎么学习、怎么优化、怎么评估、怎么提升？

整个章节可以理解成下面这棵方法论进化树：

text

数据学习问题
│
├── 有没有标签？
│   ├── 无标签 → Unsupervised Learning → Clustering
│   └── 有标签 → Supervised Learning
│
└── 输出是什么？
    ├── 连续值 → Numeric Prediction / Regression
    └── 离散类别 → Classification
            │
            ├── 如何构造分类规则？
            │
            ├── 方案 A：Decision Tree
            │   ├── 递归划分特征空间
            │   ├── Information Gain
            │   └── 信息增益偏好多值属性
            │        ↓
            │      Gain Ratio
            │
            ├── 方案 B：Bayesian Classification
            │   ├── 最大化 posterior
            │   ├── 完整联合分布太复杂
            │   │    ↓
            │   ├── Naïve Bayes：条件独立
            │   └── 零概率问题
            │        ↓
            │      Laplace smoothing
            │
            ├── 方案 C：Lazy Learning
            │   ├── 不提前建全局模型
            │   ├── kNN：根据邻居预测
            │   ├── 距离加权
            │   └── 高维灾难
            │        ↓
            │      特征选择 / axis stretching
            │
            ├── 方案 D：Linear Model
            │   ├── Linear Regression
            │   ├── 连续输出不能直接做概率
            │   │    ↓
            │   ├── Sigmoid
            │   │    ↓
            │   ├── Logistic Regression
            │   ├── Maximum Likelihood
            │   └── 无 closed-form
            │        ↓
            │      Gradient Descent / Ascent
            │
            ├── 模型到底好不好？
            │   ├── Confusion Matrix
            │   ├── Accuracy / Error
            │   ├── Sensitivity / Specificity
            │   ├── Precision / Recall / F1
            │   ├── Holdout
            │   ├── Cross-validation
            │   └── ROC / AUC
            │
            └── 单模型还不够怎么办？
                ├── Ensemble
                ├── Bagging
                ├── Boosting
                │   ├── AdaBoost
                │   └── Gradient Boosting
                ├── Random Forest
                └── Imbalanced Classification
                    ├── Re-sampling
                    ├── Threshold moving
                    └── Class weighting

这就是整章最重要的宏观逻辑。

1. Classification 基础概念

1.1 Supervised vs. Unsupervised Learning ★★★

Supervised Learning

训练数据中，每个样本都附带 class label。

设训练集为

其中：

：第个样本的属性或特征；
：对应的已知标签；
：训练样本数量。

目标是利用训练数据学习模型

之后对新的 test instance 预测标签。

课件中的 Play Golf 数据就是：

Unsupervised Learning

训练数据没有标签。

即只有：

模型试图发现数据中潜在的 cluster/class structure。

核心区别：

问题	Supervised	Unsupervised
标签	已知	未知
目标	学习输入→标签映射	发现数据内部结构
本章典型任务	Classification	Clustering
示例	是否打高尔夫	自动发现若干群体

1.2 Classification vs. Numeric Prediction ★★★

这是考试最容易出现的定义辨析之一。

Classification

输出：

即 categorical/discrete/nominal label。

例如：

Yes / No
Fraud / Non-fraud
Cancer / Healthy

Numeric Prediction

输出：

即 continuous-valued function。

例如：

房价
收入
温度

所以：

Classification 的关键不是输入是不是连续，而是输出标签是不是离散类别。

1.3 Classification 的完整生命周期 ★★★

课件明确分为：

text

Training
   ↓
Model Construction
   ↓
Validation / Model Selection
   ↓
Testing
   ↓
Deployment

Training Set

用于：

model construction。

Validation Set

用于：

模型选择、参数选择、模型 refinement。

如果一个“test set”被用于模型选择，它实际上已经承担了 validation/development set 的角色。

Test Set

只用于：

最终估计模型泛化能力。

原则：

测试集应当独立于训练集。

否则发生 information leakage。

2. Decision Tree Induction

2.1 决策树的核心思想 ★★★

决策树采用：

top-down, recursive, divide-and-conquer

即：

text

所有训练样本放在 root
        ↓
选择最佳 attribute
        ↓
根据 attribute 划分数据
        ↓
对子节点递归重复
        ↓
直到满足 stopping condition

Play Golf 示例最终形成：

text

Outlook?
├── Overcast → Yes
├── Sunny
│   └── Windy?
│       ├── False → Yes
│       └── True  → No
└── Rainy
    └── Humidity?
        ├── Normal → Yes
        └── High   → No

这里真正困难的问题只有一个：

每个节点究竟选哪个 attribute？

于是引出了 splitting measure。

2.2 决策树算法 ★★★

每个节点：

当前节点拥有训练样本集合；
对候选 attributes 计算 splitting criterion；
选择最好的 attribute；
将分成若干子集；
对每个子集递归建树。

典型 criterion：

Information Gain
Gini Index

本课件重点讲 Information Gain。

2.3 停止条件 ★★★

课件给出三种情况：

情况 1

节点中的所有样本都属于同一 class。

则已经纯净：

无需继续划分。

情况 2

没有剩余属性可以继续 partition。

此时使用：

majority voting

即预测当前节点中出现次数最多的 class。

情况 3

没有 sample 留下。

也必须停止递归。

2.4 Continuous-valued Attribute 怎么处理？ ★★★

例如：

不是 categorical，而是连续数值。

课件给出两种方法。

Method 1：Discretization

人为划分：

text

然后将其视为 categorical attribute。

缺点

划分边界比较人为，并可能损失数值结构。

Method 2：寻找最佳 split point

这是更重要的方法。

首先排序：

相邻两个值之间的候选切分点：

例如：

于是候选点包括：

对每个：

然后计算 Information Gain，选择 gain 最大的。

所以：

这实际上就是：

把 continuous variable 转化成一个最佳 binary decision boundary。

2.5 Decision Tree 的优缺点 ★★☆

优点

课件列出的优点必须记：

Easy to explain
Easy to implement
Efficient
Can tolerate missing data
White box
No need to normalize data
Non-parametric
不假设 data distribution
不假设 attributes independence
可处理不同 attribute types

其中考试很值得记住：

Decision Tree 不需要 feature normalization。

因为它做的是：

而不是基于 feature magnitude 的距离比较。

缺点

Unstable
Sensitive to noise
Accuracy 不一定足够高
Optimal splitting 是困难问题，因此实际使用 greedy algorithm
Overfitting

最重要逻辑：

一个很小的数据扰动可能改变高层节点的 split，而高层节点变化会影响整棵树，因此决策树具有较高 variance。

这也是后面 Bagging 和 Random Forest 为什么特别适合 decision trees 的理论背景。

3. Information Gain：决策树如何选择 Attribute

3.1 Entropy ★★★

熵衡量一个随机变量的不确定性。

对于离散随机变量

令：

则：

在决策树中课件使用，单位为 bit：

其中：

：类别数量；
：第类的概率。

直觉

完全确定

如果：

则：

说明没有 uncertainty。

二分类最不确定情况

若：

则：

达到最大值。

因此：

分类越混乱，entropy 越大；越纯净，entropy 越小。

3.2 Conditional Entropy ★★★

课件定义：

含义：

已经知道后，关于还剩多少 uncertainty？

决策树做 split，其本质就是希望：

尽可能小。

3.3 Information Gain ★★★

对于数据集，设有个类别。

定义：

其中：

：数据集样本数；
：属于类别的样本数。

原数据集的 entropy：

假设 attribute 把分成：

则 split 后需要的信息量：

最后：

因此：

Information Gain = split 前的不确定性 − split 后剩余的不确定性。

选：

3.4 Play Golf Information Gain 计算 ★★★

整个数据集：

Yes = 9
No = 5

所以：

得到：

对于 Outlook：

Outlook	Yes	No
Rainy	2	3
Overcast	4	0
Sunny	3	2

定义二分类 entropy：

所以：

于是：

所以：

课件同时给出：

因此：

所以 root node 选择：

这正好解释了课件中的最终树。

3.5 Information Gain 有什么问题？ ★★★

关键痛点：

Information Gain 偏爱具有很多不同取值的 attribute。

极端例子：

假设每个人 ID 都不同。

那么 split 后：

text

一个 ID → 一个 sample

每个 leaf entropy：

于是 Information Gain 非常大。

但 ID 几乎没有预测意义。

所以：

“把训练数据分得特别碎”不等于“学到了可泛化规律”。

3.6 Gain Ratio：针对 Information Gain 的改进 ★★★

C4.5 使用 Gain Ratio。

首先定义：

然后：

选择：

为什么有效？

如果 attribute 有非常多 distinct values：

往往很大。

因此归一化以后，它的 gain 会被惩罚。

课件 Temp 示例

Temp 三个分支：

所以：

因此：

ID3 → C4.5 的方法论演进 ★★★

Algorithm	Splitting measure	痛点
ID3	Information Gain	偏好多-valued attribute
C4.5	Gain Ratio	对 Information Gain 进行 normalization

这就是一个很典型的：

Existing criterion → discover bias → normalization → improved criterion。

4. Bayesian Classification

4.1 Total Probability Theorem ★★★

若事件构成样本空间的一个 partition：

则：

这是后面计算 Bayesian denominator 的基础。

4.2 Bayes' Theorem ★★★

对分类而言：

：observed evidence/sample；
：假设属于 class 。

三个概率必须分清：

Prior

在观察前，我们相信的程度。

Likelihood

如果为真，出现当前 evidence 的概率。

Posterior

看见 evidence 后，对更新后的相信程度。

因此：

因为分类比较不同 class 时：

对所有类别相同。

4.3 MAP Classification ★★★

分类目标：

由 Bayes：

因为 denominator 与无关：

这就是 maximum a posteriori classification。

4.4 Picnic Example ★★☆

课件：

则：

重要直觉：

“50% 的 rainy day 是 cloudy morning”并不等于“cloudy morning 有 50% 概率下雨”。

这就是：

5. 从 Exact Bayes 到 Naïve Bayes

5.1 为什么 Exact Bayesian Classification 很难？ ★★★

若：

链式法则：

所以：

问题：

随着 features 增多，需要估计的高维 conditional probabilities 爆炸。

也就是所谓：

dependency modeling 太复杂。

5.2 Naïve Bayes Assumption ★★★

Naïve Bayes 作出一个非常强的假设：

features are conditionally independent given the class label。

数学上：

因此：

于是：

分类：

这一步将一个复杂的 joint probability estimation 转变成：

每个 feature 单独做 sample counting。

所以非常高效。

5.3 Categorical Feature ★★★

若为 categorical feature：

则：

即：

在 class 内，取值为的样本比例。

5.4 Continuous Feature：Gaussian Naïve Bayes ★★★

若是 continuous-valued，课件采用 Gaussian：

这里表示标准差，因此正态分布记号的第二个参数应写方差。课件第 23 页将记号简写为，容易把标准差与方差混淆；下面的密度公式按为标准差书写。

概率密度：

然后：

其中：

：class 中该 feature 的均值；
：对应标准差。

5.5 Play Golf Naïve Bayes 示例 ★★★

已知：

Yes: 9
No: 5

因此：

对于 Outlook = Sunny：

于是：

同理：

因此：

5.6 多 feature 完整预测 ★★★

课件测试 tuple：

Yes：

课件计算：

No：

归一化 denominator：

所以：

最终：

6. Zero Probability Problem → Laplace Correction

6.1 Why Naïve Bayes fails? ★★★

Naïve Bayes 使用：

如果任何一项：

那么：

无论其他 features 多么支持该 class。

这就是：

zero-frequency / zero-probability problem。

6.2 Laplace Smoothing ★★★

假设 categorical variable 有：

种可能值。

计数为：

Laplace correction：

本质：

每个 category 预先增加一个 pseudo-count。

课件例子

1000 个样本：

low = 0
medium = 990
high = 10

有三个 possible values。

于是：

这样没有任何类别 probability = 0。

6.3 Naïve Bayes 优缺点 ★★☆

Strength

效率极高
只需要统计 class conditional probability
性能可能与 decision tree、部分 neural-network classifier 可比
支持 incremental learning
可以把 prior knowledge 和 observed data 结合

Weakness

核心就是：

通常并不成立。

例如：

text

age ↔ family history
fever ↔ cough
symptoms ↔ disease

存在 dependency。

Naïve Bayes 无法显式建模这些依赖。

课件给出的进一步方法：

Bayesian Belief Networks。

7. Lazy Learning

7.1 Eager vs. Lazy Learning ★★★

这是本章算法思想上的一个重要转折。

Eager Learning

例如：

Decision Tree
Naïve Bayes
Logistic Regression

流程：

text

training data
    ↓
提前训练模型 M
    ↓
test x
    ↓
M(x)

训练时间较高，prediction 较快。

Lazy Learning

训练时：

基本不构造模型，只保存 training examples。

等 query 出现时：

才根据附近的数据构造 local prediction。

因此：

	Eager	Lazy
Training	较慢	较快
Prediction	较快	较慢
模型	预先建立 global hypothesis	query 时构造 local approximation
Hypothesis	单一 global	更丰富的 local hypothesis

课件特别指出：

Lazy learner effectively uses a richer hypothesis space，因为很多 local functions 可以共同形成复杂的 global approximation。

7.2 Instance-Based Learning ★★☆

典型 lazy methods：

k-nearest neighbor
Locally weighted regression
Case-based reasoning

其中期末重点显然是 kNN。

8. k-Nearest Neighbor

8.1 基本思想 ★★★

每个 instance 表示为 -dimensional space 中一点：

对于 query：

找到距离最近的个 training examples。

8.2 Euclidean Distance ★★★

课件写作：

其标准展开为：

注意这个展开式是对课件 Euclidean distance 记号的明确化。

8.3 Classification ★★★

对于 discrete target：

即：

k 个最近邻 majority voting。

8.4 Regression ★★☆

如果 target 是 continuous：

即取平均。

因此 kNN 既能：

classification
numeric prediction

8.5 1-NN 与 Voronoi Diagram ★★☆

当：

空间中的每一个位置都归属于最近 training point。

这些区域构成：

Voronoi cells。

因此 1-NN 的 decision boundary 就是 Voronoi boundary。

8.6 Distance-weighted kNN ★★★

普通 kNN 的问题：

第 1 近邻和第近邻贡献完全相同。

但直觉上，越近越可信。

课件给出 weight：

所以距离越小：

分类时可以使用 weighted voting。

8.7 为什么更 robust？ ★★☆

1-NN 很容易受到 single noisy point 影响。

而 kNN 用多个邻居 voting/average：

因此：

averaging neighbors 增强 robustness。

8.8 Curse of Dimensionality ★★★

这是 kNN 的关键 weakness。

随着 dimensionality 增加：

irrelevant dimensions 会影响 Euclidean distance，使“nearest”逐渐失去意义。

课件描述为：

distance between neighbors could be dominated by irrelevant attributes。

解决方向：

axis stretching
eliminate least relevant attributes

本质上就是：

feature weighting / feature selection。

9. k 的选择：Bias–Variance Tradeoff

Small ★★★

例如：

模型高度灵活。

因此：

low bias
high variance
prone to overfitting

即：

Large

包含越来越多距离很远、甚至 irrelevant 的 samples。

决策边界越来越平滑。

因此：

high bias
low variance
prone to underfitting

这是非常典型的期末概念题。

10. Case-Based Reasoning

CBR 也是 lazy learner，但和 kNN 不一样。

kNN 表示：

CBR 保存的是：

rich symbolic descriptions / cases。

例如：

customer-service diagnosis
legal ruling

流程：

text

new problem
    ↓
retrieve similar historical cases
    ↓
knowledge-based reasoning
    ↓
possibly combine multiple cases
    ↓
adapt old solutions

主要挑战：

如何定义好的 similarity metric？

以及：

indexing
syntactic similarity
failure 时 backtracking
adapt to additional cases

重要度：★☆☆～★★☆

11. Linear Classifiers：从 Linear Regression 到 Logistic Regression

这是本章最明显的一条“方法演进链”。

text

Linear Regression
      ↓
输出任意实数
      ↓
无法直接解释为 class probability
      ↓
Sigmoid
      ↓
输出 [0,1]
      ↓
Logistic Regression
      ↓
Maximum Likelihood
      ↓
无 closed-form
      ↓
Gradient optimization

12. Linear Regression

12.1 问题定义 ★★★

输入：

输出：

其中：

：sample index；
：feature dimension。

模型：

其中：

是 weight vector，

是 bias/intercept。

12.2 Least Squares ★★★

课件以一维表示：

残差：

平方误差：

总 loss：

优化目标：

12.3 Closed-form Solution：课件中的公式要特别注意 ★★★

课件第 42 页原式写为：

以及：

这里需要提醒你：

课件第 42 页的分母按标准最小二乘推导看存在明显排版/公式问题。

标准形式应当是：

等价地：

因为：

而不是课件图中表面显示的：

建议期末如果要求“按课件公式写”，先确认老师是否在课堂上纠正过这一页。这里我没有静默修改课件，而是把课件原式和标准推导明确区分开。

13. 为什么 Linear Regression 不适合直接 Classification？

如果：

那么：

但 classification probability 应满足：

因此问题是：

Linear model 的 raw output 没有 probability constraint。

于是引入 sigmoid。

14. Sigmoid Function

它把：

映射成：

即：

所以：

线性 score 决定方向和强度，sigmoid 把 score 解释成 probability。

14.1 Logit ★★★

若：

则：

所以：

两者比：

取 ln：

其中：

称为 odds，

称为 log-odds/logit。

这是 Logistic Regression 名称的本质。

15. Logistic Regression Model ★★★

设：

则：

如果将 bias 合并到 feature vector：

则：

课件写：

而：

16. Bernoulli Likelihood ★★★

因为：

所以一个统一公式：

验证：

若

17. Maximum Likelihood Estimation

假设样本独立：

因此：

代入：

以及：

得到：

目标：

18. Log Likelihood ★★★

乘积不好优化，于是取 log：

得到：

代入 sigmoid：

这是 Logistic Regression 的核心优化目标。

为什么使用 log？

三个原因：

把 product 变成 sum；
数值计算更稳定；
monotonic transformation：

19. 为什么 Logistic Regression 不能像 Linear Regression 一样直接求 closed-form？

课件结论：

There's no closed form solution.

所以需要 iterative optimization：

Gradient Ascent：最大化 log-likelihood；
或 Gradient Descent：最小化 negative log-likelihood。

20. Gradient Descent

一般目标：

gradient：

指向 function 增长最快方向。

因此下降最快方向：

更新：

其中：

：第次参数；
：step size / learning rate；
：当前 gradient。

理想停止点：

课件把它描述为到达 local minimum。

21. Logistic Regression Gradient ★★★

课件后续把 sample index 改成，而表示 weight component。

梯度为：

其中：

：training sample index；
：feature/weight dimension；
：第个样本的第个 feature；
：true label；
：current predicted probability。

因为最大化，使用 gradient ascent：

其中：

是 learning rate。

课件特别提醒：

如果最小化 negative log likelihood，则写 gradient descent；如果直接最大化 log likelihood，则是 gradient ascent。

21.1 Gradient Update 的直觉 ★★★

这是第 49–50 页真正想解释的内容。

设单个 sample：

如果

更新：

因为：

所以：

朝的方向移动。

若模型已经非常确信：

则：

更新很小。

若模型严重低估 positive：

更新很大。

如果

更新：

也就是：

朝远离该 positive direction 的方向调整。

如果模型错误地认为该 negative sample 很可能为 positive：

更新力度大。

如果已经正确预测：

更新几乎为零。

所以 logistic gradient 的核心可以记成：

这个结构以后在 neural networks 里会反复出现。

22. Model Evaluation：为什么不能只看 Training Error？

训练过程中通常：

但 test error 常表现为：

text

high ←         testing error
     \        /
      \______/
             \
training error\____
────────────────────→ model complexity

三个阶段：

Underfitting

模型太简单：

training error 高
testing error 高

Good fit

模型表达能力适当。

Overfitting

模型过度学习 training details/noise：

training error 很低
testing error 上升

因此：

training accuracy 不能用于估计真正 generalization performance。

23. Confusion Matrix ★★★

二分类：

Actual \ Predicted	Positive	Negative
Positive	TP	FN
Negative	FP	TN

定义必须非常熟：

True Positive

真实正，预测正。

False Negative

真实正，预测负。

False Positive

真实负，预测正。

True Negative

真实负，预测负。

若：

为真实 positive 总数，

为真实 negative 总数，

则：

24. Accuracy 与 Error Rate ★★★

即：

所有样本中有多少预测正确。

Error rate：

且：

25. Sensitivity 与 Specificity ★★★

Sensitivity

也就是：

True Positive Rate / Recall。

问题：

真正的 positive 里，我抓到了多少？

Specificity

True Negative Rate：

问题：

真正的 negative 里，我正确排除了多少？

26. Precision 与 Recall

Precision ★★★

问题：

所有预测 positive 中，有多少真的 positive？

也称 exactness。

Recall ★★★

也就是 sensitivity。

问题：

所有真正 positive 中，我找到多少？

也称 completeness。

27. Precision–Recall Tradeoff ★★★

提高 positive prediction threshold：

模型更谨慎预测 positive。

通常：

而：

反之：

所以两者通常存在 tradeoff。

28. F Measure

课件定义 generalized ：

其中：

：Precision；
：Recall；
：控制对 recall 的重视程度。

课件说明：

assigning times as much weight to recall as to precision。

F1

当：

得到：

它是 precision 和 recall 的 harmonic mean。

为什么不用 arithmetic mean？

因为 harmonic mean 会被较小的一项显著拉低。

例如：

则：

所以必须：

Precision 和 Recall 都高，F1 才高。

29. 课件 Cancer Example ★★★

Confusion matrix：

Actual \ Predicted	Cancer Yes	Cancer No	Total
Cancer Yes	90	210	300
Cancer No	140	9560	9700

所以：

Sensitivity

Specificity

Accuracy

Error rate

Precision

Recall

F1

这个例子非常重要，因为它展示：

看起来非常高，但：

说明 70% 的癌症患者被漏掉。

所以：

imbalanced data 下 Accuracy 可以严重误导。

课件后面的类别不平衡部分正是从这里继续发展。

30. Holdout Method ★★★

给定数据集，随机切：

例如：

用于 training，

用于 testing。

优点：

simple
computationally cheap

问题：

一次随机 split 可能具有偶然性。

30.1 Repeated Random Subsampling ★★☆

重复 holdout 次：

最终：

这样降低单次 split 的偶然性。

31. k-Fold Cross Validation ★★★

把数据随机分为：

且：

第轮：

作为 test set，

剩余：

作为 training set。

最终：

课件指出：

非常常见。

31.1 Leave-One-Out ★★☆

特殊情形：

每次：

1 sample testing
samples training

适合：

small dataset。

代价：

computationally expensive。

31.2 Stratified Cross Validation ★★★

每个 fold 尽量维持 original class distribution。

例如原始：

则每个 fold 也大致保持：

在 imbalanced classification 中尤其重要。

课件同时提到 Bootstrap 也是 accuracy estimation 方法，但明确标注：

not covered。

所以考试如果完全按课件范围，不必深挖其具体公式。

32. ROC Curve

ROC：

Receiver Operating Characteristic。

源于 signal detection theory。

纵轴：

即 sensitivity/recall。

横轴：

注意：

32.1 ROC 是怎么形成的？ ★★★

分类器通常先输出：

或：

设 threshold：

若：

则预测 positive。

从：

逐渐降低到：

会产生不同：

连接起来就是 ROC curve。

32.2 AUC ★★★

课件给出：

Random-level classifier

接近 diagonal：

Perfect classifier

因此：

对于某个 operating point，越接近左上角通常越好；但 AUC 是整条 ROC 曲线的面积，曲线可能相交，不能由单个点的“左上程度”直接推出 AUC 大小。

ROC 体现的是：

TPR 与 FPR 的 tradeoff。

33. 为什么需要 Ensemble？

单个 classifier 存在：

variance
bias
noise sensitivity
model misspecification

于是：

combine multiple models to build a stronger model。

设：

最终组合成：

33.1 Ensemble 成功的两个条件 ★★★

课件给出的两个关键词必须记：

为什么？

假如所有 model 都犯同样错误：

text

M1 wrong
M2 wrong
M3 wrong

majority voting 仍然 wrong。

只有错误不完全 correlated：

text

M1 wrong on x1
M2 wrong on x2
M3 wrong on x3

ensemble 才能够互相补偿。

所以：

Ensemble 不只是“更多模型”，而是“多个性能不错且错误模式不同的模型”。

34. Bagging

Bagging：

核心是：

多个 model parallel learning。

34.1 Training ★★★

给定 training set：

对：

执行：

从中 sampling with replacement；
得到 bootstrap sample：
使用同一种 learning scheme 训练：

得到：

34.2 Classification

最终：

34.3 Regression

若是 numeric prediction：

即 average。

34.4 Why Bagging works? ★★★

不同 bootstrap draws 往往带来不同的训练样本，但不保证：

即使训练集不同，学习器也可能得到相同模型；bootstrap 主要是可能增加 model diversity。对于 high-variance、unstable models，且各模型误差不完全相关时，多个 models averaging/voting 才通常有助于降低 variance：

diversity 是倾向而非保证，variance reduction 也依赖模型之间的相关性。

特别适合：

unstable models，例如 decision trees。

课件使用的类比是：

多个医生独立诊断，最后 majority vote。

35. Boosting：从 Parallel 到 Sequential

Bagging：

text

M1
M2   ← parallel
M3

每个 model 相对独立。

Boosting：

text

M1 → M2 → M3 → ...

后一个 model：

专门关注前面 classifier 犯错的 samples。

所以课件概括：

Bagging	Boosting
Parallel	Sequential
bootstrap sample	error-focused reweighting
model 权重通常等价	final vote weighted
减少 variance	不断修正 mistakes

36. Boosting 基本机制 ★★★

设模型：

训练后：

将被 misclassified 的 samples 提高重要性。

使：

更加关注这些 hard examples。

最终：

individual models 的 vote 不是等权，而是根据 classifier accuracy 加权。

37. AdaBoost

AdaBoost 是最重要的 boosting 具体实现。

输入：

37.1 初始化 ★★★

每个样本权重：

即初始完全等权。

37.2 Weighted Classification Error ★★★

第轮训练：

使用 weighted error：

其中 indicator function：

所以：

错误样本根据其当前 weight 对 error 作贡献。

37.3 Error Rate

课件写：

如果 weight 已 normalization：

则：

37.4 Base Model Vote Weight ★★★

课件：

理解它非常重要。

如果：

则：

且 model 越准确：

所以：

strong base learner 获得更大 voting weight。

37.5 Update Sample Weights ★★★

课件给出：

因此：

分类正确

所以：

分类错误

所以：

错误样本 weight 增大。

因此下一轮：

更加关注上轮难以分类的 points。

通常之后还需要 normalization，使 weights 成为 distribution；课件重点放在上述 relative update。

37.6 Final AdaBoost Classifier

课件给出：

所以 AdaBoost 有两层 weighting：

training examples 有 weight；
base models 有 vote weight 。

这正是第 70 页强调的 “two weighting strategies”。

38. Gradient Boosting ★★☆

AdaBoost 的“关注错样本”是一种 specific boosting strategy。

Gradient Boosting 更一般。

需要：

differentiable loss；
weak learner，通常为 trees；
additive model。

即：

每次添加新的 learner：

使整体 loss 进一步降低。

课件指出 scalable implementation：

这就是：

text

Boosting
├── AdaBoost
└── Gradient Boosting
     └── XGBoost

39. Random Forest

Random Forest 可以理解为：

课件称它为：

Bagging with decision trees as base models。

39.1 Data Bagging ★★★

对每一棵 tree：

从原 training data 中 sampling with replacement。

即：

39.2 Feature Bagging ★★★

普通 Decision Tree：

每个 node 比较全部 features，选择最佳 split。

Random Forest：

每个 node 先随机抽取一部分 attributes，仅在这些候选属性中寻找最佳 split。

这是 Random Forest 比普通 Bagged Trees 更进一步的地方。

为什么？

如果某个 feature 特别强，普通 Bagging 中：

很多 trees 都会在 root 选同一个 feature。

导致 trees：

ensemble diversity 降低。

随机 feature selection：

使 ensemble 更 diverse。

39.3 Prediction

Classification：

39.4 Random Forest 两种构造方式 ★★☆

课件列：

Forest-RI

Random Input Selection：

每个 node 随机选个 attributes 作为 candidate，然后按照 CART methodology 选 best split。

Forest-RC

Random Linear Combination：

创建新的 attribute：

利用 random linear combinations 降低 classifiers correlation。

39.5 Random Forest 性质 ★★☆

课件指出：

accuracy 可与 AdaBoost 相比；
对 errors/outliers 更 robust；
对每次 split 随机选择多少 attributes 相对 insensitive；
比 typical bagging/boosting 快。

Ensemble recap 中还说：

Random Forest 与 XGBoost 是 tabular data 中最常用算法之一。

优点：

tabular performance 好；
no feature scaling；
scalable；
能一定程度处理 missing data。

缺点：

tuning 不好仍可能 overfit；
相比单棵 tree 缺乏 interpretability。

40. Bagging vs. Boosting vs. Random Forest 总比较 ★★★

属性	Bagging	Boosting	Random Forest
学习方式	Parallel	Sequential	Parallel
Data sampling	Bootstrap	Reweight difficult samples	Bootstrap
Base learner	任意	通常 weak learners	Decision Trees
Feature randomness	不要求	不要求	是
Final combination	Equal vote/average	Weighted vote/additive	Majority vote
主要思想	降低 variance	逐步纠正 errors	Bagging + decorrelation
对 outlier/noise	较稳健	可能更敏感	较稳健
Diversity 来源	data bootstrap	sequential error focus	data + feature randomness

41. Imbalanced Classification：为什么前面的 Accuracy 框架不够？

传统 classification 隐含：

各 class 数量大致 balanced，且不同错误 cost 差不多。

但现实常见：

例如课件：

HIV prevalence ≈ 0.4%
fraud accounts ≈ 2%
product defects
oil spills
disk failures

41.1 Accuracy Paradox ★★★

假设：

positive，

negative。

一个 classifier 永远输出：

则 accuracy：

但：

模型没有任何实际价值。

因此：

Accuracy 并非 class-imbalanced problem 的可靠指标。

课件建议看：

ROC Curve。

在实际考试分析中，前面学过的：

Sensitivity
Precision
Recall
F1

同样可以帮助识别这一问题。

42. Imbalanced Data：Data-Level Solutions

Oversampling ★★★

增加 minority class samples。

直觉：

使训练分布更加 balanced。

风险：

简单重复样本可能 overfit minority examples。

Under-sampling ★★★

随机删除 majority tuples：

优点：

数据更平衡、训练更快。

问题：

丢失 majority information。

Synthesizing ★★☆

不是简单复制 minority samples，而是：

合成新的 minority examples。

课件没有进一步展开具体生成算法，因此复习时掌握“synthesize new minority class examples”的概念即可，不应把课件没有讲的算法细节当作必考内容。

43. Algorithm-Level Solutions

Threshold Moving ★★★

通常：

但对于 rare positive：

False Negative 代价可能远大于 False Positive。

因此降低 threshold：

使 rare positive 更容易被识别。

结果：

通常同时：

这是显式地改变：

FP–FN tradeoff。

43.1 Class Weight Adjusting ★★★

若：

则给 positive/minority 或 FN 更高 training weight。

即错误 loss 不再等权：

其中 minority sample：

更大。

本质：

让 optimizer 更在乎 rare but costly mistakes。

43.2 Ensemble Techniques ★★☆

课件还指出：

可以通过 ensemble multiple classifiers 处理 imbalance。

没有在本章继续展开具体 imbalanced ensemble algorithm。

44. 全章“方法进化链”——这是最值得最后背的一页

44.1 Decision Tree 内部进化

text

Recursive partition
      ↓
需要判断哪个 split 最好
      ↓
Entropy
      ↓
Information Gain
      ↓
问题：偏好多值 attribute
      ↓
Gain Ratio

44.2 Bayesian 方法内部进化

text

Bayes theorem
     ↓
最大 posterior classification
     ↓
P(X|C) 高维联合分布太难估计
     ↓
Naïve conditional independence
     ↓
概率可拆成 product
     ↓
问题：任一 probability=0 → 整体=0
     ↓
Laplace correction

44.3 Lazy Learning 进化

text

Eager global model
     ↓
是否真的必须提前构造模型？
     ↓
Lazy / instance-based learning
     ↓
kNN
     ↓
1-NN 对 noise 敏感
     ↓
larger k / averaging
     ↓
所有邻居同权不合理
     ↓
distance-weighted kNN
     ↓
高维距离失效
     ↓
feature selection / weighting

44.4 Linear Model 进化

text

Linear Regression
     ↓
y = wᵀx+b
     ↓
输出 ∈ ℝ，不能直接当 probability
     ↓
Sigmoid
     ↓
P(Y=1|x)
     ↓
Maximum likelihood
     ↓
Log likelihood
     ↓
无 closed-form
     ↓
Gradient ascent/descent

44.5 Evaluation 进化

text

Training accuracy
     ↓
不能测 generalization
     ↓
Independent test set
     ↓
Accuracy
     ↓
class imbalance 下 misleading
     ↓
Confusion Matrix
     ↓
Sensitivity / Specificity
Precision / Recall / F1
     ↓
threshold-dependent
     ↓
ROC curve
     ↓
AUC

44.6 Accuracy Improvement 进化

text

Single classifier
     ↓
存在 variance / error
     ↓
Ensemble
     ↓
要求 Accurate + Diverse
     ↓
Bagging
  parallel + bootstrap
     ↓
Boosting
 sequential + error focus
     ↓
AdaBoost
 sample weights + model weights

Decision Tree + Bagging
     ↓
trees 可能高度 correlated
     ↓
Random feature selection
     ↓
Random Forest

45. 全章核心算法对比表 ★★★

Method	核心思想	Training	Prediction	主要假设	最大优点	最大问题
Decision Tree	Recursive partition	Eager	Tree traversal	无 distribution assumption	可解释	unstable / overfit
Naïve Bayes	Posterior maximization	Eager	probability product	conditional independence	极快	dependency 无法建模
kNN	Local similarity	Lazy	neighbor search	nearby points similar	灵活	slow prediction / high-dim
Logistic Regression	linear log-odds	Eager	sigmoid	linear decision boundary in feature space	简洁概率模型	nonlinear pattern 表达有限
Bagging	multiple bootstrap models	Parallel	voting	base learner diversity	降低 variance	interpretability ↓
Boosting	sequential error correction	Sequential	weighted combination	weak learners 可逐步改进	accuracy 高	noise/outlier 风险
Random Forest	bagged random trees	Parallel	voting	无强 distribution assumption	tabular 强、robust	black-box-ish

46. 期末公式总表 ★★★

这一节建议你最后直接背。

Entropy

Conditional Entropy

Decision Tree Info

Split Entropy

Information Gain

Split Information

Gain Ratio

Bayes

Naïve Bayes

Gaussian Density

Laplace

Distance-weighted kNN

Linear Regression

Least Squares

Sigmoid

Logit

Logistic Probability

Bernoulli Likelihood

Total Likelihood

Log Likelihood

Logistic Gradient

Gradient Ascent

Accuracy

Error Rate

Sensitivity / Recall

Specificity

Precision

F1

Generalized

ROC

AdaBoost Error

AdaBoost Classifier Weight

AdaBoost Sample Weight

AdaBoost Final Model

47. 最容易混淆的概念

Precision vs. Recall ★★★

记忆法：

Precision 看 prediction

我说是 positive 的，有多少是真的？

分母是：

Recall 看 reality

所有真正 positive，我找出了多少？

分母是：

Sensitivity vs. Specificity

认 positive。

认 negative。

Bagging vs. Boosting

记：

Bagging = bootstrap + parallel

Boosting = mistakes + sequential

Information Gain vs. Gain Ratio

记：

Gain 只问“uncertainty 降了多少”。

Gain Ratio 还问“你为了这个 gain 把数据切得有多碎”。

Eager vs. Lazy

记：

Eager：exam 前先把答案模型学出来。

Lazy：题目来了再查附近案例。

48. 期末重要度压缩版

如果最后时间非常紧，可以按照下面优先级。

★★★ 第一优先级

Supervised vs Unsupervised
Classification vs Regression
Train / Validation / Test
Decision Tree algorithm
Entropy
Information Gain 完整计算
Gain Ratio 及其动机
Bayes theorem
MAP classification
Naïve Bayes conditional independence
Naïve Bayes 多 feature probability calculation
Laplace smoothing
kNN
small vs large
Logistic Regression 的 sigmoid
logit
likelihood / log-likelihood
gradient update
Confusion Matrix
Accuracy / Precision / Recall / Specificity / F1
Holdout / k-fold / stratified CV
ROC / AUC
Accurate + Diverse ensemble
Bagging
Boosting
AdaBoost weights
Random Forest = data bagging + feature bagging
Imbalanced classification
为什么 accuracy 在 imbalance 下会失败
oversampling / undersampling / threshold-moving / class weighting

★★☆ 第二优先级

Continuous decision-tree splitting
Decision Tree pros/cons
Gaussian Naïve Bayes
Lazy vs Eager
distance-weighted kNN
curse of dimensionality
Training vs Testing Error
Gradient Boosting / XGBoost
Forest-RI / Forest-RC
ensemble pros/cons

★☆☆ 第三优先级

CBR applications
CBR indexing/backtracking
历史背景如 ROC 来源于 signal detection theory
References
Bootstrap evaluation，因为课件明确写 not covered

最后如果把整章浓缩成一句话，可以这样理解：

Classification 就是在带标签数据上寻找一个可泛化的 decision rule；Decision Tree 从空间划分角度解决它，Naïve Bayes 从概率推断角度解决它，kNN 从局部相似性角度解决它，Logistic Regression 从参数化 decision boundary 与概率建模角度解决它；随后通过独立验证、confusion-matrix metrics 和 ROC 判断模型是否真的有效，再通过 bagging、boosting、random forest 以及 imbalance-specific methods 修正单模型和数据分布本身的局限。

这基本就是这 83 页课件的“底层骨架”。

Chapter 7 — Classification: Advanced Methods 期末复习笔记

以下笔记严格以你上传的 86 页课件为主线整理，并结合课件中的图、公式和例子进行解释与必要推导。课件主体依次覆盖 Feature Selection、Bayesian Belief Networks、SVM、Rule/Pattern-Based Classification、Weakly Supervised Learning、Rich Data Type Classification，以及若干相关技术。

重要程度标记：

★★★：核心考点，建议能够定义、解释、推导、比较
★★☆：重要概念，通常需要解释工作原理/算法步骤
★☆☆：了解性质、应用或名词即可

0. 本章到底在解决什么问题？

前面的基础分类方法通常隐含几个很强的前提：

输入已经是质量良好的固定维特征向量；
特征之间的统计关系比较简单；
数据能被一个简单决策边界分开；
每个训练样本都有准确标签；
数据是静态、IID 的；
数据结构本身不复杂。

现实世界不断打破这些假设。

因此本章可以看成一棵非常清晰的“分类技术进化树”：

text

普通监督分类
│
├─ 问题 1：特征太多、冗余、无关
│   └─ Feature Selection
│      ├─ Filter
│      ├─ Wrapper
│      └─ Embedded
│          └─ LASSO → Elastic Net / Group Lasso / Fused Lasso
│
├─ 问题 2：Naive Bayes 的条件独立假设过强
│   └─ Bayesian Belief Network
│      └─ 用 DAG 显式表示条件依赖
│
├─ 问题 3：简单线性分类器泛化能力不足
│   └─ SVM
│      ├─ Hard-margin
│      ├─ Soft-margin
│      └─ Kernel SVM
│
├─ 问题 4：希望模型可解释，并利用高阶组合模式
│   └─ Rule / Pattern Classification
│      ├─ IF-THEN rules
│      ├─ Sequential Covering
│      └─ CBA / Association-based classification
│
├─ 问题 5：高质量标签太贵
│   └─ Weakly Supervised Learning
│      ├─ Semi-supervised
│      ├─ Active learning
│      ├─ Transfer learning
│      ├─ Distant supervision
│      └─ Zero-shot learning
│
├─ 问题 6：数据不是普通固定维向量
│   └─ Rich Data Classification
│      ├─ Stream
│      ├─ Sequence
│      └─ Graph
│
└─ 进一步扩展
    ├─ Multiclass classification
    ├─ Distance metric learning
    ├─ Interpretability / LIME
    ├─ Genetic algorithms
    └─ Reinforcement learning

如果你要抓住本章的底层逻辑，就是：

分类方法不断放松早期方法所做的假设：
从“特征已经准备好”到自动选特征；从“变量互相独立”到建模依赖；从“线性可分”到 margin + kernel；从“完整标签”到弱监督；从“固定向量”到序列、流和图。

1. Feature Selection 与 Feature Engineering

1.1 Feature Selection vs. Feature Engineering ★★★

课件 P2 首先区分两个非常容易混淆的概念。

Feature Selection

已有个特征：

目标是：

从已有特征中选择少量最有效的特征。

为什么需要？

Irrelevant feature

与预测目标基本没有关系。

例如：

student ID → GPA

学生 ID 一般不提供 GPA 的有效预测信息。

Redundant feature

两个或多个特征携带几乎相同的信息。

例如：

monthly income 与 yearly income

如果：

那么同时保留两个变量价值有限。

Feature Engineering

不是“选”，而是：

从已有变量构造新的、更有信息量的表示。

课件例子：

text

每日阳性病例
每日测试数
每日住院人数
        ↓
weekly positive rate

传统方法高度依赖 domain knowledge。

深度学习的一个重要发展则是：

自动学习 representation / feature。

2. Feature Selection 三类方法

课件 P3 给出了本节最重要的分类：

方法	Feature selection 与 classifier 的关系	优点	主要问题
Filter	分类模型训练之前完成	快、模型无关	未考虑具体 classifier
Wrapper	用 classifier 性能评价 feature subset	与模型高度适配	搜索昂贵
Embedded	训练模型时同时选特征	效率与模型适配兼顾	与具体模型绑定

这一页建议直接背熟。

3. Filter Methods

3.1 核心思想 ★★★

流程：

text

All Features
     ↓
goodness measure
     ↓
Selected Features
     ↓
Classifier

最重要特点：

Feature selection independent of the specific classifier.

即先用统计指标判断特征是否“好”，之后再训练分类器。

4. Fisher Score

4.1 公式 ★★★

课件 P4：

其中：

：当前特征的 Fisher score；
：类别数；
：类别编号；
：第类的样本数量；
：该特征在第类中的均值；
：该特征在所有样本中的总体均值；
：该特征在第类中的方差。

4.2 为什么这个公式合理？

分子：

衡量的是：

between-class variation，类间差异。

如果不同类别的平均值相距很远，这个量很大。

分母：

衡量：

within-class variation，类内差异。

如果同一个类别内部非常集中，则方差小。

因此：

理想特征应该满足：

类间距离大 + 类内距离小。

所以 Fisher Score 越大越好。

课件中的直观例子

例如用 income 判断是否购买电脑。

一个好的 income feature 应该满足：

买电脑人群平均收入与不买电脑人群明显不同；
买电脑的人内部收入比较接近；
不买电脑的人内部收入也比较接近。

正好对应：

4.3 其他 Filter 指标 ★★☆

课件还列出：

test：尤其适用于 categorical features
Information Gain
Mutual Information

这里主要需要记住：

Fisher score 是一个 feature-label association measure，而 filter 方法并不关心最终使用 SVM、tree 还是其他 classifier。

5. Wrapper Methods

5.1 为什么从 Filter 进一步发展到 Wrapper？ ★★★

Filter 的问题：

某个统计上“好”的特征，不一定对具体分类器真正有帮助。

于是 Wrapper 直接问：

“如果我用这些特征训练真实 classifier，性能到底怎么样？”

形成循环：

text

feature subset
     ↓
train classifier
     ↓
evaluate
     ↓
modify feature subset
     ↺

这就是 wrapper。

5.2 最大难题：组合搜索

个特征的非空子集总数：

因为每个特征只有：

两种状态，因此共有种组合，去掉空集得到：

复杂度：

指数级。

5.3 Stepwise Forward Selection ★★★

初始化：

每轮：

从未选择的 feature 中加入一个能够带来最大 classifier performance improvement 的特征。

例如：

text

{}
↓
{x3}
↓
{x3,x7}
↓
{x3,x7,x2}
...

问题：

Greedy search，没有保证得到 global optimum。

因为早期选错的变量一般不会重新删除。

5.4 Stepwise Backward Elimination

反过来：

每轮删除一个影响最小的特征。

5.5 Hybrid

结合 forward 和 backward。

例如：

加两个，再尝试删一个。

核心目标是缓解纯 greedy search 的不可逆问题。

6. Embedded Methods 与 LASSO

这是 Feature Selection 中最重要的数学部分之一。

6.1 从 Wrapper 到 Embedded 的逻辑 ★★★

Wrapper 的问题：

每测试一个 feature subset 都要重新训练模型。

计算昂贵。

Embedded 方法进一步把问题改成：

是否可以直接在训练 objective 中加入“少用 feature”的偏好？

答案就是 sparse learning。

7. LASSO ★★★

LASSO：

Least Absolute Shrinkage and Selection Operator.

课件 P6 给出：

又因为：

所以：

其中：

：训练样本数量；
：特征数量；
：第个样本；
：真实输出；
：预测；
：参数；
：正则化强度；
： norm。

课件公式下标从开始；这里保持其基本含义。实际实现中 intercept 是否正则化由具体定义决定。

7.1 为什么 LASSO 是 Feature Selection？

真正希望惩罚的是：

即：

有多少特征被选择。

但是非凸、离散的组合问题。

因此使用：

作为 convex approximation。

因为会产生：

的精确稀疏解。

于是：

这就是 embedded feature selection。

8. Coordinate Descent

8.1 为什么 LASSO 不直接普通求导？ ★★★

在：

处不可微。

课件 P7 给出的条件是：

若：

其中：

：convex + smooth；
每个：convex，但允许 non-smooth；
非光滑部分能够按 coordinate separable；

则 coordinate descent 可用于求 global minimum。

LASSO 恰好：

是 smooth convex，

而：

虽然 non-smooth，却是 coordinate-wise separable。

9. Coordinate Descent for LASSO

每一轮只更新一个参数，其他参数固定。

定义 partial residual：

含义：

把除第个 feature 外的所有 feature 已解释掉的部分扣掉。

于是只剩下：

先看没有 LASSO penalty 的一维 least squares：

课件假设每个 feature 已标准化：

于是该 coordinate 上的 LASSO 问题可写成：

整个高维优化问题因此变成一个一维问题。

10. Soft Thresholding 推导 ★★★

这是本章最值得自己手推一遍的公式之一。

要解：

Case 1：

此时：

所以：

求导：

令其为 0：

要求，因此：

Case 2：

此时：

所以：

求导：

得到：

要求，所以：

Case 3：靠近 0

当：

最优解就是：

因此：

也可以写成经典 soft-threshold operator：

10.1 直觉

普通 least square 想让：

penalty 则向原点拉：

text

βt > λ        → βt - λ
|βt| ≤ λ      → 0
βt < -λ       → βt + λ

因此：

小 coefficient 被直接压成 0，大 coefficient 也会被 shrink。

这正是：

Shrinkage + Selection。

11. Beyond LASSO：Sparse Learning

11.1 Elastic Net ★★★

课件：

结合：

LASSO：
Ridge：

思想：

提供 sparsity，提供 shrinkage/stability。

11.2 Group LASSO ★★★

其中：

：feature groups 数量；
：第组特征对应的一整个 coefficient vector。

核心结构：

group 内用，group 之间具有类似的 sparsity。

结果不是：

text

某组中只删一个 feature

而倾向于：

text

整个 group 一起留下 / 一起删掉

11.3 Fused LASSO ★★★

第二个正则项：

鼓励：

所以适合：

相邻 feature 具有结构关系的情况。

课件总结为：

encourage co-select / co-un-select adjacent features.

12. Bayesian Belief Networks

12.1 从 Naive Bayes 到 Bayesian Network ★★★

Naive Bayes 假设：

即：

所有 feature 在给定 class 后条件独立。

Why it fails?

现实变量经常有依赖关系。

例如：

text

Smoking
   ↓
Lung Cancer
   ↓
Positive X-Ray

这些变量显然不是完全独立。

How Bayesian Network fixes it?

不再要求：

所有变量都独立。

而是：

用 directed acyclic graph 显式描述 conditional dependency structure。

13. Bayesian Network 两个组成部分 ★★★

1. DAG

Directed Acyclic Graph：

node → random variable
directed edge → dependency

必须：

例如：

text

A → B → C
↑       ↓
└───────┘

存在有向环，因此不是 Bayesian Network。

2. CPT

Conditional Probability Table。

描述：

对于父节点所有可能组合给出 conditional probability。

14. Bayesian Network 联合概率分解 ★★★

核心公式：

这是整部分最重要公式。

例如课件 P15：

text

F = Fire
T = Tampering
S = Smoke
A = Alarm

结构：

以及：

因此：

根节点：

没有 parents，所以直接使用 marginal probability。

另一个课件例子：

15. 三种基本连接结构与条件独立 ★★★

课件 P16 展示：

Chain / head-to-tail

联合概率：

给定：

所以 conditioning on 会 block path。

Fork / tail-to-tail

是共同原因。

给定后：

Collider / head-to-head

这是特别容易考反的情况。

未观察时：

路径本身被 collider 阻断。

但一旦观察：

或其 descendant，路径可能被打开。

这就是 Bayesian Network 中 d-separation 的核心直觉。

16. Training Bayesian Networks

课件 P17–18 划分成四个 scenario。★★☆

Structure	Variables	课件给出的处理
known	all observable	计算 CPT
known	some hidden	iterative optimization / gradient-descent-style search
unknown	observable	搜索 model space，重建 topology
unknown	hidden	最困难；课件称无良好通用算法

Scenario 1

结构已知，所有变量 observable。

只需估计：

即 CPT entries。

Scenario 2

network structure known，但存在 hidden variables。

课件描述：

probability weights 随机初始化；
iterative update；
每次向当前最优方向移动；
无 backtracking；
最终可能进入 local optimum。

期末答题最好按照课件措辞作答。

Scenario 3

structure unknown + variables observable。

需要：

search model space to reconstruct network topology.

也就是说不仅要学 probability parameters，还要学 graph structure。

Scenario 4

structure unknown + hidden variables。

同时不知道：

谁依赖谁；
隐变量取值是什么。

因此难度最高。

17. Plate Notation ★★☆

用于表示：

图模型中重复出现的一组 random variables。

课件约定：

shaded / solid node → observed
unshaded node → hidden

例如：

text

        x
        ↓
     ┌───────┐
     │   y   │
     │   N   │
     └───────┘

表示：

共享同一个结构，而不需要画次。

课件 P20 的例子：

Difficulty 按 Course 重复；
Intelligence 按 Student 重复；
Grade 与 course × student 对相关。

Plate notation 的目的就是：

将重复的 probabilistic structure 压缩表达。

18. SVM：Support Vector Machine

这是本章数学分量最大的部分。建议作为期末第一优先级。

19. Classification 的数学定义

二分类：

希望学习：

例如电影评论：

20. SVM 的核心进化逻辑 ★★★

普通 linear classifier 的问题并不仅是：

能不能找到一条分界线。

因为线性可分时通常存在无穷多分界线。

SVM 问的是：

哪一条分界线最好？

答案：

即：

离两类最近训练样本尽可能远。

这引出了：

margin
support vectors
quadratic optimization

21. Linear SVM：Hyperplane

决策超平面：

其中：

：样本；
：法向量；
：bias/intercept。

二维：

分类：

22. 为什么 margin boundary 写成？

课件 P27 特别写了一句：

how about 0.5?

这是很好的潜在考点。

两条 margin boundary：

问题：

为什么一定是 1？不能是 0.5 吗？

因为：

和：

描述的是完全相同的 hyperplane。

即：

存在任意 scale ambiguity。

因此可以人为选择 normalization：

选择 0.5 也完全可以，只需重新缩放。

选择只是最方便的标准化。

23. Hard-margin SVM Constraints

对于：

要求：

对于：

要求：

可以统一成：

因为：

当：

即：

24. 点到 Hyperplane 的距离 ★★★

一般二维直线：

点到直线距离：

推广到维：

对于已知正确 label 的训练样本，可写为：

因为正确分类时：

不再需要绝对值。

25. 从 Maximum Margin 到 SVM Optimization

想让最近样本距离最大：

由于前面利用 scaling freedom 规定：

问题就变成：

等价于：

又等价于更方便的 convex objective：

subject to：

这就是 hard-margin linear SVM。

26. Margin 为什么等于？ ★★★

两条 margin hyperplanes：

和：

平行超平面距离公式：

因此：

所以：

整个 SVM primal formulation 就串起来了。

27. Support Vectors ★★★

位于：

上的训练样本称：

它们是：

离 decision boundary 最近、真正决定 margin 的训练样本。

远离 boundary 的样本发生轻微变化，一般不会影响最终 hyperplane。

这是 SVM 名称里 “support vector” 的来源。

28. Hard-margin 的问题：现实数据往往不可线性分

如果存在 noise/outlier：

text

class A   class A    class B
          ×
----------------------------

要求所有样本都严格满足：

可能根本无可行解。

29. Soft-margin SVM ★★★

解决办法：

不要求每个训练点严格在 margin 外。

引入 slack variable：

新约束：

目标函数：

subject to：

30. Slack variable 各种情况 ★★★

以下等式默认取优化解中的最小可行值：

一般可行解只要求；由于目标函数惩罚，最优解可以取上述最小 slack。

样本正确，而且在 margin 外或 margin 上。

样本：

进入 margin，但仍然在 decision boundary 正确的一侧。

正确分类。

位于：

decision boundary 上。

样本已经到了错误一侧：

misclassified。

非常建议把这一组关系直接记下来。

31. 的作用 ★★★

目标：

有两个竞争目标：

第一项

希望：

因此：

第二项

希望 violation 少。

因此：

小

错误 penalty 小。

允许更多 margin violation：

通常 margin 更宽。

大

错误昂贵：

模型更努力拟合训练数据。

课件 P31 的四幅图正是在展示这一点。

32. 非线性分类：第二条路线

Soft margin 解决的是：

“允许一些错误”。

但另一种思路是：

也许数据只是在当前 representation 中不线性可分。

因此：

把原始数据映射到更高维空间。

然后在新空间寻找 linear hyperplane。

课件用 XOR 作为典型例子。

33. Cover's Theorem ★★☆

课件 P33：

A complex pattern-classification problem, cast nonlinearly into a high-dimensional space, is more likely to be linearly separable than in a low-dimensional space.

即：

注意不是说：

“任何随便的高维映射都必然可分”。

而是在适当 nonlinear mapping 下，linear separability 更有可能实现。

34. Kernel Trick ★★★

问题来了。

如果：

是百万维甚至无限维，显式计算它非常昂贵。

SVM 中真正大量需要的是：

于是定义：

直接在原始输入上算 kernel：

而不用显式构造：

这就是：

核心思想：

implicitly operate in high-dimensional feature space.

35. 三种典型 Kernel ★★★

Polynomial Kernel

课件：

其中：

：polynomial degree。

Gaussian RBF Kernel

其中：

：控制 kernel width。

如果：

则：

距离很远时：

所以可以理解为 similarity measure。

Sigmoid Kernel

其中：

：scale；
：offset。

36. 多分类 SVM ★★★

SVM 本质是 binary classifier。

扩展到类有两种经典方法。

One-vs-Rest / One-vs-All

每个 classifier：

text

class i
vs.
all other classes

需要：

个 classifiers。

One-vs-One

每对类别训练一个：

一共有：

个 classifiers。

37. SVM Scalability

一个很容易判断错的地方：

SVM 适合 high-dimensional data
≠
SVM 适合 massive-number-of-samples data。

课件明确区分：

对 dimension

表现好。

trained classifier complexity 很大程度由：

决定，而不是单纯取决于 feature dimensionality。

对 number of samples

训练时间和 memory 不自然 scalable。

因此：

课件还提到 hierarchical micro-clustering 用于 scaling SVM。

38. SVM 总结 ★★★

Pros：

elegant mathematical formulation；
convex optimization → global optimum；
small datasets 上表现好；
kernel 灵活；
可适配 semi-supervised learning。

Cons：

large-scale training scalability 较差。

Applications：

handwritten digit recognition；
object recognition；
speaker identification；
time-series prediction；
classification；
regression。

39. Rule-Based Classification

39.1 IF-THEN Rule ★★★

形式：

即：

40. Coverage 与 Accuracy ★★★

设：

其中：

：IF 部分；
：THEN class。

Coverage

课件定义：

被 IF condition 覆盖的数据占比。

可写为：

注意：

coverage 不关心 THEN 是否正确。

Accuracy

在 rule 覆盖的数据中，预测正确比例：

所以：

coverage → rule 能管多少数据；
accuracy → 管到的数据里有多可靠。

41. Rule Conflict Resolution ★★☆

如果多个 rules 同时 triggered，需要解决冲突。

课件给出三类策略。

Size ordering

优先选择：

attribute tests 最多的 rule。

即最 specific / “toughest requirement”。

Class-based ordering

按照：

class prevalence；
misclassification cost

排序。

Rule-based ordering / Decision List

所有 rules 排成一张 priority list。

可根据：

rule quality；
expert knowledge

决定顺序。

分类时：

first matching rule wins。

42. 从 Decision Tree 提取 Rules

课件 P42：

每一条 root → leaf path 对应一条 rule。

例如：

text

age = young
    ↓
student = yes
    ↓
buy = yes

得到：

Decision-tree extracted rules 有两个性质：

同一个 sample 不会沿两条 tree path。

以及：

完整 tree 应该为输入提供某条 path。

优点：

Rules 通常比大型 decision tree 更容易理解。

43. Sequential Covering Method ★★★

Decision tree：

同时学习整组 rules。

Sequential covering：

一条一条学 rule。

这是两者的核心区别。

Step 0

初始化：

Step 1

学习一条 rule 。

目标：

覆盖很多目标类别的 tuple，同时覆盖尽量少其他类别。

Step 2

删除已被该 rule 覆盖的数据：

text

data
 ↓ learn rule
covered examples
 ↓ remove
remaining examples

Step 3

在剩余数据上重复。

终止条件例如：

没有 training examples；
新得到 rule 的质量低于 threshold。

这也解释了为什么叫：

44. Pattern-Based Classification

44.1 为什么从单 feature 进一步走向 pattern？ ★★☆

传统 feature：

单个属性。

但很多分类信息存在于高阶组合中。

例如：

text

Apple

本身歧义很强。

而：

text

Apple pie
Apple iPad

具有更强 discrimination。

所以 pattern 提供：

higher-order features；
compact representation；
discriminative representation。

此外 pattern mining 还能处理：

graphs；
sequences；
semi-structured data；
unstructured data。

因此 Pattern-Based Classification 本质是：

45. CBA：Classification Based on Associations ★★★

CBA：Liu, Hsu & Ma, KDD 1998。

首先挖掘：

high-confidence + high-support class association rules。

形式：

LHS：

conjunction of attribute-value pairs。

RHS：

class label。

标准 association rule 定义可以写成：

也就是：

Classification

rules 先按照：

confidence；
support

降序排列。

对于 test sample：

使用第一个 matching rule。

如果没有：

default rule。

Why CBA can outperform some tree methods?

因为它能直接发现：

这样的 multi-attribute high-order association。

而某些传统算法更倾向于逐个 attribute 做局部 decision。

46. Weakly Supervised Learning 总图

课件包括五类：

text

Weak Supervision
│
├─ Semi-supervised Learning
├─ Active Learning
├─ Transfer Learning
├─ Distant Supervision
└─ Zero-shot Learning

共同的核心痛点：

perfect labeled training data 很昂贵或根本不存在。

47. Semi-Supervised Learning

目标：

其中：

通常无标签数据远多于有标签数据。

48. Self-Training ★★★

课件 P52：

选择 learning method；
用 labeled data 训练 classifier；
classifier 预测 unlabeled data；
选择 confidence 最高的 unlabeled tuple；
将其预测 label 当作 pseudo-label；
加入 labeled set；
repeat。

流程：

text

small labeled set
      ↓
train classifier
      ↓
predict unlabeled
      ↓
take highest-confidence prediction
      ↓
pseudo-label
      ↓
add to labeled set
      ↺

Why can it fail?

因为模型可能：

confidently wrong。

错误 pseudo-label 被加入之后：

形成 confirmation bias。

因此 high confidence 只是 heuristic，而不是 correctness guarantee。

49. Co-Training ★★★

Self-training 只有一个 classifier。

Co-training 进一步假设存在：

两组 non-overlapping feature views。

例如：

训练：

和：

步骤：

用第一组 features 训练；
用第二组 features 训练；
两者分别预测 unlabeled examples；
最有信心的 pseudo-label 加入的 training set；
最有信心的 pseudo-label 加入的 training set；
repeat。

本质：

两个不同 views 相互提供监督信号。

50. SSL 什么时候有效？Clustering Assumption ★★★

课件 P54：

于是 decision boundary 应该尽量：

穿过 low-density region，而不是切开一个 dense cluster。

课件例子：

仍然寻找 max-margin boundary，但同时利用 unlabeled data 的 clustering structure。

51. Manifold Assumption ★★★

课件 P55：

注意这里真正重要的不是：

原始 Euclidean space 中一定很近。

而是：

数据集中真正具有意义的低维 manifold neighborhood 相近。

典型方法：

graph-based SSL。

可以把 sample 构造成 graph：

node = sample；
edge = similarity。

标签沿 graph structure 传播。

52. Active Learning ★★★

Semi-supervised learning 说：

“标签没有，就利用 unlabeled structure。”

Active learning 进一步说：

“既然标注很贵，那就只标最值得标的数据。”

目标：

oracle 可以是：

human annotator；
domain expert。

Query strategy

课件列出：

Uncertainty Sampling

选择模型最不确定的样本。

例如二分类概率：

这种样本通常最接近 boundary。

Query-by-Committee

训练多个 classifiers。

查询：

committee disagreement 最大的样本。

Version Space

version space：

与已有 labeled data 一致的全部 hypothesis 集合。

理想 query 应尽可能强烈地缩小该 hypothesis space。

Decision-Theoretic Approach

选择：

预期能带来最大 utility / error reduction 的 query。

53. Active Learning vs SSL vs Transductive Learning ★★★

课件 P57 的图非常值得理解。

方法	Unlabeled data	是否人工 query	输出目标
Active Learning	有	是	学一般 classifier
SSL	有	否	学一般 classifier
Transductive Learning	有	否	主要直接预测当前 unlabeled set

最关键区别：

Active learning

text

unlabeled → query oracle → ground-truth label

Pure SSL

text

labeled + unlabeled
       ↓
     model
       ↓
future test data

Transductive learning

重点不是学习一个未来任意的通用函数，而是：

对当前给定 unlabeled set 的 labels 做预测。

54. Transfer Learning ★★★

目标：

课件例子：

Source：

electronics review sentiment classification

Target：

movie review sentiment classification

它们共享：

positive / negative sentiment knowledge；

但 domain distribution 不完全一致。

55. TrAdaBoost

一种：

核心思路：

Source data 并不是全部有用，因此给不同 source examples 不同权重。

普通 Boosting：

如果 example 被错分：

下一轮提高其 weight，让 classifier 更关注困难样本。

TrAdaBoost 对 source samples 则不同。

如果 source tuple 在 target-oriented classifier 下持续被误分：

说明这个 source sample 可能不适合 target domain。

因此：

也就是：

transfer relevant examples，suppress irrelevant examples。

56. Negative Transfer ★★★

Transfer learning 最大风险：

如果 source 和 target 相差太远：

transfer knowledge 反而比不 transfer 更差。

因此需要量化：

课件列举：

transfer margin；
divergence metric。

57. Distant Supervision ★★★

目标：

自动产生大规模 labeled tuples。

核心 trade-off：

例 1：Twitter sentiment

如果 tweet 中含：

text

:-)

赋 positive label。

含：

text

:-(

赋 negative。

例 2：URL category

tweet 含某 URL，则：

用 URL 的 ODP category 作为 tweet label。

YouTube link：

使用 video label 作为 tweet label。

应用

social-media classification；
NLP relation extraction。

最大问题

heuristic labeling function 并不总可靠。

例如：

text

:)

可能出现在：

positive；
neutral；
sarcasm；
negative

语境中。

所以：

另一个研究问题是：

如何构造 labeling functions。

58. Zero-Shot Learning ★★★

问题：

训练类别：

text

owl
dog
fish

测试时突然出现：

text

cat

普通 supervised classifier 根本没有学习：

Zero-shot learning 目标：

59. 为什么 Zero-Shot 有可能做到？

必须引入：

课件用 semantic attributes。

例如动物类别可以表示成：

text

four legs
has wings
retractable claws
super night vision

于是即使从未训练过 cat image，仍知道：

text

cat:
four legs = yes
wings = no
retractable claws = yes
...

60. Semantic Attribute Classifier

课件 P63 的图可以抽象为：

训练：

其中：

：原始 feature matrix；
：已知 training class labels；
：semantic attributes；
：semantic attribute classifier。

先学习：

即：

从 image/features 预测 semantic attributes。

之后对于测试样本：

得到：

再将：

和 unseen classes 的 attribute prototype 比较。

标准形式可以理解为：

其中：

：class 的 semantic attribute description。

课件核心一句话：

semantic attributes 是 seen → unseen 的 bridge。

Generalized Zero-Shot Learning

普通 ZSL 假设：

test 一定来自 unseen class。

Generalized ZSL：

test 可能来自 seen 或 unseen classes。

因此更困难。

61. Classification with Rich Data Types

传统 classifier 假设：

固定维 vector。

现实则可能是：

stream；
sequence；
graph。

所以本节本质问题：

如何把普通 classification machinery 推广到非固定向量数据。

62. Stream Data Classification ★★★

例子：

fraudulent transaction detection。

交易不断到来：

text

t1 → t2 → t3 → ...

不能简单：

text

收集全部数据
↓
一次 train
↓
永久不变

四大挑战 ★★★

课件 P66：

1. High arrival speed

数据产生太快。

2. Infinite length

理论上 stream 没有终点。

3. One-pass constraint

通常没有能力反复遍历旧数据。

4. Concept drift

最重要。

随时间发生变化：

因此旧 classifier 会逐渐过时。

63. Stream Classification via Ensemble

课件 P67 的逻辑：

新 chunk

只用最新 chunk 训练一个新 classifier。

对应：

high arrival rate。

One-pass update

每个 incoming tuple：

用一次来训练 current classifier 和更新 ensemble weights。

对应：

one-pass constraint。

Dynamic classifier weights

较新的、与当前 concept 更相关的 classifier：

过时 classifier：

因此适应：

64. VFDT / Hoeffding Tree ★★☆

VFDT：

Very Fast Decision Tree。

课件提到：

Hoeffding tree；
用数据 stream 中的 sampled / incremental statistics 建树；
sliding window 强调 recent stream data。

Sliding window 的核心：

只保留最近范围信息，从而降低旧 concept 的影响。

应用：

marketing；
network monitoring；
sensor networks。

65. Sequence Classification

Sequence：

是 ordered list。

例子：

sentence；
DNA；
customer transaction history。

Sequence classification：

例如：

sentence → positive/negative；
DNA segment → coding/non-coding；
customer sequence → high-value/ordinary。

课件也提到另一类：

每个 timestamp 都预测一个 label。

66. Sequence Classification via Feature Engineering ★★★

第一类思路：

text

sequence
 ↓
fixed-dimensional vector
 ↓
conventional classifier

Symbolic sequence：n-gram

课件 DNA：

unigram candidate：

频数：

Bigrams 例如：

实际该 sequence 中：

其他为 0。

课件同时展示两种 representation：

Binary vector

是否出现：

Frequency vector

数值 sequence：

先 discretization 成 symbolic sequence。

课件还指出现代方法：

RNN and related techniques。

67. Sequence Classification via Distance / Kernel

如果不想把 sequence 强制转换成 ordinary feature vector，也可以：

直接定义 sequence-to-sequence similarity。

原因：

KNN

核心需要：

Kernel SVM

核心需要：

所以只要定义适合 sequence 的：

distance；
kernel；

即可复用传统 classifier。

课件列：

Distance：

Euclidean；
DTW。

Kernel：

string kernel。

68. Dynamic Time Warping ★★★

DTW 用于：

两条时间轴存在速度变化、局部拉伸/压缩时比较 sequence。

课件例子：

局部 cost：

动态规划：

三个 transition 分别对应课件中的：

jump an element of ；
jump an element of ；
match and 。

示例 alignment：

对应局部 costs：

因此该 alignment cost 为：

核心：

不要求只能和对齐。

因此可以吸收 temporal distortion。

69. Graph Data Classification

Graph：

其中：

：nodes；
：edges。

实例：

social networks；
power grid；
transaction networks；
biological networks。

70. Node-Level vs Graph-Level Classification ★★★

Node-level

预测：

例如：

webpage classification。

Graph-level

预测：

例如：

molecular graph → toxicity。

这是一个很常见的概念辨析题。

71. Graph Classification Methods

Feature Engineering

先提取 node / graph feature。

Node-level

例如：

degree；
number of triangles；
centrality；
PageRank。

然后：

Graph-level

例如：

graph size；
diameter；
number of triangles。

Deep learning

课件指出：

GNN 可以自动学习 node / graph representations。

Proximity-based classification

另一条路线：

定义 node/graph proximity。

然后使用：

类型 classifier。

73. Multiclass Classification ★★★

再次从一般 classification 角度总结：

OVA

classes：

AVA

任意两类别训练：

Error-Correcting Coding

给每个 class 一个 error-correcting code。

把 multiclass prediction 转化为多个 binary prediction，然后选择最接近的 codeword。

目的：

利用 code redundancy 改善 multiclass robustness。

74. Multiclass ≠ Multilabel ★★★

Multiclass

一个 tuple 只能属于一个类别：

Multilabel

同一个 tuple 可以同时拥有多个 labels：

例如：

text

image:
{dog, outdoor, snow}

因此：

75. Distance Metric Learning ★★★

普通 Euclidean distance：

默认所有 feature：

同样重要、同样 scale，并且彼此没有相关结构。

这未必适合某个 classification task。

于是：

自动学习距离 metric。

76. Mahalanobis Distance

课件 P77：

其中：

：待学习矩阵；
：positive semidefinite。

如果：

则退化为 Euclidean distance。

因此 Mahalanobis distance 可以视为：

学习 feature scaling + correlation。

77. Metric Learning Optimization

课件：

subject to：

以及：

其中：

：similar pairs；
：dissimilar pairs。

目标：

把 dissimilar pairs 推远。

约束：

similar pairs 总距离保持小。

所以核心就是：

课件强调这是 convex formulation。

78. Interpretability of Classification

定义：

模型能够以用户可理解方式解释 prediction 或 classification process 的能力。

天然比较 interpretable：

decision tree；
linear classifier。

复杂 black-box 则需要 post-hoc explanation。

79. LIME ★★★

LIME：

三个关键词必须理解。

Local

不试图解释整个模型。

只解释：

附近。

Interpretable

使用简单 surrogate：

sparse linear model 等。

Model-Agnostic

black-box 内部结构不重要，只需要能够 query：

课件 P78 的流程：

text

black-box f
     ↓
choose point x0
     ↓
sample points near x0
     ↓
query f on them
     ↓
weight nearby samples more heavily
     ↓
fit simple surrogate g
     ↓
use g to explain f locally

图中的局部 surrogate 示例：

核心 trade-off：

其他课件提及：

counterfactual explanation；
influence function。

80. Genetic Algorithms ★★☆

核心来自 natural evolution：

Procedure

1. Initial population

随机生成一组 rules。

rule 用 bit string 表示。

课件：

IF AND NOT THEN

可编码为：

text

2. Fitness

例如：

3. Selection

高 fitness rules 更容易 survive。

4. Crossover

课件例：

text

Parent 1: 110010
Parent 2: 101111

          ↓ crossover

Child:    110111

5. Mutation

例如：

text

Before: 110111
After:  111111

随机改变 bits，增加 population diversity。

6. Repeat

直到：

fitness threshold satisfied。

81. Reinforcement Learning 与 Classification

课件最后通过二者对比结束。

Classification

收到：

即：

true class label。

目标：

学 classifier。

Reinforcement Learning

收到：

例如：

但系统不会直接告诉你：

“正确 action 是哪一个”。

需要自己通过 interaction 学出来。

82. Multi-Armed Bandit ★★☆

设有：

个 arms。

每个 arm 对应 action，并有未知 expected reward：

目标：

不断选择 action，使 cumulative reward 尽可能高。

问题核心是：

课件列出的 algorithms：

-greedy；
Upper Confidence Bound, UCB。

应用：

online ads；
robotics；
chess。

83. 整章“方法演进链”总结

这是我建议你期末前真正记住的一条逻辑链。

Feature Selection

text

Filter
  ↓
问题：忽略 classifier 本身
  ↓
Wrapper
  ↓
问题：feature subset 搜索太贵，2^p
  ↓
Embedded
  ↓
LASSO
  ↓
问题：独立 feature sparsity 无法表示结构
  ↓
Elastic / Group / Fused Lasso

Probabilistic Classification

text

Naive Bayes
  ↓
问题：Xi ⟂ Xj | Y 太强
  ↓
Bayesian Network
  ↓
DAG + CPT
  ↓
局部 conditional independence
  ↓
joint probability factorization

SVM

text

普通 separating hyperplane
  ↓
问题：线性可分时有无穷多个
  ↓
Maximum Margin
  ↓
Hard-margin SVM
  ↓
问题：noise / outlier → 不可严格线性分
  ↓
Slack Variable
  ↓
Soft-margin SVM
  ↓
问题：真正 nonlinear structure
  ↓
φ(x) high-dimensional mapping
  ↓
问题：显式 mapping 太贵
  ↓
Kernel Trick

Rule / Pattern

text

Decision Tree
  ↓
可转换成 IF-THEN rules
  ↓
希望直接从 data 学 rules
  ↓
Sequential Covering
  ↓
希望捕捉高阶组合
  ↓
Pattern-Based Classification
  ↓
Association Rule Mining + Classification
  ↓
CBA

Weak Supervision

text

Full supervision
   ↓ 标签贵
Semi-supervised
   ↓ 希望主动决定标谁
Active learning
   ↓ source task 已经有知识
Transfer learning
   ↓ 大量 noisy heuristic labels 可获得
Distant supervision
   ↓ test class 甚至没出现
Zero-shot learning

Rich Data

text

fixed-dimensional vector
      ↓
stream  → concept drift / one-pass
sequence → ordering / temporal deformation
graph    → relational structure

84. 最容易混淆的概念对照表

概念	最核心的问题	最核心解决办法
Filter	哪些 feature 单独看“好”？	Statistical score
Wrapper	哪组 feature 对 classifier 最好？	Train/evaluate subsets
Embedded	如何训练时直接选 feature？	Regularization
LASSO	feature sparsity
Group LASSO	group sparsity	within groups + sparsity across groups
Fused LASSO	neighboring structure	$
Naive Bayes	简单概率分类	全 feature 条件独立
Bayesian Network	feature 有依赖	DAG + CPT
Hard SVM	完全线性可分	max margin
Soft SVM	noise / overlap	slack
Kernel SVM	nonlinear boundary	implicit
Sequential Covering	直接学 rules	learn-remove-repeat
CBA	multi-attribute pattern	association rules
Self-training	unlabeled data	own pseudo-label
Co-training	两组 feature views	classifiers teach each other
Active Learning	labels expensive	query useful samples
Transfer Learning	target data 少	transfer source knowledge
Distant Supervision	labels scarce	heuristic noisy labels
Zero-shot	unseen classes	semantic side information
Stream	infinite/changing data	online / ensemble / recent weighting
Sequence	ordered structure	n-gram / DTW / kernel / RNN
Graph	relational structure	graph features / proximity / GNN
Metric Learning	Euclidean metric 不合适	learn
LIME	black box 难解释	local surrogate

85. 期末最优先掌握的数学公式

如果复习时间有限，这组必须会默写并解释。

Fisher Score

关键词：

between-class large / within-class small。

LASSO

Coordinate residual

Soft threshold

Bayesian Network

SVM hyperplane

SVM constraint

Point-to-plane distance

Margin

Hard-margin SVM

subject to：

Soft-margin SVM

subject to：

Kernel Trick

RBF

DTW

Mahalanobis distance

86. 最可能出现的“为什么”型考试问题

最后建议重点检查自己是否能不看答案解释下面这些问题：

为什么 Feature Selection 与 Feature Engineering 不一样？ ★★☆
为什么 Fisher Score 要“类间方差 / 类内方差”？ ★★★
为什么 Wrapper 比 Filter 更 classifier-specific，但更昂贵？ ★★★
为什么 exhaustive feature selection 是？ ★★★
为什么 LASSO 能做 feature selection，而 Ridge 通常不能产生精确 sparsity？ ★★★
Soft thresholding 为什么在时直接得到 0？ ★★★
Group LASSO 和普通 LASSO 的 sparsity 有什么区别？ ★★★
Naive Bayes 的核心限制是什么？Bayesian Network 如何解除？ ★★★
为什么 Bayesian Network 必须是 DAG？ ★★☆
如何根据 graph 写出 joint probability factorization？ ★★★
Chain、fork、collider 的 conditional independence 有什么区别？ ★★★
为什么 SVM 不只是“找到一条分界线”？ ★★★
为什么 margin boundary 可以规定成，0.5 行不行？ ★★★
为什么最大 margin 等价于最小？ ★★★
为什么 margin 是？ ★★★
Support vectors 为什么决定最终 classifier？ ★★★
分别代表什么？ ★★★
大小如何改变 soft-margin behavior？ ★★★
Kernel trick 为什么能避免显式计算高维？ ★★★
OVR 和 OVO 分别需要多少 classifiers？ ★★★
Coverage 与 Accuracy 的 denominator 有什么区别？ ★★★
Sequential Covering 与 decision-tree induction 有什么不同？ ★★☆
为什么 pattern-based classification 可以比单 feature 更 discriminative？ ★★☆
Self-training 最大风险是什么？ ★★★
Co-training 为什么需要两个 feature views？ ★★★
SSL 的 clustering 和 manifold assumptions 分别是什么？ ★★★
Active Learning 与 SSL 的关键区别是什么？ ★★★
Transductive Learning 与普通 inductive SSL 有什么区别？ ★★★
什么是 negative transfer？ ★★★
为什么 Distant Supervision 同时具有“large”与“noisy”两个特点？ ★★★
Zero-shot 如何通过 semantic attribute 实现 seen→unseen transfer？ ★★★
Stream classification 为什么不能把普通 batch classifier 原封不动搬过去？ ★★★
Concept drift 是什么？ ★★★
n-gram 怎样把 sequence 转成 fixed vector？ ★★★
DTW 比 Euclidean sequence distance 多解决了什么？ ★★★
Node-level 与 graph-level classification 有什么不同？ ★★★
Mahalanobis metric learning 在学习什么？ ★★★
LIME 为什么叫 local、interpretable、model-agnostic？ ★★★
Genetic Algorithm 的 selection/crossover/mutation 各负责什么？ ★★☆
Classification 的 instructive feedback 与 RL 的 evaluative feedback 有什么区别？ ★★★

如果这 40 个问题和上面的关键公式都能独立回答，这份 86 页课件的考试主体基本就已经覆盖完整；P83–86 主要是参考文献页，不再引入新的分类方法知识点。

高密度复习：分类

1. 任务、数据与评价框架

监督分类：，；目标是对未见样本学习可泛化的。Numeric prediction 的，不要与 classification 混淆。
Train / validation / test：train 学参数；validation 选模型、超参数、阈值；test 只在最后一次估计泛化性能。测试集不能反复参与调参，避免 leakage。
类别不平衡：多数类占比很高时，永远预测多数类也可能有高 accuracy；应同时报告 confusion-matrix 指标，并按任务代价调整 threshold、class weight 或采样。
两个总原则：模型要在独立数据上评价；指标要匹配错误代价。高 accuracy 不等于高 minority recall。

2. 核心方法：一眼写出规则或方程

方法	必记表达式 / 决策规则	核心限制或关键词
Decision Tree	；$Gain(A)=Info(D)-\sum_j\frac{	D_j
Bayes / MAP		后验 likelihood prior；通常不等于
Naïve Bayes	；零计数用 $\hat P=(count+1)/(N_C+	V
kNN	分类：；回归：；加权可用	lazy；小低 bias/高 variance，大高 bias/低 variance；高维距离会退化
Logistic Regression	，；	线性 log-odds；最大化 Bernoulli log-likelihood，通常无 closed form，用 gradient ascent/descent
Linear SVM	；hard margin：；；margin	只需固定 scale，不是物理常数；support vectors 决定边界
Soft-margin SVM	，约束	小容忍更多 violation、通常 margin 更宽；大更重视训练误差
Kernel SVM	；常见 polynomial、RBF、sigmoid	隐式进入高维空间；kernel 不能自动消除数据规模导致的训练成本
Bagging	bootstrap 重采样并行训练；分类多数投票，回归平均	主要降低 variance；不同样本不保证不同模型，variance reduction 依赖模型误差相关性
AdaBoost / Boosting	顺序关注难例；；错分样本权重乘	final 要求基模型标签通常编码为；对噪声/异常值可能敏感
Random Forest	Decision Trees + data bagging + 每节点随机 feature subset；分类多数投票	通过随机特征降低树间相关性；不是“只要随机就一定更准”

补充两个概率/公式陷阱：

Gaussian NB 若表示标准差，应写，密度为。课件 P23 的写法容易混淆标准差与方差。
线性回归斜率标准式为；课件 P42 的是 PDF-originated 排版/公式错误。

3. 指标、阈值与验证

令、、：

指标	公式	问题意识
Accuracy		类别平衡或错误代价近似相等时才容易有代表性
Error rate		总体错误比例
Sensitivity / Recall / TPR		真阳性中抓到多少，漏诊对应 FN
Specificity / TNR		真阴性中排除多少
Precision		预测为阳性的样本中有多少是真的
F1		、任一很低都会拉低 harmonic mean
		更偏重 recall，更偏重 precision
ROC	横轴，纵轴	改变 threshold 得到整条 trade-off 曲线
AUC	ROC 曲线下的总面积	随机约，完美为；衡量整条曲线而非单点

阈值：提高 positive threshold 通常使 precision 上升、recall 下降；降低 threshold 通常相反，但具体方向仍应由数据检验。
验证方式：holdout 简单便宜；repeated random subsampling 平均多次 holdout；-fold 每次留一折测试；LOOCV 是；stratified CV 尽量保持各折类别比例。
ROC 陷阱：某个 operating point 越接近左上角通常越好，但两条 ROC 曲线可能相交，不能据单点“更靠左上”断言 AUC 更大。

4. 高频对照与易错点

容易混淆	记忆句 / 正确区分
Precision vs Recall	precision 看“预测为 positive 的纯度”（分母）；recall 看“真实 positive 的覆盖率”（分母）
Sensitivity vs Specificity	sensitivity 认 positive；specificity 认 negative
Bayes vs Naïve Bayes vs Bayesian Network	Bayes 是后验规则；NB 加全条件独立；BN 用 DAG+CPT 表示局部依赖，联合分布按 parents 分解
Decision Tree vs kNN	tree eager、先建全局规则；kNN lazy、查询时找局部邻居
Filter vs Wrapper vs Embedded	filter 与分类器无关；wrapper 反复训练评估子集；embedded 在训练目标中同时选特征（如 LASSO）
LASSO vs Ridge	可把系数压到精确 0；通常只收缩、不产生精确稀疏
Bagging vs Boosting vs Random Forest	bagging=bootstrap+parallel；boosting=error-focused+sequential；RF=bagged trees+random features
Hard vs Soft SVM	hard 要求全体 margin 约束；soft 用 slack 处理噪声/重叠；大并不等于 margin 大
Slack 四种情况	只有在最优解采用最小可行时，、、、才分别对应 margin 外/上、margin 内正确侧、边界、错误侧
Multiclass vs Multilabel	multiclass 一条样本一个类；multilabel 一条样本可有多个标签；OVA 需个分类器，OVO 需个
SSL vs Active vs Transfer	SSL 不额外询问标签；active 主动问 oracle 最有价值样本；transfer 从 source task 借知识并警惕 negative transfer
Distant / Zero-shot	distant supervision 用启发式自动造大量但 noisy 标签；zero-shot 依靠 semantic attributes/side information 预测训练未见类
Node-level vs Graph-level	前者给节点预测标签，后者给整张图预测标签；不要把 graph-level 样本误当普通独立向量

最后四个已审计的纠错点请直接记住：

Gaussian：标准差写在密度分母外，正态参数第二项是方差。
Bagging：bootstrap 只提供多样性的机会，不保证。
Slack：四种等式关系默认 slack 已在优化解中取最小可行值；一般可行解只有不等式约束。
ROC/AUC：左上角是单个工作点的直觉，AUC 是整条曲线面积，曲线相交时二者不能直接等同。

Chapter 6 Classification: Basic Concepts 完整复习笔记 ​

0. 本章到底要解决什么问题？——先看“进化树” ​

1. Classification 基础概念 ​

1.1 Supervised vs. Unsupervised Learning ★★★ ​

Supervised Learning ​

Unsupervised Learning ​

1.2 Classification vs. Numeric Prediction ★★★ ​

Classification ​

Numeric Prediction ​

1.3 Classification 的完整生命周期 ★★★ ​

Training Set ​

Validation Set ​

Test Set ​

2. Decision Tree Induction ​

2.1 决策树的核心思想 ★★★ ​

2.2 决策树算法 ★★★ ​

2.3 停止条件 ★★★ ​

情况 1 ​

情况 2 ​

情况 3 ​

2.4 Continuous-valued Attribute 怎么处理？ ★★★ ​

Method 1：Discretization ​

缺点 ​

Method 2：寻找最佳 split point ​

2.5 Decision Tree 的优缺点 ★★☆ ​

优点 ​

缺点 ​

3. Information Gain：决策树如何选择 Attribute ​

3.1 Entropy ★★★ ​

直觉 ​

完全确定 ​

二分类最不确定情况 ​

3.2 Conditional Entropy ★★★ ​

3.3 Information Gain ★★★ ​

3.4 Play Golf Information Gain 计算 ★★★ ​

3.5 Information Gain 有什么问题？ ★★★ ​

3.6 Gain Ratio：针对 Information Gain 的改进 ★★★ ​

为什么有效？ ​

课件 Temp 示例 ​

ID3 → C4.5 的方法论演进 ★★★ ​

4. Bayesian Classification ​

4.1 Total Probability Theorem ★★★ ​

4.2 Bayes' Theorem ★★★ ​

Prior ​

Likelihood ​

Posterior ​

4.3 MAP Classification ★★★ ​

4.4 Picnic Example ★★☆ ​

5. 从 Exact Bayes 到 Naïve Bayes ​

5.1 为什么 Exact Bayesian Classification 很难？ ★★★ ​

5.2 Naïve Bayes Assumption ★★★ ​

5.3 Categorical Feature ★★★ ​

5.4 Continuous Feature：Gaussian Naïve Bayes ★★★ ​

5.5 Play Golf Naïve Bayes 示例 ★★★ ​

5.6 多 feature 完整预测 ★★★ ​

6. Zero Probability Problem → Laplace Correction ​

6.1 Why Naïve Bayes fails? ★★★ ​

6.2 Laplace Smoothing ★★★ ​

课件例子 ​

6.3 Naïve Bayes 优缺点 ★★☆ ​

Strength ​

Weakness ​

7. Lazy Learning ​

7.1 Eager vs. Lazy Learning ★★★ ​

Eager Learning ​

Lazy Learning ​

7.2 Instance-Based Learning ★★☆ ​

8. k-Nearest Neighbor ​

8.1 基本思想 ★★★ ​

8.2 Euclidean Distance ★★★ ​

8.3 Classification ★★★ ​

8.4 Regression ★★☆ ​

8.5 1-NN 与 Voronoi Diagram ★★☆ ​

8.6 Distance-weighted kNN ★★★ ​

8.7 为什么 更 robust？ ★★☆ ​

8.8 Curse of Dimensionality ★★★ ​

9. k 的选择：Bias–Variance Tradeoff ​

Small ★★★ ​

Large ​

10. Case-Based Reasoning ​

Chapter 6 Classification: Basic Concepts 完整复习笔记

0. 本章到底要解决什么问题？——先看“进化树”

1. Classification 基础概念

1.1 Supervised vs. Unsupervised Learning ★★★

Supervised Learning

Unsupervised Learning

1.2 Classification vs. Numeric Prediction ★★★

Classification

Numeric Prediction

1.3 Classification 的完整生命周期 ★★★

Training Set

Validation Set

Test Set

2. Decision Tree Induction

2.1 决策树的核心思想 ★★★

2.2 决策树算法 ★★★

2.3 停止条件 ★★★

情况 1

情况 2

情况 3

2.4 Continuous-valued Attribute 怎么处理？ ★★★

Method 1：Discretization

缺点

Method 2：寻找最佳 split point

2.5 Decision Tree 的优缺点 ★★☆

优点

缺点

3. Information Gain：决策树如何选择 Attribute

3.1 Entropy ★★★

直觉

完全确定

二分类最不确定情况

3.2 Conditional Entropy ★★★

3.3 Information Gain ★★★

3.4 Play Golf Information Gain 计算 ★★★

3.5 Information Gain 有什么问题？ ★★★

3.6 Gain Ratio：针对 Information Gain 的改进 ★★★

为什么有效？

课件 Temp 示例

ID3 → C4.5 的方法论演进 ★★★

4. Bayesian Classification

4.1 Total Probability Theorem ★★★

4.2 Bayes' Theorem ★★★

Prior

Likelihood

Posterior

4.3 MAP Classification ★★★

4.4 Picnic Example ★★☆

5. 从 Exact Bayes 到 Naïve Bayes

5.1 为什么 Exact Bayesian Classification 很难？ ★★★

5.2 Naïve Bayes Assumption ★★★

5.3 Categorical Feature ★★★

5.4 Continuous Feature：Gaussian Naïve Bayes ★★★

5.5 Play Golf Naïve Bayes 示例 ★★★

5.6 多 feature 完整预测 ★★★

6. Zero Probability Problem → Laplace Correction

6.1 Why Naïve Bayes fails? ★★★

6.2 Laplace Smoothing ★★★

课件例子

6.3 Naïve Bayes 优缺点 ★★☆

Strength

Weakness

7. Lazy Learning

7.1 Eager vs. Lazy Learning ★★★

Eager Learning

Lazy Learning

7.2 Instance-Based Learning ★★☆

8. k-Nearest Neighbor

8.1 基本思想 ★★★

8.2 Euclidean Distance ★★★

8.3 Classification ★★★

8.4 Regression ★★☆

8.5 1-NN 与 Voronoi Diagram ★★☆

8.6 Distance-weighted kNN ★★★

8.7 为什么更 robust？ ★★☆

8.8 Curse of Dimensionality ★★★

9. k 的选择：Bias–Variance Tradeoff

Small ★★★

Large

10. Case-Based Reasoning