Machine Learning & Federated Learning

    该部分您可以参考博客博客: 从机器学习谈起，原作者：计算机的潜意识。

    参考文章：【机器学习】逻辑回归（非常详细）
    逻辑回归（Logistic Regression, 后文简称LR）是一种经典的算法，广泛应用于统计学与机器学习领域，因其简单、可并行化、可解释性强而深受工业界喜爱。下面简要对逻辑回归学习做些许介绍，具体可参考上述链接。

    关于逻辑回归的Python实现您可以参考此blog: Logistic Regression in Practice

    回顾下之前的线性模型，在线性模型中，我们对每个特征附上权重，与输入相乘相加后的到一个新的值，我们使用这个值来对输入进行划分。而在树模型中，我们需要对特征一个一个处理。决策树与逻辑回归的分类区别也如此，逻辑回归是将所有特征变化为概率，大于某一阈值的划分一类；决策树是对每个特征做一个划分。

2.1 决策树算法

• Decision Trees in Machine Learning
• 决策树算法--CART分类树算法
• 决策树算法--CART回归树算法
• 数据挖掘十大经典算法--CART: 分类与回归树

2.1.1 从一个例子出发

    假设我们想得到一个模型，用于预测在一场事故中，什么样的乘客可以生还。数据使用3个特征来表示：性别、年龄和配偶+孩子的数量。
    我们最终得到如下的一个树结构：

    其中，黑色粗体为节点，代表一种情况，最上方的节点为根节点；每个节点将树分为不同的分支（branches），当节点不再可分时，即在branch的末尾，为叶子，图中以红色和绿色表示。

    从这么一个决策树来看，乘客是否能生还是非常清晰可见的，并且特征间的关系也清晰可见。那么如何从数据得出这么一个模型呢？一种方法为Classification Tree，其目标为将乘客分类成survived和died两种；另一种为Regression Tree，表示方法与CT相同，只是RT是用来预测连续值得，比如房价。

    构建决策树，我们需要知道每个节点该使用哪个特征，需要知道节点splitting时的条件，需要知道何时结束（得到叶子节点）。在算法中通常树是在随机生长的，故我们还需要知道如何修整它。

2.1.2 Recursive Binary Splitting

    最开始我们仅含一个根节点，并且所有的feature还没有分割开。我们有3个features，所以我们有3种可能使用的splits。一个最简单的方式为，计算每种方式的cost函数，选择最小的情况最为分割方式。在本例中我们选择sex作为根节点，随后的分割方法同样可以以这种方式进行。这种方法也被称为贪心算法。所以我们发现，在树模型中，最为关键的是如何评估每种splitting的开销（cost），我们将cost的评估方法统称为cost function。

2.2 CART

    参考资料：Classification and regression trees. Wei-Yin Loh. 2011

    本节将介绍一个经典的决策树算法，CART算法。CART全称为: Classification and regression trees，即分类回归树。首先，在上文中我们简单概述了树模型的一般流程，那么现在我们用数学上的定义来更加准确的定义所谓树模型。

    对于一次观测，随机变量Y={1,2,3,...,k}表示此次观测的结果（标签），使用p维随机变量X={X1,X2,...,Xp}表示观测对象（p个特征），我们需要找到一个模型f，使得Y=f(X)。树模型的思想是，我们可以找一种分类方式对X进行分割（partition），将其从一个p维随机变量分割成k个集合A1,A2,...,Ak，根据分割结果，若X∈Aj，则代表Y=j。我们可以使用树结构来代表这一过程，该树则被称为分类树（classification tree）。

    如Figure 1右，一个2维随机变量X被分割成两组（根据X2分割）X|X2≤0.7,X|X2>0.7，再根据X1，我们最终将X归类到A1,A2,A3三类。例如，当X=(1,0)时，根据分割结果，X∈A3，即绿色叶节点，故Y=3。注意，这里的分割并不指的是降维，而是根据某一个或者几个纬度Xi来对X进行分组，我们的目的是可以将X分至k个组，进而得到对Y的预测结果。

    下面我们来介绍CART算法，该算法用来指导如何对一个节点进行split。首先我们从上面对树模型的定义可以发现，split的作用是，将预测结果Y相同的X分成同一组，也就是说，split后的X之间应该更相似，或者说更纯（pure）。CART使用基尼系数Gini来表示数据集D的纯度，其公式为：
    G∈i(D)=k∑i=1p(yi)⋅(1-p(yi))
    其中p(yi)代表在D这一分组中，yi这一标签出现的概率，k代表总的标签种类个数。

    故在一次split中，尝试根据某一个特征xi进行划分，而后分别计算划分后的两组D的Gini指数。通过计算划分前和划分后的Gini增益，选择让Gini指数下降最大的一种split方式。

    最终，我们可以通过以上这种贪心的方法逐渐的减小Gini指数，也即划分出来的组越纯。在划分完后，还需使用剪枝的方法防止过拟合，在本文中将不再介绍。

    关于DNN基础，您可以参考https://zhuanlan.zhihu.com/p/29815081此文章，在本节笔者将以此文章为基础，介绍如何进行分布式的DNN训练。

    DNN中一次迭代的步骤可以如下表示：

--------------------------------
# 前向传播
for l = 2 to L:
    # l: 第l层; W^l,b^l: 第l层的权重和偏转, σ: 激活函数
    计算al=σ(Wlal-1+bl)
计算输出层的δL
# 反向传播
for l = L to 2:
    # zl: 第l层激活函数的输入
    计算δl=(Wl+1)Tδl+1⊙σ′(zl)
# 更新W和b
for l = 2 to b:
    Wl=Wl-αm∑i=1{δl(al-1)T}
    bl=bl-αm∑i=1δl
--------------------------------

    从上述步骤可以看到，当第k此迭代时，al,k,zl,k的计算需要第k-1次迭代时的Wl,k-1，也即需要δl,k-1来更新W；同时层与层之间的计算也具有联系，即计算l层需要l-1层的结果。故可以说DNN的训练过程是复杂的，针对复杂计算的并行化可以考虑分布式的执行function，如下图：

    如若使用PS架构，可以构建上述Task Dependencies，使workers可以分布式的执行前向传播和反向传播过程，中间变量由parameter servers维护。如此，每个worker预先拷贝好其需要的数据集，再依照Task Dependencies执行即可。

    关于此节内容，您可以参考此blog：Overview of Federated Learning

    关于heterogeneous federated logistic regression，在Heterologous Logistic Regression中笔者对其进行了系统解读。以下内容则是对该博客的补充。

    那么一次Hetero-LR过程可以概括为：

    其中，[[·]]代表使用同态加密方法加密数据。

    参考资料：SecureBoost: A Lossless Federated Learning Framework. 2021. IEEE Intelligent Systems

Problem Statement

    设{Xk∈Rnk×dk}mk=1，Xk代表数据集，其分布在m个parties中。对于一个party，数据集X1有d1个features，其feature set使用F1={f1,.,fd1}表示。对于任意两个parties p,q，Fp∩Fq=o。仅有一个party持有标签Y。

    首先，简单提一下XGBoost过程，如下：

    l为损失函数，这里我们可以简单的使用平方损失函数l(yi,^yi=(yi-^yi)2)，Ω代表正则项。对XGBoost更深的理解请参考另一博文终于有人说清楚了--XGBoost算法

    在第t次迭代时，最小化(3)式来进行split。在得到最优的树后，计算每个叶子结点的权重。我们发现，上述两步计算都依赖于gi,hi，并且根据这两个参数，还可以得出class label。例如，gi=^yit-1-yi。

    于是我们可以得出：(a) 未持有标签的参与方可以根据本地数据和gi,hi计算出本地最佳split。 (b) gi,hi应该被认为是敏感数据，也即不同party间应该交互的是加密后的gi,hi。在一次split中，和XGBoost一样，需要对于每一个可能的feature分割点进行穷举，并对每次分割使用(3)式打分，使(3)式最低的可以认为是最佳分割点。我们发现，(3)式的计算是需要知道∑gi,∑hi的，于是现在问题变为，当各个party持有不同feature，并只有active party持有label时该如何计算∑gi,∑hi。

    首先，论文中使用了approximation scheme用于减少参与方交互gi,hi的次数，其各参与方计算梯度的过程如下：

    每个passive party使用local data计算完G,H矩阵后将其发送给active party，注意这里两个矩阵中的值都已经经历过同态加密，故不会有信息泄露。在active party中经历如下过程：

    该过程即active party计算自身的gradient，而后将其加入进G,H矩阵中，再使用矩阵中的值计算最终的score。通过score，active party得到了最佳的feature分割点kopt和最佳阈值vopt。当然还有一个问题，我们发现对于passive party而言，是需要输入由active party计算好的gi,hi的，那么active party当然也得先有^yi，所以最后一块拼图为，如何得到^yi？

    对于一条record x1，我们需要得到其预测值^y1。于是从root node开始一步一步的进行判断，root node中需要根据passive party 1中的feature Bill Payment进行判决，故active party通知party 1；party 1发现x1被划分到node 1，故与party 3进行交互，让party 3进行下一步。最终我们得到x1的预测值为w2，并传递给所有参与方。于是，active party可以计算出gi,hi并传递给各个passive party，再进行上述的G,H和score计算过程。