NYU-DLSP20 课程笔记：基于能量的结构化预测——因子图、高效推理与图变换网络（Graph Transformer Net）-北京尧图网络

示例工程【免费下载链接】NYU-DLSP20NYU Deep Learning Spring 2020项目地址https://gitcode.com/gh_mirrors/pyt/pytorch-Deep-Learning点击查看免费下载本文基于 NYU Deep Learning Spring 2020NYU-DLSP20第 14 周理论课 Part A讲师Yann LeCun整理对应仓库文档 docs/ko/week14/14-1.md英文原版见 docs/en/week14/14-1.md。课程围绕结构化预测Structured Prediction展开先给出结构化预测的问题定义与早期工作TDNN 动态时间规整再引出能量基因子图Energy-Based Factor Graphs及其高效推理框架随后介绍以浅层因子构建的线性结构化模型条件随机场、最大间隔马尔可夫网络、结构化感知机最后落到可端到端训练的图变换网络Graph Transformer Net, GTN并展示如何在动态计算图上完成反向传播。读完本文你将掌握能量函数如何用因子和表示、如何把推理转化为 trellis 图上的最短路径问题以及 GTN 如何用两阶段钳位/自由流程实现判别式训练。一、什么是结构化预测文档开篇给出的定义结构化预测是针对给定输入 $x$预测一个相互依赖、受约束的输出变量 $y$ 的问题——这里的 $y$ 不是标量离散值或实数值而是具有结构性的组合对象。关键特征有三点输出变量不属于单一类别其可能取值个数可以是指数级甚至无限的输出内部存在顺序、空间或组合结构各分量之间相互依赖模型的根本任务是捕获问题领域中的序列sequential、空间spatial或组合combinatorial结构。典型的应用场景包括语音识别、手写识别、自然语言翻译等。在这些任务中输出必须符合语法约束例如单词序列必须构成合法语句因此无法预先限定输出的可能数量也不能把问题简化成从有限类别中选一个。二、结构化预测的早期工作TDNN 与动态时间规整2.1 从 TDNN 到特征向量早期做法是先把输入信号如语音送入时延神经网络TDNN, Time-Delay Neural Network得到一个特征向量。在传统模型系统中这个特征向量可类比于表示某个类别的 softmax 输出。2.2 动态时间规整解决同一单词不同发音识别发音单词时面临一个天然难题不同的人以不同方式和速度发音同一个词导致特征序列长度和节奏都不一致。为此早期系统引入动态时间规整Dynamic Time Warping, DTW。其核心思想是系统预先保存一组由某人录制的、对应序列或特征向量的模板templates神经网络与模板同时训练使系统学会识别不同发音下的同一个词。**潜变量latent variable**在此扮演关键角色——它允许对特征向量做时间轴上的扭曲time-warp使其长度与模板对齐。2.3 矩阵视角与图上的最短路径将 TDNN 输出的特征向量按水平方向排列、单词模板按垂直方向排列可以把它可视化为一个矩阵矩阵中每个元素对应特征向量与模板之间的距离。这一矩阵又可进一步可视化为图graph问题目标是从左下角出发沿着使累计距离最小的路径到达右上角。2.4 训练目标训练这个潜变量模型时需要让正确答案的能量尽可能小、所有错误答案的能量尽可能大。实现方式是设计一个目标函数输入错误单词的模板将其从当前特征序列推离增大能量并通过反向传播更新梯度。三、能量基因子图3.1 基本思想能量基因子图Energy-Based Factor Graphs的核心思想是构造一个能量基模型使总能量等于若干部分能量项之和等价地概率为若干因子之积。这类模型的最大优势是可以运用高效的推理算法。因为能量被分解成局部因子全局优化不必逐点穷举而是可以利用因子间的依赖结构加速。3.2 序列标注Sequence Labeling一个具体例子是序列标注模型输入语音信号 $X$输出标签序列 $Y$使得输出标签满足总能量项最小化。在此例中能量是三个项的求和图中用蓝色方块表示——每个方块是一个神经网络为输入变量生成特征向量语音识别场景下$X$ 可视为语音信号方块实现了语法约束grammatical constraints$Y$ 表示生成的输出标签。四、能量基因子图的高效推理4.1 问题背景穷举为何不可行文档引用了经典文献A Tutorial on Energy-Based LearningYann LeCun, Sumit Chopra, Raia Hadsell, MarcAurelio Ranzato, Fu Jie Huang, 2006能量基模型的学习与推理涉及在答案集合 $\mathcal{Y}$ 与潜变量集合 $\mathcal{Z}$ 上对能量做最小化。当 $\mathcal{Y}\times\mathcal{Z}$ 的基数很大时这种最小化会变得难以处理intractable。一种解决思路是利用能量函数的结构来高效完成最小化。当能量可以表示为若干独立函数称为因子factors之和、且每个因子只依赖于 $Y$ 和 $Z$ 中不同的变量子集时这种依赖关系用**因子图factor graph**表达最自然。因子图是图模型graphical models或信念网络belief networks的一种一般化形式。4.2 四因子分解示例图 5即原文 Figure 19给出了一个简单因子图。其能量函数是四个因子之和$$E(Y, Z, X) E_a(X, Z_1) E_b(X, Z_1, Z_2) E_c(Z_2, Y_1) E_d(Y_1, Y_2)$$其中 $Y [Y_1, Y_2]$ 是输出变量$Z [Z_1, Z_2]$ 是潜变量。每个因子可视为对其输入变量取值之间的一种软约束soft constraints。推理问题即求解$$(\bar{Y}, \bar{Z})\operatorname{argmin}{y \in \mathcal{Y}, z \in \mathcal{Z}}\left(E{a}\left(X, z_{1}\right)E_{b}\left(X, z_{1}, z_{2}\right)E_{c}\left(z_{2}, y_{1}\right)E_{d}\left(y_{1}, y_{2}\right)\right)$$4.3 计算量从 96 次降到 16 次假设 $Z_1$、$Z_2$、$Y_1$ 是离散二值变量$Y_2$ 是三值变量。由于 $X$ 始终被观测其定义域的基数无关紧要。给定 $X$ 时$Z$ 和 $Y$ 的可能配置数为$$2 \times 2 \times 2 \times 3 24$$朴素穷举会评估整个能量函数 24 次即 $24 \times 4 96$ 次单因子求值。但观察因子结构可以发现$E_a$ 只依赖 $Z_1$仅有 2 种输入配置$Z_1 0$ 或 $Z_1 1$$E_b$、$E_c$ 各有 4 种配置$E_d$ 有 6 种配置。因此最多只需 $2 4 4 6 16$ 次单因子求值——这就是利用分解结构带来的指数级效率提升。4.4 trellis 图与最短路径推理把这 16 个因子值预先计算出来放到 trellis格状图的**弧arc**上每一列节点表示单个变量的可能取值每条边的权重是该因子在对应输入取值下的输出能量。此时从起点到终点的一条路径就代表所有变量的一种可能配置路径上权重之和等于该配置的总能量。于是推理问题被归结为在图中搜索最短路径shortest path可以使用Viterbi 算法或A* 算法等动态规划方法完成。其代价与边的数量16成正比而边数通常比路径数指数级更小。计算 $E(Y, X) \min_{z\in Z} E(Y, z, X)$ 时只需把图限制为与给定 $Y$ 值兼容的弧的子集再走同样的流程。4.5 min-sum 算法与它的适用边界上述过程有时被称为min-sum 算法它是图模型中传统max-product 算法的对数域版本。该流程可以自然推广到因子接收两个以上变量的因子图树结构而非链结构的因子图。但注意其前提它只适用于无环的二部树bipartite trees结构。若图中存在环loopmin-sum 算法迭代时可能只给出近似解甚至完全不收敛。此时需要改用模拟退火simulated annealing之类的下降算法。五、浅层因子的简单能量基因子图线性结构化模型5.1 对数域中的线性模型图 6原文 Figure 20展示的是线性结构化模型即文档所称简单能量基因子图的对数域因子图。其能量函数形式为$$E(W, Y, X)\sum_{(m, n) \in \mathcal{F}} W_{m n}^{T} f_{m n}\left(X, Y_{m}, Y_{n}\right)$$其中$\mathcal{F}$ 表示因子集合即存在直接相互依赖的标签对$(m, n)$ 的集合$W_{mn}$ 是因子 $(m, n)$ 的参数向量$f_{mn}(X, Y_m, Y_n)$ 是固定的特征向量全局参数向量 $W$ 是所有 $W_{mn}$ 的拼接concatenation。模型选好后剩下的核心问题是该用什么样的损失函数来训练文档由此引出三类经典模型。5.2 条件随机场Conditional Random Field, CRF对线性结构化模型使用**负对数似然NLL, negative log-likelihood**损失得到的就是条件随机场。直觉我们希望正确答案的能量低同时让包括正确答案在内所有答案的指数对数log-sum-exp尽量大。其形式化定义为$$\mathcal{L}{\mathrm{nll}}(W)\frac{1}{P} \sum{i1}^{P} E\left(W, Y^{i}, X^{i}\right)\frac{1}{\beta} \log \sum_{y \in \mathcal{Y}} e^{-\beta E\left(W, y, X^{i}\right)}$$5.3 最大间隔马尔可夫网络与潜变量 SVM也可以使用**合页损失Hinge loss进行优化这就是最大间隔马尔可夫网络Max Margin Markov Nets与潜变量 SVMLatent SVM**背后的思想。直觉在让正确答案能量低的同时从所有错误配置中找出能量最低的那个最差劲的错答案只把它最冒犯的答案most offending answer的能量推高即可——其他错误答案的能量本来就更大无需处理。这使得训练目标更温和并不要求所有错误答案都无限远只要求最坏的一个被推开。5.4 结构化感知机模型Structured Perceptron用**感知机损失perceptron loss**训练线性结构化模型即结构化感知机。Collins[Collins, 2000, Collins, 2002]在 NLP 语境下倡导对线性结构化模型使用该损失$$\mathcal{L}{\text {perceptron }}(W)\frac{1}{P} \sum{i1}^{P} E\left(W, Y^{i}, X^{i}\right)-E\left(W, Y^{* i}, X^{i}\right)$$其中 $Y^{* i}\operatorname{argmin}_{y \in \mathcal{Y}} E\left(W, y, X^{i}\right)$ 是系统自己生成的答案——即能量最低在无约束条件下的答案。5.5 早期判别式训练语音/手写识别文档还提及判别式训练的早期尝试——最小经验误差损失Minimum Empirical Error Loss, Ljolje Rabiner, 1990。其做法是在序列级别训练而不告诉系统某个声音或某个位置对应什么只给系统输入句子及其逐词转写让系统通过时间规整自行求解当时并未使用神经网络而是用其他手段把语音信号转成声音类别。这一在序列层面、通过对齐进行判别式训练的思路正是后面图变换网络GTN的历史前身。六、图变换网络Graph Transformer Net6.1 问题未知分割的序列识别GTN 面对的问题输入是一串数字如手写数字34但我们不知道该如何分割哪里是 3 的结束、哪里是 4 的开始。解决方案是构造一个图图中每条路径对应一种分割方式然后用最短路径搜索找到能量最低的那条路径。具体流程输入图像34送入分割器segmenter得到多种候选分割每种分割对应把墨迹团块blobs of ink分组的特定方式分割图中的每条路径对应一种分组方式见 Fig7对每个分割片段分别通过同一个字符识别 ConvNet得到各类别得分列表如对3的片段得到 10 类得分示例图中简化为 2 类——例如1 [0.1]表示类别 1 的能量为 0.1由此得到一个图——它可以被看作一种稀疏张量sparse tensor对每个变量的每种可能配置给出该配置的代价。由于讨论的是能量它更接近于张量上的对数分布。6.2 钳位阶段计算正确答案的能量接下来要计算正确答案的能量。给定正确答案34在路径中挑选所有标注为34的路径一条路径能量为 $3.4 2.4 5.8$另一条为 $0.1 0.6 0.7$。选择能量最低的路径这里是 0.7。这等价于对潜变量做最小化——这里的潜变量就是你选了哪条路径。概念上GTN 就是一个潜变量为路径的能量模型。6.3 对动态结构做反向传播得到正确路径能量 0.7 之后需要对整个结构做梯度反向传播调整 ConvNet 权重使最终能量下降。虽然看似困难但完全可行——因为整个系统由已知元素构成神经网络是常规的**路径选择器Path Selector**与 **Viterbi 变换器Viterbi Transformer**本质上是开关决定选择或不选择某条边。梯度如何流动0.7 是 0.1 与 0.6 之和因此这两点各获得梯度 1Viterbi 变换器在两条路径中只选一条于是把梯度复制到被选路径对应边上未被选中的路径梯度设为 0——这正是Max-Pooling / Mean-Pooling中的行为。路径选择器同理只是负责选出正确答案。之后梯度穿过神经网络反向传播使正确答案的能量变小。文档特别强调该结构是动态的dynamic——换一个新输入神经网络实例数量会随分割数量变化派生出的图也随之改变。因此必须对动态结构反向传播这正是PyTorch 这类框架真正重要的场景动态计算图自动微分。6.4 自由阶段拉开错误答案仅有第一阶段只能降低正确答案的能量还需第二阶段把错误答案的能量推高第二阶段前半段与第一阶段完全相同Viterbi 变换器直接选择能量最低的路径不关心它是否正确由于该能量是所有可能路径中最小的它必然小于等于第一阶段的能量这构成一种使用感知机损失的简化判别式训练让系统自由选择它想要的答案。6.5 两阶段合并与感知机损失把两个阶段合并损失函数为$$\text{loss} \text{energy}_1 - \text{energy}_2$$此时需要对整个结构反向传播左侧正确答案钳位路径获得 1 梯度右侧自由选择的路径获得 −1 梯度。因此如果某个分数如3 [0.1]同时出现在左右两条路径中其梯度为0。如此训练系统最终将最小化正确答案能量与任意最优答案能量之间的差距——即感知机损失与 5.4 节的公式一致。七、理解问答课程 QAQ1为什么能量基因子图的推理是容易的带潜变量的能量基模型做推理时通常需要穷举式技术如梯度下降来最小化能量但在因子图场景下能量是若干因子之和因此可以改用动态规划如 Viterbi、A*、min-sum完成推理代价随边数而非路径数增长。Q2如果因子图中的潜变量是连续的还能用 min-sum 算法吗不能——因为无法再对所有因子值做全组合穷举。但能量分解此时仍然带来好处可以做独立优化。例如图 5Figure 19中 $Z_1$ 与 $Z_2$ 的组合只影响因子 $E_b$因此仍可通过独立优化动态规划来完成推理。Q3图中的 NN 方块是否指向不同的 ConvNet不是它们是共享的——同一个字符识别 ConvNet 的多个副本只是被重复实例化到不同分割片段上。八、本篇在课程与仓库中的位置本文内容属于 NYU-DLSP20 第 14 周理论课 Part A。课程总览见 docs/ko/week14/14.mdPart A 覆盖结构化预测、能量基因子图、高效推理、浅层因子模型与 GTNPart Bdocs/ko/week14/14-2.md进一步比较各类损失函数Energy Loss、Perceptron、Hinge、Log、LVQ2、MCE、Square-Square、Square-Exp、NLL/MMI、MEE并把 Viterbi 与forward 算法Log-Sum-Exponential 软最小化应用到图变换网络上还延伸到反向传播的拉格朗日表述、Neural ODE 与基于能量的变分推理。关于实现层面的两个关键提示推理即动态规划Viterbi 找的是 $\min_z E(x,y,z)$forward 算法算的是 $-\frac{1}{\beta}\log\sum_z \exp(-\beta E(x,y,z))$两者代价相当后者可微分、便于端到端反向传播详见 14-2训练即判别式对比无论 NLL、Hinge 还是 Perceptron 损失本质都是压小正确答案能量、拉开错误答案能量区别只在于错误答案如何选取全部求和 / 最冒犯者 / 系统自选最优。理解这些概念后你可以在 PyTorch 中用自定义 autograd Function 复现 Viterbi/forward 算法的前向与反向再配合共享权重的 ConvNet 搭建一个可端到端训练的 GTN 原型——这正是该讲义留给实践者的自然延伸。赞分享示例工程【免费下载链接】NYU-DLSP20NYU Deep Learning Spring 2020项目地址https://gitcode.com/gh_mirrors/pyt/pytorch-Deep-Learning点击查看免费下载相关推荐NYU DLSP20 结构化预测导论基于能量的因子图与 Graph Transformer NetNYU DLSP20 结构化预测导论基于能量的因子图与 Graph Transformer Net 本篇文章对应 NYU Deep Learning Spri示例工程结构化预测中的能量模型因子图、高效推理与 Graph Transformer Net 实战解析NYU-DLSP20 Week14 笔记结构化预测中的能量模型因子图、高效推理与 Graph Transformer Net 实战解析NYU DLSP20 Week14 笔记本指南围绕 NYU示例工程NYU-DLSP20 第 14 周结构化预测与基于能量的图模型——从因子图、Graph Transformer Net 到正则化NYU DLSP20 第 14 周结构化预测与基于能量的图模型——从因子图、Graph Transformer Net 到正则化本篇指南基于 NYU Dee示例工程上一篇网盘文件丢给 IDM 或 Aria2先装这个浏览器脚本把直链取出来下一篇TradingAgents-CN 完整使用指南5 分钟跑通多智能体 AI 股票分析含深度调优清单创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

NYU-DLSP20 课程笔记：基于能量的结构化预测——因子图、高效推理与图变换网络（Graph Transformer Net）

相关推荐

BFE mod_doh 模块配置指南：mod_doh.conf 全参数详解与 DoH 请求转发实现

从Day1到Day105：面试经典150题刷题复盘与高效计划

高并发电商支付中台实战：从架构拆分到稳定性治理

更多资讯

SpringBoot+Vue私人诊所管理系统：协同过滤推荐算法实战解析

MagPie模型路由工具：Agent多模型统一管理与自动分发实践

用Shell脚本实现轻量级基础设施即代码（IaC）实践

本地AI项目部署实战：环境准备、API接口与批量任务全流程解析

OpenHarmony真机Flutter应用错误处理与异常管理实战指南

人类阅读与大语言模型如何应对概念中断和指称中断？

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？