Abstract
Process control problems can be modeled as closed recursive games. Learning strategies for such games is equivalent to the concept of learning infinite recursive branches for recursive trees. We use this branch learning model to measure the difficulty of learning and synthesizing process controllers. We also measure the difference between several process learning criteria, and their difference to controller synthesis. As measure we use the information content (i.e. the Turing degree) of the oracle which a machine need to get the desired power.
The investigated learning criteria are finite, EX-, BC-, Weak BC- and online learning. Finite, EX- and BC-style learning are well known from inductive inference, while weak BC- and online learning came up with the new notion of branch (i.e. process) learning. For all considered criteria — including synthesis — we also solve the questions of their trivial degrees, their omniscient degrees and with some restrictions their inference degrees. While most of the results about finite, EX- and BC-style branch learning can be derived from inductive inference, new techniques had to be developed for online learning, weak BC-style learning and synthesis, and for the comparisons of all process learning criteria with the power of controller synthesis.
Supported by the Deutsche Forschungsgemeinschaft (DFG) Graduiertenkolleg “Beherrschbarkeit komplexer Systeme” (GRK 209/2-96).
Supported by the Deutsche Forschungsgemeinschaft (DFG) grant Am 60/9-1.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Adleman and M. Blum. Inductive inference and unsolvability. Journal of Symbolic Logic, 56(3):891–900, 1991.
O. Arnold and K. P. Jantke. Therapy plan generation as program synthesis. In Proc. 5th Int. Workshop on Algorithmic Learning Theory, pages 40–55. Springer-Verlag, 1994.
L. Blum and M. Blum. Towards a mathematical theory of inductive inference. Information and Control, 28:125–155, 1975.
J. R. Büchi and L. H. Landweber. Solving sequential conditions by finite-state strategies. Transactions of the American Mathematical Society, 138:295–311, 1969.
J. Case, S. Kaufmann, E. Kinber, and M. Kummer. Learning recursive functions from approximations. In EuroCOLT'95, volume 904 of LNCS, pages 140–153. Springer-Verlag, 1995.
D. Cenzer and J. Remmel. Recursively presented games and strategies. Mathematical Social Sciences, 24:117–139, 1992.
O. Föllinger. Regelungstechnik. Hüthig, Heidelberg, 8th edition, 1994.
L. Fortnow, W. Gasarch, S. Jain, E. Kinber, M. Kummer, S. Kurtz, M. Pleszkoch, T. Slaman, R. Solovay, and F. Stephan. Extremes in the degrees of inferability. Annals of Pure and Applied Logic, 66:21–276, 1994.
E. M. Gold. Language identification in the limit. Information and Control, 10:447–474, 1967.
S. Kaufmann and M. Kummer. On a quantitative notion of uniformity. In Mathematical Foundations of Computer Science, volume 969 of LNCS, pages 169–178. Springer-Verlag, 1995.
M. Kummer and M. Ott. Effective strategies for enumeration games. In H. K. Büning, editor, Proceedings of Computer Science Logic CSL '95, pages 368–387, Berlin, 1996. Springer.
M. Kummer and M. Ott. Learning branches and learning to win closed games. In Proceedings of Ninth Annual Conference on Computational Learning Theory, pages 280–291, New York, 1996. ACM.
M. Kummer and F. Stephan. On the structure of degrees of inferability. Journal of Computer and System Sciences, 52(2):214–238, Apr. 1996.
A. H. Lachlan. On some games which are relevant to the theory of recursively enumerable sets. Annals of Mathematics, 91(2):291–310, 1970.
D. Luzeaux. Machine learning applied to the control of complex systems. In 8th International Conference on Artificial Intelligence and expert systems applications, Paris, France, 1996.
D. Luzeaux and E. Martin. Steps or stages for incremental control? In Symposium on training issues in incremental learning, Stanford University, CA, USA, 1993. AAAI-93 Spring Symposium Series.
O. Maler, A. Pnueli, and J. Sifakis. On the synthesis of discrete controllers for timed systems. In STACS 95, volume 900 of LNCS, pages 229–242. Springer-Verlag, 1995.
E. Martin. Oracles for learning programs. In IEEE International Conference on Systems Man Cybernetics, Le Touquet, France, 1993.
E. Martin, D. Luzeaux, and B. Zavidovique. Learning and control from a recursive viewpoint. In IEEE International Symposium on Intelligent Control, Glasgow, Ecosse, 1992.
R. McNaughton. Infinite games played on finite graphs. Annals of Pure and Applied Logic, 65:149–184, 1993.
W. T. Miller, R. S. Sutton, and P. J. Werbos, editors. Neural networks for control. MIT Press, Cambridge, Massachusetts, 1990.
K. S. Narendra and S. Mukhopadhyay. Intelligent control using neural networks. IEEE Control Systems Magazine, 12(5):11–18, April 1992.
P. Odifreddi. Classical Recursion Theory. North-Holland, Amsterdam, 1989.
D. Osherson, M. Stob, and S. Weinstein. Systems that Learn. MIT Press, Cambridge, Massachusetts, 1986.
M. Ott and F. Stephan. Structural measures for games and process control in the branch learning model. Technical report 39/96, Fakultät für Informatik, Universität Karsruhe, 1996.
M. Riedmiller. Learning to control dynamic systems. In R. Trappl, editor, Proceedings of the 13th. European Meeting on Cybernetics and Systems Research — 1996 (EMCSR '96), Vienna, 1996.
J. G. Thistle and W. M. Wonham. Control of infinite behavior of finite automata. SIAM Journal on Control and Optimization, 32(4):1075–1097, 1994.
W. Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, pages 133–191. Elsevier Science Publishers B. V., 1990.
W. Thomas. On the synthesis of strategies in infinite games. In STACS 95, volume 900 of LNCS, pages 1–13. Springer-Verlag, 1995.
W. Thomas and H. Lescow. Logical specification of infinite computations. In J. W. de Bakker, W.-P. de Roever, and G. Rozenberg, editors, A Decade of Concurrency: Reflections and Perspectives, volume 803 of LNCS, pages 583–621. Springer-Verlag, 1993.
D. A. White and D. A. Sofge, editors. Handbook of Intelligent Control. Van Nostrand Reinhold, New York, 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ott, M., Stephan, F. (1997). Structural measures for games and process control in the branch learning model. In: Ben-David, S. (eds) Computational Learning Theory. EuroCOLT 1997. Lecture Notes in Computer Science, vol 1208. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62685-9_9
Download citation
DOI: https://doi.org/10.1007/3-540-62685-9_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62685-5
Online ISBN: 978-3-540-68431-2
eBook Packages: Springer Book Archive