DE69814104T2

DE69814104T2 - Aufteilung von texten und identifizierung von themen

Info

Publication number: DE69814104T2
Application number: DE69814104T
Authority: DE
Inventors: Jonathan Yamron; G. Paul BAMBERG; James Barnett; S. Laurence GILLICK; A. Paul VAN MULBREGT
Original assignee: L&H Holdings USA Inc
Current assignee: L&H Holdings USA Inc
Priority date: 1997-09-09
Filing date: 1998-09-09
Publication date: 2004-04-29
Anticipated expiration: 2018-09-10
Also published as: WO1999013408A2; WO1999013408A3; US6052657A; DE69814104D1; EP1012736B1; EP1012736A2

Description

Hintergrund
Die Erfindung betrifft die Segmentierung von Themen in einem Textstrom.
Die Segmentierung von Text umfaßt das Identifizieren von Abschnitten oder Segmenten des Textes, die unterschiedliche Themen betreffen. Zum Beispiel sind Menschen darin erfahen, eine Zeitung zu überfliegen und schnell nur die Artikel herauszupicken, die für sie von Interesse sind. Auf diese Weise ist es möglich, nur einen kleinen Bruchteil des Gesamttextes zu lesen, der in der Zeitung enthalten ist. Es ist jedoch für jemanden nicht möglich, Hunderte von Zeitungen zu überfliegen, die in Dutzenden von Sprachen geschrieben sind, die interesserende Artikel enthalten könnten. Außerdem ist es sehr schwierig, Radio- und Fernsehübertragungen zu überfliegen, selbst wenn sie schon aufgezeichnet worden sind. Kurz gesagt ist es für Menschen sehr schwierig, den vollen Bereich von Informationen zu analysieren, die der ihnen potentiell zur Verfügung steht.
Einen Textstrom vorausgesetzt, in dem Wort- oder Satzgrenzen identifiziert worden sind, umfaßt die Segmentierung das Identifizieren von Punkten innerhalb des Textes, an denen Themenübergänge auftreten. Eine Herangehensweise an eine Segmentierung umfaßt die Abfrage einer Datenbank in einem Datenbanksystem. Insbesondere wird jeder Satz des Textstroms verwendet, um eine Datenbank abzufragen. Ob aufeinandertolgende Sätze dasselbe Thema betreffen, wird beruhend auf dem Zusammengehörigkeitsgrad der Ergebnisse der Abfrage für jeden Satz bestimmt. Wenn sich die Abfrageergebnisse ausreichend unterscheiden, wird eine Themengrenze zwischen die beiden Sätze eigefügt.
Eine Segmentierung kann auch durchgeführt werden, indem nach Merkmalen gesucht wird, die an Segmentgrenzen auftreten, (z. B. erscheinen Eigennamen häufig am Beginn eines Segments, während Pronomen später auftauchen) und auf das Auftreten von Wortpaaren hin kontrolliert wird. Mit jedem Wortpaar ist eine Wahrscheinlichkeit verbunden, daß, das Auftreten des ersten Wortes im Wortpaar in einer Textfolge vorausgesetzt, das zweite Wort im Wortpaar wahrscheinlich innerhalb eines festgelegten Abstandes vom ersten Wort im Wortpaar auftaucht. Mengen von Wortpaaren und zugehörigen Wahrscheinlichkeiten werden aus den Mengen von Trainingstext erzeugt, der sich mit den interessierenden Themen befaßt. Andere Textfolgen können dann unter Verwendung dieser Themeninformation segmentiert werden. Einem zusammenhängenden Textblock kann das Thema zugewiesen werden, dessen Wortpaarwahrscheinlichkeiten am besten zur Wortverteilung des Textblocks passen.
Es sind Systeme zur Bestimmung eines Themas bekannt, auf das sich Text bezieht, oder für die Klassifizierung von Text. In dem Artikel Method of Topic Processing for Co-operative Dialog Systems" von Furukawa u. a., Proceeding of 1995 IEEE International Conference on Fuzzy Systems, Yokohama, 20. März, Band 2, 20. März 1995, Seiten 843–848, IEEE wird ein System offenbart, das dazu bestimmt ist, die Benutzer-Computer-Wechselwirkung zu verbessern. Insbesondere ist das System dazu bestimmt, Themen zu identifizieren, die durch einen Benutzer aufgestellt werden, um es dem Computer zu ermöglichen, eine kooperativere Antwort bereitzustellen, als es der Fall wäre, wenn der Computer lediglich direkt auf die gestellte Frage antworten würde. Die Identifikation von Themen wird beruhend auf einer Analyse eines vorhergehenden Dialogs und auf der Bestimmung vorhergehender und vetwandter Themen erreicht. Insbesondere werden Äußerungen im vorhergehenden Dialog analysiert, um ein System bereitzustellen, durch das das Thema, mit dem eine nachfolgende Äußerung zusammenhängt, bestimmt werden kann. US 5418951 offenbart ein System zur Bestimmung eines Themas, mit dem ein Dokument und/oder die Sprache eines Dokuments zusammenhängt. Dies wird unter Verwendung von N-Grams erreicht, die nämlich vielmehr besondere Buchstabenfolgen, als herkömmlichere Schlüsselwörter bestimmen, um eine schnellere Verarbeitung zu liefern.
Die Erfindung stellt eine Technik zur Verwendung bei der Segmentierung eines Textstroms und zum Identifizieren von Themen im Textstrom (d. h. Identifizieren eines Textes, der einem spezifizierten Thema entspricht) bereit.
Die Technik setzt ein Gruppierungsverfahren ein, das als Eingabe eine Trainingstextmenge annimmt, die eine diskrete Anzahl von Berichten repräsentiert, wobei ein Bericht ein zusammenhängender Strom von Sätzen ist, die sich mit demselben Thema befassen. Der Text enthält Worte, Satzgrenzen und Berichtsgrenzen (die auch als Themenübergänge bezeichnet werden). Das Gruppierungsverfahren nimmt als Eingabe auch eine Anzeige der Anzahl der Gruppen an, die erzeugt werden sollen. Das Gruppierungsverfahren ist dazu bestimmt, den Eingangstext in die spezifizierte Anzahl von Gruppen zu trennen, wobei sich unterschiedliche Gruppen mit unterschiedlichen Themen befassen, eine einzelne Gruppe mehr als ein Thema umfassen kann, und in den meisten Fällen ein bestimmtes Thema in nur einer Gruppe erscheint. Es werden keine Themen definiert, bevor das Gruppierungsverfahren auf den Trainingstext angewendet wird. Sobald die Gruppen definiert sind, wird ein Sprachmodell für jede Gruppe erzeugt.
Erfindungsgemäß weist ein rechnergestütztes Verfahren zum Segmentieren eines Textstroms in Segmente unter Verwendung mehrerer Sprachmodelle, wobei der Textstrom eine Folge von Textblöcken umfaßt, die Schritte auf:
Bewerten der Textblöcke gegenüber den Sprachmodellen, um Sprachmodellbewertungen für die Textblöcke zu erzeugen, wobei die Sprachmodellbewertung für einen Textblock gegenüber einem Sprachmodell eine Korrelation zwischen dem Textblock und dem Sprachmodell anzeigt;
Erzeugen von Sprachmodellfolgebewertungen für unterschiedliche Folgen von Sprachmodellen, denen eine Folge von Textblöcken entsprechen kann, wobei eine Sprachmodellfolgebewertung eine Funktion der Bewertungen einer Folge von Textblöcken gegenüber einer Folge von Sprachmodellen ist;
Auswählen einer Folge von Sprachmodellen, die eine vorbestimmte Bedingung erfüllen; und
Identifizieren von Segmentgrenzen im Textstrom, die Sprachmodellübergängen in der ausgewählten Folge von Sprachmodellen entsprechen, wobei das Erzeugen von Sprachmodellfolgebewertungen aufweist:
Erzeugen mehrerer Sprachmodellfolgebewertungen für eine Teilfolge der Folge von Textblöcken;
Eliminieren schlecht bewerteter Folgen von Sprachmodellen; und
Hinzufügen eines Textblocks zur Teilfolge und Wiederholen der Erzeugungs- und Eliminierungsschritte.
Die Textblöcke können zum Beispiel Sätze, Absätze oder Äußerungen (d. h. Folgen von Worten) sein, die durch einen Spracherkenner identifiziert werden, und werden gegenüber den Sprachmodellen bewertet, um Sprachmodellbewertungen für die Textblöcke zu erzeugen. Eine Sprachmodellbewertung für einen Textblock zeigt eine Korrelation zwischen dem Textblock und dem Sprachmodell an.
Die vorbestimmten Bedingungen zur Auswahl einer Folge von Sprachmodellen können die Auswahl der Folge von Sprachmodellen mit der niedrigsten Sprachmodellfolgebewertung bevorzugen.
Eine Sprachmodellfolgebewertung für eine Folge von Sprachmodellen kann durch Summieren von Sprachmodellbewertungen für die Folge von Textblöcken erzeugt werden, die der Folge von Sprachmodellen entsprechen. Für jeden Sprachmodellübergang in der Folge von Sprachmodellen kann eine Wechselstrafe zur Sprachmodellfolgebewertung addiert werden. Die Wechselstrafe kann für jeden Sprachmodellübergang in der Folge von Sprachmodellen dieselbe sein. Sprachmodellfolgebewertungen können erzeugt werden durch Erzeugen mehrerer Sprachmodellfolgebewertungen für eine Teilfolge der Folge von Textblöcken, Eliminieren schlecht bewerteter Folgen von Sprachmodelle, Hinzufügen eines Textblocks zur Teilfolge, und Wiederholen der Erzeugungs-, Eliminierugs- und Hinzufügungsschritte. Eine schlecht bewertete Folge von Sprachmodellen kann eine Folge von Sprachmodellen mit einer Sprachmodellfolgebewertung sein, die um mehr als einen Betrag des Zurückbleibens, der gleich oder kleiner als die Wechselstrafe sein kann, schlechter als eine andere Sprachmodellfolgebewertung ist. Die Wechselstrafe kann erzeugt werden durch Auswählen eines Textstroms, für den die Anzahl der Sprachmodellübergänge bekannt ist, wiederholte Segmentierung des Textstroms in Segmente unter Verwendung mehrerer Wechselstrafen, und Auswählen einer Wechselstrafe, die zu einer Anzahl von Sprachmodellübergängen führt, die ähnlich oder gleich der bekannten Anzahl von Sprachübergängen ist.
Die Sprachmodelle können durch Gruppieren eines Trainingstextstroms in eine spezifizierte Anzahl von Gruppen und Erzeugen eines Sprachmodells für jede Gruppe erzeugt werden. Die Sprachmodelle können zum Beispiel Unigram-Sprachmodelle sein.
Die Textblöcke können gegen ein Sprachmodell bewertet werden, das einem interessierenden Thema entspricht. Segmente, die dem Sprachmodell entsprechen, das dem interessierenden Thema entspricht, können als dem interessierenden Thema entsprechend identifiziert werden.
Ein Textblock, der ein interessierendes Thema betrifft, kann unter Verwendung eines Systems identifiziert werden, das mehrere Sprachmodelle aufweist, einschließlich eines Sprachmodells für ein interessierendes Thema. Es wird ein Textstrom erhalten, der Textsegmente enthält, und die Textsegmente werden gegen die Sprachmodelle bewertet, um Sprachmodellbewertungen für die Textsegmente zu erzeugen. Ein Textsegment wird als das interessierende Thema betreffend identifiziert, wenn die Bewertung des Textsegments gegen das Sprachmodell für das interessierende Thema eine vorbestimmte Bedingung erfüllt. Die Bedingung kann sich beruhend auf der Wichtigkeit, den gesamten Text zu identfzieren, der ein interessierendes Thema betrifft, in Beziehung zur Wichtigkeit verändern, Text nicht fälschlicherweise als das interessierende Thema betreffend zu identifizieren. Wenn zum Beispiel die Identifikation des gesamten Textes wichtiger ist, kann die vorbestimmte Bedingung erfordern, daß die Bewertung des Textsegments gegenüber dem Sprachmodell für das interessierende Thema die niedrigste Bewertung unter den Bewertungen des Textsegments gegenüber den mehreren Sprachmodellen ist oder sich von der niedrigsten Bewertung um weniger als einen vorbestimmten Betrag unterscheidet. Wenn es wichtiger ist, Text nicht falsch zu identifizieren, kann die vorbestimmte Bedingung erfordern, daß die Bewertung für das interessierende Thema die niedrigste Bewertung ist und sich von der nächstniedrigen Bewertung um mehr als einen vorbestimmten Betrag unterscheidet. Der vorbestimmte Betrag kann null sein.
Unter den Vorteilen der Erfindung befinden sich einer oder mehrere der folgenden.
Ein Vorteil der Technik ist, daß sie eine Grundlage für das effiziente automatisierte Überfliegen von Text nach Themen bereitstellt, die für den Leser von Interesse sind. Dies ist besonders vorteilhaft, wenn mit großen Mengen an Text umgegangen wird, die für einen Menschen unmöglich oder untragbar kostspielig im Detail zu prüfen wären. Die Verwendung der Technik führt zu einer Zunahme der Informationsmenge, die ein menschlicher Analytiker überwachen und aufnehmen kann. Da außerdem die Themen, die durch die Technik identifiziert werden, durch einen Trainingstext definiert werden können, der durch den Benutzer bereitgestellt wird, stellt die Technik eine Flexibilität in der Wahl der zu verfolgenden Themen bereit.
Ein weiterer Vorteil ist, daß die Technik in Verbindung mit einem Spracherkennungssystem verwendet werden kann, um eine integrierte und automatisierte Themenverfolgung aufgezeichneter Sprache bereitzustellen. Durch Verwendung der Erfindung in Verbindung mit mehreren Spracherkennungssystemen, von denen jedes eine andere Sprache erkennt, kann die Erfindung verwendet werden, um aus Sprache abgeleitete Textthemen in mehreren Sprachen zu verfolgen. Dies ist besonders wichtig für Anwendungen, in denen es wünschenswert ist, fremde Übertragungen aufzuzeichnen, sie in Themen aufzubrechen und sie beruhend auf Themen zu priorisieren.
Andere Merkmale und Vorteile der Erfindung werden aus der folgenden Beschreibung einschließlich der Zeichnungen und aus den Ansprüchen deutlich werden.
Kurze Beschreibung der Zeichnungen
1 ist ein Blockdiagramm eines Themenverfolgungssystems.
2 ist ein Flußdiagramm einer Prozedur zum Segmentieren von Text in einem Textstrom.
3 ist ein Flußdiagramm einer Prozedur zur Konfiguration eines Systems, um eine Textsegmentierung durchzuführen.
4 ist ein Flußdiagramm einer Prozedur zum Segmentieren eines Testtextes. 5 ist ein Flußdiagramm einer Prozedur zum Berechnen einer Sprachmodellgeschichtsbewertung.
6 ist ein Flußdiagramm einer Prozedur zum Durchführen einer Themenverfolgung an einem Text.
Detaillierte Beschreibung
Bezugnehmend auf 1, kann ein Themenverfolgungssystem 100 Eingabe/Ausgabe- (I/O)-Vorrichtungen (z. B. ein Mikrophon 105, eine Maus 110, eine Tastatur 115 und eine Anzeige 120) und einen Allzweckcomputer 125 aufweisen, der einen Prozessor 130, eine I/O-Einheit 135 und eine Fernsehempfängerkarte 140 aufweist. Ein Speicher 145 speichert Daten und Programme, wie ein Betriebssystem 150, eine Themenverfolgungsanwendung 155, eine Spracherkennungssoftware 160, einen Gruppierungsalgorithmus 165, einen Vokabularbauer 170, und eine Segmentierungsanwendung 175. Zur Erleichterung der Erläuterung gibt die folgende Beschreibung an, daß die Softwarekomponenten Operationen ausführen, um spezifizierte Ergebnisse zu erzielen. Jedoch sollte zu verstehen sein, daß jede Komponente tatsächlich bewirkt, daß der Prozessor 130 in der spezifizierten Weise arbeitet. Zusätzlich sollte es auch zu verstehen sein, daß die Bezeichnung unterschiedlicher Softwarekomponenten zum Zwecke der Erläuterung dient und daß andere Implementierungen die Funktionen einer oder mehrerer Komponenten kombinieren können oder die Komponenten weiter unterteilen können.
Eine Kopie einer Femsehnachrichtenübertragung, die aus einem Strom von Sätzen besteht, wird zum Zwecke der folgenden Erläuterung als Testtext angenommen. Die Kopie zeigt nicht an, wo im Strom ein Bericht endet und der nächste Bericht beginnnt, oder wo der Bericht endet und ein Werbespot beginnt. Vorausgesetzt, daß jeder Bericht oder Werbespot ein einzelnes Thema abdeckt, ist es die Segmentierungsaufgabe, Themengrenzen in der Kopie zu finden, d. h. den Kopietext in diskrete Segmente zu unterteilen, wobei jedes Segment ein einzelner Bericht oder Werbespot ist. Wie unten erläutert, können auch Segmente für Themen identifiziert werden, die zu einem benutrerspezifizierten Thema passen.
Bezugnehmend auf 2, ist im allgemeinen die Segmentierung des Testtextes ein Zweischritt-Prozeß. Zuerst wird das System unter Verwendung eines Trainingstextes trainiert (Schritt 200). Danach wird der Testtext (oder ein anderer geprüfter Text) segmentiert (Schritt 205).
Eine Prozedur 300 zum Training des Systems wird in 3 dargestellt. Zuerst wird der Trainingstext empfangen (Schritt 305). Der Trainingstext weist eine Menge von Sätzen mit Themenübergängen auf, die zwischen Gruppen der Sätze angeordnet ist, ohne daß jedoch den Gruppen von Sätzen Themenidentfizierungen zugeordnet wären.
Danach wird der Gruppierungsalgonthmus 165 eingesetzt, um den Text in eine spezifizierte Anzahl von Themengruppen {c₁, c₂,..., c_n} zu unterteilen, wobei Standardgruppierungstechniken verwendet werden (Schritt 310). Zum Beispiel kann ein K- Mittelalgonthmus verwendet werden, wie er in Clustering Algonthms, John A. Hartigan, John Wiley & Sons, (1975), S. 84-112 beschrieben wird. Jede Gruppe kann Gruppen von Sätzen enthalten, die sich mit mehreren Themen beschäftigen. Jedoch werden alle Gruppen von Sätzen für ein einziges Thema dazu führen, daß sie in einer einzigen Gruppe angeordnet werden. Testergebnisse haben gezeigt, daß für Text, der aus Berichten aus nationalen Nachrichtenübertragungen besteht, die Verwendung von 100 Gruppen gute Ergebnisse liefert.
Nach dem Gruppieren des Trainingstextes wird ein Unigram- Sprachmodell Im_i (das auch als ein Gruppenmodell bezeichnet wird) für jede Gruppe c_i aufgebaut (Schritt 315). Ein Unigram- Sprachmodell für eine Gruppe zeigt die relative Häufigkeit an, mit der bestimmte Worte in der Gruppe auftreten. Es können auch anderer Arten von Sprachmodellen verwendet werden. Zum Beispiel kann ein Bigram-Sprachmodell, das die relative Häufigkeit angibt, mit der Paare von Worte zusammen auftreten, verwendet werden. Auf jeden Fall werden die Sprachmodelle unter Verwendung von Standardtechniken aufgebaut.
Für die Zwecke der folgenden Erläuterung wird angenommen, daß das System eine Menge von Testtext segmentiert, der für den Zweck erzeugt wird, das System zu beurteilen. In tatsächlichen Implementierungen kann der Text, der analysiert wird, zum Beispiel durch eine menschliche Schreibkraft oder ein Spracherkennungssystem erzeugt werden. Der Text kann Fernseh- oder Radioübertragungen oder abgefangenen Funk- oder Telefonkommunikationen entsprechen. Zum Beispiel kann, ebenfalls auf 1 bezugnehmend, der Text erhalten werden, indem Ton, wie eine Nachrichtenübertragung, durch die Antenne 105 empfangen wird. Die Spracherkennungssoftware 160 kann dann den Ton in computerlesbaren Text umwandeln und den Text im Speicher 145 des Computers 125 speichern. Zum Beispiel kann die Antenne 105 die Nachrichtenübertragung empfangen und die Übertragung in der Form eines analogen Signals zur Fernsehempfängerkarte 140 übertragen, die wiederum den Tonanteil der Übertragung durch einen Analog-Digital-(A/D)-Wandler schickt, um das analoge Signal in eine Menge digitaler Abtastwerte umzuwandeln. Unter Steuerung des Betriebssystems 150 und der Spracherkennungssoftware 160 wandelt der Prozessor 130 die Menge digitaler Abtastwerte in einer durch die Spracherkennungssoftware 160 erkannten Sprache in Text um.
4 stellt eine Prozedur 400 dar, die durch die Segmentierungsanwendung 175 verwendet wird, um Text zu segmentieren, nachdem das System trainiert worden ist. Zuerst wird zu segmentierender Text erhalten (Schritt 405). Der Text umfaßt einen Strom von Sätzen {s₁, s₂,... s_m}, wobei m die Anzahl der Sätze im Text ist. Der Text enthält keine Themeninformation oder Themengrenzen. Die Segmentierungsaufgabe ist es, aufeinanderfolgende Gruppen von Sätzen (d. h. Textsegmente), die gemeinsamen Sprachmodellen entsprechen, aus der Menge von n Sprachmodellen (Im₁, Im₂,... Im_n} zu identifizieren. Ein Sprachmodell wird jedem Satz zugewiesen, so daß das Ergebnis des Segmentierungsprozesses eine Sprachmodellgeschichte {sIm₁, sIm₂, ... sIm_n} ist, wobei sIm_i das Sprachmodell (aus der Menge der Sprachmodelle) ist, das dem Satz s_i des Textes zugewiesen wird. Da ein bestimmtes Thema im allgemeinen nur durch ein einziges Sprachmodell repräsentiert wird, ist eine implizite Themengrenze an jedem Übergang innerhalb der Sprachmodellgeschichte vorhanden. Nachdem der Text erhalten ist, wird jeder Satz im Text gegenüber den Sprachmodellen bewertet (Schritt 410), was zu Bewertungen score_i,j führt, wobei 1 <= i <= m, 1 <= j <= n ist, m die Anzahl der Sätze ist, und n die Anzahl der Gruppen ist. Mit anderen Worten ist score_i,j die Bewertung des Satzes Nummer i des Textes gegenüber dem Sprachmodell Nummer j. Tabelle 1 zeigt Beispielsatzbewertungen für einen Testtext, der zwei Sätze enthält, die in jedem von drei Sprachmodellen bewertet worden sind. Die Bewertung eines Satzes gegenüber einem Sprachmodell zeigt den Grad der Korrelation zwischen dem Textblock und dem Sprachmodell an. Der Bewertungen werden als negative logarithmische Werte erhalten, so daß niedrigere Bewertungen besser als höhere Bewertungen sind.
Tabelle 1
Die Segmentierungsanwendung 175 berechnet Sprachmodellgeschichtssummen für unterschiedliche Sprachmodellgeschichten, wobei eine Sprachmodellgeschichte eine Folge von Sprachmodellen ist, die einer Folge von Sätzen entsprechen. Eine Sprachmodellgeschichtssumme für eine Sprachmodellgeschichte ist gleich der Summe der Bewertung jedes Satz/Sprachmodell-Paares in der Sprachmodellgeschichte plus eine feste Wechselstrafe für jeden Sprachmodellübergang innerhalb der Sprachmodellgeschichte. Anstatt eine feste Wechselstrafe für alle Sprachmodellübergänge zu verwenden, kann jedem möglichen Sprachmodellübergang eine Wechselstrafe zugewiesen werden. Eine zusätzliche „Nicht-Wechsel"-Strafe kann in dem Fall eingesetzt werden, daß es keinen Sprachmodellübergang zwischen Sätzen gibt. Diese Nicht-Wechselstrafe kann sich für unterschiedliche Sprachmodelle unterscheiden, um die erwartete Länge der Textsegmente für Themen zu berücksichtigen, die mit jedem Sprachmodell verbunden sind.
Ein geeigneter Wert für die Wechselstrafe kann bestimmt werden, indem wiederholt mehrere Iterationen der Segmentierung an einer Menge Text vorgenommen werden, für den die Anzahl korrekter Themengrenzen im voraus bekannt ist. Nach jeder Iteration kann die Wechselstrafe eingestellt werden, bis die Segmentierung (Schritt 205) zur der ungefähr richtigen Anzahl von Themengrenzen führt, oder zu einer Anordnung der Themengrenzen an den ungefähr richtigen Stellen.
Tabelle 2 stellt Sprachmodellgeschichtssummen für alle möglichen Sprachmodellgeschichten dar, die mit dem Testtext in Tabelle 1 verbunden sind, wobei eine einzige Wechselstrafe von 100 und keine Nicht-Wechselstrafe verwendet wird.
Bezugnehmend auf die vierte Reihe der Tabelle 2, repräsentiert die Sprachmodellgeschichte {2, 1} eine Zuordnung des Sprachmodells Nummer 2 zum Satz Nummer 1 des Textes, und eine Zuordnung des Sprachmodells Nummer 1 zum Satz Nummer 2 des Testtextes. Die Sprachmodellgeschichtssumme für diese Sprachmodellgeschichte beträgt 210, was die Bewertung des Satzes Nummer 1 für das Sprachmodell Nummer 2 (50) plus die Bewertung des Satzes Nummer 2 für das Sprachmodell Nummer 1 (60) plus eine Wechselstrafe von 100 für den Wechsel der Sprachmodelle zwischen dem Satz Nummer 1 und dem Satz Nummer 2 repräsentiert. Wie in der fünften Reihe der Tabelle 2 gezeigt, repräsentiert die Sprachmodellgeschichte {2, 2} eine Zuordnung des Sprachmodells Nummer 2 zu den ersten und zweiten Sätzen des Textes. Die Sprachmodellgeschichtssumme für die Sprachmodellgeschichte beträgt 120, was die Bewertung des Satzes Nummer 1 für das Sprachmodell Nummer 2 (50), plus die Bewertung des Satzes Nummer 2 für das Sprachmodell Nummer 2 (70) repräsentiert. Es wird keine Wechselstrafe angewendet, da beide Sätze demselben Thema zugeordnet werden.
Bezugnehmend auf Tabelle 2, sollte dem Text eine schließliche Sprachmodellgeschichte von {2, 2} zugeordnet werden, da die Sprachmodellgeschichtssumme für die Sprachmodellgeschichte von {2, 2} das Minimum aller möglichen Sprachmodellgeschichtssummen ist, die für den Text berechnet werden.
Tabelle 2
Als nächstes weide der Testtext der Tabelle 1 mit einem zusätzlichen Satz betrachtet. Die Bewertungen für diesen neuen Testtext werden in Tabelle 3 gezeigt.
Tabelle 3
Wenn eine Wechselstrafe von 100 verwendet wird, sollte dem Testtext die Sprachmodellgeschichte {3, 1, 1} zugeordnet werden, da die Sprachmodellgeschichtssumme der Sprachmodellgeschichte {3, 1, 1} 250 ist (40 + 60 + 50 + 100), was die niedrigste Sprachmodellgeschichtssumme unter allen möglichen Sprachmodellgeschichtssummen für den Testtext ist. Es ist daher eine Sprachmodell-/Themengrenze zwischen dem Satz Nummer 1 und dem Satz Nummer 2 vorhanden. Wie in 4 gezeigt, wird dann, sobald eine Menge von Beweriungen (score_i,j) für den Text erzeugt ist (Schritt 410), ein Zeiger auf eine Liste Imh_list aller Sprachmodellgeschichten Initialisiert (Schritt 420), die bisher erzeugt wurden. Danach wird eine Variable i, die die Satz-Nummer des Satzes im Text repräsentiert, der gegenwärtig verarbeitet wird, mit einem Wert von 1 initialisiert (Schritt 430).
Die Liste der Sprachmodellgeschichten Imh_list wird so erweitert, daß sie alle möglichen Sprachmodellgeschichten für den Text bis zu und einschließlich einer Satz-Nummer i (Schritt 440) umfaßt. Zum Beispiel wird im Fall des Textes und der Sprachmodelle der Tabelle 1, wenn i = 1, Imh_list nach der Anwendung des Schrittes 430 die Sprachmodellgeschichten {1}, {2} und {3} umfassen. Entsprechend wird, wenn i = 2, Imh_list nach der Anwendung des Schrittes 430 die Sprachmodellgeschichten {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2} und {3, 3} umfassen.
Es wird dann eine Sprachmodellgeschichtsbewertung für jede Sprachmodellgeschichte Imh berechnet (Schritt 450), wie in 5 detaillierter gezeigt wird. Jede Sprachmodellgeschichte in Imh_list mit einer Sprachmodellgeschichtsbewertung, die um mehr als einen einstellbaren Betrag des Zurückbleibens größer als die Sprachmodellgeschichte mit der niedrigsten Sprachmodellgeschichtsbewertung ist, wird aus Imh_list eliminiert (Schritt 460). Wenn der Betrag des Zurückbleibens gleich der Wechselstrafe ist, wird die hoch bewertete Sprachmodellgeschichte niemals eine Bewertung über der der niedrig bewerteten Sprachmodellgeschichte haben und wird daher niemals die am besten (niedrigste) bewertete Sprachmodellgeschichte ergeben.
Wenn i nicht gleich m (die Anzahl der Sätze im Text) ist (Schritt 465), dann wird i erhöht (Schritt 470), und die Schritte 440–460 werden wiederholt. Andemfalls wird dem Text die Sprachmodellgeschichte in Imh_list mit der niedrigsten Sprachmodellgeschichtsbewertung zugeordnet (Schritt 480).
Bezugnehmend auf 5, wird eine Sprachmodellgeschichtsbewertung für eine Sprachmodellgeschichte Imh berechnet wie folgt. Zuerst werden einige lokale Variablen initialisiert (Schritt 500). Insbesondere wird die lokale Variable Imh score (die eine laufende Sprachmodellgeschichtsbewertung für die Sprachmodellgeschichte Imh hält) auf null initialisiert, eine lokale Variable j (die die Satz-Nummer des Textsatzes anzeigt, der gegenwärtig untersucht wird) wird auf eins initialisiert, und eine lokale Variable len wird auf die Länge der Sprachmodellgeschichte Imh initialisiert.
Die lokale Variable Im_num wird auf die Sprachmodell-Nummer des j-ten Eintrags in die Sprachmodellgeschichte Imh (Schritt 510) gesetzt. Der Wert von Imh_score wird dann um die Bewertung des Satzes Nummer j im Sprachmodell Nummer Im_num erhöht (Schritt 520). Die Schritte 530–560 erhöhen den Wert von Imh_score um die Wechselstrafe, falls notwendig. Insbesondere dann, wenn j = 1 (Entscheidungsschritt 530), wird niemals eine Wechselstrafe angewendet. Wenn j größer als 1 ist (Entscheidungsschritt 530), dann wird Imh_score um die Wechselstrafe erhöht (Schritt 550), wenn sich das gegenwärtige Thema (Im_num) vom vorhergehenden Thema (Imh[j-1]) unterscheidet (Entscheidungsschritt 540).
Wenn alle Sprachmodelle in der Sprachmodellgeschichte verarbeitet worden sind (Entscheidungsschritt 570), dann wird Imh score zurückgegeben (Schritt 580). Andemfalls wird j (Schritt 570) erhöht und die Schritte 510–560 werden wiederholt.
Bezugnehmend auf 6, können Segmente eines Testtextstroms, der einem bestimmten Thema entspricht, gemäß einer Prozedur 600 identifiziert werden. Zuerst gibt der Benutzer ein Thema an, indem er einen Thematext bereitstellt, der das Thema betrifft (Schritt 605). Danach wird ein Sprachmodell des Thematextes (das als das Thematext-Sprachmodell bezeichnet wird) aufgebaut, wie oben erläutert (Schritt 610).
Das System wird unter Verwendung des Trainingstextes trainiert, um die Sprachmodelle zu erzeugen, wie oben beschrieben (Schritt 620). Das Thematext-Sprachmodell wird dann zur Menge der Sprachmodelle hinzugefügt (Schritt 630).
Es wird dann ein Testtextstrom erhalten (Schritt 640). Wenn der Testtext keine Segment- (Berichis-) Grenzen enthält (Entscheidungsschritt 645), dann wird der Testtext segmentiert (Schritt 650). Jedes Segment des Testtextes wird dann in jedem der Sprachmodelle (Schritt 660) bewertet. Im Schritt 660 erzeugte Bewertungen können eine Strafe enthalten, die sich mit jedem aufeinanderfolgenden Segment erhöht, das bewertet wird. Eine solche Strafe kann zum Beispiel verwendet werden, wenn das Thema, das durch den Thematext repräsentiert wird, ein zeitspezifisches Ereignis ist (z. B. das Auftreten eines Erdbebens) und die Segmente des Testtextes von den ältesten zu den neuesten geordnet werden (z. B. ein Strom von Nachrichtenübertragungen). In einem solchen Fall spiegelt die Strafe die abnehmenden Wahrscheinlichkeit mit der Zeit wieder, daß das durch den Thematext repräsentierte Thema im Testtext vorkommen wird.
Ein Segment kann als dem Thema entsprechend identifiziert werden, das durch den Thematext definiert wird, wenn das Segment gegenüber dem Thematext-Sprachmodell besser als gegenüber irgendeinem anderen Sprachmodell bewertet wird (Schritt 670). Alternativ kann ein Segment als dem Thema entsprechend identifiziert werden, das durch den Thematext definiert wird, wenn das Segment gegenüber dem Thematext-Sprachmodell um mehr als einen vorbestimmten Betrag besser bewertet wird, als gegenüber irgendeinem anderen Sprachmodell.
Andere Ausführungsformen liegen innerhalb der Rahmens der folgenden Ansprüche. Zum Beispiel sind die hier beschriebenen Techniken nicht auf irgendeine besondere Hardware oder Software-Konfiguration beschränkt; sie können in irgendeiner Rechner- oder Verarbeitungsumgebung Anwendung finden, die zur Spracherkennung verwendet werden. Die Techniken können in Hardware oder Software oder einer Kombination der beiden implementiert werden. Vorzugsweise werden die Techniken in Computerprogrammen implementiert, die auf programmierbaren Computern ausgeführt werden, die jeweils einen Prozessor, ein Speichermedium, das durch den Prozessor lesbar ist (einschließlich einem flüchtigen und nichtflüchtigen Speicher und/oder Speicherelementen), mindestens eine Eingabevorrichtung und mindestens eine Ausgabevorrichtung aufweisen. Der Programmcode wird auf Daten angewendet, die unter Verwendung der Eingabevorrichtung eingegeben werden, um die beschriebenen funktionen auszuführen und um Ausgabeinformationen zu erzeugen. Die Ausgabeinformationen wird an eine oder mehrere Ausgabevorrichtungen angelegt. Jedes Programm wird vorzugsweise in einer prozeduralen oder objektorientierten Hochprogrammiersprache implementiert, um mit einem Computersystem zu kommunizieren. Jedoch können die Programme in Assembler- oder Maschinensprache implementiert werden, falls erwünscht. Auf jeden Fall kann die Sprache eine kompilierte oder interpretierte Sprache sein.
Jedes solche Computerprogramm wird vorzugsweise auf einem Speichermedium oder -Vorrichtung (z. B. CD-ROM, Festplatte oder Magnetdiskette) gespeichert, die durch einen programmierbaren Allzweck- oder Spezialzweckcomputer zur Konfiguration und zum Betreiben des Computers lesbar ist, wenn das Speichermedium oder -Vorrichtung durch den Computer gelesen wird, um die Prozeduren auszuführen, die in diesem Dokument beschrieben werden. Es wird auch erwogen, das System als ein computerlesbares Speichermedium zu implementieren, das mit einem Computerprogram konfiguriert ist, wobei das so konfigurierte Speichermedium bewirkt, daß ein Computer in einer spezischen und vordefinierten Weise arbeitet.

Claims

Computergestütztes Verfahren zum Segmentieren eines Stroms von Text zu Segmenten unter Verwendung einer Mehrzahl von Sprachmodellen, wobei der Strom von Text eine Sequenz von Textblöcken beinhaltet, wobei das Verfahren die folgenden Schritte umfasst: Auswerten der Textblöcke anhand der Sprachmodelle zum Generieren von Sprachmodellauswertergebnissen für die Textblöcke, wobei das Ergebnis der Sprachmodellauswertung für einen Textblock anhand eines Sprachmodells eine Korrelation zwischen dem Textblock und dem Sprachmodell anzeigt; Generieren von Sprachmodell-Sequenzauswertergebnissen für verschiedene Sequenzen von Sprachmodellen, denen eine Sequenz von Textblöcken entsprechen kann, wobei ein Sprachmodell-Sequenzauswertergebnis von den Ergebnissen der Auswertung einer Sequenz von Textblöcken anhand einer Sequenz von Sprachmodellen abhängig ist; Wählen einer Sequenz von Sprachmodellen, die eine vorbestimmte Bedingung erfüllt; und Identifizieren von Segmentgrenzen in dem Strom von Text, die Sprachmodellübergängen in der gewählten Sequenz von Sprachmodellen entsprechen, wobei das Generieren von Sprachmodell-Sequenzauswertergebnissen die folgenden Schritte umfasst: Generieren mehrerer Sprachmodell-Sequenzauswertergebnisse für eine Subsequenz der Sequenz von Textblöcken; Eliminieren von Sprachmodellsequenzen mit schlechten Auswertergebnissen; und Hinzufügen eines Textblocks zu der Subsequenz und Wiederholen der Generierungs- und Eliminierungsschritte.
Verfahren nach Anspruch 1, bei dem das Generieren eines Sprachmodell-Sequenzauswertergebnisses für eine Sequenz von Sprachmodellen das Summieren von Sprachmodellauswertergebnissen für die Sequenz von Textblöcken umfasst, die der Sequenz von Sprachmodellen entspricht.
Verfahren nach Anspruch 2, das ferner Folgendes umfasst: für jeden Sprachmodellübergang in der Sequenz von Sprachmodellen Addieren eines Schaltzusatzaufwands zu dem Sprachmodell-Sequenzauswertergebnis.
Verfahren nach Anspruch 3, bei dem der Schaltzusatzaufwand für jeden Sprachmodellübergang in der Sequenz von Sprachmodellen gleich ist.
Verfahren nach Anspruch 4, bei dem der Schaltzusatzaufwand ermittelt wird durch: Auswählen eines Stroms von Text, für den die Zahl der Sprachmodellübergänge bekannt ist; wiederholtes Segmentieren des Stroms von Text zu Segmenten mit einer Mehrzahl von Schaltzusatzaufwänden; und Wählen eines Schaltzusatzaufwands, der zu einer Anzahl von Sprachmodellübergängen führt, die der bekannten Anzahl von Sprachmodellübergängen ähnlich ist, wobei jeder Sprachmodellübergang durch Identifizieren einer Segmentgrenze in dem Strom von Text ermittelt wird.
Verfahren nach einem der vorherigen Ansprüche, bei dem: eine Sprachmodellsequenz mit einem schlechten Auswertergebnis eine Sequenz von Sprachmodellen mit einem Sprachmodell-Sequenzauswertergebnis ist, das um mehr als einen Zurückfallbetrag schlechter ist als ein anderes Sprachmodell-Sequenzauswertergebnis.
Verfahren nach Anspruch 6, bei dem: das Generieren eines Sprachmodell-Sequenzauswertergebnisses für eine Sequenz von Sprachmodellen für jeden Sprachmodellübergang in der Sequenz von Sprachmodellen das Addieren eines Schaltzusatzaufwandes zu dem Sprachmodell-Sequenzauswertergebnis umfasst; und der Zurückfallbetrag dem Schaltzusatzaufwand entspricht.
Verfahren nach einem der vorherigen Ansprüche, bei dem das Wählen einer Sprachmodellsequenz auf der Basis einer vorbestimmten Bedingung Folgendes umfasst: Wählen einer Sprachmodellsequenz mit einem Sprachmodell-Sequenzauswertergebnis, das das Minimum der berechneten Sprachmodell-Sequenzauswertergebnisse ist.
Verfahren nach einem der vorherigen Ansprüche, bei dem ein Textblock einen Satz umfasst.
Verfahren nach einem der Ansprüche 1 bis 8, bei dem ein Textblock einen Absatz umfasst.
Verfahren nach einem der Ansprüche 1 bis 8, bei dem ein Textblock eine von einem Spracherkenner identifizierte Äußerung umfasst.
Verfahren nach Anspruch 11, bei dem eine Äußerung eine Sequenz von Wörtern umfasst.
Verfahren nach einem der vorherigen Ansprüche, bei dem die Sprachmodelle erzeugt werden durch: Clustern eines Stroms von Trainingtext zu einer vorbestimmten Anzahl von Clustern; und Generieren eines Sprachmodells für jedes Cluster.
Verfahren nach einem der vorherigen Ansprüche, bei dem die Sprachmodelle Unigramm-Sprachmodelle umfassen.
Verfahren nach einem der Ansprüche 1 bis 13, bei dem die Sprachmodelle Bigramm-Sprachmodelle umfassen.
Verfahren nach einem der vorherigen Ansprüche, ferner umfassend das Auswerten der Textblöcke anhand eines Sprachmodells für ein Thema von Interesse.
Verfahren nach Anspruch 16, ferner umfassend das Identifizieren von dem Sprachmodell für das Thema von Interesse entsprechenden Segmenten als dem Thema von Interesse entsprechend.
Computerprogramm, das fassbar auf einem rechnerlesbaren Medium gespeichert ist und die Aufgabe hat, einen Computer zu veranlassen, einen Strom von Text mit Hilfe einer Mehrzahl von Sprachmodellen zu Segmenten zu segmentieren, wobei der Strom von Text eine Sequenz von Textblöcken beinhaltet, wobei das Computerprogramm Anweisungen zum Durchführen eines Verfahrens nach einem der vorherigen Ansprüche umfasst.