Combining the perception algorithm with logarithmic simulated annealing

Abstract

We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule (-), where (-) is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials (-), we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For (-) and (-), the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.