07/01/1990 09:00 AM
Computer Science
We consider the problem of learning of an integer lattice of Z^k in an on-line fashion. 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. We give an efficient learning algorithm with an absolute mistake bound of k + | k log (n sqrt{k}) | , where n is the maximum component of any tuple seen. We show 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, adapting the results of previous work, we can efficiently learn nested differences of each of the above classes (e.g.\\ concepts of the form c_1- (c_2-(c_3-(c_4-c_5))) where each c_i is the coset of a lattice).
