Abstract
We consider the problem of a learning mechanism (robot, or algorithm) that learns a parameter while interacting with either a stochastic teacher or a stochastic compulsive liar. The problem is modeled as follows: the learning mechanism is trying to locate an unknown point on a real interval by interacting with a stochastic environment through a series of guesses. For each guess the environment (teacher) essentially informs the mechanism, possibly erroneously, which way it should move to reach the point. Thus, there is a non-zero probability that the feedback from the environment is erroneous. When the probability of correct response is p>0.5, the environment is said to be Informative, and we have the case of learning from a stochastic teacher. When this probability is p<0.5 the environment is deemed Deceptive, and is called a stochastic compulsive liar.
This paper describes a novel learning strategy by which the unknown parameter can be learned in both environments. To the best of our knowledge, our results are the first reported results which are applicable to the latter scenario. Another main contribution of this paper is that the proposed scheme is shown to operate equally well even when the learning mechanism is unaware whether the environment is Informative or Deceptive. The learning strategy proposed herein, called CPL–ATS, partitions the search interval into three equi-sized sub-intervals, evaluates the location of the unknown point with respect to these sub-intervals using fast-converging ε-optimal L RI learning automata, and prunes the search space in each iteration by eliminating at least one partition. The CPL-ATS algorithm is shown to be provably converging to the unknown point to an arbitrary degree of accuracy with probability as close to unity as desired. Comprehensive experimental results confirm the fast and accurate convergence of the search for a wide range of values for the environment’s feedback accuracy parameter p. The above algorithm can be used to learn parameters for non-linear optimization techniques.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching with uncertainty. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol. 318, pp. 176–189. Springer, Heidelberg (1988)
Baeza-Yates, R.A., Schott, R.: Parallel Searching in the Plane. In: Proc. 1992 International Conference of the Chilean Computer Society, IC-SCCC 1992, pp. 269–279 (1992)
Bentley, J.L., Yao, A.C.-C.: An Almost Optimal Algorithm for Unbounded Searching. Information Processing Letters, 82–87 (August 1976)
Karlin, S., Taylor, H.M.: A First Course on Stochastic Processes, 2nd edn. Academic Press, London (1974)
Kashyap, R.L., Oommen, B.J.: Scale Preserving Smoothing of Polygons. IEEE Trans. on Pat. Anal. and Mach. Intel., 667–671 (November 1983)
Lakshmivarahan, S.: Learning Algorithms Theory and Applications. Springer, Heidelberg (1981)
Lancôt, J.K., Oommen, B.J.: Discretized Estimator Learning Automata. IEEE Trans. on Syst. Man and Cybern. SMC-22, 1473–1483 (1992)
Narendra, K.S., Thathachar, M.A.L.: Learning Automata. Prentice-Hall, Englewood Cliffs (1989)
Oommen, B.J.: Stochastic Searching on the Line and its Applications to Parameter Learning in Nonlinear Optimization. IEEE Transactions on Systems, Man and Cybernetics SMC-27, 733–739 (1997)
Oommen, B.J., Raghunath, G.: Automata Learning and Intelligent Tertiary Searching for Stochastic Point Location. IEEE Transactions on Systems, Man and Cybernetics SMC-28B, 947–954 (1998)
Pao, Y.-H.: Adaptive Pattern Recognition and Neural Networks. Addison Wesley, Reading (1989)
Pavlidis, T.: Structural Pattern Recognition. Springer, New York (1977)
Pelc, A.: Searching with Known Error Probability. Theoretical Computer Science 63, 185–202
Press, W.H., Flannery, B.P., Teukolsky, S.A., Vetterling, W.T.: Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, Cambridge (1986)
Oommen, B.J., Raghunath, G., Kuipers, B.: Parameter Learning from Stochastic Teachers and Stochastic Compulsive Liars. Technical Report in preparation, School of Computer Science, Carleton University, Ottawa. The report can be obtained by contacting the first author
Rao, S.S.: Optimization: Theory and Applications, 2nd edn. John Wiley, New Delhi (1984)
Rich, E., Knight, K.: Artificial Intelligence. McGraw Hill Inc., New York (1991)
Tsetlin, M.L.: Automaton Theory and the Modelling of Biological Systems. Academic, New York (1973)
Wasserman, P.D.: Neural Computing: Theory and Practice. Van Nostrand Reinhold, New York (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Oommen, B.J., Raghunath, G., Kuipers, B. (2003). On How to Learn from a Stochastic Teacher or a Stochastic Compulsive Liar of Unknown Identity. In: Gedeon, T.(.D., Fung, L.C.C. (eds) AI 2003: Advances in Artificial Intelligence. AI 2003. Lecture Notes in Computer Science(), vol 2903. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24581-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-24581-0_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20646-0
Online ISBN: 978-3-540-24581-0
eBook Packages: Springer Book Archive