The Entropy of Recursive Markov Processes

Benny BroddaCOLING 1967

TL;DR

This paper introduces a novel framework for calculating the entropy of "recursive Markov processes," which are essentially Markov models augmented with self-embedding capabilities, akin to recursive structures in formal grammars. By developing a method to quantify the information content of these complex, nested systems, the authors provide a mathematical tool to better understand the structure and information flow in systems that exhibit recursive properties, like natural language.

What Problem Does This Paper Address?

Understanding the information content, or entropy, of a source is fundamental in information theory. Traditional Markov models, while powerful, struggle to capture the inherent recursive nature of many real-world phenomena, particularly language. Natural language is characterized by nested structures (e.g., clauses within clauses, phrases within phrases), which are not easily represented by simple, non-recursive Markov chains. The authors aim to bridge this gap by defining and analyzing "Recursive Markov Processes" (RMPs) – Markov processes that can embed themselves within their own transitions. This allows for a more accurate modeling of systems with self-referential or nested structures, moving beyond the limitations of standard Markov grammars.

Methods

The paper builds upon the concept of Markov grammars, defining them as Markov sources with specific properties (initial, final, and intermediate states, transition probabilities, and associated letter production). The core innovation lies in defining how to calculate the entropy of embedded and recursive grammars.

  1. Embedded Grammars: The authors introduce a method to calculate the entropy of a composite grammar formed by embedding one Markov grammar (M₁) within another (M). This involves identifying states of M₁ with states of M, and a formula (Equation 4) is derived to compute the entropy of the combined grammar (M') based on the entropies and mean sentence lengths of the individual grammars.
  2. Recursive Grammars: This extends the embedding concept to allow grammars to contain themselves or other grammars that, in turn, contain them. The paper proposes a theorem (Equation 6) that relates the entropy of a set of recursive Markov grammars to the entropies of their non-recursive counterparts and their mean sentence lengths.
  3. Expected Time Calculation: A crucial lemma is presented to calculate the expected time (or "length") to produce a sentence in a Markov grammar where transitions have associated time costs. This lemma, expressed as a system of linear equations (Equation 7), is instrumental in computing the mean sentence lengths required for the entropy calculations of embedded and recursive grammars.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and mathematical formulation rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging Formal Grammars and Information Theory: The paper elegantly connects the formal linguistic concept of phrase structure grammars (and their recursive nature) with the quantitative framework of information theory via Markov processes.
  • Quantifying Recursion: The development of formulas for embedded and recursive grammars provides a concrete mathematical way to measure the information content of systems that exhibit self-embedding.
  • Mean Sentence Length as a Key Factor: The mean sentence length of a sub-grammar emerges as a critical weighting factor in the entropy calculation of composite grammars, reflecting the "waiting time" or effort associated with traversing nested structures.
  • Generalizability of Markov Models: The work demonstrates how to extend the applicability of Markov models to more complex, hierarchical structures by treating them as building blocks for larger, recursive systems.

Key Results

The paper's primary results are the derived formulas for calculating the entropy of:

  • Embedded Markov Grammars (Equation 4): $H(M') = H(M) + x_i p_{ik} \frac{H(M_1)}{1 + x_i p_{ik} (\mu_1 - 1)}$
  • Recursive Markov Grammars (Equation 6): $H_j' = H_j' (1 + \sum_k y_{jk} (\mu_k - 1)) - \sum_k y_{jk} H_k'$
  • Expected Sentence Length (Equation 7): A system of linear equations to compute expected transition times, which are then used as mean sentence lengths.

These formulas provide a theoretical framework for quantifying the information content of systems with recursive structures.

Limitations and Future Work

  • Theoretical Focus: The paper is largely theoretical, focusing on the mathematical formulation of entropy for RMPs. Empirical validation on real-world data (like natural language corpora) is not presented.
  • Computational Complexity: While formulas are provided, the practical computation of these entropies for very large or deeply nested grammars might be computationally intensive.
  • Interpretation of "Time": The lemma uses "time" for transitions, which is then equated to "sentence length." While a useful analogy, a deeper exploration of the physical or computational interpretation of this "time" in different contexts might be beneficial.

The authors suggest that the formulas can be extended to cases with multiple embedded sub-grammars. Future work could involve applying these theoretical results to analyze the entropy of actual natural language structures, compare different recursive grammar formalisms, or explore the computational efficiency of these entropy calculations.

Summary updated

BibTeX
@inproceedings{brodda1967entropy,
  author = {Benny Brodda},
  title = {{The Entropy of Recursive Markov Processes}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1967},
}

Loading related content...

Figure