Postpruning - First Whack

Zoo dataset A-B, before and after post-pruning.

It's funny I'm working on pruning for decision trees while earlier I was out in the yard pruning real trees.

It would be nice to eliminate the construction of these redundant nodes in the first place, but that seems to mean comparing the counts of the dataset and sub-datasets to see if the test is redundant which in Linq could be expensive.

It's a good thing I implemented edges because in previous versions of this function I was trying to remove and add nodes which threw an exception because you can't modify collections while your iterating over them.  I got around this by filling a list of replacement structures which was iterated over after the main routine was finished.  What was really a deal breaker is that this changed the order of the branches.  I finally realized I don't need to modify any collections I can just modify the nodes and edges.

Yay edges!

        private DtBranch Postprune(DtBranch branch)
        {
            DtBranch bottom = branch;
            //
            if (branch.HasAllLeafChildren)
                return branch;
            else if (branch.HasSingleChild)
            {
                DtBranch child = branch.Children.Single() as DtBranch;
                bottom = Postprune(child);
                bottom.Edge = branch.Edge;
                bottom.Edge.To = bottom;
            }
            else
                foreach (DtNode child in branch.Children)
                    if(child.Kind == DtElementKind.Branch)
                        Postprune(child as DtBranch);
            //
            return bottom;
        }

Decision Tree Workshop up on Google Code

Decision Tree Workshop is now available at http://code.google.com/p/decision-tree-workshop/.

It's a demo translated from python to C# based upon the article Building Decision Trees in Python
 by Christopher Roach.  I highly recommend reading it if you are unfamiliar with decision trees.

I decided to use Linq for the ID3 code because it's basically a bunch of database operations, and it makes for more understandable code in my opinion.  Besides it's just a demo, I'm not worried about speed at this point.

If the code seems strange it's because I'd like to experiment building the tree in parallel in the future.  So that is why I'm implementing worker classes instead of just using recursion.  Ideally these workers would be able to farm out some work to the GPU.  Is there Linq to GPU?  Hmmm, it appears so.  I think I will look at this Brahma thing.

I've driven myself nuts trying to validate it.  When you  translate a program you don't even really understand, things tend to get lost in translation and then you have to go back and compare the two sets of code over and over until things work.  However, it's that same process that helps to actually understand the algorithms underlying the code.  Well, I'm happy to say I'm satisfied enough with it now or I wouldn't even be writing this post.

Figure 1.  The Purchase dataset, target attribute = purchase?

Figure 1 is an example of a good tree, ideally you want the tree to be pyramid shaped which means that at run-time it requires the least amount of tests to get from the root to a result.

Figure 2.  The Iris dataset, target = class.

Figure 2 is an example of a bad tree, because there are too many child nodes under most of the nodes.  This is because the Iris dataset's attributes are all numeric except for the class attribute.  The solution is to create split points based upon the distribution of the attribute.  This is what C4.5 does.

Figure 3 looks especially depressing because at run-time it will perform a bunch of unnecessary tests.  What's happening is that the records in these branches have the same values for the attribute node that is being constructed, and then finally when it runs out of attributes to split on it reaches the target attribute and branches to multiple results.  The solution here is to use post-pruning like C4.5 does and remove the redundant nodes.

Well that about sums it up.  Next phase will be to clean up ID3 some more and then implement C4.5.

Figure 3.  The Zoo dataset, target = animal.

Behavior Language WIP

namespace SequenceTestNamespace

using System
using System.Collections.Generic
using System.Text
using System.IO

using BwBot.Runtime
using BwBot.Runtime.Tasks

class SequenceTest()
    def Main(sequence-test)
        {Console.WriteLine("a");}
        sequence
            {Console.WriteLine("1");}
            {Console.WriteLine("2");}
            {Console.WriteLine("3");}
        {Console.WriteLine("b");}
        sequence
            {Console.WriteLine("1");}
            {Console.WriteLine("2");}
            {Console.WriteLine("3");}
        {Console.WriteLine("c");}
        sequence
            {Console.WriteLine("1");}
            {Console.WriteLine("2");}
            {Console.WriteLine("3");}
            
sequence-test

Redo

I finally decided to go forward with a C# redo since the C++ version is too long and hard of a row to plow.

I've also cooked up a new syntax that is basically a prefix version of Python's syntax.

class Test():
    def Foo1($x is foo): #forward chaining method
        rule:
            $x has $y
            $y is bar
            -->
            $y is foo

I've already written a simple tokenizer based on this article about regular expression parsing in C#. Another article that was helpful was Python: Myths about Indentation. That only took one day. The rest of the week was spent agonizing whether to have the parser just read the token list or convert to s-expressions and then parse.

I finally went back to an earlier idea of writing a class called TokenTree that extends List(object) where each element is either a token or a subtree. This should make things easier on the parsing end for various reasons. The s-expression idea was kind of neat but it seems redundant since I need AST classes anyways.

Later on I'll have to dump the RegEx stuff and write a more sophisticated tokenizer but at least this was a quick way to get started. For now I need to start writing the recursive descent parsing functions and the AST classes.

Agent Language Preview

This is a preview of the Agent Language I'm working on. More details will go in a Wiki or something.

Methods are triggered by the addition and deletion of facts within the state. Methods without triggers are evaluated upon state creation. Rules within the methods are evaluated sequentially. States are evaluated until no new information can be generated at which time any facts that were proposed will cause the creation of successor states into which those proposals will be added along with any other facts in the current state.

This is a work in progress therefore any and all comments or criticisms are extremely welcome!

$ = Logic variable
. = Property of the rule, method, state, or agent

;
; Missionaries and Cannibals 
;

(domain Mac ()
 (method main ()
  ;state success
  (rule
   (topic $g (type goal))
   ($g object $bank)
   ($g missionaries $m1)
   ($bank missionaries $m2)
   ($m1 = $m2)
   ($g cannibals $c1)
   ($bank cannibals $c2)
   ($c1 = $c2)
   ($g boat $b1)
   ($bank boat $b2)
   ($b1 = $b2)
   ==>
   halt
  ) 
  ;state failure
  (rule
   (Bank-1 missionaries $m1)
   ($m1 > 0)
   (Bank-1 cannibals $c1)
   ($m1 < $c1)
   -->
   (assert(.state fail "Too many cannibals on Bank1!!!"))
   ==>
   fail
  )
  ;state failure
  (rule
   (Bank-2 missionaries $m2)
   ($m2 > 0)
   (Bank-2 cannibals $c2)
   ($m2 < $c2)
   -->
   (assert(.state fail "Too many cannibals on Bank2!!!"))
   ==>
   fail
  )
  ;state failure
  (rule
   (.parent (.goal missionaries $m1) (.goal cannibals $c1) )
   (.goal missionaries $m2)
   ($m1 = $m2)
   (.goal cannibals $c2)
   ($c1 = $c2)
   -->
   (assert(.state fail "State undoes parent goal!!!"))
   ==>
   fail
  )
  (rule
   (topic $g (type goal))
   (not($g is achieved))  
   -->
   (temporary(.agent achieve $g))
  )
 ) 
 (method MoveMissionaryPropose (.agent achieve $g)
  (rule
   (topic $bank1 (type bank))
   ($bank1 boat $boat)
   ($bank1 missionaries $m)
   ($m > 0) 
   (topic $bank2 (type bank))
   ($bank2 <> $bank1)   
   -->
   (propose((.agent move-boat $boat)
    (missionaries 1)
    (cannibals 0)
    (source $bank1)
    (destination $bank2) ) )
  )
 )
 (method MoveCannibalPropose (.agent achieve $g)
  (rule
   (topic $bank1 (type bank))
   ($bank1 boat $boat)
   ($bank1 cannibals $c)
   ($c > 0) 
   (topic $bank2 (type bank))
   ($bank2 <> $bank1)   
   -->
   (propose ((.agent move-boat $boat)
    (missionaries 0)
    (cannibals 1)
    (source $bank1)
    (destination $bank2) )
   )
  )
 )
 (method MoveMissionariesPropose (.agent achieve $g)
  (rule
   (topic $bank1 (type bank))
   ($bank1 boat $boat)
   ($bank1 missionaries $m)
   ($m > 1) 
   (topic $bank2 (type bank))
   ($bank2 <> $bank1)   
   -->
   (propose ((.agent move-boat $boat)
    (missionaries 2)
    (cannibals 0)
    (source $bank1)
    (destination $bank2) )
   )
  )
 )
 (method MoveCannibalsPropose (.agent achieve $g)
  (rule
   (topic $bank1 (type bank))
   ($bank1 boat $boat)
   ($bank1 cannibals $c)
   ($c > 1) 
   (topic $bank2 (type bank))
   ($bank2 <> $bank1)   
   -->
   (propose ((.agent move-boat $boat)
    (missionaries 0)
    (cannibals 2)
    (source $bank1)
    (destination $bank2) )
   )
  )
 )
 (method MoveMissionaryCannibalPropose (.agent achieve $g)
  (rule
   (topic $bank1 (type bank))
   ($bank1 boat $boat)
   ($bank1 missionaries $m)
   ($m > 0)
   ($bank1 cannibals $c)
   ($c > 0) 
   (topic $bank2 (type bank))
   ($bank2 <> $bank1)   
   -->
   (propose ((.agent move-boat $boat)
    (missionaries 1)
    (cannibals 1)
    (source $bank1)
    (destination $bank2) )
   )
  )
 )
 (method MoveBoatApply (.agent move-boat $boat)
  (rule
   (.thought source $bank1)
   (.thought destination $bank2)
   (.thought missionaries $m)
   (.thought cannibals $c)
   ($bank1 missionaries $m1)
   ($bank2 missionaries $m2)
   ($bank1 cannibals $c1)
   ($bank2 cannibals $c2)
   -->
   (retract 
                ($bank1 boat $boat)
    ($bank1 missionaries $m1)
    ($bank2 missionaries $m2)
    ($bank1 cannibals $c1)
    ($bank2 cannibals $c2)            
            )
   (assert 
    ($bank2 boat $boat)   
    ($bank1 missionaries (- $m1 $m))
    ($bank2 missionaries (+ $m2 $m))
    ($bank1 cannibals (- $c1 $c))
    ($bank2 cannibals (+ $c2 $c))   
   )
  )
 )
)
;
;
;
(problem Mac
 (topic Boat-1
  (type boat)
 )
 (topic Bank-1
  (type bank)
  (missionaries 3)
  (cannibals 3)
  (boat Boat-1)
 )
 (topic Bank-2
  (type bank)
  (missionaries 0)
  (cannibals 0)
 )
 (topic Goal-1
  (type goal)
  (object Bank-2)
  (missionaries 3)
  (cannibals 3)
  (boat Boat-1)
 )
)

Syntax Highlighter Test

I found a way to insert code snippets into the blog. As long as you can find somewhere to host the files SyntaxHighlighter seems to be the best solution. Here is a good tutorial to get rolling.

class MyClass {
    bool blah(){
        return 2 > 1 ; 
    }
}

Looks are Everything

Well, I managed to rearrange and rebuild everything with Visual C++ 2008 express.

Now it's time to get rid of the uglies!

I went over to a place called Psionic where most Ogre folks get their free models.

Thankfully I found a patch for the Ogre Blender Exporter that does the axis swapping again.

Only problem is that the Jeep model is still backwards. Either I research how to rotate vertices in Blender or I can just rotate the mesh in Ogre.

It's never easy.

Rock and a Hard Place

Now I'm in a real dilemma.

I'm having a problem with Boost 1.35, CeGui, and vc7.

There isn't a problem with vc9, so it must be a bug in vc7 that they haven't done a workaround for yet.

I could go back to Boost 1.34 but then I'd have to include ASIO separately and I'm not sure if I can use vc9 with it.


Hmmm...

Shaking the Tree

Sometimes when your stuck in a rut it's time to shake things up.

My way of shaking things up this time is to upgrade to Boost 1.35 and creating a build system for Visual C++ 2008.

The reason for upgrading Boost is that ASIO is now an official part of the library and I need to replace the socket classes I wrote to make Botworx more portable.

Unfortunately, they totally rewrote the thread library and the locks and mutexes I was using caused things to hang. All that synchronization stuff probably needs a rewrite anyhow.

I think I'm going to dump ODE and Bullet and just go with PhysX. I can't count the hours I've spent making a hybrid system work. It works, but ... time to move on.

Back to the Grind

Well, PyWeek ended about a month ago but I kept fiddling with RoboCute until I could decide how to proceed with trying to beat this framework into shape. Now it's back to C++. Yay.

Project on Hiatus until 4/7/2008

Yep, PyWeek is more important.

Methodology to the Madness

It just occurred to me that the way I'm getting this ready for publication is worthy of comment.

I am restructuring this thing top down. Starting with the top level concepts and classes to do some much needed refactoring, plus rearranging file directories and files in the process. I am also going to throw out a bunch of failed and half complete experiments along the way. They can be reincorporated later if desired.

After this restructuring/reevaluation phase I need to re-implement certain things from the bottom up. The main thing is object lifetime. That's always a ball of wax.

The Applet Concept

This concept is not to be confused with Java Applets. The Applet concept goes further back if you look at the Wikipedia entry here.

I had been tempted just to change the name to Application or App for short. I'm going to stay with it in the eventuality that we may wish to run several of these side by side or embedded in a web page. That makes the name stick.

The Applet's main role is to serve as the root of the simulation heirarchy.

Applets are derived according to which GUI system the user plans on using. CEGUI and wxWidgets for now. More to follow.

The User Concept

Each Scenario creates and owns a User object.

The User object is created via a factory method of the Applet. (Need to define Applet soon!)

Each User class is specific to a particular GUI system. CEGUI, wxWidgets, etc.

Each User has a UserMode tree.

A UserMode is a class that can be either an action, a UserMode group, or a mode of some kind. For instance a dialog.

User interaction consists of drilling down and escaping back out of this tree.

It makes it extremely easy to implement user interfaces and is more intuitive than your average GUI with it's multiple menus, toolbars, etc., although these elements could be integrated into the User framework as well.

Fire Bad!!!

This thing is a Frankenstein creation for sure. It's cobbled from open source components and it has graphics only a mother could love.

I'm not sure when, or even if it's going to appear. I'm not even sure about the license type yet.

So ... I'm just going to keep throwing details on this Blog for no apparent reason. :)

Requests For Comments

I'm going to start tossing some RFCs up here to help resolve issues that I can't make a clear cut decision on, even after endless hours of searching the internet.

Hopefully SOMEONE will participate.

Thanks!

GUI Madness

I'm probably the only person whose nuts enough to implement GUI interfaces for multiple GUI systems on a per scenario basis.

It all got started because the 'in-game' GUI looked like crap inside wxWidgets.

You could have GUIGUI wrappers but that would be insane, trying to wrap each element for each GUI system.

The solution is to have a factory function that returns a User object specific to the GUI that creates the interface and manages event routing.

This might be interesting in the fact that you could have the factory function create different interfaces depending on certain modalities: play, edit, etc.

Hopefully I get it refactored and working properly by days end.

Botworx and wxPython

After posting pics of the wxWidget integration it occurred to me that having a wxPython widget would be the bomb.

This would allow rapid prototyping of editing and debugging aids.

Of course that also means providing scripting support for a lot of the guts.

That's probably aways down the road. I need to clean this thing up and bang it into shape first.

Fixing wxWidgets Integration

Oh boy. This is setting off a whole chain reaction of refactoring I put off for a long time. :(

The upside is that it should make adding more GUIs in the future easier.

It's also getting rid of a lot of redundancy that existed between the CEGUI & wxWidgets wrapper classes.

.5 Roadmap

This roadmap is contingent on interest in this project and the willingness of others to participate!

Distribution will be in limited form and start at version .1

Distribution of .1 will be somewhere between April and May of '08.

Distribution of .1 will only be on an invitation basis. Mainly to AI teachers, students and game programmers.

After the period of about 1 year or I think it deserves a .5 moniker then it will go into general distribution. Whichever comes first.

The reasoning behind this is that I don't want to be a one man support team for a free product!