UCSC-CRL-93-51: LEARNING BINARY RELATIONS USING WEIGHTED MAJORITY VOTING

12/01/1993 09:00 AM
Computer Science
In this paper we apply a weighted majority voting algorithm to the problem of learning a binary relation between two sets of objects. When using exponentially many weights, the mistake bound of the algorithm is essentially optimal. We present a construction where a number of copies of our algorithm divide the problem amongst themselves and learn the relation cooperatively. In this construction the total number of weights is polynomial. The mistake bounds are non- optimal (at least when compared to the best bound obtainable when computational resources are ignored) but significantly improve previous mistake bound bounds achieved by polynomial algorithms. Moreover our method can handle noise, which widens the applicability of the results.

UCSC-CRL-93-51