Variable-Structure Systems from Graphs and Grammars
Eric Mjolsness, Uci Ics Tr · 2005
Variable-structure systems are those for which the available objects and their relationships can enter or leave the problem as a function of time or depending on the values of other variables. We seek to define probabilis-tic generative models for variable-structure systems in sufficient generality for use in complex scientific and pattern recognition applications. We define a semantic map, Y, by which model specifications map to model semantics for variable-structure systems. The specification takes the form of (a) a labelled graph or “dependency diagram ” (some of whose nodes are labelled with random variables), or (b) a context-sensive stochastic parameter-ized grammar (SPG), a particular kind of “dynamical grammar”. The semantics takes the form of a joint probabil-ity density function (pdf), in the case of a graph, or an infinite-dimensional time evolution operator on joint probability density functions for a dynamical grammar. We illustrate these frameworks by treating, with depen-dency diagrams and dynamical grammars, an elementary example: context-free but resource-bounded trees of conditionally dependent feature vectors. This model can serve as a scaffold for many other variable-structure systems. Fixed-structure Dependency Diagram (DD) classes include graphical models such as Markov Random Fields, Bayes Nets, and Factor Graphs, as well as Constraint Networks. By adding new kinds of node and link