ACEnetica

This blog is now closed

2007-08-25T20:35:00.000Z

Please go to The Spline for future blog postings.

Commentary

2007-01-26T22:42:00.000Z

Jorge Luis Borges wrote:

The composition of vast books is a laborious and impoverishing extravagance. To go on for five hundred pages developing an idea whose perfect oral exposition is possible in a few minutes! A better course of procedure is to pretend that these books already exist, and then to offer a résumé, a commentary.

Well, that should save a bit of time!

Discrete network dynamics. Part 1: Operator theory (update 2)

2007-01-24T19:04:00.000Z

I need to update what is going on with my paper "Discrete network dynamics. Part 1: Operator theory", which can be found in arXiv at cs.NE/0511027. Yes, it was that long ago and the paper is still not published, nor do I know how I can get it published. I previously blogged about this here, here, here, and here.

I have been getting rather evasive feedback from various people about this paper, and I don't like the sound of what I hear at all. In a nutshell, there is a widespread view that my use of quantum field theory is misguided and/or wrong.

One critic said that I didn't understand quantum mechanics, which I thought was rather odd given that my PhD is in quantum chromodynamics! That comment immediately told me that he had not read my paper, or at least had not read it very carefully, because I don't actually use quantum mechanics in the paper, as least not in the sense that physicists use it (i.e. the sense in which the criticism was made). In my paper I explain how I use operators to implement the elementary processes of adding samples to and removing samples from histogram bins, and that these operators have exactly the same algebraic properties as the bosonic creation and annihilation operators that are used in physics. To this extent, what I am doing is algebraically equivalent to a quantum field theory, and I explained this in greater detail in an earlier posting here. What I am certainly not doing is using a representation of these operators in which they act on an underlying wave function, because there isn't any wave function defined in my samples-in-histogram-bins model. My creation and annihilation operators should be thought of as little pieces of algorithm whose effect is to add and remove samples from histogram bins.

All I use is operators for creating and annihilating quanta; the model is defined at the level of these quanta, and there is no deeper level of theory. This is where the QFT that I use is a subset of the type of QFT that physicists are familiar with; I make use of only the combinatoric properties of field quanta, which are elegantly summarised in the algebraic properties of the corresponding creation and annihilation operators. I also use a lattice QFT, rather than a continuum QFT, but I assume that the difference between these two is relatively benign (pace, mathematical purists!). Because physicists are exposed to QFT in (relativistic) particle physics and in (non-relativistic) condensed matter physics, they naturally assume that QFT needs an underlying wave function with the usual quantum mechanical behaviours that they have been taught about. This is a very narrow definition of QFT, because you can have a QFT whose quanta are built in any way that you want.

One can manipulate these creation and annhilation operators by using their algebraic properties to rearrange "operator products" in various ways, and thus break operator expressions apart into a sum of contributions with different combinatoric properties, each weighted by a combinatoric factor that is automatically generated by the algebraic manipulations. These manipulations have the same general structure as the sorts of manipulation that occur in "operator product expansion" calculations in high energy physics; my PhD dissertation is full of this sort of calculation, and some relevant papers that I contributed to can be found by doing a search of the SPIRES database here.

All the above leaves me no choice but to describe what I write about in my paper "Discrete network dynamics. Part 1: Operator theory" as a "quantum field theory".

Four preconditions for civilisation?

2006-12-26T23:44:00.000Z

If you are wondering why there is no news on the ACEnetica front, it's because none of the Four preconditions for civilisation is currently being met.

Burden of proof

2006-08-28T18:59:00.000Z

There is an article by Marcus du Sautoy entitled Burden of Proof in this week's New Scientist, which discusses the issue of whether a computer generated mathematical proof can be considered to actually be a proof, especially since some such proofs are so lengthy that they cannot be checked by a human. An example of this type of proof is the 4-colour map theorem.

My own view on this issue is that a computer generated proof has exactly the same status as a human generated proof. The difference is only one of the degree of assistance provided to the brain of the human to help with the generation of the proof. A totally unassisted human would have to somehow do the whole proof mentally, which severely limits the length of proofs that are accessible. A human with the typical assistance that is allowed in an examination room (i.e. pen and paper) has the luxury of at least being able to write things down, which allows much longer proofs to be reliably generated. The mechanics of generating a proof then reduce to using well-defined rules to manipulate symbolic expressions, where pen and paper are used as a medium for representing these symbols, and the rules are implemented in the human brain.

The degree of assistence in generating a proof can be taken one stage further by using a computer to implement some or all of the rules for manipulating the symbolic expressions, rather than implementing all of the rules in the human brain. This seems to be a fairly radical step to take, because hitherto the only part of the proof that was "outside" the human brain was its "dumb" representation using pen and paper, whereas the "clever" bit involving the implementation of rules to manipulate this representation was "inside" the human brain.

Let us consider what these rules of manipulation actually are. Effectively, they define a procedure for taking an initial expression constructed out of symbols, and repeatedly operating on it using the rules to eventually generate the required final expression. The cleverness is in the construction of the set of rules, which is where a human is the best source of the cleverness needed to create the rules. There is no cleverness in the repeated application of these rules; all that is required is that their application is done reliably, which is where a computer is the best approach, especially if the proof has many steps.

Use a human to define the rules of manipulation, and use a computer to implement these rules. This approach seems to me to be entirely uncontroversial, and it is exactly how computer generated proofs are done. Note that software bugs in the computer part of the proof are dealt with in an analogous way to "software" bugs in human part of the proof, i.e. try a variety of approaches on a variety of platforms.

Interestingly, I wrote a paper (see here)

Luttrell S P, 1999, Self-organised modular neural networks for encoding data, in Combining Artificial Neural Networks: Ensemble and Modular Multi-Net Systems (Perspectives in Neural Computing, Springer-Verlag, ed. Sharkey A J C), pp. 235-263

in which I used a computer (running the symbolic algebra program Mathematica) to help me derive some results on the optimisation of vector quantisers so that their Euclidean distortion was minimised, and this optimisation was done non-parametrically in order to discover the globally optimal solution. The only way that I have found to do this type of optimisation involves intermediate expressions that can have a large number of terms, but which eventually leads to results that can be quite compact, and which are thus interesting. The only sensible way of handling this type of derivation is to automate it using a computer to implement the rules of manipulation (i.e. using symbolic algebra). As far as I can tell other people have not taken up my idea of using symbolic algebra to derive this type of result; my paper went down like a lead balloon, which is a great pity.

Update: OK, I can see that the Mathematica notebook in which I derive the results that I published in the above paper (see here) has now been downloaded 22 times (as of 31 December 2006). It would be interesting to hear your comments on it. Maybe you think it is just a load of algebraic twiddling which is not much use in the real world, but that conclusion would ignore the fact that exact algebraic solutions to toy problems are a powerful source of insight for interpreting approximate numerical solutions to real world problems.

Holiday

2006-07-23T18:50:00.000Z

I will be on holiday in the south-west of England for the next 2 weeks, and I won't be able to access the internet, so any comments will remain unanswered until I return.

Modelling the probability density of Markov sources

2006-07-07T20:08:00.000Z

I have just uploaded a paper to arXiv here.

Title: Modelling the probability density of Markov sources

Abstract: This paper introduces an objective function that seeks to minimise the average total number of bits required to encode the joint state of all of the layers of a Markov source. This type of encoder may be applied to the problem of optimising the bottom-up (recognition model) and top-down (generative model) connections in a multilayer neural network, and it unifies several previous results on the optimisation of multilayer neural networks.

I wrote this paper about a decade ago, and submitted it to Neural Computation on 2 February 1998, but in effect it was not accepted for publication because the referees asked for changes to be made to the paper that I thought (and still think) were unreasonable. Apart from minor reformatting changes, this arXiv version of the paper is identical to the version that I submitted to Neural Computation.

The paper contains material that is based on a preprint that I wrote at the Neural Networks and Machine Learning Scientific Programme at the Isaac Newton Institute in 1997. The Newton Institute preprint number is NI97039, and it is available online on this page of 1997 preprints, or can be accessed directly here.

The main idea in the paper is to optimise a multi-layer density-modelling network so that the joint probability of the state of all of its layers has desirable properties, rather than for the marginal probability of the state of only its input layer to have desirable properties. In effect, all of the layers of the network are put on an equal footing, rather than selecting the input layer to be treated differently from the rest of the layers. The approach to density modelling described in this paper turns out to unify various results that I had published in several of my earlier papers.

The objective function for optimising the joint probability of the state of all the layers of a network is almost the same as the one that is used to optimise a Helmholtz machine, but it omits the so-called "bits-back" term that is used by Helmholtz machines, so it penalises the use of distributed codes whilst encouraging the use of sparse codes in the hidden layers of the network. At the Neural Networks and Machine Learning Scientific Programme in 1997, I was told by Geoffrey Hinton (who is one of the originators of the Helmholtz machine) that they had looked at what happened if they omitted the bits-back term, and they had concluded that it didn't lead anywhere interesting! I found this remark quite amusing because much of my useful research output had derived from omitting the bits-back term. Also, with the decade of additional insight that I have accumulated since 1997, I can now see that joint (rather than marginal) probability optimisation is the key to obtaining useful results in multi-layer density-modelling networks. Watch this space, as they say!

Discrete network dynamics stirs

2006-06-17T19:07:00.000Z

After the setback where my DND1 paper Discrete network dynamics. Part 1: Operator theory (which can be found in arXiv at cs.NE/0511027) was rejected (see here for some remarks about this problem, and in the comments here for some less diplomatic remarks), I have finally started the ball rolling again by actually sitting down to prepare the draft of the second paper in the series (i.e. DND2).

I have published a lot of material on vector quantisers of various types, but unfortunately the common underlying thread behind all of this work is not at all clear from my papers on the subject. Historically, I started working on VQs in the mid-1980's, and I was a refugee from Markov random field models which were too computationally costly for the rather slow computers that we used back then. I have always had an MRF style of thinking (i.e. joint probabilities, Bayesian inference, etc), and VQs offered me a computationally cheap and cheerful way of using some of the properties of MRF models.

One of the many reasons why I introduced (in DND1) the operator framework for formulating MCMC algorithms was to unify all of my past work on VQs. Therefore the provisional title of DND2 will be "Discrete network dynamics. Part 2: Vector quantisers". I don't know how long DND2 will be in gestation, because I usually get side-tracked by some new angle that occurs to me whilst I am writing, which then explodes into a whole new line of research that diverts me entirely away from the original task. I will try to avoid that pitfall, but I can't promise that it won't happen.

Anyway, I thought that you should know that DND is alive and well (even if the reviewers of DND1 didn't think so!).

Update: In my spare time I have been busy "evolving" my DND2 paper. I can't just write down a paper in its final form, rather I have to evolve it from nothing until it reaches a fixed point. As predicted, during this process I have been side-tracked, but it has been onto fertile ground which directly relates to DND2, and which pulls together all of my vector quantiser work even more nicely than I had originally anticipated. As long as 20 years ago I knew all of the operator techniques that I am using in DND2, so you can imagine how annoyed I feel about the circuitous path my research has taken during the intervening years. My evolution of DND2 continues apace, and I will keep you updated as this process converges towards a fixed point.

Update: I have just returned from a long Summer holiday during which I thought about my DND2 paper for precisely 0% of the time. Now I have to try to remember where I was in the process of writing DND2, so its gestation will be fairly long as I hinted at in my original posting.

Information processing researchers don't like quantum field theory? (update)

2006-04-26T18:07:00.000Z

It has now been officially confirmed. Information processing researchers don't like quantum field theory. My paper Discrete network dynamics. Part 1: Operator theory (which can be found in arXiv at cs.NE/0511027) has been rejected by the Journal of Machine Learning Research. I presume that I should not quote verbatim from the rejection letter. However, the gist of the reasons for rejection were based on reports from two reviewers:

The need to include more citations to related work. [This is entirely reasonable. I had overlooked some prior work that didn't use the right key words to be caught by my literature search.]
The need to include a proof of the convergence to the correct joint PDF when multiple iterations of the update operator were used. [I had already proved that a single iteration of the update operator was exactly equivalent to a standard MCMC update, and we already know the convergence properties after multiple iterations of a standard MCMC update, so I don't actually need to provide any proof. There is nothing new to prove!]
The need to supply explicit examples of MCMC algorithms generated by use of this approach. [The whole section on ACEnet is such an example. I could supply more examples, but the paper is already quite long, and I intend to publish these in future papers in the series.]

The paper was also sent to a third reviewer who gave an "informal" report which included the statement that my creation and annihilation operators were curious because they anti-commuted. This is news to me, so I invite anyone to point out where I use anti-commuting operators in my paper.

I am disappointed that my paper should be unconditionally rejected. However, it was not a complete surprise to me (see the title of this posting), so I am not even angry about it. The net effect is that there is now a blockage in the way of all subsequent papers in the DND series, where I investigate various consequences of this approach. Never mind, what I do in this sort of circumstance is to dump a highly abbreviated (and thus incomprehensible) version of the paper on an unsuspecting conference somewhere, where it can languish in their proceedings to be read only by the most inquisitive researchers.

Discrete network dynamics. Part 1: Operator theory (update)

2006-03-20T20:03:00.000Z

My paper Discrete Network Dynamics. Part 1: Operator Theory which I submitted to the Journal of Machine Learning Research turns out to be rather difficult to assign to reviewers. I just received an apologetic note from the action editor for my paper saying that the people who were the most suitable for reviewing my paper were unavailable for one reason or another. The reasons were not given, but I wonder whether it is because Information processing researchers don't like quantum field theory. I hope this is not the case, but I fear the worst.

Optimistically, at least this gives me some more time to extend and refine the ideas in the paper, before I write further papers in the DND sequence of papers.

Quantum field = tokens in bins

2006-02-26T11:00:00.000Z

I wonder whether some people find the phrase "quantum field theory" off-putting, especially when it is used in the context of networks that are discrete time dynamical systems, such as is described in my paper Discrete network dynamics. Part 1: Operator theory.

Quantum field theory is defined in wikipedia as:

Quantum field theory (QFT) is the application of quantum mechanics to fields. It provides a theoretical framework, widely used in particle physics and condensed matter physics, in which to formulate consistent quantum theories of many-particle systems, especially in situations where particles may be created and destroyed.

This is a physicists' definition of QFT, which ignores the wider use of the very useful algebraic properties of QFT in the description of many-particle systems. In the discussion below I will focus on bosonic statistics only, where the algebraic properties are defined using commutation rather than anti-commutation relations. Also, I will assume that the theory is defined on a discrete lattice, rather than on a continuous background space.

Stripped down to its bare essentials, QFT is a theory of how to manipulate "tokens" (e.g. particles) that are stored in "bins" (e.g. states). Each configuration of tokens-in-bins defines a particular set of bin occupancies (e.g. pure state).

Creation and annihilation operators applied to the occupants of these bins causes tokens to be created or annihilated in exactly the way that one would intuitively expect:

A creation operator adds a token to a bin (there is only one way of doing this to a bin), whereas an annihilation operator removes a token from a bin (the number of ways of doing this is equal to the number of tokens in the bin). This corresponds to the commutation relation [a_i, a_j†] = δ_i,j.
An annihilation operator completely erases a bin if it is already empty of tokens. This corresponds to annihilation of the vacuum state a_i│0> = 0.
A weighted sum of products of creation operators produces a correspondingly weighted sum of bin occupancies (i.e. mixture state).

The above description of the properties of creation and annihilation operators does not mention Planck's constant, nor does it specify what weights to use in a weighted sum of operators. The algebraic structure of QFT is not specifically designed for a quantum theory in which Planck's constant appears, and where the weights are complex-valued probability-amplitudes. Rather, stripped down to its bare essentials, QFT is a very convenient algebraic structure for doing the combinatoric book-keeping associated with the creation and annihilation of tokens in bins, where the weights are real-valued probabilities.

So the algebra of QFT is perfect for describing the manipulation of tokens in bins. Many of the algebraic techniques of QFT that have been developed in the context of physics can be reused in the context of tokens-in-bins. For instance, Feynman diagrams are used in physics to represent algebraic expressions that are formed from operators that generate interlinked sets of particle creation and annihilation operations. These diagrams can also be used to describe interlinked sets of operations on tokens in bins.

So quantum field theory (bosons on a lattice) is entirely appropriate for describing networks that are discrete time dynamical systems, in which the basic update operation consists of the creation and annihilation of tokens in bins.

ACEnet = discretised quantum field theory

2006-02-04T20:30:00.000Z

A while ago I blogged about Markov chain Monte Carlo sampling from joint probability density functions, which is background material for my paper Discrete network dynamics. Part 1: Operator theory (DND1). I want to explain this connection in more detail here.

The purpose of DND1 is to introduce an operator framework for expressing MCMC algorithms that explore discrete state spaces, where the state space itself looks like the bins of a histogram, and each state is a particular joint occupancy of all of the histogram bins.

Special cases of this type of space are:

A single discrete-valued quantity that takes values in the set {0, 1, 2, ...} corresponds to a single histogram bin with a variable occupancy.
m binary-valued quantities, exactly one of which is 1 whilst the rest are 0, corresponds to m histogram bins with a single occupant in exactly one of the bins, whilst the rest of the bins are empty.
m discrete-valued quantities correspond to m histogram bins each with the appropriate occupancy. This directly generalises case (1) above.
If the occupancy in case (3) is constrained in any way, then the corresponding histogram bin occupancies are analogously constrained. Case (2) above is a special case of this.
nm discrete-valued quantities can be factorised as n separate instances of m quantities, which thus corresponds to n separate histograms each having m bins. This sort of factorisation generalises in a straightforward way.
A graph with n nodes, each containing m discrete values, corresponds to n histograms each having m bins. This is an example of case (5) above.

Assume that a single histogram with m=5 bins and n=10 occupants has a discrete-time evolution that is generated by hopping a single sample from one bin to another when the time index advances by one unit. A typical evolution might look like the diagram below.

In the diagram time advances from left to right, at each time instant the histogram state is represented as a bar chart, and at each advance in the time index the change in the histogram state is indicated by the red highlighted connection which shows where a sample has hopped from one bin to another.

In this example each hopping operation is generated by first annihilating a sample and then creating a sample. The annihilation operation chooses which sample to annihilate at random from the whole histogram, whereas the creation operation generates a sample in bin i with probability p_i.

The update operator H that generates this is given by (using standard quantum field theory notation for bosonic creation and annihilation operators)

H ≡ ∑_i p_i a_i† ∑_j a_j

where ∑_j a_j is a sum (from j = 1 to m) of annihilation operators that annihilates a sample at random, and ∑_i p_i a_i† is a probability-weighted sum (from i = 1 to m) of creation operators that creates a sample in the required probability-weighted fashion. If H is applied to a histogram it produces an ensemble of histograms, whose members correspond to each of the possible outcomes of applying H. In the diagram above a single member of this ensemble is randomly chosen at each time step, using an appropriate probability weighting to take account of the p_i factor.

In this case, the equilibrium mixture of histograms that is stationary under application of the update operator can be readily deduced. Each update is a random annihilation followed by a probability-weighted creation, which is overall a memoryless probability weighted hopping operation. Thus the equilibrium mixture of histograms is the same as is obtained by starting with an empty histogram (the "vacuum" state), and then randomly and independently placing n samples into its bins using the same probability weighting for selecting bins as above.

This probability-weighted placement of n samples into m bins is exactly the procedure that is used in the ACEnet self-organising encoder network, where ACEnet is a generalisation of a stochastic vector quantiser to the case of encodings that use more than one sample to represent the code.

So, the discrete-time evolution of a histogram under the action of the update operator H defined above has an equilibrium mixture of histograms that is the same as the distribution of output codes that is obtained from ACEnet.

This is an incredibly useful result, because it allows ACEnet to be replaced by a discrete-time dynamical system whose update operator H is built out of standard QFT creation and annihilation operators. Essentially, discretised QFT is a way of describing a MCMC algorithms, and ACEnet is a special case of a discretised QFT. All information processing in ACEnet can now be analysed using standard QFT techniques. This result is what motivated me to write of the DND1 paper.

Expressing ACEnet in the language of QFT has made it possible to use a lot of existing physical insight into and theoretical techniques from QFT in the analysis of ACEnet. Future papers in the DND series will focus on various developments based on these ideas.

Information processing researchers don't like quantum field theory?

2006-01-23T18:18:00.000Z

Having discovered that the problem uploading images was my fault (see update comment here) I am now trying to remember what I was planning to post about my Discrete network dynamics. Part 1: Operator theory paper. I am finding it difficult to pick up this thread.

Thus far the paper has attracted only one comment, which I hope that I answered satisfactorily. I am disappointed not to have received more comments, and it makes it difficult for me to guess what best to focus on in my planned follow-up postings on the paper. It also makes it difficult for me to fine tune the paper so that it is ready for peer-reviewed publication; I still have not submitted it for publication.

It is possible that despite my efforts to make the quantum field theory aspect of the paper self-contained, it nevertheless proves to be unintelligible to my intended readers (i.e. people working on information processing networks). Well, that is not surprising to me, because QFT is not really what you would expect to use when doing information processing.

I guess my intended readers will pay attention only when I develop the theoretical methods further, and in particular when I derive practical information processing algorithms. I can promise these readers that they are in for some surprises.

I have wondered whether a better target audience would be quantum field theorists, who might be interested to read about an unusual application of (some of) the QFT methods that they are already familiar with. I guess that there are lots of researchers who are highly trained in QFT, who eventually end up doing research in an area where QFT is not used, but who would prefer to be doing research that is based on QFT.

Anyway, I now plan to write a few postings to explain some of the background research on information processing that leads to the QFT techniques that I describe in my paper (see here). This might alleviate some of the "QFT?! Is Luttrell mad?!" responses that I suspect might be lurking out there.

Update: I have now submitted my paper (see here) to the Journal of Machine Learning Research, which "provides an international forum for the electronic and paper publication of high-quality scholarly articles in all areas of machine learning. All published papers are freely available online." (quoted from their web site).

Problem uploading images to blogger.com

2005-11-27T16:34:00.000Z

Merde, merde, and thrice merde!

For some unknown reason blogger.com is still not accepting uploaded images, so I am unable to post any images here until that is sorted out. Maybe this problem is related to the comment about "network maintenance" on the Blogger Status page.

This pretty much makes it impossible for me to post anything meaningful, so this blog will be dormant until this problem is sorted out.

I am more than a little annoyed by this.

Update: My frustration is building to the point where I might start to host all of my images elsewhere, and to include links from my postings here.

Update: I have now discovered that the uploading problem was a 30 second timeout that prevented what would otherwise have been successful uploads from completing. For some reason this 30 second threshold was not exceeded for the first 10 or so images that I uploaded, but it was exceeded thereafter. Since I was attempting to upload uncompressed bitmap versions of my images, the solution was simple: compress-before-upload. This trick worked on my first attempt, so my earlier Discrete network dynamics. Part 1: Operator theory posting is now complete with its images. I can now bring this blog out of its dormant state.

A new kind of science

2005-11-16T21:19:00.000Z

A few years ago Stephen Wolfram published a book called A new kind of science (NKS). Both the man and the book cause a strong split in people's opinions. Some claim him to be a genius and others dismiss him as a megalomaniac crackpot. Some claim that the book represents the dawn of a new scientific era, whereas others dismiss it as a derivative work with nothing new to offer. As for me, I don't really pay much attention to what people say, because idle chatter is mostly heresay. I judge things by their demonstrable benefit, and for a book that means I judge it subjectively by the new ideas that it gives me.

I originally read the whole of NKS fairly quickly to get the gist of what it said. I already had many of its concepts on board, which helped this speed-reading along. Since then I have delved into selected areas of the book when I realised how the ideas that they held might be applied to my own work on self-organising networks. Usually, I use this book in "pick and mix" mode, where I mine it for concepts rather than complete solutions.

My subjective assessment of the book is that it is invaluable for me, because it has allowed me to enlarge the toolbox of scientific techniques that I use in my work. Objectively, I am sure that most (and perhaps all) of these ideas were already available somewhere in the literature, but then I am told that needles can be found in haystacks if you look hard enough. The key point is that a lot of interesting ideas are contained in the NKS book, and they are repeated many times just in case you don't get the message the first time. I certainly find that thinking in the NKS cellular automaton style gives me a usefully different viewpoint, which I can use to augment rather than inhibit my understanding.

I don't have much time for the scientific snobs who dismiss SW because of his personal and his scientific style. I think it all makes him a rather fascinating character.

The human connectome

2005-11-13T17:55:00.000Z

We had the human genome project, and now we have the human connectome project. In this week's New Scientist there is a short article entitled Connectome. I found an on-line paper entitled The Human Connectome: A Structural Description of the Human Brain whose abstract reads:

The connection matrix of the human brain (the human “connectome”) represents an indispensable foundation for basic and applied neurobiological research. However, the network of anatomical connections linking the neuronal elements of the human brain is still largely unknown. While some databases or collations of large-scale anatomical connection patterns exist for other mammalian species, there is currently no connection matrix of the human brain, nor is there a coordinated research effort to collect, archive, and disseminate this important information. We propose a research strategy to achieve this goal, and discuss its potential impact.

This project is much more realistic in its scope than the ridiculously premature Mission to build a simulated brain that I wrote about a while ago. Measuring the connection matrix of the human brain might seem to be mundane and rather like butterfly collecting, but it is essential to collect lots of data in order to constrain the imagination of the scientists who construct models of the brain; without such data we would not be doing science.

I wish them well in the success of this project. However, knowing the connection matrix does not imply that you understand the brain states that emerge from the corresponding network of neurons. It is not even clear that the connection matrix is a sufficient description of the network of interconnections between neurons. Even if you know the connection matrix, it does not tell you anything about the self-organisation of such a network of connections in the first place. Which aspects are genetically determined and which are the result of being driven by sensory inputs?

Are there as yet undiscovered universal principles governing such self-organisation? I'll bet there are.

Discrete network dynamics. Part 1: Operator theory

2005-11-10T19:42:00.000Z

This posting is a brief overview of my recent paper entitled "Discrete network dynamics. Part 1: Operator theory", which can be found in arXiv at cs.NE/0511027.

The basic idea is that an MCMC simulation (see a description of MCMC algorithms in a previous posting of mine here) of a joint probability Pr(x), where x is the joint state of an N-dimensional system (e.g. x_i is the state of the i^th node of an N-node network), generates a sequence of x's (i.e. x(1), x(2), ... , x(t), ...) that are sampled from Pr(x). x(t+1) is generated from x(t) by an operation that holds some of the components of x(t) fixed, whilst stochastically updating the rest of the components of x(t). The MCMC update operation is chosen so that if Pr(x(t)) has the correct joint probability then so also does Pr(x(t+1)). This was discussed in detail here.

The MCMC update operation is particularly simple if the state of only one of the nodes of the network is updated at a time, so that x(t+1) differs from x(t) in only one of its vector components. Let us assume that it is the i^th component that is updated, then MCMC update operation consists of two simpler operations:

Erase the state x_i. This is an unconditional erase operation, in which the state is erased with no memory of what it used to be.
Randomly rewrite the state x_i. This is a conditional rewrite operation, in which the state is drawn from the conditional probability Pr(x_i│x\x_i).

The diagram shows an MCMC update in a visually intuitive way for a 2-node network (i.e. N=2). Node 1 is at the top of the diagram, node 2 is at the bottom of the diagram, and time reads from left to right across the diagram. The initial state x₁ of node 1 is changed to final state x₁´ by the influence of the state x₂ of node 2 (which is itself unchanged in going from initial to final state). The solid lines from left to right indicate the evolution of the states of nodes 1 and 2. The vertical dashed line indicates the influence of the state of node 2 on the state of node 1, and the probability of the final state of node 1 is indicated as Pr(x₁´│x₂), which is memoryless because it does not depend on x₁.

The above diagram is a Feynman-like diagram describing the annihilation of the state of node 1, and then subsequent creation of a new state for node 1, and the "amplitude" for this process is actually a probability given by Pr(x₁´│x₂).

This identification allows the MCMC update operator to be written as

H_a ≡ ∑_i a_i† (∑_ja_j) (∑_kPr(i│k) b_k†b_k)

where a_i† is the creation operator for state i at node 1, b_k† is the creation operator for state k at node 2, b_k†b_k is the number operator for state k at node 2, ∑_kPr(i│k) b_k†b_k is the operator for computing the conditional probability factor that weights the MCMC update, and ∑_ja_j unconditionally annihilates the state at node 1.

Application of the MCMC update operator H_a automatically generates the correct probability-weighted ensemble of possible next states of the 2-node network in which the state of node 1 is updated. The full MCMC update operator is the sum of H_a+H_b, where H_b is obtained from H_a by interchanging the "a" and "b" operators (and appropriately changing the conditional probability factor). The Feynman-like diagram version of H_a+H_b is thus a sum of two diagrams as shown below.

The MCMC update operator correctly implements the 2-step MCMC update procedure described earlier. Each node of the network has a state with occupancy 1 that is erased (i.e. annhilated) during step 1 of the MCMC update to become the "vacuum" state with occupancy 0, and the state is rewritten (i.e. created) during step 2 of the MCMC update to become a state with occupancy 1 again. This update process is memoryless because its intermediate state is the "vacuum".

However, the MCMC update operator goes beyond the standard MCMC updates, because it can also be applied to initial states that have an occupancy of 2 or more. The algebra of the creation and annihilation operators automatically does this generalisation for you, and thus defines a unique generalisation of the MCMC algorithm for multiply occupied states of the network nodes.

The above discussion has focussed on a network with only 2 nodes. The generalisation to an N-node network is straightforward when the probability Pr(x) of the joint state of the network is expanded using the Hammersley-Clifford expansion, as is shown in my paper.

The structure of this MCMC algorithm is similar to a quantum field theory of bosons:

Each state of node i of the network can have a variable occupancy, which corresponds to each state of bosons of type i having a variable occupancy.
An MCMC update causes the multiply occupied state of node i of the network to change by using the neighbouring nodes to influence the hopping of an occupant from one state of node i to another state of node i, which corresponds to a boson of type i scattering from one state to another under the influence of bosons of various other types.

This completes the reformulation of MCMC algorithms using the language of creation and annihilation operators, and opens up a large number of possible lines of enquiry.

One particularly interesting consequence of multiple occupancy MCMC algorithms is self-organising networks, in which the state space of a multiply occupied network node can split into 2 or more smaller state spaces, each of which inherits some of the original node's multiple occupants, so that overall the original node splits into several daughter nodes. I will be saying much more about this later.

Discrete network dynamics series of papers

2005-11-07T22:22:00.000Z

I am now back after a quiet period during which I was writing my first paper in a forthcoming series of papers on "discrete network dynamics". This first paper is entitled "Discrete Network Dynamics. Part 1: Operator Theory", and I have just uploaded it to arXiv where it is available at cs.NE/0511027. I will be commenting in detail on this paper in due course.

The "discrete network dynamics" series of papers will be about the use of operator techniques borrowed from quantum field theory to implement Markov chain Monte Carlo algorithms, and the emphasis will be on the adaptive cluster expansion network (ACEnet) which is a particular type of self-organising network.

Where is this all going?

2005-10-23T23:35:00.000Z

You may well wonder where all of this maths is leading us. You will just have to be patient. I am creating the simplest path possible that short-circuits the route to my latest research work. Before long I will be publishing papers in arXiv, and then subsequently discussing them here. When that happens I hope that things will start to get more exciting.

Stochastic vector quantiser

2005-10-23T14:10:00.000Z

We can now generalise the basic self-organising network known as the vector quantiser by combining results from several earlier postings:

In Basic self-organising network: vector quantiser I described a basic type of self-organising network (SON) called a vector quantiser (VQ), which does two simultaneous jobs: Encoding - which takes each continuous-valued input vector x and use an encoder k(x) to map it to a discrete-valued code k, Decoding - which takes each discrete-valued code k and use a decoder x(k) to map it to a continuous-valued input x. This creation of mappings to and from new "representation" spaces is a defining feature of SONs, and the VQ is the simplest example using non-linear mappings that I know of.
In Vector quantiser simulation I included Mathematica code for simulating a VQ, which learnt to partition a 2-dimensional regions into "code cells".
In Bayes theorem I introduced Bayes theorem for manipulating joint probabilities. This is the key result that makes it possible to do useful computations with joint probabilities, without being constrained to those special cases that admit analytic solutions.
In Markov chain Monte Carlo sampling (MCMC) I illustrated how to use Bayes theorem to draw samples from a joint probability, which generates a Markov chain of samples that visits each joint state with a frequency that is proportional to its joint probablity, with the caveat that the sequence thus generates is correlated because it has a memory of its past history.

What do these results give you when they are folded together? The basic result is item 4 above on MCMC sampling joint probabilities. If several MCMC updates are applied to a joint state (x, k) to create the state sequence (?, ?) → (x, ?) → (x, k) → (x′, k), where the MCMC updates alternate between x and k spaces, then the encoding/decoding process that occurs in a VQ can be mimicked, giving the encode/decode loop x → k → x′ that I described in Basic self-organising network: vector quantiser. More generally, if the MCMC updates alternate randomly, then the same VQ encoding/decoding process occurs, but less efficiently.

This connection between VQ encoding/decoding and MCMC algorithms allows a stochastic generalisation of the VQ to be formulated. This is called a stochastic vector quantiser (SVQ), and its structure is shown in the diagram below.

where Pr(k│x) is the encoder's conditional probability over codes k given the input vector x, and Pr(x´│k) is the corresponding decoder's conditional probability.

Compare this diagram with the following two previous diagrams:

The basic VQ that I showed in Basic self-organising network: vector quantiser. The only difference is the notation that is used to describe the "encode" and "decode" blocks of the diagrams.
The first few updates of the MCMC simulation that I showed in Markov chain Monte Carlo sampling. Each pair of successive diagrams is potentially a stochastic encoding followed by a decoding, assuming that the MCMC algorithm happens to update the right hand space followed by the left hand space.

A slightly more appropriate version of the MCMC diagram would look like the diagram below, where a larger number of states has been used in each of the two spaces than before, and arrows have been drawn to show which space the MCMC algorithm happens to update at each step. In this case the first two steps behave like an SVQ encode/decode loop, because the arrows form the characteristic out-and-back form shown in the SVQ diagram above.

To encode you compute the encoder's conditional probability Pr(k│x), and to decode you then compute the decoder's conditional probability Pr(x´│k). Overall, this specifies the chain x → k → x´ leading from the original input vector, via the code, and then back to a reconstruction of the input vector. Each of the arrows in this chain is stochastic in an SVQ. This means that for each input vector x there is a whole ensemble of alternative possible codes k, each member of which is weighted by the corresponding conditional probability Pr(k│x), and one such member is randomly selected as the coded version of the input. Similarly, for each code k there is a whole ensemble of alternative possible reconstructions x´, each member of which is weighted by the corresponding conditional probability Pr(x´│k). This procedure is equivalent to two steps of an MCMC algorithm.

The SVQ generalisation of the Euclidean VQ objective function is

D = ∫dx Pr(x) ∑_k Pr(k│x) ∫dx´Pr(x´│k) ║x - x´║²

This may be interpreted thus:

The joint probability Pr(x, k, x´) of the chain x → k → x´ can be split up as Pr(x, k, x´) = Pr(x) Pr(k│x) Pr(x´│k).
║x - x´║² is the Euclidean distance between the original input vector and its reconstruction after passing along the chain x → k → x´.
The ∫dx Pr(x) ∑_k Pr(k│x) ∫dx´Pr(x´│k) (...) sums and integrates over all of the alternative choices of the chain x → k → x´.

By using Bayes theorem this objective function can be simplified to the following

D = 2 ∫dx Pr(x) ∑_k Pr(k│x) ║x - x´(k)║²

where x´(k) is defined as

x´(k) ≡ (∫dx Pr(x) Pr(k│x) x) / (∫dx Pr(x) Pr(k│x))

Compare these expressions with the results in Basic self-organising network: vector quantiser to see that the SVQ and the VQ are mathematically very similar, except that in an SVQ the encoder is stochastic because it is described by Pr(k│x). The overall factor of 2 in the SVQ objective function is not important; it comes from the symmetrical way that I defined D for an SVQ. The VQ is a special case of an SVQ where Pr(k│x) = δ_k,k(x).

Overall, an SVQ is the same as a VQ, except that there is now some "slack" in the choice of how to encode each input vector. Also, a computational structure that is equivalent to an SVQ is embedded within an MCMC simulation of the joint probability Pr(x, k). It turns out that the MCMC viewpoint is ultimately the most useful for making further generalisations of the VQ and SVQ self-organising networks.

One face, one neuron

2005-10-18T23:36:00.000Z

This month in Scientific American there is a News Scan article entitled One Face, One Neuron, which describes some interesting results (observed in several experimental subjects) in which there was a strong response by a single neuron to fairly abstract concepts. That is to say, when an experimental subject was shown various different things that were related to the same abstract concept, the same neuron fired in each case. It wasn't clear from the article what the rest of the neurons were doing, but there are rather a lot of them so it isn't possible to measure them all.

This observation is really significant, because it means that the brain is mapping a highly variable input onto an invariant response (at least, as far as one of the neurons is concerned), in which a single neuron fires reliably in response to a whole range of inputs. No doubt the neural dynamics that leads to this invariant mapping involves many neurons recurrently interacting with each other, with the net effect being the observed firing behaviour of the single neuron.

How is it that the neural dynamics in the brain can self-organise so that it creates these invariant mappings? Presumably they are something like fixed points (or limit cycles) of the dynamics. What properties of the external input are preserved at the output end of these mappings? In other words, what is the neural code used by the brain? Are the same properties of the external input preserved by different brains? If they are, presumably the detailed mappings are different in different brains. How much can the external input be varied whilst still being mapped to the same output? Is a few vague clues in the external input enough for the recurrent neural dynamics to home in on the appropriate output?

It would be really useful to have a general theory of such self-organising mappings in recurrent networks, wouldn't it?

Laughlin versus reductionism

2005-10-17T18:48:00.000Z

In a posting Laughlin vs. reductionism Luboš Motl chooses to shoot down Robert Laughlin's book "A Different Universe: Reinventing Physics from the Bottom Down" for its supposed attack on reductionism. I commented before on Reductionism versus emergentism, where I came out in favour of Laughlin's book, because it strikes me as being a fairly balanced account of the merits and disadvantages of reductionism and emergentism. However, my salary is no longer paid to me for doing fundamental physics, so presumably I have less to lose when Laughlin's book damns reductionism with faint praise.

More generally, it is very useful to think at many levels, all the way from deep underlying theories (i.e. reductionism) up to phenomenological descriptions (i.e. emergentism), because useful science can be done at all of these levels, and usually insight at one level can help progress to be made at another level, although this isn't guaranteed.

As I said in Reductionism versus emergentism, my hope is to use self-organising networks to address the relationship between reductionism and emergentism, and "if it all goes to plan then reductionism will emerge from emergentism by a process of self-organisation".

In information processing I certainly do not want to have to think in terms of individual binary digits the whole time. I want to build software objects that have well-defined behaviour at a much higher level, and to be able to ignore the detailed internal workings of these objects, and to deal instead only with their externally exposed properties. However, at the same time, I want to be able to interrogate those higher level properties to discover their internal dynamics. This is what a self-organising network will allow me to do.

You certainly can't do useful (read "macroscopic") self-organising information processing without bumping straight into emergent properties.

Markov chain Monte Carlo sampling

2005-10-13T20:26:00.000Z

In a previous posting I explained Bayes theorem for splitting up joint probabilities Pr(x,y) into component pieces (either Pr(x│y) Pr(y) or Pr(y│x) Pr(x)), which leads onto a very neat way of drawing sample pairs of vectors (x,y) so that they have the correct joint probability Pr(x,y). This is called Markov chain Monte Carlo (MCMC) sampling.

Firstly, notice that the pair of vectors (x,y) forms a single (higher-dimensional) vector. In the description below this partitioning of the single vector into a pair of vectors (x,y) is done in whatever way is convenient. This will be explained below.

Start off by supposing that someone hands you a pair (x,y) that is known to have joint probability Pr(x,y). You can use this to generate another pair (x,y) that also has joint probability Pr(x,y). Here is how you do it:

Use Bayes theorem to split Pr(x,y) as Pr(x,y) = Pr(x│y) Pr(y), where Pr(y) ≡ ∫dx Pr(x,y). This tells you that Pr(x│y) = Pr(x,y) / ∫dx Pr(x,y) which will be used below.
Draw a sample vector (call it x´) from the Pr(x│y) computed above, and make this the new value of x. Note that you do not need to know Pr(y) to draw this sample. Here I assume that it is easy to draw an x-sample from Pr(x│y) (e.g. x is low-dimensional) but it is difficult to draw an (x,y)-sample from Pr(x,y) (e.g. (x,y) is high-dimensional) which is the sampling problem that we want to avoid.
The joint state is now (x´,y). Its joint probability is Pr(x´│y) Pr(y), where Pr(x´│y) has the same functional dependence on x´ as Pr(x│y) has on x, by construction.
Use Bayes theorem to join these together to obtain Pr(x´,y) = Pr(x│y) Pr(y), where Pr(x´,y) has the same functional dependence on x´ as Pr(x,y) has on x, by construction.

The overall effect of the above steps is that (x,y) becomes (x´,y), and the functional form of the joint probability is unchanged by this operation. Excellent! That is exactly what we wanted to do. We now have two pairs of vectors (x,y) becomes (x´,y) sampled from Pr(x,y). The only downside is that the value of y is the same in both pairs of vectors, so they must be strongly correlated with each other.

The partitioning of the whole vector into a pair of smaller vectors (x,y) can be done in any way, and as long as it is easy to draw a sample of x from Pr(x│y) then another (x,y) (different x, same y) can be generated as described above. This process can be iterated (choosing a different partitioning of the whole vector at each iteration) to generate a whole sequence (or Markov chain) of vector samples (hence the name "Markov chain Monte Carlo" sampling) all of which have the correct joint probability. The main caveat is that the sequence is correlated, because each vector in the sequence has a "memory" of the past history of the sequence.

Note that the above algorithm does not work if the initial pair of vectors does not have joint probability Pr(x,y). However, under fairly mild assumptions (i.e. ergodicity), the algorithm will generate a sequence of vectors whose joint probability settles down to Pr(x,y) after an initial convergence period, after which the assumptions of the above algorithm are satisfied.

The diagrams below show how a typical MCMC sequence building up. This uses the same Pr(x,y) and diagrammatic notation as was used in my posting on Bayes theorem here, and was in fact how I generated the diagrams there. A different random seed has been used here. Each of x and y has 3 possible states, so (x,y) has 9 (=3*3) possible joint states.

The first diagram shows the first 6 steps of the MCMC sequence, where the initial state (3,2) is at the top left, and successive states are shown in the graphics as read from left to right then top to bottom. After 1 MCMC update the state is unchanged (that is the draw of the random numbers), then after 2 MCMC updates the y part of the state updates so that the state is (3,3), then at the next step the x part of the state updates so that the state is (2,3), then the y part of the state updates so that the state is (2,1), then the next update can't be inferred from the diagram because it repeats a state that occurred earlier. The source of the correlations between successive MCMC samples is clear because each update moves only one end of the line in the graphic.

The diagram below shows the same as the diagram above except that 25 MCMC updates elapse between each graphic. Also, for visualisation purposes, the end points of each line representing a joint state are vertically jiggled a little bit so that they don't all fall on top of each other.

This MCMC approach to sampling is very powerful, and with some ingenuity it can be used to draw samples from any joint probability, but always with the caveat that the sequence is correlated.

Bayes theorem

2005-10-12T20:05:00.000Z

Thomas Bayes (1702-1761)

In probability theory Thomas Bayes is legendary for his theorem (known as Bayes theorem). which can be written thus:

Pr(x,y) = Pr(x│y) Pr(y) = Pr(y│x) Pr(x)

Pr(x) ≡ ∫dy Pr(x,y)
Pr(y) ≡ ∫dx Pr(x,y)

where Pr(x,y) is the joint probability of a pair of vectors x and y, Pr(x) and Pr(y) are marginal probabilities of the single vectors x or y (respectively), and Pr(x│y) and Pr(y│x) are conditional probabilities defined from the above as

Pr(x│y) ≡ Pr(x,y) / ∫dx Pr(x,y)
Pr(y│x) ≡ Pr(x,y) / ∫dy Pr(x,y)

These relationships can be intuitively explained using diagrams. Thus choose state spaces for x and y that each have 3 discrete states, so the total number of joint states is 9. Choose a 3 by 3 matrix of joint probabilities Pr(x,y), and from Pr(x,y) independently draw 150 samples of (x,y) at random.

Now represent each of these samples in the diagram below as a line joining one of the 3 bins on the left (the x-bins) to one of the 3 bins on the right (the y-bins). Vertically jiggle the positions of the end points of the lines so that they don't accidentally fall on top of each other. The number of lines (joining any pair of bins) in this diagram represents the corresponding element of the joint probability Pr(x,y), for each of the 9 (=3*3) possible pairs of bins.

Now display in the diagrams below the contributions that are anchored in each of the 6 (=3+3) possible bins. The number of lines (joining any pair of bins) represents the conditional probability Pr(y│x) (top row) and Pr(x│y) (bottom row). Note that the total number of lines in each diagram represents the corresponding marginal probability, i.e. Pr(x) (top row) and Pr(y) (bottom row).

These diagrams give a neat visual summary of the various probability quantities that are interrelated by Bayes theorem. They will provide neat ways of visualising various results that I will describe in future postings to this blog.

Bayesian purists will object to the above diagrams because they rely on drawing a set of samples S from the joint probability P(x,y), and then using S as if it was actually the same object as P(x,y). Of course, they are different objects, but for the purposes of visualisation S is very useful. You can always "fill in the gaps" in your mind's eye.

Mission to build a simulated brain

2005-10-06T22:54:00.000Z

In New Scientist a while ago there was an article entitled Mission to build a simulated brain begins which describes "An effort to create the first computer simulation of the entire human brain, right down to the molecular level...". It goes on to say "The hope is that the virtual brain will help shed light on some aspects of human cognition, such as perception, memory and perhaps even consciousness", and so on.

"...simulation of the entire human brain"?!!

That's rather a lot of neurons, and a mind-boggling number of connections. And that's not even going down to the molecular level. The state of the art is very limited compared to the goals of this project. I assume that the report is slightly inaccurate.
For instance, there are detailed computational models of how neurons function, and how they interact in small assemblies; there is the NEURON software for running these simulations. At a much higher level there are also general architectual models of whole regions of the brain.
In a few cases there are models that span several scales all the way from the bottom level to a fairly high level. I am thinking in particular of the visual cortex where we have the luxury of addressing the brain directly via the retina (which is effectively a layer of brain tissue). This has led to a very good (relative to other areas of the brain) neural model of visual processing in the brain.

"...and perhaps even consciousness"?!!

When I hear the "C" word I reach for my gun! People routinely use the "C" word to inject an air of mystery and importance into what they are saying. The fact is that it is a non-word that is used by people who haven't seriously reflected on what goes on inside their heads.
One book (amongst many) that I have found very insightful on this issue is The Artful Universe Expanded by John Barrow, in which he lucidly explains how evolution ensures that the universe imprints itself on the way that we we think. This means that the thing that we think with is not as free thinking as we would like to believe that it is. Is it at all surprising that we feel as if there is an inner light (call it "consciousness" if you want)?
Isn't it obvious that evolution ensures that you (whatever you are, human, fish, ant, or whatever) have a sense of "self" to encourage you to survive and reproduce, or have a sense of "host" to make you sacrifice yourself to save the nest? There will be "degrees" of "self" according to the "amount" of "processing" that is used to "implement" it. Yes, there are inverted commas everywhere because the terminology is not precisely defined.

What sort of brain studies should be given more prominence?

There is a lot of research going on near the bottom level, such as modelling neural chemical processes, modelling the dynamics of membrane potentials, modelling the interaction of small assemblies of neurons, etc. This is all very good reductionist work that potentially will lead to a deeper understanding.

However, I can't see much work going on that studies the theory of low-level brain-like processing, although there is a lot of neural modelling work. What do I mean by that? Brain-like processing is massively parallel, which needs its own special kind of "algorithm" that can be distributed across a large number of small interconnected processors. For really large parallel systems (e.g. brains) you can't go in and individually program every processor, but you can envisage the processors having inbuilt behaviours (i.e. a bootstrap program) that allow them to sort out their collective behaviour (i.e. self-organise) to do something macroscopically useful. We certainly need a lot more work on the theory of this type of massively parallel self-organising system.

There is a vast amount of research into what is called "neural networks", but which is nothing of the sort. As with the "C" word above, the "NN" phrase is used to guild otherwise rather mediocre research to make it seem more sophisticated than it is. A better phrase to describe most of this research is "non-linear adaptive filtering". The small subset of "NN" research that uses discrete firing events, rather than firing rates, is much better qualified to be called "NN".

There is the important distinction between supervised and unsupervised training:

Supervised training is usually used to guide an adaptive filter so that it approximates an externally specified output. From the point of view of brain-like processing this is not a very interesting type of adaptation.
Unsupervised training is much more interesting because it does not require an output to be externally specified, so the adaptive filter must discover for itself something "interesting" about its input; this is like answering an open-ended question, which is much more challenging than a question with a known answer. From the point of view of brain-like processing this is a very interesting type of adaptation.

Too much time is spent on supervised training by people doing what they think is true "NN" research. They are kidding themselves. How do they expect very large networks to be trained when all the external supervisor can do is to guide the network outputs? Is supervised training really going to help the deep inner workings of the network to learn anything useful? Wouldn't it be much better to distribute throughout the network the ability to discover "interesting" structure? Doesn't this sound rather like what unsupervised training is aiming to do anyway?

In Mission to build a simulated brain begins I want to see more theoretical work, especially on abstract brain-like processing and (more specifically) unsupervised training of neural networks that use discrete firing events, which would then guide the modelling work that they hope to do anyway. To understand what a large network simulation is doing you need a theory that is formulated at an appropriate level. It is not always a good idea to drill down to the bottom level of modelling (see my comments on reductionism versus emergentism).

Whither this blog?

2005-10-05T17:01:00.000Z

I have had look at the various postings that I have made thus far and notice that, although they are "on topic", they are quite variable in their style. Some verge on seeming to be philosophical (e.g. here) whilst others use a fairly demanding level of maths/software (e.g. here), including several future postings that I currently have in draft form. I even had a comment by private email that their "brain started to explode half way through the VQ article"! I had rather hoped I would get all my comments directly to the blog; there seems to be rather a shortage of them. I seem to be talking to myself!

I operate in any (all, some, or none) of these modes of expression, and my writing and maths tends to show it. It will take a while for me to converge on an optimum approach to posting on this blog, but I suspect it will always mix together different styles. I will try to make the maths as self-evident as possible. After all, I don't think you have really understood a piece of maths until it you can explain it in such an intuitively obvious way that people ask why they are paying you do do something so trivial.

I will post software written in Mathematica to illustrate the points I am making. Maybe some (most?) people don't like my choice of computer language, but I have given my reasons for using Mathematica here. It blurs the distinction between maths and algorithms which I think is a big step forwards. This is one of the main purposes of Stephen Wolfram's New Kind of Science.

I don't think I have yet started to put in enough links to the rest of the world, so I can hardly expect other people to link to me (they haven't yet, as far as I know!). I even tried to set up a trackback from one of my earlier postings here to an arXiv paper of mine here. The trackback was received (it appeared on arXiv's "recent trackbacks" page) , but it never got attached to my paper. I guess the arXiv administrators spiked it because it was a self-comment. That's OK, and it is the appropriate policy for arXiv.

I have had a poke around blogspace and I can't find anyone at all who is posting in the area of self-organising networks (or even self-organizing networks!). There are blogs which have to do with self-organising "social" networks, but that isn't what this blog is about. So how do you start off a blogging community in a new subject area? My own areas of expertise span quantum physics as well as self-organising networks, and I intend to show just how inter-related these two areas are in future postings, so at some point my postings will start to look much more like quantum physics. I hope things will start to interest a lot more people then.

Update: The above arXiv trackback eventually appeared a little over a week after I pinged arXiv. Because this was my first such trackback I must have triggered the manual part of the "semi-automated editorial process that approves trackbacks for display". I pinged arXiv with some more trackbacks, and this time they appeared straight away. So it seems that I have been judged to be "worthy". I will use the privilege wisely.

Vector quantiser simulation

2005-09-30T18:19:00.000Z

The aim here is to show how to write the code to implement the training of a vector quantiser (VQ) as described in my earlier posting here. The code is implemented as a discrete time dynamical system (DTDS) as described in another of my earlier postings here.

Call in some graphics packages.

Needs["Graphics`Graphics`"];
Needs["Graphics`MultipleListPlot`"];
Needs["DiscreteMath`ComputationalGeometry`"];

Define the size of the training set (i.e. the number of vectors sampled from the input probability density) and the number of code indices to use (i.e. the size of the "code book").

numtrain=100;
numcodes=20;

Define a function nn to compute the index of the vector (in a list of reconstruction vectors r) that lies closest (i.e. is the "nearest neighbour") to an input vector x. This is the encoded version of the input vector.

nn[x_,r_]:=Position[#,Min[#]]&[Map[#.#&[x-#]&,r]][[1,1]];

Read this definition from the inside out:

Map[#.#&[x-#]&,r] computes the list of squared distances between the input vector x and each vector in the list of vectors r (the "code book").
Position[#,Min[#]]&[...][[1,1]] computes the position in the list of the smallest of the above squared distances.

Define a function y to build a list of the codes corresponding to the whole set of training data at time step t.

y[t_]:=(y[t]=Map[nn[#,r[t]]&,data[t]]);

Read this definition from the inside out:

data[t] is a function that returns the training set at time t.
Map[nn[#,r[t]]&,data[t]] computes the list of encoded versions of all of the input vectors in the training set.
y[t]=... memorises the result of the above step.

Define a function datay to build a list of the training data that maps to each code at time step t.

datay[t_]:=Table[Cases[Transpose[{data[t],y[t]}],{x_,i}:>x],{i,numcodes}];

Read this definition from the inside out:

Transpose[{data[t],y[t]}] builds a list of pairs of corresponding input vectors and their codes.
Cases[...,{x_,i}:>x] extracts the subset of data vectors that are paired with code i.
Table[...,{i,numcodes}] builds a list of the above subsets for all codes.

Define a function r to compute the updated list of reconstruction vectors at time step t.

r[t_]:=(r[t]=Map[If[Length[#]>0,Apply[Plus,#]/Length[#],Table[Random[],{2}]]&,datay[t-1]]);

Read this definition from the inside out:

Apply[Plus,#]/Length[#]&[datay[t-1]] computes the updated list of reconstruction vectors from the list of subsets of training data that maps to each code at time step t-1.
If[Length[#]>0,...,Table[Random[],{2}]] protects the above code from a possible error codition when the length of a sublist is zero (i.e. none of the training vectors map to a particular code).
r[t]=... memorises the result of the above step.

Define the value that the r function returns at time step 0. This initialises the reconstruction vectors.

r[0]=Table[Random[],{numcodes},{2}];

Define a function data that returns the set of training data at time step t. This is a fixed set (for all time steps) of 2-dimensional vectors uniformly distributed in the unit square.

data[t_]=Table[Random[],{numtrain},{2}];

Define the number of training updates. Typically, this VQ converges in far fewer updates than the 20 chosen.

numupdates=20;

Display the training of the reconstruction vectors.

vqgraphics=Table[MultipleListPlot[data[t],r[t],PlotRange->{{0,1},{0,1}},AspectRatio->1,Frame->True,SymbolStyle->{RGBColor[0,0,1],RGBColor[1,0,0]},SymbolShape->{PlotSymbol[Triangle],PlotSymbol[Box]},PlotLabel->"Step "<>ToString[t],FrameTicks->False],{t,0,numupdates}];

[GRAPHICS OMITTED]

Display the encoding cells corresponding to the reconstruction vectors.

codecellgraphics=Table[DiagramPlot[r[t],PlotRange->{{0,1},{0,1}},LabelPoints->False,PlotLabel->"Step "<>ToString[t],Frame->True,FrameTicks->False],{t,0,numupdates}];

[GRAPHICS OMITTED]

Display all of the graphics together.

MapThread[Show[#1,#2]&,{codecellgraphics,vqgraphics}];

[GRAPHICS OMITTED]

Display the first few update steps to show the convergence to an optimum VQ. This example has been chosen deliberately so that it converges fast. It usually takes more than 3 update steps for the optimisation of this VQ to converge.

DisplayTogetherArray[Partition[Take[MapThread[Show[#1,#2]&,{codecellgraphics,vqgraphics}],4],2]];

Because this DTDS implementation of the training of a VQ memorises the values returned by the y and r functions you need to erase these values using y=. and r=. before retraining the VQ.

Basic self-organising network: vector quantiser

2005-09-29T19:44:00.000Z

The simplest self-organising network (SON) that computes non-linear transformations of data is the vector quantiser (VQ).

A VQ does two simultaneous jobs:

Encoding: take each continuous-valued input vector x and use an encoder k(x) to map it to a discrete-valued code k.
Decoding: take each discrete-valued code k and use a decoder x(k) to map it to a continuous-valued input x.

Thus a VQ defines a pair of oppositely directed mappings x → k (i.e. k(x)) and k → x (i.e. x(k)). The "quality" of the encoding may be judged by going once round the encode/decode loop thus x → k → x′, and then comparing the original input vector x with its reconstruction x′. A good VQ will have a small reconstruction error, and to achieve this the two mappings k(x) and x(k) must work together harmoniously.

Now let me explicitly show how to optimise a VQ.

A simple measure of the "goodness" of a VQ is a "Euclidean" objective function D that measures the average squared reconstruction error, which is defined as

D = ∫dx Pr(x)║x - x(k(x))║²

where the various pieces have the following interpretation:

x(k(x)) encodes (and then decodes) an input vector x to produce a reconstruction.
x - x(k(x)) computes the difference between the original input vector and its reconstruction.
║x - x(k(x))║² computes the squared length of the above difference vector.
∫dx Pr(x)║...║² averages the average of the above squared length over input vectors x with probability density Pr(x).

Minimisation of this objective function with respect to the two mappings k(x) and x(k) optimises the VQ.

By inspection, the optimum k(x) is given by

k(x) = argmin_k║x - x(k)║²

Differentiate D with respect to x(k)

∂D/∂x(k) = -2∫dx Pr(x) δ_k,k(x)(x - x(k))

where δ_k,k(x) is a Kronecker delta. The optimum x(k) satisfies ∂D/∂x(k) = 0 (strictly, this is a necessary but not sufficient condition to locate the global optimum) which is given by

x(k) = (∫dx Pr(x) δ_k,k(x)x) / (∫dx Pr(x) δ_k,k(x))

This pair of coupled non-linear equations for the optimum mappings k(x) and x(k) can be solved iteratively.

Randomly initialise the x(k) for k = 1, 2, ..., m where m is the size of the "code book" of x(k) vectors to be optimised.
Compute the right hand side of the x(k) = (...) / (...) equation, using the k(x) = ... equation to compute k(x) whenever it is needed. The integrals ∫dx Pr(x) (...) are approximated using a finite-sized set of input vectors x (normally called the "training set").
The result for (...) / (...) from step 2 above will in general not be the same as the previously assigned values for the x(k). The resolution of this is to overwrite the previous values of the x(k) with the newly computed (...) / (...) from step 2 above, and to iterate this process.
When the x(k) have settled down so that successive iterations give (approximately) the same result the optimisation has converged to a minimum of the objective function. Note that this is guaranteed to be a local minimum, but not guaranteed to be a global minimum.

Why is a VQ a SON?

The encoder and decoder pair of mappings k(x) and x(k) bidirectionally connect two spaces (x-space and k-space) thus x ↔ k. The encode/decode loop x → k → x′ contains all the places that k appears, i.e. mapping k(x), k-space, and mapping x(k). The structure of this encode/decode loop is determined entirely by the minimisation of an objective function, and the term "self-organisation" is used to describe the optimisation process that creates the loop x → k → x′. As a side effect of the creation of this encode/decode loop a new space (i.e. k-space) is created that is able to "represent" states in x-space.

This creation of mappings to and from new "representation" spaces is a defining feature of SONs, and the VQ is the simplest example using non-linear mappings that I know of. If the discrete-valued k is replaced by a continuous-valued k, or more generally a vector k, then using a Euclidean objective function the optimum mappings k(x) and x(k) are linear (this is "principal components analysis", or PCA). Note that networks of linear mappings can build only linear mappings, whereas networks of non-linear mappings can build all mappings. It is very convenient that merely using a discrete-valued (rather than a continuous-valued) k or k leads to the useful non-linearity found in a VQ.

This use of discrete-valued quantities turns out to absolutely crucial for building a generalised theory of SONs. I will repeatedly return to this theme in the future.

Quantum mechanics

2005-09-29T00:22:00.000Z

I have always loved this cartoon which I saw in an old copy of Private Eye. I know it's not about self-organising networks (SON), but QM runs deep in my veins so I thought I would share it.

Actually, SONs and QM are more closely related than you might imagine; I will say more about that in the future.

Discrete time dynamical systems

2005-09-25T15:22:00.000Z

What is a discrete time dynamical system (DTDS)?

A DTDS is a dynamical system that evolves its state in discrete time steps, rather than through continuous evolution as is usually the case. By choosing a small enough time step a DTDS can approximate a continuous-time dynamical system. All algorithms can be formulated in the language of DTDS, because algorithms are stepwise procedures whose steps can be implemented as individual DTDS time steps. An algorithm running on a piece of hardware is nothing more than a set of rules telling that hardware how to update its state at each tick of the clock. This idea generalises to multiple pieces of hardware with independent clocks.

So DTDS are really useful. How can they be neatly implemented in software?

DTDS are very easy to implement in Mathematica. The archetypal DTDS is a cellular automaton, and where the "universe" consists of an array of discrete-valued cells, and the "laws of physics" consist of a set of cell update rules. A well known example of a cellular automaton is Conway's "Game of Life". More generally, the states of the cells can be anything you want (discrete-valued or continuous-valued), and the update rules can be implemented as any update algorithm you want to apply to the current state of the "universe" of cells. Mathematica has been designed with the simulation of cellular automata in mind, which is why DTDS are very easy to implement in Mathematica.

The Lorenz attractor is a good example to illustrate the implementation of a DTDS in Mathematica.

Initialise a pair of constants. The value of e controls the size of the discrete steps used by the DTDS version of the Lorentz equations to approximate the continuous version of the Lorenz equations.

e=0.013;
r=28;

Define the initial conditions.

x[0]={0.1,0.1,10.0};

Define the Lorenz equations.

x[t_]:=x[t]=
{
  x[t-1][[1]]+10e(x[t-1][[2]]-x[t-1][[1]]),
  x[t-1][[2]]+e(r x[t-1][[1]]-x[t-1][[1]]x[t-1][[3]]-x[t-1][[2]]),
  x[t-1][[3]]+e(x[t-1][[1]]x[t-1][[2]]-(8x[t-1][[3]])/3)
};

The x[t_]:=x[t]=... construct is Mathematica's way of implementing dynamic programming, where the result of evaluating the right hand side of the Lorenz equations is "memorised" using x[t]=..., and then x[t_]:=... can subsequently be used to retrieve this memorised value. This dynamical programming trick ensures that when going from t-1 to t the DTDS memorises its updated state x[t], so that it never needs to recompute x[t].

Call in a graphics package.

Needs["Graphics`Graphics3D`"];

Plot the Lorenz attractor.

ScatterPlot3D[Table[x[t],{t,0,1000}],PlotJoined->True,AspectRatio->1];

Although {x[1],x[2],...,x[1000]} have not actually been evaluated prior to evaluating ScatterPlot3D[...], their evaluation is then forced by evaluating Table[x[t],{t,0,1000}]. In effect the evolution of the DTDS happens as a side effect of asking for its evolution to be plotted. The memorisation of intermediate results using the x[t_]:=x[t]=... construct then ensures that all of {x[0],x[1],x[2],...,x[1000]} are available for immediate reuse, and do not need to be recomputed.

This memorisation of results means that if you want to restart the computation using different initial conditions x[0], then you have to explicitly erase the previously computed values {x[1],x[2],...,x[1000]} otherwise they will not be recomputed based on the new initial condition. An approach that avoids the need to erase values is to enforce the new initial condition on x[1001], and then to carry the computations forwards from there as {x[1002],x[1003],...}. I prefer this latter method because it avoids doing what is effectively a backwards jump in time.

Tag: Mathematica

Including maths in blog postings

2005-09-25T13:00:00.000Z

In the not too distant future it should be very easy to include maths on web pages in a way that is understood by all web browsers. It is certainly possible to do this right now, but maths is very definitely a second class citizen as far as web pages are concerned.

The technology that helps us to include maths (and other structured objects) on web pages is XML (eXtensible Mark-up Language) which is like a very fancy version of the HTML that we all know and love. I have been tracking the development of XML with interest for many years.

MathML is one of the mark-up languages that has been defined using XML, and its use in blogs has been frequently discussed by Jacques Distler in his blog here. However, I am not aware of any shrink-wrapped solutions to the problem of blogging with MathML. It seems to always require too much hacking around with "utilities", which is something I could do but am too lazy to bother with.

MathML has two features that I very much like:

It explicitly represents the full structure of mathematical expressions. This means that it is not a snapshot of the finished equation, but is an algorithmic description of how to construct the equation, keeping the interrelationship between its various parts intact.
The maths is part of the web page itself, and is not a set of embedded images (called in from hundreds of small image files) as has been the case in the past (e.g. LaTeX2HTML, Mathematica's "Save as HTML", etc).

Currently few browsers understand MathML directly (e.g. Internet Explorer needs the free MathPlayer plug-in), and even then they do not necessarily display the maths very well. This technology is still not mature.

I particularly like MathML (and more generally XML) because its design allows it to be easily imported/exported to/from Mathematica. The reason for this ease of communication is that the internal representation used by Mathematica is essentially the same as XML.

Mathematica also offers another less pretty way of including maths on web pages, which also preserves the structure of the maths in the same way that MathML does. Thus you can use Mathematica InputForm to write out maths in a 1-dimensional notation. For instance, Sin[x]==Integrate[Cos[x],x] has the obvious meaning, and it will evaluate to True in Mathematica. This approach generalises to arbitrarily complicated expressions but it can become rather "wordy", so careful indenting to highlight the structure of expressions is a good idea.

The use of MathML has not yet become widely enough acknowledged that all web software knows how to display it. For instance, the blog editing software I am using (see www.blogger.com) doesn't understand MathML (or, at least, I can't find a way of doing it). So I will limit myself to using Mathematica InputForm for now in my blog postings.

Functional versus procedural programming

2005-09-25T02:00:00.000Z

The "functional programming" style that I describe here is not the purist's version of functional programming, where assignment of results to variables does not occur. I have a freer interpretation of the term "functional programming" which is explained by the physical analogy below.

The relationship between functional and procedural programming is succinctly explained by using a physical analogy. Space-time is 4-dimensional and it contains a copy of the 3 spatial dimensions for each and every possible time instant. At each time instant there will be fields recorded throughout the 3-dimensional space, and the evolution of these fields forwards to the next time instant will be governed by whatever laws apply to those fields.

The two styles of programming may then be described thus:

Functional programming is the evolution of the fields so that they progressively fill up successive 3-dimensional slices of the 4-dimensional space-time.
Procedural programming is the same as functional programming except that at each time instant the 3-dimensional slice containing the evolved copy of the fields overwites the 3-dimensional slice containing the old copy of the fields.

Thus procedural programming reuses storage whereas functional programming does not. A procedural program operates on the state of the world and updates it in place, whereas functional programming makes a copy which it then updates.

A key advantage of functional programming is that the causal chain of updates is laid out explicitly so that an "audit trail" of what has happened during the updates is recorded, whereas in procedural programming this record is overwritten. This means that when a functional program needs to make use of the state of a particular variable at a particular point in time then that state is guaranteed to be available, whereas in a procedural program there is always the danger that the value has been overwritten.

In Mathematica a concrete example of this is as follows:

negativeQ[x_]:=x<0;
f[0]=0;
g[0]=1;
f[t_?negativeQ]:=0;
g[t_?negativeQ]:=0;
f[t_]:=f[t-1]-g[t-1];
g[t_]:=g[t-1]-f[t-2];

where the state of the world at time t is {f[t],g[t]} which depends on the state at the previous two time instants t-1 and t-2. This dependence on various past states is handled completely automatically in functional programming, whereas in procedural programming the overwriting of past states must be carefully buffered in order to ensure that the state at the previous two time instant is available. Clearly, this is a trivial example, but the principle generalises to cases where functional programming is enormously more convenient than procedural programming.

Excessive memory usage by functional programs can be avoided by adopting two strategies:

Do as much computation as possible between each time step, because intermediate results that are not assigned to variables are not permanently recorded. The garbage collector will take care of this temporary memory usage.
Explicitly erase variables that are no longer required. In effect this creates blank areas in the "audit trail" where parts of the causal chain of updates are "shredded".

Functional programming is a very natural way of writing out discretised evolution equations (as illustrated above). For instance, cellular automata have a completely natural formulation in the functional programming style. More generally, any discretised version of a differential equation can be written out easily in the functional programming style. The key advantage over procedural programming is that you don't need to worry about buffering the past states of the world because they are always available, at least until you erase them.

Functional programming should come naturally to anyone who has been exposed to the space-time way of thinking in physics, where the physicist surveys the whole 4-dimensional record of the world, and thinks in terms of complete histories (i.e. "audit trails").

Mathematica

2005-09-24T20:00:00.000Z

On www.wolfram.com/products/mathematica it says Mathematica is "The Way the World Calculates". That is sales blurb so I'll allow them a little exaggeration.

It then goes on to say:

"From simple calculator operations to large-scale programming and interactive-document preparation, Mathematica is the tool of choice at the frontiers of scientific research, in engineering analysis and modeling, in technical education from high school to graduate school, and wherever quantitative methods are used."

That is is bit more restrained, and I imagine it is not too far from the truth.

I have been a long-time user of Mathematica since version 1 was released in 1988, and prior to that circa 1980 (when I was doing my PhD on QCD) I used SMP which was the direct ancestor of Mathematica. I cannot exaggerate how much Mathematica has influenced me. It was immediately clear right from version 1 that here was something really new and potentially useful. I say "potentially" because for many years (and versions) I was tantalised by what Mathematica could do in principle, but I was disappointed by its slow compute speed which was a relic of its roots in symbolic algebra. All of these problems have now gone away, and Mathematica is my main tool for technical computing of all sorts, including computationally challenging problems such as image processing. I can do everything I want within one environment, so my "laboratory notebook" is now a hyperlinked web of notebooks containing elements such as text, graphics, maths, software, etc. Apart from idle jottings and scribbles, I have not kept a paper notebook since around 2000. There are no artificial boundaries between the different types of element in Mathematica notebooks which gives me an enormous efficiency advantage over people who don't use Mathematica.

I no longer think of Mathematica as a computer language. It is actually a notation that extends standard mathematical notation into the world of algorithms. Loosely speaking, equations and algorithms are now the same thing for me, because Mathematica is what "breathes the fire into the equations".

I might sound as if I am evangelising about Mathematica, but I am not. I have heard people complain about its price, but that is false economy. It currently costs around £1,600 for a commercial license, much cheaper for teachers, and extremely cheap for students. Based on its productivity and the amount of time you save it pays for itself very quickly.

However, there is a downside. The learning curve for Mathematica is long, especially for people who have used only procedural programming languages (e.g. Fortran, Basic, C++, Matlab, etc) because you have to make a mental shift to the functional programming style. However, these problems are alleviated by the extremely logical and unified structure of Mathematica.

There is another downside that I do find irritating. You need a full Mathematica installation on any computer on which you want to run software that you have written using Mathematica. This means that it is much more difficult to get non-Mathematica users to pay attention to what you are doing than it would otherwise be. Currently it is not possible for you to wrap your software in a standalone EXE. There are various translators that will convert Mathematica to other languages, but they impose strong constraints on what Mathematica constructs you are allowed to use; I have found them to be useless for serious work.

There is a Mathematica newsgroup at comp.soft-sys.math.mathematica where world experts hang out to solve your every Mathematica problem.

I intend to use Mathematica for any code that I might publish in this blog. I will try to ensure that the code can be read as pseudocode by non-Mathematica users, though I will be programming functionally rather than dysfunctionally.

Tag: Mathematica

My online papers

2005-09-23T16:12:00.000Z

I have a few papers published in arXiv:

arXiv.org/cs.LG/0410036: Self-Organised Factorial Encoding of a Toroidal Manifold
arXiv.org/cs.NE/0410020: Adaptive Cluster Expansion (ACE): A Hierarchical Bayesian Network
arXiv.org/cs.NE/0408050: Invariant Stochastic Encoders
arXiv.org/cs.NE/0408049: Using Stochastic Encoders to Discover Structure in Data
arXiv.org/cs.NE/0406017: Using Self-Organising Mappings to Learn the Structure of Data Manifolds

I also have an archive of my Crown Copyright publications at www.luttrell.org.uk/papers.

Most of my papers are relevant in some way to the field of self-organising networks.

Tag: arXiv

Reductionism versus emergentism

2005-09-22T23:14:00.000Z

The issue of reductionism versus emergentism amounts to whether you model your experimental observations in terms of underlying causes (this is reductionism), or whether you directly model the experimental observations in terms of themselves (this is emergentism). There are "wars" waged between the factions that support one or the other approach, with the reductionists being accused of being "coldly scientific", and the emergentists accused of being "vague and mystical". I think this polarisation of attitudes is silly; it seems that people simply like to be partisan and to spoil for a fight.

A concrete example from physics is the modelling of experimental scattering amplitudes using an underlying quantum field theory (QFT), or modelling them directly using an S-matrix approach. QFT (reductionism) predicts the scattering amplitudes from the behaviour of underlying degrees of freedom, whereas the S-matrix approach (emergentism) models the observations directly by defining inter-relationships between the scattering amplitudes.

Reductionism and emergentism are really the same thing, except that they have a different view about what the fundamental degrees of freedom are. Reductionism explains experimental observations in terms of degrees of freedom that are at a deeper level than the experimental observations, whereas emergentism regards the deepest level as being the level at which the experimental observations are made.

A really good book that gives you an informal feel for the issues surrounding reductionism and emergentism is A Different Universe: Reinventing Physics from the Bottom Down by Robert B Laughlin. This book explains why it may not always be useful to use a reductionist approach. Essentially, the up-side of a reductionist model is that it reduces everything to simpler deeper degrees of freedom, but the down-side is that you have to put in the effort to derive everything from these deeper degrees of freedom. Unfortunately, the amount of effort can be prohibitive, in which case the reductionist model explains the observations "in principle", but "in practice" it is too computationally expensive to be useful.

How is all this relevant to self-organising networks?

There are two general classes of network model called "generative" and "recognition" models:

The generative class of models are reductionist, because they explain experimental observations in terms of underlying causes (or hidden variables). Usually a generative model is primed in a fair amount of detail, so it contains quite a lot of prior knowledge.
The recognition class of models are emergentist, because they compute whatever they need without reference to underlying causes. Usually a recognition model is primed only loosely, so it contains little prior knowledge.

Reductionist and emergentist network models lie at two extremes of a spectrum of possibilities. However, most networks fall close to one or other of these extremes, because each approach has its own "mind set" that tends to repel the other.

The emphasis in this blog is to start with the emergentist approach to SONs, because this approach introduces less prior knowledge, and so is more "hands off" in its analysis of data. It is possible, although not guaranteed, that self-organisation can then be used to automatically discover the sorts of underlying degrees of freedom that are used in the reductionist approach.

If it all goes to plan then reductionism will emerge from emergentism by a process of self-organisation. This sets the scene for my research programme into self-organising networks.

ACEnetica

2005-09-22T21:54:00.000Z

This is a new blog for discussing ideas about self-organising networks (SON).

The term "ACEnetica" is derived from the phrase "Adaptive Cluster Expansion network", which is what I call my own offering in the field of self-organising networks.

What is a SON?

The "N" stands for "network" by which I actually mean a network of interconnected processing nodes, where the global processing activity is broken down into a number of smaller processing activities.
The "SO" stands for "self-organising" by which I mean that both the processing at each node and the interconnections between nodes can be adjusted dynamically.

This general definition of a SON covers a wide range of possibilities. However, the only SON approaches that I consider worth discussing in this blog are those that are "scientific"; the rest of the approaches fall into the category of "natural philosophy" which is definitely not the focus of this blog.

This means that the approach must have the following minimal properties:

It must be supported by a consistent theoretical framework.
It must have predictive power.
It must be open to falsification.

There are two levels at which prediction and falsification are done with processing networks:

Relationship with the external physical world. This is conventional "science", where the processing network is judged by its ability to explain experimental observations.
Relationship with the world of algorithms. This is unconventional "science", and could be called "a new kind of science" (see http://www.wolframscience.com/), where the processing network is judged by its ability to construct processing algorithms.

Some additional properties that are desirable (but not essential) in a SON approach are:

It should scale well with network "size".
It should include "standard" approaches as special cases.

An extra property that would be a real bonus if it emerged for free:

It explains some (or even all) of the properties of brain-like processing.

In this blog I will attempt to present SONs within the above context.

Tag: ACEnetica