Combining the perceptron 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 c(k) = Γ/1n(k + 2), where Γ is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials w1 · x1a1 + ··· + wn · xnan ≥ θ, 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 n = 256, ... , 1024 and ai = 3, ... , 7, 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.