Some Classifiers with MPC

安全多方计算下机器学习分类器的讨论

机器学习在分类任务中有很好的表现，不同的分类器在特定的分类任务中的表现具有不同的应用。有五个经典的机器学习任务，包括GMM、随机森林、SVM、XGBoost和朴素贝叶斯。基于不同的数据集，也有不同的分类任务，不同的分类器表现相似。

GMM Classifier

高斯混合分类模型描述了多个高斯成分密度的加权和，其加权和由一个参数化的概率密度函数表示。每一个高斯模型代表一个类，样本数据分别成为几个高斯模型上的投影，并表出每个分类上出现概率，择取概率最大的类为结果。M是混合模型的数量，wni是混合权重满足∑Mi=1wni=1可以描述为

SVM Classifier

基本的SVM模型是一个二元分类器，学习函数的输出的正负形式对高维数据进行分类。SVM通过数据进行一系列的变换找出最佳边界条件。

随机森林

由多个决策树组成，决策树从输入向量单独采样的随机向量。随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树。

XGBoost分类器

极限梯度提升算法，提升了树突破自身的计算极限，实现运算快速，性能优秀的工程目标。和传统的梯度提升算法相比，XGBoost进行了许多改进，并且已经被认为是在分类和回归上都拥有超高性能的先进评估器。

朴素贝叶斯分类器

朴素贝叶斯网络是有向无环图行成的初级贝叶斯网络，包含已观测和未观测的节点，两种节点假设是相对独立的。

对于贝叶斯公式来说：c表示分类；x是测试样本的特征向量；Pr(c|x)是后验概率，即给定测试样本向量x，它属于类别c的概率；同理Pr(x|c)是条件概率，给定一个类别c，样本x属于类别c的概率，Pr(c)是前验概率；Pr(x)是预测的后验概率。预测概率Pr(x)是一个归一化常数，这使得Pr(c|x)的值落在区间[0,1]的范围内。实际方案中，需要比较不同类别的概率，用来确定样本的最大概率。故概率本身不重要，拿它们进行比较值才有意义。由于分母Pr(x)保持不变，因此为方便可以把公式写成如下Pr(c|x)=Pr(x|c)⋅Pr(c)。若假设相互独立的样本特征为x=(x1,…,xd)，则贝叶斯公式写成Pr(c|x)=Pr(c)∏dk=1Pr(xk|c)。 在贝叶斯分类器中，计算时概率的数字通常都是极小的小数，而他们相乘之后的积会更小，这在计算机实现中会导致堆栈下溢，从而模型不准确。因此，这就需要把所有的乘法用对数转换成为加法运算，即：

要执行分类算法，就要计算最大的值。朴素贝叶斯分类器的不同之处在于对Pr(x|c)的假设。在高斯朴素贝叶斯中，每个类别相关连续值都按照高斯分布。而对于离散的情况来说，则需要使用伯努利朴素贝叶斯或多项式朴素贝叶斯，前者的特征向量由布尔值表示，其中1代表出现，0代表未出现，后者中向量表示样本特征在样本中出现的频率。不同的场景采用不同的贝叶斯方案。这里概率Pr(xk|x)是一个单调递增的函数，而log(Pr(xk|x))同样也是单增的，故求∏dk=1Pr(xk|c)最大，亦是求∑dk=1log(Pr(xk|c)最大。

显然根据朴素贝叶斯的计算特点，三方计算中的加法秘密共享、浮点数计算、位提取和安全比较也是相对应和ABY3，BLAZE方案略有不同。

安全等式比较

两方Alice和Bob分别持有比特串X=xℓ,…,x1和Y=yℓ,…,y1。若X=Y，则该协议产生1的秘密共享，否则输出0的秘密共享

• 对i=1,…,ℓ，Alice和Bob在本地计算[[ri]]2←[[xi]]2+[[yi]]2+1
• Alice和Bob用安全乘法计算一个z=r1⋅…⋅rℓ的秘密共享，然后输出共享[[z]]2，在第i个位置上，若x=y，则所有的i个位置ri=1，因此z=1。否则若一些ri=0，则z=0。
• 通过执行乘法，以树的形式计算z，其值放在r1,…,rℓ的ℓ个叶子中。总共通信⌈log(ℓ)⌉轮，传输∑⌈log(ℓ)⌉i=1⌈ℓ/2i=1⌉比特数据转换。对于分批输入X1,…,Xk,Y1,…,Yk，通信轮数保持不变，每轮通信数据传输按照k的比例计算。

B2A

在每一个机器学习的隐私保护框架中，从二进制向十进制的转换，都是极其很重要的步骤，重SecureML，ABY3和BLAZE等方案，都有关于自己B2A的方案设计。在不泄漏x的任何信息的条件下，Alice和Bob输入一个二进制秘密共享[[x]]2转换成Zq上的十进制秘密共享[[x]]q。

• [[x]]2，令xA∈0,1是Alice的共享，xB∈0,1是Bob的共享。
• 定义[[xA]]q作为共享(xA,0)，定义[[xB]]q作为共享(0,xB)。
• Alice和Bob计算[[y]]q←[[xA]]q[[xB]]q
• 输出[[z]]q←[[xA]]q+[[xB]]q−2[[y]]q
• 上面协议通过1轮通信和总共2λ比特的数据传输，其中λ是q的比特长度，若是分批输入，则需按照批次相乘。

安全位提取

位提取协议接受一个秘密值[[x]]q，和一个公开的已知的位置α，返回一个x的第α位的Z2共享[[(x≫(α−1))∧1]]2

• 对于一个秘密共享值[[x]]q=(xA,xB)，使得x=xA+xBmodq，Alice和Bob在本地创建传播信号的比特位共享，p(α)←x(α)A⊕x(α)B,⋯,p(1)←x(1)A⊕x(1)B
• Alice和Bob利用安全乘法协议共同计算生成信号g(α)←x(α)A∧x(α)B,⋯,g(1)←x(1)A∧x(1)B

• Alice和Bob共同计算第(α−1)个进位比特计算 ∏1≤i≤α−1[[[p(i)]]2[[g(i)]]201]

• Alice和Bob在本地计算[[x(α)]]2←[[p(α)]]2⊕[[c(α−1)]]2

协议在矩阵组合之前需要一轮通信和2α比特的数据传输。矩阵组合可以通过计算所有的矩阵成对组合进行，需要通过⌈log(α−a)⌉轮通信，每一次矩阵乘法的总数据传输为4比特。

安全比较

对秘密共享整数进行安全比较，Alice和Bob输入Zq中的整数x和y的秘密共享，使得|x−y|<2λ−1。Alice和Bob可以用整数x和y的在区间[−2λ−2,2λ−2−1]执行协议，若为负值u表示为2λ−|u|。若x≥y该协议在Z2返回1的秘密共享，否则返回0的秘密共享。

• Alice和Bob本地计算x和y的差值为[[diff]]q←[[x]]q−[[y]]q，若y>x，则差值事负数
• Alice和Bob提取diff的最高有效位MSB的Z2共享 [[MSB]]2，利用位提取协议
• 若Zq秘密共享的MSB是1，其值为负。即[[z]]2←1+[[MSB]]2，负数的MSB是1当前仅当x≥y。
• 此协议共需要⌈log(λ−1)+1⌉轮通信和总共4λ+4log(λ−1)−6比特的数据传输，这里λ是q的比特长度。

用以上技术设计三方的贝叶斯分类器。三方并不是地位相等的，一方是可信中心，另外两方交互模型参数，进行联合训练。可信第三方会发送安全的三元组，另外两方利用以上协议进行点积、比较和乘法计算。一下通过比较几种安全比较、位提取和B2A协议。