Riepilogo Tecnico: Generazione di Sequenze di Ordine Variabile con Vincoli Esatti tramite Propagazione di Credenza su Stati-Contesto Sparsi

1. Enunciato del Problema

I sistemi di generazione di sequenze affrontano spesso un conflitto tra coerenza statistica locale e controllo globale esplicito. I modelli di Markov a ordine variabile (VOM) eccellono nel primo aspetto condizionando ogni simbolo al suffisso più lungo disponibile della storia che ha osservato continuazioni, preservando così i pattern stilistici locali senza la rigidità dei modelli a ordine fisso. Tuttavia, i metodi esatti esistenti per vincoli regolari (ad esempio, posizioni fisse, sottostringhe proibite, pattern metrici) tramite Propagazione di Credenza (BP) sono limitati alle catene di Markov del primo ordine.

Il problema centrale affrontato è come combinare la generazione VOM con vincoli regolari senza:

1. Collassare la memoria: Proiettare il generatore a ordine variabile in una catena del primo ordine, che fonde storie distinte e perde le informazioni contestuali specifiche richieste per le probabilità a ordine variabile corrette.
2. Espandere lo spazio degli stati: Elevare il modello a uno spazio degli stati denso di ordine-$K$ (tutte le possibili $K$-tuple), che è computazionalmente intrattabile ($|V|^K$) e ignora la sparsità dei dati di addestramento effettivi.

Un'applicazione ingenua della BP del primo ordine come maschera di fattibilità fallisce perché non riesce a distinguere tra futuri "fragili" (bassa massa di probabilità sotto i vincoli) e futuri "abbondanti", portando a distribuzioni condizionali errate.

2. Metodologia

2.1 Astrazione Sparsa degli Stati-Contesto

Il documento propone una costruzione sparsa degli stati-contesto. Invece di utilizzare l'ultimo simbolo emesso (primo ordine) o tutte le possibili $K$-tuple (ordine-$K$ denso), lo stato di inferenza è definito come il contesto attivo osservato nel modello addestrato.

• Insieme degli Stati-Contesto ($\mathcal{T}$): L'insieme dei contesti osservati memorizzati dal VOM, chiuso rispetto ai suffissi richiesti dalla regola di backoff.
• Sistema di Transizione: Le transizioni sono definite emettendo un simbolo $y$ e aggiornando il contesto al suffisso più lungo della nuova storia che esiste in $\mathcal{T}$.
• Pesi degli Archi: La probabilità di una transizione è la probabilità condizionale a ordine variabile $P_{VO}(y|s)$, potenzialmente modificata da politiche di generazione (ad esempio, evitamento dei singoletti).

2.2 Integrazione dei Vincoli Regolari

Il metodo costruisce un automata prodotto tra il grafo dei contesti sparsi e l'automata del vincolo regolare $\mathcal{A} = (Q, V, \delta, q_0, F)$.

• Spazio degli Stati: Lo stato di inferenza è una coppia $(s, q)$, dove $s \in \mathcal{T}$ è il contesto attivo e $q \in Q$ è lo stato dell'automata.
• Propagazione di Credenza: Viene eseguita la programmazione dinamica standard forward-backward su questo grafo prodotto.
  • Messaggi Indietro ($\beta$): Calcolano la massa "accettante" totale rimanente da un dato stato prodotto fino all'orizzonte.
  • Campionamento: Il campionamento ancestrale viene eseguito selezionando gli archi proporzionalmente al prodotto della probabilità di transizione locale e del messaggio indietro dello stato di destinazione.

2.3 Gestione delle Politiche di Generazione

Il documento distingue tra condizionamento esatto di una fonte stocastica fissa e politiche di generazione vincolata (ad esempio, backoff stile Continuator).

• Se la selezione dell'ordine fa parte della definizione della fonte fissa, la BP produce una posteriori esatta.
• Se la selezione dell'ordine è una politica dinamica (ad esempio, "salta i contesti ad alto ordine con continuazioni singoletto"), il documento formalizza questo come un processo sequenziale in cui la BP fornisce la massa futura esatta all'interno di ciascun ordine candidato, e la politica seleziona l'ordine più alto fattibile. Ciò richiede una separazione esplicita dell'inferenza BP dalla logica della politica per mantenere la chiarezza semantica.

2.4 Aumento dei Dati Reversibile

Il framework supporta trasformazioni reversibili (ad esempio, trasposizione di altezza) senza materializzare i corpora trasformati. I conteggi per un contesto $s$ sotto la trasformazione $g$ sono calcolati tramite ricerca inversa:
$$N_G(s, y) = \sum_{g \in G} N(g^{-1}s, g^{-1}y)$$
Ciò permette alla meccanica BP di operare su una fonte aumentata "virtuale" memorizzando solo la tabella dei conteggi originali.

3. Contributi Chiave

1. Estensione a Ordine Variabile della Macchina BP-Regolare: Il documento identifica lo spazio degli stati sparsi corretto (contesti osservati) su cui eseguire gli algoritmi BP-regolari esistenti per generatori a ordine variabile, evitando la discrepanza delle proiezioni del primo ordine.
2. Costruzione Sparsa Esatta: Una decomposizione formale che mostra come la generazione vincolata esatta possa essere ottenuta eseguendo la BP sul prodotto dei contesti a ordine variabile osservati e dell'automata del vincolo.
3. Analisi della Complessità: L'inferenza è lineare nell'orizzonte della sequenza per un grafo prodotto addestrato fisso e polinomiale nel numero di archi prodotto raggiungibili, piuttosto che esponenziale nell'ordine $K$.
4. Separazione delle Politiche: Una chiara distinzione tra l'inferenza BP esatta e le politiche di selezione dell'ordine al momento della generazione (come l'evitamento dei singoletti), assicurando che le affermazioni di "esattezza" siano semanticamente precise.
5. Interfaccia di Aumento Virtuale: Un metodo per gestire l'aumento reversibile dei dati a livello di fonte, corrispondente alle statistiche dei corpora materializzati senza memorizzarli.

4. Risultati Sperimentali

4.1 Verifica dell'Esattezza (Corpora Minuscoli)

Utilizzando corpora di interi piccoli dove la distribuzione vincolata completa può essere enumerata:

• Funzione di Partizione: La funzione di partizione calcolata dalla BP ($Z_{BP}$) corrispondeva esattamente all'enumerazione brute-force ($Z_{brute}$) (entro la precisione in virgola mobile).
• Accuratezza Distribuzionale: Le probabilità condizionali indotte dal campionatore BP corrispondevano alla distribuzione vincolata esatta.
• Soddisfazione dei Vincoli: Tutte le sequenze campionate soddisfacevano i vincoli (posizionali e sottostringhe proibite).
• Confronto: Le maschere di supporto del primo ordine non sono riuscite a produrre la distribuzione corretta, confermando la necessità dell'approccio stato-contesto.

4.2 Scalabilità (Esperimento sul Preludio di Bach)

È stato eseguito un test di scalabilità su una codifica solo di altezza del Preludio in Do di Bach (592 eventi, 25 altezze) con un orizzonte di 32 e un vincolo MAXORDER (che proibisce i 5-grammi copiati).

• Riduzione dello Spazio degli Stati: All'ordine massimo $K=6$, il prodotto raggiungibile sparso aveva 1.205 stati e 83.207 archi.
  • Questo è di ordini di grandezza inferiore al limite superiore del prodotto completo (~3,4 milioni di archi) e allo spazio degli stati sollevato denso ($25^6 \approx 2,4 \times 10^8$ stati).
• Prestazioni: Il calcolo del passaggio indietro ha richiesto < 0,1 secondi; il campionamento ha richiesto < 0,4 ms per sequenza.
• Comportamento della Politica: Una politica vincolata dello stack di ordini ha navigato con successo i vincoli, trovando continuazioni fattibili dove un condizionamento ingenuo della fonte fissa avrebbe prodotto massa zero per ordini superiori.
• Aumento Virtuale: Un esperimento di trasposizione su 12 tonalità ha mostrato che l'aumento virtuale corrispondeva alla materializzazione esplicita nella massa di successo e nella distribuzione, memorizzando solo il corpus originale.

4.3 Confronto Implementativo

Rispetto a un'implementazione esistente di Continuator (limitata ai vincoli posizionali):

• La nuova implementazione vo-regular-bp ha calcolato i messaggi indietro significativamente più velocemente per ordini $K \ge 3$.
• Il tempo di generazione end-to-end è stato più veloce per $K \ge 3$.

5. Significato e Affermazioni

Il documento afferma che le informazioni sui vincoli regolari possono essere calcolate esattamente su prodotti di contesti sparsi senza abbandonare la struttura a ordine variabile che rende il backoff attraente.

• Correttezza: Il metodo fornisce la corretta distribuzione a ordine variabile condizionata ai vincoli regolari, evitando le insidie delle proiezioni del primo ordine (che fondono storie distinte) e dell'elevazione densa (che è computazionalmente proibitiva).
• Praticità: L'approccio abilita la generazione interattiva e vincolata in domini creativi (come la musica) dove piccoli corpora e vincoli specifici (ad esempio, anti-plagio) sono critici.
• Modestia: Gli autori dichiarano esplicitamente che il lavoro non introduce nuova teoria dei vincoli regolari o BP per linguaggi regolari in generale. La novità è strettamente l'estensione a ordine variabile: applicare macchinari noti alla corretta astrazione degli stati sparsi.
• Limiti: L'affermazione di esattezza è condizionata alla definizione della fonte stocastica. Se le politiche di generazione (come l'evitamento dei singoletti) vengono applicate euristica, il risultato è una politica di generazione vincolata esatta, non necessariamente la posteriori esatta di una fonte fissa non modificata.

Il lavoro funge da decomposizione tecnica dello spazio di progettazione per i sistemi generativi controllati, offrendo una soluzione concreta, esatta e scalabile per combinare la previsione a ordine variabile con il controllo regolare a orizzonte finito.