# Finding the maximum of a random forest

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?

## 1 Answer

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.

• 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. – user1502040 Mar 21 '18 at 0:40