Filtros de partículas: ¿cómo hacer un muestreo?

24

Entiendo el principio básico de un filtro de partículas e intenté implementar uno. Sin embargo, me colgué en la parte de remuestreo.

Teóricamente hablando, es bastante simple: del conjunto de partículas antiguo (y ponderado), dibuje un nuevo conjunto de partículas con reemplazo. Al hacerlo, favorezca las partículas que tienen pesos altos. Las partículas con pesos altos se extraen con mayor frecuencia y las partículas con pesos bajos con menos frecuencia. Quizás solo una vez o nada en absoluto. Después de volver a muestrear, a todos los pesos se les asigna el mismo peso.

Mi primera idea sobre cómo implementar esto fue esencialmente esto:

  1. Normaliza los pesos
  2. Multiplique cada peso por el número total de partículas.
  3. Redondee esos pesos escalados al número entero más cercano (por ejemplo, con int()Python)

Ahora debería saber con qué frecuencia dibujar cada partícula, pero debido a los errores de redondeo, termino teniendo menos partículas que antes del paso de remuestreo.

La pregunta: ¿Cómo puedo "llenar" las partículas que faltan para llegar al mismo número de partículas que antes del paso de remuestreo? O, en caso de que esté completamente fuera de lugar aquí, ¿cómo puedo volver a muestrear correctamente?

Daniel Eberts
fuente

Respuestas:

19

El problema con el que se encuentra a menudo se conoce como empobrecimiento de la muestra. Podemos ver por qué su enfoque lo padece con un ejemplo bastante simple. Digamos que tiene 3 partículas y sus pesos normalizados son 0.1, 0.1, 0.8. Luego, multiplicando por cada peso por los 3 rendimientos 0.3, 0.3 y 2.4. Luego, el redondeo produce 0, 0, 2. Esto significa que no elegiría las dos primeras partículas y la última se recogería dos veces. Ahora tienes dos partículas. Sospecho que esto es lo que has estado viendo cuando dices "debido a los errores de redondeo, termino teniendo menos partículas".

Un método de selección alternativo sería el siguiente.

  1. Normalizar pesas.
  2. Calcule una matriz de la suma acumulativa de los pesos.
  3. Genere aleatoriamente un número y determine qué rango en esa matriz de peso acumulativo al que pertenece el número.
  4. El índice de ese rango correspondería a la partícula que debería crearse.
  5. Repita hasta que tenga el número deseado de muestras.

Entonces, usando el ejemplo anterior, comenzaríamos con los pesos normalizados. Luego calcularíamos la matriz [0.1, 0.2, 1]. A partir de ahí, calculamos 3 números aleatorios, digamos 0.15, 0.38 y 0.54. Esto nos haría elegir la segunda partícula una vez y la tercera partícula dos veces. El punto es que le da a las partículas más pequeñas la oportunidad de propagarse.

Una cosa a tener en cuenta es que, si bien este método tratará el empobrecimiento, puede conducir a soluciones subóptimas. Por ejemplo, puede ser que ninguna de las partículas coincida realmente con su ubicación dada (suponiendo que esté usando esto para la localización). Los pesos solo le dicen qué partículas coinciden mejor, no la calidad de la coincidencia. Como tal, cuando toma lecturas adicionales y repite el proceso, puede encontrar que todas sus partículas se agrupan en una sola ubicación que no es la ubicación correcta. Esto generalmente se debe a que no había buenas partículas para comenzar.

DaemonMaker
fuente
1
Gracias por la perspicaz respuesta! El método de selección que sugirió parece familiar. Si no recuerdo mal, esa era una forma común de tratar el problema de empobrecimiento de la muestra. Lo he visto antes, pero nunca entendí realmente la razón de este procedimiento. Ahora lo se mejor!
Daniel Eberts
2
Creo que su interpretación del empobrecimiento del muestreo puede ser un poco engañosa. El hecho de que el póster pierda partículas se debe a un método inadecuado para volver a muestrear. El empobrecimiento de partículas es cuando su distribución posterior ya no está representada adecuadamente por las partículas.
Jakob
9

Como supongo que lo descubrió usted mismo, el método de remuestreo que está proponiendo es ligeramente defectuoso, ya que no debería alterar el número de partículas (a menos que lo desee). El principio es que el peso representa la probabilidad relativa con respecto a las otras partículas. En el paso de remuestreo, extrae del conjunto de partículas de manera que, para cada partícula, el peso normalizado multiplicado por el número de partículas representa el número de veces que esa partícula se extrae en promedio. En eso tu idea es correcta. Solo utilizando el redondeo en lugar del muestreo, siempre eliminará las partículas cuyo valor esperado sea inferior a la mitad.

Hay varias formas de realizar el remuestreo correctamente. Hay un buen artículo llamado Sobre algoritmos de remuestreo para filtros de partículas , que compara los diferentes métodos. Solo para dar una visión general rápida:

  • Muestreo multinomial: imagine una tira de papel donde cada partícula tiene una sección, donde la longitud es proporcional a su peso. Elija aleatoriamente una ubicación en la tira N veces, y elija la partícula asociada con la sección.

  • Muestreo residual: este enfoque intenta reducir la varianza del muestreo, asignando primero a cada partícula su piso entero del valor esperado, y deja el resto a un muestreo multinomial. Por ejemplo, una partícula con un valor esperado de 2.5 tendrá 2 copias en el conjunto muestreado y otra con un valor esperado de 0.5.

  • Muestreo sistemático: tome una regla con marcas espaciadas regulares, de modo que las marcas N tengan la misma longitud que su tira de papel. Coloca al azar la regla al lado de tu tira. Toma las partículas en las marcas.

  • Muestreo estratificado: igual que el muestreo sistemático, excepto que las marcas en la regla no se colocan de manera uniforme, sino que se agregan como N procesos aleatorios de muestreo del intervalo 0..1 / N.

Entonces, para responder a su pregunta: lo que ha implementado podría extenderse a una forma de muestreo residual. Rellena los espacios faltantes mediante un muestreo basado en una distribución multinonmial de los recordatorios.

Jakob
fuente
+1 por haber respondido mi pregunta de seguimiento :)
Daniel Eberts
5

Para ver un ejemplo de código de Python que implementa correctamente el remuestreo, puede encontrar útil este proyecto github: https://github.com/mjl/particle_filter_demo

Además, viene con su propia representación visual del proceso de remuestreo, que debería ayudarlo a depurar su propia implementación. Operación de filtro de partículas

En esta visualización, la tortuga verde muestra la posición real, el gran punto gris muestra la posición estimada y se vuelve verde cuando converge. El peso va de probable (rojo) a improbable (azul).

Ian
fuente
Gracias por el enlace. Siempre es perspicaz ver cómo otras personas implementaron un algoritmo.
Daniel Eberts
Esta es una visualización de un filtro de partículas convergente. No estoy seguro de qué información proporciona con respecto a la pregunta.
Jakob
Incluí la visualización ya que es lo que produce el código que publiqué, un ejemplo de cómo implementar correctamente el remuestreo.
Ian
1

Una forma simple de hacer esto es numpy.random.choice (N, N, p = w, replace = True) donde N es el no. de partículas yw = pesos normalizados.

narayan
fuente
Bienvenido a Robotics , narayan. ¿Podría por favor ampliar esta respuesta un poco? Por ejemplo, ¿por qué usar una elección aleatoria? ¿Qué hay pen tu función? Cuanto más detallado sea su respuesta, más útil será para los futuros visitantes que tengan el mismo problema.
Chuck
1

Utilizo el enfoque de @ narayan para implementar mi filtro de partículas:

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

a es el vector de sus partículas para muestrear, el tamaño es el recuento de partículas y p es el vector de sus pesos normalizados. replace = True maneja el muestreo bootstrap con reemplazo. El valor de retorno es un vector de nuevos objetos de partículas.

Raja
fuente