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

Эта статья о математических алгоритмах. Информацию об устройствах для фильтрации частиц из воздуха см. в разделе Воздушный фильтр .

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

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

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

Со статистической и вероятностной точки зрения фильтры частиц можно интерпретировать как частиц среднего поля интерпретацию вероятностных мер Фейнмана-Каца . Эти методы интеграции частиц были разработаны в области молекулярной химии и вычислительной физики Теодором Э. Харрисом и Германом Каном в 1951 году, Маршаллом Н. Розенблутом и Арианной В. Розенблут в 1955 году. и совсем недавно Джеком Х. Хетерингтоном в 1984 году. В вычислительной физике эти методы интеграции частиц по траекториям типа Фейнмана-Каца также используются в квантовых методах Монте-Карло и, более конкретно, в диффузионных методах Монте-Карло . Методы взаимодействующих частиц Фейнмана-Каца также тесно связаны с генетическими алгоритмами мутационного отбора, которые в настоящее время используются в эволюционных вычислениях для решения сложных задач оптимизации.

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

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

История

Эвристические алгоритмы

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

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

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

С математической точки зрения условное распределение случайных состояний сигнала при некоторых частичных и зашумленных наблюдениях описывается вероятностью Фейнмана-Каца на случайных траекториях сигнала, взвешенной последовательностью потенциальных функций правдоподобия. Квантовые методы Монте-Карло и, более конкретно, диффузионные методы Монте-Карло также можно интерпретировать как аппроксимацию частиц генетического типа среднего поля интегралов по путям Фейнмана-Каца. Истоки квантовых методов Монте-Карло часто приписывают Энрико Ферми и Роберту Рихтмайеру, которые в 1948 году разработали интерпретацию нейтронных цепных реакций частицами среднего поля. но первый алгоритм частиц эвристического и генетического типа (также известный как методы Монте-Карло с повторной выборкой или реконфигурацией) для оценки энергий основного состояния квантовых систем (в моделях с уменьшенной матрицей) принадлежит Джеку Х. Хетерингтону в 1984 году. Можно также процитировать более ранние плодотворные работы Теодора Э. Харриса и Германа Кана по физике элементарных частиц, опубликованные в 1951 году, в которых использовались генетические методы среднего поля, но эвристические для оценки энергии передачи частиц. В молекулярной химии использование методологий генетических эвристических частиц (также известных как стратегии обрезки и обогащения) можно проследить до 1955 года, когда появилась плодотворная работа Маршалла Н. Розенблута и Арианны В. Розенблут.

Использование алгоритмов генетических частиц в современной обработке сигналов и байесовском выводе появилось совсем недавно. В январе 1993 года Генширо Китагава разработал «фильтр Монте-Карло». слегка измененная версия этой статьи появилась в 1996 году. В апреле 1993 года Гордон и др. опубликовали в своей плодотворной работе применение алгоритма генетического типа в байесовском статистическом выводе. Авторы назвали свой алгоритм «бутстрап-фильтром» и продемонстрировали, что по сравнению с другими методами фильтрации их бутстрап-алгоритм не требует каких-либо предположений об этом пространстве состояний или шуме системы. Независимо от них, Пьера Дель Мораля. и Химилькон Карвальо, Пьер Дель Мораль, Андре Монен и Жерар Салю по сажевым фильтрам, опубликованные в середине 1990-х годов. Фильтры частиц также были разработаны для обработки сигналов в начале 1989–1992 годов П. Дель Моралем, Дж. К. Нойером, Г. Ригалом и Г. Салютом в LAAS-CNRS в серии ограниченных и засекреченных исследовательских отчетов с STCAN (Service Technique des Constructions et Armes Navales), ИТ-компания DIGILOG и LAAS-CNRS (Лаборатория анализа и архитектуры систем) по проблемам обработки сигналов RADAR/SONAR и GPS.

Математические основы

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

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

Дэн Крисан, Джессика Гейнс и Терри Лайонс, а также Дэн Крисан, Пьер Дель Мораль и Терри Лайонс, примерно в конце 1990-х годов создали методы частиц ветвящегося типа с различными размерами популяций. П. Дель Мораль, А. Гионне и Л. Микло еще больше продвинулись в этом вопросе в 2000 году. Пьер Дель Мораль и Алиса Гионне. доказали первые центральные предельные теоремы в 1999 году, а Пьер Дель Мораль и Лоран Микло доказали их в 2000 году. Первые результаты равномерной сходимости, касающиеся временного параметра для фильтров твердых частиц, были получены в конце 1990-х годов Пьером Дель Моралем и Алисой Гионне. Первый тщательный анализ генеалогических древовидных сглаживателей фильтров частиц был проведен П. Дель Моралем и Л. Микло в 2001 году.

Теория методологий частиц Фейнмана-Каца и связанных с ними алгоритмов фильтрации частиц была разработана в книгах в 2000 и 2004 годах. Эти абстрактные вероятностные модели инкапсулируют алгоритмы генетического типа, фильтры частиц и бутстреп-фильтры, взаимодействующие фильтры Калмана (также известные как фильтр частиц Рао-Блэквеллизованного типа). ), методы фильтрации частиц в стиле выборки и повторной выборки по важности, включая методологии генеалогического дерева и обратные методы частиц для решения проблем фильтрации и сглаживания. Другие классы методологий фильтрации частиц включают модели на основе генеалогического дерева, модели обратных марковских частиц, адаптивные модели частиц среднего поля, модели частиц островного типа, частицы, методологии Монте-Карло, цепи Маркова, Последовательные пробоотборники Монте-Карло и последовательные методы приближенных байесовских вычислений Монте-Карло и последовательный байесовский бутстрап на основе Monte Carlo ABC.

Проблема с фильтрацией

Цель

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

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

${\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{observation}}\end{array}}$

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

Все байесовские оценки $X_{k}$ следует из задней плотности $p(x_{k}|y_{0},y_{1},...,y_{k})$. Методика фильтрации частиц обеспечивает аппроксимацию этих условных вероятностей с использованием эмпирической меры, связанной с алгоритмом частиц генетического типа. Напротив, подход Марковской цепи Монте-Карло или метод выборки по важности моделирует полную апостериорную картину. $p(x_{0},x_{1},...,x_{k}|y_{0},y_{1},...,y_{k})$.

Модель наблюдения за сигналом

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Приблизительное байесовское вычисление

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

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

для некоторой последовательности независимых случайных величин ${\mathcal {V}}_{k}$ с известными функциями плотности вероятности . Основная идея состоит в том, чтобы заметить, что

${\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)$

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

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

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

$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})}}$

где

${\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}}$

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

${\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)

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

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

Основная статья: формула Фейнмана – Каца

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

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

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

${\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}}$

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

$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)}}$

и

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

$\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 (условно) независимых случайных величин. ${\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}$ с общим (условным) распространением

$\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})$

где $\delta _{a}$ обозначает меру Дирака в данном состоянии a.

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

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

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

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

${\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})$

и

${\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}).$

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

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

Тогда ожидания относительно распределения фильтрации аппроксимируются выражением

$\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)

с

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

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

$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})$

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

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

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

${\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)

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

${\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 ) эквивалентно

${\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}}$

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

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

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

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

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

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

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

$\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}$

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

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

$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 мы используем соглашение $p(x_{0}|y_{0},\cdots ,y_{-1}):=p(x_{0})$.

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

${\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}$

в том смысле, что

$\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}$

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

${\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}$

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

$\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}$

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

$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})}}$

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

$\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})$

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

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

${\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}$

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

${\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 с использованием формул Байеса

$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})$

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

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

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

$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})$

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

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

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

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

$\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_{1},c_{2}$ связанный с асимптотическим смещением и дисперсией оценки частицы, а также с некоторой конечной константой c . Те же результаты будут достигнуты, если мы заменим одношаговый оптимальный предиктор аппроксимацией оптимального фильтра.

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

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

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

$\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}^{i}\right)$

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

${\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}}$

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

${\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 на случайных траекториях сигнала. Как показано в эволюция генеалогического дерева совпадает с интерпретацией уравнений эволюции, связанной с апостериорными плотностями сигнальных траекторий, частицами среднего поля. Более подробную информацию об этих моделях пространства путей можно найти в книгах.

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

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

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

с

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

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

${\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(y_{0},\cdots ,y_{n})\approx _{N\uparrow \infty }{\widehat {p}}(y_{0},\cdots ,y_{n})=\prod _{k=0}^{n}{\widehat {p}}(y_{k}|y_{0},\cdots ,y_{k-1})$

с

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

где $p(y_{k}|\xi _{k}^{i})$ означает плотность $p(y_{k}|x_{k})$ оценивается в $x_{k}=\xi _{k}^{i}$. Конструкция этой оценки частиц и свойство несмещенности были доказаны в статье 1996 года. Уточненные оценки дисперсии можно найти в и.

Сглаживатели обратных частиц

Используя правило Байеса, имеем формулу

$p(x_{0},\cdots ,x_{n}|y_{0},\cdots ,y_{n-1})=p(x_{n}|y_{0},\cdots ,y_{n-1})p(x_{n-1}|x_{n},y_{0},\cdots ,y_{n-1})\cdots p(x_{1}|x_{2},y_{0},y_{1})p(x_{0}|x_{1},y_{0})$

Обратите внимание, что

${\begin{aligned}p(x_{k-1}|x_{k},(y_{0},\cdots ,y_{k-1}))&\propto p(x_{k}|x_{k-1})p(x_{k-1}|(y_{0},\cdots ,y_{k-1}))\\p(x_{k-1}|(y_{0},\cdots ,y_{k-1})&\propto p(y_{k-1}|x_{k-1})p(x_{k-1}|(y_{0},\cdots ,y_{k-2})\end{aligned}}$

Это означает, что

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

Замена одношаговых оптимальных предикторов $p(x_{k-1}|(y_{0},\cdots ,y_{k-2}))dx_{k-1}$ по эмпирическим измерениям частиц

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

мы находим это

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

Мы заключаем, что

$p(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))\approx _{N\uparrow \infty }{\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))$

с приближением обратных частиц

${\begin{aligned}{\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))={\widehat {p}}(dx_{n}|(y_{0},\cdots ,y_{n-1})){\widehat {p}}(dx_{n-1}|x_{n},(y_{0},\cdots ,y_{n-1}))\cdots {\widehat {p}}(dx_{1}|x_{2},(y_{0},y_{1})){\widehat {p}}(dx_{0}|x_{1},y_{0})\end{aligned}}$

Вероятностная мера

${\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))$

- вероятность случайных путей цепи Маркова $\left(\mathbb {X} _{k,n}^{\flat }\right)_{0\leqslant k\leqslant n}$бегущий назад во времени от времени k=n до времени k=0 и развивающийся на каждом временном шаге k в пространстве состояний, связанном с популяцией частиц $\xi _{k}^{i},i=1,\cdots ,N.$

• Первоначально (в момент времени k=n) цепочка $\mathbb {X} _{n,n}^{\flat }$ выбирает случайным образом состояние с распределением

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

• От момента времени k до момента (k-1) цепочка начинается в некотором состоянии $\mathbb {X} _{k,n}^{\flat }=\xi _{k}^{i}$ для некоторых $i=1,\cdots ,N$ в момент времени k переходит в момент времени (k-1) в случайное состояние $\mathbb {X} _{k-1,n}^{\flat }$ выбрано с дискретной взвешенной вероятностью

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

В приведенной выше формуле ${\widehat {p}}(dx_{k-1}|\xi _{k}^{i},(y_{0},\cdots ,y_{k-1}))$ обозначает условное распределение ${\widehat {p}}(dx_{k-1}|x_{k},(y_{0},\cdots ,y_{k-1}))$ оценивается в $x_{k}=\xi _{k}^{i}$. В том же духе, $p(y_{k-1}|\xi _{k-1}^{j})$ и $p(\xi _{k}^{i}|\xi _{k-1}^{j})$ обозначают условные плотности $p(y_{k-1}|x_{k-1})$ и $p(x_{k}|x_{k-1})$ оценивается в $x_{k}=\xi _{k}^{i}$ и $x_{k-1}=\xi _{k-1}^{j}.$ Эти модели позволяют уменьшить интегрирование по плотностям. $p((x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))$ в терминах матричных операций над марковскими переходами описанной выше цепи. Например, для любой функции $f_{k}$ у нас есть оценки частиц

${\begin{aligned}\int p(d(x_{0},\cdots ,x_{n})&|(y_{0},\cdots ,y_{n-1}))f_{k}(x_{k})\\&\approx _{N\uparrow \infty }\int {\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))f_{k}(x_{k})\\&=\int {\widehat {p}}(dx_{n}|(y_{0},\cdots ,y_{n-1})){\widehat {p}}(dx_{n-1}|x_{n},(y_{0},\cdots ,y_{n-1}))\cdots {\widehat {p}}(dx_{k}|x_{k+1},(y_{0},\cdots ,y_{k}))f_{k}(x_{k})\\&=\underbrace {\left[{\tfrac {1}{N}},\cdots ,{\tfrac {1}{N}}\right]} _{N{\text{ times}}}\mathbb {M} _{n-1}\cdots \mathbb {M} _{k}{\begin{bmatrix}f_{k}(\xi _{k}^{1})\\\vdots \\f_{k}(\xi _{k}^{N})\end{bmatrix}}\end{aligned}}$

где

$\mathbb {M} _{k}=(\mathbb {M} _{k}(i,j))_{1\leqslant i,j\leqslant N}:\qquad \mathbb {M} _{k}(i,j)={\frac {p(\xi _{k}^{i}|\xi _{k-1}^{j})~p(y_{k-1}|\xi _{k-1}^{j})}{\sum \limits _{l=1}^{N}p(\xi _{k}^{i}|\xi _{k-1}^{l})p(y_{k-1}|\xi _{k-1}^{l})}}$

Это также показывает, что если

${\overline {F}}(x_{0},\cdots ,x_{n}):={\frac {1}{n+1}}\sum _{k=0}^{n}f_{k}(x_{k})$

затем

${\begin{aligned}\int {\overline {F}}(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))&\approx _{N\uparrow \infty }\int {\overline {F}}(x_{0},\cdots ,x_{n}){\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))\\&={\frac {1}{n+1}}\sum _{k=0}^{n}\underbrace {\left[{\tfrac {1}{N}},\cdots ,{\tfrac {1}{N}}\right]} _{N{\text{ times}}}\mathbb {M} _{n-1}\mathbb {M} _{n-2}\cdots \mathbb {M} _{k}{\begin{bmatrix}f_{k}(\xi _{k}^{1})\\\vdots \\f_{k}(\xi _{k}^{N})\end{bmatrix}}\end{aligned}}$

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

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

В этой ситуации аппроксимации функций правдоподобия частицами являются несмещенными, а относительная дисперсия контролируется формулой

$E\left({\widehat {p}}(y_{0},\cdots ,y_{n})\right)=p(y_{0},\cdots ,y_{n}),\qquad E\left(\left[{\frac {{\widehat {p}}(y_{0},\cdots ,y_{n})}{p(y_{0},\cdots ,y_{n})}}-1\right]^{2}\right)\leqslant {\frac {cn}{N}},$

для некоторой конечной константы c . Кроме того, для любого $x\geqslant 0$:

$\mathbf {P} \left(\left\vert {\frac {1}{n}}\log {{\widehat {p}}(y_{0},\cdots ,y_{n})}-{\frac {1}{n}}\log {p(y_{0},\cdots ,y_{n})}\right\vert \leqslant c_{1}{\frac {x}{N}}+c_{2}{\sqrt {\frac {x}{N}}}\right)>1-e^{-x}$

для некоторых конечных констант $c_{1},c_{2}$ связанный с асимптотическим смещением и дисперсией оценки частицы, и для некоторой конечной константы c .

Смещение и дисперсия оценок частиц, основанных на наследственных линиях генеалогических деревьев.

${\begin{aligned}I_{k}^{path}(F)&:=\int F(x_{0},\cdots ,x_{k})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\\&\approx _{N\uparrow \infty }{\widehat {I}}_{k}^{path}(F)\\&:=\int F(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}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\end{aligned}}$

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

$\left|E\left({\widehat {I}}_{k}^{path}(F)\right)-I_{k}^{path}(F)\right|\leqslant {\frac {c_{1}k}{N}},\qquad E\left(\left[{\widehat {I}}_{k}^{path}(F)-I_{k}^{path}(F)\right]^{2}\right)\leqslant {\frac {c_{2}k}{N}},$

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

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

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

${\overline {F}}(x_{0},\cdots ,x_{n}):={\frac {1}{n+1}}\sum _{0\leqslant k\leqslant n}f_{k}(x_{k})$

с

$I_{n}^{path}({\overline {F}})\approx _{N\uparrow \infty }I_{n}^{\flat ,path}({\overline {F}}):=\int {\overline {F}}(x_{0},\cdots ,x_{n}){\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))$

с функциями $f_{k}$ ограничено единицей, мы имеем

$\sup _{n\geqslant 0}{\left\vert E\left({\widehat {I}}_{n}^{\flat ,path}({\overline {F}})\right)-I_{n}^{path}({\overline {F}})\right\vert }\leqslant {\frac {c_{1}}{N}}$

и

$E\left(\left[{\widehat {I}}_{n}^{\flat ,path}(F)-I_{n}^{path}(F)\right]^{2}\right)\leqslant {\frac {c_{2}}{nN}}+{\frac {c_{3}}{N^{2}}}$

для некоторых конечных констант $c_{1},c_{2},c_{3}.$ Более уточненные оценки, включающие экспоненциально малую вероятность ошибок, разработаны в .

Последовательная повторная выборка по важности (SIR)

Фильтр Монте-Карло и бутстрап-фильтр

последовательной важности Повторная выборка (SIR) , фильтрация Монте-Карло (Китагава, 1993 г.) ), алгоритм бутстреп-фильтрации (Гордон и др., 1993 г.) ) и повторная выборка одного распределения (Bejuri WMYB et al. 2017). ), также широко применяются алгоритмы фильтрации, которые аппроксимируют плотность вероятности фильтрации $p(x_{k}|y_{0},\cdots ,y_{k})$ по взвешенному набору из N образцов

$\left\{\left(w_{k}^{(i)},x_{k}^{(i)}\right)\ :\ i\in \{1,\cdots ,N\}\right\}.$

важности Веса $w_{k}^{(i)}$ являются аппроксимациями относительных апостериорных вероятностей (или плотностей) выборок, таких что

$\sum _{i=1}^{N}w_{k}^{(i)}=1.$

Последовательная выборка по важности (SIS) — это последовательная (т. е. рекурсивная) версия выборки по важности . Как и при выборке по важности, математическое ожидание функции f можно аппроксимировать как средневзвешенное значение.

$\int f(x_{k})p(x_{k}|y_{0},\dots ,y_{k})dx_{k}\approx \sum _{i=1}^{N}w_{k}^{(i)}f(x_{k}^{(i)}).$

Для конечного набора выборок производительность алгоритма зависит от выбора распределения предложений.

$\pi (x_{k}|x_{0:k-1},y_{0:k})\,$.

« Оптимальное» распределение предложений задается как целевое распределение.

$\pi (x_{k}|x_{0:k-1},y_{0:k})=p(x_{k}|x_{k-1},y_{k})={\frac {p(y_{k}|x_{k})}{\int p(y_{k}|x_{k})p(x_{k}|x_{k-1})dx_{k}}}~p(x_{k}|x_{k-1}).$

Этот конкретный выбор предложения перехода был предложен П. Дель Моралем в 1996 и 1998 годах. Когда сложно отбирать переходы по распределению $p(x_{k}|x_{k-1},y_{k})$ одна естественная стратегия - использовать следующее приближение частиц

${\begin{aligned}{\frac {p(y_{k}|x_{k})}{\int p(y_{k}|x_{k})p(x_{k}|x_{k-1})dx_{k}}}p(x_{k}|x_{k-1})dx_{k}&\simeq _{N\uparrow \infty }{\frac {p(y_{k}|x_{k})}{\int p(y_{k}|x_{k}){\widehat {p}}(dx_{k}|x_{k-1})}}{\widehat {p}}(dx_{k}|x_{k-1})\\&=\sum _{i=1}^{N}{\frac {p(y_{k}|X_{k}^{i}(x_{k-1}))}{\sum _{j=1}^{N}p(y_{k}|X_{k}^{j}(x_{k-1}))}}\delta _{X_{k}^{i}(x_{k-1})}(dx_{k})\end{aligned}}$

с эмпирическим приближением

${\widehat {p}}(dx_{k}|x_{k-1})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{X_{k}^{i}(x_{k-1})}(dx_{k})~\simeq _{N\uparrow \infty }p(x_{k}|x_{k-1})dx_{k}$

связанный с N (или любым другим большим количеством выборок) независимыми случайными выборками $X_{k}^{i}(x_{k-1}),i=1,\cdots ,N$с условным распределением случайного состояния $X_{k}$ данный $X_{k-1}=x_{k-1}$. Согласованность результирующего фильтра частиц этого приближения и других расширений развита в . На приведенном выше дисплее $\delta _{a}$ обозначает меру Дирака в данном состоянии a.

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

$\pi (x_{k}|x_{0:k-1},y_{0:k})=p(x_{k}|x_{k-1}).$

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

Повторная выборка используется, чтобы избежать проблемы вырождения алгоритма, то есть избежать ситуации, когда все веса важности, кроме одного, близки к нулю. На производительность алгоритма также может повлиять правильный выбор метода повторной выборки. Стратифицированная выборка, предложенная Китагавой (1993 г.). ) является оптимальным с точки зрения дисперсии.

Один шаг последовательной повторной выборки по важности выглядит следующим образом:

1) Для $i=1,\cdots ,N$ взять образцы из распределения предложений

$x_{k}^{(i)}\sim \pi (x_{k}|x_{0:k-1}^{(i)},y_{0:k})$

2) Для $i=1,\cdots ,N$ обновите веса важности до нормализующей константы:

${\hat {w}}_{k}^{(i)}=w_{k-1}^{(i)}{\frac {p(y_{k}|x_{k}^{(i)})p(x_{k}^{(i)}|x_{k-1}^{(i)})}{\pi (x_{k}^{(i)}|x_{0:k-1}^{(i)},y_{0:k})}}.$

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

$\pi (x_{k}^{(i)}|x_{0:k-1}^{(i)},y_{0:k})=p(x_{k}^{(i)}|x_{k-1}^{(i)}),$

это упрощается до следующего:

${\hat {w}}_{k}^{(i)}=w_{k-1}^{(i)}p(y_{k}|x_{k}^{(i)}),$

3) Для $i=1,\cdots ,N$ вычислите нормализованные веса важности:

$w_{k}^{(i)}={\frac {{\hat {w}}_{k}^{(i)}}{\sum _{j=1}^{N}{\hat {w}}_{k}^{(j)}}}$

4) Рассчитайте оценку эффективного числа частиц как

${\hat {N}}_{\mathit {eff}}={\frac {1}{\sum _{i=1}^{N}\left(w_{k}^{(i)}\right)^{2}}}$

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

5) Если эффективное число частиц меньше заданного порога ${\hat {N}}_{\mathit {eff}}<N_{thr}$, затем выполните повторную выборку:

а) Нарисуйте N частиц из текущего набора частиц с вероятностями, пропорциональными их весам. Замените текущий набор частиц новым.

б) Для $i=1,\cdots ,N$ набор $w_{k}^{(i)}=1/N.$

Термин «повторная выборка по важности» также иногда используется при упоминании фильтров SIR, но термин « повторная выборка по важности » более точен, поскольку слово «повторная выборка» подразумевает, что первоначальная выборка уже была выполнена.

Последовательная выборка по важности (SIS)

• То же, что и последовательная повторная выборка по важности, но без этапа повторной выборки.

Алгоритм «Прямая версия»

Алгоритм «прямой версии» довольно прост (по сравнению с другими алгоритмами фильтрации частиц) и использует композицию и отклонение. Чтобы сгенерировать одну выборку x в k из $p_{x_{k}|y_{1:k}}(x|y_{1:k})$:

1) Установите n = 0 (это будет подсчитывать количество сгенерированных частиц)

2) Равномерно выберите индекс i из диапазона $\{1,...,N\}$

3) Создать тест ${\hat {x}}$ из распределения $p(x_{k}|x_{k-1})$ с $x_{k-1}=x_{k-1|k-1}^{(i)}$

4) Сгенерировать вероятность ${\hat {y}}$ с использованием ${\hat {x}}$ от $p(y_{k}|x_{k}),~{\mbox{with}}~x_{k}={\hat {x}}$ где $y_{k}$ измеренное значение

5) Создайте еще одну униформу u из $[0,m_{k}]$ где $m_{k}=\sup _{x_{k}}p(y_{k}|x_{k})$

6) Сравните себя и $p\left({\hat {y}}\right)$

6a) Если u больше, повторите с шага 2.

6б) Если ты меньше, то сохрани ${\hat {x}}$ как $x_{k|k}^{(i)}$ и увеличить n

7) Если n == N, то выходим

Цель состоит в том, чтобы сгенерировать P «частиц» в точке k, используя только частицы из $k-1$. Для этого необходимо, чтобы уравнение Маркова могло быть записано (и вычислено) для получения $x_{k}$ основанный только на $x_{k-1}$. Этот алгоритм использует состав частиц P из $k-1$ для генерации частицы в точке k не будет создано P частиц и повторяет действия (шаги 2–6) до тех пор, пока в точке k .

Это легче представить, если рассматривать x как двумерный массив. Одно измерение — это k , а другое — количество частиц. Например, $x(k,i)$ было бы я ^й частица в $k$ а также можно написать $x_{k}^{(i)}$ (как это сделано выше в алгоритме). Шаг 3 создает потенциал $x_{k}$ на основе случайно выбранной частицы ( $x_{k-1}^{(i)}$) во время $k-1$ и отвергает или принимает его на шаге 6. Другими словами, $x_{k}$ значения генерируются с использованием ранее сгенерированных $x_{k-1}$.

Приложения

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

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

Другие фильтры твердых частиц

• Дополнительный сажевый фильтр
• Справочная стоимость фильтра твердых частиц
• Экспоненциальный фильтр естественных частиц
• Методологии Фейнмана-Каца и частиц среднего поля
• Гауссов фильтр частиц
• Фильтр частиц Гаусса – Эрмита
• Иерархический/масштабируемый фильтр частиц
• Подталкиваемый сажевый фильтр
• Частица Маркова-Цепи Монте-Карло, см., например, псевдомаргинальный алгоритм Метрополиса – Гастингса .
• Фильтр твердых частиц Рао – Блэквеллизованный
• Регуляризированный вспомогательный сажевый фильтр
• отбора проб Оптимальный фильтр частиц на основе
• Фильтр твердых частиц без запаха

См. также

• Ансамбль фильтра Калмана
• Обобщенная фильтрация
• Генетический алгоритм
• Методы частиц среднего поля
• Локализация Монте-Карло
• Оценка движущегося горизонта
• Рекурсивная байесовская оценка

Библиография

• Дель Мораль, Пьер (1996). «Нелинейная фильтрация: решение взаимодействующих частиц» (PDF) . Марковские процессы и связанные с ними области . 2 (4): 555–580. Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 31 мая 2015 г.
• Дель Мораль, Пьер (2004). Формулы Фейнмана-Каца. Генеалогические приближения и взаимодействующие частицы . Спрингер. п. 575. «Серия: Вероятность и приложения».
• Дель Мораль, Пьер (2013). Моделирование среднего поля для интегрирования Монте-Карло . Чепмен и Холл/CRC Press. п. 626. «Монографии по статистике и прикладной теории вероятности».
• Каппе, О.; Мулен, Э.; Райден, Т. (2005). Вывод в скрытых марковских моделях . Спрингер.
• Лю, Дж. С.; Чен, Р. (1998). «Последовательные методы Монте-Карло для динамических систем» (PDF) . Журнал Американской статистической ассоциации . 93 (443): 1032–1044. дои : 10.1080/01621459.1998.10473765 .
• Лю, Дж. С. (2001). Стратегии Монте-Карло в научных вычислениях . Спрингер.
• Конг, А.; Лю, Дж. С.; Вонг, WH (1994). «Последовательные вменения и байесовские проблемы с недостающими данными» (PDF) . Журнал Американской статистической ассоциации . 89 (425): 278–288. дои : 10.1080/01621459.1994.10476469 .
• Лю, Дж. С.; Чен, Р. (1995). «Слепая деконволюция посредством последовательных вменений» (PDF) . Журнал Американской статистической ассоциации . 90 (430): 567–576. дои : 10.2307/2291068 . JSTOR   2291068 .
• Ристич, Б.; Арулампалам, С.; Гордон, Н. (2004). За пределами фильтра Калмана: фильтры частиц для приложений слежения . Артех Хаус.
• Дусе, А.; Йохансен, AM (декабрь 2008 г.). «Урок по фильтрации и сглаживанию частиц: пятнадцать лет спустя» (PDF) . Технический отчет .
• Дусе, А.; Годсилл, С.; Андрие, К. (2000). «О последовательных методах выборки Монте-Карло для байесовской фильтрации». Статистика и вычисления . 10 (3): 197–208. дои : 10.1023/A:1008935410038 . S2CID   16288401 .
• Арулампалам, MS; Маскелл, С.; Гордон, Н.; Клапп, Т. (2002). «Учебное пособие по фильтрам частиц для онлайн-нелинейного/негауссовского байесовского отслеживания». Транзакции IEEE по обработке сигналов . 50 (2): 174–188. Бибкод : 2002ITSP...50..174A . CiteSeerX   10.1.1.471.8617 . дои : 10.1109/78.978374 . S2CID   55577025 .
• Каппе, О.; Годсилл, С.; Мулен, Э. (2007). «Обзор существующих методов и последних достижений в последовательном Монте-Карло». Труды IEEE . 95 (5): 899–924. дои : 10.1109/JPROC.2007.893250 . S2CID   3081664 .
• Китагава, Г. (1996). «Фильтр Монте-Карло и сглаживатель для негауссовских нелинейных моделей в пространстве состояний». Журнал вычислительной и графической статистики . 5 (1): 1–25. дои : 10.2307/1390750 . JSTOR   1390750 .
• Котеча, Дж. Х.; Джурик, П. (2003). «Фильтрация гауссовских частиц». Транзакции IEEE по обработке сигналов . 51 (10).
• Хауг, Эй Джей (2005). «Учебное пособие по методам байесовской оценки и отслеживания, применимым к нелинейным и негауссовским процессам» (PDF) . Корпорация MITRE, США, Tech. Республика, февраль . Архивировано (PDF) из оригинала 22 декабря 2021 г. Проверено 22 декабря 2021 г.
• Питт, МК; Шепард, Н. (1999). «Фильтрация посредством моделирования: вспомогательные фильтры частиц» . Журнал Американской статистической ассоциации . 94 (446): 590–591. дои : 10.2307/2670179 . JSTOR   2670179 . Архивировано из оригинала 16 октября 2007 г. Проверено 6 мая 2008 г.
• Гордон, Нью-Джерси; Салмонд, диджей; Смит, AFM (1993). «Новый подход к оценке нелинейного/негауссовского байесовского состояния». Труды IEE F-радар и обработка сигналов . 140 (2): 107–113. дои : 10.1049/ip-f-2.1993.0015 .
• Чен, З. (2003). «Байесовская фильтрация: от фильтров Калмана к фильтрам частиц и не только». CiteSeerX   10.1.1.107.7415 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
• Васвани, Н. ; Рати, Ю.; Йеззи, А.; Танненбаум, А. (2007). «Отслеживание деформирующихся объектов с помощью фильтрации частиц по геометрическим активным контурам» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 29 (8): 1470–1475. дои : 10.1109/tpami.2007.1081 . ПМК   3663080 . ПМИД   17568149 .

Внешние ссылки

• Модели Фейнмана – Каца и алгоритмы взаимодействующих частиц (также известные как фильтрация частиц) Теоретические аспекты и список областей применения фильтров частиц
• Домашняя страница последовательных методов Монте-Карло (фильтрация частиц) в Кембриджском университете
• Анимация MCL Дитера Фокса
• Бесплатное программное обеспечение Роба Хесса
• SMCTC: класс шаблона для реализации алгоритмов SMC на C++.
• Java-апплет по фильтрации частиц
• vSMC: векторизованный последовательный Монте-Карло
• Фильтр твердых частиц объясняется в контексте беспилотного автомобиля