Сажевый фильтр

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

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

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

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

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

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

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

СОДЕРЖАНИЕ

  • 1 История
    • 1.1 Эвристические подобные алгоритмы
    • 1.2 Математические основы
  • 2 Проблема фильтрации
    • 2.1 Цель
    • 2.2 Модель наблюдения за сигналом
    • 2.3 Приближенные байесовские модели вычислений
    • 2.4 Уравнение нелинейной фильтрации
    • 2.5 Формулировка Фейнмана-Каца
  • 3 сажевых фильтра
    • 3.1 Алгоритм частиц генетического типа
    • 3.2 Принципы Монте-Карло
    • 3.3 Моделирование среднего поля частиц
      • 3.3.1 Общий вероятностный принцип
      • 3.3.2 Частичная интерпретация уравнения фильтрации
    • 3.4 Некоторые результаты сходимости
  • 4 Генеалогические деревья и свойства непредвзятости
    • 4.1 Сглаживание частиц на основе генеалогического дерева
    • 4.2 Несмещенные частичные оценки функций правдоподобия
    • 4.3 Обратные сглаживания частиц
    • 4.4 Некоторые результаты сходимости
  • 5 Последовательная передискретизация по важности (SIR)
    • 5.1 Фильтр Монте-Карло и бутстрап-фильтр
    • 5.2 Последовательная выборка по важности (SIS)
    • 5.3 Алгоритм «Прямая версия»
  • 6 Другие фильтры для твердых частиц
  • 7 См. Также
  • 8 ссылки
  • 9 Библиография
  • 10 Внешние ссылки

История

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

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

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

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

С математической точки зрения условное распределение случайных состояний сигнала при некоторых частичных и зашумленных наблюдениях описывается вероятностью Фейнмана-Каца на случайных траекториях сигнала, взвешенных последовательностью потенциальных функций правдоподобия. Квантовый Монте-Карло и, более конкретно, диффузионные методы Монте-Карло также можно интерпретировать как приближение интегралов по путям Фейнмана-Каца частицами генетического типа среднего поля. Истоки методов квантового Монте-Карло часто приписывают Энрико Ферми и Роберту Рихтмайеру, которые в 1948 году разработали интерпретацию цепных нейтронных реакций частицами среднего поля, но первый алгоритм частиц, подобный эвристическому и генетическому (также известный как Resampled или Reconfiguration Monte Carlo методов) для оценки энергий основного состояния квантовых систем (в моделях редуцированных матриц) принадлежит Джеку Х. Хетерингтону в 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 году. Статья также содержит доказательство несмещенных свойств приближения частицами функций правдоподобия и ненормализованных условных вероятностных мер. Несмещенная оценка частиц функций правдоподобия, представленная в этой статье, сегодня используется в байесовских статистических выводах.

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

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

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

Цель

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

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

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

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

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

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

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

  • Икс 0 , Икс 1 , {\ Displaystyle X_ {0}, X_ {1}, \ cdots}- это марковский процесс на (для некоторых), который развивается согласно плотности вероятности перехода. Эта модель также часто записывается синтетическим способом как р d Икс {\ Displaystyle \ mathbb {R} ^ {d_ {x}}} d Икс 1 {\ displaystyle d_ {x} \ geqslant 1} п ( Икс k | Икс k - 1 ) {\ displaystyle p (x_ {k} | x_ {k-1})}
    Икс k | Икс k - 1 знак равно Икс k п ( Икс k | Икс k - 1 ) {\ Displaystyle X_ {k} | X_ {k-1} = x_ {k} \ sim p (x_ {k} | x_ {k-1})}
с начальной плотностью вероятности. п ( Икс 0 ) {\ displaystyle p (x_ {0})}
  • Наблюдения принимают значения в некотором пространстве состояний (для некоторых) и являются условно независимыми при условии, что они известны. Другими словами, каждый зависит только от. Кроме того, мы предполагаем, что условное распределение для данного абсолютно непрерывно, и синтетическим путем имеем Y 0 , Y 1 , {\ Displaystyle Y_ {0}, Y_ {1}, \ cdots} р d у {\ displaystyle \ mathbb {R} ^ {d_ {y}}} d у 1 {\ displaystyle d_ {y} \ geqslant 1} Икс 0 , Икс 1 , {\ Displaystyle X_ {0}, X_ {1}, \ cdots} Y k {\ displaystyle Y_ {k}} Икс k {\ displaystyle X_ {k}} Y k {\ displaystyle Y_ {k}} Икс k знак равно Икс k {\ Displaystyle X_ {k} = x_ {k}}
    Y k | Икс k знак равно у k п ( у k | Икс k ) {\ Displaystyle Y_ {k} | X_ {k} = y_ {k} \ sim p (y_ {k} | x_ {k})}

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

Икс k знак равно грамм ( Икс k - 1 ) + W k - 1 {\ Displaystyle X_ {к} = г (X_ {k-1}) + W_ {k-1}}
Y k знак равно час ( Икс k ) + V k {\ Displaystyle Y_ {k} = h (X_ {k}) + V_ {k}}

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

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

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

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

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

Y k знак равно Y k + ϵ V k для какого-то параметра ϵ [ 0 , 1 ] {\ displaystyle {\ mathcal {Y}} _ {k} = Y_ {k} + \ epsilon {\ mathcal {V}} _ {k} \ quad {\ t_dv {для некоторого параметра}} \ quad \ epsilon \ in [0,1]}

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

Закон ( Икс k | Y 0 знак равно у 0 , , Y k знак равно у k ) ϵ 0 Закон ( Икс k | Y 0 знак равно у 0 , , Y k знак равно у k ) {\ 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)}

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

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

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

п ( Икс 0 , , Икс k | у 0 , , у k ) знак равно п ( у 0 , , у k | Икс 0 , , Икс k ) п ( Икс 0 , , Икс k ) п ( у 0 , , у k ) {\ Displaystyle p (x_ {0}, \ cdots, x_ {k} | y_ {0}, \ cdots, y_ {k}) = {\ frac {p (y_ {0}, \ cdots, y_ {k}) | x_ {0}, \ cdots, x_ {k}) p (x_ {0}, \ cdots, x_ {k})} {p (y_ {0}, \ cdots, y_ {k})}}}

где

п ( у 0 , , у k ) знак равно п ( у 0 , , у k | Икс 0 , , Икс k ) п ( Икс 0 , , Икс k ) d Икс 0 d Икс k п ( у 0 , , у k | Икс 0 , , Икс k ) знак равно л знак равно 0 k п ( у л | Икс л ) п ( Икс 0 , , Икс k ) знак равно п 0 ( Икс 0 ) л знак равно 1 k п ( Икс л | Икс л - 1 ) {\ Displaystyle {\ begin {align} p (y_ {0}, \ cdots, y_ {k}) amp; = \ 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}) amp; = \ prod _ {l = 0} ^ {k} p (y_ {l} | x_ {l}) \\ p (x_ {0}, \ cdots, x_ {k}) amp; = p_ {0} (x_ {0}) \ prod _ {l = 1} ^ {k} p (x_ {l} | x_ {l-1}) \ end {align}}}

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

п ( Икс k | у 0 , , у k - 1 ) обновление п ( Икс k | у 0 , , у k ) знак равно п ( у k | Икс k ) п ( Икс k | у 0 , , у k - 1 ) п ( у k | Икс k ) п ( Икс k | у 0 , , у k - 1 ) d Икс k прогноз п ( Икс k + 1 | у 0 , , у k ) знак равно п ( Икс k + 1 | Икс k ) п ( Икс k | у 0 , , у k ) d Икс k {\ displaystyle {\ begin {align} p (x_ {k} | y_ {0}, \ cdots, y_ {k-1}) amp; {\ 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}}} \\ amp; {\ 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)

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

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

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

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

грамм k ( Икс k ) знак равно п ( у k | Икс k ) . {\ displaystyle G_ {k} (x_ {k}) = p (y_ {k} | x_ {k}).}

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

F ( Икс 0 , , Икс п ) п ( Икс 0 , , Икс п | у 0 , , у п ) d Икс 0 d Икс п знак равно F ( Икс 0 , , Икс п ) { k знак равно 0 п п ( у k | Икс k ) } п ( Икс 0 , , Икс п ) d Икс 0 d Икс п { k знак равно 0 п п ( у k | Икс k ) } п ( Икс 0 , , Икс п ) d Икс 0 d Икс п знак равно E ( F ( Икс 0 , , Икс п ) k знак равно 0 п грамм k ( Икс k ) ) E ( k знак равно 0 п грамм k ( Икс 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} amp; = {\ 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}}} \\ amp; = {\ 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)}} \ конец {выровнено}}}

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

E ( F ( Икс 0 , , Икс п ) | Икс 0 А , , Икс п А ) знак равно E ( F ( Икс 0 , , Икс п ) k знак равно 0 п грамм k ( Икс k ) ) E ( k знак равно 0 п грамм k ( Икс k ) ) {\ 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)}}}

а также

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

ξ k знак равно ( ξ k я ) 1 я N отбор ξ ^ k знак равно ( ξ ^ k я ) 1 я N мутация ξ k + 1 знак равно ( ξ k + 1 я ) 1 я N {\ 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 (условно) независимых случайных величин с общим (условным) распределением ξ ^ k знак равно ( ξ ^ k я ) 1 я N {\ displaystyle {\ widehat {\ xi}} _ {k}: = \ left ({\ widehat {\ xi}} _ {k} ^ {i} \ right) _ {1 \ leqslant i \ leqslant N}}
я знак равно 1 N п ( у k | ξ k я ) j знак равно 1 N п ( у k | ξ k j ) δ ξ k я ( d Икс k ) {\ 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})}

где - мера Дирака в данном состоянии a. δ а {\ displaystyle \ delta _ {a}}

  • Во время перехода предсказание мутации из каждой выбранной частицы мы независимо отбираем переход ξ ^ k я {\ displaystyle {\ widehat {\ xi}} _ {k} ^ {i}}
ξ ^ k я ξ k + 1 я п ( Икс k + 1 | ξ ^ k я ) , я знак равно 1 , , N . {\ displaystyle {\ widehat {\ xi}} _ {k} ^ {i} \ longrightarrow \ xi _ {k + 1} ^ {i} \ sim p (x_ {k + 1} | {\ widehat {\ xi) }} _ {k} ^ {i}), \ qquad i = 1, \ cdots, N.}

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

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

п ^ ( d Икс k | у 0 , , у k ) знак равно 1 N я знак равно 1 N δ ξ ^ k я ( d Икс k ) N п ( d Икс k | у 0 , , у k ) N я знак равно 1 N п ( у k | ξ k я ) я знак равно 1 N п ( у k | ξ k j ) δ ξ k я ( d Икс 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})}

а также

п ^ ( d Икс k | у 0 , , у k - 1 ) знак равно 1 N я знак равно 1 N δ ξ k я ( d Икс k ) N п ( d Икс k | у 0 , , у 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})}

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

Принципы Монте-Карло

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

п ( Икс k | у 0 , , у k ) . {\ displaystyle p (x_ {k} | y_ {0}, \ cdots, y_ {k}).}

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

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

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

ж ( Икс k ) п ( Икс k | у 0 , , у k ) d Икс k N 1 N я знак равно 1 N ж ( ξ ^ k я ) знак равно ж ( Икс k ) п ^ ( d Икс k | у 0 , , у k ) {\ 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)

с участием

п ^ ( d Икс k | у 0 , , у k ) знак равно 1 N я знак равно 1 N δ ξ ^ k я ( d Икс 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})}

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

п ( d Икс k | у 0 , , у k ) знак равно п ( Икс k | у 0 , , у k ) d Икс k N п ^ ( d Икс k | у 0 , , у k ) знак равно 1 N я знак равно 1 N δ ξ ^ k я ( d Икс k ) {\ 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})}

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

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

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

F ( Икс 0 , , Икс k ) п ( Икс 0 , , Икс k | у 0 , , у k ) d Икс 0 d Икс k N 1 N я знак равно 1 N F ( ξ ^ 0 , k я , ξ ^ 1 , k я , , ξ ^ k , k я ) знак равно F ( Икс 0 , , Икс k ) п ^ ( d ( Икс 0 , , Икс k ) | у 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} amp; \ приблизительно _ {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) \\ amp; = \ int F (x_ {0}, \ cdots, x_ {k}) {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) \ end {align}}}

 

 

 

 

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

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

п ^ ( d ( Икс 0 , , Икс k ) | у 0 , , у k ) знак равно 1 N я знак равно 1 N δ ( ξ ^ 0 , k я , ξ ^ 1 , k я , , ξ ^ k , k я ) ( d ( Икс 0 , , Икс k ) ) {\ 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) эквивалентно

п ( d ( Икс 0 , , Икс k ) | у 0 , , у k ) знак равно п ( Икс 0 , , Икс k | у 0 , , у k ) d Икс 0 d Икс k N п ^ ( d ( Икс 0 , , Икс k ) | у 0 , , у k ) знак равно 1 N я знак равно 1 N δ ( ξ ^ 0 , k я , , ξ ^ k , k я ) ( d ( Икс 0 , , Икс k ) ) {\ displaystyle {\ begin {align} p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) amp;: = p (x_ {0}, \ cdots, x_ {k} | y_ {0}, \ cdots, y_ {k}) \, dx_ {0} \ cdots dx_ {k} \\ amp; \ приблизительно _ {N \ uparrow \ infty} {\ widehat { p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) \\ amp;: = {\ 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}}}

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

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

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

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

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

1 N я знак равно 1 N δ ξ п я ( d Икс п ) N η п ( d Икс п ) {\ displaystyle {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ delta _ {\ xi _ {n} ^ {i}} (dx_ {n}) \ приблизительно _ { N \ uparrow \ infty} \ eta _ {n} (dx_ {n})}

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

Φ п + 1 ( 1 N я знак равно 1 N δ ξ п я ) N Φ п + 1 ( η п ) знак равно η п + 1 {\ 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}}

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

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

п ( Икс k | у 0 , , у k - 1 ) d Икс k п ( Икс k + 1 | у 0 , , у k ) знак равно п ( Икс k + 1 | Икс k ) п ( у k | Икс k ) п ( Икс k | у 0 , , у k - 1 ) d Икс k п ( у k | Икс k ) п ( Икс k | у 0 , , у k - 1 ) d Икс k {\ 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 мы используем соглашение. п ( Икс 0 | у 0 , , у - 1 ) знак равно п ( Икс 0 ) {\ displaystyle p (x_ {0} | y_ {0}, \ cdots, y _ {- 1}): = p (x_ {0})}

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

п ^ ( d Икс 0 ) знак равно 1 N я знак равно 1 N δ ξ 0 я ( d Икс 0 ) N п ( Икс 0 ) d Икс 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}}

в смысле

ж ( Икс 0 ) п ^ ( d Икс 0 ) знак равно 1 N я знак равно 1 N ж ( ξ 0 я ) N ж ( Икс 0 ) п ( d Икс 0 ) d Икс 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}}

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

п ^ ( d Икс k | у 0 , , у k - 1 ) знак равно 1 N я знак равно 1 N δ ξ k я ( d Икс k ) N   п ( Икс k   |   у 0 , , у k - 1 ) d Икс 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}

ж ( Икс k ) п ^ ( d Икс k | у 0 , , у k - 1 ) знак равно 1 N я знак равно 1 N ж ( ξ k я ) N ж ( Икс k ) п ( d Икс k | у 0 , , у k - 1 ) d Икс k {\ 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}}

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

п ( Икс k + 1 | у 0 , , у k ) N п ( Икс k + 1 | Икс k ) п ( у k | Икс k ) п ^ ( d Икс k | у 0 , , у k - 1 ) п ( у k | Икс k ) п ^ ( d Икс k | у 0 , , у k - 1 ) {\ 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}) }}}

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

п ( Икс k + 1 | Икс k ) п ( у k | Икс k ) п ^ ( d Икс k | у 0 , , у k - 1 ) п ( у k | Икс k ) п ^ ( d Икс k | у 0 , , у k - 1 ) знак равно я знак равно 1 N п ( у k | ξ k я ) я знак равно 1 N п ( у k | ξ k j ) п ( Икс k + 1 | ξ k я ) знак равно q ^ ( Икс k + 1 | у 0 , , у k ) {\ 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})}

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

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

п ^ ( d Икс k + 1 | у 0 , , у k ) знак равно 1 N я знак равно 1 N δ ξ k + 1 я ( d Икс k + 1 ) N q ^ ( Икс k + 1 | у 0 , , у k ) d Икс k + 1 N п ( Икс k + 1 | у 0 , , у k ) d Икс k + 1 {\ 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}}

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

п ^ ( d Икс k | у 0 , , у k - 1 ) знак равно 1 N я знак равно 1 N δ ξ k я ( d Икс k ) N п ( d Икс k | у 0 , , у k - 1 ) знак равно п ( Икс k | у 0 , , у k - 1 ) d Икс 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}): = p (x_ {k} | y_ {0}, \ cdots, y_ {k-1}) dx_ {k}}

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

п ( d Икс k | у 0 , , у k ) N п ( у k | Икс k ) п ^ ( d Икс k | у 0 , , у k - 1 ) п ( у k | Икс k ) п ^ ( d Икс k | у 0 , , у k - 1 ) знак равно я знак равно 1 N п ( у k | ξ k я ) j знак равно 1 N п ( у k | ξ k j )   δ ξ k я ( d Икс 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})}

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

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

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

я k ( ж ) знак равно ж ( Икс k ) п ( d Икс k | у 0 , , у k - 1 ) N я ^ k ( ж ) знак равно ж ( Икс k ) п ^ ( d Икс k | у 0 , , у k - 1 ) {\ 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})}

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

Как дела k 0 | E ( я ^ k ( ж ) ) - я k ( ж ) | c 1 N {\ displaystyle \ sup _ {k \ geqslant 0} \ left \ vert E \ left ({\ widehat {I}} _ {k} (f) \ right) -I_ {k} (f) \ right \ vert \ leqslant {\ frac {c_ {1}} {N}}}
Как дела k 0 E ( [ я ^ k ( ж ) - я k ( ж ) ] 2 ) c 2 N {\ Displaystyle \ sup _ {к \ geqslant 0} E \ left (\ left [{\ widehat {I}} _ {k} (f) -I_ {k} (f) \ right] ^ {2} \ right) \ leqslant {\ frac {c_ {2}} {N}}}

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

п ( | я ^ k ( ж ) - я k ( ж ) | c 1 Икс N + c 2 Икс N Как дела 0 k п | я ^ k ( ж ) - я k ( ж ) | c Икс бревно ( п ) N ) gt; 1 - е - Икс {\ 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)gt; 1-e ^ {- x} }

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

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

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

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

( ξ ^ 0 , k я , ξ ^ 1 , k я , , ξ ^ k - 1 , k я , ξ ^ k , k я ) , ( ξ 0 , k я , ξ 1 , k я , , ξ k - 1 , k я , ξ k , 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), \ quad \ left (\ xi _ {0, k} ^ {i}, \ xi _ {1, k} ^ {i}, \ cdots, \ xi _ {k-1, k} ^ {i}, \ xi _ {k, k} \ right) }

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

п ^ ( d ( Икс 0 , , Икс k ) | у 0 , , у k ) знак равно 1 N я знак равно 1 N δ ( ξ ^ 0 , k я , , ξ ^ 0 , k я ) ( d ( Икс 0 , , Икс k ) ) N п ( d ( Икс 0 , , Икс k ) | у 0 , , у k ) N я знак равно 1 N п ( у k | ξ k , k я ) j знак равно 1 N п ( у k | ξ k , k j ) δ ( ξ 0 , k я , , ξ 0 , k я ) ( d ( Икс 0 , , Икс k ) )   п ^ ( d ( Икс 0 , , Икс k ) | у 0 , , у k - 1 ) знак равно 1 N я знак равно 1 N δ ( ξ 0 , k я , , ξ k , k я ) ( d ( Икс 0 , , Икс k ) ) N п ( d ( Икс 0 , , Икс k ) | у 0 , , у k - 1 ) знак равно п ( Икс 0 , , Икс k | у 0 , , у k - 1 ) d Икс 0 , , d Икс k {\ displaystyle {\ begin {align} {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) amp;: = { \ 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})) \\ amp; \ приблизительно _ {N \ uparrow \ infty} p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) \\ amp; \ приблизительно _ {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})) \\ amp; \ \\ {\ widehat {p}} (d (x_ {0}, \ cdots, x_ { k}) | y_ {0}, \ cdots, y_ {k-1}) amp;: = {\ 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})) \\ amp; \ приблизительно _ {N \ uparrow \ infty} p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1}) \\ amp;: = p (x_ {0}, \ cdots, x_ {k} | y_ {0}, \ cdots, y_ {k-1}) dx_ {0}, \ cdots, dx_ {k} \ end {выровнено}}}

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

F ( Икс 0 , , Икс п ) п ^ ( d ( Икс 0 , , Икс k ) | у 0 , , у k ) знак равно 1 N я знак равно 1 N F ( ξ ^ 0 , k я , , ξ ^ 0 , k я ) N F ( Икс 0 , , Икс п ) п ( d ( Икс 0 , , Икс k ) | у 0 , , у k ) N я знак равно 1 N п ( у k | ξ k , k я ) j знак равно 1 N п ( у k | ξ k , k j ) F ( ξ 0 , k я , , ξ k , k я )   F ( Икс 0 , , Икс п ) п ^ ( d ( Икс 0 , , Икс k ) | у 0 , , у k - 1 ) знак равно 1 N я знак равно 1 N F ( ξ 0 , k я , , ξ k , k я ) N F ( Икс 0 , , Икс п ) п ( d ( Икс 0 , , Икс k ) | у 0 , , у k - 1 ) {\ displaystyle {\ begin {align} \ int F (x_ {0}, \ cdots, x_ {n}) {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) amp;: = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} F \ left ({\ widehat {\ xi}} _ {0, k} ^ {i}, \ cdots, {\ widehat {\ xi}} _ {0, k} ^ {i} \ right) \\ amp; \ приблизительно _ {N \ uparrow \ infty} \ int F (x_ {0}, \ cdots, x_ {n}) p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k}) \\ amp; \ приблизительно _ {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) \\ amp; \ \\\ int F (x_ {0}, \ cdots, x_ {n}) {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1}) amp;: = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} F \ left (\ xi _ {0, k} ^ {i}, \ cdots, \ xi _ {k, k} ^ {i} \ right) \\ amp; \ приблизительно _ {N \ uparrow \ infty } \ int F (x_ {0}, \ cdots, x_ {n}) p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1}) \ конец {выровнено}}}

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

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

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

п ( у 0 , , у п ) знак равно k знак равно 0 п п ( у k | у 0 , , у k - 1 ) {\ displaystyle p (y_ {0}, \ cdots, y_ {n}) = \ prod _ {k = 0} ^ {n} p (y_ {k} | y_ {0}, \ cdots, y_ {k- 1})}

с участием

п ( у k | у 0 , , у k - 1 ) знак равно п ( у k | Икс k ) п ( d Икс k | у 0 , , у k - 1 ) {\ displaystyle p (y_ {k} | y_ {0}, \ cdots, y_ {k-1}) = \ int p (y_ {k} | x_ {k}) p (dx_ {k} | y_ {0) }, \ cdots, y_ {k-1})}

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

п ^ ( d Икс k | у 0 , , у k - 1 ) знак равно 1 N я знак равно 1 N δ ξ k я ( d Икс k ) N п ( d Икс k | у 0 , , у 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})}

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

п ( у 0 , , у п ) N п ^ ( у 0 , , у п ) знак равно k знак равно 0 п п ^ ( у k | у 0 , , у k - 1 ) {\ displaystyle p (y_ {0}, \ cdots, y_ {n}) \ приблизительно _ {N \ uparrow \ infty} {\ widehat {p}} (y_ {0}, \ cdots, y_ {n}) = \ prod _ {k = 0} ^ {n} {\ widehat {p}} (y_ {k} | y_ {0}, \ cdots, y_ {k-1})}

с участием

п ^ ( у k | у 0 , , у k - 1 ) знак равно п ( у k | Икс k ) п ^ ( d Икс k | у 0 , , у k - 1 ) знак равно 1 N я знак равно 1 N п ( у k | ξ k я ) {\ displaystyle {\ 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})}

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

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

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

п ( Икс 0 , , Икс п | у 0 , , у п - 1 ) знак равно п ( Икс п | у 0 , , у п - 1 ) п ( Икс п - 1 | Икс п , у 0 , , у п - 1 ) п ( Икс 1 | Икс 2 , у 0 , у 1 ) п ( Икс 0 | Икс 1 , у 0 ) {\ Displaystyle 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})}

Заметь

п ( Икс k - 1 | Икс k , ( у 0 , , у k - 1 ) ) п ( Икс k | Икс k - 1 ) п ( Икс k - 1 | ( у 0 , , у k - 1 ) ) п ( Икс k - 1 | ( у 0 , , у k - 1 ) п ( у k - 1 | Икс k - 1 ) п ( Икс k - 1 | ( у 0 , , у k - 2 ) {\ displaystyle {\ begin {align} p (x_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1})) amp; \ 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}) amp; \ propto p (y_ {k-1} | x_ {k-1}) p (x_ {k-1}) | (y_ {0}, \ cdots, y_ {k -2}) \ конец {выровнено}}}

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

п ( Икс k - 1 | Икс k , ( у 0 , , у k - 1 ) ) знак равно п ( у k - 1 | Икс k - 1 ) п ( Икс k | Икс k - 1 ) п ( Икс k - 1 | у 0 , , у k - 2 ) п ( у k - 1 | Икс k - 1 ) п ( Икс k | Икс k - 1 ) п ( Икс k - 1 | у 0 , , у k - 2 ) d Икс k - 1 {\ Displaystyle 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}}}}

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

п ^ ( d Икс k - 1 | ( у 0 , , у k - 2 ) ) знак равно 1 N я знак равно 1 N δ ξ k - 1 я ( d Икс k - 1 ) ( N п ( d Икс k - 1 | ( у 0 , , у k - 2 ) ) знак равно п ( Икс k - 1 | ( у 0 , , у k - 2 ) ) d Икс k - 1 ) {\ displaystyle {\ 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 (\ приблизительно _ {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)}

мы находим, что

п ( d Икс k - 1 | Икс k , ( у 0 , , у k - 1 ) ) N п ^ ( d Икс k - 1 | Икс k , ( у 0 , , у k - 1 ) ) знак равно п ( у k - 1 | Икс k - 1 ) п ( Икс k | Икс k - 1 ) п ^ ( d Икс k - 1 | у 0 , , у k - 2 ) п ( у k - 1 | Икс k - 1 )   п ( Икс k | Икс k - 1 ) п ^ ( d Икс k - 1 | у 0 , , у k - 2 ) знак равно я знак равно 1 N п ( у k - 1 | ξ k - 1 я ) п ( Икс k | ξ k - 1 я ) j знак равно 1 N п ( у k - 1 | ξ k - 1 j ) п ( Икс k | ξ k - 1 j ) δ ξ k - 1 я ( d Икс k - 1 ) {\ Displaystyle {\ begin {align} p (dx_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1})) amp; \ приблизительно _ {N \ uparrow \ infty } {\ widehat {p}} (dx_ {k-1} | x_ {k}, (y_ {0}, \ cdots, y_ {k-1})) \\ amp;: = {\ 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})}} \\ amp; = \ 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 {align}}}

Мы делаем вывод, что

п ( d ( Икс 0 , , Икс п ) | ( у 0 , , у п - 1 ) ) N п ^ б а c k ш а р d ( d ( Икс 0 , , Икс п ) | ( у 0 , , у п - 1 ) ) {\ displaystyle p (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1})) \ приблизительно _ {N \ uparrow \ infty} {\ widehat {p}} _ {назад} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1}))}

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

п ^ б а c k ш а р d ( d ( Икс 0 , , Икс п ) | ( у 0 , , у п - 1 ) ) знак равно п ^ ( d Икс п | ( у 0 , , у п - 1 ) ) п ^ ( d Икс п - 1 | Икс п , ( у 0 , , у п - 1 ) ) п ^ ( d Икс 1 | Икс 2 , ( у 0 , у 1 ) ) п ^ ( d Икс 0 | Икс 1 , у 0 ) {\ displaystyle {\ begin {align} {\ 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 {align}}}

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

п ^ б а c k ш а р d ( d ( Икс 0 , , Икс п ) | ( у 0 , , у п - 1 ) ) {\ displaystyle {\ widehat {p}} _ {назад} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1}))}

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

  • Первоначально (в момент времени k = n) цепочка случайным образом выбирает состояние с распределением Икс п , п {\ displaystyle \ mathbb {X} _ {n, n} ^ {\ flat}}
п ^ ( d Икс п | ( у 0 , , у п - 1 ) ) знак равно 1 N я знак равно 1 N δ ξ п я ( d Икс п ) {\ displaystyle {\ 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) цепочка, начиная с некоторого состояния для некоторого момента времени k, переходит в момент времени (k-1) в случайное состояние, выбранное с дискретной взвешенной вероятностью Икс k , п знак равно ξ k я {\ Displaystyle \ mathbb {X} _ {k, n} ^ {\ flat} = \ xi _ {k} ^ {i}} я знак равно 1 , , N {\ Displaystyle я = 1, \ cdots, N} Икс k - 1 , п {\ displaystyle \ mathbb {X} _ {k-1, n} ^ {\ flat}}
п ^ ( d Икс k - 1 | ξ k я , ( у 0 , , у k - 1 ) ) знак равно j знак равно 1 N п ( у k - 1 | ξ k - 1 j ) п ( ξ k я | ξ k - 1 j ) л знак равно 1 N п ( у k - 1 | ξ k - 1 л ) п ( ξ k я | ξ k - 1 л )   δ ξ k - 1 j ( d Икс k - 1 ) {\ Displaystyle {\ widehat {p}} (dx_ {k-1} | \ xi _ {k} ^ {i}, (y_ {0}, \ cdots, y_ {k-1})) = \ сумма _ {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})}

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

п ( d ( Икс 0 , , Икс п ) | ( у 0 , , у п - 1 ) ) ж k ( Икс k ) N п ^ б а c k ш а р d ( d ( Икс 0 , , Икс п ) | ( у 0 , , у п - 1 ) ) ж k ( Икс k ) знак равно п ^ ( d Икс п | ( у 0 , , у п - 1 ) ) п ^ ( d Икс п - 1 | Икс п , ( у 0 , , у п - 1 ) ) п ^ ( d Икс k | Икс k + 1 , ( у 0 , , у k ) ) ж k ( Икс k ) знак равно [ 1 N , , 1 N ] N  раз M п - 1 M k [ ж k ( ξ k 1 ) ж k ( ξ k N ) ] {\ displaystyle {\ begin {align} \ int p (d (x_ {0}, \ cdots, x_ {n}) amp; | (y_ {0}, \ cdots, y_ {n-1})) f_ {k } (x_ {k}) \\ amp; \ приблизительно _ {N \ uparrow \ infty} \ int {\ widehat {p}} _ {назад} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1})) f_ {k} (x_ {k}) \\ amp; = \ 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}) \\ amp; = \ 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 {align}}}

где

M k знак равно ( M k ( я , j ) ) 1 я , j N : M k ( я , j ) знак равно п ( ξ k я | ξ k - 1 j )   п ( у k - 1 | ξ k - 1 j ) л знак равно 1 N п ( ξ k я | ξ k - 1 л ) п ( у k - 1 | ξ k - 1 л ) {\ displaystyle \ 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})}}}

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

F ¯ ( Икс 0 , , Икс п ) знак равно 1 п + 1 k знак равно 0 п ж k ( Икс k ) {\ displaystyle {\ overline {F}} (x_ {0}, \ cdots, x_ {n}): = {\ frac {1} {n + 1}} \ sum _ {k = 0} ^ {n} f_ {k} (x_ {k})}

тогда

F ¯ ( Икс 0 , , Икс п ) п ( d ( Икс 0 , , Икс п ) | ( у 0 , , у п - 1 ) ) N F ¯ ( Икс 0 , , Икс п ) п ^ б а c k ш а р d ( d ( Икс 0 , , Икс п ) | ( у 0 , , у п - 1 ) ) знак равно 1 п + 1 k знак равно 0 п [ 1 N , , 1 N ] N  раз M п - 1 M п - 2 M k [ ж k ( ξ k 1 ) ж k ( ξ k N ) ] {\ displaystyle {\ begin {align} \ int {\ overline {F}} (x_ {0}, \ cdots, x_ {n}) p (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1})) amp; \ приблизительно _ {N \ uparrow \ infty} \ int {\ overline {F}} (x_ {0}, \ cdots, x_ {n}) {\ widehat {p}} _ {назад} (d (x_ {0}, \ cdots, x_ {n}) | (y_ {0}, \ cdots, y_ {n-1})) \\ amp; = {\ 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 {выровнены}}}

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

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

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

E ( п ^ ( у 0 , , у п ) ) знак равно п ( у 0 , , у п ) , E ( [ п ^ ( у 0 , , у п ) п ( у 0 , , у п ) - 1 ] 2 ) c п N , {\ displaystyle 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. Кроме того, для любых: Икс 0 {\ Displaystyle х \ geqslant 0}

п ( | 1 п бревно п ^ ( у 0 , , у п ) - 1 п бревно п ( у 0 , , у п ) | c 1 Икс N + c 2 Икс N ) gt; 1 - е - Икс {\ displaystyle \ 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)gt; 1-e ^ {- x}}

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

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

я k п а т час ( F ) знак равно F ( Икс 0 , , Икс k ) п ( d ( Икс 0 , , Икс k ) | у 0 , , у k - 1 ) N я ^ k п а т час ( F ) знак равно F ( Икс 0 , , Икс k ) п ^ ( d ( Икс 0 , , Икс k ) | у 0 , , у k - 1 ) знак равно 1 N я знак равно 1 N F ( ξ 0 , k я , , ξ k , k я ) {\ displaystyle {\ begin {align} I_ {k} ^ {path} (F) amp;: = \ int F (x_ {0}, \ cdots, x_ {k}) p (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1}) \\ amp; \ приблизительно _ {N \ uparrow \ infty} {\ widehat {I}} _ {k} ^ {путь } (F) \\ amp;: = \ int F (x_ {0}, \ cdots, x_ {k}) {\ widehat {p}} (d (x_ {0}, \ cdots, x_ {k}) | y_ {0}, \ cdots, y_ {k-1}) \\ amp; = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} F \ left (\ xi _ {0, k} ^ {i}, \ cdots, \ xi _ {k, k} ^ {i} \ right) \ end {align}}}

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

| E ( я ^ k п а т час ( F ) ) - я k п а т час ( F ) | c 1 k N , E ( [ я ^ k п а т час ( F ) - я k п а т час ( F ) ] 2 ) c 2 k N , {\ displaystyle \ 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, ограниченной 1, и для некоторых конечных констант Кроме того, для любых: c 1 , c 2 . {\ displaystyle c_ {1}, c_ {2}.} Икс 0 {\ Displaystyle х \ geqslant 0}

п ( | я ^ k п а т час ( F ) - я k п а т час ( F ) | c 1 k Икс N + c 2 k Икс N Как дела 0 k п | я ^ k п а т час ( F ) - я k п а т час ( F ) | c Икс п бревно ( п ) N ) gt; 1 - е - Икс {\ displaystyle \ 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)gt; 1-e ^ {- x}}

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

F ¯ ( Икс 0 , , Икс п ) знак равно 1 п + 1 0 k п ж k ( Икс k ) {\ displaystyle {\ overline {F}} (x_ {0}, \ cdots, x_ {n}): = {\ frac {1} {n + 1}} \ sum _ {0 \ leqslant k \ leqslant n} f_ {k} (x_ {k})}

с участием

я п п а т час ( F ¯ ) N я п , п а т час ( F ¯ ) знак равно F ¯ ( Икс 0 , , Икс п ) п ^ б а c k ш а р d ( d ( Икс 0 , , Икс п ) | ( у 0 , , у п - 1 ) ) {\ displaystyle I_ {n} ^ {путь} ({\ overline {F}}) \ приблизительно _ {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}))}

с функциями, ограниченными 1, имеем ж k {\ displaystyle f_ {k}}

Как дела п 0 | E ( я ^ п , п а т час ( F ¯ ) ) - я п п а т час ( F ¯ ) | c 1 N {\ displaystyle \ 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 ( [ я ^ п , п а т час ( F ) - я п п а т час ( F ) ] 2 ) c 2 п N + c 3 N 2 {\ displaystyle 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 . {\ displaystyle c_ {1}, c_ {2}, c_ {3}.}

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

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

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

{ ( ш k ( я ) , Икс k ( я ) )   :   я { 1 , , N } } . {\ Displaystyle \ left \ {\ left (w_ {k} ^ {(i)}, x_ {k} ^ {(i)} \ right) \: \ i \ in \ {1, \ cdots, N \} \верно\}.}

Эти веса важности являются приближениями к относительным апостериорным вероятностям (или плотность) образцов, такие, что ш k ( я ) {\ Displaystyle ш_ {к} ^ {(я)}}

я знак равно 1 N ш k ( я ) знак равно 1. {\ displaystyle \ sum _ {i = 1} ^ {N} w_ {k} ^ {(i)} = 1.}

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

ж ( Икс k ) п ( Икс k | у 0 , , у k ) d Икс k я знак равно 1 N ш k ( я ) ж ( Икс k ( я ) ) . {\ displaystyle \ int е (x_ {k}) p (x_ {k} | y_ {0}, \ dots, y_ {k}) dx_ {k} \ приблизительно \ sum _ {i = 1} ^ {N} w_ {k} ^ {(i)} f (x_ {k} ^ {(i)}).}

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

π ( Икс k | Икс 0 : k - 1 , у 0 : k ) {\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) \,}.

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

π ( Икс k | Икс 0 : k - 1 , у 0 : k ) знак равно п ( Икс k | Икс k - 1 , у k ) знак равно п ( у k | Икс k ) п ( у k | Икс k ) п ( Икс k | Икс k - 1 ) d Икс k   п ( Икс k | Икс k - 1 ) . {\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) = p (x_ {k} | x_ {k-1}, y_ {k}) = {\ гидроразрыв {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 годах. Когда трудно выбрать переходы в соответствии с распределением, естественной стратегией является использование следующего приближения частиц п ( Икс k | Икс k - 1 , у k ) {\ Displaystyle p (x_ {k} | x_ {k-1}, y_ {k})}

п ( у k | Икс k ) п ( у k | Икс k ) п ( Икс k | Икс k - 1 ) d Икс k п ( Икс k | Икс k - 1 ) d Икс k N п ( у k | Икс k ) п ( у k | Икс k ) п ^ ( d Икс k | Икс k - 1 ) п ^ ( d Икс k | Икс k - 1 ) знак равно я знак равно 1 N п ( у k | Икс k я ( Икс k - 1 ) ) j знак равно 1 N п ( у k | Икс k j ( Икс k - 1 ) ) δ Икс k я ( Икс k - 1 ) ( d Икс k ) {\ Displaystyle {\ begin {align} {\ 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} amp; \ 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}) \\ amp; = \ 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 {align}}}

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

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

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

π ( Икс k | Икс 0 : k - 1 , у 0 : k ) знак равно п ( Икс k | Икс k - 1 ) . {\ displaystyle \ pi (x_ {k} | x_ {0: k-1}, y_ {0: k}) = p (x_ {k} | x_ {k-1}).}

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

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

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

1) Для выборки образцов из рассылки предложений. я знак равно 1 , , N {\ Displaystyle я = 1, \ cdots, N}
Икс k ( я ) π ( Икс k | Икс 0 : k - 1 ( я ) , у 0 : k ) {\ displaystyle x_ {k} ^ {(i)} \ sim \ pi (x_ {k} | x_ {0: k-1} ^ {(i)}, y_ {0: k})}
2) Для обновления весов важности до нормализующей константы: я знак равно 1 , , N {\ Displaystyle я = 1, \ cdots, N}
ш ^ k ( я ) знак равно ш k - 1 ( я ) п ( у k | Икс k ( я ) ) п ( Икс k ( я ) | Икс k - 1 ( я ) ) π ( Икс k ( я ) | Икс 0 : k - 1 ( я ) , у 0 : k ) . {\ displaystyle {\ 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})}}.}
Обратите внимание, что когда мы используем распределение априорной вероятности перехода в качестве функции важности,
π ( Икс k ( я ) | Икс 0 : k - 1 ( я ) , у 0 : k ) знак равно п ( Икс k ( я ) | Икс k - 1 ( я ) ) , {\ displaystyle \ pi (x_ {k} ^ {(i)} | x_ {0: k-1} ^ {(i)}, y_ {0: k}) = p (x_ {k} ^ {(i)} | x_ {k-1} ^ {(i)}),}
это упрощается до следующего:
ш ^ k ( я ) знак равно ш k - 1 ( я ) п ( у k | Икс k ( я ) ) , {\ displaystyle {\ hat {w}} _ {k} ^ {(i)} = w_ {k-1} ^ {(i)} p (y_ {k} | x_ {k} ^ {(i)}),}
3) Для вычисления нормализованных весов важности: я знак равно 1 , , N {\ Displaystyle я = 1, \ cdots, N}
ш k ( я ) знак равно ш ^ k ( я ) j знак равно 1 N ш ^ k ( j ) {\ displaystyle w_ {k} ^ {(i)} = {\ frac {{\ hat {w}} _ {k} ^ {(i)}} {\ sum _ {j = 1} ^ {N} { \ hat {w}} _ {k} ^ {(j)}}}}
4) Вычислите оценку эффективного числа частиц как
N ^ е ж ж знак равно 1 я знак равно 1 N ( ш k ( я ) ) 2 {\ displaystyle {\ hat {N}} _ {\ mathit {eff}} = {\ frac {1} {\ sum _ {i = 1} ^ {N} \ left (w_ {k} ^ {(i) } \ right) ^ {2}}}}
Этот критерий отражает дисперсию весов, другие критерии можно найти в статье, включая их строгий анализ и центральные предельные теоремы.
5) Если эффективное количество частиц меньше заданного порога, выполните повторную выборку: N ^ е ж ж lt; N т час р {\ displaystyle {\ hat {N}} _ {\ mathit {eff}} lt;N_ {th}}
a) Нарисуйте N частиц из текущего набора частиц с вероятностями, пропорциональными их весу. Замените текущий набор частиц новым.
б) Для множества я знак равно 1 , , N {\ Displaystyle я = 1, \ cdots, N} ш k ( я ) знак равно 1 / N . {\ displaystyle w_ {k} ^ {(i)} = 1 / N.}

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

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

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

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

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

1) Установите n = 0 (будет подсчитано количество сгенерированных частиц)
2) Равномерно выберите индекс i из диапазона { 1 , . . . , N } {\ displaystyle \ {1,..., N \}}
3) Создайте тест из дистрибутива с Икс ^ {\ displaystyle {\ hat {x}}} п ( Икс k | Икс k - 1 ) {\ displaystyle p (x_ {k} | x_ {k-1})} Икс k - 1 знак равно Икс k - 1 | k - 1 ( я ) {\ Displaystyle х_ {к-1} = х_ {к-1 | к-1} ^ {(я)}}
4) Создание вероятности, используя из, где это измеренное значение у ^ {\ displaystyle {\ hat {y}}} Икс ^ {\ displaystyle {\ hat {x}}} п ( у k | Икс k ) ,   с участием   Икс k знак равно Икс ^ {\ displaystyle p (y_ {k} | x_ {k}), ~ {\ t_dv {with}} ~ x_ {k} = {\ hat {x}}} у k {\ displaystyle y_ {k}}
5) Создайте еще одну однородную u, откуда [ 0 , м k ] {\ displaystyle [0, m_ {k}]} м k знак равно Как дела Икс k п ( у k | Икс k ) {\ displaystyle m_ {k} = \ sup _ {x_ {k}} p (y_ {k} | x_ {k})}
6) Сравните u и п ( у ^ ) {\ displaystyle p \ left ({\ hat {y}} \ right)}
6a) Если u больше, повторите с шага 2.
6b) Если u меньше, сохраните как и увеличьте n Икс ^ {\ displaystyle {\ hat {x}}} Икс k | k ( я ) {\ Displaystyle х_ {к | к} ^ {(я)}}
7) Если n == N, то выйти

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

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

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

Смотрите также

Рекомендации

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

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

Последняя правка сделана 2023-04-05 04:27:12
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте