逻辑回归

上一页横向联邦统计下一页逻辑回归中的零知识证明

最后更新于2年前

这有帮助吗？

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

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中实现了逻辑回归。

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

\hat{y} = sigmoid(xw)

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

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

从初始点 $x_0$ 开始，不断地进行迭代，直到 $f(x)=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_{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$ 的导数。

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

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

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