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 + klog (n√ k ) is given, where n is the maximum component of any tuple seen. It is shown that this bound is approximately a log log 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).