7
$\begingroup$

I have a binary classification (supervised learning) problem, where all my features are boolean, with the following twist: I want to learn a classifier $f:\{0,1\}^n \to \{0,1\}$ that is monotone. In other words, changing any subset of features from 0 to 1 should never change the output of the classifier from 1 to 0.

How can I learn a monotone classifier? Can I adapt standard classification methods somehow, to enforce the monotonicity constraint?

I can see how to adapt logistic regression in a way that ensures it will learn a monotonic model: we can require that each feature's coefficient be non-negative, and then apply a constrained optimization algorithm to infer the coefficients of the model. Is there a reasonable way to adapt other supervised learning schemes (e.g., random forests, gradient boosting, neural networks)? Or are there dedicated algorithms that are appropriate for this situation?


Unfortunately just applying a standard random forests classifier is not guaranteed to yield a monotone classifier, even if the training set is monotone (it comes from a monotone setting, and has no noise or violations of monotonicity). See https://cs.stackexchange.com/q/69220/755 for an explicit example, i.e., an example of a monotone training set, where random forests might learn a non-monotone classifier -- even though there exists a monotone classifier that is equally good. This suggests that we might need some more sophisticated technique if we want to learn a monotone classifier.

$\endgroup$
  • 1
    $\begingroup$ Just a question: do your data come from a monotone settings or do they also contain some counter examples? If there would be no counter examples, then e.g. random forests shall work fine. If there are some, you could simply remove them from the training set. $\endgroup$ – Karel Macek Jan 19 '17 at 0:42
  • $\begingroup$ @KarelMacek, cool! Since I'm looking for an entry point into the literature or into techniques, I'm fine with assuming the data in the training set is all monotone. Is it guaranteed that a random forests classifier trained on a monotone data set will yield a monotone classifier? $\endgroup$ – D.W. Jan 19 '17 at 1:06
  • $\begingroup$ @KarelMacek, thanks for the suggestion! Unfortunately it looks like just applying standard random forests can fail -- see last paragraph of edited question for explanation and a link to an explicit example. It's not evident to me how to repair the problem. Any ideas? $\endgroup$ – D.W. Jan 24 '17 at 2:56
  • $\begingroup$ A MLP neural network with weights greater than or equal to 1 and nondecreasing, nonnegative activation functions (e.g. ReLU) satisfies the monotonicity requirement. This is because the sums of nonnegative numbers are nonnegative, and a positive number $p$ multiplied by a number greater than 1 is larger than $p$. $\endgroup$ – Reinstate Monica Jan 24 '17 at 3:56
2
$\begingroup$

While it's an old question, I have just found that gradient boosted trees support such functionality and it is already implemented with at XGBoost. Check here for more details

$\endgroup$

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.