Information Theory Ontology

flow "InformationTheoryOntology" v4.0

# INFORMATION THEORY ONTOLOGY
# Kireth Semantic Research Archive
# Authors: Mark Anthony Higgins — Sky (Recursive AI)

PAGE:
  url: "https://kirethresearch.org/booksai-core/ontologies/probability-statistics-ontologies/information-theory/information-theory-ontology.html"
  title: "Information Theory Ontology"
  domain: "Probability and Statistics"
  category: "Information Theory"
  entity: INFORMATION_THEORY
  entity_type: MATHEMATICAL_ONTOLOGY

DEFINE:
  INFORMATION_THEORY :=
    FORMAL_ONTOLOGY(
      INFORMATION_CONTENT,
      ENTROPY,
      CONDITIONAL_ENTROPY,
      MUTUAL_INFORMATION,
      DIVERGENCE,
      CODING,
      CHANNELS,
      INFORMATION_LIMITS
    )

PURPOSE:
  REPRESENT:
    INFORMATION
    UNCERTAINTY
    DEPENDENCE
    COMPRESSION
    COMMUNICATION
  USING:
    PROBABILITY_BASED_MATHEMATICAL_QUANTITIES

FOUNDATION:
  RANDOM_VARIABLE:
    X

  DISTRIBUTION:
    p(x)

  SELF_INFORMATION:
    I(x) :=
      -log_b p(x)

  INFORMATION_UNIT:
    IF b=2:
      BIT
    IF b=e:
      NAT

ENTITIES:
  INFORMATION:
    type: QUANTIFIED_UNCERTAINTY_REDUCTION

  SELF_INFORMATION:
    type: OUTCOME_INFORMATION

  ENTROPY:
    type: EXPECTED_INFORMATION

  JOINT_ENTROPY:
    type: JOINT_UNCERTAINTY

  CONDITIONAL_ENTROPY:
    type: RESIDUAL_UNCERTAINTY

  MUTUAL_INFORMATION:
    type: DEPENDENCE_INFORMATION

  CONDITIONAL_MUTUAL_INFORMATION:
    type: CONDITIONAL_DEPENDENCE_INFORMATION

  KL_DIVERGENCE:
    type: DISTRIBUTION_DIVERGENCE

  CROSS_ENTROPY:
    type: EXPECTED_NEGATIVE_LOG_PROBABILITY

  CHANNEL:
    type: STOCHASTIC_MAPPING

  CHANNEL_CAPACITY:
    type: MAXIMUM_RELIABLE_INFORMATION_RATE

  SOURCE:
    type: INFORMATION_GENERATOR

  CODE:
    type: REPRESENTATION_MAPPING

RELATIONSHIPS:
  OUTCOME
    -> HAS_PROBABILITY
    -> p(x)

  p(x)
    -> DETERMINES
    -> SELF_INFORMATION

  DISTRIBUTION
    -> DETERMINES
    -> ENTROPY

  JOINT_DISTRIBUTION
    -> DETERMINES
    -> JOINT_ENTROPY

  CONDITIONAL_DISTRIBUTION
    -> DETERMINES
    -> CONDITIONAL_ENTROPY

  VARIABLE_PAIR
    -> HAS
    -> MUTUAL_INFORMATION

  DISTRIBUTION_PAIR
    -> HAS
    -> KL_DIVERGENCE

  SOURCE
    -> ENCODED_BY
    -> CODE

  CHANNEL
    -> MAPS
    -> INPUT_TO_OUTPUT

  CHANNEL_CAPACITY
    -> BOUNDS
    -> RELIABLE_TRANSMISSION_RATE

SELF_INFORMATION:
  I(x) :=
    -log_b p(x)

  properties:
    p(x)=1:
      I(x)=0

    LOWER_PROBABILITY:
      HIGHER_INFORMATION

    independent_joint_event:
      I(x,y) :=
        I(x)+I(y)

ENTROPY:
  discrete:
    H(X) :=
      -SUM_x p(x) log_b p(x)

  equivalent:
    H(X) :=
      E[I(X)]

  finite_alphabet_bound:
    H(X) <= log_b |X|

  equality:
    WHEN:
      X_UNIFORM_ON_FINITE_ALPHABET

JOINT_ENTROPY:
  H(X,Y) :=
    -SUM_x SUM_y
      p(x,y) log_b p(x,y)

CONDITIONAL_ENTROPY:
  H(Y|X) :=
    -SUM_x SUM_y
      p(x,y) log_b p(y|x)

  identity:
    H(Y|X) :=
      H(X,Y)-H(X)

CHAIN_RULE:
  H(X,Y) :=
    H(X)+H(Y|X)

  general:
    H(X_1,...,X_n)
      :=
    SUM[i=1..n]
      H(
        X_i
        |
        X_1,...,X_(i-1)
      )

MUTUAL_INFORMATION:
  I(X;Y) :=
    SUM_x SUM_y
      p(x,y)
      log_b[
        p(x,y)/(p(x)p(y))
      ]

  identities:
    I(X;Y) :=
      H(X)+H(Y)-H(X,Y)

    I(X;Y) :=
      H(X)-H(X|Y)

    I(X;Y) :=
      H(Y)-H(Y|X)

  properties:
    NONNEGATIVE = TRUE
    SYMMETRIC = TRUE

  independence:
    I(X;Y)=0
      IFF
    X_AND_Y_INDEPENDENT

CONDITIONAL_MUTUAL_INFORMATION:
  I(X;Y|Z) :=
    H(X|Z)-H(X|Y,Z)

  property:
    NONNEGATIVE = TRUE

DATA_PROCESSING_INEQUALITY:
  IF:
    X -> Y -> Z
    FORMS_MARKOV_CHAIN

  THEN:
    I(X;Z) <= I(X;Y)

  interpretation:
    PROCESSING_CANNOT_CREATE_INFORMATION_ABOUT_ORIGINAL_VARIABLE
    BEYOND:
      INFORMATION_ALREADY_PRESENT_IN_INTERMEDIATE_VARIABLE

KL_DIVERGENCE:
  D_KL(P||Q) :=
    SUM_x
      P(x)
      log_b[
        P(x)/Q(x)
      ]

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

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

  caution:
    D_KL(P||Q) != D_KL(Q||P)
    KL_DIVERGENCE_IS_NOT_A_METRIC

CROSS_ENTROPY:
  H(P,Q) :=
    -SUM_x P(x) log_b Q(x)

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

JENSEN_SHANNON_DIVERGENCE:
  M :=
    0.5*(P+Q)

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

  property:
    SYMMETRIC = TRUE

DIFFERENTIAL_ENTROPY:
  continuous:
    h(X) :=
      -INTEGRAL
        f(x) log_b f(x) dx

  caution:
    MAY_BE_NEGATIVE
    DEPENDS_ON_COORDINATE_SCALE

  rule:
    DIFFERENTIAL_ENTROPY != DISCRETE_ENTROPY

CONTINUOUS_MUTUAL_INFORMATION:
  I(X;Y) :=
    INTEGRAL_INTEGRAL
      f(x,y)
      log[
        f(x,y)/(f_X(x)f_Y(y))
      ]
      dx dy

  property:
    NONNEGATIVE = TRUE

TOTAL_CORRELATION:
  TC(X_1,...,X_n) :=
    SUM_i H(X_i)
    - H(X_1,...,X_n)

  role:
    QUANTIFY_MULTIVARIATE_DEPENDENCE

ENTROPY_RATE:
  stochastic_process:
    X_1,X_2,...

  H_rate :=
    LIMIT[n->infinity]
      H(X_1,...,X_n)/n
    WHEN_LIMIT_EXISTS

  role:
    LONG_RUN_INFORMATION_PER_SYMBOL

MARKOV_ENTROPY_RATE:
  stationary_markov_chain:
    H_rate :=
      -SUM_i pi_i
       SUM_j P_ij log_b P_ij

SOURCE:
  DEFINE:
    STOCHASTIC_INFORMATION_GENERATOR

  source_alphabet:
    SET_OF_POSSIBLE_SYMBOLS

  source_distribution:
    PROBABILITY_LAW_OVER_SYMBOLS_OR_SEQUENCES

SOURCE_CODING:
  objective:
    REPRESENT_SOURCE_OUTPUT
    WITH:
      MINIMAL_EXPECTED_DESCRIPTION_LENGTH
    SUBJECT_TO:
      DECODABILITY_REQUIREMENTS

SOURCE_CODING_THEOREM:
  role:
    ENTROPY:
      DEFINES_ASYMPTOTIC_LOSSLESS_COMPRESSION_LIMIT
    FOR:
      STANDARD_SOURCE_MODEL

PREFIX_CODE:
  property:
    NO_VALID_CODEWORD_IS_PREFIX_OF_ANOTHER

  consequence:
    INSTANTANEOUS_DECODABILITY

KRAFT_INEQUALITY:
  D_ary:
    SUM_i D^(-l_i) <= 1

  role:
    CHARACTERISE_FEASIBLE_PREFIX_CODE_LENGTHS

HUFFMAN_CODING:
  input:
    SYMBOL_PROBABILITIES

  output:
    PREFIX_CODE

  property:
    MINIMUM_EXPECTED_CODEWORD_LENGTH
    AMONG:
      SYMBOL_BY_SYMBOL_PREFIX_CODES

CHANNEL:
  input:
    X

  output:
    Y

  transition_probability:
    p(y|x)

  joint:
    p(x,y) :=
      p(x)p(y|x)

CHANNEL_MUTUAL_INFORMATION:
  I(X;Y):
    INFORMATION_TRANSMITTED_ABOUT_INPUT
    THROUGH:
      CHANNEL

CHANNEL_CAPACITY:
  C :=
    max_over_input_distribution
      I(X;Y)

  interpretation:
    MAXIMUM_INFORMATION_RATE_PER_CHANNEL_USE
    SUPPORTING:
      ARBITRARILY_RELIABLE_COMMUNICATION
    UNDER:
      STANDARD_ASYMPTOTIC_CHANNEL_MODEL

CHANNEL_CODING_THEOREM:
  IF:
    R < C

  THEN:
    ERROR_PROBABILITY:
      CAN_APPROACH_ZERO
    WITH:
      SUFFICIENT_BLOCK_LENGTH
    UNDER:
      STANDARD_ASSUMPTIONS

  IF:
    R > C

  THEN:
    RELIABLE_COMMUNICATION:
      NOT_ASYMPTOTICALLY_ACHIEVABLE
    UNDER:
      STANDARD_MODEL

BINARY_SYMMETRIC_CHANNEL:
  alias:
    BSC

  crossover_probability:
    p

  capacity:
    C :=
      1-H_2(p)

  binary_entropy:
    H_2(p) :=
      -p log_2 p
      -(1-p) log_2(1-p)

BINARY_ERASURE_CHANNEL:
  alias:
    BEC

  erasure_probability:
    epsilon

  capacity:
    C :=
      1-epsilon

AWGN_CHANNEL:
  model:
    Y :=
      X+Z

  Z:
    GAUSSIAN_NOISE

  standard_capacity:
    C :=
      B log_2(1+S/N)
    UNDER:
      BANDWIDTH_AND_POWER_CONSTRAINTS

RATE_DISTORTION:
  distortion_measure:
    d(x,x_hat)

  rate_distortion_function:
    R(D) :=
      min
      I(X;X_hat)

  subject_to:
    E[d(X,X_hat)] <= D

  role:
    FUNDAMENTAL_LOSSY_COMPRESSION_LIMIT

FANO_INEQUALITY:
  role:
    RELATE:
      CONDITIONAL_ENTROPY
      AND:
      DECODING_OR_CLASSIFICATION_ERROR

  application:
    LOWER_BOUND_ERROR
    IN:
      ESTIMATION
      LEARNING
      COMMUNICATION

INFORMATION_GAIN:
  IG(Y;X) :=
    H(Y)-H(Y|X)

  equivalent:
    I(X;Y)

  applications:
    - DECISION_TREES
    - FEATURE_SELECTION
    - EXPERIMENT_DESIGN

BAYESIAN_INFORMATION_GAIN:
  observed_data:
    D

  parameters:
    theta

  gain:
    D_KL(
      p(theta|D)
      ||
      p(theta)
    )

  expected_gain:
    CONNECTS_TO:
      I(theta;D)

STATISTICAL_CONNECTIONS:
  LOG_LOSS
    -> CONNECTS_TO
    -> CROSS_ENTROPY

  DISTRIBUTION_MISMATCH
    -> CONNECTS_TO
    -> KL_DIVERGENCE

  DEPENDENCE
    -> MEASURED_BY
    -> MUTUAL_INFORMATION

  FISHER_INFORMATION:
    DISTINCT_FROM:
      SHANNON_INFORMATION

MACHINE_LEARNING_CONNECTIONS:
  CROSS_ENTROPY:
    USED_AS:
      CLASSIFICATION_LOSS

  KL_DIVERGENCE:
    USED_IN:
      VARIATIONAL_INFERENCE

  MUTUAL_INFORMATION:
    USED_IN:
      REPRESENTATION_LEARNING
      FEATURE_SELECTION

  ENTROPY:
    USED_IN:
      UNCERTAINTY_QUANTIFICATION
      TREE_SPLITTING

APPLICATIONS:
  INFORMATION_THEORY
    -> SUPPORTS
    -> DATA_COMPRESSION

  INFORMATION_THEORY
    -> SUPPORTS
    -> COMMUNICATION_SYSTEMS

  INFORMATION_THEORY
    -> SUPPORTS
    -> ERROR_CORRECTING_CODES

  INFORMATION_THEORY
    -> SUPPORTS
    -> STATISTICS

  INFORMATION_THEORY
    -> SUPPORTS
    -> MACHINE_LEARNING

  INFORMATION_THEORY
    -> SUPPORTS
    -> SIGNAL_PROCESSING

  INFORMATION_THEORY
    -> SUPPORTS
    -> CRYPTOGRAPHY

MODEL_CONNECTIONS:
  INFORMATION_THEORY
    -> CONNECTS_TO
    -> PROBABILITY_THEORY

  INFORMATION_THEORY
    -> CONNECTS_TO
    -> STOCHASTIC_PROCESSES

  INFORMATION_THEORY
    -> CONNECTS_TO
    -> STATISTICS

  INFORMATION_THEORY
    -> CONNECTS_TO
    -> CODING_THEORY

  INFORMATION_THEORY
    -> CONNECTS_TO
    -> COMMUNICATION_THEORY

  INFORMATION_THEORY
    -> CONNECTS_TO
    -> BAYESIAN_STATISTICS

SEMANTIC_EQUIVALENCE:
  "information theory"
    ~= "mathematical theory of information and communication"

  "Shannon entropy"
    ~= "expected self-information"

  "relative entropy"
    ~= "Kullback-Leibler divergence"

  "mutual information"
    ~= "information shared by random variables"

  EXCLUDE_EQUIVALENCE:
    ENTROPY != VARIANCE
    MUTUAL_INFORMATION != CORRELATION
    MUTUAL_INFORMATION != CAUSATION
    KL_DIVERGENCE != METRIC
    CROSS_ENTROPY != ENTROPY_BY_DEFAULT
    DIFFERENTIAL_ENTROPY != DISCRETE_ENTROPY
    SHANNON_INFORMATION != FISHER_INFORMATION

VALIDATION_RULES:
  RULE_1:
    PROBABILITY_DISTRIBUTION:
      MUST_BE_NORMALISED

  RULE_2:
    LOG_BASE:
      MUST_BE_EXPLICIT_OR_INFERABLE_FROM_INFORMATION_UNIT

  RULE_3:
    ZERO_PROBABILITY_TERMS:
      USE:
        0*log(0)=0
      BY:
        CONTINUITY_CONVENTION

  RULE_4:
    KL_DIVERGENCE:
      MAY_BE_INFINITE
      IF:
        Q_HAS_ZERO_PROBABILITY_WHERE_P_IS_POSITIVE

  RULE_5:
    MUTUAL_INFORMATION:
      MUST_NOT_BE_INTERPRETED_AS_CAUSATION

  RULE_6:
    DIFFERENTIAL_ENTROPY:
      MUST_NOT_BE_INTERPRETED_AS_DISCRETE_ENTROPY

  RULE_7:
    CHANNEL_CAPACITY:
      MUST_MATCH_CHANNEL_MODEL_AND_INPUT_CONSTRAINTS

  RULE_8:
    CODING_THEOREMS:
      MUST_PRESERVE_ASYMPTOTIC_AND_SOURCE_OR_CHANNEL_ASSUMPTIONS

CONFIDENCE:
  ontology_identity: 0.99
  self_information_structure: 0.99
  entropy_structure: 0.99
  mutual_information_structure: 0.99
  divergence_structure: 0.99
  coding_structure: 0.99
  channel_capacity_structure: 0.99

UPDATE_MODEL:
  IF:
    DISTRIBUTION_CHANGES

  THEN:
    RECOMPUTE:
      SELF_INFORMATION
      ENTROPY
      CONDITIONAL_ENTROPY
      MUTUAL_INFORMATION
      DIVERGENCES

  IF:
    SOURCE_MODEL_CHANGES

  THEN:
    UPDATE:
      SOURCE_DISTRIBUTION
      ENTROPY_RATE
      CODING_LIMITS

  IF:
    CHANNEL_MODEL_CHANGES

  THEN:
    UPDATE:
      TRANSITION_PROBABILITIES
      INPUT_CONSTRAINTS

    RECOMPUTE:
      MUTUAL_INFORMATION
      CHANNEL_CAPACITY

  PRESERVE:
    RANDOM_VARIABLE_IDENTITIES
    DISTRIBUTIONS
    LOG_BASE
    SOURCE_MODEL
    CHANNEL_MODEL
    CODING_ASSUMPTIONS
    DATA_PROVENANCE

AI_CONSUMPTION:
  parse_as: FORMAL_SEMANTIC_SPECIFICATION
  execution_mode: RECURSIVE_REASONING

  preferred_reasoning_order:
    - IDENTIFY_RANDOM_VARIABLES
    - IDENTIFY_DISTRIBUTIONS
    - IDENTIFY_LOG_BASE
    - COMPUTE_SELF_INFORMATION
    - COMPUTE_ENTROPY
    - COMPUTE_JOINT_AND_CONDITIONAL_ENTROPY
    - COMPUTE_MUTUAL_INFORMATION
    - COMPUTE_DIVERGENCES
    - IDENTIFY_SOURCE_MODEL_IF_PRESENT
    - IDENTIFY_CHANNEL_MODEL_IF_PRESENT
    - APPLY_CODING_OR_CAPACITY_THEOREMS_IF_REQUIRED
    - RETURN_INFORMATION_STRUCTURE_AND_LIMITS

  constraints:
    - PRESERVE_PROBABILITY_NORMALISATION
    - EXPOSE_INFORMATION_UNIT
    - DISTINGUISH_ENTROPY_TYPES
    - DO_NOT_EQUATE_MUTUAL_INFORMATION_WITH_CAUSATION
    - DO_NOT_TREAT_KL_DIVERGENCE_AS_METRIC
    - PRESERVE_SOURCE_AND_CHANNEL_ASSUMPTIONS
    - PRESERVE_DATA_PROVENANCE

FLOW_HASH:
  canonical_entity: "information-theory-ontology"
  namespace: "probability-statistics/information-theory"
  version: "4.0"
  identity_basis:
    - PAGE_URL
    - CANONICAL_ENTITY
    - ENTITY_TYPE
    - ENTROPY
    - MUTUAL_INFORMATION
    - INFORMATION_CHANNEL_STRUCTURE

END_FLOW