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.

Traffic problems are an essential part of our everyday lives, from daily commuter traffic to the development of urban infrastructures and global freight transportation. A key challenge is to optimize the allocation of resources to minimize costs or maximize efficiency. Optimal Transportation (OT) theory provides a mathematical framework to formally describe such problems and their solution, taking into account complex objectives and constraints. Over the years, various methods have been developed to solve OT problems. However, traditional methods reach their limits when solution spaces are continuous and the consideration of traffic density is important. The Dynamic Monge-Kantorovich (DMK) algorithm developed in recent years offers a solution to these challenges. It models traffic problems using dynamic equations and enables the solution of transportation problems in continuous two-dimensional solution spaces. It also allows traffic constraints due to traffic density to be taken into account, such as prioritizing busy routes over many smaller, similar routes. With these properties, DMK offers a practical method for solving real-world problems.

Nevertheless, the DMK algorithm reaches its limits in certain situations. Although many practical scenarios are defined in continuous space and therefore require a continuous solution, a discrete solution, for example in the form of a graph, is often required for implementation in the real world. In addition, the algorithm often requires a longer execution time, which can affect its practical applicability in time-critical scenarios. Furthermore, the DMK model has not yet been sufficiently tested in its practical application, especially in the field of machine learning, where OT problems play a major role.

In this thesis, we extend the aforementioned limitations of the DMK and show the practical application of the model in classical machine learning contexts. We first present different methods to transform the continuous solutions of the original two-dimensional space in which the DMK model is defined into practically realizable discrete solutions. In the process, we transform DMK solutions, which are available as density distributions, into graphs and hypergraphs that represent discrete solutions. Furthermore, we show that the DMK algorithm can be stopped before its termination without strongly affecting the solution quality. In time-critical practical applications, the DMK algorithm can thus find effective solutions in a short time by determining an optimal stopping time.

The second part of this thesis focuses on the practical applicability of the DMK model. Based on the theoretical findings described above, we develop algorithms for the practical use of a variant of the DMK model, the Graph-DMK algorithm, in various machine learning tasks. Specifically, we show how DMK can be used for the clustering of networks, the extraction of networks from images, and the classification of images. Our results show the potential of the DMK algorithm to successfully solve a variety of machine learning tasks.

Thus, this thesis extends the previous limits of the DMK model and demonstrates its practical application.