On Online Learning of Decision Lists
Ziv Nevo, Ran El-Yaniv;
3(Oct):271-301, 2002.
Abstract
A fundamental open problem in computational learning theory is
whether there is an attribute efficient learning algorithm for the
concept class of decision lists (Rivest, 1987; Blum, 1996). We consider a
weaker problem, where the concept class is restricted to decision
lists with
D alternations. For this class, we present a novel
online algorithm that achieves a mistake bound of
O(
rD/log
n),
where
r is the number of relevant variables, and
n is the
total number of variables. The algorithm can be viewed as a
strict generalization of the famous Winnow algorithm by
Littlestone (1988), and improves the
O(
r^(2
D)/log
n) mistake
bound of Balanced Winnow. Our bound is stronger than a similar
PAC-learning result of Dhagat and Hellerstein (1994). A combination of our
algorithm with the algorithm suggested by Rivest (1987) might
achieve even better bounds.
[abs]
[pdf]
[ps.gz]
[ps]