Warum ist eine 0-1-Verlustfunktion nicht umsetzbar?

12

In Ian Goodfellows Deep Learning- Buch steht das geschrieben

Manchmal ist die Verlustfunktion, die uns tatsächlich am Herzen liegt (z. B. Klassifizierungsfehler), nicht effizient zu optimieren. Beispielsweise ist eine genaue Minimierung des erwarteten 0-1-Verlusts selbst für einen linearen Klassifizierer normalerweise nicht möglich (exponentiell in der Eingabedimension). In solchen Situationen optimiert man normalerweise stattdessen eine Ersatzverlustfunktion, die als Proxy fungiert, aber Vorteile hat.

Warum ist ein 0-1-Verlust unlösbar oder wie ist er in den Eingabedimensionen exponentiell?

Samra Irshad
quelle

Antworten:

18

Die 0-1-Verlustfunktion ist nicht konvex und diskontinuierlich, daher können (Sub-) Gradientenmethoden nicht angewendet werden. Für die binäre Klassifizierung mit einem linearen Separator kann diese Verlustfunktion so formuliert werden, dass das , das den Durchschnittswert der Indikatorfunktion 1 ( y i β x i0 ) über alle i Abtastwerte minimiert . Dies ist in den Eingängen exponentiell, da es für jedes Paar zwei mögliche Werte gibt, gibt es 2 nβ1(yichβxich0)ich2n mögliche Konfigurationen, um auf zu prüfennGesamtprobenpunkte. Dies ist bekanntermaßen NP-hart. Die Kenntnis des aktuellen Werts Ihrer Verlustfunktion gibt keinen Hinweis darauf, wie Sie möglicherweise Ihre aktuelle Lösung ändern sollten, um sie zu verbessern, da Sie ableiten könnten, ob Gradientenmethoden für konvexe oder kontinuierliche Funktionen verfügbar wären.

Don Walpola
quelle
1
Sehr guter Punkt - in der Praxis sind Zufallssuche oder erschöpfende Suche die einzigen Methoden, mit denen das Minimum einer solchen Verlustfunktion ermittelt werden kann, oder?
DeltaIV
2
^^ oder evolutionäre / schwarmbasierte Intelligenzmethoden vielleicht?
Samra Irshad
@samrairshad Ja, in der Tat ist ein 0: 1-Verlust bei evolutionären Methoden nicht ungewöhnlich.
John Doucette
Bevor ich von der Zufallssuche zu komplexen Evolutions- / Schwarmalgorithmen übergehe, würde ich die Cross-Entropy-Methode (CEM) untersuchen.
Maxy
1

Der Klassifizierungsfehler ist tatsächlich manchmal nachvollziehbar. Es kann mithilfe der Nelder-Mead-Methode effizient - wenn auch nicht genau - optimiert werden, wie in diesem Artikel gezeigt:

https://www.computer.org/csdl/trans/tp/1994/04/i0420-abs.html

"Dimensionsreduktion ist der Prozess der Transformation mehrdimensionaler Vektoren in einen niedrigdimensionalen Raum. Bei der Mustererkennung ist es häufig erwünscht, dass diese Aufgabe ohne signifikanten Verlust von Klassifizierungsinformationen ausgeführt wird. Der Bayes-Fehler ist jedoch ein ideales Kriterium für diesen Zweck; Es ist bekannt, dass es für die mathematische Behandlung notorisch schwierig ist. Folglich wurden in der Praxis suboptimale Kriterien verwendet. Wir schlagen ein alternatives Kriterium vor, das auf der Schätzung des Bayes-Fehlers basiert und hoffentlich näher am optimalen Kriterium liegt als die derzeit verwendeten Kriterien Ein Algorithmus zur linearen Dimensionsreduktion, der auf diesem Kriterium basiert, wird konzipiert und implementiert. Experimente zeigen seine überlegene Leistung im Vergleich zu herkömmlichen Algorithmen. "

Der hier erwähnte Bayes-Fehler ist im Grunde der 0: 1-Verlust.

Diese Arbeit wurde im Rahmen der linearen Dimensionsreduktion durchgeführt. Ich weiß nicht, wie effektiv es wäre, Deep-Learning-Netzwerke zu trainieren. Aber der Punkt ist und die Antwort auf die Frage: 0-1 Verlust ist nicht allgemein unlösbar. Es kann zumindest für einige Modelltypen relativ gut optimiert werden.

ljubomir
quelle