逻辑回归

Delta中的逻辑回归针对隐私计算的场景，选用了不同的优化算法，以保证其执行效率。Delta中逻辑回归的设计介绍，可以参考专栏文章：

https://zhuanlan.zhihu.com/p/543486466zhuanlan.zhihu.com

Delta中的逻辑回归仍然执行在横向联邦任务框架下，将优化过程抽象为MapReduce操作执行，关于横向联邦任务框架，可参考这篇文档：

横向联邦任务框架

逻辑回归的算法选择

首先，我们先看一下单机场景下逻辑回归的算法。

假设逻辑回归是一个二分类任务，特征为$x$，类别标签为$y$，逻辑回归的权重为$w$，那么，逻辑回归的预测公式为

$$\hat{y} = sigmoid(xw)$$

我们要对$W$进行极大似然估计，也就是求使$ylog(\hat{y}) + (1-y)log(1-\hat{y})$最大的$W$。这是一个优化问题。我们可以证明，逻辑回归是一个凸函数，只需要使用优化算法，就能得到最优解。

常用的优化算法，有牛顿法、以BFGS为代表的拟牛顿法、共轭梯度法等等。 在单机场景下，像sklearn、statsmodel等库中的逻辑回归，都是使用这些优化算法来求解的。所以，要实现逻辑回归，我们需要在Delta中针对隐私计算的场景，实现一个效率最高的优化算法。

在上述的优化算法中，最经典就是牛顿法了：

牛顿法

牛顿法是一种迭代算法，用来求解方程$f(x)=0$。 牛顿法的迭代公式为：

$$x_{n+1} = x_{n} - f(x_{n}) / f'(x_{n})$$

从初始点$x_0$开始，不断地进行迭代，直到$f(x)=0$为止。

牛顿法还可以用于求极值问题。对于凸函数，极值点的导数为0。所以只需要使用牛顿法求出导数为0的点，即可求出极值点。

回到逻辑回归问题上。逻辑回归问题，是一个凸函数，求极值点，就相当于求导数为0的点。假设逻辑回归问题的目标函数为$L(w)$，$w$为权重，其导数为$g(w)$，我们要求的就是使$g(w)=0$的点，套用牛顿法，就可以得到迭代公式：

$$w_{n+1} = w_{n} - g(w_{n}) / g'(w_{n})$$

$g'(w)$是目标函数为$L(w)$的二阶导数，我们记为$h(w)$，那么迭代公式变为：

$$w_{n+1} = w_{n} - g(w_{n}) / h(w_{n})$$

停止迭代的条件也变为$g(w)=0$。

这里需要注意的是，上述的公式，都假设$w$是个标量。在实际的场景下，逻辑回归权重是一个向量，记为$W$，长度为$k$，那么，导数$g(w)$也变为一个$k$阶向量，记为$G$，二阶导数变为一个$k \times k$矩阵，即黑塞矩阵（Hessian matrix），记为$H$，那么，迭代公式变为：

$$W_{n+1} = W_{n} - H^{-1}G$$

停止迭代的条件也变为$||G|| = 0$，即$G$的范数等于0。

这里需要注意到，与标量不同，矩阵和向量是没有除法的，所以这里需要使用矩阵的逆来代替除法。

所以要使用牛顿法，我们只需要不断地计算梯度$G$与黑塞矩阵$H$即可。 对于逻辑回归，其梯度为

$$G = X^T(Y - sigmoid(XW))$$

其黑塞矩阵为

$$H = (X^T * sigmoid'(XW)) X$$

其中*表示逐元素相乘，$sigmoid'$为$sigmoid$的导数。

拟牛顿法

牛顿法需要求解黑塞矩阵$H$以及黑塞矩阵的逆$H^{-1}$。 黑塞矩阵的大小与逻辑回归的权重长度$k$有关，是$k \times k$。 计算黑塞矩阵的逆的复杂度为$O(k^3)$。

牛顿法的空间复杂度与时间复杂度都很高，分别为$O(k^2)$与$O(k^3)$。 当逻辑回归的权重长度$k$较大时，牛顿法的空间与时间开销就变得不可接受了。 因此，在单机场景下，我们一般不会选择牛顿法，而是使用拟牛顿法。牛顿法主要的开销都集中在了存储和计算黑塞矩阵$H$及其逆矩阵上，如果能不计算和存储黑塞矩阵$H$，那么开销就降下来了。拟牛顿法就是这个思路。

拟牛顿法有很多种，但是它们的思路都是类似的，即不计算黑塞矩阵$H$，而是通过梯度$G$，来对黑塞矩阵$H$或者其逆矩阵进行估计，然后再根据牛顿法的迭代公式，进行迭代。

不过，拟牛顿法得到的黑塞矩阵$H$只是个近似，并不准确，所以，通常在更新项前，需要乘以一个系数$\alpha$，用来确保迭代后，梯度是是下降的，即迭代公式变为：

$$W_{n+1} = W_{n} - \alpha H^{-1}G$$

而这个系数$\alpha$，一般是通过线搜索的方式来得到的。线搜索，简单来说，就是从一系列系数$\alpha$中，找出一个能够满足条件的系数，在这个搜索的过程中，会不断地更新权重$W$，同时不断地计算目标函数$L$以及梯度$G$。

拟牛顿法的空间与时间复杂度都减少到了$O(k)$，因为拟牛顿法只需要计算梯度$G$。 不过，由于拟牛顿法需要使用线搜索，在每一轮迭代的过程中，都需要计算多次目标函数$L$以及梯度$G$，所以拟牛顿法的时间复杂度常数会比较高，通常在几十至一百。

Delta中算法的选择

在Delta中，计算会被划分成多个轮次。每个轮次，都需要多个节点上计算、通信、安全聚合。因此在区块链隐私计算的场景下，计算的轮次数才是整个系统的瓶颈所在。因此真正需要优化的性能指标，是减少任务的计算轮次。

牛顿法中，每一轮迭代，都需要计算一次梯度$G$与黑塞矩阵$H$，并据此更新权重$W$。 其中梯度$G$与黑塞矩阵$H$需要各个数据节点上本地的梯度与黑塞矩阵，因此是个MapReduce操作； 更新权重$W$是个全局的操作，因此是一个reduce操作。 综上，牛顿法的一轮迭代，正好对应于一个MapReduce操作，可以对应于Delta中的一个计算轮次。

拟牛顿法中，每一轮迭代，需要计算一次梯度$G$，进行线搜索得到系数$\alpha$，并据此更新权重$W$。 其中，线搜素需要多次更新权重$W$，并计算目标函数$L$以及梯度$G$。由于更新权重$W$是一个全局的操作， 因此每一次更新都需要对应一个MapReduce操作。假设拟牛顿法中，线搜索需要进行$n$次，那么拟牛顿法每一轮迭代，都需要$n$个MapReduce操作，也就对应于Delta中的$n$个计算轮次。

综上，我们可以得出结论：从任务的计算轮次出发，牛顿法使用的计算轮次会更少。因此，Delta中选择使用牛顿法来实现逻辑回归。

Delta中的算法实现

实现逻辑回归，最主要的部分就是实现牛顿法。从牛顿法的描述可知，牛顿法需要多轮迭代，每一轮需要计算梯度$G$与黑塞矩阵$H$，并更新权重$W$。 梯度$G$与黑塞矩阵$H$需要各个数据节点上本地的梯度与黑塞矩阵，因此是个MapReduce操作；更新权重$W$是个全局的操作，因此是一个reduce操作。 更新权重$W$这个操作比较简单，只需要输入全局的梯度$G$与黑塞矩阵$H$，以及上一轮的权重$W$即可。 我们主要关注计算梯度$G$与黑塞矩阵$H$这个操作。

首先，梯度$G$与黑塞矩阵$H$的计算之间没有依赖关系，因此可以放在一起计算。其次，我们来考虑如何将单机的计算变为MapReduce。 在Delta中，map与reduce之间，需要经过安全聚合的操作，将多个节点的结果相加起来。 所以我们需要考虑，如何通过加法，来得到梯度$G$与黑塞矩阵$H$。

先说结论，我们只需要根据牛顿法中介绍的$G$与$H$的公式，在各个数据节点本地进行计算，然后再通过安全聚合相加，即可得到全局的结果。

我们可以从定义出发来得到这个结论。$G$计算的是损失函数$L$针对$W$的梯度，数据集中的每个样本 都有自身的损失函数值$l$，而整个数据集的损失函数$L$不过是每个样本的损失函数值$l$之和（或者是均值也可以）。那么，$L$对于$W$的梯度， 自然也是每个样本的损失函数值$l$针对$W$的梯度之和（或者是均值）。现在我们将数据集分布到了多个数据节点上， 我们只需要将各个数据节点上的所有样本的损失函数值$l$针对$W$的梯度加起来，就可以得到全局的$G$了。所以，安全聚合后的结果，就是全局的结果。 同理，黑塞矩阵$H$也是如此。

这样一来，我们就可以实现牛顿法中的一个迭代，只需要实现一个MapReduce操作，得到$G$与$H$，再实现一个reduce操作，更新权重$W$即可。

实现了迭代之后，我们还需要实现整个牛顿法的循环，也就是多轮迭代。这里需要注意的是，牛顿法并不是一个固定轮次的迭代，而是在每一轮迭代中，对停止迭代的条件进行判断，如果满足条件，就停止迭代。这与Delta中之前的横向联邦学习不同，横向联邦学习任务固定了迭代的总轮次，所以整个任务需要执行的轮次数量，在任务定义时就固定了，而牛顿法在任务定义时，就无法固定所需执行的轮次，需要在运行时才能决定。因此，我们在Delta中新增了一个提前结束的机制。这个机制，简单来说，就是在满足一定条件的情况下，提前结束整个任务的执行，直接返回结果。在这一机制下，我们就可以这样实现牛顿法：给牛顿法的迭代次数规定一个上限，这样在任务定义时就可以确定迭代轮次的上限，在任务执行过程中，通过提前结束的机制，来随时终止任务的执行，得到任务的结果。

实现了牛顿法之后，逻辑回归大体就实现完了。剩余的部分很简单，只需要对数据集进行预处理以及初始化权重即可。这两步操作都是map操作， 其中预处理操作是用户自定义的。

至此，我们就在Delta中实现了逻辑回归。