Resumo Técnico: Geração Exata de Markov de Ordem Variável com Restrições Regulares via Propagação de Crença em Estados de Contexto Esparsos

1. Declaração do Problema

Sistemas de geração de sequências frequentemente enfrentam um conflito entre coerência estatística local e controle global explícito. Modelos de Markov de Ordem Variável (VOM) excel no primeiro aspecto ao condicionar cada símbolo ao sufixo mais longo disponível da história que possui continuações observadas, preservando padrões estilísticos locais sem a rigidez de modelos de ordem fixa. No entanto, os métodos exatos existentes para restrições regulares (por exemplo, posições fixas, substrings proibidas, padrões métricos) via Propagação de Crença (BP) limitam-se a cadeias de Markov de primeira ordem.

O problema central abordado é como combinar a geração VOM com restrições regulares sem:

1. Colapsar a memória: Projetar o gerador de ordem variável em uma cadeia de primeira ordem, o que funde histórias distintas e perde a informação de contexto específica necessária para probabilidades de ordem variável corretas.
2. Expandir o espaço de estados: Elevar o modelo para um espaço de estados denso de ordem-$K$ (todos os $K$-tuplos possíveis), o que é computacionalmente intratável ($|V|^K$) e ignora a esparsidade dos dados de treinamento reais.

Uma aplicação ingênua de BP de primeira ordem como máscara de viabilidade falha porque não consegue distinguir entre futuros "frágeis" (baixa massa de probabilidade sob restrições) e futuros "abundantes", levando a distribuições condicionais incorretas.

2. Metodologia

2.1 Abstração de Estado de Contexto Esparso

O artigo propõe uma construção esparsa de estado de contexto. Em vez de usar o último símbolo emitido (primeira ordem) ou todos os $K$-tuplos possíveis (ordem-$K$ densa), o estado de inferência é definido como o contexto ativo observado no modelo treinado.

• Conjunto de Estados de Contexto ($\mathcal{T}$): O conjunto de contextos observados armazenados pelo VOM, fechado sob sufixos exigidos pela regra de retrocesso (backoff).
• Sistema de Transição: As transições são definidas pela emissão de um símbolo $y$ e atualização do contexto para o sufixo mais longo da nova história que existe em $\mathcal{T}$.
• Pesos das Arestas: A probabilidade de uma transição é a probabilidade condicional de ordem variável $P_{VO}(y|s)$, potencialmente modificada por políticas de tempo de geração (por exemplo, evitação de singletons).

2.2 Integração de Restrições Regulares

O método constrói um autômato produto entre o grafo de contexto esparso e o autômato de restrição regular $\mathcal{A} = (Q, V, \delta, q_0, F)$.

• Espaço de Estados: O estado de inferência é um par $(s, q)$, onde $s \in \mathcal{T}$ é o contexto ativo e $q \in Q$ é o estado do autômato.
• Propagação de Crença: Programação dinâmica padrão forward-backward é realizada neste grafo produto.
  • Mensagens Reversas ($\beta$): Calculam a massa "aceitadora" restante total de um dado estado produto até o horizonte.
  • Amostragem: Amostragem ancestral é realizada selecionando arestas proporcionais ao produto da probabilidade de transição local e da mensagem reversa do estado de destino.

2.3 Tratamento de Políticas de Tempo de Geração

O artigo distingue entre condicionamento exato de uma fonte estocástica fixa e políticas de geração com restrições (por exemplo, retrocesso estilo Continuator).

• Se a seleção de ordem faz parte da definição da fonte fixa, o BP produz um posterior exato.
• Se a seleção de ordem é uma política dinâmica (por exemplo, "pular contextos de alta ordem com continuações de singleton"), o artigo formaliza isso como um processo sequencial onde o BP fornece massa futura exata dentro de cada ordem candidata, e a política seleciona a ordem mais alta viável. Isso requer separação explícita da inferência BP da lógica da política para manter a clareza semântica.

2.4 Aumento de Dados Reversível

O framework suporta transformações reversíveis (por exemplo, transposição de altura) sem materializar corpora transformados. Contagens para um contexto $s$ sob transformação $g$ são computadas via consulta inversa:
$$N_G(s, y) = \sum_{g \in G} N(g^{-1}s, g^{-1}y)$$
Isso permite que a maquinaria BP opere em uma fonte aumentada "virtual" enquanto armazena apenas a tabela de contagens original.

3. Contribuições Principais

1. Extensão de Ordem Variável da Maquinaria BP-Regulares: O artigo identifica o espaço de estados esparso correto (contextos observados) no qual executar algoritmos BP-regular existentes para geradores de ordem variável, evitando o descompasso de projeções de primeira ordem.
2. Construção Esparsa Exata: Uma decomposição formal mostrando que a geração com restrições exata pode ser alcançada executando BP no produto de contextos de ordem variável observados e o autômato de restrição.
3. Análise de Complexidade: A inferência é linear no horizonte da sequência para um grafo produto treinado fixo e polinomial no número de arestas do produto alcançáveis, em vez de exponencial na ordem $K$.
4. Separação de Políticas: Uma distinção clara entre inferência BP exata e políticas de ordem de tempo de geração (como evitação de singletons), garantindo que as alegações de "exatidão" sejam semanticamente precisas.
5. Interface de Aumento Virtual: Um método para lidar com aumento de dados reversível no nível da fonte, correspondendo às estatísticas de corpora materializados sem armazená-los.

4. Resultados Experimentais

4.1 Verificação de Exatidão (Corpora Minúsculos)

Usando pequenos corpora inteiros onde a distribuição completa com restrições pode ser enumerada:

• Função de Partição: A função de partição computada pelo BP ($Z_{BP}$) correspondeu exatamente à enumeração por força bruta ($Z_{brute}$) (dentro da precisão de ponto flutuante).
• Precisão Distribucional: As probabilidades condicionais induzidas pelo amostrador BP corresponderam à distribuição com restrições exata.
• Satisfação de Restrições: Todas as sequências amostradas satisfizeram as restrições (posicionais e substring proibida).
• Comparação: Máscaras de suporte de primeira ordem falharam em produzir a distribuição correta, confirmando a necessidade da abordagem de estado de contexto.

4.2 Escalabilidade (Experimento Prelúdio de Bach)

Um teste de escalabilidade foi realizado em uma codificação apenas de altura do Prelúdio em Dó de Bach (592 eventos, 25 alturas) com um horizonte de 32 e uma restrição MAXORDER (proibindo 5-gramas copiados).

• Redução do Espaço de Estados: Na ordem máxima $K=6$, o produto alcançável esparso tinha 1.205 estados e 83.207 arestas.
  • Isso é ordens de magnitude menor que o limite superior do produto completo (~3,4 milhões de arestas) e o espaço de estados elevado denso ($25^6 \approx 2,4 \times 10^8$ estados).
• Desempenho: O cálculo da passagem reversa levou < 0,1 segundos; a amostragem levou < 0,4 ms por sequência.
• Comportamento da Política: Uma política de pilha de ordem com restrições navegou com sucesso pelas restrições, encontrando continuação viáveis onde um condicionamento de fonte fixa ingênuo teria produzido massa zero para ordens mais altas.
• Aumento Virtual: Um experimento de transposição de 12 tons mostrou que o aumento virtual correspondeu à materialização explícita em massa de sucesso e distribuição enquanto armazenava apenas o corpus original.

4.3 Comparação de Implementação

Comparado a uma implementação existente do Continuator (restrita a restrições posicionais):

• A nova implementação vo-regular-bp calculou mensagens reversas significativamente mais rápido para ordens $K \ge 3$.
• O tempo de geração ponta a ponta foi mais rápido para $K \ge 3$.

5. Significado e Alegações

O artigo alega que informação de restrição regular pode ser computada exatamente em produtos de contexto esparsos sem abandonar a estrutura de ordem variável que torna o retrocesso atraente.

• Correção: O método fornece a distribuição de ordem variável correta condicionada a restrições regulares, evitando as armadilhas de projeções de primeira ordem (que fundem histórias distintas) e elevação densa (que é computacionalmente proibitiva).
• Praticidade: A abordagem permite geração interativa e com restrições em domínios criativos (como música) onde pequenos corpora e restrições específicas (por exemplo, anti-plágio) são críticos.
• Modéstia: Os autores afirmam explicitamente que o trabalho não introduz nova teoria de restrição regular ou BP para linguagens regulares em geral. A novidade é estritamente a extensão de ordem variável: aplicar maquinaria conhecida à abstração de estado esparso correta.
• Limitações: A alegação de exatidão é condicional à definição da fonte estocástica. Se políticas de tempo de geração (como evitação de singletons) forem aplicadas heuricamente, o resultado é uma política de geração com restrições exata, não necessariamente o posterior exato de uma fonte de ordem fixa não modificada.

O trabalho serve como uma decomposição técnica do espaço de design para sistemas generativos controlados, oferecendo uma solução concreta, exata e escalável para combinar previsão de ordem variável com controle regular de horizonte finito.