Dirichlet-Verfahren - Dirichlet process

Zieht aus dem Dirichlet-Verfahren . Die vier Reihen verwenden unterschiedliche Alpha (von oben nach unten: 1, 10, 100 und 1000) und jede Reihe enthält drei Wiederholungen desselben Experiments. Wie aus den Diagrammen ersichtlich, sind die Ziehungen eines Dirichlet-Prozesses diskrete Verteilungen und sie werden mit zunehmender Konzentration weniger konzentriert (mehr verteilt) . Die Grafiken wurden unter Verwendung der Stick-Breaking-Prozessansicht des Dirichlet-Prozesses erstellt.${\displaystyle \operatorname {DP} (N(0,1),\alpha )}$${\displaystyle\alpha}$${\displaystyle\alpha}$

In der Wahrscheinlichkeitstheorie , Prozesse Dirichlet (nach Peter Gustav Lejeune Dirichlet ) sind eine Familie von stochastischen Prozessen , deren Realisierungen sind Wahrscheinlichkeitsverteilungen . Mit anderen Worten, ein Dirichlet-Prozess ist eine Wahrscheinlichkeitsverteilung, deren Bereich selbst ein Satz von Wahrscheinlichkeitsverteilungen ist. Es wird in der Bayesschen Inferenz häufig verwendet , um das Vorwissen über die Verteilung von Zufallsvariablen zu beschreiben – wie wahrscheinlich es ist, dass die Zufallsvariablen gemäß der einen oder anderen bestimmten Verteilung verteilt sind.

Als Beispiel ist ein Beutel mit 100 echten Würfeln ein zufälliger pmf - um diesen zufälligen pmf zu probieren, stecken Sie Ihre Hand in den Beutel und ziehen einen Würfel, dh Sie ziehen einen pmf. Eine Tüte mit Würfeln, die vor 100 Jahren in einem groben Verfahren hergestellt wurde, wird wahrscheinlich Wahrscheinlichkeiten haben, die stark von der einheitlichen pmf abweichen, während eine Tüte mit hochmodernen Würfeln, die von Casinos in Las Vegas verwendet wird, kaum wahrnehmbare Unvollkommenheiten aufweisen kann. Wir können die Zufälligkeit von pmfs mit der Dirichlet-Verteilung modellieren.

Der Dirichlet-Prozess wird durch eine Basisverteilung und eine positive reelle Zahl spezifiziert, die als Konzentrationsparameter (auch als Skalierungsparameter bezeichnet) bezeichnet wird. Die Basisverteilung ist der Erwartungswert des Prozesses, dh der Dirichlet-Prozess zeichnet Verteilungen "um" die Basisverteilung, wie eine Normalverteilung reelle Zahlen um ihren Mittelwert zieht. Aber selbst wenn die Basisverteilung stetig ist , sind die Verteilungen aus dem Dirichlet-Prozess fast sicher diskret . Der Skalierungsparameter gibt an, wie stark diese Diskretisierung ist: Im Grenzwert von werden die Realisierungen alle auf einen einzigen Wert konzentriert, während im Grenzwert der Realisierungen stetig werden. Zwischen den beiden Extremen sind die Realisierungen diskrete Verteilungen mit immer geringerer Konzentration als Zunahmen. ${\displaystyle H}$ ${\displaystyle\alpha}$ ${\displaystyle \alpha \rightarrow 0}$${\displaystyle \alpha \rightarrow\infty}$${\displaystyle\alpha}$

Der Dirichlet-Prozess kann auch als unendlichdimensionale Verallgemeinerung der Dirichlet-Verteilung angesehen werden . So wie die Dirichlet-Verteilung der konjugierte Prior für die kategoriale Verteilung ist , ist der Dirichlet-Prozess der konjugierte Prior für unendliche, nichtparametrische diskrete Verteilungen. Eine besonders wichtige Anwendung der Dirichlet-Prozesse ist als A- priori-Wahrscheinlichkeitsverteilung in Modellen für unendliche Mischungen .

Das Dirichlet-Verfahren wurde 1973 von Thomas Ferguson offiziell eingeführt. Es wird seitdem im Data Mining und Machine Learning angewendet , unter anderem für die Verarbeitung natürlicher Sprache , Computer Vision und Bioinformatik .

Besonders bewährt hat sich das Dirichlet bei der Modellierung der Wortverteilung in Textdokumenten. Wenn wir ein Wörterbuch haben, das k mögliche Wörter enthält, kann ein bestimmtes Dokument durch ein pmf der Länge k repräsentiert werden, das durch Normalisieren der empirischen Häufigkeit seiner Wörter erzeugt wird. Eine Gruppe von Dokumenten erzeugt eine Sammlung von pmfs, und wir können eine Dirichlet-Verteilung anpassen, um die Variabilität dieser pmfs zu erfassen. Verschiedene Dirichlet-Distributionen können verwendet werden, um Dokumente von verschiedenen Autoren oder Dokumente zu verschiedenen Themen zu modellieren.

Einführung

Dirichlet-Prozesse werden normalerweise verwendet, wenn Daten modelliert werden, die dazu neigen, vorherige Werte in einer sogenannten "rich get richer"-Weise zu wiederholen. Angenommen, die Erzeugung von Werten kann durch den folgenden Algorithmus simuliert werden. ${\displaystyle X_{1},X_{2},\dots}$

Eingabe: (eine Wahrscheinlichkeitsverteilung, die als Basisverteilung bezeichnet wird), (eine positive reelle Zahl, die als Skalierungsparameter bezeichnet wird )${\displaystyle H}$${\displaystyle\alpha}$

Für :${\displaystyle n\geq 1}$

Gleichzeitig besteht ein weiteres gängiges Modell für Daten darin, dass die Beobachtungen als unabhängig und identisch verteilt (iid) gemäß einer (zufälligen) Verteilung angenommen werden . Ziel der Einführung von Dirichlet-Prozessen ist es, die oben skizzierte Vorgehensweise in diesem iid-Modell beschreiben zu können. ${\displaystyle X_{1},X_{2},\dots}$${\displaystyle P}$

Die Beobachtungen im Algorithmus sind nicht unabhängig , da wir bei der Generierung des nächsten Wertes die vorherigen Ergebnisse berücksichtigen müssen. Sie sind jedoch austauschbar . Diese Tatsache lässt sich zeigen, indem man die gemeinsame Wahrscheinlichkeitsverteilung der Beobachtungen berechnet und feststellt, dass die resultierende Formel nur davon abhängt, welche Werte unter den Beobachtungen vorkommen und wie viele Wiederholungen sie jeweils haben. Wegen dieser Austauschbarkeit gilt der Darstellungssatz von de Finetti, der impliziert, dass die Beobachtungen bei einer gegebenen (latenten) Verteilung bedingt unabhängig sind . Dies ist selbst eine Zufallsvariable und hat eine Verteilung. Diese Verteilung (über Verteilungen) wird als Dirichlet-Prozess ( ) bezeichnet. Zusammenfassend bedeutet dies, dass wir ein äquivalentes Verfahren zum obigen Algorithmus erhalten: ${\displaystyle X_{1},X_{2},\dots}$${\displaystyle x}$${\displaystyle X_{1},X_{2},\dots}$${\displaystyle P}$${\displaystyle P}$${\displaystyle \operatorname {DP} }$

1. Zeichnen Sie eine Verteilung von${\displaystyle P}$${\displaystyle \operatorname {DP} \left(H,\alpha \right)}$
2. Zeichnen Sie Beobachtungen unabhängig von .${\displaystyle X_{1},X_{2},\dots}$${\displaystyle P}$

In der Praxis ist es jedoch unmöglich, eine konkrete Verteilung zu zeichnen , da deren Spezifikation unendlich viele Informationen erfordert. Dies ist ein häufiges Phänomen im Kontext der Bayesschen nichtparametrischen Statistik, wo eine typische Aufgabe darin besteht, Verteilungen auf Funktionsräumen zu lernen, die effektiv unendlich viele Parameter beinhalten. Die entscheidende Erkenntnis besteht darin, dass die unendlichdimensionalen Verteilungen in vielen Anwendungen nur als Zwischenrechenmittel erscheinen und weder für die anfängliche Spezifikation der vorherigen Überzeugungen noch für die Aussage der endgültigen Schlussfolgerung erforderlich sind. ${\displaystyle P}$

Formale Definition

Bei einer meßbaren Menge S einer Basiswahrscheinlichkeitsverteilung H und eine positive reelle Zahl , der Dirichlet - Prozess ein stochastischer Prozess , dessen Probenweg (oder Umsetzung , also eine unendliche Folge von Zufallszahlen aus dem Prozess gezogen) ist eine Wahrscheinlichkeitsverteilung über S , so dass folgendes gilt. Für jede messbare endliche Partition von S , bezeichnet mit , ${\displaystyle\alpha}$${\displaystyle \operatorname {DP} (H,\alpha)}$${\displaystyle \{B_{i}\}_{i=1}^{n}}$

${\displaystyle {\text{if }}X\sim\operatorname {DP} (H,\alpha)}$

${\displaystyle {\text{then }}(X(B_{1}),\dots ,X(B_{n}))\sim \operatorname {Dir} (\alpha H(B_{1}),\dots ,\alpha H(B_{n})),}$

wobei bezeichnet die Dirichlet-Verteilung und die Notation bedeutet, dass die Zufallsvariable die Verteilung hat . ${\displaystyle \operatorname {Dir}}$${\displaystyle X\sim D}$${\displaystyle X}$${\displaystyle D}$

Alternative Ansichten

Es gibt mehrere gleichwertige Ansichten des Dirichlet-Prozesses. Neben der obigen formalen Definition kann der Dirichlet-Prozess implizit durch den Satz von de Finetti, wie im ersten Abschnitt beschrieben, definiert werden; Dies wird oft als chinesischer Restaurantprozess bezeichnet . Eine dritte Alternative ist der stick-Brechvorgang , der den Dirichlet Prozess definiert konstruktiv durch eine Verteilung aus dem Prozeß abgetastete Schreiben als , wo Proben aus der Basisverteilung sind , ist eine Indikatorfunktion auf zentrierte (Null überall mit Ausnahme ) und die definiert sind durch ein rekursives Schema, das wiederholt Proben aus der Beta-Verteilung abtastet . ${\displaystyle f(x)=\sum_{k=1}^{\infty}\beta_{k}\delta_{x_{k}}(x)}$${\displaystyle \{x_{k}\}_{k=1}^{\infty}}$${\displaystyle H}$${\displaystyle \delta_{x_{k}}}$${\displaystyle x_{k}}$${\displaystyle \delta_{x_{k}}(x_{k})=1}$${\displaystyle \beta_{k}}$ ${\displaystyle \operatorname {Beta} (1,\alpha)}$

Der chinesische Restaurantprozess

Animation eines chinesischen Restaurantprozesses mit Skalierungsparameter . Tische werden ausgeblendet, wenn die Kunden eines Tisches nicht mehr angezeigt werden können; jedoch hat jeder Tisch unendlich viele Sitzplätze. (Aufzeichnung einer interaktiven Animation.)${\displaystyle \alpha =0.5}$

Eine weit verbreitete Metapher für den Dirichlet-Prozess basiert auf dem sogenannten chinesischen Restaurantprozess . Die Metapher lautet wie folgt:

Stellen Sie sich ein chinesisches Restaurant vor, in das Kunden eintreten. Ein neuer Kunde setzt sich mit einer Wahrscheinlichkeit proportional zur Anzahl der bereits dort sitzenden Kunden an einen Tisch. Außerdem öffnet ein Kunde eine neue Tabelle mit einer Wahrscheinlichkeit proportional zum Skalierungsparameter . Nach unendlich vielen eingegebenen Kunden erhält man eine Wahrscheinlichkeitsverteilung über unendlich viele zu wählende Tabellen. Diese Wahrscheinlichkeitsverteilung über die Tabellen ist eine zufällige Stichprobe der Wahrscheinlichkeiten von Beobachtungen, die aus einem Dirichlet-Prozess mit Skalierungsparameter gezogen wurden . ${\displaystyle\alpha}$${\displaystyle\alpha}$

Verknüpft man mit jeder Tabelle Ziehungen aus dem Basismaß, ergibt sich als Verteilung über den Stichprobenraum eine Zufallsstichprobe eines Dirichlet-Prozesses. Der chinesische Restaurantprozess ist mit dem Pólya-Urnenstichprobenschema verbunden, das Stichproben aus endlichen Dirichlet-Verteilungen liefert. ${\displaystyle H}$${\displaystyle S}$

Da Kunden mit einer Wahrscheinlichkeit proportional zur Anzahl der bereits am Tisch sitzenden Kunden an einem Tisch sitzen, lassen sich zwei Eigenschaften des DP ableiten:

1. Das Dirichlet-Verfahren weist eine sich selbst verstärkende Eigenschaft auf: Je öfter ein gegebener Wert in der Vergangenheit abgetastet wurde, desto wahrscheinlicher wird er erneut abgetastet.
2. Selbst wenn es sich um eine Verteilung über eine unzählbare Menge handelt , besteht eine Wahrscheinlichkeit ungleich Null, dass zwei Stichproben genau denselben Wert haben, da sich die Wahrscheinlichkeitsmasse auf eine kleine Anzahl von Tabellen konzentriert.${\displaystyle H}$

Der Stick-Break-Prozess

Ein dritter Ansatz für das Dirichlet-Verfahren ist die sogenannte Stick-Breaking-Prozesssicht. Konzeptionell beinhaltet dies das wiederholte Abbrechen und Verwerfen eines zufälligen Bruchteils (abgetastet aus einer Beta-Verteilung) eines "Stabs", der anfänglich die Länge 1 hat. Denken Sie daran, dass Ziehungen aus einem Dirichlet-Prozess Verteilungen über eine Menge sind . Wie bereits erwähnt, ist die gezeichnete Verteilung diskret mit Wahrscheinlichkeit 1. In der Prozessansicht des Stick-Breaking-Prozesses verwenden wir explizit die Diskretheit und geben die Wahrscheinlichkeits-Massenfunktion dieser (zufälligen) diskreten Verteilung an als: ${\displaystyle S}$

${\displaystyle f(\theta)=\sum_{k=1}^{\infty}\beta_{k}\cdot\delta_{\theta_{k}}(\theta)}$

Wo ist die Indikatorfunktion, die überall zu Null ausgewertet wird, außer für . Da diese Verteilung selbst zufällig ist, wird ihre Massenfunktion durch zwei Sätze von Zufallsvariablen parametrisiert: die Orte und die entsprechenden Wahrscheinlichkeiten . Im Folgenden stellen wir ohne Beweis dar, was diese Zufallsvariablen sind. ${\displaystyle \delta_{\theta_{k}}}$${\displaystyle \delta_{\theta_{k}}(\theta_{k})=1}$${\displaystyle \left\{\theta_{k}\right\}_{k=1}^{\infty}}$${\displaystyle \left\{\beta_{k}\right\}_{k=1}^{\infty}}$

Die Standorte sind unabhängig und identisch verteilt nach , der Basisverteilung des Dirichlet-Verfahrens. Die Wahrscheinlichkeiten werden durch ein Verfahren gegeben, das dem Brechen eines Stabes von Einheitslänge ähnelt (daher der Name): ${\displaystyle \theta_{k}}$${\displaystyle H}$${\displaystyle \beta_{k}}$

${\displaystyle \beta_{k}=\beta'_{k}\cdot \prod_{i=1}^{k-1}\left(1-\beta'_{i}\right)}$

wo sind unabhängige Zufallsvariablen mit der Beta-Verteilung . Die Ähnlichkeit mit dem "Stöckchenbrechen" kann man sehen, wenn man die Länge eines Stücks eines Stockes betrachtet. Wir beginnen mit einem Stab von einer Einheitslänge und brechen in jedem Schritt einen Teil des verbleibenden Stabes gemäß ab und ordnen dieses abgebrochene Stück zu . Die Formel kann verstanden werden, indem man feststellt, dass, nachdem die ersten k  − 1 Werte ihre Teile zugewiesen haben, die Länge des Restes des Stabes ist und dieses Stück entsprechend gebrochen und zugewiesen wird . ${\displaystyle \beta '_{k}}$ ${\displaystyle \operatorname {Beta} (1,\alpha)}$${\displaystyle \beta_{k}}$${\displaystyle \beta '_{k}}$${\displaystyle \beta_{k}}$${\displaystyle \prod_{i=1}^{k-1}\left(1-\beta '_{i}\right)}$${\displaystyle \beta '_{k}}$${\displaystyle \beta_{k}}$

Je kleiner ist, desto weniger Stick wird für nachfolgende Werte (im Durchschnitt) übrig bleiben, was zu konzentrierteren Verteilungen führt. ${\displaystyle\alpha}$

Der Stick-Break-Prozess ähnelt der Konstruktion, bei der man sequentiell von marginalen Beta-Verteilungen abtastet, um eine Stichprobe von einer Dirichlet-Verteilung zu erzeugen . Siehe für den Beweis.

Das Urnenschema von Pólya

Eine weitere Möglichkeit, den Dirichlet-Prozess und den chinesischen Restaurantprozess zu visualisieren, ist ein modifiziertes Pólya-Urnenschema, das manchmal als Blackwell-MacQueen- Stichprobenschema bezeichnet wird. Stellen Sie sich vor, wir beginnen mit einer Urne, die mit schwarzen Kugeln gefüllt ist . Dann gehen wir wie folgt vor: ${\displaystyle\alpha}$

1. Jedes Mal, wenn wir eine Beobachtung brauchen, ziehen wir eine Kugel aus der Urne.
2. Wenn die Kugel schwarz ist, erzeugen wir einheitlich eine neue (nicht schwarze) Farbe, beschriften eine neue Kugel mit dieser Farbe, legen die neue Kugel zusammen mit der gezogenen Kugel in die Urne und geben die von uns generierte Farbe zurück.
3. Andernfalls beschriften Sie einen neuen Ball mit der Farbe des von uns gezeichneten Balls, legen Sie den neuen Ball zusammen mit dem gezeichneten Ball in die Urne und geben Sie die Farbe zurück, die wir beobachtet haben.

Die resultierende Verteilung über die Farben ist dieselbe wie die Verteilung über die Tische im chinesischen Restaurantprozess. Wenn wir außerdem einen schwarzen Ball zeichnen, wählen wir, anstatt eine neue Farbe zu erzeugen, stattdessen einen zufälligen Wert aus einer Basisverteilung und verwenden diesen Wert, um den neuen Ball zu beschriften, die resultierende Verteilung über die Etiketten ist dieselbe wie die Verteilung über die Werte in einem Dirichlet-Verfahren. ${\displaystyle H}$

Als Vorverteilung verwenden

Der Dirichlet-Prozess kann als Vorabverteilung verwendet werden, um die Wahrscheinlichkeitsverteilung zu schätzen, die die Daten erzeugt. In diesem Abschnitt betrachten wir das Modell

${\displaystyle {\begin{aligned}P&\sim {\textrm {DP}}(H,\alpha)\\X_{1},\cdots,X_{n}|P&{\overset {\textrm {iid} }{\sim }}S.\end{ausgerichtet}}}$

Die Verteilung des Dirichlet-Prozesses erfüllt Prior-Konjugation , Posterior-Konsistenz und das Bernstein-von-Mises-Theorem .

Vorherige Konjugation

In diesem Modell ist die posteriore Verteilung wiederum ein Dirichlet-Prozess. Dies bedeutet, dass der Dirichlet-Prozess ein konjugierter Prior für dieses Modell ist. Die Posterior-Verteilung ist gegeben durch

${\displaystyle {\begin{aligned}P|X_{1},\cdots ,X_{n}&\sim {\textrm {DP}}\left({\frac {\alpha }{\alpha +n}} H+{\frac{1}{\alpha+n}}\sum_{i=1}^{n}\delta_{X_{i}},\;\alpha+n\right)\\&={ \textrm{DP}}\left({\frac{\alpha}{\alpha+n}}H+{\frac{n}{\alpha+n}}\mathbb{P}_{n},\;\ alpha +n\rechts)\end{ausgerichtet}}}$

wo ist unten definiert. ${\displaystyle \mathbb{P}_{n}}$

Seitenzahnkonsistenz

Wenn wir die frequentistische Sichtweise der Wahrscheinlichkeit einnehmen , glauben wir, dass es eine wahre Wahrscheinlichkeitsverteilung gibt , die die Daten generiert hat. Dann stellt sich heraus, dass der Dirichlet-Prozess in der schwachen Topologie konsistent ist , was bedeutet, dass für jede schwache Umgebung von die a-posteriori-Wahrscheinlichkeit von konvergiert zu . ${\displaystyle P_{0}}$${\displaystyle U}$${\displaystyle P_{0}}$${\displaystyle U}$${\displaystyle 1}$

Bernstein-Von-Mises-Theorem

Um die glaubwürdigen Mengen als Konfidenzmengen zu interpretieren, wird ein Bernstein-von-Mises-Theorem benötigt. Beim Dirichlet-Prozess vergleichen wir die Posterior-Verteilung mit dem empirischen Prozess . Angenommen, es handelt sich um eine -Donsker-Klasse, dh ${\displaystyle \mathbb{P}_{n}={\frac{1}{n}}\sum_{i=1}^{n}\delta_{X_{i}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle P_{0}}$

${\displaystyle {\begin{aligned}{\sqrt {(}}n)\left(\mathbb {P} _{n}-P_{0}\right)\rightsquigarrow G_{P_{0}}\end{ ausgerichtet}}}$

für einige Brownian Bridge . Nehmen wir auch an, dass es eine Funktion gibt , so dass , dann fast sicher${\displaystyle G_{P_{0}}}$${\displaystyle F}$${\displaystyle F(x)\geq\sup_{f\in {\mathcal{F}}}f(x)}$${\displaystyle \int F^{2}\mathrm {d} H<\infty}$${\displaystyle P_{0}}$

${\displaystyle {\sqrt {n}}\left(P-\mathbb{P}_{n}\right)|X_{1},\cdots ,X_{n}\rightsquigarrow G_{P_{0}}. }$

Dies impliziert, dass glaubwürdige Mengen, die Sie konstruieren, asymptotische Konfidenzmengen sind und die Bayessche Inferenz basierend auf dem Dirichlet-Prozess asymptotisch auch gültige frequentistische Inferenz ist.

Verwendung in Dirichlet-Mischmodellen

Simulation von 1000 Beobachtungen aus einem Dirichlet-Mischungsmodell. Jede Beobachtung innerhalb eines Clusters wird unabhängig von der multivariaten Normalverteilung gezeichnet . Die Clustermittel werden aus einer Verteilung G gezogen, die ihrerseits aus einem Dirichlet-Prozess mit Konzentrationsparameter und Basisverteilung gezogen wird . Jede Zeile ist eine neue Simulation.${\displaystyle N(\mu_{k},1/4)}$${\displaystyle \mu_{k}}$${\displaystyle \alpha =0.5}$${\displaystyle H=N(2,16)}$

Um zu verstehen, was Dirichlet-Prozesse sind und welches Problem sie lösen, betrachten wir das Beispiel des Datenclustering . Es ist eine übliche Situation, dass angenommen wird, dass Datenpunkte in einer hierarchischen Weise verteilt sind, wobei jeder Datenpunkt zu einem (zufällig ausgewählten) Cluster gehört und die Mitglieder eines Clusters innerhalb dieses Clusters zufällig weiter verteilt werden.

Beispiel 1

Uns könnte zum Beispiel interessieren, wie die Leute bei einer bevorstehenden Wahl über eine Reihe von Fragen abstimmen. Ein vernünftiges Modell für diese Situation könnte darin bestehen, jeden Wähler als liberal, konservativ oder gemäßigt zu klassifizieren und dann das Ereignis, dass ein Wähler zu einer bestimmten Frage „Ja“ sagt, als Bernoulli-Zufallsvariable zu modellieren, wobei die Wahrscheinlichkeit davon abhängt, welcher politische Cluster Sie gehören zu. Wenn man sich anschaut, wie in früheren Jahren über ähnliche Gesetze abgestimmt wurde, könnte man ein Vorhersagemodell mit einem einfachen Clustering-Algorithmus wie k-means anpassen . Dieser Algorithmus erfordert jedoch, die Anzahl der Cluster, die die Daten generiert haben, im Voraus zu kennen. In vielen Situationen ist es nicht möglich, dies im Voraus zu bestimmen, und selbst wenn wir vernünftigerweise von mehreren Clustern ausgehen können, möchten wir diese Annahme dennoch überprüfen können. Im obigen Abstimmungsbeispiel ist beispielsweise die Aufteilung in liberal, konservativ und gemäßigt möglicherweise nicht fein genug abgestimmt; Attribute wie Religion, Klasse oder Rasse könnten auch für die Modellierung des Wählerverhaltens entscheidend sein, was zu mehr Clustern im Modell führt.

Beispiel 2

Als weiteres Beispiel könnten wir daran interessiert sein, die Geschwindigkeiten von Galaxien mit einem einfachen Modell zu modellieren, das davon ausgeht, dass die Geschwindigkeiten geclustert sind, zum Beispiel indem angenommen wird, dass jede Geschwindigkeit gemäß der Normalverteilung verteilt ist , wobei die te Beobachtung zum ten Galaxienhaufen gehört mit gemeinsamer erwarteter Geschwindigkeit. In diesem Fall ist es alles andere als offensichtlich, wie a priori zu bestimmen ist, wie viele Cluster (mit gemeinsamen Geschwindigkeiten) es geben sollte, und jedes Modell dafür wäre höchst suspekt und sollte anhand der Daten überprüft werden. Durch die Verwendung eines Dirichlet-Prozesses für die Verteilung von Clustermitteln umgehen wir die Notwendigkeit, im Voraus explizit anzugeben, wie viele Cluster es gibt, obwohl der Konzentrationsparameter dies immer noch implizit steuert. ${\displaystyle v_{i}\sim N(\mu_{k},\sigma^{2})}$${\displaystyle i}$${\displaystyle k}$

Wir betrachten dieses Beispiel genauer. Ein erstes naives Modell ist die Annahme, dass es Cluster von normalverteilten Geschwindigkeiten mit allgemein bekannter fester Varianz gibt . Wenn wir das Ereignis bezeichnen, dass sich die th Beobachtung im th Cluster befindet , können wir dieses Modell schreiben als: ${\displaystyle K}$ ${\displaystyle \sigma ^{2}}$${\displaystyle i}$${\displaystyle k}$${\displaystyle z_{i}=k}$

${\displaystyle {\begin{ausgerichtet}(v_{i}\mid z_{i}=k,\mu_{k})&\sim N(\mu_{k},\sigma^{2})\ \\operatorname {P} (z_{i}=k)&=\pi _{k}\\({\boldsymbol {\pi}}\mid \alpha )&\sim \operatorname {Dir} \left({ \frac {\alpha }{K}}\cdot \mathbf {1}_{K}\right)\\\mu_{k}&\sim H(\lambda)\end{ausgerichtet}}}$

Das heißt, wir nehmen an, dass die Daten zu verschiedenen Clustern mit Mittelwerten gehören, und das ist die (unbekannte) vorherige Wahrscheinlichkeit eines Datenpunkts, der zum th Cluster gehört. Wir gehen davon aus, dass wir keine anfänglichen Informationen haben, die die Cluster unterscheiden, die durch den symmetrischen Prior erfasst werden . Hier bezeichnet die Dirichlet Verteilung und bezeichnet einen Vektor der Länge , wobei jedes Element 1 ist , die wir weiter assign unabhängige und identische Verteilungen vor zu jedem der Cluster Mittel, wobei jede parametrische Verteilung mit Parametern wie bezeichnet werden kann . Die Hyperparameter und werden als bekannte feste Konstanten angesehen, die ausgewählt wurden, um unsere früheren Überzeugungen über das System widerzuspiegeln. Um die Verbindung zu den Dirichlet-Prozessprioritäten zu verstehen, schreiben wir dieses Modell in eine äquivalente, aber suggestivere Form um: ${\displaystyle K}$${\displaystyle \mu_{k}}$${\displaystyle \pi_{k}}$${\displaystyle k}$${\displaystyle \operatorname {Dir} \left(\alpha /K\cdot \mathbf{1} _{K}\right)}$${\displaystyle \operatorname {Dir}}$${\displaystyle \mathbf {1} _{K}}$${\displaystyle K}$${\displaystyle H(\lambda)}$${\displaystyle H}$${\displaystyle \lambda}$${\displaystyle\alpha}$${\displaystyle \lambda}$

${\displaystyle {\begin{ausgerichtet}(v_{i}\mid {\tilde {\mu}}_{i})&\sim N({\tilde {\mu}}_{i},\sigma ^ {2})\\{\tilde{\mu}}_{i}&\sim G=\sum_{k=1}^{K}\pi_{k}\delta_{\mu_{k }}({\tilde {\mu}}_{i})\\({\boldsymbol {\pi}}\mid \alpha )&\sim \operatorname {Dir} \left({\frac {\alpha} {K}}\cdot\mathbf{1}_{K}\right)\\\mu_{k}&\sim H(\lambda)\end{ausgerichtet}}}$

Anstatt sich vorzustellen, dass jedem Datenpunkt zuerst ein Cluster zugewiesen und dann aus der diesem Cluster zugeordneten Verteilung gezogen wird, denken wir jetzt, dass jede Beobachtung mit Parametern assoziiert ist, die aus einer diskreten Verteilung mit Unterstützung der Mittelwerte gezogen werden. Das heißt, wir behandeln die jetzt so, als ob sie aus der Zufallsverteilung stammen, und unsere vorherigen Informationen werden durch die Verteilung über die Verteilungen in das Modell aufgenommen . ${\displaystyle {\tilde {\mu}}_{i}}$${\displaystyle G}$${\displaystyle K}$${\displaystyle {\tilde {\mu}}_{i}}$${\displaystyle G}$${\displaystyle G}$

Medien abspielen

Animation des Clustering-Prozesses für eindimensionale Daten mit Gauß-Verteilungen aus einem Dirichlet-Prozess. Die Histogramme der Cluster werden in verschiedenen Farben dargestellt. Während des Parameterschätzungsprozesses werden neue Cluster erstellt und wachsen auf den Daten. Die Legende zeigt die Clusterfarben und die Anzahl der jedem Cluster zugewiesenen Datenpunkte.

Wir möchten dieses Modell nun so erweitern, dass es funktioniert, ohne vorab eine feste Anzahl von Clustern festzulegen . Mathematisch bedeutet dies, dass wir eine zufällige Prior-Verteilung wählen möchten, bei der die Werte der Cluster-Mittel wieder unabhängig gemäß verteilt sind und die Verteilung über die unendliche Menge von Clustern symmetrisch ist. Genau das leistet das Modell: ${\displaystyle K}$${\displaystyle G({\tilde {\mu}}_{i})=\sum_{k=1}^{\infty}\pi_{k}\delta_{\mu_{k}}( {\tilde{\mu}}_{i})}$${\displaystyle \mu_{k}}$${\displaystyle H\left(\lambda\right)}$${\displaystyle \pi_{k}}$

${\displaystyle {\begin{ausgerichtet}(v_{i}\mid {\tilde {\mu}}_{i})&\sim N({\tilde {\mu}}_{i},\sigma ^ {2})\\{\tilde {\mu}}_{i}&\sim G\\G&\sim \operatorname {DP} (H(\lambda),\alpha)\end{ausgerichtet}}}$

Damit können wir die rechnerischen Vorzüge des Dirichlet-Prozesses besser verstehen. Angenommen, wir wollten Beobachtungen aus dem naiven Modell mit exakten Clustern zeichnen . Ein einfacher Algorithmus dafür wäre, Werte von von zu ziehen , eine Verteilung von und dann für jede Beobachtung unabhängig den Cluster mit der Wahrscheinlichkeit und dem Wert der Beobachtung gemäß abzutasten . Es ist leicht zu erkennen, dass dieser Algorithmus nicht funktioniert, wenn wir unendliche Cluster zulassen, da dies die Abtastung eines unendlich dimensionalen Parameters erfordern würde . Es ist jedoch weiterhin möglich, Beobachtungen zu proben . Man kann zB die nachfolgend beschriebene chinesische Restaurantdarstellung verwenden und die Wahrscheinlichkeit für verwendete Cluster und einen neu zu erstellenden Cluster berechnen. Dadurch wird vermieden, dass explizit angegeben werden muss . Andere Lösungen basieren auf einer Kürzung von Clustern: Es wird eine (hohe) obere Grenze der wahren Anzahl von Clustern eingeführt und Clusterzahlen über der unteren Grenze werden als ein Cluster behandelt. ${\displaystyle n}$${\displaystyle K}$${\displaystyle K}$${\displaystyle \mu_{k}}$${\displaystyle H(\lambda)}$${\displaystyle \pi}$${\displaystyle \operatorname {Dir} \left(\alpha /K\cdot \mathbf{1} _{K}\right)}$${\displaystyle k}$${\displaystyle \pi_{k}}$${\displaystyle N\left(\mu_{k},\sigma^{2}\right)}$${\displaystyle {\boldsymbol {\pi}}}$${\displaystyle v_{i}}$${\displaystyle {\boldsymbol {\pi}}}$

Das Anpassen des oben beschriebenen Modells basierend auf beobachteten Daten bedeutet das Finden der Posterior-Verteilung über die Clusterwahrscheinlichkeiten und ihre zugehörigen Mittelwerte. Im unendlichdimensionalen Fall ist es offensichtlich unmöglich, das Posterior explizit aufzuschreiben. Es ist jedoch möglich, mit einem modifizierten Gibbs-Sampler Proben aus diesem Posterior zu ziehen . Dies ist die kritische Tatsache, die den Dirichlet-Prozess a priori für die Inferenz nützlich macht . ${\displaystyle D}$ ${\displaystyle p\left({\boldsymbol {\pi}},{\boldsymbol {\mu}}\mid D\right)}$

Anwendungen des Dirichlet-Verfahrens

Dirichlet-Prozesse werden häufig in der Bayesschen nichtparametrischen Statistik verwendet . "Nichtparametrisch" bedeutet hier kein parameterloses Modell, sondern ein Modell, bei dem die Darstellungen wachsen, wenn mehr Daten beobachtet werden. Bayessche nichtparametrische Modelle haben im Bereich des maschinellen Lernens aufgrund der oben genannten Flexibilität, insbesondere beim unüberwachten Lernen, erhebliche Popularität erlangt . In einem Bayesschen nichtparametrischen Modell sind die Prior- und Posterior-Verteilungen keine parametrischen Verteilungen, sondern stochastische Prozesse. Die Tatsache, dass die Dirichlet-Verteilung eine Wahrscheinlichkeitsverteilung auf dem Simplex von Mengen nicht negativer Zahlen ist, die sich zu eins summieren, macht sie zu einem guten Kandidaten für die Modellierung von Verteilungen über Verteilungen oder Verteilungen über Funktionen. Darüber hinaus macht die nichtparametrische Natur dieses Modells es zu einem idealen Kandidaten für Clustering-Probleme, bei denen die unterschiedliche Anzahl von Clustern im Voraus unbekannt ist. Darüber hinaus wurde das Dirichlet-Verfahren auch zur Entwicklung einer Mischung von Expertenmodellen im Rahmen von überwachten Lernalgorithmen (Regressions- oder Klassifikationseinstellungen) verwendet. Zum Beispiel Mischungen von Gauss-Prozessexperten, bei denen aus den Daten auf die Anzahl der benötigten Experten geschlossen werden muss.

Da Ziehungen aus einem Dirichlet-Prozess diskret sind, ist eine wichtige Verwendung als A- priori-Wahrscheinlichkeit in Modellen für unendliche Mischungen . In diesem Fall ist der parametrische Satz von Komponentenverteilungen. Der generative Prozess besteht daher darin, dass eine Stichprobe aus einem Dirichlet-Prozess gezogen wird und für jeden Datenpunkt wiederum ein Wert aus dieser Stichprobenverteilung gezogen und als Komponentenverteilung für diesen Datenpunkt verwendet wird. Die Tatsache, dass die Anzahl der verschiedenen Komponenten, die erzeugt werden können, unbegrenzt ist, macht diese Art von Modell für den Fall geeignet, wenn die Anzahl der Mischungskomponenten im Voraus nicht genau definiert ist. Zum Beispiel die unendliche Mischung des Gauss'schen Modells sowie zugehörige Mischungsregressionsmodelle, z ${\displaystyle S}$

Die unendliche Natur dieser Modelle verleiht sie auch Anwendungen zur Verarbeitung natürlicher Sprache , bei denen es oft wünschenswert ist, das Vokabular als eine unendliche, diskrete Menge zu behandeln.

Der Dirichlet - Prozess kann auch für nichtparametrische Hypothesentests verwendet werden, dh Bayesian nichtparametrischer Versionen der klassischen nichtparametrischer Hypothesentests, zum Beispiel zu entwickeln Vorzeichentest , Wilcoxon Rangsummentest , Wilcoxon-Test , usw. Zum Beispiel Bayesian nichtparametrischer Versionen der Wilcoxon-Rangsummentest und der Wilcoxon-Vorzeichen-Rangtest wurden unter Verwendung des ungenauen Dirichlet-Prozesses entwickelt , einem Dirichlet-Prozess der früheren Unkenntnis.

Verwandte Distributionen

• Der Pitman-Yor-Prozess ist eine Verallgemeinerung des Dirichlet-Prozesses, um Potenzgesetz-Schwanzen zu berücksichtigen
• Der hierarchische Dirichlet-Prozess erweitert den gewöhnlichen Dirichlet-Prozess zur Modellierung gruppierter Daten.

Verweise

Externe Links

• Einführung in die Dirichlet-Verteilung und verwandte Prozesse von Frigyik, Kapila und Gupta
• Yee Whye Tehs Überblick über die Dirichlet-Prozesse
• Webseite für den NIPS 2003-Workshop zu nicht-parametrischen Bayes-Methoden
• Michael Jordans NIPS 2005-Tutorial: Nichtparametrische Bayessche Methoden: Dirichlet-Prozesse, chinesische Restaurantprozesse und all das
• Peter Greens Zusammenfassung der Konstruktion von Dirichlet-Prozessen
• Peter Greens Papier über probabilistische Modelle von Dirichlet-Prozessen mit Implikationen für die statistische Modellierung und Analyse
• Zoubin Ghahramanis UAI 2005-Tutorial zu nichtparametrischen Bayes-Methoden
• GIMM-Software zur Durchführung von Clusteranalysen mit Infinite-Mixture-Modellen
• Ein Spielzeugbeispiel für Clustering mit dem Dirichlet-Prozess. von Zhiyuan Weng