Oct, 2023

公平的流式主成分分析：统计和算法视角

PDF
TL;DR公平主成分分析（Fair Principal Component Analysis，fair PCA）是一个问题设置，旨在在执行主成分分析的同时，使得所得到的表示在条件敏感属性的情况下相互匹配的分布公平。然而，现有的公平主成分分析方法存在两个主要问题：从理论上讲，公平主成分分析在可学习性方面没有统计学基础；从实际上讲，有限的内存限制了现有方法的使用，因为它们明确要求对所有数据进行完全访问。在理论上，我们使用一个称为 “可能近似公平和最优学习”（PAFO-learnability）的新概念，严格地制定了公平主成分分析。在实际上，受近期应对内存限制的流数据算法的最新进展的启发，我们提出了一种称为 “公平流式主成分分析（fair streaming PCA）” 的新设置，以及一种内存高效的算法，公平噪声幂法（fair noisy power method，FNPM）。然后，在公平主成分分析文献中，我们提供了该算法的统计保证，这是其首次存在。最后，我们验证了我们算法在现实世界数据集上的效果和内存效率。
发现论文，激发创造
  • 高效公平主成分分析

    提出一种适应性一阶算法，通过使用 Pareto 最优性的概念来学习保持公平性，同时略微牺牲重构损失的子空间，证明了该算法的解对于所有敏感群体都属于 Pareto 前沿，从而保证了整体重建损失和公平约束之间的最优权衡，并提供了收敛分析和验证了该算法在各种数据集上的优异性能。该算法可有效地将不公平决策降至最低，并可推广至多组敏感特征。

    Nov, 2019

  • 公平主成分分析的凸优化方法

    本文研究了 PCA 背景下的公平性问题，并提出了 “公平降维” 的定义，即保护类别的信息不能从降维后的数据点推断出来。作者发展了凸优化公式来提高 PCA 和核 PCA 的公平性，并在几个数据集上展示了其有效性。最后，演示了如何使用该方法对健康数据进行公平（针对年龄）聚类，该数据可以用于设定健康保险费率。

    Feb, 2018

  • 公平主成分分析与滤波器设计

    本文探讨了公平主成分分析 (FPCA) 的问题，并且提出了使用次梯度下降来解决此问题的方法，该方案可以使优化结果更易于计算且结果更精确。

    Feb, 2020

  • 大数据集的主成分分析算法

    本文介绍了一种基于随机方法的主要成分分析算法，该算法适用于无法存储在内存中的大型数据集，并通过多个数值实例展示了其性能。

    Jul, 2010

  • 分布式和流式模型中的最优主成分分析

    该论文提供了改进的分布式 PCA 和流式 PCA 算法，旨在找到矩阵的最佳秩 - k 逼近。

    Apr, 2015

  • 基于 MMD 的 Stiefel 流形优化的快速高效公平 PCA 算法

    本文提出了一种公平的主成分分析方法，该方法使用最大均值差异法对不同保护类别的条件分布进行降维，并将多目标策略与数据降维技术相结合，通过在 Stiefel 流形上的非凸优化过程，优化约束条件下的主成分分析，得到较高的计算效率和分类精确性。使用合成数据和 UCI 数据集进行的实验结果表明该方法在自变量解释度，公平性和运行时间方面均优于现有工作。

    Sep, 2021

  • 异常值鲁棒主成分分析的近线性时间和流式算法

    本研究主要研究经典问题 PCA 中的异常值问题，提出了近线性时间的近似最优解鲁棒 PCA 算法以及单遍流式鲁棒 PCA 算法，并进行了相关的理论分析。

    May, 2023

  • 通过测地线下降实现分布鲁棒公平主成分

    本文提出一种在主成分分析中内在于目标函数中的公正准则的分布式稳健优化问题，通过采用超越最小二乘意义的子群重构误差之间的重构误差差异，平衡了总体重建误差和子群之间的重建误差差异，以及实验证明该方法较其他现有方法有明显优势。

    Feb, 2022

  • 公平主成分分析的代价：多一维

    本研究探讨了标准的 PCA 降维技术是否会无意中为两个不同人群产生不同的数据表示，提出了公平 PCA 的概念，并给出了一个多项式时间算法来找到数据的低维度表示，最终在真实世界的数据集上证明了该算法可以用于有效生成公平的低维表示。

    Oct, 2018

  • 改进的分布式主成分分析

    本文研究具有多台服务器的分布式计算环境，通过开发 PCA 算法来处理点集的低维子空间问题，进而解决异常检测以及聚类等计算问题，提出的新算法显著降低了 $k$-means 聚类与相关问题的计算以及通讯成本，并且经过实验验证，在解决方案质量方面具有忽略不计的退化。

    Aug, 2014