“Thanks for sharing your great work!”
BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed Bandits
用多臂老虎机把 k-medoids 聚类加速到近线性时间
k-medoids 要求聚类中心是真实数据点并支持任意距离度量,但 PAM 等主流算法每轮迭代是 n 的平方复杂度,难以用于大数据集。BanditPAM 借用多臂老虎机的随机化技术,把每轮 PAM 迭代的复杂度从 O(n²) 降到 O(n log n),并在对数据的一定假设下以高概率返回相同的结果。在多个真实数据集上,它与最先进的 PAM 类算法结果相同,速度最多快 4 倍,距离计算最多少 200 倍。
HN 上主要是作者本人在讨论中介绍这项把最优已知算法从 O(n²) 提速到 O(n log n) 的工作,并获得其他评论者的称赞。
学习路径
读这篇之前,按顺序读书架上的 1 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出候选里只有 Hyperband 一篇与目标论文的「用多臂老虎机加速机器学习计算」思路相近,所以路径很短。
- 1
Hyperband 把多臂老虎机的自适应资源分配与早停用于超参数搜索,与 BanditPAM 把老虎机思想用于加速聚类相呼应。
读successive halving 与自适应分配预算的思想;超参数搜索的实验可略读。
- 2BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed Bandits
把 k-medoids 的 PAM 算法中每一步的最优选择转化为多臂老虎机问题,实现近线性时间。
读BUILD 与 SWAP 阶段如何变为最优臂识别,以及置信区间驱动的随机化抽样。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“In our NeurIPS 2020 paper, BanditPAM, we sped up the best known algorithm from O(n^2) to O(nlogn).”
“In our NeurIPS 2020 paper, BanditPAM, we sped up the best known algorithm from O(n^2) to O(nlogn) by using techniques from multi-armed bandits.”
- BanditPAM, an improved alternative to k-means ↗lord_sudo · 2021-11-25 · 3 分