2367 lines
230 KiB
Plaintext
2367 lines
230 KiB
Plaintext
Alexander Jung
|
||
Maschinelles Lernen
|
||
Die Grundlagen
|
||
|
||
Maschinelles Lernen
|
||
|
||
Modell
|
||
|
||
Hypothese
|
||
|
||
validieren/ anpassen
|
||
Verlust
|
||
|
||
Vorhersage treffen
|
||
|
||
Beobachtungen
|
||
|
||
Inferenz
|
||
|
||
Daten
|
||
Abb. 1 Maschinelles Lernen kombiniert drei Hauptkomponenten: Daten, Modell und Verlust. Methoden des maschinellen Lernens implementieren das wissenschaftliche Prinzip des „Versuchs und Irrtums“. Diese Methoden validieren und verfeinern kontinuierlich ein Modell basierend auf dem Verlust, der durch seine Vorhersagen über ein Phänomen entsteht, das Daten generiert.
|
||
|
||
Alexander Jung
|
||
Maschinelles Lernen
|
||
Die Grundlagen
|
||
|
||
Alexander Jung Department of Computer Science Aalto University Espoo, Finland
|
||
|
||
ISBN 978-981-99-7971-4
|
||
|
||
ISBN 978-981-99-7972-1 (eBook)
|
||
|
||
https://doi.org/10.1007/978-981-99-7972-1
|
||
|
||
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.
|
||
|
||
Dieses Buch ist eine Übersetzung des Originals in Englisch „Machine Learning“ von Jung, Alexander, publiziert durch Springer Nature Singapore Pte Ltd. im Jahr 2022. Die Übersetzung erfolgte mit Hilfe von künstlicher Intelligenz (maschinelle Übersetzung). Eine anschließende Überarbeitung im Satzbetrieb erfolgte vor allem in inhaltlicher Hinsicht, so dass sich das Buch stilistisch anders lesen wird als eine herkömmliche Übersetzung. Springer Nature arbeitet kontinuierlich an der Weiterentwicklung von Werkzeugen für die Produktion von Büchern und an den damit verbundenen Technologien zur Unterstützung der Autoren.
|
||
|
||
Übersetzung der englischen Ausgabe: „Machine Learning“ von Alexander Jung, © The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2022. Veröffentlicht durch Springer Nature Singapore. Alle Rechte vorbehalten.
|
||
|
||
© Der/die Herausgeber bzw. der/die Autor(en), exklusiv lizenziert an Springer Nature Singapore Pte Ltd. 2024
|
||
|
||
Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung des Verlags. Das gilt insbesondere für Vervielfältigungen, Bearbeitungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von allgemein beschreibenden Bezeichnungen, Marken, Unternehmensnamen etc. in diesem Werk bedeutet nicht, dass diese frei durch jedermann benutzt werden dürfen. Die Berechtigung zur Benutzung unterliegt, auch ohne gesonderten Hinweis hierzu, den Regeln des Markenrechts. Die Rechte des jeweiligen Zeicheninhabers sind zu beachten. Der Verlag, die Autoren und die Herausgeber gehen davon aus, dass die Angaben und Informationen in diesem Werk zum Zeitpunkt der Veröffentlichung vollständig und korrekt sind. Weder der Verlag noch die Autoren oder die Herausgeber übernehmen, ausdrücklich oder implizit, Gewähr für den Inhalt des Werkes, etwaige Fehler oder Äußerungen. Der Verlag bleibt im Hinblick auf geografische Zuordnungen und Gebietsbezeichnungen in veröffentlichten Karten und Institutionsadressen neutral.
|
||
|
||
Planung/Lektorat: Celine Chang Springer ist ein Imprint der eingetragenen Gesellschaft Springer Nature Singapore Pte Ltd. und ist ein Teil von Springer Nature. Die Anschrift der Gesellschaft ist: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721, Singapore
|
||
|
||
Das Papier dieses Produkts ist recyclebar.
|
||
|
||
Vorwort
|
||
Maschinelles Lernen (ML) beeinflusst unseren Alltag in mehreren Aspekten. Wir bitten regelmäßig ML-gestützte Smartphones, uns schöne Restaurants vorzuschlagen oder uns durch einen fremden Ort zu führen. ML-Methoden sind auch zu Standardwerkzeugen in vielen Bereichen der Wissenschaft und Technik geworden. ML-Anwendungen verändern das menschliche Leben in einem noch nie dagewesenen Tempo und Maßstab.
|
||
Dieses Buch stellt ML als Kombination von drei grundlegenden Komponenten dar: Daten, Modell und Verlust. ML-Methoden kombinieren diese drei Komponenten innerhalb rechnerisch effizienter Implementierungen des grundlegenden wissenschaftlichen Prinzips „Versuch und Irrtum“. Dieses Prinzip besteht aus der kontinuierlichen Anpassung einer Hypothese über ein Phänomen, das Daten generiert.
|
||
ML-Methoden verwenden eine Hypothesenkarte, um Vorhersagen einer interessierenden Größe (oder höheren Tatsache) zu berechnen, die als das Label eines Datenpunkts bezeichnet wird. Eine Hypothesenkarte liest niedrigstufige Eigenschaften (als Merkmale bezeichnet) eines Datenpunkts ein und liefert die Vorhersage für das Label dieses Datenpunkts. ML-Methoden wählen oder lernen eine Hypothesenkarte aus einer (typischerweise sehr) großen Menge von Kandidatenkarten. Wir bezeichnen diese Menge an Kandidatenkarten als den Hyporaum oder das Modell, das einer ML-Methode zugrunde liegt.
|
||
Die Anpassung oder Verbesserung der Hypothese basiert auf der Diskrepanz zwischen Vorhersagen und beobachteten Daten. ML-Methoden verwenden eine Verlustfunktion, um diese Diskrepanz zu quantifizieren.
|
||
Eine Vielzahl verschiedener ML-Methoden ergibt sich durch die Kombination unterschiedlicher Designentscheidungen für die Datenrepräsentation, das Modell und den Verlust. ML-Methoden unterscheiden sich auch stark in ihren praktischen Implementierungen, was ihre vereinheitlichenden Grundprinzipien verschleiern könnte.
|
||
Deep-Learning-Methoden verwenden Cloud-Computing-Frameworks, um große Modelle auf großen Datensätzen zu trainieren. Auf einer viel feineren Granularität für Daten und Berechnungen kann lineare (kleinste Quadrate)
|
||
V
|
||
|
||
VI
|
||
|
||
Vorwort
|
||
|
||
Regression auf kleinen eingebetteten Systemen implementiert werden. Dennoch verwenden Deep-Learning-Methoden und lineare Regression das gleiche Prinzip, ein Modell basierend auf der Diskrepanz zwischen Modellvorhersagen und tatsächlich beobachteten Daten iterativ zu aktualisieren.
|
||
Wir glauben, dass das Denken über ML als Kombinationen von drei Komponenten, die durch Daten, Modell und Verlustfunktion gegeben sind, hilft, das stetig wachsende Angebot an einsatzbereiten ML-Methoden zu navigieren. Unser Drei-Komponenten-Bild ermöglicht eine einheitliche Behandlung von MLTechniken, wie frühzeitigem Stoppen, datenschutzfreundlichem ML und xml, die auf den ersten Blick recht unterschiedlich erscheinen. Zum Beispiel ist der Regularisierungseffekt der Technik des frühzeitigen Stopps in gradientenbasierten Methoden auf die Schrumpfung des effektiven Hyporaums zurückzuführen. Datenschutzfreundliche ML-Methoden können durch besondere Auswahl der zur Charakterisierung von Datenpunkten verwendeten Merkmale erzielt werden (siehe Abschn. 9.5). Erklärbare ML-Methoden können durch besondere Auswahl des Hyporaums und der Verlustfunktion erzielt werden (siehe Kap. 10).
|
||
Um ML-Tools gut zu nutzen, ist es entscheidend, die zugrunde liegenden Prinzipien auf dem angemessenen Detailgrad zu verstehen. Es ist normalerweise nicht notwendig, die mathematischen Details fortgeschrittener Optimierungsmethoden zu verstehen, um Deep-Learning-Methoden erfolgreich anzuwenden. Auf einer niedrigeren Ebene hilft dieses Tutorial ML-Ingenieuren, geeignete Methoden für die jeweilige Anwendung auszuwählen. Das Buch bietet auch eine höhere Sicht auf die Implementierung von ML-Methoden, die normalerweise erforderlich ist, um ein Team von ML-Ingenieuren und Datenwissenschaftlern zu managen.
|
||
|
||
Espoo, Finland
|
||
|
||
Alexander Jung
|
||
|
||
Danksagungen
|
||
Dieses Buch entstand aus Vorlesungsnotizen, die für die Kurse CS-E3210 „Maschinelles Lernen: Grundlegende Prinzipien“, CS-E4800 „Künstliche Intelligenz“, CS-EJ3211 „Maschinelles Lernen mit Python“, CS-EJ3311 „Tiefes Lernen mit Python“ und CS-C3240 „Maschinelles Lernen“ vorbereitet wurden, die an der Aalto-Universität und im finnischen Universitätsnetzwerk fitech.io angeboten werden. Dieses Tutorial wird von praktischen Implementierungen von ML-Methoden in MATLAB und Python begleitet https://github.com/ alexjungaalto/.
|
||
Dieser Text hat von dem umfangreichen Feedback der Studenten profitiert, die an den vom Autor (mit-)geleiteten Kursen teilgenommen haben. Der Autor ist Shamsiiat Abdurakhmanova, Tomi Janhunen, Yu Tian, Natalia Vesselinova, Linli Zhang, Ekaterina Voskoboinik, Buse Atli, Stefan Mojsilovic dankbar, die die frühen Entwürfe dieses Tutorials sorgfältig überprüft haben. Einige der Abbildungen wurden mit Hilfe von Linli Zhang erstellt. Der Autor ist dankbar für das Feedback, das er von Jukka Suomela, Väinö Mehtola, Oleg Vlasovetc, Anni Niskanen, Georgios Karakasidis, Joni Pääkkö, Harri Wallenius und Satu Korhonen erhalten hat.
|
||
VII
|
||
|
||
Inhaltsverzeichnis
|
||
1 Einführung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Beziehung zu anderen Feldern. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Lineare Algebra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 Optimierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.3 Theoretische Informatik. . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.4 Informationstheorie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.5 Wahrscheinlichkeitstheorie und Statistik. . . . . . . . . . . . . 9 1.1.6 Künstliche Intelligenz . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Arten von maschinellem Lernen . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.1 Überwachtes Lernen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.2 Unüberwachtes Lernen . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2.3 Verstärkendes Lernen. . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3 Organisation dieses Buches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
|
||
2 Komponenten des ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1 Die Daten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 Merkmale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.2 Labels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.3 Streudiagramm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.1.4 Probabilistische Modelle für Daten. . . . . . . . . . . . . . . . . 32 2.2 Das Modell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.2.1 Parametrisierte Hypothesenräume. . . . . . . . . . . . . . . . . . 37 2.2.2 Die Größe eines Hypothesenraums. . . . . . . . . . . . . . . . . 40 2.3 Der Verlust. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.3.1 Verlustfunktionen für numerische Labels . . . . . . . . . . . . 44 2.3.2 Verlustfunktionen für kategoriale Labels. . . . . . . . . . . . . 45 2.3.3 Verlustfunktionen für ordinale Labelwerte . . . . . . . . . . . 49 2.3.4 Empirisches Risiko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.3.5 Bereuen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.3.6 Belohnungen als Teilrückmeldungen. . . . . . . . . . . . . . . . 53
|
||
IX
|
||
|
||
X
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
2.4 Die Teile zusammenfügen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.5 Übungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
|
||
3 Die Landschaft des ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.1 Lineare Regression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.2 Polynomiale Regression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.3 Regression der kleinsten absoluten Abweichung. . . . . . . . . . . . . . . 66 3.4 Das Lasso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.5 Gaußsche Basis Regression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.6 Logistische Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.7 Support-Vektor-Maschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.8 Bayes-Klassifikator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.9 Kernel-Methoden. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.10 Entscheidungsbäume. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.11 Tiefes Lernen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.12 Maximale Wahrscheinlichkeit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.13 Nächste-Nachbar-Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.14 Tiefes Verstärkungslernen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.15 LinUCB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3.16 Übungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
|
||
4 Empirische Risikominimierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.1 Die Grundidee der empirischen Risikominimierung. . . . . . . . . . . . 91 4.2 Rechnerische und statistische Aspekte der ERM. . . . . . . . . . . . . . . 93 4.3 ERM für Lineare Regression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.4 ERM für Entscheidungsbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.5 ERM für Bayes-Klassifikatoren. . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.6 Trainings- und Inferenzperioden. . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.7 Online-Lernen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.8 Übung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
|
||
5 Gradientenbasiertes Lernen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.1 Der GD-Schritt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.2 Schrittgröße wählen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.3 Wann aufhören?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.4 GD für lineare Regression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.5 GD für die logistische Regression. . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.6 Daten-Normalisierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.7 Stochastisches GD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.8 Übungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
XI
|
||
|
||
6 Modellvalidierung und -auswahl. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.1 Überanpassung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.2 Validierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.2.1 Die Größe des Validierungsdatensatzes. . . . . . . . . . . . . . 131 6.2.2 k-Fold Cross Validation. . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.2.3 Unaustarierte Daten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 6.3 Modellauswahl. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.4 Eine probabilistische Analyse der Generalisierung. . . . . . . . . . . . . 139 6.5 Der Bootstrap. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.6 Diagnose von ML. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 6.7 Übungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
|
||
7 Regularisierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 7.1 Strukturelle Risikominimierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 7.2 Robustheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 7.3 Daten Augmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 7.4 Statistische und rechnerische Aspekte der Regularisierung. . . . . . . 161 7.5 Semiüberwachtes Lernen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 7.6 Multitask-Lernen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 7.7 Transferlernen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 7.8 Übungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
|
||
8 Clustering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 8.1 Hartes Clustering mit k-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 8.2 Weiches Clustering mit Gaußschen Mischmodellen. . . . . . . . . . . . 181 8.3 Verbindlichkeitsbasiertes Clustering. . . . . . . . . . . . . . . . . . . . . . . . 187 8.4 Clustering als Vorverarbeitung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 8.5 Übungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
|
||
9 Merkmalslernen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 9.1 Grundprinzip der Dimensionsreduktion . . . . . . . . . . . . . . . . . . . . . 194 9.2 Hauptkomponentenanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 9.2.1 Kombination von PCA mit linearer Regression. . . . . . . . 199 9.2.2 Wie wählt man die Anzahl der PC aus?. . . . . . . . . . . . . . 199 9.2.3 Datenvisualisierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 9.2.4 Erweiterungen von PCA . . . . . . . . . . . . . . . . . . . . . . . . . 200 9.3 Merkmalslernen für nicht-numerische Daten . . . . . . . . . . . . . . . . . 202 9.4 Merkmalslernen für gelabelte Daten. . . . . . . . . . . . . . . . . . . . . . . . 204 9.5 Datenschutzfreundliches Merkmalslernen. . . . . . . . . . . . . . . . . . . . 206 9.6 Zufällige Projektionen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 9.7 Erhöhung der Dimensionalität. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 9.8 Übungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
|
||
|
||
XII
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
10 Transparentes und erklärbares ML . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 10.1 Eine Modellagnostische Methode. . . . . . . . . . . . . . . . . . . . . . . . . . 213 10.1.1 Probabilistisches Datenmodell für XML. . . . . . . . . . . . . 215 10.1.2 Berechnung optimaler Erklärungen. . . . . . . . . . . . . . . . . 216 10.2 Erklärbares empirisches Risikominimierung. . . . . . . . . . . . . . . . . . 219 10.3 Übungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
|
||
|
||
Glossar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
|
||
|
||
Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
|
||
|
||
Symbole
|
||
|
||
Mengen
|
||
a := b N R R+ {0,1} [0,1]
|
||
|
||
Diese Aussage definiert a als Kurzform für b. Die Menge der natürlichen Zahlen 1, 2, …. Die Menge der reellen Zahlen x [2]. Die Menge der nicht-negativen reellen Zahlen x ≥ 0. Die Menge bestehend aus zwei reellen Zahlen 0 und 1. Das geschlossene Intervall der reellen Zahlen x mit 0 ≤ x ≤ 1.
|
||
|
||
Matrizen und Vektoren
|
||
|
||
I Die Identitätsmatrix, deren Diagonaleinträge gleich eins sind
|
||
|
||
und jeder Eintrag außerhalb der Diagonale gleich null ist. Rn Die Menge der Vektoren, die aus n reellen Einträgen bestehen. x = (x1, . . . , xn)T Ein Vektor der Länge n. Der jte Eintrag des Vektors wird als xj
|
||
bezeichnet.
|
||
x 2 Die euklidische (oder „ℓ2“) Norm des Vektors
|
||
|
||
x = (x1, . . . , xn)T ist gegeben als �x�2 :=
|
||
|
||
nj=1 xj2 .
|
||
|
||
x Eine Norm des Vektors x [1]. Sofern nicht anders angegeben,
|
||
meinen wir die euklidische Norm x 2. xT Die Transposition eines Vektors x, der als einzelne Spalten-
|
||
|
||
matrix betrachtet wird. Die Transposition kann als einzelne
|
||
|
||
Zeilenmatrix interpretiert werden (x1, . . . , xn). AT Die Transposition einer Matrix A. Eine quadratische Matrix
|
||
|
||
wird als symmetrisch bezeichnet, wenn A = AT
|
||
|
||
Sn+
|
||
|
||
Die Menge aller (psd) n × n Matrizen.
|
||
|
||
XIII
|
||
|
||
XIV
|
||
Maschinelles Lernen
|
||
|
||
Symbole
|
||
|
||
i Ein generischer Index i = 1,2, . . . , wird verwendet, um die
|
||
|
||
Datenpunkte innerhalb eines Datensatzes zu nummerieren.
|
||
|
||
m Die Anzahl der Datenpunkte in (die Größe von) einem Daten-
|
||
|
||
satz.
|
||
|
||
n Die Anzahl der einzelnen Eigenschaften, die zur
|
||
|
||
Charakterisierung eines Datenpunkts verwendet werden.
|
||
|
||
xj
|
||
|
||
Das jte individuelle Merkmal eines Datenpunkts.
|
||
|
||
x Der Merkmalsvektor x = (x1, . . . , xn)T eines Datenpunkts,
|
||
|
||
dessen Einträge die einzelnen Merkmale des Datenpunkts
|
||
|
||
sind.
|
||
|
||
z Neben dem Symbol x verwenden wir manchmal ein anderes
|
||
|
||
Symbol, um einen Vektor zu bezeichnen, dessen Einträge
|
||
|
||
Merkmale eines Datenpunkts sind. Wir benötigen zwei ver-
|
||
|
||
schiedene Symbole, um Merkmalsvektoren für die Diskussion
|
||
|
||
von Merkmalslernmethoden in Kap. 9 zu bezeichnen.
|
||
|
||
x(i) Der Merkmalsvektor des iten Datenpunkts innerhalb eines
|
||
|
||
Datensatzes. xj(i) Das jte Merkmal des iten Datenpunkts innerhalb eines Daten-
|
||
satzes.
|
||
|
||
y
|
||
|
||
Die Bezeichnung (Menge von Interesse) eines Datenpunkts.
|
||
|
||
y(i)
|
||
|
||
Die Bezeichnung des iten Datenpunkts.
|
||
|
||
(x(i), y(i)) Die Merkmale und das Etikett des iten Datenpunkts innerhalb
|
||
|
||
eines Datensatzes.
|
||
|
||
h(·) Eine Hypothesenkarte, die die Merkmale x eines Datenpunkts
|
||
|
||
einliest und das vorhergesagte Label y = h(x) ausgibt.
|
||
|
||
xj Das j-te Merkmal eines Datenpunkts. Das erste Merkmal
|
||
|
||
eines gegebenen Datenpunkts wird als x1 bezeichnet, das
|
||
|
||
zweite Merkmal x2 und so weiter.
|
||
|
||
L((x, y), h) Der Verlust, der durch die Vorhersage des Labels y eines
|
||
|
||
Datenpunkts mit dem Merkmalsvektor x unter Verwendung
|
||
|
||
des Wertes y = h(x) entsteht, der durch die Auswertung der
|
||
|
||
Hypothese h ∈ H am Merkmalsvektor x erzielt wird.
|
||
|
||
Ev Der Validierungsfehler einer Hypothese, der als durchschnitt-
|
||
|
||
licher Verlust berechnet wird, der auf einem Validierungsset
|
||
|
||
ermittelt wurde.
|
||
|
||
L(h|D) Der empirische oder durchschnittliche Verlust, der durch die
|
||
|
||
Vorhersagen der Hypothese h für die Datenpunkte im Daten-
|
||
|
||
satz D entsteht.
|
||
|
||
Symbole
|
||
|
||
XV
|
||
|
||
Et Der Trainer einer Hypothese h, der der durchschnittliche Verlust ist, der von h auf beschrifteten Datenpunkten verursacht wird, die einen Trainingsdatensatz bilden.
|
||
t Ein diskreter Zeitindex t = 0,1, . . . wird verwendet, um eine Sequenz von zeitlichen Ereignissen (Zeitpunkten) zu nummerieren.
|
||
t Ein generischer Index, der verwendet wird, um eine endliche Menge von Lernaufgaben innerhalb eines Multi-Task-Lernproblems zu nummerieren (siehe Abschn. 7.6).
|
||
Ein Regularisierungsparameter, der verwendet wird, um den Regularisierungsterm zu skalieren, der zum empirischen Risiko in der strukturellen Risikominimierung (SRM) hinzugefügt wird.
|
||
j(Q) Der jte Eigenwert (sortiert entweder aufsteigend oder absteigend) einer psd-Matrix Q. Wir verwenden auch die Abkürzung j, wenn die entsprechende Matrix aus dem Kontext klar ist.
|
||
f (·) Die Aktivierungsfunktion, die von einem künstlichen Neuron innerhalb eines künstlichen neuronalen Netzwerks (ANN) verwendet wird.
|
||
|
||
Literatur
|
||
1. G.H. Golub, C.F. Van Loan. Matrix Computations. (Johns Hopkins University Press, Baltimore, MD, 3. Aufl., 1996)
|
||
2. W. Rudin. Real and Complex Analysis. (McGraw-Hill, New York, 3. Aufl., 1987)
|
||
|
||
Kapitel 1
|
||
Einführung
|
||
|
||
Stellen Sie sich vor, Sie wachen an einem Wintermorgen in Finnland auf und schauen aus dem Fenster (siehe Abb. 1.1). Es scheint ein schöner sonniger Tag zu werden, der ideal für einen Skiausflug ist. Um die richtige Ausrüstung (Kleidung, Wachs) auszuwählen, ist es wichtig, eine Vorstellung von der maximalen Tagestemperatur zu haben, die normalerweise am frühen Nachmittag erreicht wird. Wenn wir eine maximale Tagestemperatur von etwa plus 5° erwarten, ziehen wir vielleicht nicht die extra warme Jacke an, sondern nehmen nur ein zusätzliches Hemd zum Wechseln mit.
|
||
Wir können ML verwenden, um einen Prädiktor für die maximale Tagestemperatur für den spezifischen Tag zu lernen, der in Abb. 1.1 dargestellt ist. Die Vorhersage soll ausschließlich auf der am Morgen dieses Tages beobachteten Mindesttemperatur basieren. ML-Methoden können auf datengetriebene Weise einen Prädiktor lernen, indem sie historische Wetterbeobachtungen verwenden, die vom Finnischen Meteorologischen Institut bereitgestellt werden. Wir können die Aufzeichnungen der minimalen und maximalen Tagestemperatur für die jüngsten Tage herunterladen und das resultierende Datenset mit
|
||
|
||
D = z(1), . . . , z(m) .
|
||
|
||
(1.1)
|
||
|
||
jedem Datenpunkt z(i) = x(i), y(i) , für i = 1, . . . , m, stellt einen früheren Tag dar, für den die minimale und maximale Tagestemperatur x(i) und y(i) aufgezeichnet wurde. Wir stellen die Daten (1.1) in Abb. 1.2 dar. Jeder Punkt in Abb. 1.2 stellt einen spezifischen Tag mit Mindesttemperatur x und maximaler Temperatur y dar.
|
||
ML-Methoden lernen eine Hypothese h(x), die die Mindesttemperatur x einliest und eine Vorhersage (Prognose oder Annäherung) yˆ = h(x) für die maximale Tagestemperatur y liefert. Jede praktische ML-Methode verwendet einen bestimmten Hypothesenraum, aus dem die Hypothese h ausgewählt wird. Dieser Hypothesenraum von Kandidaten für die Hypothesenkarte ist eine wichtige Designentscheidung und könnte auf Domänenwissen basieren.
|
||
|
||
© Der/die Autor(en), exklusiv lizenziert an Springer Nature Singapore Pte Ltd. 2024
|
||
|
||
1
|
||
|
||
A. Jung, Maschinelles Lernen, https://doi.org/10.1007/978-981-99-7972-1_1
|
||
|
||
2
|
||
Abb. 1.1 Blick aus dem Fenster während eines Wintermorgens in Finnland
|
||
|
||
1 Einführung
|
||
|
||
Abb. 1.2 Jeder Punkt stellt einen spezifischen Tag dar, der durch seine minimale Tagestemperatur x als Merkmal und seine maximale Tagestemperatur y als Label gekennzeichnet ist. Diese Temperaturen werden an einer Wetterstation des Finnischen Meteorologischen Instituts gemessen
|
||
|
||
Im Folgenden illustrieren wir, wie man Domänenwissen verwendet, um eine Wahl für den Hypothesenraum zu motivieren. Nehmen wir an, dass die Mindestund Maximaltemperatur eines beliebigen Tages ungefähr über
|
||
|
||
y ≈ w1x + w0 mit einigen Gewichten w1 ∈ R+, w0 ∈ R.
|
||
|
||
(1.2)
|
||
|
||
Die Annahme (1.2) spiegelt die Intuition (Domänenwissen) wider, dass die maximale Tagestemperatur y an Tagen mit einer höheren Mindesttagestemperatur x höher sein sollte. Die Annahme (1.2) enthält zwei Gewichte und w0. Diese Gewichte sind Abstimmungs Parameter, die eine gewisse Flexibilität in unserer Annahme ermöglichen. Wir verlangen, dass das Gewicht w1 nicht negativ ist, lassen diese Gewichte aber ansonsten vorerst unbestimmt. Hauptthema dieses Buches sind ML-Methoden, die verwendet werden können, um geeignete Werte für die Gewichte w1 und w0 auf datengetriebene Weise zu erlernen.
|
||
Bevor wir im Detail erläutern, wie ML verwendet werden kann, um gute Werte für die Gewichte w0 in w1 in (1.2) zu finden oder zu lernen, lassen Sie uns diese interpretieren. Das Gewicht w1 in (1.2) kann als die relative Erhöhung der maximalen Tagestemperatur bei einer erhöhten minimalen Tagestemperatur interpretiert werden. Betrachten Sie einen früheren Tag mit einer aufgezeichneten
|
||
|
||
1 Einführung
|
||
|
||
3
|
||
|
||
maximalen Tagestemperatur von 10° und einer minimalen Tagestemperatur von 0°. Die Annahme (1.2) bedeutet dann, dass die maximale Tagestemperatur für einen anderen Tag mit einer minimalen Tagestemperatur von +1 Grad 10 + w1 Grad betragen würde. Das zweite Gewicht w0 in unserer Annahme (1.2) kann als die maximale Tagestemperatur interpretiert werden, die wir für einen Tag mit einer minimalen Tagestemperatur von 0 erwarten.
|
||
Angesichts der Annahme (1.2) scheint es vernünftig, die ML-Methode darauf zu beschränken, nur lineare Abbildungen
|
||
|
||
h(x) := w1x + w0 mit einigen Gewichten w1 ∈ R+, w0 ∈ R.
|
||
|
||
(1.3)
|
||
|
||
zu berücksichtigen. Da wir w1 ≥ 0 benötigen, ist die Abb. (1.3) monoton steigend in Bezug auf das Argument x. Daher wird die Vorhersage h(x) für die maximale Tagestemperatur mit einer höheren minimalen Tagestemperatur x höher.
|
||
Der Ausdruck (1.3) definiert eine ganze Menge von Hypothesenabbildungen. Jede einzelne Abbildung entspricht einer bestimmten Wahl für w1 ≥ 0 und w0. Wir bezeichnen eine solche Menge von potenziellen Vorhersageabbildungen als das Modell oder den Hypothesenraum, der von einer ML-Methode verwendet wird.
|
||
Wir sagen, dass die Karte (1.3) durch den Gewichtsvektor w = w1, w0 parametrisiert ist und wir dies durch Schreiben von h(w) anzeigen. Für einen gegebenen Gewichtsvektor w = w1, w0 T erhalten wir die Karte h(w)(x) = w1x + w0. Abb. 1.3 zeigt drei Karten h(w) die für drei verschiedene Gewichtsauswahlen w erhalten wurden.
|
||
ML wäre trivial, wenn es nur eine einzige Hypothese gäbe. Eine einzige Hypothese zu haben bedeutet, dass es nicht notwendig ist, verschiedene Hypothesen auszuprobieren, um die beste zu finden. Um ML zu ermöglichen, müssen wir zwischen einem ganzen Raum von verschiedenen Hypothesen wählen. MLMethoden sind rechenintensive Methoden, um (zu lernen) eine gute Hypothese aus (typischerweise sehr großen) Hypothesenräumen zu wählen. Der durch die Karten
|
||
|
||
Merkmal
|
||
Abb. 1.3 Drei Hypothesenkarten der Form (1.3)
|
||
|
||
4
|
||
|
||
1 Einführung
|
||
|
||
(1.3) für verschiedene Gewichte konstituierte Hypothesenraum ist unzählig unendlich.
|
||
Um eine gute Hypothese aus der unendlichen Menge (1.3) zu finden oder zu lernen, müssen wir irgendwie die Qualität einer bestimmten Hypothesenkarte bewerten. ML-Methoden verwenden dazu eine Verlustfunktion. Eine Verlustfunktion wird verwendet, um den Unterschied zwischen den tatsächlichen Daten und den Vorhersagen, die aus einer Hypothesenkarte erhalten wurden (siehe Abb. 1.4), zu quantifizieren. Ein weit verbreitetes Beispiel für eine Verlustfunktion ist der quadratische Fehlerverlust (y − h(x))2. Mit dieser Verlustfunktion lernen ML-Methoden eine Hypothesenkarte aus dem Modell (1.3) durch Abstimmung von w1, w0 um den durchschnittlichen Verlust zu minimieren
|
||
|
||
m
|
||
|
||
(1/m)
|
||
|
||
y(i) − h x(i) 2.
|
||
|
||
i=1
|
||
|
||
Die oben genannte Wettervorhersage ist prototypisch für viele andere MLAnwendungen. Abb. 1.4 veranschaulicht den typischen Ablauf einer ML-Methode. Ausgehend von einer anfänglichen Vermutung verbessern ML-Methoden ihre aktuelle Hypothese wiederholt auf der Grundlage von (neuen) beobachteten Daten.
|
||
Mit der aktuellen Hypothese machen ML-Methoden Vorhersagen oder Prognosen über zukünftige Beobachtungen. Die Diskrepanz zwischen den Vorhersagen und den tatsächlichen Beobachtungen, gemessen mit einer Verlustfunktion, wird verwendet, um die Hypothese zu verbessern. Das Lernen erfolgt während der Verbesserung der aktuellen Hypothese auf der Grundlage der Diskrepanz zwischen ihren Vorhersagen und den tatsächlichen Beobachtungen.
|
||
|
||
Abb. 1.4 Jeder Punkt repräsentiert einen spezifischen Tag, der durch seine minimale Tagestemperatur x und seine maximale Tagestemperatur y gekennzeichnet ist. Wir zeigen auch eine gerade Linie, die eine lineare Vorhersagekarte darstellt. Ein Hauptprinzip von ML-Methoden besteht darin, eine Vorhersagekarte (oder Hypothese) mit minimaler Diskrepanz zwischen Vorhersagekarte und Datenpunkten zu lernen. Verschiedene ML-Methoden verwenden verschiedene Arten von Vorhersagekarten (Hypothesenraum) und Verlustfunktionen, um die Diskrepanz zwischen Hypothese und tatsächlichen Datenpunkten zu quantifizieren
|
||
|
||
1.1 Beziehung zu anderen Feldern
|
||
|
||
5
|
||
|
||
ML-Methoden müssen mit einer anfänglichen Vermutung oder Wahl für eine gute Hypothese beginnen. Diese anfängliche Vermutung kann auf einigen Vorwissen oder Fachkenntnissen basieren [1]. Während die anfängliche Vermutung für eine Hypothese in einigen ML-Methoden nicht explizit gemacht werden könnte, muss jede Methode eine solche anfängliche Vermutung verwenden. In unserer oben diskutierten Wettervorhersageanwendung haben wir das lineare Modell (1.2) als die anfängliche Hypothese verwendet.
|
||
|
||
1.1 Beziehung zu anderen Feldern
|
||
ML baut auf Konzepten aus mehreren anderen wissenschaftlichen Feldern auf. Umgekehrt bietet ML wichtige Werkzeuge für viele andere wissenschaftliche Felder.
|
||
|
||
1.1.1 Lineare Algebra
|
||
Moderne ML-Methoden sind rechenintensive Methoden zur Anpassung hochdimensionaler Modelle an große Datenmengen. Die Modelle, die den modernsten ML-Methoden zugrunde liegen, können Milliarden von einstellbaren oder lernbaren Parametern enthalten. Um ML-Methoden rechenintensiv zu machen, müssen wir geeignete Darstellungen für Daten und Modelle verwenden.
|
||
Vielleicht ist die am weitesten verbreitete mathematische Struktur zur Darstellung von Daten der euklidische Raum Rn mit einer bestimmten Dimension n ∈ N [2]. Die reiche algebraische und geometrische Struktur von Rn ermöglicht es uns, ML-Algorithmen zu entwerfen, die riesige Datenmengen verarbeiten können, um ein Modell (Parameter) schnell zu aktualisieren. Abb. 1.5 zeigt den euklidischen Raum Rn für n = 2, der zur Erstellung von Streudiagrammen verwendet wird.
|
||
Das Streudiagramm in Abb. 1.2 stellt Datenpunkte (die einzelne Tage repräsentieren) als Vektoren im euklidischen Raum R2 dar. Für einen gegebenen Datenpunkt erhalten wir seinen zugehörigen Vektor z = (x, y)T in R2, indem wir die minimale Tagestemperatur x und die maximale Tagestemperatur y in den Vektor z der Länge zwei stapeln.
|
||
Wir können den euklidischen Raum Rn nicht nur zur Darstellung von Datenpunkten, sondern auch zur Darstellung von Modellen für diese Datenpunkte verwenden. Eine solche Klasse von Modellen wird durch lineare Abbildungen auf Rn erhalten. Abb. 1.3 zeigt einige Beispiele für solche linearen Abbildungen. Wir können dann die geometrische Struktur von Rn, definiert durch die euklidische Norm, zur Suche nach dem besten Modell verwenden. Als Beispiel könnten wir nach dem linearen Modell suchen, das durch eine Gerade repräsentiert wird, so dass der durchschnittliche (euklidische) Abstand zu den Datenpunkten in Abb. 1.2 so klein wie
|
||
|
||
6
|
||
Abb. 1.5 Der euklidische Raum R2 besteht aus allen Vektoren (oder Punkten) z = z1, z2 T (mit z1, z2 ∈ R) zusammen mit dem inneren Produkt zT z′ = z1z1′ + z2z2′
|
||
|
||
1 Einführung
|
||
|
||
möglich ist (siehe Abb. 1.4). Die Eigenschaften linearer Strukturen werden innerhalb der linearen Algebra [3] untersucht. Einige wichtige ML-Methoden, wie der lineare Klassifikator (siehe Abschn. 3.1) oder die Hauptkomponentenanalyse (siehe Abschn. 9.2) sind direkte Anwendungen von Methoden aus der linearen Algebra.
|
||
1.1.2 Optimierung
|
||
Ein Hauptgestaltungsprinzip für ML-Methoden ist die Formulierung von MLProblemen als Optimierung Probleme [4]. Das oben genannte Wettervorhersageproblem kann als das Problem der Optimierung (Minimierung) des Vorhersagefehlers für die maximale Tagestemperatur formuliert werden. Viele ML-Methoden werden durch direkte Anwendungen von Optimierungsmethoden auf das aus einem MLProblem (oder Anwendung) entstehende Optimierungsproblem erhalten.
|
||
Die statistischen und rechnerischen Eigenschaften solcher ML-Methoden können mit Werkzeugen aus der Theorie der Optimierung untersucht werden. Was die Optimierungsprobleme in ML von „einfachen“ Optimierungsproblemen (siehe Abb. 1.6a) unterscheidet, ist, dass wir selten perfekten Zugang zur zu minimierenden Zielfunktion haben. ML-Methoden lernen eine Hypothese, indem sie eine verrauschte oder sogar unvollständige Version (siehe Abb. 1.6b) des tatsächlichen Ziels minimieren, das mit einer Erwartung über eine unbekannte Wahrscheinlichkeitsverteilung definiert ist. Kap. 4 diskutiert Methoden, die auf der Schätzung der Zielfunktion durch empirische Durchschnitte basieren, die über eine Menge von Datenpunkten (die ein Trainingsset bilden) berechnet werden.
|
||
|
||
1.1 Beziehung zu anderen Feldern
|
||
Zielsetzung
|
||
|
||
7
|
||
Verlust
|
||
|
||
Optimierungs variable
|
||
|
||
Hypothese
|
||
|
||
Abb. 1.6 a Ein einfaches Optimierungsproblem besteht darin, die Werte einer Optimierungsvariable zu finden, die zum minimalen Zielwert führen. b ML-Methoden lernen (finden) eine Hypothese, indem sie einen Verlust minimieren, der eine verrauschte und unvollständige Version des tatsächlichen Ziels ist
|
||
1.1.3 Theoretische Informatik
|
||
Praktische ML-Methoden bilden eine spezifische Unterklasse von Rechensystemen. Tatsächlich wenden ML-Methoden eine Sequenz von Rechenoperationen auf Eingabedaten an. Das Ergebnis dieser Rechenoperationen sind die Vorhersagen, die dem Benutzer der ML-Methode geliefert werden. Die Interpretation von ML als Rechensysteme ermöglicht die Verwendung von Werkzeugen aus der theoretischen Informatik zur Untersuchung der Machbarkeit und der intrinsischen Schwierigkeit von ML-Problemen. Selbst wenn ein ML-Problem im theoretischen Sinne gelöst werden kann, muss jede praktische ML-Methode in die verfügbare Recheninfrastruktur passen [5, 6].
|
||
Die verfügbaren Rechenressourcen, wie Prozessorzeit, Speicher und Kommunikationsbandbreite, können zwischen verschiedenen Infrastrukturen erheblich variieren. Ein Beispiel für eine solche Recheninfrastruktur ist ein einzelner Desktop-Computer. Ein weiteres Beispiel für eine Recheninfrastruktur ist ein Cloud-Computing-Dienst, der Daten und Berechnungen über große Netzwerke von physischen Computern verteilt [7].
|
||
Der Schwerpunkt dieses Buches liegt auf ML-Methoden, die als numerische Optimierungsalgorithmen verstanden werden können (siehe Kap. 4 und 5). Die meisten dieser ML-Methoden erfordern (eine große Anzahl von) Matrixoperationen wie Matrixmultiplikation oder Matrixinversion [8]. Numerische lineare Algebra bietet eine umfangreiche algorithmische Toolbox für die Gestaltung solcher ML-Methoden [3, 9]. Der jüngste Erfolg von ML-Methoden in mehreren Anwendungsbereichen könnte auf ihren effizienten Einsatz von Matrizen zur Darstellung von Daten und Modellen zurückzuführen sein. Durch die Verwendung dieser Darstellung können wir die resultierenden ML-Methoden mit hoch effizienten Hard- und Softwareimplementierungen für numerische lineare Algebra implementieren [10].
|
||
|
||
8
|
||
1.1.4 Informationstheorie
|
||
|
||
1 Einführung
|
||
|
||
Die Informationstheorie untersucht das Problem der Kommunikation über verrauschte Kanäle [11–14]. Abb. 1.7 zeigt das einfachste Kommunikationsproblem, das aus einer Informationsquelle besteht, die eine Nachricht m über einen unvollkommenen (oder verrauschten) Kanal an einen Empfänger senden möchte. Der Empfänger versucht, die ursprüngliche Nachricht ausschließlich auf der Grundlage des verrauschten Kanalausgangs zu rekonstruieren (oder zu lernen). Zwei Hauptziele der Informationstheorie sind (i) die Charakterisierung von Bedingungen, die eine zuverlässige, d. h. nahezu fehlerfreie, Kommunikation ermöglichen und (ii) die Gestaltung effizienter Sender- (Codierung und Modulation) und Empfänger- (Demodulation und Dekodierung) Methoden.
|
||
Es stellt sich heraus, dass viele Konzepte aus der Informationstheorie sehr nützlich für die Analyse und Gestaltung von ML-Methoden sind. Als Beispiel diskutiert Kap. 10 die Anwendung von informationstheoretischen Konzepten auf die Gestaltung von erklärlichen Maschinenlernmethoden. Auf einer grundlegenderen Ebene können wir zwei zentrale Kommunikationsprobleme identifizieren, die
|
||
|
||
Informations quelle
|
||
|
||
Sender
|
||
|
||
Störkanal
|
||
|
||
Empfänger
|
||
|
||
Daten quelle
|
||
|
||
Kanal
|
||
|
||
Kanal
|
||
|
||
Abb. 1.7 a Ein grundlegendes Kommunikationssystem beinhaltet eine Informationsquelle, die eine Nachricht m aussendet. Die Nachricht wird von einem Sender verarbeitet und durch einen verrauschten Kanal gesendet. Der Empfänger versucht, die ursprüngliche Nachricht m durch Berechnung der decodierten Nachricht mˆ wiederherzustellen. b Der Inferenzschritt von ML (siehe Abb. 1.4) entspricht einem Kommunikationsproblem mit einer Informationsquelle, die einen Datenpunkt mit Merkmalen x und Label y aussendet. Die ML-Methode erhält die Merkmale x und versucht, das wahre Label y wiederherzustellen, indem sie das vorhergesagte Label yˆ berechnet. c Der Lern- oder Anpassungsschritt von ML (siehe Abb.1.4) löst ein Kommunikationsproblem mit einer Quelle, die eine wahre (aber unbekannte) Hypothese h∗ als Nachricht auswählt. Die Nachricht wird durch einen abstrakten Kanal gesendet, der eine Menge D von gelabelten Datenpunkten ausgibt, die als Trainingsset von einer ML-Methode verwendet werden. Die ML-Methode versucht, die wahre Hypothese zu decodieren, was zur gelernten Hypothese hˆ führt
|
||
|
||
1.1 Beziehung zu anderen Feldern
|
||
|
||
9
|
||
|
||
innerhalb von ML auftreten. Diese Kommunikationsprobleme entsprechen jeweils dem Inferenz- (Vorhersage treffen) und dem Lernschritt (Anpassung oder Verbesserung der aktuellen Hypothese) einer ML-Methode (siehe Abb. 1.4).
|
||
Wir können den Inferenzschritt von ML als das Problem interpretieren, das wahre Label eines Datenpunkts zu decodieren, für den wir nur seine Merkmale kennen. Dieses Kommunikationsproblem wird in Abb. 1.7b dargestellt. Hier ist die zu kommunizierende Nachricht das wahre Label eines zufälligen Datenpunkts. Dieser Datenpunkt wird über einen Kanal „kommuniziert“, der nur seine Merkmale durchlässt. Der Inferenzschritt innerhalb einer ML-Methode versucht dann, die ursprüngliche Nachricht (wahres Label) aus dem Kanalausgang (Merkmale) zu decodieren, was zum vorhergesagten Label führt. Eine jüngere Forschungsrichtung hat dieses Kommunikationsproblem genutzt, um DeepLearning-Methoden zu untersuchen [11].
|
||
Ein zweites Kernkommunikationsproblem von ML entspricht dem Problem des Lernens (oder Anpassens) einer Hypothese (siehe Abb. 1.7c). In diesem Problem wählt die Quelle eine „wahre“ Hypothese als Nachricht aus. Diese Nachricht wird dann an einen abstrakten Kanal übermittelt, der den Daten-Generierungsprozess modelliert. Die Ausgabe dieses abstrakten Kanals sind Datenpunkte in einem Trainingsset D (siehe Kap. 4). Der Lernschritt einer ML-Methode, wie zum Beispiel die empirische Risikominimierung von Kap. 4, besteht dann in der Dekodierung der Nachricht (wahre Hypothese) basierend auf der Kanalausgabe (Trainingsset). Es gibt eine bedeutende Forschungsrichtung, die das Kommunikationsproblem in Abb. 1.7c verwendet, um die grundlegenden Grenzen von ML-Problemen und -Methoden zu charakterisieren, wie zum Beispiel die minimale erforderliche Anzahl von Trainingsdatenpunkten, die das Lernen ermöglichen [15–19].
|
||
Die Relevanz von informationstheoretischen Konzepten und Methoden für ML wird durch den jüngsten Trend zu verteiltem oder föderiertem ML [20–23] verstärkt. Wir können föderierte Lernanwendungen (FL) als eine spezifische Art von Netzwerkkommunikationsproblemen interpretieren [14]. Insbesondere können wir Netzwerkkodierungstechniken auf das Design und die Analyse von föderierten Lernmethoden (FL) anwenden [14].
|
||
|
||
1.1.5 Wahrscheinlichkeitstheorie und Statistik
|
||
Betrachten Sie die Datenpunkte z(1), . . . , dargestellt in Abb. 1.2. Jeder Datenpunkt repräsentiert einen vorherigen Tag, der durch seine minimale und maximale Tagestemperatur gekennzeichnet ist, gemessen an einer bestimmten Wetterbeobachtungsstation des Finnischen Meteorologischen Instituts. Es könnte nützlich sein, diese Datenpunkte als Realisierungen von i.i.d. Zufallsvariablen mit gemeinsamer (aber unbekannter) Wahrscheinlichkeitsverteilung p(z) zu interpretieren. Abb. 1.8 erweitert das Streudiagramm in Abb. 1.2 durch Hinzufügen einer Konturlinie der zugrunde liegenden Wahrscheinlichkeitsverteilung p(z)
|
||
|
||
10
|
||
|
||
1 Einführung
|
||
|
||
Abb. 1.8 Jeder Punkt repräsentiert einen Datenpunkt z = x, y , der durch ein numerisches Merkmal x und ein numerisches Label y gekennzeichnet ist. Wir zeigen auch eine Konturlinie einer Wahrscheinlichkeitsverteilung p(z), die verwendet werden könnte, um Datenpunkte als Realisierungen von i.i.d. Zufallsvariablen mit gemeinsamer Wahrscheinlichkeitsverteilung p(z) zu interpretieren
|
||
[24]. Wahrscheinlichkeit bietet prinzipielle Methoden zur Schätzung der Wahrscheinlichkeitsverteilung aus einer Menge von Datenpunkten (siehe Abschn. 3.12). Gegeben (eine Schätzung der) Wahrscheinlichkeitsverteilung p(z), können wir Schätzungen für das Label eines Datenpunkts basierend auf seinen Merkmalen berechnen.
|
||
Eine Wahrscheinlichkeitsverteilung p(z) für einen zufällig gezogenen Datenpunkt z = (x, y)T, ermöglicht es uns nicht nur, eine einzelne Vorhersage (Punktschätzung) yˆ des Labels y zu berechnen, sondern eine gesamte Wahrscheinlichkeitsverteilung q(yˆ) über alle möglichen Vorhersagewerte yˆ.
|
||
Die Verteilung q(yˆ) repräsentiert, für jeden Wert yˆ, die Wahrscheinlichkeit oder wie wahrscheinlich es ist, dass dies der wahre Labelwert des Datenpunkts ist. Nach ihrer Definition ist diese Verteilung q(yˆ) genau die bedingte Wahrscheinlichkeitsverteilung p(y|x) des Labelwerts y, gegeben den Merkmalswert x eines zufällig gezogenen Datenpunkts z = (x, y)T ∼ p(z).
|
||
Die Kenntnis (einer genauen Schätzung) der Wahrscheinlichkeitsverteilung p(z), die den in einer ML-Anwendung generierten Datenpunkten zugrunde liegt, ermöglicht es uns nicht nur, Vorhersagen von Labels zu berechnen. Wir können auch p(z) verwenden, um den verfügbaren Datensatz zu erweitern, indem wir zufällig neue Datenpunkte aus p(z) ziehen (siehe Abschn. 7.3). Eine kürzlich populär gewordene Klasse von ML-Methoden, die probabilistische Modelle zur Erzeugung synthetischer Daten verwenden, ist bekannt als generative adversarial networks [25].
|
||
|
||
1.1 Beziehung zu anderen Feldern
|
||
|
||
11
|
||
|
||
1.1.6 Künstliche Intelligenz
|
||
|
||
ML-Theorie und -Methoden sind entscheidend für die Analyse und das Design von künstlicher Intelligenz [26]. Ein künstliches Intelligenzsystem, typischerweise als Agent bezeichnet, interagiert mit seiner Umgebung, indem es (zwischen verschiedenen) Aktionen ausführt. Diese Aktionen beeinflussen die Umgebung sowie den Zustand des künstlichen Intelligenz-Agenten. Das Verhalten eines künstlichen Intelligenzsystems wird bestimmt durch die Art und Weise, wie die Wahrnehmungen über die Umgebung genutzt werden, um die nächste Aktion zu formen.
|
||
Aus ingenieurtechnischer Sicht zielt künstliche Intelligenz darauf ab, das Verhalten zu optimieren, um einen langfristigen Ertrag zu maximieren. Die Optimierung des Verhaltens basiert ausschließlich auf den Wahrnehmungen, die der Agent macht. Betrachten wir einige Anwendungsbereiche, in denen KISysteme eingesetzt werden können:
|
||
• ein Waldbrandmanagementsystem: Wahrnehmungen durch Satellitenbilder und lokale Beobachtungen mit Sensoren oder „Crowd Sensing“ über eine mobile Anwendung, die es Menschen ermöglicht, über relevante Ereignisse zu informieren; Aktionen bestehen darin, Warnungen auszugeben und offenes Feuer zu verbieten; der Ertrag ist die Reduzierung der Anzahl von Waldbränden.
|
||
• eine Steuereinheit für Verbrennungsmotoren: Wahrnehmungen durch verschiedene Messungen wie Temperatur, Kraftstoffkonsistenz; Aktionen bestehen darin, die Kraftstoffzufuhr und das Timing sowie die Menge des recycelten Abgas zu variieren; der Ertrag wird in der Reduzierung der Emissionen gemessen.
|
||
• ein Unwetterwarnungsdienst: Wahrnehmungen durch Wetterradar; Aktionen sind präventive Maßnahmen, die von Landwirten oder Stromnetzbetreibern ergriffen werden; der Ertrag wird durch Einsparungen bei den Schadenskosten gemessen (siehe https://www.munichre.com/)
|
||
• ein automatisiertes Antragssystem für die finnische Sozialversicherungsanstalt („Kela“): Wahrnehmungen durch Informationen über Antrag und Antragsteller; Aktionen bestehen entweder darin, den Antrag anzunehmen oder abzulehnen, zusammen mit einer Begründung für die Entscheidung; der Ertrag wird in der Reduzierung der Bearbeitungszeit gemessen (Antragsteller bevorzugen es in der Regel, schnell Entscheidungen zu erhalten)
|
||
• ein persönlicher Diätassistent: wahrgenommene Umgebung sind die Essvorlieben des App-Nutzers und sein Gesundheitszustand; Aktionen bestehen aus personalisierten Vorschlägen für gesundes und schmackhaftes Essen; der Ertrag ist die Steigerung des Wohlbefindens oder die Reduzierung der öffentlichen Ausgaben für Gesundheitsversorgung.
|
||
• der Reinigungsroboter Rumba (siehe Abb. 1.9) nimmt seine Umgebung mit verschiedenen Sensoren (Entfernungssensoren, On-Board-Kamera) wahr; Aktionen bestehen darin, verschiedene Bewegungsrichtungen („Norden“, „Süden“,
|
||
|
||
12
|
||
Abb. 1.9 Ein Reinigungsroboter wählt Aktionen (Bewegungsrichtungen), um einen langfristigen Ertrag zu maximieren, der durch die Menge der pro Tag gereinigten Bodenfläche gemessen wird
|
||
|
||
Aktionen
|
||
|
||
1 Einführung Umwelt
|
||
|
||
Al-System
|
||
|
||
Wahrnehmungen
|
||
|
||
„Osten“, „Westen“) zu wählen; der Ertrag könnte die Menge der gereinigten Bodenfläche innerhalb eines bestimmten Zeitraums sein. • persönlicher Gesundheitsassistent: Wahrnehmungen durch aktuellen Gesundheitszustand (Blutwerte, Gewicht,…), Lebensstil (bevorzugte Nahrung, Trainingsplan); Aktionen bestehen aus personalisierten Vorschlägen zur Änderung von Lebensgewohnheiten (weniger Fleisch, mehr Gehen,…); der Ertrag wird über das Wohlbefinden gemessen (oder die Reduzierung der öffentlichen Ausgaben für Gesundheitsversorgung). • ein Regierungssystem für ein Land: wahrgenommene Umgebung wird durch aktuelle wirtschaftliche und demografische Indikatoren wie Arbeitslosenquote, Haushaltsdefizit, Altersverteilung,… bestimmt; Aktionen beinhalten die Gestaltung von Steuer- und Arbeitsgesetzen, öffentliche Investitionen in Infrastruktur, Organisation des Gesundheitssystems; der Ertrag könnte durch das Bruttoinlandsprodukt, das Haushaltsdefizit oder das Bruttonationalglück bestimmt werden (vgl. https://de.wikipedia.org/wiki/Bruttonationalglück).
|
||
ML-Methoden werden auf verschiedenen Ebenen von einem künstlichen Intelligenz-Agenten verwendet. Auf einer niedrigeren Ebene helfen ML-Methoden dabei, die relevanten Informationen aus Rohdaten zu extrahieren. ML-Methoden werden verwendet, um Bilder in verschiedene Kategorien zu klassifizieren, die dann als Eingabe für höhere Funktionen des künstlichen Intelligenz-Agenten verwendet werden.
|
||
ML-Methoden werden auch für höhere Aufgaben eines künstlichen IntelligenzAgenten verwendet. Um optimal zu handeln, muss ein Agent eine gute Hypothese dafür lernen, wie sein Verhalten seine Umgebung beeinflusst. Wir können optimales Verhalten als eine konsequente Wahl von Aktionen betrachten, die möglicherweise durch ML-Methoden vorhergesagt werden können.
|
||
Was künstliche Intelligenz-Anwendungen von traditionelleren MLAnwendungen unterscheidet, ist die starke Interaktion zwischen ML-Methode und dem Datenerzeugungsprozess. Tatsächlich verwenden künstliche IntelligenzAgenten die Vorhersagen einer ML-Methode, um ihre nächste Aktion auszuwählen, die wiederum die Umgebung beeinflusst, die neue Datenpunkte erzeugt. Das ML-Teilgebiet des aktiven Lernens untersucht Methoden, die die Datengenerierung beeinflussen können [27].
|
||
|
||
1.2 Arten von maschinellem Lernen
|
||
|
||
13
|
||
|
||
Ein weiteres Merkmal von künstlichen Intelligenz-Anwendungen ist, dass sie es ML-Methoden typischerweise erlauben, die Qualität einer Hypothese nur im Nachhinein zu bewerten. Innerhalb einer grundlegenden (überwachten) MLAnwendung ist es möglich, dass eine ML-Methode viele verschiedene Hypothesen am selben Datenpunkt ausprobiert. Diese verschiedenen Hypothesen werden dann anhand ihrer Abweichungen von bekannten korrekten Vorhersagen bewertet. Im Gegensatz zu solchen passiven ML-Anwendungen beinhalten KIAnwendungen Datenpunkte, für die es nicht machbar ist, die korrekten Vorhersagen zu bestimmen.
|
||
Lassen Sie uns die oben genannten Unterschiede zwischen ML und künstlichen Intelligenz-Anwendungen anhand eines selbstfahrenden Spielzeugautos veranschaulichen. Das Spielzeugauto ist mit einem kleinen Onboard-Computer, einer Kamera, Sensoren und Aktoren ausgestattet, die es ermöglichen, die Lenkrichtung zu definieren. Unser Ziel ist es, den Onboard-Computer so zu programmieren, dass er einen künstlichen Intelligenz-Agenten implementiert, der das Spielzeugauto optimal steuert. Diese künstliche Intelligenz-Anwendung beinhaltet Datenpunkte, die die verschiedenen (zeitlichen) Zustände des Spielzeugautos während seiner Fahrt darstellen. Wir verwenden eine ML-Methode, um die optimale Lenkrichtung für den aktuellen Zustand vorherzusagen. Die Vorhersage für den optimalen Lenkwinkel wird durch eine Hypothesenkarte erhalten, die einen Schnappschuss von einer Onboard-Kamera liest. Da diese Vorhersagen tatsächlich dazu verwendet werden, das Auto zu steuern, beeinflussen sie die zukünftigen Datenpunkte (Zustände), die erzielt werden.
|
||
Beachten Sie, dass wir in der Regel nicht die tatsächlich optimale Lenkrichtung für jeden möglichen Zustand des Autos kennen. Es ist nicht machbar, das Spielzeugauto auf jedem möglichen Weg herumfahren zu lassen und dann jeden Schnappschuss der Onboard-Kamera manuell mit der optimalen Lenkrichtung zu beschriften (siehe Abb. 1.12). Die Nützlichkeit einer Vorhersage kann nur indirekt durch die Verwendung einer Art von Belohnungssignal gemessen werden. Ein solches Belohnungssignal könnte von einem Entfernungssensor erhalten werden, der es ermöglicht zu bestimmen, ob das Spielzeugauto die Entfernung zu einem Zielort verringert hat.
|
||
|
||
1.2 Arten von maschinellem Lernen
|
||
ML-Methoden lesen Datenpunkte ein, die innerhalb eines Anwendungsbereichs generiert werden. Ein einzelner Datenpunkt ist durch verschiedene Eigenschaften gekennzeichnet. Wir finden es praktisch, die Eigenschaften von Datenpunkten in zwei Gruppen zu unterteilen: Merkmale und Labels (siehe Abschn. 2.1). Merkmale sind Eigenschaften, die wir leicht automatisiert messen oder berechnen können. Labels sind Eigenschaften, die nicht leicht messbar sind und oft eine höhere Tatsache (oder interessante Menge) darstellen, deren Entdeckung oft menschliche Experten erfordert.
|
||
|
||
14
|
||
|
||
1 Einführung
|
||
|
||
Grob gesagt, zielt ML darauf ab, zu lernen, das Label eines Datenpunkts ausschließlich auf der Grundlage der Merkmale dieses Datenpunkts vorherzusagen (zu approximieren oder zu erraten). Formal wird die Vorhersage als Funktionswert einer Hypothesenkarte erhalten, deren Eingabeargument die Merkmale eines Datenpunkts sind. Da jede ML-Methode mit endlichen Rechenressourcen implementiert werden muss, kann sie nur eine Teilmenge aller möglichen Hypothesenkarten berücksichtigen. Diese Teilmenge wird als Hypothesenraum oder Modell bezeichnet, das einer ML-Methode zugrunde liegt. Basierend darauf, wie ML-Methoden die Qualität verschiedener Hypothesenkarten bewerten, unterscheiden wir drei Hauptformen von ML: überwachtes, unüberwachtes und verstärkendes Lernen.
|
||
|
||
1.2.1 Überwachtes Lernen
|
||
Der Hauptfokus dieses Buches liegt auf überwachten ML-Methoden. Diese Methoden verwenden einen Trainingsdatensatz, der aus gelabelten Datenpunkten besteht (für die wir die korrekten Labelwerte kennen). Wir bezeichnen einen Datenpunkt als gelabelt, wenn sein Labelwert bekannt ist. Gelabelte Datenpunkte können von menschlichen Experten erhalten werden, die Datenpunkte mit ihren Labelwerten annotieren („labeln“). Es gibt Marktplätze für die Anmietung menschlicher Labeling-Arbeitskräfte [28]. Überwachtes ML sucht nach einer Hypothese, die den menschlichen Annotator imitieren und das Label ausschließlich aus den Merkmalen eines Datenpunkts vorhersagen kann.
|
||
Abb. 1.10 veranschaulicht das Grundprinzip überwachter ML-Methoden. Diese Methoden lernen eine Hypothese mit minimaler Diskrepanz zwischen ihren Vorhersagen und den wahren Labels der Datenpunkte im Trainingsdatensatz. Locker gesprochen, passt überwachtes ML eine Kurve (die Graphik der Prädiktorkarte) an gelabelte Datenpunkte in einem Trainingsdatensatz an. Für die tatsächliche Implementierung dieser Kurvenanpassung benötigen wir eine Verlustfunktion, die den Anpassungsfehler quantifiziert. Überwachte ML-Methoden unterscheiden sich in ihrer Wahl einer Verlustfunktion zur Messung der Diskrepanz zwischen vorhergesagtem Label und wahrem Label eines Datenpunkts.
|
||
|
||
Abb. 1.10 Überwachte ML-Methoden passen eine (typischerweise hochgradig nichtlineare) Kurve an einen (typischerweise großen) Satz von Datenpunkten an
|
||
|
||
Etikett
|
||
|
||
Prädiktor
|
||
|
||
Merkmal
|
||
|
||
1.2 Arten von maschinellem Lernen
|
||
|
||
15
|
||
|
||
Obwohl das Prinzip hinter überwachtem ML trivial klingt, besteht die Herausforderung moderner ML-Anwendungen in der schieren Menge an Datenpunkten und ihrer Komplexität. ML-Methoden müssen Milliarden von Datenpunkten verarbeiten, wobei jeder einzelne Datenpunkt durch eine potenziell große Anzahl von Merkmalen charakterisiert ist. Betrachten Sie Datenpunkte, die Nutzer sozialer Netzwerke repräsentieren, deren Merkmale alle geposteten Medien umfassen (Videos, Bilder, Text). Neben der Größe und Komplexität der Datensätze ist eine weitere Herausforderung für moderne ML-Methoden, dass sie in der Lage sein müssen, hochgradig nichtlineare Prädiktorkarten anzupassen. Deep-LearningMethoden begegnen dieser Herausforderung durch die Verwendung einer rechnerisch günstigen Darstellung nichtlinearer Karten über künstliche neuronale Netzwerke [10].
|
||
|
||
1.2.2 Unüberwachtes Lernen
|
||
Einige ML-Methoden erfordern nicht, dass der Labelwert eines Datenpunkts bekannt ist und werden daher als Unüberwachtes ML bezeichnet. Unüberwachte Methoden müssen sich ausschließlich auf die intrinsische Struktur der Datenpunkte verlassen, um eine gute Hypothese zu lernen. Daher benötigen unüberwachte Methoden keinen Lehrer oder Fachexperten, der Labels für Datenpunkte bereitstellt (die zur Bildung eines Trainingsdatensatzes verwendet werden). Kap. 8 und 9 diskutieren zwei große Familien von unüberwachten Methoden, die als Clustering und Feature Lernmethoden bezeichnet werden.
|
||
Clustering-Methoden gruppieren Datenpunkte in wenige Untergruppen, so dass Datenpunkte innerhalb der gleichen Untergruppe oder des gleichen Clusters ähnlicher zueinander sind als zu Datenpunkten außerhalb des Clusters (siehe Abb. 1.11). Feature-Lernmethoden bestimmen numerische Merkmale, so dass Datenpunkte effizient mit diesen Merkmalen verarbeitet werden können. Zwei wichtige Anwendungen des Feature-Lernens sind die Reduzierung der Dimensionalität und die Datenvisualisierung.
|
||
|
||
1.2.3 Verstärkendes Lernen
|
||
Im Allgemeinen verwenden ML-Methoden eine Verlustfunktion, um verschiedene Hypothesen zu bewerten und zu vergleichen. Die Verlustfunktion weist einem Paar aus einem Datenpunkt und einer Hypothese einen (typischerweise nicht negativen) Verlustwert zu. ML-Methoden suchen nach einer Hypothese, aus einem (typischerweise großen) Hypothesenraum, die für jeden Datenpunkt den geringsten Verlust verursacht. Verstärkendes Lernen (RL) untersucht Anwendungen, bei denen die von einer Hypothese erzeugten Vorhersagen die Generierung zukünftiger
|
||
|
||
16
|
||
Abb. 1.11 ClusteringMethoden lernen, die Cluster- (oder Gruppen-) Zugehörigkeiten von Datenpunkten ausschließlich auf der Grundlage ihrer Merkmale vorherzusagen. Kap. 8 diskutiert ClusteringMethoden, die im Sinne der Nichterfordernis der Kenntnis der wahren Clusterzugehörigkeit eines Datenpunkts unüberwacht sind
|
||
|
||
1 Einführung
|
||
|
||
Datenpunkte beeinflussen. RL-Anwendungen beinhalten Datenpunkte, die die Zustände eines (programmierbaren) Systems (eines künstlichen IntelligenzAgenten) zu verschiedenen Zeitpunkten darstellen. Das Label eines solchen Datenpunktes hat die Bedeutung einer optimalen Aktion, die der Agent in einem gegebenen Zustand ausführen sollte. Ähnlich wie beim unüberwachten ML müssen RL-Methoden eine Hypothese lernen, ohne Zugang zu gelabelten Datenpunkten zu haben.
|
||
Was RL-Methoden von überwachten und unüberwachten Methoden unterscheidet, ist, dass es für sie nicht möglich ist, die Verlustfunktion für verschiedene Wahlmöglichkeiten einer Hypothese zu bewerten. Betrachten Sie eine RLMethode, die den optimalen Lenkwinkel eines Autos vorhersagen muss. Natürlich können wir nur die Nützlichkeit einer spezifischen Kombination aus vorhergesagtem Label (Lenkwinkel) und dem aktuellen Zustand des Autos bewerten. Es ist unmöglich, zwei verschiedene Hypothesen gleichzeitig auszuprobieren, da das Auto nicht zwei verschiedenen Lenkwinkeln (die durch die beiden Hypothesen erzeugt wurden) gleichzeitig folgen kann.
|
||
Mathematisch gesprochen können RL-Methoden die Verlustfunktion nur punktweise bewerten, d. h., für die aktuelle Hypothese, die verwendet wurde, um die neueste Vorhersage zu erhalten. Diese punktweisen Bewertungen der Verlustfunktion werden typischerweise durch die Verwendung eines Belohnungssignals implementiert [29]. Ein solches Belohnungssignal könnte von einem Sensorgerät erhalten werden und ermöglicht es, die Nützlichkeit der aktuellen Hypothese zu quantifizieren.
|
||
Ein wichtiges Anwendungsgebiet für RL-Methoden ist das autonome Fahren (siehe Abb. 1.12). Betrachten Sie Datenpunkte, die einzelne Zeitpunkte t = 0, 1, . . . während einer Autofahrt darstellen. Die Merkmale des tten Datenpunktes sind die Pixelintensitäten eines Schnappschusses einer On-Board-Kamera, der zum Zeitpunkt t aufgenommen wurde. Das Label dieses Datenpunktes ist die optimale Lenkrichtung zum Zeitpunkt t, um die Entfernung zwischen dem Auto
|
||
|
||
1.3 Organisation dieses Buches
|
||
|
||
17
|
||
|
||
Abb. 1.12 Autonomes Fahren erfordert die Vorhersage der optimalen Lenkrichtung (Label) basierend auf einem Schnappschuss einer On-Board-Kamera (Merkmale) in jedem Zeitpunkt. RL-Methoden passen sequenziell eine Hypothese für die Vorhersage der Lenkrichtung aus dem Schnappschuss an. Die Qualität der aktuellen Hypothese wird durch die Messung eines Entfernungssensors bewertet (um Kollisionen mit Hindernissen zu vermeiden)
|
||
und jedem Hindernis zu maximieren. Wir könnten eine ML-Methode verwenden, um eine Hypothese für die Vorhersage der optimalen Lenkrichtung ausschließlich aus den Pixelintensitäten im Schnappschuss der On-Board-Kamera zu lernen. Der durch eine bestimmte Hypothese verursachte Verlust wird aus der Messung eines Entfernungssensors bestimmt, nachdem das Auto in die vorhergesagte Richtung gefahren ist. Wir können den Verlust nur für die Hypothese bewerten, die tatsächlich verwendet wurde, um die optimale Lenkrichtung vorherzusagen. Es ist unmöglich, den Verlust für andere Vorhersagen der optimalen Lenkrichtung zu bewerten, da das Auto bereits weitergefahren ist.
|
||
1.3 Organisation dieses Buches
|
||
Kap. 2 führt die Begriffe Daten, Modell und Verlustfunktion als die drei Hauptkomponenten von ML ein. Wir werden auch einige der rechnerischen und statistischen Aspekte hervorheben, die die Designentscheidungen für diese drei Komponenten leiten könnten. Ein Leitthema dieses Buches ist die Darstellung von ML-Methoden als Kombinationen von spezifischen Designentscheidungen für Datenrepräsentation, Modell und Verlustfunktion. Anders ausgedrückt, zielen wir darauf ab, die weite Landschaft der ML-Methoden in einem abstrakten dreidimensionalen Raum abzubilden, der von den drei Dimensionen: Daten, Modell und Verlust aufgespannt wird.
|
||
Kap. 3 erläutert, wie mehrere bekannte ML-Methoden durch spezifische Designentscheidungen für Daten (Repräsentation), Modell und Verlustfunktion erzielt werden. Beispiele reichen von einfacher linearer Regression (siehe Abschn. 3.1) über Support Vector Machine (siehe Abschn. 3.7) bis hin zu tiefem Verstärkungslernen (siehe Abschn. 3.14).
|
||
|
||
18
|
||
|
||
1 Einführung
|
||
|
||
Kap. 4 diskutiert einen prinzipiellen Ansatz zur Kombination der drei Komponenten innerhalb einer praktischen ML-Methode. Insbesondere erklärt Kap. 4, wie ein einfaches probabilistisches Modell für Daten natürlich zum Prinzip der empirischen Risikominimierung führt. Dieses Prinzip übersetzt das Problem des Lernens in ein Optimierungsproblem. ML-Methoden, die auf der empirischen Risikominimierung basieren, sind daher eine spezielle Klasse von Optimierungsmethoden. Das Prinzip der empirischen Risikominimierung kann als präzise mathematische Formulierung des Paradigmas „Lernen durch Versuch und Irrtum“ interpretiert werden.
|
||
Kap. 5 diskutiert eine Familie von iterativen Methoden zur Lösung des Problems der empirischen Risikominimierung, das in Kap. 4 eingeführt wurde. Diese Methoden verwenden zur lokalen Approximation der Zielfunktion, die bei der empirischen Risikominimierung verwendet wird. Einige Varianten dieser auf Gradienten basierenden Methoden sind derzeit die Standardmethode für das Training von tiefen neuronalen Netzwerken [10].
|
||
Das Prinzip der empirischen Risikominimierung von Kap. 4 liefert eine Hypothese, die die Labels von Datenpunkten in einem Trainingssatz optimal vorhersagt. Wir möchten jedoch eine Hypothese lernen, die auch genaue Vorhersagen für Datenpunkte liefert, die nicht zum Trainingssatz gehören. Kap. 6 diskutiert einige grundlegende Validierungstechniken, die es ermöglichen, eine Hypothese außerhalb des zur Lernoptimierung dieser Hypothese verwendeten Trainingssatzes zu testen. Validierungstechniken sind entscheidend für die Modellauswahl, d. h., um das beste Modell aus einer gegebenen Reihe von Kandidatenmodellen auszuwählen. Kap. 7 stellt Regularisierungstechniken vor, die darauf abzielen, den Trainingsfehler einer Kandidatenhypothese durch eine Schätzung (oder Approximation) ihres durchschnittlichen Verlusts für Datenpunkte außerhalb des Trainingssatzes zu ersetzen.
|
||
Der Fokus von Kap. 3–7 liegt auf überwachten ML-Methoden, die einen Trainingssatz von gelabelten Datenpunkten erfordern. Kap. 8 und 9 sind unüberwachten ML-Methoden gewidmet, die keine gelabelten Daten benötigen. Kap. 8 stellt einige grundlegende Methoden zur Clusterbildung von Daten vor. Diese Methoden gruppieren oder teilen Datenpunkte in kohärente Gruppen, die als bezeichnet werden. Kap. 9 diskutiert Merkmalslern-Methoden, die automatisch die relevantesten Eigenschaften (oder Merkmale) eines Datenpunkts bestimmen. In diesem Kapitel wird auch die Bedeutung hervorgehoben, nur die relevantesten Merkmale eines Datenpunkts zu verwenden und irrelevante Merkmale zu vermeiden, um die Rechenkomplexität zu reduzieren und die Genauigkeit von MLMethoden (wie in Kap. 3) zu verbessern.
|
||
Der erfolgreiche Einsatz der ML-Methoden, wie sie in Kap. 3 diskutiert werden, hängt oft von ihrer Erklärbarkeit oder Transparenz ab. Kap. 10 diskutiert zwei verschiedene Ansätze zur Erlangung erklärbarer maschinelles Lernen. Diese Techniken berücksichtigen das individuelle Hintergrundwissen des Benutzers. Durch die Analyse eines Benutzer-Feedback-Signals, das für die Datenpunkte in einem Trainingssatz bereitgestellt wird, berechnen diese Techniken entweder
|
||
|
||
Literatur
|
||
|
||
19
|
||
|
||
personalisierte Erklärungen für eine gegebene ML-Methode oder wählen Modelle aus, die für den Benutzer intrinsisch erklärbar sind.
|
||
Voraussetzungen. Wir setzen Kenntnisse in den Grundbegriffen und Konzepten der linearen Algebra, der reellen Analysis und der Wahrscheinlichkeitstheorie voraus. Für eine Überprüfung dieser Konzepte empfehlen wir [10, Kap. 2–4] und die darin enthaltenen Referenzen. Ein Hauptziel dieses Buches ist es, die grundlegenden Ideen und Prinzipien hinter ML-Methoden mit einem Minimum an Wahrscheinlichkeitstheorie zu entwickeln. Allerdings ist ein rudimentäres Wissen über Wahrscheinlichkeitsverteilungen von beliebigen Zufallsvariablen, Wahrscheinlichkeitsdichtefunktionen von Zufallsvariablen, die im euklidischen Raum Rn definiert sind, und Wahrscheinlichkeitsmassenfunktionen für diskrete Zufallsvariablen hilfreich [24].
|
||
|
||
Literatur
|
||
1. T. Mitchell, The need for biases in learning generalizations. Technical Report CBM-TR 5-110 (Rutgers University, New Brunswick, 1980)
|
||
2. W. Rudin, Principles of Mathematical Analysis, 3. Aufl. (McGraw-Hill, New York, 1976) 3. G. Strang, Introduction to Linear Algebra, 5. Aufl. (Wellesley-Cambridge Press, Wellesley,
|
||
MA, 2016) 4. S. Sra, S. Nowozin, S.J. Wright (Hrsg.), Optimization for Machine Learning (MIT Press,
|
||
Cambridge, 2012) 5. L. Pitt, L.G. Valiant, Computational limitations on learning from examples. J. ACM 35(4),
|
||
965–984 (1988) 6. L.G. Valiant, A theory of the learnable, in Proceedings of the Sixteenth Annual ACM
|
||
Symposium on Theory of Computing, STOC ’84 (Association for Computing Machinery, New York, 1984), S. 436–445 7. C. Millard (Hrsg.), Cloud Computing Law 2. Aufl. (Oxford University Press, Oxford, 2021) 8. G.H. Golub, C.F. Van Loan, Matrix Computations, 3. Aufl. (Johns Hopkins University Press, Baltimore, MD, 1996) 9. G. Strang, Computational Science and Engineering (Wellesley-Cambridge Press, Wellesley, MA, 2007) 10. I. Goodfellow, Y. Bengio, A. Courville, Deep Learning (MIT Press, Cambridge, MA, 2016) 11. N. Tishby, N. Zaslavsky, Deep learning and the information bottleneck principle, in 2015 IEEE Information Theory Workshop (ITW) (IEEE, New York, 2015), S. 1–5 12. C.E. Shannon, Communication in the presence of noise (1948) 13. T.M. Cover, J.A. Thomas, Elements of Information Theory, 2. Aufl. (Wiley, Hoboken, NJ, 2006) 14. A.E. Gamal, Y.-H. Kim, Network Information Theory (Cambridge University Press, New York, 2012) 15. W. Wang, M.J. Wainwright, K. Ramchandran, Information-theoretic bounds on model selection for Gaussian Markov random fields, in Proc. IEEE ISIT-2010 (IEEE, New York, 2010), S. 1373–1377 16. M.J. Wainwright, Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting. IEEE Trans. Inf. Theory 55(12), 5728–5741 (2009). (Dec.) 17. N.P. Santhanam, M.J. Wainwright, Information-theoretic limits of selecting binary graphical models in high dimensions. IEEE Trans. Inf. Theory 58(7), 4117–4134 (2012). (Jul.) 18. N. Tran, O. Abramenko, A. Jung, On the sample complexity of graphical model selection from non-stationary samples. IEEE Transactions on Signal Processing 68, 17–32 (2020)
|
||
|
||
20
|
||
|
||
1 Einführung
|
||
|
||
19. A. Jung, Y. Eldar, N. Görtz, On the minimax risk of dictionary learning. IEEE Trans. Inf. Theory 62(3), 1501–1515 (2016). (Mar.)
|
||
20. B. McMahan, E. Moore, D. Ramage, S. Hampson, B.A. y Arcas, Communication-efficient learning of deep networks from decentralized data, in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Hrsg. by A. Singh, J. Zhu, Bd. 54 of Proceedings of Machine Learning Research (PMLR, 2017), S. 1273–1282
|
||
21. V. Smith, C.-K. Chiang, M. Sanjabi, A. Talwalkar, Federated multi-task learning, in Advances in Neural Information Processing Systems, Bd. 30, (MIT Press, Cambridge, MA, 2017)
|
||
22. F. Sattler, K. Müller, W. Samek, Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints, in IEEE Transactions on Neural Networks and Learning Systems (IEEE, New York, 2020)
|
||
23. Y. SarcheshmehPour, M. Leinonen, A. Jung, Federated learning from big data over networks, in Proceedings of the IEEE International Conferences on Acoustics, Speech and Signal Processing (ICASSP). Preprint at https://arxiv.org/pdf/2010.14159.pdf
|
||
24. D. Bertsekas, J. Tsitsiklis, Introduction to Probability, 2. Aufl. (Athena Scientific, Belmont, 2008)
|
||
25. I.J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio, Generative adversarial nets, in Proc. Neural Inf. Proc. Syst. (NIPS) (2014)
|
||
26. S.J. Russel, P. Norvig, Artificial Intelligence: A Modern Approach, 3. Aufl. (Prentice Hall, New York, 2010)
|
||
27. D. Cohn, Z. Ghahramani, M. Jordan, Active learning with statistical models. J. Artif. Int. Res. 4(1), 129–145 (1996). (March)
|
||
28. A. Sorokin, D. Forsyth, Utility data annotation with amazon mechanical turk, in 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (IEEE, New York, 2008), S. 1–8
|
||
29. R. Sutton, A. Barto, Reinforcement Learning: An Introduction, 2. Aufl. (MIT press, Cambridge, MA, 2018)
|
||
|
||
Kapitel 2
|
||
Komponenten des ML
|
||
|
||
Dieses Buch stellt ML als Kombinationen von drei Komponenten dar (siehe Abb. 2.1):
|
||
• Daten als Sammlungen von einzelnen Datenpunkten, die durch Merkmale (siehe Abschn. 2.1.1) und Labels (siehe Abschn. 2.1.2) gekennzeichnet sind
|
||
• ein Modell oder Hypothesenraum, der aus rechnerisch machbaren Hypothesenkarten besteht, die vom Merkmalsraum in den Labelraum führen (siehe Abschn. 2.2)
|
||
• eine Verlustfunktion (siehe Abschn. 2.3), um die Qualität einer Hypothesenkarte zu messen.
|
||
Ein ML-Problem beinhaltet spezifische Designentscheidungen für Datenpunkte, deren Merkmale und Labels, den Hypothesenraum und die Verlustfunktion zur Messung der Qualität einer bestimmten Hypothese. Ähnlich wie bei ML-Problemen (oder Anwendungen) können wir auch ML-Methoden als Kombinationen der drei oben genannten Komponenten charakterisieren.
|
||
Wir erläutern in Kap. 3 wie einige der beliebtesten ML-Methoden, einschließlich der linearen Regression (siehe Abschn. 3.1) sowie Deep-LearningMethoden (siehe Abschn. 3.11), durch spezifische Designentscheidungen für die drei Komponenten erzielt werden. Dieses Kapitel diskutiert ausführlich die Rolle und die einzelnen Komponenten von ML und ihre Kombination in ML-Methoden.
|
||
|
||
2.1 Die Daten
|
||
Daten als Sammlungen von Datenpunkten. Vielleicht ist die wichtigste Komponente eines jeden ML-Problems (und jeder Methode) die Daten. Wir betrachten Daten als Sammlungen von einzelnen Datenpunkten, die atomare Einheiten von „Informationsbehältern“ sind. Datenpunkte können Textdokumente, Signalproben von Zeitreihen, die von Sensoren erzeugt werden, ganze Zeitreihen, die von Sammlungen von Sensoren erzeugt werden, Frames innerhalb eines einzelnen Videos, Zufallsvariablen, Videos innerhalb einer Filmdatenbank, Kühe innerhalb
|
||
|
||
© Der/die Autor(en), exklusiv lizenziert an Springer Nature Singapore Pte Ltd. 2024
|
||
|
||
21
|
||
|
||
A. Jung, Maschinelles Lernen, https://doi.org/10.1007/978-981-99-7972-1_2
|
||
|
||
22 Abb. 2.1 ML-Methoden passen ein Modell an Daten an, indem sie eine Verlustfunktion minimieren
|
||
Abb. 2.2 Schnappschuss zu Beginn einer Bergwanderung
|
||
|
||
2 Komponenten des ML Modell
|
||
Daten Verlust
|
||
|
||
einer Herde, einzelne Bäume innerhalb eines Waldes, einzelne Wälder innerhalb einer Sammlung von Wäldern darstellen. Bergwanderer könnten an Datenpunkten interessiert sein, die verschiedene Wandertouren repräsentieren (siehe Abb. 2.2).
|
||
Wir verwenden das Konzept der Datenpunkte auf eine sehr abstrakte und daher hochflexible Weise. Datenpunkte können sehr unterschiedliche Arten von Objekten repräsentieren, die in grundlegend verschiedenen Anwendungsbereichen auftreten. Für eine Bildverarbeitungsanwendung könnte es nützlich sein, Datenpunkte als Bilder zu definieren. Bei der Entwicklung eines Empfehlungssystems könnten wir Datenpunkte definieren, die Kunden repräsentieren. Bei der Entwicklung neuer Medikamente könnten wir Datenpunkte verwenden, um verschiedene Krankheiten zu repräsentieren. Die Ansicht in diesem Buch ist, dass die Bedeutung der Definition von Datenpunkten als Designentscheidung betrachtet werden sollte. Wir könnten die Aufgabe, eine nützliche Definition von Datenpunkten zu finden, als „Datenpunkte-Engineering“ bezeichnen.
|
||
Eine praktische Anforderung für eine nützliche Definition von Datenpunkten ist, dass wir Zugang zu vielen von ihnen haben sollten. Viele ML-Methoden konstruieren Schätzungen für eine interessierende Größe (wie eine Vorhersage oder Prognose), indem sie über eine Menge von Referenz- (oder Trainings-) Datenpunkten mitteln. Diese Schätzungen werden genauer, je mehr Datenpunkte für die Berechnung des
|
||
|
||
2.1 Die Daten
|
||
|
||
23
|
||
|
||
Durchschnitts verwendet werden. Ein Schlüsselparameter eines Datensatzes ist die Anzahl m der einzelnen Datenpunkte, die er enthält. Die Anzahl der Datenpunkte innerhalb eines Datensatzes wird auch als Stichprobengröße bezeichnet. Statistisch gesehen ist die größere Stichprobengröße m besser. Es kann jedoch Einschränkungen bei den Rechenressourcen (wie z. B. der Speichergröße) geben, die die maximale Stichprobengröße m begrenzen, die verarbeitet werden kann.
|
||
Für die meisten Anwendungen ist es unmöglich, vollen Zugang zu jeder einzelnen mikroskopischen Eigenschaft eines Datenpunktes zu haben. Betrachten Sie einen Datenpunkt, der einen Impfstoff repräsentiert. Eine vollständige Charakterisierung eines solchen Datenpunktes würde erfordern, seine chemische Zusammensetzung bis auf die Ebene von Molekülen und Atomen zu spezifizieren. Darüber hinaus gibt es Eigenschaften eines Impfstoffs, die vom Patienten abhängen, der den Impfstoff erhalten hat.
|
||
Wir finden es nützlich, zwischen zwei verschiedenen Gruppen von Eigenschaften eines Datenpunktes zu unterscheiden. Die erste Gruppe von Eigenschaften wird als Merkmale und die zweite Gruppe von Eigenschaften wird als Labels bezeichnet. Je nach Anwendungsbereich könnten wir Labels auch als ein Ziel oder die Ausgabevariable bezeichnen. Die Merkmale eines Datenpunktes werden manchmal auch als Eingabevariablen bezeichnet.
|
||
Die Unterscheidung zwischen Merkmalen und Labels ist etwas unscharf. Die gleiche Eigenschaft eines Datenpunktes könnte in einer Anwendung als Merkmal verwendet werden, während sie in einer anderen Anwendung als Label verwendet werden könnte. Als Beispiel betrachten Sie das Merkmalslernen für Datenpunkte, die Bilder repräsentieren. Ein Ansatz, um repräsentative Merkmale eines Bildes zu lernen, besteht darin, einige der Bildpixel als das Label oder Ziel-Pixel zu verwenden. Wir können dann neue Merkmale lernen, indem wir eine Merkmalskarte lernen, die es uns ermöglicht, die Ziel-Pixel vorherzusagen.
|
||
Um die verschwommene Unterscheidung zwischen Merkmalen und Labels weiter zu veranschaulichen, betrachten Sie das Problem der fehlenden Daten. Nehmen wir an, wir haben eine Liste von Datenpunkten, die jeweils durch mehrere Eigenschaften charakterisiert sind, die im Prinzip leicht gemessen werden könnten (durch Sensoren). Diese Eigenschaften wären die ersten Kandidaten, um als Merkmale der Datenpunkte verwendet zu werden. Allerdings sind einige dieser Eigenschaften für einen kleinen Satz von Datenpunkten unbekannt (fehlend) (z. B. aufgrund von defekten Sensoren). Wir könnten dann die Eigenschaften, die für einige Datenpunkte fehlen, als Labels definieren und versuchen, diese Labels mit den verbleibenden Eigenschaften (die für alle Datenpunkte bekannt sind) als Merkmale vorherzusagen. Die Aufgabe, fehlende Werte von Eigenschaften zu bestimmen, die im Prinzip leicht gemessen werden könnten, wird als als Imputation [1] bezeichnet.
|
||
Abb. 2.3 veranschaulicht zwei Schlüsselparameter eines Datensatzes. Der erste Parameter ist die Stichprobe Größe m, d. h., die Anzahl der einzelnen Datenpunkte, die den Datensatz bilden. Der zweite Schlüsselparameter ist die Anzahl n der Merkmalen, die zur Charakterisierung eines einzelnen Datenpunktes verwendet werden. Das Verhalten von ML-Methoden hängt oft entscheidend vom Verhältnis m/n ab. Die Leistung von ML-Methoden verbessert sich in der Regel
|
||
|
||
24
|
||
|
||
2 Komponenten des ML
|
||
|
||
Jahr
|
||
|
||
Zeit precp Schnee airtmp mintmp maxtmp
|
||
|
||
Abb. 2.3 Zwei Hauptparameter eines Datensatzes sind die Anzahl (Stichprobengröße) m der einzelnen Datenpunkte, die den Datensatz bilden, und die Anzahl n der Merkmale, die zur Charakterisierung einzelner Datenpunkte verwendet werden. Das Verhalten von ML-Methoden hängt in der Regel entscheidend vom Verhältnis m/n ab.
|
||
mit zunehmendem m/n. Als Faustregel sollten wir Datensätze verwenden, für die m/n ≫ 1 gilt. Wir werden die informelle Bedingung m/n ≫ 1 in Kap. 6 genauer machen.
|
||
2.1.1 Merkmale
|
||
Ähnlich wie bei der Definition von Datenpunkten ist auch die Wahl, welche Eigenschaften als deren Merkmale verwendet werden sollen, eine Designentscheidung. Im Allgemeinen sind Merkmale Eigenschaften eines Datenpunktes, die leicht berechnet oder gemessen werden können. Dies ist jedoch eine sehr informelle Charakterisierung, da es kein universelles Kriterium für die Schwierigkeit des Berechnens oder Messens einer Eigenschaft von Datenpunkten gibt. Die Aufgabe, welche Eigenschaften als Merkmale von Datenpunkten verwendet werden sollen, könnte der herausforderndste Teil bei der Anwendung von MLMethoden sein. Kap. 9 diskutiert Methoden des Merkmallernens, die den Aufbau guter Merkmale (bis zu einem gewissen Grad) automatisieren.
|
||
In einigen Anwendungsbereichen gibt es eine eher natürliche Wahl für die Merkmale eines Datenpunktes. Für Datenpunkte, die Audioaufnahmen (von einer gegebenen Dauer) repräsentieren, könnten wir die Signalamplituden zu regelmäßigen Abtastzeitpunkten (z. B. mit einer Abtastfrequenz von 44 kHz) als Merkmale verwenden. Für Datenpunkte, die Bilder repräsentieren, scheint es natürlich, die Farbintensität (rot, grün und blau) jedes Pixels als Merkmal zu verwenden (siehe Abb. 2.4).
|
||
Die Merkmalskonstruktion für Bilder, die in Abb. 2.4 dargestellt sind, kann auf andere Arten von Datenpunkten ausgedehnt werden, solange sie effizient visualisiert werden können. Als Beispiel könnten wir eine Tonaufnahme visualisieren, indem wir ein Intensitätsdiagramm ihres Spektrogramms verwenden (siehe Abb. 2.5). Wir können dann die Pixel-RGB-Intensitäten dieses Intensitäts-
|
||
|
||
2.1 Die Daten
|
||
|
||
Pixel 2
|
||
|
||
Bildpunkt 1 Schnappschuss
|
||
|
||
25 Merkmalsvektor
|
||
|
||
Pixel
|
||
(rot-grün-blaue Bitmap) Abb. 2.4 Wenn der Schnappschuss z(i) als 512 × 512 RGB-Bitmap gespeichert wird, könnten wir als Merkmale x(i) ∈ Rn die Rot-, Grün- und Blaukomponente jedes Pixels im Schnappschuss verwenden. Die Länge des Merkmalsvektors wäre dann n = 3 · 512 · 512 ≈ 786000
|
||
Teilnehmer 1
|
||
|
||
,
|
||
|
||
,
|
||
|
||
,
|
||
|
||
,
|
||
|
||
Abb. 2.5 Zwei Visualisierungen einer Audio Aufnahme, die aus einem Liniendiagramm der Signalamplituden und dem Spektrogramm der Audioaufnahme erhalten wurden
|
||
|
||
diagramms als Merkmale für eine Tonaufnahme verwenden. Mit diesem Trick können wir jede ML-Methode für Bilddaten in eine ML-Methode für Audiodaten umwandeln. Wir können das Streudiagramm eines Datensatzes verwenden, um ML-Methoden für die Bildsegmentierung zur Clusterung des Datensatzes zu verwenden (siehe Kap. 8).
|
||
Viele wichtige ML-Anwendungsdomänen erzeugen Datenpunkte, die durch mehrere numerische Merkmale x1, . . . , xn gekennzeichnet sind. Wir repräsentieren
|
||
|
||
26
|
||
|
||
2 Komponenten des ML
|
||
|
||
numerische Merkmale durch reale Zahlen x1, . . . , xn ∈ R, was unpraktisch erscheinen mag. Tatsächlich können digitale Computer eine reale Zahl nicht genau speichern, da dies eine unendliche Anzahl von Bits erfordern würde. Allerdings ermöglicht numerische lineare Algebra-Software und -Hardware eine ausreichende Annäherung an reale Zahlen. Die Mehrheit der in diesem Buch diskutierten MLMethoden geht davon aus, dass Datenpunkte durch reale Merkmale gekennzeichnet sind. Abschn. 9.3 diskutiert Methoden zur Konstruktion numerischer Merkmale von Datenpunkten, deren natürliche Darstellung nicht numerisch ist.
|
||
Wir nehmen an, dass Datenpunkte, die in einer gegebenen ML-Anwendung auftreten, durch die gleiche Anzahl n von individuellen Merkmalen x1. . . . , xn gekennzeichnet sind. Es ist praktisch, die individuellen Merkmale eines Datenpunkts in einem einzigen Merkmalsvektor zu stapeln
|
||
x = x1, . . . , xn T .
|
||
Jeder Datenpunkt wird dann durch seinen Merkmalsvektor x gekennzeichnet. Beachten Sie, dass das Stapeln der Merkmale eines Datenpunkts in einen Spaltenvektor x reine Konvention ist. Wir könnten die Merkmale auch als Zeilenvektor oder sogar als Matrix anordnen, was für Merkmale, die durch die Pixel eines Bildes erhalten wurden, sogar natürlicher sein könnte (siehe Abb. 2.4).
|
||
Wir beziehen uns auf die Menge der möglichen Merkmalsvektoren von Datenpunkten, die in einer ML-Anwendung auftreten, als feature und bezeichnen ihn als X. Der Merkmalsraum ist eine Designentscheidung, da er davon abhängt, welche Eigenschaften eines Datenpunkts wir als seine Merkmale verwenden. Diese Designentscheidung sollte die statistischen Eigenschaften der Daten sowie die verfügbare Recheninfrastruktur berücksichtigen. Wenn die Recheninfrastruktur eine effiziente numerische lineare Algebra ermöglicht, dann könnte die Verwendung von X = Rn eine gute Wahl sein.
|
||
Der euklidische Raum Rn ist ein Beispiel für einen Merkmalsraum mit einer reichen geometrischen und algebraischen Struktur [2]. Die algebraische Struktur von Rn wird durch Vektoraddition und Multiplikation von Vektoren mit Skalaren definiert. Die geometrische Struktur von Rn wird durch die euklidische Norm als Maß für den Abstand zwischen zwei Elementen von Rn erlangt. Die algebraische und geometrische Struktur von Rn ermöglicht oft eine effiziente Suche über Rn, um Elemente mit gewünschten Eigenschaften zu finden. Abschn. 4.3 diskutiert Beispiele für solche Suchprobleme im Kontext des Lernens einer optimalen Hypothese.
|
||
Moderne Informationstechnologie, einschließlich Smartphones oder Wearables, ermöglicht es uns, eine große Anzahl von Eigenschaften über Datenpunkte in vielen Anwendungsbereichen zu messen. Betrachten Sie einen Datenpunkt, der den Buchautor „Alex Jung“ repräsentiert. Alex verwendet ein Smartphone, um ungefähr fünf Schnappschüsse pro Tag zu machen (manchmal mehr, z. B. während einer Bergwanderung), was zu mehr als 1000 Schnappschüssen pro Jahr führt. Jeder Schnappschuss enthält etwa 106 Pixel, deren Graustufen wir als Merkmale des Datenpunkts verwenden können. Dies führt zu mehr als 109 Merkmalen (pro
|
||
|
||
2.1 Die Daten
|
||
|
||
27
|
||
|
||
Jahr!). Wenn wir all diese Merkmale in einen Merkmalsvektor x stapeln, wäre seine Länge n von der Größenordnung 109.
|
||
Wie oben angegeben, beinhalten viele wichtige ML-Anwendungen Datenpunkte, die durch sehr lange Merkmalsvektoren repräsentiert werden. Um solche hochdimensionalen Daten zu verarbeiten, stützen sich moderne ML-Methoden auf Konzepte aus der hochdimensionalen Statistik [3, 4]. Ein solches Konzept aus der hochdimensionalen Statistik ist die Vorstellung von Sparsity. Abschn. 3.4 diskutiert Methoden, die die Tendenz von hochdimensionalen Datenpunkten, die durch eine große Anzahl n von Merkmalen gekennzeichnet sind, ausnutzen, sich in der Nähe von niedrigdimensionalen Unterräumen im Merkmalsraum zu konzentrieren [5].
|
||
Auf den ersten Blick könnte es scheinen, dass „je mehr Merkmale, desto besser“, da die Verwendung von mehr Merkmalen möglicherweise mehr relevante Informationen liefert, um das Gesamtziel zu erreichen. Wie wir jedoch in Kap. 7 diskutieren, kann es für die Leistung von ML-Methoden schädlich sein, eine übermäßige Anzahl von (irrelevanten) Merkmalen zu verwenden. Rechnerisch könnte die Verwendung zu vieler Merkmale zu prohibitiven Anforderungen an die Rechenressourcen (wie die Verarbeitungszeit) führen. Statistisch gesehen führt jedes zusätzliche Merkmal typischerweise eine zusätzliche Menge an Rauschen ein (aufgrund von Mess- oder Modellierungsfehlern), was sich negativ auf die Genauigkeit der ML-Methode auswirkt.
|
||
Es ist schwierig, eine genaue und allgemein anwendbare Charakterisierung der maximalen Anzahl von Merkmalen zu geben, die zur Charakterisierung der Datenpunkte verwendet werden sollten. Als Faustregel sollte die Anzahl m der (beschrifteten) Datenpunkte, die zum Trainieren einer ML-Methode verwendet werden, viel größer sein als die Anzahl n der numerischen Merkmale (siehe Abb. 2.3). Die informelle Bedingung m/n ≫ 1 kann durch das Sammeln einer ausreichend großen Anzahl m von Datenpunkten oder durch die Verwendung einer ausreichend kleinen Anzahl n von Merkmalen sichergestellt werden. Wir diskutieren als nächstes Implementierungen für jeden dieser beiden komplementären Ansätze.
|
||
Die Beschaffung von (beschrifteten) Datenpunkten kann kostspielig sein und erfordert menschliche Expertenarbeit. Anstatt mehr Rohdaten zu sammeln, könnte es effizienter sein, neue künstliche (synthetische) Daten über Datenanreicherungstechniken zu generieren. Abschn. 7.3 zeigt, wie intrinsische Symmetrien in den Daten genutzt werden können, um die Rohdaten mit synthetischen Daten zu erweitern. Als Beispiel für eine intrinsische Symmetrie von Daten betrachten Sie Datenpunkte, die ein Bild repräsentieren. Wir weisen jedem Bild das Label y = 1 zu, wenn es eine Katze zeigt und y = −1 sonst. Für jedes Bild mit bekanntem Label können wir mehrere erweiterte (zusätzliche) Bilder mit demselben Label generieren. Diese zusätzlichen Bilder könnten durch einfache Bildtransformationen wie Drehungen oder Skalierungen (Vergrößerung oder Verkleinerung) erhalten werden, die die abgebildeten Objekte (die Bedeutung des Bildes) nicht verändern. Kap. 7 zeigt, dass einige grundlegende Regularisierungstechniken als eine implizite Form von Datenaugmentation interpretiert werden können.
|
||
|
||
28
|
||
|
||
2 Komponenten des ML
|
||
|
||
Die informelle Bedingung m/n ≫ 1 kann auch durch Reduzierung der Anzahl n der zur Charakterisierung von Datenpunkten verwendeten Merkmale gewährleistet werden. In einigen Anwendungen könnten wir einige Domänenkenntnisse verwenden, um die relevantesten Merkmale auszuwählen. Für andere Anwendungen könnte es schwierig sein zu bestimmen, welche Mengen die beste Wahl für Merkmale sind. Kap. 9 diskutiert Methoden, die auf der Grundlage eines gegebenen Datensatzes lernen, eine kleine Anzahl relevanter Merkmale von Datenpunkten zu bestimmen.
|
||
Neben der verfügbaren Recheninfrastruktur müssen auch die statistischen Eigenschaften von Datensätzen bei der Auswahl des Merkmalsraums berücksichtigt werden. Die lineare algebraische Struktur von Rn ermöglicht es uns, Datensätze, die gut entlang linearer Unterräume ausgerichtet sind, effizient darzustellen und zu approximieren. Abschn. 9.2 diskutiert eine grundlegende Methode zur optimalen Approximation von Datensätzen durch lineare Unterräume einer gegebenen Dimension. Die geometrische Struktur von Rn wird auch in Kap. 8 verwendet, um einen Datensatz in wenige Gruppen oder Cluster zu zerlegen, die aus ähnlichen Datenpunkten bestehen.
|
||
In diesem Buch werden wir hauptsächlich den Merkmalsraum Rn mit der Dimension n verwenden, die die Anzahl der Merkmale eines Datenpunkts ist. Dieser Merkmalsraum hat sich in vielen ML-Anwendungen als nützlich erwiesen, da effiziente Software und Hardware für numerische lineare Algebra verfügbar sind. Darüber hinaus spiegelt die algebraische und geometrische Struktur von Rn die intrinsische Struktur der Daten wider, die in vielen wichtigen Anwendungsbereichen erzeugt werden. Dies sollte nicht allzu überraschend sein, da der Euclidean Raum sich als nützliche mathematische Abstraktion von physischen Phänomenen entwickelt hat.
|
||
Im Allgemeinen gibt es keine mathematisch korrekte Wahl dafür, welche Eigenschaften eines Datenpunkts als seine Merkmale verwendet werden sollen. Die meisten Anwendungsbereiche lassen eine gewisse Gestaltungsfreiheit bei der Auswahl der Merkmale zu. Lassen Sie uns diese Gestaltungsfreiheit anhand einer personalisierten Gesundheitsanwendung veranschaulichen. Diese Anwendung beinhaltet Datenpunkte, die Tonaufnahmen mit einer festen Dauer von drei Sekunden darstellen. Diese Aufnahmen werden über Smartphone-Mikrofone erfasst und zur Erkennung von Husten verwendet [6].
|
||
Audioaufnahmen sind typischerweise verfügbar als eine Sequenz von Signalamplituden at, die regelmäßig zu Zeitpunkten t = 1, . . . , n mit einer Abtastfrequenz von ≈ 44 kHz gesammelt werden. Aus der Sicht der Signalverarbeitung scheint es natürlich, die Signalamplituden direkt als Merkmale zu verwenden, xj = aj für j = 1, . . . , n. Eine andere Wahl für die Merkmale könnten jedoch die Pixel-RGB-Werte einer Visualisierung der Tonaufnahme sein. Abb. 2.5 zeigt zwei mögliche Visualisierungen eines Audiosignals, die aus einem Liniendiagramm der Signalamplituden (als Funktion des Zeitindex t) oder einem Intensitätsdiagramm des Spektrogramms [7, 8] erhalten wurden.
|
||
|
||
2.1 Die Daten
|
||
|
||
29
|
||
|
||
2.1.2 Labels
|
||
|
||
Neben seinen Merkmalen könnte ein Datenpunkt andere Arten von Eigenschaften haben. Diese Eigenschaften repräsentieren eine höhere Tatsache oder Menge von Interesse, die mit dem Datenpunkt verbunden ist. Wir bezeichnen solche Eigenschaften eines Datenpunkts als sein Label (oder „Ausgabe“ oder „Ziel“) und bezeichnen es typischerweise durch y (wenn es eine einzelne Zahl ist) oder durch y (wenn es sich um einen Vektor von verschiedenen Labelwerten handelt, wie bei der Mehrklassenklassifikation). Wir bezeichnen die Menge aller möglichen Labelwerte von Datenpunkten, die in einer ML-Anwendung auftreten, als Label Raum Y. Im Allgemeinen ist die Bestimmung des Labels eines Datenpunkts schwieriger (zu automatisieren) als die Bestimmung seiner Merkmale. Viele ML-Methoden drehen sich darum, effiziente Wege zu finden, um das Label eines Datenpunkts ausschließlich auf der Grundlage seiner Merkmale zu vorhersagen (schätzen oder approximieren).
|
||
Wie bereits erwähnt, ist die Unterscheidung von Datenpunkteigenschaften in Labels und Merkmale unscharf. Grob gesagt, sind Labels Eigenschaften von Datenpunkten, die möglicherweise nur mit Hilfe von menschlichen Experten bestimmt werden können. Für Datenpunkte, die Menschen repräsentieren, könnten wir sein Label y als Indikator definieren, ob die Person Grippe hat (y = 1) oder nicht (y = 0). Dieser Labelwert kann typischerweise nur von einem Arzt bestimmt werden. In einer anderen Anwendung könnten wir jedoch genügend Ressourcen haben, um den Grippestatus jeder interessierenden Person zu bestimmen und ihn als Merkmal zu verwenden, das eine Person charakterisiert.
|
||
Betrachten Sie einen Datenpunkt, der eine Wanderung repräsentiert, zu Beginn derer die Momentaufnahme in Abb. 2.2 aufgenommen wurde. Die Merkmale dieses Datenpunkts könnten die Rot-, Grün- und Blau- (RGB) Intensitäten jedes Pixels in der Momentaufnahme in Abb. 2.2 sein. Wir stapeln diese RGB-Werte in einen Vektor x ∈ Rn dessen Länge n dreimal die Anzahl der Pixel im Bild ist. Das mit einem Datenpunkt (der eine Wanderung repräsentiert) assoziierte Label y könnte die erwartete Wanderzeit sein, um den Berg auf der Momentaufnahme zu erreichen. Alternativ könnten wir das Label y als die Wassertemperatur des auf der Momentaufnahme sichtbaren Sees definieren.
|
||
Numerische Labels (Regression). Für eine gegebene ML-Anwendung enthält der Labelraum Y alle möglichen Labelwerte von Datenpunkten. Im Allgemeinen ist der Labelraum nicht nur eine Menge von verschiedenen Elementen, sondern auch mit (algebraischer oder geometrischer) Struktur ausgestattet. Um effiziente ML-Methoden zu erhalten, sollten wir solche Strukturen ausnutzen. Vielleicht das prominenteste Beispiel für einen solchen strukturierten Labelraum sind die reellen Zahlen Y = R. Dieser Labelraum ist nützlich für ML-Anwendungen, die Datenpunkte mit numerischen Labels beinhalten, die durch reelle Zahlen modelliert werden können. ML-Methoden, die darauf abzielen, ein numerisches Label vorherzusagen, werden als Regressionsmethoden bezeichnet.
|
||
Kategoriale Labels (Klassifikation). Viele wichtige ML-Anwendungen beinhalten Datenpunkte, deren Label die Kategorie oder Klasse angibt, zu der die
|
||
|
||
30
|
||
|
||
2 Komponenten des ML
|
||
|
||
Datenpunkte gehören. ML-Methoden, die darauf abzielen, solche kategorialen Labels vorherzusagen, werden als Klassifikationsmethoden bezeichnet. Beispiele für Klassifikationsprobleme sind die Diagnose von Tumoren als gutartig oder bösartig, die Klassifikation von Personen in Altersgruppen oder die Erkennung der aktuellen Bodenbedingungen („Gras“, „Fliesen“ oder „Boden“) für einen Mähroboter.
|
||
Die einfachste Art eines Klassifikationsproblems ist ein binäres Klassifikationsproblem. Innerhalb der binären Klassifikation gehört jeder Datenpunkt genau einer von zwei verschiedenen Klassen an. Daher nimmt das Label eines Datenpunkts Werte aus einer Menge an, die zwei verschiedene Elemente enthält, wie {0, 1} oder {−1, 1} oder { shows cat , shows no cat }.
|
||
Wir sprechen von einem Multi-Klassen-Klassifikation Problem, wenn Datenpunkte genau einer von mehr als zwei Kategorien angehören (z. B. Bildkategorien „keine Katze gezeigt“ vs. „eine Katze gezeigt“ und „mehr als eine Katze gezeigt“). Wenn es K verschiedene Kategorien gibt, könnten wir die Labelwerte {1, 2, . . . , K} verwenden.
|
||
Es gibt auch Anwendungen, bei denen Datenpunkte gleichzeitig zu mehreren Kategorien gehören können. Zum Beispiel kann ein Bild gleichzeitig ein Katzenund ein Hundebild sein, wenn es einen Hund und eine Katze enthält. Multi-LabelKlassifikation Probleme und Methoden verwenden mehrere Labels y1, y2, . . . , für verschiedene Kategorien, zu denen ein Datenpunkt gehören kann. Das Label yj repräsentiert die jte Kategorie und sein Wert ist yj = 1 wenn der Datenpunkt zur j -ten Kategorie gehört und yj = 0 wenn nicht.
|
||
Ordinale Labels. Ordinale Labelwerte liegen irgendwo zwischen numerischen und kategorischen Labels. Ähnlich wie kategorische Labels nehmen ordinale Labels Werte aus einer endlichen Menge an. Darüber hinaus nehmen ordinale Labels, ähnlich wie numerische Labels, Werte aus einer geordneten Menge an. Als Beispiel für einen solchen geordneten Labelraum betrachten Sie Datenpunkte, die rechteckige Flächen von 1 km mal 1 km repräsentieren. Die Merkmale x eines solchen Datenpunkts können durch Stapeln der RGB-Pixelwerte eines Satellitenbildes, das dieses Gebiet darstellt (siehe Abb. 2.4), ermittelt werden. Neben dem Merkmalsvektor wird jedes rechteckige Gebiet durch ein Label y ∈ {1, 2, 3} charakterisiert, bei dem
|
||
• y = 1 bedeutet, dass das Gebiet keine Bäume enthält. • y = 2 bedeutet, dass das Gebiet teilweise von Bäumen bedeckt ist. • y = 3 bedeutet, dass das Gebiet vollständig von Bäumen bedeckt ist.
|
||
So könnten wir sagen, dass der Label-Wert y = 2 „größer“ ist als der Label-Wert y = 1 und der Label-Wert y = 3 „größer“ ist als der Label-Wert y = 2.
|
||
Die Unterscheidung zwischen Regressions- und Klassifikationsproblemen und -methoden ist etwas unscharf. Betrachten Sie ein binäres Klassifikationsproblem basierend auf Datenpunkten, deren Label y die Werte −1 oder 1 annimmt. Wir könnten dies zu einem Regressionsproblem machen, indem wir ein neues Label y′ verwenden, das als das Vertrauen in das Label y definiert ist, gleich 1 zu sein. Andererseits können wir bei einer Vorhersage yˆ′ für das numerische Label y′ ∈ R
|
||
|
||
2.1 Die Daten
|
||
|
||
31
|
||
|
||
eine Vorhersage yˆ für das binäre Label y ∈ {−1, 1} durch Schwellenwertbildung erhalten, yˆ := 1 wenn yˆ′ ≥ 0 während yˆ := −1 sonst. Ein prominentes Beispiel für diese Verbindung zwischen Regression und Klassifikation ist die logistische Regression, die in Abschn. 3.6 diskutiert wird. Trotz ihres Namens ist die logistische Regression eine Methode zur binären Klassifikation.
|
||
Wir bezeichnen einen Datenpunkt als markiert, wenn neben seinen Merkmalen x der Wert seines Labels y bekannt ist. Die Beschaffung von markierten Datenpunkten erfordert in der Regel menschliche Arbeit, wie zum Beispiel das Bedienen eines Wasserthermometers an bestimmten Stellen in einem See. In anderen Anwendungen könnte das Erhalten von Labels das Aussenden eines Teams von Meeresbiologen in die Ostsee [9], das Durchführen eines Teilchenphysik-Experiments bei der Europäischen Organisation für Kernforschung (CERN) [10], oder das Durchführen von Tierversuchen in der Pharmakologie [11] erfordern.
|
||
Wir möchten auch auf Online-Marktplätze für menschliche LabelingArbeitskräfte hinweisen [12]. Diese Marktplätze ermöglichen das Hochladen von Datenpunkten, wie Sammlungen von Bildern oder Tonaufnahmen, und bieten dann einen Stundenlohn für Menschen an, die die Datenpunkte markieren. Diese Markierungsarbeit könnte darin bestehen, Bilder zu markieren, auf denen eine Katze zu sehen ist.
|
||
Viele Anwendungen beinhalten Datenpunkte, deren Merkmale leicht bestimmt werden können, aber deren Labels nur für wenige Datenpunkte bekannt sind. Markierte Daten sind eine knappe Ressource. Einige der erfolgreichsten MLMethoden wurden in Anwendungsbereichen entwickelt, in denen Labelinformationen leicht zu beschaffen sind [13]. ML-Methoden für Spracherkennung und maschinelle Übersetzung können massive, frei verfügbare markierte Datensätze nutzen [14].
|
||
Im extremen Fall kennen wir das Label von keinem einzigen Datenpunkt. Selbst in Abwesenheit jeglicher markierter Daten können ML-Methoden nützlich sein, um relevante Informationen nur aus Merkmalen zu extrahieren. Wir bezeichnen ML-Methoden, die keine markierten Datenpunkte benötigen, als unüberwachte ML-Methoden. Wir diskutieren einige der wichtigsten unüberwachten ML-Methoden in den Kap. 8 und 9.
|
||
Wie im Folgenden diskutiert wird, zielen viele ML-Methoden darauf ab, einen „guten“ Prädiktor h : X → Y zu konstruieren (oder zu finden), der die Merkmale x ∈ X eines Datenpunkts als Eingabe nimmt und ein vorhergesagtes Label (oder Ausgabe, oder Ziel) yˆ = h(x) ∈ Y ausgibt. Ein guter Prädiktor sollte so sein, dass yˆ ≈ y, d. h., das vorhergesagte Label yˆ ist nahe (mit kleinem Fehler yˆ − y) am wahren zugrunde liegenden Label y.
|
||
|
||
2.1.3 Streudiagramm
|
||
Betrachten Sie Datenpunkte, die durch ein einzelnes numerisches Merkmal x und ein einzelnes numerisches Label y gekennzeichnet sind. Um mehr Einblick in die Beziehung zwischen den Merkmalen und dem Label eines Datenpunkts
|
||
|
||
32
|
||
|
||
2 Komponenten des ML
|
||
|
||
zu erhalten, kann es aufschlussreich sein, ein Streudiagramm zu erstellen, wie in Abb. 1.2 gezeigt. Ein Streudiagramm stellt die Datenpunkte z(i) = (x(i), y(i)) in einer zweidimensionalen Ebene dar, wobei die Achsen die Werte des Merkmals x und des Labels y repräsentieren.
|
||
Die visuelle Inspektion eines Streudiagramms könnte potenzielle Beziehungen zwischen Merkmal x (minimale Tagestemperatur) und Label y (maximale Tagestemperatur) nahelegen. Aus Abb. 1.2 scheint es, dass es eine Beziehung zwischen Merkmal x und Label y gibt, da Datenpunkte mit größerem x tendenziell auch ein größeres y haben. Dies macht Sinn, da eine größere minimale Tagestemperatur in der Regel auch eine größere maximale Tagestemperatur impliziert.
|
||
Um ein Streudiagramm für Datenpunkte mit mehr als zwei Merkmalen zu erstellen, können wir Methoden des Merkmalslernens verwenden (siehe Kap. 9). Diese Methoden transformieren hochdimensionale Datenpunkte, die Milliarden von Rohmerkmalen haben, in drei oder zwei neue Merkmale. Diese neuen Merkmale können dann als Koordinaten der Datenpunkte in einem Streudiagramm verwendet werden.
|
||
|
||
2.1.4 Probabilistische Modelle für Daten
|
||
Eine leistungsfähige Idee in ML besteht darin, jeden Datenpunkt als Realisierung einer Zufallsvariable (ZV) zu interpretieren. Zur Vereinfachung der Darstellung betrachten wir Datenpunkte, die durch ein einzelnes Merkmal x gekennzeichnet sind. Die folgenden Konzepte können leicht auf Datenpunkte erweitert werden, die durch einen Merkmalsvektor x und ein Label y gekennzeichnet sind.
|
||
Eines der grundlegendsten Beispiele für ein probabilistisches Modell für Datenpunkte in ML ist die i.i.d. Annahme. Diese Annahme interpretiert Datenpunkte x(1), . . . , x(m) als Realisierungen statistisch unabhängiger Zufallsvariablen mit der gleichen Wahrscheinlichkeitsverteilung p(x). Es mag nicht sofort klar sein, warum es eine gute Idee ist, Datenpunkte als Realisierungen von Zufallsvariablen mit der gemeinsamen Wahrscheinlichkeitsverteilung p(x) zu interpretieren. Diese Interpretation ermöglicht es uns jedoch, die Eigenschaften der Wahrscheinlichkeitsverteilung zu nutzen, um die Gesamteigenschaften ganzer Datensätze, d. h. großer Sammlungen von Datenpunkten, zu charakterisieren.
|
||
Die Wahrscheinlichkeitsverteilung p(x), die den Datenpunkten innerhalb der i.i.d. Annahme zugrunde liegt, ist entweder bekannt (basierend auf einiger Fachkenntnis) oder wird aus Daten geschätzt. Es reicht oft aus, nur einige Parameter der Verteilung p(x) zu schätzen. Abschn. 3.12 diskutiert einen prinzipiellen Ansatz zur Schätzung der Parameter einer Wahrscheinlichkeitsverteilung aus Datenpunkten. Dieser Ansatz wird manchmal als Maximum-Likelihood bezeichnet und zielt darauf ab, (Parameter einer) Wahrscheinlichkeitsverteilung p(x) zu finden, so dass die Wahrscheinlichkeit (Dichte) der tatsächlichen Beobachtung der verfügbaren Datenpunkte maximiert wird [15–17].
|
||
|
||
2.2 Das Modell
|
||
|
||
33
|
||
|
||
Zwei der grundlegendsten und am häufigsten verwendeten Parameter einer Wahrscheinlichkeitsverteilung p(x) sind der Erwartungswert oder Mittelwert [18]
|
||
|
||
und die Varianz
|
||
|
||
ˆ
|
||
µx = E{x} := x′p(x′)dx′
|
||
x′
|
||
|
||
σx2 := E x − E{x} 2 .
|
||
|
||
Diese Parameter können mit Hilfe des Stichprobenmittelwerts (Durchschnitt) und der Stichprobenvarianz geschätzt werden,
|
||
|
||
m
|
||
µˆ x := (1/m) x(i), und
|
||
|
||
i=1
|
||
|
||
m
|
||
|
||
σx2 := (1/m)
|
||
|
||
x(i) − µˆ x 2.
|
||
|
||
i=1
|
||
|
||
(2.1)
|
||
|
||
Der Stichprobenmittelwert und die Stichprobenvarianz (2.1) sind die Maximum Likelihood-Schätzer für den Mittelwert und die Varianz einer normalen (Gaußschen) Verteilung p(x) (siehe [19, Abschn. 2.3.4]).
|
||
Die meisten der in diesem Buch diskutierten ML-Methoden basieren auf der i.i.d. Annahme. Es ist wichtig zu beachten, dass diese i.i.d. Annahme lediglich eine Modellannahme ist. Es gibt keine Möglichkeit zu überprüfen, ob eine beliebige Menge von Datenpunkten „genau“ Realisierungen von i.i.d. Zufallsvariablen sind. Es gibt jedoch prinzipielle statistische Methoden (Hypothesentests), ob eine gegebene Menge von Datenpunkten gut als Realisierungen von i.i.d. Zufallsvariablen approximiert werden kann [20]. Der einzige Weg, die i.i.d. Annahme zu gewährleisten, besteht darin, synthetische Daten mit einem Zufallszahlengenerator zu erzeugen. Solche synthetischen i.i.d. Datenpunkte könnten durch SamplingAlgorithmen erhalten werden, die einen synthetischen Datensatz schrittweise aufbauen, indem sie zufällig ausgewählte Rohdatenpunkte hinzufügen [21].
|
||
|
||
2.2 Das Modell
|
||
Betrachten Sie eine ML-Anwendung, die Datenpunkte generiert, die jeweils durch Merkmale x ∈ X und Label y ∈ Y gekennzeichnet sind. Das informelle Prinzip der meisten (wenn nicht aller) ML-Methoden besteht darin, eine Hypothesenkarte h : X → Y so zu lernen, dass
|
||
y ≈ h(x) fu¨r jeden Datenpunkt. (2.2)
|
||
yˆ
|
||
|
||
34
|
||
|
||
2 Komponenten des ML
|
||
|
||
Das informelle Ziel (2.2) wird im Laufe unseres Buches in mehreren Aspekten präzisiert. Zunächst müssen wir den Approximationsfehler (2.2) quantifizieren, der durch eine gegebene Hypothesenkarte h verursacht wird. Zweitens müssen wir präzisieren, was wir eigentlich meinen, wenn wir verlangen, dass (2.2) für „jeden“ Datenpunkt gilt. Das erste Problem lösen wir mit dem Konzept einer Verlustfunktion in Abschn. 2.3. Das zweite Problem wird dann in Kap. 4 durch die Verwendung eines einfachen probabilistischen Modells für Daten gelöst.
|
||
Gehen wir vorerst davon aus, dass wir eine vernünftige Hypothese h im Sinne von (2.2) gefunden haben. Wir können dann diese Hypothese verwenden, um das Label eines beliebigen Datenpunkts vorherzusagen, für den wir seine Merkmale kennen. Die Vorhersage yˆ = h(x) wird durch Auswertung der Hypothese für die Merkmale x eines Datenpunkts erzielt (siehe Abb. 2.6 und 2.7). Es scheint natürlich, eine Hypothesenkarte als Vorhersagekarte zu bezeichnen, da sie zur Berechnung von Vorhersagen für das Label verwendet wird.
|
||
|
||
Abb. 2.6 Eine Hypothese (Prädiktor) h bildet Merkmale x ∈ X , eines Schnappschusses einer OnBoard-Kamera, auf die Vorhersage yˆ = h(x) ∈ Y für die Koordinate des aktuellen Standorts eines Reinigungsroboters ab. ML-Methoden verwenden Daten, um Prädiktoren h zu lernen, so dass yˆ ≈ y (mit wahrem Label y )
|
||
|
||
Schnappschuss
|
||
|
||
Prädikatorenkarte
|
||
|
||
y-Koordinate von Rumba
|
||
|
||
Merkmalsraum
|
||
|
||
Etikett (Ausgabe) Raum
|
||
|
||
Abb. 2.7 Eine Hypothese h : X → Y nimmt den Merkmalsvektor x(t) ∈ X (z. B., die zu Zeit t
|
||
von Rumba aufgenommene Momentaufnahme) als Eingabe und gibt ein vorhergesagtes Label yˆ(t) = h(x(t)) aus (z. B., die vorhergesagte y-Koordinate von Rumba zu Zeit t). Ein Schlüssel-
|
||
problem, das im ML untersucht wird, ist, wie man automatisch einen guten (genauen) Prädiktor h lernt, so dass y(t) ≈ h(x(t))
|
||
|
||
2.2 Das Modell
|
||
|
||
35
|
||
|
||
Für ML-Probleme mit einem endlichen Labelraum Y (z. B., Y = {−1, 1}, bezeichnen wir eine Hypothese auch als Klassifikator. Für einen endlichen Y, können wir eine bestimmte Klassifikatorkarte h anhand ihrer verschiedenen Entscheidungsregionen charakterisieren
|
||
|
||
R(a) := {x ∈ Rn : h = a} ⊆ X .
|
||
|
||
(2.3)
|
||
|
||
Jeder Labelwert a ∈ Y ist mit einer spezifischen Entscheidungsregion R(a) := {x ∈ Rn : h = a} verbunden. Für einen gegebenen Labelwert a ∈ Y besteht die Entscheidungsregion R(a) := {x ∈ Rn : h = a} aus allen Merkmalsvektoren x ∈ X, die auf diesen Labelwert abgebildet werden, h(x) = a.
|
||
Im Prinzip könnten ML-Methoden jede mögliche Abbildung h : X → Y verwenden, um das Label y ∈ Y durch Berechnung yˆ = h(x) vorherzusagen. Die Menge aller Abbildungen vom Merkmalsraum X zum Labelraum wird typischerweise als YX bezeichnet.1 Im Allgemeinen ist die Menge YX viel zu groß, um von praktischen ML-Methoden durchsucht zu werden. Als Beispiel betrachten Sie Datenpunkte, die durch ein einziges numerisches Merkmal x ∈ R und Label y ∈ R gekennzeichnet sind. Die Menge aller reellwertigen Abbildungen h(x) eines reellwertigen Arguments enthält bereits unendlich viele verschiedene Hypothesenkarten [22].
|
||
Praktische ML-Methoden können nur einen (winzigen) Teilmenge aller möglichen Hypothesenkarten suchen und bewerten. Diese Teilmenge von rechnerisch machbaren („bezahlbaren“) Hypothesenkarten wird als Hypothesenraum oder Modell bezeichnet, das einer ML-Methode zugrunde liegt. Wie in Abb. 2.10 dargestellt, verwenden MLMethoden typischerweise einen Hypothesenraum H, der eine winzige Teilmenge von YX ist. Ähnlich wie die Merkmale und Labels, die zur Charakterisierung von Datenpunkten verwendet werden, ist auch der Hypothesenraum, der einer ML-Methode zugrunde liegt, eine Designwahl. Wie wir sehen werden, beinhaltet die Wahl des Hypothesenraums einen Kompromiss zwischen rechnerischer Komplexität und statistischen Eigenschaften der resultierenden ML-Methoden.
|
||
Die Präferenz für einen bestimmten Hypothesenraum hängt oft von der verfügbaren rechnerischen Infrastruktur ab, die einer ML-Methode zur Verfügung steht. Verschiedene rechnerische Infrastrukturen bevorzugen verschiedene Hypothesenräume. ML-Methoden, die in einem kleinen eingebetteten System implementiert sind, bevorzugen möglicherweise einen linearen Hypothesenraum, der zu Algorithmen führt, die eine geringe Anzahl von Rechenoperationen erfordern. Deep-Learning-Methoden, die in einer Cloud-Computing-Umgebung implementiert sind, verwenden typischerweise viel größere Hypothesenräume, die aus tiefen neuronalen Netzwerken gewonnen werden.
|
||
ML-Methoden können auch mit einer Tabellenkalkulationssoftware implementiert werden. Hier könnten wir einen Hypothesenraum verwenden, der aus Abbildungen h : X → Y besteht, die durch Nachschlagetabellen repräsentiert werden (siehe Tab. 2.1). Wenn wir stattdessen die Programmiersprache Python
|
||
|
||
1Die Notation YX ist als symbolische Abkürzung zu verstehen und sollte nicht wörtlich als Potenz wie 45 verstanden werden.
|
||
|
||
36
|
||
|
||
2 Komponenten des ML
|
||
|
||
Tab. 2.1 Eine Nachschlagetabelle definiert eine Hypothesenkarte h. Der Wert h(x) wird durch den Eintrag in der zweiten Spalte der Zeile gegeben, deren erster Spalteneintrag x ist. Wir können einen Hypothesenraum H erstellen, indem wir eine Sammlung verschiedener Nachschlagetabellen verwenden
|
||
|
||
Merkmal x
|
||
|
||
Vorhersage h(x)
|
||
|
||
0
|
||
|
||
0
|
||
|
||
1/10
|
||
|
||
10
|
||
|
||
2/10
|
||
|
||
3
|
||
|
||
...
|
||
|
||
...
|
||
|
||
1
|
||
|
||
22,3
|
||
|
||
verwenden, um eine ML-Methode zu implementieren, können wir eine Hypothesenklasse erhalten, indem wir alle möglichen Python-Unterroutinen mit einer Eingabe (skalares Merkmal x), einem Ausgabeargument (vorhergesagtes Label yˆ) und weniger als 100 Codezeilen sammeln.
|
||
Im Großen und Ganzen muss die Designwahl für den Hypothesenraum H einer ML-Methode zwischen zwei sich widersprechenden Anforderungen abwägen.
|
||
• Es muss ausreichend groß sein, so dass es mindestens eine genaue Vorhersagekarte hˆ ∈ H enthält. Ein Hypothesenraum H, der zu klein ist, könnte scheitern, eine Vorhersagekarte zu enthalten, die benötigt wird, um die (möglicherweise stark nichtlineare) Beziehung zwischen Merkmalen und Label zu reproduzieren. Betrachten Sie die Aufgabe, Bilder in „Katzenbilder“ und „keine Katzenbilder“ zu gruppieren oder zu klassifizieren. Die Klassifizierung jedes Bildes basiert ausschließlich auf dem Merkmalsvektor, der aus den Pixel-Farbwerten gewonnen wird. Die Beziehung zwischen Merkmalen und Label (y ∈ { cat , no cat }) ist stark nichtlinear. Jede ML-Methode, die einen Hypothesenraum verwendet, der nur aus linearen Karten besteht, wird höchstwahrscheinlich scheitern, einen guten Vorhersager (Klassifikator) zu lernen. Wir sagen, dass eine ML-Methode underfitting betreibt, wenn sie einen Hypothesenraum verwendet, der keine Hypothesenkarten enthält, die das Label von Datenpunkten genau vorhersagen können.
|
||
• Es muss ausreichend klein sein, so dass seine Verarbeitung in die verfügbaren Rechenressourcen (Speicher, Bandbreite, Verarbeitungszeit) passt. Wir müssen in der Lage sein, effizient über den Hypothesenraum zu suchen, um gute Vorhersager zu finden (siehe Abschn. 2.3 und Kap. 4). Diese Anforderung impliziert auch, dass die Karten h(x), die in H enthalten sind, effizient ausgewertet (berechnet) werden können [23]. Ein weiterer wichtiger Grund für die Verwendung eines Hypothesenraums H, der nicht zu groß ist, besteht darin, Overfitting zu vermeiden (siehe Kap. 7). Wenn der Hypothesenraum H zu groß ist, könnten wir einfach durch Glück eine Hypothese finden, die die Labels von Datenpunkten in einem Trainingssatz, der zum Lernen einer Hypothese verwendet wird, (fast) perfekt vorhersagt. Eine solche Hypothese könnte jedoch schlechte Vorhersagen für Labels von Datenpunkten außerhalb des Trainingssatzes liefern. Wir sagen, dass die Hypothese nicht gut generalisiert.
|
||
|
||
2.2 Das Modell
|
||
|
||
37
|
||
|
||
2.2.1 Parametrisierte Hypothesenräume
|
||
|
||
Eine breite Palette aktueller wissenschaftlicher Rechenumgebungen ermöglicht eine effiziente numerische lineare Algebra. Diese Hard- und Software ermöglicht es, Daten effizient zu verarbeiten, die in Form von numerischen Arrays wie Vektoren, Matrizen oder Tensoren bereitgestellt werden [24]. Um diese Recheninfrastruktur zu nutzen, verwenden viele ML-Methoden den Hypothesenraum
|
||
H(n) := {h(w) : Rn → R : h(w)(x) = xT w mit einem Gewichtsvektor w ∈ Rn}. (2.4)
|
||
Der Hypothesenraum (2.4) besteht aus linearen Abbildungen (Funktionen)
|
||
|
||
h(w) x : Rn → R : x �→ wT x.
|
||
|
||
(2.5)
|
||
|
||
Die Funktion h(w) (2.5) bildet den Merkmalsvektor in linearer Weise ab.x ∈ Rn zum vorhergesagten Label (oder Ausgabe) h(w)(x) = xT w ∈ R. Für n = 1 reduziert
|
||
der Merkmalsvektor auf ein einzelnes Merkmal x und der Hypothesenraum (2.4) besteht aus allen Abbildungen h(w)(x) = wx mit einem gewissen Gewicht w ∈ R
|
||
(siehe Abb. 2.8). Die Elemente des Hypothesenraums H in (2.4) werden durch den Gewichtsvektor w ∈ Rn parametrisiert. Jede Abbildung h(w) ∈ H ist vollständig durch den Gewichtsvektor w ∈ Rn spezifiziert. Diese Parametrisierung des Hypothesenraums H ermöglicht es, Hypothesenkarten durch Vektoroperationen zu verarbeiten und
|
||
zu manipulieren. Insbesondere können wir anstelle der Suche im Funktionenraum H (dessen Elemente Funktionen sind!) nach einer guten Hypothese, äquivalent über alle möglichen Gewichtsvektoren w ∈ Rn suchen.
|
||
Der Suchraum Rn ist immer noch (unzählbar) unendlich, hat aber eine reiche
|
||
geometrische und algebraische Struktur, die es uns ermöglicht, effizient über
|
||
diesen Raum zu suchen. Kap. 5 diskutiert Methoden, die das Konzept der
|
||
|
||
,
|
||
|
||
,
|
||
|
||
,
|
||
|
||
,
|
||
|
||
Merkmal
|
||
|
||
Abb. 2.8 Drei spezielle Mitglieder des Hypothesenraums H = {h(w) : R → R, h(w)(x) = w · x},
|
||
der aus allen linearen Funktionen des Skalarmerkmals x besteht. Wir können diesen Hypothesenraum bequem mit dem Gewicht w ∈ R parametrisieren als h(w)(x) = w · x
|
||
|
||
38
|
||
|
||
2 Komponenten des ML
|
||
|
||
Gradienten verwenden, um eine effiziente Suche nach guten Gewichten w ∈ Rn zu implementieren.
|
||
Der Hypothesenraum (2.4) ist auch attraktiv wegen der breiten Verfügbarkeit von Rechenhardware wie Grafikprozessoreinheiten. Ein weiterer Faktor, der die weit verbreitete Nutzung von (2.4) fördern könnte, ist das Angebot optimierter Softwarebibliotheken für numerische lineare Algebra.
|
||
Der Hypothesenraum (2.4) kann auch für Klassifizierungsprobleme verwendet werden, z. B. mit Labelraum Y = {−1, 1}. Tatsächlich können wir, gegeben eine lineare Vorhersagekarte h(w), Datenpunkte gemäß yˆ = 1 für h(w)(x) ≥ 0 und yˆ = −1 sonst klassifizieren. Wir bezeichnen einen Klassifikator, der das vorhergesagte Label berechnet, indem er zuerst eine lineare Abbildung auf die Merkmale anwendet, als linearen Klassifikator.
|
||
Abb. 2.9 veranschaulicht die Entscheidungsregionen (2.3) eines linearen Klassifikators für binäre Labels. Die Entscheidungsregionen sind Halbräume und die Entscheidungsgrenze ist dementsprechend eine Hyperebene {x : wT x = b}. Beachten Sie, dass jeder lineare Klassifikator einer bestimmten linearen Hypothesenkarte aus dem Hypothesenraum (2.4) entspricht (Abb. 2.10). Wir können jedoch verschiedene Verlustfunktionen verwenden, um die Qualität eines linearen Klassifikators zu messen. Drei weit verbreitete Beispiele für ML-Methoden, die einen linearen Klassifikator erlernen, sind die logistische Regression (siehe Abschn. 3.6), die Support-Vektor-Maschine (siehe Abschn. 3.7) und der naive Bayes-Klassifikator (siehe Abschn. 3.8).
|
||
In einigen Anwendungsbereichen ist die Beziehung zwischen Merkmalen x und Label y eines Datenpunkts stark nicht-linear. Betrachten Sie zum Beispiel Datenpunkte, die Bilder von Tieren repräsentieren. Die Karte, die die Pixelintensitäten des Bildes mit dem Label in Beziehung setzt, das angibt, ob es sich um ein Katzenbild handelt, ist stark nicht-linear. Für solche Anwendungen ist der Hypothesenraum (2.4) nicht geeignet, da er nur lineare Karten enthält. Das zweite
|
||
|
||
Entscheidungsgrenze
|
||
|
||
Abb. 2.9 Eine Hypothese h : X → Y für ein binäres Klassifikationsproblem, mit Labelraum Y = {−1, 1} und Merkmalsraum X = R2, kann bequem über die Entscheidungsgrenze (gestrichelte Linie) dargestellt werden, die alle Merkmalsvektoren x mit h(x) ≥ 0 von der
|
||
Region der Merkmalsvektoren mit h(x) < 0 trennt. Wenn die Entscheidungsgrenze eine Hyperebene {x : wT x = b} (mit Normalvektor w ∈ Rn) ist, bezeichnen wir die Karte h als linearen
|
||
Klassifikator
|
||
|
||
2.2 Das Modell
|
||
|
||
39
|
||
|
||
Abb. 2.10 Der Hypothesen Raum H ist eine (typischerweise
|
||
sehr kleine) Teilmenge
|
||
der (typischerweise sehr großen) Menge YX aller möglichen Abbildungen vom Merkmalsraum X in den Labelraum Y
|
||
|
||
Hauptbeispiel für einen parametrisierten Hypothesenraum, das in diesem Buch untersucht wird, enthält auch nicht-lineare Karten. Dieser parametrisierte Hypothesenraum wird aus einem parametrisierten Signalflussdiagramm gewonnen, das als künstliches neuronales Netzwerk bezeichnet wird. Abschn. 3.11 wird die Konstruktion von nicht-linearen parametrisierten Hypothesenräumen mit Hilfe eines künstlichen neuronalen Netzwerks diskutieren.
|
||
Erweiterung eines Hypothesenraums durch Merkmalsabbildungen. Lassen Sie uns eine einfache, aber leistungsstarke Technik zur Vergrößerung („Upgrade“) eines gegebenen Hypothesenraums H zu einem größeren Hypothesenraum H′ ⊇ H diskutieren, der eine größere Auswahl an Hypothesenabbildungen bietet. Die Idee besteht darin, die ursprünglichen Merkmale x eines Datenpunkts durch neue (transformierte) Merkmale z = �(x) zu ersetzen. Die transformierten Merkmale werden durch Anwendung einer feature map �(·) auf die ursprünglichen Merkmale x erzielt. Dieser erweiterte Hypothesenraum H′ besteht aus allen Verkettungen der Merkmalsabbildung und einer Hypothese h ∈ H ,
|
||
|
||
H′ := h′(·) : x �→ h �(x) : h ∈ H .
|
||
|
||
(2.6)
|
||
|
||
Die Konstruktion (2.6) wird für beliebige Kombinationen einer Merkmalsabbildung �(·) und eines „Basis“-Hypothesenraums H verwendet. Die einzige Anforderung ist, dass die Ausgabe der Merkmalsabbildung als Eingabe für eine Hypothese h ∈ H verwendet werden kann. Formeller ausgedrückt, muss der Bereich der Merkmalsabbildung zum Bereich der Abbildungen in H gehören. Beispiele für ML-Methoden, die einen Hypothesenraum der Form (2.6) verwenden, sind die Polynomregression (siehe Abschn. 3.2), die Gaußsche Basisregression (siehe Abschn. 3.5) und die wichtige Familie der Kernel-Methoden (siehe Abschn. 3.9). Die Merkmalsabbildung in (<2.6) könnte auch durch Clustering oder Feature-Learning-Methoden erzielt werden (siehe Abschn. 8.4 und 9.2.1).
|
||
Für den Spezialfall des linearen Hypothesenraums (2.4), ist der resultierende erweiterte Hypothesenraum (2.6) gegeben durch alle linearen Abbildungen wT z der transformierten Merkmale �(x). Die Kombination des Hypothesenraums (2.4) mit einer nicht-linearen Feature-Abbildung führt zu einem Hypothesenraum, der nicht-lineare Abbildungen vom ursprünglichen Merkmalsvektor x zum vorhergesagten Label yˆ enthält,
|
||
|
||
yˆ = wT z = wT �(x).
|
||
|
||
(2.7)
|
||
|
||
40
|
||
|
||
2 Komponenten des ML
|
||
|
||
Nicht-numerische Merkmale. Der Hypothesenraum (2.4) kann nur für Datenpunkte verwendet werden, deren Merkmale numerische Vektoren sind x = (x1, . . . , xn)T ∈ Rn. In einigen Anwendungsbereichen, wie der natürlichen Sprachverarbeitung, gibt es keine offensichtliche natürliche Wahl für numerische Merkmale. Da jedoch ML-Methoden, die auf dem Hypothesenraum (2.4) basieren, gut entwickelt sind (unter Verwendung numerischer linearer Algebra), könnte es nützlich sein, numerische Merkmale auch für nicht-numerische Daten (wie Text) zu konstruieren. Für Textdaten gab es in jüngster Zeit erhebliche Fortschritte bei Methoden, die einen vom Menschen generierten Text in Sequenzen von Vektoren abbilden (siehe [25, Kap. 12] für weitere Details). Darüber hinaus wird Abschn. 9.3 einen Ansatz zur Generierung numerischer Merkmale für Datenpunkte diskutieren, die eine intrinsische Vorstellung von Ähnlichkeit haben.
|
||
|
||
2.2.2 Die Größe eines Hypothesenraums
|
||
Die Vorstellung, dass ein Hypothesenraum zu klein oder zu groß sein kann, kann auf verschiedene Weisen präzisiert werden. Die Größe eines endlichen Hypothesenraums H kann als seine Kardinalität |H| definiert werden, die einfach die Anzahl seiner Elemente ist. Betrachten Sie zum Beispiel Datenpunkte, die durch 100 × 10 = 1000 Schwarz-Weiß-Pixel dargestellt und durch ein binäres Label y ∈ {0, 1} charakterisiert werden. Wir können solche Datenpunkte mit dem Merkmalsraum X = {0, 1}1000 und dem Labelraum Y = {0, 1} modellieren. Der größtmögliche Hypothesenraum H = YX besteht aus allen Abbildungen von X nach Y. Die Größe oder Kardinalität dieses Raums ist |H| = 2 . 21000
|
||
Viele ML-Methoden verwenden einen Hypothesenraum, der unendlich viele verschiedene Prädiktorabbildungen enthält (siehe z. B. (2.4)). Für einen unendlichen Hypothesenraum können wir die Anzahl seiner Elemente nicht als Maß für seine Größe verwenden. Tatsächlich ist die Anzahl der Elemente für einen unendlichen Hypothesenraum nicht gut definiert. Daher messen wir die Größe eines Hypothesenraums H mit seiner effektiven Dimension deff(H).
|
||
Betrachten Sie einen Hypothesenraum H, bestehend aus Abbildungen h : X → Y, die die Merkmale x ∈ X einlesen und ein vorhergesagtes Label yˆ = h(x) ∈ Y ausgeben. Wir definieren die effektive Dimension deff(H) von H als die maximale Anzahl D ∈ N, so dass für jede Menge D = x(1), y(1) , . . . , x(D), y(D) } von D Datenpunkten mit unterschiedlichen Merkmalen, wir immer eine Hypothese h ∈ H finden können, die die Labels perfekt passt, y(i) = h x(i) für i = 1, . . . , D.
|
||
Die effektive Dimension eines Hypothesenraums steht in engem Zusammenhang mit der Vapnik-Chervonenkis (VC) Dimension [26]. Die VapnikChervonenkis (VC) Dimension ist vielleicht das am häufigsten verwendete Konzept zur Messung der Größe von unendlichen Hypothesenräumen [19, 26–28]. Die genaue Definition der Vapnik-Chervonenkis (VC) Dimension geht jedoch über den Rahmen dieses Buches hinaus. Darüber hinaus erfasst die effektive Dimension
|
||
|
||
2.3 Der Verlust
|
||
|
||
41
|
||
|
||
die meisten relevanten Eigenschaften der Vapnik-Chervonenkis (VC) Dimension für unsere Zwecke. Für eine genaue Definition der Vapnik-Chervonenkis (VC) Dimension und eine Diskussion ihrer Anwendungen in ML verweisen wir auf [27].
|
||
Lassen Sie uns unser Konzept für die Größe eines Hypothesenraums anhand von zwei Beispielen veranschaulichen: lineare Regression und polynomiale Regression. Die lineare Regression verwendet den Hypothesenraum
|
||
H(n) = {h : Rn → R : h(x) = wT x mit irgendeinem Vektor w ∈ Rn}.
|
||
Betrachten Sie einen Datensatz D = { x(1), y(1) , . . . , x(m), y(m) } bestehend aus m Datenpunkten. Wir bezeichnen diese Anzahl auch als Stichprobengröße des Datensatzes. Jeder Datenpunkt ist durch einen Merkmalsvektor x(i) ∈ Rn und ein numerisches Label y(i) ∈ R gekennzeichnet.
|
||
Nehmen wir an, dass Datenpunkte Realisierungen von kontinuierlichen i.i.d. Zufallsvariablen mit einer gemeinsamen Wahrscheinlichkeitsdichtefunktion sind. Unter dieser Annahme ist die Matrix
|
||
X = x(1), . . . , x(m) ∈ Rn×m,
|
||
die durch Stapeln (spaltenweise) der Merkmalsvektoren x(i) (für i = 1, . . . , m), mit Wahrscheinlichkeit eins vollständig ist. Grundlegende Ergebnisse der linearen Algebra ermöglichen es zu zeigen, dass die Datenpunkte in D perfekt durch eine lineare Abbildung h ∈ H(n) dargestellt werden können, solange m ≤ n. Sobald die Anzahl m der Datenpunkte nicht strikt größer ist als die Anzahl der Merkmale, die jeden Datenpunkt charakterisieren, d. h., m ≤ n, können wir (mit Wahrscheinlichkeit eins) einen Gewichtsvektor w finden, so dass y(i) = wT x(i) für alle i = 1, . . . , m. Die effektive Dimension des linearen Hypothesenraums H(n) ist daher D = n.
|
||
Als zweites Beispiel betrachten wir den Hypothesenraum Hp(no)ly, der aus der Menge der Polynome mit maximalem Grad n besteht. Der Fundamentalsatz der Algebra besagt, dass jede Menge von m Datenpunkten mit unterschiedlichen Merkmalen perfekt durch ein Polynom des Grades n angepasst werden kann, solange n ≥ m. Daher ist die effektive Dimension des Hypothesenraums Hp(no)ly D = n. Abschn. 3.2 diskutiert die Polynomregression im Detail.
|
||
|
||
2.3 Der Verlust
|
||
Jede ML-Methode verwendet einen (mehr oder weniger expliziten) Hypothesenraum H, der aus allen rechnerisch machbaren Vorhersagekarten h besteht. Welche Vorhersagekarte h aus allen Karten im Hypothesenraum H ist die beste für das vorliegende ML-Problem? Um diese Frage zu beantworten, verwenden MLMethoden das Konzept einer Verlustfunktion. Formal ist eine Verlustfunktion eine Abbildung
|
||
|
||
42
|
||
|
||
2 Komponenten des ML
|
||
|
||
L : X × Y × H → R+ : x, y , h �→ L((x, y), h)
|
||
die einem Paar, bestehend aus einem Datenpunkt mit Merkmalen x und Label y, und einer Hypothese h ∈ H die nicht-negative reale Zahl L((x, y), h) zuweist.
|
||
Der Verlustwert L((x, y), h) quantifiziert die Diskrepanz zwischen dem wahren Label y und dem vorhergesagten Label h(x). Ein kleiner (nahe Null) Wert L((x, y), h) deutet auf eine geringe Diskrepanz zwischen vorhergesagtem Label und wahrem Label eines Datenpunkts hin. Abb. 2.11 zeigt eine Verlustfunktion für einen gegebenen Datenpunkt, mit Merkmalen x und Label y, als Funktion der Hypothese h ∈ H. Das grundlegende Prinzip von ML-Methoden kann dann formuliert werden als: Lernen (Finden) einer Hypothese aus einem gegebenen Hypothesenraum H, die einen minimalen Verlust L((x, y), h) für jeden Datenpunkt verursacht (siehe Kap. 4).
|
||
Ähnlich wie die Wahl des Hypothesenraums H, der in einer ML-Methode verwendet wird, ist auch die Verlustfunktion eine Designwahl. Wir werden einige weit verbreitete Beispiele für Verlustfunktionen in den Abschn. 2.3.1 und 2.3.2 diskutieren. Die Wahl der Verlustfunktion sollte die Rechenkomplexität der Suche im Hypothesenraum nach einer Hypothese mit minimalem Verlust berücksichtigen. Betrachten Sie eine ML-Methode, die einen Hypothesenraum verwendet, der durch einen Gewichtsvektor parametrisiert ist, und eine Verlustfunktion, die eine konvexe und differenzierbare (glatte) Funktion des Gewichtsvektors ist. In diesem Fall kann die Suche nach einer Hypothese mit geringem Verlust effizient mit den in Kap. 5 diskutierten gradientenbasierten Methoden durchgeführt werden. Die Minimierung einer Verlustfunktion, die entweder nicht konvex oder nicht differenzierbar ist, ist typischerweise rechnerisch viel schwieriger. Abschn. 4.2 diskutiert die Rechenkomplexitäten verschiedener Arten von Verlustfunktionen genauer.
|
||
Neben rechnerischen Aspekten sollte die Wahl der Verlustfunktion auch statistische Aspekte berücksichtigen. Einige Verlustfunktionen führen zu MLMethoden, die robuster gegen Ausreißer sind (siehe Abschn. 3.3 und 3.7). Die
|
||
|
||
Hypothese
|
||
Abb. 2.11 Eine Verlustfunktion L((x, y), h) für einen festen Datenpunkt, mit Merkmalen x und Label y, und variierender Hypothese h. ML-Methoden versuchen, eine Hypothese zu finden (zu lernen), die einen minimalen Verlust verursacht
|
||
|
||
2.3 Der Verlust
|
||
|
||
43
|
||
|
||
Wahl der Verlustfunktion könnte auch durch probabilistische Modelle für die in einer ML-Anwendung generierten Daten geleitet werden. Abschn. 3.12 erläutert, wie das Prinzip der maximalen Wahrscheinlichkeit der statistischen Inferenz eine explizite Konstruktion von Verlustfunktionen in Bezug auf eine (angenommene) Wahrscheinlichkeitsverteilung für Datenpunkte liefert.
|
||
Die Wahl der Verlustfunktion zur Bewertung der Qualität einer Hypothese könnte auch durch ihre Interpretierbarkeit beeinflusst werden. Abschn. 2.3.2 diskutiert Verlustfunktionen für Hypothesen, die dazu dienen, Datenpunkte in zwei Kategorien zu klassifizieren. Es scheint natürlich, die Qualität einer solchen Hypothese durch die durchschnittliche Anzahl falsch klassifizierter Datenpunkte zu messen, was genau dem durchschnittlichen 0/1-Verlust (2.9) entspricht (siehe Abschn. 2.3.2). Daher kann der durchschnittliche 0/1-Verlust als Fehlklassifikations- (oder Fehler-) Rate interpretiert werden. Die Verwendung des durchschnittlichen 0/1-Verlusts zum Erlernen einer genauen Hypothese führt jedoch zu rechnerisch anspruchsvollen Problemen. Abschn. 2.3.2 stellt den logistischen Verlust als rechnerisch attraktive alternative Wahl für die Verlustfunktion in binären Klassifikationsproblemen vor.
|
||
Die oben genannten Aspekte (Berechnung, Statistik, Interpretierbarkeit) führen typischerweise zu konfliktierenden Zielen bei der Wahl einer Verlustfunktion. Eine Verlustfunktion, die günstige statistische Eigenschaften hat, könnte eine hohe rechnerische Komplexität der resultierenden ML-Methode verursachen. Verlustfunktionen, die zu rechnerisch effizienten ML-Methoden führen, ermöglichen möglicherweise keine einfache Interpretation (was bedeutet es, wenn der logistische Verlust einer Hypothese in einem binären Klassifikationsproblem 10−1 ist?). Es könnte daher nützlich sein, verschiedene Verlustfunktionen für die Suche nach einer guten Hypothese (siehe Kap. 4) und für ihre endgültige Bewertung zu verwenden. Abb. 2.12 zeigt ein Beispiel für zwei solche Verlustfunktionen, eine
|
||
|
||
Verlust für das Erlernen eines guten
|
||
|
||
Verlust (metrisch) für die endgültige Bewertung
|
||
|
||
Hypothese
|
||
|
||
Abb. 2.12 Zwei verschiedene Verlustfunktionen für einen gegebenen Datenpunkt und variierende Hypothese h. Eine Verlustfunktion (feste Kurve) wird verwendet, um eine gute Hypothese durch Minimierung des Verlusts zu lernen. Eine andere Verlustfunktion (gestrichelte Kurve) wird für die endgültige Leistungsbewertung der gelernten Hypothese verwendet. Die für die endgültige Leistungsbewertung verwendete Verlustfunktion wird als Metrik bezeichnet
|
||
|
||
44
|
||
|
||
2 Komponenten des ML
|
||
|
||
davon wird verwendet, um eine Hypothese durch Minimierung des Verlusts zu lernen und die andere wird für die endgültige Leistungsbewertung verwendet.
|
||
Zum Beispiel könnten wir in einem binären Klassifikationsproblem den logistischen Verlust verwenden, um (zu lernen) eine genaue Hypothese mit den Optimierungsmethoden in Kap. 4 zu suchen. Der logistische Verlust ist für diesen Zweck attraktiv, da er effiziente gradientenbasierte Methoden (siehe Kap. 5) zur Suche nach einer genauen Hypothese ermöglicht. Nachdem wir (gelernt haben) eine genaue Hypothese gefunden haben, verwenden wir den durchschnittlichen 0/1-Verlust für die endgültige Leistungsbewertung. Der 0/1-Verlust ist für diesen Zweck attraktiv, da er als Fehler- oder Fehlklassifikationsrate interpretiert werden kann. Die für die endgültige Leistungsbewertung einer gelernten Hypothese verwendete Verlustfunktion wird manchmal als Metrik bezeichnet.
|
||
|
||
2.3.1 Verlustfunktionen für numerische Labels
|
||
|
||
Für ML-Probleme, die Datenpunkte mit numerischen Labels y ∈ R betreffen, d. h. für Regressionsprobleme (siehe Abschn. 2.1.2), kann eine häufig verwendete (erste) Wahl für die Verlustfunktion der quadratische Fehlerverlust
|
||
|
||
L((x, y), h) := y − h(x) 2.
|
||
=yˆ
|
||
|
||
(2.8)
|
||
|
||
sein. Der quadratische Fehlerverlust (2.8) hängt von den Merkmalen x nur über den vorhergesagten Labelwert yˆ = h(x) ab. Wir können den quadratischen Fehlerverlust ausschließlich anhand der Vorhersage h(x) und dem wahren Labelwert y bewerten. Neben der Vorhersage h(x) sind keine weiteren Eigenschaften der Merkmale x erforderlich, um den quadratischen Fehlerverlust zu bestimmen. Wir werden die Notation etwas missbrauchen und die Abkürzung L(y, yˆ) für jede Verlustfunktion verwenden, die von den Merkmalen x nur über das vorhergesagte Label yˆ = h(x) abhängt. Abb. 2.13 zeigt den quadratischen Fehlerverlust als Funktion des Vorhersagefehlers y − yˆ.
|
||
Der quadratische Fehlerverlust (2.8) hat ansprechende rechnerische und statistische Eigenschaften. Für lineare Prädiktorkarten h(x) = wT x ist der quadratische Fehlerverlust eine konvexe und differenzierbare Funktion des Gewichtsvektors w. Dies ermöglicht wiederum eine effiziente Suche nach dem optimalen linearen Prädiktor mit Hilfe effizienter iterativer Optimierungsmethoden (siehe Kap. 5). Der quadratische Fehlerverlust hat auch eine nützliche Interpretation in Bezug auf ein probabilistisches Modell für die Merkmale und Labels. Die Minimierung des quadratischen Fehlerverlusts entspricht der MaximumLikelihood-Schätzung innerhalb eines linearen Gauß-Modells [28, Abschn. 2.6.3].
|
||
Eine andere in Regressionsproblemen verwendete Verlustfunktion ist der absolute Fehlerverlust |yˆ − y|. Die Verwendung dieser Verlustfunktion zur Steuerung des Lernens eines Prädiktors führt zu Methoden, die robust gegenüber
|
||
|
||
2.3 Der Verlust
|
||
|
||
45
|
||
|
||
quadratischer Fehlerverlust
|
||
|
||
Vorhersagefehler
|
||
Abb. 2.13 Eine häufig verwendete Wahl für die Verlustfunktion bei Regressionsproblemen (mit Datenpunkten, die numerische Labels haben) ist der quadratische Fehlerverlust (2.8). Beachten Sie, dass wir den quadratischen Fehlerverlust für eine gegebene Hypothese h nur bewerten können, wenn wir die Merkmale x und das Label y des Datenpunkts kennen
|
||
wenigen Ausreißern im Trainingsset sind (siehe Abschn. 3.3). Diese verbesserte Robustheit geht jedoch auf Kosten einer erhöhten rechnerischen Komplexität bei der Minimierung des (nicht differenzierbaren) absoluten Fehlerverlusts im Vergleich zum (differenzierbaren) quadratischen Fehlerverlust (2.8).
|
||
2.3.2 Verlustfunktionen für kategoriale Labels
|
||
Klassifikationsprobleme beinhalten Datenpunkte, deren Labels Werte aus einem diskreten Labelraum annehmen Y. Im Folgenden konzentrieren wir uns, sofern nicht anders angegeben, auf binäre Klassifikationsprobleme. Darüber hinaus nehmen wir ohne Einschränkung der Allgemeinheit an, dass die Labelwerte Y = {−1, 1} sind. Klassifikationsmethoden zielen darauf ab, einen Klassifikator zu lernen, der die Merkmale x eines Datenpunkts auf ein vorhergesagtes Label yˆ ∈ Y abbildet.
|
||
Wir implementieren einen Klassifikator, indem wir den Wert h(x) ∈ R einer Hypothese, die beliebige reale Zahlen liefern kann, schwellen. Dann klassifizieren wir einen Datenpunkt als yˆ = 1 wenn h(x) > 0 und yˆ = −1 sonst. Daher wird das vorhergesagte Label aus dem Vorzeichen des Werts h(x) ermittelt. Während das Vorzeichen von h(x) das Klassifikationsergebnis bestimmt, d. h., das vorhergesagte Label yˆ, interpretieren wir den absoluten Wert |h(x)| als das Vertrauen in diese Klassifikation.
|
||
Grundsätzlich können wir die Qualität einer Hypothese messen, wenn sie zur Klassifikation von Datenpunkten mit dem quadratischen Fehlerverlust (2.8) verwendet wird. Allerdings ist der quadratische Fehler typischerweise ein schlechtes Maß für die Qualität einer Hypothese h(x), die zur Klassifikation
|
||
|
||
46 Etikett
|
||
|
||
Prädiktor
|
||
|
||
2 Komponenten des ML
|
||
Prädiktor Merkmal
|
||
|
||
Abb. 2.14 Eine Trainingsmenge bestehend aus vier Datenpunkten mit binären Labels yˆ(i) ∈ {−1, 1}. Die Minimierung des quadratischen Fehlerverlusts (2.8) würde den (schlechten) Klassifikator h(1) dem (vernünftigen) Klassifikator h(2) vorziehen.
|
||
eines Datenpunkts mit binärem Label y ∈ {−1, 1} verwendet wird. Abb. 2.14 veranschaulicht, wie der quadratische Fehlerverlust einer Hypothese in einem binären Klassifikationsproblem irreführend sein kann.
|
||
Abb. 2.14 zeigt einen Datensatz, der aus m = 4 Datenpunkten mit binären Labels y(i) ∈ {−1, 1} besteht, für i = 1, . . . , m. Die Abbildung zeigt auch zwei Kandidatenhypothesen h(1)(x) und h(2)(x), die zur Klassifizierung von Datenpunkten verwendet werden können. Die Klassifikationen yˆ, die mit der Hypothese h(2)(x) erzielt wurden, würden perfekt zu den Labels der vier Trainingsdatenpunkte passen, da h(2) x(i) ≥ 0 wenn und nur wenn y(i) = 1. Im Gegensatz dazu sind die Klassifikationen yˆ(i), die durch Schwellenwertbildung von h(1)(x) erzielt wurden, falsch für Datenpunkte mit y = −1. Daher würden wir auf Basis der Trainingsdaten bevorzugen, h(2)(x) anstelle von h(1) zur Klassifizierung von Datenpunkten zu verwenden. Der quadratische Fehlerverlust, der durch den (vernünftigen) Klassifikator h(2) verursacht wird, ist jedoch viel größer als der quadratische Fehlerverlust, der durch den (schlechten) Klassifikator h(1) verursacht wird. Der quadratische Fehlerverlust ist typischerweise eine schlechte Wahl zur Beurteilung der Qualität einer Hypothesenkarte, die zur Klassifizierung von Datenpunkten in verschiedene Kategorien verwendet wird.
|
||
Im Allgemeinen möchten wir, dass die Verlustfunktion eine Hypothese bestraft (große Werte liefert für), die sehr zuversichtlich ist (|h(x)| ist groß) bei einer falschen Klassifizierung (yˆ �= y). Darüber hinaus sollte eine gute Verlustfunktion eine Hypothese nicht bestrafen (kleine Werte liefern für), die sehr zuversichtlich ist (|h(x)| ist groß) bei einer korrekten Klassifizierung (yˆ = y). Allerdings liefert der quadratische Verlust aufgrund seiner Definition große Werte, wenn das Vertrauen |h(x)| groß ist, unabhängig davon, ob die resultierende Klassifizierung korrekt oder falsch ist.
|
||
Wir diskutieren nun einige Verlustfunktionen, die sich als nützlich erwiesen haben, um die Qualität einer Hypothese zu bewerten, die zur Klassifizierung
|
||
|
||
2.3 Der Verlust
|
||
|
||
47
|
||
|
||
von Datenpunkten verwendet wird. Sofern nicht anders angegeben, gelten die Formeln für diese Verlustfunktionen nur, wenn die Labelwerte die reellen Zahlen −1 und 1 sind, d. h., wenn der Labelraum Y = {−1, 1} ist. Diese Formeln müssen entsprechend geändert werden, wenn man für ein binäres Klassifizierungsproblem andere Labelwerte bevorzugt. Zum Beispiel könnten wir anstelle des Labelraums Y = {−1, 1} genauso gut den Labelraum Y = {0, 1}, oder
|
||
verwenden. Die erste Verlustfunktion, die wir diskutieren, ist die direkte Formalisierung der natürlichen Anforderung, dass eine Hypothese zu korrekten Klassifikationen führen sollte, d. h., yˆ = y für jeden Datenpunkt. Dies legt nahe, eine Hypothese h(x) durch Minimierung des 0/1-Verlusts zu lernen
|
||
|
||
L((x, y), h) :=
|
||
|
||
1 0
|
||
|
||
wenn y �= yˆ sonst,
|
||
|
||
mit yˆ = 1 fu¨r h(x) ≥ 0, und yˆ = −1 fu¨r h(x) < 0.
|
||
|
||
(2.9)
|
||
|
||
Abb. 2.15 veranschaulicht den 0/1-Verlust (2.9) für einen Datenpunkt mit
|
||
|
||
Merkmalen x und Label y = 1 als Funktion des Hypothesenwerts h(x). Der
|
||
|
||
0/1-Verlust ist gleich null, wenn die Hypothese eine korrekte Klassifikation liefert
|
||
|
||
yˆ = y. Bei einer falschen Klassifikation yˆ �= y ergibt der 0/1-Verlust den Wert eins.
|
||
|
||
Der 0/1-Verlust (2.9) ist konzeptionell ansprechend, wenn Datenpunkte als
|
||
|
||
Realisierungen von i.i.d. Zufallsvariablen mit der gleichen Wahrscheinlichkeits-
|
||
|
||
verteilung
|
||
|
||
p(x, y) interpretiert
|
||
|
||
werden.
|
||
|
||
Gegeben
|
||
|
||
m
|
||
|
||
Realisierungen
|
||
|
||
(x(i), y(i))
|
||
|
||
m i=1
|
||
|
||
solcher i.i.d. Zufallsvariablen,
|
||
|
||
m
|
||
(1/m) L((x(i), y(i)), h) ≈ p(y �= yˆ)
|
||
i=1
|
||
|
||
(2.10)
|
||
|
||
mit hoher Wahrscheinlichkeit für ausreichend große Stichprobengröße m. Eine
|
||
genaue Formulierung der Approximation (2.10) kann aus dem Gesetz der großen
|
||
Verlust
|
||
|
||
sehr zuversichtlich bei
|
||
|
||
sehr zuversichtlich bei
|
||
|
||
Verlust (für
|
||
|
||
Scharnierverlust (für
|
||
quadratischer Fehler (für
|
||
|
||
logistischer Verlust (für Hypothese
|
||
|
||
Abb. 2.15 Die festen Kurven stellen drei weit verbreitete Verlustfunktionen für binäre Klassifikationsprobleme dar. Ein Datenpunkt wird als yˆ = 1 klassifiziert, wenn h(x) ≥ 0 und als yˆ = −1 klassifiziert, wenn h(x) < 0. Wir können den absoluten Wert |h(x)| als das Vertrauen in die Klassifikation interpretieren. Je sicherer wir uns bei einer korrekten Klassifikation (yˆ = 1) sind, d. h., je positiver h(x), desto kleiner ist der Verlust. Beachten Sie, dass jede der drei Verlustfunktionen für binäre Klassifikation monoton auf 0 zustrebt, wenn h(x) zunimmt. Die gestrichelte Kurve stellt den quadratischen Fehlerverlust (2.8) dar, der für zunehmendes h(x) zunimmt.
|
||
|
||
48
|
||
|
||
2 Komponenten des ML
|
||
|
||
Zahlen [18, Abschn. 1] abgeleitet werden. Wir können das Gesetz der großen Zahlen anwenden, da die Verlustwerte L((x(i), y(i)), h) Realisierungen von i.i.d. Zufallsvariablen sind. Der durchschnittliche 0/1-Verlust auf der linken Seite von (2.10) wird als die Genauigkeit der Hypothese h bezeichnet.
|
||
In Anbetracht von (2.10) scheint der 0/1-Verlust eine sehr natürliche Wahl zur Beurteilung der Qualität eines Klassifikators zu sein, wenn unser Ziel darin besteht, eine korrekte Klassifikation durchzusetzen (yˆ = y). Diese ansprechende statistische Eigenschaft des 0/1-Verlusts geht jedoch mit einer hohen Rechenkomplexität einher. Tatsächlich ist der 0/1-Verlust (2.9) für einen gegebenen Datenpunkt (x, y) weder konvex noch differenzierbar, wenn er als Funktion des Klassifikators h betrachtet wird. Daher erfordert die Verwendung des 0/1-Verlusts für binäre Klassifikationsprobleme in der Regel fortgeschrittene Optimierungsmethoden zur Lösung des resultierenden Lernproblems (siehe Abschn. 3.8).
|
||
Um die Nicht-Konvexität des 0/1-Verlusts zu vermeiden, können wir ihn durch eine konvexe Verlustfunktion approximieren. Eine beliebte konvexe Approximation des 0/1-Verlusts ist der hinge Verlust
|
||
|
||
L((x, y), h) := max{0, 1 − y · h(x)}.
|
||
|
||
(2.11)
|
||
|
||
Abb. 2.15 zeigt den Hinge-Verlust (2.11) als Funktion der Hypothese h(x). Während der Hinge-Verlust die Nicht-Konvexität des 0/1-Verlusts vermeidet, ist er dennoch eine nicht differenzierbare Funktion des Klassifikators h. Nicht differenzierbare Verlustfunktionen sind in der Regel schwieriger zu minimieren, was auf eine höhere Rechenkomplexität der ML-Methode hinweist, die einen solchen Verlust verwendet.
|
||
Abschn. 3.6 diskutiert den logistischen Verlust, der eine differenzierbare Verlustfunktion ist, die für Klassifikationsprobleme nützlich ist. Der logistische Verlust
|
||
|
||
L((x, y), h) := log(1 + exp(−yh(x))),
|
||
|
||
(2.12)
|
||
|
||
wird in der logistischen Regression verwendet, um die Nützlichkeit einer linearen Hypothese h(x) = wT x zu messen.
|
||
Betrachten Sie einen spezifischen Datenpunkt mit dem Merkmalsvektor x ∈ Rn und einem binären Label y ∈ {−1, 1}. Wir verwenden eine lineare Hypothese h(w)(x) = wT x, mit einem bestimmten Gewichtsvektor w ∈ Rn, um das Label basierend auf den Merkmalen x gemäß yˆ = 1 vorherzusagen, wenn h(w)(x) = wT x > 0 und yˆ = −1 sonst. Dann sind sowohl der Hinge-Verlust (2.11) als auch der logistische Verlust (2.12) konvexe Funktionen des Gewichtsvektors w ∈ Rn. Der logistische Verlust (2.12) hängt stetig von w ab. Es handelt sich um eine differenzierbare Funktion im Sinne der Definition eines Gradienten in Bezug auf w. Im Gegensatz dazu ist der Hinge-Verlust (2.11) nicht glatt, was seine Minimierung schwieriger macht [29, Kap. 3].
|
||
ML-Methoden, die die konvexe und differenzierbare logistische Verlustfunktion verwenden, wie die logistische Regression in Abschn. 3.6, können einfache gradientenbasierte Methoden wie den Gradientenabstieg (GD) anwenden, um den durchschnittlichen Verlust zu minimieren (siehe Kap. 5). Im Gegensatz dazu
|
||
|
||
2.3 Der Verlust
|
||
|
||
49
|
||
|
||
können wir gradientenbasierte Methoden nicht verwenden, um den Hinge-Verlust zu minimieren, da er nicht differenzierbar ist. Wir können jedoch eine Verallgemeinerung von GD anwenden, die als Subgradientenabstieg bekannt ist [30] Der Subgradientenabstieg wird aus GD gewonnen, indem das Konzept eines Gradienten auf das eines Subgradienten verallgemeinert wird.
|
||
|
||
2.3.3 Verlustfunktionen für ordinale Labelwerte
|
||
|
||
Es gibt auch Verlustfunktionen, die besonders gut für die Vorhersage von ordinalen Labelwerten geeignet sind (siehe Abschn. 2.1). Betrachten Sie Datenpunkte, die Flächenbilder von rechteckigen Bereichen der Größe 1 km mal 1 km darstellen. Wir charakterisieren jeden Datenpunkt (rechteckiger Bereich) durch den Merkmalsvektor x, der durch Stapeln der RGB-Werte jedes Bildpixels erzeugt wird (siehe Abb. 2.4). Neben dem Merkmalsvektor wird jeder rechteckige Bereich durch ein Label y ∈ {1, 2, 3} charakterisiert, wobei
|
||
|
||
• y = 1 bedeutet, dass das Gebiet keine Bäume enthält. • y = 2 bedeutet, dass das Gebiet teilweise von Bäumen bedeckt ist. • y = 3 bedeutet, dass das Gebiet vollständig von Bäumen bedeckt ist.
|
||
|
||
So könnten wir sagen, dass der Labelwert y = 2 „größer“ ist als der Labelwert
|
||
y = 1 und der Labelwert y = 3 „größer“ ist als der Labelwert y = 2. Es könnte
|
||
nützlich sein, die Reihenfolge der Labelwerte zu berücksichtigen, wenn die Quali-
|
||
tät der Vorhersagen bewertet wird, die durch eine Hypothese h(x) erzielt werden.
|
||
Betrachten Sie einen Datenpunkt mit Merkmalsvektor x und Label y = 1 sowie zwei verschiedene Hypothesen h(a), h(b) ∈ H. Die Hypothese h(a) liefert das vorhergesagte Label yˆ(a) = h(a)(x) = 2, während die andere Hypothese h(b) das vorhergesagte Label yˆ(a) = h(a)(x) = 3 liefert. Beide Vorhersagen sind falsch, da
|
||
sie sich vom wahren Labelwert y = 1 unterscheiden. Es scheint vernünftig, die Vorhersage yˆ(a) als weniger falsch zu betrachten als die Vorhersage yˆ(b) und daher würden wir die Hypothese h(a) gegenüber h(b) bevorzugen. Der 0/1-Verlust ist jedoch für h(a) und h(b) gleich und spiegelt daher nicht unsere Präferenz für h(a) wider. Wir müssen den 0/1-Verlust modifizieren (oder anpassen), um die
|
||
anwendungsspezifische Ordnung der Labelwerte zu berücksichtigen. Für die oben
|
||
genannte Anwendung könnten wir eine Verlustfunktion definieren über
|
||
|
||
0 , als y = h(x) L((x, y), h) := 10 , als |y − h(x)| = 1 100 ansonsten.
|
||
|
||
(2.13)
|
||
|
||
50
|
||
2.3.4 Empirisches Risiko
|
||
|
||
2 Komponenten des ML
|
||
|
||
Die grundlegende Idee von ML-Methoden (einschließlich der in Kap. 3 diskutierten) besteht darin, eine Hypothese (aus einem gegebenen Hypothesenraum H) zu finden (oder zu lernen), die bei Anwendung auf beliebige Datenpunkte einen minimalen Verlust verursacht. Um dieses informelle Ziel präzise zu machen, müssen wir spezifizieren, was wir unter „beliebiger Datenpunkt“ verstehen. Einer der erfolgreichsten Ansätze zur Definition des Begriffs „beliebiger Datenpunkt“ besteht in probabilistischen Modellen für die beobachteten Datenpunkte.
|
||
Das grundlegendste und am weitesten verbreitete probabilistische Modell interpretiert Datenpunkte x(i), y(i) als Realisierungen von i.i.d. Zufallsvariablen mit einer gemeinsamen Wahrscheinlichkeitsverteilung p(x, y). Angesichts eines solchen probabilistischen Modells scheint es natürlich, die Qualität einer Hypothese anhand des erwarteten Verlusts oder des Bayes-Risikos [15]
|
||
|
||
ˆ
|
||
E L((x, y), h)} := L((x, y), h)dp(x, y).
|
||
x,y
|
||
|
||
(2.14)
|
||
|
||
zu messen. Das Bayes-Risiko ist der erwartete Wert des Verlusts L((x, y), h), der entsteht, wenn die Hypothese h auf (die Realisierung von) einen zufälligen Datenpunkt mit Merkmalen x und Label y angewendet wird. Beachten Sie, dass die Berechnung des Bayes-Risikos (2.15) die gemeinsame Wahrscheinlichkeitsverteilung p(x, y) der (zufälligen) Merkmale und des Labels von Datenpunkten erfordert.
|
||
Das Bayes-Risiko scheint eine vernünftige Leistungsmessung für eine Hypothese h zu sein. Tatsächlich ist das Bayes-Risiko einer Hypothese nur dann klein, wenn die Hypothese im Durchschnitt einen geringen Verlust für Datenpunkte verursacht, die aus der Wahrscheinlichkeitsverteilung p(x, y) gezogen werden. Es kann jedoch herausfordernd sein zu überprüfen, ob die in einem bestimmten Anwendungsbereich generierten Datenpunkte genau als Realisierungen (Ziehungen) aus einer Wahrscheinlichkeitsverteilung p(x, y) modelliert werden können. Darüber hinaus ist es oft auch der Fall, dass wir die korrekte Wahrscheinlichkeitsverteilung p(x, y) nicht kennen.
|
||
Gehen wir für den Moment davon aus, dass Datenpunkte als i.i.d. Realisierungen einer gemeinsamen Wahrscheinlichkeitsverteilung p(x, y) erzeugt werden, die bekannt ist. Es scheint vernünftig, eine Hypothese h∗ zu lernen, die das minimale Bayes-Risiko verursacht,
|
||
|
||
E L((x, y), h∗)} := min E L((x, y), h)}.
|
||
h∈H
|
||
|
||
(2.15)
|
||
|
||
Eine Hypothese, die (2.15) löst, d. h., die das minimal mögliche Bayes-Risiko erreicht, wird als Bayes-Schätzer bezeichnet [15, Kap. 4]. Die Hauptrechenherausforderung beim Lernen der optimalen Hypothese ist die effiziente (numerische) Lösung des Optimierungsproblems (2.15). Effiziente Methoden zur Lösung des
|
||
|
||
2.3 Der Verlust
|
||
|
||
51
|
||
|
||
Optimierungsproblems (2.15) werden innerhalb der Schätzungstheorie untersucht [15 , 31].
|
||
Der Fokus dieses Buches liegt auf ML-Methoden, die keine Kenntnis der zugrunde liegenden Wahrscheinlichkeitsverteilung p(x, y) erfordern. Eines der am häufigsten verwendeten Prinzipien für diese ML-Methoden besteht darin, das Bayes-Risiko durch einen empirischen (Stichproben-) Durchschnitt über eine endliche Menge von gelabelten Daten D = x(1), y(1) , . . . , x(m), y(m) zu approximieren. Insbesondere definieren wir das empirische Risiko einer Hypothese h ∈ H für einen Datensatz D als
|
||
|
||
m
|
||
L(h|D) = (1/m) L((x(i), y(i)), h).
|
||
i=1
|
||
|
||
(2.16)
|
||
|
||
Das empirische Risiko der Hypothese h ∈ H ist der durchschnittliche Verlust an den Datenpunkten in D. Um die Notationslast zu erleichtern, verwenden wir L(h) als Abkürzung für L(h|D) wenn der zugrunde liegende Datensatz D aus dem Kontext klar ist. Beachten Sie, dass das empirische Risiko im Allgemeinen sowohl von der Hypothese h als auch von den (Merkmale und Labels der) Datenpunkten im Datensatz D abhängt.
|
||
Wenn die Datenpunkte, die zur Berechnung des empirischen Risikos (2.16) verwendet werden, Realisierungen von i.i.d. Zufallsvariablen sind (als solche modelliert werden können), deren gemeinsame Verteilung p(x, y) ist, sagen uns grundlegende Ergebnisse der Wahrscheinlichkeitstheorie, dass
|
||
|
||
m
|
||
E L((x, y), h)} ≈ (1/m) L((x(i), y(i)), h) bei ausreichend großem Stichprobenumfang m.
|
||
i=1
|
||
(2.17)
|
||
Der Approximationsfehler in (2.17) kann genau durch einige der grundlegendsten Ergebnisse der Wahrscheinlichkeitstheorie quantifiziert werden. Diese Ergebnisse werden als das Gesetz der großen Zahlen bezeichnet.
|
||
Viele (wenn nicht die meisten) ML-Methoden sind motiviert durch (2.17), was darauf hindeutet, dass eine Hypothese mit kleinem empirischen Risiko (2.16) auch zu einem kleinen erwarteten Verlust führen wird. Der minimal mögliche erwartete Verlust wird durch den Bayes-Schätzer des Labels y, gegeben die Merkmale x, erreicht. Um jedoch den optimalen Schätzer tatsächlich zu berechnen, müssten wir die (gemeinsame) Wahrscheinlichkeitsverteilung p(x, y) der Merkmale x und des Labels y kennen.
|
||
|
||
2.3.4.1 Verwirrungsmatrix
|
||
Betrachten Sie einen Datensatz D mit Datenpunkten, die durch Merkmalsvektoren x(i) und Labels y(i) ∈ {1, . . . , k} gekennzeichnet sind. Wir könnten den Labelwert eines Datenpunkts als den Index einer Kategorie oder Klasse interpretieren, zu der
|
||
|
||
52
|
||
|
||
2 Komponenten des ML
|
||
|
||
der Datenpunkt gehört. Multiklassen-Klassifikationsprobleme zielen darauf ab, eine Hypothese h zu lernen, so dass h(x) ≈ y für jeden Datenpunkt gilt.
|
||
Im Prinzip könnten wir die Qualität einer gegebenen Hypothese h durch den durchschnittlichen 0/1-Verlust messen, der bei den gelabelten Datenpunkten in (dem Trainingsset) D anfällt. Wenn der Datensatz D jedoch hauptsächlich Datenpunkte mit einem bestimmten Labelwert enthält, könnte der durchschnittliche 0/1-Verlust die Leistung von h für Datenpunkte mit einem der seltenen Labelwerte verschleiern. Tatsächlich könnte die Hypothese selbst bei einem sehr kleinen durchschnittlichen 0/1-Verlust schlecht für Datenpunkte einer Minderheitskategorie abschneiden.
|
||
Die Verwirrung Matrix verallgemeinert das Konzept des 0/1-Verlusts auf Anwendungsdomänen, in denen die relative Häufigkeit (Fraktion) von Datenpunkten mit einem bestimmten Labelwert erheblich variiert (unausgeglichene Daten). Anstatt nur den durchschnittlichen 0/1-Verlust zu betrachten, den eine Hypothese auf einem Datensatz D verursacht, verwenden wir eine ganze Familie von Verlustfunktionen. Insbesondere definieren wir für jedes Paar von Labelwerten p, q ∈ {1, . . . , k} den Verlust
|
||
|
||
L(p→q) x, y , h :=
|
||
|
||
1 wenn y = p und h(x) = q 0 ansonsten.
|
||
|
||
(2.18)
|
||
|
||
Wir berechnen dann den durchschnittlichen Verlust (2.18) auf dem Datensatz D ,
|
||
m
|
||
L(p→q)(h|D) := (1/m) L(p→q) (x(i), y(i)), h fu¨r p, q ∈ {1, . . . , k}. (2.19)
|
||
i=1
|
||
Es ist praktisch, die Werte (2.19) als Matrix zu arrangieren, die als Verwirrungsmatrix bezeichnet wird. Die Zeilen einer Verwirrungsmatrix entsprechen verschiedenen Labelwerten p von Datenpunkten. Die Spalten einer Verwirrungsmatrix entsprechen verschiedenen Werten q, die von der Hypothese h(x) geliefert werden. Der (p, q)-te Eintrag der Verwirrungsmatrix ist L(p→q)(h|D).
|
||
|
||
2.3.4.2 Präzision, Abruf und F-Maß
|
||
|
||
Betrachten Sie eine Objekterkennungsanwendung, bei der Datenpunkte Bilder darstellen. Das Label der Datenpunkte könnte die Anwesenheit (y = 1) oder Abwesenheit (y = −1) eines Objekts anzeigen, es ist dann üblich, die [32]
|
||
|
||
Abruf := L(1→1)(h|D), und die Genauigkeit :=
|
||
|
||
L(1→1)(h|D) .
|
||
|
||
L(1→1)(h|D) + L(−1→1)(h|D)
|
||
|
||
(2.20)
|
||
|
||
Offensichtlich möchten wir eine Hypothese mit sowohl großem Abruf als auch großer Präzision finden. Diese beiden Ziele stehen jedoch typischerweise im
|
||
|
||
2.3 Der Verlust
|
||
|
||
53
|
||
|
||
Konflikt, eine Hypothese mit hohem Abruf wird eine geringe Präzision haben. Je nach Anwendung könnten wir es vorziehen, einen hohen Abruf zu haben und eine geringere Präzision zu tolerieren.
|
||
Es könnte praktisch sein, den Abruf und die Präzision einer Hypothese in eine einzige Größe zu kombinieren,
|
||
|
||
Pra¨zision · Abruf F1 := 2 · Pra¨zision + Abruf
|
||
|
||
(2.21)
|
||
|
||
Das F-Maß (2.21) ist das harmonische Mittel [33] der Präzision und des Abrufs einer Hypothese h. Es ist ein Spezialfall des Fβ -Scores
|
||
|
||
Fβ :=
|
||
|
||
1 + β2
|
||
|
||
Pra¨zision · Abruf
|
||
|
||
·
|
||
|
||
β2
|
||
|
||
Pra¨zision +
|
||
|
||
. Abruf
|
||
|
||
(2.22)
|
||
|
||
Das F-Maß (2.21) wird aus (2.22) für die Wahl β = 1 ermittelt. Es ist daher üblich, auf (2.21) als den F1-Score einer Hypothese h zu verweisen.
|
||
|
||
2.3.5 Bereuen
|
||
In einigen ML-Anwendungen haben wir möglicherweise Zugang zu den Vorhersagen, die von einigen Referenzmethoden oder Experten erhalten wurden. Die Qualität einer Hypothese h kann dann über die Differenz zwischen dem Verlust, der durch ihre Vorhersagen h(x) und dem Verlust, der durch die Vorhersagen der Experten [34] entsteht, gemessen werden. Diese Differenz, die als Bereuen bezeichnet wird, misst, wie sehr wir es bereuen, die Vorhersage h(x) anstelle der (folgenden) Vorhersage des Experten verwendet zu haben. Das Ziel der Bereuungsminimierung besteht darin, eine Hypothese zu lernen, die im Vergleich zu allen betrachteten Experten ein geringes Bereuen aufweist.
|
||
Das Konzept der Bereuungsminimierung ist nützlich, wenn wir keine probabilistischen Annahmen (siehe Abschn. 2.1.4) über die Daten machen. Ohne ein probabilistisches Modell können wir das Bayes-Risiko, das das Risiko des Bayes-Schätzers ist, nicht als Benchmark verwenden.
|
||
Techniken zur Bereuungsminimierung können entworfen und analysiert werden, ohne dass ein solches probabilistisches Modell für die Daten vorliegt [35]. Dieser Ansatz ersetzt das Bayes-Risiko durch das Bereuen im Verhältnis zu gegebenen Referenzvorhersagern (Experten) als Benchmark.
|
||
|
||
2.3.6 Belohnungen als Teilrückmeldungen
|
||
Einige Anwendungen beinhalten Datenpunkte, deren Labels so schwierig oder kostspielig zu bestimmen sind, dass wir nicht davon ausgehen können, überhaupt gelabelte Daten zur Verfügung zu haben. Ohne gelabelte Daten können wir die
|
||
|
||
54
|
||
|
||
2 Komponenten des ML
|
||
|
||
Verlustfunktion für verschiedene Hypothesenoptionen nicht bewerten. Tatsächlich kommt die Bewertung der Verlustfunktion in der Regel darauf an, den Abstand zwischen vorhergesagtem Label und wahrem Label eines Datenpunkts zu messen. Anstatt eine Verlustfunktion zu bewerten, müssen wir uns auf eine indirekte Rückmeldung oder „Belohnung“ verlassen, die die Nützlichkeit einer bestimmten Vorhersage anzeigt [35, 36].
|
||
Betrachten Sie das ML-Problem der Vorhersage der optimalen Lenkrichtungen für ein autonomes Auto. Die Vorhersage muss für jeden neuen Zustand des Autos neu berechnet werden. ML-Methoden können den Zustand über einen Merkmalsvektor x erfassen, dessen Einträge die Pixelintensitäten eines Schnappschusses sind. Das Ziel ist es, eine Hypothesenkarte von dem Merkmalsvektor x zu einer Vermutung yˆ = h(x) für die optimale Lenkrichtung y (wahres Label) zu lernen. Es sei denn, das Auto fährt in einem kleinen Bereich mit festen Hindernissen herum, haben wir keinen Zugang zu gelabelten Datenpunkten oder Referenzfahrtszenen, für die wir bereits die optimale Lenkrichtung kennen. Stattdessen muss das Auto (Steuergerät) die Hypothese h(x) ausschließlich auf der Grundlage der Rückmeldesignale lernen, die von verschiedenen Sensoren (Kameras, Abstandssensoren) erhalten werden.
|
||
|
||
2.4 Die Teile zusammenfügen
|
||
|
||
Das Hauptthema des Buches ist, dass ML-Methoden durch verschiedene Kombinationen von Daten, Modell und Verlust erzielt werden. Wir werden einige Schlüsselprinzipien hinter diesen Kombinaten in den folgenden Kapiteln ausführlich diskutieren. Lassen Sie uns ein Gefühl dafür entwickeln, wie ML-Methoden funktionieren, indem wir ein sehr einfaches ML-Problem betrachten. Dieses Problem beinhaltet Datenpunkte, die durch ein einziges numerisches Merkmal x ∈ R und ein numerisches Label y ∈ R gekennzeichnet sind. Wir gehen davon aus, dass wir Zugang zu m gelabelten Datenpunkten
|
||
|
||
x(1), y(1) , . . . , x(m), y(m)
|
||
|
||
(2.23)
|
||
|
||
haben, für die wir die wahren Labelwerte y(i) kennen. Die Annahme, die genauen wahren Labelwerte y(i) für jeden Datenpunkt zu
|
||
kennen, ist eine Idealisierung. Wir könnten oft mit Etikettierungs- oder Messfehlern konfrontiert sein, so dass die beobachteten Labels verrauschte Versionen des wahren Labels sind. Später werden wir Techniken diskutieren, die es MLMethoden ermöglichen, mit verrauschten Labels in Kap. 7 umzugehen.
|
||
Unser Ziel ist es, eine (Hypothese) Karte h : R → R zu lernen, so dass h(x) ≈ y für jeden Datenpunkt gilt. Mit anderen Worten, gegeben einen beliebigen Datenpunkt mit Merkmal x, sollte der Funktionswert h(x) eine genaue Annäherung an seinen Label-Wert y sein. Wir verlangen, dass die Karte zur Hypothesenraum H der linearen Karten gehört,
|
||
|
||
2.4 Die Teile zusammenfügen
|
||
Abb. 2.16 Wir können die Qualität eines bestimmten Prädiktors h ∈ H messen, indem wir den Vorhersagefehler y − h(x) für einen beschrifteten Datenpunkt (x, y) ermitteln.
|
||
|
||
Etikett y
|
||
|
||
55 Merkmal x
|
||
|
||
h(w0,w1)(x) = w1x + w0.
|
||
|
||
(2.24)
|
||
|
||
Der Prädiktor (2.24) ist durch die Steigung w1 und den Schnittpunkt (Bias oder Offset) w0 parametrisiert. Wir kennzeichnen dies durch die Notation h(w0,w1).
|
||
Eine bestimmte Wahl für die Gewichte w1, w0 definiert eine lineare Hypothese h(w0,w1)(x) = w1x + w0.
|
||
Lassen Sie uns die lineare Hypothesenkarte h(w0,w1)(x) verwenden, um die
|
||
Labels der Trainingsdatenpunkte vorherzusagen. Im Allgemeinen werden die Vorhersagen yˆ(i) = h(w0,w1) x(i) nicht perfekt sein und einen nicht-null Vorhersage Fehler yˆ(i) − y(i) verursachen (siehe Abb. 2.16).
|
||
Wir messen die Güte der Vorhersagekarte h(w0,w1) mit Hilfe des durchschnitt-
|
||
lichen quadratischen Fehlerverlusts (siehe (2.8))
|
||
|
||
m
|
||
|
||
f (w0, w1) := (1/m)
|
||
|
||
y(i) − h(w0,w1)(x(i)) 2
|
||
|
||
i=1
|
||
|
||
m
|
||
|
||
(2=.24)(1/m)
|
||
|
||
y(i) − (w1x(i) + w0) 2.
|
||
|
||
i=1
|
||
|
||
(2.25)
|
||
|
||
Der Trainingsfehler f (w0, w1) ist der Durchschnitt der quadratischen Vorhersagefehler, die durch den Vorhersager h(w0,w1)(x) bei den beschrifteten Datenpunkten
|
||
verursacht werden (2.23).
|
||
Es scheint natürlich, einen guten Vorhersager (2.24) zu erlernen, indem man die Gewichte w0, w1 so wählt, dass der Trainingsfehler minimiert wird
|
||
|
||
m
|
||
|
||
min f (w0, w1)(2=.25) min (1/m)
|
||
|
||
y(i) − (w1x(i) + w0) 2.
|
||
|
||
w0 ,w1 ∈R
|
||
|
||
w1 ,w0 ∈R
|
||
|
||
i=1
|
||
|
||
(2.26)
|
||
|
||
Die optimalen Gewichte w0′ , w1′ sind durch die Null-Gradienten-Bedingung gekennzeichnet,2
|
||
|
||
2Eine notwendige und hinreichende Bedingung dafür, dass w′ eine konvexe differenzierbare Funktion f (w) minimiert, ist ∇f (w′) = 0 [37, Abschn. 4.2.3].
|
||
|
||
56
|
||
|
||
2 Komponenten des ML
|
||
|
||
∂f (w0′ , w1′ ) = 0, und ∂f (w0′ , w1′ ) = 0.
|
||
|
||
∂ w0
|
||
|
||
∂ w1
|
||
|
||
(2.27)
|
||
|
||
Wenn man (2.25) in (2.27) einsetzt und grundlegende Regeln für die Berechnung von Ableitungen verwendet, erhält man die folgenden Optimalitätsbedingungen
|
||
|
||
m
|
||
(1/m)
|
||
i=1
|
||
|
||
y(i) − (w1′ x(i) + w0′ )
|
||
|
||
m
|
||
= 0, und (1/m) x(i) y(i) − (w1′ x(i) + w0′ ) = 0.
|
||
i=1
|
||
(2.28)
|
||
|
||
Alle Gewichte w0′ , w1′, die (2.28) erfüllen, definieren einen Prädiktor h(w0′ ,w1′ ) = w1′ x + w0′ , der im Sinne eines minimalen Trainingsfehlers optimal ist,
|
||
|
||
f
|
||
|
||
(w0′ ,
|
||
|
||
w1′ )
|
||
|
||
=
|
||
|
||
min
|
||
w0 ,w1 ∈R
|
||
|
||
f
|
||
|
||
(w0,
|
||
|
||
w1).
|
||
|
||
Wir finden es praktisch, die Optimalitätsbedingung (2.28) mit Matrizen und Vektoren neu zu formulieren. Zu diesem Zweck schreiben wir den Prädiktor (2.24) zunächst um als
|
||
|
||
h(x) = wT x mit w = w0, w1 T , x = 1, x T .
|
||
Lassen Sie uns die Merkmalsvektoren x(i) = 1, x(i) T und Labels y(i) der Trainingsdatenpunkte (2.23) in die Merkmalsmatrix und den Labelvektor,
|
||
|
||
X = x(1), . . . , x(m) T ∈ Rm×2, y = y(1), . . . , y(m) T ∈ Rm.
|
||
|
||
(2.29)
|
||
|
||
Dann können wir (2.28) umformulieren als
|
||
|
||
XT y − Xw′ = 0.
|
||
|
||
(2.30)
|
||
|
||
Die Einträge eines beliebigen Gewichtsvektors w′ = w0′ , w1′ , der (2.30) erfüllt, sind Lösungen für (2.28).
|
||
|
||
2.5 Übungen
|
||
Übung 2.1 Perfekte Vorhersage Betrachten Sie Datenpunkte, die durch ein einzelnes numerisches Merkmal x ∈ R und ein numerisches Label y ∈ R gekennzeichnet sind. Wir verwenden eine ML-Methode, um eine Hypothesenkarte h : R → R basierend auf einem Trainingssatz zu lernen, der aus drei Datenpunkten besteht
|
||
(x(1) = 1, y(1) = 3), (x(2) = 4, y(2) = −1), (x(3) = 1, y(3) = 5).
|
||
|
||
2.5 Übungen
|
||
|
||
57
|
||
|
||
Gibt es eine Chance, dass die ML-Methode eine Hypothesenkarte lernt, die perfekt zu den Trainingsdatenpunkten passt, so dass h x(i) = y(i) für i = 1, . . . , 3. Hinweis: Versuchen Sie, die Datenpunkte in einem Streudiagramm und verschiedene Hypothesenkarten zu visualisieren (siehe Abb. 1.3).
|
||
Übung 2.2 Temperaturdaten Betrachten Sie einen Datensatz von täglichen Lufttemperaturen x(1), . . . , x(m) gemessen an der Beobachtungsstation Utsjoki Nuorgam zwischen dem 01.12.2019 und dem 29.02.2020. Daher ist x(1) die täglich gemessene Temperatur am 01.12.2019, x(2) ist die täglich gemessene Temperatur am 02.12.2019, und x(m) ist die täglich gemessene Temperatur am 29.02.2020. Sie können diesen Datensatz von dem Link https://en.ilmatieteenlaitos.fi/downloadobservations herunterladen. ML-Methoden bestimmen oft wenige Parameter, um große Mengen von Datenpunkten zu charakterisieren. Berechnen Sie für den oben genannten Temperaturmessdatensatz die folgenden Parameter
|
||
• das Minimum A := mini=1,...,m x(i) • das Maximum B := maxi=1,...,m x(i) • den Durchschnitt C := (1/m) i=1,...,m x(i) • die Standardabweichung D := (1/m) i=1,...,m x(i) − C 2
|
||
Übung 2.3 Deep Learning auf Raspberry PI Betrachten Sie den kleinen Desktop-Computer „RaspberryPI“ ausgestattet mit insgesamt 8 Gigabyte Speicher [38]. Auf diesem Computer möchten wir einen ML-Algorithmus implementieren, der eine Hypothesenkarte lernt, die durch ein tiefes neuronales Netzwerk mit n = 106 numerischen Gewichten (oder Parametern) dargestellt wird. Jedes Gewicht wird mit 8 Bits quantisiert (= 1 Byte). Wie viele verschiedene Hypothesen können wir höchstens auf einem RaspberryPI-Computer speichern? (Sie können annehmen, dass 1 Gigabyte = 109 Bytes.)
|
||
Übung 2.4 Ensembles. Für einige Anwendungen kann es eine gute Idee sein, nicht eine einzelne Hypothese zu lernen, sondern ein ganzes Ensemble von Hypothesenkarten h(1), . . . , h(B). Diese Hypothesen könnten sogar zu verschiedenen Hypothesenräumen gehören, h(1) ∈ H(1), . . . , h(B) ∈ H(B). Diese Hypothesenräume können beliebig sein, außer dass sie für denselben Merkmalsraum und Labelraum definiert sind. Gegeben ein solches Ensemble können wir eine neue („Meta“) Hypothese h˜ konstruieren, indem wir die einzelnen Vorhersagen, die aus jeder Hypothese gewonnen wurden, kombinieren (oder aggregieren),
|
||
|
||
h˜(x) := a h(1)(x), . . . , h(B)(x) .
|
||
|
||
(2.31)
|
||
|
||
Hier bezeichnet a(·) eine gegebene (feste) Kombinations- oder Aggregations-
|
||
|
||
funktion. Ein Beispiel für eine solche Aggregationsfunktion ist der Durch-
|
||
|
||
schnitt a h(1)(x), . . . , h(B)(x) := (1/B)
|
||
|
||
B b=1
|
||
|
||
h(b)
|
||
|
||
(x).
|
||
|
||
Wir
|
||
|
||
erhalten
|
||
|
||
einen
|
||
|
||
neuen
|
||
|
||
„Meta“-Hypothesenraum H, der aus allen Hypothesen der Form (2.31)
|
||
|
||
mit h(1) ∈ H(1), . . . , h(B) ∈ H(B) besteht. Welche Bedingungen an die
|
||
|
||
58
|
||
|
||
2 Komponenten des ML
|
||
|
||
Aggregationsfunktion a(·) und die einzelnen Hypothesenräume H(1), . . . , H(B)
|
||
stellen sicher, dass H jeden einzelnen Hypothesenraum enthält, d. h., H(1), . . . , H(B) ⊆ H.
|
||
|
||
Übung 2.5 Wie viele Merkmale? Betrachten Sie das ML-Problem, das einer Musikinformationsabruf-App für Smartphones zugrunde liegt [39]. Eine solche App zielt darauf ab, einen Songtitel anhand einer kurzen Audioaufnahme einer Songinterpretation zu identifizieren. Hier repräsentiert der Merkmalsvektor x das abgetastete Audiosignal und das Label y ist ein bestimmter Songtitel aus einer riesigen Musikdatenbank. Wie lang ist der Merkmalsvektor n des Merkmalsvektors x ∈ Rn, wenn seine Einträge die Signalamplituden einer 20-sekündigen Aufnahme sind, die mit einer Rate von 44 kHz abgetastet wird?
|
||
|
||
Übung 2.6 Multilabel-Prognose. Betrachten Sie Datenpunkte, die durch einen Merkmalsvektor x ∈ R10 und ein vektorwertiges Label y ∈ R30 gekennzeichnet sind. Solche vektorwertigen Labels treten in Multilabel-Klassifikationsproblemen auf. Wir möchten den Label-Vektor mit einer linearen Vorhersagekarte vorhersagen
|
||
|
||
h(x) = Wx mit irgendeiner Matrix W ∈ R30×10.
|
||
|
||
(2.32)
|
||
|
||
Wie viele verschiedene lineare Vorhersager (2.32) gibt es? 10, 30, 40 oder unendlich?
|
||
|
||
Übung 2.7 Durchschnittlicher quadratischer Fehlerverlust als
|
||
quadratische Form Betrachten Sie den Hypothesenraum, der aus allen linearen Abbildungen h(x) = wT x mit einem bestimmten Gewichtsvektor w ∈ Rn besteht. Wir versuchen, die beste lineare Abbildung zu finden, indem
|
||
wir den durchschnittlichen quadratischen Fehlerverlust (das empirische
|
||
Risiko) minimieren, der bei beschrifteten Datenpunkten (Trainingsset) anfällt (x(1), y(1)), (x(2), y(2)), . . . , (x(m), y(m)). Ist es möglich, das resultierende empirische Risiko als konvexe quadratische Funktion darzustellen f (w) = wT Cw + bw + c? Wenn dies möglich ist, wie sind die Matrix C, der Vektor b und die Konstante c in
|
||
Bezug auf die Merkmalsvektoren und Labels der Trainingsdaten?
|
||
|
||
Übung 2.8 Finden Sie beschriftete Daten für das gegebene empirische Risiko.
|
||
Betrachten Sie den linearen Hypothesenraum, der aus linearen Abbildungen h(w)(x) = wT x besteht, die durch einen Gewichtsvektor w parametrisiert sind.
|
||
Wir lernen einen optimalen Gewichtsvektor, indem wir den durchschnittlichen quadratischen Fehlerverlust f (w) = L h(w)|D minimieren, der durch h(w)(x) auf dem Trainingssatz D = x(1), y(1) , . . . , x(m), y(m) verursacht wird. Ist es möglich, den Datensatz D nur aus der Kenntnis der Funktion f (w) zu rekonstruieren?
|
||
Ist die resultierende beschriftete Trainingsdaten eindeutig oder gibt es ver-
|
||
schiedene Trainingssätze, die zur gleichen empirischen Risikofunktion geführt haben könnten? Hinweis: Schreiben Sie den Trainingsfehler f (w) in der Form f (w) = wT Qw + c + bT w mit einer Matrix Q, Vektor b und Skalar c, der von den
|
||
Merkmalen und Beschriftungen der Trainingsdatenpunkte abhängen könnte.
|
||
|
||
2.5 Übungen
|
||
|
||
59
|
||
|
||
Übung 2.9 Dummy-Merkmal anstelle von Intercept Zeigen Sie, dass jede Hypothesenkarte der Form h(x) = w1x + w0 als Verkettung einer Merkmalskarte
|
||
: x �→ z mit einer Karte h˜(z) := wT z mit einem Gewichtsvektor w ∈ R2 erhalten werden kann.
|
||
Übung 2.10 Näherungsweise nichtlineare Abbildungen mit Indikatorfunktionen für Merkmalsabbildungen. Betrachten Sie eine ML-Anwendung, die Datenpunkte erzeugt, die durch ein skalares Merkmal x ∈ R und numerisches Label y ∈ R gekennzeichnet sind. Wir konstruieren eine nichtlineare Abbildung, indem wir das Merkmal x zuerst in einen neuen Merkmalsvektor z = (φ1(x), φ2(x), φ3(x), φ4(x)) transformieren. Die Komponenten φ1(x), . . . , φ4(x) sind Indikatorfunktionen von Intervallen [−10, −5), [−5, 0), [0, 5), [5, 10]. Insbesondere gilt φ1(x) = 1 für x ∈ [−10, −5) und φ1(x) = 0 sonst. Wir konstruieren einen Hypothesenraum H1 durch alle Abbildungen der Form wT z. Beachten Sie, dass die Abbildung eine Funktion des Merkmals x ist, da der Merkmalsvektor z eine Funktion von x ist. Welche der folgenden Prädiktorabbildungen gehören zu H1?
|
||
|
||
Übung 2.11 Python Hypothesenraum. Betrachten Sie die untenstehenden Quellcodes für fünf verschiedene Python-Funktionen, die das numerische Merkmal x einlesen, einige Berechnungen durchführen, die zu einer Vorhersage yˆ führen. Wie groß ist der Hypothesenraum, der durch alle Abbildungen gebildet wird, die durch eine dieser Python-Funktionen dargestellt werden können?
|
||
|
||
60
|
||
|
||
2 Komponenten des ML
|
||
|
||
Übung 2.12 Viele Merkmale Ein wichtiges Anwendungsgebiet für MLMethoden ist das Gesundheitswesen. Hier repräsentieren Datenpunkte menschliche Patienten, die durch Gesundheitsakten charakterisiert sind. Diese Akten können physiologische Parameter, CT-Scans sowie verschiedene Diagnosen von Gesundheitsfachleuten enthalten. Ist es eine gute Idee, jedes Datenfeld einer Gesundheitsakte als Merkmale des Datenpunkts zu verwenden?
|
||
Übung 2.13 Über-Parametrisierung Betrachten Sie Datenpunkte, die durch Merkmalsvektoren x ∈ R2 und ein numerisches Label y ∈ R charakterisiert sind. Wir möchten den besten Prädiktor aus dem Hypothesenraum
|
||
|
||
H = h(x) = xT Aw : w ∈ S}.
|
||
|
||
Hier haben wir die Matrix A =
|
||
|
||
1 −1
|
||
|
||
−1 1
|
||
|
||
und die Menge
|
||
|
||
S = (1, 1)T , (2, 2)T , (−1, 3)T , (0, 4)T ⊆ R2.
|
||
Was ist die Kardinalität des Hypothesenraums H, d. h., wie viele verschiedene Prädiktorabbildungen enthält H?
|
||
Übung 2.14 Quadratischer Fehlerverlust Betrachten Sie einen Hypothesenraum H, der aus drei Prädiktoren h(1)(·), h(2)(·), h(3)(·) besteht. Jeder Prädiktor h(j)(x) ist eine reellwertige Funktion eines reellwertigen Arguments x. Darüber hinaus gilt für jedes j ∈ {1, 2, 3} , h(j)(x) = 0 für alle x2 ≤ j und h(j)(x) = j sonst. Können Sie sagen, welche dieser Hypothesen im Sinne des kleinsten durchschnittlichen quadratischen Fehlerverlusts auf den drei (Trainings-)Datenpunkten (x = 1/10, y = 3), (0, 0) und (1, −1) optimal ist?
|
||
Übung 2.15 Klassifikationsverlust Die Abb. 2.15 zeigt verschiedene Verlustfunktionen für einen festen Datenpunkt mit dem Label y = 1 und variierender Hypothese h ∈ H. Wie würde Abb. 2.15 sich ändern, wenn wir die gleichen Verlustfunktionen für einen anderen Datenpunkt z = (x, y) mit dem Label y = −1 bewerten?
|
||
Übung 2.16 Intercept Term Lineare Regressionsmethoden modellieren die Beziehung zwischen dem Label y und dem Merkmal x eines Datenpunkts als y = h(x) + e mit einem kleinen additiven Term e. Es wird angenommen, dass die Vorhersagekarte h(x) linear ist h(x) = w1x + w0. Das Gewicht w0 wird manchmal als Intercept (oder Bias) Term bezeichnet. Angenommen, wir kennen für eine gegebene lineare Vorhersagekarte ihre Werte h (x) für x = 1 und x = 3. Können Sie die Gewichte w1 und w0 basierend auf h(1) und h(3) bestimmen?
|
||
Übung 2.17 Bildklassifikation Betrachten Sie eine riesige Sammlung von Outdoor-Bildern, die Sie auf Ihrer letzten Abenteuerreise aufgenommen haben. Sie möchten diese Bilder in drei Kategorien (oder Klassen) Hund, Vogel und Fisch organisieren. Wie könnten Sie diese Aufgabe als ML-Problem formalisieren?
|
||
|
||
Literatur
|
||
|
||
61
|
||
|
||
Übung 2.18 Maximaler Hypothesenraum Betrachten Sie Datenpunkte, die durch ein einziges reellwertiges Merkmal x und ein einziges reellwertiges Label y charakterisiert sind. Wie groß ist der größtmögliche Hypothesenraum von Vorhersagekarten h(x), die den Merkmalswert eines Datenpunkts einlesen und eine reellwertige Vorhersage yˆ = h(x) liefern?
|
||
Übung 2.19 Ein großer, aber endlicher Hypothesenraum Betrachten Sie Datenpunkte, deren Merkmale 10 × 10 Schwarz-Weiß (bw) Pixelbilder sind. Jeder Datenpunkt ist auch durch ein binäres Label y ∈ {0, 1} gekennzeichnet. Betrachten Sie den Hypothesenraum, der aus allen Abbildungen besteht, die ein bw-Bild als Eingabe nehmen und eine Vorhersage für das Label liefern. Wie groß ist dieser Hypothesenraum?
|
||
Übung 2.20 Größe des linearen Hypothesenraums Betrachten Sie einen Trainingsdatensatz von m Datenpunkten mit Merkmalsvektoren x(i) ∈ Rn und numerischen Labels y(1), . . . , y(m). Die Merkmalsvektoren und Labelwerte des Trainingsdatensatzes sind beliebig, außer dass wir annehmen, dass die Merkmalsmatrix X = x(1), . . . vollen Rang hat. Welche Bedingung an m und n garantiert, dass wir einen linearen Prädiktor h(x) = wT x finden können, der den Trainingsdatensatz perfekt anpasst, d. h., y(1) = h x(1) , . . . , y(m) = h x(m) .
|
||
|
||
Literatur
|
||
1. K. Abayomi, A. Gelman, M.A. Levy, Diagnostics for multivariate imputations. Journal of The Royal Statistical Society Series C-applied Statistics 57, 273–291 (2008)
|
||
2. W. Rudin, Principles of Mathematical Analysis, 3. Aufl. (McGraw-Hill, New York, 1976) 3. P. Bühlmann, S. van de Geer, Statistics for High-Dimensional Data (Springer, New York,
|
||
2011) 4. M. Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint (Cambridge
|
||
University Press, Cambridge, 2019) 5. R. Vidal, Subspace clustering. IEEE Signal Processing Magazine, March 2011 6. F. Barata, K. Kipfer, M. Weber, P. Tinschert, E. Fleisch, und T. Kowatsch, Towards device-
|
||
agnostic mobile cough detection with convolutional neural networks, in 2019 IEEE International Conference on Healthcare Informatics (ICHI), S. 1–11 (IEEE, New York, 2019) 7. B. Boashash (Hrsg.), Time Frequency Signal Analysis and Processing: A Comprehensive Reference (Elsevier, Amsterdam, The Netherlands, 2003) 8. S.G. Mallat, A Wavelet Tour of Signal Processing - The Sparse Way, 3. Aufl. (Academic Press, San Diego, CA, 2009) 9. S. Smoliski, K. Radtke, Spatial prediction of demersal fish diversity in the Baltic sea: comparison of machine learning and regression-based techniques. ICES Journal of Marine Science 74(1), 102–111 (2017) 10. S. Carrazza, Machine learning challenges in theoretical HEP (2018) 11. M. Gao, H. Igata, A. Takeuchi, K. Sato, Y. Ikegaya, Machine learning-based prediction of adverse drug effects: An example of seizure-inducing compounds. Journal of Pharmacological Sciences 133(2), 70–78 (2017)
|
||
|
||
62
|
||
|
||
2 Komponenten des ML
|
||
|
||
12. K. Mortensen, T. Hughes, Comparing amazon’s mechanical Turk platform to conventional data collection methods in the health and medical research literature. J. Gen. Intern Med. 33(4), 533–538 (2018)
|
||
13. A. Halevy, P. Norvig, F. Pereira, The unreasonable effectiveness of data (IEEE Intelligent Systems, New York, 2009)
|
||
14. P. Koehn, Europarl: A parallel corpus for statistical machine translation, in The 10th Machine Translation Summit, S. 79–86 (AAMT, 2005)
|
||
15. E.L. Lehmann, G. Casella, Theory of Point Estimation, 2. Aufl. (Springer, New York, 1998) 16. S.M. Kay, Fundamentals of Statistical Signal Processing: Estimation Theory (Prentice Hall,
|
||
Englewood Cliffs, NJ, 1993) 17. D. Bertsekas, J. Tsitsiklis, Introduction to Probability, 2. Aufl. (Athena Scientific, Singapore,
|
||
2008) 18. P. Billingsley, Probability and Measure, 3. Aufl. (Wiley, New York, 1995) 19. C.M. Bishop, Pattern Recognition and Machine Learning (Springer, Berlin, 2006) 20. H. Lütkepohl, New Introduction to Multiple Time Series Analysis (Springer, New York, 2005) 21. B. Efron, R. Tibshirani, Improvements on cross-validation: The 632+ bootstrap method.
|
||
Journal of the American Statistical Association 92(438), 548–560 (1997) 22. P. Halmos, Naive Set Theory (Springer, Berlin, 1974) 23. P. Austin, P. Kaski, und K. Kubjas, Tensor network complexity of multilinear maps (2018) 24. F. Pedregosa, Scikit-learn: Machine learning in python. Journal of Machine Learning
|
||
Research 12(85), 2825–2830 (2011) 25. I. Goodfellow, Y. Bengio, A. Courville, Deep Learning (MIT Press, Cambridge, 2016) 26. V.N. Vapnik, The Nature of Statistical Learning Theory (Springer, Berlin, 1999) 27. S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning-From Theory to
|
||
Algorithms (Cambridge University Press, New York, 2014) 28. T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning Springer Series in
|
||
Statistics. (Springer, New York, 2001) 29. Y. Nesterov, Introductory Lectures on Convex Optimization, Vol. 87 of Applied Optimization
|
||
(Kluwer Academic Publishers, Boston, 2004) 30. S. Bubeck, Convex optimization: Algorithms and complexity. Foundations and Trends in
|
||
Machine Learning 8(3–4), 231–357 (2015) 31. M.J. Wainwright, M.I. Jordan, Graphical Models, Exponential Families, and Variational
|
||
Inference, Foundations and Trends in Machine Learning, Bd. 1 (Now Publishers, Hanover, MA, 2008) 32. R. Baeza-Yates, B. Ribeiro-Neto, Modern Information Retrieval (ACM Press, New York, 1999) 33. M. Abramowitz, I.A. Stegun (Hrsg.), Handbook of Mathematical Functions (Dover, New York, 1965) 34. E. Hazan, Introduction to Online Convex Optimization (Now Publishers Inc., Hanover, MA, 2016) 35. N. Cesa-Bianchi, G. Lugosi, Prediction, Learning, and Games (Cambridge University Press, New York, 2006) 36. R. Sutton, A. Barto, Reinforcement Learning: An Introduction, 2. Aufl. (MIT Press, Cambridge, MA, 2018) 37. S. Boyd, L. Vandenberghe, Convex Optimization (Cambridge University Press, Cambridge, UK, 2004) 38. O. Dürr, Y. Pauchard, D. Browarnik, R. Axthelm, und M. Loeser. Deep learning on a raspberry pi for real time face recognition (2015) 39. A. Wang, An industrial-strength audio search algorithm, in International Symposium on Music Information Retrieval (2003)
|
||
|
||
Kapitel 3
|
||
Die Landschaft des ML
|
||
|
||
Wie in Kap. 2 besprochen, kombinieren ML-Methoden drei Hauptkomponenten:
|
||
• einen Satz von Datenpunkten, die durch Merkmale und Labels charakterisiert sind
|
||
• ein Modell oder Hypothesenraum H, der aus verschiedenen Hypothesen h ∈ H besteht.
|
||
• eine Verlustfunktion zur Messung der Qualität einer bestimmten Hypothese h.
|
||
Jede dieser drei Komponenten beinhaltet Designentscheidungen für die Darstellung von Daten, deren Merkmale und Labels, das Modell und die Verlustfunktion. Dieses Kapitel beschreibt die auf hoher Ebene verwendeten Designentscheidungen einiger der beliebtesten ML-Methoden. Abb. 3.1 stellt diese ML-Methoden in einer zweidimensionalen Ebene dar, deren horizontale Achsen verschiedene Hypothesenräume und die vertikale Achse verschiedene Verlustfunktionen repräsentiert.
|
||
Um eine praktische ML-Methode zu erhalten, müssen wir auch die oben genannten Komponenten kombinieren. Das grundlegende Prinzip jeder MLMethode besteht darin, das Modell nach einer Hypothese zu durchsuchen, die den geringsten Verlust bei jedem Datenpunkt verursacht. Kap. 4 wird dann eine prinzipielle Methode diskutieren, um diese informelle Aussage in tatsächliche ML-Algorithmen umzuwandeln, die auf einem Computer implementiert werden könnten.
|
||
|
||
3.1 Lineare Regression
|
||
Betrachten Sie Datenpunkte, die durch Merkmalsvektoren x ∈ Rn und numerische Labels y ∈ R gekennzeichnet sind. Die lineare Regression zielt darauf ab, eine Hypothese aus dem linearen Hypothesenraum
|
||
H(n) := {h(w) : Rn → R : h(w)(x) = wT x mit einem Gewichtsvektor w ∈ Rn}. (3.1)
|
||
|
||
© Der/die Autor(en), exklusiv lizenziert an Springer Nature Singapore Pte Ltd. 2024
|
||
|
||
63
|
||
|
||
A. Jung, Maschinelles Lernen, https://doi.org/10.1007/978-981-99-7972-1_3
|
||
|
||
64
|
||
Verlustfunktion
|
||
|
||
0/1 Verlust
|
||
|
||
Ziff. 3.8
|
||
|
||
3 Die Landschaft des ML
|
||
Ziff. 3.10 Ziff. 3.13
|
||
|
||
Bedauern
|
||
|
||
Ziff. 3.15
|
||
|
||
Ziff. 3.11
|
||
|
||
Scharnier verlust
|
||
|
||
Ziff. 3.7
|
||
|
||
Ziff. 3.9
|
||
|
||
logistischer Verlust
|
||
|
||
Ziff. 3.6
|
||
|
||
Ziff. 3.9
|
||
|
||
Ziff. 3.11
|
||
|
||
regularisierter quadratischer
|
||
Fehler
|
||
quadratischer Fehler
|
||
absoluter Verlust
|
||
|
||
Ziff. 3.4
|
||
|
||
Ziff. 3.9
|
||
|
||
Ziff. 3.1
|
||
|
||
Ziff. 3.2 Ziff. 3.5 Ziff. 3.9
|
||
|
||
Ziff. 3.3
|
||
lineare Karten
|
||
|
||
aufgerüstet linear Karten (2.7)
|
||
|
||
Ziff. 3.10 Ziff. 3.13
|
||
stückweise Konstante
|
||
|
||
Modell
|
||
|
||
Abb. 3.1 ML-Methoden passen ein Modell an Daten an, indem sie eine Verlustfunktion minimieren. Verschiedene ML-Methoden verwenden unterschiedliche Designentscheidungen für Daten, Modell und Verlust
|
||
|
||
zu lernen. Abb. 1.3 zeigt die Graphen einiger Abbildungen aus H(2) für Datenpunkte mit Merkmalsvektoren der Form x = (1, x)T. Die Qualität eines bestimmten Prädiktors h(w) wird durch den quadratischen Fehlerverlust gemessen (2.8). Mit beschrifteten Daten D = {(x(i), y(i))}mi=1 lernt die lineare Regression einen Prädiktor hˆ, der den durchschnittlichen quadratischen Fehlerverlust
|
||
minimiert, oder den mittleren quadratischen Fehler, (siehe 2.8))
|
||
|
||
m
|
||
hˆ = argmin L(h|D)(2=.16) argmin(1/m) (y(i) − h(x(i)))2.
|
||
|
||
h∈H(n)
|
||
|
||
h∈H(n)
|
||
|
||
i=1
|
||
|
||
(3.2)
|
||
|
||
Da der Hypothesenraum H(n) durch den Gewichtsvektor w parametrisiert ist (siehe (3.1)), können wir (3.2) als Optimierungsproblem direkt über den Gewichtsvektor w umschreiben:
|
||
|
||
m
|
||
|
||
w = argmin(1/m) (y(i) − h(w)(x(i)))2
|
||
|
||
w∈Rn
|
||
|
||
i=1
|
||
|
||
m
|
||
h(w)(x=)=wT x argmin(1/m) (y(i) − wT x(i))2.
|
||
|
||
w∈Rn
|
||
|
||
i=1
|
||
|
||
(3.3)
|
||
|
||
3.2 Polynomiale Regression
|
||
|
||
Abb. 3.2 Ein
|
||
|
||
Streudiagramm, das einige Datenpunkte (x(1), y(1)), . . . ,
|
||
|
||
darstellt. Der ite Datenpunkt
|
||
|
||
,
|
||
|
||
wird durch einen Punkt
|
||
|
||
Etikett
|
||
|
||
dargestellt, dessen
|
||
|
||
,
|
||
|
||
Koordinaten das Merkmal
|
||
|
||
x(i) und das Label y(i) dieses
|
||
|
||
Datenpunkts sind
|
||
|
||
,
|
||
|
||
,
|
||
|
||
65
|
||
|
||
,
|
||
|
||
,
|
||
|
||
,
|
||
|
||
,
|
||
|
||
Merkmal
|
||
|
||
Die Optimierungsprobleme (3.2) und (3.3) sind im folgenden Sinne äquivalent: Jeder optimale Gewichtsvektor w, der (3.3) löst, kann verwendet werden, um einen optimalen Prädiktor hˆ, der (3.2) löst, über hˆ(x) = h(w)(x) = w T x zu konstruieren.
|
||
|
||
3.2 Polynomiale Regression
|
||
|
||
Betrachten Sie ein ML-Problem, das Datenpunkte beinhaltet, die durch ein einzelnes numerisches Merkmal x ∈ R gekennzeichnet sind (der Merkmalsraum ist X = R) und einem numerischen Label y ∈ R (der Labelraum ist Y = R). Wir beobachten eine Reihe von gelabelten Datenpunkten, die in Abb. 3.2 dargestellt sind.
|
||
Abb. 3.2 deutet darauf hin, dass die Beziehung x → y zwischen Merkmal x und Label y stark nicht-linear ist. Für solche nicht-linearen Beziehungen zwischen Merkmalen und Labels ist es nützlich, einen Hypothesenraum zu betrachten, der aus polynomialen Abbildungen besteht
|
||
|
||
n
|
||
Hp(no)ly = {h(w) : R → R : h(w)(x) = wr xr−1, mit einigen w = (w1, . . . , wn)T ∈ Rn}.
|
||
r=1
|
||
(3.4)
|
||
|
||
Wir können jede nicht-lineare Beziehung y = h(x) mit jeder gewünschten Genauig-
|
||
|
||
keit approximieren, indem wir ein Polynom
|
||
|
||
n r=1
|
||
|
||
wr xr−1
|
||
|
||
von
|
||
|
||
ausreichend
|
||
|
||
hohem
|
||
|
||
Grad n verwenden.1
|
||
|
||
1Die genaue Formulierung dieser Aussage ist als „Stone-Weierstrass Theorem“ bekannt [1, Thm. 7.26].
|
||
|
||
66
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
Für die lineare Regression (siehe Abschn. 3.1) messen wir die Qualität eines Prädiktors anhand des quadratischen Fehlerverlusts (2.8). Basierend auf beschrifteten Datenpunkten D = {(x(i), y(i))}mi=1, die jeweils ein skalares Merkmal x(i) und ein Label y(i) haben, minimiert die Polynom-Regression den durchschnittlichen quadratischen Fehlerverlust (siehe (2.8)):
|
||
|
||
m
|
||
|
||
min (1/m) (y(i) − h(w)(x(i)))2.
|
||
|
||
h∈H(pno)ly
|
||
|
||
i=1
|
||
|
||
(3.5)
|
||
|
||
Es ist üblich, den durchschnittlichen quadratischen Fehlerverlust auch als
|
||
den mittleren quadratischen Fehler zu bezeichnen.
|
||
Wir können die Polynomregression als Kombination einer Merkmalsabbildung
|
||
(Transformation) (siehe Abschn. 2.1.1) und der linearen Regression (siehe Abschn. 3.1) interpretieren. Tatsächlich wird jeder polynomiale Prädiktor h(w) ∈ Hp(no)ly als Verkettung der Merkmalsabbildung
|
||
|
||
�(x) → (1, x, . . . , xn)T ∈ Rn+1 mit einer linearen Abbildung h˜(w) : Rn+1 → R : x �→ wT x erzielt, d.h.,
|
||
|
||
(3.6)
|
||
|
||
h(w)(x) = h˜(w)(�(x)).
|
||
|
||
(3.7)
|
||
|
||
Daher können wir die Polynomregression implementieren, indem wir zuerst die Merkmalsabbildung (siehe (3.6)) auf die skalaren Merkmale x(i) anwenden, was
|
||
zu den transformierten Merkmalsvektoren führt
|
||
|
||
x(i) = � x(i) = 1, x(i), . . . , x(i) n−1 T ∈ Rn,
|
||
|
||
(3.8)
|
||
|
||
und dann die lineare Regression (siehe Abschn. 3.1) auf diese neuen Merkmalsvektoren anwenden.
|
||
Indem wir (3.7) in (3.5) einsetzen, erhalten wir ein lineares Regressionsproblem (3.3) mit Merkmalsvektoren (3.8). Daher ist ein Prädiktor h(w) ∈ Hp(no)ly eine nichtlineare Funktion h(w)(x) des ursprünglichen Merkmals x, aber eine lineare Funktion h˜(w)(x) = wT x (siehe (3.7)), der transformierten Merkmale x (3.8).
|
||
|
||
3.3 Regression der kleinsten absoluten Abweichung
|
||
Das Erlernen eines linearen Prädiktors durch Minimierung des durchschnittlichen quadratischen Fehlerverlusts, der bei Trainingsdaten anfällt, ist nicht robust gegenüber der Anwesenheit von Ausreißern. Diese Empfindlichkeit gegenüber Ausreißern ist in den Eigenschaften des quadratischen Fehlerverlusts (y − h(x))2 verwurzelt. Die Minimierung des durchschnittlichen quadratischen Fehlers zwingt den resultierenden Prädiktor yˆ dazu, nicht zu weit von irgendeinem Datenpunkt entfernt zu sein. Es könnte jedoch nützlich sein, einen großen Vorhersagefehler
|
||
|
||
3.3 Regression der kleinsten absoluten Abweichung
|
||
|
||
67
|
||
|
||
y − h(x) für einen ungewöhnlichen oder außergewöhnlichen Datenpunkt zu tolerieren, der als Ausreißer betrachtet werden kann.
|
||
Der Austausch des quadratischen Verlusts durch eine andere Verlustfunktion kann das Lernen gegenüber Ausreißern robust machen. Ein wichtiges Beispiel für eine solche „robustifizierende“ Verlustfunktion ist der Huber-Verlust [2]
|
||
|
||
L( x, y , h) =
|
||
|
||
(1/2)(y − h(x))2 fu¨r |y − h(x)| ≤ ε ε(|y − h(x)| − ε/2) sonst.
|
||
|
||
(3.9)
|
||
|
||
Abb. 3.3 zeigt den Huber-Verlust als Funktion des Vorhersagefehlers y − h(x). Die Huber-Verlustdefinition (3.9) enthält einen Abstimmungsparameter ǫ. Der
|
||
Wert dieses Abstimmungsparameters definiert, wann ein Datenpunkt als Ausreißer betrachtet wird. Abb. 3.4 veranschaulicht die Rolle dieses Parameters als die Breite eines Bandes um eine Hypothesenkarte. Der Vorhersagefehler dieser Hypothesenkarte für Datenpunkte innerhalb dieses Bandes wird mit quadratischem Fehlerverlust gemessen (2.8). Für Datenpunkte außerhalb dieses Bandes (Ausreißer) verwenden wir stattdessen den absoluten Wert des Vorhersagefehlers als resultierenden Verlust.
|
||
Der Huber-Verlust ist robust gegenüber Ausreißern, da die entsprechenden (großen) Vorhersagefehler y − yˆ nicht quadriert werden. Ausreißer haben einen kleineren Einfluss auf den durchschnittlichen Huber-Verlust (über den gesamten Datensatz) im Vergleich zum durchschnittlichen quadratischen Fehlerverlust. Die verbesserte Robustheit des Huber-Verlusts gegenüber Ausreißern geht auf Kosten
|
||
|
||
Abb. 3.3 Der HuberVerlust (3.9) ähnelt dem quadratischen Fehlerverlust (2.8) bei kleinem Vorhersagefehler und dem absoluten Differenzverlust bei größeren Vorhersagefehlern
|
||
|
||
absoluter Fehlerverlust Vorhersagefehler quadratischer Fehlerverlust
|
||
|
||
Abb. 3.4 Der Huber-Verlust misst Vorhersagefehler über den quadratischen Fehlerverlust für reguläre Datenpunkte innerhalb des Bandes der Breite ε um die Hypothesenkarte h(x) und über den absoluten Differenzverlust für einen Ausreißer außerhalb des Bandes
|
||
|
||
"Ausreißer"
|
||
|
||
68
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
einer erhöhten Rechenkomplexität. Der quadratische Fehlerverlust kann mit effizienten gradientenbasierten Methoden minimiert werden (siehe Kap. 5). Im Gegensatz dazu ist der Huber-Verlust für ε = 0 nicht differenzierbar und erfordert fortgeschrittenere Optimierungsmethoden.
|
||
Der Huber-Verlust (3.9) enthält zwei wichtige Spezialfälle. Der erste Spezialfall tritt auf, wenn ε sehr groß gewählt wird, so dass die Bedingung |y − yˆ| ≤ ε für die meisten Datenpunkte erfüllt ist. In diesem Fall ähnelt der Huber-Verlust dem quadratischen Fehlerverlust (2.8) (bis auf einen Skalierungsfaktor 1/2). Der zweite Spezialfall ergibt sich für ε = 0. In diesem Fall reduziert sich der Huber-Verlust auf den skalierten absoluten Differenzverlust |y − yˆ|.
|
||
|
||
3.4 Das Lasso
|
||
|
||
Wir werden in Kap. 6 sehen, dass die lineare Regression (siehe Abschn. 3.1) in der Regel einen größeren Trainingsdatensatz benötigt als die Anzahl der Merkmale, die zur Charakterisierung eines Datenpunkts verwendet werden. Allerdings erzeugen viele wichtige Anwendungsbereiche Datenpunkte mit einer Anzahl n von Merkmalen, die deutlich höher ist als die Anzahl m der verfügbaren beschrifteten Datenpunkte im Trainingsdatensatz. In diesem hochdimensionalen Regime, in dem m ≪ n gilt, wird die einfache lineare Regression nicht in der Lage sein, nützliche Gewichte w für eine lineare Hypothese zu lernen.
|
||
Abschn. 6.4 zeigt, dass die lineare Regression für m ≪ n in der Regel eine Hypothese lernt, die die Labels der Datenpunkte im Trainingsdatensatz perfekt vorhersagt, aber schlechte Vorhersagen für Datenpunkte außerhalb des Trainingsdatensatzes liefert. Dieses Phänomen wird als Overfitting bezeichnet und stellt eine Hauptherausforderung für ML-Anwendungen im hochdimensionalen Regime dar.
|
||
Kap. 7 diskutiert grundlegende Regularisierungstechniken, die es ermöglichen, ML-Methoden vor Overfitting zu schützen. Wir können die lineare Regression regularisieren, indem wir den quadratischen Fehlerverlust (2.8) einer Hypothese h(w)(x) = wT x mit einem zusätzlichen Strafterm ergänzen. Dieser Strafterm hängt ausschließlich von den Gewichten w ab und dient als Schätzung für die Zunahme des durchschnittlichen Verlusts bei Datenpunkten außerhalb des Trainingssets. Unterschiedliche ML-Methoden ergeben sich aus unterschiedlichen Auswahlmöglichkeiten für diesen Strafterm. Der Least Absolute Shrinkage and Selection Operator (Lasso) wird aus der linearen Regression erhalten, indem der quadratische Fehlerverlust durch den regularisierten Verlust
|
||
|
||
L((x, y), h(w)) = (y − wT x)2 + �w�1.
|
||
|
||
(3.10)
|
||
|
||
ersetzt wird. Hier wird der Strafterm durch die skalierte Norm w 1 gegeben. Der Wert von kann auf der Grundlage eines probabilistischen Modells gewählt werden, das einen Datenpunkt als Realisierung einer Zufallsvariablen interpretiert.
|
||
|
||
3.5 Gaußsche Basis Regression
|
||
|
||
69
|
||
|
||
Das Label dieses zufälligen Datenpunkts steht in Beziehung zu seinen Merkmalen über
|
||
y = wT x + ε.
|
||
Hier bezeichnet w einen wahren zugrunde liegenden Gewichtsvektor und ε ist eine Realisierung einer Zufallsvariablen, die unabhängig von den Merkmalen x ist. Wir benötigen den „Rausch“-Term ε, da die Labels von Datenpunkten, die in einer ML-Anwendung gesammelt werden, typischerweise nicht genau durch eine lineare Kombination wT x ihrer Merkmale erzielt werden.
|
||
Die Abstimmung von in (3.10) kann durch die statistischen Eigenschaften (wie die Varianz) des Rauschens ε, der Anzahl der Nicht-Null-Einträge in w und einer unteren Grenze für die Nicht-Null-Werte [3, 4] geleitet werden. Eine weitere Option zur Auswahl des Wertes besteht darin, verschiedene Kandidatenwerte auszuprobieren und denjenigen auszuwählen, der den kleinsten Validierungsfehler ergibt (siehe Abschn. 6.2).
|
||
|
||
3.5 Gaußsche Basis Regression
|
||
|
||
Abschn. 3.2 zeigte, wie man die lineare Regression erweitern kann, indem man zuerst das Merkmal x mit einer vektorwertigen Merkmalsabbildung : R → Rn transformiert. Die Ausgabe dieser Merkmalsabbildung sind die transformierten Merkmale �(x), die wiederum an eine lineare Abbildung h �(x) = wT �(x) gefüttert werden. Die Polynom-Regression in Abschn. 3.2 wurde für die spezifische Merkmalsabbildung (3.6) erhalten, deren Einträge die Potenzen xl des skalaren ursprünglichen Merkmals x sind. Es ist jedoch möglich, andere Funktionen, die sich von Polynomen unterscheiden, zur Konstruktion der Merkmalsabbildung zu verwenden. Wir können die lineare Regression mit einer beliebigen Merkmalsabbildung erweitern
|
||
|
||
�(x) = (φ1(x), . . . , φn(x))T
|
||
|
||
(3.11)
|
||
|
||
mit den skalaren Abbildungen φj : R → R, die als Basisfunktionen bezeichnet werden. Die Wahl der Basisfunktionen hängt stark von der speziellen Anwendung und der zugrunde liegenden Beziehung zwischen Merkmalen und Labels der beobachteten Datenpunkte ab. Die Basisfunktionen, die der Polynom-Regression zugrunde liegen, sind φj(x) = xj.
|
||
Eine weitere beliebte Wahl für die Basisfunktionen sind „Gaussians“
|
||
|
||
φσ,µ(x) = exp(−(1/(2σ 2))(x−µ)2).
|
||
|
||
(3.12)
|
||
|
||
Die Familie (3.12) von Abbildungen ist parametrisiert durch die Varianz σ 2
|
||
|
||
und den Mittelwert (Verschiebung) µ. Wir erhalten Gaussian basis lineare Regression durch Kombination der Merkmalsabbildung
|
||
|
||
�(x) = φσ1,µ1 (x), . . . , φσn,µn (x) T
|
||
|
||
(3.13)
|
||
|
||
70
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
mit
|
||
|
||
Gauß
|
||
|
||
Abb. 3.5 Die wahre Beziehung x → y (blau) zwischen Merkmal x und Label y der Datenpunkte ist stark nicht-linear. Daher scheint es sinnvoll, das Label mit einer nicht-linearen Hypothesenkarte h(w)(x) ∈ HG(2a)uss mit einem bestimmten Gewichtsvektor w ∈ R2 vorherzusagen.
|
||
|
||
mit linearer Regression (siehe Abb. 3.5). Der resultierende Hypothesenraum ist dann
|
||
|
||
n
|
||
HG(na)uss = {h(w) : R → R : h(w)(x) = wjφσj,µj (x)
|
||
j=1
|
||
|
||
(3.14)
|
||
|
||
mit Gewichten w = (w1, . . . , wn)T ∈ Rn}.
|
||
|
||
Unterschiedliche Wahlmöglichkeiten für die Varianz σ 2 und Verschiebungen µj der Gaußschen Funktion in (3.12) führen zu unterschiedlichen Hypothesenräumen
|
||
HGauss. Abschn. 6.3 wird Modellauswahltechniken diskutieren, die es ermöglichen, nützliche Werte für diese Parameter zu finden.
|
||
Die Hypothesen von (3.14) sind durch einen Gewichtsvektor w ∈ Rn para-
|
||
metrisiert. Jede Hypothese in HGauss entspricht einer bestimmten Wahl für den Gewichtsvektor w. Daher können wir anstatt über HGauss zu suchen, um eine gute Hypothese zu finden, über Rn suchen.
|
||
|
||
3.6 Logistische Regression
|
||
Die logistische Regression ist eine Methode zur Klassifizierung von Datenpunkten, die durch Merkmalsvektoren x ∈ Rn (Merkmalsraum X = Rn) nach zwei Kategorien klassifiziert, die durch ein Label y kodiert sind. Es wird bequem sein, den Labelraum Y = R zu verwenden und die beiden Labelwerte als y = 1 und y = −1 zu kodieren. Die logistische Regression lernt eine Hypothese aus dem Hypothesenraum H(n) (siehe (3.1)).2 Beachten Sie, dass der Hypothesenraum derselbe ist wie bei der linearen Regression (siehe Abschn. 3.1).
|
||
Auf den ersten Blick scheint es verschwenderisch, eine lineare Hypothese h(x) = wT x, mit einem bestimmten Gewichtsvektor w ∈ Rn, zur Vorhersage eines binären Labels y zu verwenden. Tatsächlich kann die Vorhersage h(x) jede reale
|
||
|
||
2Es ist wichtig zu beachten, dass die logistische Regression mit einem beliebigen Labelraum verwendet werden kann, der zwei verschiedene Elemente enthält. Eine weitere beliebte Wahl für den Labelraum ist Y = {0, 1}.
|
||
|
||
3.6 Logistische Regression
|
||
|
||
71
|
||
|
||
Zahl annehmen, während das Label y ∈ {−1, 1} nur eine der beiden reellen Zahlen 1 und −1 annimmt.
|
||
Es stellt sich heraus, dass es sogar für binäre Labels ziemlich nützlich ist, eine
|
||
Hypothesenkarte h zu verwenden, die beliebige reale Zahlen annehmen kann. Wir können immer ein vorhergesagtes Label yˆ ∈ {−1, 1} erhalten, indem wir den Hypothesenwert h(x) mit einer Schwelle vergleichen. Ein Datenpunkt mit Merkmalen x wird als yˆ = 1 klassifiziert, wenn h(x) ≥ 0 und yˆ = −1 für h(x) < 0.
|
||
Daher verwenden wir das Vorzeichen des Prädiktors h, um die endgültige Vorhersage für das Label zu bestimmen. Der absolute Wert |h(x)| wird dann verwendet, um die Zuverlässigkeit (oder das Vertrauen in) die Klassifikation yˆ zu quanti-
|
||
fizieren. Betrachten Sie zwei Datenpunkte mit Merkmalsvektoren x(1), x(2) und
|
||
eine lineare Klassifikatorkarte h, die die Funktionswerte h(x(1)) = 1/10 und h(x(2)) = 100 liefert. Während die Vorhersagen für beide Datenpunkte im selben Labelvorhersagen resultieren, d.h., yˆ(1) = yˆ(2) = 1, scheint die Klassifikation des Datenpunkts mit dem Merkmalsvektor x(2) viel zuverlässiger zu sein.
|
||
Die logistische Regression verwendet den logistischen Verlust (2.12) um die Qualität einer bestimmten Hypothese zu bewerten h(w) ∈ H(n). Insbesondere
|
||
versucht die logistische Regression, das empirische Risiko (durchschnittlicher
|
||
logistischer Verlust) zu minimieren, gegeben ein beschriftetes Trainingsset D = {x(i), y(i)}mi=1
|
||
|
||
m
|
||
L(w|D) = (1/m) log(1 + exp(−y(i)h(w)(x(i))))
|
||
i=1 m
|
||
h(w)(x=)=wT x(1/m) log(1 + exp(−y(i)wT x(i))).
|
||
i=1
|
||
|
||
(3.15)
|
||
|
||
Sobald wir den optimalen Gewichtsvektor w gefunden haben, der (3.15) minimiert, klassifizieren wir einen Datenpunkt basierend auf seinen Merkmalen x gemäß
|
||
|
||
yˆ =
|
||
|
||
1 wenn h(w)(x) ≥ 0 −1 ansonsten.
|
||
|
||
(3.16)
|
||
|
||
Da h(w)(x) = w T x (siehe (3.1)), entspricht der Klassifikator (3.16) dem Testen, ob w T x ≥ 0 oder nicht.
|
||
Der Klassifikator (3.16) teilt den Merkmalsraum X = Rn in zwei Halbräume R1 = x : w T x ≥ 0 und R−1 = x : w T x < 0 auf, die durch die Hyperebene w T x = 0 getrennt sind (siehe Abb. 2.9). Jeder Datenpunkt mit Merkmalen
|
||
x ∈ R1 (x ∈ R−1) wird als yˆ = 1 (yˆ = −1) klassifiziert. Die logistische Regression kann als Maximum-Likelihood-Schätzer inner-
|
||
halb eines bestimmten probabilistischen Modells für die Datenpunkte interpretiert
|
||
|
||
72
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
werden. Dieses probabilistische Modell interpretiert das Label y ∈ {−1, 1} eines Datenpunkts als RV mit der Wahrscheinlichkeitsverteilung
|
||
|
||
p(y = 1; w) = 1/(1 + exp(−wT x)) = h(w)(x)=wT x1/(1 + exp(−h(w)(x)))).
|
||
|
||
(3.17)
|
||
|
||
Wie die Notation zeigt, ist die Wahrscheinlichkeit (3.17) durch den Gewichtsvektor w der linearen Hypothese h(w)(x) = wT x parametriert. Angesichts des probabilistischen Modells (3.17) können wir die Klassifikation (3.16) als Auswahl von yˆ interpretieren, um die Wahrscheinlichkeit p(y = yˆ; w) zu maximieren.
|
||
Da p(y = 1) + p(y = −1) = 1,
|
||
|
||
p(y = −1) = 1 − p(y = 1) (3=.17)1 − 1/(1 + exp(−wT x)) = 1/(1 + exp(wT x)).
|
||
|
||
(3.18)
|
||
|
||
In der Praxis kennen wir den Gewichtsvektor in (3.17) nicht. Stattdessen müssen wir den Gewichtsvektor w in (3.17) aus beobachteten Datenpunkten schätzen.
|
||
Ein prinzipieller Ansatz zur Schätzung des Gewichtsvektors besteht darin, die
|
||
Wahrscheinlichkeit (oder Likelihood) zu maximieren, tatsächlich den Datensatz D = {(x(i), y(i))}mi=1 als Realisierungen von i.i.d. Datenpunkten zu erhalten, deren Labels gemäß (3.17) verteilt sind. Dies ergibt den Maximum-Likelihood-Schätzer
|
||
|
||
w = argmax p({y(i)}mi=1)
|
||
w∈Rn
|
||
m
|
||
y(i)=i.i.d. argmax p(y(i))
|
||
w∈Rn i=1
|
||
m
|
||
(3.17=),(3.18) argmax 1/(1 + exp(−y(i)wT x(i))).
|
||
w∈Rn i=1
|
||
|
||
(3.19)
|
||
|
||
Beachten Sie, dass der letzte Ausdruck (3.19) nur gültig ist, wenn wir die binären Labels mit den Werten 1 und −1 kodieren. Die Verwendung unterschiedlicher Labelwerte führt zu einem anderen Ausdruck.
|
||
Die Maximierung einer positiven Funktion f (w) > 0 ist äquivalent zur Maximierung von log f (x),
|
||
|
||
argmax f (w) = argmax log f (w).
|
||
|
||
w∈Rn
|
||
|
||
w∈Rn
|
||
|
||
Daher kann (3.19) weiter entwickelt werden als
|
||
|
||
m
|
||
w(3=.19) argmax − log 1+exp(−y(i)wT x(i))
|
||
|
||
w∈Rn i=1
|
||
|
||
m
|
||
|
||
= argmin(1/m) log 1+exp(−y(i)wT x(i)) .
|
||
|
||
w∈Rn
|
||
|
||
i=1
|
||
|
||
(3.20)
|
||
|
||
3.7 Support-Vektor-Maschinen
|
||
|
||
73
|
||
|
||
Der Vergleich von (3.20) mit (3.15) zeigt, dass die logistische Regression nichts anderes ist als die Maximum-Likelihood-Schätzung des Gewichtsvektors w im probabilistischen Modell (3.17).
|
||
|
||
3.7 Support-Vektor-Maschinen
|
||
|
||
Support-Vektor-Maschinen sind eine Familie von ML-Methoden zum Erlernen einer Hypothese zur Vorhersage eines binären Labels y eines Datenpunkts basierend auf seinen Merkmalen x. Ohne Einschränkung der Allgemeinheit betrachten wir binäre Labels, die Werte im Labelraum annehmen Y = {−1, 1}. Eine Support-Vektor-Maschine verwendet den linearen Hypothesenraum (3.1), der aus linearen Abbildungen besteht h(x) = wT x mit einem bestimmten Gewichtsvektor w ∈ Rn. Daher verwendet die Support-Vektor-Maschine denselben Hypothesenraum wie die lineare Regression und die logistische Regression, die wir in den Abschn. 3.1 und 3.6 diskutiert haben. Was die Support-Vektor-Maschine von diesen anderen Methoden unterscheidet, ist die Wahl der Verlustfunktion.
|
||
Verschiedene Instanzen einer Support-Vektor-Maschine werden durch die Verwendung unterschiedlicher Konstruktionen für die Merkmale eines Datenpunkts erhalten. Kernel Support-Vektor-Maschinen verwenden das Konzept einer KernelAbbildung zur Konstruktion (typischerweise hochdimensionaler) Merkmale (siehe Abschn. 3.9 und [5]). Im Folgenden gehen wir davon aus, dass die Merkmalskonstruktion gelöst wurde und wir Zugang zu einem Merkmalsvektor x ∈ Rn für jeden Datenpunkt haben.
|
||
Abb. 3.6 zeigt einen Datensatz D von beschrifteten Datenpunkten, die jeweils durch einen Merkmalsvektor x(i) ∈ R2 (als Koordinaten eines Markers verwendet) und einem binären Label y(i) ∈ {−1, 1} (durch verschiedene Markerformen angezeigt) gekennzeichnet sind. Wir können den Datensatz D in zwei Klassen aufteilen
|
||
|
||
C(y=1) = {x(i) : y(i) = 1}, und C(y=−1) = {x(i) : y(i) = −1}.
|
||
|
||
(3.21)
|
||
|
||
"Unterstützungsvektor"
|
||
Abb. 3.6 Die Support-Vektor-Maschine lernt eine Hypothese (oder Klassifikator) h(w) mit minimalem durchschnittlichen Soft-Margin-Hinge-Verlust (3.23). Die Minimierung dieses Verlusts entspricht der Maximierung des Abstands ξ zwischen der Entscheidungsgrenze von h(w) und jeder Klasse des Trainingssets
|
||
|
||
74
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
Die Support-Vektor-Maschine versucht, eine lineare Abbildung h(w)(x) = wT x zu lernen, die die beiden Klassen im Sinne von
|
||
|
||
h x(i) > 0 fu¨r x(i) ∈ C(y=1) und h x(i) < 0 fu¨r x(i) ∈ C(y=−1).
|
||
|
||
wT x(i)
|
||
|
||
wT x(i)
|
||
|
||
(3.22)
|
||
|
||
perfekt trennt. Wir bezeichnen einen Datensatz, dessen Datenpunkte binäre Labels haben, als linear trennbar, wenn wir mindestens eine lineare Abbildung finden können, die im Sinne von (3.22) trennt. Der Datensatz in Abb. 3.6 ist früh trennbar.
|
||
Wie leicht zu überprüfen ist, erfüllt jede lineare Abbildung h(w)(x) = wT x, die einen durchschnittlichen Hinge-Loss von Null erzielt (2.11), auf dem Datensatz D perfekt diese Bedingung (3.22). Es scheint sinnvoll, eine lineare Abbildung zu lernen, indem man den durchschnittlichen Hinge-Loss minimiert (2.11). Ein Nachteil dieses Ansatzes ist jedoch, dass es (unendlich) viele verschiedene lineare Abbildungen geben könnte, die einen durchschnittlichen Hinge-Loss von Null erzielen und somit die Datenpunkte in Abb. 3.6 perfekt trennen. Betrachten Sie tatsächlich eine lineare Abbildung h(w), die für die D in Abb. 3.6 einen durchschnittlichen Hinge-Loss von Null erzielt (und sie daher perfekt trennt). Dann erzielt jede andere lineare Abbildung h(w′) mit Gewichten w′ = w, unter Verwendung einer beliebigen Zahl > 1 ebenfalls einen durchschnittlichen Hinge-Loss von Null (und trennt den Datensatz perfekt).
|
||
Weder die Anforderung an die Trennbarkeit (3.22) noch der Hinge-Verlust (2.11) sind als alleiniges Trainingskriterium ausreichend. Tatsächlich gibt es viele (wenn nicht die meisten) Datensätze, die nicht linear trennbar sind. Selbst für einen linear trennbaren Datensatz (wie den in Abb. 3.6) gibt es unendlich viele lineare Abbildungen mit einem durchschnittlichen Hinge-Verlust von null. Welche dieser unendlich vielen verschiedenen Abbildungen sollten wir verwenden? Um diese Fragen zu klären, verwendet die Support Vector Machine einen „regularisierten“ Hinge-Verlust,
|
||
|
||
L((x, y), h(w)) := max{0, 1 − y · h(w)(x)} + �w�2 = h(w)(x)=wT x max{0, 1 − y · wT x} + �w�2.
|
||
|
||
(3.23)
|
||
|
||
Der Verlust (3.23) erhöht den Hinge-Verlust (2.11) um den Term w 2. Dieser Term ist die skalierte (durch > 0) quadrierte euklidische Norm der Gewichte w der linearen Hypothese h, die zur Klassifizierung von Datenpunkten verwendet wird. Es kann gezeigt werden, dass die Hinzufügung des Terms w 2 zum Hinge-Verlust (2.11) einen Regularisierungseffekt hat. Lässig gesprochen, bevorzugt der resultierende Verlust lineare Abbildungen h(w), die robust gegenüber (kleinen) Störungen der Datenpunkte sind. Der Abstimmungsparameter
|
||
in (3.23) steuert die Stärke dieses Regularisierungseffekts und könnte daher auch als Regularisierungsparameter bezeichnet werden. Wir werden die grundlegenden Prinzipien der Regularisierung auf einer allgemeineren Ebene in Kap. 7 diskutieren.
|
||
|
||
3.7 Support-Vektor-Maschinen
|
||
|
||
75
|
||
|
||
Lassen Sie uns nun eine nützliche geometrische Interpretation der linearen Hypothese entwickeln, die durch Minimierung der Verlustfunktion (3.23) erhalten wird. Nach [5, Kap. 2] maximiert ein Klassifikator h(wSVM), der den durchschnittlichen Verlust (3.23) minimiert, den Abstand (Rand) ξ zwischen seiner Entscheidungsgrenze und jeder der beiden Klassen C(y=1) und C(y=−1) (siehe (3.21)). Die Entscheidungsgrenze wird durch die Menge der Merkmalsvektoren x bestimmt, die wSTVMx = 0 erfüllen,
|
||
Es ist sinnvoll, den Rand so groß wie möglich zu machen, da dies sicherstellt, dass die resultierenden Klassifikationen robust gegenüber kleinen Störungen der Merkmale sind (siehe Abschn. 7.2). Wie in Abb. 3.6 dargestellt, wird der Rand zwischen der Entscheidungsgrenze und den Klassen C1 und C2 typischerweise durch wenige Datenpunkte (wie x(6) in Abb. 3.6), die der Entscheidungsgrenze am nächsten sind, bestimmt. Diese Datenpunkte haben den geringsten Abstand zur Entscheidungsgrenze und werden als Stützvektoren bezeichnet.
|
||
Wir weisen darauf hin, dass sowohl die Support Vector Machine als auch die logistische Regression denselben Hypothesenraum von linearen Abbildungen verwenden. Daher lernen beide Methoden einen linearen Klassifikator h(w) ∈ H(n) (siehe (3.1)), dessen Entscheidungsgrenze eine Hyperebene im Merkmalsraum X = Rn ist (siehe Abb. 2.9). Der Unterschied zwischen der Support Vector Machine und der logistischen Regression liegt in ihrer Wahl für die Verlustfunktion, die zur Bewertung der Qualität einer Hypothese h(w) ∈ H(n) verwendet wird.
|
||
Der Scharnierverlust (2.11) ist (in gewisser Weise) die beste konvexe Annäherung an den 0/1-Verlust (2.9). Daher erwarten wir, dass der durch die Support-Vektor-Maschine erhaltene Klassifikator eine geringere Klassifikationsfehlerwahrscheinlichkeit p(yˆ �= y) (mit yˆ = 1 wenn h(x) ≥ 0 und yˆ = −1 sonst) im Vergleich zur logistischen Regression, die den logistischen Verlust (2.12) verwendet, liefert. Die Support-Vektor-Maschine ist auch statistisch ansprechend, da sie eine robuste Hypothese lernt. Tatsächlich impliziert das Lernen der Hypothese mit maximalem Rand, dass der resultierende Klassifikator maximal robust gegenüber Störungen der Merkmalsvektoren von Datenpunkten ist. Abschn. 7.2 diskutiert die Bedeutung von Robustheit in ML-Methoden genauer.
|
||
Die statistische Überlegenheit der Support-Vektor-Maschine geht auf Kosten einer erhöhten Rechenkomplexität. Insbesondere ist der Scharnierverlust (2.11) nicht differenzierbar, was die Verwendung einfacher gradientenbasierter Methoden (siehe Kap. 5) verhindert und fortgeschrittenere Optimierungsmethoden erfordert. Im Gegensatz dazu ist der logistische Verlust (2.12) konvex und differenzierbar. Wir können daher gradientenbasierte Methoden verwenden, um den durchschnittlichen logistischen Verlust auf einem Trainingsset zu minimieren (siehe Kap. 5).
|
||
|
||
76
|
||
3.8 Bayes-Klassifikator
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
Betrachten Sie Datenpunkte, die durch Merkmale x ∈ X und ein binäres Label y ∈ Y gekennzeichnet sind. Wir können zwei beliebige Labelwerte verwenden, aber wir gehen davon aus, dass die beiden möglichen Labelwerte y = −1 oder y = 1 sind. Wir möchten einen Klassifikator h : X → Y finden (oder lernen), so dass das vorhergesagte (oder geschätzte) Label yˆ = h(x) so gut wie möglich mit dem wahren Label y ∈ Y übereinstimmt. Daher ist es sinnvoll, die Qualität eines Klassifikators h mit dem 0/1-Verlust (2.9) zu bewerten. Wir könnten dann einen Klassifikator lernen, indem wir die empirische Risikominimierung mit der Verlustfunktion (2.9) verwenden. Das resultierende Optimierungsproblem ist jedoch in der Regel unlösbar, da der Verlust (2.9) nicht konvex und nicht differenzierbar ist.
|
||
Anstatt die (unlösbare) empirische Risikominimierung für den 0/1-Verlust zu lösen, gehen wir einen anderen Weg, um einen Klassifikator zu konstruieren. Diese Konstruktion basiert auf einem einfachen probabilistischen Modell für die Datenpunkte. Mit diesem Modell können wir den durchschnittlichen 0/1-Verlust auf den Trainingsdaten als Näherung für die Wahrscheinlichkeit Perr = p(y �= h(x)) interpretieren. Jeder Klassifikator, der diese Fehlerwahrscheinlichkeit minimiert, wird als Bayes-Schätzer bezeichnet. Beachten Sie, dass der Bayes-Schätzer von dem probabilistischen Modell für die Datenpunkte abhängt. Wir erhalten verschiedene Bayes-Schätzer für verschiedene probabilistische Modelle.
|
||
Ein weit verbreitetes probabilistisches Modell führt zu einem Bayes-Schätzer, der zum linearen Hypothesenraum gehört (3.1). Beachten Sie, dass diesem Hypothesenraum auch die logistische Regression (siehe Abschn. 3.6) und die SupportVektor-Maschine (siehe Abschn. 3.7) zugrunde liegen. Daher sind die logistische Regression, die Support-Vektor-Maschine und der Bayes-Schätzer alle Beispiele für einen linearen Klassifikator (siehe Abb. 2.9).
|
||
Ein linearer Klassifikator teilt den Merkmalsraum X in zwei Halbräume. Ein Halbraum besteht aus allen Merkmalsvektoren x, die das vorhergesagte Label yˆ = 1 ergeben und der andere Halbraum besteht aus allen Merkmalsvektoren x, die das vorhergesagte Label yˆ = −1 ergeben. Die Familie der ML-Methoden, die einen linearen Klassifikator lernen, unterscheiden sich in ihrer Wahl der Verlustfunktion und damit, wie sie diese Halbräume wählen. Abschn. 4.5 wird MLMethoden unter Verwendung des Bayes-Schätzers im Detail diskutieren.
|
||
|
||
3.9 Kernel-Methoden
|
||
Betrachten Sie ein ML-Problem (Klassifikation oder Regression) mit einem zugrunde liegenden Merkmalsraum X. Um das Label y ∈ Y eines Datenpunkts basierend auf seinen Merkmalen x ∈ X vorherzusagen, wenden wir einen Prädiktor h aus einem Hypothesenraum H an. Nehmen wir an, dass die verfügbare
|
||
|
||
3.9 Kernel-Methoden
|
||
|
||
77
|
||
|
||
Recheninfrastruktur uns nur erlaubt, einen linearen Hypothesenraum H(n) zu ver-
|
||
wenden (siehe (3.1)).
|
||
Für einige Anwendungen ist die Verwendung einer linearen Hypothese h(x) = wT x nicht geeignet, da die Beziehung zwischen Merkmalen x und Label y
|
||
möglicherweise stark nicht-linear ist. Ein Ansatz zur Erweiterung der Fähigkeiten
|
||
linearer Hypothesen besteht darin, die Rohmerkmale eines Datenpunkts zu trans-
|
||
formieren, bevor eine lineare Hypothese h angewendet wird. Die Familie der Kernel-Methoden basiert auf der Umwandlung der Merkmale x
|
||
in neue Merkmale xˆ ∈ X ′, die zu einem (typischerweise sehr) hochdimensionalen Raum X ′ [5] gehören. Es ist nicht ungewöhnlich, dass, während der ursprüngliche Merkmalsraum ein niedrigdimensionaler euklidischer Raum ist (z. B., X = R2), der transformierte Merkmalsraum X ′ ein unendlich dimensionaler Funktionen-
|
||
raum ist.
|
||
Die Begründung für die Umwandlung der ursprünglichen Merkmale in einen neuen (höherdimensionalen) Merkmalsraum X ′ besteht darin, die intrinsische Geometrie der Merkmalsvektoren x(i) ∈ X so zu verändern, dass die transformierten Merkmalsvektoren xˆ(i) eine „einfachere“ Geometrie haben (siehe
|
||
Abb. 3.7).
|
||
Kernel-Methoden werden erzielt, indem ML-Probleme (wie lineare Regression oder logistische Regression) mit den transformierten Merkmalen xˆ = φ(x)
|
||
formuliert werden. Eine zentrale Herausforderung innerhalb der Kernel-Methoden ist die Wahl der Merkmalsabbildung φ : X → X ′, die den ursprünglichen Merkmalsvektor x auf einen neuen Merkmalsvektor xˆ = φ(x) abbildet.
|
||
|
||
Abb. 3.7 Der Datensatz D = {(x(i), y(i))}5i=1 besteht aus 5 Datenpunkten mit Merkmalen x(i) und binären Labels y(i). Links: Im ursprünglichen Merkmalsraum X können die Datenpunkte nicht
|
||
perfekt durch einen linearen Klassifikator getrennt werden. Rechts: Die Merkmalsabbildung φ : X → X ′ transformiert die Merkmale x(i) zu den neuen Merkmalen xˆ(i) = φ x(i) im neuen Merkmalsraum X ′. Im neuen Merkmalsraum X ′ können die Datenpunkte perfekt durch einen
|
||
linearen Klassifikator getrennt werden
|
||
|
||
78
|
||
3.10 Entscheidungsbäume
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
Ein Entscheidungsbaum ist eine flussdiagrammähnliche Beschreibung einer Karte h : X → Y, die die Merkmale x ∈ X eines Datenpunkts auf ein vorhergesagtes Label h(x) ∈ Y abbildet [6]. Obwohl Entscheidungsbäume für beliebige Merkmalsräume X und Labelräume Y verwendet werden können, werden wir sie für den speziellen Merkmalsraum X = R2 und Labelraum Y = R diskutieren.
|
||
Abb. 3.8 zeigt ein Beispiel für einen Entscheidungsbaum. Ein Entscheidungsbaum besteht aus Knoten, die durch gerichtete Kanten verbunden sind. Man kann sich einen Entscheidungsbaum als schrittweise Anleitung oder ein „Rezept“ vorstellen, wie man den Funktionswert h(x) anhand der Merkmale x ∈ X eines Datenpunkts berechnet. Diese Berechnung beginnt am Wurzelknoten und endet an einem der Blattknoten des Entscheidungsbaums.
|
||
Ein Blattknoten m, der keine ausgehenden Kanten hat, repräsentiert eine Entscheidungsregion Rm ⊆ X im Merkmalsraum. Die Hypothese h, die mit einem Entscheidungsbaum verbunden ist, ist konstant über die Regionen Rm, so dass h(x) = hm für alle x ∈ Rm und eine festgelegte Zahl hm ∈ R gilt.
|
||
Im Allgemeinen gibt es zwei Arten von Knoten in einem Entscheidungsbaum:
|
||
• Entscheidungs- (oder Test-) Knoten, die bestimmte „Tests“ über den Merkmalsvektor x darstellen (z. B. „Ist die Norm von x größer als 10?“).
|
||
• Blattknoten, die Untergruppen des Merkmalsraums entsprechen.
|
||
Der in Abb. 3.8 dargestellte Entscheidungsbaum besteht aus zwei Entscheidungsknoten (einschließlich des Wurzelknotens) und drei Blattknoten.
|
||
Angesichts begrenzter Rechenressourcen können wir nur Entscheidungsbäume verwenden, die nicht zu tief sind. Betrachten Sie den Hypothesenraum, der aus allen Entscheidungsbäumen besteht, die die Tests „�x − u� ≤ r“ und „�x − v� ≤ r“
|
||
|
||
nein
|
||
|
||
ja
|
||
|
||
nein
|
||
|
||
ja
|
||
|
||
Abb. 3.8 Ein Entscheidungsbaum stellt eine Hypothese h dar, die auf Teilmengen Rm konstant ist, d.h., h(x) = hm für alle x ∈ Rm. Jede Teilmenge Rm ⊆ X entspricht einem Blattknoten im Entscheidungsbaum
|
||
|
||
3.10 Entscheidungsbäume
|
||
|
||
79
|
||
|
||
nein
|
||
|
||
ja
|
||
|
||
nein
|
||
|
||
ja
|
||
|
||
nein
|
||
|
||
ja
|
||
|
||
Abb. 3.9 Ein Hypothesenraum H bestehend aus zwei Entscheidungsbäumen mit einer Tiefe von höchstens 2 und unter Verwendung der Tests �x−u� ≤ r und �x−v� ≤ r mit einem festen Radius r und Vektoren u, v ∈ Rn
|
||
verwenden, mit einigen Vektoren u und v, einem positiven Radius r > 0 und einer Tiefe, die nicht größer als 2 ist.3
|
||
Um die Qualität eines bestimmten Entscheidungsbaums zu bewerten, können wir verschiedene Verlustfunktionen verwenden. Beispiele für Verlustfunktionen, die zur Messung der Qualität eines Entscheidungsbaums verwendet werden, sind der quadratische Fehlerverlust (für numerische Labels) oder die Unreinheit einzelner Entscheidungsregressionen (für diskrete Labels).
|
||
Entscheidungsbaummethoden verwenden als Hypothesenraum die Menge aller Hypothesen, die durch eine Sammlung von Entscheidungsbäumen dargestellt werden. Abb. 3.9 zeigt eine Sammlung von Entscheidungsbäumen, die dadurch gekennzeichnet sind, dass sie höchstens zwei Ebenen tief sind. Diese Methoden suchen nach Entscheidungsbäumen, so dass die entsprechende Hypothese den minimalen durchschnittlichen Verlust auf einigen beschrifteten Trainingsdaten hat (siehe Abschn. 4.4).
|
||
Eine Sammlung von Entscheidungsbäumen kann auf der Grundlage eines festen Satzes von „elementaren Tests“ auf dem Eingabe-Merkmalvektor erstellt werden, z. B., x > 3, x3 < 1 oder eine kontinuierliche Gruppe von parametrisierten Tests wie {x2 > η}η∈[0,10]. Wir erstellen dann einen Hypothesenraum, indem wir alle Entscheidungsbäume berücksichtigen, die eine maximale Tiefe nicht überschreiten und deren Entscheidungsknoten einen der elementaren Tests durchführen.
|
||
Ein Entscheidungsbaum stellt eine Abbildung h : X → Y dar, die stückweise konstant über Bereiche des Merkmalsraums X ist. Diese sich nicht überlappenden Bereiche bilden eine Partitionierung des Merkmalsraums. Jeder Blattknoten eines Entscheidungsbaums entspricht einer bestimmten Region. Mit großen Entscheidungsbäumen, die viele verschiedene Testknoten beinhalten, können wir sehr komplizierte Partitionen darstellen, die einem gegebenen gelabelten Datensatz ähneln (siehe Abb. 3.10).
|
||
|
||
3Die Tiefe eines Entscheidungsbaums ist die maximale Anzahl von Sprüngen, die benötigt werden, um von der Wurzel aus einen Blattknoten zu erreichen, wenn man den Pfeilen folgt. Der in Abb. 3.8 dargestellte Entscheidungsbaum hat eine Tiefe von 2.
|
||
|
||
80
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
nein nein ja
|
||
|
||
ja nein ja
|
||
|
||
Abb. 3.10 Mit einem ausreichend großen (tiefen) Entscheidungsbaum können wir eine Karte h erstellen, die perfekt zu einem gegebenen beschrifteten Datensatz {(x(i), y(i))}mi=1 passt, so dass h(x(i)) = y(i) für i = 1, . . . , m
|
||
Dies unterscheidet sich stark von ML-Methoden, die den linearen Hypothesenraum verwenden (3.1), wie lineare Regression, logistische Regression oder die Support-Vektor-Maschine. Diese Methoden lernen lineare Hypothesenkarten mit einer eher einfachen Geometrie. Tatsächlich ist eine lineare Karte entlang von Hyperflächen konstant. Darüber hinaus sind die Entscheidungsregionen, die aus linearen Klassifikatoren gewonnen werden, immer ganze Halbräume (siehe Abb. 2.9).
|
||
Im Gegensatz dazu kann die Form einer Karte, die durch einen Entscheidungsbaum dargestellt wird, viel komplizierter sein. Mit einem ausreichend großen (tiefen) Entscheidungsbaum können wir eine Hypothesenkarte erhalten, die eine gegebene nichtlineare Karte genau approximiert. Die Verwendung von ausreichend tiefen Entscheidungsbäumen für Klassifikationsprobleme ermöglicht hochgradig unregelmäßige Entscheidungsregionen.
|
||
|
||
3.11 Tiefes Lernen
|
||
|
||
Ein weiteres Beispiel für einen Hypothesenraum verwendet eine Signalflussdar-
|
||
|
||
stellung einer Hypothesenkarte h : Rn → R. Diese Signalflussdarstellung wird
|
||
|
||
als künstliches neuronales Netzwerk bezeichnet. Abb. 3.8 zeigt ein Beispiel für
|
||
|
||
ein künstliches neuronales Netzwerk, das zur Darstellung einer (parametrisierten)
|
||
|
||
Hypothese h(w) : Rn → R verwendet wird. Ein Merkmalsvektor x ∈ Rn wird in
|
||
|
||
die Eingabeeinheiten eingespeist, von denen jede ein einzelnes Merkmal xj ∈ R
|
||
|
||
einliest. Die Merkmale xj werden dann mit den Gewichten wj,j′ multipliziert, die mit der Verbindung zwischen dem jten Eingabeknoten („Neuron“) und dem j′ten
|
||
|
||
Knoten in der mittleren (verborgenen) Schicht verbunden sind. Die Ausgabe des j′
|
||
|
||
-ten Knotens in der verborgenen Schicht wird gegeben durch sj′ = g(
|
||
|
||
n j=1
|
||
|
||
wj,j′
|
||
|
||
xj
|
||
|
||
)
|
||
|
||
mit einer (typischerweise nicht-linearen) Aktivierungsfunktion f : R → R. Das
|
||
|
||
Eingabeargument für die Aktivierungsfunktion ist die gewichtete Kombination
|
||
|
||
3.11 Tiefes Lernen
|
||
|
||
81
|
||
|
||
n j=1
|
||
|
||
wj,j′
|
||
|
||
sj′
|
||
|
||
der
|
||
|
||
Ausgaben
|
||
|
||
sj
|
||
|
||
der
|
||
|
||
Knoten
|
||
|
||
in
|
||
|
||
einer
|
||
|
||
vorherigen
|
||
|
||
Schicht.
|
||
|
||
Für
|
||
|
||
das
|
||
|
||
in
|
||
|
||
Abb. 3.11 dargestellte künstliche neuronale Netzwerk ist die Ausgabe des Neurons
|
||
|
||
s1 ist f (z) mit z = w1,1x1 + w1,2x2.
|
||
|
||
Zwei beliebte Wahlmöglichkeiten für die in künstlichen neuronalen
|
||
|
||
Netzwerken verwendete Aktivierungsfunktion sind die Sigmoid Funktion
|
||
|
||
f (z) =
|
||
|
||
1 1+exp(−z)
|
||
|
||
oder
|
||
|
||
die tief
|
||
|
||
Netz
|
||
|
||
f (z) = max{0, z}.
|
||
|
||
Künstliche
|
||
|
||
neuronale
|
||
|
||
Netz-
|
||
|
||
werke, die viele, sagen wir 10, versteckte Schichten verwenden, werden oft als tief
|
||
|
||
Netz bezeichnet. ML-Methoden, die Hypothesenräume aus tiefen Netzen ver-
|
||
|
||
wenden, sind als tief Lernmethoden bekannt [7].
|
||
|
||
Bemerkenswerterweise ermöglicht uns die Verwendung einer einfachen
|
||
|
||
nichtlinearen Aktivierungsfunktion f (z) als Baustein für künstliche neuronale
|
||
|
||
Netzwerke, eine extrem große Klasse von Vorhersagekarten h(w) : Rn → R dar-
|
||
|
||
zustellen. Der durch eine gegebene Struktur eines künstlichen neuronalen Netz-
|
||
|
||
werks erzeugte Hypothesenraum, d.h. die Menge aller Vorhersagekarten, die
|
||
|
||
durch ein gegebenes künstliches neuronales Netzwerk und geeignete Gewichte w
|
||
|
||
implementiert werden können, ist in der Regel viel größer als der Hypothesenraum
|
||
|
||
(2.4) linearer Prädiktoren, die Gewichtsvektoren w der gleichen Länge verwenden
|
||
|
||
[7, Abschn. 6.4.1.]. Es kann gezeigt werden, dass ein künstliches neuronales
|
||
|
||
Netzwerk mit nur einer einzigen (aber beliebig großen) versteckten Schicht jede
|
||
|
||
gegebene Karte h : X → Y = R mit beliebiger Genauigkeit approximieren kann
|
||
|
||
[8]. Eine Schlüsselerkenntnis, die vielen Deep-Learning-Methoden zugrunde
|
||
|
||
liegt, ist jedoch, dass die Verwendung mehrerer Schichten mit wenigen Neuronen,
|
||
|
||
anstatt einer einzigen Schicht mit vielen Neuronen, rechnerisch günstiger ist [9].
|
||
|
||
Der jüngste Erfolg von ML-Methoden, die auf künstlichen neuronalen Netz-
|
||
|
||
werken mit vielen versteckten Schichten (was sie tief macht) basieren, könnte
|
||
|
||
darauf zurückzuführen sein, dass die Netzwerkdarstellung von Hypothesen-
|
||
|
||
karten für die rechnerische Implementierung von ML-Methoden vorteilhaft ist.
|
||
|
||
Erstens können wir eine Karte h(w), die durch ein künstliches neuronales Netz-
|
||
|
||
werk repräsentiert wird, effizient mit moderner paralleler und verteilter Rechen-
|
||
|
||
infrastruktur über Nachrichtenübertragung im Netzwerk auswerten. Zweitens
|
||
|
||
Abb. 3.11 Darstellung eines
|
||
künstlichen neuronalen
|
||
Netzwerks eines Prädiktors h(w)(x), der den Eingabevektor (Feature) x = (x1, x2)T auf
|
||
ein vorhergesagtes Label (Ausgabe) h(w)(x) abbildet
|
||
|
||
Eingabes chicht
|
||
|
||
ausgeblendete Schicht
|
||
|
||
Ausgabes chicht
|
||
|
||
82
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
ermöglicht uns die grafische Darstellung einer parametrisierten Hypothese in Form eines künstlichen neuronalen Netzwerks, den Gradienten der Verlustfunktion effizient über ein (hoch skalierbares) Nachrichtenübertragungsverfahren, das als Backpropagation bekannt ist, zu berechnen [7].
|
||
|
||
3.12 Maximale Wahrscheinlichkeit
|
||
|
||
Für viele Anwendungen ist es nützlich, die beobachteten Datenpunkte z(i), mit i = 1, . . . , m, als i.i.d. Realisierungen einer Zufallsvariable z mit Wahrscheinlichkeitsverteilung p(z; w) zu modellieren. Diese Wahrscheinlichkeitsverteilung ist im Sinne einer Abhängigkeit von einem Gewichtsvektor w ∈ Rn parametrisiert. Ein prinzipieller Ansatz zur Schätzung des Vektors w basierend auf einer Menge von i.i.d. Realisierungen z(1), . . . , z(m) ∼ p(z; w) ist die Schätzung nach der Methode der maximalen Wahrscheinlichkeit [10].
|
||
Die Schätzung nach der Methode der maximalen Wahrscheinlichkeit kann als ein ML-Problem interpretiert werden, das durch den Gewichtsvektor w parametrisiert ist, d.h., jedes Element h(w) des Hypothesenraums H entspricht einer bestimmten Wahl für den Gewichtsvektor w, und die Verlustfunktion
|
||
|
||
L(z, h(w)) := − log p(z; w).
|
||
|
||
(3.24)
|
||
|
||
Eine weit verbreitete Wahl für die Wahrscheinlichkeitsverteilung p z; w ist eine multivariate Normalverteilung (Gaußsche Verteilung) mit Mittelwert µ und Kovarianzmatrix , die beide den Gewichtsvektor bilden w = (µ, �) (wir müssen die Matrix geeignet in eine Vektorform umformen). Gegeben die i.i.d. Realisierungen z(1), . . . , z(m) ∼ p z; w , die Maximum-Likelihood-Schätzungen µˆ , des Mittelwertvektors und der Kovarianzmatrix werden über
|
||
|
||
m
|
||
|
||
µˆ , � = argmin (1/m) − log p z(i); (µ, �) .
|
||
|
||
µ∈Rn ,� ∈Sn+
|
||
|
||
i=1
|
||
|
||
(3.25)
|
||
|
||
Die Optimierung in (3.25) erfolgt über alle möglichen Auswahlmöglichkeiten für den Mittelwertvektor µ ∈ Rn und die Kovarianzmatrix ∈ Sn+. Hier bezeichnet Sn+ die Menge aller positiven semidefiniten hermiteschen n × n Matrizen.
|
||
Das Maximum-Likelihood-Problem (3.25) kann als ein Beispiel für empirische
|
||
Risikominimierung (4.3) mit einer speziellen Verlustfunktion (3.24) interpretiert
|
||
werden. Die resultierenden Schätzungen sind explizit als
|
||
|
||
m
|
||
|
||
m
|
||
|
||
µˆ = (1/m) z(i), und � = (1/m) (z(i) − µˆ )(z(i) − µˆ )T .
|
||
|
||
i=1
|
||
|
||
i=1
|
||
|
||
(3.26)
|
||
|
||
Beachten Sie, dass die Ausdrücke (3.26) nur gültig sind, wenn die Wahrscheinlichkeitsverteilung der Datenpunkte als multivariate Normalverteilung modelliert wird.
|
||
|
||
3.14 Tiefes Verstärkungslernen
|
||
|
||
83
|
||
|
||
3.13 Nächste-Nachbar-Methoden
|
||
|
||
Nächste-Nachbar-Methoden sind eine wichtige Familie von ML-Methoden, die durch eine spezifische Konstruktion des Hypothesenraums gekennzeichnet sind. Diese Familie bietet Methoden für Regressionsprobleme mit numerischen Labels (z. B. mit Labelraum Y = R) sowie für Klassifikationsprobleme mit kategorischen Labels (z. B. mit Labelraum Y = {−1, 1}). Während Nächste-Nachbar-Methoden mit beliebigen Labelräumen kombiniert werden können, erfordern sie, dass der Merkmalsraum ein metrischer Raum ist [1], damit wir Abstände zwischen verschiedenen Merkmalsvektoren berechnen können.
|
||
Ein weit verbreitetes Beispiel für einen metrischen Merkmalsraum ist der euklidische Raum Rn mit dem euklidischen Abstand �x−x′� zwischen zwei Vektoren x, x′ ∈ Rn. Betrachten Sie einen Datensatz D = {(x(i), y(i))}mi=1 von beschrifteten Datenpunkten, die jeweils durch einen Merkmalsvektor und ein Label charakterisiert sind. Nächste-Nachbar-Methoden verwenden einen Hypothesenraum, der aus stückweisen Abbildungen besteht h : X → Y. Der Funktionswert h(x), für einen bestimmten Merkmalsvektor x, hängt nur von den (Labels der) k nächsten Datenpunkten im Datensatz D ab. Die Anzahl k der nächsten Nachbarn ist ein Designparameter der Methode. Nächste-Nachbar-Methoden werden auch als k-nächste-Nachbar-Methoden (k-NN) bezeichnet, um ihre Abhängigkeit vom Parameter k explizit zu machen.
|
||
Es ist wichtig zu beachten, dass im Gegensatz zu den ML-Methoden in den Abschn. 3.1–3.11 der Hypothesenraum von k-NN von einem (Trainings-)Datensatz D abhängt. Als Konsequenz müssen k-NN-Methoden den Trainingsdatensatz abfragen (einlesen), wann immer sie eine Vorhersage berechnen. Insbesondere um eine Vorhersage h(x) für einen neuen Datenpunkt mit Merkmalen x zu berechnen, muss k-NN die nächsten Nachbarn im Trainingsdatensatz bestimmen. Bei Verwendung eines großen Trainingsdatensatzes (was in der Regel vorteilhaft für die resultierende Genauigkeit der ML-Methode ist) bedeutet dies einen großen Speicherbedarf für k-NN-Methoden. Darüber hinaus könnten k-NN-Methoden dazu neigen, mit ihren Vorhersagen sensible Informationen preiszugeben (siehe Übung 3.7).
|
||
|
||
3.14 Tiefes Verstärkungslernen
|
||
Tiefes Verstärkungslernen (DRL) bezieht sich auf eine Teilmenge von MLProblemen und -Methoden, die sich um die Steuerung dynamischer Systeme wie autonom fahrende Autos oder Reinigungsroboter drehen [11–13]. Ein DRLProblem beinhaltet Datenpunkte, die die Zustände eines dynamischen Systems zu verschiedenen Zeitpunkten repräsentieren t = 0, 1, . . .. Die Datenpunkte, die den Zustand zu einem bestimmten Zeitpunkt t repräsentieren, werden durch den Merkmalsvektor x(t) charakterisiert. Die Einträge dieses Merkmalsvektors sind die
|
||
|
||
84
|
||
|
||
3 Die Landschaft des ML
|
||
|
||
individuellen Merkmale des Zustands zur Zeit t. Diese Merkmale könnten durch
|
||
Sensoren, Onboard-Kameras oder andere ML-Methoden (die die Position des dynamischen Systems vorhersagen) erlangt werden. Das Label y(t) eines Daten-
|
||
punkts könnte den optimalen Lenkwinkel zur Zeit t darstellen.
|
||
DRL-Methoden lernen eine Hypothese h, die optimale Vorhersagen yˆ(t) := h x(t) für den optimalen Lenkwinkel y(t) liefert. Wie der Name schon
|
||
sagt, verwenden DRL-Methoden Hypothesenräume, die aus einem tiefen Netz (siehe Abschn. 3.11) gewonnen werden. Die Qualität der Vorhersage yˆ(t), die aus einer Hypothese gewonnen wird, wird durch den Verlust L( x(t), y(t) , h) := −r(t) mit einem Belohnungssignal r(t) gemessen. Dieses Belohnungssignal könnte von
|
||
einem Abstandssensor (Kollisionsvermeidung) oder niedrigstufigen Eigenschaften
|
||
eines Onboard-Kamera-Schnappschusses erhalten werden. Das (negative) Belohnungssignal −r(t) hängt typischerweise von dem
|
||
Merkmalsvektor x(t) und der Diskrepanz zwischen optimaler Lenkrichtung y(t) (die unbekannt ist) und ihrer Vorhersage yˆ(t) := h x(t) ab. Was jedoch DRL-Methoden
|
||
von anderen ML-Methoden wie der linearen Regression (siehe Abschn. 3.1) oder
|
||
der logistischen Regression (siehe Abschn. 3.6) unterscheidet, ist, dass sie die Verlustfunktion nur punktweise L( x(t), y(t) , h) für die spezifische Hypothese h, die zur Berechnung der Vorhersage yˆ(t) := h x(t) zum Zeitpunkt t verwendet
|
||
wurde, bewerten können. Dies unterscheidet sich grundlegend von der linearen
|
||
Regression, die den quadratischen Fehlerverlust (2.8) verwendet, der für jede
|
||
mögliche Hypothese h ∈ H bewertet werden kann.
|
||
|
||
3.15 LinUCB
|
||
|
||
ML-Methoden sind für verschiedene Empfehlungssysteme [14] unerlässlich. Eine grundlegende Form eines Empfehlungssystems besteht darin, zu einem bestimmten Zeitpunkt t den am besten geeigneten Artikel (Produkt, Lied, Film) aus einer endlichen Menge von Alternativen a = 1, . . . , A auszuwählen. Jede Alternative wird durch einen Merkmalsvektor x(t,a) charakterisiert, der zwischen verschiedenen Zeitpunkten variiert.
|
||
Die in Empfehlungssystemen auftretenden Datenpunkte repräsentieren typischerweise verschiedene Zeitpunkte t, zu denen Empfehlungen berechnet werden. Der Datenpunkt zur Zeit t ist durch einen Merkmalsvektor gekennzeichnet
|
||
|
||
x(t) = x(t,1) T , . . . , x(t,A) T T .
|
||
|
||
(3.27)
|
||
|
||
Der Merkmalsvektor x(t) wird erhalten, indem die Merkmalsvektoren der Alternativen zur Zeit t zu einem einzigen langen Merkmalsvektor gestapelt werden. Das Label des Datenpunkts t ist ein Vektor von Belohnungen y(t) := r1(t), . . . , rA(t) T ∈ RA. Der Eintrag ra(t) repräsentiert die Belohnung, die durch
|
||
|
||
3.16 Übungen
|
||
|
||
85
|
||
|
||
die Auswahl (Empfehlung) der Alternative a (mit Merkmalen x(t,a)) zur Zeit t erzielt wird. Wir könnten die Belohnung r(t,a) als Indikator interpretieren, ob der Kunde
|
||
das Produkt, das der empfohlenen Alternative entspricht, tatsächlich kauft a.
|
||
Die ML-Methode LinUCB (der Name scheint von den Begriffen „linear“ und
|
||
„upper confidence bound“ (UCB) inspiriert zu sein) zielt darauf ab, eine Hypothese h zu lernen, die es ermöglicht, die Belohnungen y(i) auf der Grundlage des Merkmalsvektors x(t) (3.27) vorherzusagen. Als Hypothesenraum H verwendet
|
||
LinUCB den Raum der linearen Abbildungen von den gestapelten Merkmalsvektoren RnA in den Raum der Belohnungsvektoren RA. Dieser Hypothesenraum kann durch Matrizen W ∈ RA×nA parametrisiert werden. Daher lernt LinUCB eine
|
||
Hypothese, die die vorhergesagten Belohnungen berechnet via
|
||
|
||
y(t) := Wx(t).
|
||
|
||
(3.28)
|
||
|
||
Die Einträge von y(t) = rˆ1(t), . . . , rˆA(t) sind Vorhersagen der einzelnen Belohnungen r(t,a). Es scheint natürlich, zur Zeit t die Alternative a zu empfehlen,
|
||
|
||
deren vorhergesagte Belohnung maximal ist. Es stellt sich jedoch heraus, dass
|
||
|
||
dieser Ansatz suboptimal ist, da er das Empfehlungssystem daran hindert, die
|
||
|
||
optimale Vorhersagekarte W zu lernen.
|
||
|
||
Grob gesagt, probiert LinUCB jede Alternative a ∈ {1, . . . , A} ausreichend oft
|
||
|
||
aus (erkundet), um eine ausreichende Menge an Trainingsdaten für das Erlernen
|
||
|
||
einer guten Gewichtsmatrix W zu erhalten. Zum Zeitpunkt t wählt LinUCB die Alternative a(t), die die Menge maximiert
|
||
|
||
rˆa(t) + R(t, a), a = 1, . . . , A.
|
||
|
||
(3.29)
|
||
|
||
Wir können die Komponente R(t, a) als eine Art Konfidenzintervall betrachten.
|
||
Es wird so konstruiert, dass (3.29) die tatsächliche Belohnung ra(t) mit einem vorgegebenen Konfidenzniveau (oder Wahrscheinlichkeit) nach oben begrenzt. Der Konfidenzterm R(t, a) hängt von den Merkmalsvektoren x(t′,a) der Alternative
|
||
a zu früheren Zeitpunkten t′ < t ab. Daher wählt LinUCB zu jedem Zeitpunkt t
|
||
|
||
die Alternative a, die zur größten oberen Konfidenzgrenze (UCB) (3.29) für die
|
||
|
||
Belohnung führt (daher das „UCB“ in LinUCB). Wir verweisen auf die ein-
|
||
|
||
schlägige Literatur zum sequenziellen Lernen (und Entscheidungsfindung) für
|
||
|
||
weitere Details zu LinUCB [14].
|
||
|
||
3.16 Übungen
|
||
Übung 3.1 Logistischer Verlust und Genauigkeit Abschn. 3.6 diskutierte die logistische Regression als eine ML-Methode, die eine lineare Hypothesenkarte lernt, indem sie den logistischen Verlust minimiert (3.15). Der logistische Verlust hat rechnerisch angenehme Eigenschaften, da er glatt und konvex ist. In einigen Anwendungen könnten wir jedoch letztendlich an der Genauigkeit oder (äquivalent) dem durchschnittlichen 0/1-Verlust (2.9) interessiert sein. Können wir den
|
||
|