{'fraction_non_alphanumeric': 0.07392197125256673, 'fraction_numerical': 0.02053388090349076, 'mean_word_length': 4.895161290322581, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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.