Decision trees are interpretable models that are well-suited to non-linear learning problems. Much work has been done on extending decision tree learning algorithms with differential privacy, a system that guarantees the privacy of samples within the training data. However, current state-of-the-art algorithms for this purpose sacrifice much utility for a small privacy benefit. These solutions create random decision nodes that reduce decision tree accuracy or spend an excessive share of the privacy budget on labeling leaves. Moreover, many works do not support or leak information about feature values when data is continuous. We propose a new method called PrivaTree based on private histograms that chooses good splits while consuming a small privacy budget. The resulting trees provide a significantly better privacy-utility trade-off and accept mixed numerical and categorical data without leaking additional information. Finally, while it is notoriously hard to give robustness guarantees against data poisoning attacks, we prove bounds for the expected success rates of backdoor attacks against differentially-private learners. Our experimental results show that PrivaTree consistently outperforms previous works on predictive accuracy and significantly improves robustness against backdoor attacks compared to regular decision trees.

本文提出了一种名为 PrivaTree 的新方法，基于私有直方图的决策树扩展算法，它在具有混合数值和分类数据的情况下，在消耗小的隐私预算的同时选择了良好的分裂策略，并且在隐私-效用平衡上提供了显著更好的性能，并且相对于常规决策树，显著提高了对抗象征攻击的鲁棒性。

具有概率鲁棒性的差分隐私决策树对抗数据污染