On Online Learning of Decision Lists

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(rDlog 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(r2Dlog 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.

• Publication year

  2003

• Venue

  Journal of machine learning research

• Publication date

  2003-03-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1162/153244303765208395
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Learning decision lists

  2004influential reference
• On Online Learning of Decision Lists

  2002cited by this paper
• Decision lists and related Boolean functions

  2002cited by this paper
• Monotone term decision lists

  2001cited by this paper
• Computational sample complexity and attribute-efficient learning

  1999influential reference
• Attribute-efficient learning in query and mistake-bound models

  1998cited by this paper
• Projection Learning

  1998influential reference
• On-line Algorithms in Machine Learning

  1996cited by this paper
• PAC learning with irrelevant attributes

  1994influential reference
• Computational learning theory: an introduction

  1992cited by this paper
• Rank-r Decision Trees are a Subclass of r-Decision Lists

  1992cited by this paper
• Learning in the presence of finitely or infinitely many irrelevant attributes

  1991cited by this paper
• Learning functions of k terms

  1990influential reference
• Mistake bounds and logarithmic linear-threshold learning algorithms

  1990cited by this paper
• Learning Nested Differences of Intersection-Closed Concept Classes

  1989cited by this paper
• Occam's Razor

  1987cited by this paper
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

  1987influential reference
• A theory of the learnable

  1984influential reference

• Privately Learning Decision Lists and a Differentially Private Winnow

  2026cites this paper
• From Online to Non-i.i.d. Batch Learning

  2020cites this paper
• Decision list compression by mild random restrictions

  2019cites this paper
• A General Memory-Bounded Learning Algorithm

  2017cites this paper
• Cognitive Reasoning and Learning Mechanisms

  2016cites this paper
• Firewall Policy Reconnaissance: Techniques and Analysis

  2014cites this paper
• Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions

  2012cites this paper
• Power-saving algorithms in electricity usage - comparison between the power saving algorithms and machine learning techniques

  2010cites this paper
• FireCracker: A Framework for Inferring Firewall Policies using Smart Probing

  2007cites this paper
• Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions

  2006cites this paper
• Kernels as features: On kernels, margins, and low-dimensional mappings

  2006cites this paper
• Toward Attribute Efficient Learning of Decision Lists and Parities

  2006cites this paper
• Learning with Decision Lists of Data-Dependent Features

  2005cites this paper
• Learning Comprehensible Theories from Structured Data

  2005cites this paper
• Toward Attribute Efficient Learning Algorithms

  2003cites this paper
• Toward Attribute E cient Learning Algorithms

  year unknowncites this paper