211service.com
Eine Maschine hat den Rubik’s Cube ganz alleine herausgefunden
Eine weitere Bastion menschlicher Fähigkeiten und Intelligenz ist dem Ansturm der Maschinen zum Opfer gefallen. Eine neuartige Deep-Learning-Maschine hat sich selbst beigebracht, einen Zauberwürfel ohne menschliche Hilfe zu lösen.
Der Meilenstein ist bedeutsam, weil der neue Ansatz ein wichtiges Problem in der Informatik angeht – wie man komplexe Probleme löst, wenn die Hilfe minimal ist.
Zuerst etwas Hintergrund. Der Rubik’s Cube ist ein dreidimensionales Puzzle, das 1974 von dem ungarischen Erfinder Erno Rubik entwickelt wurde, dessen Ziel es ist, alle Quadrate derselben Farbe auf derselben Seite des Würfels auszurichten. Es wurde zu einem internationalen Bestseller-Spielzeug und verkaufte sich über 350 Millionen Mal.
Auch bei Informatikern und Mathematikern stößt das Rätsel auf großes Interesse. Eine Frage, die sie fasziniert hat, ist die kleinste Anzahl von Zügen, die benötigt werden, um es aus jeder Position zu lösen . Die 2014 bewiesene Antwort lautet 26.
Eine weitere häufige Herausforderung besteht darin, Algorithmen zu entwerfen, die den Würfel von jeder Position aus lösen können. Rubik selbst entwickelte innerhalb eines Monats nach der Erfindung des Spielzeugs einen Algorithmus, der dies leisten konnte.
Versuche, den Prozess zu automatisieren, stützten sich jedoch alle auf Algorithmen, die von Menschenhand erstellt wurden.
In jüngerer Zeit haben Informatiker versucht, Wege zu finden, wie Maschinen das Problem selbst lösen können. Eine Idee ist, denselben Ansatz zu verwenden, der bei Spielen wie Schach und Go so erfolgreich war.
In diesen Szenarien erhält eine Deep-Learning-Maschine die Spielregeln und spielt dann gegen sich selbst. Entscheidend ist, dass es bei jedem Schritt entsprechend seiner Leistung belohnt wird. Dieser Belohnungsprozess ist enorm wichtig, da er der Maschine hilft, gutes Spiel von schlechtem Spiel zu unterscheiden. Mit anderen Worten, es hilft der Maschine beim Lernen.
Dies funktioniert jedoch in vielen realen Situationen nicht, da Belohnungen oft selten oder schwer zu bestimmen sind.
So lassen sich beispielsweise zufällige Drehungen eines Zauberwürfels nicht ohne Weiteres belohnen, da schwer zu beurteilen ist, ob die neue Konfiguration einer Lösung näher kommt. Und eine Folge zufälliger Runden kann lange dauern, ohne dass eine Lösung erreicht wird, sodass die Endzustandsbelohnung nur selten angeboten werden kann.
Beim Schach hingegen gibt es einen relativ großen Suchraum, aber jeder Zug kann entsprechend bewertet und belohnt werden. Das ist beim Rubik's Cube einfach nicht der Fall.
Betreten Sie Stephen McAleer und Kollegen von der University of California, Irvine. Diese Jungs haben Pionierarbeit für eine neue Art von Deep-Learning-Technik geleistet, die als autodidaktische Iteration bezeichnet wird und sich selbst beibringen kann, einen Zauberwürfel ohne menschliche Hilfe zu lösen. Der Trick, den McAleer und Co. gemeistert haben, besteht darin, einen Weg zu finden, wie die Maschine ihr eigenes Belohnungssystem erstellen kann.
So funktioniert das. Bei einem ungelösten Würfel muss die Maschine entscheiden, ob eine bestimmte Bewegung eine Verbesserung der bestehenden Konfiguration darstellt. Dazu muss es in der Lage sein, die Bewegung zu bewerten.
Die autodidaktische Iteration tut dies, indem sie mit dem fertigen Würfel beginnt und rückwärts arbeitet, um eine Konfiguration zu finden, die dem vorgeschlagenen Zug ähnlich ist. Dieser Prozess ist nicht perfekt, aber Deep Learning hilft dem System herauszufinden, welche Bewegungen im Allgemeinen besser sind als andere.
Nach dem Training verwendet das Netzwerk dann einen Standardsuchbaum, um nach vorgeschlagenen Zügen für jede Konfiguration zu suchen.
Das Ergebnis ist ein Algorithmus, der bemerkenswert gut funktioniert. Unser Algorithmus ist in der Lage, 100 % der zufällig gemischten Würfel zu lösen, während er eine durchschnittliche Lösungslänge von 30 Zügen erreicht – weniger als oder gleich Lösern, die menschliches Domänenwissen verwenden, sagen McAleer und Co.
Das ist interessant, weil es Auswirkungen auf eine Vielzahl anderer Aufgaben hat, mit denen Deep Learning zu kämpfen hat, darunter Rätsel wie Sokoban, Spiele wie Montezuma’s Revenge und Probleme wie die Faktorisierung von Primzahlen.
Tatsächlich haben McAleer und Co. andere Ziele im Visier: Wir arbeiten daran, diese Methode zu erweitern, um Näherungslösungen für andere kombinatorische Optimierungsprobleme wie die Vorhersage der Tertiärstruktur von Proteinen zu finden.
Ob diese Probleme für diesen Ansatz ebenso zugänglich sind, ist nicht klar. Sie profitieren im Allgemeinen nicht von einem Beweis, dass sie in einer kleinen Anzahl von Zügen gelöst werden können, wie dies beim Rubik’s Cube-Problem der Fall ist. Das hat hier zweifellos zu Gunsten des Teams gewirkt.
McAleer und Co. argumentieren, dass ihr Ansatz eine Form des Nachdenkens über Probleme ist. Sie weisen darauf hin, dass eine Definition von Argumentation lautet: algebraisches Manipulieren von zuvor erworbenem Wissen, um eine neue Frage zu beantworten.
Sie sagen, dass ihr Algorithmus namens DeepCube genau das tut. Herkömmliche Deep-Learning-Maschinen erkennen dagegen lediglich bestimmte Muster. DeepCube ist in der Lage, sich selbst beizubringen, wie man argumentiert, um eine komplexe Umgebung mit nur einem Belohnungszustand durch reines Verstärkungslernen zu lösen, sagen sie.
Womöglich. Der eigentliche Test wird natürlich sein, wie dieser Ansatz mit komplexeren Problemen wie der Proteinfaltung fertig wird. Wir werden beobachten, wie es funktioniert.
Ref: arxiv.org/abs/1805.07470 : Lösen des Zauberwürfels ohne menschliches Wissen