Capabilities of Thoughtful Machines

• Autorzy: Kalyanasundaram B. , Velauthapillai M.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

inductive inference; mind changes; error; thoughtful machines

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 2,3
• Strony: 329--340
• Opis fizyczny: bibliogr. 26 poz.

Twórcy

autor

Kalyanasundaram B.

autor

Velauthapillai M.

• Computer Science Dept. Georgetown University, Washington, D.C., USA,

Bibliografia

• [1] Angluin, D., Smith, C. H.: Inductive inference: Theory and Methods, Computing Surveys, 15, 237-269, 1983.
• [2] Angluin, D., Smith, C. H.: Inductive inference, Encyclopedia of Artificial Intelligence, (ed: S. Shapiro), pp.409-418,Wiley, New York, 1987.
• [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] Barzdin, J. A., Freivalds, R. V.: On the prediction of general recursive functions, Soviet Math. Dokl., 13, 1224-1228, 1972.
• [5] Blum, L., Blum, M.: Toward a mathematical theory of inductive inference, Information and Control, 28, 125-155, 1975.
• [6] Case J., Smith, C. H.: Comparison of identification criteria for machine inductive inference, Theoretical Computer Science, 25, 193-220, 1983.
• [7] Daley, R., Kalyanasundaram, B.: Capabilities of Probabilistic Learners with Bounded Mind Changes, Proceedings of the 1993Workshop on Computational Learning Theory, 182-191, 1993.
• [8] Daley, R., Kalyanasundaram, B.: Use of reduction arguments in determining Popperian FINite learning capabilities, Proceedings of Algorithmic Learning Theory, 173-186, 1993.
• [9] Daley, R., Kalyanasundaram, B.: Probabilistic and Pluralistic Learners with Mind Changes, Proceedings of Mathematical Foundations of Computer Science, 218-226, 1992.
• [10] Daley, R., Kalyanasundaram, B., Velauthapillai, M.: Breaking the probability 1/2 barrier in FIN-type learning, Proceedings of the 1992Workshop on Computational Learning Theory, 203-217, 1992.
• [11] Daley, R., Pitt, N., Velauthapillai, M, Will, T.: Relations between probabilistic and team one-shot learners, Proceedings of the 1991Workshop on Computational Learning Theory, 228-239, 1991.
• [12] Daley, R., Smith, C. H.: On the complexity of inductive inference, Information and Control, 69, 12-40, 1986.
• [13] Freivalds, R. V.: Finite Identification of General Recursive Functions by Probabilistic Strategies, Akademie Verlag, Berlin, 1979.
• [14] Freivalds, R. V., Smith, C. H., Velauthapillai,M.: Trade-off among Parameters Affecting Inductive Inference, Information and Computation, 82, 323-349, 1989.
• [15] Gasarch,W., Pleszkoch,M., Solovay, R.: Learning via Queries to [+,¡], Journal of Symbolic Logic, Vol. 57, 53-81, 1992.
• [16] Gasarch, W., Smith, C. H.: Learning via Queries, Journal of the Association of Computing Machinery, Vol. 39, pp. 649-675, 1992.
• [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] Gold, E. M.: Learning Identification in the Limit, Information and Control, vol 10, 447-474, 1967.
• [19] Jantke, K. P., Beick, H. R.: Combining postulates of naturalness in inductive inference, Electron. Inform. Kebernet. 17,465-484, 1981.
• [20] Jain, S., Sharma, A.: Finite learning by a team, Proceedings of the 1990 Workshop on Computational Learning Theory, 163-177, 1990.
• [21] Machtey,M., Young, P.: An Introduction to General Theory of Algorithms, North-Holland, New York. 1978.
• [22] Pitt, L.: Probabilistic inductive inference, Journal of ACM 36(2), 383-433, 1989.
• [23] Pitt, L., Smith, C. H,: Probability and plurality for aggregations of learning machines, Information and Computation 77(1), 77-92, 1988.
• [24] Smith, C. H.: The Power of Pluralism for Automatic Program Synthesis, Journal of the Association for Computing Machinery, vol 29, 1144-1165, 1982.
• [25] Valiant, L. G.: A theory of Learnable, Communications of the ACM, vol 27, 1134-1142, 1987.
• [26] Wiehagen, R., Freivalds, R. V., Kinber, E.: On the power of probabilistic strategies in inductive inference, Theoretical Computer Science, 111-113, 1984.