Search for nonmonotonic regions in decision trees

Question

I have a binary decision tree T that takes a vector V from n real numbers and prints the number S, following the coordinate binary partitions on V. I would like to find areas of the tree that are nonmonotonic. That is, if I reduce another input to V to form V ', and the tree then assigns a larger output to V' than V, then I found a non-monotonic region.

How to find these regions?

Answer 1

I assume that “for coordinated binary splits” means that decisions are made one coordinate at a time. For all leaf pairs L1 and L2, where L1 has a smaller value than L2, define the axis-oriented bounding fields for L1 and L2. If the maximum angle L1 dominates the minimum angle L2 for some L1 and L2, then the tree is not monotonic. Conversely, if such a pair does not exist, then the tree is monotonous.

Answer 2

I do not provide details, just a general direction. let me know if you need more information.

Suppose you have a tree that considers one function (i.e. one real number) and prints either a single number or a range. Now it is easy to find non-monotonic areas of this tree (for any node, if the range of the left subtree overlaps the range of the right subtree, then there are non-monotonic areas in this part of the tree).

You can convert your general DT to DT, which works with only one function and applies the above methodology.

In general, you can maintain a range for each function on each node and use the same criteria that I mentioned above to find such regions.