Resumen Técnico: Generación Exacta de Cadenas de Markov de Orden Variable con Restricciones Regulares Mediante Propagación de Creencias en Estados de Contexto Dispersos

1. Planteamiento del Problema

Los sistemas de generación de secuencias a menudo enfrentan un conflicto entre la coherencia estadística local y el control global explícito. Los modelos de Markov de orden variable (VOM) sobresalen en lo primero al condicionar cada símbolo sobre el sufijo más largo disponible del historial que ha observado continuaciones, preservando patrones estilísticos locales sin la rigidez de los modelos de orden fijo. Sin embargo, los métodos exactos existentes para restricciones regulares (por ejemplo, posiciones fijas, subcadenas prohibidas, patrones métricos) mediante Propagación de Creencias (BP) se limitan a cadenas de Markov de primer orden.

El problema central abordado es cómo combinar la generación VOM con restricciones regulares sin:

1. Colapsar la memoria: Proyectar el generador de orden variable en una cadena de primer orden, lo que fusiona historiales distintos y pierde la información de contexto específica requerida para las probabilidades de orden variable correctas.
2. Expandir el espacio de estados: Elevar el modelo a un espacio de estados denso de orden-$K$ (todas las posibles $K$-tuplas), lo cual es computacionalmente intratable ($|V|^K$) e ignora la dispersión de los datos de entrenamiento reales.

Una aplicación ingenua de BP de primer orden como máscara de factibilidad falla porque no puede distinguir entre futuros "frágiles" (baja masa de probabilidad bajo restricciones) y futuros "abundantes", lo que conduce a distribuciones condicionales incorrectas.

2. Metodología

2.1 Abstracción de Estado de Contexto Disperso

El artículo propone una construcción de estado de contexto disperso. En lugar de utilizar el último símbolo emitido (primer orden) o todas las posibles $K$-tuplas (orden-$K$ denso), el estado de inferencia se define como el contexto activo observado en el modelo entrenado.

• Conjunto de Estados de Contexto ($\mathcal{T}$): El conjunto de contextos observados almacenados por el VOM, cerrado bajo los sufijos requeridos por la regla de retroceso (backoff).
• Sistema de Transición: Las transiciones se definen emitiendo un símbolo $y$ y actualizando el contexto al sufijo más largo del nuevo historial que existe en $\mathcal{T}$.
• Pesos de las Aristas: La probabilidad de una transición es la probabilidad condicional de orden variable $P_{VO}(y|s)$, potencialmente modificada por políticas de tiempo de generación (por ejemplo, evitación de ocurrencias únicas).

2.2 Integración de Restricciones Regulares

El método construye un autómata producto entre el grafo de contexto disperso y el autómata de restricción regular $\mathcal{A} = (Q, V, \delta, q_0, F)$.

• Espacio de Estados: El estado de inferencia es un par $(s, q)$, donde $s \in \mathcal{T}$ es el contexto activo y $q \in Q$ es el estado del autómata.
• Propagación de Creencias: Se realiza programación dinámica estándar hacia adelante-hacia atrás en este grafo producto.
  • Mensajes hacia Atrás ($\beta$): Calculan la "masa aceptante" restante total desde un estado producto dado hasta el horizonte.
  • Muestreo: Se realiza muestreo ancestral seleccionando aristas proporcionales al producto de la probabilidad de transición local y el mensaje hacia atrás del estado de destino.

2.3 Manejo de Políticas de Tiempo de Generación

El artículo distingue entre la condicionamiento exacto de una fuente estocástica fija y las políticas de generación restringida (por ejemplo, retroceso estilo Continuator).

• Si la selección de orden es parte de la definición fija de la fuente, BP produce un posterior exacto.
• Si la selección de orden es una política dinámica (por ejemplo, "saltar contextos de alto orden con continuaciones únicas"), el artículo formaliza esto como un proceso secuencial donde BP proporciona la masa futura exacta dentro de cada orden candidato, y la política selecciona el orden factible más alto. Esto requiere una separación explícita de la inferencia BP de la lógica de la política para mantener la claridad semántica.

2.4 Aumento de Datos Reversible

El marco soporta transformaciones reversibles (por ejemplo, transposición de altura) sin materializar corpus transformados. Los conteos para un contexto $s$ bajo la transformación $g$ se calculan mediante búsqueda inversa:
$$N_G(s, y) = \sum_{g \in G} N(g^{-1}s, g^{-1}y)$$
Esto permite que la maquinaria BP opere sobre una fuente aumentada "virtual" mientras almacena solo la tabla de conteos original.

3. Contribuciones Clave

1. Extensión de Orden Variable de la Maquinaria BP-Regulada: El artículo identifica el espacio de estados disperso correcto (contextos observados) sobre el cual ejecutar los algoritmos existentes BP-regulados para generadores de orden variable, evitando la incompatibilidad de las proyecciones de primer orden.
2. Construcción Dispersa Exacta: Una descomposición formal que muestra que la generación restringida exacta puede lograrse ejecutando BP sobre el producto de los contextos de orden variable observados y el autómata de restricción.
3. Análisis de Complejidad: La inferencia es lineal en el horizonte de la secuencia para un grafo producto entrenado fijo y polinómica en el número de aristas producto alcanzables, en lugar de exponencial en el orden $K$.
4. Separación de Políticas: Una distinción clara entre la inferencia BP exacta y las políticas de orden de tiempo de generación (como la evitación de ocurrencias únicas), asegurando que las afirmaciones de "exactitud" sean semánticamente precisas.
5. Interfaz de Aumento Virtual: Un método para manejar el aumento de datos reversible a nivel de fuente, igualando las estadísticas de los corpus materializados sin almacenarlos.

4. Resultados Experimentales

4.1 Verificación de Exactitud (Corpus Pequeños)

Utilizando corpus enteros pequeños donde la distribución restringida completa puede enumerarse:

• Función de Partición: La función de partición calculada por BP ($Z_{BP}$) coincidió exactamente con la enumeración por fuerza bruta ($Z_{brute}$) (dentro de la precisión de punto flotante).
• Precisión Distribucional: Las probabilidades condicionales inducidas por el muestreador BP coincidieron con la distribución restringida exacta.
• Satisfacción de Restricciones: Todas las secuencias muestreadas satisficieron las restricciones (posicionales y de subcadenas prohibidas).
• Comparación: Las máscaras de soporte de primer orden fallaron al producir la distribución correcta, confirmando la necesidad del enfoque de estado de contexto.

4.2 Escalabilidad (Experimento con Preludio de Bach)

Se realizó una prueba de escalabilidad en una codificación solo de alturas del Preludio en Do de Bach (592 eventos, 25 alturas) con un horizonte de 32 y una restricción MAXORDER (prohibiendo 5-gramos copiados).

• Reducción del Espacio de Estados: En el orden máximo $K=6$, el producto alcanzable disperso tenía 1,205 estados y 83,207 aristas.
  • Esto es varias órdenes de magnitud menor que el límite superior del producto completo (~3.4 millones de aristas) y el espacio de estados elevado denso ($25^6 \approx 2.4 \times 10^8$ estados).
• Rendimiento: El cálculo del paso hacia atrás tomó < 0.1 segundos; el muestreo tomó < 0.4 ms por secuencia.
• Comportamiento de la Política: Una política de pila de orden restringida navegó con éxito las restricciones, encontrando continuaciones factibles donde un condicionamiento de fuente fija ingenuo habría producido masa cero para órdenes superiores.
• Aumento Virtual: Un experimento de transposición de 12 tonos mostró que el aumento virtual coincidió con la materialización explícita en masa de éxito y distribución mientras almacenaba solo el corpus original.

4.3 Comparación de Implementación

En comparación con una implementación existente de Continuator (restringida a restricciones posicionales):

• La nueva implementación vo-regular-bp calculó mensajes hacia atrás significativamente más rápido para órdenes $K \ge 3$.
• El tiempo de generación de extremo a extremo fue más rápido para $K \ge 3$.

5. Significado y Afirmaciones

El artículo afirma que la información de restricción regular puede calcularse exactamente sobre productos de contexto dispersos sin abandonar la estructura de orden variable que hace atractivo el retroceso.

• Correctitud: El método proporciona la distribución de orden variable correcta condicionada a restricciones regulares, evitando los peligros de las proyecciones de primer orden (que fusionan historiales distintos) y la elevación densa (que es computacionalmente prohibitiva).
• Practicidad: El enfoque permite la generación interactiva y restringida en dominios creativos (como la música) donde los corpus pequeños y las restricciones específicas (por ejemplo, anti-plagio) son críticos.
• Modestia: Los autores declaran explícitamente que el trabajo no introduce nueva teoría de restricciones regulares ni BP para lenguajes regulares en general. La novedad es estrictamente la extensión de orden variable: aplicar maquinaria conocida a la abstracción de estado disperso correcta.
• Limitaciones: La afirmación de exactitud es condicional a la definición de la fuente estocástica. Si las políticas de tiempo de generación (como la evitación de ocurrencias únicas) se aplican heurísticamente, el resultado es una política de generación restringida exacta, no necesariamente el posterior exacto de una fuente de orden fijo no modificada.

El trabajo sirve como una descomposición técnica del espacio de diseño para sistemas generativos controlados, ofreciendo una solución concreta, exacta y escalable para combinar la predicción de orden variable con el control regular de horizonte finito.