Оценка скорости появления события с экспоненциальным сглаживанием и нерегулярными событиями

Представьте, что у меня есть набор измерений x, которые принимаются многими процессами x ₀... x _N в разы t ₀... t _N. Предположим, что в момент времени t я хочу сделать оценку текущего значения x, исходя из предположения о том, что не существует долговременного тренда, о котором я знаю, и что x можно предсказать из алгоритма, такого как экспоненциальное сглаживание. Поскольку у нас много процессов, и N может стать очень большим, я не могу хранить больше нескольких значений (например, предыдущего состояния).

Один из подходов здесь - адаптировать нормальный алгоритм экспоненциального сглаживания. Если образцы берутся регулярно, я бы сохранил оценку y _n, чтобы:

Этот подход невелик, когда выборка нерегулярна, так как многие образцы вместе будут иметь непропорциональное влияние. Поэтому эта формула может быть адаптирована к:

y _n= & alpha; _n. y _n-1 + (1 - & alpha; _n). <Я > х <суб > псуб >

IE динамически корректирует константу сглаживания в зависимости от интервала между двумя предыдущими образцами. Я доволен этим подходом и, похоже, работает. Это первый ответ, приведенный здесь, и хорошее резюме этих методов дано Экнером в этой статье в 2012 году (PDF).

Теперь, мой вопрос заключается в следующем. Я хочу адаптировать приведенное выше, чтобы оценить скорость возникновения. Иногда случается событие. Используя аналогичную методику экспоненты, я хочу получить оценку скорости, в которой происходит событие.

Ни один из них не оказался хорошим, насколько я могу судить. Во-первых, принять событие, которое происходит каждые 500 мс (с одной стороны) и событие, которое происходит с задержкой в 200 мс и с задержкой в 800 мс с другой. Очевидно, что оба они происходят два раза в секунду, поэтому приведенная оценка скорости должна быть одинаковой. Игнорирование времени из последнего образца кажется безрассудным, поэтому я сосредоточусь на второй стратегии. Использование задержки (а не обратной) не оказывается хорошим предиктором, потому что имитация потока проб 200 мс /800 мс дает оценку около 1,5 (на основе среднего числа обратных не является обратным среднему).

Но гораздо важнее то, что ни одна стратегия не справляется с тем, что на самом деле происходит на практике, а это значит, что внезапно все события прекращаются надолго. Таким образом, "последним" значением y является значение на последнем событии, и поэтому оценка скорости никогда не рассчитывается. Следовательно, скорость становится постоянной. Конечно, если бы я анализировал данные ретроспективно, это не было бы проблемой, но я анализирую ее в реальном времени.

Я понимаю, что другой способ сделать это - периодически запускать поток (например, каждые 10 секунд) и подсчитывать количество вхождений в этот 10-секундный интервал. Это очень ресурс, тяжелый мой конец, так как статистика не нужна часто, и мне не нравится запускать поток, который проверяет все из-за проблем с мьютексом. Поэтому я хотел бы (каким-то образом) использовать алгоритм, который регулирует состояние, считанное (например), время с момента последнего образца. Это кажется разумным подходом, как если бы производительность измерялась по времени, выбранному независимо от образцов, время измерения в среднем составляло бы половину пути между периодами между образцами, поэтому очень грубая неопределенная оценка скорости была бы половиной обратной величины время с момента последнего образца. Чтобы усложнить ситуацию, мое время измерения не будет зависеть от образцов.

У меня такое чувство, что у этого есть простой ответ, но он ускользает от меня. У меня есть ощущение, что правильный маршрут состоит в том, чтобы предположить, что события распределены по Пуассону, и получить оценку для & lambda;на основе интервала с последнего образца и некоторой формы скользящей средней, но моя статистика слишком ржавая, чтобы сделать эту работу.

В этом вопросе есть примерно такой обход , но ответ кажется не очень удовлетворительным (надеюсь, я объяснил, почему). Я бы добавил, что фильтр Калмана кажется способным к тяжеловесу, учитывая, что у меня есть одна переменная, чтобы оценить и ничего не знать об этом. Существует множество других близких друг к другу случаев, большинство из которых либо предполагают сохранение больших значений значений (не реалистично здесь с точки зрения памяти), либо не затрагивают две проблемы выше.

Ответы

Ответ 1

Во-первых, если вы предполагаете, что частота возникновения событий сама по себе (или вас интересует только ее долгосрочная средняя), вы можете просто оценить ее как:

& lambda; * = N/(t & minus; t ₀)

где t - текущее время, t ₀ - начало наблюдений, N - количество событий, наблюдаемых с тех пор, как t ₀ и & lambda; * - оценка истинная частота & lambda;.

На этом этапе полезно отметить, что приведенная выше формула оценки может быть переформулирована как интеграл:

& lambda; * = интеграл (& delta; _event (& tau;) d & tau;)/интеграл (1 d & tau;)

где переменная интегрирования & tau; варьируется от t ₀ до t и & delta; _event (& tau;) = sum (& delta; (& tau; & plusmn; t _i), я = 1.. N) представляет собой сумму N дельта-функции Дирака с одним дельта-пиком в момент времени t _i каждого события i.

Конечно, это был бы совершенно бесполезный способ вычисления & lambda; *, но он оказался концептуально полезной формулировкой. В принципе, способ просмотра этой формулы состоит в том, что функция & delta; _event (& tau;) измеряет мгновенную скорость, с которой число событий увеличивается во времени & tau;, тогда как второе подынтегральное выражение, которое просто константа 1, измеряет скорость, с которой время увеличивается со временем (что, конечно, составляет одну секунду в секунду).

ОК, но что, если частота & lambda; может со временем измениться, и вы хотите оценить его текущее значение или, по крайней мере, его среднее значение за последний период?

Используя приведенную выше формулу отношения интегралов, мы можем получить такую оценку просто путем взвешивания обоих подынтегральных выражений некоторой взвешивающей функцией w (& tau;), которая смещена в последнее время:

< _recent= интеграл (& delta; _event (& tau;) w (& tau;) d & tau;)/интеграл (w (& tau;) d & tau;)

Теперь остается только выбрать разумный w (& tau;), чтобы эти интегралы упростили к чему-то легкому вычислению. Как оказалось, если мы выберем экспоненциально убывающую функцию взвешивания вида w (& tau;) = exp (k (& tau; & minus; t)) для некоторой скорости распада k, то интегралы упростят до:

< _recent= sum (exp (k (t _i & minus; t)), я = 0.. N) k/(1 & minus; exp (k ( t ₀ & minus; t)))

В пределе при t ₀ → & Минус; & INFIN; (т.е. на практике, когда общее время наблюдения (t & min; t ₀) намного больше, чем шкала времени распада веса 1/k), это еще больше упрощает:

< _recent= k sum (exp (k (t _i & minus; t)), я = 0.. N)

Увы, наивное применение этой формулы все равно потребует, чтобы мы помнили все время события t _i. Однако мы можем использовать тот же трюк, что и для вычисления обычных экспоненциально взвешенных средних — учитывая средневзвешенную скорость события & lambda; * _recent (t ') в некоторый более ранний момент времени t' и считая, что между t 'и t не произошло никаких новых событий, мы можем вычислить текущее средневзвешенное событие rate & lambda; * _recent (t) просто как:

< недавний (t) = exp (k (t '& minus; t)) & lambda; * _recent (t')

Кроме того, если мы теперь наблюдаем новое событие, происходящее ровно через время t, средневзвешенная скорость события сразу после события становится:

< _recent (t) = k + exp (k (t '& minus; t)) & lambda; * _recent (t')

Таким образом, мы получаем очень простое правило: все, что нам нужно сохранить, - это время t _last предыдущего наблюдаемого события, а оценочная недавняя скорость события < * _last сразу после указанного события. (Мы можем инициализировать их, например, t _last= t ₀ и & lambda; * _last= 0; на самом деле, с & lambda; * _last= 0, значение t _last не имеет значения, хотя для ненулевой & lambda; * _last).

Всякий раз, когда происходит новое событие (в момент времени t _new), мы обновляем эти значения как:

& lambda; * _last & larr; k + exp (k (t _last & minus; t _new)) & lambda; * _last
t _last & larr; т <суб > новыйсуб >

и всякий раз, когда мы хотим узнать последнее среднее значение скорости события в текущее время t, мы просто вычислим его как:

& lambda; * (t) = exp (k (t _last & minus; t)) & lambda; * _last

Ps. Чтобы исправить исходное смещение к (произвольному) начальному значению t _last, мы можем добавить обратно 1/(1 & minus; exp (k (t ₀ & minus; t))) поправочный член, который мы упростили ранее, когда мы предположили, что t & gg; т <суб > 0суб > . Для этого просто начинайте с t _last= 0 при t = t ₀, обновите t _last, как указано выше, но вычислите оценочное недавнее событие средняя скорость в момент времени t как:

</sub> corr (t) = exp (k (t _last & minus; t)) & lambda; * _last/(1 & minus; exp (k (t ₀ & minus; t)))

(Здесь t ₀ обозначает время, в которое вы начинаете измерять события, а не появление первого события.)

Это позволит устранить начальное смещение к нулю за счет увеличения ранней дисперсии. Здесь примерный график, показывающий эффекты коррекции для k = 0,1 и истинной средней скорости события 2:

Красная линия показывает & l; * (t) без первоначальной коррекции смещения (начиная с & lambda; * (t ₀) = 0), тогда как зеленая линия показывает скорректированную смещением оценку & l * суб > коррсуб > (т).

Pps. Как видно из приведенного выше графика, , как вычислено выше, не будет непрерывной функцией времени: он скачет к k всякий раз, когда происходит событие, и экспоненциально убывает к нулю когда события не происходят.

Если вы предпочтете более плавную оценку, вы можете вычислить экспоненциально убывающее среднее значение самого λ:

(t) = интеграл (& lambda; * (& tau;) exp (k ₂ (& tau; & minus; t)) d & tau;)/интеграл (exp (k ₂ (& tau; & minus; t)) d & tau;)

где & lambda; - экспоненциально убывающая средняя скорость события, рассчитанная выше, k ₂ - это скорость затухания для второго среднего, а интегралы превышают & min; & infin; < &тау; & Ле; т.

Этот интеграл можно также вычислить пошаговым правилом обновления, как указано выше:

& lambda; ** _last & larr; W (& Delta; t) & lambda; * _last + exp (& minus; k ₂ & Delta; t) & lambda; ** _last
& lambda; * _last & larr; k ₁ + exp (& minus; k ₁ & Delta; t) & lambda; * _last
t _last & larr; т <суб > новыйсуб >

где k ₁ и k ₂ - это скорости распада для первой и второй средних, & Delta; t = t _new & minus; t _last - это прошедшее время между событиями и:

W (& Delta; t) = k ₂ (exp (& minus; k ₂ & Delta; t) & minus; exp (& minus; k ₁ & Delta; t))/(k ₁ & minus; k ₂)

если k ₁ & ne; k ₂, или

W (& delta; t) = k & Delta; t exp (& минус; k & Delta; t)

если k ₁= k ₂= k (последнее выражение, возникающее из первого как предел, когда (k ₁ & minus; k ₂) → 0).

Чтобы вычислить второе среднее для произвольной точки времени t, используйте ту же формулу:

(t) = W (& Delta; t) & lambda; * _last + exp (& minus; k ₂ & Delta; t) & lambda; ** _{последняясуб >}

кроме & Delta; t = t & minus; т <суб > последняясуб > .

Как и выше, эту оценку можно также скорректировать смещением, применяя подходящий зависящий от времени масштабный коэффициент:

< </ > corr (t) = & lambda; ** (t)/(1 - S (t & minus; t ₀))

где:

S (& Delta; t) = (k ₁ exp (& minus; k ₂ & Delta; t) & minus; k ₂ exp (& minus; k ₁ & Delta; t))/(k ₁ & minus; k ₂)

если k ₁ & ne; k ₂, или

S (& delta; t) = (1 + k & Delta; t) exp (& минус; k & Delta; t)

если k ₁= k ₂= k.

В приведенном ниже графике показаны эффекты этого сглаживания. Красные и зеленые линии показывают: * (t) и < l _corr(t), как указано выше, тогда как желтая и синяя линии показывают: ** (t) и ** _corr (t), рассчитанные с помощью k ₁= 0,1 (как указано выше) и k ₂= 0,2:

Ответ 2

Вы можете попробовать следующее:

Держите оценку zn так, чтобы при каждом событии:

z _n= (z _n-1 + & kappa;). e ^{- <я > & каппа;.} ( т <суб > псуб > -t <суб > п-1суб > )

Это будет сходиться к скорости события в s ^-1. Тогда более слабая лучшая оценка (поскольку по-прежнему возникает ошибка/шум, если вы вычисляете оценку непосредственно перед или сразу после события):

w _n= z _n.e ^{- & kappa;/(2.z _{nсуб > )}}

В вашем примере он будет сходиться к 2s ^-1 (обратный к 500 мс)

Постоянная & kappa; отвечает за сглаживание и находится в s ^-1. Небольшие значения будут больше сглаживаться. Если ваш показатель активности составляет примерно секунды, значение 0,01 с-1

для & kappa; это хорошее начало.

Этот метод имеет начальное смещение, а z ₀ может быть задано для оценки значения для более быстрой сходимости. Небольшие значения & kappa; будет удерживать смещение дольше.

Есть гораздо более мощные способы анализа пуассоновских распределений, но они часто требуют больших буферов. Частотный анализ, такой как преобразование Фурье, является одним.