On learning Decision Committees

摘要

This paper presents decision committees. A decision committee contains rules, each of these beeing a couple (monomial, vector). Each monomial is a condition that, when matched by an instance, returns its vector. When each monomial is tested, the sum of the returned vectors is used to take the clas-sification decision. We show that for every constant k, the subclass of decision committees whose elements have monomial of length <= k is pac-learnable and that it properly contains k-DL. However, we also show that the problem of inducing the shortest consistent decision committee is NP-Hard. This leads to theoretical results on non-learnability, and to negative considerations for practical optimization problems on decision committees. A two-stages heuristic algorithm, IDC, is presented, that learns by a particular subclass of decision committees. It first chooses monomials by a breadth-first search inspired from branch-and-bound algorithms. Then it clusters gradually the resulting rules to form decision committees, according to the minimization of empirical risk. Finally it selects the decision committee over the final population, which is the best according to the learning sample. Experimental results on 15 artificial and real domains tend to show that IDC achieves good results, while constructing small, and interpretable decision committees.