nips nips2001 nips2001-163 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sebastian Thrun, John Langford, Vandi Verma
Abstract: We propose a new particle filter that incorporates a model of costs when generating particles. The approach is motivated by the observation that the costs of accidentally not tracking hypotheses might be significant in some areas of state space, and next to irrelevant in others. By incorporating a cost model into particle filtering, states that are more critical to the system performance are more likely to be tracked. Automatic calculation of the cost model is implemented using an MDP value function calculation that estimates the value of tracking a particular state. Experiments in two mobile robot domains illustrate the appropriateness of the approach.
Reference: text
sentIndex sentText sentNum sentScore
1 edu ¡ Abstract We propose a new particle filter that incorporates a model of costs when generating particles. [sent-3, score-0.733]
2 The approach is motivated by the observation that the costs of accidentally not tracking hypotheses might be significant in some areas of state space, and next to irrelevant in others. [sent-4, score-0.322]
3 By incorporating a cost model into particle filtering, states that are more critical to the system performance are more likely to be tracked. [sent-5, score-0.639]
4 Automatic calculation of the cost model is implemented using an MDP value function calculation that estimates the value of tracking a particular state. [sent-6, score-0.131]
5 Experiments in two mobile robot domains illustrate the appropriateness of the approach. [sent-7, score-0.448]
6 1 Introduction In recent years, particle filters [3, 7, 8] have found widespread application in domains with noisy sensors, such as computer vision and robotics [2, 5]. [sent-8, score-0.65]
7 Particle filters are powerful tools for Bayesian state estimation in non-linear systems. [sent-9, score-0.159]
8 The key idea of particle filters is to approximate a posterior distribution over unknown state variables by a set of particles, drawn from this distribution. [sent-10, score-0.763]
9 This paper addresses a primary deficiency of particle filters: Particle filters are insensitive to costs that might arise from the approximate nature of the particle representation. [sent-11, score-1.285]
10 Their only criterion for generating a particle is the posterior likelihood of a state. [sent-12, score-0.688]
11 If failure to track such lowlikelihood events may incur high costs—such as a mission failure—these variables should be tracked even when their posterior probability is low. [sent-16, score-0.263]
12 This observation suggests that costs should be taken into consideration when generating particles in the filtering process. [sent-17, score-0.4]
13 This paper proposes a particle filter that generates particles according to a distribution that combines the posterior probability with a risk function. [sent-18, score-1.292]
14 The risk function measures the importance of a state location on future cumulative costs. [sent-19, score-0.547]
15 We obtain this risk function via an MDP that calculates the approximate future risk of decisions made in a particular state. [sent-20, score-0.73]
16 Experimental results in two robotic domains illustrate that our approach yields significantly better results than a particle filter insensitive to costs. [sent-21, score-0.725]
17 2 The “Classical” Particle Filter Particle filters are a popular means of estimating the state of partially observable controllable Markov chains [3], sometimes referred to as dynamical systems [1]. [sent-22, score-0.199]
18 To do so, particle filters require two types of information: data, and a probabilistic generative model of the system. [sent-23, score-0.563]
19 The measurement at time will be denoted , and denotes the control asserted in the time interval . [sent-29, score-0.146]
20 ¡ Following common notation in the controls literature, we use the subscript to refer to an event at time and the superscript to denote all events leading up to time . [sent-32, score-0.155]
21 ¢ ¢ Particle filters, like any member of the family of Bayes filters such as Kalman filters and HMMs, estimate the posterior distribution of the state of the dynamical system conditioned on the data, . [sent-33, score-0.258]
22 To calculate this posterior, three probability distributions are required, which together are commonly referred as the probabilistic model of the dynamical system: (1) A measurement model , which describes the probability of measuring when the system is in state . [sent-35, score-0.211]
23 (2) A control model , which characterizes the effect of controls on the system state by specifying the probability that the system is in state after executing control in state . [sent-36, score-0.546]
24 (3) An initial state distri, which specifies the user’s knowledge about the initial system state. [sent-37, score-0.191]
25 Approximations to Bayes filters includes the Kalman filter, the hidden Markov model, binary filters, and of course particle filters. [sent-46, score-0.563]
26 Even in discrete applications, the state space is often too large to compute the entire posterior in reasonable time. [sent-48, score-0.2]
27 ¤ 4 ¡ The particle filter addresses these concerns by approximating the posterior using sets of state samples (particles): (3) qt srsrsrW q x xx ww© u ¡ i pf hgf D4 e¢ ¢ d d The set consists of particles , for some large number (e. [sent-49, score-1.142]
28 Initially, at time , the particles are generated from the initial state distribution . [sent-53, score-0.4]
29 1¤ %B¦92 § 94 g C e¢ ¨8c4 ¦ ¨ © § ¢£ ¡P ¢ d u ¢ hgf 34 e¢ d ¢ hg ef 4 © Lines 2 through 7 generates a new set of particles that incorporates the control . [sent-55, score-0.418]
30 The common aim of this rich body of literature, however, is to generate samples from the posterior . [sent-58, score-0.17]
31 If different controls at different states infer drastically different costs, generating samples according to the posterior runs the risk of not capturing important events that warrant action. [sent-59, score-0.689]
32 7 ¤ 6 ¢ 4¥ 8¢ ) ¢ ¡ %0¦92 3 Risk Sensitive Particle Filters This section describes a modified particle filter that is sensitive to the risk arising from the approximate nature of the particle representation. [sent-61, score-1.577]
33 To arrive at a notion of risk, our approach requires a cost function (4) ¨ ¤ 4 7 5¥ This function assigns real-valued costs to states and control. [sent-62, score-0.155]
34 From a decision theoretic point of view, the goal of risk sensitive sampling is to generate particles that minimize the cumulative increase in cost due to the particle approximation. [sent-63, score-1.362]
35 First, we modify the basic particle filters so that particles are generated in a risk-sensitive way, where the risk is a function of . [sent-65, score-1.162]
36 Second, an appropriate risk function is defined that approximates the cumulative expected costs relative to tracking individual states. [sent-66, score-0.619]
37 1 Risk-Sensitive Sampling 4 7 5¥ Risk-sensitive sampling generates particles factoring in a risk function, . [sent-69, score-0.684]
38 Formally, all we have to ask of a risk function is that it be positive and finite almost everywhere. [sent-70, score-0.365]
39 Not all risk functions will be equally useful, however, so deriving the “right” risk function is important. [sent-71, score-0.73]
40 By considering approximation errors due to monte carlo sampling in decision theory and making a sequence of rough approximations, we can arrive at the , which is discussed further below. [sent-73, score-0.126]
41 For now, let us simply assume are given a suitable risk function. [sent-75, score-0.365]
42 Risk sensitive particle filters generate samples that are distributed according to E7 ¤ 6 4¥ 4 DC B4 )¢ ) ¢ ¡ 3¦92 7 5¥ ! [sent-79, score-0.752]
43 Thus, the probability that a state sample is part of is not only a function of its posterior probability, but also of the risk associated with that sample. [sent-82, score-0.596]
44 d Sampling from (5) is easily achieved by the following two modifications of the basic particle filter algorithm. [sent-84, score-0.563]
45 First, the initial set of particles is generated from the distribution g v ef G 4 G 4¥ G 4 7 1592 7 15¥ ! [sent-85, score-0.291]
46 G (6) Second, Line 5 of the particle filter algorithm is replaced by the following assignment: g ¡¥ 4 g 4 7 8§ e ¢ 64 ¢ ¦32 ¨C 7 D8§Cg e ¢ ¦¥ ! [sent-86, score-0.563]
47 g 8§ e ¢ set (7) We conjecture that this simple modification results in a particle filter with samples dis. [sent-88, score-0.668]
48 Our conjecture is obviously true for the base tributed according to case , since the risk function was explicitly incorporated in the construction of (see eqn. [sent-89, score-0.389]
49 By induction, let us assume that the particles in are distributed according to . [sent-91, score-0.256]
50 Thus, the risk sensitive particle filter successfully generates samples from a distribution that factors in the risk . [sent-108, score-1.501]
51 2 The Risk Function The remaining question is: What is an appropriate risk function ? [sent-111, score-0.365]
52 Our approach rests on the assumption that there are two possible situations, one in which the state is tracked well, and one in which the state is tracked poorly. [sent-113, score-0.338]
53 In the first situation, we assume that any controller will basically chose the right control, whereas in the second situation, it is reasonable to assume that controls are selected anywhere between random and in the worst possible way. [sent-114, score-0.154]
54 To complete this model, we assume that with small probability, the state estimator might move from “well-tracked” to “lost track” and vice versa. [sent-115, score-0.138]
55 The MDP is defined over an augmented state space (see also [10]), where is a binary state variable that models the event that the estimator tracks the state with sufficient ( ) or insufficient ( ) accuracy. [sent-118, score-0.384]
56 The only unspecified terms on the right hand side are the initial tracking probability and the transition probabilities for the state estimator . [sent-120, score-0.268]
57 The former must be set in accordance to the initial knowledge state (e. [sent-121, score-0.137]
58 , 1 if the initial system state is known, 0 if it is unknown). [sent-123, score-0.165]
59 For the latter, we adopt a model where with high likelihood the tracking state is retained ( ) and with low likelihood it changes ( ). [sent-124, score-0.215]
60 , the state is estimated sufficiently accurately, it is assumed that the controller acts by minimizing costs. [sent-129, score-0.162]
61 If , however, the controller adopts a mixture of picking the worst possible control , and a random control. [sent-130, score-0.135]
62 These two options are traded off by the gain factor , which controls the suggests that poor state estimation leads to the worst “pessimism” of the approach. [sent-131, score-0.237]
63 x ¤ ¤ © x ¢ $ Qx Finally, the risk is defined as the difference between the value function that arises from accurate versus inaccurate state estimation: ! [sent-135, score-0.476]
64 4 Experimental Results We have applied our approach to two complimentary real-world robotic domains: robot localization, and mobile robot diagnostics. [sent-139, score-0.66]
65 Both yield superior results using our new risk sensitive approach when compared to the standard particle filter. [sent-140, score-1.039]
66 1 Mobile Robot Localization Our first evaluation domain involves the problem of localizing a mobile robot from sensor data [2]. [sent-142, score-0.42]
67 In our experiments, we focused on the most difficult of all localization problems: (b) (a) B A ¡ ¡ ¢ C Figure 1: (a) Robot Pearl, as it interacts with elderly people at an assisted living facility in Oakmont, PA. [sent-143, score-0.302]
68 Shown here are also three testing locations labeled A, B, and C, and regions of high costs (black contours). [sent-145, score-0.134]
69 This function, which is used in the proposal distribution, is derived from the immediate risk function shown in Figure 1b. [sent-147, score-0.365]
70 (b) Sample of a uniform distribution, taking into consideration the risk function. [sent-148, score-0.388]
71 1 ¤ ¤ ¤ ¤ ¤ steps to re-localize when ported to A steps to re-localize when ported to B steps to re-localize when ported to C number of violations after global kidnapping Table 1: Localization results for the kidnapped robot problem, which emulates a total localization failure. [sent-162, score-0.641]
72 Here a well-localized robot is “tele-ported” to some unknown location and has to recover from this event. [sent-165, score-0.269]
73 This problem plays an important role in evaluating the robustness of a localization algorithm. [sent-166, score-0.132]
74 Figure 1a shows the robot Pearl, which has recently been deployed in an assisted living facility as an assistant to the elderly and cognitively frail. [sent-167, score-0.411]
75 Our study is motivated by the fact that some of the robot’s operational area is a densely cluttered dining room, where the robot is not allowed to cross certain boundaries due to the danger of physically harming people. [sent-168, score-0.269]
76 Figure 2a shows the risk function , projected into 2D. [sent-171, score-0.365]
77 A sample set drawn from this risk function is shown in Figure 2b. [sent-173, score-0.396]
78 Since risk sensitive particle filters incorporate the risk ! [sent-175, score-1.379]
79 (a) v2 (b) α v1 Rover position at time step 1, 10, 22 and 35 (c) 6 W2 Sy 5 Sx 4 W1 3 y −> Ry L Rx v3 2 v4 1 0 W3 W4 −4 B −3 −2 −1 0 x −> 1 2 3 4 Figure 3: (a) The Hyperion rover, a mobile robot being developed at CMU. [sent-176, score-0.423]
80 10,000 samples 100,000 samples 5 5 5 (b) 10 5 Most Likely State 10 0 0 20 40 0 0 20 40 0 0 20 0 40 Sample Variance 8 8 8 6 6 20 40 8 6 0 6 4 4 4 4 2 2 2 2 0 0 0 0 100 samples Most likely state 1000 samples 10 Median error (1−0 loss) Avg. [sent-179, score-0.435]
81 sample variance 100 samples 10 1000 samples 10 40 0 20 40 0 20 40 0 1 1 0. [sent-180, score-0.193]
82 5 0 1 10000 samples 10 1 0 10 20 30 Time step −> 40 −1 0 0 20 Time step −> 40 −1 Figure 4: Tracking curves obtained with (a) plain particle filters, and (b) our new risk sensitive filter. [sent-187, score-1.192]
83 function into the sampling process, however, the density of samples is proportional to the risk function . [sent-189, score-0.49]
84 We ran two types of experiments: First, we kidnapped the robot to any of the locations marked A, B, and C in Figure 1, and measured the number of sensor readings required to recover from this global failure. [sent-192, score-0.389]
85 All three locations are within the high-risk area so the recovery time is significantly shorter than with plain particle filters. [sent-193, score-0.66]
86 Here we find that our approach is almost twice as safe as the conventional particle filter, at virtually the same computational expense. [sent-195, score-0.563]
87 2 Mobile Robot Diagnosis In some domains, particle filters simply cannot be applied in real time because of a large number of high loss and low probability events. [sent-198, score-0.623]
88 Our evaluation involves a data set where a rover is driven with a variety of different control inputs in the normal operation mode. [sent-200, score-0.158]
89 The rover returns to the normal operation mode and continues to operate normally until the gear on wheel #4 breaks at the time step. [sent-203, score-0.199]
90 Notice that both failures lead to very similar sensor measurement, despite the fact that they are caused by quite different events. [sent-205, score-0.132]
91 ¢ £ ¡© ¢ x £¤ (a) Tracking results in Figure 4 show that our approach yields superior results to the standard particle filter. [sent-206, score-0.588]
92 Even though failures are very unlikely, our approach successfully identifies them due to the high risk associated with such a failure while the plain particle filter essentially fails to do so. [sent-207, score-1.085]
93 Vanialle particle filters exhibit non-zero error even with 100,000 samples. [sent-209, score-0.563]
94 5 Discussion We have proposed a particle filter algorithm that considers a cost model when generating samples. [sent-211, score-0.65]
95 The key idea is that particles are generated in proportion to their posterior likelihood and to the risk that arises relative to a control goal. [sent-212, score-0.734]
96 An MDP algorithm was developed that computes the risk function as a differential cumulative cost. [sent-213, score-0.408]
97 Experimental results in two robotic domains show the superior performance of our new approach. [sent-214, score-0.135]
98 Bounds on the performance loss due to the approximate nature of particle filters can be found in [9]. [sent-216, score-0.594]
99 Pursuing the problem of risk-sensitive particle generation within the POMDP framework might be a promising future line of research. [sent-217, score-0.587]
100 Acknowledgment The authors thank Dieter Fox and Wolfram Burgard, who generously provided some the localization software on which this research is built. [sent-218, score-0.132]
wordName wordTfidf (topN-words)
[('particle', 0.563), ('risk', 0.365), ('lters', 0.296), ('robot', 0.241), ('particles', 0.234), ('lter', 0.197), ('localization', 0.132), ('mobile', 0.125), ('rover', 0.112), ('state', 0.111), ('costs', 0.107), ('tracking', 0.104), ('posterior', 0.089), ('sensitive', 0.086), ('samples', 0.081), ('mdp', 0.079), ('failures', 0.078), ('kidnapped', 0.067), ('ported', 0.067), ('qx', 0.066), ('controls', 0.065), ('facility', 0.058), ('wheel', 0.058), ('tracked', 0.058), ('domains', 0.057), ('sensor', 0.054), ('robotic', 0.053), ('controller', 0.051), ('control', 0.046), ('track', 0.046), ('elderly', 0.045), ('endfor', 0.045), ('sampling', 0.044), ('cumulative', 0.043), ('measurement', 0.042), ('cg', 0.041), ('plain', 0.041), ('generates', 0.041), ('carlo', 0.041), ('monte', 0.041), ('dc', 0.04), ('hgf', 0.039), ('burgard', 0.039), ('fault', 0.039), ('failure', 0.038), ('worst', 0.038), ('generating', 0.036), ('assisted', 0.036), ('insuf', 0.036), ('occupancy', 0.036), ('modi', 0.035), ('observable', 0.034), ('vf', 0.033), ('fox', 0.033), ('darker', 0.033), ('events', 0.032), ('sample', 0.031), ('living', 0.031), ('ef', 0.031), ('loss', 0.031), ('dynamical', 0.03), ('unlikely', 0.03), ('kalman', 0.03), ('robotics', 0.03), ('pomdp', 0.03), ('time', 0.029), ('boundaries', 0.028), ('location', 0.028), ('programs', 0.028), ('system', 0.028), ('step', 0.028), ('estimator', 0.027), ('locations', 0.027), ('contours', 0.027), ('incorporates', 0.027), ('insensitive', 0.027), ('cost', 0.027), ('pearl', 0.026), ('initial', 0.026), ('superior', 0.025), ('addresses', 0.025), ('tools', 0.025), ('illustrate', 0.025), ('conjecture', 0.024), ('considers', 0.024), ('ltering', 0.024), ('partially', 0.024), ('line', 0.024), ('normalization', 0.024), ('filters', 0.024), ('augmented', 0.024), ('consideration', 0.023), ('draw', 0.023), ('estimation', 0.023), ('years', 0.022), ('notice', 0.022), ('distributed', 0.022), ('american', 0.022), ('grid', 0.022), ('states', 0.021)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999994 163 nips-2001-Risk Sensitive Particle Filters
Author: Sebastian Thrun, John Langford, Vandi Verma
Abstract: We propose a new particle filter that incorporates a model of costs when generating particles. The approach is motivated by the observation that the costs of accidentally not tracking hypotheses might be significant in some areas of state space, and next to irrelevant in others. By incorporating a cost model into particle filtering, states that are more critical to the system performance are more likely to be tracked. Automatic calculation of the cost model is implemented using an MDP value function calculation that estimates the value of tracking a particular state. Experiments in two mobile robot domains illustrate the appropriateness of the approach.
2 0.65782845 102 nips-2001-KLD-Sampling: Adaptive Particle Filters
Author: Dieter Fox
Abstract: Over the last years, particle filters have been applied with great success to a variety of state estimation problems. We present a statistical approach to increasing the efficiency of particle filters by adapting the size of sample sets on-the-fly. The key idea of the KLD-sampling method is to bound the approximation error introduced by the sample-based representation of the particle filter. The name KLD-sampling is due to the fact that we measure the approximation error by the Kullback-Leibler distance. Our adaptation approach chooses a small number of samples if the density is focused on a small part of the state space, and it chooses a large number of samples if the state uncertainty is high. Both the implementation and computation overhead of this approach are small. Extensive experiments using mobile robot localization as a test application show that our approach yields drastic improvements over particle filters with fixed sample set sizes and over a previously introduced adaptation technique.
3 0.205699 156 nips-2001-Rao-Blackwellised Particle Filtering via Data Augmentation
Author: Christophe Andrieu, Nando D. Freitas, Arnaud Doucet
Abstract: In this paper, we extend the Rao-Blackwellised particle filtering method to more complex hybrid models consisting of Gaussian latent variables and discrete observations. This is accomplished by augmenting the models with artificial variables that enable us to apply Rao-Blackwellisation. Other improvements include the design of an optimal importance proposal distribution and being able to swap the sampling an selection steps to handle outliers. We focus on sequential binary classifiers that consist of linear combinations of basis functions , whose coefficients evolve according to a Gaussian smoothness prior. Our results show significant improvements. 1
4 0.15504558 179 nips-2001-Tempo tracking and rhythm quantization by sequential Monte Carlo
Author: Ali Taylan Cemgil, Bert Kappen
Abstract: We present a probabilistic generative model for timing deviations in expressive music. performance. The structure of the proposed model is equivalent to a switching state space model. We formulate two well known music recognition problems, namely tempo tracking and automatic transcription (rhythm quantization) as filtering and maximum a posteriori (MAP) state estimation tasks. The inferences are carried out using sequential Monte Carlo integration (particle filtering) techniques. For this purpose, we have derived a novel Viterbi algorithm for Rao-Blackwellized particle filters, where a subset of the hidden variables is integrated out. The resulting model is suitable for realtime tempo tracking and transcription and hence useful in a number of music applications such as adaptive automatic accompaniment and score typesetting. 1
5 0.14455266 138 nips-2001-On the Generalization Ability of On-Line Learning Algorithms
Author: Nicolò Cesa-bianchi, Alex Conconi, Claudio Gentile
Abstract: In this paper we show that on-line algorithms for classification and regression can be naturally used to obtain hypotheses with good datadependent tail bounds on their risk. Our results are proven without requiring complicated concentration-of-measure arguments and they hold for arbitrary on-line learning algorithms. Furthermore, when applied to concrete on-line algorithms, our results yield tail bounds that in many cases are comparable or better than the best known bounds.
6 0.14262708 150 nips-2001-Probabilistic Inference of Hand Motion from Neural Activity in Motor Cortex
7 0.11896734 183 nips-2001-The Infinite Hidden Markov Model
8 0.10551663 139 nips-2001-Online Learning with Kernels
9 0.084702298 105 nips-2001-Kernel Machines and Boolean Functions
10 0.076131709 26 nips-2001-Active Portfolio-Management based on Error Correction Neural Networks
11 0.071555302 19 nips-2001-A Rotation and Translation Invariant Discrete Saliency Network
12 0.063785784 108 nips-2001-Learning Body Pose via Specialized Maps
13 0.060768872 43 nips-2001-Bayesian time series classification
14 0.059336375 181 nips-2001-The Emergence of Multiple Movement Units in the Presence of Noise and Feedback Delay
15 0.059310284 115 nips-2001-Linear-time inference in Hierarchical HMMs
16 0.059166618 67 nips-2001-Efficient Resources Allocation for Markov Decision Processes
17 0.058462575 55 nips-2001-Convergence of Optimistic and Incremental Q-Learning
18 0.058333661 59 nips-2001-Direct value-approximation for factored MDPs
19 0.057311505 116 nips-2001-Linking Motor Learning to Function Approximation: Learning in an Unlearnable Force Field
20 0.056301348 7 nips-2001-A Dynamic HMM for On-line Segmentation of Sequential Data
topicId topicWeight
[(0, -0.195), (1, -0.057), (2, 0.086), (3, 0.007), (4, -0.179), (5, -0.166), (6, 0.161), (7, 0.597), (8, 0.137), (9, 0.282), (10, 0.074), (11, -0.15), (12, 0.193), (13, 0.14), (14, 0.083), (15, -0.114), (16, 0.138), (17, -0.11), (18, -0.13), (19, 0.011), (20, -0.032), (21, -0.092), (22, -0.037), (23, 0.021), (24, -0.003), (25, 0.096), (26, -0.037), (27, 0.056), (28, 0.071), (29, 0.014), (30, -0.017), (31, -0.002), (32, 0.012), (33, -0.008), (34, -0.004), (35, -0.048), (36, 0.031), (37, 0.008), (38, -0.056), (39, -0.034), (40, 0.029), (41, 0.036), (42, 0.076), (43, 0.025), (44, -0.018), (45, -0.0), (46, -0.033), (47, 0.029), (48, -0.002), (49, 0.027)]
simIndex simValue paperId paperTitle
same-paper 1 0.96848035 163 nips-2001-Risk Sensitive Particle Filters
Author: Sebastian Thrun, John Langford, Vandi Verma
Abstract: We propose a new particle filter that incorporates a model of costs when generating particles. The approach is motivated by the observation that the costs of accidentally not tracking hypotheses might be significant in some areas of state space, and next to irrelevant in others. By incorporating a cost model into particle filtering, states that are more critical to the system performance are more likely to be tracked. Automatic calculation of the cost model is implemented using an MDP value function calculation that estimates the value of tracking a particular state. Experiments in two mobile robot domains illustrate the appropriateness of the approach.
2 0.94870186 102 nips-2001-KLD-Sampling: Adaptive Particle Filters
Author: Dieter Fox
Abstract: Over the last years, particle filters have been applied with great success to a variety of state estimation problems. We present a statistical approach to increasing the efficiency of particle filters by adapting the size of sample sets on-the-fly. The key idea of the KLD-sampling method is to bound the approximation error introduced by the sample-based representation of the particle filter. The name KLD-sampling is due to the fact that we measure the approximation error by the Kullback-Leibler distance. Our adaptation approach chooses a small number of samples if the density is focused on a small part of the state space, and it chooses a large number of samples if the state uncertainty is high. Both the implementation and computation overhead of this approach are small. Extensive experiments using mobile robot localization as a test application show that our approach yields drastic improvements over particle filters with fixed sample set sizes and over a previously introduced adaptation technique.
3 0.55587816 156 nips-2001-Rao-Blackwellised Particle Filtering via Data Augmentation
Author: Christophe Andrieu, Nando D. Freitas, Arnaud Doucet
Abstract: In this paper, we extend the Rao-Blackwellised particle filtering method to more complex hybrid models consisting of Gaussian latent variables and discrete observations. This is accomplished by augmenting the models with artificial variables that enable us to apply Rao-Blackwellisation. Other improvements include the design of an optimal importance proposal distribution and being able to swap the sampling an selection steps to handle outliers. We focus on sequential binary classifiers that consist of linear combinations of basis functions , whose coefficients evolve according to a Gaussian smoothness prior. Our results show significant improvements. 1
4 0.37301323 179 nips-2001-Tempo tracking and rhythm quantization by sequential Monte Carlo
Author: Ali Taylan Cemgil, Bert Kappen
Abstract: We present a probabilistic generative model for timing deviations in expressive music. performance. The structure of the proposed model is equivalent to a switching state space model. We formulate two well known music recognition problems, namely tempo tracking and automatic transcription (rhythm quantization) as filtering and maximum a posteriori (MAP) state estimation tasks. The inferences are carried out using sequential Monte Carlo integration (particle filtering) techniques. For this purpose, we have derived a novel Viterbi algorithm for Rao-Blackwellized particle filters, where a subset of the hidden variables is integrated out. The resulting model is suitable for realtime tempo tracking and transcription and hence useful in a number of music applications such as adaptive automatic accompaniment and score typesetting. 1
5 0.36833516 26 nips-2001-Active Portfolio-Management based on Error Correction Neural Networks
Author: Hans-Georg Zimmermann, Ralph Neuneier, Ralph Grothmann
Abstract: This paper deals with a neural network architecture which establishes a portfolio management system similar to the Black / Litterman approach. This allocation scheme distributes funds across various securities or financial markets while simultaneously complying with specific allocation constraints which meet the requirements of an investor. The portfolio optimization algorithm is modeled by a feedforward neural network. The underlying expected return forecasts are based on error correction neural networks (ECNN), which utilize the last model error as an auxiliary input to evaluate their own misspecification. The portfolio optimization is implemented such that (i.) the allocations comply with investor’s constraints and that (ii.) the risk of the portfolio can be controlled. We demonstrate the profitability of our approach by constructing internationally diversified portfolios across different financial markets of the G7 contries. It turns out, that our approach is superior to a preset benchmark portfolio. ¢ £¡ 1 Introduction: Portfolio-Management We integrate the portfolio optimization algorithm suggested by Black / Litterman [1] into a neural network architecture. Combining the mean-variance theory [5] with the capital asset pricing model (CAPM) [7], this approach utilizes excess returns of the CAPM equilibrium to define a neutral, well balanced benchmark portfolio. Deviations from the benchmark allocation are only allowed within preset boundaries. Hence, as an advantage, there are no unrealistic solutions (e. g. large short positions, huge portfolio changes). Moreover, there is no need of formulating return expectations for all assets. In contrast to Black / Litterman, excess return forecasts are estimated by time-delay recurrent error correction neural networks [8]. Investment decisions which comply with given allocation constraints are derived from these predictions. The risk exposure of the portfolio is implicitly controlled by a parameter-optimizing task over time (sec. 3 and 5). Our approach consists of the following three steps: (i.) Construction of forecast models on the basis of error correction neural networks (ECNN) for all assets (sec. 2). ¤§© © © § ¥ ¦¨¦¤ To whom correspondence should be addressed: Georg.Zimmermann@mchp.siemens.de. ¤ ¤ (ii.) Computation of excess returns by a higher-level feedforward network (sec. 3 and 4). By this, the profitability of an asset with respect to all others is measured. on the basis of the excess returns. (iii.) Optimization of the investment proportions Allocation constraints ensure, that the investment proportions may deviate from a given benchmark only within predefined intervals (sec. 3 and 4). £ § ¨¡ ¥ £¡ ¦¤¢ ¡ © ¡ © Finally, we apply our neural network based portfolio management system to an asset allocation problem concerning the G7 countries (sec. 6). 2 Forecasting by Error Correction Neural Networks Most dynamical systems are driven by a superposition of autonomous development and external influences [8]. For discrete time grids, such a dynamics can be described by a recurrent state transition and an output equation (Eq. 1). ¥ § § state transition eq. output eq. (1) $
6 0.29804128 150 nips-2001-Probabilistic Inference of Hand Motion from Neural Activity in Motor Cortex
7 0.26823121 138 nips-2001-On the Generalization Ability of On-Line Learning Algorithms
8 0.26367575 183 nips-2001-The Infinite Hidden Markov Model
9 0.21829541 108 nips-2001-Learning Body Pose via Specialized Maps
10 0.21078761 168 nips-2001-Sequential Noise Compensation by Sequential Monte Carlo Method
11 0.20463026 121 nips-2001-Model-Free Least-Squares Policy Iteration
12 0.20392878 115 nips-2001-Linear-time inference in Hierarchical HMMs
13 0.19518252 139 nips-2001-Online Learning with Kernels
14 0.19277924 3 nips-2001-ACh, Uncertainty, and Cortical Inference
15 0.19160397 55 nips-2001-Convergence of Optimistic and Incremental Q-Learning
16 0.18931155 7 nips-2001-A Dynamic HMM for On-line Segmentation of Sequential Data
17 0.18842107 67 nips-2001-Efficient Resources Allocation for Markov Decision Processes
18 0.18766674 148 nips-2001-Predictive Representations of State
19 0.18609744 140 nips-2001-Optimising Synchronisation Times for Mobile Devices
20 0.18373112 177 nips-2001-Switch Packet Arbitration via Queue-Learning
topicId topicWeight
[(14, 0.031), (17, 0.026), (19, 0.022), (27, 0.078), (30, 0.478), (38, 0.019), (49, 0.017), (59, 0.05), (72, 0.055), (79, 0.029), (83, 0.02), (91, 0.094)]
simIndex simValue paperId paperTitle
Author: Takashi Morie, Tomohiro Matsuura, Makoto Nagata, Atsushi Iwata
Abstract: This paper describes a clustering algorithm for vector quantizers using a “stochastic association model”. It offers a new simple and powerful softmax adaptation rule. The adaptation process is the same as the on-line K-means clustering method except for adding random fluctuation in the distortion error evaluation process. Simulation results demonstrate that the new algorithm can achieve efficient adaptation as high as the “neural gas” algorithm, which is reported as one of the most efficient clustering methods. It is a key to add uncorrelated random fluctuation in the similarity evaluation process for each reference vector. For hardware implementation of this process, we propose a nanostructure, whose operation is described by a single-electron circuit. It positively uses fluctuation in quantum mechanical tunneling processes.
2 0.98080301 173 nips-2001-Speech Recognition with Missing Data using Recurrent Neural Nets
Author: S. Parveen, P. Green
Abstract: In the ‘missing data’ approach to improving the robustness of automatic speech recognition to added noise, an initial process identifies spectraltemporal regions which are dominated by the speech source. The remaining regions are considered to be ‘missing’. In this paper we develop a connectionist approach to the problem of adapting speech recognition to the missing data case, using Recurrent Neural Networks. In contrast to methods based on Hidden Markov Models, RNNs allow us to make use of long-term time constraints and to make the problems of classification with incomplete data and imputing missing values interact. We report encouraging results on an isolated digit recognition task.
3 0.96477801 82 nips-2001-Generating velocity tuning by asymmetric recurrent connections
Author: Xiaohui Xie, Martin A. Giese
Abstract: Asymmetric lateral connections are one possible mechanism that can account for the direction selectivity of cortical neurons. We present a mathematical analysis for a class of these models. Contrasting with earlier theoretical work that has relied on methods from linear systems theory, we study the network’s nonlinear dynamic properties that arise when the threshold nonlinearity of the neurons is taken into account. We show that such networks have stimulus-locked traveling pulse solutions that are appropriate for modeling the responses of direction selective cortical neurons. In addition, our analysis shows that outside a certain regime of stimulus speeds the stability of this solutions breaks down giving rise to another class of solutions that are characterized by specific spatiotemporal periodicity. This predicts that if direction selectivity in the cortex is mainly achieved by asymmetric lateral connections lurching activity waves might be observable in ensembles of direction selective cortical neurons within appropriate regimes of the stimulus speed.
4 0.95314968 159 nips-2001-Reducing multiclass to binary by coupling probability estimates
Author: B. Zadrozny
Abstract: This paper presents a method for obtaining class membership probability estimates for multiclass classification problems by coupling the probability estimates produced by binary classifiers. This is an extension for arbitrary code matrices of a method due to Hastie and Tibshirani for pairwise coupling of probability estimates. Experimental results with Boosted Naive Bayes show that our method produces calibrated class membership probability estimates, while having similar classification accuracy as loss-based decoding, a method for obtaining the most likely class that does not generate probability estimates.
same-paper 5 0.94519651 163 nips-2001-Risk Sensitive Particle Filters
Author: Sebastian Thrun, John Langford, Vandi Verma
Abstract: We propose a new particle filter that incorporates a model of costs when generating particles. The approach is motivated by the observation that the costs of accidentally not tracking hypotheses might be significant in some areas of state space, and next to irrelevant in others. By incorporating a cost model into particle filtering, states that are more critical to the system performance are more likely to be tracked. Automatic calculation of the cost model is implemented using an MDP value function calculation that estimates the value of tracking a particular state. Experiments in two mobile robot domains illustrate the appropriateness of the approach.
6 0.92381459 151 nips-2001-Probabilistic principles in unsupervised learning of visual structure: human data and a model
7 0.81330436 149 nips-2001-Probabilistic Abstraction Hierarchies
8 0.80844259 65 nips-2001-Effective Size of Receptive Fields of Inferior Temporal Visual Cortex Neurons in Natural Scenes
9 0.78576267 73 nips-2001-Eye movements and the maturation of cortical orientation selectivity
10 0.77807087 102 nips-2001-KLD-Sampling: Adaptive Particle Filters
11 0.72813535 63 nips-2001-Dynamic Time-Alignment Kernel in Support Vector Machine
12 0.69256198 46 nips-2001-Categorization by Learning and Combining Object Parts
13 0.67912465 20 nips-2001-A Sequence Kernel and its Application to Speaker Recognition
14 0.67661619 77 nips-2001-Fast and Robust Classification using Asymmetric AdaBoost and a Detector Cascade
15 0.67307234 60 nips-2001-Discriminative Direction for Kernel Classifiers
16 0.67280465 52 nips-2001-Computing Time Lower Bounds for Recurrent Sigmoidal Neural Networks
17 0.66580421 176 nips-2001-Stochastic Mixed-Signal VLSI Architecture for High-Dimensional Kernel Machines
18 0.66096544 4 nips-2001-ALGONQUIN - Learning Dynamic Noise Models From Noisy Speech for Robust Speech Recognition
19 0.65694797 34 nips-2001-Analog Soft-Pattern-Matching Classifier using Floating-Gate MOS Technology
20 0.65143538 116 nips-2001-Linking Motor Learning to Function Approximation: Learning in an Unlearnable Force Field