Фильтры частиц: как сделать повторную выборку?

Я понял основной принцип фильтра частиц и попытался реализовать его. Тем не менее, я зациклился на части пересэмплирования.

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

Моя первая идея о том, как реализовать это, была, по сути, такой:

1. Нормализовать вес
2. Умножьте каждый вес на общее количество частиц
3. Округлите эти весы до ближайшего целого (например, с помощью int()в Python)

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

Вопрос: Как «заполнить» отсутствующие частицы, чтобы получить то же количество частиц, что и до шага повторной выборки? Или, если я совершенно не в курсе, как мне правильно сделать повторную выборку?

Проблема, с которой вы сталкиваетесь, часто называется пробным обнищанием. Мы можем видеть, почему ваш подход страдает от этого на довольно простом примере. Допустим, у вас есть 3 частицы, и их нормализованные веса равны 0,1, 0,1, 0,8. Затем умножение каждого веса на 3 дает 0,3, 0,3 и 2,4. Затем округление дает 0, 0, 2. Это означает, что вы не выберете первые две частицы, а последняя будет выбрана дважды. Теперь вы до двух частиц. Я подозреваю, что это то, что вы видели, когда говорите «из-за ошибок округления у меня в конечном итоге будет меньше частиц».

Альтернативный метод выбора будет следующим.

1. Нормализовать вес.
2. Рассчитать массив совокупной суммы весов.
3. Произвольно сгенерируйте число и определите, к какому диапазону в этом массиве совокупного веса принадлежит данное число.
4. Индекс этого диапазона будет соответствовать частице, которая должна быть создана.
5. Повторяйте, пока не получите желаемое количество образцов.

Итак, используя приведенный выше пример, мы начнем с нормализованных весов. Затем мы вычислим массив [0,1, 0,2, 1]. Оттуда мы вычисляем 3 случайных числа, скажем, 0,15, 0,38 и 0,54. Это заставило бы нас выбрать вторую частицу один раз, а третью - дважды. Дело в том, что это дает мелким частицам возможность размножаться.

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

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

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

• Полиномиальная повторная выборка: представьте полоску бумаги, где каждая частица имеет сечение, длина которого пропорциональна ее весу. Случайно выберите место на полосе N раз и выберите частицу, связанную с разрезом.

• Остаточная повторная выборка: этот подход пытается уменьшить дисперсию выборки, сначала выделяя каждой частице их целое минимальное значение ожидаемого значения, а оставшуюся часть оставляют для многочленной повторной выборки. Например, частица с ожидаемым значением 2,5 будет иметь 2 копии в наборе с измененной выборкой и еще одну с ожидаемым значением 0,5.

• Систематическая повторная выборка: возьмите линейку с правильными разнесенными отметками, так чтобы отметки N имели ту же длину, что и ваша полоска бумаги. Случайно поместите линейку рядом с вашей полосой. Возьмите частицы на отметках.

• Стратифицированная повторная выборка: такая же, как и систематическая повторная выборка, за исключением того, что метки на линейке размещаются неравномерно, а добавляются как N случайных выборочных процессов из интервала 0..1 / N

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

Для примера кода Python, который правильно реализует повторную выборку, вы можете найти этот проект github полезным: https://github.com/mjl/particle_filter_demo

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

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

Один простой способ сделать это - numpy.random.choice (N, N, p = w, replace = True), где N - нет. частиц и W = нормализованные веса.

Я использую подход @ narayan для реализации моего фильтра частиц:

new_sample = numpy.random.choice(a=particles, size=number_of_particles, replace=True, p=importance_weights)

a - вектор ваших частиц для выборки, размер - количество частиц, а p - вектор их нормализованных весов. replace = True обрабатывает выборку начальной загрузки с заменой. Возвращаемым значением является вектор новых объектов частиц.