Off-the-grid: Fast and Effective Hyperparameter Search for Kernel Clustering

Bruno Ordozgoiti Rubio, Lluís Belanche-Muñoz

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

Kernel functions are a powerful tool to enhance the k-means clustering algorithm via the kernel trick. It is known that the parameters of the chosen kernel function can have a dramatic impact on the result. In supervised settings, these can be tuned via cross-validation, but for clustering this is not straightforward and heuristics are usually employed. In this paper we study the impact of kernel parameters on kernel k-means. In particular, we derive a lower bound, tight up to constant factors, below which the parameter of the RBF kernel will render kernel k-means meaningless. We argue that grid search can be ineffective for hyperparameter search in this context and propose an alternative algorithm for this purpose. In addition, we offer an efficient implementation based on fast approximate exponentiation with provable quality guarantees. Our experimental results demonstrate the ability of our method to efficiently reveal a rich and useful set of hyperparameter values.
Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2020, Proceedings
EditorsFrank Hutter, Kristian Kersting, Jefrey Lijffijt, Isabel Valera
Pages399-415
Number of pages17
Edition1
ISBN (Electronic)9783030676612
DOIs
Publication statusPublished - Feb 2021
MoE publication typeA4 Article in a conference publication
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - Virtual, Online
Duration: 14 Sep 202018 Sep 2020
https://ecmlpkdd2020.net/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12458
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases
Abbreviated titleECML-PKDD
CityVirtual, Online
Period14/09/202018/09/2020
Internet address

Fingerprint

Dive into the research topics of 'Off-the-grid: Fast and Effective Hyperparameter Search for Kernel Clustering'. Together they form a unique fingerprint.

Cite this