Abstract We address the issue of detecting changes of models that lie behind a data stream. The model refers to an integer-valued structural information such as the number of free parameters in a parametric model. Specifically we are concerned with the problem of how we can detect signs of model changes earlier than they are actualized. To this end, we employ continuous model selection on the basis of the notion of descriptive dimensionality (Ddim). It is a real-valued model dimensionality, which is designed for quantifying the model dimensionality in the model transition period. Continuous model selection is to determine the real-valued model dimensionality in terms of Ddim from a given data. We propose a novel methodology for detecting signs of model changes by tracking the rise-up/descent of Ddim in a data stream. We apply this methodology to detecting signs of changes of the number of clusters in a Gaussian mixture model and those of the order in an auto regression model. With synthetic and real data sets, we empirically demonstrate its effectiveness by showing that it is able to visualize well how rapidly model dimensionality moves in the transition period and to raise early warning signals of model changes earlier than they are detected with existing methods.

This study is concerned with an algorithm to detect structural change with KC in nonparametric distributions. We propose an index of the quantification of structural information for nonparametric distributions with the aim of detecting their changes in time series data. In a parametric model such as a Gaussian mixture model, the number of clusters can represent the structural information. However, the notion of structural information for modeling data nonparametrically does not exist. Herein we introduce the novel notion of kernel complexity (KC) as structural information in a nonparametric setting. The key idea of KC is to combine the information bias by the Gini index with the quantity of information measured by the normalized maximum likelihood (NML) code length. We empirically show the similarities between KC and the number of clusters in a parametric model under certain conditions. Using synthetic and real datasets, we empirically demonstrate that our framework enables us to detect the structural changes underlying the data. We use the synthetic datasets to demonstrate the usefulness of our method with some characteristic data distribution. We then use real datasets to evaluate the validity of the detected results both quantitatively and qualitatively.

Compression techniques for deep neural network models are becoming very important for the efficient execution of high-performance deep learning systems on edge-computing devices. The concept of model compression is also important for analyzing the generalization error of deep learning, known as the compression-based error bound. However, there is still huge gap between a practically effective compression method and its rigorous background of statistical learning theory. To resolve this issue, we develop a new theoretical framework for model compression and propose a new pruning method called {\it spectral pruning} based on this framework. We define the ``degrees of freedom'' to quantify the intrinsic dimensionality of a model by using the eigenvalue distribution of the covariance matrix across the internal nodes and show that the compression ability is essentially controlled by this quantity. Moreover, we present a sharp generalization error bound of the compressed model and characterize the bias--variance tradeoff induced by the compression procedure. We apply our method to several datasets to justify our theoretical analyses and show the superiority of the the proposed method.

This study is concerned with the issue of detecting changes in Gaussian mixture models (GMM) from stream data. A change in a GMM implies a change in the number of clusters as well as a change in the cluster assignments. Unlike all the existing work that addresses this issue, we aim at detecting the early warning signals of changes as well as the changes themselves. To this end, we propose a novel notion of the sequential MDL change statistics (SMCS). SMCS is a real-valued index measuring the degree of change in a GMM from an information-theoretic viewpoint. This index can also be calculated sequentially every time a dataset is generated. Therefore, by tracking the changes of SMCS in real-time, we can possibly detect the early warning signals of changes in a GMM as well as its changes. We derive error probabilities for model change detection with SMCS to show that they converge to zero exponentially as sample size increases, and we derive a suitable parameter using this theorem. Furthermore, we empirically demonstrate cases where early warning signals of the changes can be successfully tracked by SMCS.

This paper corrects errors in the calculation of the normalized maximum likelihood (NML) code length for a Gaussian mixture model (GMM). It shows that the NML code length calculated in “efficient computation of the NML codes for the GMMs with its applications to clustering” is an upper bound on the NML code length strictly calculated for the GMM. In addition, we correct the NML code length for generalized logistic distribution.

This paper proposes a new method for detecting the uncertainty of a latent structure. We consider the case where the latent structure of dataset changes gradually over time, with the goal of selecting the optimal model at any given time. In selecting the optimal model, we use the minimum description length (MDL) principle, specifically the normalized maximum likelihood (NML), which is the optimal code length in the sense of Shtarkov's minimax regret. To detect the uncertainty of a latent structure, the main idea proposed here is that the uncertainty of the model selection will increase at the initial stage when the model change occurs. Here, we propose a new indicator called "structural entropy (SE)", which defines model selection uncertainty based on the MDL principle. We use several models for model selection, including the clustering structures of the Gaussian mixture model and Poisson mixture model, and a time-dependent structure model such as the autoregression model. We show the behavior of the proposed indicator (SE) using an artificial dataset and a real marketing dataset.

This paper addresses the issue of estimating from a given data sequence the number of mixture components for a Gaussian mixture model(GMM). Our approach is to compute the normalized maximum likelihood (NML) code length for the data sequence relative to a GMM, then to find the mixture size that attains the minimum of the NML on the basis of the minimum description length principle. For finite domains, Kontkanen and Myllymäki proposed a method for efficient computation of the NML code length for specific models, however, for general classes over infinite domains, it has remained open how we compute the NML code length efficiently. We first propose a general method for calculating the NML code length for a general exponential family. Then, we apply it to the efficient computation of the NML code length for a GMM. The key idea is to restrict the data domain in combination with the technique of employing a generating function for computing the normalization term for a GMM. We use artificial datasets to empirically demonstrate that our estimate of the mixture size converges to the true one significantly faster than other criteria.

We are concerned with the issue of detecting changes of clustering structures from multivariate time series. From the viewpoint of the minimum description length(MDL) principle, we propose an algorithm that tracks changes of clustering structures so that the sum of the code-length for data and that for clustering changes is minimum. Here we employ a Gaussian mixture model(GMM) as representation of clustering, and compute the code-length for data sequences using the normalized maximum likelihood (NML) coding. The proposed algorithm enables us to deal with clustering dynamics including merging, splitting, emergence, disappearance of clusters from a unifying view of the MDL principle. We empirically demonstrate using artificial data sets that our proposed method is able to detect cluster changes significantly more accurately than an existing statistical-test based method and AIC/BIC-based methods. We further use real customers' transaction data sets to demonstrate the validity of our algorithm in market analysis. We show that it is able to detect changes of customer groups, which correspond to changes of real market environments.

This paper addresses the issue of estimating from a given data sequence the number of mixture components for a Gaussian mixture model. Our approach is to compute the normalized maximum likelihood (NML) code-length for the data sequence relative to a Gaussian mixture model, then to find the mixture size that attains the minimum of the NML. Here the minimization of the NML code-length is known as Rissanen's minimum description length (MDL) principle. For discrete domains, Kontkanen and Myllymäki proposed a method of efficient computation of the NML code-length for specific models, however, for continuous domains it has remained open how we compute the NML code-length efficiently. We propose a method for efficient computation of the NML code-length for Gaussian mixture models. We develop it using an approximation of the NML code-length under the restriction of the domain and using the technique of a generating function. We apply it to the issue of determining the optimal number of clusters in clustering using a Gaussian mixture model, where the mixture size is the number of clusters. We use artificial data sets and benchmark data sets to empirically demonstrate that our estimate of the mixture size converges to the true one significantly faster than AIC and BIC.