【差分隐私相关概念】约束下的矩阵机制

矩阵机制（Matrix Mechanism，MM）详细解释

矩阵机制是差分隐私中一种高效的数据发布方法，通过设计策略矩阵 $\mathbf{A}$ 对线性查询进行组合，优化噪声添加和结果重构的准确性。以下分步骤解释其原理及示例。

一、核心概念与公式解析

1. 策略矩阵 $\mathbf{A}$

   • 作用：将原始数据库 $\mathbf{x}$ 编码为一组线性查询 $\mathbf{Ax}$，例如总和、平均值或更复杂的组合。
   • 设计目标：通过矩阵设计最小化重构误差或隐私预算消耗。

2. 噪声添加

   • 拉普拉斯机制：生成带噪声的响应
     $$\tilde{\mathbf{r}}=\mathbf{Ax}+\text{Lap}({\Delta }_{\mathbf{A}}/ϵ),$$
     其中 ${\Delta }_{\mathbf{A}}$ 是策略矩阵的敏感度，$ϵ$ 是隐私预算。
   • 敏感度 ${\Delta }_{\mathbf{A}}$：定义为相邻数据库 $\mathbf{x}$ 与 ${\mathbf{x}}^{\prime }$ 的 $\mathbf{A}(\mathbf{x}-{\mathbf{x}}^{\prime })$ 的 $L_1$ 范数最大值。

3. 最小二乘解

   • 无约束近似：通过伪逆矩阵 ${\mathbf{A}}^{†}$ 重构数据库
     $$\hat{\mathbf{x}}={\mathbf{A}}^{†}\tilde{\mathbf{r}}=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}\tilde{\mathbf{r}},$$
     最小化 $L_2$ 误差 $\Vert \tilde{\mathbf{r}}-\mathbf{A}\hat{\mathbf{x}}{\Vert }_2^2$。

4. 带约束的优化问题

   • 非负性与最大似然：修正解以满足 $\hat{\mathbf{x}}\ge 0$ 并最小化 $L_1$ 误差
     $$\overline{\mathbf{x}}=\arg \underset{\hat{\mathbf{x}}\ge 0}{\min }\Vert \tilde{\mathbf{r}}-\mathbf{A}\hat{\mathbf{x}}{\Vert }_1.$$

二、具体示例：人口统计发布

1. 场景设定

• 数据库 $\mathbf{x}$：两个群体的人口数 $\mathbf{x}=[x_1,x_2]$，其中 $x_1=100$（城市人口），$x_2=200$（农村人口）。
• 策略矩阵 $\mathbf{A}$：设计为同时查询总人口和城乡差异：
  $$\mathbf{A}=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right].$$
  • 查询结果：$\mathbf{Ax}=[300,-100]$（总人口 300，城乡差 -100）。

2. 敏感度计算

• 相邻数据库：假设 $\mathbf{x}$ 与 ${\mathbf{x}}^{\prime }$ 相差 1（如 $x_1^{\prime }=x_1+1$）。
  • $\mathbf{A}(\mathbf{x}-{\mathbf{x}}^{\prime })$ 的可能值为 $[1,1]$ 或 $[1,-1]$。
  • $L_1$ 范数的最大值为 $2$，因此 ${\Delta }_{\mathbf{A}}=2$。

3. 噪声添加

• 隐私参数：设 $ϵ=1$，噪声尺度为 ${\Delta }_{\mathbf{A}}/ϵ=2$。
• 生成噪声：从拉普拉斯分布采样，假设噪声为 $\text{Lap}(2)$：
  $$\tilde{\mathbf{r}}=[300+3,-100-1]=[303,-101].$$

4. 最小二乘解

• 计算伪逆：
  $${\mathbf{A}}^{†}=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}=\frac{1}{2}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right].$$
• 重构结果：
  $$\hat{\mathbf{x}}=\frac{1}{2}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{c}303\\ -101\end{array}\right]=\frac{1}{2}\left[\begin{array}{c}202\\ 404\end{array}\right]=[101,202].$$
  • 结果 $\hat{\mathbf{x}}=[101,202]$ 非负，无需进一步优化。

5. 含负数的优化示例

• 假设噪声导致负值：若 $\tilde{\mathbf{r}}=[305,-105]$，则：
  $$\hat{\mathbf{x}}=\frac{1}{2}\left[\begin{array}{c}200\\ 410\end{array}\right]=[100,205].$$
  • 结果仍为非负，直接接受。

三、优化问题的必要性

若最小二乘解出现负数，需通过优化问题修正：

1. 示例场景

• 噪声响应：$\tilde{\mathbf{r}}=[290,90]$（不合理，因城乡差不可能超过总人口）。
• 最小二乘解：
  $$\hat{\mathbf{x}}=\frac{1}{2}\left[\begin{array}{c}290+90\\ 290-90\end{array}\right]=[190,100].$$
  • 结果合理，但若噪声更大（如 $\tilde{\mathbf{r}}=[300,150]$）：
    $$\hat{\mathbf{x}}=\frac{1}{2}\left[\begin{array}{c}450\\ 150\end{array}\right]=[225,75].$$
    • 需确保非负（此处已满足）。

2. 优化问题解决步骤
若 $\hat{\mathbf{x}}$ 含负数（例如 $\hat{\mathbf{x}}=[150,-50]$）：

• 约束条件：${\overline{x}}_1\ge 0$，${\overline{x}}_2\ge 0$。
• 目标：最小化 $\Vert \tilde{\mathbf{r}}-\mathbf{A}\overline{\mathbf{x}}{\Vert }_1$。
• 求解方法：使用线性规划或投影梯度下降，找到满足 $\overline{\mathbf{x}}\ge 0$ 且最接近 $\tilde{\mathbf{r}}$ 的解。

四、策略矩阵的设计意义

1. 误差优化

   • 直接发布原始数据：对每个 $x_i$ 独立加噪，误差随维度线性增长。
   • 矩阵机制：通过线性组合查询，可能降低全局误差。例如，若 $\mathbf{A}$ 正交，噪声在各方向均匀分布，重构误差更小。

2. 敏感度权衡

   • 单位矩阵策略：$\mathbf{A}=\mathbf{I}$，敏感度 ${\Delta }_{\mathbf{A}}=1$，但重构误差与维度相关。
   • 聚合查询策略：如 $\mathbf{A}=[1,1]$，敏感度 ${\Delta }_{\mathbf{A}}=1$，但丢失个体信息。

五、总结

• 矩阵机制流程：

  1. 设计策略矩阵 $\mathbf{A}$ 编码查询。
  2. 计算敏感度 ${\Delta }_{\mathbf{A}}$ 并添加拉普拉斯噪声。
  3. 通过伪逆矩阵重构初步解 $\hat{\mathbf{x}}$。
  4. 优化非负约束下的 $L_1$ 误差，得到最终解 $\overline{\mathbf{x}}$。

• 优势：通过矩阵设计平衡隐私与准确性，适用于复杂查询和高维数据发布。

• 关键点：策略矩阵的敏感度计算、噪声分布分析及带约束优化求解。