Random forests on monotone training set yields a monotone classifier?

Question

Suppose I train a random forests classifier on a monotone training set. Is the resulting classifier guaranteed to be a monotone function?

Suppose I apply the ID3 algorithm (the greedy algorithm) to learn a decision tree on a monotone training set. Is the resulting decision tree guaranteed to be a monotone function?

---

I can formalize this a bit more precisely. Recall that a function is monotone if $x \le y$ implies $f(x) \le f(y)$, where we define $\le$ on $\{0,1\}^n$ by pointwise comparison ($x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,n$).

Suppose we have a monotone boolean function $f:\{0,1\}^n \to \{0,1\}$, and suppose that we build a training set as some set of pairs $(x_i,y_i)$ where $y_i=f(x_i)$. In other words, the training set is consistent with some monotone function, with no errors.

Now train a random forests classifier on a training set of this form. This will learn a classifier that can be thought of as a map $g:\{0,1\}^n \to \{0,1\}$. Is it guaranteed that the learned classifier will be a monotone function? Alternatively, suppose we apply the ID3 algorithm on this training set. (The ID3 algorithm is the obvious greedy algorithm for recursively building a decision tree that is consistent with the training set.) Is it guaranteed that the learned decision tree will form a monotone function?

Answer 1

No, it's not guaranteed. You can end up with a decision tree or classifier that is non-monotone.

Here is an explicit counterexample, i.e., a training set of 5 samples on 5 attributes:

$$\begin{align*} &(01011, 0)\\ &(01101, 0)\\ &(00111, 1)\\ &(10110, 0)\\ &(11000, 1) \end{align*}$$

This training set is monotone: it is consistent with the monotone function

$$f(x_0,x_1,x_2,x_3,x_4) = (x_0 \land x_1) \lor (x_2 \land x_3 \land x_4).$$

However, if you run the ID3 algorithm on this training set, you may end up with a decision tree that computes the function

$$g(x_0,x_1,x_2,x_3,x_4) = (\neg x_0 \land \neg x_1) \lor (x_0 \land x_1),$$

which is also consistent with the training set yet is not monotone. In other words, ID3 might produce the following decision tree:

       x0
     /    \
    /      \
  x1        x1
 /  \      /  \
1    0    0    1

which is quite evidently non-monotone (there's an obvious violation of monotonicity in the lower-left part of the tree, where the tree says that the output should be the negation of $x_1$ -- clearly non-monotonic).

Why can ID3 produce this decision tree? Starting with the entire training set, splitting on $x_0$ yields predictions (information gain) that is at least as good as splitting on any other attribute. Then we recursively run ID3 on the subset of training samples where $x_0=0$ and recursively run ID3 on the subset of training samples where $x_0=1$, and on each recursive run we discover an attribute that provides perfect prediction. Try running the ID3 algorithm by hand to see what I mean.

Now at this point perhaps you are going to object: the ID3 algorithm made a choice that is obviously stupid. When the training set contained $(01011,0)$, $(01101,0)$, and $(00111,1)$, the algorithm noticed that $x_1$ provides perfect prediction of $y$, via the rule $y = \neg x_1$ -- but this is a stupid choice if we want to end up with a monotone classifier, since even without looking into the future we can immediately see that this is going to yield a non-monotonic result.

So it is natural to try to rescue the ID3 algorithm with a local pruning rule that, at each stage, only considers attributes that aren't obviously dumb -- that aren't obviously going to lead to a violation of monotonicity. Here is one way we could try to operationalize that idea. Let's adjust the ID3 algorithm to be locally monotone. Normally, the ID3 algorithm chooses an attribute $x_i$ that reduces the information gain as much as possible. We could adjust this to also require that we pick an $x_i$ that is locally monotone, i.e., the fraction of training set pairs with $x_i=0 \land y=1$ is at most the fraction of training set pairs with $x_i=1 \land y=1$. (If $x_i$ is not locally monotone, then splitting on $x_i$ seems likely to yield a decision tree where we predict an output of 1 more often when $x_i=0$ than when $x_i=1$, which is a violation of monotonicity.) Out of all locally monotone choices, we'll pick the attribute with the best information gain (or the lowest Gini impurity, if you prefer).

Unfortunately, even with this modification to enforce local monotonicity, ID3 can still fail to yield a monotonic decision tree. When we run the ID3 algorithm on the above data set, we obtain a decision tree that computes the function

$$g'(x_0,x_1,x_2,x_3,x_4) = (\neg x_0 \land x_2 \land x_3) \lor (x_0 \land x_1),$$

which is consistent with the training set yet is not monotonic. In particular, we might obtain the following decision tree:

       x0
     /    \
    /      \
  x2        x1
 /  \      /  \
0    x3   0    1
    /  \
   0    1

This decision tree achieves 100% accuracy on the training set, yet it isn't monotone, even though there exists another decision tree (of the same depth) that is monotone and also achieves 100% accuracy.

Why can ID3 produce this decision tree? Starting with the entire training set, splitting on $x_0$ yields predictions (information gain) that is at least as good as splitting on any other attribute. Then we recursively run ID3 on the subset of training samples where $x_0=0$ and recursively run ID3 on the subset of training samples where $x_0=1$, and similar comments apply at each stage of the algorithm. I'll let you run ID3 by hand and see that there is a way to resolve ties at each step that yields the decision tree above.

In short, we can potentially lose either way, whether or not we apply the "locally monotone" constraint. We might get lucky and end up with a monotone decision tree, but there is no guarantee of that -- we also might unlucky and end up with a non-monotone decision tree, even though there exists a monotone decision tree that would be at least as good.

Similar comments apply to the random forests algorithm, as it merely applies the ID3 algorithm multiple times. (Each tree is learned on a different subset of the training set, and with different subsets of the features at each node of the tree, but the same kind of anomaly can still occur.)

This proves that it is at least possible to end up with a non-monotonic classifier, even when starting from a monotone data set. I don't know how likely it is that this will happen in practice, though, when taking the probability over the random choices made in the ID3 algorithm (to resolve ties) and in the random forests algorithm (for bagging and feature subsetting).

In other words, this demonstrates that if our goal is to learn a monotonic classifier, it's not enough to simply apply the standard random forests or ID3 training procedure on a (monotone) training set; something more sophisticated is needed.