Universität Tübingen
Optimal Transport: The Dynamical Monge-Kantorovich Model as a Bridge between Theory and Applications
Abstract
Verkehrsprobleme sind ein wesentlicher Bestandteil unseres Alltags, angefangen beim täglichen Berufsverkehr über die Entwicklung städtischer Infrastrukturen bis hin zum globalen Gütertransport. Eine zentrale Herausforderung besteht dabei darin, die Ressourcenallokation zu optimieren, um Kosten zu minimieren oder Effizienz zu maximieren. Die Theorie des optimalen Transports (OT) bietet einen mathematischen Rahmen zur formalen Beschreibung solcher Probleme und ihrer Lösung unter Berücksichtigung komplexer Ziele und Einschränkungen. Im Laufe der Jahre wurden verschiedene Methoden entwickelt, um OT-Probleme zu lösen. Traditionelle Methoden stoßen jedoch an Grenzen, wenn Lösungsräume kontinuierlich sind und die Berücksichtigung der Verkehrsdichte von Bedeutung ist. Der in den letzten Jahren entwickelte Dynamic Monge-Kantorovich (DMK) Algorithmus bietet eine Lösung für diese Herausforderungen. Er modelliert Verkehrsprobleme mithilfe dynamischer Gleichungen und ermöglicht die Lösung von Transportproblemen in kontinuierlichen zweidimensionalen Lösungsräumen. Außerdem erlaubt er die Berücksichtigung von Verkehrseinschränkungen aufgrund der Verkehrsdichte, wie etwa die Priorisierung stark frequentierter Routen gegenüber vielen kleineren, ähnlich verlaufenden Wegen. Mit diesen Eigenschaften bietet DMK eine praktische Methode zur Lösung realweltlicher Probleme. Dennoch stößt der DMK-Algorithmus in bestimmten Situationen an seine Grenzen. Viele praktische Szenarien sind zwar im kontinuierlichen Raum definiert und erfordern daher eine kontinuierliche Lösung, aber für die Umsetzung in der realen Welt ist oft eine diskrete Lösung erforderlich, zum Beispiel in Form eines Graphen. Außerdem benötigt der Algorithmus häufig eine längere Ausführungszeit, was seine praktische Anwendbarkeit in zeitkritischen Szenarien beeinträchtigen kann. Darüber hinaus wurde das DMK-Modell bisher noch nicht in seiner praktischen Anwendung, insbesondere im Bereich des maschinellen Lernens, wo OT-Probleme eine große Rolle spielen, ausreichend getestet. In dieser Arbeit erweitern wir die genannten Grenzen des DMK und zeigen die praktische Anwendung des Modells in klassischen Machine-Learning-Kontexten. Wir stellen zunächst verschiedene Methoden vor, um die kontinuierlichen Lösungen des ursprünglichen zweidimensionalen Raums, in dem das DMK-Modell definiert ist, in praktisch umsetzbare diskrete Lösungen zu transformieren. Dabei wandeln wir DMK-Lösungen, die als Dichteverteilungen vorliegen, in Graphen und Hypergraphen um, die diskrete Lösungen darstellen. Außerdem zeigen wir, dass der DMK-Algorithmus vor seiner Terminierung angehalten werden kann, ohne die Lösungsqualität stark zu beeinträchtigen. In zeitkritischen praktischen Anwendungen kann der DMK-Algorithmus somit durch die Festlegung einer optimalen Anhaltezeit effektive Lösungen in kurzer Zeit finden. Der zweite Teil dieser Arbeit fokussiert sich auf die praktische Anwendbarkeit des DMK-Modells. Basierend auf den oben beschriebenen theoretischen Erkenntnissen entwickeln wir Algorithmen zur praktischen Nutzung einer Variante des DMK-Modells, dem Graph-DMK-Algorithmus, in verschiedenen Aufgaben des maschinellen Lernens. Konkret zeigen wir, wie DMK für das Clustern von Netzwerken, die Extraktion von Netzwerken aus Bildern und die Klassifizierung von Bildern eingesetzt werden kann. Unsere Ergebnisse zeigen das Potenzial des DMK-Algorithmus, eine Vielzahl von maschinellen Lernaufgaben erfolgreich zu lösen. Damit erweitert diese Arbeit die bisherigen Grenzen des DMK-Modells und demonstriert seine praktische Anwendung.
Author and committee
dc:creator, dc:contributor.*- Author
-
- Baptista Theuerkauf, Diego Alejandro
Identifiers
dc:identifier.*- Identifier
- hdl:10900/156980