Instability, complexity, and evolution

S. Vakulenko   ; D. Grigoriev

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamics systems, combinatorial methods. Part XVI, Tome 360 (2008), pp. 31-69

Résumé

In this paper, we consider a new class of random dynamical systems which contains in particular neural networks and complicated circuits. For these systems we consider the viability problem: we suppose that the system survives only if the system state is in a prescribed domain $\Pi$ of a phase space. The approach developed here is based on some fundamental ideas proposed by A. Kolmogorov, R. Thom, M. Gromov, L. Valiant, L. Van Valen, and others. Under some conditions it is shown that almost all systems from this class with fixed parameters are unstable in the following sense: the probability $P_t$ to leave $\Pi$ within time interval $[0,t]$ tends to 1 as $t\to\infty$. However, if it is allowed to change these parameters sometimes (“evolutionary” case), then possibly that $P_t<1-\delta<1$ for all $t$ (“stable evolution”). Furthermore we study the properties of such stable evolution assuming that the system parameters are coded by a dicsrete code. This allows us to apply the complexity theory, coding, algorithms etc. Evolution is a Markov process of this code modification. Under some conditions we show that the stable evolution of unstable systems possesses such general fundamental property: the relative Kolmogorov complexity of the code cannot be bounded by a constant as time $t\to\infty$. For circuit models we define complexity characteristics of these circuits. We find that these complexities also have a tendency to increase during stable evolution. We give concrete examples of stable evolution. Bibl. – 80 titles.

Bibliographie

[1] B. Alberts, D. Bray, J. Lewis, M. Raff, K. Roberts, P. Walter, Molecular Biology of the Cell, 4nd ed., Garland Publishing, Inc., New York, 2002

[2] J.-P. Aubin, A. Bayen, N. Bonneuil, P. Saint-Pierre, Viability, control and games: regulation of complex evolutionary systems under uncertainty and viability constraints, Springer-Verlag, 2005

[3] J.-P. Aubin, Mutational and morphological analysis: tools for shape regulation and morphogenesis, Birkhäuser, 2000 | MR

[4] J.-P. Aubin, Dynamic economic theory: a viability approach, Springer-Verlag, 1997 | MR | Zbl

[5] J.-P. Aubin, Neural networks and qualitative physics: a viability approach, Cambridge University Press, 1996 | MR | Zbl

[6] R. Albert, A. L. Barabási, “Statistical mechanics of complex networks”, Rev. Modern Physics, 74 (2002), 47–97 | DOI | MR | Zbl

[7] A. Barron, “Universal Approximation Bounds for superpositions of a sigmoidal functions”, IEEE Trans. Inf. Theory, 39 (1993), 930–945 | DOI | MR | Zbl

[8] R. Bhattacharya, M. Majumdar, Random Dynamical Systems. Theory and Applcations, Cambridge, 2007 | MR

[9] M. Benaim, N. El Karoui, Promenade aleatoire (Chaines de Markov et simulations; martingales et strategies), Les editions de l'école polytechnique, 2004 | Zbl

[10] S. Boucheron, O. Bousquet, G. Lucosi, “Theory of classification: survey of some recent advances”, ESAIM: Probability and Statistics, 9 (2005), 323–375 | DOI | MR | Zbl

[11] B. S. Cireltson, I. A. Ibragimov, V. N. Sudakov, “Norm of Gaussian sample function”, Proceedings of the 3rd Japan–U.S.S.R. Symposium on Probability Theory, Lect. Notes in Math., 550, Springer-Verlag, Berlin, 1976, 20–41 | MR

[12] T. H. Cormen, Charles E. Leiserson, L. Ronald, Rivest, and Cliff Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001 | MR | Zbl

[13] C. Deroulers, R. Monasson, “Criticality and universality in the unit-propagation search rule”, Eur. Phys. J., B49 (2006), 339

[14] C. Deroulers, R. Monasson, “Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class”, Europhys. Lett., 68 (2004), 153 | DOI

[15] V. M. Dilman, “Aging, Rate of Aging, and Cancer”, A Search for Preventive Treatment, Annals of the New York Academy of Sciences, 719, The Aging Clock: The Pineal Gland and Other Pacemakers in the Progression of Aging and Carci (1994), 454–455 | DOI

[16] R. Edwards, T. H. Siegelmann, K. Aziza, L. Glass, “Symbolic dynamics and computation in model gene networks”, Chaos, 11 (2001), 160–169 | DOI

[17] M. Eigen, P. Schuster, The Hypercycle: A Principle of Natural Self-Organization, Springer, Berlin, 1979 | Zbl

[18] P. Erdos, A. Rényi, “On the evolution of random graphs”, Publ. Math. Inst. Hungarian Academy of Sciences, 5 (1960), 17–61 | MR

[19] K. Funahashi, Y. Nakamura, “Approximation of Dynamical Systems by Continuous Time Recurrent Neural Networks”, Neural Networks, 6 (1993), 801–806 | DOI

[20] A. Gabrielov, N. Vorobjov, “Complexity of computations with Pfaffian and Noetherian functions”, Normal Forms, Bifurcations and Finiteness Problems in Differential Equations, Kluwer, 2004, 211–250 | MR

[21] L. Glass, S. Kauffman, “The logical analysis of continuous, nonlinear biochemical control networks”, J. Theor. Biology, 34 (1973), 103–129 | DOI

[22] D. Grigoriev, N. Vorobjov, “Complexity Lower Bounds for Computation Trees with Elementary Transcendental Functions Gates”, Theoret. Comput. Sci., 157 (1996), 185–214 | DOI | MR | Zbl

[23] D. Grigoriev, “Deviation theorems for solutions of linear ordinary differential equations and applications to parallel complexity of sigmoids”, St. Petersburg Math. J., 6 (1995), 89–106 | MR

[24] D. Grigoriev, “Deviation theorems for Pfaffian sigmoids”, St. Petersburg Math. J., 6 (1995), 107–111 | MR

[25] D. Grigoriev, “Approximation and complexity: Liouvillean type theorems for linear differential equations on an interval”, Found. Computat. Math., 1 (2001), 289–295 | MR | Zbl

[26] D. Grigoriev, “Approximation and complexity. II. Iterated integration”, Found. Computat. Math., 2 (2002), 295–304 | DOI | MR | Zbl

[27] M. Gromov, A. Carbone, Mathematical slices of molecular biology, Preprint IHES/M/01/03, 2001 | MR

[28] J. K. Hale, J. K. La Salle, M. Slemrod, “Theory of a general class of dissipative process”, J. Math. Anal. Appl., 39 (1972), 177–191 | DOI | MR | Zbl

[29] L. H. Hartwell, J. J. Hopfield, S. Leibler, A. W. Murray, “From molecular to modular cell biology”, Nature (London), 402 (1999), C47–C52 | DOI

[30] R. Hecht-Nielsen, “Kolmogorov's mapping neural network existence theorem”, IEEE International Conference on Neural Networks, SOS Printing, San Diego, 1987, 11–14

[31] D. Henry, Geometric Theory of Semilinear Parabolic Equations, Lect. Notes in Math., 840, Springer, New York–Heidleberg–Berlin, 1981 | MR | Zbl

[32] M. W. Hirsch, Differential topology, New York–Heidelberg–Berlin, 1976 | MR

[33] J. J. Hopfield, “Neural networks and physical systems with emergent collective computational abilities”, Proc. Natl. Acad. USA, 79 (1982), 2554–2558 | DOI | MR

[34] K. Hornik, M. Stinchcombe, H. White, “Multilayer feedforward networks are universal approximators”, Neural Networks, 2 (1989), 359–366 | DOI

[35] H. Jeong, B. Tombor, R. Albert, Z. N. Otvai, A. L. Barabási, “The large-scale organisation of metabolic networks”, Nature (London), 407 (2000), 651–654 | DOI

[36] Yu. Ilyashenko, Li Weigu, Nonlocal bifurcations, Amer. Math. Soc., Providence, RI, 1999 | MR | Zbl

[37] H. Jeong, S. P. Mason, A. L. Barabási, Z. N. Otvai, “Lethality and centrality in protein networks”, Nature (London), 411 (2000), 41–42 | DOI

[38] A. Khovanskii, Fewnomials, Transl. Math. Monographs, 88, Amer. Math. Soc., Providence, RI, 1991 | MR | Zbl

[39] P. Koiran, C. Moore, Closed-form analytic maps in one and two dimensions can simulate Turing machines, DIMACS Technical Report 96-25; Theoretical Computer Science, 210:1 (1999), 217–223 | DOI | MR | Zbl

[40] O. A. Ladyzenskaya, “On a dynamical system generated by Navier–Stokes equations”, Zap. Nauchn. Semin. LOMI, 27, 1972, 97–114

[41] C. Lobry, “Une proprieté generique des couples de champs de vecteurs”, Chechoslovak Math. J., 22(97) (1972), 230–237 | MR | Zbl

[42] Ming Li, P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd ed., Springer-Verlag, 1997, xx+637pp. | MR

[43] A. L. Lehninger, D. L. Nelson, M. M. Cox, Principles of Biochemistry, 2nd ed., Worth, New York, 1993

[44] A. Lesne, “Complex networks: from graph theory to biology”, Lett. Math. Phys., 78 (2006), 235–262 | DOI | MR | Zbl

[45] H. Meinhardt, Mathematical Models for Biological Pattern Formation, IMA Volumes in Mathematics and its Applications, 121, eds. P. K. Maini, H. G. Othmer, Springer, New York–Berlin–Heidelberg, 2000 | MR | Zbl

[46] L. Mendoza, E. R. Alvarez-Buylla, “Dynamics of Genetic Regulatory Networks for Arabodopsis thaliana Flower Morphogenesis”, J. Theor. Biol., 193 (1998), 307–319 | DOI

[47] E. Mjolness, D. H. Sharp, J. Reinitz, “A connectionist Model of Development”, J. Theor. Biol., 152 (1991), 429–453 | DOI

[48] J. D. Murray, Mathematical Biology, Springer, New York–Berlin–Heidelberg, 1993 | MR

[49] C. H. Papadimitriou, K. Steglitz, Combinatorial optimization, Algorithms and Complexity, Prentice Hall, Inc., Englewood Cliffs, NJ, 1982 | MR | Zbl

[50] J. Reinitz, D. H. Sharp, “Mechanism of formation of eve stripes”, Mechanisms of Development, 49 (1995), 133–158 | DOI

[51] M. Ridley, Evolution, 2nd ed., Blokwell Scientific Publications Ltd., Oxford, 1996

[52] D. Ruelle, Elements of differentiable dynamics and bifurcation theory, Acad. Press, Boston, 1989 | MR | Zbl

[53] I. Salazar-Ciudad, J. Garcia-Fernadez, R. V. Solé, “Gene Networks Capable of Pattern Formation: From Induction to Reaction-Diffusion”, J. Theor Biology, 205 (2000), 587–603 | DOI

[54] S. Smale, Mathematics of Time, Springer, New York, 1980 | MR | Zbl

[55] P. Smolen, D. Baxter, J. H. Byrne, “Mathematical modelling of gene networks”, Review Neuron, 25 (2000), 247–292

[56] H. J. Sussmann, “A general theorem on local contollability”, SIAM J. Control and Optimization, 25:1 (1987), 158–194 | DOI | MR | Zbl

[57] M. Talagrand, “Concentration of measure and isoperimetric inequalities in product spaces”, Inst. Hautes Études Sci. Publ. Math., 81 (1995), 73–205 | DOI | MR | Zbl

[58] M. Talagrand, “New concentration inequalities in product spaces”, Invent. Math., 126 (1996), 505–563 | DOI | MR | Zbl

[59] R. Temam, Infinite dimensional system in mechanics and physics, Springer-Verlag, New York, 1998 | Zbl

[60] D. Thieffry, R. Thomas, “Dynamical behaviour of biological regulatory networks. II. Immunity control in bacteriophage lambda”, Bull. Math. Biology, 57 (1995), 277–295

[61] R. Thom, Stabilité structurelle et morphogénèse, Benjamin, New York, 1972 | MR

[62] A. M. Turing, “The chemical basis of morphogenesis”, Phil. Trans. Roy. Soc. B, 237 (1952), 37–72 | DOI

[63] S. Vakulenko, S. Genieys, “Patterning by genetic networks”, Mathematical Methods in Applied Sciences, 29 (2005), 173–190 | MR

[64] S. Vakulenko, D. Grigoriev, “Algorithms and complexity in biological pattern formation problems”, Annales of Pure and Applied Logic, 141 (2006), 421–428 | MR

[65] S. Vakulenko, D. Grigoriev, “Evolution in random environment and structural stability”, J. Math. Sci., 138 (2006), 5644–5662 | DOI | MR

[66] S. Vakulenko, D. Grigoriev, “Stable growth of complex systems”, Proceeding of Fifth Workshop on Simulation, St. Petersburg, 2005, 705–709

[67] S. Vakulenko, D. Grigoriev, “Complexity of gene circuits, Pfaffian functions and the morphogenesis problem”, C. R. Acad. Sci. Ser. I, 337 (2003), 721–724 | MR | Zbl

[68] S. Vakulenko, S. Genieys, “Pattern programming by genetic networks, Patterns and Waves”, Patterns and waves, Collection of papers, eds. A. Abramian, S. Vakulenko, V. Volpert, St. Petersburg, 2003, 346–365 | MR

[69] S. A. Vakulenko, “Dissipative systems generating any structurally stable chaos”, Adv. Diff. Equations, 5 (2000), 1139–1178 | MR | Zbl

[70] L. Van Valen, “A new evolutionary law”, Evolutionary Theory, 1 (1973), 1–30

[71] L. Valiant, “Evolvibility”, Lect. Notes Comput. Sci., 4708, 2007, 22–43 | MR | Zbl

[72] L. G. Valiant, “A theory of learnable”, Comm. ACM, 27 (1984), 1134–1142 | DOI | Zbl

[73] A. D. Ventsel, M. I. Freidlin, Random Perturbations of Dynamic systems, Springer, New York, 1984 | MR

[74] A. M. Vershik, F. V. Petrov, Invariant measures on the set of graphs and homogeneous uncountable universal graphs, PDMI preprint 08/2008, 2008 | MR

[75] B. L. van der Waerden, Modern Algebra, Vol. 1, Ungar, New York, 1953

[76] M. Blum, “A machine-independent theory of the complexity of recursive functions”, J. Assoc. Comput. Machin., 14 (1967), 322–336 | MR | Zbl

[77] E. Friedgut, “Sharp thresholds of graph properties, and the $k$-SAT problem”, J. Amer. Math. Soc., 12:4 (1999), 1017–1054 | DOI | MR | Zbl

[78] L. Wolpert, R. Beddington, T. Jessell, P. Lawrence, E. Meyerowitz, J. Smith, Principles of Development, Oxford University Press, 2002

[79] M. K. S. Yeung, J. Tegner, J. J. Collins, “Reverse engineering gene networks using singular decomposition and robust regression”, Proceeding of Nat. Acad. Sci., 99, 2002, 6163–6168

[80] A. K. Zvonkin, L. A. Levin, “The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms”, Russ. Math. Surv., 25:6 (1970), 83–124 | DOI | MR | Zbl