Modelling of Biochemical Reactions by Stochastic Automata Networks

This paper presents a stochastic modelling framework based on stochastic automata networks (SANs) for the analysis of complex biochemical reaction networks. Our approach takes into account the discrete character of quantities of components (i.e. the individual populations of the involved chemical species) and the inherent probabilistic nature of microscopic molecular collisions. Moreover, as for process calculi that have recently been applied to systems in biology, the SAN approach has the advantage of a modular design process being adequate for abstraction purposes. The associated composition operator leads to an elegant and compact representation of the underlying continuous-time Markov chain in form of a Kronecker product. SANs have been extensively used in performance analysis of computer systems and a large variety of numerical and simulative analysis algorithms exist. We illustrate that describing a biochemical reaction network by means of a SAN offers promising opportunities to get insight into the quantitative behaviour of systems in biology while taking advantage of the benefits of a compositional modelling approach.     

Saturation for a General Class of Models

Implicit techniques for construction and representation of the reachability set of a high-level model have become quite efficient for certain types of models. In particular, previous work developed a "saturation" algorithm that exploits asynchronous behavior to efficiently construct the reachability set using multiway decision diagrams, but using a Kronecker product expression to represent each model event. For models whose events do not naturally fall into this category, use of the saturation algorithm requires adjusting the model by combining components or splitting events into subevents until a Kronecker product expression is possible. In practice, this can lead to additional overheads during reachability set construction. This paper presents a new version of the saturation algorithm that works for a general class of models: models whose events are not necessarily expressible as Kronecker products, models containing events with complex priority structures, and models whose state variables have unknown bounds. Experimental results are given for several examples     

Structure and order estimation of multivariable stochasticprocesses

An easy-to-implement, numerically efficient algorithm which estimates the Kronecker invariants is presented. A procedure allowing estimation of the structure of a state-space representation for a multivariable stationary stochastic process from measured output data is presented. It is assumed that the observed vector time series is a realization of a process with rational spectrum or the output of a stable, time-invariant, linear system driven by white noise. An algorithm is proposed which selects a maximal set of linearly independent rows of the Hankel matrix built upon the estimated covariance sequence, and thus yields estimates of the Kronecker invariants. When applied to simulated examples, it systematically yielded the good structure without any ambiguity, i.e. with a surprising robustness with respect to the choice of the probability of false alarm. The numerical efficiency of the procedure is remarkable, and no exhaustive search over the set of all possible Kronecker indexes has to be performed     

Numerical analysis of superposed GSPNs

The numerical analysis of various modeling formalisms profits from a structured representation for the generator matrix Q of the underlying continuous-time Markov chain, where Q is described by a sum of tensor (Kronecker) products of much smaller matrices. In this paper, we describe such a representation for the class of superposed generalized stochastic Petri nets (GSPNs), which is less restrictive than in previous work. Furthermore a new iterative analysis algorithm is proposed. It pays special attention to a memory-efficient representation of iteration vectors as well as to a memory-efficient structured representation of Q in consequence the new algorithm is able to solve models which have state spaces with several million states, where other exact numerical methods become impracticable on a common workstation     

Asymptotical stability of 2-D linear discrete stochastic systems

The main goal of the present paper is to find computable stability criteria for two-dimensional stochastic systems based on Kronecker product and nonnegative matrices theory. First, 2-D discrete stochastic system model is established by extending system matrices of the well-known Fornasini–Marchesini?s second model into stochastic matrices. The elements of these stochastic matrices are second-order, weakly stationary white-noise sequences. Second, a necessary and sufficient condition for 2-D stochastic systems is presented, this is the first time that has been proposed. Third, computable mean-square asymptotic stability criteria are derived via Kronecker product and the nonnegative matrix theory. The criteria are only sufficient conditions. Finally, illustrative examples are provided.     

Time and lag recursive computation of cumulants from a state-spacemodel

Time and lag recursive algorithms for the computation of the cumulants of the state vector and the output process of a multiple-input multiple-output time-varying state-space model are derived, using a Kronecker product representation for the cumulants of vector processes. The noise processes are not assumed to be stationary. Symmetry relations for the cumulants of vector processes are discussed. Computational aspects are examined in detail. It is conjectured that the recursive equations derived will be useful in developing state estimators and even optimal controllers based on higher order statistics     

Hierarchical Reachability Graph Generation for Petri Nets

Reachability analysis is the most general approach to the analysis of Petri nets. Due to the well-known problem of state-space explosion, generation of the reachability set and reachability graph with the known approaches often becomes intractable even for moderately sized nets. This paper presents a new method to generate and represent the reachability set and reachability graph of large Petri nets in a compositional and hierarchical way. The representation is related to previously known Kronecker-based representations, and contains the complete information about reachable markings and possible transitions. Consequently, all properties that it is possible for the reachability graph to decide can be decided using the Kronecker representation. The central idea of the new technique is a divide and conquer approach. Based on net-level results, nets are decomposed, and reachability graphs for parts are generated and combined. The whole approach can be realized in a completely automated way and has been integrated in a Petri net-based analysis tool.     

Hypermatrix Algebra: Theory

Algebraic manipulation of two-dimensional data structures—typical in image processing—requires operations more powerful than those afforded by classical matrix algebra. To this end, hypermatrix algebra provides a compact treatment of multidimensional objects and associated operations. Initially presented as array algebra, it uses a notation derived from tensor analysis. By extending matrix algebra with Kronecker products and matrix representations of shuffle permutations, a duality between the two algebras is shown. This serves as a means of transferring into the domain that is most convenient for a particular type of operation or representation. Hypermatrix algebra can be a powerful design tool for multidimensional massively parallel computing structures. A mathematical foundation for such an algebra is presented in this paper as a supplement to separate application notes.     

A Framework for Generating Distributed-Memory Parallel Programs for Block Recursive Algorithms

A framework for synthesizing communication-efficient distributed-memory parallel programs for block recursive algorithms such as the fast Fourier transform (FFT) and Strassen's matrix multiplication is presented. This framework is based on an algebraic representation of the algorithms, which involves the tensor (Kronecker) product and other matrix operations. This representation is useful in analyzing the communication implications of computation partitioning and data distributions. The programs are synthesized under two different target program models. These two models are based on different ways of managing the distribution of data for optimizing communication. The first model uses point-to-point interprocessor communication primitives, whereas the second model uses data redistribution primitives involving collective all-to-many communication. These two program models are shown to be suitable for different ranges of problem size. The methodology is illustrated by synthesizing communication-efficient programs for the FFT. This framework has been incorporated into the EXTENT system for automatic generation of parallel/vector programs for block recursive algorithms.     

Finding Minimum Vertex Covering in Stochastic Graphs: A Learning Automata Approach

Structural and behavioral parameters of many real networks such as social networks are unpredictable, uncertain, and have time-varying parameters, and for these reasons, deterministic graphs for modeling such networks are too restrictive to solve most of the real-network problems. It seems that stochastic graphs, in which weights associated to the vertices are random variables, might be better graph models for real-world networks. Once we use a stochastic graph as the model for a network, every feature of the graph such as path, spanning tree, clique, dominating set, and cover set should be treated as a stochastic feature. For example, choosing a stochastic graph as a graph model of an online social network and defining community structure in terms of clique, the concept of a stochastic clique may be used to study community structures’ properties or define spreading of influence according to the coverage of influential users; the concept of stochastic vertex covering may be used to study spread of influence. In this article, minimum vertex covering in stochastic graphs is first defined, and then four learning, automata-based algorithms are proposed for solving a minimum vertex-covering problem in stochastic graphs where the probability distribution functions of the weights associated with the vertices of the graph are unknown. It is shown that through a proper choice of the parameters of the proposed algorithms, one can make the probability of finding minimum vertex cover in a stochastic graph as close to unity as possible. Experimental results on synthetic stochastic graphs reveal that at a certain confidence level the proposed algorithms significantly outperform the standard sampling method in terms of the number of samples needed to be taken from the vertices of the stochastic graph.     

Stochastic perturbation finite elements

This paper extends the stochastic perturbation method to vector-valued and matrix-valued functions. The numerical method for the response and reliability of uncertain structures is formulated using matrix calculus, Kronecker algebra and perturbation theory. Random variables and system derivatives are conveniently arranged into two-dimensional matrices and generalized mathematical formulae are obtained. The results derived are easily amenable to computational procedures.     

Stochastic process semantics for dynamical grammars

We define a class of probabilistic models in terms of an operator algebra of stochastic processes, and a representation for this class in terms of stochastic parameterized grammars. A syntactic specification of a grammar is formally mapped to semantics given in terms of a ring of operators, so that composition of grammars corresponds to operator addition or multiplication. The operators are generators for the time-evolution of stochastic processes. The dynamical evolution occurs in continuous time but is related to a corresponding discrete-time dynamics. An expansion of the exponential of such time-evolution operators can be used to derive a variety of simulation algorithms. Within this modeling framework one can express data clustering models, logic programs, ordinary and stochastic differential equations, branching processes, graph grammars, and stochastic chemical reaction kinetics. The mathematical formulation connects these apparently distant fields to one another and to mathematical methods from quantum field theory and operator algebra. Such broad expressiveness makes the framework particularly suitable for applications in machine learning and multiscale scientific modeling.      

Recursive Compositional Models for Vision: Description and Review of Recent Work

This paper describes and reviews a class of hierarchical probabilistic models of images and objects. Visual structures are represented in a hierarchical form where complex structures are composed of more elementary structures following a design principle of recursive composition. Probabilities are defined over these structures which exploit properties of the hierarchy??e.g. long range spatial relationships can be represented by local potentials at the upper levels of the hierarchy. The compositional nature of this representation enables efficient learning and inference algorithms. In particular, parts can be shared between different object models. Overall the architecture of Recursive Compositional Models (RCMs) provides a balance between statistical and computational complexity. The goal of this paper is to describe the basic ideas and common themes of RCMs, to illustrate their success on a range of vision tasks, and to gives pointers to the literature. In particular, we show that RCMs generally give state of the art results when applied to a range of different vision tasks and evaluated on the leading benchmarked datasets.     

A canonical parameterization of the Kronecker form of a matrix pencil

The Kronecker form is the classical canonical form for matrix pencils under strict equivalence transformation. Consider a matrix pencil whose entries are smooth functions of a parameter vector. The Kronecker form of the parameterized pencil will, in general, be a discontinuous function of the parameters. For a linear time-invariant control system these discontinuities correspond to a change in the finite and infinite invariant zero structure. Since many control strategies require knowledge of, or place restrictions on, the zero structure, these points of discontinuity are of considerable interest. In this paper a general approach to the study of such points is developed in the framework of singularity theory. We derive a ‘miniversal’ parameterization of a given pencil. That is, a parameterized family of pencils that: (i) includes the given pencil, (ii) is locally equivalent to any other family up to a change of parameters, and (iii) uses the fewest number of parameters to achieve this property. All ‘nearby’ zero structures can be obtained by varying parameter values in the miniversal parameterization. From all miniversal parameterizations, one having a particularly uncluttered representation is selected as canonical. However, some restrictions on the finite elementary divisors are then required.     

Reduced Kronecker Coefficients and Counter–Examples to Mulmuley’s Strong Saturation Conjecture SH

We provide counter–examples to Mulmuley’s strong saturation conjecture (strong SH) for the Kronecker coefficients. This conjecture was proposed in the setting of Geometric Complexity Theory to show that deciding whether or not a Kronecker coefficient is zero can be done in polynomial time. We also provide a short proof of the #P– hardness of computing the Kronecker coefficients. Both results rely on the connections between the Kronecker coefficients and another family of structural constants in the representation theory of the symmetric groups, Murnaghan’s reduced Kronecker coefficients. An appendix by Mulmuley introduces a relaxed form of the saturation hypothesis SH, still strong enough for the aims of Geometric Complexity Theory.     

Representing and computing regular languages on massively parallelnetworks

A general method is proposed for incorporating rule-based constraints corresponding to regular languages into stochastic inference problems, thereby allowing for a unified representation of stochastic and syntactic pattern constraints. The authors' approach establishes the formal connection of rules to Chomsky grammars and generalizes the original work of Shannon on the encoding of rule-based channel sequences to Markov chains of maximum entropy. This maximum entropy probabilistic view leads to Gibbs representations with potentials which have their number of minima growing at precisely the exponential rate that the language of deterministically constrained sequences grow. These representations are coupled to stochastic diffusion algorithms, which sample the language-constrained sequences by visiting the energy minima according to the underlying Gibbs probability law. This coupling yields the result that fully parallel stochastic cellular automata can be derived to generate samples from the rule-based constraint sets. The production rules and neighborhood state structure of the language of sequences directly determine the necessary connection structures of the required parallel computing surface. Representations of this type have been mapped to the DAP-510 massively parallel processor consisting of 1024 mesh-connected bit-serial processing elements for performing automated segmentation of electron-micrograph images.