Dirichlet-Prozesse für Clustering: Wie gehe ich mit Etiketten um?

14

F: Was ist die Standardmethode zum Clustering von Daten mithilfe eines Dirichlet-Prozesses?

Bei Verwendung von Gibbs treten während der Probenahme Cluster auf und verschwinden. Außerdem haben wir ein Identifizierungsproblem, da die posteriore Verteilung für Cluster-Relabelings nicht relevant ist. Wir können also nicht sagen, welches der Cluster eines Benutzers ist, sondern dass sich zwei Benutzer in demselben Cluster befinden (dh p(ci=cj) ).

Können wir die Klassenzuordnungen so zusammenfassen, dass wir, wenn die Clusterzuordnung von Punkt , nicht nur sondern auch ? i c i = c jciici=cjci=cj=cj=...=cz

Dies sind die Alternativen, die ich gefunden habe und warum ich denke, dass sie unvollständig oder falsch sind.

(1) DP-GMM + Gibbs-Abtastung + paarbasierte Verwirrungsmatrix

Um ein Dirichlet-Prozess-Gauß-Mischungsmodell (DP-GMM) für ein Clustering zu verwenden, implementierte ich dieses Papier, in dem die Autoren ein DP-GMM für die Dichteschätzung unter Verwendung von Gibbs-Stichproben vorschlagen .

Um die Clustering-Leistung zu untersuchen, heißt es:

Da sich die Anzahl der Komponenten über die [MCMC] -Kette ändert, müsste eine Verwirrungsmatrix gebildet werden, die die Häufigkeit jedes Datenpaars angibt, das derselben Komponente für die gesamte Kette zugewiesen ist (siehe 6). Bildbeschreibung hier eingeben

Nachteile : Dies ist kein echtes "vollständiges" Clustering, sondern ein paarweises Clustering. Die Abbildung sieht so gut aus, weil wir die realen Cluster kennen und die Matrix entsprechend anordnen.

(2) DP-GMM + Gibbs-Probenahme + Probe, bis sich nichts mehr ändert

Ich habe gesucht und einige Leute gefunden, die behaupteten, mit einem Gibbs-Sampler Clustering auf der Basis des Dirichlet-Prozesses durchzuführen. In diesem Beitrag wird beispielsweise davon ausgegangen, dass die Kette konvergiert, wenn sich weder die Anzahl der Cluster noch die Mittelwerte geändert haben, und daher die Zusammenfassungen von dort abgerufen.

Nachteile : Ich bin mir nicht sicher, ob dies erlaubt ist, wenn ich mich nicht irre:

  • (a) Während der MCMC kann es zu Etikettenwechseln kommen.

  • (b) Selbst in der stationären Verteilung kann der Sampler von Zeit zu Zeit einen Cluster erzeugen.

(3) DP-GMM + Gibbs-Sampling + Sample mit der wahrscheinlichsten Partition auswählen

In diesem Artikel sagen die Autoren:

Nach einer Einbrennphase können aus dem Gibbs-Probenehmer unverfälschte Proben aus der posterioren Verteilung des IGMM entnommen werden. Eine harte Clusterbildung kann festgestellt werden, indem viele solcher Stichproben gezogen und die Stichprobe mit der höchsten gemeinsamen Wahrscheinlichkeit der Klassenindikatorvariablen verwendet werden. Wir verwenden eine modifizierte IGMM-Implementierung von M. Mandel .

Nachteile : Sofern es sich nicht um einen Collapsed Gibbs-Sampler handelt, bei dem nur die Zuordnungen abgetastet werden, können wir berechnen , nicht jedoch das marginale p ( c ) . (Wäre es eine gute Übung, stattdessen den Zustand mit dem höchsten p ( c , θ ) zu erhalten ?)p(c|θ)p(c)p(c,θ)

(4) DP-GMM mit variatonaler Inferenz :

Ich habe gesehen, dass einige Bibliotheken Variationsinferenz verwenden. Ich kenne Variational Inference nicht sehr gut, aber ich vermute, dass Sie dort keine Identifizierungsprobleme haben. Ich möchte mich jedoch (wenn möglich) an MCMC-Methoden halten.

Jeder Hinweis wäre hilfreich.

alberto
quelle
p(c)
p(c)
das ist so gewollt . Tatsächlich geht es über MCMC hinaus: Es ist ein eingebautes Merkmal jedes Bayes'schen Modells. Wenn überhaupt, stoßen Sie auf ein Problem, weil Sie versuchen, etwas Unnatürliches zu tun, etwas, von dem wir besessen sind: eine Verteilungsschätzung in eine Punktschätzung zu
stopfen
Es gibt Gründe, warum Sie so etwas überhaupt nicht machen wollen - es gibt verschiedene Möglichkeiten, in denen das Dirichlet-Prozessmischungsmodell die Anzahl der Cluster nicht einheitlich abschätzen kann (und daher die Wiederherstellung eines " true "Clustering der Daten). Zu diesem Thema gab es kürzlich einen Artikel bei NIPS.
Kerl
1
Sehen Sie hier . Ich denke, sie schlagen stattdessen vor, ein Poisson vor die Anzahl der Komponenten zu setzen (und eine Art Restaurantprozess abzuleiten, um es zu implementieren), aber ich bin nicht sicher, ob dies das Papier ist, das sie tun.
Kerl

Antworten:

1

Meine vorläufige Antwort wäre, als Parameter zu behandeln, so dass p ( c , θ ) einfach der hintere Modus ist. Ich vermute, dass Niekum und Barto dies getan haben (das in Option 3 genannte Papier). Der Grund, warum sie vage waren, ob sie p verwendetencp(c,θ)p(c,θ)p(c|θ)

Der Grund, warum ich diese Antwort als "vorläufig" bezeichne, ist, dass ich nicht sicher bin, ob die Bezeichnung eines Wertes als "Parameter" nur eine Frage der Semantik ist oder ob es eine technisch / theoretischere Definition gibt, als einer der Doktoranden hier wäre zu klären.

Shadowtalker
quelle
p(c,θ)=p(c|θ)p(θ)p(c)
@alberto nochmal, das hat nichts mit diesem Modell zu tun und alles was mit Bayes'schen Statistiken zu tun hat. Siehe hier: groups.google.com/forum/m/#!topic/stan-users/qH-2Mq219gs . Und wenn Sie sich Sorgen um mehrere Modi machen, lesen Sie hier: groups.google.com/forum/m/#topic/stan-users/RsVo9NUn0yM und hier: stats.stackexchange.com/q/3328/36229
shadowtalker
1

Ich wollte nur einige Ressourcen zum Thema teilen, in der Hoffnung, dass einige von ihnen bei der Beantwortung dieser Frage hilfreich sein könnten. Es gibt viele Tutorials zu Dirichlet-Prozessen (DP) , darunter einige zur Verwendung von DP für Clustering . Sie reichen von "sanft", wie in diesem Präsentationstutorial , bis zu fortgeschritteneren, wie in diesem Präsentationstutorial . Letzteres ist eine aktualisierte Version des gleichen Tutorials, das Yee Whye Teh auf der MLSS'07 vorgestellt hat. Das Video zu diesem Gespräch mit synchronisierten Folien können Sie hier ansehen . Sprechen über Videos, können Sie ein weiteren interessanten und relevanten Vortrag mit Dia von Tom Griffith sehen hier . In Bezug auf die papierformatierten Tutorials ist dieses Tutorial ist eine schöne und sehr beliebte.

Abschließend möchte ich noch einige verwandte Arbeiten vorstellen. Dieses Papier über hierarchische EP scheint wichtig und relevant zu sein. Gleiches gilt für dieses Papier von Radford Neal. Wenn Sie interessiert sind Thema Modellierung , latente Dirichlet Allocation (LDA) sollte höchstwahrscheinlich auch auf dem Radar sein. In diesem Fall präsentiert dieses kürzlich erschienene Papier einen neuartigen und stark verbesserten LDA-Ansatz. In Bezug auf das Thema Modellierung würde ich empfehlen, Forschungsarbeiten von David Blei und seinen Mitarbeitern zu lesen. Dieser Artikel ist eine Einführung, den Rest finden Sie auf seiner Seite mit Forschungspublikationen. Mir ist klar, dass einige der von mir empfohlenen Materialien zu einfach für Sie sein könnten, aber ich dachte, dass Sie die Chance erhöhen würden, eine Antwort zu finden, wenn Sie alles einbeziehen, was ich zu diesem Thema gesagt habe .

Aleksandr Blekh
quelle
Ich verstehe, was Sie hier versuchen, aber es geht wirklich nicht um die Frage.
Shadowtalker
1
@ssdecontrol: Wenn Sie verstehen, was ich hier zu tun versuche (was dem OP hilft, die Antwort zu finden und ein oder zwei Dinge zu lernen), worum geht es dann in Ihrem Kommentar? Ich habe nie behauptet, dass meine Antwort die Antwort ist, habe aber die Hoffnung geäußert, dass sie hilfreich ist , was letztendlich dem OP überlassen bleibt. Wenn Sie eine bessere Antwort haben, bin ich sicher, dass dies vom OP und der Community geschätzt wird.
Aleksandr Blekh
1
Ja, ich verstehe das total. Das ist eine Menge von dem, was ich auch hier mache. Die Frage ist jedoch, wie Cluster-Labels aus MCMC-Ergebnissen richtig herausgesucht werden können, und ich denke, dass diese Frage hier überhaupt nicht beantwortet wird.
Shadowtalker
@AleksandrBlekh Ich würde ssdecontrol zustimmen, dass es ein wenig vom Thema abweicht, da OP die "Grundlagen" zu kennen scheint und eine bestimmte Frage stellt.
Tim
1
@AleksandrBlekh Ich weiß deinen Beitrag zu schätzen, zumindest macht er eine gute Zusammenfassung für eine Einführung in DP. Ich kenne die Grundlagen (zum Beispiel für Fortgeschrittene), aber zumindest haben mich Ihre Referenzen dazu veranlasst, zur LDA zurückzukehren und festzustellen, dass sie das Problem auf Zehenspitzen umgehen, da ihre Labels häufig nicht wechseln.
Alberto