Вычисление дисперсии на лету, Возможно ли Опции

[hobgoblin]

Подскажите, пожалуйста, существует ли в природе алгоритм, который позволял бы вычислять, пусть даже грубо, дисперсию не по завершению накопления выборки, а в процессе накопления. Есть устройство на ПЛИС, которое вычисляет помимо прочего среднее значение разности фаз в двух каналах внутри импульса переменной длины (от 16 до 2^14 отсчетов). Теперь просят добавить туда вычисление дисперсии, но так чтобы значительных задержек с выдачей результата не было.

[Alex255]

Подскажите, пожалуйста, существует ли в природе алгоритм, который позволял бы вычислять, пусть даже грубо, дисперсию не по завершению накопления выборки, а в процессе накопления. Есть устройство на ПЛИС, которое вычисляет помимо прочего среднее значение разности фаз в двух каналах внутри импульса переменной длины (от 16 до 2^14 отсчетов). Теперь просят добавить туда вычисление дисперсии, но так чтобы значительных задержек с выдачей результата не было.

Если Вы сохраняете всю выборку - проблем никаких. Скажем, после 100 отсчетов оцениваете дисперсию, затем по 200 отсчетам и тд

[Guest_TSerg_*]

m[i] = (1-k)*m[i-1] + k*X[i]
k=1/i
D[i]=((j-1)/j)*D[i-1] + (1/j)*(X[i] - m[i])^2
j=i-1

Вроде так.

[NickNich]

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

Вычисление влоб - невозможно. Для вычисления оценки дисперсии по известной формуле требуется оценка мат. ожидания от всей выборки. Появление нового измерения заставляет вычислять новое значение мат.ожидания, а потом пересчитывать значение дисперсии с уже новым значением.

Выражение, которое привет TSerg, фактически, вычисляет оценки дисперсии по нескольким первым отсчетам, примерно по первым 20-ти. Обратите внимание, что множитель перед обновлением оценки дисперсии (квадрате разности) убывает обратно пропорционально номеру отсчета. Т.е. при каких-то значениях теущего номера обновления просто перестанут обновлять получившуюся оценку, в силу малости их весового коэффициента. Можно даже ввести эффективную длину входного потока, по которой вычисляется оценка лисперсии, сохранять это количество в буфер, а потом считать дисперсию по обычной формуле - так честнее получится

[SIA]

Вычисление влоб - невозможно. Для вычисления оценки дисперсии по известной формуле требуется оценка мат. ожидания от всей выборки. Появление нового измерения заставляет вычислять новое значение мат.ожидания, а потом пересчитывать значение дисперсии с уже новым значением.

Выражение, которое привет TSerg, фактически, вычисляет оценки дисперсии по нескольким первым отсчетам, примерно по первым 20-ти. Обратите внимание, что множитель перед обновлением оценки дисперсии (квадрате разности) убывает обратно пропорционально номеру отсчета. Т.е. при каких-то значениях теущего номера обновления просто перестанут обновлять получившуюся оценку, в силу малости их весового коэффициента. Можно даже ввести эффективную длину входного потока, по которой вычисляется оценка лисперсии, сохранять это количество в буфер, а потом считать дисперсию по обычной формуле - так честнее получится

Не совсем так, формулы для вычисления текущей дисперсии и МО без полного пересчета для любой последовательности давно известны (используются даже в калькуляторах), но требуют повышенной точности вычислений. Есть в любом справочнике (Бронштейн, Выгодский, ну и Вентцель - тервер не забываем). Под рукой нет, если надо, откопаю (можно и вывести). Для ответа существенно, нужно ли "забывание" старых значений (нужна ли весовая функция) или получаемые СКО и МО должны относиться ко всей последовательности в равной мере.

[vladv]

Не совсем так, формулы для вычисления текущей дисперсии и МО без полного пересчета для любой последовательности давно известны (используются даже в калькуляторах), но требуют повышенной точности вычислений. Есть в любом справочнике (Бронштейн, Выгодский, ну и Вентцель - тервер не забываем). Под рукой нет, если надо, откопаю (можно и вывести). Для ответа существенно, нужно ли "забывание" старых значений (нужна ли весовая функция) или получаемые СКО и МО должны относиться ко всей последовательности в равной мере.

Надо. "Откопайте", пожалуйста.

[SIA]

Надо. "Откопайте", пожалуйста.

Хорошо, если не забуду, завтра напишу.

[Guest_TSerg_*]

Если о динамическом процессе известно лишь то, что он стационарен, приведенные мной формулы вполне решают поставленную задачу.
Если хочется сложностей - см. теорию оптимального оценивания, калмановскую фильтрацию (ФК) в рамках байевского подхода. ФК работает по рекуррентным формулам.

[Konste]

первый момент, m1, он же мат. ожидание - сумма элементов выборки, поделенная на объем выборки N. m1 = sum(xi)/N
второй момент, m2, сумма квадратов элементов выборки, нормированная к объему выборки. m2 = sum(xi^2)/N
дисперсия D = m2 - (m1)^2

[NickNich]

Не совсем так, формулы для вычисления текущей дисперсии и МО без полного пересчета для любой последовательности давно известны

Действительно, щас заглянул в справичник - есть такие формулы. Я ошибка в утверждении невозможности оценки.

Если о динамическом процессе известно лишь то, что он стационарен, приведенные мной формулы вполне решают поставленную задачу.
Если хочется сложностей - см. теорию оптимального оценивания, калмановскую фильтрацию (ФК) в рамках байевского подхода. ФК работает по рекуррентным формулам.

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

С КФ ситуация совершенно другая - при проектировании КФ заранее известны все дисперсии измерительного шума и шума процесса. И ФК рекурернтно рассчитывает дисперсию вектора состояния, не принимая во внимание фактическое значение вектора измерения. Т.е. рассчетные значения дисперсии никак не связаны с фактическими значениями. В поставленной задаче дисперсия измеряемой величины, она же - дисперсия измерительного шума, заранее неизвестна (ее требуется рассчитать)

Эскизы прикрепленных изображений

 

[Guest_TSerg_*]

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

С КФ ситуация совершенно другая - при проектировании КФ заранее известны все дисперсии измерительного шума и шума процесса. И ФК рекурернтно рассчитывает дисперсию вектора состояния, не принимая во внимание фактическое значение вектора измерения. Т.е. рассчетные значения дисперсии никак не связаны с фактическими значениями. В поставленной задаче дисперсия измеряемой величины, она же - дисперсия измерительного шума, заранее неизвестна (ее требуется рассчитать)

Проблема только в одном. Несоответствие или плохое соответствие заявленному в сабже.
Вопрос был в получении минимальных задержек в оценке.
Оценка же матожидания вида Mi = (N/(N+1) * Mii + Xi / (N+1) приводит к задержке получения его более-менее достоверного значения вплоть до окончания заданного окна.
По оценке которую я приводил - задержка минимальна.

Более того, именно в таком виде
Mi = (N/(N+1) * Mii + Xi / (N+1) (2)
оценка не сходится к концу интервала,
а необходима вот такая версия
Mi = Mii + Xi / N; (3)

Вот пример моделирования оценки гауссовского СП с дисперсией 1 и мат ожиданием 1.
Красная линия - мной приведенная оценка Mi = (1-1/i)*Mii + Xi / i (1)
Синяя - оценка Mi = Mii + Xi / N;

Отчетливо видно, где скорость получения достоверной оценки выше.
Кроме того, оценка по (1) практически совпадает (до 14-го знака) в конце интервала с точной оценкой M = (1/N)*sum(Xi)

[NickNich]

Проблема только в одном. Несоответствие или плохое соответствие заявленному в сабже.

В сабще была заявлена тема об ускоренном полоучении дисперсии выборки, без накопления и задержки. Со второй итерации, при помощи справочника, такие формулы были написаны. Это точные формулы, просто стандартные формулы для вычисления мат. ожидания и дисперсии переписаны в рекуррентной форме. В моих обозначениях, N - это текущиее дискретное время, оно же - число входных отсчетов, прошедших через систему к этому времени.

Как получена рекуррентная формула для мат. ожидания - смотрите новую картинку, на предыдущей я этого не рисовал. То, что у Вас значения совпадают до 14-того знака неудивительно, это все разные записи одной и той же вормулы. Но в теме обсуждается рекуррентное вычисление дисперсии, а не математического ожидания.

Эскизы прикрепленных изображений

 

[SIA]

Действительно, щас заглянул в справичник - есть такие формулы. Я ошибка в утверждении невозможности оценки.

Да, именно эти рекуррентные формулы и имелись в виду, Вы опередили Результат относится ко всей последовательности в равной мере, т.е. как при классическом анализе выборки (т.е. условная "весовая функция" - прямоугольная).

[vladv]

Интересно, а насколько несмещенная такая оценка дисперсии?
Вот, например, для накопленных n выборок несмещенной оценкой дисперсии будет:
D = sum((X[n]-m)^2) / (n-1)
а не, что кажется естественным:
D = sum((X[n]-m)^2) / n

[SIA]

Интересно, а насколько несмещенная такая оценка дисперсии?
Вот, например, для накопленных n выборок несмещенной оценкой дисперсии будет:
D = sum((X[n]-m)^2) / (n-1)
а не, что кажется естественным:
D = sum((X[n]-m)^2) / n

Не вопрос, просто вводится поправочный множитель n/(n-1)

[Guest_TSerg_*]

Выражение, которое привет TSerg, фактически, вычисляет оценки дисперсии по нескольким первым отсчетам, примерно по первым 20-ти. Обратите внимание, что множитель перед обновлением оценки дисперсии (квадрате разности) убывает обратно пропорционально номеру отсчета. Т.е. при каких-то значениях теущего номера обновления просто перестанут обновлять получившуюся оценку, в силу малости их весового коэффициента. Можно даже ввести эффективную длину входного потока, по которой вычисляется оценка лисперсии, сохранять это количество в буфер, а потом считать дисперсию по обычной формуле - так честнее получится
..
Так я и написал, что решают, но не полностью а на какой-то эффективной длине выборки. Если оценка дисперсии по нескольким десяткам отсчетов удовлетворяет - то задача решена. Если не удовлетворяет, то нужно либо считать точно, либо пользоваться рекуррентными формулами другого типа, по поводу которых меня уже поправили.
..
В моих обозначениях, N - это текущиее дискретное время, оно же - число входных отсчетов, прошедших через систему к этому времени.
..
Но в теме обсуждается рекуррентное вычисление дисперсии, а не математического ожидания.

"Как тебя понимать, Саид ?"

Если и в "Ваших" формулах N это i (текущий номер отсчета), то см. Ваше же выделенное мной.
А рекуррентное вычисление дисперсии включает рекуррентное же вычисление мат.ожидания.

[NickNich]

Интересно, а насколько несмещенная такая оценка дисперсии?
Вот, например, для накопленных n выборок несмещенной оценкой дисперсии будет:
D = sum((X[n]-m)^2) / (n-1)
а не, что кажется естественным:
D = sum((X[n]-m)^2) / n

Это асимтотически несмещенная оценка, т.е. при вычислении диспрерсии по конечной выборке результат имеет смещение, которое стремится к нулю при учеличении длины выборки. При больших длинах разницы между множителями 1/N и 1/(N-1) практически нет...

"Как тебя понимать, Саид ?"

Если Вам что-то непонятно, просто спросите об этом. Для того, чтобы правильно интерпретировать Вашу реплику нужно обладать некоторыми телепатическими способностями. Которые я развить в себе так и не сумел, несмотря на огромное количество потраченного на это времени и сил.

[Guest_TSerg_*]

Если Вам что-то непонятно, просто спросите об этом...

Мне - понятно
Вы же пришли к тому, что и я написал.
Если N - номер отсчета, т.е. N это мое i, то и в Вашем случае последующие значения Xi убывают по весу.
Собственно - я об этом.

[NickNich]

Мне - понятно
Вы же пришли к тому, что и я написал.
Если N - номер отсчета, т.е. N это мое i, то и в Вашем случае последующие значения Xi убывают по весу.
Собственно - я об этом.

А я - нет. Я присал про убывание обновляющей поправки к дисперсии, т.е. вот об этой формуле

D[i]=((j-1)/j)*D[i-1] + (1/j)*(X[i] - m[i])^2

К выражению для мат.ожидания у меня вопросов нет.

[vladv]

Не вопрос, просто вводится поправочный множитель n/(n-1)

Не, вопрос в том, смещена эта оценка или не смещена (я имею ввиду формулы, которые NickNich в посте #10 привел).

Это асимтотически несмещенная оценка, т.е. при вычислении диспрерсии по конечной выборке результат имеет смещение, которое стремится к нулю при учеличении длины выборки. При больших длинах разницы между множителями 1/N и 1/(N-1) практически нет...

Ну так и "D = sum((X[n]-m)^2) / n" "асимптотически несмещенная"... А как насчет смещения (или несмещения) для конкретного N?

Выражение, которое привет TSerg, фактически, вычисляет оценки дисперсии по нескольким первым отсчетам, примерно по первым 20-ти. Обратите внимание, что множитель перед обновлением оценки дисперсии (квадрате разности) убывает обратно пропорционально номеру отсчета. Т.е. при каких-то значениях теущего номера обновления просто перестанут обновлять получившуюся оценку, в силу малости их весового коэффициента. Можно даже ввести эффективную длину входного потока, по которой вычисляется оценка лисперсии, сохранять это количество в буфер, а потом считать дисперсию по обычной формуле - так честнее получится

...

А я - нет. Я присал про убывание обновляющей поправки к дисперсии, т.е. вот об этой формуле

D[i]=((j-1)/j)*D[i-1] + (1/j)*(X[i] - m[i])^2

К выражению для мат.ожидания у меня вопросов нет.

Если внимательно проследить "судьбу" первого "отсчета" (X[k] - m[k])^2, то для i-й оценки дисперсии он войдет с коффициентом 1/j - как и для последнего отсчета (X[k] - m[k])^2. Это верно вообще для всех отсчетов. I.e. в D[i] ВСЕ отсчеты (X[k]-m[k])^2 войдут с коэффициентом 1/j.

Впрочем, даже в формуле D[i]=D[i-1] + (1/i)*(X[i] - m[i])^2 нельзя пренебрегать последними отсчетами, поскольку ряд 1/i расходится.

Сообщение отредактировал vladv - Jan 25 2008, 23:25

[NickNich]

Не, вопрос в том, смещена эта оценка или не смещена (я имею ввиду формулы, которые NickNich в посте #10 привел).
Ну так и "D = sum((X[n]-m)^2) / n" "асимптотически несмещенная"... А как насчет смещения (или несмещения) для конкретного N?

Тут нужно точно понимать смысл употребляемых терминов. "Смещение" оценки это разность между мат.ожиданием оценки и мат.ожиданием оцениваемой величины. Если эта разность равна нулю, то оценка несмещенная. Если эта разность не равна нулю - оценка смещенная. Если ненулевая разность убывает до нуля с увеличением числа обрабатываемых отсчетов - оценка асимтотически несмещенная. Вот в этих терминах, оценка дисперсии с множителем 1/(N-1) - несмещенная, оценка с множителем 1/N - асимтотически несмещенная. Случайная составляющая ошибки оценки дисперсии для конкретного N описываются дисперсией оценки дисперсии. Формулы из книжки - если истинное значение дисперсии равно D, то дисперсия оценки дисперсии для формулы с множителем 1/N: D1 = 2*(N-1)*D^2/N^2, для формулы с множителем 1/(N-1): D2 = 2*D^2/(N-1).
...

Если внимательно проследить "судьбу" первого "отсчета" (X[k] - m[k])^2,

Вот и проследите - полностью распишите формулу и удивитесь. Дело в том, что первый отсчет очитывается с оценкой мат.ожидания по одному отсчету, второй отсчет - с мат.ожиданием по двум отсчетам и т.д.

[vladv]

Тут нужно точно понимать смысл употребляемых терминов. "Смещение" оценки это разность между мат.ожиданием оценки и мат.ожиданием оцениваемой величины. Если эта разность равна нулю, то оценка несмещенная. Если эта разность не равна нулю - оценка смещенная. Если ненулевая разность убывает до нуля с увеличением числа обрабатываемых отсчетов - оценка асимтотически несмещенная. Вот в этих терминах, оценка дисперсии с множителем 1/(N-1) - несмещенная, оценка с множителем 1/N - асимтотически несмещенная. Случайная составляющая ошибки оценки дисперсии для конкретного N описываются дисперсией оценки дисперсии. Формулы из книжки - если истинное значение дисперсии равно D, то дисперсия оценки дисперсии для формулы с множителем 1/N: D1 = 2*(N-1)*D^2/N^2, для формулы с множителем 1/(N-1): D2 = 2*D^2/(N-1).

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

...

Вот и проследите - полностью распишите формулу и удивитесь. Дело в том, что первый отсчет очитывается с оценкой мат.ожидания по одному отсчету, второй отсчет - с мат.ожиданием по двум отсчетам и т.д.

Чему удивиться? То, что каждый отсчет со своей оценкой матожидания обсчитывается - это очевидно. Только при чем здесь это? Мой комментарий относился исключительно к Вашей фразе, которая не верна:

"Выражение, которое привет TSerg, фактически, вычисляет оценки дисперсии по нескольким первым отсчетам, примерно по первым 20-ти. Обратите внимание, что множитель перед обновлением оценки дисперсии (квадрате разности) убывает обратно пропорционально номеру отсчета. Т.е. при каких-то значениях теущего номера обновления просто перестанут обновлять получившуюся оценку, в силу малости их весового коэффициента.".

Сообщение отредактировал vladv - Jan 27 2008, 23:08