Ents: An Efficient Three-party Training Framework for Decision Trees by Communication Optimization

本文介绍了一种名为Ents的高效三方训练框架，通过通信优化来训练决策树。多方计算决策树的训练框架可以在保护隐私的前提下，利用分布式私有数据训练高性能模型。训练过程基本上涉及根据分裂标准（例如基尼不纯度）频繁地对数据集进行分裂。然而，现有的多方训练框架在以下问题上表现出通信效率低下：（1）在安全地分割具有连续属性的数据集时，它们遭受巨大的通信开销。（2）由于几乎所有计算都在大环上进行，以适应分裂标准的安全计算，因此它们遭受巨大的通信开销。为了解决这些问题，本文提出了一系列基于安全基数排序协议的训练协议，以有效且安全地分割具有连续属性的数据集。同时，本文还提出了一种有效的份额转换协议，以在小环和大环之间转换份额，以减少几乎所有计算都在大环上进行所带来的通信开销。实验结果表明，Ents在8个广泛使用的数据集上的表现优于现有的框架，通信大小提高了5.5倍到9.3倍，通信轮次提高了3.9倍到5.3倍。在培训时间方面，Ents的改进为3.5倍到6.7倍。为了证明其实用性，Ents在WAN环境下仅需要不到三个小时即可对一个广泛使用的真实数据集（皮肤分割）进行安全的决策树训练。

论文旨在提出一种高效的三方训练框架（Ents）来解决现有多方决策树训练框架中存在的通信效率问题，尤其是在连续属性数据集的安全划分和大环上的计算通信开销问题。

论文的关键思路是通过优化通信来提高多方决策树训练框架的效率。具体而言，论文提出了一系列基于安全基数排序协议的训练协议来高效安全地划分具有连续属性的数据集，并提出了一种有效的份额转换协议来在小环和大环之间转换份额，以减少计算通信开销。

论文的实验结果表明，Ents相比现有的多方训练框架，在通信大小和通信轮数上分别提高了$5.5\times \sim 9.3\times$和$3.9\times \sim 5.3\times$，在训练时间上提高了$3.5\times \sim 6.7\times$。论文还演示了Ents在真实数据集（Skin Segmentation）上的实际训练时间不到三个小时。值得关注的是，Ents使用的安全基数排序协议和份额转换协议可以在其他多方计算任务中使用。

最近在这个领域中，也有一些相关的研究，如：SecureBoost、Privacy-preserving decision tree learning等。