Comment on page
逻辑回归

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