DE68923981T2

DE68923981T2 - Verfahren zur Bestimmung von Textteilen und Verwendung.

Info

Publication number: DE68923981T2
Application number: DE68923981T
Authority: DE
Inventors: Kenneth Ward Church
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1988-02-05
Filing date: 1989-01-27
Publication date: 1996-05-15
Anticipated expiration: 2009-01-28
Also published as: EP0327266A3; KR890013549A; EP0327266A2; JPH01224796A; JPH0769910B2; DE68923981D1; CA1301345C; ES2076952T3; AU617749B2; IN175380B; KR970006402B1; US5146405A; AU2899089A; EP0327266B1

Description

Erfindungsgebiet

Die vorliegende Erfindung betrifft Verfahren zur Sprachteilbestimmung und Verfahren zur Benutzung der Ergebnisse einschließlich von Zwischenverfahren der Nominalphrasenanalyse, und mit Sprachsynthese, Spracherkennung, Schreibertraining, Korrekturlesen, Indexieren und Datenabruf.

Stand der Technik

Es wurde schon vor langer Zeit erkannt, daß die Fähigkeit der Bestimmung von Sprachteilen, besonders für Worte, die als unterschiedliche Sprachteile benutzt werden können, für viele unterschiedliche Probleme in der Anwendung der englischen Sprache relevant ist. Beispielsweise ist bekannt, daß Sprachbetonung einschließlich von Tonhöhe, Dauer und Energie von den bestimmten Sprachteilen von Worten und ihrer Satzordnung abhängig ist. Dementsprechend ist zur Sprachsynthese Sprachteilanalyse des schriftlichen oder nichtverbalen Eingabetextes notwendig, um ein wie menschliche Sprache klingendes Ergebnis zu erzeugen.
Darüber hinaus kann die automatische Sprachteilbestimmung eine wichtige Rolle bei der automatischen Spracherkennung, in der Ausbildung und dem Trainieren von Schreibern mit computerunterstützten Verfahren, beim Redigieren und Korrekturlesen von an einer Textverarbeitungsstation erzeugten Dokumenten, bei der Indexierung eines Dokuments und bei verschiedenen Formen des Abrufs von wortabhängigen Daten aus einer Datenbank spielen.
Beispielsweise finden sich einige dieser Anwendungen in verschiedenen Versionen von Writer's Workbench von AT&T. Man siehe den Artikel von Barbara Wallraff, "The Literate Computer" [Der gebildete Computer] in The Atlantic Monthly, Januar 1988, SS. 64 et seq., insbesondere die letzten zwei Absätze auf Seite 68. Das Verhältnis von Sprachteilen zur Indexierung findet sich in dem am 1. April 1986 C. L. Raye erteilten US-Patent Nr. 4,580,218.
Bislang sind in der Literatur zwei Hauptverfahren der automatischen Sprachteilbestimmung besprochen und zu einem gewissen Maß eingesetzt worden. Das erste ist von verschiedenen Ad-Hoc-Regeln abhängig, mit denen bestimmte interessierende Situationen erkannt werden sollen. Diese Regeln können beispielsweise auf die Benutzung von Wortendungen zur Vorhersage von Sprachteilen oder auf irgendeine Abwandlung davon bezogen sein. Einige Ad-Hoc-Regeln für Sprachteilbestimmung sind in dem unter dem UNIX - Betriebssystem laufenden Anwendungsprogramm Writer's Workbench benutzt worden. Diese Regeln sind gewöhnlich bezüglich der von ihnen erfolgreich lösbaren Probleme sehr begrenzt und es mangelt ihnen an grundlegender Einheitlichkeit. Dieses Verfahren ist in Computer Science Technical Report, Nr. 81, "PARTS - A System for Assigning Word Classes to English Text" [PARTS - Ein System zur Zuweisung von Wortklassen zu englischem Text] von L. L. Cherry, Juni 1978, Bell Telephone Laboratories Incorporated, beschrieben. Das zweite Hauptverfahren, das potentiell eine größere grundlegende Einheitlichkeit aufweist, ist das in dem Artikel "The Automatic Tagging of the LOB Corpus" [Die automatische Markierung des LOB-Korpus], in ICAME News, Band 7, SS. 13-33, von G. Leech et al., 1983, Universität Lancaster, England, beschriebene "N-Gramm"- Verfahren. Ein Teil des dort beschriebenen Verfahrens macht den zugewiesenen Sprachteil abhängig von den gegenwärtig besten Wahlen von Sprachteilen gewisser vorhergehender oder nachfolgender Worte auf Grundlage gewisser Regeln hinsichtlich möglicher Kombinationen aufeinanderfolgender Sprachteile. Bei dieser Analyse werden auch verschiedene Ad-Hoc-Regeln benutzt, so daß insgesamt dieses Verfahren immer noch nicht so genau wie wünschenswert ist. Zusätzlich werden bei diesem Verfahren keine lexikalischen Wahrscheinlichkeiten auf systematische Weise modelliert.
Die obigen Verfahren haben unter den Forschern der Technik aufgrund der obigen Betrachtungen und aufgrund enttäuschender Ergebnisse kein bedeutendes Interesse erweckt.
In der Tat sind Vermutungen angestellt worden, daß jedes "N-Gramm"-Verfahren schlechte Ergebnisse zeigen wird, da mit ihm der wahrscheinliche Satzaufbau nicht genügend überblickt werden kann. Andererseits ist es nicht möglich gewesen, den einem menschlichen Gehirn möglichen Gesamtüberblick bei der Analyse der Sprachteile in einem Satz robust in einen Rechner einzuprogrammieren. Man siehe das Buch A Theory of Syntactic Recognition for Natural Language [Eine Theorie der syntaktischen Erkennung bei natürlicher Sprache] von M. Marcus, MIT Press, Cambridge, MA, 1980. Infolgedessen ist die "N- Gramm"-artige Sprachteilbestimmung im Gegensatz zur "N- Gramm"-Analyse der Häufigkeit des Auftretens von Worten größtenteils auf Aufgaben wie die Beihilfe zur Erzeugung von größeren Volumina voll "markierten" Textes zur Verwendung bei zukünftiger Forschung beschränkt gewesen. Zu diesem Zweck müssen die Ergebnisse durch Eingriff eines sehr fähigen Menschens korrigiert werden.
Trotzdem wäre es wünschenswert, Sprachteile mit einem hohen Wahrscheinlichkeitsgrad mit relativ einfachen Verfahren wie dem "N-Gramm"-Verfahren identifizieren zu können, so daß es leicht in allen anfangs oben erwähnten Anwendungen angewandt werden kann.

Beschreibung der Erfindung

Erfindungsgemäß entspricht ein automatisiertes Verfahren zur Zuweisung von Sprachteilen zu Worten in einer Nachricht dem Anspruch 1 und ein automatisiertes Verfahren zur Bestimmung von Beginn- und Endegrenzen von Nominalphrasen in einer Nachricht dem Anspruch 4. Bevorzugte Formen der Verfahren entsprechen den abhängigen Ansprüchen.
In einer bevorzugten Ausführungsform der Erfindung sind Sprachteile Worten in einer Nachricht durch Optimieren des Produkts von lexikalen Einzelwortwahrscheinlichkeiten und normierten textabhängigen Dreiwortwahrscheinlichkeiten zugewiesen. Bei der Normierung werden die enthaltenen textabhängigen Zweiwortwahrscheinlichkeiten benutzt. Endpunkten von Sätzen (einschließlich einer Mehrzahl von Leerstellen zwischen ihnen), Interpunktion und mit niedriger Häufigkeit auftretenden Worten werden lexikale Wahrscheinlichkeiten zugewiesen und werden sonst so behandelt, als wenn sie Worte wären, so daß in der vorbekannten N-Gramm-Sprachteilzuweisung angetroffene Unterbrechungen und die vorbekannte Anwendung von Ad-Hoc-Regeln allgemein vermieden werden. Damit wird die Allgemeingültigkeit des Verfahrens hergestellt.
In einer Nachricht, in der den Worten vorher Sprachteile zugewiesen worden sind, werden die Nominalphrasen auf eine Weise identifiziert, die ihre Verwendung für Sprachsynthese erleichtert. Diese Nominalphrasenanalyse kann auch andere Anwendungen haben. Insbesondere ein hochprobabilistisches Verfahren, das anfangs an jedem Beginn oder Ende eines Wortes Anfänge und Enden von Nominalphrasen zuweist und nacheinander solche Zuweisungen durch Eliminieren der Zuweisungen mit der niedrigsten Wahrscheinlichkeit eliminiert, bis nur nichtkursive Zuweisungen mit sehr hoher Wahrscheinlichkeit übrigbleiben. Mit nichtrekursiven Zuweisungen ist gemeint, daß keine Nominalphrasenzuweisung, die sich teilweise oder ganz innerhalb einer anderen Nominalphrase befindet, behalten wird.
Als Alternative können mit dem Verfahren dieses Merkmals der vorliegenden Erfindung auch einige Nominalphrasen mit hoher Wahrscheinlichkeit beibehalten werden, die ganz innerhalb anderer Nominalphrasen auftreten, da solche Zuweisungen in der Praxis, beispielsweise bei Sprachsynthese, nützlich sind.
Einige Nominalphrasenzuweisungen, die stets eliminiert werden, sind Endungen ohne entsprechende Anfänge (zum Beispiel an einem Satzanfang) oder Anfänge ohne Endungen (zum Beispiel an einem Satzende), jedoch werden mit meinem Verfahren weiterhin Zuweisungen der Anfänge und Enden von Nominalphrasen mit niedriger Wahrscheinlichkeit elminiert oder, anders gesagt, nur die Zuweisungen mit höchster Wahrscheinlichkeit bewahrt.
Andere Nominalphrasen mit niedriger Wahrscheinlichkeit werden dadurch eliminiert, daß jeder Satz einer Nachricht wiederholt von Anfang bis Ende abgetastet wird und bei jeder Abtastung die Wahrscheinlichkeiten für jedes Paar eines Anfangs und eines Endes multipliziert werden und dann diejenigen Kombinationen mit einem Produkt in der Nähe oder oberhalb der vorher für das Gebiet des Satzes erhaltenen höchsten Wahrscheinlichkeit, oder die zumindest nicht mit anderen Nominalphrasen hoher Wahrscheinlichkeit unvereinbar sind, behalten werden.
Die Ausgabe des vorliegenden Sprachteilzuweisungsverfahrens kann die Eingabe in das vorliegende Nominalphrasenanalyseverfahren sein. In diesem Zusammenhang verstärken die in beiden Verfahren benutzten Optimierungsverfahren zu größter Wahrscheinlichkeit einander, da jedes Verfahren für sich selbst eine bessere Leistung als das des Standes der Technik aufweist.

Kurze Beschreibung der Zeichnung

Weitere Merkmale und Vorteile der vorliegenden Erfindung werden aus der folgenden detaillierten Beschreibung im Zusammenhang mit der Zeichnung offenbar. In der Zeichnung zeigt:
Figur 1 ein Flußdiagramm eines Sprachteilzuweisungsverfahrens nach der vorliegenden Erfindung;
Figur 2 ein Flußdiagramm eines Nominalphrasenanalyseverfahrens nach der vorliegenden Erfindung;
Figur 3 ein Blockschaltbild eines Sprachsynthetisierers unter Benutzung der Verfahren der Figuren 1 und 2; und
Figur 4 ein Blockschaltbild einer Textaufbereitung unter Benutzung des Verfahrens der Figur 1.

Beschreibung der beispielhaften Ausführungsformen

Im Verfahren der Figur 1 wird für Darstellungszwecke angenommen, daß die Nachricht eine Textnachricht war, die gelesen und in einer elektronischen Form gespeichert worden ist. Wie im Block 11 angedeutet, wird der erste Schritt dann das satzweise Lesen des gespeicherten Textes sein. Dieser Schritt erfordert die Bestimmung von Satzgrenzen. Dafür gibt es viele bekannte Verfahren, aber hier wird bevorzugt, die Anfangsannahme zu treffen, daß jeder Punkt einen Satz beendet, und dann diesen Satz und seine Ergebnisse zu verwerfen, wenn durch das vorliegende Verfahren nachher bewiesen wird, daß der Punkt einen wahrscheinlicheren Anwendungszweck hatte.
Auf alle Fälle schreitet das vorliegende Verfahren fort, beginnend am Ende jeden Satz zu bearbeiten.
Die nachfolgenden Schritte können in drei allgemeine Schritte gruppiert werden:
Markieren der Worte mit Zeichen (Block 12);
Berechnen der lexikalen Sprachteilwahrscheinlichkeiten (Block 13), beginnend am Satzende; und
Optimieren der textabhängigen Sprachteilwahrscheinlichkeiten (Block 14), natürlich mit dem allgemeinen Endschritt (15) des Anwendens des Ergebnisses auf irgendeine der vielen möglichen Nutzungen von Sprachteilanalyse.
Diese allgemeinen Schritte können, wie nunmehr erläutert wird, in viele weitere detaillierte Schritte eingeteilt werden.
Bei der Markierung von Worten mit Zeichen führe ich an dem gewöhnlichen linguistischen Ansatz zur Sprachteilanalyse geringe, aber doch bedeutende Änderungen durch. Trotzdem benutze ich aus praktischen Gründen dieselben Bezeichnungen von Sprachteilen wie die in der "Liste der Markierungen" in dem Buch von W. Nelson Francis et al., Freguency Analvysis of English Usage [Häufigkeitsanalyse im Gebrauch des Englischen], Houghton Mifflin Co., 1982, auf Seiten 6-8 angeführten. Sie werden überall dort, wo es zum Verständnis von Beispielen beiträgt, hier wiederholt werden.
Zu der Markierung mit Zeichen gehört die Kennzeichnung von Worten und gewissen Nichtworten wie Interpunktion und Klammern. Zusätzlich hat sich als wichtig herausgestellt, nach jedem Satzpunkt zwei Leerstellen zuzuweisen, um für solche Stellen in einem markierten Textkörper wie dem, der die Grundlage für das Buch von Francis et al. bildetete (der vorangehende Textkörper wird gewöhnlich der "Brown-Korpus" genannt), eine neue Menge von Häufigkeiten zu erzeugen. An dem Vorgang beteiligte Zeichenarten sind die eigentlichen Worte eines Satzes und die Strukturanzeiger, die den Prozeß darüber informieren, daß das Ende eines Satzes erreicht worden ist. Diese Strukturanzeiger enthalten beispielsweise einen Satzendeanzeiger wie z.B. das maschinenlesbare Zeichen für einen Punkt, einen durch ein entsprechendes im Manuskript oder der Datei zusammen mit den Textworten gespeichertes Formatierungszeichen dargestellten Kopf oder Absatzanzeiger und einen Dateiendeanzeiger.
Etwas vorausschauend werden wir sehen, daß für jedes abschließende Wort in einem Satz seine textabhängige Wahrscheinlichkeit zusammen mit der für den Punkt und die nachfolgende Leerstelle gemessen werden wird. Diese drei bilden ein "Trigramm", und die Wahrscheinlichkeitsanalyse ist daher die Untersuchung der Frage: "Wie wahrscheinlich ist es, daß dieses Wort als ein gewisser Sprachteil einen Satz beenden kann?" In diesem Fall ist die textabhängige Wahrscheinlichkeit, den Punkt an dieser Stelle zu beobachten, sehr hoch (in der Nähe von 1,0); und die textabhängige Wahrscheinlichkeit für die Leerstelle ist 1,0. In jedem Fall sind diese Wahrscheinlichkeiten dieselben, sowohl in Zähler als auch im Nenner der normierten Wahrscheinlichkeit, so daß die resultierende textabhängige Wahrscheinlichkeit nur die gemessene Wahrscheinlichkeit dafür ist, den betroffenen Sprachteil am Ende eines Satzes zu sehen, was wiederum eine Statistik ist, die aus dem Textkörper tabelliert und in einem Festspeicher des Rechners gespeichert werden kann.
Nach Markierung der beobachteten Worte und Zeichen, wie in Verbindung mit Block 12 erläutert, werden mit dem vorliegenden Verfahren als nächstes die lexikalen Sprachteilwahrscheinlichkeiten (die Wahrscheinlichkeit der Beobachtung des Sprachteils i bei dem gegebenen Wort j) in Abhängigkeit von der Häufigkeit des Auftretens wie folgt berechnet: Würde jeder Sinn jedes interessierenden Wortes mit einigermaßen hoher Häufigkeit im Brown-Korpus auftreten, würde diese Berechnung einfach der Quotient der beobachteten Häufigkeit des Auftretens des Wortes als bestimmter Sprachteil, geteilt durch seine Gesamthäufigkeit des Auftretens, ungeachtet des Sprachteils sein.
Hier wird diese Berechnung für Worte oder Zeichen mit niedriger Häufigkeit des Auftretens wie folgt ersetzt: Man bedenke, daß es nach dem Gesetz von Zipf stets einen langen Schwanz von Worten, die nur wenige Male erscheinen, geben wird, egal wie viel Text wir betrachten. Im Brown-Korpus erscheinen beispielsweise 40.000 Worte fünfmal oder weniger oft. Wenn ein Wort wie yawn einmal als Substantivum und einmal als Verbum erscheint, wie hoch ist die Wahrscheinlichkeit, daß es ein Adjektiv sein kann? Ohne weitere Information ist es unmöglich, das zu sagen. Glücklicherweise kann dieses Problem in gewissem Maß durch Wörterbücher gelindert werden. Zu der Häufigkeitszählung von Möglichkeiten im Wörterbuch addieren wir eins. Beispielsweise wird yawn zufälligerweise in unserem Wörterbuch als entweder ein Substantivum oder als ein Verbum aufgeführt. Damit glätten wir die Möglichkeiten. In diesem Fall bleiben die Wahrscheinlichkeiten unverändert. Yawn wird 50% der Zeit als Substantivum und die übrige Zeit als Verbum geschätzt, sowohl vor als auch nach der Glättung. Es besteht keine Möglichkeit, daß yawn ein Adjektiv ist.
In manchen anderen Fällen macht die Glättung einen großen Unterschied. Man betrachte das Wort cans. Dieses Wort erscheint fünfmal als Substantivum in der Mehrzahl und niemals als Verbum im Brown-Korpus. Das Lexikon (und seine morphologischen Routinen) geben glücklicherweise beide Möglichkeiten an. So lautet die revidierte Schätzung, daß cans 6/7 Mal als Substantivum in der Mehrzahl und 1/7 Mal als Verbum erscheint.
So addieren wir "eins" zu jeder beobachteten Häufigkeit des Auftretens als jeder mögliche Sprachteil entsprechend dem Lernmaterial, einem ungekürzten Wörterbuch; und berechnen daraus die lexikalischen Wahrscheinlichkeiten.
Um damit zu beginnen, unseren Wahrscheinlichkeitssuchbaum für dieses Wort aufzubauen, multiplizieren wir nun diese lexikalische Wahrscheinlichkeit mit der normierten geschätzten textabhängigen Wahrscheinlichkeit, d.h. der Häufigkeit der Beobachtungen des Sprachteiles X bei gegebenen nachfolgenden bereits bestimmten Sprachteilen Y und Z, geteilt durch die "Bigramm"-Häufigkeit der Beobachtungen des Sprachteils Y bei gegebenem Sprachteil Z. Die letzteren beiden Daten können von einem bereits markierten Korpus tabelliert werden, auf den von Francis et al. in ihrem Buch Bezug genommen wird. Die tabellierten Daten werden in einem Rechnerspeicher gespeichert.
Wir schreiten damit fort, den obigen Prozeß für das betreffende Wort als jeden anderen Sprachteil, der es sein kann, zu wiederholen, und behalten nur die maximalen Wahrscheinlichkeiten aus unseren vorigen Berechnungsmengen. Ehe wir zum vorletzten Wort im Satz fortschreiten, haben wir eine maximale Produktwahrscheinlichkeit für das letzte Wort errechnet.
Es lassen sich bereits zweierlei Dinge über den Prozeß in Betracht ziehen. Als erstes liegen die in dem Produkt benutzten lexikalischen Wahrscheinlichkeiten entlang einem Kontinuum und sind nicht nur einer von drei willkürlich zugewiesenen Werten, so wie sie in der Literaturstelle von Leech et al. benutzt werden. Zweitens ist, obwohl die Anwendungen der Mathematik für Worte, die in Wirklichkeit am Ende eines Satzes liegen, trivial zu sein scheinen, der bedeutende Punkt, daß überall dieselbe Mathematik angewandt wird.
Zu einem vollständigeren spezifischen Beispiel fortschreitend sollte bedacht werden, daß die Wahrscheinlichkeitsschätzungen durch Lernen am markierten Brown- Korpus erhalten wurden, auf den Bezug genommen, der aber nicht in der oben erwähnten Analyse von Francis et al. erwähnt ist. Es ist ein Korpus mit annähernd einer Million Worten, wobei Sprachteilmarkierungen zugewiesen und mühsam von Hand überprüft wurden.
Die Gesamtleistung des vorliegenden Verfahrens ist überraschend gut, wenn man in Betracht zieht, daß seine Funktionsweise streng ortsbezogen ist und daß es ihm im allgemeinen unmöglich ist, auf beide Seiten einer Nominalphrase zu schauen, um beispielsweise die Anwendungsmöglichkeit eines möglichen Hilfsverbs zu bestimmen.
Wenn jeder Möglichkeit im Wörterbuch gleiches Gewicht zugeteilt werden muß, ist die Syntaxanalyse sehr schwierig. Im allgemeinen liegt der Brennpunkt von Wörterbüchern auf dem Möglichen und nicht auf dem Wahrscheinlichen. Man betrachte den trivialen Satz "I see a bird". In der Praxis ist jedes Wort in dem Satz unzweideutig. Nach Francis und Kucera erscheint "I" als Pronomen in 5837 von 5838 Beobachtungen (100%), "see" erscheint als Verbum in 771 von 772 Beobachtungen (100%), "a" erscheint als Artikel in 23013 von 23019 Beobachtungen (100%) und "bird" erscheint als Substantiv in 26 von 26 Beobachtungen (100%). Nach Websters Siebentem New Collegiate Dictionary ist jedoch jedes Wort zweideutig. Zusätzlich zu den gewünschten Zuweisungen von Markierungen (Sprachteilen) sind die ersten drei Worte als Substantiva und das letzte als intransitives Verbum aufgeführt. Es wäre zu hoffen, daß diese unerwünschten Zuweisungen von der Syntaxanalyse als syntaktisch schlecht gebildet ausgeschlossen werden könnten. Leider gibt es im Stand der Technik keine konsequente Art und Weise, dieses Ergebnis zu erzielen. Wenn die Syntaxanalyse Nominalphrasen der Form:
[NP [N city] [N school][N committee][N meeting]]
akzeptiert, dann kann sie
[NP[N I][N see] [N a] [N bird]] nicht ausschließen, wobei "NP" für "Nominalphrase" und "N" für "Substantiv" stehen.
Gleichermaßen muß die Syntaxanalyse wahrscheinlich auch bird als intransitives Verbum akzeptieren, da:
[S[NP[N I][N see][N a]] [VP[V bird]]] syntaktisch nicht falsch ist, wobei "S" für "Subjekt" und "VP" für "Verbalphrase" und "V" für "Verbum" stehen.
Diese Sprachteilzuweisungen sind nicht falsch; sie sind nur äußerst unwahrscheinlich.
Man betrachte nochmals den Satz "I see a bird". Das Problem besteht darin, eine Zuweisung von Sprachteilen zu Worten zu finden, die sowohl die lexikalischen als auch die textabhängigen Wahrscheinlichkeiten optimiert, die beide aus dem markierten Brown-Korpus geschätzt werden. Die lexikalischen Wahrscheinlichkeiten werden aus den folgenden Häufigkeiten geschätzt (PPSS = Pronomen im Singular; NP = Eigenname; VB = Verbum; UH = Interjektion; IN = Präposition; AT = Artikel; NN = Substantiv): Wort Sprachteile I see a bird In (französisch)
Die lexikalischen Wahrscheinlichkeiten werden auf offensichtliche Weise geschätzt. Beispielsweise wird die Wahrscheinlichkeit, daß "I" ein Pronomen ist, Wahrsch(PPSS "I") als die Häuf(PPSS "I")/Häuf("I") beziehungsweise 5837/5838 geschätzt. Die Wahrscheinlichkeit, daß "see" ein Verbum ist, wird als 771/772 geschätzt. Die anderen Schätzungen der lexikalischen Wahrscheinlichkeit folgen demselben Muster.
Die textabhängige Wahrscheinlichkeit, die Wahrscheinlichkeit der Beobachtung des Sprachteiles X bei gegebenen folgenden zwei Sprachteilen Y und Z wird durch Teilen der Trigramm-Sprachteilhäufigkeit XYZ durch die Bigramm-Sprachteilhäufigkeit YZ geschätzt. So wird beispielsweise geschätzt, daß die Wahrscheinlichkeit der Beobachtung eines Verbums vor einem Artikel und einem Substantiv das Verhältnis der Häuf(VB, AT, NN) über der Häuf(AT, NN) beziehungsweise 3412/53091 = 0,064 ist. Die Wahrscheinlichkeit der Beobachtung eines Substantivums im selben Zusammenhang wird als Verhältnis der Häuf(NN, AT, NN) über 53091 beziehungsweise 629/53091 = 0,01 geschätzt. Die anderen Schätzungen der textabhängigen Wahrscheinlichkeit folgen demselben Muster.
Um die Zuweisung von Sprachteilmarkierungen zu Worten zu finden, wird eine Suche durchgeführt, die das Produkt der lexikalischen und textabhängigen Wahrscheinlichkeit optimiert. Konzeptmäßig zählt die Suche alle möglichen Zuweisungen von Sprachteilen zu Eingangsworten auf. In diesem Fall gibt es vier Eingangsworte, von denen drei auf zwei Weisen zweideutig sind, wodurch eine Menge von 2*2*2*1=8 mölichen Zuweisungen von Sprachteilen zu
Eingangsworten erzeugt wird: I see a bird
Jede der acht Folgen wird dann durch das Produkt der lexikalischen Wahrscheinlichkeiten und der textabhängigen Wahrscheinlichkeiten gewichtet und die beste Folge wird ausgewählt. In diesem Fall ist die erste Folge bei weitem die beste.
Es ist in der Tat nicht notwendig, alle möglichen Zuweisungen auf zuzählen, da die Bewertungsfunktion nicht mehr als zwei Worte übersehen kann. Anders gesagt, ist es in dem Vorgang der Aufzählung von Sprachteilfolgen in manchen Fällen möglich, zu wissen, daß eine Folge unmöglich mit einer anderen in den Wettbewerb treten kann und daher verworfen werden kann. Aufgrund dieser Tatsache werden nur (n) Wege aufgezählt. Diese Optimierung läßt sich mit einem Beispiel erläutern:
Man finde alle Zuweisungen von Sprachteilen zu "bird" und bewerte die Teilfolge. Hiernach sind alle Bewertungen als logarithmische Wahrscheinlichkeiten zu deuten.
(-4,848072 "NN")
Man finde alle Zuweisungen von Sprachteilen zu "a" und bewerte diese. An dieser Stelle gibt es zwei Wege:
(-7,4453945 "AT" "NN")
(-15,01957 "IN "NN")
Man finde nunmehr Zuweisungen von "see" und bewerte diese. An dieser Stelle scheint die Anzahl von Wegen immer noch exponentiell zu wachsen.
(-10,1914 "VB" "AT" "NN")
(-18,54318 "VB" "IN" "NN")
(-29,974142 "UH" "AT" "NN")
(-36,53299 "UH" "IN" "NN")
Nunmehr finde man Zuweisungen von "I" und bewerte diese. Es ist zu bemerken, daß es jedoch nicht mehr notwendig ist, die Hypothese aufzustellen, daß "a" eine französische Präposition IN sein könnte, da alle vier Wege PPSS VB IN NN, NN VB IN NN, PPSS UH IN NN und NP UH IN NN weniger hoch bewertet werden als irgendein anderer Weg und irgendeine zusätzliche Eingabe die relative Bewertung keinesfalls ändern könnte. Insbesondere wird der Weg PPSS VB IN NN niedriger als der Weg PPSS VB AT NN bewertet und eine zusätzliche Eingabe wird PPSS VB IN NN nicht helfen, da die textabhängige Bewertungsfunktion ein begrenztes Fenster von drei Sprachteilen aufweist und dies nicht dazu ausreicht, an dem bestehenden PPSS und VB vorbeizusehen.
(-12,927581 "PPSS" "VB" "AT" "NN")
(-24,177242 "NP" "VB" "AT" "NN")
(-35,667458 "PPSS" "UH" "AT" "NN")
(-44,33943 "NP" "UH" "AT" "NN")
Die Suche läuft noch zwei Iterationen weiter, mit der Annahme von leeren Sprachteilen für außerhalb des Bereichs liegende Worte.
(-13,262333 Leerstelle "PPSS" "VB" "AT" "NN")
(-26,5196 Leerstelle "NP" "VB" "AT" "NN")
Abschließend ist das Ergebnis: PPSS VB AT NN.
(-13,262333 Leerstelle Leerstelle "PPSS" "VB" "AT" "NN").
Ein etwas interessanteres Beispiel ist: "Can they can cans".
cans
(-5,456845 "NNS"), wobei "NNS" für "Substantiv in der Mehrzahl" steht.
can
(-12,603266 "NN" "NNS")
(-15,935471 "VB" "NNS")
(-15,946739 "MD" "NNS"), wobei "MD" für "Modell-Hilfswort" steht.
they
(-18,02618 "PPSS" "MD" "NNS")
(-18,779934 "PPSS" "VB" "NNS")
(-21,411636 "PPSS" "NN" "NNS")
can
(-21,766554 "MD" "PPSS" "VB" "NNS")
(-26,45485 "NN" "PPSS" "MD" "NNS")
(-28,306572 "VB" "PPSS" "MD" "NNS")
(-21,932137 Leerstelle "MD" "PPSS" "VB" "NNS")
(-30,170452 Leerstelle "VB" "PPSS" "MD" "NNS")
(-31,453785 Leerstelle "NN" "PPSS" "MD" "NNS")
Und das Ergebnis ist: Can/MD they/PPSS can/VB cans/NNS
Weitere Einzelheiten des Verfahrens - Optimierung von Wahrscheinlichkeiten - sind aus Anhang A ersichtlich.
Mit dieser Beschreibung wird die Beschreibung der Funktionsweise bis zu der des Blocks 14 vollendet.
Als Beispiel der im Block 15 auftretenden Nutzungen ist die Anzeige konzeptmäßig die einfachste, aber immer noch praktisch, insbesondere in einem Dialogsystem mit einem menschlichen Bediener. Ein ausführlicheres Nutzungsbeispiel wird hiernach in der Beschreibung der Figuren 3 und 4 gegeben. Als erstes ist es jedoch wünschenswert, noch ein Werkzeug zu beschreiben. Dieses Werkzeug ist die Nominalphrasen-Syntaxanalyse unter Verwendung einer Erweiterung des vorliegenden Verfahrens.
Ähnliche stochastische Verfahren sind zur Lokalisierung einfacher Nominalphrasen mit sehr hoher Genauigkeit angewandt worden. Das vorgeschlagene Verfahren ist ein stochastisches Analog der Vorrangs-Syntaxanalyse. Man erinnere sich, daß bei Vorrangs-Syntaxanalyse eine Tabelle angewandt wird, die besagt, ob zwischen beliebigen zwei (Abschluß- oder Nichtabschluß-)Kategorien eine Klammer auf oder Klammer zu einzufügen ist. Das vorgeschlagene Verfahren bedient sich einer Tabelle, die die Wahrscheinlichkeiten einer Klammer auf und Klammer zu zwischen allen Paaren von Sprachteilen angibt. Ein Beispiel wird unten für die fünf Sprachteile: AT (Artikel), NN (Substantiv im Singular), NNS (Substantiv nicht im Singular), VB (nicht gebeugtes Verbum), IN (Präposition) gezeigt. Diese Wahrscheinlichkeiten wurden aus circa 40.000 Worten von aus dem Brown-Korpus ausgewähltem Lernmaterial geschätzt. Das Lernmaterial wurde durch aufwendige halbautomatische Mittel syntaktisch in Nominalphrasen eingeteilt. Wahrscheinlichkeit des Beginnens einer Nominalphrase zwischen ersten und zweiten Worten Zweites Wort Erstes Wort Wahrscheinlichkeit des Beendens einer Nominalphrase zwischen ersten und zweiten Worten Zweites Wort Erstes Wort
Der stochastischen Syntaxanalyse wird eine Folge von Sprachteilen als Eingabe gegeben und sie wird aufgefordert, dem Anfang und Ende von Nominalphrasen entsprechende Klammern einzufügen. Konzeptmäßig zählt die Syntaxanalyse alle möglichen syntaktischen Aufteilungen der Eingabe auf und wertet sie jeweils nach den Vorrangswahrscheinlichkeiten. Man betrachte beispielsweise die Eingangsfolge: NN VB. Es gibt fünf mögliche Weisen, diese Folge mit Klammern zu versehen (angenommen, es gibt keine Rekursion):
NN VB
[NN] VB
[NN VB]
[NN] [VB]
NN [VB]
Jede dieser syntaktischen Einteilungen wird durch Multiplizieren von sechs Vorrangswahrscheinlichkeiten bewertet, der Wahrscheinlichkeit, daß eine Klammer auf/zu an irgendeiner der drei Stellen (vor dem NN, nach dem NN oder nach dem VB) erscheint (oder nicht erscheint). Die syntaktische Einteilung mit der höchsten Bewertung wird als Ausgabe zurückgeführt.
Das Verfahren funktioniert beachtenswert gut, wenn man bedenkt, wie einfach es ist. Es besteht eine Neigung, die Anzahl der Klammern zu unterschätzen und zwei Nominalphrasen zusammen zuführen.
Es ist zu bemerken, daß die in der Figur 2 beschriebene Nominalphrasen-Syntaxanalyse annimmt, daß die Ausgabe aus der Sprachteilzuweisung der Figur 1 ihre Eingabe ist. Sie könnte jedoch auch die Ergebnisse jedes anderen Sprachteilzuweisungsverfahrens benutzen.
Auf alle Fälle sind im Block 22 alle möglichen Nominalphrasengrenzen zugewiesen. Im Block 23 werden nichtpaarige Grenzen beseitigt. Bei jedem Satz würden diese eine Beendigungsgrenze am Satzanfang und eine Beginngrenze am Satzende (einschließlich Leerstellen) umfassen.
Zu der Funktion des Blocks 24 gehört das Auslegen eines Wahrscheinlichkeitsbaumes für jede in sich widerspruchsfreie Zuweisung von Nominalphrasengrenzen. Die Zuweisungen mit der höchsten Wahrscheinlichkeit werden dann für die spätere Verarbeitung, z.B. Nutzung der Ergebnisse, wie in Block 25 angedeutet, zurückgehalten.
Wir wenden uns nunmehr einer spezifischeren Anwendung der vorliegenden Erfindung zu. Sprachteilmarkierung ist ein bedeutendes praktisches Problem mit möglichen Anwendungen in vielen Bereichen einschließlich Sprachsynthese, Spracherkennung, Buchstabierungskorrektur, Korrekturlesen, Fragenbeantwortung, Maschinenübersetzung und die Durchsuchung von großen Textdatenbänken (beispielsweise Patenten, Zeitungen). Mein besonderes Interesse liegt in Sprachsyntheseanwendungen, wobei es klar ist, daß die Aussprache manchmal von Sprachteilen abhängig ist. Man betrachte die folgenden drei Beispiele, wo die Aussprache von Sprachteilen abhängig ist.
Als erstes gibt es Worte wie "wind", wo das Substantiv einen anderen Vokal als das Verbum hat. Das heißt, das Substantiv "wind" weist einen kurzen Vokal wie bei "The wind is strong" auf, während das Verbum "wind" einen langen wie bei "Do not forget to wind your watch" aufweist.
Zweitens wird das Pronomen "that" wie bei "Did you see THAT?" betont, ungleich dem Ergänzungswort "that" wie bei "it is a shame that he is leaving".
Drittens beachte man den Unterschied zwischen "oily FLUID" und "TRANSMISSION fluid"; als allgemeine Regel wird eine Adjektiv-Substantiv-Folge wie "oily FLUID" typisch rechts betont, während eine Substantiv- Substantiv-Folge wie "TRANSMISSION fluid" typisch links betont wird, wie beispielsweise von Erik Fudge in English Word Stress, George Allen & Unroin (Publishers) Ltd., London, 1984 angegeben. Dies sind nur drei der vielen Konstruktionen, die natürlicher klingen würden, wenn der Synthetisierer Zugriff auf genaue Sprachteilinformationen hätte.
In der Figur 3 ist der Sprachteilmarkierer 31 ein das Verfahren der Figur 1 benutzender Rechner. Die Nominalphrasen-Syntaxanalyse 32 ist ein das Verfahren der Figur 2 benutzender Rechner.
Die Ausgaben des Markierers 31 und der Syntaxanalyse 32 werden in einem Syntaxanalysator angewandt, um die Eingangssignale für den Absolutbetonungssignalgenerator 18 der Figur 1 des C.H. Coker et al. erteilten US- Patents Nr. 3,704,345 bereitzustellen.
Als Beispiel für die besprochenen Regeln wird die Aufmerksamkeit auf Anhang 5.1 auf Seiten 144-149 des Buches von Fudge gerichtet, in dem die Regeln für Nominalphrasen aufgeführt sind.
In anderer Hinsicht ist die Funktionsweise der Ausführungsform der Figur 3 gleich der der Ausführungsform der Figur 1 im Patent von Coker.
Gleichermaßen funktioniert in den Ausführungsformen der Figur 4 der Sprachteilmarkierer 41 wie in Figur 1 beschrieben und die Nominalphrasen-Syntaxanalyse 42 funktioniert wie in Figur 2 beschrieben.
In diesem Fall wird die Nominalphrasen- und Sprachteilinformation in dem Texteditiersystem 43 angewandt, das dem in dem F. R. Lange et al. erteilten US-Patent Nr. 4,674,065 beschriebenen entspricht. Insbesondere bietet der Sprachteilmarkierer 41 und die Nominalphrasen-Syntaxanalyse 42 einen Ersatz für den "Sprachteil"-Teil 33 im Patent von Lange et al., um bei der Erzeugung der Editieranzeigen darin behilflich zu sein. Die meinem Verfahren der Figuren 1 und 2 innewohnende Genauigkeit sollte nützlichere Editieranzeigen als im Falle des Standes der Technik ergeben.
Als Alternative kann das Texteditiersystem 43 das im Computer Science Technical Report, Nr. 91 "Writing Tools - The STYLE & Diction Programs", von L. L. Cherry et al., Februar 1981, Bell Telephone Laboratories Incorporated beschriebene System Writer's Workbench sein. Meine Verfahren würden ein Ersatz für das darin mit "PARTS" bezeichnete Verfahren sein.
Es sollte klar sein, daß verschiedene Abänderungen meiner Erfindung durchgeführt werden können, ohne von dessen Rahmen abzuweichen.
Beispielsweise würde eine Weise der Realisierung der Betonungsregeln des Buches von Fudge die mittels des von Jonathan Allen et al. in dem Buch From Text to Speech: The MIT Talk Svstem, The Cambridge University Press, Cambridge (1987) und insbesondere im Kapitel 10 "The Fundamental Frequency Generator" [Der Grundfrequenzgenerator] offenbarten Algorithmus sein.
Weiterhin sind die lexikalischen Wahrscheinlichkeiten nicht die einzigen Wahrscheinlichkeiten, die durch Glätten verbessert werden könnten. Textabhängige Häufigkeiten scheinen ebenfalls dem Gesetz von Zipf zu folgen. Das heißt, für die Menge aller Folgen von drei Sprachteilen haben wir die Häufigkeit der Folge über seinem Rang auflogarithmischem Papier aufgezeichnet und die klassische lineare Beziehung und Steigung von beinahe -1 beobachtet. Es ist klar, daß Glättungsverfahren sehr gut auf Alternativen textabhängiger Häufigkeiten angewandt werden könnten. Dasselbe läßt sich auch für die bei der Nominalphrasen-Syntaxanalyse benutzten Vorrangswahrscheinlichkeiten sagen.
Die Verfahren der vorliegenden Erfindung sind auch für andere Anwendungen wie beispielsweise Spracherkennung relevant. Textabhängige Sprachteilwahrscheinlichkeiten könnten bessere Wahlmöglichkeiten für ein zu erkennendes gesprochenes Wort ermöglichen.
Meine Verfahren können auch direkt die beschriebene Sprachteilmarkierung in dem System für die Abfrage einer Datenbank ersetzen, das in dem am 18. August 1987 C. W. Thompson et al. erteilten US-Patent Nr. 4,688,194 offenbart ist.

Claims

1. Ein automatisiertes Verfahren zur Zuweisung von Sprachteilen zu Worten in einer Nachricht, mit folgenden Schritten:

Speichern (13) von Daten in einem Rechnersystem, die für Worte relevant sind, die wahrscheinlich in der Nachricht enthalten sind, und für Anwendungen der besagten Worte als verschiedene Sprachteile, und Einsetzen von Verarbeitungsmitteln im Rechnersystem zum Auswählen (14), für jedes Wort in der Nachricht, eines wahrscheinlichen Sprachteils als Reaktion auf einen wahrscheinlichen Sprachteil für mindestens ein benachbartes Wort in der Nachricht und als Reaktion auf die besagten gespeicherten Daten, wobei das besagte Verfahren dadurch gekennzeichnet ist, daß

der Speicherschritt das Speichern von statistischen Daten in bezug auf

(1) die tatsächliche Wahrscheinlichkeit des Auftretens jedes der besagten wahrscheinlichen Worte als bestimmter Sprachteil (hiernach die lexikalische Wahrscheinlichkeit), und

(2) die tatsächlichen Wahrscheinlichkeiten des Auftretens jedes der besagten Worte als bestimmter Sprachteil, wenn sie neben Worten auftreten, die bestimmte Sprachteile sind (hiernach die textabhängige Wahrscheinlichkeit) umfaßt, und der Auswählschritt die Maximierung, für jedes Wort in der Nachricht, seiner Gesamtwahrscheinlichkeit, daß es ein bestimmter Sprachteil ist, anhand eines Optimierungsverfahrens des finiten Zustandes umfaßt, wobei das besagte Verfahren sowohl auf die gespeicherten lexikalischen Wahrscheinlichkeiten für jedes besagte Wort als auch die gespeicherten textabhängigen Wahrscheinlichkeiten für mindestens das besagte benachbarte Wort reagiert.

2 Automatisiertes Verfahren nach Anspruch 1, weiterhin mit Zuweisung von gepaarten Nominalphrasenbeginn- und -endegrenzen in der besagten Nachricht, wobei besagtes Verfahren weiterhin durch folgende Schritte gekennzeichnet ist:

Zuweisen aller möglichen Nominalphrasengrenzen, Beseitigen aller nicht gepaarten Grenzen und Optimieren von textabhängigen Nominalphrasengrenzenwahrscheinlichkeiten.

3. Automatisiertes Verfahren nach Anspruch 1, weiterhin dadurch gekennzeichnet, daß der Schritt des Speicherns von statistischen Daten das Speichern von Daten enthält, die zur Beseitigung von unwahrscheinlichen Sprachteilanwendungen geglättet worden sind, und

der Auswählschritt weiterhin die Bestimmung des Produkts der lexikalen Wahrscheinlichkeit und der textabhängigen Wahrscheinlichkeit enthält, wobei

die lexikale Wahrscheinlichkeit als der Quotient der Häufigkeit des Auftretens des Wortes als bestimmter Sprachteil, geteilt durch die Häufigkeit seines Auftretens als alle Sprachteile, geschätzt wird, und

die textabhängige Wahrscheinlichkeit durch Teilen der Trigrammhäufigkeit durch die Bigrammhäufigkeit geschätzt wird, wobei die Trigrammhäufigkeit die Häufigkeit des Auftretens des bestimmten Sprachteils in Reihenfolge mit den zwei nachfolgenden Sprachteilen, wie bereits für die zwei folgenden Worte bestimmt, ist, und die Bigrammhäufigkeit die Häufigkeit des Auftretens des bestimmten Sprachteils des nachfolgenden Wortes in Reihenfolge mit dem nächstfolgenden Sprachteil, wie bereits für das nächstfolgende Wort bestimmt, ist; und

Wiederholen des Bestimmungsschrittes für eine Anzahl möglicher Sprachteilkombinationen einschließlich des Zurückhaltens von Produkten, die vorherige Produkte für dasselbe Wort überschreiten.

4. Automatisiertes Verfahren zur Bestimmung von Beginn- und Endegrenzen von Nominalphrasen in einer Nachricht mit einer Folge von Worten, gekennzeichnet durch folgende Schritte:

Speichern von Daten in einem Rechnersystem, wobei die Daten die Wahrscheinlichkeit des Auftretens von Nominalphrasengrenzen zwischen den besagten Worten betreffen, und in Verarbeitungsmitteln im Rechnersystem, Durchführen der Schritte des Zuweisens (22) von allen möglichen Nominalphrasengrenzen, Beseitigen (23) von allen nicht paarigen Grenzen und Auwählen (24) von optimalen Wahlmöglichkeiten für die besagten Grenzen unter Benutzung von textabhängigen Nominalphrasengrenzenwahrscheinlichkeiten auf Grundlage der besagten gespeicherten Daten.

5. Automatisiertes Verfahren nach Anspruch 1 oder 4, dadurch gekennzeichnet, daß

der besagte Speicherschritt das Speichern von Informationen betreffend die gemeinsame Häufigkeit des Auftretens von Sprachteilen bei Gruppen nahegelegener Worte umfaßt,

weiterhin dadurch gekennzeichnet, daß der besagte Auswählschritt das Zuweisen von Sprachteilen in der Nachricht durch N-Grammanalyse in bezug auf die Sprachteile nahegelegener Worte umfaßt, einschließlich folgender Schritte:

Darstellen von gewissen Nichtworten als Worte mit empirisch bestimmten Häufigkeiten des Auftretens in einer nichtsprachlichen Aufzeichnung der Nachricht,

Berechnen einer optimalen normalisierten textabhängigen Wahrscheinlichkeit, daß jedes andere nahegelegene Wort in der Nachricht ein bestimmter Sprachteil im Verhältnis zu den textabhängigen Sprachteilwahrscheinlichkeiten unterschiedlicher Anwendungen der besagten Nichtworte ist, wobei die normalisierte textabhängige Wahrscheinlichkeit die Trigramm-Sprachteilwahrscheinlichkeit, geteilt durch die Bigramm-Sprachteilwahrscheinlichkeit, ist, die alle durch Beginnen am Ende eines Satzes, einschließlich von Leerstellen, bestimmt werden, umfaßt.

6. Automatisiertes Verfahren nach Anspruch 1 oder Anspruch 3, weiterhin dadurch gekennzeichnet, daß

der Speicherschritt das Speichern von statistischen Daten in bezug auf:

(1) die tatsächliche Wahrscheinlichkeit des Auftretens jedes von gewissen Zeichen, die Nichtworte wie beispielsweise Interpunktion und vor und nach Sätzen auftretende zusätzliche Leerstellen sind, (die lexikalische Wahrscheinlichkeit), und

(2) die tatsächlichen Wahrscheinlichkeiten des Auftretens jedes der besagten Zeichen, wenn sie neben Worten auftreten, die besondere Sprachteile sind, oder neben anderen Zeichen auftreten, (die textabhängige Wahrscheinlichkeit) enthält, und der Auswählschritt die Zeichen so behandelt, als wenn sie Worte wären.