Reconstruction of Sequential Data with Probabilistic Models and Continuity Constraints
Authors: Miguel Á. Carreira-Perpiñán
Published in: Advances in Neural Information Processing Systems 12  (NIPS 1999) (Main Conference Track), 1999

Abstract: We consider the problem of reconstructing a temporal discrete sequence  of multidimensional real vectors when part of the data is  missing, under  the  assumption  that  the  sequence  was  generated  by  a  continuous  pro(cid:173) cess.  A particular case of this problem is  multivariate regression, which  is  very difficult when  the  underlying mapping is one-to-many.  We  pro(cid:173) pose  an  algorithm  based  on  a joint probability  model  of the  variables  of interest,  implemented using a  nonlinear latent  variable  model.  Each  point  in  the  sequence  is  potentially reconstructed  as  any  of the  modes  of the conditional distribution of the missing  variables given the present  variables (computed using an exhaustive mode search in a Gaussian mix(cid:173) ture).  Mode selection is determined by  a dynamic programming search  that  minimises a geometric measure of the reconstructed sequence,  de(cid:173) rived from continuity constraints.  We illustrate the algorithm with a toy  example  and  apply  it  to  a real-world  inverse problem,  the  acoustic-to(cid:173) articulatory mapping.  The results  show  that the  algorithm outperforms  conditional mean imputation and multilayer perceptrons. 
1  Definition of the problem 
Consider  a  mobile  point  following  a  continuous trajectory  in  a  subset  of ]RD.  Imagine  that  it  is  possible to  obtain  a finite  number of measurements of the position of the point.  Suppose that these measurements are corrupted by noise and that sometimes part of, or all,  the variables are missing.  The problem considered here is to reconstruct the sequence from  the part of it which is observed.  In the particular case where the present variables and the  missing ones  are the  same for every  point,  the  problem is  one of multivariate regression.  If the  pattern  of missing  variables  is  more  general,  the  problem  is  one  of missing  data  reconstruction. 
Consider the problem of regression.  If the present variables uniquely identify the missing  ones  at every  point of the data set,  the problem can  be  adequately  solved  by  a  universal  function approximator, such as  a multilayer perceptron.  In  a probabilistic framework,  the  conditional mean of the missing variables given the present ones will minimise the average  squared reconstruction error [3].  However, if the underlying mapping is one-to-many, there  will  be  regions  in  the  space for  which  the  present variables do  not identify  uniquely  the  missing  ones.  In  this  case,  the  conditional  mean  mapping  will  fail,  since  it  will  give  a  compromise  value-an average of the correct ones.  Inverse  problems,  where the  inverse 
Probabilistic Sequential Data Reconstruction 
415 
of a  mapping is  one-to-many,  are  of this  type.  They  include the  acoustic-to-articulatory  mapping in speech [15], where different vocal tract shapes may produce the same acoustic  signal, or the robot arm problem [2], where different configurations of the joint angles may  place the hand in the same position. 
In some situations, data reconstruction is a means to some other objective, such as classifi(cid:173) cation or inference. Here, we deal solely with data reconstruction of temporally continuous  sequences according to  the squared error.  Our algorithm does  not apply for data sets that  either lack continuity (e.g. discrete variables) or have lost it (e.g.  due to undersampling or  shuffling). 
We follow a statistical learning approach:  we attempt to reconstruct the sequence by learn(cid:173) ing  the  mapping  from  a  training  set  drawn from  the  probability  distribution  of the  data,  rather than  by  solving  a  physical  model  of the  system.  Our  algorithm can  be  described  briefly as follows.  First, a joint density model of the data is learned in an unsupervised way  from  a sample of the datal .  Then, pointwise reconstruction is  achieved by  computing all  the  modes of the conditional distribution  of the  missing  variables given  the present ones  at the current point.  In principle, any of these modes is potentially a plausible reconstruc(cid:173) tion.  When  reconstructing a sequence,  we  repeat this  mode search  for  every point in  the  sequence,  and then  find  the  combination of modes that  minimises a geometric sequence  measure, using dynamic programming. The sequence measure is derived from local conti(cid:173) nuity constraints, e.g. the curve length. 
The algorithm is detailed in §2 to §4.  We illustrate it with a 2D toy problem in §5 and apply  it to  an  acoustic-to-articulatory-like problem in §6.  §7 discusses the results and compares  the approach with previous work.  Our  notation  is  as  follows.  We  represent the  observed  variables  in  vector form  as  t  =  (tl' ... , t D)  E  ~D. A data set (possibly a temporal sequence) is represented as  {t n } ~=l .  Groups of variables are represented by  sets of indices I, J  E  {I, ... , D}, so  that if I  =  {I, 7, 3}, then tI = (tlt7t3). 
2  Joint generative modelling using latent variables 
Our starting point is a joint probability model of the observed variables p( t).  From it,  we  can compute conditional distributions of the form p( t..71 tI) and, by picking representative  points,  derive a  (multivalued) mapping  tI  ~ t..7.  Thus,  contrarily  to  other approaches,  e.g.  [6],  we  adopt multiple pointwise  imputation.  In  §4  we  show how  to  obtain a single  reconstructed sequence of points. 
Although density estimation requires more parameters than mapping approximation, it has  a fundamental advantage [6]:  the density  model represents the relation  between any  vari(cid:173) ables,  which allows to  choose any  missing/present variable combination.  A mapping ap(cid:173) proximator treats asymmetrically some variables as inputs (present) and the rest as outputs  (missing) and can't easily deal with other relations. 
The existence of functional  relationships (even one-to-many) between the  observed  vari(cid:173) ables indicates that the data must span a low-dimensional manifold in the data space.  This  suggests the  use of latent variable  models for  modelling the joint density.  However,  it  is  possible to use other kinds of density models. 
In  latent variable  modelling the  assumption is  that the observed high-dimensional data t  is  generated from  an  underlying  low-dimensional process  defined  by  a  small  number L  of latent  variables  x  =  (Xl, ... , xL)  [1] .  The  latent  variables  are  mapped  by  a  fixed 
I In our examples we only use complete training data (i.e., with no missing data), but it is perfectly  possible to estimate a probability model with incomplete training data by using an EM algorithm [6]. 
416 
M  A.  Carreira-Perpiful.n 
transformation  into  a  D-dimensional  data  space  and  noise  is  added  there.  A  particular  model is specified by three parametric elements:  a prior distribution in latent space p(x), a  smooth mapping f  from  latent space to data space and a noise model in data space p(tlx).  Marginalising the joint probability density function p(t, x)  over the latent space gives the  distribution  in  data space, p(t).  Given  an  observed sample in  data space  {t n };;=l'  a pa(cid:173) rameter estimate can  be  found  by  maximising  the  log-likelihood,  typically  using  an  EM  algorithm.  We  consider the  following  latent  variable  models,  both of which  allow  easy  computation of conditional distributions of the form p( tJ It I  ): 
Factor analysis  [1], in which the mapping is linear, the prior in latent space is  unit Gaus(cid:173) sian and the noise model  is  diagonal Gaussian.  The density  in data space is  then  Gaussian with a constrained covariance matrix.  We  use  it as  a baseline for com(cid:173) parison with more sophisticated models. 
The generative topographic mapping (GTM)  [4]  is  a  nonlinear  latent  variable  model, 
where the mapping is  a generalised linear model, the prior in  latent space is  dis(cid:173) crete uniform and the noise model is isotropic Gaussian.  The density in data space  is then a constrained mixture of isotropic Gaussians. 
In  latent  variable  models  that  sample  the  latent space prior distribution  (like  GTM),  the  mixture centroids  in  data space  (associated to  the  latent space samples)  are  not trainable  parameters. We can then improve the density model at a higher computational cost with no  generalisation loss by increasing the number of mixture components. Note that the number  of components required  will  depend exponentially  on  the  intrinsic  dimensionality  of the  data (ideally coincident with that of the latent space, L) and not on the observed one, D. 
3  Exhaustive mode finding 
Given a conditional distribution p(tJltI), we  consider all  its  modes as  plausible predic(cid:173) tions for tJ.  This requires an  exhaustive mode search in  the space of t J .  For Gaussian  mixtures, we do this by  using a maximisation algorithm starting from each centroid2 ,  such  as a fixed-point iteration or gradient ascent combined with quadratic optimisation  [5].  In  the particular case where all  variables are missing, rather than performing a mode search,  we  return  as  predictions all  the  component centroids.  It  is  also  possible  to  obtain  error  bars at each mode by locally approximating the density function by  a normal distribution.  However,  if the dimensionality of tJ is  high,  the error bars become very  wide due to  the  curse of the dimensionality. 
An advantage of multiple pointwise imputation is the easy incorporation of extra constraints  on the missing variables.  Such constraints might include keeping only those modes that lie  in  an interval dependent on the present variables [8]  or discarding  low-probability (spuri(cid:173) ous) modes-which speeds up the reconstruction algorithm and may make it more robust. 
A faster way to generate representative points of p(tJltI) is simply to draw a fixed number  of samples from  it-which may also give robustness to poor density models.  However, in  practice this resulted in a higher reconstruction error. 
4  Continuity constraints and dynamic programming (D.P) search 
Application  of the  exhaustive mode  search  to  the  conditional  distribution  at every  point  of the  sequence produces  one  or more  candidate reconstructions  per point.  To  select  a 
2 Actually,  given  a  value  of tz, most  centroids  have  negligible  posterior probability  and  can  be  removed  from  the  mixture  with  practically  no  loss  of accuracy.  Thus,  a  large  number  of mixture  components may be used  without deteriorating excessively the computational efficiency. 
Probabilistic Sequential Data Reconstrnction 
417 
trajectory  factor an.  mean  dpmode