TextMining Flashcards

Question

**Clustering** Unterschiede bei Algorithmen/Modellen

Answer 1

* Cluster disjunkt o. überlappend * Verfahren deterministisch o. probabilistisch * Cluster hierarchisch o. nicht * Algorithmus lernt inkrementell o. nur global

Answer 2

* **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

Answer 3

* **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

Answer 4

* Daten werden vom Algorithmus in vorgeg. Anzahl von k Clustern geteilt 1. **Initialisierung**: k Clusterzentren werden zufällig gewählt 2. **Zuordnung:** Instanzen werden jeweils Cluster mit dem nächstgelegenen Clusterzentrum zugeordnet. 3. **Zentroid**: Zentroiden der so entstandenen Cluster werden als neue Clusterzentren benutzt. 4. **Schleife**: Gehe zu 2, solange sich noch Zuordnungen einzelner Elemente zu Clustern ändern.

Answer 5

* 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.

Answer 6

* **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

Answer 7

* 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

Answer 8

* 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

Answer 9

* Anzahl der korrekten Klassifizierungen * Genauigkeit von Wahrscheinlichkeitsvorhersagen * Genauigkeit von numerischen Vorhersagen * Kosten Klassifizierung: Fehllerate

Answer 10

* 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**

Answer 11

1. Schritt: Aufteilung der Daten in k Mengen gleicher Größe 2. 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)

Answer 12

* 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

Answer 13

* bei einfacher ja/nein-Klassifikation * gute Matrix: große Zahlen auf der Hauptdiagonalen

Answer 14

* **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

Answer 15

* **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

Answer 16

* **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?

Answer 17

1. Klassifikation der "Lücken" zwischen Buchstaben 2. Klassifikation durch Kontext 3. Erkennen und Klassifikation von Mustern

Answer 18

* 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

Answer 19

* **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

Answer 20

* 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

Answer 21

1. Wiedererkennen bekannter Objekte * Listen mit Eigennamen (Wikipedia, Telefonbücher, GNS/Gazetteer für Ortsnamen) _oder_ wiederkehrende Strukturen (Titel-Vorname-Name) * sprachabhängig, Mehrdeutigkeiten, Ausnahmen 2. 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.)

Answer 22

1. **Grundformreduktion:** intuitiv = Endungen abschneiden 2. **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

Answer 23

* **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

Answer 24

* abgeleitet von Information Re**trie**val * Spezielle **m-Wege Bäum**e, m = Kardinalität des Alphabets * Knoten ist **Vektor** mit **m** Zeigern auf Töchterknoten, implizite Zuordnung Alphabetzeichen und Position * **Baumhöhe**: Länge des längsten gespeicherten Wortes -\> Suchzeit linear in Wortlänge * Gestalt unabhängig von Einfügereihenfolge * Schlechte Speicherplatzausnutzung (viele leere Pointer) vermeiden durch * Zusammenfassen von Unterbäumen, falls diese nicht verzweigen * nur Abspeichern der besetzten Zeiger, Angabe über Position erforderlich

Answer 25

* 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

Answer 26

* 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

Answer 27

* 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

Answer 28

* Kompositazerlegung: * 2 CPTs, Schnittstellen von vorn und hinten * Morphologieklasse * Geschlechter von Namen * Wortarterkennung * Terminologie * ...

Answer 29

+ alle Trainingsdaten werden im Test reproduziert + beliebige Sonderfälle trainierbar - Trainingsmenge muss gewisse Größe haben - ohne Trainingsmenge ist Algorithmus hilflos

Answer 30

* 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**

Answer 31

* **nominal**: Anzahl der Tochterknoten entspricht Anzahl der möglichen Werte (z.B. alle Buchstaben) * **numerisch**: Vergleich auf größer/kleiner * Alternativen: **Dreifachverzweigungen** * Integer: kleiner, gleich, größer * Intervall: unterhalb, innerhalb, oberhalb

Answer 32

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"

Answer 33

Entropie einer Wahrscheinlichkeitsverteilung p={p₁, p₂,..., p_n} (d.h. p_i≥0, Σp_i=1): entropie(p₁, p₂,..., p_n) = - Σp_i log(p_i)

Answer 34

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

Answer 35

(Info vor dem Split) – (Info nach dem Split) ## Footnote **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

Answer 36

* 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

Answer 37

* „Beschneiden“ von Bäumen zur Vereinfachung * 2 Strategien: 1. **Postpruning** = nachträgliche Beschneidung des vollständigen Baums 2. **Prepruning** = Entscheidung während des Baumbildungsverfahrens, z.B. Entwicklung weiterer Unterbäume einzustellen * In der Praxis wird **Postpruning** bevorzugt * **Problem bei Prepruning**: zu frühes Stoppen

Answer 38

* je mehrere Experten für 1 Fragetyp zuständig * Experten antworten mit verschiedenen Methoden * jeder Experte beantwortet eine Frage mit Wahrscheinlichkeiten p,q,r richtig, gar nicht oder falsch. * Expertenrunde entscheidet nach folgenden **Regeln**: Entscheidung angenommen, wenn * es stimmen mind. 2 Experten zu * zugestimmt wird mit einer Mehrheit von mindestens 75% (ohne Berücksichtigung der Enthaltungen) * z.B. richtige Entscheidung angenommen mit p³+3p²q * Wahrscheinlichkeiten für falsche Ergebnisse hängen nicht von Größe des Expertenforums ab

Answer 39

precision = tp / (tp+fp) recall = tp / (tp + fn) tp = true positive

Answer 40

* mehrere, teil-korrekte Klassifikatoren * versch. Algorithmen + versch. Trainingsdaten * gewisse **Mindestgüte** * können **auf verschiedenen Teilen des Instanzenraums unterschiedlich gut** sein * Kombination der Einzelergebnisse, um Gesamtverhalten signifikant zu verbessern * Algorithmen: **Bagging + Boosting + Stacking**

Answer 41

* **(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)

Answer 42

* **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

Answer 43

**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

Answer 44

* 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

Answer 45

* 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.

Answer 46

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

Answer 47

falls alle Hypothesen die gleiche a priori Wahrscheinlichkeit haben

Answer 48

* 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**.

Answer 49

* Dokumente auf vorgegebene Klassen verteilen * **Annahme**: Klassen lassen sich durch Wörter beschreiben, die in den Dokumenten der entsprechenden Klassen auftauchen * **Attribute:** Wörter, **unabhängig** von ihrer Position im Text mit Werten ja/nein * z.B. **Spamfilter:** Initiales Training vom Hersteller mittels bekannter Spam-Emails und Nicht-Spam + handgemachte Wortgruppen als Features +nachträgliches Trainieren durch Nutzer

Answer 50

* **Greedy:** Entscheidungsbaum, Regelbasiert, probabilistisch (Naive Bayes, max. Entropie), ... * Modellbindung während/nach Trainieren * **Lazy:** kNN * Modellbindung zur Zeit der Anfrage

Answer 51

* jedes Objekt beschrieben durch **Attribut-Wert- Paare** * feste Reihenfolge der Attribute erzeugt **Vektor von Attributwerten**. * **Entscheidungsbäume** nutzen die Attribute nacheinander. * Im **Vektorraum** können wir alle Attribute gleichzeitig nutzen

Answer 52

* 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

Answer 53

+ Can construct a different approximation to the target function for each distinct query instance to be classified + Can use more complex, symbolic representations – Cost of classification can be high – Uses all attributes (not most important)

Answer 54

* 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.

Answer 55

* new node is inserted as a leaf * different keys are compared at different levels

Answer 56

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.

Answer 57

* With a memory filled with instances of language mappings – from text to speech, – from words to syntactic structure, – ... * With the use of analogical reasoning, * Process new instances from input (text, words) to output (speech, syntactic structure)

Answer 58

* 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)

Answer 59

* Tend do go **upwards** because of Zipf’s tail * upward trend may **slow down** * more examples add more of the same information w.r.t. classification * trend may **revert to going down** * additional data contains errors, noise, or is sampled in a different manner than before * trend **stops** * 100% mark or the annotation accuracy is reached * input representation lacks expressiveness to resolve more ambiguity

Answer 60

* 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

Answer 61

* EBL methods base decisions on similarity to specific past instances rather than constructing abstractions * abandon the goal of maintaining concept “simplicity” * trade decreased learning time for increased classification time * store all examples = all exceptions = very important for NLP tasks

Answer 62

**Learning:** store instances in memory **Classification:** * given new test instance X, * compare it to all memory instances * compute a distance between X and memory instance Y * update the top k of closest instances (NNs) * take the majority class of the k NNs as the class of X

Answer 63

Wenn für viele Attribute Nullwerte vorliegen 0000010200001000 -\> 6:1 8:2 13:1 0010010001200000 -\> 3:1 6:1 10:1 11:2

Answer 64

* verschränkt \> rechtsbündig \> linksbündig * 2000 häufige \> 20000 \> 2000 zufällige * kNN (IB1 mit k=3) \> Entscheidungsbaum (IGTree)

Answer 65

* **Lexicon** of words * all: **closed classes** * not all: **open classes** (Subst., Verben, Adjektive, Adverben) * For each word in the lexicon information about all its possible tags according to a chosen **tagset** * 40-1300 Tags * Wortarten, grammatische Informationen,... * Different methods for choosing the correct tag for a word: – Rule-based methods – Statistical methods – Transformation Based Learning (TBL) methods

Answer 66

* Start with a dictionary * Assign all possible tags to words from the dictionary * Write rules by hand to selectively remove tags * Leaving the correct tag for each word

Answer 67

1. **Most Frequent Tag Algorithm** **Training:** – Take a tagged corpus – Create dict containing every word in the corpus with all its possible tags – Count number each tag occurs for a word and compute the probability P(tag|word); save all probabilities **Tagging:** – geg. new sentence – for each word, pick the most frequent tag from the corpus

Answer 68

HMM = Hidden Markov Model **Training:** – Create dict containing every word in the corpus with all its possible tags – Compute the probability of each tag generating a certain word + the probability each tag is preceded by a specific tag (Bigram HMM Tagger =\> dependent only on the previous tag) **Tagging:** – Given a new sentence – for each word, pick the most likely tag for that word using the parameters obtained after training – HMM Taggers choose the tag sequence that maximizes this formula: P(word|tag) \* P(tag|previous tag)

Answer 69

**Combination of rule-based and stochastic tagging methodologies** – rule templates are used to learn transformations – stochastic: machine learning is used - with tagged corpus as input **Input:** tagged corpus, lexicon **basic idea:** Set the most probable tag for each word as a start value – Change tags according to rules of type “if word-1 is a determiner and word is a verb then change the tag to noun” in a specific order

Answer 70

* 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 über ein Wort das getaggt werden soll, seinem linken und rechten Kontext und einer dazugehörigen Kategorie für das Wort in diesem Kontext

Answer 71

* 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

Answer 72

= 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

Answer 73

* 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.

Answer 74

* 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

Answer 75

* 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

Answer 76

**Latent Semantic Analysis:** Produkt von kleineren Matrizen

Answer 77

* Texte nehmen, in denen wir die relevanten Topics vermuten (Zeitungsartikel, Wikipedia-Artikel) * Auswahl der zuzuordnenden Wörter, da Wörter mit breiter Verteilung die Topics möglicherweise „verschlechtern“ (keine Stoppwörter, nur Substantive) * Anzahl der Topics (50 ... 500, meist 100 oder 200) * Schwellwert, wie lange Wörter als zu einem Topic zugehörig betrachtet werden sollen (p\>0.004)

Answer 78

* wenig große, viele kleine Topics (~Zipfsches Gesetz) * große Topics aufgesplittet, kleine unpassend zusammengefasst * am besten 100-200 * **Namen**: markanteste Wörter o. Bezeichnungen von Menschen

Answer 79

**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

Answer 80

* Automatische Auswahl der heute auffälligen Wörter (heute viel häufiger als im Mittel, nur Substantive (Großschreibung)) * Einmalige Klassifikation der Wörter von Hand * vorgegebene, praktisch sinnvolle Klassen * keine flektierten Formen erlaubt * automatische Wiederverwendung klassifizierter Wörter. **Probleme:** nur fürs Deutsche, Klassifikation muss nicht stabil sein, (z.B. Schwarzenegger Schauspieler/Politiker) * *Neu:** vorgefertigte Klassifikation mittels Topics, abgeleitet aus Wikipedia-Kategorien * *Vorteile:** für viele Sprachen * *Nachteile:** POS-Tagging + Grundformreduktion nötig

Answer 81

* Objekte durch Vektoren in einem hochdimensionalen Raum beschreiben * Zuordnung = "word/sentence/... embedding" * **semantisch:** * Semantisch ähnliche Objekte werden nahe beieinanderliegenden Vektoren zugeordnet * Umgedreht entsprechen nahe beienanderliegende Vektoren semantisch ähnlichen Objekten * Dimension des Vektorraums ist gleich der Anzahl der berücksichtigten Beschreibungswörter

Answer 82

* Ähnlichkeit zweier Wörter als Vektorabstand berechnen * nur für Wörter mit Mindesthäufigkeit. (Rang\<200.000) **Version 1:** Wortkookkurrenzen. Wortvektor von Wort A * 1 an Position b, wenn Wort B mit Id=b Satzkookkurrenz zu A ist. * 1 an Position 200000+b, wenn Wort B mit Id=b NB-Kookkurrenz zu A ist. Vergleich zweier Vektoren für Wörter A und B über das Skalarprodukt: berechnet Anzahl der gemeinsamen Kookkurrenzen von A und B. * **Vorteil:** Die V ektoren sind schwach besetzt, nur 0 oder 1. * **Nachteile:** Bewertet werden die Gemeinsamkeiten, nicht bestraft werden die Unterschiede, rechte und linke Nachbarn werden nicht unterschieden.

Answer 83

Version 2: Wortkookkurrenzen. Wortvektor von Wort A * 1 an Position b, wenn Wort B mit Id=b Satzkookkurrenz zu A ist. * 1 an Position 200000+b, wenn Wort mit Id=b linke NB-Kookkurrenz zu A ist. * 1 an Position 400000+b, wenn Wort mit Id=b rechter NB-Kookkurrenz zu A ist * Vektoren normiert Vergleich zweier Vektoren für Wörter A und B über das Skalarprodukt: Cosinus des Winkels zwischen den Vektoren

Answer 84

* Projeziere Vektorraum auf z.B. 500 zufällig erzeugte paarweise (fast) orthogonale Einheitsvektoren. * **Nachteil:** Vektoren nicht mehr schwach besetzt.

Answer 85

* **Word2Vec** * Konstruktion des Vektors durch **neuronales Netz** * inkl. Dimensionsreduktion. * mit variablem Fenster über den Text gelesen und Kontext der einzelnen Wörter berücksichtigt * ähnlich zu Kookkurrenzen.

Answer 86

* 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.

Answer 87

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)**

Answer 88

* **Bag-of-words-Ansatz:** Beschreibe einen Satz durch die Menge seiner Wörter = Summe seiner Wortvektoren, evtl. noch normiert * zusätzliche Forderung: Gleiche oder ähnliche Satzbaupläne

Answer 89

* **lexikalische** Ebene: Ball – Ball * **semantische** Ebene (strukturelle/kompositionell-semantische): Jeder Mann tanzte mit einer Frau * **syntaktische** Ebene: Mann mit dem Fernrohr sehen * **Phonem**ebene: Miene – Mine * **morphologische** Ebene: Staubecken – Staubecken durch etymologische Entwicklungen, semantische Zusammenhänge und v. a.

Answer 90

* durch **Redundanz** in Sprache und **Kontext** für Menschen kein Problem * normal: **Paraphrasierung** (z.B. "Herrschaftshaus" statt "Schloss" * außerdem: grammatische Analyse, außersprachlicherKontext

Answer 91

* **konstruktiv:** keine vollständig vorhanden * **beschreibend:** kurz, in ein einem oder zwei Sätzen für einen durchschnittlichen Menschen verständlich erläutert * **differenzierend**: für jede Bedeutung soviele Begriffe gegeben, dass die konkrete Bedeutung klar von allen anderen abgrenzbar wird -\> für **Algorithmen** Methode der Berechnung von Kookkurrenzen / Wortassoziationen und Clustering dieser für lediglich distinktive Definition von Bedeutungen

Answer 92

* Sense Induction by Greedy Iterative Labeling * **Hauptannahme**: Nur eine Bedeutung pro Kookkurrenz * **Precision** von ca. 63% 1. Berechne Kookkurrenzen aus Korpus 2. Zu Ausgangswort W, Auswahl “relevanter” Wörter mit hohen Wahrscheinlichkeiten P(W | w_i), ergibt Ähnlichkeitsmatrix 3. Auswahl von **Saatwörtern** für jede zu induzierende Bedeutung von W 4. Zuordnung weiterer Wörter aus der relevanten Menge aufgrund von in 1. berechneten Kookkurrenzen 5. 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**

Answer 93

* 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**

Answer 94

* Lokale Cluster sind **omnipräsent**, jedes Wort befindet sich in einem oder mehreren Clustern: * Cluster sind **semantischer** Natur * Cluster sind **Kontext-Homogen** (wenn Wörter ‘zusammenpassen’, ist Schnittmenge kontext-homogen)