Kernel Complexity for Nonparametric Distributions and Detection of Its Changes

This paper addresses the issues of how we can quantify structural information for nonparametric distributions and how we can detect its changes. Structural information refers to an index for a global understanding of a data distribution. When we consider the problem of clustering using a parametric model such as a Gaussian mixture model, the number of mixture components (clusters) can be thought of as structural information in the model. However, there does not exist any notion of structural information for nonparametric modeling of data. In this paper we introduce a novel notion of {\em kernel complexity} (KC) as structural information in the nonparametric setting. The key idea of KC is to combine the information bias inspired by the Gini index with the information quantity measured in terms of the normalized maximum likelihood (NML) code length. We empirically show that KC has a property similar to the number of clusters in a parametric model. We further propose a framework for structural change detection with KC in nonparametric distributions. With synthetic and real data sets we empirically demonstrate that our framework enables us to detect structural changes underlying the data and their early warning signals.