Sparsity induced similarity measure for label propagation
Authors:
- 1 September 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15505499,p. 317-324
Abstract
Graph-based semi-supervised learning has gained considerable interests in the past several years thanks to its effectiveness in combining labeled and unlabeled data through label propagation for better object modeling and classification. A critical issue in constructing a graph is the weight assignment where the weight of an edge specifies the similarity between two data points. In this paper, we present a novel technique to measure the similarities among data points by decomposing each data point as an L1 sparse linear combination of the rest of the data points. The main idea is that the coefficients in such a sparse decomposition reflect the point's neighborhood structure thus providing better similarity measures among the decomposed data point and the rest of the data points. The proposed approach is evaluated on four commonly-used data sets and the experimental results show that the proposed Sparsity Induced Similarity (SIS) measure significantly improves label propagation performance. As an application of the SIS-based label propagation, we show that the SIS measure can be used to improve the Bag-of-Words approach for scene classification.Keywords
This publication has 14 references indexed in Scilit:
- Robust Label Propagation on Multiple NetworksIEEE Transactions on Neural Networks, 2008
- Counting faces of randomly projected polytopes when the projection radically lowers dimensionJournal of the American Mathematical Society, 2008
- Correlated Label Propagation with Application to Multi-label Learning2006
- Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories2006
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solutionCommunications on Pure and Applied Mathematics, 2006
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Spatially coherent clustering using graph cuts2004
- Analyzing appearance and contour based methods for object categorization2003
- Modeling the Shape of the Scene: A Holistic Representation of the Spatial EnvelopeInternational Journal of Computer Vision, 2001
- A database for handwritten text recognition researchIEEE Transactions on Pattern Analysis and Machine Intelligence, 1994