Фильтр твердых частиц - Википедия - Particle filter

Фильтры твердых частиц или же Последовательный Монте-Карло (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] филогенетика, вычислительная наука, Экономика и математические финансы, молекулярная химия, вычислительная физика, фармакокинетический и другие поля.

История

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

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

Истоки эволюционных вычислительных методов типа среднего поля можно проследить до 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] но первый эвристический алгоритм частиц генетического типа (также известный как методы повторной выборки или реконфигурации Монте-Карло) для оценки энергий основного состояния квантовых систем (в сокращенных матричных моделях) был создан Джеком Х. Хетерингтоном в 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 { множество}}}$

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

Все байесовские оценки ${ displaystyle X_ {k}}$ следовать из задняя плотность п(Икс_k | у₀,у₁,…,у_k). Методология фильтрации частиц обеспечивает приближение этих условных вероятностей с использованием эмпирической меры, связанной с алгоритмом частиц генетического типа. Напротив, MCMC или же выборка по важности подход будет смоделировать полный задний п(Икс₀,Икс₁,…,Икс_k | у₀,у₁,…,у_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_ {к} = г (X_ {k-1}) + W_ {k-1}}$

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

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

Предположение об абсолютной непрерывности начального распределения и переходов цепи Маркова относительно меры Лебега можно ослабить. Чтобы разработать фильтр частиц, нам просто нужно предположить, что мы можем семплировать переходы ${ 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 {для некоторого параметра}} quad epsilon in [0,1]}$

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

${ displaystyle { text {Law}} left (X_ {k} | { mathcal {Y}} _ {0} = y_ {0}, cdots, { mathcal {Y}} _ {k} = y_ {k} right) приблизительно _ { epsilon downarrow 0} { text {Law}} left (X_ {k} | Y_ {0} = y_ {0}, cdots, Y_ {k} = y_ {k} right)}$

Фильтр частиц, связанный с марковским процессом ${ 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})}$. Эти вероятностные методы тесно связаны с Приближенное байесовское вычисление (ABC). В контексте фильтров твердых частиц эти методы фильтрации частиц ABC были введены в 1998 г. П. Дель Моралем, Дж. Джакодом и П. Проттером.^[57] Дальнейшее развитие они получили П. Дель Мораль, А. Дусе и А. Ясра.^[58][59]

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

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

${ 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 {align} 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 {выравнивается}}}$

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

${ displaystyle { begin {align} p (x_ {k} | y_ {0}, cdots, y_ {k-1}) & { stackrel { text {update}} { 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 {align}}}$

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

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

Формулировка Фейнмана-Каца

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

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

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

${ displaystyle { begin {align} 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)}} конец {выровнено}}}$

Эти модели интеграции пути Фейнмана-Каца возникают в различных научных дисциплинах, включая вычислительную физику, биологию, теорию информации и компьютерные науки.^[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 независимые случайные величины ${ displaystyle left ( xi _ {0} ^ {i} right) _ {1 leqslant i leqslant N}}$ с общей плотностью вероятности ${ displaystyle p (x_ {0})}$. Генетический алгоритм выборочно-мутационных переходов^[1][3]

${ 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 _ {я = 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}) приблизительно _ {N uparrow infty} p (dx_ {k} | y_ {0 }, cdots, y_ {k}) приблизительно _ {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}) приблизительно _ {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 е (x_ {k}) p (x_ {k} | y_ {0}, cdots, y_ {k}) , dx_ {k} приблизительно _ {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})}$

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

${ displaystyle p (dx_ {k} | y_ {0}, cdots, y_ {k}): = p (x_ {k} | y_ {0}, cdots, y_ {k}) dx_ {k} приблизительно _ {N uparrow infty} { widehat {p}} (dx_ {k} | y_ {0}, cdots, y_ {k}) = { frac {1} {N}} sum _ { я = 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)}$

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

${ displaystyle { begin {align} int F (x_ {0}, cdots, x_ {k}) p (x_ {0}, cdots, x_ {k} | y_ {0}, cdots, y_ {k}) , dx_ {0} cdots dx_ {k} & приблизительно _ {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 {align}}}$

(Уравнение 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 {align} 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} & приблизительно _ {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 {align}}}$

Фильтры частиц можно интерпретировать по-разному. С вероятностной точки зрения они совпадают с частица среднего поля интерпретация уравнения нелинейной фильтрации. Переходы обновления-прогнозирования эволюции оптимального фильтра также можно интерпретировать как переходы классических генетических типов отборов-мутаций индивидуумов. Метод последовательной повторной выборки по важности обеспечивает другую интерпретацию переходов фильтрации, связывающих выборку по важности с этапом начальной повторной выборки. Наконец, что не менее важно, фильтры для частиц можно рассматривать как методологию приемки-отказа, снабженную механизмом рециркуляции.^[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}}$

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

для любой ограниченной функции ${ displaystyle f}$. Далее предполагаем, что построили последовательность частиц ${ displaystyle left ( xi _ {k} ^ {i} right) _ {1 leqslant i leqslant N}}$ в каком-то звании 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}) приблизительно _ {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}) приблизительно _ {N uparrow infty} int f (x_ {k}) p (dx_ {k } | y_ {0}, cdots, y_ {k-1}) dx_ {k}}$

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

${ displaystyle p (x_ {k + 1} | y_ {0}, cdots, y_ {k}) приблизительно _ {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 я = 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}) приблизительно _ {N uparrow infty} { widehat {q}} (x_ { k + 1} | y_ {0}, cdots, y_ {k}) dx_ {k + 1} приблизительно _ {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}) приблизительно _ {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}) приблизительно _ {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})}$

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

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

Анализ сходимости сажевых фильтров был начат в 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}) приблизительно _ {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 _ {к geqslant 0} E left ( left [{ widehat {I}} _ {k} (f) -I_ {k} (f) right] ^ {2} right ) leqslant { frac {c_ {2}} {N}}}$

для любой функции ж ограничено единицей, а для некоторых конечных констант ${ displaystyle c_ {1}, c_ {2}.}$ Кроме того, для любого ${ Displaystyle х 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} }$

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

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

Эта секция может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к Сделайте это понятным для неспециалистов, не снимая технических деталей. (Июнь 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) }$

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

${ displaystyle { begin {align} { 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})) & приблизительно _ {N uparrow infty} p (d (x_ {0}, cdots, x_ {k}) | y_ {0}, cdots, y_ {k}) & приблизительно _ {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})) & приблизительно _ {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 {выровнено}}}$

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

${ displaystyle { begin {align} 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) & приблизительно _ {N uparrow infty} int F (x_ {0}, cdots, x_ {n}) p (d (x_ {0}, cdots, x_ {k}) | y_ {0}, cdots, y_ {k}) & приблизительно _ {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) & приблизительно _ {N uparrow infty } int F (x_ {0}, cdots, x_ {n}) p (d (x_ {0}, cdots, x_ {k}) | y_ {0}, cdots, y_ {k-1} ) конец {выровнено}}}$

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

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

Используем формулу продукта

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