[mlpack] GSoC Project: LMNN (via LRSDP) & BoostMetric Implementation

[Manish Kumar]

Hi Ryan,

This is regarding the constraints generation algorithm for LMNN. So, here's
what I think could be an option for generating {data point, target
neighbors, impostors} triplets:
1) We can use KNN  to search for N - 1 neighbors for all the N data points.
(The runtime of KNN search will determine the major part of runtime of
whole algo.)
2) Then we could select k targetNeighbors and impostors corresponding to
each data point.
3) finally generate triplets using targetNeighbors and impostors.

Here is a sample code https://pastebin.com/Vb5VJawv for above 3 steps.

I have compared the runtime of above code with Boostmetric's KNN-triplets
generation algo and this one has shown a significant speedup. (0.15s/5.82s
on a dataset of 125 points and k = 5)

Let me know your view on this.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://knife.lugatgt.org/pipermail/mlpack/attachments/20180510/a6801886/attachment.html>