逻辑回归
Delta中的逻辑回归针对隐私计算的场景,选用了不同的优化算法,以保证其执行效率。Delta中逻辑回归的设计介绍,可以参考专栏文章:
Delta中的逻辑回归仍然执行在横向联邦任务框架下,将优化过程抽象为MapReduce操作执行,关于横向联邦任务框架,可参考这篇文档:
横向联邦任务框架逻辑回归的算法选择
首先,我们先看一下单机场景下逻辑回归的算法。
假设逻辑回归是一个二分类任务,特征为,类别标签为,逻辑回归的权重为,那么,逻辑回归的预测公式为
我们要对进行极大似然估计,也就是求使最大的。这是一个优化问题。我们可以证明,逻辑回归是一个凸函数,只需要使用优化算法,就能得到最优解。
常用的优化算法,有牛顿法、以BFGS为代表的拟牛顿法、共轭梯度法等等。 在单机场景下,像sklearn
、statsmodel
等库中的逻辑回归,都是使用这些优化算法来求解的。所以,要实现逻辑回归,我们需要在Delta中针对隐私计算的场景,实现一个效率最高的优化算法。
在上述的优化算法中,最经典就是牛顿法了:
牛顿法
牛顿法是一种迭代算法,用来求解方程。 牛顿法的迭代公式为:
从初始点开始,不断地进行迭代,直到为止。
牛顿法还可以用于求极值问题。对于凸函数,极值点的导数为0。所以只需要使用牛顿法求出导数为0的点,即可求出极值点。
回到逻辑回归问题上。逻辑回归问题,是一个凸函数,求极值点,就相当于求导数为0的点。假设逻辑回归问题的目标函数为,为权重,其导数为,我们要求的就是使的点,套用牛顿法,就可以得到迭代公式:
是目标函数为的二阶导数,我们记为,那么迭代公式变为:
停止迭代的条件也变为。
这里需要注意的是,上述的公式,都假设是个标量。在实际的场景下,逻辑回归权重是一个向量,记为,长度为,那么,导数也变为一个阶向量,记为,二阶导数变为一个矩阵,即黑塞矩阵(Hessian matrix),记为,那么,迭代公式变为:
停止迭代的条件也变为,即的范数等于0。
这里需要注意到,与标量不同,矩阵和向量是没有除法的,所以这里需要使用矩阵的逆来代替除法。
所以要使用牛顿法,我们只需要不断地计算梯度与黑塞矩阵即可。 对于逻辑回归,其梯度为
其黑塞矩阵为
其中*表示逐元素相乘,为的导数。
拟牛顿法
牛顿法需要求解黑塞矩阵以及黑塞矩阵的逆。 黑塞矩阵的大小与逻辑回归的权重长度有关,是。 计算黑塞矩阵的逆的复杂度为。
牛顿法的空间复杂度与时间复杂度都很高,分别为与。 当逻辑回归的权重长度较大时,牛顿法的空间与时间开销就变得不可接受了。 因此,在单机场景下,我们一般不会选择牛顿法,而是使用拟牛顿法。牛顿法主要的开销都集中在了存储和计算黑塞矩阵及其逆矩阵上,如果能不计算和存储黑塞矩阵,那么开销就降下来了。拟牛顿法就是这个思路。
拟牛顿法有很多种,但是它们的思路都是类似的,即不计算黑塞矩阵,而是通过梯度,来对黑塞矩阵或者其逆矩阵进行估计,然后再根据牛顿法的迭代公式,进行迭代。
不过,拟牛顿法得到的黑塞矩阵只是个近似,并不准确,所以,通常在更新项前,需要乘以一个系数,用来确保迭代后,梯度是是下降的,即迭代公式变为:
而这个系数,一般是通过线搜索的方式来得到的。线搜索,简单来说,就是从一系列系数中,找出一个能够满足条件的系数,在这个搜索的过程中,会不断地更新权重,同时不断地计算目标函数以及梯度。
拟牛顿法的空间与时间复杂度都减少到了,因为拟牛顿法只需要计算梯度。 不过,由于拟牛顿法需要使用线搜索,在每一轮迭代的过程中,都需要计算多次目标函数以及梯度,所以拟牛顿法的时间复杂度常数会比较高,通常在几十至一百。
Delta中算法的选择
在Delta中,计算会被划分成多个轮次。每个轮次,都需要多个节点上计算、通信、安全聚合。因此在区块链隐私计算的场景下,计算的轮次数才是整个系统的瓶颈所在。因此真正需要优化的性能指标,是减少任务的计算轮次。
牛顿法中,每一轮迭代,都需要计算一次梯度与黑塞矩阵,并据此更新权重。 其中梯度与黑塞矩阵需要各个数据节点上本地的梯度与黑塞矩阵,因此是个MapReduce
操作; 更新权重是个全局的操作,因此是一个reduce
操作。 综上,牛顿法的一轮迭代,正好对应于一个MapReduce
操作,可以对应于Delta中的一个计算轮次。
拟牛顿法中,每一轮迭代,需要计算一次梯度,进行线搜索得到系数,并据此更新权重。 其中,线搜素需要多次更新权重,并计算目标函数以及梯度。由于更新权重是一个全局的操作, 因此每一次更新都需要对应一个MapReduce
操作。假设拟牛顿法中,线搜索需要进行次,那么拟牛顿法每一轮迭代,都需要个MapReduce
操作,也就对应于Delta中的个计算轮次。
综上,我们可以得出结论:从任务的计算轮次出发,牛顿法使用的计算轮次会更少。因此,Delta中选择使用牛顿法来实现逻辑回归。
Delta中的算法实现
实现逻辑回归,最主要的部分就是实现牛顿法。从牛顿法的描述可知,牛顿法需要多轮迭代,每一轮需要计算梯度与黑塞矩阵,并更新权重。 梯度与黑塞矩阵需要各个数据节点上本地的梯度与黑塞矩阵,因此是个MapReduce
操作;更新权重是个全局的操作,因此是一个reduce
操作。 更新权重这个操作比较简单,只需要输入全局的梯度与黑塞矩阵,以及上一轮的权重即可。 我们主要关注计算梯度与黑塞矩阵这个操作。
首先,梯度与黑塞矩阵的计算之间没有依赖关系,因此可以放在一起计算。其次,我们来考虑如何将单机的计算变为MapReduce
。 在Delta中,map
与reduce
之间,需要经过安全聚合的操作,将多个节点的结果相加起来。 所以我们需要考虑,如何通过加法,来得到梯度与黑塞矩阵。
先说结论,我们只需要根据牛顿法中介绍的与的公式,在各个数据节点本地进行计算,然后再通过安全聚合相加,即可得到全局的结果。
我们可以从定义出发来得到这个结论。计算的是损失函数针对的梯度,数据集中的每个样本 都有自身的损失函数值,而整个数据集的损失函数不过是每个样本的损失函数值之和(或者是均值也可以)。那么,对于的梯度, 自然也是每个样本的损失函数值针对的梯度之和(或者是均值)。现在我们将数据集分布到了多个数据节点上, 我们只需要将各个数据节点上的所有样本的损失函数值针对的梯度加起来,就可以得到全局的了。所以,安全聚合后的结果,就是全局的结果。 同理,黑塞矩阵也是如此。
这样一来,我们就可以实现牛顿法中的一个迭代,只需要实现一个MapReduce
操作,得到与,再实现一个reduce
操作,更新权重即可。
实现了迭代之后,我们还需要实现整个牛顿法的循环,也就是多轮迭代。这里需要注意的是,牛顿法并不是一个固定轮次的迭代,而是在每一轮迭代中,对停止迭代的条件进行判断,如果满足条件,就停止迭代。这与Delta中之前的横向联邦学习不同,横向联邦学习任务固定了迭代的总轮次,所以整个任务需要执行的轮次数量,在任务定义时就固定了,而牛顿法在任务定义时,就无法固定所需执行的轮次,需要在运行时才能决定。因此,我们在Delta中新增了一个提前结束的机制。这个机制,简单来说,就是在满足一定条件的情况下,提前结束整个任务的执行,直接返回结果。在这一机制下,我们就可以这样实现牛顿法:给牛顿法的迭代次数规定一个上限,这样在任务定义时就可以确定迭代轮次的上限,在任务执行过程中,通过提前结束的机制,来随时终止任务的执行,得到任务的结果。
实现了牛顿法之后,逻辑回归大体就实现完了。剩余的部分很简单,只需要对数据集进行预处理以及初始化权重即可。这两步操作都是map
操作, 其中预处理操作是用户自定义的。
至此,我们就在Delta中实现了逻辑回归。
最后更新于