• ist effektiv auf großen Korpora und Korpora mit fehlerhaften Daten.

• läuft in linearer Zeit.

• kann mit direkter Repräsentation des Textes arbeiten: ein Dokument wird als geordnete Liste von Zeichen/tokens repräsentiert. Es ist nicht nötig als Vorbereitungsstufe, ein Features Set aus dem Korpus zu extrahieren.

• nimmt Rücksicht nicht nur darauf, wie die An/Abwesenheit des Wortes in d den Prozeß der Textkategorisierung beeinflußt, sondern erlaubt auch dem Kontext, seinen Einfluß auf die Klassifizierung zu nehmen. Etwas kompliziertere Features als An/Abwesenheit w in d werden genommen, solche die das Vorkommen des Wortes in einer kontextuelle Umgebung überprüfen. Die technische Herausforderung dieses Zieles besteht darin, daß man aus einer potentiell unendlichen Menge der möglichen Features nur diejenigen nehmen muß, die wirklich von Nutzen sind.

Ein Kontext von einem Wort w_i für den Ripper besteht aus einer (normaler Weise kleiner) Anzahl anderer Wörter (w₂......w_k), die im gleichen Dokument d auch an beliebiger Stelle vorkommen:
 

• Kontexte werden von dem Algorithmus  selber bestimmt. Es gibt weder Vorbereitungsselektion der Wörterkombination, noch von außen bestimmte Konzepte, was als Kontext betrachtet werden soll. Statt dessen werden die Kontexte als ein Nebenprodukt der Suche nach optimalen Predictiv –Classifier kreiert.

• Der Ripper versucht, eine einfache Hypothese dadurch zu finden, daß er die obige Konjunktion disjunktiert, so daß eine möglichst kleine Anzahl von Disjunktionen die Daten möglichst sorgfältig sortiert. Um dieses Ziel zu erreichen, werden einige heuristische Methoden verwendet.

Der vom Ripper erzielte Classifier ist ein Regelset wie z.B.:

(das Wort irelandin d vorkommt) oder
(das Wort iraund das Wortkilledin d vorkommen) oder
.
.
.
(das Wort ira unddas Wort shot in d vorkommen) oder
(das Wort iraund das Wort outin d vorkommen)

Diese Regelsets sind kompakt und einfach für die menschliche Wahrnehmung.

Solche unkomplizierte greedy (starre) Algorithmen produzieren oft Regelsets mit zu hoher Fehlerrate oder sogar fehlerfreie Algorithmen werden ineffizient bei großen noisy Daten. Das alles bedingt die Komplexität des Rs Algorithmus.

- Greedy process: erzeugt das anfängliche Regelset
- Optimierungsprozeß: das Regelset wird verbessert, der Algorithmus wird kompakter gemacht. Seine Sorgfältigkeit und Richtigkeit steigern.

Stufe I (Generierung des anfänglichen Regelsets)

Die erste Stufe vom Ripper ist eine Variante vom Rs Vorfahr- Algorithmus: IREP (Incremental Reduced Error Prunning). Es ist ein "set-covering" (Set- deckender) Algorithmus, der die Regeln eine nach der anderen erzeugt. Der Ripper durchsucht den Korpus und löscht aus der aktuellen Suche alle Dokumente, die mit der aktuellen Regel korrelieren (positiv oder negativ). Die heuristische Methoden dahinter zielen darauf, daß mehrere positive und wenige negative Beispiele (in unserem Fall Dokumente) durch die Regel entdeckt werden.

Um eine neue Regel zu produzieren, werden noch nicht gecheckte Dokumente im Korpus willkürlich in 2 Subsets geteilt:

"Growing Set" (2/3) und "Prunning Set" (1/3). Der IREP- Algorithmus läßt die Regel zuerst wachsen (grows a rule) und danach kürzt er (pruns a rule) die Konditionen, die die Leistung der Regeln nicht mehr steigern:
 

RULE = Cond₁ + Cond₂ + Cond₃ +..............+ Cond_k

^{¬¾¾¾¾¾¾ PRUN}

"Information Gain" wird folgendermaßen definiert:

T⁺_i (bzw. T^–_i) ist die Anzahl der positiven (negativen) Beispielen im Growing Set, die von der Regel r_jgedeckt sind_.

Information Gain unterstützt die Regel r_i+1. Als Folge wird die Dichte der positiven Regel erhöht. Dieses greedy Wachstum (Einfügen der neuen Konditionen zur Regel) geht bis zum Punkt, wenn die Regel keine negativen Beispiele (Dokumente) im Growing Set mehr entdeckt oder keine Kondition mehr positives Information Gain hat.

Nach dem Growing wird eine Regel vereinfacht (pruned). Das ist auch ein greedy Prozeß: mit jedem Schritt i wird ein Pruning Operator verwendet: entweder wird eine Konditionsfolge am Ende der Regel r_i gelöscht, oder eine ganze Regel wird eliminiert. Motivation: Senkung der Anzahl von Fehlern (der falschen positiven Beispiele).

Das Ziel ist die Maximierung von folgender Funktion:

U^+_i+1(bzw. U^–_i+1) ist die Anzahl der positiven (negativen) Beispiele im Pruning Set, die von einer neuen Regel erfaßt wird. Pruning hört dann auf, wenn weitere Eliminierungen zur Erhöhung der Fehlerrate im Pruning Set führen würden. Nach dem Pruning wird die gekürzte (pruned) Regel zum Regelset addiert und die von ihr erfaßten Beispiele werden gelöscht.
 

Die Grundidee: das beste Modell unter gegebenen Datensets ist immer dasjenige, das am kürzesten verschlüsselt werden kann. Die Datenverschlüsselung geschieht in 2 Schritten: zuerst wird das Modell verschlüsselt und dann werden auch seine Fehler verschlüsselt. Nachdem alle Modelle kodiert wurden, wird das beste gewählt: dasjenige mit der kleinsten Beschreibungslänge (smallest descripton length) – die kleinste Anzahl der Bits, die man für das Encoding braucht.

IREP: Immer wenn eine Regel zum Regelset addiert wird, wird auch die total description length vom Regelset berechnet. IREP hört auf, die Regeln zu addieren, wenn diese Beschreibungslänge 64 Bit größer als die kleinste Beschreibungslänge ist, die zu dem Moment bekannt ist, oder falls es keine positiven Beispiele mehr gibt. Das Regelset wird danach so komprimiert, daß alle Regel durchgegangen werden, angefangen mit der letzten addierten Regel. Jede Regel, die die Beschreibungslänge erhöht, wird gelöscht.

Stufe II (Optimierung des Regelsets)

Danach wird eine Entscheidung getroffen, welche der drei (Original: r, Replacement: r‘, Revision: r^) im endgültigen Regelset bleibt. Es wird wieder mit der MDL-Heuristik gemacht: die Variante, die nach der Kompression die kleinste Beschreibungslänge hat, wird genommen.
Nach der Optimierung kann die Regel weniger positive Bespiele entdecken als vorher, deswegen wird die IREP (Generierungsstufe) wieder aufgerufen, um die nicht erfaßten positiven Beispiele zu finden und alle neue Regeln, die dabei generiert würden, zum Regelset addiert werden.
Die Optimierungsstufe kann man mehrmals aufrufen, als Default wird dieses zwei mal gemacht.

RIPPER und Textkategorisierung

• Loss ratio (Verlustratio): bedeutet Korrelation zwischen Gewicht von falschen negativen Beispielen und Gewicht von falschen positiven Beispielen.  Die richtige Manipulation von Gewichten in Pruning- und Optimierungsstufen verbessert Ergebnisse auf unsichtbaren Daten. 
• Ursprünglich sollte der Ripper nur ein Regelset von Boolean Features konstruieren können. Das bedeutet, daß man für jedes Wort w_i, das im Korpus vorkommt (Matrix m × n:  m Dokumenten mit insgesamt n Wörtern), ein Feature b_i erzeugt: den Wörtern werden boolische Werte zugewiesen: true - wenn das Wort in d vorkommt, und entsprechend false- wenn nicht. Für die Textkategorisierung ist das ungünstig, da die Dokumente verschiedene Wörter enthalten und es relativ wenig Wörter gibt, die in beliebigen Dokumenten vom Korpus vorkommen würden.

Als Attributelemente kann man auch die Phrasen und Wortstämme benutzen.
 

Für den Referat wurden die fogenden Quellen benuzt:

• William W. Cohen and Yoram Singer: Context-sensitive learning methods for text categorization           (April 21, 1998). Der Autor des Algoritmus bietet im Kapitel 2.1 eine fast ausführliche Beschreibung des Rippers an. Download in ps Format.
• Kjersti Aas and Line Eikvil: Text Categorisation: A survey (June 1999) Download in ps Format.
• William W. Cohen: Fast effective Rule induction (1995) Hier findet man die Beschreibung vom IREP-Algoritmus (der Vorfahr vom Ripper), als auch den Mechanismus von Rule Prunning. Download in ps Format.
• William W. Cohen: Learning Trees and Rules with Set-valued Features (1996). Es geht um den Prinzipien der "Set-valued Feature" Attributen. Download in ps Format.