Stochastic complexity of vectors containing cluster structure

# Stochastic complexity of vectors containing cluster structure
Source: [https://arxiv.org/html/2609.00084](https://arxiv.org/html/2609.00084)
Daniel NicoriciOlli Yli\-HarjaAffiliation:Institute of Signal Processing, Tampere University of TechnologyP\.O\. Box 553, FIN\-33101 Tampere, FinlandE\-mails:Olli\.Yli\-Harja@tut\.fi,Jaakko\.Astola@tut\.fiJaakko AstolaAffiliation:Institute of Signal Processing, Tampere University of TechnologyP\.O\. Box 553, FIN\-33101 Tampere, FinlandE\-mails:Olli\.Yli\-Harja@tut\.fi,Jaakko\.Astola@tut\.fi

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\.

###### 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\.

Keywords:minimum description length, normalized maximum likelihood, stochastic complexity, MDL clustering, estimating number of clusters, finding cluster structure\.

## 1Introduction

The MDL principle for statistical model selection and statistical inference is based on the simple idea that the best way to capture regular features in data is to construct a model in a certain class which permits the shortest description of the data and the model itself\[[1](https://arxiv.org/html/2609.00084#bib.bib1),[2](https://arxiv.org/html/2609.00084#bib.bib2),[3](https://arxiv.org/html/2609.00084#bib.bib3),[4](https://arxiv.org/html/2609.00084#bib.bib4),[5](https://arxiv.org/html/2609.00084#bib.bib5)\]\. This principle chooses a model such that it trades off between goodness\-of\-fit on the observed data with “complexity” of the model\[[6](https://arxiv.org/html/2609.00084#bib.bib6)\]\. Also, the MDL approach fits models to the data and no assumption that the data are a sample from a “true” random variable is needed\[[3](https://arxiv.org/html/2609.00084#bib.bib3),[5](https://arxiv.org/html/2609.00084#bib.bib5)\]\. This eliminates the difficulty in other approaches to modeling that the more complex model is fitted to the data the better estimate of the data one gets\[[3](https://arxiv.org/html/2609.00084#bib.bib3),[4](https://arxiv.org/html/2609.00084#bib.bib4)\]\. The MDL principle\[[1](https://arxiv.org/html/2609.00084#bib.bib1),[3](https://arxiv.org/html/2609.00084#bib.bib3),[5](https://arxiv.org/html/2609.00084#bib.bib5)\]has been widely used in statistical inference in an asymptotically justified form\[[7](https://arxiv.org/html/2609.00084#bib.bib7)\]\.

Recently, a more efficient form of MDL principle based on the normalized maximum likelihood model, which effects a universal sufficient statistics decomposition to separate noise from the learnable information in data has been found\[[7](https://arxiv.org/html/2609.00084#bib.bib7)\]\. The NML model provides a better yardstick for comparison of performance of different model classes than other alternative ways of computing the code length, e\.g\. two\-part codes\[[3](https://arxiv.org/html/2609.00084#bib.bib3),[4](https://arxiv.org/html/2609.00084#bib.bib4),[7](https://arxiv.org/html/2609.00084#bib.bib7)\]\. The stochastic complexity, based on the NML model, is the shortest description length of a given data for a given model class\[[8](https://arxiv.org/html/2609.00084#bib.bib8)\]\.

The scenario we follow is that the encoder and the decoder agree beforehand on the NML model for a specific class of models that is being used to design the codes for encoding the message, e\.g\. the vector containing the cluster structure\. The optimal length of the message is well known in information theory and it can be achieved based on practical coding methods\[[7](https://arxiv.org/html/2609.00084#bib.bib7)\]\. However, our goal is to compute the code length of the encoded message and not to write down the encoded message\. We choose the model which gives the smallest encoded message based on the MDL principle\.

Clustering is one of the central concepts in the field of unsupervised data analysis\. The problem of finding the cluster structure and number of clusters for the given data, based on the MDL principle, when no information other than the observed values is available is known as MDL clustering and its goal is to partition the data into several non\-hierarchical groups of items\[[9](https://arxiv.org/html/2609.00084#bib.bib9)\]\. The approach of the MDL clustering is based on the idea that a good clustering is such that one can encode the cluster structure together with the data based on the NML models so that the resulting total code length is minimized\[[9](https://arxiv.org/html/2609.00084#bib.bib9)\]\. The models, representing the different ways of clustering the data, are compared based on the code lengths\. The problems of finding the number of clusters and the cluster structure are solved simultaneously by choosing the best model, which gives the shortest code length for the data\.

The efficient encoding based on NML model of the vector containing the cluster structure, also called clustering vector throughout this study, is of great importance in the MDL clustering framework\. Our previous study\[[10](https://arxiv.org/html/2609.00084#bib.bib10)\]introduced an efficient NML model for encoding the clustering vector and a polynomial time method to compute its NML code length\. This had been used in our previous work\[[10](https://arxiv.org/html/2609.00084#bib.bib10),[11](https://arxiv.org/html/2609.00084#bib.bib11)\]for finding the number of clusters and the cluster structure in gene expression data from microarray experiments\. The previously introduced polynomial time method, which is similar to Kontkanenet al\.\[[9](https://arxiv.org/html/2609.00084#bib.bib9)\], is infeasible for large of even moderate size data sets\. In this study, our main goal is to derive a linear time recursive method for the computation of the NML code length of the encoded clustering vector, based on properties of generating functions\[[12](https://arxiv.org/html/2609.00084#bib.bib12)\]\. The properties of the generating functions have been previously used for finding asymptotic expansions for sums arising in coding theory\[[13](https://arxiv.org/html/2609.00084#bib.bib13),[14](https://arxiv.org/html/2609.00084#bib.bib14),[12](https://arxiv.org/html/2609.00084#bib.bib12)\]and for computing the stochastic complexity in the case of multinomial data\[[8](https://arxiv.org/html/2609.00084#bib.bib8)\]\.

In section 2 we introduce introduce the notation and review MDL clustering\. The NML model for encoding clustering vector is presented in section 3\. The properties of generating function is presented in section 4 and the new recursion formula for computing the NML code length of the encoded clustering vector is derived using a generating function in section 5\. Finally, section 6 gives the concluding remarks\.

## 2MDL clustering

Here we present the MDL clustering approach of Kontkanenet al\.\[[9](https://arxiv.org/html/2609.00084#bib.bib9)\]for data clustering\. Let us consider a data set𝐱n=\(𝐱1,…,𝐱n\)\\mathbf\{x\}^\{n\}=\(\\mathbf\{x\}\_\{1\},\\ldots,\\mathbf\{x\}\_\{n\}\)consisting ofnncolumn vectors, where𝐱i=\(xi​1,…,xi​q\)T\\mathbf\{x\}\_\{i\}=\(x\_\{i1\},\\ldots,x\_\{iq\}\)^\{T\}andi=1,…,ni=1,\\ldots,n\. Clustering of the data set𝐱n\\mathbf\{x\}^\{n\}is defined as a partitioning of the data into mutually exclusive subsets, the union of which forms the data set\. We denote a clustering by using the clustering vector𝐲n=\(y1,…,yn\)\\mathbf\{y\}^\{n\}=\(y\_\{1\},\\ldots,y\_\{n\}\)whereyi=\{1,…,m\}y\_\{i\}=\\\{1,\\ldots,m\\\}andyi=ky\_\{i\}=kwherek∈\{1,…,m\}k\\in\\\{1,\\ldots,m\\\}if and only if𝐱i\\mathbf\{x\}\_\{i\}belongs to the clusterkk\. The number of clusters is denoted bymm, wherem=1,…,nm=1,\\ldots,n\.

The MDL code length \(two part\-code\)\[[1](https://arxiv.org/html/2609.00084#bib.bib1),[9](https://arxiv.org/html/2609.00084#bib.bib9)\]of the encoded data𝐱n\\mathbf\{x\}^\{n\}together with the clustering vector𝐲n\\mathbf\{y\}^\{n\}considering the modelℳm\\mathcal\{M\}\_\{m\}\[[9](https://arxiv.org/html/2609.00084#bib.bib9)\]is

ℒ⁡\(𝐱n,𝐲n\|ℳm\)=ℒ⁡\(𝐲n\|ℳm\)\+ℒ⁡\(𝐱n\|𝐲n\),\\mathcal\{L\}\(\\mathbf\{x\}^\{n\},\\mathbf\{y\}^\{n\}\|\\mathcal\{M\}\_\{m\}\)=\\mathcal\{L\}\(\\mathbf\{y\}^\{n\}\|\\mathcal\{M\}\_\{m\}\)\+\\mathcal\{L\}\(\\mathbf\{x\}^\{n\}\|\\mathbf\{y\}^\{n\}\),\(1\)where the first term gives the cost of encoding the clustering vector𝐲n\\mathbf\{y\}^\{n\}and the last term gives the cost of encoding𝐱n\\mathbf\{x\}^\{n\}\. In the case that the data𝐱n\\mathbf\{x\}^\{n\}contains discrete values one can compute its code lengthℒ⁡\(𝐱n\|𝐲n\)\\mathcal\{L\}\(\\mathbf\{x\}^\{n\}\|\\mathbf\{y\}^\{n\}\)as in\[[9](https://arxiv.org/html/2609.00084#bib.bib9),[15](https://arxiv.org/html/2609.00084#bib.bib15)\]\. When the data contains no quantized values the approach in\[[11](https://arxiv.org/html/2609.00084#bib.bib11)\]can be used for computingℒ⁡\(𝐱n\|𝐲n\)\\mathcal\{L\}\(\\mathbf\{x\}^\{n\}\|\\mathbf\{y\}^\{n\}\)\.

## 3NML model for encoding clustering vector

In the approach of Kontkanenet al\.\[[9](https://arxiv.org/html/2609.00084#bib.bib9)\]the clustering vector𝐲n\\mathbf\{y\}^\{n\}is encoded considering all possiblemm\-ary sequences of lengthnn\. We introduced a refinement in the NML model for computing code length of the encoded clustering vector𝐲n\\mathbf\{y\}^\{n\}by taking into account more faithfully the number of clustering vectors\. This allows us to encode more efficiently the clustering vector using the NML model and to discriminate better between different models\.

The NML approach is used for encoding the clustering vector𝐲n\\mathbf\{y\}^\{n\}by postulating a simple parametric modelP⁡\(𝐲n,Θ⁡\(𝐲n\)\)P\(\\mathbf\{y\}^\{n\};\\Theta\(\\mathbf\{y\}^\{n\}\)\)\. The clustering vector𝐲n\\mathbf\{y\}^\{n\}contains in generalhih\_\{i\}values ofiiand for𝐲n\\mathbf\{y\}^\{n\}the ML estimate ofΘ=\{θ1,…,θq\}\\Theta=\\\{\\theta\_\{1\},\\ldots,\\theta\_\{q\}\\\}isΘ^​\(𝐲n\)=\{θ^1​\(𝐲n\),…,θ^q​\(𝐲n\)\}\\hat\{\\Theta\}\(\\mathbf\{y\}^\{n\}\)=\\\{\\hat\{\\theta\}\_\{1\}\(\\mathbf\{y\}^\{n\}\),\\ldots,\\hat\{\\theta\}\_\{q\}\(\\mathbf\{y\}^\{n\}\)\\\}, whereθ^i​\(𝐲n\)=hin\\hat\{\\theta\}\_\{i\}\(\\mathbf\{y\}^\{n\}\)=\\frac\{h\_\{i\}\}\{n\}\. The probability of the𝐲n\\mathbf\{y\}^\{n\}becomesP⁡\(𝐲n,Θ^​\(𝐲n\)\)=∏i=1m\(hin\)hiP\(\\mathbf\{y\}^\{n\};\\hat\{\\Theta\}\(\\mathbf\{y\}^\{n\}\)\)=\\prod\_\{i=1\}^\{m\}\{\(\\frac\{h\_\{i\}\}\{n\}\)\}^\{h\_\{i\}\}\. The NML model is known to be a solution of two minmax problems, which gives it strong optimality properties\[[4](https://arxiv.org/html/2609.00084#bib.bib4)\]\. The normalized maximum likelihood is

P^​\(𝐲n,Θ^​\(𝐲n\)\)=∏i=1m\(hin\)hiCn​\(m\),\\hat\{P\}\(\\mathbf\{y\}^\{n\};\\hat\{\\Theta\}\(\\mathbf\{y\}^\{n\}\)\)=\\frac\{\\prod^\{m\}\_\{i=1\}\{\\left\(\\frac\{h\_\{i\}\}\{n\}\\right\)\}^\{h\_\{i\}\}\}\{C\_\{n\}\(m\)\},\(2\)where

Cn​\(m\)=∑𝐭n∈ℱmnP⁡\(𝐭n,Θ^​\(𝐭n\)\),C\_\{n\}\(m\)=\\sum\_\{\\mathbf\{t\}^\{n\}\\in\\mathcal\{F\}^\{n\}\_\{m\}\}P\(\\mathbf\{t\}^\{n\};\\hat\{\\Theta\}\(\\mathbf\{t\}^\{n\}\)\),\(3\)is the normalizing constant for the probabilityP⁡\(𝐲n,Θ^​\(𝐲n\)\)P\(\\mathbf\{y\}^\{n\};\\hat\{\\Theta\}\(\\mathbf\{y\}^\{n\}\)\)andℱmn\\mathcal\{F\}^\{n\}\_\{m\}is chosen to include all the possible sequences representing clustering vectors𝐭n\\mathbf\{t\}^\{n\}containing exactlymmclusters and that are unique among them\. Two clustering vectors are considered not unique when they describe the same cluster structure, i\.e\. RAND index=1=1\. The RAND index\[[16](https://arxiv.org/html/2609.00084#bib.bib16)\]ranges between 0 and 1 and it is a measure of agreement between alternative data partitions \(data clusters\)\.

For instance, one has forn=4n=4andm=2m=2, the following spaceℱ24\\mathcal\{F\}^\{4\}\_\{2\}of77unique clustering vectors

\(1,2,2,2\)\\displaystyle\\left\(1,2,2,2\\right\)\(2,1,2,2\)\\displaystyle\\left\(2,1,2,2\\right\)\(2,2,1,2\)\\displaystyle\\left\(2,2,1,2\\right\)\(2,2,2,1\)\\displaystyle\\left\(2,2,2,1\\right\)\(1,1,2,2\)\\displaystyle\\left\(1,1,2,2\\right\)\(1,2,1,2\)\\displaystyle\\left\(1,2,1,2\\right\)\(1,2,2,1\)\\displaystyle\\left\(1,2,2,1\\right\)instead of all1414possible clustering vectors

\(1,1,1,2\)\\displaystyle\\left\(1,1,1,2\\right\)\(1,1,2,1\)\\displaystyle\\left\(1,1,2,1\\right\)\(1,1,2,2\)\\displaystyle\\left\(1,1,2,2\\right\)\(1,2,1,1\)\\displaystyle\\left\(1,2,1,1\\right\)\(1,2,1,2\)\\displaystyle\\left\(1,2,1,2\\right\)\(1,2,2,1\)\\displaystyle\\left\(1,2,2,1\\right\)\(1,2,2,2\)\\displaystyle\\left\(1,2,2,2\\right\)\(2,1,1,1\)\\displaystyle\\left\(2,1,1,1\\right\)\(2,1,1,2\)\\displaystyle\\left\(2,1,1,2\\right\)\(2,1,2,1\)\\displaystyle\\left\(2,1,2,1\\right\)\(2,1,2,2\)\\displaystyle\\left\(2,1,2,2\\right\)\(2,2,1,1\)\\displaystyle\\left\(2,2,1,1\\right\)\(2,2,1,2\)\\displaystyle\\left\(2,2,1,2\\right\)\(2,2,2,1\)\\displaystyle\\left\(2,2,2,1\\right\)which are not all unique between them, e\.g\. the clustering vectors\(1,1,1,2\)\\left\(1,1,1,2\\right\)and\(2,2,2,1\)\\left\(2,2,2,1\\right\)represent the same way of clustering the data \(the first three samples are clustered together and the fourth sample is clustered separately\), i\.e\. RAND Index=1=1\.

One can notice that the normalization constant in \([3](https://arxiv.org/html/2609.00084#S3.E3)\) for encoding the clustering vector𝐲n\\mathbf\{y\}^\{n\}withmmunique clusters is\[[10](https://arxiv.org/html/2609.00084#bib.bib10)\],

Cn​\(m\)=Cn∗​\(m\)m\!,C\_\{n\}\(m\)=\\frac\{C\_\{n\}^\{\*\}\(m\)\}\{m\!\},\(4\)whereCn∗​\(m\)C\_\{n\}^\{\*\}\(m\)is the normalizing constant for the NML model for encodingmm\-ary sequences of lengthnnsuch that all symbols from themm\-alphabet appear at least once in every sequence;Cn∗​\(m\)C\_\{n\}^\{\*\}\(m\)includes all possible suchmm\-ary sequences\. Thus one has

Cn∗​\(m\)=∑h1\+…\+hm=nh1,…,hm≥1n\!h1\!​…​hm\!​∏i=1m\(hin\)hi\.C\_\{n\}^\{\*\}\(m\)=\\sum\_\{\\begin\{subarray\}\{c\}h\_\{1\}\+\\ldots\+h\_\{m\}=n\\\\ h\_\{1\},\\ldots,h\_\{m\}\\geq 1\\end\{subarray\}\}\\frac\{n\!\}\{h\_\{1\}\!\\ldots h\_\{m\}\!\}\\prod^\{m\}\_\{i=1\}\{\\left\(\\frac\{h\_\{i\}\}\{n\}\\right\)\}^\{h\_\{i\}\}\.\(5\)An efficient way of computing theCn∗​\(m\)C\_\{n\}^\{\*\}\(m\)\[[10](https://arxiv.org/html/2609.00084#bib.bib10),[12](https://arxiv.org/html/2609.00084#bib.bib12),[9](https://arxiv.org/html/2609.00084#bib.bib9)\]is as following

Cn∗​\(m\)=∑i=1n−1n\!i\!​\(n−i\)\!​\(in\)i​\(n−in\)n−i​Ci∗​\(m−1\),C\_\{n\}^\{\*\}\(m\)=\\sum\_\{i=1\}^\{n\-1\}\\frac\{n\!\}\{i\!\(n\-i\)\!\}\{\\left\(\\frac\{i\}\{n\}\\right\)\}^\{i\}\{\\left\(\\frac\{n\-i\}\{n\}\\right\)\}^\{n\-i\}C\_\{i\}^\{\*\}\(m\-1\),\(6\)whereC0∗​\(m\)=1C\_\{0\}^\{\*\}\(m\)=1andCn∗​\(1\)=1C\_\{n\}^\{\*\}\(1\)=1\. The values forCn∗​\(m\)C\_\{n\}^\{\*\}\(m\)andCn∗​\(m\)C\_\{n\}^\{\*\}\(m\)can be pre\-computed and tabulated to speed up the computations\.

The code length, in bits, of the encoded clustering vector𝐲n\\mathbf\{y\}^\{n\}withmmclusters based on the NML model is

ℒ⁡\(𝐲n\|ℳm\)\\displaystyle\\mathcal\{L\}\(\\mathbf\{y\}^\{n\}\|\\mathcal\{M\}\_\{m\}\)=\\displaystyle=−log2⁡P^​\(𝐲n,Θ^​\(𝐲n\)\)\\displaystyle\-\\log\_\{2\}\\hat\{P\}\(\\mathbf\{y\}^\{n\};\\hat\{\\Theta\}\(\\mathbf\{y\}^\{n\}\)\)\(7\)=\\displaystyle=log2⁡Cn​\(m\)−log⁡∏i=1m2⁡\(hin\)hi\.\\displaystyle\\log\_\{2\}C\_\{n\}\(m\)\-\\log\_\{2\}\\prod^\{m\}\_\{i=1\}\\left\(\\frac\{h\_\{i\}\}\{n\}\\right\)^\{h\_\{i\}\}\.For instance, for a clustering vector𝐲n\\mathbf\{y\}^\{n\}withn=mn=mclusters \(each sample is clustered separately\), one has from \([7](https://arxiv.org/html/2609.00084#S3.E7)\) thatℒ⁡\(𝐲n\|ℳn\)=0\\mathcal\{L\}\(\\mathbf\{y\}^\{n\}\|\\mathcal\{M\}\_\{n\}\)=0, which is what one would expect\. In this case no additional information is needed for encoding the clustering vector beside the order of the model\. It is enough for the decoder to know thatn=mn=min order to decode the clustering vector\. When the method from\[[9](https://arxiv.org/html/2609.00084#bib.bib9)\]forn=mn=mis used, one hasℒ⁡\(𝐲n\|ℳn\)\>0\\mathcal\{L\}\(\\mathbf\{y\}^\{n\}\|\\mathcal\{M\}\_\{n\}\)\>0and the code length of the encoded clustering vector is longer and not so efficient as in \([7](https://arxiv.org/html/2609.00084#S3.E7)\)\.

## 4Generating Function

The generating functions are a popular analytic tool in establishing recurrence formulas, finding asymptotic expansions, and proving combinatorial identities\[[12](https://arxiv.org/html/2609.00084#bib.bib12)\]\.

The generating function of a sequence\{an\}=\(a0,a1,…\)\\\{a\_\{n\}\\\}=\(a\_\{0\},a\_\{1\},\\ldots\)is defined\[[12](https://arxiv.org/html/2609.00084#bib.bib12)\]as

A⁡\(z\)=∑n=0∞an​zn\.A\(z\)=\\sum\_\{n=0\}^\{\\infty\}a\_\{n\}z^\{n\}\.\(8\)An useful tree function that generates the sequence\{nn−1n\!\}\\\{\\frac\{n^\{n\-1\}\}\{n\!\}\\\}is Cayley’s tree functionT⁡\(z\)T\(z\)\[[12](https://arxiv.org/html/2609.00084#bib.bib12),[13](https://arxiv.org/html/2609.00084#bib.bib13),[14](https://arxiv.org/html/2609.00084#bib.bib14)\]where

T⁡\(z\)=∑n=1∞nn−1n\!​zn,T\(z\)=\\sum\_\{n=1\}^\{\\infty\}\\frac\{n^\{n\-1\}\}\{n\!\}z^\{n\},\(9\)and one of its basic properties is

T⁡\(z\)=z⋅eT⁡\(z\)\.T\(z\)=z\\cdot e^\{T\(z\)\}\.\(10\)
Differentiating \([9](https://arxiv.org/html/2609.00084#S4.E9)\) and multiplying withzzyields

z⋅T′​\(z\)=∑n=0∞nnn\!​zn−1=B⁡\(z\)−1,z\\cdot T^\{\\prime\}\(z\)=\\sum\_\{n=0\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}z^\{n\}\-1=B\(z\)\-1,\(11\)where

B⁡\(z\)=∑n=0∞nnn\!​zn,B\(z\)=\\sum\_\{n=0\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}z^\{n\},\(12\)generates the sequence\{nnn\!\}\\\{\\frac\{n^\{n\}\}\{n\!\}\\\}\. From \([11](https://arxiv.org/html/2609.00084#S4.E11)\) one has

B⁡\(z\)=z​T′​\(z\)\+1\.B\(z\)=zT^\{\\prime\}\(z\)\+1\.\(13\)
Also, by differentiating \([10](https://arxiv.org/html/2609.00084#S4.E10)\) one has

T′​\(z\)=eT⁡\(z\)\+z⋅eT⁡\(z\)⋅T′​\(z\)\.T^\{\\prime\}\(z\)=e^\{T\(z\)\}\+z\\cdot e^\{T\(z\)\}\\cdot T^\{\\prime\}\(z\)\.\(14\)By plugging \([10](https://arxiv.org/html/2609.00084#S4.E10)\) in \([14](https://arxiv.org/html/2609.00084#S4.E14)\) one has

z⋅T′​\(z\)=T⁡\(z\)1−T⁡\(z\)\.z\\cdot T^\{\\prime\}\(z\)=\\frac\{T\(z\)\}\{1\-T\(z\)\}\.\(15\)Also, by plugging \([15](https://arxiv.org/html/2609.00084#S4.E15)\) in \([11](https://arxiv.org/html/2609.00084#S4.E11)\) one has

B⁡\(z\)=11−T⁡\(z\),B\(z\)=\\frac\{1\}\{1\-T\(z\)\},\(16\)and

B⁡\(z\)−1=T⁡\(z\)1−T⁡\(z\)\.B\(z\)\-1=\\frac\{T\(z\)\}\{1\-T\(z\)\}\.\(17\)
To show the connection betweenB⁡\(z\)B\(z\)andCn∗​\(m\)C\_\{n\}^\{\*\}\(m\)we compute\(B⁡\(z\)−1\)2\(B\(z\)\-1\)^\{2\}, which yields

\(B⁡\(z\)−1\)2=∑h1=1∞h1h1h1\!​zh1​∑h2=1∞h2h2h2\!​zh2\\displaystyle\\left\(B\(z\)\-1\\right\)^\{2\}=\\sum\_\{h\_\{1\}=1\}^\{\\infty\}\\frac\{h\_\{1\}^\{h\_\{1\}\}\}\{h\_\{1\}\!\}z^\{h\_\{1\}\}\\sum\_\{h\_\{2\}=1\}^\{\\infty\}\\frac\{h\_\{2\}^\{h\_\{2\}\}\}\{h\_\{2\}\!\}z^\{h\_\{2\}\}=∑n=2∞\(∑h1\+h2=nh1,h2≥1h1h1h1\!​h2h2h2\!\)​zh1\+h2\\displaystyle=\\sum\_\{n=2\}^\{\\infty\}\\left\(\\sum\_\{\\begin\{subarray\}\{c\}h\_\{1\}\+h\_\{2\}=n\\\\ h\_\{1\},h\_\{2\}\\geq 1\\end\{subarray\}\}\\frac\{h\_\{1\}^\{h\_\{1\}\}\}\{h\_\{1\}\!\}\\frac\{h\_\{2\}^\{h\_\{2\}\}\}\{h\_\{2\}\!\}\\right\)z^\{h\_\{1\}\+h\_\{2\}\}=∑n=2∞nnn\!​\(∑h1\+h2=nh1,h2≥1n\!h1\!​h2\!​\(h1n\)h1​\(h2n\)h2\)​zn\\displaystyle=\\sum\_\{n=2\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}\\left\(\\sum\_\{\\begin\{subarray\}\{c\}h\_\{1\}\+h\_\{2\}=n\\\\ h\_\{1\},h\_\{2\}\\geq 1\\end\{subarray\}\}\\frac\{n\!\}\{h\_\{1\}\!h\_\{2\}\!\}\\left\(\\frac\{h\_\{1\}\}\{n\}\\right\)^\{h\_\{1\}\}\\left\(\\frac\{h\_\{2\}\}\{n\}\\right\)^\{h\_\{2\}\}\\right\)z^\{n\}=∑n=2∞nnn\!​\(∑h1=1n−1\(nh1\)​\(h1n\)h1​\(n−h1n\)n−h1\)​zn\\displaystyle=\\sum\_\{n=2\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}\\left\(\\sum\_\{h\_\{1\}=1\}^\{n\-1\}\\binom\{n\}\{h\_\{1\}\}\\left\(\\frac\{h\_\{1\}\}\{n\}\\right\)^\{h\_\{1\}\}\\left\(\\frac\{n\-h\_\{1\}\}\{n\}\\right\)^\{n\-h\_\{1\}\}\\right\)z^\{n\}=∑n=2∞nnn\!​Cn∗​\(2\)​zn,\\displaystyle=\\sum\_\{n=2\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}C\_\{n\}^\{\*\}\(2\)z^\{n\},\(18\)where the last equality follows from \([6](https://arxiv.org/html/2609.00084#S3.E6)\) form=2m=2\. Therefore it is straightforward to prove this to

\(B⁡\(z\)−1\)m=∑n=2∞nnn\!​Cn∗​\(m\)​zn,\\left\(B\(z\)\-1\\right\)^\{m\}=\\sum\_\{n=2\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}C\_\{n\}^\{\*\}\(m\)z^\{n\},\(19\)which generates the sequence\{nnn\!​Cn∗​\(m\)\}\\\{\\frac\{n^\{n\}\}\{n\!\}C\_\{n\}^\{\*\}\(m\)\\\}\. Thus our generating function of interest is\(B⁡\(z\)−1\)m\(B\(z\)\-1\)^\{m\}\.

Plugging \([17](https://arxiv.org/html/2609.00084#S4.E17)\) in \([19](https://arxiv.org/html/2609.00084#S4.E19)\) yields

\(B⁡\(z\)−1\)m=Tm​\(z\)\(1−T⁡\(z\)\)m=∑n=2∞nnn\!​Cn∗​\(m\)​zn\.\(B\(z\)\-1\)^\{m\}=\\frac\{T^\{m\}\(z\)\}\{\(1\-T\(z\)\)^\{m\}\}=\\sum\_\{n=2\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}C\_\{n\}^\{\*\}\(m\)z^\{n\}\.\(20\)

## 5Recursion formula

Based on \([20](https://arxiv.org/html/2609.00084#S4.E20)\), let define a special tree function

Tm−1​\(z\)\(1−T⁡\(z\)\)m−1=∑n=1∞Cn∗​\(m−1\)​nnn\!​zn\.\\frac\{T^\{m\-1\}\(z\)\}\{\(1\-T\(z\)\)^\{m\-1\}\}=\\sum\_\{n=1\}^\{\\infty\}C^\{\*\}\_\{n\}\(m\-1\)\\frac\{n^\{n\}\}\{n\!\}z^\{n\}\.\(21\)
Differentiating the right\-hand term of \([21](https://arxiv.org/html/2609.00084#S5.E21)\) and multiplying withzz, one has

z⋅dd​z∑n=1∞Cn∗\(m−1\)nnn\!zn=∑n=2∞nCn∗\(m−1\)nnn\!zn\.z\\cdot\\frac\{d\}\{dz\}\\sum\_\{n=1\}^\{\\infty\}C\_\{n\}^\{\*\}\(m\-1\)\\frac\{n^\{n\}\}\{n\!\}z^\{n\}=\\sum\_\{n=2\}^\{\\infty\}nC\_\{n\}^\{\*\}\(m\-1\)\\frac\{n^\{n\}\}\{n\!\}z^\{n\}\.\(22\)
Also, differentiating the left\-hand term of \([21](https://arxiv.org/html/2609.00084#S5.E21)\) and multiplying withzz, one has

z⋅dd​z​Tm−1​\(z\)\(1−T⁡\(z\)\)m−1=Tm​\(z\)\(1−T⁡\(z\)\)m​m−1T2​\(z\)​z​T′​\(z\)\\displaystyle z\\cdot\\frac\{d\}\{dz\}\\frac\{T^\{m\-1\}\(z\)\}\{\(1\-T\(z\)\)^\{m\-1\}\}=\\frac\{T^\{m\}\(z\)\}\{\(1\-T\(z\)\)^\{m\}\}\\frac\{m\-1\}\{T^\{2\}\(z\)\}zT^\{\\prime\}\(z\)=\(m−1\)​Tm​\(z\)\(1−T⁡\(z\)\)m​1\(1−T⁡\(z\)\)​T​\(z\)\\displaystyle=\(m\-1\)\\frac\{T^\{m\}\(z\)\}\{\(1\-T\(z\)\)^\{m\}\}\\frac\{1\}\{\\left\(1\-T\(z\)\\right\)T\(z\)\}=\(m−1\)​Tm\+1​\(z\)\(1−T⁡\(z\)\)m\+1\+2​\(m−1\)​Tm​\(z\)\(1−T⁡\(z\)\)m\\displaystyle=\(m\-1\)\\frac\{T^\{m\+1\}\(z\)\}\{\(1\-T\(z\)\)^\{m\+1\}\}\+2\(m\-1\)\\frac\{T^\{m\}\(z\)\}\{\(1\-T\(z\)\)^\{m\}\}\+\(m−1\)​Tm−1​\(z\)\(1−T⁡\(z\)\)m−1\\displaystyle\+\(m\-1\)\\frac\{T^\{m\-1\}\(z\)\}\{\(1\-T\(z\)\)^\{m\-1\}\}=\(m−1\)​∑n=2∞nnn\!​Cn∗​\(m\+1\)​zn\\displaystyle=\(m\-1\)\\sum\_\{n=2\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}C\_\{n\}^\{\*\}\(m\+1\)z^\{n\}\+2\(m−1\)∑n=2∞nnn\!Cn∗\(m\)zn\\displaystyle\+2\(m\-1\)\\sum\_\{n=2\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}C\_\{n\}^\{\*\}\(m\)z^\{n\}\+\(m−1\)∑n=2∞nnn\!Cn∗\(m−1\)zn\.\\displaystyle\+\(m\-1\)\\sum\_\{n=2\}^\{\\infty\}\\frac\{n^\{n\}\}\{n\!\}C\_\{n\}^\{\*\}\(m\-1\)z^\{n\}\.\(23\)Comparing the coefficients ofznz^\{n\}in \([22](https://arxiv.org/html/2609.00084#S5.E22)\) and \([23](https://arxiv.org/html/2609.00084#S5.Ex27)\), one has

n​Cn∗​\(m−1\)\\displaystyle nC\_\{n\}^\{\*\}\(m\-1\)=\\displaystyle=\(m−1\)​Cn∗​\(m\+1\)\+2​\(m−1\)​Cn∗​\(m\)\\displaystyle\(m\-1\)C\_\{n\}^\{\*\}\(m\+1\)\+2\(m\-1\)C\_\{n\}^\{\*\}\(m\)\(24\)\+\(m−1\)​Cn∗​\(m−1\),\\displaystyle\+\(m\-1\)C\_\{n\}^\{\*\}\(m\-1\),and it yields

Cn∗​\(m\)=mn−m​\(Cn∗​\(m\+2\)\+2​Cn∗​\(m\+1\)\),C\_\{n\}^\{\*\}\(m\)=\\frac\{m\}\{n\-m\}\\left\(C\_\{n\}^\{\*\}\(m\+2\)\+2C\_\{n\}^\{\*\}\(m\+1\)\\right\),\(25\)which holds for1<m<n−11<m<n\-1\. For recursively computing \([25](https://arxiv.org/html/2609.00084#S5.E25)\) one needs to knowCn∗​\(n\)C\_\{n\}^\{\*\}\(n\)andCn∗​\(n−1\)C\_\{n\}^\{\*\}\(n\-1\)which are straightforward to compute using \([5](https://arxiv.org/html/2609.00084#S3.E5)\)\. Therefore one has

Cn∗​\(n\)=n\!nn,C\_\{n\}^\{\*\}\(n\)=\\frac\{n\!\}\{n^\{n\}\},\(26\)and

Cn∗​\(n−1\)=2​\(n−1\)​n\!nn\.C\_\{n\}^\{\*\}\(n\-1\)=2\(n\-1\)\\frac\{n\!\}\{n^\{n\}\}\.\(27\)The computation ofCn∗​\(m\)C\_\{n\}^\{\*\}\(m\)starts withCn∗​\(n\)C\_\{n\}^\{\*\}\(n\)andCn∗​\(n−1\)C\_\{n\}^\{\*\}\(n\-1\)and thenCn∗​\(n−2\)C\_\{n\}^\{\*\}\(n\-2\),…,Cn∗​\(m\)C\_\{n\}^\{\*\}\(m\)are computed using the recursion formula \([25](https://arxiv.org/html/2609.00084#S5.E25)\)\. The plot of the normalizing constantCn∗​\(m\)C\_\{n\}^\{\*\}\(m\)computed using the recursion formula \([25](https://arxiv.org/html/2609.00084#S5.E25)\) is represented in Figure[1](https://arxiv.org/html/2609.00084#S5.F1)\. It can be seen that the maximum ofCn∗​\(m\)C\_\{n\}^\{\*\}\(m\)is achieved for⌊n4⌋\+1\\lfloor\\frac\{n\}\{4\}\\rfloor\+1for a givennn\.

Figure 1:The NML normalizing constantCn∗​\(m\)C\_\{n\}^\{\*\}\(m\)that includes all possiblemm\-ary sequences of lengthnnand all symbols from themm\-alphabet appear at least once in every sequence, wheren=100000n=100000andm=1​…​nm=1\\ldots n\.From \([4](https://arxiv.org/html/2609.00084#S3.E4)\), \([26](https://arxiv.org/html/2609.00084#S5.E26)\), \([27](https://arxiv.org/html/2609.00084#S5.E27)\), and \([25](https://arxiv.org/html/2609.00084#S5.E25)\) one has the recursion formula for normalizing constantCn​\(m\)C\_\{n\}\(m\)as follows,

Cn​\(m\)=m⁡\(m\+1\)n−m​\(\(m\+2\)​Cn​\(m\+2\)\+2​Cn​\(m\+1\)\),C\_\{n\}\(m\)=\\frac\{m\(m\+1\)\}\{n\-m\}\\left\(\(m\+2\)C\_\{n\}\(m\+2\)\+2C\_\{n\}\(m\+1\)\\right\),\(28\)which holds for1<m<n−11<m<n\-1, where

Cn​\(n\)=1nn,C\_\{n\}\(n\)=\\frac\{1\}\{n^\{n\}\},\(29\)and

Cn​\(n−1\)=2​n​\(n−1\)nn\.C\_\{n\}\(n\-1\)=\\frac\{2n\(n\-1\)\}\{n^\{n\}\}\.\(30\)
Figure 2:The NML normalizing constantCn​\(m\)C\_\{n\}\(m\)that includes all possible clustering vectors of lengthnnwithmmunique clusters, wheren=100000n=100000andm=1​…​nm=1\\ldots n\.The computation ofCn​\(m\)C\_\{n\}\(m\)starts withCn​\(n\)C\_\{n\}\(n\)andCn​\(n−1\)C\_\{n\}\(n\-1\)using \([29](https://arxiv.org/html/2609.00084#S5.E29)\) and \([30](https://arxiv.org/html/2609.00084#S5.E30)\), and thenCn​\(n−2\)C\_\{n\}\(n\-2\),…,Cn​\(m\)C\_\{n\}\(m\)are computed using the recursion formula \([28](https://arxiv.org/html/2609.00084#S5.E28)\)\. The plot of the normalizing constantCn​\(m\)C\_\{n\}\(m\)computed using the recursion formula \([28](https://arxiv.org/html/2609.00084#S5.E28)\) is represented in Figure[2](https://arxiv.org/html/2609.00084#S5.F2)\. The whole computation has a linear time complexity which is a major improvement compared to the previous method\[[10](https://arxiv.org/html/2609.00084#bib.bib10)\]\.

## 6Concluding remarks

The efficient encoding based on NML model of the encoded vector containing the cluster structure and efficient computation of its NML code length are of great importance in the MDL clustering framework\. In this study we introduced a linear time complexity method for fast computation of the NML code length of the encoded vector containing cluster structure\. The previous method has a polynomial time complexity with respect of the size and numbers of clusters in the vector\. The newly introduced method is based on a recursion formula for efficient computation of normalizing constant from the NML model for clustering vectors\.

## References

- \[1\]J\. Rissanen,“Modelling by the shortest data description,”Automatica, vol\. 14, pp\. 465–471, 1978\.
- \[2\]J\. Rissanen,“A universal prior for integers and estimation by minimum description length,”Annals of Statistics, vol\. 11, no\. 2, pp\. 416–431, 1983\.
- \[3\]J\. Rissanen,“MDL denoising,”IEEE Transactions on Information Theory, vol\. 46, no\. 7, pp\. 2537–2543, 2000\.
- \[4\]J\. Rissanen,“Strong optimality of the normalized ML models as universal codes and information in data,”IEEE Transactions on Information Theory, vol\. 47, no\. 5, pp\. 1712–1717, 2001\.
- \[5\]J\. Rissanen,“Complexity and information in modeling,”inComputability, Complexity and Constructivity in Economic Analysis, V\. Velupillai, Ed\. Blackwell Publishings, Oxford, 2005\.
- \[6\]P\. Grünwald,“Minimum description length principle tutorial,”inAdvances in Minimum Description Length: Theory and Applications, P\. Grünwald, I\.J\. Myung, and M\. Pitt, Eds\., pp\. 22–79\. MIT Press, Cambridge, 2005\.
- \[7\]I\. Tăbuş, J\. Rissanen, and J\. Astola,“Classification and feature gene selection using the normalized maximum likelihood model for discrete regression,”Signal Processing, Special Issue on Genomic Signal Processing, vol\. 83, no\. 4, pp\. 713–727, 2003\.
- \[8\]P\. Kontkanen and P\. Myllymäki,“Analyzing the stochastic complexity via tree polynomials,”inTechnical Report HIIT\-2005\-4, Helsinki, Finland, 2005, The Helsinki Institute for Information Technology\.
- \[9\]P\. Kontkanen, P\. Myllymäki, W\. Buntine, J\. Rissanen, and H\. Tirri,“An MDL framework for data clustering,”inAdvances in Minimum Description Length: Theory and Applications, P\. Grünwald, I\.J\. Myung, and M\. Pitt, Eds\., pp\. 323–353\. MIT Press, Cambridge, 2005\.
- \[10\]D\. Nicorici, J\. Astola, and O\. Yli\-Harja,“Estimating the number of clusters in microarray data sets based on an information theoretic criterion,”inIEEE Workshop on Statistical Signal Processing \(SSP’05\), Bordeaux, France, July 17–20, 2005\.
- \[11\]D\. Nicorici, O\. Yli\-Harja, and J\. Astola,“Cluster structure inference for microarray data based on an information theoretic criterion,”inIEEE International Workshop on Genomic Signal Processing and Statistics \(GENSIPS’06\), College Station, Texas, USA, May 28–30, 2006\.
- \[12\]W\. Szpankowski,Average Case Analysis of Algorithms on Sequences,John Wiley & Sons, New York, USA, 2001\.
- \[13\]W\. Szpankowski,“On asymptotics of certain sums arising in coding theory,”IEEE Transactions on Information Theory, vol\. 41, no\. 6, pp\. 2087–2090, February 1995\.
- \[14\]W\. Szpankowski,“On asymptotics of certain recurrences arising in universal coding,”Problems of Information Transmission, vol\. 34, no\. 2, pp\. 55–61, February 1998\.
- \[15\]D\. Nicorici, O\. Yli\-Harja, and J\. Astola,“Cluster\-structure inference for microarray data via MDL principle,”inIEEE International Workshop on Genomic Signal Processing and Statistics \(GENSIPS’05\), Newport, Rhode Island, USA, May 22–24 2005\.
- \[16\]L\. Hubert and P\. Arabie,“Comparing partitions,”Journal of Classification, vol\. 2, pp\. 193–218, 1985\.