Online Learning of Binary and n-ary Relations over Clustered Domains

摘要

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, 14⌊log k⌋⌊log l⌋+12(n−k) ⌊log k⌋+12(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.