Verteilungen auf Teilmengen von ?

9

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}JJ=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 .νθ()θr1r2r1=(0,0,1,0,1)r2=(0,0,1,1,1)θνθ(r1)νθ(r2)r1

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θ{0,1}Jνθ(r)exp(dθ(r,μ))exp{rμ2/(2σ2)}

Kerl
quelle
Das Abtasten einer Teilmenge ist ein grundlegendes Problem in der Umfragemethodik.
Stéphane Laurent
@Stephane sicher, aber ich denke, mein Problem unterscheidet sich darin, dass ich eine zusätzliche gewünschte Struktur habe, die meine Verteilung widerspiegeln soll. Vielleicht war es eine schlechte Idee, die Frage in Teilmengen zu formulieren, da ich eine vage Vorstellung davon habe, wie Distanz für mich arbeitet.
Kerl
Wollten Sie schreiben "... dann ist wahrscheinlich klein ..."? In Bezug auf die Normalisierungskonstante sollten Sie die Hamming-Distanz für die Metrik verwenden: Für Verteilungsfamilien auf Ortsskala können Sie diese Konstante als Summe von nur Termen berechnen . Darüber hinaus können alle diese Familien, die Ihre Kriterien erfüllen, durch nur diskrete Parameter (für den Standort) und kontinuierliche Parameter beschrieben werden. vθ(r2)J+1JJ
whuber
@whuber nein, ich meinte groß. Ich möchte, dass seine Masse um Punkte verteilt, die nahe beieinander liegen. Es wäre wahrscheinlich sinnvoller gewesen, die Frage so zu formulieren, dass eine Verteilung auf die Eckpunkte eines Hyperwürfels erfolgt. Ich hatte die Hamming-Distanz in Betracht gezogen (die in meinem Fall mit identisch ist). Ich würde es wahrscheinlich als optimieren wollen , und ich denke, ich müsste wahrscheinlich etwas MCMC machen, um aus einer solchen Distribution zu probieren. νθ()L1|riμiσi|
Kerl
Oh, ich verstehe jetzt. Aber das haben Sie ursprünglich nicht gesagt. Wenn beispielsweise in Ihrer Charakterisierung groß ist und die Menge der Vektoren "weit weg" von ist und ein beliebiger Vektor ist, der nicht in , muss auch "wahrscheinlich" sein groß sein. Aber "nicht weit weg" und "nah" bedeuten nicht genau dasselbe. Es wäre einfacher - und intern konsistenter -, die Bedingung wie in Ihrem Kommentar neu zu formulieren. Aber nein, Sie benötigen kein MCMC, um anhand von Hamming-Entfernungen anhand von Verteilungen im Standortmaßstab zu ermitteln: Es gibt viel effizientere Möglichkeiten. ν(r1)Rr1r2Rν(r2)
whuber

Antworten:

6

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(e1,e2,,eJ) δHv=v1e1++vJeJw=w1e1++wJeJiviwi

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 esv0VVSi(v0)i=0,1,,JSi(v0)={wV | δH(w,v0)=i}nVnJSi(v)(Ji)(n1)iSi(v)vi(Ji)Möglichkeiten - und dass es unabhängig Werte für jeden Ort gibt.)n1

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 woVfVf:V[0,1]f(v)0vVvVf(v)=1wVf(w)

f(w)(v)=f(vw)

für alle . Ein Ort Familien von Verteilungen invariant ist im Rahmen dieser Aktion: impliziert für alle .vV ΩfΩf(v)ΩvV

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.v0=(0,0,,0)VΩ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 = . einstellenJ+1a0a0a1aJ0

A=i=0J(n1)i(Ji)ai

und definieren Sie die Funktion durchfa:V[0,1]

fa(v)=aδH(0,v)A.

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 .faVfa=faaaRJ+1aa0=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 .fa(v)a=1a1a2aJ0vV

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.)va

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:fa(v)

  1. Zeichnen Sie einen Index aus der diskreten Verteilung auf die durch die Wahrscheinlichkeiten , wobei wie zuvor definiert ist .i{0,1,,J}(Ji)(n1)iai/AA

  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 .ivii(Ji)iJ iI

  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 .wwjvjjIwj=vjuujjIuj=0w=v+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.2104fa(v)J=10n=2v=(1,1,,1)a=(211,210,,21)

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

whuber
quelle
Danke dafür! Die Hamming-Distanz beträgt in diesem Fall nur in auf die Würfelscheitelpunkte beschränkt. In diesem Zusammenhang wirkt die Hamming-Distanz isotrop. Wenn ich davon wegkomme, werden diese Dinge wahrscheinlich komplizierter, weil ich mehr als verschiedene Werte für mein Entfernungsmaß habe. Irgendwelche allgemeinen Kommentare dazu? L1RJJ
Kerl
Ja: Die Auswahl der Abstandsfunktionen hängt davon ab, was die Werte in darstellen. Da die Frage abstrakt formuliert wurde, haben wir wirklich nichts zu tun, um Meinungen darüber zu bilden, was eine gute Wahl wäre. Der Hamming-Abstand wäre für Nennwerte und möglicherweise auch in anderen Fällen geeignet , aber andere Abstände könnten besser funktionieren, wenn für die Menge ein inhärenter Abstandssinn besteht . Im binären Fall ist es schwierig, Hamming-Entfernungen zu verallgemeinern: Sie sind bereits ziemlich allgemein. {1,2,,n}{1,2,,n}n=2
whuber
1

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.

Leichenwagen
quelle