Рекуррентное оценивание

Пакетная обработка и алгоритмы реального времени

Допустим, мы хотим оценивать состояние системы по результатам многократных измерений её некоторых параметров. Результаты измерений поступают с некоторой периодичностью в моменты времени \(t_k\), где \(k = 0, 1, 2,\ldots\).

Существуют два возможных подхода к решению данной задачи.

Пакетная обработка (batch processing). Мы ожидаем, когда будут получены все измерения, а потом один раз проводим все вычисления. Такой режим ещё называют автономной обработкой (off-line processing).

Обработка в режиме реального времени (on-line processing). Требуется, чтобы получаемые данные измерений сразу же использовались для текущей оценки состояния системы, а потом с каждым новым измерением наша оценка бы уточнялась. Этот режим ещё называется неавтономной обработкой.

Оценивание среднего значения случайной константы

Предположим, нам необходимо в реальном времени оценивать среднее значение неизвестной случайной константы, основываясь на ряде её зашумлённых измерений.

Каждый результат измерения обозначим \(y_k\), где \(k = 0, 1, 2,\ldots\) — дискретные моменты времени.

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

\[\hat{m}_1 = y_1 .\]

После получения 2-го измерения вычислим арифметическое среднее двух имеющихся значений:

\[\hat{m}_2 = \frac{y_1 + y_2}{2}.\]

После 3-го измерения:

\[\hat{m}_3 = \frac{y_1 + y_2 + y_3}{3}\]

и т. д. После \(k\)-го измерения:

\[\hat{m}_k = \frac{y_1 + y_2 + \ldots + y_k}{k} = \frac{1}{k}\sum_{i=1}^k{y_i}.\]

Очевидно, что описанная процедура больше подходит для однократного вычисления (после получения всех отсчётов измерений), чем для режима онлайн, т.к. требует на каждом шаге больших вычислительных затрат и большого объёма памяти для хранения всех прошлых значений измеряемой величины.

Рекуррентная процедура оценивания случайной константы

Модифицируем алгоритм для работы в режиме реального времени. Запишем формулу для \(k\)-го шага, выделив в числителе \(k-1\) предыдущих слагаемых:

\[\hat{m}_k = \frac{y_1 + y_2 + \ldots + y_{k-1}}{k} + \frac{y_k}{k}.\]

Но ведь на предыдущем, \((k-1)\)-м шаге мы уже вычисляли эту сумму, только знаменатель был на 1 меньше:

\[\hat{m}_{k-1} = \frac{y_1 + y_2 + \ldots + y_{k-1}}{k-1}.\]

Поэтому проще восстановить сумму, умножив предыдущую оценку на старый знаменатель, чем суммировать все предыдущие значения заново:

\[y_1 + y_2 + \ldots + y_{k-1} = \hat{m}_{k-1} \cdot (k-1).\]

В результате алгоритм вычислений будет следующим.

Первый шаг оставим без изменений:

\[\hat{m}_1 = y_1 ,\]

а на 2-м шаге (после получения результата 2-го измерения) будем вычислять очередное значение оценки, используя её предыдущее значение:

\[\hat{m}_2 = \frac{1}{2} \hat{m}_1 + \frac{1}{2} y_2 .\]

На 3-м шаге:

\[\hat{m}_3 = \frac{2}{3} \hat{m}_2 + \frac{1}{3} y_3\]

и т. д. На \(k\)-м шаге:

\[\hat{m}_k = \frac{k-1}{k} \hat{m}_{k-1} + \frac{1}{k} y_k .\]

На каждом шаге требуется знать только три числа: предыдущее значение оценки, номер измерения и новый результат измерения. Все остальные данные хранить не надо, в вычислениях они не участвуют.

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

(продолжение следует...)

Ссылки



Комментарии

Комментариев пока нет.

* Обязательные поля
(Не публикуется)
 
Жирный Курсив Подчеркнутый Перечеркнутый Степень Индекс Код PHP Код Кавычки Вставить линию Вставить маркированный список Вставить нумерованный список Вставить ссылку Вставить e-mail Вставить изображение Вставить видео
 
Улыбка Печаль Удивление Смех Злость Язык Возмущение Ухмылка Подмигнуть Испуг Круто Скука Смущение Несерьёзно Шокирован
 
1000
Captcha
Refresh
 
Введите код:
 
Запомнить информацию введенную в поля формы.