DeepMind Breaks 50-Year Math Record Using AI; New Record Falls a Week Later (arstechnica.com) 30
Last week, DeepMind announced it discovered a more efficient way to perform matrix multiplication, conquering a 50-year-old record. This week, two Austrian researchers at Johannes Kepler University Linz claim they have bested that new record by one step. Ars Technica reports: In 1969, a German mathematician named Volker Strassen discovered the previous-best algorithm for multiplying 4x4 matrices, which reduces the number of steps necessary to perform a matrix calculation. For example, multiplying two 4x4 matrices together using a traditional schoolroom method would take 64 multiplications, while Strassen's algorithm can perform the same feat in 49 multiplications. Using a neural network called AlphaTensor, DeepMind discovered a way to reduce that count to 47 multiplications, and its researchers published a paper about the achievement in Nature last week.
To discover more efficient matrix math algorithms, DeepMind set up the problem like a single-player game. The company wrote about the process in more detail in a blog post last week. DeepMind then trained AlphaTensor using reinforcement learning to play this fictional math game -- similar to how AlphaGo learned to play Go -- and it gradually improved over time. Eventually, it rediscovered Strassen's work and those of other human mathematicians, then it surpassed them, according to DeepMind. In a more complicated example, AlphaTensor discovered a new way to perform 5x5 matrix multiplication in 96 steps (versus 98 for the older method).
This week, Manuel Kauers and Jakob Moosbauer of Johannes Kepler University in Linz, Austria, published a paper claiming they have reduced that count by one, down to 95 multiplications. It's no coincidence that this apparently record-breaking new algorithm came so quickly because it built off of DeepMind's work. In their paper, Kauers and Moosbauer write, "This solution was obtained from the scheme of [DeepMind's researchers] by applying a sequence of transformations leading to a scheme from which one multiplication could be eliminated."
To discover more efficient matrix math algorithms, DeepMind set up the problem like a single-player game. The company wrote about the process in more detail in a blog post last week. DeepMind then trained AlphaTensor using reinforcement learning to play this fictional math game -- similar to how AlphaGo learned to play Go -- and it gradually improved over time. Eventually, it rediscovered Strassen's work and those of other human mathematicians, then it surpassed them, according to DeepMind. In a more complicated example, AlphaTensor discovered a new way to perform 5x5 matrix multiplication in 96 steps (versus 98 for the older method).
This week, Manuel Kauers and Jakob Moosbauer of Johannes Kepler University in Linz, Austria, published a paper claiming they have reduced that count by one, down to 95 multiplications. It's no coincidence that this apparently record-breaking new algorithm came so quickly because it built off of DeepMind's work. In their paper, Kauers and Moosbauer write, "This solution was obtained from the scheme of [DeepMind's researchers] by applying a sequence of transformations leading to a scheme from which one multiplication could be eliminated."
That's silly (Score:3, Funny)
Everyone knows that in $HighLevelLanguage, a matrix multiply is only one line of code!
Not in Python (Score:2)
You need to include 12 libraries.
And add a lot of tabs to this single line of code.
Or was it spaces? =/
Never trust a programming language made by a Dutch bureacrat playing with Dutch taxpayers money during worktime.
Re: Not in Python (Score:2)
import numpy as np A = np.random.random((3,4)) B = np.random.random((4,5)) C = A @ B
Re: Not in Python (Score:1)
Re: Not in Python (Score:3, Funny)
Yeah. If only programming languages had some kind of way to indicate that one statement ends, or that some set of code is encapsulated in a block. But that's science fiction, I know.
Hmm yes a fine successor the Strassen Algorithm (Score:1)
Re: (Score:2)
The 'FBHHRBNRSSSHK' Algorithm. Rolls of the tongue.
It sure does, if you're Bill the Cat, lead tongue for Deathtongue
Cue the nerds (Score:1, Troll)
Re: (Score:1)
I could have solved this in my sleep.
It was solved by an AI. It doesn't matter who presses the "start" button, or what they're doing while the software is running.
You want to be smarter than all the nerds, but you didn't even figure out the context successfully.
Re: (Score:1)
You have completely misunderstood his comment.
Re: (Score:2)
Even when warned you didn't understand the context, you dove right in blind! lol
Re: Cue the nerds (Score:2)
I could have solved this in my sleep.
It was solved by an AI
Do you see the issue yet?
Kasparov (Score:5, Interesting)
Kasparov was right. I remember some years ago, when he spoke at DEFCON, he said that computer+human assistance is better then either one alone (I guess that is fairly obvious). He also said said naive human + AI is better than smart human + AI. i suppose the smart human second guesses the AI in the wrong instances. Maybe a non-math/CS person ought to take a crack at this algorithm too.
Been done before (Score:5, Interesting)
BTW this is all theoretical and not practical. All of these techniques are numerically unstable so you wouldn't use them for reals, but only for matrix multiply over finite fields and they only really pay for humongous matrices.
Re: Been done before (Score:2)
Thereâ(TM)s value in working on enabling AI to assist in developing and optimizing algorithms. This shows a step towards that.
Re: (Score:2)
Re: (Score:2)
Is this really AI or just a brute force search?
Deepmind does not work by brute force searching. Not at all.
Re: (Score:3)
The CW matrix multiplication algorithm and its relatives have horrible constant factors that make them slower than Strassen for any matrix that is feasible to process on existing hardware. The algorithms presented in these papers have lower constant factors, so they're actually feasible to use -- when your matrix size has the right prime factors. (Strassen's algorithm has a smaller constant factor for its big-O time, so these all represent different points on a Pareto frontier. But if you read any of the
Re: (Score:2)
You should probably measure the time for n x n matrices, using the classical method, using a faster method for 2 x 2, 4 x 4, or 5 x 5 (having a 3 x 3 m
Re: (Score:2)
The methods for 4x4 and 5x5 should be easily integratable into Strassen's method. Having a non-power of two improves things for matrix sizes that are not a power of two, for example 100 x 100 which can be split into 96 20x20, each 20x20 into 96 4x4, and each 4x4 can be done wit
Re:Been done before (Score:4, Informative)
Naive matrix multiply is n^3. Strassen showed roughly O(n^2.8074). Currently the best algorithm has O(n^2.3728596) complexity but is impractical for realistic matrix sizes. All of these faster algorithms are based on Strassen's approach. See https://en.wikipedia.org/wiki/... [wikipedia.org]
I don't think DeepMind made this claim. All they showed is that they could solve some rather small matrices "faster" than current Strassen style decompositions. Their direct approach does not apply to arbitrary matrix multiply. Given the recursive nature of Strassen algorithms, I would guess these techniques might help, but I have not seen it reported.
It sounds like they previously developed a trick to shave off a multiply. They just applied their trick to the DeepMind solution. It probably required an insight that was not in the search space of the algorithm.
The naive multiply wins because it can be effectively parallelized with good cache performance.
impressive but not surprising (Score:2)
Is AI needed for that? (Score:2)
Re: (Score:3)
Can't this simply be brute forced for small matrixes?
It blows up incredibly fast, such that the answer isn't definitively known for n > 2.
Picking at crumbs? (Score:2)
I know the point is the accomplishment itself, but is there any significant improvement to be had by reducing 96 multiplications to merely 95? Is there any GPU that's going to process 95 multiplies in a cycle but the 96th one just can't be shoehorned in? The process may be interesting for the mathematical insight, but it may not be worth the extra time to code if you can get within one or two multiplies of ideal while remaining "pretty" and easy to maintain.
Re: (Score:2)
The improvement works recursively. For example, you can multiply a 25x25 matrix by treating it as a 5x5 matrix of 5x5 matrices. So, instead of 96*96 (9216) integer multiplications, you have 95*95 (9025).
The savings compound, so what was a ~1% improvement for 5x5 becomes ~5% for 3125x3125, and so on.
Re: (Score:2)
Thanks for the explanation. While you ideally never say no to extra speed, I don't think a 5% difference is going to be that important in most cases. By the time the savings compound that much, the system is going to run into other bottlenecks, unless the hardware is closely tuned to the load. I think for most people, the hardware is going to be one or more GPUs, meaning they're pretty far from tuned to the load although still immensely better than trying to do it on the CPU.
SIMD? (Score:2)
The number of linear (pun intended) steps is meaningless. The number of clocks matters.