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

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?

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.

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.

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.

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).

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.

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.