Метод частиц: алгоритмы Монте-Карло для обработки сигналов и статистического вывода.

Введение

Тип алгоритмов Монте-Карло для обработки сигналов и статистического вывода – математические алгоритмы

Фильтры частиц, или последовательные методы Монте-Карло, – это набор алгоритмов Монте-Карло, используемых для поиска приближенных решений задач фильтрации для нелинейных систем пространства состояний, таких как обработка сигналов и байесовский статистический вывод. Задача фильтрации состоит в оценке внутренних состояний в динамических системах при частичных наблюдениях и наличии случайных возмущений как в датчиках, так и в динамической системе. Цель состоит в вычислении апостериорных распределений состояний марковского процесса, учитывая зашумленные и частичные наблюдения. Термин "фильтр частиц" впервые был введен в 1996 году Пьером Дель Моралем по отношению к методам взаимодействия частиц в среднем поле, используемым в механике жидкости с начала 1960-х годов. Термин "последовательное Монте-Карло" был введен Чжун С. Лю и Рон Ченом в 1998 году. Фильтрация частиц использует набор частиц (также называемых образцами) для представления апостериорного распределения стохастического процесса, учитывая зашумленные и/или частичные наблюдения. Модель пространства состояний может быть нелинейной, а начальное распределение состояний и шума может принимать любую необходимую форму. Методы фильтрации частиц обеспечивают хорошо зарекомендовавшую себя методологию для генерации образцов из требуемого распределения без необходимости делать предположения о модели пространства состояний или распределениях состояний. Однако эти методы неэффективны при применении к системам очень высокой размерности. Фильтры частиц обновляют свои прогнозы приближенным (статистическим) образом. Образцы из распределения представлены набором частиц; каждой частице присваивается вес вероятности, который представляет вероятность того, что эта частица была отобрана из функции плотности вероятности. Неравномерность весов, приводящая к коллапсу весов, является распространенной проблемой, возникающей в этих алгоритмах фильтрации. Однако ее можно смягчить, включив шаг перевыборки до того, как веса станут слишком неравномерными. Можно использовать несколько критериев адаптивной перевыборки, включая дисперсию весов и относительную энтропию по отношению к равномерному распределению. На этапе перевыборки частицы с пренебрежимо малыми весами заменяются новыми частицами вблизи частиц с более высокими весами. С точки зрения статистики и теории вероятностей, фильтры частиц можно интерпретировать как интерпретации частиц в среднем поле мер вероятности Фейнмана-Каца. Эти методы интегрирования частиц были разработаны в молекулярной химии и вычислительной физике Теодором Э. Харрисом и Германом Каном в 1951 году, Маршаллом Н. Розенблютом и Арианной В. Розенблют в 1955 году, а в последнее время Джеком Х. Хеттерингтоном в 1984 году. Методы взаимодействия частиц Фейнмана-Каца также тесно связаны с генетическими алгоритмами мутации и отбора, которые в настоящее время используются в эволюционных вычислениях для решения сложных задач оптимизации. Методология фильтра частиц используется для решения задач скрытой модели Маркова (HMM) и нелинейной фильтрации. За исключением заметных моделей наблюдения линейных гауссовских сигналов (фильтр Калмана) или более широких классов моделей (фильтр Бенеса), Мирель Шалеят-Морель и Доминик Мишель доказали в 1984 году, что последовательность апостериорных распределений случайных состояний сигнала, учитывая наблюдения (также известный как оптимальный фильтр), не имеет конечной рекурсии. Различные другие численные методы, основанные на приближениях фиксированной сетки, методах Монте-Карло цепей Маркова, обычной линеаризации, расширенных фильтрах Калмана или определении наилучшей линейной системы (в смысле ожидаемой ошибки стоимости), не могут справиться с крупномасштабными системами, неустойчивыми процессами или недостаточно гладкими нелинейностями. Фильтры частиц и методологии частиц Фейнмана-Каца находят применение в обработке сигналов и изображений, байесовском выводе, машинном обучении, анализе рисков и отборе редких событий, инженерии и робототехнике, искусственном интеллекте, биоинформатике, филогенетике, вычислительной науке, экономике и математических финансах, молекулярной химии, вычислительной физике, фармакокинетике, количественной оценке рисков и страховании и других областях.

Particle filters, or sequential Monte Carlo methods, are a set of Monte Carlo algorithms used to find approximate solutions for filtering problems for nonlinear state space systems, such as signal processing and Bayesian statistical inference. The filtering problem consists of estimating the internal states in dynamical systems when partial observations are made and random perturbations are present in the sensors as well as in the dynamical system. The objective is to compute the posterior distributions of the states of a Markov process, given the noisy and partial observations. The term "particle filters" was first coined in 1996 by Pierre Del Moral about mean field interacting particle methods used in fluid mechanics since the beginning of the 1960s. The term "Sequential Monte Carlo" was coined by Jun S. Liu and Rong Chen in 1998. Particle filtering uses a set of particles (also called samples) to represent the posterior distribution of a stochastic process given the noisy and/or partial observations. The state space model can be nonlinear and the initial state and noise distributions can take any form required. Particle filter techniques provide a well established methodology for generating samples from the required distribution without requiring assumptions about the state space model or the state distributions. However, these methods do not perform well when applied to very high dimensional systems. Particle filters update their prediction in an approximate (statistical) manner. The samples from the distribution are represented by a set of particles; each particle has a likelihood weight assigned to it that represents the probability of that particle being sampled from the probability density function. Weight disparity leading to weight collapse is a common issue encountered in these filtering algorithms. However, it can be mitigated by including a resampling step before the weights become uneven. Several adaptive resampling criteria can be used including the variance of the weights and the relative entropy concerning the uniform distribution. In the resampling step, the particles with negligible weights are replaced by new particles in the proximity of the particles with higher weights. From the statistical and probabilistic point of view, particle filters may be interpreted as mean field particle interpretations of Feynman Kac probability measures. These particle integration techniques were developed in molecular chemistry and computational physics by Theodore E. Harris and Herman Kahn in 1951, Marshall N. Rosenbluth and Arianna W. Rosenbluth in 1955, and more recently by Jack H. Hetherington in 1984. Feynman Kac interacting particle methods are also strongly related to mutation selection genetic algorithms currently used in evolutionary computation to solve complex optimization problems. The particle filter methodology is used to solve Hidden Markov Model (HMM) and nonlinear filtering problems. With the notable exception of linear Gaussian signal observation models (Kalman filter) or wider classes of models (Benes filter), Mireille Chaleyat Maurel and Dominique Michel proved in 1984 that the sequence of posterior distributions of the random states of a signal, given the observations (a. k. a. optimal filter), has no finite recursion. Various other numerical methods based on fixed grid approximations, Markov Chain Monte Carlo techniques, conventional linearization, extended Kalman filters, or determining the best linear system (in the expected cost error sense) are unable to cope with large scale systems, unstable processes, or insufficiently smooth nonlinearities. Particle filters and Feynman Kac particle methodologies find application in signal and image processing, Bayesian inference, machine learning, risk analysis and rare event sampling, engineering and robotics, artificial intelligence, bioinformatics, phylogenetics, computational science, economics and mathematical finance, molecular chemistry, computational physics, pharmacokinetics, quantitative risk and insurance and other fields.

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

С статистической и вероятностной точки зрения, фильтры частиц относятся к классу алгоритмов разветвления/генетического типа и методологий взаимодействия частиц среднего поля. Интерпретация этих методов частиц зависит от научной дисциплины. В эволюционных вычислениях методологии частиц среднего генетического типа часто используются в качестве эвристических и естественных алгоритмов поиска (также известных как метаэвристические). В вычислительной физике и молекулярной химии они используются для решения задач интеграции пути Фейнмана — Кака или для вычисления мер Болцмана — Гиббса, верхних собственных значений и основных состояний операторов Шредингера. В биологии и генетике они представляют собой эволюцию популяции индивидуумов или генов в некоторой среде. Истоки эволюционных вычислительных методов среднего поля можно проследить до 1950 и 1954 годов с работы Алана Тьюринга по машинному обучению селекции мутаций генетического типа и статей Нильса Аалла Барричелли в Институте передовых исследований в Принстоне, Нью-Джерси. Первые следы фильтров частиц в статистической методологии датируются серединой 1950-х годов; «Монте-Карло для бедных», предложенный Хаммерсли и др. в 1954 году, содержал намеки на методы фильтрации частиц генетического типа, используемые сегодня. В 1963 году Нильс Аалл Барричелли смоделировал алгоритм генетического типа, чтобы имитировать способность людей играть в простую игру. В литературе по эволюционным вычислениям алгоритмы отбора мутаций генетического типа стали популярными благодаря основополагающей работе Джона Холланда в начале 1970-х годов, особенно его книге, опубликованной в 1975 году. В биологии и генетике австралийский генетик Алекс Фрейзер также опубликовал в 1957 году серию статей о генетическом моделировании искусственного отбора организмов. Компьютерное моделирование эволюции биологами стало более распространенным в начале 1960-х годов, а методы были описаны в книгах Фрейзера и Бернелла (1970) и Кросби (1973). Моделирование Фрейзера включало в себя все основные элементы современных алгоритмов генетических частиц селекции мутаций. С математической точки зрения, условное распределение случайных состояний сигнала при некоторых частичных и шумных наблюдениях описывается вероятностью Фейнмана — Кака на случайных траекториях сигнала, взвешенных последовательностью потенциальных функций правдоподобия. Происхождение квантовых методов Монте-Карло часто приписывают Энрико Ферми и Роберту Рихтмайеру, которые разработали в 1948 году интерпретацию частиц среднего поля нейтронных цепных реакций, но первый эвристический алгоритм частиц, подобный генетическому типу (также известный как методы Монте-Карло с перевыбором или переконфигурацией) для оценки энергий основного состояния квантовых систем (в моделях уменьшенной матрицы) был разработан Джеком Х. Хетеррингтоном в 1984 году. В молекулярной химии использование генетических эвристических методологий (так называемых стратегий отсева и обогащения) можно проследить до 1955 года с основополагающей работы Маршалла Н. Розенблюта и Арианны В. Розенблют. В 1996 году появилась слегка измененная версия этой статьи. В апреле 1993 года Гордон и др. опубликовали в своей основополагающей работе применение алгоритма генетического типа в байесовском статистическом выводе. Авторы назвали свой алгоритм «загрузочным фильтром» и продемонстрировали, что по сравнению с другими методами фильтрации их загрузочный алгоритм не требует каких-либо предположений о пространстве состояний или шуме системы. Независимо от этого, работы Пьера Дель Мораля по фильтрам частиц, опубликованные в середине 1990-х годов. Фильтры частиц также были разработаны в обработке сигналов в начале 1989–1992 годов П. Дель Моралем, Ж. К. Нуайером, Г. Ригалем и Г. Салютом в LAAS CNRS в серии ограниченных и засекреченных исследовательских докладов с STCAN (Service Technique des Constructions et Armes Navales), IT-компанией DIGILOG и LAAS CNRS (Лаборатория анализа и архитектуры систем) по проблемам обработки сигналов РЛС/ГСЛ и GPS.

From a statistical and probabilistic viewpoint, particle filters belong to the class of branching/genetic type algorithms, and mean field type interacting particle methodologies. The interpretation of these particle methods depends on the scientific discipline. In Evolutionary Computing, mean field genetic type particle methodologies are often used as heuristic and natural search algorithms (a. k. a. Metaheuristic). In computational physics and molecular chemistry, they are used to solve Feynman Kac path integration problems or to compute Boltzmann Gibbs measures, top eigenvalues, and ground states of Schrödinger operators. In Biology and Genetics, they represent the evolution of a population of individuals or genes in some environment. The origins of mean field type evolutionary computational techniques can be traced back to 1950 and 1954 with Alan Turing's work on genetic type mutation selection learning machines and the articles by Nils Aall Barricelli at the Institute for Advanced Study in Princeton, New Jersey. The first trace of particle filters in statistical methodology dates back to the mid 1950s; the 'Poor Man's Monte Carlo', that was proposed by Hammersley et al., in 1954, contained hints of the genetic type particle filtering methods used today. In 1963, Nils Aall Barricelli simulated a genetic type algorithm to mimic the ability of individuals to play a simple game. In evolutionary computing literature, genetic type mutation selection algorithms became popular through the seminal work of John Holland in the early 1970s, particularly his book published in 1975. In Biology and Genetics, the Australian geneticist Alex Fraser also published in 1957 a series of papers on the genetic type simulation of artificial selection of organisms. The computer simulation of the evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970) and Crosby (1973). Fraser's simulations included all of the essential elements of modern mutation selection genetic particle algorithms. From the mathematical viewpoint, the conditional distribution of the random states of a signal given some partial and noisy observations is described by a Feynman Kac probability on the random trajectories of the signal weighted by a sequence of likelihood potential functions. The origins of Quantum Monte Carlo methods are often attributed to Enrico Fermi and Robert Richtmyer who developed in 1948 a mean field particle interpretation of neutron chain reactions, but the first heuristic like and genetic type particle algorithm (a. k. a. Resampled or Reconfiguration Monte Carlo methods) for estimating ground state energies of quantum systems (in reduced matrix models) is due to Jack H. Hetherington in 1984. In molecular chemistry, the use of genetic heuristic like particle methodologies (a. k. a. pruning and enrichment strategies) can be traced back to 1955 with the seminal work of Marshall N. Rosenbluth and Arianna W. Rosenbluth. a slightly modified version of this article appeared in 1996. In April 1993, Gordon et al., published in their seminal work an application of genetic type algorithm in Bayesian statistical inference. The authors named their algorithm 'the bootstrap filter', and demonstrated that compared to other filtering methods, their bootstrap algorithm does not require any assumption about that state space or the noise of the system. Independently, the ones by Pierre Del Moral on particle filters published in the mid 1990s. Particle filters were also developed in signal processing in early 1989 1992 by P. Del Moral, J. C. Noyer, G. Rigal, and G. Salut in the LAAS CNRS in a series of restricted and classified research reports with STCAN (Service Technique des Constructions et Armes Navales), the IT company DIGILOG, and the LAAS CNRS (the Laboratory for Analysis and Architecture of Systems) on RADAR/SONAR and GPS signal processing problems.

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

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

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

Цель

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

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

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

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

Отбор проб по последовательному значению (SIS)

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