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

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

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

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

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

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

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

История

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

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

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

Цель

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

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

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

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

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

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

  • - это марковский процесс на (для некоторых ), который развивается согласно плотности вероятности перехода . Эта модель также часто записывается синтетическим способом как
с начальной плотностью вероятности .
  • Наблюдения принимают значения в некотором пространстве состояний (для некоторых ) и являются условно независимыми при условии, что они известны. Другими словами, каждый зависит только от . Кроме того, мы предполагаем, что условное распределение для данного абсолютно непрерывно, и синтетическим путем имеем

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

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

Предположение об абсолютной непрерывности начального распределения и переходов цепи Маркова относительно меры Лебега можно ослабить. Чтобы разработать фильтр частиц, нам просто нужно предположить, что мы можем выполнить выборку переходов цепи Маркова и вычислить функцию правдоподобия (см., Например, описание мутации генетического отбора фильтра частиц, приведенное ниже). Абсолютно непрерывное предположение о марковских переходах используется только для неформального (и довольно оскорбительного) вывода различных формул между апостериорными распределениями с использованием правила Байеса для условных плотностей.

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

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

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

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

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

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

где

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

 

 

 

 

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

с конвенцией для к = 0. Нелинейная задача фильтрации состоит в вычислении этих условных распределений последовательно.

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

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

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

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

а также

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

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

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

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

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

  • Во время перехода от выбора к обновлению мы отбираем N (условно) независимых случайных величин с общим (условным) распределением

где - мера Дирака в данном состоянии a.

  • Во время перехода предсказание мутации из каждой выбранной частицы мы независимо отбираем переход

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

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

а также

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

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

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

Например, у нас может быть N выборок из приблизительного апостериорного распределения , где выборки помечены надстрочными индексами как

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

 

 

 

 

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

с участием

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

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

частиц . Случайные состояния с нижними индексами l = 0, ..., k обозначают предка индивидуума на уровне l = 0, ..., k. В этой ситуации имеем аппроксимационную формулу

 

 

 

 

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

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

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

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

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

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

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

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

На следующем этапе мы выбираем N (условно) независимых случайных величин с общим законом.

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

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

 

 

 

 

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

Для k = 0 мы используем соглашение .

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

в смысле

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

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

В этой ситуации, заменив на эмпирических мерах в уравнении эволюции оптимального фильтра одностадийного , указанном в ( э. 4 ) находят , что

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

где обозначает плотность , измеренную при , и обозначает плотность , измеренную при для

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

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

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

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

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

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

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

для любой функции f, ограниченной 1, и для некоторых конечных констант Кроме того, для любых :

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

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

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

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

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

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

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

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

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

с участием

а также конвенции и для K = 0. Заменяя в эмпирическом приближении

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

с участием

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

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

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

Заметь

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

Замена одношаговых оптимальных предикторов эмпирическими мерами частиц

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

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

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

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

- это вероятность того, что случайные траектории цепи Маркова бегут назад во времени от времени k = n до времени k = 0 и развиваются на каждом временном шаге k в пространстве состояний, связанном с популяцией частиц

  • Первоначально (в момент времени k = n) цепочка случайным образом выбирает состояние с распределением
  • От момента k до момента времени (k-1) цепочка, начиная с некоторого состояния для некоторого момента времени k, переходит в момент времени (k-1) в случайное состояние, выбранное с дискретной взвешенной вероятностью

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

где

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

тогда

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

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

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

для некоторой конечной постоянной c . Кроме того, для любых :

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

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

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

для любой функции F, ограниченной 1, и для некоторых конечных констант Кроме того, для любых :

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

с участием

с функциями, ограниченными 1, имеем

а также

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

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

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

Последовательная передискретизация (SIR) , фильтрация Монте-Карло (Китагава, 1993) и алгоритм бутстрапной фильтрации (Гордон и др., 1993) также широко применяются в алгоритмах фильтрации, которые аппроксимируют плотность вероятности фильтрации взвешенным набором из N выборок.

Эти веса важности являются приближениями к относительным апостериорным вероятностям (или плотность) образцов , такие , что

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

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

.

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

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

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

связан с N (или любого другого большого числа образцов) независимых случайных выборок с условным распределением случайного состояния заданного . Согласованность результирующего фильтра частиц этого приближения и других расширений разработана в. На приведенном выше отображении обозначена мера Дирака в данном состоянии a.

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

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

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

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

1) Для выборки образцов из рассылки предложений.
2) Для обновления весов важности до нормализующей константы:
Обратите внимание, что когда мы используем распределение априорной вероятности перехода в качестве функции важности,
это упрощается до следующего:
3) Для вычисления нормализованных весов важности:
4) Вычислите оценку эффективного числа частиц как
Этот критерий отражает дисперсию весов, другие критерии можно найти в статье, включая их строгий анализ и центральные предельные теоремы.
5) Если эффективное количество частиц меньше заданного порога , выполните повторную выборку:
a) Нарисуйте N частиц из текущего набора частиц с вероятностями, пропорциональными их весу. Замените текущий набор частиц новым.
б) Для множества

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

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

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

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

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

1) Установите n = 0 (будет подсчитано количество сгенерированных частиц)
2) Равномерно выберите индекс i из диапазона
3) Создайте тест из дистрибутива с
4) Создание вероятности , используя из , где это измеренное значение
5) Создайте еще одну однородную u, откуда
6) Сравните u и
6a) Если u больше, повторите с шага 2.
6b) Если u меньше, сохраните как и увеличьте n
7) Если n == N, то выйти

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

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

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

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

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

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

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