article

Capabilities of Thoughtful Machines

Authors:

Bala Kalyanasundaram,

Mahe VelauthapillaiAuthors Info & Claims

Fundamenta Informaticae, Volume 74, Issue 2,3

Pages 329 - 340

Published: 01 November 2006 Publication History

Abstract

When learning a concept the learner produces conjectures about the concept he learns. Typically the learner contemplates, performs some experiments, make observations, does some computation, thinks carefully (that is not output a new conjecture for a while) and then makes a conjecture about the (unknown) concept. Any new conjecture of an intelligent learner should be valid for at least some "reasonable amount of time" before some evidence is found that the conjecture is false. Then maybe the learner can further study and explore the concept more and produce a new conjecture that again will be valid for some "reasonable amount of time". In this paper we formalize the idea of reasonable amount of time. The learners who obey the above constraint are called "Thoughtful learners" (TEX learners). We show that there are classes that can be learned using the above model. We also compare this leaning paradigm to other existing ones. The surprising result is that there is no capability intervals in team TEX-type learning. On the other hand, capability intervals exist in all other models. Also these learners are orthogonal to the learners that have been studied in the literature.

References

[1]

[1] Angluin, D., Smith, C. H.: Inductive inference: Theory and Methods, Computing Surveys, 15, 237-269, 1983.

Digital Library

[2]

[2] Angluin, D., Smith, C. H.: Inductive inference, Encyclopedia of Artificial Intelligence, (ed: S. Shapiro), pp. 409-418, Wiley, New York, 1987.

[3]

[3] Barzdin, J. A.: Two theorems on the limiting synthesis of functions, Theory of Algorithms and Programs (Barzdin, Ed.), Vol. 1, 82-88, Latvian State University, Riga, USSR, 1974.

[4]

[4] Barzdin, J. A., Freivalds, R. V.: On the prediction of general recursive functions, Soviet Math. Dokl., 13, 1224-1228, 1972.

[5]

[5] Blum, L., Blum, M.: Toward a mathematical theory of inductive inference, Information and Control, 28, 125-155, 1975.

[6]

[6] Case J., Smith, C. H.: Comparison of identification criteria for machine inductive inference, Theoretical Computer Science, 25, 193-220, 1983.

[7]

[7] Daley, R., Kalyanasundaram, B.: Capabilities of Probabilistic Learners with Bounded Mind Changes, Proceedings of the 1993 Workshop on Computational Learning Theory, 182-191, 1993.

Digital Library

[8]

[8] Daley, R., Kalyanasundaram, B.: Use of reduction arguments in determining Popperian FINite learning capabilities, Proceedings of Algorithmic Learning Theory, 173-186, 1993.

[9]

[9] Daley, R., Kalyanasundaram, B.: Probabilistic and Pluralistic Learners with Mind Changes, Proceedings of Mathematical Foundations of Computer Science, 218-226, 1992.

Digital Library

[10]

[10] Daley, R., Kalyanasundaram, B., Velauthapillai, M.: Breaking the probability 1/2 barrier in FIN-type learning, Proceedings of the 1992 Workshop on Computational Learning Theory, 203-217, 1992.

[11]

[11] Daley, R., Pitt, N., Velauthapillai, M, Will, T.: Relations between probabilistic and team one-shot learners, Proceedings of the 1991 Workshop on Computational Learning Theory, 228-239, 1991.

[12]

[12] Daley, R., Smith, C. H.: On the complexity of inductive inference, Information and Control, 69, 12-40, 1986.

Digital Library

[13]

[13] Freivalds, R. V.: Finite Identification of General Recursive Functions by Probabilistic Strategies, Akademie Verlag, Berlin, 1979.

[14]

[14] Freivalds, R. V., Smith, C. H., Velauthapillai, M.: Trade-off among Parameters Affecting Inductive Inference, Information and Computation, 82, 323-349, 1989.

Digital Library

[15]

[15] Gasarch, W., Pleszkoch, M., Solovay, R.: Learning via Queries to [+,], Journal of Symbolic Logic, Vol. 57, 53-81, 1992.

[16]

[16] Gasarch, W., Smith, C. H.: Learning via Queries, Journal of the Association of Computing Machinery, Vol. 39, pp. 649-675, 1992.

Digital Library

[17]

[17] Gasarch, W., Velauthapillai, M.: Asking Questions Versus Verifiability, International Workshop on Analogical and Inductive Inference, Dagstuhl Castle, Germany, (Lecture notes in Artificial Intelligence vol. 642, 197-213), 1992.

[18]

[18] Gold, E. M.: Learning Identification in the Limit, Information and Control, vol 10, 447-474, 1967.

[19]

[19] Jantke, K. P., Beick, H. R.: Combining postulates of naturalness in inductive inference, Electron. Inform. Kebernet. 17, 465-484, 1981.

[20]

[20] Jain, S., Sharma, A.: Finite learning by a team, Proceedings of the 1990 Workshop on Computational Learning Theory, 163-177, 1990.

Digital Library

[21]

[21] Machtey, M., Young, P.: An Introduction to General Theory of Algorithms, North-Holland, New York. 1978.

[22]

[22] Pitt, L.: Probabilistic inductive inference, Journal of ACM 36(2), 383-433, 1989.

Digital Library

[23]

[23] Pitt, L., Smith, C. H,: Probability and plurality for aggregations of learning machines, Information and Computation 77(1), 77-92, 1988.

Digital Library

[24]

[24] Smith, C. H.: The Power of Pluralism for Automatic Program Synthesis, Journal of the Association for Computing Machinery, vol 29, 1144-1165, 1982.

Digital Library

[25]

[25] Valiant, L. G.: A theory of Learnable, Communications of the ACM, vol 27, 1134-1142, 1987.

Digital Library

[26]

[26] Wiehagen, R., Freivalds, R. V., Kinber, E.: On the power of probabilistic strategies in inductive inference, Theoretical Computer Science, 111-113, 1984.

Cited By

Kalyanasundaram BVelauthapillai M(2019)Learning Behaviors of Functions with TeamsFundamenta Informaticae10.5555/2594908.2594909124:3(251-270)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2594908.2594909
Kalyanasundaram BVelauthapillai M(2019)Learning Behaviors of FunctionsFundamenta Informaticae10.5555/1803682.180368598:2-3(183-198)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/1803682.1803685

Capabilities of Thoughtful Machines
1. Computing methodologies

Recommendations

Capabilities of Thoughtful Machines

When learning a concept the learner produces conjectures about the concept he learns. Typically the learner contemplates, performs some experiments, make observations, does some computation, thinks carefully (that is not output a new conjecture for a ...
Learning Behaviors of Functions with Teams

We consider the inductive inference model of Gold [15]. Suppose we are given a set of functions that are learnable with certain number of mind changes and errors. What can we consistently predict about those functions if we are allowed fewer mind ...
Learning Behaviors of Functions

We consider the inductive inference model of Gold [15]. Suppose we are given a set of functions that are learnable with certain number of mind changes and errors. What properties of these functions are learnable if we allow fewer number of mind changes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Fundamenta Informaticae

Fundamenta Informaticae Volume 74, Issue 2,3

November 2006

220 pages

ISSN:0169-2968

Issue’s Table of Contents

Publisher

IOS Press

Netherlands

Publication History

Published: 01 November 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
2
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kalyanasundaram BVelauthapillai M(2019)Learning Behaviors of Functions with TeamsFundamenta Informaticae10.5555/2594908.2594909124:3(251-270)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2594908.2594909
Kalyanasundaram BVelauthapillai M(2019)Learning Behaviors of FunctionsFundamenta Informaticae10.5555/1803682.180368598:2-3(183-198)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/1803682.1803685

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents