.

Inference and Complexity in Composite Systems

maths

This project tackles a particularly demanding area of composite systems: complex systems of interacting subcomponents where there is a combination of local interactions between subcomponents, together with a different scale of longer range interactions.


In contrast to traditional methods, based typically on large scale agent-based simulations or on numerical solutions of coupled non-linear deterministic or stochastic differentialequations, our framework is based on inherently distributive and approximative probabilistic approaches. Our methods to describe uncertainty, information transfer and emergent properties in complexsystems are based on complex connected graphs. The techniques for analysing such graphs derive from extensions of methods in statistical physics to decompose high dimensional joint distributions into simpler, computable quantities. The novelty of our method stems from the focus on systems which exhibit this composite character: a combination of localised and long range, sparse and dense, weak and strong interactions between subcomponents in such graphs.

We are interested in exploiting complexity in information systems which can be described by such graphs, but we are using techniques from physics and modify them to be applicable to inference in, and analysis of, complex systems.

This framework leads to new insights and fundamental tools and techniques on generic systems which are applicable to many important current real world problems, including CDMA coding methods, ad-hoc sensor networks, distributive traffic-lights management, embedded intelligent sensors, and cortical functioning.

The investigators of this project are Prof David Saad and Prof David Lowe.

Funding
  • Funding source: EPSRC - EP/E049516/1
  • Funding amount: £ 322,747 (D. Lowe - CI).
  • Duration: 9/2007-9/2010


Project Background

The study of complexity has been identified as a key research area of significant future demand both by UK research councils and the EU and is supported through several dedicated programmes.

However, current methods to study complexity are based on large scale simulations, for instance of interacting agents, or on numerical solutions of coupled non-linear deterministic or stochastic differential equations. Being of a large scale, highly non-linear and inherently with multi-level interactions these methods are likely to be unsuccessful in providing generic theoretical insight as well as robust, principled and reliable solutions for specific instantiations of such systems. The main problems in these approaches are their sensitivity to model parameters and external observations, their sheer scale that prevents reliable numerical modelling and the difficulty in modelling and analysing systems with multi-level interactions.

The general approach that we propose for understanding such systems is based on probabilistic approximative and distributive methods that are local, scale well (linearly or at most quadratically) with the system size, accommodate variable and measurement uncertainties and readily provide confidence levels for the inferred variables. The macroscopic description in specific problems can be provided using methods of equilibrium statistical mechanics that exploit the large system size to provide typical and robust expectation values that characterise the system's behaviour. This gives generic theoretical and analytical description of the system and further understanding of its capabilities and limitations that are difficult to obtain numerically due to the computational effort required. For instance, the macroscopic framework will identify threshold values for the ratios between the strengths of dense and sparse interactions under which a composite system could provide optimal solutions, the types and quality of solutions obtained and the conditions under which a collaborative behaviour is likely to emerge.

The problem we focus on here is that of composite systems of huge numbers of elements with multi-level interactions. These are particularly difficult and challenging in complex systems since although principled approaches have been devised for very dense or for very sparse interaction systems, they fail for the composite multilevel systems we investigate. We aim to obtain insights into information inference and knowledge structures by taking inspiration from the physics of coupled, interacting many-body systems normally analysed by methods of equilibrium statistical physics.

The exemplar application domains we have in mind span novel embedded sensor systems, control of transportation flow systems such as networks of traffic lights, and information flow in nervous systems, all of which exhibit the phenomenon of local connections with long-range interactions.  For instance, a distributive inference method for traffic light management would include information on the state of neighbouring traffic lights (strong interactions) as well as weak interactions with all traffic lights related to traffic coming into/out-of town. Similarly, individual oscillators in a MEMS array of sensors will inevitably have local neighbourhood mechanical coupling combined with parasitic long range interactions leading to possible novel emergent behaviours and new self-organising sensor modalities.

A principled approach is required to determine the optimal state and to analyse such composite systems. We propose that insight into the complexity of such systems will derive from the interdisciplinary approach of extending concepts from physics across into the information/inference domain.

For instance, in the inference domain, probabilistic graphical models (Bayes belief networks) provide a powerful framework for modelling statistical dependencies between variables in systems that can be mapped onto sparse graphs (i.e., where the number of direct probabilistic dependencies per variable is much smaller than the number of system variables and interactions are characteristically strong). These methods play an essential role in providing principled approximate probabilistic inference in a broad range of applications from medical expert systems to telecommunication. (These methods, that have largely been developed independently in the computer science and information theory literature, can be derived from early results in statistical physics: belief propagation on graphs for instance, relates to stationary points of the Bethe approximation of the free energy dating back to 1935).

However, these methods and their variations are generally inappropriate for systems that are globally more densely connected (and where the interactions are characteristically weak) as the computational effort grows exponentially with the connectivity. Also, dense systems include a high number of loops in the corresponding graphical representation which cannot be generally tolerated by these methods (since one of the main approximations used is the weak dependence between variables that are not directly connected, which is clearly violated in the presence of loops).

On the other hand, different methods, based on mean-field approximations, have been suggested for obtaining solutions in the case of densely connected systems, where the number of connections is large and of the same order as the number of variables (while the
connection strength is relatively weak compared to the system size). However, these methods rely heavily on the fact that the system is very large and the interactions weak, through a sequence of approximations.

The same dichotomy exists in the methods used for analysing disordered physical systems, and systems that can be mapped onto disordered systems.  The statistical physics methods used for analysing densely connected models, such as the Sherrington-Kirkpatrick model require different assumptions than those used in the study of sparsely connected systems. Although the models have originated in the statistical physics literature, very similar models have been used to study other complex systems such as neural networks, CDMA signal detection and error-correcting codes.

We have identified this particularly challenging area of systems' complexity of  composite systems that include both naturally sparse, strong connections and weak, dense interactions. The proposal includes both the development of inference methods in composite systems, aimed at finding solutions for particular instances, and the analysis of generic systems with multi-level interactions where computational studies are intrinsically intractable.


Objectives

In this project we will:

  • Formalise relationships between the theory and techniques of inference in composite systems to specific real-world complexity aimed at developing generic tools.

  • Develop inference methods for composite systems that include both strong and weak interactions, which are randomly
    connected in a sparse and dense manner, respectively.

  • Extend the new inference algorithms to problems that include more complex structures, such as local strongly connected regions with weak long range interactions.

  • Analyse composite models via methods of statistical physics to gain insight by studying the behaviour of such a composite system and to demonstrate the efficacy of such tools to the study of generic composite systems.

The success of the inference techniques developed will be assessed by the ability of the developed algorithms derived from principled theory to find successfully exact solutions for composite systems, compared with the performance of heuristic search algorithms. A successful analysis of generic composite physical systems, comprising interactions of various strengths and connectivities will enable us to gain insight into the behaviour of such generic complex systems, demonstrating the usefulness of the method for analysing complex systems. The insight obtained will include the identification of threshold for the system's parameters (e.g., ratios between the strengths of dense and sparse interactions) under which a composite system could provide optimal solutions both practically and theoretically, the solutions obtained in other regimes and parameter values, and under which conditions collaborative behaviour is likely to emerge.


Achievements


Publications

Journal papers

  1. R. Alamino and D. Saad, Typical Behaviour ofRelays in Communication Channels, Phys. Rev. E 76, 061124 (2007) | AURA Preprint
  2. R.C. Alamino and D. Saad, Typical Kernel Size and Number of Sparse Random Matrices over Galois Fields: A Statistical
  3. Physics Approach, Phys. Rev. E 77, 061123 (2008) | AUPreprint
  4. J. Raymond and D.Saad, Composite Systems of Dilute and Dense Couplings, J. Phys. A 41, 324014 (2008)
  5. T. Yano, T. Tanaka and D. Saad, A Mean Field Theory of Coded CDMA Systems,  J. Phys. A 41, 324022 (2008) | AURA Preprint
  6. K.Y.M. Wong and D. Saad, Minimizing  Unsatisfaction in Colourful Neighbourhoods, J. Phys. A 41, 324023 (2008) | AURA Preprint
  7. E. Mallard and D. Saad, Bayesian Inference by Message Passing in Composite Systems, Phys. Rev. E 78, 021107 (2008) | AURA Preprint
  8. J. Raymond and D. Saad, Composite CDMA - A Statistical Mechanics Analysis, Journal of Statistical Mechanics: Theory and Experiment 2009, P05015 (2009) | arXiv Preprint
  9. R.C. Alamino and D. Saad, Properties of Sparse Random Matrices over Finite Fields, Journal of Statistical Mechanics: Theory and Experiment 2009, P04017 (2009) | AURA Preprint
  10. J. Raymond and D. Saad, Equilibrium Properties of Disordered Spin Models with Two Scale Interactions, Phys. Rev. E 80, 031138 (2009) | AURA Preprint
  11. J. Reichardt, R. Alamino and D. Saad, The interplay microscopic and mesoscopic structure in complex networks (2010) submitted | arXiv Preprint
  12.  M. F. Randrianandrasana, X. Wei, D. Lowe, APreliminary Study into Emergent Behaviours in a Lattice of InteractingNonlinear Resonators and Oscillators, Communications in Nonlinear Science and Numerical  Simulations, (2010)
  13. X. Wei, M. F. Randrianandrasana, M. Ward and D. Lowe, Nonlinear Dynamics of a Periodically Driven Duffing Resonator Coupled toa Van der Pol Oscillator, Mathematical Problems in Engineering 2011, 248328 (2010)

Conferences proceedings

  1. D. Saad, J.P. Neirotti and E. Mallard, Inference by Message Passing in Dense and Composite Systems, Dagstuhl Seminar Proceedings on Similarity-based Clustering, Eds. M. Biehl, B. Hammer, M. Verleysen and T. Villmann, 8, 2007
  2. J. Raymond and D. Saad, Randomness and metastability in CDMA paradigms, 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, IEEE, 626-630, 2008
  3. R.C. Alamino and D. Saad, Typical Performance of Generalised Vector Channels, 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, IEEE, 598-602, 2008
  4. K.Y.M. Wong, D. Saad and C.H. Yeung,  Network Optimisation - A Statistical Physics Perspective, 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, IEEE, 577-582, 2008
  5. J. Raymond and D. Saad, Characteristic Behaviour of Composite Systems with Two Scale Interactions, Proceedings of the 5th European Conference on Complex Systems (electronic media) 2008
  6.  X. Wei, M. Ward, C. Anthony and D. Lowe, A preliminary study of a nonlinear micro vibro-impact system,  Proceeding of the 36th International Conference on Micro & Nano Engineering, Italy, 19 - 22 2010
  7. M. F. Randrianandrasana, X. Wei, D. Lowe, Collective Behaviour in a Square Latticeof Driven Duffing Resonators Coupled to van der Pol Oscillators, 785-790, 2010 10th IEEE International Conference on Computer and Information Technology, 2010
  8.  X. Wei, C. Anthony, D. Lowe and M. Ward, Design and Fabrication of a Nonlinear Micro Impact Oscillator Procedia Chemistry 1, 855-858, Proceedings of the Eurosensors XXIII conference, 2009

Presentations - oral

  1. R.C. Alamino and D. Saad,  GF(q) Sparse Random Matrices: Some Properties via Statistical Physics, NEXT-SigmaPhi2008 International Conference in Statistical Physics, 14-18 July 2008, Kolymbari, Crete.
  2. J. Raymond and D. Saad, Composite CDMA - A Statistical Mechanic Analysis, NEXT-SigmaPhi2008 International Conference in Statistical Physics, 14-18 July 2008, Kolymbari, Crete.
  3.  J. Raymond and D. Saad, Characteristic Behaviour of Composite Systems with Two Scale Interactions, 5th European Conference on Complex Systems, September 14-19, 2008, Jerusalem.
  4. R.C. Alamino and D. Saad, Statistical Physics of Sparse Random Matrices Over Finite Fields, The Science of Complexity, 29 March - 1 April 2009, Eilat, Israel. *
  5. R.C. Alamino and D. Saad, Statistical Physics of Sparse Random Matrices Over Finite Fields, in a workshop of the Max Planck Institute, ENRAGEing Perspectives - Random Geometry and Random Matrices: From Quantum Gravity to Econophysics, May 18-22, 2009, Dresden, Germany. *
  6. R.C. Alamino and D. Saad, Properties of Sparse Random Matrices over Finite Fields, in Statistical Mechanics of Glassy and Complex Systems, King's College London, 26 May 2009, London.
  7. D. Saad, Probabilistic Approaches to Understanding Complex Systems, The NCAF (Natural Computing Application Forum) Winter Meeting, 19-20 January, 2010, Birmingham, UK. *
  8. D. Saad and J. Raymond,  Inference and analysis of complex systems with two scale interactions, Statistical Physics and Computer Science(Satellite Meeting of STATPHYS-24) 7-11 July 2010,  Beijing, China.*
 * - By invitation

Presentation - poster

  1. J. Raymond and D. Saad, Randomness and metastability in CDMA paradigms, PHYSCOMNET 2008, The 1st Workshop on Physics-Inspired Paradigms in Wireless Communications and Networks, April 4th, 2008, Berlin, Germany
  2. R.C. Alamino and D. Saad, Typical Performance of Generalised Vector Channels, PHYSCOMNET 2008, The 1st Workshop on Physics-Inspired Paradigms in Wireless Communications and Networks, April 4th, 2008, Berlin, Germany
  3. R.C. Alamino and D. Saad, Low-Density Parity-Check Codes in Multiuser Channels: Statistical Physics Approach, European Conference on Complex Systems' 09, University of Warwick, 21-25 September, 2009
  4. D. Saad, D. Lowe,  R.C. Alamino, J. Raymond and E. Mallard, Complexity in Composite Systems, European Conference on Complex Systems' 09, University of Warwick, 21-25 September, 2009
  5. R. Alamino, J. Reichardt and D. Saad, Message passing methods for community detection in complex networks, StatPhysHK, Complexity, Computation, Information, (Hong Kong Satellite Meeting of STATPHYS-24), Hong Kong, 13-16 July 2010

Employable Graduates; Exploitable Research