# Algebra

During the project we persued the following objectives:

• develop a theory of probabilistic computation based on elementary operators and gates,
•  propose a way to encode probability distribution with stochastic binary signals and pulses,
• develop mathematical tools for analyzing the dynamic properties of networks of Bayesian gates
•  and extend some basic notions of language and programming to probabilistic machines.

Reasoning and manipulating knowledge under uncertainty is not a new idea. In fact it can be traced back to Bayes, Laplace, Poincaré, Cox, Jaynes, etc. The theory of probabilistic inference is now well established. This mathematical framework allows manipulation of uncertain knowledge at a very general and abstract level. The novelty in the BAMBI project resides entirely in the search for the minimal and simplest elements required to perform any probabilistic reasoning.

The current concept of computation manipulates sets of binary variables using Boolean algebra. It was formally expressed by Alan Turing, and supported the design of memory devices and logical gates. Later, the concept of programmable computing opened the possibility of high-level representations and hierarchies of programming languages, but still built on the base of Boolean logic operators.

The Bayesian gate is an extension of the classical logical gate. It takes two probability distributions on binary variables as entries, to provide after some elementary probabilistic inference, a probability distribution on a boolean variable as output. It will be the elementary component of the envisioned probabilistic computer.

To develop probabilistic computation as an extension to Boolean logic, we have to follow a similar roadmap. Our first objective will be to formalize an extension of Boolean algebra, which manipulates probability distributions on binary variables. The elementary atoms in this Bayesian algebra are the Bayesian values, i.e. the probability distributions over some binary variable B. The logical “false” and “true” values correspond to P([B=”true”]) = 0 and P([B=”true”]) = 1, respectively. We will also introduce new elementary operators (called Bayesian gates), e.g. sum, product and inverse operating on the Bayesian values, which can also be viewed as extensions of logical operators. For instance, the inverse of P(B) is equal to the probability of Not(B). We plan to demonstrate that any finite probabilistic inference on discrete variables can be reduced to a finite combination of these elementary operators. This “bottom-up” approach to the foundation of probability theory challenges the existing “top-down” theory which starts with general and abstract definitions of probability distributions. A key issue was to show how to build hierarchical models, starting from elementary operators to achieve complex probabilistic computations.

We proposed an efficient encoding of probability distribution on variables with stochastic signals.

Following both the thermodynamic approach and the theory of stochastic nonlinear systems, we have investigated several important dynamical properties of recurrent circuits of Bayesian gates: conventional and unconventional memory properties, adaptation and learning capacities, and implementation of Bayesian filters in space or time.  Numerical simulations and implementation on reconfigurable logic hardwarehave been performed to confirm  the obtained theoretical results.