包含簇结构的向量的随机复杂度

2026-09-02 1 阅读约1分钟阅读 Daniel Nicorici, Olli Yli-Harja, Jaakko Astola

arXiv:2609.00084v1 发布类型：new 摘要：本文研究了使用归一化最大似然（NML）模型计算包含簇结构的编码向量的随机概率（最短码长）的问题。这对于基于最小描述长度（MDL）原理的数据聚类具有重要的理论和实践意义，例如估计数据的最佳聚类数量和最佳聚类结构。基于 NML 模型直接计算包含簇结构的向量的最短代码长度需要关于向量大小和簇数量的多项式时间。我们通过引入递归公式来有效计算 NML 模型的归一化常数，证明这是一个易于处理的问题。新公式的时间复杂度与之前的多项式时间相对于向量大小和簇数量呈线性。

订阅66必读