<div dir="ltr"><div><span></span>Hello again,<br><br></div>sorry for the late reply<br><div><div><span></span><br><span></span><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span>
</span>Yes, definitely other forms of LSH or improvement to the existing LSH<br>
implementation would be a good way to go. Dong's paper is where LSHKIT<br>
came from, right? If so it might be interesting to implement that, but<br>
only if we are pretty sure we can outperform LSHKIT (i.e. if we can make<br>
a faster implementation).<br></blockquote><div><br></div><div>From what I
can recall, LSHKIT is quite well optimized, so it might be a hard task
to outperform it. I'm not sure if it has been parallelized, though, so
that might be a way to achieve that (if you don't consider that cheating
:P).<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
One thing I found with other LSH implementations was that most of them<br>
are a little difficult to work with... a user is most likely going to<br>
want to say "I want k approximate nearest neighbors with a desired<br>
maximum of e% relative error", so they specify k and e and then the<br>
algorithm returns results with the desired error bound. But some LSH<br>
packages do not offer this kind of interface and can be very hard to<br>
work with (E2LSH is one example).<br></blockquote><div><br>Yes, that is
true, most have a big number of parameters that people not familiar with
the algorithm might not understand at first. That's why I proposed
implementing something similar to Dong's paper, since they propose a way
to identify sets of parameters that will yield results near some
specified recall/selectivity. <br>Of course this is probably going to be slower than the naive kNN implementation, but it is reasonable to run the tuning program once for a given dataset, produce favorable sets of parameters, and store these for further runs of LSH.<br></div><div>An alternative would be developing some heuristic that maps neighbor error rates to algorithm parameters. This might be tricky though, since error depends highly on the dataset. It would be an interesting endeavour though.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Here are some interesting runtime comparisons to LSHKIT that I did last<br>
year (on page 9 and 10); I compared some tree-based algorithms and then<br>
also multiprobe LSH:<br>
<br>
<a href="http://ratml.org/pub/pdf/2015faster.pdf" rel="noreferrer" target="_blank">http://ratml.org/pub/pdf/2015faster.pdf</a><br>
<br>
I think that probably LSH would be faster in higher dimensions, but that<br>
wasn't the region of interest for the study I linked to. Also that<br>
paper might be a decent place to start reading about dual-tree nearest<br>
neighbor search (and the papers that paper references might be<br>
interesting as well).<br></blockquote><div> </div><div>I've put this paper on my
reading list, as well as "An Optimal Algorithm for Approximate Nearest
Neighbor Searching in Fixed Dimensions" which you linked to in another mail. I believe I will be able to read them by the time I start writing my proposal.<br><br><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Anyway, maybe you would be the right person for this task?<br>
<br>
<a href="https://github.com/mlpack/mlpack/issues/261" rel="noreferrer" target="_blank">https://github.com/mlpack/mlpack/issues/261</a><br>
<br>
I think that if you have spent a lot of time studying and thinking about<br>
LSH, then this one may not be so difficult.<br></blockquote><div><br></div><div>** I'll respond to this in the end of my email.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
> *Another question* is inspired from an old ticket I found in GitHub, where<br>
<span>> you mention interest in parallelization. I would also be interested in, as<br>
> a side goal, implementing a parallel version of a few of the approximate<br>
> algorithms. Is that something interesting to you guys?<br>
<br>
</span>Yes, parallelization is interesting, but should probably be done via<br>
OpenMP. It can be really difficult to read parallel code, so if we make<br>
the code too complex, then suddenly developers need to have good<br>
knowledge of C++, parallel programming, and also machine learning. It's<br>
already hard enough to find people at the intersection of C++ and<br>
machine learning. :)<br></blockquote><div><br>Yes, OpenMP is probably
the best solution, each much easier to read than Pthreads code (not to mention much easier to write than Pthreads) and doesn't require a special
compiler like Intel Cilk and TBB do.<br><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
You're more than welcome to submit two proposals, but often it's better<br>
to focus on just one, since we can only accept one proposal per student.<br>
:)<br><br></blockquote><div>Then I will probably stick with one proposal and try to make it as good as possible :)<br><br></div><div>** Regarding LSH Tests:<br>The "impossibly hard" label makes this look scary, admittedly :P <br>I'll look at the test and current LSH code and see what I can think of, in the meantime could you provide some help regarding where I can find more
documentation for the test function? I haven't figured out how to run
only specific tests instead of all 616 of them.<br><br>At the moment, an idea I have is this: <br>A
typical way to test how "good" approximate algorithms are is against
some base case, so for example I've often used the SIFT dataset (<a href="http://corpus-texmex.irisa.fr/">Evaluation of Approximate nearest neighbors: large datasets</a>) to calculate metrics like selectivity and recall.<br>Of
course this doesn't check if the implementation is correct, but it
produces results we can evaluate as reasonable or unreasonable. <br><br>So
maybe an approach would be, have our LSH implementation run a few times with a few different parameters we've selected, and see how close these results get to some benchmark we know to be correct? Problems with this idea:<br>a) That requires packing a benchmarks file and SIFT dataset along with the rest of the software.<br></div><div>b) We need benchmarks, which we could get by either using some implementation we know to be good - for example, LSHKit - or by running the LSH implementation now and then re-run it every time we change the code.<br></div><br></div><div class="gmail_quote">Is this what you had in mind when you mentioned probabilistic tests?<br></div><div class="gmail_quote"><br><div><br></div><div>Thanks for the advice, I'll keep in touch!<br><br></div><div>Yannis<br><br></div></div></div></div></div></div>