Learning Binary Relations Using Weighted Majority Voting

Authors: Goldman S.A.¹; Warmuth M.K.²

Source: Machine Learning, Volume 20, Number 3, September 1995 , pp. 245-271(27)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

In this paper we demonstrate how weighted majority voting with multiplicative weight updating can be applied to obtain robust algorithms for learning binary relations. We first present an algorithm that obtains a nearly optimal mistake bound but at the expense of using exponential computation to make each prediction. However, the time complexity of our algorithm is significantly reduced from that of previously known algorithms that have comparable mistake bounds. The second algorithm we present is a polynomial time algorithm with a non-optimal mistake bound. Again the mistake bound of our second algorithm is significantly better than previous bounds proven for polynomial time algorithms.

A key contribution of our work is that we define a “non-pure” or noisy binary relation and then by exploiting the robustness of weighted majority voting with respect to noise, we show that both of our algorithms can learn non-pure relations. These provide the first algorithms that can learn non-pure binary relations.

Keywords: on-line learning; mistake-bounded learning; weighted majority voting; noise tolerance; binary relation

Language: English

Document Type: Research article

Affiliations: 1: Dept. of Computer Science, Washington University, St. Louis, MO 63130. sg@cs.wustl.edu 2: Dept. of Computer and Information Sciences, University of California, Santa Cruz, CA 95064. manfred@cs.ucsc.edu

Publication date: 1995-09-01