Was sind die Hauptsätze beim maschinellen (Tiefen-) Lernen?

Al Rahimi hat kürzlich in NIPS 2017 einen sehr provokanten Vortrag gehalten, in dem er das aktuelle maschinelle Lernen mit Alchemie vergleicht. Eine seiner Behauptungen ist, dass wir zu theoretischen Entwicklungen zurückkehren müssen, um einfache Theoreme zu haben, die grundlegende Ergebnisse beweisen.

Als er das sagte, fing ich an, nach den Hauptsätzen für ML zu suchen, konnte aber keine gute Referenz finden, die für die Hauptergebnisse Sinn macht. Hier ist meine Frage: Was sind die aktuellen mathematischen Hauptsätze (Theorie) in ML / DL und was beweisen sie? Ich würde vermuten, dass Vapniks Arbeit irgendwohin gehen würde. Was sind die wichtigsten offenen theoretischen Probleme?

Wie ich in den Kommentaren schrieb, erscheint mir diese Frage zu weit gefasst, aber ich werde versuchen, eine Antwort zu finden. Um einige Grenzen zu setzen, beginne ich mit einer kleinen Mathematik, die den meisten ML zugrunde liegt, und konzentriere mich dann auf die jüngsten Ergebnisse für DL.

---

Der Bias-Varianz-Kompromiss wird in unzähligen Büchern, Kursen, MOOCs, Blogs, Tweets usw. zu ML erwähnt, daher können wir nicht ohne Erwähnung beginnen:

$$\mathbb{E}[(Y-\hat{f}(X))^2|X=x_0]=\sigma_{\epsilon}^2+\left(\mathbb{E}\hat{f}(x_0)-f(x_0)\right)^2+\mathbb{E}\left[\left(\hat{f}(x_0)-\mathbb{E}\hat{f}(x_0)\right)^2\right]=\text{Irreducible error + Bias}^2 \text{ + Variance}$$

Beweis hier: https://web.stanford.edu/~hastie/ElemStatLearn/

---

Das Gauß-Markov-Theorem (ja, lineare Regression wird ein wichtiger Teil des maschinellen Lernens bleiben, egal was: damit umgehen) stellt klar, dass OLS das Minimum hat, wenn das lineare Modell wahr ist und einige Annahmen zum Fehlerterm gültig sind mittlerer quadratischer Fehler (der im obigen Ausdruck nur $\text{Bias}^2 \text{ + Variance}$ ) nur unter den unverzerrten linearen Schätzern des linearen Modells. Es könnte also durchaus lineare Schätzer mit Bias (oder nichtlineare Schätzer) geben, die einen besseren mittleren quadratischen Fehler und damit einen besser erwarteten Vorhersagefehler als OLS aufweisen. Und dies ebnet den Weg zu all dem Regularisierungs-Arsenal (Grat-Regression, LASSO, Gewichtsabnahme usw.), das ein Arbeitstier von ML ist. Ein Beweis wird hier (und in unzähligen anderen Büchern) gegeben: https://www.amazon.com/Linear-Statistical-Models-James-Stapleton/dp/0470231467

Wahrscheinlich relevanter für die Explosion von Regularisierungsansätzen, wie Carlos Cinelli in den Kommentaren feststellte, und definitiv unterhaltsamer, ist das James-Stein-Theorem . Betrachten Sie $n$ unabhängige, gleiche Varianz, aber nicht gleiche mittlere Gaußsche Zufallsvariablen:

$$X_i|\mu_i\sim \mathcal{N}(\theta_i,\sigma^2), \quad i=1,\dots,n$$

mit anderen Worten, wir haben einen $n-$ Komponenten Gaußschen Zufallsvektor . Wir haben eine Stichprobe aus und möchten schätzen . Der MLE- (und auch UMVUE-) Schätzer ist offensichtlich . Betrachten Sie den James-Stein-Schätzer$\mathbf{X}\sim \mathcal{N}(\boldsymbol{\theta},\sigma^2I)$$\mathbf{x}$$\mathbf{X}$$\boldsymbol{\theta}$& thgr; M L E = x$\hat{\boldsymbol{\theta}}_{MLE}=\mathbf{x}$

$$\hat{\boldsymbol{\theta}}_{JS}= \left(1-\frac{(n-2)\sigma^2}{||\mathbf{x}||^2}\right)\mathbf{x}$$

Wenn , schrumpft die MLE-Schätzung in Richtung Null. Der James-Stein - Theorem besagt , dass für , dominiert streng , dh es hat eine geringere MSE . Pheraps überraschend, auch wenn wir auf jede andere Konstante schrumpfen , noch dominiert . Seit dem$(n-2)\sigma^2\leq||\mathbf{x}||^2$θ J S n ≥ 4 θ J S$\hat{\boldsymbol{\theta}}_{JS}$ $n\geq4$$\hat{\boldsymbol{\theta}}_{JS}$ $\hat{\boldsymbol{\theta}}_{MLE}$$\forall \ \boldsymbol{\theta}$$\boldsymbol{c}\neq \mathbf{0}$ & theta; JS θ MLEXi$\hat{\boldsymbol{\theta}}_{JS}$$\hat{\boldsymbol{\theta}}_{MLE}$$X_i$Unabhängig sind, mag es seltsam erscheinen, dass der Versuch, die Größe von drei unabhängigen Personen zu schätzen, einschließlich einer Stichprobe aus der Anzahl der in Spanien erzeugten Äpfel, unsere Schätzung im Durchschnitt verbessern kann . Der entscheidende Punkt ist hier "im Durchschnitt": Der mittlere quadratische Fehler für die gleichzeitige Schätzung aller Komponenten des Parametervektors ist kleiner, der quadratische Fehler für eine oder mehrere Komponenten kann jedoch durchaus größer sein, und zwar häufig, wenn Sie haben "extreme" Beobachtungen.

Das Herausfinden, dass MLE, das in der Tat der "optimale" Schätzer für den Fall der univariaten Schätzung war, für die multivariate Schätzung entthront wurde, war zu dieser Zeit ein ziemlicher Schock und führte zu einem großen Interesse an Schrumpfung, besser bekannt als Regularisierung in der ML-Sprache. Man könnte einige Ähnlichkeiten mit gemischten Modellen und dem Konzept der "Ausleihstärke" feststellen: Es gibt tatsächlich einen Zusammenhang, wie hier diskutiert

Einheitliche Sicht auf die Schrumpfung: Welche Beziehung besteht (wenn überhaupt) zwischen Steins Paradoxon, Gratregression und zufälligen Effekten in gemischten Modellen?

Literaturhinweis: James, W., Stein, C., Schätzung mit quadratischem Verlust . Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Band 1: Beiträge zur Theorie der Statistik, 361-379, University of California Press, Berkeley, CA, 1961

---

Die Hauptkomponentenanalyse ist der Schlüssel zum wichtigen Thema der Dimensionsreduktion und basiert auf der Singularwertzerlegung : Für jede reelle Matrix (obwohl der Satz leicht auf komplexe Matrizen verallgemeinert werden kann) können wir schreiben$N\times p$$X$

$$X=UDV^T$$

wobei der Größe orthogonal ist, eine Diagonalmatrix mit nichtnegativen Diagonalelementen ist und der Größe wiederum orthogonal ist. Für Beweise und Algorithmen zur Berechnung siehe: Golub, G. und Van Loan, C. (1983), Matrix-Berechnungen , John Hopkins University Press, Baltimore.$U$$N \times p$$D$$p \times p$$U$$p \times p$

---

Der Satz von Mercer ist der Grundstein für viele verschiedene ML-Methoden: dünne Plattensplines, Support-Vektor-Maschinen, die Kriging-Schätzung eines Gaußschen Zufallsprozesses usw. Grundsätzlich ist er einer der beiden Sätze hinter dem sogenannten Kernel-Trick . Sei eine symmetrische stetige Funktion oder ein Kernel. wenn positiv semidefinit ist, lässt es eine orthornormale Basis von Eigenfunktionen zu, die nichtnegativen Eigenwerten entsprechen:$K(x,y):[a,b]\times[a,b]\to\mathbb{R}$$K$

$$K(x,y)=\sum_{i=1}^\infty\gamma_i \phi_i(x)\phi_i(y)$$

Die Bedeutung dieses Theorems für die ML-Theorie wird durch die Anzahl der Referenzen in berühmten Texten, wie zum Beispiel Rasmussen & Williams-Text zu Gaußschen Prozessen, bestätigt .

Literaturhinweis: J. Mercer, Funktionen vom positiven und negativen Typ und ihr Zusammenhang mit der Theorie der Integralgleichungen. Philosophische Transaktionen der Royal Society of London. Serie A, mit mathematischen oder physikalischen Aufsätzen, 209: 415-446, 1909

Es gibt auch eine einfachere Darstellung in Konrad Jörgens, Lineare Integraloperatoren , Pitman, Boston, 1982.

---

Der andere Satz, der zusammen mit dem Satz von Mercer die theoretische Grundlage des Kernel-Tricks bildet, ist der Repräsentantensatz . Angenommen, Sie haben einen Sample-Space und einen symmetrisch positiven semidefiniten Kernel . Es sei auch das mit assoziierte RKHS . Schließlich sei ein Übungsbeispiel. Der Satz besagt, dass unter allen Funktionen , die alle eine unendliche Repräsentation in Form von Eigenfunktionen von zulassen$\mathcal{X}$$K: \mathcal{X} \times \mathcal{X}\to \mathbb{R}$$\mathcal{H}_K$$K$$S=\{\mathbb{x}_i,y_i\}_{i=1}^n$$f\in \mathcal{H}_K$$K$Aufgrund des Mercer-Theorems hat derjenige, der das regulierte Risiko minimiert, immer eine endliche Repräsentation in der Basis, die durch den an den Trainingspunkten bewerteten Kern gebildet wird , d. h$n$

$$\min_{f \in \mathcal{H}_K} \sum_{i=1}^n L(y_i,f(x_i))+\lambda||f||^2_{\mathcal{H}_K}=\min_{\{c_j\}_1^\infty} \sum_{i=1}^n L(y_i,\sum_j^\infty c_j\phi_j(x_i))+\lambda\sum_j^\infty \frac{c_j^2}{\gamma_j}=\sum_{i=1}^n\alpha_i K(x,x_i)$$

(Der Satz ist die letzte Gleichheit). Literatur: Wahba, G. 1990, Spline Models for Observational Data , SIAM, Philadelphia.

---

Der universelle Näherungssatz wurde bereits von Benutzer Tobias Windisch zitiert und ist für das maschinelle Lernen viel weniger relevant als für die Funktionsanalyse, auch wenn dies auf den ersten Blick nicht so scheint. Das Problem ist, dass der Satz nur besagt, dass ein solches Netzwerk existiert, aber:

• es gibt keine Korrelation zwischen der Größe der verborgenen Schicht und einem Maß für die Komplexität der Zielfunktion , wie zum Beispiel Total Variation. Wenn und das für einen festen Fehler erforderliche exponentiell mit gewachsen ist , dann wächst eine einzelne verborgene Schicht neuronal Netzwerke wären nutzlos.$N$$f(x)$$f(x)=\sin(\omega x):[0,2\pi]\to[-1,1]$$N$$\epsilon$$\omega$
• es sagt nicht , wenn das Netzwerk ist erlernbar . Mit anderen Worten , wir gehen davon aus, dass wir bei gegebenem und wissen, dass sich eine Größe NN mit der erforderlichen Toleranz im Hyperkubus annähert. Haben wir dann durch die Verwendung von Trainingssätzen der Größe und eines Lernverfahrens wie zum Beispiel Back-Prop die Garantie, dass wir durch Erhöhen von wiederherstellen können ?$F(x)$$f$$\epsilon$$N$$f$$M$$M$$F$
• Schließlich, und schlimmer noch, sagt es nichts über den Vorhersagefehler neuronaler Netze aus. Was wir wirklich interessiert, ist eine Abschätzung des Vorhersagefehler, zumindest im Durchschnitt über alle Trainingssätze der Größe . Der Satz hilft in dieser Hinsicht nicht weiter.$M$

Ein kleinerer Nachteil bei der Hornik-Version dieses Theorems ist, dass es für ReLU-Aktivierungsfunktionen nicht gilt. Inzwischen hat Bartlett jedoch eine erweiterte Version bewiesen, die diese Lücke schließt.

---

Bis jetzt waren wohl alle Theoreme, die ich für gut hielt, jedem bekannt. Nun ist es Zeit für das lustige Zeug :-) Sehen wir uns ein paar Deep Learning- Sätze an:

Annahmen:

• Das tiefe neuronale Netzwerk (für festes ist die Funktion, die die Eingänge des neuronalen Netzwerks mit seinen Ausgängen verknüpft) und der Regularisierungsverlust sind beide Summen von positiv homogene Funktionen in gleichem Maße$\Phi(X,W)$$W$$\Phi_W(X)$$\Theta(W)$
• Die Verlustfunktion ist konvex und einmal in differenzierbar , in einer kompakten Menge$L(Y,\Phi(X,W)$$X$$S$

Dann:

• ein beliebiges lokales Minimum für so dass ein Subnetz von null Gewichte hat, ist ein globales Minimum ( Satz 1 )$L(Y,\Phi(X,W))+\lambda\Theta(W)$$\Phi(X,W)$
• oberhalb einer kritischen Netzwerkgröße konvergiert der lokale Abfall von jeder Initialisierung immer gegen ein globales Minimum ( Satz 2 ).

Dies ist sehr interessant: CNNs, die nur aus Faltungsschichten, ReLU, Max-Pooling, vollständig verbundenen ReLU und linearen Schichten bestehen, sind positiv homogene Funktionen, während dies nicht mehr zutrifft, wenn wir Sigmoid-Aktivierungsfunktionen einbeziehen , was den Vorgesetzten teilweise erklären könnte Leistung in einigen Anwendungen von ReLU + max-Pooling in Bezug auf Sigmoide. Darüber hinaus gelten die Sätze nur, wenn auch in im gleichen Maße wie positiv homogen ist . Nun ist die lustige Tatsache, dass oder Regularisierung, obwohl positiv homogen, nicht den gleichen Grad von (der Grad von$\Theta$$W$$\Phi$$l_1$$l_2$$\Phi$$\Phi$steigt im oben erwähnten einfachen CNN-Fall mit der Anzahl der Schichten an. Stattdessen entsprechen modernere Regularisierungsmethoden wie Batch-Normalisierung und Pfad-SGD einer positiv homogenen Regularisierungsfunktion in demselben Ausmaß wie , und Dropout ist zwar nicht genau diesem Framework angepasst, weist jedoch starke Ähnlichkeiten auf. Dies mag erklären, warum die Regularisierung von und nicht ausreicht, um eine hohe Genauigkeit bei CNNs zu , aber wir müssen alle möglichen teuflischen Tricks anwenden, wie zum Beispiel Dropout- und Batch-Normalisierung! Nach meinem besten Wissen ist dies die Erklärung der Wirksamkeit der Chargennormalisierung, die ansonsten sehr undurchsichtig ist, wie Al Rahimi in seinem Vortrag richtig feststellte.$\Phi$$l_1$$l_2$

Eine andere Beobachtung, die einige Leute auf der Grundlage von Satz 1 machen , ist, dass sie erklären könnte, warum ReLU auch mit dem Problem toter Neuronen gut funktioniert . Nach dieser Intuition ist die Tatsache, dass einige ReLU-Neuronen während des Trainings "sterben" (zur Aktivierung auf Null gehen und sich dann nie davon erholen, da für der Gradient von ReLU Null ist) "ein Merkmal, kein Fehler" ", denn wenn wir ein Minimum erreicht haben und ein vollständiges Teilnetzwerk gestorben ist, dann haben wir nachweislich ein globales Minimum erreicht (unter den Hypothesen von Satz 1)$x<0$). Ich kann etwas vermissen, aber ich denke, diese Interpretation ist weit hergeholt. Erstens können ReLUs während des Trainings "sterben", bevor wir ein lokales Minimum erreicht haben. Zweitens muss bewiesen werden, dass ReLU-Einheiten, wenn sie "sterben", dies immer über ein vollständiges Subnetz tun. Der einzige Fall, in dem dies trivial zutrifft, ist, dass Sie nur eine verborgene Schicht haben, in welchem ​​Fall natürlich jedes einzelne Neuron ist ein Subnetz. Aber im Allgemeinen würde ich "tote Neuronen" sehr vorsichtig als eine gute Sache ansehen.

Verweise:

B. Haeffele und R. Vidal, Globale Optimalität beim Training neuronaler Netze , In IEEE-Konferenz über Computer Vision und Mustererkennung, 2017.

B. Haeffele und R. Vidal. Globale Optimalität bei Tensorfaktorisierung, Deep Learning und darüber hinaus , arXiv, abs / 1506.07540, 2015.

---

Die Bildklassifizierung erfordert Lerndarstellungen, die gegenüber verschiedenen Transformationen wie Position, Pose, Blickwinkel, Beleuchtung, Ausdruck usw., die in natürlichen Bildern häufig vorhanden sind, jedoch keine Informationen enthalten, unveränderlich (oder zumindest robust, dh sehr schwach empfindlich) sind für die Klassifizierungsaufgabe. Dasselbe gilt für die Spracherkennung: Änderungen in Tonhöhe, Lautstärke, Tempo und Akzent. usw. sollte nicht zu einer Änderung der Klassifizierung des Wortes führen. Operationen wie Faltung, maximales Pooling, durchschnittliches Pooling usw., die in CNNs verwendet werden, verfolgen genau dieses Ziel. Wir gehen daher intuitiv davon aus, dass sie für diese Anwendungen funktionieren. Aber haben wir Theoreme, die diese Intuition stützen? Es gibt einen vertikalen TranslationsinvarianzsatzDies hat, ungeachtet des Namens, nichts mit der vertikalen Übersetzung zu tun, aber es ist im Grunde genommen ein Ergebnis, das besagt, dass die in den folgenden Ebenen erlernten Funktionen mit zunehmender Anzahl von Ebenen immer unveränderlicher werden. Dies steht im Gegensatz zu einem älteren Satz der horizontalen Translationsinvarianz, der jedoch für Streunetzwerke gilt, nicht jedoch für CNNs. Der Satz ist jedoch sehr technisch:

• Angenommen, (Ihr Eingabebild) ist quadratisch integrierbar$f$
• , Ihr Filter pendelt mit dem Übersetzungsoperator , der das Eingabebild auf eine übersetzte Kopie von sich selbst . Ein gelernter Faltungskern (Filter) erfüllt diese Hypothese.$T_t$$f$$T_t f$
• Angenommen, alle Filter, Nichtlinearitäten und Pools in Ihrem Netzwerk erfüllen eine so genannte schwache Zulässigkeitsbedingung , bei der es sich im Grunde um eine schwache Regelmäßigkeits- und Begrenzungsbedingung handelt. Diese Bedingungen werden durch erlernten Faltungskern (solange eine Normalisierungsoperation für jede Schicht durchgeführt wird), ReLU, Sigmoid, Tanh usw., Nichtlinearitäten und durch durchschnittliches Pooling, jedoch nicht durch maximales Pooling erfüllt. Es deckt also einige (nicht alle) reale CNN-Architekturen ab.
• Es sei schließlich angenommen, dass jede Schicht einen Pooling-Faktor , dh Pooling wird in jeder Schicht angewendet und verwirft effektiv Informationen. Die Bedingung würde auch für eine schwächere Version des Theorems ausreichen.$n$$S_n> 1$$S_n\geq 1$

Geben Sie mit die Ausgabe der Schicht des CNN an, wenn die Eingabe . Dann endlich:$\Phi^n(f)$$n$$f$

$$\lim_{n\to\infty}|||\Phi^n(T_f f)-\Phi^n(f)|||=0$$

(Die dreifachen Balken sind kein Fehler.) Dies bedeutet im Grunde, dass jede Schicht Merkmale lernt, die immer invarianter werden, und im Rahmen eines unendlich tiefen Netzwerks haben wir eine vollkommen invariante Architektur. Da CNNs eine begrenzte Anzahl von Schichten haben, sind sie nicht perfekt übersetzungsinvariant, was den Praktikern gut bekannt ist.

Referenz: T. Wiatowski und H. Bolcskei, Eine mathematische Theorie tiefer Faltungsneuralnetze zur Merkmalsextraktion , arXiv: 1512.06293v3 .

---

Zusammenfassend lässt sich sagen, dass zahlreiche Grenzen für den Verallgemeinerungsfehler eines Deep Neural Network aufgrund seiner Vapnik-Chervonkensis-Dimension oder der Rademacher-Komplexität mit der Anzahl der Parameter (einige sogar exponentiell) zunehmen, was bedeutet, dass sie nicht erklären können, warum DNNs so gut funktionieren in der Praxis auch dann, wenn die Anzahl der Parameter erheblich größer ist als die Anzahl der Trainingsmuster. Tatsächlich ist die VC-Theorie beim Deep Learning nicht sehr nützlich.

Umgekehrt haben einige Ergebnisse des letzten Jahres den Generalisierungsfehler eines DNN-Klassifikators an eine Größe gebunden, die von der Tiefe und Größe des neuronalen Netzes unabhängig ist, jedoch nur von der Struktur des Trainingssatzes und dem Eingaberaum abhängt. Unter einigen ziemlich technischen Annahmen zum Lernverfahren, zum Trainingssatz und zum Eingaberaum, aber mit sehr geringen Annahmen zum DNN (insbesondere, CNNs sind vollständig abgedeckt), haben wir dann mit einer Wahrscheinlichkeit von mindestens$1-\delta$

$$\text{GE} \leq \sqrt{2\log{2}N_y\frac{\mathcal{N_{\gamma}}}{m}}+\sqrt{\frac{2\log{(1/\delta)}}{m}}$$

wo:

• $\text{GE}$ ist der Generalisierungsfehler, definiert als die Differenz zwischen dem erwarteten Verlust (dem durchschnittlichen Verlust des erlernten Klassifikators bei allen möglichen Testpunkten) und dem empirischen Verlust (nur der gute alte Trainingssatzfehler).
• $N_y$ ist die Anzahl der Klassen
• $m$ ist die Größe des Trainingssatzes
• $\mathcal{N_{\gamma}}$ ist die Deckungszahl der Daten, eine Größe, die sich auf die Struktur des Eingaberaums und auf den minimalen Abstand zwischen Punkten verschiedener Klassen im Trainingssatz bezieht. Referenz:

J. Sokolic, R. Giryes, G. Sapiro und M. Rodrigues. Generalisierungsfehler von invarianten Klassifikatoren . In AISTATS, 2017

Ich denke, der folgende Satz, auf den Sie anspielen, wird als ziemlich grundlegend für das statistische Lernen angesehen.

Theorem (Vapnik und Chervonenkis, 1971) Sei eine hypothetische Klasse von Funktionen von einer Domäne bis und sei die Verlustfunktion der Verlust. Dann sind die folgenden äquivalent:X { 0 , 1 } 0 - $H$$X$$\{0, 1\}$$0 − 1$

1. $H$ hat die einheitliche Konvergenzeigenschaft.
2. $H$ ist PAC lernbar.
3. $H$ hat eine endliche VC-Dimension.

Bewiesen in einer quantitativen Version hier:

VN Vapnik und AY Chervonenkis: Zur einheitlichen Konvergenz der relativen Häufigkeiten von Ereignissen mit ihren Wahrscheinlichkeiten. Wahrscheinlichkeitstheorie und ihre Anwendungen, 16 (2): 264–280, 1971.

Die oben formulierte Version sowie eine schöne Darstellung weiterer Ergebnisse der Lerntheorie finden Sie hier :

Shalev-Shwartz, Shai und Shai Ben-David. Maschinelles Lernen verstehen: Von der Theorie zum Algorithmus. Cambridge University Press, 2014.

Der Kernel-Trick ist eine allgemeine Idee, die an vielen Orten verwendet wird und aus einer Menge abstrakter Mathematik über Hilbert-Räume stammt. Es ist viel zu viel Theorie, als dass ich sie hier in eine Antwort eintippen (kopieren ...) könnte, aber wenn Sie dies durchgehen, können Sie sich einen guten Überblick über die strengen Grundlagen verschaffen:

http://www.stats.ox.ac.uk/~sejdinov/teaching/atml14/Theory_2014.pdf

Mein Favorit ist die Kraft-Ungleichung.

Satz: Für jede Beschreibungsmethode für endliches Alphabet müssen die Codewortlängen die Ungleichung erfüllen .A = { 1 , ... , m } L C ( 1 ) , ... , L C ( 2 ) Σ x ∈ A 2 - L C ( x ) ≤ $C$$A = \{1,\dots, m\}$$L_C(1), \dots, L_C(2)$$\sum_{x \in A} 2 ^{-L_C(x)} \leq 1$

Diese Ungleichung bezieht sich auf die Komprimierung mit der Wahrscheinlichkeitsdichte : Bei einem Code ist die Länge eines durch diesen Code dargestellten Ergebnisses die negative logarithmische Wahrscheinlichkeit eines durch den Code identifizierten Modells.

Darüber hinaus ist das No-Free-Lunch-Theorem für maschinelles Lernen weniger bekannt als das No-Hyper-Compression-Theorem, das besagt, dass nicht alle Sequenzen komprimiert werden können.

Ich würde es nicht als Hauptsatz bezeichnen, aber ich denke, dass der folgende Satz (der manchmal als universeller Näherungssatz bezeichnet wird) einen interessanten (und zumindest für mich überraschenden) Satz darstellt, da er die approximative Kraft von vorwärtsgerichteten neuronalen Netzen angibt.

Theorem: Sei eine nicht konstante und monotinisch zunehmende stetige Funktion. Für jede kontinuierliche Funktion und jedes gibt es eine ganze Zahl und ein mehrschichtiges Perzeptron mit einer verborgenen Schicht mit Neuronen, die als Aktivierung haben funktionieren damit$\sigma$$f:[0,1]^m\to\mathbb{R}$$\epsilon>0$$N$$F$$N$$\sigma$

x ∈ [ 0 , 1 ]

$$|F(x)-f(x)|\le\epsilon$$ für alle .$x\in[0,1]^m$

Da dies eine Aussage über die Existenz ist , ist ihre Auswirkung auf die Praktiker natürlich vernachlässigbar.

Ein Beweis findet sich in Hornik, Approximation Capabilities of Muitilayer Feedforward Networks, Neuronale Netze 4 (2), 1991,

Ein netter Beitrag, der sich mit dieser Frage befasst (insbesondere Deep Learning statt allgemeiner maschineller Lernsätze), ist hier:

https://medium.com/mlreview/modern-theory-of-deep-learning-why-does-it-works-so-well-9ee1f7fb2808

Es gibt eine leicht zugängliche Zusammenfassung der wichtigsten neu aufkommenden Theoreme für die Fähigkeit tiefer neuronaler Netze, so gut zu verallgemeinern.