LITMIR.BIZ

Скачать книгу

href="#fb3_img_img_7014d630-6fbf-5b3b-a443-90f829143c39.png" alt="ModifyingAbove normal x With ampersand c period circ semicolon equals upper R left-parenthesis bold-italic chi right-parenthesis"/>, such that .

      An interesting property of any dimensionality reduction technique is to consider its stability. In this context, a technique is said to be ε‐stable if for any two input data points, x₁ and x₂, the following inequality holds [36]: . Intuitively, this equation implies that Euclidean distances in the original input space are relatively conserved in the output feature space.

      Methods based on statistics and information theory: This family of methods reduces the input data according to some statistical or information theory criterion. Somehow, the methods based on information theory can be seen as a generalization of the ones based on statistics in the sense that they can capture nonlinear relationships between variables, can handle interval and categorical variables at the same time, and many of them are invariant to monotonic transformations of the input variables.

Vector quantization and mixture models: Probably the simplest way of reducing dimensionality is by assigning a class {among a total of K classes) to each one of the observations x_n. This can be seen as an extreme case of dimensionality reduction in which we go from M dimensions to 1 (the discrete class label χ). Each class, χ, has a representative which is the average of all the observations assigned to that class. If a vector x_n has been assigned to the χ_n‐th class, then its approximation after the dimensionality reduction is simply , (see Figure 2.19).

The goal is thus to find the representatives , and class assignment u_χ(x)(u_χ(x) is equal to 1 if the observation x is assigned to the χ‐th class, and is 0 otherwise) such that is minimized. This problem is known as vector quantization or k‐means, already briefly introduced in Section 2.1. The optimization of this goal function is a combinatorial problem, although there are heuristics to cut down its cost [37, 38]. An alternative formulation of the k‐means objective function is subject to U^t U = I and u_ij ∈ {0, 1} {i.e. that each input vector is assigned to one and only one class). In this expression, W is a M × m matrix with all representatives as column vectors, U is an m × N matrix whose ij‐th entry is 1 if the j‐th input vector is assigned to the i‐th class, and denotes the Frobenius norm of a matrix. This intuitive goal function can be put in a probabilistic framework. Let us assume we have a generative model of how the data is produced. Let us assume that the observed data are noisy versions of K vectors x_χ which are equally likely a priori. Let us assume that the observation noise is normally distributed with a spherical covariance matrix = σ² I. The likelihood of observing x_n having produced x_χ is

Figure 2.19 Black circles represent the input data, x_n; gray squares represent class representatives,

      With our previous definition of u_χ(x), we can express it as

      The log likelihood of observing the whole dataset x_n{n = 1, 2, …, N) after removing all constants is We thus see that the goal function of vector quantization J_VQ produces the maximum likelihood estimates of the underlying x_l vectors.

      Under this generative model, the probability density function of the observations is the convolution of a Gaussian function and a set of delta functions located at the x_χ vectors, that is, a set of Gaussians located at the x_χ vectors. The vector quantization then is an attempt to find the centers of the Gaussians forming the probability density function of the input data. This idea has been further pursued by Mixture Models, which are a generalization of vector quantization in which, instead of looking only for the means of the Gaussians associated with each class, we also allow each class to have a different covariance matrix ∑_χ and different a priori probability π_χ. The algorithm looks for estimates of all these parameters by Expectation–Maximization, and at the end produces for each input observation x_n, the label χ of the Gaussian that has the

Скачать книгу