Bagaimana cara sampel distribusi multinomial terpotong?

Saya perlu algoritma untuk sampel distribusi multinomial terpotong. Itu adalah,

\vec{x} \sim \frac{1}{Z} \frac{p_{1}^{x_{1}} \dots p_{k}^{x_{k}}}{x_{1}! \dots x_{k}!}

$\vec x \sim \frac{1}{Z} \frac{p_1^{x_1} \dots p_k^{x_k}}{x_1!\dots x_k!}$

di mana adalah konstanta normalisasi, memiliki komponen positif, dan . Saya hanya mempertimbangkan nilai dalam rentang . $Z$ $\vec x$ $k$ $\sum x_i = n$ $\vec{x}$ $\vec a \le \vec x \le \vec b$

Bagaimana saya bisa mencicipi distribusi multinomial terpotong ini?

Catatan: Lihat Wikipedia untuk algoritme untuk mencicipi distribusi multinomial yang tidak terpotong. Apakah ada cara untuk mengadaptasi algoritma ini ke distribusi terpotong?

Versi seragam: Versi masalah yang lebih sederhana adalah mengambil semua sama, . Jika Anda dapat merancang algoritma untuk mencicipi distribusi terpotong dalam kasus ini setidaknya, silakan posting itu. Meskipun bukan jawaban umum, itu akan membantu saya memecahkan masalah praktis lainnya saat ini. $p_i$ $p_i = 1/k$

algorithms multinomial random-generation becko
sumber

Jawaban:

Jika saya memahami Anda dengan benar, Anda ingin mengambil sampel nilai dari distribusi multinomial dengan probabilitas sedemikian rupa sehingga , namun Anda ingin distribusinya terpotong sehingga untuk semua . $x_1,\dots,x_k$ $p_1,\dots,p_k$ $\sum_i x_i = n$ $a_i \le x_i \le b_i$ $x_i$

Saya melihat tiga solusi (tidak seindah dalam kasus non-terpotong):

Terima tolak. Sampel dari multinomial non-terpotong, terima sampel jika sesuai dengan batas pemotongan, jika tidak, tolak dan ulangi prosesnya. Ini cepat, tetapi bisa sangat tidak efisien.

rtrmnomReject <- function(R, n, p, a, b) {
  x <- t(rmultinom(R, n, p))
  x[apply(a <= x & x <= b, 1, all) & rowSums(x) == n, ]
}

Simulasi langsung. Sampel dengan cara yang menyerupai proses penghasil data, yaitu sampel marmer tunggal dari guci acak dan ulangi proses ini sampai Anda mencicipi total kelereng, tetapi saat Anda menggunakan jumlah kelereng dari guci tertentu ( sudah sama dengan ) kemudian berhenti menggambar dari guci tersebut. Saya menerapkan ini dalam skrip di bawah ini. $n$ $x_i$ $b_i$

# single draw from truncated multinomial with a,b truncation points
rtrmnomDirect <- function(n, p, a, b) {
  k <- length(p)

  repeat {
    pp <- p         # reset pp
    x <- numeric(k) # reset x
    repeat {
      if (sum(x<b) == 1) { # if only a single category is left
        x[x<b] <- x[x<b] + n-sum(x) # fill this category with reminder
        break
      }
      i <- sample.int(k, 1, prob = pp) # sample x[i]
      x[i] <- x[i] + 1  
      if (x[i] == b[i]) pp[i] <- 0 # if x[i] is filled do
      # not sample from it
      if (sum(x) == n) break    # if we picked n, stop
    }
    if (all(x >= a)) break # if all x>=a sample is valid
    # otherwise reject
  }

  return(x)
}

Algoritma Metropolis. Akhirnya, pendekatan ketiga dan paling efisien adalah menggunakan algoritma Metropolis . Algoritma ini diinisialisasi dengan menggunakan simulasi langsung (tetapi dapat diinisialisasi secara berbeda) untuk menggambar sampel pertama . Dalam langkah-langkah berikut secara iteratif: nilai proposal diterima sebagai dengan probabilitas , jika tidak nilai diambil dalam itu tempatnya, di mana. Sebagai proposal saya menggunakan fungsi yang mengambil nilai dan secara acak membalik dari 0 ke jumlah kasus dan memindahkannya ke kategori lain. $X_1$ $y = q(X_{i-1})$ $X_i$ $f(y)/f(X_{i-1})$ $X_{i-1}$ $f(x) \propto \prod_i p_i^{x_i}/x_i!$ $q$ $X_{i-1}$ step

# draw R values
# 'step' parameter defines magnitude of jumps
# for Meteropolis algorithm
# 'init' is a vector of values to start with
rtrmnomMetrop <- function(R, n, p, a, b,
                          step = 1,
                          init = rtrmnomDirect(n, p, a, b)) {

  k <- length(p)
  if (length(a)==1) a <- rep(a, k)
  if (length(b)==1) b <- rep(b, k)

  # approximate target log-density
  lp <- log(p)
  lf <- function(x) {
    if(any(x < a) || any(x > b) || sum(x) != n)
      return(-Inf)
    sum(lp*x - lfactorial(x))
  }

  step <- max(2, step+1)

  # proposal function
  q <- function(x) {
    idx <- sample.int(k, 2)
    u <- sample.int(step, 1)-1
    x[idx] <- x[idx] + c(-u, u)
    x
  }

  tmp <- init
  x <- matrix(nrow = R, ncol = k)
  ar <- 0

  for (i in 1:R) {
    proposal <- q(tmp)
    prob <- exp(lf(proposal) - lf(tmp))
    if (runif(1) < prob) {
      tmp <- proposal
      ar <- ar + 1
    }
    x[i,] <- tmp
  }

  structure(x, acceptance.rate = ar/R, step = step-1)
}

Algoritme dimulai pada dan kemudian berkeliaran di berbagai wilayah distribusi. Ini jelas lebih cepat daripada yang sebelumnya, tetapi Anda harus ingat bahwa jika Anda akan menggunakannya untuk sampel sejumlah kecil kasus, maka Anda bisa berakhir dengan imbang yang dekat satu sama lain. Masalah lain adalah bahwa Anda perlu memutuskan tentang ukuran, yaitu seberapa besar lompatan yang harus dibuat oleh algoritma - terlalu kecil dapat menyebabkan bergerak lambat, terlalu besar dapat menyebabkan terlalu banyak proposal yang tidak valid dan menolaknya. Anda dapat melihat contoh penggunaannya di bawah ini. Pada plot Anda dapat melihat: kepadatan marginal di baris pertama, traceplots di baris kedua dan plot yang menunjukkan lompatan berikutnya untuk pasangan variabel. $X_1$ step

n <- 500
a <- 50
b <- 125
p <- c(1,5,2,4,3)/15
k <- length(p)
x <- rtrmnomMetrop(1e4, n, p, a, b, step = 15)

cmb <- combn(1:k, 2)

par.def <- par(mfrow=c(4,5), mar = c(2,2,2,2))
for (i in 1:k)
  hist(x[,i], main = paste0("X",i))
for (i in 1:k)
  plot(x[,i], main = paste0("X",i), type = "l", col = "lightblue")
for (i in 1:ncol(cmb))
  plot(jitter(x[,cmb[1,i]]), jitter(x[,cmb[2,i]]),
       type = "l", main = paste(paste0("X", cmb[,i]), collapse = ":"),
       col = "gray")
par(par.def)

Masalah dengan pengambilan sampel dari distribusi ini adalah yang menggambarkan strategi pengambilan sampel yang sangat tidak efisien secara umum. Bayangkan bahwa dan , dan dekat dengan , dalam hal ini Anda ingin sampel ke kategori dengan probabilitas yang berbeda, tetapi berharap serupa frekuensi pada akhirnya. Dalam kasus ekstrem, bayangkan distribusi dua kategori di mana , dan , $p_1 \ne \dots \ne p_k$ $a_1 = \dots = a_k$ $b_1 = \dots b_k$ $a_i$ $b_i$ $p_1 \gg p_2$ $a_1 \ll a_2$ $b_1 \ll b_2$ , dalam kasus seperti itu Anda mengharapkan sesuatu peristiwa yang sangat langka terjadi (contoh kehidupan nyata dari distribusi tersebut adalah peneliti yang mengulangi pengambilan sampel sampai ia menemukan sampel yang konsisten dengan hipotesisnya, sehingga lebih berkaitan dengan kecurangan daripada pengambilan sampel acak) .

Distribusi jauh lebih bermasalah jika Anda mendefinisikannya sebagai Rukhin (2007, 2008) di mana Anda sampel kasus untuk setiap kategori, yaitu sampel secara proporsional ke . $np_i$ $p_i$

Rukhin, AL (2007). Statistik urutan normal dan jumlah variabel acak geometrik dalam masalah alokasi perawatan. Statistik & surat probabilitas, 77 (12), 1312-1321.

Rukhin, AL (2008). Menghentikan Aturan dalam Masalah Alokasi Seimbang: Distribusi Tepat dan Asimptotik. Analisis Sekuensial, 27 (3), 277-292.

Tim
sumber

y_{i} = x_{i} - a_{i}

$y_i = x_i - a_i$

m = n - \sum_{i} a_{i}

$m = n - \sum_i a_i$

y_{i} \leq b_{i} - a_{i}

$y_i \le b_i - a_i$

x \geq a

$x \ge a$

a

$a$

@becko jika Anda membandingkan pendekatan tersebut dengan yang dijelaskan oleh saya, Anda akan melihat bahwa mereka memberikan solusi yang berbeda .

Tim

Saya tidak mengerti bagaimana mereka bisa berbeda? Yang saya lakukan hanyalah perubahan variabel.

becko

@becko titik awal Anda adalah itu saja x[i] >= a. Bayangkan Anda melemparkan koin bias dengan probabilitas kepala = 0,9. Anda melempar koin sampai Anda mendapatkan setidaknya 10 kepala dan 10 ekor. Pada titik berhenti Anda akan memiliki rata-rata lebih banyak kepala daripada ekor. Mulai pada x[1] = ... = x[k] = aberarti Anda mengabaikan fakta bahwa titik awal masing-masing x[i]berbeda karena berbeda p[i].

Tim

Saya mengerti maksud Anda. Satu-satunya hal yang saya tidak suka tentang solusi Anda adalah bahwa saya pikir itu bisa sangat tidak efisien untuk pilihan parameter tertentu.

becko

Ini adalah usaha saya dalam mencoba menerjemahkan kode R Tim ke Python. Karena saya menghabiskan waktu untuk memahami masalah ini dan mengkodekan algoritme dengan Python, saya berpikir untuk membagikannya di sini kalau-kalau ada orang yang tertarik.

Algoritma Terima-Tolak :

def sample_truncated_multinomial_accept_reject(k, pVec, a, b):
    x = list(np.random.multinomial(k, pVec, size=1)[0])
    h = [x[i] >= a[i] and x[i] <= b[i] for i in range(len(x))]
    while sum(h) < len(h):
        x = list(np.random.multinomial(k, pVec, size=1)[0])
        h = [x[i] >= a[i] and x[i] <= b[i] for i in range(len(x))]
    return x

Simulasi langsung

def truncated_multinomial_direct_sampling_from_urn(k, pVec, a, b):
    n = len(pVec)
    while True:
        pp = pVec 
        x = [0 for _ in range(n)] 
        while True:
            if sum([x[h] < b[h] for h in range(n)])==1:
                indx = [h for h in range(n) if x[h] < b[h]][0]
                x[indx] = k - sum(x)
                break
            i = np.random.choice(n, 1, p=pp)[0]
            x[i] += 1
            if x[i] == b[i]:
                pp = [pp[j]/(1-pp[i]) for j in range(n)]
                pp[i] = 0 
            if sum(x) == k:
                break  
        if sum([x[h] < a[h] for h in range(n)]) == 0:
            break 
    return x

Algoritma Metropolis

def compute_log_function(x, pVec, a, b):
    x_less_a = sum([x[i] < a[i] for i in range(len(pVec))])
    x_more_a = sum([x[i] > b[i] for i in range(len(pVec))])
    if x_less_a or x_more_a or sum(x) != k:
        return float("-inf")
    return np.sum(np.log(pVec)*x - np.array([math.lgamma(h+1) for h in x]))

def sampling_distribution(original, pVec, a, b, step):
    x = copy.deepcopy(original) 
    idx = np.random.choice(len(x), 2, replace=False)
    u = np.random.choice(step, 1)[0]
    x[idx[0]] -= u
    x[idx[1]] += u
    x_less_a = sum([x[i] < a[i] for i in range(len(pVec))])
    x_more_a = sum([x[i] > b[i] for i in range(len(pVec))])
    while x_less_a or x_more_a or sum(x) != k:
        x = copy.deepcopy(original)  
        idx = np.random.choice(len(x), 2, replace=False)
        u = np.random.choice(step, 1)[0]
        x[idx[0]] -= u
        x[idx[1]] += u
        x_less_a = sum([x[i] < a[i] for i in range(len(pVec))])
        x_more_a = sum([x[i] > b[i] for i in range(len(pVec))])
    return x

def sample_truncated_multinomial_metropolis_hasting(k, pVec, a, b, iters, step=1):
    tmp=sample_truncated_multinomial_accept_reject(k, pVec, a, b)[0]
    step = max(2, step)
    for i in range(iters):
        proposal = sampling_distribution(tmp, pVec, a, b, step)
        if compute_log_function(proposal, pVec, a, b) == float("-inf"):
            continue             
        prob = np.exp(np.array(compute_log_function(proposal, pVec, a, b)) -\
                      np.array(compute_log_function(tmp, pVec, a, b)))
        if np.random.uniform() < prob:
            tmp = proposal 
        step -= 1 
    return tmp

Untuk implementasi lengkap dari kode ini, silakan lihat repositori Github saya di

https://github.com/mohsenkarimzadeh/sampling

Mohsen Kiskani
sumber