nips nips2006 nips2006-185 knowledge-graph by maker-knowledge-mining

185 nips-2006-Subordinate class recognition using relational object models

Source: pdf

Author: Aharon B. Hillel, Daphna Weinshall

Abstract: We address the problem of sub-ordinate class recognition, like the distinction between different types of motorcycles. Our approach is motivated by observations from cognitive psychology, which identify parts as the deﬁning component of basic level categories (like motorcycles), while sub-ordinate categories are more often deﬁned by part properties (like ’jagged wheels’). Accordingly, we suggest a two-stage algorithm: First, a relational part based object model is learnt using unsegmented object images from the inclusive class (e.g., motorcycles in general). The model is then used to build a class-speciﬁc vector representation for images, where each entry corresponds to a model’s part. In the second stage we train a standard discriminative classiﬁer to classify subclass instances (e.g., cross motorcycles) based on the class-speciﬁc vector representation. We describe extensive experimental results with several subclasses. The proposed algorithm typically gives better results than a competing one-step algorithm, or a two stage algorithm where classiﬁcation is based on a model of the sub-ordinate class. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Subordinate class recognition using relational object models Aharon Bar Hillel Department of Computer Science The Hebrew university of Jerusalem aharonbh@cs. [sent-1, score-0.474]

2 Our approach is motivated by observations from cognitive psychology, which identify parts as the deﬁning component of basic level categories (like motorcycles), while sub-ordinate categories are more often deﬁned by part properties (like ’jagged wheels’). [sent-8, score-0.711]

3 Accordingly, we suggest a two-stage algorithm: First, a relational part based object model is learnt using unsegmented object images from the inclusive class (e. [sent-9, score-1.095]

4 In the second stage we train a standard discriminative classiﬁer to classify subclass instances (e. [sent-13, score-0.644]

5 In this organization, higher nodes close to the root describe inclusive classes (like vehicles), intermediate nodes describe more speciﬁc categories (like motorcycles), and lower nodes close to the leaves capture ﬁne distinctions between objects (e. [sent-19, score-0.388]

6 Intuitively one could expect such hierarchy to be learnt either bottom-up or top-down (or both), but surprisingly, this is not the case. [sent-23, score-0.249]

7 In fact, there is a well deﬁned intermediate level in the hierarchy, called basic level, which is learnt ﬁrst [11]. [sent-24, score-0.441]

8 In addition to learning, this level is more primary than both more speciﬁc and more inclusive levels, in terms of many other psychological, anthropological and linguistic measures. [sent-25, score-0.272]

9 The primary role of basic level categories seems related to the structure of objects in the world. [sent-26, score-0.409]

10 Their experiments show that basic level categories (like cars and ﬂowers) are often described as a combination of distinctive parts (e. [sent-28, score-0.548]

11 In this level different objects share parts but differ in the parts’ values (e. [sent-41, score-0.428]

12 Top row: Two motorcycle subordinate classes, sport (right) and cross (left). [sent-46, score-0.583]

13 As members of the same basic level category, they share the same part structure. [sent-47, score-0.297]

14 Bottom row: Objects from different basic level categories, like a chair and a face, lack such natural part correspondence. [sent-48, score-0.372]

15 Several parts from a learnt motorcycle model as detected in cross and sport motorcycle images. [sent-50, score-0.796]

16 (Better seen in color) This discrimination paradigm cannot easily generalize to the classiﬁcation of basic level objects, mostly because these objects do not share common informative parts, and therefore cannot be efﬁciently compared using an ordered vector of ﬁxed parts. [sent-52, score-0.464]

17 In this paradigm objects are modeled as a set of parts with spatial relations between them. [sent-56, score-0.346]

18 The models are learnt and applied to images, which are represented as unordered feature sets (usually image patches). [sent-57, score-0.383]

19 However, given the characteristics of human categorization discussed above, this seems to be the correct paradigm to address the classiﬁcation of basic level categories. [sent-59, score-0.323]

20 These considerations suggest that sub-ordinate classiﬁcation should be solved using a two stage method: First we should learn a generative model for the basic category. [sent-60, score-0.408]

21 Using such a model, the object parts should be identiﬁed in each image, and their descriptions can be concatenated into an ordered vector. [sent-61, score-0.48]

22 In a second stage, the distinction between subordinate classes can be done by applying standard machine learning tools, like SVM, to the resulting ordered vectors. [sent-62, score-0.541]

23 In this framework, the model learnt in stage 1 is used to solve the correspondence problem: features in the same entry in two different image vectors correspond since they implement the same part. [sent-63, score-0.476]

24 Using this relatively high level representation, the distinction between subordinate categories may be expected to get easier. [sent-64, score-0.595]

25 Similar notions, of constructing discriminative classiﬁers on top of generative models, have been recently proposed in the context of object localization [10] and class recognition [7]. [sent-65, score-0.485]

26 Thus the discriminative classiﬁer for a class in [7, 10] uses a generative model of the same class as a representation scheme. [sent-67, score-0.37]

27 1 In contrast, in this work we use a recent learning algorithm, which already learns a generative relational model of basic categories using a discriminative boosting technique [2]. [sent-68, score-0.555]

28 The new element in our approach is in the learning of a model of one class (the more general basic level category) to allow the efﬁcient discrimination of another class (the more speciﬁc sub-ordinates). [sent-69, score-0.489]

29 Thus our main contribution lies the use of objcet hierarchy, where we represent sub-ordinate classes using models of the more general, basic level class. [sent-70, score-0.352]

30 For an under-sampled sub-ordinate class, the basic level model can be learnt from a larger sample, leading to a more stable representation for the second stage SVM and lower error rate. [sent-74, score-0.659]

31 100 50 0 −50 −100 −150 −100 −50 0 50 Figure 2: Left A Bayesian network specifying the dependencies between the hidden variables Cl , Cs and the k k parts scale and location Xlk , Xs for k = 1, . [sent-76, score-0.336]

32 Middle The spatial relations between 5 parts from a learnt chair model. [sent-80, score-0.494]

33 The cyan cross indicates the position of the hidden object center cl . [sent-81, score-0.297]

34 Right The implementations of the 5 parts in a chair image. [sent-82, score-0.298]

35 Such a system can better cope with new subordinate classes, since learning to identify a new class may rely on existing basic class models. [sent-84, score-0.629]

36 Typically the learning of generative models from unsegmented images is exponential in the number of parts and features [5, 6]. [sent-85, score-0.532]

37 This signiﬁcantly limits the richness of the generative model, to a point where it may not contain enough detail to distinguish between subclass instances. [sent-86, score-0.504]

38 Alternatively, rich models can be learnt from images with part segmentations [4, 9], but obtaining such training data requires a lot of human labor. [sent-87, score-0.433]

39 The algorithm we use in this work, presented in [2], learns from unsegmented images, and its complexity is linear in the number of model parts and image features. [sent-88, score-0.407]

40 We can hence learn models with many parts, providing a rich object description. [sent-89, score-0.272]

41 We also compare to another two-stage approach, called SLP (Subordinate Level Primacy), in which discrimination is done based on a model of the subordinate class. [sent-97, score-0.439]

42 1 Efﬁcient learning of object class models The learning method from [2] learns a generative relational object model, but the model parameters are discriminatively optimized using an extended boosting process. [sent-104, score-0.703]

43 The class model is learnt from a set of object images and a set of background images. [sent-105, score-0.633]

44 The object model is a generative part-based model with P parts (see example in Fig. [sent-110, score-0.527]

45 The appearance of parts is assumed to be independent, while their location and scale are relative to the unknown object location and scale. [sent-113, score-0.6]

46 It is a star-like model, where the center node is a 3-dimensional hidden node C = (Cl , Cs ), with the vector Cl denoting the unknown object location and the scalar Cs denoting its unknown scale. [sent-116, score-0.268]

47 , it is determined by the single best implementation of model parts by image features. [sent-121, score-0.332]

48 This MAP solution can be efﬁciently found using standard message passing in time linear in the number of parts P and the number of image features Nf . [sent-122, score-0.322]

49 Speciﬁcally, labeling object images by +1 and background images by −1, the learning algorithm N tries to minimize the exp loss of the margin, L(f ) = i=1 exp(−yi f (Ii )), which is the loss minimized by the Adaboost algorithm [12]. [sent-125, score-0.421]

50 Additional tweaks are added to improve class recognition results, including a gradient descent weak learner and a feedback loop between the optimization of the a weak hypothesis and its weight. [sent-131, score-0.314]

51 2 Subclass recognition As stated in the introduction, we approach subclass recognition using a two-stage algorithm. [sent-133, score-0.659]

52 In the ﬁrst stage a model of the basic level class is applied to the image, and descriptors of the identiﬁed parts are concatenated into an ordered vector. [sent-134, score-0.83]

53 In the second stage the subclass label is determined by feeding this vector into a classiﬁer trained to identify the subclass. [sent-135, score-0.606]

54 Class model learning Subclass recognition in the proposed framework depends on part consistency across images, and it is more sensitive to part identiﬁcation failures than the original class recognition task. [sent-137, score-0.446]

55 In [2], model parts are learnt using a gradient based weak learner, which tends to produce exaggerated part location models to enhance its discriminative power. [sent-142, score-0.732]

56 In such cases parts are modeled as being unrealistically far from the object center. [sent-143, score-0.378]

57 In addition, we found out experimentally that when the data contains object images with rich backgrounds, performance of subclass recognition and localization is improved when using models with increased relative location weight. [sent-145, score-0.972]

58 Speciﬁcally, a part hypothesis in the model includes appearance, location and scale components with relative weights λi /(λ1 + λ2 + λ3 ), i = 1, 2, 3, learnt automatically by the algorithm. [sent-146, score-0.4]

59 We multiply λ2 of all the parts in the learnt model by a constant factor of 10 when learning from images with rich background. [sent-147, score-0.609]

60 Subclass discrimination Given a learnt object model and a new image, we match for each model part the corresponding image feature which implements it in the MAP solution. [sent-150, score-0.653]

61 We then build the feature vector, which represents the new image, by concatenating all the feature descriptors implementing parts 1, . [sent-151, score-0.392]

62 • A normalized mean of the feature (m − m)/std(m) where m is the feature’s mean (over ˆ feature pixels), and m, std(m) are the empirical mean and std of m over the P parts in the ˆ image. [sent-156, score-0.389]

63 Vector representations are prepared in this manner for a training sample including objects from the sub-ordinate class, objects from other sub-ordinate classes of the same basic category, and background images. [sent-161, score-0.431]

64 Finally, a linear SVM [3] is trained to discriminate the target subordinate class images from all other images. [sent-162, score-0.524]

65 3 Experimental results Methods: In our experiments, we regard subclass recognition as a binary classiﬁcation problem in a retrieval scenario. [sent-163, score-0.546]

66 Images are labeled by the subclass they represent, or as background if they do not contain any object from the inclusive class. [sent-165, score-0.805]

67 We avoid this problem in the current study by ﬁltering the data sets, leaving only instances with clear-cut subclass afﬁliation. [sent-171, score-0.433]

68 The algorithms compared: We compare the performance of the following three algorithms: • Basic Level Primacy (BLP) - The two-stage method for subclass recognition described above, in which a model of the basic level category is used to form the vector representation. [sent-179, score-0.93]

69 • Subordinate level primacy (SLP) - A two-stage method for subclass recognition, in which a model of the sub-ordinate level category is used to form the vector representation. [sent-180, score-0.927]

70 (60) Grand (60) Upright (60) Figure 3: Object images from the subclasses learnt in our experiments. [sent-185, score-0.465]

71 The number of images in each subclass is indicated in the parenthesis next to the subclass name. [sent-187, score-0.966]

72 Individual faces were also considered as subclasses, and the males and females subclasses above include a single example from 4 such individuals. [sent-188, score-0.306]

73 This algorithm is competitive with current state-of-the-art methods in object class recognition [2]. [sent-191, score-0.345]

74 The third and the second method learn a different model for each subordinate category, and use images from the other sub-ordinate classes as part of the background class during model learning. [sent-192, score-0.798]

75 The ﬁrst and second method both employ the distinction between a representation and classiﬁcation, but the ﬁrst uses a model of the basic category, and so tries to take advantage of the structural similarity between different subordinate classes of the same basic category. [sent-194, score-0.824]

76 Datasets We have considered 12 subordinate classes from 6 basic categories. [sent-195, score-0.517]

77 We took the subordinate classes of grand piano and electric guitar from the Caltech 101 dataset 4 and supplemented them with classes of upright piano and classical guitar collected using google images. [sent-200, score-0.962]

78 Finally, we used subsets of the chairs and furniture background used in [2]5 to deﬁne classes of dining and living room chairs, dining and coffee tables. [sent-201, score-0.579]

79 4 Performance and parts number Performance and parts number 0. [sent-225, score-0.446]

80 02 10 20 30 40 Number of parts 50 60 0 10 20 30 40 Number of parts 50 60 Figure 4: Left: RPC error rates as a function of the number of model parts P in the two-stage BLP method, for 5 ≤ P ≤ 60. [sent-239, score-0.708]

81 The curves are presented for 6 representative subclasses, one from each basic level category presented in Fig. [sent-240, score-0.345]

82 This graph reports errors for the 6 basic level models used in the experiments reported on the left graph. [sent-242, score-0.279]

83 In general, while adding only a minor improvement to inclusive class recognition, adding parts beyond 30 signiﬁcantly improves subclass recognition performance. [sent-243, score-0.997]

84 The representation based on the basic level model is hence usually preferable for the ﬁne discriminations required. [sent-248, score-0.348]

85 Males Females Dining chair Living room chair Coffee table Dining table Classic guitar Electric guitar Grand piano Upright piano Individuals One stage method 14. [sent-254, score-0.643]

86 5)∗ Table 1: Error rates (in percents), when separating subclass images from non-subclass and background images. [sent-322, score-0.599]

87 The graph on the right describes the errors of the ﬁrst stage class models in the task of discriminating the basic level classes background images. [sent-331, score-0.664]

88 While the performance of inclusive class recognition stabilizes after ∼ 30 parts, the error rates in subclass recognition continue to drop signiﬁcantly for most subclasses well beyond 30 parts. [sent-332, score-1.056]

89 It seems that while later boosting rounds have minor contribution to class recognition in the ﬁrst stage of the algorithm, the added parts enrich the class representation and allow better subclass recognition in the second stage. [sent-333, score-1.292]

90 4 Summary and Discussion We have addressed in this paper the challenging problem of distinguishing between subordinate classes of the same basic level category. [sent-334, score-0.638]

91 Second, using a larger sample from the more general basic level category to build a richer representation. [sent-336, score-0.383]

92 Technically speaking, we use an efﬁcient algorithm to learn the generative model, and are therefore able to use a rich representation with dozens of parts (in [7] the representation typically includes 3 parts). [sent-340, score-0.451]

93 Our experiments show that the large number of model parts i a critical for the success of the two stage method. [sent-341, score-0.404]

94 The more important difference is that we use the hierarchy of natural objects, and learn the representation model for a more general class of objects - the basic level class (BLP). [sent-342, score-0.644]

95 We show experimentally that this is preferable to using a model of the target subordinate (SLP). [sent-343, score-0.386]

96 In our experiments, learning a generative relational model per class (or subclass) required 12-24 hours, while SVM training was typically done in a few seconds. [sent-348, score-0.311]

97 This advantage is more pronounced as the number of subclasses of the same class increases. [sent-349, score-0.279]

98 A sparse object category model for efﬁcient learning and exhaustive recognition. [sent-385, score-0.294]

99 Combining generative models and ﬁsher kernels for object class recognition. [sent-391, score-0.337]

100 Integrating representative and discriminative models for object category detection. [sent-408, score-0.358]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('subclass', 0.433), ('subordinate', 0.32), ('blp', 0.26), ('parts', 0.223), ('learnt', 0.196), ('subclasses', 0.169), ('object', 0.155), ('inclusive', 0.151), ('stage', 0.142), ('dining', 0.13), ('slp', 0.13), ('sport', 0.13), ('basic', 0.124), ('level', 0.121), ('motorcycles', 0.12), ('primacy', 0.113), ('recognition', 0.113), ('rpc', 0.108), ('nf', 0.103), ('images', 0.1), ('category', 0.1), ('relational', 0.095), ('guitar', 0.087), ('location', 0.086), ('objects', 0.084), ('caltech', 0.08), ('categories', 0.08), ('boosting', 0.077), ('class', 0.077), ('chair', 0.075), ('unsegmented', 0.075), ('motorcycle', 0.075), ('petals', 0.075), ('piano', 0.075), ('distinction', 0.074), ('classi', 0.073), ('classes', 0.073), ('generative', 0.071), ('image', 0.07), ('discriminative', 0.069), ('faces', 0.069), ('background', 0.066), ('grand', 0.065), ('std', 0.064), ('cross', 0.058), ('cl', 0.057), ('upright', 0.056), ('chairs', 0.056), ('eer', 0.056), ('coffee', 0.056), ('hierarchy', 0.053), ('part', 0.052), ('electric', 0.051), ('rich', 0.051), ('feature', 0.051), ('discrimination', 0.051), ('appearance', 0.05), ('svm', 0.046), ('ordered', 0.045), ('dct', 0.043), ('living', 0.041), ('model', 0.039), ('paradigm', 0.039), ('categorization', 0.039), ('cs', 0.038), ('leibe', 0.038), ('tversky', 0.038), ('daphna', 0.038), ('kadir', 0.038), ('build', 0.038), ('representation', 0.037), ('individuals', 0.035), ('models', 0.034), ('females', 0.034), ('males', 0.034), ('psychology', 0.034), ('weak', 0.033), ('advantage', 0.033), ('learn', 0.032), ('unordered', 0.032), ('er', 0.031), ('learner', 0.031), ('iccv', 0.031), ('identify', 0.031), ('ijcv', 0.03), ('concatenated', 0.03), ('features', 0.029), ('done', 0.029), ('female', 0.029), ('descriptors', 0.029), ('descriptions', 0.027), ('room', 0.027), ('preferable', 0.027), ('discriminate', 0.027), ('discriminating', 0.027), ('hidden', 0.027), ('hypothesis', 0.027), ('male', 0.026), ('fergus', 0.026), ('cation', 0.026)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999988 185 nips-2006-Subordinate class recognition using relational object models

Author: Aharon B. Hillel, Daphna Weinshall

2 0.15217294 50 nips-2006-Chained Boosting

Author: Christian R. Shelton, Wesley Huie, Kin F. Kan

Abstract: We describe a method to learn to make sequential stopping decisions, such as those made along a processing pipeline. We envision a scenario in which a series of decisions must be made as to whether to continue to process. Further processing costs time and resources, but may add value. Our goal is to create, based on historic data, a series of decision rules (one at each stage in the pipeline) that decide, based on information gathered up to that point, whether to continue processing the part. We demonstrate how our framework encompasses problems from manufacturing to vision processing. We derive a quadratic (in the number of decisions) bound on testing performance and provide empirical results on object detection. 1 Pipelined Decisions In many decision problems, all of the data do not arrive at the same time. Often further data collection can be expensive and we would like to make a decision without accruing the added cost. Consider silicon wafer manufacturing. The wafer is processed in a series of stages. After each stage some tests are performed to judge the quality of the wafer. If the wafer fails (due to ﬂaws), then the processing time, energy, and materials are wasted. So, we would like to detect such a failure as early as possible in the production pipeline. A similar problem can occur in vision processing. Consider the case of object detection in images. Often low-level pixel operations (such as downsampling an image) can be performed in parallel by dedicated hardware (on a video capture board, for example). However, searching each subimage patch of the whole image to test whether it is the object in question takes time that is proportional to the number of pixels. Therefore, we can imagine a image pipeline in which low resolution versions of the whole image are scanned ﬁrst. Subimages which are extremely unlikely to contain the desired object are rejected and only those which pass are processed at higher resolution. In this way, we save on many pixel operations and can reduce the cost in time to process an image. Even if downsampling is not possible through dedicated hardware, for most object detection schemes, the image must be downsampled to form an image pyramid in order to search for the object at different scales. Therefore, we can run the early stages of such a pipelined detector at the low resolution versions of the image and throw out large regions of the high resolution versions. Most of the processing is spent searching for small faces (at the high resolutions), so this method can save a lot of processing. Such chained decisions also occur if there is a human in the decision process (to ask further clarifying questions in database search, for instance). We propose a framework that can model all of these scenarios and allow such decision rules to be learned from historic data. We give a learning algorithm based on the minimization of the exponential loss and conclude with some experimental results. 1.1 Problem Formulation Let there be s stages to the processing pipeline. We assume that there is a static distribution from which the parts, objects, or units to be processed are drawn. Let p(x, c) represent this distribution in which x is a vector of the features of this unit and c represents the costs associated with this unit. In particular, let xi (1 ≤ i ≤ s) be the set of measurements (features) available to the decision maker immediately following stage i. Let c i (1 ≤ i ≤ s) be the cost of rejecting (or stopping the processing of) this unit immediately following stage i. Finally, let c s+1 be the cost of allowing the part to pass through all processing stages. Note that ci need not be monotonic in i. To take our wafer manufacturing example, for wafers that are good we might let c i = i for 1 ≤ i ≤ s, indicating that if a wafer is rejected at any stage, one unit of work has been invested for each stage of processing. For the same good wafers, we might let cs+1 = s − 1000, indicating that the value of a completed wafer is 1000 units and therefore the total cost is the processing cost minus the resulting value. For a ﬂawed wafer, the values might be the same, except for c s+1 which we would set to s, indicating that there is no value for a bad wafer. Note that the costs may be either positive or negative. However, only their relative values are important. Once a part has been drawn from the distribution, there is no way of affecting the “base level” for the value of the part. Therefore, we assume for the remainder of this paper that c i ≥ 0 for 1 ≤ i ≤ s + 1 and that ci = 0 for some value of i (between 1 and s + 1). Our goal is to produce a series of decision rules f i (xi ) for 1 ≤ i ≤ s. We let fi have a range of {0, 1} and let 0 indicate that processing should continue and 1 indicate that processing should be halted. We let f denote the collection of these s decision rules and augment the collection with an additional rule f s+1 which is identically 1 (for ease of notation). The cost of using these rules to halt processing an example is therefore s+1 i−1 ci fi (xi ) L(f (x), c) = i=1 (1 − fj (xj )) . j=1 We would like to ﬁnd a set of decision rules that minimize E p [L(f (x), c)]. While p(x, c) is not known, we do have a series of samples (training set) D = {(x1 , c1 ), (x2 , c2 ), . . . , (xn , cn )} of n examples drawn from the distribution p. We use superscripts to denote the example index and subscripts to denote the stage index. 2 Boosting Solution For this paper, we consider constructing the rules f i from simpler decision rules, much as in the Adaboost algorithm [1, 2]. We assume that each decision f i (xi ) is computed as the threshold of another function g i (xi ): fi (xi ) = I(gi (xi ) > 0).1 We bound the empirical risk: n n s+1 L(f (xk ), ck ) = i−1 ck I(gi (xk ) > 0) i i k=1 i=1 k=1 n s+1 j=1 k i−1 ck egi (xi ) i ≤ k=1 i=1 I(gj (xk ) ≤ 0) j k n s+1 j=1 k ck egi (xi )− i e−gj (xj ) = Pi−1 j=1 gj (xk ) j . (1) k=1 i=1 Our decision to make all costs positive ensures that the bounds hold. Our decision to make the optimal cost zero helps to ensure that the bound is reasonably tight. As in boosting, we restrict g i (xi ) to take the form mi αi,l hi,l (xi ), the weighted sum of m i subl=1 classiﬁers, each of which returns either −1 or +1. We will construct these weighted sums incrementally and greedily, adding one additional subclassiﬁer and associated weight at each step. We will pick the stage, weight, and function of the subclassiﬁer in order to make the largest negative change in the exponential bound to the empirical risk. The subclassiﬁers, h i,l will be drawn from a small class of hypotheses, H. 1 I is the indicator function that equals 1 if the argument is true and 0 otherwise. 1. Initialize gi (x) = 0 for all stages i k 2. Initialize wi = ck for all stages i and examples k. i 3. For each stage i: (a) Calculate targets for each training example, as shown in equation 5. (b) Let h be the result of running the base learner on this set. (c) Calculate the corresponding α as per equation 3. (d) Score this classiﬁcation as per equation 4 ¯ 4. Select the stage ¯ with the best (highest) score. Let h and α be the classiﬁer and ı ¯ weight found at that stage. ¯¯ 5. Let g¯(x) ← g¯(x) + αh(x). ı ı 6. Update the weights (see equation 2): ¯ k k ¯ ı • ∀1 ≤ k ≤ n, multiply w¯ by eαh(x¯ ) . ı ¯ k k ¯ ı • ∀1 ≤ k ≤ n, j > ¯, multiply wj by e−αh(x¯ ) . ı 7. Repeat from step 3 Figure 1: Chained Boosting Algorithm 2.1 Weight Optimization We ﬁrst assume that the stage at which to add a new subclassiﬁer and the subclassiﬁer to add have ¯ ¯ already been chosen: ¯ and h, respectively. That is, h will become h¯,m¯+1 but we simplify it for ı ı ı ease of expression. Our goal is to ﬁnd α ¯,m¯+1 which we similarly abbreviate to α. We ﬁrst deﬁne ¯ ı ı k k wi = ck egi (xi )− i Pi−1 j=1 gj (xk ) j (2) + as the weight of example k at stage i, or its current contribution to our risk bound. If we let D h be ¯ − ¯ the set of indexes of the members of D for which h returns +1, and let D h be similarly deﬁned for ¯ ¯ returns −1, we can further deﬁne those for which h s+1 + W¯ = ı k w¯ + ı + k∈Dh ¯ s+1 k wi − W¯ = ı − ı k∈Dh i=¯+1 ¯ k w¯ + ı − k∈Dh ¯ k wi . + ı k∈Dh i=¯+1 ¯ + ¯ We interpret W¯ to be the sum of the weights which h will emphasize. That is, it corresponds to ı ¯ ¯ the weights along the path that h selects: For those examples for which h recommends termination, we add the current weight (related to the cost of stopping the processing at this stage). For those ¯ examples for which h recommends continued processing, we add in all future weights (related to all − future costs associated with this example). W¯ can be similarly interpreted to be the weights (or ı ¯ costs) that h recommends skipping. If we optimize the loss bound of Equation 1 with respect to α, we obtain ¯ α= ¯ 1 Wı− log ¯ . + 2 W¯ ı (3) The more weight (cost) that the rule recommends to skip, the higher its α coefﬁcient. 2.2 Full Optimization Using Equation 3 it is straight forward to show that the reduction in Equation 1 due to the addition of this new subclassiﬁer will be + ¯ − ¯ W¯ (1 − eα ) + W¯ (1 − e−α ) . ı ı (4) We know of no efﬁcient method for determining ¯, the stage at which to add a subclassiﬁer, except ı by exhaustive search. However, within a stage, the choice of which subclassiﬁer to use becomes one of maximizing n s+1 k¯ k k z¯ h(x¯ ) , where z¯ = ı ı ı k k wi − w¯ ı (5) i=¯+1 ı k=1 ¯ with respect to h. This is equivalent to an weighted empirical risk minimization where the training 1 2 n k k set is {x¯ , x¯ , . . . , x¯ }. The label of x¯ is the sign of z¯ , and the weight of the same example is the ı ı ı ı ı k magnitude of z¯ . ı 2.3 Algorithm The resulting algorithm is only slightly more complex than standard Adaboost. Instead of a weight vector (one weight for each data example), we now have a weight matrix (one weight for each data example for each stage). We initialize each weight to be the cost associated with halting the corresponding example at the corresponding stage. We start with all g i (x) = 0. The complete algorithm is as in Figure 1. Each time through steps 3 through 7, we complete one “round” and add one additional rule to one stage of the processing. We stop executing this loop when α ≤ 0 or when an iteration counter ¯ exceeds a preset threshold. Bottom-Up Variation In situations where information is only gained after each stage (such as in section 4), we can also train the classiﬁers “bottom-up.” That is, we can start by only adding classiﬁers to the last stage. Once ﬁnished with it, we proceed to the previous stage, and so on. Thus instead of selecting the best stage, i, in each round, we systematically work our way backward through the stages, never revisiting previously set stages. 3 Performance Bounds Using the bounds in [3] we can provide a risk bound for this problem. We let E denote the expectaˆ tion with respect to the true distribution p(x, c) and En denote the empirical average with respect to the n training samples. We ﬁrst bound the indicator function with a piece-wise linear function, b θ , 1 with a maximum slope of θ : z ,0 . I(z > 0) ≤ bθ (z) = max min 1, 1 + θ We then bound the loss: L(f (x), c) ≤ φ θ (f (x), c) where s+1 φθ (f (x), c) = ci min{bθ (gi (xi )), bθ (−gi−1 (xi−1 )), bθ (−gi−2 (xi−2 )), . . . , bθ (−g1 (x1 ))} i=1 s+1 i ci Bθ (gi (xi ), gi−1 (xi−1 ), . . . , g1 (x1 )) = i=1 We replaced the product of indicator functions with a minimization and then bounded each indicator i with bθ . Bθ is just a more compact presentation of the composition of the function b θ and the minimization. We assume that the weights α at each stage have been scaled to sum to 1. This has no affect on the resulting classiﬁcations, but is necessary for the derivation below. Before stating the theorem, for clarity, we state two standard deﬁnition: Deﬁnition 1. Let p(x) be a probability distribution on the set X and let {x 1 , x2 , . . . , xn } be n independent samples from p(x). Let σ 1 , σ 2 , . . . , σ n be n independent samples from a Rademacher random variable (a binary variable that takes on either +1 or −1 with equal probability). Let F be a class of functions mapping X to . Deﬁne the Rademacher Complexity of F to be Rn (F ) = E sup f ∈F n 1 n σ i f (xi ) i=1 1 where the expectation is over the random draws of x through xn and σ 1 through σ n . Deﬁnition 2. Let p(x), {x1 , x2 , . . . , xn }, and F be as above. Let g 1 , g 2 , . . . , g n be n independent samples from a Gaussian distribution with mean 0 and variance 1. Analogous to the above deﬁnition, deﬁne the Gaussian Complexity of G to be Gn (F ) = E sup f ∈F 1 n n g i f (xi ) . i=1 We can now state our theorem, bounding the true risk by a function of the empirical risk: Theorem 3. Let H1 , H2 , . . . , Hs be the sequence of the sets of functions from which the base classiﬁer draws for chain boosting. If H i is closed under negation for all i, all costs are bounded between 0 and 1, and the weights for the classiﬁers at each stage sum to 1, then with probability 1 − δ, k ˆ E [L(f (x), c)] ≤ En [φθ (f (x), c)] + θ s (i + 1)Gn (Hi ) + i=1 8 ln 2 δ n for some constant k. Proof. Theorem 8 of [3] states ˆ E [L(x, c)] ≤ En (φθ (f (x), c)) + 2Rn (φθ ◦ F ) + 8 ln 2 δ n and therefore we need only bound the R n (φθ ◦ F ) term to demonstrate our theorem. For our case, we have 1 Rn (φθ ◦ F ) = E sup n f ∈F = E sup f ∈F 1 n s+1 ≤ E sup j=1 f ∈F n n σ i φθ (f (xi ), ci ) i=1 s+1 σi i=1 1 n s ci Bθ (gj (xi ), gj−1 (xi ), . . . , g1 (xi )) j j j−1 1 j=1 n s+1 s σ i Bθ (gj (xi ), gj−1 (xi ), . . . , g1 (xi )) = j j−1 1 i=1 s Rn (Bθ ◦ G j ) j=1 where Gi is the space of convex combinations of functions from H i and G i is the cross product of G1 through Gi . The inequality comes from switching the expectation and the maximization and then from dropping the c i (see [4], lemma 5). j s s Lemma 4 of [3] states that there exists a k such that R n (Bθ ◦ G j ) ≤ kGn (Bθ ◦ G j ). Theorem 14 j 2 s j s of the same paper allows us to conclude that G n (Bθ ◦ G ) ≤ θ i=1 Gn (Gi ). (Because Bθ is the 1 s minimum over a set of functions with maximum slope of θ , the maximum slope of B θ is also 1 .) θ Theorem 12, part 2 states G n (Gi ) = Gn (Hi ). Taken together, this proves our result. Note that this bound has only quadratic dependence on s, the length of the chain and does not explicitly depend on the number of rounds of boosting (the number of rounds affects φ θ which, in turn, affects the bound). 4 Application We tested our algorithm on the MIT face database [5]. This database contains 19-by-19 gray-scale images of faces and non-faces. The training set has 2429 face images and 4548 non-face images. The testing set has 472 faces and 23573 non-faces. We weighted the training set images so that the ratio of the weight of face images to non-face images matched the ratio in the testing set. 0.4 0.4 CB Global CB Bottom−up SVM Boosting 0.3 0.25 0.2 0.15 0.1 150 0.2 100 0.1 False positive rate 0.3 50 Average number of pixels 0.35 average cost/error per example 200 training cost training error testing cost testing error 0.05 0 100 200 300 400 500 number of rounds 700 1000 (a) 0 0 0.2 0.4 0.6 False negative rate 0.8 0 1 (b) Figure 2: (a) Accuracy verses the number of rounds for a typical run, (b) Error rates and average costs for a variety of cost settings. 4.1 Object Detection as Chained Boosting Our goal is to produce a classiﬁer that can identify non-face images at very low resolutions, thereby allowing for quick processing of large images (as explained later). Most image patches (or subwindows) do not contain faces. We, therefore, built a multi-stage detection system where any early rejection is labeled as a non-face. The ﬁrst stage looks at image patches of size 3-by-3 (i.e. a lowerresolution version of the 19-by-19 original image). The next stage looks at the same image, but at a resolution of 6-by-6. The third stage considers the image at 12-by-12. We did not present the full 19-by-19 images as the classiﬁcation did not signiﬁcantly improve over the 12-by-12 versions. We employ a simple base classiﬁer: the set of all functions that look at a single pixel and predict the class by thresholding the pixel’s value. The total classiﬁer at any stage is a linear combination of these simple classiﬁers. For a given stage, all of the base classiﬁers that target a particular pixel are added together producing a complex function of the value of the pixel. Yet, this pixel can only take on a ﬁnite number of values (256 in this case). Therefore, we can compile this set of base classiﬁers into a single look-up function that maps the brightness of the pixel into a real number. The total classiﬁer for the whole stage is merely the sum of these look-up functions. Therefore, the total work necessary to compute the classiﬁcation at a stage is proportional to the number of pixels in the image considered at that stage, regardless of the number of base classiﬁers used. We therefore assign a cost to each stage of processing proportional to the number of pixels at that stage. If the image is a face, we add a negative cost (i.e. bonus) if the image is allowed to pass through all of the processing stages (and is therefore “accepted” as a face). If the image is a nonface, we add a bonus if the image is rejected at any stage before completion (i.e. correctly labelled). While this dataset has only segmented image patches, in a real application, the classiﬁer would be run on all sub-windows of an image. More importantly, it would also be run at multiple resolutions in order to detect faces of different sizes (or at different distances from the camera). The classiﬁer chain could be run simultaneously at each of these resolutions. To wit, while running the ﬁnal 12-by12 stage at one resolution of the image, the 6-by-6 (previous) stage could be run at the same image resolution. This 6-by-6 processing would be the necessary pre-processing step to running the 12-by12 stage at a higher resolution. As we run our ﬁnal scan for big faces (at a low resolution), we can already (at the same image resolution) be performing initial tests to throw out portions of the image as not worthy of testing for smaller faces (at a higher resolution). Most of the work of detecting objects must be done at the high resolutions because there are many more overlapping subwindows. This chained method allows the culling of most of this high-resolution image processing. 4.2 Experiments For each example, we construct a vector of stage costs as above. We add a constant to this vector to ensure that the minimal element is zero, as per section 1.1. We scale all vectors by the same amount to ensure that the maximal value is 1.This means that the number of misclassiﬁcations is an upper bound on the total cost that the learning algorithm is trying to minimize. There are three ﬂexible quantities in this problem formulation: the cost of a pixel evaluation, the bonus for a correct face classiﬁcation, and the bonus for a correct non-face classiﬁcation. Changing these quantities will control the trade-off between false positives and true positives, and between classiﬁcation error and speed. Figure 2(a) shows the result of a typical run of the algorithm. As a function of the number of rounds, it plots the cost (that which the algorithm is trying to minimize) and the error (number of misclassiﬁed image patches), for both the training and testing sets (where the training set has been reweighted to have the same proportion of faces to non-faces as the testing set). We compared our algorithm’s performance to the performance of support vector machines (SVM) [6] and Adaboost [1] trained and tested on the highest resolution, 12-by-12, image patches. We employed SVM-light [7] with a linear kernels. Figure 2(b) compares the error rates for the methods (solid lines, read against the left vertical axis). Note that the error rates are almost identical for the methods. The dashed lines (read against the right vertical axis) show the average number of pixels evaluated (or total processing cost) for each of the methods. The SVM and Adaboost algorithms have a constant processing cost. Our method (by either training scheme) produces lower processing cost for most error rates. 5 Related Work Cascade detectors for vision processing (see [8] or [9] for example) may appear to be similar to the work in this paper. Especially at ﬁrst glance for the area of object detection, they appear almost the same. However, cascade detection and this work (chained detection) are quite different. Cascade detectors are built one at a time. A coarse detector is ﬁrst trained. The examples which pass that detector are then passed to a ﬁner detector for training, and so on. A series of targets for false-positive rates deﬁne the increasing accuracy of the detector cascade. By contrast, our chain detectors are trained as an ensemble. This is necessary because of two differences in the problem formulation. First, we assume that the information available at each stage changes. Second, we assume there is an explicit cost model that dictates the cost of proceeding from stage to stage and the cost of rejection (or acceptance) at any particular stage. By contrast, cascade detectors are seeking to minimize computational power necessary for a ﬁxed decision. Therefore, the information available to all of the stages is the same, and there are no ﬁxed costs associated with each stage. The ability to train all of the classiﬁers at the same time is crucial to good performance in our framework. The ﬁrst classiﬁer in the chain cannot determine whether it is advantageous to send an example further along unless it knows how the later stages will process the example. Conversely, the later stages cannot construct optimal classiﬁcations until they know the distribution of examples that they will see. Section 4.1 may further confuse the matter. We demonstrated how chained boosting can be used to reduce the computational costs of object detection in images. Cascade detectors are often used for the same purpose. However, the reductions in computational time come from two different sources. In cascade detectors, the time taken to evaluate a given image patch is reduced. In our chained detector formulation, image patches are ignored completely based on analysis of lower resolution patches in the image pyramid. To further illustrate the difference, cascade detectors can always be used to speed up asymmetric classiﬁcation tasks (and are often applied to image detection). By contrast, in Section 4.1 we have exploited the fact that object detection in images is typically performed at multiple scales to turn the problem into a pipeline and apply our framework. Cascade detectors address situations in which prior class probabilities are not equal, while chained detectors address situations in which information is gained at a cost. Both are valid (and separate) ways of tackling image processing (and other tasks as well). In many ways, they are complementary approaches. Classic sequence analysis [10, 11] also addresses the problem of optimal stopping. However, it assumes that the samples are drawn i.i.d. from (usually) a known distribution. Our problem is quite different in that each consecutive sample is drawn from a different (and related) distribution and our goal is to ﬁnd a decision rule without producing a generative model. WaldBoost [12] is a boosting algorithm based on this. It builds a series of features and a ratio comparison test in order to decide when to stop. For WaldBoost, the available features (information) not change between stages. Rather, any feature is available for selection at any point in the chain. Again, this is a different problem than the one considered in this paper. 6 Conclusions We feel this framework of staged decision making is useful in a wide variety of areas. This paper demonstrated how the framework applies to one vision processing task. Obviously it also applies to manufacturing pipelines where errors can be introduced at different stages. It should also be applicable to scenarios where information gathering is costly. Our current formulation only allows for early negative detection. In the face detection example above, this means that in order to report “face,” the classiﬁer must process each stage, even if the result is assured earlier. In Figure 2(b), clearly the upper-left corner (100% false positives and 0% false negatives) is reachable with little effort: classify everything positive without looking at any features. We would like to extend this framework to cover such two-sided early decisions. While perhaps not useful in manufacturing (or even face detection, where the interesting part of the ROC curve is far from the upper-left), it would make the framework more applicable to informationgathering applications. Acknowledgements This research was supported through the grant “Adaptive Decision Making for Silicon Wafer Testing” from Intel Research and UC MICRO. References [1] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. In EuroCOLT, pages 23–37, 1995. [2] Yoav Freund and Robert E. Schapire. Experiments with a new boosting algorithm. In ICML, pages 148–156, 1996. [3] Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. JMLR, 2:463–482, 2002. [4] Ron Meir and Tong Zhang. Generalization error bounds for Bayesian mixture algorithms. JMLR, 4:839–860, 2003. [5] MIT. CBCL face database #1, 2000. http://cbcl.mit.edu/cbcl/softwaredatasets/FaceData2.html. [6] Bernhard E. Boser, Isabelle M. Guyon, and Vladimir N. Vapnik. A training algorithm for optimal margin classiﬁers. In COLT, pages 144–152, 1992. [7] T. Joachims. Making large-scale SVM learning practical. In B. Schlkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods — Support Vector Learning. MIT-Press, 1999. [8] Paul A. Viola and Michael J. Jones. Rapid object detection using a boosted cascade of simple features. In CVPR, pages 511–518, 2001. [9] Jianxin Wu, Matthew D. Mullin, and James M. Rehg. Linear asymmetric classiﬁer for cascade detectors. In ICML, pages 988–995, 2005. [10] Abraham Wald. Sequential Analysis. Chapman & Hall, Ltd., 1947. [11] K. S. Fu. Sequential Methods in Pattern Recognition and Machine Learning. Academic Press, 1968. ˇ [12] Jan Sochman and Jiˇ´ Matas. Waldboost — learning for time constrained sequential detection. rı In CVPR, pages 150–156, 2005.

3 0.13591589 115 nips-2006-Learning annotated hierarchies from relational data

Author: Daniel M. Roy, Charles Kemp, Vikash K. Mansinghka, Joshua B. Tenenbaum

Abstract: The objects in many real-world domains can be organized into hierarchies, where each internal node picks out a category of objects. Given a collection of features and relations deﬁned over a set of objects, an annotated hierarchy includes a speciﬁcation of the categories that are most useful for describing each individual feature and relation. We deﬁne a generative model for annotated hierarchies and the features and relations that they describe, and develop a Markov chain Monte Carlo scheme for learning annotated hierarchies. We show that our model discovers interpretable structure in several real-world data sets.

4 0.135885 94 nips-2006-Image Retrieval and Classification Using Local Distance Functions

Author: Andrea Frome, Yoram Singer, Jitendra Malik

Abstract: In this paper we introduce and experiment with a framework for learning local perceptual distance functions for visual recognition. We learn a distance function for each training image as a combination of elementary distances between patch-based visual features. We apply these combined local distance functions to the tasks of image retrieval and classiﬁcation of novel images. On the Caltech 101 object recognition benchmark, we achieve 60.3% mean recognition across classes using 15 training images per class, which is better than the best published performance by Zhang, et al. 1

5 0.13243139 199 nips-2006-Unsupervised Learning of a Probabilistic Grammar for Object Detection and Parsing

Author: Yuanhao Chen, Long Zhu, Alan L. Yuille

Abstract: We describe an unsupervised method for learning a probabilistic grammar of an object from a set of training examples. Our approach is invariant to the scale and rotation of the objects. We illustrate our approach using thirteen objects from the Caltech 101 database. In addition, we learn the model of a hybrid object class where we do not know the speciﬁc object or its position, scale or pose. This is illustrated by learning a hybrid class consisting of faces, motorbikes, and airplanes. The individual objects can be recovered as different aspects of the grammar for the object class. In all cases, we validate our results by learning the probability grammars from training datasets and evaluating them on the test datasets. We compare our method to alternative approaches. The advantages of our approach is the speed of inference (under one second), the parsing of the object, and increased accuracy of performance. Moreover, our approach is very general and can be applied to a large range of objects and structures. 1

6 0.1270896 78 nips-2006-Fast Discriminative Visual Codebooks using Randomized Clustering Forests

7 0.1012048 160 nips-2006-Part-based Probabilistic Point Matching using Equivalence Constraints

8 0.09931957 110 nips-2006-Learning Dense 3D Correspondence

9 0.095483296 66 nips-2006-Detecting Humans via Their Pose

10 0.078951687 58 nips-2006-Context Effects in Category Learning: An Investigation of Four Probabilistic Models

11 0.077793345 130 nips-2006-Max-margin classification of incomplete data

12 0.070916429 122 nips-2006-Learning to parse images of articulated bodies

13 0.066944599 8 nips-2006-A Nonparametric Approach to Bottom-Up Visual Saliency

14 0.066402107 179 nips-2006-Sparse Representation for Signal Classification

15 0.065434836 170 nips-2006-Robotic Grasping of Novel Objects

16 0.062424328 97 nips-2006-Inducing Metric Violations in Human Similarity Judgements

17 0.061333138 51 nips-2006-Clustering Under Prior Knowledge with Application to Image Segmentation

18 0.059763178 37 nips-2006-Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions

19 0.059159543 106 nips-2006-Large Margin Hidden Markov Models for Automatic Speech Recognition

20 0.057752695 73 nips-2006-Efficient Methods for Privacy Preserving Face Detection

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.206), (1, 0.037), (2, 0.126), (3, -0.115), (4, 0.019), (5, 0.029), (6, -0.188), (7, -0.08), (8, 0.025), (9, -0.121), (10, 0.07), (11, 0.1), (12, 0.012), (13, -0.032), (14, 0.101), (15, -0.018), (16, 0.051), (17, -0.03), (18, -0.01), (19, 0.023), (20, -0.069), (21, 0.111), (22, 0.014), (23, 0.002), (24, 0.028), (25, 0.0), (26, 0.019), (27, 0.091), (28, 0.093), (29, -0.094), (30, 0.088), (31, 0.112), (32, 0.16), (33, 0.033), (34, 0.065), (35, -0.07), (36, 0.054), (37, -0.082), (38, 0.033), (39, 0.091), (40, 0.055), (41, 0.172), (42, -0.003), (43, 0.057), (44, 0.029), (45, 0.013), (46, 0.01), (47, 0.107), (48, 0.095), (49, -0.101)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.93863535 185 nips-2006-Subordinate class recognition using relational object models

Author: Aharon B. Hillel, Daphna Weinshall

2 0.67184144 94 nips-2006-Image Retrieval and Classification Using Local Distance Functions

Author: Andrea Frome, Yoram Singer, Jitendra Malik

3 0.63016003 50 nips-2006-Chained Boosting

Author: Christian R. Shelton, Wesley Huie, Kin F. Kan

4 0.62089503 73 nips-2006-Efficient Methods for Privacy Preserving Face Detection

Author: Shai Avidan, Moshe Butman

Abstract: Bob offers a face-detection web service where clients can submit their images for analysis. Alice would very much like to use the service, but is reluctant to reveal the content of her images to Bob. Bob, for his part, is reluctant to release his face detector, as he spent a lot of time, energy and money constructing it. Secure MultiParty computations use cryptographic tools to solve this problem without leaking any information. Unfortunately, these methods are slow to compute and we introduce a couple of machine learning techniques that allow the parties to solve the problem while leaking a controlled amount of information. The ﬁrst method is an information-bottleneck variant of AdaBoost that lets Bob ﬁnd a subset of features that are enough for classifying an image patch, but not enough to actually reconstruct it. The second machine learning technique is active learning that allows Alice to construct an online classiﬁer, based on a small number of calls to Bob’s face detector. She can then use her online classiﬁer as a fast rejector before using a cryptographically secure classiﬁer on the remaining image patches. 1

5 0.60710341 199 nips-2006-Unsupervised Learning of a Probabilistic Grammar for Object Detection and Parsing

Author: Yuanhao Chen, Long Zhu, Alan L. Yuille

6 0.59640843 115 nips-2006-Learning annotated hierarchies from relational data

7 0.59279764 78 nips-2006-Fast Discriminative Visual Codebooks using Randomized Clustering Forests

8 0.55695951 160 nips-2006-Part-based Probabilistic Point Matching using Equivalence Constraints

9 0.54332471 52 nips-2006-Clustering appearance and shape by learning jigsaws

10 0.53688431 58 nips-2006-Context Effects in Category Learning: An Investigation of Four Probabilistic Models

11 0.53338104 170 nips-2006-Robotic Grasping of Novel Objects

12 0.48065296 110 nips-2006-Learning Dense 3D Correspondence

13 0.47686136 130 nips-2006-Max-margin classification of incomplete data

14 0.4281809 66 nips-2006-Detecting Humans via Their Pose

15 0.4035866 140 nips-2006-Multiple Instance Learning for Computer Aided Diagnosis

16 0.40214044 122 nips-2006-Learning to parse images of articulated bodies

17 0.3985993 193 nips-2006-Tighter PAC-Bayes Bounds

18 0.36159158 179 nips-2006-Sparse Representation for Signal Classification

19 0.35995772 106 nips-2006-Large Margin Hidden Markov Models for Automatic Speech Recognition

20 0.34612206 63 nips-2006-Cross-Validation Optimization for Large Scale Hierarchical Classification Kernel Methods

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(1, 0.11), (3, 0.012), (7, 0.121), (9, 0.052), (12, 0.011), (20, 0.024), (21, 0.044), (22, 0.042), (44, 0.046), (57, 0.122), (65, 0.056), (69, 0.025), (75, 0.254)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.79629421 101 nips-2006-Isotonic Conditional Random Fields and Local Sentiment Flow

Author: Yi Mao, Guy Lebanon

Abstract: We examine the problem of predicting local sentiment ﬂow in documents, and its application to several areas of text analysis. Formally, the problem is stated as predicting an ordinal sequence based on a sequence of word sets. In the spirit of isotonic regression, we develop a variant of conditional random ﬁelds that is wellsuited to handle this problem. Using the M¨ bius transform, we express the model o as a simple convex optimization problem. Experiments demonstrate the model and its applications to sentiment prediction, style analysis, and text summarization. 1

same-paper 2 0.7897408 185 nips-2006-Subordinate class recognition using relational object models

Author: Aharon B. Hillel, Daphna Weinshall

3 0.65644479 94 nips-2006-Image Retrieval and Classification Using Local Distance Functions

Author: Andrea Frome, Yoram Singer, Jitendra Malik

4 0.65091622 78 nips-2006-Fast Discriminative Visual Codebooks using Randomized Clustering Forests

Author: Frank Moosmann, Bill Triggs, Frederic Jurie

Abstract: Some of the most effective recent methods for content-based image classiﬁcation work by extracting dense or sparse local image descriptors, quantizing them according to a coding rule such as k-means vector quantization, accumulating histograms of the resulting “visual word” codes over the image, and classifying these with a conventional classiﬁer such as an SVM. Large numbers of descriptors and large codebooks are needed for good results and this becomes slow using k-means. We introduce Extremely Randomized Clustering Forests – ensembles of randomly created clustering trees – and show that these provide more accurate results, much faster training and testing and good resistance to background clutter in several state-of-the-art image classiﬁcation tasks. 1

5 0.63871598 110 nips-2006-Learning Dense 3D Correspondence

Author: Florian Steinke, Volker Blanz, Bernhard Schölkopf

Abstract: Establishing correspondence between distinct objects is an important and nontrivial task: correctness of the correspondence hinges on properties which are difﬁcult to capture in an a priori criterion. While previous work has used a priori criteria which in some cases led to very good results, the present paper explores whether it is possible to learn a combination of features that, for a given training set of aligned human heads, characterizes the notion of correct correspondence. By optimizing this criterion, we are then able to compute correspondence and morphs for novel heads. 1

6 0.63838851 119 nips-2006-Learning to Rank with Nonsmooth Cost Functions

7 0.6351248 80 nips-2006-Fundamental Limitations of Spectral Clustering

8 0.63493437 8 nips-2006-A Nonparametric Approach to Bottom-Up Visual Saliency

9 0.63397402 34 nips-2006-Approximate Correspondences in High Dimensions

10 0.63070482 51 nips-2006-Clustering Under Prior Knowledge with Application to Image Segmentation

11 0.62219214 160 nips-2006-Part-based Probabilistic Point Matching using Equivalence Constraints

12 0.62136322 43 nips-2006-Bayesian Model Scoring in Markov Random Fields

13 0.62004435 72 nips-2006-Efficient Learning of Sparse Representations with an Energy-Based Model

14 0.61945885 118 nips-2006-Learning to Model Spatial Dependency: Semi-Supervised Discriminative Random Fields

15 0.61909771 158 nips-2006-PG-means: learning the number of clusters in data

16 0.61760712 42 nips-2006-Bayesian Image Super-resolution, Continued

17 0.61694759 130 nips-2006-Max-margin classification of incomplete data

18 0.61625808 174 nips-2006-Similarity by Composition

19 0.61603755 117 nips-2006-Learning on Graph with Laplacian Regularization

20 0.6156503 124 nips-2006-Linearly-solvable Markov decision problems