Most standard results on structure identification in first order theories depend upon the correctness and completeness (in the limit) of the data, which are provided to the learner. These assumption are essential for the reliability of inductive methods and for their limiting success (convergence to the truth). The paper investigates inductive inference from (possibly) incorrect and incomplete data. It is shown that such methods can be reliable not in the sense of truth approximation, but in the sense that the methods (...) converge to "empirically adequate" theories, i.e. theories, which are consistent with all data (past and future) and complete with respect to a given complexity class of L-sentences. Adequate theories of bounded complexity can be inferred uniformly and effectively by polynomial-time learning algorithms. Adequate theories of unbounded complexity can be inferred pointwise by less efficient methods. (shrink)

This article reviews a number of different areas in the foundations of formal learning theory. After outlining the general framework for formal models of learning, the Bayesian approach to learning is summarized. This leads to a discussion of Solomonoff's Universal Prior Distribution for Bayesian learning. Gold's model of identification in the limit is also outlined. We next discuss a number of aspects of learning theory raised in contributed papers, related to both computational and representational complexity. The article concludes with a (...) description of how semi-supervised learning can be applied to the study of cognitive learning models. Throughout this overview, the specific points raised by our contributing authors are connected to the models and methods under review. (shrink)