Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Multiplying Matrices Without Multiplying

arxiv.org

Post reply on HN
Print view View original

61–70 of 124 posts

Re: Multiplying Matrices Without Multiplying

#61

Post by 0-_-0 »

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

>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.

Isn't that basically the same as replacing your hardware multiplication operations with a hardware lookup table?

Re: Multiplying Matrices Without Multiplying

#62

Post by robertlagrant »

kazinator wrote: post #58
qsort wrote: post #53

Earlier quoted context omitted.

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

Sure, but you seem to have gone off on a wild tangent. How does that relate to matrix multiplication?

Re: Multiplying Matrices Without Multiplying

#63

Post by tgv »

alfor wrote: post #11

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

The "original" and easy to grasp idea behind neural learning is reinforcement: every time a good result is obtained, the connections that contributed get strengthened (reinforced). Bad results lead to weakening. Back-prop is specific implementation, and it is usually expressed in terms of matrix operations, but you can describe it without as well at the single connection level. Implementing that isn't efficient, though, hence matrix operations.

Re: Multiplying Matrices Without Multiplying

#64

Post by BongoMcCat »

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.

take the first line/vector, then just call that line/vector "first-new-dimension".

Then take the second line/vector, and decide that this vector can be written as a 2-dimensional vector made out of "first-new-dimension" and "second-new-dimension", now you just have to figure out what "second-new-dimension" is.

A simple trick would be to measure the length of the line, and then add/remove a multiple of the first dimension until the length of the line becomes as short as possible, this new line is your "second-new-dimension".

Now, even if you are working with a 10-dimensional space, you have two lines that only exist in the first two (new) dimensions, so, you can treat them as two-dimensional objects and find an angle using your old 2-dimensional methods.

Re: Multiplying Matrices Without Multiplying

#65

Post by amelius »

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

One question is: how does it scale? E.g. how does the time/space complexity increase in the big-O sense with increasing dimension N?

Re: Multiplying Matrices Without Multiplying

#66

Post by bollu »

Certhas wrote: post #57
tpoacher wrote: post #55

Earlier quoted context omitted.

> 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.

I would say that this is intuitive. For any direction you pick, there are (n-1) orthogonal directions in nD space. It's only natural that the expected inner product drops to zero.

Re: Multiplying Matrices Without Multiplying

#67

Post by rocqua »

infogulch wrote: post #36

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:/…

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.

Re: Multiplying Matrices Without Multiplying

#68

Post by atq2119 »

Certhas wrote: post #57
tpoacher wrote: post #55

Earlier quoted context omitted.

> 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.

The variance goes to 0 only if you normalize, which is to say that two random high-dimensional vectors are very likely to be close to orthogonal (under mild assumptions on their distribution).

I agree that that's one of those important but initially unintuitive facts about high dimensions. Just like almost all of the volume of a reasonably round convey body is near its surface. But it also doesn't really contradict the GP comment.

Re: Multiplying Matrices Without Multiplying

#69

Post by trilinearnz »

richrichardsson wrote: post #60
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.

Ah that's useful to know that it was conventional up until then, thanks. It was my first exposure, personally :)

Re: Multiplying Matrices Without Multiplying

#70

Post by 10000truths »

atq2119 wrote: post #68
Certhas wrote: post #57

Earlier quoted context omitted.

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.

The variance goes to 0 only if you normalize, which is to say that two random high-dimensional vectors are very likely to be close to orthogonal (under mild assumptions on their distribution). I agree that that's one of those important but initially unintuitive facts about high dimensions. Just like almost all of the volume of a reasonably round convey body is near its surface. But it also doesn't really contradict t…

> Just like almost all of the volume of a reasonably round convey body is near its surface.

I’d say that’s pretty intuitive for anyone who can see a pattern in surface area to volume ratios.

1D ball: 2 / (2 * r) = 1/r

2D ball: (2 * pi * r) / (pi * r^2) = 2/r

3D ball: (4 * pi * r^2) / (4/3 * pi * r^3) = 3/r

nD ball: ... = n/r

Post reply on HN