Kun Liu

Kun Liu

CS & Applied Math & MPC @ GZU | Phd

Some Classifiers with MPC

less than 1 minute read

Published:

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

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

GMM Classifier

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

SVM Classifier

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

随机森林

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

XGBoost分类器

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

朴素贝叶斯分类器

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

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

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

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

安全等式比较

两方Alice和Bob分别持有比特串$X = {x_\ell, \dots, x_1 }$和$Y = {y_\ell, \dots, y_1 }$。若$X=Y$，则该协议产生1的秘密共享，否则输出0的秘密共享

  • 对$i = 1, \dots, \ell$，Alice和Bob在本地计算
  • Alice和Bob用安全乘法计算一个$z = r_1 \cdot {\dots} \cdot r_\ell$的秘密共享，然后输出共享，在第$i$个位置上，若$x=y$，则所有的$i$个位置$r_i = 1$，因此$z=1$。否则若一些$r_i = 0$，则$z = 0$。
  • 通过执行乘法，以树的形式计算$z$，其值放在$r_1, \dots, r_\ell$的$\ell$个叶子中。总共通信$ \lceil \log(\ell) \rceil $轮，传输$ \sum^{\lceil \log(\ell) \rceil}_{i=1}\lceil \ell / 2^{i=1} \rceil$比特数据转换。对于分批输入${X_1, \dots, X_k}, {Y_1, \dots, Y_k}$，通信轮数保持不变，每轮通信数据传输按照$k$的比例计算。

B2A

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

  • ，令$x_A \in {0, 1}$是Alice的共享，$x_B \in {0, 1}$是Bob的共享。
  • 定义作为共享$(x_A, 0)$，定义作为共享$(0, x_B)$。
  • Alice和Bob计算
  • 输出
  • 上面协议通过1轮通信和总共$2\lambda$比特的数据传输，其中$\lambda$是$q$的比特长度，若是分批输入，则需按照批次相乘。

安全位提取

位提取协议接受一个秘密值，和一个公开的已知的位置$\alpha$，返回一个$x$的第$\alpha$位的共享

  • 对于一个秘密共享值，使得$x = x_A +x_B \mod q$，Alice和Bob在本地创建传播信号的比特位共享，
  • Alice和Bob利用安全乘法协议共同计算生成信号

  • Alice和Bob共同计算第$(\alpha -1)$个进位比特计算

  • Alice和Bob在本地计算

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

安全比较

对秘密共享整数进行安全比较，Alice和Bob输入中的整数$x$和$y$的秘密共享，使得$\vert x -y \vert < 2^{\lambda -1}$。Alice和Bob可以用整数$x$和$y$的在区间$[-2^{\lambda -2}, 2^{\lambda -2}-1]$执行协议，若为负值$u$表示为$2^\lambda - \vert u \vert $。若$x \ge y$该协议在返回$1$的秘密共享，否则返回$0$的秘密共享。

  • Alice和Bob本地计算$x$和$y$的差值为，若$y > x$，则差值事负数
  • Alice和Bob提取的最高有效位MSB的共享 ，利用位提取协议
  • 若秘密共享的MSB是1，其值为负。即，负数的MSB是1当前仅当$x \ge y $。
  • 此协议共需要轮通信和总共比特的数据传输，这里$\lambda$是$q$的比特长度。

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

You May Also Enjoy