Learning binary relations and total orders

Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages46-51
Number of pages6
ISBN (Print)0818619821, 9780818619823
DOIs
StatePublished - 1989
Externally publishedYes
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

Other30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/1/89

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Learning binary relations and total orders'. Together they form a unique fingerprint.

  • Cite this

    Goldman, S. A., Rivest, R. L., & Schapire, R. E. (1989). Learning binary relations and total orders. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 46-51). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1989.63454