nips nips2012 nips2012-101 knowledge-graph by maker-knowledge-mining

101 nips-2012-Discriminatively Trained Sparse Code Gradients for Contour Detection

Source: pdf

Author: Ren Xiaofeng, Liefeng Bo

Abstract: Finding contours in natural images is a fundamental problem that serves as the basis of many tasks such as image segmentation and object recognition. At the core of contour detection technologies are a set of hand-designed gradient features, used by most approaches including the state-of-the-art Global Pb (gPb) operator. In this work, we show that contour detection accuracy can be significantly improved by computing Sparse Code Gradients (SCG), which measure contrast using patch representations automatically learned through sparse coding. We use K-SVD for dictionary learning and Orthogonal Matching Pursuit for computing sparse codes on oriented local neighborhoods, and apply multi-scale pooling and power transforms before classifying them with linear SVMs. By extracting rich representations from pixels and avoiding collapsing them prematurely, Sparse Code Gradients effectively learn how to measure local contrasts and ﬁnd contours. We improve the F-measure metric on the BSDS500 benchmark to 0.74 (up from 0.71 of gPb contours). Moreover, our learning approach can easily adapt to novel sensor data such as Kinect-style RGB-D cameras: Sparse Code Gradients on depth maps and surface normals lead to promising contour detection using depth and depth+color, as veriﬁed on the NYU Depth Dataset. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com Abstract Finding contours in natural images is a fundamental problem that serves as the basis of many tasks such as image segmentation and object recognition. [sent-4, score-0.319]

2 At the core of contour detection technologies are a set of hand-designed gradient features, used by most approaches including the state-of-the-art Global Pb (gPb) operator. [sent-5, score-0.499]

3 In this work, we show that contour detection accuracy can be significantly improved by computing Sparse Code Gradients (SCG), which measure contrast using patch representations automatically learned through sparse coding. [sent-6, score-0.692]

4 We use K-SVD for dictionary learning and Orthogonal Matching Pursuit for computing sparse codes on oriented local neighborhoods, and apply multi-scale pooling and power transforms before classifying them with linear SVMs. [sent-7, score-0.53]

5 Moreover, our learning approach can easily adapt to novel sensor data such as Kinect-style RGB-D cameras: Sparse Code Gradients on depth maps and surface normals lead to promising contour detection using depth and depth+color, as veriﬁed on the NYU Depth Dataset. [sent-12, score-0.954]

6 Accurately ﬁnding both object boundaries and interior contours has far reaching implications for many vision tasks including segmentation, recognition and scene understanding. [sent-14, score-0.241]

7 High-quality image segmentation has increasingly been relying on contour analysis, such as in the widely used system of Global Pb [2]. [sent-15, score-0.459]

8 Accurately ﬁnding contours in natural images is a challenging problem and has been extensively studied. [sent-17, score-0.185]

9 With the availability of datasets with human-marked groundtruth contours, a variety of approaches have been proposed and evaluated (see a summary in [2]), such as learning to classify [17, 20, 16], contour grouping [23, 31, 12], multi-scale features [21, 2], and hierarchical region analysis [2]. [sent-18, score-0.459]

10 Most of these approaches have one thing in common [17, 23, 31, 21, 12, 2]: they are built on top of a set of gradient features [17] measuring local contrast of oriented discs, using chisquare distances of histograms of color and textons. [sent-19, score-0.395]

11 Despite various efforts to use generic image features [5] or learn them [16], these hand-designed gradients are still widely used after a decade and support top-ranking algorithms on the Berkeley benchmarks [2]. [sent-20, score-0.202]

12 In this work, we demonstrate that contour detection can be vastly improved by replacing the handdesigned Pb gradients of [17] with rich representations that are automatically learned from data. [sent-21, score-0.695]

13 With multi-scale pooling, oriented gradients efﬁciently capture local contrast and lead to much more accurate contour detection than those using hand-designed features including Global Pb (gPb) [2]. [sent-25, score-0.787]

14 Our sparse code gradients (SCG) are much more effective in capturing local contour contrast than existing features. [sent-29, score-0.688]

15 By only changing local features and keeping the smoothing and globalization parts ﬁxed, we improve the F-measure on the BSDS500 benchmark to 0. [sent-30, score-0.177]

16 Moreover, our approach is built on unsupervised feature learning and can directly apply to novel sensor data such as RGB-D images from Kinect-style depth cameras. [sent-35, score-0.272]

17 Using the NYU Depth dataset [27], we verify that our SCG approach combines the strengths of color and depth contour detection and outperforms an adaptation of gPb to RGB-D by a large margin. [sent-36, score-0.852]

18 Modern approaches to contour detection are evaluated on datasets of natural images against human-marked groundtruth. [sent-38, score-0.52]

19 [17] combined a set of gradient features, using brightness, color and textons, to outperform the Canny edge detector on the Berkeley Benchmark (BSDS). [sent-41, score-0.196]

20 computed gradients on eigenvectors of the afﬁnity graph and combined them with local cues [2]. [sent-54, score-0.175]

21 [5] learned boosted trees on generic features such as gradients and Haar wavelets, Kokkinos used SIFT features on edgels [12], and Prasad et. [sent-57, score-0.229]

22 A major difference of our work is the use of oriented gradients: comparing to directly classifying a patch, measuring contrast between oriented half-discs is a much easier problem and can be effectively learned. [sent-61, score-0.218]

23 Similar to deep network approaches [11, 14], recent works tried to avoid feature engineering and employed sparse coding of image patches to learn features from “scratch”, for texture analysis [15] and object recognition [30, 3]. [sent-64, score-0.354]

24 In particular, Orthogonal Matching Pursuit [18] is a greedy algorithm that incrementally ﬁnds sparse codes, and K-SVD is also efﬁcient and popular for dictionary learning. [sent-65, score-0.177]

25 used matching pursuit and K-SVD to learn features in a coding hierarchy [3] and are extending their approach to RGB-D data [4]. [sent-68, score-0.221]

26 In-depth studies of contour and segmentation problems for depth data are much in need given the fast growing interests in RGB-D perception. [sent-77, score-0.601]

27 3 Contour Detection using Sparse Code Gradients We start by examining the processing pipeline of Global Pb (gPb) [2], a highly inﬂuential and widely used system for contour detection. [sent-78, score-0.363]

28 The gPb contour detection has two stages: local contrast estimation at multiple scales, and globalization of the local cues using spectral grouping. [sent-79, score-0.703]

29 Originally developed in [17], this set of features use relatively simple pixel representations (histograms of brightness, color and textons) and similarity functions (chi-square distance, manually chosen), comparing to recent advances in using rich representations for high-level recognition (e. [sent-81, score-0.389]

30 We set out to show that both the pixel representation and the aggregation of pixel information in local neighborhoods can be much improved and, to a large extent, learned from and adapted to input data. [sent-84, score-0.204]

31 1 we show how to use Orthogonal Matching Pursuit [18] and K-SVD [1], efﬁcient sparse coding and dictionary learning algorithms that readily apply to low-level vision, to extract sparse codes at every pixel. [sent-86, score-0.39]

32 We show learned dictionaries for a number of channels that exhibit different characteristics: grayscale/luminance, chromaticity (ab), depth, and surface normal. [sent-88, score-0.237]

33 2 we show how the pixel-level sparse codes can be integrated through multi-scale pooling into a rich representation of oriented local neighborhoods. [sent-90, score-0.414]

34 K-SVD [1] is a popular dictionary learning algorithm that generalizes K-Means and learns dictionaries of codewords from unsupervised data. [sent-94, score-0.211]

35 Given a set of image patches Y = [y1 , · · · , yn ], K-SVD jointly ﬁnds a dictionary D = [d1 , · · · , dm ] and an associated sparse code matrix X = [x1 , · · · , xn ] by minimizing the reconstruction error min Y − DX D,X 2 F s. [sent-95, score-0.353]

36 Given the dictionary D, optimizing the sparse code matrix X can be decoupled to sub-problems, each solved with Orthogonal Matching Pursuit (OMP) [18], a greedy algorithm for ﬁnding sparse codes. [sent-99, score-0.325]

37 Given the codes X, the dictionary D and its associated sparse coefﬁcients are updated sequentially by singular value decomposition. [sent-100, score-0.25]

38 Once the dictionary D is learned, we again use the Orthogonal Matching Pursuit (OMP) algorithm to compute sparse codes at every pixel. [sent-102, score-0.25]

39 For a typical BSDS image of resolution 321x481, the sparse code extraction is efﬁcient and takes 1∼2 seconds. [sent-104, score-0.236]

40 One advantage of unsupervised dictionary learning is that it readily applies to novel sensor data, such as the color and depth frames from a Kinect-style RGB-D camera. [sent-106, score-0.5]

41 We learn K-SVD dictionaries up to four channels of color and depth: grayscale for luminance, chromaticity ab for color in the Lab space, depth (distance to camera) and surface normal (3-dim). [sent-107, score-0.916]

42 These dictionaries are interesting 3 (a) Grayscale (b) Chromaticity (ab) (c) Depth (d) Surface normal Figure 2: K-SVD dictionaries learned for four different channels: grayscale and chromaticity (in ab) for an RGB image (a,b), and depth and surface normal for a depth image (c,d). [sent-110, score-0.889]

43 to look at and qualitatively distinctive: for example, the surface normal codewords tend to be more smooth due to ﬂat surfaces, the depth codewords are also more smooth but with speckles, and the chromaticity codewords respect the opponent color pairs. [sent-116, score-0.629]

44 Over decades of research on contour detection and related topics, a number of fundamental observations have been made, repeatedly: (1) contrast is the key to differentiate contour vs non-contour; (2) orientation is important for respecting contour continuity; and (3) multi-scale is useful. [sent-120, score-1.324]

45 Each pixel is presented with sparse codes extracted from a small patch (5-by-5) around it. [sent-123, score-0.236]

46 a hybrid of average and max pooling) to generate its representation |xi1 | F (N ) = i∈N I|xi1 |>0 , · · · , i∈N |xim | i∈N I|xim |>0 (2) i∈N where xij is the j-th entry of the sparse code xi , and I is the indicator function whether xij is nonzero. [sent-130, score-0.2]

47 We rotate the image (after sparse coding) and use integral images for fast computations (on both |xij | and |xij | > 0, whose costs are independent of the size of N . [sent-131, score-0.181]

48 Since the magnitude of sparse codes varies over a wide range due to local variations in illumination as well as occlusion, this step makes the appearance features robust to such variations and increases their discriminative power, as commonly done in both contour detection and object recognition. [sent-134, score-0.77]

49 The concatenated feature Dp (non-negative) provides multi-scale contrast information for classifying whether p is a contour location for a particular orientation. [sent-141, score-0.387]

50 Empirically, we ﬁnd that the double power transform works much better than either no transform or a single power transform α, as sometimes done in other classiﬁcation contexts. [sent-145, score-0.362]

51 One plausible intuition for a double power transform is that the optimal exponent α may be different across feature dimensions. [sent-149, score-0.18]

52 4 Experiments We use the evaluation framework of, and extensively compare to, the publicly available Global Pb (gPb) system [2], widely used as the state of the art for contour detection1 . [sent-155, score-0.363]

53 All the results reported on gPb are from running the gPb contour detection and evaluation codes (with default parameters), and accuracies are veriﬁed against the published results in [2]. [sent-156, score-0.551]

54 The gPb evaluation includes a number of criteria, including precision-recall (P/R) curves from contour matching (Fig. [sent-157, score-0.42]

55 4), F-measures computed from P/R (Table 1,2,3) with a ﬁxed contour threshold (ODS) or per-image thresholds (OIS), as well as average precisions (AP) from the P/R curves. [sent-158, score-0.363]

56 The main dataset we use is the BSDS500 benchmark [2], an extension of the original BSDS300 benchmark and commonly used for contour evaluation. [sent-160, score-0.419]

57 We conduct both color and grayscale experiments (where we convert the BSDS500 images to grayscale and retain the groundtruth). [sent-162, score-0.423]

58 For RGB-D contour detection, we use the NYU Depth dataset (v2) [27], which includes 1449 pairs of color and depth frames of resolution 480x640, with groundtruth semantic regions. [sent-167, score-0.829]

59 For positive data, we sample groundtruth contour locations and estimate the orientations at these locations using groundtruth. [sent-172, score-0.508]

60 5 to 2 1 In this work we focus on contour detection and do not address how to derive segmentations from contours. [sent-176, score-0.478]

61 84 150 1 2 3 (b) 4 5 6 sparsity level 7 8 (c) Figure 3: Analysis of our sparse code gradients, using average precision of classiﬁcation on sampled boundaries. [sent-196, score-0.19]

62 2 0 Table 1: F-measure evaluation on the BSDS500 benchmark [2], comparing to gPb on grayscale and color images, both for local contour detection as well as for global detection (i. [sent-236, score-0.942]

63 9 1 Recall Figure 4: Precision-recall curves of SCG vs gPb on BSDS500, for grayscale and color images. [sent-248, score-0.319]

64 In particular, we want to understand how the choices in the local sparse coding affect contour classiﬁcation. [sent-258, score-0.546]

65 The numbers reported are intermediate results, namely the mean of average precision of four oriented gradient classiﬁer (0, 45, 90, 135 degrees) on sampled locations (grayscale unless otherwise noted, on validation). [sent-261, score-0.182]

66 The dictionary size has a minor impact, and there is a small (yet observable) beneﬁt to use dictionaries larger than 75, particularly for diagonal orientations (45- and 135-deg). [sent-266, score-0.204]

67 3(c), we see that for grayscale only, K = 1 (normalized nearest neighbor) does quite well; on the other hand, color needs a larger K, possibly because ab is a nonlinear space. [sent-269, score-0.327]

68 ) We also empirically evaluate the double power transform vs single power transform vs no transform. [sent-274, score-0.377]

69 A double power transform (with exponents 6 gPb SCG gPb SCG MSRC2 ODS OIS AP . [sent-280, score-0.18]

70 27 gPb (color) SCG (color) gPb (depth) SCG (depth) gPb (RGB-D) SCG (RGB-D) Table 2: F-measure evaluation comparing our SCG approach to gPb on two additional image datasets with contour groundtruth: MSRC2 [26] and PASCAL2008 [6]. [sent-292, score-0.42]

71 54 Table 3: F-measure evaluation on RGB-D contour detection using the NYU dataset (v2) [27]. [sent-311, score-0.478]

72 We compare to gPb on using color image only, depth only, as well as color+depth. [sent-312, score-0.431]

73 windmills, faces, ﬁsh ﬁns) while at the same time achieving higher precision on large-scale contours (e. [sent-317, score-0.185]

74 900, which translates to a large improvement in contour detection accuracy. [sent-324, score-0.478]

75 We conduct four sets of experiments, using color or grayscale images, with or without the globalization component (for which we use exactly the same setup as in gPb). [sent-328, score-0.349]

76 While our scale range is similar to that of gPb, the multi-scale pooling scheme allows the ﬂexibility of learning the balance of scales separately for each code word, which may help detecting the details. [sent-343, score-0.182]

77 The improvement on MSRC2 is much larger, partly because the images are smaller, hence the contours are smaller in scale and may be over-smoothed in gPb. [sent-347, score-0.185]

78 7 Figure 6: Examples of RGB-D contour detection on the NYU dataset (v2) [27]. [sent-350, score-0.478]

79 Color is good picking up details such as photos on the wall, and depth is useful where color is uniform (e. [sent-352, score-0.374]

80 A median ﬁltering is applied to remove double contours (boundaries from two adjacent regions) within 3 pixels. [sent-359, score-0.208]

81 For RGB-D baseline, we use a simple adaptation of gPb: the depth values are in meters and used directly as a grayscale image in gPb gradient computation. [sent-360, score-0.38]

82 We use a linear combination to put (soft) color and depth gradients together in gPb before non-max suppression, with the weight set from validation. [sent-361, score-0.484]

83 Table 3 lists the precision-recall evaluations of SCG vs gPb for RGB-D contour detection. [sent-362, score-0.404]

84 Our approach learns the low-level representations of depth data fully automatically and does not require any manual tweaking. [sent-366, score-0.257]

85 We also achieve a much larger boost by combining color and depth, demonstrating that color and depth channels contain complementary information and are both critical for RGB-D contour detection. [sent-367, score-0.944]

86 Qualitatively, it is easy to see that RGB-D combines the strengths of color and depth and is a promising direction for contour and segmentation tasks and indoor scene analysis in general [22]. [sent-368, score-0.83]

87 There are plenty of such cases where color alone or depth alone would fail to extract contours for meaningful parts of the scenes, and color+depth would succeed. [sent-371, score-0.517]

88 5 Discussions In this work we successfully showed how to learn and code local representations to extract contours in natural images. [sent-372, score-0.286]

89 Our approach combined the proven concept of oriented gradients with powerful representations that are automatically learned through sparse coding. [sent-373, score-0.369]

90 Sparse Code Gradients (SCG) performed signiﬁcantly better than hand-designed features that were in use for a decade, and pushed contour detection much closer to human-level accuracy as illustrated on the BSDS500 benchmark. [sent-374, score-0.513]

91 Global Pb [2]), we maintain the high dimensional representation from pooling oriented neighborhoods and do not collapse them prematurely (such as computing chi-square distance at each scale). [sent-377, score-0.249]

92 This passes a richer set of information into learning contour classiﬁcation, where a double power transform effectively codes the features for linear SVMs. [sent-378, score-0.651]

93 discriminative dictionaries in [16]), our uses of multi-scale pooling and oriented gradients lead to much higher classiﬁcation accuracies. [sent-381, score-0.389]

94 Our work opens up future possibilities for learning contour detection and segmentation. [sent-382, score-0.478]

95 As we illustrated, there is a lot of information locally that is waiting to be extracted, and a learning approach such as sparse coding provides a principled way to do so, where rich representations can be automatically constructed and adapted. [sent-383, score-0.225]

96 Rgb-d mapping: Using depth cameras for dense 3d modeling of indoor environments. [sent-457, score-0.263]

97 Discriminative sparse image models for class-speciﬁc edge detection and image interpretation. [sent-497, score-0.311]

98 Realtime human pose recognition in parts from single depth images. [sent-557, score-0.23]

99 Linear spatial pyramid matching using sparse coding for image classiﬁcation. [sent-585, score-0.254]

100 Learning image representations from the pixel level via hierarchical sparse coding. [sent-591, score-0.226]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('gpb', 0.615), ('contour', 0.363), ('scg', 0.33), ('depth', 0.199), ('color', 0.175), ('contours', 0.143), ('ns', 0.131), ('detection', 0.115), ('gradients', 0.11), ('pb', 0.107), ('grayscale', 0.103), ('oriented', 0.097), ('dictionary', 0.095), ('nyu', 0.094), ('pooling', 0.092), ('sparse', 0.082), ('codes', 0.073), ('pursuit', 0.071), ('globalization', 0.071), ('dictionaries', 0.069), ('transform', 0.067), ('chromaticity', 0.067), ('ods', 0.067), ('ois', 0.067), ('code', 0.066), ('double', 0.065), ('groundtruth', 0.061), ('coding', 0.058), ('ren', 0.058), ('image', 0.057), ('matching', 0.057), ('orientation', 0.055), ('bsds', 0.053), ('pixel', 0.053), ('patches', 0.053), ('dp', 0.053), ('gray', 0.051), ('ab', 0.049), ('power', 0.048), ('surface', 0.047), ('codewords', 0.047), ('local', 0.043), ('images', 0.042), ('precision', 0.042), ('bo', 0.041), ('vs', 0.041), ('orientations', 0.04), ('segmentation', 0.039), ('cameras', 0.039), ('orthogonal', 0.038), ('object', 0.038), ('features', 0.035), ('kinect', 0.035), ('representations', 0.034), ('svm', 0.034), ('omp', 0.033), ('neighborhoods', 0.033), ('ap', 0.032), ('channels', 0.032), ('resolution', 0.031), ('sensor', 0.031), ('cvpr', 0.031), ('shotton', 0.031), ('recognition', 0.031), ('scene', 0.029), ('fowlkes', 0.029), ('benchmark', 0.028), ('eccv', 0.028), ('patch', 0.028), ('rich', 0.027), ('discs', 0.027), ('dollar', 0.027), ('edgels', 0.027), ('prematurely', 0.027), ('rgbd', 0.027), ('xim', 0.027), ('brightness', 0.026), ('xij', 0.026), ('indoor', 0.025), ('classi', 0.025), ('contrast', 0.024), ('scales', 0.024), ('automatically', 0.024), ('fitzgibbon', 0.024), ('textons', 0.024), ('visualized', 0.023), ('spectral', 0.022), ('learned', 0.022), ('arbelaez', 0.022), ('disc', 0.022), ('luminance', 0.022), ('cues', 0.022), ('mairal', 0.022), ('locations', 0.022), ('discriminative', 0.021), ('gradient', 0.021), ('half', 0.021), ('prasad', 0.02), ('suppression', 0.02), ('iser', 0.02)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 101 nips-2012-Discriminatively Trained Sparse Code Gradients for Contour Detection

Author: Ren Xiaofeng, Liefeng Bo

2 0.20202087 106 nips-2012-Dynamical And-Or Graph Learning for Object Shape Modeling and Detection

Author: Xiaolong Wang, Liang Lin

Abstract: This paper studies a novel discriminative part-based model to represent and recognize object shapes with an “And-Or graph”. We deﬁne this model consisting of three layers: the leaf-nodes with collaborative edges for localizing local parts, the or-nodes specifying the switch of leaf-nodes, and the root-node encoding the global veriﬁcation. A discriminative learning algorithm, extended from the CCCP [23], is proposed to train the model in a dynamical manner: the model structure (e.g., the conﬁguration of the leaf-nodes associated with the or-nodes) is automatically determined with optimizing the multi-layer parameters during the iteration. The advantages of our method are two-fold. (i) The And-Or graph model enables us to handle well large intra-class variance and background clutters for object shape detection from images. (ii) The proposed learning algorithm is able to obtain the And-Or graph representation without requiring elaborate supervision and initialization. We validate the proposed method on several challenging databases (e.g., INRIA-Horse, ETHZ-Shape, and UIUC-People), and it outperforms the state-of-the-arts approaches. 1

3 0.13137569 87 nips-2012-Convolutional-Recursive Deep Learning for 3D Object Classification

Author: Richard Socher, Brody Huval, Bharath Bath, Christopher D. Manning, Andrew Y. Ng

Abstract: Recent advances in 3D sensing technologies make it possible to easily record color and depth images which together can improve object recognition. Most current methods rely on very well-designed features for this new 3D modality. We introduce a model based on a combination of convolutional and recursive neural networks (CNN and RNN) for learning features and classifying RGB-D images. The CNN layer learns low-level translationally invariant features which are then given as inputs to multiple, ﬁxed-tree RNNs in order to compose higher order features. RNNs can be seen as combining convolution and pooling into one efﬁcient, hierarchical operation. Our main result is that even RNNs with random weights compose powerful features. Our model obtains state of the art performance on a standard RGB-D object dataset while being more accurate and faster during training and testing than comparable architectures such as two-layer CNNs. 1

4 0.1186135 92 nips-2012-Deep Representations and Codes for Image Auto-Annotation

Author: Ryan Kiros, Csaba Szepesvári

Abstract: The task of image auto-annotation, namely assigning a set of relevant tags to an image, is challenging due to the size and variability of tag vocabularies. Consequently, most existing algorithms focus on tag assignment and ﬁx an often large number of hand-crafted features to describe image characteristics. In this paper we introduce a hierarchical model for learning representations of standard sized color images from the pixel level, removing the need for engineered feature representations and subsequent feature selection for annotation. We benchmark our model on the STL-10 recognition dataset, achieving state-of-the-art performance. When our features are combined with TagProp (Guillaumin et al.), we compete with or outperform existing annotation approaches that use over a dozen distinct handcrafted image descriptors. Furthermore, using 256-bit codes and Hamming distance for training TagProp, we exchange only a small reduction in performance for efﬁcient storage and fast comparisons. Self-taught learning is used in all of our experiments and deeper architectures always outperform shallow ones. 1

5 0.097402193 344 nips-2012-Timely Object Recognition

Author: Sergey Karayev, Tobias Baumgartner, Mario Fritz, Trevor Darrell

Abstract: In a large visual multi-class detection framework, the timeliness of results can be crucial. Our method for timely multi-class detection aims to give the best possible performance at any single point after a start time; it is terminated at a deadline time. Toward this goal, we formulate a dynamic, closed-loop policy that infers the contents of the image in order to decide which detector to deploy next. In contrast to previous work, our method signiﬁcantly diverges from the predominant greedy strategies, and is able to learn to take actions with deferred values. We evaluate our method with a novel timeliness measure, computed as the area under an Average Precision vs. Time curve. Experiments are conducted on the PASCAL VOC object detection dataset. If execution is stopped when only half the detectors have been run, our method obtains 66% better AP than a random ordering, and 14% better performance than an intelligent baseline. On the timeliness measure, our method obtains at least 11% better performance. Our method is easily extensible, as it treats detectors and classiﬁers as black boxes and learns from execution traces using reinforcement learning. 1

6 0.093152583 360 nips-2012-Visual Recognition using Embedded Feature Selection for Curvature Self-Similarity

7 0.091968499 258 nips-2012-Online L1-Dictionary Learning with Application to Novel Document Detection

8 0.083217613 197 nips-2012-Learning with Recursive Perceptual Representations

9 0.075962305 91 nips-2012-Deep Neural Networks Segment Neuronal Membranes in Electron Microscopy Images

10 0.074724868 62 nips-2012-Burn-in, bias, and the rationality of anchoring

11 0.074724868 116 nips-2012-Emergence of Object-Selective Features in Unsupervised Feature Learning

12 0.0686386 158 nips-2012-ImageNet Classification with Deep Convolutional Neural Networks

13 0.067587391 90 nips-2012-Deep Learning of Invariant Features via Simulated Fixations in Video

14 0.065659821 357 nips-2012-Unsupervised Template Learning for Fine-Grained Object Recognition

15 0.065037243 210 nips-2012-Memorability of Image Regions

16 0.063901439 201 nips-2012-Localizing 3D cuboids in single-view images

17 0.063171878 81 nips-2012-Context-Sensitive Decision Forests for Object Detection

18 0.062578239 40 nips-2012-Analyzing 3D Objects in Cluttered Images

19 0.062294956 8 nips-2012-A Generative Model for Parts-based Object Segmentation

20 0.060205586 193 nips-2012-Learning to Align from Scratch

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.14), (1, 0.042), (2, -0.171), (3, -0.025), (4, 0.101), (5, -0.051), (6, 0.002), (7, -0.063), (8, 0.037), (9, -0.008), (10, -0.025), (11, 0.049), (12, 0.043), (13, -0.014), (14, -0.012), (15, 0.058), (16, 0.025), (17, -0.029), (18, -0.041), (19, -0.025), (20, -0.012), (21, -0.02), (22, 0.027), (23, 0.019), (24, -0.074), (25, 0.041), (26, -0.077), (27, 0.049), (28, 0.025), (29, 0.067), (30, -0.005), (31, 0.021), (32, -0.001), (33, -0.057), (34, 0.072), (35, 0.025), (36, 0.073), (37, 0.091), (38, 0.02), (39, -0.076), (40, 0.047), (41, -0.036), (42, -0.049), (43, 0.033), (44, -0.01), (45, 0.009), (46, -0.118), (47, -0.091), (48, -0.079), (49, 0.031)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9360047 101 nips-2012-Discriminatively Trained Sparse Code Gradients for Contour Detection

Author: Ren Xiaofeng, Liefeng Bo

2 0.71111888 92 nips-2012-Deep Representations and Codes for Image Auto-Annotation

Author: Ryan Kiros, Csaba Szepesvári

3 0.70309055 357 nips-2012-Unsupervised Template Learning for Fine-Grained Object Recognition

Author: Shulin Yang, Liefeng Bo, Jue Wang, Linda G. Shapiro

Abstract: Fine-grained recognition refers to a subordinate level of recognition, such as recognizing different species of animals and plants. It differs from recognition of basic categories, such as humans, tables, and computers, in that there are global similarities in shape and structure shared cross different categories, and the differences are in the details of object parts. We suggest that the key to identifying the ﬁne-grained differences lies in ﬁnding the right alignment of image regions that contain the same object parts. We propose a template model for the purpose, which captures common shape patterns of object parts, as well as the cooccurrence relation of the shape patterns. Once the image regions are aligned, extracted features are used for classiﬁcation. Learning of the template model is efﬁcient, and the recognition results we achieve signiﬁcantly outperform the stateof-the-art algorithms. 1

4 0.70270491 210 nips-2012-Memorability of Image Regions

Author: Aditya Khosla, Jianxiong Xiao, Antonio Torralba, Aude Oliva

Abstract: While long term human visual memory can store a remarkable amount of visual information, it tends to degrade over time. Recent works have shown that image memorability is an intrinsic property of an image that can be reliably estimated using state-of-the-art image features and machine learning algorithms. However, the class of features and image information that is forgotten has not been explored yet. In this work, we propose a probabilistic framework that models how and which local regions from an image may be forgotten using a data-driven approach that combines local and global images features. The model automatically discovers memorability maps of individual images without any human annotation. We incorporate multiple image region attributes in our algorithm, leading to improved memorability prediction of images as compared to previous works. 1

5 0.66755837 87 nips-2012-Convolutional-Recursive Deep Learning for 3D Object Classification

Author: Richard Socher, Brody Huval, Bharath Bath, Christopher D. Manning, Andrew Y. Ng

6 0.65863252 360 nips-2012-Visual Recognition using Embedded Feature Selection for Curvature Self-Similarity

7 0.65165222 106 nips-2012-Dynamical And-Or Graph Learning for Object Shape Modeling and Detection

8 0.58357829 202 nips-2012-Locally Uniform Comparison Image Descriptor

9 0.57880199 176 nips-2012-Learning Image Descriptors with the Boosting-Trick

10 0.56463295 201 nips-2012-Localizing 3D cuboids in single-view images

11 0.55118746 90 nips-2012-Deep Learning of Invariant Features via Simulated Fixations in Video

12 0.53909278 159 nips-2012-Image Denoising and Inpainting with Deep Neural Networks

13 0.53131032 146 nips-2012-Graphical Gaussian Vector for Image Categorization

14 0.51370919 91 nips-2012-Deep Neural Networks Segment Neuronal Membranes in Electron Microscopy Images

15 0.50884104 8 nips-2012-A Generative Model for Parts-based Object Segmentation

16 0.50327981 158 nips-2012-ImageNet Classification with Deep Convolutional Neural Networks

17 0.50169659 303 nips-2012-Searching for objects driven by context

18 0.49545854 81 nips-2012-Context-Sensitive Decision Forests for Object Detection

19 0.49508825 1 nips-2012-3D Object Detection and Viewpoint Estimation with a Deformable 3D Cuboid Model

20 0.48936269 193 nips-2012-Learning to Align from Scratch

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.034), (17, 0.013), (21, 0.022), (38, 0.068), (42, 0.029), (44, 0.01), (54, 0.037), (55, 0.034), (72, 0.25), (74, 0.128), (76, 0.102), (80, 0.062), (92, 0.117)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.79274791 101 nips-2012-Discriminatively Trained Sparse Code Gradients for Contour Detection

Author: Ren Xiaofeng, Liefeng Bo

2 0.70621544 107 nips-2012-Effective Split-Merge Monte Carlo Methods for Nonparametric Models of Sequential Data

Author: Michael C. Hughes, Erik B. Sudderth, Emily B. Fox

Abstract: Applications of Bayesian nonparametric methods require learning and inference algorithms which efﬁciently explore models of unbounded complexity. We develop new Markov chain Monte Carlo methods for the beta process hidden Markov model (BP-HMM), enabling discovery of shared activity patterns in large video and motion capture databases. By introducing split-merge moves based on sequential allocation, we allow large global changes in the shared feature structure. We also develop data-driven reversible jump moves which more reliably discover rare or unique behaviors. Our proposals apply to any choice of conjugate likelihood for observed data, and we show success with multinomial, Gaussian, and autoregressive emission models. Together, these innovations allow tractable analysis of hundreds of time series, where previous inference required clever initialization and lengthy burn-in periods for just six sequences. 1

3 0.70249289 9 nips-2012-A Geometric take on Metric Learning

Author: Søren Hauberg, Oren Freifeld, Michael J. Black

Abstract: Multi-metric learning techniques learn local metric tensors in different parts of a feature space. With such an approach, even simple classiﬁers can be competitive with the state-of-the-art because the distance measure locally adapts to the structure of the data. The learned distance measure is, however, non-metric, which has prevented multi-metric learning from generalizing to tasks such as dimensionality reduction and regression in a principled way. We prove that, with appropriate changes, multi-metric learning corresponds to learning the structure of a Riemannian manifold. We then show that this structure gives us a principled way to perform dimensionality reduction and regression according to the learned metrics. Algorithmically, we provide the ﬁrst practical algorithm for computing geodesics according to the learned metrics, as well as algorithms for computing exponential and logarithmic maps on the Riemannian manifold. Together, these tools let many Euclidean algorithms take advantage of multi-metric learning. We illustrate the approach on regression and dimensionality reduction tasks that involve predicting measurements of the human body from shape data. 1 Learning and Computing Distances Statistics relies on measuring distances. When the Euclidean metric is insufﬁcient, as is the case in many real problems, standard methods break down. This is a key motivation behind metric learning, which strives to learn good distance measures from data. In the most simple scenarios a single metric tensor is learned, but in recent years, several methods have proposed learning multiple metric tensors, such that different distance measures are applied in different parts of the feature space. This has proven to be a very powerful approach for classiﬁcation tasks [1, 2], but the approach has not generalized to other tasks. Here we consider the generalization of Principal Component Analysis (PCA) and linear regression; see Fig. 1 for an illustration of our approach. The main problem with generalizing multi-metric learning is that it is based on assumptions that make the feature space both non-smooth and non-metric. Speciﬁcally, it is often assumed that straight lines form geodesic curves and that the metric tensor stays constant along these lines. These assumptions are made because it is believed that computing the actual geodesics is intractable, requiring a discretization of the entire feature space [3]. We solve these problems by smoothing the transitions between different metric tensors, which ensures a metric space where geodesics can be computed. In this paper, we consider the scenario where the metric tensor at a given point in feature space is deﬁned as the weighted average of a set of learned metric tensors. In this model, we prove that the feature space becomes a chart for a Riemannian manifold. This ensures a metric feature space, i.e. dist(x, y) = 0 ⇔ x = y , dist(x, y) = dist(y, x) (symmetry), (1) dist(x, z) ≤ dist(x, y) + dist(y, z) (triangle inequality). To compute statistics according to the learned metric, we need to be able to compute distances, which implies that we need to compute geodesics. Based on the observation that geodesics are 1 (a) Local Metrics & Geodesics (b) Tangent Space Representation (c) First Principal Geodesic Figure 1: Illustration of Principal Geodesic Analysis. (a) Geodesics are computed between the mean and each data point. (b) Data is mapped to the Euclidean tangent space and the ﬁrst principal component is computed. (c) The principal component is mapped back to the feature space. smooth curves in Riemannian spaces, we derive an algorithm for computing geodesics that only requires a discretization of the geodesic rather than the entire feature space. Furthermore, we show how to compute the exponential and logarithmic maps of the manifold. With this we can map any point back and forth between a Euclidean tangent space and the manifold. This gives us a general strategy for incorporating the learned metric tensors in many Euclidean algorithms: map the data to the tangent of the manifold, perform the Euclidean analysis and map the results back to the manifold. Before deriving the algorithms (Sec. 3) we set the scene by an analysis of the shortcomings of current state-of-the-art methods (Sec. 2), which motivate our ﬁnal model. The model is general and can be used for many problems. Here we illustrate it with several challenging problems in 3D body shape modeling and analysis (Sec. 4). All proofs can be found in the supplementary material along with algorithmic details and further experimental results. 2 Background and Related Work Single-metric learning learns a metric tensor, M, such that distances are measured as dist2 (xi , xj ) = xi − xj 2 M ≡ (xi − xj )T M(xi − xj ) , (2) where M is a symmetric and positive deﬁnite D × D matrix. Classic approaches for ﬁnding such a metric tensor include PCA, where the metric is given by the inverse covariance matrix of the training data; and linear discriminant analysis (LDA), where the metric tensor is M = S−1 SB S−1 , with Sw W W and SB being the within class scatter and the between class scatter respectively [9]. A more recent approach tries to learn a metric tensor from triplets of data points (xi , xj , xk ), where the metric should obey the constraint that dist(xi , xj ) < dist(xi , xk ). Here the constraints are often chosen such that xi and xj belong to the same class, while xi and xk do not. Various relaxed versions of this idea have been suggested such that the metric can be learned by solving a semi-deﬁnite or a quadratic program [1, 2, 4–8]. Among the most popular approaches is the Large Margin Nearest Neighbor (LMNN) classiﬁer [5], which ﬁnds a linear transformation that satisﬁes local distance constraints, making the approach suitable for multi-modal classes. For many problems, a single global metric tensor is not enough, which motivates learning several local metric tensors. The classic work by Hastie and Tibshirani [9] advocates locally learning metric tensors according to LDA and using these as part of a kNN classiﬁer. In a somewhat similar fashion, Weinberger and Saul [5] cluster the training data and learn a separate metric tensor for each cluster using LMNN. A more extreme point of view was taken by Frome et al. [1, 2], who learn a diagonal metric tensor for every point in the training set, such that distance rankings are preserved. Similarly, Malisiewicz and Efros [6] ﬁnd a diagonal metric tensor for each training point such that the distance to a subset of the training data from the same class is kept small. Once a set of metric tensors {M1 , . . . , MR } has been learned, the distance dist(a, b) is measured according to (2) where “the nearest” metric tensor is used, i.e. R M(x) = r=1 wr (x) ˜ Mr , where wr (x) = ˜ ˜ j wj (x) 1 0 x − xr 2 r ≤ x − xj M otherwise 2 Mj , ∀j , (3) where x is either a or b depending on the algorithm. Note that this gives a non-metric distance function as it is not symmetric. To derive this equation, it is necessary to assume that 1) geodesics 2 −8 −8 Assumed Geodesics Location of Metric Tensors Test Points −6 −8 Actual Geodesics Location of Metric Tensors Test Points −6 Riemannian Geodesics Location of Metric Tensors Test Points −6 −4 −4 −4 −2 −2 −2 0 0 0 2 2 2 4 4 4 6 −8 6 −8 −6 −4 −2 0 (a) 2 4 6 −6 −4 −2 0 2 4 6 6 −8 −6 (b) −4 −2 (c) 0 2 4 6 (d) Figure 2: (a)–(b) An illustrative example where straight lines do not form geodesics and where the metric tensor does not stay constant along lines; see text for details. The background color is proportional to the trace of the metric tensor, such that light grey corresponds to regions where paths are short (M1 ), and dark grey corresponds to regions they are long (M2 ). (c) The suggested geometric model along with the geodesics. Again, background colour is proportional to the trace of the metric tensor; the colour scale is the same is used in (a) and (b). (d) An illustration of the exponential and logarithmic maps. form straight lines, and 2) the metric tensor stays constant along these lines [3]. Both assumptions are problematic, which we illustrate with a simple example in Fig. 2a–c. Assume we are given two metric tensors M1 = 2I and M2 = I positioned at x1 = (2, 2)T and x2 = (4, 4)T respectively. This gives rise to two regions in feature space in which x1 is nearest in the ﬁrst and x2 is nearest in the second, according to (3). This is illustrated in Fig. 2a. In the same ﬁgure, we also show the assumed straight-line geodesics between selected points in space. As can be seen, two of the lines goes through both regions, such that the assumption of constant metric tensors along the line is violated. Hence, it would seem natural to measure the length of the line, by adding the length of the line segments which pass through the different regions of feature space. This was suggested by Ramanan and Baker [3] who also proposed a polynomial time algorithm for measuring these line lengths. This gives a symmetric distance function. Properly computing line lengths according to the local metrics is, however, not enough to ensure that the distance function is metric. As can be seen in Fig. 2a the straight line does not form a geodesic as a shorter path can be found by circumventing the region with the “expensive” metric tensor M1 as illustrated in Fig. 2b. This issue makes it trivial to construct cases where the triangle inequality is violated, which again makes the line length measure non-metric. In summary, if we want a metric feature space, we can neither assume that geodesics are straight lines nor that the metric tensor stays constant along such lines. In practice, good results have been reported using (3) [1,3,5], so it seems obvious to ask: is metricity required? For kNN classiﬁers this does not appear to be the case, with many successes based on dissimilarities rather than distances [10]. We, however, want to generalize PCA and linear regression, which both seek to minimize the reconstruction error of points projected onto a subspace. As the notion of projection is hard to deﬁne sensibly in non-metric spaces, we consider metricity essential. In order to build a model with a metric feature space, we change the weights in (3) to be smooth functions. This impose a well-behaved geometric structure on the feature space, which we take advantage of in order to perform statistical analysis according to the learned metrics. However, ﬁrst we review the basics of Riemannian geometry as this provides the theoretical foundation of our work. 2.1 Geodesics and Riemannian Geometry We start by deﬁning Riemannian manifolds, which intuitively are smoothly curved spaces equipped with an inner product. Formally, they are smooth manifolds endowed with a Riemannian metric [11]: Deﬁnition A Riemannian metric M on a manifold M is a smoothly varying inner product < a, b >x = aT M(x)b in the tangent space Tx M of each point x ∈ M . 3 Often Riemannian manifolds are represented by a chart; i.e. a parameter space for the curved surface. An example chart is the spherical coordinate system often used to represent spheres. While such charts are often ﬂat spaces, the curvature of the manifold arises from the smooth changes in the metric. On a Riemannian manifold M, the length of a smooth curve c : [0, 1] → M is deﬁned as the integral of the norm of the tangent vector (interpreted as speed) along the curve: 1 Length(c) = 1 c (λ) M(c(λ)) dλ c (λ)T M(c(λ))c (λ)dλ , = (4) 0 0 where c denotes the derivative of c and M(c(λ)) is the metric tensor at c(λ). A geodesic curve is then a length-minimizing curve connecting two given points x and y, i.e. (5) cgeo = arg min Length(c) with c(0) = x and c(1) = y . c The distance between x and y is deﬁned as the length of the geodesic. Given a tangent vector v ∈ Tx M, there exists a unique geodesic cv (t) with initial velocity v at x. The Riemannian exponential map, Expx , maps v to a point on the manifold along the geodesic cv at t = 1. This mapping preserves distances such that dist(cv (0), cv (1)) = v . The inverse of the exponential map is the Riemannian logarithmic map denoted Logx . Informally, the exponential and logarithmic maps move points back and forth between the manifold and the tangent space while preserving distances (see Fig. 2d for an illustration). This provides a general strategy for generalizing many Euclidean techniques to Riemannian domains: data points are mapped to the tangent space, where ordinary Euclidean techniques are applied and the results are mapped back to the manifold. 3 A Metric Feature Space With the preliminaries settled we deﬁne the new model. Let C = RD denote the feature space. We endow C with a metric tensor in every point x, which we deﬁne akin to (3), R M(x) = wr (x)Mr , where wr (x) = r=1 wr (x) ˜ R ˜ j=1 wj (x) , (6) with wr > 0. The only difference from (3) is that we shall not restrict ourselves to binary weight ˜ functions wr . We assume the metric tensors Mr have already been learned; Sec. 4 contain examples ˜ where they have been learned using LMNN [5] and LDA [9]. From the deﬁnition of a Riemannian metric, we trivially have the following result: Lemma 1 The space C = RD endowed with the metric tensor from (6) is a chart of a Riemannian manifold, iff the weights wr (x) change smoothly with x. Hence, by only considering smooth weight functions wr we get a well-studied geometric structure ˜ on the feature space, which ensures us that it is metric. To illustrate the implications we return to the example in Fig. 2. We change the weight functions from binary to squared exponentials, which gives the feature space shown in Fig. 2c. As can be seen, the metric tensor now changes smoothly, which also makes the geodesics smooth curves (a property we will use when computing the geodesics). It is worth noting that Ramanan and Baker [3] also consider the idea of smoothly averaging the metric tensor. They, however, only evaluate the metric tensor at the test point of their classiﬁer and then assume straight line geodesics with a constant metric tensor. Such assumptions violate the premise of a smoothly changing metric tensor and, again, the distance measure becomes non-metric. Lemma 1 shows that metric learning can be viewed as manifold learning. The main difference between our approach and techniques such as Isomap [12] is that, while Isomap learns an embedding of the data points, we learn the actual manifold structure. This gives us the beneﬁt that we can compute geodesics as well as the exponential and logarithmic maps. These provide us with mappings back and forth between the manifold and Euclidean representation of the data, which preserve distances as well as possible. The availability of such mappings is in stark contrast to e.g. Isomap. In the next section we will derive a system of ordinary differential equations (ODE’s) that geodesics in C have to satisfy, which provides us with algorithms for computing geodesics as well as exponential and logarithmic maps. With these we can generalize many Euclidean techniques. 4 3.1 Computing Geodesics, Maps and Statistics At minima of (4) we know that the Euler-Lagrange equation must hold [11], i.e. ∂L d ∂L , where L(λ, c, c ) = c (λ)T M(c(λ))c (λ) . = ∂c dλ ∂c As we have an explicit expression for the metric tensor we can compute (7) in closed form: (7) Theorem 2 Geodesic curves in C satisfy the following system of 2nd order ODE’s M(c(λ))c (λ) = − 1 ∂vec [M(c(λ))] 2 ∂c(λ) T (c (λ) ⊗ c (λ)) , (8) where ⊗ denotes the Kronecker product and vec [·] stacks the columns of a matrix into a vector [13]. Proof See supplementary material. This result holds for any smooth weight functions wr . We, however, still need to compute ∂vec[M] , ˜ ∂c which depends on the speciﬁc choice of wr . Any smooth weighting scheme is applicable, but we ˜ restrict ourselves to the obvious smooth generalization of (3) and use squared exponentials. From this assumption, we get the following result Theorem 3 For wr (x) = exp − ρ x − xr ˜ 2 ∂vec [M(c)] = ∂c the derivative of the metric tensor from (6) is R ρ R j=1 2 Mr R 2 wj ˜ T r=1 T wj (c − xj ) Mj − (c − xr ) Mr ˜ wr vec [Mr ] ˜ . (9) j=1 Proof See supplementary material. Computing Geodesics. Any geodesic curve must be a solution to (8). Hence, to compute a geodesic between x and y, we can solve (8) subject to the constraints c(0) = x and c(1) = y . (10) This is a boundary value problem, which has a smooth solution. This allows us to solve the problem numerically using a standard three-stage Lobatto IIIa formula, which provides a fourth-order accurate C 1 –continuous solution [14]. Ramanan and Baker [3] discuss the possibility of computing geodesics, but arrive at the conclusion that this is intractable based on the assumption that it requires discretizing the entire feature space. Our solution avoids discretizing the feature space by discretizing the geodesic curve instead. As this is always one-dimensional the approach remains tractable in high-dimensional feature spaces. Computing Logarithmic Maps. Once a geodesic c is found, it follows from the deﬁnition of the logarithmic map, Logx (y), that it can be computed as v = Logx (y) = c (0) Length(c) . c (0) (11) In practice, we solve (8) by rewriting it as a system of ﬁrst order ODE’s, such that we compute both c and c simultaneously (see supplementary material for details). Computing Exponential Maps. Given a starting point x on the manifold and a vector v in the tangent space, the exponential map, Expx (v), ﬁnds the unique geodesic starting at x with initial velocity v. As the geodesic must fulﬁll (8), we can compute the exponential map by solving this system of ODE’s with the initial conditions c(0) = x and c (0) = v . (12) This initial value problem has a unique solution, which we ﬁnd numerically using a standard RungeKutta scheme [15]. 5 3.1.1 Generalizing PCA and Regression At this stage, we know that the feature space is Riemannian and we know how to compute geodesics and exponential and logarithmic maps. We now seek to generalize PCA and linear regression, which becomes straightforward since solutions are available in Riemannian spaces [16, 17]. These generalizations can be summarized as mapping the data to the tangent space at the mean, performing standard Euclidean analysis in the tangent and mapping the results back. The ﬁrst step is to compute the mean value on the manifold, which is deﬁned as the point that minimizes the sum-of-squares distances to the data points. Pennec [18] provides an efﬁcient gradient descent approach for computing this point, which we also summarize in the supplementary material. The empirical covariance of a set of points is deﬁned as the ordinary Euclidean covariance in the tangent space at the mean value [18]. With this in mind, it is not surprising that the principal components of a dataset have been generalized as the geodesics starting at the mean with initial velocity corresponding to the eigenvectors of the covariance [16], γvd (t) = Expµ (tvd ) , (13) th where vd denotes the d eigenvector of the covariance. This approach is called Principal Geodesic Analysis (PGA), and the geodesic curve γvd is called the principal geodesic. An illustration of the approach can be seen in Fig. 1 and more algorithmic details are in the supplementary material. Linear regression has been generalized in a similar way [17] by performing regression in the tangent of the mean and mapping the resulting line back to the manifold using the exponential map. The idea of working in the tangent space is both efﬁcient and convenient, but comes with an element of approximation as the logarithmic map is only guarantied to preserve distances to the origin of the tangent and not between all pairs of data points. Practical experience, however, indicates that this is a good tradeoff; see [19] for a more in-depth discussion of when the approximation is suitable. 4 Experiments To illustrate the framework1 we consider an example in human body analysis, and then we analyze the scalability of the approach. But ﬁrst, to build intuition, Fig. 3a show synthetically generated data samples from two classes. We sample random points xr and learn a local LDA metric [9] by considering all data points within a radius; this locally pushes the two classes apart. We combine the local metrics using (6) and Fig. 3b show the data in the tangent space of the resulting manifold. As can be seen the two classes are now globally further apart, which shows the effect of local metrics. 4.1 Human Body Shape We consider a regression example concerning human body shape analysis. We study 986 female body laser scans from the CAESAR [20] data set; each shape is represented using the leading 35 principal components of the data learned using a SCAPE-like model [21, 22]. Each shape is associated with anthropometric measurements such as body height, shoe size, etc. We show results for shoulder to wrist distance and shoulder breadth, but results for more measurements are in the supplementary material. To predict the measurements from shape coefﬁcients, we learn local metrics and perform linear regression according to these. As a further experiment, we use PGA to reduce the dimensionality of the shape coefﬁcients according to the local metrics, and measure the quality of the reduction by performing linear regression to predict the measurements. As a baseline we use the corresponding Euclidean techniques. To learn the local metric we do the following. First we whiten the data such that the variance captured by PGA will only be due to the change of metric; this allows easy visualization of the impact of the learned metrics. We then cluster the body shapes into equal-sized clusters according to the measurement and learn a LMNN metric for each cluster [5], which we associate with the mean of each class. These push the clusters apart, which introduces variance along the directions where the measurement changes. From this we construct a Riemannian manifold according to (6), 1 Our software implementation for computing geodesics and performing manifold statistics is available at http://ps.is.tue.mpg.de/project/Smooth Metric Learning 6 30 Euclidean Model Riemannian Model 24 20 18 16 20 15 10 5 14 12 0 (a) 25 22 Running Time (sec.) Average Prediction Error 26 10 (b) 20 Dimensionality 0 0 30 50 (c) 100 Dimensionality 150 (d) 4 3 3 2 2 1 1 0 −1 −2 −3 −4 −4 −3 −2 −1 0 1 2 3 4 Shoulder breadth 20 −2 −3 Euclidean Model Riemannian Model 0 −1 25 Prediction Error 4 15 10 0 −4 −5 0 4 10 15 20 Dimensionality 16 25 30 35 17 3 3 5 5 Euclidean Model Riemannian Model 2 15 2 1 1 Prediction Error Shoulder to wrist distance Figure 3: Left panels: Synthetic data. (a) Samples from two classes along with illustratively sampled metric tensors from (6). (b) The data represented in the tangent of a manifold constructed from local LDA metrics learned at random positions. Right panels: Real data. (c) Average error of linearly predicted body measurements (mm). (d) Running time (sec) of the geodesic computation as a function of dimensionality. 0 0 −1 −2 −1 −3 14 13 12 11 −2 −4 −3 −4 −4 10 −5 −3 −2 −1 0 1 Euclidean PCA 2 3 −6 −4 9 0 −2 0 2 4 Tangent Space PCA (PGA) 6 5 10 15 20 Dimensionality 25 30 35 Regression Error Figure 4: Left: body shape data in the ﬁrst two principal components according to the Euclidean metric. Point color indicates cluster membership. Center: As on the left, but according to the Riemannian model. Right: regression error as a function of the dimensionality of the shape space; again the Euclidean metric and the Riemannian metric are compared. compute the mean value on the manifold, map the data to the tangent space at the mean and perform linear regression in the tangent space. As a ﬁrst visualization we plot the data expressed in the leading two dimensions of PGA in Fig. 4; as can be seen the learned metrics provide principal geodesics, which are more strongly related with the measurements than the Euclidean model. In order to predict the measurements from the body shape, we perform linear regression, both directly in the shape space according to the Euclidean metric and in the tangent space of the manifold corresponding to the learned metrics (using the logarithmic map from (11)). We measure the prediction error using leave-one-out cross-validation. To further illustrate the power of the PGA model, we repeat this experiment for different dimensionalities of the data. The results are plotted in Fig. 4, showing that regression according to the learned metrics outperforms the Euclidean model. To verify that the learned metrics improve accuracy, we average the prediction errors over all millimeter measurements. The result in Fig. 3c shows that much can be gained in lower dimensions by using the local metrics. To provide visual insights into the behavior of the learned metrics, we uniformly sample body shape along the ﬁrst principal geodesic (in the range ±7 times the standard deviation) according to the different metrics. The results are available as a movie in the supplementary material, but are also shown in Fig. 5. As can be seen, the learned metrics pick up intuitive relationships between body shape and the measurements, e.g. shoulder to wrist distance is related to overall body size, while shoulder breadth is related to body weight. 7 Shoulder to wrist distance Shoulder breadth Figure 5: Shapes corresponding to the mean (center) and ±7 times the standard deviations along the principal geodesics (left and right). Movies are available in the supplementary material. 4.2 Scalability The human body data set is small enough (986 samples in 35 dimensions) that computing a geodesic only takes a few seconds. To show that the current unoptimized Matlab implementation can handle somewhat larger datasets, we brieﬂy consider a dimensionality reduction task on the classic MNIST handwritten digit data set. We use the preprocessed data available with [3] where the original 28×28 gray scale images were deskewed and projected onto their leading 164 Euclidean principal components (which captures 95% of the variance in the original data). We learn one diagonal LMNN metric per class, which we associate with the mean of the class. From this we construct a Riemannian manifold from (6), compute the mean value on the manifold and compute geodesics between the mean and each data point; this is the computationally expensive part of performing PGA. Fig. 3d plots the average running time (sec) for the computation of geodesics as a function of the dimensionality of the training data. A geodesic can be computed in 100 dimensions in approximately 5 sec., whereas in 150 dimensions it takes about 30 sec. In this experiment, we train a PGA model on 60,000 data points, and test a nearest neighbor classiﬁer in the tangent space as we decrease the dimensionality of the model. Compared to a Euclidean model, this gives a modest improvement in classiﬁcation accuracy of 2.3 percent, when averaged across different dimensionalities. Plots of the results can be found in the supplementary material. 5 Discussion This work shows that multi-metric learning techniques are indeed applicable outside the realm of kNN classiﬁers. The idea of deﬁning the metric tensor at any given point as the weighted average of a ﬁnite set of learned metrics is quite natural from a modeling point of view, which is also validated by the Riemannian structure of the resulting space. This opens both a theoretical and a practical toolbox for analyzing and developing algorithms that use local metric tensors. Speciﬁcally, we show how to use local metric tensors for both regression and dimensionality reduction tasks. Others have attempted to solve non-classiﬁcation problems using local metrics, but we feel that our approach is the ﬁrst to have a solid theoretical backing. For example, Hastie and Tibshirani [9] use local LDA metrics for dimensionality reduction by averaging the local metrics and using the resulting metric as part of a Euclidean PCA, which essentially is a linear approach. Another approach was suggested by Hong et al. [23] who simply compute the principal components according to each metric separately, such that one low dimensional model is learned per metric. The suggested approach is, however, not difﬁculty-free in its current implementation. Currently, we are using off-the-shelf numerical solvers for computing geodesics, which can be computationally demanding. While we managed to analyze medium-sized datasets, we believe that the run-time can be drastically improved by developing specialized numerical solvers. In the experiments, we learned local metrics using techniques specialized for classiﬁcation tasks as this is all the current literature provides. We expect improvements by learning the metrics speciﬁcally for regression and dimensionality reduction, but doing so is currently an open problem. Acknowledgments: Søren Hauberg is supported in part by the Villum Foundation, and Oren Freifeld is supported in part by NIH-NINDS EUREKA (R01-NS066311). 8 References [1] Andrea Frome, Yoram Singer, and Jitendra Malik. Image retrieval and classiﬁcation using local distance functions. In B. Sch¨ lkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing o Systems 19 (NIPS), pages 417–424, Cambridge, MA, 2007. MIT Press. [2] Andrea Frome, Fei Sha, Yoram Singer, and Jitendra Malik. Learning globally-consistent local distance functions for shape-based image retrieval and classiﬁcation. In International Conference on Computer Vision (ICCV), pages 1–8, 2007. [3] Deva Ramanan and Simon Baker. Local distance functions: A taxonomy, new algorithms, and an evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(4):794–806, 2011. [4] Shai Shalev-Shwartz, Yoram Singer, and Andrew Y. Ng. Online and batch learning of pseudo-metrics. In Proceedings of the twenty-ﬁrst international conference on Machine learning, ICML ’04, pages 94–101. ACM, 2004. [5] Kilian Q. Weinberger and Lawrence K. Saul. Distance metric learning for large margin nearest neighbor classiﬁcation. The Journal of Machine Learning Research, 10:207–244, 2009. [6] Tomasz Malisiewicz and Alexei A. Efros. Recognition by association via learning per-exemplar distances. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1–8, 2008. [7] Yiming Ying and Peng Li. Distance metric learning with eigenvalue optimization. The Journal of Machine Learning Research, 13:1–26, 2012. [8] Matthew Schultz and Thorsten Joachims. Learning a distance metric from relative comparisons. In Advances in Neural Information Processing Systems 16 (NIPS), 2004. [9] Trevor Hastie and Robert Tibshirani. Discriminant adaptive nearest neighbor classiﬁcation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(6):607–616, June 1996. [10] Elzbieta Pekalska, Pavel Paclik, and Robert P. W. Duin. A generalized kernel approach to dissimilaritybased classiﬁcation. Journal of Machine Learning Research, 2:175–211, 2002. [11] Manfredo Perdigao do Carmo. Riemannian Geometry. Birkh¨ user Boston, January 1992. a [12] Joshua B. Tenenbaum, Vin De Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000. [13] Jan R. Magnus and Heinz Neudecker. Matrix Differential Calculus with Applications in Statistics and Econometrics. John Wiley & Sons, 2007. [14] Jacek Kierzenka and Lawrence F. Shampine. A BVP solver based on residual control and the Matlab PSE. ACM Transactions on Mathematical Software, 27(3):299–316, 2001. [15] John R. Dormand and P. J. Prince. A family of embedded Runge-Kutta formulae. Journal of Computational and Applied Mathematics, 6:19–26, 1980. [16] P. Thomas Fletcher, Conglin Lu, Stephen M. Pizer, and Sarang Joshi. Principal Geodesic Analysis for the study of Nonlinear Statistics of Shape. IEEE Transactions on Medical Imaging, 23(8):995–1005, 2004. [17] Peter E. Jupp and John T. Kent. Fitting smooth paths to spherical data. Applied Statistics, 36(1):34–46, 1987. [18] Xavier Pennec. Probabilities and statistics on Riemannian manifolds: Basic tools for geometric measurements. In Proceedings of Nonlinear Signal and Image Processing, pages 194–198, 1999. [19] Stefan Sommer, Francois Lauze, Søren Hauberg, and Mads Nielsen. Manifold valued statistics, exact ¸ principal geodesic analysis and the effect of linear approximations. In European Conference on Computer Vision (ECCV), pages 43–56, 2010. [20] Kathleen M. Robinette, Hein Daanen, and Eric Paquet. The CAESAR project: a 3-D surface anthropometry survey. In 3-D Digital Imaging and Modeling, pages 380–386, 1999. [21] Dragomir Anguelov, Praveen Srinivasan, Daphne Koller, Sebastian Thrun, Jim Rodgers, and James Davis. Scape: shape completion and animation of people. ACM Transactions on Graphics, 24(3):408–416, 2005. [22] Oren Freifeld and Michael J. Black. Lie bodies: A manifold representation of 3D human shape. In A. Fitzgibbon et al. (Eds.), editor, European Conference on Computer Vision (ECCV), Part I, LNCS 7572, pages 1–14. Springer-Verlag, oct 2012. [23] Yi Hong, Quannan Li, Jiayan Jiang, and Zhuowen Tu. Learning a mixture of sparse distance metrics for classiﬁcation and dimensionality reduction. In International Conference on Computer Vision (ICCV), pages 906–913, 2011. 9

4 0.67574418 250 nips-2012-On-line Reinforcement Learning Using Incremental Kernel-Based Stochastic Factorization

Author: Doina Precup, Joelle Pineau, Andre S. Barreto

Abstract: Kernel-based stochastic factorization (KBSF) is an algorithm for solving reinforcement learning tasks with continuous state spaces which builds a Markov decision process (MDP) based on a set of sample transitions. What sets KBSF apart from other kernel-based approaches is the fact that the size of its MDP is independent of the number of transitions, which makes it possible to control the trade-off between the quality of the resulting approximation and the associated computational cost. However, KBSF’s memory usage grows linearly with the number of transitions, precluding its application in scenarios where a large amount of data must be processed. In this paper we show that it is possible to construct KBSF’s MDP in a fully incremental way, thus freeing the space complexity of this algorithm from its dependence on the number of sample transitions. The incremental version of KBSF is able to process an arbitrary amount of data, which results in a model-based reinforcement learning algorithm that can be used to solve continuous MDPs in both off-line and on-line regimes. We present theoretical results showing that KBSF can approximate the value function that would be computed by conventional kernel-based learning with arbitrary precision. We empirically demonstrate the effectiveness of the proposed algorithm in the challenging threepole balancing task, in which the ability to process a large number of transitions is crucial for success. 1

5 0.63452041 87 nips-2012-Convolutional-Recursive Deep Learning for 3D Object Classification

Author: Richard Socher, Brody Huval, Bharath Bath, Christopher D. Manning, Andrew Y. Ng

6 0.6073482 258 nips-2012-Online L1-Dictionary Learning with Application to Novel Document Detection

7 0.60478461 42 nips-2012-Angular Quantization-based Binary Codes for Fast Similarity Search

8 0.5995689 3 nips-2012-A Bayesian Approach for Policy Learning from Trajectory Preference Queries

9 0.59913391 235 nips-2012-Natural Images, Gaussian Mixtures and Dead Leaves

10 0.59570634 202 nips-2012-Locally Uniform Comparison Image Descriptor

11 0.59311217 339 nips-2012-The Time-Marginalized Coalescent Prior for Hierarchical Clustering

12 0.58700281 360 nips-2012-Visual Recognition using Embedded Feature Selection for Curvature Self-Similarity

13 0.58646518 274 nips-2012-Priors for Diversity in Generative Latent Variable Models

14 0.58581471 178 nips-2012-Learning Label Trees for Probabilistic Modelling of Implicit Feedback

15 0.58550721 176 nips-2012-Learning Image Descriptors with the Boosting-Trick

16 0.58457172 193 nips-2012-Learning to Align from Scratch

17 0.58451825 90 nips-2012-Deep Learning of Invariant Features via Simulated Fixations in Video

18 0.58333087 260 nips-2012-Online Sum-Product Computation Over Trees

19 0.58326054 201 nips-2012-Localizing 3D cuboids in single-view images

20 0.58001888 357 nips-2012-Unsupervised Template Learning for Fine-Grained Object Recognition