The power of comparative reasoning
- 1 November 2011
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2431-2438
- https://doi.org/10.1109/iccv.2011.6126527
Abstract
Rank correlation measures are known for their resilience to perturbations in numeric values and are widely used in many evaluation metrics. Such ordinal measures have rarely been applied in treatment of numeric features as a representational transformation. We emphasize the benefits of ordinal representations of input features both theoretically and empirically. We present a family of algorithms for computing ordinal embeddings based on partial order statistics. Apart from having the stability benefits of ordinal measures, these embeddings are highly nonlinear, giving rise to sparse feature spaces highly favored by several machine learning methods. These embeddings are deterministic, data independent and by virtue of being based on partial order statistics, add another degree of resilience to noise. These machine-learning-free methods when applied to the task of fast similarity search outperform state-of-the-art machine learning methods with complex optimization setups. For solving classification problems, the embeddings provide a nonlinear transformation resulting in sparse binary codes that are well-suited for a large class of machine learning algorithms. These methods show significant improvement on VOC 2010 using simple linear classifiers which can be trained quickly. Our method can be extended to the case of polynomial kernels, while permitting very efficient computation. Further, since the popular Min Hash algorithm is a special case of our method, we demonstrate an efficient scheme for computing Min Hash on conjunctions of binary features. The actual method can be implemented in about 10 lines of code in most languages (2 lines in MATLAB), and does not require any data-driven optimization.Keywords
This publication has 22 references indexed in Scilit:
- SPEC hashing: Similarity preserving algorithm for entropy-based codingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Robust Real-Time Pattern Matching Using Bayesian Sequential Hypothesis TestingIeee Transactions On Pattern Analysis and Machine Intelligence, 2008
- Keypoint recognition using randomized treesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2006
- Large-Scale Duplicate Detection for Web Image SearchPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Boosting Sex Identification PerformanceInternational Journal of Computer Vision, 2006
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- On the resemblance and containment of documentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Min-Wise Independent PermutationsJournal of Computer and System Sciences, 2000
- Approximate nearest neighborsPublished by Association for Computing Machinery (ACM) ,1998
- Non-parametric local transforms for computing visual correspondenceLecture Notes in Computer Science, 1994