Pattern Discovery and Computational Mechanics

Cosma Rohilla Shalizi and James P. Crutchfield
Santa Fe Institute
1399 Hyde Park Rd.
Santa Fe, NM 87501, USA

Abstract

Computational mechanics is a method for discovering, describing and quantifying patterns, using tools from statistical physics. It constructs optimal, minimal models of stochastic processes and their underlying causal structures. These models tell us about the intrinsic computation embedded within a process---how it stores and transforms information. Here we summarize the mathematics of computational mechanics, especially recent optimality and uniqueness results. We also expound the principles and motivations underlying computational mechanics, emphasizing its connections to the minimum description length principle, PAC theory, and other aspects of machine learning.

Citation

C. R. Shalizi and J. P. Crutchfield Pattern Discovery and Computational Mechanics, Santa Fe Insitute Working Paper 00-01-008 and arXiv.org/abs/cs.LG/0001027.

To transfer a compressed PostScript version of the paper
click on its title or use one of the links below.