1
$\begingroup$

I have a collection of high dimensional vectors such as $\vec{a}_{i} \in \mathbb{R}^{n}$ where $n$ is 3000. What I want to do is to embed these vectors into a space such as $\vec{b}_{i} \in [0, 255]^{n}$ where $n$ in this case is now 32. I want to embed it (using any hash trick or something like that) in a way that will preserve similarity. For example, if I have the following two vectors that are very similar to each other:

$\vec{a}_{1} = (1.2, 0.1, 0.4, 12.8, \ldots)$

$\vec{a}_{2} = (1.1, 0.1, 0.4, 12.5, \ldots)$

I want these two vectors to end in the same "bucket" of this other space where the vectors belongs to $[0, 255]^{32}$. Note that I don't want to use it for search, I want similar vectors to be in the same "bucket" in this other low dimensional space. I was trying to use LSH but I wasn't able to figure out a way to solve this.

Improve this question
$\endgroup$
2
  • $\begingroup$ 1. LSH is one reasonable approach. Can you edit your question to elaborate on where you got stuck, when you tried to apply LSH? Please provide more detail: what LSH schemes did you consider? How did you consider using them? What resources have you read? 2. How do you propose to measure similarity? Can you quantify how similar vectors need to be before they need to be in the same bucket? $\endgroup$
    – D.W. ♦
    Commented Jul 25, 2016 at 1:05
  • $\begingroup$ I answered your question regarding the LSH in the answer below, let's concentrate the comments there. $\endgroup$
    – Tarantula
    Commented Jul 25, 2016 at 13:04

1 Answer 1

Reset to default
4
$\begingroup$

Locality-sensitive hashing is one reasonable approach for this. I suggest reading standard resources on locality-sensitive hashing (LSH). In your case, a locality-sensitive hash is a hash function that maps $h:\mathbb{R}^n \to S$ where if $x,y \in \mathbb{R}^n$ are close enough, then we'll have $h(x)=h(y)$ with high probability.

To get started, tead https://en.wikipedia.org/wiki/Locality-sensitive_hashing and https://cstheory.stackexchange.com/q/10053/5038.

Do understand that LSH is fundamentally probabilistic: if $x,y$ are similar, they will have a high probability of being mapped to the same bucket, but this cannot be guaranteed.

Alternatively, you might be interested in metric space embeddings. An embedding $E:\mathbb{R}^n \to \mathbb{R}^d$ has the property that if $x,y$ are close (i.e., $\|x-y\|_2$ is not too large), then $E(x),E(y)$ will be close (i.e., $\|E(x)-E(y)\|_2$ will be not too large). This could then provide a solution to your scheme, if you are satisfied that similar inputs map to buckets that are "nearby" but not necessarily identical.

For more on metric space embeddings, you can start with https://cs.stackexchange.com/a/27923/755, https://cstheory.stackexchange.com/a/6818/5038, https://cstheory.stackexchange.com/q/21487/5038, https://cstheory.stackexchange.com/questions/tagged/embeddings.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So, I've tried to use LSH but the problem of LSH is that it requires an exact comparison for disambiguation due to the fact that it uses random hyperplanes to separate the space. What I mean is that LSH will put similar vectors in different buckets and different vectors in the same bucket. What I see that it is really intended more for a search perspective. But I don't have means for searching and exact comparison of my vectors, I want them to be close in this embedded space instead of requiring a exact search between the items in the same bucket. $\endgroup$
    – Tarantula
    Commented Jul 25, 2016 at 13:03
  • $\begingroup$ Note that I don't want the vectors close (using a L2 for instance) to be close, I want vectors close to be in the same bucket. For instance, I need similar vectors to have the same hash. $\endgroup$
    – Tarantula
    Commented Jul 25, 2016 at 13:43
  • $\begingroup$ @Tarantula, I can't tell what you're looking for, and I can't understand your comments. You say you don't like LSH because it puts similar vectors into the same bucket, then later you say need similar vectors to be in the same bucket. Well, that's exactly what LSH does. I suggest you try to get clearer on what exactly your requirements are. Depending on what your requirements actually are, either LSH, low-distortion embeddings, or a combination of the two is likely to meet your needs. $\endgroup$
    – D.W. ♦
    Commented Jul 25, 2016 at 17:01
  • $\begingroup$ Sorry D.W. I wasn't really clear. What I need to do is to have: similar vectors (similar in L2) to have the same hash. I don't think LSH is a good fit here because it will put dissimilar vectors in the same bucket right ? $\endgroup$
    – Tarantula
    Commented Jul 25, 2016 at 19:01
  • 1
    $\begingroup$ @Tarantula, there is no scheme that ensures that similar vectors are always in the same bucket (have the same hash) and that dissimilar vectors are never in the same bucket (have the same hash). If you want perfection, you won't find it. What LSH achieves is that similar vectors will usually be in the same bucket (have the same hash), and dissimilar vectors will almost never be in the same bucket (have the same hash). That's about the most one can hope for. That's what I mean when I said LSH is probabilistic. Putting specific numbers on this requires choosing parameters. $\endgroup$
    – D.W. ♦
    Commented Jul 25, 2016 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.