揭示k-medoids与核密度估计在向量量化中的深层联系
Kernel $k$-Medoids as General Vector Quantization
- 用二次无约束二值优化统一建模k-medoids与核密度估计
- 证明核密度估计是k-medoids的特例，仅需温和核假设
- 为向量量化权重参数提供几何解释，适合机器学习理论研究者
向量量化（VQ）在机器学习和数据压缩中广泛应用，因其简洁性和可解释性而备受青睐。在硬向量量化方法中，k- medoids聚类和核密度估计（KDE）代表了两种看似无关的范式——前者基于距离，后者基于概率密度匹配。本文通过二次无约束二值优化（QUBO）的视角探究二者联系。我们对比了用于k-medoids的启发式QUBO（平衡中心性与多样性）与从KDE-VQ最小化最大均值差异推导出的严格QUBO。令人惊讶的是，在核特征映射满足温和假设条件下，KDE-QUBO是k-medoids-QUBO的一个特例。这一发现揭示了两类方法之间的深层结构关联，并为QUBO形式中权重参数的几何意义提供了新见解。
原文摘要 · Abstract (English)
Vector Quantization (VQ) is a widely used technique in machine learning and data compression, valued for its simplicity and interpretability. Among hard VQ methods, $k$-medoids clustering and Kernel Density Estimation (KDE) approaches represent two prominent yet seemingly unrelated paradigms -- one distance-based, the other rooted in probability density matching. In this paper, we investigate their connection through the lens of Quadratic Unconstrained Binary Optimization (QUBO). We compare a heuristic QUBO formulation for $k$-medoids, which balances centrality and diversity, with a principled QUBO derived from minimizing Maximum Mean Discrepancy in KDE-based VQ. Surprisingly, we show that the KDE-QUBO is a special case of the $k$-medoids-QUBO under mild assumptions on the kernel's feature map. This reveals a deeper structural relationship between these two approaches and provides new insight into the geometric interpretation of the weighting parameters used in QUBO formulations for VQ.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。