DE3886080T2

DE3886080T2 - Verfahren und System zur Spracherkennung.

Info

Publication number: DE3886080T2
Application number: DE88302730T
Authority: DE
Inventors: Stephen Eliot Levinson
Original assignee: American Telephone and Telegraph Co Inc
Current assignee: AT&T Corp
Priority date: 1987-04-03
Filing date: 1988-03-28
Publication date: 1994-05-11
Anticipated expiration: 2008-03-29
Also published as: AU596510B2; ES2047029T3; EP0285353B1; SG22094G; CA1336207C; EP0285353A2; DE3886080D1; US4852180A; AU1404288A; HK107994A; EP0285353A3; JPS63259697A

Description

Technisches Gebiet

Diese Erfindung bezieht sich auf ein Spracherkennungssystem und im Eesonderen auf solche Systemarten, die unabhängig vom Sprecher sind.

Hintergrund der Erfindung

Es ist allgemein bekannt, daß die Spracherkennung das schwierigste der drei Hauptprobleme auf dem Gebiet der Sprachverarbeitung ist. Die Sprachcodierung ist derzeit die kommerziell am weitest verbreitete Art von Sprachverarbeitungseinrichtungen. Außerdem sind auch einige Einrichtungen zur Sprachsynthese bereits kommerziell erhältlich.
Trotzdem ist das Problem der Spracherkennung in einem hohen Maß nur schwer bearbeitbar. Die meisten Erkennungssysteme sind in ihrem Spracherkennungsvermögen auf die Erkennung der Sprache verschiedener Sprecher oder auf ein eng begrenztes Vokabular in einer sehr stark gebündelten oder aufgabengerichteten Umgebung eingeschränkt.
Es ist weitgehend bekannt, daß es wünschenswert wäre, über ein Spracherkennungssystem zu verfügen, mit dem es möglich ist, Sprache fortlaufend zu erkennen.
In den vorausgegangenen Jahren wurden einige auf Wörtern basierende fortlaufende Spracherkennungssysteme hergestellt. Ein solches bereits hergestelltes System ist beispielsweise in dem Aufsatz von S.E.Levinson, L.R.Rabiner "A Task-oriented Conversational Mode Speech Understanding System", in Speech and Speaker Pecognition, herausgegeben von M.R.Schroeder, Kargar, Easel, Schweiz, 1985 auf den Seiten 149-196, beschrieben. Dieses und andere ähnliche vor kurzem entwickelte Systeme basieren in erster Linie auf Wörtern. Während dieses Systeme zwar alle erfolgreich auf bestimmten, begrenzten Gebieten Sprache genau erkennen konnten, gibt es Grund zur Annahme, daß die Verwendung von Wörtern als fundamentale akustischen Muster die Möglichkeit ausschließen, daß die Eeschränkungen mit denen dieses Systeme derzeit arbeiten, überwunden werden, und daß diese Systeme fortlaufende Gespräche von vielen Sprecher mit großem Wortschatz aufnehmen können.
Eine sehr oft vorgeschlagene Alternative zu dem auf Wörtern basierenden Ansatz ist das sogenannte akustisch/phonetische Verfahren, bei dem einige relativ kurz dauernde phonetische Einheiten, aus denen alle Wörter aufgebaut werden können, durch ihre meßbaren akustischen Eigenschaften definiert werden. Allgemein gesprochen sollte Spracherkennung, die auf diesem Verfahren basiert, in drei Stufen stattfinden. Zuerst sollte das Sprachsignal in seine konstituierende, phonetische Pestandteile aufgeteilt werden, die dann auf der Grundlage ihrer gemessenen akustischen Eigenschaften klassifiziert werden. In einem zweiten Schritt sollten die phonetischen Einheiten dann zur Eildung von Wörtern auf einer Grundlage kombiniert werden, die teilweise ein Lexikon verwendet wird, in dem alle Wörter des Wortschatzes in den ausgewählten phonetischen Einheiten beschrieben sind. In einem dritten Schritt sollten die Wörter zum Eildung von Sätzen unter Berücksichtigung grammatikalischer Regeln kombiniert werden.
Einige sehr verschiedene Ausführungsbeispiele dieser grundlegenden Vorgehensweise können bei genauer Suche auch nach weniger offensichtlichen Gesichtspunkten einiger der oben erwähnten Komponenten in der Literatur gefunden werden. Siehe hierzu beispielsweise den Aufsatz von W.A.Woods, "Motivation ard Overview of SPEECHLIS: An Experimental Prototype for Speech and Understanding Research" in IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-23, No.1, Februar 1975 auf den Seiten 2-10. Alle derartigen Systeme sind sehr komplex, wobei die oben dargestellten Grundbestandtetle immer vorhanden waren, wenn auch manchmal in verborgener Form. Der Umstand, daß all diese Elemente bezüglich des Gesamtsyntax und des Gesamtsprachschatzes nicht in Gänze tauglich sind, bedeutet, daß diese Systeme in ihrer Nutzung sehr stark eingeschränkt sind (bspw. auf eine Aufgabe, wie die Wiedergewinnung von Informationen zu Mondgesteinsproben).
In dem Aufsatz "Explicit Modelling of state occupancy in hidden Markov models for automatic speech recognition", in ICASSP 85 auf den Seiten 1.2.1 bis 1.2.4. offenbaren M.J.Russel und R.K.Moore die Verwendung eines Markov-Modells mit expliziten Zustandsdauer-Wahrscheinlichkeitsdichtefunktionen zur Wortbildung innerhalb eines Wortschatzes für die Spracherkennung.
Dementsprechend ist es Gegenstand der vorliegenden Erfindung die Organisation eines derartigen Systemes zur Verfügung zu stellen, das über eine ausreichende Leistungsfähigkeit verfügt, um die gesamte Grammatik, den gesamten Wortschatz und alle möglichen verschiedenen Sprecher zu umfassen, und das methodisch derart organisiert ist, daß es leicht erweitert werden kann.

Zusammenfassung der Erfindung

Gemäß der vorliegenden Erfindung wird ein Spracherkennungsverfahren gemäß Anspruch 1 zur Verfügung gestellt.
Die Erfindung stellt eine leistungsfähige Organisation zur Weiterentwicklung und für einen weiteren Ausbau zur Verfügung. Anders als bei den zuvor beschriebenen Spracherkennungssystem foigt dies unmittelbar aus der obigen Darstellung des akustisch/phonetischen Verfahrens, das für eine Implementation im Umfeld von sehr komplizierten Anwendungen am geeignetsten ist. Die Unmittelbarkeit und Einfachheit der Implementierung folgt aus der Verwendung des kontinuierlichen, zeitdauervariablen verborgenen Markov-Modells als Modell für die akustisch/phonetische Sprachstruktur, an Stelle des weniger umfangreichen Satzes an phonologischen Regeln, die im Stand der Technik verwandt wurden. Der Ausdruck "Markov" bezieht sich hier auf die wahrscheinlichen und nicht direkt beobachtbaren Ereignisse, die einem Sprachsignal zugrunde liegen.
Das kontinuierliche, zeitdauervariable verborgene Markov-Modell, das bei dieser Erfindung verwandt wird, stellt die akustisch/phonetische Struktur von Sprache dar und repräsentiert die Wörter nicht direkt. Die Phonetikeinheiten, werden mit den nichtobservablen Zuständen der zugrundeliegenden Markov-Kette identifiziert. Die weiteren Parameter des Systems werden derart organisiert, daß ein dynamischer Programmieralgorithmus verwandt werden kann, um eine phonetische Transkription einer Äußerung zu erhalten.
Bei einer bevorzugten Ausführungsform der Erfindung basiert die lexikalische Zugriffsphase der Erkennung auf einem Aussprachewörterbuch (oben als Lexikon bezeichnet), in dem jeder Eintrag orthographisch in phonetischen Symbolen, die die Zustände der verborgenen Markov-Kette wiedergeben, dargestellt wird. Eestimmte andere Eigenschaften der bevorzugten Ausführungsform werden weiter unten dargestellt.
Der Erkennungsprozeß wird abschließend durcb Satzerkennungsschemata nach dem Stand der Technik abgeschlossen, bei dem der grammatikalisch am besten geformte Satz mit der auf Messungen beruhenden größten Wahrscheinlichkeit aus dem Wortgitter wiederhergestellt wird. Man erwartet, daß dieser Schlußteil des Erkennungsprozesses aufgrund der Kandidatenanordnungen und der Wahrscheinlichkeitssignale, die durch dieses Erfindung zur Verfügung gesteltt werden, effizienter arbeitet.

Kurze Geschreibung der Zeichnungen

Es zeigen:
Fig.1 schematisch die neuartige Organisation des neuen akustisch/phonetischen Spracherkennungsystems;
Fig.2 schematisch den Stand der Technik, der durch den oben erwähnten Aufsatz von Wood repräsentiert wird;
Fig.3 ein Flußdiagramm für einen Optimierungsalgorithmus zur Detektion der phonetischen Segmente und Zeitdauern für die in Fig.1 dargestellte Ausführungsform;
Fig.4 die Fortsetzung des Flußdiagramms von Fig.3;
Fig.5 ein Plockdiagramm, in dem einige der in der einleitenden lexikalischen Zugriffsprozedur zur Detektion von Wörtern durchgeführten Operationen dargestellt werden;
Fig.6 ein Diagramm, das einige der Konzepte, die in dem Flußdiagramm in Fig.7 verwandt werden, darstellt, das weiter unten beschrieben wird;
Fig.7 ein Flußdiagramm des Ausrichtungsschrittes;
Fig.8 ein Konzept, bei dem Paare benachbarter phonetischer Segmente in dem Ausrichtungsschritt verwandt werden;
Fig.9 zeigt Flußdiagramm der Implementation eines einfachen akustisch/phonetischen Modells für die Zahlen 0-9, das als Teil der hierin offenbarten lexikalischen Zugriffsprozedur verwandt werden kann.

Allgemeine Beschreibung

In der in Fig.1 gezeigten Ausführungsform stammt der Eingangssprachstrom von einem menschlichen Sprecher, was die Verwendung eines Eingangssprachstromes von einer anderen Maschine nicht ausschließt. Der Sprachstrom fließt in eine als Block 11 dargestellte bekannte Vorrichtung zur berechenbaren linearen Codieranalyse, die auch mit der Bezeichnung LPC-Analyse abgekürzt wird. Die grundlegende Organisation und der grundlegende Aufbau der Vorrichtung in Block 11 ist detailliert von F.Itakura in dem Aufsatz "Minimum Prediction Residual Principle Applied to Speech Recognition", IEEE Transaction on Acoustic Speech and Signal Processing, Vol. ASSP-23, Nr.1, November 1975 offenbart. Mit der Großintegration der modernen Elektronik sind daneben noch eine Reihe anderer Implementationen möglich, die beispielsweise gemäß Fig.2 des oben erwähnten Aufsatzes von L.R.Rabiner verwirklicht werden.
Der resultierende Satz von Sprachmerkmalsignalen wird anschließend durch eine Kombination von Techniken im Systemteil 12 verarbeitet, die nicht nur darauf beschränkt sind, phonetische Segemente mit einem gewissen Wahrscheinlichkeitsgrad zu detektieren, sondern auch eine nützliche Zeitdauerinformation zusammen mit den Segmentarrays zur Verfügung stellt. Der Verarbeitungsalgorithmus in der Vorrichtung 12 greift auf ein gespeichertes, sogenanntes kontinuierliches zeitdauervariables verborgenes Markov-Modell zu, das im auf den Erfinder zurückgehenden Aufsatz "Continuously Variable Duration Hidden Markov Models for Automatic Speech Recognition", in Computer Speech and Language, Bd.1, S. 29-44, Academic Press Inc., (London) Limited (1986> beschrieben ist. Darüberhinaus wird im Bauteil 12 ein Such-und Sortieralgorithmus zur Verfügung gestellt, der im folgenden noch näher beschrieben wird und vorteilhafterweise die komplementäre phonetische Information verwertet. Anschließend greift das Systembauteil 14 mit den phonetischen Segementen und Zeitdauern des Kandidaten auf das Lexikon 15 (das als erweiterter Speicher in einem Computer elektronisch gespeichert ist) vorzugsweise mit phonetischen Segmentpaaren zu, um die Anordnungen bzw. Arrays der Kandidatenworte zu erhalten.
Dann wird im Systembauteil 16 eine Ausrichtungssprozedur als Antwort auf die akustischen Eigenschaften aus der LPC-Analyse in Block 11 ausgeführt, um die Wahrscheinlichkeitssignale für die angezeigten Kandidatenwörter zu berechnen.
Die Implementation der Vorrichtungen 12-16 wird vorteilhafterweise auf einer Rechenanlage vorgenommen, beispielsweise auf einem Computer vom Typ Alliant FX-8, der von der Firma Alliant Computer Corperation in Acton, Ohio hergestellt wird. Das Modell 13, das Lexikon 15 und die Satzerkennungsvorrichtung 17 verwenden alle einen erheblichen Anteil an vorbestimmten Informationen, die in Speichern abgelegt sind.
Das Ausgangssignal der Ausrichtungssvorrichtung 16 wird dann in eine Satzerkennungsvorrichtung 17 nach dem Stand der Technik geführt, die verbleibenden Mehrdeutigkeiten der Wortkandidaten auflöst und den besten Satz auswählt.
Ein grundlegendes Verständnis für die Erfindung kann man erhalten, wenn man die folgenden Punkte in Betracht zieht. Eine grundlegende Untermauerung der hier vorgeschlagenen akustisch/phonetischen Vorrichtung ist die Annahme, daß die Sprache ein Code ist, der auf einer geringen Anzahl von Symbolen beruht. Während die Identität dieser Symbole unbekannt ist, können deren physikalische Erscheinungen direkt durch Messung des akustischen Signales beobachten werden. Unter dieser Annahme und im Licht vieler vorangegangener Experimente auf diesem Gebiet, erscheint es selbstverständlich ein solches Phänomen mit der sogennanten verborgenen Markov-Kette nachzubilden. Da angenommen wird, daß die Symbole des Codes diskret, unbekannt und nicht direkt beobachtbar sind, ist es plausibel, diese mit den Zuständen einer unterlegten, nicht beobachtbaren Wahrscheinlichkeitskette von Ereignissen zu kennzeichnen, die im allgemeinen als sogenannte Markov-Kette bezeichnet wird. Andereseits ist das akustische Signal zugänglich und von seinen spektralen und zeitlichen Eigenschaften wird angenommen, daß sie mit den Symbolen des Codes korreliert sind. Es erscheint daher zweckmäßig, das Signales als Satz einer statistischen Verteilung von akustischen Ereignissen darzustellen und jeweils eine Verteilung mit jedem Zustand der Markov-Kette zu verknüpfen. Um eine zeitliche Codierung der Informationem im Signal zu berücksichtigen, sollte man auch ein Verfahren zur Charakterisierung der Zeitdauer der wahrscheinlichen Zustände einschließen.

Detaillierte Beschreibung

Es stellt sich heraus, daß das kontinuierliche, zeitdauervariable verborgene Markov-Modell die wichtigsten Eigenschaften des Sprachsignals ziemlich gut wiedergibt. Die Phonetikeinheiten (d.h. die Code-Symbole) werden durch die verborgene Markov-Zustände {qi}ni=1 dargestellt. Die Zustandsübergangswahrscheinlichkeiten aij der verborgenen Markov-Kette sind verantwortlich für die phonotakustische Struktur der Sprache (d.h. den Code selbst). Die Akustik, die mit den Symbolen korreliert ist, sind die zeitindexierten Beobachtungen Ot &epsi; Rd. Die spektrale Information ist im Satz der Beobachtungsdichten {bj(Ot)}nj=1 und die zeitabhängige Information im Satz der Zeitdauerdichten {dj(t)}nj=1 enthalten.
Die d-dimensionalen Eeobachtungsdichten sollten gaussverteilt sein und die Zeitdauerdichten gammaverteilt. Unter diesen Annahmen sind die Parameter eines n-Zustandsmodells die Zustandsübergangswahrscheinlichkeiten, aij, 1≤i, j≤n; die Beobachtungsmittelwerte ujk, 1≤j≤n, 1≤k≤d, die Beobachtungskovarianzen ujkl, 1≤j≤n, 1≤k,l≤d; und die Zeitdauergestalts und ZuordnungsParamter γj und ηj, 1≤j≤n. Für diese Parameterisierung sind Verfahren zur Berechnung eines optimalen Wertesatzes bekannt. Ein solches Verfahren wird hierin im folgenden dargestellt.
In einigen Spracherkennungssystemen, die auf verborgenen Markov- Modellen basieren, wird jedes Wort aus dem Sprachschatz durch ein unterschiedliches Modell dargestellt, dessen Wahrscheinlichkeitsfunktion für ein gegebenes Eingangssignal ausgewertet und in einem Bayesschen Klassifikationsschema verwandt werden kann. In dem vorliegenden System spielt jedoch die Zustandssequenz die entscheidende Rolle, da sie eine phonetische Transkription hervorbringt. Die Wahrscheinlichkeitsfunktion wird ebenfalls benutzt, aber für einen weniger kritischen Fall, wie man später sehen wird.
In dem vorliegenden akustisch/phonetischen System ist es die wesentliche Aufgabe, zu ermitteln, wie man die Zustandssequenz, die zu einem gegebenen Sprachsignal gehört, bestimmt. Dies wird vorzugsweise durch einen dynamischen Programmieralgorithmus erreicht, der für die Zeitdauerdichten verantwortlich ist.
Sei αt(j) die Wahrscheinlichkeit der Zustandssequenz, die im Zustand j endet, der die Verknüpfungswahrscheinlichkeit des Zustandes und die Beobachtungssequenzen bis zur und einschließlich der Zeit t maximiert, dann kann diese Größe rekursiv aus folgender Formel berechnet werden:
für 1≤j≤n and 1≤t≤T
(Die Terme in Gleichung 1 werden im Anhang A definiert)
Wenn man gleichzeitig setzt:
kann man vom Endzustand
her , die gewünschte Zustandssequenz rekonstruieren, und damit die phonetische Transkription des Eingangssignales erhalten.
Die Aufgabe, die phonetische Transkription, die aus den Gleichungen 1-3 erhalten wird, als Wortsequenz zu interpretieren, ist nicht unähnlich der Aufgabe, einen Text zu lesen, der durch willkürliche Einfügungen, Auslassungen und Substitutionen von Buchstaben verstümmelt ist und der Leerzeichen zwischen den Wörtern besitzt. Das Verfahren, mit dem wir vorschlagen, die Interpretation durchzuführen, basiert auf dem psycholinguistischen Begriff des lexikalischen Zugriffs.
Die grundlegende Prämisse des Konzepts des lexikalischen Zugriffs besteht darin, daß die Wörter in einem Wörterbuch gespeichert werden, in dem sie nach einer phonetischen Orthographie anstatt nach akustischen Merkmalen wiedergegeben werden. Im kognitiven Prozeß des Verstehens von Sprache, werden Worte aus dem Wörterbuch auf der Grundlage von partieller phonetischer Information wiedergewonnen. Die Abbildung der Phonetik auf die Lexikographie ist daher inhärent eine Abbildung, bei der eine Vielzahl an Möglichkeiten auf eine Möglichkeit abgebildet wird, was zu zwei Arten von Vieldeutigkeiten führt. Zum einen kann eine phonetische Sequenz verschiedenen Wörtern gemeinsam sein. Zum anderen können Wörter auf der Basis von mehreren verschiedenen phonetischen Sequenzen wiedergewonnen werden. Die erste Art der Vieldeutigkeit erschwert das Erkennungsproblem und muß in einer späteren Stufe der Verarbeitung gelöst werden. Die zweite Art von Vieldeutigkeiten ist jedoch auf vielversprechendere Art und Weise zu lösen. Da die phonetische Transkription verstümmelt ist, wird ein Vielzahl von Aufrufen (Cues) für ein gegebenes Wort benötigt. Die spezielle lexikalische Zugriffsprozedur, dies in der vorliegenden Erfindung verwandt wird, stellt vorteilhafterweise ein Verfahren zur Verwertung komplementärer phonetischer Information zur Verfügung.
Die spezielle Form der hier verwandten Technik ist die folgende.
Nimmt man ans daß die phonetische Transkription, die aus der Auswertung der Gleichungen 1 bis 3 die Zustandssequenz:
q=q&sub1;,q&sub2;,....qi,qi+1,....Qi+p,.....qn (4)
ist, worin qi der i-te Zustand der Sequenz für 1≤i≤N ist. Man zieht alle p+1 Tupel der Form
q=qt,qt+1,.....,qt+p (5)
für 1≤t≤N-p bei festem p in Betracht. Jedes solche q wird als Argument der Hash-Funktion
verwandt, wobei deren Wert a eine Adresse im Lexikon darstellt. Die Primzahl P wird derart gewählt, daß sie größer als die Anzahl der Einträge im Lexikon ist, das derart aufgebaut ist, daß der a-te Eintrag eine orthographische Darstellung besitzt, die q als Untersequenz umfasst. Das Lexikon ist auch so aufgebaut, daß der a-te Eintrag eine Verbindung zu einem anderen q enthaltenden Wort besitzt. Das letzte Wort in der Kette besitzt eine Nullverbindung. Im Allgemeinen umfasst jeder lexikalische Gegenstand mehr als ein p+1 Tupel und muß daher eine separate Verbindung für jedes Tupel aufweisen. Die Verbindungen werden alle automatisch aus dei lexikalisch orthographischen Darstellung erzeugt und müssen nicht manuel konstruiert werden.
Weitere Einzelheiten bezüglich der Mathematik und der Computerimplementation eines solchen Verfahrens im Alllgemeinen können dem Buch von D.E.Knuth, "The Art of Computer Programming", Addison-Wesley, Bd.1, 5.230-231, und Bd.3, 5.506- 542, insbesondere dem Teil, der sich auf das Suchen und Sortieren bezieht, entnommen werden.
Die oben beschriebene lexikalische Zugriffsprozedur besitzt die Wirkung, daß sie eine grobe Schätzung für die Orte der Wörter gibt, beispielsweise ihren Beginn und ihr Ende im Sprachstrom. Wie zuvor bemerkt, sind diese Orte voraussichtlich widersprüchlich. Um diese Vieldeutigkeit aufzuheben, muß man mehr Information aus den akustischen Messungen und der pbonetsichen Transkription extrahieren und diese Information in einer Art darstellen, mit der eine optimale Interpretation des Signales erreicht wird. Im Speziellen soll die Wahrscheinlichkeit L(γ τ&sub0;,τm), mit der das Wort im Intervall (τ&sub0;,τm) auftritt, berechnet werden. Nachdem dies für alle Wörter, die durch die Zugriffsprozedur aufgefunden wurden, berechnet wurde, kann diese Information auf nützliche Art und Weise durch einen Graphen, der als sogenanntes Wortgitter bezeichnet wird, dargestellt werden.
Wenn man zunächst einen optimalen theoretischen Zugang zu dem Problem in Betracht zieht, nimmt man an, daß das zugegriffene Wort deine Orthographie
besitzt, in der die Subsequenz, die mit der phonetischen Transkription übereinstimmt
ist. Nimmt man für das erste weiter an, daß γ zum Zeitpunkt τ&sub0; begann und nicht später als τm endet, so muß q irgendwo in diesem Intervall mit dem Zustand qi, der zu einer Zeit τi &epsi; (τ&sub0;,τm) endet, auftreten, wobei τi+1> τi für 1≤i≤m ist. Eine vernünftige Definition von L(v τ&sub0;,τm) ist dann der Maximalwert der Verknüpfungswahrscheinlichkeit von
und q&sub1;,q&sub2;,...qm unter allen Möglichkeiten, die die Zwangsbedingungen der Zustandübergangszeiten τ&sub0;,τ&sub1;,...,τm erfüllen. Damit ist
wobei T der Satz aller möglichen Zustandsübergangszeiten ist, insbesondere
Wenn L(γ τ&sub0;,τm) wie in Gleichung 7 definiert wird, dann kann L berechnet werden aus:
Obwohl Gleichung 9 korrekt ist, ist sie praktisch nutzlos, da die Mächtigkeit von T im allgemeinen sehr groß ist. Es gibt jedoch einen effizienten Weg L(γ τ&sub0;,τm) zu berechnen. Wenn t( i) die maximale logarithmische Verknüpfungswahrscheinlichkeit von Oτ&sub0;,....Ot und &sub1;, &sub2;,... i ist, dann kann t( i) rekursiv für τ&sub0;< t< τm) und für 1≤i≤m aus der Gleichung
berechnet werden. Abschließend ergibt sich:
Der lexikalische Zugang und die Ausrichtungsprozedur, die oben dargestellt wurde, erzeugt im allgemeinen viele lexikalische Annahmen, von denen einige inkonsistent sein werden. Es sollen alle derartigen Annahmen in einer geeigneten Form aufbewahrt werden7 so daß die Vieldeutigekeiten nacheinander aufgelöst werden können und damit der beste Satz wiedergewonnen wird. Die Datenstruktur, die diese Bedingungen erfüllt ist das Wortgitter. Die horizontale Richtung im Gitter repräsentiert die Zeit und die alternativen lexikalischen Annahmen werden vertikal angeordnet, so daß die inkonsistenten Annahmen als Satz von Blöcken auftreten, die dieselbe horizontale aber eine verschiedene vertikale Position besitzen. Eine derartige Datenstruktur wird günstigerwesie in einem Computer als ein geführter Graph gespeichert, dessen Vertices die Wortgrenzen und dessen Kanten die Wörter, gewichtet mit ihren immer in der Zeit nach vorne gerichteten, zugehörigen logarithmischen Wahrscheinlichkeiten, sind. Man bezeichnet die Kante, die das Wort -im Intervall von τi bis τj mit einer Wahrscheinlichkeit L(γ τi,τj) darstellt als (τi,γ,τj,Lγ). Im Allgemeinen gibt es in dem Gitter Auslassungen und Überlappungen, die den zugehörenden Graphen unverbunden lassen würden. Dieses Problem wird dadurch beseitigt, daß immer dann zwei bestimmte Grenzen ermittelt werden, wenn ihr zeitliches Auftreten innerhalb einer geeigneten, empirisch gewählten Nachbarschaft zueinander liegt.
Kehrt man zu den Flußdiagrammen in den Fig.3 und 4 zurück, so werden in einem ersten Betriebsschritt des zentralen Computerprozessors alle zentralen Verarbeitungsregister auf geeignete Startbedingungen zurückgesetzt. Die Eingangsdaten von der Vorrichtung 11 liegen als Größenarrays an, die in einem Eingangsregister gespeichert werden, wobei dieses Array als Array bjτ wie im Flußdiagramm dargestellt bezeichnet wird.
Jede Art der Verarbeitung durch den Block 35 setzt Anfangsspeicherwerte. Die Blöcke 36 und 37 inkrementieren Zustands- und Zeitindizes. Die Blöcke 38-39 berechnen die Summe der logarithmischen Beobachtungswahrscheinlichkeiten.
Die Blöcke 40-44 berechnen die maximale Wahrscheinlichkeit für die ersten t Beobachtungen, die vom Anfangszustand herrühren.
Die Blöcke 45-54 berechnen die maximale Wahscheinlichkeit der ersten t Beobachtungen, die von irgendeiner Zustandssequenz herrühren.
Die Blöcke 55-59 bestimmen den wahrscheinlichsten Zustand, aus dem die letzte Beobachtung erzeugt wurde, und die Wahrscheinlichkeit der Beobachtungssequenz.
Die Blöcke 30 bis zum Schluß rekonstruieren die optimale Zustandssequenz.
Alle benötigten Parameter für das erste Array von Eingangsdaten, um die oben beschriebenen Prozeduren auszuführen sind jetzt berechnet worden und der Prozeß wird anschleißend mit der Bearbeitung des nächsten Arrays von Eingangsdaten fortgesetzt. Jeder Datensatz, der aus dem zyklischen Durchlauf durch das in den Fig.3 und 4 dargestellte Flußdiagramm folgt, kann anschließend an einer geeigneten Stelle im Speicher gespeichert werden, um in der Endberechnung der Gleichungen 1,2 und 3 verwandt zu werden, derart daß die abschließende phonetische Transkription des Eingangssignales aus den gewünschten Zustandssequenzen jeden Zykluses wiedergewonnen wird.
Wie oben erwähnt, ist die Aufgabe, die sich ergebende phonetische Transkription zu interpretieren dieselbe, wie einen Text zu lesen, in dem die Wörter zusammenlaufen, und in dem zufällige Einfügungen, Streichungen und Ersetzungen vorhanden sind.
Eine spezielle Form der hier verwandten Technik ist in den Fig.5 und 6 dargestellt.
Für den speziellen Fall von p=l kann die Mash-Funktion, Gleichung 6, durch die in Fig.6 gezeigte HEAD-Tabelle ersetzt werden. Bezüglich der Bedeutung und der Implementation der HEAD- Tabelle, siehe auch Knuth, Bd.3, (Zitat oben erwähnt). Wenn q = qtqt+1 = i,j ist, dann ist der Zeileneintrag i und der Spalteneintrag j der HEAD-Tabelle die Adresse des lexikalischen Zuganges, der q enthält. Diese Tabelle kann leicht automatisch erstellt werden. Die Methode für die HEAD-Tabelle kann auf p=2 oder größer verallgemeinert werden, was abei- schließlich ineffizient wird.
Es ist weder notwendig, die Definitionen der Gleichung 7 zu benutzen noch die Rekursion nach Gleichung 10, da die folgende äußerst einfache und hocheffiziente Methode existiert. Definiert man einfacherweise L(γ τ&sub0;,τm) als die Verknüpfungsswahrscheinlichkeit von OτO...Oτm und , wobei die Zustandsübergangszeiten durch die in Gleichung 2 berechneten Zustandszeitdauern bestimmt werden, so kann log[L(γ τ&sub0;,τm)] einfach aus Gleichung 9, anstelle der zuvor berechneten Segmentation der phonetischen Transkription, berechnet werden, ohne, daß eine Maximierung über T benutzt wird.
Das Flußdiagramm zur Erfüllung der wichtigsten Berechnungen nach den Gleichungen 4-10, ist in Fig.7 dargestellt. Dieses Flußdiagramm zeigt zusammen mit dem in Fig.8 dargestellten Ausrichtungsdiagramm, wie die verschiedenen Ergebnisse der vorigen Schritte, die jetzt in verschiedenen großen Speichern des Computers gespeichert sind, im Ausrichtungsschritt zusammenwirken. Der Anfangszugang ist im Block 73 dargestellt. Der Ausrichtungsschritt gemäß Fig.8, wird durch die Blöcke 75-77 repräsentiert. Block 8 zeigt die Berechnung der Wortwahrscheinlichkeiten gemäß folgender Beziehung:
für einige k,l
und die Speicherung auf der Kandidatenliste. Block 80 zeigt, wie die Verknüpfungsliste als Zugriff zum nächsten Kandidatenwort verwandt wird. Block 81 ist ein Test für die letzte Verknüpfung der Liste. Wenn dieser Test erfolgreich ist, wird die Steuerung an den Zustandszähler zurückgegeben und das nächste Zustandspaar wird an die HEAD-Tabelle angelegt. Block 83 zeigt den Test für das letzte Zustandspaar. Wenn dieser Test eifolgreich ist, durchläuft die Steuerung den Block 84, in dem der beste Kandidat ausgewählt und der Prozeß abgebrochen wird.
Der Ausrichtungssprozeß zeigt, wie eine berechnete Zustandssequenz an eine Wörterbuchbeitrag angepasst werden kann. Im Allgemeinen wird die Anpassung nicht perfekt sein, aber es wird eine Vielzahl von Zustandssequenzen geben, die teilweise zu der geschätzten Zustandssequenz des Kandidatenwortes passen.
Es soll nebenbei bemerkt werden, daß andere Ausrichtungsalgorithmen möglich sind, beispielsweise solche, die auf einer dynamischen Programmierung basieren, obwohl es Gegenstand der Erfindung ist, eine dynamisches Zeiteinhüllung, wenn möglich zu verhindern. Diese anderen möglichen Algorithmen sind mit den Merkmalen der vorliegenden Erfindung in der das Konzept der Verwendung eines separaten Ausrichtungsschrittes gemäß Fig.1 eingeführt wurde, kompatibel.
Abschließend sei zur Ausrichtungssprozedur gemäß Fig.7 bemerkt, daß im Prinzip alle Paare benachbarter Zustände in als Schlüssel in der Ausrichtungssprozedur verwendet werden können sollten.
Die Einzelheiten der Satzerkennungsvorrichtung 17 sind nicht der entscheidende Teil der vorliegenden Erfindung. Eine geeignete Organisation einer Satzerkennungsvorrichtung kann gemäß U.S.- Patent No. 4.277.644 sein, das am 7.Juli 1981 ausgegeben wurde.
Für den Fachmann auf dem vorliegenden Gebiet ist es unmittelbar einsichtig, daß alternativ zu den oben erwähnten Verfahren andere Satzerkennungsverfahren verwandt werden können. Zur Erkennung der Zahlen 0-9 kann ein 22-Zustandsmodell gemäß Fig.9 entwickelt werden. Um die Strukturen der zugrundeliegenden Markov-Kette zu vereinfachen werden drei Zustände kopiert, so daß sich insgesamt 25 Zustände ergeben. Die Vektoren, die jedem Segemnt zugeordnet sind, werden gesammelt und die wahrscheinlichste Schätzvariable für die Mittelwerte, die Kovarianzen, die Zeitdauern und die Standardabweichung der Zeitdauer werden berechnet. Die für ein Segment erhaltenen Werte werden dann als Parameterwerte mit den zugeordneten Zustände verknüpft.
Die Übergangswahrscheinlichkeiten der zugrundeliegenden Markov- Kette werden unter der Annahme, daß alle Zahlen gleich sind, geschätzt. Unter dieser Annahme ist es einfach die Anzahl der Zeiten zu zählen zu denen ein Übergang auftritt, aus deren Ereigniszahlen die Übergangswahrscheinlichkeiten leicht erhalten werden können.
Fig.9 zeigt die Arten der phonetischen Elemente, von denen die Spracherkennungsforscher annehmen, daß sie die am wahrscheinlichste oder zumindest geeigneste Repräsentation der irreduziblen Elemente des verborgenen Prozesses sind, die in der vokalen Strecke auftreten können
Für den Fachmann auf dem vorliegenden Gebiet ist sofort einsichtig, daß verschiedene Änderungen der zuvor beschriebenen Verfahren abhängig vom Grad der Allgültigkeit und der Möglichkeiten gegenüber dem Komplexitätsgrad, der in einem System gemäß der vorliegenden Erfindung benötig wird, gemacht werden können.

Claims

1. Verfahren zur Erkennung von Sprache mit den Schritten:

Speichern von Signalen, die ein Modeil der zu erkennenden Sprache darstellen, wobei das Modell vom Zustandsübergangstyp ist und jeder Zustand eindeutig durch eine phonetische Einheit identifiziert wird,

jedem Zustand ein Teil einer Übergangsmatrix zugeordnet ist, die Zustände beschreibt, denen der Zustand folgen kann und mit welcher Wahrscheinlichkeit,

jedem Zustand eine Beobachtungsdichtefunktion zugeordnet ist, die jedem Satz von Sprachmerkmalssignalen, die sich in flüssiger Sprache beobachten lassen, eine Wahrscheinlichkeit für die Beobachtung in Verbindung mit diesem Zustand zuweist, und

jedem Zustand eine Dauerdichtefunktion zugeordnet ist, die jeder Dauer, die der Zustand haben kann, eine Wahrscheinlichkeit für das Auftreten in flüssiger Sprache zuweist,

Speichern von Signalen, die lexikalische Kandidaten darstellen, welche Ansammlungen phonetischer Einheiten der Sprache in Verbindung mit phonetischen Teilinformationen des Typs sind, der sich in Wörterbüchern findet,

sequentielles Umwandeln aufeinanderfolgender Zeitrahmenteile einer Nußerung, die in entsprechend aufeinanderfolgenden Zeitrahmen auftreten, in Signale, die entsprechende Sätze akustischer, die Teile darstellender Merkmalssignale darstellen, und

Zugreifen auf das gespeicherte Modell und die gespeicherten lexikalischen Kandidaten zur Gewinnung von Signalen, die Folgen der phonetischen Einheiten darstellen, einschließlich Auswählen der optimalen Mitglieder dieser Folgen zur Erzeugung eines Auswahlsignals, das die Erkennung der Äußerung darstellt, dadurch gekennzeichnet, daß der Zugriffsschritt die Schritte enthält:

Zuordnung eines Phonetikeinheit-Signals und eines Phonetikdauer-Signals aus dem gespeicherten Modell zu einem oder mehreren der Zeitrahmenteile von Sprache, dargestellt durch einen oder mehrere der entsprechenden Sätze akustischer Merkmalssignale,

Maximieren unabhängig von den gespeicherten lexikalischen Kandidaten der Wahrscheinlichkeiten jeder phonet ischen Einheit und jeder phonetischen Dauer zusammen mit der Wahrscheinlichkeit für die Beobachtung des einen oder mehrerer entsprechender Sätze akustischer Merkmalssignale,

Zugreifen auf die gespeicherten lexikalischen Kandidaten entsprechend Teilen der vorgeschlagenen Folgen phonetischer Einheiten zur Gewinnung vorgesctlagener lexikalischer Kandidaten, die je jeden Teil enthalten,

immer dann, wenn mehrere vorgeschlagene lexikalische Kandidaten den gleichen Teil enthalten, Zuweisen der mehreren vorgeschlagenen lexikalischen Kandidaten zu dem einen oder den mehreren entsprechenden Sätzen akustischer Merkmalssignale, aus denen die vorgeschlagenen Folgen phonetischer Einheiten gewonnen worden sind, um die mehreren vorgeschlagenen lexikalischen Kandidaten auszuwerten.

2. Verfahren zur Erkennung von Sprache nach Anspruch 1, dadurch gekennzeichnet, daß der Modellspeicherschritt die Speicherung eines ergodischen Modells beinhaltet, bei dem jeder Zustand nach Jedem anderen Zustand auftreten kann.

3. Verfahren zur Erkennung von Sprache nach Anspruch 2, dadurch gekennzeichnet, daß der Schritt zur Speicherung lexikalischer Kandidaten die Schritte umfaßt

Speichern von Wörtern, die durch eine phonetische Orthographie dargestellt werden, welche durch partielle phonetische Informationen gekennzeichnet ist, derart, daß Wörter auf der Grundlage der phonetischen Einheiten wiedergewonnen werden können, die sie enthalten, und

Speicherung von Informationen, die eine Vielzahl von gleiche Folgen phonetischer Einheiten enthaltender Wörter verketten, wodurch für jede Folge phonetischer Einheiten so viele Wörter direkt zugreifbar sind, wie sie enthält.

4. Verfahren zur Erkennung von Sprache nach Anspruch 1, dadurch gekennzeichnet, daß die Zuordnung und Maximierung rekursiv für alle Zuordnungen und Übergänge über alle Zeitrahmen bis zum und einschließlich des augenblicklichen Zeitrahmens durchgeführt wird und

daß die Ergebnisse der Maximierung mittels eines Durchlaufens der phonetischen Bestimmungen in einer strengen Reihenfolge zuruckverfolgt werden, um eine vorgeschlagene phonetische Folge für einen Zugriff zu den lexikalischen Kandidaten zu erzeugen.

5. Verfahren zur Erkennung von Sprache nach Anspruch 1, dadurch gekennzeichnet, daß der Ausrichtungsschritt die Vielzahl von vorgeschlagenen lexikalischen Kandidaten so auswertet, daß sie nur diejenigen enthalten, die für eine nachfolgende unzweideutige Reihenfolge geeignet sind, und zwar durch eine Verarbeitung durch Verfahren, die sich auf die Satzstruktur und die Bedeutung beziehen.

6. Verfahren zur Erkennung von Sprache, dadurch gekennzeichnet, daß der Ausrichtungsschritt die Vielzahl von vorgeschlagenen lexikalischen Kandidaten so auswertet, daß nur der beste Kandidat ausgewählt wird, wodurch ein Auswahlsignal erzeugt wird, das fiie Aussprache als ein Wort darstellt.