【差分隐私相关概念】约束下的列联表边缘分布计算方法

列联表及其边缘分布的详细解释

一、列联表的定义

列联表（Contingency Table） 是一种用于表示 多个分类变量联合分布 的表格。其核心是通过多维数组记录不同属性组合的频次。以下是关键点：

1. 分类属性：

   • 设有 $k$ 个分类属性 $A_1,A_2,\dots ,A_k$，每个属性 $A_j$ 的取值范围为 I j = { 1 , 2 , … , I j } \mathcal{I}_j = \{1, 2, \dots, I_j\} Ij​={1,2,…,Ij​}。
   • 示例：若 $k=3$，属性可能为性别（ A 1 ∈ { 男 , 女 } A_1 \in \{男, 女\} A1​∈{男,女}）、年龄段（ A 2 ∈ { 0 − 10 , 11 − 20 } A_2 \in \{0-10, 11-20\} A2​∈{0−10,11−20}）、地区（ A 3 ∈ { 城市 , 农村 } A_3 \in \{城市, 农村\} A3​∈{城市,农村}}）。

2. 多维数组表示：

   • 每个单元格 $x(i_1,i_2,\dots ,i_k)$ 表示属性组合 $(A_1=i_1,A_2=i_2,\dots ,A_k=i_k)$ 的频次。
   • 示例：$x(1,2,1)$ 表示“男性、11-20岁、城市”的人口数。

3. 向量化表示：

   • 通过字典序函数 $\Psi$，将多维索引 $(i_1,i_2,\dots ,i_k)$ 映射为一维索引 i ∈ { 1 , 2 , … , n } i \in \{1, 2, \dots, n\} i∈{1,2,…,n}，其中 $n={\prod }_{j=1}^k{I}_j$。
   • 示例：若 $k=2$， I 1 = { 1 , 2 } \mathcal{I}_1=\{1,2\} I1​={1,2}， I 2 = { 1 , 2 } \mathcal{I}_2=\{1,2\} I2​={1,2}，则：
     • $\Psi (1,1)=1$，$\Psi (1,2)=2$，$\Psi (2,1)=3$，$\Psi (2,2)=4$，向量 $\mathbf{x}=(x_1,x_2,x_3,x_4)$。

二、边缘分布的计算

边缘分布（Marginal Distribution） 是通过对某些属性求和得到的简化分布。其目的是观察部分属性的联合频次。

1. 属性子集 $B\subseteq K$：

   • 选择需要保留的属性集合（如 B = { A 1 , A 3 } B = \{A_1, A_3\} B={A1​,A3​}）。
   • 投影操作：将多维索引 $(i_1,i_2,\dots ,i_k)$ 投影到 $B$ 上，得到 $(i_{j_1},i_{j_2},\dots ,i_{j_b})$，其中 $j_1,j_2,\dots ,j_b\in B$。

2. 边缘分布公式：
   对于固定的 $b\in {\mathcal{I}}_B$（即 $B$ 中属性的某个取值组合），其边缘计数为：
   $$\mathfrak{m}(b)=\sum _{j\in K\setminus B}x(b,j),$$
   其中 $x(b,j)$ 表示在固定 $B$ 的取值为 $b$ 时，对所有其他属性（$K\setminus B$）的可能取值求和。

   示例：

   • 若 $k=3$， B = { A 1 , A 3 } B = \{A_1, A_3\} B={A1​,A3​}，$b=(男,城市)$，则：
     $$\mathfrak{m}(b)=x(男,0-10,城市)+x(男,11-20,城市).$$

三、边缘分布的线性约束

边缘分布 $\mathfrak{m}(b)$ 可以表示为列联表向量 $\mathbf{x}$ 上的线性约束。

1. 系数向量 $\mathbf{a}$ 的构造：

   • 对于每个一维索引 i ∈ { 1 , 2 , … , n } i \in \{1, 2, \dots, n\} i∈{1,2,…,n}，检查其对应的多维索引 ${\Psi }^{-1}(i)$ 在 $B$ 上的投影是否为 $b$。
   • 如果是，则 $a_i=1$，否则 $a_i=0$。
   • 数学定义：
     $$a_i=\{\begin{array}{ll}1,& \text{if }{\text{proj}}_B({\Psi }^{-1}(i))=b,\\ 0,& \text{otherwise}.\end{array}$$

2. 约束方程：
   边缘计数 $\mathfrak{m}(b)$ 对应的线性约束为：
   $$\sum _{i=1}^n{a}_i{x}_i=\mathfrak{m}(b).$$
   本质：将满足 $B$ 取值为 $b$ 的所有单元格的频次相加。

四、具体案例解释

1. 场景设定

• 属性：$A_1$（性别，$I_1=2$），$A_2$（年龄段，$I_2=2$）。
• 列联表为 2x2 二维数组，向量化为 $\mathbf{x}=(x_1,x_2,x_3,x_4)$，其中：
  • $x_1=x(男,0-10)$，$x_2=x(男,11-20)$，
  • $x_3=x(女,0-10)$，$x_4=x(女,11-20)$。

2. 计算边缘分布

• 选择子集 B = { A 1 } B = \{A_1\} B={A1​}（仅保留性别）：
  • I B = { 男 , 女 } \mathcal{I}_B = \{男, 女\} IB​={男,女}。
  • 对每个 $b\in {\mathcal{I}}_B$，计算边缘分布：
    • $b=男$：$\mathfrak{m}(男)=x_1+x_2$，
    • $b=女$：$\mathfrak{m}(女)=x_3+x_4$。

3. 线性约束表示

• 对于 $b=男$，系数向量 $\mathbf{a}=(1,1,0,0)$，约束方程为：
  $$1\cdot x_1+1\cdot x_2+0\cdot x_3+0\cdot x_4=\mathfrak{m}(男).$$

五、后处理的目标

给定含噪声的列联表 $\tilde{\mathbf{x}}$ 和真实的边缘分布 $\mathfrak{m}(B)$，后处理的目标是找到一个修正后的表 $\overline{\mathbf{x}}$，使得：

1. 满足所有边缘约束：对每个 $b\in {\mathcal{I}}_B$，$\sum a_i{\overline{x}}_i=\mathfrak{m}(b)$。
2. 非负性：${\overline{x}}_i\ge 0$。
3. 最小化误差：$\overline{\mathbf{x}}$ 与 $\tilde{\mathbf{x}}$ 尽可能接近（如最小化 $\Vert \overline{\mathbf{x}}-\tilde{\mathbf{x}}{\Vert }_2^2$）。

六、总结

• 列联表：多维分类数据的频次表格，可向量化为 $\mathbf{x}\in {\mathbb{N}}^n$。
• 边缘分布：通过投影和求和操作，提取部分属性的联合频次。
• 线性约束：每个边缘分布对应一个系数为 0/1 的线性方程，用于保证数据一致性。
• 应用：在差分隐私中，通过后处理修复噪声数据，使其满足原始数据的统计结构。