Verteilungen auf Teilmengen von ?

Ich frage mich, ob es Standardverteilungen für Teilmengen von Ganzzahlen . Entsprechend könnten wir dies als Verteilung auf einen Längenvektor von binären Ergebnissen ausdrücken , z. B. wenn dann entspricht dem Vektor .$\{1, 2, ..., J\}$$J$$J = 5$$\{1, 3, 5\}$$(1, 0, 1, 0, 1)$

Im Idealfall suche ich eine Verteilung , die aus einer Familie stammt, die durch einen endlichen dimensionalen Parameter indiziert ist und deren Masse so verteilt, dass zwei binäre Vektoren und ähnlich sind Wahrscheinlichkeit, wenn sie "nahe" beieinander liegen, dh und haben ähnliche Wahrscheinlichkeiten. Wirklich, was ich hoffentlich tun möchte, ist, einen Prior zu geben, so dass, wenn ich weiß, dass ziemlich groß ist, wahrscheinlich relativ zu Vektoren weit weg von groß ist .$\nu_\theta (\cdot)$$\theta$$r_1$$r_2$$r_1 = (0, 0, 1, 0, 1)$$r_2 = (0, 0, 1, 1, 1)$$\theta$$\nu_\theta (r_1)$$\nu_\theta (r_2)$$r_1$

Eine Strategie, die mir in den Sinn kommt, wäre, eine Metrik oder ein anderes Maß für die Streuung auf auf und dann oder ähnliches. Ein explizites Beispiel wäre in Analogie zur Normalverteilung. Das ist in Ordnung, aber ich hoffe, dass es etwas Standardisches gibt, das der Bayes'schen Analyse zugänglich ist. damit kann ich die normalisierungskonstante nicht aufschreiben.$d_\theta$$\{0, 1\}^J$$\nu_\theta (r) \propto \exp (-d_\theta (r, \mu))$$\exp\left\{-\|r - \mu\|^2 / (2 \sigma^2)\right\}$

Möglicherweise bevorzugen Sie Standortfamilien basierend auf der Hamming-Entfernung aufgrund ihres Reichtums, ihrer Flexibilität und ihrer Rechenleistung.

Notation und Definitionen

Denken Sie daran, dass in einem freien endlichdimensionalen Modul mit der Basis der Hamming-Abstand zwischen zwei Vektoren liegt und ist die Anzahl der Stellen wo .$V$$\left(\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_J\right)$ $\delta_H$$\mathbf{v}=v_1 \mathbf{e}_1 + \cdots + v_J\mathbf{e}_J$$\mathbf{w}=w_1 \mathbf{e}_1 + \cdots + w_J\mathbf{e}_J$$i$$v_i \ne w_i$

Bei gegebenem Ursprung der Hamming-Abstand in Kugeln , , wobei . Wenn der Erdungsring hat Elemente hat - Elemente und hat - Elemente. (Dies folgt unmittelbar aus der Beobachtung, dass sich Elemente von an genau Stellen von unterscheiden - von denen es$\mathbf{v}_0\in V$$V$$S_i(\mathbf{v}_0)$$i=0, 1, \ldots, J$$S_i(\mathbf{v}_0) = \{\mathbf{w}\in V\ |\ \delta_H(\mathbf{w}, \mathbf{v}_0) = i\}$$n$$V$$n^J$$S_i(\mathbf{v})$$\binom{J}{i}\left(n-1\right)^i$$S_i(\mathbf{v})$$\mathbf{v}$$i$$\binom{J}{i}$Möglichkeiten - und dass es unabhängig Werte für jeden Ort gibt.)$n-1$

Die affine Übersetzung in wirkt sich natürlich auf ihre Verteilungen aus, um Standortfamilien zu erhalten. Insbesondere wenn eine beliebige Verteilung auf (was wenig mehr als , für alle und ) und ist ein beliebiges Element von , dann ist auch eine Verteilung wo$V$$f$$V$$f:V\to [0,1]$$f(\mathbf{v})\ge 0$$\mathbf{v} \in V$$\sum_{\mathbf{v}\in V}f(\mathbf{v})=1$$\mathbf{w}$$V$$f^{(\mathbf{w})}$

für alle . Ein Ort Familien von Verteilungen invariant ist im Rahmen dieser Aktion: impliziert für alle .$\mathbf{v}\in V$ $\Omega$$f\in \Omega$$f^{(\mathbf{v})}\in \Omega$$\mathbf{v}\in V$

Konstruktion

Dies ermöglicht es uns, potenziell interessante und nützliche Verteilungsfamilien zu definieren, indem wir ihre Formen an einem festen Vektor als und Übersetzen dieser "erzeugenden Verteilungen" unter der Wirkung von , um die vollständige Familie . Um die gewünschte Eigenschaft zu erreichen, dass an nahe gelegenen Punkten vergleichbare Werte haben sollte, benötigen Sie einfach diese Eigenschaft aller erzeugenden Verteilungen.$\mathbf{v}$$\mathbf{0} = (0,0,\ldots,0)$$V$$\Omega$$f$

Um zu sehen, wie dies funktioniert, konstruieren wir die Standortfamilie aller Verteilungen, die mit zunehmender Entfernung abnehmen. Da nur Hamming-Entfernungen möglich sind, berücksichtigen Sie eine abnehmende Folge nicht negativer reeller Zahlen = . einstellen$J+1$$\mathbf{a}$$0 \ne a_0 \ge a_1 \ge \cdots \ge a_J \ge 0$

und definieren Sie die Funktion durch$f_\mathbf{a}:V\to [0,1]$

Dann wird , wie ist einfach zu überprüfen, ist eine Verteilung auf . Außerdem ist genau dann, wenn ein positives Vielfaches von (als Vektoren in ). Wenn wir möchten, können wir also auf standardisieren .$f_\mathbf{a}$$V$$f_\mathbf{a} = f_{\mathbf{a}'}$$\mathbf{a}'$$\mathbf{a}$$\mathbb{R}^{J+1}$$\mathbf{a}$$a_0=1$

Dementsprechend liefert diese Konstruktion eine explizite Parametrisierung aller derartigen ortsinvarianten Verteilungen, die mit der Hamming-Entfernung abnehmen: Jede solche Verteilung hat die Form für eine Sequenz und einige Vektor .$f_\mathbf{a}^{(\mathbf{v})}$$\mathbf{a} = 1 \ge a_1 \ge a_2 \ge \cdots \ge a_J \ge 0$$\mathbf{v}\in V$

Diese Parametrisierung kann eine bequeme Angabe von Prioritäten ermöglichen: Berücksichtigen Sie diese in einem Prior an der Position und einem Prior an der Form . (Natürlich könnte man eine größere Anzahl von Prioritäten in Betracht ziehen, bei denen Ort und Form nicht unabhängig sind, aber dies wäre ein komplizierteres Unterfangen.)$\mathbf{v}$$\mathbf{a}$

Zufallswerte generieren

Eine Möglichkeit, aus zu probieren, besteht darin, es in eine Verteilung über das sphärische Strahl und eine andere Verteilung zu zerlegen, die von jeder Kugel abhängig ist:$f_\mathbf{a}^{(\mathbf{v})}$

1. Zeichnen Sie einen Index aus der diskreten Verteilung auf die durch die Wahrscheinlichkeiten , wobei wie zuvor definiert ist .$i$$\{0,1,\ldots,J\}$$\binom{J}{i}(n-1)^i a_i / A$$A$

2. Der Index entspricht der Menge von Vektoren, die sich an genau Stellen von unterscheiden . Wählen Sie daher die Stellen aus den möglichen Teilmengen und geben Sie jede gleiche Wahrscheinlichkeit an. (Dies ist nur eine Auswahl von Indizes aus ohne Ersatz.) Lassen Sie diese Teilmenge von Stellen schreiben .$i$$\mathbf{v}$$i$$i$$\binom{J}{i}$$i$$J$ $i$$I$

3. Zeichnen Sie ein Element indem Sie unabhängig einen Wert einheitlich aus der Menge der Skalare für alle nicht gleich und ansonsten . Erstellen Sie entsprechend einen Vektor indem Sie gleichmäßig zufällig aus den Skalaren ungleich Null auswählen, wenn und andernfalls . Setze .$\mathbf{w}$$w_j$$v_j$$j\in I$$w_j=v_j$$\mathbf{u}$$u_j$$j\in I$$u_j=0$$\mathbf{w} = \mathbf{v} + \mathbf{u}$

Schritt 3 ist im Binärfall nicht erforderlich.

Beispiel

Hier ist eine RImplementierung zur Veranschaulichung.

rHamming <- function(N=1, a=c(1,1,1), n=2, origin) {
  # Draw N random values from the distribution f_a^v where the ground ring
  # is {0,1,...,n-1} mod n and the vector space has dimension j = length(a)-1.
  j <- length(a) - 1
  if(missing(origin)) origin <- rep(0, j)

  # Draw radii `i` from the marginal distribution of the spherical radii.
  f <- sapply(0:j, function(i) (n-1)^i * choose(j,i) * a[i+1])
  i <- sample(0:j, N, replace=TRUE, prob=f)

  # Helper function: select nonzero elements of 1:(n-1) in exactly i places.
  h <- function(i) {
    x <- c(sample(1:(n-1), i, replace=TRUE), rep(0, j-i))
    sample(x, j, replace=FALSE)
  }

  # Draw elements from the conditional distribution over the spheres
  # and translate them by the origin.
  (sapply(i, h) + origin) %% n
}

Als Beispiel für seine Verwendung:

test <- rHamming(10^4, 2^(11:1), origin=rep(1,10))
hist(apply(test, 2, function(x) sum(x != 0)))

Es dauerte Sekunden, um iid-Elemente aus der Verteilung zu zeichnen, wobei , (der binäre Fall), und nimmt exponentiell ab.$0.2$$10^4$$f_{\mathbf{a}}^{(\mathbf{v})}$$J=10$$n=2$$\mathbf{v}=(1,1,\ldots,1)$$\mathbf{a}=(2^{11},2^{10},\ldots,2^1)$

(Dieser Algorithmus erfordert nicht, dass abnimmt. Daher werden zufällige Variablen aus jeder Standortfamilie generiert , nicht nur aus den unimodalen.)$\mathbf{a}$

Eine Stichprobe aus einem k-determinanten Punktprozess modelliert eine Verteilung über Teilmengen, die die Diversität fördert, sodass ähnliche Elemente in der Stichprobe weniger wahrscheinlich zusammen auftreten. Siehe K-Determinanten-Punkt-Prozess-Sampling von Alex Kulesza, Ben Taskar.