Resumo Técnico: Aprendizado de Biblioteca com E-graphs na Harmonia Jazzística

Declaração do Problema

O artigo aborda o desafio da Descoberta de Padrões Musicais (MPD) no domínio da harmonia jazzística. A dificuldade central reside em identificar regularidades musicais recorrentes que sejam simultaneamente:

1. Suficientemente abstratas para subsumir repetições não exatas (capturando estruturas de "semelhança familiar" em vez de mera correspondência de strings).
2. Analiticamente significativas para suportar a interpretação estrutural.

Abordagens existentes frequentemente enfrentam um trade-off: padrões altamente abstratos arriscam gerar falsos positivos, enquanto padrões altamente específicos falham em capturar variações. Além disso, métodos tradicionais separam parsing (inferir uma derivação a partir de uma gramática fixa) e aprendizado de biblioteca (descobrir abstrações reutilizáveis a partir de um corpus de programas). Os autores argumentam que, em um cenário não supervisionado onde o objetivo é aprender padrões diretamente a partir de dados de superfície (progressões de acordes), esses dois problemas são mutuamente dependentes: o espaço de derivações possíveis depende das abstrações disponíveis, e a utilidade de uma abstração depende de seu papel em derivações específicas. Uma abordagem sequencial ingênua (parsing exaustivo primeiro, depois aprendizado de uma biblioteca) leva à intratabilidade computacional devido à explosão combinatória das árvores de parsing (escalando com números de Catalan).

Metodologia

Os autores propõem um modelo computacional não supervisionado que integra parsing dedutivo com aprendizado de biblioteca usando e-graphs (grafos de igualdade). O sistema é implementado em egglog, uma extensão declarativa do framework de saturação de igualdade que suporta programação lógica bottom-up.

1. Representação como uma Linguagem de Domínio Específico (DSL)

A análise harmônica é modelada como um programa generativo em uma DSL.

• Primitivas: Em vez de reescrever símbolos de acordes, a gramática usa predicados lógicos representando relações harmônicas (ex: V-I, QuintaDescendente). Essas relações afirmam restrições entre instâncias de acordes (ex: intervalos de raiz, qualidades de acorde).
• Estrutura: Uma derivação é uma composição dessas relações, formando uma árvore onde os nós internos são predicados lógicos conectando objetos de acorde estruturados.

2. O Pipeline Integrado

O modelo opera em três etapas interconectadas para evitar a explosão combinatória de enumerar todas as árvores de parsing:

• Etapa de Parsing (Parsing Dedutivo):

  • Progressões de acordes são codificadas como fatos lógicos (axiomas).
  • Um procedimento dedutivo estilo CYK é implementado dentro do e-graph.
  • Em vez de comprometer-se com uma única árvore de parsing, o sistema mantém uma representação de Floresta de Parsing Empacotada Compartilhada (SPPF). Todas as derivações válidas para uma peça são armazenadas compactamente como classes de equivalência (e-classes) dentro de um único e-graph, mesclando sub-derivações idênticas.
  • Uma passagem de filtragem (propagação top-down de conectividade à raiz) garante que apenas derivações participando de um parsing completo da peça sejam retidas.

• Etapa de Abstração (Anti-unificação):

  • O sistema identifica padrões candidatos realizando anti-unificação sobre as e-classes.
  • A anti-unificação computa a generalização menos geral de duas sub-derivações, substituindo subárvores incompatíveis por variáveis para criar um template parametrizado.
  • Esse processo é intercalado com a saturação do e-graph para garantir eficiência, computando anti-unificadores entre classes de equivalência em vez de árvores individuais.

• Etapa de Refatoração (Aprendizado de Biblioteca e Análise de Custo):

  • Padrões candidatos são adicionados ao e-graph como regras de reescrita, acionando a saturação de igualdade para explorar todas as derivações equivalentes obtíveis via essas novas abstrações.
  • Análise de Conjunto de Custos: O sistema avalia bibliotecas candidatas usando um objetivo de Comprimento Mínimo de Descrição (MDL). Cada termo no e-graph está associado a um conjunto de custos de pares (custo(ℒ), custo(𝒟|ℒ)), representando a complexidade da biblioteca e o custo de codificar os dados dada essa biblioteca.
  • Uma heurística de busca em feixe (beam-search) poda o espaço de busca para encontrar a biblioteca ℒ* que minimiza o comprimento total de descrição: arg min (custo(ℒ) + custo(𝒟|ℒ)).
  • A saída final é uma base de código refatorada: uma biblioteca aprendida de padrões harmônicos e derivações comprimidas para cada peça expressas em termos dessa biblioteca.

Contribuições Principais

1. Framework de Inferência Conjunta: O artigo propõe uma arquitetura inovadora que infere conjuntamente derivações estruturadas para peças individuais e um conjunto compartilhado de abstrações reutilizáveis, tratando-as como variáveis mutuamente dependentes em vez de etapas sequenciais.
2. Integração de E-graphs para Música: Adapta o algoritmo Babble (originalmente para síntese de programas) ao domínio da teoria musical. Ao utilizar e-graphs, o modelo pode representar e manipular famílias exponencialmente grandes de derivações equivalentes sem enumeração explícita.
3. Formalização de Padrões como Abstrações Tipadas: O trabalho formaliza padrões musicais não como substrings de superfície, mas como blocos de construção composicionais e tipados (relações lógicas) que podem ser reutilizados para gerar análises harmônicas completas.
4. Implementação em egglog: Os autores fornecem uma implementação declarativa usando egglog, aproveitando suas capacidades de programação lógica bottom-up para expressar parsing CYK e anti-unificação de forma eficiente.

Resultados

O estudo apresenta uma avaliação de prova de conceito em um pequeno corpus de três standards de jazz (Red Clay, Valse Hot, Sunny) devido aos limites computacionais atuais em conjuntos de dados maiores e altamente ambíguos.

• Resultados Quantitativos:

  • Compressão: O aprendizado conjunto com uma biblioteca compartilhada reduziu o tamanho total da derivação de 87 nós (gramática base) para 27 nós.
  • Eficiência: A taxa de compressão normalizada (CR) para o aprendizado conjunto foi de 1,5, comparada a 1,16 para o aprendizado peça a peça (onde cada peça induz sua própria biblioteca). Isso demonstra que compartilhar abstrações entre peças produz explicações mais econômicas do que tratar as peças isoladamente.
  • Custo de Armazenamento: A abordagem conjunta incorreu em um custo total de armazenamento menor (31) comparado à abordagem peça a peça (47), apesar da sobrecarga da biblioteca compartilhada.

• Resultados Qualitativos:

  • O modelo identificou com sucesso progressões jazzísticas padrão (ex: ii-V-I, quintas descendentes) como padrões reutilizáveis.
  • Descobriu constituintes estruturalmente incompletos (ex: padrões de ramificação esquerda como "tônica faltando uma dominante"), alinhando-se com a aplicação direcional de funções na gramática categorial.
  • Interpreções Inconvencionais: Em Red Clay, o modelo produziu uma derivação que atribuiu um papel estrutural profundo à tônica inicial, diferindo das anotações de especialistas no Jazz Harmony Tree Bank (JHTB). Os autores notam que isso foi impulsionado pela eficiência de compressão, permitindo a reutilização de uma abstração específica (f6) através de regiões aninhadas.
  • Em Sunny, o modelo interpretou corretamente uma sequência complexa usando uma relação VI-V, evitando uma interpretação inválida de dominante aplicada que surgiria em um contexto de modo maior.

Significado e Alegações

O artigo alega que sua abordagem oferece uma nova perspectiva sobre cognição e teoria musicais:

• Plausibilidade Cognitiva: O modelo sugere que ouvintes humanos podem adquirir compreensão musical através de ciclos iterativos de hipótese e revisão, construindo "bibliotecas" de esquemas reutilizáveis que permitem o "agrupamento" (chunking) de sequências em unidades de ordem superior. Isso espelha o processo de refatoração na engenharia de software.
• Teoria como Compressão: Postula que constructos teóricos como esquemas harmônicos e arquétipos formais podem emergir de abstração e reutilização implícitas sobre experiências musicais repetidas, impulsionados pela pressão por explicações compactas (compressão).
• Limitações e Trabalho Futuro: Os autores são modestos sobre suas alegações, reconhecendo que a implementação atual ainda não é escalável para grandes corpora altamente ambíguos. Eles notam que a análise "inconvencional" de Red Clay pode refletir uma limitação do pequeno conjunto de dados, onde padrões de nicho podem parecer ótimos para compressão. Trabalhos futuros exigem melhoria na eficiência de implementação e conjuntos de dados maiores e mais diversos para garantir que os padrões aprendidos generalizem através do gênero em vez de sobreajustar a peças específicas.

O artigo conclui que, embora a compressão não garanta análises musicalmente plausíveis em todos os casos, o framework de aprendizado de biblioteca guiado por compressão fornece uma hipótese computacional rigorosa sobre como padrões musicais estruturados e reutilizáveis podem ser descobertos de forma não supervisionada a partir de dados de superfície.