Algebraic Structure of Some Learning Systems

Abstract

The goal of this research is to define some general properties of representation languages, e.g. lattice structures, distributive lattice structures, cylindric algebras, etc. to which generalization algorithms could be related. This paper introduces a formal framework providing a clear description of version space. It is of great theoretical interest since it makes the generalization and comparison of many machines learning algorithms possible. Moreover, it could lead to reconsider some aspects of the classical description of version space. In this paper, the scope of investigation will be restricted to lattices — i.e. to cases where there exists one and only one generalization for any set of examples — and in particular to Brouwerian lattices. It is shown that a particularly interesting case covered by this restriction is the product of hierarchical posets which is equivalent to the conjunction of tree structured or linearly ordered attributes.