I have trained two binary decision tree classifiers with splits in $\mathbb{R}^4$. Same data, but from two different patches. Now, I want to find the exact intervals where the two trees disagree.

The splits are along the lines of: \begin{align*} & (x_1 > 0.35592521727085114) \wedge (x_3 \leq-0.13628841191530228) \implies 0, \\ & \vdots \\ & (x_3 \leq -0.013720870949327946) \wedge (x_1 > 0.35592521727085114) \wedge (x_3 > -0.13628841191530228) \implies1. \\ \end{align*} ($x_2$ and $x_4$ are allowed to live anywhere between their absolute bounds.)

Any advice on how to approach this? I've read some material on interval trees, and theoretically at least I can see how they might be expanded to higher dimensions, but I'm wondering if someone out there has experience with a particular tree variant, or other data-structure that would be appropriate in this case.

Help very much appreciated.

  • 1
    $\begingroup$ You can go over all pairs of leaves in the two different trees with different classification, and compute the set of points reaching them — it will be some sort of cylinder. $\endgroup$ – Yuval Filmus Apr 21 at 5:31

Yuval Filmus has articulated an elegant solution, which I'll expand on.

Given a leaf of a decision tree, it is easy to characterize the set of values of $x$ that reach that leaf. Namely, you take the conjunction of all the conditions along the path from the root to the leaf. For trees of the form you list, this will have the form $[\ell_1,u_1] \times \cdots \times [\ell_4,u_4]$, i.e., the set of all $x$ such that $\ell_1 \le x_1 \le u_1 \land \cdots \land \ell_4 \le x_4 \le u_4$, where you can explicitly compute $\ell_1,\dots,\ell_4,u_1,\dots,u_4$.

Now apply the following algorithm:

  • For each pair of leaves, with one leaf in the first tree and the other leaf in the second tree, such that the two leaves lead to different classifications:

    • Compute the set of values $x$ that reach the first leaf, the set of values $x$ that reach the second leaf, and compute their intersection. Output the intersection (this is one set of points where the decision trees differ).

The union (i.e., disjunction) of all of those outputs will be the complete set of points where the two trees give a different decision.

It is possible to come up with algorithms that might be faster; however, I'm not sure whether they will lead to a significant improvement in higher dimensions.

One approach is to construct a new tree via a "product construction". Thus, each node in the new tree is a pair $(u,v)$, where $u$ is a node in your first tree and $v$ is a node in your second tree. The root of the tree is $(r_1,r_2)$, where $r_1$ is the root of your first tree and $r_2$ is the root of your second tree. You can build the new tree top-down, starting from $(r_1,r_2)$, then splitting using the condition at one of these two nodes ($r_1$ or $r_2$). As you build the tree, keep track of the set of values that can reach each new node $(u,v)$. If this set is empty, you can prune it and don't need to explore any of its children. This might reduce the number of nodes you need to expand. In the worst case, there is no speedup, but in practice, it might help a little.

It gets more interesting if each classifier is an ensemble/forest of trees; then the best solution would probably be to use a SMT solver.

  • $\begingroup$ Ok- so as you and @yuval suggest, if tree A has n leaves w/ response 1, and tree B has m leaves w/ response 0, we need to make m*n comparisons (plus comparisons for the opposite case). Is there a more efficient way? Suppose A and B make choices based on a single 1D variable. We construct a binary search tree whose nodes store the (non-overlapping) intervals where A responds with 1. We determine intersections with intervals where B responds with 0 by searching the tree, which wouldn't require n comparisons. Does it make sense to try something like this in higher dimensions? $\endgroup$ – Nate S. Apr 21 at 23:34
  • $\begingroup$ @NateS., perhaps, but are you sure it is necessary to look for a speedup? How large is n and m in your application? Have you tried to implement this basic approach to see how well it works for your situation? Fancier methods might not work very well in higher dimensions, so the cost of designing and implementing a fancier algorithm might not be worth it. I suggest you check whether the basic approach is good enough before embarking on such a project. $\endgroup$ – D.W. Apr 22 at 1:05
  • $\begingroup$ @NateS., see the edited answer for an additional algorithm that tries to be more efficient, but doesn't come with any guarantees. $\endgroup$ – D.W. Apr 22 at 6:37
  • $\begingroup$ ah very interesting. Ok let me give this a shot. Thanks for your help! $\endgroup$ – Nate S. Apr 22 at 10:26

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.