Ars Technica berichtete im Oktober 2022, dass DeepMind einen effizienteren Weg gefunden hatte, Matrizen zu multiplizieren, und damit einen 50 Jahre alten Rekord brach. Im Jahr 1969 fand Volker Strassen einen Algorithmus, der zwei 4x4-Matrizen in 49 Multiplikationen statt in 64 nach der Schulmethode multipliziert. Mit einem neuronalen Netz namens AlphaTensor fand DeepMind einen Weg, dies in 47 zu tun, und veröffentlichte dies in Nature.
DeepMind stellte das Problem als Ein-Personen-Spiel auf. Das „Brett“ ist ein dreidimensionaler Tensor, der erfasst, wie weit der aktuelle Algorithmus von der Korrektheit entfernt ist; die erlaubten Züge entsprechen Algorithmusanweisungen, und der Spieler versucht, die Einträge des Tensors auf null zu setzen. Dies ergibt einen nachweislich korrekten Algorithmus für jedes Paar von Matrizen, wobei die Effizienz durch die Anzahl der Schritte erfasst wird. AlphaTensor, trainiert durch bestärkendes Lernen wie AlphaGo, entdeckte laut DeepMind zunächst Strassens Arbeit und die anderer Mathematiker wieder und übertraf sie dann.
Für 5x5-Matrizen fand AlphaTensor eine 96-Schritt-Methode gegenüber 98 für die ältere. Eine Woche später meldeten Manuel Kauers und Jakob Moosbauer von der Johannes Kepler Universität Linz 95 und schrieben, ihre Lösung sei aus DeepMinds Schema durch eine Folge von Transformationen gewonnen worden, die eine Multiplikation eliminierten. Ars merkt an, dass Matrixmultiplikation unter Spracherkennung, Bilderkennung und Grafik liegt und dass täglich Billionen solcher Berechnungen auf GPUs laufen, sodass sich kleine Einsparungen summieren können.
Die Suche nach schnelleren Matrixalgorithmen wurde als Ein-Personen-Spiel auf einem Tensor neu formuliert, sodass eine spielende KI nachweislich korrekte Algorithmen entdecken kann.
Ein korrekter Algorithmus ist ein auf null reduzierter Tensor, sodass die Korrektheit in die Spielregeln eingebaut ist.
Die Anzahl der verwendeten Schritte ist eine saubere Punktzahl, sodass die KI lernen kann, welche Züge zu kürzeren Algorithmen führen.
Matrixmultiplikation ist so weit verbreitet, dass selbst der Schritt von 49 auf 47 Schritte im GPU-Maßstab zählt.
Die Veröffentlichung des entdeckten Schemas ermöglichte es menschlichen Forschern, innerhalb einer Woche darauf aufzubauen.
Wenn ein Forschungsproblem als Spiel mit einer klaren Punktzahl formuliert werden kann, kann eine spielende KI es durchsuchen, und ihre Ergebnisse können weitere menschliche Verbesserungen anstoßen.
Eine Woche nach DeepMinds Ankündigung beanspruchten die beiden österreichischen Forscher ein Schema mit 95 Multiplikationen für 5x5-Matrizen, aufbauend auf DeepMinds Arbeit. Ars spekulierte, dass mit KI, die nun nach neuen Algorithmen sucht, bald weitere langjährige Mathematikrekorde fallen könnten.
DEN BELEGEN FOLGEN
Die Quellen
- DeepMind breaks 50-year math record using AI; new record falls a week later Ars Technica · arstechnica.com ·