¿Algoritmo en línea para calcular la EWMA a intervalos irregulares?

Question

¿Cuál es un algoritmo rápido en línea para calcular la EWMA (media móvil ponderada exponencialmente) de una variable de entrada observada a intervalos irregulares?

Conozco la fórmula para cuando se toman muestras a intervalos regulares:

Calcular el alfa a partir de la vida media:

$$ \alpha = 1 - e^{\frac{\ln{.5}}{H}} $$

Calcular el EWMA de x:

$$ E = \alpha\cdot x + (1-\alpha)\cdot E_{-1} $$

¿Cuál es el algoritmo para hacer lo mismo cuando el intervalo de muestreo es irregular?

Editar:

He encontrado un algoritmo en línea, que pretende lograr un EWMA irregular.

double operator()(double x)
{
    if (isnan(prev_ewma_)) // we don't decay the first sample
    {
        prev_ewma_ = x;
        prev_time_ = Time::now();
        return x;
    }

    double time_decay = Time::now() - prev_time_;

    double alpha = 1 - std::exp(-time_decay / halflife_);
    double ewma  = alpha * x + (1 - alpha) * prev_ewma_;

    prev_ewma_ = ewma;
    prev_time_ = now;
    return ewma;
}

¿Es correcto este algoritmo?

Answer 1

El código anterior para un EWMA irregular no da exactamente una vida media - al código le falta el $e^{\ln(.5)}$ término que se encuentra en la fórmula anterior. Para obtener una vida media real, el código debería ser así:

double operator()(double x)
{
    if (isnan(prev_ewma_)) // we don't decay the first sample
    {
        prev_ewma_ = x;
        prev_time_ = Time::now();
        return x;
    }

    double time_decay = Time::now() - prev_time_;

    double alpha = 1 - std::exp(std::log(0.5) * time_decay / halflife_);
    double ewma  = alpha * x + (1 - alpha) * prev_ewma_;

    prev_ewma_ = ewma;
    prev_time_ = now;
    return ewma;
}

Para demostrar que esto funciona, observamos cómo se utiliza alfa en la fórmula EWMA.

$$E = \alpha \cdot x + (1-\alpha) \cdot E_{-1}$$

Esperamos que una vez transcurrida la vida media, exactamente la mitad de $E_{-1}$ permanecerá en nuestro valor filtrado. Para cada paso de tiempo de filtrado, el valor restante de $E_{-1}$ se multiplicará por $1-\alpha$ lo que significa que queremos resolver para $\alpha$ tal que

$$0.5 = (1-\alpha)^N$$

donde $N$ es el número de muestras que filtramos durante nuestra vida media. Para un paso de tiempo fijo $dt$ (time_decay en el código), calculamos $N$ como

$$N = \frac{H}{dt}$$

donde $H$ es la vida media. Esto nos da

$$0.5 = (1-\alpha)^{\frac{H}{dt}}$$

Introduciendo nuestra nueva fórmula para $\alpha$ :

$$\alpha = 1 - e^{\ln(0.5) \cdot \frac {dt} {H}}$$

$$(e^{\ln(0.5)\cdot \frac {dt} {H}})^{\frac{H}{dt}}$$

$$e^{\ln(0.5)} = 0.5$$

Quedará exactamente la mitad del valor original.

Answer 2

Se cuenta el número de "intervalos de unidades" dentro de esa duración irregular entre dos eventos y se repite la función de actualización por el recuento. El tiempo amortizado es el número medio de intervalos unitarios.

En los casos de uso práctico, los "intervalos unitarios" son mayores (submuestreo), por lo que se realiza en tiempo constante amortizado.