Tag: Unsupervised Learning

由Google研究的Graph Mining团队的Vincent Cohen-Addad和Alessandro Epasto发布 聚类是无监督机器学习（ML）中的一个核心问题，广泛应用于行业和学术研究的多个领域。在其核心，聚类包括以下问题：给定一组数据元素，目标是将数据元素分成组，使得相似的对象在同一组中，而不相似的对象在不同的组中。60多年来，这个问题在数学、计算机科学、运筹学和统计学中以其无数的变体进行了研究。聚类的两种常见形式是度量聚类，其中元素是度量空间中的点，例如k-means问题，和图聚类，其中元素是图的节点，其边表示它们之间的相似性。 在k-means聚类问题中，我们给出了度量空间中的一组点，目标是识别k个代表点，称为中心（在此处表示为三角形），以最小化每个点到其最近中心的平方距离之和。来源，版权：CC-BY-SA-4.0 尽管算法设计方面的聚类文献很广泛，但很少有实际工作专注于在聚类过程中严格保护用户的隐私。当聚类应用于个人数据（例如用户所做的查询）时，有必要考虑在实际系统中使用聚类解决方案的隐私影响以及输出解决方案揭示有关输入数据的信息量。 为了在严格意义上保护隐私，一个解决方案是开发差分隐私（DP）聚类算法。这些算法确保聚类的输出不会揭示有关特定数据元素（例如，用户是否进行了给定查询）或有关输入图中的敏感数据（例如，社交网络中的关系）的私有信息。鉴于隐私保护在无监督机器学习中的重要性，在最近几年中，Google一直在研究不同ially private metric或graph clustering和各种情境下的差分隐私，例如热图或设计DP算法的工具。 今天我们很高兴地宣布两个重要的更新：1）一种新的差分隐私层次图聚类算法，我们将在ICML 2023上展示，2）可扩展的差分隐私k-means算法代码的开源发布。此代码使用分布式计算将差分隐私k-means聚类应用于大规模数据集。在这里，我们还将讨论我们在健康领域最近推出的用于向公共卫生当局提供信息的聚类技术的工作。 差分隐私层次聚类 层次聚类是一种流行的聚类方法，它包括将数据集递归地分成越来越细的群集。生物学中著名的层次聚类的例子是分类系统，其中地球上的所有生命都被分成越来越细的组（例如，王国、门、纲、目等）。层次聚类算法接收表示实体相似性的图作为输入，并以无监督的方式学习这种递归分区。然而，在我们的研究中，尚不知道任何算法可以计算带有边缘隐私的图的层次聚类，即保护顶点交互的隐私。 在“带有可证明逼近保证的差分隐私层次聚类”中，我们考虑在DP上下文中可以对问题进行多好逼近，并对隐私保证建立了坚实的上限和下限。我们设计了一种多项式运行时间的逼近算法（其类型的第一个算法），它具有随节点数n（约为n 2.5 ）缩放的附加误差和O（log ½ n）的乘法逼近，其中乘法误差与非私有设置相同。我们进一步为任何私有算法提供了一个新的附加误差下限（约为n 2 ），并提供了一个与此下限相匹配的指数时间算法。此外，我们的论文包括一种超越最坏情况的分析，重点关注分层随机块模型，这是一种展现自然分层聚类结构的标准随机图模型，并引入了一种私有算法，其返回与最优解相比可以忽略不计的附加成本，这再次匹配非私有状态下的最先进方法。我们相信这项工作扩展了图数据上隐私保护算法的理解，并将使这些设置中的新应用成为可能。 大规模差分隐私聚类 我们现在转换话题，讨论我们在度量空间聚类方面的工作。在差分隐私度量聚类的先前工作中，大多数专注于提高算法在 k-means…