Metric Properties of Structured Data Visualizations through Generative Probabilistic Modeling

1 Introduction

Topographic visualisation techniques have been an important tool in multi-variate data analysis and data mining. Generative probabilistic approaches [Bishop et al., 1998b; 1998a; Kab´an and Girolami, 2001; Nabney et al., 2005] demonstrated advantages over non-probabilistic alternatives in terms of a flexible and technically sound framework that makes various extensions possible in a principled manner.Recently, Tino et al.[2004] introduced a general framework for visualizing sets of sequential data. Loosely speaking, a smooth twodimensional manifold in the space of appropriate noise models (e.g. Hidden Markov models (HMM) of a given topology) is constructed so that HMMs constrained on the manifold explain the observed sequences well. Each sequence (data item) is then projected on the manifold by visualizing the relevant HMMs likely to be responsible for generating that sequence.

It is possible in non-linear projections that visualizations of two data items get close in the visualization space, even though they may be separated by a large distance in the data space (and vice-versa). Therefore, to be of practical use, nonlinear projection methods must be equipped with representations in the visualization space of metric relationships among data items in the original data space. Otherwise, one would not be able to detect and understand the underlying cluster structure of data items. To that end, in the case of static vectorial data of fixed-dimensionality, Bishop et al. [1997] calculated magnification factors of the Generative Topographic Mapping (GTM) [Bishop et al., 1998b] using tools of differential geometry.

However, in the case of structured data types (such as sequences or trees) one has to be careful when dealing with the notion of a metric in the data space. The generative probabilistic visualization models studied in this paper naturally induce a metric in the structured data space. Loosely speaking, two data items (sequences) are considered to be close (or similar) if both of them are well-explained by the same underlying noise model (e.g. HMM) from the two-dimensional manifold of noise models. Due to non-linear parametrization of the manifold, projections of two quite different data items may end up being mapped close to each other. We emphasise, that in this framework, the distance between structured data items is implicitly defined by the local noise models that drive topographic map formation. If the noise model changes, the perception of what kind of data items are considered similar changes as well. For example, if the noise models were 1storder Markov chains, sequences would be naturally grouped with respect to their short-range subsequence structure. If, on the other hand, the noise models were stochastic machines specializing at latching special events occurring within the data sequences, the sequences would naturally group with respect to the number of times the special event occurred, irrespective of the length of temporal separation between the events.

In this paper, we quantify the extend to which small positional changes on manifold of local noise models explaining structured data (for visualization purposes the manifold is identified with visualization space) lead to changes in the distributions defined by the noise models. It is important to quantify the changes in a parametrization-free manner - we use approximations of Kullback-Leibler divergence. We present two techniques for estimating local metric induced on the structured data space by the model formulation. We first verify our approach in two controlled experiments involving artificially generated sequences. We then illustrate our methodology on sequences representing chorals by J.S. Bach.

2 A latent trait model for sequential data

Consider a set of sequences over the alphabet S of S symbols, S = {1, 2, ..., S}. The n-th sequence is denoted by s(n) = (s(n) t )t=1:Tn , where n = 1 : N and Tn denotes its length. The aim is to represent each sequence using a two-dimensional latent (visualization) space V = [-1, 1]2. In order to exploit the visualization space fully, a maximum entropy (uniform) prior distribution is imposed over the latent space. With each latent point x, we associate a generative distribution over sequences p(s|x). One possibility (considered in this paper) is to use HMM with K hidden states [Rabiner and Juang, 1986]:

where h is the set of all Tn-tuples over the K hidden states.

For tractability reasons, we discretize the latent space into a regular grid of C points 1 x1, ..., xC. In order to have the HMMs topologically organized, we (in the spirit of [Bishop et al., 1998b; Kab´an and Girolami, 2001]) constrain the flat mixture of HMMs,

by requiring that the HMM parameters be generated through a parameterised smooth nonlinear mapping from the latent space V into the HMM parameter space:

where indexes k, l run from 1 to K; index s ranges from 1 to S, and

• the function g(.) is the softmax function 2 and gk(.) denotes the k-th component returned by the softmax, i.e.

• φ(.) = (φ1(.), ..., φM(.))T , φm(.) : R2 → R is an ordered set of M non-parametric nonlinear smooth basis functions (typically RBFs),
• the matrices A(π) ∈ RK×M , A(T l) ∈ RK×M and A(Bk) ∈ RS×M are free parameters of the model.

Assuming the sequences s(n) , n = 1 : N, were independently generated, the model likelihood reads

1 these sample (grid) points are analogous to the nodes of a Self Organising Map

2 which is the canonical inverse link function of multinomial distributions

Maximum likelihood estimates of the free parameters can be obtained via Expectation-Maximization (EM) algorithm [Tino et al., 2004].

Given a sequence s, some regions of the latent visualization space are better at explaining it than the others. A natural representation (visualization) of s is the mean of the posterior distribution over the latent space, given that sequence:

3 Quantifying metric properties of the visualization space

In this section, we present two approaches to quantifying metric properties of the visualization space V as sensitivities (measured by Kullback-Leibler divergence) of local noise models (HMM) addressed by the points in V to small perturbations in V.

3.1 Approximating Kullback-Leibler divergence through observed Fisher information matrix

Consider the visualization (latent) space V = [-1,+1]2 and the two-dimensional manifold M of local noise models p(·|x) (e.g. HMM with 3 states, emissions over 7 symbols) parametrized by the latent space through (1) and (2-4). The manifold is embedded in manifold H of all noise models of the same form (e.g. all HMMs with 3 states and emissions over 7 symbols). Consider a latent point x ∈ V. If we displace x by an infinitesimally small perturbation dx, the Kullback-Leibler divergence DKL(p(·|x)‖(p(·|x + dx)) between the corresponding noise models p(·|x), (p(·|x+dx) ∈ M can be determined via Fisher information matrix

that acts like a metric tensor on the Riemannian manifoldM [Kullback, 1959]:

The situation is illustrated in figure 1.

Local noise models used in this paper (HMMs) are latent variable models and there is no closed-form formula for calculating the Fisher information matrix. However, Lystig and Hughes[2002] presented a framework for efficient calculation of the observed Fisher information matrix of HMMs based on forward calculations related to those used in maximum likelihood parameter estimation via EM algorithm. We adapt the framework to a special kind of parametrization of HMM used in the latent trait model of section 2. Each HMM has two parameters - latent space coordinates x = (x1, x2) (these can be thought of as coordinates on the visualization screen).

Consider a set S(x) of N sequences independently generated by HMM p(·|x). All sequences have equal length T . Given the n-th sequence, we start recursion from the beginning of the sequence:

Recursive step:

where Λ(n) t = ∑Kj=1 λt(j)(n) .

Starting again at the beginning of the sequence, we recursively evaluate 1st-order derivatives with respect to latent coordinates x1, x2. Letting q ∈ {1, 2}, we have:

The calculations recursively employ ψ(n) t-1 , λ(n) t-1 and Λ(n) t-1 . We also need 1st-order derivatives of initial state, state transition and state-conditional emission probabilities with respect to latent coordinates. We present only the equation for state transitions, other formulas can be obtained in the same manner:

where A(.) i denotes the i-th row of the parameter matrixA(.) . 2nd-order derivatives are obtained in a recursive manner as well:

and Ω(n) t (xq, xr) = ∑Kj=1 ω(n) t (j; xq, xr). The calculations recursively employ ψ(n) t-1 , ω(n) t-1, λ(n) t-1 and Λ(n)

t-1 . We also need both 1st- and 2nd-order derivatives of initial state, state transition and state-conditional emission probabilities with respect to latent coordinates. Again, we present only the equation for state transitions:

Denoting

we calculate elements of the observed Fisher information matrix ˆ F(x), given the set of sequences S(x), as

To illustrate metric properties of the visualization space, we calculate the observed Fisher information matrices ˆ F (xc) in all latent centers xc, c = 1, 2, ...,C, and detect through eigen-analysis of ˆ F(xc) directions of dominant local change in Kullback-Leibler divergence between the HMM parametrized by xc and its perturbed version parametrized by xc + dx. In the visualization space, we signify magnitude of the dominant change (dominant eigenvalue of ˆ F(xc)) by local brightness of the background as well as mark the direction of the dominant change by a piece of line.

3.2 Direct recursive approximation of Kullback-Leibler divergence

Another alternative approach to probe metric properties of the visualization space is the estimate DKL(p(·|x)‖(p(·|x + Δx)) directly. Do [2003] presented an efficient algorithm for approximating Kullback-Leibler (K-L) divergence between two HMM of the same topology. The approximation is based on backward calculations related to those used in maximum likelihood parameter estimation via EM algorithm.

With each hidden state k ∈ {1, 2, ...,K} we associate an auxiliary process βk(t). Given a sequence s = (st)t=1:T , the likelihood p(s|x) can be efficiently calculated by

• starting at the end of the sequence:

• Recursive step:

• Final step:

For u, v ∈ (0, 1], define

The Kullback-Leibler (K-L) divergence between two HMMs p(·|x) and p(·|x′ ), can be approximated as follows:

• Recursion is initiated at end of the sequence:

• Recursive step:

• Final step: the empirical K-L divergence, given the sequence s, is bounded by

Given the set of N sequences, S(x), generated independently by the HMM addressed by x, an estimate of DKL(p(·|x)‖(p(·|x+Δx)) is calculated as

Again, to illustrate metric properties of the visualization space, we perturb latent centers xc in regular intervals around small circle centered at xc and for each perturbation Δx calculate ˆDKL(p(·|x)‖(p(·|x+Δx)). As before, in the visualization space, we signify magnitude of the dominant change by local brightness of the background as well as mark the direction of the dominant change by a piece of line.

4 Experiments

In this section we demonstrate techniques introduced in sections 3.1 and 3.2 to provide additional metric information when visualizing sequential data.

In all experiments the latent space centres xc were positioned on a regular 10 × 10 square grid (C = 100) and there were M = 16 basis functions φi. The basis functions were spherical Gaussian functions of the same width σ = 1.0. The basis functions were centred on a regular 4×4 square grid, reflecting uniform distribution of the latent classes. We account for a bias term by using an additional constant basis function φ17(x) = 1.

Free parameters of the model were randomly initialized in the interval [-1, 1]. Training consisted of repeating EM iterations [Tino et al., 2004]. Typically, the likelihood levelled up after 30-50 EM cycles.

When calculating metric properties of the visualization space, each set S(xc) consisted of 100 generated sequences of length 40.

4.1 Toy data

We first generated a toy data set of 400 binary sequences of length 40 from four HMMs (K = 2 hidden states) with identical emission structure, i.e. the HMMs differed only in transition probabilities. Each of the four HMMs generated 100 sequences. Local noise models p(·|x) were imposed as HMMs with 2 hidden states. Visualization of the sequences is presented in figure 2(a). Sequences are marked with four different markers, corresponding to the four different HMMs used to generate the data set. We stress that the model was trained in a completely unsupervised way. The markers are used for illustrative purposes only. Representations of induced metric in the local noise model space based on Fisher Information matrix (section 3.1) and direct K-L divergence estimations (section 3.2) can be seen in figures 2(b) and 2(c), respectively. Dark areas signify homogeneous regions of local noise models and correspond to possible clusters in the data space. Light areas signify abrupt changes in local noise model distributions (as measured by K-L divergence) and correspond to boundaries between data clusters. The visualization plot reveals that the latent trait model essentially discovered the organization of the data set and the user would be able to detect the four clusters, even without help of the marking scheme in figure 2(a). Of course, the latent trait model benefited from the fact that the distributions used to generate data were from the same model class as the local noise models. There were few atypical sequences generated by the HMM marked with '+', and this is clearly reflected by their projections in the lower left corner.

4.2 Melodic lines of chorals by J.S. Bach

Next we subjected the latent trait model to a set of 100 chorales by J.S. Bach from UCI repository of Machine Learning Databases. We extracted the melodic lines - pitches are represented in the space of one octave, i.e. the observation symbol space consists of 12 different pitch values. Local noise models had K = 3 hidden states. Figure 3 shows choral visualizations, while representations of induced metric in the local noise model space based on Fisher Information matrix and direct K-L divergence estimations can be seen in figures 4(a) and 4(b), respectively. The method discovered natural topography of the key signatures, corroborated with similarities of melodic motives. The melodies can contain sharps and flats other than those included in their key signature due to both modulation and ornaments. The upper region contains melodic lines that utilise keys with flats. Central part of the visualisation space is taken by sharps (left) and almost no sharps/flats (center). The lower region of the plot contains chorals with tense patterns (e.g containing tritons) and is quite clearly strongly separated from other chorals. Again, the overall clustering of chorals is well-matched by the metric representations of figures 4(a) and 4(b). Flats, sharps and tense patterns are clearly separated, as are sharps and infrequent sharps/flats. There are more interesting features to this visualization (e.g. enharmony patterns) that cannot be addressed due to space limitations.

5 Discussion and conclusion

When faced with the problem of non-linear topographic data visualization, one needs additional information putting relative distances of data projections in proportion to local stretchings/contractions of the visualization manifold in the data space. It is important to base representations of manifold stitchings/contractions on the particular notion of distance or similarity between data items that drives formation of the topographic mapping. If one visualizes structured data, such as sequences, this can be a highly non-trivial task, especially for the family of neural-based topographic mappings of sequences [Koskela et al., 1998; Horio and Yamakawa, 2001; Voegtlin, 2002; Strickert and Hammer, 2003]. However, when the visualization model is formulated as a latent trait model, such calculations follow naturally from the model formulation. Two sequences are considered to be similar if both of them are well-explained by the same underlying noise model (in our particular case - HMM). Noise models are organized on a smooth two-dimensional manifold and we can study changes of the local metric (based on Kullback-Leibler divergence) due to non-linear parametrization. We have presented two approaches to metric analysis of the visualization space and experimentally verified that additional information provided by metric representations in the visualization space can be useful for understanding of the overall organization of data. We stress. that the data organization revealed is always with respect to the notion of similarity between data items imposed in the model construction.

The results can be easily generalized e.g. to treestructured data using, for example, Hidden Markov Tree models (HMTM) [Durand et al., 2004]). We stress that the presented framework is general and can be applied to visualizations through latent trait models of a wide variety of structured data, provided a suitable noise model is used. For example, we are currently working on topographic organizations (and metric properties of such) of fluxes form binary star complexes, where the noise models are based on real physical models of binary stars.