Distribusi pada himpunan bagian dari

9

Saya ingin tahu apakah ada jenis distribusi standar pada himpunan bilangan bulat . Secara ekuivalen, kita dapat menyatakan ini sebagai distribusi pada vektor panjang dari hasil biner, misalnya jika maka sesuai dengan vektor .{1,2,...,J}JJ=5{1,3,5}(1,0,1,0,1)

Idealnya yang saya cari adalah distribusi , berasal dari keluarga yang diindeks oleh parameter dimensi hingga , yang akan mendistribusikan massanya sedemikian rupa sehingga dua biner vektor dan akan memiliki kesamaan probabilitas jika mereka "berdekatan", yaitu dan memiliki probabilitas yang serupa. Sungguh, apa yang ingin saya lakukan mudah-mudahan, adalah meletakkan pada sehingga jika saya tahu cukup besar maka mungkin relatif besar untuk vektor yang jauh dari .νθ()θr1r2r1=(0,0,1,0,1)r2=(0,0,1,1,1)θνθ(r1)νθ(r2)r1

Salah satu strategi yang muncul dalam pikiran adalah meletakkan metrik atau ukuran dispersi lain pada pada dan kemudian mengambil , atau yang serupa. Contoh eksplisit adalah dalam analogi dengan distribusi normal. Tidak apa-apa, tapi saya berharap ada sesuatu yang standar dan sesuai dengan analisis Bayesian; dengan ini saya tidak dapat menuliskan konstanta normalisasi.dθ{0,1}Jνθ(r)exp(dθ(r,μ))exp{rμ2/(2σ2)}

orang
sumber
Sampling subset adalah masalah dasar dalam metodologi survei.
Stéphane Laurent
@Stephane yakin, tapi saya pikir masalah saya berbeda karena saya memiliki beberapa struktur tambahan yang diinginkan yang ingin saya distribusikan oleh distribusi saya. Mungkin mengutarakan pertanyaan dalam hal himpunan bagian adalah ide yang buruk karena saya memiliki gagasan yang kabur tentang bekerja untuk saya.
pria
Apakah Anda bermaksud menulis "... lalu mungkin kecil ..."? Sejauh konstanta normalisasi berjalan, pertimbangkan untuk menggunakan jarak Hamming untuk metrik: untuk keluarga distribusi skala-lokasi, Anda dapat menghitung konstanta itu sebagai jumlah dari hanya istilah . Selain itu, semua keluarga yang memenuhi kriteria Anda dapat dijelaskan hanya dengan parameter diskrit (untuk lokasi) dan parameter kontinuJ + 1vθ(r2)J+1JJJ
whuber
@whuber tidak, maksudku besar. Saya ingin untuk mendistribusikan massanya di sekitar titik yang berdekatan. Mungkin akan lebih tepat untuk mengutarakan pertanyaannya dengan meletakkan distribusi pada verticies kubus. Saya telah mempertimbangkan jarak Hamming (yang saya kira sama dengan dalam kasus saya); Saya mungkin ingin mengubahnya sebagai, dan saya kira mungkin harus melakukan beberapa MCMC untuk mengambil sampel dari distribusi tersebut. L 1 ¢ | r i - μ iνθ()L1|riμiσi|
pria
Oh, saya mengerti sekarang. Tapi bukan itu yang awalnya Anda katakan. Misalnya, dalam karakterisasi Anda, jika besar, dan adalah himpunan vektor "jauh" dari , dan adalah vektor yang tidak ada dalam , maka juga harus "mungkin" menjadi besar. Tetapi "tidak jauh" dan "dekat" tidak berarti hal yang persis sama. Akan lebih sederhana - dan lebih konsisten secara internal - untuk mengulangi kondisi seperti yang Anda lakukan dalam komentar Anda. Tapi tidak, Anda tidak perlu MCMC untuk mengambil sampel dari distribusi skala lokasi berdasarkan jarak Hamming: ada cara yang jauh lebih efisien. R r 1 r 2 R ν ( r 2 )ν(r1)Rr1r2Rν(r2)
whuber

Jawaban:

6

Anda mungkin menyukai keluarga lokasi berdasarkan jarak Hamming , karena kekayaan, fleksibilitas, dan kemampuan penelusuran komputasinya.


Notasi dan definisi

Ingatlah bahwa dalam modul berdimensi-bebas bebas dengan basis , jarak Hamming antara dua vektor dan adalah jumlah tempat di mana .( e 1 , e 2 , , e J ) δ H v = v 1 e 1 + + v J e J w = w 1 e 1 + + w J e J i v iw iV(e1,e2,,eJ) δHv=v1e1++vJeJw=w1e1++wJeJiviwi

Diberikan asal , partisi jarak Hamming ke dalam bola , , di mana . Ketika cincin dasar memiliki elemen, memiliki elemen dan memiliki elemen. (Ini mengikuti segera dari mengamati bahwa unsur-unsur berbeda dari persis di tempat - yang adaV S i ( v 0 )i=0,1,,J S i ( v 0 )={ wV | δ H ( w , v 0 )=i}nV n J S i ( v ) ( Jv0VVSi(v0)i=0,1,,JSi(v0)={wV | δH(w,v0)=i}nVnJSi(v)Si(v)vi ( J(Ji)(n1)iSi(v)vi n-1(Ji)kemungkinan - dan bahwa ada, secara mandiri, pilihan nilai untuk setiap tempat.)n1

Terjemahan affine dalam berlaku secara alami pada distribusinya untuk memberi keluarga lokasi. Khususnya, ketika adalah distribusi apa pun pada (yang berarti sedikit lebih dari , untuk semua , dan ) dan adalah elemen , maka juga merupakan distribusi dimanaf V f : V [ 0 , 1 ] f ( v ) 0 vV vV f ( v ) = 1 w V f ( w )VfVf:V[0,1]f(v)0vVvVf(v)=1wVf(w)

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

untuk semua . Sebuah keluarga lokasi distribusi adalah invarian dalam tindakan ini: menyiratkan untuk semua .Ω f Ω f ( v )Ω vVvV ΩfΩf(v)ΩvV

Konstruksi

Ini memungkinkan kami untuk menentukan keluarga distribusi yang berpotensi menarik dan bermanfaat dengan menentukan bentuk mereka pada satu vektor tetap , yang untuk kenyamanan saya akan menjadi , dan menerjemahkan "menghasilkan distribusi" ini di bawah tindakan untuk mendapatkan keluarga lengkap . Untuk mencapai properti yang diinginkan yang harus memiliki nilai yang sebanding di titik terdekat, cukup minta properti dari semua distribusi yang dihasilkan.0 = ( 0 , 0 , ... , 0 ) V Ω fv0=(0,0,,0)VΩf

Untuk melihat bagaimana ini bekerja, mari kita membangun keluarga lokasi semua distribusi yang menurun dengan meningkatnya jarak. Karena hanya jarak Hamming yang mungkin, pertimbangkan setiap urutan penurunan bilangan real non-negatif = . Seta 0 a 0a 1a J0J+1a0a0a1aJ0

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

dan tentukan fungsi olehfa:V[0,1]

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

Kemudian, seperti mudah untuk memeriksa, adalah distribusi pada . Selanjutnya, jika dan hanya jika adalah kelipatan positif dari (sebagai vektor dalam ). Jadi, jika kita suka, kita dapat membuat standar menjadi . V f suatu = f sebuah ' a ' a R J + 1 a a 0 = 1faVfa=faaaRJ+1aa0=1

Dengan demikian, konstruksi ini memberikan parameterisasi eksplisit dari semua distribusi invarian lokasi yang berkurang dengan jarak Hamming: distribusi tersebut dalam bentuk untuk beberapa urutan dan beberapa vektor . a = 1 a 1a 2a J0 vVfa(v)a=1a1a2aJ0vV

Parameterisasi ini memungkinkan spesifikasi priors yang sesuai: faktorkan menjadi prior di lokasi dan prior pada shape . (Tentu saja orang dapat mempertimbangkan kumpulan prior yang lebih besar di mana lokasi dan bentuk dan tidak independen, tetapi ini akan menjadi usaha yang lebih rumit.)ava

Menghasilkan nilai acak

Salah satu cara untuk mengambil sampel dari adalah secara bertahap dengan memfaktorkannya ke dalam distribusi di atas radio bola dan distribusi lain yang tergantung pada setiap bola:fa(v)

  1. Gambarkan indeks dari distribusi diskrit pada diberikan oleh probabilitas , di mana didefinisikan seperti sebelumnya .{ 0 , 1 , , J } ( Ji{0,1,,J}A(Ji)(n1)iai/AA

  2. Indeks sesuai dengan himpunan vektor yang berbeda dari tepat di tempat . Oleh karena itu, memilih orang-orang menempatkan keluar dari mungkin himpunan bagian, memberikan masing-masing probabilitas yang sama. (Ini hanya contoh dari subscript dari tanpa pengganti.) Biarkan bagian ini tempat ditulis .v i i ( Jivii iJiI(Ji)iJ iI

  3. Gambarkan elemen dengan secara independen memilih nilai secara seragam dari himpunan skalar yang tidak sama dengan untuk semua dan sebaliknya atur . Secara ekuivalen, buat vektor dengan memilih secara seragam secara acak dari skalar bukan nol ketika dan jika tidak, atur . Set .w j v j j I w j = v j u u j j I u j = 0 w = v + uwwjvjjIwj=vjuujjIuj=0w=v+u

Langkah 3 tidak perlu dalam kasus biner.


Contoh

Berikut ini adalah Rimplementasi untuk menggambarkan.

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
}

Sebagai contoh penggunaannya:

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

Ini membutuhkan detik untuk menggambar elemen awal dari distribusi mana , (case biner), , dan menurun secara eksponensial.10 4 f ( v ) a J = 10 n = 2 v = ( 1 , 1 , , 1 ) a = ( 2 11 , 2 10 , , 2 1 )0.2104fa(v)J=10n=2v=(1,1,,1)a=(211,210,,21)

(Algoritma ini tidak mengharuskan berkurang; dengan demikian, ia akan menghasilkan variasi acak dari sembarang keluarga lokasi, bukan hanya yang unimodal.)a

whuber
sumber
Terima kasih untuk ini! Jarak Hamming dalam hal ini hanya di terbatas pada kubus vertikal; dalam konteks itu, jarak Hamming bertindak isotropis. Semakin jauh dari yang saya kira merumitkan hal-hal ini karena saya memiliki lebih dari nilai yang berbeda untuk mengukur jarak saya? Ada komentar umum tentang ini? R J JL1RJJ
pria
Ya: pilihan fungsi jarak akan tergantung pada apa yang diwakili oleh nilai dalam . Karena pertanyaan telah dirumuskan secara abstrak, kami benar-benar tidak memiliki apa-apa untuk membentuk pendapat tentang apa yang akan menjadi pilihan yang baik. Jarak Hamming akan sesuai untuk nilai nominal dan mungkin dalam kasus lain juga, tetapi jarak lain mungkin bekerja lebih baik ketika ada rasa jarak yang melekat untuk himpunan . Dalam kasus biner , sulit untuk menyamaratakan jarak Hamming: mereka sudah cukup umum. { 1 , 2 , ... , n } n = 2{1,2,,n}{1,2,,n}n=2
whuber
1

Sampel dari titik proses k-determinan memodelkan distribusi lebih dari himpunan bagian yang mendorong keragaman, sehingga item serupa kurang mungkin terjadi bersama-sama dalam sampel. Mengacu pada pengambilan sampel titik proses penentuan-K oleh Alex Kulesza, Ben Taskar.

mobil jenazah
sumber