Isolation Kernel: The X Factor in Efficient and Effective Large Scale
  Online Kernel Learning
  Large scale online kernel learning aims to build an efficient and scalable
kernel-based predictive model incrementally from a sequence of potentially
infinite data points. A current key approach focuses on ways to produce an
approximate finite-dimensional feature map, assuming that the kernel used has a
feature map with intractable dimensionality---an assumption traditionally held
in kernel-based methods. While this approach can deal with large scale datasets
efficiently, this outcome is achieved by compromising predictive accuracy
because of the approximation. We offer an alternative approach which overrides
the assumption and puts the kernel used at the heart of the approach. It
focuses on creating an exact, sparse and finite-dimensional feature map of a
kernel called Isolation Kernel. Using this new approach, to achieve the above
aim of large scale online kernel learning becomes extremely simple---simply use
Isolation Kernel instead of a kernel having a feature map with intractable
dimensionality. We show that, using Isolation Kernel, large scale online kernel
learning can be achieved efficiently without sacrificing accuracy.
