922 lines
114 KiB
Plaintext
922 lines
114 KiB
Plaintext
Kristian Kersting · Christoph Lampert Constantin Rothkopf Hrsg.
|
||
Wie Maschinen lernen
|
||
Künstliche Intelligenz verständlich erklärt
|
||
|
||
Wie Maschinen lernen
|
||
|
||
Kristian Kersting · Christoph Lampert · Constantin Rothkopf
|
||
(Hrsg.)
|
||
Wie Maschinen lernen
|
||
Künstliche Intelligenz verständlich erklärt
|
||
|
||
Hrsg. Kristian Kersting Technische Universität Darmstadt Darmstadt, Deutschland
|
||
Constantin Rothkopf Technische Universität Darmstadt Darmstadt, Deutschland
|
||
|
||
Christoph Lampert Institute of Science and Technology Klosterneuburg, Österreich
|
||
|
||
ISBN 978-3-658-26762-9
|
||
|
||
ISBN 978-3-658-26763-6 (eBook)
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6
|
||
|
||
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer Nature 2019 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.
|
||
|
||
Bildnachweis Umschlag: © Nanina Föhr. Mit Abbildungen von Nanina Föhr.
|
||
|
||
Springer ist ein Imprint der eingetragenen Gesellschaft Springer Fachmedien Wiesbaden GmbH und ist ein Teil von Springer Nature. Die Anschrift der Gesellschaft ist: Abraham-Lincoln-Str. 46, 65189 Wiesbaden, Germany
|
||
|
||
Geleitwort
|
||
Grußwort Matthias Kleiner, Präsident der LeibnizGemeinschaft und Vorsitzender des wissenschaftlichen Beirates der KI-Kompetenzzentren in Deutschland Liebe Leserinnen und Leser – oder einfach: Dear All! Ob es wohl stimmt, dass jedes Buch schließlich die Leserinnen und Leser findet, die es verdient? Für das vorliegende Buch hoffe ich, dass die Menge der Leserschaft rasch gen 100 % strebt – eben alle, einfach jede und jeder seine Leserinnen und Leser werden. Warum? Weil seine Inhalte alle angehen. Weil es sich zur Aufgabe gemacht hat, für alle zu sein. Das vorliegende Buch haben angehende Expertinnen und Experten für künstliche Intelligenz und maschinelles Lernen geschrieben, um beides zugänglich zu machen, um beides nicht nur in den Alltag des Nutzens und Benutzens, sondern in den Alltag des Verstehens zu rücken, um zu informieren, Schlagworte zu konkretisieren und Chancen und Risiken zu diskutieren – für mehr
|
||
V
|
||
|
||
VI Geleitwort
|
||
Bewusstsein, mehr Entscheidungskompetenz und am Ende sicher auch für weniger Ängste und Hysterie.
|
||
Das ist gut, das ist wichtig. Denn im Verhältnis zwischen unserer Gesellschaft und künstlicher Intelligenz ist wissenschaftliche Sachlichkeit ebenso nötig wie umgekehrt beherzte Dialogbereitschaft wie die vorliegende dem Verhältnis von Gesellschaft und Wissenschaft wohl bekommt: Künstliche Intelligenz ist kein Wesen mit Eigenleben oder eigenständigen Vitalfunktionen, das jegliches menschliche Handeln übernehmen kann oder soll. Künstliche Intelligenz bezeichnet im Grunde genommen ein Bündel von Technologien, oder besser noch, Algorithmen, also Rechen- oder Handlungsanweisungen, die verschiedene Prozesse des Erschließens und Aneignens, des Anwendens und Transformierens, gerichtet auf bestimmte Funktionalitäten und Ergebnisse, umsetzen können.
|
||
Dem kommt eine gewisse Lisa – also eine junge Dame aus unserer Mitte – auf den folgenden Seiten mit, Dir, mit Euch, mit allen, liebe Leserinnen und Leser, auf die Spur. Viel Vergnügen!
|
||
Matthias Kleiner
|
||
|
||
Vorwort
|
||
Wir sehen sie vielleicht nicht, aber Künstliche Intelligenz ist überall um uns herum. Sie hat längst unser Leben erobert und hilft uns, den Alltag bequemer und besser informiert zu gestalten. Sie hilft uns beim Suchen im Internet, sie übersetzt uns im Urlaub die Straßenschilder, und sie erlaubt es uns, in natürlicher Sprache unser Smartphone zu bedienen. KI, so die populäre Abkürzung für Künstliche Intelligenz, ermöglicht es der Feuerwehr im Notfall schneller durch den Verkehr zu kommen, sie hilft der Landwirtschaft optimal zu düngen und zu säen, sie verbessert Aussagen über den Klimawandel und sie hilft, das Zusammenspiel von neuen Medikamenten mit tausenden möglicher Nebenwirkungen vorauszusagen. KI erlaubt aber auch personalisierte Werbung im Internet, sie ermöglicht die rund-um-die-Uhr Kameraüberwachung von öffentlichen Plätzen, und überhaupt übernimmt sie mehr und mehr Tätigkeiten, die vorher Menschen vorbehalten waren.
|
||
VII
|
||
|
||
VIII Vorwort
|
||
Diese Entwicklungen kann man begrüßen oder kritisieren, aber man sollte sie nicht ignorieren. Klar ist, dass mit der immer schnelleren Entwicklung solcher KI-Systeme auch das Potenzial wächst, dass der Alltag von Bürgerinnen und Bürgern massiv beeinträchtigt wird. Insofern überrascht es nicht, dass in den letzten Jahren eine öffentliche Debatte über die Auswirkungen von KI auf unsere Gesellschaft entstanden ist. Was passiert, wenn manche Staaten KI nutzen, um ihre Bürgerinnen und Bürger zu überwachen? Welche Informationen kann KI aus den Daten gewinnen, die große Konzerne über ihre Milliarden von Nutzern sammeln? Wie verändert KI die Kommunikation oder die Arbeitswelt? Welche Auswirkungen hat KI für jeden Einzelnen und für das Zusammenleben in der Gesellschaft? Welche Grenzen sollte es für KI geben?
|
||
Fassen wir zusammen: Künstliche Intelligenz ist die wohl spannendste Zukunftstechnologie unserer Zeit. Leider ist KI für viele unter uns ein Buch mit sieben Siegeln. Man hört Sensationsmeldungen in den Nachrichten oder im Internet, doch was verbirgt sich hinter den Schlagzeilen, was ist Wirklichkeit und was ist Fiktion? Um heute gemeinsam die Weichen dafür zu stellen, wie die Welt von morgen aussehen wird, braucht jeder ein grundlegendes Verständnis darüber, was KI ist und wie sie funktioniert. Nur so kann eine Diskussion stattfinden, die die ganze Gesellschaft erreicht.
|
||
Aufzuklären und einen bescheidenen Beitrag zur Öffnung der Diskussion zu leisten, das war auch unser Ziel, als wir vor gut zwei Jahren das wissenschaftliche Kolleg „Künstliche Intelligenz – Fakten, Chancen, Risiken“ der Studienstiftung des deutschen Volkes ins Leben riefen – Danke für die Chance und die finanzielle und logistische Unterstützung an die Studienstiftung. In zahlreichen Treffen mit einer Gruppe von 25 Studierenden haben wir uns
|
||
|
||
Vorwort IX
|
||
informiert, gestaunt, diskutiert und gelacht. In dem Buch, das Sie gerade in den Händen halten, präsentieren wir Ihnen unsere Ergebnisse: einen Einblick in den aktuellen Stand der Künstlichen Intelligenz, aufbereitet in allgemeinverständlicher Weise ohne zu viele technische Details, aber auch ohne zu starke Vereinfachungen, denn in ihrer Essenz sind die zugrunde liegenden Techniken bereits einfach genug.
|
||
Der Motor, welcher die moderne KI antreibt, ist das Konzept des maschinellen Lernens. Dieses erlaubt, Computern neue Fähigkeiten beizubringen, einfach indem man ihnen passende Daten zur Verfügung stellt. Statt vieler spezialisierter Verfahren benötigt man nur eine kleine Anzahl von Lernalgorithmen, von denen wir Ihnen die wichtigsten in diesem Buch vorstellen. Sie sind alles, was Sie wirklich wissen müssen, um zu verstehen, wie das maschinelle Lernen die Welt verändert. Weit entfernt von Esoterik und ganz abgesehen von ihrem Einsatz in Computern sind sie Antworten auf Fragen, die uns alle angehen: Wie lernen Maschinen? Wo liegen ihre Grenzen? Können wir dem, was Maschinen gelernt haben, wirklich vertrauen? Und wie lernen wir?
|
||
Diese und andere Fragen beantwortet die Heldin unseres Buches, Lisa. Die wahren Helden sind aber die Teilnehmerinnen und Teilnehmer des Kollegs. Ihr habt das Buch geschrieben. Ihr habt Lisa ins Leben gerufen und so nahbar und liebevoll gestaltet, wie wir das niemals geschafft hätten. Danke!
|
||
|
||
Darmstadt, Deutschland Wien, Österreich Darmstadt, Deutschland
|
||
|
||
Kristian Kersting Christoph Lampert Constantin Rothkopf
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
Teil I Grundlagen
|
||
|
||
1 Einleitung
|
||
|
||
3
|
||
|
||
Jannik Kossen, Fabrizio Kuruc und
|
||
|
||
Maike Elisa Müller
|
||
|
||
2 Algorithmen
|
||
|
||
11
|
||
|
||
Nicolas Berberich
|
||
|
||
3 Maschinelles Lernen
|
||
|
||
21
|
||
|
||
Michael Krause und Elena Natterer
|
||
|
||
4 Daten
|
||
|
||
29
|
||
|
||
Alexandros Gilch und Theresa Schüler
|
||
|
||
5 Regression
|
||
|
||
39
|
||
|
||
Jannik Kossen und Maike Elisa Müller
|
||
|
||
XI
|
||
|
||
XII Inhaltsverzeichnis
|
||
|
||
6 Klassifikation
|
||
|
||
45
|
||
|
||
Jana Aberham und Jannik Kossen
|
||
|
||
7 Clusteranalyse
|
||
|
||
53
|
||
|
||
Jana Aberham und Fabrizio Kuruc
|
||
|
||
Teil II Lernverfahren und mehr
|
||
|
||
8 Lineare Regression
|
||
|
||
61
|
||
|
||
Jannik Kossen und Maike Elisa Müller
|
||
|
||
9 Ausreißer
|
||
|
||
69
|
||
|
||
Jannik Kossen und Maike Elisa Müller
|
||
|
||
10 k-Nächste-Nachbarn
|
||
|
||
73
|
||
|
||
Michael Neumann
|
||
|
||
11 k-Means-Algorithmus
|
||
|
||
81
|
||
|
||
Dorothea Müller
|
||
|
||
12 Fluch der Dimensionalität
|
||
|
||
89
|
||
|
||
Jannik Kossen und Fabrizio Kuruc
|
||
|
||
13 Support Vector Machine
|
||
|
||
95
|
||
|
||
Jana Aberham und Fabrizio Kuruc
|
||
|
||
14 Logistische Regression
|
||
|
||
105
|
||
|
||
Theresa Schüler
|
||
|
||
15 Entscheidungsbäume
|
||
|
||
111
|
||
|
||
Jannik Kossen, Maike Elisa Müller und
|
||
|
||
Max Ruckriegel
|
||
|
||
Inhaltsverzeichnis XIII
|
||
|
||
16 Verzerrung-Varianz-Dilemma
|
||
|
||
119
|
||
|
||
Jannik Kossen und Maike Elisa Müller
|
||
|
||
17 Hauptkomponentenanalyse
|
||
|
||
125
|
||
|
||
Christian Hölzer
|
||
|
||
18 Eine kurze Geschichte der künstlichen
|
||
|
||
Intelligenz
|
||
|
||
135
|
||
|
||
Ina Kalder
|
||
|
||
19 Big Data
|
||
|
||
141
|
||
|
||
Christian Hölzer und Elena Natterer
|
||
|
||
20 Künstliche neuronale Netze
|
||
|
||
149
|
||
|
||
Leon Hetzel und Frederik Wangelik
|
||
|
||
21 Faltungsnetze
|
||
|
||
163
|
||
|
||
Jannik Kossen und Maike Elisa Müller
|
||
|
||
22 Gradientenabstiegsverfahren
|
||
|
||
171
|
||
|
||
Wolfgang Böttcher, Charlotte Bunne und
|
||
|
||
Johannes von Stetten
|
||
|
||
23 No Free Lunch Theorem
|
||
|
||
181
|
||
|
||
Maike Elisa Müller
|
||
|
||
24 Bayesregel
|
||
|
||
185
|
||
|
||
Justin Fehrling und Michael Krause
|
||
|
||
25 Generative gegnerische Netzwerke
|
||
|
||
195
|
||
|
||
Jannik Kossen und Maike Elisa Müller
|
||
|
||
26 Verstärkendes Lernen
|
||
|
||
203
|
||
|
||
Thomas Herrmann und Lars Frederik Peiss
|
||
|
||
XIV Inhaltsverzeichnis
|
||
Teil III Künstliche Intelligenz und Gesellschaft
|
||
|
||
27 Über die Mystifizierung von KI
|
||
|
||
215
|
||
|
||
Nicolas Berberich und Christian Hölzer
|
||
|
||
28 Künstliche Intelligenz und Sicherheit
|
||
|
||
223
|
||
|
||
Nicolas Berberich und Ina Kalder
|
||
|
||
29 Künstliche Intelligenz und Ethik
|
||
|
||
229
|
||
|
||
Nicolas Berberich
|
||
|
||
30 Schlusswort
|
||
|
||
241
|
||
|
||
Jannik Kossen, Maike Elisa Müller und
|
||
|
||
Elena Natterer
|
||
|
||
Teil I
|
||
Grundlagen
|
||
|
||
1
|
||
Einleitung
|
||
Lassen Sie uns loslegen!
|
||
Jannik Kossen, Fabrizio Kuruc und Maike Elisa Müller
|
||
|
||
Lisa und ihr Mitbewohner Max sitzen – wie jeden Tag – beim entspannten Sonntagsfrühstück in der Küche. „Glaubst du, die Menschen werden bald durch Roboter ersetzt?“, fragt Max mit einer Zeitung in der Hand. Lisa verdreht die Augen: „Nein?!“ Daraufhin streckt Max ihr den Zeitungsartikel entgegen: Ein Roboter mit roten Augen schaut Lisa direkt ins Gesicht und der Titel
|
||
|
||
J. Kossen (*) Universität Heidelberg, Heidelberg, aus Darmstadt, Deutschland E-Mail: jannik.kossen@gmail.com
|
||
F. Kuruc Buseck, Deutschland
|
||
M. E. Müller TU Berlin, Berlin, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
3
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_1
|
||
|
||
4 J. Kossen et al.
|
||
des Artikels lautet: „Sind wir bald alle überflüssig?“ Lisa schweigt, Max redet weiter: „Aber was da gerade alles passiert: Künstliche Intelligenz, schlaue Algorithmen, Big Data und Digitalisierung. Davon lese ich zurzeit überall. Gerade hat eine künstliche Intelligenz in dem Brettspiel ‚Go‘ den besten menschlichen Spieler geschlagen, und bald haben wir selbstfahrende Autos auf den Straßen. Gibt es eigentlich irgendetwas, das künstliche Intelligenz nicht kann?“ So ganz genau weiß das auch Lisa nicht. Aber irgendwie traut sie dem Braten nicht. Sie nimmt sich vor, herauszufinden, was hinter den Schlagzeilen steckt.
|
||
Was heißt es, wenn Maschinen lernen? Und wie kann Künstliches intelligent sein?
|
||
Oft denken wir an Roboter, selbstfahrende Autos und digitale Assistenten, wenn wir künstliche Intelligenz (KI) hören. Hinter künstlicher Intelligenz verbergen sich oft Methoden des sogenannten maschinellen Lernens (ML). Und tatsächlich begegnen uns diese „intelligenten“ Methoden an vielen Stellen des Alltags. Eine der einfachsten Anwendungen des maschinellen Lernens sind zum Beispiel Spamfilter. Diese sortieren die unerwünschte elektronische Post automatisch aus. Ein Algorithmus analysiert, welche E-Mails in der Vergangenheit von Ihnen als Spam bezeichnet worden sind. E-Mails mit Wortfolgen wie „extrem billig“, „super sexy“ oder „Millionengewinn – jetzt!“ können anschließend automatisch erkannt und ausgefiltert werden. Was genau Algorithmen und maschinelles Lernen sind, klären wir natürlich noch an späterer Stelle.
|
||
Auch beim Online-Versandhändler Amazon1 überlegen sich nicht unzählige Menschen explizit, welche
|
||
1https://www.amazon.com/gp/help/customer/display.html?nodeId=16465251, aufgerufen am 24.03.2019.
|
||
|
||
1 Einleitung 5
|
||
Produkte zusammenpassen könnten. Ein Algorithmus lernt aus den Einkäufen der Nutzerinnen und Nutzer in der Vergangenheit. Sobald Sie sich ein neues Produkt bei Amazon anschauen, bestimmt dieser Algorithmus andere Produkte, die dazu passen. Ähnliches gilt für Plattformen wie Netflix2 und Spotify3. Anhand der Aktivitäten der Nutzerinnen und Nutzer entscheidet ein Algorithmus, welche Filme, Serien oder Musik für Sie auch infrage kommen könnten. Wenn Sie ein großer „Harry Potter“-Fan sind, gefällt Ihnen wahrscheinlich auch „Der Herr der Ringe“ gut. Dies kann der Algorithmus berechnen, nachdem er aus den Daten gelernt hat. Und bei Facebook4 lernt ein Algorithmus Ihnen anhand Ihrer besuchten Seiten und „Gefällt mir“-Bewertungen passende Werbung zu präsentieren.
|
||
Wir möchten Ihnen mit diesem Buch eine leicht verständliche Einführung in die Welt der lernenden Maschinen bieten. Dazu stellen wir einflussreiche, weitverbreitete Algorithmen des maschinellen Lernens Schritt für Schritt und anschaulich vor. Sie benötigen dazu keine besonderen Vorkenntnisse. Jeder kann verstehen, wie diese Methoden funktionieren. Und Sie werden eine Vorstellung davon entwickeln, was diese Methoden leisten können, was (noch) nicht und was vermutlich nie. Dadurch wollen wir Licht in die Dunkelheit der Blackbox der künstlichen Intelligenz bringen.
|
||
Wir möchten als Autoren dieses Buches betonen, dass wir sowohl die Chancen als auch die Risiken künstlicher
|
||
2https://help.netflix.com/en/node/100639, aufgerufen am 24.03.2019. 3https://developer.spotify.com/documentation/web-api/reference/browse/ get-recommendations/, aufgerufen 24.03.2019. 4https://code.fb.com/core-data/recommending-items-to-more-than-a-billionpeople/, aufgerufen am 24.03.2019.
|
||
|
||
6 J. Kossen et al.
|
||
Intelligenz sehen. Allerdings geht es uns nicht darum, einzelne Anwendungen künstlicher Intelligenz zu bewerten oder zu entscheiden, ob diese nun gut oder schlecht sind. Unser Ziel ist es hingegen, sachlich über die Thematik zu informieren, um damit einen Beitrag zur Objektivierung der aktuellen Debatte zu liefern und aufzuklären. Der Zeitpunkt, über den Einsatz und die Folgen der künstlichen Intelligenz in der Gesellschaft zu diskutieren, ist spätestens jetzt. Für eine aufgeklärte Debatte mangelt es unserer Meinung nach vor allem an einem grundlegenden Verständnis darüber, was künstliche Intelligenz eigentlich ist und wie diese funktioniert. Nur mit einem solchen Grundverständnis lässt sich informiert über wichtige Themen, wie zum Beispiel die Ethik der KI oder die Fairness von algorithmischen Entscheidungen, reden. Wir hoffen, dass Ihnen dieses Buch helfen wird, dieses Grundverständnis zu entwickeln. Dann können wir angemessen über die Chancen und Risiken künstlicher Intelligenz diskutieren und gemeinsam unsere Zukunft gestalten.
|
||
Bevor wir loslegen, grenzen wir noch ein paar wesentliche Begriffe voneinander ab. Künstliche Intelligenz ist ein Oberbegriff, der immer dann benutzt wird, wenn Systeme Entscheidungen treffen, für die man vermutlich „Intelligenz“ besitzen muss – was auch immer das genau bedeutet. Diese recht schwammige Definition reicht nicht für philosophische Unterhaltungen über das Thema aus, aber sie drückt ganz gut aus, was wir unter künstlicher Intelligenz verstehen. Was unter diesen Begriff fällt, hängt allerdings auch von der Zeit ab, in der man sich befindet. Waren die Menschen vor einigen Jahren noch dazu bereit, Navigationssysteme als künstliche Intelligenz zu bezeichnen, so beeindrucken uns diese heutzutage schon lange nicht mehr. Vielleicht wird es selbstfahrenden Autos
|
||
|
||
1 Einleitung 7
|
||
dann bald ähnlich ergehen. Andere Definitionen von künstlicher Intelligenz beinhalten oft das Kriterium, dass „intelligente“ Systeme mit ihrer Umgebung interagieren müssen: Das heißt, Informationen aus der Umwelt aufzunehmen, auf diese zu reagieren, aus dieser zu lernen und daraus zukünftiges Verhalten abzuleiten.
|
||
Damit kommen wir zum Begriff des maschinellen Lernens. Maschinelles Lernen ist der Sammelbegriff für alle Computerprogramme, deren Verhalten nicht fest einprogrammiert ist. Stattdessen gibt man fest vor, wie diese aus Daten lernen. Aus den Daten kann dann das Verhalten der Computerprogramme in die gewünschte Richtung geformt werden. Maschinelles Lernen ist daher eine sehr beliebte Möglichkeit, Systeme zu erschaffen, die über künstliche Intelligenz verfügen.
|
||
Die Grundidee ist dabei folgende: Wir hätten gerne ein System, das eine bestimmte Aufgabe erledigt, zum Beispiel Tumore auf Röntgenbildern erkennt, Spam-Mails identifiziert oder uns den richtigen Film vorschlägt. Für diese Beispiele fällt es schwer, genau zu formulieren, wie die Aufgabe Schritt für Schritt zu lösen ist. Tumore können unterschiedlich aussehen oder sich an verschiedenen Stellen im Körper befinden; nicht jede E-Mail, die das Wort „Millionengewinn“ enthält, ist eine Spam-Mail; und nicht jeder mag dieselben Filme. Maschinelles Lernen löst dieses Problem meist mit Hilfe von zwei Zutaten: Zunächst brauchen wir Erfahrungswerte, etwa Röntgenbilder, bei denen wir wissen, ob sie einen Tumor enthalten; E-Mails, bei denen uns gesagt wurde, ob sie Spam sind; oder Filme, bei denen wir wissen, dass sie anderen, ähnlichen Nutzern in der Vergangenheit gefallen haben.
|
||
Die zweite Zutat sind Methoden, also Computerprogramme, um aus diesen Erfahrungswerten Muster zu
|
||
|
||
8 J. Kossen et al.
|
||
erkennen, z. B. welche Wortkombinationen auffällig für Spam-Mails sind. Ebenso verhält es sich mit Tumoren und Filmen. Aus Röntgenaufnahmen von gesunden und kranken Menschen lässt sich das Aussehen von Tumoren lernen. Aus den verschiedenen Filmbewertungen einzelner Nutzerinnen und Nutzer ergibt sich, welche Filme oft zusammen gemocht werden und welche Filme nicht zusammenpassen. Für unterschiedliche Aufgaben – ob die Erkennung von Tumoren auf Röntgenbildern, den Inhalten von Text, oder die Empfehlung von Filmen – gibt es auch verschiedene, angepasste Methoden. Einige wichtige davon werden wir in diesem Buch kennenlernen.
|
||
Genau genommen ist der der Begriff der künstlichen Intelligenz etwas weiter gefasst als der des maschinellen Lernens. Schließlich sind auch andere Wege denkbar, intelligent handelnde Systeme zu erschaffen. Im aktuellen Diskurs verbergen sich hinter künstlicher Intelligenz allerdings meist Systeme, die auf Methoden des maschinellen Lernens zurückgreifen. Denn aus den richtigen Daten lässt sich intelligent scheinendes Verhalten gut lernen. Dies erfährt man aber oft nicht und die mystische Aura der künstlichen Intelligenz ist alles, was zurückbleibt. Das ist schade, denn die Methoden des maschinellen Lernens lassen sich eigentlich gut erklären.
|
||
Begleiten Sie daher unsere Heldin „Machine-Learning-Lisa“, kurz Lisa, auf ihren Abenteuern durch die Welt des maschinellen Lernens (siehe Abb. 1.1). Anhand von Lisa und (mal mehr und mal weniger realistischen) Alltagsbeispielen werden wir die grundlegenden Methoden des maschinellen Lernens erklären. Fiebern Sie mit, wenn Lisa knifflige Probleme ihres Alltags durch maschinelles Lernen löst.
|
||
Teil I führt die grundlegenden Begriffe und Disziplinen des maschinellen Lernens ein. In Teil II, dem Hauptteil
|
||
|
||
1 Einleitung 9
|
||
Abb. 1.1 Lisa ist bereit für ihre Abenteuer!
|
||
des Buches, erklären wir Schritt für Schritt die Funktionsweisen zahlreicher Methoden des maschinellen Lernens. Und wenn Sie das Gefühl haben, dass es mal Zeit für eine Pause von den ganzen Algorithmen wäre, lohnt sich auf
|
||
|
||
10 J. Kossen et al.
|
||
jeden Fall ein Blick in den Schlussteil, Teil III. In diesem nehmen wir Abstand von den konkreten Algorithmen und diskutieren den Einsatz künstlicher Intelligenz in der Gesellschaft und den sich daraus ergebenden Fragen zur Sicherheit und Ethik von KI.
|
||
Schnappen Sie sich einen Tee oder Kaffee, lehnen Sie sich zurück und vor allem: Haben Sie viel Spaß beim Lesen!
|
||
|
||
2
|
||
Algorithmen
|
||
Über die Kunst, Computer zu Problemlösern zu machen
|
||
Nicolas Berberich
|
||
Zuallererst möchten wir einen zentralen Begriff der Informatik klären, der Ihnen in diesem Buch immer wieder begegnen wird, und zwar den des Algorithmus. Wir könnten das kurz und schmerzlos machen, indem wir Ihnen einfach eine Definition präsentieren.
|
||
Definition Algorithmus Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems. Eine Eingabe wird dabei in genau definierten Schritten zu einer Ausgabe umgewandelt.
|
||
|
||
N. Berberich (*) TU München und LMU München, München, Deutschland E-Mail: n.berberich@tum.de
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
11
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_2
|
||
|
||
12 N. Berberich
|
||
Zum besseren Verständnis sind jedoch konkrete Beispiele hilfreich und deutlich interessanter als reine Definitionen. Zum Glück hat unsere Lisa ein abenteuerliches Leben, in dem es nur so von Algorithmen wimmelt. So wie an diesem Sonntag. Endlich ist es soweit: Lisas Brieffreundin Jana aus Frankreich kommt sie besuchen. Lisa hat Jana versprochen, mit ihr deutsche Pfannkuchen zu backen. Wenn Lisa ihre Freundin das nächste Mal in Frankreich besucht, wird Jana sie dafür in die hohe Kunst der Crêpe-Zubereitung einführen. Ärgerlicherweise kann sich Lisa aber nicht mehr erinnern, wie genau Pfannkuchen zubereitet werden, und muss deshalb auf ein Backrezept zurückgreifen. Im Grunde ist ein Backrezept ein Algorithmus, denn es liefert eine genaue Handlungsvorschrift, nach der die Zutaten (die Eingabe des Algorithmus) in mehrere Pfannkuchen (die Ausgabe des Algorithmus) umgewandelt werden. Hier ist das Backrezept für das sich Lisa entscheidet:
|
||
Backrezept für Pfannkuchen: Eingabe (Zutaten): 400 g Mehl, 750 ml Milch, 3 Eier, 1 Prise Salz Handlungsvorschrift:
|
||
1. Mehl und Milch in einer Schüssel verrühren. 2. Eier und eine Prise Salz hinzugeben und verrühren. 3. Pfanne erhitzen. 4. Mit einer Schöpfkelle Teig in die Pfanne geben und
|
||
auf dem Pfannenboden verteilen. 5. Pfannkuchen bei mittlerer Hitze backen. 6. Wenn die Unterseite goldbraun ist, dann wende
|
||
den Pfannkuchen mit einem Pfannenwender.
|
||
|
||
2 Algorithmen 13
|
||
7. Wenn die zweite Seite goldbraun ist, dann nimm den Pfannkuchen mit dem Pfannenwender heraus.
|
||
8. Solange noch Teig übrig ist: Gehe zu Schritt 4. 9. Fertig! Guten Appetit! Ausgabe: 12 Pfannkuchen
|
||
Theoretisch könnte man einen solchen Algorithmus auch einem fortgeschrittenen Roboter übergeben und diesen die Handlungsschritte durchführen lassen. Wichtig ist, dass ein Algorithmus, der von einem Roboter oder einem Computer durchgeführt werden soll, sehr präzise formuliert ist und keine Mehrdeutigkeiten zulässt. Im Gegensatz zu einem Menschen verfügt ein Roboter nämlich nicht über einen gesunden Menschenverstand und weiß deshalb nicht, was „eine Prise“ Salz bedeutet. Hier müsste stattdessen eine genaue Mengenangabe stehen. Genauso müsste auch exakt vorgeschrieben werden, was mit „mittlerer Hitze“ und was genau mit „goldbraun“ gemeint ist.
|
||
Möchte man einen Algorithmus von einem Computer durchführen lassen, dann müssen Eingabe und Ausgabe natürlich digital sein – zum Beispiel Zahlen, Wörter oder digitale Dokumente. Ein einfaches Beispiel ist ein Algorithmus, der zwei Zahlen durch wiederholte Addition miteinander multipliziert.1
|
||
1Das Prinzip, eine Multiplikation durch wiederholte Addition in einer Rechenmaschine darzustellen, geht auf den Universalgelehrten Gottfried Wilhelm Leibniz zurück. Schon im Jahr 1673 – mehrere Jahrhunderte vor der Entwicklung von elektronischen Computern – stellte Leibniz in London der Royal Society das Modell einer mechanischen Rechenmaschine vor, welche alle vier Grundrechenarten beherrschte. Leibniz führte übrigens auch das Binärsystem in der europäischen Wissenschaft ein, nach dem alle Zahlen durch 0en und 1en dargestellt werden können und welches die Basis für alle digitalen Computer bildet.
|
||
|
||
14 N. Berberich
|
||
Dieser kann so aussehen (zum besseren Verständnis stehen die Beispielzahlen in eckigen Klammern):
|
||
Eingabe: zwei positive ganze Zahlen, die miteinander multipliziert werden sollen [z. B. 3 und 4]: Handlungsvorschrift:
|
||
1. Setze die Variable x zu Beginn auf 0. 2. Zähle von 0 in Einserschritten bis zur ersten Ein-
|
||
gabezahl [bis 3]. 3. Bei jedem dieser Einserschritte addiere die zweite
|
||
Zahl [4] auf x und speichere das Ergebnis erneut in x ab. 4. Nachdem du in Einserschritten bei der ersten Zahl [3] angekommen bist und das Ergebnis aktualisiert hast [12], bist du fertig. Ausgabe: Das Ergebnis ist das Produkt der beiden Eingabezahlen.
|
||
Auch wenn sich diese Vorschrift vielleicht etwas kompliziert gelesen hat, entspricht sie doch genau der Art und Weise, wie wir alle in der Grundschule Multiplizieren gelernt haben: Man erhält das Ergebnis von „3 mal 4“, wenn man 4 drei mal addiert: „3 * 4 = 4 + 4 + 4“.
|
||
Diese logische Struktur des Algorithmus kann mithilfe einer Programmiersprache in Computercode a ufgeschrieben werden. Effektiv funktioniert ein Algorithmus also wie eine Maschine, in die wir Dinge oben hineinwerfen (Eingabe) und aus der nach mehreren Verarbeitungsschritten unten ein Ergebnis herauskommt (Ausgabe). Was genau im Inneren des Algorithmus vor sich geht, ist häufig für Anwender gar nicht so wichtig. Deshalb werden Algorithmen manchmal als schwarze Boxen (engl. black boxes) betrachtet, in die
|
||
|
||
2 Algorithmen 15
|
||
man nicht hineinsehen kann und von denen man nur die Eingabe und Ausgabe kennt.
|
||
Dieses Blackbox-Denken kann aber auch gefährlich sein, weil man dadurch leicht übersieht, in welchen Fällen man den Algorithmus nicht einsetzen kann. Der obige Multiplikationsalgorithmus funktioniert beispielsweise nur für positive ganze Zahlen und nicht für die Multiplikation von zwei negativen Zahlen oder zwei Kommazahlen. Wann genau (also für welche Eingabewerte) ein Algorithmus eingesetzt werden kann und für welche Eingabewerte er falsche Ergebnisse liefert, kann man nur herausfinden, indem man die Blackbox öffnet und versucht, die Funktionsweise des Algorithmus nachzuvollziehen. Es wird in diesem Buch darum gehen, die Blackboxes der wichtigsten Algorithmen des maschinellen Lernens und der künstlichen Intelligenz zu öffnen.
|
||
Die Eingabe und Ausgabe eines Algorithmus können auch Positionen und Richtungen in der realen Welt sein (z. B. die eigene Position in einem Labyrinth und der Weg nach draußen). Das erkennen Lisa und Jana, als sie nach dem Verzehr ihrer Pfannkuchen zu einem Maislabyrinth fahren:
|
||
„Wie sollen wir hier jemals wieder herausfinden?“ Leicht genervt schaut sich Jana um. „Das sieht in allen Richtungen gleich aus. Überall diese blöden Pflanzen!“
|
||
Lisa fühlt sich etwas schuldig, schließlich hat sie ihre Freundin zum Besuch des Maislabyrinths überredet. Es dauert nicht lange, bis sich die beiden heillos verlaufen haben. Bei jeder Kreuzung eine zufällige Richtung zu wählen, war kein guter Plan gewesen, um aus dem Labyrinth zu kommen…
|
||
|
||
16 N. Berberich
|
||
„Wir brauchen eine richtige Strategie. Eine Vorschrift, nach der wir uns bei jeder Kreuzung für eine Richtung entscheiden können und damit nach draußen finden. Lass uns mal etwas nachdenken, bevor wir weiter planlos umherirren“, sagt Lisa. Obwohl Jana wenig überzeugt aussieht, nickt sie und setzt sich zum Nachdenken neben Lisa.
|
||
Seneca über Irrgärten
|
||
„Das eben geschieht den Menschen, die in einem Irrgarten hastig werden: Eben die Eile führt immer tiefer in die Irre.“
|
||
Lucius Annaeus Seneca (4 n. Chr.–65 n. Chr.)
|
||
Nach einigen Minuten hat sich Lisa eine Strategie überlegt. Sie möchte einfach immer an der rechten Wand entlang laufen und an jeder Kreuzung den Weg nehmen, der direkt rechts von ihrer Laufrichtung liegt.
|
||
Diese Strategie heißt Tiefensuche und lässt sich wie folgt in Algorithmenform schreiben:
|
||
Eingabe: Lisa und Jana im Inneren des Labyrinths. Handlungsvorschrift:
|
||
1. Wähle eine beliebige Richtung parallel zur Labyrinthwand.
|
||
2. Gehe an der rechten Labyrinthwand entlang, bis du am Ausgang des Labyrinths angekommen bist.
|
||
Ausgabe: Weg zum Ausgang des Labyrinths
|
||
Obwohl Jana der Zweifel an dieser Strategie ins Gesicht geschrieben steht, folgt sie ihrer Freundin Lisa. Und tatsächlich! Schon nach kurzer Zeit haben die beiden den Ausgang des Labyrinths gefunden. „War ja gar nicht so schwer, wie gedacht“, grinst Lisa zufrieden. In Abb. 2.1
|
||
|
||
2 Algorithmen 17
|
||
Abb. 2.1 Der Weg aus dem Labyrinth mithilfe des Tiefensuche-Algorithmus
|
||
ist der Weg eingezeichnet, den die beiden zurückgelegt haben.
|
||
Algorithmen werden meist in einer allgemeinen Form und damit unabhängig vom konkreten Problemfeld definiert. Das hat den Vorteil, dass sie damit auf eine große Anzahl verschiedener Problemfelder angewendet werden können. Die allgemeine Form des Algorithmus, den Lisa und Jana verwendet haben, um aus dem Labyrinth herauszufinden, wird Tiefensuche-Algorithmus genannt. Wie der Name schon andeutet, gehört der Tiefensuche-Algorithmus zur Gruppe der Suchalgorithmen. Neben dem Suchen eines Weges durch
|
||
|
||
18 N. Berberich
|
||
ein Labyrinth gehören Routenplaner in Navigationsgeräten und Suchmaschinen wie diejenige von Google zu den praktischen Anwendungen von Suchalgorithmen. Wie oben bereits erwähnt, ist es wichtig zu wissen, welche Algorithmen für eine bestimmte Aufgabe verwendet werden können und insbesondere, in welchen Situationen bestimmte Algorithmen nicht angewendet werden können. Der Tiefensuche-Algorithmus führt nach einiger Zeit immer zum Ziel, es sei denn, im Labyrinth gibt es Zyklen. Ein Zyklus ist ein Rundweg, bei dem man immer wieder und ohne Ende an bereits besuchte Kreuzungen kommt. Ein Mensch würde nach einigen Runden im Kreis stutzig werden, seinen gesunden Menschenverstand einschalten und die Strategie abwandeln. Ein Computer oder Roboter weicht hingegen von seinem Algorithmus nicht ab und würde bis in alle Ewigkeit seine Runden drehen (siehe Abb. 2.2).
|
||
Abb. 2.2 Der Tiefensuche-Algorithmus kann auf manche Probleme angewendet zu Endlosschleifen führen. Deshalb muss auf Zyklen geprüft werden. Man sollte im Allgemeinen Algorithmen nicht blind anwenden, sondern deren Begrenzungen beachten
|
||
|
||
2 Algorithmen 19
|
||
Albert Einstein hat angeblich einmal gesagt: „Die Definition von Wahnsinn ist, immer wieder das Gleiche zu tun und andere Ergebnisse zu erwarten.“ Für intelligentes Verhalten ist es notwendig, aus Erfahrung lernen zu können und das eigene Handeln entsprechend anzupassen. Auch dafür gibt es Algorithmen. Diese definieren eine Strategie, wie Erfahrungen in Form von Daten zum Lernen genutzt werden können. So kann die Leistungsfähigkeit eines Computers in Bezug auf eine bestimmte Problemstellung verbessert werden. Man gibt den Algorithmen also nicht vor, wie genau sie ein Problem zu lösen haben, sondern stattdessen, wie sie aus ihrer Erfahrung lernen können, das Problem besser zu lösen.
|
||
Der Teilbereich der künstlichen Intelligenz, der sich mit diesen Lernalgorithmen beschäftigt, wird maschinelles Lernen genannt und ist für die meisten der neuesten Erfolgsmeldungen im Bereich der künstlichen Intelligenz verantwortlich. Deshalb fokussieren wir uns in diesem Buch auf Lernalgorithmen (und nicht auf Back-, Multiplikations- oder Suchalgorithmen). Die Anwendung von maschinellem Lernen auf KI-Probleme läuft in zwei Schritten ab: Algorithmen der klassischen KI, wie zum Beispiel Suchalgorithmen, können direkt auf eine Problemstellung angewendet werden. Beim maschinellen Lernen hingegen wird zuerst mit Hilfe von Trainingsdaten (z. B. Erfahrungswerten) unter Anwendung eines Lernalgorithmus in der sogenannten Trainingsphase ein Modell gelernt. Dieses gelernte Modell kann dann in einem zweiten Schritt, der Test- oder Anwendungsphase, auf eine Problemstellung angewendet werden. Was unter dem Begriff Modell in diesem Zusammenhang zu verstehen ist, welche verschiedenen Modelle es im maschinellen Lernen gibt und wie diese mit Hilfe von Lernalgorithmen gelernt werden, darum geht es in diesem Buch.
|
||
|
||
20 N. Berberich
|
||
Interessanterweise sind die meisten Lernalgorithmen gar nicht besonders neu, sondern wurden bereits vor Jahrzehnten entwickelt. Neu ist jedoch die gigantische Menge an Daten, dank günstiger Sensoren und dem Internet, sowie modernen Computerchips, auf denen die Lernalgorithmen besonders effizient angewendet werden können. Das bedeutet aber nicht, dass die Algorithmen selbst unwichtig geworden sind. Ganz im Gegenteil! Denn genau wie bei den Suchalgorithmen geben auch die Algorithmen des maschinellen Lernens vor, wofür man maschinelles Lernen verwenden kann und wo dessen Grenzen und Risiken liegen.
|
||
Treiber der Erfolgsgeschichte des maschinellen Lernens
|
||
Das Zusammenspiel von Algorithmen, Daten und Computer-Hardware bildet das Herz der Erfolgsgeschichte des maschinellen Lernens.
|
||
Im nächsten Kapitel stellen wir das Feld des maschinellen Lernens noch genauer vor und zeigen, in welche drei Bereiche es sich einteilen lässt.
|
||
|
||
3
|
||
Maschinelles Lernen
|
||
Wie sich Computer an Probleme anpassen
|
||
Michael Krause und Elena Natterer
|
||
|
||
Während Lisa und ihre Freundin im vorherigen Kapitel Pfannkuchen backten und im Maislabyrinth umherirrten, haben wir den Begriff des Algorithmus kennengelernt. Wir erinnern uns, dass ein Algorithmus eine eindeutige Handlungsanweisung ist. Man gibt dem Algorithmus eine Eingabe (die Zutaten für Pfannkuchen) und er verarbeitet diese nach einem festen Handlungsmuster (einem Rezept). Hat er diese Handlungsanweisung abgearbeitet, gibt er seine Ausgabe zurück (die Pfannkuchen). Für manche Probleme ist es aber viel schwieriger, ein festes Handlungsmuster aufzustellen, als für das Backen von Pfannkuchen
|
||
|
||
M. Krause (*) Lemgo, Deutschland E-Mail: michael.krause@rwth-aachen.de
|
||
E. Natterer Tübingen, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
21
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_3
|
||
|
||
22 M. Krause und E. Natterer
|
||
oder das Durchqueren eines Labyrinths. Lernalgorithmen treffen Entscheidungen daher aufgrund von Erfahrungswerten. Diese Erfahrungswerte werden dem Algorithmus in Form von Daten gegeben.
|
||
Ein Beispiel dafür ist Lisa, die sich entschließt, das Pfannkuchenrezept etwas an ihren Geschmack anzupassen. Wenn sie findet, dass der Pfannkuchenteig zu flüssig ist, beschließt sie, beim nächsten Mal etwas weniger Milch in den Teig zu geben. Oder sie könnte die Pfannkuchen nicht süß genug finden und deswegen das nächste Mal etwas mehr Zucker in den Teig geben. Um in die Lage zu kommen, das Rezept zu verändern, muss Lisa es allerdings erst ein paar Mal zubereitet haben und Erfahrungswerte damit sammeln. Dabei wird sie wohl niemals voll und ganz vom Rezept abweichen, aber kleine Stellschrauben anpassen.
|
||
Damit kann ein Lernalgorithmus für viele Varianten eines Problems angewendet werden, die sich nicht mit einem festen, unabänderlichen Rezept abdecken lassen. Auch Lernalgorithmen folgen Regeln – sie sind nicht „kreativ“ oder „denkend“. Doch die Regeln von Lernalgorithmen basieren zusätzlich auf Daten. Die Disziplin, die sich mit diesen Typen von Algorithmen beschäftigt, heißt maschinelles Lernen. Viele ihrer Methoden haben aber ursprünglich nichts mit Maschinen zu tun, sondern wurden interdisziplinär von Kognitionswissenschaftlerinnen, Psychologen, Mathematikern, Neurowissenschaftlerinnen“ und Informatikern entwickelt.
|
||
Bei Lernalgorithmen unterscheidet man drei Haupttypen:
|
||
1. Überwachtes Lernen 2. Unüberwachtes Lernen 3. Verstärkendes Lernen
|
||
|
||
3 Maschinelles Lernen 23
|
||
Hier erklären wir kurz die ersten beiden Typen von Lernalgorithmen. Verstärkendes Lernen behandeln wir in Kap. 26.
|
||
Lisa arbeitet an einem Projekt zum Bienensterben und muss dafür Bilder von verschiedenen Bienen in unterschiedliche Arten einteilen: Die westliche Honigbiene, die Sandbiene, die Holzbiene, die Wespenbiene und die Blattschneiderbiene (siehe Abb. 3.1).
|
||
Das einzige Problem ist, dass Lisa nicht 10, nicht 20, nicht 100, sondern sage und schreibe 800 Bilder einteilen soll und zu allem Überfluss in den nächsten Tagen eine Klausur schreibt. Wie gut, dass Lisa ihre kleinen Brüder Leon und Lars hat, die nur allzu viel Zeit haben und ihrer älteren Schwester gerne helfen.
|
||
Lisa beschließt, ihren Brüdern zunächst 100 Bilder zur Probe zu geben. Sobald einer der beiden es schafft, die Bilder gut aufzuteilen, möchte sie ihm die restlichen 700 geben.
|
||
Die 100 Bilder teilt sie weiterhin auf, in Testdaten und Trainingsdaten.
|
||
Die Trainingsdaten sind Bilder, welche Lisa ihren Brüdern gibt, um sie auf die Aufgabe vorzubereiten. Die Testdaten sind einige Bilder, die sie zur Seite legt und mit denen sie später überprüfen möchte, wie viele Fehler ihre Brüder tatsächlich machen. Hierin liegt der wichtige Unterschied zwischen den Testdaten und dem „Rest der
|
||
Abb. 3.1 Fünf Beispielbienen aus Lisas Katalog
|
||
|
||
24 M. Krause und E. Natterer
|
||
Bilder“, also der 700 Exemplare von vorher: Auf den Testdaten schaut Lisa noch nach, ob die Zuordnung richtig war. Auf den restlichen Daten (700 in diesem Fall) lässt sie bloß noch ihre Brüder Vorhersagen treffen: Bei diesen Daten werden falsche Zuordnungen also nicht mehr korrigiert.
|
||
Es gibt keine klare Regel, wie viel Prozent der Daten Trainingsdaten und wie viel Prozent der Daten Testdaten sein sollen, aber in der Praxis ist das Verhältnis bei ca. 70:30. In unserem Beispiel hat Lisa also 70 Bilder als Trainingsdaten und 30 Bilder als Testdaten ausgewählt.
|
||
Leon ist der jüngere der beiden Brüder. Daher bereitet Lisa die 70 Bilder der Trainingsdaten für ihn etwas vor: Sie schaut sich die Bilder genau an und schlägt im Internet nach, um welche Biene es sich jeweils handelt. Für jede Bienenart bildet sie dann einen Stapel. Diese gibt sie ihrem Bruder. Leon versucht anhand der Stapel das Aussehen und die Unterschiede der verschiedenen Bienenarten zu lernen. Dabei betrachtet er Merkmale wie Länge der Flügel, Größe der Augen oder Farbe des Pelzes. Hierin liegt das Lernen im Lernalgorithmus: Ein Lernalgorithmus (hier Leon) verarbeitet solche Merkmale, mit denen die Bilder sortiert werden können.
|
||
Anschließend erhält Leon von Lisa die 30 Bilder der Testdaten und ordnet jedes davon einem der Bienenarten zu. Auch wenn Leon sich bei einem Bild unsicher ist und findet, dass es auf keinen Stapel so richtig gut passt, legt er das Bild trotzdem auf einen der Stapel ab (der eben seiner Einschätzung nach einer bestimmten Biene am ähnlichsten sieht). In so eine Situation könnte er zum Beispiel kommen, wenn er das Bild einer weiblichen Holzbiene auf einen Stapel legen möchte, auf dem bisher nur männliche Holzbienen liegen, die etwas anders aussehen. Zum
|
||
|
||
3 Maschinelles Lernen 25
|
||
Schluss kontrolliert Lisa, wie viele der 30 Bilder Leon richtig zugeordnet hat. Damit kann sie abschätzen, wie viele Fehler er wohl auf den 700 restlichen Daten machen wird.
|
||
Diesen Lernvorgang nennen wir überwachtes Lernen. Tatsächlich hat Leon bei sieben Bienen einen Fehler gemacht. Diese sollten eigentlich auf einem anderen Stapel landen.
|
||
Lars ist schon älter. Lisa beschließt daher, ihm für die 70 Bilder der Trainingsdaten nicht vorab die zugehörige Bienenart zu verraten. Lars schaut sich also die Trainingsbilder an und teilt diese in Stapel ein. Ebenso wie beim überwachten Lernen kann er die Einteilung auch hier anhand von Merkmalen wie Länge der Zunge, Größe der Augen oder Farbe des Pelzes, vornehmen. Im Unterschied zum überwachten Lernen kennt er aber weder für Testnoch für Trainingsdaten die richtige Bienenart. Diese Form des Lernens bezeichnet man als unüberwachtes Lernen.
|
||
Einem Algorithmus beizubringen, aufgrund welcher Merkmale Bienen (oder Anderes) sich ähnlich sehen, ist eine der großen Herausforderungen des unüberwachten Lernens. Männliche Bienen haben beispielsweise tendenziell größere Augen und einen größeren Körper als ihr weibliches Pendant. Wenn der Algorithmus also die Augen- oder Körpergröße als Merkmal lernt, so würde die Einteilung vermutlich nicht in Arten, sondern nach Geschlecht vorgenommen werden. Auch Lars könnte so etwas passieren. Denn vielleicht sortiert er die Bilder ja nach der Länge der Flügel. Die hängt aber eher vom Entwicklungsstadium der Biene als von ihrer Art ab. Die resultierenden Stapel würden dann nicht unbedingt Bienenarten entsprechen.
|
||
Auf den Trainingsdaten hat sich Lars überlegt, welche verschiedenen Bienenarten es geben könnte und diesen
|
||
|
||
26 M. Krause und E. Natterer
|
||
jeweils einen Stapel zugeordnet. Auf den Trainingsdaten lernt der Bruder (oder der Algorithmus) also Zusammenhänge zwischen den Merkmalen. Die 30 Testbilder ordnet Lars nun den Stapeln zu, die er gebildet hat, wendet also die gelernte Regel nur noch an. Wenn die Stapel Entwicklungsstadien oder Geschlechter und nicht Bienenarten darstellen würden, dann wäre das jetzt natürlich ärgerlich: denn so müsste Lars (oder auch Lisa) alles nochmal machen. Am Ende findet Lisa heraus, dass Lars zwar fünf Stapel gebildet hat, die auch in etwa den Bienenarten entsprechen. Dennoch hat er zwölf Bilder der Testdaten falsch zugeordnet.
|
||
Die Bezeichnungen als überwachtes und unüberwachtes Lernen mag für den einen oder anderen etwas irreführend klingen, denn es geht nicht um eine „Überwachung“ der Algorithmen, sondern vielmehr um die Form der Eingabe: Wenn dem Lernalgorithmus die richtige Lösung auf den Trainingsdaten bekannt ist, spricht man von überwachtem Lernen, sonst von unüberwachtem Lernen.
|
||
Lisa erkennt also, dass Leon nur 7 Fehler gemacht hat, Lars hingegen 12 Fehler. Welchem der beiden soll sie also wichtige Aufgaben wie diese anvertrauen? Sie steht vor einem Dilemma: Auf der einen Seite möchte sie möglichst wenig falsche Zuordnungen haben, und das spricht für Leon. Auf der anderen Seite spart es Lisa natürlich eine ganze Menge Zeit, wenn sie die Trainingsbilder nicht vorher zuordnen muss, wie sie es bei Lars gemacht hat. Es gibt also keine klare Lösung, welchen der beiden Lisa bevorzugen sollte, wenn sie für ihr nächstes Projekt Bilder von Bäumen sortieren soll.
|
||
Beispiele für überwachtes Lernen sind Regression oder Klassifizierung (Kap. 5 und 6). Ein Beispiel für unüberwachtes Lernen ist Clustering (Kap. 7).
|
||
|
||
3 Maschinelles Lernen 27
|
||
Unüberwachte maschinelle Lernverfahren werden häufig verwendet, um Übersicht in riesigen Datenbanken zu schaffen. Es ist also wie „Lernen ohne Lehrer“: Durch Beobachtung werden Strukturen in den Daten gefunden. Dies kann allerdings auch dazu führen, dass die Merkmale, nach denen sortiert wird, gar nicht so viel Sinn ergeben, wie es auch bei Lars der Fall hätte sein können.
|
||
Für verschiedene Probleme gibt es verschiedene Lernalgorithmen. Ein Algorithmus, der auf bestimmten Daten sehr erfolgreich ist, kann auf anderen grandios scheitern – siehe auch Kap. 23 zu „No Free Lunch“.
|
||
Menschen lernen ihr ganzes Leben lang und machen eine Vielzahl von Erfahrungen, sodass sie auch neue Aufgaben (wie etwa Bilder von Bienen zu sortieren) recht schnell meistern können. Ein Lernalgorithmus lernt jedoch von Grund auf. Deshalb brauchen Lernalgorithmen tendenziell viel mehr Beispiele als Menschen, um zugrunde liegende Muster zu erkennen oder Entscheidungen zu treffen. Dementsprechend wird, je mehr Daten für das Training zur Verfügung stehen, im Allgemeinen auch die Auswertung auf den Testdaten besser. In der Praxis brauchen überwachte Lernalgorithmen nicht nur ein paar Dutzend, sondern typischerweise Tausende von Beispielen, die zunächst aufwendig von Hand zugeordnet werden müssen. Dies erklärt auch, wieso mit dem Aufkommen riesiger Datenmengen im Zuge der Digitalisierung solche Lernalgorithmen immer erfolgreicher wurden. Ist ein Lernalgorithmus dann auf den Trainingsdaten für seine Aufgabe vorbereitet und auf den Testdaten auf seine Güte geprüft worden, so kann er anschließend tatsächlich angewandt werden. Da Daten für ein erfolgreiches Lernen so wichtig
|
||
sind, werden wir diese im nächsten Kapitel besprechen.
|
||
|
||
4
|
||
Daten
|
||
Der unsichtbare Rohstoff
|
||
Alexandros Gilch und Theresa Schüler
|
||
|
||
Der Begriff des maschinellen Lernens fällt häufig im Zusammenhang mit den großen Internetfirmen unserer Zeit, wie Google, Facebook oder Amazon. Diese Unternehmen sind bekannt dafür, viele Daten von und über ihre Nutzerinnen und Nutzer zu sammeln. Gleichzeitig sind diese Firmen auch Vorreiter im Bereich des maschinellen Lernens. Dieser Zusammenhang ist kein Zufall. Stattdessen zeigt sich daran, dass viele Methoden des maschinellen Lernens erst auf großen Datenmengen ihr volles Potenzial entfalten. Überhaupt sind Daten die
|
||
|
||
A. Gilch (*) Universität Bonn, Bonn, Deutschland E-Mail: alexandros.gilch@freenet.de
|
||
T. Schüler Ruhr-Universität Bochum, Bochum, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
29
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_4
|
||
|
||
30 A. Gilch und T. Schüler
|
||
Grundzutat jedes lernenden Algorithmus. Wir wollen uns deshalb in diesem Kapitel damit beschäftigen, was Daten überhaupt sind, welche Probleme auftauchen können, wenn wir Schlüsse aus ihnen ziehen, und wie wir die Daten für das maschinelle Lernen vorbereiten sollten.
|
||
Ein klassisches Beispiel für maschinelles Lernen ist das Geschäftsmodell der Streaming-Anbieter im Internet – man denke zum Beispiel an Netflix, Maxdome oder Amazon Prime. Diese Unternehmen arbeiten permanent daran, ihr Film- und Serienangebot zu verbessern, und möchten gleichzeitig ihren Abonnenten individuell passende Filmvorschläge unterbreiten. Da es meist eine große Zahl an Nutzerprofilen gibt, ist es für die Streaming-Anbieter nicht möglich, genügend Mitarbeiter einzustellen, die diese individuellen Vorschläge und Vorhersagen „per Hand“ erstellen. Stattdessen sollen die Empfehlungen, basierend auf den vorhandenen Nutzerdaten, automatisch abgegeben werden. Wie so etwas funktioniert und was man sich genau unter dem Daten-Begriff vorstellen kann, schauen wir uns gemeinsam mit unserer Protagonistin Lisa an.
|
||
Lisas Cousin Fred hat in Berlin mit zwei Freunden ein Streaming-Start-up namens Watch ‘n’ Chill gegründet. Auch Lisa zählt zu den Abonnenten von Watch ‘n’ Chill und interessiert sich besonders für Actionfilme und Krimiserien. Sie mag aber auch französische Komödien, da Französisch in der Schule eines ihrer Lieblingsfächer war. Das Ratingsystem von Watch ‘n’ Chill versucht, Lisas Vorlieben kennenzulernen. Auf einer Skala von 0 bis 5 kann sie daher angeben, ob ihr ein gewisser Film gefallen hat. Zusätzlich werden bereits geschaute Filme und Serien protokolliert.
|
||
Dies reicht aber noch nicht aus, um automatisch zu entscheiden, was Lisa sonst gefallen könnte – Watch ‘n’ Chill braucht noch viel mehr Daten! Es wird zum Beispiel nicht nur dokumentiert, welche Filme Lisa bisher
|
||
|
||
4 Daten 31
|
||
angesehen hat, sondern auch, zu welcher Tageszeit sie dies tat und ob sie bis zum Ende durchgehalten hat. Ist dies nicht der Fall, so merkt sich Watch ‘n’ Chill an welcher Stelle Lisa den Film abgebrochen hat.
|
||
Wozu ist das gut? Obwohl sie der gleichen Kategorie angehören, sind manche Actionfilme brutaler als andere. Lisa mag aber keine brutalen Szenen und hat Filme aus diesem Grund schon häufiger ausgeschaltet. Mithilfe dieser Informationen lernt das Unternehmen, dass es für Lisa eine weitere Unterteilung der Kategorie „Actionfilme“ vornehmen sollte. Ein weiterer essenzieller Teil der Vorhersagen besteht darin, Lisas Vorlieben mit denjenigen anderer Nutzerinnen und Nutzer zu vergleichen. Bezogen auf französische Komödien bedeutet das: Falls viele andere Abonnenten neben französischen Komödien auch schwedische Komödien anschauen, so werden auch Lisa schwedische Komödien vorgeschlagen. Wäre die Kombination von französischen und schwedischen Komödien jedoch eher unüblich, so würde Watch ‘n’ Chill Lisa vielleicht eher belgische oder spanische Komödien empfehlen. Auch um sein Gesamtangebot zu verbessern, beobachtet das Start-up das Verhalten seiner Abonnenten sehr genau. Falls die Menschen zum Beispiel überproportional viele Kochshows ansehen, so wird das Angebot in diesem Bereich voraussichtlich zukünftig ausgebaut werden.
|
||
Wir wollen die Daten, die das Start-up Watch ‘n’ Chill sammelt, nun etwas näher ergründen und insbesondere verstehen, wie man sie sinnvoll in verschiedene Typen einteilen könnte. In jeglichen Anwendungen des maschinellen Lernens kommt nur eine begrenzte Anzahl an verschiedenen Datentypen vor. Daher führt ein besseres Verständnis der wichtigsten Datentypen auch zu einem besseren Verständnis von maschinellem Lernen im Allgemeinen.
|
||
|
||
32 A. Gilch und T. Schüler
|
||
Der erste Datentyp, den wir betrachten, ist derjenige der kategorischen Daten. Um Vorhersagen über die Filmvorlieben seiner Nutzerinnen und Nutzer machen zu können, sammelt das Unternehmen Watch ‘n’ Chill zunächst einmal ganz allgemeine Informationen über die Abonnenten wie ihr Geschlecht und ihr Bundesland. Dies könnte schließlich bereits ein Indiz für den Geschmack der jeweiligen Nutzer sein. Die Variable „Geschlecht“ hat hier drei mögliche Ausprägungen – weiblich, männlich und divers. Auch die Variable „Bundesland“ besitzt nur einige wenige Ausprägungen – nämlich exakt 16. Um später mit diesen Daten weiterarbeiten zu können, wird jeder möglichen Ausprägung eine Zahl als Platzhalter zugewiesen. Die Werte dieser Zahlen sind jedoch willkürlich und sagen nichts über die Daten selbst aus. Die Ausprägungen können wie unsortierte Schubladen (oder Kategorien) verstanden werden. Man könnte die Schubladen für die Variable „Geschlecht“ also sowohl mit den Zahlen 0, 1 und 2 kennzeichnen als auch mit den Werten 255, 17 und 57. Wichtig ist nur, dass sich die drei Zahlen unterscheiden.
|
||
Der nächste Datentyp, den wir uns anschauen wollen, ist dem der kategorischen Daten sehr ähnlich und versteckt sich hinter dem Ratingsystem des Unternehmens Watch ‘n’ Chill Es geht um sogenannte ordinale Daten. Die Abonnenten werden dazu aufgefordert, zu verschiedenen Filmen und Filmkategorien eine Bewertung in Form einer ganzen Zahl zwischen 0 („gefällt mir gar nicht“) und 5 („gefällt mir äußerst gut“) abzugeben. Diese sechs möglichen Antworten stellen also sechs verschiedene Schubladen bzw. Kategorien dar, in die die jeweilige Bewertung einsortiert werden kann. Genau wie bei den kategorischen Daten fällt bei ordinalen Daten auf, dass die tatsächlichen Zahlenwerte keine nähere Bedeutung
|
||
|
||
4 Daten 33
|
||
aufweisen. Nun kommt es aber auf die Reihenfolge der Schubladen an. Anstatt einer Skala von 0 bis 5 hätte man zum Beispiel auch eine Skala mit den Zahlen 0, 2, 4, 6, 8 und 10 verwenden können – die Abstände zwischen den Zahlen spielen keine Rolle, die Reihenfolge jedoch schon.
|
||
Bei einer weiteren Datenform geht es um diskrete Daten (oder auch Zähldaten ). Fred und seine Freunde bei Watch ‘n’ Chill wollen ihr Filmangebot im Allgemeinen verbessern und zu diesem Zweck wird für jeden Film ermittelt, wie viele Nutzer sich den Film vom Anfang bis zum Ende anschauen. Da man hierbei eine Anzahl ermittelt, handelt es sich um ein Zähldatenbeispiel. Zähldaten liefern „echte Zahlen“, die man zum Beispiel addieren kann, wohingegen die Zahlen im Falle von ordinalen Daten nur „Platzhalter“ sind, die bis auf ihre Reihenfolge keine tiefere Bedeutung haben.
|
||
Zuletzt lernen wir noch stetige Daten kennen. Wie bereits beschrieben, ermittelt das Start-up Watch ‘n’ Chill jedes Mal die genaue Stelle, an der ein Abonnent einen Film abbricht. Konkreter wird die genaue Zeit gemessen, bis zu welcher der Film noch lief. Da dort jeder mögliche Wert erscheinen könnte (zumindest, falls er größer als 0 s und kleiner als die Gesamtlänge des Films ist), handelt es sich um Daten, die jeden beliebigen Wert auf dem Zahlenstrahl annehmen können, insbesondere auch Kommazahlen. Dies ist das essenzielle Merkmal für stetige Daten.
|
||
Alle Daten, die das Unternehmen Watch ‘n’ Chill sammelt, kann man in einen der oben beschriebenen Datentypen einordnen. Dies ist jedoch nicht immer offensichtlich: Stellen wir uns vor, dass Fred mit seinem Unternehmen neue, innovative Wege beschreiten möchte, um die Kundenzufriedenheit zu erhöhen. Dazu
|
||
|
||
34 A. Gilch und T. Schüler
|
||
lässt er bei einer Testgruppe beobachten, wie aufmerksam und interessiert sie die Sendungen verfolgen, indem er Audiodaten während des Zuschauens aufnimmt. Sind die Zuschauer zum Beispiel abgelenkt und unterhalten sich, so ist die Sendung vermutlich nicht interessant für sie. Bei einer Komödie dagegen ist häufiges Lachen ein sehr positives Zeichen. Diese Daten lässt Fred erheben, indem ein Mikrofon alle zwei Sekunden die aktuelle Lautstärke als Zahlenwert aufnimmt. Die einzelnen Datenpunkte werden nun über die gesamte Filmlaufzeit in eine Liste geschrieben. So hat Fred für jeden Nutzer in der Testgruppe und jeden gesehenen Film ein Audioprofil ermittelt, mithilfe dessen er Rückschlüsse über die Zufriedenheit seiner Kunden ziehen kann. Auch wenn es vielleicht nicht offensichtlich erscheint, handelt es sich bei so einer Liste um eine sehr komplexe Ausprägung von stetigen Daten. Natürlich hat sich Fred von seinen Nutzerinnen und Nutzern zuvor die ausdrückliche Genehmigung für sein Vorgehen eingeholt!
|
||
Worauf muss Fred nun aber bei der Datensammlung achten?
|
||
Zunächst einmal ist es unerlässlich, genügend Daten zur Verfügung zu haben. Gehen wir dazu noch einmal zurück zu dem Rating-Beispiel. Ganz zu Anfang ihres Abonnements hat Lisa vielleicht erst drei Filme bewertet. Mit dieser Information allein ist es schwierig zu entscheiden, welche Filme Lisa noch gefallen könnten. Vielleicht gefällt Lisa zum Beispiel der Film Pippi Langstrumpf, da er in ihrer Kindheit ihr Lieblingsfilm war. Trotzdem ist diese Information wahrscheinlich nicht ausschlaggebend dafür, welche Filme Lisa heutzutage noch gerne anschauen würde.
|
||
|
||
4 Daten 35
|
||
Ein weiterer wichtiger Punkt neben der Datenmenge betrifft die Repräsentativität der Daten. Kurz nachdem Fred und seine Freunde das Start-up gegründet haben, bestand der Großteil ihrer Abonnenten aus jungen Studierenden. Ihr Ziel war es jedoch von Anfang an, auch für ältere Menschen ein ansprechendes Film- und Serienangebot zur Verfügung zu stellen. Daher wäre es nicht aussagekräftig gewesen, das gesamte Angebot nur auf Grundlage der Daten, die mithilfe der ersten Abonnenten gesammelt wurden, auszurichten. Ein Lernalgorithmus, der nur auf den Daten der jungen anfänglichen Abonnenten basiert, hätte älteren Zuschauern wahrscheinlich nur Filme für Studierende empfohlen.
|
||
Auch muss Fred darauf achten, dass bei der Datenerfassung keine grundsätzlichen Fehler auftreten. Zum Beispiel zeigte Watch ‘n’ Chill in seinen Anfangstagen zu Beginn eines jeden Films einen 30-sekündigen Trailer zu einem anderen, für den Zuschauer wahrscheinlich interessanten Film. Wären diese 30 s nun fälschlicherweise in die Filmzeit eingerechnet worden, hätte man falsche Rückschlüsse über die Abbruchzeitpunkte gezogen.
|
||
Trotz aller Vorsichtsmaßnahmen kann Fred dennoch nicht sicherstellen, dass die gesammelten Daten von einheitlich guter Qualität sind. Es könnte bei den von Watch ‘n’ Chill aufgenommenen Audiodaten zum Beispiel passieren, dass die Mikrofone ungenau sind und somit keine exakten Ergebnisse liefern. Generell sind Messungen nie absolut genau, sondern liegen immer im Bereich einer gewissen Fehlertoleranz. Ebenso können Sensoren ausfallen, sodass Lücken in der Datenerfassung auftreten.
|
||
Anwender von maschinellem Lernen müssen auch darauf Acht geben, dass sie keine Fehler bei der Interpretation ihrer Daten machen. Beispielsweise müssen Daten, die
|
||
|
||
36 A. Gilch und T. Schüler
|
||
aus verschiedenen Quellen stammen, richtig zusammengeführt werden. Möchten Fred und seine Freunde ihr Start-up vielleicht mit einem anderen Streaming-Start-up aus Köln fusionieren, so müssen die bisher erhobenen Daten der beiden Start-ups natürlich in eine gemeinsame Datenbank eingepflegt werden. Würde das Start-up aus Köln beispielsweise ein Ratingsystem mit maximal drei statt fünf Sternen verwenden, so müssten sich die Jungunternehmer eine Methode überlegen, diese sinnvoll ineinander umzurechnen.
|
||
Um all diese Probleme zu lösen, ist der Prozess der sogenannten Datenaufbereitung unerlässlich: So wendet ein Datenexperte häufig mehr Zeit dafür auf, unvollständige oder miteinander inkompatible Daten für den Algorithmus vorzubereiten, beziehungsweise den Algorithmus auf den Umgang mit fehlerbehafteten Daten einzustellen, als überhaupt den richtigen Algorithmus für das Problem zu finden.
|
||
Wir haben gesehen, dass Daten der Grundstoff für maschinelles Lernen sind und in den verschiedensten Formen auftreten können. Die Vorbereitung der Daten für den Lernalgorithmus ist dabei ein zweistufiger, arbeitsaufwendiger Prozess. In einem ersten Arbeitsschritt müssen geeignete Datenquellen erschlossen und die jeweiligen Daten erfasst werden. Auch wenn der erste Schritt durchgeführt wurde, müssen diese Daten in einem zweiten Arbeitsschritt aufbereitet werden, da beispielsweise unvermeidbare Messfehler auftreten können.
|
||
In den folgenden Kapiteln werden wir meist voraussetzen, dass Lisa und ihre Freunde bereits über die richtigen, vollständigen und bereinigten Daten verfügen, um uns ganz darauf konzentrieren zu können, wie Lernalgorithmen funktionieren. Wir unterscheiden bei den Lernalgorithmen des maschinellen Lernens zwischen
|
||
|
||
4 Daten 37
|
||
Regression, Klassifikation und Clustering. Die folgenden Kapitel führen diese Begriffe ein. Die im zweiten Teil vorgestellten Methoden lassen sich immer (mindestens) einem der drei Begriffe zuordnen.
|
||
|
||
5
|
||
Regression
|
||
Voll im Trend
|
||
Jannik Kossen und Maike Elisa Müller
|
||
|
||
Immer auf der Suche nach neuen Abenteuern in der Welt des maschinellen Lernens begibt sich Lisa auf einen Waldspaziergang in einem sommergrünen Laubwald. Aufmerksam beobachtet sie ihre Umgebung. Sie sieht Bäume, Moose, Pilze, Vögel, Flechten, Spinnen, ein paar Mäuse, sogar das ein oder andere Reh und viele Fußabdrücke – die erdigen Abdrücke verschiedener Tiere, manche Tatzen klein, andere groß. Einige kann Lisa direkt einem Tier zuordnen: zum Beispiel die kleinen, süßen Abdrücke der Kaninchen oder die charakteristischen Pferdehufe.
|
||
|
||
J. Kossen (*) Universität Heidelberg, Heidelberg, aus Darmstadt, Deutschland E-Mail: jannik.kossen@gmail.com
|
||
M. E. Müller TU Berlin, Berlin, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
39
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_5
|
||
|
||
40 J. Kossen und M. E. Müller
|
||
Lisa läuft weiter durch den Wald, beobachtet die Tatzen und überlegt sich, welcher Tatzenabdruck zu welchem Tier gehört. Plötzlich bleibt Lisa vor einem gigantischen Abdruck stehen – der größte, der ihr bisher begegnet ist. Lisa ist erstaunt und möchte unbedingt wissen, wie schwer wohl das Tier hinter solch einem gigantischen Fußabdruck sein muss.
|
||
Deswegen entscheidet sie sich – aus Gründen, die es nur in fiktiven Mathegeschichten gibt – den großen Abdruck des unbekannten Tieres zu vermessen und die Maße in ihr Notizbuch einzutragen. Bewaffnet mit Maßband und Waage begibt sich Lisa in den nächstgelegenen Zoo. Dort angekommen beginnt sie, das Gewicht und die Tatzengröße von allen Tieren im Zoo zu vermessen. Die Ergebnisse ihrer Messung trägt sie in Abb. 5.1 ein. Jeder Punkt steht für ein Tiergewicht-Tatzengröße-Paar. Je weiter rechts ein Punkt ist, desto größer war die Tatze (je weiter links, desto kleiner) und je weiter oben ein Punkt, desto schwerer das Tier (je weiter unten, desto leichter).
|
||
Vielleicht ist Lisa jetzt in der Lage abzuschätzen (siehe rote Linie in Abb. 5.1), wie schwer das Riesentier des Laubwaldes ist? Na, was denken Sie?
|
||
Die Fragestellung, die Lisa hier lösen möchte, nennt man im maschinellen Lernen und in der Statistik Regression. Bei einer Regression möchte man aus einer Größe, hier der Größe des Abdrucks, die Zielgröße, hier das Tiergewicht, vorhersagen.
|
||
Wichtig ist hierbei, dass alle möglichen Werte für die Zielgröße auftreten können. Mit Erinnerung an das Kap. 4 können wir also sagen, dass diese stetig ist. Dies ist der wesentliche Unterschied zur Klassifikation, die wir im nächsten Kapitel, Kap. 6, besprechen. In unserem Beispiel ist auch die Ausgangsgröße stetig. Eine Tatzengröße
|
||
|
||
5 Regression 41
|
||
Abb. 5.1 Wie kann Lisa das Gewicht des unbekannten Tieres aus seinem Fußabdruck schätzen?
|
||
von 33 cm ist ebenso denkbar wie eine von 50 cm oder 33,3 cm oder auch 40,1234 cm, wenn Lisa nur genau genug messen könnte. Sobald Lisa das Regressionsproblem gelöst hat, kann sie somit einen beliebigen Wert – und nicht nur einen, den sie schon einmal vermessen hat – für die Tatzengröße eingeben und eine Vorhersage für das Tiergewicht erhalten. Perfekt also, um dem wunderbaren Riesenabdruck ein Gewicht zuzuordnen!
|
||
Es gibt viele verschiedene Ansätze, um Regressionsprobleme zu lösen. Alle haben jedoch gemein, dass sie für einen beliebigen Wert der Tatzengröße eine eindeutige Vorhersage über das Tiergewicht abgeben müssen. Man spricht von einem funktionalen Zusammenhang. Wenn wir für viele aufeinanderfolgende Tatzengrößen unseren Lösungsansatz nach seiner Vorhersage fragen, erhalten wir eine Kurve.
|
||
|
||
42 J. Kossen und M. E. Müller
|
||
Je nachdem, für welchen Ansatz wir uns entschieden haben, können die vorhergesagten Kurven verschieden aussehen. Man spricht auch von verschiedenen Modellen. Abb. 5.2 zeigt einige mögliche Kurven, die die Vorhersagen verschiedener Modelle sein könnten. Das richtige Modell für die gegebenen Daten zu finden, ist eine der größten Herausforderungen im maschinellen Lernen. Dies liegt daran, dass Zusammenhänge in der echten Welt oft deutlich komplexer als die hier gezeigten sind. Manchmal kann man aber mit Wissen darüber, was für
|
||
Abb. 5.2 Verschiedene Möglichkeiten der Regression. Für welche wird sich Lisa entscheiden?
|
||
|
||
5 Regression 43
|
||
Größen die Daten beinhalten und wie diese zusammenhängen, bestimmte Ansätze bevorzugen oder ausschließen. So kommen zum Beispiel häufig Probleme vor, in denen es nicht nur eine, sondern gleich mehrere Ausgangsgrößen gibt, die eine Zielgröße vorhersagen sollen. Oft sind es sogar Tausende. Die Herausforderungen, die sich hier ergeben, lassen sich in Kap. 12 zum Fluch der Dimensionalität nachlesen. Entsprechend den Anforderungen des Problems gibt es immer geeignete und weniger geeignete Modelle. Was es jedoch niemals geben kann, ist das eine Modell, welches alle Probleme löst. Eine interessante Aussage, für die sich ein Blick in das Kap. 23 zum „No Free Lunch Theorem“ lohnt.
|
||
Lisa wird ihr Regressionsproblem zu dem Riesenabdruck mit einem einfachen, aber durchaus erfolgreichen Ansatz lösen: der linearen Regression. Wie diese funktioniert, steht in Kap. 8.
|
||
|
||
6
|
||
Klassifikation
|
||
Schubladendenken!
|
||
Jana Aberham und Jannik Kossen
|
||
|
||
Nachdem wir im letzten Kapitel die Regression kennengelernt haben, wagen wir uns jetzt an die Klassifikation, eine Methode des überwachten Lernens. Während wir bei einer Regression versuchen, detaillierte Vorhersagen zu treffen – das vorhergesagte Tiergewicht kann je nach Tatzengröße alle möglichen Werte von null bis tausenden Kilogramm annehmen –, reicht es uns bei der Klassifikation, aus den Daten eine sogenannte Klasse abzuleiten. Aus dem Kapitel zu Daten wissen wir, dass bei der Regression die genaue Vorhersage eine stetige Zahl ist, während
|
||
|
||
J. Aberham (*) Karlsruhe, Deutschland E-Mail: jana.aberham@gmail.com
|
||
J. Kossen Universität Heidelberg, Heidelberg, aus Darmstadt, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
45
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_6
|
||
|
||
46 J. Aberham und J. Kossen
|
||
bei der Klassifikation eine Klasse, also kategorische Daten, gesucht sind.
|
||
In diesem Kapitel wird die allgemeine Idee hinter der Klassifikation erklärt. In späteren Kapiteln stellen wir spezielle Methoden zur Klassifikation wie den k-Nächste-Nachbarn-Algorithmus (Kap. 10), die Support Vector Machine (Kap. 13) oder das neuronale Netz (Kap. 20) vor.
|
||
Um genauer zu verdeutlichen, wie eine Klassifikation mit Methoden des maschinellen Lernens ablaufen könnte, schauen wir uns mal an, was Lisa so treibt:
|
||
Nach ihren morgendlichen Abenteuern im Zoo fährt sie nachmittags in den Laden ihrer Eltern. Diese besitzen ein sehr großes Möbelgeschäft, das sich ausschließlich auf den Verkauf von Tischen und Stühlen spezialisiert hat. In den zwei Lagerhallen stehen die prächtigen Möbelstücke stilvoll angeordnet – immer ein Tisch und die passenden Stühle dazu. Diese müssen jedoch wegen der anstehenden Renovierung in der kleinen Lagerhalle von Onkel Nicolas zwischengelagert werden. Für den Transport und die Lagerung sollen nun die Stühle von den Tischen getrennt werden. Das ist sehr viel Arbeit und Lisa überlegt, wie toll es wäre, wenn eine Maschine diese für sie übernehmen könnte. Sie selbst erkennt ohne Probleme, ob es sich bei dem Möbelstück um einen Stuhl oder einen Tisch handelt, aber wie soll sie das einer Maschine beibringen?
|
||
Lisa möchte eine Regel finden, anhand der die Maschine ganz leicht prüfen kann, welcher Klasse das Möbelstück zuzuordnen ist. Daher stellt sie sich die Frage, worin sich Tische von Stühlen unterscheiden. Schwierig. Vielleicht durch die Beinlänge? Aha! Tischbeine sind viel länger als Stuhlbeine! Zur Unterscheidung von Stühlen und Tischen muss die Maschine lediglich die Länge der Beine messen. Das ist eine hervorragende Regel! Lisa
|
||
|
||
6 Klassifikation 47
|
||
freut sich und will diese gerade in die Maschine einprogrammieren, da fällt ihr Blick auf den Barhocker an der Küchentheke. Das wäre ein Fall, bei dem die Regel nicht so gut funktionieren würde. Der Hocker hat sogar längere Beine als so mancher Tisch, ist jedoch eindeutig zum Sitzen gedacht. Solche Regeln zu finden, ist oft nicht so einfach.
|
||
Vielleicht kann ja ein Lernalgorithmus helfen? Dieser würde verschiedene Merkmale der Möbel clever vereinen und so eine automatisierte Entscheidungsregel erlernen. Oftmals erkennen wir eine Klasse nicht an einer einzigen Eigenschaft. Erst durch eine Vielzahl unterschiedlicher Merkmale (Größe, Material, Anzahl der Beine, …) und ihren Verknüpfungen bekommen wir eine Idee davon, in welche Gruppe wir das Möbelstück einordnen müssen.
|
||
Lisa versteht, dass es sich hier um ein Klassifikationsproblem handelt. Aber wie genau lässt sich dieses nun lösen? Sie ruft beim Dienst „Can-AI-Help?“ an und schildert ihr Problem. Es wäre toll, wenn es einen Algorithmus gäbe, der die Möbelstücke automatisch einordnen würde. Sie hätte sogar schon zwei relevante Merkmale gefunden: Die Auflagefläche sowie die Beinlänge. Der nette Mensch am anderen Ende des Hörers versichert ihr, dass sich das Problem lösen wird. Aber da es sich hier um überwachtes Lernen handelt, wird Lisa am nächsten Tag wohl erst ein wenig etikettieren müssen – ähnlich wie sie für ihren Bruder Leon die Bienenbilder ihres Biologieprojekts in Kap. 3 vorbereitet hat. Sie muss also jedem Datenpunkt im Trainings- und Testdatensatz eine Klasse zuweisen. Dies wird im Fachjargon auch annotieren (v. engl. label ) genannt. Sie steht extra früh auf und beschriftet einige Möbelstücke aus der Lagerhalle als Stuhl oder als Tisch – je nachdem, was sie denn sind. Diese Beispiele sind ihr Trainingsdatensatz:
|
||
|
||
48 J. Aberham und J. Kossen
|
||
der Lernstoff für unseren Klassifikationsalgorithmus. (Wie schon in Kap. 3 hebt sich Lisa natürlich auch hier einige Beispiele auf, um zu testen, ob ihr Algorithmus erfolgreich gelernt hat.)
|
||
Ähnlich wie im vorherigen Kapitel über die Regression kann Lisa nun ihre Tabelle mit den Trainingsdaten in ein Koordinatensystem (siehe Abb. 6.1) eintragen. Jedes etikettierte Möbelstück wird einem Punkt zugeordnet, je nach den gemessenen Werten für Auflagefläche und Länge der Beine. Im Vergleich zur Regression kann Lisa die Punkte nun zusätzlich noch einfärben. Grün, wenn es sich um einen Stuhl und rot, wenn es sich um einen Tisch handelt. „Wow!“, Lisa schaut sich ihre Grafik an und staunt. Die roten und grünen Punkte bilden zwei getrennte Datenwolken. Jetzt muss Lisa sich nur noch eine Regel überlegen, um die roten von den grünen Punkten zu unterscheiden.
|
||
Abb. 6.1 Die Stühle und Tische werden als Punkte in Abhängigkeit von ihrer Auflagefläche und Beinlänge dargestellt
|
||
|
||
6 Klassifikation 49
|
||
Eine Möglichkeit der Klassifikation ist, eine Trennlinie zwischen den beiden Wolken zu ziehen. Wenn sie nun die restlichen Möbel klassifizieren will, muss sie diese lediglich als zusätzlichen Punkt in das Diagramm eintragen und nachschauen, auf welcher Seite der Trennlinie sie liegen (siehe Abb. 6.2). Liegt ein Punkt auf der Seite der Tische, wird es sich höchstwahrscheinlich um einen Tisch handeln. Liegt er auf der Seite der Stühle, so ist es vermutlich auch ein Stuhl.
|
||
Diese Trennlinie zu finden, ist die Aufgabe eines Klassifikationsalgorithmus. Es gibt unterschiedliche Ansätze, die richtige Trennlinie zu finden. Dabei macht jeder Algorithmus andere Annahmen und optimiert verschiedene Problemstellungen. Somit finden sich auch ganz unterschiedliche Trennlinien (siehe Abb. 6.3), wodurch Punkte in der Nähe der Linie anders klassifiziert werden.
|
||
Abb. 6.2 Die Trennlinie ermöglicht eine klare Unterscheidung der beiden Klassen
|
||
|
||
50 J. Aberham und J. Kossen
|
||
Für das hier vorgestellte Beispiel hat die Wahl der Methode vermutlich keine großen Auswirkungen, da die beiden Wolken weit auseinander liegen und einfach zu trennen sind. In realen Datensätzen können die Verhältnisse aber oft komplizierter und die Daten schwerer zu trennen sein (siehe Abb. 6.4). In solchen Fällen ist es wichtig, sich genau mit den verschiedenen Methoden und ihren Vor- und Nachteilen auseinanderzusetzen. Zudem haben in echten Anwendungen Daten natürlich mehr als nur zwei Merkmale (Auflagefläche, Länge und Anzahl der Beine, Lehne, Gewicht, Farbe, Material, Preis, …). Während unser obiges Beispiel mit nur zwei Merkmalen auch
|
||
Abb. 6.3 Verschiedene Möglichkeiten, die beiden Klassen zu trennen. Welche Linie ist die beste?
|
||
|
||
6 Klassifikation 51
|
||
Abb. 6.4 Es ist nicht immer so leicht, die richtige Trennlinie zu finden
|
||
gut von Menschenhand lösbar ist, kommen wir Menschen mit mehr als drei Merkmalen nicht mehr so gut zurecht. Klassifikationsalgorithmen besitzen den Vorteil, dass sie auch mit Datensätzen mit großen Anzahlen an Merkmalen funktionieren. Mehr dazu im Exkurs zum Fluch der Dimensionalität in Kap. 12.
|
||
Folgendes haben wir erreicht: Dem Klassifikationsalgorithmus werden Datenpunkte und deren Klasse im überwachten Training gezeigt. Daraufhin lernt der Klassifikator Regeln, anhand derer sich die Datenpunkte den verschiedenen Klassen zuweisen lassen. Diese Regeln lassen sich nun auf neue, vorher noch nicht gesehene Datenpunkte anwenden, sodass diesen eine Klasse zugewiesen werden kann.
|
||
Schließlich lohnt sich der ganze Aufwand des Etikettierens und der Suche nach dem richtigen Algorithmus doch
|
||
|
||
52 J. Aberham und J. Kossen
|
||
noch. Denn nun kann Lisa sich entspannt zurücklehnen und die Maschine bei der Arbeit beobachten. Für welchen Klassifikationsalgorithmus hat sich wohl Lisa entschieden? Hierfür lohnt sich ein Blick in Kap. 13.
|
||
|
||
7
|
||
Clusteranalyse
|
||
Gruppenzwang. Wer gehört wohin?
|
||
Jana Aberham und Fabrizio Kuruc
|
||
|
||
Lisa ist genervt. Sie würde gerne gemeinsam mit ihrem kompletten Freundeskreis etwas unternehmen. Deswegen schlägt sie ihnen verschiedene Aktivitäten vor, aber zu keinem ihrer Vorschläge sagen alle zu: Versucht sie ihren Freunden Beachvolleyball schmackhaft zu machen, dann gibt es immer einige, die keine Lust haben. Und wenn sie einen Spieleabend plant, sind davon auch nicht alle begeistert. Das Gleiche passiert, wenn sie eine Wandertour oder einen Filmabend vorschlägt. Um herauszufinden, woran das liegt, startet Lisa eine kleine Umfrage in ihrem Freundeskreis. Alle ihre Freundinnen und Freunde sollen
|
||
|
||
J. Aberham (*) Karlsruhe, Deutschland E-Mail: jana.aberham@gmail.com
|
||
F. Kuruc Buseck, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
53
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_7
|
||
|
||
54 J. Aberham und F. Kuruc
|
||
auf einer Skala von eins bis zehn angeben, wie sehr ihnen sportliche Aktivitäten liegen und wie sehr sie Aktivitäten zu Hause mögen. Die Antworten ihrer Freunde trägt sie in eine Tabelle (Abb. 7.1) ein und zeichnet sie anschließend zur Veranschaulichung in ein Koordinatensystem (Abb. 7.2).
|
||
Schnell bemerkt sie, dass es zwei Gruppen innerhalb ihres Freundeskreises zu geben scheint, denn die Punkte in der Grafik scheinen sich an zwei Stellen zu häufen. Die einen haben wohl eine größere Präferenz für sportliche Aktivitäten, mögen dafür Aktivitäten zu Hause scheinbar nicht so gerne. Bei den Anderen ist dies genau umgekehrt. Sie zeichnet daher je eine Wolke um diese Gruppen und benennt die eine Sportskanonen (orangene Wolke) und die andere Stubenhocker (grüne Wolke). Vielleicht sind diese Gruppen der Grund dafür, dass sie immer Absagen erhalten hat. Um zu testen, ob die gewählte Einteilung
|
||
Abb. 7.1 Umfrage in Lisas Freundeskreis
|
||
|
||
7 Clusteranalyse 55
|
||
Abb. 7.2 Gruppierung in Sportskanonen und Stubenhocker
|
||
in irgendeiner Form sinnvoll ist, überlegt sich Lisa ein Experiment: Wenn sie das nächste Mal zu einem Treffen einlädt, macht Lisa jeder Person aus ihrem Freundeskreis einen zu ihrer Gruppe passenden Vorschlag. Und tatsächlich, alle Freunde aus der Gruppe der Sportskanonen haben zum Fußballspielen zugesagt, und alle Stubenhocker sind für einen Filmabend zu haben. Die Interessen waren in Bezug auf ihre Vorschläge vorher also zu unterschiedlich und liegen nun in den Gruppen näher beieinander. Lediglich ihre Freundin Maike konnte sie nicht so gut zuordnen. Ihre Interessen scheinen nicht so richtig in eine der beiden Gruppen zu passen. Sie hat auch schon eine Idee, wie sie damit umgehen soll – es lohnt ein Blick in Kap. 9 – als der Blick ihres Mitbewohners Max auf das Notizbuch fällt: „Du hältst mich für einen Stubenhocker?“ Beschämt schaut Lisa zu Boden; vielleicht hätte sie für diese Gruppe eher eine andere Bezeichnung wählen sollen.
|
||
|
||
56 J. Aberham und F. Kuruc
|
||
Lisa hat sich in diesem Beispiel zwei Merkmale ausgesucht, die sie für ihre Problemstellung („Warum erhalte ich so viele Absagen?“) für relevant hielt. Anhand der Ausprägung dieser Merkmale konnte sie ihren Freundeskreis in zwei Gruppen einteilen. In diesem Beispiel wusste Lisa allerdings vorab nicht, wie viele Gruppen sie eigentlich identifizieren möchte. Außerdem haben ihre Freunde ja noch viele weitere Eigenschaften, wie beispielsweise ihren Humor oder ihre Gesprächigkeit. Allgemein kann man sich daher fragen, nach welchen Kriterien wir unsere Daten in Gruppen einteilen können und wie wir diese Gruppen überhaupt finden. Das Themengebiet, das sich mit der systematischen Beantwortung dieser Fragestellungen beschäftigt, wird als Clusteranalyse bezeichnet. Ziel der Clusteranalyse ist es, verschiedene Objekte bestimmten Gruppen zuzuordnen, sodass Objekte innerhalb einer Gruppe ähnlich zueinander sind und sich möglichst deutlich von Elementen anderer Gruppen unterscheiden. Diese Gruppen werden auch Cluster genannt.
|
||
Einige Algorithmen der Clusteranalyse fassen Objekte nach bestimmten Kriterien zu immer größeren Gruppen zusammen oder teilen sie in immer kleinere Gruppen auf. Andere Clusteralgorithmen benötigen die Anzahl der insgesamt gewünschten Gruppen, in welche die Daten eingeteilt werden sollen. Im Gegensatz zur Klassifikation muss die Bedeutung der Gruppen im Vorhinein aber nicht bekannt sein. Dementsprechend handelt es sich bei der Clusteranalyse um ein Verfahren des unüberwachten Lernens. So überlegte sich Lisa in dem Beispiel erst nach der Zusammenfassung der Freunde, was die gefundenen Gruppen bedeuten könnten. Wir werden in Kap. 11 den k-Means-Algorithmus als Beispiel kennenlernen.
|
||
|
||
7 Clusteranalyse 57
|
||
Nachdem wir im ersten Teil dieses Buches die nötigen Grundlagen und Begrifflichkeiten kennengelernt haben, sind wir nun perfekt vorbereitet, um uns eine Auswahl der bekanntesten Algorithmen des maschinellen Lernens genauer anzuschauen. Darüber hinaus werden uns spannende Exkurse die Möglichkeit geben, ein wenig über den Tellerrand hinauszuschauen. Und los geht’s!
|
||
|
||
Teil II
|
||
Lernverfahren und mehr
|
||
|
||
8
|
||
Lineare Regression
|
||
Einfach nur ein Strich?
|
||
Jannik Kossen und Maike Elisa Müller
|
||
|
||
Erinnern wir uns zurück an Lisas Abenteuer im sommergrünen Laubwald. Lisa wollte den Zusammenhang zwischen Tatzengröße und Tiergewicht herausfinden. Sie weiß schon, dass es sich hierbei um ein Regressionsproblem handelt. Jetzt muss sie sich nur noch für eine passende Regressionsmethode entscheiden. Sie könnte zum Beispiel eine lineare Regression probieren: Dort nimmt bei einer Zunahme der Ausgangsgröße um einen festen Betrag die Zielgröße ebenfalls um einen festen Betrag zu. Die Ausgangsgröße ist hier die Tatzengröße und die Zielgröße das
|
||
|
||
J. Kossen (*) Universität Heidelberg, Heidelberg, aus Darmstadt, Deutschland E-Mail: jannik.kossen@gmail.com
|
||
M. E. Müller TU Berlin, Berlin, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
61
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_8
|
||
|
||
62 J. Kossen und M. E. Müller
|
||
Tiergewicht. Dies nennt man einen linearen Zusammenhang. Lisa kennt ihn schon aus der Obstwaage vom Supermarkt: Wenn sie dort Äpfel kauft, richtet sich der Preis linear nach dem Gewicht der Äpfel. In unserem Beispiel könnte es den folgenden linearen Zusammenhang geben: Wenn eine Tatze 5 cm größer als eine andere ist, wiegt das zugehörige Tier auch immer 10 kg mehr. Dies bedeutet, dass ein Tier mit einer Tatzengröße von 40 cm also 10 kg mehr wiegt als ein Tier mit einer Tatzengröße von 35 cm.
|
||
Wenn man die Punkte, die Tatzengröße mit Tiergewicht in Zusammenhang bringen, in eine Grafik einzeichnet, so liegen diese – mit etwas Fantasie – auf einer geraden Linie. Eine lineare Regression findet genau so eine gerade Linie (auch Gerade genannt) und scheint hier also die richtige Lösung zu sein. Lisa könnte sich aber auch zum Beispiel für eine sogenannte quadratische Regression entscheiden. Hier würde sich statt einer Geraden eine krumme Kurve, eine sogenannte Parabel, ergeben. Nimmt die Ausgangsgröße um einen festen Betrag zu, so nimmt die Zielgröße nun nicht mehr um einen festen Betrag zu. Stattdessen hängt die Zunahme der Zielgröße von dem Wert der Ausgangsgröße ab und kann zum Beispiel mit wachsender Ausgangsgröße immer größer werden.
|
||
Wie führt Lisa also eine lineare Regression durch? Sie schaut sich nochmal ihre gezeichnete Grafik an (siehe Abb. 5.1) und überlegt sich, wie genau sie die Punkte sinnvoll miteinander in Verbindung bringen kann. Dabei stellt sie fest, dass dies gar nicht so einfach ist. Würden ihre Ergebnisse so wie in Abb. 8.1 aussehen, wäre das Ergebnis klar: Es ließe sich einfach eine Gerade durch die Punkte zeichnen und dann das Gewicht des unbekannten Tieres erfahren. Wie wir aber schon festgestellt haben, sehen Lisas Daten leider nicht so schön aus. Trotzdem
|
||
|
||
8 Lineare Regression 63
|
||
scheint es auf den ersten Blick nicht verkehrt zu sein, eine gerade Linie durch die Punkte zu legen. Aber wie soll diese Linie dann aussehen? Welche ist die beste Gerade (siehe Abb. 8.2)?
|
||
Da es Lisa anscheinend nicht möglich ist, eine Gerade zu finden, die direkt durch alle Datenpunkte geht, versucht sie, diejenige Gerade zu finden, die am nächsten an ihren Datenpunkten liegt. Wie kann sie dies erreichen? Sie probiert erst einmal verschiedene Geraden aus und beobachtet, wie groß der Abstand eines jeden Datenpunktes zu dieser Geraden ist. Die Summe dieser Abweichungen bezeichnet man als Fehler der Geraden. Diesen Fehler möchte Lisa so klein wie möglich machen, um somit die bestmögliche Gerade zu finden. Lisa wackelt also an der Geraden, dreht und verschiebt diese, und schaut, wie sich der Fehler verändert. Schlussendlich
|
||
Abb. 8.1 Doch leider sind die Dinge oft nicht so einfach!
|
||
|
||
64 J. Kossen und M. E. Müller
|
||
Abb. 8.2 Welche dieser Geraden passt am besten zu den Daten?
|
||
nimmt sie diejenige Gerade, die den kleinsten Fehler aufweist (siehe Abb. 8.3). Unter allen möglichen Geraden beschreibt diese Gerade die von ihr gemessenen Daten am besten. Praktischerweise muss man in der Realität nicht an den Geraden wackeln, sondern kann direkt mittels mathematischer Methoden die bestmögliche Gerade aus den
|
||
Abb. 8.3 Die Gerade mit dem kleinsten Fehler ist die beste
|
||
|
||
8 Lineare Regression 65
|
||
aufgezeichneten Datenpunkten bestimmen (siehe Infokasten). Wer keine Mathematik benutzen möchte, darf aber gerne auch wackeln.
|
||
Nach ihrer Auswertung kann Lisa nun für beliebige Tatzengrößen Vorhersagen (siehe Abb. 8.4) über das Gewicht des zugehörigen Tieres treffen. Auch das Gewicht zu der mysteriösen Riesentatze kann sie nun ermitteln. Dies funktioniert, indem sie auf der x-Achse – die mit den Tatzengrößen – nach der Größe der gemessenen Tatze sucht. Dort angekommen schaut sie senkrecht nach oben, bis sie ihre Gerade kreuzt. An dem Punkt, an dem sie die Gerade kreuzt, schaut sie waagerecht nach links und kann nun ihren Vorhersagewert für das unbekannte Tiergewicht zum gemessenen Fußabdruck an der y-Achse ablesen.
|
||
Da die Daten nicht perfekt auf einer Geraden liegen, führt dies selbst bei den beobachteten Tatzengrößen
|
||
Abb. 8.4 Für jede beliebige Tatzengröße (rot) kann Lisa nun mithilfe der Gerade eine Vorhersage über das Gewicht (rot) treffen
|
||
|
||
66 J. Kossen und M. E. Müller
|
||
zu Abweichungen der Vorhersagen von den gemessenen Tiergewichten. Der vorhergesagte Wert des Gewichts des unbekannten Tieres liegt aber vermutlich nah genug am wahren Wert.
|
||
Fassen wir zusammen, was Lisa getan hat: Ausgehend von der Größe der monstergroßen Tatze wollte sie eine Vorhersage über das Gewicht des zugehörigen, unbekannten Tieres treffen. Dazu hat sie zunächst die Tatzengrößen und das Gewicht verschiedener Tiere aus dem Zoo gesammelt. Diese Daten hat Lisa in eine Grafik eingetragen und festgestellt, dass diese ungefähr auf einer Geraden liegen. Nachdem sie die beste Gerade gefunden hat, kann sie diese nutzen, um Vorhersagen zu treffen. Allein aus der Größe der Riesentatze ist es ihr am Ende möglich, eine Vorhersage über das Gewicht des Tieres zu treffen.
|
||
Mit der linearen Regression haben wir in diesem Kapitel eine sehr einfache Vorhersagemethode des maschinellen Lernens kennengelernt. Oftmals lässt sich mit diesem einfachen Ansatz aber schon viel erreichen. Für schwierigere Zusammenhänge funktioniert dieser aber nicht immer. Dann müssen kompliziertere Methoden ans Werk, von denen wir in den nachfolgenden Kapiteln einige kennenlernen werden.
|
||
Aber dennoch: Ist in den Medien die Rede von einer KI, die aus ihrem Bewegungsprofil (vom Handy aufgezeichnet) ihr Alter vorhersagt, so kann es sein, dass sich hier nichts weiter als eine lineare Regression verbirgt. So einfach kann KI sein!
|
||
|
||
8 Lineare Regression 67
|
||
Wie bekomme ich die bestmögliche Gerade?
|
||
Auch wenn die Erinnerungen womöglich dunkel und verschwommen sind, werden die meisten von Ihnen in der Schule bereits Geradengleichungen gesehen haben.
|
||
Als kleine Erinnerung: Eine Gerade wird durch die Gleichung y = m * x + b beschrieben, wobei m die Steigung der Geraden bezeichnet und b der y-Achsenabschnitt ist, d. h. der Wert, an dem unsere Gerade bei x = 0 die y-Achse schneidet. Für eine gegebene Tatzengröße erhalten wir nun das vorhergesagte Gewicht des Tieres, indem wir die Tatzengröße für x in unsere Geradengleichung einsetzen und daraus unser vorhergesagtes Gewicht y berechnen. Um die Geradengleichung so benutzen zu können, müssen wir aber schon wissen, welche Steigung m und welchen Achsenabschnitt b unsere Gerade hat. Um dies herauszufinden, können wir nun mehrere Datenpunkte messen und daraus eine Gleichung für den Fehler in Abhängigkeit von den gewählten m und b aufstellen, d. h. die Abweichung unseres vorhergesagten Tiergewichtes y und des tatsächlich gemessenen Tiergewichtes. Diese Abweichungen quadrieren wir und addieren sie auf. Ein Grund für das Quadrieren ist, dass somit egal ist, ob unsere Abweichungen nach oben oder unten sind, d. h. ob wir das Gewicht zu groß oder zu klein geschätzt haben. Dazu wollen wir diejenigen Parameter m und b finden, die die Summe der quadratischen Abweichungen möglichst klein machen, denn die Parameter mit dem geringsten Fehler beschreiben die Daten am besten. Dieses Verfahren nennt sich die Kleinste-Quadrate-Methode. Im obigen Beispiel haben wir das Quadrieren der Einfachheit halber weggelassen.
|
||
Es gibt nun verschiedene Möglichkeiten, die Parameter zum kleinsten Fehler zu finden. Analog zum „Wackeln an der Kurve“, wie in unserer Geschichte, könnte man auch hier einfach verschiedene Werte von m und b ausprobieren. Wie man mathematisch „ausprobiert“ und sich Schritt für Schritt der Lösung nähert, ist im Kap. 22 zum Gradientenabstiegsverfahren erklärt. Bei einer einfachen linearen Regression muss man aber gar nicht ausprobieren, sondern kann stattdessen direkt eine Lösung mit der sogenannten Differenzialrechnung herleiten.
|
||
|
||
9
|
||
Ausreißer
|
||
Ausnahmen von der Regel
|
||
Jannik Kossen und Maike Elisa Müller
|
||
|
||
Lisa ist begeistert von ihrem Modell aus Kap. 8. Sie freut sich, dass sie das Gewicht von Tieren anhand ihres Fußabdrucks ungefähr schätzen kann. Als sie die Tiere im Zoo vermessen hat, hat sie zunächst allerdings nur die in Deutschland heimischen Tiere untersucht. Um noch mehr Daten zu sammeln und ihr Ergebnis genauer zu machen, beginnt sie, auch exotischere Tiere zu vermessen. Sie trägt diese Informationen ebenfalls in ihr Diagramm ein und wird auf einmal stutzig, als sie die Ergebnisse sieht.
|
||
|
||
J. Kossen (*) Universität Heidelberg, Heidelberg, aus Darmstadt, Deutschland E-Mail: jannik.kossen@gmail.com
|
||
M. E. Müller TU Berlin, Berlin, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
69
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_9
|
||
|
||
70 J. Kossen und M. E. Müller
|
||
Lisa stellt fest, dass eines der Tiere, von dem sie die Daten gesammelt hat, ein extrem hohes Körpergewicht hat, aber gar keine so großen Fußabdrücke – eine Giraffe!
|
||
Lisa ist zunächst überrascht, die Daten scheinen sehr ungewöhnlich zu sein. Hat sie sich etwa verschrieben? Sollte sie dieses Tier einfach ignorieren oder wäre das ein Fehler?
|
||
Wenn sie nun die ideale Gerade so wie in Kap. 8 zeichnet, dann sieht diese plötzlich anders aus (siehe Abb. 9.1). Dies liegt daran, dass der neue Messpunkt einen sehr großen Abstand zu den anderen Punkten hat. Würde Lisa beim Finden der richtigen Geraden diesen Punkt ignorieren, so würde der Gesamtfehler nur aufgrund dieses einen Punktes sehr groß werden. Es ist also besser, die Gerade ein wenig in Richtung der Giraffe zu korrigieren. Hierbei nimmt man nun für die anderen Punkte etwas größere
|
||
Abb. 9.1 Ein einzelner Ausreißer kann die Gerade stark beeinflussen
|
||
|
||
9 Ausreißer 71
|
||
Fehler in Kauf, kann aber den großen Fehler des neuen Punktes etwas abdämpfen. So hat schon dieser eine Ausreißer einen großen Einfluss auf die gefundene Gerade.
|
||
Die Frage ist, wie man zu solchen Ausreißern steht. Nun, man könnte sich zum Beispiel dafür entscheiden, diesen Punkt und seinen Abstand zur Gerade zu ignorieren. Das ist in diesem Fall sinnvoll, denn Lisa studiert Biologie und meint, dass Tiere mit hohem Gewicht und kleinen Fußabdrücken die Ausnahmen sind. Somit glaubt sie, die Giraffe getrost vernachlässigen zu können und bei der bereits gefundenen Gerade zu bleiben. Das neue Tier wäre im Jargon des maschinellen Lernens ein Ausreißer – im Gegensatz zu den Regelfällen, die durch unsere Gerade beschrieben werden.
|
||
Es gibt Methoden, um solche Ausreißer automatisch zu erkennen. Trotzdem bleibt es extrem schwer, mit Sicherheit zu entscheiden, wann ein Punkt wirklich ein Ausreißer, und damit vernachlässigbar ist. Unter Umständen kann es sich nämlich auch um einen sehr wichtigen Punkt handeln, der eine Eigenschaft der Daten zeigt, die bisher nicht berücksichtigt worden ist. Das Entfernen eines solchen Punktes würde die Daten dann gefährlich verfremden. Möglicherweise ist das auffällige Tier gar nicht so ungewöhnlich und Lisa hat in ihren Vorlesungen nicht so gut aufgepasst, wie sie dachte. (Hat Lisa noch nie ein Reh, Pferd oder eine Kuh gesehen? Gab es die nicht im Zoo?) Im Zweifelsfall ist es immer eine gute Idee, die Ausreißer mit Experten, die sich gut mit den Daten auskennen, zu besprechen.
|
||
Denn ein Vernachlässigen von Ausreißern kann zu ernsthaften Problemen führen. Mit einem solchen Fall hatten es Forscher der NASA um 1980 zu tun. Ihre Software hatte Ozonwerte gemessen, die niedrigen Werte über
|
||
|
||
72 J. Kossen und M. E. Müller
|
||
der Antarktis für Ausreißer gehalten und als solche automatisch aussortiert. Dadurch wurden diese bei den Auswertungen nicht beachtet und statt der NASA haben letztendlich erst später britische und japanische Forscher diese „Ausreißer“ als das Ozonloch über der Antarktis enttarnt.1 Ein pflichtbewusster Umgang mit Ausreißern ist wichtig, aber leider nicht leicht.
|
||
1Die tatsächliche Geschichte ist etwas nuancierter und lässt sich unter anderem in den folgenden Links nachlesen. https://robjhyndman.com/hyndsight/omitting-outliers/, abgerufen am 20.01.2019 https://www.math.uni-augsburg.de/ htdocs/emeriti/pukelsheim/1990c.pdf, abgerufen am 20.01.2019.
|
||
|
||
10
|
||
k-Nächste-Nachbarn
|
||
Nachbarschaftshilfe mal anders
|
||
Michael Neumann
|
||
|
||
Lisa arbeitet montags und mittwochs in einem Bekleidungsgeschäft. Ihrer Chefin Dorothea fällt es häufig schwer, die richtige Anzahl an Mitarbeitern und Mitarbeiterinnen einzuteilen, da die Anzahl der Kunden von Tag zu Tag stark schwankt. Es scheint, als hätten Sonderangebote oder das Wetter einen Einfluss darauf. Lisa überlegt sich, wie sie vorhersagen könnte, wie viele Kunden das Geschäft pro Tag besuchen. Dafür möchte sie Tage untersuchen, die sich im Bezug auf Wochentag, Wetter und Sonderangebote ähneln. Sie hat bereits über mehrere Wochen Daten erfasst und gelabelt, also mit einer Klasse versehen (siehe Abb. 10.1). Wie bereits in Kap. 6 zur
|
||
|
||
M. Neumann (*) Haßfurt, Deutschland E-Mail: neumann.michael1993@gmx.de
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
73
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_10
|
||
|
||
74 M. Neumann
|
||
Klassifikation erläutert, ist diese Vorarbeit nötig, um überwachte Lernverfahren anwenden zu können.
|
||
Werden nun zum Beispiel an einem bewölkten Montag mit Sonderangeboten (letzter Datenpunkt in Abb. 10.1, Tag X) wenige oder viele Kunden erwartet? Für den Anfang möchte Lisa nicht eine konkrete Anzahl von Kunden vorhersagen (dies wäre eine Regression), sondern lediglich abschätzen, ob an einem bestimmten Tag mit vielen oder wenigen Kunden zu rechnen ist.
|
||
Für die Klassifikation dieses Datenpunktes, also dessen Zuordnung in die Klasse „wenige Kunden“ oder „viele Kunden“, kann sie auf die vorher gesammelten Daten zurückgreifen. Sie möchte nun für Tag X eine Vorhersage treffen und vergleicht diesen mit den drei ähnlichsten Tagen. Hierzu benötigt sie eine Möglichkeit, die Ähnlichkeit bzw. Verschiedenheit von Datenpunkten zu bestimmen. Sie entscheidet sich dafür, die Anzahl der unterschiedlichen Eigenschaften zwischen den Tagen zu zählen. Betrachten wir den zu klassifizierenden Tag X (Montag, bewölkt, ja) und Tag 1 (Montag, bewölkt, nein),
|
||
Abb. 10.1 Ausschnitt der Daten vergangener Tage
|
||
|
||
10 k-Nächste-Nachbarn 75
|
||
so unterscheiden sich die beiden Tage in genau einer Eigenschaft, nämlich darin, ob es ein Sonderangebot gab oder nicht. Der Unterschied beträgt daher 1. Die Verschiedenheit von Tag 2 und Tag 4 beträgt 2, da sie sich in zwei Eigenschaften unterscheiden. Die Unterschiedlichkeit zwischen dem neuen Datenpunkt und allen bisherigen Tagen ist bereits in Abb. 10.2 eingetragen, wobei die drei ähnlichsten Tage unterstrichen wurden. Eine rote Hervorhebung zeigt die Unterschiede der Datenpunkte zum neuen Datenpunkt.
|
||
Am ähnlichsten sind also Tag 1, Tag 2 und Tag 5. Diese Tage bezeichnen wir als Nachbarn des Tages X. Da an der Mehrheit dieser Nachbar-Tage viele Kunden das Geschäft besuchten, geht Lisa auch an diesem Montag (Tag X) von einer großen Kundenzahl aus.
|
||
Folgendes Prinzip steckt hinter dem Algorithmus: Soll ein neuer Datenpunkt klassifiziert werden, so wird dessen Klasse durch die Mehrheit der nächstliegenden k Datenpunkte, auch Nachbarn genannt, bestimmt. k ist hierbei ein Platzhalter für die gewählte Zahl an Nachbarn.
|
||
Lisas Chefin Dorothea ist begeistert von der Idee, die Kundenzahlen auf diese Art und Weise vorherzusagen, um
|
||
Abb. 10.2 Ausschnitt der Daten mit berechneter Verschiedenheit zum aktuellen Montag
|
||
|
||
76 M. Neumann
|
||
die Mitarbeiter besser einteilen zu können. Nach einigen Wochen Testbetrieb entscheiden die beiden gemeinsam, das System künftig weiterhin zu verwenden. Damit auch alle Arbeitskollegen von Lisa das Prinzip der Vorhersage verstehen, präsentiert sie den Algorithmus in einer Mittagspause und beschreibt hierbei einige grundlegende Details:
|
||
Der Parameter k, also die Anzahl der zu betrachtenden Nachbarn, muss bei der Klassifikation neuer Daten vorgegeben werden. Abhängig vom jeweiligen Datensatz kann das optimale k stark variieren. Das beste k kann durch Ausprobieren verschiedener k-Werte und anschließendem Überprüfen auf dem Testdatensatz, wie in Kap. 3 beschrieben, gefunden werden. Ein Sonderfall ist k = 1, womit jeder neue Datenpunkt genau wie sein nächster Nachbar klassifiziert wird. Abb. 10.3 skizziert ein weiteres
|
||
Abb. 10.3 Skizze von k-Nächste-Nachbarn mit k = 5
|
||
|
||
10 k-Nächste-Nachbarn 77
|
||
Beispiel mit k = 5. Gehört der neue Datenpunkt (gekennzeichnet durch ein x ) zur Klasse der roten oder grünen Punkte? In diesem Fall würde der Algorithmus die grüne Klasse ausgeben, da drei der fünf nächstgelegenen Nachbarn, und damit die Mehrheit, ebenfalls zu dieser Klasse gehören. Bei vielen Daten ist ein großes k sinnvoll, um einzelne Ausreißer nicht zu stark zu gewichten (siehe dazu auch Kap. 9).
|
||
Die Verschiedenheit von Datenpunkten
|
||
Um die Verschiedenheit von Punkten bestimmen zu können, muss der Abstand zwischen zwei Punkten definiert und der neue Datenpunkt mit allen bisherigen Punkten dementsprechend verglichen werden. Bei Datenpunkten, die auf einer Landkarte liegen, ist dies beispielsweise häufig einfach der Abstand in Luftlinie (siehe Abb. 10.4). Hierbei dient eben genau die intuitiv verstandene Entfernung zwischen zwei Punkten als Maß der Verschiedenheit. Neben der Luftlinie wird zur Bestimmung der Verschiedenheit bei Punkten im 2-dimensionalen Raum gerne auch die Manhattan-Distanz (siehe Abb. 10.5) genutzt. Hierbei wird nur waagerecht und senkrecht gemessen – als ob man um Manhattans Häuserblöcke läuft. Für kategorische Attribute wird häufig die oben schon genutzte, sogenannte Hamming-Distanz verwendet, welche die Anzahl der unterschiedlichen Eigenschaften zählt. Abb. 10.6 skizziert diese nochmals beispielhaft daran, wie stark sich Personen unterscheiden.
|
||
Nach anfänglicher Skepsis konnte Lisa ihre Arbeitskollegen überzeugen. Aufgrund der nun effizienteren Einplanung der Mitarbeiter möchten diese den Algorithmus nicht mehr missen.
|
||
In diesem Kapitel wurde das k-Nächste-Nachbarn-Verfahren zur Klassifikation eingeführt. Als sog. fauler Lernalgorithmus (engl. lazy learner ) verzichtet
|
||
|
||
78 M. Neumann
|
||
Abb. 10.4 Verschiedenheit des Punktes unten links zu den anderen Punkten mit der Euklidischen Distanz (Luftlinie)
|
||
Abb. 10.5 Verschiedenheit des Punktes unten links zu den anderen Punkten mit der Manhattan-Distanz
|
||
k-Nächste-Nachbarn (k-NN, engl. k-nearest-neighbors) auf einen vorgeschalteten Lernprozess. Statt beispielsweise eine Trennlinie aus den Trainingsdaten zu lernen, werden zur späteren Klassifikation direkt die bekannten, gelabelten Datenpunkte verwendet.
|
||
|
||
10 k-Nächste-Nachbarn 79
|
||
Abb. 10.6 Verschiedenheit der angegebenen Personenpaare durch die Hamming-Distanz
|
||
Wir haben gesehen, dass auch dieser Algorithmus nicht alles von selbst löst. Je nach Anwendungsfall müssen Stellschrauben wie das verwendete k oder die Methode zur Bestimmung der Abstände zwischen Datenpunkten angepasst werden.
|
||
Achtung: Bei der Abkürzung k-NN ist im deutschen Sprachraum etwas Vorsicht geboten, da künstliche neuronale Netze (siehe Kap. 20) in der Literatur teilweise ebenfalls mit KNN abgekürzt werden.
|
||
|
||
11
|
||
k-Means-Algorithmus
|
||
Finde deine Mitte
|
||
Dorothea Müller
|
||
|
||
„Oh, ups,…“ – hätte Lisa doch mal besser aufgepasst! Als sie ihren Onkel, den Professor Steffen Rombledure besucht, kippt ihr ein ganzer Stapel von Papieren und Dokumenten von seinem Schreibtisch. Aber da er gerade das Zimmer verlassen hat, um Kaffee zu holen, ließe sich das Chaos vielleicht etwas eindämmen, bis er wiederkommt?! Ideal wäre es, ein paar Stapel oder Gruppen von Dokumenten zu bilden, die irgendwie zusammengehören, überlegt sich Lisa, während sie durch die Unterlagen blättert. Wie gut, dass sie rein zufällig schon eine Idee hat, mit welchem Algorithmus das machbar wäre: k-Means-Clustering!
|
||
|
||
D. Müller (*) TU Berlin, Berlin, Deutschland E-Mail: dorothea@bccn-berlin.de
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
81
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_11
|
||
|
||
82 D. Müller
|
||
Was sie dafür braucht? Zunächst die Anzahl der Gruppen. Lisa ist etwas überfordert, entscheidet sich aber, erst einmal alles auf zwei Gruppen aufzuteilen. Anders als im vorherigen Kapitel steht beim k-Means-Algorithmus das k für die Anzahl der Gruppen, welche man bilden möchte. Hier ist k also 2. Dann benötigt sie noch Merkmale, anhand derer sich die Gruppen unterscheiden könnten. Wie könnte sie die verschiedenen Textdokumente einteilen?
|
||
Eine Möglichkeit wäre es, die Länge der Dokumente zu betrachten, beispielsweise gemessen an der Anzahl der Wörter. Eine andere, die Anzahl der benutzten Fremdwörter zu zählen, also Wörter, die Lisa irgendwie spanisch vorkommen. Aber auch das Gewicht des Papiers wäre ein mögliches Merkmal, denn einige der Unterlagen sind auf dickerem Papier gedruckt. Lisa entscheidet sich, blitzschnell alle Wörter zu zählen und in Windeseile die Blätter zu wiegen. Sie erhebt also zwei Merkmale, das Papiergewicht und die Anzahl der Wörter. Das ergibt dann Punktwolken wie in Abb. 11.1.
|
||
Als Mensch ist es relativ offensichtlich, wie sich hier Gruppen einzeichnen lassen. Aber wie könnte Lisa dies einem Computer beibringen (s. Abb. 11.2)? Die intuitive Idee des Algorithmus ist, dass sich für jede Gruppe (also für jedes sogenannte Cluster ) ein Punkt finden lässt, der das typische Aussehen des ganzen Clusters beschreibt. Er ist gewissermaßen der Prototyp und der Mittelpunkt aller Punkte dieses Clusters. Alle Punkte eines Clusters sind diesem Mittelpunkt näher als den Mittelpunkten anderer Cluster (siehe Abb. 11.3).
|
||
|
||
11 k-Means-Algorithmus 83
|
||
Abb. 11.1 Für alle Dokumente werden die gewählten Eigenschaften erhoben und eingetragen
|
||
Abb. 11.2 Der Algorithmus muss nur seine Mitte finden
|
||
|
||
84 D. Müller
|
||
Abb. 11.3 Die Distanz eines Punktes zu den Mittelpunkten
|
||
Der Algorithmus funktioniert wie folgt: 1. Beginn Am Anfang weiß man nicht, wo die optimalen Mittelpunkte für die Cluster liegen. Eine Vorgehensweise ist daher, mit k zufällig gewählten Datenpunkten als potenzielle Mittelpunkte zu starten. Lisa will die Dokumente in zwei Gruppen aufteilen, würde also zwei beliebige Punkte wählen (Schritt 1 in Abb. 11.4). 2. Zuordnen Nun ordnet man alle Datenpunkte, also Dokumente, einem Cluster zu. Dazu nimmt man einen Datenpunkt und schaut sich an, wie weit er von den jeweiligen Mittelpunkten entfernt ist. Jetzt kann man ihn entsprechend dem jeweiligen Mittelpunkt, welchem er am nächsten ist, zuordnen und einfärben (Schritt 2 in Abb. 11.4).
|
||
|
||
11 k-Means-Algorithmus 85 Abb. 11.4 So wird geclustert!
|
||
|
||
86 D. Müller
|
||
3. Aktualisieren der Mittelpunkte Der Mittelpunkt beschreibt nun nicht mehr perfekt das „typische“ Aussehen der Gruppe! Wie kann man dies beheben? Man berechnet ihn nun neu aus allen Punkten, die der entsprechenden Gruppe zugeordnet sind. Übrigens: Der neue Mittelpunkt muss nicht mehr einer der Datenpunkte sein (Schritt 3 in Abb. 11.4).
|
||
Moment mal – da sich die Mittelpunkte verändert haben, kann es jetzt sein, dass es Datenpunkte gibt, die einem anderem Mittelpunkt als dem ihrer Gruppe näher sind. Genau! Daher wiederholt man jetzt das Zuordnen der Punkte (erneut Schritt 2, in Abb. 11.4 ist dies Schritt 4) und das Aktualisieren der Mittelpunkte (Schritt 3) immer wieder. Wenn man keine Punkte mehr einem anderen Cluster zuordnen muss und sich die Mittelpunkte nicht mehr verändern, ist man fertig.
|
||
Lisa ist zufrieden. Sie konnte mithilfe des Algorithmus zwei Gruppen von Dokumenten bilden. Nun ist sie neugierig, was ihre Gruppen eigentlich bedeuten: Eine Sache ist es, Gruppen aus ähnlichen Dokumenten oder anderen Daten zu bilden, eine andere, sich zu überlegen, was sie inhaltlich beschreiben. Lisa überlegt: Alle wissenschaftlichen Texte des Professors sind bestimmt lang – die grüne Punktwolke beschreibt also sicherlich akademische Arbeiten. Die anderen Texte sind kürzer, also vielleicht Notizen von verschiedenen Konferenzen, die er im Laufe der Zeit auf seinem Schreibtisch angehäuft hat. Was passiert, wenn man die Dokumente in mehr Gruppen unterteilen möchte? Für k =3, also drei Gruppen, merkt Lisa, dass einige von den Blättern mit kurzen Texten deutlich schwerer als der Rest sind und sich aus ihnen eine eigene Gruppe bilden lässt (Abb. 11.5). Was kann Lisa daraus schlussfolgern? Stammen die Notizen vielleicht von einer bestimmten Konferenz oder macht der Professor nebenher heimlich Notizen auf anderem Papier, um mit einem Liebesroman Erfolg zu
|
||
|
||
11 k-Means-Algorithmus 87
|
||
Abb. 11.5 Je nach k (also je nach Anzahl der Gruppen) bekommt man verschiedene Cluster. Hier sind beispielhaft die Cluster für k = 2, k = 3, k = 4 eingezeichnet
|
||
haben? Nein, sinnvoll scheint das nicht. Welche Aussagen lassen sich hier also wirklich treffen?
|
||
Hier stoßen wir auf eine generelle Herausforderung. Wenn man Datenpunkte beziehungsweise Dokumente in Gruppen einteilt (also clustert ), sollte man immer überprüfen, was die einzelnen Gruppen überhaupt bedeuten und ob die erhaltene Gruppierung sinnvoll ist. Enthalten die Gruppen nur ganz wenige Punkte oder haben in einer Gruppe ganz viele Punkte einen hohen Abstand zum Mittelpunkt (siehe Abb. 11.6)? Dann ist die mit k-Means gefundene Gruppierung eventuell nicht sinnvoll.
|
||
Abb. 11.6 Ein Beispiel für problematische Daten
|
||
|
||
88 D. Müller
|
||
Man kommt also nicht umhin, sich die Daten genauer anzuschauen. Der Algorithmus an sich nimmt einem diesen Schritt nicht ab. Hierbei ist es auch wichtig, die Merkmale zu betrachten, nach denen das Clustern durchgeführt wird. Lisa wählte beispielsweise das Gewicht des Papiers als Merkmal. Vielleicht hätte sie auch bessere Merkmale zur Differenzierung der Texte nehmen können?
|
||
Entsprechend sollte man sich auch immer Gedanken machen, was die Merkmale über die Gruppen aussagen und ob diese sinnvoll gewählt sind. Wenn man beispielsweise Kunden eines großen Einkaufszentrums in Kundengruppen einordnen möchte, um gezielter Werbung zu machen, könnte man messen, wie weit sie vom Einkaufszentrum entfernt leben (was nur wenig aufschlussreich sein könnte) oder alternativ erheben, wie viel sie von bestimmten Produkten bereits gekauft haben (was vielleicht eher eine effektivere Gruppierung ermöglicht).
|
||
„Hm, ich kann mich ja gar nicht erinnern, dass ich die sortiert hatte…“, runzelt der Professor die Stirn, als er seine Unterlagen auf dem Schreibtisch betrachtet. „Aber nun zu dem, weswegen du eigentlich hier bist…“
|
||
|
||
12
|
||
Fluch der Dimensionalität
|
||
Kein echter Fluch – aber auch kein Segen
|
||
Jannik Kossen und Fabrizio Kuruc
|
||
|
||
Im Kap. 8 zur linearen Regression haben wir versucht, aus einer Eigenschaft, der Tatzengröße, Rückschlüsse über eine Zielgröße, das Tiergewicht, zu ziehen. Es wäre auch denkbar gewesen, noch weitere Eigenschaften hinzuzunehmen, wie zum Beispiel die Tiefe des Fußabdruckes. Die Vorhersage über das Tiergewicht hätte sich dann aus der gemessenen Tatzengröße und der Abdrucktiefe ergeben.
|
||
Wir können die Anzahl der gemessenen Eigenschaften auch die Dimension der Daten nennen. Je größer diese Anzahl ist, desto mehr Eigenschaften haben wir für jeden
|
||
|
||
J. Kossen (*) Universität Heidelberg, Heidelberg, aus Darmstadt, Deutschland E-Mail: jannik.kossen@gmail.com
|
||
F. Kuruc Buseck, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
89
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_12
|
||
|
||
90 J. Kossen und F. Kuruc
|
||
einzelnen Datenpunkt. Für jede Eigenschaft kommt dann eine Achse im Koordinatensystem hinzu. Dies sehen wir auch in Abb. 12.1: Die Ausprägungen einer einzelnen Eigenschaft können wir sehr gut auf einer Achse festhalten. Bei zwei Eigenschaften, also zwei Dimensionen, können wir die Ausprägungen in einem Koordinatensystem mit zwei Achsen darstellen. Nehmen wir nun noch eine dritte Eigenschaft hinzu, so haben unsere Daten nun drei Dimensionen und wir benötigen auch ein dreidimensionales Koordinatensystem zur Darstellung. Mehr als drei Dimensionen sind mathematisch kein Problem, allerdings lassen sich diese nur noch schwer zeichnen.
|
||
Für Lisa bedeutet das Sammeln zusätzlicher Informationen erst einmal mehr Arbeit, denn nun muss sie neben der Tatzengröße auch noch die Tiefe des Abdrucks messen. Das könnte sich jedoch lohnen. Grundsätzlich sollte unsere Vorhersage besser werden, je mehr Eigenschaften wir in unserer Regression berücksichtigen können. Reale Datensätze haben oft viele Tausende solcher Eigenschaften. Die vielen Informationen können uns aber auch zum Verhängnis werden. Denn bei einer großen Anzahl an Dimensionen sind diese nicht mehr hilfreich. Ganz im Gegenteil: Wir werden vom sogenannten Fluch der Dimensionalität (buuuuuhhuhuhu) heimgesucht. Denn je größer die Anzahl der Dimensionen ist, desto größer wird die Anzahl der möglichen Kombinationen dieser Eigenschaften. Es wird schwieriger, sinnvolle Aussagen über den Zusammenhang der Eigenschaften zur Zielgröße zu treffen.
|
||
Um zu illustrieren, woran das liegt und wie bedeutsam der Fluch ist, gehen wir zurück zu Lisa und den Tatzengrößen. Im ursprünglichen Problem sollte aus nur einer einzigen Eigenschaft eine Vorhersage über die Zielgröße angestellt werden, nämlich aus der Tatzengröße über das Gewicht des Tieres. Lisa möchte nun Abdrücke bis zur
|
||
|
||
12 Fluch der Dimensionalität 91
|
||
Abb. 12.1 Für nur eine Dimension benötigt Lisa lediglich 10 Messungen, für zwei Dimensionen schon 100 Messungen und für drei Dimensionen sind schließlich 1000 Messungen nötig
|
||
Größe von einem Meter vermessen. Damit ihr Modell nachher auch für alle Größen in diesem Bereich gut funktioniert, ist es wichtig, dass sie sowohl kleine als auch große Tatzengrößen sammelt. Die Messpunkte müssen
|
||
|
||
92 J. Kossen und F. Kuruc
|
||
also gut über den Wertebereich der auftretenden Tatzengrößen verteilt sein. Da sie nicht alle Tatzenabdrücke der Welt vermessen kann, gibt sie sich mit 10 Messungen im Abstand von ungefähr 0,1 Metern zufrieden. Dies zeigt der eindimensionale Zahlenstrahl in Abb. 12.1 (oben).
|
||
Was passiert nun, wenn wir die Abdrucktiefe als zusätzliche Eigenschaft hinzunehmen?
|
||
Lisa benötigt nun ein zweidimensionales Koordinatensystem, in das sie die Kombination aus gemessener Tatzengröße und Abdrucktiefe eintragen kann. Wie viele Werte muss sie nun vermessen? Lisa nimmt an, dass die Abdrucktiefe ebenfalls zwischen 0 und 1 m liegt (etwas unrealistisch, aber mathematisch bequem). Und auch hier gibt sie sich mit Messwerten zufrieden, die in 0,1 m Abständen den Bereich abdecken. 10 Messwerte pro Eigenschaft ergeben bei zwei Eigenschaften dann 20 Messwerte, oder? Ganz und gar nicht! Wie man der Abb. 12.1 (mittig) entnehmen kann, braucht Lisa nun tatsächlich 10*10 = 100 Messwerte, um für alle möglichen Kombinationen der beiden Eigenschaften ausreichend Messwerte zu sammeln. Mit nur 20 Punkten im zweidimensionalen Koordinatensystem könnte Lisa hingegen nicht genug Kombinationen der Eigenschaften abdecken, um später eine verlässliche Aussage zu treffen.
|
||
Um sich dies zu erklären, denkt Lisa ans Würfelspielen. Wirft sie einen Würfel einmal, gibt es nur 6 mögliche Ergebnisse (1, 2, 3, 4, 5, 6). Wirft sie den Würfel hingegen zwei mal, gibt es schon 6*6 = 36 mögliche Würfe (1–1, 1–2, 1–3, 1–4, 1–5, 1–6, 2–1, 2–2, 2–3, 2–4, 2–5, 2–6, 3–1, 3–2 … usw. bis 6–1, 6–2, 6–3, 6–4, 6–5, 6–6). Bei drei Würfen gibt es folglich 6*6*6 = 216 mögliche Kombinationen. Hätte Lisa also noch eine dritte Eigenschaft gemessen, wie zum Beispiel das Gewicht der zugehörigen Kothaufen, müsste sie schon unglaubliche 10*10*10 = 1000
|
||
|
||
12 Fluch der Dimensionalität 93
|
||
Tiere vermessen, um das dreidimensionale Koordinatensystem ebenso dicht mit Punkten zu füllen (siehe Abb. 12.1 (unten)) wie im eindimensionalen Fall.
|
||
Dies ist der Fluch der Dimensionalität. Mit steigender Anzahl an Dimensionen eines Problems steigt die Anzahl der benötigten Messpunkte exponentiell an. Angenommen Lisa reichen im eindimensionalen Fall 10 Messpunkte, benötigt sie in zwei Dimensionen schon 100, in drei Dimensionen gleich 1000, in vier Dimensionen 10.000 und in zehn Dimensionen unvorstellbare 10.000.000.000 Datenpunkte. Mehr als drei Dimensionen kann man sich zwar schwer vorstellen, aber wir meinen mit Dimensionen ja nur die Anzahl der gesammelten Eigenschaften pro Messpunkt (oder Tier). Und bei einem Tier mehr als 3 Eigenschaften zu messen, ist doch durchaus möglich. Angenommen wir könnten durch unser zehndimensionales Koordinatensystem fliegen. Jeder Punkt, an dem wir vorbeiflögen, entspräche einer gemessenen Kombination der Eigenschaften. Lisa könnte sich zwar größte Mühe geben, möglichst viele Tiere zu vermessen, aber die benötigten 10.000.000.000 kann sie unmöglich schaffen. Deswegen wären wir die meiste Zeit einsam und allein beim Durchfliegen des hauptsächlich leeren Koordinatensystems. Nur ganz selten wären wir in der Nähe eines Datenpunktes, also einer Kombination aus Eigenschaften, die Lisa tatsächlich gemessen hat. Aber nur in der Nähe eines Datenpunktes kennen wir das Verhalten unserer Daten und nur hier können wir sichere Vorhersagen unserer Zielgröße treffen.
|
||
Je nach verwendeter Methode des maschinellen Lernens könnten aufgrund des Fluchs der Dimensionalität Lisas Vorhersagen sogar schlechter werden, wenn sie mehr Eigenschaften pro Tier misst, ohne auch exponentiell mehr Tiere zu vermessen. Der Fluch der Dimensionen ist eine
|
||
|
||
94 J. Kossen und F. Kuruc
|
||
ernst zu nehmende Hürde für das maschinelle Lernen und die künstliche Intelligenz. Denn oftmals befinden wir uns genau in der eben genannten Situation: Die Daten haben viele tausende Dimensionen und die geringe Anzahl der Datenpunkte erschwert es, die gesuchte Struktur in den Daten – die Ordnung im Chaos – zu finden. Wir Menschen hingegen haben mit dem Fluch der Dimensionalität scheinbar keine Probleme. In jeder Sekunde unseres Lebens, mit jedem Augenblick, jeder Berührung und jedem gehörten Geräusch nehmen wir umfangreiche – also hochdimensionale – Informationen auf, verarbeiten diese und unterscheiden dabei mit Leichtigkeit Wichtiges von Unwichtigem.
|
||
Wie man Dimensionen los wird
|
||
Eine Möglichkeit den Fluch der Dimensionalität zu umgehen, sind Methoden zur Dimensionsreduktion, welche die Dimensionalität der Daten clever verringern. Nach einer sinnvollen Verringerung der Dimensionalität eines Problems, wäre man vor dem Fluch sicher und könnte wieder die altbewährten Methoden anwenden. Diese sinnvolle Verringerung zu finden, ist leider oft nicht so leicht und manchmal fast unmöglich. Ein einfaches Beispiel für eine Methode zur Dimensionsreduktion ist die Hauptkomponentenanalyse aus Kap. 17.
|
||
|
||
13
|
||
Support Vector Machine
|
||
Immer schön Abstand halten
|
||
Jana Aberham und Fabrizio Kuruc
|
||
|
||
Erinnern Sie sich noch an Lisas Problem mit dem Sortieren der Möbel? Sie suchte eine Möglichkeit Stühle und Tische automatisch klassifizieren zu lassen.
|
||
Wir haben in Kap. 3 schon erkannt, dass Algorithmen genauso wie wir Menschen aus Erfahrungen lernen können. Aus Kap. 6 wissen wir noch, dass solchen Lernalgorithmen des überwachten Lernens Datenpunkte und die jeweils zugehörige Klasse zur Verfügung gestellt werden müssen. Diese Trainingsdaten hatte Lisa schon mit sehr viel Mühe durch das Etikettieren produziert. In unserem Fall besteht ein Datenpunkt aus Auflagefläche
|
||
|
||
J. Aberham (*) Karlsruhe, Deutschland E-Mail: jana.aberham@gmail.com
|
||
F. Kuruc Buseck, Deutschland
|
||
|
||
© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer
|
||
|
||
95
|
||
|
||
Nature 2019
|
||
|
||
K. Kersting et al. (Hrsg.), Wie Maschinen lernen,
|
||
|
||
https://doi.org/10.1007/978-3-658-26763-6_13
|
||
|