原文课程: Lecture 8 — Private Multiplicative Weights (Gautam Kamath, CS 860, Fall 2020)前面我们学习了拉普拉斯机制、高斯机制和指数机制。它们能回答单个或少量查询但如果要回答海量查询呢比如一个数据分析师想问你一万个关于人口普查数据的问题——每个问题都精确到 1% 以内。用拉普拉斯机制你需要至少O(|Q|)个样本——大约一万人才能回答一个问题(误差 1%)而回答一万个问题就需要一亿人这合理吗显然不合理——数据集中包含的信息是有限的它不可能支持任意多查询的精确回答。但问题在于能不能比拉普拉斯机制做得更好答案是能。而且方法出乎意料地优雅——它来自一个叫乘法权重的古老算法。1. 从一条数据到合成数据线性查询的定义先来定义我们要回答的问题。**线性查询Linear Query是一类非常基础的问题给定一个查询函数 q: X → [0,1]它在某个数据集 D 上的答案是所有样本取值的平均值**q(D) (1/n) · Σ_{x∈D} q(x)举个具体例子查询q(x) 的含义在数据集上的平均值有多少人是女性q(x)1 如果是女性否则 0女性比例平均年龄是多少将年龄归一化到 [0,1]归一化平均年龄有多少人年收入超过 5 万q(x)1 如果收入5万高收入比例有多少人是大学以上学历q(x)1 如果学历≥本科高学历比例线性查询看起来简单但几乎所有基础统计都可以表示为线性查询的组合。拉普拉斯机制需要多少数据如果要回答 |Q| 个查询每个误差 ≤ α拉普拉斯机制需要多少个样本根据组合定理n O(|Q| / (αε))这是线性增长的——查询越多所需数据越多。如果 |Q| 10,000α 0.01ε 1你需要n 1,000,000条数据。graph LR A[|Q| 个查询] -- B{所需样本量} B -- C[拉普拉斯: O(|Q|/αε) ] B -- D[乘法权重: O(√|Q|/αε) ]乘法权重算法能把这个需求降到O(√|Q|)——从线性变成平方根质的飞跃2. 核心思想你需要一个草稿直觉想象你在考试前复习。你手上没有标准答案原始数据集但你有一个草稿本一个对数据的初步估计。一开始你的草稿很粗糙——你可能随便猜了猜数据的分布。然后你开始做题回答查询。每次做完一道题你发现自己的答案和标准答案有差距你就回到草稿本上修正一下。经过多次迭代你的草稿本越来越接近真实数据。graph TB A[初始化: 均匀分布 D₁] -- B[找出差异最大的查询 q] B -- C[用指数机制选查询] C -- D[比较 D₁ 与真实数据在 q 上的答案] D -- E[用乘法权重更新 → D₂] E -- B E -- F[重复 T 轮后输出最终分布] style A fill:#e3f2fd,stroke:#1565c0 style E fill:#e8f5e9,stroke:#2e7d32 style F fill:#fff3e0,stroke:#e65100算法总览Private Multiplicative Weights (PMW) 算法包含以下组件组件作用类比真实数据集 D我们想保护的原始数据标准答案合成分布对真实数据的逐步修正的估计草稿本查询集合 Q所有待回答的问题考题指数机制选择当前误差最大的查询标记最需要纠正的题乘法权重更新根据误差调整合成分布修正草稿3. 算法拆解一步一步来第一步初始化假设数据集来自某个空间 X例如X 是性别、年龄、收入等所有可能属性的组合。一开始我们对真实数据一无所知所以合成分布 D₁ 设为均匀分布D₁(x) 1/|X| 对所有 x ∈ X如果 X 有 100 种可能的属性组合那每种组合的初始概率都是 1%。第二步找到最不准确的查询现在对每个查询 q ∈ Q我们计算它的误差Error(q) |q(合成分布) - q(真实数据)|误差衡量了当前合成分布在这个查询上的表现有多糟糕。graph TD A[查询 q₁: 女性比例真实: 52% 合成: 50%误差: 2%] B[查询 q₂: 平均年龄真实: 0.42 合成: 0.50误差: 8%] C[查询 q₃: 高收入比例真实: 30% 合成: 28%误差: 2%] D[查询 q₄: 高学历比例真实: 35% 合成: 50%误差: 15% ← 最大!] D -- E[指数机制选中 q₄ 的概率最高]但我们不能直接选误差最大的查询——那会暴露真实数据信息。我们用指数机制来选Pr[选择 q] ∝ exp(ε · Error(q) / 2)其中 ε 是每轮分配的隐私预算。这样选中最差查询的概率最高但也不排除其他查询——这保护了隐私。第三步用乘法权重更新分布找到误差最大的查询 q 后我们就知道了真实数据在这个查询上的答案 v q(真实数据)以及当前合成分布的答案 u q(合成分布)。如果 u v低估了意味着真实数据中满足 q 条件的人比我们猜的要多。我们就要提高那些满足 q 条件的个体的权重。具体更新规则是对每个 x ∈ X: 如果 q(x) 接近 1满足条件: D_new(x) D_old(x) · exp(η · (v - u)) 如果 q(x) 接近 0不满足条件: D_new(x) D_old(x) · exp(-η · (v - u))其中 η 是学习率类似于机器学习中的步长。然后归一化使所有概率之和为 1。graph LR subgraph 更新前 A1[满足条件的个体权重: 较低] A2[不满足条件的个体权重: 较高] end subgraph 乘法权重更新 B[乘以 exp(η·(v-u)) ↑] C[乘以 exp(-η·(v-u)) ↓] end subgraph 更新后 D1[满足条件的个体权重: 提高 ✅] D2[不满足条件的个体权重: 降低] end A1 -- B -- D1 A2 -- C -- D2直观理解这就像你发现自己的草稿低估了女性比例于是你调高了女性这一格的权重同时调低了男性的权重。多次迭代后分布会越来越准确。第四步重复 T 轮重复第 2-3 步 T 次。每轮分配 ε ε/T 的隐私预算用高级组合定理可以做得更好。最后把最后一轮的合成分布作为输出——所有查询在这个分布上的答案就是最终答案。4. 为什么它能节省样本量信息论视角拉普拉斯机制浪费了大量信息——它对每个查询独立地添加噪声完全没有利用查询之间的相关性。而 PMW 算法通过维护一个合成分布把所有查询的答案拧成一股绳——合成分布只需描述数据本身|X| 维而不是 |Q| 个独立答案。graph TD subgraph 拉普拉斯机制 L1[查询 q₁: 真实答案 噪声₁] L2[查询 q₂: 真实答案 噪声₂] L3[查询 q₃: 真实答案 噪声₃] L4[......] end subgraph PMW 算法 P1[合成分布 D一个统一的模型] P2[在 D 上同时回答所有查询] P3[答案自动满足一致性] end L1 -- L4 P1 -- P2 -- P3拉普拉斯每个答案独立加噪 → O(|Q|) 条数据/查询PMW用合成分布统一建模 → O(√|Q|) 条数据/查询理论保证PMW 的核心定理是对于 |Q| 个线性查询如果样本量满足n ≥ O( √(|Q| · log|X|) / (αε) )则 PMW 算法能以高概率回答所有查询误差 ≤ α。注意是√|Q|而不是 |Q|——当查询数量很大时这是巨大的改进查询数拉普拉斯所需 nPMW 所需 n节省10010,0001,00010x1,000100,0003,16232x10,0001,000,00010,000100x1,000,000100,000,000100,0001,000x查询越多优势越明显5. 一个具体例子假设 X {0,1}³3 个二进制属性共 8 种组合。我们有 n100 条数据想回答 |Q|100 个线性查询。初始状态合成分布 D₁ [1/8, 1/8, ..., 1/8]均匀分布。真实数据分布 D_real [0.10, 0.05, 0.15, 0.10, 0.20, 0.08, 0.12, 0.20]。第 1 轮指数机制选中查询 q 第一个属性 1。真实答案: 0.10 0.05 0.15 0.10 0.40合成答案: 0.50均匀分布下一半的个体第一个属性1误差: 0.10乘法权重更新提高前 4 种组合的权重降低后 4 种组合的权重。第 2 轮指数机制选中查询 q 第二个属性 0 且第三个属性 1。真实答案: 0.15 0.12 0.27合成答案: 约 0.25经过了第一轮修正误差: 0.02乘法权重更新进一步微调。第 20 轮经过 20 轮迭代合成分布已经非常接近真实分布组合真实第 1 轮后第 5 轮后第 20 轮后0000.100.080.090.100010.050.060.050.050100.150.170.160.150110.100.110.110.101000.200.170.190.201010.080.090.080.081100.120.140.130.121110.200.180.190.20所有 100 个查询的误差都 ≤ 0.01。Python 代码实现下面我们用 Python 实现一个简化的 PMW 算法复现上面这个具体例子。代码会模拟 100 条数据记录8 种属性组合、随机生成 100 个线性查询然后运行 20 轮 PMW 迭代。import numpy as np # 设置参数 # 数据域 X {0,1}³共 8 种可能的属性组合 domain_size 8 num_records 100 num_queries 100 num_rounds 20 epsilon 1.0 # 总隐私预算 epsilon_per_round epsilon / num_rounds # 每轮隐私预算 learning_rate 0.5 # 乘法权重更新步长 η # 1. 模拟真实数据集 # 真实分布8 种组合的概率 true_distribution np.array([0.10, 0.05, 0.15, 0.10, 0.20, 0.08, 0.12, 0.20]) # 生成 100 条数据记录 np.random.seed(42) dataset np.random.choice(domain_size, sizenum_records, ptrue_distribution) # 真实数据直方图归一化 true_histogram np.bincount(dataset, minlengthdomain_size) / num_records print(真实数据直方图:, np.round(true_histogram, 3)) # 2. 生成随机查询集合 # 每个查询是一个长度为 domain_size 的向量元素在 [0,1] 之间 # q(D) (1/n) * Σ q(x_i) queries np.random.rand(num_queries, domain_size) # 计算所有查询在真实数据上的答案 true_answers queries true_histogram # 3. PMW 核心循环 # 初始化均匀分布 synth_dist np.ones(domain_size) / domain_size print(\n开始 PMW 迭代...\n) for t in range(1, num_rounds 1): # 计算所有查询在当前合成分布上的回答 synth_answers queries synth_dist # 计算每个查询的误差 errors np.abs(synth_answers - true_answers) # 指数机制选择误差最大的查询添加隐私保护噪声 # 每轮隐私预算为 epsilon_per_round scores errors * epsilon_per_round / 2 scores scores - np.max(scores) # 防止数值溢出 probs np.exp(scores) probs probs / np.sum(probs) # 按概率选择查询 chosen_idx np.random.choice(num_queries, pprobs) chosen_query queries[chosen_idx] # 获取真实答案和合成答案 v true_answers[chosen_idx] # 真实答案 u synth_answers[chosen_idx] # 合成答案 # 乘法权重更新 # 对每个 x ∈ X如果 q(x) 大满足条件且 v u低估提高权重 # 如果 q(x) 大满足条件且 v u高估降低权重 update_factor np.exp(learning_rate * (v - u) * (2 * chosen_query - 1)) synth_dist synth_dist * update_factor synth_dist synth_dist / np.sum(synth_dist) # 归一化 if t % 5 0 or t 1: max_error np.max(errors) avg_error np.mean(errors) print(f第 {t:2d} 轮 | 最大误差: {max_error:.4f} | 平均误差: {avg_error:.4f}) # 4. 最终结果对比 print(\n * 50) print(PMW 估计 vs 真实分布) print( * 50) final_errors np.abs((queries synth_dist) - true_answers) print(f\n所有 {num_queries} 个查询的最大误差: {np.max(final_errors):.4f}) print(f所有 {num_queries} 个查询的平均误差: {np.mean(final_errors):.4f}) print(f\n{组合:6} | {真实:8} | {PMW估计:8} | {误差:8}) print(- * 35) for i in range(domain_size): err abs(true_histogram[i] - synth_dist[i]) print(f {i:03b} | {true_histogram[i]:.4f} | {synth_dist[i]:.4f} | {err:.4f})代码说明这个实现使用指数机制代替直接选择最大误差查询差分隐私的关键然后通过乘法权重调整合成分布。每轮迭代中合成分布都会向真实数据靠近一步。你可以调整num_rounds、learning_rate和epsilon来观察不同参数对收敛速度和精度的影响。6. 与在线学习的巧妙联系PMW 算法的设计思路和**在线学习Online Learning**有着惊人的相似graph TB subgraph 在线学习 L1[初始化模型参数] L2[接收一个样本/问题] L3[做出预测] L4[看到真实标签] L5[计算损失并更新模型] L1 -- L2 -- L3 -- L4 -- L5 -- L2 end subgraph PMW 算法 P1[初始化合成分布] P2[用指数机制选一个查询] P3[用合成分布回答该查询] P4[看到真实答案] P5[计算误差并用乘法权重更新] P1 -- P2 -- P3 -- P4 -- P5 -- P2 end在线学习概念PMW 中的对应模型参数合成分布 D训练样本查询 q预测值q(合成分布)真实标签q(真实数据)损失函数梯度下降乘法权重更新PMW 本质上是在在线地学习真实数据的分布——每一轮选取一个最有信息量的查询用它的答案来修正当前分布。这正是为什么它比一次性加噪的拉普拉斯机制高效得多它迭代地从查询中提取信息而不是一次性处理所有查询。7. PMW 的局限与变体不是万能的PMW 虽然强大但也有其局限局限原因应对仅适用于线性查询更新规则依赖线性性质对非线性查询需特殊处理空间复杂度高需要维护X**需要知道X**轮数 T 需预先设定隐私预算需按轮分配可用自适应停止改进重要变体Multiplicative Weights with Exponential Mechanism (MWEM)Hardt、Ligett 和 McSherry 在 2012 年提出的变体是 PMW 家族中最著名的版本。它显式地使用指数机制选择查询每轮仅消耗少量的隐私预算。Iterative Database ConstructionRoth 和 Roughgarden 的版本更强调博弈论的解释。在线 PMW对动态数据流的版本不需要预先知道所有查询。graph TD A[Private Multiplicative Weights 家族] A -- B[原始 PMWHardt Rothberg (2009)] A -- C[MWEMHardt, Ligett McSherry (2012)] A -- D[Iterative DatabaseRoth Roughgarden] A -- E[在线 PMW动态查询流] C -- F[最实用的版本指数机制 乘法权重]8. 直观理解为什么它能成立压缩的力量想象你有两种方式描述一个数据集方式一拉普拉斯针对每个问题单独记录答案每个答案都加噪声。如果问题数量 |Q| 10,000你需要记录 10,000 个数字。方式二PMW先描述数据的分布比如 100 个可能的属性组合每种的概率然后用这个分布自动回答所有问题。你只需要维护 100 个数字。PMW 本质上在进行信息压缩用 O(|X|) 的参数来描述数据而不是用 O(|Q|) 的参数来描述所有可能的查询。由于 |X| 通常远小于 |Q|特别是当数据维度不高时这就产生了巨大的效率提升。graph LR A[原始数据集 Dn 条记录] -- B[合成分布|X| 个参数] B -- C[无限查询在合成分布上计算] B -- D[但只选 T 个最有价值的查询来更新] D -.-|修正| B主动学习的视角PMW 不是被动地回答所有查询而是主动选择那些最有信息量的查询。这就像学生复习时不是看所有课本内容而是只刷不会的题——显然高效得多。每次迭代PMW 做两件事诊断找出当前分布与真实数据差异最大即最不了解的查询修正根据这个查询的答案调整分布经过 T 轮那些最需要修正的查询都被处理了分布也就接近真实数据了。小结要点说明核心思想用合成分布逐步逼近真实数据关键机制指数机制选择最差查询 乘法权重更新分布样本复杂度O(√\适用范围线性查询集合有限数据域与在线学习的关系本质上是迭代学习过程的差分隐私版本PMW 算法展示了差分隐私中的一个重要设计范式与其直接保护每个查询不如构建一个受保护的数据模型然后在这个模型上自由回答问题。这种先建模、再回答的思路在后续的很多差分隐私算法中都有体现包括我们后面会讲的稀疏向量技术。下一讲我们将学习稀疏向量技术Sparse Vector Technique——另一种高效处理大量查询的方法它通过只回答足够大的查询来节省隐私预算。下一篇: 稀疏向量技术只回答大查询