Online semi-supervised perception: Real-time learning without explicit feedback

1. Probleemdefinitie

Het artikel behandelt de uitdaging van online semi-supervised learning in real-time omgevingen waar expliciete feedback (ware labels) schaars is of niet beschikbaar na de initiële opstelling.

• De Setting: Het systeem opereert in een herhalend spel tegen een potentieel adversariale omgeving. Op elk tijdstip $t$ observeert het algoritme een voorbeeld $x_t$ en moet het de label $\hat{y}_t$ voorspellen.
• De Beperking: Ware labels $y_t$ worden zelden geobserveerd. Het algoritme moet vertrouwen op indirecte feedback, specifiek de onderliggende manifoldstructuur van de data, om zich aan te passen aan veranderingen in de omgeving.
• Het Doel: Het bouwen van een adaptief leeralgoritme dat start met een kleine set offline gelabelde voorbeelden (initiële bias) en continu zijn model bijwerkt met een stroom van ongelabelde data om hoge precisie en recall te behouden.

2. Methodologie

De voorgestelde oplossing combineert Semi-Supervised Learning (SSL) op grafen met Online Learning technieken. De kernbenadering omvat het iteratief bouwen van een grafische representatie van de wereld en het stapsgewijs updaten ervan.

A. Harmonische Functie Oplossing (Offline Fundament)

Het algoritme is gebaseerd op de harmonische functie-oplossing voor SSL op grafen (Zhu et al.).

• Grafconstructie: Hoekpunten vertegenwoordigen data-voorbeelden, en gewichten van randen ($w_{ij}$) vertegenwoordigen gelijkenis (bijvoorbeeld gezichtsgelijkenis).
• Doel: Minimaliseren van de kwadratische doelstelling $\ell^T L \ell$ onder voorwaarde van vaste labels voor de gelabelde set $l$, waarbij $L$ de graf-Laplaciaan is.
• Interpretatie: De oplossing $\ell$ komt overeen met een willekeurige wandeling op de graaf. De label van een ongelabeld knooppunt wordt bepaald door de waarschijnlijkheid dat een willekeurige wandeling die start bij dat knooppunt eindigt bij een gelabeld knooppunt van een specifieke klasse.
• Regularisatie: Om extrapolatie naar ongelabelde data te beheersen, introduceren de auteurs een regularisatieparameter $\gamma_g$. Dit wordt geïnterpreteerd als het toevoegen van een extra "afvoer" aan de graaf, waardoor de willekeurige wandeling stopt met waarschijnlijkheid $\gamma_g/(d_i + \gamma_g)$, waardoor het vertrouwen voor knooppunten ver van gelabelde voorbeelden wordt verminderd.

B. Online Implementatie via Quantisatie

Een naïeve online implementatie (het opnieuw berekenen van de volledige graaf bij elke stap) is computationeel onuitvoerbaar ($O(t^3)$). De auteurs stellen een Quantisatie-strategie voor om een compacte representatie te behouden:

1. Representatieve Hoekpunten: In plaats van elk geobserveerd voorbeeld op te slaan, onderhoudt het algoritme een set van representatieve hoekpunten $C_t$.
2. Verdubbelingsalgoritme: Nieuwe voorbeelden worden samengevoegd met bestaande representanten als ze binnen een straal $R$ liggen. Als de set van representanten een limiet $n_g$ overschrijdt, wordt de straal $R$ verdubbeld en wordt de set opnieuw gepartitioneerd.
3. Veelvouden: Identieke of samengevoegde hoekpunten worden bijgehouden door een veelvoud-vector $v_t$.
4. Compacte Oplossing: De harmonische functie wordt berekend op deze gereduceerde graaf $\hat{W}_t$ met aangepaste Laplaciaan-termen ($\hat{L} + \gamma_g V$), waardoor de complexiteit wordt gereduceerd tot $O(n_g^3)$, onafhankelijk van tijd $t$.

C. Omgaan met Uitbijters

Om uitbijters (data-punten die niet passen in de manifold) te behandelen:

• Als de berekende label-zekerheid nul is (wat een uitbijter aangeeft), onthoudt het algoritme zich van het maken van een voorspelling.
• Uitbijters worden genegeerd bij het updaten van de set van representatieve hoekpunten, waarbij ze effectief worden behandeld als een enkel knooppunt met nul impact op de harmonische oplossing.

3. Belangrijkste Bijdragen

1. Nieuw Algoritme: Een real-time, online semi-supervised learning algoritme dat geen expliciete feedback vereist voor elke stap, maar in plaats daarvan vertrouwt op het volgen van de data-manifold.
2. Theoretische Garanties: De auteurs bieden een analyse van de regret-bound. Ze bewijzen dat de regret per stap afneemt met een snelheid van $O(n^{-1/2})$ naarmate het aantal voorbeelden $n$ toeneemt, mits de regularisatieparameter $\gamma_g$ op de juiste manier wordt gekozen ($\Omega(n^{1/4})$).
3. Efficiënte Implementatie: De introductie van een op quantisatie gebaseerd "verdubbelingsalgoritme" stelt het systeem in staat om in real-time te draaien door een grafische representatie van vaste grootte te behouden, waardoor de kubische tijdscomplexiteit van standaard SSL wordt vermeden.
4. Robuustheid: De methode blijkt robuust te zijn voor uitbijters en in staat om zich aan te passen aan plotselinge veranderingen in de omgeving (bijvoorbeeld belichting, locatie) zonder opnieuw vanaf nul te hoeven trainen.

4. Experimentele Resultaten

Het algoritme werd geëvalueerd op drie videodatasets (V1, V2, VO) met taken voor gezichtsherkenning met een classificatie van 8-weg.

• Prestatiemetingen:
  • Bereikte 95% precisie bij 90% recall op datasets V1 en V2.
  • Bereikte 100% precisie en 95% recall op dataset VO (die plotselinge veranderingen in locatie en belichting omvatte).
• Vergelijkingen:
  • vs. Nearest Neighbor (NN): De voorgestelde leerder presteerde beter dan de offline NN-classificator met ongeveer 10% in precisie bij dezelfde recall-niveaus, toegeschreven aan het volgen van de data-manifold.
  • vs. Online Semi-Supervised Boosting: De voorgestelde methode presteerde beter dan state-of-the-art online boosting, vooral wanneer de zwakke leerders niet de volledige data-distributie dekten. De boosting-methode degradeerde aanzienlijk wanneer de data-dieking onvolledig was, terwijl de op grafen gebaseerde benadering zijn representatie dynamisch aanpaste.
• Real-time Capaciteit: Het systeem draait in real-time, verwerkend ongeveer 7 frames per seconde zelfs met een grafgrootte van 500 representatieve hoekpunten.

5. Betekenis

• Adaptief Leren: Dit werk toont aan dat hoogwaardige machine learning-modellen in real-time kunnen worden gebouwd en onderhouden met minimale menselijke supervisie (initiële labels) en overvloedige ongelabelde data.
• Praktijk voor Wereldproblemen: Het adresseert de "cold start" en "concept drift" problemen die veel voorkomen in real-world toepassingen zoals surveillance of robotica, waar data-distributies veranderen in de tijd en labelen duur is.
• Generaliseerbaarheid: Hoewel gedemonstreerd op gezichtsherkenning, is het kader algemeen en toepasbaar op andere domeinen met streamende ongelabelde data (bijvoorbeeld objectherkenning).
• Theoretisch Fundament: Het overbrugt de kloof tussen statische op grafen gebaseerde SSL en dynamisch online leren, en biedt theoretische grenzen voor de kwaliteit van oplossingen in een online setting.

Kortom, het artikel presenteert een robuust, theoretisch onderbouwd en computationeel efficiënt kader voor real-time perceptiesystemen die continu leren van de omgeving zonder constante menselijke feedback nodig te hebben.