经典机器学习

经典 ML 算法从数据中学习模式，无需显式编程，使用闭合解或启发式搜索而非 gradient descent。本文涵盖 Naive Bayes、k-NN、决策树、random forests、SVM、k-means 聚类和 PCA。

• 机器学习研究的是通过从数据中学习来提升某项任务性能的算法，而非被显式编程规则约束。与其编写"如果收入 > 5 万且年龄 < 30 则批准贷款"，不如将数千条历史贷款决策交给算法，让它自己找出规律。

• 有三大范式。监督学习使用有标签的数据，即每个输入都带有已知的正确输出，算法学习从输入到输出的映射。无监督学习处理无标签数据，尝试发现隐藏结构，如聚类或压缩表示。强化学习通过试错进行学习，针对在环境中采取的行动获得奖励或惩罚（见第 04 篇）。

• 在监督学习中，分类预测离散类别（垃圾邮件或非垃圾邮件、猫或狗），而回归预测连续值（房价、明天的气温）。边界并非总是清晰的：logistic regression 名为"回归"，但执行分类任务。

• 概率模型中的一个关键区分是生成式 vs 判别式。生成式模型学习联合分布 \(P(x, y)\)，理解数据本身是如何生成的，可以生成新样本。判别式模型直接学习 \(P(y \mid x)\)，只关注类别之间的边界。Naive Bayes 是生成式的；logistic regression（第 02 篇）是判别式的。生成式模型更灵活但更难训练；在数据充足时，判别式模型通常给出更好的分类精度。

• Naive Bayes 是最简单也最有效的分类器之一。它直接应用贝叶斯定理（来自第五章）：

\[P(C_k \mid x) = \frac{P(x \mid C_k) \, P(C_k)}{P(x)}\]

• "naive"（朴素）的部分是一个强独立性假设：它将所有特征视为在给定类别条件下相互独立的。如果你在将电子邮件分类为垃圾邮件，Naive Bayes 假设在已知邮件是垃圾邮件的情况下，"免费"这个词的出现与"获奖者"这个词的出现毫无关联。现实中几乎从不如此，但这个分类器的效果出乎意料地好。

• 由于 \(P(x)\) 对所有类别都相同，分类简化为选择使分子最大的类别：

\[\hat{y} = \arg\max_{k} \; P(C_k) \prod_{i=1}^{n} P(x_i \mid C_k)\]

• Prior \(P(C_k)\) 就是每个类别在训练样本中的比例。Likelihood \(P(x_i \mid C_k)\) 取决于特征的类型，由此产生三种常见变体。

• 多项式 Naive Bayes 设计用于计数数据，如文档中的词频。每个特征 \(x_i\) 表示词 \(i\) 出现的次数，likelihood 服从多项式分布。这是文本分类、情感分析和垃圾邮件过滤的标准选择。

• Gaussian Naive Bayes 假设每个特征在每个类别内服从正态分布。从训练数据中估计类别 \(k\) 下特征 \(i\) 的均值 \(\mu_{ik}\) 和方差 \(\sigma_{ik}^2\)，然后计算：

\[P(x_i \mid C_k) = \frac{1}{\sqrt{2\pi\sigma_{ik}^2}} \exp\!\left(-\frac{(x_i - \mu_{ik})^2}{2\sigma_{ik}^2}\right)\]

• 当特征是连续测量值（如身高、体重或传感器读数）时，这是自然的选择。

• Bernoulli Naive Bayes 对二值特征建模：每个特征要么存在（1）要么缺失（0）。它不计算词出现了多少次，只追踪是否出现。这对于短文本或二值特征向量效果很好。

• 当训练数据中某个特征值从未与某个类别同时出现时，会出现一个实际问题：likelihood 变为零，由于所有项相乘，整个 posterior 崩溃为零。Laplace 平滑通过向每个特征-类别组合添加一个小计数（通常为 1）来解决这个问题：

\[P(x_i \mid C_k) = \frac{\text{count}(x_i, C_k) + \alpha}{\text{count}(C_k) + \alpha \cdot V}\]

• 其中 \(\alpha\) 是平滑参数（通常为 1），\(V\) 是该特征的可能值数量。这确保没有概率恰好为零。

• 决策树采用完全不同的方法。它不计算概率，而是通过一系列是/否问题对特征空间进行分区。想象一下"20 个问题"游戏：每一步你都问能最大程度缩小可能性的问题。

• 树从包含所有训练样本的根节点开始。在每个内部节点，它选择一个特征和一个阈值进行分裂（例如，"年龄 < 30 吗？"）。样本根据答案向左或向右流动。这个过程递归进行，直到到达叶节点，叶节点存放预测：分类问题取多数类，回归问题取均值。

• 关键问题是：应该在哪个特征上分裂？你希望分裂产生"最纯"的子节点，即大多数样本属于同一类别。两种常见的不纯度度量是 Gini 不纯度和 entropy。

• Gini 不纯度衡量随机选取的样本按照该节点的分布进行标注时被错误分类的概率：

\[\text{Gini}(S) = 1 - \sum_{k=1}^{K} p_k^2\]

• 如果节点完全纯净（全部同一类），Gini 为 0。如果类别均匀平衡（二分类时各占 50%），Gini 达到最大值 0.5。

• Entropy（来自第五章的信息论部分）衡量平均惊讶程度：

\[H(S) = -\sum_{k=1}^{K} p_k \log_2 p_k\]

• 纯节点的 entropy 为 0。完全平衡的二分类节点的 entropy 为 1 比特。实际上，Gini 和 entropy 给出非常相似的树；Gini 计算稍快，因为它避免了对数运算。

• 信息增益是通过一次分裂实现的不纯度降低。对于将集合 \(S\) 分为子集 \(S_L\) 和 \(S_R\) 的分裂：

\[\text{IG}(S, \text{split}) = H(S) - \frac{|S_L|}{|S|} H(S_L) - \frac{|S_R|}{|S|} H(S_R)\]

• 算法在每个节点贪婪地选择信息增益最高的分裂。这是局部最优策略，不是全局最优，但实际效果很好。

• 回归树工作方式相同，但叶节点预测连续值（到达该叶节点的样本的均值），分裂准则使用方差减少而非 Gini 或 entropy。

• 如果不加限制，决策树会一直分裂直到每个叶节点都纯净，本质上是在记忆训练数据，这是严重的过拟合。剪枝应对这一问题。预剪枝在树生长之前设置限制：最大深度、每个叶节点的最小样本数，或进行分裂所需的最小信息增益。后剪枝先生长完整树，然后删除在验证集上不能改善性能的分支。

• 单棵决策树容易理解，但往往不稳定：数据的微小变化可能产生完全不同的树。集成方法结合多个模型，以获得比任何单个模型更好的预测。

• 核心思想是"群体的智慧"。如果你询问 100 个一般的分类器并取多数投票，集成可以非常出色——只要个体分类器的错误具有一定的独立性。

• Bagging（bootstrap 聚合）在数据的不同随机子集上训练多个模型，子集通过有放回抽样（bootstrap 样本）得到。每个模型看到大约 63% 的原始数据。预测时，对输出取平均（回归）或多数投票（分类）。由于每个模型看到不同的数据，它们犯不同的错误，取平均可以消除大部分方差。

• Random Forests 是将 bagging 应用于决策树并增加一个额外技巧：在每次分裂时，树只考虑特征的随机子集（通常是 \(d\) 个特征中的 \(\sqrt{d}\) 个）。这进一步降低了树之间的相关性，使集成更加强大。Random forests 是机器学习中最可靠的开箱即用分类器之一。

• Boosting 采用相反的哲学。它不是独立训练模型，而是顺序训练，每个新模型专注于之前模型犯错的样本。

• AdaBoost（自适应 Boosting）为每个训练样本维护一个权重。初始时所有权重相等。训练一个弱学习器（通常是非常浅的决策树，称为"树桩"）后，被错误分类的样本权重增加，使下一个学习器更关注它们。最终预测是所有学习器的加权投票，性能更好的学习器话语权更大：

\[H(x) = \text{sign}\!\left(\sum_{t=1}^{T} \alpha_t \, h_t(x)\right)\]

• 学习器 \(t\) 的权重 \(\alpha_t\) 取决于其错误率 \(\epsilon_t\)：

\[\alpha_t = \frac{1}{2} \ln\!\left(\frac{1 - \epsilon_t}{\epsilon_t}\right)\]

• 低错误率的学习器获得大正权重；表现与随机猜测相当（\(\epsilon = 0.5\)）的学习器权重为零。

• Gradient Boosting 推广了这一思想。每个新模型不是重新为样本加权，而是被训练来预测当前集成的残差误差（损失函数的负梯度）。对于平方误差损失，残差就是预测值与目标值之差。使用决策树的 gradient boosting（GBDT）是结构化数据竞赛中许多获奖方案的基础（XGBoost、LightGBM、CatBoost 是常用实现）。

• 关键对比：bagging 减少方差（通过平均消除噪声），而 boosting 减少偏差（纠正系统性错误）。当个体模型过拟合时，bagging 效果最好；当它们欠拟合时，boosting 效果最好。

• 转向无监督学习，K-Means 聚类是最简单且使用最广泛的聚类算法。给定 \(n\) 个数据点和目标聚类数 \(K\)，它将每个点分配到 \(K\) 个组中的一个，以最小化每个点到其聚类中心的总距离。

• 算法交替执行两个步骤。首先，将每个点分配到最近的质心。其次，将每个质心更新为分配给它的所有点的均值。重复直到分配不再变化。这保证收敛，因为簇内总距离在每一步都会减小（或保持不变）。

• 形式上，K-Means 最小化簇内平方和，称为惯性（inertia）：

\[J = \sum_{k=1}^{K} \sum_{x \in C_k} \|x - \mu_k\|^2\]

• 其中 \(\mu_k\) 是簇 \(C_k\) 的质心。

• K-Means 对初始化敏感。不好的初始质心可能导致差劲的局部极小值。K-Means++ 初始化策略随机选择第一个质心，然后以与最近已有质心平方距离成比例的概率选择每个后续质心。这使初始中心分散，几乎总能给出更好的结果。

• 如何选择 \(K\)？两种常用工具。肘部法则绘制惯性 vs \(K\) 的图，寻找增加更多簇收益递减的"肘部"。轮廓系数衡量一个点与自己所在簇的相似程度相对于最近其他簇的程度，范围从 -1（错误的簇）到 +1（很好地聚类）。所有点的平均轮廓系数提供簇质量的总体度量。

• K-Means 有局限性：它假设大小大致相等的球形簇，并做"硬"分配（每个点恰好属于一个簇）。高斯混合模型（GMM）放宽了这两个限制。

• GMM 将数据建模为 \(K\) 个 Gaussian 分布的混合，每个分布有其自己的均值 \(\mu_k\)、协方差 \(\Sigma_k\) 和混合权重 \(\pi_k\)（权重之和为 1）：

\[P(x) = \sum_{k=1}^{K} \pi_k \, \mathcal{N}(x \mid \mu_k, \Sigma_k)\]

• 每个点得到软分配：它属于每个簇的概率（称为"责任"）。靠近两个 Gaussian 边界的点可能有 60% 属于簇 A，40% 属于簇 B。

• GMM 使用期望最大化（EM）算法拟合，与 K-Means 类似地交替执行两个步骤。E 步计算责任：对于每个点，它来自每个 Gaussian 的概率是多少？M 步更新参数：给定责任，最佳均值、协方差和混合权重是什么？EM 保证在每次迭代时增加数据 likelihood，收敛到局部最大值。

• K-Means 实际上是 EM 对 GMM 的特例：对应于球形 Gaussian，协方差相等且责任为硬（0/1）分配。

• 支持向量机（SVM）从几何角度处理分类问题。给定两个线性可分的类别，有无数个超平面可以分离它们。SVM 找到具有最大间隔的那个——超平面与每个类别最近数据点之间尽可能大的间隙。

• 最近的那些点——恰好坐在间隔边缘的点——称为支持向量。它们是定义边界的唯一重要点；你可以删除所有其他训练点，得到相同的超平面。

• 对于线性分类器 \(f(x) = w \cdot x + b\)，找到最大间隔相当于求解：

\[\min_{w, b} \; \frac{1}{2}\|w\|^2 \quad \text{满足} \quad y_i(w \cdot x_i + b) \geq 1 \; \text{对所有 } i\]

• 这是一个凸二次规划问题，所以它有唯一的全局解（无需担心局部极小值）。

• 真实数据很少是完全可分的。软间隔 SVM 通过引入松弛变量 \(\xi_i \geq 0\) 允许一些点违反间隔：

\[\min_{w, b, \xi} \; \frac{1}{2}\|w\|^2 + C \sum_{i=1}^{n} \xi_i \quad \text{满足} \quad y_i(w \cdot x_i + b) \geq 1 - \xi_i\]

• 超参数 \(C\) 控制权衡：大 \(C\) 严重惩罚错误分类（更紧的拟合，过拟合风险），小 \(C\) 允许更多违规（更宽的间隔，更多正则化）。

• SVM 最强大的特性是核技巧。在原始特征空间中不能线性分离的许多数据集，映射到高维空间后变得可分离。核技巧让你计算在该高维空间中的内积，而无需显式计算变换。

• 核函数 \(K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)\) 替换 SVM 优化中的每个内积。最流行的核是径向基函数（RBF）核：

\[K(x_i, x_j) = \exp\!\left(-\gamma \|x_i - x_j\|^2\right)\]

• RBF 核将数据隐式映射到无限维空间。参数 \(\gamma\) 控制单个训练点的影响范围：大 \(\gamma\) 意味着每个点只影响其直接邻域（过拟合风险），小 \(\gamma\) 给出更平滑的边界。

• 其他常见核包括多项式核 \(K(x_i, x_j) = (x_i \cdot x_j + c)^d\) 和线性核 \(K(x_i, x_j) = x_i \cdot x_j\)（无任何变换的标准 SVM）。

• 在实践中，带 RBF 核的 SVM 在深度学习兴起之前是主流分类器。它们在中小型数据集上仍然有效，特别是当特征数量相对于样本数量较大时。

• SVM 与第二章（矩阵）的联系很深。优化通常以对偶形式求解，解只依赖于训练样本之间的内积，这正是核技巧得以实现的原因。整个算法运作在内积和线性代数的语言中。

• 经典 ML 工具箱总结：

算法	类型	核心优势	核心弱点
Naive Bayes	监督（生成式）	快速，少量数据也有效	独立性假设
决策树	监督	可解释	容易过拟合
Random Forest	监督（集成）	鲁棒，超参数少	可解释性较差
Gradient Boosting	监督（集成）	表格数据上效果最好	较慢，需要更多调整
K-Means	无监督（聚类）	简单，可扩展	假设球形簇
GMM	无监督（聚类）	软分配，形状灵活	对初始化敏感
SVM	监督	在高维空间有效	大数据集上较慢

编程任务（使用 CoLab 或 notebook）

1. 从头实现 Gaussian Naive Bayes。在二维合成数据的两个类别上训练，并可视化决策边界。与 scikit-learn 的实现进行比较。

   import jax.numpy as jnp
   import matplotlib.pyplot as plt
   from sklearn.datasets import make_classification
   
   # 生成合成数据
   X, y = make_classification(n_samples=300, n_features=2, n_redundant=0,
                              n_informative=2, n_clusters_per_class=1, random_state=42)
   X, y = jnp.array(X), jnp.array(y)
   
   # 从头拟合 Gaussian Naive Bayes
   classes = jnp.unique(y)
   params = {}
   for c in classes:
       c = int(c)
       mask = y == c
       X_c = X[mask]
       params[c] = {
           'mean': jnp.mean(X_c, axis=0),
           'var': jnp.var(X_c, axis=0),
           'prior': jnp.sum(mask) / len(y)
       }
   
   def gaussian_log_likelihood(x, mean, var):
       return -0.5 * jnp.sum(jnp.log(2 * jnp.pi * var) + (x - mean)**2 / var)
   
   def predict(X):
       preds = []
       for x in X:
           log_posts = []
           for c in [0, 1]:
               log_post = jnp.log(params[c]['prior']) + gaussian_log_likelihood(
                   x, params[c]['mean'], params[c]['var'])
               log_posts.append(log_post)
           preds.append(jnp.argmax(jnp.array(log_posts)))
       return jnp.array(preds)
   
   # 决策边界可视化
   xx, yy = jnp.meshgrid(jnp.linspace(X[:,0].min()-1, X[:,0].max()+1, 200),
                          jnp.linspace(X[:,1].min()-1, X[:,1].max()+1, 200))
   grid = jnp.column_stack([xx.ravel(), yy.ravel()])
   zz = predict(grid).reshape(xx.shape)
   
   plt.figure(figsize=(8, 6))
   plt.contourf(xx, yy, zz, alpha=0.3, cmap='coolwarm')
   plt.scatter(X[y==0, 0], X[y==0, 1], c='#3498db', label='类别 0', edgecolors='k', s=20)
   plt.scatter(X[y==1, 0], X[y==1, 1], c='#e74c3c', label='类别 1', edgecolors='k', s=20)
   plt.title("Gaussian Naive Bayes 决策边界")
   plt.legend()
   plt.grid(alpha=0.3)
   plt.show()
   
   accuracy = jnp.mean(predict(X) == y)
   print(f"训练准确率: {accuracy:.2%}")
   

2. 构建使用 Gini 不纯度进行分裂的决策树。实现单个节点的分裂逻辑，展示信息增益如何选择最佳特征和阈值。

   import jax.numpy as jnp
   
   def gini_impurity(y):
       """标签数组的 Gini 不纯度。"""
       classes, counts = jnp.unique(y, return_counts=True)
       probs = counts / len(y)
       return 1.0 - jnp.sum(probs ** 2)
   
   def information_gain(y, left_mask):
       """通过布尔掩码将 y 分为左/右两部分的信息增益。"""
       parent_gini = gini_impurity(y)
       left_y, right_y = y[left_mask], y[~left_mask]
       n = len(y)
       if len(left_y) == 0 or len(right_y) == 0:
           return 0.0
       child_gini = (len(left_y)/n) * gini_impurity(left_y) + \
                    (len(right_y)/n) * gini_impurity(right_y)
       return float(parent_gini - child_gini)
   
   def best_split(X, y):
       """找到使信息增益最大的特征和阈值。"""
       best_ig, best_feat, best_thresh = -1, None, None
       for feat in range(X.shape[1]):
           thresholds = jnp.unique(X[:, feat])
           for thresh in thresholds:
               mask = X[:, feat] <= float(thresh)
               ig = information_gain(y, mask)
               if ig > best_ig:
                   best_ig, best_feat, best_thresh = ig, feat, float(thresh)
       return best_feat, best_thresh, best_ig
   
   # 示例：合成数据
   from sklearn.datasets import make_classification
   X, y = make_classification(n_samples=100, n_features=4, n_redundant=0, random_state=0)
   X, y = jnp.array(X), jnp.array(y)
   
   feat, thresh, ig = best_split(X, y)
   print(f"最佳分裂：特征 {feat}，阈值 {thresh:.3f}，信息增益 {ig:.4f}")
   print(f"父节点 Gini：{gini_impurity(y):.4f}")
   mask = X[:, feat] <= thresh
   print(f"左子节点 Gini：{gini_impurity(y[mask]):.4f}（{int(jnp.sum(mask))} 个样本）")
   print(f"右子节点 Gini：{gini_impurity(y[~mask]):.4f}（{int(jnp.sum(~mask))} 个样本）")
   

3. 使用 K-Means++ 初始化从头实现 K-Means。对合成数据集进行聚类，并可视化每次迭代时的簇变化。

   import jax
   import jax.numpy as jnp
   import matplotlib.pyplot as plt
   from sklearn.datasets import make_blobs
   
   # 生成合成簇
   X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.8, random_state=42)
   X = jnp.array(X)
   
   def kmeans_plus_plus_init(X, K, key):
       """K-Means++ 初始化。"""
       n = X.shape[0]
       idx = jax.random.randint(key, (), 0, n)
       centroids = [X[idx]]
       for _ in range(1, K):
           dists = jnp.min(jnp.stack([jnp.sum((X - c)**2, axis=1) for c in centroids]), axis=0)
           probs = dists / jnp.sum(dists)
           key, subkey = jax.random.split(key)
           idx = jax.random.choice(subkey, n, p=probs)
           centroids.append(X[idx])
       return jnp.stack(centroids)
   
   def kmeans(X, K, max_iters=20, key=jax.random.PRNGKey(0)):
       centroids = kmeans_plus_plus_init(X, K, key)
       history = [centroids]
       for _ in range(max_iters):
           # 分配步骤
           dists = jnp.stack([jnp.sum((X - c)**2, axis=1) for c in centroids])
           labels = jnp.argmin(dists, axis=0)
           # 更新步骤
           new_centroids = jnp.stack([
               jnp.mean(X[labels == k], axis=0) for k in range(K)
           ])
           history.append(new_centroids)
           if jnp.allclose(centroids, new_centroids):
               break
           centroids = new_centroids
       return labels, centroids, history
   
   K = 4
   labels, centroids, history = kmeans(X, K)
   
   # 绘制最终结果
   colors = ['#3498db', '#e74c3c', '#27ae60', '#9b59b6']
   plt.figure(figsize=(8, 6))
   for k in range(K):
       mask = labels == k
       plt.scatter(X[mask, 0], X[mask, 1], c=colors[k], s=20, alpha=0.6)
       plt.scatter(centroids[k, 0], centroids[k, 1], c=colors[k], marker='X',
                   s=200, edgecolors='k', linewidths=1.5)
   plt.title(f"K-Means 聚类（K={K}，共 {len(history)-1} 次迭代）")
   plt.grid(alpha=0.3)
   plt.show()
   
   # 计算惯性
   inertia = sum(jnp.sum((X[labels == k] - centroids[k])**2) for k in range(K))
   print(f"最终惯性：{inertia:.2f}")
   

4. 演示核技巧。通过比较核矩阵与多项式核的显式特征映射，展示 RBF 核在高维空间中计算内积。

   import jax.numpy as jnp
   
   # 简单的 2D 数据
   X = jnp.array([[1.0, 2.0], [3.0, 4.0], [5.0, 6.0]])
   
   # 多项式核：K(x,y) = (x·y + 1)^2
   def poly_kernel(X, degree=2, c=1.0):
       return (X @ X.T + c) ** degree
   
   # 2D 二次显式特征映射：(1, sqrt(2)*x1, sqrt(2)*x2, x1^2, x2^2, sqrt(2)*x1*x2)
   def poly_features(X):
       x1, x2 = X[:, 0], X[:, 1]
       return jnp.column_stack([
           jnp.ones(len(X)),
           jnp.sqrt(2) * x1,
           jnp.sqrt(2) * x2,
           x1 ** 2,
           x2 ** 2,
           jnp.sqrt(2) * x1 * x2
       ])
   
   K_trick = poly_kernel(X)
   phi = poly_features(X)
   K_explicit = phi @ phi.T
   
   print("核技巧（二次多项式）：")
   print(K_trick)
   print("\n显式特征映射内积：")
   print(K_explicit)
   print(f"\n矩阵一致：{jnp.allclose(K_trick, K_explicit)}")
   
   # RBF 核：不存在有限维显式映射
   def rbf_kernel(X, gamma=0.5):
       sq_dists = jnp.sum(X**2, axis=1, keepdims=True) + \
                  jnp.sum(X**2, axis=1) - 2 * X @ X.T
       return jnp.exp(-gamma * sq_dists)
   
   K_rbf = rbf_kernel(X)
   print("\nRBF 核矩阵：")
   print(K_rbf)
   print("对角线始终为 1（一个点与自身完全相同）")
   print("非对角线元素随距离衰减")