Learning Integer Lattices

Résumé du livre

We show that this bound is only a factor of roughly ln ln n 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][superscript 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 [HSW90], we 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[subscript i] is the coset of a lattice).