Evolvable Rules
I stumbled on Evolvable Rules and REAT (Rete Evolution of Augmenting Topologies) yesterday whilst searching for interesting stuff to read. I'm not yet sure about what I think of the project but Greg sure got my attention.
The idea behind evolvable rules seem to be using Artificial Neural Network (ANN) techniques to generate a Rete network and some additional stuff like conflict resolution and the code needed for executing the RHS of a rule.
There's not that much info yet but Greg shares a few references that explain the technology he intends to use. Apart from Charles Forgy's Rete papers (the thesis and the article) and the Wikipedia description of the Rete algorithm (which we have another Charles to thank for) he also refers to Evolving Neural Networks through Augmenting Topologies by Kenneth O. Stanley and Risto Miikkulainen.
I haven't read the last paper that thoroughly (skimmed it once) and I'm only just learning about ANN technology but it seems to me that this requires a lot of work. And, if I understand correctly, it might not be very good at producing a Rete network at all and since there are "simple" rules that can be used to construct a Rete network based on, for example, an Abstract Syntax Tree I don't really see the point. Apart from being really cool of course ;-)
Anyway, I'm real interested to see how all this works out. I've had similar lines of thought myself after having read An Optimization Algorithm for Production Systems by Toru Ishida last summer. It would be really neat to find a way to automatically optimize (restructure) a Rete network based on the contents of the working memory without having to pass through all Facts and re-evaulate the goal of the optimization continuously.
The problem is that I have no idea of how, or even if, it can be accomplished. But I bet that if someone does it, it's probably going to have something to do with using ANN GA techniques. I'm not holding my breath though.
Labels:
AI,
Neural Networks,
Programming,
Rete Algorithm,
Rule Engine
13 kommentarer:
If you look at figure 5 page 113 of the ENNAT paper, it shows how it modifies the network.
Could this be done with RETE? My bias opinion for what it's worth is yes. I've thought about dynamic optimization of RETE over the last 8 years and it should be feasible. Having said that, much of the machine learning research using expert systems have relied on metarules techniques.
Rather than insert nodes into the network of an existing rule, most create new rules and remove or deactivate useless rules.
A couple of years back I had the idea of dynamically re-ordering the the alpha nodes to improve performance but it turns out the gain isn't worth it.
You and I have discussed the idea of re-ordering the joins in the past. The trick with dynamic optimization using node re-ordering is the cost. For small rulesets, it's trivial, but for large rulesets the cost could be high.
I have some old ideas on this. If I have time i'll try to blog about it.
Hi Peter,
Are you talking about generating a Rete network or using this technique (or something similar) to optimize one?
A couple of years back I had the idea of dynamically re-ordering the the alpha nodes to improve performance but it turns out the gain isn't worth it.
Yes, I guess you'd really have to have a Rete implementation that is constructed around being easy to modify on the fly otherwise the cost/benefit ratio will be a problem. Maybe it will always be an issue. It would be real interesting to see the things you tried though.
I have some old ideas on this. If I have time i'll try to blog about it.
Please do ;-)
I'm not intending to optimize a rete with evolution. Just the opposite, in fact. I fully expect REAT to produce gross monstrosities. :) What I'm searching for is automatic creativity: discovery of problem solutions without human intervention. It'll be another flavor of Genetic Programming once I'm done. (If that ever happens. It seems that whenever I start getting into it again I get distracted.)
Ah, and to clarify...
REAT will evolve RETEs, not via a "neural network technique" per se, but using a technique that has on;y been used on neural networks. (so far...) I figure the NEAT techniques can be used to create the structure of the RETE, but other approaches will be necessary to generate LHS conditions and RHS actions. (Probably some very slow and conservative evolution for LHS code, and something more exploratory for the RHS code.)
Also, I'm not intending on evolving conflict resolution rules at all. The way the inference engine executes will serve as the bed upon which evolution operates. Monkeying around with that would introduce even more wild behavior into a process that will probably be wild enough as it is. I've considered it, though. It'd be like exploring alternate universes where the laws of physics are subtly altered to see if the Anthropic Principle is true. I have yet to create one universe, though, so one thing at a time. :)
Hi Greg,
I'm not intending to optimize a rete with evolution.
Well, the optimizing bit is one of these things that take up a lot of my thoughts so I guess I projected my problem on your project. "If you have a hammer" and all that ;-)
What I'm searching for is automatic creativity: discovery of problem solutions without human intervention.
Ok, I *really* need to read that paper and, honestly, I don't think you need any other excuse than it being cool. Really.
Hopefully in another day I'll have my summary of RETE optimization techniques written and posted on my blog.
Mind giving me permission to read your blog, woolfel? I'd be interested in reading that.
It's possible that evolutionary techniques could be used to optimize a RETE. Evolutionary computation is best suited to situations where you can have a large population of test subjects to work with, and can slightly vary the approaches to solving the problem with each population member. So, if the problem to solve is "how to optimize this RETE" there are two possibilities, mattering on the nature of what the RETE is processing.
1) Run many independent parallel copies of the RETE, with each copy being a population member. (Presumably the subproblems are homogeneous, or this wouldn't work well.)
2) Consider a sequence of time during one RETE's processing to be a "population member" and try a different optimization configuration in each timeslice. Again, this would only be useful if the same kind of computation was done in each timeslice. One example of this would be a long running process that runs daily. Each day could be a population member, with the evolution phase (evaluation/recombination/mutation) happening every 30 days.
What you'd need for each of these approaches would be a description of how to optimize a RETE that fit well into one of the popular evolutionary algorithms. (i.e. a genome representation of RETE optimization)
Hey johan, the new entry is up.
http://woolfel.blogspot.com/2008/02/dynamic-rete-optimization.html
hi greg, send me an email woolfel AT gmail DOT com and i'll send you an invite.
Hi again Greg,
REAT will evolve RETEs, not via a "neural network technique" per se, but using a technique that has on;y been used on neural networks.
Are you using "Rete" as a synonym for "behaviour"? I really hope so, because if you do, things make a lot more sense. At least to me ;-)
It's possible that evolutionary techniques could be used to optimize a RETE.
I most certainly hope so. But the problem is that a Rete network can only be optimized in relation to the contents of the working memory. And since that (usually) constantly changes, an optimization might be completely useless after just one round of (run).
Also, the cost of actually running through all rules in order to figure out in what way the network can be optimized is probably too much.
I'm kind of hoping for some sort of analysis of the WM contents (probably implemented somewhere within the assert and retract methods) that allows you to figure out how to restructure the network without running all facts through it. Some form of statistical analysis perhaps?
Of course, once you do disconnect and reconnect some nodes in the network you *have* to propagate partial matches downward anyway and that's why I'm wondering whether it will ever be worth it.
Even if we can keep the cost of figuring out the optimal structure close to zero. The cost of re-structuring a (non-empty) Rete network is probably *not* going to be negligable. And that's (in my scenario) *before* we've even asserted the facts that the optimization is for!
Anyway, that's mostly random thoughts from me. I'm going to have to finish my rule compiler before ever doing any experimantation of this kind anyway and, just like you, I'm easily distracted ;-)
I've tried to describe some of the techniques in the blog, hope that helps.
Hi again Peter,
yes I saw your post. Didn't have time to comment until just now though. I've tried to expand on my comment here. Still quite fuzzy though but I hope I get my point across anyway.
the comments make sense. dynamic optimization definitely isn't cheap for non-trivial machine learning. It's too bad not many Phd programs study RETE anymore. I feel there's still so much to discover in RETE, but not many people care enough to explore.
Skicka en kommentar