Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26604
Titel: A flexible framework for solving constrained ratio problems in machine learning
Sonstige Titel: Ein flexibles Framework zur Lösung von beschränkten Bruchproblemen im maschinellen Lernen
Verfasser: Bühler, Thomas
Sprache: Englisch
Erscheinungsjahr: 2014
SWD-Schlagwörter: Maschinelles Lernen
Optimierung
Graphpartitionierung
Cluster-Analyse
Freie Schlagwörter: machine learning
optimization
graph partitioning
clustering
community detection
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: The (constrained) optimization of a ratio of non-negative set functions is a problem appearing frequently in machine learning. As these problems are typically NP hard, the usual approach is to approximate them through convex or spectral relaxations. While these relaxations can be solved globally optimal, they are often too loose and thus produce suboptimal results. In this thesis we present a flexible framework for solving such constrained fractional set programs (CFSP). The main idea is to transform the combinatorial problem into an equivalent unconstrained continuous problem. We show that such a tight relaxation exists for every CFSP. It turns out that the tight relaxations can be related to a certain type of nonlinear eigenproblem. We present a method to solve nonlinear eigenproblems and thus optimize the corresponding ratios of in general non-differentiable differences of convex functions. While the global optimality cannot be guaranteed, we can prove the convergence to a solution of the associated nonlinear eigenproblem. Moreover, in practice the loose spectral relaxations are outperformed by a large margin. Going over to constrained fractional set programs and the corresponding nonlinear eigenproblems leads to a greater modelling flexibility, as we demonstrate for several applications in data analysis, namely the optimization of balanced graph cuts, constrained local clustering, community detection via densest subgraphs and sparse principal component analysis.
Die (beschränkte) Optimierung von nichtnegativen Bruchfunktionen über Mengen ist ein häufig auftretendes Problem im maschinellen Lernen. Da diese Probleme typischerweise NP-schwer sind, besteht der übliche Ansatz darin, sie durch konvexe oder spektrale Relaxierungen zu approximieren. Diese können global optimal gelöst werden, sind jedoch häufig zu schwach und führen deshalb zu suboptimalen Ergebnissen. In dieser Arbeit stellen wir ein flexibles Verfahren zur Lösung solcher beschränkten fraktionellen Mengenprogramme (BFMP) vor. Die Grundidee ist, das kombinatorische in ein equivalentes unbeschränktes kontinuerliches Problem umzuwandeln. Wir zeigen dass dies für jedes BFMP möglich ist. Die strenge Relaxierung kann dann mit einem nichtlinearen Eigenproblem in Bezug gebracht werden. Wir präsentieren ein Verfahren zur Lösung der nichtlinearen Eigenprobleme und damit der Optimierung der im Allgemeinen nichtdifferenzierbaren und nichtkonvexen Bruchfunktionen. Globale Optimalität kann nicht garantiert werden, jedoch die Lösung des nichtlinearen Eigenproblems. Darüberhinaus werden in der Praxis die schwachen spektralen Relaxierungen mit einem großen Vorsprung übertroffen. Der Übergang zu BFMPs und nichtlinearen Eigenproblemen führt zu einer verbesserten Flexibilität in der Modellbildung, die wir anhand von Anwendungen in Graphpartitionierung, beschränkter lokaler Clusteranalyse, dem Finden von dichten Teilgraphen, sowie dünnbesetzter Hauptkomponentenanalyse demonstrieren.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-61590
hdl:20.500.11880/26660
http://dx.doi.org/10.22028/D291-26604
Erstgutachter: Hein, Matthias
Tag der mündlichen Prüfung: 17-Jun-2015
SciDok-Publikation: 19-Jun-2015
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
phd_thesis_thomas_buehler_2015.pdf2,87 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.