A Field Guide to Dynamical Recurrent Networks

Acquire the tools for understanding new architectures and algorithms of dynamical recurrent networks (DRNs) from this valuable field guide, which documents recent forays into artificial intelligence, control theory, and connectionism. This unbiased introduction to DRNs and their application to time-series problems (such as classification and prediction) provides a comprehensive overview of the recent explosion of leading research in this prolific field. A Field Guide to Dynamical Recurrent Networks emphasizes the issues driving the development of this class of network structures. It provides a solid foundation in DRN systems theory and practice using consistent notation and terminology. Theoretical presentations are supplemented with applications ranging from cognitive modeling to financial forecasting. A Field Guide to Dynamical Recurrent Networks will enable engineers, research scientists, academics, and graduate students to apply DRNs to various real-world problems and learn about different areas of active research. It provides both state-of-the-art information and a road map to the future of cutting-edge dynamical recurrent networks.

Table of Contents:
Preface xvii Acknowledgments xix List of Figures xxi List of Tables xxvii List of Contributors xxix PART I INTRODUCTION 1 Chapter 1 Dynamical Recurrent Networks 3 John F, Kolen and Stefan C. Kroner 1.1 Introduction 3 1.2 Dynamical Recurrent Networks 4 1.3 Overview 6 1.4 Conclusion 11 PART II ARCHITECTURES 13 Chapter 2 Networks with Adaptive State Transitions 15 David Calvert and Stefan C. Kremer 2.1 Introduction 15 2.2 The Search for Context 15 2.3 Recurrent Approaches to Context 17 2.4 Representing Context 18 2.5 Training 19 2.6 Architectures 19 2.7 Conclusion 25 Chapter 3 Delay Networks: Buffers to the Rescue 27 Tsung-Nan Lin and C. Lee Giles 3.1 Introduction to Delay Networks 27 3.2 Back-Propagation Through Time Learning Algorithm 28 3.3 Delay Networks with Feedback: NARX Networks 31 3.4 Long-Term Dependencies in NARX Networks 33 3.5 Experimental Results: The Latching Problem 36 3.6 Conclusion 38 Chapter 4 Memory Kernels 39 Ah Chung Tsoi, Andrew Back, Jose Principe, and Mike Mozer 4.1 Introduction 39 4.2 Different Types of Memory Kernels 40 4.3 Generic Representation of a Memory Kernel 44 4.4 Basis Issues 45 4.5 Universal Approximation Theorem 47 4.6 Training Algorithms 48 4.7 Illustrative Example 51 4.8 Conclusion 54 PART III CAPABILITIES 55 Chapter 5 Dynamical Systems and Iterated Function Systems 57 John F. Kolen 5.1 Introduction 57 5.2 Dynamical Systems 57 5.3 Iterated Function Systems 72 5.4 Symbolic Dynamics 78 5.5 The DRN Connection 80 5.6 Conclusion 81 Chapter 6 Representation of Discrete States 83 C. Lee Giles and Christian Omlin 6.1 Introduction 83 6.2 Finite-State Automata 83 6.3 Neural Network Representations of DFA 85 6.4 Pushdown Automata 99 6.5 Turing Machines 101 6.6 Conclusion 102 Chapter 7 Simple Stable Encodings of Finite-State Machines in Dynamic Recurrent Networks 103 Mikel L. Forcada and Raphael C. Carrasco 7.1 Introduction 103 7.2 Definitions 106 7.3 Encoding 109 7.4 Encoding of Mealy Machines in DRN 114 7.5 Encoding of Moore Machines in DRN 123 7.6 Encoding of Deterministic Finite-State Automata in DRN 125 7.7 Conclusion 126 7.8 Acknowledgments 127 Chapter 8 Representation Beyond Finite States: Alternatives to Pushdown Automata 129 Janet Wiles, Alan D. Blair, and Mikael Boden 8.1 Introduction 129 8.2 Hierarchies of Languages and Machines 130 8.3 DRNs and Nonregular Languages 134 8.4 Generalization and Inductive Bias 141 8.5 Conclusion 142 Chapter 9 Universal Computation and Super-Hiring Capabilities 143 Hava T. Siegelmann 9.1 Introduction 143 9.2 The Model 144 9.3 Preliminary: Computational Complexity 145 9.4 Summary of Results 146 9.5 Pondering Real Weights 149 9.6 Analog Computation 149 9.7 Conclusion 150 9.7 Acknowledgments 151 PART IV ALGORITHMS 153 Chapter 10 Insertion of Prior Knowledge 155 Paolo Frasconi, C. Lee Giles, Marco Gori, and Christian Omlin 10.1 Introduction 155 10.2 Constrained Nondeterministic Insertion in First-Order Networks 156 10.3 Second-Order Networks 160 10.4 Other Related Techniques 175 10.5 Conclusion 177 Chapter 11 Gradient Calculations for Dynamic Recurrent Neural Networks 179 Barak A. Pearlmutter 11.1 Introduction 179 11.2 Learning in Networks with Fixed Points 182 11.3 Computing the Gradient Without Assuming a Fixed Point 188 11.4 Some Simulations 196 11.5 Stability and Perturbation Experiments 198 11.6 Other Non-Fixed Point-Techniques 199 11.7 Learning with Scale Parameters 203 11.8 Conclusion 203 Chapter 12 Understanding and Explaining DRN Behavior 207 Christian Omlin 12.1 Introduction 207 12.2 Performance Deterioration 208 12.3 Dynamic Space Exploration 209 12.4 DFA Extraction: Fool's Gold? 215 12.5 Theoretical Foundations 216 12.6 How Can DFA Outperform Networks? 218 12.7 Alternative Extraction Methods 220 12.8 Extension to Fuzzy Automata 225 12.9 Application to Financial Forecasting 226 12.10 Conclusion 227 PART V LIMITATIONS 229 Chapter 13 Evaluating Benchmark Problems by Random Guessing 231 Jiirgen Schmidhuber, Sepp Hochreiter, and Yoshua Bengio 13.1 Introduction 231 13.2 Random Guessing (RG) 231 13.3 Experiments 232 13.4 Final Remarks 234 13.5 Conclusion 235 13.6 Acknowledgments 235 Chapter 14 Gradient Flow in Recurrent Nets: The Difficulty of Learning Long-Term Dependencies 237 Sepp Hochreiter, Yoshua Bengio, Paolo Frasconi, and Jiirgen Schmidhuber 14.1 Introduction 237 14.2 Exponential Error Decay 237 14.3 Dilemma: Avoiding Aradient Decay Prevents Long-Term Latching 240 14.4 Remedies 241 14.5 Conclusion 243 Chapter 15 Limiting the Computational Power of Recurrent Neural Networks: VC Dimension and Noise 245 Christopher Moore 15.1 Introduction 245 15.2 Time-Bounded Networks and VC Dimension 246 15.3 Robustness to Noise 250 15.4 Conclusion 254 15.5 Acknowledgments 254 PART VI APPLICATIONS 255 Chapter 16 Dynamical Recurrent Networks in Control 257 Danil V Prokhorov, Gintaras V Puskorius, and Lee A. Feldkamp 16.1 Introduction 257 16.2 Description and Execution of TLRNN 258 16.3 Elements of Training 260 16.4 Basic Approach to Controller Synthesis 266 16.5 Example 1 272 16.6 Example 2 282 16.7 Conclusion 288 Chapter 17 Sentence Processing and Linguistic Structure 291 Whitney Tabor 17.1 Introduction 291 17.2 Case Studies: Dynamical Networks for Sentence Processing 295 17.3 Conclusion 308 Chapter 18 Neural Network Architectures for the Modeling of Dynamic Systems 311 Hans-Georg Zimmermann and Ralph Neuneier 18.1 Introduction and Overview 311 18.2 Modeling Dynamic Systems by Feedforward Neural Networks 312 18.3 Modeling Dynamic Systems by Recurrent Neural Networks 321 18.4 Combining State-Space Reconstruction and Forecasting 334 18.5 Conclusion 350 Chapter 19 From Sequences to Data Structures: Theory and Applications 351 Paolo Frasconi, Marco Gori, Andreas Kuchler, and Alessandro Sperduti 19.1 Introduction 351 19.2 Historical Remarks 352 19.3 Adaptive Processing of Structured Information 354 19.4 Applications 366 19.5 Conclusion 374 PART VII CONCLUSION 375 Chapter 20 Dynamical Recurrent Networks: Looking Back and Looking Forward 377 Stefan C. Kremer and John F. Kolen 20.1 Introduction 377 20.2 The Challenges 377 20.3 The Potential 378 20.4 The Approaches 378 20.5 The Successes 378 20.6 Conclusion 378 Bibliography 379 Glossary 409 Index 415 About the Editors 423