Macmillan Computer Science Series Consulting Editor: Professor F.H. Sumner, University of Manchester A. Abdellatif. J. Le Bihan and M. Limame, Oracle - A user's guide S.T. Allworth and R.N. Zobel, Introduction to Real-time Software Design, second edition Ian O. Angell, High-resolution Computer Graphics Using C Ian O. Angell and Oareth Oriffith, High-resolution Computer Graphics Using FORTRAN 77 Ian O. Angell and Oareth Griffith, High-resolution Computer Graphics Using Pascal M. Azmoodeh, Abstract Data Types and Algorithms, second edition C. Bamford and P. Curran, Data Structures. Files and Databases Philip Barker, Author Languages for CAL A.N. Barrett and A.L. Mackay, Spatial Structure and the Microcomputer R.E. Berry, B.A.E. Meekings and M.D. Soren, A Book on C. second edition P. Beynon-Davies, Information Systems Development O.M. Birtwistle, Discrete Event Modelling on Simula B.O. Blundell and C.N. Daskalakis, Using and Administering an Apollo Network B.O. Blundell, C.N. Daskalakis, N.A.E. Heyes and T.P. Hopkins, An Introductory Guide to Silvar Lisco and HILO Simulators T.B. Boffey, Graph Theory in Operations Research Richard Bomat, Understanding and Writing Compilers Linda E.M. Brackenbury, Design ofVLSI Systems - A Practical Introduction Alan Bradley, Peripherals for Computer Systems O.R. Brookes and A.J. Stewart, Introduction to occam 2 on the Transputer J.K. Buckle, Software Configuration Management W.D. Burnham and A.R. Hall, Prolog Programming and Applications P.e. Capon and P.J. Jinks, Compiler Ellgineering Using Pascal J.C. Cluley, Interfacing to Microprocessors J.C. Cluley, Introduction to Low Level Programming for Microprocessors Robert Cole, Computer Communications. second edition Derek Coleman, A Structured Programming Approach to Data E. Davalo and P. NaIrn, Neural Networks S.M. Deen, Fundamentals of Data Base Systems S.M. Deen, Principles and Practice of Database Systems C. Delannoy, Turbo Pascal Programming Tim Denvir, Introduction to Discrete Mathematics for Software Engineering D. England et al., A Sun User's Guide A.B. Fontaine and F. Barrand, 80286 and 80386 Microprocessors J.B. Oosling, Design of Arithmetic Units for Digital Computers M.G. Hartley, M. Healey and P.O. Depledge, Mini and Microcomputer Systems J.A. Hewitt and RJ. Frank, Software Engineering in Modula-2 - An Object-oriented Approach Roger Hutty, COBOL 85 Programming Roger Hutty, Z80 Assembly Lallguage Programming for Students Roland N. Ibbett and Nigel P. Topham, Architecture of High Performance Computers, Volume I Roland N. Ibbett and Nigel P. Topham, Architecture of High Performance Computers, Volume II Patrick Jaulent, The 68000 - Hardware and Software P. Jaulent, L. Batide and P. Pillot, 68020-30 Microprocessors alld their Coprocessors MJ. King and J.P. Pardoe, Program Design Using JSP - A Practical Introduction E.V. Krishnamurthy, Introductory Theory ofC omputer Science V.P. Lane, Security of Computer Based Illformatioll Systemr (continued overleaf) A.M. Lister and R.D. Eager, Fundamentals ofO perating Systems,fourth edition Elizabeth Lynch, Understanding SQL Tom Manns and Michael Coleman, Software Quality Assurance A. M6vel and T. Gu6guen, Smalltalk-80 R.J. Mitchell, Microcomputer Systems Using the STE Bus R.J. Mitchell, Modula-2 Applied Y. Nishinuma and R. Espesser, UNIX - First contact Pim Oets, MS-DOS and PC-DOS -A Practical Guide, second edition A.J. Pilavakis, UNIX Workshop Christian Queinnec, USP E.J. Redfern, Introduction to Pascal for Computational Mathematics Gordon Reece, Microcomputer Modelling by Finite Differences W.P. Salman, O. Tisserand and B. Toulout, FORIH L.E. Scales, Introduction to Non-Linear Optimization Peter S. Sell, Expert Systems - A Practical Introduction A.G. Sutcliffe, Human-Computer Interface Design Colin J. Theaker and Graham R. Brookes, A Practical Course on Operating Systems M.R. Tolhurst et al., Open Systems Interconnection J-M. Trio, 8086 - 8088 Architecture and Programming AJ. Tyrrell, COBOL/rom Pascal M.J. Usher,lnformation Theory for Information Technologists B.S. Walker, Understanding Microprocessors Colin Walls, Programming Dedicated Microprocessors I.R. Wilson and A.M. Addyman, A Practical Introduction to Pascal-with BS6192, second edition Non-series Roy Anderson, Management, Information Systems and Computers 1.0. Angell, Advanced Graphics with the IBM Personal Computer J.E. Bingham and G.W.P. Davies, Planning for Data Communications B.V. Cordingley and D. Chamund, Advanced BASIC Scientific Subroutines N. Frude, A Guide to SPSSIPC+ Percy Mett, Introduction to Computing Barry Thomas, A PostScript Cookbook Neural Networks Eric Davalo and Patrick NaIrn Translated by A. Rawsthome Department of Computer Science University of Manchester M MACMILLAN © Macmillan Education 1991 © Editions Eyrolles 1990 All rights reserved. No reproduction, copy or transmission of this pUblication may be made without written permission. No paragraph of this publication may be reproduced, copied or transmitted save with written permission or in accordance with the provisions of the Copyright, Designs and Patents Act 1988, or under the terms of any licence permitting limited copying issued by the Copyright Licensing Agency, 33-4 Alfred Place, London WCIE 7DP. Any person who does any unauthorised act in relation to this publication may be liable to criminal prosecution and civil claims for damages. Authorised English language edition of Des Reseaux de Neurones, by E. Davalo and P Nairn, published by Editions Eyrolles, Paris 1991 This edition published 1991 by MACMILLAN EDUCATION LTD Houndmills, Basingstoke, Hampshire RG21 2XS and London Companies and representatives throughout the world British Library Cataloguing in Publication Data Davalo, Eric Neural Networks. - (Macmillan computer science) I. Cybernetics I. Title II. Nairn, Patrick 003.5 ISBN 978-0-333-54996-4 ISBN 978-1-349-12312-4 (eBook) DOl 10.1007/978-1-349-12312-4 Contents Foreword x Preface xiii 1 Biological Foundations 1 1.1 Background.................. 1.1.1 The History of the Study of the Brain 1 1.1.2 The Evolution of the Brain . 2 1.2 The Components of the Brain 3 1.2.1 The Neuron . . 3 1.2.2 Synapses... 7 1.2.3 Support Cells . 9 1.3 Functional Principles . 9 1.3.1 Central and Hierarchical Control. 9 1.3.2 Information from the External World 10 1.3.3 Processing Complex Information 11 1.3.4 A Plastic System . . . . . . 15 1.4 Summary . . . . . . . . . . . . . . . . . 17 1.4.1 Biological Characterisation. . . . 17 1.4.2 Functional Description of the Brain 18 2 Neural Models 19 2.1 A Synthetic Neuron . . . . . . . . . . . . . 19 2.1.1 The Model of McCulloch and Pitts 19 2.1.2 General Model . . . . 20 2.1.3 Common Cases . . . . 23 2.2 The Structure of Connections . 24 2.2.1 The General Case. . 24 v vi Contents 2.2.2 Two Classical Models 25 2.3 State Dynamics . . . . . . . . 26 2.4 Connection Dynamics. . . . . 26 2.4.1 The Cybernetic Model 26 2.4.2 The Hebb Rule . . 27 2.4.3 Alternative Rules . 28 2.5 Functioning of the Models 29 2.5.1 Initial State 29 2.5.2 Operation..... 29 2.6 The Perceptron . . . . . . 30 2.6.1 Origins and General Organisation 30 2.6.2 The Simple Perceptron . . . . 31 2.6.3 The Perceptron Rule . . . . . 31 2.6.4 Limitations of the Perceptron 33 2.6.5 Summary .......... . 35 3 Multi-layer Neural Networks 36 3.1 Associative Networks and Pattern Recognition 36 3.2 Single-layer Associative Networks . . . . . . . 37 3.2.1 The Perceptron and Linear Separability 37 3.2.2 Widrow-HoffRule .......... . 40 3.2.3 Single-layer Networks: A General Framework 42 3.2.4 An Application . . . . . . . . . . . . 43 3.2.5 The Limits of Single-layer Networks 45 3.2.6 The Credit Assignment Problem . 47 3.3 Back-propagation ... 47 3.3.1 Introduction.. 47 3.3.2 Formalisation . 48 3.3.3 Examples ... 50 3.3.4 Hidden Representations 51 3.3.5 Applications . . . . . . 55 3.3.6 Difficulties and Limitations 57 3.4 Development of the Back-propagation Model 58 3.4.1 Back-propagation ......... . 59 3.4.2 Models which Extend the Network 60 3.5 Summary .. . . . . . . . . . . . . . . . . . 62 Contents vii 4 The Hopfield Model 63 4.1 A Content-addressable Memory 63 4.2 The Model. . . . . . . . . . . . 64 4.2.1 A Fully-connected Network 64 4.2.2 Learning in Hopfield Networks 65 4.2.3 Stability of States. . . 66 4.2.4 Conclusions.......... 66 4.3 Use in Optimisation Problems . . . . 68 4.3.1 Energy in Hopfield Networks 68 4.3.2 A Dual Problem ..... . . 69 4.3.3 The Travelling Salesman Problem 69 4.4 Simulated Annealing . . . . . . . . . . . 72 4.4.1 A Thermodynamic Analogy . . . 72 4.4.2 Simulated Annealing in Neural Networks 74 4.5 The Boltzmann Machine . . 76 4.5.1 Description ..... 76 4.5.2 Formal Description . 78 4.5.3 Conclusion 80 4.6 Summary . . . . 80 5 The Kohonen Model 81 5.1 A General Model . . . . . . . . . 81 5.1.1 The Synthetic Neuron .. 81 5.1.2 The Learning Mechanism 82 5.1.3 The Structure ofthe Network 83 5.2 Self-adaptive Topological Maps 84 5.2.1 Introduction.......... 84 5.2.2 Specialised Neurons . . . . . 84 5.2.3 Lateral Interaction Between Neurons 84 5.2.4 Consequences ............ . 86 5.2.5 A Simple Two-dimensional Autonomous System 87 5.2.6 Application to the Travelling Salesman Problem 92 5.3 Adaptive Filters ...... . 95 5.3.1 Introduction ........ . 95 5.3.2 Network Description . . . . 95 5.3.3 A Self-associative Memory 96 5.3.4 A Filter for Detecting Novelty . 97 5.3.5 Projective Filters . . . . . . . . 99 viii Contents 5.3.6 The General Case. 99 5.4 Pattern Recognition ... . 100 5.4.1 Introduction ... . 100 5.4.2 Classical Network Limitations. 100 5.4.3 Algorithm Description 100 5.5 Summary .......... . .101 6 Applications of Neural Networks 104 6.1 Introduction.......... 104 6.2 Reasons for Using Neural Networks 104 6.2.1 Some Fascinating Properties 104 6.2.2 Limits in the Use of Neural Networks . 106 6.2.3 Characteristics of Suitable Applications . 107 6.3 Methodology . . 107 6.3.1 Step One . . . . . . . . . 107 6.3.2 Step Two ........ . 108 6.4 Review of Different Applications 108 6.4.1 Classification by Sectors of Activity . 108 6.4.2 Classification by Application Domain 109 6.4.3 Application Examples . . . . . . 109 6.5 Detailed Description of One Application. 114 6.5.1 Overview .... 114 6.5.2 Introduction.......... 114 6.5.3 Data Acquisition . . . . . . . 115 6.5.4 Construction of the Classifier 115 6.5.5 Conclusion 118 7 Neural Computers 119 7.1 Introduction................ 119 7.2 A Model for a General Neural Computer 119 7.3 Commercial Implementations ...... . 122 7.3.1 Sequential Simulations and Coprocessors 122 7.3.2 General Parallel Architectures . . 124 7.4 Prototypes and Prospects . . . . . . . . . 125 7.4.1 Specialised Parallel Architectures 125 7.4.2 VLSI Neural Computers . 125 7.4.3 Optical Neural Computers 127 7.4.4 Molecular Computers 128 7.5 Summary . . . . . . . . . . . . . 129 Contents ix Appendix A Back-propagation Rule 130 Appendix B The Kohonen Model -Formal Description 133 B.1 Algorithm for a 2-dimensional Autonomous System 133 B.2 Algorithm for Travelling Salesman Problem . 133 B.3 The Pseudo-inverse: the Penrose Algorithm. 134 B.4 Learning Algorithm for Pattern Recognition . 135 References 136