Private Sequential Learning 论文详解

本文介绍了一篇有趣的机器学习理论工作: Private Sequential Learning. 这篇文章在 Sequential Learning 中引入了隐私保护的目标, 从理论角度分析了该目标的可行性.

问题背景

有时我们想要获得某些信息, 在获取信息的过程中需要与另一个数据库进行交互, 我们发出某个提问, 数据库给予答复; 通过数据库已给出的答复, 我们设计后续的问题, 直到获取到我们想要的信息.

举个简单的例子, Alice 是一位优秀大学生, 她想要从教务老师那里问出自己的绩点 (精确到小数点后两位). 现在已知 Alice 的绩点是落在 $[0,4]$ 这个区间内的任一个实数, 而教务老师不能直接告诉 Alice 她的绩点. Alice 只能试着问一个数字, 教务老师只会回答"高了"或者"低了". 显然一个高效的方法是二分提问, Alice 从 $2$ 开始问, 如果教务老师回答"高了", 就从 $1$ 继续问; 如果教务老师回答"低了", 就从 $3$ 继续问, 直到二分区间小于 $0.01$. 还有一个低效的方法是把所有可能值都问一遍, Alice 从 $0$ 开始问, 然后问 $0.01$, 然后问 $0.02$... 一直问到 $4.00$, 全部问完之后, 找到教务老师回答"高了"和"低了"的分界线.

但有可能这时候一位 Bob 也想知道 Alice 的绩点, 于是偷偷观察 Alice 的提问方法, 但 Bob 没法听到教务老师的回答. 如果这时候 Alice 采用高效的二分方法, Bob 只要观察到 Alice 停止了提问, 即使不知道教务老师对所有问题的回答是什么, 他也能立刻知道 Alice 的绩点是多少, 因此 Alice 的二分提问法是毫无隐私可言的. 但如果 Alice 把所有可能的值都问一遍, 再根据教务老师的回答自己做判断, Bob 的观察是获取不到任何信息的, 因为不管 Alice 的绩点是多少, 她的提问方式都一样, 因此这个方法保护了 Alice 的所有隐私.

这个简单的例子告诉我们: 当有第三方窃听时, 高效的方法可能会导致严重的隐私泄露. 也许算法效率与隐私保护之间存在某种 trade-off, 我们没法同时达到这两个目标. 在 Private Sequential Learning 这篇论文中, 作者对这一问题进行了详细的分析.

问题描述

问题定义

我们对隐私保护的 Sequential Learning 进行形式化定义如下:

一个学习者 (learner) 希望得到一个真实值 $v \in R$. 该真实值 $v $ 被存在外部的数据库中, learner 会与数据库进行交互, 每次提交一个询问 $q_k$, 并得到一个答复 $r_k\in\{0,1\}$, 满足:

$$\left\{ \begin{array}{**lr**} r_k=0, \quad v < q_k \\ r_k=1, \quad v \geq q_k, \end{array} \right.$$

或用示性函数表示为 $r_k=\mathbb{I}(v^*\geq q_k)$.

不失一般性, 设 $v \in[0,1)$, 因此也有 $q_k\in[0,1)$. 每次提交询问时对 $q_k$ 的选择可以依赖于前面所有的询问与答复.

在进行 $N$ 次询问后, learner 希望得到对真实值 $v $ 的误差不超过 $\epsilon/2$ 的估计 $\hat x$, 即 $\hat x$ 应当满足:

$$|\hat x-v |\leq \frac{\epsilon}{2}.$$

与此同时, 有一个窃听者 (adversary) 也想得到该真实值 $v $. Adversary 可以窃听 learner 所提交的所有询问 $q_k$ 与 learner 的提问策略, 但无法与数据库交互, 因此不知道 $r_k$. 在窃听了 learner 的所有询问后, adversary 希望得到对真实值 $v $ 的误差不超过 $\delta/2$ 的估计 $\hat x^a$, 即 $\hat x^a$ 应当满足:

$$|\hat x^a-v |\leq \frac{\delta}{2}.$$

我们用 $L$ 定义 learner 的隐私保护程度: 当 adversary 只能以不超过 $1/L$ 的概率在 $\delta/2$ 的误差范围内估计 $v $ 时, learner 的隐私保护程度为 $L$.

Learner 与 Adversary

前面我们提到, learner 在每次提交询问时, 对 $q_k$ 的选择依赖于前面所有的询问与答复. 对于总次数为 $N$ 的询问, learner strategy 由两部分构成, 可表示为 $\phi=((\phi_1,\phi_2,\cdots,\phi_N),\phi^E)$. 其中 $(\phi_1,\phi_2,\cdots,\phi_N)$ 是询问策略函数, $\phi^E$ 是估计函数. 设定一个随机数种子 $Y$.

对于 $(\phi_1,\phi_2,\cdots,\phi_N)$, 有:

$$q_1=\phi_1(Y),$$ $$q_k=\phi_{k}(q_1,q_2,\cdots,q_{k-1},r_1,r_2,\cdots,r_{k-1},Y)\quad 1< k\leq N.$$

每一个 $\phi_k$ 的作用是根据已提出的询问和已获得的答复 (以及随机数种子) 来选择下一个询问.

对于 $\phi^E$, 有:

$$\hat x=\phi^{E}(q_1,q_2,\cdots,q_{N},r_1,r_2,\cdots,r_{N},Y).$$

$\phi^E$ 的作用是根据全部的询问和已获得的答复 (以及随机数种子) 来对真实值进行估计.

Adversary 可以从 learner 处获得的信息如下: 首先, adversary 知道 $v \in[0,1)$; 其次, adversary 知道 learner 所有的询问策略函数 $(\phi_1,\phi_2,\cdots,\phi_N)$ 以及 learner 的所有询问 $(q_1,q_2,\cdots,q_N)$.

信息集

我们在上述定义的基础上, 对 adversary 所拥有的信息进一步进行表示:

固定 learner 的策略 $\phi$, 用 $\mathcal Q(x)$ 表示当真实值 $v =x$ 时, learner 可能的询问序列的集合, 即:

$$\mathcal Q(x)=\{\overline q\in[0,1)^N\mid P_{\phi}(Q_x=\overline q)>0\}.$$

这里 $Q_x$ 是指当真实值 $v =x$ 时, learner 真正的询问序列.

用 $\mathcal I(\overline q)$ 表示 adversary 的信息集, 当 learner 的提问序列为 $\overline q$ 时, 所对应的所有可能的真实值, 即

$$\mathcal I(\overline q)=\{x\in[0,1)\mid \overline q\in \mathcal Q(x)\}.$$

这里我们可以想到, 如果 $\mathcal I(\overline q)$ 的"规模"很大, 即 $\overline p$ 对应了许多可能的真实值 $x$, 那么 adversary 观察到 learner 的提问序列是 $\overline q$ 时, 也很难猜出真实值到底是多少. 这时其实 learner 的隐私就是被保护了的. 因此, 我们可以先粗略地意识到, 想要保护 learner 的隐私, 就是要让这个信息集的 $\mathcal I(\overline q)$ 的"规模"尽可能大, 使得 adversary 没法通过 $\overline q$ 解出 $x$.

那么究竟该如何定义 $\mathcal I(\overline q)$ 的规模呢? 回忆我们在此问题中的定义中提到, adversary 希望对真实值 $v $ 估计的误差不超过 $\delta$. 因此, 这里可以考虑用长度为 $\delta$ 的小区间覆盖 $\mathcal I(\overline q)$, 通过覆盖的数量来定义 $\mathcal I(\overline q)$ 的规模.

给定 $\delta>0,L\in \mathbb N$ 与集合 $\mathcal E\subset R$, 对于一组 $L$ 个闭区间 $[a_1,b_1],[a_2,b_2],\cdots,[a_L,b_L]$, 如果满足 $\mathcal E\subset \cup_{1\leq j\leq L}[a_j,b_j]$ 且 $b_j-a_j\leq \delta,\forall j$, 则称这组闭区间为 $\mathcal E$ 的一个 $(\delta,L)$ 覆盖.

对于集合 $\mathcal E$, 只要它存在一个 $(\delta, L)$ 覆盖, 我们则称它是 $(\delta,L)-{\rm coverable}$.

定义集合 $\mathcal E$ 的 $\delta-{\rm cover~number}$ 为:

$$C_\delta(\mathcal E)=\min\{L\in \mathbb N\mid \mathcal E ~{\rm is}~(\delta,L)-{\rm coverable}\}.$$

显然, 对于任一值 $v \in \mathcal E$, 该 $v $ 必然落在这 $L$ 个区间内的某一个. 我们有 $1/C_\delta(\mathcal E)$ 的概率找到正确的那个区间.

隐私策略

在上述定义的基础上, 给定 $\epsilon,\delta>0,L\in \mathbb N$, 我们可以对 learner 定义隐私策略: 对于 learner 的策略 $\phi$, 若它满足以下两点, 则称它是 $(\epsilon,\delta,L)-{\rm private}$ 的:

• 准确度: 在允许的误差下, learner 一定可以估计出真实值, 即

  $$P(|\hat x(x,Y)-x|\leq \epsilon/2)=1,\forall x\in[0,1).$$

  此处 $\hat x( x,Y)$ 表示真实值为 $x$, 随机数种子为 $Y$ 时, 该策略下 learner 给出的估计值.

• 隐私性: 对于所有可能的真实值 $x\in [0,1)$ 与所有可能的询问序列 $\overline q\in \mathcal Q(x)$, adversary 的信息集的 $\delta-{\rm cover~number}$ 都不小于 $L$, 即

  $$C_\delta(\mathcal I(\overline q))\geq L,\forall \overline q\in \mathcal Q(x).$$

对于 adversary 的信息集 $\mathcal I(\overline q)$, 如果它至少需要 $L$ 个长度为 $\delta$ 的区间才能被覆盖, 那么显然 adversary 只有 $1/L$ 的概率在允许的误差 $\delta$ 范围内猜到正确的真实值. 因此如果 learner 的策略满足了上述两点, 这个策略就符合我们的期望, 既能保证 learner 自己算出真实值, 又能保证程度为 $L$ 的隐私.

理论结果

定义询问复杂度 (query complexity) 为 learner 的满足 $\epsilon,\delta>0,L\in \mathbb N$ 隐私策略所需要的最少询问次数, 表示为 $N^{*}(\epsilon,\delta,L)$, 即

$$N^{*}(\epsilon, \delta, L)=\min \left\{N \in \mathbb{N}: \Phi_{N} \text { contains at least one }(\epsilon, \delta, L) \text { -private strategy }\right\}$$

这里 $\Phi_{N}$ 是所有长度为 $N$ 的策略集合 $[0,1)^N$.

我们将条件限定在 $0<2\epsilon<\delta\leq 1/L$. $2\epsilon < \delta$ 是基于 adversary 只希望有一个粗略估计的假设. $\delta \leq 1 / L$ 是因为, 一旦有 $\delta \geq 1 /(L-1)$, 那么整个 $[0,1)$ 区间就是一个平凡的 $(\delta,L-1)-{\rm coverable}$: 我们只需要把它以 $\delta$ 为间隔分为不少于 $L-1$ 个小段就可以了.

在上述定义与限定下, 对于询问复杂度, 我们有如下的定理:

$$\max \left\{\log \frac{1}{\epsilon}, \log \frac{\delta}{\epsilon}+2 L-4\right\} \leq N^{*}(\epsilon, \delta, L) \leq \log \frac{1}{L \epsilon}+2 L.$$

该公式直接给出了询问复杂度的 upper bound 和 lower bound. 对于不等式的右边 (upper bound), 我们进行构造式的证明, 提出一种二分搜索策略的变体: Opportunistic Bisection 策略. 对于不等式的左边 (lower bound), 我们尝试说明: 为了混淆 adversary 的信息集, 我们需要在二分搜索的询问基础上加入至少额外的 $2L$ 次询问.

Upper Bound

询问复杂度的 Upper Bound 通过 Opportunistic Bisection 策略的构造进行证明. 顾名思义, 该策略具有两个阶段: Opportunistic Guessing 与 Bisection Search.

• Opportunistic Guessing

  在这一阶段, learner 以固定策略提交 $2L$ 次询问. 其中

  $$\left\{\begin{aligned} &q_i=\frac{i-1}{L}, \quad 1\leq i \leq L\\ &q_i=q_{i-L}+\epsilon, \quad l+1\leq i\leq 2L. \end{aligned} \right.$$

• Bisection Search

  上一阶段结束后, learner 可能知道 $v $ 落在哪个小区间里. 假设它落在 $(q_v,q_{v+L})$ 中. 那么此时 learner 的目标已经达成, 在这一阶段, learner 再提交 $M=\log \left(\frac{1}{\epsilon L}\right)$ 次二分搜索的询问, 不过忽视数据库的答复, 采用随机的二分搜索.

  如果 learner 还未能知道 $v $ 落在哪个小区间内, 在这一阶段, learner 再根据数据库的答复提交 $M=\log \left(\frac{1}{\epsilon L}\right)$ 次二分搜索的询问, 采用真实的二分搜索.

显然, 该策略是 $(\epsilon,\delta,L)-{\rm private}$ 的. 该策略中总共的询问次数为:

$$N=2 L+\log \left(\frac{1}{\epsilon L}\right).$$

Lower Bound

对于每个随机数种子 $Y$, 一定存在 $x\in (0,\delta)$, 使得 learner 的提问序列 $\overline q(x,Y)$ 中至少有 $\log(\delta/\epsilon)$ 个询问落在区间 $(0,\delta)$ 中. 实际上, 对于每个长度为 $\delta$ 的小区间, 我们都有这样的性质. 因此不失一般性, 我们将该小区间设为了 $(0,\delta)$.

固定 $v = x_0,Y=y_0$ 为满足上述性质的 $v 和 Y$. 我们现在考虑 $[\delta,1]$ 区间上的查询.

定义长度不超过 $\epsilon$ 的小区间为 special intervals. 接下来, 我们考虑那些是 special intervals 的端点的询问, 并称之为 special queries, 表示为 $s_1,s_2,\cdots,s_K$. 对于所有的 special intervals $s_i$, 它与相邻的查询 $s_{i-1}$ 与 $s_{i+1}$ 的距离不超过 $\epsilon$.

前面我们已经假设 $\delta>2\epsilon$, 那么每一个长度为 $\delta$ 的区间可以包括2或3个 $s_i$.
因此如果希望 learner 的策略是 $(\epsilon,\delta,L)-{\rm private}$ 的, learner 需要让 $\delta-{\rm cover}$ 的数量至少是 $L$. 因此应有 $(K+3)/2\geq L$.

因此, learner 在 $[0,\delta)$ 中至少需要 $\log(\delta/\epsilon)$ 次询问, 在$[\delta,1]$ 中至少需要 $2L-3$ 次询问. 而效率最高的二分搜索保证总询问次数不少于 $\log(1/\epsilon)$. 因此询问复杂度的 lower bound 为

$$N\geq \max \left\{\log \frac{1}{\epsilon}, \log \frac{\delta}{\epsilon}+2 L-4\right\}.$$

一些额外的思考

1. 如果真实值 $v $ 具有一个初始的概率分布 $p(x)$, 考虑这个 $p(x)$ 仅被 learner 知道与同时被 learner 和 adversary 知道的情况, 那么 learner 和 adversary 的策略又会如何?
2. 如果数据库是分布式的, learner 需要以分布式的方式提交查询, 该过程中可能有多个 adversary 在监视他, 这是会有怎样的结果?