Vorteile der Lösung eines Problems durch Formulierung einer Kostenfunktion, die global optimierbar ist

9

Dies ist eine eher allgemeine Frage (dh nicht unbedingt spezifisch für Statistiken), aber ich habe einen Trend in der maschinellen Lern- und statistischen Literatur festgestellt, bei dem Autoren den folgenden Ansatz bevorzugen:

Ansatz 1 : Erhalten Sie eine Lösung für ein praktisches Problem, indem Sie eine Kostenfunktion formulieren, für die es möglich ist (z. B. aus rechnerischer Sicht), eine global optimale Lösung zu finden (z. B. durch Formulierung einer konvexen Kostenfunktion).

eher, als:

Ansatz 2 : Erhalten Sie eine Lösung für dasselbe Problem, indem Sie eine Kostenfunktion formulieren, für die wir möglicherweise keine global optimale Lösung erhalten können (z. B. können wir nur eine lokal optimale Lösung dafür erhalten).

Beachten Sie, dass die beiden Probleme streng genommen unterschiedlich sind. Die Annahme ist, dass wir die global optimale Lösung für die erste finden können, aber nicht für die zweite.

Abgesehen von anderen Überlegungen (z. B. Geschwindigkeit, einfache Implementierung usw.) suche ich:

  1. Eine Erklärung dieses Trends (zB mathematische oder historische Argumente)
  2. Vorteile (praktisch und / oder theoretisch) für die Befolgung von Ansatz 1 anstelle von 2 bei der Lösung eines praktischen Problems.
Amelio Vazquez-Reina
quelle

Antworten:

3

Meiner Meinung nach sollte das Ziel darin bestehen, die Funktion zu optimieren, an der Sie interessiert sind. Wenn dies zufällig die Anzahl der Fehlklassifizierungen ist - und nicht etwa eine Binomialwahrscheinlichkeit -, sollten Sie versuchen, die Anzahl der Fehlklassifizierungen zu minimieren. Aus der Anzahl der genannten praktischen Gründe (Geschwindigkeit, Implementierung, Instabilität usw.) ist dies jedoch möglicherweise nicht so einfach und sogar unmöglich. In diesem Fall beschließen wir, die Lösung zu approximieren.

Ich kenne grundsätzlich zwei Approximationsstrategien; Entweder entwickeln wir Algorithmen, die versuchen, die Lösung des ursprünglichen Problems direkt zu approximieren, oder wir formulieren das ursprüngliche Problem als direkt lösbares Problem neu (z. B. konvexe Relaxationen).

Ein mathematisches Argument für den Vorzug eines Ansatzes gegenüber dem anderen ist, ob wir a) die Eigenschaften der tatsächlich berechneten Lösung verstehen können und b) wie gut sich die Lösung der Lösung des Problems annähert, an dem wir tatsächlich interessiert sind.

Ich kenne viele Ergebnisse in Statistiken, bei denen wir die Eigenschaften einer Lösung für ein Optimierungsproblem nachweisen können. Für mich scheint es schwieriger zu sein, die Lösung eines Algorithmus zu analysieren, bei dem Sie keine mathematische Formulierung dessen haben, was er berechnet (z. B. dass er ein bestimmtes Optimierungsproblem löst). Ich werde sicherlich nicht behaupten, dass Sie nicht können, aber es scheint ein theoretischer Vorteil zu sein , wenn Sie eine klare mathematische Formulierung dessen geben können, was Sie berechnen.

Es ist mir unklar, ob solche mathematischen Argumente Ansatz 1 gegenüber Ansatz 2 praktische Vorteile bringen . Es gibt sicherlich jemanden da draußen, der keine Angst vor einer nicht konvexen Verlustfunktion hat .

NRH
quelle
Vielen Dank für den Hinweis auf Yann LeCuns Vortrag. Ich freue mich darauf, es zu sehen.
Amelio Vazquez-Reina
1

@NRH hat eine Antwort auf diese Frage gegeben (vor über 5 Jahren), daher biete ich nur einen Ansatz 3 an, der die Ansätze 1 und 2 kombiniert.

Ansatz 3 :

  1. Formulieren und lösen Sie ein konvexes oder auf jeden Fall global optimierbares (nicht unbedingt konvexes) Problem, das dem Problem, das Sie wirklich lösen möchten, "nahe" kommt.
  2. Verwenden Sie die global optimale Lösung aus Schritt 1 als Startlösung (Anfang) für ein nicht konvexes Optimierungsproblem, das Sie wirklich lösen möchten (oder mehr als das in Schritt 1 gelöste Problem). Hoffen Sie, dass Ihre Ausgangslösung in der "Region der Anziehung" zum globalen Optimum im Verhältnis zur Lösungsmethode liegt, die zur Lösung des nicht konvexen Optimierungsproblems verwendet wird, das Sie wirklich lösen möchten.
Mark L. Stone
quelle
Bitte geben Sie ein konkretes Beispiel.
HoraceT
Es ist nicht genau Marks Fall, aber ein üblicher Ansatz bei vielen Computer-Vision-Problemen besteht darin, eine abgestufte Nichtkonvexität zu verwenden, um eine Folge von "guten" lokalen Optima für verwandte Probleme zu erhalten. Ein konkretes Beispiel ist der grobe bis feine optische Fluss, bei dem für ein Bildpaar eine Grobskalierungsausrichtung verwendet wird, um die Suche in feineren Maßstäben zu starten und sich durch ein Paar Bildpyramiden zu bewegen .
GeoMatt22
yeinebxyeinein+bbxein=eeineinÖptichmeinl,b=bbÖptichmeinlals Startwerte für die nichtlinearen kleinsten Quadrate. Die Probleme sind ähnlich, aber die Fehler werden unterschiedlich behandelt. Es gibt viele Probleme, bei denen eine nicht konvexe Strafe erwünscht ist (für Schritt 2), die jedoch durch eine konvexe Strafe für Schritt 1 ersetzt werden könnte. Es sind auch mehrere Iterationen möglich.
Mark L. Stone
@ GeoMatt22 Was Sie beschrieben haben, ist im Geiste ähnlich und überschneidet sich mit sogenannten Homotopie-Methoden, bei denen ein Weg zur Lösung des Problems, das Sie wirklich lösen möchten, durch Lösen einer Reihe von Problemen ermittelt wird, bei denen ein Parameter wie z Eine Beschränkung wird schrittweise geändert und aufeinanderfolgende Probleme gelöst, für die das erste Problem leicht von Grund auf zu lösen ist. Es könnte tatsächlich der Fall sein, dass das erste Problem konvex oder auf andere Weise lösbar ist, spätere Probleme jedoch möglicherweise nicht, obwohl ihre optimale Lösung im Parameter kontinuierlich sein kann.
Mark L. Stone