Maschinelles Lernen und neuronale Netze - Seite 27

Neuer Kommentar
 

Vorlesung 16. Ableitungen von Invers- und Singulärwerten


16. Ableitungen von inversen und singulären Werten

Dieses Video behandelt eine Vielzahl von Themen, darunter die Ableitung der inversen und singulären Werte einer Matrix, Interlacing und die Nuklearnorm einer Matrix. Der Referent stellt eine Formel für die Ableitung von Singulärwerten unter Verwendung der SVD vor, um zu verstehen, wie sich eine Matrix im Laufe der Zeit ändert, und legt gleichzeitig Grenzen für Änderungen der Eigenwerte in symmetrischen Matrizen fest. Die Ungleichung von Vial wird eingeführt, um die Lambda-Werte einer Matrix zu schätzen, und die Basisverfolgung wird bei Matrixvervollständigungsproblemen verwendet. Der Referent diskutiert auch die Idee, dass die nukleare Norm einer Matrix aus einer Norm stammt, die nicht ganz eine Norm ist, und führt das Konzept von Lasso und komprimierter Wahrnehmung ein, das in der nächsten Vorlesung diskutiert wird.

  • 00:00:00 In diesem Abschnitt erörtert der Kursleiter verschiedene Themen, darunter das Ermitteln der Ableitung der Inversen einer Matrix, der Ableitung eines Eigenwerts und der Ableitung des Singulärwerts. Der Dozent teilt eine Formel für die Ableitung des Singularwerts mit, die er kürzlich entdeckt hat, und erwähnt, dass die Formel für die Ableitung der Inversen nicht einfach die Ableitung der ursprünglichen Matrix ist. Er spricht auch über Laborhausaufgaben, bittet um Rat zu einem Projekt und erwähnt die bevorstehende Vorlesung von Professor Townsend über Angewandte Lineare Algebra. Der Kursleiter erklärt weiter, wie man systematisch die Ableitung einer quadratischen Matrix findet und warum die allgemein angenommene Formel falsch ist.

  • 00:05:00 In diesem Abschnitt geht der Referent auf die Ableitung von Singulärwerten ein, die der Ableitung von Eigenwerten ähnlich ist. Die Formel für die Ableitung singulärer Werte ergibt sich aus der Transponierten von da/dt mal dem singulären Vektor von a. Diese Formel stützt sich auf die SVD, die besagt, dass a mal V gleich Sigma U ist. Durch die Verwendung dieser Fakten und die Manipulation der Gleichung ist es möglich, die Formel für die Ableitung von singulären Werten abzuleiten. Diese Formel ist nützlich, um zu verstehen, wie sich eine Matrix im Laufe der Zeit verändert, und kann in verschiedenen Bereichen wie Physik und Ingenieurwesen angewendet werden.

  • 00:10:00 In diesem Abschnitt behandelt der Referent die Ableitungen von inversen und singulären Werten. Sie erklären zunächst die Formel für die singulären Werte anhand der SVD einer Matrix und nehmen dann die Ableitung der Gleichung. Der Sprecher verwendet die Produktregel und vereinfacht die resultierende Gleichung, um den Term zu finden, der ihm die gesuchte Antwort liefert. Sie zeigen dann, dass die anderen beiden Terme Null sind, was beweist, dass ihr gewählter Term der richtige ist. Schließlich verwenden sie Punktprodukte und eine Zahl, um zu zeigen, dass die Ableitung von U mit U-Transponierung gleich Null ist.

  • 00:15:00 In diesem Abschnitt behandelt der Referent Ableitungen von Singulärwerten und Eigenwerten einer symmetrischen Matrix. Während eine genaue Formel für die Änderung von Singulär- oder Eigenwerten nicht berechnet werden kann, können Grenzen festgelegt werden, indem man erkennt, dass positive Änderungen der Eigenwerte nicht dazu führen, dass sie abnehmen. Die Verschachtelung der alten und neuen Werte wird durch die Tatsache veranschaulicht, dass der zweite Eigenwert den ersten alten Eigenwert nicht überschreitet und der erste neue Eigenwert nicht kleiner als der erste alte Eigenwert ist, was diese Konzepte für das Verständnis der SVD nützlich macht.

  • 00:20:00 In diesem Abschnitt des Videos stellt der Sprecher eine Rätselfrage bezüglich des Effekts, den das Hochziehen des zweiten Eigenvektors auf die Eigenwerte einer Matrix hat. Er weist darauf hin, dass, wenn der zweite Eigenwert um einen bestimmten Betrag, der als Theta bezeichnet wird, erhöht wird, er schließlich den ersten Eigenwert übertreffen kann, was ein potenzielles Problem darstellt. Dann erklärt er jedoch seinen Denkprozess und zeigt, dass dies eigentlich kein Problem ist, da der erste Eigenwert unverändert bleibt, während der zweite Eigenwert nach oben verschoben wird, aber schließlich gegen die Summe von Lambda 1 und Theta konvergiert.

  • 00:25:00 In diesem Abschnitt geht der Sprecher auf Interlacing und Vials Ungleichheit ein. Die Ungleichung von Vial ist eine Möglichkeit, die Lambda-Werte einer Matrix zu schätzen, bei denen es sich um die Eigenwerte handelt, die vom größten zum kleinsten geordnet sind. Die Ungleichung gilt für jede symmetrische Matrix und besagt, dass der größte Eigenwert der Summe zweier symmetrischer Matrizen kleiner oder gleich der Summe der größten Eigenwerte jeder Matrix einzeln ist. Diese Verschachtelungseigenschaft gilt nicht nur für Störungen des ersten Ranges, sondern auch für Störungen anderer Ränge. Der Sprecher verwendet das Beispiel des Hinzufügens einer positiven Matrix T zu S und erklärt, wie dies mit der Ungleichung von Vial zusammenhängt.

  • 00:30:00 In diesem Abschnitt erörtert der Sprecher die Ungleichheit von Vile und ihre Beziehung zum Interlacing. Die Ungleichung von Vile gibt eine Grenze dafür vor, wie stark ein Eigenwert ansteigen kann, und diese Tatsache ist entscheidend für das Verständnis des Interlacing-Phänomens. Der Redner erwähnt, dass es zwei Möglichkeiten gibt, Interlacing zu beweisen, einschließlich der Ungleichung von Vile und einer anderen Methode, die einen Graphen beinhaltet. Der Abschnitt führt auch in die komprimierte Erkennung ein, die im nächsten Teil des Videos besprochen wird.

  • 00:35:00 In diesem Abschnitt wird das Konzept der Kernnorm einer Matrix eingeführt, die die Summe der Einzelwerte der Matrix ist. Dies kann als die L1-Norm für einen Vektor angesehen werden. Es hat eine spezielle Eigenschaft, ähnlich der L1-Norm, bei der das Minimieren der Kernnorm mit einer Einschränkung zu einer dünnbesetzten Lösung führt. Diese Eigenschaft ist bei Matrixvervollständigungsproblemen nützlich, bei denen fehlende Daten in einer Matrix ausgefüllt werden müssen. Die Zahlen, die die Kernnorm minimieren, sind eine gute Wahl, um die fehlenden Daten zu ergänzen. Die Nullnorm eines Vektors, der die Anzahl der Nicht-Nullen darstellt, ist keine Norm, aber sie kann zur nächsten Norm, der L1-Norm, verschoben werden. Diese Norm ist die Summe der Absolutwerte der Komponenten des Vektors. Die Minimierung dieser Norm unter bestimmten Bedingungen wird als Basisverfolgung bezeichnet und bei Matrixvervollständigungsproblemen verwendet.

  • 00:40:00 In diesem Abschnitt diskutiert der Sprecher die Idee, dass die nukleare Norm einer Matrix aus einer Norm stammt, die keine Norm ist. Er erklärt, dass der Rang der Matrix dieser Norm entspricht, aber keine Norm ist, weil er nicht skalierbar ist, wenn die Größe der Matrix verdoppelt wird. Der Referent beschreibt weiter die Vermutung, dass der Deep-Learning-Algorithmus des Gradientenabstiegs die Lösung für das Minimalproblem in der Nuklearnorm findet, und führt das Konzept von Lasso und komprimiertem Sensing ein, das im nächsten Vortrag weiter diskutiert wird.
 

Vorlesung 17: Schnell abnehmende Singulärwerte



Vorlesung 17: Schnell abnehmende Singulärwerte

Die Vorlesung konzentriert sich auf Matrizen und ihre Ränge und wie schnell abnehmende Singularwerte in der Computermathematik vorherrschen. Der Dozent untersucht Matrizen mit niedrigem Rang und demonstriert, dass sie viele Nullen in ihrer Folge von Einzelwerten haben, wodurch es effizienter ist, die Matrix in Form mit niedrigem Rang an einen Freund zu senden als in Form mit vollem Rang. Sie führen auch den numerischen Rang einer Matrix ein, der definiert wird, indem ein gewisser Spielraum gelassen wird, um die Toleranz einzelner Werte einer Matrix zu definieren. Durch das Abtasten glatter Funktionen, die durch Polynome gut approximiert werden können, kann der numerische Rang niedrig sein, was zu einer niedrigrangigen Approximation der Matrix X führt. Die Vorlesung enthält auch Beispiele für Gaußsche und Vandermonde-Matrizen, um zu erklären, wie sie führen können Matrizen von niedrigem Rang und diskutiert die Nützlichkeit von Zolotarev-Zahlen beim Begrenzen von singulären Werten.

  • 00:00:00 In diesem Abschnitt erklärt ein Professor, warum Matrizen mit niedrigem Rang in der Welt der Computermathematik so weit verbreitet sind. Er diskutiert die Bedeutung von singulären Werten, die uns etwas über den Rang einer Matrix sagen und wie gut er durch eine Matrix mit niedrigem Rang angenähert werden kann. Er erklärt weiter, dass eine Matrix X in eine Summe von K Rang-Eins-Matrizen zerlegt werden kann, wenn sie K Singularwerte ungleich Null hat. Darüber hinaus haben sowohl der Spaltenraum als auch der Zeilenraum von X die Dimension K. Die Singularwertsequenz ist für eine Matrix einzigartig, und der Schwerpunkt liegt auf der Identifizierung der Eigenschaften von X, die Matrizen mit niedrigem Rang in verschiedenen mathematischen Problemen erscheinen lassen.

  • 00:05:00 In diesem Abschnitt bespricht der Dozent Matrizen mit niedrigem Rang und warum sie viele Nullen in ihrer Folge von singulären Werten haben. Bei einer Matrix mit niedrigem Rang ist es effizienter, die Matrix in Form mit niedrigem Rang an einen Freund zu senden als in Form mit vollem Rang. Die Vorlesung verwendet verschiedene Flags, um das Konzept der Matrizen mit niedrigem Rang zu demonstrieren, wobei extrem niedrige Ränge stark an den Koordinaten der Zeilen und Spalten ausgerichtet sind. Mit zunehmendem Rang wird die Ausrichtung verschwommen und es wird schwieriger zu erkennen, ob die Matrix einen niedrigen Rang hat. Matrizen mit hohem Rang sind ineffizient, wenn sie in Form mit niedrigem Rang gesendet werden.

  • 00:10:00 In diesem Abschnitt untersucht der Dozent die dreieckige Flag-Matrix, um zu verstehen, warum diagonale Muster nicht gut für die Low-Rank-Komprimierung sind. Die Matrix aller Einsen hat eine Eigenschaft, die Gils Lieblingsmatrix ähnelt, wenn man ihre Umkehrung nimmt. Durch die Untersuchung der Singulärwerte dieser Matrix zeigt der Dozent, dass Dreiecksmuster einer Low-Rank-Komprimierung nicht zugänglich sind. Der Kreisfall und das japanische Flaggenmuster sind jedoch für eine Komprimierung mit niedrigem Rang geeignet.

  • 00:15:00 In diesem Abschnitt geht der Dozent auf den Rang eines Kreises ein, insbesondere auf die japanische Flagge. Indem die Flagge in einen Kreis, ein Stück mit Rang eins in der Mitte und ein Quadrat zerlegt wird, kann der Rang bestimmt werden, indem die Ränge jedes Stücks addiert werden. Der Dozent zeigt, dass das Stück mit dem Rang eins durch eins begrenzt ist, und verwendet dann die Symmetrie, um den Rang des quadratischen Stücks zu bestimmen, der vom Radius des Kreises abhängt. Durch einige Berechnungen mit Trigonometrie kommt der Dozent zu dem Schluss, dass der Rang ungefähr 1/2 beträgt, was es effizient macht, die japanische Flagge in niedriger Rangform darzustellen. Die meisten Matrizen in der Computermathematik haben jedoch keinen endlichen Rang, sondern einen numerischen Rang, der dem Rang ähnlich ist, aber eine gewisse Annäherung ermöglicht.

  • 00:20:00 In diesem Abschnitt lernen wir den numerischen Rang einer Matrix kennen, der definiert wird, indem man etwas Spielraum lässt, um die Toleranz einzelner Werte einer Matrix zu definieren. Der numerische Rang ist K, wenn K der erste Singularwert über Epsilon ist, was die Toleranz bezeichnet, und der Rang derselbe ist wie der letzte Singularwert über Epsilon und der erste Singularwert unter Epsilon ist. Numerisch niederrangige Matrizen sind nicht nur niederrangige Matrizen, sondern auch Vollrangmatrizen mit schnell abnehmenden singulären Werten. Dies ermöglicht es uns, Matrizen unter Verwendung einer Annäherung mit niedrigem Rang zu komprimieren, während in der Praxis ein vernünftiges Toleranzniveau zugelassen wird. Die Hilbert-Matrix ist ein Beispiel für eine Vollrangmatrix mit niedrigem numerischen Rang.

  • 00:25:00 In diesem Abschnitt erörtert der Dozent, wie Matrizen einen niedrigen numerischen Rang haben können, aber nicht unbedingt einen niedrigen Rang im Allgemeinen. Als klassisches Beispiel hierfür wird die Vandermonde-Matrix verwendet. Diese Matrix entsteht bei der Polynominterpolation an realen Punkten und hat oft einen numerisch niedrigen Rang, was es schwierig macht, sie zu invertieren. Ein numerischer niedriger Rang ist jedoch nicht immer wünschenswert, insbesondere wenn versucht wird, das Inverse zu finden. Der Dozent erklärt, dass der Grund, warum es so viele niederrangige Matrizen gibt, darin besteht, dass die Welt glatt ist, was bedeutet, dass Matrizen numerisch niederrangig sind. Es wird ein Beispiel angegeben, bei dem ein Polynom in zwei Variablen abgetastet wird, und es wird gezeigt, dass die resultierende Matrix mathematisch einen niedrigen Rang hat, wobei Epsilon gleich Null ist.

  • 00:30:00 In diesem Abschnitt erläutert der Referent, wie man eine niederrangige Approximation für eine Matrix X erhält, indem man eine Funktion abtastet und diese Funktion durch ein Polynom approximiert. Wenn ein Polynom von zwei Variablen mit dem Grad M in x und y niedergeschrieben und dann abgetastet werden kann, hat das resultierende x einen niedrigen Rang, wobei Epsilon gleich Null ist und höchstens M zum Quadrat hat. Durch das Abtasten glatter Funktionen, die durch Polynome gut approximiert werden können, kann der numerische Rang niedrig sein, was zu einer niedrigrangigen Approximation der Matrix X führt. Die Argumentation hinter dieser Methode funktioniert jedoch nicht gut für die Hilbert-Matrix, die ist voller Rang.

  • 00:35:00 In diesem Abschnitt erörtert der Dozent, wie man einen angemessenen Grund für die Begrenzung des Rangs einer Matrix findet. Viele Leute haben versucht, ein Polynom zu entwickeln, das den Rang einer Matrix genau vorhersagen kann, aber die Methoden waren unbefriedigend. Der Dozent führt in die Idee der Sylvester-Matrizen ein, bei denen es sich um Matrizen handelt, die eine bestimmte Gleichung erfüllen, die als Sylvester-Gleichung bezeichnet wird. Indem ein A, B und C gefunden wird, die die Gleichung erfüllen, kann gezeigt werden, dass eine Matrix einen numerischen niedrigen Rang hat. Der Dozent gibt ein Beispiel mit der Hilbert-Matrix und einer speziellen Methode, links und rechts mit der Hälfte zu multiplizieren, um die Sylvester-Gleichung zu erfüllen.

  • 00:40:00 In diesem Abschnitt lieferte die Vorlesung Beispiele für Gaußsche und Vandermonde-Matrizen, um zu erklären, wie Permutationen und Multiplikationen zu Matrizen mit niedrigem Rang führen können. Die Vorlesung erklärt, dass, wenn X eine Semestergleichung erfüllt, eine Schranke auf den singulären Werten jeder Matrix gefunden werden kann, die einen ähnlichen Ausdruck wie die Gaußschen und Vandermonde-Matrizen erfüllt, die sogenannte Frobenius-Norm. Der Fuller and Bound wird verwendet, um diesen numerischen niedrigen Rang in Matrizen zu demonstrieren, wobei Beispiele gegeben werden, um eine Verbindung zwischen der Erfüllung bestimmter Gleichungen und dem Auftreten dieser Matrizen mit niedrigem Rang in der Praxis zu demonstrieren.

  • 00:45:00 In diesem Abschnitt erörtert der Dozent, wie nützlich das abstrakte Problem der Singularwerte ist, die durch Zolotarev-Zahlen begrenzt sind, da viele Menschen diese Zahlen bereits studiert haben. Der Hauptgrund, warum dies nützlich ist, ist, dass die Mengen E und F getrennt sind, und das ist es, was die Zolotarev-Zahl mit k extrem schnell klein werden lässt. Der Dozent verwendet die Hilbert-Matrix als Beispiel, um zu zeigen, wie die Zolotarev-Zahl eine Grenze für den numerischen Rang angeben kann, was darauf hinweist, warum es in der Computermathematik so viele Matrizen mit niedrigem Rang gibt. Der Dozent erwähnt auch den inoffiziellen Fluch, der die beiden Schlüsselpersonen umgibt, die an dem Problem Zolotarev gearbeitet haben; beide starben im Alter von 31 Jahren, weshalb neben Pencils Namen ein Fragezeichen steht.
 

Vorlesung 18: Zählparameter in SVD, LU, QR, Sattelpunkte



Vorlesung 18: Zählparameter in SVD, LU, QR, Sattelpunkte

In diesem Vortrag geht der Referent auf verschiedene Matrixfaktorisierungen wie L&U-, Q&R- und Eigenvektormatrizen ein und zählt die Anzahl der freien Parameter in jeder dieser Matrizen. Sie diskutieren auch die Berechnung von Qs versus SVD und zählen die Anzahl der Parameter in der SVD für eine Rang-R-Matrix. Der Dozent erklärt auch das Konzept von Sattelpunkten in Matrizen und wie man sie mit Hilfe von Optimierungstechniken und Lagrange-Multiplikatoren findet. Schließlich diskutiert der Dozent das Vorzeichen der Eigenwerte einer symmetrischen Matrix und wie der Rayleigh-Quotient helfen kann, den Maximalwert und den entsprechenden Eigenvektor der Matrix zu bestimmen.

  • 00:00:00 In diesem Abschnitt überprüft der Sprecher die großen Faktorisierungen einer Matrix, wie L&U-, Q&R- und Eigenvektormatrizen, und zählt die Anzahl der freien Parameter in jeder dieser Matrizen. Der Sprecher weist darauf hin, dass die Anzahl der freien Parameter in L&U oder Q&R mit der Anzahl der Parameter in der ursprünglichen Matrix übereinstimmen sollte und dass sich die freien Parameter der Eigenwert- und Eigenvektormatrizen zu N Quadrat aufaddieren. Der Referent merkt an, dass diese Übung nicht oft in Lehrbüchern zu finden ist, aber eine wichtige Wiederholung für das Verständnis der linearen Algebra darstellt.

  • 00:05:00 In diesem Abschnitt erörtert der Referent die Anzahl freier Parameter in verschiedenen Matrixfaktorisierungen, einschließlich SVD, LU, QR und polarer Zerlegung. Der Sprecher merkt an, dass die Anzahl der freien Parameter in einer orthogonalen N-mal-n-Matrix Q N-1 für die erste Spalte und N-2 für nachfolgende Spalten aufgrund von Normalisierungs- und Orthogonalitätsbedingungen ist. Sie diskutieren auch die Anzahl der freien Parameter in einer symmetrischen Matrix S, die 1/2 N mal N minus 1 plus die Anzahl der diagonalen Elemente ist. Anschließend zeigen sie, wie sich diese Zählungen für verschiedene Faktorisierungen addieren, einschließlich L mal U, Q mal R und Q mal S. Schließlich erwähnen sie die polare Zerlegung als eine weitere Faktorisierung, die zu einer orthogonalen mal einer symmetrischen Matrix führt.

  • 00:10:00 In diesem Abschnitt diskutiert der Dozent die Berechnung von Qs im Vergleich zur SVD und zählt dann die Parameter in der SVD. Der größte Rang, den die rechteckige Matrix haben kann, ist M, was zu einer M-mal-N-Matrix für die SVD führt. Der Dozent erwartet, dass es sich zur Summe der ursprünglichen Matrix aufaddiert, die MN-Parameter hat. Der Zählwert für S ist gleich M und der Zählwert für V ist gleich N. Der Zählwert für U ist gleich 1/2 (M^2 + M), wenn es sich um eine orthogonale M-mal-M-Matrix handelt.

  • 00:15:00 In diesem Abschnitt erläutert der Referent, wie die wichtigen Parameter in der Singulärwertzerlegung (SVD) einer Matrix für eine Rang-R-Matrix gezählt werden. Die M Spalten von V, die Singularwerten ungleich Null entsprechen, sind die einzigen wichtigen Teile der Matrix. Um die Anzahl der Parameter zu zählen, verwendet der Sprecher eine Formel, die die unterschiedliche Anzahl notwendiger Parameter in jeder orthogonalen Spalte von V bis zur M-ten Spalte berücksichtigt. Die Formel beinhaltet das Addieren von 1 zu NM für jede Spalte und das Subtrahieren dieser Zahl von der Hälfte von M zum Quadrat plus M plus 1. Das Ergebnis der Formel ist die endgültige Anzahl für die Parameter in der SVD einer Rang-R-Matrix.

  • 00:20:00 In diesem Abschnitt diskutiert der Sprecher Matrizen des Ranges R und die Anzahl ihrer Parameter. Matrizen des Rangs R sind kein Unterraum, da verschiedene Matrizen denselben Rang haben können, was sie eher wie eine Oberfläche mit unterschiedlichen Teilen macht. Der Sprecher glaubt, dass eine Matrix vom Rang R R-Parameter hat. Anschließend ermitteln sie die Anzahl der Parameter in einer Rang-R-Matrix. Die Anzahl der Parameter ist R für Sigma, (R + 1) / 2 für V und (M - 1) + (M - 2) + ... + (M - R) für U.

  • 00:25:00 In diesem Abschnitt der Vorlesung diskutiert der Dozent das Konzept der Sattelpunkte in Matrizen, die sich von Maxima und Minima unterscheiden. Sattelpunkte entstehen bei der Optimierung einer quadratischen Kostenfunktion, die linearen Beschränkungen unterliegt, unter Verwendung von Lagrange-Multiplikatoren. Der Lehrer führt Lambda ein und zeigt, wie es im Lagrange verwendet wird, um eine Funktion zu bilden, die sowohl von X als auch von Lambda abhängt. Diese Funktion kann dann optimiert werden, um eventuell auftretende Sattelpunkte zu finden. Der Ausbilder erwähnt auch eine andere Quelle für Sattelpunkte, die in Matrizen auftreten, die nicht positiv definit oder negativ definit sind.

  • 00:30:00 In diesem Abschnitt erörtert der Referent, wie man Sattelpunkte einer Funktion findet, und zeigt, wie sie in einer wichtigen Klasse von Problemen entstehen, die durch eine Blockmatrix dargestellt werden. Die Funktion hat Sattelpunkte, kein Maximum. Lagrons Beitrag zu diesem Problem besteht darin, die Ableitungen in Bezug auf X und Lambda zu nehmen, wodurch n- bzw. m-Gleichungen erzeugt werden. Letztendlich zeigt die durch die Blockmatrix dargestellte Matrix an, dass sie nicht positiv definit ist, und diese Information kann verwendet werden, um Sattelpunkte zu bestimmen.

  • 00:35:00 In diesem Abschnitt erörtert der Dozent, wie die Determinante einer Matrix helfen kann, die Vorzeichen ihrer Eigenwerte zu bestimmen. An einem einfachen Beispiel zeigt er, dass es bei negativer Determinante Eigenwerte beider Vorzeichen geben muss. Er bezieht dies dann auf die bei der Optimierung verwendeten KKT-Matrizen und argumentiert, dass sie im Allgemeinen unbestimmt sind, aber ihnen ein positiver bestimmter Block zugeordnet ist. Er demonstriert, dass bei Anwendung der Blockeliminierung auf diesen positiv definiten Block alle n Pivots positiv sind, was zu dem Schluss führt, dass die KKT-Matrizen sowohl positive als auch negative Eigenwerte haben.

  • 00:40:00 In diesem Abschnitt erörtert der Dozent Sattelpunkte und ihre Beziehung zu Einschränkungen. Er erklärt, wie man das Vorzeichen der Eigenwerte einer symmetrischen Matrix anhand der Vorzeichen ihrer Drehpunkte bestimmt. Der Dozent definiert auch den Rayleigh-Quotienten und bespricht, wie er uns helfen kann, den Maximalwert und den entsprechenden Eigenvektor einer symmetrischen Matrix zu bestimmen. Die Vorlesung endet mit einer Erklärung, wie jeder Wert, den wir in den Rayleigh-Quotienten einsetzen, kleiner als der Maximalwert sein wird.

  • 00:45:00 In diesem Abschnitt erörtert der Sprecher das Konzept der Sattelpunkte im Rayleigh-Quotienten. Es gibt schwierig zu handhabende Zwischenlambdas zwischen dem Minimum und dem Maximum. Beim Maximum und Minimum sind die Quotientenwerte jedoch leicht zu messen. Wenn irgendein Vektor in irgendwelchen Dimensionen ausgewählt wird, können wir R von X berechnen, das zwischen dem Maximum und dem Minimum liegt. Der Referent sagt, dass das Sprechen über die Details der Sattelpunkte für die nächste Vorlesung aufgehoben wird, aber vorher wird das dritte Labor gegeben, das über Overfitting, Deep Learning lehrt und nach der Pause fällig ist.
 

Vorlesung 19. Fortsetzung Sattelpunkte, Maximin-Prinzip



19. Sattelpunkte Fortsetzung, Maximin-Prinzip

In diesem Video diskutiert der Sprecher weiterhin Sattelpunkte und wie man mithilfe des Rayleigh-Quotienten im zweidimensionalen Raum Minimal- und Maximalwerte findet. Das Interlacing-Theorem wird erklärt, bei dem Sattelpunkte als Maximum eines Minimums geschrieben werden, um Maxima und Minima schnell zu finden. Der Referent warnt auch vor Überanpassung beim Anpassen von Daten mit einem hochgradigen Polynom und diskutiert zwei Open-End-Labs für die Klasse, die Sattelpunkte und ein einfaches neuronales Netzwerk beinhalten. Die Konzepte von Mittelwert und Varianz in Statistiken und Stichprobenvarianz und -kovarianz werden erläutert, wobei der Sprecher anmerkt, dass die Kovarianzmatrix für vollständig abhängige Ergebnisse nicht umkehrbar wäre und für Umfrageszenarien mit mehreren Personen, die in einem Haus leben, eine gewisse Kovarianz erwartet wird nicht ganz unabhängig.

  • 00:00:00 In diesem Abschnitt erörtert der Referent die Bedeutung des Verständnisses von Sattelpunkten in Bezug auf das Finden des Minimums der Kostengesamtfunktion beim Deep Learning. Sie liefern ein Beispiel für einen Rayleigh-Quotienten und eine einfache Matrix S, um die Hauptfakten von Sattelpunkten, die maximalen und minimalen Werte der Funktion und das Vorhandensein eines Sattelpunkts zu veranschaulichen. Der Redner erwähnt auch ihre Pläne, Labor drei, Projekte und grundlegende Statistiken, insbesondere die Kovarianzmatrix, zu diskutieren.

  • 00:05:00 In diesem Abschnitt erörtert der Sprecher Sattelpunkte und wie man die Minimal- und Maximalwerte findet, indem man alles auf eine Variable lädt und die Ableitungen berechnet, um herauszufinden, wo sie gleich Null sind. Sie demonstrieren, wie man den Minimalwert findet, und zeigen, dass die Eigenvektoren und Eigenwerte der Matrix dabei helfen, die Position und den Wert des Sattelpunkts zu finden. Der Referent spricht auch darüber, wie man die zweiten Ableitungen und die symmetrische Matrix berechnet. Sie betonen die Bedeutung der Berechnung der Sattelpunktwerte und schlagen vor, mit Codes zu arbeiten und den Prozess zu berücksichtigen.

  • 00:10:00 In diesem Abschnitt erörtert der Sprecher die Idee von Sattelpunkten und wie man sie als Maximum eines Minimums schreibt, um schnell zu Maxima und Minima zurückzukehren. Er erklärt, dass dies zum Interlacing-Theorem führt, und gibt ein Beispiel dafür, wie man das Minimum über einen zweidimensionalen Unterraum nimmt, um das Minimum des Rayleigh-Quotienten zu finden. Indem er das Maximum dieses Minimums über alle Unterräume nimmt, ist er in der Lage, Lambda, den Sattelpunktwert, zu erhalten.

  • 00:15:00 In diesem Abschnitt erklärt der Referent, wie man mithilfe des Rayleigh-Quotienten die Maximal- und Minimalwerte in einem zweidimensionalen Raum findet. Er demonstriert, dass der Maximalwert drei ist, indem er das Maximum über alle möglichen 2D-Räume nimmt und zeigt, dass diese spezielle Wahl von V die Antwort von drei ergibt. Der Sprecher erklärt dann, dass der Mindestwert für jeden anderen Unterraum unter drei liegen wird, was bedeutet, dass der Höchstwert für die Minima ebenfalls drei ist. Das Konzept der Sattelpunkte wird ebenfalls diskutiert, wobei der Sprecher anmerkt, dass diese Punkte häufig an den höchsten Punkten bestimmter Regionen auftreten und Maxima von Minima oder Minima von Maxima sein können. Das Video endet mit einer Diskussion der Projekte und einer Aufforderung an die Zuschauer, Fragen dazu zu stellen.

  • 00:20:00 In diesem Abschnitt erläutert der Sprecher ein Modell der Überanpassung, bei dem ein Polynom vom Grad 5 verwendet wird, um 6 Punkte anzupassen. Der Sprecher weist darauf hin, dass das Polynom 5. Grades genau zu den Datenpunkten passen würde, aber es wäre auch ein fehlerhaftes Modell, weil es nicht glatt oder schön wäre. Dieses Beispiel dient als Warnung vor Überanpassung, die auftritt, wenn ein Modell zu komplex und zu eng an die Trainingsdaten angepasst ist.

  • 00:25:00 In diesem Abschnitt erörtert der Sprecher das Problem der Anpassung von Daten an ein Polynom hohen Grades. Während die Anpassung einer geraden Linie zu einer Unteranpassung führen kann, kann die Anpassung eines hochgradigen Polynoms zu einer Überanpassung führen, da es eine perfekte Anpassung für alle gegebenen Datenpunkte erzeugt, ohne Berücksichtigung des Rauschens in den Daten. Die Idee einer perfekten Anpassung hängt mit der Vandermonde-Matrix zusammen, die aufgrund des riesigen Koeffizientenvektors, der sich aus der perfekten Anpassung ergibt, eine große Inverse aufweist. Die Matrix hat eine breite Palette von singulären Werten, wobei winzige Werte neben normal großen Werten auftreten. Daher kann es schwierig sein, den richtigen Polynomgrad zu finden, der an die Daten angepasst werden kann, um ein Gleichgewicht zwischen Unteranpassung und Überanpassung zu finden.

  • 00:30:00 In diesem Abschnitt beschreibt der Referent zwei Beispiele für Open-Ended Labs für seine Klasse, eines mit Sattelpunkten und das andere mit einem einfachen neuronalen Netzwerk. Für das Sattelpunktbeispiel schlägt der Sprecher vor, Diagramme und Datentabellen an den Graduierungsumfang zu übermitteln und Schlussfolgerungen über die Sicherheit und das Risiko einer Erhöhung von K zu ziehen. In Bezug auf das Beispiel des neuronalen Netzwerks skizziert der Sprecher ein grundlegendes Klassifizierungsproblem und ermutigt die Schüler, das zu ändern Modell, wie sie es für richtig halten, während sie immer noch lineare Algebra verwenden. Der Redner erwähnt auch ein bevorstehendes Fakultätstreffen über die Pläne des MIT für Kurse in Computational Thinking, wofür dieser Kurs ein Beispiel ist. Abschließend lädt der Referent die Studierenden ein, ihm eine E-Mail mit groben Projektideen und Gruppenpräferenzen zu schicken.

  • 00:35:00 In diesem Abschnitt diskutiert der Professor die Idee eines Projekts für die Klasse und verdeutlicht seinen Umfang. Er erwähnt, dass das Projekt nicht zu groß wäre, vielleicht drei Hausaufgaben entsprechen würde, aber auch nicht trivial. Er bittet die Studenten um ihre Fragen und Beiträge zum Projekt und schlägt die Möglichkeit vor, Themen wie Convolutional Neural Nets einzubeziehen. Der Professor erwähnt auch, dass einige Studenten ein Treffen im Media Lab initiiert hätten, das erfolgreich stattgefunden habe. Er fragt, ob nach den Frühlingsferien wieder Interesse an solchen Treffen besteht.

  • 00:40:00 In diesem Abschnitt führt der Referent in die Konzepte von Mittelwert und Varianz in der Statistik ein, wie sie sich auf das tatsächliche Ergebnis und das erwartete Ergebnis beziehen und den Unterschied zwischen dem Stichprobenmittelwert und dem erwarteten Mittelwert. Der Stichprobenmittelwert wird aus dem tatsächlichen Ergebnis eines Experiments berechnet, während der erwartete Mittelwert aus den Wahrscheinlichkeiten dieser Ergebnisse berechnet wird. Auch die Varianz wird diskutiert, wobei Stichprobenvarianz und erwartete Varianz unterschieden werden. Der Sprecher erklärt, dass sich die erwarteten Werte von Mittelwert und Varianz den tatsächlichen Werten annähern, wenn die Anzahl der Proben oder Möglichkeiten zunimmt.

  • 00:45:00 In diesem Abschnitt wird das Konzept der Stichprobenvarianz besprochen, die den durchschnittlichen quadrierten Abstand vom Mittelwert eines Satzes von n Stichproben misst. In der Statistik bedeutet die Division durch n minus eins, dass dieser Abstand aus dem Stichprobenmittelwert und nicht aus Null berechnet wird, und wenn n groß ist, ist die Differenz zwischen n und n minus eins nicht signifikant. Kovarianz hingegen ist eine tiefere Idee, die eine Matrixmanipulation beinhaltet, wenn mehrere Experimente durchgeführt werden, und die gemeinsame Wahrscheinlichkeit von zwei separaten Ereignissen berechnet wird.

  • 00:50:00 In diesem Abschnitt erörtert der Sprecher die beiden Extreme der Kovarianzausgabe: unabhängige Ausgaben und vollständig abhängige Ausgaben. Während unabhängige Ausgaben eine Kovarianz von 0 haben, haben vollständig abhängige Ausgaben eine maximale Kovarianz, wobei eine Ausgabe vollständig durch die andere bestimmt wird. Der Referent erklärt dieses Konzept am Beispiel des Werfens von zusammengeklebten Münzen. Die Kovarianzmatrix für abhängige Ausgänge wäre nicht umkehrbar und symmetrisch positiv definit oder semidefinit für den zusammengeklebten Fall. Der Sprecher erwähnt, dass in Umfrageszenarien, in denen mehrere Personen in einem Haus leben, eine gewisse Kovarianz zu erwarten wäre, die jedoch nicht vollständig unabhängig wäre.
 

Vorlesung 20. Definitionen und Ungleichungen



20. Definitionen und Ungleichungen

In diesem Abschnitt des Videos erörtert der Referent verschiedene Konzepte der Wahrscheinlichkeitstheorie, darunter Erwartungswert-, Varianz- und Kovarianzmatrizen. Die Markowsche Ungleichung und die Tschebyscheffsche Ungleichung wurden ebenfalls als grundlegende Werkzeuge zum Schätzen von Wahrscheinlichkeiten eingeführt. Der Sprecher erklärt dann die Beziehung zwischen der Ungleichung von Markov und Chebychev und veranschaulicht, wie sie zu demselben Ergebnis führen. Das Konzept der Kovarianz und der Kovarianzmatrix, ein grundlegendes Werkzeug in der Wahrscheinlichkeitstheorie, wurde ebenfalls eingeführt. Das Video untersucht auch die Idee gemeinsamer Wahrscheinlichkeiten und Tensoren und erklärt, wie das Zusammenkleben von Münzen Abhängigkeiten hinzufügt und die Wahrscheinlichkeiten verändert. Abschließend erörtert der Redner die Eigenschaften der Kovarianzmatrix und betont, dass sie immer positiv semidefinit ist und eine Kombination aus positiven semidefiniten Matrizen vom Rang 1 ist.

  • 00:00:00 In diesem Abschnitt diskutiert der Dozent Erwartungswert, Varianz und Kovarianzmatrix. Der Erwartungswert, symbolisiert als „e“, ist definiert als der gewichtete Durchschnitt aller möglichen Ergebnisse basierend auf ihren Wahrscheinlichkeiten. Die Varianz hingegen ist der erwartete Wert des Quadrats des Abstands zwischen dem Mittelwert und jedem Datenpunkt. Die Kovarianzmatrix kann auch auf ähnliche Weise ausgedrückt werden. Der Dozent untersucht dann einen zweiten Ausdruck für die Varianz, indem er die Quadrate aufschreibt und sie anders kombiniert, was zu einer effizienteren Methode zur Berechnung der Varianz führt.

  • 00:05:00 In diesem Abschnitt erörtert der Sprecher einen algebraischen Prozess zum Vereinfachen einer Gleichung, um den erwarteten Wert von x zum Quadrat zu finden. Er zeigt, dass der Erwartungswert von x zum Quadrat minus dem Erwartungswert von x minus M zum Quadrat gleich der Summe der Wahrscheinlichkeiten von x zum Quadrat ist. Der Redner führt dann die Markov-Ungleichung ein, die eine statistische Ungleichung ist, die Wahrscheinlichkeiten und Erwartungen beinhaltet. Er merkt an, dass Markov ein großer russischer Mathematiker war und dass sie Markov-Ketten und -Prozesse später in diesem Buch sehen werden.

  • 00:10:00 In diesem Abschnitt erläutert der Sprecher die Markovsche Ungleichung, die dabei helfen kann, die Wahrscheinlichkeit abzuschätzen, dass X größer oder gleich einer bestimmten Zahl ist. Die Ungleichung besagt, dass die Wahrscheinlichkeit, dass X größer oder gleich a ist, kleiner oder gleich dem Mittelwert von X dividiert durch a ist. Der Sprecher gibt ein Beispiel mit einem Mittelwert von eins und einem Wert von a von drei, was zeigt, dass die Wahrscheinlichkeit, dass X größer oder gleich drei ist, kleiner oder gleich 1/3 ist. Der Sprecher merkt jedoch an, dass diese Ungleichung nur für nicht negative Ereignisse gilt und nicht mit Ereignissen verwendet werden kann, deren Ausgänge von negativ bis positiv unendlich reichen.

  • 00:15:00 In diesem Abschnitt des Videos spricht der Sprecher über die Verwendung eines Sonderfalls, um die Wahrscheinlichkeit größer oder gleich 3 zu demonstrieren. Sie verwenden die Definition des Mittelwerts, um eine bestimmte Gleichung zu schreiben und dann Annahmen zu treffen über die Werte von X1 bis X5, um die Markov-Ungleichung zu erfüllen. Sie sagen aus, dass sich die Wahrscheinlichkeiten zu 1 addieren und alle größer oder gleich 0 sind. Der Sprecher fährt dann fort, die Gleichung zu manipulieren, um zu zeigen, dass die Wahrscheinlichkeit, größer oder gleich 3 zu sein, kleiner oder gleich 1/ ist. 3 durch Subtrahieren bestimmter Werte von der Gleichung. Sie schließen, indem sie zeigen, dass die Gleichung die Markov-Ungleichung erfüllt.

  • 00:20:00 In diesem Abschnitt diskutiert der Redner die Wahrscheinlichkeitsungleichungen von Markov und Chebyshev. Bei der Markovschen Ungleichung wird die Wahrscheinlichkeit geschätzt, dass eine Variable größer oder gleich einem bestimmten Wert ist, und sie gilt nur, wenn alle Variablen größer oder gleich Null sind. Die Tschebyscheff-Ungleichung hingegen befasst sich mit der Wahrscheinlichkeit, dass eine Variable in einem bestimmten Abstand vom Mittelwert entfernt ist, und trifft keine Annahmen über die Eingaben. Diese beiden Ungleichungen sind grundlegende Werkzeuge zum Schätzen von Wahrscheinlichkeiten in der Wahrscheinlichkeitstheorie.

  • 00:25:00 In diesem Abschnitt erklärt der Sprecher die Beziehung zwischen der Ungleichung von Markov und Chebychev. Er führt eine neue Variable Y ein, die X minus M zum Quadrat ist, und erklärt, wie man ihren Mittelwert berechnet. Der Sprecher wendet dann die Ungleichung von Markov auf Y und die Ungleichung von Chebychev auf X an und zeigt, wie sie zu demselben Ergebnis führen. Schließlich führt er das Konzept der Kovarianz und der Kovarianzmatrizen ein.

  • 00:30:00 In diesem Abschnitt stellt der Sprecher das Konzept der Kovarianz und der Kovarianzmatrix vor, bei der es sich um eine M-mal-M-Matrix handelt, wobei M die Anzahl der gleichzeitig durchgeführten Experimente ist. Um dieses Konzept zu veranschaulichen, verwendet der Referent das Werfen von zwei Münzen mit einer Ausgabe (X) pro Münze. Wenn die beiden Münzen unabhängig geworfen werden, gibt es keine Korrelation zwischen den Ausgaben, aber wenn sie zusammengeklebt werden, dann werden die Ausgaben korreliert und die gemeinsamen Wahrscheinlichkeiten werden in eine 2x2-Matrix gesetzt.

  • 00:35:00 In diesem Abschnitt diskutiert der Referent das Konzept gemeinsamer Wahrscheinlichkeiten und Matrizen für Versuchsaufbauten mit unabhängigen Münzen. Sie untersuchen die Idee einer Drei-Wege-Struktur oder eines Tensors in Fällen, in denen es drei Experimente mit unabhängigen fairen Münzen gibt oder wenn Münzen zusammengeklebt werden. Die resultierenden Einträge in den Tensor wären die gemeinsamen Wahrscheinlichkeiten, die verwendet werden können, um die Wahrscheinlichkeit verschiedener Ergebnisse zu berechnen. Der Sprecher merkt an, dass die Einträge in einem einfachen Fall eines ungeklebten Experiments zwar ein Achtel betragen, das Zusammenkleben der Münzen jedoch Abhängigkeiten hinzufügt und die Wahrscheinlichkeiten verändert.

  • 00:40:00 In diesem Abschnitt des Videos diskutiert der Sprecher die gemeinsame Wahrscheinlichkeit, drei Münzen zu werfen, und wie sie in einer 3-Wege-Matrix dargestellt werden kann. Er erwähnt das Konzept der Tensoren und Kovarianzmatrizen und definiert letztere als die Varianz des gemeinsamen Ergebnisses zweier Experimente, X und Y, ausgedrückt als Summe aller möglichen Ergebnisse. Der Referent erklärt auch das Symbol P IJ und wie es sich auf das Zusammenkleben und Lösen von Münzen in verschiedenen Konfigurationen bezieht.

  • 00:45:00 In diesem Abschnitt des Videos erläutert der Sprecher die gemeinsame Wahrscheinlichkeit zweier Ereignisse – X und Y – und wie diese Wahrscheinlichkeit für verschiedene Wertepaare berechnet wird. Der Referent gibt Beispiele für die Verwendung der gemeinsamen Wahrscheinlichkeit, einschließlich der Berechnung der Wahrscheinlichkeit für ein bestimmtes Alter und eine bestimmte Größe. Der Sprecher definiert auch die Randwahrscheinlichkeiten, die die individuellen Wahrscheinlichkeiten jedes Ereignisses sind, und erklärt, wie man die Wahrscheinlichkeiten entlang Zeilen oder Spalten in einer Matrix addiert. Anschließend definiert der Referent die Kovarianzmatrix und erklärt, wie deren Einträge zu berechnen sind.

  • 00:50:00 In diesem Abschnitt spricht der Sprecher über die Kovarianzmatrix und ihre Eigenschaften. Er erklärt, dass die Varianz des X-Experiments aus der Addition aller P IJs abgeleitet wird, während die Varianz des Y-Experiments durch den Quadratwert von Sigma Y gegeben ist. Die Kovarianz zwischen X und Y ist die Summe der P IJ mal dem Abstand von X von seinem Mittelwert und dem Abstand von Y von seinem Mittelwert. Bei unabhängigen Münzen wäre die Kovarianz Null, während sie bei geklebten Münzen gleich Sigma X zum Quadrat Sigma Y zum Quadrat wäre. Die Determinante der Matrix ist im Fall der geklebten Münzen Null, was zeigt, dass die quadrierte Kovarianz die gleiche ist wie Sigma X zum Quadrat Sigma Y zum Quadrat. Die Kovarianzmatrix ist immer positiv semidefinit und ist eine Kombination aus positivem semidefinitem Rang 1, also positiv semidefinit oder positiv definit.
 

Vorlesung 21: Eine Funktion Schritt für Schritt minimieren



Vorlesung 21: Eine Funktion Schritt für Schritt minimieren

Dieser Videovortrag behandelt die grundlegenden Algorithmen zur Minimierung einer Funktion und ihre Konvergenzraten, insbesondere das Newton-Verfahren und den steilsten Abstieg. Es hebt auch die Bedeutung der Konvexität hervor, die sicherstellt, dass die Funktion ein Minimum hat, und führt das Konzept der konvexen Mengen und konvexen Funktionen ein. Der Dozent erklärt, wie man eine Funktion auf Konvexität testet, die bestimmt, ob sie Sattelpunkte oder lokale Minima hat, im Gegensatz zu einem globalen Minimum. Das Video endet mit einer Diskussion von Levenberg Marquardt, einer billigeren Version von Newtons Methode, die nicht vollständig zweiter Ordnung ist.

  • 00:00:00 In diesem Abschnitt erörtert der Dozent die Grundlagen der Optimierung, dem grundlegenden Algorithmus für Deep Learning. Die Vorlesung beginnt mit der Erläuterung der Taylor-Reihe und zeigt dann, wie die Taylor-Reihe erweitert werden kann, wenn die Funktion aus mehr als einer Variablen besteht. Der Dozent führt dann den Gradienten von F ein, der die partiellen Ableitungen von F in Bezug auf jede X-Variable darstellt. Abschließend wird der quadratische Term erklärt, und die Vorlesung endet mit der Diskussion der zweiten Ableitungen und wie sie sich mit mehr Variablen ändern.

  • 00:05:00 In diesem Abschnitt der Vorlesung wird das Konzept der Hesse-Matrix eingeführt, die die Matrix der zweiten Ableitungen einer Funktion ist. Die Hesse-Matrix ist symmetrisch und ihre Berechnung ist für kleine bis mittelgroße Werte von n durchführbar. Es gibt ein paralleles Bild für die Vektorfunktion, die die Jacobi-Matrix ist, wobei die Einträge die Ableitungen der Funktion in Bezug auf verschiedene Variablen sind. Dies sind Tatsachen der Mehrvariablenrechnung, die zum Lösen von Gleichungen in Optimierungsproblemen verwendet werden.

  • 00:10:00 In diesem Abschnitt diskutiert der Dozent Newtons Methode zur Lösung von Gleichungssystemen mit n Unbekannten, bei der eine gegebene Funktion minimiert wird. Die Newton-Methode ist der beste Weg, um n Gleichungen in n Unbekannten zu lösen, was ausgedrückt werden kann als F gleich 0, wobei F von Eins gleich Null ist und es insgesamt n Gleichungen gibt. Der Dozent zeigt, wie man mit dem Newton-Verfahren die Gleichung x zum Quadrat minus 9 gleich 0 löst, die als Funktion geschrieben werden kann, und demonstriert Schritt für Schritt, wie man das Verfahren anwendet.

  • 00:15:00 In diesem Abschnitt erläutert der Dozent, wie das Newton-Verfahren verwendet wird, um eine Funktion zu minimieren und wie man bestimmt, wie schnell sie konvergiert. Sie beginnen mit der Vereinfachung der Formel, die X sub K + 1 bestimmt, und zeigen, dass, wenn X sub K genau 3 ist, dann X sub K + 1 auch 3 ist. Dann konzentrieren sie sich darauf, wie schnell sich der Fehler Null nähert, und subtrahieren 3 von beiden Seiten, um 1 über X sub K herauszurechnen. Die Vereinfachung der Gleichung zeigt, dass der Fehler bei Schritt K + 1 bei jedem Schritt quadriert wird, was beweist, warum Newtons Methode fantastisch ist, wenn sie nahe genug ausgeführt wird.

  • 00:20:00 In diesem Abschnitt erörtert der Dozent die Verwendung der Newton-Methode zur Optimierung und wie sie auf sehr komplizierte Verlustfunktionen mit Tausenden oder sogar Hunderttausenden von Variablen anwendbar ist. Der Vortrag behandelt zwei Methoden -- steilster Abstieg und Newton-Methode -- wobei der steilste Abstieg das Bewegen in Richtung des Gradienten von F beinhaltet, aber mit der Freiheit, über die Schrittgröße zu entscheiden. Andererseits berücksichtigt das Newton-Verfahren die zweite Ableitung von F und ermöglicht eine schnellere Konvergenz, könnte aber auch zu unerwünschten Lösungen konvergieren oder für bestimmte Startpunkte explodieren. Dies führt zum Konzept der Anziehungszonen, bei denen bestimmte Ausgangspunkte zur gewünschten Lösung führen, während andere zu unerwünschten oder ins Unendliche führen.

  • 00:25:00 In diesem Abschnitt erläutert der Dozent zwei Methoden zur schrittweisen Minimierung einer Funktion: steilster Abstieg und Newton-Methode. Beide beinhalten die iterative Auswahl einer Richtung im n-dimensionalen Raum und die Bewegung um eine bestimmte Strecke entlang dieser Richtung, aber der steilste Abstieg verwendet den Gradienten der Funktion, um die Richtung zu wählen, während Newtons Methode die hessische oder zweite Ableitung verwendet. Der Vortrag erläutert auch das Konzept einer exakten Zeilensuche und die Bedeutung der Wahl einer angemessenen Lernrate bei diesen Methoden.

  • 00:30:00 In diesem Abschnitt behandelt der Dozent die grundlegenden Algorithmen zur Minimierung einer Funktion und deren Konvergenzraten. Der Dozent erklärt, dass das Newton-Verfahren eine quadratische Konvergenzrate hat, was es superschnell macht, wenn es nah genug gestartet wird. Im Gegensatz dazu hat der Algorithmus für den steilsten Abstieg eine lineare Konvergenzrate, was ihn weniger effizient macht. Der Dozent betont, dass der Ausgangspunkt für die Lösung dieser Probleme die Konvexität sein sollte, die sicherstellt, dass die Funktion ein Minimum hat. Der Dozent definiert konvexe Mengen und Funktionen und erläutert deren Bedeutung bei der Minimierung einer Funktion für Punkte in einer konvexen Menge. Der Vortrag schließt mit einer Diskussion von Levenberg Marquardt, einer billigeren Version von Newtons Methode, die nicht vollständig zweiter Ordnung ist.

  • 00:35:00 In diesem Abschnitt des Videos erläutert der Sprecher, wie eine Funktion minimiert wird. Die Einschränkungen für die Funktion werden durch eine konvexe Menge definiert, was bedeutet, dass jede Linie, die zwischen zwei Punkten innerhalb der Menge gezogen wird, innerhalb der Menge bleiben muss. Der Sprecher nennt das Beispiel zweier überlappender Dreiecke, die zusammengenommen keine konvexe Menge bilden.

  • 00:40:00 In diesem Abschnitt wird das Konzept der konvexen Mengen und konvexen Funktionen eingeführt. Es wird darauf hingewiesen, dass die Schnittmenge zweier konvexer Mengen immer konvex ist und die leere Menge als konvexe Menge betrachtet wird. Die Anmerkungen im Video betonen, wie wichtig es ist, diese Konzepte beim Minimieren von Funktionen zu verstehen, da das Prototypenproblem darin besteht, Funktionen mit einem konvexen Bild zu finden. Das Video verbindet auch die Definition einer konvexen Funktion mit der Definition einer konvexen Menge und stellt fest, dass der Graph einer konvexen Funktion einer Schale ähnelt, während die Punkte auf dieser Oberfläche keine konvexen Mengen sind. Die Menge der Punkte auf dem Graphen ist jedoch eine konvexe Menge.

  • 00:45:00 In diesem Abschnitt der Vorlesung behandelt der Referent einen Test für die konvexe Funktion. Er erklärt, dass zwei konvexe Funktionen verwendet werden können, um eine minimale und maximale Funktion zu erstellen, und eine davon wird konvex sein, während die andere dies nicht ist. Die minimale Funktion hat einen Knick und ist daher nicht konvex, während die maximale Funktion konvex ist. Der Referent erwähnt auch, dass dieser Test auf maximal 1500 Funktionen erweitert werden kann, und wenn alle 1500 Funktionen konvex sind, wird ihr Maximum auch konvex sein.

  • 00:50:00 In diesem Abschnitt erklärt der Sprecher, wie man eine Funktion auf Konvexität testet. Für eine Funktion mit nur einer Variablen im Kalkül kann eine konvexe Funktion bewiesen werden, indem geprüft wird, ob die zweite Ableitung positiv oder Null ist. Bei einer Vektorfunktion mit mehreren Variablen würde der Funktion eine symmetrische Matrix F hinzugefügt. Der Test auf Konvexität wäre hier positiv semidefinit für die Hesse, da die zweiten Ableitungen eine Matrix ergeben. Konvexe Probleme haben keine Sattelpunkte oder lokale Minima, sondern nur das globale Minimum, was sie wünschenswert macht.
 

Vorlesung 22. Gradient Descent: Downhill to a Minimum



22. Steigungsabfahrt: Bergab auf ein Minimum

Im Video „Gradient Descent: Downhill to a Minimum“ erörtert der Referent die Bedeutung des Gradientenabstiegs bei der Optimierung und beim Deep Learning, bei denen das Ziel darin besteht, eine Funktion zu minimieren. Der Referent stellt die Steigung und das Hessische vor und illustriert die Stufen des steilsten Gefälles anhand einer quadratischen Funktion. Der Referent erörtert auch die Interpretation des Gradienten und des Hessischen sowie deren Rolle bei der Messung der Konvexität. Der Sprecher vertieft sich in die Auswahl der geeigneten Lernrate und betont die Bedeutung der Bedingungszahl bei der Steuerung der Konvergenzgeschwindigkeit. Das Video bietet auch praktische Beispiele und Formeln, um das Konzept des Gradientenabstiegs, einschließlich der Heavy-Ball-Methode, zu verstehen.

  • 00:00:00 In diesem Abschnitt diskutiert der Referent den Gradientenabstieg als zentralen Algorithmus in neuronalen Netzen, Deep Learning, maschinelles Lernen und Optimierung im Allgemeinen. Das Ziel besteht darin, eine Funktion zu minimieren, und wenn es zu viele Variablen gibt, um zweite Ableitungen zu nehmen, liegt der Fokus auf den ersten Ableitungen der Funktion. Der Referent stellt die Idee von Gradient und Hessisch sowie die Rolle der Konvexität vor, bevor er auf ein entscheidendes Beispiel einer reinen quadratischen Funktion mit zwei Unbekannten eintaucht. Anhand des Beispiels demonstriert der Sprecher die Schritte des steilsten Abstiegs und wie schnell sie zur Antwort, dem Mindestpunkt, zusammenlaufen. Der Referent erklärt auch die Bedeutung der Bedingungszahl für die Konvergenzgeschwindigkeit und wie man den Gradienten einer Funktion interpretiert und berechnet.

  • 00:05:00 In diesem Abschnitt erklärt der Sprecher, wie der Gradient und das Hessische einer Fläche zu interpretieren sind. Am Beispiel einer Fläche, bei der die Steigung konstant ist und die Hesse nur zweite Ableitungen von Null enthält, zeigt der Referent, wie man die Fläche visualisiert und die Steigung und die Hesse in Bezug auf steilste Steigung oder Gefälle und Pegelsätze interpretiert. Der Referent betont, dass die Hesse-Matrix der zweiten Ableitungen Auskunft über die Form einer Fläche gibt und wie schnell sie sich in verschiedene Richtungen ändert.

  • 00:10:00 In diesem Abschnitt wird das Konzept des Hesseschen als Werkzeug zur Messung der Konvexität einer Funktion eingeführt. Der Hesse einer Funktion sagt uns, ob eine Oberfläche konvex ist oder nicht, wobei positive semidefinite oder positiv definite Hesse die Konvexität anzeigen. Eine lineare Funktion ist konvex, aber nicht streng konvex, während eine streng konvexe Funktion nach oben gebogen wäre. Ein Beispiel für eine streng konvexe Funktion ist gegeben, nämlich 1/2 x transponiertes x, das einen minimalen Wert hat, wenn der Gradient die Hälfte von sx zum Quadrat beträgt.

  • 00:15:00 In diesem Abschnitt erörtert der Referent das Konzept, den Minimalwert einer quadratischen Funktion mithilfe des Gradientenabstiegs zu ermitteln. Das Minimum wird an einem Punkt erreicht, an dem der Gradient Null ist, und dieser Punkt wird als argh men bezeichnet. Der Referent betont, dass dieser vom eigentlichen Minimalwert der Funktion abweicht und dass der Fokus oft eher auf dem Finden des Punktes liegt, an dem das Minimum erreicht wird, als auf dem Minimalwert selbst. In diesem speziellen Beispiel ist der Mindestwert null, da kein linearer Term vorhanden ist.

  • 00:20:00 In diesem Abschnitt diskutiert der Referent die grundlegende Minimierungsfrage, das Minimum einer quadratischen Funktion zu finden. Die Funktion geht durch Null und erreicht an einem bestimmten Punkt ihren Tiefpunkt, und indem wir diesen Punkt einstecken, können wir ihr niedrigstes Niveau bestimmen. Der Sprecher erwähnt eine bemerkenswerte konvexe Funktion und stellt fest, dass die Konvexität das ist, was die Dinge wirklich zum Laufen bringt. Diese Funktion ist eine Funktion einer Matrix und enthält N quadrierte Variablen.

  • 00:25:00 In diesem Abschnitt diskutiert der Sprecher eine konvexe Funktion, die man erhält, indem man die Determinante einer Matrix nimmt, gefolgt von der Logarithmierung mit negativem Vorzeichen. Die resultierende Funktion ist konvex, und für eine gegebene Matrix fungieren die partiellen Ableitungen als die Einträge der Inversen dieser Matrix. Der Sprecher vertieft sich dann in die Ableitung der Determinante einer Matrix in Bezug auf ihre Einträge und betont die Bedeutung der Berechnung dieser Ableitungen in Gradientenabstiegsalgorithmen.

  • 00:30:00 In diesem Abschnitt erklärt der Sprecher die Determinante und ihre grundlegende Eigenschaft, die besagt, dass sie in Zeile 1 linear ist. Er geht auch auf die Formel für die Kofaktorerweiterung einer Determinante ein und verbindet sie mit der Tatsache, dass der Gradient linear ist die Einträge von X invers. Der Sprecher führt dann den Gradientenabstieg ein und stellt seine Formel bereit, die die Schrittgröße und den Gradienten von s bei X beinhaltet. Die einzige Eingabe, die zur Entscheidungsfindung übrig bleibt, ist die Schrittgröße.

  • 00:35:00 In diesem Abschnitt erörtert der Ausbilder die Bedeutung der Auswahl der geeigneten Lernrate beim Gradientenabstieg. Wenn die Lernrate zu groß ist, wird die Funktion oszillieren und schwierig zu optimieren sein. Wenn die Lernrate andererseits zu klein ist, dauert es zu lange, bis der Algorithmus konvergiert. Eine Möglichkeit, die optimale Lernrate zu wählen, ist eine exakte Zeilensuche, die jedoch bei großen Problemen zeitaufwändig sein kann. Stattdessen schätzen Menschen typischerweise eine geeignete Lernrate und passen sie nach Bedarf durch Backtracking-Liniensuche an. Der Dozent betont die Bedeutung der Konditionszahl für die Steuerung der Konvergenzgeschwindigkeit und stellt die Frage, wie stark eine exakte Liniensuche die Funktion reduzieren würde.

  • 00:40:00 In diesem Abschnitt diskutiert der Sprecher ein Beispiel, um den Gradientenabstieg besser zu verstehen. Es wird eine besondere Funktion eingeführt, bei der die genauen Antworten bekannt sind, sodass Vergleiche angestellt werden können. Beginnend an einem Punkt auf der Oberfläche dieser Funktion wendet der Sprecher die Gradientenabstiegsformel an und berechnet die Iterationen für diese spezielle Funktion. Der Sprecher stellt dann eine schöne Formel vor, die als bestmögliches Beispiel zum Verständnis des Gradientenabstiegs dienen soll.

  • 00:45:00 In diesem Abschnitt erörtert der Sprecher, wie wichtig das Verhältnis (1-B)/(1+B) für die Bestimmung der Konvergenzgeschwindigkeit während des Gradientenabstiegs ist. Wenn B nahe Null ist, ist das Verhältnis nahe Eins, was zu langsamer Konvergenz führt, und wenn B nahe Eins ist, ist das Verhältnis nahe Null, was zu schneller Konvergenz führt. Der Referent erklärt am Beispiel von Pegelmengen und Ellipsen, wie das schmale Tal bei Annäherung an das Minimum zu einer langsamen Konvergenz führen kann. Der Referent betont die Bedeutung einer guten Konditionszahl für die Optimierung.

  • 00:50:00 In diesem Abschnitt erläutert der Sprecher, wie sich der Gradientenabstieg einer Kurve mit einer Zickzackbahn nähert, um schließlich einen bestimmten Punkt zu erreichen. Er betont, dass der Multiplikator 1 - B/ (1 + B) eine entscheidende Rolle spielt, und für eine konvexe Funktion ist diese Größe entscheidend für die Bestimmung der Konvergenz des steilsten Abfalls. In der nächsten Vorlesung geht es um Momentum oder Heavy Ball, was das Hinzufügen eines zusätzlichen Begriffs beinhaltet, der es der Bewegung ermöglicht, sich zu beschleunigen, anstatt sie nur durch den steilsten Abstieg an jedem Punkt zu dirigieren. Die Idee ist, den Schwung eines schweren Balls übernehmen und herunterrollen zu lassen, ähnlich wie es im wirklichen Leben der Fall wäre.
 

Vorlesung 23. Gradientenabstieg beschleunigen (Momentum verwenden)



23. Beschleunigung des Gradientenabstiegs (Momentum verwenden)

In diesem Video wird das Konzept des Impulses beim Beschleunigen des Gradientenabstiegs erläutert. Der Moderator erklärt die grundlegende Formel für den Gradientenabstieg und zeigt, wie das Hinzufügen von Schwung zu einem schnelleren Abstieg als bei der herkömmlichen Methode führen kann, was letztendlich zu erheblichen Verbesserungen führt. Sie diskutieren auch ein kontinuierliches Modell des steilsten Abfalls und erklären, wie es als Differentialgleichung zweiter Ordnung mit einem Impulsterm analysiert werden kann. Der Moderator betont, wie wichtig es ist, beide Eigenwerte zu minimieren, wenn Impuls verwendet wird, um den größten Eigenwert zu minimieren, indem Werte für s und Beta gewählt werden, um die Eigenwerte der Matrix so klein wie möglich zu machen. Sie diskutieren auch Nesterovs Methode und schlagen vor, dass es möglich sein könnte, weitere Verbesserungen zu erzielen, indem man zwei oder drei Schritte oder mehr zurückgeht.

  • 00:00:00 In diesem Abschnitt erörtert der Sprecher die grundlegende Gradientenabstiegsformel, bei der der neue Punkt der alte Punkt abzüglich der Schrittgröße mal dem negativen Gradienten bei XK ist, der die Richtung des Abstiegs ist. Das Hinzufügen von Schwung, um Zickzacks beim Gradientenabstieg zu vermeiden, führt zu einem schnelleren Abstieg als bei der normalen Methode. Es gibt auch eine Alternative zum Momentum, die den Abstieg beschleunigt, entwickelt von einem russischen Mathematiker namens Nestoroff. Für maschinelle Lernprobleme mit Hunderttausenden von Variablen wird stochastischer Gradientenabstieg verwendet, bei dem ein Mini-Stapel von Trainingsdaten zufällig oder systematisch ausgewählt wird, um einen Stapel von Trainingsproben für jeden Schritt auszuführen.

  • 00:05:00 In diesem Abschnitt erörtert der Sprecher den Abfall der steilsten Richtung und die Pegelsätze für ein Modellproblem mit einer Funktion von X und Y im Quadrat gleich einer Konstanten, die Ellipsen bildet. Sie erklären, dass der optimale Haltepunkt dort ist, wo Sie die am weitesten entfernte Ellipse im Levelset berühren und wieder nach oben gehen. Der Sprecher führt den Impulsterm ein, um die Formel für den steilsten Abstieg zu verbessern, und verfolgt seinen Abstieg mit einem Zick-Zack-Muster, was die Verbesserung des Werts der Eigenvektoren zeigt. Der Sprecher kommt zu dem Schluss, dass der Ausdruck mit Schwung ein Wunder ist und erhebliche Verbesserungen bringt.

  • 00:10:00 In diesem Abschnitt des Videos erörtert der Sprecher die Verwendung von Momentum beim Beschleunigen des Gradientenabstiegs. Der Decay-Term in Momentum sagt Ihnen, wie schnell der Decay kleiner ist, und mit Momentum ändert sich dieser Term von 1 minus B über 1 plus B zu eins minus Quadratwurzel von B über 1 plus Quadratwurzel von B. Der Sprecher nimmt das Beispiel von B ist 1 über 100, und das neue X ist das alte X minus dem Gradienten mit einem zusätzlichen Term, der uns ein wenig Gedächtnis gibt. Dieser Begriff beinhaltet das Nehmen einer neuen Größe Z mit einer Schrittgröße, und anstatt Z nur als Gradient zu nehmen, was der steilste Abfall wäre, fügt der Sprecher ein mehrfaches Beta des vorherigen Z hinzu, das die Suchrichtung ist.

  • 00:15:00 In diesem Abschnitt erörtert der Sprecher das Konzept des Impulses beim Beschleunigen des Gradientenabstiegs. Anstatt einen Punkt zur Darstellung der Funktion zu verwenden, schlägt der Sprecher vor, einen schweren Ball zu verwenden, der sich schneller durch das Tal der Kostenfunktion bewegt. Dies wird erreicht, indem der vorherige Schritt in die Berechnungen einbezogen wird, was zu einem dreistufigen Verfahren anstelle eines zweistufigen Verfahrens führt. Der Referent bezieht dies dann auf ein kontinuierliches Modell des steilsten Abfalls und erklärt, wie es als Differentialgleichung zweiter Ordnung mit einem Impulsterm analysiert werden kann. Anschließend zeigen sie, wie dies als System aus zwei Gleichungen erster Ordnung geschrieben werden kann, die verwendet werden können, um einen effizienteren und schnelleren Gradientenabstiegsalgorithmus zu erstellen.

  • 00:20:00 In diesem Abschnitt erörtert der Sprecher, wie analysiert werden kann, was passiert, wenn k im beschleunigten Gradientenabstiegsalgorithmus vorwärts wandert. Sie erklären, dass es bei jedem Schritt ein konstantes Koeffizientenproblem gibt, da die XZ-Variable mit einer Matrix multipliziert wird. Der Sprecher erwähnt auch, dass sie, um jeden Eigenvektor von s zu verfolgen, jedem Eigenwert folgen, was es ihnen ermöglicht, die Formel in Bezug auf Skalare statt Vektoren umzuschreiben.

  • 00:25:00 In diesem Abschnitt erörtert der Sprecher, wie man einen Eigenvektor verfolgt und ihn verwendet, um das gesamte Problem skalar zu machen. Durch die Wahl der Schrittgröße und des Impulskoeffizienten können sie eine Matrix erstellen, die die Koeffizienten des Eigenvektors bei jedem Schritt multiplizieren kann, um ihn zu aktualisieren. Indem sie s und Beta so klein wie möglich machen, können sie sicherstellen, dass der Algorithmus die Verlustfunktion über den gesamten Bereich möglicher Lambdas minimiert. Ziel ist es, diese Werte so zu wählen, dass der Prozess so effizient wie möglich wird.

  • 00:30:00 In diesem Abschnitt erklärt der Referent das Konzept der Konditionszahl, die das Verhältnis des größten Eigenwerts zum kleinsten Eigenwert einer symmetrischen positiv definiten Matrix ist. Eine höhere Bedingungszahl bedeutet ein schwierigeres Problem, eine niedrigere bedeutet ein einfacheres Problem. Der Referent erklärt, wie man den Impuls nutzt, um den Gradientenabstieg zu beschleunigen und den größten Eigenwert zu minimieren, indem man Werte für s und Beta wählt, um die Eigenwerte der Matrix so klein wie möglich zu machen. Der Referent betont, dass es wichtig ist, beide Eigenwerte zu minimieren, da es sich als tödlich erweisen kann, einen kleinen, aber einen großen Eigenwert zu haben.

  • 00:35:00 In diesem Abschnitt des Videos diskutiert der Sprecher ein Problem des Findens der optimalen Parameter s und beta für eine Zwei-mal-zwei-Matrix, basierend auf den von Lambda, m und Capya abhängigen Eigenwerten. Das Ziel besteht darin, Parameter zu wählen, die zu einem möglichst kleinen Eigenwert führen, was zu einer schnelleren Konvergenz führt. Der Referent stellt die Formel für das optimale s und Beta vor, die vom Verhältnis zwischen kleinem m und großem M abhängen, und erklärt, wie man anhand dieser Formel den resultierenden minimalen Eigenwert berechnet. Letztendlich kommt der Sprecher zu dem Schluss, dass diese optimale Wahl von s und Beta zu Eigenwerten führt, die kleiner als eine bestimmte Zahl sind, was zu einer schnelleren Konvergenz führt.

  • 00:40:00 In diesem Abschnitt spricht der Redner über die Nutzung von Momentum zur Verbesserung der Konvergenzrate beim maschinellen Lernen. Sie erwähnen Nesterovs Methode, um eine etwas andere Idee zu verwenden, die den vorherigen Zeitwert beinhaltet und den Gradienten an einem anderen Punkt auswertet. Der Referent weist darauf hin, dass es inzwischen sehr beliebte Methoden für maschinelles Lernen gibt, die eine einfache Formel beinhalten, um die vorherigen Werte zu addieren, wie z. B. ADA grad. Sie schlagen auch vor, dass es möglich sein könnte, weitere Verbesserungen zu erzielen, indem man zwei oder drei Schritte oder mehr zurückgeht, wie dies bei Rückwärtsdifferenzformeln in MATLAB-Software und bei Planetenberechnungen der Fall ist.

  • 00:45:00 In diesem Abschnitt spricht der Moderator über den Impulsterm und Nesterov, bei dem der Gradient an einem Punkt zwischen XK und XK minus 1 bewertet wird. Der Bewertungspunkt für den Gradienten von F liegt an einem nicht ganzzahligen Punkt, was unerwartet und seltsam ist, weil es kein Mesh-Punkt ist. Dies beinhaltet XK plus 1, XK und XK minus 1, also ist es eine Methode zweiter Ordnung. Um es zu analysieren, wird der Prozess des Schreibens in zwei Schritten erster Ordnung befolgt, um die Koeffizienten in Nesterov zu optimieren. Dieser Prozess beinhaltet das Schreiben als gekoppeltes System aus einem Schritt, das eine Matrix hat, das Finden der Matrix, das Finden der Eigenwerte der Matrix und das Machen dieser Eigenwerte so klein wie möglich.
 

Vorlesung 24. Lineare Programmierung und Zwei-Personen-Spiele



24. Lineare Programmierung und Zwei-Personen-Spiele

Dieses YouTube-Video behandelt das Thema lineare Programmierung und Zwei-Personen-Spiele. Die lineare Programmierung ist der Prozess der Optimierung einer linearen Kostenfunktion, die einer Reihe linearer Einschränkungen unterliegt, und wird in Bereichen wie Wirtschaft und Technik verwendet. Das Video erklärt die in der linearen Programmierung verwendeten Algorithmen, einschließlich der Simplex-Methode und der Inneren-Punkt-Methode, sowie das Konzept der Dualität, bei dem das Primalproblem und sein duales Problem eng miteinander verbunden sind und mit der Simplex-Methode gelöst werden können. Das Video behandelt auch, wie lineare Programmierung auf Zwei-Personen-Spiele angewendet werden kann, einschließlich des Prozesses, eine Obergrenze für den maximalen Fluss in einem Netzwerk zu finden und ein Spiel mit einer Matrix zu lösen. Abschließend erörtert das Video kurz die Grenzen der Anwendung dieser Techniken auf Spiele mit drei oder mehr Personen und erwähnt, dass die nächste Vorlesung den stochastischen Gradientenabstieg behandeln wird.

  • 00:00:00 In diesem Abschnitt führt der Dozent in das Thema der linearen Programmierung als Teil der Optimierung ein und erklärt, was es ist und wie es funktioniert. Er definiert die lineare Programmierung als den Prozess der Optimierung einer linearen Kostenfunktion, die einer Reihe linearer Einschränkungen unterliegt. Er stellt fest, dass sowohl der Kostenvektor als auch die Beschränkungsgleichungen linear sind. Wenn es jedoch Einschränkungen gibt, ist das Problem nicht wirklich linear, da die Einschränkungsgleichungen es komplexer machen können. Trotzdem ist die lineare Programmierung ein wichtiger Bestandteil der Optimierung und wird häufig in Bereichen wie Wirtschaftswissenschaften und Ingenieurwissenschaften eingesetzt.

  • 00:05:00 In diesem Abschnitt behandelt der Sprecher die lineare Programmierung und Zwei-Personen-Spiele. Sie erklären das Konzept der zulässigen Menge X, die eine Beschränkungsmenge in der Sprache der linearen Algebra ist, und zeichnen eine Visualisierung, um das Konzept zu zeigen. Sie verwenden ein Beispiel für die Minimierung einer Funktion mit einfachen Einschränkungen und Ungleichungen, um zu erklären, warum eine der drei Ecken eines Dreiecks gewinnt, was gelöst wird, indem der Mindestwert an dem Punkt gefunden wird, an dem sich die Ebene mit dem Oktanten schneidet. Die Kosten sind linear, und die Lösung ist entweder eine der drei Ecken oder wenn gleiche Werte entlang dieser Ecken auftreten. In dem gegebenen Beispiel ist drei null null die gewinnende Ecke.

  • 00:10:00 In diesem Abschnitt erklärt das Video die beiden Algorithmen, die bei der linearen Programmierung verwendet werden: Simplex-Methode und Innere-Punkt-Methode. Die Simplex-Methode bewegt sich entlang der Kanten der zulässigen Menge, um die optimale Ecke zu erreichen, während die Inner-Point-Methoden innerhalb der zulässigen Menge gehen, um die Ableitungen zu erhalten und zu minimieren. Die innere Methode ist die neuere Idee, und obwohl der genaue von Karmarkar vorgeschlagene Algorithmus nicht überlebt hat, wird die Idee noch heute verwendet und erforscht. Beide Algorithmen stehen weiterhin in Konkurrenz zueinander.

  • 00:15:00 In diesem Abschnitt erörtert der Referent die lineare Programmierung und ihre verschiedenen Arten wie nichtlineare Programmierung, quadratische Programmierung, semi-definite Programmierung und innere Punktmethoden. Der Redner führt die Idee der Dualität ein, bei der ein duales Problem des linearen Programmierproblems erstellt wird und das primäre Problem in ein Maximierungsproblem mit linearen Kosten und linearen Ungleichungsbeschränkungen umgewandelt wird. Der Sprecher erklärt dann, dass das Primalproblem und sein duales Problem eng miteinander verbunden sind und mit der Simplex-Methode gelöst werden können. Darüber hinaus stellt der Redner die Schlüsselidee der Dualität vor, die besagt, dass der Maximalwert immer kleiner oder gleich einem möglichen zulässigen Wert ist. Schließlich gibt der Sprecher einen einzeiligen Beweis für die Ungleichung B transponiert Y ist kleiner oder gleich C transponiert X.

  • 00:20:00 In diesem Abschnitt erörtert der Redner die Bedeutung von X größer oder gleich Null in der linearen Programmierung und seine Rolle beim Erreichen einer schwachen Dualität. Die Tatsache, dass X größer oder gleich Null ist, stellt sicher, dass die gewünschten Ungleichungen erfüllt sind und dass das vom System erhaltene Ergebnis korrekt ist. Der Redner erwähnt das Konzept der Dualität und wie es sich auf lineare Programmierung und Zwei-Personen-Spiele bezieht, und betont, wie wichtig es ist, in beiden Fällen auf den Algorithmus zu achten. Der Redner liefert auch ein Beispiel für maximalen Durchfluss gleich minimalem Schnitt, um die besprochenen Konzepte zu demonstrieren.

  • 00:25:00 In diesem Abschnitt erörtert der Redner das Problem der linearen Programmierung und Zwei-Personen-Spiele im Zusammenhang mit der Maximierung des Flusses durch ein Netzwerk mit Beschränkungen der Edge-Kapazitäten. Sie erklären, dass das Ziel darin besteht, den Fluss an der Senke zu maximieren und gleichzeitig sicherzustellen, dass die Flussvariable die durch die Kapazitäten der Kanten zulässige Flussmenge nicht überschreitet. Das Problem kann mit ganzzahliger Programmierung gelöst werden, kann aber sicher gelockert werden, um nicht ganzzahlige Variablen zuzulassen. Der Referent liefert Beispiele zur Lösung dieses Problems und erörtert die Bedeutung der Auswahl geeigneter Edge-Kapazitäten.

  • 00:30:00 In diesem Abschnitt behandelt der Dozent lineare Programmierung und Zwei-Personen-Spiele. Insbesondere untersucht er das Auffinden einer Obergrenze für den maximalen Fluss in einem Netzwerk, wobei er sich auf einen Schnitt im Netzwerk konzentriert, der Kanten trennt, die zu einer Quelle gehören, und diejenigen, die zu einem Ziel gehören. Der maximale Durchfluss für dieses Beispiel beträgt 14, was dem minimalen Schnitt entspricht. Das Konzept der Dualität wird auch eingeführt, um bei der Optimierung eines Problems eine obere Schranke zu finden.

  • 00:35:00 In diesem Abschnitt behandelt der Sprecher die lineare Programmierung und Zwei-Personen-Spiele. Das Maximum-Cut-Problem in einem großen Netzwerk kann schnell mit linearer Programmierung gelöst werden, obwohl der Maximum-Cut bei Tausenden von Kanten möglicherweise nicht sichtbar ist. Die Simplex-Methode, die fast immer einen Durchschnittsfall hat, ist in der Zeit polynomial zu lösen. Der Redner spricht auch über Dualität in der linearen Programmierung, wo kein Fluss die Kapazität des Schnitts überschreiten kann. Abschließend spricht der Sprecher über Zwei-Personen-Spiele und eine Auszahlungsmatrix, die verwendet wird, um Entscheidungen basierend auf Auszahlungen für die Minimierung und Maximierung von Spielern zu treffen. Das Spiel ist ein Nullsummenspiel, was bedeutet, dass alle Auszahlungen von X an Y gehen.

  • 00:40:00 In diesem Abschnitt behandelt das Video die lineare Programmierung und Zwei-Personen-Spiele anhand eines Beispiels, bei dem X eine kleine Zahl und Y eine große Zahl erreichen möchte. Dies führt zu einem einfachen Spiel mit einem Sattelpunkt, bei dem Y jedes Mal Spalte zwei und X jedes Mal Zeile eins wählt. Wenn sich jedoch das Beispiel ändert und Y auf Spalte zwei abzielt, muss X eine gemischte Strategie wählen, da kein Sattelpunkt vorhanden ist. Y verfolgt auch eine gemischte Strategie, die X schließlich herausfindet, was zu einem Wettbewerb führt, um die beste Wahl zwischen 0 und 1 zu finden.

  • 00:45:00 In diesem Abschnitt erörtert der Sprecher den Lösungsprozess eines Zwei-Personen-Spiels mit linearer Programmierung und gibt ein Beispiel für das Lösen eines Spiels mit einer Matrix. Die optimale Strategie für Y ist 2/3 in der ersten Spalte und 1/3 in der zweiten Spalte. Das beste q4 für X wird bei dieser optimalen Y-Strategie bestimmt. Der Sprecher erklärt, dass es andere Spalten oder Zeilen für X geben könnte, die nicht in das Optimum verwechselt werden.

  • 00:50:00 In diesem Abschnitt diskutiert der Sprecher die Verbindungen zwischen linearer Programmierung und Zwei-Personen-Spielen. Er weist auf die Bedeutung des Dualitätssatzes hin und wie er sich auf die Lösung von Optimierungsproblemen bezieht, sowie auf die Einschränkungen bei der Anwendung dieser Techniken auf Spiele mit drei oder mehr Personen. Er erzählt auch kurz die Geschichte von John Nash und seinen Beiträgen auf diesem Gebiet, einschließlich seiner Verbesserung und seines anschließenden tragischen Todes. Abschließend erwähnt der Referent, dass der nächste Vortrag den stochastischen Gradientenabstieg behandeln wird.
 

Vorlesung 25. Stochastischer Gradientenabstieg



25. Stochastischer Gradientenabstieg

In diesem Video wird das Konzept des stochastischen Gradientenabstiegs (SGD) als Optimierungsmethode zur Lösung umfangreicher maschineller Lernprobleme vorgestellt, die häufig in Form eines Finite-Summen-Problems auftreten. Der Referent erklärt, wie SGD zufällige Datenpunkte auswählt, um den Gradienten zu berechnen, um die Berechnung zu beschleunigen, und wie es sich aufgrund der schwankenden Natur der Methode anders verhält als der Batch-Gradientenabstieg, wenn es sich dem Optimum nähert. Die Schlüsseleigenschaft von SGD ist, dass die Schätzung des stochastischen Gradienten eine unvoreingenommene Version des wahren erwarteten Gradienten ist und die Varianz des stochastischen Gradienten kontrolliert werden muss, um das Rauschen zu reduzieren. Die Verwendung von Mini-Batches wird als Mittel für kostengünstige Parallelität beim Deep-Learning-GPU-Training diskutiert, aber die Auswahl der richtigen Mini-Batch-Größe ist immer noch eine offene Frage, die sich auf die Robustheit der Lösung bei Vorhandensein von unsichtbaren Daten auswirken kann. Zu den Herausforderungen bei der Optimierung von SGD gehören die Bestimmung der Mini-Batch-Größe und die Berechnung stochastischer Gradienten, aber Forscher versuchen, die Wirksamkeit von SGD in neuronalen Netzwerken durch die Entwicklung einer Generalisierungstheorie zu verstehen.

  • 00:00:00 In diesem Abschnitt stellt der Referent das Konzept des stochastischen Gradientenabstiegs als alte Optimierungsmethode vor, die immer noch zum Trainieren großer maschineller Lernsysteme verwendet wird. Sie erklären, dass das Lösen von Optimierungsproblemen in der Datenwissenschaft von entscheidender Bedeutung ist und diese Probleme oft ziemlich groß sind. Der Referent stellt eine Implementierung des Gradientenabstiegs in MATLAB vor und zeigt, dass nur eine Zeile geändert werden muss, um alle Deep-Learning-Toolboxen und groß angelegtes maschinelles Lernen zu steuern. Der Referent beschreibt dann die Optimierungsprobleme beim maschinellen Lernen, bei denen ein x über einer als Summe geschriebenen Kostenfunktion gefunden wird. Diese werden Finite-Summen-Probleme genannt und werden typischerweise mit stochastischen Optimierungsmethoden gelöst.

  • 00:05:00 In diesem Abschnitt diskutiert der Referent maschinelles Lernen im großen Maßstab, was bedeutet, dass sowohl die Anzahl der Trainingsdatenpunkte (n) als auch die Dimensionalität der Vektoren (d) groß sein können. Ein großes n kann Millionen oder Milliarden erreichen, und ein großes d könnte aus bis zu einer Milliarde Merkmalen bestehen. Dies treibt eine Menge Forschung zu Optimierungsmethoden für groß angelegtes maschinelles Lernen voran, einschließlich der Suche nach sublinearen Zeitalgorithmen in Datenstrukturen und Hash-Tricks, um mit solchen großen Datenmengen umzugehen. Der Referent gibt Beispiele für die klassischste Frage in der linearen Algebra, das Regressionsproblem der kleinsten Quadrate und eine andere weit verbreitete Methode namens la sol, die beide in Bezug auf einen Verlust über Trainingsdaten mit einem endlichen Summenformat geschrieben sind. Abschließend stellt der Redner fest, dass tiefe neuronale Netze ein weiteres Beispiel für dieses Finite-Summen-Problem mit n Trainingsdatenpunkten sind.

  • 00:10:00 In diesem Abschnitt geht der Referent darauf ein, wie Optimierungsverfahren notwendig sind, um Finite-Summen-Probleme zu lösen, die beim maschinellen Lernen und in der Statistik auftreten. Dies liegt daran, dass die meisten Probleme auf diesem Gebiet als Finite-Summen-Problem ausgedrückt werden können und spezialisierte Optimierungsverfahren erforderlich sind, um sie zu lösen. Der Referent stellt die Gradientenabstiegsmethode vor, weist jedoch darauf hin, dass die Berechnung des Gradienten eines einzelnen Punktes in einem großen Datensatz Stunden oder Tage dauern kann, was ein großer Nachteil ist. Der Redner bittet das Publikum um Vorschläge, um diesem Nachteil entgegenzuwirken, und einige vorgestellte Ideen umfassen die Verwendung eines stochastischen Gradientenabstiegs und das Abtasten einer Teilmenge des vollständigen Datensatzes.

  • 00:15:00 In diesem Abschnitt erörtert der Referent das Konzept des stochastischen Gradientenabstiegs, bei dem bei jeder Iteration einige Datenpunkte zufällig ausgewählt und der Gradient eines einzelnen Punkts berechnet werden, wodurch der Prozess viel schneller wird. Der Referent stellt jedoch fest, dass die Schlüsselfrage darin besteht, ob diese Idee mathematisch sinnvoll ist. Der stochastische Gradientenabstieg wurde erstmals 1951 von Robbins in Monroe vorgeschlagen und mit der Gradientenabstiegsmethode verglichen. Der Referent merkt an, dass der stochastische Gradientenabstieg empfindlicher auf Schrittgrößen reagiert und zeigt eine Simulation eines Spielzeugproblems, um zu veranschaulichen, wie die Linie schwankt. Das Verfahren scheint trotz Schwankungen immer noch dem Optimum entgegenzuschreiten.

  • 00:20:00 In diesem Abschnitt erörtert der Referent das Konzept des stochastischen Gradientenabstiegs (SGD), der den Gradienten des zufällig ausgewählten Datenpunkts multipliziert mit einem Alpha-Wert (Schrittweite) berechnet, um sich einer Lösung anzunähern. Der Prozess reagiert sehr empfindlich auf den Schrittgrößenparameter und ist empfindlicher als der Gradientenabstieg. Während er den Parameter variiert, beobachtet der Sprecher den Lösungsfortschritt und erklärt das typische Verhalten von SGD. Er erklärt, warum die Leute SGD lieben, da es am Anfang in großen Datensätzen schnelle Fortschritte macht und man schnelle und schmutzige Fortschritte erzielen kann, während man eine Überanpassung vermeidet. Wenn es jedoch der Lösung nahe kommt, schwankt es stärker, und es kann aufgrund chaotischen Verhaltens schwierig sein, das beste Optimum zu finden.

  • 00:25:00 In diesem Abschnitt erläutert der Referent, wie stochastische Gradientenverfahren in einem einfachen eindimensionalen Optimierungsproblem funktionieren, bei dem quadratische Funktionen verwendet werden. Ziel ist es, diese quadratischen Funktionen zu minimieren, und der Referent demonstriert, wie man die Steigungen einzelner Komponenten dazu nutzt. Sie erklären, dass die Methode am Anfang gut funktioniert, weil sie den vollen Gradienten nutzt, aber sobald sie sich dem Optimum nähert, kann alles passieren und es wird verwirrend. Der Referent zeigt auch, wie man die Lösung in geschlossener Form findet und wo das wahre Minimum innerhalb eines bestimmten Bereichs individueller Min- und Max-Werte zu finden ist.

  • 00:30:00 In diesem Abschnitt erläutert der Referent das Verhalten des stochastischen Gradientenabstiegs (SGD), wenn der Skalar X außerhalb des Verwirrungsbereichs liegt, was bedeutet, dass der Punkt sehr weit von der Lösung entfernt ist. In diesem weit entfernten Regime hat ein stochastischer Gradient einer Komponente genau das gleiche Vorzeichen wie der volle Gradient, dh die Richtung, in die man gehen muss, um die Verlustfunktion zu verringern. Der Redner verwendet dies, um zu erklären, warum SGD weit entfernt solide Fortschritte machen kann und wie es eine beeindruckende Anfangsgeschwindigkeit bieten kann, die Millionen von stochastischen Schritten in der Zeit ermöglicht, die für eine einzelne Iteration des Batch-Gradientenabstiegs erforderlich wäre. Sobald sich der stochastische Gradientenabstieg im Bereich der Verwirrung befindet, wird er bei der Optimierung weniger effektiv, aber beim maschinellen Lernen können die Schwankungen die Methode robuster und besser für die Verallgemeinerung machen. Die Referenten weisen darauf hin, dass dies eine Idee ist, die im maschinellen Lernen, in der theoretischen Informatik und in der Statistik weit verbreitet ist, wo die Randomisierung verwendet wird, um die Berechnung teurer Mengen zu beschleunigen.

  • 00:35:00 In diesem Abschnitt erörtert der Referent die Schlüsseleigenschaft des stochastischen Gradientenabstiegs (SGD). Die Hauptidee hinter SGD besteht darin, einen zufällig geschätzten Gradienten zu verwenden, um Berechnungen einzusparen. Die Schlüsseleigenschaft von SGD ist, dass die Schätzung des stochastischen Gradienten erwartungsgemäß eine unverzerrte Version des wahren Gradienten ist. Über diese Unvoreingenommenheit hinaus wird die Menge an Rauschen oder die Menge an Stochastik so gesteuert, dass die Varianz des stochastischen Gradienten verringert wird. Je kleiner die Varianz, desto besser ist Ihr stochastischer Gradient als Ersatz für den wahren Gradienten und desto schneller ist die Konvergenz.

  • 00:40:00 In diesem Abschnitt erörtert der Referent die stochastische Gradientenabstiegsmethode und ihr Verhalten bei konvexen und nicht-konvexen Problemen. Der Sprecher erwähnt auch zwei Varianten des Verfahrens, eine ohne Einschränkungen, bei der ein zufälliger Vektor ausgewählt wird, und die andere mit Einschränkungen, bei der ein Trainingsdatenpunkt zufällig mit oder ohne Ersatz ausgewählt wird. Der Referent erklärt, dass die Methode zwar schon seit 1951 existiert und in Deep-Learning-Toolkits weit verbreitet ist, es aber immer noch Lücken zwischen theoretischer und praktischer Anwendung gibt. Die Toolkits verwenden die Version ohne Ersatz, obwohl die Version, die wir zu analysieren wissen, die Version mit einheitlichem Zufall ist, was ein großes offenes Problem auf dem Gebiet des stochastischen Gradienten ist. Der Redner erwähnt auch die Mini-Batch-Idee, die eine Reihe von Punkten verwendet, um die Varianz zu reduzieren, was zu weniger Rauschen führt.

  • 00:45:00 In diesem Abschnitt des Videos diskutiert der Sprecher das Konzept der Mini-Batches und wie sie von Menschen genutzt werden, um eine billige Version der Parallelität im Deep-Learning-GPU-Stil-Training zu bieten. Je größer der Mini-Batch, desto mehr Dinge können parallel erledigt werden. Es gibt jedoch auch ein Rätsel darin, dass die Verwendung sehr großer Mini-Batches impliziert, dass der stochastische Gradient beginnt, eher wie ein Batch-Gradientenabstieg auszusehen, wodurch das Rauschen bis zu einem Punkt verringert wird, an dem der Verwirrungsbereich zu stark schrumpft. Dies ist schädlich für das maschinelle Lernen, da es zu einer Überanpassung des neuronalen Netzwerks führen kann, was die Vorhersage unsichtbarer Daten erschwert. Daher ist die Auswahl der richtigen Mini-Batch-Größe noch eine offene Frage im Optimierungsprozess der tiefen neuronalen Netze.

  • 00:50:00 In diesem Abschnitt erörtert der Referent die Herausforderungen im Zusammenhang mit der Optimierung des stochastischen Gradientenabstiegs (SGD), einschließlich der Bestimmung, welcher Mini-Batch verwendet werden soll, und wie stochastische Gradienten berechnet werden. Der Back-Propagation-Algorithmus wird als beliebte Methode zur Berechnung eines einzelnen stochastischen Gradienten eingeführt, und Toolkits für maschinelles Lernen können verschiedene Möglichkeiten zur Automatisierung der Berechnung eines Gradienten haben. Theoretische Herausforderungen beim Nachweis der Wirksamkeit von SGD werden diskutiert, einschließlich der Frage, warum SGD trotz ihrer angeblich suboptimalen Eigenschaften so gut für neuronale Netze funktioniert. Forscher versuchen derzeit, dieses Mysterium zu verstehen, indem sie eine Theorie der Verallgemeinerung entwickeln.
1...202122232425262728293031323334...74
Neuer Kommentar