Filtry cząstek: jak wykonać ponowne próbkowanie?

Rozumiem podstawową zasadę filtra cząstek i próbowałem go wdrożyć. Jednak rozłączyłem się w części dotyczącej ponownego próbkowania.

Teoretycznie jest to dość proste: ze starego (i ważonego) zestawu cząstek narysuj nowy zestaw cząstek z zamiennikiem. Czyniąc to, faworyzuj te cząsteczki, które mają duże ciężary. Cząstki o wysokiej masie są częściej rysowane, a cząstki o niskiej masie rzadziej. Być może tylko raz lub wcale. Po ponownym próbkowaniu wszystkie ciężary mają taką samą wagę.

Mój pierwszy pomysł, jak to zaimplementować, był zasadniczo następujący:

1. Normalizuj wagi
2. Pomnóż każdą masę przez całkowitą liczbę cząstek
3. Zaokrąglij te wyskalowane wagi do najbliższej liczby całkowitej (np. int()W Pythonie)

Teraz powinienem wiedzieć, jak często rysować każdą cząstkę, ale z powodu błędów zaokrągleń, w końcu mam mniej cząstek niż przed krokiem ponownego próbkowania.

Pytanie: Jak „uzupełnić” brakujące cząstki, aby uzyskać taką samą liczbę cząstek jak przed etapem ponownego próbkowania? Lub, w przypadku, gdy jestem całkowicie nie na miejscu, w jaki sposób poprawnie przeskalować?

Problem, na który napotykasz, jest często określany jako zubożenie próbki. Możemy zrozumieć, dlaczego cierpi na to twoje podejście, na dość prostym przykładzie. Załóżmy, że masz 3 cząstki, a ich znormalizowane wagi to 0,1, 0,1, 0,8. Następnie pomnożenie przez każdą wagę przez 3 daje 0,3, 0,3 i 2,4. Następnie zaokrąglenie daje 0, 0, 2. Oznacza to, że nie wybrałbyś dwóch pierwszych cząstek, a ostatni zostałby wybrany dwa razy. Teraz masz dwie cząstki. Podejrzewam, że to właśnie widziałeś, kiedy mówiłeś „z powodu błędów zaokrągleń, w końcu mam mniej cząstek”.

Alternatywna metoda selekcji byłaby następująca.

1. Normalizuj ciężary.
2. Oblicz tablicę skumulowanej sumy wag.
3. Generuj losowo liczbę i określ zakres w tej skumulowanej tablicy wag, do której należy liczba.
4. Indeks tego zakresu odpowiadałby cząsteczce, którą należy utworzyć.
5. Powtarzaj, aż uzyskasz żądaną liczbę próbek.

Korzystając z powyższego przykładu, zaczniemy od znormalizowanych wag. Następnie obliczylibyśmy tablicę [0,1, 0,2, 1]. Stamtąd obliczamy 3 liczby losowe: 0,15, 0,38 i 0,54. To sprawiłoby, że wybraliśmy drugą cząstkę raz, a trzecią cząstkę dwa razy. Chodzi o to, że daje szansę mniejszym cząsteczkom na propagację.

Należy zauważyć, że chociaż ta metoda poradzi sobie z zubożeniem, może prowadzić do nieoptymalnych rozwiązań. Na przykład może się zdarzyć, że żadna cząsteczka nie pasuje dobrze do podanej lokalizacji (zakładając, że używasz tego do lokalizacji). Masy mówią tylko, które cząstki pasują najlepiej, a nie jakość dopasowania. W związku z tym, gdy wykonasz dodatkowe odczyty i powtórzysz proces, może się okazać, że wszystkie twoje cząstki grupują się w jednym miejscu, które nie jest poprawnym miejscem. Dzieje się tak zwykle dlatego, że nie było dobrych cząstek na początek.

Jak sądzę, sam się przekonałeś, proponowana przez ciebie metoda ponownego próbkowania jest nieco wadliwa, ponieważ nie powinna zmieniać liczby cząstek (chyba że chcesz). Zasadą jest, że ciężar reprezentuje względne prawdopodobieństwo w odniesieniu do innych cząstek. W kroku ponownego próbkowania rysujesz z zestawu cząstek tak, że dla każdej cząstki znormalizowana waga razy liczba cząstek reprezentuje liczbę średnich pobrań cząstki. Pod tym względem twój pomysł jest poprawny. Tylko za pomocą zaokrąglania zamiast próbkowania zawsze wyeliminujesz cząstki, dla których oczekiwana wartość jest mniejsza niż połowa.

Istnieje wiele sposobów prawidłowego przeprowadzenia ponownego próbkowania. Jest ładny artykuł o algorytmach ponownego próbkowania filtrów cząstek , porównujący różne metody. Aby dać szybki przegląd:

• Ponowne próbkowanie wielomianowe: wyobraź sobie pasek papieru, w którym każda cząstka ma przekrój, którego długość jest proporcjonalna do jego ciężaru. Losowo wybierz lokalizację na pasku N razy i wybierz cząstkę związaną z sekcją.

• Resztkowe ponowne próbkowanie: to podejście stara się zmniejszyć wariancję próbkowania, najpierw przydzielając każdej cząsteczce ich dolną liczbę całkowitą o oczekiwanej wartości, a resztę pozostawiając do wielomianowego ponownego próbkowania. Np. Cząstka o oczekiwanej wartości 2,5 będzie miała 2 kopie w zestawie ponownie próbkowanym, a druga o oczekiwanej wartości 0,5.

• Systematyczne ponowne próbkowanie: weź linijkę o regularnych odstępach, tak aby znaki N miały taką samą długość jak pasek papieru. Losowo umieść linijkę obok paska. Weź cząstki za znaki.

• Ponowne próbkowanie warstwowe: to samo co ponowne próbkowanie systematyczne, z tym wyjątkiem, że znaczniki na linijce nie są równomiernie rozmieszczone, ale dodawane jako N losowych procesów próbkowania z przedziału 0..1 / N.

Aby odpowiedzieć na twoje pytanie: to, co wdrożyłeś, można rozszerzyć na formę próbkowania resztkowego. Uzupełniasz brakujące miejsca, próbkując w oparciu o wielomianowy rozkład przypomnień.

Na przykład kodu python, który poprawnie implementuje resampling, może okazać się przydatny ten projekt github: https://github.com/mjl/particle_filter_demo

Ponadto zawiera własną wizualną reprezentację procesu ponownego próbkowania, która powinna pomóc w debugowaniu własnej implementacji.

W tej wizualizacji zielony żółw pokazuje rzeczywistą pozycję, duża szara kropka pokazuje oszacowaną pozycję i zmienia kolor na zielony, gdy się zbiega. Waga zmienia się z prawdopodobnej (czerwonej) na mało prawdopodobną (niebieską).

jednym prostym sposobem na to jest numpy.random.choice (N, N, p = w, replace = True), gdzie N jest nie. cząstek i w = znormalizowane masy.

Używam podejścia @ narayan do implementacji mojego filtra cząstek:

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

a jest wektorem cząstek do pobrania próbki, rozmiar jest liczbą cząstek, a p jest wektorem ich znormalizowanych wag. replace = True obsługuje próbkowanie bootstrap z wymianą. Zwracana wartość to wektor nowych obiektów cząstek.