Optimization beyond a single submodular function
Submodular optimization for ranking, decision trees and diversity
Tid: On 2023-02-15 kl 13.30
Plats: F3, Lindstedtsvägen 26 & 28, Stockholm
Videolänk: https://kth-se.zoom.us/j/69024442639
Språk: Engelska
Ämnesområde: Datalogi
Respondent: Guangyi Zhang , Teoretisk datalogi, TCS
Opponent: Parinya Chalermsook, Aalto University, Finland
Handledare: Aristides Gionis, Teoretisk datalogi, TCS; Danupon Na Nongkai, Teoretisk datalogi, TCS
QC 20221220
Abstract
Submodulära funktioner karakteriserar matematiskt den allestädes närvarande egenskapen ``minskande avkastning''. De används ofta för att beskriva kärnämnen i många tillämpningar, inklusive ekonomisk nytta, redundans i information, spridning av inflytande i sociala nätverk och mer. Optimering av submodulära funktioner spelar således en central roll i ett brett spektrum av tillämpningar inom datavetenskap. Befintliga arbeten koncentrerar sig dock till stor del på att optimera en enda submodulär funktion, med enbart fokus på kortfattat urval av delmängder bland massiva data. Andra omständigheter har inte undersökts fullt ut, till exempel när det finns ett samspel mellan en submodulär funktion och andra komponenter.
I denna avhandling studerar vi optimering bortom en enda (icke-minskande) submodulär funktion inom följande tre områden.
- Ranking: Rangordning uppstår naturligt i närvaro av flera submodulära funktioner, till exempel när en lista med delade resurser serveras sekventiellt för att tillfredsställa flera submodulära krav med individuella budgetar. Ett konkret exempel är att rangordna webbsidor för att tillfredsställa flera användares avsikter med olika ``tålamod''. Vi studerar först detta rankningsproblem under kardinalitetsbegränsningar, och sedan överväger vi utökningar av den grundläggande inställningen, inklusive ryggsäcksbegränsningar, strömningsinställningar och robusthetskrav.
- Beslutsträd: Ett träd (eller en policy) kan ses som en adaptiv generalisering av rangordning. Populära beslutsträd för klassificering, inklusive CART och C4.5, är konstruerade av rekursiva giriga splittringar, styrda av någon orenhetsfunktion. Dessa träd är korrekta, men kanske inte är lätta att förstå på grund av en potentiellt stor trädstorlek. En ny karaktärisering av ett beslutsträd sker via adaptiv skärningspunkt mellan flera submodulära funktioner, en för varje objekt som ska klassificeras. Vi upptäcker att denna karakterisering gör det möjligt för en att analysera och kontrollera trädets komplexitet för en stor familj av föroreningsfunktioner.Som en konsekvens kan vi producera korrekta och tolkningsbara beslutsträd med begränsad komplexitet.
- Mångfald: Multi-objektiv optimering påträffas ofta i verkligheten. En specifik viktig form är en gemensam optimering av nytta och mångfald, där nytta ofta modelleras av en submodulär funktion. Från den teoretiska sidan diskuterar vi nya tekniker för sådan gemensam optimering över klustrad input; Från den praktiska sidan föreslår vi en ny tillämpning för att lära sig olika regeluppsättningar, där mångfald uppmuntrar icke-överlappande regler som ger önskvärda entydiga beslut.
För vart och ett av de tre områden som diskuterats ovan, vi introducerar nya formuleringar för tillämpningar inom datavetenskap och utvecklar algoritmer som är effektiva, lätta att implementera och har bevisbara approximationsgarantier. Utöver teori lyfter vi också fram deras praktiska potential genom att presentera empiriska prestationer i utvalda tillämpningar. Vårt arbete förbättrar avsevärt modelleringsmöjligheterna för submodulär optimering för nya applikationsdomäner.