2020-03-28 17:26:00 聯邦學習

前言

Gradient Boosting Decision Tree (GBDT) 是一个非常流行的机器学习模型，经常在机器学习及数据挖掘竞赛中被使用。随着人们对隐私越来越注重，联邦学习最近得到了越来越多的关注。GBDT和联邦学习结合是一个重要的研究课题。今天为大家介绍的是一篇被AAAI 2020接收的论文《Practical Federated Gradient Boosting Decision Trees》，作者来自新加坡国立大学的Qinbin Li, Bingsheng He和西澳大学的Zeyi Wen，论文地址https://arxiv.org/pdf/1911.04206.pdf。在这篇文章中，作者提出了一个实用的GBDT联邦学习框架。

背景

GBDT模型由多颗决策树组成。在进行预测时，预测值为所有树上的对应叶子值的和。一个示例如图1所示。在构造决策树时，需要用到各个样本的损失函数在当前预测值上的一阶和二阶导数 (用g和h表示)。

图1 GBDT示例

本文中作者考虑横向联邦学习的场景。多个组织拥有不同的数据，如何在不交换数据的情况下联合训练一个有效的GBDT模型？作者提出了SimFL (Similarity-based Federated Learning)，一个新的联邦学习框架。

方法介绍

整个联邦学习框架分为两个阶段：预处理阶段和训练阶段。

预处理阶段的目标是收集相似信息，如图2所示。这里作者使用到了局部敏感哈希 (Locality-Sensitive Hashing, LSH)，这种哈希函数的特点是两个相似的样本得到相同哈希值的可能性也较高，而且无法从哈希值逆推出样本值。作者采用了多个LSH函数，每个组织首先计算自己样本对应的哈希值，然后广播这些值给其他的组织。经过广播后，所有的组织都可以构建一个哈希表，里面存储着样本序号和对应的哈希值。然后，每个组织都可以通过这个哈希表来计算相似信息。具体来说，如果两个样本有更多相同的哈希值，那么他们相似的可能性更大。每个组织对于自己的每个样本，都在其他组织中寻找一个拥有相同哈希值最多的样本，标记为相似样本。预处理阶段过后，每个组织对于自己的样本，都能在其他各个组织中找到一个相似样本。

图2 预处理阶段

收集完相似信息后，接下来进入到训练阶段。图3给出了一个简单示例。总的来说，每个组织轮流训练一些树，最终的模型为各个组织训练的树之和。在训练一棵树前，所有组织都需要用目前已经构建的决策树来更新各个样本的g和h，并将g和h传给接下来训练新的一颗决策树的组织。这个组织利用自己的样本和所有的g和h来训练一棵树，然后将这棵树发送给其他的组织。最终，就可以训练完成整个GBDT模型。

这里作者提出了一个新的训练方法，取名为加权梯度下降 (weighted gradient boosting)。传统的GBDT使用g和h来构建决策树，这里作者将相似样本的g相加，将得到的结果作为加权梯度来代替原来的g进行训练 (h同理)。这种训练方式可以有效的整合其他组织的数据分布信息，即使没有获取到其他组织的具体样本值。论文中有提供这种方法的理论分析。

图3 训练阶段

实验结果

作者在6个公开数据集上进行了实验。这里作者尝试了两种不同的数据划分方法:均匀划分和不均匀划分。在均匀划分中，作者将数据集随机等分成几份，每份表示一个组织的本地数据集，这样不同组织的数据服从独立同分布。在不均匀划分中，作者按照样本标签来进行划分，保证部分组织某一种样本的比例要比另一部分要高，这样不同组织数据不服从独立同分布。实验具体细节请参考论文，下面展示论文中的部分实验结果。

图4 不均匀划分下的实验

图4中横坐标为组织的数量，纵坐标为测试集上的错误率。蓝线为作者提出的方法 (SimFL)，灰线为所有组织直接分享数据进行训练 (ALL-IN)，黑线为组织之间不合作只进行本地训练 (SOLO)，红线为另一篇发表于INFOCOM 2018 (http://nisplab.whu.edu.cn/paper/infocom_2018_3.pdf) 的一个框架 (TFL)。可以看到，SimFL的效果不错，比TFL和SOLO好，并且在组织数目少的时候非常逼近ALL-IN。