Das Dirichlet-Prozessmischungsmodell

• 23. Juni 2014
• Vasilis Vryniotis
• . 2 Kommentare

Dieser Blog-Beitrag ist der vierte Teil der Serie über Clustering mit Dirichlet-Prozessmischungsmodellen. In früheren Artikeln haben wir die Finite-Dirichlet-Mischungsmodelle diskutiert und die Grenze ihres Modells für unendliche k-Cluster genommen, was uns zur Einführung von Dirichlet-Prozessen führte. Wie wir gesehen haben, besteht unser Ziel darin, ein Mischungsmodell zu erstellen, bei dem wir nicht von Anfang an die Anzahl der k Cluster / Komponenten angeben müssen. Nach dem Präsentation verschiedener Darstellungen von Dirichlet-ProzessenJetzt ist es an der Zeit, mithilfe von DPs ein unendliches Mischungsmodell zu erstellen, mit dem wir Clustering durchführen können. Das Ziel dieses Artikels ist es, die Dirichlet-Prozessmischungsmodelle zu definieren und die Verwendung des chinesischen Restaurantprozesses und der Gibbs-Probenahme zu diskutieren. Wenn Sie die vorherigen Beiträge nicht gelesen haben, wird dies dringend empfohlen, da das Thema etwas theoretisch ist und ein gutes Verständnis für die Konstruktion des Modells erfordert.

Update: Das Datumbox Machine Learning Framework ist jetzt Open Source und kostenlos für herunterladen. Schauen Sie sich das Paket com.datumbox.framework.machinelearning.clustering an, um die Implementierung von Dirichlet Process Mixture Models in Java zu sehen.

1. Definition des Dirichlet-Prozessmischungsmodells

Die Verwendung von Dirichlet-Prozessen ermöglicht es uns, ein Mischungsmodell mit unendlichen Komponenten zu haben, von dem angenommen werden kann, dass es die Grenze des endlichen Modells für k bis unendlich nimmt. Nehmen wir an, wir haben das folgende Modell:

Gleichung 1: Dirichlet-Prozessmischungsmodell

Wobei G definiert ist als und wird als Kurznotation für verwendet Dies ist eine Delta-Funktion, die 1 if benötigt und 0 anderswo. Das θ_i sind die Clusterparameter, die aus G abgetastet werden. Die generative Verteilung F wird durch Clusterparameter & thgr; konfiguriert_i und wird verwendet, um x zu erzeugen_i Beobachtungen. Schließlich können wir eine Dichteverteilung definieren Das ist unsere Mischungsverteilung (zählbare unendliche Mischung) mit Mischungsverhältnissen und Mischen von Komponenten .

Abbildung 1: Grafisches Modell des Dirichlet-Prozessmischungsmodells

Oben sehen wir das äquivalente grafische Modell des DPMM. Der G.₀ ist die Basisverteilung von DP und wird normalerweise so ausgewählt, dass sie vor unserer generativen Verteilung F konjugiert wird, um die Berechnungen zu vereinfachen und die ansprechenden mathematischen Eigenschaften zu nutzen. Das α ist der skalare Hyperparameter des Dirichlet-Prozesses und beeinflusst die Anzahl der Cluster, die wir erhalten werden. Je größer der Wert von α ist, desto mehr Cluster; Je kleiner das α, desto weniger Cluster. Wir sollten beachten, dass der Wert von α ausdrückt die Stärke des Glaubens in G.₀. Ein großer Wert zeigt an, dass die meisten Proben unterschiedlich sind und Werte haben, die auf G konzentriert sind₀. Das G ist eine zufällige Verteilung über den vom DP abgetasteten Parameterraum, die den Parametern Wahrscheinlichkeiten zuweist. Das θ_i ist ein Parametervektor, der aus der G-Verteilung gezogen wird und die Parameter des Clusters enthält. Die F-Verteilung wird durch θ parametrisiert_i und x_i ist der Datenpunkt, der von der generativen Verteilung F erzeugt wird.

Es ist wichtig zu beachten, dass θ_i sind Elemente des Θ-Parameterraums und „konfigurieren“ unsere Cluster. Sie können auch als latente Variablen auf x angesehen werden_i welche sagen uns aus welcher Komponente / Cluster das x_i kommt von und was sind die Parameter dieser Komponente. Also für jedes x_i dass wir beobachten, zeichnen wir ein θ_i aus der G-Verteilung. Bei jeder Ziehung ändert sich die Verteilung in Abhängigkeit von der vorherigen Auswahl. Wie wir im Urnenschema von Blackwell-MacQueen gesehen haben, kann die G-Verteilung und unsere zukünftige Auswahl von θ integriert werden_i hängen nur von G ab₀: . Das Schätzen der Parameter & thgr; i aus der vorherigen Formel ist nicht immer möglich, da viele Implementierungen (wie der chinesische Restaurantprozess) das Aufzählen durch das beinhalten exponentiell ansteigende k Komponenten. Daher werden ungefähre Berechnungsmethoden wie Gibbs Sampling verwendet. Schließlich sollten wir beachten, dass obwohl die k Cluster unendlich sind, die Anzahl der aktiven Cluster ist . Also das θ_i wird wiederholt und zeigt einen Clustering-Effekt.

2. Verwenden des chinesischen Restaurantprozesses zum Definieren eines unendlichen Mischungsmodells

Das im vorherigen Segment definierte Modell ist mathematisch solide, hat jedoch einen großen Nachteil: für jedes neue x_i dass wir beobachten, müssen wir ein neues θ abtasten_i unter Berücksichtigung der vorherigen Werte von θ. Das Problem ist, dass das Abtasten dieser Parameter in vielen Fällen eine schwierige und rechenintensive Aufgabe sein kann.

Ein alternativer Ansatz besteht darin, den chinesischen Restaurantprozess zu verwenden, um die latenten Variablen zu modellieren. Z._i von Clusterzuweisungen. Auf diese Weise anstelle von θ_i Um sowohl die Clusterparameter als auch die Clusterzuweisungen zu bezeichnen, verwenden wir die latente Variable z_i um die Cluster-ID anzugeben und diesen Wert dann zum Zuweisen der Cluster-Parameter zu verwenden. Infolgedessen müssen wir nicht mehr jedes Mal, wenn wir eine neue Beobachtung erhalten, ein θ abtasten, sondern wir erhalten die Clusterzuordnung durch Abtasten von z_i von CRP. Mit diesem Schema wird ein neues θ nur dann abgetastet, wenn ein neuer Cluster erstellt werden muss. Nachfolgend präsentieren wir das Modell dieses Ansatzes:

Gleichung 2: Mischungsmodell mit CRP

Das Obige ist ein generatives Modell, das beschreibt, wie die Daten x_i und die Cluster werden erzeugt. Um die Clusteranalyse durchzuführen, müssen wir die Beobachtungen x verwenden_i und schätzen Sie die Clusterzuweisungen z_i.

3. Inferenz des Mischungsmodells und Gibbs-Abtastung

Da Dirichlet-Prozesse nicht parametrisch sind, haben wir leider EM-Algorithmus kann nicht verwendet werden um die latenten Variablen zu schätzen, in denen die Clusterzuweisungen gespeichert sind. Um die Zuordnungen abzuschätzen, verwenden wir die Kollabierte Gibbs-Sampling.

Das Collapsed Gibbs Sampling ist ein einfacher Markov Chain Monte Carlo (MCMC) -Algorithmus. Es ist schnell und ermöglicht es uns, einige Variablen zu integrieren, während wir eine andere Variable abtasten. Trotzdem müssen wir für diesen Algorithmus ein G auswählen₀ Dies ist ein Konjugat vor der generativen F-Verteilung, um die Gleichungen analytisch lösen und direkt daraus abtasten zu können .

Die Schritte der Collapsed Gibbs-Stichprobe, mit denen wir die Clusterzuweisungen schätzen, sind die folgenden:

• Initialisieren Sie die z_i Clusterzuweisungen zufällig
• Wiederholen bis zur Konvergenz
• Wählen Sie zufällig Axt_i
  
• Behalte den anderen z_j fest für jedes j ≠ i:
• Weisen Sie z einen neuen Wert zu_i durch Berechnung der „CRP-Wahrscheinlichkeit“, die von z abhängt_j und x_j von allen j ≠ i:

Im nächsten Artikel konzentrieren wir uns auf die Durchführung von Clusteranalysen mithilfe von Dirichlet Process Mixture-Modellen. Wir werden zwei verschiedene Dirichlet-Prozessmischungsmodelle definieren, die den chinesischen Restaurantprozess und die kollabierte Gibbs-Stichprobe verwenden, um Clustering für kontinuierliche Datensätze und Dokumente durchzuführen.