Some Classifiers with MPC
Published:
安全多方计算下机器学习分类器的讨论
机器学习在分类任务中有很好的表现，不同的分类器在特定的分类任务中的表现具有不同的应用。有五个经典的机器学习任务，包括GMM、随机森林、SVM、XGBoost和朴素贝叶斯。基于不同的数据集，也有不同的分类任务，不同的分类器表现相似。
GMM Classifier
高斯混合分类模型描述了多个高斯成分密度的加权和，其加权和由一个参数化的概率密度函数表示。每一个高斯模型代表一个类，样本数据分别成为几个高斯模型上的投影，并表出每个分类上出现概率，择取概率最大的类为结果。$M$是混合模型的数量，$w^n_i$是混合权重满足$\sum^M_{i=1}w^n_i = 1$可以描述为
\[\begin{align*} p(\vec{x} \vert \lambda_n ) = \sum\nolimits^M_{i=1}w^n_i p^n_i(\vec{x}) \end{align*}\]SVM Classifier
基本的SVM模型是一个二元分类器，学习函数的输出的正负形式对高维数据进行分类。SVM通过数据进行一系列的变换找出最佳边界条件。
\[\begin{align*} minimize: \, Q(w) = \frac{1}{2} \Vert w \Vert^2 \\ s.t. \quad \forall (x_i, y_i) \in D \; y_i(w \cdot x_i -b) \geq q \end{align*}\]随机森林
由多个决策树组成，决策树从输入向量单独采样的随机向量。随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树。
XGBoost分类器
极限梯度提升算法，提升了树突破自身的计算极限，实现运算快速，性能优秀的工程目标。和传统的梯度提升算法相比，XGBoost进行了许多改进，并且已经被认为是在分类和回归上都拥有超高性能的先进评估器。
\[\begin{align*} y^{(t)}_i = \sum \nolimits ^t_{k=1}f_k(x_i) = y^{(t-1)}_i + f_t(x_i) \end{align*}\]朴素贝叶斯分类器
朴素贝叶斯网络是有向无环图行成的初级贝叶斯网络，包含已观测和未观测的节点，两种节点假设是相对独立的。
\[\begin{align*} \Pr(c \vert x) = \frac{\Pr(x \vert c) \cdot \Pr(c)}{\Pr(x)} \end{align*}\]对于贝叶斯公式来说：$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)$保持不变，因此为方便可以把公式写成如下\(\Pr(c \vert x) = \Pr(x \vert c) \cdot \Pr(c)\)。若假设相互独立的样本特征为$x = (x_1, \dots, x_d)$，则贝叶斯公式写成\(\Pr(c \vert x) = \Pr(c) \prod \nolimits ^d _{k=1}\Pr(x_k \vert c)\)。 在贝叶斯分类器中，计算时概率的数字通常都是极小的小数，而他们相乘之后的积会更小，这在计算机实现中会导致堆栈下溢，从而模型不准确。因此，这就需要把所有的乘法用对数转换成为加法运算，即：
\[\begin{align*} \log(\Pr(c \vert x)) &= \log(\Pr(c) \prod^d_{k=1}\Pr(x_k \vert c)) \\ &= \log(\Pr(c)) + \sum^d_{k=1}\log(\Pr(x_k \vert c)) \end{align*}\]要执行分类算法，就要计算最大的值。朴素贝叶斯分类器的不同之处在于对$\Pr(x \vert c)$的假设。在高斯朴素贝叶斯中，每个类别相关连续值都按照高斯分布。而对于离散的情况来说，则需要使用伯努利朴素贝叶斯或多项式朴素贝叶斯，前者的特征向量由布尔值表示，其中1代表出现，0代表未出现，后者中向量表示样本特征在样本中出现的频率。不同的场景采用不同的贝叶斯方案。这里概率$\Pr(x_k \vert x)$是一个单调递增的函数，而$\log(\Pr(x_k \vert x))$同样也是单增的，故求\(\prod^d_{k=1}\Pr(x_k \vert c)\)最大，亦是求\(\sum^d_{k=1}\log(\Pr(x_k \vert c)\)最大。
\[\begin{align*} \hat{c} = \mathsf{argmax}_c[\log \Pr(c) + \sum^d_{k=1} \log (\Pr(x_k \vert c))] \end{align*}\]显然根据朴素贝叶斯的计算特点，三方计算中的加法秘密共享、浮点数计算、位提取和安全比较也是相对应和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在本地计算\([\![r_i ]\!]_2 \leftarrow [\![x_i ]\!]_2 + [\![y_i ]\!]_2 + 1\)
- Alice和Bob用安全乘法计算一个$z = r_1 \cdot {\dots} \cdot r_\ell$的秘密共享，然后输出共享\([\![z ]\!]_2\)，在第$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 ]\!]_2\)转换成\(\mathbb{Z}_q\)上的十进制秘密共享\([\![ x ]\!]_q\)。
- \([\![ x ]\!]_2\)，令$x_A \in {0, 1}$是Alice的共享，$x_B \in {0, 1}$是Bob的共享。
- 定义\([\![ x_A ]\!]_q\)作为共享$(x_A, 0)$，定义\([\![ x_B ]\!]_q\)作为共享$(0, x_B)$。
- Alice和Bob计算\([\![ y ]\!]_q \leftarrow [\![ x_A ]\!]_q[\![ x_B ]\!]_q\)
- 输出\([\![ z ]\!]_q \leftarrow [\![ x_A ]\!]_q + [\![ x_B ]\!]_q - 2[\![ y ]\!]_q\)
- 上面协议通过1轮通信和总共$2\lambda$比特的数据传输，其中$\lambda$是$q$的比特长度，若是分批输入，则需按照批次相乘。
安全位提取
位提取协议接受一个秘密值\([\![ x ]\!]_q\)，和一个公开的已知的位置$\alpha$，返回一个$x$的第$\alpha$位的\(\mathbb{Z}_2\)共享\([\![ (x \gg (\alpha - 1)) \land 1 ]\!]_2\)
- 对于一个秘密共享值\([\![ x ]\!]_q = (x_A, x_B)\)，使得$x = x_A +x_B \mod q$，Alice和Bob在本地创建传播信号的比特位共享，\(p^{(\alpha)} \leftarrow x^{(\alpha)}_A \oplus x^{(\alpha)}_B, \cdots, p^{(1)} \leftarrow x^{(1)}_A \oplus x^{(1)}_B\)
- Alice和Bob利用安全乘法协议共同计算生成信号\(g^{(\alpha)} \leftarrow x^{(\alpha)}_A \land x^{(\alpha)}_B, \cdots, g^{(1)} \leftarrow x^{(1)}_A \land x^{(1)}_B\)
Alice和Bob共同计算第$(\alpha -1)$个进位比特计算 \(\prod_{1 \le i \le \alpha -1} \begin{bmatrix} [\![ p^{(i)} ]\!]_2 & [\![ g^{(i)} ]\!]_2 \\ 0 & 1 \end{bmatrix}\)
- Alice和Bob在本地计算\([\![ x^{(\alpha)} ]\!]_2 \leftarrow [\![ p^{(\alpha)} ]\!]_2 \oplus [\![ c^{(\alpha - 1)} ]\!]_2\)
协议在矩阵组合之前需要一轮通信和$2 \alpha$比特的数据传输。矩阵组合可以通过计算所有的矩阵成对组合进行，需要通过\(\lceil \log (\alpha -a) \rceil\)轮通信，每一次矩阵乘法的总数据传输为4比特。
安全比较
对秘密共享整数进行安全比较，Alice和Bob输入\(\mathbb{Z}_q\)中的整数$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$该协议在\(\mathbb{Z}_2\)返回$1$的秘密共享，否则返回$0$的秘密共享。
- Alice和Bob本地计算$x$和$y$的差值为\([\![ \mathsf{diff} ]\!]_q \leftarrow [\![ x ]\!]_q - [\![ y ]\!]_q\)，若$y > x$，则差值事负数
- Alice和Bob提取\(\mathsf{diff}\)的最高有效位MSB的\(\mathbb{Z}_2\)共享 \([\![ MSB ]\!]_2\)，利用位提取协议
- 若\(\mathbb{Z}_q\)秘密共享的MSB是1，其值为负。即\([\![ z ]\!]_2 \leftarrow 1 + [\![ MSB ]\!]_2\)，负数的MSB是1当前仅当$x \ge y $。
- 此协议共需要\(\lceil \log(\lambda -1) + 1 \rceil\)轮通信和总共\(4\lambda + 4 \log(\lambda -1)-6\)比特的数据传输，这里$\lambda$是$q$的比特长度。
用以上技术设计三方的贝叶斯分类器。三方并不是地位相等的，一方是可信中心，另外两方交互模型参数，进行联合训练。可信第三方会发送安全的三元组，另外两方利用以上协议进行点积、比较和乘法计算。一下通过比较几种安全比较、位提取和B2A协议。