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

120 nips-2005-Learning vehicular dynamics, with application to modeling helicopters

Source: pdf

Author: Pieter Abbeel, Varun Ganapathi, Andrew Y. Ng

Abstract: We consider the problem of modeling a helicopter’s dynamics based on state-action trajectories collected from it. The contribution of this paper is two-fold. First, we consider the linear models such as learned by CIFER (the industry standard in helicopter identiﬁcation), and show that the linear parameterization makes certain properties of dynamical systems, such as inertia, fundamentally difﬁcult to capture. We propose an alternative, acceleration based, parameterization that does not suffer from this deﬁciency, and that can be learned as efﬁciently from data. Second, a Markov decision process model of a helicopter’s dynamics would explicitly model only the one-step transitions, but we are often interested in a model’s predictive performance over longer timescales. In this paper, we present an efﬁcient algorithm for (approximately) minimizing the prediction error over long time scales. We present empirical results on two different helicopters. Although this work was motivated by the problem of modeling helicopters, the ideas presented here are general, and can be applied to modeling large classes of vehicular dynamics. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 First, we consider the linear models such as learned by CIFER (the industry standard in helicopter identiﬁcation), and show that the linear parameterization makes certain properties of dynamical systems, such as inertia, fundamentally difﬁcult to capture. [sent-7, score-0.85]

2 We propose an alternative, acceleration based, parameterization that does not suffer from this deﬁciency, and that can be learned as efﬁciently from data. [sent-8, score-0.397]

3 [7, 9, 2, 4, 3, 8] In designing helicopter controllers, one typically begins by constructing a model for the helicopter’s dynamics, and then uses that model to design a controller. [sent-14, score-0.618]

4 These differences between simulation and real-life performance can therefore be directly attributed to errors in the simulator (model) of the helicopter, and building accurate helicopter models remains a key technical challenge in autonomous ﬂight. [sent-16, score-0.745]

5 With an emphasis on helicopter aerodynamics, in this paper we consider the problem of learning good dynamical models of vehicles. [sent-18, score-0.681]

6 Helicopter aerodynamics are, to date, somewhat poorly understood, and (unlike most ﬁxedwing aircraft) no textbook models will accurately predict the dynamics of a helicopter from only its dimensions and speciﬁcations. [sent-19, score-0.704]

7 CIFER R (Comprehensive Identiﬁcation from Frequency Responses) is the industry standard for learning helicopter (and other rotorcraft) models from data. [sent-21, score-0.618]

8 The models obtained from CIFER fail to capture some important aspects of the helicopter dynamics, such as the effects of inertia. [sent-23, score-0.649]

9 Consider a setting in which the helicopter is ﬂying forward, and suddenly turns sideways. [sent-24, score-0.618]

10 Due to inertia, the helicopter will continue to travel in the same direction as before, so that it has “sideslip,” meaning that its orientation is not aligned with its direction of motion. [sent-25, score-0.685]

11 This is a non-linear effect that depends both on velocity and angular rates. [sent-26, score-0.317]

12 The core of the problem is that the naive body-coordinate representation used in all these settings makes it fundamentally difﬁcult for the learning algorithm to capture certain properties of dynamical systems such as inertia and gravity. [sent-29, score-0.194]

13 In Section 4, we propose an alternative parameterization for modeling dynamical systems that does not suffer from this deﬁciency. [sent-31, score-0.16]

14 It is not immediately obvious how such prior knowledge can be encoded into a complex learning algorithm, but we will describe an acceleration based parameterization in which this can be done. [sent-35, score-0.317]

15 Alternatively, we can minimize the squared one-step prediction error in the time domain. [sent-38, score-0.161]

16 Forward simulation on a held-out test set is a standard way to assess model quality, and we use it to compare the linear models learned using CIFER to the same linear models learned by optimizing the one-step prediction error. [sent-39, score-0.299]

17 In this paper, we present an efﬁcient algorithm that approximately optimizes the lagged criterion. [sent-44, score-0.237]

18 Combining this with the acceleration based parameterization results in our best helicopter model. [sent-46, score-0.935]

19 2 Helicopter state, input and dynamics The helicopter state s comprises its position (x, y, z), orientation (roll φ, pitch θ, yaw ˙ ˙ ˙ ω), velocity (x, y, z) and angular velocity (φ, θ, ω). [sent-47, score-1.404]

20 The helicopter is controlled via a 4˙ ˙ ˙ dimensional action space: 1. [sent-48, score-0.618]

21 u1 and u2 : The longitudinal (front-back) and latitudinal (left-right) cyclic pitch controls cause the helicopter to pitch forward/backward or sideways, and can thereby also affect acceleration in the longitudinal and latitudinal directions. [sent-49, score-1.145]

22 u3 : The tail rotor collective pitch control affects tail rotor thrust, and can be used to yaw (turn) the helicopter. [sent-51, score-0.4]

23 u4 : The main rotor collective pitch control affects the pitch angle of the main rotor’s blades, by rotating the blades around an axis that runs along the length of the blade. [sent-53, score-0.382]

24 As the main rotor blades sweep through the air, the resulting amount of upward thrust (generally) increases with this pitch angle; thus this control affects the main rotor’s thrust. [sent-54, score-0.304]

25 Following standard practice in system identiﬁcation ([8, 6]), the original 12-dimensional helicopter state is reduced to an 8-dimensional state represented in body (or robot-centric) coordinates sb = (φ, θ, x, y, z, φ, θ, ω). [sent-55, score-0.766]

26 The body coordinate representation speciﬁes the helicopter state using a coordinate frame in which the x, y, and z axes are forwards, sideways, and down relative to the current orientation of the helicopter, instead of north, east and down. [sent-57, score-1.107]

27 Thus, xb is the forward velocity, ˙ whereas xs is the velocity in the northern direction. [sent-58, score-0.337]

28 (φ and θ are always expressed in world ˙ coordinates, because roll and pitch relative to the body coordinate frame is always zero. [sent-59, score-0.38]

29 ) By using a body coordinate representation, we encode into our model certain “symmetries” of helicopter ﬂight, such as that the helicopter’s dynamics are the same regardless of its absolute position (x, y, z) and heading ω (assuming the absence of obstacles). [sent-60, score-0.94]

30 Even in the reduced coordinate representation, only a subset of the state variables needs to be modeled ˙ ˙ ˙ explicitly using learning. [sent-61, score-0.18]

31 Given a model that predicts only the angular velocities (φ, θ, ω), we can numerically integrate to obtain the orientation (φ, θ, ω). [sent-62, score-0.259]

32 We can integrate the reduced body coordinate states to obtain the complete world coordinate states. [sent-63, score-0.336]

33 Integrating body-coordinate angular velocities to obtain world-coordinate angles is nonlinear, thus the model resulting from this process is necessarily nonlinear. [sent-64, score-0.192]

34 81m/s is the acceleration due to gravity and ∆t is the time discretization, which is 0. [sent-67, score-0.303]

35 Instead, we can minimize the average squared prediction error of next state given current state and action. [sent-74, score-0.247]

36 In our experiments (see Section 6) we compare the simulation accuracy over several time-steps of the differently learned linear models. [sent-76, score-0.157]

37 4 Acceleration prediction model Due to inertia, if a forward-ﬂying helicopter turns, it will have sideslip (i. [sent-79, score-0.747]

38 , the helicopter will not be aligned with its direction of motion). [sent-81, score-0.618]

39 The linear model is unable to capture the sideslip effect, since this effect depends non-linearly on velocity and angular rates. [sent-82, score-0.44]

40 1 D0 captures the sideways acceleration caused by the tail rotor’s thrust. [sent-88, score-0.337]

41 From physics, we have the following update equation for velocity in body-coordinates: ˙ ˙ ˙ (x, y, z)b = R (φ, θ, ω)b ∗ (x, y, z)b + (¨, y , z )b ∆t . [sent-89, score-0.163]

42 (1) to obtain velocity over time, may perform well. [sent-93, score-0.163]

43 Such a model would naturally capture inertia, by using the velocity update of Eqn. [sent-94, score-0.194]

44 But the change in bodycoordinate velocity does not correspond directly to physical accelerations, because the body-coordinate velocity at times t and t + 1 are expressed in different coordinate frames. [sent-97, score-0.463]

45 Thus, xb − xb is not the forward acceleration—because xb and xb are expressed in dif˙ t+1 ˙ t ˙ t+1 ˙t ferent coordinate frames. [sent-98, score-0.833]

46 To capture inertia, these models therefore need to predict not only the physical accelerations, but also the non-linear inﬂuence of the angular rates through the rotation matrix. [sent-99, score-0.23]

47 Our discussion above has focused on linear velocity, but a similar argument also holds for angular velocity. [sent-101, score-0.183]

48 The previous discussion suggests that we learn to predict physical accelerations and then integrate the accelerations to obtain the state trajectories. [sent-102, score-0.359]

49 To do this, we propose: ˙ ¨ φb = Cφ φt + C1 (u1 )t + D1 , xb = Cx xb + (gx )b , ¨t ˙t t t b b ¨ ˙ θ = Cθ θt + C2 (u2 )t + D2 , y = Cy y b + (gy )b + D0 , ¨ ˙ t t t t ωt = Cω ωt + C3 (u3 )t + D3 , zt = Cz zt + (gz )b + C4 (u4 )t + D4 . [sent-103, score-0.46]

50 ¨b ˙ ¨b ˙b t Here (gx )b , (gy )b , (gz )b are the components of the gravity acceleration vector in each of the t t t body-coordinate axes at time t; and C· , D· are the free parameters to be learned from data. [sent-104, score-0.35]

51 The model predicts accelerations in the body-coordinate frame, and is therefore able to take advantage of the same invariants as discussed earlier, such as invariance of the dynamics to the helicopter’s (x, y, z) position and heading (ω). [sent-105, score-0.281]

52 Further, it additionally captures the fact that the dynamics are invariant to roll (φ) and pitch (θ) once the (known) effects of gravity are subtracted out. [sent-106, score-0.242]

53 Frequency domain techniques cannot be used to learn the acceleration model above, because it is non-linear. [sent-107, score-0.253]

54 Nevertheless, the parameters can be learned as easily as for the linear model in the time domain: Linear regression can be used to ﬁnd the parameters that minimize the squared error of the one-step prediction in acceleration. [sent-108, score-0.237]

55 2 5 The lagged error criterion To evaluate the performance of a dynamical model, it is standard practice to run a simulation using the model for a certain duration, and then compare the simulated trajectory with the real state trajectory. [sent-109, score-0.475]

56 2 Note that, as discussed previously, the one-step difference of body coordinate velocities is not the acceleration. [sent-113, score-0.237]

57 To obtain actual accelerations, the velocity at time t + 1 must be rotated into the body-frame at t before taking the difference. [sent-114, score-0.163]

58 We therefore present a simple and fast algorithm for (approximately) minimizing the lagged criterion. [sent-116, score-0.268]

59 Minimizing the one-step prediction error would correspond to ﬁnding the parameters that minimize the expected squared difference between the left and right sides of Eqn. [sent-118, score-0.161]

60 By summing the update equations for two consecutive time steps, we get that, for simulation to be exact over two time steps, the following needs to hold: st+2 − st = Ast + But + Aˆt+1|t + But+1 . [sent-120, score-0.206]

61 More generally, by summing up the update equations for h consecutive timesteps and then minimizing the left and right sides’ expected squared difference, we can minimize the h-step prediction error. [sent-123, score-0.22]

62 Thus, it may seem that we can directly solve for the parameters that minimize the lagged criterion of Eqn. [sent-124, score-0.324]

63 This ˆ is because st+1|t represents the result of a one-step simulation from st using our model. [sent-128, score-0.178]

64 Use least squares to minimize the one-step squared prediction error criterion to obtain an initial model A(0) , B (0) . [sent-135, score-0.247]

65 Our helicopter acceleration prediction model is not of the simple form st+1 − st = Ast + But described above. [sent-152, score-1.034]

66 However, a similar derivation still applies: The change in velocity over several time-steps corresponds to the sum of changes in velocity over several single time-steps. [sent-153, score-0.326]

67 Thus by adding the one-step acceleration prediction equations as given in Section 4, we might expect to obtain equations corresponding to the acceleration over several time-steps. [sent-154, score-0.628]

68 However, the acceleration equations at different time-steps are in different coordinate frames. [sent-155, score-0.418]

69 In the algorithm described below, we rotate all accelerations into the world coordinate frame. [sent-157, score-0.295]

70 The acceleration equations from Section 4 give us (¨, y , z )b = Apos st + Bpos ut , and x ¨ ¨t 3 This step of the algorithm uses a simple line search to choose the stepsize α. [sent-158, score-0.378]

71 ) The XCell Tempest is a competition-class aerobatic helicopter (length 54”, height 19”), is powered by a 0. [sent-164, score-0.681]

72 The larger Bergen Industrial Twin helicopter is powered by a twin cylinder 46cc, two-stroke engine, and has an unloaded weight of 18 lbs. [sent-168, score-0.792]

73 Linear-One-Step: The linear model from Section 3 trained using linear regression to minimize the one-step prediction error. [sent-175, score-0.16]

74 Linear-Lagged: The linear model from Section 3 trained minimizing the lagged criterion. [sent-179, score-0.297]

75 Acceleration-One-Step: The acceleration prediction model from Section 4 trained using linear regression to minimize the one step prediction error. [sent-181, score-0.45]

76 Acceleration-Lagged: The acceleration prediction model from Section 4 trained minimizing the lagged criterion. [sent-183, score-0.587]

77 Our algorithm optimizing the lagged criterion appears to converge after at most 30 iterations. [sent-189, score-0.288]

78 Since this algorithm is only approximate, we can then use coordinate descent search to further improve the lagged criterion. [sent-190, score-0.421]

79 5 This coordinate descent search took an additional four hours for the XCell Tempest data and an additional 30 minutes for the Bergen Industrial Twin data. [sent-191, score-0.212]

80 We report results both with and without this coordinate descent search. [sent-192, score-0.184]

81 Our results show that the algorithm presented in Section 5 works well for fast approximate optimization of the lagged criterion, but that locally greedy search (coordinate descent) may then improve it yet further. [sent-193, score-0.237]

82 The orientation error is measured by the squared magnitude of the minimal rotation needed to align the simulated orientation with the true orientation. [sent-204, score-0.238]

83 Velocity, position, angular rate and orientation errors are measured in m/s, m, rad/s and rad (squared) respectively. [sent-205, score-0.221]

84 Similarly, for the acceleration prediction models, we have that AccelerationLagged consistently outperforms Acceleration-One-Step. [sent-208, score-0.319]

85 These experiments support the case for training with the lagged criterion. [sent-209, score-0.237]

86 The best acceleration prediction model, Acceleration-Lagged, is signiﬁcantly more accurate than any of the linear models presented in Section 3. [sent-210, score-0.348]

87 7 Summary We presented an acceleration based parameterization for learning vehicular dynamics. [sent-214, score-0.364]

88 We also described an efﬁcient algorithm for approximately minimizing the lagged criterion, which measures the predictive accuracy of the algorithm over both short and long time-scales. [sent-216, score-0.268]

89 In our experiments, learning with the acceleration parameterization and using the lagged criterion gave signiﬁcantly more accurate models than previous approaches. [sent-217, score-0.605]

90 We give warm thanks to Adam Coates and to helicopter pilot Ben Tse for their help on this work. [sent-221, score-0.618]

91 5 We used coordinate descent on the criterion of Eqn. [sent-222, score-0.235]

92 (2), but reweighted the errors on velocity, angular velocity, position and orientation to scale them to roughly the same order of magnitude. [sent-223, score-0.258]

93 4 40 20 150 100 50 orientation 60 angular rate position velocity 1. [sent-226, score-0.421]

94 5 2 t (s) Bergen Industrial Twin position velocity 1. [sent-243, score-0.2]

95 Red, dashed: LinearLagged learned with fast, approximate algorithm from Section 5 followed by greedy coordinate descent search. [sent-270, score-0.231]

96 Black,*: Acceleration-Lagged learned with fast, approximate algorithm from Section 5 followed by greedy coordinate descent search. [sent-273, score-0.231]

97 The blue, yellow, magenta and cyan lines (visually) coincide in the Bergen angular rate and orientation plots. [sent-275, score-0.322]

98 The red and black lines (visually) coincide in the Bergen angular rate plot. [sent-276, score-0.187]

99 Autonomous helicopter control using reinforcement learning policy search methods. [sent-287, score-0.618]

100 Flight test and simulation results for an autonomous aerobatic helicopter. [sent-302, score-0.19]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('helicopter', 0.618), ('acceleration', 0.253), ('lagged', 0.237), ('cifer', 0.174), ('xb', 0.174), ('velocity', 0.163), ('accelerations', 0.158), ('bergen', 0.158), ('angular', 0.154), ('twin', 0.142), ('xcell', 0.142), ('coordinate', 0.137), ('tempest', 0.126), ('pitch', 0.105), ('inertia', 0.1), ('st', 0.097), ('rotor', 0.096), ('industrial', 0.093), ('simulation', 0.081), ('helicopters', 0.079), ('orientation', 0.067), ('prediction', 0.066), ('parameterization', 0.064), ('dynamical', 0.063), ('aerobatic', 0.063), ('sideslip', 0.063), ('ight', 0.063), ('body', 0.062), ('squared', 0.059), ('zt', 0.056), ('dynamics', 0.054), ('criterion', 0.051), ('ying', 0.05), ('gravity', 0.05), ('agged', 0.047), ('apos', 0.047), ('arot', 0.047), ('blades', 0.047), ('bpos', 0.047), ('brot', 0.047), ('cy', 0.047), ('mettler', 0.047), ('microstrain', 0.047), ('rbt', 0.047), ('sideways', 0.047), ('vehicular', 0.047), ('descent', 0.047), ('learned', 0.047), ('autonomous', 0.046), ('rotation', 0.045), ('state', 0.043), ('frame', 0.043), ('stanford', 0.041), ('cz', 0.038), ('velocities', 0.038), ('earn', 0.038), ('ast', 0.038), ('tail', 0.037), ('position', 0.037), ('minimize', 0.036), ('squares', 0.035), ('cyan', 0.035), ('magenta', 0.033), ('coincide', 0.033), ('roll', 0.033), ('suffer', 0.033), ('aerodynamics', 0.032), ('aiaa', 0.032), ('funnel', 0.032), ('gavrilets', 0.032), ('gx', 0.032), ('gyros', 0.032), ('heading', 0.032), ('ights', 0.032), ('inear', 0.032), ('inertial', 0.032), ('latitudinal', 0.032), ('magnetometers', 0.032), ('martinos', 0.032), ('novatel', 0.032), ('rotorcraft', 0.032), ('tischler', 0.032), ('triaxial', 0.032), ('unloaded', 0.032), ('minimizing', 0.031), ('capture', 0.031), ('cx', 0.03), ('frequency', 0.029), ('affects', 0.029), ('linear', 0.029), ('minutes', 0.028), ('identi', 0.028), ('equations', 0.028), ('gz', 0.027), ('flight', 0.027), ('thrust', 0.027), ('coates', 0.027), ('ganapathi', 0.027), ('tse', 0.027), ('varun', 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999946 120 nips-2005-Learning vehicular dynamics, with application to modeling helicopters

Author: Pieter Abbeel, Varun Ganapathi, Andrew Y. Ng

2 0.21849461 69 nips-2005-Fast Gaussian Process Regression using KD-Trees

Author: Yirong Shen, Matthias Seeger, Andrew Y. Ng

Abstract: The computation required for Gaussian process regression with n training examples is about O(n3 ) during training and O(n) for each prediction. This makes Gaussian process regression too slow for large datasets. In this paper, we present a fast approximation method, based on kd-trees, that signiﬁcantly reduces both the prediction and the training times of Gaussian process regression.

3 0.063548416 45 nips-2005-Conditional Visual Tracking in Kernel Space

Author: Cristian Sminchisescu, Atul Kanujia, Zhiguo Li, Dimitris Metaxas

Abstract: We present a conditional temporal probabilistic framework for reconstructing 3D human motion in monocular video based on descriptors encoding image silhouette observations. For computational efÄ?Ĺš ciency we restrict visual inference to low-dimensional kernel induced non-linear state spaces. Our methodology (kBME) combines kernel PCA-based non-linear dimensionality reduction (kPCA) and Conditional Bayesian Mixture of Experts (BME) in order to learn complex multivalued predictors between observations and model hidden states. This is necessary for accurate, inverse, visual perception inferences, where several probable, distant 3D solutions exist due to noise or the uncertainty of monocular perspective projection. Low-dimensional models are appropriate because many visual processes exhibit strong non-linear correlations in both the image observations and the target, hidden state variables. The learned predictors are temporally combined within a conditional graphical model in order to allow a principled propagation of uncertainty. We study several predictors and empirically show that the proposed algorithm positively compares with techniques based on regression, Kernel Dependency Estimation (KDE) or PCA alone, and gives results competitive to those of high-dimensional mixture predictors at a fraction of their computational cost. We show that the method successfully reconstructs the complex 3D motion of humans in real monocular video sequences. 1 Introduction and Related Work We consider the problem of inferring 3D articulated human motion from monocular video. This research topic has applications for scene understanding including human-computer interfaces, markerless human motion capture, entertainment and surveillance. A monocular approach is relevant because in real-world settings the human body parts are rarely completely observed even when using multiple cameras. This is due to occlusions form other people or objects in the scene. A robust system has to necessarily deal with incomplete, ambiguous and uncertain measurements. Methods for 3D human motion reconstruction can be classiÄ?Ĺš ed as generative and discriminative. They both require a state representation, namely a 3D human model with kinematics (joint angles) or shape (surfaces or joint positions) and they both use a set of image features as observations for state inference. The computational goal in both cases is the conditional distribution for the model state given image observations. Generative model-based approaches [6, 16, 14, 13] have been demonstrated to Ä?Ĺš‚exibly reconstruct complex unknown human motions and to naturally handle problem constraints. However it is difÄ?Ĺš cult to construct reliable observation likelihoods due to the complexity of modeling human appearance. This varies widely due to different clothing and deformation, body proportions or lighting conditions. Besides being somewhat indirect, the generative approach further imposes strict conditional independence assumptions on the temporal observations given the states in order to ensure computational tractability. Due to these factors inference is expensive and produces highly multimodal state distributions [6, 16, 13]. Generative inference algorithms require complex annealing schedules [6, 13] or systematic non-linear search for local optima [16] in order to ensure continuing tracking. These difÄ?Ĺš culties motivate the advent of a complementary class of discriminative algorithms [10, 12, 18, 2], that approximate the state conditional directly, in order to simplify inference. However, inverse, observation-to-state multivalued mappings are difÄ?Ĺš cult to learn (see e.g. Ä?Ĺš g. 1a) and a probabilistic temporal setting is necessary. In an earlier paper [15] we introduced a probabilistic discriminative framework for human motion reconstruction. Because the method operates in the originally selected state and observation spaces that can be task generic, therefore redundant and often high-dimensional, inference is more expensive and can be less robust. To summarize, reconstructing 3D human motion in a Figure 1: (a, Left) Example of 180o ambiguity in predicting 3D human poses from silhouette image features (center). It is essential that multiple plausible solutions (e.g. F 1 and F2 ) are correctly represented and tracked over time. A single state predictor will either average the distant solutions or zig-zag between them, see also tables 1 and 2. (b, Right) A conditional chain model. The local distributions p(yt |ytĂ˘ˆ’1 , zt ) or p(yt |zt ) are learned as in Ä?Ĺš g. 2. For inference, the predicted local state conditional is recursively combined with the Ä?Ĺš ltered prior c.f . (1). conditional temporal framework poses the following difÄ?Ĺš culties: (i) The mapping between temporal observations and states is multivalued (i.e. the local conditional distributions to be learned are multimodal), therefore it cannot be accurately represented using global function approximations. (ii) Human models have multivariate, high-dimensional continuous states of 50 or more human joint angles. The temporal state conditionals are multimodal which makes efÄ?Ĺš cient Kalman Ä?Ĺš ltering algorithms inapplicable. General inference methods (particle Ä?Ĺš lters, mixtures) have to be used instead, but these are expensive for high-dimensional models (e.g. when reconstructing the motion of several people that operate in a joint state space). (iii) The components of the human state and of the silhouette observation vector exhibit strong correlations, because many repetitive human activities like walking or running have low intrinsic dimensionality. It appears wasteful to work with high-dimensional states of 50+ joint angles. Even if the space were truly high-dimensional, predicting correlated state dimensions independently may still be suboptimal. In this paper we present a conditional temporal estimation algorithm that restricts visual inference to low-dimensional, kernel induced state spaces. To exploit correlations among observations and among state variables, we model the local, temporal conditional distributions using ideas from Kernel PCA [11, 19] and conditional mixture modeling [7, 5], here adapted to produce multiple probabilistic predictions. The corresponding predictor is referred to as a Conditional Bayesian Mixture of Low-dimensional Kernel-Induced Experts (kBME). By integrating it within a conditional graphical model framework (Ä?Ĺš g. 1b), we can exploit temporal constraints probabilistically. We demonstrate that this methodology is effective for reconstructing the 3D motion of multiple people in monocular video. Our contribution w.r.t. [15] is a probabilistic conditional inference framework that operates over a non-linear, kernel-induced low-dimensional state spaces, and a set of experiments (on both real and artiÄ?Ĺš cial image sequences) that show how the proposed framework positively compares with powerful predictors based on KDE, PCA, or with the high-dimensional models of [15] at a fraction of their cost. 2 Probabilistic Inference in a Kernel Induced State Space We work with conditional graphical models with a chain structure [9], as shown in Ä?Ĺš g. 1b, These have continuous temporal states yt , t = 1 . . . T , observations zt . For compactness, we denote joint states Yt = (y1 , y2 , . . . , yt ) or joint observations Zt = (z1 , . . . , zt ). Learning and inference are based on local conditionals: p(yt |zt ) and p(yt |ytĂ˘ˆ’1 , zt ), with yt and zt being low-dimensional, kernel induced representations of some initial model having state xt and observation rt . We obtain zt , yt from rt , xt using kernel PCA [11, 19]. Inference is performed in a low-dimensional, non-linear, kernel induced latent state space (see Ä?Ĺš g. 1b and Ä?Ĺš g. 2 and (1)). For display or error reporting, we compute the original conditional p(x|r), or a temporally Ä?Ĺš ltered version p(xt |Rt ), Rt = (r1 , r2 , . . . , rt ), using a learned pre-image state map [3]. 2.1 Density Propagation for Continuous Conditional Chains For online Ä?Ĺš ltering, we compute the optimal distribution p(yt |Zt ) for the state yt , conditioned by observations Zt up to time t. The Ä?Ĺš ltered density can be recursively derived as: p(yt |Zt ) = p(yt |ytĂ˘ˆ’1 , zt )p(ytĂ˘ˆ’1 |ZtĂ˘ˆ’1 ) (1) ytĂ˘ˆ’1 We compute using a conditional mixture for p(yt |ytĂ˘ˆ’1 , zt ) (a Bayesian mixture of experts c.f . Ă‚Â§2.2) and the prior p(ytĂ˘ˆ’1 |ZtĂ˘ˆ’1 ), each having, say M components. We integrate M 2 pairwise products of Gaussians analytically. The means of the expanded posterior are clustered and the centers are used to initialize a reduced M -component Kullback-Leibler approximation that is reÄ?Ĺš ned using gradient descent [15]. The propagation rule (1) is similar to the one used for discrete state labels [9], but here we work with multivariate continuous state spaces and represent the local multimodal state conditionals using kBME (Ä?Ĺš g. 2), and not log-linear models [9] (these would require intractable normalization). This complex continuous model rules out inference based on Kalman Ä?Ĺš ltering or dynamic programming [9]. 2.2 Learning Bayesian Mixtures over Kernel Induced State Spaces (kBME) In order to model conditional mappings between low-dimensional non-linear spaces we rely on kernel dimensionality reduction and conditional mixture predictors. The authors of KDE [19] propose a powerful structured unimodal predictor. This works by decorrelating the output using kernel PCA and learning a ridge regressor between the input and each decorrelated output dimension. Our procedure is also based on kernel PCA but takes into account the structure of the studied visual problem where both inputs and outputs are likely to be low-dimensional and the mapping between them multivalued. The output variables xi are projected onto the column vectors of the principal space in order to obtain their principal coordinates y i . A z Ă˘ˆˆ P(Fr ) O p(y|z) kP CA ĂŽĹšr (r) Ă˘Š‚ Fr O / y Ă˘ˆˆ P(Fx ) O QQQ QQQ QQQ kP CA QQQ Q( ĂŽĹšx (x) Ă˘Š‚ Fx x Ă˘‰ˆ PreImage(y) O ĂŽĹšr ĂŽĹšx r Ă˘ˆˆ R Ă˘Š‚ Rr x Ă˘ˆˆ X Ă˘Š‚ Rx p(x|r) Ă˘‰ˆ p(x|y) Figure 2: The learned low-dimensional predictor, kBME, for computing p(x|r) Ă˘‰Ä„ p(xt |rt ), Ă˘ˆ€t. (We similarly learn p(xt |xtĂ˘ˆ’1 , rt ), with input (x, r) instead of r Ă˘€“ here we illustrate only p(x|r) for clarity.) The input r and the output x are decorrelated using Kernel PCA to obtain z and y respectively. The kernels used for the input and output are ĂŽĹš r and ĂŽĹšx , with induced feature spaces Fr and Fx , respectively. Their principal subspaces obtained by kernel PCA are denoted by P(Fr ) and P(Fx ), respectively. A conditional Bayesian mixture of experts p(y|z) is learned using the low-dimensional representation (z, y). Using learned local conditionals of the form p(yt |zt ) or p(yt |ytĂ˘ˆ’1 , zt ), temporal inference can be efÄ?Ĺš ciently performed in a low-dimensional kernel induced state space (see e.g. (1) and Ä?Ĺš g. 1b). For visualization and error measurement, the Ä?Ĺš ltered density, e.g. p(yt |Zt ), can be mapped back to p(xt |Rt ) using the pre-image c.f . (3). similar procedure is performed on the inputs ri to obtain zi . In order to relate the reduced feature spaces of z and y (P(Fr ) and P(Fx )), we estimate a probability distribution over mappings from training pairs (zi , yi ). We use a conditional Bayesian mixture of experts (BME) [7, 5] in order to account for ambiguity when mapping similar, possibly identical reduced feature inputs to very different feature outputs, as common in our problem (Ä?Ĺš g. 1a). This gives a model that is a conditional mixture of low-dimensional kernel-induced experts (kBME): M g(z|ĂŽÂ´ j )N (y|Wj z, ĂŽĹ j ) p(y|z) = (2) j=1 where g(z|ĂŽÂ´ j ) is a softmax function parameterized by ĂŽÂ´ j and (Wj , ĂŽĹ j ) are the parameters and the output covariance of expert j, here a linear regressor. As in many Bayesian settings [17, 5], the weights of the experts and of the gates, Wj and ĂŽÂ´ j , are controlled by hierarchical priors, typically Gaussians with 0 mean, and having inverse variance hyperparameters controlled by a second level of Gamma distributions. We learn this model using a double-loop EM and employ ML-II type approximations [8, 17] with greedy (weight) subset selection [17, 15]. Finally, the kBME algorithm requires the computation of pre-images in order to recover the state distribution x from itĂ˘€™s image y Ă˘ˆˆ P(Fx ). This is a closed form computation for polynomial kernels of odd degree. For more general kernels optimization or learning (regression based) methods are necessary [3]. Following [3, 19], we use a sparse Bayesian kernel regressor to learn the pre-image. This is based on training data (xi , yi ): p(x|y) = N (x|AĂŽĹšy (y), Ă˘„Ĺš) (3) with parameters and covariances (A, Ă˘„Ĺš). Since temporal inference is performed in the low-dimensional kernel induced state space, the pre-image function needs to be calculated only for visualizing results or for the purpose of error reporting. Propagating the result from the reduced feature space P(Fx ) to the output space X pro- duces a Gaussian mixture with M elements, having coefÄ?Ĺš cients g(z|ĂŽÂ´ j ) and components N (x|AĂŽĹšy (Wj z), AJĂŽĹšy ĂŽĹ j JĂŽĹšy A + Ă˘„Ĺš), where JĂŽĹšy is the Jacobian of the mapping ĂŽĹšy . 3 Experiments We run experiments on both real image sequences (Ä?Ĺš g. 5 and Ä?Ĺš g. 6) and on sequences where silhouettes were artiÄ?Ĺš cially rendered. The prediction error is reported in degrees (for mixture of experts, this is w.r.t. the most probable one, but see also Ä?Ĺš g. 4a), and normalized per joint angle, per frame. The models are learned using standard cross-validation. Pre-images are learned using kernel regressors and have average error 1.7o . Training Set and Model State Representation: For training we gather pairs of 3D human poses together with their image projections, here silhouettes, using the graphics package Maya. We use realistically rendered computer graphics human surface models which we animate using human motion capture [1]. Our original human representation (x) is based on articulated skeletons with spherical joints and has 56 skeletal d.o.f. including global translation. The database consists of 8000 samples of human activities including walking, running, turns, jumps, gestures in conversations, quarreling and pantomime. Image Descriptors: We work with image silhouettes obtained using statistical background subtraction (with foreground and background models). Silhouettes are informative for pose estimation although prone to ambiguities (e.g. the left / right limb assignment in side views) or occasional lack of observability of some of the d.o.f. (e.g. 180o ambiguities in the global azimuthal orientation for frontal views, e.g. Ä?Ĺš g. 1a). These are multiplied by intrinsic forward / backward monocular ambiguities [16]. As observations r, we use shape contexts extracted on the silhouette [4] (5 radial, 12 angular bins, size range 1/8 to 3 on log scale). The features are computed at different scales and sizes for points sampled on the silhouette. To work in a common coordinate system, we cluster all features in the training set into K = 50 clusters. To compute the representation of a new shape feature (a point on the silhouette), we Ă˘€˜projectĂ˘€™ onto the common basis by (inverse distance) weighted voting into the cluster centers. To obtain the representation (r) for a new silhouette we regularly sample 200 points on it and add all their feature vectors into a feature histogram. Because the representation uses overlapping features of the observation the elements of the descriptor are not independent. However, a conditional temporal framework (Ä?Ĺš g. 1b) Ä?Ĺš‚exibly accommodates this. For experiments, we use Gaussian kernels for the joint angle feature space and dot product kernels for the observation feature space. We learn state conditionals for p(yt |zt ) and p(yt |ytĂ˘ˆ’1 , zt ) using 6 dimensions for the joint angle kernel induced state space and 25 dimensions for the observation induced feature space, respectively. In Ä?Ĺš g. 3b) we show an evaluation of the efÄ?Ĺš cacy of our kBME predictor for different dimensions in the joint angle kernel induced state space (the observation feature space dimension is here 50). On the analyzed dancing sequence, that involves complex motions of the arms and the legs, the non-linear model signiÄ?Ĺš cantly outperforms alternative PCA methods and gives good predictions for compact, low-dimensional models.1 In tables 1 and 2, as well as Ä?Ĺš g. 4, we perform quantitative experiments on artiÄ?Ĺš cially rendered silhouettes. 3D ground truth joint angles are available and this allows a more 1 Running times: On a Pentium 4 PC (3 GHz, 2 GB RAM), a full dimensional BME model with 5 experts takes 802s to train p(xt |xtĂ˘ˆ’1 , rt ), whereas a kBME (including the pre-image) takes 95s to train p(yt |ytĂ˘ˆ’1 , zt ). The prediction time is 13.7s for BME and 8.7s (including the pre-image cost 1.04s) for kBME. The integration in (1) takes 2.67s for BME and 0.31s for kBME. The speed-up for kBME is signiÄ?Ĺš cant and likely to increase with original models having higher dimensionality. Prediction Error Number of Clusters 100 1000 100 10 1 1 2 3 4 5 6 7 8 Degree of Multimodality kBME KDE_RVM PCA_BME PCA_RVM 10 1 0 20 40 Number of Dimensions 60 Figure 3: (a, Left) Analysis of Ă˘€˜multimodalityĂ˘€™ for a training set. The input zt dimension is 25, the output yt dimension is 6, both reduced using kPCA. We cluster independently in (ytĂ˘ˆ’1 , zt ) and yt using many clusters (2100) to simulate small input perturbations and we histogram the yt clusters falling within each cluster in (ytĂ˘ˆ’1 , zt ). This gives intuition on the degree of ambiguity in modeling p(yt |ytĂ˘ˆ’1 , zt ), for small perturbations in the input. (b, Right) Evaluation of dimensionality reduction methods for an artiÄ?Ĺš cial dancing sequence (models trained on 300 samples). The kBME is our model Ă‚Â§2.2, whereas the KDE-RVM is a KDE model learned with a Relevance Vector Machine (RVM) [17] feature space map. PCA-BME and PCA-RVM are models where the mappings between feature spaces (obtained using PCA) is learned using a BME and a RVM. The non-linearity is signiÄ?Ĺš cant. Kernel-based methods outperform PCA and give low prediction error for 5-6d models. systematic evaluation. Notice that the kernelized low-dimensional models generally outperform the PCA ones. At the same time, they give results competitive to the ones of high-dimensional BME predictors, while being lower-dimensional and therefore signiÄ?Ĺš cantly less expensive for inference, e.g. the integral in (1). In Ä?Ĺš g. 5 and Ä?Ĺš g. 6 we show human motion reconstruction results for two real image sequences. Fig. 5 shows the good quality reconstruction of a person performing an agile jump. (Given the missing observations in a side view, 3D inference for the occluded body parts would not be possible without using prior knowledge!) For this sequence we do inference using conditionals having 5 modes and reduced 6d states. We initialize tracking using p(yt |zt ), whereas for inference we use p(yt |ytĂ˘ˆ’1 , zt ) within (1). In the second sequence in Ä?Ĺš g. 6, we simultaneously reconstruct the motion of two people mimicking domestic activities, namely washing a window and picking an object. Here we do inference over a product, 12-dimensional state space consisting of the joint 6d state of each person. We obtain good 3D reconstruction results, using only 5 hypotheses. Notice however, that the results are not perfect, there are small errors in the elbow and the bending of the knee for the subject at the l.h.s., and in the different wrist orientations for the subject at the r.h.s. This reÄ?Ĺš‚ects the bias of our training set. Walk and turn Conversation Run and turn left KDE-RR 10.46 7.95 5.22 RVM 4.95 4.96 5.02 KDE-RVM 7.57 6.31 6.25 BME 4.27 4.15 5.01 kBME 4.69 4.79 4.92 Table 1: Comparison of average joint angle prediction error for different models. All kPCA-based models use 6 output dimensions. Testing is done on 100 video frames for each sequence, the inputs are artiÄ?Ĺš cially generated silhouettes, not in the training set. 3D joint angle ground truth is used for evaluation. KDE-RR is a KDE model with ridge regression (RR) for the feature space mapping, KDE-RVM uses an RVM. BME uses a Bayesian mixture of experts with no dimensionality reduction. kBME is our proposed model. kPCAbased methods use kernel regressors to compute pre-images. Expert Prediction Frequency Ă˘ˆ’ Closest to Ground truth Frequency Ă˘ˆ’ Close to ground truth 30 25 20 15 10 5 0 1 2 3 4 Expert Number 14 10 8 6 4 2 0 5 1st Probable Prev Output 2nd Probable Prev Output 3rd Probable Prev Output 4th Probable Prev Output 5th Probable Prev Output 12 1 2 3 4 Current Expert 5 Figure 4: (a, Left) Histogram showing the accuracy of various expert predictors: how many times the expert ranked as the k-th most probable by the model (horizontal axis) is closest to the ground truth. The model is consistent (the most probable expert indeed is the most accurate most frequently), but occasionally less probable experts are better. (b, Right) Histograms show the dynamics of p(yt |ytĂ˘ˆ’1 , zt ), i.e. how the probability mass is redistributed among experts between two successive time steps, in a conversation sequence. Walk and turn back Run and turn KDE-RR 7.59 17.7 RVM 6.9 16.8 KDE-RVM 7.15 16.08 BME 3.6 8.2 kBME 3.72 8.01 Table 2: Joint angle prediction error computed for two complex sequences with walks, runs and turns, thus more ambiguity (100 frames). Models have 6 state dimensions. Unimodal predictors average competing solutions. kBME has signiÄ?Ĺš cantly lower error. Figure 5: Reconstruction of a jump (selected frames). Top: original image sequence. Middle: extracted silhouettes. Bottom: 3D reconstruction seen from a synthetic viewpoint. 4 Conclusion We have presented a probabilistic framework for conditional inference in latent kernelinduced low-dimensional state spaces. Our approach has the following properties: (a) Figure 6: Reconstructing the activities of 2 people operating in an 12-d state space (each person has its own 6d state). Top: original image sequence. Bottom: 3D reconstruction seen from a synthetic viewpoint. Accounts for non-linear correlations among input or output variables, by using kernel nonlinear dimensionality reduction (kPCA); (b) Learns probability distributions over mappings between low-dimensional state spaces using conditional Bayesian mixture of experts, as required for accurate prediction. In the resulting low-dimensional kBME predictor ambiguities and multiple solutions common in visual, inverse perception problems are accurately represented. (c) Works in a continuous, conditional temporal probabilistic setting and offers a formal management of uncertainty. We show comparisons that demonstrate how the proposed approach outperforms regression, PCA or KDE alone for reconstructing the 3D human motion in monocular video. Future work we will investigate scaling aspects for large training sets and alternative structured prediction methods. References [1] CMU Human Motion DataBase. Online at http://mocap.cs.cmu.edu/search.html, 2003. [2] A. Agarwal and B. Triggs. 3d human pose from silhouettes by Relevance Vector Regression. In CVPR, 2004. [3] G. Bakir, J. Weston, and B. Scholkopf. Learning to Ä?Ĺš nd pre-images. In NIPS, 2004. [4] S. Belongie, J. Malik, and J. Puzicha. Shape matching and object recognition using shape contexts. PAMI, 24, 2002. [5] C. Bishop and M. Svensen. Bayesian mixtures of experts. In UAI, 2003. [6] J. Deutscher, A. Blake, and I. Reid. Articulated Body Motion Capture by Annealed Particle Filtering. In CVPR, 2000. [7] M. Jordan and R. Jacobs. Hierarchical mixtures of experts and the EM algorithm. Neural Computation, (6):181Ă˘€“214, 1994. [8] D. Mackay. Bayesian interpolation. Neural Computation, 4(5):720Ă˘€“736, 1992. [9] A. McCallum, D. Freitag, and F. Pereira. Maximum entropy Markov models for information extraction and segmentation. In ICML, 2000. [10] R. Rosales and S. Sclaroff. Learning Body Pose Via Specialized Maps. In NIPS, 2002. [11] B. SchĂ‚Â¨ lkopf, A. Smola, and K. MĂ‚Â¨ ller. Nonlinear component analysis as a kernel eigenvalue o u problem. Neural Computation, 10:1299Ă˘€“1319, 1998. [12] G. Shakhnarovich, P. Viola, and T. Darrell. Fast Pose Estimation with Parameter Sensitive Hashing. In ICCV, 2003. [13] L. Sigal, S. Bhatia, S. Roth, M. Black, and M. Isard. Tracking Loose-limbed People. In CVPR, 2004. [14] C. Sminchisescu and A. Jepson. Generative Modeling for Continuous Non-Linearly Embedded Visual Inference. In ICML, pages 759Ă˘€“766, Banff, 2004. [15] C. Sminchisescu, A. Kanaujia, Z. Li, and D. Metaxas. Discriminative Density Propagation for 3D Human Motion Estimation. In CVPR, 2005. [16] C. Sminchisescu and B. Triggs. Kinematic Jump Processes for Monocular 3D Human Tracking. In CVPR, volume 1, pages 69Ă˘€“76, Madison, 2003. [17] M. Tipping. Sparse Bayesian learning and the Relevance Vector Machine. JMLR, 2001. [18] C. Tomasi, S. Petrov, and A. Sastry. 3d tracking = classiÄ?Ĺš cation + interpolation. In ICCV, 2003. [19] J. Weston, O. Chapelle, A. Elisseeff, B. Scholkopf, and V. Vapnik. Kernel dependency estimation. In NIPS, 2002.

4 0.060144775 80 nips-2005-Gaussian Process Dynamical Models

Author: Jack Wang, Aaron Hertzmann, David M. Blei

Abstract: This paper introduces Gaussian Process Dynamical Models (GPDM) for nonlinear time series analysis. A GPDM comprises a low-dimensional latent space with associated dynamics, and a map from the latent space to an observation space. We marginalize out the model parameters in closed-form, using Gaussian Process (GP) priors for both the dynamics and the observation mappings. This results in a nonparametric model for dynamical systems that accounts for uncertainty in the model. We demonstrate the approach on human motion capture data in which each pose is 62-dimensional. Despite the use of small data sets, the GPDM learns an effective representation of the nonlinear dynamics in these spaces. Webpage: http://www.dgp.toronto.edu/∼ jmwang/gpdm/ 1

5 0.051332783 111 nips-2005-Learning Influence among Interacting Markov Chains

Author: Dong Zhang, Daniel Gatica-perez, Samy Bengio, Deb Roy

Abstract: We present a model that learns the inﬂuence of interacting Markov chains within a team. The proposed model is a dynamic Bayesian network (DBN) with a two-level structure: individual-level and group-level. Individual level models actions of each player, and the group-level models actions of the team as a whole. Experiments on synthetic multi-player games and a multi-party meeting corpus show the effectiveness of the proposed model. 1

6 0.046239581 67 nips-2005-Extracting Dynamical Structure Embedded in Neural Activity

7 0.043521378 82 nips-2005-Generalization Error Bounds for Aggregation by Mirror Descent with Averaging

8 0.041781027 78 nips-2005-From Weighted Classification to Policy Search

9 0.040971193 136 nips-2005-Noise and the two-thirds power Law

10 0.040884238 65 nips-2005-Estimating the wrong Markov random field: Benefits in the computation-limited setting

11 0.040572714 87 nips-2005-Goal-Based Imitation as Probabilistic Inference over Graphical Models

12 0.04005548 145 nips-2005-On Local Rewards and Scaling Distributed Reinforcement Learning

13 0.038618539 8 nips-2005-A Criterion for the Convergence of Learning with Spike Timing Dependent Plasticity

14 0.036973216 187 nips-2005-Temporal Abstraction in Temporal-difference Networks

15 0.036693141 124 nips-2005-Measuring Shared Information and Coordinated Activity in Neuronal Networks

16 0.034609754 142 nips-2005-Oblivious Equilibrium: A Mean Field Approximation for Large-Scale Dynamic Games

17 0.034498282 72 nips-2005-Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation

18 0.033091255 129 nips-2005-Modeling Neural Population Spiking Activity with Gibbs Distributions

19 0.031488325 148 nips-2005-Online Discovery and Learning of Predictive State Representations

20 0.031377457 119 nips-2005-Learning to Control an Octopus Arm with Gaussian Process Temporal Difference Methods

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.121), (1, -0.02), (2, 0.071), (3, 0.008), (4, 0.025), (5, -0.035), (6, 0.022), (7, -0.018), (8, 0.058), (9, 0.105), (10, -0.015), (11, 0.03), (12, -0.029), (13, 0.031), (14, 0.055), (15, 0.042), (16, -0.007), (17, 0.006), (18, -0.116), (19, -0.025), (20, 0.008), (21, -0.086), (22, 0.002), (23, -0.096), (24, -0.104), (25, -0.041), (26, -0.102), (27, 0.069), (28, -0.014), (29, 0.02), (30, -0.07), (31, -0.105), (32, 0.112), (33, 0.081), (34, 0.122), (35, 0.117), (36, 0.048), (37, -0.207), (38, 0.032), (39, -0.209), (40, -0.152), (41, 0.041), (42, 0.094), (43, -0.106), (44, -0.303), (45, -0.007), (46, 0.059), (47, 0.126), (48, -0.139), (49, -0.04)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.93291777 120 nips-2005-Learning vehicular dynamics, with application to modeling helicopters

Author: Pieter Abbeel, Varun Ganapathi, Andrew Y. Ng

2 0.69328421 69 nips-2005-Fast Gaussian Process Regression using KD-Trees

Author: Yirong Shen, Matthias Seeger, Andrew Y. Ng

3 0.47548664 71 nips-2005-Fast Krylov Methods for N-Body Learning

Author: Nando D. Freitas, Yang Wang, Maryam Mahdaviani, Dustin Lang

Abstract: This paper addresses the issue of numerical computation in machine learning domains based on similarity metrics, such as kernel methods, spectral techniques and Gaussian processes. It presents a general solution strategy based on Krylov subspace iteration and fast N-body learning methods. The experiments show signiﬁcant gains in computation and storage on datasets arising in image segmentation, object detection and dimensionality reduction. The paper also presents theoretical bounds on the stability of these methods.

4 0.36751705 68 nips-2005-Factorial Switching Kalman Filters for Condition Monitoring in Neonatal Intensive Care

Author: Christopher Williams, John Quinn, Neil Mcintosh

Abstract: The observed physiological dynamics of an infant receiving intensive care are affected by many possible factors, including interventions to the baby, the operation of the monitoring equipment and the state of health. The Factorial Switching Kalman Filter can be used to infer the presence of such factors from a sequence of observations, and to estimate the true values where these observations have been corrupted. We apply this model to clinical time series data and show it to be effective in identifying a number of artifactual and physiological patterns. 1

5 0.35982105 59 nips-2005-Dual-Tree Fast Gauss Transforms

Author: Dongryeol Lee, Andrew W. Moore, Alexander G. Gray

Abstract: In previous work we presented an efﬁcient approach to computing kernel summations which arise in many machine learning methods such as kernel density estimation. This approach, dual-tree recursion with ﬁnitedifference approximation, generalized existing methods for similar problems arising in computational physics in two ways appropriate for statistical problems: toward distribution sensitivity and general dimension, partly by avoiding series expansions. While this proved to be the fastest practical method for multivariate kernel density estimation at the optimal bandwidth, it is much less efﬁcient at larger-than-optimal bandwidths. In this work, we explore the extent to which the dual-tree approach can be integrated with multipole-like Hermite expansions in order to achieve reasonable efﬁciency across all bandwidth scales, though only for low dimensionalities. In the process, we derive and demonstrate the ﬁrst truly hierarchical fast Gauss transforms, effectively combining the best tools from discrete algorithms and continuous approximation theory. 1 Fast Gaussian Summation Kernel summations are fundamental in both statistics/learning and computational physics. NR e This paper will focus on the common form G(xq ) = −||xq −xr ||2 2h2 i.e. where the ker- r=1 nel is the Gaussian kernel with scaling parameter, or bandwidth h, there are NR reference points xr , and we desire the sum for NQ different query points xq . Such kernel summations appear in a wide array of statistical/learning methods [5], perhaps most obviously in kernel density estimation [11], the most widely used distribution-free method for the fundamental task of density estimation, which will be our main example. Understanding kernel summation algorithms from a recently developed uniﬁed perspective [5] begins with the picture of Figure 1, then separately considers the discrete and continuous aspects. Discrete/geometric aspect. In terms of discrete algorithmic structure, the dual-tree framework of [5], in the context of kernel summation, generalizes all of the well-known algorithms. 1 It was applied to the problem of kernel density estimation in [7] using a simple 1 These include the Barnes-Hut algorithm [2], the Fast Multipole Method [8], Appel’s algorithm [1], and the WSPD [4]: the dual-tree method is a node-node algorithm (considers query regions rather than points), is fully recursive, can use distribution-sensitive data structures such as kd-trees, and is bichromatic (can specialize for differing query and reference sets). Figure 1: The basic idea is to approximate the kernel sum contribution of some subset of the reference points XR , lying in some compact region of space R with centroid xR , to a query point. In more efﬁcient schemes a query region is considered, i.e. the approximate contribution is made to an entire subset of the query points XQ lying in some region of space Q, with centroid xQ . ﬁnite-difference approximation, which is tantamount to a centroid approximation. Partially by avoiding series expansions, which depend explicitly on the dimension, the result was the fastest such algorithm for general dimension, when operating at the optimal bandwidth. Unfortunately, when performing cross-validation to determine the (initially unknown) optimal bandwidth, both suboptimally small and large bandwidths must be evaluated. The ﬁnite-difference-based dual-tree method tends to be efﬁcient at or below the optimal bandwidth, and at very large bandwidths, but for intermediately-large bandwidths it suffers. Continuous/approximation aspect. This motivates investigating a multipole-like series approximation which is appropriate for the Gaussian kernel, as introduced by [9], which can be shown the generalize the centroid approximation. We deﬁne the Hermite functions 2 hn (t) by hn (t) = e−t Hn (t), where the Hermite polynomials Hn (t) are deﬁned by the 2 2 Rodrigues formula: Hn (t) = (−1)n et Dn e−t , t ∈ R1 . After scaling and shifting the argument t appropriately, then taking the product of univariate functions for each dimension, we obtain the multivariate Hermite expansion NR G(xq ) = e −||xq −xr ||2 2h2 NR = r=1 r=1 α≥0 1 α! xr − xR √ 2h2 α hα xq − xR √ 2h2 (1) where we’ve adopted the usual multi-index notation as in [9]. This can be re-written as NR G(xq ) = e r=1 −||xq −xr ||2 2h2 NR = r=1 α≥0 1 hα α! xr − xQ √ 2h2 xq − xQ √ 2h2 α (2) to express the sum as a Taylor (local) expansion about a nearby representative centroid xQ in the query region. We will be using both types of expansions simultaneously. Since series approximations only hold locally, Greengard and Rokhlin [8] showed that it is useful to think in terms of a set of three ‘translation operators’ for converting between expansions centered at different points, in order to create their celebrated hierarchical algorithm. This was done in the context of the Coulombic kernel, but the Gaussian kernel has importantly different mathematical properties. The original Fast Gauss Transform (FGT) [9] was based on a ﬂat grid, and thus provided only one operator (“H2L” of the next section), with an associated error bound (which was unfortunately incorrect). The Improved Fast Gauss Transform (IFGT) [14] was based on a ﬂat set of clusters and provided no operators with a rearranged series approximation, which intended to be more favorable in higher dimensions but had an incorrect error bound. We will show the derivations of all the translation operators and associated error bounds needed to obtain, for the ﬁrst time, a hierarchical algorithm for the Gaussian kernel. 2 Translation Operators and Error Bounds The ﬁrst operator converts a multipole expansion of a reference node to form a local expansion centered at the centroid of the query node, and is our main approximation workhorse. Lemma 2.1. Hermite-to-local (H2L) translation operator for Gaussian kernel (as presented in Lemma 2.2 in [9, 10]): Given a reference node XR , a query node XQ , and the Hermite expansion centered at a centroid xR of XR : G(xq ) = Aα hα α≥0 xq −xR √ 2h2 , the Taylor expansion of the Hermite expansion at the centroid xQ of the query node XQ is given by G(xq ) = Bβ β≥0 xq −xQ √ 2h2 β where Bβ = (−1)|β| β! Aα hα+β α≥0 xQ −xR √ 2h2 . Proof. (sketch) The proof consists of replacing the Hermite function portion of the expansion with its Taylor series. NR Note that we can rewrite G(xq ) = α≥0 r=1 1 α! xr −xR √ 2h2 α hα xq −xR √ 2h2 by interchanging the summation order, such that the term in the brackets depends only on the reference points, and can thus be computed indepedent of any query location – we will call such terms Hermite moments. The next operator allows the efﬁcient pre-computation of the Hermite moments in the reference tree in a bottom-up fashion from its children. Lemma 2.2. Hermite-to-Hermite (H2H) translation operator for Gaussian kernel: Given the Hermite expansion centered at a centroid xR′ in a reference node XR′ : xq −x G(xq ) = A′ hα √2hR′ , this same Hermite expansion shifted to a new locaα 2 α≥0 tion xR of the parent node of XR is given by G(xq ) = Aγ hγ γ≥0 Aγ = 0≤α≤γ 1 ′ (γ−α)! Aα xR′ −xR √ 2h2 xq −xR √ 2h2 where γ−α . Proof. We simply replace the Hermite function part of the expansion by a new Taylor series, as follows: « x q − x R′ √ 2h2 α≥0 „ « X ′ X 1 „ x R − x R′ « β xq − xR √ √ = Aα (−1)|β| hα+β β! 2h2 2h2 α≥0 β≥0 „ «β « „ X X ′ 1 x R − x R′ xq − xR |β| √ √ (−1) hα+β = Aα β! 2h2 2h2 α≥0 β≥0 „ «β „ « X X ′ 1 x R′ − x R xq − xR √ √ Aα = hα+β β! 2h2 2h2 α≥0 β≥0 3 2 «γ−α „ « „ X X 1 x R′ − x R q ′ 5 hγ x√− xR 4 √ = Aα (γ − α)! 2h2 2h2 γ≥0 0≤α≤γ G(xq ) = where γ = α + β. X A′ hα α „ The next operator acts as a “clean-up” routine in a hierarchical algorithm. Since we can approximate at different scales in the query tree, we must somehow combine all the approximations at the end of the computation. By performing a breadth-ﬁrst traversal of the query tree, the L2L operator shifts a node’s local expansion to the centroid of each child. Lemma 2.3. Local-to-local (L2L) translation operator for Gaussian kernel: Given a Taylor expansion centered at a centroid xQ′ of a query node XQ′ : G(xq ) = xq −xQ′ √ 2h2 Bβ β≥0 β , the Taylor expansion obtained by shift- ing this expansion to the new centroid xQ of the child node XQ is G(xq ) = α≥0 β≥α β! α!(β−α)! Bβ β−α xQ −xQ′ √ 2h2 xq −xQ √ 2h2 α . Proof. Applying the multinomial theorem to to expand about the new center xQ yields: G(xq ) = X Bβ β≥0 = „ XX β≥0 α≤β xq − xQ′ √ 2h2 Bβ «β β! α!(β − α)! „ xQ − xQ′ √ 2h2 «β−α „ xq − xQ √ 2h2 «α . whose summation order can be interchanged to achieve the result. Because the Hermite and the Taylor expansion are truncated after taking pD terms, we incur an error in approximation. The original error bounds for the Gaussian kernel in [9, 10] were wrong and corrections were shown in [3]. Here, we will present all necessary three error bounds incurred in performing translation operators. We note that these error bounds place limits on the size of the query node and the reference node. 2 Lemma 2.4. Error Bound for Truncating an Hermite Expansion (as presented in [3]): Suppose we are given an Hermite expansion of a reference node XR about its centroid xR : G(xq ) = Aα hα α≥0 xq −xR √ 2h2 NR where Aα = r=1 1 α! xr −xR √ 2h2 α . For any query point xq , the error due to truncating the series after the ﬁrst pD term is |ǫM (p)| ≤ rp )k rp √ p! NR (1−r)D D−1 k=0 D k (1 − D−k where ∀xr ∈ XR satisﬁes ||xr − xR ||∞ < rh for r < 1. Proof. (sketch) We expand the Hermite expansion as a product of one-dimensional Hermite functions, and utilize a bound on one-dimensional Hermite functions due to [13]: n −x2 1 2 √ 2 e 2 , n ≥ 0, x ∈ R1 . n! |hn (x)| ≤ n! Lemma 2.5. Error Bound for Truncating a Taylor Expansion Converted from an Hermite Expansion of Inﬁnite Order: Suppose we are given the following Taylor expansion about the centroid xQ of a query node G(xq ) = Bβ β≥0 2 xq −xQ √ 2h2 β where `Strainn[12] proposed the interesting idea of using Stirling’s formula (for any non-negative integer ´ ≤ n!) to lift the node size constraint; one might imagine that this could allow approxin: n+1 e mation of larger regions in a tree-based algorithm. Unfortunately, the error bounds developed in [12] were also incorrect. We have derived the three necessary corrected error bounds based on the techniques in [3]. However, due to space, and because using these bounds actually degraded performance slightly, we do not include those lemmas here. (−1)|β| β! Bβ = Aα hα+β α≥0 xQ −xR √ 2h2 and Aα ’s are the coefﬁcients of the Hermite ex- pansion centered at the reference node centroid xR . Then, truncating the series after pD terms satisﬁes the error bound |ǫL (p)| ≤ NR (1−r)D D−1 k=0 D k (1 − rp )k rp √ p! D−k where ||xq − xQ ||∞ < rh for r < 1, ∀xq ∈ XQ . Proof. Taylor expansion of the Hermite function yields e −||xq −xr ||2 2h2 Use e „ «„ «β X (−1)|β| X 1 „ xr − xR «α xq − xQ xQ − xR √ √ √ hα+β = β! α! 2h2 2h2 2h2 α≥0 β≥0 «α „ «„ «β „ X (−1)|β| X 1 xR − xr xQ − xR xq − xQ |α| √ √ √ = (−1) hα+β β! α! 2h2 2h2 2h2 β≥0 α≥0 «„ «β „ X (−1)|β| xq − xQ xQ − xr √ √ = hβ β! 2h2 2h2 β≥0 −||xq −xr ||2 2h2 D = i=1 (up (xqi , xri , xQi ) + vp (xqi , xri , xQi )) for 1 ≤ i ≤ D, where «„ «n „ X (−1)ni xqi − xQi i xQi − xri √ √ hni ni ! 2h2 2h2 ni =0 „ «„ «ni ∞ X (−1)ni xqi − xQi xQi − xri √ √ hni vp (xqi , xri , xQi ) = . ni ! 2h2 2h2 ni =p p−1 up (xqi , xri , xQi ) = 1−r p 1−r These univariate functions respectively satisfy up (xqi , xri , xQi ) ≤ 1 rp vp (xqi , xri , xQi ) ≤ √p! 1−r , for 1 ≤ i ≤ D, achieving the multivariate bound. and Lemma 2.6. Error Bound for Truncating a Taylor Expansion Converted from an Already Truncated Hermite Expansion: A truncated Hermite expansion centered about xq −xR the centroid xR of a reference node G(xq ) = Aα hα √2h2 has the following α < rh, and a reference node XR for which ||xr − xR ||∞ < rh for r < 1 , ∀xq ∈ XQ , ∀xr ∈ XR . 2 Proof. We deﬁne upi = up (xqi , xri , xQi , xRi ), vpi = vp (xqi , xri , xQi , xRi ), wpi = wp (xqi , xri , xQi , xRi ) for 1 ≤ i ≤ D: upi = „ «„ «ni p−1 X X (−1)ni p−1 1 „ xR − xr «nj xqi − xQi xQi − xRi i i √ √ √ (−1)nj hni +nj ni ! n =0 nj ! 2h2 2h2 2h2 ni =0 j vpi = „ «„ «n ∞ X (−1)ni X 1 „ xR − xr «nj xQi − xRi xqi − xQi i i i √ √ √ (−1)nj hni +nj ni ! n =p nj ! 2h2 2h2 2h2 ni =0 j p−1 wpi = „ «„ «n ∞ ∞ X (−1)ni X 1 „ xR − xr «nj xQi − xRi xqi − xQi i i i √ √ √ (−1)nj hni +nj ni ! n =0 nj ! 2h2 2h2 2h2 ni =p j Note that e −||xq −xr ||2 2h2 D = i=1 (upi + vpi + wpi ) for 1 ≤ i ≤ D. Using the bound for Hermite functions and the property of geometric series, we obtain the following upper bounds: p−1 p−1 upi ≤ X X (2r)ni (2r)nj = ni =0 nj =0 „ 1 − (2r)p ) 1 − 2r «2 „ «„ « p−1 ∞ 1 X X 1 1 − (2r)p (2r)p vpi ≤ √ (2r)ni (2r)nj = √ 1 − 2r 1 − 2r p! n =0 n =p p! i 1 wpi ≤ √ p! j ∞ ∞ X X ni =p nj 1 (2r)ni (2r)nj = √ p! =0 „ 1 1 − 2r «„ (2r)p 1 − 2r « Therefore, ˛ ˛ ! «D−k „ D D−1 ˛ −||xq −xr ||2 ˛ Y X D ((2r)p )(2 − (2r)p ) ˛ ˛ −2D 2 2h √ − upi ˛ ≤ (1 − 2r) ((1 − (2r)p )2 )k ˛e ˛ ˛ k p! i=1 k=0 ˛ ˛ ˛ « ˛ „ „ « D−1 “ ” X D X ˛ xq − xQ β ˛ ((2r)p )(2 − (2r)p ) D−k NR p 2 k ˛≤ ˛G(xq ) − √ ((1 − (2r) ) ) √ Cβ ˛ ˛ 2D (1 − 2r) k p! 2h2 ˛ ˛ k=0 β < 2h, pDH = the smallest p ≥ 1 such that NR (1−r)D D−1 k=0 D k (1 − rp )k rp √ p! D−k < ǫGmin . Q if Q.maxside < 2h, pDL = the smallest p ≥ 1 such that NR (1−r)D D−1 k=0 D k (1 − rp )k rp √ p! D−k < ǫGmin . Q if max(Q.maxside,R.maxside) < h, pH2L = the smallest p ≥ 1 such that NR (1−2r)2D D−1 k=0 D k ((1 − (2r)p )2 )k ((2r)p )(2−(2r)p ) √ p! D−k < ǫGmin . Q cDH = pD NQ . cDL = pD NR . cH2L = DpD+1 . cDirect = DNQ NR . DH DL H2L if no Hermite coefﬁcient of order pDH exists for XR , Compute it. cDH = cDH + pD NR . DH if no Hermite coefﬁcient of order pH2L exists for XR , Compute it. cH2L = cH2L + pD NR . H2L c = min(cDH , cDL , cH2L , cDirect ). if c = cDH < ∞, (Direct Hermite) Evaluate each xq at the Hermite series of order pDH centered about xR of XR using Equation 1. if c = cDL < ∞, (Direct Local) Accumulate each xr ∈ XR as the Taylor series of order pDL about the center xQ of XQ using Equation 2. if c = cH2L < ∞, (Hermite-to-Local) Convert the Hermite series of order pH2L centered about xR of XR to the Taylor series of the same order centered about xQ of XQ using Lemma 2.1. if c = cDirect , Update Gmin and Gmax in Q and all its children. return. if leaf(Q) and leaf(R), Perform the naive algorithm on every pair of points in Q and R. else DFGT(Q.left, R.left). DFGT(Q.left, R.right). DFGT(Q.right, R.left). DFGT(Q.right, R.right). ˛ ˛ ˛b ˛ For the FGT, note that the algorithm only ensures: ˛G(xq ) − Gtrue (xq )˛ ≤ τ . Therefore, we ﬁrst set τ = ǫ, halving τ until the error tolerance ǫ was met. For the IFGT, which has multiple parameters that must be tweaked simultaneously, an automatic scheme was created, based on the recommendations given in the paper and software documentation: For D = 2, use p = 8; for D = 3, √ use p = 6; set ρx = 2.5; start with K = N and double K until the error tolerance is met. When this failed to meet the tolerance, we resorted to additional trial and error by hand. The costs of parameter selection for these methods in both computer and human time is not included in the table. 4 Algorithm \ scale Naive FGT IFGT DFD DFGT DFGTH Naive FGT IFGT DFD DFGT DFGTH Naive FGT IFGT DFD DFGT DFGTH Naive FGT IFGT DFD DFGT DFGTH Naive FGT IFGT DFD DFGT DFGTH 0.001 0.01 0.1 1 10 100 sj2-50000-2 (astronomy: positions), D = 2, N = 50000, h∗ = 0.00139506 301.696 301.696 301.696 301.696 301.696 301.696 out of RAM out of RAM out of RAM 3.892312 2.01846 0.319538 > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive 0.837724 1.087066 1.658592 6.018158 62.077669 151.590062 0.849935 1.11567 4.599235 72.435177 18.450387 2.777454 0.846294 1.10654 1.683913 6.265131 5.063365 1.036626 ∗ = 0.0016911 colors50k (astronomy: colors), D = 2, N = 50000, h 301.696 301.696 301.696 301.696 301.696 301.696 out of RAM out of RAM out of RAM > 2×Naive > 2×Naive 0.475281 > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive 1.095838 1.469454 2.802112 30.294007 280.633106 81.373053 1.099828 1.983888 29.231309 285.719266 12.886239 5.336602 1.081216 1.47692 2.855083 24.598749 7.142465 1.78648 ∗ edsgc-radec-rnd (astronomy: angles), D = 2, N = 50000, h = 0.00466204 301.696 301.696 301.696 301.696 301.696 301.696 out of RAM out of RAM out of RAM 2.859245 1.768738 0.210799 > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive 0.812462 1.083528 1.682261 5.860172 63.849361 357.099354 0.84023 1.120015 4.346061 73.036687 21.652047 3.424304 0.821672 1.104545 1.737799 6.037217 5.7398 1.883216 ∗ mockgalaxy-D-1M-rnd (cosmology: positions), D = 3, N = 50000, h = 0.000768201 354.868751 354.868751 354.868751 354.868751 354.868751 354.868751 out of RAM out of RAM out of RAM out of RAM > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive 0.70054 0.701547 0.761524 0.843451 1.086608 42.022605 0.73007 0.733638 0.799711 0.999316 50.619588 125.059911 0.724004 0.719951 0.789002 0.877564 1.265064 22.6106 ∗ bio5-rnd (biology: drug activity), D = 5, N = 50000, h = 0.000567161 364.439228 364.439228 364.439228 364.439228 364.439228 364.439228 out of RAM out of RAM out of RAM out of RAM out of RAM out of RAM > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive 2.249868 2.4958865 4.70948 12.065697 94.345003 412.39142 > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive > 2×Naive 1000 301.696 0.183616 7.576783 1.551019 2.532401 0.68471 301.696 0.114430 7.55986 3.604753 3.5638 0.627554 301.696 0.059664 7.585585 0.743045 1.977302 0.436596 354.868751 > 2×Naive > 2×Naive 383.12048 109.353701 87.488392 364.439228 out of RAM > 2×Naive 107.675935 > 2×Naive > 2×Naive Discussion. The experiments indicate that the DFGTH method is able to achieve reasonable performance across all bandwidth scales. Unfortunately none of the series approximation-based methods do well on the 5-dimensional data, as expected, highlighting the main weakness of the approach presented. Pursuing corrections to the error bounds necessary to use the intriguing series form of [14] may allow an increase in dimensionality. References [1] A. W. Appel. An Efﬁcient Program for Many-Body Simulations. SIAM Journal on Scientiﬁc and Statistical Computing, 6(1):85–103, 1985. [2] J. Barnes and P. Hut. A Hierarchical O(N logN ) Force-Calculation Algorithm. Nature, 324, 1986. [3] B. Baxter and G. Roussos. A new error estimate of the fast gauss transform. SIAM Journal on Scientiﬁc Computing, 24(1):257–259, 2002. [4] P. Callahan and S. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential ﬁelds. Journal of the ACM, 62(1):67–90, January 1995. [5] A. Gray and A. W. Moore. N-Body Problems in Statistical Learning. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13 (December 2000). MIT Press, 2001. [6] A. G. Gray. Bringing Tractability to Generalized N-Body Problems in Statistical and Scientiﬁc Computation. PhD thesis, Carnegie Mellon University, 2003. [7] A. G. Gray and A. W. Moore. Rapid Evaluation of Multiple Density Models. In Artiﬁcial Intelligence and Statistics 2003, 2003. [8] L. Greengard and V. Rokhlin. A Fast Algorithm for Particle Simulations. Journal of Computational Physics, 73, 1987. [9] L. Greengard and J. Strain. The fast gauss transform. SIAM Journal on Scientiﬁc and Statistical Computing, 12(1):79–94, 1991. [10] L. Greengard and X. Sun. A new version of the fast gauss transform. Documenta Mathematica, Extra Volume ICM(III):575– 584, 1998. [11] B. W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall, 1986. [12] J. Strain. The fast gauss transform with variable scales. SIAM Journal on Scientiﬁc and Statistical Computing, 12:1131– 1139, 1991. [13] O. Sz´ sz. On the relative extrema of the hermite orthogonal functions. J. Indian Math. Soc., 15:129–134, 1951. a [14] C. Yang, R. Duraiswami, N. A. Gumerov, and L. Davis. Improved fast gauss transform and efﬁcient kernel density estimation. International Conference on Computer Vision, 2003.

6 0.32173967 111 nips-2005-Learning Influence among Interacting Markov Chains

7 0.28378183 45 nips-2005-Conditional Visual Tracking in Kernel Space

8 0.2728745 33 nips-2005-Bayesian Sets

9 0.25269562 119 nips-2005-Learning to Control an Octopus Arm with Gaussian Process Temporal Difference Methods

10 0.23282026 200 nips-2005-Variable KD-Tree Algorithms for Spatial Pattern Search and Discovery

11 0.22160761 80 nips-2005-Gaussian Process Dynamical Models

12 0.21382436 72 nips-2005-Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation

13 0.20509417 73 nips-2005-Fast biped walking with a reflexive controller and real-time policy searching

14 0.20413391 157 nips-2005-Principles of real-time computing with feedback applied to cortical microcircuit models

15 0.20227993 53 nips-2005-Cyclic Equilibria in Markov Games

16 0.2008805 156 nips-2005-Prediction and Change Detection

17 0.19944412 20 nips-2005-Affine Structure From Sound

18 0.18506028 44 nips-2005-Computing the Solution Path for the Regularized Support Vector Regression

19 0.18422914 67 nips-2005-Extracting Dynamical Structure Embedded in Neural Activity

20 0.18391784 18 nips-2005-Active Learning For Identifying Function Threshold Boundaries

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(3, 0.034), (10, 0.044), (27, 0.038), (31, 0.041), (34, 0.06), (39, 0.011), (45, 0.01), (55, 0.038), (65, 0.019), (69, 0.058), (71, 0.015), (73, 0.024), (88, 0.1), (89, 0.376), (91, 0.021)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.77223152 120 nips-2005-Learning vehicular dynamics, with application to modeling helicopters

Author: Pieter Abbeel, Varun Ganapathi, Andrew Y. Ng

2 0.37129816 45 nips-2005-Conditional Visual Tracking in Kernel Space

Author: Cristian Sminchisescu, Atul Kanujia, Zhiguo Li, Dimitris Metaxas

3 0.36828223 21 nips-2005-An Alternative Infinite Mixture Of Gaussian Process Experts

Author: Edward Meeds, Simon Osindero

Abstract: We present an inﬁnite mixture model in which each component comprises a multivariate Gaussian distribution over an input space, and a Gaussian Process model over an output space. Our model is neatly able to deal with non-stationary covariance functions, discontinuities, multimodality and overlapping output signals. The work is similar to that by Rasmussen and Ghahramani [1]; however, we use a full generative model over input and output space rather than just a conditional model. This allows us to deal with incomplete data, to perform inference over inverse functional mappings as well as for regression, and also leads to a more powerful and consistent Bayesian speciﬁcation of the effective ‘gating network’ for the different experts. 1

4 0.36731789 200 nips-2005-Variable KD-Tree Algorithms for Spatial Pattern Search and Discovery

Author: Jeremy Kubica, Joseph Masiero, Robert Jedicke, Andrew Connolly, Andrew W. Moore

Abstract: In this paper we consider the problem of ﬁnding sets of points that conform to a given underlying model from within a dense, noisy set of observations. This problem is motivated by the task of efﬁciently linking faint asteroid detections, but is applicable to a range of spatial queries. We survey current tree-based approaches, showing a trade-off exists between single tree and multiple tree algorithms. To this end, we present a new type of multiple tree algorithm that uses a variable number of trees to exploit the advantages of both approaches. We empirically show that this algorithm performs well using both simulated and astronomical data.

5 0.36596793 136 nips-2005-Noise and the two-thirds power Law

Author: Uri Maoz, Elon Portugaly, Tamar Flash, Yair Weiss

Abstract: The two-thirds power law, an empirical law stating an inverse non-linear relationship between the tangential hand speed and the curvature of its trajectory during curved motion, is widely acknowledged to be an invariant of upper-limb movement. It has also been shown to exist in eyemotion, locomotion and was even demonstrated in motion perception and prediction. This ubiquity has fostered various attempts to uncover the origins of this empirical relationship. In these it was generally attributed either to smoothness in hand- or joint-space or to the result of mechanisms that damp noise inherent in the motor system to produce the smooth trajectories evident in healthy human motion. We show here that white Gaussian noise also obeys this power-law. Analysis of signal and noise combinations shows that trajectories that were synthetically created not to comply with the power-law are transformed to power-law compliant ones after combination with low levels of noise. Furthermore, there exist colored noise types that drive non-power-law trajectories to power-law compliance and are not affected by smoothing. These results suggest caution when running experiments aimed at verifying the power-law or assuming its underlying existence without proper analysis of the noise. Our results could also suggest that the power-law might be derived not from smoothness or smoothness-inducing mechanisms operating on the noise inherent in our motor system but rather from the correlated noise which is inherent in this motor system. 1

6 0.36573651 144 nips-2005-Off-policy Learning with Options and Recognizers

7 0.36573127 132 nips-2005-Nearest Neighbor Based Feature Selection for Regression and its Application to Neural Activity

8 0.36349624 30 nips-2005-Assessing Approximations for Gaussian Process Classification

9 0.36347756 74 nips-2005-Faster Rates in Regression via Active Learning

10 0.36343232 60 nips-2005-Dynamic Social Network Analysis using Latent Space Models

11 0.36266866 179 nips-2005-Sparse Gaussian Processes using Pseudo-inputs

12 0.36264908 23 nips-2005-An Application of Markov Random Fields to Range Sensing

13 0.36153457 48 nips-2005-Context as Filtering

14 0.36135244 69 nips-2005-Fast Gaussian Process Regression using KD-Trees

15 0.36124378 171 nips-2005-Searching for Character Models

16 0.36074638 67 nips-2005-Extracting Dynamical Structure Embedded in Neural Activity

17 0.35851362 72 nips-2005-Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation

18 0.35756075 94 nips-2005-Identifying Distributed Object Representations in Human Extrastriate Visual Cortex

19 0.357546 16 nips-2005-A matching pursuit approach to sparse Gaussian process regression

20 0.35709694 92 nips-2005-Hyperparameter and Kernel Learning for Graph Based Semi-Supervised Classification