Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T05:17:36.945Z Has data issue: false hasContentIssue false
  • English
  • Français

Robust separations in inductive inference

Published online by Cambridge University Press:  12 March 2014

Mark Fulk
Get access Rights & Permissions [Opens in a new window]

Abstract

Results in recursion-theoretic inductive inference have been criticized as depending on unrealistic self-referential examples. J. M. Bārzdiņš proposed a way of ruling out such examples, and conjectured that one of the earliest results of inductive inference theory would fall if his method were used. In this paper we refute Bārzdiņš' conjecture.

We propose a new line of research examining robust separations; these are defined using a strengthening of Bārzdiņš' original idea. The preliminary results of the new line of research are presented, and the most important open problem is stated as a conjecture. Finally, we discuss the extension of this work from function learning to formal language learning.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 2 , June 2011 , pp. 368 - 376
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[Bār74]Bārzdiņš, J., Two theorems on the limiting synthesis of functions, Theory of algorithms and programs, vol. 1, Latvian State University, 1974, In Russian, pp. 82–88.Google Scholar
[BB75]Blum, L. and Blum, M., Toward a mathematical theory of inductive inference, Information and Control, vol. 28 (1975), pp. 125–155.CrossRefGoogle Scholar
[Blu67]Blum, M., A machine-independent theory of the complexity of recursive functions, Journal of the ACM, vol. 14 (1967), pp. 322–336.CrossRefGoogle Scholar
[CJO+00]Case, J., Jain, S., Ott, M., Sharma, A., and Stephan, F., Robust learning aided by context, Journal of Computer and System Sciences, vol. 60 (2000), pp. 234–257, Special Issue for COLT'98.CrossRefGoogle Scholar
[CJSW94]Case, J., Jain, S., Stephan, F., and Wiehagen, R., Robust learning — rich and poor, Journal of Computer and System Sciences, vol. 69 (2004), no. 2, pp. 123–165.CrossRefGoogle Scholar
[CL82]Case, J. and Lynes, C., Machine inductive inference and language identification, Proceedings of the 9th International Colloquium on Automata, Languages and Programming (Nielsen, M. and Schmidt, E.M., editors), Lecture Notes in Computer Science, vol. 140, Springer-Verlag, 1982, pp. 107–115.CrossRefGoogle Scholar
[CS83]Case, J. and Smith, C., Comparison of identification criteria for machine inductive inference, Theoretical Computer Science, vol. 25 (1983), pp. 193–220.CrossRefGoogle Scholar
[Ful88]Fulk, M., Saving the phenomenon: Requirements that inductive machines not contradict known data, Information and Computation, vol. 79 (1988), pp. 193–209.CrossRefGoogle Scholar
[Ful90a]Fulk, M., Prudence and other conditions on formal language learning, Information and Computation, vol. 85 (1990), pp. 1–11.CrossRefGoogle Scholar
[Ful90b]Fulk, M., Robust separations in inductive inference, 31st Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1990, pp. 405–410.Google Scholar
[FJ94]Fulk, M. and Jain, S., Approximate inference and scientific method, Information and Computation, vol. 114 (1994), pp. 179–191.CrossRefGoogle Scholar
[Gol67]Gold, E.M., Language identification in the limit, Information and Control, vol. 10 (1967), pp. 447–474.CrossRefGoogle Scholar
[Jai99]Jain, S., Robust behaviorally correct learning, Information and Computation, vol. 153 (1999), no. 2, pp. 238–248.CrossRefGoogle Scholar
[JSW01]Jain, S., Smith, C., and Wiehagen, R., Robust learning is rich, Journal of Computer and System Sciences, vol. 62 (2001), no. 1, pp. 178–212.CrossRefGoogle Scholar
[KS89]Kurtz, S. and Smith, C., On the role of search for learning. Proceedings of the Second Annual Workshop on Computational Learning Theory (Rivest, R., Haussler, D., and Warmuth, M., editors). Morgan Kaufmann, 1989, pp. 303–311.CrossRefGoogle Scholar
[OSW86]Osherson, D., Stob, M., and Weinstein, S., Systems that learn: An introduction to learning theory for cognitive and computer scientists, MIT Press, 1986.Google Scholar
[OS02]Ott, M. and Stephan, F., Avoiding coding tricks by hyperrobust learning. Theoretical Computer Science, vol. 284 (2002), no. 1, pp. 161–180.CrossRefGoogle Scholar
[Rog67]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, 1967, Reprinted by MIT Press in 1987.Google Scholar
[Wie78]Wiehagen, R., Characterization problems in the theory of inductive inference, Proceedings of the Sth International Colloquium on Automata, Languages and Programming (Ausiello, G. and Böhm, C., editors), Lecture Notes in Computer Science, vol. 62, Springer-Verlag, 1978, pp. 494–508.CrossRefGoogle Scholar
[Zeu86]Zeugmann, T., On Bārzdiņš” conjecture, Analogical and inductive inference. Proceedings of the International Workshop (Jantke, K.P., editor). Lecture Notes in Computer Science, vol. 265. Springer-Verlag, 1986, pp. 220–227.CrossRefGoogle Scholar