Huang, Wei, Zhao, Xingyu 
ORCID: 0000-0002-3474-349X and Huang, Xiaowei ORCID: 0000-0001-6267-0366
(2022)
Embedding and Extraction of Knowledge in Tree Ensemble Classifiers.
Machine Learning, 111 (5).
pp. 1925-1958.
|
Text
Embedding_and_Extraction_of_Knowledge_in_Tree_Ensemble_Classifiers.pdf - Author Accepted Manuscript Download (2MB) | Preview |
Abstract
The embedding and extraction of knowledge is a recent trend in machine learning applications, e.g., to supplement training datasets that are small. Whilst, as the increasing use of machine learning models in security-critical applications, the embedding and extraction of malicious knowledge are equivalent to the notorious backdoor attack and defence, respectively. This paper studies the embedding and extraction of knowledge in tree ensemble classifiers, and focuses on knowledge expressible with a generic form of Boolean formulas, e.g., point-wise robustness and backdoor attacks. For the embedding, it is required to be \emph{preservative} (the original performance of the classifier is preserved), \emph{verifiable} (the knowledge can be attested), and \emph{stealthy} (the embedding cannot be easily detected). To facilitate this, we propose two novel, and effective, embedding algorithms, one of which is for black-box settings and the other for white-box settings. The embedding can be done in \textbf{PTIME}. Beyond the embedding, we develop an algorithm to extract the embedded knowledge, by reducing the problem to be solvable with an SMT (satisfiability modulo theories) solver. While this novel algorithm can successfully extract knowledge, the reduction leads to an \textbf{NP} computation. Therefore, if applying embedding as backdoor attacks and extraction as defence, our results suggest a complexity gap (P vs. NP) between the attack and defence when working with tree ensemble classifiers. We apply our algorithms to a diverse set of datasets to validate our conclusion extensively.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | cs.CR, cs.CR, cs.LG |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 Sep 2021 08:25 |
| Last Modified: | 18 Jan 2023 21:28 |
| DOI: | 10.1007/s10994-021-06068-6 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3137076 |
Dimensions
Dimensions
