Random composition trees show language like entropy patterns
Information Theory of Random Composition Trees
Information TheoryComputation and Language
Summary
Understanding how texts are built can be like understanding how people break down stories into parts. The authors studied random composition trees, which model this breakdown by splitting text into smaller meaningful chunks. They found that these trees share information patterns similar to real language, like how uncertainty grows as texts get bigger. This helps show that the way language is structured can be captured using simple statistical models.
What this means in practice
- •For natural language processing engineers: Design better models for hierarchical text segmentation by using the entropy rate insights of random composition trees.
- •For data compression developers: Improve compression algorithms by leveraging the confirmed linear entropy growth and typicality in text structures modeled by random composition trees.
A theory result. No direct application yet.
Authors
Doron Sivan, Weishun Zhong, Tankut Can, Mikhail Katkov, Misha Tsodyks
Abstract
Random composition trees model the hierarchical semantic structures of meaningful texts as a statistical ensemble generated by recursively splitting texts into coherent chunks. A recent study shows that different text types can be described by random composition trees with distinct branching factors, and that the entropy rates of these trees exhibit a similar dependence across text types as the entropy rates of the actual texts. Motivated by this correspondence, we analyze information-theoretic properties of this stochastic splitting model. First, we demonstrate that the entropy of random composition trees grows linearly with the root size, and we derive an analytical expression for the entropy rate as a function of the branching factor. Second, we prove that large trees exhibit typicality: with high probability, they belong to a typical set in which each tree is approximately equally likely. Our analysis reveals that the random composition tree model shares two key information-theoretic properties of language when modeled as a stationary and ergodic stochastic process: linear entropy growth and typicality.