@Article{GRS93, author = { Sally A. Goldman and Ronald L. Rivest and Robert E. Schapire }, title = { Learning binary relations and total orders }, journal = { SIAM Journal on Computing }, issn = { 0097-5397 }, publisher = { SIAM }, OPTyear = { 1993 }, OPTmonth = { October }, date = { 1993-10 }, volume = { 22 }, number = { 5 }, pages = { 1006--1034 }, url = { http://link.aip.org/link/?SMJ/22/1006/1 }, doi = { 10.1137/0222062 }, keywords = { machine learning; computational learning theory; on-line learning; mistake-bounded learning; binary relations; total orders; fully polynomial randomized approximation schemes }, abstract = { The problem of learning a binary relation between two sets of objects or between a set and itself is studied. This paper represents a binary relation between a set of size $n$ and a set of size $m$ as an $n \times 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 are presented for learning binary relations 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. \par The first part of this paper presents results for the case in which the matrix of the relation has at most $k$ row types. It presents 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. Furthermore, it describes a technique that simplifies the proof of expected mistake bounds against a randomly chosen query sequence. \par In the second part of this paper the problem of learning a binary relation that is a total order on a set is considered. A general technique using a fully polynomial randomized approximation scheme (fpras) to implement a randomized version of the halving algorithm is described. This technique is applied to the problem of learning a total order, through the use of an fpras for counting the number of extensions of a partial order, to obtain a polynomial prediction algorithm that with high probability makes at most $n\lg n + (\lg e)\lg n$ mistakes when an adversary selects the query sequence. The case in which a teacher or the learner selects the query sequence is also considered }, }