Seite 1 von 1

Klausur SS05

Verfasst: 13. Jul 2012 22:34
von h4ck4
Klausur SS05, Aufgabe 01

(a)
i) R=5/6
ii) P = 1/3
iii)P[10] = 3/5 @ R=1/2

(b) acc = 97,8%

(c) a=b=7 => Query nach dem 14.Rank abschneiden =>Acc= 98,8%

(d) F-Measure, Break-Even-Point?

Kann das jmd bestätigen?

Klausur SS05 Aufgabe 05

Verfasst: 13. Jul 2012 23:25
von h4ck4
Klausur SS05, Aufgabe 05

(a)
h0 = (1 1 1)
a0 = (1 1 1)

h1 = (1/2 1/4 1/4)
a1 = (0 1/2 1/2)

h2 = (1/2 1/4 1/4)
a2 = (0 1/2 1/2)

-> Keine Veränderung mehr nach 2. Iteration!

(b)
- query dependent -> root set
- execute @ query time
- processed on a small subset (= focused graph, base set)
reason for constructing base set: ensure that many of strongest authorities are included.

(c) wiki:
...d ein Dämpfungsfaktor zwischen 0 und 1, mit dem ein kleiner Anteil des Gewichts () einer jeden Seite abgezogen und gleichmäßig auf alle vom Algorithmus erfassten Seiten verteilt wird. Dies ist notwendig, damit das Gewicht nicht zu Seiten „abfließt“, die auf keine andere Seite verweisen. Oft wird die obige Formel auch ohne den Normierungsfaktor angegeben.

(d) ???

(e) kNN-classifier

(f) kNN -> supervised (completely labeled data for training)

Kann das jmd bestätigen?

Klausur SS05 Aufgabe 04

Verfasst: 14. Jul 2012 00:21
von h4ck4
Klausur SS05, Aufgabe 04

(a)
|c| = 10
|D| = 1.000 -> concatenate all docs per class
|V| = 30.000

prior p(c) -> |c| = 10
p(t|c) -> |V| * |c| = 10 * 30.000 = 300.000

-> ca. 300.010 WS-Schätzungen

(b)
WS für alle Klassen 0 -> Entscheidung unmöglich
-> Lösung: laplace correction

(c)
- different docs length/# features
- consider doc as "bag of words" (feature subset selection?)

(d)
semi-supervised: train with both, a small set of labeled data + a large set of unlabeled data
-> reason, e.g. on the web -> labeling is expensive

(e)
-active learning
- self-training
- co-training

-> good confidence estimates in their own predictions


Kann das jmd bestätigen?

Klausur SS05 Aufgabe 03

Verfasst: 14. Jul 2012 00:57
von h4ck4
Klausur SS05, Aufgabe 03

(a)
supervised: Lernalgo läuft auf completely labeled data (training) -> Modell. Danach kann das System unbekannte, beliebige Sample klassifizieren.
unsupervised: ohne voherige Klassenspezifikation (unbekannt); completely unlabeled data -> clustering

(b)
increase: stemming
decrease: n-grams

Dafür gibts 6pkts?? Ernsthaft? Steht ja in keinem Verhältnis zu den restlichen Teilaufgaben :-/

(c)
Feature subset selection führt auch zur Verbesserung d. Klassifizierungsleistung
Reason: teilweise Filterung von irrelevanten + redundanten Features

(d) ???

(e) nicht sinnvoll:
- latent semantic leraning verringert dimension d. space => Informationsverlust bzw Veränderung der Distanz/Cluster Zentren Relation
- k-means: clustert anhand der Distanz -> Ergebnisverfälschung

Kann das jmd bestätigen?^^

Klausur SS05 Aufgabe 02

Verfasst: 14. Jul 2012 11:51
von h4ck4
Klausur SS05, Aufgabe 02

(a) ???

(b) Bottom-up hierarchical clustering (hierachical agglomerative clustering)

(c) Skript:
use the 5-10 most frequent words in each cluster -> problem same topic of clusters
-> Use distinguishing words/phrases: that appear more frequently in one class than in other classes (e.g., significance tests)

(d) top-down -> bis zum Blatt "hangeln" mit nähster Distanz
-> Blatt in Hierarchie mit neuem Cluster aus Blatt + neuer Seite ersetzen

(e) ??? Was ist die Frage??

(f) HTLR-Wrapper -> extract infos from "structured" text like (HTML-)tables

Re: Klausur SS05

Verfasst: 14. Jul 2012 15:01
von MaMaj
Aufgabe 1 habe ich bis auf die c) genauso.

Die c hätte ich so beantwortet:

Man kann 98,8% Genauigkeit dadurch erreichen, dass man den Algorithmus einfach keine Dokumente retournieren lässt.
Dadurch steigt die Anzahl der relevanten, aber nicht retournierten Dokumente auf 12 (von 12) und die Anzahl der irrelevanten Dokumente auf 988 von 988.
Die Accuracy Formel sagt ja: (rel-ret-doc + irrel-nret-doc) / #docs = accuracy
Und in dem Fall 988 / 1000 = 0,988 => 98,8%

Aufgabe 2

a) Relevante Feedback Query Formation - Man betrachtet die erhaltenen Ergebnisse und selektiert diejenigen, welche man für relevant betrachtet und sucht aus diesen neue Terme heraus. Mit diesen Termen erzeugt man einen neuen Query, prüft dessen Ergebnisse und verfeinert weiter bzw. verwirft die letzte Änderung.

b) gleich

c) Phrasen nutzen, welche prominent in einem Cluster sind, aber selten in den anderen auftreten. Also eigentlich selbe Antwort.

d) gleich

e) (Die Frage habe ich auch nicht ganz verstanden, aber geschätzt): Neighbor Feature Absorbing - Die Vorgänger- und Nachfolgerseiten können auf ähnliche Features und Phrasen hin abgesucht und entweder direkt an die bereits in der hier. Struktur befindlichen Seiten angehängt, oder neu in die Struktur sortiert werden.

f) reicht auch einfach "Wrapper" zu sagen? Oder muss man genau den HTLR Wrapper nennen?

Aufgabe 3

a) UFSS: Wählt Feature Samples zufällig oder nach empirisch / statistisch bekannten Eigenschaften (z.B. Wissen um irrelevante Features / TF-IDF Statistik) aus. Ist somit schnell und für große Datenbestände gut geeignet, auch wenn das FS nicht immer optimal ist.
SFSS: Nutzt eine Gewichtungsfunktion für Terme und gewichtet damit möglichst alle Terme aller Dokumente. Dadurch großer Scan-Overhead bei großen Dokumentsätzen, nicht praxistauglich, jedoch sehr gute Ergebnisse.

b) gleich

c) Ein gutes FS sollte zu einer besseren Klassifikationsleistung des NB führen, da das FS die Klasse besser widerspiegelt, die Wahrscheinlichkeit der Klassenzugehörigkeit steigt und die Wahrscheinlichkeitsergebnisse des NB schärfer werden. (Im Grunde gleiche Antwort)

d) Der CHI2 Test liefert Feature Subsets, welche sich zwischen den jeweiligen Klassen am deutlichsten voneinander unterscheiden. Zu viele redundante Features machen diese Unterscheidung schwieriger, da sie in Dokumenten beider Klassen rel. gleich oft vorkommen. Eine TF-IDF Methode hätte diese Probleme nicht, da sie redundante Features deutlich schwächer für das Ergebnis gewichtet.

Keine Ahnung ob das so Stimmt. Dafür habe ich jetzt drei Stunden im Internet nach mehr Infos gefischt. Anscheinend waren meine Querys nicht spezifisch genug! :-P

e) Danke sehr, habe hier jetzt auch lange recherchiert wie der Zusammenhang ist. Deine Antwort deckt sich mit meiner Vermutung.

Aufgabe 4 und 5 bearbeite ich gerade

Re: Klausur SS05

Verfasst: 14. Jul 2012 15:55
von MaMaj
Okay, Aufgabe 4)

a) Da steige ich nicht ganz durch. Die priori p(c) Anzahl hast du von wo? Ist das Seite 25 im tm Foliensatz?
Kannst du da bitte noch ein paar Erklärungen zu deinem Lösungsweg geben?

b) gleich mit Zusatz: Man nimmt einfach an, dass jeder Wort mind. einmal auftritt (Seite 26 im tm Foliensatz).

c) Multinomial NB: Nutzt bag of words - Wahrscheinlichkeit, dass ein Dokument aufgrund der Frequenz bestimmter Wörter zu einer Klasse gehört.
Binomial NB: Nutzt set of words - Wahrscheinlichkeit, dass ein Dokument, Aufgrund aller verschiedener Wörter welches es beinhaltet und nicht beinhaltet, zu einer Klasse gehört.

d) Training-Set besteht überwiegend aus unmarkierten Daten und nur wenigen markierten Daten.

e) Hier geht es doch um die Frage, welche Anforderung die zugrunde-liegenden Klassifikations-Algos erfüllen müssen, nicht?!
Wo hast du deine Lösung her? Kannst du bitte noch was dazu sagen?!

Re: Klausur SS05

Verfasst: 14. Jul 2012 16:00
von klte
(a)
i) R=5/6
ii) P = 1/3
iii)P[10] = 3/5 @ R=1/2

(b) acc = 97,8%

(c) a=b=7 => Query nach dem 14.Rank abschneiden =>Acc= 98,8%

(d) F-Measure, Break-Even-Point?
zu c): meine Begrünung: In dem man einfach nicht auf 30 Dokumente sich eingrenzt, sondern auf 25 zum Beispiel. Es wächst dann die Zahl nicht rel und nicht retr Dokumente zu, damin nimmt accuracy zu. Man kann damit die 98% erreichen.

Re: Klausur SS05

Verfasst: 14. Jul 2012 19:39
von MaMaj
Okay, hier noch meine Lösungen zur Aufgabe 5

5-a)

h_0(a, b, c) = (1, 1, 1),

a_1(a, b, c) = A^t * h_0 = (0, 2, 2) => ||a_1||_1 = 4 => (0/4, 1/2, 1/2)
h_1(a, b, c) = A * a_1 = (4, 2, 2) => ||h_1||_1 = 8 => (1/2, 1/4, 1/4)

a_2(a, b, c) und h_2(a, b, c) keine weitere Veränderung!

5-b)

HITS berechnet das Ranking erst bei Anfrage und baut ein Root-Set bestehend aus k anfrage-relevanten Seiten. Dieses Root-Set wird zu einem Base-Set erweitert: Root-Set Seiten und Seiten die in und aus dem Root Set verweisen. Base-Set dient zum Aufbau des Hub-Authorities Graphen.

PageRank berechnet Ranking vorab für "alle" Webseiten, ohne auf eine direkte Anfrage angewiesen zu sein, weshalb kein anfrage-relevantes Set und damit auch kein Base-Set benötigt wird.

5-c)

Bei der PageRank Methode wird ein "Zufalls-Surfer" simuliert, welcher von einer Quellseite über eine Anzahl von Zwischenseiten auf eine Zielseite (für die der PageRank berechnet werden soll) gelangt, indem er eine Link-Kette verfolgt.
Der Dämpfungsfaktor (zwischen 0 und 1) gibt die Wahrscheinlichkeit an, mit welcher ein Zufalls-Surfer die Weiterverfolgung von Links NICHT abbricht, d.h. weiter klickt um auf die Zielseite zu gelangen.
Je größer der Wert, desto Größer die Wahrscheinlichkeit, dass der Zufallssurfer die Zielwebseite über den Link-Pfad findet.

5-d)

Bei der Zusammenführung von Vorgänger-Seiten zu EINEM Dokument geht man davon aus, dass das Thema der Vorgängerseite gleich dem Thema der zitierten Seite ist. Das ist jedoch nicht immer wahr: Oft sind die Themen nur verwandt, aber nicht gleich. Dadurch entsteht eher eine Aufweichung der Vorhersage, als eine Verschärfung.

5-e)

Graph-Foliensatz Seite 38:

Zu Beginn werden alle (Nachbar-) Seiten mit bekannten Methoden bestmöglich klassifiziert.
Im iterativen Schritt werden diese Klassifizierungen dazu herangezogen die Klassifizierungen der benachbarten Seiten zu verfeinern.
Der Algo stoppt wenn sich die Änderungen der Klassifizierungen unterhalb eines Maßes befinden - Labeling ist stabil.

5-f)

Semi-Supervised, da Anfangs im Allgemeinen nur ein Subset an Seiten richtig klassifiziert ist. Das ist darauf zurückzuführen, dass die Klassifizierer für die initiale Klassifizierung nur einen begrenzten Satz an richtig gelabelten Seiten zur Verfügung haben.

Bei der f) bin ich mit der Formulierung nicht zufrieden. Hab mir das so gedacht: Das Trainingsset unterscheidet sich hierbei nicht vom Set aller miteinander verlinkter Seiten. Wären alle Seiten des Sets bereits markiert (Supervised), so wären auch alle Seiten richtig klassifiziert und der Algorithmus würde sofort stoppen. Dieses initiale labeling der Seiten übernehmen ja herkömmliche Klassifizierer die auf das o.g. Set losgelassen werden. Also ist die Anzahl der richtig gelabelten Seiten nur eine Teilmenge aller Seiten (Semi-Supervised). Ist die Teilmenge richtig gelabelter Seiten hingegen leer, wäre das eine unsupervised Methode - aber das will ich ihr nicht unterstellen! ^_^


Ich stehe gerade auf dem Schlauch: Der kNN Classifier hört sich for e und f auch sehr gut an, aber ich finde die dazugehören Foliensätze nicht. Wo haben wir den denn behandelt?!

Re: Klausur SS05

Verfasst: 14. Jul 2012 19:50
von h4ck4
MaMaj hat geschrieben: Ich stehe gerade auf dem Schlauch: Der kNN Classifier hört sich for e und f auch sehr gut an, aber ich finde die dazugehören Foliensätze nicht. Wo haben wir den denn behandelt?!
Skript: Text Classification -> p.11ff.

Kommt öfters bei den Klausuren vor (e.g. Klausur SS08 Aufg. 05) ;-)

kNN classifier ist dann aber supervised learning.

Aber kein Plan, ob der hier gemeint ist :-O Einfach mal paar Ideen posten ;-)

Re: Klausur SS05

Verfasst: 15. Jul 2012 11:35
von MaMaj
Okay, der kNN Classifier passt hier auch. Ich denke, dass die Antwort eh eine Kombination aus dem Kasten auf Seite 38 des Graph-Foliensatzes und dem kNN ist. Der Initialisierungschritt ist dann das bestmögliche "Vorlabeln" aller (Nachbar-) Dokumente, so dass ein complete labeled data set entsteht. Dann geht es supervised weiter indem pro iteration alle (Nachbar-) Dokumente immer weiter in ihrer Klassifikation verfeinert werden, bis sich eine Stabilisierung der Ergebnisse ergibt und der Algo stoppt.

Re: Klausur SS05

Verfasst: 15. Jul 2012 19:23
von sqrtsben
h4ck4 hat geschrieben:Klausur SS05, Aufgabe 01
(d) F-Measure, Break-Even-Point?
Ich würde da eher Average Precision und 11pt Average Precision - vgl Folie 70 im IR-Teil.