The entropy rate of Linear Additive Markov Processes

Area of Science:

• Information Theory
• Statistical Modeling
• Machine Learning

Background:

• Complex data often exhibits long-range dependencies.
• Higher-order Markov processes can model these dependencies but have large parameter spaces.
• A simpler model with theoretical tractability is needed.

Purpose of the Study:

• To derive the theoretical entropy of a Linear Additive Markov Process (LAMP).
• To compare the expressibility and parameter efficiency of LAMP models against higher-order Markov processes.
• To apply the LAMP model for entropy rate estimation on real-world datasets.

Main Methods:

• Theoretical derivation of entropy for LAMP models.
• Comparison of LAMP model entropy with first-order Markov chains.
• Application of LAMP for entropy estimation on LastFM, BrightKite, Wikispeedia, and Reuters-21578 datasets.

Main Results:

• The theoretical entropy rate of a LAMP model is equivalent to its underlying first-order Markov Chain.
• LAMP models capture complex relationships with fewer parameters than higher-order models.
• LAMP model entropy estimates were generally lower than alternatives, indicating better accommodation of structural dependencies.

Conclusions:

• LAMP models offer a computationally efficient and theoretically sound approach for modeling complex sequential data.
• The equivalence of LAMP and first-order Markov chain entropy simplifies analysis.
• LAMP provides more accurate entropy rate estimates for datasets with structural dependencies.