Eric Martin

In the context of learning paradigms of identification in the limit, we address the question: why is uncertainty sometimes desirable? We use mind change bounds on the output hypotheses as a measure of uncertainty and interpret `desirable` as reduction in data memorization, also defined in terms of mind change bounds. The resulting model is closely related to iterative learning with bounded mind change complexity, but the dual use of mind change bounds - for hypotheses and for data - is a key distinctive feature of our approach. We show that situations exist where the more mind changes the learner is willing to accept, the less the amount of data it needs to remember in order to converge to the correct hypothesis. We also investigate relationships between our model and learning from good examples, set-driven, monotonic and strong-monotonic learners, as well as class-comprising versus class-preserving learnability. © 2007 Elsevier Ltd. All rights reserved.

Many connections have been established between learning and logic, or learning and topology, or logic and topology. Still, the connections are not at the heart of these fields. Each of them is fairly independent of the others when attention is restricted to basic notions and main results. We show that connections can actually be made at a fundamental level, and result in a logic with parameters that needs topological notions for its early developments, and notions from learning theory for interpretation and applicability. One of the key properties of first-order logic is that the classical notion of logical consequence is compact. We generalize the notion of logical consequence, and we generalize compactness to β-weak compactness where β is an ordinal. The effect is to stratify the set of generalized logical consequences of a theory into levels, and levels into layers. Deduction corresponds to the lower layer of the first level above the underlying theory, learning with less than β mind changes to layer β of the first level, and learning in the limit to the first layer of the second level. Refinements of Borel-like hierarchies provide the topological tools needed to develop the framework. © 2005 Elsevier B.V. All rights reserved.

The present work studies clustering from an abstract point of view and investigates its properties in the framework of inductive inference. Any class S considered is given by a hypothesis space, i.e., numbering, A(0), A(1),... of nonempty recursively enumerable (r. e.) subsets of N or Q(k). A clustering task is a finite and nonempty set of r. e. indices of pairwise disjoint such sets. The class S is said to be clusterable if there is an algorithm which, for every clustering task I, converges in the limit on any text for boolean OR(i is an element of I) A(i) to a finite set J of indices of pairwise disjoint clusters such that boolean OR(j is an element of J) A(j) = boolean OR(i is an element of I) A(i). A class is called semiclusterable if there is such an algorithm which finds a J with the last condition relaxed to boolean OR(j is an element of J) A(j) superset of boolean OR(i is an element of I) A(i). The relationship between natural topological properties and clusterability is investigated. Topological properties can provide sufficient or necessary conditions for clusterability, but they cannot characterize it. On the one hand, many interesting conditions make use of both the topological structure of the class and a well-chosen numbering. On the other hand, the clusterability of a class does not depend on which numbering of the class is used as a hypothesis space for the clusterer. These ideas are demonstrated in the context of naturally geometrically defined classes. Besides the text for the clustering task, clustering of many of these classes requires the following additional information: the class of convex hulls of finitely many points in a rational vector space can be clustered with the number of clusters as additional information. Interestingly, the class of polygons ( together with their interiors) is clusterable if the number of clusters and the overall number of vertices of these clusters is given to the clusterer as additional information. Intriguingly,