Learning Binary Relations and Total Orders
Abstract
Learning a binary relation between two sets of objects or between a set and itself represents a binary relation between a set of size n and a set of size m as an n x m matrix of bits, whose (i,j) entry is 1 if and only if the relation holds between the corresponding elements of the two sets. Polynomial prediction algorithms for learning binary relations are present in an extended on-line learning model, where the examples are drawn by the learner, by a helpful teacher, by an adversary, or according to a uniform probability distribution on the instance space. Results are presented for the case that the matrix of the relation has at most k row types with upper and lower bounds on the number of prediction mistakes any prediction algorithm makes when learning such a matrix under the extended on-line learning model. A technique is described that simplifies the proof of expected mistake bounds against a randomly chosen query sequence. (JHD)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1990
- Accession Number
- ADA221643
Entities
People
- Robert E. Schapire
- Ronald L. Rivest
- Sally A. Goldman
Organizations
- Massachusetts Institute of Technology