Classification (I): Decision Trees, KNN, Naïve Bayes & SVM

1. Classification: Definition & General Approach

Slide 3：給定一批 records（training set），每個 record 由 tuple $(x, y)$ 描述：

• $x$：attribute set（又叫 attribute、predictor、independent variable、input）
• $y$：class label（又叫 class、response、dependent variable、output）

Task：Learn a model that maps each attribute set $x$ into one of the predefined class labels $y$，即將 class label 建模成 attribute set 嘅 function。

Slide 4 Goal：previously unseen records should be assigned a class as accurately as possible. 用 test set 量度 model 嘅 accuracy：通常將 data 分成 training set（建 model）同 test set（validate model）。

Task (Slide 5)	Attribute set, $x$	Class label, $y$
Categorizing email messages	Features extracted from email message header and content	spam or non-spam
Identifying tumor cells	Features extracted from x-rays or MRI scans	malignant or benign cells
Cataloging galaxies	Features extracted from telescope images	Elliptical, spiral, or irregular-shaped galaxies

Slide 6 "General Approach for Building Classification Model"：Training Set → Learning algorithm（Induction）→ Learn Model → Apply Model 到 Test Set（Deduction）。

2. Decision Trees: 結構同應用

Slide 8–9 展示 decision tree 例子。Tree 由 root node、internal nodes（每個係一個 attribute test condition，叫 splitting attributes）同 leaf nodes（class label）組成。Slide 9 "Another Example" 說明：同一份 data 可以 fit 出多過一棵 tree。

本 chapter 一直用一個 10-record 稅務例子（attributes：Refund、Marital Status、Taxable Income；class：Evade / Cheat）。以下係教科書嘅數據同經典 tree（數字同 slide 58 文字 $P(\text{No}) = 7/10$、$P(\text{Married} \mid \text{No}) = 4/7$、$P(\text{Refund} = \text{Yes} \mid \text{Yes}) = 0$ 完全吻合）：

Tid	Refund	Marital Status	Taxable Income	Evade
1	Yes	Single	125K	No
2	No	Married	100K	No
3	No	Single	70K	No
4	Yes	Married	120K	No
5	No	Divorced	95K	Yes
6	No	Married	60K	No
7	Yes	Divorced	220K	No
8	No	Single	85K	Yes
9	No	Married	75K	No
10	No	Single	90K	Yes

Refund?
├── Yes → NO
└── No  → MarSt?
          ├── Married → NO
          └── Single, Divorced → TaxInc?
                                 ├── < 80K → NO
                                 └── > 80K → YES

2.1 Apply Model to Test Data (Slides 10–17)

Slides 11–16 一步步示範：由 root 開始，按 test record 嘅 attribute 值沿住分支行，直到 leaf。例：test record (Refund = No, Marital Status = Married, Taxable Income = 80K, Evade = ?)：

1. Root：Refund = No → 行去 MarSt 節點
2. MarSt = Married → 去到 leaf NO
3. 結果：Assign Evade = "No"

3. Decision Tree Induction & Hunt's Algorithm

Slide 18：好多 induction algorithms：Hunt's Algorithm（最早期之一）、CART、ID3, C4.5、SLIQ, SPRINT。

ExamSlide 19：General Structure of Hunt's Algorithm。設 $D_t$ 為到達 node $t$ 嘅 training records：

Slides 20–23 用稅務 data 示範（圖片）：一開始成個 data 係一個 node（label = majority class "No"，7 No vs 3 Yes）→ 用 Refund split（Refund = Yes 全部 No → leaf）→ Refund = No 嗰邊再用 Marital Status split（Married 全部 No → leaf）→ Single / Divorced 嗰邊再用 Taxable Income < 80K split → 全部 nodes 變 pure。

4. Design Issues & Test Conditions

Slide 24–25：Decision tree induction 有兩大設計問題：

1. How should training records be split?
   • Method for specifying test condition：視乎 attribute types（Nominal / Ordinal / Continuous）同 number of ways to split（2-way / multi-way）。
   • Measure for evaluating the goodness of a test condition：node impurity（Gini Index、Entropy、Misclassification error）。
2. How should the splitting procedure stop?
   • Stop splitting if all the records belong to the same class or have identical attribute values。
   • Model Selection：Pre-Pruning (Early Stopping Rule)、Post-pruning（trimming the nodes）。

4.1 Test Conditions by Attribute Type (Slides 26–29)

Attribute type	Multi-way split	Binary split
Nominal（例：Marital Status）	Use as many partitions as distinct values：{Single}, {Married}, {Divorced}	Divides values into two subsets，例：{Married} vs {Single, Divorced}。$k$ 個值有 $2^{k-1}-1$ 種 binary splits。
Ordinal（例：Shirt Size S/M/L/XL）	As many partitions as distinct values	Two subsets，但要 preserve order property：{S, M} vs {L, XL} ✓；{S, L} vs {M, XL} ✗（破壞次序）
Continuous（例：Taxable Income）	Discretize 成多個 ranges（例如 <10K, [10K,25K), [25K,50K), [50K,80K), ≥80K）	Binary decision：$(A \lt v)$ or $(A \ge v)$

Splitting based on continuous attributes (slide 29)：

• Discretization to form an ordinal categorical attribute：ranges 用 equal interval bucketing、equal frequency bucketing（percentiles）或 clustering 搵。Static = 開頭 discretize 一次；Dynamic = 每個 node 重做。
• Binary Decision $(A \lt v)$ or $(A \ge v)$：考慮所有可能嘅 splits 搵 best cut；計算量可以較大。

5. Choosing the Best Split: Impurity Measures

Slide 30–31：Greedy approach：nodes with purer class distribution are preferred。需要一個 measure of node impurity。例如 C0 : 5, C1 : 5（high impurity，non-homogeneous）vs C0 : 9, C1 : 1（low impurity，homogeneous）。

5.1 Worked example：計單一 node 嘅 impurity

Node (C1, C2)	p	Gini	Entropy	Error
(0, 6)	0, 1	$1 - 0 - 1 =$ 0	$-0 - 1 \cdot \log_2 1 =$ 0	$1 - 1 =$ 0
(1, 5)	1/6, 5/6	$1 - (1/6)^2 - (5/6)^2 =$ 0.278	$-(1/6)\log_2(1/6) - (5/6)\log_2(5/6) =$ 0.650	$1 - 5/6 =$ 0.167
(2, 4)	2/6, 4/6	$1 - (1/3)^2 - (2/3)^2 =$ 0.444	0.918	$1 - 4/6 =$ 0.333
(3, 3)	0.5, 0.5	0.5	1	0.5

三個 measures 嘅排序一致（越 pure 越細），只係數值唔同。Entropy 對 impurity 最敏感。

5.2 Finding the Best Split (Slides 33–34)

5.3 Worked example：用 10-record data 揀 root split（Gini）

Parent：7 No、3 Yes → $P = 1 - 0.7^2 - 0.3^2 = 1 - 0.49 - 0.09 = \mathbf{0.42}$

(a) Refund：

• Refund = Yes：3 records（No 3, Yes 0）→ $\text{Gini} = 0$
• Refund = No：7 records（No 4, Yes 3）→ $\text{Gini} = 1 - (4/7)^2 - (3/7)^2 = 1 - 25/49 = 0.490$
• $M = (3/10)(0) + (7/10)(0.490) =$ 0.343 → $\text{Gain} = 0.42 - 0.343 =$ 0.077

(b) Marital Status（multi-way）：

• Single：4 records（Tid 1, 3, 8, 10 → No 2, Yes 2）→ $\text{Gini} = 0.5$
• Married：4 records（Tid 2, 4, 6, 9 → No 4）→ $\text{Gini} = 0$
• Divorced：2 records（Tid 5 Yes, 7 No）→ $\text{Gini} = 0.5$
• $M = 0.4(0.5) + 0.4(0) + 0.2(0.5) =$ 0.300 → $\text{Gain} =$ 0.120

(c) Marital Status（binary {Married} vs {Single, Divorced}）：{S, D} 有 6 records（No 3, Yes 3）→ Gini 0.5 → $M = 0.6(0.5) + 0.4(0) =$ 0.300（同 multi-way 一樣）。

(d) Taxable Income（continuous，binary split）：先排序，再喺相鄰值中點試每個 cut：

Sorted income	60	70	75	85	90	95	100	120	125	220
Class	No	No	No	Yes	Yes	Yes	No	No	No	No

Cut $v$	$\le v$ (Yes, No)	$> v$ (Yes, No)	Weighted Gini
65	(0, 1)	(3, 6)	0.400
72.5	(0, 2)	(3, 5)	0.375
80	(0, 3)	(3, 4)	0.343
87.5	(1, 3)	(2, 4)	0.417
92.5	(2, 3)	(1, 4)	0.400
97.5	(3, 3)	(0, 4)	0.300 ← best
110	(3, 4)	(0, 3)	0.343
122.5	(3, 5)	(0, 2)	0.375
172.5	(3, 6)	(0, 1)	0.400

例：$v = 97.5$：左 6 records Gini 0.5，右 4 records Gini 0 → $M = 0.6 \times 0.5 = 0.3$。

結論：Marital Status 同 Taxable Income ($\le 97.5$) 都得 $M = 0.300$（Gain 0.12），好過 Refund（$M = 0.343$）。

5.4 Worked example：Information Gain（Entropy）

Parent entropy：$H = -0.3\log_2 0.3 - 0.7\log_2 0.7 = 0.521 + 0.360 = \mathbf{0.881}$

• Refund：Refund = No (3 Yes, 4 No) $\text{entropy} = 0.985$；$M = 0.7 \times 0.985 = 0.690$；$IG = 0.881 - 0.690 = 0.192$
• Marital Status：Single (2, 2) = 1；Married = 0；Divorced (1, 1) = 1；$M = 0.4 + 0 + 0.2 = 0.6$；$IG = 0.281$
• Income $\le 97.5$：(3, 3) = 1；(0, 4) = 0；$M = 0.6$；$IG = 0.281$

同 Gini 結論一致：Refund 最差。

from sklearn.tree import DecisionTreeClassifier, export_text
clf = DecisionTreeClassifier(criterion="gini")   # 或 criterion="entropy"
clf.fit(X_train, y_train)
print(export_text(clf, feature_names=list(X_train.columns)))

6. Stopping, Strengths & Weaknesses of Decision Trees

Stopping Criteria (slide 35)：

• 所有 records 屬同一 class 就停止 expand 該 node。
• 所有 records 嘅 attribute values 相似（identical）就停止。
• Early termination（防止 overfitting，詳見 Chapter 4B）。

Handling interactions (slide 37) 同 Limitations of single attribute-based decision boundaries (slide 38)：因為每個 test 只用一個 attribute，decision boundaries 永遠平行於坐標軸（axis-parallel，好似樓梯級）。如果真正嘅 boundary 係斜線（例如 $x + y \lt 1$）或者 class 取決於兩個 attributes 嘅 interaction（例如 XOR 型），tree 就要好多層先近似到。

7. Nearest-Neighbor Classifiers (KNN)

Slide 40 Basic idea："If it walks like a duck, quacks like a duck, then it's probably a duck."

ExamSlide 41：Requires three things：

1. The set of labeled records
2. Distance metric to compute distance between records
3. The value of $k$, the number of nearest neighbors to retrieve

Slide 42：To classify an unknown record：

1. Compute distance to other training records
2. Identify $k$ nearest neighbors
3. Use class labels of nearest neighbors to determine the class label of unknown record（e.g., by taking majority vote）

Slide 43：Compute proximity，例如 Euclidean distance $d(\mathbf{x},\mathbf{y}) = \sqrt{\sum_i (x_i - y_i)^2}$。決定 class：

• Take the majority vote of class labels among the $k$-nearest neighbors
• Weight the vote according to distance：weight factor $w = 1/d^2$

7.1 Worked example（自擬）

Training：$P_1(1,1)$ A、$P_2(2,2)$ A、$P_3(3,1)$ A、$P_4(5,4)$ B、$P_5(6,5)$ B、$P_6(4,4)$ B。Test $X = (3.2, 3)$。

Point	Class	Euclidean distance to $X$	$w = 1/d^2$	Rank
$P_6$ (4,4)	B	$\sqrt{0.64+1} = 1.281$	0.609	1
$P_2$ (2,2)	A	$\sqrt{1.44+1} = 1.562$	0.410	2
$P_3$ (3,1)	A	$\sqrt{0.04+4} = 2.010$	0.248	3
$P_4$ (5,4)	B	$\sqrt{3.24+1} = 2.059$	0.236	4
$P_1$ (1,1)	A	$\sqrt{4.84+4} = 2.973$	0.113	5
$P_5$ (6,5)	B	$\sqrt{7.84+4} = 3.441$	0.084	6

• $k = 1$：最近係 $P_6$ → B
• $k = 3$：$P_6$ (B)、$P_2$ (A)、$P_3$ (A) → majority A（2:1）
• $k = 3$, distance-weighted：$B = 0.609$；$A = 0.410 + 0.248 = 0.658$ → A（好接近！）
• $k = 5$：B, A, A, B, A → A（3:2）

結論：$k$ 嘅選擇可以改變答案。

7.2 Choosing k & Proximity (Slides 44–45)

Slide 45：Choice of proximity measure matters——視乎 data types 同 attribute types（例如 documents 用 cosine，binary 用 Jaccard，見 Chapter 2）。

7.3 Data Preprocessing for KNN (Slide 46)

ExamAttributes may have to be scaled to prevent distance measures from being dominated by one of the attributes。例：

• height of a person may vary from 1.5m to 1.8m
• weight of a person may vary from 90lb to 300lb
• income of a person may vary from $10K to $1M

唔 scale 嘅話，distance 幾乎完全由 income 決定。Time series 通常 standardize 成 mean 0、standard deviation 1（Z-score transformation）。

7.4 其他特性 (Slides 47–49)

• Local classifiers：只用附近嘅點決定，can produce decision boundaries of arbitrary shapes（1-NN 嘅 decision boundary 係 Voronoi diagram 形狀，slide 47 圖）。
• Missing values：proximity 計算通常需要全部 attributes；有啲方法只用兩個 instances 都有嘅 attributes subset，但咁樣每對 instances 實際用唔同嘅 proximity measure，proximities are not comparable，效果未必好。
• Irrelevant attributes add noise to the proximity measure；Redundant attributes bias the proximity measure towards certain attributes。可用 variable selection 或 dimensionality reduction 處理。

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
knn = make_pipeline(StandardScaler(),
                    KNeighborsClassifier(n_neighbors=3, weights="distance"))  # 先 scale 再 KNN
knn.fit(X_train, y_train); knn.predict(X_test)

8. Naïve Bayes Classifiers

8.1 Bayes Classifier (Slides 51–54)

A probabilistic framework for solving classification problems。

將每個 attribute 同 class label 當 random variables。給定 record with attributes $(X_1, X_2, \dots, X_d)$，目標係預測 class $Y$：搵令 $P(Y \mid X_1, \dots, X_d)$ 最大嘅 $Y$。

Slide 53 問：可唔可以直接由 data 估計 $P(\text{Evade} = \text{Yes} \mid X)$ 同 $P(\text{Evade} = \text{No} \mid X)$？（$X = (\text{Refund} = \text{No}, \text{Divorced}, \text{Income} = 120\text{K})$）——通常唔得，因為 training data 未必有完全相同 attribute 組合嘅 record。

ExamApproach (slide 54)：用 Bayes theorem 計 posterior probability：

Maximum a-posteriori (MAP)：揀令 $P(Y \mid X_1 \dots X_d)$ 最大嘅 $Y$。因為分母對所有 class 一樣，等價於揀令 $P(X_1 \dots X_d \mid Y)\,P(Y)$ 最大嘅 $Y$。問題：點估計 $P(X_1 \dots X_d \mid Y)$？

8.2 Naïve Bayes Assumption (Slide 56)

Exam假設 class 已知時 attributes 之間 conditional independence：

Example：Arm length and reading skills：細路仔手臂較短、閱讀能力有限（同成人比）→ 兩者表面上相關；但如果 age 固定，arm length 同 reading skills 冇明顯關係 → 佢哋係 conditionally independent given age。

咁就可以由 training data 估計每個 $P(X_i \mid Y_j)$。新點分類到令 $P(Y_j)\prod_i P(X_i \mid Y_j)$ 最大嘅 $Y_j$。

8.3 Estimate Probabilities from Data (Slides 58–60)

• Class prior：$P(y)$ = fraction of instances of class $y$。例：$P(\text{No}) = 7/10$，$P(\text{Yes}) = 3/10$。
• Categorical attributes：$P(X_i = c \mid y) = n_c / n$，$n_c$ = 屬於 class $y$ 而 attribute value 為 $c$ 嘅 instances 數，$n$ = 屬於 class $y$ 嘅 instances 數。例：$P(\text{Status} = \text{Married} \mid \text{No}) = 4/7$、$P(\text{Refund} = \text{Yes} \mid \text{Yes}) = 0$。
• Continuous attributes（slide 59）：
  • Discretization：將 range 分 bins，用 bin value 代替（continuous → ordinal）。
  • Probability density estimation：假設 attribute 跟 normal distribution，用 data 估 parameters（mean、standard deviation），再用 distribution 估 conditional probability。

8.4 Worked example：X = (Refund = No, Divorced, Income = 120K)

8.5 Issues with Naïve Bayes (Slides 64–66)

由 slide 58 可見 $P(\text{Refund} = \text{Yes} \mid \text{Yes}) = 0$。如果 test record 係 Refund = Yes，咁 $P(X \mid \text{Yes})$ 成個乘積都會變 0——無論其他 attributes 幾支持 Yes 都冇用。如果某 record 對兩個 class 都有一個 conditional probability = 0，就完全分類唔到。

教科書嘅解決方法係用其他 probability estimates：

其中 $c$ = attribute 可取值嘅數目，$p$ = 初始估計 (prior) 概率，$m$ = parameter。例：Laplace 下 $P(\text{Refund} = \text{Yes} \mid \text{Yes}) = (0 + 1)/(3 + 2) =$ 0.2（唔再係 0）。

8.6 Characteristics of Naïve Bayes (Slide 67)

• Robust to isolated noise points（概率係由大量 records 平均估計）
• Handle missing values by ignoring the instance during probability estimate calculations
• Robust to irrelevant attributes（irrelevant attribute 嘅 $P(X_i \mid Y)$ 對所有 class 差唔多，乘落去唔改變排序）
• Redundant and correlated attributes will violate class conditional independence assumption（同一資訊被乘兩次，過度影響結果）

from sklearn.naive_bayes import GaussianNB, CategoricalNB
GaussianNB().fit(X_num, y)             # continuous attributes，假設 normal
CategoricalNB(alpha=1).fit(X_cat, y)   # categorical；alpha=1 即 Laplace smoothing

9. Support Vector Machines (SVM)

9.1 Maximum Margin Idea (Slides 69–75)

• Slide 69：Find a linear hyperplane (decision boundary) that will separate the data。
• Slides 70–72：有好多個可能嘅 hyperplanes（"One possible solution"、"Another possible solution"、"Other possible solutions"）都可以將兩類分開。
• Slide 73：Which one is better? B1 or B2? How do you define better?
• Slide 74：ExamFind hyperplane maximizes the margin → B1 is better than B2.

Margin = decision boundary 同兩邊最近 data points 之間嘅距離（兩條平行 hyperplanes $b_{11}$、$b_{12}$ 之間嘅闊度）。Margin 越大，對新 data 嘅 generalization 越好（對 noise 有更大緩衝）。

9.2 Linear SVM (Slides 76–79)

Linear model：

Decision boundary：$\mathbf{w}\cdot\mathbf{x} + b = 0$；兩條 margin hyperplanes：$\mathbf{w}\cdot\mathbf{x} + b = \pm 1$。Learning the model is equivalent to determining the values of $\mathbf{w}$ and $b$.

• Slide 78：Support vectors 係 Lagrange multipliers $\lambda_i \gt 0$ 嘅點（即剛好喺 margin 上嘅點；細節略過）。
• Slide 79：Decision boundary depends only on support vectors——如果另一個 data set 有相同 support vectors，decision boundary 唔會變（其他點移動或刪除都唔影響）。
• 搵到 $\mathbf{w}$、$b$ 之後點分類 test record $\mathbf{x}$？
  $$f(\mathbf{x}) = \begin{cases} +1 & \text{if } \mathbf{w}\cdot\mathbf{x} + b \ge 0 \\ -1 & \text{if } \mathbf{w}\cdot\mathbf{x} + b \lt 0 \end{cases}$$

9.3 Non-linearly Separable: Slack Variables (Slides 80–81)

如果問題唔係 linearly separable？引入 slack variables $\xi_i \ge 0$，容許部分點越過 margin 甚至分錯：

If $k$ is 1 or 2, this leads to similar objective function as linear SVM but with different constraints。$C$ 控制「大 margin」同「少錯誤」之間嘅 trade-off（$C$ 大 → 少容忍錯誤）。

9.4 Characteristics of SVM (Slides 82–83)

• Learning problem 係 convex optimization problem：有 efficient algorithms 搵 global minima（其他好多方法用 greedy approaches，只搵到 locally optimal solutions，例如 decision tree）。
• High computational complexity for building the model（training 慢）。
• Robust to noise。
• Overfitting is handled by maximizing the margin of the decision boundary。
• SVM can handle irrelevant and redundant attributes better than many other techniques。
• Difficult to handle missing values。

from sklearn.svm import SVC
svm = make_pipeline(StandardScaler(), SVC(kernel="linear", C=1.0))
svm.fit(X_train, y_train)
svm[-1].coef_, svm[-1].intercept_, svm[-1].support_vectors_   # w, b, support vectors

10. Summary: 四種 Classifiers 比較

自我測驗 Self-test

Q1. 一個 node 有 class 分佈 $(C_1 = 4, C_2 = 6)$。計 Gini、Entropy、Classification error。

$p = 0.4, 0.6$。$\text{Gini} = 1 - 0.16 - 0.36 =$ 0.48；$\text{Entropy} = -0.4 \log_2 0.4 - 0.6 \log_2 0.6 = 0.529 + 0.442 =$ 0.971；$\text{Error} = 1 - 0.6 =$ 0.4。

Q2. Parent node $(C_0 = 10, C_1 = 10)$。Split A 得 children $(C_0 = 7, C_1 = 3)$ 同 $(C_0 = 3, C_1 = 7)$；Split B 得 $(C_0 = 10, C_1 = 4)$ 同 $(C_0 = 0, C_1 = 6)$。用 Gini 揀邊個 split 較好？

$P = 0.5$。
Split A：每個 child $\text{Gini} = 1 - 0.49 - 0.09 = 0.42$；$M = 0.5(0.42) + 0.5(0.42) = 0.42$；$\text{Gain} = 0.08$。
Split B：child1 (10, 4)：$\text{Gini} = 1 - (10/14)^2 - (4/14)^2 = 1 - 0.510 - 0.082 = 0.408$；child2 pure = 0；$M = (14/20)(0.408) = 0.286$；$\text{Gain} =$ 0.214。
→ Split B 較好。

Q3. 用 entropy 計 Q2 Split B 嘅 information gain。

Parent entropy = 1。Child1 (10/14, 4/14)：$-0.714 \log_2 0.714 - 0.286 \log_2 0.286 = 0.347 + 0.516 = 0.863$；child2 = 0。$M = 0.7 \times 0.863 = 0.604$。$IG = 1 - 0.604 =$ 0.396。

Q4. 點解 decision tree 嘅 decision boundaries 係 axis-parallel？有咩後果？

因為每個 internal node 只 test 一個 attribute（例如 $x_1 < 5$），所以每條 boundary 都垂直於某條軸。如果真正 boundary 係斜線或者 class 取決於 attributes 之間嘅 interaction，tree 要用大量 splits 去近似（樓梯形），容易變得複雜同 overfit（slides 36–38）。

Q5. KNN 中 $k$ 太細同太大各有咩問題？點解要 scale attributes？

$k$ 太細 → 對 noise points 敏感；$k$ 太大 → neighborhood 會包含其他 class 嘅點。要 scale 係因為 attributes 範圍唔同（例如 income $10K–$1M vs height 1.5–1.8m），唔 scale 嘅話 distance 被範圍最大嘅 attribute 主導。

Q6. 用本頁稅務 data，用 Naïve Bayes 分類 $X = (\text{Refund} = \text{No}, \text{Married}, \text{Income} = 120\text{K})$。

$P(X \mid \text{No}) = P(\text{Refund}=\text{No} \mid \text{No}) \times P(\text{Married} \mid \text{No}) \times P(120 \mid \text{No}) = 4/7 \times 4/7 \times 0.0072 = 0.00235$；$\times P(\text{No})\ 0.7 = 1.6 \times 10^{-3}$。
$P(X \mid \text{Yes}) = 1 \times P(\text{Married} \mid \text{Yes}) \times \dots = 1 \times$ 0/3 $\times \dots =$ 0。
→ 分類為 No。留意 $P(\text{Married} \mid \text{Yes}) = 0$ 令 Yes 嘅概率直接變 0——就係 zero-probability issue，可用 Laplace smoothing 修正。

Q7. 「Naïve」指咩假設？舉一個 conditional independence 例子。邊類 attributes 會令佢失效？

假設 given class 時 attributes 互相 conditionally independent：$P(X_1 \ldots X_d \mid Y) = \prod P(X_i \mid Y)$。例：arm length 同 reading skills 係 conditionally independent given age。Redundant / correlated attributes 會違反呢個假設（slide 67）。

Q8. SVM 點解要 maximize margin？寫出 optimization problem。邊啲點決定 decision boundary？

Margin 大 → generalization 較好、對 noise 更 robust、減少 overfitting。Problem：minimize $\|w\|^2/2$ subject to $y_i(w\cdot x_i + b) \ge 1$ for all $i$（等價於 maximize $2/\|w\|$）。用 Lagrange multipliers 解；decision boundary 只取決於 support vectors（$\lambda_i > 0$ 嘅點）。

Q9. 一個 linear SVM 有 $w = (2, -1)$、$b = 1$。分類 $x = (1, 4)$ 同 $x = (0, 0)$，並計 margin。

(1, 4)：$2 - 4 + 1 = -1 < 0$ → −1。(0, 0)：$0 + 0 + 1 = 1 \ge 0$ → +1。$\text{Margin} = 2/\|w\| = 2/\sqrt{5} =$ 0.894。

Q10. 邊個 classifier：(a) prediction 最慢 (b) training 最慢 (c) 對 redundant attributes 最差 (d) 係 lazy learner？

(a) KNN (b) SVM (c) Naïve Bayes（very poor）(d) KNN（Instance, Lazy）。

一頁總結 Cheat sheet