Online Regression with Kernels

TitleOnline Regression with Kernels
Publication TypeBook Chapter
Year of Publication2014
AuthorsS. Van Vaerenbergh, and I. Santamaría
Book TitleRegularization, Optimization, Kernels, and Support Vector Machines
Series VolumeMachine Learning & Pattern Recognition Series
PublisherChapman and Hall/CRC
CityNew York
ISBN Number9781482241396
KeywordsKLMS, KRLS
AbstractOnline machine learning algorithms are designed to learn from one data instance at a time. They are typically used in real-time scenarios, such as prediction or tracking problems, where data arrive sequentially and instant decisions must be made. The real-time nature of these settings implies that shortly after the decision is made, the true label will be made available, which allows the learning algorithm to adjust its solution before a new datum is received. Online kernel methods extend the nonlinear learning capabilities of standard batch kernel methods to online environments. Especially important for these techniques is that they maintain their computational load moderate during each iteration, in order to perform fast updates in real time. Ideally, they should not only be able to learn in a stationary environment but also in non-stationary settings, where they must forget outdated information and adapt their solution to respond to changes in time. Online kernel methods also find use in batch scenarios where the amount of data is too high to fit in the machine's memory, and one or several passes over the data are to be performed. In this chapter we focus on the problem of online regression. We will give an overview of the most important kernel-based methods for this problem, which have been developed over the span of the last decade. We start by formulating the online solution to the kernel ridge regression problem, and we point out different strategies to overcome the bottlenecks associated to using kernels in online methods. The discussed techniques are often referred to as kernel adaptive filtering algorithms, due to their close relationship with classical adaptive filters from the signal processing literature. After reviewing the most relevant algorithms in this area, we introduce an evaluation framework that allows us to compare their performance. We finish the discussion with a brief overview of the recent and future research directions.