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]")].