The Verve Project

Practical Solutions to Hard AI Problems

2011-02-14T18:30:00.000-06:00

An observation: the practical solutions to several recent hard AI problems seem to favor ensemble-based approaches. For example:

Data compression: record-setting PAQ-based compressors are "context mixing" algorithms that combine several context/prediction models.
Netflix Prize: the winner used a blend of many different predictors.
IBM's Watson Jeopardy player: their DeepQA architecture considers several hypotheses simultaneously and chooses one with highest confidence score, or none if max confidence is too low.

In each case the solution is not to focus on one really good model but rather a mixture of several independent models. Maybe the reason is just that inductive learning is an under-determined problem. For any given data set there are many possible explanatory models. Occam's razor/Kolmogorov complexity tells us to assume the simplest model/program that could have generated the data. This assumption might be wrong, especially with limited data, but given limited data it's the only sane thing to assume.

For any data set the number of models is often so large that we can't just enumerate them and pick the simplest. We have to sample the model space somehow. If we have prior knowledge of good models, we should use it; otherwise we can sample randomly (e.g. random forests).

Matt Mahoney (PAQ inventor): "Modeling is provably not solvable." There is no computable procedure that finds the optimal model for any problem, and there's no way to tell if any model is the best/simplest.

Marvin Minsky: "The basic idea I promote is that you mustn't look for a magic bullet. You mustn't look for one wonderful way to solve all problems. Instead you want to look for 20 or 30 ways to solve different kinds of problems. And to build some kind of higher administrative device that figures out what kind of problem you have and what method to use."

IDSIA Postdoc, iBonsai, PhD Prelim, Sapience Engine, etc.

2009-06-29T13:57:00.042-05:00

It's been several months since I posted here, mainly because I've been busy working on my research code and my PhD preliminary proposal/presentation. Here's a quick summary of things since March...

IDSIA
In March I applied for a postdoc position at Juergen Schmidhuber's lab at IDSIA in Lugano Switzerland. At the AGI 2009 conference I met with Juergen to interview for this. Shortly afterwards I was offered and accepted the position, starting in January 2010! So now I need to hurry and wrap up the PhD before then, which is stressful (because I hate trying to write up work until it's truly ready), but also good (because I'm gonna go crazy if I'm in school much longer). The postdoc will involve research related to artificial curiosity, which is very exciting to me, especially considering that I'll be working with Juergen, one of the most important researchers in the field. I'll be working with the iCub robot (pictured below) at IDSIA for much of the time. (Next month I'll be attending the RobotCub summer school to learn more about the iCub.)

iBonsai

iBonsai (details here) was released for the iPhone/iPod touch on December 28, 2008. My primary motivation for making this was to make money so I can continue my AI research unconstrained. (Despite the fact that I'm in it for the money, I can't stand to put out a sub-par app... I did spend several months of nights and weekends tweaking the algorithm and visual style, and I'm proud of the result.)

After 6 months of sales I can't say I'm ready to retire off the sales, but I'd say it has done better than expected. The picture below shows the top 100 apps list in the iTunes App Store on 6-9-09. Note that on this day iBonsai is right behind Myst and is beating several popular apps like Fieldrunners, Koi Pond, Ocarina, and SimCity. This high rank is mainly due to being featured on the App Store during that week (in Staff Picks in the US, What's Hot in several other countries). Overall iBonsai has been downloaded 95,000 times (mostly free downloads during short promotional periods to gain exposure).

I would really like to make some more apps, though I don't know when I'll find time to do it. I made a list of possible app ideas last fall and decided to start with something small (iBonsai) just to test the waters. Maybe when I finish the postdoc I'll continue iPhone app development as a source of income. Or maybe I'll find time on the weekends. We'll see. I must say it is much more satisfying to be able to point to a real product and say, "Wanna see my iPhone app?" instead of, "Wanna see this project I've been working on? I posted the source code on my website. You have a C++ compiler, right?"

PhD Preliminary Proposal

I wrote up a research proposal for my PhD in April and May, then presented it to my committee in early June. The title of the proposal (and tentative title of the final thesis) is "Sapience: A Brain Inspired Cognitive Architecture." The proposal is mainly a high-level description of my Sapience Architecture, which represents the bulk of the conceptual work I've been doing over the past several years. This architecture is fully implementable; each component can (and has been) implemented in software and tested in simulated or robotic bodies. It is comprised of 5 main components inspired by the brain's sensorimotor cortex, hippocampus, basal ganglia, cerebellum, and prefrontal cortex. And it's intended to be useful, with behavioral shaping provided by programmer-defined reinforcements.

It's been a little while since I've written up any research, so it was a bit of a struggle to convert my ideas into such a formal document. I feel like I'm good at writing, given enough time (and admittedly, this proposal could have used more time...); it's just very mentally taxing to produce a document worth other people's attention. One thing that helped was to create diagrams. I made a high-level architecture diagram (shown below) and a more detailed one for each of the main components. I think these really help clarify the design much better than words alone.

I'm glad to have written this proposal because it forced me to articulate several of my underlying assumptions. For example, I describe the "purpose" of this architecture in terms of reinforcement learning; the system's objectives include external reinforcements (i.e. programmer-defined goals) which makes the system practically useful, and internal curiosity reinforcements which provides a source of autonomous self-development even without a human teacher. Corresponding to these rewards are two useful metrics for measuring learning progress: external reward intake (goal achievement rate) and world model improvement rate (information gain).

At this point I have a software implementation of each of the 5 components, along with the necessary code to integrate them into a cohesive "software brain" (described next). Now the primary work involves testing each component in isolation and in combination with the other components. Part of the testing process will involve a simulated human arm, complete with proprioceptive, tactile, and vision sensors and servo motors (shown below).

Sapience Engine

For my PhD thesis I'm calling the conceptual work the Sapience Architecture, which is basically a blueprint for a practical, engineered thinking system. The corresponding software implementation of this architecture is called the Sapience Engine. I plan to use this software as a research platform for my postdoc position at IDSIA, hopefully applying it to the iCub.

I'm pretty excited about this software. When I started grad school in 2003, I originally wanted to build a black box software brain, and that's exactly what the Sapience Engine is. It's shaping up to be a pretty powerful system, scalable to high-dimensional inputs and outputs, with a very general behavioral shaping system. The API is very simple. It's written in C++ and has Python bindings (via ctypes). It has built-in multithreading and runtime performance profiling. It has been structured in a way that can be easily adapted for clustered computers (e.g., via MPI). Several pieces could even be GPU-parallelized.

I also have written a very useful real-time probe tool, designed as a client/server pair: I can link any Sapience Engine-powered program with the Sapience probe server, which provides access to various internal variables, then run a separate Sapience probe client (earlier version pictured below) which displays real-time plots, 2D array visualizations, neural network adaptation, etc. This "brain debugger" is turning out to be a crucial tool in the testing process.

I Don't Want to Do Academic Research

Ok, this statement doesn't really make sense considering that I'm currently finishing a PhD and preparing to start a postdoc position. I guess what I mean is that the idea of being a traditional academic researcher does not appeal to me. I hate the idea of structuring my research in order to generate publications at a fixed rate. That just doesn't make sense to me. (Well, it makes sense in general in that it makes the academic system scalable to lots of researchers, but I don't think it's the best strategy for every project or person.) Also, I think my medium of choice is software development, not publications. I would rather have a list of open source software projects on my website than a list of papers. A well-designed, well-written, timely software release can have an overall impact similar to that of an influential paper.

I would prefer to work on big ideas, to work on them long enough to see them succeed (even if that means several years without publishing), then write up papers after the fact. Some ideas just seem to work better that way. Lots of trial and error and engineering work up front, then scientific analysis later. For example, the automobile, the world wide web, the large hadron collider... It doesn't always make sense to do a lot of scientific work until the engineering work is complete. And the same might be true for general AI.

On a personal level, I think what bothers me most about traditional academic research is the expectations. I work best when I feel unconstrained by external pressures (to make money, to publish papers, to reach certain artificial objectives, etc.). In that sense, I suppose what I'm looking for long-term is complete freedom of expression within the realm of AI research. I expect my work to be very useful, but I just don't want to feel constrained. I want to be an engineer with the motivation of an artist. Over the next several years I intend to find a way to make that happen, ideally by making a big chunk of money up front to support several years of unconstrained creativity.

AGI 2009 Conference

2009-03-23T09:14:00.007-05:00

I attended the 2nd AGI conference a few weeks back. The goal of the conference is to help organize the field of artificial general intelligence (AGI).

Juergen Schmidhuber (pictured above) gave the keynote, entitled "The New AI." I was especially interested in the part of his talk on artificial curiosity. Marcus Hutter gave two good paper presentations, "Feature Markov Decision Processes" and "Feature Dynamic Bayesian Networks." John Laird's talk on the SOAR architecture included a helpful definition of cognitive architectures (specific set of fixed mechanisms) vs. frameworks (neural nets, rule-based systems, etc.). There was an interesting mixture of people there (maybe 100 total?) from academia and AGI-based startup companies and organizations.

In order for the AGI field to move forward in a cohesive, organized way, it will be important to define standard evaluation metrics. (The conference session on creating an "AGI preschool" discussed this issue.) This seems to be one of the biggest hurdles in the near term. Communication among researchers is already difficult since nearly everyone uses a different set of terminology, but the lack of standard evaluation and comparison methods makes it even more difficult. Producing solid metrics might even be the most crucial step here... once you know what you're measuring, it's much easier to work towards that goal. However, general intelligence is really hard to measure, even in humans. The best starting point is probably to start from our current definitions of general intelligence, which are usually in the form of "an agent must be successful at achieving goals/maximizing rewards in a wide variety of environments." So I'm thinking that a good practical approach is the one described in a paper by Thomas Hazy, Michael Frank, & Randall O'Reilly (Towards an Executive Without a Homunculus: Computational Models of the Prefrontal Cortex/Basal Ganglia System): "To the extent that the same basic model can account for a progressively wider range of data, it provides confidence that the model is capturing some critical core elements of cognitive function." So we can build a standardized, ever-growing repository of small tasks, each with a clear measure of success/failure (either binary or scalar). Then we can subject our AGI systems to the entire test set and measure general intelligence performance as the fraction of tests passed. Our confidence that the metric is useful should then be proportional to the number and variety of tasks in the test set. I can't think of a better, simpler way to measure general intelligence than this.

At the conference I showed a live demo of my sensory cortex model learning from natural images, along with the following poster (full-sized image available from my website):

Practical Mind Control

2009-02-20T10:33:00.015-06:00

Effective mind control (for any purpose) is not about making people do things they don't want to do. It's about changing what they want. Then they think they still have free will over their own decisions.

To accomplish this, simply expose them to your idea/product/meme repeatedly. Here's how it works:

The more we experience something, the better we can imagine it.
The better we can imagine something, the more we choose to think about it.
The more we think about something, the more it influences our actions.

The more we experience something, the better we can imagine it.

Our brains build representations of things as they receive data samples of those things; sensations physically change our mental hardware. The more samples from a particular data source (foods, music styles, visual art styles, places), the more accurate our mental representation of that source.

The better we can imagine something, the more we choose to think about it.

Our minds are attracted to some thoughts over others. The question of which thoughts are most attractive can be answered by the theory of curiosity rewards: our brains produce internal rewards as long as they can improve at predicting new data. The better our mental representation of something, the more we are able to notice, appreciate, predict, and enjoy its complexities (for example, the complex flavor patterns in coffee, wine, chocolate, olives, and cheese). These situations can be intrinsically rewarding as long as we get better at understanding/predicting them. (When we can no longer improve, boredom ensues.)

Thus, we perform a type of unconscious mental rehearsal of a small subset of possible thoughts. Our attention is most focused on those ideas which provide the most rewarding progress towards better prediction, which tend to be the ones about which we have significant experience (and thus mental representation). As we continually gravitate towards those ideas, they become the easiest to recall.

(In some cases there might even be a positive feedback loop here: the better we can imagine something, the more it evokes curiosity rewards, the more we want to experience it, the more we do experience it, the better our mental representation, the better we can imagine it... The process is bootstrapped by an outside force which provides the initial exposure, but this feedback loop keeps it going.)

The more we think about something, the more it influences our actions.

The burden of making a decision (e.g., which of several products to buy) is lessened by having a short list of options in mind.

If the cost of making a decision is factored in (which is usually the case), we must find a balance between picking the best option and minimizing the time needed to make the decision itself. The weighting of these two factors depends on the cost of the decision outcome vs. the cost of wasting time making the decision; we can afford to spend more time if the decision outcome is more important.

More exposure to/thinking about one option makes it easier to recall vs. others, which shortens the decision process, possibly to the point where the other options are not even worth recalling...

Conclusion

By the transitive property, we tend to choose things we have experienced most. Thus, to make people like/choose your idea/product/art, simply expose them to it repeatedly.

George Costanza utilizes this mind control technique in the Seinfeld episode The Chicken Roaster. Heather: "Alright George, I'll be honest. The first time we went out, I found you very irritating, but after seeing you for a couple of times, you sorta got stuck in my head... Co-stanza!" (to the tune of "By Mennen").

Note that this only works for emotionally/value neutral things. If a person already has an aversion to something, simple exposure might not be enough to make it attractive. But repeated exposure to an initially neutral thing/place/idea tends to make it more attractive than other still-neutral options.

This is the essence of advertising in general, the idea that "any press is good press," and the rich-get-richer type of driving force behind all kinds of pop culture phenomena. It is practical on a personal level (self mind control) in terms of discovering new tastes. Our dislike for certain things should not be considered an intrinsic property of ourselves, but rather a set of tastes which we have not yet acquired. Expect not to like things at first; everything is an acquired taste which can be enjoyed with a certain amount of practice (although the investment might not always be worth the effort).

Brainpower Labs LLC

2008-12-31T10:26:00.006-06:00

I decided to go ahead and start a company. I was planning on doing this eventually after I finish my PhD, but it seems like a good idea just to get the ball rolling now. The plan is to commercialize my AI research.

Back in 2004 and 2005 I just assumed that my research would always be open source. I released my master's thesis implementation as the open source project Verve. I posted on this blog in detail about every idea and simulation result. Monetizing this work didn't appeal to me; I was just happy to be able to work on something as grandiose as general AI.

I slowly came to realize that after graduation, I won't be able to sustain my progress without getting a day job. I really want to continue this research full-time, and I really do not want to divide my attention in order to make an income. So what are my options?

I worked on the Netflix Prize for a while (and still do periodically)... a quick $1,000,000 would be a great source of initial funding. (My best result so far is 0.5% better than Netflix's own algorithm, but I need to reach 10% for the win.) Going for such a big prize is a lot of fun, but I'm not betting on it. I still need something a little more predictable.

When the iPhone SDK was announced, I didn't really consider iPhone app development. It seemed like a lot of work and a big distraction from research. But when the iPhone App Store was launched, I started watching the list of top paid apps. Many of them are very simple but seem to sell pretty well. I started thinking more seriously about starting an LLC and building a few simple apps. It would be a good way to get my feet wet in the free market (learning what people want, as Paul Graham would say), plus I would learn the iPhone SDK and be able to use it for other projects. That's not to mention the psychological benefits of making things more concrete... feeling part of the real world and less like a graduate student.

So in October I decided to pull the trigger and formed Brainpower Labs LLC. Our first product, iBonsai, is definitely not AI-related, but it has been a good first app for me to learn the iPhone SDK, OpenGL ES, and the iPhone's performance limitations. (The thing is very impressive for a handheld device, by the way.) It's a little distracting right now switching between AI research and iPhone app development, but I'm hoping the two efforts converge at some point. I'm thinking our next app will be based around some simple AI techniques.

I'm really glad to have started the company now rather than after graduation. Besides having a new source of income (fingers crossed) to ease the transition out of grad school, I now have an immediate outlet for turning research ideas into real applications. As my core intelligence architecture progresses (which I've dubbed the Sapience Engine), I'll be able to use it to produce increasingly interesting applications, which could be iPhone apps, desktop computer software, console video games, or robotics applications.

iBonsai Version 1.0 for iPhone and iPod touch

2008-12-29T23:26:00.009-06:00

UPDATE (1/5/09): iBonsai was featured on gizmodo.com and iphoneappreviews.net.

I just finished iBonsai, a new app for the iPhone and iPod touch, which is now available on the App Store:

For more info about this app and my long-term business plans, visit my new company website.

iBonsai Description
Bonsai is the Japanese art of miniaturizing trees by growing them in small pots. Now you can create your own 3D miniature trees right on your iPhone or iPod!

With a tap of your finger, iBonsai's sophisticated generative algorithm begins growing a unique digital tree. No two bonsai trees are the same! After about 30 seconds of growth, your mature bonsai becomes a beautifully rendered image in the sumi-e style of Japanese brush painting.

Enjoy the zen-like relaxing nature of this ancient art form.

FEATURES:
- Simple, clean interface.
- Interactive 3D view. Rotate/zoom to see your trees from all angles.
- Many different leaf types: japanese maple, flowering dogwood, and more (even a rare money tree...).
- Shake your iPhone/iPod to scatter leaves!
- Save images of your favorite trees, then use them for your background.
- Optional gravity-based viewing mode makes the tree appear to float in space.
- Advanced generative algorithm and random number generator give you totally unique results every time. Produce virtually infinite trees!

Progression of Intelligent Processes

2008-11-25T22:54:00.005-06:00

The purpose of this article is to discuss the possible roots of intelligence in the universe. As with most fuzzy concepts like "intelligence," we must begin by producing several basic formal definitions which we can then use as tools to build more powerful concepts. We attempt to use these definitions to classify intelligent processes and their advancements over time. The result of this thought process is the idea that an intelligent process tends to produce other intelligent processes with goals that also fulfill the goals of the original intelligent process.

Definitions

System: any collection of interacting components.

State: a complete description of all components of a system.

Process: a sequence of changes to the state a system.

What's the difference between a "random" and "non-random" process? It depends on the level of detail of the analysis. If we analyze a complex process operating on a large system with a crude level of detail, representing it with too few variables, then we lose the ability to model all predictable effects. Thus, we must quantify the results with a certain degree of uncertainty/randomness simply because our model lacks enough detail. However, given infinite resources used to analyze processes, any process becomes non-random.

Stability: a property of the state of a system, proportional to its ability to remain relatively unchanged over time when perturbed only by a completely random process.

A process can change a system from a stable state to an unstable one, or vice versa. It can move a system through a trajectory of stable states. It can even, in a way, give birth to other processes: it can lead a system to a state where other "child" processes are able to act on it as well.

Goal: a target state of a system.

Intelligence: a property of a process, proportional to its ability to move a system closer to a pre-defined goal state.

Goals are defined by outside observers. For any particular analysis of any particular process, we can define whatever goals we want and determine the degree of intelligence present. Thus, intelligence is in a sense arbitrarily defined, but it can be a useful measurement as long as the goals are well-specified. We can say that a process has zero intelligence if: 1) it has no goals defined, or 2) it is completely unable to move a system towards a defined goal.

Now let's take a step back and think about our universe as a whole. The universe is defined by its initial conditions and its fundamental forces: the initial conditions specify the initial state of all systems, and the fundamental forces constrain the possible processes that can act on those systems. Interestingly, there seems to be a universal process which tends to favor systems in stable states. Imagine the state of any system as a point on a surface (or landscape), where the lowest points are more stable than the peaks. This universal process forces all systems down the slopes of their stability surfaces towards the (locally) minimum points. If the minimum is bowl-shaped, the system will stop changing when it reaches that minimum. (The minimum might be a valley, though, so there can be room for the system to wander around its state space within the valley and remain stable. This is a key requirement for a process to birth another process: when the parent process succeeds in reaching the minimum, the child process can begin to explore the valley.) Systems might go through unstable states temporarily, but they will tend towards the most stable. So what is this universal process which favors stability?

Evolution: a process which tends to change the state of a system to increase its stability, i.e. an intelligent process whose pre-defined goal state is the one with maximum stability.

The universal process described above seems to select the most stable states, allowing them to last, while discarding the unstable ones. We can view it as a type of evolution, "physical evolution," the first intelligent process within the universe.

Brain: a system which supports a specific variety of intelligent process. This process represents a transformation from input space (sensory) to output space (motor). Brains are produced by some other intelligent process which specifies their goal states.

Note that evolutionary and brain-based intelligence are processes, and remember that processes can give birth to other processes. In general, processes with a high degree of intelligence tend to lead to the existence of other intelligent processes. A single parent intelligence can even produce an entire family tree of intelligent processes. Furthermore, the child processes tend to be given goal states from a subset of the parent's goal states. A child process whose goals violate those of the parent will not last.

Progression

The following list describes the progression of intelligent systems in the universe. Each stage represents the result of some combination of events which produces a kind of intelligence phase change. There can be multiple intelligent processes at work simultaneously (e.g., the original physical evolution, its child "genetic evolution,", etc.). We intermix the more significant advances of each process as they appear. The list is, of course, not exhaustive; it represents a very small sample of all the complex processes in existence. Since we must choose a small subset, we choose to focus on those events that are most interesting to humans, i.e. those involved in the generation of our own existence.

Note that the goals of each child intelligent process cannot oppose the goals of the parent process without being destroyed. Also note that a key ingredient to many forms of intelligence, including evolutionary processes and more advanced brain-based intelligence, is the random exposure to new situations which enables trial-and-error-based decision making.

Physical Evolution Level 0: Initial state of the universe
The "null" stage. The universe is in its initial state, determined by some unknown process, waiting for the fundamental forces to begin acting.

Physical Evolution Level 1: Clusters
As soon as the fundamental universal forces start acting, physical evolution appears. Gravity produces clusters of particles from the initial state of matter. Larger clusters have more pulling force than smaller ones; the large get larger, and the small get sucked into the larger ones. Eventually physical evolution produces its first result in achieving its goal of stability: the universe becomes a stable collection of clusters of matter separated by empty space.

Physical Evolution Level 2: Stable molecules
Once the cosmic-scale events have settled down, interesting things begin happening at the microscopic level. Atoms are constantly colliding, "trying out" new ideas for molecules. The molecules that last longer are more stable; if they stay around just a little bit longer than others, they will become more common. So we begin to see physical evolution performing a type of selection process on molecules. Those that are most stable proliferate, and the unstable ones disappear. Each stable molecule flourishes in a certain habitat. There can be multiple stable "species" of molecules that coexist, possibly with symbiotic relationships.

Physical Evolution Level 3: Stable structures
Now that there are stable molecules available, physical evolution can operate on combinations of molecules. Random collisions of molecules produce all kinds of physical structures, some stable, and some not. Physical evolution again selects the more stable structures to proliferate, resulting in a new kind of battle for survival.

Physical Evolution Level 4: The cell wall
A molecular structure is produced that acts as a shield against bombardment: the lipid bilayer. Any collection of molecules with one of these protective shells (i.e. a crude "cell wall") gains a massive advantage over others in terms of mean lifespan. Their existence is still relatively short but much longer than before. In certain hospitable environments, these stable "cells" become common.

Physical Evolution Level 5: Birth of genetic evolution
With the protective cell wall in place, physical evolution can begin to experiment with various modifications to the internal cell structures. As before, any changes that increase the lifespan of the cell produce more long-term stability of that design. The game-changing event at this stage is the appearance of intra-cellular structures which support information-based representations of physical structures (primitive DNA). Physical evolution has given birth to a new intelligent process: genetic evolution.

Genetic Evolution Level 0: Gene expression
The presence of some molecule results in the production of some corresponding physical structure. This is the essence of gene expression. Any cell containing molecule X produces structure Y. Such a procedure is enabled by a combination of structures that acts as a gene expression machine. The details of the actual transformation (from X to Y) are unimportant as long as X reliably produces Y. Cell stability is still fundamentally tied to its physical properties, but with this gene expression machine in place, it is now indirectly tied to the presence of certain genetic molecules. Long-term survival under these new rules depends on having the right combination of these "genes." If having gene X implies having structure Y, and structure Y is related to a stronger cell wall, better repair mechanism, faster acquisition of resources, etc., then cells with gene X will become more common. Essentially, this new intelligent process operates in gene space, which is just a proxy for physical space. Genetic mutations, random events that modify a cell's genetic material, are an essential part of exploring this new gene space. The goals of the new genetic evolution intelligence (proliferation of stable genes) still fall within the constraints of its parent's goals (proliferation of stable structures).

Genetic Evolution Level 1: Cell replication
When cells develop the machinery to copy their own genetic information, they become able to copy their physical structures as well. This produces an explosion in the speed at which genetic evolution can operate. The "fitness" (relative long-term stability) of a given genetic solution is multiplied by the number of instances of that solution: a large population of short-lived physical entities is now more stable than a single long-lived non-replicating entity. The feedback loop (successful genes produces more numerous, stable physical populations, which generate more copies of those genes, and so on) means that systems with replication quickly outnumber non-replicating systems.

Genetic Evolution Level 2: Motility
Moving around increases the probability of acquiring resources, resulting in an increased ability to build and repair structural elements. Motility is possible even without feedback-based control: simply moving around quickly without any particular target is much better than sitting still. One possible form of early motility is enabled by a basic type of short-term memory: the charging/discharging cycles of cell depolarization, tied to some physical deformation of the cell, produces a variety of repetitive motions, some of which tend to move the cell around in its environment.

Genetic Evolution Level 3: Brains
Targeted acquisition of resources based on sensation is a more advanced form of motility which usurps simple blind movement. When external events are allowed to affect cell depolarization (which drives motility), a feedback loop is present in the system. This presents a new domain for genetic evolution: the control system between sensation and action - the brain. Brains are defined by genes, just like all other structures in the system, so genetic mutations changes can can act upon the parameters of these controllers. Genetic changes are favored that improve the control system in a way that results in more copies of those genes. We consider the transformation process (inputs to outputs) performed by the brain as a child intelligent process of its parent, genetic evolution. The initial brain's implicit goals involve acquiring energy and materials, but can potentially involve anything needed by genetic evolution. Any changes in the brain's parameters are constrained to help achieve the goals of genetic evolution.

Brain Level 0: Simple feedback control
The simplest brains are basic feedback control mechanisms (e.g., P/PD/PID controllers) which transform some sensory input signal into an output control signal. Initial possible "behaviors" for entities evolved in different environments include chemotaxis (chemical gradients), thermotaxis (temperature gradients), phototaxis (light gradients), etc. These feedback-based behaviors provide much more resources for the entity, increasing its long-term stability over those without such skills.

Genetic Evolution Level 4: Sexual reproduction
Targeted motility enables sexual reproduction. The success of a gene may depend upon the presence of other genes. In general, more complex structures must be represented by larger chunks of genetic material. The evolution of an entity's genetic material is a slow process when based on asexual reproduction and mutations alone; furthermore, the emergence of complex structures from mutations of an individual genome is fairly improbable. However, the emergence of genetic crossover, the ability of two physical entities to exchange chunks of genetic information, dramatically increases the probability of producing more complex structures. This procedure represents a wormhole through gene space through which information can warp. The result is that genetic material present in two separate entities, which might produce simple structures in isolation, can combine synergistically to produce much more complex structures in the offspring entities. Genes are now favored that optimize the control system towards more sexual reproduction, e.g., producing an implicit goal in the physical entities of maximizing intercourse.

Genetic Evolution Level 5: Multi-celled entities
A collection of cells that functions together in close proximity provides a benefit to each cell involved. By "cooperating" in a sense, many cells can share the overhead costs of staying alive, amounting to a type of microscopic trade agreement. While sharing the burdens of life with nearby cells, they can start to specialize into different roles, increasing the variety of macro-scale multi-celled structures.

Brain Level 1: Discrete switching control
With the appearance of multi-celled entities, the brain can now consist of a network of specialized neural cells which communicate via synaptic transmission. Each neural cell represents a nonlinear transformation of inputs to outputs, and the collective activity of the neural network can be viewed as a dynamical system. Such dynamical systems can have many stable states. Thus, instead of using a single feedback-based controller, the brain has now evolved multiple discrete control systems ("reflexes"). Each one is used in a different situation (e.g., feeding, swimming, mating, fleeing). The "decision" of when to switch is still solely influenced by the current (or very recent) sensory information; when the entity is exposed to a certain situation (i.e. a certain pattern of sensory inputs), its brain switches to a different stable feedback loop (attractor state in the dynamical system).

Brain Level 2: Language
Language emerges when the brain evolves distinct behaviors based on sensory input patterns caused by other entities. The basic ability to communicate information among individuals has the potential to augment the individual's representation of the state of the world with key information that can improve decision making (e.g., the task of information acquisition can be shared among many individuals). This is a necessary step towards the beginning of cross-generational information transfer, or "culture."

Brain Level 3: Structural learning
Previously, learning was possible based only on very short-term effects (e.g., cell membrane voltage). Now, brains are able to store information indefinitely by making structural changes to themselves based on experiences. This provides the brain with the ability to make decisions (about which action to perform next) based on current sensory information AND past experiences. Individuals can learn from mistakes. This takes some of the burden off genetic evolution; instead of evolving entities whose genes are tuned for very specific environments, it can instead evolve entities whose brains have a certain degree of adaptability, making them successful in a wider variety of environments.

Brain Level 4: Explicit goal representation
Previously, the brain's goals were implicitly determined by genetic evolution (produce behaviors that help proliferate genes). Brains that did not meet these goals were wiped out. Now it is possible to represent goals explicitly in the brain via reward signals (e.g., dopamine). This new brain sub-component is a mapping from certain sensory input patterns ("reward states") to a scalar reward signal. When this reward value is high, the entity's current actions are reinforced. So any situation that increases the brain's reward level will reinforce the recent actions that led to it. This operates on the existing switching control system by adjusting the probabilities of switching to each individual action in any given situation. Interestingly, the specification of which sensory situations produce reward signals is arbitrary and can be defined genetically.

Genetic Evolution Level 6: Genetic determination of brain goal states
Now, instead of having to make complex, global changes to the brain in order to add new goals, genetic evolution can now just modify the mapping from sensory state to reward. The brain's explicit goal representation, which is genetically defined, provides a simple unified architecture for adding, deleting, and adjusting its goals.

Brain Level 5: Value learning
Adjusting the action switching system based solely on the current reward signal is not always ideal; sometimes it is important to take a series of actions that produce no reward in order to achieve a larger final reward. It is possible to circumvent this issue by learning an internal representation of the "value" of various situations. This "value function" (in mammals, the striatum/basal ganglia) is a mapping in the brain from the current sensory experience to an estimate of future reward. Now the action switching system can operate on the long-term expectation of rewards, not just immediate rewards, resulting in individuals which are able to achieve their goals much more effectively.

Brain Level 6: Motor automation
Repetitive motions are often represented as reflexes, but often it is important for an individual to learn novel motions during the course of a lifetime. A special brain structure (in mammals, the cerebellum) enables repetitive motions to be automated. Although the combination of value learning and action switching is a very flexible system, it can be wasteful for these well-learned motion sequences. This new brain structure provides a general-purpose action sequence memory that can offload these sequences, performing them at the appropriate time while allowing the action selection mechanism to focus on novel decisions.

Brain Level 7: Simple context representation
Any brain component that depends upon the state of the environment will perform better given an improved internal representation of the environment. Since the state of the external world cannot be accessed directly by these components, they are only as good as the brain's "mental model" of the world. So a specialized brain structure (in mammals, the archicortex/hippocampus) that can classify the state of the world into one of several distinct categories will help the brain represent value and choose actions more effectively.

Brain Level 8: Advanced context representation
Any further improvement of the "mental model" of the world is exceedingly valuable to decision making entities. An outgrowth of the initial simple pattern classifier appears (in mammals, the 6-layered cerebral cortex). This enhanced version extracts information content, computes degrees of belief about the world, and presents a summary in a simplified (linearly separable) form for use by other brain components like the value learning and action switching system.

Brain Level 9: Information-based rewards
A new explicit goal in the brain appears as a reward signal based on the information content provided by the entity's sensory inputs. The entity is thus intrinsically motivated to explore unexplored places and ideas. Before this new motivation, behaviors were mainly focused on survival and reproduction with little need for acquisition of new information. Now there is a strong drive to explore the world, simultaneously training and improving the brain's mental model. (An advanced context representation is useless without the motivation to fill it with information.)

Brain Level 10: General purpose working memory
All kinds of decisions can be improved by considering various action sequences before physically executing them. This requires the ability to simulate various state of the world within the internal representation, including sequences of actions and their expected consequences and rewards. This type of simulation is accomplished in a special short-term memory array (in mammals, the prefrontal cortex) that can be written to and read from. The read/write operations are extensions of the old action selection system: now, instead of being limited only to physical actions, the brain has acquired the mental actions "read from memory cell" and "write to memory cell."

Technological Evolution Level 0: First appearance
With the advent of working memory, the current combination of brain structures allows the construction and execution of extremely complex action sequences. This includes several unique new abilities. It is possible for individuals to make physical artifacts ("tools") from materials in the environment, enhancing the effectiveness of the body in various ways: extended reach, impact force, and leverage. Simultaneously, it provides an extension to the brain itself: the "tool-enhanced brain" has an extended long-term memory because it can record information in the environment rather than relying on brain-based memory. This greatly enhances the accuracy of cross-generational information transfer, which was first enabled by the onset of language. The accumulation of knowledge concerning advanced tool production results in a new intelligent process: technological evolution. The goal of this new evolutionary process is to produce artifacts that are the most stable in the space of the parent process's goals (i.e. the goals of the human brain), i.e. tools that provide the most benefit to humans.

Technological Evolution Level 1: Computing machines
The continual generation of new knowledge (driven by information-based rewards, collected/recorded/analyzed/organized with physical tools, and shared across multiple generations) enables the creation of increasingly complex physical artifacts. These artifacts are increasingly helpful to humans in achieving their goals (eating, socializing, reproducing, acquiring information, etc.), which support the goals of genetic evolution (proliferation of the most stable genes), which is confined by the simple goal of universal stability-based evolution. The evolution of technology operates at a scale much faster than genetic evolution, so it produces the equivalent of the next addition to the brain before genetic evolution has a chance. This product, the computing machine, is an extension to the most advanced area of the human brain, the prefrontal cortex. It allows the execution of arbitrary algorithms and simulations much more quickly than the prefrontal cortex itself, enabling humans to solve all kinds of symbolic problems more quickly and effectively.

Technological Evolution Level 2: Intelligent computing machines
Technological evolution continues to produce increasingly useful artifacts until a milestone is reached: an artifact with the same degree of intelligence and autonomy as the human, i.e. a human-level artificial intelligence. This artifact boosts the ability of humans to achieve their goals in an exponential way: machines continually design and build the next generation of machines, each better/faster/cheaper than the last. The artifact itself represents the next child intelligent process with goals defined by the parent intelligence (technological evolution), which could include anything that helps (or at least does not harm) its parent process in achieving its goals.

What's Next?
I won't try to speculate here about specifics, but it is expected that, barring some major catastrophe, the same overall process continues: intelligent processes tend to produce other intelligent processes which help achieve the goals of the parent process (or at least don't contradict them).

Lineage

The following is an abridged lineage of the intelligent processes described here, starting from the oldest ancestor:

1. Physical Evolution (goals: physical stability)
2. Genetic Evolution (goals: proliferation of genes)
3. Brains (goals: eat/sleep/avoid pain/socialize/reproduce/acquire information/etc.)
4. Technological Evolution (goals: help humans achieve their goals)
5. Intelligent Computing Machines (goals: arbitrarily defined by tech evolution)

(Not listed here are all kinds of cultural evolution, including language, music, the free market, etc. Each of these represents a separate branch of the intelligence tree, which, like the others, must not violate the goals of the parent intelligent process.)

Learning to Represent Patterns

2008-10-21T10:53:00.003-05:00

For the past several months I have been revisiting the issue of sensory and motor representation. I had implemented some initial ideas at the end of 2006, but I hadn't taken the time to study things in depth. My goal here is to represent real-valued sensory and motor spaces as efficiently as possible with limited resources. For example, say we're talking about visual sensory data (i.e. pixel arrays) involving 100 pixels (10x10 image), and we only have the resources to represent the 28 most common visual patterns. If we want to represent that visual space efficiently, we have to move our 28 basis vectors around the 100-dimensional space so that the resulting vectors represent the 28 most common visual patterns. This all must be learned online (in real time) as the system is experiencing visual data. Then, after learning, each incoming image will be classified as one of those 28 "categories."

One approach is based on the standard statistical approach of maximum likelihood learning. We assume the basis vectors are the center points of Gaussian kernels, each with a corresponding variance. For each data sample, we compute the likelihood of seeing that sample. (Given our current model, i.e. the 28 Gaussian centers and variances, what's the likelihood that the data sample was "generated" by our model?) Maximum likelihood learning attempts to adjust the Gaussian kernel positions and sizes within the data space to maximize this likelihood value over all data samples. The end result should be the model that best represents the actual data distribution.

Another approach is based on information theory, specifically the mutual information between the "input" and "output" variables. (This idea is usually attributed to Ralph Linsker at IBM Research, who called it "infomax.") I like to think of it this way: the data samples are coming from a real-valued input variable, V. We want to classify those samples into a discrete number of classes which represent the discrete class variable C. Each Gaussian kernel represents one class in C. Now, for each sample v, we want to transmit the maximum amount of information to the output class variable. We can do this by maximizing the mutual info between V and C, given the constraint of limited resources (i.e. a finite number of Gaussian kernels).

How do we do this? There are several ways. The simplest way to get started is to do gradient ascent on the mutual info. (Take the derivative of the expression for mutual info between V and C with respect to the Gaussian kernels' parameters, then continually adjust those parameters to increase the mutual info.) However, this direct gradient-based approach is hard to derive for mutual info because it depends on terms that are difficult to estimate; also, the resulting learning rules are (in my experience) unstable. But in general, any learning rule can be used as long as it generates a model with two properties: maximal prior entropy and minimal posterior entropy. Before seeing each data sample, the prior distribution over C should be uniform (maximum entropy/uncertainty), ensuring that each kernel is utilized equally (i.e. we're not wasting resources). After seeing each sample, the posterior distribution over C should be totally peaked on one class/kernel, representing minimal entropy/uncertainty. This is true when the Gaussian kernels are distinct, not overlapping. Thus, for each data sample received, we're reducing uncertainty as much as possible, which is equivalent to transmitting the greatest amount of information.

So I've been working on an infomax algorithm to represent real-valued data vectors optimally with limited resources. The tricky thing is that the posterior probability calculations require an accurate estimation of the probability density at each data sample. But I think I have a good solution to all these issues. The resulting algorithm appears to be great at pattern classification (< 10% error on the classic Iris data set and < 4% error on a handwritten digits set). More importantly, it should be just what I need for the core of my sensory and motor cortex systems.

Visualizing the Truth

2008-09-25T13:23:00.002-05:00

Here's an idea I submitted to Google's 10 to the 100th Project:

8. Your idea's name (maximum 50 characters)

Visualizing the Truth

9. Please select a category that best describes your idea.

Everything else

10. What one sentence best describes your idea? (maximum 150 characters)

To improve decision making, we store knowledge as a massive Bayesian belief network, display it intuitively, and enable extensive what-if simulations.

11. Describe your idea in more depth. (maximum 300 words)

Our brains are amazing decision making devices. For most problems involving a few variables, we can mentally simulate various outcomes before deciding, often with great results. For larger problems we can also rely on instincts/emotions (i.e. pre-computed solutions based on lots of experience). However, for the most complex issues, especially those critical decisions faced by government leaders, our human brains are not able to accumulate enough data or foresee enough outcomes. The number of possibilities is too great. (For example, banning DDT to save endangered birds seems reasonable, but then third-world farmers produce less food and many people die of hunger. Ideally, we could predict such long-term consequences from the start.)

My idea is to augment human decision making with Bayesian networks in a way that scales with the exponential growth of computer hardware. Bayesian networks enable us to represent knowledge intuitively as "beliefs about the world." Arguably, they function similarly to the brain's neocortex. Running on a large computer cluster, a massive Bayesian network could represent a repository of our society's knowledge. Unlike text-based systems, the belief representation would be ideally suited for decision making. This wiki-style belief network would be totally open to modifications by the global community (with abuse prevention) via a variety of input methods, including mobile devices. Users could add variables/nodes, modify connections/probabilistic relationships or utility values, etc. based on their own experience. (Software agents could offload some of this burden, e.g., by suggesting new connections based on inferred relationships.) Crucially, the belief network could be viewed in visually beautiful ways (e.g., see IBM's Many Eyes project). Users could perform extensive what-if scenarios. The result would be a concise summary of our collective beliefs and a substrate for meaningful simulations.

12. What problem or issue does your idea address? (maximum 150 words)

The problem is that of making hugely important decisions by fundamentally limited decision making machines (i.e. the human brain). My idea provides a way for us to avoid persuasive fallacies, to which our human brains are so susceptible, that have greatly hindered progress on large-scale decisions. For example, as presidential candidates propose new policies during their campaigning, citizens could immediately run the ideas through the belief network and see the expected outcomes. It would provide a simple, automatic way for the general public to cut through the BS.

13. If your idea were to become a reality, who would benefit the most and how? (maximum 150 words)

In general this technology could be used by anyone making difficult decisions. However, government policy makers are one of the most important target users. Members of congress could spend their time performing highly informative what-if scenarios more quickly and effectively than via spoken language. They could see immediate answers to questions like, "If we enforce this new policy, how does that affect key economic and environmental variables? How does it affect more distant variables, like diplomatic relationships? What are the expected probabilities of these outcomes? How should we make this decision in order to maximize expected utility given conflicting goals?" ("Utility" values could be determined by voting.) Imagine permanent client installations as centerpieces of congressional meeting places. Thus, the beneficiaries would include all citizens of any country whose government decides to utilize this technology.

14. What are the initial steps required to get this idea off the ground? (maximum 150 words)

We would need to design, implement, and test a prototype. This involves connecting a scalable Bayesian network software library (freely available) with a website displaying the belief network in an attractive manner. The Bayesian network could be hosted on a scalable compute platform, like Amazon's EC2. There should be a dead-simple (fun!) way to input new data via the website and mobile clients. Similarly, users should be able to perform simulations by making (temporary, client-side only) changes to the network and watching the results propagate through the belief network. Besides the basic technologies involved (Bayesian networks, hosting, and user input methods), the success of the project greatly depends on the visual attractiveness of the website and how much fun it is to use. Thus, it is critical to involve skilled graphic designers and possibly video game developers in the implementation.

15. Describe the optimal outcome should your idea be selected and successfully implemented. How would you measure it? (maximum 150 words)

The ideal outcome is that when facing complicated decisions, the proposed system would change our default decision making behavior, similarly to how Google search has changed our default memory recall behavior. The effect would be pervasive but undoubtedly very diffuse; measuring the effect would be difficult. One simple way might be through a public poll, e.g., "When faced with difficult decisions, do you: A) think about it for a while, B) decide on instinct, C) get advice from friends, D) consult wikitruth.com/visualtruth.com/whatever-its-called.com?" Ideally, using the system would be both fun (encouraging massive participation) and highly informative. The result is that our most important decisions would be based on more than just a few mental simulations, more than even instincts or emotions, but on the collective knowledge of humanity.

The Toilet Test for Machine Intelligence

2008-06-29T15:51:00.002-05:00

A machine could be considered intelligent if it makes a person uncomfortable to use the toilet in its presence.

Xenopsychology

2008-05-05T10:08:00.003-05:00

I just read this article, Xenopsychology, by Robert Freitas Jr. It asks the questions: What are alien minds like? What predictions can we make about alien goals, behaviors, and brains? What universals might exist in the psychology of creatures across the universe? What metrics do we have to compare different minds? "So far we have very little direct knowledge of alien minds -- but we have some fascinating bases for speculation."

What methods can we use to begin answering these questions? We can look at the diversity of brains on earth, studying their overall architectures and the evolutionary reasons those architectures exist. For example, one major division is that between ganglionic (decentralized network of independent sub-brains; less scalable) and chordate (central brain with many peripherals; very scalable) nervous systems. What are the benefits and drawbacks of these different types of brain design? Why did they emerge in the first place? Should we expect alien brains to fit one of these two patterns? Are there other options?

Concerning metrics, the author introduces the "sentience quotient" (SQ). "Generally the more information a brain can process in a shorter length of time, the more intelligent it can be." This is basically a measure of a brain's information processing efficiency. The exact definition is given as log(I / M), where I is the information processing rate in bits/second, and M is the mass of the machine. (Because I and M can cover very large ranges, the logarithm is used to focus on the ratio's order of magnitude.) So a small machine that can process quickly will have a higher SQ. The SQ ranges from -70 to +50. (Note that this definition only deals with processing speed, not solving problems/achieving goals. I like the more general definition of intelligence given by Shane Legg and Marcus Hutter: "Intelligence measures an agent’s ability to achieve goals in a wide range of environments."). The author suggests that there may be a "minimum SQ 'communication gap,' an intellectual distance beyond which no two entities can meaningfully converse." Just as rocks and trees are barely aware of our existence, let alone being able to communicate with us or understand our goals, we might find it difficult to communicate with or even sense the presence of an alien intelligence with an SQ 10 points above ours.

Here are some excerpts from the article:

"Will ETs be more or less emotionally motivated than humans? Will they have emotions foreign to us, or are there any universal emotions?"

"Extraterrestrial logicians may find many of our most enduring paradoxes to be trivially solvable, just as we may be able to resolve some of theirs equally effortlessly."

"Consciousness may be an emergent property of intelligence, a fortuitous feature of a terrestrial animal brain architecture originally designed for other jobs. Is it possible that there could exist yet higher-order emergents beyond consciousness?"

QuickMP 0.8.0 Released

2008-04-02T20:12:00.004-05:00

I just released the first version of QuickMP, which is a very small (one header file) piece of C++ code to ease the burden of shared-memory programming. It's ideal for applications where you perform the same operations repeatedly on lots of data.

The basic idea is that you convert your main C++ for loop from something like this:

// Normal for loop uses only 1 thread.
for (int i = 0; i < 1000000; ++i)
{
   processMyData(i);
}

...to something like this:

// Parallel for loop automatically uses 1 thread per processor.
QMP_PARALLEL_FOR(i, 0, 1000000)
   processMyData(i);
QMP_END_PARALLEL_FOR

A Cheap Barcode System Could Tie the Internet to the Real World

2008-03-11T09:33:00.008-05:00

Many people, including myself, are just starting to realize the potential of mobile barcode scanners. I'm not talking about using a mobile phone to generate barcodes for things like food orders (see this prototype of a Starbucks ordering system on the iPhone; thanks Tony for showing me this), although that mode of operation will also be revolutionary. I'm talking about using a mobile phone to scan barcodes on all kinds of objects in the physical world which provide a sort of hyperlink to more information about those objects, which is then displayed on the phone. Here are some examples to show how interesting this could be...

You could easily keep a written history of personal objects. You might find an old baseball bat in the attic, scan it, and read old entries, like, "May 5, 2012: Got this new bat for my birthday." Or, "July 12, 2015: This bat hit a winning homerun against the Tigers." You wouldn't have to keep a physical file cabinet full of records like this... they would be attached to the object itself.

The same principle would apply to public property. Imagine tying internet forums to specific places or objects. Forums usually assume a shared interest of some sort; in this case the thing you share is that you have experienced the same location or object. Sort of like bathroom stall graffiti, but everywhere... and hopefully more useful. Imagine walking through a park and sitting on a park bench. Embedded in the bench beneath a piece of glass is an inconspicuous little barcode. You scan it with your phone, which provides you with a few paragraphs about the park, the donor of the bench itself, etc.; sort of a Wikipedia entry. There are random text entries people have written, like, "August 21, 2010: It was rainy today, but I went for a walk anyway. Sat here for a half hour until it cleared up. Oh, be sure to smell the freesias about 30 ft NW of here," or, "November 7, 2011: I started reading A Brave New World here today. Has anyone read it? If not, check out the link. Man, Huxley was way ahead of his time." It also includes pictures people have taken nearby and "added" to the bench. And videos. Maybe even music recordings from the bandshell across the park. Each of these bits of info are tagged with dates, so the bench's entire history could be displayed as a timeline of local events. There might be problems, like people spamming the digital timelines of public property with advertisements. But we wouldn't have to hire people as spam filters to clean them up physically; all the data would be stored in the cloud, so there would be automatic spam filters.

Products you buy would no longer need paper instructions for assembly and usage. (Instead, you would get hyperlinked text, audio, and video instructions.) Nor would they need paper warranty statements. Even purchase information from paper receipts could be stored with a product's digital identity. When you buy a book, the store scans the book, gets your bank account info (by scanning your mobile barcode-producing device?), debits your account for the purchase, and transfers ownership from Barnes & Noble to you. Later, returning defective products is dead simple. Or, if you want to give the book to a friend, you perform a similar ritual to transfer ownership. So the object's digital identity could store the original purchase price, the current owner, and even the history of owners.

All kinds of physical objects could benefit from metadata. Easily keep car maintenance history with the car itself. Store your personal medical records on a bracelet. Stickers on produce would direct you to the harvest date, expected expiration date, the grower's location, and helpful recipes. Medication could provide personalized audio messages from your doctor and up-to-date warnings and recall notices. Musical instruments could hold audio recordings from previous owners. Paintings could link to more art from the artist. Power tools could give you tips on how to use them. The list of potential applications is really long.

Note that all of these things could be done without the barcode (e.g., keeping online documents which you can find via text search), but the barcode provides a context-relevant link to that data. Context is the key idea here: you can easily access the relevant info when and where it is needed. Replace (or augment) the searchable online file cabinet with hyperlinks directly from the physical objects.

Of course, other technologies could provide similar capabilities, but they're too expensive to be practical. Barcode systems are essentially available now, and they're so cheap, both in terms of the scanners (i.e. camera phones) and the individual barcode labels. They fit so easily into our existing infrastructure. You could print your own barcode labels at home and stick 'em on anything. Practically, all we need is a standard barcode format, barcode scanning software on our mobile phones, and free web hosting for all the metadata. Eventually such a system could evolve to include RFID tags, GPS devices, augmented reality displays, and Google Maps/Earth/Metaverse, but cheap barcodes could start laying the groundwork today.

GDC 2008

2008-02-26T10:53:00.008-06:00

Ray Kurzweil keynote on Thursday

Shana and friends storming the expo floor

Last week I went to GDC 2008 in San Francisco. As usual, I was a volunteer ("conference associate") for the conference. This year (and last year) I avoided attending a lot of programming sessions and focused more on things like game design. My purpose in going to the conference this year was mainly to keep tabs on the industry as a whole and to get a feel for where things are headed. On the technical side, the general trend continues to be more cores, threads, and parallelism. Also, there is a lot of experimentation with funky new input methods; some of the coolest ones, in my opinion, are the brain-computer interface devices from NeuroSky and Emotiv. It seems easier than ever to be an independent game developer because there are so many game portals out there to host indie games, like Steam and Kongregate.

Monday
I went to the Independent Games Summit all day. One interesting discussion was on the topic of defining rewards for the player... for example, is it more rewarding for a game to have good graphics and visual style or interesting game mechanics? I think they both have their place: the visceral aspects of a game, including visuals and audio, can provide an immediate draw to the player, but eventually even the best-looking games can get boring. The game mechanics provide the long-term rewards and can keep a player interested. So, in my opinion, good graphics draws people in, and good gameplay keeps them there. Also, someone mentioned the balance between boring and overwhelming, which I think is crucial because it forms the basis of curiosity and "information rewards" in our brains.

Other sessions at the Independent Games Summit discussed a lot of real life issues for indie developers, including legal issues. A lot of this was in the form of post-mortem advice from developers talking about specific games they had made.

Tuesday
I went to the last half of the games and education keynote. It seemed well thought out and very encouraging, though I can't remember any of the details now. There was a Serious Games Summit panel session on measuring what players learn when they play games... how do we define such a metric? Is this metric even necessary or desirable? This was a thought-provoking talk, although no consensus was reached.

Wednesday
I helped with a session on Xbox Live Arcade and attended the Microsoft keynote on XNA development for Windows, Zune, and Xbox. I also helped with a panel discussion on art outsourcing.

In the expo Sony had a cool demo of a head tracking system which used a single camera to detect the head's position (2D or 3D? I couldn't tell) and orientation using only face and eye detection.

Natural Motion's Euphoria is being used in the upcoming games Star Wars: The Force Unleashed and Grand Theft Auto 4. These games should be a great demonstration of Natural Motion's dynamic character animation techniques in real time. Up till now the main benefit of their tools has been to ease the burden of animating characters for movies. Having their system run in real time interactive games will really show off their technology and will probably have a profound impact on gamers and the industry.

Wednesday evening during the awards ceremony I sat next to Michael Callahan, co-founder of Ambient Corporation. Ambient is developing a system called the Audeo, a wireless neckband that enables telepathic chat by silently translating vocal nerve signals into a synthesized voice. So you could use it to make silent phone calls or google queries in public places. I remember a NASA group working on something similar a few years ago, but Ambient is ready to commercialize it. Pretty cool.

Thursday
Ray Kurzweil gave a keynote talk, which was similar to most of his other talks, but it was exciting to me to be in a room with thousands of people hearing his central thesis for the first time.

I helped with a session for Emotiv (one of two companies providing an EEG-based game input device) on their new SDK. Their system detects facial movements, "emotional" states (relaxed, tense, etc.), and cognitive/intentional state (e.g., thinking about moving an object through space). A short training period is required for some modes. They have a really nice control panel for testing all aspects of the system. One interesting point they made was that they could map brain states to existing keystrokes, enabling immediate usage with existing games.

I attended an Intel session on threading options for multicore machines and another programming session on undefined behavior in C++.

The Game Design Challenge 2008 was The Interspecies Game. This is always really entertaining. My favorite of the three designs was Bac Attack, a real-time strategy game against a petri dish of bacteria.

Friday
I mainly did random volunteer jobs throughout the day. I attended one session on legal issues for game music composers (e.g., maintaining IP vs. work for hire). Friday evening the conference volunteers had their final meeting, which is a mix of feedback for next year's conference and prizes for the volunteers. I won a copy of Star Wars: The Force Unleashed, signed by all the developers. :)

At one point during Friday afternoon I was scanning people's badges at the entrance to the expo floor. A gentleman from the academic world needed help finding the Carnegie Mellon University booth (which turned out not to exist). As I was helping him find his destination we got into a brief discussion regarding the game industry as a whole. He made the comment, "I hope these games can someday be used for something important rather than just entertainment." My immediate response was something like, "But entertainment is very important. Children playing with toys are actively learning many skills that will be needed later in life. Entertainment doesn't appear useful because the benefits are not immediate." Besides the personal benefits, at a societal level entertainment is part of what creates culture. This is sort of the main thesis of Leisure: The Basis of Culture.

Later I thought more about this issue, and Shana helped convince me that entertainment is indeed different from other endeavors. It is important in a way that is different from how food and national security are important. Entertainment is important for rich life, but other things are important for life at all. I think Maslow's hierarchy of needs helps clarify the issue: basic needs (e.g., nutrition and safety) must be satisfied in order to support higher needs, which I believe includes entertainment and play behavior. All needs are important, in the sense that we all want to reach the top of the hierarchy of needs, but some must be satisfied in order to support others.

Working on Action Selection

2008-01-10T13:35:00.000-06:00

In October I wrote about developing a simulated human test application. I have yet to begin implementing this because I'm still working out some issues with the basal ganglia component, which performs the essential task of action selection. It seems to me that action selection is the core required function of any intelligent system (see the wikipedia entry here), so it must work correctly.

I have written several test applications that focus squarely on learning proper action selection, including a 2d arm (1 degree of freedom) that must learn to reach a goal angle, a basic n-armed bandit test, and a 2d mobile robot that must seek reward objects. Once I'm confident that my system can solve these tasks robustly, I will continue down the path towards a simulated human test. Although I really want to start experimenting with a human-like test platform now, I have to take things one step at a time... If I just throw together an integrated control system without first testing each part in isolation, it will be impossible to debug any problems that arise.

Multitouch Game of Life

2008-01-09T12:41:00.001-06:00

I made a Game of Life application for VRAC's multitouch table. Check it out...

NIPS 2006 Talk, "Bayesian Models of Human Learning and Inference"

2007-11-30T12:20:00.000-06:00

This NIPS 2006 talk by Josh Tenenbaum, entitled "Bayesian Models of Human Learning and Inference," is a good overview of how Bayesian techniques are being used to model human intelligence. The NIPS page includes an abstract of the talk, the powerpoint presentation (170 slides), and a video of the talk (about 2 hrs long). (It looks like the large 900x600 video doesn't include sound, so don't download that one.)

This talk was interesting to me because I am using Bayesian networks (non-parametric, hierarchical) for sensory and motor representations. It's good to see that people are seriously considering Bayesian methods as realistic models of human intelligence.

Somatosensory Topographic Map Formation, Part 2

2007-11-13T21:25:00.000-06:00

(See Somatosensory Topographic Map Formation, Part 1 for more details.)

I ran some more tests, this time training topographic maps on a set of 3D models, including a hand, a human head, a wooden doll, a sword, and a full human body. Each image below is a sequence captured during the training process for each model. One interesting detail is that the maps learn to devote more resources to the regions that are sampled most often, which correspond to the parts of the models with lots of vertices. For example, the human head model has a lot of vertices in the mouth cavity, so it becomes well-represented in the topographic map.

This is the basic idea behind the homunculus representation of the sensory and motor cortices: the brain regions that represent the body learn to devote more real estate to those areas that need high resolution representations. Check out this image from the wikipedia article:

Burlington Hawkeye 52 Faces Article

2007-11-12T09:40:00.001-06:00

The Hawkeye newspaper, published in Burlington, IA (my hometown) does a special section called 52 Faces every Sunday. Each week focuses on a different person, usually a local resident in the Burlington area. My mother nominated me for this week's edition. The article talks about my research on brain-inspired artificial intelligence and a little about my polyphasic sleep experience.

Here is the article:

Somatosensory Topographic Map Formation

2007-11-02T14:52:00.000-05:00

In order to give my simulated human touch sensors, I need a representation of its relatively complex body surface transformed into a simple 2D array. The hard part is that the transformation must maintain topographic relationships (i.e. points near each other on the body surface should be near each other in the final 2D array). Fortunately, I already have a tool to do this: my topographic map code.

The following images show a topographic map learning to cover a simple body surface. In this case the body is just a human torso and arms. It starts out as a flat 2D sheet and learns to wrap itself around the body. After enough training it will cover the entire body. Where does the training data come from? I simulate random data points from the body surface... sort of like having someone constantly poke it in different places. The topographic map responds to these data points by moving part of itself closer to them. One cool thing about my method is that it automatically learns to represent the most-touched regions with higher fidelity; it's like how our brains use more real estate to represent our hands and faces. (In this example, I'm sampling the body surface uniformly, so the effect doesn't show up in the images.)

One way to think of this is a flat sheet of brain (somatosensory cortex) stretching itself in sensory space to represent the entire body surface.

Video: What We Still Don't Know

2007-10-23T10:36:00.000-05:00

This 48 minute video entitled "What We Still Don't Know" discusses some of the fundamental questions regarding the nature of the universe. It progresses through the following questions:

1. Was the universe designed by an intelligent entity, or did it come about through random interactions constrained by fundamental physical laws?
2. Why do the fundamental physical constants appear to be "tuned" precisely to support life?
3. Are there many universes (a "multiverse")? If so, maybe they all have different physical constants, and ours is just one of the few that supports life.
4. (Coming full circle...) In the same way that we can simulate life-filled universes in computers, is it possible that some superintelligent entity may have created our universe (perhaps with similar motivations to our own)?

Conway's game of life is used as an enlightening example of complexity arising from a simulated universe based on simple rules. Towards the end it includes some commentary by Nick Bostrom, one of my favorite philosophers.

Simulated Human Test Application Plans

2007-10-18T14:52:00.000-05:00

I'm getting to the point in my research where I need to begin testing the larger, integrated intelligent system. Enough of the brain-based components have been implemented and tested in isolation that it's time to hook things together and apply them to some initial tasks. I will probably start without all the components just to make it easier to debug problems at first. For example, I can ignore the cerebellum, prefrontal cortex, and possibly the hippocampus because they aren't totally necessary to solve very simple motor control tasks. The sensory cortex, motor cortex, and basal ganglia are necessary, though: at a bare minimum, you must be able to represent perceptions (sensory cortex), represent actions (motor cortex), and be able to choose which actions to perform based on perceptions and a learned value function (basal ganglia).

For an initial test environment, I plan to create a physically simulated human situated in a simulated room. (I've used this type of setup several times before, so it shouldn't take too long to make.) The simulated human will have tactile, visual, and vestibular sensory inputs, and it will have direct control over various muscles which move its limbs. The first task will be something like learning to roll over from its back to its stomach. Later testing could include large motor tasks like standing up and walking around. At first the room will contain only the human, but eventually I would like to add simulated toys in order to provide new learning opportunities.

So I'm excited to see how this goes. I have a lot of ideas of where to go next, but first I need to work out all the bugs on some basic motor control tasks.

Updated Website

2007-09-12T16:03:00.001-05:00

I recently overhauled my website. Now instead of using ugly pages created in Word, I'm using a Tiddlywiki-based system. I think it turned out pretty well. I spent a lot of time polishing up old projects to make them presentable online. This includes lots of new content, like screenshots, videos, and executable downloads (e.g., win32 executables for Opal Playpen and the Curious Robot Playground). Here are some highlights of the new stuff:

Singularity Summit 2007

2007-09-12T09:04:00.000-05:00

I attended the Singularity Summit 2007 this past weekend in San Francisco. Here's a good summary of the sessions. While I was there, I got a chance to speak with Steve Omohundro, Peter Norvig, Barney Pell, and Sam Adams.

The X-Prize Foundation announced their plans to enter the education space. They want to provide an Education X-Prize, and they were looking for suggestions from the audience at the summit on how best to frame the problem.

Here are some thoughts:

There is no general consensus as to when a singularity will happen, if it is likely to be beneficial or destructive to human life, or if one will happen at all. There isn't really an agreed-upon definition of what a singularity is. But that's the point of this summit: to define what we're looking for and how to influence it positively. And to raise awareness of a potentially huge issue. I think Ray Kurzweil's writing (like The Singularity is Near) continues to be a good reference, especially for people just joining the singularity discussion.

There seems to be a fair amount of venture capital available for startups in the artificial general intelligence (AGI) space. (Several investment firms were represented at the summit, including Clarium Capital, the John Templeton Foundation, and Draper Fisher Jurvetson.) Also, there are several stealth-mode startups working on AGI technology and products.

Festo's Fluidic Muscles

2007-08-27T09:06:00.000-05:00

Check out this very organic-looking artificial arm. There's a good video of it on that site. It uses fluidic muscles, an amazing product from the company Festo. Also check out some other biologically inspired projects here.

Concerning "Stuff"

2007-08-01T09:28:00.001-05:00

Stuff used to be more difficult and expensive to manufacture, so people would accumulate all they could. Basically, stuff used to be more valuable. Over the past century, stuff has become so mass-produced that it doesn't cost much to fill a house with it. Unfortunately, people haven't adjusted their values accordingly, so they actually do fill houses with it, usually to their own detriment.

As usual, Paul Graham has hit the nail on the head, this time regarding "stuff" - why we overvalue material possessions, collect too many of them, and let them exhaust us mentally:

...unless you're extremely organized, a house full of stuff can be very depressing. A cluttered room saps one's spirits. One reason, obviously, is that there's less room for people in a room full of stuff. But there's more going on than that. I think humans constantly scan their environment to build a mental model of what's around them. And the harder a scene is to parse, the less energy you have left for conscious thoughts. A cluttered room is literally exhausting.

Research Update

2007-07-21T15:45:00.000-05:00

It has been a long time since I last posted about my research. I have been avoiding putting too much online until it's ready (a different approach than my master's research, which was an open source software project). I still have a lot of work ahead, but things having been progressing very well. I seem to be finding answers to all of my big questions at a fairly constant rate.

Again, my goal is to build an intelligent machine based on the structure and computational functions of the mammalian brain. My general approach is to implement models of what I consider the core computational structures of the brain: the posterior cerebral cortex, the motor cortex, the prefrontal cortex, the hippocampus, the basal ganglia, and the cerebellum. I have been studying each of these elements at a time, attempting to extract its core function and purpose within the brain as a whole. For each one I am going through a series of phases: studying biological evidence, developing a computational model, implementing the model in software, and testing the implementation. Once I complete these phases for each component, I will begin a series of whole-system tests.

Testing these models has become a pretty involved process. You can't debug a hippocampus model implementation in a debugger like most other software; there are just too many variables to watch at once. Instead, I have to design a custom testing program for each component. For the case of the hippocampus model, I made an electronic music program where you can play notes on the computer keyboard. This lets you present songs to the hippocampus, allowing it to learn temporal patterns, and later recall songs from small pieces of the same songs. The end result is that by using the medium of sound/music, I can study the system's capabilities much easier than by watching huge arrays of variables in a standard debugger.

The following is a summary my current status. Obviously it's impossible to quantify these things exactly, but this is my best estimate.

Posterior Cortex
Model: 90%
Implementation: 90%
Testing: 90%

Motor Cortex
Model: 50%
Implementation: 90%
Testing: 60%

Prefrontal Cortex
Model: 50%
Implementation: 90%
Testing: 60%

Hippocampus
Model: 95%
Implementation: 95%
Testing: 95%

Basal Ganglia
Model: 90%
Implementation: 90%
Testing: 50%

Cerebellum
Model: 50%
Implementation: 20%
Testing: 0%

Modified Delta Learning Rule Part 2

2007-05-18T16:03:00.000-05:00

Another modification to my delta learning rule is motivated by my preference for working with real time values (t=0.13s, t=0.16s, t=0.19s, ...) as opposed to abstract discrete time values (t=1, t=2, t=3, ...). This distinction is important for interactive real time applications, like robotics and video games.

I want to be able to specify how much error is reduced per second (e.g., an error reduction rate of 0.3 means that the error is reduced by 30% per second). Here's how I do it:

error_reduction_rate = 1 - exp(-step_size / error_reduction_tc)

"step_size" is the amount of real elapsed time between weight updates (it's best if this is a fixed constant, both for stable learning and to avoid recomputing the error reduction rate constantly). "error_reduction_tc" is a time constant which determines how fast errors are reduced.

For example, an error reduction time constant of 2.0 means that the error will be reduced to about 37% of its original value after 2.0 seconds of updates. If weight updates occur every 0.05 seconds, this yields an error reduction rate of 0.02469. If we change the time constant to 0.1, leaving the step size at 0.05, the error reduction rate jumps up to 0.3935 since the time constant is much faster. Note: it's important to keep the step size smaller than the time constant; otherwise, things can get unstable.

A Delta Learning Rule with a Meaningful Learning Rate

2007-05-18T15:12:00.000-05:00

Recently I was looking for a way to train a simple linear neural network using the delta rule in such a way that I could specify exactly how much error is reduced on each weight update. The usual delta learning rule for a single linear neuron is:

delta_w_i = learning_rate * error * x_i

In my opinion, the learning rate parameter lacks an intuitive interpretation. Ideally it would represent exactly how much error is reduced per update, but it doesn't. It is usually just set to some small constant, like 0.01, which is hopefully not too small (slow convergence) or too large (instability). My goal was to find a modified learning rule with a learning rate-like parameter which could reduce the error by a specific amount on each weight update (e.g., a value of 0.2 would reduce the error by 20% per update).

Temporarily assume a network with only one input/weight. Also assume that the goal is to reduce the error by 100% within a single step. (These assumptions will be relaxed later.) The output function is:

y = w * x

The error is:

error = target - y

In order to achieve zero error in one step, we need the following to be true:

y = target = (w + delta_w) * x

So we need to solve for the learning rate which yields zero error after one step:

delta_w = target / x - w
learning_rate * error * x = target / x - w
learning_rate = (target / x - w) / (error * x)
= [(target / x - w) / (error * x)] * (x / x)
= (target - w * x) / (error * x^2)
= (target - w * x) / ((target - w * x) * x^2)
= 1 / (x^2)

So a learning rate of 1 / (x * x) will reduce the error in the system to zero after one step. We can easily make this work for multiple inputs/weights by simply dividing by the size of the input/weight space n:

learning_rate = 1 / (n * x^2)

Of course, we don't usually want to reduce the error completely in one step, so we replace the 1 with an "error reduction rate." This quantity, which is a value within [0, 1], determines the amount of error to be reduced on each weight update. It is a rate with meaningful units (0.01 x error reduction percent per weight update). For example, an error reduction rate of 0.4 will reduce the error by 40% on each update compared to the error value on the previous step. It is equivalent to 1 - error(t+1) / error(t). Now the desired learning rate becomes the following:

learning_rate = error_reduction_rate / (n * x^2)

Now we can modify the delta learning rule by replacing the traditional learning rate:

delta_w_i = error_reduction_rate * error * x_i / (n * x_i * x_i)
= error_reduction_rate * error / (n * x_i)

One problem remains: we can't divide by zero when the input (x_i) values are zero. To remedy this, we only update weights associated with active (non-zero) inputs. Also, instead of dividing by n, we divide by the number of active inputs m:

only for non-zero x_i:
delta_w_i = error_reduction_rate * error / (m * x_i)

This looks very similar to the original delta rule except for three major differences:

The learning rate has been replaced with the error reduction rate, a quantity with a much more meaningful interpretation.
The weight deltas are divided by m, the number of active inputs. This essentially scales the error by the number of weights that contribute to the error.
The weight deltas are divided by their associated input (x_i) values. This is an interesting deviation from the original delta rule which instead multiplies them by their input values.

UPDATE (5/23/07): It turns out that there's a problem with this modified delta rule. My assumptions concerning how the single input/weight case generalize to multiple inputs/weights were incorrect. Fortunately, only a small change is needed. Instead of dividing by the input value squared, we need to divide by the input vector length squared, which serves to normalize the weight deltas by the energy of the input vector:

delta_w_i = error_reduction_rate * error * x_i / length(x)^2

length(x) here is the Euclidean norm of the input vector. If length(x) is zero, we simply avoid modifying any weights, which is valid because all x_i values are zero which would produce weight deltas of zero. We are still able to specify the error reduction rate in an intuitive way, which was the motivation behind my search for a better delta rule.

Interestingly, this turns out to be equivalent to the normalized LMS rule. (LMS, or least-mean-square, is another name for the delta rule). Normalized LMS is described here and in Haykin's Neural Networks book, 2nd edition, p. 152.

Randall C. O'Reilly's Wiki

2007-05-14T11:10:00.000-05:00

This is one of the best things I've read in a while. It's a very detailed, personal account of Randall O'Reilly's belief system, covering the brain, epistemology, religion, physics, politics, and much more. I just finished reading the whole thing, which was very refreshing.

I especially enjoyed the constant focus on developing self-consistent beliefs as a practical goal: "Self-consistency is probably the only useful criterion for establishing the "truth" of a belief system. It is itself consistent with the fact that we cannot escape our fundamental subjectivity..." Here's another great quote: "You might argue that this is all circular. It is. However, if you make a big enough circle that encompasses all of experience, then I don't see what the problem is."

I think self-consistency is implemented in the brain as a Bayesian network. New pieces of evidences are constantly coming in through sensors and being passed around among nodes to update their beliefs about the world. The whole belief propagation mechanism is designed to maintain self-consistent beliefs as well as possible; complete self-consistency isn't always achieved, but it's at least maximized. Interestingly, we are still able to bias the system by focusing attention on certain details while ignoring others, which can basically keep certain pieces of knowledge from affecting our belief systems.

Polyphasic Sleeping Log

2007-05-07T16:31:00.000-05:00

Back in 2005 I tried a polyphasic sleep schedule (specifically, the Uberman schedule) for almost a month. It was loads of fun after the first two weeks were over. I'd say I have a much different perspective on sleep now. During the process I kept a daily log, which I forgot about until now. I thought I'd post it here...

Related links:
http://www.kuro5hin.org/story/2002/4/15/103358/720
http://www.jonnyhenderson.com/secret/sleeping.php?week=1

General comments:
* Take vitamins daily.
* Keep a healthy diet.
* Drink lots of fluids.
* Learn to fall asleep fast. With only 20 minutes to sleep at a time, you'll need to fall asleep as soon as possible. Be able to make yourself extremely bored when you're lying down; immediately forget any thoughts that come up. This takes practice.
* Don't oversleep, and don't miss naps. Having a rigid sleep schedule helps your body adjust faster.
* I found that during the induction period, it's much harder to stay awake at night. Be especially careful during the nightly naps that you don't oversleep.
* Before the evening starts, have a list of projects written down. It's really hard to think of new things to do later.
* If you start to get overpowered by the urge to sleep, do something different: eat, play a video game (much better than watching a movie since it's interactive), go for a walk (I enjoy walking in the morning at sunrise), etc.. Don't just sit (or lie) there wishing you weren't so tired.
* If you get heartburn, it's probably from eating within 2 hours before sleep. Lying down lets fluids travel up the esophagus easier. (I would think the sphincter muscle down there would keep everything in the stomach, but maybe it's not perfect.) Something that helps is sleeping on an incline. Try putting a few wadded up blankets under the head of your mattress.
* Summary of my induction period:
- Days 1 & 2: Felt like I had missed a lot of sleep.
- Days 3 & 4: Didn't feel terribly sleepy anymore most of the time. Felt generally normal.
- Days 5 & 6: Felt kind of queasy all day. Felt sleepy during the night if I didn't keep busy.
- Days 7 - 10: Felt mostly normal, but still a little sleepy during the night if I didn't keep busy.
- After day 10: Felt mostly normal.

------------------------------------------------------

Day 1: Saturday, 7-23-05
Total sleep: 1:40
* Started at 12 a.m.
* 4 a.m.: I took my first nap. I slept most of the time and woke up easily. After getting up, I didn't feel too much different; I just felt like I was up really late.
* 4:20 a.m. to 6 a.m.: I read a magazine.
* 6:30 a.m. to 7:30 a.m.: I took a walk and listened to the Lord of the Rings BBC radio show.
* 8 a.m. to 8:20 a.m.: I took my second nap. I felt more tired after waking up this time, but I was still able to get up easily.
* 8:20 a.m. to 12 p.m.: I ate breakfast and played video games.
* 12 p.m. to 12:20 p.m.: I took my third nap. I felt rested afterwards, though a little groggy. Still not bad. Once I get up and move around, I feel pretty awake.
* 12:20 p.m. to 4:15 p.m.: Ate lunch. Ran errands around town... but accidentally didn't get home till after 4pm.
* 4:25 p.m. to 4:45 p.m.: Took a nap, but probably only slept for less than half the time. I was really awake from running errands in the 101 degree heat; also, I had just found that I received a scholarship for the next school year, so that made it a little hard to sleep.
* 4:45 p.m. to 8 p.m.: At supper with Ken.
* 8 p.m. to 8:20 p.m.: Took a nap at Ken's place. Didn't sleep very much.
* 8:20 p.m. to 11:30 p.m.: Played video games with Ken until I felt pretty tired.
* 11:30 p.m. to 12 a.m.: Drove home from Ken's. Got ready for a nap.

------------------------------------------------------

Day 2: Sunday, 7-24-05
Total sleep: 4:10
* 12 a.m. to 12:20 a.m. Took a nap.
* 12:20 a.m. to 4 a.m.: When I woke up from my nap, I really wanted to keep sleeping. It took a long time before I started feeling awake. Played computer games and watched TV.
* 4 a.m. to 6:30 a.m.: Tried to take a nap, but accidentally slept way too long.
* 6:30 a.m. to 8 a.m.: Listened to the Lord of the Rings BBC radio show while trying to stay awake.
* 8 a.m. to 8:20 a.m.: Took a nap.
* 8:20 a.m. to 12:15 p.m.: Went to church.
* 12:20 p.m. to 12:40 p.m.: Took a nap.
* 12:40 p.m. to 4 p.m.: Watched TV and listened to the Lord of the Rings BBC radio show.
* 4 p.m. to 4:20 p.m.: Took a nap. I've noticed that it's much easier to get up after a nap during the day than after one at night. Maybe this will change after another week or so.
* 4:20 p.m. to 8 p.m.: Priced computer parts online.
* 8 p.m. to 8:20 p.m.: Took a nap.
* 8:20 p.m. to 12 a.m. Read Uberman sleep schedule info on the web.

------------------------------------------------------

Day 3: Monday, 7-25-05
Total sleep: 2:10
* 12 a.m. to 12:20 a.m. Took a nap.
* 12:20 a.m. to 4 a.m.: Read more Uberman sleep schedule experiences.
* 4 a.m. to 4:10 a.m.: Took a nap. Woke up early because I had to use the bathroom. I didn't want to try to go back to sleep for ten minutes.
* 4:30 a.m. to 5:15 a.m.: Took a walk and listened to the Lord of the Rings BBC radio show.
* 5:15 a.m. to 8 a.m.: Read about C++ threading libraries. Took a shower.
* 8 a.m. to 8:20 a.m.: Took a nap.
* 8:20 a.m. to 12 p.m.: Thesis work.
* 12 p.m. to 12:40 p.m.: Took a nap. I woke up easily, but I didn't actually sit up. Instead, I fell asleep for another 20 minutes.
* 12:40 p.m. - 4 p.m.: Thesis work. I'm glad I can actually do something productive at this point. I felt sort of lousy earlier today, but my 8 a.m. nap really helped. I almost feel normal.
* 4 p.m. to 4:20 p.m.: Took a nap.
* 4:20 p.m. to 8:20 p.m.: Went out for supper and bought groceries. Didn' finish groceries quite on time, though.
* 8:20 p.m. to 8:40 p.m.: Took a nap.
* 8:40 p.m. to 12 a.m.: Played video games, read a book, and read about 'gnuplot'.

------------------------------------------------------

Day 4: Tuesday, 7-26-05
Total sleep: 7:30
* 12 a.m. to 6:30 a.m.: Took a nap. This was really disappointing after doing so well yesterday. I just didn't wake up to my alarm. I decided to skip my 8 a.m. nap and then continue napping like normal.
* 6:30 a.m. to 11:45 a.m.: Ate breakfast. Read literature on threading and OpenMP.
* 11:45 a.m. to 12:05 p.m.: Took a nap.
* 12:05 p.m. to 4 p.m.: Ate lunch. Tried to buy a motherboard at Best Buy, but they didn't have any in stock.
* 4 p.m. to 4:20 p.m.: Took a nap.
* 4:20 p.m. to 8 p.m.: Priced computers online and read about wiki software. Ate supper.
* 8 p.m. to 8:20 p.m.: Took a nap.
* 8:20 p.m. to 12 a.m.: Read more stuff online. Played video games.

------------------------------------------------------

Day 5: Wednesday, 7-27-05
Total sleep: 2:00
* Worked at VRAC throughout the night, which was pretty fun. I felt alert most of the time, but I didn't end up being too productive. Did research throughout the day.

------------------------------------------------------

Day 6: Thursday, 7-28-05
Total sleep: 2:00
* Worked at VRAC throughout the night again. I felt more sleepy this time, though. I must be adjusting still. Worked on research/code throughout the day.

------------------------------------------------------

Day 7: Friday, 7-29-05
Total sleep: 2:00
* Stayed home during the night. It was difficult to stay awake while I wasn't working on the computer. For the past day or so I've felt a weird queasy feeling with stomach cramps. I hope that goes away soon.

------------------------------------------------------

Day 8: Saturday, 7-30-05
Total sleep: 3:20
* Accidentally slept from 12 a.m. to 2:30 a.m. Skipped 4 a.m. nap. Didn't sleep during 12 p.m. nap (on Ken's trampoline outside). Slept 10 minutes during 4 p.m. nap. Still have the weird stomach pains sometimes.

------------------------------------------------------

Day 9: Sunday, 7-31-05
Total sleep: 3:25
* Accidentally slept from 8 a.m. to 9:45 a.m. No other problems.

------------------------------------------------------

Day 10: Monday, 8-1-05
Total sleep: 2:00
* Worked at VRAC 1 a.m. to 6:30 a.m. I still have stomach pains most of the time. I can't tell if it's muscle cramps or heartburn (located just under my breastbone).

------------------------------------------------------

Day 11: Tuesday, 8-2-05
Total sleep: 2:00
* Worked at VRAC 2 a.m. to 7:30 a.m. (replaced the motherboard in my old desktop computer that died about a year ago). I think the stomach pains aren't as bad when I don't eat large meals, so I'll try to spread out my eating more throughout the day.

------------------------------------------------------

Day 12: Wednesday, 8-3-05
Total sleep: 3:00
* Worked at VRAC 2 a.m. to 7:30 a.m. It took a while to wake up after my 12 a.m. nap. I hope that within a few days (the 2 week mark) I won't be as tired during the night. Oops, I accidentally slept from 12 p.m. to 1:20 p.m.

------------------------------------------------------

Day 13: Thursday, 8-4-05
Total sleep: 2:00
* Worked at VRAC 2 a.m. to 7:30 a.m.

------------------------------------------------------

Day 14: Friday, 8-5-05
Total sleep: 3:30
* Stayed home during the morning this time. Overslept from 4 a.m. to 5:50 a.m. Didn't skip my 8 a.m. nap.

------------------------------------------------------

Day 15: Saturday, 8-6-05
Total sleep: 2:00
* Stayed home during the morning. I think that my stomach pains were probably intense heartburn. I read today that eating just before lying down can cause heartburn (because gravity isn't keeping the stomach acid down). So I think I'll try to limit how much I eat within the 2 hours before a nap.

------------------------------------------------------

Day 16: Sunday, 8-7-05
Total sleep: 3:10
* Overslept from 8:20 a.m. to 9:50 a.m.

------------------------------------------------------

Day 17: Monday, 8-8-05
Total sleep: 3:30
* Overslept from 8:20 a.m. to 10:10 a.m.

------------------------------------------------------

Day 18: Tuesday, 8-9-05
Total sleep: 2:00
* Took my 8 p.m. nap at 9 p.m. since we were in Des Moines at that time. I've noticed something weird over the past 3-4 days: periodically I have the sensation of something pressing against my forehead. It feels like someone's fingers. Also, the more I focus on it, the stronger the feeling. If I think about something else, the feeling goes away. It also goes away if I briefly touch my forehead.

------------------------------------------------------

Day 19: Wednesday, 8-10-05
Total sleep: 7:30
* Overslept from 12 a.m. to 6:30 a.m. Wow. I don't know how that happened. I did feel really rested when I woke up, even if I was overwhelmed with guilt. I'm going to skip my 8 a.m. nap and start again at noon.

------------------------------------------------------

Day 20: Thursday, 8-11-05
Total sleep: 2:00
* Today I didn't feel too much different than normal, which was surprising after sleeping so long yesterday. I got a new computer yesterday and spent the whole day today installing software.

------------------------------------------------------

Day 21: Friday, 8-12-05
Total sleep: 2:00
* Went camping Friday through Sunday.

------------------------------------------------------

Day 22: Saturday, 8-13-05
Total sleep: 6:00
* Fell asleep multiple times during the morning.

------------------------------------------------------

Day 23: Sunday, 8-14-05
Total sleep: 3:10
* Overslept 8 a.m. to 9:30 a.m.

------------------------------------------------------

Day 24: Monday, 8-15-05
Total sleep: 2:50
* Overslept 4 p.m. to 5:10 p.m. The sensations on my forehead are pretty constant now. I notice them more when I lie down for a nap.

------------------------------------------------------

Day 25: Tuesday, 8-16-05
Total sleep: 2:30
* Overslept 12 p.m. to 12:50 p.m.

------------------------------------------------------

Day 26: Wednesday, 8-17-05
Total sleep: N/A (I am no longer doing polyphasic sleep.)
* Overslept 12 a.m. to 2:20 a.m.

I'm making the conscious decision (not affected by lack of sleep, as far as I can tell) to go back to monophasic sleeping. My reasons are the following:

- So far I haven't felt up to my normal mental capacity. This is fine in most situations, but not when doing research. I never succeeded in going a full week without oversleeping, though. Maybe then I would have felt normal.
- Of course, there are still unknown health risks as this hasn't been studied in people for long periods of time (i.e. years).
- Even though I can now mostly avoid heartburn, I still feel a weird lump in my chest underneath my breastbone. I feel it when I lean forward. I have no idea what this is, but it has only developed since I started polyphasic sleep.
- I feel like I've gained a lot of weight since I started. I would guess about 10 pounds (started at 182, now up to about 192). This is strange to me since I thought staying up around the clock would help me burn more calories. I even started exercising (using elliptical machines) for 30 minutes a day, 3 times a week, over the past two weeks. Maybe sleep stages 3 and 4 (which I'm not getting) are involved in regulating metabolism.
- My wife doesn't like sleeping in an empty bed most of the night.
- If I am going to stop, now is a good time since school is starting in a few days (on Monday).

That being said, I'm going to miss polyphasic sleeping. It was great having so much free time that I actively had to think of things to do. Maybe I'll try it again someday. I think it'll be easier to start next time since I know what to expect.

------------------------------------------------------

Day 27: Thursday, 8-17-05
Total sleep: 12 hours! (This includes part of yesterday: 8 p.m. to 8 a.m.)
* I feel good today. I can't quite explain it, but I just feel generally good... and sad. I'm a little groggy after having slept for 12 hours, but that should only last a day or two. The weird lump in my chest is gone. I can't help feeling like I failed, but I don't think that's the right attitude. At least I got a month of experience with polyphasic sleep.

Sumotori Dreams

2007-04-30T11:06:00.000-05:00

Sumotori Dreams website

This is amazing. It's a physically simulated sumo wrestling game. You provide simple high-level control signals (walk forward, push, etc.) in order to defeat your opponent, and the wrestlers try to do those actions while maintaining their balance. It's as if they have their own reflexive control systems to stand up straight without falling over, and it works fairly well. It's loads of fun to watch and play. And it's incredibly small... collision detection, physics (with shattering blocks, even), sound effects, music, graphics code (with shadows), textures, etc. all fits in an 87k executable.

HCI Forum/Emerging Technology Conference 2007

2007-04-30T09:28:00.000-05:00

My graduate program just had our annual open house event last week (ETC 2007). Speakers included Don Norman, Neal Stephenson, Guy Kawasaki, and Raghu Ramakrishnan.

We unveiled the newly-upgraded C6, a 6-sided VR cave display with 100 million pixels of total resolution (4096 x 4096 per wall)... double that with stereo enabled. For this event we've been working on a tropical island demo. Here's a picture of Tom Batkiewicz running the app:

Do Schools Kill Creativity?

2007-04-16T21:28:00.000-05:00

This is a great talk by Sir Ken Robinson on how we are educated out of creativity. He says we are taught to be afraid to make mistakes, which I think is very true and very frustrating.

"Our education system has mined our minds in the way that we've strip-mine the earth for a particular commodity."

Why I Love The Matrix

2007-04-16T17:04:00.000-05:00

I love The Matrix, and it's not because of the action scenes or special effects. (If those were the movie's best attributes, I probably would have watched it only a couple of times.) I love The Matrix because it represents very advanced forms of three crucial ideas: virtual reality, artificial intelligence, and education.

Bayesian Model of Curiosity

2007-03-28T15:49:00.000-05:00

As I continue to implement and experiment with a context representation based on Bayesian inference, I have considered various ways to implement curiosity. The main component I need is a prediction error based on the difference between the system's predictions and reality. Given the tools available in the Bayesian framework, the most obvious method would be to use the prior and posterior distribution. The prior represents the systems predictions, and the posterior represents reality (approximately). So the prediction error would be the difference (possible KL divergence) between the prior and posterior distributions. (One implication is that if the incoming evidence (likelihood) contains no new information, the prior and posterior will be equal, resulting in zero prediction error.) The prediction error can then be used to generate a curiosity reward, either for "surprising" events or for those that yield high learning progress (reduction in surprise over time).

After I went through all the trouble of figuring this out, I came across this mathematical model of surprise based on Bayesian statistics (in which surprise is measured in units of "wow").

QuickProf 0.9.0 Released

2007-03-22T09:06:00.000-05:00

Just a quick note to say that I just released version 0.9.0 of QuickProf, a very small (one header file) cpu profiling API for C++ applications on all platforms. It's easy to add it to your projects, and the timing measurements it provides are very useful for optimizing performance. For example, it can give you an overall timing summary when your app finishes, or it can generate an output file for graphing your app's runtime performance.

For example, I use QuickProf to profile the major components of my context representation code (inference, propagation, and adaptation). I have it print out an overall summary at the end, which usually gives me something like this:

adaptation: 23.2914 %
inference: 11.5562 %
propagation: 0.200819 %

...and I have it output a timing data file, which I then plot with the Python library Matplotlib:

The Universe as a Computer Simulation, Quantum Mechanics

2007-03-12T19:52:00.000-05:00

I had a thought last week. Say you wanted to build a simulated universe, and your simulation would contain intelligent beings. To conserve computational resources, you would want to avoid simulating aspects of the universe that are not observed by its inhabitants. It would be like a colossal view frustum culling process. For example, events that are very small or very far away from an observer might not need to be computed.

If our universe is a computer simulation, maybe that's why we see quantum mechanical effects. The detailed positions of individual particles remain in indeterminant states until they are observed, at which point their wave functions collapse (i.e. their states are computed in more detail).

Interestingly, this entire thought process assumes that the observer has a very important role in the simulation, as if the universe were designed for intelligent beings.

GDC 2007

2007-03-12T15:10:00.000-05:00

I just got back from the Game Developers Conference 2007 in San Francisco. I hung out with Ken Kopecky, Andres Reinot, and Josh Larson most of the week.

Here is a very terse summary of each day at the conference:

Monday
I attended Creativity Boot Camp, a full-day tutorial by Paul Schuytema. The morning was more lecture style, covering a set of practical tips on how to live a lifestyle that fosters creativity. In the afternoon the audience formed groups to work on several exercises. One was a problem solving task (deciding which objects to bring along when trying to escape a mall full of zombies). Another was a board game design task based on a random set of pieces, randomizers, and board layouts. Alexey Pajitnov happened to be there observing the groups as they worked.

Tuesday
I attended the day-long Independent Games Summit, which included sessions on prototyping, bootstrapping an indie game dev project, retail distribution, indie development logistics, the casual game market (presented by Eric Zimmerman of gamelab), the story behind Cloud, marketing for indie games, physics games (presented by Matthew Wegner, creator of Fun-Motion), and a panel discussion on the future of indie games.

Wednesday
At the Sony keynote they presented a "home" feature for the PS3. It looks like a SecondLife kind of thing with much better graphics. They also introduced an great-looking game called LittleBigPlanet. I went to a round table discussion on non-profit games, moderated by Martin de Ronde of OneBigGame. I also went to a round table on security and privacy in games, which touched on the legal and marketing issues related to storing user data. Finally, in the evening we went to the Independent Games Festival & awards ceremony and Game Developers Choice awards.

Thursday
Shigeru Miyamoto gave the Nintendo keynote, discussing his vision and how it relates to that of Nintendo. One interesting point was that his goal for the original Zelda for NES was to introduce a new form of communication: instead of playing the game in isolation, gamers were forced to talk to each other about how to solve puzzles. Miyamoto also showed a video of Super Mario Galaxy.

At the annual Game Design Challenge, three designers were presented with the task of creating a video game using a needle and thread interface. Alexey Pajitnov won. I then attended a game design talk by Clint Hocking entitled Exploration: From Systems to Spaces to Self. The talk was based on the idea that humans have a need to explore things and that every game is an exploration game. "Exploration" was defined in several ways, including system exploration (the general idea of exploring the properties of some system, like the mechanics of a video game), spatial exploration (the special case where the system in question is defined spatially, e.g., a physics simulation). A third type, rarely seen in video games, is self-exploration, which refers to the process of putting ourselves in situations that lead to us learning something about ourselves.

Chris Hecker gave a talk on "how to animate a character you've never seen before," referring to the challenge of animating the user-designed creatures in SPORE. In the evening we went to the Programmer's Challenge, a game show with six of the industry's leading programmers.

Friday
Tom Leonard from Valve gave a talk on making the Source engine scalable to multiple cores. It sounds like they built a custom framework to support several different concurrency models (course-grained and fine-grained parallelism) for different situations. Chaim Gingold gave a talk entitled SPORE's Magic Crayons, which was about limiting the parameters available for user-generated content in order to push the space of probable designs into the space of desirable designs. In other words, for SPORE it was important to avoid giving users knobs that tend to yield ugly results.

We went to the Video Games Live concert in the evening, which included performances by Koji Kondo and Martin Leung (aka the Video Game Pianist).

Planning, a.k.a. Time Travel in the Brain

2007-01-24T10:52:00.000-06:00

The January 29th issues of Time is focused on the brain (The Brain: A User's Guide). One interesting article is Time Travel in the Brain. It explains mental "time travel" as our ability to remember past situations and to simulate future scenarios, jumping through time at arbitrary speeds.

The purpose of this function, as explained in the article, is basically the same as that of planning in reinforcement learning:

Moving around in the world exposes organisms to danger, so as a rule they should have as few experiences as possible and learn as much from each as they can. Although some of life's lessons are learned in the moment ("Don't touch a hot stove"), others become apparent only after the fact ("Now I see why she was upset. I should have said something about her new dress"). Time travel allows us to pay for an experience once and then have it again and again at no additional charge, learning new lessons with each repetition.

Concerning how often we switch into "planning mode":

Perhaps the most startling fact [... is ...] how often it does it. Neuroscientists refer to it as the brain's default mode, which is to say that we spend more of our time away from the present than in it.

I agree. And that's how agents in the Verve library are designed to work when in planning mode: for each "real" time step, the agent simulates many time steps (default=50, if I remember correctly) through the use of its learned predictive model.

Testing a New Context Representation on Visual Images

2006-12-14T11:34:00.000-06:00

This semester I've been working hard to design a totally new type of "context representation." The purpose of this system is to represent sensory information in a form that is compact, retains as much information as possible, and is useful for behavior. What I have so far is a hierarchical inference system that can do nonlinear dimensionality reduction on the input data while maintaining topographic relationships at each level.

These two pictures show a single layer during and after training on a set of images of contrasting edges. Notice the smooth topographic representation.

The next one shows the result of training on a set of line images.

The next picture shows a single layer in training above two other images below. The bottom left is the actual input image, and the bottom right is a reconstruction of the input image (i.e. after compression and decompression). "Reconstruction" here is performed with a generative model. Note that the compression level here is easily adjustable, which gives a clear speed/accuracy trade off.

The final picture shows a hierarchical setup. Again, the bottom images show the actual input (left) and reconstruction (right). In the middle is a layer of four processing elements with limited receptive fields (each looks at one fourth of the input image). On top is a layer connected to the layer below; its receptive field covers the entire input image. Again, notice the smooth topographic representation in the middle layer, even between the four processing elements.

I'm still in the middle of running lots of experiments to verify that everything is working properly. I really want to make sure I'm getting correct results (the reconstructed images should match the inputs well) with efficient runtime performance (which should be good with a hierarchical architecture). I wouldn't feel too bad spending another semester testing this thing since it's one of the most critical components of an intelligent system. Lots of other components are context-dependent, meaning that a good context representation will enable other parts to do their jobs better.

New Tyler & Shana Blog

2006-12-14T10:43:00.000-06:00

Shana and I started a new blog for things that relate to both of us. We started it off with pictures of our new house. Check 'em out.

Microsoft Robotics Studio 1.0

2006-12-13T09:35:00.000-06:00

Microsoft Robotics Studio 1.0 was just released. This letter describes what it's all about, as does this video.

It's pretty exciting to have a standard development environment for robotics applications. If it's robust enough, I might end up using it for research. In the past I have used OPAL/ODE for physics and OGRE for visualization, which is great because I have full control over the entire simulation, but it requires a lot of overhead to setup each new control task. Using Microsoft Robotics Studio would save me tons of time and give me lots of new features (e.g., debugging sensors via a web browser).

Mario Paint Caricature Video, 1993 CES

2006-12-07T15:45:00.000-06:00

At the Consumer Electronics Show in Chicago, 1993, Nintendo had artists at their booth showing off the new SNES game Mario Paint by doing live caricatures of people. This is the caricature video of my brother (Tony, on the right), and me (Tyler, on the left).

Videos - Reinforcement Learning Control Tasks

2006-11-16T10:54:00.000-06:00

These videos are from two reinforcement learning control problems I setup for my master's thesis work last year.

Pendulum Swing-Up

A physically-simulated pendulum is controlled by a Verve agent (http://verve-agents.sourceforge.net). Based on simple reinforcement signals (+1 when the pendulum is close to vertical, -1 otherwise), the agent learns to swing the pendulum upright and balance it after about 60 trials.

Cart-Pole/Inverted Pendulum

A physically-simulated cart is controlled by a Verve agent (http://verve-agents.sourceforge.net) in order to balance an attached pole. Based on simple reinforcement signals (-1 when the pole falls over or the cart goes off the edge of the platform, +1 otherwise), the agent learns to balance the pole for 30 minutes after about 600 trials.

Videos - Magnet Toy Simulation

2006-11-16T10:45:00.000-06:00

These are videos of a simulation I made earlier this year. I was trying to simulate a magnet toy using OPAL/ODE. The toy has two sets of magnets, each attached to a rotating axle. Here's a picture (thanks, JO):

Videos - Artificial Evolution of Humanoid Behaviors

2006-11-16T10:27:00.000-06:00

These videos are from a project I did in 2003. A physically simulated humanoid is controlled by an artificial neural network which senses joint angles and controls muscle forces. A genetic algorithm optimizes the neural network weights to improve performance on some motor control task.

Jumping Vertically

Standing Upright

Walking Forward

Neuron and Tree Growth Simulations

2006-11-08T10:44:00.000-06:00

We are All Allotted a Constant Amount of Mental Energy

2006-11-07T10:41:00.000-06:00

Given that we humans all have similar brain structures of comparable sizes, bandwidths, etc., we are all allotted a constant amount of mental energy which enables us to perform a certain amount of mental work per unit time. You could think of "mental work" as "planning" or "thinking." To be more precise, let's define it as reducing the uncertainty (or increasing the predictability) of a situation.

Let's look at some examples:

Visual scenes: The more time you spend looking at a landscape, an interior space, or a painting, the better you are able to predict it. At first you aren't able to predict the spatial relationships between elements, but after some time it becomes easy.
Logic and word puzzles: After expending a certain amount of mental energy, uncertainty is reduced, and the puzzles disappear.
People: At first, strangers can be unpredictable. The more you interact with a person, the better you understand him or her. It becomes easier it is to predict his or her behavior. (Most people's personalities are moving targets, though, so it isn't possible to reach a state of completely accurate prediction.)
TV shows: The more you watch a certain show, the better you are able to predict subtle interactions between characters and high-level plot elements.
Sports and music: Learning new motor behaviors (like new sports, new pieces of music, and new musical instruments) requires a lot of attention. It takes effort to coordinate muscle movements into desired patterns. Over time, though, repetitive training produces smooth, synchronized motions with little effort.
Cooking: The more brain-time you invest, the better you understand how ingredients interact, and the better you can predict what things will taste like.
Investments: At first you have no idea how stable various markets are. Over time, your uncertainty is reduced, and you can make well-informed decisions based on past experience.

In each situation it takes a certain amount of mental work to reduce uncertainty, just like it takes a certain amount of physical work to move heavy objects. You could say that complex situations are "heavier" than others.

Even though most of our brain structures function in parallel, the whole attention system is a serial mechanism. Think about it. You can only focus on one discrete thought at a time. Try looking at a complex scene or object. You are able to look at the whole thing at once, but you can't attend to more than one component at a time. Right now I'm looking at a house plant in my living room, and I can't simultaneously think "plant" and "leaf." I have to focus on either a small part or the whole thing. It's complicated because you can think of similar sets of objects at a time ("all the books on my bookshelf"), but you're still limited to a single discrete thought.

Imagine your attention system constantly switching among various thoughts. It spends some time working on a crossword puzzle, switches for a half second to think about what to have for lunch, switches back to the puzzle, switches to the sound coming from the radio for a bit, switches back to the puzzle... Every time attention shifts, it starts applying mental force to a new mental object, moving it a little bit across the spectrum from unpredictable to predictable.

The point here is that we all have a similar (within an order of magnitude) amount of mental energy available to us per unit time. Since birth we have all expended a similar amount of this energy on something. So everyone must have some kind of hidden talent related to those things that occupy most of his or her thoughts.

(The whole idea of "useful" mental work is another story. Utility can be defined in a variety of ways. A common one might be something along the lines of "the good of the many." If a person's goals are aligned with the utilitarian viewpoint, he or she would spend his or her mental energy on problems that benefit the most people. If the reward hypothesis is correct, we spend our mental energy on those things that we expect [based on previous experience] will bring us the most rewards. This gets into the whole area of motivation, which is beyond the scope of this article. To attain the highest level of utility, however it is defined, it is probably necessary to spend time thinking of ways to improve one's own thinking abilities, or metalearning.)

Now Listening to...

2006-11-07T10:34:00.000-06:00

...audio lectures from Jeremy Wolfe's course, Intro to Psychology, Fall 2004, on MIT OpenCourseWare. Even though it's an intro course, I think it'll be good. Jeremy sounds like a great teacher (you can just tell after listening to him for 30 seconds). And I think it's good to hear the fundamentals lots of times from a variety of teachers.

I didn't quite finish to Gerald Schneider's Animal Behavior course (I finished 22 out of 37 lectures). I heard all I wanted to hear and decided to move on.

Update on Verve Development

2006-11-07T10:17:00.000-06:00

For a while my posts have been focused on things other than the Verve project itself. One reason is that I enjoy posting about random interesting ideas that pop into my head. The other reason is that I've been thinking of starting a new software development effort. It would have the same general goals as Verve, but it would use much more advanced methods. For instance, I have been doing a lot of research into the general topic of context representation. I have prototyped a few subcomponents and have drawn lots of plans. Rather than ripping out the existing context representation in Verve (i.e. its dynamically-growing radial basis function system) and reworking all the components that connect to it, I'll probably just leave it how it is and continue building this new system.

Things are going very well overall. I'm having a blast. I think it's important to have a blast when you're doing research. It's good for morale. And if your morale is suffering, you're not going to do good research.

I'll post more details as things progress.

Intuitiveness

2006-09-21T16:39:00.000-05:00

What does it mean for something to be "intuitive?"

It must have something to do with our intuition. Ok... so what's "intuition?" I like to define it as previous knowledge (loosely defined), either instinctive or gained through learning. Thus, something that is intuitive is something that takes advantage of previous knowledge. A key point here is that intuitiveness is subjective.

If you have played poker games in the past, the rules of a new poker game will be intuitive if they rely on knowledge gained from other poker games. If you have used Microsoft products in the past, new Microsoft products will be intuitive as long as they are designed like the old ones. If you have driven a car in the past, driving a new car should be easy. (Driving may not be very intuitive at first since we don't otherwise press levers to change velocity and turn a wheel to change directions... except in video games.) In all of these cases standards are important since they ensure that previous knowledge is exploited.

This thought process started a year and a half ago in a class assignment for "Interaction Methods for Emerging Technologies." The assignment was to explain why direct manipulation devices are usually preferred by users. (Direct manipulation devices are those in which the user's actions directly affect the end object, as opposed to devices that add one or more levels of indirect manipulation. For example, a computer mouse has one level of indirect manipulation since it indirectly controls the pointer on the screen.) This was my answer:

Why are direct-manipulation interfaces preferred?

I will use the phrase "knowledge transfer" to refer to the amount of previous knowledge that can be applied to a new domain. Direct-manipulation exploits a lot of knowledge transfer because user's manipulate the device in a similar way to how they manipulate everyday objects. Direct-manipulation usually requires little learning, thus less effort and/or frustration when using a new device.

Additionally, I would say that intuitiveness in any domain is directly proportional to the amount of knowledge transfer being used, maybe going so far as to say intuitiveness is equivalent to the utilization of knowledge transfer. So things can be intuitive to some people and not others depending on their experience. Direct-manipulation is more intuitive to almost everyone because almost everyone has had a lot of experience manipulating everyday objects. A new Microsoft product, on the other hand, would be intuitive for people experienced with Microsoft products because of the knowledge transfer involved, but not for others who aren't used to them (hence the effectiveness of interface standardization).

Monday, February 28, 2005

ASME IDETC & CIE Conference 2006

2006-09-18T11:37:00.000-05:00

I presented a paper on Verve at the 2006 ASME (American Society of Mechanical Engineering) IDETC & CIE conference (International Design Engineering Technical Conferences and Computers and Information in Engineering... whew). The official reference is the following:

Streeter, T., Oliver, J., & Sannier, A. 2006. A General Purpose Open Source Reinforcement Learning Toolkit. In Proceedings of the ASME International Design Engineering Technical Conferences and Computers and Information in Engineering Conference.

The presentation went pretty well. I was put in a strange topic area, though (Knowledge Management in Design Automation). I think the audience liked the live demos, and I had some good questions from them afterwards. The paper and presentation slides are available in the publications section of my website.

I attended a talk called "The Spirituality of Engineering" by two professors from Delft University in the Netherlands. They showed a video of a grad student from Russia doing a 6 month research internship in Paris (developing a control algorithm for the inverted pendulum problem). Then the speakers and the audience talked about various types of symbolism present in the film.

I also went to two industry/government panel discussions: "Challenges Confronting Mechanical Systems with Emphasis on Intelligence," and "Industry & Government Perspective on Issues and Challenges for Robotics." James Albus gave a presentation at the first one called "Building Brains for Thinking Machines," which was a brief summary of his work on hierarchical control systems. I talked with Dr. Albus briefly before his talk about some of his books (Intelligent Systems and Engineering of Mind).

Now Listening to...

2006-09-02T09:40:00.000-05:00

...audio lectures from another Gerald Schneider course, "Animal Behavior," on MIT OpenCourseWare.

I'm really enjoying taking courses on my own schedule. I just fit an entire course (Neuroscience and Behavior) into two weeks. (Actually I only listened to 16 out of the 30 audio lectures available, but they covered the topics I cared about.) It's great because I usually get bored with normal courses by the end of the semester. I have a pretty good feel for when I'm in a learning mood, and it usually doesn't coincide with scheduled lecture times. Now I can just keep my iPod with me all the time and listen to a chunk of a lecture while I'm riding the bus, exercising, or waiting for software to compile. I don't think I could go back to the old way. I'm done with old school school.

Are Dreams Undirected Planning Sequences?

2006-08-24T13:54:00.000-05:00

I had a thought. Say we have mental models of the world available for planning, and we can direct our planning sequences (i.e. trains of thought) through imagined spaces in order to achieve some goal. That's in the awake state. During dreaming, there is reduced activity in the prefrontal cortex, an area that is usually associated with planning/judgment. Maybe when we dream, our minds move through the same imagined spaces, but they do so in an undirected manner because the high-level planning control center is turned off. It's like the car is still moving, but no one's in the driver's seat. Without the prefrontal cortex, we can't really judge the absurdity of different situations, which explains why dreams always seem normal until we wake up.

Currently Listening To...

2006-08-24T13:26:00.000-05:00

...audio lectures from Gerald Schneider's course, "Neuroscience and Behavior," on MIT OpenCourseWare.

Main Areas of Investigation

2006-08-24T13:14:00.000-05:00

The main areas of the Verve agent design that need work are:

Context representation - should be more computationally efficient, and it should include a short-term memory of previous observations
Hierarchical action construction - complex actions should be built up automatically from low-level primitives
Experimentation with curiosity - this will be much more interesting once the previous two areas have been developed

I'm back from New York

2006-08-22T14:57:00.000-05:00

I just got back from my internship in New York on Sunday night. It was a lot of fun. I had some great discussions with the other researchers in my group. My project was to help develop and test a computational model of the cerebellum. I learned a lot about the cerebellum (of course) and was introduced to several information theory-based approaches (like Linsker's Infomax framework and the subsequent ICA work of Bell & Sejnowski).

Now that I'm home, I'll be able to work on my own research again. I'd like to start looking at better context representations soon, possibly using ICA.

The Classical and Romatic Qualities of Jazz Improvisation

2006-08-06T17:49:00.000-05:00

I saw Arturo Sandoval play at the Blue Note on Friday. It was great, of course. I first heard him play in high school when I bought his album Hot House.

As I was listening, I started thinking about what goes on in your head when you improvise jazz. I think it helps to separate things into two categories: playing well technically (high notes, fast difficult patterns, etc.), and playing well emotionally (having a good gut feeling for what sounds good when). In other words, knowing how to play and knowing what to play. These two components trade control back and forth throughout a solo; one part chooses which pattern to play next, the other part executes it, the first part chooses another pattern, the other part executes it...

Some improvisers are good at one but not the other. For example, some are very proficient at playing difficult material, like high notes and fast, intricate syncopated sequences. But they don't have any clear direction to their solos (i.e. they're not good at choosing patterns). Others lack technical skill (i.e. they haven't mastered a lot of patterns), but they choose sounds in a way that produces an interesting overall message. They play with soul. I like to think of these two types of skill as Classical and Romantic Quality, as defined by Robert Pirsig in Zen and the Art of Motorcycle Maintenance. (I also think these two categories can be mapped roughly onto the brain's cognitive/analytical processes and its emotional/limbic processes, respectively.)

The best imrovisers are good at both kinds of Quality. Their brains have large libraries filled with high-quality patterns (Classical), and they have amazing selection mechanisms (Romantic). Their solos have relevant messages, and they're constructed out of masterful building blocks.

I haven't played jazz for a little while (about a year and a half), but I'd like to play again. I stopped playing because grad school got busy, mainly, but I also became frustrated with how I was playing. One thing was that I didn't like how I sounded in recordings. Something just wasn't right. Kind of like how most people don't like to hear their own voice. Another thing was that I wasn't really advancing as an improviser. I think it was because I was too focused on achieving Classical Quality. I would always practice with the goal of mastering some new pattern in all twelve keys, for example. I was never able to focus on learning to fashion the overall structure of a solo into anything meaningful. Then when it came time to play a solo with a group, I would go on autopilot, randomly jumping from one well-learned pattern to the next. My solos lacked direction.

I think what led to this problem was how, in most school bands I played in, the kids that could play the highest/fastest solos got the most respect (usually from their peers, not necessarily from the directors). So people that wanted to be noticed (myself included) would practice playing high notes and flashy passages. The Classical Quality of musical performance alone was usually equated with proficiency. Of course, it's hard to practice (and harder to teach) the Romantic Quality of jazz improvisation, especially in isolation. It's best to get real experience with a group that's not totally focused on the attention-getting parts of soloing.

Pirsig's division of idealogies into Classical and Romantic appears to be a good one. It appears to encompass a wide range to situations, including jazz improvisation. (I think that this division can be tied somewhat directly to the structure and function of our brains. I'm interested to find out if this is true.) Some improvisers choose to focus on developing one are more than the other (sometimes to the point of producing totally unbalanced solos), but the best soloists are good at both.

Curiosity Rewards Related to Flow

2006-08-01T00:15:00.000-05:00

First, here's a diagram I made for a presentation on Artificial Curiosity at the HCI Forum 2006. It shows the simple idea behind the powerful Schmidhuber type of curiosity mechanism:

I had read about Mihaly Csikszentmihalyi's idea of "flow" in the book Satisfaction: The Science of Finding True Fulfillment, by Gregory Berns (which totally sounds like a hokey self-help book, but it's not). According to wikipedia, "The flow state is an optimal state of intrinsic motivation, where the person is fully immersed in what he or she is doing." Yesterday I came across Jenova Chen's game flOw, which is supposed to be based on the same principle. He has this great diagram in his thesis that explains flow quite simply:

Notice any similarity between this and Schmidhuber's curiosity model? Seems like the same type of mechanism; the optimal situation is somewhere between overly challenging and too simple. Intrinsic rewards for situations with maximum learning progress. Or, in the case of flow, intrinsic rewards for appropriate challenges. This seems like a major isomorphism.

Simulacra and Simulation Related to Online Virtual Worlds

2006-07-31T22:29:00.000-05:00

From Simulacra and Simulation, by Jean Baudrillard, 1981, page 1:

"If once we were able to view the Borges fable in which the cartographers of the Empire draw up a map so detailed that it ends up covering the territory exactly (the decline of the Empire witnesses the fraying of this map, little by little, and its fall into ruins, though some shreds are still discernible in the deserts - the metaphysical beauty of this ruined abstraction testifying to a pride equal to the Empire and rotting like a carcass, returning to the substance of the soil, a bit as the double ends by being confused with the real through aging) - as the most beautiful allegory of simulation..."

This particular idea of simulation, a copy of some original thing which might acquire more attention than the original itself, makes me think of what Google Earth might turn into.

"...this fable has now come full circle for us, and possesses nothing but the discrete charm of second-order simulacra.

Today abstraction is no longer that of the map, the double, the mirror, or the concept. Simulation is no longer that of a territory, a referential being, or a substance. It is the generation by models of a real without origin or reality: a hyperreal. The territory no longer precedes the map, nor does it survive it. It is nevertheless the map that precedes the territory - precession of simulacra - that engenders the territory, and if one must return to the fable, today it is the territory whose shreds slowly rot across the extent of the map. It is the real, and not the map, whose vestiges persist here and there in the deserts that are no longer those of the Empire, but ours. The desert of the real itself."

The simulacrum concept (a copy with no original), however, appears to be more similar to our fantasy virtual worlds: Second Life, World of Warcraft, There, Project Entropia.

The major distinction between these two types of online worlds (that one is based on our physical world and the other is totally fictional) might become more pronounced in the future as these places gain in popularity. Each type has its benefits: one is instantly familiar, the other allows more creative freedom. Both seem to have their own place in the foreseeable future. If people someday spend so much time in virtual worlds that the real one is no longer familiar, the Earth-simulation type might fade away.

Ethical Issues in Advanced Artificial Intelligence

2006-07-13T09:04:00.000-05:00

Why should we study intelligence (either artificial or biological) and develop intelligent machines? What is the benefit of doing so? About a year ago I decided my answer to this question:

To the extent that scientific knowledge is intrinsically interesting to us, the knowledge of how our brains work is probably the most interesting topic to study. To the extent that technology is useful to us, intelligent machines are probably the most useful technology to develop.

I have been meaning to write up a more detailed justification of this answer, but now I don't have to, because I just read this great paper... "Ethical Issues in Advanced Artificial Intelligence," by Nick Bostrom. I think this paper provides a clear explanation for developing intelligent machines. It touches on all the important issues, in my opinion.

A few points really resonated with me. Here are some succinct excerpts:

"Superintelligence may be the last invention humans ever need to make."
"Artificial intellects need not have humanlike motives."
"If a superintelligence starts out with a friendly top goal, however, then it can be relied on to stay friendly, or at least not to deliberately rid itself of its friendliness."

The third point, I believe, adequately deals with the issue of intelligent machines going crazy and taking over the world. It's all about motivation. If a machine has no intrinsic motivation to harm anybody, it will not do so. There are some caveats to this, some of which were discussed in the paper. I don't think any of these are insurmountable. First, random exploration during development in an unpredictable world will inevitably cause damage to someone/something. I don't think this is a huge problem, as long as the machine is sufficiently contained during development. Second, a machine with a curiosity-driven motivation system will essentially be able to create arbitrary value systems over time. The solution to this is simply to scale the magnitude of any "curiosity rewards" to be smaller than a hard-wired reward for avoiding harm. Third, a machine that can change its own code might change its motivations into harmful ones. Again, hard-coding a pain signal for any code modifications would help combat the problem. Further, if any critical code or hardware is modified, the whole machine could shut itself down. Of course, malignant or careless programmers might build intelligent machines with harmful motivations, but this is a separate issue from statement #3 above.

July Update

2006-07-11T23:05:00.000-05:00

I've been pretty busy with my internship this summer, so I haven't done much work with Verve. It's probably best that I wait till I'm done at IBM, anyway, to avoid any conflicts of interest. The internship itself is going well. I'll post more details when it's over... maybe after we've submitted some things to be published.

Next week is the AAAI 2006 conference in Boston. I'll be there to present a poster in the student abstract program. My abstract is entitled, "Curiosity-Driven Exploration with Planning Trajectories." More details are here.

Some Biological Evidence of Curiosity Rewards

2006-06-21T09:01:00.000-05:00

I can't stop thinking about curiosity rewards and how interesting the whole concept is. It seems like such a fundamental component of mental development. I can't wait to implement the more powerful model in Verve and run some experiments.

I just came across this article (referring to an article in the latest issue of American Scientist, which I couldn't find) describing some recent biological evidence of a sort of curiosity reward system: http://www.physorg.com/news70030587.html

The original (not free) article is in American Scientist... here is the first paragraph and a good diagram: http://www.americanscientist.org/template/AssetDetail/assetid/50770

Evidently, there is a "25-year-old finding that mu-opioid receptors – binding sites for natural opiates – increase in density along the ventral visual pathway..." These receptors are said to be involved in pain/pleasure processing elsewhere. Based on this evidence, Irving Biederman ran experiments using fMRI on humans viewing various types of images. "Biederman also found that repeated viewing of an attractive image lessened both the rating of pleasure and the activity in the opioid-rich areas."

It seems that the evidence described here might correspond to the more powerful model of curiosity, which says that curiosity rewards are proportional to the reduction in novelty. So, once the stimulus is fully predicted (and no longer novel), the rewards will disappear.

Here is another good quote: "The brain's craving for a fix motivates humans to maximize the rate at which they absorb knowledge."

"Building Gods" Video, Robot Limits, and Modifying Our Reward Systems

2006-05-04T16:20:00.000-05:00

I just watched this video documentary called "Building Gods." It is a "rough cut to the feature film about AI, robots, the singularity, and the 21st century." I thought it was pretty well made and had a good selection of speakers. It's 1 hr 20 min long. Watch it if you have time:

http://video.google.com/videoplay?docid=1079797626827646234

Some parts talked about how we will need to figure out how to limit AI in some ways. We don't want our superintelligent "artilects" to turn against us, of course. I've thought about this problem often in terms of reinforcement learning. If we build intelligent agents with some sort of reinforcement learning/motivation/drives/goals (which seems to me like the best way to achieve general purpose intelligent agents), we can put limits on how rewarding certain situations are. We can hard-wire reward/pain signals corresponding to the equivalent of Asimov's 3 laws of robotics, for example. Since the motivation system would determine action selection, it could be designed so that bad behavior is painful to the agent. Even with a curiosity reward system (which presumably causes a lot of misbehavior in children), rewards from "interesting" situations could be scaled down if they are harmful to humans.

Rather than hard-wire all kinds of reward signals, there could be just a couple of them related to human approval. The reinforcing approval and disapproval received from a human teacher could be scaled very high compared to other rewards. It would be like training a pet. A well-trained dog is pretty reliable, after all. I think it could be even more effective for a robot. If your housecleaning robot decides to break a vase just to see what would happen, a verbal scolding (which becomes a large pain signal to the robot internally) would ensure that it never happened again. And all of this training would only be necessary once - the learned associations could be transferred to other robots.

A more interesting issue is whether intelligent agents should be allowed to change their own hardware and software. If so, things could get messy. In hope of achieving a higher long-term reward (which is the basis for reinforcement learning), they might modify their internal reward system and overwrite the hard-wired limits. They could remove the reward/pain system associated with Asimov's 3 laws. Everyone knows what happens next. The only good solution I see would be to make it painful for a robot to try to modify itself (or to even think about doing so).

Speaking of modifying reward systems, I think this is an interesting possibility for humans, too, which I've never heard discussed. Futurists always talk about the amazing possibilities down the road, like fully immersive VR, but they usually assume that our brains' reward systems will stay the same. Most of the things predicted in futuristic utopian societies (like vast scientific and technological advancements, upgraded bodies and minds, extensive space exploration, automated everything, etc.) are only rewarding if our brains say so.

What if we could change the hard-wired reward signals within ourselves? What if a person could be altered so that the mere sight of a stapler was the most pleasurable sensation possible? Sounds kind of boring... but so does taking drugs. Why would injecting heroine into your bloodstream be fun? Watching a person do so doesn't look fun. It's fun because it hijacks the brain's reward system, making the behavior much more desirable than other things. So, the problem with the stapler addict would be the same: normal daily activities would lose their appeal, and even the stapler rewards wouldn't be so great after a while. He/she would move on to two staplers, then three, then five, then ten... So goes the hedonic treadmill.

The problem is that the brain quickly adapts to whatever level of reward it receives. People that win the lottery aren't really much happier than the rest of us, once the euphoria wears off. So is there any point in modifying the brain's reward signals? I still think so. The solution isn't merely to change what's rewarding, but to modify the reward processing algorithm itself. It could be made so that it does not adapt to (i.e. get bored with) a given rewarding situation. Or it could just reset itself after a while. So every January 1st, your brain resets the reward adaptation system, and everything from the previous year that has become boring is suddenly exciting again.

Even more extreme, we could just set the internal reward signal (like the TD error-like signal encoded by midbrain dopamine neurons) to be maximal all the time. It would never adapt, like it does with drug addicts. A person in that state would be high constantly and never come down. He/she wouldn't even need fully immersive VR. What would be the purpose? At that point the hedonic treadmill would effectively be defeated.

Ok, admittedly, that would be a twisted existence... but from the point of view of the person with the altered brain, it would be great. Assuming the reward hypothesis is true for humans, I wouldn't be surprised if it actually happens someday. Disclaimer: I'm not recommending that anyone actually try this, either now or in the future. I just think it's a really interesting idea that should be discussed more among futurists. And I have never taken illegal drugs.

HCI Forum 2006 w/ Ray Kurzweil

2006-04-28T17:19:00.000-05:00

Here are a couple of pictures from the HCI Forum 2006. One is of Ray Kurzweil trying out my demo application of a curious robot exploring a physically simulated environment. (I'll post pictures of it on the Verve website soon.) The other is of me talking about current models of curiosity in intelligent agents.

Curiosity System Changes

2006-04-25T16:50:00.000-05:00

I've been meaning to make several changes to Verve's curiosity reward system for a while. Right now it still uses a simple method that only applies to very simple situations: it gives the agent a reward in situations that yield high prediction errors. The new system will only apply rewards in situations that contain learnable information (i.e. those that are neither too predictable nor too unpredictable). This works by making curiosity rewards proportional to the learning progress (i.e. reduction in prediction errors) in a given situation over time. This new method is inspired by the artificial curiosity research of Schmidhuber and Oudeyer.

So now I need localized representation of estimated learning progress. I currently have a localized representation of uncertainty/confidence. I think the changes will be fairly simple: I just need to add a new linear neural network (the "learning progress estimator") which gets input from the RBF state-action representation and outputs a scalar localized estimation of learning progress (i.e. reduction in uncertainty). This neural network will be trained with the actual reduction in uncertainty (measured using the change in uncertainty estimation, which is computed by measuring the uncertainty estimation before and after training it).

Finally, instead of being proportional to the prediction uncertainty estimation, curiosity rewards will be proportional to the estimated learning progress.

Internship This Summer at IBM Research

2006-04-25T16:43:00.000-05:00

This summer I'll be doing an internship at IBM's TJ Watson lab in Yorktown Heights, NY. I'll be working with Charles Peck and the Biometaphorical Computing group, which is currently heavily involved in the Blue Brain project (see here and here). At this point, I think the plan is for me to work on a computational model of the cerebellum.

I'm not sure yet how much I'll be able to work on Verve in my spare time this summer because I don't know if it's too closely related to my work at IBM. I'll post again later when I find out.

Self-Organizing RBF Methods

2006-03-31T16:38:00.000-06:00

Lately I've been thinking about various methods for self-organizing RBF centers. Instead of having RBF position fixed, they could move around over time using an unsupervised learning approach. This would focus resources on the most important parts of the input space.

Below I described a few different adaptation methods. "x" represents the distance between an RBF and the input point. I tested some of these ideas in a simple PyGame application and posted some screenshots below.

Method 1
Move the RBF closer to the input point in proportion to x. The farther away the RBF is from the input point, the faster it will move towards it. In other words, given input that stays in the same place over time, all the RBFs will reach it at the same time.

This method can be made more local by only considering RBFs within some radius from the input. The following image shows units being adapted towards the mouse pointer in my PyGame app. Adaptation is proportional to x.

You can see how all of the units beyond a certain radius do not move at all.

Method 2
If we adapt the RBF positions based on a Gaussian function...

...the RBFs will move towards the input point faster as they approach it. This is desirable because more distant points will not be affected as much. The following screenshot from my PyGame application demonstrates this using a Gaussian-based adaptation function. I moved the mouse pointer (which determines the input point) around in a smooth curve.

The problem with these approaches is that the RBFs tend to clump together near the inputs... which is fine if your goal is to reach a set of discrete clusters, but not if you're trying to approximate some function. In my case, I'm usually trying to represent a state space for a physically-simulated creature, so I don't want the RBFs to clump together so much. I do want them to move towards the input points (presumably increasing the representation's resolution where it matters), but not so much that they're totally covering the exact same area.

Method 3
I tried a hybrid approach which combines the simple linear function of Method 1 and the Gaussian function of Method 2. By simply multiplying the Gaussian and linear functions, I got the following:

This looks like it would help because the RBFs adapt slowly at large distances, quickly at medium distances, then slow down again as they approach the input. This is, in fact, what it does, but I still get the clumping effect I was trying to avoid. The following picture shows the PyGame app using this hybrid approach. It's hard to tell the difference between this and the plain Gaussian method just by looking at the picture; the main difference is in how quickly the RBFs approach the input.

So now I have a few methods to self-adapt RBF centers. (Of course, these have probably already been described elsewhere, but sometimes it's fun and enlightening to figure these things out yourself.)

The problem remains that the RBFs clump too much. What I need is a good way to keep them a minimum distance apart. A brute-force approach would be to compute the distances between each pair of RBFs, but that's O(n^2) runtime complexity. The classic Kohonen's self-organizing map approach would probably work. To implement that I would simply need to add connections between nearby RBFs, and I could use those local connections to force them apart if they get too close.

GDC 2006 Summary

2006-03-29T10:39:00.000-06:00

This is a summary of my GDC 2006 experience. Keep in mind that I attended only ~15 out the the several hundred lectures available, and most of the ones I attended were in the programming track.

Overall
GDC 2006 was a continuation of last year's topics. Compared to last year, there was nothing terribly revolutionary (which was to be expected... there's already enough for people to learn without having to worry about, say, yet another hardware platform). With all the new hardware coming out, most of the focus was on preparing developers for the transition to parallel processing. Overall, it was a great conference; I think the GDC is one of the most important conferences available for people interested in real time computer graphics, simulated physics, AI, software development techniques, 3D modeling, etc.

In the game programming world, there was more of a push towards parallel architectures and algorithms. This change started last year with the introduction of new hardware (the Cell chip for the PS3, Ageia's PhysX chip, and multiple core chips for PCs).

Sessions
I attended the following sessions. For some of these I was working as a conference associate; the rest I attended for my own interest. More info on these can be found on the GDC 2006 site.

A day long tutorial, "Embodied Agents in Computer Games," by John O'Brien and Bryan Stout.
A roundtable discussion, "Technical Issues in Tools Development," moderated by John Walker.
A keynote speech, "Building a Better Battlestar," by Ronald D. Moore.
"The Next Generation Animation Panel," by Okan Arikan, Leslie Ikemoto, Lucas Kovar, Julien Merceron, Ken Perlin, and Victor Zordan.
"High Performance Physics Solver Design for Next Generation Consoles," by Vangelis Kokkevis. This included a demo of 500,000 particles running in real time on the PS3.
"Sim, Render, Repeat - An Analysis of Game Loop Architectures," by Michael Balfour and Daniel Martin.
The Nintendo keynote speech, "Disrupting Development," by Satoru Iwata. They handed out several thousand free copies of Brain Age for the Nintendo DS.
"Serious Games Catch-Up," by Ben Sawyer.
"The Game Design Challenge: The Nobel Peace Prize," by Cliff Bleszinski, Harvey Smith, Keita Takahashi, and Eric Zimmerman.
"Spore: Preproduction Through Prototyping," by Eric Todd.
"Half Weasel, Half Otter, All Trouble: A Postmortem of Daxter for the Sony PSP," by Didier Malenfant.
"Physical Gameplay in Half-Life 2," by Jay Stelly.
"Behavioral Animation for Next-Generation Characters" (Havok sponsored session), by Jeff Yates.
"Crowd Simulation on PS3," by Craig Reynolds. Showed 10,000 fish interacting @60 fps on the PS3.

People
I made a few new connections this year. I talked to Steve Wozniak, Dan Goodman (who works with Kevin Meinert, a former VRAC researcher, at Lucasarts), Leslie Ikemoto, and a bunch of people from the conference associates group. I also talked with several people that I have met before, including John Walker (High Voltage Software), Mat Best (Natural Motion), and Ken Stanley.

Meeting with Leslie Ikemoto at GDC 2006

2006-03-29T10:23:00.000-06:00

At the GDC last week I met Leslie Ikemoto at a tutorial on embodied agents in video games. She brought up the Nero game during the tutorial, which uses evolved neural networks (specifically, the NEAT algorithm, invented by Ken Stanley) to control soldiers in a real-time strategy game. Since I had used NEAT before and am familiar with Ken Stanley and NEAT, I talked to her briefly during a break.

The next day we talked again about our own research. She showed me a project where she trained an animated character to run around on a platform, seeking goals and avoiding barriers, using reinforcement learning. The character's trajectory was determined by the animation sequence, so the RL part learned to choose the best animation to perform at any given state. Overall, it worked pretty well. She was a little unhappy with the results when the character seemed to wander around idly, even though there was a clear path to the goal. My best guess was that the state space needed higher resolution. I also suggested using a clustering algorithm to group the sensors into the most important parts of the state space.

It was very cool to see RL applied to character animation like this. I think it is a very powerful approach, especially in situations where the character must adapt to changing environments. Hopefully we'll see more of this in the future.

Leslie's colleague, Okan Arikan, whom I also met at the GDC, has done some pretty cool computer graphics research. Check out these explosions!

How Much of the Brain is Understood?

2006-03-27T00:02:00.000-06:00

A few days ago, right after talking to Steve Wozniak, my friend Ken Kopecky and I were talking about how much of the brain is understood. He asked me roughly how much of it I thought I understood (which is sort of an ill-posed question, but anyway...), and I said maybe 50%. He replied, "That's a very bold statement, Tyler Streeter." I said, "Ya, I know."

The next day I thought more about that conversation. I realized that I should have qualified my response a bit. I talked to Ken again, saying that I was mainly referring to the brain's functional/computational aspects. I said, "My 50% estimation from the other day was not meant to imply that I am especially intelligent, but that the functional, computational aspects of the brain are not as complex as most people think."

To elaborate a bit, some of the key elements (also described in my notes posted earlier) are probably:
* Data compression/feature extraction (e.g., principal components analysis, clustering)
* Reinforcement learning (e.g., temporal difference learning)
* Planning/imagining (e.g., using a learned predictive model of the world to enable reinforcement learning from simulated experiences)
* Curiosity rewards (e.g., intrinsic rewards from novel, learnable information)
* Temporal processing/short-term memory (e.g., tapped delay lines)

Meeting Steve Wozniak at GDC2006

2006-03-22T02:20:00.000-06:00

I met Steve Wozniak (cofounder of Apple) today at GDC2006. I showed him some videos of my research, which he enjoyed. He was very eager to meet all of the Conference Associates (the volunteer group of which I am a member).

We talked briefly about the brain and what we currently understand about it. We disagreed about how much is known about the brain. It was a good time.

My Notes on Theoretical and Biological Intelligence

2006-03-17T18:55:00.000-06:00

Over the past year I've been keeping a couple of text files that summarize what I know about biological intelligence (from a neuroscience perspective) and theoretical models of intelligence. I am constantly updating these files as I gain more knowledge. I thought it would be good to post them here, just to have a record of what I understood on March 17, 2006.

biological_intelligence_3-17-06.pdf
theoretical_intelligence_3-17-06.pdf

What Does the Cerebellum Do?

2006-03-13T13:46:00.000-06:00

The cerebellum automates motor tasks. It learns the temporal relationships between sensory and motor signals. After much practice, motor tasks get transferred to the cerebellum. In other words, well-learned tasks get chunked together as motor programs in the cerebellum. More specifically, these are probably closed-loop policies/options, as defined in the reinforcement learning literature. This whole process frees other areas (in the cerebral cortex) to focus its attention on new tasks, building upon the automatic skills stored in the cerebellum. It enables agents to learn hierarchies of motor skills.

Functions of Predictive Models

2006-03-10T10:28:00.000-06:00

What are predictive models good for? Here's what I think:

Planning - Without an accurate predictive model, it's impossible to generate simulated experiences. Planning requires a predictive model.
Curiosity - The only models of curiosity I've seen so far depend upon prediction. Curiosity is defined as novelty or, even better, the reduction in novelty over time. The only good way to measure novelty in a general way is by comparing the output of a predictive model with reality. This could include a reflexive, metapredictor component that can predict a level of uncertainty about its own predictions.
Attention - I think attention is drawn to unpredicted, novel situations (and novelty measurement depends upon predictive models... see Curiosity above). In other words, the limited attention channel is focused on situations that contain the highest probability of containing useful information. These can be externally driven (unpredicted external stimuli) or internally driven (through planning/simulated experiences, we might come to a novel situation which attracts our attention and may guide external movement toward that situation in the real world).

Note that, in any kind of general purpose intelligent agent, predictive models must be learned from experience.

What is Rewarding?

2006-02-27T11:46:00.000-06:00

So, assuming the brain is trying to maximize long-term reward intake... what is a "reward?" I think it can be arbitrarily defined, of course, but biological brains have a set of hard-wired primary reward/reinforcement signals. (I am using "reward" and "reinforcement" interchangeably here, with the assumption that both can represent positive and negative values.) The most obvious ones are: food, sex, and pain. Incoming sensory information that is classified into these categories generates reward signals.

A more interesting hypothetical reward signal comes from novelty. For now, let's call it "novelty rewards." We are drawn to novel situations because of novelty rewards. There is evidence that the same dopamine neurons that fire during unexpected "normal" rewards (e.g., food) also fire in all kinds of novel situations. The book Satisfaction: The Science of Finding True Fulfillment, by Gregory Berns, talks extensively about novelty being a major source of rewards in humans.

But I think there's more to it than simple novelty. If we were rewarded simply by experiencing novel situations, we would be drawn to all kinds of random signals (e.g., static radio signals) like moths to a street lamp. As Juergen Schmidhuber proposed in the early 1990s, a better model of novelty-based rewards is that it is rewarding to experience the reduction in uncertainty over time (see Juergen's papers on curiosity here: http://www.idsia.ch/~juergen/interest.html). Basically, it is rewarding to learn. I'll call this "learning rewards." This whole idea is based on our predictions about the world. The term "novelty," then, means the same thing as "uncertainty" and "unpredictability." Fortunately for computational modelers, uncertainty can easily be quantified using predictive models.

If an agent remains in a situation where predictable information can be gained over time, we can say the following:

Uncertainty/novelty/unpredictability is reduced
Learning occurs (specifically, the predictive model gets better)
"Learning rewards" should be given to the agent

These learning rewards are extremely powerful. They enable very open-ended learning where agents are drawn to situations that contain learnable, predictable information. It drives them to experiment at the edge of their current knowledge of the world. Since it drives agents to improve their predictive models, it is very beneficial for planning.

Subjectively, it feels rewarding to gain information. When you are working on a crossword puzzle, and suddenly the "aha!" moment hits, it's the resulting transition (from uncertainty to certainty) that feels good.

The Reward Hypothesis

2006-02-27T11:33:00.000-06:00

In general, I think the core idea that makes biological brains understandable is rewards. The following "Reward Hypothesis," as described on the RLAI research group's site (http://rlai.cs.ualberta.ca/RLAI/rewardhypothesis.html), summarizes my point:

"That all of what we mean by goals and purposes can be well thought of as maximization of the expected value of the cumulative sum of a received scalar signal (reward)."

I think this is a clear description what the brain is "trying to do." All other major brain functions make the task of reward maximization easier.

Hierarchical representations

2006-01-31T16:57:00.000-06:00

I've been reading from Principles of Neural Science (2000) by Kandel, Schwartz, and Jessell. (It's the required text for my Neural Basis of Human Movement class.) It's a big, pretty standard textbook. So far I've gained a lot of info on how the motor control centers are organized, something which my previous class (Neurobiology) didn't touch.

The main underlying idea I keep coming back to is hierarchy (both in terms of sensation and action). It makes so much sense. Low-level sensory inputs are combined into higher-level representations. In the cerebral cortex this occurs within modalities at first. Higher up in the hierarchy it occurs across modalities. So the highest levels of the sensory hierarchy represent very abstract states, combining all sensory input. Most of this seems to occur in the occipital, parietal, and temporal lobes.

Similarly, the spinal cord, brainstem, and parts of the frontal cortex appear to form a motor hierarchy. Currently, my best guess is that this hierarchy is arranged as follows, from lowest to highest level: spinal cord, brainstem, primary motor cortex (MC1), premotor cortex, supplementary motor area, presupplementary motor area, prefrontal cortex. If the prefrontal cortex is at the highest level, it might form an interface between the sensory and motor hierarchies... if they are totally separate structures (see next paragraph).

One of the big confounding issues for me is whether there are separate sensory and motor hierarchies. It might be possible that there is a single sensory-motor hierarchy. This would mimic the idea of hierarchical policies in reinforcement learning; each module in the hierarchy would be a mapping from state to action, so it would require both sensory and motor pathways.

So it might be a while before I (or anyone) understands the overall organization of the sensory and motor systems. The method of thinking that has been most help to me in this kind of situation is this: pick a hypothesis and assume it's true until proven wrong. The brain's overall organization is just so poorly understood that it's easy to get overwhelmed. I enjoy at least having a hypothetical model as a framework.

I plan to start working on an implementable hierarchical model soon. It might use radial basis functions like the current Verve agents do, but maybe not. It would be nice to have a totally self-developing hierarchy that could split nodes and add more resolution in the high-information parts of the state-action space. This is getting a little hard to picture, though, so I might make some drawings...

Verve 0.1.0 Release

2006-01-25T13:48:00.000-06:00

I put a 0.1.0 source release on SourceForge last night. This is the "thesis" version that was used to generate the results in my MS thesis. Enjoy!

Pendulum Swing-Up and Cart-Pole Videos

2006-01-24T16:45:00.000-06:00

I posted two videos: one of the pendulum swing-up task, and one of the cart-pole task. Check them out here: http://verve-agents.sourceforge.net/gallery

Version 0.1.0 should be ready within the next few days.

First software release soon

2006-01-06T15:06:00.000-06:00

I'm planning on releasing an initial version of the Verve library soon. It will probably be the version I used for my master's thesis experiments. Even though I have lots of ideas for further development, I think I'll just release the "thesis version," mainly to have a snapshot of the software at the time I wrote the thesis. Not sure if I'll even reimplement the XML loading and saving code (which worked a looong time ago but got totally outdated after a ton of architecture changes... so I just commented it out). So look for something like version 0.1.0 soon.

Also, I've recently registered the project on SourceForge as 'verve-agents.' So now the main project website is http://verve-agents.sourceforge.net. (For the record, the old site was http://www.vrac.iastate.edu/~streeter/verve/main.html.) The new site is powered by the PHP-based Dokuwiki software, making it much easier for me to manage than a bunch of HTML files.

Finished MS Thesis

2005-12-12T19:02:00.000-06:00

I've spent most of the past two months implementing planning and curiosity, running experiments, and writing my thesis. The title of it is "Design and Implementation of General Purpose Reinforcement Learning Agents." I put a link to the pdf version on my website here: http://www.vrac.iastate.edu/~streeter. It sums up most of my ideas over the past year or so, including some new ones since my last post.

By the way, I have a working version of the Verve library ready. I just need to clean up a few things before releasing it. As soon as someone bugs me about it, I'll hurry up and get it ready.

One more value function image...

2005-10-18T00:10:00.000-05:00

Here's another version of the estimated value function for the agent in the 2D world described in the previous post. This was generated as a scalable vector graphics from from gnuplot, and I converted it to a PNG:

Simple value function images

2005-10-17T19:58:00.000-05:00

Here are a couple of sample (estimated) value functions, both using radial basis functions for state representation.

The first one is for an agent in a 1D world with -1 reward everywhere except on the left and right side:

This second one is for an agent in a 2D world with -1 reward everywhere except at the 4 corners:

State representation update

2005-10-17T19:29:00.000-05:00

I've been working on writing my master's thesis lately. I'm trying to finish it by Nov. 1st. I'll post a link to it when I'm done. I also plan on overhauling the Verve website before too long... at least by the time I release an initial version.

Here's a quick summary of my recent thoughts on state representation:

The agent should have a linear state representation in order to assure temporal difference learning convergence. We need to transform the direct sensory inputs into this linear form.
The state representation should contain features that combine certain inputs where necessary. For a general purpose agent we need to use features that encompass all possible combinations of sensory inputs. Over time the features that never get used could be purged.
The boxes approach, tile coding, radial basis functions, etc. are all valid methods we could use to represent these features in a linear form. For now I'm choosing an RBF state representation that combines all inputs. Later I would like to experiment with hierarchies of RBF arrays to mimic the hierarchical sensory processing in the cortex.
We could reduce the dimensionality of sensory inputs by using principal components analysis (PCA) or independent components analysis (ICA). I considered trying this, but I won't have time before finishing my thesis. I might use the "candid covariance-free incremental principal component analysis" (CCIPCA) method since it's incremental and seems fast.

The last thing I want to implement for my thesis is planning. The following is the general design described using the boxes approach. (Things get a little more complicated now that we're using RBFs, described later.) I would have a state-action array of boxes with a single active box representing a unique state-action combination. This array would connect to another array representing the predicted next state and a single predicted reward element. This state/reward predictor would be trained with a simple delta rule using the actual state and reward. The predicted state array would use a winner-take-all rule to pick the predicted next state. Since the winner-take-all system uses roulette selection with selection probabilities for each state, we can interpret these probabilities as the agent's prediction certainty. These certainty/uncertainty values can be used to generate curiosity rewards (proportional to uncertainty); agents are attracted to uncertain situations until they learn to predict them, at which point they get bored. Using the state/reward predictor, the agent can shut off its actual sensory inputs and run "simulated experiences" using this predictive model. It uses this system to learn its value function and policy without having to interact with the environment constantly.

The main changes when replacing the boxes with RBFs are the following: Instead of using a state-action array of boxes, we need an "observation"-action array of RBFs. Here we are taking the actual sensory input (i.e. the observation) combined with a particular action and transforming them into an RBF representation. This RBF array projects to a predicted observation and reward array of neurons. The system is still trained using a delta rule. The observation/reward predictor no longer uses a winner-take-all rule: instead of choosing a single next state, we have an array of real-valued outputs representing the predicted next observation (and reward).

More to come when I get further...

I Need a Better State Representation

2005-09-20T19:41:00.000-05:00

I'm trying to come up with a better way to represent the current state. Right now I use the "boxes" approach, as described in the last post. Another idea is "tile coding" (aka CMAC) described in Sutton & Barto's RL book. I think the boxes method is like having a single tiling, but in general you could have any number of tilings, each offset a little from the others. That means that with 5 tilings over some input space, you would have 5 active tiles, one from each tiling. Tile coding would give better generalization than using the simple boxes approach. Also, there are ways to use hashing to reduce the memory needed; memory would only be allocated when new states are encountered.

It would be nice to have an array of states where only the "important" states are represented. This could even be dynamic where newly encountered states are compared to the existing list of states. If a new state is different enough, it would be added to the list.

There are a lot of things I could try, but I want to finish adding new features and testing before October, then write my thesis in November. So if I'm going to improve the state representation, I don't want to have to try anything too experimental.

Solved Pendulum Task (and others)

2005-09-13T16:56:00.000-05:00

I finally solved the pendulum swing-up task the other day. Here's a picture of it balancing itself:

The main change that helped solve this task was the following relatively major change: I no longer use radial basis functions. Instead, I discretize all incoming continuous inputs into separate "boxes" (to use the terminology from the literature) and generate a list of all possible combinations of the input signals. So in the case of the pendulum, say we discretize the two inputs (pendulum angle and angular velocity) into 12 boxes each. That means the intermediate state representation is an array of 144 possible combinations, each one representing a unique state. It's kind of a brute-force method, but it's very reliable and easy to understand. I may come back to radial basis functions and hebbian learning mechanisms later to form a more compact state representation.

Here are some pictures of the pendulum's (simple) neural network before and after learning the task. Excitatory connections are green, inhibitory are red. The connection diameter represents its weight's magnitude.

So here's a list of the tasks solved so far (with the number of inputs and outputs specified as (inputs/outputs)):
- N-armed bandit (0/10)
- hot plate (1/3)
- signaled hot plate (2/3)
- 2D signaled hot plate (3/5)
- pendulum swing up (2/3)

Next up: the inverted pendulum (aka cart-pole)...

One more thing: I used SWIG to generate Python bindings. Verve seems to work pretty well as a Python module. I don't know if I'll use it much right away, but it's good to have around.

Extensive Testing

2005-08-06T19:39:00.000-05:00

So what's new over the past 2 months? Mainly, I have been creating lots of different tests (unit tests and "learning tests"). I was on the brink of finishing the pendulum swing-up task... for about two weeks. It gets frustrating after seeing the pendulum almost hold itself up for the 1000th time, so I took a step back and decided to go about things more scientifically. I developed a framework for what I'm calling "learning tests" - simple learning tasks that can be thrown together quickly and added to an ever-growing suite. Every time I make a significant change in how the agent's work, I can run the suite of learning tests and make sure the agents perform each one above some threshold. I also plot the results of each one using gnuplot (http://www.gnuplot.info). Here are a few example plots (green is overall performance, red is temporal difference error):

Also, I wrote a bunch of unit tests to make sure each functional component is working correctly even after I make big changes. (I decided to write my own C++ unit testing framework. Check here if you're interested: http://quicktest.sf.net)

The purpose of adding all these tests is so I can scale up the learning task complexity a little at a time and find out exactly where problems occur. This seems much more reasonable than throwing a bunch of complicated systems together (learning agent, physics simulation, etc.) and hope it can learn efficiently.

Another big change has been in the area of input representation. Now the agents' inputs are much more customizeable. You can choose between 'continuous' and 'discrete' input channels. Continuous inputs are real values within [-1, 1]. They have a 'resolution' option which determines how many radial basis functions are used when encoding the input signal as a population code. Discrete inputs have a finite number of possible options. You could have a discrete input channel with 13 possible options representing ace, 2, 3, ..., 9, 10, jack, queen, king. Or you could have one with 2 possible options: alarm on, alarm off.

I'm continually excited about working on this project. It helps my morale to have the unit tests and learning tests. I feel like I can keep making incremental progress this way.

Oh, one more thing... I just bought a new Dell Dimension 9100: dual core 2.8 GHz (to inspire me to make Verve multithreaded :) ), 1 Gb ram, nVidia GeForce 6800, and a 24" LCD.

Motor Output Representation

2005-06-17T23:54:00.000-05:00

Progress has been pretty steady, but slower than I'd like. At least I'm getting close to finishing the pendulum swing up task. Then I can move on to the cart-pole/inverted pendulum task.

My current problem (and probably the last main problem before the pendulum task is finished) is how motor output signals are represented. Here are two possibilities:

1. Use one output neuron for each motor output signal. The neuron's firing rate encodes the motor signal to be used (e.g. a torque value). This allows the use of continuous signals for motor control, a desirable feature. The problem is that any reinforcement (via the temporal difference error) increases or decreases the firing rate of all outputs in the same direction (i.e. all firing rates will either increase or decrease), but we actually might want some to increase and some to decrease. It might be possible to use some kind of differential Hebbian update in conjunction with the temporal difference error (i.e. weight changes are proportional to TD error * pre-synaptic firing rate * change in post-synaptic firing rate), though I haven't read about anyone else doing this.

2. Use a "winner-take-all" scheme to select from among many action choices. Say we have three actions for the pendulum task: apply a constant clockwise torque, apply a constant counter-clockwise torque, or do nothing (letting the pendulum swing freely). Using three output neurons, we choose the one with the highest firing rate as the "winner." The winning neuron's associated action is applied. Another alternative is to have the firing rates represent probabilities of being chosen as the winner. The problem here is that there is a finite number of possible actions. This method currently gives me better results on the pendulum swing up task (it learns to swing the pendulum up and hold it for a second or two), but it can't keep it up indefinitely.

It might be possible (and probably is biologically plausible) to combine the two approaches: fine motor control is learned by one mechanism and encapsulated in a motor program, and another mechanism learns to switch from among a finite set of motor programs. It would be nice to have an agent automatically construct such motor programs, possibly even constructing hierarchies of them. Richard Sutton has done some work recently with what he calls "options" which are basically control policies that have special starting and termination conditions. I think these might be a pretty good theoretical foundation for building hierarchies of motor programs.

Radial Basis Functions, Neural Net Visualization

2005-05-27T14:15:00.000-05:00

Two new things...

1. I've been experimenting with a layer of radial basis functions (RBFs) for the input layer to my neural nets. Before I would just use a single real value for each input. For example, the pendulum angle was a single real value which used a single input neuron. Now I separate each input into an array of RBFs. It seems that a lot of people use RBFs when using neural nets for motor control. They increase the "locality" of learning: only the connection weights associated with a particular part of the state space are affected, so it helps the neural net retain old knowledge better. Also, it's neat to think about RBFs in terms of biology (think of the arrays of sensory nerves on the skin, the retina, the vestibular system, etc.)

2. I have always had a hard time visualizing what's going on with the neural networks while they learn. The combination of learning rates, eligibility traces for connections, neuronal firing rates, etc. makes it hard to understand what's going on. I had already been plotting various parameters on graphs after the simulations end, but I really wanted to watch how the parameters change in real time. So I wrote some code to see the neural nets floating in 3D space beside the agent's physical body. It shows me the neuron firing rates, connection weight sign/magnitudes, and eligibility traces, making it much easier to see what's going on.

Fixed Problems with Multilayer Neural Network

2005-05-20T09:16:00.000-05:00

I discovered yesterday that it really helps to connect the input neurons directly to the output neurons in the multilayer neural net. Now the value function neural net learns really well. The temporal difference error almost always goes to +/- 0.001 eventually.

Now I'm having trouble with the policy/actor neural net. It doesn't seem to improve its performance very much. It'll learn to swing the pendulum a little higher over time, but it never gets high enough to swing straight up. It definitely has enough torque, so that's not the problem. I wonder if it needs more random exploration. I'm currently using a low-pass filtered noise channel that changes slowly over time to encourage long random actions. I'll keep trying stuff...

Problems Learning the Value Function with a Multilayer Neural Network

2005-05-19T12:40:00.000-05:00

I've noticed that my agents can learn the value function really well using a linear function approximator - a neural network with a single output layer using linear activation functions. However, when I add a hidden layer of neurons, the agent cannot learn the value function very closely (i.e. the temporal difference error fluctuates between -0.1 and +0.1; the max possible error is +/-1.0). I usually use sigmoid activation functions for the hidden neurons, so I tried linear functions for them as well, but it didn't help. So I'm trying to figure out why it can't converge to something closer to the real value function using a hidden and output layer of neurons. I know that there are not any good convergence guarantees for nonlinear function approximators using temporal difference, but I at least thought using linear activation functions in all neurons, even in a multilayer neural network, still represented a linear function approximator. So maybe something else is wrong.

On the other hand, maybe I won't really need a nonlinear function approximator. It seems like a lot of researchers do pretty well with linear only, but then they only attempt fairly simple control problems.

I've learned a good way to represent the state for the pendulum swing up task. I was inputting the sine and cosine of the pendulum's angle (plus the angular velocity), similar to what Remi Coulom did in his thesis, but I had trouble learning the value function with this method, even with a single layer neural network. Instead I tried representing the angle as two inputs: one "turns on" when the pendulum is between 0 and 180 degrees (the input value ranging from 0 to 1) while the other is "off" (i.e. value of 0). When the pendulum is between 180 and 360 degrees, the first input is off and the other is on. This seemed to work really well - the temporal difference error usually falls to around +/-0.001 within a few minutes of real-time training.

More Time for Research

2005-05-12T09:50:00.000-05:00

Summer's here, so I finally have time for research again. I'm going to (try to) graduate with a master's degree this summer, so I'll be working on this project a lot over the next few months.

I didn't find any definitive answer concerning time representation in Daw's dissertation, but it was still a great (long) read. I'm still using it as a reference. I implemented some of his ideas about average reward rates (as opposed to discounted rewards, the standard method in temporal difference learning) and opponent dopamine/serotonin channels. The dopamine channel represents phasic (short-term) rewards and tonic (long-term) punishment, and the serotonin channel represents phasic punishment and tonic rewards. Eventually I'd like to do some experiments to see if this model more closely mimics animal behavior.

I've pretty much decided what I'm going to cover in my thesis. The main two topics are 1) temporal difference learning for motor control in continuous time and space, and 2) artificial neural networks for function approximation. My focus is on biologically realistic algorithms, so I'll spend some time talking about how my implementation relates to the brain. I'd like to include at least three experiments with solid results. I'm thinking maybe the pendulum swing up task (a pendulum hanging in midair has to swing itself upright and stay there using a limited amount of torque), the cart-pole task (a cart resting on a plane with an attached pole must force the cart back and forth to keep the pole balanced), and maybe a legged creature that learns to walk.

Another possible addition is the use of a learned model of the environment's dynamics, also using an artificial neural network. We'll see if I have time for that. I'd really like to try it, though, because others (e.g. Doya in his 2000 paper on continuous reinforcement learning) have gotten better results in motor control tasks using a learned dynamics model.

So far I've been working on the pendulum task. I have my value function (critic) working pretty well, but I can't get the policy (actor) to learn very well. I'm thinking my problem is either with my exploration method or how I'm representing the state as inputs to the neural nets.

Time Representation

2005-02-23T09:51:00.000-06:00

Last month I mentioned that I was running a classical conditioning experiment on my new agents. Given some stimulus at time t and a reward at time t+ISI (where ISI is a constant "inter-stimulus interval"), the agent should learn to predict when the time and magnitude of the reward after experiencing the stimulus. So, in other words, after the agent has been trained to predict the reward, when it sees the stimulus (which was previously neutral but now predicts reward), it should now exactly how long to wait before getting the reward and how big the reward will be.

My current problem is that the agent doesn't have a good way to represent the passage of time, a crucial element in classical conditioning. The agent can predict rewards immediately following the stimulus, but if there is a significant gap (ISI) between the stimulus and reward, the agent quickly forgets about the stimulus. I think I'm about to find some answer's in Nathaniel Daw's PhD thesis. Daw finished his thesis at Carnegie Mellon in 2003. The title of it is "Reinforcement Learning Models of the Dopamine System and their Behavioral Implications." It contains a lot of good material, including an extensive literature review and some new ideas about long-term reward predictions. Anyway, I'm just getting into chapter 4 which deals with time representation. I'm hoping to find some ideas there.

Research update

2005-01-19T11:04:00.000-06:00

Things are changing.

I have spent the past two months reading literature on two topics:

1) Reinforcement learning (for machines)
2) Reward signals in biological learning systems

A few months ago I started exploring things other than evolutionary methods. I couldn't help thinking that one of the best ways to improve machine learning methods is by studying and mimicking biological brains. At the same time I dove deeper into the (machine) reinforcement learning literature, trying to find out which methods are the best for motor control.

I decided to read the book Reinforcement Learning by Sutton & Barto over Christmas break, something I probably should have read a long time ago. Before reading it, my plan was to try out an actor-critic architecture, along with some kind of "sensory predictor" (a module that could learn to predict future sensory inputs based on some given state and action). The sensory predictor would allow an agent to simulate its environment and make decisions based off those simulations. I was proud of this idea at the time since I had thought of it one day in the middle of class, but later found out it already existed. Also, I had heard something about temporal difference learning methods (from the neuroscientific literature - dopamine neuron behavior is very similar to the temporal difference error signal), but I didn't know much about them. So I read Reinforcement Learning straight through. It turns out that temporal difference learning is a very effective way to predict future rewards (in the critic) AND to modify the actor's policy to reinforce effective actions (using "eligibility traces"). This works even when the reinforcement received from the environment is sparse. Temporal difference methods learn to associate neutral stimuli with rewards, thus creating chains of reward-predicting stimuli. Very cool stuff. And, the more I read in the neuroscientific literature about reward signals in the brain, the more confident I become that biological brains use temporal difference learning.

Additionally, the Reinforcement Learning book made it clear to me why neural networks are important. In the real world there are so many possible states that an agent cannot simply store an internal table of each state or state-action pair, along with reward estimates for each. A neural network condenses the state space by using a small set of parameters to approximate a more complex function.

At this point I have made a fairly permanent switch from evolutionary methods to reinforcement learning methods. I have written a good chunk of code so far to begin testing new ideas, including the basic neural network setup, temporal difference learning, and back-propagation. The back-prop will probably be used by the "sensory predictor" (i.e. internal/world model) to learn an internal representation of the external environment. Back-prop seems to be good for this because there will be predicted sensory inputs and actual sensory inputs, naturally leading to error signals at each output neuron.

I have run a few simple tests to make sure each component is functioning properly. The thing I'm testing now is a simple classical conditioning response. I'm trying to get my new agents to be able to predict rewards given some stimulus 200 ms before reward reception.

In the future I would like to setup a SETI-like system for training simulated creatures and/or robots. I think it would be a good way to get people involved in AI research, not to mention the extra CPU resources.

Right now I'm preparing a Verve presentation for the ISU Robotics Club tomorrow which will basically cover everything in this post, plus a little more background information. I'm hoping to use Verve to train real robots in the future (as opposed to simulated creatures). Maybe some folks from the club will be interested in working on something like that.

Tyler

November Update

2004-11-07T17:54:00.000-06:00

Just a note to say that I'm still doing a lot of background research. I'm currently writing a review paper for a psych class I'm in. It will cover reinforcement learning in natural and artificial neural networks and why biologically-realistic algorithms are important. A lot of the papers I've been reading recently are from Nature Neuroscience and Nature Reviews Neuroscience.

Something my Verve code has been lacking is reward sensing/predicting by the neural network. After reading a few neuroscience papers dealing with reward signals in human brains, I think my artificial neural network should be able to: 1) sense "rewards" (kind of a vague term, but this will probably be programmed explicitly, as in neuralNet->addReward(0.5)), and 2) predict rewards (i.e. some special neurons should output a signal when rewards are expected to be given).

Research Update

2004-09-20T21:34:00.000-05:00

Lately I've spent my time reading about neuroscience and biologically-realistic learning algorithms (and doing classwork, of course).

I skimmed through "Biophysics of Computation" by Chrisfof Koch. It describes the low-level electrical and chemical properties of neurons and synapses. Pretty good stuff. I especially like how he shows the similarities between certain neural structures and well-known electrical circuits. I'm also reading a bunch of articles out of "The Handbook of Brain Theory and Neural Networks" by Michael Arbib. (I have the 1st edition from the school library, but I'm trying to get the second edition since it's a lot newer and supposedly updated a lot.) It has a lot of good short articles on neural reinforcement learning and motor control.

I'm also reading Russell Smith's (the guy who wrote Open Dynamics Engine) PhD thesis, "Intelligent Motion Control with an Artificial Cerebellum." This contains a great overview of the human motor control system (especially the cerebellum) and other motion control research. He extends a system called the CMAC controller. I can't explain it yet since I just started reading it, but I think it'll be pretty good.

One more thing I'm doing that will probably pertain to Verve... I'm working with some other students on an abstract simulated physics interface (OPAL: Open Physics Abstraction Layer). This will be a high-level interface to physics engines. The purposes of this are: 1) to have an abstract interface that can be extended to work with any physics engine, and 2) to have a simple API that does tons of cool things automatically with relatively few function calls. Open Dynamics Engine, for instance, gives developers total control over a ton of parameters, but it takes a while to learn to use it well. Hopefully OPAL will alleviate this problem. I hope to use OPAL to make a lot of good Verve demos.

Tyler

Self-Referential Reinforcement Learning

2004-08-28T09:52:00.000-05:00

Lately I've been researching new reinforcement learning methods. Genetic algorithms have worked well so far, but I thought it might be good to see what else is out there.

I came across the website of Juergen Schmidhuber, a researcher at the IDSIA lab in Switzerland (www.idsia.ch). A lot of his work deals with "self-referential" learning systems. Instead of having a single hard-coded learning algorithm for some agent, you start with some initial learning "germ" that is able to modify any part of the agent's policy, including the learning system itself. This allows an agent to learn better strategies, to learn better learning strategies, to learn how to learn better learning strategies... An important feature of such a system is that there must be a closed loop somewhere (something like Hofstadter's "strange loops" he describes in Goedel, Escher, Bach). You can't simply have a meta-learning algorithm that only modifies the level below it; it must be totally self-referential to be able to change all parts of its learning strategy.

Obviously there must be some hard-coded aspects of the system. For example, if reinforcement is provided from the agent's environment, the agent shouldn't learn to misinterpret what's good and what's bad reinforcement; the agent should continually try to improve itself to meet a fixed goal.

My main concern is the problem of getting stuck in local optima. GAs can search through different chunks of the solution space in parallel, but this new method might not allow that. How do humans search through a solution space? We don't have multiple bodies that can try a ton of possible solutions in parallel, though something like this probably occurs in our minds. We create lots of hypotheses and test them against our mental model of the world, then test the best hypothesis against the real world. Predicting outcomes and measuring the actual outcomes against our predictions probably comes into play somewhere.

I've implemented two such self-referential learning systems so far, both modifying a character's neural net. One is sort of a dynamic programming approach, the other is totally neural net-based. The first didn't work so well, probably because it had to learn a sequential program to adjust a parallel architecture (the character's neural net). The second is a regular neural net with special output nodes that can address, read, and modify any parameter in the net. I'm still experimenting with this. One problem I'm having is that the network usually reaches a stable attractor and just stops changing: no character movement and no changes due to learning. I might add some probabilistic features to keep this from happening. For example, maybe there should always be a non-zero probability that the learning system can modify things at any time.

Connectionism...

2004-08-09T12:47:00.000-05:00

I've been reading some articles on Wikipedia about language and philosophies of the mind. Here are some links:

http://en.wikipedia.org/wiki/Sapir-Whorf_Hypothesis
http://en.wikipedia.org/wiki/Loglan
http://en.wikipedia.org/wiki/Connectionism

I haven't thought about it much before, but I think I subscribe to the connectionist philosophy. I may be a little biased, though, having studied artificial neural networks a lot recently.

The following quote from the connectionism article describes one of the main differences between connectionism and computationalism:

“Connectionists engage in "low level" modelling, trying to ensure that their models resemble the anatomy of the human brain, whereas computationalists construct "high level" models that do not resemble neurological structure at all...”

I hope to develop a connectionist system with Verve using only biologically-plausible components; however, this might not be the most practical approach. At first I might have to use some "high level models" that the neural architecture can learn to use, making the system part connectionist and part computationalist. The end goal would be to use only a neural architecture to control all behaviors at various levels of complexity.