指数机制

问题引出

在Laplace机制中，我们首先对数据库进行查询，然后再查询结果之上添加一定的噪声使其满足DP的要求。因此，返回的数据通常只是“接近准确”的。那么差分隐私能否允许我们得到真实的结果呢？在这种情况下，指数机制应运而生。
指数机制（The exponential mechanism）是为我们希望选择“最佳”响应的情况而设计的，但直接在计算数量上添加噪声可以完全破坏其价值。

变量说明

可用性函数

设查询函数的输出域为 $R$ ，域中每个值 $r \in R$ 为一实体对象， $X$ 为给点的数据集。在指数机制下，函数 $q(X,r) \rightarrow R$ 称为输出值 $r$ 的可用性函数。
指数机制的敏感度
$\Delta q = \max_{x,x'}||q(x,r)-q'(x',r)||$

则：
$\frac{q(x,r)-q'(x',r)}{\Delta q} \leqslant \frac{|q(x,r)-q'(x',r)|}{\Delta q} \leqslant 1$

结论

指数机制 $\varepsilon$ -差分隐私

选择一个查询 $q$ ，给定分值函数（Score function)（比如给数据打分投票，分越高，表示这个数据越重要）。指数机制以 $M(x,q,r)$ 的概率输出结果 $r$ 。

则，指数分布 $E(\frac {\varepsilon}{2 \Delta q})$ 满足 $\varepsilon$ -差分隐私。

另一种说法：

给定数据集 $D$ 及可用性函数 $q(D,r) \rightarrow R$ ，隐私保护机制 $M$ 满足 $\varepsilon$ -差分隐私，当且仅当下述表达式成立：
$M(D,q)\propto e^{\frac{\varepsilon * q(D,r)}{2\Delta q}}$
指数分布（Exponential Distribution，补充）

指数分布的概率密度函数如下：
$f(x)=\begin{cases} \lambda e^{- \lambda x},x>0 \\ 0,x \leqslant0 \end{cases}$

记为： $X \sim E(\lambda)$ 。

证明

因为结果是以概率输出结果，不是直接对数值数据进行加噪，因此需要归一化以概率表示：
$\frac{P[M_E(x,q,R)=r]}{P[M_E(x',q,R)=r]}=\frac{(\frac{e^{\frac{\varepsilon*q(x,r)}{2 \Delta q}}}{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}})}{(\frac{e^{\frac{\varepsilon*q(x,r)}{2 \Delta q}}}{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x',r_i)}{2 \Delta q}}})}\\=\frac{e^{\frac{\varepsilon * q(x,r)}{2 \Delta q}}}{e^{\frac{\varepsilon * q(x',r)}{2 \Delta q}}}*\frac{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x',r_i)}{2 \Delta q}}}{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}}$

第一个因子，可整理为如下形式：
$\frac{e^{\frac{\varepsilon * q(x,r)}{2 \Delta q}}}{e^{\frac{\varepsilon * q(x',r)}{2 \Delta q}}}=e^{\frac{\varepsilon}{2} * \frac{(q(x,r)-q(x',r))}{\Delta q}}\leqslant e^{\frac{\varepsilon}{2}*{1}}=e^{\frac{\varepsilon}{2}}$
第二个因子，可整理为如下形式，（变形技巧来了，）：
$\frac{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x',r_i)}{2 \Delta q}}}{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}}=\frac{\displaystyle \sum_{r_i \in R} (e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}*e^{\frac{\varepsilon * (q(x',r_i)-q(x,r_i))}{2 \Delta q}})}{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}}$

$\because e^{\frac{\varepsilon * (q(x',r_i)-q(x,r_i))}{2 \Delta q}} \leqslant e^{\frac{\varepsilon}{2}}$

$\therefore {\displaystyle \sum_{r_i \in R} (e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}*e^{\frac{\varepsilon * (q(x',r_i)-q(x,r_i))}{2 \Delta q}})} \leqslant e^{\frac{\varepsilon}{2}}*{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}}$

$\therefore\frac{\displaystyle \sum_{r_i \in R} (e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}*e^{\frac{\varepsilon * (q(x',r_i)-q(x,r_i))}{2 \Delta q}})}{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}} \leqslant e^{\frac{\varepsilon}{2}}*\frac{{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}}}{\displaystyle \sum_{r_i \in R} e^{\frac{\varepsilon * q(x,r_i)}{2 \Delta q}}}=e^{\frac{\varepsilon}{2} *1}=e^{\frac{\varepsilon}{2}}$

综上：
$\frac{P[M_E(x,q,R)=r]}{P[M_E(x',q,R)=r]} \leqslant e^{\frac{\varepsilon}{2}} *e^{\frac{\varepsilon}{2}}=e ^ \varepsilon$
所以， $E(\frac{\varepsilon}{2 \Delta q})$ 满足 $\varepsilon$ -差分隐私。