Computational learning theory for artificial neural networks

There are many types of activity which are commonly known as ‘learning’. Here, we shall discuss a mathematical model of one such process, known as the the ‘probably approximately correct ’ (or PAC) model. We shall illustrate how key problems of learning in artificial neural networks can be studied within this framework, presenting theoretical analyses of two important issues: the size of training sample that should be used, and the running time of learning algorithms; in other words, sample complexity and computational complexity. In a general framework for our discussion of learning, we have a ‘real world ’ W containing a set of objects which we shall refer to as examples. We also have a ‘pre-processor ’ P, which takes an example and converts it into a coded message, such as a string of bits or a real vector. This coded version of the example is then presented to M, a machine whose purpose is to recognise certain examples. The output of M is a single bit, either 1 (if the example is recognised as belonging to a certain set), or 0 (if not). For example, M may be a feedforward linear threshold network. The machine can be in one of many states. For example, M might be in a state in which it will recognise examples of th