Title :
Learning binary relations and total orders
Author :
Goldman, Sally A. ; Rivest, Ronald L. ; Schapire, Robert E.
Author_Institution :
MIT Lab. for Comput. Sci., Cambridge, MA, USA
fDate :
30 Oct-1 Nov 1989
Abstract :
The problem of designing polynomial prediction algorithms for learning binary relations is studied for an online model in which the instances are drawn by the learner, by a helpful teacher, by an adversary, or according to a probability distribution on the instance space. The relation is represented as an n×m binary matrix, and results are presented when the matrix is restricted to have at most k distinct row types, and when it is constrained by requiring that the predicate form a total order
Keywords :
computational complexity; learning systems; matrix algebra; adversary; binary matrix; binary relations; distinct row types; helpful teacher; instance space; learner; learning; online model; polynomial prediction algorithms; predicate; probability distribution; total orders; Algorithm design and analysis; Animals; Bipartite graph; Computer science; Laboratories; Polynomials; Prediction algorithms; Predictive models; Probability distribution; Size measurement;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63454
