Weight Annealing Source Code


License for academic use

Weight Annealing source code fore C++ / Matlab Copyright (C) 2002 Gal Elidan, Matan Ninio, Nir Friedman and Dale Schuurmans

This code is released for academic research only under the LESSER GENERAL PUBLIC LICENSE

If you use this code, please cite this paper
@incollection{Elidan+al:2002, author = "Gal Elidan and Matan Ninio and Nir Friedman and Dale Schuurmans", booktitle = "Proc. National Conference on Artificial Intelligence (AAAI-02)", pages = "132-139", year = "2002", title = "Data Perturbation for Escaping Local Maxima in Learning", }

For purposes other then academic research you should contact:

annealing@cs.huji.ac.il


Weight Annealing in a Nutshell

Weight Annealing is a general method for escaping local maxima in optimization problems and learning scenarios. It was introduced in Data Perturbation for Escaping Local Maxima in Learning, G. Elidan, M. Ninio, N. Friedman and D. Schuurmans, AAAI02.

The idea of Weight Annealing is to introduce perturbations into the search process by changing the weight of the instances. This combined with annealing gives state of the art results in many domains (so far we have tried Bayesian networks, Neural network like functions, clustering, decision trees and more). The outline of the algorithm is very simple: given the current model, new weights are calculated. These are fed into the black box optimizer (e.g. greedy hill climbing, gradient ascent...) that produces a new hypothesis and so on. The process is annealed toward the original weights so that at the final stage optimization is performed on the actual target function.

At the heart of this process is the re-weighting procedure. There are two schemes:

In order to use Weight Annealing you should be able to formulate your target function (or score) as a function of instances and their weights. If you want to use Adversarial Reweighting the target function also has to be differentiable with respect to the weights

Example in the source code

A simple example is used as a demonstration for both the C++ and Matlab code. We consider K points (20 in the demo) equally spread out between 0 and 1. We now look at a simple regression problem of fitting those point with a cosine function. That is, out target function is:

sum ( w(i) * cos(PI * i/20 * x) )

where i = { 1...20 }. We look for x that maximized this function. This can be viewed as finding the frequency that fits the cos with our instance points.

C++ source Code and Example

WeightUpdate.h defines a hierarchy of classes that perform weight annealing.
tWeightUpdateRandom and tWeightUpdateGradient are derived from the interface class tWeightUpdate.

Both reweighting objects are initialized with the starting and stopping temperature and the coolling factor. The object progresses via iterative calls to the CoolDown() method followed by a call to GetWeights(). See the header file for more information.

The easiest way to start is to look at the simple example described above implemented in testAnneal.cpp. Start with looking at the main() function.

all the files you need can be found in this tarball.
in the tarball you will find: