Metric-valued regression

Deze paper presenteert een efficiënt algoritme voor regressie tussen metriekruimtes dat, gebaseerd op metrische medoïden en het nieuwe concept van semi-stabiele compressie, de eerste sterk Bayes-consistente leerbaarheid garandeert voor onbegrensde verliezen in het agnostische scenario.

De kern

Stel je voor dat je een supersterke leerkracht bent die een nieuwe taal moet leren. Maar hier is de twist: de "woorden" die je moet leren, zijn niet gewoon cijfers of letters, maar kunnen van alles zijn. Ze kunnen afstanden zijn op een kaart, kleuren op een palet, of zelfs complexe 3D-vormen.

Deze paper, getiteld "Metric-valued regression" (Regressie met metrische waarden), gaat over hoe een computer zo'n taal kan leren, zelfs als de "woorden" (de labels) heel vreemd of oneindig groot zijn.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De Vreemde Woordenboeken

Normaal gesproken leert een computer twee dingen:

• Classificatie: "Is dit een kat of een hond?" (Antwoorden zijn simpel: A of B).
• Regressie: "Hoeveel weegt deze hond?" (Antwoorden zijn getallen: 5, 10, 15 kg).

Maar wat als je moet voorspellen waar een hond precies in een park moet lopen, of welke kleur een schilderij moet hebben? De antwoorden zijn dan geen simpele getallen of ja/nee, maar punten in een heel groot, complex landschap.

De auteurs zeggen: "Hoe leer je een computer om het beste antwoord te vinden in zo'n groot, complex landschap, zelfs als dat landschap oneindig groot is en we niet weten hoe de verdeling eruitziet?"

2. De Oplossing: De "MedNet" (Het Slimme Kompas)

De auteurs hebben een nieuw algoritme bedacht, genaamd MedNet.

Stel je voor dat je een grote groep mensen hebt die elk een punt in een groot veld hebben gemarkeerd. Je wilt een centraal punt vinden dat het beste past bij al die mensen.

• De oude manier (K-NN): Kijk naar de 5 dichtstbijzijnde mensen en kies hun gemiddelde.
• Het probleem: Soms is het beste antwoord een punt dat niemand in de groep heeft gemarkeerd. Het is een punt dat nog nooit gezien is, maar wiskundig gezien het beste middenpunt is. De oude methoden kunnen dat niet doen; ze blijven hangen in de bestaande punten.

MedNet doet iets slims:

1. Het maakt een kaart: Het verdeelt het veld in gebieden (zoals Voronoi-cellen, denk aan een honingraat).
2. Het zoekt het "Medoid": In elk gebied zoekt het niet naar een gemiddelde, maar naar het beste bestaande punt (de medoid) dat het dichtst bij al de andere punten in dat gebied ligt.
3. Het snijt de oneindigheid af: Omdat het landschap oneindig groot kan zijn, maakt MedNet slimme "snijlijnen". Het negeert tijdelijk de punten die zo ver weg liggen dat ze waarschijnlijk niet belangrijk zijn (zoals het negeren van sterren die te ver weg zijn om te zien).

3. De Magische Truc: "Semi-stable Compression"

Dit is het meest technische, maar ook het coolste deel.

Stel je voor dat je een heel dik boek met antwoorden moet onthouden, maar je mag er maar een paar pagina's uitknippen om het te onthouden.

• Stabiele compressie: Je knipt pagina's uit, maar als je een paar extra pagina's toevoegt aan je boek, mag je antwoord niet veranderen.
• Semi-stabiele compressie (de nieuwe truc): Je mag extra "korte notities" (zij-informatie) bij je geknipte pagina's doen. Zolang de knipte pagina's zelf stabiel blijven, mag je die notities gebruiken om het antwoord te verfijnen.

Dit stelt de computer in staat om te zeggen: "Ik heb deze specifieke punten onthouden, en met deze kleine notitie kan ik het antwoord voor een punt dat ik nooit heb gezien, toch perfect voorspellen."

4. Waarom is dit belangrijk?

Vroeger dachten wetenschappers dat je voor zulke complexe problemen altijd een heel groot, perfect dataset nodig had, of dat je alleen kon werken met simpele getallen.

Deze paper bewijst dat je niet perfect hoeft te zijn om perfect te leren. Zolang het "landschap" van de antwoorden niet te chaotisch is (de auteurs noemen dit "topologisch scheidbaar" en "begrensd in verwachting"), kan MedNet leren om steeds beter te worden naarmate er meer voorbeelden zijn.

De kernboodschap in één zin:
We hebben een nieuwe manier bedacht om computers te leren hoe ze het beste antwoord moeten kiezen in een wereld van oneindige en vreemde opties, door slim te "snijden" in de data en een nieuwe soort geheugen-truc te gebruiken.

Samenvattend met een metafoor:

Stel je voor dat je een kok bent die een perfecte soep moet maken.

• Oude methode: Je proeft alleen de ingrediënten die je in de pan hebt gegooid en mengt die. Als je een speciaal kruid mist dat de soep perfect maakt, kun je het niet toevoegen omdat je het niet in de pan hebt.
• MedNet: Je kijkt naar alle ingrediënten die je hebt, verdeelt ze in groepjes, en zoekt in elke groep het beste kruid dat je al hebt. Maar je bent slim genoeg om te weten dat als je een heel groot kruidenrek hebt, je alleen naar de dichtstbijzijnde, meest waarschijnlijke kruiden hoeft te kijken. En met een kleine "notitie" (de semi-stabiele compressie) kun je de perfecte smaak voorspellen, zelfs voor een soep die je nog nooit hebt gemaakt.

Het resultaat? Een computer die nooit moe wordt, nooit fouten maakt in de lange termijn, en elke taal van de wereld kan leren, zolang die taal maar een beetje structuur heeft.

Technische samenvatting

Titel: Metric-valued regression (Regressie met metrische waarden)

Auteurs: Dan Tsir Cohen en Aryeh Kontorovich
Publicatiedatum: 7 februari 2022 (arXiv:2202.03045v1)

---

1. Het Probleem

Het artikel adresseert het fundamentele probleem van supervised learning (toezicht op leren) in een zeer algemene setting: metric-valued regression.

• Context: Traditionele regressie veronderstelt dat labels in de reële getallen ($\mathbb{R}$) liggen met een absolute of kwadratische fout, terwijl classificatie discrete labels gebruikt met een 0-1 verliesfunctie.
• Definitie: In dit werk worden zowel het instance-ruimte $X$ als de label-ruimte $Y$ uitgerust met een willekeurige metriek ($\rho$ voor $X$ en $\ell$ voor $Y$). De leerder ontvangt een trainingsstichproef $(X_i, Y_i)$ getrokken uit een onbekende verdeling $\bar{\mu}$ en moet een hypothees $f_n: X \to Y$ construeren om het risico $R(f_n) = \mathbb{E}[\ell(f_n(X), Y)]$ te minimaliseren.
• Doel: Het bewijzen van sterke universele Bayes-consistentie. Dit betekent dat voor elke mogelijke verdeling $\bar{\mu}$, het risico van de geleerde hypothees $R(f_n)$ bijna zeker convergeert naar het optimale Bayes-risico $R^*$ (het minimum risico bereikbaar door elke meetbare functie) naarmate de steekproefgrootte $n \to \infty$.
• Uitdaging: De labelruimte $Y$ kan ongebonden zijn (d.w.z. de verliesfunctie is niet begrensd), wat de meeste bestaande methoden faalt te garanderen in een agnostische setting (waar geen aanname wordt gedaan over de "wiskundige waarheid" van de data, alleen dat er ruis is).

2. Methodologie: De MedNet-algoritme

De auteurs introduceren een nieuw algoritme genaamd MedNet. De kern van de methologie verschilt fundamenteel van eerdere benaderingen (zoals k-NN of OptiNet) door gebruik te maken van metrische medoïden in plaats van stemmechanismen.

De werking van MedNet:

1. Voronoi-partitie: De trainingsdata in $X$ wordt opgesplitst in Voronoi-cellen gebaseerd op een $\gamma$-net (een verzameling van representatieve punten).
2. Medoïd-bepaling: Voor elke Voronoi-cel wordt niet de meest voorkomende label gekozen (zoals bij k-NN), maar de empirische medoïd. Dit is het label $y \in Y$ dat de som van de afstanden tot alle labels in die cel minimaliseert:
   $$y' = \arg\min_{y \in Y} \sum_{j: X_j \in \text{cel}} \ell(y, Y_j)$$
3. Truncatie en Side Information: Omdat $Y$ onbeperkt kan zijn, truncateert het algoritme de labelruimte adaptief naar een eindige subset $Y_n$. Dit is cruciaal omdat:
   • Concentratie-ongelijkheden een begrensd bereik vereisen.
   • Het compressieschema beperkte "side information" vereist.
   • Het algoritme labels kan voorspellen die nooit in de trainingsset zijn voorgekomen (een essentieel kenmerk voor consistentie in onbeperkte ruimtes).
4. Selectie van schaal: Het algoritme test meerdere schalen ($\gamma$) en kiest de beste op basis van een generalisatiebound die het risico maximaliseert.

Technische Innovatie: Semi-stable Compression
De auteurs introduceren een nieuwe techniek: semi-stable compression.

• In tegenstelling tot eerdere "stable compression" methoden (die alleen werken voor realizable/noise-free settings of beperkte verliezen), maakt deze variant gebruik van side information (bijv. bits die de truncatie van de labelruimte beschrijven).
• Alleen de compressieset (de geselecteerde voorbeelden) moet voldoen aan de stabiliteitsvoorwaarde; de side information mag variëren zonder de stabiliteit te breken. Dit maakt het mogelijk om onbeperkte verliezen en agnostische ruis te hanteren.

3. Belangrijkste Bijdragen

1. Eerste resultaat voor onbeperkt verlies: Dit is het eerste bewijs van sterke universele Bayes-consistentie voor regressie met onbeperkte verliesfuncties in een agnostische setting, zonder beperkingen aan de labelruimte behalve de "bounded in expectation" (BIE) voorwaarde.
2. Algoritme MedNet: Een efficiënt algoritme dat gebaseerd is op metrische medoïden en in staat is om labels te genereren die niet in de trainingsdata voorkomen.
3. Techniek van Semi-stable Compression: Een nieuwe theoretische tool die de analyse van compressieschema's uitbreidt naar settings met side information, wat mogelijk van onafhankelijk belang is voor andere leerproblemen.
4. Minimalistische Aannames: De methode vereist slechts dat $X$ en $Y$ scheidbare metrische ruimtes zijn en dat $Y$ "bounded in expectation" is ($\mathbb{E}[\ell(y_0, Y)] < \infty$).

4. Resultaten en Theorema's

• Hoofdstelling (Theorem 1): Er bestaat een leer-algoritme (MedNet) dat sterk universeel Bayes-consistent is voor elke scheidbare metrische ruimte $X$ en $Y$, mits $Y$ bounded in expectation is.
• Vergelijking met bestaande methoden: De auteurs tonen aan dat bestaande methoden (zoals k-NN, OptiNet, of memory-based technieken) falen in specifieke scenario's.
  • Voorbeeld: Als de labelruimte $Y = \{a, b, c, o\}$ is met een specifieke metriek waarbij $o$ de optimale voorspelling is, maar $a, b, c$ de enige waargenomen labels in de data zijn, zullen stem-mechanismen altijd een van de waargenomen labels kiezen. De Bayes-optimale predictor zou echter $o$ moeten kiezen. MedNet kan dit doen omdat het de medoïd berekent en $o$ kan "voorspellen" als het de beste gemiddelde afstand heeft, zelfs als $o$ niet in de sample zit.
• Generalisatie: De resultaten gelden voor:
  • Eindige $Y$.
  • Teldbare $Y$ met eindige diameter.
  • Teldbare $Y$ met onbeperkte diameter (onder de BIE-conditie).
  • Scheidbare $Y$ (via discretisatie).

5. Betekenis en Impact

• Theoretische Vooruitgang: Het artikel sluit een belangrijke theoretische gap. Eerdere werken beperkten zich tot 0-1 verlies (classificatie) of beperkte verliezen. Dit werk generaliseert de theorie van "learning whenever learning is possible" naar onbeperkte verliesfuncties in metrische ruimtes.
• Praktische Toepassingen: De methode is relevant voor problemen waar labels niet in $\mathbb{R}$ liggen, zoals:
  • Regressie in Hilbert-ruimten of Banach-ruimten.
  • Regressie op grafen of netwerken.
  • Regressie met complexe structurele labels (bijv. bomen, vectoren met specifieke afstandsfuncties).
• Robuustheid: Door de focus op medoïden en truncatie is het algoritme robuust tegen ruis en in staat om de onderliggende structuur van de data te benutten zonder aan te nemen dat de labels beperkt zijn tot een eindige set.

Conclusie:
Dit artikel biedt een doorbraak in het theoretisch begrip van regressie in algemene metrische ruimtes. Door de introductie van MedNet en semi-stable compression, bewijzen de auteurs dat leren mogelijk is onder zeer algemene voorwaarden, zelfs wanneer de verliesfunctie onbeperkt is en de optimale voorspelling een label is dat nooit in de trainingsdata is gezien.