Identification of Discrete Event Systems Using the Compound Recurrent Neural Network: Extracting DEVS from Trained Network

Abstract

The authors consider identifying an unknown discrete event system (DES) as recognition of characteristic functions of a discrete event systems specification (DEVS) model that validly represents the system. Such identification consists of two major steps: behavior learning using a specially designed neural network and extraction of a DEVS model from the learned neural network. This paper presents a method for extracting a DEVS model from one such neural network called CRNN (compound recurrent neural network), which is trained using observed input/output events of an unknown DES. The DES to be identified is restricted to a subclass of DES in which any unknown state can be determined by a finite number of input/output sequences. Identification experiments were performed with three types of unknown DESs, the result of which verified the validity of the proposed model extraction method.

Keywords

Discrete event system identification DEVS formalism neural network model extraction model minimization

Get full access to this article

View all access options for this article.

References

Eykhoff, P. 1981. Trends and progress in system identification. Oxford, UK: Pergamon.

Brandin, B. A. , and W. M. Wonham . 1994. Supervisory control of timed discrete-event systems. IEEE Transactions on Automatic Control 39 (2): 329-342.

Hae Sang Song. 2000. A DEVS framework for analysis and design of discrete event systems control. PhD diss., Department of Electrical Engineering, KAIST.

Cassandras, C. G. 1993. Discrete event systems. Homewood, IL: Irwin.

Zeigler, B. P. , H. Praehofer , and T. G. Kim . 2000. Theory of modeling and simulation. 2d ed. San Diego: Academic Press.

Angluin, D. , and C. H. Smith . 1983. Inductive inference: Theory and methods. ACM Computing Surveys 15 (3): 237-269.

Giles, C. L. , C. B. Miller , D. Chen , H. H. Chen , G. Z. Sun , and Y. C. Lee . 1992. Learning and extracting finite state automata with second-order recurrent neural network. Neural Computation 4:393-405.

Watrous, R. , and G. Kuhn . 1992. Induction of finite-state languages using second-order networks. Neural Computation 4 (3): 406.

Ngom, L. , C. Baron , and J. C. Geffroy . 2000. Improved functional identification using genetic simulation. Transactions of the Society for Computer Simulation International 17 (1): 12-27.

10.

Giles, C. L. , and C. W. Omlin . 1993. Extraction, insertion and refinement of symbolic rules in dynamical-driven recurrent neural networks. Connection Science 5 (3/4): 307-337.

11.

Narendra, K. S. , and K. Parthasarathy . 1990. Identification and control of dynamical systems using neural networks. IEEE Transactions on Neural Networks 1 (1): 4.

12.

Siegelmann, H. T. , B. G. Horne , and C. L. Giles . 1997. Computational capabilities of recurrent NARX neural networks. IEEE Transactions on Systems, Man and Cybernetics, Part B: Cybernetics 27 (2): 208-215.

13.

Connor, J. , R. Martin , and L. Atlas . 1994. Recurrent neural networks and robust time series prediction. IEEE Transactions on Neural Networks 5 (2): 240-254.

14.

Caileanu, C. , and J. L. Boimond . 2000. Considerations on discrete event dynamic system identification. Proceedings of the SCI 2000 Systemics, Cybernetics and Informatics Multiconference, July, Orlando, FL, pp. 324-329.

15.

Baccelli, F. L. , G. Cohen , G. J. Olsder , and J. P. Quadrat . 1992. Synchronization and linearity. New York: John Wiley.

16.

Zeigler, B. P. 1984. Multifaceted modeling and discrete event simulation. San Diego: Academic Press.

17.

Giles, C. L. , B. G. Horne , and T. Lin . 1995. Learning a class of large finite machines with a recurrent neural network. Neural Networks 8 (9): 1359-1365.

18.

Hopcroft, J. E. , and J. D. Ullman . 1979. Introduction to automata theory, languages and computation. Reading, MA: Addison-Wesley.

19.

Tomita, M. 1982. Dynamic construction of finite state automata from examples using hill climbing. Proceedings of the Fourth Annual Cognitive Science Conference, pp. 105-108.

20.

Kohavi, Z. 1978. Switching and finite automata theory. 2d ed. New York: McGraw-Hill.

21.

Haykin, S. 1994. Neural networks. New York: Macmillan.

22.

Werbos, P. J. 1990. Backpropagation through time: What it does and how to do it. Proceeding of the IEEE 78 (10): 1550-1560.

23.

Miller, C. B. , and C. L. Giles . 1993. Experimental comparison of the effect of order in RNNs. International Journal of Pattern Recognition and Artificial Intelligence 7 (4): 849-723.