Transcript Elementary Processes - A New Kind of Science

UCI ICS IGB SISL
Towards a Searchable Space of
Dynamical System Models
Eric Mjolsness
Scientific Inference Systems Laboratory (SISL)
University of California, Irvine
www.ics.uci.edu/~emj
In collaboration with: Guy Yosiphon
NKS June 2006
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Motivations shared with NKS
• Objective exploration of properties of
“simple” computational systems
• Relation of such to the sciences
• Example: bit string lexical ordering of
cellular automata rules; reducibility
relationships; applications to fluid flow
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Criteria for a space of simple
formal systems
• C1: Demonstrated expressive power in scientific
modeling
• C2: Representation as discrete labeled graph
structure
– that can be searched and explored computationally
– E.g. Bayes nets, Markov Random Fields
• roughly in order of increasing size - with index nodes (DD’s)
• C3: Self-applicability
– useful transformations and searches of such dynamical
systems should be expressible
• … as discrete-time dynamical systems that compute
• So major changes of representation during learning are not
NKS Washington DC 06/15/06
excluded.
UCI ICS IGB SISL
C1: Demonstration of expressive
power in scientific modeling
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Elementary Processes
• A(x)  B(y) + C(z) with rf (x, y, z)
• B(y) + C(z)  A(x) with rr (y, z, x)
• Examples
– Chemical reaction networks w/o params
– .
– XXX from paper
• Effective conservation laws
– E.g. ∫ NA(x) dx + ∫ NB(y) dy ,
∫ NA(x) dx + ∫ NC(z) dz
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Amino Acid Syntheses
tRNA-Ala
Leu
tRNA-Leu
Val
Ile
tRNA-Val
Ala
Glucose
TCA cycle
Glycolysis
Pyr
Asp
aKB
Thr
Lys Met
tRNA-Ile
+
tRNA-Thr
Kmech: Yang, et al. Bioinformatics 21: 774-780, 2005
Amino acid synthesis: Yang et al., J. Biological Chemistry, 280(12):11224-32, , Mar 25 2005.
Washington DC
GMWC modeling: Najdi et al., J. NKS
Bioinformatics
and06/15/06
Comp. Biol., to appear 2006.
UCI ICS IGB SISL
Example: Anabaena
Prusinkiewicz et al. model
G. Yosiphon,
SISL, UCI
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Example: Galaxy Morphology
G. Yosiphon, SISL, UCI
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Example: Arabidopsis
Shoot Apical Meristem (SAM)
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Quantification of growth
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
NKSraw
Washington
DC 06/15/06
Co-visualization of
and
extracted nuclei data
UCI ICS IGB SISL
PIN1-GFP expression
Timelapse
imaging
over 40
hrs
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
(Marcus
Heisler,
Caltech)
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Dynamic Phyllotactic Model
QuickTime™ and a
QuickTime™
and a
decompressor
decompressor
are needed
to see this picture.
are needed to see this picture.
Emergence of new
extended,
interacting objects:
floral meristem
primordia.
DG’s at ≥ 3 scales:
- molecular;
- cellular;
- multicellular.
NKS Washington DC 06/15/06
H. Jönnson, M. Heisler, B. Shapiro,
E. Meyerowitz, E. Mjolsness - Proc. Nat’l Acad. Sci. 1/06
UCI ICS IGB SISL
Model simulation on growing template
QuickTime™ and a
MPEG-4 Video decompressor
are needed to see this picture.
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Spatial Dynamics in
Biological Development
• Reimplemented weak spring model in 1 page
• Applying to 1D stem cell niches with
diffusion, in plant and animal tissues
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Ecology: predator-prey models
with Elaine Wong, UCI
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Example: Hierarchical Clustering
NKS Washington DC 06/15/06
UCI ICS IGB SISL
ML example:
Hierarchical Clustering
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Logic Programming
• E.g. Horn clauses
• Rules
• Operators
• Project to fixed-point semantics
NKS Washington DC 06/15/06
UCI ICS IGB SISL
An Operator Algebra for Processes
• Composition is by independent parallelism
• Create elementary processes from yet more
elementary “Basis operators”
– Term creation/annihilation operators: for each parm
value,
– Obeying Heisenberg algebra
[ai, cj] = di j
or
– Yet classical, not quantum, probabilities
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Basic Operator Algebra
Composition Operations: +, *
G Syntax
Operator algebra Informal meaning
• parallel rules
• H1 + H2
• independent,
parallel occurrence
• Multiple terms
• instantaneous,
• H1 * H2
on LHS, RHS
serial
(noncommutative)
co-occurrence
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Time Evolution Operators
• Master equation:
d p(t) / dt = H p(t)
• where 1·H = 0, e.g.
H = P(H’) = H’ - 1· diag(1·H’ )
• H = time evolution operator
– can be infinite-dimensional
• Formal solution:
p(t) = exp(t H) p(0)
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Discrete-Time Semantics of
Stochastic Parameterized Grammars
This formulation can also be used as a programming
language, expressing algorithms.
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Algorithm Derivation:
Conceptual Map
Operator Space (high dim)
DG rules
(c)
(H,
Trotter
Product
Formula
et H)
Euler’s
formula
stochastic
program
(d)
(H´, H´n/(1· H´n ·p))
NKS Washington DC 06/15/06
CBH
Time
Ordered
Product
Expansion
Heisenberg
Picture
Functional
Operator
Space
UCI ICS IGB SISL
C2: Representation as discrete
labeled graph structure that can
be searched and explored
computationally
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Basic Syntax for a Modeling Language:
Stochastic Parameterized Grammars (SPG’s)
• G = set of rules
• Each rule has:
– LHS  RHS {keyword expression}*
– Parameterized term instances within LHS and/or RHS
– LHS, RHS: sets (of such terms) with Variables
• LHS matches subsets of parameterized term instances in the Pool
– Keyword clauses specify probability rate, as a product
• Keyword: with
– Algebraic sublanguage for probability rate functions
• rates are independent of # of other matches; oblivious.
• Rule/object : verb/noun : reaction/reactant bipartite graphs
– … with complex labels
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Graph Meta-Grammar
t=3
t=1
t=3
t=1
t=2
t=2
t=3
 
 t
 
  j  I 

G  { Ai  term t i ,x i ,  A i,a  a   i  I


 Aj  term j , x j ,  A j,  

with
}
G tr ;t   0,1
NKS Washington DC 06/15/06
UCI ICS IGB SISL
“Plenum” SPG/DG
implementation
• builds on Cellerator experience
• [Shapiro et al., Bioinformatics 19(5):677-678 2003]
• computer algebra embedding provides
– probability rate language
– Symbolic transformations to executability
• includes mixed stochastic/continuous sims
NKS Washington DC 06/15/06
UCI ICS IGB SISL
SPG/DG Expressiveness Subsumes …
• Logic programming (w. Horn clauses)
– LHS  RHS; all probability rates equal
– Hence, any simulation or inference algorithms can in principle be
expressed as discrete-time SPG’s
• Chemical reaction networks
– No parameters; stoichiometry = weighted labeled bipartite graph
• Context-free (stochastic) grammars
– No parameters; 1 input term/rule
– Formally “solvable” with generating functions
• Stochastic (finite) Markov processes
– No parameters; 1 input/rule, 1 output/rule
– “Solvable” with matrices (or queuing theory?)
NKS Washington DC 06/15/06
UCI ICS IGB SISL
SPG/DG Expressiveness Subsumes …
• Bayes Nets
–
•
Each variable x gets one rule:
Unevaluated-term, {evaluated predecessors(y)}  evaluated-term(x)
MCMC dynamics
– Inverse rule pairs satisfying detailed balance
– Each rule can itself have the power of a Boltzmann distribution
•
Probabilistic Object Models
– “Frameville”, PRM, …
•
•
Petri Nets
Graph grammars
– Hence, meta-grammars and grammar transformations
•
DG’s subsume: ODE’s, SDE’s, PDE’s, SPDE’s
– Unification with SPG’s too
NKS Washington DC 06/15/06
UCI ICS IGB SISL
C3: Self-applicability
-Arrow reversal
-Arrow reversal graph grammar exercise
-Machine learning by statistical inference
-e.g. hierarchical clustering (reported)
-? Equilibrium reaction networks for MRF’s
-Further possible applications …
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Template: A-Life
Concisely expressed in SPG’s
Steady state condition: total influx into g = total outflow from g
NKS Washington DC 06/15/06
UCI ICS IGB SISL
Applications to
Dynamic Grammar Optimization
and a “Grammar Soup”
• Map genones to grammars
• Map hazards to functionality tests
• Map reproduction to crossover or simulation
NKS Washington DC 06/15/06
Conclusions
UCI ICS IGB SISL
• Stochastic process operators as the semantics for a
language
– A fundamental departure
– Specializes to all other dynamics
• Deterministic, discrete-time, DE, computational, …
• Graph grammars allow meta-processing
• Operator algebra leads to novel algorithms
• Wide variety of examples at multiple scales
– Sciences
• Cell, developmental biology; astronomy; geology
• multiscale integrated models
– AI
• Pattern Recognition
• Machine learning
• Searchable space of simple dynamical system models
including computations
NKS Washington DC 06/15/06
UCI ICS IGB SISL
For More Information
• www.ics.uci.edu/~emj  modeling frameworks
NKS Washington DC 06/15/06