Dec/091
Concurrent Hierarchical Reinforcement Learning & Lisp
Allan recently set me onto quite a good paper:
B. Marthi, S. Russell, D. Latham, and C. Guestrin, “Concurrent hierarchical reinforcement learning,” in Proceedings of the National Conference on Artificial Intelligence, vol. 20, 2005, p. 1652.
Marthi et al. describe an extension to Lisp that forms part of their concurrent hierarchical reinforcement learner. Their algorithm is trained to control simulated peasants in the Stratagus real-time strategy game domain. Their approach is similar to Parr and Russell's Hierarchical Abstract Machines (HAMs) in that a program defines a semi-Markov decision process which is then solved with a reinforcement learner and prior knowledge is included in the design of the program.
The paper made me interested in learning Lisp, although I have some hesitation because Lisp is (according to Wikipedia) the second oldest programming language still in use.
Peter
Oct/093
pi: a pattern language
π is a new pattern-based language being developed by the Software Technology group at Technische Universität Darmstadt. In π, there's only one language construct: the pattern. Essentially, a pattern is an EBNF expression that is associated with a meaning. So when writing a π program, you're basically defining both syntax and semantics as you go. This makes it a powerful tool for defining domain-specific languages, and for experimenting with new programming language ideas.
Oct/090
Paper: Recent Advances in Hierarchical Reinforcement Learning (2003)
I came across this article today in my search for work on hierarchical reinforcement learning:
Recent Advances in Hierarchical Reinforcement Learning by Barto and Mahadevan, 2003. While much of the paper is on Dietterich's MAXQ and Parr and Russell's HAM algorithms, there is a section on hierarchical memory that looks interesting and seems closer to my area of interest than the MAXQ algorithm.
I'm just beginning my exploration of the hierarchical memory concept, thanks to Barto and Mahadevan's paper. Please post if you have good references that are even more recent than 2003.
Peter
Oct/090
Magnetic charge has been measured
Researchers from the London Centre for Nanotechnology have measured magnetic charge.
Our measurement of magnetic charge and magnetic current establishes an instance of a perfect symmetry between electricity and magnetism.
Wow! That's nothing short of amazing!
Peter
Oct/090
Kids doing research: Blackawton bees
Beau Lotto and 25 under 8-years-old collaborators produce new results relating to the behaviour of bees. Beau Lotto and his eponymous research lab do research on perception, mixing seeing and hearing, and adaptive things (life and mechanical approximations of life).
It's cool beyond words, and it's got me thinking about education, how it's done and how it could be improved. And it would be totally awesome if a bunch of kids got published before reaching the double digits!
Peter
Oct/090
Book: “Reinforcement Learning: An Introduction” by Sutton and Barto
Sutton and Barto introduce reinforcement learning in their clear, comprehensible book. Like many textbooks that are meant to be able to be used in pieces, it suffers from a bit of redundancy. However, it does well on a number of fronts.
Oct/092
SPARK Ada
SPARK is a carefully defined subset of Ada that comes with a set of tools designed to provide extremely thorough static analysis of SPARK programs. SPARK programs are annotated with additional "contract" information which are also statically checked. SPARK's analyses can detect programming errors such as improper input validation, buffer overflow errors, improper initialization, and information leaks. As a result, it's quite popular in safety-critical and high-integrity systems circles, and makes a good language for developing dependable embedded systems. Adacore has a good tutorial on SPARK that demonstrates some of the ways that SPARK can be used.
Here's a simple example of a SPARK contract for a procedure that increments some variables (derived from here):
procedure Inc (X : in out Integer); ––# global in out CallCount; ––# pre X < Integer’Last and ––# CallCount < Integer’Last; ––# post X = X~ + 1 and ––# CallCount = CallCount~ + 1;
The contract specifies that
- The parameter X and the global variable CallCount must be read by at least one path, and must be updated by at least one path through the procedure.
- Both X and CallCount must be less than the variable Integer'Last prior to execution of the procedure.
- Once the procedure has executed both X and CallCount must have been incremented
SPARK's static analysis tools raise an error if X or CallCount are not read or updated in any path, or if any other global variable is read or updated. Errors will also be raised if there is a possible call to the procedure that violates the precondition, or if the implementation of the procedure won't satisfy the postcondition. Note that all of these things are check statically, not as part of a dynamic check at runtime.
SPARK has been around for quite a while, and has been used in a wide range of industrial projects. So why am I bringing it up now? Because I've just found out that the SPARK language and toolset is now available under the GPL! Which makes it even easier to experiment with SPARK than it was previously.
Oct/090
Vorpal Slot Definitions
Vorpal now has special syntax to streamline slot definition. I hope writing clear Vorpal code will be easier now. In the past, Vorpal required a highly manual form of slot definition:
x = new() x.a = new() x.a.b = 2 x.a[0] = 4
No longer! Now the same result can be achieved with a nicer syntax (and slightly more efficient execution):
x = new(){
'a' = new(){
'b' = 2,
4,
},
}
Oct/093
Comparing Echo State Networks with Multiple Context
Echo State Networks (ESN) take advantage of the computing power now available, while Multiple Context (MC), the basic learning system for the PURR-PUSS robot brain, was developed when computing power was minimal. This suggests to me that the design of MC should be able to benefit from that of ESN. I will be talking only about ESN used for prediction
Both MC and ESN are driven by a complex short-term memory. In each case, there is a strong in-built structure. In an ESN it is a recurrent neural network with pre-set connection strengths. In MC it is a collection of contexts of events, where the event types of the events in a context are prescribed by fixed templates.
In the ESN, prediction is improved by a set of variable connections that pick out (in a mysterious way!) the appropriate parts of the recurrent network to make the prediction.
In the MC, prediction is improved by accumulating experienced contexts that have predicted successfully in the past. It allows one-off learning as well as gradual learning. After a time, some of these are discarded because of poor performance and shortage of space.
The MC could be made more like the ESN if it began with a very large number of templates and had a variable weight attached to each template that measured the usefulness of predictions coming from the contexts of that template. The weights would be taken into account when contexts from different templates were predicting different events. They could lead to the discarding of templates and even the introduction of new ones.
The ramifications of this idea are considerable!
John H Andreae
Oct/090
Langford on Research
Here's a nice posting from John Lagford on pursuing grand ML challenges.
Necessary and Sufficient Research
Researchers are typically confronted with big problems that they have no idea how to solve. In trying to come up with a solution, a natural approach is to decompose the big problem into a set of subproblems whose solution yields a solution to the larger problem. This approach can go wrong in several ways.
- Decomposition failure. The solution to the decomposition does not in fact yield a solution to the overall problem.
- Artificial hardness. The subproblems created are sufficient if solved to solve the overall problem, but they are harder than necessary.
Then later he lists some things he thinks are necessary to achieve, "a master machine learning algorithm that can solve any reasonable learning problem where “reasonable” includes at least the set that humans can solve."
- Large data
- Online learning
- Interactive learning
- Compositional design
- Large contexts
- Nonlinearity
Read the post to see what these qualities mean in detail. I agree with all of them, but I haven't done a lot to pursue #1 yet.