Learning binary relations and total orders
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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
This publication has 9 references indexed in Scilit:
- Equivalence of models for polynomial learnabilityInformation and Computation, 1991
- A random polynomial time algorithm for approximating the volume of convex bodiesPublished by Association for Computing Machinery (ACM) ,1989
- Queries and concept learningMachine Learning, 1988
- Learning quickly when irrelevant attributes abound: A new linear-threshold algorithmMachine Learning, 1988
- Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolvedPublished by Association for Computing Machinery (ACM) ,1988
- Learning regular sets from queries and counterexamplesInformation and Computation, 1987
- A theory of the learnableCommunications of the ACM, 1984
- The complexity of approximate countingPublished by Association for Computing Machinery (ACM) ,1983
- The complexity of computing the permanentTheoretical Computer Science, 1979