Jul, 2016

度量扰动韧性

PDF
TL;DR本文研究了计算机科学中由 Bilu, Linial （2010）和 Awasthi, Blum, Sheffet（2012）提出的微扰鲁棒性概念。作者考虑了一类基于中心的聚类问题，包括 k-means，k-median 和 k-center 等问题，并给出了一个用于聚类 2 - 扰动抵抗性实例的精确算法。该结果改进了 Balcan 和 Liang（2016）的结果，并且是最紧密的结果，除非 NP = RP，否则没有多项式时间算法能够解决（2-ε）- 扰动强度抵抗实例。作者还展示了该算法在满足比扰动强度抵抗更弱和自然的度量扰动强度抵抗条件的实例上的表现。
发现论文，激发创造
  • 扰动鲁棒性下的聚类

    通过小乘的扰动，可在目标基础聚类问题中进行最优聚类，本文提供了几个在此框架内的结果并且基于新的关联准则提供了基于中心的和最小和聚类的算法。

    Dec, 2011

  • 聚类中的数据稳定性：深入研究

    本文考虑了 Bilu 和 Linial（2010）提出的模型，研究了最佳聚类不发生变化的问题，我们发现即使问题是 NP 困难的，有时候也可能获得有效算法，这些算法对于特定的多项式扰动是鲁棒的。同时，我们证明了该区间内的乘法鲁棒性参数可能太强，以至于聚类问题变得微不足道，只有一个较窄的区间是有趣的。

    Jul, 2011

  • 抗扰动 $k$- 中心聚类

    该研究提供了一种在输入稳定条件下解决对称和非对称 $k$-center 问题的算法，并且这种算法在输入距离 2 - 扰动稳定时可以在最劣情况下保证聚类近似算法的最优解。

    May, 2015

  • 基于稳定性扰动的中心聚类

    本文证明了当度量空间中没有 Steiner 点时，对于任何以中心为基础的聚类目标函数（例如 k - 中位数，k - 均值和 k - 中心），我们可以有效地找到最优的聚类，假设仅稳定于基础度量的 3 倍扰动，对于一般的度量，稳定性因子为 2 + 根号 3 扰动，我们还在相关条件下提出了 NP 困难性结果。

    Sep, 2010

  • 欧几里得 k-means 的稳定实例聚类

    本文研究在实际应用中，哪些加性扰动稳定性的实例可以设计有效算法，并证明它们能找到最优聚类。我们提出了一种稳定性定义，并设计了算法以证明稳定实例的最优聚类。当实例具有一定的分离性时，我们显示出一种具有证明保证的鲁棒算法，也能容忍异常值。通过研究真实数据集的稳定性，我们补充了这些结果，并展示了我们的算法在这些基准数据集上的表现。

    Dec, 2017

  • 弹性：在任意异常值存在情况下进行学习的标准

    引入鲁棒性标准使属性的计算更加稳健，包括鲁棒分布学习、鲁棒估计碰巧矩阵模型和鲁棒均值估计，提供新的信息论和算法结果。

    Mar, 2017

  • 广义韧性与健壮统计学

    通过在任意 Wasserstein 距离下考虑扰动，实现鲁棒统计推断的推广。在这种情况下，我们首次证明了一个称为广义弹性的性质，并通过 Moment 或超对交条件证明了这种弹性的有效性。最后，我们提供了两种设计具有良好有限样本速率的 MD 估计器的不同方法，包括弱化差异和扩展分布集的方法，回顾了与 GAN 领域最近相关的研究结果。

    Sep, 2019

  • 离散几何空间中鲁棒聚类的参数化逼近

    本文介绍了 Robust k-z 聚类和其在度量空间、算法公平性、欧几里得空间和 FPT 近似等领域的应用，提出了相应的算法，其中在特殊的欧几里得空间中得到了较好的近似结果。

    May, 2023

  • 利用 1-Center 和 1-Mean 聚类法处理带有离群值的分布式学习的近最优鲁棒聚合规则

    该研究论文讨论了拜占庭机器学习中安全抵御拜占庭机器的关键问题，并提出了一种基于异常值鲁棒聚类的近似聚集器，该方法在度量标准上表现出优越性，为均匀和异构情况提供了近乎最优的聚集器。基于研究结果，提出了一个两阶段的安全聚集框架，并通过图像分类实验验证了该框架的有效性。

    Dec, 2023

  • 个体公平聚类的改进近似算法

    此论文介绍了一种可行的算法，用于从簇成员与簇中心之间的距离范数角度出发解决公平聚类问题，并对相应指标（如 bicriteria）进行了优化；同时，提供了一种基于模类约束的距离范数成本设施位置 16^p - 近似算法，并将借鉴此算法，将个体公平聚类转化为更一般如群体公平聚类的解法。

    Jun, 2021