Warum konvexe Optimierung für theoretisches maschinelles Lernen studieren?

27

Ich arbeite am theoretischen maschinellen Lernen - Transferlernen, um genau zu sein - für meine Promotion.

  • Warum sollte ich aus Neugier einen Kurs zur konvexen Optimierung belegen?

  • Welche Erkenntnisse aus der konvexen Optimierung kann ich für meine Forschung zum theoretischen maschinellen Lernen nutzen?

Upendra Pratap Singh
quelle
2
Es ist unklar, ob Sie gegen den konvexen Teil, den Optimierungsteil oder beides Einwände erheben.
Mehrdad
Beachten Sie, dass die von Ihnen akzeptierte Antwort eindeutig falsch ist. Vielleicht können Sie sich diese Frage noch einmal ansehen und eine Antwort wählen, die viel sinnvoller ist.
Xji
Convex Optimization and Math Optimization ist ein Tool zum Erstellen von Modellen. Mit dieser Technik werden Modelle erstellt, gesteuert und Parameter für verständliche Phänomene bis zu einer gewissen Ungewissheit gefunden.
Bruziuz
Beim maschinellen Lernen geht es darum, Funktionsannäherungen wie bei Beratungsmethoden zu erstellen. Soweit Sie eine Concept-Select-Funktion kennen, mit der Verluste (die nicht konvex sind oder im schlimmsten Fall Indikatorvariablen enthalten) annähernd minimiert werden.
Bruziuz
Zu Ihrer
Information:

Antworten:

59

Algorithmen für maschinelles Lernen verwenden ständig Optimierung. Wir minimieren Verluste oder Fehler oder maximieren irgendeine Art von Bewertungsfunktionen. Gradient Descent ist der "Hallo Welt" -Optimierungsalgorithmus, der in wahrscheinlich jedem maschinellen Lernkurs behandelt wird. Bei Regressions- oder Klassifikationsmodellen ist dies offensichtlich, aber auch bei Aufgaben wie Clustering suchen wir nach einer Lösung, die optimal zu unseren Daten passt (z. B. minimiert k-means die Quadratsumme innerhalb des Clusters). Wenn Sie also verstehen möchten, wie die Algorithmen für maschinelles Lernen funktionieren, hilft es, mehr über Optimierung zu lernen. Wenn Sie beispielsweise Hyperparameter-Tuning durchführen müssen, verwenden Sie auch direkt die Optimierung.

Man könnte argumentieren, dass die konvexe Optimierung für das maschinelle Lernen nicht so interessant sein sollte, da wir anstelle der konvexen Funktionen häufig auf Verlustoberflächen wie die folgende stoßen, die alles andere als konvex sind .

Beispiel einer realen, nicht konvexen Verlustlandschaft.

(Quelle: https://www.cs.umd.edu/~tomg/projects/landscapes/ und arXiv: 1712.09913 )

Wie in anderen Antworten erwähnt, ist die konvexe Optimierung jedoch schneller, einfacher und weniger rechenintensiv. Daher ist es häufig einfacher, ein Problem zu "konvexisieren" (konvexe Optimierung wird vereinfacht) und anschließend die nicht konvexe Optimierung zu verwenden. Beispielsweise werden beim maschinellen Lernen häufig Algorithmen für die Gradientenabnahme und dergleichen verwendet, insbesondere für neuronale Netze, da sie "funktionieren", skalieren und weitgehend in verschiedene Software implementiert sind. Dennoch sind sie nicht das Beste, was wir bekommen und haben können , wie in Ali Rahimis Vortrag auf der NIPS 2017 besprochen .

Andererseits scheinen nichtkonvexe Optimierungsalgorithmen wie evolutionäre Algorithmen in der ML-Community immer mehr Beachtung zu finden, z. B. scheint das Training neuronaler Netze durch Neuroevolution ein aktuelles Forschungsthema zu sein (siehe auch arXiv: 1712.07897 ).

Tim
quelle
5
Diese Antwort scheint sich nicht auf "konvex" zu
beziehen
@ hxd1011 Ich habe es kommentiert.
Tim
Gute Antwort! Behandelt wirklich, wie wichtig die Optimierung für ML ist und wie sich ML vereinfacht, indem konvexe Approximationen verwendet werden, die mit Gradientenabstieg funktionieren.
ChuckCottrill
Dies sollte die akzeptierte Antwort sein.
Jan Kukacka
11

Ich denke, hier gibt es zwei Fragen.

  • Warum Optimierung studieren?
  • Warum konvexe Optimierung?

Ich denke, @Tim hat eine gute Antwort, warum Optimierung. Ich stimme voll und ganz zu und würde jedem empfehlen, der sich für maschinelles Lernen interessiert, um die kontinuierliche Optimierung zu meistern. Weil der Optimierungsprozess / das Finden der besseren Lösung im Laufe der Zeit der Lernprozess für einen Computer ist.

Ich möchte mehr darüber sprechen, warum wir an konvexen Funktionen interessiert sind. Der Grund ist einfach: Konvexe Optimierungen sind "leichter zu lösen", und wir haben eine Menge zuverlässiger Algorithmen zu lösen.

Aber ist die Welt konvex? Warum von Konvexität besessen? Überprüfen Sie diese Metapher

Ein Polizist sieht einen betrunkenen Mann unter einer Straßenlaterne nach etwas suchen und fragt, was der Betrunkene verloren hat. Er sagt, er habe seine Schlüssel verloren und beide schauen zusammen unter die Straßenlaterne. Nach ein paar Minuten fragt der Polizist, ob er sicher ist, dass er sie hier verloren hat, und der Betrunkene antwortet, nein, und dass er sie im Park verloren hat. Der Polizist fragt, warum er hier sucht, und der Betrunkene antwortet: "Hier ist das Licht".

Haitao Du
quelle
2
Aber metaphorisch erhalten Sie deshalb eine Taschenlampe. Die Suche nach den Schlüsseln im Dunkeln ist schwer bis unmöglich, daher passen Sie das Problem in ein Problem an, das Sie zu lösen wissen. Wenn Sie an einem Problem mit nicht konvexen Algorithmen arbeiten und eine Lösung finden, die 3 Millionen US-Dollar kostet, und ich ein ähnliches Problem mit der konvexen Optimierung habe, nehme ich meine Antwort und finde eine Lösung für das nicht konvexe Problem, das 2 kostet Millionen Dollar, ich habe eine bessere Antwort gefunden.
Prosfilaes
Diese Antwort ist auf so vielen Ebenen fehlerhaft. Der Vergleich der konvexen Analyse mit dem Straßenbeleuchtungseffekt ist einfach falsch . Ich rate Ihnen, das Einführungslehrbuch Convex Optimization von Boyd und Vandenberghe zu lesen, um mehr über das Thema zu erfahren.
Digio
2

Der wichtigste Aspekt ist, dass maschinelles Lernen auf Probleme angewendet wird, für die es keine optimale Lösung gibt. Das Beste, was Sie tun können, ist eine gute Annäherung zu finden.

Im Gegensatz dazu gibt es bei Optimierungsproblemen eine optimale Lösung, die jedoch normalerweise nicht in angemessener Zeit oder mit angemessener Rechenleistung gefunden werden kann.

Die von Ihnen verwendeten Tools und Algorithmen unterscheiden sich grundlegend. Ich würde also sagen, dass es keinen unmittelbaren Vorteil hat, an einem Optimierungskurs teilzunehmen, aber es ist immer gut, etwas über verwandte Bereiche zu wissen. Wenn Sie ein Optimierungsproblem erkennen, wissen Sie, dass Sie es nicht mit maschinellen Lernalgorithmen, sondern mit Optimierungsalgorithmen angehen sollten. Das allein ist viel wert, würde ich sagen.

Toby
quelle
33
Ja, beim maschinellen Lernen suchen wir nach den besten Annäherungen. Aber Sie irren sich, wenn Sie sagen, dass beide Dinge "grundlegend anders" sind. ML-Algorithmen verwenden die Optimierung, um Verlustfunktionen zu minimieren und die optimalen Parameter unter Berücksichtigung der Daten und des Ziels zu finden. Wenn Sie Ihre Hyperparameter optimieren, suchen Sie nach einer optimalen Kombination dieser Parameter. In jedem Fall maximieren oder minimieren Sie etwas, um Ihr Ziel zu erreichen, und verwenden daher eine Art Optimierung.
Tim
@ Tim: Stimmt, ich hätte das anders formulieren sollen.
Toby
17
Wenn Sie damit einverstanden sind, sollten Sie es wahrscheinlich umformulieren.
Tim
19
Diese Antwort ist offensichtlich falsch. Eine erhebliche Anzahl von Problemen beim maschinellen Lernen resultiert aus Optimierungsproblemen.
Setzen Sie Monica am
2
Die Behauptung, dass bei "Optimierungsproblemen in der Regel keine optimale Lösung gefunden werden kann", ist falsch. Insbesondere im Kontext der konvexen Optimierung (nach der OP fragt) kann die optimale Lösung leicht gefunden werden (zum Beispiel wird garantiert , dass der Gradientenabstieg mit abnehmender Lernrate zum Optimum einer konvexen Funktion konvergiert). Das große Problem ist, dass viele Probleme beim maschinellen Lernen nicht konvex sind .
Jan Kukacka
2

Wie hxd1011 sagte, sind konvexe Probleme sowohl theoretisch als auch (typischerweise) in der Praxis leichter zu lösen. Selbst bei nicht konvexen Problemen beginnen viele Optimierungsalgorithmen mit "Schritt 1. Reduzieren Sie das Problem auf einen konvexen" (möglicherweise innerhalb einer while-Schleife).

Ähnliches passiert beim nichtlinearen Rootfinding. Normalerweise lautet die Lösung (z. B. mit der Newton-Methode) "Schritt 1. Reduzieren Sie auf ein lineares Problem, weil wir wissen, wie man diese löst".

Federico Poloni
quelle
1

Wenn Ihre Interessen in der (konvexen) Optimierung von Deep-Learning-Anwendungen (Sie erwähnen das in der Praxis bei neuronalen Netzen weit verbreitete Transfer-Learning) liegen, empfehle ich Ihnen nachdrücklich, Kapitel 8 (Optimierung für das Training von tiefen neuronalen Netzen) von http zu lesen : //www.deeplearningbook.org/

Es gibt eine Diskussion über die konvexe Optimierung und warum sie noch nicht so erfolgreich war, wenn tiefe neuronale Netze angewendet wurden. Vielleicht könnten Sie in diesem Bereich Nachforschungen anstellen, die den gegenwärtigen Konsens ändern!

FXQuantTrader
quelle
0

Wie ich von Jerome H. Friedman gehört habe, gehören Methoden, die im maschinellen Lernen entwickelt wurden, in der Tat nicht zur maschinellen Lerngemeinschaft.

Maschinelles Lernen ist aus meiner Sicht eher eine Sammlung verschiedener Methoden aus anderen Bereichen.

Aus Sicht des statistischen Lernens sind die drei Hauptfragen für die Regression und Klassifikation:

  1. Was ist Funktionsfamilie, aus der Sie Approximator ziehen

  2. Was ist ein Kriterium, wie Sie eine Funktion ziehen

  3. Was ist eine Methode, um die beste Funktion zu finden


Konstruktiv mit (1) umzugehen - es ist nicht so offensichtlich, wie die Verwendung der mathematischen Optimierung helfen kann

Konstruktiv mit (2) umzugehen - es ist offensichtlich, dass das Ziel das Ziel ist. Und die mathematische Optimierung kann dabei helfen.

Um (3) konstruktiv zu bearbeiten, ist eine mathematische Optimierung erforderlich.


Es gibt mehrere Teile der mathematischen Optimierung:

  1. Konvexe Optimierung / Konvexe Analyse - sehr cooles Gebiet der Mathematik. Nichtdifferenzierbarkeit ist kein Problem. Und es gibt 50 Verallgemeinerungen von konvexen Funktionen, von denen zwei in Bezug auf die Anwendung nützlich sind, nämlich quasikonvex und logkonkav.

Es gibt auch Möglichkeiten, mit "Stochastizität" umzugehen, auch wenn "Niemand weiß, wie man stochastische konvexe Optimierungen löst".

  1. NonConvex-Optimierung - Normalerweise bedeuten Menschen damit etwas, was kontinuierlich objektiv ist, aber die Krümmung kann variieren. Die Menschen auf diesem Planeten wissen nicht, wie sie es genau lösen sollen. Und in der Tat machen alle Methoden Hebelwirkung in (1)

  2. Kombinatorische Optimierung - es ist noch wilder als (2), jetzt können Sie für Parameter, die Sie finden, sogar keinen Minusoperator anwenden. Ein Beispiel sind "Regionen" in Entscheidungsbäumen. Es gibt also zwei Möglichkeiten, wie Sie damit umgehen können: a) Konvexifizieren Sie das Problem und wenden Sie die folgenden Methoden an: (1) Bilden Sie rohe Gewalt. Funktioniert nicht für eine große Anzahl von Parametern. c) Machen Sie rohe Gewalt, aber mit einigen gierigen Schritten. Das macht CART.


Zumindest glaube ich, dass ich Sie davon überzeugen kann:

I) Die konvexe Optimierung ist für die meisten Optimierungsprobleme von zentraler Bedeutung.

II) "01:15 Optimierung ist in der Tat ein größeres Thema als ML oder AI, aber es ist in der Tat ein größeres Thema." ( https://www.youtube.com/watch?v=uF3htLwUHn0&t=992s )

Bruziuz
quelle
Dies ist nach den Maßstäben dieser Website eine kurze Antwort. Glauben Sie, Sie könnten sie erweitern? Andernfalls eignet es sich am besten als Kommentar.
Silberfischchen
Okay. Ich werde erweitern, aber in der Tat ist es möglich, einen Artikel über die Verbindung mit verschiedenen Bereichen zu schreiben. Tatsächlich habe ich Stephen P. Boyd zu Fragen bezüglich der Frage, an die die Leute vorher und wann gedacht haben, befragt . Er sagte, dass die heutige Welt zerbrochen sei.
Bruziuz
1
@Silverfish habe ich aktualisiert, jetzt ist es Langtext statt eines Satzes.
Bruziuz