5 ms·

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

by 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.
  - tpoacher 5y ago
    > 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).
    - Certhas 5y ago
      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.
      - bollu 5y ago
        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.
      - atq2119 5y ago
        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.
        10000truths 5y ago
- adwn 5y ago
  > 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.
  - Nevermark 5y ago
    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.
    - adwn 5y ago
      > 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. Okay, but now you've got a plane in n-dimensional space. How do you define/calculate the angle between the two vectors without falling back on the dot product? You could say: The angle between the two vectors A and B is defined as the smallest rotation around their common normal vector so that the rotated first vector points in the same direction as the second vector. But what is the normal vector? It's a third vector C which is 90° to each of A and B. Now your definition is cyclic. Okay, then: C is a non-zero vector so that dot(A,C)=0 and dot(B,C)=0. Now you're back to using dot-products for defining angles in higher-dimensional space.
      - Nevermark 5y ago
        The normal vector is the cross product of the two vectors. u = [u1 u2 u3] v = [v1 v2 v3] in dimensions i, j, k u x v = determinate of this matrix: = | i j k| |u1 u2 u3| |v1 v2 v3| = (u2v3-v2y3)i - (u1v3 - v1y3)j + (u1v2 - v2u2)k
davesque 5y ago
Thanks for your succinct summary of the result. Just the other day, I was thinking about how useful clusterings seem in summarizing the landscape of a set of points in any number of dimensions. This work seems to be built on top of the same insight as well as the innovation of using hashing to speed up the similarity checks.
0-_-0 5y ago
>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?
amelius 5y ago
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?
bick_nyers 5y ago
I spent some time thinking about this in college, the problem you run into is the sheer size of the lookup table, you will get higher complexity in the ability to search this table (or prep your input matrix to be searchable). I'm going to try and remember the calculations I performed, but I remember just looking at permutations/combinations of 8bit integer matrices, 2x2 seems reasonable but 3x3 or 4x4 gets unreasonable from an algorithmic/memory perspective very quickly
cs702 5y ago
Please see this thread started by one of the authors, which I would rather see at the top of the page, above my comment: https://news.ycombinator.com/item?id=28376439 https://news.ycombinator.com/item?id=28376439

by cs702 5y ago

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.
- tpoacher 5y ago
  > 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).
  - Certhas 5y ago
    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.
    - bollu 5y ago
      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.
    - atq2119 5y ago
      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.
      - 10000truths 5y ago
adwn 5y ago
> 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.
- Nevermark 5y ago
  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.
  - adwn 5y ago
    > 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. Okay, but now you've got a plane in n-dimensional space. How do you define/calculate the angle between the two vectors without falling back on the dot product? You could say: The angle between the two vectors A and B is defined as the smallest rotation around their common normal vector so that the rotated first vector points in the same direction as the second vector. But what is the normal vector? It's a third vector C which is 90° to each of A and B. Now your definition is cyclic. Okay, then: C is a non-zero vector so that dot(A,C)=0 and dot(B,C)=0. Now you're back to using dot-products for defining angles in higher-dimensional space.
    - Nevermark 5y ago
      The normal vector is the cross product of the two vectors. u = [u1 u2 u3] v = [v1 v2 v3] in dimensions i, j, k u x v = determinate of this matrix: = | i j k| |u1 u2 u3| |v1 v2 v3| = (u2v3-v2y3)i - (u1v3 - v1y3)j + (u1v2 - v2u2)k

davesque 5y ago

Thanks for your succinct summary of the result. Just the other day, I was thinking about how useful clusterings seem in summarizing the landscape of a set of points in any number of dimensions. This work seems to be built on top of the same insight as well as the innovation of using hashing to speed up the similarity checks.

0-_-0 5y ago

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

amelius 5y ago

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?

bick_nyers 5y ago

I spent some time thinking about this in college, the problem you run into is the sheer size of the lookup table, you will get higher complexity in the ability to search this table (or prep your input matrix to be searchable). I'm going to try and remember the calculations I performed, but I remember just looking at permutations/combinations of 8bit integer matrices, 2x2 seems reasonable but 3x3 or 4x4 gets unreasonable from an algorithmic/memory perspective very quickly

cs702 5y ago

Please see this thread started by one of the authors, which I would rather see at the top of the page, above my comment: https://news.ycombinator.com/item?id=28376439 https://news.ycombinator.com/item?id=28376439