New algorithms for attribute-efficient on-line linear learning
This thesis describes an investigation of old and new on-line linear learning algorithms and their attribute-efficiency properties. When large amounts of irrelevent information, in the form of noninformative attributes, is given to some on-line learning algorithms, the number of prediction errors for particular concept classes rises drastically. Other learners, those with the property of attribute-efficiency, incur only a small increase in errors. 
The Winnow algorithm class is attribute-efficient, and is a standard alternative to the non-attribute-efficient Perceptron algorithm commonly used to learn on-line linear concepts (Littlestone 1988, Littlestone 1989, Kivenen et al. 1997, Blum 1995, Golding and Roth, 1999). Recent work has identified the Incremental Delta-Bar-Delta (IDBD) algorithm as probably attribute-efficient (Harris and Reichler 2001, Harris 2002). IDBD was proposed by Sutton (1992) as an on-line linear learning algorithm that learns particularly quickly. A major component of this thesis is to argue that IDBD is actually attribute-efficient, and to identify which components of the algorithm underly that property. 
A set of IDBD variations is introduced, allowing targeted experimental work and tractable theoretical work. The most important new algorithm is Second-order Perceptron, exponential and symmetric (2Pes), which omits a complicating factor from IDBD, but improves upon IDBD's attribute-efficiency. 
Two proofs of attribute-efficiency are reported. In one, the 2Pes algorithm is shown to be attribute-efficient to the same extent as Winnow. In the other, another variation on IDBD and 2Pes is shown to have a lesser level of attribute-efficiency. Experimental results support this theoretical work, showing attribute-efficiency for 2Pes that often provides better results than even Winnow. Other experiments identify subtleties important to understanding the relative strengths and weaknesses of each algorithm. 
Another significant goal of this work was to identify the inductive biases of each algorithm, so that they can be fairlycompared with each other. By examining their biases and properties using the results presented here, it is possible to view 2Pes as a particular generalization of the Winnow algorithm, and IDBD as a further generalization of 2Pes. Understanding these relationships furthers the potential of attribute-efficient algorithms for real-world applications.