Studio e Confronto di Tre Algoritmi di Spectral Clustering con Vincolo di Group Fairness

Il machine learning (ML) ha ad oggi molteplici applicazioni: ad esempio, è utilizzato dai motori di ricerca per interpretare le richieste degli utenti; permette la realizzazione di pubblicità mirate; è alla base dei sistemi di guida autonoma. Per quanto potente, il ML è vulnerabile a pregiudizi, che possono essere presenti nei dati o incorporati negli stessi algoritmi. Il crescente impiego di strumenti di ML per l’automatizzazione di decisioni che possono avere forti implicazioni sociali, ha fatto emergere la necessità di sviluppare strategie che promuovono l’equità (fairness) negli algoritmi di ML. Esistono numerosi studi che approfondiscono il problema, che variano a seconda degli algoritmi analizzati e della definizione di fairness considerata. Questo lavoro si concentra sullo spectral clustering con vincolo di group fairness. Tale vincolo assicura che, in ogni insieme del raggruppamento determinato dall’algoritmo di spectral clustering, la percentuale di elementi con una determinata caratteristica di interesse sia sempre la stessa. In altre parole, si mira a garantire che tale caratteristica non influenzi il processo di raggruppamento dei dati. Lo scopo di questo elaborato di tesi è quello di illustrare e motivare matematicamente tre algoritmi di spectral clustering che implementano il vincolo, nonché confrontarne le performance su alcuni datasets reali e sintetici. Si mostra che i tre algoritmi, equivalenti da un punto di vista matematico, ottengono risultati del tutto analoghi sia per quanto riguarda la capacità di riflettere un’eventuale similarità o dissimilarità fra i dati sia per quanto riguarda l’equità. Inoltre, si mostra che i tre algoritmi implementano efficacemente il vincolo di equità ottenendo sempre raggruppamenti più equi rispetto all’algoritmo di spectral clustering tradizionale. Tuttavia, solo uno dei tre ha un costo computazionale paragonabile a quello dell'algoritmo senza vincolo ed è quindi adatto anche a datasets di grandi dimensioni.