Abstract
Several well-known inductive inference strategies change the actual hypothesis only when they discover that it “provably misclassifies” an example seen so far. This notion is made mathematically precise and its general power is characterized. In spite of its strength it is shown that this approach is not of universal power. Consequently, then hypotheses are considered which “unprovably misclassify” examples and the properties of this approach are studied. Among others it turns out that this type is of the same power as monotonic identification. Then it is shown that universal power can be achieved only when an unbounded number of alternations of these dual types of hypotheses is allowed. Finally, a universal method is presented enabling an inductive inference strategy to verify the incorrectness of any of its incorrect intermediate hypotheses.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
ANGLUIN, D. (1980), Inductive inference of formal languages from positive data, Information and Control 45, 117–135.
ANGLUIN, D., and SMITH, C. H. (1983), Inductive inference: Theory and methods, Computing Surveys 15, 237–269.
BARZDIN, J. (1971), Complexity and frequency solution of some algorithmically unsolvable problems, Doct. Diss., Novosibirsk State Univ. (Russian).
BARZDIN, J. (1974), Inductive inference of automata, functions and programs, in “Proceedings, International Congress of Mathematicians” pp.455–460.
BARZDIN, J., and FREIVALDS, R. (1972), On the prediction of general recursive functions, Soviet Math. Dokl. 13, 1224–1228.
BARZDIN, J., and FREIVALDS, R. (1974), Prediction and limit synthesis of recursively enumerable function classes, Theory of algorithms and programs, vol. 1, 100–111 (Russian).
BLUM, L., and BLUM, M. (1975), Toward a mathematical theory of inductive inference, Information and Control 28, 125–155.
CASE, J., and NGO MANGUELLE, S. (1979), Refinements of inductive inference by Popperian machines, Technical Report Nr. 152, Dept. of Computer Science, State Univ. of New York at Buffalo.
CASE, J., and SMITH, C. (1983), Comparison of identification criteria for machine inductive inference, Theoretical Computer Science 25, 193–220.
FREIVALDS, R., and BARZDIN, J. (1975), Relations between predictability and identifiability in the limit, Theory of algorithms and programs, vol.2, 26–34 (Russian).
FREIVALDS, R., KINBER, E. B., and WIEHAGEN, R. (199x), How inductive inference strategies discover their errors, Information and Computation (to appear)
FULK, M. A. (1988), Saving the phenomena: Requirements that inductive inference machines not contradict known data, Information and Computation 79, 193–209.
FULK, M. A. (1990), Robust separations in inductive inference, in “Proceedings, 31st IEEE Symposium on Foundations of Computer Science” pp.405–410.
FULK, M. A. (1991), personal communication to R. Wiehagen.
GOLD, E. M. (1967), Language identification in the limit, Information and Control 10, 447–474.
JANTKE, K. P. (1991), Monotonic and non-monotonic inductive inference, New Generation Computing 8, 349–360.
KLETTE, R., and WIEHAGEN, R. (1980), Research in the theory of inductive inference by GDR mathematicians — a survey, Information Sciences 22, 149–169.
KUMMER, M. (1992), personal communication to E. B. Kinber.
OSHERSON, D. N., STOB, M., and WEINSTEIN, S. (1986), “Systems that learn: An introduction to learning theory for cognitive and computer scientists”, MIT Press, Cambridge, Mass.
PODNIEKS, K. (1974), Comparing various types of limit synthesis and prediction of functions, Theory of algorithms and programs, vol.1, 68–81 (Russian).
POPPER, K. (1968), “The logic of scientific discovery”, 2nd ed. Harper Torch, New York.
ROGERS, H. (1967), “Theory of recursive functions and effective computability”, McGraw-Hill, New York.
“Theory of algorithms and programs”, vol.1, 2, 3 (1974, 1975, 1977), J. Barzdin, Ed., Latvian State Univ., Riga (Russian).
WIEHAGEN, R. (1976), Limes-Erkennung rekursiver Funktionen durch spezielle Strategien, Elektronische Informationsverarbeitung und Kybernetik 12, 93–99 (German).
WIEHAGEN, R. (1978a), Zur Theorie der algorithmischen Erkennung, Diss. B, Sektion Mathematik, Humboldt-Univ. Berlin (German).
WIEHAGEN, R. (1978b) Characterization problems in the theory of inductive inference, in “Proceedings, Int. Coll. on Automata, Languages and Programming”, G. Ausiello, C. Böhm, Eds., Lecture Notes in Computer Science 62, 494–508.
WIEHAGEN, R. (1991), A thesis in inductive inference, in “Proceedings, First International Workshop Nonmonotonic and Inductive Logic” 1990, J. Dix, K. P. Jantke, P. Schmitt, Eds., Lecture Notes in Artificial Intelligence 543, 184–207.
WIEHAGEN, R., and ZEUGMANN, T. (1994), Ignoring data may be the only way to learn efficiently, Journal of Experimental and Theoretical Artificial Intelligence 6, 131–144.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Freivalds, R., Kinber, E.B., Wiehagen, R. (1995). Error detecting in inductive inference. In: Jantke, K.P., Lange, S. (eds) Algorithmic Learning for Knowledge-Based Systems. Lecture Notes in Computer Science, vol 961. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60217-8_2
Download citation
DOI: https://doi.org/10.1007/3-540-60217-8_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60217-0
Online ISBN: 978-3-540-44737-5
eBook Packages: Springer Book Archive