A Study of Clustering Techniques and Hierarchical Matrix Formats for Kernel Ridge Regression
We present memory-efficient and scalable algorithms for kernel methods used in machine learning. Using hierarchical matrix approximations for the kernel matrix the memory requirements, the number of floating point operations, and the execution time are drastically reduced compared to standard dense linear algebra routines. We consider both the general $\mathcal{H}$ matrix hierarchical format as well as Hierarchically Semi-Separable (HSS) matrices. Furthermore, we investigate the impact of several preprocessing and clustering techniques on the hierarchical matrix compression. Effective clustering of the input leads to a ten-fold increase in efficiency of the compression. The algorithms are implemented using the STRUMPACK solver library. These results confirm that --- with correct tuning of the hyperparameters --- classification using kernel ridge regression with the compressed matrix does not lose prediction accuracy compared to the exact --- not compressed --- kernel matrix and that our approach can be extended to $\mathcal{O}(1M)$ datasets, for which computation with the full kernel matrix becomes prohibitively expensive. We present numerical experiments in a distributed memory environment up to 1,024 processors of the NERSC's Cori supercomputer using well-known datasets to the machine learning community that range from dimension 8 up to 784.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningClusteringregressionSimilar Papers 제목 키워드 기반
Hierarchical Clustering with Prior Knowledge
Hierarchical clustering is a class of algorithms that seeks to build a hierarchy of clusters. It has been the dominant approach to constructing embedded classification schemes since it outputs dendrograms, which capture …
ClusteringConstrained ClusteringHierarchical Clustering of Hyperspectral Images using Rank-Two Nonnegative Matrix Factorization
In this paper, we design a hierarchical clustering algorithm for high-resolution hyperspectral images. At the core of the algorithm, a new rank-two nonnegative matrix factorizations (NMF) algorithm is used to split the c…
ClusteringVocal Bursts Valence PredictionA Bayesian alternative to mutual information for the hierarchical clustering of dependent random variables
The use of mutual information as a similarity measure in agglomerative hierarchical clustering (AHC) raises an important issue: some correction needs to be applied for the dimensionality of variables. In this work, we fo…
ClusteringIncremental hierarchical text clustering methods: a review
The growth in Internet usage has contributed to a large volume of continuously available data, and has created the need for automatic and efficient organization of the data. In this context, text clustering techniques ar…
ClusteringHierarchical Text ClusteringText ClusteringAn optimal hierarchical clustering approach to segmentation of mobile LiDAR point clouds
This paper proposes a hierarchical clustering approach for the segmentation of mobile LiDAR point clouds. We perform the hierarchical clustering on unorganized point clouds based on a proximity matrix. The dissimilarity …
ClusteringPoint Cloud SegmentationSegmentation