TextMining Flashcards
Anwendungsbereiche des Text Mining
- konzeptbasierte Suche / Finden ähnlicher Texte (Dokumenten-Management-Systeme, ähnliche Artikel, …)
- Dokumentenklassifikation und Clustering (automatische Archivierung, Workflow-Optimierung, Spamfilter)
- Informationsstrukturierung und -extraktion (Aufbau von Ontologien/Taxonomien, Name/Orte/Institutionen/Daten/Zahlen/…)
Einordnung des Text Mining
- zw. Information Retrieval und linguistischer Informatik
- inhaltlich orientierter Zugriff auf unstrukturierte Daten
Forschungsansätze
- wissensbasierte/regelbasierte Ansätze
- Mustersuche
- neuronale Netze
- statistische/korpuslinguistische Ansätze
Arten von Kookurrenzen
+ Anwendung
- Nachbarschaftskook. = unmittelbar nebeneinander
- Satzkookkurrenz
- auffällig: gemeinsames Auftreten wahrscheinlicher als Einzelwahrscheinlichkeiten vermuten ließen
-> mit Kookurrenzen lassen sich Cluster zu einem Wort bilden = Disambiguierung!
Formeln für Ähnlichkeitsmaße (Kookurrenzen)
- Tanimoto-Ähnlichkeit: Anteil Doppeltreffer bzgl. Anteil Einzeltreffer
- Mutual Information: Abweichung von statistischer Unabhängigkeit
- G-Test: Wahrscheinlichkeit simultaner seltener Ereignisse
- Poisson-Signifikanz
Tanimoto-Ähnlichkeit
(Ähnlichkeitsmaß Kookkurrenzen)
Anteil Doppeltreffer bzgl. Anteil Einzeltreffer
simT(A,B) = nAB / (nA+nB-nAB)
Mutual Information
(Ähnlichkeitsmaß Kookkurrenzen)
Abweichung von statistischer Unabhängigkeit
i(A,B) = log(nABnges / (nAnB))
[=log(pAB/(pApB))]
if A and B are independent, then pAB=(pApB) and therefore: log(pAB/(pApB)) = log 1 = 0
G-Test
(Ähnlichkeitsmaß Kookkurrenzen)
Wahrscheinlichkeit simultaner seltener Ereignisse
x = nAnB / nges
sig(A,B) = x - nAB log x + log nAB!
(für 2.5x < nAB)
Kookkurrenz-Graph mit Simulated Annealing
Benachbarte Knoten ziehen sich nach Kookurrenzstärke an, nicht benachbarte stoßen einander ab
ges.: energetisch günstigste Position der Knoten in der Ebene
- hohe Temperatur -> starke Schwingung der Knoten ->Verhinderung der Stabilisierung in lokalem Minimum
- durch wirkende Kräfte und Temp. in jedem Iterationsschritt zur optimalen Position bewegt
- Temperatur abgekühlt -> relat. Lage der Knoten stabil, nur noch Abstände optimiert
Birthday Problem + Co-occurrence Problem
Modification: What is the probability p of the existence of k couples with the same birthday - a boys and b girls randomly chosen?
-> Poisson Distribution
Poisson Signifikanz
(Ähnlichkeitsmaß Kookkurrenzen)
beruhend auf common birthday problem
λ = ab / n (=npapb)
k = Anzahl Kookkurrenzen
Eigenschaften von sig(n,k,a,b)
Poisson Signifikanz
(Ähnlichkeitsmaß Kookkurrenzen)
- einmalige Kookurrenz in sig(n,1,1,1) -> 1
- independence: sig(n,npq,np,nq) -> 0 (p,q propabilities for A,B)
- negativ: häufige Wörter, die nicht gemeinsam auftreten
- enlarging corpus by factor m: sig(mn,mk,ma,mb) = m*sig(n,k,a,b) = umso häufiger gesehen, umso mehr steigt Signifikanz (nicht bei Tanimoto/Mutual Information)
-
additivity: für k/b ~ k’/b’, unification of words B, B’:
- sig(n,k,a,b)+sig(n,k’,a,b’) ~sig(n,k+k’,a,b+b’)
- Zusammenführen von Wörtern hinterher möglich statt vorherige Lemmatisierung
- Maximum: max(B) sig(A,B) ~ a = am größen, wenn immer mit A auftritt und A möglichst selten einzeln
Zipf’sches Gesetz
- “Prinzip der geringsten Anstrengung” in natürlicher Sprache
- Wortformen eines Textes nach absteigender Häufigkeit ordnen
- Rang r einer Wortform * Häufigkeit n ~ konstant mit textabhängiger Konstante k
r * n ~k
n ~ 1/r
Zipf’sches Gesetz
- Frequenz des häufigsten Wortes (n maximal)
- Größe des Vokabulars = Anzahl der types (m=1)
Konstante c
- k ~ rmax
- k ~ r1
k steigt linear mit Korpusgröße N -> Konstante c = k/N unabhängig von Korpusgröße, aber evtl. einzelsprachenabgängig
Zipf’sches Gesetz
Abschätzung über Anzahl an Wortformen, die n mal im Text vorkommen (= rn)
- N: Gesamtanzahl aller Wortformen des Textes (tokens)
- t: Umfang des Vokabulars (types)
- rn: größter Rang der Wortformen, die genau n mal auftreten
- In: Anzahl der Wortformen, die genau n mal auftreten
rn ~ c * N/n
Zipf’sches Gesetz
Abschätzung des Zuwachses des Vokabulars, wenn sich die Textmenge erhöht (= In)
Besonderheit I1
- N: Gesamtanzahl aller Wortformen des Textes (tokens)
- t: Umfang des Vokabulars (types)
- rn: größter Rang der Wortformen, die genau n mal auftreten
- In: Anzahl der Wortformen, die genau n mal auftreten
In = rn - rn+1
= (cN/n) - (cN/(n+1))
= cN / (n(n+1))
I1 = c*N/(1+2) = t/2
Zipf’sches Gesetz
D
- exakte Herleitung ergibt n ~ (r+V)-1/D
- D = (fraktale) Dimension nahe 1, die charakteristisch für die jeweilige Sprache ist
- 1/D = Anstieg der Gerade in der doppelt-logarithmischen Darstellung und eben nur näherungsweise 1
Zipf’sches Gesetz
Korpusgröße
- unendlich viele Wörter: mit Korpusgröße steigt Anzahl an Wörtern (types) geradlinig
- auch nur endlich viele möglich: Kurve s.o. gekrümmt
Neologismen
Fragestellungen
- Neu: wann erstmalig beobachtet
- Nachhaltig: Wird man in zehn Jahren das Wort noch kennen?
- Tendenz: Wird Häufigkeit zunehmen?
- Korrelation: Wie wirkt ein Wort auf die Tendenz eines anderen?
Neologismen
Typen
- Echter Neologismus, völlige Neuschöpfung
- Tendenz wachsend oder
- Nach starkem Anfang fallende Tendenz
- Vorher niederfrequentes Wort,
- dessen Häufigkeit unaufhaltsam steigt (DVD) oder
- das plötzlich (z.B. wegen eines Ereignisses) in der Allgemeinsprache auffällt, dann fällt
- Ereignisabhängige Wörter, die in Abständen mit großer Häufigkeit auftreten (Papstwahl)
- Wort mit neuer Bedeutung (Kurzmitteilung)
- Bezeichner für Einzelobjekte oder Gruppen (Hotelerbin, Terroristenchef)
- Wörter mit kurzer Lebensdauer (UMTS-Auktion)
Clustering & Klassifikation
Unterscheidung
Cluster:
- entstehen “von selbst” aus der inneren Struktur der Daten, interpretiert als Ähnlichkeit
- Gruppen nicht vorgegeben
- Anzahl der Gruppen vorgegeben o. muss vom Algorithmus ermittelt werden.
Klassifikation: Klassen sind vorgegeben, beispielsweise durch Trainingsdaten
Clustering und Klassifikation
Maschinelles Lernen
- Funktion f: M → {0, 1 , …, n-1}, die jedem Element x∈M seine Klasse f(x) zuordnet
- f unüberwacht gelernt = Clustering: Bekannt sein kann die Anzahl n der Klassen,Aufteilung kann nur über Ähnlichkeit der Attribut-Werte gelernt werden
- f überwacht lernen = Klassifikation: f ist auf Teil der Menge M bekannt und soll für restlichen Teil ermittelt werden
Clustering und Klassifikation
Anforderungen an Unterteilung
- Homogenität innerhalb der Cluster
- Heterogenität zwischen verschiedenen Clustern
Clustering
Darstellungsform
Dendrogramm
- Cluster werden zu Instanzen, die wieder mit verarbeitet werden
- Cluster können zu größeren Clustern zusammengefasst werden
- zeigt Beziehungen zwischen Clustern mit an
Clustering
Unterschiede bei Algorithmen/Modellen
- Cluster disjunkt o. überlappend
- Verfahren deterministisch o. probabilistisch
- Cluster hierarchisch o. nicht
- Algorithmus lernt inkrementell o. nur global
Hierarchisches Clustering
-
bottom up:
- Start mit Clustern aus je einem Objekt
- jeweils benachbarte Cluster verschmelzen
-
top down: meist sehr schnell
- zerlege Gesamtmenge in zwei Cluster.
- wiederholt auf den entstandenen Clustern ausführen
Clustering
Abstand zwischen Clustern bei verschiedenen Attributarten berechnen
- numerisches Attribut: Differenz der Werte
- mehrere numerische Attribute: normiere die Attribute & wähle Euklidischen Abstand
- Nominale Attribute: Abstand 0 oder 1 je nachdem, ob die Werte gleich oder verschieden sind
- Cluster durch eines seiner Elemente oder durch ein fiktives Element (Zentroid) vertreten
- Single Link: Abstand zw. 2 Clustern = min. Abstand zwischen 2 Elementen der versch. Cluster
- Zentroid: fiktives Element mit Mittelwert der (numerischen) Attribute der Elemente
Clustering
k-means-Algorithmus
- Daten werden vom Algorithmus in vorgeg. Anzahl von k Clustern geteilt
- Initialisierung: k Clusterzentren werden zufällig gewählt
- Zuordnung: Instanzen werden jeweils Cluster mit dem nächstgelegenen Clusterzentrum zugeordnet.
- Zentroid: Zentroiden der so entstandenen Cluster werden als neue Clusterzentren benutzt.
- Schleife: Gehe zu 2, solange sich noch Zuordnungen einzelner Elemente zu Clustern ändern.
Clustering
k-means-Algorithmus
Probleme + Lösung
- Konvergenz ist nicht gesichert.
- Konvergenz verläuft nur zu einem lokalen Minimum, nicht unbedingt zum globalen Minimum -> Clustering muss nicht optimal sein
- Lösung: Algorithmus mehrfach starten.
Clustering
CobWeb
Idee, Vorgehen, Nachteil
- inkrementelles Clustering: sukzessive Dendrogramm aufbauen
- Start: leerer Baum -> Instanzen nacheinander an der am besten passenden Stelle einfügen
- möglich: Umstrukturierung nach Einfügeschritt
- Maß für „am besten passenden Stelle“ ist Kategoriennützlichkeit
- Nachteil: entstehende Clustering kann von Reihenfolge abhängen
Clustering
CobWeb
Einfügeschritt
- Auswahl nach größter Kategoriennützlichkeit
- bei Einfügen getestet:
- Hinzufügen zu bestehenden Cluster
- Anlegen neues Cluster mit nur dieser Instanz
- wenn Hinzufügeschritt -> zusätzlich Verschmelzungsschritt und Aufteilungsschritt für Cluster, in das hinzugefügt wurde testen -> ausführen, falls Kategoriennützlichkeit verbessert
- Verschmelzungsschritt: verschmolzen mit zweitbesten Cluster, zu dem sie „beinahe hinzugefügt worden wäre“.
- Aufteilungsschritt: Instanzen eine Hierarchiestufe höher als einzelne, neue Cluster gewählt
Evaluierung
einfache Lösungen
- auf Trainingsdaten testen = kein guter Indikator
- Aufteilung in Test- und Trainingsdaten, aber:
- bestimmte Daten sind von ihrer Natur her beschränkt, z.B. Aussagen über Feiertage, 29. Februar
- Datenqualität ist häufig von Experten abhängig, sind knapp
Evaluierung
statistische Tests: Messungen
- bei Klassifikation
- Anzahl der korrekten Klassifizierungen
- Genauigkeit von Wahrscheinlichkeitsvorhersagen
- Genauigkeit von numerischen Vorhersagen
- Kosten
Klassifizierung: Fehllerate
Evaluierung
Holdout-Methode
Problem+Stratifikation
- 1/3 zum Testen, 2/3 zum Trainieren
- Problem: Trainingsmenge ist vielleicht nicht repräsentativ
- Stratifikation: jede Klasse sollte in beiden Mengen etwa im gleichen Verhältnis auftreten wie in der Gesamtmenge
-
wiederholt: Kompensation der Fehler durch wiederholtes Training und Testen mit verschiedenen Daten-Stichproben
- Fehlerraten werden einfach gemittelt
- Vermeidung der Überlappung der Datenmengen : Kreuzvalidierung
Evaluierung
Holdout-Methode
Kreuzvalidierung
- Schritt: Aufteilung der Daten in k Mengen gleicher Größe
- Schritt: pro Durchlauf wird eine Menge für den Test benutzt, der Rest für das Training (3 Mengen = 3 Durchläufe)
- populär: k=3, dreifache Kreuzvalidierung
- mit Stratifikation: stratifizierte dreifache Kreuzvalidierung
- Standardmethode: stratifizierte zehnfache Kreuzvalidierung
- besser: zehn zehnfache Kreuzvalidierungen und danach Mitteln (wiederholte Kreuzvalidierung)
Evaluierung
Holdout-Methode
Leave-One-Out-Kreuzvalidierung
- Vor- und Nachteile
- k-fache Kreuzvalidierung mit k = Anzahl der Instanzen
- eine Instanz wird weggelassen und nach der korrekten Vorhersage dieser Instanz bewertet
- das Ergebnis aller k Beurteilungen wird gemittelt
- Vorteile:
- Benutzung der größtmöglichen Datenmenge
- kein Zufall möglich, deterministisch
- Nachteile:
- sehr rechenaufwendig
- keine Stratifizierung möglich
Evaluierung
Confusion Matrix
- bei einfacher ja/nein-Klassifikation
- gute Matrix: große Zahlen auf der Hauptdiagonalen
Text Mining
Objekte und Attribute
-
Objekte für Klassifikation:
- Dokumente
- Wörter und Wortgruppen
-
Attribute:
- Teile der Objekte (z.B. Buchstaben für Wörter, Wörter für Dokumente)
- Metadaten (für Dokumente), Wörterbuchdaten (für Wörter)
- Zusätzlich daraus abgeleitete Größen
Attribute
Dokumente
- Metadaten: Autor, Titel, Erscheiningsdatum, Quelle (Verlag), Sprache
-
Dokumententext:
- Text als “Bag of Words”
- Wort-N-Gramme, speziell Eigennamen (Personen, geogr. Namen, Firmen), Zahlen mit Maßeinheiten
Attribute
Wörter
-
Teile des Wortes
- Buchstaben-N-Gramme, speziell am Wortanfang und –ende
- Präfixe, Wortstamm, Suffixe
-
Klassifikation des Wortes:
- Grundform, Wortart
- Zugehörigkeit zu Sachgebiet, Information aus Thesaurus
-
Kontext des Wortes
- Nachbarschafts- und Satzkookkurrenzen
- Kompliziertere Nachbarschaftsmuster (mehrere Wörter, evtl. mit Platzhaltern)
- Relationen zwischen solchen Objekten?
Text Mining
Grundaufgaben
- Klassifikation der “Lücken” zwischen Buchstaben
- Klassifikation durch Kontext
- Erkennen und Klassifikation von Mustern
Text Mining - Grundaufgaben
- Klassifikation der “Lücken” zwischen Buchstaben
Beschreibung u. Aufgaben
- Lücken zwischen jeweils zwei aufeinanderfolgenden Buchstaben
- typisch: “eng zusammengehörende” Buchstabenpaare + Bruchstellen
- Für Wörter: Silbentrennung, morphologische Zerlegung von Wörtern, Kompositazerlegung, fehlende arabische kurze Vokale einfügen
- Für Sätze: Tokenisierung für Chinesisch und Japanisch
Text Mining - Grundaufgaben
- Klassifikation durch Kontext
- Kontext, Aufgaben
- Kontext bei Buchstaben: Umgebende Buchstaben (Fenster)
- Kontext bei Wörtern: Wörter als Nachbarn oder in größerem Fenster (Satz, Dokument)
-
Für Wörter
- Aussprache eines Wortes: Phonem zu Graphem
- Betonte Silbe finden = Klassifikation von Vokalen
- Silbenzahl: Klassifikation von Vokalen als Silbengipfel
-
Klassifikation eines Wortes mittels Kookkurrenzen
- Zugehörigkeit zu Sachgebiet
- Unterschied zw. normalen Substantiven und Eigennamen
- Clustering von Wörtern mittels Kookkurrenzen: Finden semantisch ähnlicher Wörter
-
Für Sätze
- Ermittlung der Wortart eines Wortes im Text (POS-Tagging)
- Disambiguierung eines mehrdeutigen Wortes
- Klassifikation eines Textes: Zugehörigkeit zu Sachgebiet
- Dokumentenclustering: Finden ähnlicher Dokumente
Text Mining - Grundaufgaben
Erkennen und Klassifikation von Mustern
- Aufgaben
- oft mit regulären Ausdrücken beschreibbar
- für mittel- und hochfrequente Wörter oft typische (= signifikante) Kontexte als Muster
-
in Wörtern:
- Sprachidentifikation für Sprachen mit speziellen Zeichen
- Grundformreduktion: wiederholende Gruppen von Endungen zu einer Grundform
- Erkennung von Fremdwörtern: Typische Präfixe und Suffixe
-
in Sätzen:
- Personennamenerkennung: Muster wie Titel-Vorname-Nachname
- Erkennen von Redewendungen (von X zu X)
- Paraphrasierung von Komposita als Beschreibung, Blumenvase = Vase für Blumen, Glasvase = Vase aus Glas
- Semantik von Präpositionen, z.B. mit (Bestandteil, Werkzeug, Eigenschaft)
-
in Dokumenten:
- Sprachindentifikation durch typische hochfrequente Wörter
- Sachgebietsklassifikation
- Spamfilter
- Plagiatserkennung
Text Mining
Eigennamenerkennung
Teilaufgaben
- Wiedererkennen bekannter Objekte
- Listen mit Eigennamen (Wikipedia, Telefonbücher, GNS/Gazetteer für Ortsnamen) oder wiederkehrende Strukturen (Titel-Vorname-Name)
- sprachabhängig, Mehrdeutigkeiten, Ausnahmen
- Erkennen von Namen als Klassifikation
- Kontext des zu klassifizierenden Wortes im Text
- Vorname vor potenziellem Nachname, aber kein Artikel
- in, aus, nach vor potentiellem Ortsnamen, aber kein Artikel
- Wortähnlichkeiten
- Stringähnlichkeit (Obermayer Nachname -> Obermeyer)
- Häufige Wortbestandteile (wie -stadt, -walde usw.)
- Kontext des zu klassifizierenden Wortes im Text
Text Mining
Wörter in Teile zerlegen
- Aufgaben, Speicherung
- Grundformreduktion: intuitiv = Endungen abschneiden
- Kompositazerlegung: ein vorhandenes Wort abschneiden, so dass ein Wort übrig bleibt
- Zerlege Worte so, dass Teile bekannt sind (Wörter, Endungen)
- verwende
- Ähnlichkeiten der Wörter vom Wortende her (bei 1 und 2)
- Ähnlichkeiten der Wörter vom Wortanfang her (bei 2)
- Datenstrukturen, die Wortanfang oder Wortende „benutzen“: CPT
Speicherung
Möglichkeiten
- relationale DB: viel Speicherplatz, Elementaroperationen implementiert, Zusatzinformationen speicherbar, aber langsam, v.a. kompleye Operationen wie partial match
- Wortlisten: Reihenfolge unwichtig, strukturelle Redundanzen (gleiche Präfixe/Suffixe), eingeschränktes Alphabet mit 26 Buchstaben + Sonderzeichen
- Trie: Ausnutzen gleicher Präfixe/Suffixe, Knoten haben 0 bis N Töchter (N Anzahl möglicher Characters
Speicherung
CPT: Compact Patricia Trie
- Prinzip, Suchen, Einfügen
- Reduzieren der Kanten durch Speicherung von mehreren Characters in einen Knoten
-
Suche:
- Rekursives Absteigen, Suchwort von vorn verkleinern
- Zurückliefern des letzten erreichten Knotens.
- falls restliches Suchwort leer: exact match, sonst partial match
-
Einfügen von w:
- Suche nach w liefert den Zielknoten k
- falls exact match: Wort schon vorhanden
- falls partial match: Inhalt des Zielknotens k aufteilen, Töchterknoten einfügen.
- Es gilt im Zielknoten k: w=uv, k.inhalt=ux
- Suche nach w liefert den Zielknoten k
Speicherung von Zusatzinformationen in CPTs
z.B. Grundformreduktion
- Knoten werden um Feld erweitert, das die Zusatzinformation + zusammengezählte Klassifizierungen der Unterbäume aufnimmt
- Beispiel: CPT wird aus rückwärts gelesenen Wörtern aufgebaut, “<” ist Wortanfang-Zeichen
- Reduktionsregel in letztem gefundenen Knoten wird angewendet
Speicherung: CPT
Pruning
- wenn CPT nur zum Klassifizieren und nicht zum Speichern von Wörtern verwendet
- redundante Teilbäume abschneiden
- Strings in den Blättern ohne Änderung des Verhaltens auf Länge 1 kürzen
Klassifikation
Entscheidungsbäume
- Aufbau ist rekursiv
- wähle 1 Attribut als Wurzel und verzweige für jeden möglichen Wert -> Beispielmenge in Untermengen zerlegt
- für jeden Zweig rekursiv ausführen mit nur noch jenen Instanzen, die die Verzweigung auch erreichen
- Abbruch, wenn alle Instanzen in einem Knoten dieselbe Klasse aufweisen
Auswahl der Attribute nach Informationsgewinn
Klassifikation: Entscheidungsbaum
1R-Algorithmus
For each attribute:
For each value of the attribute, make a rule as follows:
count how often each class appears find the most frequent class make the rule assign that class to this attribute-value
Calculate the error rate of the rules
Choose the set of rules for the attibute with the smallest error rate
-> z.B. wähle Regelmenge für das Attribut “outlook”
Klassifikation: Entscheidungsbäume
Entropie
Beispiel: Entropie für ‘outlook’
Entropie einer Wahrscheinlichkeitsverteilung p={p1, p2,…, pn} (d.h. pi≥0, Σpi=1):
entropie(p1, p2,…, pn) = - Σpi log(pi)
Klassifikation: Entscheidungsbäume
Information eines Knotens
Beispiel: ‘outlook’
Verteilung der Instanzen einbeziehen:
info(outlook) = info([2,3], [4,0], [3,2])
= 5/14 x 0.971 + 4/14 x 0 + 5/14 x 0.971
= 0.693
Entropie für sunny, overcast, rainy
Klassifikation: Entscheidungsbäume
Informationszuwachs
(Info vor dem Split) – (Info nach dem Split)
gain(outlook) = info([9,5]) - info([2,3], [4,0], [3,2] )
= 0.940 – 0.693
= 0.247
-> erstes Attribute im Entscheidungsbaum ist das mit höchstem Informationsgewinn
Klassifikation: Entscheidungsbaum
numerische Attribute
Beispiel: temperature
- Standardmethode: binäre bzw. Zwei-Wege-Aufteilung
- Unterschied zu nominalen Attributen: viele Splitpunkte möglich
- Lösung:
- berechne Informationsgewinn für jeden Splitpunkt
- wähle besten Punkt
- Informationsgewinn für diesen Punkt entspricht Informationsgewinn des Attributs
- Splitpunkte werden in der Mitte zwischen zwei Werten gesetzt
- Test aller Splitpunkte in nur einem Durchlauf
Klassifikation
Precision und Recall
precision = tp / (tp+fp)
recall = tp / (tp + fn)
tp = true positive
Klassifikation
Meta-Lernen
- Bagging
- (ungewichtete) Mehrheitsentscheidung
- jedes Modell erhält das gleiche Gewicht
- ideale Version:
- mehrere Trainingsdatenmengen gleicher Größe herausgreifen
- 1 Klassifizierer für jede Menge bilden
- Vorhersagen der Klassifizierer kombinieren
- führt fast immer zur Leistungsverbesserung bei „unstabilen“ Lernverfahren (z.B. Entscheidungsbaum)
Klassifikation
Meta-Lernen
- Boosting
- Mehrheitsentscheidungen mit Gewichtung in Abhängigkeit von der Leistung
- gewichtet werden Instanzen
- belohnt wird das Lösen einer „schwierigen“ (d.h. hoch bewerteten) Aufgabe.
-
iterativ: neue Modelle durch Leistung älterer beeinflusst
- neue Modelle ermutigt, Experten für Instanzen zu werden, die von früheren Modellen unkorrekt gehandhabt wurden
- intuitiv: Modelle sollten sich ergänzen statt sich zu überlagern
Klassifikation
Meta-Lernen
Stacking
Stacked Generalisation (gestapelte Generalisierung)
- Abstimmungsverfahren wird durch Metalernverfahren ersetzt
- Vorhersagen der Basislernsysteme (Level-0-Modelle) werden als Eingabe für das Metalernverfahren (Level-1-Modell) benutzt
- Level-1-Verfahren benutzt Ausgaben der Level-0-Verfahren, um Entscheidung zu treffen
- Basislernsystem benutzten Modelle verschiedenen Typs
weniger oft eingesetzt als Bagging und Boosting + theoretisch schwer zu analysieren
Klassifikation
Bayessches Lernen
allgemein
- zw. verschiedenen Attributen wird Kausalität vermutet
- damit Vorhersage für ein unbekanntes Attribut gemacht
- aus Trainingsinstanzen wird Art der Abhängigkeit gelernt
- jede beobachtete Trainingsinstanz kann erwarteten Wahrscheinlichkeiten verändern
- explizites Vorwissen (z.B. Richtung der Zusammenhänge) kann ausgedrückt werden
- vorhergesagt werden Wahrscheinlichkeiten
Klassifikation
Bayessches Formel
Beispiel: Wir haben eine blaue Kugel gezogen. Wie groß ist die Wahrscheinlichkeit, dass sie aus Sack Nr. 1 stammt
- P(h|D) = a posteriori Wahrscheinlichkeit von h
- P(h) = a priori Wahrscheinlichkeit von h
- P(D|h) = Wahrscheinlichkeit des Ereignisses D unter der Hypothese h
- P(D) = Wahrscheinlichkeit des Ereignisses D unabhängig von einer Hypothese
P(h|D) = (P(D|h) * P(h)) / P(D)
D: blaue Kugel gezogen
h: vorher Sack 1 ausgewählt.
Klassifikation
Bayessches Lernen
MAP: Maximum a posteriori Propability
P(weather=’rainy’|grass=’wet’) = 0.1
P(sprinkler=’on’|grass=’wet’) = 0.08
-> wähle weather=’rainy’, weil Wahrscheinlichkeit, dass Gras durch Regen nass ist höher ist, als durch Sprinkler
Klassifikation
Bayessches Lernen
Maximum Likelihood Hyotheses
falls alle Hypothesen die gleiche a priori Wahrscheinlichkeit haben
Klassifikation
BOC: Bayesscher optimaler Klassifikator
- wahrscheinlichste Klassifikation einer neuen Instanz unter Berücksichtigung der Trainingsdaten
- {V} = Menge der Klassen
- Klasse = einzelne Hypothese o. Menge von Hypothesen
- BOC berechnet a posteriori Wahrscheinlichkeit jeder Hypothese und kombiniert Voraussagen für Klassifikation der neuen Instanz
- innerhalb der Hypothesenraums und des Vorwissens BOC im Mittel unschlagbar
- rechenaufwändig.
kNN
Definition - instance based learning
- Learning: store all the data instances
- Performance: when a new query instance is encountered
- retrieve a similar set of related instances from memory
- use to classify the new query
-
kNN: most basic type of instance learning
- all instances are points in n-dimensional space
- distance measure to determine “closeness” of instances
- Classify an instance by finding its nearest neighbors and picking the most popular class among the neighbors
K-D Tree
- Multiple dimensional data
- Extending BST from one dimensional to k-dimensional
- binary tree
- Organized by levels (root is at level 0, its children level 1, etc.)
- Tree branching at level 0 according to the first key, at level 1 according to the second key, etc.
- KdNode: has a vector of keys, in addition to the pointers to its subtrees.
K-D Tree
2-D Tree: insert
- new node is inserted as a leaf
- different keys are compared at different levels
approximative NN-Suche
nächsten Nachbarn mit max. Abstand d zu einem Punkt x zu finden:
- suche Clusterzentrum entsprechend Grob-Quantisierung
- betrachte die dazugehörige Voronoi-Zelle sowie alle Nachbarzellen mit geeignet kleinem Abstand
- wähle alle Punkte daraus und berechne näherungsweisen Abstand zu x
- Ausgabe in Reihenfolge der Abstände.
More Data Effect
allgemein
- Differences between algorithms flip or disappear
- Differences between representations disappear
- Growth of curve seems log-linear (constant improvement with exponentially more data) -> effect persists
- Explanation sought in “Zipf’s tail”
- More observations of words already seen
- More new words become known (the tail)
Memory Based Learning
Example Storage - instance editing
(Prinzip, Algorithmus)
- store a subset of the most informative training examples in order to focus the system and to make it more efficient: instance editing
- Edit superfluous regular instances
- evidence that keeping all training instances
is best in exemplar-based approaches to NLP - e.g. IB2 Algorithmus
Tagger-Architektur
Konstruktion eines POS-Taggers
- geg: neues annotiertes Korpus
- 3 Datenstrukturen werden automatisch extrahiert:
- Lexikon
- Fallbasierung für known words
- Fallbasierung für unknown words
- (beide Fallbasierungen als IGTree implementiert)
- Fall = Information über ein Wort das getaggt werden soll, seinem linken und rechten Kontext und einer dazugehörigen Kategorie für das Wort in diesem Kontext
Tagger-Architektur
Ablauf des Taggen
- Jedes Wort wird im Lexikon nachgeschaut
- Wird es gefunden:
- lexikalische Repräsentation wird abgefragt
- Kontext wird bestimmt
- resultierendes Muster wird in der known words - Fallbasierung nachgeschlagen
- Wird es nicht gefunden:
- lexikalische Repräsentation wird auf Grundlage seiner Form berechnet
- Kontext wird bestimmt
- resultierendes Muster wird in der unknown words Fallbasierung nachgeschlagen
Memory Based Learning
IGTree
Prinzip, Knoten, Performanz
= Entscheidungsbaum nach Information Gain
- kombiniert 2 Algorithmen:
– Komprimieren von Fallunterscheidungen in Bäumen
– Zurückholen von Klassifikationsinformationen - Fälle als Wege von verbundenen Knoten gespeichert
- Blattknoten: eindeutige Klassifikation
- Knoten: Infos über wahrscheinlichste Klassifikation o. Default-Klassifikation
- Verwenden der Default-Klassifikation des letzten abgefragten nicht-terminierenden Knotens, falls eine feature-value-Abfrage fehlschlägt
- IGTree-Abfrage 100-200 mal schneller als eine normale speicherbasierte Abfrage und nutzt über 95% weniger Speicher
Topic Models
Idee, Posterior Distribution
- Topic Model: model topics as distribution over words
- Annahme: wenige Topics (100-200)
- Only documents are observable
- Infer underlying topic structur:
- Topics that generated the documents
- For each document, distribution of topics
- For each word, which topic generated the word
- Algorithmic challenge: Finding the conditional distribution of all the latent variables, given the observation.
Topic Models
Inference
- Three sets of latent variables
– topic mixtures θ
– word distributions φ
– topic assignments z - Integrate out θ and φ and estimate topic assignments
- Use MCMC with Gibbs sampling for approximate inference
Topic Models
Gibbs Sampling
- mit zufälliger Verteilung starten und schauen, ob bei minimalen Änderungen Idealzustand annäherungsweise erreicht wird
Start with random assignments of words to topics
Repeat M iterations
- Repeat for all words i
- Sample a new topic assignment for word i conditioned on all other topic assignments
Topic Models
theoretische Idee vs. praktische Umsetzung
Latent Semantic Analysis: Produkt von kleineren Matrizen
Topic Models
Kookkurrenzen, künstliche Dokumente
Kookkurrenzen:
- geg: Eingabewort und vorhandenes Topic Model
- untersucht wird Verteilung der Satzkookkurrenzen auf vorberechnete Topics
künstliche Dokumente:
- damit Wort mehrere (z.B. mind. 10) Kookkurrenzen hat, braucht es eine Mindestfrequenz von ca. 50.
- seltenere Wörter/noch nie gesehene: typische Kontexte (=Kookkurrenzen) durch tatsächliche Kontexte (=Beispielsätze) ersetzen
- aus Beispielsätzen künstliches Dokument erzeugen und für dieses die Topicverteilung ermitteln
Word Embedding
Word2Vec: Reduzierung des Featureraums
- Semantisch ähnlichen Wörtern entsprechen ähnliche Spalten in der Kookkurrenzmatrix, damit ist eine große Rangreduktion möglich auf 50-200 Features.
- Ermittlung der Matrix F: iterativ mittels neuronaler Netze. Optimierungskiterium: Jedes Wort soll sich selbst als ähnlichstes Wort behalten.
- Features entsprechen nicht (wie bei Topics) mit Wahrscheinlichkeiten gewichteten Mengen von Wörtern, sondern beliebigen Linearkombinationen.
Word Embedding
Möglichkeiten, Wörter darzustellen + Dimensionsreduktion
Word Embedding
Vektoralgebra
(Polen : Warschau = Ungarn : X)
Verbindungen (=Differenzvektoren) fast identisch
Polen : Warschau = Ungarn : X folgender Maßen lösen:
X ist das Wort mit dem dazugehörigen Vektor am nächsten zu vec(Ungarn) – vec(Polen) + vec(Warschau)
Disambiguität
SIGIL
- Sense Induction by Greedy Iterative Labeling
- Hauptannahme: Nur eine Bedeutung pro Kookkurrenz
- Precision von ca. 63%
- Berechne Kookkurrenzen aus Korpus
- Zu Ausgangswort W, Auswahl “relevanter” Wörter mit hohen Wahrscheinlichkeiten P(W | wi), ergibt Ähnlichkeitsmatrix
- Auswahl von Saatwörtern für jede zu induzierende Bedeutung von W
- Zuordnung weiterer Wörter aus der relevanten Menge aufgrund von in 1. berechneten Kookkurrenzen
- Iteriert 4, bis für jedes Wort wahrscheinlichkeitsbasierte Zuordnung von relevanten Wörtern zu den zu induzierenden Bedeutungen von W
- Schritt 1 und 2 ist Berechnen von Kookkurrenzen
- Schritt 4 und 5 ist eigentlich Clustering
Grapheigenschaft der Kookkurrenzen
+ allgemeine Eigenschaften
- durch Satzkookkurrenzen wird implizit ein Graph definiert
- stark zusammenhängende Knoten liegen nah beieinander
- Graph zusammenhängend
- dünner Graph, sehr wenige Kanten
- Zipfsches Gesetz der Verbundenheitsgrade: einige wenige Knoten, die zu fast allen verbunden sind (Artikel) und absteigend Funktionswörter, Adjektive, Verben, etc.
- sehr hoher lokaler Clusterwert -> überall im Graphen abgrenzbare Häufungen
- sehr kurze Wege zwischen einzelnen Punkten des Graphen
-> Small World Graph
