next up previous
Next: State Space Models Up: Acceptors and Transducers Previous: Generalized Transducers

Variable Length Markov Models

 

In this section we will briefly mention some constructive learning algorithms for acceptors and transducers, which learn to process discrete sequences (e.g., for language modeling tasks).

A Variable Length Markov Model [&make_named_href('', "node31.html#rissanen83","[116]"), &make_named_href('', "node31.html#Ron94","[10]"), &make_named_href('', "node31.html#weinberger95","[117]"), &make_named_href('', "node31.html#buhlmann97","[118]")] is a probability model over strings in which the state variable is not hidden: its value is a deterministic function of the past observation sequence. However, this function uses more or less of the past sequence for different contexts, hence the name, variable length Markov model. For example, for subsequences which are more frequent, a deeper context may be maintained.

When d=0 the next output distribution is unconditional. A tree of suffixes for past contexts is used to efficiently represent this distribution, with each node representing a particular context , and the children of a node representing contexts that are deeper by one time step. A constructive, on-line (one-pass), learning algorithm was proposed to adaptively grow this tree [&make_named_href('', "node31.html#Ron94","[10]")]. Each node of the tree at depth d represents a particular value of the context of depth d, and may be associated with a distribution over the next symbol . The basic idea is to add a child to a node (i.e., deeper context for certain values of the context) when one measures a sufficiently large Kullback-Liebler divergence (or relative entropy) of the next-output distribution of the child from that of the parent node. The potential branching factor of the tree is equal to the size of the alphabet for , but most nodes may have much fewer children. More recently, an extension of this idea to probabilistic but synchronous transducers was proposed [&make_named_href('', "node31.html#Singer96","[11]")]:

Like in the unconditional case, this model can also be conveniently represented by a tree, where each node represents a particular input context, associated with a distribution on the next output given that input context, and the root is associated with the unconditional distribution of the next output. An on-line, one-pass, constructive learning algorithm for suffix tree transducers is proposed that adaptively grows the tree when new contexts are encountered (possibly up to a maximum depth D). A simple pruning algorithm can be used to discard deep nodes with low posterior probability (i.e., the normalized product of the probability of emitting the right data, times a prior which depends exponentially on the depth). Using these posteriors, a mixture over a very large family of such trees can be formed, whose generalization performance tracks that of the best tree in that family [&make_named_href('', "node31.html#Singer96","[11]")]. These algorithms were used in language modeling [&make_named_href('', "node31.html#Guyon95","[35]"), &make_named_href('', "node31.html#Singer96","[11]")] and handwritten character recognition [&make_named_href('', "node31.html#Guyon96","[36]")].


next up previous
Next: State Space Models Up: Acceptors and Transducers Previous: Generalized Transducers

Yoshua Bengio
Tue Oct 7 08:34:36 EDT 1997