Technische Samenvatting: Gegarandeerd Optimale Compositie-Verklaringen voor Neuronen

Probleemstelling

Compositie- verklaringen hebben tot doel de ruimtelijke uitlijning tussen de activeringen van het receptieve veld van een neuron en specifieke concepten (bijvoorbeeld objecten, texturen) te beschrijven met behulp van logische regels. Het kerndoel is het vinden van een logische formule $L$, samengesteld uit concepten uit een verzameling $L_1$, die de Intersection over Union (IoU) maximaliseert tussen de activatiemap van het neuron en de conceptannotaties.

De zoekruimte voor alle mogelijke conceptcombinaties is echter combinatorisch explosief. Eerdere literatuur (bijvoorbeeld Mu en Andreas, 2020) heeft dit aangepakt door de zoekruimte te beperken via structurele aannames en het toepassen van beam search. Hoewel beam search computationeel efficiënt is, biedt het geen theoretische garantie op optimaliteit. Bijgevolg blijft het onduidelijk of de gegenereerde verklaringen werkelijk de best mogelijke uitlijningen zijn of slechts lokale optima, en hoe ver ze afwijken van de ground truth. Deze onzekerheid beperkt de betrouwbaarheid van huidige interpretatiemethoden en hindert de ontwikkeling van algoritmen die benaderingsfouten kunnen verminderen.

Methodologie

De auteurs stellen een raamwerk voor om garandeerd optimale compositie- verklaringen te berekenen over de volledige toestandsruimte die wordt gedefinieerd door standaardaannames, zonder in te leveren op computationele haalbaarheid. De methodologie bestaat uit drie hoofdcomponenten:

1. Decompositie van de IoU-metriek (dIoU)

Het artikel introduceert een decompositie van de IoU-score in fundamentele grootheden die de uitlijningskwaliteit beheersen. Dit berust op drie aannames:

• Aanname 1: Concepten in een verklaring zijn distinct.
• Aanname 2: Concepten worden incrementeel gecombineerd.
• Aanname 3: Logische operatoren zijn 00-bewarend (dat wil zeggen, ze kunnen geen 1 produceren uit twee 0'en). Dit omvat standaard bitwijze operatoren: OF ($\lor$), EN ($\land$), en EN NIET ($\land \neg$).

De IoU wordt herschreven met behulp van vier sleutelverzamelingen die zijn afgeleid van de neuronactivatiematrix $N$ en conceptmatrices $M$:

• Uniek/Intersectie ($I_U, I_C$): Locaties waar het neuron activeert op unieke of gemeenschappelijke conceptannotaties.
• Uniek/Extra ($E_U, E_C$): Locaties waar het concept is geannoteerd maar het neuron niet activeert.

Deze decompositie ($dIoU$) maakt een fijnmazige analyse mogelijk van hoe logische operatoren de teller (intersectie) en de noemer (unie) van de IoU-score beïnvloeden.

2. Heuristische Schatting

Om de zoektocht te sturen, ontwerpen de auteurs een heuristiek die de maximale en minimale mogelijke IoU schat voor elke partiële label $L$ en elk potentieel pad dat $L$ uitbreidt tot de maximale lengte $n$.

• Labelgrootheden: De heuristiek schat de impact van het toevoegen van een concept $k$ aan een label $L$ met behulp van een Disjuncte Matrix om overlappingen te controleren. Het leidt grenzen af voor intersectie en extra's op basis van of de operanden disjunct of overlappend zijn.
• Padgrootheden: Om het potentieel van een verdere uitbreiding van een label te schatten, maakt de methode gebruik van Top en Bott vectoren. Deze vectoren slaan de cumulatieve sommen op van de $t$ hoogste en laagste waarden voor elke grootheid over het dataset, waardoor het algoritme de beste en slechtst mogelijke verbeteringen kan schatten die bereikbaar zijn door de resterende concepten toe te voegen.
• Geaggregeerde versus Steekproefberekening: Om precisie en efficiëntie in evenwicht te brengen, gebruikt de heuristiek geaggregeerde berekeningen (optellen over het dataset) voor initiële pruning en frontbeheer, terwijl op steekproeven gebaseerde berekeningen (per afbeelding) worden gereserveerd voor het verfijnen van schattingen van veelbelovende knopen.

3. Optimaal Zoekalgoritme

De auteurs stellen een best-first zoekalgoritme voor (Algoritme 1) dat optimaliteit garandeert:

1. Initialisatie: Bereken exacte grootheden voor alle atomaire concepten en schat paden met behulp van de heuristiek.
2. Frontbeheer: Onderhoud een prioriteitswachtrij van knopen, gesorteerd op hun geschatte maximale IoU ($dIoU_{max}$).
3. Pruning: Prune dynamisch de front door knopen te verwijderen waarvan de $dIoU_{max}$ onder het globale maximum van de tot nu toe gevonden minimale schattingen ($MinIoU$) valt.
4. Uitbreiding en Verfijning:
   • Haal de knoop met de hoogste schatting uit de wachtrij.
   • Als de schatting geaggregeerd is, verfijn deze tot een op steekproeven gebaseerde schatting.
   • Pas logische equivalentieregels toe om redundantie te verminderen.
   • Als de knoop een definitief label is, bereken de exacte IoU. Als het de nieuwe beste is, update het globale beste en propageer exacte grootheden terug om de schattingen van andere knopen die deelsublabels delen, te updaten.
   • Als de knoop niet definitief is, breid deze uit door alle mogelijke concepten en operatoren te concateneren, de grenzen opnieuw te schatten en ze in de front in te voegen.

Het algoritme is bewezen toelaatbaar (het onderschat nooit de maximale mogelijke IoU) en compleet, waardoor het gegarandeerd de globaal optimale oplossing vindt.

Belangrijkste Bijdragen

1. Formele Garanties: Dit is het eerste raamwerk dat theoretische garanties van optimaliteit biedt voor compositie- verklaringen over de volledige toestandsruimte die wordt bespannen door standaardaannames.
2. Decompositie (dIoU): Een nieuwe decompositie van de IoU-metriek die fundamentele grootheden identificeert die uitlijning beheersen, waardoor een precieze karakterisering van de impact van logische operatoren mogelijk wordt.
3. Optimaal Algoritme: Een zoekalgoritme dat optimale verklaringen berekent in een tijd die vergelijkbaar is met exhaustieve beam search, waardoor de exploratie van de volledige toestandsruimte haalbaar wordt.
4. Heuristisch Gesteunde Beam Search: Een variant van beam search die wordt gestuurd door de voorgestelde decompositie en heuristiek, die de eerdere runtime-prestaties matcht of verbetert, terwijl het meer flexibiliteit biedt in hyperparameters.

Resultaten

De auteurs evalueerden hun methode op ResNet18, AlexNet en DenseNet161-modellen die zijn getraind op Places365, met gebruik van drie datasets van variërende complexiteit (Cityscapes, Ade20K, Broden).

• Haalbaarheid: Het optimale algoritme vindt succesvol de optimale oplossing binnen haalbare runtimes over alle complexiteitsniveaus. Hoewel het een grotere toestandsruimte exploreert dan beam search, blijft de runtime vergelijkbaar met vanilla beam search (bijvoorbeeld ~5768 seconden/eenheid voor hoge complexiteit versus ~5929 voor vanilla beam search), terwijl een naïeve breedte-zoektocht honderden miljoenen uren zou vereisen.
• Suboptimaliteit van Beam Search: De analyse onthult dat 10–40% van de verklaringen die eerder via beam search zijn verkregen, suboptimaal zijn wanneer overlappende concepten betrokken zijn.
  • Categorie 1 (Meest Voorkomend): Verklaringen verschillen zowel in concepten als in IoU. Beam search faalt vaak om verklaringen te vinden die complexe EN/EN-NIET-combinaties bevatten die gespecialiseerde eenheden beschrijven.
  • Categorie 2: Verklaringen delen concepten maar verschillen in logische structuur, wat leidt tot verschillende IoU-scores (bijvoorbeeld ((A OF B) EN C) versus ((A EN C) OF B)).
  • Categorie 3: Verklaringen hebben dezelfde IoU maar verschillen in structuur. Beam search kan "ongeverifieerde" verklaringen produceren die vertrouwen op disjuncte concepten die nooit samen voorkomen, terwijl het optimale algoritme de juiste uitlijning identificeert.
• Heuristische Prestaties: De variant van beam search die wordt gestuurd door de voorgestelde heuristiek, presteert beter dan baselines (MMESH, Vanilla Beam) wat betreft bezochte toestanden en schaalt effectiever met verklaringlengte en beam-grootte, terwijl het minder geheugen vereist omdat het geen ruimtelijke tensoren hoeft op te slaan voor heuristische berekening.

Betekenis en Claims

Het artikel stelt dat het identificeren van de ground-truth optimale oplossing cruciaal is voor:

1. Betrouwbaarheid: Het voorkomen van misleidende inzichten in neuron-gedrag veroorzaakt door suboptimale benaderingen.
2. Datasetkarakterisering: Het onthullen van onbestudeerde eigenschappen van datasets als beam search convergeert naar het optimum.
3. Algoritmeontwikkeling: Het bieden van een benchmark om de ontwikkeling van nieuwe algoritmen te sturen die benaderingsfouten verminderen.

De auteurs benadrukken dat hun methode niet afhankelijk is van ruimtelijke informatie (in tegenstelling tot MMESH), waardoor de heuristiek potentieel toepasbaar is over domeinen buiten computer vision. Ze positioneren dit werk als een theoretische fundament dat de kloof overbrugt tussen Network Dissection (dat optimale enkele concepten vindt) en Compositie- verklaringen (die eerder optimaliteit opofferden voor complexiteit). Het artikel concludeert met de opmerking dat hoewel het optimale algoritme een belangrijke stap is, er toekomstig werk nodig is om deze garanties uit te breiden naar niet-00-bewarende operatoren en andere architecturen zoals Transformers.