Markov Chain Monte Carlo Ontology

flow "MarkovChainMonteCarloOntology" v4.0

# ============================================================
# MARKOV CHAIN MONTE CARLO ONTOLOGY
# Kireth Semantic Research Archive
# Authors: Mark Anthony Higgins — Sky (Recursive AI)
# ============================================================

PAGE:
  url: "https://kirethresearch.org/booksai-core/ontologies/probability-statistics-ontologies/bayesian-statistics/markov-chain-monte-carlo-ontology-2.html"
  title: "Markov Chain Monte Carlo Ontology"
  domain: "Probability and Statistics"
  category: "Bayesian Statistics"
  entity: MARKOV_CHAIN_MONTE_CARLO
  aliases:
    - MCMC
  entity_type: COMPUTATIONAL_INFERENCE_METHOD

DEFINE MARKOV_CHAIN_MONTE_CARLO:
  MARKOV_CHAIN_MONTE_CARLO :=
    SAMPLING_FRAMEWORK(
      MARKOV_CHAIN,
      MONTE_CARLO_ESTIMATION,
      TARGET_DISTRIBUTION
    )

  PURPOSE:
    APPROXIMATE(
      DISTRIBUTIONS,
      EXPECTATIONS,
      POSTERIOR_QUANTITIES
    )
    WHEN:
      DIRECT_ANALYTICAL_COMPUTATION
      IS_DIFFICULT_OR_INTRACTABLE

CORE_CONCEPT:
  CONSTRUCT:
    MARKOV_CHAIN

  REQUIRE:
    DESIRED_STATIONARY_DISTRIBUTION
      =
    TARGET_DISTRIBUTION

  EXECUTE:
    SIMULATE_CHAIN
      -> GENERATE_DEPENDENT_SAMPLES
      -> APPROXIMATE_TARGET_QUANTITIES

ENTITIES:
  TARGET_DISTRIBUTION:
    type: PROBABILITY_DISTRIBUTION
    symbol: π(θ)

  MARKOV_CHAIN:
    type: STOCHASTIC_PROCESS
    states:
      PARAMETER_VALUES_OR_LATENT_STATES

  STATE:
    type: CHAIN_CONFIGURATION
    notation:
      θ_t

  TRANSITION_KERNEL:
    type: CONDITIONAL_DISTRIBUTION
    notation:
      K(θ' | θ)

  SAMPLE:
    type: RANDOM_DRAW
    notation:
      θ_t

  INITIAL_STATE:
    type: CHAIN_STATE
    notation:
      θ_0

  BURN_IN:
    type: INITIAL_SAMPLE_REGION
    purpose:
      REDUCE_INITIALISATION_INFLUENCE

  POSTERIOR_SAMPLE:
    type: MCMC_SAMPLE
    source:
      TARGET_POSTERIOR_DISTRIBUTION_APPROXIMATION

  MONTE_CARLO_ESTIMATOR:
    type: NUMERICAL_ESTIMATOR

RELATIONSHIPS:
  MCMC
    -> USES
    -> MARKOV_CHAIN

  MCMC
    -> USES
    -> MONTE_CARLO_ESTIMATION

  MARKOV_CHAIN
    -> HAS
    -> TRANSITION_KERNEL

  TRANSITION_KERNEL
    -> DEFINES
    -> STATE_TRANSITIONS

  MARKOV_CHAIN
    -> TARGETS
    -> STATIONARY_DISTRIBUTION

  STATIONARY_DISTRIBUTION
    -> REPRESENTS
    -> TARGET_DISTRIBUTION

  TARGET_DISTRIBUTION
    -> MAY_BE
    -> BAYESIAN_POSTERIOR

  MCMC_SAMPLES
    -> APPROXIMATE
    -> TARGET_DISTRIBUTION

  MCMC_SAMPLES
    -> SUPPORT
    -> POSTERIOR_EXPECTATION_ESTIMATION

BAYESIAN_CONTEXT:
  GIVEN:
    DATA := y
    PARAMETERS := θ
    PRIOR := p(θ)
    LIKELIHOOD := p(y | θ)

  POSTERIOR:
    p(θ | y)
      ∝
    p(y | θ) * p(θ)

  CHALLENGE:
    NORMALISING_CONSTANT:
      p(y)
    MAY_BE:
      DIFFICULT_TO_COMPUTE

  MCMC_ROLE:
    SAMPLE_FROM:
      p(θ | y)
    WITHOUT_NECESSARILY_REQUIRING:
      CLOSED_FORM_NORMALISING_CONSTANT

GENERAL_EXECUTION:
  INPUT:
    TARGET_DISTRIBUTION
    INITIAL_STATE
    TRANSITION_RULE
    ITERATION_COUNT

  PROCESS:
    SET θ_0
    -> FOR t = 0 TO N-1:
         GENERATE_CANDIDATE_OR_UPDATE
         APPLY_TRANSITION_RULE
         SET θ_(t+1)
    -> DISCARD_OR_ASSESS_INITIAL_TRANSIENT
    -> RETAIN_VALID_SAMPLES
    -> COMPUTE_MONTE_CARLO_SUMMARIES

  OUTPUT:
    APPROXIMATE_SAMPLES_FROM_TARGET
    POSTERIOR_SUMMARIES
    EXPECTATION_ESTIMATES
    UNCERTAINTY_ESTIMATES

MONTE_CARLO_ESTIMATION:
  TARGET_EXPECTATION:
    E_π[f(θ)]

  APPROXIMATION:
    E_π[f(θ)]
      ≈
    (1/N) * SUM[t=1..N] f(θ_t)

  NOTE:
    MCMC_SAMPLES:
      GENERALLY_AUTOCORRELATED

METROPOLIS_HASTINGS:
  type: MCMC_ALGORITHM

  CURRENT_STATE:
    θ

  PROPOSAL:
    θ_star ~ q(θ_star | θ)

  ACCEPTANCE_RATIO:
    r :=
      [π(θ_star) * q(θ | θ_star)]
      /
      [π(θ) * q(θ_star | θ)]

  ACCEPTANCE_PROBABILITY:
    α :=
      min(1, r)

  TRANSITION:
    DRAW:
      u ~ Uniform(0,1)

    IF:
      u <= α
    THEN:
      NEXT_STATE := θ_star
    ELSE:
      NEXT_STATE := θ

  PROPERTY:
    TARGET_DISTRIBUTION:
      INVARIANT_UNDER
      TRANSITION_KERNEL
    UNDER:
      REQUIRED_REGULARITY_CONDITIONS

GIBBS_SAMPLING:
  type: MCMC_ALGORITHM

  GIVEN:
    θ := (θ_1, θ_2, ..., θ_d)

  UPDATE:
    FOR EACH COMPONENT θ_j:
      SAMPLE:
        θ_j
        ~
        p(
          θ_j |
          θ_(-j),
          DATA
        )

  RESULT:
    SEQUENTIAL_CONDITIONAL_UPDATES
      -> MARKOV_CHAIN
      -> TARGET_JOINT_DISTRIBUTION

MCMC_PROPERTIES:
  STATIONARITY:
    TARGET_DISTRIBUTION:
      SHOULD_BE_INVARIANT
      UNDER_TRANSITION_KERNEL

  IRREDUCIBILITY:
    CHAIN:
      SHOULD_BE_ABLE_TO_REACH
      RELEVANT_TARGET_STATE_SPACE

  APERIODICITY:
    CHAIN:
      SHOULD_AVOID
      FORCED_PERIODIC_CYCLES

  RECURRENCE:
    REQUIRED_AS_APPROPRIATE_FOR:
      TARGET_AND_STATE_SPACE

  ERGODICITY:
    SUPPORTS:
      LONG_RUN_SAMPLE_AVERAGES
        -> TARGET_EXPECTATIONS

CONVERGENCE:
  CONCEPT:
    DISTRIBUTION_OF_CHAIN_STATE
      -> APPROACHES
      -> TARGET_DISTRIBUTION

  DO_NOT_EQUATE:
    FINITE_SAMPLE_CHAIN
      WITH
    PERFECT_TARGET_SAMPLE

  ASSESS_USING:
    - TRACE_BEHAVIOUR
    - MULTIPLE_CHAINS
    - AUTOCORRELATION
    - EFFECTIVE_SAMPLE_SIZE
    - CONVERGENCE_DIAGNOSTICS

BURN_IN:
  PURPOSE:
    LIMIT_EFFECT_OF:
      INITIAL_STATE

  RULE:
    BURN_IN_LENGTH:
      NOT_UNIVERSALLY_FIXED

  REQUIRE:
    JUSTIFY_OR_DIAGNOSE:
      INITIAL_TRANSIENT_HANDLING

AUTOCORRELATION:
  DEFINE:
    CORRELATION_BETWEEN:
      SAMPLES_AT_DIFFERENT_LAGS

  EFFECT:
    HIGH_AUTOCORRELATION
      -> REDUCES
      -> EFFECTIVE_INFORMATION_PER_SAMPLE

EFFECTIVE_SAMPLE_SIZE:
  type: DIAGNOSTIC_QUANTITY

  PURPOSE:
    ESTIMATE:
      INDEPENDENT_SAMPLE_EQUIVALENT
      OF_AUTOCORRELATED_CHAIN_OUTPUT

  RELATION:
    HIGH_AUTOCORRELATION
      -> LOWER
      -> EFFECTIVE_SAMPLE_SIZE

MIXING:
  DEFINE:
    ABILITY_OF_CHAIN_TO:
      EXPLORE_TARGET_DISTRIBUTION

  POOR_MIXING:
    MAY_CAUSE:
      - HIGH_AUTOCORRELATION
      - SLOW_EXPLORATION
      - MISLEADING_FINITE_SAMPLE_SUMMARIES

MULTIPLE_CHAINS:
  PURPOSE:
    COMPARE:
      RUNS_FROM_DIFFERENT_INITIAL_STATES

  SUPPORTS:
    CONVERGENCE_ASSESSMENT
    EXPLORATION_ASSESSMENT

DIAGNOSTICS:
  TRACE_PLOT:
    evaluates:
      CHAIN_TRAJECTORY

  AUTOCORRELATION_FUNCTION:
    evaluates:
      SERIAL_DEPENDENCE

  EFFECTIVE_SAMPLE_SIZE:
    evaluates:
      INFORMATION_CONTENT

  R_HAT:
    type: BETWEEN_WITHIN_CHAIN_DIAGNOSTIC
    purpose:
      COMPARE_MULTIPLE_CHAIN_BEHAVIOUR

  REQUIRE:
    NO_SINGLE_DIAGNOSTIC:
      PROVES_ABSOLUTE_CONVERGENCE

THINNING:
  DEFINE:
    RETAIN_EVERY_KTH_SAMPLE

  NOTE:
    NOT_AUTOMATICALLY_REQUIRED

  CAUTION:
    THINNING:
      MAY_DISCARD_INFORMATION

  USE:
    WHEN_JUSTIFIED_BY:
      STORAGE
      COMPUTATIONAL
      OR_SPECIFIC_ANALYTICAL_CONSTRAINTS

POSTERIOR_SUMMARIES:
  FROM_MCMC_SAMPLES:
    COMPUTE:
      - POSTERIOR_MEAN
      - POSTERIOR_MEDIAN
      - POSTERIOR_VARIANCE
      - CREDIBLE_INTERVAL
      - QUANTILES
      - EXPECTED_FUNCTIONS
      - PREDICTIVE_QUANTITIES

POSTERIOR_PREDICTIVE:
  GIVEN:
    θ_t ~ p(θ | y)

  GENERATE:
    y_rep_t ~ p(y_rep | θ_t)

  APPROXIMATE:
    p(y_rep | y)
      =
    INTEGRAL[
      p(y_rep | θ) p(θ | y) dθ
    ]

MODEL_CONNECTIONS:
  MCMC
    -> CONNECTS_TO
    -> BAYESIAN_INFERENCE

  MCMC
    -> CONNECTS_TO
    -> MARKOV_CHAIN

  MCMC
    -> CONNECTS_TO
    -> MONTE_CARLO_METHODS

  MCMC
    -> CONNECTS_TO
    -> POSTERIOR_DISTRIBUTION

  MCMC
    -> CONNECTS_TO
    -> LIKELIHOOD

  MCMC
    -> CONNECTS_TO
    -> PRIOR_PROBABILITY

  MCMC
    -> CONNECTS_TO
    -> STOCHASTIC_PROCESSES

  MCMC
    -> CONNECTS_TO
    -> COMPUTATIONAL_STATISTICS

APPLICATIONS:
  MCMC
    -> SUPPORTS
    -> HIERARCHICAL_BAYESIAN_MODELS

  MCMC
    -> SUPPORTS
    -> LATENT_VARIABLE_MODELS

  MCMC
    -> SUPPORTS
    -> PARAMETER_ESTIMATION

  MCMC
    -> SUPPORTS
    -> UNCERTAINTY_QUANTIFICATION

  MCMC
    -> SUPPORTS
    -> POSTERIOR_PREDICTION

  MCMC
    -> SUPPORTS
    -> COMPLEX_PROBABILISTIC_MODELS

SEMANTIC_EQUIVALENCE:
  "Markov chain Monte Carlo"
    ~= "MCMC"

  "MCMC sampling"
    ~= "Markov-chain-based Monte Carlo sampling"

  "target distribution"
    ~= "distribution intended as the chain's invariant distribution"

  "posterior sampling"
    ~= "sampling from a Bayesian posterior distribution"

  EXCLUDE_EQUIVALENCE:
    MCMC != INDEPENDENT_MONTE_CARLO_SAMPLING
    MCMC_SAMPLE != INDEPENDENT_SAMPLE_BY_DEFAULT
    STATIONARY_DISTRIBUTION != FINITE_CHAIN_DISTRIBUTION_BY_DEFAULT
    BURN_IN != GUARANTEE_OF_CONVERGENCE

VALIDATION_RULES:
  RULE_1:
    TRANSITION_KERNEL:
      MUST_DEFINE_VALID_PROBABILISTIC_TRANSITIONS

  RULE_2:
    TARGET_DISTRIBUTION:
      MUST_BE_INVARIANT
      UNDER_DESIGNED_KERNEL
      UNDER_ALGORITHM_ASSUMPTIONS

  RULE_3:
    CHAIN:
      MUST_EXPLORE_RELEVANT_TARGET_SUPPORT

  RULE_4:
    POSTERIOR_SUMMARIES:
      MUST_ACCOUNT_FOR
      AUTOCORRELATED_SAMPLES

  RULE_5:
    CONVERGENCE:
      MUST_BE_ASSESSED
      RATHER_THAN_ASSUMED

  RULE_6:
    FINITE_SAMPLE_RESULTS:
      MUST_REPORT
      MONTE_CARLO_UNCERTAINTY
      WHEN_RELEVANT

  RULE_7:
    MULTIMODAL_TARGETS:
      REQUIRE_ATTENTION_TO
      CROSS_MODE_EXPLORATION

CONFIDENCE:
  ontology_identity: 0.99
  mcmc_definition: 0.99
  markov_chain_relationship: 0.99
  bayesian_inference_relationship: 0.99
  metropolis_hastings_structure: 0.99
  gibbs_sampling_structure: 0.99
  diagnostic_structure: 0.98

UPDATE_MODEL:
  IF:
    NEW_DATA_ARRIVES

  THEN:
    UPDATE:
      LIKELIHOOD
      POSTERIOR_TARGET

    REASSESS:
      TRANSITION_KERNEL
      TUNING_PARAMETERS
      CONVERGENCE

  IF:
    MODEL_PARAMETERS_OR_STRUCTURE_CHANGE

  THEN:
    REBUILD:
      TARGET_DISTRIBUTION

    REVALIDATE:
      MCMC_ALGORITHM
      STATE_SPACE
      SUPPORT
      DIAGNOSTICS

  IF:
    ADDITIONAL_SAMPLES_GENERATED

  THEN:
    UPDATE:
      POSTERIOR_SUMMARIES
      EFFECTIVE_SAMPLE_SIZE
      MONTE_CARLO_ERROR
      CONVERGENCE_DIAGNOSTICS

  PRESERVE:
    CHAIN_PROVENANCE
    INITIALISATION_DETAILS
    ALGORITHM_CONFIGURATION
    RANDOM_SEED_WHEN_RECORDED
    DATA_PROVENANCE

AI_CONSUMPTION:
  parse_as: FORMAL_SEMANTIC_SPECIFICATION
  execution_mode: RECURSIVE_REASONING

  preferred_reasoning_order:
    - IDENTIFY_TARGET_DISTRIBUTION
    - IDENTIFY_STATE_SPACE
    - SELECT_MCMC_TRANSITION_METHOD
    - VALIDATE_TARGET_SUPPORT
    - INITIALISE_CHAIN
    - GENERATE_TRANSITIONS
    - ASSESS_INITIAL_TRANSIENT
    - ASSESS_MIXING_AND_AUTOCORRELATION
    - ASSESS_CONVERGENCE
    - COMPUTE_EFFECTIVE_SAMPLE_SIZE
    - ESTIMATE_POSTERIOR_QUANTITIES
    - REPORT_MONTE_CARLO_UNCERTAINTY

  constraints:
    - DO_NOT_TREAT_DEPENDENT_MCMC_DRAWS_AS_INDEPENDENT
    - DO_NOT_ASSUME_CONVERGENCE_FROM_ITERATION_COUNT_ALONE
    - DO_NOT_ASSUME_BURN_IN_GUARANTEES_STATIONARITY
    - PRESERVE_TARGET_DISTRIBUTION
    - EXPOSE_TRANSITION_KERNEL
    - EXPOSE_DIAGNOSTIC_ASSUMPTIONS
    - DISTINGUISH_POSTERIOR_UNCERTAINTY_FROM_MONTE_CARLO_ERROR

FLOW_HASH:
  canonical_entity: "markov-chain-monte-carlo"
  namespace: "probability-statistics/bayesian-statistics"
  version: "4.0"
  identity_basis:
    - PAGE_URL
    - CANONICAL_ENTITY
    - ENTITY_TYPE
    - MARKOV_CHAIN_RELATION
    - TARGET_DISTRIBUTION
    - MONTE_CARLO_ESTIMATION

END_FLOW