[mlpack-git] [mlpack/mlpack] Spill trees (#747)

Ryan Curtin notifications at github.com
Sat Aug 13 01:16:26 EDT 2016

> +#include <mlpack/core.hpp>
> +
> +#include "spill_tree.hpp"
> +
> +namespace mlpack {
> +namespace tree {
> +
> +template<typename MetricType,
> +         typename StatisticType,
> +         typename MatType,
> +         template<typename HyperplaneMetricType> class HyperplaneType,
> +         template<typename SplitMetricType, typename SplitMatType>
> +             class SplitType>
> +template<typename RuleType>
> +class SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
> +    SingleTreeTraverser

The mlpack tree traversers (single-tree and dual-tree) implement the concepts defined as "pruning single-tree traversals" and "pruning dual-tree traversals" in the tree-independent dual-tree algorithms paper.  But in this case the traversals you have here don't actually satisfy that definition because they have defeatist search hard-coded into them.  So if the Rules class doesn't explicitly handle that case, then the traversal is technically invalid.

In the scheme of things this is a really minor point, but I think that it's possible that this may confuse someone way down the line who just says "okay, I want to test my Rules class with all the trees and their default traversers" and suddenly it doesn't work for spill trees and their traversers.  So, I can think of a couple quick solutions:

 * Add a boolean template parameter which, if true, will do the defeatist search as you have implemented it, but it is documented that setting that template parameter to true will make the traverser technically violate the definition.

 * Add documentation stating that the traverser technically violates the definition, providing no way to get a "rigorously correct" traversal.

I am not sure if either of those is the best solution, but I do think it is important that the defeatist search part of this traversal is implemented, otherwise it will be doing two scores when it only needs to do one in those cases.  Maybe you have a better idea for how to handle this?

You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160812/1b5bccb7/attachment-0001.html>

More information about the mlpack-git mailing list