Learning Algorithms

Theory and Applications in Signal Processing, Control and Communications

P. Mars

• Publisher: CRC Press
• Year: 2018
• Print ISBN: 9781315894874
• eBook ISBN: 9781351090872
• Topic: Technology & Engineering
• Subtopic: Electrical Engineering & Telecommunications
• Index: Technology & Engineering

Over the past decade, interest in computational or non-symbolic artificial intelligence has grown. The algorithms involved have the ability to learn from past experience, and therefore have significant potential in the adaptive control of signals and systems. This book focuses on the theory and applications of learning algorithms-stochastic learning automata; artificial neural networks; and genetic algorithms, evolutionary strategies, and evolutionary programming. Hybrid combinations of various algorithms are also discussed.Chapter 1 provides a brief overview of the topics discussed and organization of the text. The first half of the book (Chapters 2 through 4) discusses the basic theory of the learning algorithms, with one chapter devoted to each type. In the second half (Chapters 5 through 7), the emphasis is on a wide range of applications drawn from adaptive signal processing, system identification, and adaptive control problems in telecommunication networks.Learning Algorithms: Theory and Applications in Signal Processing, Control and Communications is an excellent text for final year undergraduate and first year graduate students in engineering, computer science, and related areas. Professional engineers and everyone involved in the application of learning techniques in adaptive signal processing, control, and communications will find this text a valuable synthesis of theory and practical application of the most useful algorithms.

Chapter One

Introduction

In this book we use the term learning to denote machine learning based on the notion of change [Sim83]. According to this definition, learning denotes changes in the system that are adaptive in the sense that they enable the system to do the same task or tasks drawn from the same population more efficiently and more effectively the next time.

Learning can be further classified into supervised and unsupervised learning. In supervised learning we assume the availability of a teacher who provides training samples of inputs and desired outputs. In contrast, unsupervised learning involves the processing of only inputs to perform some general clustering of information in the input space.

This book focuses on three learning paradigms originally derived from biology or human psychology. Specifically we consider the theory and some applications of Stochastic Learning Automata, Artificial Neural Networks and Genetic/Evolutionary Algorithms.

A Stochastic Learning Automaton (SLA) is an automaton that operates in a random environment and updates its action probabilities in accordance with the inputs received from the environment so as to improve its performance in some specified sense. Early work in the context of mathematical psychology was followed by major research efforts in both Russia and the U.S.

An automaton is modelled as a finite state machine with a stochastic transition matrix. Reinforcement learning algorithms are used to update the transition probabilities of the stochastic matrix. Both linear and non-linear learning algorithms have been extensively studied in the literature. A seminal research monograph provides an excellent detailed critical review of the various algorithms [NT89a].

In addition to isolated automata, interconnected arrays of automata involving games and hierarchical structures have been studied. Automata have been used as models for investigation of decentralised decision making in uncertain environments and sequential models have led to new results in the control of Markov chains [NW83, WN86].

Artificial Neural Networks (ANNs) are parallel distributed information processing structures consisting of an array of interconnected processing elements called neurons. Each neuron has several inputs and one output. Each connection between neurons has an associated weight, and an activation function within the neuron determines the relationship between the input excitation and the neuron’s output.

Numerous ANN architectures have been proposed in the literature. They mainly differ in their choice of learning algorithm (i.e., how are the connection weights changed?) and the neural network topology [Hay94].

We consider three specific paradigms of Evolutionary optimisation — Genetic Algorithms, Evolutionary Strategies and Evolutionary Programming. Genetic Algorithms (GAs) are search techniques that are based on the mechanics of natural selection and genetics, involving a structured yet randomised information exchange resulting in a survival of the fittest amongst a population of string structures. The GA operates on a population of structures that are fixed length strings representing all possible solutions to a problem domain. A binary expression can be used to encode a parameter as a bit string. Using such a representation, an initial population is randomly generated. For each structure (trial solution) in the population, a fitness value is assigned. Each structure is then assigned a probability measure based on the fitness value that decides the contribution that structure would make to the next generation. This phase is known as the Reproduction Phase. Each of the offspring generated by the reproduction phase is then modified using genetic operators of Crossover and Mutation. In the Crossover operation, sub-strings of two individual strings selected randomly from the population are swapped resulting in two new strings. The crossover operation is governed by a crossover probability. The mutation operator generates a new string by independently modifying the values at each location of an existing string with a certain probability of mutation.

Evolutionary Strategies (ESs) are another optimisation technique based on the principles of natural evolution. The algorithm operates on a population of string structures, each of which represents a solution to the optimisation problem. Each string undergoes genetic modifications resulting in a new string, which then forms part of a new population. Multi-parameter cases are handled in the same way as in GAs by concatenating the string representations of all the parameters of the optimisation process. As in the case with GAs, evolutionary strategies are also based on the principle of survival of the fittest. An important difference between GAs and ESs is the fact that GAs operate on a genotypic level (coding of the real parameters) while ESs operate at the phenotypic level using the parameter values as genetic material.

The third and final evolutionary paradigm we consider is Evolutionary Programming (EP). As with ES, the EP technique uses a phenotypic representation of parameters that rely on mutation as the primary search operator. The main difference between ES and EP is the manner of selection using different ranking schemes and the use of the fitness value as the standard deviation for mutation of a particular string. An important feature of EP is the lack of any kind of crossover/recombination operator.

What type of applications are best suited for the three main types of learning paradigms? A great deal of early published work was concerned with inappropriate or trivial applications with no clear demonstration that the algorithm considered was superior in some way to the best alternative.

In the case of stochastic learning automation, clear guidelines have been established [NT89a] of the desired characteristics of a problem for automata application:

1. The system should involve large operational uncertainties and must be of such a complexity that a dynamic mathematical model cannot be established.
2. The system should be amenable to decentralised control with each automata able to select between a small number of finite actions.
3. The global performance index should be stochastic and feedback of some function of the index provided to each automata.

As we will demonstrate in Chapter 7 one application that satisfies the above criteria is provided by the problem of routing in communications networks.

ANNs have been applied to a very wide spectrum of applications areas. The most convincing applications have been those involving some form of pattern recognition. Although ANNs have been applied to many off-line pattern recognition tasks, the really significant results are obtained in using the networks for complex pattern recognition in real time [Hay94].

Genetic and Evolutionary optimisation algorithms are robust search techniques well suited to optimisation problems involving stochastic multi-model surfaces in several dimensions. Unlike stochastic learning automata, they do not suffer from slow convergence as the dimension of the search space is significantly increased. We demonstrate the application of genetic and evolutionary algorithms to adaptive signal processing in Chapter 5.

In some application areas the best approach is provided by hybrid combinations of various algorithms. Work has been reported on combinations of ANNs and expert systems [Fu94], neuro fuzzy approaches [KWH92] and hierarchical intelligent control systems [Sar87].

The book is organised into two parts. The first part (Chapters 2, 3 and 4) provides the basic theory of Stochastic Learning Automata, Artificial Neural Networks and Genetic/Evolutionary Algorithms. Chapter 2 reviews the basic types of learning automata including discretised algorithms and relative reward strength algorithms. This chapter also discusses interconnected hierarchical automata and automata games. There are numerous types of ANNs available. Chapter 3 considers four of the most popular structures. Specifically we deal with Multilayer Perceptrons, Radial Basis Function Networks, Kohonen Self-Organisation Networks and, finally, Reinforcement Learning Neural Networks. This chapter concludes with a discussion of inductive and statistical generalisation. Chapter 4 deals with GAs and the closely related ESs and EP. As mentioned previously, all three methods are based on the principle of the survival of the fittest.

The second part of the book (Chapters 5, 6 and 7) considers selected applications of the learning algorithms to problems in adaptive signal processing, control (system identification) and communications. Chapter 5 describes the application of stochastic learning automata to parameter optimisation in adaptive filters. The problem essentially involves the minimisation of a multi-model surface embedded in noise. We show that Genetic/Evolutionary Algorithms are able to overcome the dimensionality problems associated with stochastic learning automata. Chapter 6 considers a problem fundamental to both control and signal processing — identification of a non-linear system. We consider the use of ANNs for the identification of non-linear dynamic systems and extend the results to chaotic time series prediction. Finally, Chapter 7 considers three problems in communication systems. The first problem considers access control in broadband Integrated Services Digital Network (ISDN). This is of interest because although ANNs have been proposed, we demonstrate superior performance with a simple random access memory (RAM)-based control rule. Adaptive equalisation is a problem well suited to ANNs and in Chapter 7 we compare the performance obtained with multi-layer perception (MLP), Kohonen and Radial Basis Function Networks. The chapter concludes with a discussion of the use of SLA for dynamic routing in both circuit and packet-switched communication networks.

Chapter Two

Stochastic Learning Automata (SLA)

2.1 Introduction

The process by which biological organisms learn has been a fascinating area of research for well over a century. The focus of research has been mainly two pronged — to understand the principles involved during the learning process of biological systems and to develop methodologies whereby these principles could be incorporated into machines. Learning can be regarded as a change brought about in a system performance as a result of past experience [NT89a]. An important characteristic of a learning system is its ability to improve its performance with time. In a strictly mathematical context, the goal of a learning system can be said to be the optimization of a functional which may not be known completely. Thus, an approach...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Contents
• 1 Introduction
• 2 Stochastic Learning Automata (SLA)
• 3 Artificial Neural Networks (ANN)
• 4 Genetic and Evolutionary Optimisation
• 5 Applications in Signal Processing
• 6 Applications in Systems Control
• 7 Applications in Communications
• Index