Complexity Reduction in State-Based Modeling

Martin Zwick

Presented at the International Conference on Complex Systems
Nashua, NH, Oct. 25-30, 1998
Session on Dynamics and Complexity of Physical Systems

Abstract

For a system described by a relation among qualitative variables (or quantitative variables "binned" into symbolic states), expressed either set-theoretically or as a multivariate joint probability distribution, complexity reduction (compression of representation) is normally achieved by modeling the system with projections of the overall relation. To illustrate, if ABCD is a four variable relation, then models ABC:BCD or AB:BC:CD:DA, specified by two triadic or four dyadic relations, respectively, represent simplifications of the ABCD relation. Simplifications which are lossless are always preferred over the original full relation, while simplifications which lose constraint are still preferred if the reduction of complexity more than compensates for the loss of accuracy.

State-based modeling is an approach introduced by Bush Jones, which significantly enhances the compression power of information-theoretic (probabilistic) models, at the price of significantly expanding the set of models which might be considered. Relation ABCD is modeled not in terms of the projected relations which exist between subsets of the variables but rather in terms of a set of specific states of subsets of the variables, e.g., (Ai,Bj,Ck), (Cl,Dm), and (Bn). One might regard such state-based, as opposed to variable-based, models as utilizing an "event"- or "fact"-oriented representation. In the complex systems community, even variable-based decomposition methods are not widely utilized, but these state-based methods are still less widely known. This talk will compare state- and variable-based modeling, and will discuss open questions and research areas posed by this approach.