Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees

Probleemstelling
Random forests (RF's) zijn een dominante methode voor voorspelling op tabulaire data, die hoge nauwkeurigheid en rekenkundige efficiëntie bieden. Hun toepassing in gevoelige domeinen (bijvoorbeeld gezondheidszorg, financiën) wordt echter belemmerd door het risico op het lekken van informatie over individuele trainingsrecords. Hoewel Differentiële Privacy (DP) een rigoureus kader biedt om deze risico's te mitigeren, lijden bestaande benaderingen voor het afdwingen van DP op random forests onder ernstige degradatie van de bruikbaarheid.

Huidige methoden vallen over het algemeen in twee paradigma's, die beide aanzienlijke beperkingen ondervinden:

1. Gierige Boomconstructie: Het aanpassen van standaard beslisboomalgoritmen (die splitsen selecteren op basis van datage afhankelijke onzuiverheidscriteria) aan de DP-omgeving vereist het injecteren van ruis in het proces voor het selecteren van splitsingen. Deze ruis hoopt zich snel op, wat leidt tot slechte boomstructuren en lage bruikbaarheid.
2. Volledig Random Bomen: Geïnspireerd door "Extra Trees", genereren deze methoden boomstructuren die onafhankelijk zijn van de data en gebruiken ze de data uitsluitend om de bladeren te labelen. Hoewel dit voorkomt dat het privacybudget wordt besteed aan het leren van structuren, zijn deze bomen zeer gevoelig voor diepte. Ondiepe bomen resulteren in overmatig grote bladeren, terwijl diepe bomen bladeren produceren met onvoldoende steekproeven voor betrouwbare geprijsde voorspellingen. Bovendien falen ze zonder datage afhankelijke stopcondities vaak om informatieve structuren in de kenmerkruimte te vangen en reduceren ze tot voorspellingen op basis van de meerderheidsklasse.

Methodologie: Lumberjack
Het artikel introduceert Lumberjack, een nieuw differentieel privé random forest-algoritme dat is ontworpen om de kloof te overbruggen tussen de expressiviteit van diepe bomen en de beperkingen van differentiële privacy. De kerninnovatie is een tweestapsproces: het construeren van grote, volledig random bomen en vervolgens het toepassen van agressieve, privacybehoudende snoeiing om alleen voldoende gevulde knopen te behouden.

• Grandomiseerde Constructie: Lumberjack bouwt diepe random bomen (vergelijkbaar met Extra Trees) waarbij splitsingen uniform willekeurig worden gekozen uit de kenmerkruimte, onafhankelijk van de data. Dit vermijdt de hoge ruiskost die geassocieerd is met gierige selectie van splitsingen.
• Privacybehoudende Snoeiing via Detectie van Zware Hitters: De kritieke uitdaging is bepalen welke knopen voldoende datapunten bevatten om te behouden zonder de privacy te schenden. Lumberjack formuleert dit als een probleem van zware hitter-detectie over een hiërarchische boomstructuur. Het doel is om knopen te identificeren waar het aantal datapunten een drempelwaarde $\tau$ overschrijdt.
• Nieuw Algoritme voor Zware Hitters: De auteurs stellen een nieuw $(\epsilon, \delta)$-DP-algoritme voor voor het detecteren van zware hitters in bomen met hoogte $h$.
  • Mechanisme: In plaats van een naïeve top-down doorloop die een $\ell_2$-gevoeligheid oplevert die schaalt als $\sqrt{h}$, voert het algoritme gestructureerde, overlappende ruisbeheerde binaire zoekopdrachten uit. Het queryt knopen in een middenlaag en markeert ze als "Zwaar" of "Licht".
  • Propagatie: Vanwege de monotoon aard van boomtellingen (de telling van een ouder is de som van zijn kinderen) impliceert een "Zware" knoop dat al zijn voorouders Zwaar zijn, en impliceert een "Lichte" knoop dat al zijn nakomelingen Licht zijn. Dit stelt het algoritme in staat om grote delen van de boom over te slaan.
  • Verlaging van Gevoeligheid: Door deze structuur te exploiteren, verlaagt het algoritme de $\ell_2$-gevoeligheid van $O(\sqrt{h})$ naar $O(\sqrt{\log h})$.
  • Integratie van Sparse Histograms: Om de rekenkundige onuitvoerbaarheid van het queryen van alle knopen in diepe bomen (waarvan de meeste leeg zijn) het hoofd te bieden, integreert het algoritme technieken uit schatting van sparse histogrammen. Het mappet query's met voldoende kleine tellingen deterministisch naar "Licht" (leeg) en voegt alleen Gaussische ruis toe aan query's die mogelijk niet-leeg zijn.
• Gecentraliseerde Privacy-Accounting: De auteurs voeren een gecentraliseerde privacyanalyse uit voor de constructie van het hele bos in plaats van te vertrouwen op standaard compositie over individuele bomen, wat een strakkere privacygrens oplevert.

Belangrijkste Bijdragen

1. Lumberjack-algoritme: Een nieuwe DP random forest-methode die randomiseerde boomconstructie combineert met datage afhankelijke snoeiing, waardoor het trainen van diepe, hoogbruikbare bomen onder strikte privacybudgetten mogelijk wordt.
2. Nieuwe Zware Hitter-detectie: Een nieuw algoritme voor $(\epsilon, \delta)$-DP zware hitter-detectie in hiërarchische data met een fout-schaling van $O_{\epsilon, \delta}(\sqrt{\log h})$ voor bomen met hoogte $h$. De auteurs merken op dat dit onderdeel op zichzelf van belang kan zijn voor andere problemen met hiërarchische data.
3. Theoretische Analyse: Een strakke privacyanalyse die de losse grenzen van standaard compositiestellingen vermijdt en een ondergrens vaststelt die aantoont dat de schaling van $O(\sqrt{\log h})$ bijna optimaal is voor methoden die diepe bomen ondersteunen.
4. Empirische State-of-the-Art: Uitgebreide evaluatie die aantoont dat Lumberjack consistent beter presteert dan bestaande DP random forest-baselines (waaronder DiffPrivLib, SNR, Smooth Sensitivity en gierige varianten) over meerdere datasets en privacyregimes.

Resultaten
De auteurs hebben Lumberjack geëvalueerd op de Adult-dataset en vier binaire classificatietaken uit de Folktables (California 2018)-dataset.

• Prestaties: Lumberjack presteerde consistent beter dan alle eerdere DP random forest-methoden over privacybudgetten $\epsilon \in \{0.5, 1, 2, 4, 8\}$.
• Vergelijking met Niet-Privé: Hoewel er een kloof blijft bestaan in vergelijking met niet-privé Extra Trees, presteert Lumberjack vaak beter dan niet-privé gierige beslisbomen, zelfs bij gematigde privacyniveaus.
• Problemen met Baselines: Het artikel merkt op dat veel bestaande DP-RF-baselines (met name die welke gierige boomconstructie gebruiken) privacyfouten bevatten, zoals datage afhankelijke stopcriteria of onjuiste gevoeligheidsberekeningen, die de auteurs in een appendix in detail beschrijven. Ondanks deze fouten in eerdere werken, overtreft Lumberjack hun gerapporteerde prestaties nog steeds.
• Schaalbaarheid: De methode slaagt erin om diepe bomen (diepte tot 100) te verwerken zonder de ineenstorting van de bruikbaarheid die wordt gezien bij benaderingen met volledig random bomen.

Betekenis en Claims
Het artikel claimt dat Lumberjack een nieuwe state-of-the-art vestigt voor differentieel privé random forests. De auteurs betogen dat hun bevindingen suggereren dat zorgvuldig ontworpen DP random forests de "grote meerderheid van de bruikbaarheidskloof" met niet-privé tegenhangers kunnen dichten. Ze benadrukken dat de combinatie van randomiseerde constructie met principiële, privacybewuste snoeiing een veelbelovende en onderbelichte richting is.

De auteurs stellen expliciet dat hoewel ze de bruikbaarheidskloof voor gerandomiseerde bossen hebben aangepakt, het ontwerpen van hoogbruikbare DP gierige random forests een open uitdaging blijft. Ze suggereren dat toekomstig werk mogelijk verfijndere compositietechnieken en probleemspecifieke mechanismen vereist om de afweging tussen privacy en bruikbaarheid verder te verbeteren. Het artikel dient ook als een waarschuwing met betrekking tot de rigorousheid van privacybewijzen in de bestaande literatuur, waarbij privacyovertredingen worden geïdentificeerd in meer dan 10 eerdere papers.