Learning nonparametric kernel matrices from pairwise constraints

Many kernel learning methods have to assume parametric forms for the target kernel functions, which significantly limits the capability of kernels in fitting diverse patterns. Some kernel learning methods assume the target kernel matrix to be a linear combination of parametric kernel matrices. This assumption again importantly limits the flexibility of the target kernel matrices. The key challenge with nonparametric kernel learning arises from the difficulty in linking the nonparametric kernels to the input patterns. In this paper, we resolve this problem by introducing the graph Laplacian of the observed data as a regularizer when optimizing the kernel matrix with respect to the pairwise constraints. We formulate the problem into Semi-Definite Programs (SDP), and propose an efficient algorithm to solve the SDP problem. The extensive evaluation on clustering with pairwise constraints shows that the proposed nonparametric kernel learning method is more effective than other state-of-the-art kernel learning techniques.

• Publication year

  2007

• Venue

  International Conference on Machine Learning

• Publication date

  2007-06-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1273496.1273542
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Statistical Learning Theory

  2021influential reference
• Learning low-rank kernel matrices

  2006cited by this paper
• Learning the unified kernel machines for classification

  2006influential reference
• Learning a Mahalanobis Metric from Equivalence Constraints

  2005influential reference
• Analysis of Spectral Kernel Design based Semi-supervised Learning

  2005cited by this paper
• YALMIP : a toolbox for modeling and optimization in MATLAB

  2004cited by this paper
• Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning

  2004influential reference
• Regularization and Semi-supervised Learning on Large Graphs

  2004cited by this paper
• Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions

  2003cited by this paper
• Cluster Kernels for Semi-Supervised Learning

  2002influential reference
• Learning the Kernel Matrix with Semidefinite Programming

  2002influential reference
• Distance Metric Learning with Application to Clustering with Side-Information

  2002influential reference
• Diffusion Kernels on Graphs and Other Discrete Input Spaces

  2002cited by this paper
• Diffusion kernels on graphs and other discrete structures

  2002cited by this paper
• Learning the Kernel Matrix with Semi-Definite Programming

  2002influential reference
• On Kernel-Target Alignment

  2001influential reference
• Learning with Kernels: support vector machines, regularization, optimization, and beyond

  2001influential reference
• Constrained K-means Clustering with Background Knowledge

  2001cited by this paper
• Algorithms for Non-negative Matrix Factorization

  2000cited by this paper
• Fast Training of Support Vector Machines using Sequential Minimal Optimization

  2000influential reference
• An Introduction to the Conjugate Gradient Method Without the Agonizing Pain

  1994cited by this paper

• Semi-supervised constrained clustering: an in-depth overview, ranked taxonomy and future research directions

  2025cites this paper
• Decomposition and Symmetric Kernel Deep Neural Network Fuzzy Support Vector Machine

  2024cites this paper
• Semi-Supervised SPO Tree Classifier Based on the DPC Framework

  2024cites this paper
• Kernel Learning by Spectral Representation and Gaussian Mixtures

  2023cites this paper
• A Bibliographic View on Constrained Clustering

  2022cites this paper
• Joint Embedding Self-Supervised Learning in the Kernel Regime

  2022cites this paper
• Constrained clustering and multiple kernel learning without pairwise constraint relaxation

  2022cites this paper
• Semi-supervised consensus clustering based on closed patterns

  2021cites this paper
• Online kernel classification with adjustable bandwidth using control-based learning approach

  2020cites this paper
• Pairwise Constraint Propagation With Dual Adversarial Manifold Regularization

  2020cites this paper
• Semisupervised learning based on nuclear norm regularization

  2020cites this paper
• Theoretical basis of machine learning

  2020cites this paper
• Constrained Clustering: Current and New Trends

  2020cites this paper
• Semi-supervised kernel matrix learning using adaptive constraint-based seed propagation

  2020cites this paper
• Large Scale Online Multiple Kernel Regression with Application to Time-Series Prediction

  2019cites this paper
• Imbalance-aware Pairwise Constraint Propagation

  2019cites this paper
• Semi-Supervised Ensemble Clustering

  2019cites this paper
• Efficient Low-Rank Semidefinite Programming With Robust Loss Functions

  2019cites this paper
• Random forest for dissimilarity based multi-view learning: application to radiomics. (Forêt aléatoire pour l'apprentissage multi-vues basé sur la dissimilarité: Application à la Radiomique)

  2019cites this paper
• Querying informative constraints for data clustering: An embedding approach

  2019cites this paper
• Robust Learning from Noisy Side-information by Semidefinite Programming

  2019cites this paper
• Institutional Knowledge at Singapore Management University Unsupervised Multiple Kernel Learning

  2019cites this paper
• Learning a metric when clustering data points in the presence of constraints

  2019influential citation
• Clustering in the presence of side information: a non-linear approach

  2019cites this paper
• Constrained distance based clustering for time-series: a comparative and experimental study

  2018cites this paper
• Learning Data-adaptive Nonparametric Kernels

  2018cites this paper
• Clustering Using Boosted Constrained k-Means Algorithm

  2018cites this paper
• Weighted Large Margin Nearest Center Distance-Based Human Depth Recovery With Limited Bandwidth Consumption

  2018cites this paper
• Drug-Drug Interaction Discovery: Kernel Learning from Heterogeneous Similarities.

  2018cites this paper
• A Random Walk Approach to Query Informative Constraints for Clustering

  2018cites this paper
• Out-of-Sample Extensions for Non-Parametric Kernel Methods

  2017cites this paper
• Composite Kernel Optimization in Semi-Supervised Metric

  2017cites this paper
• Active Clustering with Model-Based Uncertainty Reduction.

  2017cites this paper
• A Semi-supervised Low Rank Kernel Learning Algorithm via Extreme Learning Machine

  2017cites this paper
• Semi-Supervised Clustering Based on Exemplars Constraints

  2017cites this paper
• Large Scale Online Kernel Learning

  2016cites this paper
• A Novel Framework for Learning Geometry-Aware Kernels

  2016cites this paper
• Efficient learning of supervised kernels with a graph-based loss function

  2016cites this paper
• Efficiently and Effectively Learning Models of Similarity from Human Feedback

  2016cites this paper
• Semi-supervised low rank kernel learning algorithm via extreme learning machine

  2016cites this paper
• Embedded non-parametric kernel learning for kernel clustering

  2016influential citation
• Adaptive Constraint Propagation for Semi-Supervised Kernel Matrix Learning

  2015influential citation
• An Efficient Algorithm for Learning Distances that Obey the Triangle Inequality

  2015influential citation
• Exploiting side information in Bayesian nonparametric models and their applications

  2015cites this paper
• Scalable Nonparametric Low-Rank Kernel Learning Using Block Coordinate Descent

  2015cites this paper
• Generalization of Determinant Kernels for Non-Square Matrix and its Application in Video Retrieval

  2015cites this paper
• A semi-supervised privacy-preserving clustering algorithm for healthcare

  2015cites this paper
• Efficient Active Learning Constraints for Improved Semi-Supervised Clustering Performance

  2015cites this paper
• Scalable semi-supervised clustering by spectral kernel learning

  2014cites this paper
• Handbook of Cluster Analysis (provisional top level file)

  2014cites this paper
• Online multiple kernel similarity learning for visual search.

  2014cites this paper
• Quantized Kernel Learning for Feature Matching

  2014cites this paper
• Constraint Neighborhood Projections for Semi-Supervised Clustering

  2014cites this paper
• Online multiple kernel regression

  2014cites this paper
• Content based Video Querying Technique for Video Retrieval and Video Making from Large Video Compilation

  2014cites this paper
• Active Image Clustering with Pairwise Constraints from Humans

  2014influential citation
• Incremental fuzzy clustering with multiple kernels

  2014cites this paper
• Constraint Based Partitional Clustering – a Comprehensive Study and Analysis

  2014cites this paper
• Online Multiple Kernel Similarity Learning for Visual Search

  2014cites this paper
• Ideal regularization for learning kernels from labels

  2014cites this paper
• Collaborative learning from multiple data sources

  2013cites this paper
• Online Multiple Kernel Classification

  2013cites this paper
• Learning mid-perpendicular hyperplane similarity from cannot-link constraints

  2013cites this paper
• Online Learning with (Multiple) Kernels: A Review

  2013cites this paper
• Unsupervised non-parametric kernel learning algorithm

  2013cites this paper
• Flexible Nonparametric Kernel Learning with Different Loss Functions

  2013cites this paper
• Semi-supervised learning with nuclear norm regularization

  2013cites this paper
• Online multi-modal distance learning for scalable multimedia retrieval

  2013cites this paper
• Extending low-rank matrix factorizations for emerging applications

  2013cites this paper
• Learning Triggering Kernels for Multi-dimensional Hawkes Processes

  2013cites this paper
• Uncertainty Sampling for Constrained Cluster Ensemble

  2013cites this paper
• Probabilistic non-linear distance metric learning for constrained clustering

  2013cites this paper
• MKBoost: A Framework of Multiple Kernel Boosting

  2013cites this paper
• Online Active Constraint Selection For Semi-Supervised Clustering

  2012cites this paper
• Learning kernels from labels with ideal regularization

  2012cites this paper
• Learning from noisily connected data

  2012cites this paper
• Boosting with Side Information

  2012cites this paper
• Active sampling for constrained clustering

  2012cites this paper
• Learning kernel combination from noisy pairwise constraints

  2012cites this paper
• Clustering with Extended Constraints by Co-Training

  2012cites this paper
• A survey of the state of the art in learning the kernels

  2012influential citation
• Learning from pairwise constraints by Similarity Neural Networks

  2012cites this paper
• Semi-Supervised Maximum Margin Clustering with Pairwise Constraints

  2012cites this paper
• Iterative Clustering with Constrained Graph Cut

  2012cites this paper
• Improving clustering with pairwise constraints: a discriminative approach

  2012cites this paper
• Exemplars-Constraints for Semi-supervised Clustering

  2012cites this paper
• A unified framework for Support Vector Machines, Multiple Kernel Learning and metric learning

  2012cites this paper
• Fast semi-supervised clustering with enhanced spectral embedding

  2012cites this paper
• Semi-supervised learning with mixed knowledge information

  2012cites this paper
• Active Constraint Selection For Semi-Supervised Clustering

  2012cites this paper
• Graph-cut based Constrained Clustering by Grouping Relational Labels

  2012influential citation
• Integrating Spectral Kernel Learning and Constraints in Semi-Supervised Classification

  2012cites this paper
• AIL Active and Incremental Learning August 27 , 2012 , Montpellier , France ECAI 2012 – 20 TH European Conference on Artificial Intelligence

  2012cites this paper
• Social Image Tag Ranking by Two-View Learning

  2011cites this paper
• Graph-Cut Based Iterative Constrained Clustering

  2011cites this paper
• Non-Parametric Kernel Learning with robust pairwise constraints

  2011influential citation
• Learning a Kernel for Multi-Task Clustering

  2011cites this paper
• Structured clustering with automatic kernel adaptation

  2011cites this paper
• BCDNPKL: Scalable Non-Parametric Kernel Learning Using Block Coordinate Descent

  2011influential citation
• A Family of Simple Non-Parametric Kernel Learning Algorithms

  2011influential citation