В этом посте я попытаюсь объяснить фильтры частиц (PF) и их применение для корректировки измерений GPS. По моему опыту, большинство источников в Интернете предоставляют правильные и подробные объяснения, но обычно недоступны, см., Например, следующий абзац, содержащий определение Википедии:
«Фильтры частиц - это набор алгоритмов Монте-Карло, используемых для решения проблем фильтрации, возникающих при обработке сигналов и байесовском статистическом выводе. Задача фильтрации состоит в оценке состояния динамической системы при частичных наблюдениях. Цель состоит в том, чтобы вычислить апостериорные распределения состояний некоторого марковского процесса ... Этот термин впервые был введен в употребление в 1996 году Делом Моралом для обозначения методов взаимодействующих частиц среднего поля ... »
Моя цель - помочь широкой аудитории понять PF с практической точки зрения, но прежде чем мы разберемся, что такое PF и как мы можем их использовать, мы должны подумать, почему мы вообще хотим исправлять местоположения GPS. На рисунке 1 красные точки показывают фактическое местоположение показаний GPS с устройств (например, телефонов, автомобилей и т. Д.), Эти показания обычно состоят из широты и долготы (а также других метаданных, таких как время, скорость, высота). . В большинстве доступных клиентам устройств это местоположение находится в пределах 10 м (примерно 30 футов) от фактического местоположения. Как вы можете видеть на изображении, это означает, что необработанные данные, поступающие с устройств GPS, могут поместить вас в центр здания, в воду, и не обязательно там, где вы на самом деле находитесь. Это может ухудшиться, если устройство находится близко к препятствиям, например, к большим зданиям. Задача в этом случае состоит в том, чтобы найти фактическое местоположение устройства на основе всей доступной информации и поместить показание в то место, где оно действительно произошло (или, по крайней мере, то место, где оно наиболее вероятно произошло).
Можно подумать, что достаточно привязать точку к ближайшей улице, но это не так. Как видно на рисунке 2, ближайшая улица к некоторым точкам за углом будет означать, что движущийся объект сделает быстрый разворот, что маловероятно, учитывая, что мы видим, что объект, скорее всего, просто поворачивал за угол. . Понимание здесь состоит в том, что мы можем угадать реальную траекторию объекта, посмотрев, где он был раньше, а где будет позже.
Задача прогнозирования состояния системы (например, местоположения автомобиля) с использованием предыдущих состояний называется фильтрацией, а PF - лишь один из многих алгоритмов, которые можно использовать для решения этой проблемы. Формально входные данные для фильтров можно определить как измерения датчика с шумом от динамической системы, и цель состоит в том, чтобы оценить измерение (т. Е. Новое состояние) в момент t с использованием всех наблюдений с самого начала. .
Можно думать о динамической системе в терминах состояний и наблюдений. На каждом временном шаге система переходит из состояния в состояние по определенной схеме (обычно представленной как функция или распределение вероятностей), называемой моделью перехода, в то время как датчик выдает измерение на основе текущего состояния. , который может содержать шум или следовать другому определенному шаблону, традиционно называемому датчиком или моделью наблюдения. См. Рисунок 3 для графического представления.
Следуя символам на рисунке 3, состояние системы в момент t можно вычислить как
где v_t - шум. Обратите внимание, что здесь мы делаем несколько сильное (но общее) предположение, что текущее состояние зависит только от предыдущего, это называется Марковским предположением (первого порядка).
Тогда задача фильтрации может быть определена как вычисление следующей вероятности итеративным способом:
который можно читать как «Чтобы вычислить апостериорную вероятность нахождения в состоянии s_t с учетом всех наблюдений от начала до предыдущего временного шага, нам нужно только вычислить вероятность нахождения в состоянии предыдущее состояние s_t-1 (это итеративная часть), умноженное на вероятность перехода от s_t-1 к s_t для всех возможных s_t-1 состояния ».
Теоретически это значение может быть точно вычислено с использованием алгоритма переадресации, но только в очень конкретных случаях это может быть выполнено эффективно (например, все распределения являются гауссовскими). На практике в большинстве интересных случаев пространство состояний либо слишком велико для эффективных вычислений, либо распределения необходимо аппроксимировать (например, посредством выборки).
Именно в этих случаях в игру вступает PF. Общая идея состоит в том, чтобы представить вероятность набором случайно выбранных взвешенных выборок (называемых частицами), см. Рисунок 4. Случайно выбранная часть - это то, что делает этот алгоритм Монте-Карло.
У использования этого представления несколько преимуществ: 1) оно может представлять любое произвольное распределение, чем больше частиц, тем точнее наше представление, и 2) оно позволяет нам более эффективно вычислять желаемые значения, ограничивая пространство поиска, потому что вместо сохраняя весь дистрибутив, мы буквально сохраняем только список из N частиц.
Одной из основных концепций, которые очень важны для PF, является выборка по важности, которая представляет собой метод оценки распределения вероятностей по выборкам. Основная идея состоит в том, что, поскольку мы не знаем реального распределения, нам нужно брать выборку из распределения, которое, как ожидается, будет похоже на то, которое мы ищем, и придать большее значение выборкам, которые наиболее репрезентативны для реального распределения. распределение.
Конкретно, если мы хотим приблизиться к P (s), приблизительное значение P (s) - это количество частиц со значением s , что означает, что у многих из них будет P (s) = 0. Кроме того, мы будем взвешивать частицы в соответствии с вероятностью наблюдения фактического наблюдения с учетом состояния s, т. Е. w (s) = P (o | s) .
Из-за этого взвешивания вероятности не будут в сумме равняться единице, что важно, если мы хотим, чтобы веса представляли вероятности. Чтобы исправить это, мы можем либо нормализовать (т. Е. Изменить значения так, чтобы они равнялись единице), либо повторно дискретизировать частицы (рисование с заменой) в соответствии с весом, пока не получим общий вес, суммируя к одному. Это гарантирует, что частицы, которые наиболее репрезентативны для фактического распределения, будут иметь тенденцию выжить до следующей итерации, в то время как менее репрезентативные исчезнут. В конце концов, частица с наибольшей вероятностью будет содержать ожидаемое состояние.
Вот краткое изложение шагов, которые мы описали выше:
In order to predict the state of a system at time t do:
At step = 1:
(Since we have no idea what the real state of our system is, we throw particles everywhere, i.e., sample N particles according to the expected distribution):
Sample the possible initial states S_i following P(s_i|o_i)
Compute the weights w_i as a function of P(o_i|s_i)
Resample N particles according to w_i (i.e., particles with higher should be more likely to be selected)
At step > 1:
Compute the weights w_i as a function of P(o_i|s_i) for the current particles
Apply the transition model as a function of P(s_i+1|s_i)
Resample N particles according to w_i
Do this t steps and return the particle with the higher weight
Важно отметить, что на практике большая часть «волшебства» в обеспечении работы PF заключается в модели перехода и наблюдения. Вам нужно будет очень тщательно об этом подумать, чтобы получить наилучшие возможные результаты. В конкретном случае корректировки измерений GPS модель перехода должна кодировать, как объекты перемещаются с одной улицы на другую (например, если вы считаете, что автомобиль находится на углу 2-й улицы и 5-й авеню, какие множество возможных улиц, что такая же машина будет при следующем замере?). Аналогичным образом модель наблюдения должна кодировать то, что мы знаем о точности показаний GPS и фактических местоположениях (например, что фактическое местоположение может находиться в пределах 10-метрового радиуса).
Давайте рассмотрим небольшой пример, который определенно не требует использования фильтра твердых частиц, но поможет нам проиллюстрировать каждый из шагов, описанных выше. Представьте себе объект (маленький велоцираптор на рисунке 5), движущийся по сетке 2x2. Мы хотим отслеживать передвижения нашего динозавра каждый час. Мы знаем, что он может двигаться как угодно, но из предыдущих экспериментов (или из знаний, предоставленных известным экспертом по динозаврам доктором Аланом Грантом) мы замечаем, что он движется в основном по часовой стрелке. Кроме того, у нас есть нечеткая система видеонаблюдения, которая позволяет нам видеть, где сейчас находится динозавр, с некоторой известной ошибкой.
Мы только что описали модель перехода и наблюдения. В частности, предположим следующую модель перехода:
╔═════════════╦═══════╦═════════════╗ ║ Moving From ║ To ║ Probability ║ ╠═════════════╬═══════╬═════════════╣ ║ (0,0) ║ (0,1) ║ 0.8 ║ ║ (0,0) ║ (1,0) ║ 0.2 ║ ║ (0,1) ║ (1,1) ║ 0.8 ║ ║ (0,1) ║ (0,0) ║ 0.2 ║ ║ (1,1) ║ (1,0) ║ 0.8 ║ ║ (1,1) ║ (0,1) ║ 0.2 ║ ║ (1,0) ║ (0,0) ║ 0.8 ║ ║ (1,0) ║ (1,1) ║ 0.2 ║ ╚═════════════╩═══════╩═════════════╝ all other possible movements have a zero probability.
Модель наблюдения будет следующей: если объект находится в позиции (i, j), то мы получим наблюдение (i, j) с вероятностью 0,75, (i ', j) с 0,1, (i, j') с 0,1 и (i ', j') с 0,05. Индексы со штрихом относятся к любому значению, отличному от фактического индекса.
На шаге 1 мы не знаем, где находится динозавр, поэтому мы создадим по одной частице для каждой ячейки сетки с равной вероятностью (синие точки на рисунке 5). То есть:
s1 = (0,0) with w1 = 0.25 s2 = (0,1) with w2 = 0.25 s3 = (1,1) with w3 = 0.25 s4 = (1,0) with w4 = 0.25
где sᵢ - идентификатор частицы, а wᵢ - ее вес.
Наш датчик сообщает, что динозавр находится в точке (0,0) с вероятностью 0,75, в точке (0,1) с вероятностью 0,1, в точке (1,0) с 0,1 и в точке (1,1) с 0,05 (см. Рисунок 6). . Следовательно, когда мы применяем нашу модель сенсора, мы получаем следующие веса для каждой частицы:
Если нам нужны фактические вероятности, мы можем нормализовать значения, но в этом шаге нет необходимости. Этот результат в основном говорит нам, что мы считаем, что исходное местоположение нашего динозавра находится в точке (0,0). А теперь посмотрим, что произойдет через час…
На втором этапе мы будем сохранять только 3 частицы на каждую итерацию (на практике вы хотите оставить тысячи). В этом случае мы оставим s₁, s₂ и s₃ и забудем о s₄, а эти 3 частицы будут все, что мы получили из предыдущего шага.
Сначала мы предполагаем, что все три оставшиеся частицы имеют одинаковый вес, и поэтому для второго шага мы имеем:
s1 = (0,0) with w1 = 0.33 s2 = (0,1) with w2 = 0.33 s3 = (1,1) with w3 = 0.33
Теперь применим модель перехода, умножая вероятность перехода от ячейки, указанной в каждой оставшейся частице, к каждому возможному пункту назначения. Мы также можем сразу применить модель наблюдения, которая дает нам 0,75 для (0,1), 0,1 для (0,0), 0,1 для (1,1) и 0,05 для (1,0).
Следовательно, в этом случае мы получаем 6 возможных значений:
s11 = (0,0) to (0,1): w11 = 0.33*0.8*0.75=0.198 s12 = (0,0) to (1,0): w12 = 0.33*0.2*0.05=0.0033 s21 = (0,1) to (1,1): w21 = 0.33*0.8*0.1=0.0264 s22 = (0,1) to (0,0): w22 = 0.33*0.2*0.1=0.0066 s31 = (1,1) to (1,0): w31 = 0.33*0.8*0.1=0.0264 s32 = (1,1) to (0,1): w32 = 0.33*0.2*0.1=0.0066
Это означает, что наша система считает, что динозавр сейчас находится в ячейке (0,1) с вероятностью 0,74 (полученной после нормализации значений).
Если мы хотим продолжить отслеживание движения нашего динозавра, мы бы просто повторили последние шаги: отобрали 3 частицы из 6 выше (в зависимости от веса), применили функцию перехода и функцию наблюдения и продолжили бы по мере необходимости.
Приведенный выше пример может быть слишком упрощен, но на самом деле он не сильно отличается от корректировки местоположения автомобилей по GPS, просто представьте ячейки в сетке как фактические улицы, а наблюдения - как любую пару широты и долготы. Уловка (секретный соус Ай-инкуба) заключается в том, как мы определяем модели перехода и наблюдения.
Эта запись в блоге была задумана как быстрое введение в фильтры частиц. Можно сделать множество различных вариантов и оптимизаций, но общий принцип остается неизменным. Я надеюсь, что это проясняет и развлекает всех читателей.
