nips nips2006 nips2006-174 nips2006-174-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Oren Boiman, Michal Irani
Abstract: We propose a new approach for measuring similarity between two signals, which is applicable to many machine learning tasks, and to many signal types. We say that a signal S1 is “similar” to a signal S2 if it is “easy” to compose S1 from few large contiguous chunks of S2 . Obviously, if we use small enough pieces, then any signal can be composed of any other. Therefore, the larger those pieces are, the more similar S1 is to S2 . This induces a local similarity score at every point in the signal, based on the size of its supported surrounding region. These local scores can in turn be accumulated in a principled information-theoretic way into a global similarity score of the entire S1 to S2 . “Similarity by Composition” can be applied between pairs of signals, between groups of signals, and also between different portions of the same signal. It can therefore be employed in a wide variety of machine learning problems (clustering, classification, retrieval, segmentation, attention, saliency, labelling, etc.), and can be applied to a wide range of signal types (images, video, audio, biological data, etc.) We show a few such examples. 1
[1] S. Altschul, W. Gish, W. Miller, E. Myers, and D. Lipman. Basic local alignment search tool. JMolBiol, 215:403–410, 1990.
[2] E. Bart and S. Ullman. Class-based matching of object parts. In VideoRegister04, page 173, 2004.
[3] A. Birnbaum. On the foundations of statistical inference. J. Amer. Statist. Assoc, 1962.
[4] M. Blank, L. Gorelick, E. Shechtman, M. Irani, and R. Basri. Actions as space-time shapes. In ICCV05.
[5] O. Boiman and M. Irani. Detecting irregularities in images and in video. In ICCV05, pages I: 462–469.
[6] P. Felzenszwalb and D. Huttenlocher. Pictorial structures for object recognition. IJCV, 61, 2005.
[7] R. Fergus, P. Perona, and A. Zisserman. Object class recognition by unsupervised scale-invariant learning. In CVPR03.
[8] S. Lazebnik, C. Schmid, and J. Ponce. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories. In CVPR06.
[9] D. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91–110, 2004.
[10] J. Shi and J. Malik. Normalized cuts and image segmentation. PAMI, 22(8):888–905, August 2000.
[11] J. Sivic, B. Russell, A. Efros, A. Zisserman, and W. Freeman. Discovering objects and their localization in images. In ICCV05, pages I: 370–377.
[12] P. Viola and W. Wells, III. Alignment by maximization of mutual information. In ICCV95, pages 16–23.