Structured Credal Learning

Titel: Structured Credal Learning

Auteurs: Varun Venkatesh, Eyke Hüllermeier, Bernd Bischl, Mina Rezaei

1. Het Probleem

In real-world leeropdrachten (zoals medische diagnose, drugontwikkeling en autonoom rijden) is voorspellende onzekerheid cruciaal voor betrouwbare beslissingen. Deze onzekerheid ontstaat uit twee fundamenteel verschillende bronnen:

1. Covariaatverschuiving (Covariate Shift): De verdeling van de invoerdata ($X$) verandert tussen training en test, terwijl het conditionele labelmechanisme ($Y|X$) stabiel blijft.
2. Ambiguïteit in het labelmechanisme (Label Mechanism Ambiguity): Onzekerheid in de conditionele labelverdeling veroorzaakt door meetruis, variabiliteit tussen annotatoren of intrinsieke overlap tussen klassen.

Bestaande robuuste leermethoden (zoals Distributionally Robust Optimization - DRO) behandelen deze twee bronnen vaak als één ongestructureerde verzameling van waarschijnlijkheidsverdelingen. Dit leidt tot een "conflatie" van onzekerheid: het is onduidelijk of een fout komt door een verschuiving in de data-distributie of door fundamentele onzekerheid in de labels. Hierdoor zijn gerichte interventies (zoals domeinadaptatie versus verbeterde supervisie) moeilijk toe te passen.

2. Methodologie: Het Gestructureerde Credale Leerframework

De auteurs introduceren een nieuw framework dat onzekerheid expliciet ontleedt in de twee bovengenoemde bronnen door gebruik te maken van gestructureerde credale verzamelingen (structured credal sets).

• Constructie van de Credale Verzameling:
  In plaats van een willekeurige verzameling van gezamenlijke verdelingen $(X, Y)$ te modelleren, construeren ze de onzekerheidsset als het convexe hull van productmaten. Dit wordt gedaan door:

  • Een verzameling van plausibele covariaatverdelingen (omgevingen) $\mathcal{E} = \{P_X^{(i)}\}$.
  • Een verzameling van plausibele labelmechanismen (annotatoren) $\mathcal{L} = \{P_{Y|X}^{(j)}\}$.
  • Het creëren van "werelden" door elke combinatie van een omgeving en een annotator te koppelen: $P_{ij}(A \times B) = \int_A P_{Y|X}^{(j)}(B|x) dP_X^{(i)}(x)$.
  • De gestructureerde credale set $\mathcal{P}$ is het convexe hull van alle deze $P_{ij}$.

• Geometrische Analyse (Totale Variatie):
  De kern van de theorie is het analyseren van de diameter van deze set onder de Totale Variatie (TV) afstand ($diam_{TV}(\mathcal{P})$). De auteurs bewijzen dat deze diameter niet zomaar een som is, maar een interactie vertoont tussen covariaatverschuiving en labeldisagreement.

• Het "Gating Effect":
  Een cruciale inzichten is dat de omgeving fungeert als een "poort" (gate). Labeldisagreement draagt alleen significant bij aan de totale onzekerheid in gebieden waar de covariaatverdeling voldoende massa heeft. Een schijnbaar onschadelijke verschuiving in de covariaten kan daarom de effectieve onzekerheid drastisch verhogen als deze verschuiving de data naar gebieden met hoge labeldisagreement verplaatst.

3. Belangrijkste Bijdragen

1. Expliciete Ontleding van Onzekerheid:
   Het framework scheidt covariaatverschuiving en labelmechanisme-ambiguïteit, waardoor robuustheidsgaranties direct toewijsbaar zijn aan de specifieke bron van onzekerheid.

2. Geometrische Bound en Decompositie:
   De auteurs leiden een nieuwe bovengrens af voor de TV-diameter van gestructureerde credale sets:
   $$\max\{\eta_X, \eta^*_{Y|X}\} \leq diam_{TV}(\mathcal{P}) \leq \eta_X + \eta^{eff}_{Y|X}$$
   Waarbij $\eta_X$ de maximale covariaatverschuiving is en $\eta^*_{Y|X}$ de verwachte labeldisagreement. De term $\eta^{eff}_{Y|X}$ toont aan hoe de omgeving de bijdrage van labeldisagreement moduleert (het gating effect).

3. Exacte Karakterisering in het "Pure Labeling Uncertainty" Regime:
   Wanneer de covariaten stabiel zijn (geen verschuiving), wordt de diameter exact gelijk aan de maximale paarsgewijze disagreement rate tussen annotatoren. Dit transformeert een abstract robustheidsparameter in een direct meetbare statistiek.

   • Voor deterministische labels: $\eta^*_{Y|X} = \max_{j,j'} P(f^{(j)}(X) \neq f^{(j')}(X))$.
   • Voor zachte labels: Evenredig met de verwachte $L_1$-afstand tussen waarschijnlijkheidsvectoren.

4. Finite-Sample Concentratie en Schatting:
   Er wordt bewezen dat de diameter met een parametrische snelheid $O(n^{-1/2})$ geschat kan worden vanuit eindige data, met een logaritmische afhankelijkheid van het aantal annotatoren. Dit maakt het mogelijk om robuustheidscertificaten te genereren zonder hyperparameters te tunen.

5. Tractabele Optimalisatie:
   Robuuste optimalisatie over deze gestructureerde set reduceert tot een discrete min-max probleem over de uiterste punten (extreme points) van de set. Dit elimineert de noodzaak voor externe straal-parameters (zoals bij Wasserstein DRO) en beperkt de "adversariaal" tot semantisch betekenisvolle alternatieven.

4. Resultaten

• Synthetische Experimenten:
  De auteurs valideren de theorie op synthetische datasets met Gaussische verdelingen en verschillende labelmechanismen (soft en hard).

  • De empirische TV-afstanden voldeden strikt aan de theoretische onder- en bovengrenzen (met bijna nul slack in pure verschuivingssituaties).
  • De schatters voor de diameter waren onbevooroordeeld en convergeerden snel naar de ware waarde naarmate de steekproefgrootte toenam.
  • De concentratiebounds bleken conservatief maar betrouwbaar, met een zeer lage schendingskans.

• Minimax Lagere Bound:
  Er wordt bewezen dat geen enkel algoritme de kosten van ambiguïteit (de diameter) kan omzeilen in het ergste geval. Dit bevestigt dat de gevonden grenzen scherp zijn.

5. Betekenis en Impact

Dit werk biedt een fundamentele verschuiving in hoe we robuust leren benaderen:

• Van Hyperparameter naar Statistiek: Robuustheid wordt niet langer bepaald door het handmatig instellen van een straal (radius), maar wordt een direct meetbare eigenschap van de data (annotator disagreement).
• Interpreteerbaarheid: Door de onzekerheid te ontleden, kunnen onderzoekers en praktici precies zien of een model faalt door een verschuiving in de data-distributie (op te lossen met domeinadaptatie) of door fundamenteel onduidelijke labels (op te lossen met betere supervisie).
• Praktische Toepasbaarheid: Het framework is direct toepasbaar in scenario's met meerdere annotatoren (zoals crowdsourcing of medische beeldvorming), waar het mogelijk maakt om robuustheid te garanderen zonder dat een "ground truth" bekend is.
• Theoretische Strenheid: Het koppelt credale leertheorie (imprecise probabilities) aan distributionally robust optimization, waardoor er zowel sterke theoretische garanties als praktische optimalisatie-algoritmen beschikbaar zijn.

Kortom, dit artikel levert een principieel raamwerk voor leren onder onzekerheid dat zowel wiskundig elegant als operationeel bruikbaar is voor complexe real-world toepassingen.