Бөлшектік сүзгілер: сигналды өңдеу және статистикалық қорытындылар үшін Монте-Карло әдістері

Кіріспе

Сигналды өңдеу және статистикалық қорытынды жасау үшін Монте-Карло алгоритмдерінің түрлері – математикалық алгоритмдер.

Көлшек сүзгілері немесе ретті Монте-Карло әдістері – сигналды өңдеу және Байес статистикалық қорытынды жасау сияқты сызықтық емес жай-күй кеңістігі жүйелері үшін сүзгілеу мәселелерін шешуге қолданылатын Монте-Карло алгоритмдерінің жиынтығы. Сүзгілеу мәселесі динамикалық жүйелердегі ішкі күйлерді бағалаудан тұрады, егер ішінара байқаулар жасалса және динамикалық жүйедегі сенсорларда да кездейсоқ бұзылыстар болса. Мақсаты – шулы және ішінара бақылауларды ескере отырып, Марков процесінің күйлерінің кейінгі үлестірілімдерін есептеу. «Көлшек сүзгілері» термині алғаш рет 1996 жылы Пьер Дель Мораль 1960 жылдардың басынан бері сұйықтық механикасында қолданылатын орташа өрістегі өзара әрекеттесетін бөлшектер әдістері туралы айтқан. «Ретті Монте-Карло» термині 1998 жылы Цзюнь С. Лю және Ронг Ченмен бірге пайда болды. Көлшек сүзгілеу шулы және/немесе ішінара бақылауларды ескере отырып, стохастикалық процестің артқы таралуын бейнелеу үшін бөлшектер жиынтығын (сондай-ақ, үлгілер деп аталады) пайдаланады. Жай-күй кеңістігі моделі сызықтық емес болуы мүмкін, ал бастапқы жай-күй және шудың таралуы кез келген қажетті нысанда болуы мүмкін. Көлшек сүзгілеу әдістері қажетті үлестіруден үлгілер алу үшін жақсы қалыптасқан әдістемені ұсынады, бұл үшін жай-күй кеңістігі моделі немесе жай-күй үлестірулері туралы болжамдар қажет емес. Алайда, бұл әдістер өте жоғары өлшемді жүйелерге қолданылғанда жақсы жұмыс істемейді. Көлшек сүзгілері өз болжамын шамамен (статистикалық) түрде жаңартады. Таралымнан алынған үлгілер бөлшектер жиынтығы арқылы бейнеленеді; әрбір бөлшекке оның үлгілену ықтималдығын көрсететін ықтималдық салмағы беріледі. Салмақтың айырмашылығына байланысты салмақ құлдырауы – бұл сүзгілеу алгоритмдерінде кездесетін жиі кездесетін мәселе. Алайда, салмақ біркелкі болмас бұрын қайта іріктеу кезеңін қосу арқылы оны жеңілдетуге болады. Салмақтардың дисперсиясы және біркелкі таралуға қатысты салыстырмалы энтропияны қоса алғанда, бірнеше адаптивті қайта іріктеу критерийлерін қолдануға болады. Қайта іріктеу кезеңінде салмағы аз бөлшектер салмағы жоғары бөлшектердің жанында жаңа бөлшектермен ауыстырылады. Статистикалық және ықтималдық тұрғысынан алғанда, көлшек сүзгілерін Фейнман-Кац ықтималдық өлшемдерінің орташа өрістегі бөлшектер түсіндірмесі ретінде қарастыруға болады. Бұл бөлшектерді интеграциялау әдістерін молекулалық химия және есептеу физикасында Теодор Э. Харрис пен Герман Кан 1951 жылы, Маршалл Н. Розенблут пен Арианна В. Розенблут 1955 жылы және соңғы кезде Джек Х. Хетрингтон 1984 жылы әзірлеген. Фейнман-Кацтың өзара әрекеттесетін бөлшектер әдістері қазіргі кезде эволюциялық есептеулерде күрделі оптимизациялық мәселелерді шешу үшін қолданылатын мутациялық-селекциялық генетикалық алгоритмдермен де тығыз байланысты. Көлшек сүзгілеу әдістемесі жасырын Марков моделін (ЖММ) және сызықтық емес сүзгілеу мәселелерін шешу үшін қолданылады. Сызықтық Гаусс сигналдарын бақылау модельдерін (Калман сүзгісі) немесе модельдердің кеңірек топтарын (Бенс сүзгісі) қоспағанда, Мирель Шалеят Маурел мен Доминик Мишель 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 жылдың сәуір айында Гордон және авторлар өздерінің маңызды жұмысында Байес статистикалық қорытындысында генетикалық типтегі алгоритмді қолдануды жариялады. Авторлар өз алгоритмін «bootstrap сүзгісі» деп атады және басқа сүзгілеу әдістерімен салыстырғанда, олардың bootstrap алгоритміне күй кеңістігі немесе жүйенің шуы туралы ешқандай болжам қажет емес екенін көрсетті. Пьер Дель Моральдың 1990 жылдардың ортасында жарық көрген бөлшектер сүзгілері туралы тәуелсіз зерттемелері де болды. Бөлшектер сүзгілерін сигналды өңдеуде 1989-1992 жылдары П. Дель Мораль, Дж.К. Нойер, Г. Ригал және Г. Салют LAAS CNRS-те STCAN (Service Technique des Constructions et Armes Navales), DIGILOG IT компаниясы және LAAS CNRS (Системаларды талдау және архитектура зертханасы) RADAR/SONAR және 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)

Кезекті маңыздылықты қайта бағалаумен бірдей, бірақ қайта бағалау кезеңі жоқ.