Tiefes Clustering durch probabilistische Ratio-Cut-Optimierung

Wir schlagen einen neuartigen Ansatz zur Optimierung des Graphen-Ratio-Cut vor, indem wir die binären Zuordnungen als Zufallsvariablen modellieren. Wir leiten eine obere Schranke für den erwarteten Ratio-Cut sowie eine erwartungstreue Schätzung seines Gradienten her, um die Parameter der Zuordnungsvariablen in einem Online-Setting zu lernen. Die durch unsere probabilistische Methode (PRCut) erzielte Clustering-Leistung übertrifft die Rayleigh-Quotient-Relaxation des kombinatorischen Problems, deren Erweiterungen für Online-Lernen sowie mehrere weit verbreitete Methoden. Wir zeigen, dass das PRCut-Clustering eng mit der Ähnlichkeitsmaßnahme übereinstimmt und, wenn labelbasierte Ähnlichkeiten zur Verfügung stehen, die Leistung eines überwachten Klassifikators erreichen kann. Dieser neuartige Ansatz kann aus der Box kommende selbstüberwachte Darstellungen nutzen, um konkurrenzfähige Ergebnisse zu erzielen, und fungiert zudem als Evaluationsmethode für die Qualität solcher Darstellungen.