面向重尾和污染数据的鲁棒差分隐私主成分分析方法

《Statistical Analysis and Data Mining: An ASA Data Science Journal》:Robust and Differentially Private Principal Component Analysis

【字体: 大 中 小 】 时间:2025年12月15日 来源:Statistical Analysis and Data Mining: An ASA Data Science Journal

编辑推荐:

  本文提出了一种适用于重尾和潜在污染数据的差分隐私(DP)主成分分析(PCA)新方法。该方法利用广义空间符号和Kendall's tau矩阵,通过有界变换确保数据处理的鲁棒性,并引入高斯噪声机制满足(ε,δ)-DP。理论分析和大量实验表明,该方法在非高斯或污染数据设置下,在统计效用和子空间恢复方面均优于现有方法,为隐私保护下的稳健数据分析提供了有效工具。

  
1 引言
随着数据量和种类的增长,理解数据结构变得日益重要。主成分分析(PCA)是一种基本而强大的降维方法,用于识别定义低维子空间的主成分方向,以捕获数据中固有的最大方差。近几十年来,限制数据分析中敏感个人信息的披露已成为一个重要问题。为此,差分隐私(DP)已成为确保隐私保障的事实标准。原始的DP概念,称为ε-DP,由Dwork等人提出。考虑一个随机化机制,该机制从数据集输出一个随机扰动的统计量。如果对于任何相邻数据集(最多相差一条记录),输出分布在任意单个个体记录被替换时保持不可区分性,则该机制满足ε-DP。隐私参数ε表示隐私保护的程度。DP的扩展提供了更灵活的不可区分性度量框架。为了设计满足给定DP水平的机制,常见方法是对感兴趣的统计量添加适当缩放的随机噪声。例如,一个实值随机化机制如果添加服从尺度参数与灵敏度成比例的拉普拉斯分布的噪声,则满足ε-DP。此外,还提出了各种旨在增强效用的DP机制。
除了隐私性,鲁棒性的重要性也日益受到重视。在实践中,数据可能是重尾的,偏离高斯假设,或包含异常值和异常情况。除了这种自然的不规则性,恶意用户可以通过向训练集注入中毒数据来破坏模型训练。因此,开发既私有又鲁棒的统计方法对于现代数据分析至关重要。然而,仅靠DP并不能保证鲁棒性,因为差分私有模型可能仍然容易受到对抗性攻击。此外,如果不考虑鲁棒性,异常值的存在可能会大大增加DP方法所需的噪声规模(例如,灵敏度),导致效用严重损失。
本文开发了一种鲁棒且差分隐私的PCA方法。所提出的方法简单、易于计算,并允许任意数量的主成分方向。该方法的鲁棒性通过利用两个最近开发的工具来保证:Raymaekers和Rousseeuw提出的广义空间符号,以及Han和Liu研究的Kendall's tau的矩阵变量扩展。通过将由此产生的鲁棒PCA框架适配以满足DP,我们的方法同时实现了隐私性和鲁棒性。
2 提出的方法
2.1 广义多元Kendall's Tau矩阵
考虑一对单变量随机变量,其总体Kendall's tau定义为符号函数期望。空间符号是单变量符号的多元扩展,它将向量映射到其归一化方向。这导致了Kendall's tau的多元版本。令观测值为随机向量,其独立副本为。总体多元Kendall's tau矩阵定义为期望外积。重要的是,当数据服从椭圆分布(包括高斯分布和重尾分布)时,Kendall's tau矩阵的特征向量与散度矩阵的特征向量一致,因此主成分方向也可以从Kendall's tau矩阵中获得。空间符号是一种自归一化过程,可减轻观测数据中严重异常值的影响。因此,Kendall's tau矩阵估计量的特征向量是有效且鲁棒的主成分方向估计量。
Raymaekers和Rousseeuw进一步将空间符号扩展为一类广义变换。对于正值尺度函数,考虑一个映射,称为广义空间符号。显然,空间符号是广义空间符号在尺度函数为欧几里得范数时的特例。通常,广义空间符号通过尺度函数对给定点进行重新缩放,使其方向保持不变,但长度变为尺度函数值。我们提出通过用广义空间符号替换空间符号来自然扩展多元Kendall's tau。
定义广义多元Kendall's tau矩阵为广义空间符号变换后向量外积的期望。只要变换形式适当,当数据服从椭圆分布时,该矩阵的特征向量与散度矩阵的特征向量相同。这证明了为了PCA的目的,将焦点转移到该矩阵的特征向量上是合理的。
广义空间符号被称为有界的,如果其值域范数有界。我们将注意力限制在有界的广义空间符号上。特别地,球形变换是有界的,因为其值域在单位球面上;缩尾变换也是有界的。相比之下,产生通常协方差矩阵的恒等映射是无界的。
对于简单随机样本,我们使用二阶U统计量作为广义Kendall's tau矩阵的估计量。广义空间符号的有界性使得该估计量对数据污染具有鲁棒性。此外,有界性也意味着估计量具有有限的灵敏度。因此,向估计量添加高斯噪声提供了Kendall's tau矩阵的差分私有估计量,其中高斯噪声的标准差与估计量的灵敏度成比例。
2.2 提出的差分隐私PCA
我们提出一种基于广义Kendall's tau矩阵的差分隐私PCA机制。记估计量关于Frobenius范数的灵敏度为Δ。如果广义空间符号是有界的,那么灵敏度是有界的。尽管数据的定义域是无界的,灵敏度也满足Δ ≤ 2c2。虽然估计量是矩阵值的,但向量化算子使我们能够应用标准的向量值高斯机制。对于数据集和隐私参数,我们定义一个随机化机制,其输出为估计量加上适当校准的高斯噪声。然后,我们将扰动矩阵的特征向量矩阵定义为私有主成分方向估计量。
命题表明,对于任何隐私参数和样本大小,只要数据域有界,该随机化机制满足(ε,δ)-DP。此外,最终的主成分方向估计量也满足(ε,δ)-DP。在机制中,私有主成分方向估计量矩阵被称为g-DPPCA。
3 统计效率与鲁棒性
3.1 模型
我们简要概述椭圆分布,并说明广义Kendall's tau矩阵如何在椭圆分布下实现有效的PCA过程。一个d维随机向量服从球对称分布,当且仅当其对任何正交变换具有分布不变性。对于球对称的随机向量,其密度函数具有特定形式。考虑一个对称正定矩阵,表示分布的散度。如果一个随机向量可以表示为位置参数加上散度矩阵的平方根与一个球对称随机向量的乘积,则该随机向量服从椭圆分布。我们记作,其中是球对称随机向量的密度函数。
我们考虑一个PCA问题,即从随机样本中估计散度矩阵的前几个特征向量。即使矩不存在,这个问题也是良定义的。当协方差矩阵存在时,它与散度矩阵仅相差一个常数因子,因此的特征向量与的特征向量相同。在这种椭圆数据模型下,我们可以通过估计广义Kendall's tau矩阵而不是协方差矩阵来进行PCA。
命题表明,对于椭圆分布的随机向量和有界的广义空间符号,广义Kendall's tau矩阵与散度矩阵具有相同的特征向量。此外,如果尺度函数是递减函数,则特征向量的顺序和重数也保持一致。广义Kendall's tau矩阵的正交不变性保留了散度矩阵的特征向量,而尺度函数的递减性确保了特征值的顺序得以维持。
3.2 子空间恢复的误差界
我们研究了g-DPPCA在椭圆模型下子空间恢复性能的统计效率。令随机样本来自椭圆分布,其中尺度函数是递减的。记为我们考虑的前k个领先特征向量。令为广义Kendall's tau矩阵的前k个特征向量。
为了推导私有估计的特征子空间与总体子空间之间的偏差,我们需要两个子空间之间的距离度量。我们使用sin Θ距离。令子空间和分别由矩阵的列张成。则和之间的sin Θ距离定义为最大主角的正弦值。
定理描述了私有估计的特征子空间如何很好地逼近总体子空间。在椭圆分布假设和下,私有子空间估计量与总体子空间之间的sin Θ距离以高概率有一个上界,该上界包含由隐私约束引起的项和样本估计效率引起的项。特征值间隙比出现在上界中是由于Davis-Kahan类型的定理。上界依赖于通过尺度函数对广义Kendall's tau矩阵的特定选择。
3.3 对抗数据污染的鲁棒性
关于误差界的结果对于即使没有有限矩的重尾椭圆分布也是有效的,这暗示了鲁棒性。本节我们通过经典的崩溃点分析和子空间恢复分析,进一步证明所提出方法在任意数据污染下的鲁棒性。
我们首先对g-DPPCA进行崩溃点分析。一个统计量的崩溃点是指能够导致该统计量产生任意大误差的最小污染样本比例。我们采用针对子空间值统计量提出的崩溃点概念。对于数据集,令为广义Kendall's tau矩阵的前k个特征向量矩阵。定义子空间值统计量为由这些特征向量张成的子空间。定理表明,该子空间统计量的崩溃点有一个下界。
考虑基于样本协方差矩阵进行PCA。令为相应的主成分子空间值统计量。则其崩溃点为1/n,随着样本量增加而趋于零。相比之下,定理中的下界随着样本量增加而趋于1/2。这表明在非私有设置下,g-DPPCA在崩溃点方面比基于标准样本协方差的估计量更鲁棒。
上述关于非私有g-DPPCA的论点揭示了g-DPPCA的鲁棒性。由于添加的噪声与数据独立,如果非私有估计量没有崩溃,则私有化后的估计量也能避免崩溃。这意味着私有主成分方向估计量也对任意数据污染具有鲁棒性。
接下来,我们研究在数据污染下子空间恢复的误差界,以衡量g-DPPCA在效用方面的鲁棒性。下面的定理为椭圆分布数据提供了这样一个界,其中一部分样本被任意污染。该定理对私有和非私有设置都有效。
定理表明,误差界包含三个部分:由隐私约束引起的项、与数据污染无关的项,以及与污染比例相关的项。当污染比例趋于零时,误差界恢复到的形式。如果污染比例固定,则即使在大样本极限下,误差界也不消失。然而,只要污染比例随样本量增加而趋于零,误差界的所有项都变为零。因此,在适度水平的数据污染下,g-DPPCA在满足差分隐私的同时仍能保持对污染的鲁棒性。
3.4 g-DPPCA的两个例子
本小节我们针对两种特定的广义空间符号选择:球形变换和缩尾变换,给出了子空间恢复误差上界的表达式。
首先考虑球形变换。在椭圆分布假设下,广义Kendall's tau矩阵的特征值可以表示为高斯随机向量的自归一化加权二次型的期望。命题描述了球形变换下的误差上界可以用散度矩阵的特征值和维度来表示。当信噪比足够大时,误差上界可以进一步简化。
接下来考虑缩尾变换。对于给定的半径,缩尾变换将范数小于半径的点保持不变,否则将其投影到半径球的边界上。命题描述了缩尾变换下的误差上界。如果选择的半径满足特定条件,则缩尾变换的效果与球形变换相似。对于高斯分布和多元t分布,选择半径是足够的。
在实际应用中,可以简单地将半径设置为一个固定值,或者基于先验或公开信息确定,或者使用一小部分隐私预算从观测到的配对差异中私有地估计分位数(如第一四分位数)来确定半径。
4 数值研究
4.1 对比方法
我们考虑了三种竞争方法:Dwork等人提出的Analyze Gauss(AG)机制,该机制向样本协方差矩阵添加高斯噪声;Cai等人提出的Spiked Covariance Gaussian PCA(SGPCA),该方法假设尖峰协方差模型和数据的亚高斯性,并将高斯机制应用于投影矩阵;以及Maunu等人提出的Noisy Stochastic Geodesic Gradient Descent(NSGGD),该方法通过在最优化问题上迭代近似测地梯度来求解私有PCA问题,并且被设计为对异常值具有鲁棒性。
4.2 模拟研究
为了评估所提出方法的实证性能,我们从椭圆分布生成模拟数据集,并拟合主成分方向的私有估计量。我们考虑了具有双尖峰结构的散度矩阵的两种椭圆分布:高斯分布和自由度为1的多元t分布(多元柯西分布)。为了研究方法的鲁棒性,我们还从5%污染的高斯分布中抽样数据。
模拟结果表明,在高斯分布下,提出的g-DPPCA方法与SGPCA性能相当或更优,但SGPCA在特定假设下可能表现更好。在重尾的多元t分布和污染高斯分布下,提出的g-DPPCA方法显著优于所有其他方法,包括AG、SGPCA和NSGGD,显示了其出色的鲁棒性。随着样本量的增加,所有鲁棒方法的性能都会提升,但非鲁棒方法(AG和SGPCA)在存在污染或重尾数据时性能会下降。改变隐私参数的实验也表明,g-DPPCA在广泛的隐私预算范围内都能保持良好的性能。
4.3 可视化:欧洲地图数据
我们还将私有PCA方法应用于Novembre等人研究的1387个欧洲个体的遗传数据上,以评估其实际效用。原始研究通过传统PCA将遗传数据投影到二维空间,结果与欧洲国家的地理布局高度相似。我们获得了数据的一个20维版本,并使用g-DPPCA计算前两个私有主成分,然后将数据投影到这两个主成分张成的子空间上,并根据个体的国籍进行着色。
可视化结果显示,g-DPPCA产生的投影图与非私有PCA的投影图非常相似,有效地捕捉了数据中潜在的地理结构。相比之下,NSGGD产生的投影图信息量较少,在第二个主成分方向上的国籍区分度下降。这表明g-DPPCA在保持隐私的同时,能够有效地恢复数据的底层结构。
结论
本文提出了一种新颖的鲁棒且差分隐私的PCA方法。该方法利用广义空间符号和Kendall's tau矩阵,适用于重尾和污染数据。理论分析证明了该方法在子空间恢复方面的误差界和鲁棒性保证。大量的数值实验表明,该方法在非高斯或污染数据设置下,在统计效用方面 consistently 优于现有方法。这项工作为需要在保护隐私的同时处理复杂现实数据的分析任务提供了有力的工具。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号