Change search
ReferencesLink to record
Permanent link

Direct link
Picking up the pieces: Causal states in noisy data, and how to recover them
KTH, School of Electrical Engineering (EES), Sound and Image Processing (Closed 130101).
KTH, School of Electrical Engineering (EES), Sound and Image Processing (Closed 130101).
2013 (English)In: Pattern Recognition Letters, ISSN 0167-8655, Vol. 34, no 5, 587-594 p.Article in journal (Refereed) Published
Abstract [en]

Automatic structure discovery is desirable in many Markov model applications where a good topology (states and transitions) is not known a priori. CSSR is an established pattern discovery algorithm for stationary and ergodic stochastic symbol sequences that learns a predictively optimal Markov representation consisting of so-called causal states. By means of a novel algebraic criterion, we prove that the causal states of a simple process disturbed by random errors frequently are too complex to be learned fully, making CSSR diverge. In fact, the causal state representation of many hidden Markov models, representing simple but noise-disturbed data, has infinite cardinality. We also report that these problems can be solved by endowing CSSR with the ability to make approximations. The resulting algorithm, robust causal states (RCS), is able to recover the underlying causal structure from data corrupted by random substitutions, as is demonstrated both theoretically and in an experiment. The algorithm has potential applications in areas such as error correction and learning stochastic grammars.

Place, publisher, year, edition, pages
2013. Vol. 34, no 5, 587-594 p.
Keyword [en]
Computational mechanics, Causal states, CSSR, Hidden Markov model, HMM, Learnability
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-121467DOI: 10.1016/j.parrec.2012.11.013ISI: 000316425800020ScopusID: 2-s2.0-84873870023OAI: diva2:619085
EU, European Research Council, FP6-034362

QC 20130502

Available from: 2013-05-02 Created: 2013-04-29 Last updated: 2013-12-03Bibliographically approved
In thesis
1. Probabilistic Sequence Models with Speech and Language Applications
Open this publication in new window or tab >>Probabilistic Sequence Models with Speech and Language Applications
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Series data, sequences of measured values, are ubiquitous. Whenever observations are made along a path in space or time, a data sequence results. To comprehend nature and shape it to our will, or to make informed decisions based on what we know, we need methods to make sense of such data. Of particular interest are probabilistic descriptions, which enable us to represent uncertainty and random variation inherent to the world around us.

This thesis presents and expands upon some tools for creating probabilistic models of sequences, with an eye towards applications involving speech and language. Modelling speech and language is not only of use for creating listening, reading, talking, and writing machines---for instance allowing human-friendly interfaces to future computational intelligences and smart devices of today---but probabilistic models may also ultimately tell us something about ourselves and the world we occupy.

The central theme of the thesis is the creation of new or improved models more appropriate for our intended applications, by weakening limiting and questionable assumptions made by standard modelling techniques. One contribution of this thesis examines causal-state splitting reconstruction (CSSR), an algorithm for learning discrete-valued sequence models whose states are minimal sufficient statistics for prediction. Unlike many traditional techniques, CSSR does not require the number of process states to be specified a priori, but builds a pattern vocabulary from data alone, making it applicable for language acquisition and the identification of stochastic grammars. A paper in the thesis shows that CSSR handles noise and errors expected in natural data poorly, but that the learner can be extended in a simple manner to yield more robust and stable results also in the presence of corruptions.

Even when the complexities of language are put aside, challenges remain. The seemingly simple task of accurately describing human speech signals, so that natural synthetic speech can be generated, has proved difficult, as humans are highly attuned to what speech should sound like. Two papers in the thesis therefore study nonparametric techniques suitable for improved acoustic modelling of speech for synthesis applications. Each of the two papers targets a known-incorrect assumption of established methods, based on the hypothesis that nonparametric techniques can better represent and recreate essential characteristics of natural speech.

In the first paper of the pair, Gaussian process dynamical models (GPDMs), nonlinear, continuous state-space dynamical models based on Gaussian processes, are shown to better replicate voiced speech, without traditional dynamical features or assumptions that cepstral parameters follow linear autoregressive processes. Additional dimensions of the state-space are able to represent other salient signal aspects such as prosodic variation. The second paper, meanwhile, introduces KDE-HMMs, asymptotically-consistent Markov models for continuous-valued data based on kernel density estimation, that additionally have been extended with a fixed-cardinality discrete hidden state. This construction is shown to provide improved probabilistic descriptions of nonlinear time series, compared to reference models from different paradigms. The hidden state can be used to control process output, making KDE-HMMs compelling as a probabilistic alternative to hybrid speech-synthesis approaches.

A final paper of the thesis discusses how models can be improved even when one is restricted to a fundamentally imperfect model class. Minimum entropy rate simplification (MERS), an information-theoretic scheme for postprocessing models for generative applications involving both speech and text, is introduced. MERS reduces the entropy rate of a model while remaining as close as possible to the starting model. This is shown to produce simplified models that concentrate on the most common and characteristic behaviours, and provides a continuum of simplifications between the original model and zero-entropy, completely predictable output. As the tails of fitted distributions may be inflated by noise or empirical variability that a model has failed to capture, MERS's ability to concentrate on high-probability output is also demonstrated to be useful for denoising models trained on disturbed data.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2013. xviii, 80 p.
Trita-EE, ISSN 1653-5146 ; 2013:042
Time series, acoustic modelling, speech synthesis, stochastic processes, causal-state splitting reconstruction, robust causal states, pattern discovery, Markov models, HMMs, nonparametric models, Gaussian processes, Gaussian process dynamical models, nonlinear Kalman filters, information theory, minimum entropy rate simplification, kernel density estimation, time-series bootstrap
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
urn:nbn:se:kth:diva-134693 (URN)978-91-7501-932-1 (ISBN)
Public defence
2013-12-17, D3, Lindstedtsvägen 5, KTH, Stockholm, 09:00 (English)
ACORNS: Acquisition of Communication and Recognition SkillsLISTA – The Listening Talker
EU, European Research Council, FP6-034362EU, FP7, Seventh Framework Programme, 256230

QC 20131128

Available from: 2013-11-28 Created: 2013-11-27 Last updated: 2013-11-28Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Henter, Gustav EjeKleijn, W. Bastiaan
By organisation
Sound and Image Processing (Closed 130101)
In the same journal
Pattern Recognition Letters
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 117 hits
ReferencesLink to record
Permanent link

Direct link