Multiplying Matrices Without Multiplying • Hacker News Board

Re: Multiplying Matrices Without Multiplying

#51

Post by kazinator » Wed, Sep 01, 2021, 6:56 AM UTC

xyzzyz wrote: post #37

cs702 wrote: post #31

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 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,…

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 To make it more explicit, dot product of two vectors is just cosine of the angle between them, multiplied by their lengths.

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.

Re: Multiplying Matrices Without Multiplying

#52

Post by adwn » Wed, Sep 01, 2021, 7:04 AM UTC

xyzzyz wrote: post #37

cs702 wrote: post #31

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 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,…

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 To make it more explicit, dot product of two vectors is just cosine of the angle between them, multiplied by their lengths.

> dot product of two vectors is just cosine of the angle between them, multiplied by their lengths

How do you define the "angle" between two n-dimensional vectors? Most likely using the dot-product and the arccos. "cos(angle) times lengths" might give a good intuition for 2D or 3D space, but it doesn't help in higher-dimensional vectors.

Re: Multiplying Matrices Without Multiplying

#53

Post by qsort » Wed, Sep 01, 2021, 7:17 AM UTC

kazinator wrote: post #50

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

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.

Re: Multiplying Matrices Without Multiplying

#54

Post by Y_Y » Wed, Sep 01, 2021, 7:30 AM UTC

kazinator wrote: post #51

xyzzyz wrote: post #37

Earlier quoted context omitted.

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 To make it more explicit, dot product of two vectors is just cosine of the angle between them, multiplied by their lengths.

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 b…

This idea generalises to the concept of https://en.wikipedia.org/wiki/Inner_product_space and a the equivalent of a change-of-basis.

Re: Multiplying Matrices Without Multiplying

#55

Post by tpoacher » Wed, Sep 01, 2021, 7:31 AM UTC

kazinator wrote: post #51

xyzzyz wrote: post #37

Earlier quoted context omitted.

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 To make it more explicit, dot product of two vectors is just cosine of the angle between them, multiplied by their lengths.

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 b…

> The angle and cosine start to lose their geometric intuition when we go beyond 3D

... they do?

"Geometry" in general loses intuition beyond 3D, but apart from that, angles between two vectors are probably the one thing that still remains intuitive in higher dimensions (since the two vectors can always be reduced to their common plane).

Re: Multiplying Matrices Without Multiplying

#56

Post by Nevermark » Wed, Sep 01, 2021, 7:43 AM UTC

adwn wrote: post #52

xyzzyz wrote: post #37

Earlier quoted context omitted.

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 To make it more explicit, dot product of two vectors is just cosine of the angle between them, multiplied by their lengths.

> dot product of two vectors is just cosine of the angle between them, multiplied by their lengths How do you define the "angle" between two n-dimensional vectors? Most likely using the dot-product and the arccos. "cos(angle) times lengths" might give a good intuition for 2D or 3D space, but it doesn't help in higher-dimensional vectors.

It generalizes perfectly. The angle between two lines in any dimensions is the same concept.

Two (non-collinear) lines share a plane. The angle on that plane is just the ordinary angle, no matter how many dimensions the two lines are embedded in.

In the case they are collinear, the angle between them is zero on any plane that intersects them. So that corner case works too, regardless of numbers of dimensions.

Re: Multiplying Matrices Without Multiplying

#57

Post by Certhas » Wed, Sep 01, 2021, 7:46 AM UTC

tpoacher wrote: post #55

kazinator wrote: post #51

Earlier quoted context omitted.

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 b…

> The angle and cosine start to lose their geometric intuition when we go beyond 3D ... they do? "Geometry" in general loses intuition beyond 3D, but apart from that, angles between two vectors are probably the one thing that still remains intuitive in higher dimensions (since the two vectors can always be reduced to their common plane).

Even angles behave very counter-intuitively in high dimensions. E.g. in high dimensional spaces uniformaly randomly chosen vectors always have the same inner product. Why? Sum x_i y_i is a sum of iid random variables, so the variance goes to zero by the central limit theorem.

Re: Multiplying Matrices Without Multiplying

#58

Post by kazinator » Wed, Sep 01, 2021, 7:51 AM UTC

qsort wrote: post #53

kazinator wrote: post #50

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

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.

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.

Re: Multiplying Matrices Without Multiplying

#59

Post by Nevermark » Wed, Sep 01, 2021, 7:54 AM UTC

noobermin wrote: post #14

TrainedMonkey wrote: post #4

Earlier quoted context omitted.

Ironic thing is large part of how ML works is via matrix multiplication.

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…

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.

Re: Multiplying Matrices Without Multiplying

#60

Post by richrichardsson » Wed, Sep 01, 2021, 8:29 AM UTC

trilinearnz wrote: post #19

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.

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.