ICML-98 Submission #92

On the Power of Decision Lists

Richard Nock, Pascal Jappy
LIRMM, 161 rue Ada, 34392 MONTPELLIER Cedex 5, FRANCE

Abstract

This paper adresses the problem of using decision lists for building
machine learning algorithms. In this work, we first highlight the
expressive power of decision lists, which were already known to
generalize decision trees. Here, we show that decision lists are in
fact much more general, in that they can match classes of Boolean
formalism capturing the expressive power of some kind of discrete
neural networks, or depth-3 circuits : the decision
committees. Decision lists therefore represent an excellent compromise
between expressive power and interpretability for rule-based
systems. We also present ICDL, a new algorithm for learning simple
Decision Lists.  This problem -learning low size and high accuracy
lists- is, as we prove formally, theoretically hard and calls for the
use of heuristics such as CN2, BruteDL or ICDL. Our method is based on
an original technique midway between learning rule based procedures
and decision trees. ICDL operates in two stages : it first greedily
builds a large decision list then prunes it to obtain a smaller yet
accurate one, thereby avoiding the drawbacks associated with the first
phase alone. Experimental results show the efficiency of our approach
by comparing them to the two well-known algorithms CN2 and
C4.5. ICDL's time complexity is low. It produces decision lists whose
size is far smaller compared to both CN2 and C4.5, and whose accuracy
also compares favourably with theirs.

Keywords:
Decision Lists, Learning from Examples, CART

Email adress of contact author:
nock@lirmm.fr

Phone number of contact author:
(+33) 4 67 41 85 78