Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Angluin, D. and Smith, C., 1983, “A Survey of inductive Inference: Theory and Methods”,Computing Surveys 15(3), 237–269.
Angluin, D. and Laird, P., 1988, “Learning from Noisy Examples”,Machine Learning 2, 343–370.
Benedek, G. M. and Itai, A. 1991, “Learnability with Respect to Fixed Distributions”,Theoretical Computer Science 86, 377–389.
Blum, L. and Blum, M., 1975, “Toward a Mathematical Theory of Inductive Inference”,Information and Control 28, 125–155.
Blumer, A., Ehrenfeucht, A., Haussler, D. and Warmuth, M. K., 1986, “Learnability and the Vapnik-Chervonenkis Dimension”,JACM 36(4), 926–965.
Dzeroskis, S., Muggleton, S. and Russell, S., 1992, “PAC-Learnability of Determinate Logic Programs”, inProc. 5th Annual ACM Workshop on Computational Learning Theory, New York, pp. 128–135.
Gold, E. M., 1967, “Language Identification in the Limit”,Information and Control 10, 447–474.
Kearns, M. and Li, M., 1988, “Learning in the Presence of Malicious Errors”, inProc. 21st ACM Symp. on on Theory of Comp., ACM, New York, pp. 267–280.
Kelly, K., 1995,The Logic of Reliable Inquiry, forthcoming.
Kelly, K. and Glymour, C., 1989, “Convergence to the Truth and Nothing but the Truth”,Philosophy of Science 56(2).
Lauth, B., 1993, “Inductive Inference in the Limit for First-Order Sentences”,Studia Logica 52, 491–517.
Lauth, B., 1994, “An Abstract Model for Inductive Inference”,Erkenntnis 40, 87–120.
Muggleton, S., 1991, “Inductive Logic Programming”,New Generation Computing 8, 295–318.
Osherson, D., Stob, M. and Weinstein, S., 1986,Systems that Learn, Cambridge, MA.
Osherson, D. and Weinstein, S., 1986, “Identification in the Limit of First Order Structures”,Journal of Philosophical Logic 15, 55–81.
Osherson, D. and Weinstein, S., 1989, “Paradigms of Truth Detection”,Journal of Philosophical Logic 18, 1–42.
Popper, K., 1968,The Logic Scientific Discovery, New York.
Popper, K., 1963,Conjectures and Refutations, London.
Popper, K., 1972,Objective Knowledge, Oxford.
Shapiro, E., 1981, “Inductive Inference of Theories from Facts”, Research Report 192, Dep. of Computer Science, Yale Univ.
Valiant, V., 1984, “A Theory of the Learnable”,Communications of the ACM 27(11), 1134–1142.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lauth, B. Inductive inference in the limit of empirically adequate theories. J Philos Logic 24, 525–548 (1995). https://doi.org/10.1007/BF01052601
Issue Date:
DOI: https://doi.org/10.1007/BF01052601