4 ms·

Slightly offtopic, but I'm currently working on a video similarity search tool, and the vectors I'm using are pretty big (the size of a vector is over 2M). This

by nl 3y ago

Slightly offtopic, but I'm currently working on a video similarity search tool, and the vectors I'm using are pretty big (the size of a vector is over 2M). This is quite different to the normal vector size of maybe 10k max. Currently I'm using Annoy (mostly because it's what I've used before) but I am a bit worried that this is well outside what it has been designed for. Has anyone got specific advice for things I should try? I've used FAISS previously but it seems to have the same design space.

ashvardanian 3y ago
Yes, Annoy is probably not the best tool for the task. Are the vectors sparse?
- nl 3y ago
  > Are the vectors sparse? No they aren't.
shri_krishna 3y ago
> the size of a vector is over 2M Do you mean the dimension of the vector or the number of vectors?
- nl 3y ago
  The dimension of the vector. It's the hidden state from a video vision transformer.
  - ashvardanian 3y ago
    Ouch! That’s fat! Which model is that? We have built a few video-search system by now, using USearch and UForm for embedding. They are only 256 dims and you can concatenate a few from different parts of the video. Any chance it would help? https://github.com/unum-cloud/uform https://github.com/unum-cloud/uform
    - nl 3y ago
      It's https://huggingface.co/docs/transformers/main/model_doc/vivit https://huggingface.co/docs/transformers/main/model_doc/vivi... I'm doing the most naive implementation possible at the moment though so it's likely I could improve it. > UForm Looks interesting. I'll have a play, thanks. I'm surprised there aren't more options in this space actually
  - shri_krishna 3y ago
    Damn! 2M dimension dense vector is huge. Maybe you need to do some dimensionality reduction before attempting ANN. Something like PCA should help.
    - henrydark 3y ago
      How do you do pca on dimension 2M?
  - woadwarrior01 3y ago
    Have you considered training a shallow MLP autoencoder, perhaps with tied weights between the encoder and the decoder to reduce the dimensionality of the embeddings? Another (IMO, better) approach I can think of off the top of my head, would be to use a semi-supervised contrastive learning approach, with labelled similar and dissimilar video pairs, like in this notebook[1] from OpenAI. [1]: https://github.com/openai/openai-cookbook/blob/main/examples/Customizing_embeddings.ipynb https://github.com/openai/openai-cookbook/blob/main/examples...
    - nl 3y ago
      I originally started doing a triplet loss for video similarity similar to https://keras.io/examples/vision/siamese_network/ https://keras.io/examples/vision/siamese_network/ except for video instead of images. But I'm sort of hoping to avoid training a model.
nl 3y ago
Reading the docs of this library it seems like I should try it, especially since it has built-in downcasting to save space on the indexes (which is rapidly turning into a big problem for me!)
jhj 3y ago
This seems impractical, it's likely that the data is highly redundant and you'd probably do just as well by just picking a random projection to a much smaller subspace (or simply just perform a random subsampling of the dimensions, or sum dimensions together, stuff like that) rather than spending the compute to learn a projection via SVD or some such. Hubness might be a significant problem as well and lead to search results not matching your intent. Also, numeric problems (e.g., if you were accumulating distance in floating point) would become an issue as well with millions of dimensions unless the way that distances are summed get special treatment (like Kahan summation, or reduction trees to sum values of roughly equal expected magnitude, etc) too; x += dist[i] won't cut it. Any kind of acceleration technique to limit the search to a subset of the database (such as cell-probe-ish methods like LSH or IVF, or graph-based methods, etc) would take a ton of time to compute. Simply storing all the data you need for search, even brute force, would rapidly explode, not to mention the compute required. Most cases with such large vectors I've seen begin with highly sparse vectors. Certainly Faiss (I wrote the GPU side of Faiss), Annoy, or most any similarity search libraries out there are geared to dense vectors in the 20 - 2000ish dimension range (beyond the number of dimensions where exact methods such as BSP or k-D trees work well as in "high" dimensions your nearest neighbor is highly likely to lie on either side of a dividing hyperplane, but below cases where simply storing the data uncompressed / unquantized / etc is hard and the amount of compute is prohibitive as well). How big is the data set (number of vectors) that you are searching among, and are you performing single queries or batch queries?
- nl 3y ago
  Thanks for the response. You are probably right in the general case. I'm only searching hundreds of vectors, and it seems to be working surprisingly well (astonishingly well really!) - but I've only spent a few hours working on this and are far from having a proper measure of how good it is. I'll try the smaller subspace ideas - seems like it'd be easy to try and could work. > How big is the data set (number of vectors) that you are searching among The biggest dataset I've tried so far is 400 (it is searching similar scenes in a sports broadcast) > and are you performing single queries or batch queries? single - choose a scene and it finds similar ones. Thanks for Faiss BTW. I love love love it - long time member of the FB group you have. I think I switched to Annoy because I had a packaging issue some time back or something.
janalsncm 3y ago
Train an autoencoder to reduce your vector dimensions down to something more workable. It’s unlikely you’ll be able to search against such enormous vectors in a reasonable amount of time anyways. Another option is to shard your vectors into N pieces, where N*k is the length of your vector. Since cosine similarity doesn’t care about order, it will be fine. The only requirement is that the k-th vector can only be compared with other k-th vectors for similarity. The benefit of this approach is that it can be parallelized easily.
- nl 3y ago
  The autoencoder was what I was thinking too. I was hoping to avoid training anything though! Search speed is good (although the datasize is pretty small - hundreds of vectors). So the sharding idea I'd: slice up the vector compare each sub vector with the corresponding sub vector ones from other vectors getting the similarities. sum the similarities choose the maximum Is this the general idea? Is there an implementation of this you've seen?
  - janalsncm 3y ago
    If you’re looking for something out of the box, I can’t help you unfortunately. I do ML at a company where we have our own in-house tooling. I agree with your algorithm, it is equivalent to cosine similarity. But you might also consider whether you need all the shards at all. Maybe you can get away with a half or even a tenth of them. If you have some metric like ndcg you can measure the drop in performance and consider the trade off.

by nl 3y ago

ashvardanian 3y ago

Yes, Annoy is probably not the best tool for the task. Are the vectors sparse?

nl 3y ago
> Are the vectors sparse? No they aren't.

shri_krishna 3y ago

> the size of a vector is over 2M Do you mean the dimension of the vector or the number of vectors?

nl 3y ago
The dimension of the vector. It's the hidden state from a video vision transformer.
- ashvardanian 3y ago
  Ouch! That’s fat! Which model is that? We have built a few video-search system by now, using USearch and UForm for embedding. They are only 256 dims and you can concatenate a few from different parts of the video. Any chance it would help? https://github.com/unum-cloud/uform https://github.com/unum-cloud/uform
  - nl 3y ago
    It's https://huggingface.co/docs/transformers/main/model_doc/vivit https://huggingface.co/docs/transformers/main/model_doc/vivi... I'm doing the most naive implementation possible at the moment though so it's likely I could improve it. > UForm Looks interesting. I'll have a play, thanks. I'm surprised there aren't more options in this space actually
- shri_krishna 3y ago
  Damn! 2M dimension dense vector is huge. Maybe you need to do some dimensionality reduction before attempting ANN. Something like PCA should help.
  - henrydark 3y ago
    How do you do pca on dimension 2M?
- woadwarrior01 3y ago
  Have you considered training a shallow MLP autoencoder, perhaps with tied weights between the encoder and the decoder to reduce the dimensionality of the embeddings? Another (IMO, better) approach I can think of off the top of my head, would be to use a semi-supervised contrastive learning approach, with labelled similar and dissimilar video pairs, like in this notebook[1] from OpenAI. [1]: https://github.com/openai/openai-cookbook/blob/main/examples/Customizing_embeddings.ipynb https://github.com/openai/openai-cookbook/blob/main/examples...
  - nl 3y ago
    I originally started doing a triplet loss for video similarity similar to https://keras.io/examples/vision/siamese_network/ https://keras.io/examples/vision/siamese_network/ except for video instead of images. But I'm sort of hoping to avoid training a model.

nl 3y ago

Reading the docs of this library it seems like I should try it, especially since it has built-in downcasting to save space on the indexes (which is rapidly turning into a big problem for me!)

jhj 3y ago

This seems impractical, it's likely that the data is highly redundant and you'd probably do just as well by just picking a random projection to a much smaller subspace (or simply just perform a random subsampling of the dimensions, or sum dimensions together, stuff like that) rather than spending the compute to learn a projection via SVD or some such. Hubness might be a significant problem as well and lead to search results not matching your intent. Also, numeric problems (e.g., if you were accumulating distance in floating point) would become an issue as well with millions of dimensions unless the way that distances are summed get special treatment (like Kahan summation, or reduction trees to sum values of roughly equal expected magnitude, etc) too; x += dist[i] won't cut it. Any kind of acceleration technique to limit the search to a subset of the database (such as cell-probe-ish methods like LSH or IVF, or graph-based methods, etc) would take a ton of time to compute. Simply storing all the data you need for search, even brute force, would rapidly explode, not to mention the compute required. Most cases with such large vectors I've seen begin with highly sparse vectors. Certainly Faiss (I wrote the GPU side of Faiss), Annoy, or most any similarity search libraries out there are geared to dense vectors in the 20 - 2000ish dimension range (beyond the number of dimensions where exact methods such as BSP or k-D trees work well as in "high" dimensions your nearest neighbor is highly likely to lie on either side of a dividing hyperplane, but below cases where simply storing the data uncompressed / unquantized / etc is hard and the amount of compute is prohibitive as well). How big is the data set (number of vectors) that you are searching among, and are you performing single queries or batch queries?

nl 3y ago
Thanks for the response. You are probably right in the general case. I'm only searching hundreds of vectors, and it seems to be working surprisingly well (astonishingly well really!) - but I've only spent a few hours working on this and are far from having a proper measure of how good it is. I'll try the smaller subspace ideas - seems like it'd be easy to try and could work. > How big is the data set (number of vectors) that you are searching among The biggest dataset I've tried so far is 400 (it is searching similar scenes in a sports broadcast) > and are you performing single queries or batch queries? single - choose a scene and it finds similar ones. Thanks for Faiss BTW. I love love love it - long time member of the FB group you have. I think I switched to Annoy because I had a packaging issue some time back or something.

janalsncm 3y ago

Train an autoencoder to reduce your vector dimensions down to something more workable. It’s unlikely you’ll be able to search against such enormous vectors in a reasonable amount of time anyways. Another option is to shard your vectors into N pieces, where N*k is the length of your vector. Since cosine similarity doesn’t care about order, it will be fine. The only requirement is that the k-th vector can only be compared with other k-th vectors for similarity. The benefit of this approach is that it can be parallelized easily.

nl 3y ago
The autoencoder was what I was thinking too. I was hoping to avoid training anything though! Search speed is good (although the datasize is pretty small - hundreds of vectors). So the sharding idea I'd: slice up the vector compare each sub vector with the corresponding sub vector ones from other vectors getting the similarities. sum the similarities choose the maximum Is this the general idea? Is there an implementation of this you've seen?
- janalsncm 3y ago
  If you’re looking for something out of the box, I can’t help you unfortunately. I do ML at a company where we have our own in-house tooling. I agree with your algorithm, it is equivalent to cosine similarity. But you might also consider whether you need all the shards at all. Maybe you can get away with a half or even a tenth of them. If you have some metric like ndcg you can measure the drop in performance and consider the trade off.