Title (eng)
Efficient algorithms for problems in clustering and fairness
Author
Advisor
Monika Henzinger
Kathrin Hanauer
Assessor
Aristides Gionis
Stefan Neumann
Abstract (deu)
Basierend auf Trends hin zu immer größeren Datenmengen zum Training moderner Machine Learning- und KI-Systeme, ist die Verarbeitung und Analyse großer Datensätze zu einer der wichtigsten Aufgaben in der Informatik geworden. Dabei führen der Umfang und die Vielfalt der Datensätze -- von statischen vektorwertigen Mengen, über Graphen, bis hin zu Live-Daten -- sowohl aus theoretischer als auch aus praktischer Sicht zu zahlreichen Herausforderungen. Beispielsweise passen derart große Datensätze in der Regel nicht in den Hauptspeicher eines einzelnen Computers, was einer grundlegenden theoretischen Annahme des klassischen Wort-RAM Maschinenmodells widerspricht. Um diesen Herausforderungen gerecht zu werden, wurde eine Reihe neuer algorithmischer Modelle entwickelt, wie z.B. das Streaming-, das Distributed Computing- oder das Online-Modell. Darüber hinaus sind Techniken zur Datenreduzierung, wie zum Beispiel Datenkomprimierung und Clustering, in den Vordergrund der anwendungsorientierten Algorithmenforschung gerückt. In dieser Arbeit konzentrieren wir uns auf zwei wichtige Konzepte im Design von Algorithmen zur Analyse und Reduzierung großer Datenmengen und untersuchen sie sowohl aus theoretischer als auch aus experimenteller Sicht. Das erste Konzept bezieht sich auf Clustering, eine der grundlegenden Aufgaben der Datenanalyse. Die Fähigkeit, ähnliche Datenpunkte zu gruppieren, ist für viele Anwendungen von entscheidender Bedeutung. Sie ermöglicht es uns, Daten zu komprimieren, z.B. über Coresets oder Vektordatenbanken, Muster in den Daten zu finden oder repräsentative Elemente in den Daten zu identifizieren. Der andere Aspekt ist sozio-technischer Art. Viele der Datensätze, die wir analysieren enthalten sensible personenbezogene Daten, welche dann in automatisierten Prozessen als Entscheidungsgrundlage dienen. Da solche Systeme zunehmenden Einfluß auf das allt\"agliche Leben haben, müssen wir sicherstellen können, dass keinem Nutzer ungerechtfertigte Diskrimination widerfährt. In den letzten Jahren gab es eine Reihe an Beispielen wo KI-basierte Entscheidungsprozesse rassistische, sexistische oder klassistische Entscheidungen trafen, was zeigt, dass der Bedarf für faire Systeme in der Praxis gegeben ist. Motiviert durch diese beiden Themen sind die wichtigsten Ergebnisse dieser Arbeit. - Einführung des fairen Paging-Problems, einer natürlichen Erweiterung des klassischen Online-Paging-Problems unter dem Aspekt der algorithmischen Fairness. Wir zeigen, dass das faire Problem strikt schwieriger ist als die zuvor untersuchten Versionen des Paging-Problems, und wir stellen die ersten bekannten oberen und unteren Schranken für dieses Problem vor. - Die besten bekannten Algorithmen für das binäre Matrixfaktorisierungsproblem unter verschiedenen Metriken. Das Ziel dieses Problems besteht darin eine niedrigrangige Approximation einer binärwertigen Matrix zu finden. Zusätzlich stellen wir die ersten Algorithmen für dieses Problem im Streaming- und Distributed-Modell vor. Wir verwenden eine Äquivalenz zu $k$-means Clustering sowie Sketching und Enumeration, um Algorithmen zu entwickeln, die in einfach exponentieller Zeit zum Rang $k$ der Outputmatrix laufen. Auch evaluieren wir mehrere praktische Algorithmen für dieses Problem auf experimentelle Weise und zeigen, dass unsere algorithmischen Ideen verwendet werden können, um bessere praktische Lösungen für dichte Matrizen zu erhalten. - Der erste Algorithmus mit beweisbaren Garantien für das $k$-Means Problem, der in Zeit nahezu linear zur Anzahl der Vektoren im Datensatz läuft, und keine Abhängigkeit von der Anzahl der Cluster $k$ aufweist. Für dünnbesetzte Matrizen zeigen wir außerdem, dass keine Laufzeitabhängigkeit von der Dimensionalität des Datensatzes besteht. Wir zeigen, dass eine aggressive Dimensionalitätsreduktion auf eine einzige Dimension zu einem Algorithmus mit polynomialem Approximationsverhältnis führt, der sowohl theoretische als auch praktische Vorteile aufweist. Weiters evaluieren wir den Algorithmus experimentell und zeigen, dass er im Vergleich zu Basisalgorithmen für Clustering und Coreset-Konstruktion große Geschwindigkeitsvorteile bietet. - Der erste praktische Graph-Clustering-Algorithmus, der Expander-Zerlegung und die Expander-Hierarchie in der Praxis anwendet. Unter Verwendung eines auf Random Walks basierenden Expander-Zerlegungsalgorithmus entwickeln wir einen Algorithmus zur Sparsifizierung und Lösung des Normalized Cut Problems auf großen Graphen und führen umfangreiche Experimente durch, die seine konkurrenzfähige Leistung zeigen.
Abstract (eng)
Driven by the developments of modern machine learning and AI systems, processing and analyzing large datasets has become one of the most important tasks in computer science. The volume and diversity of datasets, from static vector-valued sets to graphs to live data streams, presents numerous challenges from both a theoretical and practical point of view. For example, large datasets usually do not fit into a single computer's memory, contrary to a fundamental theoretical assumption of the classical random access machine model. To model these challenges, a number of new models, such as the streaming, distributed, or online models, were developed. Moreover, data reduction techniques, such as data compression and clustering, have moved to the forefront of application-minded algorithms design. In this thesis we focus on two important concepts in the study of algorithms for analyzing and reducing large datasets and study them from both theoretical and experimental viewpoints: The first is clustering, one of the fundamental data analysis tasks. Being able to group similar data points is of crucial importance for many applications. It allows us to compress data, for example via coresets or vector databases, or to find patterns in the data, as well as to identify representative elements in the data. The other aspect is of a socio-technical nature. As we are often processing datasets containing sensitive personal data and use them in automated decision processes, the lives of people are increasingly governed by digital systems. Therefore, we need to ensure that no user is discriminated against unfairly. Many examples of automated decision making exhibiting racial-, gender- or other biases have been observed, which shows that a focus on algorithmic fairness is tantamount. Motivated by these two topics, the main results of this thesis are: - Introduction of the fair paging problem, a natural extension of the well-studied online paging problem under a perspective of algorithmic fairness. We show that the fair problem is strictly harder than previously studied versions of the paging problem, and we introduce the first known upper and lower bounds for this problem. - The current best-known algorithms under several metrics for the binary matrix factorization problem, where the goal is to find a low-rank approximation of a binary matrix. Additionally, we introduce the first algorithms for this problem in the streaming and distributed settings. We employ an equivalence to $k$-means clustering, as well as sketching and enumeration to obtain algorithms running in time singly exponential in the rank of the output matrix $k$. We also experimentally evaluate several algorithms for this problem and show that our algorithmic ideas may be used to obtain better solutions for non-sparse matrices in practice. - The first algorithm with provable guarantees for the $k$-means problem which runs in time near linear in the number of input vectors while exhibiting no dependence on the number of clusters $k$. For sparse matrices it additionally exhibits no running time dependence on the dimensionality of the dataset. We show that aggressive dimensionality reduction to a single dimension yields an algorithm with polynomial approximation ratio that is both theoretically and practically feasible. We also thoroughly evaluate the algorithm experimentally and show that it produces large speedups over baseline algorithms for clustering and coreset construction. - The first practical graph clustering algorithm applying expander decomposition and the expander hierarchy in practice. Using a random walk-based expander decomposition algorithm, we engineer a novel state of the art algorithm for sparsifying and solving the normalized cut problem on large graphs, and we perform extensive experiments demonstrating its competitive performance.
Keywords (deu)
Theoretische InformatikAlgorithmenClustering
Keywords (eng)
Theoretical Computer ScienceAlgorithmsClusteringUnsupervised Learning
Subject (deu)
Type (deu)
Persistent identifier
Extent (deu)
xi, 187 Seiten : Illustrationen
Number of pages
202
Study plan
Doktoratsstudium der technischen Wissenschaften Informatik
[UA]
[786]
[880]
Association (deu)
Title (eng)
Efficient algorithms for problems in clustering and fairness
Author
Abstract (deu)
Basierend auf Trends hin zu immer größeren Datenmengen zum Training moderner Machine Learning- und KI-Systeme, ist die Verarbeitung und Analyse großer Datensätze zu einer der wichtigsten Aufgaben in der Informatik geworden. Dabei führen der Umfang und die Vielfalt der Datensätze -- von statischen vektorwertigen Mengen, über Graphen, bis hin zu Live-Daten -- sowohl aus theoretischer als auch aus praktischer Sicht zu zahlreichen Herausforderungen. Beispielsweise passen derart große Datensätze in der Regel nicht in den Hauptspeicher eines einzelnen Computers, was einer grundlegenden theoretischen Annahme des klassischen Wort-RAM Maschinenmodells widerspricht. Um diesen Herausforderungen gerecht zu werden, wurde eine Reihe neuer algorithmischer Modelle entwickelt, wie z.B. das Streaming-, das Distributed Computing- oder das Online-Modell. Darüber hinaus sind Techniken zur Datenreduzierung, wie zum Beispiel Datenkomprimierung und Clustering, in den Vordergrund der anwendungsorientierten Algorithmenforschung gerückt. In dieser Arbeit konzentrieren wir uns auf zwei wichtige Konzepte im Design von Algorithmen zur Analyse und Reduzierung großer Datenmengen und untersuchen sie sowohl aus theoretischer als auch aus experimenteller Sicht. Das erste Konzept bezieht sich auf Clustering, eine der grundlegenden Aufgaben der Datenanalyse. Die Fähigkeit, ähnliche Datenpunkte zu gruppieren, ist für viele Anwendungen von entscheidender Bedeutung. Sie ermöglicht es uns, Daten zu komprimieren, z.B. über Coresets oder Vektordatenbanken, Muster in den Daten zu finden oder repräsentative Elemente in den Daten zu identifizieren. Der andere Aspekt ist sozio-technischer Art. Viele der Datensätze, die wir analysieren enthalten sensible personenbezogene Daten, welche dann in automatisierten Prozessen als Entscheidungsgrundlage dienen. Da solche Systeme zunehmenden Einfluß auf das allt\"agliche Leben haben, müssen wir sicherstellen können, dass keinem Nutzer ungerechtfertigte Diskrimination widerfährt. In den letzten Jahren gab es eine Reihe an Beispielen wo KI-basierte Entscheidungsprozesse rassistische, sexistische oder klassistische Entscheidungen trafen, was zeigt, dass der Bedarf für faire Systeme in der Praxis gegeben ist. Motiviert durch diese beiden Themen sind die wichtigsten Ergebnisse dieser Arbeit. - Einführung des fairen Paging-Problems, einer natürlichen Erweiterung des klassischen Online-Paging-Problems unter dem Aspekt der algorithmischen Fairness. Wir zeigen, dass das faire Problem strikt schwieriger ist als die zuvor untersuchten Versionen des Paging-Problems, und wir stellen die ersten bekannten oberen und unteren Schranken für dieses Problem vor. - Die besten bekannten Algorithmen für das binäre Matrixfaktorisierungsproblem unter verschiedenen Metriken. Das Ziel dieses Problems besteht darin eine niedrigrangige Approximation einer binärwertigen Matrix zu finden. Zusätzlich stellen wir die ersten Algorithmen für dieses Problem im Streaming- und Distributed-Modell vor. Wir verwenden eine Äquivalenz zu $k$-means Clustering sowie Sketching und Enumeration, um Algorithmen zu entwickeln, die in einfach exponentieller Zeit zum Rang $k$ der Outputmatrix laufen. Auch evaluieren wir mehrere praktische Algorithmen für dieses Problem auf experimentelle Weise und zeigen, dass unsere algorithmischen Ideen verwendet werden können, um bessere praktische Lösungen für dichte Matrizen zu erhalten. - Der erste Algorithmus mit beweisbaren Garantien für das $k$-Means Problem, der in Zeit nahezu linear zur Anzahl der Vektoren im Datensatz läuft, und keine Abhängigkeit von der Anzahl der Cluster $k$ aufweist. Für dünnbesetzte Matrizen zeigen wir außerdem, dass keine Laufzeitabhängigkeit von der Dimensionalität des Datensatzes besteht. Wir zeigen, dass eine aggressive Dimensionalitätsreduktion auf eine einzige Dimension zu einem Algorithmus mit polynomialem Approximationsverhältnis führt, der sowohl theoretische als auch praktische Vorteile aufweist. Weiters evaluieren wir den Algorithmus experimentell und zeigen, dass er im Vergleich zu Basisalgorithmen für Clustering und Coreset-Konstruktion große Geschwindigkeitsvorteile bietet. - Der erste praktische Graph-Clustering-Algorithmus, der Expander-Zerlegung und die Expander-Hierarchie in der Praxis anwendet. Unter Verwendung eines auf Random Walks basierenden Expander-Zerlegungsalgorithmus entwickeln wir einen Algorithmus zur Sparsifizierung und Lösung des Normalized Cut Problems auf großen Graphen und führen umfangreiche Experimente durch, die seine konkurrenzfähige Leistung zeigen.
Abstract (eng)
Driven by the developments of modern machine learning and AI systems, processing and analyzing large datasets has become one of the most important tasks in computer science. The volume and diversity of datasets, from static vector-valued sets to graphs to live data streams, presents numerous challenges from both a theoretical and practical point of view. For example, large datasets usually do not fit into a single computer's memory, contrary to a fundamental theoretical assumption of the classical random access machine model. To model these challenges, a number of new models, such as the streaming, distributed, or online models, were developed. Moreover, data reduction techniques, such as data compression and clustering, have moved to the forefront of application-minded algorithms design. In this thesis we focus on two important concepts in the study of algorithms for analyzing and reducing large datasets and study them from both theoretical and experimental viewpoints: The first is clustering, one of the fundamental data analysis tasks. Being able to group similar data points is of crucial importance for many applications. It allows us to compress data, for example via coresets or vector databases, or to find patterns in the data, as well as to identify representative elements in the data. The other aspect is of a socio-technical nature. As we are often processing datasets containing sensitive personal data and use them in automated decision processes, the lives of people are increasingly governed by digital systems. Therefore, we need to ensure that no user is discriminated against unfairly. Many examples of automated decision making exhibiting racial-, gender- or other biases have been observed, which shows that a focus on algorithmic fairness is tantamount. Motivated by these two topics, the main results of this thesis are: - Introduction of the fair paging problem, a natural extension of the well-studied online paging problem under a perspective of algorithmic fairness. We show that the fair problem is strictly harder than previously studied versions of the paging problem, and we introduce the first known upper and lower bounds for this problem. - The current best-known algorithms under several metrics for the binary matrix factorization problem, where the goal is to find a low-rank approximation of a binary matrix. Additionally, we introduce the first algorithms for this problem in the streaming and distributed settings. We employ an equivalence to $k$-means clustering, as well as sketching and enumeration to obtain algorithms running in time singly exponential in the rank of the output matrix $k$. We also experimentally evaluate several algorithms for this problem and show that our algorithmic ideas may be used to obtain better solutions for non-sparse matrices in practice. - The first algorithm with provable guarantees for the $k$-means problem which runs in time near linear in the number of input vectors while exhibiting no dependence on the number of clusters $k$. For sparse matrices it additionally exhibits no running time dependence on the dimensionality of the dataset. We show that aggressive dimensionality reduction to a single dimension yields an algorithm with polynomial approximation ratio that is both theoretically and practically feasible. We also thoroughly evaluate the algorithm experimentally and show that it produces large speedups over baseline algorithms for clustering and coreset construction. - The first practical graph clustering algorithm applying expander decomposition and the expander hierarchy in practice. Using a random walk-based expander decomposition algorithm, we engineer a novel state of the art algorithm for sparsifying and solving the normalized cut problem on large graphs, and we perform extensive experiments demonstrating its competitive performance.
Keywords (deu)
Theoretische InformatikAlgorithmenClustering
Keywords (eng)
Theoretical Computer ScienceAlgorithmsClusteringUnsupervised Learning
Subject (deu)
Type (deu)
Persistent identifier
Number of pages
202
Association (deu)
License
- Citable links
- Other links
- Managed by
- Details
- Usage statistics-
- Metadata
- Export formats