具有最优性保证的对抗鲁棒聚类
在无监督学习的背景下,Lloyd 算法是最常用的聚类算法之一。本研究证明了在合适的初始化和小扰动的条件下,Lloyd 算法在从次高斯混合中扰动的样本上的误聚类率也在 O (log (n)) 次迭代后呈指数级下降的边界。
Sep, 2023
聚类是无监督机器学习中的关键问题,如何通过混合模型来研究聚类是常见的。本文首先通过契诺夫散度建立了聚类任何混合模型的一个普遍下界,然后证明在具有次指数尾部的混合模型中,迭代算法可以达到这个下界;此外,对于更适合使用泊松或负二项式混合模型的数据集,我们研究了属于指数族的混合模型,在这种混合模型中,我们证明了一种改进的 Lloyd 算法 ——Bregman 硬聚类,是速率最优的。
Feb, 2024
本文首次给出了一个多项式时间算法,用于在示例和标签中对抗性堕落下执行线性或多项式回归,并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。
Mar, 2018
本文采用一种剪枝方法,探讨基于 Bregman 距离的 k-means 聚类方法,以聚类可能被污染的数据为主要焦点,证明存在最优码本,提出具有剪枝参数的 Lloyd 算法,可根据数据选择启发式方法进行选择,并提供了一些实验结果。
Dec, 2018
研究了在高维高斯混合假设下,少量数据受到对手损坏的情况下的高效可学习性,提出了一种多项式算法并证明了在成分经过配对后在总变异距离上分离时,该问题是可多项式学习的;这种算法是第一个可处理 $k=2$ 的高斯混合问题的多项式时间算法,并使用基于 Sum-of-Squares 证明算法的技术,提出了一种新的用于高斯混合的鲁棒可辨识性证明方法和使用 SoS 可证明的反集中方法和新的特征距离度量组来解决问题。
May, 2020
本研究提出了一种黑盒对于线性可分聚类模型的对抗攻击方法,在不知道真实度量的情况下生成溢出性对抗样本,攻击强度高且难以被检测,被证明能够成功攻击多种数据集与聚类算法。
Nov, 2019
本研究探讨了增强 $k$-means 聚类算法对抗性操纵的挑战和策略,评估了聚类算法对抗性攻击的易受攻击性,强调了相关的安全风险,并研究了攻击强度对训练的影响,引入了有监督和无监督模型之间的可传递性概念,并突出了无监督模型对样本分布的敏感性。此外,我们还引入和评估了一种对抗性训练方法,该方法提高了在对抗情景下的测试性能,并强调了所提出训练方法中的各种参数的重要性,如连续学习、质心初始化和对抗步数。
Dec, 2023
本研究提出了一种新的检测离群值的高效算法,用于聚类混合的高斯模型,这种方法是鲁棒的,可以处理在数据中有少部分的失真或错误,它依赖于 TV 距离和方差有限度等假定条件,并使用极小化两种偏差的方法来修复度量误差和离群值异常。
May, 2020
本文研究了神经网络对抗性鲁棒性问题,通过理论和实验结果表明,增加未标记数据的使用,可以提高抗干扰泛化性能,并提出一种算法在 MNIST 和 Cifar-10 上的对抗训练方法。
Jun, 2019
在存在对抗离群值的情况下,我们开发了有效的算法来估计未知分布的低阶矩。这些算法的保证在许多情况下显著优于 Diakonikolas 等人、Lai 等人和 Charikar 等人的最佳先前算法,同时我们还展示了这些算法的保证与我们考虑的分布类别的信息论下界相匹配,这些改进的保证使我们能够在存在离群值的情况下提供改进的独立成分分析和学习混合高斯的算法,我们的算法基于对下面概念简单优化问题的标准平方和松弛:在所有矩与未知分布相同的分布中,找到与对抗性污染样本的经验分布在统计距离上最接近的分布。
Nov, 2017