Stochastic complexity of vectors containing cluster structure

Abstract:This paper studies the problem of computing the stochastic probability (shortest code length) of the encoded vectors containing cluster structure using Normalized Maximum Likelihood (NML) model. This is of great theoretical and practical importance in data clustering based on Minimum Description Length (MDL) principle, such as for estimating the best number of clusters and best cluster structure for the data. Straightforward computation of the shortest code length of the vector containing cluster structure based on the NML model requires polynomial time with respect to the size of the vector and number of clusters. We show that this is a tractable problem by introducing a recursion formula for the efficient computation of normalizing constant from the NML model. The time complexity of the new formula is linear opposed to previous polynomial time with respect to the size of the vector and number of clusters.

8 pages, 2 figures. Originally published in the Proceedings of the International Workshop on Nonlinear Signal and Image Processing (NSIP 2007), Bucharest, Romania, 10-12 September 2007, pp. 164-169

Machine Learning (cs.LG); Information Theory (cs.IT); Machine Learning (stat.ML)

arXiv:2609.00084 [cs.LG]

(or arXiv:2609.00084v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2609.00084 arXiv-issued DOI via DataCite (pending registration)

Proceedings of NSIP 2007 - International Workshop on Nonlinear Signal and Image Processing (2007), pp. 164-169