Investigating The Scalability of Kernel Minimum Enclosing Balls for Novelty Detection: Algorithms with Empirical Evaluations

Though being a family of powerful representation learning methods, Kernel Minimum Enclosing Balls (KMEBs), as for many kernel based methods, require careful attention when analyzing large scale data. In this standalone paper we take a look at the algorithms for Kernel Minimum Enclosing Balls and examine their scalability. To that end, we firstly present a detailed investigation of the recently existing scalable methods to compute the kernel minimum enclosing balls. Those methods feature sub-matrices, coresets and density-based sampling approaches. The strength of those methods lies in their simplicity and theoretically proven approximation of the decision boundaries. Secondly, we bring additional value to the scalability of KMEBs by introducing a principle of uniting decision boundaries obtained from multiple kernel balls. This principle can be described as sampling batches of data, performing independent training on those batches and using models fitted to the batches to create the ensemble approach. We present two simple and efficient algorithms that rely on the above-described principle: randomized sampling speedup and characteristic function based partition. We show that former speedup is highly efficient, and we assume that the reason for it lies in KMEBs’ outstanding abilities in few-shot learning. Additionally, we compare two introduced algorithms against recent methods from literature mentioned above. We perform the comparison of novelty detection scores on the example of two popular image datasets.