# 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.,
(A_{i},B_{j},C_{k}), (C_{l},D_{m}),
and (B_{n}). 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.