Predictive Memory and Particle Filters

I keep thinking about the Particle Filters AI method, so might as well right some of it down. Note that in AI Particle Filters has a particular meaning, different from the physics for particles in a real-world simulation or in a video game. In AI filtering is a method for localization of an object, which could be a large physical object like a robot. It involves probabilistic methods (Monte Carlo techniques) for predicting where the object might be, combined with sensory feedback. Typically it requires a pre-existing map of the territory (which for a robot is real, but which could be highly abstract in other cases) and a method for matching the feedback to the map. It has been most notably used as an essential software component of the Google self-driving car. A somewhat more extensive overview can be found at Particle Filters.

The reason I keep thinking about it is because I started noticing how I consciously (and probably subconsciously) localize myself in the physical world. Most notably, when I am navigating in the dark in my house. I do this to avoid backtracking: turning on a light, going back to the prior switch & turning it off, etc. In any case I know my house well, but in just a few feet in the dark it is easy to get a bit off course and bump into furniture or a wall where I expected a doorway. The stairs can be tricky too.

So I walk a few feet in what I guess is the right direction based on experience. Then I reach out to touch what I expect is a wall or piece of furniture. Or I note a change from rug to bare floor, or spot an LED. Usually I get the feedback I expect, but sometimes I find I am off course and need to make a correction.

In Particle Filter Localization terms, I project a probabilistic range of particles representing where I, the human robot, might be next. Then I check. Often I know exactly where I am after a check, but sometimes all I know is that I am not near a wall or furniture piece. Then I make another mental projection, take a step or two depending on my expectations and level of caution, and try again to touch something. I go through similar mental gymnastics when driving a car or taking a daylight walk, but the feedback is visual rather than touch.

I went through a similar analysis process after reading Jeff Hawkins theory of predictive memory in On Intelligence. The theory is that the brain largely operates by making constant predictions, based on memory of historical patterns, and checking them against sensory input. When input varies from predictions, neurons send special signals about detecting novelty to higher brain centers that deal with novelty. For instance, as you read this your brain knows a number of words might be included in this zebra. See, you expected "sentence" or maybe "essay" or the like, you were not expecting "zebra", and so the normal flow of processing was interrupted.

I have not seen a neural network model for particle filters. It could be that the resemblance between how human brains seem to work is only superficially like particle filters. More generally we are talking about feedback systems, which can take a number of forms. Even very primitive animals that lack differentiated neurons have feedback systems, so there could be many types of neural feedback schemes operating in the human brain.

I often notice my dog doing something that makes me think that most mammals, including pre-sapiens homo species, can do that. Yet when these processes, say chasing a rabbit, are abstracted, they can become quite complex. I can imagine chasing a rabbit. I can plan to chase a rabbit into a trap. I can pursue something more abstract, say a solution to a construction problem or even a math problem in a way that resembles chasing a rabbit. Let's see, the answer to the solution of this differential equation has disappeared, it is not obvious. I'll beat the bushes, using three techniques known to help solve this type of equation, most-likely technique first. Hopefully one technique will put the problem in a form that I recognize from the standard map for solving such equations.

How would particle filters be implemented with neural networks? Let me know your thoughts.

Stanford AI Class wrap up

I managed to muddle my way through the free Internet version of the Stanford Introduction to Artificial Intelligence (AI) course. "Congratulations! You have successfully completed the Advanced Track of Introduction to Artificial Intelligence ..." says my Statement of Accomplishment.

Before putting on my analyst mask, I would like to thank Stanford University and particularly the instructors, Sebastian Thrun and Peter Norvig, for conducting the course. In particular, for making it free of charge. I am hoping they will leave the instruction videos up for a while, there are some I would like to go over again.

I got a good review of Bayes Rule, basic probability, and some simple machine learning algorithms. I had not worked on Planning algorithms before, so that was of some interest. Markov Models had always been a bit vague to me, so that section helped me nail down the idea. Games and game theory seem to have made little progress since the 1940's, but I guess they have to be covered, and I did get clear on how MinMax works. Computer vision seemed kind of weak, but then you can't assume students know basic optics and at least we learned how to recognize simple features. Robotics was a prior interest for me, and I did not know about Thrun's obvious favorite, Particle Filters, which are a useful paradigm for spatial positioning (aka localization).

The last two units were on Natural Language Processing, and that is a good place to start a critique (keeping in mind that all this material was introductory). Apparently you can do a lot of tricks processing language, both in the form of sounds/speech and written text, without the algorithms understanding anything. They showed a way to do pretty decent inter-ethnic language translations, but the usefulness depends on humans being able to understand at least one language.

Plenty of humans do plenty of things, including paid work, without understanding what they are doing. I suppose that could be called a form of artificial intelligence. Pay them and feed them and they'll keep up those activities. But when people do things without understanding (I am pretty sure some of my math teachers fell into that category), danger lurks.

The Google Car that drives itself around San Francisco (just like Science Fiction!) just demonstrates that driving a Porsche proves little about your intelligence capabilities. Robot auto-driving was a difficult problem for human engineers to solve. They were able to solve it because they understood a whole lotta stuff. Particle Filters, which involve probability techniques combined with sensory feedback to map and navigate an environment, are a cool part of the solution. If I say "I understand now: I have been walking through a structure, and to get to the kitchen I just turn left at the Picasso reproduction," I may be using the word understand in a way that compares well with what we call the AI capabilities of the Google Car. Still, I don't think the Car meets my criteria for machine understanding. The car might even translate from French to English for its human cargo, but I still classify it as dumb as a brick.

Hurray! Despite my advancing age, lack of a PhD., less than brilliant business model, and tendency to be interested in too many different things to be successful in this age of specialization, no one seems to have gotten to the essence of how humans understand, and are aware of, the world and themselves.

If the human brain, or its neural network subcomponents, did Particle Filters, how would that work? I know from much practice that bumping around in the dark can lead to orientation or disorientation, depending on circumstances. On the other hand the random micro-fine movements of the eye might be a physical way of generating randomness to test micro-hypotheses that we are not normally consciously aware of.

We sometimes say (hear Wittgenstein in my voice) that someone has a shallow understanding of something. "Smart enough to add columns of numbers, not smart enough to do accounting," or "Good at game basics, but unable to make strategic decisions." Let me put it another way: in some ways the course itself was an intelligence test. I imagine it would be very rough for anyone without a background in algebra and basic probability theory. The students in the class already knew a lot, and had to learn difficult things.

I want to know how our bodies, our brains, learn difficult things. The only way I will be able to be sure that I understand how that is done is if I can build a machine that can do the same thing.

Stanford AI Class thoughts, and a brief tour of AI history

"people who face a difficult question often answer an easier one instead, without realizing it"
— Daniel Kahneman,

Despite time management issues (which will only get worse this week) I managed to struggle through the first two weeks, or four units, of the online Stanford introduction to artificial intelligence course.

In the past I had already tried to struggle through Judea Pearl's Probabilistic Reasoning in Intelligent Systems. That was published well over 20 years ago, and yet this course uses many of the same examples. The course is much more about working out actual examples; it is practical, not so theoretical. We've covered Bayes networks and conditional probability, both concepts I had already learned because Numenta was using them. Pearl's book contains a lot of material about wrong directions to take; the Stanford course seems to be focussed on what actually works, at least for Google.

My impression is still that the Stanford AI paradigm, while very practical, is not going to provide the core methods for truly intelligent machines, which I characterize as machine understanding. I think this largely because I am ancient and have watched quite a few AI paradigms come and go over the decades.

When AI got started, let's say in the 1950's, there was an obsession with logic as the highest form of human intelligence (often equated with reasoning). That computers operated with logic circuits seemed a natural match. Math guys who were good at logic tended to deride other human activities as less difficult and requiring less intelligence. Certain problems, including games with limited event spaces (like checkers), could be solved more rapidly by computers (once a human had written an appropriate program) than by humans. By the sixties, at latest by the seventies, computers running AI programs would be smarter than humans. In retrospect, this was idiotic, but the brightest minds of those times believed it.

One paradigm that showed some utility was expert systems. To create one of these, experts (typical example: a doctor making a diagnosis) were consulted to find out how they made decisions. Then a flow chart was created to allow a computer program to make a decision in a similar manner. As a result a computer might appear intelligent, especially if provided by the then more difficult trick of an audio imitation voice output, but today no one would call such a system intelligent. That is no more intelligent than the early punch card sorters that once served as input and output for computers that ran on vacuum tubes.

In the 1980's there was a big push in artificial neural networks. This actually was a major step towards machines being able to imitate human brain functions. It is not a defunct field. Some practical devices today work with technologies developed in that era. But scaling, the problems grew faster than the solutions. No one could build an artificial human brain out of the old artificial neural networks. We know that if we can exactly model a human brain, down to the molecular (maybe even atomic) level, we should get true artificial intelligence. But simplistic systems of neurons and synapses are not easy to assemble into a funcioning human brain analog.

The Stanford model for AI has been widely applied to real world problems, with considerable success. This probabilistic model allows it to deal with more complex data than the old logic and expert system paradigms ever could. Machine systems really can learn new things about their environment and store and organize that information in a way that allows for practical decision making. Clearly that is one thing human brains can do, and it is a lot more difficult than playing in a set-piece world like tic-tac-toe or even chess.

Sad as the state of human reasoning can be at times, and as slow as we are to learn new lessons, and as proud as we are of our least bouts of creativity, (and as much as we may occasionally ignore the rule against run-on sentences), I think the Stanford model is not, by itself, going to lead to machine understanding. The human brain has a lot of very interesting structures at the gross level and at the synaptic level. Neurologists have not yet deciphered them. Their initial "programming," or hard-wiring is purely the result of human evolution.

When is imitated intelligence real intelligent? When does a machine (or a human, for that matter) understand something, as opposed to merely changing internal memory to reflect the external reality?

Then again, maybe a Stanford model computer/program/input/output system would have done better at the Stanford AI course than I have. I certainly have not been getting all the quizzes and homework problems right on the first try. On the other hand, I think it will be some good long time before a machine can read, say, a book on neurology and carry on an extended intelligent conversation about it.

On Bayesian Belief Propagation

Towards a Mathematical Understanding of Cortical Micro-circuits [Dileep George & Jeff Hawkins, PLoS Computational Biology, October 2009, Volume 5, Issue 10] assumes some knowledge of Bayesian Belief Propagation. I was hoping the article would explain this topic as it went along, but apparently, to AI specialists, this is a well-known area. I found the Wikipedia entry, belief propagation, jumps into mathematical formulism rather quickly. Some words of explanation without math symbols would probably help many people who are interested in machine understanding; that is my goal here. If some of you Bayesian belief propagation experts think I have it wrong, or want to add anything, feel free to add comments. I have ordered a copy of the classic work on the subject, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, and so hope to be more fluent in this area at a later date.

Bayesian Belief Propagation (BBP) was formulated by Judea Pearl, who later authored Probabilistic Reasoning in Intelligent Systems. It appears to be a system for determining unknown probabilities within certain types of complex systems. Let's start with a review of a very simple probability model.

Much of early probability work was formulated in terms of a pair of ordinary gambling dice, six-sided cubes with faces numbered one through six. Thrown many times, they make a nice distribution pattern of numbers two through twelve. It can be shown with a little math and logic that there are percentages that are expected for each of these numbers. If you make a large number of dice throws, say more than 100, and you get results that differ by very much from the expected distribution of results, you may be looking at one of two things. It is possible that you have a distribution skewed purely by chance. On the other hand, you might want to investigate whether your dice and throwing systems are physically constructed to be truly random in the results they give.

Now imagine a black box, say the size of a shoe box. If you shake the box and then stop shaking, it gives you a number. In fact, imagine a room with a variety of such boxes. You shake them, keeping tracks of the resulting numbers for each. If one box consistently gives numbers between 2 and 12 inclusive, and the frequencies for each number match the pattern that we believe two dice would give, then we can conclude that the internal mechanism of the box, whatever it is, has a probability distribution that is created by the same logic that creates the dice probability distribution. There might even be a tiny pair of nano-dice inside.

In computer programming we tend to think in purely causal mechanics. If something does not happen as expected, we have a bug in our program. But in the case of living groups of biological neurons we cannot (so far) look at the inner mechanics of each neuron while watching how the whole group operates. However, if we can control the inputs and read the outputs of a system, then, if we can do the math, we might figure out the probabilities of individual neurons firing given known inputs from the other neurons in the system.

Formally, BBP allows us to calculate the probability characteristics for nodes we can't observe directly, if we can observe enough of the rest of the system. A node does not need to be a neuron. In an AI system, a node is a processing unit with inputs, outputs, or both, that connect it to the system of nodes in question. In our case the nodes are part of a Bayesian network, also known as a belief network. Communication (or messaging) within the network is in terms of probabilities. (See also Bayesian probability)



Think of a network of three people, where each of the people represents a node. Let there be a piece of paper we will call the message (it is blank; the paper is the message, in this case). Let each person have a single die and the rule: if you have the message, throw the die. If it comes up a one, a two, or a three, pass the message to the left. Otherwise, pass it to the right. If we watch the game progress, the message moves around or back and forth in a random pattern. However, it is not a Bayesian network, because it is cyclical. Bayesian networks are not cyclic. Messages more only in one direction.

Now start a series of games in which the message is always handed to person 1 (node 1). Person 1 throws the die and passes the message to person 2 if the result is 3 or less, and to person 3 if the result is 3 or more. Person 2 also throws a die and simply holds the message if the result is 3 or less, but passes if to person 3 if the result is 3 or more. When person 3 gets a message the game is over.

It is a simple game and a tad boring, but if we focus on the propagation time, the number of die throws from the beginning of a game until the end of a game, we can see a set of variations. Over the long run they should form a probability distribution of the times.

Now change the rules slightly. Say person 2 forwards the message if the die comes out 2 or higher. The range of possible results does not change, but the probability distribution will.

Now suppose you know about this type of game, but you can't see the game because it is in a tent. You see a message handed in, and can time how long it is before the message is handed back out by person 3.

By keeping track of the times, you can get the probability distribution. That should tell you the exact rules of the game being played, including the probability that person 1 will give the message directly to person 3, and how long person 2 might keep the message before passing it.

In more complex networks, you need to pin down the probabilities at more of the nodes, if you want to be able to characterize the probability rules for an unknown node.

Which is what the BBP algorithm is supposed to do. It calculates the probabilities for an unobservable node based on the observed nodes.

Theories of the Brain

As a summary, what Jeff Hawkins says on page 2 of On Intelligence seems accurate to me and note this was published in 2004:

Yet we have no productive theories about what intelligence is or how the brain works as a whole. Most neurobiologists don't think much about overall theories of the brain because they're engrossed in doing experiments to collect more data about the brain's many subsystems. And although legions of computer programmers have tried to make computers intelligent, they have failed. I believe they will continue to fail as long as they keep ignoring the differences between computers and brains.

Of course later Hawkins discusses in some detail both neuroscience and attempts at creating human-like machine behavior with what we will call the old AI, or Artificial Intelligence.

All of my experience led me to the same conclusion. It is not that some scientists, computer software engineers, and philosophers have not looked at the problems that On Intelligence addresses. In retrospect, however, most of them made the same fundamental mistake. Characterize it as trying to replicate behavior instead of creating intelligence that replicates human intelligence and therefore human behavior. And one reason most people made the same mistake was because there was no good model of the brain available from the neuroscientists.

I have on my bookshelf The Formal Mechanics of Mind by Stephen N. Thomas. The inside cover blurb says "The author's intention is to provide an analysis of the nature of the mind, and of our knowledge of it—an analysis that solves or avoids longstanding philosophical problems and that fits well with the results of psychological and neuropsychological investigations of mental phenomena." It is a good book. Published in 1978, it is one of the best I had read before On Intelligence.

On the other hand we have the computer programming AI people. They did some pretty good work, but it is a cautionary tale. Most AI worked with very simple models of objects. AI did best, or appeared to do best, when dealing with certain higher human mental functions, like formal logic. But the brain does not appear to operate with formal logic. Humans invented formal logic. It may (or may not) serve as a basis for a theory of mathematics, as Bertrand Russel, A. N. Whitehead, Ludwig Wittgenstein, and John von Neuman attempted to show.

We will, of course, be using mathematics to understand "real" intelligence. Yet there is almost no math in On Intelligence. Before we can develop a math, or apply an existing branch of mathematics, to this problem we have to understand both the true nature of the problem and how the brain implements the solution, both structurally and dynamically.

I also have on my bookshelf, among other books on neural networks, Parallel Distributed Processing by James L. McClelland et. al. I wrote some computer programs to implement some of the models presented in the book. That was back in the late 1980's. The intelligence problem, then, seemed to be solvable in a piecemeal manner. Difference types of neural networks could be combined and improved until something approaching intelligence emerged. But my own attempts at building an intelligence model went nowhere, and I got involved in trying to save some redwood forests. The forests were clearcut despite my efforts, and I'll take Hawkins' word for it when he said that the neural network model had not made substantial progress in the 1990's. Again, neural network software and hardware became very good at certain things, notably pattern recognition. But while intelligent systems (humans) can recognize patters, apparently pattern recognition is not in itself the basis of intelligence.

Next up: Real Intelligence versus AI

Welcome to Machine Understanding

I have been interested in the idea of intelligent, understanding, conscious machines (computers and robots) since I was a child. How could a fan of science fiction books and movies not be? At some point I started wondering how the human mind itself could be intelligent, understanding, and conscious. During my life I have periodically returned to that theme.

A relatively recent wake-up call for me was On Intelligence by Jeff Hawkins. I read the book last year and I am re-reading it now. So most of these early blog entries are inspired by statements from the book. I am more than half-way through the book, well into the nuts-and-bolts of Chapter 6, so I will probably both comment on what I am reading and go back to various passages in the front half of the book.

A few years ago my article Indexing Books: Lessons in Language Computations was published by the Key Words, the Bulletin of the American Society for Indexing. I don't want to discourage you from reading the article, but let me sum it up: if a machine can't read with comprehension, it can't create a high-quality index for a text. Most people think using a computer to generate a good index of a text should be an easy accomplishment.

I chose the term "machine understanding" over AI, artificial intelligence, because I agree with Jeff that the AI field has mainly been a failure. Perhaps I should have called it "human understanding," since we don't really have a good understanding of why humans can understand things, exhibit intelligence, and are conscious.

This blog is mainly for me to keep a record of my thoughts, but if anyone else stumbles across it I hope I can introduce them to the ideas of people who work in this fascinating field.