** Next:** Example: nlp_speech_trigram method.
** Up:** Robust parsing of word-graphs
** Previous:** Search algorithm

##

Complications for Ngrams

In this section we want to extend the * nlp_speech* method to take
into account Ngram probabilities. Obviously, we can extend the weight
tuple with a further argument which expresses the accumulated weight
according to the Ngram probabilities. However, a potential problem
arises. If we extend a given path by using the transition labeled
*w*, then we want to take into account the probability of
reading this word *w* given the previous *N*-1 words. However note that in
the definition of the annotated word-graph given above these words are not
readily available. Even if we make sure that each path is associated
with the last words seen so far, we must be careful that weights
remain uniform.

The solution to this problem is to alter the definition of the graph,
in such a way that the relevant *N*-1 words are part of the vertex.
If we want to take into account Ngram probabilities (),
then the vertices of the graph will be tuples
where *v* is a state of the word-graph as before, and
are the previous *N*-1 words. For example, in the case of
bigrams (*N*=2), vertices are pairs consisting of a word-graph state
and a word (the previous word). A number of special symbols
is introduced as beginning-of-sentence markers. The start
vertex is now
. The notation *x*:*k* is used to
refer to the last *k* elements of *x*.

The * annotated word-graph for Ngrams* is a weighted graph
(*V*,*E*) and some fixed *N*, such that:

*V* is a set of pairs
where *v* is a
word-graph state and *w*_{i} are labels in the word-graph.
The start vertex is
; the final vertex is
.
*E* is the set of edges consisting of:
* skip* edges. For all
,
and all vertices *V*_{i}=(*v*_{i},*x*) and
*V*_{j}=(*v*_{j},*xw*:*N*-1), there are edges
.
* category* edges. For all
, and for
all vertices *V*_{i}=(*v*_{i},*x*_{1}) and
*V*_{j}=(*v*_{j},*x*_{1}*x*_{2}:*N*-1),
there are edges
(*V*_{i},*V*_{j},*x*_{2},*a*,*q*).
* stopping* edges. For all
and for
all vertices *V*_{i}=(*v*_{i},*x*) there are edges
.

**Subsections**

** Next:** Example: nlp_speech_trigram method.
** Up:** Robust parsing of word-graphs
** Previous:** Search algorithm

*2000-07-10*