A GENERALIZED VERSION SPACE LEARNING ALGORITHM FOR NOISY AND UNCERTAIN DATA

This paper generalizes the learning strategy of version space to manag e noisy and uncertain training data. A new learning algorithm is propo sed that consists of two main phases: searching and pruning. The searc hing phase generates and collects possible candidates into a large set ; the pruning phase then prunes this set according to various criteria to find a maximally consistent version space. When the training insta nces cannot completely be classified, the proposed learning algorithm can make a trade-off between including positive training instances and excluding negative ones according to the requirements of different ap plication domains. Furthermore, suitable pruning parameters are chosen according to a given time limit, so the algorithm can also make a tra de-off between time complexity and accuracy. The proposed learning alg orithm is then a flexible and efficient induction method that makes th e version space learning strategy more practical.