Source-linked AI summary
Stochastic complexity of vectors containing cluster structure
Daniel Nicorici, Olli Yli-Harja, Jaakko Astola
TL;DR
The paper addresses polynomial-time computation of the NML shortest code length for vectors encoding cluster structure in MDL clustering. It introduces a recursion for the NML normalizing constant and reports linear-time computation instead of the previous polynomial-time method. This supports efficient encoding for MDL-based estimation of cluster number and structure.
Problem
Computing the NML shortest code length for clustering vectors was polynomial-time in vector size and cluster number, limiting efficient MDL clustering.
Method
The paper derives a recursion formula for efficiently computing the NML normalizing constant of clustering vectors using generating-function properties.
Results
The new computation has linear time complexity, compared with the previous polynomial-time method.
Takeaways & Limitations
Efficient NML encoding of clustering vectors can support MDL clustering tasks such as estimating the number of clusters and the cluster structure.
Abstract
from arXiv · showhide
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.
1 Introduction
The section frames MDL clustering as selecting models that give the shortest data-and-model description, and identifies efficient NML code-length computation for clustering vectors as the paper’s goal.
- MDL selects a model by trading off goodness-of-fit on observed data against model complexity.
- NML stochastic complexity is the shortest description length for data under a given model class.
- MDL clustering partitions data into non-hierarchical groups while estimating the cluster structure and number of clusters from observed values.
- MDL clustering compares alternative clustering models by encoding the data and cluster structure and choosing the shortest total code length.
- The paper targets a linear-time recursive computation of the clustering vector’s NML code length, replacing a previous polynomial-time method that becomes infeasible for moderate or large data sets.
2 MDL clustering
This section describes MDL clustering as coding both the clustering vector and the data, then selecting the model with the shortest combined description.
- A data set is partitioned into mutually exclusive subsets represented by a clustering vector y_n, with m denoting the number of clusters.
- The MDL code length for data x_n and clustering vector y_n under model M_m has separate terms for encoding the clustering vector and the data.
- The conditional data code length depends on whether the observations are discrete or unquantized.
3 NML model for encoding clustering vector
The paper refines NML encoding for clustering vectors by counting unique cluster structures rather than all label sequences, yielding more efficient coding and better model discrimination.
- The refined NML model counts clustering vectors that represent distinct cluster structures, excluding sequences equivalent up to cluster-label permutations.
- The clustering vector is encoded with a parametric model whose parameters are estimated by maximum likelihood from symbol counts.
- For n = 4 and m = 2, the refined space contains 7 unique clustering vectors instead of all 14 possible vectors.
- The normalizing constant includes m-ary sequences of length n in which every alphabet symbol appears at least once.
- When n = m, the refined code length is L(y_n|M_n) = 0 because knowing the model order suffices to decode the clustering vector.
4 Generating Function
This section uses generating functions to represent the normalizing-constant sequence and derive identities that support the paper’s recursion formula.
- Generating functions are used to establish recurrence formulas, derive asymptotic expansions, and prove combinatorial identities.
- The generating function of a sequence is defined from its coefficients as a formal power series.
- Cayley’s tree function and its derivative generate sequences involving powers and factorial terms used in the normalizing-constant derivation.
- Differentiating the tree-function relation yields T′(z) = e^T(z) + z · e^T(z) · T′(z), an identity used in the derivation.
- The generating function of interest is constructed as (B(z) − 1)^m to represent the sequence associated with C*_n(m).
5 Recursion formula
The paper derives a recursion formula for computing the NML normalizing constant Cn(m) for clustering vectors, enabling linear-time computation across cluster counts. The computation initializes boundary values and recursively obtains the remaining constants.
- Related result: The related normalizing constant C∗n(m) reaches its maximum at ⌊n/4⌋ + 1 for a given n.Figure 1 presents the corresponding computed normalizing constant.
- Computation: Cn(n) and Cn(n −1) provide the starting values for recursively computing Cn(n −2), . . . , Cn(m).Cn(n) is obtained using equation (29), while Cn(n −1) is obtained using equation (30).
- Complexity: The full computation of Cn(m) has linear time complexity, improving on the previous polynomial-time method.The method computes the constants sequentially from the boundary values down to the requested m.
- Illustration: Figure 2 plots Cn(m) for all possible clustering vectors of length n = 100000 with m = 1 . . . n unique clusters.The plotted normalizing constant includes all m-ary sequences in which every alphabet symbol appears at least once.
6 Concluding remarks
The study introduces a linear-time method for computing the NML code length of an encoded vector containing cluster structure. It achieves this through a recursion formula for efficiently computing the NML normalizing constant, replacing the previous polynomial-time approach.
- Conclusion: The new method computes the NML code length of an encoded clustering vector in linear time.The previous method had polynomial time complexity with respect to the vector size and number of clusters.
- Conclusion: The method is based on a recursion formula for efficiently computing the NML normalizing constant for clustering vectors.This targets efficient encoding within the MDL clustering framework.