Learning Integer Lattices
Abstract
Abstract We consider the problem of learning of an integer lattice of Zk 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 Zk . 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 k ) ] , where n is the maximum component of any tuple seen. We show that this bound is only a factor of roughly In In 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 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 c1 — (c 2 — (c 3 — (c 4 — c 5))) where each ci is the coset of a lattice).
Cite
Text
Helmbold et al. "Learning Integer Lattices." Annual Conference on Computational Learning Theory, 1990. doi:10.1016/B978-1-55860-146-8.50025-4Markdown
[Helmbold et al. "Learning Integer Lattices." Annual Conference on Computational Learning Theory, 1990.](https://mlanthology.org/colt/1990/helmbold1990colt-learning/) doi:10.1016/B978-1-55860-146-8.50025-4BibTeX
@inproceedings{helmbold1990colt-learning,
title = {{Learning Integer Lattices}},
author = {Helmbold, David P. and Sloan, Robert and Warmuth, Manfred K.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1990},
pages = {288-302},
doi = {10.1016/B978-1-55860-146-8.50025-4},
url = {https://mlanthology.org/colt/1990/helmbold1990colt-learning/}
}