next up previous
Next: Variable Length Markov Models Up: Acceptors and Transducers Previous: Acceptors and Transducers

Generalized Transducers

A way to generalize transducers was recently proposed [&make_named_href('', "node31.html#Bottou+96","[114]"), &make_named_href('', "node31.html#lecun-97","[115]")] which allows any kind of data structure to be used as ``labels'' (instead of discrete symbols) in the sequences to be processed, and allows the transducers and acceptors to have parameters that are learned with respect to a global criterion.

  
Figure 11: Example of application of a generalized transducer to the task of reading the courtesy amount on check images. The initial (input) graph represents the whole check image. The system computes and is trained to maximize the probability of the correct answer given this input graph.

In this framework, data processing is viewed as a transformation of directed acyclic weighted graphs into other directed acyclic weighted graphs. These graphs are different from the graphs which may be used to represent transducers and acceptors. They are usually different representations of the data, not of the model. They have a start node and an end node, and they typically represent a set of hypotheses: each path from an initial node to a final node corresponds to a distinct hypothesis, with a weight that is the sum (or the product) of the weights on the individual arcs. When normalized over all the paths, these path weights can be formally interpreted as probabilities for different hypotheses (conditional on the assumption that the correct hypothesis is one of those represented in the graph). Note again that although these weights can be formally interpreted as probabilities, they should be viewed as tools for decision-taking, rather than the actual and true probabilities that certain events would take place. As such they do not need to be normalized as probabilities.

An object that maps one such graph to another one is called a transformer and can be viewed as a generalization of a transducer. Many transformers can be stacked on top of each other, using the composition operation of transducers, in a processing style that resembles the multi-layer neural networks, but in which the intermediate variables are not simply numeric vectors but instead graphs representing a set of sequential interpretations for some data, with arbitrary data structures attached to the arcs of the graph.

In a typical sequence recognition application, a learning criterion is defined at the last level of the transformers cascade, e.g., as in the maximum mutual information criterion, to maximize the weight (or posterior probability given the input data) of the hypotheses corresponding to a correct interpretation of the data, and minimize the score or probability of alternative interpretations of the data. As in multi-layer neural networks, the parameters of a transformer can be learned by propagating gradients with respect to this criterion in the reverse direction.

This approach was successfully used as part of a document analysis system [&make_named_href('', "node31.html#Bottou+96","[114]")] that reads amounts from check images. It is used by customers of NCR to process millions of checks per day. Whereas HMMs allow all possible segmentations before taking a decision, the segmentation of the input (image) sequence used in this system is based on two steps. In the first step, heuristics are used to select plausible cutting points and segments (in the form of a graph where each path from the source to the final node represents a segmentation of the whole image). In the second step, each possible segment is weighed (according to the character recognizer and the language model) and the best segmentation is finally selected (along the with the recognized sequence of words). A transducers cascade such that illustrated in Figure 11 was used. It incorporates a sequence of processing stages, such as generating field location hypotheses (where in the whole check image might the courtesy amount be located?), segmentation hypotheses (how to cut a word image into a sequence of character sub-images?), isolated character recognition hypotheses (what character class should be associated to each character segment hypothesis?), and a language model (preferences on the possible sequences of characters). In the figure, the data structures associated to each arc of the hypotheses graph are different at the different levels of processing: initially it is the whole image, after field location and segmentation it is a piece of image, and subsequently it is a character class. The training criterion can be interpreted as maximizing the likelihood of the correct class given the input observation, and it is formulated as the ratio of the sum of the scores of paths that are consistent with the correct answer to the sum of the scores of all the paths at the last level (interpretation graph). The Viterbi algorithm may also be applied on the interpretation graph in order to obtain an answer (represented by a path), given the input observation.


next up previous
Next: Variable Length Markov Models Up: Acceptors and Transducers Previous: Acceptors and Transducers

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