Causal architecture, complexity and self-organization in time series and cellular automata Export

@phdthesis{citeulike:1028937, abstract = {All self-respecting nonlinear scientists know self- organization when they see it: except when we disagree. For this reason, if no other, it is important to put some mathematical spine into our floppy intuitive notion of self-organization. Only a few measures of self- organization have been proposed; none can be adopted in good intellectual conscience. To find a decent formalization of self-organization, we need to pin down what we mean by organization. The best answer is that the organization of a process is its causal architecture-its internal, possibly hidden, causal states and their interconnections. Computational mechanics is a method for inferring causal architecture-represented by a mathematical object called the \ε-machine-from observed behavior. The \ε-machine captures all patterns in the process which have any predictive power, so computational mechanics is also a method for pattern discovery. In this work, I develop computational mechanics for four increasingly sophisticated types of process-memoryless transducers, time series, transducers with memory, and cellular automata. In each case I prove the optimality and uniqueness of the \ε-machine's representation of the causal architecture, and give reliable algorithms for pattern discovery. The \ε-machine is the organization of the process, or at least of the part of it which is relevant to our measurements. It leads to a natural measure of the statistical complexity of processes, namely the amount of information needed to specify the state of the E-machine. Self-organization is a self- generated increase in statistical complexity. This fulfills various hunches which have been advanced in the literature, seems to accord with people's intuitions, and is both mathematically precise and operational.}, author = {Shalizi, C. R.}, citeulike-article-id = {1028937}, citeulike-linkout-0 = {http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=2001PhDT........28S}, keywords = {algebraic, algorithmic-information-theory, automata, causal-networks, causal-state-machine, cellular-automaton, computation, computational-epistemology, computational-mechanics, discreteness, domain-theory, entropy, information-system, minimal-sufficient-statistic, physical-structures, self-organization, space-time, symbolic-dynamics, temporal-concept-analysis}, posted-at = {2007-08-03 02:03:49}, priority = {0}, school = {THE UNIVERSITY OF WISCONSIN - MADISON}, title = {Causal architecture, complexity and self-organization in time series and cellular automata}, url = {http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=2001PhDT........28S}, year = {2001} }

TY - THES ID - citeulike:1028937 L3 - citeulike-article-id:1028937 N2 - All self-respecting nonlinear scientists know self- organization when they see it: except when we disagree. For this reason, if no other, it is important to put some mathematical spine into our floppy intuitive notion of self-organization. Only a few measures of self- organization have been proposed; none can be adopted in good intellectual conscience. To find a decent formalization of self-organization, we need to pin down what we mean by organization. The best answer is that the organization of a process is its causal architecture-its internal, possibly hidden, causal states and their interconnections. Computational mechanics is a method for inferring causal architecture-represented by a mathematical object called the ε-machine-from observed behavior. The ε-machine captures all patterns in the process which have any predictive power, so computational mechanics is also a method for pattern discovery. In this work, I develop computational mechanics for four increasingly sophisticated types of process-memoryless transducers, time series, transducers with memory, and cellular automata. In each case I prove the optimality and uniqueness of the ε-machine's representation of the causal architecture, and give reliable algorithms for pattern discovery. The ε-machine is the organization of the process, or at least of the part of it which is relevant to our measurements. It leads to a natural measure of the statistical complexity of processes, namely the amount of information needed to specify the state of the E-machine. Self-organization is a self- generated increase in statistical complexity. This fulfills various hunches which have been advanced in the literature, seems to accord with people's intuitions, and is both mathematically precise and operational. TI - Causal architecture, complexity and self-organization in time series and cellular automata PB - THE UNIVERSITY OF WISCONSIN - MADISON KW - algebraic KW - algorithmic-information-theory KW - automata KW - causal-networks KW - causal-state-machine KW - cellular-automaton KW - computation KW - computational-epistemology KW - computational-mechanics KW - discreteness KW - domain-theory KW - entropy KW - information-system KW - minimal-sufficient-statistic KW - physical-structures KW - self-organization KW - space-time KW - symbolic-dynamics KW - temporal-concept-analysis AU - Shalizi, CR PY - 2001/// UR - http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=2001PhDT........28S ER -