12 ms·

Multiplying Matrices Without Multiplying

235 points by moinnadeem 5y ago

ausbah 5y ago
as a total outside to this sort of stuff, doesn't this have the big issue of error propagation?
- echelon 5y ago
  Probably, but hill climbing will avoid loss in the long run. The speed boost is probably more than worth it. I wouldn't be surprised if we started using lossier math for faster state space search. Once you find a peak, you could swap out the maths to be more exact.
  - erosenbe0 5y ago
    Suppose you have a set membership question. If you approximate yes, you do a more complex inquiry to grab details. If you approximate no, you tell the user no, don't know that face [answer, command, etc]. So this is ripe for approximate methods as you can tune to get very few false negatives (respond no when it's really yes), but allow a healthy dose of false positives.
    - shadowgovt 5y ago
      This reminds me of the mechanism of a bloom filter (https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter).
nynx 5y ago
Huh, that’s kinda fascinating. Maybe it’d be worth running ml on matrix multiplication that’s approximated by ml?
- TrainedMonkey 5y ago
  Ironic thing is large part of how ML works is via matrix multiplication.
  - r00fus 5y ago
    That's not ironic, it could be revolutionary for this algorithm and ML in general.
  - uluyol 5y ago
    Lots of things are like this. I program my network using a network. I run a server (BMC) on my server. I start my engine with an engine (https://en.m.wikipedia.org/wiki/Lockheed_SR-71_Blackbird https://en.m.wikipedia.org/wiki/Lockheed_SR-71_Blackbird).
  - deleted 5y ago
    [deleted]
  - noobermin 5y ago
    It important to remember dense matrix multiplication (doing it by hand) is a O(N^3) operation, this is about approximations to multiplication that beat that already harsh complexity. There is a whole field that develops approximations to matrix multiplication of large matrices, I'm assuming this article is about using ML to find good approximations. To the replies, the very act of evaluting a prediction from a NN is matrix multiplication (linear transform of a column vector is matrix multiplication). This doesn't replace matrix multiplication wholesale, lol. This is about multiplication in a specific case.
    - Nevermark 5y ago
      As long as their is enough consistency between approximating a multiply X*W and Z*Wt (Wt = W transpose), then it is possible it could be used in NN training. Y = X*W is the forward propagation. If Z is an error or derivative of error, Z*Wt is the back propagation. Its an interesting question as to how well that would work. Anything that speeds up matrix multiply in NN and deep learning in general would be a big deal.
    - 5y ago
random314 5y ago
Ha ha! What the hell! This is revolutionary if true!
antonzabirko 5y ago
Had this same exact thought as an undergrad like 3 years ago! I kinda gave up due to the massive barrier and difficult financial burdens faced by phd students. This feels nice to know i wasn't crazy.
- jmount 5y ago
  In my opinion, that is the thing with theoretical computer science. Many of the ideas are comprehendible. And if one has the opportunity to do the work: you may get the result.
  - jvanderbot 5y ago
    Well, taken to the extreme, and from what I can tell, that's the truth for any field. If you roll everything, financial incentives, emotional readiness, support and preparation, etc, into 'opportunity' then yeah, I believe it.
  - mhh__ 5y ago
    The biggest blocker for me is usually working out how I can implement a given idea without either writing a bunch of code (I'll get bored) or trying to verify if the paper even works for my use case without doing the aforementioned. One field I pay attention to with this problem seems to be abstract interpretation, with my background at least, the methods are very theoretically clean and impressive but actually implementing these as code and knowing how to write good implementations seems to be quite obtuse. I genuinely don't understand why we allow papers to be published on computer science, with graphs plotted of the supposed efficacy of research (i.e. not just a theoretical paper), with no code attached.
    - jijji 5y ago
      On page six of the paper: To assess MADDNESS’s effectiveness, we implemented both it and existing algorithms in C++ and Python. All of our code and raw numerical results are publicly available at https://smarturl.it/Maddness https://smarturl.it/Maddness. All experiments use a single thread on a Macbook Pro with a 2.6GHz Intel Core i7-4960HQ processor. edit: the url above redirects to: https://github.com/dblalock/bolt https://github.com/dblalock/bolt
alfor 5y ago
I wonder how our brain can train billion of neuron without matrix multiplication. What is the biological process that get a similar result?
- jvanderbot 5y ago
  Perhaps addition and multiplication are the tools we use to get a computer to appear to act like a biological system with all its chemical pathways and simultaneous stimuli. Lets take that one step further. Who taught orbiting bodies how to do differential equations?
  - alfor 5y ago
    That’s a good one! I feel there is a difference as the cells are actively doing something, they are fighting entropy and create structure. In a similar way we are with our programs, of course what we do is a crude approximation of what neuron cells do in other ways. In other words, I wonder it there is a process that we could use to speed up neural training by looking at how the brain does it.
    - MauranKilom 5y ago
      I feel that the presented algorithm is actually somewhat close to what our brains do in similar tasks. As mentioned elsethread, the problem is essentially reduced to determining angles between two vectors (one of which is known ahead of time) in high dimensional space. This is done by projecting the other vector into different specially chosen subspaces and classifying it in those, then summing up the "scores" in each subspace. Given the similar task of determining the angle between two lines in 3D space, we tend to do something very similar (I feel): We look at the pair of lines (or vectors) from a few different perspectives (="subspaces") and get a feel for how well-aligned they are in each (="score"). We can then guess pretty well how large the angle between the two is. Of course, we frequently use other cues too (e.g. perspective and texture when talking about alignment of real-world 3D objects). And even when you are considering plain lines displayed on a screen (in which case these cues don't work), we tend to also take into account the relative movement of the objects as we (continuously) shift our perspective (e.g. drag-to-rotate a scene). Maybe the latter part could also be a hint towards further algorithmic ideas. Maybe somehow involving (signs of) derivatives (finite differences?) or similar could be a cheap way to improve accuracy. Just spitballing here though.
yangjunpro 5y ago
An interesting work, with some to-be-addressed questions: 1.The paper only covers the GEMM part with small-scale experiments(CIFAR-10/100), not covering convolution, not covering GEMM part in more popular network such as Transformer/BERT, etc. 2. It is still an approximating method, meaning potential accuracy loss. So I think this method is less attractive to training acceleration scenario, maybe potentially as a complementing methods for inference acceleration. 3. No results evaluated in GPU with TensorCore equipment. I am a little bit curious, since modern AI accelerator(including NV GPU) all incorporate TensorCore which by-design supports GEMM acceleration, what is the add-on value brought by the approximating method mentioned in this paper.
- Ar-Curunir 5y ago
  If it works better for inference, it could enable fast inference on devices which don't have good tensor cores/gpus
- ffast-math 5y ago
  Great observations. I see this paper as the first in a three-part series. The second part is specializing it for convolution (which has additional structure to exploit), and the third is hooking these approximate ops into deep neural nets the way people currently do with scalar quantization / pruning. I'm not optimistic about beating tensor cores when running on GPUs, at least until/unless we get similar hardware support.* Barring better hardware support, the killer app is probably CPU inference--once there are Conv implementations and the necessary GPU kernels to train the network. *Aside: this support would be pretty doable since the kernels look almost identical to GEMM kernels--you just need a multiplex-add rather than a multiply-add. On an x86 machine, all it would take is a vpshufb-add and a 4-bit unpack instruction.
- criticaltinker 5y ago
  > I think this method is less attractive to training acceleration scenario The proposed hash based encoding function is not differentiable, so it doesn’t appear this method can be used for training at all. I’m not aware of any hash functions that are analytically differentiable, so to support efficient back-propagation I suspect that some fundamental changes to this method would be necessary.
trilinearnz 5y ago
Clever and logical. It reminds me of when John Carmack used a precomputed table of Sine values for fast lookup in Quake, rather than running the actual function on the CPU.
- richrichardsson 5y ago
  I was using a precomputed table of sine values in 3D graphics way before Quake ever hit the scene, and I certainly didn't invent that idea either.
  - trilinearnz 5y ago
    Ah that's useful to know that it was conventional up until then, thanks. It was my first exposure, personally :)
    - eesmith 5y ago
      Checking Google Scholar, I found this 1962 paper by King titled "Table Look-Up Procedures in Data Processing" - https://dl.acm.org/doi/abs/10.1145/800198.806120 https://dl.acm.org/doi/abs/10.1145/800198.806120 > It is not generally known that to provide seven- decimal accuracy of the sine function, allowing third-order interpolation, only 15 entries are required [*] ... The following commentary is interesting. > In spite of these developments in table construction, it turned out two decades ago that the technology was such that table look-up was too slow for arithmetic. The stored-program type of machine displaced this approach. By this method the value of a function, such as sin x, is computed afresh every time. One cannot but wonder how many times such a number has been re-computed in the last decade, and inquire whether technological developments may make tables efficient again. > Over the years the emphasis in machines has slowly changed from the central processing unit to memory. From the point of view of table look-up, the memory is the central feature of a machine. Indeed the central processing unit is unnecessary. The [*] is Krawitz. E., "Proc. Industrial Comp. Seminar," IBM, p. 66, 1950. I cannot find this publication with only a simple search. See also https://scholar.google.com/scholar?as_sdt=0%2C5&as_yhi=1990&q=sine+%22lookup+table%22 https://scholar.google.com/scholar?as_sdt=0%2C5&as_yhi=1990&... which finds titles like "A rapid lookup table method for trigonometric functions" (1982) at https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380121002 https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801210... .
leecarraher 5y ago
For some reason they run all their tests single threaded. Seems like parallelism is where all computing hardware is inevitably going. I also wish they had run time comparisons to more recent matrix sketching and multiplication method such as frequent directions, newer FJLT implementations, and RIP matrices based on hashing.
- ffast-math 5y ago
  We compared to several frequent directions variants, Fast Johnson–Lindenstrauss, some other hashing-based methods, and a bunch of other approximate matrix multiplication approaches. We had to omit some of them from the results section though because they were 10-100x worse than exact matrix products and they ruined the plots. More info in appendix E5. As far as single threaded, there's a simple answer and a subtle one. The simple answer is that we consider the core subroutine a single thread would run in a multithreaded context, not how to do the multithreading. These are basically orthogonal issues since matrix multiplication is embarrassingly parallel and our method would parallelize just like any other. More details in appendix E2. The subtler answer is that we could do even better in the multithreaded context if you could fuse the encoding step with whatever earlier code produces the larger matrix. This is a result of matrix products becoming memory-bandwidth-bound in the limit of sufficient cores, combined with our approach reducing the size of the matrix by a huge amount.
esjeon 5y ago
> MADDNESS I think this name really fits well to the concept. Replacing matrix-multiplication with some hash-lookups! (warning: an overly simplified statement) This is a really interesting application of PQ(product quantization), which itself also requires learning (usually K-means). Paper: https://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_with_quantization.pdf https://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_wi... Considering that ANN has survived through many approximations (e.g. lower precision, pruning), and that many ANN applications are anyway subjective (e.g. image processing, recommendation), I think this can be highly useful in many cases.
- arthur2e5 5y ago
  Certainly off topic, but gotta say I prefer “MADDLESS” over “MADDNESS” for being more… obvious. It still sounds close enough to me, but again I might be just letting my Southern-Chinese ear loose with the n/l confusions…
joe_the_user 5y ago
Shouldn't the solution to fast matrix multiplication be logarithms, similarly to fast scalar multiplication? https://en.wikipedia.org/wiki/Logarithm_of_a_matrix https://en.wikipedia.org/wiki/Logarithm_of_a_matrix
- PythonNut 5y ago
  Perhaps surprisingly, the matrix logarithm does not satisfy log(A) + log(B) = log(AB) in general (only when AB = BA) which is why you cannot use it to "multiply by adding".
  - adgjlsfhk1 5y ago
    More importantly, matrix logarithms only exist for square matrices.
    - xyzzyz 5y ago
      That’s not that big of a problem, as you can easily reduce the problem of multiplication of rectangular matrices to multiplication of square ones.
cs702 5y ago
Every element of a matrix multiplication is a dot-product of two vectors. The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if < 0, the two vectors point in dissimilar directions; if = 0, the two vectors are orthogonal. It's not too hard to imagine that it might be possible to learn representative K-means clusters of training vectors and then, at run-time, find similar vectors using an efficient hashing scheme and do the equivalent of a table lookup to get the approximate dot-product similarity scores -- without having to perform any multiplications. This isn't quite correct (I'm oversimplifying and ignoring many important details), but I think it's a helpful mental image. Very clever stuff.
- xyzzyz 5y ago
  The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if < 0, the two vectors point in dissimilar directions; if = 0, the two vectors are orthogonal. To make it more explicit, dot product of two vectors is just cosine of the angle between them, multiplied by their lengths.
  - kazinator 5y ago
    The angle and cosine start to lose their geometric intuition when we go beyond 3D. The concept of correlation has no issue with additional components. The concept of similarity of two 17-element vectors is clear. In fact correlation intuitively scales to "infinite component vectors": the dot product becomes multiplying two functions together and then taking an integral. The Fourier transform of a periodic signal is based in the concept of how similar the signal is to a certain basis of sine/cosine quadratures spaced along a frequency spectrum. This is like a projection of a vector into a space; only the vector has an infinite number of components since it is an interval of a smooth function.
    - Y_Y 5y ago
      This idea generalises to the concept of https://en.wikipedia.org/wiki/Inner_product_space https://en.wikipedia.org/wiki/Inner_product_space and a the equivalent of a change-of-basis.
infogulch 5y ago
I wonder how much alternative number representations have been studied for use in matrices. Like, storing the log of values instead so that multiplication can be done by just adding. Or something like Zech's logarithm. Or even, take the log of whole matrices (which is a thing apparently [0]), then adding them to compute their multiplication. I wonder if the logarithm of a matrix can be computed using ML. [0]: https://en.wikipedia.org/wiki/Logarithm_of_a_matrix https://en.wikipedia.org/wiki/Logarithm_of_a_matrix
- thwoeri2324 5y ago
  Quick note: the exp does not work the way it does with scalars. https://en.wikipedia.org/wiki/Matrix_exponential#Elementary_properties https://en.wikipedia.org/wiki/Matrix_exponential#Elementary_...
- ffast-math 5y ago
  There's been some work on doing adds instead of multiplies (e.g., https://arxiv.org/abs/2012.03458 https://arxiv.org/abs/2012.03458). And I think float8 will roughly be doing this under the hood. Personally, I'm not sure whether this is the path to go down or not. Doing everything in log space could help from a hardware perspective, since multiply-adds are much more complex than adds. But it 1) doesn't reduce the number of operations being performed, 2) might increase the necessary bit width for a given level of fidelity (depending on your input distribution and other factors), and 3) might make accumulate operations expensive, since these aren't cleanly expressed in the log domain.
- rocqua 5y ago
  storing log values helps with the multiply part of multiply and add. But it seems like it would make the add part of multiply and add quite a bit more difficult.
- michelpp 5y ago
  There is a logarithmic semiring: https://en.wikipedia.org/wiki/Log_semiring https://en.wikipedia.org/wiki/Log_semiring which can be used to multiply two sparse matrices with the GraphBLAS. here is an example in Python: https://github.com/Graphegon/pygraphblas/blob/main/demo/Log-Semiring.ipynb https://github.com/Graphegon/pygraphblas/blob/main/demo/Log-...
ffast-math 5y ago
Primary author here. Happy to answer questions! Also, feel free to email me at the address in the paper if you're interested in talking about it in more detail. E.g., I've already heard from some hardware folks looking at expanding on this work.
- FabHK 5y ago
  So, do I understand this correctly: 0. The problem you're really looking at is quickly computing a'B for many different vectors a (of length D) which are conceptually random. 1. To do that, you approximate AB, where A is very long and thin (NxD), and B (DxM). (Note: this problem has complexity O(NDM) naively, or, if N=D=M, O(N^3), and there are smarter algorithms that reduce the exponent 3 down to 2.8 (Strassen) or even further down, though those are not practical from what I gather. Oh, and note that at minimum, you're looking at time (N+M)D, because you need to look at every element, unless you approximate). 2. You approximate AB by f(g(A),h(B)), such that the error (in "relative Frobenius norm", ie norm of the error divided by norm of the actual product) is "small" with "high probability". 3. You're given B and a "typical" A^~ (ie training data), and then have two steps: 3.1. Do some training mumbo jumbo (fast?), and 3.2. now finally you can quickly compute the approximate AB (or a'B) for "new" A (or a'), presumably fast? Quite cool that there are new techniques (and apparently fast, the article claims 100x faster than exact, and 10x faster than existing approximations) for such a classic problem! But, if I understand correctly, it could happen with a certain probability that the actual error is quite high? Maybe if your a' is untypical? ETA: From what I understand, in many ML applications people use 32bit or even 16bit floats, so high accuracy is not as important as speed anyway?
  - ffast-math 5y ago
    Yes, basically correct. A couple notes/clarifications for other readers: - The rows a of A are "random," but in the sense of being drawn from some distribution for which we have a training set--not in the sense of, e.g., "assume everything is gaussian" or some other idealized case. - The training takes a few seconds to maybe a couple minutes, depending on your training set size. But it does have to be done ahead of time--you can't train after receiving the matrices and still get a speedup. Unless maybe the matrices are unrealistically large. - The error in the approximation is provably not much larger than the error on the training set with high probability (under standard ML assumptions--finite variance, training and test distributions match), but there's no hard limit on it in general. If you know the range of values in your individual vectors, you could obtain a hard limit, although it would be much looser than what you see in practice. - Correct that many ML applications tolerate large losses in precision. But caveat is that we won't get the right answer to a full 16 bits in each element (this would be ~99.999% accuracy), but instead more like 90-99.9%, depending on the speed-quality tradeoff chosen. So we can't claim it will be sufficiently accurate in all cases
kazinator 5y ago
If machine learning depends on matrix multiplications, but you fib them using machine learning ... do you see the problem?
- qsort 5y ago
  If a C++ compiler depends on a C++ compiler to be compiled itself... do you see the problem? I have only superficially looked at the paper, but it's pretty clear they are using an offline lookup table. There are no such problems involved.
  - kazinator 5y ago
    Yes, I do; your bootstrapping is dependent on a binary C++ compiler, which could be hiding something that isn't in the source code, but which propagates to newly bootstrapped compiler binaries which again pass it on to the next round of bootstrapping, ad infinitum. Basically, we can't be sure that you really have a C++ compiler. The source code can be verified to be a C++ compiler, but the binaries deviate in some way, possibly malicious.
    - robertlagrant 5y ago
      Sure, but you seem to have gone off on a wild tangent. How does that relate to matrix multiplication?
      - deleted 5y ago
        [deleted]
      - kazinator 5y ago
        By "you", you mean user qsort, right?
      - setr 5y ago
        I believe he’s getting at the idea of nested levels of corruption, with no visibility into where that corruption happens (because recompilation of the compiler/ML produces a fresh inscrutable binary). I suppose the better term in this context is error propogation
TaupeRanger 5y ago
Method 1: computer, use MUL to multiply X and Y. Method 2: computer, remember this number. When I give you X and Y, tell me what that number was. This requires no multiplication! Let us tell SCIENCE about our discovery!
- rm445 5y ago
  How about using a look-up table for small numbers (say up to 12x12), left shifts for powers of ten, and decomposing larger multiplications into summation of those operations?
- MauranKilom 5y ago
  Or, oversimplified in a different way: Method 1: Computer, tell me the angle between these two 3D lines! Method 2: Computer, look at this (second) 3D line from a few different perspectives (determined by the first line) and then tell me how often it looks more vertical than horizontal. That'll give me a good enough idea of the angle between the two.
- ffast-math 5y ago
  So this misses a few aspects of why the method works: - You can't actually get a speedup from the proposed approach. You'd need a lookup table of size b^2 to multiply two b-bit numbers, which will be much slower than just doing the multiplication. - Most of what we do is perform fewer operations. We're actually slower per op than multiply-adds because those are supported better in hardware. We just compress the matrices by so much that it's worth it. Relatedly, for sufficiently few codebooks, we're actually sublinear in the input size--i.e., we don't even read it all. - We have some lightweight machine learning in there to make the sublinearity and other approximations not suck. Getting the ML fast enough to beat a BLAS GEMM is far from trivial.
bawana 5y ago
Lots of discussion here about higher dimensional matrices. The argument is that the dot product is an operation on two arguments, therefore any multidimensional matrix multiplication can be broken down into multiple two dimensional operations. The image offerred is that two vectors define a plane so any two dimensional operation is valid. But how about curved space? Suppose I have two vectorsin curved space-they look like two droopy arrows. How does one calculate this dot product? I guess the the local curvature has to be taken into account. In spherically shaped space, this is a constant, but what about irregularly bent space-like that near an amorphous blob of dark matter? Suppose you are trying to calculate electrostatic potentials or do anything with Maxwell's equations? Currently, we define the curvature of space with gravity or the deflection of light past massive objects. Is there a way to measure the curvature of space locally? Can the curvature of space alter the piezoelectric potential generated by a crystal for example and allow its measurement- I am thinking that a miniscule deformation on a large macroscopic object is multiplied many fold on a property that is distributed over the atomic level and happening in parallel on all the atoms of a crystal.
- codethief 5y ago
  > But how about curved space? Suppose I have two vectorsin curved space-they look like two droopy arrows. No, they don't. In math, curved spaces are modeled through so-called manifolds which locally look like ℝ^n. In particular, at any point p of the manifold there's a tangent space, i.e. a linear space (higher-dimensional plane) tangent to the manifold at p. Vectors at p are just vectors in that linear space. So they are "straight" not "droopy". On the tangent space of each point p you can now define an inner product g(p). The resulting family of inner products g is called a (Riemannian) metric on the manifold[0] and describes how lengths (of vectors) and angles (between vectors) can be measured at each point. > Currently, we define the curvature of space with gravity or the deflection of light past massive objects. Is there a way to measure the curvature of space locally? Yes, there is. In fact, the curvature[1] of a (Riemannian) manifold is a purely local quantity – it's basically the second derivative of the metric g, so it describes how the notion of length changes (more precisely: how the change in length changes) as you go from a point p to neighboring points. There are other ways to express what curvature is, e.g. by locally parallelly transporting[2] a vector along a closed curve (and making that curve smaller and smaller) which basically measures how the notion of straight lines changes locally. (Though, since a line being "straight" means "locally length minimizing" this brings us back to the notion of length and, thus, the metric.) Alternatively, if the manifold has dimension 2, there's a particularly simple way of looking at and interpreting curvature, see [3]. In any case, curvature being used to model gravity is entirely separate from that idea. [0]: Provided this inner product "varies smoothly" as you move from p to a neighboring point q. [1]: https://en.wikipedia.org/wiki/Riemann_curvature_tensor https://en.wikipedia.org/wiki/Riemann_curvature_tensor [2]: https://en.wikipedia.org/wiki/Parallel_transport https://en.wikipedia.org/wiki/Parallel_transport [3]: https://en.wikipedia.org/wiki/Gaussian_curvature https://en.wikipedia.org/wiki/Gaussian_curvature
sriram_malhar 5y ago
Can someone help me understand how approximate it is? what are te error bounds?
- ffast-math 5y ago
  We have a generalization guarantee in Section 4.5. It's not especially tight though; in practice, the errors from different codebooks tend to be mostly independent, and you get nice Gaussian-like concentration. I would look at the empirical results in Section 5 to get a better feel for how it performs in practice.

235 points by moinnadeem 5y ago

ausbah 5y ago

as a total outside to this sort of stuff, doesn't this have the big issue of error propagation?

echelon 5y ago
Probably, but hill climbing will avoid loss in the long run. The speed boost is probably more than worth it. I wouldn't be surprised if we started using lossier math for faster state space search. Once you find a peak, you could swap out the maths to be more exact.
- erosenbe0 5y ago
  Suppose you have a set membership question. If you approximate yes, you do a more complex inquiry to grab details. If you approximate no, you tell the user no, don't know that face [answer, command, etc]. So this is ripe for approximate methods as you can tune to get very few false negatives (respond no when it's really yes), but allow a healthy dose of false positives.
  - shadowgovt 5y ago
    This reminds me of the mechanism of a bloom filter (https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter).

nynx 5y ago

Huh, that’s kinda fascinating. Maybe it’d be worth running ml on matrix multiplication that’s approximated by ml?

TrainedMonkey 5y ago
Ironic thing is large part of how ML works is via matrix multiplication.
- r00fus 5y ago
  That's not ironic, it could be revolutionary for this algorithm and ML in general.
- uluyol 5y ago
  Lots of things are like this. I program my network using a network. I run a server (BMC) on my server. I start my engine with an engine (https://en.m.wikipedia.org/wiki/Lockheed_SR-71_Blackbird https://en.m.wikipedia.org/wiki/Lockheed_SR-71_Blackbird).
- deleted 5y ago
  [deleted]
- noobermin 5y ago
  It important to remember dense matrix multiplication (doing it by hand) is a O(N^3) operation, this is about approximations to multiplication that beat that already harsh complexity. There is a whole field that develops approximations to matrix multiplication of large matrices, I'm assuming this article is about using ML to find good approximations. To the replies, the very act of evaluting a prediction from a NN is matrix multiplication (linear transform of a column vector is matrix multiplication). This doesn't replace matrix multiplication wholesale, lol. This is about multiplication in a specific case.
  - Nevermark 5y ago
    As long as their is enough consistency between approximating a multiply X*W and Z*Wt (Wt = W transpose), then it is possible it could be used in NN training. Y = X*W is the forward propagation. If Z is an error or derivative of error, Z*Wt is the back propagation. Its an interesting question as to how well that would work. Anything that speeds up matrix multiply in NN and deep learning in general would be a big deal.
  - 5y ago

random314 5y ago

Ha ha! What the hell! This is revolutionary if true!

antonzabirko 5y ago

Had this same exact thought as an undergrad like 3 years ago! I kinda gave up due to the massive barrier and difficult financial burdens faced by phd students. This feels nice to know i wasn't crazy.

jmount 5y ago
In my opinion, that is the thing with theoretical computer science. Many of the ideas are comprehendible. And if one has the opportunity to do the work: you may get the result.
- jvanderbot 5y ago
  Well, taken to the extreme, and from what I can tell, that's the truth for any field. If you roll everything, financial incentives, emotional readiness, support and preparation, etc, into 'opportunity' then yeah, I believe it.
- mhh__ 5y ago
  The biggest blocker for me is usually working out how I can implement a given idea without either writing a bunch of code (I'll get bored) or trying to verify if the paper even works for my use case without doing the aforementioned. One field I pay attention to with this problem seems to be abstract interpretation, with my background at least, the methods are very theoretically clean and impressive but actually implementing these as code and knowing how to write good implementations seems to be quite obtuse. I genuinely don't understand why we allow papers to be published on computer science, with graphs plotted of the supposed efficacy of research (i.e. not just a theoretical paper), with no code attached.
  - jijji 5y ago
    On page six of the paper: To assess MADDNESS’s effectiveness, we implemented both it and existing algorithms in C++ and Python. All of our code and raw numerical results are publicly available at https://smarturl.it/Maddness https://smarturl.it/Maddness. All experiments use a single thread on a Macbook Pro with a 2.6GHz Intel Core i7-4960HQ processor. edit: the url above redirects to: https://github.com/dblalock/bolt https://github.com/dblalock/bolt

alfor 5y ago

I wonder how our brain can train billion of neuron without matrix multiplication. What is the biological process that get a similar result?

jvanderbot 5y ago
Perhaps addition and multiplication are the tools we use to get a computer to appear to act like a biological system with all its chemical pathways and simultaneous stimuli. Lets take that one step further. Who taught orbiting bodies how to do differential equations?
- alfor 5y ago
  That’s a good one! I feel there is a difference as the cells are actively doing something, they are fighting entropy and create structure. In a similar way we are with our programs, of course what we do is a crude approximation of what neuron cells do in other ways. In other words, I wonder it there is a process that we could use to speed up neural training by looking at how the brain does it.
  - MauranKilom 5y ago
    I feel that the presented algorithm is actually somewhat close to what our brains do in similar tasks. As mentioned elsethread, the problem is essentially reduced to determining angles between two vectors (one of which is known ahead of time) in high dimensional space. This is done by projecting the other vector into different specially chosen subspaces and classifying it in those, then summing up the "scores" in each subspace. Given the similar task of determining the angle between two lines in 3D space, we tend to do something very similar (I feel): We look at the pair of lines (or vectors) from a few different perspectives (="subspaces") and get a feel for how well-aligned they are in each (="score"). We can then guess pretty well how large the angle between the two is. Of course, we frequently use other cues too (e.g. perspective and texture when talking about alignment of real-world 3D objects). And even when you are considering plain lines displayed on a screen (in which case these cues don't work), we tend to also take into account the relative movement of the objects as we (continuously) shift our perspective (e.g. drag-to-rotate a scene). Maybe the latter part could also be a hint towards further algorithmic ideas. Maybe somehow involving (signs of) derivatives (finite differences?) or similar could be a cheap way to improve accuracy. Just spitballing here though.

yangjunpro 5y ago

An interesting work, with some to-be-addressed questions: 1.The paper only covers the GEMM part with small-scale experiments(CIFAR-10/100), not covering convolution, not covering GEMM part in more popular network such as Transformer/BERT, etc. 2. It is still an approximating method, meaning potential accuracy loss. So I think this method is less attractive to training acceleration scenario, maybe potentially as a complementing methods for inference acceleration. 3. No results evaluated in GPU with TensorCore equipment. I am a little bit curious, since modern AI accelerator(including NV GPU) all incorporate TensorCore which by-design supports GEMM acceleration, what is the add-on value brought by the approximating method mentioned in this paper.

Ar-Curunir 5y ago
If it works better for inference, it could enable fast inference on devices which don't have good tensor cores/gpus
ffast-math 5y ago
Great observations. I see this paper as the first in a three-part series. The second part is specializing it for convolution (which has additional structure to exploit), and the third is hooking these approximate ops into deep neural nets the way people currently do with scalar quantization / pruning. I'm not optimistic about beating tensor cores when running on GPUs, at least until/unless we get similar hardware support.* Barring better hardware support, the killer app is probably CPU inference--once there are Conv implementations and the necessary GPU kernels to train the network. *Aside: this support would be pretty doable since the kernels look almost identical to GEMM kernels--you just need a multiplex-add rather than a multiply-add. On an x86 machine, all it would take is a vpshufb-add and a 4-bit unpack instruction.
criticaltinker 5y ago
> I think this method is less attractive to training acceleration scenario The proposed hash based encoding function is not differentiable, so it doesn’t appear this method can be used for training at all. I’m not aware of any hash functions that are analytically differentiable, so to support efficient back-propagation I suspect that some fundamental changes to this method would be necessary.

trilinearnz 5y ago

Clever and logical. It reminds me of when John Carmack used a precomputed table of Sine values for fast lookup in Quake, rather than running the actual function on the CPU.

richrichardsson 5y ago
I was using a precomputed table of sine values in 3D graphics way before Quake ever hit the scene, and I certainly didn't invent that idea either.
- trilinearnz 5y ago
  Ah that's useful to know that it was conventional up until then, thanks. It was my first exposure, personally :)
  - eesmith 5y ago
    Checking Google Scholar, I found this 1962 paper by King titled "Table Look-Up Procedures in Data Processing" - https://dl.acm.org/doi/abs/10.1145/800198.806120 https://dl.acm.org/doi/abs/10.1145/800198.806120 > It is not generally known that to provide seven- decimal accuracy of the sine function, allowing third-order interpolation, only 15 entries are required [*] ... The following commentary is interesting. > In spite of these developments in table construction, it turned out two decades ago that the technology was such that table look-up was too slow for arithmetic. The stored-program type of machine displaced this approach. By this method the value of a function, such as sin x, is computed afresh every time. One cannot but wonder how many times such a number has been re-computed in the last decade, and inquire whether technological developments may make tables efficient again. > Over the years the emphasis in machines has slowly changed from the central processing unit to memory. From the point of view of table look-up, the memory is the central feature of a machine. Indeed the central processing unit is unnecessary. The [*] is Krawitz. E., "Proc. Industrial Comp. Seminar," IBM, p. 66, 1950. I cannot find this publication with only a simple search. See also https://scholar.google.com/scholar?as_sdt=0%2C5&as_yhi=1990&q=sine+%22lookup+table%22 https://scholar.google.com/scholar?as_sdt=0%2C5&as_yhi=1990&... which finds titles like "A rapid lookup table method for trigonometric functions" (1982) at https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380121002 https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801210... .

leecarraher 5y ago

For some reason they run all their tests single threaded. Seems like parallelism is where all computing hardware is inevitably going. I also wish they had run time comparisons to more recent matrix sketching and multiplication method such as frequent directions, newer FJLT implementations, and RIP matrices based on hashing.

ffast-math 5y ago
We compared to several frequent directions variants, Fast Johnson–Lindenstrauss, some other hashing-based methods, and a bunch of other approximate matrix multiplication approaches. We had to omit some of them from the results section though because they were 10-100x worse than exact matrix products and they ruined the plots. More info in appendix E5. As far as single threaded, there's a simple answer and a subtle one. The simple answer is that we consider the core subroutine a single thread would run in a multithreaded context, not how to do the multithreading. These are basically orthogonal issues since matrix multiplication is embarrassingly parallel and our method would parallelize just like any other. More details in appendix E2. The subtler answer is that we could do even better in the multithreaded context if you could fuse the encoding step with whatever earlier code produces the larger matrix. This is a result of matrix products becoming memory-bandwidth-bound in the limit of sufficient cores, combined with our approach reducing the size of the matrix by a huge amount.

esjeon 5y ago

> MADDNESS I think this name really fits well to the concept. Replacing matrix-multiplication with some hash-lookups! (warning: an overly simplified statement) This is a really interesting application of PQ(product quantization), which itself also requires learning (usually K-means). Paper: https://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_with_quantization.pdf https://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_wi... Considering that ANN has survived through many approximations (e.g. lower precision, pruning), and that many ANN applications are anyway subjective (e.g. image processing, recommendation), I think this can be highly useful in many cases.

arthur2e5 5y ago
Certainly off topic, but gotta say I prefer “MADDLESS” over “MADDNESS” for being more… obvious. It still sounds close enough to me, but again I might be just letting my Southern-Chinese ear loose with the n/l confusions…

joe_the_user 5y ago

Shouldn't the solution to fast matrix multiplication be logarithms, similarly to fast scalar multiplication? https://en.wikipedia.org/wiki/Logarithm_of_a_matrix https://en.wikipedia.org/wiki/Logarithm_of_a_matrix

PythonNut 5y ago
Perhaps surprisingly, the matrix logarithm does not satisfy log(A) + log(B) = log(AB) in general (only when AB = BA) which is why you cannot use it to "multiply by adding".
- adgjlsfhk1 5y ago
  More importantly, matrix logarithms only exist for square matrices.
  - xyzzyz 5y ago
    That’s not that big of a problem, as you can easily reduce the problem of multiplication of rectangular matrices to multiplication of square ones.

cs702 5y ago

Every element of a matrix multiplication is a dot-product of two vectors. The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if < 0, the two vectors point in dissimilar directions; if = 0, the two vectors are orthogonal. It's not too hard to imagine that it might be possible to learn representative K-means clusters of training vectors and then, at run-time, find similar vectors using an efficient hashing scheme and do the equivalent of a table lookup to get the approximate dot-product similarity scores -- without having to perform any multiplications. This isn't quite correct (I'm oversimplifying and ignoring many important details), but I think it's a helpful mental image. Very clever stuff.

xyzzyz 5y ago
The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if < 0, the two vectors point in dissimilar directions; if = 0, the two vectors are orthogonal. To make it more explicit, dot product of two vectors is just cosine of the angle between them, multiplied by their lengths.
- kazinator 5y ago
  The angle and cosine start to lose their geometric intuition when we go beyond 3D. The concept of correlation has no issue with additional components. The concept of similarity of two 17-element vectors is clear. In fact correlation intuitively scales to "infinite component vectors": the dot product becomes multiplying two functions together and then taking an integral. The Fourier transform of a periodic signal is based in the concept of how similar the signal is to a certain basis of sine/cosine quadratures spaced along a frequency spectrum. This is like a projection of a vector into a space; only the vector has an infinite number of components since it is an interval of a smooth function.
  - Y_Y 5y ago
    This idea generalises to the concept of https://en.wikipedia.org/wiki/Inner_product_space https://en.wikipedia.org/wiki/Inner_product_space and a the equivalent of a change-of-basis.

infogulch 5y ago

I wonder how much alternative number representations have been studied for use in matrices. Like, storing the log of values instead so that multiplication can be done by just adding. Or something like Zech's logarithm. Or even, take the log of whole matrices (which is a thing apparently [0]), then adding them to compute their multiplication. I wonder if the logarithm of a matrix can be computed using ML. [0]: https://en.wikipedia.org/wiki/Logarithm_of_a_matrix https://en.wikipedia.org/wiki/Logarithm_of_a_matrix

thwoeri2324 5y ago
Quick note: the exp does not work the way it does with scalars. https://en.wikipedia.org/wiki/Matrix_exponential#Elementary_properties https://en.wikipedia.org/wiki/Matrix_exponential#Elementary_...
ffast-math 5y ago
There's been some work on doing adds instead of multiplies (e.g., https://arxiv.org/abs/2012.03458 https://arxiv.org/abs/2012.03458). And I think float8 will roughly be doing this under the hood. Personally, I'm not sure whether this is the path to go down or not. Doing everything in log space could help from a hardware perspective, since multiply-adds are much more complex than adds. But it 1) doesn't reduce the number of operations being performed, 2) might increase the necessary bit width for a given level of fidelity (depending on your input distribution and other factors), and 3) might make accumulate operations expensive, since these aren't cleanly expressed in the log domain.
rocqua 5y ago
storing log values helps with the multiply part of multiply and add. But it seems like it would make the add part of multiply and add quite a bit more difficult.
michelpp 5y ago
There is a logarithmic semiring: https://en.wikipedia.org/wiki/Log_semiring https://en.wikipedia.org/wiki/Log_semiring which can be used to multiply two sparse matrices with the GraphBLAS. here is an example in Python: https://github.com/Graphegon/pygraphblas/blob/main/demo/Log-Semiring.ipynb https://github.com/Graphegon/pygraphblas/blob/main/demo/Log-...

ffast-math 5y ago

Primary author here. Happy to answer questions! Also, feel free to email me at the address in the paper if you're interested in talking about it in more detail. E.g., I've already heard from some hardware folks looking at expanding on this work.

FabHK 5y ago
So, do I understand this correctly: 0. The problem you're really looking at is quickly computing a'B for many different vectors a (of length D) which are conceptually random. 1. To do that, you approximate AB, where A is very long and thin (NxD), and B (DxM). (Note: this problem has complexity O(NDM) naively, or, if N=D=M, O(N^3), and there are smarter algorithms that reduce the exponent 3 down to 2.8 (Strassen) or even further down, though those are not practical from what I gather. Oh, and note that at minimum, you're looking at time (N+M)D, because you need to look at every element, unless you approximate). 2. You approximate AB by f(g(A),h(B)), such that the error (in "relative Frobenius norm", ie norm of the error divided by norm of the actual product) is "small" with "high probability". 3. You're given B and a "typical" A^~ (ie training data), and then have two steps: 3.1. Do some training mumbo jumbo (fast?), and 3.2. now finally you can quickly compute the approximate AB (or a'B) for "new" A (or a'), presumably fast? Quite cool that there are new techniques (and apparently fast, the article claims 100x faster than exact, and 10x faster than existing approximations) for such a classic problem! But, if I understand correctly, it could happen with a certain probability that the actual error is quite high? Maybe if your a' is untypical? ETA: From what I understand, in many ML applications people use 32bit or even 16bit floats, so high accuracy is not as important as speed anyway?
- ffast-math 5y ago
  Yes, basically correct. A couple notes/clarifications for other readers: - The rows a of A are "random," but in the sense of being drawn from some distribution for which we have a training set--not in the sense of, e.g., "assume everything is gaussian" or some other idealized case. - The training takes a few seconds to maybe a couple minutes, depending on your training set size. But it does have to be done ahead of time--you can't train after receiving the matrices and still get a speedup. Unless maybe the matrices are unrealistically large. - The error in the approximation is provably not much larger than the error on the training set with high probability (under standard ML assumptions--finite variance, training and test distributions match), but there's no hard limit on it in general. If you know the range of values in your individual vectors, you could obtain a hard limit, although it would be much looser than what you see in practice. - Correct that many ML applications tolerate large losses in precision. But caveat is that we won't get the right answer to a full 16 bits in each element (this would be ~99.999% accuracy), but instead more like 90-99.9%, depending on the speed-quality tradeoff chosen. So we can't claim it will be sufficiently accurate in all cases

kazinator 5y ago

If machine learning depends on matrix multiplications, but you fib them using machine learning ... do you see the problem?

qsort 5y ago
If a C++ compiler depends on a C++ compiler to be compiled itself... do you see the problem? I have only superficially looked at the paper, but it's pretty clear they are using an offline lookup table. There are no such problems involved.
- kazinator 5y ago
  Yes, I do; your bootstrapping is dependent on a binary C++ compiler, which could be hiding something that isn't in the source code, but which propagates to newly bootstrapped compiler binaries which again pass it on to the next round of bootstrapping, ad infinitum. Basically, we can't be sure that you really have a C++ compiler. The source code can be verified to be a C++ compiler, but the binaries deviate in some way, possibly malicious.
  - robertlagrant 5y ago
    Sure, but you seem to have gone off on a wild tangent. How does that relate to matrix multiplication?
    - deleted 5y ago
      [deleted]
    - kazinator 5y ago
      By "you", you mean user qsort, right?
    - setr 5y ago
      I believe he’s getting at the idea of nested levels of corruption, with no visibility into where that corruption happens (because recompilation of the compiler/ML produces a fresh inscrutable binary). I suppose the better term in this context is error propogation

TaupeRanger 5y ago

Method 1: computer, use MUL to multiply X and Y. Method 2: computer, remember this number. When I give you X and Y, tell me what that number was. This requires no multiplication! Let us tell SCIENCE about our discovery!

rm445 5y ago
How about using a look-up table for small numbers (say up to 12x12), left shifts for powers of ten, and decomposing larger multiplications into summation of those operations?
MauranKilom 5y ago
Or, oversimplified in a different way: Method 1: Computer, tell me the angle between these two 3D lines! Method 2: Computer, look at this (second) 3D line from a few different perspectives (determined by the first line) and then tell me how often it looks more vertical than horizontal. That'll give me a good enough idea of the angle between the two.
ffast-math 5y ago
So this misses a few aspects of why the method works: - You can't actually get a speedup from the proposed approach. You'd need a lookup table of size b^2 to multiply two b-bit numbers, which will be much slower than just doing the multiplication. - Most of what we do is perform fewer operations. We're actually slower per op than multiply-adds because those are supported better in hardware. We just compress the matrices by so much that it's worth it. Relatedly, for sufficiently few codebooks, we're actually sublinear in the input size--i.e., we don't even read it all. - We have some lightweight machine learning in there to make the sublinearity and other approximations not suck. Getting the ML fast enough to beat a BLAS GEMM is far from trivial.

bawana 5y ago

Lots of discussion here about higher dimensional matrices. The argument is that the dot product is an operation on two arguments, therefore any multidimensional matrix multiplication can be broken down into multiple two dimensional operations. The image offerred is that two vectors define a plane so any two dimensional operation is valid. But how about curved space? Suppose I have two vectorsin curved space-they look like two droopy arrows. How does one calculate this dot product? I guess the the local curvature has to be taken into account. In spherically shaped space, this is a constant, but what about irregularly bent space-like that near an amorphous blob of dark matter? Suppose you are trying to calculate electrostatic potentials or do anything with Maxwell's equations? Currently, we define the curvature of space with gravity or the deflection of light past massive objects. Is there a way to measure the curvature of space locally? Can the curvature of space alter the piezoelectric potential generated by a crystal for example and allow its measurement- I am thinking that a miniscule deformation on a large macroscopic object is multiplied many fold on a property that is distributed over the atomic level and happening in parallel on all the atoms of a crystal.

codethief 5y ago
> But how about curved space? Suppose I have two vectorsin curved space-they look like two droopy arrows. No, they don't. In math, curved spaces are modeled through so-called manifolds which locally look like ℝ^n. In particular, at any point p of the manifold there's a tangent space, i.e. a linear space (higher-dimensional plane) tangent to the manifold at p. Vectors at p are just vectors in that linear space. So they are "straight" not "droopy". On the tangent space of each point p you can now define an inner product g(p). The resulting family of inner products g is called a (Riemannian) metric on the manifold[0] and describes how lengths (of vectors) and angles (between vectors) can be measured at each point. > Currently, we define the curvature of space with gravity or the deflection of light past massive objects. Is there a way to measure the curvature of space locally? Yes, there is. In fact, the curvature[1] of a (Riemannian) manifold is a purely local quantity – it's basically the second derivative of the metric g, so it describes how the notion of length changes (more precisely: how the change in length changes) as you go from a point p to neighboring points. There are other ways to express what curvature is, e.g. by locally parallelly transporting[2] a vector along a closed curve (and making that curve smaller and smaller) which basically measures how the notion of straight lines changes locally. (Though, since a line being "straight" means "locally length minimizing" this brings us back to the notion of length and, thus, the metric.) Alternatively, if the manifold has dimension 2, there's a particularly simple way of looking at and interpreting curvature, see [3]. In any case, curvature being used to model gravity is entirely separate from that idea. [0]: Provided this inner product "varies smoothly" as you move from p to a neighboring point q. [1]: https://en.wikipedia.org/wiki/Riemann_curvature_tensor https://en.wikipedia.org/wiki/Riemann_curvature_tensor [2]: https://en.wikipedia.org/wiki/Parallel_transport https://en.wikipedia.org/wiki/Parallel_transport [3]: https://en.wikipedia.org/wiki/Gaussian_curvature https://en.wikipedia.org/wiki/Gaussian_curvature

sriram_malhar 5y ago

Can someone help me understand how approximate it is? what are te error bounds?

ffast-math 5y ago
We have a generalization guarantee in Section 4.5. It's not especially tight though; in practice, the errors from different codebooks tend to be mostly independent, and you get nice Gaussian-like concentration. I would look at the empirical results in Section 5 to get a better feel for how it performs in practice.