图最小割算法图最小割算法专用于二分类问题。其核心思想是我们希望为未标记数据分配标签使得在分配完成后所有正类样本与负类样本之间的总相似度之和最小。换句话说我们要最小化违反“相似点同标签”假设的程度。如果一对标签不同的点具有很高的相似度就意味着我们的假设被严重违反了。因此最小化这个总和相当于在图中找到一个切割将图分成正、负两类并且被切割的边的权重即相似度之和最小。上一节我们介绍了构建图的基本思想本节中我们来看看如何用“割”的概念来形式化我们的目标。在图的术语中一个“割”是将图的节点划分成两个不相交子集的操作。被割掉的边是那些连接两个不同子集的边。“最小割”就是找到一种划分方式使得被割掉的边的权重总和最小。在我们的设定中两个子集分别对应我们预测的正类和负类。已标记数据点的标签是固定的它们必须属于对应的子集。我们的任务是为未标记点分配标签即决定它们属于哪个子集使得这个割的权重总和最小。这样图最小割算法就将我们的直观目标转化为了一个可以在图上高效计算的图论问题。调和能量最小化算法图最小割算法是“硬”分配它要求最终每个点都有一个确定的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 Σ usubject 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.pnghttps://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)判断这两个网络不等价。理由示例在第一个网络中给定 AB 和 D 是条件独立的。而在第二个网络中即使给定 AB 和 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型”结构来判断两个贝叶斯网络是否编码相同的独立性关系并练习了具体案例。马尔可夫毯我们回顾了马尔可夫毯的定义它包含一个节点的父节点、子节点及其子节点的其他父节点并理解了如何确定一组节点的马尔可夫毯。这些概念是理解概率图模型和进行概率推理的基础希望本次复习对你的备考有所帮助。