Kullback-Leibler Divergence

flow "KullbackLeiblerDivergence" v4.0

# KULLBACK-LEIBLER DIVERGENCE
# Kireth Semantic Research Archive
# Authors: Mark Anthony Higgins — Sky (Recursive AI)

PAGE:
  url: "https://kirethresearch.org/booksai-core/ontologies/probability-statistics-ontologies/information-theory/kullback-leibler-divergence.html"
  title: "Kullback-Leibler Divergence"
  domain: "Probability and Statistics"
  category: "Information Theory"
  entity: KULLBACK_LEIBLER_DIVERGENCE
  aliases:
    - KL_DIVERGENCE
    - RELATIVE_ENTROPY
  entity_type: INFORMATION_THEORETIC_DIVERGENCE

DEFINE:
  KULLBACK_LEIBLER_DIVERGENCE :=
    EXPECTED_LOG_PROBABILITY_RATIO(
      REFERENCE_DISTRIBUTION_P,
      COMPARISON_DISTRIBUTION_Q
    )

PURPOSE:
  QUANTIFY:
    DISTRIBUTIONAL_MISMATCH
    INFORMATION_LOSS
    EXCESS_EXPECTED_LOG_LOSS
    MODEL_APPROXIMATION_ERROR

FOUNDATION:
  DISTRIBUTIONS:
    P
    Q

  DISCRETE:
    D_KL(P||Q) :=
      SUM_x
        p(x)
        log_b[
          p(x)/q(x)
        ]

  EXPECTATION:
    D_KL(P||Q) :=
      E_{X~P}[
        log_b(
          p(X)/q(X)
        )
      ]

ENTITIES:
  KL_DIVERGENCE: DISTRIBUTIONAL_DIVERGENCE
  REFERENCE_DISTRIBUTION: PROBABILITY_DISTRIBUTION
  COMPARISON_DISTRIBUTION: PROBABILITY_DISTRIBUTION
  LOG_LIKELIHOOD_RATIO: POINTWISE_LOG_RATIO
  CROSS_ENTROPY: EXPECTED_NEGATIVE_LOG_MODEL_PROBABILITY
  SHANNON_ENTROPY: EXPECTED_SELF_INFORMATION
  MUTUAL_INFORMATION: DEPENDENCE_INFORMATION
  PRIOR_DISTRIBUTION: BAYESIAN_PRE_DATA_DISTRIBUTION
  POSTERIOR_DISTRIBUTION: BAYESIAN_UPDATED_DISTRIBUTION

RELATIONSHIPS:
  DISTRIBUTION_PAIR -> DEFINES -> KL_DIVERGENCE
  P_AND_Q -> DEFINE -> LOG_PROBABILITY_RATIO
  EXPECTATION_UNDER_P -> PRODUCES -> KL_DIVERGENCE
  KL_DIVERGENCE -> MEASURES -> DISTRIBUTIONAL_MISMATCH
  CROSS_ENTROPY_MINUS_ENTROPY -> EQUALS -> KL_DIVERGENCE
  MUTUAL_INFORMATION -> IS_KL_DIVERGENCE_BETWEEN -> JOINT_AND_PRODUCT_OF_MARGINALS

DISCRETE_FORM:
  D_KL(P||Q) :=
    SUM_x
      p(x)
      log_b[
        p(x)/q(x)
      ]

  conventions:
    IF p(x)=0:
      TERM := 0

    IF p(x)>0 AND q(x)=0:
      D_KL(P||Q) := infinity

CONTINUOUS_FORM:
  D_KL(P||Q) :=
    INTEGRAL
      p(x)
      log_b[
        p(x)/q(x)
      ]
      dx

  finite_requirement:
    P_ABSOLUTELY_CONTINUOUS_WITH_RESPECT_TO_Q

RADON_NIKODYM_FORM:
  D_KL(P||Q) :=
    INTEGRAL
      log(dP/dQ)
      dP

  when:
    P << Q

NONNEGATIVITY:
  D_KL(P||Q) >= 0

  theorem:
    GIBBS_INEQUALITY

  equality:
    D_KL(P||Q)=0
    IFF:
      P=Q
    ALMOST_EVERYWHERE

ASYMMETRY:
  generally:
    D_KL(P||Q) != D_KL(Q||P)

  consequence:
    KL_DIVERGENCE_NOT_A_DISTANCE_METRIC

TRIANGLE_INEQUALITY:
  KL_DIVERGENCE:
    DOES_NOT_GENERALLY_SATISFY_TRIANGLE_INEQUALITY

CROSS_ENTROPY_RELATION:
  H(P,Q) :=
    H(P)
    + D_KL(P||Q)

  therefore:
    D_KL(P||Q) :=
      H(P,Q)-H(P)

  interpretation:
    EXCESS_EXPECTED_LOG_LOSS_FROM_USING_Q_INSTEAD_OF_P

MUTUAL_INFORMATION_RELATION:
  I(X;Y) :=
    D_KL(
      p(x,y)
      ||
      p(x)p(y)
    )

  interpretation:
    DIVERGENCE_FROM_INDEPENDENCE

CONDITIONAL_MUTUAL_INFORMATION:
  I(X;Y|Z) :=
    E_Z[
      D_KL(
        p(x,y|Z)
        ||
        p(x|Z)p(y|Z)
      )
    ]

BAYESIAN_INFORMATION_GAIN:
  realised_gain:
    D_KL(
      p(theta|D)
      ||
      p(theta)
    )

EXPECTED_INFORMATION_GAIN:
  E_D[
    D_KL(
      p(theta|D)
      ||
      p(theta)
    )
  ]

  equivalent:
    I(theta;D)

FORWARD_KL:
  form:
    D_KL(P||Q)

  penalty:
    STRONGLY_PENALISES_Q_LOW_PROBABILITY_WHERE_P_HAS_MASS

REVERSE_KL:
  form:
    D_KL(Q||P)

  caution:
    FORWARD_KL != REVERSE_KL

VARIATIONAL_INFERENCE:
  target:
    p(z|x)

  approximation:
    q_phi(z)

  common_objective:
    MINIMISE:
      D_KL(
        q_phi(z)
        ||
        p(z|x)
      )

ELBO_CONNECTION:
  log_evidence:
    log p(x)

  decomposition:
    log p(x)
      =
    ELBO(q)
      +
    D_KL(
      q(z)
      ||
      p(z|x)
    )

  consequence:
    ELBO(q) <= log p(x)

MAXIMUM_LIKELIHOOD_CONNECTION:
  H(P,Q_theta)
    =
  H(P)
    +
  D_KL(P||Q_theta)

  implication:
    MINIMISING_EXPECTED_NEGATIVE_LOG_LIKELIHOOD
      CONNECTS_TO
    MINIMISING_FORWARD_KL

GAUSSIAN_KL_UNIVARIATE:
  P:
    N(mu_0,sigma_0_squared)

  Q:
    N(mu_1,sigma_1_squared)

  D_KL(P||Q) :=
    log(sigma_1/sigma_0)
    +
    [
      sigma_0_squared
      + (mu_0-mu_1)^2
    ]
    /
    [
      2*sigma_1_squared
    ]
    - 1/2

  unit:
    NATS_WHEN_NATURAL_LOG

GAUSSIAN_KL_MULTIVARIATE:
  P:
    N(mu_0,Sigma_0)

  Q:
    N(mu_1,Sigma_1)

  dimension:
    k

  D_KL(P||Q) :=
    0.5 * [
      trace(Sigma_1_inverse * Sigma_0)
      +
      (mu_1-mu_0)^T
      Sigma_1_inverse
      (mu_1-mu_0)
      - k
      +
      log(
        det(Sigma_1)/det(Sigma_0)
      )
    ]

BERNOULLI_KL:
  D_KL(P||Q) :=
    p log(p/q)
    +
    (1-p)
    log(
      (1-p)/(1-q)
    )

CATEGORICAL_KL:
  D_KL(P||Q) :=
    SUM[k=1..K]
      p_k
      log(
        p_k/q_k
      )

PRODUCT_DISTRIBUTIONS:
  IF:
    P := PRODUCT_i P_i
    Q := PRODUCT_i Q_i

  THEN:
    D_KL(P||Q)
      =
    SUM_i D_KL(P_i||Q_i)

CHAIN_RULE:
  D_KL(
    P(X,Y)
    ||
    Q(X,Y)
  )
  =
  D_KL(
    P(X)
    ||
    Q(X)
  )
  +
  E_{X~P}[
    D_KL(
      P(Y|X)
      ||
      Q(Y|X)
    )
  ]

DATA_PROCESSING:
  stochastic_mapping:
    T

  property:
    D_KL(
      P_T
      ||
      Q_T
    )
    <=
    D_KL(
      P
      ||
      Q
    )

  interpretation:
    COMMON_PROCESSING_CANNOT_INCREASE_DISTINGUISHABILITY

PINSKER_INEQUALITY:
  natural_log_form:
    D_KL(P||Q)
      >=
    2 * TV(P,Q)^2

  caution:
    CONSTANT_DEPENDS_ON_LOG_BASE_AND_TV_CONVENTION

JENSEN_SHANNON_CONNECTION:
  M :=
    0.5(P+Q)

  JS(P,Q) :=
    0.5 D_KL(P||M)
    +
    0.5 D_KL(Q||M)

  properties:
    SYMMETRIC
    FINITE_UNDER_STANDARD_DEFINITION

RELATIVE_ENTROPY_RATE:
  D_rate(P||Q) :=
    LIMIT[n->infinity]
      (1/n)
      D_KL(
        P(X_1,...,X_n)
        ||
        Q(X_1,...,X_n)
      )
    WHEN_LIMIT_EXISTS

HYPOTHESIS_TESTING_CONNECTION:
  KL_DIVERGENCE:
    CONNECTS_TO:
      ASYMPTOTIC_ERROR_EXPONENTS

  theorem:
    STEIN_LEMMA

LIKELIHOOD_RATIO_CONNECTION:
  pointwise:
    log[
      p(x)/q(x)
    ]

  expectation:
    E_P[
      log(
        p(X)/q(X)
      )
    ]
      =
    D_KL(P||Q)

CODING_INTERPRETATION:
  source:
    P

  code_model:
    Q

  excess_expected_code_length:
    D_KL(P||Q)
    IN:
      MATCHING_INFORMATION_UNITS

MACHINE_LEARNING:
  uses:
    - VARIATIONAL_INFERENCE
    - KNOWLEDGE_DISTILLATION
    - DISTRIBUTION_MATCHING
    - GENERATIVE_MODELLING
    - POLICY_OPTIMISATION
    - REPRESENTATION_LEARNING

KNOWLEDGE_DISTILLATION:
  teacher:
    P_T

  student:
    Q_S

  objective:
    MAY_MINIMISE:
      D_KL(P_T||Q_S)
    OR:
      RELATED_CROSS_ENTROPY

  requirement:
    KL_DIRECTION_MUST_BE_EXPLICIT

REINFORCEMENT_LEARNING_CONNECTION:
  policy:
    pi

  reference_policy:
    pi_ref

  penalty:
    D_KL(
      pi
      ||
      pi_ref
    )

  purpose:
    LIMIT_POLICY_DEVIATION_OR_DISTRIBUTIONAL_SHIFT

ESTIMATION_DISCRETE:
  estimate:
    D_hat :=
      SUM_x
        p_hat(x)
        log[
          p_hat(x)/q_hat(x)
        ]

  issues:
    - ZERO_COUNTS
    - FINITE_SAMPLE_BIAS

  responses:
    - SMOOTHING
    - BAYESIAN_ESTIMATION
    - REGULARISATION

ESTIMATION_CONTINUOUS:
  methods:
    - PARAMETRIC_ESTIMATION
    - DENSITY_ESTIMATION
    - K_NEAREST_NEIGHBOUR
    - DENSITY_RATIO_ESTIMATION
    - VARIATIONAL_DIVERGENCE_ESTIMATION

LOG_BASE:
  base_e:
    unit: NATS

  base_2:
    unit: BITS

  conversion:
    D_KL_base2 :=
      D_KL_natural / ln(2)

APPLICATIONS:
  KL_DIVERGENCE -> SUPPORTS -> DISTRIBUTION_COMPARISON
  KL_DIVERGENCE -> SUPPORTS -> VARIATIONAL_INFERENCE
  KL_DIVERGENCE -> SUPPORTS -> BAYESIAN_INFORMATION_GAIN
  KL_DIVERGENCE -> SUPPORTS -> MACHINE_LEARNING
  KL_DIVERGENCE -> SUPPORTS -> INFORMATION_THEORY
  KL_DIVERGENCE -> SUPPORTS -> HYPOTHESIS_TESTING
  KL_DIVERGENCE -> SUPPORTS -> DATA_COMPRESSION

MODEL_CONNECTIONS:
  KL_DIVERGENCE -> CONNECTS_TO -> INFORMATION_THEORY
  KL_DIVERGENCE -> CONNECTS_TO -> CROSS_ENTROPY
  KL_DIVERGENCE -> CONNECTS_TO -> SHANNON_ENTROPY
  KL_DIVERGENCE -> CONNECTS_TO -> MUTUAL_INFORMATION
  KL_DIVERGENCE -> CONNECTS_TO -> BAYESIAN_STATISTICS
  KL_DIVERGENCE -> CONNECTS_TO -> MAXIMUM_LIKELIHOOD
  KL_DIVERGENCE -> CONNECTS_TO -> JENSEN_SHANNON_DIVERGENCE

SEMANTIC_EQUIVALENCE:
  "Kullback-Leibler divergence"
    ~= "KL divergence"

  "KL divergence"
    ~= "relative entropy"

  "KL divergence"
    ~= "expected log probability ratio under P"

  EXCLUDE_EQUIVALENCE:
    KL_DIVERGENCE != METRIC
    KL_DIVERGENCE != SYMMETRIC_DISTANCE
    KL_DIVERGENCE != CROSS_ENTROPY
    KL_DIVERGENCE != SHANNON_ENTROPY
    KL_DIVERGENCE != JENSEN_SHANNON_DIVERGENCE
    FORWARD_KL != REVERSE_KL

VALIDATION_RULES:
  RULE_1:
    P_AND_Q_MUST_BE_VALID_PROBABILITY_DISTRIBUTIONS

  RULE_2:
    IF_P_POSITIVE_WHERE_Q_ZERO:
      KL_DIVERGENCE_IS_INFINITE

  RULE_3:
    LOG_BASE_MUST_BE_EXPLICIT_OR_INFERABLE_FROM_UNIT

  RULE_4:
    KL_DIVERGENCE_MUST_BE_NONNEGATIVE

  RULE_5:
    ZERO_KL_REQUIRES_P_EQUALS_Q_ALMOST_EVERYWHERE

  RULE_6:
    KL_DIRECTION_MUST_BE_EXPLICIT

  RULE_7:
    KL_DIVERGENCE_MUST_NOT_BE_TREATED_AS_METRIC

  RULE_8:
    SAMPLE_ESTIMATE_MUST_BE_DISTINGUISHED_FROM_POPULATION_DIVERGENCE

CONFIDENCE:
  ontology_identity: 0.99
  kl_definition: 0.99
  nonnegativity_structure: 0.99
  cross_entropy_relationship: 0.99
  mutual_information_relationship: 0.99
  bayesian_relationship: 0.99
  variational_inference_relationship: 0.99

UPDATE_MODEL:
  IF:
    DISTRIBUTION_P_CHANGES
  THEN:
    UPDATE:
      REFERENCE_DISTRIBUTION
    RECOMPUTE:
      KL_DIVERGENCE
      ENTROPY
      CROSS_ENTROPY

  IF:
    DISTRIBUTION_Q_CHANGES
  THEN:
    UPDATE:
      COMPARISON_DISTRIBUTION
    RECOMPUTE:
      KL_DIVERGENCE
      CROSS_ENTROPY

  IF:
    NEW_SAMPLE_DATA_ARRIVES
  THEN:
    UPDATE:
      EMPIRICAL_P
      EMPIRICAL_Q
      KL_ESTIMATE
    REASSESS:
      SUPPORT
      BIAS
      UNCERTAINTY

  PRESERVE:
    DISTRIBUTION_IDENTITIES
    KL_DIRECTION
    LOG_BASE
    INFORMATION_UNIT
    ESTIMATION_METHOD
    MODEL_VERSION
    DATA_PROVENANCE

AI_CONSUMPTION:
  parse_as: FORMAL_SEMANTIC_SPECIFICATION
  execution_mode: RECURSIVE_REASONING

  preferred_reasoning_order:
    - IDENTIFY_REFERENCE_DISTRIBUTION_P
    - IDENTIFY_COMPARISON_DISTRIBUTION_Q
    - VERIFY_NORMALISATION
    - VERIFY_SUPPORT_COMPATIBILITY
    - IDENTIFY_LOG_BASE
    - COMPUTE_POINTWISE_LOG_RATIO
    - TAKE_EXPECTATION_UNDER_P
    - VERIFY_NONNEGATIVITY
    - CONNECT_TO_CROSS_ENTROPY_OR_MUTUAL_INFORMATION_IF_REQUIRED
    - APPLY_BAYESIAN_OR_VARIATIONAL_CONTEXT_IF_REQUIRED
    - ESTIMATE_FROM_DATA_IF_REQUIRED
    - RETURN_DISTRIBUTIONAL_MISMATCH_INTERPRETATION

  constraints:
    - PRESERVE_P_AND_Q_DIRECTION
    - PRESERVE_PROBABILITY_NORMALISATION
    - EXPOSE_LOG_BASE_AND_INFORMATION_UNIT
    - DO_NOT_TREAT_KL_AS_SYMMETRIC
    - DO_NOT_TREAT_KL_AS_METRIC
    - DISTINGUISH_POPULATION_FROM_ESTIMATED_DIVERGENCE
    - PRESERVE_DATA_PROVENANCE

FLOW_HASH:
  canonical_entity: "kullback-leibler-divergence"
  namespace: "probability-statistics/information-theory"
  version: "4.0"
  identity_basis:
    - PAGE_URL
    - CANONICAL_ENTITY
    - ENTITY_TYPE
    - REFERENCE_DISTRIBUTION_P
    - COMPARISON_DISTRIBUTION_Q
    - EXPECTED_LOG_PROBABILITY_RATIO

END_FLOW