Nonparametric Multi Change Point Detection for Markov Chains via Adaptive Clustering

Resumen Técnico: Detección de Múltiples Puntos de Cambio No Paramétricos para Cadenas de Markov mediante Agrupamiento Adaptativo

Planteamiento del Problema
La detección de puntos de cambio fuera de línea (offline) tiene como objetivo identificar los puntos temporales dentro de una secuencia de datos donde la distribución subyacente cambia. Aunque es un tema bien establecido para datos independientes e idénticamente distribuidos (i.i.d.), las técnicas no paramétricas rigurosas para datos dependientes, específicamente flujos de Markov, han permanecido esquivas. Los métodos existentes suelen depender de supuestos paramétricos o requieren el conocimiento previo del número de puntos de cambio. Además, los enfoques estándar de pruebas de hipótesis (por ejemplo, Kolmogorov-Smirnov) enfrentan patologías teóricas cuando se aplican a la detección de múltiples puntos de cambio en flujos de datos dependientes únicos, particularmente en lo que respecta a los parámetros de ajuste que carecen de sentido sin múltiples flujos. Este artículo aborda el desafío de detectar un número desconocido de puntos de cambio en cadenas de Markov no estacionarias sin asumir una forma paramétrica específica para las distribuciones.

Metodología
Los autores proponen un marco no paramétrico que vincula dos componentes de la estadística matemática: las complejidades de Rademacher de las cadenas de Markov y el agrupamiento adaptativo mediante penalización.

1. Función de Riesgo y Objetivo: El método minimiza una varianza de agrupamiento total penalizada. Para una secuencia de puntos de cambio estimados $\tau'_1, \dots, \tau'_L$, el riesgo $R_n$ se define como la suma de las varianzas de los grupos integrada contra la distribución empírica:
   $$R_n(\tau'_1, \dots, \tau'_L) = \sum_{i=0}^{L-1} (\tau'_{i+1} - \tau'_i) \int \hat{F}_{\tau'_i}^{\tau'_{i+1}}(u) (1 - \hat{F}_{\tau'_i}^{\tau'_{i+1}}(u)) d\hat{F}_n(u)$$
   El estimador final se obtiene minimizando el Criterio de Información Bayesiano (BIC):
   $$\text{BIC}_L = \min_{\tau'_1 < \dots < \tau'_L} \left( R_n(\tau'_1, \dots, \tau'_L) + L\zeta_n \right)$$
   donde $\zeta_n$ es una secuencia de penalización adecuadamente creciente.

2. Fundamento Teórico (Desigualdad DKW): Una contribución teórica central es la derivación de una desigualdad de tipo Dvoretzky-Kiefer-Wolfowitz (DKW) para la distribución empírica de cadenas de Markov regenerativas. Al utilizar avances recientes en las complejidades de Rademacher para cadenas regenerativas, los autores establecen un límite de cola para el supremo del proceso empírico. Esta desigualdad incluye un factor $\log n$, que se demuestra es ajustado hasta términos logarítmicos en comparación con la desigualdad DKW estándar para i.i.d.

3. Formulación Computacional: Reconociendo que enumerar todos los posibles puntos de cambio es un problema NP-duro, los autores reformulan el problema de optimización como un problema de optimización binaria no lineal. Proponen dos formulaciones de Programación Entera Mixta (MIP):

   • Una formulación directa de la varianza de agrupamiento.
   • Una reformulación bilineal que evita la división dentro de la función objetivo, permitiendo su solución mediante solucionadores comerciales (por ejemplo, Gurobi). Esta reformulación preserva la optimalidad al tiempo que ofrece mejoras significativas en la velocidad computacional.

Contribuciones Clave y Resultados

• Desigualdad DKW para Cadenas de Markov Regenerativas: El artículo establece una desigualdad de cola de tipo Hoeffding para los supremos de la distribución empírica de cadenas de Markov regenerativas (Teorema 1). Demuestra que este resultado es esencialmente ajustado, recuperando las tasas i.i.d. estándar (hasta términos logarítmicos) cuando el tiempo de regeneración es determinista (es decir, 1). Los autores también discuten la cuestión abierta de derivar una desigualdad de tipo Bennett (Poissoniana) para estas cadenas, lo que mejoraría aún más las funciones de riesgo para regímenes de diferencia de cola.
• Detección Consistente de Múltiples Puntos de Cambio: Explotando la desigualdad DKW, los autores demuestran la consistencia del algoritmo de agrupamiento adaptativo para cadenas de Markov regenerativas (Teorema 2). Bajo supuestos relativos a la brecha mínima entre puntos de cambio y la fuerza mínima de la señal (separación entre distribuciones), el método estima consistentemente tanto el número correcto de puntos de cambio ($\hat{K}_n \to K_n$) como sus ubicaciones. Las tasas de localización se muestran como ajustadas, coincidiendo con las tasas óptimas conocidas para datos i.i.d. hasta factores polilogarítmicos.
• Eficiencia Computacional y Precisión: En simulaciones sobre datos de cadenas de Markov no estacionarias, las formulaciones MIP propuestas (específicamente la reformulación bilineal) recuperan exactamente los verdaderos puntos de cambio. En contraste, el método base estándar, Pruned Exact Linear Time (PELT), sobre-segmenta consistentemente los datos (estimando más puntos de cambio de los que existen), a pesar de ser más rápido en tiempo de ejecución. El método propuesto ofrece un compromiso superior entre precisión y costo computacional.

Significancia y Reivindicaciones
El artículo afirma proporcionar el primer mecanismo de detección de puntos de cambio fuera de línea y no paramétrico para cadenas de Markov regenerativas que logra tasas de convergencia óptimas sin conocimiento previo del número de cambios. Al establecer una desigualdad DKW para esta clase de procesos dependientes, el trabajo llena un vacío teórico en la literatura, demostrando que la dependencia (específicamente la estructura de Markov) no impide fundamentalmente la detectabilidad, siempre que la cadena sea regenerativa.

Los autores posicionan su trabajo como una alternativa rigurosa a los métodos existentes que dependen de modelos paramétricos o que fallan en proporcionar garantías sólidas en el entorno de múltiples puntos de cambio dependientes. Expresan explícitamente que, si bien su marco actual utiliza una medida de integración no ponderada para aprovechar la desigualdad DKW, el desarrollo de contrapartes de Markov para las desigualdades de concentración de tipo Poisson sigue siendo una vía abierta para futuras mejoras. El artículo concluye reconociendo que las extensiones multivariantes siguen siendo un problema abierto, ya que el marco DKW univariante no se transfiere directamente sin nuevas herramientas como los procesos empíricos basados en núcleos (kernels).