Warum ist Deep Learning trotz der schlechten VC-Dimension sehr beliebt?

86

Die Vapnik-Chervonenkis (VC) -Dimensionsformel für neuronale Netze reicht von bis , wobei im ungünstigsten Fall die Anzahl der Kanten und ist die Anzahl der Knoten. Die Anzahl der Trainingsmuster, die für eine starke Generalisierungsgarantie erforderlich sind, ist linear zur VC-Dimension.O(E)O(E2)O(E2V2)EV

Dies bedeutet, dass für ein Netzwerk mit Milliarden von Kanten, wie im Fall erfolgreicher Deep-Learning-Modelle, der Trainingsdatensatz im besten Fall Milliarden von Trainingsmustern benötigt, im schlimmsten Fall Billiarden. Die größten Trainingssets haben derzeit etwa hundert Milliarden Proben. Da nicht genügend Trainingsdaten vorliegen, ist es unwahrscheinlich, dass Deep-Learning-Modelle verallgemeinern. Stattdessen passen sie die Trainingsdaten über. Dies bedeutet, dass die Modelle bei Daten, die sich von den Trainingsdaten unterscheiden, keine gute Leistung erbringen, was für das maschinelle Lernen eine unerwünschte Eigenschaft ist.

Warum sind Deep-Learning-Ergebnisse laut VC-Dimensionsanalyse angesichts der Unfähigkeit zu verallgemeinern, so hochgelobt? Nur eine hohe Genauigkeit für einige Datensätze zu haben, bedeutet nicht viel für sich. Gibt es etwas Besonderes an Deep Learning-Architekturen, das die VC-Dimension erheblich reduziert?

Wenn Sie der Meinung sind, dass die Analyse der VC-Dimension nicht relevant ist, geben Sie bitte Hinweise / Erklärungen, dass Deep Learning verallgemeinernd und nicht überpassend ist. Dh hat es einen guten Rückruf UND Präzision oder nur einen guten Rückruf? Ein 100% iger Rückruf ist ebenso trivial wie eine 100% ige Präzision. Beides in die Nähe von 100% zu bringen ist sehr schwierig.

Im Gegenteil, hier ist ein Beweis dafür, dass tiefes Lernen überpassend ist. Ein Overfit-Modell ist leicht zu täuschen, da es deterministisches / stochastisches Rauschen enthält. Das folgende Bild zeigt ein Beispiel für eine Überanpassung.

Beispiel für Unter-, Anpassung und Überanpassung.

Lesen Sie auch die Antworten auf diese Frage mit niedrigerem Rang , um die Probleme mit einem Überpassungsmodell trotz guter Genauigkeit der Testdaten zu verstehen.

Einige haben geantwortet, dass Regularisierung das Problem einer großen VC-Dimension löst . Siehe diese Frage zur weiteren Diskussion.

yters
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
DW
7
Ich denke nicht, dass Fragen, warum etwas "hochgespielt" ist, gut sind. Die Antwort lautet "weil Menschen". Menschen interessieren sich für Dinge aus einer Vielzahl von Gründen, einschließlich Marketing.
Luk32
Deep Learning funktioniert in der Praxis. Es könnte überanpassend sein. Es könnte völlig ungerechtfertigt sein. Es könnte sein, dass sie Geheimnisse des Universums von einer eltrichen Gottheit lernen. Der Hype geht jedoch von Praktikern aus, die plötzlich in der Lage sind, 30 Zeilen Code zu schreiben und einer Kamera beizubringen, Unterschriften zu scannen und mit gespeicherten zu vergleichen, um Bankgeschäfte zu validieren. Oder unbekannte Personen auf Fotos markieren. Vielleicht haben Sie die Zeile "Es ist keine Beleidigung, wenn es wahr ist" gehört? Nun, es ist kein Hype, wenn es funktioniert. Es gibt viele Probleme, bei denen es nicht funktioniert, und einen übermäßigen Hype. Aber es funktioniert in der Praxis.
Stella Biderman
@StellaBiderman Einfache Werkzeuge für Standardtechniken des maschinellen Lernens sind in jeder Hinsicht gut. Das Interesse scheint jedoch mehr mit der vermeintlichen Lernfähigkeit von DNNs zu tun zu haben, die vielleicht mit der menschlichen Fähigkeit konkurriert, die angesichts der VC-Analyse des Modells überfordert zu sein scheint. Eine solch hohe VC-Dimension impliziert, dass die Modelle nicht generalisieren und stattdessen die Datensätze speichern, wodurch sie sehr spröde werden. Alle kontroversen Beispielpapiere scheinen diesen Punkt zu demonstrieren.
27.
@ Gerrit Ich bin mir nicht sicher, ob die Bearbeitung wirklich hilfreich war. Ich wette, dass mehr Leute wissen, was VC-Dimension ist, als wissen, wofür es steht.
David Richerby

Antworten:

75

"Wenn die Karte und das Gelände nicht übereinstimmen, vertrauen Sie dem Gelände."

Es ist nicht wirklich klar, warum Deep Learning so gut funktioniert, aber alte Konzepte aus der Lerntheorie wie VC-Dimensionen scheinen nicht sehr hilfreich zu sein.

Die Sache ist heiß umstritten, siehe zB:

In Bezug auf die Frage der widersprüchlichen Beispiele wurde das Problem entdeckt in:

  • C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich, Tiefer mit Faltungen .

Es wird weiterentwickelt in:

  • I. Goodfellow, J. Shlens, C. Szegedy, Erklären und Nutzen von Gegenbeispielen .

Es gibt viel Nacharbeit.

Martin Berger
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
DW
Wenn Sie sagen "Es gibt viel Nacharbeit", beziehen Sie sich auf das letzte Papier von 2014? Die ersten beiden Artikel, die Sie erwähnen, sind ziemlich neu. Könnten Sie die Papiere, auf die Sie sich beziehen, aktualisieren?
VF1
2
Stark +1 für "Wenn Karte und Gelände nicht übereinstimmen, vertraue dem Gelände." Die Modelle funktionieren in der Praxis hervorragend, unabhängig davon, ob die Mathematik dies vorschreibt oder nicht. Aus wissenschaftlicher Sicht passiert dies die ganze Zeit und wenn irgendetwas Probleme interessanter macht. Niemand las Rasborows und Rudichs Arbeit über natürliche Beweise und sagte: "Nun, ich denke, P gegen NP ist keine interessante Frage." Sie gingen und fanden heraus, dass es möglich sein könnte, algebraische Geometrie zur Durchführung der Komplexitätstheorie zu verwenden. Aus wissenschaftlicher Sicht sind Probleme, die über unser Verständnis hinausgehen , nicht schlimmer, sondern besser .
Stella Biderman
65

"Angesichts der Unfähigkeit von Deep Learning zu verallgemeinern, nach VC dimensionale Analyse [...]"

Nein, das sagt die VC-Dimensionsanalyse nicht aus. Die VC-Dimensionsanalyse liefert einige ausreichende Bedingungen, unter denen eine Verallgemeinerung gewährleistet ist. Aber das Gegenteil ist nicht unbedingt so. Auch wenn Sie diese Bedingungen nicht erfüllen, kann die ML-Methode dennoch verallgemeinern.

Anders ausgedrückt: Deep Learning funktioniert besser als es die VC-Dimensionsanalyse erwarten lässt (besser als es die VC-Analyse "vorhersagt"). Das ist ein Mangel der VC-Dimensionsanalyse, kein Mangel des tiefen Lernens. Es bedeutet nicht, dass tiefes Lernen fehlerhaft ist. Es bedeutet vielmehr, dass wir nicht wissen, warum Deep Learning funktioniert - und die VC-Analyse kann keine nützlichen Erkenntnisse liefern.

Eine hohe VC-Dimension bedeutet nicht, dass Deep Learning getäuscht werden kann. Ein hohes VC-Maß garantiert überhaupt nichts darüber, ob es in praktischen Situationen getäuscht werden kann. Die VC-Dimension bietet eine unidirektionale Grenze im ungünstigsten Fall: Wenn Sie diese Bedingungen erfüllen, passieren gute Dinge, aber wenn Sie diese Bedingungen nicht erfüllen, wissen wir nicht, was passieren wird (vielleicht passieren trotzdem gute Dinge, wenn Die Natur verhält sich besser als der schlimmste Fall, die VC-Analyse verspricht nicht, dass gute Dinge nicht passieren können / werden .

Es könnte sein, dass die VC-Dimension des Modellraums groß ist (sie umfasst möglichst sehr komplexe Muster), die Natur jedoch durch einfache Muster erklärt wird und der ML-Algorithmus das in der Natur vorhandene einfache Muster lernt (z. B. aufgrund von Regularisierung). - In diesem Fall wäre die VC-Dimension hoch, aber das Modell würde sich verallgemeinern (für das bestimmte Muster, das in der Natur vorhanden ist).

Das heißt, es gibt immer mehr Beweise dafür, dass tiefes Lernen durch widersprüchliche Beispiele getäuscht werden kann . Aber seien Sie vorsichtig mit Ihrer Argumentationskette. Die Schlussfolgerungen, die Sie ziehen, folgen nicht den Prämissen, mit denen Sie begonnen haben.

DW
quelle
6
Eine hohe VC-Dimension ist schwieriger zu verallgemeinern (zumindest in gewissem Sinne, wenn es um beliebige Verteilungen geht). Die untere Grenze des Verallgemeinerungsfehlers bedeutet genau, dass für die Anzahl der im Vergleich zur VC-Dimension kleinen Stichproben eine Verteilung existiert, die einen beliebigen Algorithmus relativ dazu darstellt tritt ein hoher Generalisierungsfehler auf (mit hoher Wahrscheinlichkeit). Ω(dn)
Ariel
5
-1 für "Hohe VC-Abmessungen garantieren überhaupt nichts." Dies ist nicht wahr: Eine hohe VC-Dimension impliziert eine untere Grenze der Probenkomplexität für das PAC-Lernen. Eine gute Antwort sollte Worst-Case- und Real-Life-Verteilungen betreffen.
Sasho Nikolov
1
@SashoNikolov, guter Punkt - danke! Bearbeitet
DW
Dieser Beitrag wurde in minderer Qualität bewertet. Angesichts des Inhalts, der Länge, der Stimmen und der Qualität ist dies lächerlich und zeigt dies hier, aber es braucht möglicherweise Meta, weil etwas wirklich falsch ist.
Evil
23

Industrie Leute haben keine Rücksicht auf VC Dimension, Hooligans ...

Im Ernst, obwohl das PAC-Modell (zumindest meiner Meinung nach) eine elegante Form des Lernens darstellt und komplex genug ist, um interessante Konzepte und Fragen aufzuwerfen (z. B. die VC-Dimension und deren Zusammenhang mit der Komplexität der Stichproben). Es hat sehr wenig mit realen Situationen zu tun.

Denken Sie daran, dass Sie im PAC-Modell zur Verarbeitung beliebiger Verteilungen verpflichtet sind. Dies bedeutet, dass Ihr Algorithmus auch mit konträren Verteilungen umgehen muss. Beim Versuch, einige Phänomene in der realen Welt zu lernen, gibt Ihnen niemand "gegnerische Daten", um Ihre Ergebnisse durcheinander zu bringen. Daher kann es viel zu stark sein, dass eine Konzeptklasse lernfähig sein muss. Manchmal können Sie den Generalisierungsfehler unabhängig von der VC-Dimension für eine bestimmte Verteilungsklasse festlegen. Dies ist der Fall bei Randbegrenzungen, die unabhängig von der VC-Dimension formuliert werden. Sie können einen geringen Generalisierungsfehler versprechen, wenn Sie einen hohen empirischen Spielraum garantieren können (was natürlich nicht bei allen Verteilungen der Fall ist, z. B. nehmen Sie zwei enge Punkte in der Ebene mit entgegengesetzten Tags und konzentrieren Sie die Verteilung auf diese).

Abgesehen vom PAC-Modell und der VC-Dimension liegt der Hype meiner Meinung nach in der Tatsache begründet, dass sie einfach zu funktionieren scheinen und bei Aufgaben erfolgreich sind, die zuvor nicht möglich waren (eine der neuesten Errungenschaften, die mir in den Sinn kommen, ist AlphaGo). Ich weiß sehr wenig über neuronale Netze, daher hoffe ich, dass jemand mit mehr Erfahrung einspringt, aber meines Wissens gibt es noch keine guten Garantien (definitiv nicht wie im PAC-Modell). Vielleicht könnte man unter den richtigen Voraussetzungen den Erfolg von neuronalen Netzen formal rechtfertigen (ich gehe davon aus, dass es Arbeiten zur formalen Behandlung von neuronalen Netzen und zum "tiefen Lernen" gibt, also hoffe ich, dass Leute mit mehr Wissen zu diesem Thema einige Artikel verlinken können). .

Ariel
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
DW
15

Angesichts der Unfähigkeit von Deep Learning zu verallgemeinern,

Ich weiß nicht, woher du das nimmst. Empirisch wird Generalisierung als Punktzahl (z. B. Genauigkeit) für unsichtbare Daten angesehen.

Die Antwort, warum CNNs verwendet werden, ist einfach: CNNs funktionieren viel besser als alles andere . Siehe ImageNet 2012 zum Beispiel:

  • CNNs: 15,315% (das war ein frühes Beispiel. CNNs sind jetzt viel besser. Bei etwa 4% Top-5-Fehler)
  • Bester Nicht-CNN: 26,172% Top-5-Fehler ( Quelle - meines Wissens nach sind Techniken, die keine CNNs verwenden, nicht unter 25% Top-5-Fehler gefallen )

Erstellen Sie einen Klassifikator, der besser ist und zu dem die Leute wechseln werden.

UPDATE: Ich werde jedem eine Antwort geben, der veröffentlichte Beweise dafür liefert, dass maschinelles Lernen im Allgemeinen leicht zu täuschen ist, wie diese Beweise für Deep Learning.

Das ist nicht der Fall. Sie können einen Klassifikator erstellen, der für ein einfaches Dataset äußerst einfach ist. Es wird nicht möglich sein, es zu täuschen (es spielt keine Rolle, was "einfach" bedeutet), aber es ist auch nicht interessant.

Martin Thoma
quelle
3
Ein niedriger Fehler impliziert keine Verallgemeinerung. Dies ist eine notwendige, aber nicht ausreichende Bedingung.
Heute,
3
@yters Bitte definieren Sie dann die Verallgemeinerung.
Martin Thoma
5
@yters, dieser Kommentar lässt mich denken, dass Sie nicht viel über maschinelles Lernen gelesen haben. Martin sagte Genauigkeit auf unsichtbaren Daten . Sie sprechen von Genauigkeit der Trainingsdaten. Sie haben im Grunde genommen Recht mit der Verallgemeinerung, aber bitte nehmen Sie zur Kenntnis, dass dies auch alle anderen hier verstehen .
Ken Williams
1
Ich bin mir ziemlich sicher, dass Ken (und viele Leute auf dieser Seite, einschließlich ich selbst) das wissen. Wenn Ihr Testsatz jedoch nicht Ihren Datensatz darstellt, können Sie keine Aussage zur Verallgemeinerung treffen. Obwohl es sich lohnt, daran zu denken, verstehe ich nicht, wie Ihnen dies in irgendeiner Weise bei dieser Frage hilft. Sie müssen lediglich davon ausgehen, dass Ihr Test-Set Ihre Daten zur Produktionszeit darstellt. In der Tat ist es wirklich einfach zu zeigen, dass Sie jeden Klassifikator beliebig schlecht machen können, wenn die Trainingsbeispiele nicht die Verteilung darstellen.
Martin Thoma
2
Das ist offensichtlich. Sie können nicht erwarten, dass sich ein Modell gut verallgemeinert, wenn es darauf trainiert ist, die falschen Daten zu validieren. Sie brauchen bessere Daten, kein besseres Modell.
Emre
9

Die Antwort mit einem Wort lautet "Regularisierung". Die naive VC-Dimensionsformel gilt hier nicht wirklich, da die Regularisierung voraussetzt, dass die Gewichte nicht allgemein sind. Nur ein winziger (infinitesimaler?) Anteil der Gewichtskombinationen hat nach der Regularisierung einen akzeptablen Verlust. Die wahre Dimension ist infolgedessen um viele Größenordnungen geringer, so dass bei den Trainingssets, die wir haben, eine Verallgemeinerung auftreten kann. Die tatsächlichen Ergebnisse belegen, dass es in der Regel nicht zu einer Überanpassung kommt.

David Khoo
quelle
2
Ich habe die wiederholte Behauptung gesehen, dass echte Ergebnisse zeigen, dass tiefes Lernen verallgemeinert wird. Was genau sind die Ergebnisse, die eine Verallgemeinerung zeigen? Alles, was ich bisher gesehen habe, ist, dass DL bei bestimmten Datensätzen niedrige Fehlerraten erzielt, was nicht bedeutet, dass DL verallgemeinert.
Uhr
3
Es zeigt gute Ergebnisse ("gut" = besser als andere ML-Methoden) für Daten , für die es nicht trainiert wurde . Ich bin mir nicht sicher, wie Sie die Verallgemeinerung sonst praktisch messen wollen.
lvilnis
3

Wir sprechen das Papier an: Um Deep Learning zu verstehen, muss man die Verallgemeinerung überdenken. im

Um die Verallgemeinerung zu überdenken, müssen alte Ideen überarbeitet werden: statistische Mechanismen und komplexes Lernverhalten. Charles H. Martin und Michael W. Mahoney

Siehe: https://arxiv.org/pdf/1710.09553.pdf

Grundsätzlich argumentieren wir, dass die VC-Grenzen zu locker sind, weil der grundsätzliche Ansatz und die Art und Weise, wie das statistische Limit verwendet wird, unrealistisch sind.

Ein besserer Ansatz liegt in der statistischen Mechanik, die eine Klasse datenabhängiger Funktionen betrachtet und die thermodynamische Grenze verwendet (nicht nur die Grenze großer Zahlen).

Darüber hinaus weisen wir auch darauf hin, wie die natürlichen Diskontinuitäten in der Tiefe zu Phasenübergängen in der Lernkurve führen, die unserer Meinung nach in der Google-Veröffentlichung (oben) beobachtet werden.

Zu den Grenzwerten siehe Abschnitt 4.2 unseres Papiers

"Wenn wir die Stichprobengröße m festlegen und [die Größe der Funktionsklasse] N → ∞, [oder umgekehrt, N festlegen, m → ∞] lassen, sollten wir natürlich kein nicht triviales Ergebnis erwarten, da [ N] wird größer, aber die Stichprobengröße ist fest. Daher betrachtet man [in der statistischen Mechanik] typischerweise den Fall, dass m, N → ∞, so dass α = m / N eine feste Konstante ist.

Das heißt, sehr selten würden wir einem tiefen Netz einfach mehr Daten (m) hinzufügen. Wir vergrößern auch immer das Netz (N), weil wir wissen, dass wir detailliertere Merkmale / Informationen aus den Daten erfassen können. Stattdessen machen wir in der Praxis das, wofür wir in der Arbeit argumentieren - nehmen Sie die Grenze der großen Größe, wobei das Verhältnis m / N festgelegt ist (im Gegensatz dazu, wenn Sie m festlegen und N erhöhen lassen).

Diese Ergebnisse sind in der statistischen Lernmechanik bekannt. Die Analyse ist komplizierter, aber die Ergebnisse führen zu einer viel umfassenderen Struktur, die viele Phänomene des Tiefenlernens erklärt.

Es ist auch und insbesondere bekannt, dass viele Grenzen aus Statistiken entweder trivial werden oder nicht für nicht glatte Wahrscheinlichkeitsverteilungen gelten oder wenn die Variablen diskrete Werte annehmen. Bei neuronalen Netzen tritt nicht-triviales Verhalten aufgrund von Diskontinuitäten (in den Aktivierungsfunktionen) auf, was zu Phasenübergängen (die in der thermodynamischen Grenze auftreten) führt.

Der Artikel, den wir geschrieben haben, versucht, die herausragenden Ideen einem Informatikpublikum zu erklären.

Vapnik selbst erkannte, dass seine Theorie nicht wirklich auf neuronale Netze anwendbar war ... schon 1994

"Die Erweiterung [der VC-Dimension] auf mehrschichtige Netzwerke ist mit [vielen] Schwierigkeiten verbunden. Die vorhandenen Lernalgorithmen können nicht als Minimierung des empirischen Risikos über den gesamten Satz von Funktionen angesehen werden, die vom Netzwerk implementiert werden können ... [weil] dies der Fall ist wahrscheinlich ... wird die Suche auf eine Teilmenge dieser Funktionen beschränkt ... Die Kapazität dieses Satzes kann viel geringer sein als die Kapazität des gesamten Satzes ... [und] können sich mit der Anzahl der Beobachtungen ändern. Dies kann eine Theorie erfordern, die den Begriff einer nicht konstanten Kapazität mit einer "aktiven" Teilmenge von Funktionen "
Vapnik, Levin und LeCun 1994 berücksichtigt

http://yann.lecun.com/exdb/publis/pdf/vapnik-levin-lecun-94.pdf

Obwohl es mit der VC-Theorie nicht einfach zu behandeln ist, ist dies kein Problem für statistische Mechanismen. (welches das Thema eines zukünftigen Papiers sein wird)

Charles Martin
quelle
Das hört sich interessant an, aber ich bin mir nicht sicher, ob ich Ihrem Argument folge. Können Sie den ersten Satz näher erläutern, dh, wie unrealistisch der grundlegende Ansatz / die statistische Grenze ist, und zwar auf eigenständige Weise, ohne dass Sie die statistische Mechanik verstehen müssen? Welche Annahmen treffen VC-Grenzen und warum sind sie unrealistisch? Vielleicht können Sie Ihre Antwort so bearbeiten, dass sie diese Informationen enthält?
DW
Ich fügte einen Verweis auf die Originalarbeit von Vapnik und LeCun (1994) hinzu, in der das Thema erörtert wird.
Charles Martin
Und fügte eine Klarstellung hinzu.
Charles Martin
1

Niemand scheint in den obigen Antworten darauf hingewiesen zu haben, dass die angegebene VC-Dimensionsformel nur für ein neuronales Netzwerk mit einer Schicht gilt. Ich vermute, dass die VC-Dimension tatsächlich exponentiell wächst, wenn die Anzahl der Schichten L zunimmt. Meine Argumentation basiert auf der Betrachtung tiefer neuronaler Netze, bei denen die Aktivierungsfunktion durch polynomielle ersetzt wird. Dann wächst der Grad der zusammengesetzten Polynome exponentiell, wenn die Schichten zunehmen.

Yan König Yin
quelle