Nonlinear parameter estimation in classification problems

Abstract

A nonlinear generalisation of the perceptron learning algorithm is presented and analysed. The new algorithm is designed for learning nonlinearly parametrised decision regions. It is shown that this algorithm can be viewed as a stepwise gradient descent of a certain cost function. Averaging theory is used to describe the behaviour of the algorithm, and in the process conditions guaranteeing convergence of the algorithm are established. These conditions are hard to test, so some simpler sufficient are derived using the directional derivative of the instantaneous cost. A number of simulation examples and applications are given, showing the variety of situations in which the algorithm can be used. In the initial analysis, a great deal of a priori knowledge about the decision region to be learnt has been assumed-in particular, it is assumed that the decision region is parametrised by some known (nonlinear) function. Often in applications, a general class of decision regions must be assumed, in which case the best approximate from the class is sought. It is shown that function approximation results can be used to derive degree of approximation results for decision regions. The approximating classes of decision regions considered are described by polynomial and neural network parametrisations. One shortcoming of all gradient descent type algorithms, such as the online learning algorithm discussed in the first part of this thesis, is that estimates may be attracted to local minima of the cost function. This is a problem because local minima occur in many interesting cases. Therefore a modified version of the algorithm, which avoids local minima traps, is presented. In the new algorithm, a number of parameter estimates ( called a congregation) are kept at any one time, and periodically all but the best estimate are restarted. Convergence of the new algorithm is established using the averaging theory that was used for the first algorithm. A probabilistic result concerning the expected time to convergence of the algorithm is given, and the effect of different population sizes is investigated. Again, a number of simulation examples are presented, including the application to the CMA algorithm for blind equalisation. Show more