一些差分隐私的代码练习

计算平均数

我们假设有一个数据集，里面是1000个人的身高数据，我们想得到这个数据集的平均身高

我们使用 numpy 库来获取随机的拉普拉斯噪声，函数如下：

import numpy as np

def laplace(scale):
    """ 随机拉普拉斯噪声 """
    return np.random.laplace(loc=0, scale=scale)

简单应用拉普拉斯机制（顺序组成）

由顺序组成性质我们可以有如下方法：

def laplace_mechanism_composition(d: List[float], epsilon: float, a_max: float, a_min: float) -> float:
    """ s, c 符合 epsilon / 2 - DP, (s / c) 符合 epsilon - DP """
    s = sum(d) + laplace(2 * (a_max - a_min) / epsilon)
    c = len(d) + laplace(2 / epsilon)
    if c <= 1:
        return (a_max + a_min) / 2
    return round(s / c, 2)

一种使用真实计数的非隐私方法

这种方法使用了真实的数据集计数，但是因为其在重采样过程中对其他值的输出概率有着放大的作用，最终导致其不满足 $ \epsilon - DP $，同时，这种方法也引入了一种名为 clamping down 的方法来将输出限制在一个范围内

def non_private_with_true_count(d: List[float], epsilon: float, a_max: float, a_min: float) -> float:
    """
    只在数据和上添加拉普拉斯噪声，对不在 [a_min, a_max] 范围内的值进行重采样以保证输出固定在此范围内
    但是重采样的过程对其他值有着放大输出概率的作用，所以不满足 epsilon - DP
    """
    s = sum(d)
    c = len(d)
    if c == 0:
        return random.uniform(a_min, a_max)
    a = (s + laplace((a_max - a_min) / epsilon)) / c
    while a < a_min or a > a_max:
        a = (s + laplace((a_max - a_min) / epsilon)) / c
    return round(a, 2)

一种使用了真实计数和 clamping down 的隐私方法

不同于上一个方法，本方法采用了不同的 clamping down 策略，即

$$
\begin{equation}
\label{eq6}
\prod_\nolimits{[a_{min},a_{max}]}(y)=\left\{
\begin{aligned}
& a_{min}, & y < a_{min}\\
& y, & a_{min} \leq y \leq a_{max} \\
& a_{max}, & y > a_{max}
\end{aligned}
\right.
\end{equation}
$$

并且在数据集为空时应用指数机制，输出概率如下：

$$
\begin{equation}
\label{eq7}
output=\left\{
\begin{aligned}
& Pr[a_{min}] & = & \frac{1}{2}exp(-\frac{\epsilon}{2}) \\
& Pr[uniform(a_{min}, a_{max})] & = & 1 - exp(-\frac{\epsilon}{2}) \\
& Pr[a_{max}] & = & \frac{1}{2}exp(-\frac{\epsilon}{2})
\end{aligned}
\right.
\end{equation}
$$

代码如下

def clamping_down_with_true_count(d: List[float], epsilon: float, a_max: float, a_min: float) -> float:
    """
    不同于 non_private_with_true_count，采用了不同的 clamping down 策略，
    即 when a < a_min, return a_min; when a > a_max, return a_max; else, return a
    可以保证 epsilon - DP
    """
    s = sum(d)
    c = len(d)
    if c == 0:
        return round(
            np.random.choice(
                [a_min, random.uniform(a_min, a_max), a_max], 1,
                p=[1 / 2 * (np.e ** (- epsilon / 2)), 1 - np.e ** (- epsilon / 2), 1 / 2 * (np.e ** (- epsilon / 2))]
            )[0], 2
        )
    a = (s + laplace((a_max - a_min) / epsilon)) / c
    if a < a_min:
        return a_min
    elif a > a_max:
        return a_max
    return round(a, 2)

使用归一化处理

对数据总和进行归一化处理，可以将全局敏感度从 $ a_max - a_min $ 降低到 $ \delta_a / 2 $

def noisy_average_with_normalization(d: List[float], epsilon: float, a_max: float, a_min: float) -> float:
    """ 对s进行归一化处理，可以将全局敏感度从 a_max - a_min 降低到 delta_a / 2 """
    s = sum(d) - len(d) * ((a_max + a_min) / 2) + laplace(2 * (a_max - a_min) / epsilon)
    c = len(d) + laplace(2 / epsilon)
    if c <= 1:
        return (a_max + a_min) / 2
    return round(s / c + (a_min + a_max) / 2, 2)

总结

经实际证明，[一种使用了真实计数和 clamping down 的隐私方法]()比[使用归一化处理]()表现更好，当 $ \epsilon $ 较大时它们表现相近，当 $ \epsilon $ 较小时前者的优势更为突出