8 ms·

Have You Tried Using a Nearest Neighbor Search?

87 points by gjstein 11y ago

bpires 10y ago
I don't think YOLO [0], the object detector he talked about, requires a massive amount of data as he claimed. Yes, if you want to learn how to classify 1000 different categories like on ImageNet, then yes, you need a lot of data. But if you're taking a pretrained network like YOLO (it was pretrained on ImageNet and trained on Pascal), you don't need a lot of images. I've retrained it with the KITTI dataset [1] and had no issues at all. They're only 7k images. By the way KITTI actually has a vehicles dataset that might be helpful for your case. And also by the way, you don't even need to retrain YOLO with your vehicle dataset. It was trained on Pascal VOC [2], a dataset of 20 categories and one of the categories is car. So YOLO already knows how to detect cars, it just might not be ideal for your dataset, but you don't care anyways since you just want any solution to compare to as a baseline. This would probably have been even less work than training the cascade classifier you used and have achieved better results. [0]: http://pjreddie.com/darknet/yolo/ http://pjreddie.com/darknet/yolo/ [1]: http://www.cvlibs.net/datasets/kitti/ http://www.cvlibs.net/datasets/kitti/ [2]: http://host.robots.ox.ac.uk/pascal/VOC/ http://host.robots.ox.ac.uk/pascal/VOC/
- romaniv 10y ago
  > They're only 7k images. I feel like all those deep learning papers distorted people's perception of scale. If you need to take those 7k images by hand because your application domain is obscure and they aren't available in an existing dataset, that's way beyond feasible.
  - WiseWeasel 10y ago
    You could generate 7k images at a resolution of 4096x2160 pixels by walking around the vehicle for just under four minutes while shooting 4k video at 30 FPS, something of which modern phones are capable.
    - romaniv 10y ago
      Yes, but how different would those 7K frames would really be? Same lighting, same background, same surrounding objects, the exact same condition of the vehicle's interior and exterior, same quirks of the camera's color profile, etc, etc. It would be an interesting experiment to actually try this, but I have a feeling the results wouldn't be all that good. Point being, you probably wouldn't get most of the benefits of deep learning and you might as well use the same approach the author used.
      - WiseWeasel 10y ago
        As you walk around the vehicle, and change the angle from low to high, the lighting and background should have a good variance.
        fredophile 10y ago
        No they won't. All of the pictures will have lighting from the time of day and weather conditions from the time and place the pictures were taken. The same problems will happen for the background. If I want my neural network to identify the make and model of cars, but every picture I have of a Mazda3 is taken at noon on a sunny day in suburbia then it is reasonably likely to train on the wrong features and either identify trucks on sunny days in suburbia as Mazda3's or not recognize a Mazda3 photographed on a rainy night.
        WiseWeasel 10y ago
        A human might have difficulty recognizing a Mazda 3 on a rainy night as well. You can adjust color temperature and white balance in post-processing, or film a couple minutes at night too. Point is, generating 7k images is not insurmountable, especially in this case with the criteria that it only has to recognize a particular car.
leecarraher 10y ago
I think your results are pretty strongly predicated on the fact that we have immensely powerful computers these days such that brute forcing is a viable option in many casual real world situations (detect objects in a picture). In fact exact NN algoirthms for high dimensional embeddings converge to linear search performance as the dimensionality increase so a brute force NN is often a good choice always. But that doesn't mean there aren't other problems where the datasets are truly large and require fast query responses (bioinformatics, GIS, anomaly detection...). Which is where you get approximate nearest neighbor search. Haar transform is useful if you dont expect your object to ever rotate or significantly change size, but for more robust image recognition i would suggest david lowes' sift. Which actually spurred much of the approximate nearest neighbor search space, since you didn't necessarily need the closest match, rather just something that was near. Currently the optimal approximate nearest neighbor search algorithm has complexity O(n^rho+d log n) where rho is typically less than 0.37.
liviu- 10y ago
> I quickly discovered that such a system was overkill for me, and resorted to using an open source implementation of a simpler algorithm [1]. Maybe worth pointing out that the "simpler algorithm" they used seems to be a cascading ensemble of adaptive boosting algorithms, technique similar to the ones used on Kaggle to win the big prizes. Maybe simpler than some neural nets in some ways, but nothing close to the simplicity of nearest neighbour search. [1] http://docs.opencv.org/2.4/doc/tutorials/objdetect/cascade_classifier/cascade_classifier.html http://docs.opencv.org/2.4/doc/tutorials/objdetect/cascade_c...
GrantS 10y ago
Very good to be reminded of this. The funny thing is that there was a brief time right before deep learning took over computer vision research, but after people realized the implications of big data, where it looked like the future could be really simple nearest neighbor search supported by enormous data sets. For example, the famous "80 million tiny images" paper by Torralba, Fergus, and Freeman from 2008. PDF: http://people.csail.mit.edu/torralba/publications/80millionImages.pdf http://people.csail.mit.edu/torralba/publications/80millionI... Web: http://groups.csail.mit.edu/vision/TinyImages/ http://groups.csail.mit.edu/vision/TinyImages/
itodd 10y ago
I'm currently trying to find similar strings (max hamming of 2) between two very large (1e9) sets. Approximate Nearest Neighbor search makes this just barely manageable. Annoy[0] from Spotify deserves a look for anyone who is outgrowing traditional nearest neighbor algorithms. [0] https://github.com/spotify/annoy https://github.com/spotify/annoy
- dalke 10y ago
  Assuming your strings are a lot larger than length 2, you might look at locality-sensitive hashing. If you are using fixed length bit strings, let me know as there are other ways to get sublinear search time for NxM searches. Handwave: order your strings in M by popcount. If string n has popcount p then you only need to compare to the m in M which have between p-2 and p+2 bits set. You can subdivide the search space even further. And with newer processors, the POPCNT instruction is your friend.
  - aktenlage 10y ago
    Do you have a suggestion about the case where the hamming distance of the nearest neighbor is unknown? My first thought is to start at the "distance-of-p" block and continue with the "p+i" and "p-i" block in a loop.
    - dalke 10y ago
      Yes, that is why my code does.
      - aktenlage 10y ago
        thanks
  - retbull 10y ago
    I thought popcnt has a bug? I am just going off of memory of reading some very indepth blog posts on how it slowed down run times rather than sped them up. I could have forgotten though. Before I even finished this post I just went and found it. Looks like it might be only for haswell and sandy/ivy bridge http://stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-count-variable-with-64-bit-introduces-crazy-performance http://stackoverflow.com/questions/25078285/replacing-a-32-b...
wodenokoto 10y ago
In the statistical learning course available online as a mooc at stanford they take it a step further: "If it wasn't for the course of dimensionality we would only use nearest neighbor search"
- infodroid 10y ago
  > the course of dimensionality dimensionality is surely a curse :)
- arcanus 10y ago
  In my field you could state that if it was not for the curse of dimensionality, we would use anything but MCMC.

87 points by gjstein 11y ago

I don't think YOLO [0], the object detector he talked about, requires a massive amount of data as he claimed. Yes, if you want to learn how to classify 1000 different categories like on ImageNet, then yes, you need a lot of data. But if you're taking a pretrained network like YOLO (it was pretrained on ImageNet and trained on Pascal), you don't need a lot of images. I've retrained it with the KITTI dataset [1] and had no issues at all. They're only 7k images. By the way KITTI actually has a vehicles dataset that might be helpful for your case. And also by the way, you don't even need to retrain YOLO with your vehicle dataset. It was trained on Pascal VOC [2], a dataset of 20 categories and one of the categories is car. So YOLO already knows how to detect cars, it just might not be ideal for your dataset, but you don't care anyways since you just want any solution to compare to as a baseline. This would probably have been even less work than training the cascade classifier you used and have achieved better results. [0]: http://pjreddie.com/darknet/yolo/ http://pjreddie.com/darknet/yolo/ [1]: http://www.cvlibs.net/datasets/kitti/ http://www.cvlibs.net/datasets/kitti/ [2]: http://host.robots.ox.ac.uk/pascal/VOC/ http://host.robots.ox.ac.uk/pascal/VOC/

romaniv 10y ago
> They're only 7k images. I feel like all those deep learning papers distorted people's perception of scale. If you need to take those 7k images by hand because your application domain is obscure and they aren't available in an existing dataset, that's way beyond feasible.
- WiseWeasel 10y ago
  You could generate 7k images at a resolution of 4096x2160 pixels by walking around the vehicle for just under four minutes while shooting 4k video at 30 FPS, something of which modern phones are capable.
  - romaniv 10y ago
    Yes, but how different would those 7K frames would really be? Same lighting, same background, same surrounding objects, the exact same condition of the vehicle's interior and exterior, same quirks of the camera's color profile, etc, etc. It would be an interesting experiment to actually try this, but I have a feeling the results wouldn't be all that good. Point being, you probably wouldn't get most of the benefits of deep learning and you might as well use the same approach the author used.
    - WiseWeasel 10y ago
      As you walk around the vehicle, and change the angle from low to high, the lighting and background should have a good variance.
      - fredophile 10y ago
        No they won't. All of the pictures will have lighting from the time of day and weather conditions from the time and place the pictures were taken. The same problems will happen for the background. If I want my neural network to identify the make and model of cars, but every picture I have of a Mazda3 is taken at noon on a sunny day in suburbia then it is reasonably likely to train on the wrong features and either identify trucks on sunny days in suburbia as Mazda3's or not recognize a Mazda3 photographed on a rainy night.
        WiseWeasel 10y ago
        A human might have difficulty recognizing a Mazda 3 on a rainy night as well. You can adjust color temperature and white balance in post-processing, or film a couple minutes at night too. Point is, generating 7k images is not insurmountable, especially in this case with the criteria that it only has to recognize a particular car.

leecarraher 10y ago

I think your results are pretty strongly predicated on the fact that we have immensely powerful computers these days such that brute forcing is a viable option in many casual real world situations (detect objects in a picture). In fact exact NN algoirthms for high dimensional embeddings converge to linear search performance as the dimensionality increase so a brute force NN is often a good choice always. But that doesn't mean there aren't other problems where the datasets are truly large and require fast query responses (bioinformatics, GIS, anomaly detection...). Which is where you get approximate nearest neighbor search. Haar transform is useful if you dont expect your object to ever rotate or significantly change size, but for more robust image recognition i would suggest david lowes' sift. Which actually spurred much of the approximate nearest neighbor search space, since you didn't necessarily need the closest match, rather just something that was near. Currently the optimal approximate nearest neighbor search algorithm has complexity O(n^rho+d log n) where rho is typically less than 0.37.

liviu- 10y ago

> I quickly discovered that such a system was overkill for me, and resorted to using an open source implementation of a simpler algorithm [1]. Maybe worth pointing out that the "simpler algorithm" they used seems to be a cascading ensemble of adaptive boosting algorithms, technique similar to the ones used on Kaggle to win the big prizes. Maybe simpler than some neural nets in some ways, but nothing close to the simplicity of nearest neighbour search. [1] http://docs.opencv.org/2.4/doc/tutorials/objdetect/cascade_classifier/cascade_classifier.html http://docs.opencv.org/2.4/doc/tutorials/objdetect/cascade_c...

GrantS 10y ago

Very good to be reminded of this. The funny thing is that there was a brief time right before deep learning took over computer vision research, but after people realized the implications of big data, where it looked like the future could be really simple nearest neighbor search supported by enormous data sets. For example, the famous "80 million tiny images" paper by Torralba, Fergus, and Freeman from 2008. PDF: http://people.csail.mit.edu/torralba/publications/80millionImages.pdf http://people.csail.mit.edu/torralba/publications/80millionI... Web: http://groups.csail.mit.edu/vision/TinyImages/ http://groups.csail.mit.edu/vision/TinyImages/

itodd 10y ago

I'm currently trying to find similar strings (max hamming of 2) between two very large (1e9) sets. Approximate Nearest Neighbor search makes this just barely manageable. Annoy[0] from Spotify deserves a look for anyone who is outgrowing traditional nearest neighbor algorithms. [0] https://github.com/spotify/annoy https://github.com/spotify/annoy

dalke 10y ago
Assuming your strings are a lot larger than length 2, you might look at locality-sensitive hashing. If you are using fixed length bit strings, let me know as there are other ways to get sublinear search time for NxM searches. Handwave: order your strings in M by popcount. If string n has popcount p then you only need to compare to the m in M which have between p-2 and p+2 bits set. You can subdivide the search space even further. And with newer processors, the POPCNT instruction is your friend.
- aktenlage 10y ago
  Do you have a suggestion about the case where the hamming distance of the nearest neighbor is unknown? My first thought is to start at the "distance-of-p" block and continue with the "p+i" and "p-i" block in a loop.
  - dalke 10y ago
    Yes, that is why my code does.
    - aktenlage 10y ago
      thanks
- retbull 10y ago
  I thought popcnt has a bug? I am just going off of memory of reading some very indepth blog posts on how it slowed down run times rather than sped them up. I could have forgotten though. Before I even finished this post I just went and found it. Looks like it might be only for haswell and sandy/ivy bridge http://stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-count-variable-with-64-bit-introduces-crazy-performance http://stackoverflow.com/questions/25078285/replacing-a-32-b...

wodenokoto 10y ago

In the statistical learning course available online as a mooc at stanford they take it a step further: "If it wasn't for the course of dimensionality we would only use nearest neighbor search"

infodroid 10y ago
> the course of dimensionality dimensionality is surely a curse :)
arcanus 10y ago
In my field you could state that if it was not for the curse of dimensionality, we would use anything but MCMC.