Human Guided Forests - HGF

Yesterday I posted some slides about an idea I had recently which I call Human Guided Forests or HGF for short.  This an attempt to marry crowdsourcing with machine learning to produce better class predictors for datasets with very large features spaces.  Specifically, the idea is to replace the 'random' in the Random Forest algorithm with 'human'.

Random Forests basically work like this:
Given a labeled dataset with M input variables and N samples,

• Choose m as the number of input variables allowed per tree in the forest
• For X iterations:

1. Choose a subset of n samples from the training set
2. Select m random input variables
3. Build a decision tree using the randomly selected variables, all n samples (the 'bootstrap' or 'in bag' sample), and standard induction techniques (e.g. C4.5)
4. Measure the error rate for that tree on the samples not used to train it (the 'out of bag' or 'oob' samples)
5. Save the tree

After the forest of decision trees has been constructed, classify new samples by running them through all the trees and choose the class that is predicted most frequently.  (This is a very successful kind of 'ensemble classifier' that is similar to one that I, because of my ignorance, reinvented as one of my first projects in bioinformatics.)

This algorithm has been shown to be very effective at extracting good classifiers from datasets automatically.  However, as the random forest authors say:

 "But the cleverest algorithms are no substitute for human intelligence and knowledge of the data in the problem."  Leo Breiman and Adele Cutler

So, the question I'm posing is this: by inserting humans into the learning process can we improve it using their reasoning and background knowledge?

For HGF we replace the random input variable selection at step 2 above with expert guided variable selection.  (We may also let people guide the inference of the decision tree.)  The hypothesis is that the experts will choose feature sets that are better than the randomly selected ones - that will generalize to novel datasets with less error and produce more easily understood classifiers.  

As with standard RF, we need the HGF to produce many trees for each dataset with each tree having high classification performance and low overlap with the rest of the forest.  Ideally we would have each bootstrap of the training data converted into a tree by a different expert where the experts were drawn from a pool with highly diverse expertise.  This would require a significant investment of work from a large collection of expensive people..

Now, the next question is how on earth are we going to get a very large pool of skilled professionals to contribute their expertise to this project?  The answer we have been gravitating towards is games.  We hope to translate the feature selection problem into a game that knowledgable biologists and interested lay people will play for fun.

The formulation of the game(s) that will be used to drive an HGF implementation is very much a work in progress.  At the moment, the basic structure of our candidate games is that of a card game.  One way or another, players compose 'hands' of cards that correspond to features in a particular dataset.  For example, cards might correspond to genes from a gene expression dataset.  Hands are scored by testing the predictive performance of classifier trees inferred using the features in the hand and the training data (like one cycle of a random forest run).

Relation to Network Guided Forests

This idea is highly related to the concept of 'Network Guided Forests' (NGF) described by Dutkowski and Ideker in a PLoS paper last fall.  In that approach, the features used to build decision trees are constrained to related nodes within protein-protein interaction networks.  Features are selected for a given tree by picking one at random and then walking out along the network to bring in others in close proximity in the network.  The algorithm did not improve on classification performance in comparison to standard random forest as measured in cross-validation, but it did result in much more stable and coherent feature selection across several datasets.  It tended towards choosing genes that were known to relate to the phenotype of interest (e.g. breast cancer prognosis) much more often than random methods.  In comparison, NGF has the huge advantage that it can be used immediately based on data in databases without any dependence on human intelligence.  HGF has the theoretical advantage of tapping into a much broader collection of knowledge that is not limited to interaction data.  

Call for comments

At this point, this is just a nascent idea.  I have no evidence beyond intuition that it will succeed and there is a quite a bit of difficult work ahead to find out.  Any thoughts on it at this early point in time are most welcome!

Engines of Gamification

After years of talking about games for science, I'm finally going to jump in and make one.  I've got an idea (which I will elaborate on soon) and now I'm trying to figure out how to go about implementing it.  The challenge right now is to decide which of the infinite options that I should use to make it happen.

My basic requirements are pretty simple:

1. the game should be accessible in most Web browsers
2. it should run happily on an iPad
3. it should have basic graphics (e.g. blocks and arrows) and sounds
4. it should talk to a server running Java that will perform some computations and keep track of the data
5. it should enable fast prototyping
6. I should be able to do the prototyping myself

I discussed this with Josh Peay, a longtime game engineer at Sony and recent founder of mobile gaming company South Bird Studios, and he advocated jumping right in and learning a full-fledged game development system called Unity3d.  So I had a look.. and was immediately intimidated by its complexity.  It turns out that building immersive interactive games in a 3d environment still takes quite a bit of work - and quite a bit of artistic support - even with a hulking (2GB application) gaming engine in the background.  Since I really haven't conceived of anything that would benefit substantially from the level of interactive control offered by Unity or its brethren I'm really hesitant to start climbing up its learning curve.

Flash seems like it would probably do the job pretty well, but see #2 above.

And that leads me towards some sort of javascript environment.  Though I have played a bit with javascript before, I'm really not very good at it.  This causes me concern for #5 and #6 above.  To reduce this concern I've started looking for library support.

Here is a year-old list of 66 game-related javascript libraries that clearly is an underrepresentation of what is out there.  One that isn't listed is a Google product called PlayN (formerly 'forplay') based on GWT.  PlayN is tempting for me because you write your code in Java (which I guess is appealing to those of us in their thirties or greater) and it can generate deployable games in HTML5, Flash, the desktop and there are rumors maybe someday for iOS.  Its also easy to distribute the games via the Chrome store.  It doesn't have a lot of the Unity3d bells and whistles but, like I said, I don't need to use it to build the next Call of Duty.  Still, PlayN is still alpha code and, as my colleagues enjoy reminding me, Java and other compiled languages are for old farts...

Which to choose????

Update The interested gamifier might also like to have a look at the following frameworks for creating computerized versions of board and card games:

1. Vassal
2. Battlegrounds
3. ZunTzu

I like that you have the basics of player/card/board/hand/deck etc. management taken care of, there are nice realtime communication features ready out of the box and that you are provided with what appears to be a pretty straightforward development environment.  I don't like that players would have to install the engine on their computers before they could play the game and that none of them would work on an iPad.