Backpropagation durch kombinatorische Algorithmen: Identität mit Projektion funktioniert

Die Einbettung diskreter Löser als differenzierbare Schichten hat modernen tiefen Lernarchitekturen kombinatorische Ausdruckskraft und Fähigkeiten zur diskreten Schlussfolgerung verliehen. Da die Ableitung dieser Löser null oder undefiniert ist, ist eine sinnvolle Ersetzung für ein effektives gradientenbasiertes Lernen entscheidend. Bisherige Ansätze stützen sich auf die Glättung des Löser mittels Eingabestörungen, die Relaxierung des Löser zu kontinuierlichen Problemen oder die Interpolation der Verlustlandschaft mit Techniken, die typischerweise zusätzliche Löseraufrufe erfordern, zusätzliche Hyperparameter einführen oder die Leistung beeinträchtigen. Wir schlagen einen konsistenten Ansatz vor, der die Geometrie des diskreten Lösungsraums ausnutzt, um den Löser im Rückwärtsdurchlauf als negative Identität zu behandeln, und liefern zudem eine theoretische Begründung hierfür. Unsere Experimente zeigen, dass ein so einfacher, hyperparameterfreier Ansatz in zahlreichen Anwendungen – wie Backpropagation durch diskrete Stichproben, tiefe Graphenübereinstimmung und Bildretrieval – mit komplexeren vorherigen Methoden konkurrieren kann. Darüber hinaus ersetzen wir den früher vorgeschlagenen, problem- und labelabhängigen Margin durch ein generisches Regularisierungsverfahren, das eine Kostenkollapsierung verhindert und die Robustheit erhöht.