A network that learns Strassen multiplication
We study neural networks whose only non-linear components are multipliers, to test a new training rule in a context where the precise representation of data is paramount. These networks are challenged to discover the rules of matrix multiplication, given many examples. By limiting the number of multipliers, the network is forced to discover the Strassen multiplication rules. This is the mathematical equivalent of finding low rank decompositions of the $n\times n$ matrix multiplication tensor, $M_n$. We train these networks with the conservative learning rule, which makes minimal changes to the weights so as to give the correct output for each input at the time the input-output pair is received. Conservative learning needs a few thousand examples to find the rank 7 decomposition of $M_2$, and $10^5$ for the rank 23 decomposition of $M_3$ (the lowest known). High precision is critical, especially for $M_3$, to discriminate between true decompositions and "border approximations".
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Neural Learning of Fast Matrix Multiplication Algorithms: A StrassenNet Approach
Fast matrix multiplication can be described as searching for low-rank decompositions of the matrix--multiplication tensor. We design a neural architecture, \textsc{StrassenNet}, which reproduces the Strassen algorithm fo…
StrassenNets: Deep Learning with a Multiplication Budget
A large fraction of the arithmetic operations required to evaluate deep neural networks (DNNs) consists of matrix multiplications, in both convolution and fully connected layers. We perform end-to-end learning of low-cos…
Deep Learningimage-classificationImage ClassificationKnowledge Distillation+4Strassen Multisystolic Array Hardware Architectures
While Strassen's matrix multiplication algorithm reduces the complexity of naive matrix multiplication, general-purpose hardware is not suitable for achieving the algorithm's promised theoretical speedups. This leaves th…
Universal Matrix Multiplication on Quantum Computer
As a core underlying operation in pattern recognition and machine learning, matrix multiplication plays a crucial role in modern machine learning models and constitutes a major contributor to computational expenditure. H…
Fast Matrix Multiplication Without Tears: A Constraint Programming Approach
It is known that the multiplication of an $N \times M$ matrix with an $M \times P$ matrix can be performed using fewer multiplications than what the naive $NMP$ approach suggests. The most famous instance of this is Stra…
Deep Reinforcement LearningProblem Decompositionvalid