论文笔记[15]——度量空间中的差分隐私

论文:Holohan N, Leith D J, Mason O. Differential privacy in metric spaces: Numerical, categorical and functional data under the one roof[J]. Information Sciences, 2015, 305: 256-268.

基础知识

首先是一些实变/测度论里的基础知识:\(\sigma\) 代数、测度空间、乘积 \(\sigma\) 代数、单调类等等. 不多赘述..

  • \(U\) 是一个度量空间,带有度量 \(\rho\). 考虑其上的 Borel \(\sigma\) 代数 \(\mathcal{A}\)
    • \(D\) 是其子空间,我们称其为所有数据(可能是数值,也可能不是)构成的集合. \(D\) 天然继承了 Borel \(\sigma\) 代数.
    • 进一步,如果我们的数据是 \(n\) 维向量,那么其所属的空间就是 \(D^n\),当然,其上的测度完全可以用乘积测度来构造.
  • Database:一个 database 就是一个序列 \(\mathbf{d}=(d_1,\ldots,d_n)\).
    • \(\mathbf{d}\)\(\mathbf{d}'\) 为 neighboring datasets,如果仅有一项不同,记作 \(\mathbf{d}\sim\mathbf{d}'\).
    • 更一般地,Hamming 距离用 \(h(\mathbf{d},\mathbf{d}')\) 表示.
  • Query:设所有查询结果所构成的集合为 \(E_Q\)\(\mathcal{A}_Q\) 是其上的 \(\sigma\)-代数.(若 \(E_Q\) 为度量空间,则为 Borel 代数)
    • 一个查询 \(Q(\mathbf{d})\) 是一个可测映射 \(Q:U^n\to E_Q\).
  • Reponse Mechanism:现给定一个概率空间 \((\Omega,\mathcal{F},\mathbb{P})\),其中 \(\Omega\) 是一个集合(原文:corresponding informally to the set of outcomes of some ‘random experiment’)
    • 一个应答机制就是一大堆可测映射 \(\{X_{Q,\mathbf{d}}:\Omega\to E_Q| Q\in\mathcal{Q},\mathbf{d}\in D^n\}\).
  • Sanitised Reponse Mechanism:一个应答机制 \(X_{Q,\mathbf{d}}\) 是 sanitised reponse mech,当且仅当它具有 \(X_{Q,\mathbf{d}}=Q\circ Y_\mathbf{d}\) 的形式.
    • Sanitisation:一些可测映射 \(\{Y_\mathbf{d}:\Omega\to U^n | \mathbf{d}\in D^n \}\). 这些映射实际上是对 \(D^n\) 中的数据做了“清洗”(譬如加噪音).
  • Output Perturbations:给定查询 \(Q: U^n\to E_Q\),考虑一族可测函数 \(\{Z_q:\Omega\to E_Q|Q\in E_Q\}\). 我们假定查询的真实结果就是 \(q\),那么 \(Z_q\) 就是对该查询的一个扰动. 因此一个 Output Pertur Mech 应当具有 \(X_{Q,\mathbf{d}}=Z_{Q(\mathbf{d})}\) 的形式.

现在即可定义差分隐私:

Def 1. (DP with respect to a query) 现有 \(\epsilon\geqslant 0\)\(\delta\in [0,1]\),一个应答机制对查询 \(Q_0\in\mathcal{Q}\) 服从 \((\epsilon,\delta)\)-DP,当且仅当对 \(\forall \mathbf{d}\sim\mathbf{d}'\in D^n\),以及 \(\forall A\in \mathcal{A}_{Q_0}\),总有 \[\mathbb{P}\left(X_{Q_{0}, \mathbf{d}} \in A\right) \leqslant e^{\epsilon} \mathbb{P}\left(X_{Q_{0}, \mathbf{d ^ { \prime }}} \in A\right)+\delta.\]

Sufficient sets for differential privacy

本节主要讨论了这样的一个问题:是否存在 \(\mathcal{A}_Q\) 的一个真子集 \(\mathcal{S}\),s.t. 只要 \(\forall A\in\mathcal{S}\) 都满足差分隐私的定义,就足以说明 \(\mathcal{A}_Q\) 中所有集合也都满足差分隐私.

Output space:\(\mathbb{R}^n\)\(C([0,T])\).

Thm 3 给定应答机制 \(X_{Q,\mathbf{d}}\) 以及查询 \((Q,E_Q,\mathcal{A}_Q)\),令 \(\mathcal{S}\subset \mathcal{A}_Q\) 是一个集代数,s.t. \(\sigma(\mathcal{S})=\mathcal{A}_Q\). 若对 \(\forall A\in\mathcal{S}\)\((\epsilon,\delta)\)-DP 的定义式都成立,则对 \(\forall A\in\mathcal{A}_Q\) 也才成立.

Sanitised response mechanisms and the identity query

  • Identity query:\(I_n\)\(U^n\) 上的恒等映射,即 \(I_n(\mathbf{x})=\mathbf{x},~\forall \mathbf{x}\in U^n\). 对于 Id query 而言,\(E_Q=U^n\).
  • 在数据清洗中,\(Y_\mathbf{d}(\omega)\) 可被视为对于 id query 的一个响应.

Th 4(Id query) 若数据清洗过程的 \(Y_\mathbf{d}\)\((\epsilon,\delta)\)-DP 的,则任何查询 \((Q,E_Q,\mathcal{A}_Q)\) 的响应机制都满足相同规格的 DP.

文中这里有一个 Remark,比较了一下数据清洗与输出扰动. 事实上,二者的区别是显而易见的:

  • 数据清洗后,显然可以在保证隐私的情况下回答任何问题;
  • 采用输出扰动机制的话,反复进行相同查询会导致隐私泄露,似乎没什么难以理解的吧(

Cor 1 考虑一个基于数据清洗的应答机制,设 \(I_n\in\mathcal{Q}\). 则该机制是 \((\epsilon,\delta)\)-DP 的,当且仅当该机制对所有 \(I_n\) 的应答是 \((\epsilon,\delta)\)-DP 的.

Product sanitisations

顾名思义,乘积数据清洗就是把一维的清洗扩展到高维.

先是一个集类的结论:

Lemma 1\(A_1,\ldots,A_p,B_1,\ldots,B_p\) 是两列非空集合,则有 \[\bigcup_{i=1}^p(A_i\times B_i)=\bigcup_{I\subset\{1,\ldots,p\}}(\tilde{A}_I\times\tilde{B}_I)\] 其中 \(\tilde{A}_I=\bigcup_{i\in I}A_i\)\(\tilde{B}_I=\bigcap_{i\in I}B_i\backslash\bigcup_{i\notin I}B_i\).(进一步有 \(\tilde{B_I}\cap\tilde{B_J}=\varnothing\)\(\forall I\neq J\)

Lemma 3 给定一族可测映射 \(\{Y_d:\Omega\to U | d\in D\}\),定义 \(Y_\mathbf{d}:\Omega\to U\)\(Y_\mathbf{d}(\omega)=\left( Y^1_\mathbf{d}(\omega),Y^2_\mathbf{d}(\omega),\ldots,Y^n_\mathbf{d}(\omega) \right)\). 若 \(Y_\mathbf{d}\)\((\epsilon,\delta)\)-DP 的,则 \[\mathbb{P}(Y_d\in A)\leqslant e^\epsilon \mathbb{P}(Y_{d'}\in A)+\delta,\quad \forall d,d'\in D, A\in\mathcal{A}_U\]

Th 5 考虑一族可测映射 \(\{Y_d:\Omega\to U|d\in D\}\),假设 \[\mathbb{P}(Y_d\in A)\leqslant e^\epsilon \mathbb{P}(Y_{d'}\in A)+\delta,\quad \forall d,d'\in D,A\in\mathcal{A}_U\] 按照前文所述定义 \(Y_\mathbf{d}\),则有: \[\mathbb{P}(Y_\mathbf{d}\in A)\leqslant e^\epsilon \mathbb{P}(Y_{\mathbf{d}'}\in A)+\delta,\quad \forall \mathbf{d}\sim\mathbf{d}'\in D^n, A\in\mathcal{A}_{U^n}\]

上述 Th 5 还是比较有用的,文中给出了两个例子:

Accuracy

我们利用期望误差来评价准确性: \[\mathcal{E}=\max\limits_{d\in D}~\mathbb{E} [\rho(Y_d,d)]\]

文中的 Lemma 4 没什么营养,就是告诉我们在满足 DP 的前提下 \(\mathcal{E}\) 一定是正数.

接下来是关于它的进一步估计:

Th 6 给定一族可测映射 \(\{Y_d:\Omega\to U|d\in D\}\),且满足 \((\epsilon,\delta)\)-DP,则有: \[\mathcal{E}\geqslant (1-\delta)\left( \frac{\operatorname{diam}(D)}{2(1+e^\epsilon)} \right)\]


简单总结一下...这篇文章大概给了一个度量空间下的差分隐私框架. 文中先对数据清洗和输出扰动两种隐私方案进行了介绍与比较,然后分析了一下准确性(误差). 总体来说,有一点点失望hhh,感觉没有想象中营养丰富==(不过文章也不算长吧,13页)