An Information-Theoretic Approach to Generalization Theory
Tid: Ti 2024-04-23 kl 13.00
Plats: F3 (Flodis), Lindstedtsvägen 26 & 28, Stockholm
Språk: Engelska
Ämnesområde: Elektro- och systemteknik
Respondent: Borja Rodríguez Gálvez , Teknisk informationsvetenskap
Opponent: Associate Professor Benjamin Guedj, University College London
Handledare: Professor Mikael Skoglund, Teknisk informationsvetenskap; Professor Ragnar Thobaben, Teknisk informationsvetenskap
QC 20240402
Abstract
I denna avhandling undersöker vi maskininlärningsalgoritmers generaliseringsförmåga för likafördelad data, med fokus på att upprätta stränga övre gränser för generaliseringsfelet. Vi avviker från traditionella komplexitetsbaserade metoder genom att introducera och analysera informationsteoretiska gränser som kvantifierar beroendet mellan en inlärningsalgoritm och träningsdata.
Vi studerar två kategorier av generaliseringsgarantier:
- Väntevärdegarantier. Dessa gränser mäter prestanda i genomsnitt. I detta fall fångas beroendet mellan algoritmen och data ofta av ömsesidig information eller andra informationsmått baserade på ƒ-divergenser. Trots att dessa mått erbjuder en intuitiv tolkning, kan de förbise geometrin hos algoritmens hypotesklass. För att hantera denna begränsning introducerar vi gränser som använder Wassersteinavstånd, vilket innehåller geometriska överväganden på bekostnad av att vara mer matematiskt invecklat. Dessutom föreslår vi en strukturerad, systematisk metod för att härleda gränser som fångar beroendet mellan algoritmen och en enskild datapunkt, samt mellan algoritmen och delmängder av träningsdata, under förutsättning att resten av datan är känd. Dessa typer av gränser ger djupare insikter, vilket vi demonstrerar genom att tillämpa dem för att härleda generaliseringsgarantier för algoritmen stokastisk gradient Langevindynamik.
- PAC-Bayesiska garantier. Dessa gränser mäter prestandanivån med hög sannolikhet. I detta fall fångas beroendet mellan algoritmen och data ofta av relativ entropi. Vi härleder samband mellan Seeger--Langfords- och Catonis gränser, vilket avslöjar att den förra optimeras av Gibbsfördelningen. Dessutom introducerar vi nya, starkare gränser för olika typer av kostnadsfunktioner, inklusive de med begränsad värdemängd, momentgenererande funktion, moment, eller varians. För att uppnå detta introducerar vi en ny teknik för att optimera parametrar i sannolikhetsuttryck.
Vi studerar också begränsningarna för dessa metoder. Vi presenterar ett motexempel där de flesta av de existerande (relativ entropibaserade) informationsteoretiska gränserna misslyckas, och där traditionella metoder fungerar. Slutligen utforskar vi sambandet mellan dataintegritet och generaliseringsförmåga. Vi visar att algoritmer med ett begränsad maximalt läckage generaliserar. Dessutom härleder vi för diskreta data nya gränser för algoritmer med differentiellt dataintegritet, som försvinner när antal sampel ökar, vilket garanterar deras generaliseringsförmåga även med en konstant dataintegritetsparameter. Detta står i kontrast till tidigare gränser i litteraturen, som kräver att dataintegritetsparametern minskar med antalet sampel för att säkerställa generaliseringsförmåga.