home | library | feedback

Searching for the best model

For us, best model is the model that will most accurately classify unclassified data vectors. We have means to estimate this out-of-sample performance, but our model set often contains so many models that it is impossible to go through all the models and pick the estimated most predictively accurate one. That is why we have to search.

Computer science and fast computers

The bad news is that in computer science it is practically proved that no matter how smart computational methods are and no matter how fast the computers will be in a future, there will never be a fast way to find out for sure the best model unless the number of variables is very small. On the other hand, this is not anything extraordinary, it is very common in computer science. That is why in computer science researchers have developed many computer programs that deal with these "impossible" problems. In our case it means that it takes time to find a good model, and still we cannot be sure that we find the best one. But sometimes we may find the best one (although there is no way of knowing that) and usually we find a very good one (maybe second best or third, again cannot know for sure).

Simple and greedy random search

To get an idea of the search we describe a very simple random search. It goes as follows. We pick one model at random and declare it the best model so far (which it is since it is the only one). We then pick another model at random and compare the predictive accuracy of this second model to the accuracy of the best model so far. If the accuracy of the second model is bigger than the accuracy of the best model so far (the first model) we declare the second model to be the best model and we throw away the old champion. If, on the other hand, the accuracy of the second model is less than the accuracy of the best model so far, the old champion can keep its title and we throw away the second model.

We then continue picking up models at random and we always compare the predictive accuracy of the freshly picked model to the accuracy of the best model so far. The one that wins this comparison is declared the current best model and the other is dumped. This game can be continued forever (since we put the loosing models back to the pool where we pick them.) When we get tired playing this game, we stop and declare the current best model to be result of our search.

B-Course can do better

However, it is possible to do something smarter. Namely, the models which resemble each other a lot (i.e., they have almost same variables and discretizations) are likely to be almost equally good. This leads us to a search strategy, where we do not pick models from a set of models randomly, but we pick models that resemble the current best model. These models are more likely to be predictively more accurate than the current best model than if we picked the models randomly.

We can also abandon our habit of always dumping the looser and collect a set of relatively good models. We can then try to combine the best parts of these models so that the resulting combined model is better than any of the original models. This is roughly the idea of what computer scientists call genetic algorithms.

There are many more tricks like sometimes dumping the better model (algorithms like hill climbing, simulated annealing) or trying to avoid picking similar model twice (tabu search). There is also systems that learn to search better by experience.

B-Course is not committed to any particular search strategy. The underlying search engine in B-Course is frequently and without notification improved.

B-Course informs about its search

When asked about an intermediate or a final search status, B-Course sometimes reports having evaluated a very large amount of models. As the search routine has limited memory, these numbers are not exact. When it encounters a model it cannot remember seeing before, it counts the model as a new one. So sometimes the search routine evaluates and counts the same model more than once. It is true when B-Course says that it has evaluated very many models, however they are not necessarily different models.


  B-Course, version 2.0.0
CoSCo 2002