Except apparently that commit breaks the code... Maybe I've misunderstood
something :(
On 16 April 2015 at 14:18, Joel Nothman <joel.noth...@gmail.com> wrote:
> ball tree is not vectorized in the sense of SIMD, but there is
> Python/numpy overhead in LSHForest that is not present in ball tree.
>
> I think one of the problems is the high n_candidates relative to the
> n_neighbors. This really increases the search time.
>
> Once we're dealing with large enough index and n_candidates, most time is
> spent in searchsorted in the "synchronous ascending phase", while any
> overhead around it is marginal. Currently we are searching over the whole
> array in each searchsorted, while it could be rewritten to keep better
> track of context to cut down the overall array when searching. While
> possible, I suspect this will look confusing in Python/Numpy, and Cython
> will be a clearer and faster way to present this logic.
>
> On the other hand, time spent in _compute_distances is substantial, and
> yet most of its consumption is *outside* of pairwise_distances. This
> commit
> <https://github.com/scikit-learn/scikit-learn/commit/c1f335f70aa0f766a930f8ac54eeaa601245725a>
> cuts a basic benchmark from 85 to 70 seconds. Vote here for merge
> <https://github.com/scikit-learn/scikit-learn/pull/4603>!
>
> On 16 April 2015 at 12:32, Maheshakya Wijewardena <pmaheshak...@gmail.com>
> wrote:
>
>> Moreover, this drawback occurs because LSHForest does not vectorize
>> multiple queries as in 'ball_tree' or any other method. This slows the
>> exact neighbor distance calculation down significantly after approximation.
>> This will not be a problem if queries are for individual points.
>> Unfortunately, former is the more useful usage of LSHForest.
>> Are you trying individual queries or multiple queries (for n_samples)?
>>
>> On Thu, Apr 16, 2015 at 6:14 AM, Daniel Vainsencher <
>> daniel.vainsenc...@gmail.com> wrote:
>>
>>> LHSForest is not intended for dimensions at which exact methods work
>>> well, nor for tiny datasets. Try d>500, n_points>100000, I don't remember
>>> the switchover point.
>>>
>>> The documentation should make this clear, but unfortunately I don't see
>>> that it does.
>>> On Apr 15, 2015 7:08 PM, "Joel Nothman" <joel.noth...@gmail.com> wrote:
>>>
>>>> I agree this is disappointing, and we need to work on making LSHForest
>>>> faster. Portions should probably be coded in Cython, for instance, as the
>>>> current implementation is a bit circuitous in order to work in numpy. PRs
>>>> are welcome.
>>>>
>>>> LSHForest could use parallelism to be faster, but so can (and will) the
>>>> exact neighbors methods. In theory in LSHForest, each "tree" could be
>>>> stored on entirely different machines, providing memory benefits, but
>>>> scikit-learn can't really take advantage of this.
>>>>
>>>> Having said that, I would also try with higher n_features and
>>>> n_queries. We have to limit the scale of our examples in order to limit the
>>>> overall document compilation time.
>>>>
>>>> On 16 April 2015 at 01:12, Miroslav Batchkarov <mbatchka...@gmail.com>
>>>> wrote:
>>>>
>>>>> Hi everyone,
>>>>>
>>>>> was really impressed by the speedups provided by LSHForest compared to
>>>>> brute-force search. Out of curiosity, I compared LSRForest to the existing
>>>>> ball tree implementation. The approximate algorithm is consistently slower
>>>>> (see below). Is this normal and should it be mentioned in the
>>>>> documentation? Does approximate search offer any benefits in terms of
>>>>> memory usage?
>>>>>
>>>>>
>>>>> I ran the same example
>>>>> <http://scikit-learn.org/stable/auto_examples/neighbors/plot_approximate_nearest_neighbors_scalability.html#example-neighbors-plot-approximate-nearest-neighbors-scalability-py>
>>>>> with
>>>>> a algorithm=ball_tree. I also had to set metric=‘euclidean’ (this may
>>>>> affect results). The output is:
>>>>>
>>>>> Index size: 1000, exact: 0.000s, LSHF: 0.007s, speedup: 0.0, accuracy:
>>>>> 1.00 +/-0.00
>>>>> Index size: 2511, exact: 0.001s, LSHF: 0.007s, speedup: 0.1, accuracy:
>>>>> 0.94 +/-0.05
>>>>> Index size: 6309, exact: 0.001s, LSHF: 0.008s, speedup: 0.2, accuracy:
>>>>> 0.92 +/-0.07
>>>>> Index size: 15848, exact: 0.002s, LSHF: 0.008s, speedup: 0.3,
>>>>> accuracy: 0.92 +/-0.07
>>>>> Index size: 39810, exact: 0.005s, LSHF: 0.010s, speedup: 0.5,
>>>>> accuracy: 0.84 +/-0.10
>>>>> Index size: 100000, exact: 0.008s, LSHF: 0.016s, speedup: 0.5,
>>>>> accuracy: 0.80 +/-0.06
>>>>>
>>>>> With n_candidates=100, the output is
>>>>>
>>>>> Index size: 1000, exact: 0.000s, LSHF: 0.006s, speedup: 0.0, accuracy:
>>>>> 1.00 +/-0.00
>>>>> Index size: 2511, exact: 0.001s, LSHF: 0.006s, speedup: 0.1, accuracy:
>>>>> 0.94 +/-0.05
>>>>> Index size: 6309, exact: 0.001s, LSHF: 0.005s, speedup: 0.2, accuracy:
>>>>> 0.92 +/-0.07
>>>>> Index size: 15848, exact: 0.002s, LSHF: 0.007s, speedup: 0.4,
>>>>> accuracy: 0.90 +/-0.11
>>>>> Index size: 39810, exact: 0.005s, LSHF: 0.008s, speedup: 0.7,
>>>>> accuracy: 0.82 +/-0.13
>>>>> Index size: 100000, exact: 0.007s, LSHF: 0.013s, speedup: 0.6,
>>>>> accuracy: 0.78 +/-0.04
>>>>>
>>>>>
>>>>>
>>>>> ---
>>>>> Miroslav Batchkarov
>>>>> PhD Student,
>>>>> Text Analysis Group,
>>>>> Department of Informatics,
>>>>> University of Sussex
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>> BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
>>>>> Develop your own process in accordance with the BPMN 2 standard
>>>>> Learn Process modeling best practices with Bonita BPM through live
>>>>> exercises
>>>>> http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual-
>>>>> event?utm_
>>>>> source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
>>>>> _______________________________________________
>>>>> Scikit-learn-general mailing list
>>>>> Scikit-learn-general@lists.sourceforge.net
>>>>> https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
>>>>>
>>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
>>>> Develop your own process in accordance with the BPMN 2 standard
>>>> Learn Process modeling best practices with Bonita BPM through live
>>>> exercises
>>>> http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual-
>>>> event?utm_
>>>> source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
>>>> _______________________________________________
>>>> Scikit-learn-general mailing list
>>>> Scikit-learn-general@lists.sourceforge.net
>>>> https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
>>>>
>>>>
>>>
>>> ------------------------------------------------------------------------------
>>> BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
>>> Develop your own process in accordance with the BPMN 2 standard
>>> Learn Process modeling best practices with Bonita BPM through live
>>> exercises
>>> http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual-
>>> event?utm_
>>> source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
>>> _______________________________________________
>>> Scikit-learn-general mailing list
>>> Scikit-learn-general@lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
>>>
>>>
>>
>>
>> --
>>
>> *Maheshakya Wijewardena,Undergraduate,*
>> *Department of Computer Science and Engineering,*
>> *Faculty of Engineering.*
>> *University of Moratuwa,*
>> *Sri Lanka*
>>
>>
>> ------------------------------------------------------------------------------
>> BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
>> Develop your own process in accordance with the BPMN 2 standard
>> Learn Process modeling best practices with Bonita BPM through live
>> exercises
>> http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual-
>> event?utm_
>> source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
>> _______________________________________________
>> Scikit-learn-general mailing list
>> Scikit-learn-general@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
>>
>>
>
------------------------------------------------------------------------------
BPM Camp - Free Virtual Workshop May 6th at 10am PDT/1PM EDT
Develop your own process in accordance with the BPMN 2 standard
Learn Process modeling best practices with Bonita BPM through live exercises
http://www.bonitasoft.com/be-part-of-it/events/bpm-camp-virtual- event?utm_
source=Sourceforge_BPM_Camp_5_6_15&utm_medium=email&utm_campaign=VA_SF
_______________________________________________
Scikit-learn-general mailing list
Scikit-learn-general@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
