Common Lisp Package: MICMAC.METROPOLIS-HASTINGS

Metroplis-Hastings MCMC.

README:

FUNCTION

Public

JUMP-TO-SAMPLE (CHAIN JUMP &KEY (RESULT-SAMPLE (STATE CHAIN)))

From the current state of CHAIN make JUMP (from the current distribution of CHAIN) and return the sample where we landed. Reuse RESULT-SAMPLE when possible.

Private

RANDOM-ELEMENT (SEQ &KEY (KEY #'IDENTITY) (START 0) (END (LENGTH SEQ)) (SUM (SUM-SEQ SEQ KEY KEY START START END END)))

Choose an element randomly from the [START,END) subsequence of SEQ with given probabilities. KEY returns the unormalized probability of an element, SUM is the sum of these unnormalized probalities contains unnormalized probabilties. Return the element chosen and its index.

SUM-SEQ (SEQ &KEY (KEY #'IDENTITY) (START 0) (END (LENGTH SEQ)))

Return the sum of elements in the [START,END) subsequence of SEQ.

Undocumented

LOG->ACCEPTANCE-PROBABILITY (X)

RANDOM-UNTIL-DIFFERENT (LIMIT TABU &KEY (TEST #'EQL))

GENERIC-FUNCTION

Public

ACCEPT-JUMP (CHAIN JUMP CANDIDATE)

Called when CHAIN accepts JUMP to CANDIDATE.

ACCEPT-SWAP-CHAIN-STATES (MC3 CHAIN1 CHAIN2)

Swap the states of CHAIN1 and CHAIN2 of MC3.

ACCEPTANCE-PROBABILITY (CHAIN JUMP CANDIDATE)

Calculate the acceptance probability of CANDIDATE to which JUMP leads from the current STATE of CHAIN.

JUMP (CHAIN)

Take a step on the markov chain. Return a boolean indicating whether the proposed jump was accepted.

JUMP-BETWEEN-CHAINS (MC3)

Choose two chains randomly and swap their states with MC3 acceptance probability.

JUMP-TO-SAMPLE* (CHAIN JUMP RESULT-SAMPLE)

This function is called by JUMP-TO-SAMPLE. It is where JUMP-TO-SAMPLE behaviour shall be customized.

LOG-JUMP-PROBABILITY-RATIO (CHAIN JUMP TARGET)

Return Q(TARGET->STATE) / Q(STATE->TARGET) where Q is the jump distribution and JUMP is from the current STATE of CHAIN to TARGET sample.

LOG-PROBABILITY-RATIO (CHAIN SAMPLE1 SAMPLE2)

Return P(SAMPLE1)/P(SAMPLE2). It's in the log domain to avoid overflows and the ratio part is because that it may allow computational shortcuts as opposed to calculating unnormalized probabilities separately.

LOG-PROBABILITY-RATIO-TO-JUMP-TARGET (CHAIN JUMP TARGET)

Return P(TARGET)/P(STATE) where JUMP is from the current state of CHAIN to TARGET sample. This can be specialized for speed. The default implementation just falls back on LOG-PROBABILITY-RATIO.

MAYBE-SWAP-CHAIN-STATES (MC3 CHAIN1 CHAIN2 ACCEPTANCE-PROBABILITY)

Swap of states of CHAIN1 and CHAIN2 of MC3 with ACCEPTANCE-PROBABILITY.

PREPARE-JUMP-DISTRIBUTION (CHAIN)

Prepare for sampling from the F(X) = Q(SAMPLE->X) distribution. Called by RANDOM-JUMP. The around method ensures that nothing is done unless there was a state change.

RANDOM-JUMP (CHAIN)

Sample a jump from the current distribution of jumps that was computed by PREPARE-JUMP-DISTRIBUTION.

REJECT-JUMP (CHAIN JUMP CANDIDATE)

Called when CHAIN rejects JUMP to CANDIDATE. It does nothing by default, it's just a convenience for debugging.

REJECT-SWAP-CHAIN-STATES (MC3 CHAIN1 CHAIN2)

Called when the swap of states of CHAIN1 and CHAIN2 is rejected. It does nothing by default, it's just a convenience for debugging.

Private

MAYBE-JUMP (CHAIN JUMP CANDIDATE ACCEPTANCE-PROBABILITY)

Randomly accept or reject JUMP to CANDIDATE from the current state of CHAIN with ACCEPTANCE-PROBABILITY.

Undocumented

SET-STATE (STATE CHAIN)

SLOT-ACCESSOR

Public

STATE (OBJECT)

This is the current sample where the chain is.

TEMPERATURE (OBJECT)

The PROBABILITY-RATIO of samples is raised to the power of 1 / TEMPERATURE before calculating the acceptance probability. This effectively flattens the peaks if TEMPERATURE > 1 which makes it easier for the chain to traverse deep valleys.

SETFTEMPERATURE (NEW-VALUE OBJECT)

The PROBABILITY-RATIO of samples is raised to the power of 1 / TEMPERATURE before calculating the acceptance probability. This effectively flattens the peaks if TEMPERATURE > 1 which makes it easier for the chain to traverse deep valleys.

Private

Undocumented

CANDIDATE (OBJECT)

SETFCANDIDATE (NEW-VALUE OBJECT)

HOT-CHAINS (OBJECT)

JUMP-DISTRIBUTION-PREPARED-P (OBJECT)

SETFJUMP-DISTRIBUTION-PREPARED-P (NEW-VALUE OBJECT)

P-JUMPS (OBJECT)

CLASS

Public

ENUMERATING-CHAIN

A simple abstract chain subclass that explicitly enumerates the probabilities of the distribution.

MC-CHAIN

A simple markov chain for Metropolis Hastings. With temperature it is suitable for MC3.

MC3-CHAIN

High probability island separated by low valley make the chain poorly mixing. MC3-CHAIN has a number of HOT-CHAINS that have state probabilities similar to that of the main chain but less jagged. Often it suffices to set the temperatures of the HOT-CHAINS higher use the very same base probability distribution.

TRACING-CHAIN

Mix this in with your chain to have it print trace of acceptances/rejections.