Ein Dirichlet-Prozessmodell verstehen und implementieren

11

Ich versuche, einen Dirichlet-Prozess zu implementieren und zu lernen, um meine Daten zu gruppieren (oder während die Leute beim maschinellen Lernen sprechen, schätzen Sie die Dichte).

Ich habe viel Papier zu diesem Thema gelesen und bin irgendwie auf die Idee gekommen. Aber ich bin immer noch verwirrt; Hier sind eine Reihe von Fragen,

1) Was ist der Unterschied zwischen Chinese Restaurant Model und DP? 2) Was ist der Unterschied zwischen Infinite Mixture Models und DP?

Um alles vollständig zu verstehen, habe ich das chinesische Restaurantmodell, das Polya-Urnenmodell und das Stick-Breaking implementiert. Aber es scheint, dass es schwierig ist, DP von Grund auf neu zu implementieren! Ich kann Python, R, Matlab lesen und schreiben.

1) Gibt es Code, den Sie lesen und verbessern sollten, um DP vollständig zu verstehen, zu arbeiten oder zu entwickeln? 2) Aufgrund meiner Recherchen waren Codes für den Dirichlet-Prozess nicht leicht zu lesen! wirklich lang, langwierig (wahrscheinlich da die Effizienz wichtiger war als Klarheit). 3) Das Infinite Mixture Model enthält jedoch mehr Code als der Dirichlet-Prozess. Wenn diese beiden Methoden nicht weit voneinander entfernt sind, kann ich IMM verwenden ?! Grundsätzlich möchte ich mein neues Modell aufbauen und kein Rad neu erfinden.

Ich freue mich über Ihre Kommentare

UPDATE, da viele Leute Edwin Chens Tutorial zum "Infinite Mixture Model mit nicht parametrischen Bayes und dem DP" empfohlen haben ; Dieses Tutorial hat einen irreführenden Titel. Es werden nur verschiedene Darstellungen von DP, Spezifität, CPR, Stick-Breaking und Polya-Urn-Modell behandelt. und am Ende verwendet er ein Mischungsmodell von scikit und erstellt ein paar Histogramme für jeden Cluster;

machine-learning clustering dirichlet-process user4581
quelle

Ich verstehe nicht, was für Chens Titel irreführend ist. Er benutzt ein DP-GMM von Scikit, ja.

Anne van Rossum

Yee Whye Tehs Seite: stats.ox.ac.uk/~teh/npbayes.html enthält neben einer Matlab-Implementierung eines kollabierten Gibbs-Samplers für das Dirichlet Process Mixture Model (DPMM) mehrere gute Tutorials.

Vadim Smolyakov

5

Was ist der Unterschied zwischen DP und CRP?

Der Chinese Restaurant Process (CRP) ist eine Verteilung auf Partitionen von ganzen Zahlen . Die Verbindung zum Dirichlet-Prozess (DP) besteht dank des Satzes von De Finetti.

De Finettis Theorem: Angenommen, wir haben einen zufälligen Prozess , der unendlich austauschbar ist , dann hat die gemeinsame Wahrscheinlichkeit eine Darstellung als Mischung: $(\theta_1,\ldots,\theta_N)$ $p(\theta_1,\ldots,\theta_N)$

p (θ_{1}, \dots, θ_{N}) = \int d P (G) \prod_{i = 1}^{N} G (θ_{i})

$p(\theta_1,\ldots,\theta_N)=\int dP(G) \prod_{i=1}^N G(\theta_i)$

für einige Zufallsvariable . $G$

Die Austauschbarkeitseigenschaft bedeutet, dass wir uns weder um die Indizes der Tabellen kümmern (wir benennen die Tabellen nicht), noch um die Reihenfolge der Kunden an einem bestimmten Tisch. Die Aufteilung von Kunden in verschiedene Gruppen ist die einzige Struktur, an der wir interessiert sind. Dies bedeutet, dass wir bei einer Aufteilung nicht die bestimmten Zuordnungen von Kunden zu den Tabellen kennen müssen, sondern nur die Anzahl der Kunden an jeder Tabelle.

Der Satz von De Finetti hilft nicht, die Verteilung . Es heißt nur, dass es existieren sollte. $G$

Der Dirichlet-Prozess ist ein Vorrang vor Verteilungen . Informell haben Sie eine Wahrscheinlichkeitsverteilung eingegeben, und wenn Sie eine Stichprobe daraus erstellen, erhalten Sie eine Wahrscheinlichkeitsverteilung nach der Wahrscheinlichkeitsverteilung.

Die Verbindung zwischen beiden kann hergestellt werden, indem bewiesen wird, dass, wenn aus einem Dirichlet-Prozess abgetastet wird, die Gleichung in De Finettis Theorem für dieses bestimmte . $G$ $G$

Wenn

G \sim D P (α, H)

$G \sim DP(\alpha, H)$

dann

p ({θ_{(z = 0)_{0}}, \dots, θ_{(z = 0)_{n_{0}}}}, \dots, {θ_{(z = k)_{0}}, \dots, θ_{(z = k)_{n_{k}}}}) = \frac{α^{k} Γ (α)}{Γ (α + n)} \prod_{i = 0}^{k} Γ (n_{i})

$p(\{\theta_{(z=0)_0},\ldots, \theta_{(z=0)_{n_0}}\},\ldots,\{\theta_{(z=k)_0},\ldots, \theta_{(z=k)_{n_k}}\}) = \frac{\alpha^k \Gamma(\alpha)}{\Gamma(\alpha+n)} \prod_{i=0}^k \Gamma(n_i)$

Beachten Sie, dass durch ein CRP durch Wahrscheinlichkeiten für bestimmte Partitionen beschrieben wird. Hier bezeichnet einen Tabellenindex . Und ist die Anzahl der Kunden an Tabelle . Denken Sie der Vollständigkeit halber daran, dass der : $p(\theta_1, \ldots, \theta_N)$ $z=i$ $i$ $n_i$ $i$ $DP$

{G (A_{1}), \dots, G (A_{k})} \sim D i r i c h l e t (α H (A_{1}), \dots, α H (A_{k}))

$\{G(A_1),\ldots,G(A_k)\} \sim Dirichlet(\alpha H(A_1), \ldots, \alpha H(A_k))$

Ich denke, dass aus dieser Darstellung klar hervorgeht, dass die Verbindung besteht, aber nicht als trivial angesehen werden sollte. Beachten Sie auch, dass ich das CRP nicht im Sinne einer bedingten Verteilung auf eingehende Einzelkunden beschrieben habe. Dies würde einen weiteren konzeptionellen Schritt zwischen CRP und DP hinzufügen. Mein Rat: Fühlen Sie sich frei, wenn Sie sich unwohl fühlen, wenn Sie ihre Beziehung direkt verstehen, und beginnen Sie damit, gemeinsame und marginale Verteilungen zu beschreiben, bis Sie die Verbindung reproduzieren. Das CRP wird durch Marginalisieren von aus dem DP erhalten. $G$

Zum Zusammenhang zwischen der gemeinsamen Wahrscheinlichkeit und der sequentiellen Beschreibung des CRP siehe [1].

Was ist, wenn die Austauschbarkeit nicht gilt? Wenn die Austauschbarkeit nicht gewährleistet ist, sprechen wir nicht mehr über die DP oder die CRP, sondern über den Dependent Dirichlet-Prozess und den Dependent Chinese Restaurant-Prozess. Und natürlich geht die Verbindung zwischen ihnen verloren!

Siehe [2] für Details. Das abhängige CRP beschreibt, welcher Kunde mit welchem (einzelnen) anderen Kunden zusammensitzen möchte. Durch Clustering aller Kunden-Kunden-Beziehungen können wir eine Zuordnung über Tabellen vornehmen. Das abhängige CRP ist nicht unwesentlich: Die Wahrscheinlichkeit einer Partition beim Entfernen eines Kunden hängt auch von diesem Kunden ab. Im Gegensatz dazu wird der abhängige DP häufig durch diesen sehr marginalen definiert: . Hier ist zum Beispiel eine Dirichlet-Verteilung selbst oder eine beliebige Verteilung, die bewirkt, dass und in Beziehung stehen. $G_t \sim DP(\alpha, H)$ $H$ $G_t$ $G_{t'}$

Es sind viele andere Verallgemeinerungen möglich, von denen einige eine Darstellung über Partitionen sowie über Verteilungen zulassen, wie beispielsweise den chinesischen Restaurantprozess mit zwei Parametern mit dem Pitman-Yor-Prozess oder den indischen Buffet-Prozess mit dem Beta-Prozess [3]. . Einige von ihnen werden nicht.

[1] : Ein Tutorial zu Bayes'schen nichtparametrischen Modellen (2011) Gershman und Blei
[2] : Entfernungsabhängige chinesische Restaurantprozesse (2011) Blei und Frazier
[3] : Hierarchische Beta-Prozesse und der indische Buffet-Prozess (2007) Thibaux und Jordanien

Anne van Rossum
quelle

Könnten Sie genauer erläutern, was ist und wie diese Gleichung wird abgeleitet?

θ_{{(z = i)}_{n_{i}}}

$\theta_{\left(z=i\right)_{n_{i}}}$

\frac{α^{k} Γ (α)}{Γ (α + n)} \prod_{i = 0}^{k} Γ (n_{i})

$\frac{\alpha^{k}\Gamma \left(\alpha\right)}{\Gamma \left(\alpha + n\right)}\prod_{i=0}^{k}\Gamma \left(n_{i}\right)$

Daeyoung Lim

Dies sind die Parameter von Cluster . Die Ableitung finden Sie unter math.stackexchange.com/questions/709959/… und können durch Integration der zusammengesetzten N-kategorialen Dirichlet-Verteilung erhalten werden. Erweiterung eines Prozesses, den Sie in meinem Blog unter annevanrossum.com/blog/2015/03/03/sampling-of-dirichlet-process lesen können . Es verwendet Neals technisches Papier und ich denke, es ist die detaillierteste Ableitung, die Sie online finden können.

n_{i}

$n_i$

i

$i$

Anne van Rossum

2

1) Was ist der Unterschied zwischen Chinese Restaurant Model und DP?

Keiner. CRP ist eine besondere Darstellung von DP. Abhängig von Ihrem Problem möchten Sie möglicherweise eine Darstellung über einer anderen verwenden (CRP, Stick-Breaking usw.).

2) Was ist der Unterschied zwischen Infinite Mixture Models und DP?

DP wird nur als Prior für das Infinite Mixture Model verwendet. Aus diesem Grund werden Infinite Gaussian Mixture Models auch als DP-GMM bezeichnet. Tatsächlich ist das erste Papier zu diesem Thema "The Infinite Gaussian Mixture Model" (Rasmussen, 1999).

3) Implementierungen

Ich versuche tatsächlich, Rasmussens Artikel für einen multivariaten Fall in Python zu implementieren. (Er verwendet Gibbs-Abtastung, die einfacher ist als Variationsinferenznäherungen). In der Zwischenzeit fand ich:

Ein sehr schöner Beitrag von Edwin Chen: Unendliche Mischungsmodelle mit nichtparametrischen Bayes und dem Dirichlet-Prozess
Eine Einführung in IGMM von Frank Wood / Gentle Einführung in die unendliche Gaußsche Mischungsmodellierung
Ein Versuch, das IGMM von Michael Mander zu implementieren: Implementierung des Infinite GMM . Er berichtet über einige Probleme im multivariaten Fall. Aber das war im Jahr 2005. Ich bin mir nicht sicher, ob es bereits veraltet ist und seine Probleme in Chens Beitrag oder in einem neueren Rasmussen-Artikel Dirichlet-Prozess-Gauß-Mischungsmodelle: Wahl der Basisverteilung gelöst wurden (ich sehe mir diese derzeit an.)

alberto
quelle

1

Ich kämpfe mit der gleichen Sache. Durch dieses Forum habe ich einige Hinweise gefunden:

http://scikit-learn.org/stable/modules/generated/sklearn.mixture.DPGMM.html

http://statistical-research.com/dirichlet-process-infinite-mixture-models-and-clustering/

Das erste ist die Implementierung einer unendlichen Mischung multivariater Gaußscher durch scikit-learn (lassen Sie sich nicht vom n_componentsParameter abschrecken , obwohl ich nicht sicher bin, warum es tatsächlich da ist ...).

Letzteres enthält Code in R und modelliert Dinge in einer K-Mittel-Art (ich habe den Eindruck), aber ohne K anzugeben (natürlich ;-)).

Wenn Sie weitere nützliche Pakete / Beschreibungen finden, posten Sie diese bitte!

Tom

Tom
quelle

Danke, mach die Antwort. Ich habe in Ihren zweiten Link geschaut und für mich hat er DP in seinem Beispiel nicht verwendet. Es ist sowieso eine Art K-Mittel. Lassen Sie uns diesen Beitrag aktualisieren, indem wir nützliche Pakete / Beschreibungen einfügen.

user4581

Ich habe genau das Gleiche gedacht. Im Code bezieht er sich jedoch darauf dirichletClusters, also dachte ich, ich hätte mich geirrt. Aber ich sehe die DP auch nicht darin ...

Tom

Schauen Sie sich diesen Videovortrag von Teh selbst an: videolectures.net/mlss09uk_teh_nbm Ungefähr in Minute 43 gibt es einige Gleichungen, die ich für wirklich hilfreich halte!

Tom

Um Sie zu aktualisieren, gibt es ein R-Paket namens DIRECT. hat eine sehr klare Implementierung von DP! Ich fing an, den Code zu lesen und mich weiterzubilden! Ich empfehle Ihnen, einen Blick darauf zu werfen

user4581

1

Ein sehr verständlicher Code von Jacob Eisenstein ist für Matlab unter https://github.com/jacobeisenstein/DPMM verfügbar . Es basiert auf der Dissertation "Grafische Modelle zur visuellen Objekterkennung und -verfolgung" von EB Sudderth.

Maxim Do.
quelle

Ein Dirichlet-Prozessmodell verstehen und implementieren

Antworten: