CMU 10-601 机器学习笔记（三）-尧图网络科技

图最小割算法

图最小割算法专用于二分类问题。其核心思想是：我们希望为未标记数据分配标签，使得在分配完成后，所有正类样本与负类样本之间的总相似度之和最小。

换句话说，我们要最小化违反“相似点同标签”假设的程度。如果一对标签不同的点具有很高的相似度，就意味着我们的假设被严重违反了。因此，最小化这个总和，相当于在图中找到一个切割，将图分成正、负两类，并且被切割的边的权重（即相似度）之和最小。

上一节我们介绍了构建图的基本思想，本节中我们来看看如何用“割”的概念来形式化我们的目标。

在图的术语中，一个“割”是将图的节点划分成两个不相交子集的操作。被割掉的边是那些连接两个不同子集的边。“最小割”就是找到一种划分方式，使得被割掉的边的权重总和最小。

在我们的设定中：

两个子集分别对应我们预测的正类和负类。
已标记数据点的标签是固定的，它们必须属于对应的子集。
我们的任务是为未标记点分配标签（即决定它们属于哪个子集），使得这个割的权重总和最小。

这样，图最小割算法就将我们的直观目标，转化为了一个可以在图上高效计算的图论问题。

调和能量最小化算法

图最小割算法是“硬”分配，它要求最终每个点都有一个确定的0或1标签。调和能量最小化则提供了一种“软”的、基于概率的视角。

该算法的目标是：为每个节点（数据点）分配一个实数值（可以理解为属于正类的“可能性”或“置信度”），并满足两个条件：

对于已标记节点，其分配值必须严格等于其真实标签（例如，+1 或 -1）。
对于整个图，所有相邻节点分配值的差异，应与其边权（相似度）成反比。也就是说，边权越高（越相似）的两个点，它们的分配值应该越接近。

这个目标可以通过最小化一个称为调和能量的函数来实现。直观上，这就像让已标记节点的标签信息，沿着高权重的边“平滑地”传播到整个图中。最终，未标记节点的值会介于已标记节点的标签值之间，我们可以根据这个值的正负或大小来决定其类别。

调和能量最小化可以自然地扩展到多分类场景，并且有高效的线性系统求解方法。

主动学习扩展

主动学习解决的是“哪些样本最值得标注”的问题。调和能量最小化算法有一个优雅的主动学习扩展。

其核心思想是：在为标准半监督学习问题求解后，算法会为每个未标记点计算一个值，这个值反映了当前模型对该点标签的不确定程度。一个自然的策略是：请求专家去标注那些模型最不确定的点。

具体来说，在调和能量的框架下，我们可以计算出每个未标记点预测值的方差。方差越高的点，说明模型对其标签越不确定。因此，主动学习算法可以：

用当前已标记数据训练模型，并为未标记数据预测标签及不确定性。
选择不确定性最高的一个或一批未标记点。
请求专家标注这些点，并将其加入已标记数据集。
用新的已标记数据集重新训练模型，并重复此过程。

这种方法能高效地利用专家的标注精力，快速提升模型性能。

总结

本节课我们一起学习了半监督学习的核心思想，即利用“相似点同标签”的假设，借助大量未标记数据来提升模型性能。我们重点介绍了两种基于图的算法：

图最小割：通过最小化不同类别点之间的相似度之和，为未标记点进行“硬”标签分配，适用于二分类。
调和能量最小化：通过最小化相邻节点标签值的加权差异，实现标签信息的“软”传播，可扩展至多分类。

最后，我们还探讨了如何将调和能量最小化扩展至主动学习，通过查询模型最不确定的样本，来最大化专家标注的效用。理解这些算法的动机和直观思想，比掌握其具体计算细节更为重要。

063：主成分分析（PCA）与核PCA 🧠

在本节课中，我们将要学习降维技术，特别是主成分分析及其核化版本。降维旨在将高维数据转换为低维表示，同时尽可能保留数据中的关键信息。

降维概述

当我们谈论线性降维时，我们有一个数据集X。该数据集包含n个样本，每个样本的维度为D。这里的符号表示可能与之前课程不同：X的每一列代表一个样本。

我们希望将矩阵X表示为两个矩阵的乘积：

X ≈ U Z

其中，U是一个D × K的矩阵，而Z是一个K × n的矩阵。这里的K远小于D。

从维度角度看，这个乘法运算的结果应是一个D × n的矩阵。Z的每一列z_i可以看作是样本x_i在K维空间（而非原始的D维空间）中的表示，因此它是一种低维表示。

我们定义一种线性变换C，使得z_i = C^T x_i。同时，我们也希望有一种方法能从z_i近似地重构回原始的x_i。我们定义另一种线性变换U，使得近似地有x_i ≈ U z_i。

观察这个矩阵表示，我们可以发现矩阵U和这里的U是相同的。因此，每个x_i ≈ U z_i。如果U是标准正交矩阵（即U^T U = I），那么z_i确实等于U^T x_i。

存在多种降维技术，它们的核心区别在于寻找最佳U和Z分解的准则不同。我们在课程中学到的是主成分分析，其准则是希望找到U和Z，使得在最小化重构误差L的意义下，能最好地近似X。

为何需要降维？

我们将高维的x替换为低维的z，这主要带来以下好处：

计算与存储效率：低维数据能显著减少计算复杂度和存储需求。
样本复杂度：在监督学习中，所需的样本数量依赖于特征数量。减少特征维度可以降低对样本量的要求。
解释与可视化：面对成百上千维的数据，直接观察和理解其结构、聚类等特性非常困难。通过PCA等技术将其投影到二维或三维空间，可能揭示出数据中的模式，例如清晰的聚类分组。
数据压缩：降维本身可以作为一种压缩机制。例如，在人脸图像数据中，每张图片可以用K个数字（如10个）而非原始的D个像素值（如1000个）来表示。我们只需要存储被称为“特征脸”的矩阵U，就能根据低维表示z来重构人脸图像。

总而言之，流程如下：我们拥有数据X，从中计算出矩阵U，然后计算低维表示Z = U^T X。对于一个新的数据点x_new，我们同样可以使用已学习到的U来找到其低维表示z_new = U^T x_new。随后，我们可以在低维的Z上构建分类器、聚类算法等模型。如果需要从低维表示恢复到全维度表示，我们可以使用近似公式x_i ≈ U z_i。

上一节我们介绍了降维的基本概念和动机，本节中我们来看看最经典的方法——主成分分析的具体原理。

主成分分析（PCA）原理

让我们从PCA开始。为了在黑板上便于演示，我们假设一个简化场景：将二维数据点压缩为一维数据点。

我们有一系列样本，每个样本是二维的。我们希望将每个样本表示为一个单独的数字z_i。我们假设数据已经中心化，即均值为零。我们的目标是找到一种表示，使得z_i = u^T x_i，其中u是一个向量。本质上，我们是在寻找一个投影方向。

PCA寻找投影方向的标准是最大化投影后数据的方差。方差越大，意味着数据在投影方向上的信息保留得越多。数学上，这等价于求解以下优化问题：

max_u u^T Σ u

subject to u^T u = 1

其中，Σ是数据X的协方差矩阵。这个约束条件u^T u = 1是为了确保u是一个单位向量，避免解无限缩放。

这个优化问题的解是：u是协方差矩阵Σ的特征向量，对应的特征值就是投影后的方差。我们选择特征值最大的前K个特征向量作为投影矩阵U的列。

以下是PCA的核心步骤：

数据中心化：计算每个特征的均值，然后将每个样本减去该均值，得到零均值数据。
计算协方差矩阵：对于中心化后的数据矩阵X，计算其协方差矩阵Σ = (1/n) X X^T。
特征值分解：对协方差矩阵Σ进行特征值分解，得到特征值和对应的特征向量。
选择主成分：将特征向量按对应特征值大小降序排列，选择前K个最大的特征值对应的特征向量，构成投影矩阵U。
降维投影：将原始数据投影到选定的主成分上，得到低维表示Z = U^T X。

核主成分分析（Kernel PCA）简介

标准的PCA只能进行线性降维。然而，很多时候数据在原始空间中不是线性可分的，但在某个高维特征空间中可能是线性可分的。核PCA通过“核技巧”将PCA扩展到非线性降维。

核PCA的核心思想是：我们并不显式地将数据映射到高维空间，而是通过一个核函数k(x, y)来计算数据在高维空间中的内积。常用的核函数包括多项式核和径向基函数核。

在核PCA中，我们需要解决的是在高维特征空间中中心化后的核矩阵K的特征值问题。具体步骤如下：

计算核矩阵K，其中K_ij = k(x_i, x_j)。
对核矩阵进行中心化处理。
对中心化后的核矩阵进行特征值分解。
选择前K个主成分对应的特征向量。
得到数据在特征空间中的低维表示。

核PCA允许我们捕获数据中更复杂的非线性结构。

总结

本节课中我们一起学习了降维技术。我们首先理解了降维的目标，即用低维表示Z和变换矩阵U来近似原始高维数据X，并探讨了降维在效率、可视化、压缩等方面的应用价值。接着，我们深入探讨了主成分分析这一经典线性降维方法，其核心是寻找最大化投影方差的方向，这等价于求解数据协方差矩阵的特征向量。最后，我们简要介绍了核PCA，它利用核技巧将PCA扩展到非线性场景，能够处理更复杂的数据结构。掌握PCA是理解许多现代降维和特征提取方法的基础。

064：神经网络入门教程 🧠

在本节课中，我们将学习神经网络的基本概念、常见架构以及核心的训练算法。我们将从人工神经元的基础定义开始，逐步深入到前馈网络和卷积网络的结构，并简要介绍训练网络的关键算法。

人工神经元的基本定义

神经网络由大量相互连接的人工神经元组成。首先，我们定义单个神经元。

一个人工神经元接收一组实数输入。每个输入连接都有一个关联的权重，通常用W表示。神经元本身具有一个激活函数，通常是非线性的，用F表示。神经元的输出Y是激活函数应用于所有输入的加权和的结果。

公式：Y = F( Σ (W_i * X_i) )

其中，X_i是输入，W_i是对应的权重。神经网络就是许多这样的神经元以某种方式连接起来形成的有向图。整个过程是确定性的：给定输入和权重，通过计算可以得到确定的输出。

神经网络的常见架构

上一节我们介绍了单个神经元的工作原理，本节中我们来看看如何将它们组织成网络。神经网络有多种架构，以下是两种主要的类型。

前馈神经网络

前馈神经网络是最流行的架构之一。顾名思义，在这种网络中，信息只朝一个方向流动，从输入层经过若干隐藏层，最终到达输出层。神经元通常被组织成层，层与层之间的连接可以看作一个巨大的权重矩阵。

理解连接的一种有效方式：将层间的连接视为一个矩阵W。假设前一层的神经元值用向量x表示，那么下一层的神经元值可以通过简单的矩阵乘法获得，再应用激活函数。

公式：y = F(W * x)

其中，矩阵W的行数等于下一层的神经元数量，列数等于前一层的神经元数量。矩阵元素W_ij代表从前一层第j个神经元到下一层第i个神经元的连接权重。

卷积神经网络

卷积神经网络是前馈网络的一种特殊类型，其灵感来源于大脑初级视觉皮层中神经元的组织方式。在这种架构中，下一层的每个神经元只依赖于前一层中一个局部区域的神经元，而不是全部连接。

核心特点：这种局部连接和权值共享的特性，使得卷积网络特别擅长处理具有网格状拓扑结构的数据，如图像。你可以将每一层想象成一个二维阵列。

神经网络的训练：反向传播算法

了解了网络的结构后，接下来的关键问题是如何训练它，即如何找到合适的权重W。这通常通过反向传播算法来实现。

反向传播算法的核心是链式法则。它首先进行前向传播计算网络输出和误差，然后反向逐层计算每个权重对总误差的贡献（梯度），最后使用梯度下降等优化方法更新权重。

算法核心步骤概述：

前向传播：输入数据，计算每一层的激活值，直到得到最终输出。
计算误差：比较网络输出与真实标签，计算损失函数。
反向传播：从输出层开始，反向计算损失函数对每一层权重的梯度。
权重更新：使用计算出的梯度，按照学习率更新网络中的所有权重。

总结与近期发展

本节课中我们一起学习了神经网络的基础知识。我们从人工神经元的定义出发，理解了其输入、权重、激活函数和输出的关系。接着，我们探讨了两种主要的网络架构：信息单向流动的前馈神经网络和具有局部连接特性的卷积神经网络。最后，我们概述了训练神经网络的核心算法——反向传播的基本思想。

神经网络领域在持续快速发展，出现了许多新的架构（如循环神经网络、Transformer）和训练技巧（如Dropout、批量归一化），这些进步极大地推动了深度学习在计算机视觉、自然语言处理等领域的成功应用。

065：期末考试复习

在本节课中，我们将通过一系列练习题来复习机器学习课程中的核心概念。我们将从概率论开始，逐步深入到贝叶斯网络和马尔可夫毯等主题。每个问题都旨在帮助你巩固理解，并为期末考试做好准备。

概率论：条件独立性

首先，我们从概率论中的一个基础概念——条件独立性开始。理解这个概念对于后续学习贝叶斯网络至关重要。

假设我们有变量 A、B、C 和 D。已知在给定 D 的条件下，A 与 B 和 C 条件独立。这意味着，当我们知道 D 的信息时，A 的发生与 B 和 C 的发生无关。

我们的目标是证明：如果 A 在给定 D 的条件下与 B 和 C 独立，那么 A 在给定 D 的条件下也与 B 独立。

以下是证明过程：

我们想证明的条件独立性定义是：

P(A, B | D) = P(A | D) * P(B | D)

根据已知条件，A 与 (B, C) 在给定 D 的条件下独立，即：

P(A, B, C | D) = P(A | D) * P(B, C | D)

现在，我们从左边开始推导：

P(A, B | D) = Σ_C P(A, B, C | D)（对 C 进行边缘化）

= Σ_C [P(A | D) * P(B, C | D)]（应用已知条件）

= P(A | D) * Σ_C P(B, C | D)（将P(A | D)提出求和符号）

= P(A | D) * P(B | D)（再次对 C 进行边缘化）

因此，我们证明了P(A, B | D) = P(A | D) * P(B | D)，即 A 在给定 D 的条件下与 B 独立。

直观上理解，如果一个随机变量（A）与一组变量（B, C）条件独立，那么它与该组中的任何一个子集（如 B）也条件独立。

贝叶斯网络：等价性判断

上一节我们讨论了条件独立性，本节中我们来看看如何将这一概念应用于贝叶斯网络。贝叶斯网络是一种用有向无环图表示变量间概率依赖关系的模型。

以下是判断两个贝叶斯网络是否等价的方法。如果两个网络编码了完全相同的一组（条件）独立性关系，则它们是等价的。

我们将分析以下几对网络。对于每一对，你需要判断它们是否等价。如果等价，请指出一个它们共享的（条件）独立性假设；如果不等价，请指出一个其中一个网络满足而另一个不满足的假设。

第一对网络分析

https://github.com/OpenDocCN/dsai-notes-pt2-zh/raw/master/docs/cmu-10601-ml/img/c0bf186df505945e2d94266154e8383e_1.png

对于网络 (a)：

第一个网络 (左):结构为 A → B ← C。这是一个“V”型结构（共同效应）。当未观测到 B 时，A 和 C 是边缘独立的。当观测到 B 时，A 和 C 变得条件依赖（解释消除）。
第二个网络 (右):结构为 A → B → C。这是一个链式结构。当未观测到 B 时，A 和 C 是依赖的。当观测到 B 时，A 和 C 变得条件独立（B 阻断了路径）。

判断：这两个网络不等价。

理由：在给定 B 的条件下，第一个网络中的 A 和 C 是依赖的，而第二个网络中的 A 和 C 是独立的。这是一个关键区别。

对于网络 (b)：

第一个网络 (左):结构为 A ← B → C。这是一个“分叉”结构（共同原因）。B 是 A 和 C 的共同父节点。当未观测到 B 时，A 和 C 是依赖的。当观测到 B 时，A 和 C 变得条件独立。
第二个网络 (右):结构为 A → B ← C。这与 (a) 中的左图相同，是“V”型结构。其独立性关系与 (a) 左图一致。

判断：这两个网络不等价。

理由：在给定 B 的条件下，第一个网络中的 A 和 C 是独立的，而第二个网络中的 A 和 C 是依赖的。

第二对网络分析

对于网络 ©：

这两个网络结构更复杂，但经过分析（例如通过道德图或 d-分离准则），可以发现它们编码的独立性关系是相同的。

判断：这两个网络等价。

共享的独立性示例：在未观测到 C 的条件下，D 与 A 和 B 都是独立的。这是因为 C 是一个“V”型结构的头节点（A → C ← B 和 A → C ← D？需根据实际图形判断，但原理是观测中间节点会激活依赖，未观测则保持独立）。

对于网络 (d)：

判断：这两个网络不等价。

理由示例：在第一个网络中，给定 A，B 和 D 是条件独立的。而在第二个网络中，即使给定 A，B 和 D 之间仍然可能存在依赖关系（因为存在其他未阻断的路径）。或者，更简单地说，在无条件情况下，第一个网络中的 B 和 D 是独立的，而第二个网络中则不是。

贝叶斯网络：马尔可夫毯

在理解了网络结构的等价性之后，我们来看看贝叶斯网络中一个重要的局部性质——马尔可夫毯。马尔可夫毯是一个节点的“最小隔离集”，即给定一个节点的马尔可夫毯，该节点与网络中所有其他节点条件独立。

一个节点 X 的马尔可夫毯包括以下节点：

X 的父节点
X 的子节点
X 的子节点的其他父节点（即 X 的“配偶”）

现在，考虑一个具体的贝叶斯网络（假设网络结构已给出，图中包含节点 A, S, …）。问题是：节点集合 {A, S} 的马尔可夫毯是什么？

根据定义，集合的马尔可夫毯是其每个节点马尔可夫毯的并集。因此，你需要：

分别找出节点 A 的马尔可夫毯（A 的父节点、子节点、子节点的其他父节点）。
分别找出节点 S 的马尔可夫毯。
将这两个集合取并集。
最后，从这个并集中减去原集合 {A, S} 本身，因为马尔可夫毯不包含节点本身。

例如，如果 A 的马尔可夫毯是 {P1, C1, SP1}，S 的马尔可夫毯是 {P2, C2, SP2}，那么 {A, S} 的马尔可夫毯就是({P1, C1, SP1} ∪ {P2, C2, SP2}) \ {A, S}。

具体的节点集合需要根据题目中给出的实际网络图来确定。

总结

本节课中我们一起复习了机器学习的几个核心主题：

概率与条件独立性：我们通过数学推导证明了，如果变量 A 与集合 (B, C) 在给定 D 下条件独立，那么 A 与 B 在给定 D 下也条件独立。
贝叶斯网络等价性：我们学习了如何通过分析网络结构（特别是“分叉”、“链式”和“V型”结构）来判断两个贝叶斯网络是否编码相同的独立性关系，并练习了具体案例。
马尔可夫毯：我们回顾了马尔可夫毯的定义，它包含一个节点的父节点、子节点及其子节点的其他父节点，并理解了如何确定一组节点的马尔可夫毯。