Learning Integer Lattices

Abstract

The problem of learning an integer lattice of Z(k) 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(k). The goal of the algorithm is to minimize the number of prediction mistakes. An efficient learning algorithm with an absolute mistake bound of k + right perpendicular k log(n square-root k) left perpendicular 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}k. 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 c1 - (c2 - (c3 - (c4 - c5))), where each c(i) is the coset of a lattice).