Algorithmes « basiques »

Algorithme accept-reject

  • On veut échantillonner \(p(\theta|y)\) mais on dispose d'une fonction dite enveloppe \(q(\theta)\) telle que \(p(\theta|y)<Aq(\theta)\) pour tous les \(\theta\)

  • Pour constituer un échantillon on répète alors la procédure:

    1. tirer une valeur \(t\) dans \(q(\theta)\) et une valeur \(u\) dans une uniforme [0,1]

    2. on accepte \(t\) comme une valeur acceptable pour \(p(\theta|y)\) si \(u \leq p(t|y)/Aq(t)\), on la rejette sinon

  • On retient \(A = \max_x\left(\frac{p}{q}\right)\)

  • L'algorithme est d'autant plus efficace que A est proche de 1

Évolutions de l'algorithme accept-reject

Des évolutions à cet algorithme AR ont été proposées

  • ARS : Adaptive rejection sampling (avec tangent method ou derivative-free method), etc

  • L'ARS peut aussi être dans un algorithme de Metropolis (cf. plus loin)=ARMS algorithm.

D'autres algorithmes

  • "importance sampling", "weighted sampling-resampling method" (SIR), etc

  • Ces approches sont proches de l'AR mais sans la nécessité de disposer d'une fonction d'enveloppe. A la place, on utilise des poids \(p/q\). Le poids à un point \(\theta\) est d'autant plus lourd que la fonction \(q\) est proche de \(p\) à ce point.

Manipulation