Hostname: page-component-848d4c4894-p2v8j Total loading time: 0 Render date: 2024-05-07T15:56:02.127Z Has data issue: false hasContentIssue false
  • English
  • Français

Parsimony hierarchies for inductive inference

Published online by Cambridge University Press:  12 March 2014

Andris Ambainis ,
John Case ,
Sanjay Jain  and
Mandayam Suraj
Andris Ambainis
Affiliation:
Institute of Mathematics and Computer Science, University of Latvia, Raina Bulv. 29, Riga, LV-1459, Latvia, E-mail: ambainis@lanet.lv
John Case
Affiliation:
Department of Computer and Information Sciences, University of Delaware, Newark, de 19716, USA, E-mail: case@cis.udel.edu
Sanjay Jain
Affiliation:
School of Computing, National University of Singapore, Singapore 119260, Republic of Singapore, E-mail: sanjay@comp.nus.edu.sg
Mandayam Suraj
Affiliation:
Department of Computer and Information Sciences, University of Delaware, Newark, de 19716, USA, E-mail: suraj@cis.udel.edu
Get access Rights & Permissions [Opens in a new window]

Abstract

Freivalds defined an acceptable programming system independent criterion for learning programs for functions in which the final programs were required to be both correct and “nearly” minimal size. i.e.. within a computable function of being purely minimal size. Kinber showed that this parsimony requirement on final programs limits learning power. However, in scientific inference, parsimony is considered highly desirable. A lim-computable function is (by definition) one calculable by a total procedure allowed to change its mind finitely many times about its output. Investigated is the possibility of assuaging somewhat the limitation on learning power resulting from requiring parsimonious final programs by use of criteria which require the final, correct programs to be “not-so-nearly” minimal size, e.g., to be within a lim-computable function of actual minimal size. It is shown that some parsimony in the final program is thereby retained, yet learning power strictly increases. Considered, then, are lim-computable functions as above but for which notations for constructive ordinals are used to bound the number of mind changes allowed regarding the output. This is a variant of an idea introduced by Freivalds and Smith. For this ordinal notation complexity bounded version of lim-computability, the power of the resultant learning criteria form finely graded, infinitely ramifying, infinite hierarchies intermediate between the computable and the lim-computable cases. Some of these hierarchies, for the natural notations determining them, are shown to be optimally tight.

Keywords

Computational learning theoryminimal size programconstructive ordinal notationslimiting computable function
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 69 , Issue 1 , March 2004 , pp. 287 - 327
Copyright
Copyright © Association for Symbolic Logic 2004

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

[Add65]Addison, J. W., The method of alternating chains, Theory of models. (Proceedings of the 1963 International Symposium) (Berkeley, California) (Addison, J. W., Henkin, Leon, and Tarski, Alfred, editors), North-Holland, Amsterdam, 1965, pp. 1–16.Google Scholar
[Amb95]Ambainis, A., The power of procrastination in inductive inference: How it depends on used ordinal notations, EuroCOLT'95, Lecture Notes in Computer Science, vol. 904, 1995, pp. 99–111.Google Scholar
[AFS99]Ambainis, A., Freivalds, R., and Smith, C. H., Inductive inference with procrastination: Back to definitions, Fundamenta Informaticae, vol. 40 (1999), pp. 1–16.CrossRefGoogle Scholar
[AJS99]Ambainis, A., Jain, S., and Sharma, A., Ordinal mind change complexity of language identification, Theoretical Computer Science, vol. 220 (1999), no. 2, pp. 323–343.Google Scholar
[Ang80]Angluin, D., Finding patterns common to a set of strings, Journal of Computer and System Sciences, vol. 21 (1980), pp. 46–62.Google Scholar
[Aps94]Apsītis, K., Derived sets and inductive inference, Algorithmic learning theory, Proceedings of the 4th International Workshop on Analogical and Inductive Inference (AII'94) and the 5th International Workshop on Algorithmic Learning Theory (ALT'94), October 10–15, 1994 (Reinhardsbrunn Castle, Germany) (Arikawa, Setsuo and Jantke, Klaus P., editors), Lecture Notes in Artificial Intelligence, vol. 872, Springer-Verlag, 1994, pp. 26–39.Google Scholar
[ASY92]Arikawa, S., Shinohara, T., and Yamamoto, A., Learning elementary formal systems, Theoretical Computer Science, vol. 95 (1992), pp. 97–113.Google Scholar
[Beh97]Behounek, L., Ordinal calculator, 1997, Web document at: http://www.ff.cuni.cz/~behounek/ordinalc.htm.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
[BM95]Bratko, I. and Muggleton, S., Applications of inductive logic programming, Communications of the ACM, vol. 38 (1995), no. 11, pp. 65–70.CrossRefGoogle Scholar
[BUV96]Brazma, A., Ukkonen, E., and Vilo, J., Discovering unbounded unions of regular pattern languages from positive examples, Proceedings of the Seventh International Symposium on Algorithms and Computation (ISAAC'96) (Osaka, Japan), Lecture Notes in Computer Science, vol. 1178, 1996, pp. 95–104.Google Scholar
[Cas74]Case, J., Periodicity in generations of automata, Mathematical Systems Theory, vol. 8 (1974). pp. 15–32.CrossRefGoogle Scholar
[Cas94]Case, J., Infinitary self-reference in learning theory, Journal of Experimental and Theoretical Artificial Intelligence, vol. 6 (1994), pp. 3–16.Google Scholar
[CJK+01]Case, J., Jain, S., Kaufmann, S., Sharma, A., and Stephan, F., Predictive learning models for concept drift, Theoretical Computer Science, vol. 268 (2001), pp. 323–349, Special Issue for ALT'98.Google Scholar
[CJLZ99]Case, J., Jain, S., Lange, S., and Zeugmann, T., Incremental concept learning for bounded data mining, Information and Computation, vol. 152 (1999), pp. 74–110.Google Scholar
[CJS96]Case, J., Jain, S., and Sharma, A., Machine induction without revolutionary changes in hypothesis size, Information and Computation, vol. 128 (1996), pp. 73–86.CrossRefGoogle Scholar
[CJS95]Case, J., Jain, S., and Suraj, M., Not-so-nearly-minimal-size program inference, Algorithmic learning for knowledge-based systems (Jantke, Klaus P. and Lange, Steffen, editors), Lecture Notes in Artificial Intelligence, vol. 961, Springer-Verlag. 1995, pp. 77–96.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
[CS03]Case, J. and Suraj, M., Characterizing Ershov hierarchies by algorithmic O-count down, Working paper, 2003.Google Scholar
[Che82]Chen, K., Tradeoffs in inductive inference of nearly minimal sized programs, Information and Control, vol. 52 (1982), pp. 68–86.CrossRefGoogle Scholar
[EHK81]Epstein, R. L., Haas, R., and Kramer, R. L., Hierarchies of sets and degrees below 0′, Logic year 1979–80, Lecture Notes in Mathematics, vol. 859, Springer-Verlag, Heidelberg, 1981, pp. 32–48.Google Scholar
[Ers68a]Ershov, Yu. L., A hierarchy of sets, I, Algebra i Logika, vol. 7 (1968), no. 1, pp. 47–74, In Russian (English translation in Algebra and Logic, vol. 7 (1968), pp. 25–43.Google Scholar
[Ers68b]Ershov, Yu. L., A hierarchy of sets, II, Algebra i Logika, vol. 7 (1968), no. 4, pp. 15–47, In Russian (English translation in Algebra and Logic, vol. 7 (1968), pp. 212–232.Google Scholar
[Ers70]Ershov, Yu. L., A hierarchy of sets, III, Algebra i Logika, vol. 9 (1970), no. 1, pp. 34–51, In Russian (English translation in Algebra and Logic, vol. 9 (1970), pp. 20–31.Google Scholar
[Fre75]Freivalds, R., Minimal Gödel numbers and their identification in the limit, Proceedings of the 4th Symposium on Mathematical Foundations of Computer Science (Becvár, Jirí, editor), Lecture Notes in Computer Science, vol. 32, 1975, pp. 219–225.Google Scholar
[Fre90]Freivalds, R., Inductive inference of minimal programs, Proceedings of the Third Annual Workshop on Computational Learning Theory (Fulk, M. and Case, J., editors), Morgan Kaufmann Publishers, Inc., 08 1990, pp. 3–20.Google Scholar
[FS93]Freivalds, R. and Smith, C., On the role of procrastination in machine learning, Information and Computation, vol. 107 (1993), no. 2, pp. 237–271.Google Scholar
[FW79]Freivalds, R. and Wiehagen, R., Inductive inference with additional information, Electronische Informationverarbeitung und Kybernetik, vol. 15 (1979), pp. 179–195.Google Scholar
[Ful85]Fulk, M., A study of inductive inference machines, Ph.D. thesis, SUNY at Buffalo, 1985.Google Scholar
[GD01]Gale, A. and Downey, R., On genericity and Ershov's hierarchy, Mathematical Logic Quarterly, vol. 47 (2001), no. 2, pp. 161–182.3.0.CO;2-E>CrossRefGoogle Scholar
[GS95]Gasarch, W. I. and Smith, C. H., Recursion theoretic models of learning: some results and intuitions, Annals of Mathematics and Artificial Intelligence, vol. 15 (1995), no. 2, pp. 151–166.Google Scholar
[Gol67]Gold, E., Language identification in the limit, Information and Control, vol. 10 (1967), pp. 447–474.CrossRefGoogle Scholar
[JORS99]Jain, S., Osherson, D., Royer, J., and Sharma, A., Systems that learn: An introduction to learning theory, second ed., MIT Press, Cambridge, Mass., 1999.Google Scholar
[JS97]Jain, S. and Sharma, A., Elementary formal systems, intrinsic complexity, and procrastination, Information and Computation, vol. 132 (1997), pp. 65–84.CrossRefGoogle Scholar
[JS99]Jain, S. and Sharma, A., Mind change complexity of learning logic programs, Fourth European Conference on Computational Learning Theory (Fischer, P. and Simon, H. U., editors), Lecture Notes in Artificial Intelligence, vol. 1572, Springer-Verlag, Berlin, 1999, pp. 198–213.Google Scholar
[JS01]Jain, S. and Sharma, A., On a generalized notion of mistake bounds, Information and Computation, vol. 166 (2001), pp. 156–166.Google Scholar
[Joc82]Jockusch, C. G. Jr., Review of “Hierarchies of Sets and Degrees Below 0′” by Richard L. Epstein, Richard Haas, and Richard L. Kramer, Mathematical Reviews, (1982), MR 82k:03073.Google Scholar
[KMU95]Kilpeläinen, P., Mannila, H., and Ukkonen, E., MDL learning of unions of simple pattern languages from positive examples, Second European Conference on Computational Learning Theory (Vitanyi, Paul, editor). Lecture Notes in Artificial Intelligence, vol. 904, Springer-Verlag, 1995, pp. 252–260.Google Scholar
[Kin74]Kinber, E., On the synthesis in the limit of almost minimal Gödel numbers, Theory of algorithms and programs, vol. 1, Latvian State University, Riga, 1974, pp. 221–223.Google Scholar
[Kle38]Kleene, S. C., On notation for ordinal numbers, this Journal, vol. 3 (1938), pp. 150–155.Google Scholar
[Kle44]Kleene, S. C., On the forms of predicates in the theory of constructive ordinals, American Journal of Mathematics, vol. 66 (1944), pp. 41–58.Google Scholar
[Kle55]Kleene, S. C., On the forms of predicates in the theory of constructive ordinals (second paper), American Journal of Mathematics, vol. 77 (1955), pp. 405–428.CrossRefGoogle Scholar
[KM67]Kuratowski, K. and Mostowski, A., Set theory, North-Holland, 1967.Google Scholar
[LD94]Lavrač, N. and Džeroski, S., Inductive logic programming: Techniques and applications, Ellis Horwood, 1994.Google Scholar
[MY78]Machtey, M. and Young, P., An introduction to the general theory of algorithms, North Holland, New York, 1978.Google Scholar
[Mit97]Mitchell, T., Machine learning, McGraw Hill, 1997.Google Scholar
[MR94]Muggleton, S. and de Raedt, L., Inductive logic programming: Theory and methods, Journal of Logic Programming, vol. 19/20 (1994), pp. 669–679.Google Scholar
[Nix83]Nix, R., Editing by examples, Technical Report 280, Department of Computer Science, Yale University, New Haven, CT, USA, 1983.Google Scholar
[Odi99]Odifreddi, P., Classical recursion theory, vol. II, Elsevier, Amsterdam, 1999.Google Scholar
[Put63]Putnam, H., Probability and confirmation, Voice of America, Forum on Philosophy of Science, 10, 1963.Google Scholar
[Put65]Putnam, H., Trial and error predicates and the solution to a problem of Mostowski, this Journal, vol. 30 (1965), pp. 49–57.Google Scholar
[Rog58]Rogers, H., Gödel numberings of partial recursive functions, this Journal, vol. 23 (1958), pp. 331–341.Google Scholar
[Rog67]Rogers, H., Theory of recursive functions and effective computability, McGraw Hill, New York, 1967, Reprinted, MIT Press, 1987.Google Scholar
[Roy87]Royer, J., A connotational theory of program structure, Lecture Notes in Computer Science, vol. 273, Springer-Verlag, Berlin, 1987.Google Scholar
[Sac90]Sacks, G., Higher recursion theory, Springer-Verlag, 1990.Google Scholar
[Sal94a]Salomaa, A., Patterns (The Formal Language Theory Column), The Bulletin for the European Association for Theoretical Computer Science, vol. 54 (1994), pp. 46–62.Google Scholar
[Sal94b]Salomaa, A., Return to patterns (The Formal Language Theory Column), The Bulletin for the European Association for Theoretical Computer Science, vol. 55 (1994), pp. 144–157.Google Scholar
[Sch98]Schaefer, M., A guided tour of minimal indices and shortest descriptions, Archive for Mathematical Logic, vol. 18 (1998), pp. 521–548.Google Scholar
[Sel84]Selivanov, V.L., On a hierarchy of limiting computations, Sibirskii Mathematicheskii Zhurnal, vol. 25 (1984), no. 5, pp. 146–156, In Russian (English translation in Siberian Mathematical Journal, vol. 25 (1984), pp. 798–806.Google Scholar
[Sha71]Shapiro, N., Review of “Limiting recursion” by E. M. Gold and “Trial and error predicates and the solution to a problem of Mostowski” by H. Putnam, this Journal, vol. 36 (1971), p. 342.Google Scholar
[SSV97]Sharma, A., Stephan, F., and Ventsov, Y., Generalized notions of mind change complexity, Proceedings of the Tenth Annual Conference on Computational Learning Theory, ACM Press, 1997, pp. 96–108.CrossRefGoogle Scholar
[SSS+94]Shimozono, S., Shinohara, A., Shinohara, T., Miyano, S., Kuhara, S., and Arikawa, S., Knowledge acquisition from amino acid sequences by machine learning system BONSAI, Transactions of the Information Processing Society of Japan, vol. 35 (1994), pp. 2009–2018.Google Scholar
[Shi83]Shinohara, T., Inferring unions of two pattern languages, Bulletin of Informatics and Cybernetics, vol. 20 (1983), pp. 83–88.Google Scholar
[SA95]Shinohara, T. and Arikawa, A., Pattern inference, Algorithmic learning for knowledge-based systems (Jantke, Klaus P. and Lange, Steffen, editors), Lecture Notes in Artificial Intelligence, vol. 961, Springer-Verlag, 1995, pp. 259–291.CrossRefGoogle Scholar
[Sie65]Sierpinski, W., Cardinal and ordinal numbers, second revised ed., PWN-Polish Scientific Publishers, 1965.Google Scholar
[Smu61]Smullyan, R., Theory of formal systems, Annals of Mathematics Studies, no. 47, Princeton University Press, 1961.CrossRefGoogle Scholar
[Soa96]Soare, R. I.. Computability and recursion, The Bulletin of Symbolic Logic, vol. 2 (1996), no. 3, pp. 284–321.Google Scholar
[Wri89]Wright, K., Identification of unions of languages drawn from an identifiable class, Proceedings of the Second Annual Workshop on Computational Learning Theory (Santa Cruz, California) (Rivest, R., Haussler, D., and Warmuth, M., editors), Morgan Kaufmann Publishers, Inc., 1989, pp. 328–333.Google Scholar