2
$\begingroup$

If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is it possible to efficiently find the subspace on which this function achieves its maximum? Enumerating all intersections could take exponential time in e.g. the case where each tree is a stump which bisects a different dimension.

It is possible to do better by computing bounds and doing some pruning, but I wonder whether a polynomial-time solution is possible.

If the leaf values are taken from $\{0, 1\}$ then this is a restricted max-clique problem, but I suspect it should be possible to exploit the decision-tree structure to create a faster algorithm.

Any thoughts?

|cite|improve this question
$\endgroup$
2
$\begingroup$

Apparently, it's NP-hard. See the following paper:

Evasion and Hardening of Tree Ensemble Classifiers. Alex Kantchelian, J.D. Tygar, Anthony D. Joseph. ICML 2016.

Section 4.2 says that solving the problem exactly is NP-hard. However, the paper then goes on to develop techniques that, in practice, might often find an approximate maximum, using integer linear programming.

For a proof of NP-hardness, see Section 5.2 of Kantchelian's PhD dissertation.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! It's obvious in retrospect that the problem is NP-hard. I suspect it's probably fairly easy in practice, just like the traveling salesman problem. $\endgroup$ – user1502040 Mar 21 '18 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.