Score-based change point detection via tracking the best of infinitely many experts

Aquí presento un resumen técnico detallado del artículo "Score-based Change Point Detection via Tracking the Best of Infinitely Many Experts" (Detección de Puntos de Cambio basada en Puntuaciones mediante el Seguimiento del Mejor de Infinitos Expertos), escrito por Anna Markovich y Nikita Puchkin.

---

1. Problema Abordado

El artículo se centra en el problema de la detección de puntos de cambio en línea (online change point detection) en un entorno no paramétrico.

• Escenario: Se observa una secuencia de vectores aleatorios $X_1, \dots, X_T$. Antes de un punto de cambio desconocido $\tau^*$, las observaciones provienen de una densidad de probabilidad $p$. Después de $\tau^*$, provienen de una densidad diferente $q$ ($q \neq p$).
• Desafío: Ni $\tau^*$ ni las densidades $p$ y $q$ son conocidas. El objetivo es detectar el momento del cambio lo más rápido posible (minimizar el retraso de detección) mientras se mantiene una tasa baja de falsas alarmas.
• Limitaciones de enfoques previos:
  • Muchos métodos asumen cambios en la media con distribuciones Gaussianas o sub-Gaussianas.
  • Los métodos paramétricos requieren suposiciones fuertes sobre la familia de distribuciones.
  • Los métodos no paramétricos existentes a menudo son computacionalmente costosos o carecen de límites teóricos rigurosos en regímenes no asintóticos.
  • Métodos anteriores basados en optimización convexa online (como los de Cao et al., 2018) requerían calcular integrales de alta dimensión (la función de partición $\Phi(\theta)$), lo que los hacía inviables para distribuciones generales.

2. Metodología Propuesta

Los autores proponen un algoritmo que combina la predicción secuencial con asesoramiento de expertos y la estimación de funciones de puntuación (score function estimation).

A. Enfoque de Aprendizaje Online

El problema se reformula como un juego de predicción con asesoramiento de expertos:

1. Clase de Referencia: Se utiliza una clase paramétrica de densidades $\mathcal{P} = \{p_\theta : \theta \in \mathbb{R}^d\}$ de la forma:
   $$\log p_\theta(x) = \Psi(x)^\top \theta - \Phi(\theta)$$
   donde $\Psi(x)$ es un mapeo fijo (ej. polinomios o características de base) y $\Phi(\theta)$ es la función de normalización.
2. Pérdida basada en Divergencia de Fisher: Para evitar el cálculo costoso de $\Phi(\theta)$, se mide la cercanía entre la densidad candidata $p_\theta$ y la verdadera densidad utilizando la Divergencia de Fisher. Gracias a la identidad de Green, se puede construir un estimador no sesgado de la pérdida sin necesidad de calcular la integral de normalización:
   $$\ell_t(\theta) = \frac{1}{2} \theta^\top A_t \theta - b_t^\top \theta$$
   donde $A_t$ y $b_t$ dependen de $\nabla \Psi(X_t)$ y $\Delta \Psi(X_t)$.

B. Algoritmo de Detección

El núcleo del método es comparar dos estrategias de predicción online:

1. Promedio Ponderado Exponencialmente (EWA): Un predictor que se adapta a una distribución estática. Si no hay cambio, este predictor tiene un bajo arrepentimiento (regret).
2. Predictor de "Fixed Share" (Acción Fija): Una variante adaptada para un número infinito de expertos. Este predictor es capaz de "cambiar" de experto (adaptarse a un nuevo parámetro $\theta$) cuando la distribución subyacente cambia.

La Estadística de Prueba ($S_t$):
Se define como la diferencia acumulada de pérdidas entre ambos predictores:
$$\hat{S}_t = \hat{L}_{1:t}^{EWA} - \hat{L}_{1:t}^{FS}$$

• Antes del cambio ($t \leq \tau^*$): Ambos predictores se comportan de manera similar, por lo que $\hat{S}_t$ permanece pequeño.
• Después del cambio ($t > \tau^*$): El predictor EWA se queda "atascado" en el parámetro antiguo, mientras que el predictor Fixed Share se adapta rápidamente al nuevo régimen. La diferencia de pérdidas $\hat{S}_t$ crece rápidamente.
• Decisión: Se declara un cambio cuando $\hat{S}_t$ supera un umbral predefinido $z$.

C. Complejidad Computacional

El artículo deriva fórmulas recursivas cerradas para calcular las predicciones del predictor Fixed Share en el caso de infinitos expertos con pérdidas cuadráticas.

• Con una tasa de aprendizaje constante, la complejidad por paso de tiempo es $O(d^3 t)$, resultando en una complejidad total de $O(d^3 T^2)$. Esto es significativamente más eficiente que las implementaciones de fuerza bruta.

3. Contribuciones Clave

1. Algoritmo No Paramétrico Online: Propuesta de un algoritmo para la detección de cambios que no asume formas específicas para $p$ y $q$, solo que sus funciones de puntuación son suaves y aproximables.
2. Extensión del Fixed Share a Infinitos Expertos: Desarrollo de una versión del algoritmo "Fixed Share" (originalmente para un conjunto finito de expertos) aplicable a un espacio continuo de parámetros ($\mathbb{R}^d$) con pérdidas cuadráticas, manteniendo la eficiencia computacional.
3. Límites Teóricos Rigurosos: Derivación de límites de alta probabilidad no asintóticos para la estadística de prueba:
   • Régimen Pre-cambio: Se demuestra que $\hat{S}_t$ está acotado por términos logarítmicos ($O(\log^3 \tau^*)$) con alta probabilidad, garantizando un control de falsas alarmas.
   • Régimen Post-cambio: Se demuestra que $\hat{S}_t$ crece linealmente con el tiempo después del cambio, asegurando la detección.
4. Validación Empírica: Evaluación exhaustiva en datos sintéticos y del mundo real.

4. Resultados Experimentales

Los autores compararon su algoritmo (denominado Algorithm 3.1) contra cuatro métodos competidores:

• FLH (Follow-the-Leading-History).
• FALCON (Enfoque contrastivo basado en optimización convexa).
• KLIEP (Estimación directa de la importancia relativa).
• M-statistic (Detección basada en discrepancia máxima media con kernels).

Hallazgos principales:

• Datos Sintéticos: En tareas de detección de cambios de media y varianza (univariados y multivariados Gaussianos), el algoritmo propuesto logró los retrasos de detección más bajos (a menudo detectando cambios en ~1-3 observaciones) manteniendo cero falsas alarmas.
• Datos Reales (Actividad Humana - WISDM): En un conjunto de datos de acelerómetros de smartphones, el método propuesto superó a los competidores en velocidad de detección y precisión, con un promedio de retraso de 15.43 observaciones frente a 16.29-25.9 de los otros métodos.
• Datos de Voz y Ocupación: En datos de audio (CENSREC) y sensores de habitación, el método mostró robustez ante ruido y superó consistentemente a los métodos basados en ventanas deslizantes (como KLIEP y M-statistic), que sufrieron de mayores retrasos o falsas alarmas.

5. Significado e Impacto

• Superación de Limitaciones Computacionales: Al evitar el cálculo de integrales de normalización ($\Phi(\theta)$) mediante el uso de la divergencia de Fisher, el método hace viable la detección de cambios en modelos no normalizados o de alta dimensión, un problema que limitaba enfoques anteriores como el de Cao et al. (2018).
• Teoría Sólida: Proporciona garantías teóricas rigurosas en un régimen no asintótico, algo raro en métodos no paramétricos de detección de cambios en línea.
• Versatilidad: Al no depender de suposiciones distribucionales fuertes (como la normalidad), el algoritmo es aplicable a una gama más amplia de problemas en el mundo real donde las distribuciones subyacentes son desconocidas o complejas.
• Eficiencia: La derivación de fórmulas recursivas permite su implementación en tiempo real, superando la barrera de complejidad computacional de los métodos de "seguimiento del mejor experto" en espacios continuos.

En resumen, este trabajo presenta un marco unificado que conecta la teoría de aprendizaje online con la estadística de detección de cambios, ofreciendo una solución práctica, teóricamente fundamentada y computacionalmente eficiente para problemas de detección de anomalías y cambios de distribución en tiempo real.