May 12, 2000
4:00

Fernando de Carvalho Gomes

A Stochastic Algorithm for Learning Decision Lists with limited Complexity

This work deals with learning decision lists from examples. In real world problems, data are often noisy and imperfectly described. It is commonly acknowledged that in such cases, consistent but inevitably complex classification procedures usually cause overfitting: results are perfect on the learning set but worse on new examples. Therefore, one searches for less complex procedures which are almost consistent or, in other words, for a good compromise between complexity and goodness of fit. We propose an optimization stochastic algorithm to search the space of the complexity-limited decision lists, where the minimization criterion is Vapnik's empirical risk.