A Short Review on Minimum Description Length: An Application to Dimension Reduction in PCA

Abstract

The minimun description length (MDL) is a powerful criterion for model selection that is gaining increasing interest from both theorists and practicioners. It allows for automatic selection of the best model for representing data without having a priori information about them. It simply uses both data and model complexity, selecting the model that provides the least coding length among a predefined set of models. In this paper, we briefly review the basic ideas underlying the MDL criterion and its applications in different fields, with particular reference to the dimension reduction problem. As an example, the role of MDL in the selection of the best principal components in the well known PCA is investigated.

Keywords: classification; dimension reduction; features extraction; minimum description length; principal component analysis.

Figure 1

TEST 1. (Top) Red dotted line: $sc(\mathit{X};k)$ versus the number of components k for $N=5$, $P=25$; the minimum is correctly attained at $k=5$. Blue dashed line: $sc(\mathit{X};k)$ versus the number of components k for $N=10$, $P=20$; the minimum is correctly attained at $k=10$. (Bottom) The same plot where $log\left(sc\right(\mathit{X};k\left)\right)$ has been considered to improve its readability in correspondence to the minimum value.

Figure 2

TEST 2. Plot of $sc(\mathit{X};k)$ and its components versus the number of components k. (Top): non-normalized data. (Bottom): normalized data.

Figure 3

TEST 2. (Top) Plot of $sc(\mathit{X};k)$ and its components versus the number of components k. Signals have been uniformly sampled so that the dimension of $\mathit{X}$ is $n\times m=66\times 90$. (Bottom) Plot of $log\left(sc\right(\mathit{X};k)$).

Figure 4

TEST 3. Plot of $sc(\mathit{X};k)$ and its components versus the number of components k; the minimum is attained at $k=22$.

Figure 5

TEST 3. (Left) Ground-truth Indian Pines image; (Middle) classification image using the best result of PCA-SVM in [78]; (Right) classification image using the PCA-SVM method and the number of components estimated using the stochastic complexity, as in Equation (5).