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

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

Source: pdf

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

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Bob offers a face-detection web service where clients can submit their images for analysis. [sent-4, score-0.16]

2 Alice would very much like to use the service, but is reluctant to reveal the content of her images to Bob. [sent-5, score-0.128]

3 Bob, for his part, is reluctant to release his face detector, as he spent a lot of time, energy and money constructing it. [sent-6, score-0.253]

4 Secure MultiParty computations use cryptographic tools to solve this problem without leaking any information. [sent-7, score-0.156]

5 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. [sent-8, score-0.268]

6 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. [sent-9, score-0.207]

7 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. [sent-10, score-0.296]

8 She can then use her online classiﬁer as a fast rejector before using a cryptographically secure classiﬁer on the remaining image patches. [sent-11, score-0.491]

9 This beneﬁt is hindered by the fact that the seller, that owns the classiﬁer, learns a great deal about the buyers’ data, needs or goals. [sent-14, score-0.091]

10 This raised the need for privacy in Internet transactions. [sent-15, score-0.137]

11 While it is now common to assume that the buyer and the seller can secure their data exchange from the rest of the world, we are interested in a stronger level of security that allows the buyer to hide his data from the seller as well. [sent-16, score-0.403]

12 Of course, the same can be said about the seller, who would like to maintain the privacy of his hard-earned classiﬁer. [sent-17, score-0.137]

13 Secure Multi-Party Computation (SMC) are based on cryptographic tools that let two parties, Alice and Bob, to engage in a protocol that will allow them to achieve a common goal, without revealing the content of their input. [sent-18, score-0.164]

14 For example, Alice might be interested in classifying her data using Bobs’ classiﬁer without revealing anything to Bob, not even the classiﬁcation result, and without learning anything about Bobs’ classiﬁer, other than a binary answer to her query. [sent-19, score-0.116]

15 Recently, Avidan & Butman introduced Blind Vision [1] which is a method for securely evaluating a Viola-Jones type face detector [12]. [sent-20, score-0.151]

16 Blind Vision uses standard cryptographic tools and is painfully slow to compute, taking a couple of hours to scan a single image. [sent-21, score-0.101]

17 The purpose of this work is to explore machine learning techniques that can speed up the process, at the cost of a controlled leakage of information. [sent-22, score-0.067]

18 In our hypothetical scenario Bob has a face-detection web service where clients can submit their images to be analyzed. [sent-23, score-0.16]

19 Alice would very much like to use the service, but is reluctant to reveal the content of the images to Bob. [sent-24, score-0.128]

20 Bob, for his part, is reluctant to release his face detector, as he spent a lot of time, energy and money constructing it. [sent-25, score-0.253]

21 In our face detection protocol Alice raster scans the image and sends every image patch to Bob to be classiﬁed. [sent-26, score-0.544]

22 The challenge is to design protocols that can explicitly control the amount of information leaked. [sent-28, score-0.104]

23 One based on the information bottleneck and the other on active learning. [sent-30, score-0.157]

24 The ﬁrst method is a privacy-preserving feature selection which is a variant of the informationbottleneck principle to ﬁnd features that are useful for classiﬁcation but not for signal reconstruction. [sent-31, score-0.148]

25 In this case, Bob can use his training data to construct different classiﬁers that offer different trade-offs of information leakage versus classiﬁcation accuracy. [sent-32, score-0.092]

26 Alice can then choose the trade-off that suits her best and send only those features to Bob for classiﬁcation. [sent-33, score-0.088]

27 This method can be used, for example, as a ﬁltering step that rejects a large number of the image patches as having no face included in them, followed by a SMC method that will securely classify the remaining image patches, using the full classiﬁer that is known only to Bob. [sent-34, score-0.735]

28 The second method is active learning and it helps Alice choose which image patches to send to Bob for classiﬁcation. [sent-35, score-0.572]

29 The idea being that instead of sending all image patches to Bob for classiﬁcation, Alice might try to learn from the interaction as much as she can and use her online trained classiﬁer to reject some of the image patches herself. [sent-37, score-0.995]

30 This can minimize the amount of information revealed to Bob, if the parties use the privacy-preserving features or the computational load, if the parties are using cryptographically-based SMC methods. [sent-38, score-0.25]

31 2 Background Secure multi-party computation originated from the work of Yao [14] who gave a solution to the millionaire problem: Two parties want to ﬁnd which one has a larger number, without revealing anything else about the numbers themselves. [sent-39, score-0.17]

32 [5] showed that any function can be computed in such a secure manner. [sent-41, score-0.193]

33 Since then many secure protocols were reported for various data mining applications [7, 13, 1]. [sent-44, score-0.262]

34 A common assumption in SMC is that the parties are honest but curious, meaning that they will follow the agreed-upon protocol but will try to learn as much as possible from the data-ﬂow between the two parties. [sent-45, score-0.157]

35 The information bottleneck principle [10] shows how to compress a signal while preserving its information with respect to a target signal. [sent-47, score-0.11]

36 We offer a variant of the self-consistent equations used to solve this problem and offer a greedy feature selection algorithm that satisfy privacy constraints, that are represented as the percentage of the power spectrum of the original signal. [sent-48, score-0.337]

37 The usual motivation in active learning is that the Oracle is assumed to be a human operator and having him label data is a time consuming task that should be avoided. [sent-50, score-0.101]

38 Our motivation is similar, Alice would like to avoid using Bob because of the high computational cost involved in case of cryptographically secure protocols, or for fear of leaking information in case non-cryptographic methods are used. [sent-51, score-0.334]

39 Typical active learning applications assume that the distribution of class size is similar [2, 11]. [sent-52, score-0.101]

40 A notable exception is the work of [8] that propose an active learning method for anomaly detection. [sent-53, score-0.124]

41 Our case is similar as image patches that contain faces are rare in an image. [sent-54, score-0.472]

42 3 Privacy-preserving Feature Selection Feature selection aims at ﬁnding a subset of the features that optimize some objective function, typically a classiﬁcation task [6]. [sent-55, score-0.073]

43 However, feature selection does not concern itself with the correlation of the feature subset with the original signal. [sent-56, score-0.136]

44 This is handled with the information bottleneck method [10], that takes a joint distribution p(x, y) and ﬁnds a compressed representation of X, denoted by T , that is as informative about Y . [sent-57, score-0.056]

45 We map the information bottleneck idea to a feature selection algorithm to obtain a Privacypreserving Feature Selection (PPFS) and describe how Bob can construct such a feature set. [sent-60, score-0.212]

46 Let Bob have a training set of image patches, their associated label and a weight associated with every feature (pixel) denoted {xn , yn , sn }N . [sent-61, score-0.254]

47 Formally, Bob needs to minimize: N (F (xn (I)) − yn ))2 min F (2) n=1 si < Λ subject to i∈I where Λ is a user deﬁned threshold that deﬁnes the amount of information that can be leaked. [sent-68, score-0.111]

48 We found it useful to use the PCA spectrum to measure the amount of information. [sent-69, score-0.068]

49 Speciﬁcally, Bob computes the PCA space of all the face images in his database and maps all the data to that space, without reducing dimensionality. [sent-70, score-0.125]

50 This avoids the need to compute the mutual information between pixels by making the assumption that features do not carry mutual information with other features beyond second order statistics. [sent-72, score-0.066]

51 Algorithm 1 Privacy-Preserving Feature Selection Input: {xn , yn , sn }N n=1 Threshold Λ Number of iterations T Output: A privacy-preserving strong classiﬁer F (x) • Start with weights wn = 1/N n = 1, 2, . [sent-73, score-0.11]

52 In each iteration Bob can use features that were already selected or those that adding them will not increase the total weight of selected features beyond the threshold Λ. [sent-84, score-0.134]

53 Once Bob computed the privacy-preserving feature subset, the amount of information it leaks and its classiﬁcation accuracy he publishes this information on the web. [sent-85, score-0.083]

54 Alice then needs to map her image patches to this low-dimensional privacy-preserving feature space and send the data to Bob for classiﬁcation. [sent-86, score-0.54]

55 4 Privacy-Preserving Active Learning In our face detection example Alice needs to submit many image patches to Bob for classiﬁcation. [sent-87, score-0.595]

56 This is computationally expensive if SMC methods are used and reveals information, in case the privacy-preserving feature selection method discussed earlier is used. [sent-88, score-0.088]

57 Hence, it would be beneﬁcial if Alice could minimize the number of image patches she needs to send Bob for classiﬁcation. [sent-89, score-0.492]

58 Instead of raster scanning the image and submitting every image patch for classiﬁcation she sends a small number of randomly selected image patches, and based on their label, she determines the next group of image patches to be sent for classiﬁcation. [sent-91, score-1.007]

59 Let {cj , yj }M be the list of M prototypes that were labeled so far. [sent-94, score-0.061]

60 The score of each image patch x is given by h(x) = [k(x, c1 ), . [sent-100, score-0.191]

61 For the next round of classiﬁcation Alice chooses the image patches with the highest h(x) score. [sent-104, score-0.416]

62 In our case, Alice is interested in ﬁnding image patches that contain faces (which we assume are labeled +1) but most of the prototypes will be labeled −1, because faces are a rear event in an image. [sent-106, score-0.627]

63 As long as Alice does not sample a face image patch she will keep exploring the space of image patches in her image, by sampling image patches that are farthest away from the current set of prototypes. [sent-107, score-1.113]

64 If an image patch that contains a face is sampled, then her online classiﬁer h(x) will label similar image patches with a high score, thus guiding the search towards other image patches that might contain a face. [sent-108, score-1.176]

65 To avoid large overlap between patches, we force a minimum distance, in the image plane, between selected patches. [sent-109, score-0.17]

66 The information leakage is deﬁned as the amount of PCA spectrum captured by the features used in each classiﬁer. [sent-133, score-0.147]

67 The number in parenthesis shows how much of the eigen spectrum is captured by the features used in each classiﬁer. [sent-134, score-0.066]

68 The ﬁrst experiment evaluates the privacy-preserving feature selection method. [sent-135, score-0.088]

69 The training set consisted of 9666 image patches of size 24 × 24 pixels each, split evenly to face/no-face images. [sent-136, score-0.416]

70 1 gives identical results to a full classiﬁer, without any privacy constraints. [sent-141, score-0.162]

71 05 from the previous experiment, and measure how effective is the on-line classiﬁer that Alice constructs in rejecting no-face image patches. [sent-146, score-0.25]

72 One is the full classiﬁer that Bob owns, the second is the privacy-preserving classiﬁer that Bob owns and the last is the on-line classiﬁer that Alice constructs. [sent-148, score-0.095]

73 Alice uses the labels of Bobs’ privacy-preserving classiﬁer to construct her on-line classiﬁer and the questions is: how many image patches she can reject, without actually rejecting image patches that will be classiﬁed as faces by the full classiﬁer (that she knows nothing about)? [sent-149, score-1.036]

74 Before we performed the experiment, we conducted the following pre-processing operation: We ﬁnd, for each image, the scale at which the largest number of faces are detected using Bob’s full classiﬁer, and used only the image at that scale. [sent-150, score-0.285]

75 Alice chooses 5 image patches in each round, maps them to the reduced PCA space and sends them to Bob for classiﬁcation, using his privacy-preserving classiﬁer. [sent-152, score-0.455]

76 Based on his labels, Alice then picks the next 5 image patches according to algorithm 2 and so on. [sent-153, score-0.416]

77 Alice repeats the process 10 times, resulting in 50 patches that are sent to Bob for classiﬁcation. [sent-154, score-0.289]

78 Figure 2 shows the 50 patches selected by Alice, the online classiﬁer h and the corresponding rejection/recall curve, for several test images. [sent-156, score-0.355]

79 The rejection/recall curve shows how many image patches Alice can safely reject, based on h, without rejecting a face that will be detected by Bobs’ full classiﬁer. [sent-157, score-0.695]

80 For example, in the top row of ﬁgure 2 we see that rejecting the bottom 40% of image patches based on the on-line classiﬁer h will not reject any face that can be detected with the full classiﬁer. [sent-158, score-0.769]

81 Thus 50 image patches that can be quickly labeled while leaking very little information can help Alice reject thousands of image patches. [sent-159, score-0.789]

82 We found that, on average (dashed line), 1 We used the 65 images in the newtest directory of the CMU+MIT dataset (a-1) (b-1) (c-1) (a-2) (b-2) (c-2) (a-3) (b-3) (c-3) Figure 2: Examples of privacy-preserving feature selection and active learning. [sent-162, score-0.224]

83 (a) The input images and the image patches (marked with white rectangles) selected by the active learning algorithm. [sent-163, score-0.575]

84 (b) The response image computed by the online classiﬁer (the black spots correspond to the position of the selected image patches). [sent-164, score-0.38]

85 (c) The rejection/recall curve showing how many image patches can be safely rejected. [sent-166, score-0.442]

86 For example, panel (c-1) shows that Alice can reject almost 50% of the image patches, based on her online classiﬁer (i. [sent-167, score-0.31]

87 , response image), and not miss a face that can be detected by the full classiﬁer (that is known to Bob and not to Alice). [sent-169, score-0.174]

88 The ﬁgure shows how many image patches can be rejected, based on the online classiﬁer that Alice owns, without rejecting a face. [sent-172, score-0.582]

89 The horizontal axis shows how many image patches are rejected, based on the on-line classiﬁer, and the vertical axis shows how many faces are maintained. [sent-173, score-0.472]

90 For example, the ﬁgure shows (dashed line) that rejecting 20% of all image patches, based on the on-line classiﬁer, will maintain 80% of all faces. [sent-174, score-0.25]

91 The solid line shows that rejecting 40% of all image patches, based on the on-line classiﬁer, will not miss a face in at least half (i. [sent-175, score-0.364]

92 using only 50 labeled image patches Alice can reject up to about 20% of the image patches in an image while keeping 80% of the faces in that image (i. [sent-178, score-1.32]

93 , Alice will reject 20% of the image patches that Bob’s full classiﬁer will classify as a face). [sent-180, score-0.563]

94 If we look at the median (solid line), we see that for at least half the images in the data set, Alice can reject a little more than 40% of the image patches without erroneously rejecting a face. [sent-181, score-0.654]

95 6 Conclusions We described two machine learning methods to accelerate cryptographically secure classiﬁcation protocols. [sent-183, score-0.269]

96 The methods greatly accelerate the performance of the system, while leaking a controlled amount of information. [sent-184, score-0.167]

97 The two methods are a privacy preserving feature selection that is similar to the information bottleneck and an active learning technique that was found to be useful in learning a rejector from an extremely small number of labeled data. [sent-185, score-0.509]

98 We plan to keep investigating these methods, apply them to classiﬁcation tasks in other domains and develop new methods to make secure classiﬁcation faster to use. [sent-186, score-0.193]

99 How to play any mental game or a completeness theorem for protocols with honest majority. [sent-212, score-0.104]

100 Support vector machine active learning with applications to text classiﬁcation. [sent-243, score-0.101]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('alice', 0.548), ('bob', 0.528), ('patches', 0.269), ('secure', 0.193), ('classi', 0.152), ('image', 0.147), ('er', 0.144), ('privacy', 0.137), ('smc', 0.107), ('rejecting', 0.103), ('active', 0.101), ('reject', 0.1), ('parties', 0.091), ('face', 0.09), ('leaking', 0.088), ('avidan', 0.07), ('bobs', 0.07), ('owns', 0.07), ('reluctant', 0.07), ('seller', 0.07), ('protocols', 0.069), ('online', 0.063), ('stump', 0.061), ('bottleneck', 0.056), ('faces', 0.056), ('send', 0.055), ('preserving', 0.054), ('buyers', 0.053), ('cryptographically', 0.053), ('gentleboost', 0.053), ('wn', 0.051), ('feature', 0.048), ('cryptographic', 0.046), ('leakage', 0.046), ('submit', 0.046), ('service', 0.044), ('patch', 0.044), ('revealing', 0.042), ('selection', 0.04), ('sends', 0.039), ('labeled', 0.038), ('anything', 0.037), ('detected', 0.035), ('images', 0.035), ('butman', 0.035), ('buyer', 0.035), ('clients', 0.035), ('crypto', 0.035), ('cryptography', 0.035), ('honest', 0.035), ('rejector', 0.035), ('securely', 0.035), ('internet', 0.035), ('amount', 0.035), ('spectrum', 0.033), ('couple', 0.033), ('ers', 0.033), ('features', 0.033), ('yn', 0.033), ('protocol', 0.031), ('blind', 0.031), ('cj', 0.031), ('pca', 0.029), ('money', 0.028), ('variant', 0.027), ('offer', 0.026), ('sn', 0.026), ('ku', 0.026), ('safely', 0.026), ('detector', 0.026), ('ft', 0.025), ('full', 0.025), ('raster', 0.024), ('oracle', 0.024), ('miss', 0.024), ('cmu', 0.024), ('content', 0.023), ('selected', 0.023), ('prototypes', 0.023), ('ej', 0.023), ('release', 0.023), ('anomaly', 0.023), ('accelerate', 0.023), ('tools', 0.022), ('conducted', 0.022), ('rejected', 0.022), ('calls', 0.022), ('spent', 0.022), ('threshold', 0.022), ('repeat', 0.022), ('classify', 0.022), ('xn', 0.022), ('detection', 0.022), ('kij', 0.021), ('controlled', 0.021), ('needs', 0.021), ('aj', 0.021), ('construct', 0.02), ('sent', 0.02), ('lot', 0.02)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999994 73 nips-2006-Efficient Methods for Privacy Preserving Face Detection

Author: Shai Avidan, Moshe Butman

2 0.12178982 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.10431632 8 nips-2006-A Nonparametric Approach to Bottom-Up Visual Saliency

Author: Wolf Kienzle, Felix A. Wichmann, Matthias O. Franz, Bernhard Schölkopf

Abstract: This paper addresses the bottom-up inﬂuence of local image information on human eye movements. Most existing computational models use a set of biologically plausible linear ﬁlters, e.g., Gabor or Difference-of-Gaussians ﬁlters as a front-end, the outputs of which are nonlinearly combined into a real number that indicates visual saliency. Unfortunately, this requires many design parameters such as the number, type, and size of the front-end ﬁlters, as well as the choice of nonlinearities, weighting and normalization schemes etc., for which biological plausibility cannot always be justiﬁed. As a result, these parameters have to be chosen in a more or less ad hoc way. Here, we propose to learn a visual saliency model directly from human eye movement data. The model is rather simplistic and essentially parameter-free, and therefore contrasts recent developments in the ﬁeld that usually aim at higher prediction rates at the cost of additional parameters and increasing model complexity. Experimental results show that—despite the lack of any biological prior knowledge—our model performs comparably to existing approaches, and in fact learns image features that resemble ﬁndings from several previous studies. In particular, its maximally excitatory stimuli have center-surround structure, similar to receptive ﬁelds in the early human visual system. 1

4 0.096016914 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.080796525 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

6 0.070344679 20 nips-2006-Active learning for misspecified generalized linear models

7 0.065578774 130 nips-2006-Max-margin classification of incomplete data

8 0.061743896 42 nips-2006-Bayesian Image Super-resolution, Continued

9 0.059583772 193 nips-2006-Tighter PAC-Bayes Bounds

10 0.058549795 66 nips-2006-Detecting Humans via Their Pose

11 0.058447104 186 nips-2006-Support Vector Machines on a Budget

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

13 0.055301283 156 nips-2006-Ordinal Regression by Extended Binary Classification

14 0.054767337 51 nips-2006-Clustering Under Prior Knowledge with Application to Image Segmentation

15 0.051601067 52 nips-2006-Clustering appearance and shape by learning jigsaws

16 0.049533285 57 nips-2006-Conditional mean field

17 0.048763026 11 nips-2006-A PAC-Bayes Risk Bound for General Loss Functions

18 0.048214369 65 nips-2006-Denoising and Dimension Reduction in Feature Space

19 0.047552906 33 nips-2006-Analysis of Representations for Domain Adaptation

20 0.046628963 76 nips-2006-Emergence of conjunctive visual features by quadratic independent component analysis

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.154), (1, 0.026), (2, 0.077), (3, -0.058), (4, -0.024), (5, 0.055), (6, -0.176), (7, -0.047), (8, 0.004), (9, 0.036), (10, 0.096), (11, 0.053), (12, 0.052), (13, -0.042), (14, 0.053), (15, 0.056), (16, 0.031), (17, -0.002), (18, 0.018), (19, 0.043), (20, 0.057), (21, 0.043), (22, -0.013), (23, -0.016), (24, 0.056), (25, -0.024), (26, -0.063), (27, 0.103), (28, -0.005), (29, -0.056), (30, 0.062), (31, 0.048), (32, -0.013), (33, -0.0), (34, 0.004), (35, 0.022), (36, 0.064), (37, -0.073), (38, 0.107), (39, -0.03), (40, 0.034), (41, -0.011), (42, 0.044), (43, 0.099), (44, -0.032), (45, -0.094), (46, -0.09), (47, 0.04), (48, -0.065), (49, -0.021)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.92857295 73 nips-2006-Efficient Methods for Privacy Preserving Face Detection

Author: Shai Avidan, Moshe Butman

2 0.73861909 50 nips-2006-Chained Boosting

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

3 0.63960487 52 nips-2006-Clustering appearance and shape by learning jigsaws

Author: Anitha Kannan, John Winn, Carsten Rother

Abstract: Patch-based appearance models are used in a wide range of computer vision applications. To learn such models it has previously been necessary to specify a suitable set of patch sizes and shapes by hand. In the jigsaw model presented here, the shape, size and appearance of patches are learned automatically from the repeated structures in a set of training images. By learning such irregularly shaped ‘jigsaw pieces’, we are able to discover both the shape and the appearance of object parts without supervision. When applied to face images, for example, the learned jigsaw pieces are surprisingly strongly associated with face parts of different shapes and scales such as eyes, noses, eyebrows and cheeks, to name a few. We conclude that learning the shape of the patch not only improves the accuracy of appearance-based part detection but also allows for shape-based part detection. This enables parts of similar appearance but different shapes to be distinguished; for example, while foreheads and cheeks are both skin colored, they have markedly different shapes. 1

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

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

5 0.56746846 94 nips-2006-Image Retrieval and Classification Using Local Distance Functions

Author: Andrea Frome, Yoram Singer, Jitendra Malik

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

7 0.5486384 170 nips-2006-Robotic Grasping of Novel Objects

8 0.54352063 78 nips-2006-Fast Discriminative Visual Codebooks using Randomized Clustering Forests

9 0.50537026 156 nips-2006-Ordinal Regression by Extended Binary Classification

10 0.49194551 42 nips-2006-Bayesian Image Super-resolution, Continued

11 0.48552209 193 nips-2006-Tighter PAC-Bayes Bounds

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

13 0.44927424 51 nips-2006-Clustering Under Prior Knowledge with Application to Image Segmentation

14 0.44807881 130 nips-2006-Max-margin classification of incomplete data

15 0.41866928 174 nips-2006-Similarity by Composition

16 0.41858411 199 nips-2006-Unsupervised Learning of a Probabilistic Grammar for Object Detection and Parsing

17 0.40582603 66 nips-2006-Detecting Humans via Their Pose

18 0.40388995 72 nips-2006-Efficient Learning of Sparse Representations with an Energy-Based Model

19 0.391065 105 nips-2006-Large Margin Component Analysis

20 0.38571087 186 nips-2006-Support Vector Machines on a Budget

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(1, 0.542), (3, 0.018), (7, 0.054), (9, 0.024), (22, 0.03), (44, 0.056), (57, 0.1), (65, 0.038), (69, 0.022)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.99688214 186 nips-2006-Support Vector Machines on a Budget

Author: Ofer Dekel, Yoram Singer

Abstract: The standard Support Vector Machine formulation does not provide its user with the ability to explicitly control the number of support vectors used to deﬁne the generated classiﬁer. We present a modiﬁed version of SVM that allows the user to set a budget parameter B and focuses on minimizing the loss attained by the B worst-classiﬁed examples while ignoring the remaining examples. This idea can be used to derive sparse versions of both L1-SVM and L2-SVM. Technically, we obtain these new SVM variants by replacing the 1-norm in the standard SVM formulation with various interpolation-norms. We also adapt the SMO optimization algorithm to our setting and report on some preliminary experimental results. 1

2 0.99444616 46 nips-2006-Blind source separation for over-determined delayed mixtures

Author: Lars Omlor, Martin Giese

Abstract: Blind source separation, i.e. the extraction of unknown sources from a set of given signals, is relevant for many applications. A special case of this problem is dimension reduction, where the goal is to approximate a given set of signals by superpositions of a minimal number of sources. Since in this case the signals outnumber the sources the problem is over-determined. Most popular approaches for addressing this problem are based on purely linear mixing models. However, many applications like the modeling of acoustic signals, EMG signals, or movement trajectories, require temporal shift-invariance of the extracted components. This case has only rarely been treated in the computational literature, and speciﬁcally for the case of dimension reduction almost no algorithms have been proposed. We present a new algorithm for the solution of this problem, which is based on a timefrequency transformation (Wigner-Ville distribution) of the generative model. We show that this algorithm outperforms classical source separation algorithms for linear mixtures, and also a related method for mixtures with delays. In addition, applying the new algorithm to trajectories of human gaits, we demonstrate that it is suitable for the extraction of spatio-temporal components that are easier to interpret than components extracted with other classical algorithms. 1

3 0.98645264 63 nips-2006-Cross-Validation Optimization for Large Scale Hierarchical Classification Kernel Methods

Author: Matthias Seeger

Abstract: We propose a highly efﬁcient framework for kernel multi-class models with a large and structured set of classes. Kernel parameters are learned automatically by maximizing the cross-validation log likelihood, and predictive probabilities are estimated. We demonstrate our approach on large scale text classiﬁcation tasks with hierarchical class structure, achieving state-of-the-art results in an order of magnitude less time than previous work. 1

4 0.98568302 142 nips-2006-Mutagenetic tree Fisher kernel improves prediction of HIV drug resistance from viral genotype

Author: Tobias Sing, Niko Beerenwinkel

Abstract: Starting with the work of Jaakkola and Haussler, a variety of approaches have been proposed for coupling domain-speciﬁc generative models with statistical learning methods. The link is established by a kernel function which provides a similarity measure based inherently on the underlying model. In computational biology, the full promise of this framework has rarely ever been exploited, as most kernels are derived from very generic models, such as sequence proﬁles or hidden Markov models. Here, we introduce the MTreeMix kernel, which is based on a generative model tailored to the underlying biological mechanism. Speciﬁcally, the kernel quantiﬁes the similarity of evolutionary escape from antiviral drug pressure between two viral sequence samples. We compare this novel kernel to a standard, evolution-agnostic amino acid encoding in the prediction of HIV drug resistance from genotype, using support vector regression. The results show signiﬁcant improvements in predictive performance across 17 anti-HIV drugs. Thus, in our study, the generative-discriminative paradigm is key to bridging the gap between population genetic modeling and clinical decision making. 1

same-paper 5 0.98088652 73 nips-2006-Efficient Methods for Privacy Preserving Face Detection

Author: Shai Avidan, Moshe Butman

6 0.86621034 179 nips-2006-Sparse Representation for Signal Classification

7 0.85450494 152 nips-2006-Online Classification for Complex Problems Using Simultaneous Projections

8 0.85368228 108 nips-2006-Large Scale Hidden Semi-Markov SVMs

9 0.84973902 84 nips-2006-Generalized Regularized Least-Squares Learning with Predefined Features in a Hilbert Space

10 0.82883316 138 nips-2006-Multi-Task Feature Learning

11 0.8056798 178 nips-2006-Sparse Multinomial Logistic Regression via Bayesian L1 Regularisation

12 0.80325389 177 nips-2006-Sparse Kernel Orthonormalized PLS for feature extraction in large data sets

13 0.80276757 82 nips-2006-Gaussian and Wishart Hyperkernels

14 0.80226201 140 nips-2006-Multiple Instance Learning for Computer Aided Diagnosis

15 0.79956967 51 nips-2006-Clustering Under Prior Knowledge with Application to Image Segmentation

16 0.79645616 111 nips-2006-Learning Motion Style Synthesis from Perceptual Observations

17 0.79351044 75 nips-2006-Efficient sparse coding algorithms

18 0.79117942 130 nips-2006-Max-margin classification of incomplete data

19 0.79045206 65 nips-2006-Denoising and Dimension Reduction in Feature Space

20 0.78271276 99 nips-2006-Information Bottleneck Optimization and Independent Component Extraction with Spiking Neurons