论文：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页）