Martingalas de potencia para la detección de cambios: ¿M va a cero?

Question

Estoy tratando de aplicar el marco de la martingala de poder por [ Vovk et al., 2003 ] para la detección de cambios en flujos de datos no etiquetados, al igual que en [ Ho y Wechsler, 2007 ]. La idea básica consiste en utilizar una martingala de potencia de la forma $$M_n^{(\epsilon)} := \prod_{i=1}^n\left(\epsilon p_i^{\epsilon-1}\right) = \epsilon p_n^{\epsilon-1} M_{n-1}^{(\epsilon)}.$$ Si he entendido bien el método, se supone que funciona de la siguiente manera:

• $p_i$ son valores p de alguna secuencia de entrada que se distribuyen uniformemente en $[0,1]$ cuando la secuencia es intercambiable;
• cuando se viola la intercambiabilidad, $p_i$ se hacen más pequeños, y $M_n$ comienza a crecer;
• cuando $M_n$ ha crecido hasta algún umbral o la diferencia entre los vecinos $M_n$ ha superado algún umbral, hacemos sonar la alarma de que se ha producido algún cambio y volvemos a empezar.

Parece muy sencillo, pero no he conseguido que funcione: en mis datos, los valores de $M_n$ osciló aleatoriamente durante un tiempo, pero muy pronto bajó a cero (a valores como 1e-100) y se quedó ahí; hubo algunos factores grandes cuando se produjo un cambio real en los datos, pero se necesitarían muchos factores para volver de 1e-100...

Intenté una prueba simple: generé una distribución uniforme $p_i$ y calculado $M_n$ para ellos. Aquí está el código python completo de mi prueba ( $\epsilon=0.92$ es un valor sugerido por los documentos, pero he probado otros $\epsilon$ con resultados similares):

epsilon = 0.92
pv_test = [random.random() for _ in xrange(5000)]
test_mult = [epsilon * (x ** (epsilon - 1)) for x in pv_test]
Mtest = [1]
for i in xrange(len(test_mult)):
    Mtest.append(Mtest[i] * test_mult[i])

Y observé el mismo comportamiento: $M_n$ ¡siempre bajaba a cero! A veces más rápido, a veces más lento, pero siempre. Aquí hay algunos gráficos de muestra de $M_n$ :

Parece un paseo aleatorio, pero siempre acaba cayendo a cero incluso para valores p perfectamente uniformes. Obviamente, esto no funcionará para la detección de cambios porque incluso una secuencia relativamente larga de valores p pequeños no puede resucitar $M_n$ de 1e-100.

Así que mi pregunta es: ¿qué estoy haciendo mal?

Answer 1

Su aplicación es correcta. La martingala de potencia tiende a ser muy pequeña (más cercana a 0) cuando los valores p están distribuidos uniformemente. Para evitar eso, sólo tiene que reiniciar su martingala desde 1 tan pronto como se hace más pequeño que 1. Así que sólo tiene que añadir:

Mtest[i] = max(Mtest[i], 1)

Esto mantendrá su martingala pequeña (pero no inferior a 1) cuando los valores p se distribuyan uniformemente, incluso durante un período largo.

Answer 2

Creo que se puede ver la naturaleza del problema si se calcula cuántos puntos de datos "extraños" se necesitan, dado que se ha observado una larga serie de puntos de datos "no extraños" (usando el lenguaje de Ho y Wechsler aquí).

Hagamos algunos cálculos de memoria: para un flujo de $k$ puntos de datos con constante $p_i = p$ entonces $M_k \sim 10^{k(\text{log}_{10}(\epsilon) + (\epsilon-1) \text{log}_{10}(p))}$ . Digamos que después de un número $n$ de puntos de datos no extraños con $p_i = .5$ (el valor esperado de una RV uniforme sobre $[0,1]$ ), obtenemos un flujo de $\eta$ extraños acontecimientos con $p_i \sim 10^{-3}$ . A continuación, nos preguntamos "¿qué tamaño tiene $\eta$ tiene que ser antes de $M_{n+\eta} \sim 10$ ?" (el umbral dado en Ho y Wechsler).

Si utilizamos $\epsilon = .92$ después del flujo de datos no extraños ( $n$ puntos con $p_i=.5$ ) tenemos que $M_n \sim 10^{-.012n}$ . Abusando un poco de la notación, vamos a denotar que la "contribución" del flujo de datos sorprendente es $M_{\eta}$ (así $M_{n+\eta} = M_n M_{\eta}$ ), podemos entonces calcular que $M_{\eta} = 10^{.204 \eta}$ . Dado el umbral de $10$ queremos $M_{n+\eta} = 10^{.204\eta - .012n} = 10$ o $.204\eta - .012n = 1$ Por lo tanto $\eta = \frac{1+.012n}{.204} \approx 5 + .06 n$ . Esto significa que $\eta$ tiene que estar en torno al 6% de $n$ si vamos a pasar el umbral de 10.

Obviamente, esto es sólo un cálculo aproximado, pero creo que presenta una clara intuición del problema: este método de martingala es robusto frente a series cortas de datos sorprendentes. Cuantos más datos no sorprendentes tenga, más datos sorprendentes necesitará antes de que concluya que se ha producido un cambio. Dado que le das 5000 observaciones no extrañas, necesitarás unas 300 bastante extrañas para convencerle de que se ha producido un cambio. Obsérvese que en Ho y Wechsler parecen alimentar con datos sorprendentes cada 1000 puntos de datos, lo que significa que sólo necesitan unos 60 puntos de datos sorprendentes.

Answer 3

En mi opinión, no entiendes el concepto de cambio. Intenta hacer esto:

1. Debe implementar un conjunto de datos con al menos 2 clusters con vectores de n dimensiones (para una prueba es mejor 2-dimesiones).
2. Su código debe leer una a una todas las fechas del cluster #1. Cuando tu código empiece a leer las fechas del cluster #2 tu martigale debe detectar un cambio.

Sobre el algoritmo. Es necesario implementar (todas las referencias están en Ho & Wechler papel):

1. Medida de la extrañeza. Yo intentaría aplicar el modelo de cluster (fórmula 7). Calcule todas las fechas medias leídas hasta ese momento (centroide del cluster). A continuación hay que calcular la distancia euclidiana para cada punto leído hasta ese momento desde el centroide.
2. Función del valor P (fórmula 7). La medida de extrañeza es una entrada para esta fórmula.
3. Introduzca cada valor p en Martingale.
4. Debe definir un valor Lambda para activar una alarma de cambio.