June 16, 2006

Unified Theory of Learning Systems; or why markets, neural nets, evolution, and Page Rank are all the same thing

Posted in algorithms, computer science, economics, machine learning, math, science at 10:43 pm by Francisco

I was recently thinking about the commonalities between all systems that can learn. Neural networks learn by updating the strength of the connections between neurons. Groups of people and societies in general learn by leveraging the power of markets. Species learn through natural selection and evolution. The Page Rank algorithm that Google uses to analyze the links between all pages on the web learns by updating the weight of each page based on the pages that link to it. What do all these systems have in common? I will try to answer that question in this post.

I first saw the connection between neural networks and markets when I was thinking about prediction markets. In a neural network, every time a connection is used to produce a "positive" result the strength of the connection is increased, and every time it is used to produce a "negative" result the strength of the connection is decreased. Positive and negative depend on the purpose of the neural network. If the neural network is the brain of a mouse, finding cheese would be considered a positive result but getting an electric shock would be a negative result. If the neural network is supposed to identify a handwritten number 6, then correct identification would be considered positive, and incorrect identification would be a negative. In any case, the positive signal could be considered a payment to the neural system, and the updating of the weights is how the neural net distributes the payment among those connections that were responsible for the results. Those connections that are right, i.e. that were activated when the payoff was positive, get paid more by having their strength increased. In contrast those connections that were wrong lose part of their fortune by having their strength diminished. We can start seeing an analogy to a market here, a connection is a bet in a particular direction, and those connections that get it right have more to bet in the next round, but those connections who get it wrong have less to bet.

Now let's look at a market. When an individual buys a security in a market he is betting that the security is going to go up in price. If he is right he makes money and the purchasing power of his account increases, if he is wrong, he loses money and his purchasing power decreases. Next time he makes a decision to buy or sell, the amount that he can buy or sell is going to be limited to how much he has in his account. After several rounds those who usually guess right will have pretty big accounts, and those who usually guess wrong will have very small accounts. So their guesses will be weighted differently, and the price resulting from aggregating those guesses will become more accurate. Once the market reaches a steady state the purchasing power of individuals will be proportional to how good they are at guessing the right price, and the aggregate price will be the most accurate. So the purchasing power of each individual is the weight of their vote, the strength of their connection to the final aggregated price.

From the previous paragraphs we can see how neural nets and markets are alike. We can think of markets as weighted voting systems, where the size of the account of each individual is their weight, and the system updates the weights of individuals according to the accuracy of their votes in predicting an outcome. We can think of neural networks as markets where connections bid for a particular correlation between the activity of two neurons, and those who bid correctly get rich, but those who bid incorrectly lose their shirts.

We can now start to see some of the commonalities:

1) Both of these learning systems have a predicted signal and an actual signal, their objective is to make the predicted sinal equal to the actual signal. In the case of a market the predicted signal is the market price of a security and the actual signal is the true price of the security, the price that makes supply equal demand and that makes markets clear. In the case of a neural net the predicted and actual signals are more obvious since neural nets are designed for pattern recognition where the pattern is the actual signal, and the predicted signal is what the neural net guesses when it is learning.

2) Both of these systems are composed of several distinct units that vote/bet for an outcome, or for a part of the process in an outcome. In the neural net each connection between two neurons is a vote for the state of one neuron being relevant to the state of the other neuron in predicting an outcome. In a market each individual buying or selling a security is voting on whether that security is overpriced or underpriced.

3) Both of these systems give different weights to different voters. Connections are weighted in a neural net, different market participants have different levels of wealth, where the wealth represents buying power, and since each transaction is a vote, the vote is weighted by the wealth of the person doing the transaction.

4) Both of these systems learn by updating the weights of the voters. In a market those who vote wrong lose some of their wealth, in a neural net those connections who contribute to wrong results lose part of their strenght.

5) Once these systems learn, their weights stop being updated. This is achieved by a dynamic equilibrium where the sum total of positive updates is equal and opposite to the sum total of negative updates. Once a neural net learns what it needs to learn, the weights remain stable, they lose as much as they gain in every training round. Once the market participants have attained a level of wealth that represents all their knowledge on a particular security, they are as likely to guess right as they are to guess wrong, so their gain as frequently as they lose and their wealth remains static.

Now that we have these basis, it is easy to see how they extend to other learning systems. Consider evolution, each gene is a vote for a particular physical characteristic for an organism, and on how likely is the organism that possesses that characteristic to survive in its environment. Those genes that vote correctly get reproduced more often than those who vote incorrectly, and their percentages in the population increase. This means that they have a higher weight on the percentage of the next generation. The wealth/weight of each gene is represented in the percent probability that they have of being passed to the next generation in contrast to competing genes. The fitness in genetic algorithm parlance. Once the optimal phenotype is reached the percentages reach a steady state, where half of the organisms are helped by the characteristic, and the other half are hindered. This shows that evolution is very similar to markets and neural nets, since it conforms to the same five broadly outlined principles above.

What about the Page Rank algorithm? This algorithm is applied to a directed graph to find out which nodes are the most popular. At first glance you would want to count how many incoming links each node has to measure its popularity. That is a good first approximation, but not all links are equal, the links of more popular nodes are worth more than the links of unpopular nodes. So you start by counting the links and assigning a popularity to each node, then you count the links again but weight the links according to the popularity of the incoming node. This updates the popularity of each node, so you do this again, until you reach a steady state and the popularity measure of the nodes doesn't change. Again, we can see that each node is voting by linking to other nodes, and its vote is weighted by its popularity. Its popularity is updated according to how many popular nodes point to it. The algorithm of updating can be thought of as a flux of popularity through the system, from the least popular to the most popular. Each node in between has some popularity coming in and some going out. The steady state is reached when the popularity coming in equals the popularity going out. Although the training signal here is less obvious than in other learning systems, it is still something separate from the predicted signal, it is the actual popularity of each node according to the graph topology. As we can see Page Rank also shares the same five basic characteristics of learning systems that markets, neural nets, and evolving systems all have.

I think we can apply the same sort of analysis to anything that learns. That is a conjecture that I am not going to prove because it would require me to either enumerate all learning systems, or prove that a system that doesn't share those characteristics cannot learn. That proof might be doable, but that would be too much work for a Friday night post. My purpose is only to advance the hypothesis that all learning systems are instances of the same algorithm and to provide some examples as evidence to that conjecture.

To the science and engineering inclined, this can serve as motivation to specify the learning algorithm exactly by observing many instances of systems that learn. To the mathematically inclined, this could serve as motivation to find a rigorous argument of why this is true. To the scientifically inclined with a skeptic bent, this can serve as inspiration to try to disprove it probably by finding an example of a learning system that doesn't fit the model. As for me, this was just a way to record an insight I found interesting.

As I finish writing this I realized that the expectations maximization algorithm, and the fuzzy clustering algorithm also fit this description, but I leave these as an exercise to the reader because I am tired of typing, and I want this post to be short enough for people to actually read.  

About these ads

6 Comments »

  1. Cy said,

    Blimey, mate! I hope enough people at the top of the class read this as to have made it worth your while to have written it. Here at the bottom of the class, I have read and enjoyed it as I might enjoy a dazzling athlete doing his stuff. Of course, I cannot hang around and try to soak in the whole deal. I have trivia to attend to.

    I hope none of those nasty spoil sport boffins try and disprove what you said, and as for those maths fans, they are always trying to put into number what is best left in words. I just wish there was a simpler way to put it. Once bitten, twice shy, or something.

    As to the Al Gore rythm, are we sure the poor lad has any? Rather plodding, he seems to be. No insult intended. No harm done. But ability to distinguish between Green-Fascist selective statistics to serve an anti-West agenda on the one hand, and truth on the other hand, score zero he does I think. Very sincere he is, but easy to fool also.

    I set your piece aside yesterday and today, after a walk down to the pier (my bike has a rear wheel puncture) and a nice siesta on return I have tackled it. I can only repeat: cor blimey, mate! cyquick.wordpress.com

  2. Fred said,

    Really enjoyed it.
    Does it also work with students trying to learn ?

  3. David Relyea said,

    Hey Francisco! You got geekpressed! Nice. Good essay, though this is how all AI people see the world. John Langford (www.crush.net) (if you remember him at all, or ever knew him) works on AI/learning now, and has written a lot about it, though it’s technical. You might enjoy his work.

    Hope you’re doing well!

  4. Francisco said,

    Hi Dave,
    Good to hear from you, and thanks for the reference on John Langford, the name doesn’t ring a bell but his picture might, what house did he live in? In any case, if he is writing technical papers about this I definitely want to read them.
    I don’t think that all AI people see the world like this as you claim, I also went on to study AI, and I currently work developing AI systems. In all my readings, classes, conferences, etc. most of the people I met did not see the world like this. First of all, not everybody in AI is interested on learning, some people are interested in reasoning, others in optimization, others in representation, multiagent systems, fuzzy reasoning, embodied agents, etc. Among the learning crowd I remember references to proofs that bayesian nets were equivalent to neural nets under certain conditions, Q-learning could also be represented as a neural net, that they all were special cases of statistical learning, etc. but I never saw anybody make a broad claim that markets, evolution, and neural nets were all equivalent. In my experience AI people didn’t think about markets too much, with the exception of those who are building multiagent systems but are not necessarily interested in learning. In that case they used markets as a coordination tool, not as a learning tool. The claim that markets can learn comes mostly from economics, not AI. Also, AI people tend to use evolution in genetic algorithms or genetic programming as a stochastic search, or as a creativity machine, not as a learning machine. Note that I am not claiming to be the first to have thought of this, I am just saying that the great majority of AI people do not see the world like this, so I am glad to hear that there are some who do, and I definitely want to read their papers :-)

  5. celexa side effects

    celexa side effects

  6. Dave Jilk said,

    Francisco,

    I think it’s an interesting and useful analogy but my gut says it’s a stretch to demonstrate that these are isomorphic below the highest level. At the highest level, there are a large number of interacting agents and the interaction tends toward equilibria, but never reaches one because of continuous new stimuli. Isn’t that just “complexity theory”?

    At a lower level, there is a critical difference between neural networks (at least good ones, and the ones in our heads) and markets. In markets, indeed the wealth goes to those who are right so their “weights” to various other areas continues to increase. But in a real network of neurons, the neurons are actually driven toward biological homeostasis, so that the average firing rate of each neuron lands in about the same range (too little or too much and the neuron will die) – it’s a communist society! However, the way they do this is divide-and-conquer, in effect – neurons end up specializing and respond to certain stimuli and not to others. The analogy would be that everyone in the market picks certain kinds of stocks and ends up about as rich as everyone else. Not really what happens.

    I think the analogy is good in the short run, the idea that weights increase etc in response to error conditions, but in the long run the dynamics are different.

    Anyway, in thinking about this you’ll definitely want to make sure you’re at the right level of analysis.

    Dave


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: