Institut de Mathématiques de Luminy

Abstract 2004-3

Ghattas Badih, Perera Gonzalo.
A memory-restricted learning algorithm.

In this paper we present an algorithm for supervised learning under severe memory restrictions: at each step of the learning process, the total amount of information to be kept in memory must be smaller than a fixed quantity M. This is of particular interest for apllications where data correspond to signals or very high-dimensional vectors. Our algorithm proceeds as a sequence of cycles: for each cycle, a training sample sequence of fixed size T is available and a prediction rule is chosen from the combination of a given class of statistical models F and a set of experts. The choice is made by means of a matrix of credit scores cj(x,h), which measures, at the cycle j, how much should we trust on the advice of predictor h to decide the predicted value to be assigned to the input x. The particular choice of the predictor fj corresponding to the model F at cycle j is made by maximization of the mean of a given reward function R (or minimization of a cost function). A fixed validation sample of size V is also assumed to be available, and for the validation of the procedure at cycle j, each value of x corresponding to the evaluation sample is given as an input to the prediction rule and its performance is measured by means of the reward function R. The credit to be assigned to each predictor h for step j + 1 at the point x is the sum of cj(x,h) and the overall reward obtained for the predictor h when it was used to predict the value corresponding to the input x. Once this is done, only the matrix of credits, the class F and the last choice of the model will be kept in memory; any other data will be removed and a new training sample corresponding to a new iteration of the algorithm will be used. No use of an arbitrary large training sample is allowed. The asymptotic behaviour of our algorithm is derived and in particular its performance is compared to that of a similar procedure without memory restriction (when arbitrary large training samples are available).

Mathematics Subject Classification (2000): 68T05, 93E35, 62J20.

Keywords: learning algorithm, prediction model, classification, regression, expert advice, limit theorems, Markov processes, Bayes rules.


Last update : january 29, 2004, EL.