Learning Integer Lattices

The problem of learning an integer lattice of Zᵏ in an on-line fashion is considered. That is, the learning algorithm is given a sequence of k-tuples of integers and predicts for each tuple in the sequence whether it lies in a hidden target lattice of Zᵏ. The goal of the algorithm is to minimize the number of prediction mistakes. An efficient learning algorithm with an absolute mistake bound of k + k (n k) is given, where n is the maximum component of any tuple seen. It is shown that this bound is approximately a n factor larger than the lower bound on the worst case number of mistakes given by the VC dimension of lattices that are restricted to \ - n, , 0, , n \ᵏ. This algorithm is used to learn rational lattices, cosets of lattices, an on-line word problem for abelian groups, and a subclass of the commutative regular languages. Furthermore, by adapting the results of D. Helmbold, R. Sloan, and M. K. Warmuth, Machine Learning, 5 (1990), pp. 165–196, one can efficiently learn nested differences of each of the above classes (e. g. , concepts of the form c₁ - (c₂ - (c₃ - (c₄ - c₅) ) ), where each cᵢ is the coset of a lattice).