About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Computer and System Sciences
Paper
Online learning of binary and n-ary relations over clustered domains
Abstract
We consider the online learning problem for binary relations defined over two finite sets, each clustered into a relatively small number k, l of types (such a relation is termed a (k, l)-binary relation), extending the models of S. Goldman, R. Rivest, and R. Schapire (1993, SIAM J. Comput. 22, 1006-1034). We investigate the learning complexity of (k, l)-binary relations with respect to both the self-directed and adversary-directed learning models. We also generalize this problem to the learning problem for (k1, . . ., kd)-d-ary relations. In the self-directed model, we exhibit an efficient learning algorithm which makes at most kl + (n - k)log k + (m -l)log l mistakes, where n and m are the number of rows and columns, roughly twice the lower bound we show for this problem, 1/4⌊log k⌋ ⌊log l⌋ + 1/2(n - k) ⌊log k⌋ + 1/2(m -l) ⌊log l⌋. In the adversary-directed model, we exhibit an efficient algorithm for the (2,2)-binary relations, which makes at most n + m + 2 mistakes, only two more than the lower bound we show for this problem, n + m. As for (k1, . . ., kd)-d-ary relations, we obtain lower bounds and upper bounds on the number of mistakes in the self-directed model, teacher-directed model, and adversary-directed model. Finally we show that, although the sample consistency problem for (2,2)-binary relations is solvable in polynomial time, the same problem for (2,2,2)-ternary relations is already NP-complete. © 2002 Elsevier Science (USA).