TY - GEN

T1 - Efficiency versus convergence of boolean kernels for on-line learning algorithms

AU - Khardon, Roni

AU - Roth, Dan

AU - Servedio, Rocco

PY - 2002

Y1 - 2002

N2 - We study online learning in Boolean domains using kernels which capture feature expansions equivalent to using conjunctions over basic features. We demonstrate a tradeoff between the computational efficiency with which these kernels can be computed and the generalization ability of the resulting classifier. We first describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efficiently run the Perceptron algorithm over an exponential number of conjunctions; however we also prove that using such kernels the Perceptron algorithm can make an exponential number of mistakes even when learning simple functions. We also consider an analogous use of kernel functions to run the multiplicative-updateWinnow algorithm over an expanded feature space of exponentially many conjunctions. While known upper bounds imply that Winnow can learn DNF formulae with a polynomial mistake bound in this setting, we prove that it is computationally hard to simulate Winnow's behavior for learning DNF over such a feature set, and thus that such kernel functions for Winnow are not efficiently computable.

AB - We study online learning in Boolean domains using kernels which capture feature expansions equivalent to using conjunctions over basic features. We demonstrate a tradeoff between the computational efficiency with which these kernels can be computed and the generalization ability of the resulting classifier. We first describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efficiently run the Perceptron algorithm over an exponential number of conjunctions; however we also prove that using such kernels the Perceptron algorithm can make an exponential number of mistakes even when learning simple functions. We also consider an analogous use of kernel functions to run the multiplicative-updateWinnow algorithm over an expanded feature space of exponentially many conjunctions. While known upper bounds imply that Winnow can learn DNF formulae with a polynomial mistake bound in this setting, we prove that it is computationally hard to simulate Winnow's behavior for learning DNF over such a feature set, and thus that such kernel functions for Winnow are not efficiently computable.

UR - http://www.scopus.com/inward/record.url?scp=84898963616&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84898963616&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84898963616

SN - 0262042088

SN - 9780262042086

T3 - Advances in Neural Information Processing Systems

BT - Advances in Neural Information Processing Systems 14 - Proceedings of the 2001 Conference, NIPS 2001

PB - Neural information processing systems foundation

T2 - 15th Annual Neural Information Processing Systems Conference, NIPS 2001

Y2 - 3 December 2001 through 8 December 2001

ER -