Фильтр твердых частиц

Фильтры частиц или методы последовательного Монте-Карло (SMC) представляют собой набор алгоритмов Монте-Карло , используемых для решения проблем фильтрации, возникающих при обработке сигналов и байесовском статистическом выводе . Проблема фильтрации состоит в оценке внутренних состояний в динамических системах, когда производятся частичные наблюдения, и случайные возмущения присутствуют в датчиках, а также в динамической системе. Цель состоит в том, чтобы вычислить апостериорные распределения состояний некоторого марковского процесса, учитывая некоторые зашумленные и частичные наблюдения. Термин «фильтры частиц» был впервые введен в употребление в 1996 г. Делом Моралом ^[1] в отношении методов взаимодействующих частиц среднего поля, используемых в механике жидкостей с начала 1960-х годов. Термин «последовательный Монте-Карло» был введен Лю и Ченом в 1998 году ^[2].

Фильтрация частиц использует набор частиц (также называемых выборками) для представления апостериорного распределения некоторого случайного процесса с учетом шумных и / или частичных наблюдений. Модель в пространстве состояний может быть нелинейной, а начальное состояние и распределения шума могут принимать любую требуемую форму. Методы фильтрации частиц обеспечивают хорошо зарекомендовавшую себя методологию ^{[1] [3] [4]} для генерации выборок из требуемого распределения, не требуя предположений относительно модели пространства состояний или распределений состояний. Однако эти методы не работают хорошо при применении к очень многомерным системам.

Фильтры частиц обновляют свои прогнозы приблизительным (статистическим) способом. Выборки из распределения представлены набором частиц; каждой частице присвоен вес правдоподобия, который представляет вероятность того, что эта частица будет выбрана из функции плотности вероятности. Несоответствие веса, ведущее к коллапсу веса, является частой проблемой, с которой сталкиваются эти алгоритмы фильтрации; однако его можно уменьшить, включив шаг повторной выборки до того, как веса станут слишком неравномерными. Можно использовать несколько адаптивных критериев повторной выборки, включая дисперсию весов и относительную энтропию относительно равномерного распределения. ^[5] На этапе повторной выборки частицы с незначительным весом заменяются новыми частицами в непосредственной близости от частиц с более высоким весом.

Со статистической и вероятностной точек зрения фильтры частиц можно интерпретировать как интерпретацию частиц среднего поля вероятностных мер Фейнмана-Каца . ^{[6] [7] [8] [9] [10]} Эти методы интеграции частиц были разработаны в молекулярной химии и вычислительной физике Теодором Э. Харрисом и Германом Каном в 1951 году, Маршаллом Н. Розенблютом и Арианной У. Розенблут в 1955 году ^{[ 11]} и совсем недавно Джеком Х. Хетерингтоном в 1984 году. ^[12] В вычислительной физике эти методы интегрирования частиц по траектории типа Фейнмана-Каца также используются вКвантовый Монте-Карло , а точнее методы диффузионного Монте-Карло . ^{[13] [14] [15]} Методы взаимодействующих частиц Фейнмана-Каца также тесно связаны с генетическими алгоритмами выбора мутаций, которые в настоящее время используются в эволюционных вычислениях для решения сложных задач оптимизации.

Методология фильтрации частиц используется для решения скрытой марковской модели (HMM) и задач нелинейной фильтрации . За заметным исключением линейно-гауссовских моделей наблюдения сигналов ( фильтр Калмана ) или более широких классов моделей (фильтр Бенеша ^[16] ) Мирей Шалея-Морель и Доминик Мишель доказали в 1984 году, что последовательность апостериорных распределений случайных состояний сигнал с учетом наблюдений (он же оптимальный фильтр) не имеет конечно-рекурсивной рекурсии. ^[17] Различные другие численные методы, основанные на аппроксимациях фиксированной сетки, методах Монте-Карло цепей Маркова (MCMC), традиционной линеаризации, расширенных фильтрах Калмана., или определение наилучшей линейной системы (в смысле ожидаемых затрат и ошибок) не могут справиться с крупномасштабными системами, нестабильными процессами или когда нелинейности недостаточно гладкие.

Фильтры частиц и методологии частиц Фейнмана-Каца находят применение в обработке сигналов и изображений , байесовском выводе , машинном обучении , анализе рисков и выборке редких событий , инженерии и робототехнике , искусственном интеллекте , биоинформатике , ^[18] филогенетике , вычислительной науке , экономике и математических финансах. , молекулярная химия , вычислительная физика , фармакокинетика и другие области.

История [ править ]

Эвристические подобные алгоритмы [ править ]

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

Истоки эволюционных вычислительных методов среднего поля можно проследить до 1950 и 1954 годов с основополагающей работой Алана Тьюринга об обучающих машинах по генетическому отбору мутаций ^[19] и статьями Нильса Алла Барричелли из Института перспективных исследований в Принстоне. , Нью-Джерси . ^{[20] [21]} Первые следы фильтров частиц в статистической методологии относятся к середине 1950-х годов; «Монте-Карло бедняков» ^[22], который был предложен Хаммерсли и др. в 1954 году, содержал намеки на методы фильтрации частиц генетического типа, используемые сегодня. В 1963 году Нильс Алл Барричеллисмоделировал алгоритм генетического типа, чтобы имитировать способность людей играть в простую игру. ^[23] В литературе по эволюционным вычислениям алгоритмы выбора мутаций генетического типа стали популярными благодаря основополагающей работе Джона Холланда в начале 1970-х годов и, в частности, его книге ^[24], опубликованной в 1975 году.

В 1957 году австралийский генетик Алекс Фрейзер опубликовал в журнале « Биология и генетика» серию статей о моделировании генетического типа при искусственном отборе организмов. ^[25] Компьютерное моделирование эволюции биологами стало более распространенным в начале 1960-х годов, и методы были описаны в книгах Фрейзера и Бернелла (1970) ^[26] и Кросби (1973). ^[27] Моделирование Фрейзера включало все основные элементы современных алгоритмов генетических частиц с отбором мутаций.

С математической точки зрения условное распределение случайных состояний сигнала при некоторых частичных и зашумленных наблюдениях описывается вероятностью Фейнмана-Каца на случайных траекториях сигнала, взвешенных последовательностью потенциальных функций правдоподобия. ^{[6] [7]} Квантовый Монте-Карло и, более конкретно, диффузионные методы Монте-Карло также могут быть интерпретированы как приближение интегралов по путям Фейнмана-Каца частицами генетического типа среднего поля. ^{[6] [7] [8] [12] [13] [28] [29]}Истоки методов квантового Монте-Карло часто приписывают Энрико Ферми и Роберту Рихтмайеру, которые в 1948 году разработали интерпретацию цепных нейтронных реакций частицами среднего поля ^[30], но первый алгоритм частиц, подобный эвристическому и генетическому (также известный как Resampled или Реконфигурация методов Монте-Карло) для оценки энергий основного состояния квантовых систем (в редуцированных матричных моделях) принадлежит Джеку Х. Хетерингтону в 1984 году. ^[12] Можно также процитировать более ранние основополагающие работы Теодора Э. Харриса и Германа Кана в разделе « Частица». физика, опубликованная в 1951 году, использующая генетические методы среднего поля, но схожие с эвристикой, для оценки энергий прохождения частиц. ^[31]В молекулярной химии использование генетических эвристических методологий частиц (также известных как стратегии сокращения и обогащения) можно проследить до 1955 года, когда был основан основополагающий труд Маршалла. Н. Розенблют и Арианна. В. Розенблют. ^[11]

Использование генетических алгоритмов частиц в расширенной обработке сигналов и байесовском выводе появилось совсем недавно. В январе 1993 года Генширо Китагава разработал «фильтр Монте-Карло» ^[32], слегка измененную версию этой статьи, появившуюся в 1996 году. ^[33] В апреле 1993 года Гордон и др. Опубликовали в своей основополагающей работе ^[34] приложение. алгоритма генетического типа в байесовском статистическом выводе. Авторы назвали свой алгоритм «фильтром начальной загрузки» и продемонстрировали, что по сравнению с другими методами фильтрации их алгоритм начальной загрузки не требует каких-либо предположений об этом пространстве состояний или шумах системы. Независимо от Пьера Дель Мораля ^[1]и Химилькон Карвалью, Пьер Дель Мораль, Андре Монен и Жерар Салю ^[35] о фильтрах частиц, опубликованных в середине 1990-х годов. Фильтры частиц также были разработаны для обработки сигналов в начале 1989-1992 гг. П. Дель Мораль, Дж. К. Нойер, Г. Ригал и Г. Салют в LAAS-CNRS в серии закрытых и засекреченных исследовательских отчетов с STCAN (Service Technique des Constructions et Armes Navales), ИТ-компании DIGILOG и LAAS-CNRS (Лаборатория анализа и архитектуры систем) по проблемам обработки сигналов RADAR / SONAR и GPS. ^{[36] [37] [38] [39] [40] [41]}

Математические основы [ править ]

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

Математические основы и первый строгий анализ этих алгоритмов частиц принадлежат Пьеру Дель Моралю ^{[1] [3]} в 1996 году. Статья ^[1] также содержит доказательство несмещенных свойств приближения частицами функций правдоподобия и ненормализованных условных вероятностные меры. Несмещенная оценка частиц функций правдоподобия, представленная в этой статье, сегодня используется в байесовском статистическом выводе.

Методологии частиц ветвящегося типа с различными размерами популяции также были разработаны к концу 1990-х Дэном Крисаном, Джессикой Гейнс и Терри Лайонс, ^{[42] [43] [44]} и Дэном Крисаном, Пьером Дель Моралем и Терри Лайонсом. ^[45] Дальнейшие разработки в этой области были разработаны в 2000 г. П. Дель Моралем, А. Гионнет и Л. Микло. ^{[7] [46] [47]} Первые центральные предельные теоремы принадлежат Пьеру Дель Моралю и Алисе Гионне ^[48] в 1999 г. и Пьеру Дель Моралю и Лорану Микло ^[7] в 2000 г. Первые результаты равномерной сходимости Временной параметр для фильтров твердых частиц был разработан в конце 1990-х Пьером Дель Моралем и Алисой Гионне.^{[46] [47]} Первый строгий анализ сглаживающих устройств на основе генеалогического дерева был проведен П. Дель Моралем и Л. Микло в 2001 г. ^[49]

Теория методологии частиц Фейнмана-Каца и связанных алгоритмов фильтров частиц была разработана в 2000 и 2004 годах в книгах. ^{[7] [4]} Эти абстрактные вероятностные модели инкапсулируют алгоритмы генетического типа, фильтры частиц и бутстрапов, взаимодействующие фильтры Калмана (также известные как фильтр частиц Рао – Блэквелла ^[50] ), методы фильтрации частиц в стиле выборки по важности и повторной выборки, включая генеалогическое древо и частицы обратные методологии решения задач фильтрации и сглаживания. Другие классы методологий фильтрации частиц включают модели на основе генеалогического дерева, ^{[9] [4] [51]} обратные модели марковских частиц, ^{[9] [52]} адаптивные модели частиц среднего поля,^[5] модели частиц островного типа, ^{[53] [54]} и методологии Монте-Карло с цепью Маркова для частиц. ^{[55] [56]}

Проблема фильтрации [ править ]

Цель [ править ]

Задача фильтра частиц - оценить апостериорную плотность переменных состояния с учетом переменных наблюдения. Фильтр частиц разработан для скрытой Марковской модели , в которой система состоит как из скрытых, так и из наблюдаемых переменных. Наблюдаемые переменные (процесс наблюдения) связаны со скрытыми переменными (состояние-процесс) некоторой известной функциональной формой. Подобным образом динамическая система, описывающая эволюцию переменных состояния, также известна вероятностно.

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

${\ displaystyle {\ begin {array} {cccccccccc} X_ {0} & \ to & X_ {1} & \ to & X_ {2} & \ to & X_ {3} & \ to & \ cdots & {\ text {signal} } \\\ downarrow && \ downarrow && \ downarrow && \ downarrow && \ cdots & \\ Y_ {0} && Y_ {1} && Y_ {2} && Y_ {3} && \ cdots & {\ text {наблюдение}} \ end { множество}}}$

Задача фильтрации состоит в том, чтобы последовательно оценивать значения скрытых состояний , учитывая значения процесса наблюдения на любом временном шаге k .${\ displaystyle X_ {k}}$${\displaystyle Y_{0},\cdots ,Y_{k},}$

Все байесовские оценки следуют из апостериорной плотности p ( x _k  |  y ₀ , y ₁ ,…, y _k ). Методология фильтрации частиц обеспечивает аппроксимацию этих условных вероятностей с использованием эмпирической меры, связанной с алгоритмом частиц генетического типа. Напротив, подход MCMC или выборки по важности будет моделировать полный апостериорный p ( x ₀ , x ₁ ,…, x _k  |  y ₀ , y ₁ ,…,${\displaystyle X_{k}}$ у _к ).

Модель наблюдения за сигналом [ править ]

Методы частиц часто предполагают, и наблюдения могут быть смоделированы в такой форме:${\displaystyle X_{k}}$${\displaystyle Y_{k}}$

• ${\displaystyle X_{0},X_{1},\cdots }$- это марковский процесс на (для некоторых ), который развивается согласно плотности вероятности перехода . Эта модель также часто записывается синтетическим способом как${\displaystyle \mathbb {R} ^{d_{x}}}$${\displaystyle d_{x}\geqslant 1}$${\displaystyle p(x_{k}|x_{k-1})}$

  ${\displaystyle X_{k}|X_{k-1}=x_{k}\sim p(x_{k}|x_{k-1})}$

с начальной плотностью вероятности .${\displaystyle p(x_{0})}$

• Наблюдения принимают значения в некотором пространстве состояний (для некоторых ) и являются условно независимыми при условии, что они известны. Другими словами, каждый зависит только от . Кроме того, мы предполагаем, что условное распределение для данного абсолютно непрерывно, и синтетическим путем имеем${\displaystyle Y_{0},Y_{1},\cdots }$${\displaystyle \mathbb {R} ^{d_{y}}}$${\displaystyle d_{y}\geqslant 1}$${\displaystyle X_{0},X_{1},\cdots }$${\displaystyle Y_{k}}$${\displaystyle X_{k}}$${\displaystyle Y_{k}}$${\displaystyle X_{k}=x_{k}}$

  ${\displaystyle Y_{k}|X_{k}=y_{k}\sim p(y_{k}|x_{k})}$

Пример системы с этими свойствами:

${\displaystyle X_{k}=g(X_{k-1})+W_{k-1}}$

${\displaystyle Y_{k}=h(X_{k})+V_{k}}$

где обе и - взаимно независимые последовательности с известными функциями плотности вероятности, а g и h - известными функциями. Эти два уравнения можно рассматривать как уравнения пространства состояний и они похожи на уравнения пространства состояний для фильтра Калмана. Если функции g и h в приведенном выше примере являются линейными, и если обе и являются гауссовыми , фильтр Калмана находит точное распределение байесовской фильтрации. В противном случае методы на основе фильтра Калмана представляют собой приближение первого порядка ( EKF ) или приближение второго порядка ( UKF${\displaystyle W_{k}}$${\displaystyle V_{k}}$${\displaystyle W_{k}}$${\displaystyle V_{k}}$ в общем, но если распределение вероятностей гауссово, возможно приближение третьего порядка).

Предположение об абсолютной непрерывности начального распределения и переходов цепи Маркова относительно меры Лебега можно ослабить. Чтобы разработать фильтр частиц, нам просто нужно предположить, что мы можем выполнить выборку переходов цепи Маркова и вычислить функцию правдоподобия (см., Например, описание мутации генетического отбора для фильтра частиц, приведенное ниже). Абсолютно непрерывное предположение о марковских переходах используется только для неформального (и довольно оскорбительного) вывода различных формул между апостериорными распределениями с использованием правила Байеса для условных плотностей.${\displaystyle X_{k-1}\to X_{k}}$${\displaystyle X_{k},}$${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$${\displaystyle X_{k}}$

Приближенные байесовские модели вычислений [ править ]

В некоторых задачах условное распределение наблюдений с учетом случайных состояний сигнала может не иметь плотности или может быть невозможно или слишком сложно вычислить. ^[18] В этой ситуации нам нужно прибегнуть к дополнительному уровню приближения. Одна из стратегий состоит в том, чтобы заменить сигнал цепью Маркова и ввести виртуальное наблюдение вида${\displaystyle X_{k}}$${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$

${\displaystyle {\mathcal {Y}}_{k}=Y_{k}+\epsilon {\mathcal {V}}_{k}\quad {\mbox{for some parameter}}\quad \epsilon \in [0,1]}$

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

${\displaystyle {\text{Law}}\left(X_{k}|{\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k}\right)\approx _{\epsilon \downarrow 0}{\text{Law}}\left(X_{k}|Y_{0}=y_{0},\cdots ,Y_{k}=y_{k}\right)}$

Фильтр частиц, связанный с марковским процессом с учетом частичных наблюдений , определяется в терминах эволюционирующих частиц с функцией правдоподобия, заданной с некоторыми очевидными неправильными обозначениями как . Эти вероятностные методы тесно связаны с приближенным байесовским вычислением (ABC). В контексте фильтров твердых частиц эти методы фильтрации частиц ABC были введены в 1998 г. П. Дель Моралем, Дж. Джакодом и П. Проттером. ^[57] Они были развиты П. Дель Моралем, А. Дусе и А. Ясра. ^{[58] [59]}${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$${\displaystyle {\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k},}$${\displaystyle \mathbb {R} ^{d_{x}+d_{y}}}$${\displaystyle p({\mathcal {Y}}_{k}|{\mathcal {X}}_{k})}$

Уравнение нелинейной фильтрации [ править ]

Правило Байеса для условной вероятности дает:

${\displaystyle p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})={\frac {p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})}{p(y_{0},\cdots ,y_{k})}}}$

где

${\displaystyle {\begin{aligned}p(y_{0},\cdots ,y_{k})&=\int p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})dx_{0}\cdots dx_{k}\\p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})&=\prod _{l=0}^{k}p(y_{l}|x_{l})\\p(x_{0},\cdots ,x_{k})&=p_{0}(x_{0})\prod _{l=1}^{k}p(x_{l}|x_{l-1})\end{aligned}}}$

Фильтры твердых частиц также являются приблизительными, но при достаточном количестве частиц они могут быть гораздо более точными. ^{[1] [3] [4] [46] [47]} Уравнение нелинейной фильтрации задается рекурсией

${\displaystyle {\begin{aligned}p(x_{k}|y_{0},\cdots ,y_{k-1})&{\stackrel {\text{updating}}{\longrightarrow }}p(x_{k}|y_{0},\cdots ,y_{k})={\frac {p(y_{k}|x_{k})p(x_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x'_{k})p(x'_{k}|y_{0},\cdots ,y_{k-1})dx'_{k}}}\\&{\stackrel {\text{prediction}}{\longrightarrow }}p(x_{k+1}|y_{0},\cdots ,y_{k})=\int p(x_{k+1}|x_{k})p(x_{k}|y_{0},\cdots ,y_{k})dx_{k}\end{aligned}}}$

(Уравнение 1)

с конвенцией для к = 0. Нелинейная задача фильтрации состоит в вычислении этих условных распределений последовательно.${\displaystyle p(x_{0}|y_{0},\cdots ,y_{k-1})=p(x_{0})}$

Формулировка Фейнмана-Каца [ править ]

Зафиксируем временной горизонт n и последовательность наблюдений , и для каждого k = 0, ..., n зададим:${\displaystyle Y_{0}=y_{0},\cdots ,Y_{n}=y_{n}}$

${\displaystyle G_{k}(x_{k})=p(y_{k}|x_{k}).}$

В этих обозначениях для любой ограниченной функции F на множестве траекторий от начала координат k = 0 до момента времени k = n имеем формулу Фейнмана-Каца${\displaystyle X_{k}}$

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{n})p(x_{0},\cdots ,x_{n}|y_{0},\cdots ,y_{n})dx_{0}\cdots dx_{n}&={\frac {\int F(x_{0},\cdots ,x_{n})\left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}{\int \left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}}\\&={\frac {E\left(F(X_{0},\cdots ,X_{n})\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}}\end{aligned}}}$

Эти модели интеграции пути Фейнмана-Каца возникают в различных научных дисциплинах, в том числе в вычислительной физике, биологии, теории информации и компьютерных науках. ^{[7] [9] [4]} Их интерпретация зависит от области применения. Например, если мы выбираем индикаторную функцию некоторого подмножества пространства состояний, они представляют условное распределение цепи Маркова при условии, что она остается в данной трубке; то есть у нас есть:${\displaystyle G_{n}(x_{n})=1_{A}(x_{n})}$

${\displaystyle E\left(F(X_{0},\cdots ,X_{n})|X_{0}\in A,\cdots ,X_{n}\in A\right)={\frac {E\left(F(X_{0},\cdots ,X_{n})\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}}}$

а также

${\displaystyle P\left(X_{0}\in A,\cdots ,X_{n}\in A\right)=E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}$

как только нормирующая постоянная станет строго положительной.

Фильтры частиц [ править ]

Алгоритм частиц генетического типа [ править ]

Первоначально мы начинаем с N независимых случайных величин с общей плотностью вероятности . Генетический алгоритм перехода от выбора к мутации ^{[1] [3]}${\displaystyle \left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}}$${\displaystyle p(x_{0})}$

${\displaystyle \xi _{k}:=\left(\xi _{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{selection}}{\longrightarrow }}{\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{mutation}}{\longrightarrow }}\xi _{k+1}:=\left(\xi _{k+1}^{i}\right)_{1\leqslant i\leqslant N}}$

имитировать / аппроксимировать переходы между обновлением и прогнозированием оптимальной эволюции фильтра ( уравнение 1 ):

• Во время перехода от выбора к обновлению мы отбираем N (условно) независимых случайных величин с общим (условным) распределением${\displaystyle {\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle \sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})}$

• Во время перехода предсказание мутации из каждой выбранной частицы мы независимо отбираем переход${\displaystyle {\widehat {\xi }}_{k}^{i}}$

${\displaystyle {\widehat {\xi }}_{k}^{i}\longrightarrow \xi _{k+1}^{i}\sim p(x_{k+1}|{\widehat {\xi }}_{k}^{i}),\qquad i=1,\cdots ,N.}$

В приведенных выше формулах обозначает функцию правдоподобия, оцениваемую при , и обозначает условную плотность, оцениваемую при .${\displaystyle p(y_{k}|\xi _{k}^{i})}$${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$${\displaystyle x_{k}=\xi _{k}^{i}}$${\displaystyle p(x_{k+1}|{\widehat {\xi }}_{k}^{i})}$${\displaystyle p(x_{k+1}|x_{k})}$${\displaystyle x_{k}={\widehat {\xi }}_{k}^{i}}$

В каждый момент времени k мы имеем приближения частиц

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})}$

а также

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1})}$

В сообществе генетических алгоритмов и эволюционных вычислений описанная выше цепь Маркова с отбором мутаций часто называется генетическим алгоритмом с пропорциональным отбором. Также в статьях было предложено несколько вариантов ветвления, в том числе со случайными размерами популяции. ^{[4] [42] [45]}

Принципы Монте-Карло [ править ]

Методы частиц, как и все подходы на основе выборки (например, MCMC ), генерируют набор выборок, которые приблизительно соответствуют плотности фильтрации.

${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k}).}$

Например, у нас может быть N выборок из приблизительного апостериорного распределения , где образцы помечены надстрочными индексами как${\displaystyle X_{k}}$

${\displaystyle {\widehat {\xi }}_{k}^{1},\cdots ,{\widehat {\xi }}_{k}^{N}.}$

Тогда ожидания относительно фильтрующего распределения аппроксимируются следующим образом:

${\displaystyle \int f(x_{k})p(x_{k}|y_{0},\cdots ,y_{k})\,dx_{k}\approx _{N\uparrow \infty }{\frac {1}{N}}\sum _{i=1}^{N}f\left({\widehat {\xi }}_{k}^{i}\right)=\int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})}$

(Уравнение 2)

с участием

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})}$

где - мера Дирака в данном состоянии a. Функция f , как обычно для Монте-Карло, может дать все моменты и т. Д. Распределения с точностью до некоторой ошибки аппроксимации. Когда аппроксимационное уравнение ( уравнение 2 ) выполняется для любой ограниченной функции f, мы пишем${\displaystyle \delta _{a}}$

${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k}):=p(x_{k}|y_{0},\cdots ,y_{k})dx_{k}\approx _{N\uparrow \infty }{\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})}$

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

${\displaystyle \left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k-1,k}^{i},{\widehat {\xi }}_{k,k}^{i}\right)}$

частиц . Случайные состояния с нижними индексами l = 0, ..., k обозначают предка индивидуума на уровне l = 0, ..., k. В этой ситуации имеем аппроксимационную формулу${\displaystyle i=1,\cdots ,N}$${\displaystyle {\widehat {\xi }}_{l,k}^{i}}$${\displaystyle {\widehat {\xi }}_{k,k}^{i}={\widehat {\xi }}_{k}^{i}}$

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})\,dx_{0}\cdots dx_{k}&\approx _{N\uparrow \infty }{\frac {1}{N}}\sum _{i=1}^{N}F\left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)\\&=\int F(x_{0},\cdots ,x_{k}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\end{aligned}}}$

(Уравнение 3)

с эмпирической мерой

${\displaystyle {\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))}$

Здесь F обозначает любую основанную функцию на пространстве пути сигнала. В более синтетической форме ( уравнение 3 ) эквивалентно

${\displaystyle {\begin{aligned}p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})\,dx_{0}\cdots dx_{k}\\&\approx _{N\uparrow \infty }{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\end{aligned}}}$

Фильтры частиц можно интерпретировать по-разному. С вероятностной точки зрения они совпадают с интерпретацией уравнения нелинейной фильтрации для частиц среднего поля . Переходы обновления-прогнозирования эволюции оптимального фильтра также можно интерпретировать как переходы классических генетических типов отборов-мутаций индивидуумов. Метод последовательной повторной выборки по важности обеспечивает другую интерпретацию переходов фильтрации, связывающих выборку по важности с этапом начальной повторной выборки. Наконец, что не менее важно, фильтры для частиц можно рассматривать как методологию приемки-отказа, снабженную механизмом рециркуляции. ^{[9] [4]}

Моделирование частиц среднего поля [ править ]

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

Общий вероятностный принцип [ править ]

Эволюцию нелинейной фильтрации можно интерпретировать как динамическую систему в множестве вероятностных мер следующего вида, где - некоторое отображение множества вероятностных распределений в себя. Например, эволюция одношагового оптимального предиктора${\displaystyle \eta _{n+1}=\Phi _{n+1}\left(\eta _{n}\right)}$${\displaystyle \Phi _{n+1}}$${\displaystyle \eta _{n}(dx_{n})=p(x_{n}|y_{0},\cdots ,y_{n-1})dx_{n}}$

удовлетворяет нелинейной эволюции, начиная с распределения вероятностей . Один из самых простых способов аппроксимировать эти вероятностные меры - начать с N независимых случайных величин с общим распределением вероятностей . Предположим, мы определили последовательность из N случайных величин такую, что${\displaystyle \eta _{0}(dx_{0})=p(x_{0})dx_{0}}$${\displaystyle \left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}}$${\displaystyle \eta _{0}(dx_{0})=p(x_{0})dx_{0}}$${\displaystyle \left(\xi _{n}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{n}^{i}}(dx_{n})\approx _{N\uparrow \infty }\eta _{n}(dx_{n})}$

На следующем этапе мы выбираем N (условно) независимых случайных величин с общим законом.${\displaystyle \xi _{n+1}:=\left(\xi _{n+1}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle \Phi _{n+1}\left({\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{n}^{i}}\right)\approx _{N\uparrow \infty }\Phi _{n+1}\left(\eta _{n}\right)=\eta _{n+1}}$

Частичная интерпретация уравнения фильтрации [ править ]

Мы проиллюстрируем этот принцип частиц среднего поля в контексте эволюции одношаговых оптимальных предикторов.

${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}\to p(x_{k+1}|y_{0},\cdots ,y_{k})=\int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}')p(x'_{k}|y_{0},\cdots ,y_{k-1})dx'_{k}}{\int p(y_{k}|x''_{k})p(x''_{k}|y_{0},\cdots ,y_{k-1})dx''_{k}}}}$

(Уравнение 4)

Для k = 0 мы используем соглашение .${\displaystyle p(x_{0}|y_{0},\cdots ,y_{-1}):=p(x_{0})}$

По закону больших чисел имеем

${\displaystyle {\widehat {p}}(dx_{0})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{0}^{i}}(dx_{0})\approx _{N\uparrow \infty }p(x_{0})dx_{0}}$

в смысле

${\displaystyle \int f(x_{0}){\widehat {p}}(dx_{0})={\frac {1}{N}}\sum _{i=1}^{N}f(\xi _{0}^{i})\approx _{N\uparrow \infty }\int f(x_{0})p(dx_{0})dx_{0}}$

для любой ограниченной функции . Далее предполагаем, что мы построили последовательность частиц некоторого ранга k такую, что${\displaystyle f}$${\displaystyle \left(\xi _{k}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }~p(x_{k}~|~y_{0},\cdots ,y_{k-1})dx_{k}}$

в том смысле, что для любой ограниченной функции мы имеем${\displaystyle f}$

${\displaystyle \int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})={\frac {1}{N}}\sum _{i=1}^{N}f(\xi _{k}^{i})\approx _{N\uparrow \infty }\int f(x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$

В этой ситуации, заменив на эмпирических мерах в уравнении эволюции оптимального фильтра одностадийного , указанном в ( э. 4 ) находят , что${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$ ${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

${\displaystyle p(x_{k+1}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }\int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}'){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x''_{k}){\widehat {p}}(dx''_{k}|y_{0},\cdots ,y_{k-1})}}}$

Обратите внимание, что правая часть в приведенной выше формуле представляет собой взвешенную вероятностную смесь.

${\displaystyle \int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}'){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x''_{k}){\widehat {p}}(dx''_{k}|y_{0},\cdots ,y_{k-1})}}=\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{j})}}p(x_{k+1}|\xi _{k}^{i})=:{\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})}$

где обозначает плотность , измеренную при , и обозначает плотность , измеренную при для${\displaystyle p(y_{k}|\xi _{k}^{i})}$${\displaystyle p(y_{k}|x_{k})}$${\displaystyle x_{k}=\xi _{k}^{i}}$${\displaystyle p(x_{k+1}|\xi _{k}^{i})}$${\displaystyle p(x_{k+1}|x_{k})}$${\displaystyle x_{k}=\xi _{k}^{i}}$${\displaystyle i=1,\cdots ,N.}$

Затем мы выбираем N независимых случайных величин с общей плотностью вероятности, так что${\displaystyle \left(\xi _{k+1}^{i}\right)_{1\leqslant i\leqslant N}}$${\displaystyle {\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})}$

${\displaystyle {\widehat {p}}(dx_{k+1}|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k+1}^{i}}(dx_{k+1})\approx _{N\uparrow \infty }{\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})dx_{k+1}\approx _{N\uparrow \infty }p(x_{k+1}|y_{0},\cdots ,y_{k})dx_{k+1}}$

Повторяя эту процедуру, мы построим цепь Маркова так, что

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1}):=p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$

Обратите внимание, что оптимальный фильтр аппроксимируется на каждом временном шаге k с использованием формул Байеса

${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }{\frac {p(y_{k}|x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x'_{k}){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}}=\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k}^{j})}}~\delta _{\xi _{k}^{i}}(dx_{k})}$

Термин «приближение среднего поля» происходит от того факта, что мы заменяем на каждом временном шаге вероятностную меру эмпирическим приближением . Приближение задачи фильтрации с помощью частиц среднего поля далеко не единственно. В книгах разработано несколько стратегий. ^{[9] [4]}${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k-1})}$${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

Некоторые результаты сходимости [ править ]

Анализ сходимости фильтров частиц был начат в 1996 г. ^{[1] [3]} и в 2000 г. в книге ^[7] и серии статей. ^{[45] [46] [47] [48] [49] [60] [61]} Более свежие разработки можно найти в книгах, ^{[9] [4]} Когда уравнение фильтрации устойчиво (в том смысле, что оно исправляет любое ошибочное начальное условие), смещение и дисперсия оценок частицы

${\displaystyle I_{k}(f):=\int f(x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})\approx _{N\uparrow \infty }{\widehat {I}}_{k}(f):=\int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

контролируются неасимптотическими равномерными оценками

${\displaystyle \sup _{k\geqslant 0}\left\vert E\left({\widehat {I}}_{k}(f)\right)-I_{k}(f)\right\vert \leqslant {\frac {c_{1}}{N}}}$

${\displaystyle \sup _{k\geqslant 0}E\left(\left[{\widehat {I}}_{k}(f)-I_{k}(f)\right]^{2}\right)\leqslant {\frac {c_{2}}{N}}}$

для любой функции f, ограниченной 1, и для некоторых конечных констант Кроме того, для любых :${\displaystyle c_{1},c_{2}.}$${\displaystyle x\geqslant 0}$

${\displaystyle \mathbf {P} \left(\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c_{1}{\frac {x}{N}}+c_{2}{\sqrt {\frac {x}{N}}}\land \sup _{0\leqslant k\leqslant n}\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c{\sqrt {\frac {x\log(n)}{N}}}\right)>1-e^{-x}}$

для некоторых конечных констант, связанных с асимптотическим смещением и дисперсией оценки частицы, и некоторой конечной константы c . Те же результаты будут удовлетворены, если мы заменим одношаговый оптимальный предсказатель на приближение оптимального фильтра.${\displaystyle c_{1},c_{2}}$

Генеалогические деревья и свойства непредвзятости [ править ]

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

Сглаживание частиц на основе генеалогического дерева [ править ]

Прослеживая во времени родовые линии

${\displaystyle \left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k-1,k}^{i},{\widehat {\xi }}_{k,k}^{i}\right),\quad \left(\xi _{0,k}^{i},\xi _{1,k}^{i},\cdots ,\xi _{k-1,k}^{i},\xi _{k,k}\right)}$

индивидов и на каждом временном шаге k мы также имеем приближения частиц${\displaystyle {\widehat {\xi }}_{k}^{i}\left(={\widehat {\xi }}_{k,k}^{i}\right)}$${\displaystyle \xi _{k}^{i}\left(={\xi }_{k,k}^{i}\right)}$

${\displaystyle {\begin{aligned}{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\ \\{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\\&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k-1})dx_{0},\cdots ,dx_{k}\end{aligned}}}$

Эти эмпирические приближения эквивалентны приближениям интегральных частиц

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\ \\\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\end{aligned}}}$

для любой ограниченной функции F на случайных траекториях сигнала. Как показано в ^[51], эволюция генеалогического дерева совпадает с интерпретацией среднеполевой частицами уравнений эволюции, связанных с апостериорными плотностями сигнальных траекторий. Для получения более подробной информации об этих моделях пространства путей мы отсылаем к книгам. ^{[9] [4]}

Несмещенные оценки функций правдоподобия частицами [ править ]

Мы используем формулу продукта

${\displaystyle p(y_{0},\cdots ,y_{n})=\prod _{k=0}^{n}p(y_{k}|y_{0},\cdots ,y_{k-1})}$

с участием

${\displaystyle p(y_{k}|y_{0},\cdots ,y_{k-1})=\int p(y_{k}|x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})}$

а также конвенции и для K = 0. Заменяя в эмпирическом приближении${\displaystyle p(y_{0}|y_{0},\cdots ,y_{-1})=p(y_{0})}$${\displaystyle p(x_{0}|y_{0},\cdots ,y_{-1})=p(x_{0}),}$${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$