Fairness and Diversity-Aware Algorithms

QC 20260408

Abstract

Eftersom algoritmiska system i allt högre grad formar mänskliga upplevelser har det blivit en central utmaning att säkerställa rättvisa och mångfald. Denna avhandling studerar rättvisa och mångfald genom algoritm design och optimerings teori, och tillhandahåller formella ramverk och effektiva algoritmer inom tre domäner: rankningsbaserad rekommendation, strömmande rekommendation och grafanalys.

Den första delen av avhandlingen undersöker mångfaldsmaximering i rekommendationssystem med stokastiskt användarengagemang. Vi studerar först hur man rangordnar objekt i rekommendationssystem, där användare engagerar sig med innehåll sekventiellt och probabilistiskt. Vi introducerar två nya mångfaldsmått, sekventiell summa-mångfald och sekventiell täcknings-mångfald, som tar hänsyn till osäkerhet i användarengagemang. Vårt mål är att hitta en rangordning av objekt som maximerar dessa sekventiella mångfaldsmått. Vi visar att sekventiell täcknings-mångfald är ordnad submodulär, vilket möjliggör en girig 1/2-approximation. För sekventiell summa-mångfald tillhandahåller vi polynomtids konstant-faktor approximationsalgoritmer. Separat studerar vi en strömmande miljö där objekt anländer kontinuerligt och användare kan besöka systemet flera gånger vid godtyckliga tidpunkter. För denna miljö strävar vi efter att designa en strömmande algoritm som maximerar ett stokastiskt täcknings-mångfaldsmått. Vi visar att en klassisk girig algoritm uppnår ett tight 1/2-konkurrensförhållande men kräver minne linjärt i strömlängden. Med sublinjärt minne och en övre gräns T' på antalet användarbesök T, föreslår vi STORM, som uppnår ett 1/4(T'-T+1)-konkurrensförhållande. Vi föreslår vidare STORM++ som förbättrar konkurrensförhållandet till 1/8delta, där heltalsparametern delta kontrollerar avvägningen mellan lösningskvalitet och beräkningskostnad.

Den andra delen av avhandlingen studerar mångfald som en bivillkor i upptäckt av tätaste delgrafer och behandlar problemet med att hitta täta gemenskaper i nätverk med heterogena relationstyper. Vi modellerar relationstyper som kantfärger och formulerar problemet At Least h Colored Edges Densest Subgraph (ALHCEDGESDSP), som söker delgrafer som är både täta och innehåller åtminstone hi kanter av varje färg i. Vi bevisar att även den enklaste varianten av detta problem är NP-svår och utvecklar konstant-faktor approximationsalgoritmer. Vårt viktigaste tekniska bidrag kopplar samman kant-begränsade och nod-begränsade versionerna av tätaste delgraf-problemet. Vi visar först att algoritmer för problemet At Least k Nodes Densest Subgraph (DalkS) kan approximera problemet At Least h edges Densest Subgraph (ATLEASTHEDGESDSP), och utökar sedan algoritmen för DalkS för att hantera färgade kantbegränsningar för att lösa ALHCEDGESDSP.

Den tredje delen av avhandlingen studerar grafinterventioner för rättvisa i nätverk. Vi undersöker två rättvisemått, PageRank-rättvisa och träfftids-rättvisa, och utvecklar metoder för att balansera inflytande och förbättra tillgänglighet mellan grupper. För varje demografisk grupp kvantifierar summan av PageRank-poäng inom den gruppens inflytande. PageRank-rättvisa mäter hur långt den nuvarande gruppvisa influensfördelningen avviker från ett givet mål. Vi formulerar PageRank-rättvisaproblemet som ett optimeringsproblem som justerar kantvikter så att den resulterande grafen uppnår en gruppvis influensfördelning så nära målet som möjligt. Optimeringsproblemet involverar ett icke-konvext mål över en konvex genomförbar mängd under praktiska begränsningar, såsom att inte lägga till nya kanter och begränsa kantviktningsskalan. Vi löser detta PageRank rättvisemaximerings-problem med hjälp av effektiv projicerad gradientnedstigning, och bevisar konvergens till en stationär punkt. För träfftids-rättvisa i bipartita grafer formulerar vi två problem, att minimera medelvärdet (BMAH) och det maximala träfftidsvärdet (BMMH) från en grupp till en annan via strategiska kanttillägg. Vi tillhandahåller en (2+epsilon)-approximation för BMAH genom att kombinera snabb slumpvandrings-simulering med girig supermodulär minimering. För det mer utmanande BMMH-problemet utvecklar vi två tillvägagångssätt, det första utnyttjar dess koppling till BMAH-problemet, och det andra använder en metod baserad på det asymmetriska k center-problemet. Båda tillvägagångssätten ger bevisliga approximationsgarantier för BMMH.

Algoritmerna och analystekniker som presenteras i denna avhandling bidrar till den växande mängden arbete om rättvisa och mångfald i algoritmiska system. Genom att formalisera nya problemvarianter som fångar realistiska begränsningar i interaktiva och nätverksbaserade miljöer, och genom att tillhandahåller approximationsalgoritmer med bevisliga garantier, utökar detta arbete verktygslådan som finns tillgänglig för att hantera utmaningar kring rättvisa och mångfald i beräkningssystem.

Link to DiVA