Learning Behaviors of Functions

• 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 properties of these functions are learnable if we allow fewer number of mind changes or errors? In order to answer this question this paper extends the Inductive Inference model introduced by Gold [15]. Another motivation for this extension is to understand and characterize properties that are learnable for a given set of functions. Our extension considers a wide range of properties of function based on their input-output relationship. Two specific properties of functions are studied in this paper. The first property, which we call modality, explores how the output of a function fluctuates. For example, consider a function that predicts the price of a stock. A brokerage company buys and sells stocks very often in a day for its clients with the intent of maximizing their profit. If the company is able predict the trend of the stock market "reasonably" accurately then it is bound to be very successful. Identification criterion for this property of a function f is called PREX which predicts if f(x) is equal to, less than or greater than f(x + 1) for each x. Next, as opposed to a constant tracking by a brokerage company, an individual investor does not often track dynamic changes in stock values. Instead, the investor would like to move the investment to a less risky option when the investment exceeds or falls below certain threshold. We capture this notion using an identification criterion called TREX that essentially predicts if a function value is at, above, or below a threshold value. Conceptually,modality prediction (i.e., PREX) and threshold prediction (i.e., TREX) are "easier" than EX learning. We show that neither the number of errors nor the number of mind-changes can be reduced when we ease the learning criterion from exact learning to learning modality or threshold. We also prove that PREX and TREX are totally different properties to predict. That is, the strategy for a brokerage company may not be a good strategy for individual investor and vice versa.

Słowa kluczowe

EN

inductive inference; properties of functions; mind changes; errors; learning

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 98, nr 2/3
• Strony: 183--198
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Kalyanasundaram B.

autor

Velauthapillai M.

• Department of Computer Science, 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] Machtey,M., Young, P.: An Introduction to General Theory of Algorithms, North-Holland, 1978, New York.
• [21] Pitt, L.: Probabilistic inductive inference, J. ACM 36(2), 1989, 383-433.
• [22] Pitt, L., Smith, C.: Probability and plurality for aggregations of learning machines, Information and Computation 77(1), 1988, 77-92.
• [23] Smith, C. H.: The Power of Pluralism for Automatic Program Synthesis, Journal of the Association for Computing Machinery, vol 29, 1982, pp. 1144-1165.
• [24] Valiant, L. G.: A theory of Learnable, Communications of the ACM, vol 27, 1987, pp.1134-1142.
• [25] Wiehagen, R., Freivalds, R., V., Kinber, E.: On the power of probabilistic strategies in inductive inference, Theoretical Computer Science, 1984, 111-113.