Rozkłady na podzbiory ?

9

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

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

chłopak
źródło
Próbkowanie podzbioru jest podstawowym problemem w metodologii ankiet.
Stéphane Laurent,
@Stephane na pewno, ale myślę, że mój problem różni się tym, że mam dodatkową pożądaną strukturę, którą chciałbym, aby odzwierciedlała moja dystrybucja. Być może sformułowanie pytania w odniesieniu do podzbiorów było złym pomysłem, ponieważ mam dla mnie niejasne pojęcie odległości.
facet
Czy Ci o napisanie „... to jest prawdopodobnie małe ...”? Jeśli chodzi o stałą normalizującą, rozważ użycie odległości Hamminga dla metryki: w przypadku rodzin rozkładów lokalizacji w skali lokalizacji możesz obliczyć tę stałą jako sumę tylko składników . Co więcej, wszystkie takie rodziny, które spełniają twoje kryteria, można opisać za pomocą dyskretnych parametrów (dla lokalizacji) i parametrów ciągłych. vθ(r2)J+1JJ
whuber
@ whuber nie, miałem na myśli duże. Chcę, aby rozłożył swoją masę wokół punktów, które są blisko siebie. Prawdopodobnie byłoby więcej aproposów, aby sformułować to pytanie jako umieszczenie rozkładu na wierzchołkach hipersześcianu. odległość Hamminga (która w moim przypadku jest taka sama jak ); Prawdopodobnie chciałbym go ulepszyć jakoi przypuszczam, że prawdopodobnie musiałbym zrobić trochę MCMC, aby pobrać próbki z takiej dystrybucji. νθ()L1|riμiσi|
facet
Och, teraz rozumiem. Ale nie to pierwotnie powiedziałeś. Na przykład, w twojej charakterystyce, jeśli jest duży, a jest zbiorem wektorów „daleko” od , a jest dowolnym wektorem spoza , to musi również „prawdopodobnie” być dużym. Ale „nie daleko” i „blisko” nie oznaczają dokładnie tych samych rzeczy. Byłoby łatwiej - i bardziej wewnętrznie spójne - przeformułować ten warunek, tak jak w komentarzu. Ale nie, nie potrzebujesz MCMC do próbkowania z rozkładów w skali lokalizacji opartych na odległościach Hamminga: istnieją znacznie bardziej wydajne sposoby. ν(r1)Rr1r2Rν(r2)
whuber

Odpowiedzi:

6

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

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 jestv0VVSi(v0)i=0,1,,JSi(v0)={wV | δH(w,v0)=i}nVnJSi(v)(Ji)(n1)iSi(v)vi(Ji)możliwości - i że istnieje niezależnie wybór wartości dla każdego miejsca).n1

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

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

wszystkie . Rodzinę Położenie rozkładów niezmienna przy tym działania: oznacza dla wszystkich .vV ΩfΩf(v)ΩvV

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

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

i zdefiniuj funkcję przezfa:V[0,1]

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

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

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

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

  1. Narysuj indeks z rozkładu dyskretnego na podany przez prawdopodobieństwa , gdzie jest zdefiniowane jak poprzednio .i{0,1,,J}(Ji)(n1)iai/AA

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

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

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

Whuber
źródło
Dzięki za to! Odległość Hamminga w tym przypadku jest tylko w ograniczona do wierzchołków sześcianu; w tym kontekście odległość Hamminga działa izotropowo. Odchodzę od tego, jak sądzę, komplikuje te rzeczy, ponieważ mam więcej niż różnych wartości dla mojego pomiaru odległości? Jakieś ogólne komentarze na ten temat? L1RJJ
facet
Tak: wybór funkcji odległości zależy od tego, co reprezentują wartości w . Ponieważ pytanie zostało sformułowane w sposób abstrakcyjny, naprawdę nie mamy nic do kształtowania opinii na temat tego, co byłoby dobrym wyborem. Odległość Hamminga byłaby odpowiednia dla wartości nominalnych i być może również w innych przypadkach, ale inne odległości mogą działać lepiej, gdy istnieje nieodłączne poczucie odległości dla zestawu . W przypadku binarnym trudno jest uogólnić odległości Hamminga: są już dość ogólne. {1,2,,n}{1,2,,n}n=2
whuber
1

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.

karawan
źródło