基于隐私算法的学生作弊分析

二项分布

在开始介绍隐私算法之前，让我们先学习一下，本实验将会用到分布函数：二项分布。

二项分布是一种应用非常广泛的分布，这归功于它的简单和实用。和之前介绍的分布不同的是，它存在两个参数。
N ：代表试验次数或潜在事件发生数。
p ：代表一次实验中一种事件发生的概率。

跟 Poisson 分布类似，二项分布是一个离散分布。但不同的是，它只对 0 到 N 的整数设置概率，而 Poisson 分布可以对 0 到无穷的任意整数设置概率。

image.png

二项分布的期望取值等于N∗p。接下来，我们使用 PyMC 来展示它的概率分布。

import scipy.stats as stats
import numpy as np
from IPython.core.pylabtools import figsize
import matplotlib.pyplot as plt
%matplotlib inline
figsize(12.5, 4)
binomial = stats.binom

# 定义了两组参数
parameters = [(10, .4), (10, .9)]
colors = ["#348ABD", "#A60628"]

# 对这两组二项随机变量进行画图
for i in range(2):
    N, p = parameters[i]
    _x = np.arange(N + 1)
    plt.bar(_x - 0.5, binomial.pmf(_x, N, p), color=colors[i],
            edgecolor=colors[i],
            alpha=0.6,
            label="$N$: %d, $p$: %.1f" % (N, p),
            linewidth=3)

plt.legend(loc="upper left")
plt.xlim(0, 10.5)
plt.xlabel("$k$")
plt.ylabel("$P(X = k)$")
plt.title("Probability mass distributions of binomial random variables")

如上图，分别画出了（N,p）=(10,0.4) 和(N,p)=(10,0.9) 的二项分布

学生作弊实例

接下来，让我们利用二项分布来获取某次考试中，学生们作弊的比例。如果用 NN 表示参加这次考试的学生数，并假设同学都是在考试结束后接受的采访（无论回答是或者否，都不会承受任何后果）。我们把回答为，“是的，我作弊了”的答案的数量记作为 X。把学生的真实作弊比例记作 p。
我们需要做的事就是，给定 N、p 的先验分布和观察数据 X ，用贝叶斯推断出 p 的后验分布。
这是个非常荒唐的实验，我想，就算没有任何惩罚，也没有学生会承认自己作弊了。对于询问学生是否作弊，我们需要的是一个更好的算法。理想情况下，这种算法鼓励了参与者在保护隐私的情况下，说出实情。下面我们就来介绍一种很好的满足上面需求的算法：隐私算法。
隐私算法的概念
在采访每一个学生的过程中，学生需要先抛一枚硬币。对于硬币结果采访者是不知道的。学生答应，如果结果正面朝上的话，他就必须如实回答。如果结果反面朝上，学生需要再秘密地抛一次硬币。如果这一次，也是正面朝上，则回答：“是的，我作弊了”。如果反面朝上，则回答“不，我没有作弊”。当然上面整个过程中，采访者都不知道学生抛出的硬币是正面还是反面。这样，采访者就不知道“是的，我做作弊了”，是由于学生因为真的作弊了所说的话，还是由于第二次抛硬币的结果所造成的。
这样做，既保护了学生的隐私（因为你不知道每个学生到底是真作弊了还是由于硬币的随机性而说的“我作弊了”），又让研究者获得了真实的数据。
这就是隐私算法，研究者放弃了一半的数据（因为这一半数据是随机产生的），却获得了另一半的真实数据。
现在让我们使用 PyMC 来找出作弊概率的后验分布（即更加接近真实的概率）。
假设有 100 位学生参与了是否作弊的调查，我们希望找到一个概率值 p来描述作弊者的比例。在 PyMC 中，有很多种模拟方式，这里采取最能说明问题的一种，并在后面展示一个简单版。当然，这两个版本都能够得到相同的推论。
学生的真实作弊数据模拟
在模型开始时，我们对p是没有概念，因此，假设先验来自一个 (0,1) 上的均匀分布（在第一次加载模型时，可能需要1~2min，请耐心等待）。

import pymc3 as pm

N = 100
model = pm.Model()
with model:
    p = pm.Uniform("freq_cheating", 0, 1)
model

由于学生只会回答作弊或者不作弊，因此，对于学生的回答，我们完全可以使用上一个试验提到的伯努利分布来模拟。即输出 1 代表这个学生作弊，输出 0 代表这个学生没有作弊。

with model:
    true_answers = pm.Bernoulli(
        "truths", p, shape=N, testval=np.random.binomial(1, 0.5, N))
true_answers

好的现在，我们得到的是每个学生是否作弊的真实数据。接下来，我们就需要利用隐私算法对这些学生进行采访，得到他们对采访者的回答集合。
隐私算法的计算机仿真
我们的第一步就是让每位同学抛一次硬币。这又是一个以p= 1/2的伯努利随机变量抽样。其中 1 代表正面朝上，0 代表正面朝下。

with model:
    # 第一次投币的结果仿真
    first_coin_flips = pm.Bernoulli("first_flips", 0.5, shape=N,
                                    testval=np.random.binomial(1, 0.5, N))
print(first_coin_flips.tag.test_value)

虽然并不是每位同学都会抛第二次硬币，我们仍然可以先模拟出每个学生第二次抛硬币的结果。代码如下：

with model:
    second_coin_flips = pm.Bernoulli("second_flips", 0.5, shape=N,
                                     testval=np.random.binomial(1, 0.5, N))
print(second_coin_flips.tag.test_value)

接下来，我们通过这两次的投硬币结果来生成采访者得到的数据。

image.png

让我们用代码实现上面这些情况：

import theano.tensor as tt
with model:

    # 这个代码其实就是在求出每个同学给采访者的真实数据
    # first_coin_flips*true_answers：只有第一硬币，投掷为1的才能输出正确的值。其他输出的都为0
    # 1 - first_coin_flips 排除掉那些第一次为 正面朝上的同学
    #  *second_coin_flips 剩下的数据，根据第二次硬币的结果而发生变化
    val = first_coin_flips*true_answers + \
        (1 - first_coin_flips)*second_coin_flips

    # 下面代码，通过采访数据，求出观测出来的学生作弊率
    # 对所有的结果求和并除以N
    # 再将结果转为一个确定型函数(Deterministic)
    observed_proportion = pm.Deterministic(
        "observed_proportion", tt.sum(val)/float(N))
observed_proportion.tag.test_value

如上所示，我们设置了作弊率的先验概率，并且模拟隐私算法，得到了观测数据。由于采集数据时的随机性，我们直接用这个值来衡量整个班级的学生的作弊率是有问题的。
因此，我们需要用贝叶斯推断，对作弊率的后验概率进行推断。
作弊率推断：版本一
那么接下来，我们就需要将采访得到的数据与模型相结合。假设现在研究者们收到了35个“是的，我作弊了”的答案。（这个假设是合理的，我们可以取极限进行思考这个问题。当所有的学生都没有做过弊，那么由于第一次有 1/2 的概率反面，第二次有1/2的概率为正面，因此采访者会收到1/4 ×100=25 个“是的，我作弊了”的答案。同样，当所有的学生都作弊了话，我们会收到3/4 ×100=75 个“是的，我作弊了”的回答。）。
因此我们假设收到 35 个，回答为作弊的答案较为合理

image.png

# x 表示回答为“是的，我作弊了”的人数
X = 35
# N 表示采访的总人数
N = 100

with model:
    # 将采集到的数据 X 固定到模型中
    observations = pm.Binomial("obs", N, observed_proportion, observed=X)
observations.tag.test_value

接下来，就是模型的训练，下面代码，我们将在后面的实验进行学习。现在，你只需要记住，该段代码用于模型的训练（可能需要 2~3min）。

with model:
        step = pm.Metropolis(vars=[p])
        trace = pm.sample(1000, step=step)
        burned_trace = trace[150:]

最后，让我们展示一下真实作弊者的比例在贝叶斯推断下的后验分布图。

figsize(12.5, 3)
# 从训练好的模型中获得样本
p_trace = burned_trace["freq_cheating"][150:]
# 通过样本数据集画图
plt.hist(p_trace, histtype="stepfilled", normed=True, alpha=0.85, bins=30,
         label="posterior distribution", color="#348ABD")
plt.vlines([.05, .35], [0, 0], [5, 5], alpha=0.3)
plt.xlim(0, 1)
plt.legend()

由于线上资源有限，所以我们只生成了 1000 个样本。不过，我们也可以从上图中大致看出，作弊率为 0.2 左右的可能性较高。当然，由于生成的样本较少，因此可能结果存在一定的随机性。你可自行增加上上段代码段中所生成的数据集合个数，以提高精度。
推断作弊率：版本2
如果知道了真正作弊的人的比例，记作 pp ，我们就可以直接得到回答“是的，我作弊了”的人数比例。因此，我们可以把回答作弊了的人数作为一个确定型变量，而不是像上面一样，还进行两次投硬币的计算机仿真，导致后面的运行效率极低。让我们来定义 p 的先验概率，以及确定型变量 p_skewed (学生回答“是的，我作弊了”的概率)。

with pm.Model() as model:
    # 下面这些都还是变量，只有程序在运行时，才会赋予相应的值
    # 我们的模型最后就是需要给这些参数找到合适的值
    p = pm.Uniform("freq_cheating", 0, 1)
    p_skewed = pm.Deterministic("p_skewed", 0.5*p + 0.25)
p_skewed

将我们知道了回答“是的”的概率，记作 p_skewed，并且知道了 N = 100。那么回答“是的”的人数则为一个带有参数 N 和 p_skewed 的二项随机变量。
这里，我们还是假设采集到的数据中有 35 个同学回答了“是的，我作弊了”。因此在下面代码中，我们将通过采集得到的数据 35 和 参数为 (100，p_skewed) 的二项分布函数相结合来进行贝叶斯推断：

with model:
    # 即将真实数据 35  和分布函数相结合，得到每个人具体的1回答数据
    yes_responses = pm.Binomial("number_cheaters", 100, p_skewed, observed=35)
yes_responses

接下来，自然是按下模型的训练按钮。此时模型训练的目标，就是找到最佳的 p_skewed 使二项分布函数所生产的数据集中，回答“是的”的人数为 35 。在通过最佳的 p-skewed 推断出最佳的 p。

# 本段代码将在后面实验中讲解
with model:
    step = pm.Metropolis()
    trace = pm.sample(25000, step=step)
    burned_trace = trace[2500:]

最后，让我们再次画出本版本下的学生撒谎概率后验的分布函数：

figsize(12.5, 3)
p_trace = burned_trace["freq_cheating"]
plt.hist(p_trace, histtype="stepfilled", normed=True, alpha=0.85, bins=30,
         label="posterior distribution", color="#348ABD")
plt.vlines([.05, .35], [0, 0], [5, 5], alpha=0.2)
plt.xlim(0, 1)
plt.legend()

由于，本版本的运行效率较高。因此，我们生成了 25000 个样本用以训练，得到了上图这种比较精确的分布函数。