DE60025687T2

DE60025687T2 - Vorrichtung zum Spracherkennung mit Durchführung einer syntaktischen Permutationsregel

Info

Publication number: DE60025687T2
Application number: DE60025687T
Authority: DE
Inventors: Thomson Multimedia Frωdωric Soufflet; Thomson Multimedia Christophe Delaunay
Original assignee: Thomson Multimedia SA
Current assignee: Vantiva SA
Priority date: 1999-11-30
Filing date: 2000-11-14
Publication date: 2006-07-27
Anticipated expiration: 2020-11-15
Also published as: DE60025687D1; CN1159701C; CN1298171A; FR2801716A1; US20010002465A1; JP2001188560A; ES2254118T3; EP1111587B1; FR2801716B1; JP4689032B2; EP1111587A1

Description

Informationssysteme oder Steuersysteme haben eine ständig zunehmende Benutzung einer Sprachschnittstelle, um eine Zusammenarbeit mit dem Benutzer schnell und intuitiv zu gestalten. Da diese Systeme immer komplexer werden, werden die benutzten Dialogstile immer reicher, und man gelangt in das Gebiet eines sehr großen Vokabulars einer kontinuierlichen Spracherkennung.
Es ist bekannt, dass der Aufbau eines großen vokabularen kontinuierlichen Spracherkennungssytems die Herstellung eines Sprachmodells erfordert, das die Wahrscheinlichkeit definiert, dass auf ein bestimmtes Wort aus dem Vokabular der Anwendung ein anderes Wort oder Gruppe von Wörtern in der chronologischen Reihenfolge des Satzes folgt.
Dieses Sprachmodell muss den Gesprächsstil, der im Allgemeinen durch einen Benutzer des Systems angewendet wird, wiedergeben.
Die Qualität des benutzten Sprachmodells beeinflusst stark die Zuverlässigkeit der Spracherkennung. Diese Qualität wird meistens durch einen Index gemessen, der die Verwirrung des Sprachmodells und schematisch die Zahl der Wahlmöglichkeiten darstellt, die das System für jedes decodierte Wort vornehmen muss. Je geringer diese Verwirrung oder Perplexität ist, umso besser ist die Qualität.
Das Sprachmodell wird zur Umsetzung des Sprachsignals in eine Textreihe von Wörtern benötigt, ein Schritt, der häufig durch Dialogsysteme benutzt wird. Es ist dann notwendig, eine Verständnislogik zu erzeugen, die es möglich macht, die Frage zu verstehen, um so auf sie zu antworten.
Es gibt zwei Standardverfahren zur Erzeugung von großen Vokabular-Sprachmodellen.

(1) Das so genannte N-gram statistische Verfahren, das meistens ein Bigram oder Trigram verwendet, besteht in der Annahme, dass die Wahrscheinlichkeit des Auftretens eines Worts in dem Satz nur abhängig von den N Wörtern ist, die ihm vorangehen, unabhängig von seinem Kontext in dem Satz. Wenn man das Beispiel des Trigrams für ein Vokabular von 1000 Wörtern nimmt, wäre es notwendig, 1000³ Möglichkeiten zu definieren, um das Sprachmodell zu definieren, was ziemlich unpraktikabel ist. Zur Lösung dieses Problems werden die Wörter in Sätze gruppiert, die entweder explizit durch den Modelldesigner definiert oder durch selbst-organisierende Verfahren abgeleitet werden. Dieses Sprachmodell wird automatisch aus einem Textkörper gebildet.
(2) Das zweite Verfahren besteht in der Beschreibung der Syntax durch Mittel einer Wahrscheinlichkeits-Grammatik, im Allgemeinen eine kontextfreie Grammatik, definiert durch einen Satz von Regeln, die in der so genannten Backus-Naur-Form oder BNF-Form geschrieben werden.

Die die Grammatiken beschreibenden Regeln sind meistens handgeschrieben, können jedoch ebenfalls automatisch abgeleitet werden. In dieser Beziehung wird verwiesen auf die folgenden Dokumente:
"Basic methods of probabilistic context-fee grammars" von F. Jelinek, J. D. Lafferty und R. L Mercer, NATO ASI Series, Band 75, Seiten 345–359, 1992.
Die oben beschriebenen Modelle ergeben spezielle Probleme, wenn sie auf Schnittstellen von natürlichen Sprachsystemen angewendet werden:
Die N-gram Typ Sprachmodelle (1) modulieren nicht richtig die Abhängigkeiten zwischen mehreren grammatikalischen Unterstrukturen in dem Satz. Für einen syntaktisch richtig ausgesprochenen Satz gibt es nichts zu garantieren, dass diese Unterstrukturen in dem Laufe der Erkennung eingehalten werden, und es ist daher schwierig, zu ermitteln, ob ein derartiger Sinn, der gewöhnlicherweise durch einen oder mehrere spezifische syntaktische Strukturen entsteht, durch den Satz befördert wird.
Diese Modelle sind geeignet für ein kontinuierliches Diktat, jedoch leidet ihre Anwendung in Dialogsystemen häufig an den genannten Mängeln.
Die auf den Grammatiken (2) basierenden Modelle machen es möglich, die entfernten Abhängigkeiten in einem Satz richtig zu modellieren und ebenso mit synthetischen Unterstrukturen zu arbeiten. Die Verwirrtheit oder Perplexität der erhaltenen Sprache ist häufig für eine bestimmte Anwendung geringer als die Modelle vom Typ N-gram.
Andererseits ergeben für hochflektierende Sprachen, wie Französisch oder Italienisch, in denen die Lage der syntaktischen Gruppen in dem Satz ziemlich frei ist, die Grammatiken vom BNF-Typ Probleme in der Definition der Permutationen der in Frage stehenden syntaktischen Gruppen.
Für weniger flektierende Sprachen, wie Englisch, sind diese Permutationen ebenfalls notwendig für die Beschreibung der Verzögerungen und den falschen Beginn einer ordnungsgemäß gesprochenen Sprache und machen das auf BNFs-basierende Sprachmodell ziemlich unpassend.
Das Dokument US 5 937 385 zeigt ein automatisches System, das für die Spracherkennung syntaktische Grammatiken erzeugt. Die Erzeugung enthält zwei Zeiten. In einer ersten Zeit wird die Grammatik eingeführt und ausgeführt zur Erzeugung aller möglichen Sätze. Zu einer zweiten Zeit überprüft ein Operator jeden Satz für die Klassifizierung in zwei Gruppen: die verständlichen Sätze und die unverständlichen Sätze. Das System lässt alle unverständlichen Sätze aus und ändert die Grammatik zum Erhalt nur der verständlichen Sätze. Daher werden alle Permutationen entfaltet. Dieses System ist real nicht geeignet für die Verarbeitung von Verzögerungen und die falschen Anfänge einer ordnungsgemäß gesprochenen Sprache.
Das Dokument VILLADSEN "Combinatory categorial grammar for intensional fragment of natural language" zeigt einen Prozessor einer natürlichen Sprache auf der Grundlage einer kategorischen Grammatik, die einen Satz in eine logische Formel übersetzt. Die benutzten Operatoren ermöglichen die Interpretation eines als richtig angenommenen Satzes, somit entsprechend den erschöpfenden Regeln. Dieser Prozessor ist für die Verarbeitung von oralen Sätzen, die Zögerungen oder Pausen enthalten, nicht geeignet.
Das Dokument JUNQUA, ( US 5 799 065 ) zeigt ein Telefongerät mit einem Spracherkennungssystem. Das Gerät ist in der Lage, einen Namen in einer Liste von Namen zu erkennen, die in seinem Speicher aufgezeichnet sind, und diesem Namen einer Telefonnummer zuzuordnen. Junqua benutzt keine syntaxiale Grammatik, sondern eine stochastische oder zufällige Grammatik. Dieses System ist sehr geeignet für die Spracherkennung einer begrenzten Zahl von Wörtern, wie in einem Telefonverzeichnis, jedoch nicht für die Verarbeitung von oralen Sätzen mit Zögerungen und falschen Anfängen.
Der Gegenstand der Erfindung, wie sie im Anspruch 1 beansprucht wird, ist ein Spracherkennungsgerät mit einem Audioprozessor für die Erfassung eines Audiosignals und einem Linguistik-Decoder zur Ermittlung einer Folge von dem Audiosignal entsprechenden Wörtern.
Das durch die Erfinder vorgeschlagene Sprachmodell erstreckt den Formalismus von BNF-Grammatiken, um so die syntaktischen Permutationen einer normalen Sprache und von hochflexierenden Sprachen zu übertragen. Sie macht es möglich, die für die Spracherkennungsverarbeitung benötigten Speicher zu verringern, und ist insbesondere geeignet für die Anwendung in Massenartikeln.
Gemäß einer bevorzugten Ausführungsform enthält die syntaktische Regel für die Permutierung der Symbole eine Liste von Symbolen und als geeignete Ausdrücke von Bemühungen auf der Reihenfolge der Symbole.
Gemäß einer bevorzugten Ausführungsform enthält der Linguistik-Decoder ein Erkennungsgerät, das bei der Zuordnung von Symbolen einer Permutation zu einer Reihe von Ausdrücken eines Satzes ein Symbol für die Zuordnung zu einem bestimmten Ausdruck nur unter den Symbolen der Permutation wählt, die nicht vorher zugeordnet worden sind.
Gemäß einer besonderen Ausführungsform implementiert das Erkennungsgerät einen Algorithmus von dem Typ "beam search" oder "n-best".
Andere Algorithmen können ebenfalls ausgeführt werden.
Weitere Merkmale und Vorteile der Erfindung ergeben sich aus der Beschreibung einer besonderen, nicht-einschränkenden Ausführungsform, die anhand der beigefügten Zeichnung erläutert wird. In der Zeichnung:
1 ist ein Diagramm eines Spracherkennungssystems,
2 ist ein Diagramm einer bekannten Stapel-basierenden Automation,
3 ist ein Diagramm einer Stapel-basierenden Automation gemäß der Erfindung,
4 ist ein Schema zur Erläuterung der alternativen Symbole beim Start der Analyse einer beispielhaften Permutation gemäß der Erfindung,
5 ist ein Schema zur Erläuterung der alternativen Symbole des Beispiels von 4 bei einem späteren Schritt gemäß der Erfindung,
6 ist ein Schema zur Erläuterung der alternativen Symbole in dem Fall des Ausdrucks einer Permutation mittels Regeln nach dem Stand der Technik,
7a ist ein Baum zur Erläuterung des Satzes von Alternativen bei den Knotenpunkten, resultierend aus der beispielhaften Permutation, gemäß der Erfindung, und
7b ist ein Baum zur Erläuterung des Satzes von Alternativen an den Knotenpunkten, resultierend aus der beispielhaften Permutation gemäß dem Stand der Technik.
1 ist ein Blockschaltbild eines beispielhaften Geräts 1 für eine Spracherkennung. Dieses Gerät enthält einen Prozessor 2 des Audiosignals, der die Digitalisierung eines Audiosignals, das von einem Mikrophon 3 stammt, mittels einer Signal-Erfassungsschaltung 4 durchführt. Der Prozessor setzt außerdem die digitalen Abtastwerte in akustische Symbole um, die aus einem vorbestimmten Alphabet ausgewählt sind. Zu diesem Zweck enthält er einen akustisch/phonetischen Decoder 5. Ein Linguistik-Decoder 6 verarbeitet diese Symbole, um so für eine Folge A von Symbolen die wahrscheinlichste Folge W von Wörtern, die die Folge A ergeben, zu ermitteln.
Der Linguistik-Decoder benutzt ein akustisches Modell 7 und ein Sprachmodell 8, die durch einen auf Hypothese beruhenden Suchalgorithmus 9 durchgeführt werden. Das akustische Modell ist z.B. ein sogenanntes " hidden Markov"-Modell (oder HMM). Das in der vorliegenden beispielhaften Ausführungsform durchgeführte Sprachmodell basiert auf einer Grammatik, die mittels Syntaxregeln von der Backus-Naur-Form beschrieben wird. Das Sprachmodell dient zur Aufstellung von Hypothesen für den Suchalgorithmus. Der letztere, der das richtige Erkennungsgerät ist, ist bezüglich des vorliegenden Beispiels ein Suchalgorithmus auf der Basis eines Algorithmus vom Typ Viterbi und bezeichnet als der "n-best". Der Algorithmus vom Typ "n-best" ermittelt bei jedem Schritt der Analyse eines Satzes die n höchstwahrscheinlichen Folgen von Wörtern. Am Ende des Satzes wird die wahrscheinlichste Lösung unter den n Kandidaten ausgewählt.
Die Konzepte in dem obigen Absatz sind für sich dem Fachmann auf diesem Gebiet bekannt, jedoch werden Informationen, die sich insbesondere auf den Algorithmus "n-best" beziehen, in der folgenden Arbeit angegeben:
"Statistical methods for speech recognition" von F. Jelinik, MIT Press 1999, ISBN 0-262-10066-5, Seiten 79–84. Es können auch andere Algorithmen ausgeführt werden, insbesondere andere Algorithmen vom Typ "beam search", von denen der Algorithmus "n-best" ein Beispiel ist.
Der akustische/phonetische Decoder und der Linguistik-Decoder können durch eine geeignete Software ausgeführt werden, die durch einen Mikroprozessor ausgeführt wird, der Zugriff hat zu einem Speicher, der den Algorithmus des Erkennungsgeräts und die Akustik- und Sprachmodelle enthält.
Die Erfindung betrifft außerdem das Sprachmodell sowie seine Benutzung durch das Erkennungsgerät.
Die folgenden vier syntaktischen Regeln werden im Allgemeinen benutzt, um eine Sprachmodell-Wahrscheinlichkeitsgrammatik zu definieren.
Diese vier Regeln sind:
(a) "Or" symbol
<symbol A> = <symbol B> | <symbol C>
(b) "And" symbol (concatenation)
<symbol A> = <symbol B> <symbol C
(c) Optional element
<symbol A> = <symbol B>? (optional index)
(d) Lexical assignment <symbol A> = "lexical word"
Es sollte bemerkt werden, dass nur die Regeln (a), (b) und (d) tatsächlich obligatorisch sind. Regel (c) kann mittels des anderen Baums reproduziert werden, wenngleich zu Lasten der Kompaktheit des Sprachmodells.
Das Sprachmodell gemäß der vorliegenden beispielhaften Ausführungsform benutzt eine zusätzliche syntaktische Regel zur Definition der Wahrscheinlichkeitsgrammatik des Sprachmodells:
(e) "Permutation" symbol
<symbol A> = Permut. {<symbol A1 >, <symbol A2>, ..., <symbol An>}
(<symbol Ai> > <symbol Aj>
, ...,
<symbol Ak> > <symbol Aj>)
Das bedeutet, dass das Symbol A ein beliebiges der wiederholungslosen Permutation der n Symbole A1, ..., An ist. Diese Symbole werden durch die "And"-Regel für jede Permutation zugefügt.
Außerdem werden gemäß der vorliegenden beispielhaften Ausführungsform nur die Permutationen, die die Anforderungen erfüllen, die zwischen den Klammern ausgedrückt sind und die sich folgendermaßen lesen: "das Symbol Ai erscheint in der Permutation vor dem Symbol Aj, das Symbol Ak erscheint vor dem Symbol A1", sind syntaktisch gültig.
Der optionale Index in der Definition der Regel (c) arbeitet folgendermaßen:
Ein optionaler Index ist ein Paar, gebildet aus einer ganzen Zahl und einem Boolean, der richtig oder falsch sein kann. Wenn eine Neuschreibregel vom Typ:
<symbol A> = <symbol B>? (optional index)
angetroffen wird, dann ist:

• Wenn dieselbe ganze Zahl wie die des vorliegenden optionalen Index in den optionalen Indices der anderen Regeln niemals angetroffen wird, die in dem laufenden Zustand in der Grammatik des Sprachmodells erzeugt wurden, für die derzeit unter Nachforschung stehende Hypothese, dann kann das Symbol A sein:
• es kann ausgelagert (swapped) sein für das Symbol B und den optionalen aktivierten Index,
• es kann ausgelagert (swapped) sein in die leere Regel und den nicht aktivierten optionalen Index.
• Wenn derselbe Index durch Anwendung einer Regel von demselben Typ gemäß dem oben beschriebenen Protokoll aktiviert wurde, dann ist der einzige gültige Ausdruck der Regel:
• Austausch des Symbols A für das Symbol B, wenn der Boolean-Index wahr ist,
• Austausch des Symbols A für das leere Symbol, wenn der Boolean-Index falsch ist.

Die Permutationen könnten ausgedrückt werden in einer Sprache vom Typ mit einem Kontext-unabhängigen BNF, durch einfaches Erstrecken des syntaktischen Baums, ausgedrückt durch die fünfte Regel, wobei diese Erweiterung nur durch Anwendung der ersten vier erfolgt. Aus kombinatorischen Gründen hat der gebildete syntaktische Baum eine große Abmessung, sobald die Zahl der permutierten Symbole zunimmt.
Der Vorgang der Permutationen erfolgt durch ein Stapel-basiertes Automaten, d.h. einer, der von dem Kontext abhängig ist und der markiert, ob im Laufe der syntaktischen Suche ein Auftreten der Gruppe, die an der Permutation teilnimmt, bereits richtig im Bezug auf die Anforderungen der Reihenfolge angetroffen ist.
Die übliche oder Standard-Verarbeitung einer BNF-Grammatik wird durch die in 2 dargestellten Objekte erreicht.
Die beispielhafte Ausführungsform beruht andererseits auf einem Stapel-basierten Automaten, der die in 3 dargestellten neuen Objekte benutzt.
Zur Beschreibung der Ausführung der Syntaxregel (e) nehmen wir das Beispiel eines einfachen Satzes, zusammengesetzt aus einer einzigen Permutation von drei syntaktischen Ausdrücken ohne Anforderungen:
<Sentence> = Permut{<A>, , <C>}
Die Ausdrücke A, B und C können selbst komplexe Ausdrücke sein, definiert in einem oder mehreren Permutationssymbolen und/oder anderen Symbolen.
Ein Spracherkennungssystem, basierend auf der Grundlage der konventionellen Prinzipien der Beschreibung von Grammatiken, d.h. unter Anwendung der einfachen BNF-Syntax, setzt diese Form eines Satzes in der folgenden Weise um:
<Sentence>=
<A><C>|
<A><C>|
<A><C>|
<C><A>|
<C><A>|
<C><A>.
Es gibt 3! Kombinationen, die durch das "or"-Symbol (|) verbunden sind. Der syntaktische Baum ist vollständig entfaltet, und die Informationen, dass dieser Baum tatsächlich die Darstellung einer Permutation ist, geht verloren. Der beschriebene Baum wird vollständig in einem Speicher gespeichert, um das für die Spracherkennung benötigte Sprachmodell darzustellen.
Dieser Aufbau dient zum Vorschlagen von Hilfsausdrücken, die im Laufe des "n-best search"-Algorithmus des Erkennungsgeräts analysiert werden, wobei diese Ausdrücke verknüpft werden zur Bildung von Syntax-verträglichen Sätzen, von denen das Gerät die n besten zurückbehält, d.h. diejenigen, die die höchste Wahrscheinlichkeit haben, wenn das Tonsignal aufgezeichnet wird.
Der "n-best search"-Algorithmus ist gekoppelt mit einer Strategie für das "Ausästen" (pruning) der Zweige des syntaktischen Baums, der im Verlauf der links-zu-rechts-Analyse des Satzes nur die n besten Hilfssegmente bis zu dem laufenden Analysepunkt behält.
Es ist ersichtlich, dass dann, wenn der in Frage kommende Satz untersucht wird beim Beginn der Analyse sechs Alternativen, dem Gerät zur akustischen Decodierung dargeboten werden, einer für jede der Kombinationen der drei Ausdrücke <A>, und <C>. Die Tatsache, dass es möglich ist, zwischen den links-zu-rechts drei Untergruppen der beiden Kombinationen zu unterscheiden (wobei einer mit dem Symbol <A> beginnt, der zweite mit dem Symbol und der letzte mit dem Symbol <C>), verlorengegangen ist und das Gerät eine Analyse jeder der sechs Strukturen in einer nicht differenzierten Weise. Wenn sich ergibt, dass die syntaktischen Strukturen <A>, und <C> ausreichend komplex sind für das "Pruning" im Laufe der Analyse der drei Strukturen, dann werden die n besten analysierten Segmente aus Paaren von Strukturen zusammengesetzt, die vollständig identisch sind und somit werden nur n-best/2 Alternativen in Erwägung gezogen.
Die neue, durch die Erfindung vorgeschlagene Verarbeitung leidet nicht an dieser Verringerung in dem Untersuchungsraum: die Informationen, dass eine Permutation in der Grammatik existiert, wird explizit angezeigt, und die Permutation wird so wie sie ist verarbeitet.
Im Folgenden wird das Verhalten des Erkennungsgeräts zunächst im Detail beschrieben, in dem Fall der Ausführung der Regel (e) für die Beschreibung einer Permutation. Dann konzentrieren wir uns auf die Beschreibung des Verhaltens des Erkennungsgeräts in dem Fall, wo die Permutationen durch die Regeln (a) bis (d) ausgedrückt werden. Die oben genannten, durch die Erfindung erzielten Vorteile ergeben sich aus dem Vergleich der beiden Verhaltensweisen.
4 und 5 sind Diagramme zur Erläuterung des Verhaltens des Erkennungsgeräts, wenn es mit einer Permutation gemäß der Erfindung dargestellt ist.
Beim Beginn der Analyse der Permutation, dem in 3 dargestellten Schritt, ergeben sich drei Möglichkeiten für das Erkennungsgerät für die Wahl des ersten Ausdrucks des Satzes: Das Symbol <A>, das Symbol und das Symbol <C>.
Eine "n-best"-Analyse mit dem "Pruning" wird auf diese Strukturen angewendet. Das Gerät betrachtet zunächst das Symbol <A>. Der Weg (patch), der der Route <A> folgt, wird in der linken/rechten Analyse folgendermaßen ausgehandelt:
Da es der Weg des Startens mit <A> ist, der analysiert wird, erhält ein logisches Symbol in dem Speicher diese Informationen durch Setzen einer Variablen für die in Frage stehende Permutation und zu der derzeit ausgehandelten Alternativen aufrecht. Diese durch das Gerät verwaltete Variable bewirkt, dass dieses Symbol <A> für den Rest der Analyse des vorliegenden Wegs nicht länger aktiv ist, d.h. er wird nicht länger als ein Hilfssymbol für einen Ausdruck sein, der auf demselben Weg weiter entfernt liegt.
Im Einzelnen ist die Situation beim Start der Analyse diejenige, die in 4 dargestellt ist: die drei Symbole <A>, , <C> sind aktiv und Kandidaten für den n-best-Erkennungsalgorithmus.
Im Laufe der Suche wird jede der Alternativen untersucht. Z.B. wird zunächst das Symbol <A> dargestellt. Im Laufe dieser Untersuchung wird es notwendig sein, die möglichen Symbolreihen, beginnend mit <A>, zu untersuchen: vom Standpunkt der Analyse des zweiten Ausdrucks des Satzes ergibt sich die in 5 dargestellte Situation: das Symbol <A> ist für die Analyse des Restes des Satzes für die derzeit untersuchte Alternative nicht mehr verfügbar, da sie vorher in der linken/rechten Analyse des Aufgezeichneten Signalflusses benutzt wurde.
Somit verbleiben zwei Hilfssymbole, und <C>. In analoger Weise markiert die Suchroute, die z.B. analysiert, dieses Symbol als inaktiv, und nur das Symbol <C> bleibt für den Rest der Decodierung verfügbar.
Anders ausgedrückt, verarbeitet das Erkennungsgerät gemäß der Erfindung eine Permutation, wie definiert durch die Regel (e), in der in 7a erläuterten Weise. Es wird erwogen, dass das Gerät den Ausdruck vom Rang i des zu analysierenden Satzes beachtet. Das Gerät ermittelt den Satz der möglichen alternativen Symbole: In dem Fall der beispielhaften Permutation mit drei Symbolen gibt es drei mögliche Alternativen beim Wert i: <A>, , <C>. Beim Rang i + 1 gibt es nunmehr nur zwei Alternativen, das vorangehende, beim Rang i gewählte Symbol wird durch das Gerät nicht weiter beachtet. Beim Rang i + 2 ist keine Wahl mehr möglich.
Aus dem Gesichtspunkt der Beachtung der n besten Wege erscheint es, dass die Verringerung in der Zahl von möglichen Alternativen beim Wert der bestimmten Knoten des Baums von 7a die Beachtung von teilweise redundanten Wegen vermeidet.
Die Operation eines konventionellen Spracherkennungsalgorithmus, der nicht den Mechanismus unserer Erfindung benutzt, kann ebenso dargestellt werden.
Beim Beginn der Decodierung ist die Situation die von 6: es ist ersichtlich, dass beim Beginn der Analyse des Satzes das Erkennungsgerät annimmt, dass es sechs Möglichkeiten gegenübersteht. Die beiden ersten beginnen mit dem Symbol A, und ihre Verarbeitung ist genau identisch, bis zum Erscheinen der aktuellen Alternative, die zu dem zweiten Ausdruck gehört.
Somit enthält bis zu diesem Punkt der Speicherplatz, der in dem n-best-Algorithmus zur Erhaltung der meistversprechenden Wege benutzt wird, jede Suchhypothese zweimal.
Wenn außerdem die Gruppe <A> ziemlich komplex ist und das "Pruning" vor dem Erscheinen der auf <A> folgenden differenzierenden Ausdrücke erfolgt, dann wird der "n-best-search"-Algorithmus tatsächlich nur einen "n/2 best-search" ausführen, und jeder analysierte Weg wird verdoppelt.
Das angegebene Beispiel gehört zu einer Permutation mit drei Ausdrücken. Für eine Permutation mit vier oder mehr Ausdrücken gelten dieselben Bemerkungen für schädlichere Effekte für den Erkennungsalgorithmus. Die von dem Erkennungsgerät gesehene Perplexität ist wesentlich größer als die tatsächliche Perplexität des Sprachmodells.
7b zeigt die bekannte Verarbeitung: Es existieren sechs Alternativen beim Rang i anstelle von drei.
Dieses Beispiel zeigt, dass unsere Erfindung zwei Hauptvorteile aufweist, verglichen mit dem bekannten Verfahren, selbst wenn sie die Ausdrucksfähigkeit des Sprachmodells nicht erhöhen.
Anstelle des Speicherns von drei, eine Permutation beschreibenden Bäumen, das bis zu mehreren Speichern führen kann, speichert man nur die Ausdrücke in der Permutation plus Variable von einem einfachen Typ, die die mögliche Aktivierung der syntaktischen Gruppe im Laufe der n-best-Analyse des Erkennungsgeräts markieren.
Die auf Grammatik basierende syntaktische BNF-Verarbeitung der Permutationen ist nicht geeignet für den n-best-Suchalgorithmus, der durch den akustischen Teil der Spracherkennungsverarbeitung nötig wird: ein und dieselbe Analysehypothese wird mehrere Male angewandt, und die "n-best" ist meistens nur eine "n/m-best", wobei m von der Anzahl der Ausdrücke abhängig ist, die an der Permutation teilnehmen.
Das dargestellte neue Sprachmodell ist beabsichtigt für Dialoganwendungen in einer Sprache bei einer Vokabular-Mensch-Maschine, für hochflektierende Sprachen oder für eine spontane Spracherkennung.
Die auf den obigen Regeln basierende Sprache ist nicht ausdrucksvoller oder mächtiger als eine Sprache vom Typ BNF, ausgedrückt mittels der konventionellen Regeln, wenn der Satz von grammatikalischen Sätzen begrenzt ist. Der Vorteil der Erfindung besteht daher nicht in der Ausdrucksfähigkeit der neuen Sprache, sondern in den Vorteilen bei der Verarbeitung durch den Algorithmus des Geräts zur Spracher kennung der syntaktischen Regeln. Es wird weniger Speicher für die Verarbeitung benötigt.
Außerdem ermöglicht die neue syntaktische Regel eine größere Leichtigkeit beim Schreiben der Grammatik.
Da der Vorgang auf einem Stapel-basierenden Automaton beruht, ist er besonders geeignet, anders als die laufenden Lösungen, für Anwendungen für den Einbau mit geringen Kosten, wie Anwendungen in elektronischen Massenartikeln.

Claims

Spracherkennungsgerät mit einem Audioprozessor (2) für die Erfassung eines Audiosignals und einem Linguistikdecoder (6) für die zur Bestimmung einer dem Audiosignal entsprechenden Folge von Wörtern, dadurch gekennzeichnet, dass der Linguistikdecoder (6) ein Erkennungsgerät (9) und ein Sprachmodel (8) enthält, das durch eine Grammatik mit einer Syntaxregel für die wiederholungslose Änderung von Symbolen ermittelt wird, wobei das Erkennungsgerät Informationen verwaltet, die jedem Symbol der Permutation zugeordnet sind, und die eine Analyse jedes Symbols nur einmal ermöglicht, dass das Erkennungsgerät (9) einen Algorithmus des "beam search"- oder "n-best"-Typs durch Lieferung von n besten Ergebnissen durchführt und die wahrscheinlichste Lösung unter diesen besten Ergebnissen gewählt wird.
Gerät nach Anspruch 1, dadurch gekennzeichnet, dass die Syntaxregel zur Permutation von Symbolen eine Liste von Symbolen und als geeignete Ausdrücke für die Beschränkungen in der Ordnung der Symbole enthält.
Gerät nach einem der Ansprüche 1 oder 2, dadurch gekennzeichnet, dass bei der Zuordnung von Symbolen einer Permutation zu einer Reihe von Ausdrücken eines Satzes das Erkennungsgerät (9) ein Symbol auswählt für die Zuordnung zu einem bestimmten Ausdruck nur unter den Symbolen der Permutation, die nicht vorher zugeordnet worden sind.
Gerät nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass jedes Element des Satzes einem Wahrscheinlichkeitswert zugeordnet wird, und der Linguistikdecoder (6) mit einer Pruning-Strategie läuft, die nur den besten Hilfssatz zurückbehält.