Outlier-robust Autocovariance Least Square Estimation via Iteratively Reweighted Least Square

Dit artikel introduceert ALS-IRLS, een robuust algoritme dat de autocovariantie-kleinstekwadratenmethode voor Kalman-filterruis schatting uitbreidt met een tweestaps-strategie op basis van iteratief hergewogen kleinstekwadraten en Huber-kostfuncties om extreme uitbijters effectief te filteren en de schattingsnauwkeurigheid aanzienlijk te verbeteren.

De kern

Stel je voor dat je een zeer slimme, maar soms verwarde navigator hebt die een auto bestuurt. Deze navigator (de Kalman-filter) probeert te voorspellen waar de auto op elk moment is, zelfs als de weg hobbelig is of als de GPS-signalen soms storen.

Om dit goed te doen, moet de navigator twee dingen weten:

1. Hoe onvoorspelbaar de auto zelf is (bijvoorbeeld: hoe vaak stuitert hij op een kassei?). Dit noemen we procesruis.
2. Hoe onbetrouwbaar de GPS-metingen soms zijn. Dit noemen we meetruis.

In de echte wereld weten we deze "ruis" vaak niet precies. We moeten ze dus schatten terwijl we rijden. De oude methode (ALS) deed dit door naar een groot aantal metingen te kijken en een gemiddelde te nemen.

Het Probleem: De "Vreemde Gast"

Stel je voor dat je een klasje kinderen vraagt om hun lengte te meten om het gemiddelde te bepalen.

• De meeste kinderen meten correct.
• Maar plotseling staat er één kind dat op een krukje staat en een hoed op heeft, en zegt dat hij 3 meter lang is.

De oude methode (ALS) zou dit ene, absurde getal meenemen in de berekening. Het gemiddelde springt dan enorm omhoog, en de navigator denkt: "Oh, deze auto is gigantisch groot!" Hierdoor raakt de navigator volledig de weg kwijt. In de technische taal noemen we deze fouten uitbijters (outliers).

De Oplossing: ALS-IRLS (De Slimme Chef)

De auteurs van dit paper hebben een nieuwe, slimmere methode bedacht, genaamd ALS-IRLS. Ze gebruiken een twee-stappen strategie om die "krukje-dragende kinderen" te negeren.

Stap 1: De Strikte Doorman (Innovatie-drempel)

Voordat de data überhaupt in de rekenmachine terechtkomt, passeert het eerst een strenge doorman.

• De navigator kijkt naar elke nieuwe meting.
• Als een meting te gek is (bijvoorbeeld: "De auto staat plotseling 100 meter naar links"), zegt de doorman: "Stop! Dit is onzin, dit is een fout van de sensor."
• Deze extreme metingen worden direct weggegooid voordat ze het gemiddelde kunnen verstoren.
• Analogie: Het is alsof je de krukjes en hoeden van de kinderen afpakt voordat je de meting doet.

Stap 2: De Slimme Rekenmachine (Iteratief Herwegen)

Stel dat er nog steeds een paar kinderen zijn die iets te hoog of te laag meten, maar niet zo gek dat de doorman ze direct weggooit. De oude methode zou ze allemaal even zwaar laten tellen.
De nieuwe methode (IRLS) werkt als een slimme chef die een soep kookt:

1. Hij proeft de soep (de eerste berekening).
2. Hij ziet dat er een paar stukjes groente zijn die de smaak verstoren.
3. In plaats van ze eruit te halen, vermindert hij de hoeveelheid van die specifieke stukjes groente in de volgende ronde.
4. Hij herhaalt dit proces steeds opnieuw. Bij elke ronde worden de "verkeerde" metingen steeds minder belangrijk, terwijl de "goede" metingen het gewicht krijgen.
5. Uiteindelijk zijn de verkeerde metingen zo klein geworden dat ze de smaak van de soep (de berekening) niet meer beïnvloeden.

Waarom is dit zo geweldig?

In de simulaties die de auteurs hebben gedaan, bleek dit systeem wonderen te doen:

1. Ongeëvenaarde Nauwkeurigheid: Waar de oude methode de ruis-schattingen soms 100 keer te hoog of te laag maakte, zat de nieuwe methode binnen 1% van de waarheid. Het is alsof de navigator plotseling niet meer droomt, maar perfect ziet.
2. Robuustheid: Zelfs als 30% van de metingen foutief waren (bijvoorbeeld door een storing in de GPS), bleef de nieuwe methode werken. De oude methode gaf in zo'n geval volledig de geest.
3. Beter dan andere slimme filters: Er bestaan al andere methoden die proberen om fouten te negeren (zoals de "Student-t" filter of de "MCKF"). Maar deze nieuwe methode werkt beter, vooral omdat hij eerst de basis (de ruis-schatting) perfect maakt, in plaats van alleen maar te proberen de fouten onderweg te verbergen.

Conclusie

Kortom: Dit paper introduceert een manier om een navigatiesysteem te bouwen dat niet zomaar door één gekke meting in paniek raakt. Door eerst de duidelijkste fouten weg te filteren en daarna slim de rest van de data te "gewichten", krijgt de navigator een kristalhelder beeld van de werkelijkheid.

Het resultaat? Een auto (of robot, of drone) die zich ook in stormachtig weer en met een kapotte GPS nog steeds perfect op de weg houdt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Outlier-robust Autocovariance Least Square Estimation via Iteratively Reweighted Least Square" in het Nederlands.

Titel: Outlier-robuste Autocovariantie-Kwadratische Schatting via Iteratief Herweegt Kwadratische Middelste (IRLS)

Auteurs: Jiahong Li en Fang Deng

---

1. Probleemstelling

De Kalman-filter (KF) is de optimale schatter voor lineaire tijd-invariante (LTI) systemen met Gaussisch ruis, mits de ruiscovariantiematrices van het proces ($Q$) en de meting ($R$) bekend zijn. In de praktijk zijn deze statistieken vaak onbekend of onnauwkeurig, wat leidt tot een degradatie van de filterprestaties.

De Autocovariantie-Kwadratische Middelste (ALS) methode is een efficiënte techniek om $Q$ en $R$ te schatten zonder specifieke ruismodellen, door gebruik te maken van de autocovariantie van de innovaties (residuen). Echter, de klassieke ALS-methode en zijn varianten vertrouwen op het Least Mean Squares (LMS) criterium ($\ell_2$-norm). Dit maakt ze extreem gevoelig voor uitbijters (outliers) in meetdata (veroorzaakt door sensorfouten of externe storingen). Zelfs een klein percentage uitbijters kan de schatting van de covariantie volledig verstoren, wat resulteert in ernstige prestatieverlies van de Kalman-filter. Bestaande robuuste Kalman-filters (ORKF) lossen dit vaak op door de filterupdate aan te passen, maar verwaarlozen vaak de noodzaak van nauwkeurige online schatting van de onderliggende ruisstatistieken.

2. Methodologie: ALS-IRLS

Het paper introduceert een nieuw algoritme, ALS-IRLS, dat de gevoeligheid voor uitbijters oplost door een twee-traps robuustheidsstrategie te implementeren binnen het ALS-raamwerk:

1. Innovatie-niveau adaptieve drempelwaarde (Hard Filtering):

   • Voordat de autocovariantie wordt berekend, worden de innovaties ($e_k$) geanalyseerd.
   • Een robuuste schaalindicator, gebaseerd op de MAD (Median Absolute Deviation), wordt gebruikt om een dynamische drempel te bepalen.
   • Innovaties die deze drempel overschrijden (zwaar vervuild data) worden direct verwijderd uit de dataset. Dit voorkomt dat extreme waarden de autocovariantie-matrix verstoren.

2. IRLS met Huber-kostfunctie (Soft Down-weighting):

   • Voor de resterende data wordt het schattingsprobleem geformuleerd als een robuuste regressie in plaats van standaard lineaire regressie.
   • Het klassieke LMS-criterium wordt vervangen door de Huber-kostfunctie, die een kwadratische straal voor kleine fouten en een lineaire straal voor grote fouten gebruikt.
   • Het Iteratief Herweegt Kwadratische Middelste (IRLS) algoritme wordt toegepast. Dit algoritme lost iteratief een gewogen kwadratische middelste probleem op, waarbij de gewichten voor elke datapunt worden aangepast op basis van de residuen.
   • Datapunten met grote afwijkingen krijgen een lager gewicht, waardoor de invloed van resterende uitbijters wordt geminimaliseerd zonder de structuur van de autocovariantie te verstoren.

Wiskundige Formulering:
Het probleem wordt herschreven als het minimaliseren van een robuuste kostfunctie:
$$\theta^* = \arg \min_{\theta} \sum_{i=1}^n \rho(r_i(\theta))$$
waarbij $\rho(\cdot)$ de Huber-verliesfunctie is en $r_i$ het residu. De IRLS-stap update de gewichten $w_i$ iteratief volgens:
$$w_i^{(t)} = \begin{cases} 1 & \text{als } |r_i| \le \delta \\ \delta / |r_i| & \text{als } |r_i| > \delta \end{cases}$$

3. Belangrijkste Bijdragen

1. Koppeling tussen Robuuste Regressie en ALS: De auteurs leggen een theoretische link tussen outlier-robuste regressie en ALS-door het vervangen van de $\ell_2$-norm door de Huber-criteria ($\ell_p$-norm), waardoor het schattingsprobleem van ruiscovariantie wordt omgezet in een robuust regressieprobleem.
2. Ontwikkeling van ALS-IRLS: Een nieuw algoritme dat IRLS combineert met een tweestapsstrategie (verwijdering op innovatie-niveau + gewogen regressie). Dit biedt flexibiliteit en past zich aan aan de data-distributie.
3. Convergentie en Complexiteit: Het paper bewijst de convergentie van het algoritme naar een uniek globaal minimum onder bepaalde voorwaarden en analyseert de rekencomplexiteit, die vergelijkbaar is met standaard ALS maar dan vermenigvuldigd met het aantal IRLS-iteraties.

4. Resultaten (Simulaties)

De prestaties zijn getest via Monte Carlo-simulaties op een lineair tijd-invariant systeem met $\epsilon$-vervuiling (waarbij 15% van de metingen vervuild is met grote uitbijters).

• Nauwkeurigheid Covariantieschatting:

  • Standaard ALS faalt volledig: de Root Mean Square Error (RMSE) voor $Q$ en $R$ is extreem hoog (bijna 100x de werkelijke waarde) door de invloed van de uitbijters.
  • ALS-IRLS reduceert de RMSE met meer dan twee ordes van grootte (van ~48.5 naar ~0.38 voor $Q$). De geschatte waarden liggen binnen 1% van de werkelijke covarianties.
  • Het algoritme blijft robuust zelfs bij vervuilingssnelheden tot 30%.

• State Estimation (Filterprestaties):

  • De Kalman-filter die gebruikmaakt van de ALS-IRLS-schattingen bereikt een state-estimation RMSE die slechts 9% afwijkt van de "Oracle" ondergrens (de ideale filter met perfecte kennis van $Q$ en $R$).
  • Vergelijking met bestaande robuuste filters (Student-t KF en Maximum Correntropy KF): Deze filters presteren aanzienlijk slechter (2.3x tot 3.5x hogere RMSE) omdat ze vaak werken met verkeerd gespecificeerde, vaste covarianties.
  • Conclusie: Een nauwkeurige online schatting van de ruisstatistieken (via ALS-IRLS) levert grotere prestatiewinst op dan alleen het toepassen van robuuste update-mechanismen in de filter.

5. Betekenis en Conclusie

Dit paper demonstreert dat het oplossen van het probleem van onbekende ruisstatistieken in aanwezigheid van uitbijters cruciaal is voor de prestaties van Kalman-filters. De voorgestelde ALS-IRLS-methode biedt een elegante oplossing die de rekenkundige eenvoud van de klassieke ALS-methode behoudt, maar deze robuust maakt tegen extreme data-afwijkingen.

De twee-traps aanpak (hard filtering van innovaties gevolgd door soft down-weighting via IRLS) zorgt ervoor dat het algoritme een breakdown-punt van 50% bereikt (theoretisch maximum voor robuuste schatters). De resultaten tonen aan dat het herwinnen van nauwkeurige covarianties essentieel is en dat dit een grotere impact heeft op de algehele filternauwkeurigheid dan het alleen aanpassen van de filter-update voor uitbijters. Toekomstig werk richt zich op het uitbreiden naar niet-lineaire systemen en het aanpassen van drempels voor niet-stationaire ruis.