nips nips2012 nips2012-83 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Vasiliy Karasev, Alessandro Chiuso, Stefano Soatto
Abstract: We describe the tradeoff between the performance in a visual recognition problem and the control authority that the agent can exercise on the sensing process. We focus on the problem of “visual search” of an object in an otherwise known and static scene, propose a measure of control authority, and relate it to the expected risk and its proxy (conditional entropy of the posterior density). We show this analytically, as well as empirically by simulation using the simplest known model that captures the phenomenology of image formation, including scaling and occlusions. We show that a “passive” agent given a training set can provide no guarantees on performance beyond what is afforded by the priors, and that an “omnipotent” agent, capable of infinite control authority, can achieve arbitrarily good performance (asymptotically). In between these limiting cases, the tradeoff can be characterized empirically. 1
Reference: text
sentIndex sentText sentNum sentScore
1 We focus on the problem of “visual search” of an object in an otherwise known and static scene, propose a measure of control authority, and relate it to the expected risk and its proxy (conditional entropy of the posterior density). [sent-2, score-0.683]
2 We show that a “passive” agent given a training set can provide no guarantees on performance beyond what is afforded by the priors, and that an “omnipotent” agent, capable of infinite control authority, can achieve arbitrarily good performance (asymptotically). [sent-4, score-0.376]
3 1 Introduction We are interested in visual learning for recognition of objects and scenes embedded in physical space. [sent-6, score-0.235]
4 Rather than using datasets consisting of collections of isolated snapshots, however, we wish to actively control the sensing process during learning. [sent-7, score-0.296]
5 Visual learning is thus a process of discovery, literally uncovering occluded portions of an object or scene, and viewing it from close enough that all structural details are revealed. [sent-9, score-0.306]
6 1 We call this phase of learning exploration or mapping, accomplished by actively controlling the sensor motion within a scene, or by manipulating an object so as to discover all aspects. [sent-10, score-0.445]
7 2 Once exploration has been performed, one has a model (or “map” or “representation”) of the scene or object of interest. [sent-11, score-0.505]
8 One can then attempt to detect, localize or recognize a particular object or scene, or a class of them, provided intra-class variability has been exposed during exploration. [sent-12, score-0.27]
9 This phase can yield localization – where one wishes to recognize a portion of a mapped scene and, as a byproduct, infer the pose relative to the map – or search where a particular object mapped during the exploration phase is detected and localized within an otherwise known scene. [sent-13, score-0.684]
10 2 Note that we are not suggesting that one should construct a three-dimensional (3-D) model of an object or a scene for recognition, as opposed to using collections of 2-D images. [sent-16, score-0.418]
11 The multiple images must portray the same scene or object, lest one cannot attribute the variability in the data to nuisance factors as opposed to intrinsic variability of the object of interest. [sent-19, score-0.493]
12 1 where a known object is sought in an unknown map, exploration and search have to be conducted simultaneously. [sent-22, score-0.459]
13 Within this scenario, exploration and search can be framed as optimal control and optimal stopping time problems. [sent-23, score-0.358]
14 In this manuscript we consider the problem of detecting and estimating discrete parameters of an unknown object in a known environment. [sent-26, score-0.285]
15 Discuss the tradeoff between performance in a visual decision task and the control authority that the explorer possesses. [sent-31, score-0.85]
16 This tradeoff is akin the tradeoff between rate and distortion in a communication system, but it pertains to decision and control tasks, as opposed to the transmission of data. [sent-32, score-0.349]
17 We characterize this tradeoff for the simple case of a static environment, where control authority relates to reachability and energy. [sent-33, score-0.62]
18 Discuss and test algorithms for visual search based on the maximization of the conditional entropy of future measurements and the proxies of this quantity. [sent-35, score-0.452]
19 These algorithms can be used to locate an unknown object in unknown position of a known environment, or to perform change detection in an otherwise known map, for the purpose of updating it. [sent-36, score-0.331]
20 1 Related prior work Active search and recognition of objects in the scene has been one of the mainstays of Active Perception in the eighties [2, 3], and has recently resurged (see [4] and references therein). [sent-40, score-0.39]
21 Active recognition using next-best-view generation and object appearance is discussed in [6] where authors use PCA to embed object images in a linear, low dimensional space. [sent-42, score-0.558]
22 More recently, information driven sensor control for object recognition was used in [7, 8, 9], who deal with visual and sonar sensors, but take features (e. [sent-44, score-0.639]
23 A utility function that accounts for occlusions, viewing angle, and distance to the object is proposed in [10] who aim to actively learn object classifiers during the training stage. [sent-47, score-0.548]
24 Exploration and learning of 3D object surface models by robotic manipulation is discussed in [11]. [sent-48, score-0.282]
25 The case of object localization (and tracking if object is moving) is discussed in [12]; information-theoretic approach for solving this problem using a sensor network is described in [13]. [sent-49, score-0.564]
26 With regards to models, our work is different in several aspects: instead of choosing the next best view on a sphere centered at the object, we model a cluttered environment where the object of interest occupies a negligible volume and is therefore fully occluded when viewed from most locations. [sent-52, score-0.419]
27 Third, given the significance of quantization-scale and occlusions in a visual recognition task, we model the sensing process such that it accounts for both. [sent-54, score-0.246]
28 We use the problem of visual search (finding a not previously seen object in a scene) as a motivation. [sent-64, score-0.407]
29 Constraints on the controller enter through f ; photometric nuisances, quantization and occlusions enter through the measurement map h. [sent-67, score-0.297]
30 1 Signal models The simplest model that includes both scaling and occlusion nuisances is the “cartoon flatland”, where a bounded subset of R2 is populated by self-luminous line segments, corresponding to clutter objects. [sent-70, score-0.401]
31 The number of objects in the scene C is the clutter density parameter that can possibly grow to be infinite in the limit. [sent-75, score-0.499]
32 Each object is described by its center (ck ), length (lk ), binary orientation (ok ), and radiance function supported on the segment ⇢k . [sent-76, score-0.358]
33 R+ ] (3) An agent can move continuously throughout the search domain. [sent-78, score-0.249]
34 We take the state gt 2 R2 to be its current position, ut 2 R2 the currently exerted move, and assume trivial dynamics: gt+1 = gt + ut . [sent-79, score-0.942]
35 More complex agents where gt 2 SE(3) can be incorporated without conceptual difficulties. [sent-80, score-0.234]
36 The measurement model is that of an omnidirectional m-pixel camera, with each entry of yt 2 Rm in (2) given by: Z (i+ 1 ) 2⇡ Z 1 2 m yt (i) = ⇢`(✓,gt ) (z)d✓d⌧ + nt (i), with z = (⌧ cos(✓), ⌧ sin(✓)) (4) (i 1 2⇡ 2) m 0 where is the angle subtended by each pixel. [sent-81, score-0.666]
37 The index of the object (clutter or object of interest) that contributes to the image is denoted by `(✓, gt ) and is defined as: ✓ ◆ n o l k lk ok `(✓, gt ) = arg min k 9(sk , k ) 2 [ , ] ⇥ R+ s. [sent-84, score-1.128]
38 ck , lk , and ok ˆ are k-th segment center, length, and orientation. [sent-87, score-0.251]
39 In order to design control sequences to minimize risk, we need to evaluate the uncertainty of future measurements, those we have not yet measured, which are a function of the control action to be taken. [sent-95, score-0.4]
40 3 We first describe the general case of visual exploration where the environment is unknown. [sent-97, score-0.287]
41 The density can be decomposed as a product of likelihoods since knowledge of environment (⇠) and location (gt ) is sufficient to predict measurement yt up to Gaussian noise. [sent-107, score-0.554]
42 In this paper we focus on visual search of a particular object in an otherwise known environment, so marginalization is only performed with respect to a single object in the environment, x, whose parameters are discrete, but otherwise analogous to (6): p(x) = U {0, . [sent-109, score-0.677]
43 , |X | object with parameters (ci , li , oi , ⇢i ) and write ⇠i = (xi , 1 , . [sent-118, score-0.239]
44 , C ) to denote the scene with known clutter objects 1 , . [sent-121, score-0.448]
45 This depends upon whether ut is sufficiently exciting, a “richness” condition that has been extensively used in the identification and adaptive control literature [17, 18], which guarantees that the state trajectory g t explores the space of interest. [sent-130, score-0.421]
46 Under this scenario it is easy to prove that, averaging over the possible scenes and initial agent locations, the probability of error approaches chance (i. [sent-134, score-0.225]
47 that given by the prior distribution) as clutter density and/or the environment volume increase. [sent-136, score-0.395]
48 Full control on g t : if the control action can take the “omnipotent agent” anywhere, and infinite time is available to collect measurements, then the conditional entropy H(x|y t ) decreases asymptotically to zero thus providing arbitrarily good recognition rate in the limit. [sent-138, score-0.659]
49 yt+T ) 4 In general, there is a tradeoff between the ability to gather new information through suitable control actions, which we name “control authority”, and the recognition rate. [sent-151, score-0.294]
50 In the sequel we shall propose a measure for the “control authority” over the sensing process; later in the paper we will consider conditional entropy as a proxy (upper bound) on probability of error and evaluate empirically how control authority affects the conditional entropy decrease. [sent-152, score-1.092]
51 1 Control authority Unlike the passive case, in the controlled scenario time plays an important role. [sent-154, score-0.446]
52 If objects in the scene move, this can be done only at an expense in energy, and achieving asymptotic performance may not be possible under control limitations. [sent-157, score-0.438]
53 Control authority depends on (i) the controller u, as measured for instance by a norm5 kuk : U [0, T ] ! [sent-160, score-0.501]
54 We propose to measure control authority in the following manner: associate to each pair of locations in the state space (go , gf ) and a given time horizon T the cost kuk required to move from go at time t = 0 to gf at time t = T along a minimum cost path i. [sent-162, score-1.218]
55 J⇠ (go , gf , T ) = inf kuk (13) u : gu (0)=go ,gu (T )=gf ⇠ where gu (t) is the state vector at time t under control u. [sent-165, score-0.503]
56 If gf is not reachable from go in time T we set J⇠ (go , gf , T ) = 1. [sent-166, score-0.662]
57 This will depend on the dynamical properties of the agent g = f (g, u) (or ˙ gt+1 = f (gt , ut ) for discrete time) as well as on the scene ⇠ where the agent has to navigate through while avoiding obstacles. [sent-167, score-0.74]
58 The control authority (CA) can be measured via the volume of the reachable space for fixed control cost, and will be a function of the initial configuration g0 and of the scene ⇠, i. [sent-168, score-1.095]
59 CA(k, go , ⇠) = V ol{gf : J⇠ (g0 , gf , k) 1} (14) If instead one is interested in average performance (e. [sent-171, score-0.319]
60 the possible scene distributions with fixed clutter density), a reasonable measure is the average of smallest volume (as g0 varies) of the reachable space with a unit cost input ⇥ ⇤ . [sent-176, score-0.546]
61 CA(k) = E⇠ inf CA(k, go , ⇠) (15) go If planning on an indefinitely long time horizon is allowed, then one would minimize J(go , gf , T ) over time T : . [sent-177, score-0.515]
62 J(go , gf ) = inf J(go , gf , T ) (16) T with 0 . [sent-178, score-0.435]
63 CA1 = inf (V ol{gf : J(go , gf ) 1}) go (17) The figures CA(k, go , ⇠) in (14), CA(k) and CA1 in (17) are proxies of the exploration ability which, in turn, is related to the ability to gather new information on the task at hand. [sent-179, score-0.588]
64 The data acquisition process can be regarded as an experiment design problem [16] where the choice of the control signal guides the experiment. [sent-180, score-0.216]
65 More control authority corresponds to more freedom in the choice of which samples one is taking (from which location and at which scale). [sent-183, score-0.603]
66 Therefore the risk, considered against CA(k) in (15), CA(k, go , ⇠) in (14) or CA1 in (17) will follow a surface that depends on the clutter: For any given clutter (or clutter density), the risk will be a monotonically non-increasing function of control authority CA(k). [sent-184, score-1.117]
67 As is standard, we can settle for the greedy k = 1 case: Z u⇤ = arg min p(yt+1 |y t , ut ) 1 max p(xi |y t , yt+1 , ut ) dyt+1 t ut i (19) but it is still often impractical. [sent-189, score-0.747]
68 H(yt+1 |y t , ut ) is the entropy of a Gaussian mixture distribution which can be easily approximated by Monte Carlo, and for which both lower [20] and upper bounds [21] are known. [sent-191, score-0.449]
69 is unable to traverse the environment in one step, optimization is taken over a small ball in R2 centered at current location gt . [sent-194, score-0.426]
70 Since this location is typically not reachable in a single step, one can adopt a “stubborn” strategy that follows the planned path to the target location before choosing next action, and an “indecisive” – that replans as soon as additional information becomes available as a consequence of motion. [sent-197, score-0.336]
71 We demonstrate the characteristics of conditional entropy as a criterion for planning in Fig. [sent-198, score-0.255]
72 To test average performance of these strategies, we consider search in 100 environment instances, each containing 40 known clutter objects and one unknown object. [sent-204, score-0.521]
73 Clutter objects are sampled from the continuous prior distribution (6) and unknown object is chosen from the prior (10) discretized to |X | ⇡ 9000. [sent-205, score-0.394]
74 Agent’s sensor has m = 30 pixels, with additive noise set to half of the difference between object colors. [sent-206, score-0.325]
75 Search is terminated once residual entropy falls below a threshold value: H(x|y t ) < 0. [sent-208, score-0.225]
76 In all cases, the agent is at the bottom of the environment, and a small unknown object is at the top. [sent-212, score-0.447]
77 The agent has made one measurement (y1 ) and must now determine the best location to visit. [sent-213, score-0.279]
78 The left three panels demonstrate a case of scaling: object is seen, but due to noise and quantization its parameters are uncertain. [sent-214, score-0.269]
79 Agent gains information if putative object location (top) is approached. [sent-215, score-0.283]
80 Middle three panels demonstrate partial occlusion: a part of the object has been seen, and there is now a region (bottom right corner) that is uninformative – measurements taken there are predictable. [sent-216, score-0.282]
81 The object has not been seen (due to occluder in the middle of the environment) and the best action is to visit new area. [sent-218, score-0.271]
82 Objects are colored according to their radiance and the unknown object is shown as a thick line. [sent-223, score-0.354]
83 we define as the excess fraction of the minimum energy path to the center of the unknown object (c0 ) . [sent-230, score-0.38]
84 Because it is not always necessary to reach the object to recognize it (viewing it closely from multiple viewpoints may be sufficient), this quantity is an approximation to minimum search effort. [sent-232, score-0.357]
85 “Random-walk” strategy was unable to find the object unless it was visible initially or became visible by chance. [sent-241, score-0.268]
86 We next indecisive stubborn Average search duration max-ent max-var max-p(x|y t ) 28. [sent-242, score-0.407]
87 prior entropy environment volume reachable volume without clutter Figure 4: Left: Control authority. [sent-258, score-0.691]
88 Right: Residual entropy H(x|y t ), as a function of control authority and clutter density. [sent-261, score-0.927]
89 Lines correspond to residual entropy for a given control authority averaged over the test suite; markers – to residual entropy on a specific problem instance. [sent-263, score-1.009]
90 For certain scenes, agent is unable to significantly reduce entropy because the object never becomes unoccluded (once object is seen, there is a sharp drop in residual entropy, as shown in Fig. [sent-264, score-0.894]
91 empirically evaluated explorer’s exploration ability under finite control authority. [sent-266, score-0.301]
92 Reachable volume was computed by Monte Carlo sampling, following (14)-(15) for several clutter density values. [sent-267, score-0.276]
93 For each clutter density, we generated 40 scene instances and tested ”indecisive” max-entropy strategy with respect to control authority. [sent-268, score-0.557]
94 We have then related the amount of “control authority” the agent can exercise during the data acquisition process with the performance in the visual search task. [sent-273, score-0.393]
95 In the limit of infinite control authority, arbitrarily good decision performance can be attained. [sent-275, score-0.227]
96 In between, we have empirically characterized the tradeoff between decision performance and control authority. [sent-276, score-0.318]
97 Active perception and scene modeling by planning with probabilistic 6d object poses. [sent-315, score-0.463]
98 Robotic object detection: Learning to improve the classifiers using sparse graphs for path planning. [sent-335, score-0.293]
99 Autonomous generation of complete 3d object models using next best view manipulation planning. [sent-341, score-0.239]
100 Mobile sensor network control using mutual information methods and particle filters. [sent-356, score-0.27]
wordName wordTfidf (topN-words)
[('authority', 0.375), ('yt', 0.267), ('object', 0.239), ('ut', 0.237), ('gt', 0.234), ('gf', 0.201), ('clutter', 0.194), ('control', 0.184), ('scene', 0.179), ('entropy', 0.174), ('stubborn', 0.17), ('agent', 0.162), ('indecisive', 0.15), ('reachable', 0.142), ('environment', 0.119), ('go', 0.118), ('explorer', 0.106), ('search', 0.087), ('exploration', 0.087), ('sensor', 0.086), ('active', 0.085), ('ok', 0.085), ('occlusion', 0.085), ('kuk', 0.085), ('visual', 0.081), ('objects', 0.075), ('nuisances', 0.075), ('measurement', 0.073), ('ca', 0.07), ('radiance', 0.069), ('occlusions', 0.067), ('lk', 0.061), ('tradeoff', 0.061), ('nt', 0.059), ('photometric', 0.056), ('ck', 0.055), ('path', 0.054), ('risk', 0.052), ('regret', 0.052), ('planned', 0.052), ('density', 0.051), ('residual', 0.051), ('robotics', 0.05), ('segment', 0.05), ('sensing', 0.049), ('snapshots', 0.049), ('recognition', 0.049), ('simplest', 0.047), ('unknown', 0.046), ('planning', 0.045), ('nuisance', 0.044), ('location', 0.044), ('decision', 0.043), ('measurements', 0.043), ('robotic', 0.043), ('pomdp', 0.043), ('atland', 0.042), ('cartoon', 0.042), ('finish', 0.042), ('omnipotent', 0.042), ('unmodeled', 0.042), ('controller', 0.041), ('energy', 0.041), ('ber', 0.039), ('nc', 0.039), ('upper', 0.038), ('passive', 0.038), ('dyt', 0.038), ('mobility', 0.038), ('traveled', 0.038), ('viewing', 0.037), ('conditional', 0.036), ('arg', 0.036), ('phenomenology', 0.035), ('designer', 0.035), ('ol', 0.035), ('discretized', 0.034), ('proxy', 0.034), ('actively', 0.033), ('scenario', 0.033), ('inf', 0.033), ('acquisition', 0.032), ('action', 0.032), ('images', 0.031), ('recognize', 0.031), ('wishes', 0.031), ('exercise', 0.031), ('suite', 0.031), ('proxies', 0.031), ('marginalization', 0.031), ('volume', 0.031), ('scenes', 0.03), ('quantization', 0.03), ('map', 0.03), ('occluded', 0.03), ('mobile', 0.03), ('afforded', 0.03), ('empirically', 0.03), ('wish', 0.03), ('unable', 0.029)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000006 83 nips-2012-Controlled Recognition Bounds for Visual Learning and Exploration
Author: Vasiliy Karasev, Alessandro Chiuso, Stefano Soatto
Abstract: We describe the tradeoff between the performance in a visual recognition problem and the control authority that the agent can exercise on the sensing process. We focus on the problem of “visual search” of an object in an otherwise known and static scene, propose a measure of control authority, and relate it to the expected risk and its proxy (conditional entropy of the posterior density). We show this analytically, as well as empirically by simulation using the simplest known model that captures the phenomenology of image formation, including scaling and occlusions. We show that a “passive” agent given a training set can provide no guarantees on performance beyond what is afforded by the priors, and that an “omnipotent” agent, capable of infinite control authority, can achieve arbitrarily good performance (asymptotically). In between these limiting cases, the tradeoff can be characterized empirically. 1
2 0.22061239 218 nips-2012-Mixing Properties of Conditional Markov Chains with Unbounded Feature Functions
Author: Mathieu Sinn, Bei Chen
Abstract: Conditional Markov Chains (also known as Linear-Chain Conditional Random Fields in the literature) are a versatile class of discriminative models for the distribution of a sequence of hidden states conditional on a sequence of observable variables. Large-sample properties of Conditional Markov Chains have been first studied in [1]. The paper extends this work in two directions: first, mixing properties of models with unbounded feature functions are being established; second, necessary conditions for model identifiability and the uniqueness of maximum likelihood estimates are being given. 1
3 0.21688068 252 nips-2012-On Multilabel Classification and Ranking with Partial Feedback
Author: Claudio Gentile, Francesco Orabona
Abstract: We present a novel multilabel/ranking algorithm working in partial information settings. The algorithm is based on 2nd-order descent methods, and relies on upper-confidence bounds to trade-off exploration and exploitation. We analyze this algorithm in a partial adversarial setting, where covariates can be adversarial, but multilabel probabilities are ruled by (generalized) linear models. We show O(T 1/2 log T ) regret bounds, which improve in several ways on the existing results. We test the effectiveness of our upper-confidence scheme by contrasting against full-information baselines on real-world multilabel datasets, often obtaining comparable performance. 1
4 0.19661753 216 nips-2012-Mirror Descent Meets Fixed Share (and feels no regret)
Author: Nicolò Cesa-bianchi, Pierre Gaillard, Gabor Lugosi, Gilles Stoltz
Abstract: Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension. This is done using either a carefully designed projection or by a weight sharing technique. Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds on a notion of regret generalizing shifting, adaptive, discounted, and other related regrets. Our analysis also captures and extends the generalized weight sharing technique of Bousquet and Warmuth, and can be refined in several ways, including improvements for small losses and adaptive tuning of parameters. 1
5 0.16567409 13 nips-2012-A Nonparametric Conjugate Prior Distribution for the Maximizing Argument of a Noisy Function
Author: Pedro Ortega, Jordi Grau-moya, Tim Genewein, David Balduzzi, Daniel Braun
Abstract: We propose a novel Bayesian approach to solve stochastic optimization problems that involve finding extrema of noisy, nonlinear functions. Previous work has focused on representing possible functions explicitly, which leads to a two-step procedure of first, doing inference over the function space and second, finding the extrema of these functions. Here we skip the representation step and directly model the distribution over extrema. To this end, we devise a non-parametric conjugate prior based on a kernel regressor. The resulting posterior distribution directly captures the uncertainty over the maximum of the unknown function. Given t observations of the function, the posterior can be evaluated efficiently in time O(t2 ) up to a multiplicative constant. Finally, we show how to apply our model to optimize a noisy, non-convex, high-dimensional objective function.
6 0.14601739 303 nips-2012-Searching for objects driven by context
7 0.13449308 314 nips-2012-Slice Normalized Dynamic Markov Logic Networks
8 0.13194093 344 nips-2012-Timely Object Recognition
9 0.11896458 60 nips-2012-Bayesian nonparametric models for ranked data
10 0.11601961 241 nips-2012-No-Regret Algorithms for Unconstrained Online Convex Optimization
11 0.11419262 122 nips-2012-Exploration in Model-based Reinforcement Learning by Empirically Estimating Learning Progress
12 0.10530928 80 nips-2012-Confusion-Based Online Learning and a Passive-Aggressive Scheme
13 0.10326348 138 nips-2012-Fully Bayesian inference for neural models with negative-binomial spiking
14 0.10200167 281 nips-2012-Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders
15 0.093618125 32 nips-2012-Active Comparison of Prediction Models
16 0.092722617 292 nips-2012-Regularized Off-Policy TD-Learning
17 0.08973515 293 nips-2012-Relax and Randomize : From Value to Algorithms
18 0.088215709 56 nips-2012-Bayesian active learning with localized priors for fast receptive field characterization
19 0.085018359 199 nips-2012-Link Prediction in Graphs with Autoregressive Features
20 0.08453095 40 nips-2012-Analyzing 3D Objects in Cluttered Images
topicId topicWeight
[(0, 0.247), (1, -0.103), (2, 0.009), (3, 0.197), (4, 0.123), (5, -0.13), (6, -0.001), (7, -0.03), (8, 0.009), (9, 0.025), (10, -0.015), (11, 0.041), (12, 0.041), (13, -0.148), (14, -0.02), (15, 0.058), (16, 0.055), (17, -0.021), (18, -0.051), (19, -0.069), (20, 0.04), (21, 0.042), (22, 0.024), (23, 0.144), (24, 0.077), (25, 0.023), (26, 0.046), (27, -0.049), (28, 0.09), (29, 0.012), (30, 0.047), (31, 0.094), (32, 0.011), (33, 0.043), (34, 0.009), (35, -0.042), (36, 0.102), (37, 0.059), (38, -0.048), (39, -0.048), (40, 0.031), (41, 0.029), (42, 0.078), (43, 0.038), (44, 0.015), (45, -0.007), (46, 0.142), (47, 0.022), (48, -0.103), (49, 0.005)]
simIndex simValue paperId paperTitle
same-paper 1 0.96185774 83 nips-2012-Controlled Recognition Bounds for Visual Learning and Exploration
Author: Vasiliy Karasev, Alessandro Chiuso, Stefano Soatto
Abstract: We describe the tradeoff between the performance in a visual recognition problem and the control authority that the agent can exercise on the sensing process. We focus on the problem of “visual search” of an object in an otherwise known and static scene, propose a measure of control authority, and relate it to the expected risk and its proxy (conditional entropy of the posterior density). We show this analytically, as well as empirically by simulation using the simplest known model that captures the phenomenology of image formation, including scaling and occlusions. We show that a “passive” agent given a training set can provide no guarantees on performance beyond what is afforded by the priors, and that an “omnipotent” agent, capable of infinite control authority, can achieve arbitrarily good performance (asymptotically). In between these limiting cases, the tradeoff can be characterized empirically. 1
2 0.67660242 283 nips-2012-Putting Bayes to sleep
Author: Dmitry Adamskiy, Manfred K. Warmuth, Wouter M. Koolen
Abstract: We consider sequential prediction algorithms that are given the predictions from a set of models as inputs. If the nature of the data is changing over time in that different models predict well on different segments of the data, then adaptivity is typically achieved by mixing into the weights in each round a bit of the initial prior (kind of like a weak restart). However, what if the favored models in each segment are from a small subset, i.e. the data is likely to be predicted well by models that predicted well before? Curiously, fitting such “sparse composite models” is achieved by mixing in a bit of all the past posteriors. This self-referential updating method is rather peculiar, but it is efficient and gives superior performance on many natural data sets. Also it is important because it introduces a long-term memory: any model that has done well in the past can be recovered quickly. While Bayesian interpretations can be found for mixing in a bit of the initial prior, no Bayesian interpretation is known for mixing in past posteriors. We build atop the “specialist” framework from the online learning literature to give the Mixing Past Posteriors update a proper Bayesian foundation. We apply our method to a well-studied multitask learning problem and obtain a new intriguing efficient update that achieves a significantly better bound. 1
3 0.61140531 303 nips-2012-Searching for objects driven by context
Author: Bogdan Alexe, Nicolas Heess, Yee W. Teh, Vittorio Ferrari
Abstract: The dominant visual search paradigm for object class detection is sliding windows. Although simple and effective, it is also wasteful, unnatural and rigidly hardwired. We propose strategies to search for objects which intelligently explore the space of windows by making sequential observations at locations decided based on previous observations. Our strategies adapt to the class being searched and to the content of a particular test image, exploiting context as the statistical relation between the appearance of a window and its location relative to the object, as observed in the training set. In addition to being more elegant than sliding windows, we demonstrate experimentally on the PASCAL VOC 2010 dataset that our strategies evaluate two orders of magnitude fewer windows while achieving higher object detection performance. 1
4 0.60891336 252 nips-2012-On Multilabel Classification and Ranking with Partial Feedback
Author: Claudio Gentile, Francesco Orabona
Abstract: We present a novel multilabel/ranking algorithm working in partial information settings. The algorithm is based on 2nd-order descent methods, and relies on upper-confidence bounds to trade-off exploration and exploitation. We analyze this algorithm in a partial adversarial setting, where covariates can be adversarial, but multilabel probabilities are ruled by (generalized) linear models. We show O(T 1/2 log T ) regret bounds, which improve in several ways on the existing results. We test the effectiveness of our upper-confidence scheme by contrasting against full-information baselines on real-world multilabel datasets, often obtaining comparable performance. 1
5 0.60032523 314 nips-2012-Slice Normalized Dynamic Markov Logic Networks
Author: Tivadar Papai, Henry Kautz, Daniel Stefankovic
Abstract: Markov logic is a widely used tool in statistical relational learning, which uses a weighted first-order logic knowledge base to specify a Markov random field (MRF) or a conditional random field (CRF). In many applications, a Markov logic network (MLN) is trained in one domain, but used in a different one. This paper focuses on dynamic Markov logic networks, where the size of the discretized time-domain typically varies between training and testing. It has been previously pointed out that the marginal probabilities of truth assignments to ground atoms can change if one extends or reduces the domains of predicates in an MLN. We show that in addition to this problem, the standard way of unrolling a Markov logic theory into a MRF may result in time-inhomogeneity of the underlying Markov chain. Furthermore, even if these representational problems are not significant for a given domain, we show that the more practical problem of generating samples in a sequential conditional random field for the next slice relying on the samples from the previous slice has high computational cost in the general case, due to the need to estimate a normalization factor for each sample. We propose a new discriminative model, slice normalized dynamic Markov logic networks (SN-DMLN), that suffers from none of these issues. It supports efficient online inference, and can directly model influences between variables within a time slice that do not have a causal direction, in contrast with fully directed models (e.g., DBNs). Experimental results show an improvement in accuracy over previous approaches to online inference in dynamic Markov logic networks. 1
6 0.5669412 80 nips-2012-Confusion-Based Online Learning and a Passive-Aggressive Scheme
7 0.53825629 218 nips-2012-Mixing Properties of Conditional Markov Chains with Unbounded Feature Functions
8 0.52662987 13 nips-2012-A Nonparametric Conjugate Prior Distribution for the Maximizing Argument of a Noisy Function
9 0.5152967 222 nips-2012-Multi-Task Averaging
10 0.48625439 209 nips-2012-Max-Margin Structured Output Regression for Spatio-Temporal Action Localization
11 0.48276252 122 nips-2012-Exploration in Model-based Reinforcement Learning by Empirically Estimating Learning Progress
12 0.47447965 344 nips-2012-Timely Object Recognition
13 0.46669337 353 nips-2012-Transferring Expectations in Model-based Reinforcement Learning
14 0.46414319 43 nips-2012-Approximate Message Passing with Consistent Parameter Estimation and Applications to Sparse Learning
15 0.46051326 72 nips-2012-Cocktail Party Processing via Structured Prediction
16 0.45906439 223 nips-2012-Multi-criteria Anomaly Detection using Pareto Depth Analysis
17 0.44336677 216 nips-2012-Mirror Descent Meets Fixed Share (and feels no regret)
18 0.4379375 2 nips-2012-3D Social Saliency from Head-mounted Cameras
19 0.43555143 108 nips-2012-Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search
20 0.43068835 51 nips-2012-Bayesian Hierarchical Reinforcement Learning
topicId topicWeight
[(0, 0.048), (21, 0.053), (38, 0.114), (39, 0.018), (42, 0.026), (54, 0.069), (55, 0.025), (73, 0.109), (74, 0.091), (76, 0.12), (78, 0.039), (80, 0.11), (92, 0.051)]
simIndex simValue paperId paperTitle
same-paper 1 0.89095372 83 nips-2012-Controlled Recognition Bounds for Visual Learning and Exploration
Author: Vasiliy Karasev, Alessandro Chiuso, Stefano Soatto
Abstract: We describe the tradeoff between the performance in a visual recognition problem and the control authority that the agent can exercise on the sensing process. We focus on the problem of “visual search” of an object in an otherwise known and static scene, propose a measure of control authority, and relate it to the expected risk and its proxy (conditional entropy of the posterior density). We show this analytically, as well as empirically by simulation using the simplest known model that captures the phenomenology of image formation, including scaling and occlusions. We show that a “passive” agent given a training set can provide no guarantees on performance beyond what is afforded by the priors, and that an “omnipotent” agent, capable of infinite control authority, can achieve arbitrarily good performance (asymptotically). In between these limiting cases, the tradeoff can be characterized empirically. 1
2 0.87658024 103 nips-2012-Distributed Probabilistic Learning for Camera Networks with Missing Data
Author: Sejong Yoon, Vladimir Pavlovic
Abstract: Probabilistic approaches to computer vision typically assume a centralized setting, with the algorithm granted access to all observed data points. However, many problems in wide-area surveillance can benefit from distributed modeling, either because of physical or computational constraints. Most distributed models to date use algebraic approaches (such as distributed SVD) and as a result cannot explicitly deal with missing data. In this work we present an approach to estimation and learning of generative probabilistic models in a distributed context where certain sensor data can be missing. In particular, we show how traditional centralized models, such as probabilistic PCA and missing-data PPCA, can be learned when the data is distributed across a network of sensors. We demonstrate the utility of this approach on the problem of distributed affine structure from motion. Our experiments suggest that the accuracy of the learned probabilistic structure and motion models rivals that of traditional centralized factorization methods while being able to handle challenging situations such as missing or noisy observations. 1
3 0.87204033 47 nips-2012-Augment-and-Conquer Negative Binomial Processes
Author: Mingyuan Zhou, Lawrence Carin
Abstract: By developing data augmentation methods unique to the negative binomial (NB) distribution, we unite seemingly disjoint count and mixture models under the NB process framework. We develop fundamental properties of the models and derive efficient Gibbs sampling inference. We show that the gamma-NB process can be reduced to the hierarchical Dirichlet process with normalization, highlighting its unique theoretical, structural and computational advantages. A variety of NB processes with distinct sharing mechanisms are constructed and applied to topic modeling, with connections to existing algorithms, showing the importance of inferring both the NB dispersion and probability parameters. 1
4 0.84736151 344 nips-2012-Timely Object Recognition
Author: Sergey Karayev, Tobias Baumgartner, Mario Fritz, Trevor Darrell
Abstract: In a large visual multi-class detection framework, the timeliness of results can be crucial. Our method for timely multi-class detection aims to give the best possible performance at any single point after a start time; it is terminated at a deadline time. Toward this goal, we formulate a dynamic, closed-loop policy that infers the contents of the image in order to decide which detector to deploy next. In contrast to previous work, our method significantly diverges from the predominant greedy strategies, and is able to learn to take actions with deferred values. We evaluate our method with a novel timeliness measure, computed as the area under an Average Precision vs. Time curve. Experiments are conducted on the PASCAL VOC object detection dataset. If execution is stopped when only half the detectors have been run, our method obtains 66% better AP than a random ordering, and 14% better performance than an intelligent baseline. On the timeliness measure, our method obtains at least 11% better performance. Our method is easily extensible, as it treats detectors and classifiers as black boxes and learns from execution traces using reinforcement learning. 1
5 0.8469795 168 nips-2012-Kernel Latent SVM for Visual Recognition
Author: Weilong Yang, Yang Wang, Arash Vahdat, Greg Mori
Abstract: Latent SVMs (LSVMs) are a class of powerful tools that have been successfully applied to many applications in computer vision. However, a limitation of LSVMs is that they rely on linear models. For many computer vision tasks, linear models are suboptimal and nonlinear models learned with kernels typically perform much better. Therefore it is desirable to develop the kernel version of LSVM. In this paper, we propose kernel latent SVM (KLSVM) – a new learning framework that combines latent SVMs and kernel methods. We develop an iterative training algorithm to learn the model parameters. We demonstrate the effectiveness of KLSVM using three different applications in visual recognition. Our KLSVM formulation is very general and can be applied to solve a wide range of applications in computer vision and machine learning. 1
6 0.84524363 274 nips-2012-Priors for Diversity in Generative Latent Variable Models
7 0.84424704 287 nips-2012-Random function priors for exchangeable arrays with applications to graphs and relational data
8 0.84338439 173 nips-2012-Learned Prioritization for Trading Off Accuracy and Speed
9 0.84257799 108 nips-2012-Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search
10 0.83932704 177 nips-2012-Learning Invariant Representations of Molecules for Atomization Energy Prediction
11 0.83910549 38 nips-2012-Algorithms for Learning Markov Field Policies
12 0.83833981 162 nips-2012-Inverse Reinforcement Learning through Structured Classification
13 0.83614618 197 nips-2012-Learning with Recursive Perceptual Representations
14 0.83593047 355 nips-2012-Truncation-free Online Variational Inference for Bayesian Nonparametric Models
15 0.83400202 229 nips-2012-Multimodal Learning with Deep Boltzmann Machines
16 0.8337546 193 nips-2012-Learning to Align from Scratch
17 0.83371544 234 nips-2012-Multiresolution analysis on the symmetric group
18 0.833561 112 nips-2012-Efficient Spike-Coding with Multiplicative Adaptation in a Spike Response Model
19 0.8329547 303 nips-2012-Searching for objects driven by context
20 0.83233911 48 nips-2012-Augmented-SVM: Automatic space partitioning for combining multiple non-linear dynamics