Adaptive Budget for Online Learning

Although the perceptron algorithm has been considered a simple supervised learning algorithm, it has the advantage of learning from the training data set one at a time. This makes it more suitable for online learning tasks and new families of kernelized perceptrons have been shown to be effective in handling streaming data. However, the amount of memory required for storing the online model which grows without any limits and the consequent excessive computation and time complexity makes this framework infeasible in real problems. A common solution to this restriction is to limit the allowed budget size and discard some of the examples in the memory when the budget size is exceeded. In this paper we present a framework for choosing a proper adaptive budget size based on underlying properties of data streams. The experimental results on several synthetic and real data sets show the efficiency of our proposed system compared to other algorithms.