21–30 of 85 posts
Man I remembered something similar I had tried working on in 2018, but gave up after all my PhD applications got rejected. https://github.com/ixaxaar/pytorch-dni The concept here goes a bit further and tries to replicate backprop with an external network, arguing that that's probably what the brain actually does.
This looks pretty cool! What's the catch? e.g. why isn't this already implemented in accelerators, is it really just a forgotten algorithm, or this has some implications on the cost of building the accelerator or else?
It's not just a software algorithm. It's a hardware architecture optimization. To benefit, you have to build hardware that matches the dimensions of the algorithm. That's an expensive commitment.
Yes the benefits are realized in custom hardware designs as opposed to software, however, the hardware architectures work for multiplying matrices of arbitrary dimensions by splitting up larger matrices into smaller tiles, then summing up the tile products to form the final larger matrix products (i.e. GEMM)
Man I remembered something similar I had tried working on in 2018, but gave up after all my PhD applications got rejected. https://github.com/ixaxaar/pytorch-dni The concept here goes a bit further and tries to replicate backprop with an external network, arguing that that's probably what the brain actually does.
Unrelated to the technical discussion but I was wondering what you made that architecture gif with? Looks neat!
Earlier quoted context omitted.
Not to everyone. If it's clear to you, you could helpfully explain it.
This is an analogy. a^2 - b^2 = a a - b b. This can be factored to (a+b)(a-b). In the first expression there are two multiplies, in the factored version there is only one. However, from a numerical analysis / accuracy standpoint, evaluating the factored expression can result in loss of precision in the result when a is close to b. This is especially true if you repeatedly and sequentially do a lot of these operations…
I conjecture that for every j > 0 in R, a number n exists so that any two n x n matrices can be multiplied together in O(n^(2+j)) steps.
(Now proven for for 2+j = w = 2.3728596, or j > 0.3728596)
If you're interested in the mathematical theory behind sub-cubic algorithms for matrix multiplications, you can start from here: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith... I conjecture that for every j > 0 in R, a number n exists so that any two n x n matrices can be multiplied together in O(n^(2+j)) steps. (Now proven for for 2+j = w = 2.3728596, or j > 0.3728596)
If you're interested in the mathematical theory behind sub-cubic algorithms for matrix multiplications, you can start from here: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith... I conjecture that for every j > 0 in R, a number n exists so that any two n x n matrices can be multiplied together in O(n^(2+j)) steps. (Now proven for for 2+j = w = 2.3728596, or j > 0.3728596)
Predicting that this holds for any j > 0 seems rather bold. Would you care to share your intuition why you think that's the case?
It's clear that the algorithm needs at least O(N^2) because to access each element of the matrices once, you need a double for loop, which is O(N^2).
for i in rows
for j in cols
# do something with element matrix1 [i, j], matrix2[i, j],...
If you're interested in the mathematical theory behind sub-cubic algorithms for matrix multiplications, you can start from here: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith... I conjecture that for every j > 0 in R, a number n exists so that any two n x n matrices can be multiplied together in O(n^(2+j)) steps. (Now proven for for 2+j = w = 2.3728596, or j > 0.3728596)
Is this stated correctly? Because it seems almost meaningless as stated. You start with "for every j, there exists an n such that...". That would mean that for the rest of the statement, n and j are constant. So you are just saying that you can multiply constant sized matrices in constant time. Technically true, but I feel like you are trying to claim something stronger.
Another cool way to eliminate multiplication in matrix multiplication is to use different semirings [1]. The Tropical Semiring [2] for example substitutes addition for multiplication and min (or max) for addition. It's still matrix multiplication but with substituted binary operations. The research in this relatively new field of Tropical Algebra [3] is quite active and rich right now, being used for all kinds of optimization problems and in research for optimizing neural networks [4] . This approach also lends itself to hardware synthesis since most FPGA configurable logical blocks can add/min/max in one clock cycle, whereas efficient multiplication requires fixed dedicated on-chip hardware multipliers.
Another way to efficiently remove multiplications with a different but related semiring is to use a Log Semiring [5]. If you have to multiply chains of probabilities (like Markov chains) then the numbers quickly become very small and floating point loses its accuracy to represent the numbers. By scaling the numbers first by taking the log, multiplication becomes addition and addition becomes x + log1p(exp(y - x)).
[1] https://en.wikipedia.org/wiki/Semiring
[2] https://en.wikipedia.org/wiki/Tropical_semiring
[3] https://en.wikipedia.org/wiki/Tropical_geometry
This looks pretty cool! What's the catch? e.g. why isn't this already implemented in accelerators, is it really just a forgotten algorithm, or this has some implications on the cost of building the accelerator or else?
There are a lot of matrix multiplication algorithms out there with a lot of pluses and minuses. It's always a balance of accuracy, runtime, and scaling. This one probably has bad accuracy in floating point.