Algorithmen für künstliche Intelligenz

the next big thing Golo Roden  –  26 Kommentare

Im Bereich der künstlichen Intelligenz (KI) gibt es zahlreiche Algorithmen für die verschiedensten Arten von Problemen. Welche grundlegenden Algorithmen sollte man in dem Zusammenhang einordnen können?

Vergangene Woche ging es um verschiedene Grundbegriffe der künstlichen Intelligenz. Sie stellen die Basis dar, auf der man sich mit einigen grundlegenden Algorithmen beschäftigen kann. Selbstverständlich gibt es zahllose Algorithmen für künstliche Intelligenz, aber einige davon sind essenzieller als andere und gehören somit eher zum elementaren Handwerkszeug.

Den Anfang macht dabei der k-Means-Algorithmus, der dazu dient, automatisiert Daten in Cluster einzuteilen, wobei lediglich die Anzahl, nicht aber die Art der Cluster vorgegeben sind. Da der Algorithmus vollständig autonom arbeitet, handelt es sich um einen Algorithmus, der unsupervised vorgeht.

k-Means besteht letztlich aus drei Schritten. Im ersten werden k Cluster erzeugt und die Daten zufällig diesen Clustern zugewiesen. Im zweiten Schritt wird der Mittelwert für jedes Cluster berechnet, der sogenannte "Centroid". Im dritten Schritt werden die Daten den Clustern neu zugeordnet, sodass sie dem Centroid des jeweiligen Clusters möglichst ähnlich sind. Anschließend wird so lange iteriert, bis keine Veränderung mehr auftritt.

Das wirkt auffallend unspektakulär und hat erschreckend wenig mit "Intelligenz" zu tun, ist aber tatsächlich einer der Algorithmen, die häufig als Einstieg in die KI gelehrt werden. Im Prinzip handelt es sich bei k-Means um nichts anderes als eine geschickte Kombination aus Raten und Rechnen, in Verbindung mit ein bisschen Statistik. So ernüchternd sich das anhört – das ist leider der Kern von ziemlich jedem KI-Algorithmus, es schwankt lediglich die Komplexität der Berechnungen.

Clustern mit K-Means

Genetische Algorithmen

Nicht viel anders sieht es bei "genetischen Algorithmen" aus, die häufig zum Lösen (beziehungsweise Annähern) von Optimierungsprobleme genutzt werden. Im Prinzip wird auch hier eine anfängliche Lösung zufällig geraten, die anschließend iterativ verbessert wird. Dazu stehen verschiedene Maßnahmen zur Verfügung, die an die Genetik angelehnt sind.

Dazu zählen beispielsweise die Mutation, bei der zufällig Elemente der Lösung verändert werden, und die Rekombination, bei der durch Mergen von verschiedenen Lösungskandidaten ein neuer geformt wird. Da es häufig bei Optimierungsproblemen schwierig ist, eine Lösung absolut zu bewerten, begnügt man sich mit relativen Vergleichen: So lange die Lösung durch Mutation, Rekombination & Co. besser wird, bewegt man sich anscheinend in die richtige Richtung.

Lösungen, die das Ergebnis wieder verschlechtern, werden in der Regel verworfen. Hier findet also eine Auslese statt. Auf dem Weg lässt sich beispielsweise eine Lösung für das TSP-Problem (Traveling Sales Person) annähern, allerdings mit deutlich geringerem Rechenaufwand, als wenn man klassisch versuchen würde, das Problem zu lösen.

Genetische Algorithmen

Neuronale Netze

Etwas anders sieht es schließlich bei neuronalen Netzen aus. Sie sind sozusagen das Paradebeispiel für erfolgreiche KI-Algorithmen, da viele Entwicklungen der vergangenen Jahre auf dem Fortschritt bei neuronalen Netzen basieren. Dieser Fortschritt ist allerdings weniger der Grundlagenforschung, sondern vielmehr der schnelleren Hardware zu verdanken.

Die Grundkonzepte neuronaler Netzen sind heute nämlich immer noch die gleichen wie vor 50 Jahren – nur stehen heutzutage mit leistungsfähigen GPUs extrem schnelle Chips zur Verfügung, die auf Vektor- und Matrizenrechnung spezialisiert sind, und Dinge ermöglichen, von denen man vor ein paar Jahrzehnten nur zu träumen wagte.

Prinzipiell besteht ein neuronales Netz aus Neuronen, wobei ein Neuron in dem Fall eine Funktion ist, die eine gewichtete Summe über ihre Parameter berechnet. Die Eingabewerte liegen üblicherweise zwischen 0 und 1, die gewichtete Summe kann aber größer als 1 werden. Daher wird das Ergebnis häufig noch normalisiert, beispielsweise mit der Sigmoid-Funktion. Durch die Gewichte lassen sich die einzelnen Summanden jeweils stärker betonen oder dämpfen.

Ordnet man solche Neuronen nun nebeneinander in einer Schicht und mehrere solcher Schichten hintereinander an und verbindet die Schichten, erhält man ein neuronales Netz. Das Training findet supervised statt, was bedeutet, dass sich Fehler berechnen lassen. Aus den Fehlern lässt sich mit einem Vorgehen namens Back-Propagation ermitteln, wie die Gewichte angepasst werden müssen, um den Fehler zu verringern. Auf dem Weg "lernt" ein neuronales Netz.

Letztlich handelt es sich bei einem neuronalen Netz also um nichts anderes als eine sehr komplexe Funktion. Üblicherweise wird mit drei Schichten gearbeitet, einem Input-, einem Hidden- und einem Output-Layer. Während die Anzahl der Neuronen in der ersten und dritten Schicht durch die Form der Eingabe und der erwarteten Ausgabe feststehen, ist der Hidden-Layer variabel.

Neuronale Netze

Generative, Convolutional & Co.

Wichtig bei neuronalen Netzen ist, dass die Daten stets nur von Schicht zu Schicht, sozusagen "vorwärts" weitergegeben werden. Daher spricht man auch von Feed-Forward-Netzen. Das muss aber nicht so sein. Es lassen sich beispielsweise Feedback-Schleifen einbauen, indem Neuronen sich selbst auf direktem oder indirektem Wege beeinflussen. In diesem Fall spricht man von Recurrent Neural Networks (RNN).

Daneben gibt es aber auch noch andere Arten neuronaler Netze, beispielsweise die Convolutional Neural Networks (CNN), die nicht nur einzelne Datenwerte, sondern auch deren Umgebung beachten. Das ist insbesondere im Bereich der Bild- und Spracherkennung sinnvoll, weshalb CNNs hier besonders häufig zum Einsatz kommen.

Außerdem lassen sich neuronale Netze auch kombinieren, indem beispielsweise ein Netz Daten erzeugt, die von einem anderen auf Gültigkeit überprüft werden. Auf dem Weg lässt sich Kreativität nachahmen: Ein Netz erzeugt beispielsweise Bilder, das zweite entscheidet, ob die Bilder gewissen Kriterien entsprechen, woraus das erste Netz wiederum lernt. Man spricht hier von Generative Adversarial Networks (GAN).

Generative, Convolutional & Co.

Deep Learning

Fügt man einem neuronalen Netz mehr als einen Hidden-Layer hinzu, spricht man von Deep Learning. Zunächst steigt der Rechenaufwand dadurch natürlich enorm an, die Hoffnung ist aber, bessere Ergebnisse zu erhalten. Das kann auch tatsächlich sein, allerdings wird die Frage nach der Anzahl der Neuronen in den Hidden-Layern nun schwieriger, zumal auch noch die Anzahl der Hidden-Layer an sich zu definieren ist. An der Stelle kommt daher viel Trial-and-Error zum Einsatz.

Der Ansatz kann mit den zuvor genannten Arten neuronaler Netze kombiniert werden, man spricht dann beispielsweise von Deep Convolutional Neural Networks (DCNN), was zugegebenermaßen sehr hochtrabend klingt, aber eigentlich auch nichts anderes ist als das zuvor beschriebene Modell, nur mit mehr Rechenaufwand – was wiederum nur dank der heutzutage verfügbaren leistungsfähigen Hardware möglich ist.

Deep-Learning

Fazit

Die Frage, die sich bei alldem stellt, ist: Wohin wird uns das noch bringen? Wirkliche Fortschritte im großen Stil sind bis heute Mangelware, von einer starken KI, die dem Menschen ebenbürtig wäre, ist man nach wie vor sehr weit entfernt. Die erste Ernüchterung trat in den 1980er/90er-Jahren ein. Das ging so weit, dass damals vom sogenannten KI-Winter die Rede war.

All die modernen KI-Entwicklungen der vergangenen zehn Jahre sind einerseits beeindruckend, andererseits aber nicht das, was sie vorgeben zu sein, da sie eben primär der gestiegenen Rechenleistung geschuldet sind. Es bleibt abzuwarten, wie lange das noch funktioniert, und wann der zweite KI-Winter einsetzt. Dass er kommen wird, steht fest – die Frage ist nur, wann.