This chapter discusses probabilistic global search methods which are suited for neural network optimization. Global search methods, as opposed to deterministic gradient-based search methods, must be used in optimization problems where reaching the global minimum (or maximum) is at a premium. However, the price one pays for using global search methods is increased computational and/or storage requirements as compared to that of local search. The intrinsic slowness of global search methods is mainly due to the slow but crucial exploration mechanisms employed.

Global search methods may be used as optimal learning algorithms for neural networks. Some global search methods may also be mapped onto recurrent neural networks such that the retrieval dynamics of these networks escape local minima and evolve towards global minimum.

Two major probabilistic global search methods are covered in this chapter. The first method is stochastic simulated annealing which is motivated by statistical mechanics, and the second method is genetic algorithms which is motivated by the mechanics of natural selection and natural genetics. The exploration mechanism in simulated annealing is governed by the Boltzmann-Gibbs probability distribution, and its convergence is determined by a "cooling" schedule of slowly decreasing "temperature." This method is especially appealing since it can be naturally implemented by a stochastic neural network known as the Boltzmann machine. The Boltzmann machine is a stochastic version of Hopfield's energy minimizing net which is capable of almost guaranteed convergence to the global minimum of an arbitrary bounded quadratic energy function. Simulated annealing is also applied to optimal weight learning in generally interconnected multilayer Boltzmann machines, thus extending the applicability of the Boltzmann machine from combinatorial optimization to optimal supervised learning of complex binary mappings. However, these desirable features of Boltzmann machines come with slow learning and/or retrieval.

Mean-field annealing is a deterministic approximation (based on mean-field theory) to stochastic simulated annealing where the mean behavior of the stochastic state transitions are used to characterize the Boltzmann machine. This approximation is found to preserve the optimal characteristics of the Boltzmann machine but with one to two orders of magnitude speed advantage. Mean-field annealing is applied in the context of retrieval dynamics and weights learning in a Boltzmann machine. It is interesting to see that applying mean-field theory to a single-layer Boltzmann machine leads to the deterministic continuous Hopfield net.

Genetic algorithms (GA's) are introduced as another method for optimal neural network design. They employ a parallel multipoint probabilistic search strategy which is biased towards reinforcing search points of high fitness. The most distinguishing feature of GA's is their flexibility and applicability to a wide range of optimization problems. In the domain of neural networks, GA's are useful as global search methods for synthesizing the weights of generally interconnected networks, optimal network architectures and learning parameters, and optimal learning rules.

It is argued that, in order to make global search methods more speed efficient, local gradient information (if available) could be used advantageously. In the context of GA optimization, it is possible to think of the GA as an evolutionary mechanism which could be accelerated by simple learning processes. This observation motivates the hybrid GA/gradient descent method for feedforward multilayer net training introduced at the end of the chapter.

to find a minimum of the function y(x) = x sin starting from the initial search point: a. x(0) = 0.05; b. x(0) = 0.1; c. x(0) = 0.15. Assume  = 10-4.

† 8.1.4 Repeat Problem 8.1.3 for the function in Problem 8.1.1 (c) with x(0) = -20 and  = 0.01.

† 8.1.5 Employ the gradient descent/ascent global search strategy described in Section 8.1 to find the global minima of the functions (a) - (d) in Problem 8.1.1.

† 8.1.6 "Global descent" is a global search method which was discussed in Section 5.1.2. Implement the global descent method to search for the global minimum of the function y(x) given in Problem 8.1.1 (c). Assume ,  = 0.005, x = 0.01,  = 2, and experiment with different values of the repeller parameter . Plot y[x(t)] versus t for various values of k.

† 8.1.7 For the uni-variate case, y = y(x), the global minimum can be reached by gradient descent on the noisy function

where N(t) is a "noise signal" and c(t) is a parameter which controls the magnitude of noise. Apply the gradient descent rule (with  = 0.01) of Problem 8.1.3 to . Use the resulting "stochastic" gradient rule to find the global minimum of y(x) in Problem 8.1.1 (c). Assume that N(t) is a normally distributed sequence with a mean of zero and a variance of one, and that c(t) = 150 exp(-t). Start from x(0) = -20 and experiment with different values of ,   [0.01, 0.001]. Plot x(t) versus t (t = 0, 1, 2, ...). What range of values of are likely to lead to the global minimum of y(x)?

† 8.2.1 Use the simulated annealing algorithm described in Section 8.2 with the temperature schedule in Equation (8.2.5) to find the global minima of the functions in Problem 8.1.1 (a) - (c) and Problem 8.1.2 (a) and (b). Make intelligent choices for the variance of the random perturbation x taking into account the domain of the function being optimized. Also, make use of the plots of these functions to estimate the largest possible change in y due to x, , and use this information to guide your estimate of To.