BlueDown：在同等差分隐私保证下降低美国人口普查后处理误差的简洁块层次回归算法

《SCIENCE》：Denoising the US Census: Succinct block hierarchical regression

　　

2020年美国人口普查（United States Census）采用差分隐私（differential privacy, DP）保护个体机密性，在汇总人口统计测量中加入校准噪声，随后将这些测量协调为人口表。研究人员开发了BlueDown，一种后处理算法（postprocessing algorithm），其结合线性回归（linear regression）与约束优化（constrained optimization）技术，并利用测量结构提升效率。在2020年人口普查数据上，BlueDown将县级（county level）按种族分组（groupings by race）的误差降低21%至36%，并将所有县级分组的误差降低9%至58%；在普查区级（tract level），其将按住房类型（housing type）分组的误差降低38%至61%。这些增益未以机密性或计算效率为代价，并将提高依赖这一权威数据集（definitive dataset）的研究的有效性，以及用于指导每年超过$1.5 trillion联邦支出分配的分析的有效性。

研究背景与问题：美国十年一次人口普查（US Census）数据决定国会席位分配，并用于指导每年超过$1.5 trillion的联邦资金分配，也服务于市政与基础设施规划以及公共卫生、社会学、政治学、经济学研究。美国法典第13编要求个体回答必须保密。历史上，美国人口普查局依赖启发式数据交换技术保护受访者隐私；但2010年人口普查后开展的模拟重建攻击显示这些技术存在严重缺陷，暴露约5000万至1.8亿个体数据。该隐私失败促使普查局在2020年人口普查中采用基于差分隐私（differential privacy, DP）的数学严格披露避免框架。该框架向机密普查返回的汇总加入校准离散高斯噪声，产生可公开的噪声测量；DP提供数学保证限制任何单一个体对发布输出的影响，但所需噪声必然损害统计效用。为权衡隐私与效用，普查局开发TopDown算法作为2020年披露避免系统（Disclosure Avoidance System, DAS）核心。TopDown处理从 Nation 到 census block 的六个地理层级、超过100亿噪声测量，通过大规模约束优化恢复所需不变量并产生一致的微观数据明细文件（Microdata Detail File, MDF）；但其按地理层级顺序处理，在产生各地理单元估计时未最优结合所有可用测量。尤其种族相关查询以及县（county）和普查区（tract）级分析的误差受到研究者关注。因此，Ghazi et al.开展本研究，开发BlueDown后处理算法，以在相同强保密保证与计算效率下降低协调后人口表误差。

研究人员开展的研究、结论与意义：Ghazi et al.开发了BlueDown，将线性回归与约束优化技术结合，并利用测量结构提升效率。其关键是以统计上原则化的层次回归增强TopDown的二次优化核心：计算所有地理单元的最佳线性无偏估计（best linear unbiased estimator, BLUE），整合全部测量而非仅单个地理单元及其包含它的较大地理，且计算时间随地理区域数量线性增长；随后将BLUE估计送入基于TopDown的额外优化程序，以满足非负整数计数等强制结构约束。2020年人口普查数据上，BlueDown在县和普查区级直方图查询中降低估计误差9%至44%，对种族和集体宿舍（group quarters）分组改善更大，同时满足同样隐私保证和普查局施加的所有结构约束。该研究的重要意义在于：在不牺牲机密性或计算效率的前提下提高这一权威数据集的效用，改善依赖普查数据的研究及用于指导联邦支出分配的分析的有效性；其层次回归框架还可推广到其他树状噪声测量系统。论文发表在《SCIENCE》。

关键技术方法（不超过250字）：研究人员将后处理表述为带等式约束的广义线性回归并计算最佳线性无偏估计（BLUE）；利用地理编码树（geocode tree）的块层次结构，以自底向上和自顶向下两遍算法线性时间整合全部测量；利用测量工作负载与协方差的Kronecker积对称性，以成对32×32矩阵表示中间协方差，压缩表示近2000倍；在自顶向下阶段采用与TopDown相关的二次规划和混合整数规划，满足非负整数、结构零及住房占用上下界；评估以公开2020 MDF作为机密普查编辑文件（Census Edited File, CEF）替代，按生产噪声分布与隐私预算独立采样10个噪声测量文件（Noisy Measurement File, NMF），并与TopDown基线比较?₁误差。样本队列来源为2020年美国人口普查公开MDF及独立采样的10个NMF。

研究结果：

普查隐私流程（The Census privacy pipeline）：研究人员梳理了DAS将机密普查返回转化为可发布数据产品的管线：原始返回经编译、去重、插补和制表形成CEF；向CEF上的线性查询加入独立离散高斯噪声形成可公开但需后处理的NMF；去噪算法（TopDown或BlueDown）输入NMF及政策强制不变量和结构约束，输出每人一条记录的MDF；MDF再聚合产生Redistricting Data Summary File。地理编码树含 country、state、county、tract、block group、block 六层，2020年有5,892,698个非空块；50个州和Washington, DC各为州级节点，37个含部落地区的州另有美洲印第安人和阿拉斯加原住民（American Indian and Alaska Native, AIAN）平行核算脊，共88个州级节点。Redistricting Data以家庭或集体宿舍类型、Hispanic或Latino origin、投票年龄、种族四类属性形成2016个人口统计桶；每个地理节点测量2603个线性查询。约束包括州和国家总人口精确发布、结构零、非负整数、住房单元和集体宿舍设施占用上下界。结论：BlueDown位于同一管线的去噪步骤，输入同一NMF并输出满足约束的MDF。

最优层次估计（Optimal hierarchical estimation）：研究人员在暂时忽略不等式和整数约束时，将后处理形式化为广义线性回归问题；每个节点观测y_v=W_vx_v^?+η_v，其中x_v^?为真实人口计数向量，W_v为已知工作负载矩阵，η_v为零均值离散高斯噪声且具有已知对角协方差Σ_v；地理编码树的父子结构施加等式约束，内部节点真实计数等于其子节点真实计数之和。该约束线性回归的统计最优解为约束广义最小二乘估计，即BLUE。结论：后处理可表述为BLUE问题，但朴素计算需形成并反转覆盖全部地理节点和人口统计桶的协方差矩阵，在普查规模不可行。

层次BLUE算法（A hierarchical BLUE algorithm）：研究人员利用工作负载、协方差和等式约束可按节点分解、仅由父子一致性约束连接的结构，设计两遍地理编码树算法：自底向上从叶节点开始，每节点局部估计为单节点广义最小二乘解；内部节点合并节点自身局部估计与由子节点估计聚合得到的估计，因孩子估计本身为BLUE且与节点自身测量独立，可用显式公式合并并纳入连接等式约束；自顶向下将“外部”估计与自底向上子树估计合并，外部估计由父节点外部和局部估计合并再减去兄弟子树估计得到。证明所得估计器恰为全约束回归BLUE（不含不等式约束）。结论：可在节点数线性时间内计算全局BLUE。

简洁矩阵代数（Succinct matrix algebra）：研究人员观察到63个普查种族类别被对称测量：工作负载中每个查询要么以相同噪声尺度逐一种族枚举，要么对所有种族聚合；工作负载可分解为32×32非对称分量与63个对称种族类别上的单位矩阵和全1向量的Kronecker积。该结构在树算法所有操作下保持，故每个中间协方差矩阵可用一对32×32矩阵表示而非单个2016×2016矩阵。结论：表示规模压缩近2000倍，矩阵乘法和求逆加速约10⁴倍，使块层次BLUE可部署于普查规模。

施加普查约束（Enforcing census constraints）：两遍BLUE满足等式约束，但不满足普查局要求的非负整数计数和每个普查块住房类型总数上下界。BlueDown保留逐节点处理和自底向上BLUE，将自顶向下替换为与TopDown密切相关的逐层约束优化：每层求解二次规划，在所有等式、不等式和非负约束下最小化到底部BLUE估计的马氏距离（Mahalanobis distance），随后用整数规划将连续解取整为满足同约束的整数计数，并使用标准混合整数求解器。无不等式和整数约束时，该程序退化为BLUE算法的线性自顶向下过程；约束活跃时可视为将TopDown优化推广到自底向上计算的非对角协方差。借助辅助变量和Kronecker结构，目标从每个子节点约4×2016²≈1.6×10⁷个单项降至2016项，并增加2080个额外变量和等式约束。结论：BlueDown满足结构约束，优化问题规模与运行时间与TopDown相当；不等式和整数约束使估计器有偏，但经验上提高广泛查询准确性。

2020年普查数据准确性增益（Accuracy gains on 2020 Census data）：
评估方法（Evaluation methodology）：因真实CEF机密，研究人员采用普查局提出的方法，以公开2020 MDF作为CEF替代；使用与生产2020年普查相同的噪声分布和隐私预算独立采样10个NMF；在每个NMF上运行BlueDown与TopDown基线，以算法输出与MDF之间在各地理层级多种聚合上的?₁距离衡量准确性；误差按每个查询的TopDown误差中位数归一化，值低于1.0表示改善。结论：建立了可比较的准确性评估框架。

广泛准确性改进（Broad accuracy improvements）：在US详细查询及州、县、普查区、块组、块层级所有比较上，BlueDown显著提高准确性，县和普查区增益最大；县边缘查询误差降低9%至30%，普查区降低12%至44%，州和块组分别仅3%至10%和0.5%至7%；10次重复间方差在州级以下较小；改善幅度随查询和层级变化，通常对隐私预算在较低层级分配给相似查询较多者改善更大。结论：BlueDown广泛降低误差，县和普查区层级对立法再分配和联邦资金分配具有直接政策意义。

种族和集体宿舍查询（Race and group-quarters queries）：县级每个单一种族类别及两类以上种族查询误差降低21%至36%，普查区降低12%至16%；集体宿舍查询在县、普查区、块组多数设施类型误差降低32%至61%，包括惩教设施、护理设施、学生住房和军事营房；块级机构设施类型类似改善，非机构设施类型约20%的较小但显著改善；家庭查询在普查区和县分别改善38%和12%，但在块和块组改善很小。部分增益源于将无集体宿舍块的结构零约束纳入BlueDown自底向上过程，有效增强父节点和其他住房类型对应隐私预算。结论：BlueDown显著改善种族和集体宿舍查询，与投票权法执行、少数族裔服务项目分配及按种族死亡率等公共卫生统计相关。

偏倚降低和小人口地理（Bias reduction and small-population geographies）：两种算法均因非负约束出现系统偏倚：小地理总人口倾向高估、大地理低估。按真实人口分箱后，BlueDown在县和普查区最小和最大人口箱均大幅降低总人口平均符号误差（偏倚），块组和块降低较小；县和普查区最小人口箱的偏倚降低对应绝对误差特别大的改善。结论：BlueDown降低小人口地理的偏倚与误差，而该问题此前被视为TopDown的重要数据质量关切。

讨论部分总结：讨论与展望（Outlook）指出，BlueDown证明通过算法进步可在不增加隐私成本下实质性提高普查数据产品准确性；将隐私预算分配策略与BlueDown联合优化而非仅针对TopDown，可能在未来数据发布中带来额外增益。2026年6月美国商务部宣布噪声注入不再符合部门政策；由于BlueDown是纯后处理算法，作用于与TopDown相同的噪声测量，也可回顾性应用于2020年人口普查以改善现有数据产品。在直接使用普查估计作为分子或分母的任务中，准确性改进应直接转化为实际影响；当少数人承担不成比例权重时误差尤为关键，集体宿舍查询显示大幅准确性改进，包括小区域层级（如惩教设施误差降低>50%），单个宿舍、营房或监狱可能占农村地区人口很大比例，差异会影响地方服务规划；当法定阈值尖锐且计数边际变化会翻转资源分配分类时，准确性也特别重要，例如联邦交通资金按普查统计在200,000居民上下分设资金池。进一步研究人口构成、城市化及其他因素在社区间估计准确性中的作用，可能揭示下游政策影响以及隐私预算分配和地理脊等上游参数选择的影响。BlueDown的层次回归框架并非美国普查专用，可应用于任何噪声测量按树组织并由父子一致性约束连接的系统，潜在应用包括其他国家普查机构的统计系统、社会与健康科学中的层次调查设计，以及测量跨组织或地理层级聚合的归因系统。Su et al.最近分析表明，2020年人口普查使用改进隐私会计后提供比原报告更强的隐私保证；因BlueDown作用于同一噪声数据，这些更紧保证也适用于它，从而互补改善整体隐私-准确性权衡。

研究结论（译）：这些结果表明，采用BlueDown可实质性改善依赖普查数据的下游政策决策和科学分析。