DE69717899T2

DE69717899T2 - Verfahren und Vorrichtung zur Spracherkennung

Info

Publication number: DE69717899T2
Application number: DE69717899T
Authority: DE
Inventors: Hiyan Alshawi
Original assignee: Lucent Technologies Inc
Current assignee: Nokia of America Corp
Priority date: 1996-04-10
Filing date: 1997-04-01
Publication date: 2003-08-21
Anticipated expiration: 2017-04-02
Also published as: EP0801378A3; EP0801378B1; EP0801378A2; MX9702521A; CA2198306C; US5870706A; CA2198306A1; DE69717899D1

Description

Technisches Gebiet

Die vorliegende Erfindung betrifft allgemein die Sprachenerkennung und insbesondere ein verbessertes Sprachenerkennungssystem, das ein probabilistisches lexikales Assoziationsmodell verwendet.

Allgemeiner Stand der Technik

Die Spracherkennung ist ein Vorgang, durch den eine unbekannte Sprachäußerung ("Eingangssignal") identifiziert wird. Die Spracherkennung umfaßt in der Regel eine Signalverarbeitungsstufe, in der mehrere Wortkettenhypothesen, d. h. mögliche Wortsequenzen, für das Eingangssignal vorgeschlagen werden. Die Aufgabe besteht darin, die "beste" Wortkette aus einer Menge von Hypothesen zu erkennen oder zu identifizieren, d. h. aus vorgeschlagenen Wortketten, die mit dem Eingangssignal vereinbar sind. Spracherkennungssysteme verwenden für diesen Zweck ein Sprachenmodell.
Typische Spracherkennungssysteme können ein quantitatives Sprachenmodell verwenden. Quantitative Modelle ordnen jeder Hypothese einen "Kostenfaktor" zu, wobei die Hypothese mit dem niedrigsten Kostenfaktor als die erkannte Wortkette ausgewählt wird.
Ein Beispiel für ein quantitatives Modell ist ein probabilistisches Sprachenmodell. Probabilistische Modelle weisen Wortketten Wahrscheinlichkeiten zu und wählen die Kette, die die höchste Wahrscheinlichkeit aufweist, ein gegebenes Eingangssignal darzustellen. Die Wahrscheinlichkeitsberechnung kann mit vielfältigen Verfahren durchgeführt werden. Ein solches Verfahren, das als das N-gramm-Modell bezeichnet wird, gibt die Wahrscheinlichkeit eines Worts, das Teil einer Kette ist, konditional an den vorherigen N - 1 Wörtern in der Kette an. Siehe zum Beispiel Jelinek et al., "Principles of Lexical Language Modeling for Speech Recognition", Adv. Speech Signal Processing, S. 651-699 (1992). Das N-gram-Modell ist insofern lexikalisch empfindlich, als die Parameter des Modells bestimmten lexikalischen Elementen, d. h. Worten zugeordnet werden. Durch diese Empfindlichkeit kann das Modell lokale Verteilungsmuster erfassen, die für bestimmte Wörter idiosynkratisch sind.
Ein zweites Verfahren, das als stochastische kontextfreie Grammatik bezeichnet wird, verwendet eine baumartige Datenstruktur, bei der Wörter in einem Eingangssignal als Randnoten eines Baums erscheinen. Wahrscheinlichkeiten werden als die Summe von Wahrscheinlichkeiten aller Baumableitungen zugewiesen, für die Wörter in der Kandidatenkette als Randnoten erscheinen. Siehe zum Beispiel Jelinek et al., "Computation of the Probability of Initial Substring Generation by Stochastic Context-Free Grammers", Computational Linguistics, Band 17(3), S. 315-324 (1991). Bei kontextfreien Grammatiken werden strukturelle Eigenschaften modelliert, d. h. die Wahrscheinlichkeit, daß eine Phrase einer bestimmten Kategorie, z. B. Nomen- oder Verbphrasen, in Teilphrasen spezifizierter Kategorien zerlegt werden kann.
Beide oben erwähnten Verfahren zum Bewerten der Wahrscheinlichkeit haben Nachteile. Das N-gram-Modell ist zwar lexikalisch empfindlich, erleidet jedoch, da es keine bedeutungsvollen Assoziationen mit großer Reichweite zwischen Wörtern erfassen kann, Nachteile. Wenn Grammatik ignoriert wird, gehen nützliche Informationen verloren, die nur aus grammatischen Beziehungen zwischen Wörtern abgeleitet werden können. Obwohl eine stochastische kontextfreie Grammatik gegenüber solchen grammatischen Beziehungen empfindlich ist, kann sie keine Assoziationen zwischen lexikalischen Elementen erfassen, die semantische Informationen wiedergeben, durch die eine Kette wesentlich wahrscheinlicher als eine andere wird. Ein Sprachenmodell, das nicht sowohl semantische als auch strukturelle Informationen berücksichtigt, hat unweigerlich durch Genauigkeitsverlust Nachteile.
Die Wahrscheinlichkeitsmodelle des Stands der Technik werden in der Regel zu einem großen Automaten zusammengestellt. Der oben erwähnte Nachteil der lexikalisch empfindichen Wahrscheinlichkeitsmodelle ist teilweise auf diese Struktur zurückzuführen. Die gewöhnlich für die Spracherkennung implementierten Automaten sind in der Regel auf eine Bewegung nach links oder rechts durch die Wortkettenhypothesen begrenzt und verarbeiten Wortketten wortweise. Als Folge gehen die Assoziationen mit großer Reichweite zwischen Wörtern verloren.
Eine Zusammenstellung von stochastischen kontextfreien Grammatiken oder besser Approximationen solcher Grammatiken zu einem großen Automaten begrenzt die Fähigkeit dieser Modelle, Assoziationen mit großer Reichweite zu erfassen, nicht. Wie bereits besprochen, werden solche Assoziationen aufgrund der Beschaffenheit des Modells erfaßt. Es besteht jedoch ein anderer Nachteil, der mit der Verwendung eines einzigen großen Automaten zusammenhängt und beide Arten von Wahrscheinlichkeitsmodellen betrifft. Bei der Zusammenstellung des Modells zu einem großen Automaten muß das vollständige Lexikon oder Vokabular des Sprachenmodells darin enthalten sein. Im typischen Fall einer Softwareimplementierung werden solche Automaten zu groß für Computer mit begrenztem RAM-Speicher.
Deshalb wird ein Sprachenmodell benötigt, das sowohl lexikalische als auch strukturelle Empfindlichkeit aufweist und bei Implementierung in Software kompakt genug ist, um auf Computern mit begrenztem RAM-Speicher installiert zu werden.

Kurze Darstellung der Erfindung

Es werden Verfahren und Vorrichtungen für ein verbessertes Sprachenmodell und Sprachenerkennungssysteme offengelegt. Gemäß der in den Ansprüchen 1-13 definierten vorliegenden Erfindung steuern mehrere "kleine" Automaten das Sprachenmodell an. Jeder dieser Automaten hat die Fähigkeit, ein Paar von Sequenzen zu erkennen, wobei eines nach links und das andere nach rechts abgetastet wird. Jeder Automat, der hier als lexikalischer Kopfautomat bezeichnet wird, entspricht einem Wort im Vokabular des Sprachenmodells. Gemäß den vorliegenden Verfahren werden nur die lexikalischen Kopfautomaten aktiviert, die den in den Wortkettenhypothesen enthaltenen Wörtern entsprechen.
Durch die aktivierten lexikalischen Kopfautomaten werden Phrasen aus den in den Wortkettenhypothesen enthaltenen Wörtern durch eine Reihe von Links- und Rechtsübergängen aufgebaut oder abgeleitet. Die lexikalischen Kopfautomaten erzeugen mehrere solcher Phrasen für die verschiedenen Wörter, während sie Assoziationen mit anderen Wörtern in den Wortkettenhypothesen bilden. Die lexikalischen Kopfautomaten berechnen inkrementell einen "Kostenfaktor" für die abgeleiteten Phrasen. Der Kostenfaktor hängt mit der Wahrscheinlichkeit zusammen, daß die abgeleitete Phrase mit dem Eingangssprachensignal übereinstimmt. Die Phrase mit dem niedrigsten Kostenfaktor wird als die Phrase ausgewählt, die dem Eingangssprachensignal entspricht.
Wie bereits erwähnt, verwendet das vorliegende Verfahren eine begrenzte Menge "kleiner" lexikalischer Kopfautomaten, entsprechend den Wörtern in den Wortkettenhypothesen, anstelle eines "großen" Automaten, der das gesamte Vokabular enthält. Folglich können die vorliegenden Verfahren und Vorrichtungen mit wesentlich weniger RAM-Speicher als vorbekannte Sprachenerkennungssysteme implementiert werden.
Die Automaten der vorliegenden Erfindung, die ein Paar von Sequenzen erkennen, unterscheiden sich von sogenannten "zweiseitigen" Automaten, die sich entweder nach links oder nach rechts bewegen können, aber nur eine einzige Sequenz erkennen. Solche zweiseitigen Automaten sind in der Technik bekannt und besitzen dieselbe Erkennungsleistung wie Automaten, die sich nur von links nach rechts bewegen können. Siehe zum Beispiel Hopcroft et al., Introduction to Automata Theory, Languages and Computation, (Addison Wesley, 1979).
Ungeachtet solcher zweiseitigen Automaten sind die in der Regel im Stand der Technik zur Spracherkennung verwendeten Automaten auf die Verarbeitung von Wortketten durch Bewegung von links nach rechts begrenzt, während die in der vorliegenden Erfindung verwendeten lexikalischen Kopfautomaten die Eingabe gleichzeitig nach links und nach rechts bestimmter Wörter in der Mitte der Kette abtasten. Dies führt zu genaueren Vorhersagen angrenzender Wörter, da die Verarbeitung mit einem weniger häufigen Wort beginnen kann, wodurch die Möglichkeiten für das angrenzende Wort begrenzt werden. Man betrachte den folgenden Beispielsatz: "Ich will den Transistor". Ein Automat, der auf eine Verarbeitung von links nach rechts beschränkt ist, muß das Wort wählen, das "den" folgt, d. h. "ich will den?". Es ist anzunehmen, daß sehr viele Wörter in dem bestimmten Vokabular, das verwendet wird, geeignet dem Wort "den" in dem Beispielsatz folgen können. Die lexikalischen Kopfautomaten der vorliegenden Erfindung, die in beiden Richtungen verarbeiten, sind frei, mit dem Wort "Transistor" zu beginnen und das vorherige Wort zu wählen. Es gibt wesentlich weniger Wahlmöglichkeiten für Wörter, die geeignet dem Wort "Transistor" vorausgehen können, als Wörter, die dem Wort "den" folgen.
Durch Verwendung mehrerer kleiner lexikalischer Kopfautomaten sind die vorliegenden Verfahren und Vorrichtungen sowohl lexikalisch als auch strukturell empfindlich. Lexikalische Zuordnungen werden erfaßt, da an jedem Kopfautomatenübergang Kostenfaktoren beteiligt sind, die an bestimmte lexikalische Elemente, d. h. Wortzuordnungen, gebunden sind. Die implizit in der hierarchischen Organisation eines Satzes vorliegenden strukturellen Assoziationen werden als Folge der Kaskade lexikalischer Kopfautomaten erfaßt.

Kurze Beschreibung der Zeichnungen

Weitere Merkmale der Erfindung werden aus der folgenden ausführlichen Beschreibung spezifischer Ausführungsformen in Verbindung mit den beigefügten Zeichnungen deutlicher. Es zeigen:
Fig. 1 ein Verfahren gemäß der vorliegenden Erfindung zum Implementieren eines Spracherkennungssystems;
Fig. 2 eine Darstellung eines Wortverbands;
Fig. 3 ein Diagramm von Zustandsübergängen für einen beispielhaften lexikalischen Kopfautomaten gemäß der vorliegenden Erfindung;
Fig. 4 eine Ausführungsform eines Verfahrens gemäß der vorliegenden Erfindung zur Erzeugung mehrerer Phrasendatensätze zur Auswahl der besten Wahl mehrerer Wortkettenhypothesen;
Fig. 5 eine beispielhafte Teilphrasenableitung, die durch die vorliegenden Verfahren und Vorrichtungen für eine einfache Wortkette erzeugt wird; und
Fig. 6 die lexikalischen Kopfautomaten und Übergängen, die zur Erzeugung der Teilphrasenableitung von Fig. 5 erforderlich sind.

Ausführliche Beschreibung

Die vorliegende Erfindung betrifft Sprachenmodellierungsverfahren zur Verwendung in vielfältigen Sprachenerkennungsanwendungen. Die Rolle des Sprachenmodells bei der Sprachenerkennung umfaßt eine Identifizierung der "besten" Wortkette aus einer Menge von Wortkettenhypothesen, die von anderen Teilen des Sprachenerkennungssystems abgeleitet werden. Die vorliegende Erfindung wird im Kontext der Spracherkennung beschrieben. Es versteht sich jedoch, daß die vorliegenden Verfahren auch auf alle Modalitäten der Sprachenerkennung anwendbar sind, darunter ohne Einschränkung die Handschrifterkennung und optische Zeichenerkennung. Außerdem versteht sich, daß die vorliegenden Verfahren als Software oder als Hardware implementiert werden können.
Fig. 1 ist eine Darstellung eines Sprachenerkennungsverfahrens gemäß der vorliegenden Erfindung. Auf seine Grundlagen reduziert, kann ein solches Verfahren Sprachsignalverarbeitung (SSP), Sprachenanalyse (LA) und Anwendungsverarbeitung (AP) umfassen.
Das Verfahren beginnt mit der Sprachsignalverarbeitung SSP, bei der ein Sprachsignal angenommen und eine Menge von mit diesem Sprachsignal zu vereinbarenden Wortkettenhypothesen erzeugt wird. Bei einem Spracherkennungssystem werden die Wortkettenhypothesen durch ein sogenanntes "akustisches Modell" erzeugt. Solche Modelle sind Fachleuten wohl bekannt.
Genauer gesagt, umfaßt die Sprachsignalverarbeitung SSP eine Umsetzung eines analogen Sprachsignals in ein digitales Sprachsignal im Operationsblock 10 und ein Suchen mit einem Erkennungsnetzwerk und ein Erzeugen von Wortkettenhypothesen im Operationsblock 15. Bei Verwendung in den vorliegenden Sprachenerkennungsverfahren erzeugt diese Signalverarbeitung die Wortkettenhypothesen als Wortsequenzierung, gleichgültig, ob ein Sprachsignal verarbeitet wird oder ob diese Verarbeitung andere Modalitäten der Sprachenerkennung betrifft. Diese Wortsequenzierung kann ohne Einschränkung eine explizite Menge von Kandidatenwortketten oder vorzugsweise eine Wortverbanddatenstruktur umfassen. Der Wortverband ist ein wohlbekanntes Konstrukt zum Speichern einer Ansammlung möglicher Zeichenketten, wobei eine gemeinsame Nutzung von Teilketten erlaubt ist. Die in den Operationsblöcken 10 und 16 referenzierten Techniken sind in der Technik wohl bekannt.
Die Sprachenanalyse LA nimmt die Wortkettenhypothesen an und wählt aus diesen unter Verwendung eines Sprachenmodells gemäß den vorliegenden Lehren die beste Wortkette. Die Verfahren und Vorrichtungen der vorliegenden Erfindung betreffen insbesondere diesen Aspekt des Sprachenerkennungsprozesses. Das vorliegende Sprachenmodell kann dann in einem Sprachenerkennungssystem, wie zum Beispiel dem gerade beschriebenen Spracherkennungssystem, implementiert werden.
Genauer gesagt werden die Wortkettenhypothesen im Operationsblock 20 aus der Sprachsignalverarbeitung SSP empfangen. Das Sprachenmodell wird angewandt, um eine Liste möglicher Wortketten oder Phrasen entsprechend dem Eingangssprachsignal zu erzeugen und einzustufen (Operationsblock 22). Im Operationsblock 24 wird die beste Wortkette gewählt, und, wie im Operationsblock 26 angegeben, die beste Wortkette wird zu der Anwendungsverarbeitung AP gesendet. Die Anwendungsverarbeitung nimmt somit die beste Kette an und verarbeitet diese Kette dann je nachdem, z. B. Übersetzung, Transkription oder dergleichen. Nachdem nun beschrieben wurde, wo Verfahren und Vorrichtungen für das vorliegende Sprachenmodell in den Sprachenerkennungsprozeß bzw. in das Sprachenerkennungssystem gemäß der vorliegenden Erfindung passen, sollen nun das vorliegende Sprachenmodell und Verfahren zu seiner Implementierung ausführlich beschrieben werden.
Wie bereits beschrieben, empfängt die Sprachenanalyse LA eine Menge von Wortkettenhypothesen. Vorzugsweise liegen diese Wortketten in Form eines Wortverbands, d. h. eines gerichteten azyklischen Graphen, vor. Ein beispielhafter Wortverband ist in Fig. 2 dargestellt. Der Wortverband enthält eine Menge von Anfangsknoten I, die in Fig. 2 durch 10 dargestellt ist, und eine Menge von Endknoten J, die in Fig. 2 durch j1 und j2 dargestellt ist. Die durch den Wortverband dargestellten Hypothesen entsprechen möglichen Wegen von der Menge von Anfangsknoten I zu der Menge von Endknoten J.
Der Wortverband ist außerdem durch mehrere "Verbandbogen" oder "Wortbogen" gekennzeichnet, die mit einem Wort w zwischen zwei Positionen gekennzeichnet werden, die Zeitpunkte für Sprache darstellen. Die Bogen werden außerdem mit einem Kostenfaktor co gekennzeichnet, der wiedergibt, wie gut das Wort mit diesem Teil des Eingangssignals übereinstimmt. Zum Beispiel sind in Fig. 2 die Wortbogen mit w&sub0;, c0 bis w8, c8 gekennzeichnet. Der Verband und die Kostenfaktoren werden während der Sprachsignalverarbeitung SSP unter Verwendung von in der Technik wohl bekannten Techniken erzeugt. Der Wortbogenkostenfaktor wird von dem vorliegenden Verfahren akkumuliert und trägt somit zu dem Kostenfaktor einer Phrase bei, wodurch er eine Rolle bei der Bestimmung der besten Phrase spielt.
Die Menge von Bogen in dem Eingangswortverband kann somit durch eine Menge von Datensätzen der Form < w,i, j,co> dargestellt werden, wobei i und j Indizes für die Verbandknoten sind. Bei einem Verband, der aus einem Sprachsignal erzeugt wird, ist die gewöhnliche Interpretation für einen solchen Bogendatensatz, daß das Wort w mit dem Eingangssprachensignal von der Zeitposition i bis zu der Zeitposition j mit dem Kostenfaktor co übereinstimmt.
Nachdem sie einen Wortverband erhalten, werden die lexikalischen Kopfautomaten für die in dem Verband vorliegenden Wörter aktiviert. Jeder lexikalische Kopfautomat besteht aus einer endlichen Menge von Zuständen Q und einer Aktionstabelle T mit Kostenfaktoren. Einträge in der Aktionstabelle können entweder Beginnaktionen, Linksübergänge, Rechtsübergänge oder Stoppaktionen sein. Die Notation C(A,m) stellt den Gesamtkostenfaktor einer Sequenz von Aktionen A = a1...ak dar, die von einem lexikalischen Kopfautomaten m unternommen wird, wobei a&sub1; die Startaktion und ak eine Stoppaktion ist. C(A,m) ist somit die Summe der Kostenfaktoren für Aktionen in der Sequenz A.
Fig. 3 ist ein Diagramm von Zustandsübergängen für einen beispielhaften lexikalischen Kopfautomaten gemäß der vorliegenden Erfindung. Die Knoten q1-q6 stellen verschiedene Zustände des lexikalischen Kopfautomaten dar. Bogen zwischen den Knoten zeigen Zustandsübergänge, wobei der Kopfautomat eine Phrase aufbraucht, wie durch w "n", z. B. w&sub2; usw. angegeben wird. Die Zustandsübergänge können als Links- oder Rechtsaktionen gekennzeichnet werden, wie durch die Richtung des Pfeils neben der Phrase angegeben wird. Zum Beispiel bewegt sich der beispielhafte lexikalische Kopfautomat von Zustand 1 zu Zustand 2 durch Aufbrauchen der Phrase w&sub2; in einem Linksübergang. Der Automat verfolgt zwei Positionszeiger in der Kette. Ein Linksübergang bewegt den Linkszeiger nach links und ein Rechtsübergang bewegt den Rechtszeiger nach rechts. Die Pfeilspitzen bei q1 und q2 zeigen an, daß sich an diesen Zuständen ein endlicher Startaktionskostenfaktor befindet. Anders ausgedrückt sind diese wahrscheinliche Startpunkte für die Phrase. Die anderen Zustände weisen unendliche Startaktionskostenfaktoren auf und sind somit unwahrscheinliche Startpunkte für die Phrase. Die konzentrischen Kreise bei q3 und q6 zeigen an, daß an diesen Zuständen ein endlicher Stoppaktionskostenfaktor besteht.
Der lexikalische Kopfautomat für ein Wort w baut eine Phrase, d. h. eine Anordnung der Wörter in dem Verband, durch eine Reihe von Links- oder Rechtsübergängen auf bzw. leitet diese ab. Bei jedem Übergang wird die Phrase durch "aufbrauchen" einer angrenzenden Phrase erweitert, die ihrerseits durch einen anderen lexikalischen Kopfautomaten für ein Wort w' als eine "Teilphrasenableitung" gebildet wurde. Eine solche Bewegung entspricht der Bildung einer Assoziation zwischen w, "dem Kopf", und w', "dem Abhängigen". Somit erzeugen die lexikalischen Kopfautomaten für die verschiedenen Wörter mehrere solcher Phrasen, während sie Assoziationen mit anderen Wörtern in dem Wortverband bilden. Ein Beispiel für eine Teilphrasenableitung, lexikalische Kopfautomaten und die eigentlichen Übergänge für die Automaten, so wie sie gemäß der vorliegenden Erfindung zur Erkennung eines Probensatzes erzeugt werden, werden später in der vorliegenden Beschreibung vorgestellt.
Das Verfahren wird durch Hinzufügen solcher Phrasen in verschiedenen Zuständen der Vervollständigung zu einem Phrasenverband fortgesetzt. Dieser Verband, der von dem Wortverband unterschieden wird, ist eine Menge von Phrasendatensätzen, die jeweils einem bestimmten Zustand des Ausführens eines lexikalischen Kopfautomatens für ein bestimmtes Wort entsprechen. Ein Phrasendatensatz enthält die folgenden Felder: < w,s,i,j,q,m,c> . In dem Datensatz ist w der Kopf einer Phrase (möglicherweise unvollständig), der in seiner aktuellen Phase der Vervollständigung die Positionen i bis j überspannt. Die Phrase ist gemäß dem lexikalischen Kopfautomaten m aufgebaut, wobei der aktuelle Zustand von m q ist. Außerdem ist s die Ausgabewortliste, die bis zu diesem Punkt konstruiert wurde, und c die aktuelle Bewertung, die der Phrasenhypothese zugeordnet ist. Die aktuelle Bewertung ist die Summe der auf diesen Punkt in der Bildung der Phrase angewandten Kostenfaktoren.
Der Kostenfaktor für eine Phrase wird durch die lexikalischen Kopfautomaten berechnet. Jede Bewegung des Kopfautomaten trägt um einen Betrag zu dem Kostenfaktor der Phrase bei, der von dem Zustand des Automaten und den Identitäten der beiden Wörter w und w' abhängt. Die Phrase oder Wortkette, die von dem Verfahren ausgewählt wird, ist die mit dem niedrigsten Kostenfaktor, die den vollständigen Wortverband überspannt, d. h. vom Start des Eingangssprachsignals zum Ende dieses Signals.
Der Kostenfaktor zum Ableiten einer den gesamten Verband überspannenden Phrase umfaßt die Kostenfaktoren von Automatenaktionen, die zu der Ableitung führen, zusammen mit zusätzlichen Kostenfaktoren für das Zuordnen von Automaten zu Wörtern und für Zuordnungen zwischen jedem Kopfwort und seinen abhängigen Wörtern. Die zusätzlichen Kostenparameter umfassen Zuordnungsparameter, die den Kostenfaktor für ein Wort wi angeben, das der Kopf des Worts wj ist: wj:C(h(wi wj)), und lexikalische Parameter, die den Kostenfaktor für das Wort w, laufender Automat, zuführen m:C(m,w). Jede Paarung zwischen einem Wort und einem Automaten zusammen mit dem entsprechenden lexikalischen Parameter erscheint als ein Eintrag in ein Lexikon oder Wörterbuch. Es versteht sich, daß mehr als ein Eintrag, d. h. Automat, pro Wort in dem Lexikon vorliegen kann. Der Grund dafür besteht darin, daß ein gegebenes Wort auf mehr als eine Weise verwendet werden kann, wie zum Beipiel als Nomen oder als Verb.
Der Kostenfaktor C(Do,wo) einer Teilphrasenableitung Do mit einem Kopfwort wo ist die Summe des lexikalischen Kostenfaktors für die Auswahl eines Automaten mo, des Kostenfaktors von Automatenaktionen Ao, die von mo bei der Ableitung unternommen werden, der Zuordnungsparameter für das Zuordnen von wo zu seinen abhängigen Wörtern w&sub1;...wm und der Kostenfaktoren von Ableitungen der Teilphrasen, denen diese Abhängigen voranstehen, rekursiv berechnet:
C(Do,wo) = C(mo,wo) + C(Ao, mo) + Σ1≤m≤nC(h(wo,wm)) + C (Dm,wm)
Zur Berechnung des Kostenfaktors einer Phrase können verschiedene Kostenfunktionen verwendet werden. Gewöhnlich basiert die Kostenfunktion auf Wahrscheinlichkeiten, wobei weniger wahrscheinliche Wortassoziationen zu höheren Kostenfaktoren führen. Auf diese Weise gibt der Kostenfaktor Assoziationen mit großer Reichweite zwischen Wörtern in einer Kette wieder. Kostenfunktionen werden später in der vorliegenden Beschreibung ausführlicher beschrieben.
Das Verfahren, durch das die lexikalischen Kopfautomaten den Wortverband analysieren, wird später ausführlicher beschrieben. Bei einer bevorzugten Ausführungsform wird, während Phrasen verlängert werden, ein laufender Kostenfaktor solcher Phrasen berechnet, so daß Phrasen zurückgeschnitten werden können, wenn es offensichtlich wird, daß sie nicht Teil der Phrase mit dem niedrigsten Kostenfaktor sein werden. Vorzugsweise wird für diesen Zweck eine hash- Tabelle verwendet. Die Einträge in der hash-Tabelle umfassen einen Hash-Schlüssel < w,i,j,q,m> und einen hash-Wert, der ein Zeiger auf den Phrasendatensatz ist. Die hash-Tabelle führt einen Zeiger auf den Phrasendatensatz mit dem niedrigsten Kostenfaktor, der zwischen i und j gefunden wird, dem w voransteht, in Zustand q des Automaten m. Die Informationen, aus denen der hash-Schlüssel besteht, werden als "Vollzustand" bezeichnet, und c als der "Vollzustandskostenfaktor".
Das Verfahren zur Analyse des Wortverbands weist vorzugsweise eine Steuerstruktur des Typs "bottom-up" auf, die der für kontextfreie Analysealgorithmen wie zum Beispiel CKY ähnelt, die von Younger beschrieben werden, und verwendet Datenstrukturen, die den Strukturen bei der sogenannten "chart-Analyse" ähneln, die von Early beschrieben wird. Siehe Younger, D., "Recognition and Parsing of Context-Free Languages in Time n³", Information and Control, Band 10, S. 189-208, 1967; Early, J., "An Efficient Context-Free Parsing Algorithm", Co mm. Of the ACM, Band 14, S. 453-460, 1970. Das vorliegende Verfahren wird durch die lexikalischen Kopfautomaten für Wörter in dem Wortverband angesteuert.
Fig. 4 zeigt eine Ausführungsform eines Verfahrens gemäß der vorliegenden Erfindung, durch das die mehreren lexikalischen Kopfautomaten zur Erzeugung mehrerer Phrasendatensätze verwendet werden, aus denen ein bester Phrasensatz, d. h. die beste Wortkette, ausgewählt wird. Somit zeigt Fig. 4 ein Verfahren gemäß der vorliegenden Erfindung zur Erzielung des Schrittes 22 von Fig. 1. Wie im Operationsblock 100 dargestellt, wird der von dem Sprachsignalprozessor SSP erzeugte Wortverband empfangen. Das Verfahren beginnt mit einem Initialisierungsschritt, der durch die Operationsblöcke 105 bis 120 erzielt wird, die zusammen durch die Bezugszahl 130 identifiziert werden. Die Initialisierung findet statt, indem zu einer Warteschlange eine Menge von Phrasendatensätzen < w,[w],i,j,m,q&sub0;,c> hinzugefügt wird, die aus dem Wortverband entwickelt wurde. Ein solcher Phrasendatensatz wird für jedes Element < w,i,j,c&sub0;> in dem Wortverband und jeden Eintrag (m,w) in dem Lexikon hinzugefügt. Somit wird im Operationsblock 105 ein lexikalischer Kopfautomat aktiviert, der einem der Wörter in dem Wortverband entspricht. Genauer gesagt wird ein lexikalischer Kopfautomat, der einem Wort w aus dem Wortverband entspricht, aus einem in einer Speichereinrichtung gespeicherten Lexikon abgerufen. Der dem Wort w entsprechende Lexikoneintrag enthält einen Automaten m und einen Kostenfaktor c&sub1; = C(m,w). Der Automat m enthält eine Startaktion mit einem Kostenfaktor c&sub2; = C(start,qo,m). Der Kostenfaktor c jedes Phrasendatensatzes ist die Summe des lexikalischen Kostenfaktors c&sub1;, des Automatenstartkostenfaktors c&sub2; und des Wortbogenkostenfaktors co, der von der Spracherkennungsvorrichtung 10 zugewiesen wird. Alle lexikalischen Kopfautomaten für jeden Wortbogen in dem Wortverband werden durch die durch die Entscheidungsblöcke 115 und 105 eingerichteten Schleifen aktiviert.
Die übrigen Operations-/Entscheidungsblöcke 140-195 bilden eine Schleife, die Elemente aus der Warteschlange aufbraucht und neue Phrasendatensätze erzeugt. Der Entscheidungsblock 140 fragt ab, ob die Warteschlange leer ist. Wenn die Warteschlange leer ist, wurden alle Phrasendatensätze mit niedrigem Kostenfaktor, die aus dem Eingangswortverband entwickelt werden können, soweit wie möglich verlängert. Der Phrasenverband, d. h. die Ansammlung von Phrasendatensätzen, der von den vorliegenden Verfahren entwickelt wird, wird dann nachverarbeitet, um die beste Wortkette auszubilden, wie im Operationsblock 200 angegeben. Diese Nachverarbeitung wird später ausführlicher beschrieben. Wenn die Warteschlange nicht leer ist, wird die Verarbeitung im Operationsblock 145 fortgesetzt, in dem ein Phrasendatensatz aus der Warteschlange entfernt wird. Bei einer bevorzugten Ausführungsform des vorliegenden Verfahrens wird der Kostenfaktor c des Phrasendatensatzes mit der Phrase mit dem niedrigsten Kostenfaktor, d. h. dem Vollzustandskostenfaktor, in der hash-Tabelle verglichen (Block 150). Wenn der Kostenfaktor c des betrachteten Phrasendatensatzes ("die aktuelle Phrase") nicht kleiner als der Vollzustandskostenfaktor ist, wird die aktuelle Phrase verworfen oder "zurückgeschnitten". Die Verarbeitung kehrt dann zum Block 140 zurück, um zu bestimmen, ob ein weiterer Phrasendatensatz verfügbar ist. Wenn der aktuelle Phrasendatensatz einen geringeren Kostenfaktor als die Phrase mit dem niedrigsten Kostenfaktor in der hash-Tabelle aufweist, wird sie im Operationsblock 155 zu dem Phrasenverband hinzugefügt. Block 150 ist zwar nicht als Schritt in dem vorliegenden Verfahren erforderlich, verbessert aber die Effizienz, da er eine Erzeugung von Phrasendatensätzen, die später verworfen werden, vermeidet.
Wenn nach dem Hinzufügen des Phrasendatensatzes zu dem Phrasenverband im Operationsblock 155 der Phrasendatensatz einer anderen Phrase benachbart ist, dann kann eine Kombinationsaktion stattfinden. Somit fragt der Entscheidungsblock 160 ab, ob es weitere Phrasen gibt oder nicht, mit denen kombiniert werden kann. Wenn nicht, kehrt die Verarbeitung in einer Schleife zum Entscheidungsblock 140 zurück. Wenn weitere Phrasen vorliegen, führt eine Kombinationsoperation, die durch die zusammen durch die Bezugszahl 180 identifizierten Operationsblöcke durchgeführt wird, zu einem neuen Datensatz für eine verlängerte Phrase. Die alten Datensätze verbleiben in dem Verband. Es sind zwei Arten von Kombinationen möglich, Linkskombination und Rechtskombination. Bei einer Linkskombination führt der Automat für den Phrasendatensatz nach rechts wie unten beschrieben eine Linksaktion durch. Wenn der Verband einen ersten Phrasendatensatz < w&sub1;,s&sub1;,i,k,m&sub1;,q&sub1;,c&sub1;> links von einem zweiten Phrasendatensatz < w&sub2;,s&sub2;,k,j,m&sub2;,q&sub2;,c&sub2;> enthält, m² eine Linksaktion mit einem Kostenfaktor c&sub3; = C(left,q'&sub2;,q&sub2;,m&sub2;) enthält und ml eine Stoppaktion mit einem Kostenfaktor c&sub4; = C(stop,q&sub1;,m&sub1;) enthält, dann ergibt die im Operationsblock 165 durchgeführte Kombination die folgende verlängerte Phrase: < w&sub2;,s'&sub2;,i,j,m&sub2;,_,_> , wobei s'&sub2; = concatenate (s&sub1;,s&sub2;). Eine Rechtskombination ist das Spiegelbild einer Linkskombination. Im Operationsblock 170 wird gemäß dem Automatenübergang ein neuer Zustand gesetzt. Bei dem obigen Beispiel ist der neue Zustand q'&sub2;, so daß die verlängerte Phrase folgendermaßen lautet: < w&sub2;,s'&sub2;,i,j,m&sub2;,q'&sub2;,_> . Der Kostenfaktor der neuen Phrase wird im Operationsblock 175 bestimmt. Der neue Kostenfaktor ist die Summe des Automatenübergangskostenfaktors, des Wortassoziationskostenfaktors, des Phrasenaufbrauchkostenfaktors, des aufgebrauchte-Phrase-Kostenfaktors und des aufgebrauchter-Automat-Stop-Kostenfaktors. Bei dem obigen Beispiel wird der neue Kostenfaktor c'&sub2; gegeben durch c'&sub2; = c&sub1; + c&sub2; + c&sub3; + c&sub4; + C(h(w&sub2;,w&sub1;)). Der verlängerte Phrasendatensatz lautet dann: < w&sub2;,s'&sub2;,i,j,m&sub2;,q'&sub2;,c'&sub2;> .
Für jeden aus der Kombinationsoperation 180 entstehenden Phrasendatensatz wird im Block 185 der Kostenfaktor des Datensatzes mit dem Vollzustandskostenfaktor in der Hash-Tabelle verglichen. Wenn der Kostenfaktor des neuen Phrasendatensatzes höher als der Vollzustandskostenfaktor ist, dann kehrt die Verarbeitung zum Operationsblock 160 zurück, ohne den neuen Phrasendatensatz zu der Warteschlange hinzuzufügen, so daß er effektiv verworfen wird. Wenn der Kostenfaktor des neuen Phrasendatensatzes kleiner als der Vollzustandswert ist, dann wird der hash-Tabelleneintrag im Schritt 190 mit dem neuen Datensatzzeiger aktualisiert und der alte Vollzustandsdatensatz wird aus dem Phrasenverband entfernt. Der neue Phrasendatensatz mit niedrigem Kostenfaktor wird dann im Schritt 195 zu der Warteschlange hirnzugefügt und die Verarbeitung wird im Block 160 fortgesetzt.
Nachdem die Warteschlange geleert wurde, wird die Verarbeitung im Operationsblock 200 fortgesetzt, in dem die folgenden Schritte durchgeführt werden, um die Wortkette mit dem niedrigsten Kostenfaktor auszuwählen. Als erstes wird eine Liste aller Verbandsdatensätze < w,s,i,j,q,m,c> aus einem Anfangsknoten i I zu einem Endknoten j J zusammengestellt. Für jeden Datensatz in der Liste addiert man den Kostenfaktor für den Automat m, der im Zustand q anhält, d. h. C(stop,q,m). Darnach wählt man die Kette s aus dem Datensatz mit dem niedrigsten Gesamtkostenfaktor. Wenn es mehrere solcher überspannenden Phrasen mit minimalem Kostenfaktor gibt, dann wird vorzugsweise einer zufällig gewählt.
Bezüglich Kostenparametern erfordern die vorliegenden Verfahren keine spezifische Interpretation der verschiedenen Kostenparameter für Automatenaktionen und lexikalische und Assoziationskosten, außer der allgemeinen Anforderung, daß niedrigere Kostenfaktoren erwünschteren Ketten entsprechen. Es gibt Fachleuten bekannte Verfahren zur Bereitstellung spezifischer Kostenfunktionen, die auf die vorliegenden Verfahren anwendbar sind. Vorzugsweise ist die Kostenfunktion negierte log-likelihood. Ein Verfahren zur Ableitung von log-likelihood-Kosten für die Verfahren der vorliegenden Erfindung wird nachfolgend beschrieben. Die Automatenaktionen, lexikalischen Auswahlen und Zuordnungsauswahlen werden als Ereignisse in einem generativen Modell, spezifisch einem probabilistischen Modell zur Erzeugung von Wortketten, genommen. Aus gesammelten Daten für die konkrete Spracherkennungsanwendung wird eine Menge von Eingangssprachäußerungssignalen transkribiert.
Das in Fig. 4 dargestellte Verfahren zur Erzeugung von Phrasendatensätzen wird über die von der Sprachsignalverarbeitung erzeugten Wortverbände ausgeführt, wobei ein Zählwert von Automatenaktionen, lexikalischen Automatenauswahlen und Wortassoziationsauswahlen, die zu den transkribierten Ketten für jedes Sprachäußerungssignal führen, geführt wird. Als nächstes werden aus diesen Zählwerten mit standardmäßigen statistischen Verfahren Wahrscheinlichkeiten abgeschätzt. Für jede abgeschätzte Wahrscheinlichkeit P(e) für ein Ereignis e setzt man den Kostenfaktor für e auf -log(P(e)).
Es versteht sich, daß auch andere Fachleuten bekannte Verfahren zur Abschätzung von Wahrscheinlichkeiten verwendet werden können, wie zum Beispiel Maximierung des Erwartungswerts. Außerdem können andere Kostenfunktionen als log-likelihood verwendet werden, wie zum Beispiel ohne Einschränkung das likelihood-Verhältnis. Das likelihood-Verhältnis ist das Verhältnis der Anzahl, wie oft eine bestimmte Automatenaktion oder -auswahl beim Training zu der falschen Kette führte und der Anzahl, wie oft sie zu der Auswahl der transkribierten Kette führte.

Beispiele

Fig. 5 zeigt eine beispielhafte Teilphrasenableitung, die von den vorliegenden Verfahren und Vorrichtungen für die Kette "Please show me the cheapest flights from Boston to Newark" erzeugt wurde. Fig. 6 zeigt beispielhafte lexikalische Kopfautomaten, die den Wörtern in diesem Satz zugeordnet sind. Die tatsächlichen Übergänge, die zur Erkennung der Kette erforderlich sind, sind in Fig. 6 als durchgezogene Linien gezeigt. Einige wenige der vielen anderen möglichen Übergänge, die bei dieser konkreten Ableitung nicht genommen wurden, sind als gestrichelte Linien gezeigt. Die Notation "-> " zeigt einen Rechtsübergang und die Notation "< -" einen Linksübergang an. Die Wörter, unter denen die Automaten in dem Lexikon erscheinen würden, sind neben den Startzuständen gezeigt, d. h. q1, q4, q7 usw.
Die Übergänge, die die lexikalischen Kopfautomaten bei der Erkennung der Kette "Please show me the cheapest flights from Boston to Newark" genommen werden, die in Fig. 6 gezeigt sind, werden nachfolgend beschrieben. Es werden Startaktionen für alle Wörter in der Kette genommen: "please" bei q9, "show" bei q1, "me" bei q8, "the" bei q7, "cheapest" bei q16, "from" bei q10, "Boston" bei q14, "to" bei q12 und "Newark" bei q15. Die Wörter für die folgenden Automaten nehmen Stoppaktionen, da für diese keine Übergänge möglich sind: "please", "me", "the", "cheapest", "Boston" und "Newark". Der Automat für das Wort "from" nimmt einen Rechtsübergang von q10 nach q11, wobei der Automat für das Wort "Boston" aufgebraucht wird, und stoppt, wobei eine vollständige Phrase "from Boston" gebildet wird. Der Automat für das Wort "to" nimmt einen Rechtsübergang von q12 nach q13, wobei der Automat für das Wort "Newark" aufgebraucht wird, und stoppt, wodurch eine vollständige Phrase "to Boston" gebildet wird. Dadurch wird die niedrigste Ebene der in Fig. 5 gezeigten Teilphrasenableitung abgeschlossen.
Der Automat für das Wort "flights" nimmt einen Linksübergang von q4 nach q5, wobei der Automat für das Wort "cheapest" aufgebraucht wird, einen Rechtsübergang von q5 zurück nach q5, wobei die Phrase "from Boston" aufgebraucht wird, und einen weiteren Rechtsübergang von q5 zurück nach q5, wobei die Phrase "to Newark" aufgebraucht wird, einen Linksübergang von q5 nach q6, wobei der Automat für das Wort "the" aufgebraucht wird und hält an. Dadurch wird die Erkennung der Phrase "the cheapest flights from Boston to Newark" entsprechend den beiden niedrigsten Ebenen der in Fig. 5 gezeigten Teilphrasenableitung abgeschlossen.
Der Automat für das Wort "show" nimmt einen Linksübergang von q1 zurück nach q1, wodurch der Automat für das Wort "please" aufgebraucht wird, einen Rechtsübergang von q1 nach q2, wobei der Automat für das Wort "me" aufgebraucht wird, einen Rechtsübergang von q2 nach q3, wobei die Phrase, die mit "flights" anfängt, aufgebraucht wird, d. h. "the cheapest flights from Boston to Newark", und hält an. Dadurch wird die gesamte in Fig. 5 gezeigte Ableitung und die Erkennung von "Please show me the cheapest flights from Boston to Newark" abgeschlossen.
Es versteht sich, daß die hier beschriebenen Ausführungsformen lediglich die Prinzipien der vorliegenden Erfindung veranschaulichen, und daß verschiedene Modifikationen auftreten können und von Fachleuten implementiert werden können, ohne vom Schutzumfang der vorliegenden Erfindung abzuweichen. Obwohl die hier beschriebenen Ausführungsformen die Spracherkennung betreffen, können die vorliegenden Verfahren zum Beispiel auch in anderen Arten von Sprachenerkennungssystemen eingesetzt werden.

Claims

1. Verfahren zur Sprachenerkennung, bei dem ein die zu erkennende Sprache anzeigendes Signal erzeugt wird, mit den folgenden Schritten:

Erzeugen von Kandidaten-Wortketten für das Signal;

Auswählen unter den Kandidaten durch Verwendung eines Sprachenmodells unter Verwendung mehrerer Automaten, wobei jeder Automat ein Paar von Sequenzen erkennen kann, wobei eine Sequenz nach links und die andere nach rechts abgetastet wird und jeder Automat einem Wort in einem Vokabular des Sprachenmodells entspricht.

2. Verfahren nach Anspruch 1, wobei bei dem Schritt des Auswählens weiterhin nur solche Automaten verwendet werden, die den in den Kandidaten- Wortketten enthaltenen Wörtern entsprechen.

3. Verfahren nach Anspruch 1, wobei der Schritt des Erzeugens von Kandidaten-Wortketten weiterhin das Erzeugen solcher Wortketten in Form eines Wortverbands umfaßt.

4. Verfahren nach Anspruch 1, wobei der Schritt des Auswählens weiterhin die Verwendung der Automaten zum Ableiten von Phrasen aus den in den Kandidaten-Wortketten enthaltenen Wörtern und das Berechnen eines Kostenfaktors für die abgeleiteten Phrasen umfaßt, wobei der Kostenfaktor mit dem Grad der Entsprechung zwischen der abgeleiteten Phrase und der durch das Signal dargestellten Sprache zusammenhängt.

5. Verfahren nach Anspruch 4, wobei ein niedrigerer Kostenfaktor einen höheren Grad der Entsprechung anzeigt.

6. Verfahren nach Anspruch 5, wobei der Schritt des Auswählens weiterhin das Bestimmen der Phrase mit dem niedrigsten Kostenfaktor umfaßt.

7. Verfahren nach Anspruch 4, wobei der Kostenfaktor einer Phrase auf Wahrscheinlichkeiten basiert, wobei weniger wahrscheinliche Wortzuordnungen zu einem höheren Kostenfaktor führen.

8. Verfahren nach Anspruch 4, wobei Kosten inkrementell während des Ableitens von Phrasen angewandt werden.

9. Verfahren nach Anspruch 1, wobei die zu erkennende Sprache gesprochen wird und der Schritt des Erzeugens von Kandidaten-Wortketten weiterhin das Anwenden eines akustischen Modells umfaßt.

10. Computerlesbares Speichermedium mit codierten computerlesbaren Programmbefehlen zur Verwendung in Verbindung mit einem programmierbaren Computer, wobei die Befehle bewirken, daß der Computer aus mehreren Sprachenkettenhypothesen eine Sprachenkette auswählt, wobei die gewählte Kette die beste Entsprechung mit einem Sprache darstellenden Signal liefert, wobei diese Auswahl aus der Handlung mehrerer Automaten resultiert, die ein Paar von Sequenzen erkennen können, wobei eine Sequenz nach links und die andere nach rechts durch eine auf den mehreren Sprachenkettenhypothesen basierende Datenstruktur hindurch abgetastet wird.

11. Computerlesbares Speichermedium nach Anspruch 10, wobei die Datenstruktur ein Phrasenverband ist, der aus durch die mehreren Automaten gebildeten Phrasen besteht.

12. Computerlesbares Speichermedium nach Anspruch 10, wobei der programmierbare Computer ein Spracherkennungssystem ist, die Sprachenkettenhypothesen in Form eines Wortverbands vorgelegt werden und wobei die handelnden Automaten den Wörtern in dem Wortverband ent sprechen.

13. Verfahren zum Auswählen einer Wortkette aus mehreren Wortkettenhypothesen, wobei die Wortkettenhypothesen aus einem Eingangssignal abgeleitet werden, das Sprache darstellt, und die gewählte Wortkette die Sprache am besten darstellt, mit den folgenden Schritten:

(a) Aktivieren von Automaten, die den Wörtern in den Wortkettenhypothesen entsprechen, wobei die aktivierten Automaten aus mehreren solchen Automaten ausgewählt werden, die ein Lexikon definieren, wobei jeder der aktivierten Automaten ein Paar von. Sequenzen erkennen kann, wobei eine Sequenz nach links und die andere nach rechts abgetastet wird, und wobei weiterhin jeder Automat einen Anfangszustand umfaßt;

(b) Erzeugen einer ersten Vielzahl von Phrasendatensätzen, wobei für jedes Wort in den Wortkettenhypothesen ein Phrasendatensatz erzeugt wird und jeder Phrasendatensatz durch ein Wort, einen Automaten, den Anfangszustand und einen Kostenfaktor gekennzeichnet ist;

(c) Erzeugen eines Phrasenverbands durch Bilden einer Datenstruktur, die die Phrasendatensätze aus Schritt (b) umfaßt;

(d) Erzeugen mehrerer erweiterter Phrasendatensätze, wobei ein erweiterter Phrasendatensatz gebildet wird, wenn ein Phrasendatensatz in dem Phrasenverband einen benachbarten Phrasendatensatz in dem Phrasenverband durch einen Automatenübergang aufbraucht, wobei der erweiterte Phrasendatensatz

die Wörter sowohl des Phrasendatensatzes als auch des benachbarten Phrasendatensatzes enthält und den Automaten des aufbrauchenden Phrasendatensatzes umfaßt,

wobei ein neuer Zustand dem Übergang des Automaten und

einem neuen Kostenfaktor entspricht, wobei

der neue Kostenfaktor die Summe der Kostenfaktoren der aufgebrauchten Phrase und der aufbrauchenden Phrase ist, wobei ein Kostenfaktor dem Automatenübergang der aufbrauchenden Phrase zugeordnet ist und ein Kostenfaktor einem durch den aufgebrauchten Automaten unternommenem Stopp zugeordnet ist und ein Kostenfaktor eine Zuordnung zwischen den Wörtern in dem aufgebrauchten und dem aufbrauchenden Phrasendatensatz betrifft;

(e) Hinzufügen des erweiterten Phrasendatensatzes zu dem Phrasenverband, wenn der neue Kostenfaktor des erweiterten Phrasendatensatzes niedriger als ein Bezugs-Phrasendatensatz-Kostenfaktor ist;

(f) Wiederholen der Schritte (d) und (e) wobei ein Phrasendatensatz einen benachbarten Phrasendatensatz solange aufbrauchen kann, bis alle Phrasendatensätze völlig erweitert worden sind, und wobei der Bezugs-Phrasendatensatz-Kostenfaktor mit den zu dem Phrasenverband hinzugefügten erweiterten Phrasendatensätzen aktualisiert wird; und

(g) Wählen des Phrasendatensatzes mit dem niedrigsten Kostenfaktor, der das gesamte Eingangssignal überspannt.