Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity

Deze paper introduceert twee efficiënte algoritmen voor conformale voorspelling in hiërarchische classificatie die geldige voorspellingsets genereren, waarbij de tweede methode gebruikmaakt van representatiecomplexiteit om kleinere sets te verkrijgen ten koste van een complexer inferentieprobleem.

De kern

Stel je voor dat je een zeer ervaren, maar soms twijfelende arts bent. Je krijgt een patiënt met vreemde symptomen. Je weet niet precies welke ziekte het is, maar je bent redelijk zeker dat het iets met de longen te maken heeft.

In de traditionele wereld van kunstmatige intelligentie zou de computer nu proberen om één specifieke ziekte te noemen, bijvoorbeeld "Longkanker". Als de computer zich vergist, is dat een fout.

De nieuwe aanpak: "Het is waarschijnlijk dit, óf dit, óf dat"
De auteurs van dit paper (Mortier en collega's) zeggen: "Waarom niet een lijstje geven?" In plaats van één ziekte te noemen, zegt de computer: "Het is waarschijnlijk Longkanker, maar het zou ook Astma of Pneumonie kunnen zijn." Dit heet in het vakjargon een voorspellende set. Dit is veiliger, want als de echte ziekte op die lijst staat, heb je gelijk.

Het probleem: De hiërarchie (De Stamboom)
Maar in veel gebieden, zoals geneeskunde of het herkennen van planten, zijn de categorieën niet los van elkaar. Ze zitten in een boomstructuur (een hiërarchie).

• Bovenaan staat "Levende wezens".
• Daaronder "Planten".
• Daaronder "Bloemen".
• En pas onderaan specifieke soorten, zoals "Lotus" of "Tulp".

Als de computer twijfelt tussen een Lotus en een Tulp, en hij moet een voorspelling doen die past binnen deze boom, kan hij niet zomaar zeggen: "Het is een Lotus of een Tulp". Dat is als zeggen: "Het is een dier of een auto". Dat klopt technisch, maar is nutteloos.

In de oude methoden moest de computer dan een hoger niveau kiezen, bijvoorbeeld "Bloemen". Maar dat is ook niet heel specifiek. Het is alsof je zegt: "Het is een bloem" terwijl je eigenlijk weet dat het een van de twee specifieke soorten is.

De oplossing: "Representatie Complexiteit" (De bouwpakket-metode)
Hier komt het slimme idee van dit paper om de hoek kijken. Ze introduceren een concept dat ze Representatie Complexiteit noemen.

Stel je voor dat je een Lego-bouwpakket hebt om je voorspelling te maken.

• Mogelijkheid 1 (Strikt): Je mag maar één Lego-blok gebruiken. Je moet dan een heel groot blok kiezen dat alles omvat, zoals "Alle Bloemen". Dat is veilig, maar niet nuttig.
• Mogelijkheid 2 (Vrij): Je mag onbeperkt blokken gebruiken. Je kunt dan zeggen: "Lotus, Tulp, en een paar andere rare bloemen". Dat is heel specifiek, maar de lijst wordt zo lang en rommelig dat niemand het meer begrijpt.
• De nieuwe methode (De Gouden Middenweg): Je mag een beperkt aantal blokken gebruiken, zeg maar maximaal 3.
  • Je kunt dan zeggen: "Het is een Lotus, een Tulp, of een Varen".
  • Dit is nog steeds een klein, overzichtelijk lijstje (maximaal 3 blokken), maar het is veel specifieker dan alleen "Bloemen".

Dit is wat ze Conformal Prediction noemen. Ze garanderen dat hun methode statistisch gezien altijd goed is (bijvoorbeeld: in 90% van de gevallen zit de juiste ziekte op het lijstje), maar ze doen dit op een slimme manier die rekening houdt met de boomstructuur en de beperking van het aantal blokken.

Hoe werkt het in de praktijk?
De auteurs hebben twee algoritmes bedacht:

1. De Strikte Manier: Kiest altijd één groot blok uit de boom. Veilig, maar soms te vaag.
2. De Slimme Manier (CRSVP-r): Kiest een combinatie van blokken, maar houdt het aantal blokken binnen een limiet (bijvoorbeeld 3).

Het resultaat
Ze hebben dit getest op datasets met duizenden soorten planten en dieren.

• Als je heel strikt bent (slechts 1 blok), krijg je vaak een lijstje met 1000 soorten (te groot, niet nuttig).
• Als je de limiet op 3 blokken zet, krijg je een lijstje met 3 soorten. Dit is veel nuttiger voor de gebruiker, terwijl de computer nog steeds garandeert dat hij niet "zomaar wat" roept.

Kort samengevat:
Deze paper leert computers hoe ze hun twijfels op een slimme manier moeten uiten. In plaats van te zeggen "Ik weet het niet, het is misschien alles" of "Ik gok maar één ding", zeggen ze: "Ik ben niet 100% zeker, maar het is waarschijnlijk een van deze 3 specifieke dingen." En ze doen dit op een manier die statistisch betrouwbaar is en makkelijk te begrijpen voor mensen.

Technische samenvatting

Hieronder volgt een gedetailleerde technische samenvatting van het artikel "Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity" in het Nederlands.

Titel: Conformal Prediction in Hiërarchische Classificatie met Beperkte Representatiecomplexiteit

Auteurs: Thomas Mortier, Alireza Javanmardi, Yusuf Sale, Eyke Hüllermeier, Willem Waegeman.

---

1. Probleemstelling

In multi-class classificatie kan een classifier onzeker zijn over de juiste class-label voor een testinstance. In dergelijke gevallen is het nuttig om voorspellingen te doen in de vorm van verzamelingen van klassen (set-valued predictions) in plaats van één enkele klasse. Dit is vooral relevant in hiërarchische classificatie, waar klassen georganiseerd zijn in een boomstructuur (bijv. medische diagnoses volgens ICD of plantensoorten).

Bestaande methoden voor set-valued voorspellingen in hiërarchische contexten hanteren vaak een strikte restrictie: de voorspelling moet een interne knoop van de hiërarchie zijn. Hoewel dit semantisch duidelijk is, leidt dit tot inefficiëntie wanneer de classifier onzeker is tussen klassen in verschillende takken van de boom. In dat geval moet de voorspelling vaak een zeer hoge, oninformatieve knoop zijn (bijv. de wortel van de boom, wat alle klassen omvat).

Aan de andere kant staat het toestaan van willekeurige subsets van klassen, wat flexibel is maar leidt tot complexe, moeilijk interpreteerbare voorspellingen. De auteurs introduceren het concept van representatiecomplexiteit ($R_T$) als een compromis: dit is het minimale aantal knopen in de boom dat nodig is om een specifieke verzameling klassen te representeren. Het doel is om voorspellende verzamelingen te construeren die een gegarandeerde dekking (coverage) hebben, terwijl de representatiecomplexiteit wordt beperkt tot een door de gebruiker gedefinieerde waarde $r$.

2. Methodologie

De auteurs breiden het framework van Split Conformal Prediction uit naar hiërarchische classificatie. Ze stellen twee algoritmen voor die geldige voorspellende verzamelingen genereren met een gegarandeerde marginale dekking van $1-\alpha$, onder de voorwaarde dat de representatiecomplexiteit $R_T(\hat{Y}) \leq r$.

A. Basisconcepten

• Hiërarchische Boom: De klasse-ruimte $Y$ wordt gemodelleerd als een boom $T$ met knopen $V_T$. Bladknopen vertegenwoordigen individuele klassen, interne knopen vertegenwoordigen groepen klassen.
• Representatiecomplexiteit ($R_T$): Gedefinieerd als het minimale aantal disjuncte knopen in de boom die nodig zijn om de voorspelde verzameling $\hat{Y}$ te vormen.
  • $R_T = 1$: De voorspelling is één enkele interne knoop (traditionele hiërarchische aanpak).
  • $R_T \leq r$: De voorspelling kan bestaan uit meerdere knopen, zolang het totaal aantal knopen $\leq r$ is.
• Split Conformal Prediction: Gebruikt een calibratieset om een drempelwaarde $\tau$ te bepalen die de grootte van de voorspellende verzameling regelt, zodat de waarheid in de verzameling zit met kans $1-\alpha$.

B. Algoritme 1: CRSVP (Conformal Restricted Set-Valued Prediction)

• Doel: Voorspellingen beperkt tot $R_T = 1$ (dus één interne knoop).
• Methode: Het algoritme start bij de meest waarschijnlijke bladknoop (de modus van de verdeling) en beweegt omhoog naar de wortel. Het zoekt de laagste knoop op het pad naar de wortel die de ware klasse bevat en waarvoor de cumulatieve kans (gecorrigeerd voor randomisatie) onder de drempel $\tau$ valt.
• Voordeel: Zeer efficiënt ($O(\log K)$ tijdens inferentie) en semantisch helder.
• Nadeel: Kan leiden tot zeer grote, oninformatieve verzamelingen bij onzekerheid over verschillende takken.

C. Algoritme 2: CRSVP-r (Conformal Set-Valued Prediction met Representatiecomplexiteit)

• Doel: Voorspellingen met $R_T \leq r$ (waarbij $r$ een gebruikersparameter is, bijv. $r=3$).
• Methode: Dit is een complexere, combinatorische optimalisatie. Het algoritme zoekt voor een gegeven $k$ (aantal top-k klassen) de verzameling van gemeenschappelijke voorouders (common ancestors) die de $k$ klassen bedekken met maximaal $r$ knopen.
• Optimalisatie: Het probleem wordt opgelost met een Dynamic Programming benadering (Algorithm 5). Dit is een variant op het "Lowest Common Ancestor" probleem, maar dan gericht op het minimaliseren van de grootte van de verzameling onder de complexiteitsbeperking.
• Inferentie: Het algoritme bouwt een geneste reeks van voorspellende verzamelingen op door de complexiteit stapsgewijs te verhogen en stopt wanneer de drempel $\tau$ wordt overschreden.
• Complexiteit: De ergste geval tijdcomplexiteit is $O(K^2 r d)$, wat praktisch haalbaar is voor kleine $r$ (bijv. $r \leq 3$).

3. Belangrijkste Bijdragen

1. Extensie van Conformal Prediction: De eerste toepassing van split conformal prediction op hiërarchische classificatie met een expliciete beperking op de representatiecomplexiteit.
2. Twee Nieuwe Algoritmen:
   • Een efficiënt algoritme voor de strikte $R_T=1$ case.
   • Een geavanceerd algoritme voor $R_T \leq r$ dat een trade-off mogelijk maakt tussen interpretatie (kleine $r$) en efficiëntie (grotere $r$).
3. Distributie-vrije Garantie: Beide methoden bieden strikte marginale dekkingsgaranties ($P(y \in \hat{Y}) \geq 1-\alpha$) zonder aannames over de onderliggende data-distributie.
4. Efficiënte Implementatie: Het introduceren van een dynamisch programmeringsalgoritme om het combinatorisch zoekprobleem voor de "gemeenschappelijke voorouders" op te lossen.

4. Experimentele Resultaten

De auteurs evalueren hun methoden op zes benchmark datasets (o.a. CIFAR-10, Caltech-101/256, PlantCLEF 2015, DBPedia, Allen Mouse Brain).

• Dekking (Coverage): Alle voorgestelde methoden (CRSVP en CRSVP-r) bereiken de nominale dekking (bijv. 90%) nauwkeurig. "Naïeve" methoden zonder randomisatie falen vaak om exacte dekking te garanderen.
• Efficiëntie (Set Size):
  • De methode met $R_T=1$ (CRSVP) levert vaak zeer grote verzamelingen op, vooral op datasets met veel klassen en onzekerheid (zoals PlantCLEF 2015).
  • Het verhogen van de complexiteit naar $r=3$ (CRSVP-3) vermindert de gemiddelde grootte van de voorspellende verzameling aanzienlijk, terwijl de dekking behouden blijft.
• Trade-off: Er is een duidelijke trade-off tussen representatiecomplexiteit en efficiëntie. Voor datasets met een ondiepe hiërarchie en veel klassen (zoals PlantCLEF) is een hogere complexiteit ($r > 1$) essentieel om bruikbare, compacte voorspellingen te krijgen.
• Vergelijking: De voorgestelde methoden presteren beter dan traditionele hiërarchische restricties (die te groot zijn) en zijn praktischer dan volledig onbeperkte verzamelingen (die te complex zijn voor interpretatie).

5. Betekenis en Conclusie

Dit werk biedt een oplossing voor het fundamentele dilemma in hiërarchische classificatie: hoe om te gaan met onzekerheid zonder te vervallen in oninformatieve of onbegrijpelijke voorspellingen.

• Interpretatie: Door de representatiecomplexiteit te beperken, blijven voorspellingen semantisch betekenisvol (ze bestaan uit een beperkt aantal hiërarchische concepten).
• Flexibiliteit: Het framework stelt gebruikers in staat om de balans te kiezen tussen de grootte van de voorspellende verzameling en de complexiteit van de output, afhankelijk van de toepassing.
• Toekomstperspectief: De auteurs suggereren dat het beperken van de complexiteit ook kan fungeren als regularisatie, wat de nauwkeurigheid kan verbeteren bij slecht geschatte kansen. Toekomstig werk richt zich op het uitbreiden van de methoden naar complexere structuren zoals Directed Acyclic Graphs (DAGs).

Kortom, de paper introduceert een robuust en flexibel raamwerk voor betrouwbare voorspellingen in complexe hiërarchische domeinen, waarbij de interpretatiebaarheid van de output centraal staat.