Time Mapping with Hypergraphs

Time Mapping with Hypergraphs Jan W. Amtrup Volker Weber Computing Research Laboratory University of Hamburg, New Mexico State University Computer Science Department, Las Cruces, NM 88003,USA Vogt-K611n-Str. 30, D-22527 Hamburg, Germany email: jamtrup~crl.nmsu, edu email: weber@informatik.uni-hamburg.de Abstract Word graphs are able to represent a large num- ber of different utterance hypotheses in a very compact manner. However, usually they con- tain a huge amount of redundancy in terms of word hypotheses that cover almost identi- cal intervals in time. We address this problem by introducing hypergraphs for speech process- ing. Hypergraphs can be classified as an ex- tension to word graphs and charts, their edges possibly having several start and end vertices. By converting ordinary word graphs to hyper- graphs one can reduce the number of edges considerably. We define hypergraphs formally, present an algorithm to convert word graphs into hypergraphs and state consistency proper- ties for edges and their combination. Finally, we present some empirical results concerning graph size and parsing efficiency. 1 Introduction The interface between a word recognizer and language processing modules is a crucial issue with modern speech processing systems. Given a sufficiently high word recognition rate, it suf- fices to transmit the most probable word se- quence from the recognizer to a subsequent module (e.g. a parser). A slight extension over this best chain mode would be to deliver n-best chains to improve language processing results. However, it is usually not enough to deliver just the best 10 or 20 utterances, at least not for reasonable sized applications given todays speech recognition technology. To overcome this problem, in most current systems word graphs are used as speech-language interface. Word graphs offer a simple and efficient means to rep- resent a very high number of utterance hypothe- ses in a extremely compact way (Oerder and Ney, 1993; Aubert and Ney, 1995). und (and) dann (then) Figure 1: Two families of edges in a word graph Although they are compact, the use of word graphs leads to problems by itself. One of them is the current lack of a reasonable measure for word graph size and evaluation of their contents (Amtrup et al., 1997). The problem we want to address in this paper is the presence of a large number of almost identical word hypotheses. By almost identical we mean that the start and end vertices of edges differ only slightly. Consider figure 1 as an example section of a word graph. There are several word hypothe- ses representing the words und (and) and dann (then). The start and end points of them differ by small numbers of frames, each of them 10ms long. The reasons for the existence of these fam- ilies of edges are at least twofold: * Standard HMM-based word recognizers try to start (and finish) word models at each individual frame. Since the resolution is quite high (10ms, in many cases shorter than the word onset), a word model may have boundaries at several points in time. • Natural speech (and in particular …

Content truncated to 500 words