Comment échantillonner une distribution multinomiale tronquée?

J'ai besoin d'un algorithme pour échantillonner une distribution multinomiale tronquée. C'est,

\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!}$

où est une constante de normalisation, a composantes positives et . Je ne considère que les valeurs de dans la plage . $Z$ $\vec x$ $k$ $\sum x_i = n$ $\vec{x}$ $\vec a \le \vec x \le \vec b$

Comment puis-je échantillonner cette distribution multinomiale tronquée?

Remarque: voir Wikipedia pour un algorithme d'échantillonnage d'une distribution multinomiale non tronquée. Existe-t-il un moyen d'adapter cet algorithme à une distribution tronquée?

Version uniforme: Une version plus simple du problème est de prendre tous les égaux, . Si vous pouvez concevoir un algorithme pour échantillonner la distribution tronquée dans ce cas au moins, veuillez le poster. Bien que ce ne soit pas la réponse générale, cela m'aiderait à résoudre d'autres problèmes pratiques pour le moment. $p_i$ $p_i = 1/k$

algorithms multinomial random-generation Becko
la source

Réponses:

Si je vous comprends bien, vous voulez échantillonner valeurs de la distribution multinomiale avec des probabilités telles que , mais vous voulez que la distribution soit tronquée donc pour tout . $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$

Je vois trois solutions (ni aussi élégantes que dans le cas non tronqué):

Accepter-rejeter. Échantillon à partir de multinomiaux non tronqués, acceptez l'échantillon s'il correspond aux limites de troncature, sinon rejetez et répétez le processus. C'est rapide, mais peut être très inefficace.

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

Simulation directe. Échantillonnez à la mode qui ressemble au processus de génération de données, c'est-à-dire échantillonnez une seule bille dans une urne aléatoire et répétez ce processus jusqu'à ce que vous ayez échantillonné billes au total, mais lorsque vous déployez le nombre total de billes à partir d'une urne donnée ( est déjà égal à ) puis arrêtez de tirer de cette urne. J'ai implémenté cela dans un script ci-dessous. $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)
}

Algorithme Metropolis. Enfin, la troisième approche, la plus efficace, serait d'utiliser l'algorithme Metropolis . L'algorithme est initialisé en utilisant la simulation directe (mais peut être initialisé différemment) pour tirer le premier échantillon . Dans les étapes suivantes de manière itérative: la valeur de proposition est acceptée comme avec la probabilité , sinon $X_1$ $y = q(X_{i-1})$ $X_i$ $f(y)/f(X_{i-1})$ $X_{i-1}$ la valeur est prise à sa place, où . Comme proposition, j'ai utilisé la fonction qui prend la valeur et retourne au hasard de 0 au nombre de cas et la déplace vers une autre catégorie. $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)
}

$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)

Le problème de l'échantillonnage à partir de cette distribution est qu'il décrit une stratégie d'échantillonnage très inefficace en général. Imaginez que $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$

$np_i$ $p_i$

Rukhin, AL (2007). Statistiques d'ordre normal et sommes de variables géométriques aléatoires dans les problèmes d'allocation de traitement. Statistiques et lettres de probabilité, 77 (12), 1312-1321.

Rukhin, AL (2008). Arrêt des règles dans les problèmes d'allocation équilibrée: distributions exactes et asymptotiques. Analyse séquentielle, 27 (3), 277-292.

Tim
la source

Le rejet d'échantillons invalides peut être trop lent. Il est probablement plus simple de faire une traduction,

. De cette façon, vous n'avez que la limite supérieure,

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 si vous comparez une telle approche à celle que j'ai décrite, vous verrez qu'elles donnent des solutions différentes .

Tim

Je ne comprends pas comment ils peuvent être différents? Tout ce que j'ai fait, c'est un changement de variables.

Becko

@becko votre point de départ est tout cela x[i] >= a. Imaginez que vous jetiez une pièce biaisée avec une probabilité de têtes = 0,9. Vous lancez la pièce jusqu'à ce que vous obteniez au moins 10 têtes et 10 queues. Au point d'arrêt, vous auriez en moyenne beaucoup plus de têtes que de queues. Commencer à x[1] = ... = x[k] = asignifie que vous ignorez le fait que les points de départ de chacun x[i]sont différents en raison de différents p[i].

Tim

Je vois ce que tu veux dire. La seule chose que je n'aime pas dans votre solution, c'est que je pense qu'elle pourrait être très inefficace pour des choix particuliers de paramètres.

Becko

Voici mes efforts pour essayer de traduire le code R de Tim en Python. Depuis que j'ai passé un peu de temps à comprendre ce problème et à coder les algorithmes en Python, j'ai pensé à les partager ici au cas où les gens seraient intéressés.

Algorithme d'acceptation-rejet :

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

Simulation directe

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

Algorithme 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

Pour une implémentation complète de ce code, veuillez consulter mon référentiel Github à l'adresse

https://github.com/mohsenkarimzadeh/sampling

Mohsen Kiskani
la source