Library learning with e-graphs on jazz harmony

基于电子图的库学习在爵士和声中的应用

https://arxiv.org/pdf/2605.04622

打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片

摘要

人类能够对音乐模式形成高度结构化的直觉理解,但这些模式往往需要多轮反思与反复聆听才能完全内化。为刻画这一内化过程,我们提出一种基于库学习的爵士和声模式计算模型。给定一个和声进行语料库,我们的模型在由原始和声关系构成的程序空间中搜索,以发现对语料库的简洁生成性解释。模型首先为每首作品枚举可能的程序,然后联合学习一个和声模式库与重构后的程序。为高效地在程序与库的巨大联合空间中导航,我们将演绎解析与基于电子图的库学习相结合。我们通过评估程序与库的直觉性,以及与人类书写的和声推导之间的相似性,来考察模型在多大程度上捕捉了人类音乐模式学习的各个方面。

关键词:库学习,电子图,演绎解析,音乐重复,爵士和声

1 引言

音乐模式是音乐创作、感知与分析的核心。在音乐理论中,动机、图式、终止公式、和声进行与节奏细胞等模式提供了可复用的描述单元,既支持分析性解读,也支持创作实践。在音乐信息检索(MIR)中,模式发现同样是一个基础性问题[14],支撑着动机/主题搜索[2, 10, 13, 16, 24]、结构分段[8, 17–19, 25]、相似性[1, 5, 20, 31, 35]与风格刻画[7, 9, 30, 34]等任务。更广泛地说,模式学习是人类音乐认知的标志性特征:听者形成预期、识别再现,并通过将当前材料与先前语境相联系来构建更高层次的结构。因此,音乐模式的计算模型不仅具有实用价值,而且作为关于使音乐理解成为可能的表征与归纳偏置的假设,也具有理论启示意义。

本文聚焦于音乐模式发现(MPD):即直接从数据中识别反复出现的音乐规律性这一问题。MPD的一个核心挑战在于找到既(1)足够抽象以涵盖非精确重复、又(2)具有分析意义以支持解读与结构理解的模式。这两项要求常常相互冲突。模式越抽象,往往匹配的段落越多;若缺乏适当的归纳偏置,匹配空间很快会被假阳性填满,方法返回的模式也变得琐碎或在音乐上无信息量。反之,高度具体的模式虽然精确却脆弱,无法捕捉音乐变奏所特有的家族相似结构。为系统地应对这些挑战,我们提出:究竟是什么使一个音乐模式在一般意义上具有趣味性?我们认为,一个广泛适用的答案不应仅以计数或表面相似性来表述,而应将模式质量与抽象在构建紧凑、可复用的音乐结构解释中所起的作用联系起来。

1.1 我们的视角与方法

人类能够从音乐表面获取高度结构化的音乐模式,但这种结构很少在一次聆听中就被习得。理解通常通过假设与修正的迭代循环而涌现:听者(与分析者)提出候选抽象,重新审视材料,并根据这些抽象对音乐表面的解释程度来修正它们。在这一观点下,模式发现与构建一部作品或一个语料库之解释的更广泛过程不可分割。

为使这一想法精确化,我们采纳计算认知科学的视角,将理解建模为构建解释观察数据的结构化程序[6, 15, 29]。这些程序是生成性与组合性的:它们能从少量部件产生大量表面形式。这使我们能够陈述具体目标。我们希望解释既拟合数据,又简单——例如程序短或描述长度低。程序表征还支持镜像分析过程的显式操作,如提取重复的子计算并引入可复用的库组件。从这一视角看,“好的”音乐模式是在许多解释中有用的抽象。它之所以在模型中占有一席之地,是因为它可以被复用,且能降低语料库的整体描述长度。因此,模式并非仅由频率定义,而是由其对压缩与解释的效用定义。这一视角引出了本工作的指导性问题:我们能否仅从和弦进行出发,以无监督的方式,通过将模式发现视为可复用程序片段的发现,来学习爵士和声模式?

本研究的核心计算问题是:仅给定观测到的音乐表面(例如和弦进行),我们能否联合推断出(1)每首作品的紧凑生成程序(推导)以及(2)一组可跨作品复用的共享抽象?换言之,我们能否同时构建对单部作品的结构化解释,并发现使这些解释变得经济的更高层构建模块?

传统上,这两个问题对应彼此分离的研究传统。第一个问题(从表面形式推断结构化推导)对应解析,通常假定一个固定语法,并寻求给定表面序列在该语法下的最佳推导。第二个问题涉及从一组程序中发现有可复用的抽象,对应库学习。在程序合成中,人们从一组程序语料库出发,通过引入共享子程序来压缩它们,从而降低整体描述长度。解析预设了一组稳定的原始操作;库学习预设了一组程序语料库作为输入。然而在我们的设定中,这种分离是人为的。如果目标是从表面数据直接学习和声模式,那么推导空间取决于可用的抽象,而任何抽象的有用性又取决于它如何参与具体作品的推导。因此,这两个问题相互依赖。

一种朴素的解决方案将按顺序进行(见图1)。人们可能首先为每个和弦进行穷举枚举所有解析树,将每个推导视为候选程序。然后可对这批程序语料库应用库学习,以识别共享子结构并引入新的抽象。尽管概念上简单直接,这一流程在计算上是不可行的。对于二叉分支的歧义上下文无关文法,长度为的字符串的解析数量按卡塔兰数−1增长;对于由部独立作品组成的语料库,可能的程序语料库空间相应地按−1规模增长。因此,在抽象之前穷举枚举推导会导致运行时间爆炸。

打开网易新闻 查看精彩图片

本研究提出一种无监督的爵士和声模式发现方法,将演绎解析与基于电子图的库学习相结合。电子图是一种紧凑的数据结构,旨在通过非破坏性项重写来表示和操作大量等价程序族[3, 33]。通过在共享表示中维护许多候选推导,电子图使抽象与解析决策能够相互作用,而无需显式枚举整个搜索空间。我们从两个互补维度评估该系统。在定量上,我们测量压缩率,以评估学习到的抽象在多大程度上降低了语料库的整体描述长度。在定性上,我们考察学习到的模式的音乐合理性,以及它们用于解释具体作品的方式。

2 基于和弦进行的库学习

2.1 问题设定

上一节将音乐模式发现动机化为:寻找可复用的程序片段,以支持对音乐结构的紧凑解释。目标是从一个和弦进行语料库中推断出(1)每个进行的结构化推导(即程序)以及(2)一组使这些推导变得经济的共享和声抽象。这两个目标相互依赖:推导决定哪些结构会反复出现,而抽象重塑可能的推导空间。

第一阶段涉及解析,旨在直接从和弦序列推断所有可能的推导。我们将和声分析建模为特定领域语言(DSL)中的程序。程序是一种组合性推导,通过递归组合原始和声关系来生成和弦序列(见2.2节)。由于每个进行在歧义上下文无关文法(CFG)下通常允许多种有效推导,所有能求值为整个语料库表面和弦进行的可能程序空间可能呈组合式增长。我们不是过早地为每首作品确定单一推导,而是保留这种歧义性,并通过电子图对推导族进行推理。

第二阶段涉及为整个语料库寻找紧凑的代码库。如果每个进行仅使用原始关系独立解释,所得程序往往会在不同作品间重复相似子结构。这种冗余信号表明存在更高层次的规律性。库学习的目标是将这些反复出现的结构提取为可复用的抽象,从而更经济地描述语料库。其结果类似于对代码库进行重构:重复片段被提取为具名函数,减少重复并澄清共享结构。

2.2 和声关系作为DSL原始操作

我们采用一个已有语法[23]作为爵士和声的DSL,但以显式的关系术语重新解释其产生式规则。我们不再将和声分析表示为和弦符号树,而是将其视为和声关系的组合。和弦本身是结构化对象,推导的内部节点是连接它们的逻辑谓词,如图2所示。例如,V-I(或下行五度)关系并非简单地将一个和弦符号重写为另一个;它断言两个和弦实例满足音程与性质约束(例如,一个根音在另一个上方五度,一个和弦具有属性质)。这一重心的转变在概念上很重要。它明确表明,和声结构在于和弦之间如何处于系统性的相互关系之中。形式上,每个原始操作都编码为egglog[33]中的逻辑规则,egglog提供了基于电子图的逻辑编程接口(下行五度关系的编码见附录Listing 1)。

打开网易新闻 查看精彩图片

2.3 将演绎解析与电子图上的库学习相结合

我们的模型将演绎解析[21, 26]与库学习[3]集成到单一架构中。图3总结了完整流程。每个和弦进行被编码为逻辑事实(公理),并使用在egglog[33]中实现的CYK风格演绎过程进行解析。所得的电子图紧凑地表示所有作品的所有推导,将相同的子推导合并为等价类。候选模式()通过对电子类进行反合一生成。反合一计算两个子推导的最小一般泛化,得到一个参数化模板,捕捉它们的共享结构。这些候选作为重写规则加入电子图,我们执行等式饱和[28, 32]:通过穷举应用重写来扩展图,直到无法再推导出新的等价表达式。这产生一个饱和图′,它不仅紧凑地表示所有原始推导,还表示使用候选抽象可获得的所有等价推导。

打开网易新闻 查看精彩图片

给定饱和电子图′,我们使用代价集分析评估候选库。每个电子节点关联一个代价集he(cost(ℒ), cost(|ℒ))。第一项cost(ℒ)衡量引入库ℒ中抽象的复杂度;第二项cost(|ℒ)衡量使用这些抽象编码语料库的代价。这两项共同实例化了一个MDL目标:只有当抽象在编码数据时带来的节省超过其自身复杂度时,抽象才受到青睐。我们选择在当前搜索空间下使总描述长度最小的库:

打开网易新闻 查看精彩图片

最后,我们使用最优库ℒ*重构原始电子图。因此,模型的输出是一个紧凑的代码库:一个学习到的和声模式库,以及每个进行用该库表达的压缩推导。

3 在egglog中的实现

我们的实现构建于egglog[33]之上,它是等式饱和框架egg的声明式扩展。原始egg系统将等式饱和引入为一种在电子图上进行等式推理的高效方法,允许同时表示和优化大量等价程序[32]。egglog通过自底向上的逻辑编程扩展了这一工作路线,将Datalog风格的规则求值直接集成到电子图表示中。这一扩展对我们的目的至关重要。自底向上的求值策略使我们能够将CYK风格的演绎解析表达为逻辑规则,其推论累积在电子图中。我们还可以以紧凑方式显式存储所有可能的推导树。结果是,DSL允许的所有良构推导都作为等价类(电子类)紧凑地存储在单一共享结构中。

3.0.1 解析阶段。解析阶段在给定语法下推导并紧凑存储语料库中所有作品的所有推导。我们在egglog中以声明式方式实现这一过程,通过运行两条推理规则(见附录图1)至不动点(通常称为饱和)。该过程在电子图内实例化一个CYK风格的动态规划,并经过增强以在推理过程中显式构造和合并推导程序。重要的是,对于每个形如IsPhrase的推导事实,我们将所有导致同一短语的推导程序识别为与规范项Der等价(记作≡)。所得电子图紧凑地合并等价推导。饱和之后,电子图因此类似于共享打包解析森林(SPPF)[26]:它编码了一组在歧义语法下可能呈指数级庞大的推导。

CYK风格解析的一个标准局限是,它会生成所有局部良构的跨度,包括不参与作品任何完整解析的部分推导。由于我们的目标是从完整推导中发现可复用结构,我们通过后续过滤步骤排除这类片段。这实现为根连通性的自顶向下传播。基本情况将对应于跨越整部作品的推导的电子类标记为根连通。归纳地,如果一个跨越(, )的短语是根连通的,并且是通过合并跨越(, )和(, )的短语推导而来,那么这些子短语(及其关联的推导电子类)也被标记为根连通。这种反向传播确保只有参与至少一个完整解析的推导被保留用于后续库学习。

3.0.2 反合一阶段。一旦电子图填充了推导,下一步是识别候选抽象。直观上,我们寻求推导程序中反复出现的结构模式。例如,表达式(3 + 42) × (42)和(2 + 7) × (7)共享共同结构( + ) × (),其中常量和子表达式已被抽象为变量。发现此类共享结构的一种标准技术是反合一[4, 22]。将程序视为树,反合一计算它们的最小一般泛化(即通过将不匹配的子树替换为变量所能获得的最大共同有根树)。结果是一个精确捕捉两个输入共享结构的模式。近期关于babble[3]的工作将经典的基于树的反合一[22]扩展为直接在电子图上操作。我们不是比较两棵单独的树,而是计算推导等价类之间的反合一。

该计算在电子节点与电子类之间相互递归定义,并通过动态规划实现以避免冗余工作。由于egglog将等式饱和与自底向上逻辑编程相结合,整个过程可以声明式表达,同时保持高效。

一个核心挑战是控制反合一信息如何在电子图中传播。朴素地传播部分结果可能导致在新函数值被推导出时发生冗余的重复传播。为避免这种情况,我们交错进行电子节点和电子类反合一的计算。依赖关系如下:电子节点的反合一依赖于其子电子类最终确定的反合一;电子类最终确定的反合一依赖于已收集其组成电子节点产生的所有反合一候选。因此,我们交替进行:(i) 使用已最终确定的子信息在电子节点层面计算候选反合一,以及 (ii) 一旦所有节点级贡献可用,就将它们合并为最终确定的电子类值。

形式化该过程的规则见附录图1。基本情况处理原始关系:相同的原始操作反合一为自身,而不同的原始操作则坍缩为恒等模式Id。归纳情况处理组合模板。当两个节点共享相同的外层构造子且其子节点允许非平凡反合一时,这些反合一被组合成更大的模式(成功归纳)。如果子节点不存在有信息量的泛化,结果默认为Id(失败归纳)。谓词CanCoOccur确保只考虑能够共同参与完整解析的推导,从而防止来自不相关片段的抽象。

3.0.3 压缩(重构)阶段。在为语料库计算出反合一集合()之后,我们使用这些模式使电子图()饱和,并在饱和后的电子图′上执行重写。再次考虑模式( + ) × ()。这种抽象可以重写

在模板程序中,相应的模式写作

其中方括号表示结构组合(在平凡元规则下),而非λ演算意义上的函数应用。方括号表明×组合了两个子模板,一个以为头部,另一个以为头部,并共享占位符结构。模板重写也可以用无变量风格表达:

尖括号运算符规定了参数如何从输入元组路由到模板的开放位置。实际上,重构是作为电子图上的模板重写来实现的:它用高阶组合子替换重复结构,该组合子在提供适当参数时能重建原始程序。

3.0.4 候选库的代价集分析。将所有发现的模式都作为库条目通常并非最优。许多抽象会重叠或竞争解释同一结构,且每个抽象都会带来存储成本。因此核心问题是一个权衡问题:当同时考虑库复杂度与使用成本时,哪种抽象组合能使总描述长度最小?穷举枚举候选模式的所有子集在计算上不可行。相反,babble通过电子图传播代价信息,以组合方式评估库选择。

关键思想是将电子图中的每个项(电子节点和电子类)关联一个代价集:一组配对(ℒ, ),其中ℒ是库条目的候选子集,是对应的使用代价。对于不含子结构且无需抽象的原始项,代价集包含单个元素(∅, 1)。对于复合项,代价集自底向上构造。电子节点的代价集通过组合其子电子类的代价集获得:我们取子节点库–代价配对的笛卡尔积,并加上父构造子的局部贡献(包括可能适用的任何抽象)。这捕捉了在给定各部分解释的情况下解释父节点的所有一致方式。电子类的代价集则定义为其组成电子节点代价集的并集,因为任何等价推导都提供了一种有效解释。与反合一阶段一样,该计算是相互递归的:节点级代价依赖于最终确定的子类,而类级代价则聚合自备选节点。

这种组合结构自然地契合egglog的推理框架。每条规则指定一个局部代价变换,而底层关系引擎高效地执行所需的连接(笛卡尔积)与并集操作。当同一项被推导出多个值时,它们通过集合并集合并,从而累积备选的代价集配对,而无需显式枚举库的全局子集。

由于可能的库–代价组合数量可能迅速增长,babble在自底向上传播过程中使用束搜索启发式对每个电子类的代价集进行剪枝,仅保留在MDL目标下最有希望的候选。与先前阶段一样,我们将节点级累积与类级最终化分离,以确保传播稳定并避免冗余重算。结果是一个紧凑表示:候选库及其语料库范围的使用代价。

4 结果与评估

将库学习过程应用于完整语料库在当前算法下尚不可行。特别是,基于egglog的系统尚未充分优化,无法支持对高度歧义作品进行大规模联合推断。因此,我们呈现一项针对三首作品小子集联合学习的原理验证研究。这一受限设定使我们能够详细考察模型行为,并检视学习到的抽象及使用它们的推导在音乐上的合理性。

这三首作品被选择为在基础语法下具有相对较低的歧义性(可能推导数量),因为歧义是组合爆炸的主要来源。语料库包括《Red Clay》(长度13,5种可能推导)、《Valse Hot》(长度15,6种推导)和《Sunny》(长度17,31种推导)。在本实验中,我们将学习库的最大规模限制为15个抽象,并在搜索过程中使用宽度为5的束搜索。

4.1 定量结果

我们首先测量相对于仅使用原始语法规则的推导的压缩率。由于该语法处于乔姆斯基范式,长度为的作品的任何推导树恰好包含2 − 1个节点。这提供了一个固定的基线描述长度。引入库后,总描述长度包括两部分:(1)使用库条目表达的推导大小,以及(2)库本身的存储成本。在联合条件下,共享库的存储成本在所有作品间平均分摊。

由于我们的模型输出使用学习到的模式的推导,压缩率是相对于仅使用语法产生式规则的推导树大小来测量的。由于我们使用的是乔姆斯基范式下爵士和声语法的简化版本,长度为的作品的任何推导树大小为2 − 1。这是二叉树中非叶节点数比叶节点数少一的简单推论。表1比较了联合学习与逐作品库学习。对于每个条目,主值报告使用共享库的联合学习结果,括号中的值报告逐作品学习结果,即每首作品独立处理、无共享抽象。在联合条件下,学习到的模式可以跨作品复用,从而鼓励捕捉反复出现结构的抽象。相反,逐作品条件允许每首作品归纳自己的库,从而允许更多局部和作品特定的模式。

打开网易新闻 查看精彩图片

联合学习大幅降低了总推导大小,从基础语法下的87降至使用共享库的27。在计入存储成本后,归一化压缩率(CR)为1.5。相反,逐作品学习产生的总推导大小为28,但带来大得多的总体存储成本(47对31),导致较低的压缩率1.16。尽管单次运行偶尔能为单首作品实现略好的压缩(例如“Valse Hot”的情况),但它们是通过引入该作品特定、无法在其他地方复用的更优抽象来实现的。

4.2 定性结果

图4展示了学习到的抽象以及用这些抽象表达的三首作品的推导。所发现的模式在大小、元数和终结符数量上各不相同。在CFG框架内,每个抽象可以理解为一个新的产生式规则,展开为终结符与非终结符的序列。

打开网易新闻 查看精彩图片

我们将这些抽象可视化为组合块,明确显示它们所消耗的表面材料以及它们留下的开放结构位置。

仅生成终结符的模式显示为实心矩形,可直接与表面和弦符号对齐。这些包括0(一个具体的属—主进行)、1(一个下行五度进行)以及2(一个包含三个终结符的具体ii-V-I模式)。它们出现在学习到的库中是预期之中的:此类进行在爵士和声中极为频繁,因此作为可复用单元被抽象时能提供显著压缩。模型识别出2的四个出现位置,如图4中深蓝色区域所示。有人可能会问,为什么模型没有将两个B♭7 E7 Am7连续进行识别为ii-V-I。这是因为如果对B♭7 E7 Am7使用2,那么它会被概括为一个非终结符Am7,从而使前面的FM7无法被解释(因为要纳入它,唯一方式是将它视为与E7形成VI-V属准备关系,而这会破坏2)。

同时生成终结符和非终结符的模式表示为带有方形空洞的矩形(例如4和6)。填充部分对应该模式直接匹配的表面和弦,而空洞标记一个必须由另一抽象填充的开放参数。每个此类模式具有固定片段长度(即它直接消耗的终结符和弦数量)。

学习到的此类抽象分为两大类。第一类由将原始产生式与终止规则组合而形成的模式构成,实际上为原始操作引入了左分支或右分支结构。示例包括3(左分支V–I)、4(左分支下行五度进行)和5(左分支后门属和弦)。这些抽象编码结构上不完整的成分。例如,3捕捉了“主和弦左侧缺少属和弦”的概念。在这方面,它们类似于范畴语法[27]中的方向性函数应用,其中成分规定其如何与周围语境组合。有趣的是,模型优先选择左分支模式。这一观察与先前语法归纳结果[11]中的目标导向性一致。第二类包括结构上更复杂的模式,它们组合多个非终止产生式。其中,6尤其值得注意。它消耗围绕bVII和声区域的两个具体表面和弦,其中起始和弦与该区域构成下行五度关系。模型令人惊讶地使用这一抽象以非常规方式分析《Red Clay》的开头。尽管对序列B♭m7-D♭sus-E♭sus的解释与爵士和声树库(JHTB)[12]中的专家分析一致,但对起始主和弦的处理不同。在JHTB中,起始主和弦处于最高结构层级。然而,模型将其解释为F sus(第五和弦)的下行五度。从压缩角度看,这一解释是合理的,因为它可以复用6抽象,并以句法连贯的方式在两个嵌套紫色区域Cm7_Fsus与B♭m7_E♭sus之间进行类比(见图4)。

另一个有趣的方面是模式9在作品《Sunny》中用于解释重复片段C7-FM7-B♭7-E7-Am7。这是一个典型的III-VI-ii-V-i进行。在大调式中,这样的罗马数字可解释为一系列应用属和弦,其中III是VI的属和弦,VI是ii的属和弦。然而,仔细审视后,这种解释在小调语境中并不成立,因为VI与ii之间的根音音程是减五度而非纯五度。这一点,再加上VI具有大七和弦性质,排除了将VI视为II的应用属和弦的可能性。模型使用FM7与E7之间的VI-V关系正确解释了这五个和弦,这与JHTB中的专家标注一致。

5 总体讨论与结论

本文提出了一种利用库学习技术从观测到的表面序列中发现爵士和声模式的新方法,其中音乐模式发现被形式化为推导与可复用抽象的联合构建。在概念层面上,该方法严肃对待音乐理论中一个熟悉的隐喻:音乐结构由可复用组件构建。在这里,这一隐喻被精确化。和声分析被建模为由原始关系构建的组合性程序,而模式被学习为可复用的抽象,这些抽象可以被系统地组合以生成完整推导。音乐模式不再是表面片段,而是有类型的、组合性的构建模块。它们不仅仅是和弦符号的频繁子串,也不是表面标记的简单拼接。

这提出了一个实践和概念上的问题:音乐模式应如何被封装,以便在使用时无需回忆其完整的内部推导?答案在于它们的类型签名,即表达为约束的组合逻辑关系。例如,我们可以在不将其展开回原始规则的情况下,概括一个学习到的抽象如9:

打开网易新闻 查看精彩图片

对其正确应用而言,重要的是支配该展开中终结符与非终结符的一组约束。这些约束确保模式能够被高效匹配,并能在单步中生成或预测多个和弦。从听者的角度看,解析一首作品可类比为用兼容的结构块(如图4)覆盖一个和弦序列,使整体结构保持连贯。如果只有小的原始关系可用,构建完整分析需要许多增量步骤。更大的抽象则充当预制块:一旦其表面约束与结构约束得到满足,它们就允许在单步中纳入多个和弦,从而降低推断过程中的搜索深度。这也补充了PCFG独立性假设的局限,因为它额外规定了哪些产生式规则组合可能共同出现。在认知上,这暗示了内化的图式如何通过让听者将序列“组块化”为更高阶单元来加速结构解读。音乐经验在某种程度上正是由这种随时间构建的音乐抽象库所捕获。

此外,压缩是否能可靠地产生音乐上合理的分析,仍是一个开放的实证问题。在《Red Clay》的案例中,模型实现了显著压缩,但所得推导非常规:开头的的主和弦被赋予了一个偏离标准和声解释的深层结构角色。这可能反映了原理验证实验中所用小语料库的局限。为应对这一局限,未来工作可以聚焦于提升实现效率。在更大、更多样的数据集上,高度特定或小众的分析可能不再在压缩上最优,因为能泛化到许多作品的模式将受到青睐。与此同时,将音乐理解构想为压缩引导的库学习,为音乐理论本身提供了新视角。它提出了这样一种可能性:和声图式与形式原型等理论构造,源自反复音乐经验中的隐式抽象与复用。

打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片

原文链接: https://arxiv.org/pdf/2605.04622