Filter partikel: Bagaimana cara melakukan resampling?

Saya memahami prinsip dasar filter partikel dan mencoba menerapkannya. Namun, saya terpaku pada bagian resampling.

Secara teori, ini cukup sederhana: Dari set partikel lama (dan berbobot), gambarkan set partikel baru dengan penggantian. Sambil melakukannya, nikmatilah partikel-partikel yang memiliki bobot tinggi. Partikel dengan bobot tinggi lebih sering ditarik dan partikel dengan bobot rendah lebih jarang. Mungkin hanya sekali atau tidak sama sekali. Setelah resampling, semua bobot diberi bobot yang sama.

Ide pertama saya tentang bagaimana mengimplementasikan ini pada dasarnya adalah ini:

1. Menormalkan bobot
2. Lipat gandakan setiap bobot dengan jumlah total partikel
3. Bulatkan bobot yang diskalakan ke bilangan bulat terdekat (mis. Dengan dengan int()Python)

Sekarang saya harus tahu seberapa sering menggambar setiap partikel, tetapi karena kesalahan pembulatannya, saya akhirnya memiliki lebih sedikit partikel daripada sebelum langkah resampling.

Pertanyaan: Bagaimana cara saya "mengisi" partikel yang hilang untuk mendapatkan jumlah partikel yang sama seperti sebelum langkah resampling? Atau, kalau-kalau saya benar-benar keluar jalur di sini, bagaimana saya melakukan resample dengan benar?

Masalah yang Anda hadapi sering disebut sebagai pemiskinan sampel. Kita dapat melihat mengapa pendekatan Anda menderita dengan contoh yang cukup sederhana. Katakanlah Anda memiliki 3 partikel dan bobotnya yang dinormalisasi adalah 0,1, 0,1, 0,8. Kemudian mengalikan dengan masing-masing berat dengan 3 menghasilkan 0,3, 0,3, dan 2,4. Kemudian pembulatan menghasilkan 0, 0, 2. Ini berarti Anda tidak akan memilih dua partikel pertama dan yang terakhir akan dipetik dua kali. Sekarang Anda tinggal dua partikel. Saya menduga ini adalah apa yang Anda lihat ketika Anda mengatakan "karena kesalahan pembulatan, saya akhirnya memiliki lebih sedikit partikel."

Metode pemilihan alternatif adalah sebagai berikut.

1. Menormalkan bobot.
2. Hitung array jumlah kumulatif bobot.
3. Secara acak menghasilkan angka & menentukan rentang mana dalam array bobot kumulatif yang dimiliki nomor tersebut.
4. Indeks rentang itu akan sesuai dengan partikel yang harus dibuat.
5. Ulangi sampai Anda memiliki jumlah sampel yang diinginkan.

Jadi, dengan menggunakan contoh di atas kita akan mulai dengan bobot yang dinormalisasi. Kami kemudian akan menghitung array [0,1, 0,2, 1]. Dari sana kita menghitung 3 angka acak katakan 0,15, 0,38, dan 0,54. Ini akan membuat kita memilih partikel kedua satu kali dan partikel ketiga dua kali. Intinya adalah memberi partikel yang lebih kecil peluang untuk berkembang biak.

Satu hal yang perlu diperhatikan adalah bahwa sementara metode ini akan menangani pemiskinan, ia dapat mengarah pada solusi yang kurang optimal. Misalnya, mungkin tidak ada partikel yang benar-benar cocok dengan lokasi Anda dengan baik (dengan asumsi Anda menggunakan ini untuk pelokalan). Bobot hanya memberi tahu Anda partikel mana yang paling cocok, bukan kualitas kecocokan. Dengan demikian ketika Anda mengambil bacaan tambahan dan mengulangi prosesnya, Anda mungkin menemukan bahwa semua partikel Anda mengelompokkan pada satu lokasi yang bukan lokasi yang benar. Ini biasanya karena tidak ada partikel yang baik untuk memulai.

Seperti yang saya kira Anda tahu sendiri, metode resampling yang Anda usulkan sedikit cacat, karena seharusnya tidak mengubah jumlah partikel (kecuali jika Anda mau). Prinsipnya adalah berat mewakili probabilitas relatif terhadap partikel lain. Pada langkah resampling, Anda menggambar dari himpunan partikel sedemikian rupa sehingga untuk setiap partikel, berat dinormalisasi kali jumlah partikel mewakili berapa kali rata-rata partikel digambar. Dalam hal itu ide Anda benar. Hanya dengan menggunakan pembulatan alih-alih pengambilan sampel, Anda akan selalu menghilangkan partikel yang nilainya kurang dari setengahnya.

Ada sejumlah cara untuk melakukan resampling dengan benar. Ada sebuah makalah yang bagus yang disebut pada resampling algoritma untuk filter partikel , membandingkan berbagai metode. Hanya untuk memberikan gambaran singkat:

• Resampling multinomial: bayangkan selembar kertas di mana setiap partikel memiliki bagian, di mana panjangnya sebanding dengan beratnya. Pilih lokasi secara acak pada jalur N kali, dan pilih partikel yang terkait dengan bagian tersebut.

• Resampling residual: pendekatan ini mencoba mengurangi varians pengambilan sampel, dengan terlebih dahulu mengalokasikan masing-masing partikel bilangan bulat dari nilai yang diharapkan, dan membiarkan sisanya untuk multinomial resampling. Misalnya suatu partikel dengan nilai yang diharapkan dari 2,5 akan memiliki 2 salinan dalam set yang di-resampled dan yang lainnya dengan nilai yang diharapkan dari 0,5.

• Resampling sistematis: ambil penggaris dengan tanda spasi reguler, sehingga tanda N sama panjangnya dengan potongan kertas Anda. Secara acak letakkan penggaris di sebelah strip Anda. Ambil partikel pada tanda.

• Resampling bertingkat: sama dengan resampling sistematis, kecuali bahwa tanda pada penggaris tidak ditempatkan secara merata, tetapi ditambahkan sebagai N proses pengambilan sampel acak dari interval 0..1 / N.

Jadi untuk menjawab pertanyaan Anda: apa yang telah Anda implementasikan dapat diperluas ke bentuk residual sampling. Anda mengisi slot yang hilang dengan mengambil sampel berdasarkan distribusi multinonmial dari pengingat.

Untuk contoh kode python yang mengimplementasikan resampling dengan benar, Anda mungkin menemukan proyek github ini berguna: https://github.com/mjl/particle_filter_demo

Plus, ia hadir dengan representasi visualnya sendiri dari proses resampling, yang seharusnya membantu Anda men-debug implementasi Anda sendiri.

Dalam visualisasi ini, penyu hijau menunjukkan posisi sebenarnya, titik abu-abu besar menunjukkan posisi yang diperkirakan dan berubah menjadi hijau ketika konvergen. Bobotnya berubah dari kemungkinan (merah) menjadi tidak mungkin (biru).

satu cara sederhana untuk melakukan ini adalah numpy.random.choice (N, N, p = w, ganti = True) di mana N adalah no. partikel dan w = bobot dinormalisasi.

Saya menggunakan pendekatan @ narayan untuk mengimplementasikan filter partikel saya:

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

a adalah vektor partikel Anda untuk sampel, ukuran adalah jumlah partikel dan p adalah vektor bobot dinormalisasi. replace = True menangani pengambilan sampel bootstrap dengan penggantian. Nilai kembali adalah vektor objek partikel baru.