Learning Behaviors of Functions with Teams

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

Abstrakty

EN

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 changes or errors? In [20] we relaxed the notion of exact learning by considering some higher level properties of the input-output behavior of a given function. in this context, a learner produces a program that describes the property of a given function. Can we predict generic properties such as threshold or modality if we allow fewer number of mind changes or errors? These questions were completely answered in [20] when the learner is restricted to a single IIM. In this paper we allow a team of IIMs to collaborate in the learning process. The learning is considered to be successful if any one of the team member succeeds. A motivation for this extension is to understand and characterize properties that are learnable for a given set of functions in a team environment.

Słowa kluczowe

EN

errors; Inductive Inference; learning; mind changes; properties of functions; teams

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 124, nr 3
• Strony: 251--270
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Kalyanasundaram B.

• Computer Science Department, Georgetown University, Washington DC, USA

autor

Velauthapillai M.

• Computer Science Department, Georgetown University, Washington DC, USA

Bibliografia

• [1] Angluin, D., Smith, C.H.: Inductive inference: Theory and Methods, Computing Surveys, 1983,15, 237-269.
• [2] Angluin, D., Smith, C.H.: Inductive inference, in Encyclopedia of Artificial Intelligence (S. Shapiro), 1987, pp. 409-418, Wiley, New York.
• [3] Barzdin, J.A.: Two theorems on the limiting synthesis of functions, in Theory of Algorithms and Programs (Barzdin, Ed.), 1974, Vol. 1, 82-88, Latvian State University, Riga, USSR.
• [4] Barzdin, J.A., Freivalds, R.V.: On the prediction of general recursive functions, Soviet Math. Dokl., 1972, 13, 1224-1228.
• [5] Blum, L., and Blum, M,: Toward a mathematical theory of inductive inference, Information and Control, 1975, 28, 125-155.
• [6] Case J., and Smith, C.H.: Comparison of identification criteria for machine inductive inference, Theoretical Computer Science, 1983, 25, 193-220.
• [7] Daley, R., Kalyanasundaram, B.: Capabilities of Probabilistic Learners with Bounded Mind Changes, Proceedings of the 1993 Workshop on Computational Learning Theory, 1993, 182-191.
• [8] Daley, R., Kalyanasundaram, B.: Use of reduction arguments in determining Popperian FINite learning capabilities, Proceedings of Algorithmic Learning Theory, 1993, 173-186.
• [9] Daley, R., Kalyanasundaram, B.: Probabilistic and Pluralistic Learners with Mind Changes, Proceedings of Mathematical Foundations of Computer Science, 1992, 218-226.
• [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, 1992, 203-217.
• [11] Daley, R, Pitt, L., Velauthapillai, M., Will, T.: Relations between probabilistic and team one-shot learners, Proceedings of the 1991 Workshop on Computational Learning Theory, 1991, 228-239.
• [12] Daley, R.P., Smith, C.H.: On the complexity of inductive inference, Information and Control, 1986, 69, 12-40.
• [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 (1989), 82, 323-349.
• [15] Gold, E. M.: Learning Identification in the Limit, Information and Control, vol 10, 1967, pp. 447-474.
• [16] Jantke, K. P., Beick, H. R.: Combining postulates of naturalness in inductive inference, Electron. Inform. Kebernet. 1981, 17,465-484.
• [17] Jain, S., Sharma, A.: Finite learning by a team, Proceedings of the 1990 Workshop on Computational Learning Theory, 1990, 163-177.
• [18] Kalyanasundaram B., Velauthapillai, M.: Taming Teams with Mind Changes, Journal of Computer and System Sciences, June 2008, Vol 74(4), pp. 512-526.
• [19] Kalyanasundaram, B., Velauthapillai, M.: Capabilities of Thoughtful Machines, Fundamenta Informaticae, 74(2-3): 329-340 (2006).
• [20] Kalyanasundaram, B., Velauthapillai, M.: Learning Behaviours of Functions, Fundamenta Informaticae, 98(2-3): 183-198 (2010).
• [21] Machtey, M., Young, P.: An Introduction to General Theory of Algorithms, North-Holland, 1978, New York.
• [22] Pitt, L.: Probabilistic inductive inference, J. ACM 36(2), 1989, 383-433.
• [23] Pitt, L., Smith, C.: Probability and plurality for aggregations of learning machines, Information and Computation 77(1), 1988, 77-92.
• [24] Smith, C. H.: The Power of Pluralism for Automatic Program Synthesis, Journal of the Association for Computing Machinery, vol 29, 1982, pp. 1144-1165.
• [25] Valiant, L. G.: A theory of Learnable, Communications of the ACM, vol 27, 1987, pp.1134-1142.
• [26] Wiehagen, R., Freivalds, R., V., Kinber, E.: On the power of probabilistic strategies in inductive inference, Theoretical Computer Science, 1984, 111-113.