Semi-supervised eigenvectors for large-scale locally-biased learning

zbMATH Open1311.68136arXiv1304.7528MaRDI QIDQ5249574FDOQ5249574

Authors: Toke J. Hansen, Michael W. Mahoney 

Publication date: 6 May 2015

Abstract: In many applications, one has side information, e.g., labels that are provided in a semi-supervised manner, about a specific target region of a large data set, and one wants to perform machine learning and data analysis tasks "nearby" that prespecified target region. For example, one might be interested in the clustering structure of a data graph near a prespecified "seed set" of nodes, or one might be interested in finding partitions in an image that are near a prespecified "ground truth" set of pixels. Locally-biased problems of this sort are particularly challenging for popular eigenvector-based machine learning and data analysis tools. At root, the reason is that eigenvectors are inherently global quantities, thus limiting the applicability of eigenvector-based methods in situations where one is interested in very local properties of the data. In this paper, we address this issue by providing a methodology to construct semi-supervised eigenvectors of a graph Laplacian, and we illustrate how these locally-biased eigenvectors can be used to perform locally-biased machine learning. These semi-supervised eigenvectors capture successively-orthogonalized directions of maximum variance, conditioned on being well-correlated with an input seed set of nodes that is assumed to be provided in a semi-supervised manner. We show that these semi-supervised eigenvectors can be computed quickly as the solution to a system of linear equations; and we also describe several variants of our basic method that have improved scaling properties. We provide several empirical examples demonstrating how these semi-supervised eigenvectors can be used to perform locally-biased learning; and we discuss the relationship between our results and recent machine learning algorithms that use global eigenvectors of the graph Laplacian.

Full work available at URL: https://arxiv.org/abs/1304.7528

Recommendations

• scientific article; zbMATH DE number 6276186
• Semi-supervised learning with regularized Laplacian
• Properly-weighted graph Laplacian for semi-supervised learning
• Semi-supervised graph clustering: a kernel approach
• Learning Theory

zbMATH Keywords

kernel methodsspectral clusteringsemi-supervised learninglarge-scale machine learninglocal spectral methodslocally-biased learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Cited In (3)

• Title not available (Why is that?)
• A Nyström spectral clustering algorithm based on probability incremental sampling
• Local learning integrating global structure for large scale semi-supervised classification

Uses Software

• MNIST

This page was built for publication: Semi-supervised eigenvectors for large-scale locally-biased learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5249574)