Exhaustive and Efficient Constraint Propagation: A Graph-Based Learning Approach and Its Applications

This paper presents a novel pairwise constraint propagation approach by decomposing the challenging constraint propagation problem into a set of independent semi-supervised classification subproblems which can be solved in quadratic time using label propagation based on -nearest neighbor graphs. Con...

Full description

Saved in:
Bibliographic Details
Published in:International journal of computer vision 2013-07, Vol.103 (3), p.306-325
Main Authors: Lu, Zhiwu, Peng, Yuxin
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Artificial Intelligence
Classification
Cluster analysis
Computer Imaging
Computer Science
Computer science
control theory
systems
Computer vision
Control theory
Data points
Data processing. List processing. Character string processing
Exact sciences and technology
Graphs
Image Processing and Computer Vision
Information retrieval
Information systems. Data bases
Learning
Machine learning
Memory organisation. Data processing
Multimedia
Pattern Recognition
Pattern Recognition and Graphics
Propagation
Similarity
Software
Spectra
Studies
Vision
Vision systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a novel pairwise constraint propagation approach by decomposing the challenging constraint propagation problem into a set of independent semi-supervised classification subproblems which can be solved in quadratic time using label propagation based on -nearest neighbor graphs. Considering that this time cost is proportional to the number of all possible pairwise constraints, our approach actually provides an efficient solution for exhaustively propagating pairwise constraints throughout the entire dataset. The resulting exhaustive set of propagated pairwise constraints are further used to adjust the similarity matrix for constrained spectral clustering. Other than the traditional constraint propagation on single-source data, our approach is also extended to more challenging constraint propagation on multi-source data where each pairwise constraint is defined over a pair of data points from different sources. This multi-source constraint propagation has an important application to cross-modal multimedia retrieval. Extensive results have shown the superior performance of our approach.
ISSN:0920-5691
1573-1405
DOI:10.1007/s11263-012-0602-z