nips nips2005 nips2005-131 knowledge-graph by maker-knowledge-mining

131 nips-2005-Multiple Instance Boosting for Object Detection

Source: pdf

Author: Cha Zhang, John C. Platt, Paul A. Viola

Abstract: A good image object detection algorithm is accurate, fast, and does not require exact locations of objects in a training set. We can create such an object detector by taking the architecture of the Viola-Jones detector cascade and training it with a new variant of boosting that we call MILBoost. MILBoost uses cost functions from the Multiple Instance Learning literature combined with the AnyBoost framework. We adapt the feature selection criterion of MILBoost to optimize the performance of the Viola-Jones cascade. Experiments show that the detection rate is up to 1.6 times better using MILBoost. This increased detection rate shows the advantage of simultaneously learning the locations and scales of the objects in the training set along with the parameters of the classiﬁer. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com Abstract A good image object detection algorithm is accurate, fast, and does not require exact locations of objects in a training set. [sent-3, score-0.562]

2 We can create such an object detector by taking the architecture of the Viola-Jones detector cascade and training it with a new variant of boosting that we call MILBoost. [sent-4, score-0.826]

3 Experiments show that the detection rate is up to 1. [sent-7, score-0.247]

4 This increased detection rate shows the advantage of simultaneously learning the locations and scales of the objects in the training set along with the parameters of the classiﬁer. [sent-9, score-0.378]

5 1 Introduction When researchers use machine learning for object detection, they need to know the location and size of the objects, in order to generate positive examples for the classiﬁcation algorithm. [sent-10, score-0.378]

6 In this paper, we explicitly acknowledge that object recognition is innately a Multiple Instance Learning problem: we know that objects are located in regions of the image, but we don’t know exactly where. [sent-14, score-0.246]

7 Instead, they come in “bags”, where all of the examples in a bag share a label [4]. [sent-16, score-0.434]

8 A positive bag means that at least one example in the bag is positive, while a negative bag means that all examples in the bag are negative. [sent-17, score-1.657]

9 In MIL, learning must simultaneously learn which examples in the positive bags are positive, along with the parameters of the classiﬁer. [sent-18, score-0.329]

10 We have combined MIL with the Viola-Jones method of object detection, which uses Adaboost [11] to create a cascade of detectors. [sent-19, score-0.32]

11 In addition, we show how early stage in the detection cascade can be re-trained using information extracted from the ﬁnal MIL classiﬁer. [sent-21, score-0.383]

12 The MIL framework is shown to produce classiﬁers with much higher detection rates and fast computation times. [sent-24, score-0.263]

13 1 Structure of paper We ﬁrst review the previous work in two ﬁelds: previous related work in object detection (Section 2. [sent-26, score-0.355]

14 We derive a new MIL variant of boosting in Section 3, called MILBoost. [sent-29, score-0.228]

15 We then adapt MILBoost to train an effective cascade using a new criterion for selecting features in the early rounds of training (Section 5). [sent-31, score-0.263]

16 The paper concludes in Section 6 with experimental results on the problem of person detection in a teleconferencing application. [sent-32, score-0.319]

17 The MIL framework is shown to produce classiﬁers with much higher detection rates and fast computation times. [sent-33, score-0.263]

18 2 Relationship to previous work This paper lies at the intersection between the subﬁelds of object detection and multiple instance learning. [sent-34, score-0.455]

19 1 Previous work in image object detection The task of object detection in images is quite daunting. [sent-37, score-0.854]

20 Amongst the challenges are 1) creating a system with high accuracy and low false detection rate, 2) restricting the system to consume a reasonable amount of CPU time, and 3) creating a large training set that has low labeling error. [sent-38, score-0.427]

21 These models can be trained using unsegmented images in which the object can appear at any location. [sent-41, score-0.257]

22 However, hitherto, the detection accuracy has not be as good as the best methods. [sent-43, score-0.235]

23 It is also very efﬁcient, because it uses a cascade of detectors and very simple image features. [sent-46, score-0.25]

24 The exact location and size of the hands is approximately truthed: the neural network used MIL training to co-learn the object location and the parameters of the classiﬁer. [sent-51, score-0.292]

25 Unlike Nowlan and Platt, we maintain a cascade of detectors for maximum speed. [sent-56, score-0.174]

26 Diverse Density uses the Noisy OR generative model [6] to explain the bag labels. [sent-66, score-0.348]

27 Finally, a number of researchers have modiﬁed the boosting algorithm to perform MIL. [sent-70, score-0.2]

28 For example, Andrews and Hofmann [1] have proposed modifying the inner loop of boosting to use linear programming. [sent-71, score-0.2]

29 This is not practically applicable to the object detection task, which can have millions of examples (pixels) and thousands of bags. [sent-72, score-0.441]

30 A third approach is that of Xu and Frank [14], which uses a generative model that the probability of a bag being positive is the mean of the probabilities that the examples are positive. [sent-75, score-0.538]

31 We believe that this rule is unsuited for object detection, because only a small subset of the examples in the bag are ever positive. [sent-76, score-0.58]

32 which views boosting as a gradient descent process [9]. [sent-79, score-0.2]

33 1 Noisy-OR Boost Recall in boosting each example is classiﬁed by a linear combination of weak classiﬁers. [sent-83, score-0.292]

34 The score of the example is yij = C(xij ) and C(xij ) = t t λt c (xij ) a weighted sum of weak classiﬁers. [sent-87, score-0.191]

35 The probability of an example is positive is given by 1 pij = , 1 + exp(−yij ) the standard logistic function. [sent-88, score-0.185]

36 The probability that the bag is positive is a “noisy OR” pi = 1 − j∈i (1 − pij ) [6] [8]. [sent-89, score-0.63]

37 Under this model the likelihood assigned to a set of training bags is: L(C) = pti (1 − pi )(1−ti ) i i where ti ∈ {0, 1} is the label of bag i. [sent-90, score-0.728]

38 The derivative of the log likelihood is: ∂ log L(C) t i − pi = wij = pij . [sent-92, score-0.212]

39 Each round of boosting is a search for a classiﬁer which maximizes ij c(xij )wij where c(xij ) is the score assigned to the example by the weak classiﬁer (for a binary classiﬁer c(xij ) ∈ {−1, +1}). [sent-95, score-0.409]

40 Examining the criteria (1) the weight on each example is the product of two quantities: the bag weight Wbag = ti −pi and the instance weight Winstance = pij . [sent-97, score-0.754]

41 Observe that Wbag for pi a negative bag is always −1. [sent-98, score-0.52]

42 Thus, the weight for a negative instance, pij , is the same that would result in a non-MIL AdaBoost framework (i. [sent-99, score-0.247]

43 The weight on the positive instances is more complex. [sent-102, score-0.167]

44 As learning proceeds and the probability of the bag approaches the target, the weight on the entire bag is reduced. [sent-103, score-0.759]

45 Within the bag, the examples are assigned a weight which is higher for examples with higher scores. [sent-104, score-0.279]

46 Intuitively the algorithm selects a subset of examples to assign a higher positive weight, and these example dominate subsequent learning. [sent-105, score-0.19]

47 The quantity Si can be interpreted as a likelihood ratio that some (at least one) instance is positive, and ﬁnally pi is the probability that some instance is positive. [sent-113, score-0.223]

48 The example weights for the ISR framework are: ∂ log L(C) χij (2) = wij = (ti − pi ) ∂yij j∈i χij Examining the ISR criteria reveals two key properties. [sent-114, score-0.221]

49 The examples in the bag compete for weight, since the weight is normalized by sum of the χij ’s. [sent-116, score-0.528]

50 Though the experimental evidence is weak, this rule perhaps leads to a very localized representation, where a single example is labeled positive and the other examples are labeled negative. [sent-117, score-0.318]

51 The second property is that the negative examples also compete for weight. [sent-118, score-0.192]

52 This turns out to be troublesome in the detection framework since there are many, many more negative examples than positive. [sent-119, score-0.398]

53 In contrast, the Noisy OR criteria treats all negative examples as independent negative examples. [sent-121, score-0.271]

54 4 Application of MIL Boost to Object Detection in Images Each image is divided into a set of overlapping square windows that uniformly sample the space of position and scale (typically there are between 10,000 and 100,000 windows in a training image). [sent-122, score-0.352]

55 Each training image is labeled to determine the position and scale of the object of interest. [sent-124, score-0.348]

56 One possibility is to localize the eyes and then to determine the single positive image window in which the eyes appear at a given relative location and scale. [sent-126, score-0.303]

57 Even for this type of object the effort in carefully labeling the images is signiﬁcant. [sent-127, score-0.214]

58 For many other types of objects (objects which may be visible from multiple poses, or Figure 1: Two example images with people in a wide variety of poses. [sent-128, score-0.217]

59 It is not clear how to normalize images of people in a conference room, who may be standing, sitting upright, reclining, looking toward, or looking away from the camera. [sent-132, score-0.165]

60 In every training image each person is labeled by hand. [sent-138, score-0.246]

61 At the available resolution (approximately 1000x150 pixels) the head is often less than 10 pixels wide. [sent-141, score-0.186]

62 At this resolution, even for clear frontal faces, the best face detection algorithms frequently fail. [sent-142, score-0.29]

63 The only way to detect the head is to include the surrounding image context. [sent-144, score-0.233]

64 Each positive head is represented, during training, by a large number of related image windows (see Figure 2). [sent-150, score-0.444]

65 The MIL boosting algorithm is then used to simultaneously learn a detector and determine the location and scale of the appropriate image context. [sent-151, score-0.426]

66 5 MIL Boosting a Detection Cascade In their work on face detection Viola and Jones train a cascade of classiﬁers, each designed to achieve high detection rates and modest false positive rates. [sent-152, score-0.906]

67 During detection almost all of the computation is performed by the early stages in the cascade, perhaps 90% in the ﬁrst 10 features. [sent-153, score-0.209]

68 Training the initial stages of the cascade is the key to a fast and effective classiﬁer. [sent-154, score-0.2]

69 Training and evaluating a detector in a MIL framework has a direct impact on cascade construction, both on the features selected and the appropriate thresholds. [sent-155, score-0.31]

70 Those examples in positive bags which are assigned high weight have also high score. [sent-157, score-0.436]

71 The remaining examples in the positive bags are assigned a low weight and have a low score. [sent-159, score-0.436]

72 Since boosting is a greedy process, the initial weak classiﬁers do not have any knowledge of the subsequent classiﬁers. [sent-161, score-0.292]

73 The key to efﬁcient processing, is that the initial classiﬁers have a low false negative rate on the examples determined to be positive by the ﬁnal MIL classiﬁer. [sent-163, score-0.433]

74 Train a complete MIL boosted classiﬁer and set the detection threshold to achieve the desired false positive and false negative rates. [sent-165, score-0.679]

75 Retrain the initial weak classiﬁer so that it has a zero false negative rate on the examples labeled positive by the full classiﬁer. [sent-166, score-0.589]

76 The process can be repeated, so that the second classiﬁer is trained to yield a zero false negative rate on the remaining examples. [sent-168, score-0.286]

77 In all cases the detector was trained on 7 video conferences and tested on the remaining video conference. [sent-171, score-0.215]

78 Each was labeled by drawing a rectangle around the head of each person. [sent-173, score-0.25]

79 Figure 3: ROC comparison between various boosting rules. [sent-180, score-0.2]

80 For the MIL algorithms there is one bag for each labeled head, containing those positive windows which overlap that head. [sent-183, score-0.656]

81 Additionally there is one negative bag for each image. [sent-184, score-0.423]

82 During training a set of positive windows are generated for each labeled example. [sent-186, score-0.337]

83 5 times the head width and whose center is within 0. [sent-189, score-0.212]

84 5 times the head width of the center of the head are labeled positive. [sent-190, score-0.433]

85 An exception is made for AdaBoost, which has a tighter deﬁnition on positive examples (width between 0. [sent-191, score-0.19]

86 All windows which do not overlap with any head are considered negative. [sent-195, score-0.297]

87 A second experiment corrupts this ground truth further, moving each head by a uniform random shift such that there is non-zero overlap with the true position. [sent-197, score-0.26]

88 A typical example of detection results are shown in Figure 4. [sent-202, score-0.209]

89 In order to simplify the display, signiﬁcantly overlapping detection windows are averaged into a single window. [sent-204, score-0.316]

90 The scheme for retraining the initial classiﬁer was evaluated on the noisy OR strong classiﬁer trained above. [sent-205, score-0.171]

91 Training a conventional cascade requires ﬁnding a small set of weak classiﬁers that can achieve zero false negative rate (or almost zero) and a low false positive rate. [sent-206, score-0.743]

92 Using the ﬁrst weak classiﬁer yields a false positive rate of 39. [sent-207, score-0.364]

93 Including the ﬁrst four weak classiﬁers yields a false positive rate of 21. [sent-209, score-0.364]

94 After retraining the ﬁrst weak classiﬁer alone yields a false positive rate of 11. [sent-211, score-0.43]

95 This improved rejection rate has the effect of reducing computation time of the cascade by roughly a factor of three. [sent-213, score-0.212]

96 7 Conclusions This paper combines the truthing ﬂexibility of multiple instance learning with the high accuracy of the boosted object detector of Viola and Jones. [sent-214, score-0.411]

97 Maximum likelihood on the output of these bag combination functions ﬁt within the AnyBoost framework, which generates boosting weights for each example. [sent-217, score-0.575]

98 NorBoost improves the detection rate over standard AdaBoost (tight positive) by nearly 15% (at a 10% false positive rate). [sent-219, score-0.481]

99 Using MILBoost for object detection allows the detector to ﬂexibly assign labels to the training set, which reduces label noise and improves performance. [sent-220, score-0.525]

100 Logistic regression and boosting for labeled bags of instances. [sent-324, score-0.403]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('mil', 0.458), ('bag', 0.348), ('isr', 0.219), ('milboost', 0.219), ('detection', 0.209), ('boosting', 0.2), ('cascade', 0.174), ('adaboost', 0.16), ('head', 0.157), ('object', 0.146), ('bags', 0.139), ('false', 0.13), ('classi', 0.119), ('viola', 0.111), ('keeler', 0.11), ('detector', 0.108), ('windows', 0.107), ('positive', 0.104), ('pi', 0.097), ('anyboost', 0.095), ('weak', 0.092), ('nowlan', 0.088), ('xij', 0.087), ('examples', 0.086), ('pij', 0.081), ('er', 0.08), ('image', 0.076), ('negative', 0.075), ('boost', 0.073), ('yij', 0.073), ('ers', 0.07), ('objects', 0.069), ('images', 0.068), ('retraining', 0.066), ('teleconferencing', 0.066), ('labeled', 0.064), ('instance', 0.063), ('weight', 0.063), ('training', 0.062), ('noisy', 0.062), ('jones', 0.058), ('width', 0.055), ('face', 0.053), ('ij', 0.047), ('platt', 0.046), ('assigned', 0.044), ('person', 0.044), ('auer', 0.044), ('norboost', 0.044), ('reclining', 0.044), ('schmid', 0.044), ('subwindows', 0.044), ('unavoidable', 0.044), ('wbag', 0.044), ('trained', 0.043), ('people', 0.043), ('location', 0.042), ('convolutional', 0.042), ('volume', 0.038), ('ground', 0.038), ('maron', 0.038), ('rate', 0.038), ('ti', 0.038), ('multiple', 0.037), ('criteria', 0.035), ('zip', 0.035), ('mason', 0.035), ('wij', 0.034), ('overlap', 0.033), ('pages', 0.033), ('andrews', 0.032), ('video', 0.032), ('truth', 0.032), ('nal', 0.031), ('recognition', 0.031), ('si', 0.031), ('notes', 0.031), ('boosted', 0.031), ('constellation', 0.031), ('compete', 0.031), ('sub', 0.031), ('microsoft', 0.031), ('rectangle', 0.029), ('localize', 0.029), ('pixels', 0.029), ('framework', 0.028), ('perona', 0.028), ('frontal', 0.028), ('variant', 0.028), ('weights', 0.027), ('xu', 0.027), ('indexes', 0.027), ('train', 0.027), ('al', 0.027), ('looking', 0.027), ('accuracy', 0.026), ('derivation', 0.026), ('score', 0.026), ('fast', 0.026), ('eyes', 0.026)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999911 131 nips-2005-Multiple Instance Boosting for Object Detection

Author: Cha Zhang, John C. Platt, Paul A. Viola

2 0.19884619 5 nips-2005-A Computational Model of Eye Movements during Object Class Detection

Author: Wei Zhang, Hyejin Yang, Dimitris Samaras, Gregory J. Zelinsky

Abstract: We present a computational model of human eye movements in an object class detection task. The model combines state-of-the-art computer vision object class detection methods (SIFT features trained using AdaBoost) with a biologically plausible model of human eye movement to produce a sequence of simulated ﬁxations, culminating with the acquisition of a target. We validated the model by comparing its behavior to the behavior of human observers performing the identical object class detection task (looking for a teddy bear among visually complex nontarget objects). We found considerable agreement between the model and human data in multiple eye movement measures, including number of ﬁxations, cumulative probability of ﬁxating the target, and scanpath distance.

3 0.15548293 63 nips-2005-Efficient Unsupervised Learning for Localization and Detection in Object Categories

Author: Nicolas Loeff, Himanshu Arora, Alexander Sorokin, David Forsyth

Abstract: We describe a novel method for learning templates for recognition and localization of objects drawn from categories. A generative model represents the conﬁguration of multiple object parts with respect to an object coordinate system; these parts in turn generate image features. The complexity of the model in the number of features is low, meaning our model is much more efﬁcient to train than comparative methods. Moreover, a variational approximation is introduced that allows learning to be orders of magnitude faster than previous approaches while incorporating many more features. This results in both accuracy and localization improvements. Our model has been carefully tested on standard datasets; we compare with a number of recent template models. In particular, we demonstrate state-of-the-art results for detection and localization. 1

4 0.11284705 151 nips-2005-Pattern Recognition from One Example by Chopping

Author: Francois Fleuret, Gilles Blanchard

Abstract: We investigate the learning of the appearance of an object from a single image of it. Instead of using a large number of pictures of the object to recognize, we use a labeled reference database of pictures of other objects to learn invariance to noise and variations in pose and illumination. This acquired knowledge is then used to predict if two pictures of new objects, which do not appear on the training pictures, actually display the same object. We propose a generic scheme called chopping to address this task. It relies on hundreds of random binary splits of the training set chosen to keep together the images of any given object. Those splits are extended to the complete image space with a simple learning algorithm. Given two images, the responses of the split predictors are combined with a Bayesian rule into a posterior probability of similarity. Experiments with the COIL-100 database and with a database of 150 deA graded LTEX symbols compare our method to a classical learning with several examples of the positive class and to a direct learning of the similarity. 1

5 0.1033155 57 nips-2005-Distance Metric Learning for Large Margin Nearest Neighbor Classification

Author: Kilian Q. Weinberger, John Blitzer, Lawrence K. Saul

Abstract: We show how to learn a Mahanalobis distance metric for k-nearest neighbor (kNN) classiﬁcation by semideﬁnite programming. The metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. On seven data sets of varying size and difﬁculty, we ﬁnd that metrics trained in this way lead to signiﬁcant improvements in kNN classiﬁcation—for example, achieving a test error rate of 1.3% on the MNIST handwritten digits. As in support vector machines (SVMs), the learning problem reduces to a convex optimization based on the hinge loss. Unlike learning in SVMs, however, our framework requires no modiﬁcation or extension for problems in multiway (as opposed to binary) classiﬁcation. 1

6 0.099669695 11 nips-2005-A Hierarchical Compositional System for Rapid Object Detection

7 0.091705605 50 nips-2005-Convex Neural Networks

8 0.080189951 79 nips-2005-Fusion of Similarity Data in Clustering

9 0.078983739 14 nips-2005-A Probabilistic Interpretation of SVMs with an Application to Unbalanced Classification

10 0.077767409 55 nips-2005-Describing Visual Scenes using Transformed Dirichlet Processes

11 0.076882802 49 nips-2005-Convergence and Consistency of Regularized Boosting Algorithms with Stationary B-Mixing Observations

12 0.076162927 12 nips-2005-A PAC-Bayes approach to the Set Covering Machine

13 0.075123355 97 nips-2005-Inferring Motor Programs from Images of Handwritten Digits

14 0.062384289 143 nips-2005-Off-Road Obstacle Avoidance through End-to-End Learning

15 0.061426383 92 nips-2005-Hyperparameter and Kernel Learning for Graph Based Semi-Supervised Classification

16 0.059817452 195 nips-2005-Transfer learning for text classification

17 0.059708778 23 nips-2005-An Application of Markov Random Fields to Range Sensing

18 0.059699398 121 nips-2005-Location-based activity recognition

19 0.059184372 98 nips-2005-Infinite latent feature models and the Indian buffet process

20 0.055126984 113 nips-2005-Learning Multiple Related Tasks using Latent Independent Component Analysis

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.199), (1, 0.031), (2, -0.033), (3, 0.152), (4, -0.003), (5, 0.147), (6, 0.132), (7, 0.179), (8, -0.033), (9, -0.092), (10, -0.006), (11, -0.047), (12, 0.003), (13, 0.054), (14, 0.109), (15, 0.022), (16, -0.084), (17, -0.091), (18, 0.072), (19, 0.044), (20, -0.012), (21, 0.214), (22, 0.002), (23, 0.058), (24, -0.135), (25, -0.044), (26, -0.049), (27, 0.017), (28, -0.043), (29, -0.008), (30, -0.041), (31, -0.006), (32, -0.088), (33, 0.076), (34, 0.007), (35, -0.076), (36, 0.02), (37, 0.047), (38, -0.076), (39, -0.094), (40, 0.058), (41, 0.022), (42, 0.08), (43, -0.153), (44, -0.042), (45, 0.115), (46, 0.104), (47, -0.037), (48, -0.019), (49, -0.017)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9598521 131 nips-2005-Multiple Instance Boosting for Object Detection

Author: Cha Zhang, John C. Platt, Paul A. Viola

2 0.7270537 151 nips-2005-Pattern Recognition from One Example by Chopping

Author: Francois Fleuret, Gilles Blanchard

3 0.72051769 63 nips-2005-Efficient Unsupervised Learning for Localization and Detection in Object Categories

Author: Nicolas Loeff, Himanshu Arora, Alexander Sorokin, David Forsyth

4 0.66177827 11 nips-2005-A Hierarchical Compositional System for Rapid Object Detection

Author: Long Zhu, Alan L. Yuille

Abstract: We describe a hierarchical compositional system for detecting deformable objects in images. Objects are represented by graphical models. The algorithm uses a hierarchical tree where the root of the tree corresponds to the full object and lower-level elements of the tree correspond to simpler features. The algorithm proceeds by passing simple messages up and down the tree. The method works rapidly, in under a second, on 320 × 240 images. We demonstrate the approach on detecting cats, horses, and hands. The method works in the presence of background clutter and occlusions. Our approach is contrasted with more traditional methods such as dynamic programming and belief propagation. 1

5 0.60773891 5 nips-2005-A Computational Model of Eye Movements during Object Class Detection

Author: Wei Zhang, Hyejin Yang, Dimitris Samaras, Gregory J. Zelinsky

6 0.44108564 55 nips-2005-Describing Visual Scenes using Transformed Dirichlet Processes

7 0.4312993 12 nips-2005-A PAC-Bayes approach to the Set Covering Machine

8 0.42599228 57 nips-2005-Distance Metric Learning for Large Margin Nearest Neighbor Classification

9 0.41457912 97 nips-2005-Inferring Motor Programs from Images of Handwritten Digits

10 0.41395125 94 nips-2005-Identifying Distributed Object Representations in Human Extrastriate Visual Cortex

11 0.40673262 79 nips-2005-Fusion of Similarity Data in Clustering

12 0.39723328 81 nips-2005-Gaussian Processes for Multiuser Detection in CDMA receivers

13 0.39417043 171 nips-2005-Searching for Character Models

14 0.37803933 195 nips-2005-Transfer learning for text classification

15 0.36177126 50 nips-2005-Convex Neural Networks

16 0.35876301 14 nips-2005-A Probabilistic Interpretation of SVMs with an Application to Unbalanced Classification

17 0.34601131 49 nips-2005-Convergence and Consistency of Regularized Boosting Algorithms with Stationary B-Mixing Observations

18 0.33404341 189 nips-2005-Tensor Subspace Analysis

19 0.32043049 143 nips-2005-Off-Road Obstacle Avoidance through End-to-End Learning

20 0.31689578 121 nips-2005-Location-based activity recognition

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(3, 0.505), (10, 0.015), (27, 0.017), (31, 0.039), (34, 0.086), (39, 0.043), (41, 0.017), (55, 0.023), (69, 0.043), (73, 0.028), (88, 0.079), (91, 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.97851014 83 nips-2005-Generalization error bounds for classifiers trained with interdependent data

Author: Nicolas Usunier, Massih-reza Amini, Patrick Gallinari

Abstract: In this paper we propose a general framework to study the generalization properties of binary classiﬁers trained with data which may be dependent, but are deterministically generated upon a sample of independent examples. It provides generalization bounds for binary classiﬁcation and some cases of ranking problems, and clariﬁes the relationship between these learning tasks. 1

same-paper 2 0.95710135 131 nips-2005-Multiple Instance Boosting for Object Detection

Author: Cha Zhang, John C. Platt, Paul A. Viola

3 0.95262128 117 nips-2005-Learning from Data of Variable Quality

Author: Koby Crammer, Michael Kearns, Jennifer Wortman

Abstract: We initiate the study of learning from multiple sources of limited data, each of which may be corrupted at a different rate. We develop a complete theory of which data sources should be used for two fundamental problems: estimating the bias of a coin, and learning a classiﬁer in the presence of label noise. In both cases, efﬁcient algorithms are provided for computing the optimal subset of data. 1

4 0.95169348 159 nips-2005-Q-Clustering

Author: Mukund Narasimhan, Nebojsa Jojic, Jeff A. Bilmes

Abstract: We show that Queyranne’s algorithm for minimizing symmetric submodular functions can be used for clustering with a variety of different objective functions. Two speciﬁc criteria that we consider in this paper are the single linkage and the minimum description length criteria. The ﬁrst criterion tries to maximize the minimum distance between elements of different clusters, and is inherently “discriminative”. It is known that optimal clusterings into k clusters for any given k in polynomial time for this criterion can be computed. The second criterion seeks to minimize the description length of the clusters given a probabilistic generative model. We show that the optimal partitioning into 2 clusters, and approximate partitioning (guaranteed to be within a factor of 2 of the the optimal) for more clusters can be computed. To the best of our knowledge, this is the ﬁrst time that a tractable algorithm for ﬁnding the optimal clustering with respect to the MDL criterion for 2 clusters has been given. Besides the optimality result for the MDL criterion, the chief contribution of this paper is to show that the same algorithm can be used to optimize a broad class of criteria, and hence can be used for many application speciﬁc criterion for which efﬁcient algorithm are not known.

5 0.82125843 85 nips-2005-Generalization to Unseen Cases

Author: Teemu Roos, Peter Grünwald, Petri Myllymäki, Henry Tirri

Abstract: We analyze classiﬁcation error on unseen cases, i.e. cases that are different from those in the training set. Unlike standard generalization error, this off-training-set error may differ signiﬁcantly from the empirical error with high probability even with large sample sizes. We derive a datadependent bound on the difference between off-training-set and standard generalization error. Our result is based on a new bound on the missing mass, which for small samples is stronger than existing bounds based on Good-Turing estimators. As we demonstrate on UCI data-sets, our bound gives nontrivial generalization guarantees in many practical cases. In light of these results, we show that certain claims made in the No Free Lunch literature are overly pessimistic. 1

6 0.79273391 112 nips-2005-Learning Minimum Volume Sets

7 0.71623284 41 nips-2005-Coarse sample complexity bounds for active learning

8 0.70623946 49 nips-2005-Convergence and Consistency of Regularized Boosting Algorithms with Stationary B-Mixing Observations

9 0.70392799 196 nips-2005-Two view learning: SVM-2K, Theory and Practice

10 0.6593048 84 nips-2005-Generalization in Clustering with Unobserved Features

11 0.65560651 9 nips-2005-A Domain Decomposition Method for Fast Manifold Learning

12 0.65430439 177 nips-2005-Size Regularized Cut for Data Clustering

13 0.65076154 58 nips-2005-Divergences, surrogate loss functions and experimental design

14 0.64130473 191 nips-2005-The Forgetron: A Kernel-Based Perceptron on a Fixed Budget

15 0.63946015 147 nips-2005-On the Convergence of Eigenspaces in Kernel Principal Component Analysis

16 0.62949932 160 nips-2005-Query by Committee Made Real

17 0.62861836 47 nips-2005-Consistency of one-class SVM and related algorithms

18 0.62666541 95 nips-2005-Improved risk tail bounds for on-line algorithms

19 0.62414497 74 nips-2005-Faster Rates in Regression via Active Learning

20 0.62257457 151 nips-2005-Pattern Recognition from One Example by Chopping