03.06.2024
Lucas Fabian Naumann veröffentlicht auf der International Conference on Machine Learning (ICML)
SECAI-Stipendiat Lucas Fabian Naumann hat zusammen mit Fellow Björn Andres und seinem Team zwei offene Fragen zu hochdimensionalen geometrischen Objekten, den so genannten „lifted multicut polytopes“, beantwortet. Seine Arbeit [1], die in Verbindung mit Clustering-Problemen im Bereich des Maschinellen Lernens steht, wurde zur Veröffentlichung auf der International Conference on Machine Learning (ICML), einer der führenden Konferenzen in diesem Bereich, bewilligt. In der Begründung wird die technische Schwierigkeit eines von Fabians Beweisen gewürdigt und die Schlussfolgerung gezogen, dass seine Arbeit, obwohl sie rein theoretisch ist, zu Verbesserungen der Algorithmen führen wird.
Im Wesentlichen geht es in der Veröffentlichung um die Struktur der zulässigen Lösungen des „lifted multicut“-Problems, eines kombinatorischen Optimierungsproblems, dessen zulässige Lösungen eins zu eins mit den Zerlegungen eines Graphen korrespondieren, indem sie angeben, welche Kanten zu schneiden sind. Dieses Problem hat viele Anwendungen im Bereich Computer Vision, wie zum Beispiel „multiple object tracking“. Insbesondere ist es von Interesse, graphentheoretische Charakterisierungen von Facetten zu finden. Dies sind Teilmengen von zulässigen Lösungen mit bestimmten Eigenschaften, die eine Beschleunigung von Branch-and-Cut-Algorithmen zur genauen Lösung des Problems ermöglichen. In der Vergangenheit sind viele Klassen von Facetten untersucht und charakterisiert worden. Diese Arbeit befasst sich mit zwei von ihnen, für die bisher keine solche Charakterisierung gefunden werden konnte: den sogenannten Lower-Box- und Cut-Facetten.
„Während es vergleichsweise einfach war, eine solche effizient entscheidbare Charakterisierung für die Lower-Box-Facetten zu finden, erwiesen sich die Cut-Facetten als herausfordernder. Nach einer Weile der vergeblichen Suche und viel Frustration meinerseits erkannten wir, dass wir zwar noch keine Charakterisierung geben können, unser Wissen über die Struktur jedoch ausreicht, um zu beweisen, dass jede solche Charakterisierung NP-schwer zu entscheiden sein muss“, sagt Fabian. Auch wenn dieses Resultat ursprünglich nicht beabsichtigt war, ist es doch von größerer Bedeutung, da die Struktur, die für die NP-schwere Charakterisierung von Cut-Facetten verantwortlich ist, existiert, wenn man einen Graphen durch Schneiden seiner Kanten zerlegt, wie beim „lifted multicut“-Problem, aber nicht, wenn man ihn durch Entfernen von Knoten zerlegt. Daher wird eine Verlagerung der Forschung auf kombinatorische Optimierungsprobleme für die Zerlegung von Graphen durch das Entfernen von Knoten erwartet.
Obwohl Fabian schon vorher an dem Papier arbeitete und von SECAI-Fellow Björn Andres und seinem Team unterstützt wurde, konnte er sich dank des SECAI-Stipendiums voll auf die Forschung konzentrieren. „Ohne das Stipendium wäre die Arbeit wahrscheinlich nicht rechtzeitig fertig geworden“, sagt er.
