3  An Abstract Model of Incremental Processing

3.1  The Abstract Model

On a very abstract level, linguistic processing is about building structure. Speech recognisers build up word lattices (networks of hypotheses over acoustic signal), parsers build up syntactic structures which, if used in the context of larger processing systems, are connected with semantic structures, and so on. In modular systems, typically the modules work in a pipeline fashion, taking structures built by the previous module as input and building their structures using this information. Which linguistic unit - word, sentence, paragraph, text - they are working on depends on the task, but whatever this unit is, it normally is processed as a whole, and the output of the module relates to this whole unit.

This is what incremtal systems change. The major characteristic of such systems, which only makes them incremental, is that they, compared to typical, non-incremental systems, can consume input in smaller units. For a parser, this may mean that it is fed what ultimately will amount to a sentence (or rather, an utterance) word-by-word instead of en bloc, or for a generator it may mean that it receives an intention that only partly describes what is to be verbalised.

What at first may seem like a small change offers many new possibilities, but also opens up new questions. How shall such intermediate results, based on "incomplete" input be represented? Can results of further processing of intermediate output guide the processing of the remaining input; that is, should information be `fed back' to earlier modules? How often should a module produce new output; e.g., every time it receives an input chunk, or can it `collect' input chunks before it forms a new output chunk? If an earlier module made a mistake, can the module return to an earlier state also incrementally, that is, by `removing' only those bits of output that correspond to the revoked input?

To be able to describe the different possible behaviours of modules and module combinations, we developed an abstract model of incremental processing that tries to abstract away from questions of how the actual processing proceeds and focusses on ways incremental information can be communicated throughout an incremental system Schlangen and Skantze, [2009,Schlangen and Skantze, [2011] (both papers were entitled "A general, abstract model of incremental dialogue processing", the latter being a revised and greatly extended journal version of the former).

The basic ideas of this model are simple: we call the units that are communcated between modules incremental units (IUs), and we assume that two types of relations between IUs are important in such a system. Same level links (SLL) connect IUs together and basically communicate "these are the bits out of which one larger unit can be built (and, if that matters to you, in this order)". For example, the words hypothesised by an incremental speech recogniser can be seen as connected with this relation, and linking two different words with the same precursor can express alternative or parallel hypotheses. (Modules where the output IUs stand in a more complex relation than sequentiality, e.g., trees representing configurations of constituents, will need an additional kind of SLL to represent this.)

The second type of relations are grounded in links (GRIN), which connect a module's internal data structures (and the IUs it outputs) to its input IUs. They are of use when such input IUs are revoked by the module that produced them, because they do not represent its best hypothesis anymore. GRIN links allow the processing module to compute what its reaction should be to such a revokation, i.e. which of its own structures have lost their grounding.

As shown in Schlangen and Skantze, [2009,Schlangen and Skantze, [2011], these concepts (IUs, linked through certain relations), provide a vocabulary that allows us to describe different possible configurations of modules and module behaviours. They can also more directly inspire the architecture of implemented systems, as described in the next section.

3.2  Computational "middlewares" inspired by the model

The abstract model described in the previous section has been taken up by several groups who used it as a basis for implementing computational "middlewares", that is, an architectural component that deals with inter-module communication in a modular system. In the paper Baumann et al., [2010,Schlangen et al., [2010] ("Middleware for incremental processing in conversational agents") we came together to describe the similarities and the differences of the approaches. Schlangen and Skantze, [2011] also has some more general thoughts about different possible implementation design decisions.

Baumann et al., [2010] ("InproTK in action: Open-source software for building german-speaking incremental spoken dialogue systems") finally describes the approach that is mainly develop within the InPro project in some more detail.


This website reports on some results of the research project "InPro", which was led by David Schlangen and ran from 2006 to 2011. The information contained in this website is for general information purposes only; we make no representations or warranties of any kind, express or implied, about the completeness, accuracy, reliability, suitability or availability with respect to the website or the information, products, services, or related graphics

... Continued

contained on the website for any purpose. Any reliance you place on such information is therefore strictly at your own risk.
Through this website you are able to link to other websites which are not under the control of us or Bielefeld University. We have no control over the nature, content and availability of those sites. The inclusion of any links does not necessarily imply a recommendation or endorse the views expressed within them.