Learning Binary Relations and Total Orders (Extended 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. >

Authors

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

Keywords

• Algorithm design and analysis
• Probability distribution
• Polynomials
• Prediction algorithms
• Laboratories
• Computer science
• Animals
• Predictive models
• Bipartite graph
• Size measurement
• Linear Order
• Binary Relation
• Lower Bound
• Upper Bound
• Efficient Algorithm
• Row Vector
• Query Sequence
• Binary Matrix
• Number Of Concepts
• Learning Session
• Positive Instances
• Negative Instances
• Counting Algorithm
• Random Bits
• Target Concept
• Proof Sketch
• Concept Of Class
• Number Of Mistakes
• Entries In Column
• Projective Geometry
• Exact Counts
• Head And Tail
• Learning Algorithms