A Field Guide to Dynamical Recurrent Networks

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