Paper ID: 1062
Title: Evasion and Hardening of Tree Ensemble Classifiers

Review #1
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): The classifier evasion problem for tree ensemble is studied. Contributions are:  * One exact and one approximate algorithms are proposed to evade a tree ensemble classifier * Empirically shows that tree ensemble is vulnerable to classifier evasion * Propose a simple yet effective remedy to "harden" (i.e., to make it much harder to evade) a tree ensemble

Clarity - Justification: The English reads comfortable and the whole article is easy to follow. The presentation may have a room to improve, though. See the detailed comments. 

Significance - Justification: This study is novel in the classifier evasion sub discipline. The tree ensemble evasion has not yet been systematically studied before.   The shown empirical results support the authors' claim. But I may have other concerns on the experiments.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): * Significance *  Classifier evasion for neural network and linear classifier have attracted a lot of interests recently. The submitted paper seems the first one to systematically study how to evade a tree ensemble, which has not yet been studied well. The most related previous paper simply relies on a genetic optimization to do the same thing, lacking a detailed analysis. In this paper, both an exact (based on integer programming) and an approximate (based on coordinate descent with dynamic-programming-like sub-problem) algorithms are proposed to evade a tree ensemble.  The observation of tree ensemble's brittleness to evasion is interesting and makes sense intuitively. BTW, I think all the classifiers with internal/implicit feature selection would be vulnerable, because perturbing the selected feature with large weight/importance will dramatically alter the prediction score (similar to the authors' hunch at line 795), no matter whether the classifier model is linear or non-linear. Meanwhile, this may also explain the robustness of RBF-SVM that the weights are more evenly distributed to all features (raw pixels in the paper's experiments) with a template-matching-like kernel trick. Having said that, I may have concerns here:  * Cons of The Experiments *  This paper empirically finds that Boosting tree is easy to evade and the proposed adversary boosting can harden a boosting tree ensemble without loss of testing time accuracy. However, the result is reported on an image dataset with medium-sized feature space, where only a few raw features (i.e., the pixels) will be picked up by boosting tree according to my experience - this is likely to be the source of the evasion brittleness, as what I said above.   What if all the features with almost evenly distributed weights enter in the final tree ensemble for a particular dataset with low dimensional feature space (e.g., the UCI German dataset)? Actually, whether the boosting tree is still evasion vulnerable would be unclear in this case.  However, it may ask too much for a conference paper intending for the fast spreading of novel work to address this problem. But it is indeed a serious concern for the future work, as what the authors (subtly) say at line 795 and line 876.  * Other Comments *   Here are some texts in the paper that I think need more explanation/clarification to help the readers understand them better: - Line 305: why let $ell$ be continuous, are't they finally binary variables when considering the constraints line 378 - line 396 ? - At the end of section 4.3, could add a summary of the objective and all the constraints with new variables $p$ and $ell$, which help the readers to compare them with eq (1).  - At section 5.3, add a feature importance "heat map" organized as 28 x 28 image size for several selected classifiers, including the boosting tree. This is to see if less features indicate less robustness to evasion.  Other minor comments: - Line 127: didn't see the discussion for extracted features at section 3? (BTW, boosting tree over transformed features, like SIFT, HOG, random-pixel-difference for computer vision, would be another interesting topic for machine learning practitioners) - Fig 1. explicitly say -2, 1, -1, 2 are leaf predictions (easily to mistake them with ell) - Line 464, superscript for L? - Line 474, explicitly say (x_0 = 0, x_1 = 3) - Line 567, dot or tilde for x_k? - Sometimes "leafs", sometimes "leaves" through the paper? 

=====

Review #2
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): This paper tackles the problem of evading instances in learning ensembles of decision trees, ie. the problem of finding an instance with a negligible perturbation that changes radically its predicted class. Two algorithms are proposed, an exact one and an approximate. They are tested on a subset of MNIST (6s vs 2s). Furthermore, the approximate algorithm is successfully used to train a more robust version of ensembles of trees.

Clarity - Justification: The explanations are very clear. The plots are pertinent.  Question: starting from the lin 378, aren't the conditions 1) and 3) redundant? Can you clarify the difference between them?

Significance - Justification: Model evasion is a crucial topic, as machine learning systems, now widely used in practice, could potentially expose security flaws. Additionally, the topic can be beneficial in understanding these models, often presented as black boxes. In this regard, the paper extends an area of research that has been almost exclusively restricted to neural networks and it does it elegantly by casting the problem as a Mixed Integer Linear Program. 

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): As mentioned, hardening against evasion wrt one norm makes it easier to evade in other norms. Question: have you tried to combine different distances into one objective to see if this effect can be avoided?

=====

Review #3
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): This paper has several contributions: - Adversarial examples can be created for sum-ensemble of tree regressors. - NP-Hardness of the creation of adversarial examples - Efficient practical algorithm for the construction of adversarial examples based on ILP (both accurate and approximate ones) - Training with adversarial examples can significantly enhance the robustness of tree-ensemble models.

Clarity - Justification: The paper is very clearly structured and has intuitive clear structuring into the relevant sections. The paper is clearly motivated by related phenomenons in adjacent domains. They mathematical notations are concise and can the statements can be easily followed. It is nicely written and the various sections of the paper make sense in isolation as well. The related literature is very well explained and a concise overview is given to the interested reader.

Significance - Justification: The existence of adversarial examples and training with adversarial examples poses a lot of practical and theoretical questions. It is important to know which classes of models are susceptible to adversarial examples and how they can be tested for the existence of those. Also, it is useful to know whether those models can be made more robust in general.  This paper gives convincing answers several of these question for case of tree-regressor models. These answers are sometimes non-trivial, as these kinds of models require special purpose discrete solvers to construct and harden against adversarial examples. 

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): Although susceptibility to adversarial examples has been viewed as a deficiency of deep neural networks, it was clear since their introduction that even linear classifiers can be fooled relatively easily. Later work by Goodfellow et al has established that the existence of adversarial examples is connected to the feasibility of their optimization. Those kinds of models that can be efficiently constructed have easy to construct adversarial examples.  For the ensemble of tree regressors it used to be unclear how susceptible they were to adversarial example procedures. This paper addresses this question by showing that optimal adversarial examples can be created efficiently using integer-linear-programming. Also approximate construction of such examples is discussed. It turns out that the adversarial examples created by this way include variations not percievable by human observers in the case of mnist. Also the papers present compelling evidence that ensembles of tree-classifiers can be made robust by training on the newly created adversarial examples.  The main criticism on this paper is that experimental evidence is only provided for the MNIST dataset. It is fairly unclear how results should generalize to more practical datasets.   The other criticism is that the paper does not seem to study the most interesting aspect of adversarial examples: their generalization across different training sets.  

=====