Adversarially Robust Decision Tree Relabeling

Daniël Vos; Sicco Verwer

doi:10.1007/978-3-031-26409-2_13

Adversarially Robust Decision Tree Relabeling

^*Corresponding author for this work

Cyber Security

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

2 Citations (Scopus)

56 Downloads (Pure)

Abstract

Decision trees are popular models for their interpretation properties and their success in ensemble models for structured data. However, common decision tree learning algorithms produce models that suffer from adversarial examples. Recent work on robust decision tree learning mitigates this issue by taking adversarial perturbations into account during training. While these methods generate robust shallow trees, their relative quality reduces when training deeper trees due the methods being greedy. In this work we propose robust relabeling, a post-learning procedure that optimally changes the prediction labels of decision tree leaves to maximize adversarial robustness. We show this can be achieved in polynomial time in terms of the number of samples and leaves. Our results on 10 datasets show a significant improvement in adversarial accuracy both for single decision trees and tree ensembles. Decision trees and random forests trained with a state-of-the-art robust learning algorithm also benefited from robust relabeling.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings
Editors	Massih-Reza Amini, Stéphane Canu, Asja Fischer, Tias Guns, Petra Kralj Novak, Grigorios Tsoumakas
Publisher	Springer
Pages	203-218
Number of pages	16
ISBN (Print)	9783031264085
DOIs	https://doi.org/10.1007/978-3-031-26409-2_13
Publication status	Published - 2023
Event	22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022 - Grenoble, France Duration: 19 Sept 2022 → 23 Sept 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13715 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022
Country/Territory	France
City	Grenoble
Period	19/09/22 → 23/09/22

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Adversarial examples
Decision trees
Pruning

Access to Document

10.1007/978-3-031-26409-2_13

978-3-031-26409-2_13Final published version, 1.76 MB

Cite this

Vos, D., & Verwer, S. (2023). Adversarially Robust Decision Tree Relabeling. In M.-R. Amini, S. Canu, A. Fischer, T. Guns, P. Kralj Novak, & G. Tsoumakas (Eds.), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings (pp. 203-218). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13715 LNAI). Springer. https://doi.org/10.1007/978-3-031-26409-2_13

Vos, Daniël ; Verwer, Sicco. / Adversarially Robust Decision Tree Relabeling. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings. editor / Massih-Reza Amini ; Stéphane Canu ; Asja Fischer ; Tias Guns ; Petra Kralj Novak ; Grigorios Tsoumakas. Springer, 2023. pp. 203-218 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{77ce9829e274474fa8b5aa147f87ea76,

title = "Adversarially Robust Decision Tree Relabeling",

abstract = "Decision trees are popular models for their interpretation properties and their success in ensemble models for structured data. However, common decision tree learning algorithms produce models that suffer from adversarial examples. Recent work on robust decision tree learning mitigates this issue by taking adversarial perturbations into account during training. While these methods generate robust shallow trees, their relative quality reduces when training deeper trees due the methods being greedy. In this work we propose robust relabeling, a post-learning procedure that optimally changes the prediction labels of decision tree leaves to maximize adversarial robustness. We show this can be achieved in polynomial time in terms of the number of samples and leaves. Our results on 10 datasets show a significant improvement in adversarial accuracy both for single decision trees and tree ensembles. Decision trees and random forests trained with a state-of-the-art robust learning algorithm also benefited from robust relabeling.",

keywords = "Adversarial examples, Decision trees, Pruning",

author = "Dani{\"e}l Vos and Sicco Verwer",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. ; 22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022 ; Conference date: 19-09-2022 Through 23-09-2022",

year = "2023",

doi = "10.1007/978-3-031-26409-2_13",

language = "English",

isbn = "9783031264085",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "203--218",

editor = "Massih-Reza Amini and St{\'e}phane Canu and Asja Fischer and Tias Guns and {Kralj Novak}, Petra and Grigorios Tsoumakas",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings",

}

Vos, D & Verwer, S 2023, Adversarially Robust Decision Tree Relabeling. in M-R Amini, S Canu, A Fischer, T Guns, P Kralj Novak & G Tsoumakas (eds), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13715 LNAI, Springer, pp. 203-218, 22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022, Grenoble, France, 19/09/22. https://doi.org/10.1007/978-3-031-26409-2_13

Adversarially Robust Decision Tree Relabeling. / Vos, Daniël ; Verwer, Sicco.
Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings. ed. / Massih-Reza Amini; Stéphane Canu; Asja Fischer; Tias Guns; Petra Kralj Novak; Grigorios Tsoumakas. Springer, 2023. p. 203-218 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13715 LNAI).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Adversarially Robust Decision Tree Relabeling

AU - Vos, Daniël

AU - Verwer, Sicco

N1 - Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2023

Y1 - 2023

N2 - Decision trees are popular models for their interpretation properties and their success in ensemble models for structured data. However, common decision tree learning algorithms produce models that suffer from adversarial examples. Recent work on robust decision tree learning mitigates this issue by taking adversarial perturbations into account during training. While these methods generate robust shallow trees, their relative quality reduces when training deeper trees due the methods being greedy. In this work we propose robust relabeling, a post-learning procedure that optimally changes the prediction labels of decision tree leaves to maximize adversarial robustness. We show this can be achieved in polynomial time in terms of the number of samples and leaves. Our results on 10 datasets show a significant improvement in adversarial accuracy both for single decision trees and tree ensembles. Decision trees and random forests trained with a state-of-the-art robust learning algorithm also benefited from robust relabeling.

AB - Decision trees are popular models for their interpretation properties and their success in ensemble models for structured data. However, common decision tree learning algorithms produce models that suffer from adversarial examples. Recent work on robust decision tree learning mitigates this issue by taking adversarial perturbations into account during training. While these methods generate robust shallow trees, their relative quality reduces when training deeper trees due the methods being greedy. In this work we propose robust relabeling, a post-learning procedure that optimally changes the prediction labels of decision tree leaves to maximize adversarial robustness. We show this can be achieved in polynomial time in terms of the number of samples and leaves. Our results on 10 datasets show a significant improvement in adversarial accuracy both for single decision trees and tree ensembles. Decision trees and random forests trained with a state-of-the-art robust learning algorithm also benefited from robust relabeling.

KW - Adversarial examples

KW - Decision trees

KW - Pruning

UR - http://www.scopus.com/inward/record.url?scp=85151058816&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-26409-2_13

DO - 10.1007/978-3-031-26409-2_13

M3 - Conference contribution

AN - SCOPUS:85151058816

SN - 9783031264085

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 203

EP - 218

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings

A2 - Amini, Massih-Reza

A2 - Canu, Stéphane

A2 - Fischer, Asja

A2 - Guns, Tias

A2 - Kralj Novak, Petra

A2 - Tsoumakas, Grigorios

PB - Springer

T2 - 22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022

Y2 - 19 September 2022 through 23 September 2022

ER -

Vos D , Verwer S. Adversarially Robust Decision Tree Relabeling. In Amini MR, Canu S, Fischer A, Guns T, Kralj Novak P, Tsoumakas G, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2022, Proceedings. Springer. 2023. p. 203-218. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-26409-2_13

Adversarially Robust Decision Tree Relabeling

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this