Rozkłady na podzbiory ?

Zastanawiam się, czy istnieją jakieś standardowe rozkłady na podzbiorach liczb całkowitych . Równolegle możemy to wyrazić jako rozkład na wektor długości wyników binarnych, np. Jeśli to odpowiada wektorowi .$\{1, 2, ..., J\}$$J$$J = 5$$\{1, 3, 5\}$$(1, 0, 1, 0, 1)$

Idealnie szukam jakiejś dystrybucji , pochodzącej z rodziny indeksowanej skończonym parametrem wymiarowym , która rozdzieliłaby swoją masę w taki sposób, że dwa wektory binarne i będą miały podobne prawdopodobieństwo, jeśli są „blisko” razem, tzn. i mają podobne prawdopodobieństwa. Mam nadzieję, że to, co zamierzam zrobić, polega na tym, żeby tak, że jeśli wiem, że jest dość duży, to jest prawdopodobnie duży w stosunku do wektorów daleko od .$\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$

Jedną ze strategii, która przychodzi na myśl, byłoby umieszczenie metryki lub innej miary rozproszenia na na a następnie wzięcie lub coś podobnego. Wyraźnym przykładem byłoby analogicznie do rozkładu normalnego. W porządku, ale mam nadzieję, że istnieje coś standardowego i podlegającego analizie bayesowskiej; dzięki temu nie mogę zapisać stałej normalizującej.$d_\theta$$\{0, 1\}^J$$\nu_\theta (r) \propto \exp (-d_\theta (r, \mu))$$\exp\left\{-\|r - \mu\|^2 / (2 \sigma^2)\right\}$

Możesz preferować rodziny lokalizacji oparte na odległości Hamminga , ze względu na ich bogactwo, elastyczność i podatność na obliczenia.

Notacja i definicje

Przypomnijmy, że w wolnej modułu skończonej trójwymiarowy Bazując The odległość Hamminga pomiędzy dwoma wektorami i jest liczba miejsc gdzie .$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$

Biorąc pod uwagę dowolne pochodzenie , odległość Hamminga dzieli na sfery , , gdzie . Kiedy pierścień uziemiający ma elementów, ma elementów, a ma . (Wynika to natychmiast z obserwacji, że elementy różnią się od w dokładnie miejscach - w których jest$\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}$możliwości - i że istnieje niezależnie wybór wartości dla każdego miejsca).$n-1$

Tłumaczenie afiniczne w działa naturalnie na jego dystrybucje, dając rodziny lokalizacji. W szczególności, gdy jest dowolnym rozkładem na (co oznacza niewiele więcej niż , dla wszystkich , i ) i jest dowolnym elementem , to jest również rozkładem gdzie$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})}$

wszystkie . Rodzinę Położenie rozkładów niezmienna przy tym działania: oznacza dla wszystkich .$\mathbf{v}\in V$ $\Omega$$f\in \Omega$$f^{(\mathbf{v})}\in \Omega$$\mathbf{v}\in V$

Budowa

To pozwala nam zdefiniować potencjalnie interesujące i przydatne rodziny rozkładów, określając ich kształty w jednym stałym wektorze , co dla wygody wezmę za i tłumaczenie tych „rozkładów generowania” pod działaniem celu uzyskania pełnej rodziny . Aby osiągnąć pożądaną właściwość, która powinna mieć porównywalne wartości w pobliskich punktach, po prostu wymagaj tej właściwości wszystkich rozkładów generowania.$\mathbf{v}$$\mathbf{0} = (0,0,\ldots,0)$$V$$\Omega$$f$

Aby zobaczyć, jak to działa, stwórzmy rodzinę lokalizacji wszystkich rozkładów, które zmniejszają się wraz ze wzrostem odległości. Ponieważ możliwe są tylko odległości Hamminga , rozważ każdą malejącą sekwencję nieujemnych liczb rzeczywistych = . Zestaw$J+1$$\mathbf{a}$$0 \ne a_0 \ge a_1 \ge \cdots \ge a_J \ge 0$

i zdefiniuj funkcję przez$f_\mathbf{a}:V\to [0,1]$

Potem, jak to łatwe do sprawdzenia, jest dystrybucja na . Ponadto wtedy i tylko wtedy, gdy jest dodatnią wielokrotnością (jako wektory w ). Zatem, jeśli chcemy, możemy standaryzować do .$f_\mathbf{a}$$V$$f_\mathbf{a} = f_{\mathbf{a}'}$$\mathbf{a}'$$\mathbf{a}$$\mathbb{R}^{J+1}$$\mathbf{a}$$a_0=1$

Odpowiednio, ta konstrukcja daje wyraźną parametryzację wszystkich takich niezmiennych lokalizacji, które maleją wraz z odległością Hamminga: każdy taki rozkład ma postać dla pewnej sekwencji niektóre wektor .$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$

Ta parametryzacja może pozwolić na wygodną specyfikację priorów: uwzględnij je w przedziale w lokalizacji i przed w kształcie . (Oczywiście można rozważyć większy zestaw priorytetów, w których lokalizacja i kształt nie są niezależne, ale byłoby to bardziej skomplikowane przedsięwzięcie).$\mathbf{v}$$\mathbf{a}$

Generowanie losowych wartości

Jednym ze sposobów na pobranie próbki z jest etapowanie poprzez podzielenie jej na rozkład w promieniu kulistym i inny rozkład zależny od każdej kuli:$f_\mathbf{a}^{(\mathbf{v})}$

1. Narysuj indeks z rozkładu dyskretnego na podany przez prawdopodobieństwa , gdzie jest zdefiniowane jak poprzednio .$i$$\{0,1,\ldots,J\}$$\binom{J}{i}(n-1)^i a_i / A$$A$

2. Indeks odpowiada zestawowi wektorów różniących się od w dokładnie miejscach. Dlatego wybierz te miejsca spośród możliwych podzbiorów , dając każdemu jednakowemu prawdopodobieństwu. (To jest tylko przykładowy indeksy z bez zastąpienia). Niech to podzbiór miejscach być napisany .$i$$\mathbf{v}$$i$$i$$\binom{J}{i}$$i$$J$ $i$$I$

3. Narysuj element , niezależnie wybierając wartość równomiernie ze zbioru skalarów od dla wszystkich a w przeciwnym razie ustaw . utwórz wektor , wybierając losowo z niezerowych skalarów, gdy a w przeciwnym razie ustawiając . Ustaw .$\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}$

Krok 3 jest niepotrzebny w przypadku binarnym.

Przykład

Oto Rimplementacja do zilustrowania.

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
}

Jako przykład jego zastosowania:

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

Miało to sekundy zwrócić lid elementy Distribution , gdzie , (w przypadku binarnej), i maleje wykładniczo.$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)$

(Ten algorytm nie wymaga zmniejszania ; w ten sposób będzie generować losowe zmienne z dowolnej rodziny lokalizacji, nie tylko z tych jednomodalnych.)$\mathbf{a}$

Próbka z procesu punktowego determinującego k modeluje rozkład na podzbiory, który zachęca do różnorodności, tak że podobne elementy rzadziej występują razem w próbce. Zapoznaj się z próbkowaniem w procesie punktowym wyznaczania K przez Alexa Kuleszy, Ben Taskar.