Warning: fopen(111data/log202008141714.log): failed to open stream: No space left on device in /home/pde321/public_html/header.php on line 107

Warning: flock() expects parameter 1 to be resource, boolean given in /home/pde321/public_html/header.php on line 108

Warning: fclose() expects parameter 1 to be resource, boolean given in /home/pde321/public_html/header.php on line 113
Schnelles Merkmalsauswahlverfahren und System zur Maximalentropiemodellierung - Dokument DE112004001214T5
 
PatentDe  


Dokumentenidentifikation DE112004001214T5 03.08.2006
Titel Schnelles Merkmalsauswahlverfahren und System zur Maximalentropiemodellierung
Anmelder Robert Bosch GmbH, 70469 Stuttgart, DE;
The Board of Trustees of the Leland Stanford Junior University, Palo Alto, Calif., US
Erfinder Weng, Fuliang, Montain View, Calif., US;
Zhou, Yaqian, Shanghai, CN
Vertreter Dreiss, Fuhlendorf, Steimle & Becker, 70188 Stuttgart
DE-Aktenzeichen 112004001214
Vertragsstaaten AE, AG, AL, AM, AT, AU, AZ, BA, BB, BG, BR, BW, BY, BZ, CA, CH, CN, CO, CR, CU, CZ, DE, DK, DM, DZ, EC, EE, EG, ES, FI, GB, GD, GE, GH, GM, EP, HR, HU, ID, IL, IN, IS, JP, KE, KG, KP, KR, KZ, LC, LK, LR, LS, LT, LU, LV, MA, MD, MG, MK, MN, MW, MX, MZ, NA, NI, NO, NZ, OM, PG, PH, PL, PT, RO, RU, SC, SD, SE, SG, SK, SL, SY, TJ, TM, TN, TR, TT, TZ, UA, UG, US, UZ, VC, VN, YU, ZA, ZM, ZW, BW, GH, GM, KE, LS, MW, MZ, NA, SD, SL, SZ, TZ, UG, ZM, ZW, AM, AZ, BY, KG, KZ, MD, RU, TJ, TM, AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, FI, FR, GB, GR, HU, IE, IT, LU, MC, NL, PL, PT, RO, SE, SI, SK, TR, BF, BJ, CF, CG, CI, CM, GA, GN, GQ, GW, ML, MR, NE, SN, TD, TG, BF, BJ, CF, CG, CI, CM, GA, GN, GQ, GW, ML, MR, NE, SN, TD, TG
WO-Anmeldetag 28.06.2004
PCT-Aktenzeichen PCT/US2004/020912
WO-Veröffentlichungsnummer 2005008365
WO-Veröffentlichungsdatum 27.01.2005
Date of publication of WO application in German translation 03.08.2006
Veröffentlichungstag im Patentblatt 03.08.2006
IPC-Hauptklasse G06F 17/10(2006.01)A, F, I, 20060119, B, H, DE

Beschreibung[de]
GEBIET DER ERFINDUNG

Die vorliegende Erfindung betrifft ein Verfahren und ein System zum effizienten Auswählen von hochqualitativen Merkmalen für eine konditionale Maximalentropiemodellierung.

HINTERGRUNDINFORMATION

Die Maximalentropiemodellierung (ME-Modellierung) ist ein allgemeines statistisches Modellierungsparadigma, das in der Sprachenmodellierung und der Verarbeitung von natürlicher Sprache angewendet werden kann, um linguistisches Verhalten durch Einbringen verschiedener informativer, jeweils ein linguistisch statistisches Ereignis kodierender Merkmale aus einem Datenkörper im Rahmen konditionaler Modelle vorherzusagen. Eine solche Modellierung kann jedoch rechenintensiv sein.

Die ME-Modellierung kann in zwei Hauptaufgaben getrennt werden: einen Merkmalsauswahlprozess, der aus einem Merkmalsereignisraum eine Teilmenge von in das Modell einzuschließenden, gewünschten Merkmalen auswählt; und einen Parameterschätzungsprozess, der die Gewichtungsfaktoren für jedes ausgewählte Merkmal abschätzt. In vielen Anwendungen kann es jedoch unklar sein, welche Merkmale für eine bestimmte Aufgabe wichtig sind, so dass ein großer Merkmalsereignisraum erforderlich sein kann, um zu gewährleisten, dass wichtige Merkmale nicht fehlen. Jedoch kann das Einschließen aller oder nahezu aller Merkmale eine Datenüberanpassung bewirken, kann den Vorhersageprozess verlangsamen, und kann das sich ergebende Modell zur groß für in den Ressourcen beschränkte Anwendungen machen.

Bislang wurde in der ME-Modellierung ein stärkerer Fokus auf die Parameterabschätzung gelegt und es wurden geringere Anstrengungen hinsichtlich der Merkmalsauswahl, da sie für bestimmte Aufgaben nicht erforderlich ist, wenn die Parameterschätzalgorithmen hinreichend schnell sind. Wenn jedoch der Merkmalsereignisraum notwendigerweise groß und komplex ist, kann es wünschenswert sein, wenigstens eine Art von Merkmalsauswahl durchzuführen, um die Wahrscheinlichkeitsberechnung zu beschleunigen, die Speicheranforderungen während der Laufzeit zu vermindern, und den Zyklus der Modellauswahl während des Trainings zu verkürzen. Unglücklicher Weise kann, wenn der betrachtete Merkmalsereignisraum groß ist, die Merkmalsauswahl selbst schwierig und langsam sein, da die Gesamtheit aller möglichen Merkmalsteilmengen, aus denen zu wählen ist, übermäßig groß sein kann. Insbesondere kann die Gesamtheit aller möglichen Merkmalsteilmengen eine Größe von 2|&OHgr;| haben, worin |&OHgr;| die Größe des Merkmalsereignisraums ist.

verschiedene Techniken können angewendet werden, um die Aufgabe der Merkmalsauswahl zu erleichtern und/oder zu minimieren. Wie diskutiert in Ronald Rosenfeld, "Adaptive Statistical Language Modeling: A Maximum Entropy Approach", Doktorarbeit, Carnegie Mellon Universität, April 1994 ("Rosenfeld (1994)"); Adwait Ratnaparkhi, "Maximum Entropy Models for Natural Language Ambiguity Resolution", Doktorarbeit, Universität von Pennsylvania, 1998 ("Ratnaparkhi (1998)"); J. Reynar und A. Ratnaparkhi, "A Maximum Entropy Approach to Identifying Sentence Boundaries", Tagungsberichte der Fifth Conference on Applied Natural Language Processing 1997, Washington D.C., 16-19 ("Reynar und Ratnaparkhi (1997)"); Rob Koeling, "Chunking with Maximum Entropy Models", Tagungsberichte von CoNLL-2000 und LLL-2000, Lissabon, Portugal, 139-141 ("Koeling (2000)") kann eine einfache Zählabschneidetechnik verwendet werden, bei der nur die Merkmale ausgewählt werden, die in einem Körper oberhalb einer vordefinierten Abschneideschwelle auftreten. Wie diskutiert in Ratnaparkhi (1998) kann die Zählabschneidetechnik schnell und leicht zu implementieren sein, kann jedoch eine große Zahl redundanter Merkmale enthalten. Ein verfeinerter Algorithmus, der so genannte inkrementelle Merkmalsauswahlalgorithmus (IFS-Algorithmus), auf welchen in Adam L. Berger, Stephen A. bella Pietra und Vincent J. bella Pietra "A Maximum Entropy Approach to Natural Language Processing", Computational Linguistic, 22(1):39-71, 2000 ("Berger et al. (1996)"), Bezug genommen wird, erfordert, dass nur ein einziges Merkmal in jeder Auswahlstufe hinzu gefügt wird und dass geschätzte Parameterwerte für die in den vorigen Stufen gewählten Merkmale beibehalten werden. In dieser Hinsicht kann für jede Auswahlstufe der IFS-Algorithmus verwendet werden, um die Merkmalsausbeuten für alle zu prüfenden Merkmale (ein Maß für den Informationsgehalt der Merkmale) zu berechnen, das Merkmal mit der maximalen Ausbeute auszuwählen, und dann das Modell mit dem ausgewählten Merkmal auszuwählen.

Verglichen mit der einfachen Zählabschneidetechnik, kann der IFS-Algorithmus die Redundanz in dem ausgewählten Merkmalssatz beseitigen, jedoch kann die Geschwindigkeit des Algorithmus ein wesentlicher Punkt bei komplexen Aufgaben sein. Den Nachteil des IFS-Algorithmus realisierend, haben Adam L. Berger und Harry Printz "A Comparison of Criteria for Maximum Entropy/Minimum Divergence Feature Selection", Tagungsberichte der 3. Konferenz über empirische Methoden in der Verarbeitung natürlicher Sprachen, Granda, Spanien 1998 ("Berger und Printz" (1998)") eine &PHgr;-orthogonale Bedingung zum Auswählen von k Merkmalen zur gleichen Zeit, ohne die Qualität der ausgewählten Merkmal stark zu beeinflussen, vorgeschlagen. Obgleich diese Technik für bestimmte Merkmalssätze anwendbar sein kann, wie für Verknüpfungsmerkmale zwischen Wörtern, kann die &PHgr;-orthogonale Bedingung nicht standhalten, wenn part-of-speech (Sprachteil)-Anhängsel (POS-Anhängsel) in einer Merkmalsteilmenge vorherrschend vorhanden sind.

Stanley Chen und Ronald Rosenfeld in "Efficient Sampling and Feature Selection in Whole Sentence maximum Entropy Language Models", Tagungsberichte von ICASSP-1999, Phoenix, Arizona ("Chen und Rosenfeld (1999)") experimentierten an einer Merkmalsauswahltechnik, die einen x2-Test verwendet, um zu prüfen, ob ein Merkmal in das ME-Modell eingeschlossen werden sollte, wobei der x2-Test unter Verwendung der Zählungen aus einer früheren Verteilung und der Zählungen aus den echten Trainingsdaten berechnet wird. Sie kann für einige Sprachenmodellierungsaufgaben ausreichend sein. Jedoch kann ein Zusammenhang zwischen dem x2-Testergebnis und der Wahrscheinlichkeitsausbeute, die erforderlich sein kann, um das ME-Modell zu optimieren, fehlen.

Insgesamt können die bestehenden Merkmalsauswahlalgorithmen langsam sein, können Merkmale mit geringerer als optimaler Qualität auswählen, können eine nicht geringfügige Menge an manueller Arbeit beinhalten, oder können eine niedrige Reduktionsrate haben. Folglich können jene, die bestehende Merkmalsauswahlalgorithmen verwenden, einen viel kleineren oder beschränkten Merkmalsereignisraum verwenden, dem wichtige nicht entdeckte Merkmale fehlen, oder sie können ein größeres Modell erstellen, das einen zusätzlichen Bedarf an Systemspeicheranforderungen auferlegt.

Zusammenfassung der Erfindung

Die vorliegende Erfindung soll ein schnelleres Verfahren zum Auswählen hochqualitativer Merkmale für Maximalentropie (ME)-Modellierung liefern, das auf Gebieten der statistischen Modellierung und linearen Regression, die vom Sprachenverständnis und Bio-Informatik bis zu Aktienmarktvorhersagen reichen, angewendet werden kann. In dieser Hinsicht kann das schnelle Merkmalsauswahlverfahren der vorliegenden Erfindung kompakte, hochqualitative, robuste Modelle erstellen und viele zuvor unpraktische Aufgaben möglich machen.

Gemäß einem beispielhaften Merkmalsauswahlverfahren der vorliegenden Erfindung berechnet das beispielhafte Merkmalsauswahlverfahren, anstelle des Berechnens der approximativen Merkmalsausbeuten für alle zu prüfenden Merkmale in jeder Auswahlstufe, was zeitraubend für Anwendungen sein kann, die einen großen Merkmalsereignisraum erfordern, nur die approximativen Ausbeuten für die höchstrangigen Merkmale auf Basis von Modellen, die aus vorigen Merkmalsauswahlstufen gewonnen wurden. In dieser Hinsicht kann das beispielhafte Merkmalsauswahlverfahren als selektives Ausbeutenberechnungsverfahren (SGC-Verfahren) bezeichnet werden und kann eine schnellere Merkmalsauswahl liefern, ohne die Qualität der ausgewählten Merkmale zu opfern. Beispielsweise kann ein beispielhaftes SGC-Merkmalsauswahlverfahren Hundert bis Tausend Mal schneller laufen als bestehende inkrementelle Merkmalsauswahlalgorithmen (IFS-Algorithmen).

Gemäß einer beispielhaften Ausführungsform kann das SGC-Merkmalsauswahlverfahren eine "Vorausschau"-Funktionalität enthalten.

Gemäß einer weiteren beispielhaften Ausführungsform kann das SGC-Merkmalsauswahlverfahren eine Wiederbewertung der Merkmalsausbeuten von allen Merkmalen in einem vorspezifizierten Intervall enthalten.

Experimente unter Verwendung eines Finanzzeitungstests des Wall Street Journals, erhalten von der Penn Treebank, vorbereitet durch das Linguistic Data Consortium, wurden durchgeführt, um zu zeigen, dass ein beispielhaftes selektives Ausbeuteberechnungs (SGC)-Merkmalsauswahlverfahren den Merkmalsauswahlprozess signifikant beschleunigen kann, während die gleiche Qualität der ausgewählten Merkmale aufrecht erhalten wird.

Gemäß einer weiteren beispielhaften Ausführungsform kann das schnelle Auswahlverfahren Merkmale für die konditionale Maximalentropiemodellierung auswählen. In dieser Hinsicht bestimmt das beispielhafte schnelle Auswahlverfahren, anstelle des Bestimmens der approximativen Ausbeuten für alle zu prüfenden Merkmale in jeder Auswahlstufe, nur die approximativen Ausbeuten für die höchstrangigen Merkmale basierend auf den aus den vorigen Stufen erhaltenen Modellen. Das beispielhafte schnelle Auswahlverfahren kann auch eine Vorausschau-Funktionalität enthalten, um die Qualität der ausgewählten Merkmale zu bestätigen. Bei einem gegebenen Merkmalsraum der Größe F verwendet das beispielhafte schnelle Auswahlverfahren nur O(F) mehr Raum als ein Ansatz, der approximative Ausbeuten für alle zu prüfenden Merkmale in jeder Auswahlstufe bestimmt.

Ein beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei Ausbeuten für zu prüfende Merkmale während einer Initialisierungsstufe bestimmt und Ausbeuten nur für höchstrangige Merkmale während jeder Merkmalsauswahlstufe bestimmt werden, die zu prüfenden Merkmale in einer geordneten Liste basierend auf den bestimmten Ausbeuten angeordnet, ein höchstrangiges Merkmal in der geordneten Liste mit einer höchsten Ausbeute ausgewählt wird, und ein Modell unter Verwenden des höchstrangigen Merkmals angepasst wird.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei die Ausbeuten für die zu prüfenden Merkmale, welche in einer vorigen Merkmalsauswahlstufe bestimmt wurden, als obere Grenzausbeuten der verbleibenden Prüf-Merkmale in einer aktuellen Merkmalsauswahlstufe wieder verwendet werden.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei das höchstrangige Merkmal ausgewählt wird, wenn seine bestimmte Ausbeute größer ist als die oberen Grenzausbeuten der restlichen Prüf-Merkmale.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei das höchstrangige Merkmal ausgewählt wird, wenn eine Ausbeute des unter Verwendung eines aktuell angepassten Modells bestimmten höchstrangigen Merkmals größer ist als die Ausbeuten der restlichen Prüf-Merkmale, welche unter Verwendung eines zuvor angepassten Modells bestimmt werden.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei die Ausbeuten für eine vordefinierte Anzahl von höchstrangigen Merkmalen in jeder Merkmalsauswahlstufe bestimmt werden.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei Ausbeuten aller restlichen Prüf-Merkmale in einer vordefinierten Merkmalsauswahlstufe wieder bewertet werden.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei nur die nichtnormalisierten konditionalen Wahrscheinlichkeiten, die einer Menge von ausgewählten Merkmalen genügen, modifiziert werden.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei Ausbeuten von Prüf-Merkmalen unter Verwendung einer einheitlichen Verteilung berechnet werden, die Prüf-Merkmale in einer geordneten Liste basierend auf den berechneten Ausbeuten angeordnet werden, ein höchstrangiges Merkmal mit einer höchsten Ausbeute in der geordneten Liste ausgewählt wird, ein Modell unter Verwendung des ausgewählten höchstrangigen Merkmals angepasst wird, das höchstrangige Merkmal aus der geordneten Liste entfernt wird, so dass ein nächstrangiges Merkmal in der geordneten Liste das höchstrangiges Merkmal wird, eine Ausbeute des höchstrangigen Merkmals unter Verwendung des angepassten Modells berechnet wird, und die Ausbeute des höchstrangigen Merkmals mit einer Ausbeute des nächstrangigen Merkmals in der geordneten Liste verglichen wird. Wenn die Ausbeute des höchstrangigen Merkmals niedriger ist als die Ausbeute des nächstrangigen Merkmals wird das höchstrangige Merkmal in der geordneten Liste repositioniert, so dass das nächstrangige Merkmal das höchstrangige Merkmal wird und eine Reihenfolge der geordneten Liste beibehalten wird und die Schritte des Berechnens der Ausbeute des höchstrangigen Merkmals, Vergleichen der Ausbeute des höchstrangigen Merkmals mit der Ausbeute des nächstrangigen Merkmals wiederholt werden. Die gesamten Nicht-Initialisierungsschritte werden wiederholt bis eine Menge von ausgewählten Merkmalen einen vordefinierten Wert übersteigt oder eine Ausbeute eines zuletzt ausgewählten Merkmals unter einen vordefinierten Wert fällt.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei der Schritt des Berechnens der Ausbeute des höchstrangigen Merkmals das Berechnen der Ausbeute einer vordefinierten Anzahl von höchstrangigen Merkmalen enthält.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei die Ausbeuten aller verbleibenden Merkmale in einer vordefinierten Merkmalsauswahl wieder bewertet werden.

Ein weiteres beispielhaftes Verfahren der vorliegenden Erfindung ist auf das Auswählen von Merkmalen für die Maximalentropiemodellierung gerichtet, wobei die Ausbeuten eines Großteils der Prüf-Merkmale, welche in jeder Merkmalsauswahlstufe verbleiben, basierend auf dem in einer vorigen Merkmalsauswahlstufe angepassten Modell, wieder verwendet werden.

Eine weitere beispielhafte Ausführungsform der vorliegenden Erfindung ist auf ein Verarbeitungsanordnungssystem zum Durchführen einer Maximalentropiemodellierung gerichtet, wobei ein oder mehrere aus einem Datenkörper abgeleitete Prüf-Merkmale in ein Modell eingebracht werden, das ein linguistisches Verhalten vorhersagt, wobei das System eine Ausbeuteberechnungsanordnung zum Bestimmen von Ausbeuten für die Prüf-Merkmale während einer Initialisierungsstufe und zum Berechnen von Ausbeuten nur für höchstrangige Merkmale während einer Merkmalsauswahlstufe, eine Merkmalsrangeinstufungsanordnung zum rangmäßigen Einstufen von Merkmalen basierend auf der bestimmten Ausbeute, eine Merkmalsauswahlanordnung zum Auswählen eines Merkmals mit einer höchsten Ausbeute und eine Modellanpassungsanordnung zum Anpassen des Modells unter Verwendung des ausgewählten Merkmals enthält.

Eine weitere beispielhafte Ausführungsform der vorliegenden Erfindung ist auf ein Verarbeitungsanordnungssystem zum Durchführen einer Maximalentropiemodellierung gerichtet, wobei die Merkmalsrangeinstufungsanordnung zum Wiederverwenden von Ausbeuten restlicher Prüf-Merkmale, bestimmt in einer vorigen Merkmalsauswahlstufe unter Verwendung eines zuvor angepassten Modells, konfiguriert ist.

Eine weitere beispielhafte Ausführungsform der vorliegenden Erfindung ist auf ein Verarbeitungsanordnungssystem zum Durchführen einer Maximalentropiemodellierung gerichtet, wobei die Ausbeuteberechnungsanordnung zum Bestimmen von Ausbeuten für höchstrangige Merkmale in aufsteigender Reihenfolge von einem höchsten zu einem niedrigsten bis ein höchstrangiges Merkmal angetroffen wird, dessen zugehörige Ausbeute basierend auf einem aktuellen Modell größer als die Ausbeuten der restlichen Prüf-Merkmale ist, konfiguriert ist.

Eine weitere beispielhafte Ausführungsform der vorliegenden Erfindung ist auf ein Verarbeitungsanordnungssystem zum Durchführen einer Maximalentropiemodellierung gerichtet, wobei die Ausbeuteberechnungsanordnung zum Bestimmten von Ausbeuten für eine vordefinierte Anzahl von höchstrangigen Merkmalen in jeder Merkmalsauswahlstufe konfiguriert ist.

Eine weitere beispielhafte Ausführungsform der vorliegenden Erfindung ist auf ein Verarbeitungsanordnungssystem zum Durchführen einer Maximalentropiemodellierung gerichtet, wobei die vordefinierte Anzahl von höchstrangigen Merkmalen 500 ist.

Eine weitere beispielhafte Ausführungsform der vorliegenden Erfindung ist auf ein Verarbeitungsanordnungssystem zum Durchführen einer Maximalentropiemodellierung gerichtet, wobei die Ausbeuten von allen Prüf-Merkmalen, die in einer vordefinierten Merkmalsauswahlstufe übrig bleiben, wieder bewertet werden.

Eine weitere beispielhafte Ausführungsform der vorliegenden Erfindung ist auf ein Speichermedium mit einer Menge von durch einen Prozessor auszuführenden Befehlen gerichtet, um Prüf-Merkmale basierend auf Ausbeuten, die auf einer einheitlichen Verteilung berechnet wurden, zu ordnen, um eine geordnete Liste von Prüf-Merkmalen zu formen, ein höchstrangiges Merkmal mit einer größten Ausbeute auszuwählen, um ein Modell für eine nächste Stufe zu formen, das höchstrangige Merkmal aus der geordneten Liste von Prüf-Merkmalen zu entfernen, eine Ausbeute des höchstrangigen Merkmals basierend auf einem in einer vorigen Stufe geformten Modell zu berechnen, die Ausbeute des höchstrangigen Merkmals mit Ausbeuten von verbleibenden Prüf-Merkmalen in der geordneten Liste zu vergleichen, das höchstrangige Merkmal in dem Modell einzuschließen, wenn die Ausbeute des als höchstes eingestuften Merkmals größer als die Ausbeute des als nächstes eingestuften Merkmals in der geordneten Liste ist, wenn die Ausbeute des höchstrangigen Merkmals niedriger als irgend eine der Ausbeuten des als nächstes eingestuften Merkmals in der geordneten Liste ist, das höchstrangige Merkmal in der geordneten Liste einzufügen, so dass das als nächste eingestufte Merkmal das höchstrangige Merkmal wird und eine Reihenfolge der geordneten Liste aufrechterhalten wird, und die Schritte des Berechnens der Ausbeute des höchstrangigen Merkmals, Vergleichen der Ausbeuten des höchstrangigen und als nächstes eingestuften Merkmals bis die Ausbeute des höchstrangigen Merkmals die Ausbeuten der geordneten Prüf-Merkmale übersteigt, und Beenden des Verfahrens, wenn eines aus einer Menge von ausgewählten Merkmalen einen vordefinierten Wert erreicht und eine Ausbeute eines letzten Merkmals einen vordefinierten Wert erreicht, wiederholt werden.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

1 zeigt ein beispielhaftes Maximalentropiemodellierungssystem, welches ein selektives Ausbeuteberechnungsverfahren (SGC-Verfahren) zum Durchführen einer Merkmalsauswahl verwendet.

2 zeigt einen Pseudokode, welcher einen beispielhaften inkrementellen Merkmalsauswahlansatz (IFS-Ansatz) widerspiegelt.

3 zeigt einen Pseudokode, welcher ein beispielhaftes selektives Ausbeuteberechnungsverfahren (SGC-Verfahren) zur Merkmalsauswahl widerspiegelt.

4 zeigt beispielhafte Initialisierungsschritte gemäß dem IFS-Ansatz oder dem SGC-Verfahren.

5A zeigt beispielhafte IFS-Schritte für die Merkmalsauswahlstufe k=0.

5B zeigt beispielhafte SGC-Schritte für die Merkmalsauswahlstufe k=0.

6A zeigt beispielhafte IFS-Schritte für die Merkmalsauswahlstufe k=1.

6B zeigt beispielhafte SGC-Schritte für die Merkmalsauswahlstufe k=1.

7A zeigt beispielhafte IFS-Schritte für die Merkmalsauswahlstufe k=2.

7B zeigt beispielhafte SGC-Schritte für die Merkmalsauswahlstufe k=2.

8 zeigt ein Flussdiagramm 800, welches die beispielhaften Merkmalsauswahlschritte für den in den 4, 5A, 6A und 7A gezeigten inkrementellen Merkmalsauswahlansatz (IFS-Ansatz) beschreibt.

9 zeigt ein Flussdiagramm 900, welches die beispielhaften Merkmalsauswahlschritte für das in den 4, 5B, 6B und 7B gezeigte selektive Ausbeuteberechnungsverfahren (SGC-Verfahren) beschreibt.

10 zeigt experimentelle oder empirische Ergebnisse zum Vergleichen der Anzahl von Merkmalen, welche mit der beispielhaften Implementierung, die den IFS-Ansatz und die beispielhaften SGC- und SGC-mit-Vorausschau-Merkmal-Auswahlverfahren widerspiegelt, betrachtet werden.

11 zeigt experimentelle oder empirische Ergebnisse zum Vergleichen des Umfangs an Verarbeitungszeit, die von der, den IFS-Ansatz und das beispielhafte SGC-Merkmalsauswahlverfahren widerspiegelnden, beispielhaften Implementierung benötigt wird.

12 zeigt experimentelle oder empirische Ergebnisse zum Vergleichen der Auswahlgenauigkeit der beispielhaften Implementierung, die den IFS-Ansatz, das beispielhafte SGC-Merkmalsauswahlverfahren, das beispielhafte SGC-Merkmalsauswahlverfahren mit Vorausschau, und den einfachen Zählabschneidalgorithmus widerspiegelt.

GENAUE BESCHREIBUNG

1 zeigt ein beispielhaftes Entropiemodellierungssystem 100, welches ein selektives Ausbeuteberechnungsverfahren (SGC-Verfahren) verwendet, um eine Merkmalsauswahl durchzuführen, in dem ein oder mehrere, von einem Datenkörper 102 abgeleitete Prüf-Merkmale 103 in ein Basismodell 101 durch eine Verarbeitungsanordnung 110 eingebracht werden, um ein neues Modell 104 zum Vorhersagen linguistischen Verhaltens zu erzeugen. Der Datenkörper 102 kann zum Beispiel den Finanzzeitungstext des Wall Street Journal von der Penn Treebank, vorbereitet durch das Linguistic Data Consortium, enthalten, und das Basismodell 101 kann zum Beispiel eine einheitliche Verteilung sein.

Die beispielhafte Verarbeitungsanordnung 110 enthält eine Ausbeuteberechnungsanordnung 111 zum Bestimmen oder Berechnen der Ausbeuten aller Prüf-Merkmale 103 während der Initialisierungsstufe und der Ausbeuten nur für die höchstrangigen Merkmale während jeder Merkmalsauswahlstufe, eine Merkmalseinstufungsanordnung 112 zum Einstufen von Merkmalen in einer geordneten Liste, eine Merkmalsauswahlanordnung 113 zum Auswählen eines Merkmals, welches die höchste Ausbeute in der geordneten Liste hat, eine Modellanpassanordnung 114 zum Anpassen des Modells unter Verwendung des ausgewählten Merkmals, einen Prozessor 115 zum Durchführen von hier beschriebenen Verfahren und Berechnungen, einen Speicher 116 zum Speichern von Daten, und eine Schnittstelle 117 oder eine andere geeignete graphische Schnittstelle (GUI) zum Wechselwirken mit dem beispielhaften Entropiemodellierungssystem 100.

2 zeigt einen beispielhaften Pseudokode, der einen inkrementellen Merkmalsauswahlansatz (IFS-Ansatz) zum Auswählen von Merkmalen widerspiegelt, worin S den Satz an ausgewählten Merkmalen darstellt, I die Anzahl von Trainingsfällen darstellt, Y die Anzahl von Ausgabeklassen darstellt, und F die Anzahl von Prüf-Merkmalen oder die Größe des Prüf-Merkmalssatzes darstellt. Der beispielhafte IFS-Pseudokode kann wie folgt beschrieben werden. Angenommen, das konditionale ME-Modell nimmt die folgende Form an:

worin fj(x,y) eine Merkmalsfunktion (oder kurz Merkmal) ist, die ein bestimmtes linguistisches Ereignis beschreibt, (x,y),&lgr;j ein zugehöriges Gewicht ist, das angibt, wie wichtig das Merkmal f; für das Modell ist, Z(x) ein Normalisierungsfaktor ist, und p(y|x) die resultierende konditionale Wahrscheinlichkeitsverteilung ist, welche die Entropie maximiert – das heißt, die Wahrscheinlichkeit, welche das Modell dem Ausgang y bei Vorliegen der kontextuellen Information x zuweist.

Die den IFS-Ansatz reflektierende, beispielhafte Implementierung kann eine Approximierung vornehmen, indem angenommen wird, dass die Addition eines Merkmals f in einem exponentiellen Modell nur sein zugehöriges Gewicht &agr; beeinflusst und die zu den anderen Merkmalen gehörenden &lgr;-Werte unverändert lässt. In dieser Hinsicht spiegelt der beispielhafte IFS-Pseudokode von 2 eine Technik wider, auf welche in Joshua Goodman, "Sequential Conditional Generalized Iterative Scaling", Association for Computational Linguistics, Philadelphia, Pennsylvania, 2002 ("Goodman (2002)") Bezug genommen wird, um die Parameter in dem konditionalen ME-Training zu optimieren. Genauer wird eine Anordnung z verwendet, um die normalisierten Faktoren zu speichern, und eine Anordnung sum wird für alle nichtnormalisierten konditionalen Wahrscheinlichkeiten sum(i,y] verwendet. Somit muss man nur jene sum(i,y] modifizieren, welche f*(xi,y)=1 genügen, und Änderungen an ihren zugehörigen normalisierten Faktoren z[i] vornehmen. Die verschiedenen Werte in diesem beispielhaften IFS-Pseudokode können wie folgt berechnet oder bestimmt werden.

Sei das Folgende bezeichnet:

Dann kann das Modell durch sum(y|x) und Z(x) wie folgt dargestellt werden: P (y|x) =sum (y|x) /Z (x), worin sum (y|xi) und Z (xi) in 1 sum [i, y] bzw. z [i] entspricht.

Unter der Annahme, der ausgewählte Merkmalssatz sei S, und dass das Merkmal f aktuell betrachtet wird, wird in jeder Auswahlstufe ein Versuch gemacht, das Merkmal f auszuwählen, welches die Ausbeute der logarithmischen Wahrscheinlichkeit maximiert, worin der Gewichtungsfaktor &agr; und die Ausbeute von f durch die folgenden Schritte abgeleitet werden: Sei die logarithmische Wahrscheinlichkeit des Modells:

und die empirische Erwartung von Merkmal f:

Unter Verwendung einer Approximationsannahme, auf welche in Berger et al. (1996) Bezug genommen wird, können die nichtnormalisierte Komponente und der Normalisierungsfaktor des Modells die folgenden rekursiven Formen haben:

Die approximative Ausbeute der logarithmischen Wahrscheinlichkeit wird wie folgt berechnet oder bestimmt:

Die maximale approximative Ausbeute und ihr zugehöriges &agr; werden dargestellt als:

Die den IFS-Ansatz widerspiegelnde, beispielhafte Implementierung kann ineffizient sein, weil alle Prüf-Merkmale betrachtet werden bevor eines ausgewählt wird, und die Ausbeuten für jedes Merkmal werden in jeder Auswahlstufe wieder berechnet oder wieder bestimmt. Zusätzlich kann das Berechnen eines Parameters unter Verwendung einer iterativen Wurzelfindungstechnik, wie zum Beispiel das Newton'schen Verfahren, nicht effizient sein. Deshalb kann die Gesamtberechnung für die gesamte Auswahlverarbeitung unerwünscht teuer sein.

3 zeigt einen Pseudokode für ein beispielhaftes selektives Ausbeuteberechnungsverfahren (SCG-Verfahren) für ME-Modellierung, das verglichen mit der beispielhaften, den IFS-Ansatz widerspiegelnden Pseudokode-Implementierung von 2 eine schnellere Merkmalsauswahl liefern kann. Das beispielhafte SGC-Merkmalsauswahlverfahren kann wie folgt erklärt werden.

Sei g(j,k) die Ausbeute aufgrund des Zufügens von Merkmal fj zum aktiven Modell in der Auswahlstufe k. In Experimenten kann gezeigt werden, dass sogar dann, wenn &Dgr; (d. h. die zusätzliche Anzahl von Stufen nach Stufe k) groß ist, für die meisten j, g(j, k+&Dgr;)-g(j, k) eine negative Zahl oder höchstens eine sehr kleine positive Zahl ist. Dementsprechend kann g(j, k) verwendet werden, um die obere Grenze von g(j, k+&Dgr;) zu approximieren.

Wenn in dieser Hinsicht ein neues Merkmal zu einem Modell hinzugefügt wird, ändern sich die Ausbeuten für die anderen Merkmale vor dem Hinzufügen und nach dem Hinzufügen nicht viel. Wenn es Änderungen gibt, sollten ihre tatsächlichen Mengen im Wesentlichen innerhalb eines engen Bereichs über verschiedene Merkmale von den am höchsten eingestuften bis zu den am niedrigsten eingestuften liegen. Deshalb müssen nur die Ausbeuten von dem höchstrangigen Merkmal abwärts bis zum Erreichen des Merkmals, dessen zugehörige Ausbeute, basierend auf dem neuen Modell, größer als die Ausbeuten der restlichen Merkmale ist, berechnet und verglichen werden. Mit einigen wenigen Ausnahmen können die Ausbeuten der Mehrzahl der verbleibenden Merkmale basierend auf den vorigen Modellen wieder verwendet werden.

Wie bei der beispielhaften, einen IFS-Ansatz widerspiegelnden Pseudokodeimplementierung von 2 kann angenommen werden, dass das Hinzufügen eines Merkmals f nur seinen Gewichtungsfaktor beeinträchtigt. Weil eine einheitliche Verteilung als erstes in der anfänglichen Stufe angenommen wird, kann eine Formel in geschlossener Form für &agr;(j, 0) und g(j, 0) wie folgt abgeleitet werden.

worin &PHgr; die leere Menge und p∅ eine einheitliche Verteilung ist. Die anderen Schritte zum Berechnen oder Bestimmen der Ausbeuten und Auswählen der Merkmale sind in 3 als Pseudokode angegeben. Weil nur die Ausbeuten für eine kleine Zahl von höchstrangigen Merkmalen berechnet werden, wird dieses Merkmalsauswahlverfahren als das selektive Ausbeuteberechnungsverfahren (SGC-Verfahren) bezeichnet.

In dem beispielhaften SGC-Merkmalsauswahlverfahren wird eine Anordnung g verwendet, um die sortierten Ausbeuten und ihre zugehörigen Merkmalsindizes zu behalten. In der Praxis kann ein binärer Suchbaum verwendet werden, um die Reihenfolge der Anordnung aufrechtzuerhalten.

Anders als die beispielhafte Pseudokodeimplementierung von 2, welche den IFS-Ansatz widerspiegelt, bewertet das beispielhafte SGC-Merkmalsauswahlverfahren von 3 nicht alle Merkmale für das aktive Modell in jeder Stufe (eine einzelne Stufe entspricht der Auswahl eines einzigen Merkmals). Anfänglich werden die Merkmalskandidaten basierend auf ihren über die einheitliche Verteilung berechneten Ausbeuten geordnet. Das Merkmal mit der größten Ausbeute wird ausgewählt und formt das Modell für die nächste Stufe. In der nächsten Stufe wird die Ausbeute des höchsten Merkmals in der geordneten Liste basierend auf dem gerade in der vorigen Stufe geformten Modells berechnet. Diese Ausbeute wird mit den Ausbeuten der restlichen Merkmale in der Liste verglichen. Wenn diese neu berechnete Ausbeute immer noch die größte ist, wird dieses Merkmal hinzugefügt, um das Modell in der nächsten Stufe zu formen. Wenn die Ausbeute nicht die größte ist, wird sie in die geordnete Liste eingefügt, so dass die Ordnung aufrechterhalten wird. In diesem Fall wird die Ausbeute des nächsten höchstrangigen Merkmals in der geordneten Liste unter Verwendung des Modells in der aktuellen Stufe wieder berechnet.

Dieser Prozess kann fortdauern bis die Ausbeute des unter dem aktuellen Modell berechneten, höchstrangigen Merkmals immer noch die größte Ausbeute in der geordneten Liste hat. Dann wird das Modell für die nächste Stufe mit dem Hinzufügen dieses neu ausgewählten Merkmals erzeugt. Der gesamte Merkmalsauswahlprozess stoppt entweder wenn die Anzahl der ausgewählten Merkmale einen vordefinierten Wert in der Eingabe erreicht, oder wenn die Ausbeuten zu klein werden, um nützlich für das Modell zu sein.

Zusätzlich zu dieser ersten beispielhaften Ausführungsform des SGC-Merkmalsauswahlverfahrens können in jeder Stufe zusätzliche Ausbeuten basierend auf dem aktuellen Modell für eine vordefinierte Anzahl von in der geordneten Liste direkt nach dem Merkmal f* (erhalten in Schritt 2) aufgelisteten Merkmalen wiederberechnet werden, um zu gewährleisten, dass das ausgewählte Merkmal f* tatsächlich das Merkmal mit der höchsten Ausbeute innerhalb des vordefinierten Vorausschau-Abstands ist. Diese beispielhafte Ausführungsform kann als die Vorausschau-Version des SGC-Merkmalsauswahlverfahrens bezeichnet werden.

Die 4 bis 7 liefern einen "Schritt-zu-Schritt"vergleich der IFS- und SGC-Merkmalsauswahlverfahren von der Initialisierung durch die Stufen k=0, 1 und 2 der Merkmalsauswahl für einen beispielhaften Merkmalsereignisraum von fünf Prüf-Merkmalen f1, f2, f3, f4, f5, worin gj,k die Ausbeute von Merkmal f; in Stufe k darstellt, Mk das von der Addition des Merkmals mit maximaler Ausbeute in Stufe k sich ergebende Modell darstellt, und p∅ eine einheitliche Verteilung darstellt. Insbesondere zeigt 4 beispielhafte Initialisierungsschritte gemäß dem IFS-Ansatz oder dem SGC-Verfahren, die 5A, 6A und 7A zeigen beispielhafte IFS-Schritte in Auswahlstufen k=0, 1 bzw. 2, und die 5B, 6B und 7B zeigen beispielhafte SGC-Schritte in Auswahlstufen k=0, 1 bzw. 2.

8 zeigt ein beispielhaftes Flussdiagramm 800 von Merkmalsauswahlschritten für den in den 4, 5A, 6A und 7A gezeigten, inkrementellen Merkmalsauswahlansatz (IFS-Ansatz). In Schritt S81 werden die Ausbeuten von allen Prüf-Merkmalen berechnet. In Schritt S82 wird ein einzelnes Merkmal mit der maximalen Ausbeute ausgewählt. In Schritt S83 bleiben die Gewichtungsfaktoren des gerade ausgewählten Merkmals und aller zuvor ausgewählten Merkmale unverändert. In Schritt S84 wird das Modell unter Verwendung des gerade ausgewählten Merkmals angepasst. In Schritt S85 wird das ausgewählte Merkmal aus der Liste der Prüf-Merkmale entfernt.

9 zeigt ein beispielhaftes Flussdiagramm 900, das in der beispielhaften Verarbeitungsanordnung und in dem System von 1 verwendet werden kann und beschreibt die Merkmalsauswahlschritte für das in den 4, 5B, 6B und 7B gezeigte, selektive Ausbeuteberechnungsverfahren (SGC-Verfahren). In Schritt S91 berechnet das System die Ausbeuten von allen Prüf-Merkmalen. In Schritt S92 ordnet das System Prüf-Merkmale basierend auf ihren zugehörigen Ausbeuten, wobei zum Beispiel das Merkmal mit der höchsten Ausbeute in seinem Rang als erstes eingestuft und das Merkmal mit der niedrigsten Ausbeute in seinem Rang als letztes eingestuft wird. Die geordnete Liste kann zum Beispiel in einer Anordnung gespeichert werden, die zum Beispiel als Ausbeutenanordnung bezeichnet wird. In Schritt S93 wählt das System das höchstrangige Merkmal mit der höchsten Ausbeute. In Schritt S94 passt das System das Modell unter Verwendung des gerade ausgewählten Merkmals an. In Schritt S95 entfernt das System das ausgewählte Merkmal aus der geordneten Liste von Prüf-Merkmalen. In Schritt S96 berechnet das System die Ausbeute des höchstrangigen Merkmals in der geordneten Liste von Prüf-Merkmalen. In Schritt S97 vergleicht das System die Ausbeute des höchstrangigen Merkmals mit der Ausbeute des nächstrangigen Merkmals in der geordneten Liste von Prüf-Merkmalen. Wenn die Ausbeute des höchstrangigen Merkmals größer ist als die Ausbeute des nächstrangigen Merkmals, dann geht das SGC-Verfahren in dem System zu Schritt S93 über, andererseits, wenn die Ausbeute des höchstrangigen Merkmals niedriger ist als die Ausbeute des nächstrangigen Merkmals, geht das SGC-Verfahren in dem System zu Schritt S98 über, indem das höchstrangige Merkmal in der geordneten Liste repositioniert wird, so dass das nächstrangige Merkmal das höchstrangige Merkmal wird und die richtige Ordnung der Liste aufrecht erhalten wird – das heißt, das frühere höchstrangige Merkmal wird von der höchsten Position in der geordneten Liste basierend auf der jüngst berechneten Ausbeute zur Position seines eigentlichen Rangs verschoben. Anschließend geht das SGC-Verfahren zurück zu Schritt S96, um die Ausbeute des im Rang neu als höchstes eingestuften Merkmals in der geordneten Liste von Prüf-Merkmalen zu berechnen.

Experimente wurden durchgeführt, um die Leistung des IFS-Ansatzes und des SGC-Merkmalsauswahlverfahrens der vorliegenden Erfindung zu vergleichen.

Die ersten Experimente verwendeten eine Datenmenge {(x,y)}, abgeleitet von der Penn Treebank, vorbereitet durch das Linguistic Data Consortium, worin x ein 10-dimensionaler Vektor ist, der Wort, part-of-speech (POS)-Anhängsel und grammatikalische Beziehung-Anhängsel-Information von zwei angrenzenden Regionen umfasst. Beispiele der grammatikalischen Beziehung-Anhängsel umfassen Subjekt und Objekt mit dem rechten Bereich oder dem linken Bereich als Kopf. Die Gesamtzahl der verschiedenen grammatikalischen Anhängsel, d. h. die Größe des Ausgaberaums ist 86. Ein wenig mehr als 600000 Trainingsfälle wurden aus einem Körper des Wall Street Journal Finanzzeitungstexts, erhalten aus Sektion 02-22 der Penn Treebank, erzeugt, und der Testkörper wurde aus Sektion 23 erzeugt.

In den Experimenten wird der Merkmalsereignisraum in Teilräume, genannt Merkmalsschablonen, partitioniert, wobei nur bestimmte Dimensionen enthalten sind. Alle möglichen Kombinationen in dem 10-dimensionalen Raum zu betrachten, würde 210 Merkmalsschablonen erfordern. Um den Vergleich durchzuführen, wurde linguistisches Wissen verwendet, um nicht plausible Teilräume auszufiltern, so dass tatsächlich nur 24 Merkmalsschablonen verwendet wurden. Mit dieser Menge an Merkmalsschablonen können mehr als 1900000 Prüf-Merkmale aus den Trainingsdaten erhalten werden. Um die Experimente zu beschleunigen, was für die den IFS-Ansatz widerspiegelnde, beispielhafte Pseudokode-Implementierung erforderlich sein kann, kann ein Cut-Off von 5 verwendet werden, um den Merkmalsraum auf 191098 Merkmale zu reduzieren. Im Mittel deckt jedes Prüf-Merkmal ca. 485 Fälle ab, was 0,083% der gesamten Trainingsfallmenge ausmacht, und wird wie folgt berechnet:

Das erste Experiment verglich die Geschwindigkeit der den IFS-Ansatz widerspiegelnden, beispielhaften Pseudokode-Implementierung mit jener des beispielhaften SGC-Merkmalsauswahlverfahrens. Angenommen, die den IFS-Ansatz widerspiegelnde, beispielhafte Pseudokode-Implementierung berechnet die Ausbeuten für alle Merkmale in jeder Stufe, dann benötigt die den IFS-Ansatz widerspiegelnde, beispielhafte Implementierung O(NF) Zeit, um eine Merkmalsteilmenge der Größe N aus einer Prüf-Merkmalsmenge der Größe F auszuwählen. Im Vergleich hierzu, kann das beispielhafte SGC-Merkmalsauswahlverfahren viel weniger Merkmale (zum Beispiel im Mittel nur 24,1 Merkmale in jeder Stufe) betrachten, wenn ein Merkmal aus dem großen Merkmalsraum in diesem Experiment ausgewählt wird.

10 zeigt die mittlere Zahl von Merkmalen, für welche Ausbeuten für das beispielhafte SGC-Merkmalsauswahlverfahren, das beispielhafte SGC-Merkmalsauswahlverfahren mit "500"-Vorausschau, und die den IFS-Ansatz widerspiegelnde, beispielhafte Pseudokode-Implementierung berechnet werden. Die gemittelte Zahl von Merkmalen wird über ein Intervall von der anfänglichen Stufe bis zum aktuellen Merkmalsauswahlpunkt genommen, was die Fluktuation der Merkmalszahlen, die jede Stufe betrachtet, glätten soll. Das beispielhafte SGC-Merkmalsauswahlverfahren mit "500"-Vorausschau schaut auf eine zusätzliche feste Zahl von Merkmalen, 500 in diesem Experiment, jenseits von jenen, die von dem beispielhaften SGC-Merkmalsauswahlverfahren ohne Vorausschau-Funktionalität betrachtet werden. Das beispielhafte SGC-Merkmalsauswahlverfahren mit "500"-Vorausschau weist eine linear abnehmende Anzahl von auszuwählenden Merkmalen auf, weil die ausgewählten Merkmale nicht wieder-betrachtet werden. In 10 stoppt die den IFS-Ansatz widerspiegelnde, beispielhafte Pseudokode-Implementierung nachdem 1000 Merkmale ausgewählt sind, weil es zu lange für diesen Algorithmus braucht, um den gesamten Auswahlprozess zu beenden. Der gleiche Stopp erfolgt in 11, wie unten erklärt wird. Das beispielhafte SGC-Merkmalsauswahlverfahren mit "500"-Vorausschau berechnet im Mittel Ausbeuten für weniger Merkmale als die den IFS-Ansatz widerspiegelnde, beispielhafte Pseudokode-Implementierung. Das beispielhafte SGC-Merkmalsauswahlverfahren ohne "500"-Vorausschau-Funktionalität berechnet noch weniger.

11 vergleicht die Zeit, die von den beispielhaften SGC-Merkmalsauswahlverfahren und der den IFS-Ansatz widerspiegelnden, beispielhaften Pseudokode-Implementierung benötigt werden. Eine Linux-Workstation mit 1,6 GHz Dual-Xeon CPUs und einem 1 GB (Gigabyte) Speicher wurde verwendet, um die beiden Experimente gleichzeitig laufen zu lassen. Ausgenommen der anfängliche Teil des Kodes der ihnen gemeinsam ist, ist die Beschleunigung durch Verwenden des beispielhaften SGC-Merkmalsauswahlverfahrens viele Größenordnungen schneller als die den IFS-Ansatz widerspiegelnde, beispielhafte Pseudokode-Implementierung, und reicht von mehr als 100 zu Tausenden Male, abhängig von der Anzahl der ausgewählten Merkmale.

Um die Qualität der ausgewählten Merkmale unter Verwendung des beispielhaften SGC-Merkmalsauswahlverfahrens zu überprüfen, wurden vier Experimente durchgeführt. In dem ersten Experiment wurden alle Merkmale verwendet, um ein konditionales ME-Modell zu erstellen. In dem zweiten Modell wurde die den IFS-Ansatz widerspiegelnde, beispielhafte Pseudokode-Implementierung verwendet, um 1000 Merkmale auszuwählen. In dem dritten Experiment wurde das beispielhafte SGC-Merkmalsauswahlverfahren verwendet. In dem vierten Experiment wurde das beispielhafte SGC-Merkmalsauswahlverfahren mit "500"-Vorausschau verwendet. In dem fünften Experiment wurden die höchsten "n" häufigsten Merkmale aus den Trainingsdaten erhalten. Die prozentualen Genauigkeiten wurden auf Sektion 23 der wall Street Journal Datenmenge in der Penn Treebank berechnet. Die Ergebnisse sind in 12 aufgelistet.

Wie aus 12 offensichtlich sein kann, wenn die Modelle mehr als 3000 ausgewählte Merkmale enthalten, übersteigt die Leistung der SGC-Auswahlverfahren signifikant das Modell mit allen Merkmalen. Die schlechtere Leistung des Modells mit allen Merkmalen auf der rechten Seite des Diagramms kann auf dem Datenüberanpassungsproblem beruhen. Ferner hat der einfache Zählabschneidalgorithmus eine schlechtere Leistung als die anderen Merkmalsauswahlalgorithmen, wenn Merkmalsteilmengen mit nicht mehr als 10000 Merkmalen betrachtet werden.

Um die Ergebnisse bezüglich Genauigkeit weiter zu bestätigen, wurde ein weiteres Experiment mit Basis NP-Erkennung als Aufgabe durchgeführt. Das Experiment verwendet Sektion 15-18 des Wall Street Journal Texts als Trainingsdaten und Sektion 20 als Testdaten. Während des Experiments wurden 1160 Merkmale aus einem einfachen Merkmalsraum unter Verwendung des SGC-Merkmalsauswahlverfahrens ausgewählt, um eine Genauigkeit/Rückholung von 92,75%/93,25% zu erhalten. Die als beste berichtete ME-Arbeit umfasst Koeling (2000), die eine Genauigkeit/Rückholung von 92,84%/93,18% mit einem Cut-Off von 5 hat, und Zhou Ya-qian, Guo Yi-kun, Huang Xuan-jing, und Wu Li-de "Chinese and English Base NP Recognized by Maximum Entropy", Journal of Computer Research and Devlelopment, 40(3):440-446, Beijing, 2003 ("Zhou et al. (2003)") hat eine Leistung von 93,04%/93,31% mit einem Cut-Off von 7 erreicht und erreichte eine Leistung von 92,46%/92,74% mit 615 Merkmalen unter Verwenden der den IFS-Ansatz widerspiegelnden, beispielhaften Pseudokode-Implementierung. Obgleich die Ergebnisse aufgrund verschiedener in den obigen Experimenten verwendeter Merkmalsereignisräume nicht direkt vergleichbar sein können, können die Ergebnisse als kompetitiv bezüglich dieser besten Zahlen betrachtet werden, was angibt, dass das SGC-Merkmalsauswahlverfahren sowohl effektiv im Auswählen von hoch-qualitativen Merkmalen als auch effizient im Durchführen der Aufgabe sein kann.

ZUSAMMENFASSUNG

Ein Verfahren zum Auswählen von Merkmalen für Maximalentropiemodellierung, bei welchem die Ausbeuten für alle Prüf-Merkmale während einer Initialisierungsstufe bestimmt und Ausbeuten nur für höchstrangige Merkmale während jeder Merkmalsauswahlstufe bestimmt werden. Die Prüf-Merkmale werden in einer geordneten Liste basierend auf den bestimmten Ausbeuten im Rang eingestuft, ein höchstrangiges Merkmal in der geordneten Liste mit einer höchsten Ausbeute wird ausgewählt, und das Modell wird unter Verwenden des höchstrangigen Merkmals angepasst.


Anspruch[de]
  1. Verfahren zum Auswählen von Merkmalen für Maximalentropiemodellierung, welches Verfahren umfasst:

    Bestimmen von Ausbeuten für Prüf-Merkmale während einer Initialisierungsphase und nur für höchstrangige Merkmale während jeder Merkmalsauswahlstufe;

    Einstufen im Rang der Prüf-Merkmale in einer geordneten Liste basierend auf den bestimmten Ausbeuten;

    Auswählen eines höchstrangigen Merkmals in der geordneten Liste mit einer höchsten Ausbeute; und

    Anpassen eines Modells unter Verwenden des höchstrangigen Merkmals.
  2. Verfahren nach Anspruch 1, bei welchem die Ausbeuten der in einer vorigen Merkmalsauswahlstufe bestimmten Prüf-Merkmale als obere Grenzausbeuten verbleibender Prüf-Merkmale in einer aktuellen Merkmalsauswahlstufe wieder verwendet werden.
  3. Verfahren nach Anspruch 2, bei welchem das höchstrangige Merkmal ausgewählt wird, wenn seine bestimmte Ausbeute größer als die oberen Grenzausbeuten der verbleibenden Prüf-Merkmale ist.
  4. Verfahren nach Anspruch 1, bei welchem das höchstrangige Merkmal ausgewählt wird, wenn eine unter Verwendung eines aktuell angepassten Modells bestimmte Ausbeute des höchstrangigen Merkmals größer als die unter Verwendung eines vorher angepassten Modells bestimmten Ausbeuten verbleibender Prüf-Merkmale ist.
  5. Verfahren nach Anspruch 1, bei welchem die Ausbeuten für eine vordefinierte Anzahl von höchstrangigen Merkmalen in jeder Merkmalsauswahlstufe bestimmt werden.
  6. Verfahren nach Anspruch 1, welches ferner umfasst:

    Wiederbewerten der Ausbeuten aller verbleibenden Prüf-Merkmale in einer vordefinierten Merkmalsauswahlstufe.
  7. Verfahren nach Anspruch 1, bei welchem nur die nichtnormalisierten konditionalen Wahrscheinlichkeiten, die einer Menge von ausgewählten Merkmalen genügen, modifiziert werden.
  8. Verfahren zum Auswählen von Merkmalen für Maximalentropiemodellierung, welches Verfahren umfasst:

    a) Berechnen von Ausbeuten von Prüf-Merkmalen unter Verwenden einer einheitlichen Verteilung;

    b) Ordnen der Prüf-Merkmale in einer geordneten Liste basierend auf den berechneten Ausbeuten;

    c) Auswählen eines höchstrangigen Merkmals mit einer höchsten Ausbeute in der geordneten Liste;

    d) Anpassen eines Modells unter Verwenden des ausgewählten höchstrangigen Merkmals;

    e) Entfernen des höchstrangigen Merkmals aus der geordneten Liste, so dass ein nächstrangiges Merkmal in der geordneten Liste zu dem höchstrangigen Merkmal wird;

    f) Berechnen einer Ausbeute des höchstrangigen Merkmals unter Verwenden des angepassten Modells;

    g) Vergleichen der Ausbeute des höchstrangigen Merkmals mit einer Ausbeute des nächstrangigen Merkmals in der geordneten Liste;

    h) wenn die Ausbeute des höchstrangigen Merkmals weniger als die Ausbeute des nächstrangigen Merkmals beträgt, Repositioneren des höchstrangigen Merkmals in der geordneten Liste, so dass das nächstrangige Merkmal das höchstrangige Merkmal wird und eine Reihenfolge der geordneten Liste aufrechterhalten wird und Wiederholen der Schritte (f) bis (g); und

    i) Wiederholen der Schritte (c) bis (h) bis eines einer Menge von ausgewählten Merkmalen einen vordefinierten Wert übersteigt und eine Ausbeute eines zuletzt ausgewählten Merkmals unter einen vordefinierten Wert fällt.
  9. Verfahren nach Anspruch 8, bei welchem der Schritt (f) zum Berechnen der Ausbeute des höchstrangigen Merkmals das Berechnen der Ausbeute einer vordefinierten Anzahl von höchstrangigen Merkmalen umfasst.
  10. Verfahren nach Anspruch 8, bei welchem die Ausbeuten aller verbleibenden Merkmale in einer vordefinierten Merkmalsauswahl wiederbewertet werden.
  11. Verfahren nach Anspruch 7, bei welchem die Ausbeuten einer Mehrzahl von Prüf-Merkmalen in jeder Merkmalsauswahlstufe basierend auf einem in einer vorigen Merkmalsauswahlstufe angepassten Modell wieder verwendet werden.
  12. Verarbeitungsanordnungssystem zum Durchführen einer Maximalentropiemodellierung, bei der ein oder mehr von einem Datenkörper abgeleitete Prüf-Merkmale in ein Modell eingebracht werden, das das linguistisches Verhalten vorhersagt, wobei das System umfasst:

    eine Ausbeuteberechnungsanordnung zum Bestimmen von Ausbeuten für die Prüf-Merkmale während einer Initialisierungsstufe und zum Bestimmen von Ausbeuten nur für die höchstrangigen Merkmale während einer Merkmalsauswahlstufe;

    eine Merkmalsrangeinstufungsanordnung zum Einstufen im Rang von Merkmalen basierend auf den bestimmten Ausbeuten;

    eine Merkmalsauswahlanordnung zum Auswählen eines Merkmals mit einer höchsten Ausbeute; und

    eine Modellanpassungsanordnung zum Anpassen des Modells unter Verwenden des ausgewählten Merkmals.
  13. Verarbeitungsanordnung nach Anspruch 12, bei welcher die Merkmalsrangeinstufungsanordnung zum Wiederverwenden von in einer vorigen Merkmalsauswahlstufe unter Verwenden eines zuvor angepassten Modells bestimmten Ausbeuten von verbleibenden Prüf-Merkmalen konfiguriert ist.
  14. Verarbeitungsanordnung nach Anspruch 12, bei welcher die Ausbeuteberechnungsanordnung zum Bestimmen von Ausbeuten für höchstrangige Merkmale in aufsteigender Reihenfolge von einer höchsten zu einer niedrigsten, bis ein höchstrangiges Merkmal angetroffen wird, dessen zugehörige Ausbeute basierend auf einem aktuellen Modell größer als die Ausbeuten der verbleibenden Prüf-Merkmale ist, konfiguriert ist.
  15. Verarbeitungsanordnung nach Anspruch 12, bei welcher die Ausbeuteberechnungsanordnung zum Bestimmen von Ausbeuten für eine vordefinierte Anzahl von höchstrangigen Merkmalen in jeder Merkmalsauswahlstufe konfiguriert ist.
  16. Verarbeitungsanordnung nach Anspruch 15, bei welcher die vordefinierte Anzahl von höchstrangigen Merkmalen 500 beträgt.
  17. Verarbeitungsanordnung nach Anspruch 11, bei welcher die Ausbeuten von allen Prüf-Merkmalen, welche in einer vordefinierten Merkmalsauswahlstufe verbleiben, wiederbewertet werden.
  18. Speichermedium mit einem Satz von durch einen Prozessor ausführbaren Befehlen zum Durchführen des Folgenden:

    Ordnen von Prüf-Merkmalen basierend auf Ausbeuten, welche auf einer einheitlichen Verteilung berechnet sind, um eine geordnete Liste von Prüf-Merkmalen zu formen;

    Auswählen eines höchstrangigen Merkmals mit einer höchsten Ausbeute zum Formen eines Modells für eine nächste Stufe;

    Entfernen des höchstrangigen Merkmals aus der geordneten Liste von Prüf-Merkmalen;

    Berechnen einer Ausbeute des höchstrangigen Merkmals basierend auf einem in einer vorigen Stufe geformten Modell;

    Vergleichen der Ausbeute des höchstrangigen Merkmals mit Ausbeuten verbleibender Prüf-Merkmale in der geordneten Liste;

    Einschließen des höchstrangigen Merkmals in das Modell, wenn die Ausbeute des höchstrangigen Merkmals größer als die Ausbeute eines nächstrangigen Merkmals in der geordneten Liste ist;

    Einfügen des höchstrangigen Merkmals in der geordneten Liste, so dass das nächstrangige Merkmal das höchstrangige Merkmal wird und eine Reihenfolge der geordneten Liste aufrecht erhalten wird, wenn die Ausbeute des höchstrangigen Merkmals niedriger ist als irgendeine der Ausbeuten des nächstrangigen Merkmals in der geordneten Liste;

    Wiederholen der Schritte des Berechnens der Ausbeute des höchstrangigen Merkmals, Vergleichen der Ausbeuten der höchst- und nächstrangigen Merkmale bis die Ausbeute des höchstrangigen Merkmals die Ausbeuten des geordneten Prüf-Merkmale übersteigt; und

    Beenden des Verfahrens, wenn eines aus einer Menge von ausgewählten Merkmalen einen vordefinierten Wert erreicht und eine Ausbeute eines letzten Merkmals einen vordefinierten Wert erreicht.
Es folgen 12 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

  Patente PDF

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com