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

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

Source: pdf

Author: Jin Yu, Douglas Aberdeen, Nicol N. Schraudolph

Abstract: Reinforcement learning by direct policy gradient estimation is attractive in theory but in practice leads to notoriously ill-behaved optimization problems. We improve its robustness and speed of convergence with stochastic meta-descent, a gain vector adaptation method that employs fast Hessian-vector products. In our experiments the resulting algorithms outperform previously employed online stochastic, ofﬂine conjugate, and natural policy gradient methods. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 au Abstract Reinforcement learning by direct policy gradient estimation is attractive in theory but in practice leads to notoriously ill-behaved optimization problems. [sent-6, score-0.362]

2 We improve its robustness and speed of convergence with stochastic meta-descent, a gain vector adaptation method that employs fast Hessian-vector products. [sent-7, score-0.28]

3 In our experiments the resulting algorithms outperform previously employed online stochastic, ofﬂine conjugate, and natural policy gradient methods. [sent-8, score-0.47]

4 1 Introduction Policy gradient reinforcement learning (RL) methods train controllers by estimating the gradient of a long-term reward measure with respect to the parameters of the controller [1]. [sent-9, score-0.597]

5 The advantage of policy gradient methods, compared to value-based RL, is that we avoid the often redundant step of accurately estimating a large number of values. [sent-10, score-0.362]

6 Policy gradient methods are particularly appealing when large state spaces make representing the exact value function infeasible, or when partial observability is introduced. [sent-11, score-0.229]

7 However, in practice policy gradient methods have shown slow convergence [2], not least due to the stochastic nature of the gradients being estimated. [sent-12, score-0.474]

8 The stochastic meta-descent (SMD) gain adaptation algorithm [3, 4] can considerably accelerate the convergence of stochastic gradient descent. [sent-13, score-0.495]

9 In contrast to other gain adaptation methods, SMD copes well not only with stochasticity, but also with non-i. [sent-14, score-0.128]

10 In this paper we derive SMD in the context of policy gradient RL, and obtain over an order of magnitude improvement in convergence rate compared to previously employed policy gradient algorithms. [sent-18, score-0.785]

11 1 Stochastic Meta-Descent Gradient-based gain vector adaptation Let R be a scalar objective function we wish to maximize with respect to its adaptive parameter vector θ ∈ Rn , given a sequence of observations xt ∈ X at time t = 1, 2, . [sent-20, score-0.271]

12 Where R is not available or expensive to compute, we use the stochastic approximation Rt : Rn × X → R of R instead, and maximize the expectation Et [Rt (θt , xt )]. [sent-23, score-0.146]

13 θ, with gradient and Hessian given by gt = ∂ ∂θ Rt (θ, xt )|θ=θt and Ht = ∂2 ∂θ ∂θ Rt (θ, xt )|θ=θt , (1) respectively, we maximize Et [Rt (θ)] by the stochastic gradient ascent θt+1 = θt + γt · gt , (2) + n where · denotes element-wise (Hadamard) multiplication. [sent-25, score-0.957]

14 The gain vector γt ∈ (R ) serves as a diagonal conditioner, providing each element of θ with its own positive gradient step size. [sent-26, score-0.274]

15 We adapt γ by a simultaneous meta-level gradient ascent in the objective Rt . [sent-27, score-0.212]

16 A straightforward implementation of this idea is the delta-delta algorithm [5], which would update γ via ∂Rt+1 (θt+1 ) ∂Rt+1 (θt+1 ) ∂θt+1 = γt + µ · = γt + µgt+1 · gt , (3) ∂γt ∂θt+1 ∂γt where µ ∈ R is a scalar meta-step size. [sent-28, score-0.24]

17 In a nutshell, gains are decreased where a negative autocorrelation of the gradient indicates oscillation about a local minimum, and increased otherwise. [sent-29, score-0.268]

18 Unfortunately such a simplistic approach has several problems: Firstly, (3) allows gains to become negative. [sent-30, score-0.052]

19 Secondly, delta-delta’s cure is worse than the disease: individual gains are meant to address ill-conditioning, but (3) actually squares the condition number. [sent-34, score-0.052]

20 The autocorrelation of the gradient must therefore be normalized before it can be used. [sent-35, score-0.216]

21 Such sign-based methods [5, 7–9], however, do not cope well with stochastic approximation of the gradient since the non-linear sign function does not commute with the expectation operator [10]. [sent-37, score-0.255]

22 Finally, (3) fails to take into account that gain changes affect not only the current, but also future parameter updates. [sent-39, score-0.061]

23 In recognition of this shortcoming, gt in (3) is often replaced with a running average of past gradients. [sent-40, score-0.194]

24 By contrast, Sutton [11] modeled the long-term effect of gains on future parameter values in a linear system by carrying the relevant partials forward in time, and found that the resulting gain adaptation can outperform a less than perfectly matched Kalman ﬁlter. [sent-42, score-0.226]

25 2 The SMD Algorithm SMD employs two modiﬁcations to address the problems described above: it adjusts gains in log-space, and optimizes over an exponentially decaying trace of gradients. [sent-45, score-0.134]

26 Elementwise exponentiation of (4) yields the desired multiplicative update γt+1 = γt · exp(µ gt+1 · vt+1 ) ≈ γt · max( 1 , 1 + µ gt+1 · vt+1 ). [sent-47, score-0.048]

27 2 u max( 1 , 1+u) 2 (5) The linearization e ≈ eliminates an expensive exponentiation for each gain update, improves its robustness by reducing the effect of outliers (|u| 0), and ensures that γ remains positive. [sent-48, score-0.113]

28 (7) 2 Although the Hessian of a system with n parameters has O(n ) entries, efﬁcient indirect methods from algorithmic differentiation are available to compute its product with an arbitrary vector in the same time as 2–3 gradient evaluations [12, 13]. [sent-50, score-0.213]

29 An iteration of SMD — comprising (5), (2), and (7) — thus requires less than 3 times the ﬂoating-point operations of simple gradient ascent. [sent-52, score-0.196]

30 The extra computation is typically more than compensated for by the faster convergence of SMD. [sent-53, score-0.062]

31 Fast convergence minimizes the number of expensive world interactions required, which in RL is typically of greater concern than computational cost. [sent-54, score-0.078]

32 3 Policy Gradient Reinforcement Learning A Markov decision process (MDP) consists of a ﬁnite1 set of states s ∈ S of the world, actions a ∈ A available to the agent in each state, and a (possibly stochastic) reward function r(s) for each state s. [sent-55, score-0.169]

33 Each action a determines a stochastic matrix P (a) = [P(s |s, a)] of transition probabilities from state s to state s given action a. [sent-57, score-0.3]

34 All policies are stochastic, with a probability of choosing action a given state s, and parameters θ ∈ Rn of P(a|θ, s). [sent-59, score-0.107]

36 1 GP OMDP Monte Carlo estimates of gradient and hessian GP OMDP is an inﬁnite-horizon policy gradient method [1] to compute the gradient of the T long-term average reward 1 R(θ) := lim Eθ r(st ) , (9) T →∞ T t=1 with respect the policy parameters θ. [sent-62, score-1.094]

37 a policy parameter θi is θi R(θ) = π(θ) θi P (θ)[I − P (θ) + uπ(θ) ]−1 r , (10) where π(θ) is the stationary distribution of states induced by θ. [sent-69, score-0.166]

38 The GP OMDP algorithm instead computes a Monte-Carlo approximation of (10): the agent interacts with the environment, producing an observation, action, reward sequence {x1 , a1 , r1 , x2 , . [sent-72, score-0.113]

39 Without it, rewards would be assigned over a potentially inﬁnite horizon, resulting in gradient estimates with inﬁnite variance. [sent-77, score-0.219]

40 As β decreases, so does the variance, but the bias of the gradient estimate increases [1]. [sent-78, score-0.196]

41 In practice, (11) is implemented efﬁciently via the discounted eligibility trace et = βet−1 + δt , where δt := θ P(at |θ, st )/ P(at |θ, st ) . [sent-79, score-0.264]

42 (12) Now gt = rt et is the gradient of R(θ) arising from assigning the instantaneous reward to all log action gradients, where β gives exponentially more credit to recent actions. [sent-80, score-0.892]

43 Likewise, Baxter and Bartlett [1] give the Monte Carlo estimate of the Hessian as Ht = rt (Et + et et ), using an eligibility trace matrix Et = βEt−1 + Gt − δt δt , where Gt := 2 θ P(at |θ, st )/ P(at |θ, st ) . [sent-81, score-0.498]

44 (13) 2 Maintaining E would be O(n ), thus computationally expensive for large policy parameter spaces. [sent-82, score-0.193]

45 Noting that SMD only requires the product of Ht with a vector v, we instead use Ht v = rt [dt + et (et v)] , where dt = βdt−1 + Gt v − δt (δt v) (14) is an eligibility trace vector that can be maintained in O(n). [sent-83, score-0.413]

46 We describe the efﬁcient computation of Gt v in (14) for a speciﬁc action selection method in Section 3. [sent-84, score-0.074]

47 2 GP OMDP-Based optimization algorithms Baxter et al. [sent-87, score-0.072]

48 [2] proposed two optimization algorithms using GP OMDP’s policy gradient estimates gt : O L P OMDP is a simple online stochastic gradient descent (2) with scalar gain γt . [sent-88, score-0.932]

49 Alternatively, C ONJ P OMDP performs Polak-Ribi` re conjugation of search directions, e using a noise-tolerant line search to ﬁnd the approximately best scalar step size in a given search direction. [sent-89, score-0.06]

50 Since conjugate gradient methods are very sensitive to noise [14], C ONJ P OMDP must average gt over many steps to obtain a reliable gradient measurement; this makes the algorithm inherently inefﬁcient (cf. [sent-90, score-0.607]

51 We can, however, employ SMD’s gain vector adaptation to greatly accelerate it while retaining the beneﬁts of high noise tolerance and online learning. [sent-93, score-0.202]

52 Kakade [15] has applied natural gradient [16] to GP OMDP, premultiplying the policy gradient by the inverse of the online estimate 1 Ft = (1 − t )Ft−1 + 1 (δt δt t + I) (15) of the Fisher information matrix for the parameter update: θt+1 = θt + γ0 · rt Ft−1 et . [sent-95, score-0.851]

53 This approach can yield very fast convergence on small problems, but in our experience does not scale well at all to larger, more realistic tasks; see our experiments in Section 4. [sent-96, score-0.053]

54 2 We use rt as shorthand for r(st ), making it clear that only the reward value is known, not the underlying state st . [sent-97, score-0.349]

55 Given action at ∼ zt , GP OMDP’s instantaneous log-action gradient wrt. [sent-100, score-0.538]

56 y is then ˜ gt := y [zt ]at /[zt ]at = uat − zt , (17) where ui is the unity vector in direction i. [sent-101, score-0.507]

57 θ is obtained by ˜ backpropagating gt through f ’s adjoint system [13], performing an efﬁcient multiplication ˜ by the transposed Jacobian of f . [sent-103, score-0.251]

58 The resulting gradient δt := Jf gt is then accumulated in the eligibility trace (12). [sent-104, score-0.5]

59 GP OMDP’s instantaneous Hessian for softmax action selection is ˜ Ht := 2 y [zt ]at /[zt ]at = (uat −zt )(uat −zt ) + zt zt − diag(zt ) . [sent-105, score-0.633]

60 Furthermore, its 4 expectation over possible actions is zero: ˜ Ezt (Ht ) = [diag(zt ) − 2zt zt + zt zt ] + zt zt − diag(zt ) = 0 . [sent-107, score-1.148]

61 (19) The extended Gauss-Newton matrix-vector product [4] employed by SMD is then given by ˜ Gt vt := Jf Ht Jf vt , (20) where the multiplication by the Jacobian off (resp. [sent-108, score-0.341]

62 its transpose) is implemented efﬁciently by propagating vt through f ’s tangent linear (resp. [sent-109, score-0.145]

63 Algorithm 1 S MD P OMDP with softmax action selection 1. [sent-111, score-0.14]

64 qt := (uat − zt )(δt vt ) + zt (zt pt ) − zt · pt iv. [sent-121, score-0.892]

65 dt = βdt−1 + Jf qt − δt (δt vt ) (c) update SMD parameters: i. [sent-123, score-0.219]

66 vt+1 = λvt + rt γt · [(1 + λet vt )et + λdt ] 6/18 12/18 12/18 6/18 5/18 5/18 6 12 5 12/18 6/18 5/18 r=0 r=0 r=1 r=1 r = -1 r=8 Fig. [sent-126, score-0.307]

67 States are labelled with their observable features and instantaneous reward r; arrows indicate the 80% likely transition for the ﬁrst (solid) resp. [sent-129, score-0.183]

68 1 (left) depicts the simple 3-state POMDP used by Baxter et al. [sent-134, score-0.072]

69 The preferred transition is determined by the action of a simple probabilistic adaptive controller that receives two state-dependent feature values as input, and is trained to maximize the expected average reward by policy gradient methods. [sent-137, score-0.667]

70 We then implemented S MD P OMDP (Algorithm 1), and ran a comparison of algorithms, using the best free parameter settings found by Baxter et al. [sent-141, score-0.088]

71 [2] collect and plot results for C ONJ P OMDP in terms of its T parameter, which speciﬁes the number of Markov chain iterations per gradient evaluation. [sent-145, score-0.259]

72 For a fair comparison of convergence speed we added code to record the total number of Markov chain iterations consumed by C ONJ P OMDP, and plot performance for all three algorithms in those terms, with error bars along both axes for C ONJ P OMDP. [sent-146, score-0.096]

73 While early on C ONJ P OMDP on average reaches a given level of performance about three times faster than O L P OMDP, it does so at the price of far higher variance. [sent-149, score-0.048]

74 Once its step size adaptation gets going, S MD P OMDP converges asymptotically to the op2. [sent-153, score-0.089]

75 C ONJ P OMDP converges faster but to asymptotically inferior solutions (see inset) than the two online algorithms. [sent-173, score-0.105]

76 Natural policy gradient has rapid early convergence but diverges asymptotically. [sent-176, score-0.414]

77 timal policy about three times faster than O L P OMDP in terms of Markov chain iterations, making the two algorithms roughly equal in terms of computational expense. [sent-177, score-0.221]

78 C ONJ P OMDP on average performs less than two iterations of conjugate gradient in each run. [sent-178, score-0.254]

79 While this is perfectly understandable — the controller only has two trainable parameters — it bears keeping in mind that the performance of C ONJ P OMDP here is almost entirely governed by the line search rather than the conjugation of search directions. [sent-179, score-0.112]

80 2 Modiﬁed Three-State POMDP The three-state POMDP employed by Baxter et al. [sent-181, score-0.1]

81 [2] has the property that greedy maximization of instantaneous reward leads to the optimal policy. [sent-182, score-0.156]

82 The best results are obtained with the eligibility trace turned off (β = 0). [sent-184, score-0.11]

83 To create a more challenging problem, we rearranged the POMDP’s state transitions and reward structure so that the instantaneous reward becomes deceptive (Fig. [sent-185, score-0.302]

84 We also multiplied one state feature by 18 to create an ill-conditioned input to the controller, while leaving the actions and relative transition probabilities (80% resp. [sent-187, score-0.083]

85 In our modiﬁed POMDP, the high-reward state can only be reached through an intermediate state with negative reward. [sent-189, score-0.066]

86 S MD P OMDP converges about 20 times faster than O L P OMDP because its adjustable gains compensate for the ill-conditioned input. [sent-199, score-0.081]

87 01) performs extremely well early on, taking 2–3 times fewer iterations than S MD P OMDP to reach optimal performance (R = 2. [sent-201, score-0.056]

88 3 Puck World We also implemented the Puck World benchmark of Baxter et al. [sent-205, score-0.072]

89 To improve its stability, we modiﬁed SMD here to track instantaneous log-action gradients δt instead of noisy rt et estimates of θ R. [sent-212, score-0.297]

90 5, with the adaptive reduction schedule described by Baxter et al. [sent-214, score-0.098]

91 3 shows our results averaged over 100 runs, except for natural policy gradient where only a single typical run is shown. [sent-217, score-0.384]

92 3: The action-gradient version of S MD P OMDP yields better asymptotic results on PuckWorld than O L P OMDP; C ONJ P OMDP is inefﬁcient; natural policy gradient even more so. [sent-220, score-0.384]

93 Average Reward SMD Gains 3 -20 smd ol conj ng -30 -40 -50 -60 1e+5 1e+6 1e+7 Iterations 1e+8 makes natural policy gradient intolerably slow for this task, where n = 88. [sent-221, score-0.72]

94 Moreover, its convergence is quite poor here in terms of the number of iterations required as well. [sent-222, score-0.07]

95 C ONJ P OMDP is again inferior to the best online algorithms by over an order of magnitude. [sent-223, score-0.054]

96 S MD P OMDP-trained controllers achieve a long-term average reward of -6. [sent-225, score-0.134]

97 5, signiﬁcantly above the optimum of -8 hypothesized by Baxter et al. [sent-226, score-0.072]

98 Natural policy gradient can converge rapidly, but is too unstable and computationally expensive for all but very small controllers. [sent-229, score-0.389]

99 A direct adaptive method for faster backpropagation learning: The RPROP algorithm. [sent-292, score-0.073]

100 Combining conjugate direction methods with stochastic approximation of gradients. [sent-329, score-0.08]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('omdp', 0.654), ('onj', 0.299), ('smd', 0.256), ('zt', 0.225), ('gradient', 0.196), ('gt', 0.194), ('policy', 0.166), ('rt', 0.162), ('vt', 0.145), ('md', 0.139), ('baxter', 0.135), ('pomdp', 0.126), ('reward', 0.113), ('jf', 0.099), ('ht', 0.081), ('action', 0.074), ('et', 0.072), ('uat', 0.071), ('eligibility', 0.068), ('adaptation', 0.067), ('softmax', 0.066), ('ln', 0.064), ('gain', 0.061), ('hessian', 0.061), ('stochastic', 0.059), ('gp', 0.054), ('gains', 0.052), ('controller', 0.047), ('conj', 0.043), ('instantaneous', 0.043), ('rn', 0.042), ('xt', 0.042), ('trace', 0.042), ('st', 0.041), ('rl', 0.038), ('online', 0.037), ('conjugation', 0.037), ('ol', 0.037), ('iterations', 0.037), ('dt', 0.035), ('adjoint', 0.034), ('state', 0.033), ('convergence', 0.033), ('faster', 0.029), ('almeida', 0.028), ('puck', 0.028), ('schraudolph', 0.028), ('pt', 0.028), ('governed', 0.028), ('employed', 0.028), ('transition', 0.027), ('australia', 0.027), ('expensive', 0.027), ('adaptive', 0.026), ('chain', 0.026), ('partials', 0.025), ('exponentiation', 0.025), ('reinforcement', 0.024), ('ft', 0.023), ('rewards', 0.023), ('actions', 0.023), ('update', 0.023), ('scalar', 0.023), ('employs', 0.023), ('multiplication', 0.023), ('jacobian', 0.023), ('natural', 0.022), ('asymptotically', 0.022), ('yt', 0.022), ('bartlett', 0.022), ('conjugate', 0.021), ('credit', 0.021), ('australian', 0.021), ('controllers', 0.021), ('outperform', 0.021), ('gradients', 0.02), ('accelerate', 0.02), ('autocorrelation', 0.02), ('inset', 0.02), ('fast', 0.02), ('pages', 0.019), ('exponentiated', 0.019), ('ict', 0.019), ('early', 0.019), ('diag', 0.018), ('backpropagation', 0.018), ('world', 0.018), ('maximize', 0.018), ('markov', 0.017), ('kakade', 0.017), ('inef', 0.017), ('inferior', 0.017), ('vector', 0.017), ('exponentially', 0.017), ('networks', 0.016), ('free', 0.016), ('modi', 0.016), ('ascent', 0.016), ('qt', 0.016), ('mdp', 0.016)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999988 72 nips-2005-Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation

Author: Jin Yu, Douglas Aberdeen, Nicol N. Schraudolph

2 0.15764134 144 nips-2005-Off-policy Learning with Options and Recognizers

Author: Doina Precup, Cosmin Paduraru, Anna Koop, Richard S. Sutton, Satinder P. Singh

Abstract: We introduce a new algorithm for off-policy temporal-difference learning with function approximation that has lower variance and requires less knowledge of the behavior policy than prior methods. We develop the notion of a recognizer, a ﬁlter on actions that distorts the behavior policy to produce a related target policy with low-variance importance-sampling corrections. We also consider target policies that are deviations from the state distribution of the behavior policy, such as potential temporally abstract options, which further reduces variance. This paper introduces recognizers and their potential advantages, then develops a full algorithm for linear function approximation and proves that its updates are in the same direction as on-policy TD updates, which implies asymptotic convergence. Even though our algorithm is based on importance sampling, we prove that it requires absolutely no knowledge of the behavior policy for the case of state-aggregation function approximators. Off-policy learning is learning about one way of behaving while actually behaving in another way. For example, Q-learning is an off- policy learning method because it learns about the optimal policy while taking actions in a more exploratory fashion, e.g., according to an ε-greedy policy. Off-policy learning is of interest because only one way of selecting actions can be used at any time, but we would like to learn about many different ways of behaving from the single resultant stream of experience. For example, the options framework for temporal abstraction involves considering a variety of different ways of selecting actions. For each such option one would like to learn a model of its possible outcomes suitable for planning and other uses. Such option models have been proposed as fundamental building blocks of grounded world knowledge (Sutton, Precup & Singh, 1999; Sutton, Rafols & Koop, 2005). Using off-policy learning, one would be able to learn predictive models for many options at the same time from a single stream of experience. Unfortunately, off-policy learning using temporal-difference methods has proven problematic when used in conjunction with function approximation. Function approximation is essential in order to handle the large state spaces that are inherent in many problem do- mains. Q-learning, for example, has been proven to converge to an optimal policy in the tabular case, but is unsound and may diverge in the case of linear function approximation (Baird, 1996). Precup, Sutton, and Dasgupta (2001) introduced and proved convergence for the ﬁrst off-policy learning algorithm with linear function approximation. They addressed the problem of learning the expected value of a target policy based on experience generated using a different behavior policy. They used importance sampling techniques to reduce the off-policy case to the on-policy case, where existing convergence theorems apply (Tsitsiklis & Van Roy, 1997; Tadic, 2001). There are two important difﬁculties with that approach. First, the behavior policy needs to be stationary and known, because it is needed to compute the importance sampling corrections. Second, the importance sampling weights are often ill-conditioned. In the worst case, the variance could be inﬁnite and convergence would not occur. The conditions required to prevent this were somewhat awkward and, even when they applied and asymptotic convergence was assured, the variance could still be high and convergence could be slow. In this paper we address both of these problems in the context of off-policy learning for options. We introduce the notion of a recognizer. Rather than specifying an explicit target policy (for instance, the policy of an option), about which we want to make predictions, a recognizer speciﬁes a condition on the actions that are selected. For example, a recognizer for the temporally extended action of picking up a cup would not specify which hand is to be used, or what the motion should be at all different positions of the cup. The recognizer would recognize a whole variety of directions of motion and poses as part of picking the cup. The advantage of this strategy is not that one might prefer a multitude of different behaviors, but that the behavior may be based on a variety of different strategies, all of which are relevant, and we would like to learn from any of them. In general, a recognizer is a function that recognizes or accepts a space of different ways of behaving and thus, can learn from a wider range of data. Recognizers have two advantages over direct speciﬁcation of a target policy: 1) they are a natural and easy way to specify a target policy for which importance sampling will be well conditioned, and 2) they do not require the behavior policy to be known. The latter is important because in many cases we may have little knowledge of the behavior policy, or a stationary behavior policy may not even exist. We show that for the case of state aggregation, even if the behavior policy is unknown, convergence to a good model is achieved. 1 Non-sequential example The beneﬁts of using recognizers in off-policy learning can be most easily seen in a nonsequential context with a single continuous action. Suppose you are given a sequence of sample actions ai ∈ [0, 1], selected i.i.d. according to probability density b : [0, 1] → ℜ+ (the behavior density). For example, suppose the behavior density is of the oscillatory form shown as a red line in Figure 1. For each each action, ai , we observe a corresponding outcome, zi ∈ ℜ, a random variable whose distribution depends only on ai . Thus the behavior density induces an outcome density. The on-policy problem is to estimate the mean mb of the outcome density. This problem can be solved simply by averaging the sample outcomes: mb = (1/n) ∑n zi . The off-policy problem is to use this same data to learn what ˆ i=1 the mean would be if actions were selected in some way other than b, for example, if the actions were restricted to a designated range, such as between 0.7 and 0.9. There are two natural ways to pose this off-policy problem. The most straightforward way is to be equally interested in all actions within the designated region. One professes to be interested in actions selected according to a target density π : [0, 1] → ℜ+ , which in the example would be 5.0 between 0.7 and 0.9, and zero elsewhere, as in the dashed line in 12 Probability density functions 1.5 Target policy with recognizer 1 Target policy w/o recognizer without recognizer .5 Behavior policy 0 0 Action 0.7 Empirical variances (average of 200 sample variances) 0.9 1 0 10 with recognizer 100 200 300 400 500 Number of sample actions Figure 1: The left panel shows the behavior policy and the target policies for the formulations of the problem with and without recognizers. The right panel shows empirical estimates of the variances for the two formulations as a function of the number sample actions. The lowest line is for the formulation using empirically-estimated recognition probabilities. Figure 1 (left). The importance- sampling estimate of the mean outcome is 1 n π(ai ) mπ = ∑ ˆ zi . n i=1 b(ai ) (1) This approach is problematic if there are parts of the region of interest where the behavior density is zero or very nearly so, such as near 0.72 and 0.85 in the example. Here the importance sampling ratios are exceedingly large and the estimate is poorly conditioned (large variance). The upper curve in Figure 1 (right) shows the empirical variance of this estimate as a function of the number of samples. The spikes and uncertain decline of the empirical variance indicate that the distribution is very skewed and that the estimates are very poorly conditioned. The second way to pose the problem uses recognizers. One professes to be interested in actions to the extent that they are both selected by b and within the designated region. This leads to the target policy shown in blue in the left panel of Figure 1 (it is taller because it still must sum to 1). For this problem, the variance of (1) is much smaller, as shown in the lower two lines of Figure 1 (right). To make this way of posing the problem clear, we introduce the notion of a recognizer function c : A → ℜ+ . The action space in the example is A = [0, 1] and the recognizer is c(a) = 1 for a between 0.7 and 0.9 and is zero elsewhere. The target policy is deﬁned in general by c(a)b(a) c(a)b(a) = . (2) π(a) = µ ∑x c(x)b(x) where µ = ∑x c(x)b(x) is a constant, equal to the probability of recognizing an action from the behavior policy. Given π, mπ from (1) can be rewritten in terms of the recognizer as ˆ n π(ai ) 1 n c(ai )b(ai ) 1 1 n c(ai ) 1 mπ = ∑ zi ˆ = ∑ zi = ∑ zi (3) n i=1 b(ai ) n i=1 µ b(ai ) n i=1 µ Note that the target density does not appear at all in the last expression and that the behavior distribution appears only in µ, which is independent of the sample action. If this constant is known, then this estimator can be computed with no knowledge of π or b. The constant µ can easily be estimated as the fraction of recognized actions in the sample. The lowest line in Figure 1 (right) shows the variance of the estimator using this fraction in place of the recognition probability. Its variance is low, no worse than that of the exact algorithm, and apparently slightly lower. Because this algorithm does not use the behavior density, it can be applied when the behavior density is unknown or does not even exist. For example, suppose actions were selected in some deterministic, systematic way that in the long run produced an empirical distribution like b. This would be problematic for the other algorithms but would require no modiﬁcation of the recognition-fraction algorithm. 2 Recognizers improve conditioning of off-policy learning The main use of recognizers is in formulating a target density π about which we can successfully learn predictions, based on the current behavior being followed. Here we formalize this intuition. Theorem 1 Let A = {a1 , . . . ak } ⊆ A be a subset of all the possible actions. Consider a ﬁxed behavior policy b and let πA be the class of policies that only choose actions from A, i.e., if π(a) > 0 then a ∈ A. Then the policy induced by b and the binary recognizer cA is the policy with minimum-variance one-step importance sampling corrections, among those in πA : π(ai ) 2 π as given by (2) = arg min Eb (4) π∈πA b(ai ) Proof: Denote π(ai ) = πi , b(ai ) = bi . Then the expected variance of the one-step importance sampling corrections is: Eb πi bi πi bi 2 2 − Eb = ∑ bi i πi bi 2 −1 = ∑ i π2 i − 1, bi where the summation (here and everywhere below) is such that the action ai ∈ A. We want to ﬁnd πi that minimizes this expression, subject to the constraint that ∑i πi = 1. This is a constrained optimization problem. To solve it, we write down the corresponding Lagrangian: π2 L(πi , β) = ∑ i − 1 + β(∑ πi − 1) i i bi We take the partial derivatives wrt πi and β and set them to 0: βbi ∂L 2 = πi + β = 0 ⇒ πi = − ∂πi bi 2 (5) ∂L = πi − 1 = 0 ∂β ∑ i (6) By taking (5) and plugging into (6), we get the following expression for β: − β 2 bi = 1 ⇒ β = − 2∑ ∑i bi i By substituting β into (5) we obtain: πi = bi ∑i b i This is exactly the policy induced by the recognizer deﬁned by c(ai ) = 1 iff ai ∈ A. We also note that it is advantageous, from the point of view of minimizing the variance of the updates, to have recognizers that accept a broad range of actions: Theorem 2 Consider two binary recognizers c1 and c2 , such that µ1 > µ2 . Then the importance sampling corrections for c1 have lower variance than the importance sampling corrections for c2 . Proof: From the previous theorem, we have the variance of a recognizer cA : Var = ∑ i π2 bi i −1 = ∑ bi ∑ j∈A b j i 2 1 1 1 −1 = −1 = −1 bi µ ∑ j∈A b j 3 Formal framework for sequential problems We turn now to the full case of learning about sequential decision processes with function approximation. We use the standard framework in which an agent interacts with a stochastic environment. At each time step t, the agent receives a state st and chooses an action at . We assume for the moment that actions are selected according to a ﬁxed behavior policy, b : S × A → [0, 1] where b(s, a) is the probability of selecting action a in state s. The behavior policy is used to generate a sequence of experience (observations, actions and rewards). The goal is to learn, from this data, predictions about different ways of behaving. In this paper we focus on learning predictions about expected returns, but other predictions can be tackled as well (for instance, predictions of transition models for options (Sutton, Precup & Singh, 1999), or predictions speciﬁed by a TD-network (Sutton & Tanner, 2005; Sutton, Rafols & Koop, 2006)). We assume that the state space is large or continuous, and function approximation must be used to compute any values of interest. In particular, we assume a space of feature vectors Φ and a mapping φ : S → Φ. We denote by φs the feature vector associated with s. An option is deﬁned as a triple o = I, π, β where I ⊆ S is the set of states in which the option can be initiated, π is the internal policy of the option and β : S → [0, 1] is a stochastic termination condition. In the option work (Sutton, Precup & Singh, 1999), each of these elements has to be explicitly speciﬁed and ﬁxed in order for an option to be well deﬁned. Here, we will instead deﬁne options implicitly, using the notion of a recognizer. A recognizer is deﬁned as a function c : S × A → [0, 1], where c(s, a) indicates to what extent the recognizer allows action a in state s. An important special case, which we treat in this paper, is that of binary recognizers. In this case, c is an indicator function, specifying a subset of actions that are allowed, or recognized, given a particular state. Note that recognizers do not specify policies; instead, they merely give restrictions on the policies that are allowed or recognized. A recognizer c together with a behavior policy b generates a target policy π, where: b(s, a)c(s, a) b(s, a)c(s, a) π(s, a) = (7) = µ(s) ∑x b(s, x)c(s, x) The denominator of this fraction, µ(s) = ∑x b(s, x)c(s, x), is the recognition probability at s, i.e., the probability that an action will be accepted at s when behavior is generated according to b. The policy π is only deﬁned at states for which µ(s) > 0. The numerator gives the probability that action a is produced by the behavior and recognized in s. Note that if the recognizer accepts all state-action pairs, i.e. c(s, a) = 1, ∀s, a, then π is the same as b. Since a recognizer and a behavior policy can specify together a target policy, we can use recognizers as a way to specify policies for options, using (7). An option can only be initiated at a state for which at least one action is recognized, so µ(s) > 0, ∀s ∈ I. Similarly, the termination condition of such an option, β, is deﬁned as β(s) = 1 if µ(s) = 0. In other words, the option must terminate if no actions are recognized at a given state. At all other states, β can be deﬁned between 0 and 1 as desired. We will focus on computing the reward model of an option o, which represents the expected total return. The expected values of different features at the end of the option can be estimated similarly. The quantity that we want to compute is Eo {R(s)} = E{r1 + r2 + . . . + rT |s0 = s, π, β} where s ∈ I, experience is generated according to the policy of the option, π, and T denotes the random variable representing the time step at which the option terminates according to β. We assume that linear function approximation is used to represent these values, i.e. Eo {R(s)} ≈ θT φs where θ is a vector of parameters. 4 Off-policy learning algorithm In this section we present an adaptation of the off-policy learning algorithm of Precup, Sutton & Dasgupta (2001) to the case of learning about options. Suppose that an option’s policy π was used to generate behavior. In this case, learning the reward model of the option is a special case of temporal-difference learning of value functions. The forward ¯ (n) view of this algorithm is as follows. Let Rt denote the truncated n-step return starting at ¯ (0) time step t and let yt denote the 0-step truncated return, Rt . By the deﬁnition of the n-step truncated return, we have: ¯ (n) ¯ (n−1) Rt = rt+1 + (1 − βt+1 )Rt+1 . This is similar to the case of value functions, but it accounts for the possibility of terminating the option at time step t + 1. The λ-return is deﬁned in the usual way: ∞ ¯ (n) ¯ Rtλ = (1 − λ) ∑ λn−1 Rt . n=1 The parameters of the linear function approximator are updated on every time step proportionally to: ¯ ¯ ∆θt = Rtλ − yt ∇θ yt (1 − β1 ) · · · (1 − βt ). In our case, however, trajectories are generated according to the behavior policy b. The main idea of the algorithm is to use importance sampling corrections in order to account for the difference in the state distribution of the two policies. Let ρt = (n) Rt , π(st ,at ) b(st ,at ) be the importance sampling ratio at time step t. The truncated n-step return, satisﬁes: (n) (n−1) Rt = ρt [rt+1 + (1 − βt+1 )Rt+1 ]. The update to the parameter vector is proportional to: ∆θt = Rtλ − yt ∇θ yt ρ0 (1 − β1 ) · · · ρt−1 (1 − βt ). The following result shows that the expected updates of the on-policy and off-policy algorithms are the same. Theorem 3 For every time step t ≥ 0 and any initial state s, ¯ Eb [∆θt |s] = Eπ [∆θt |s]. (n) (n) ¯ Proof: First we will show by induction that Eb {Rt |s} = Eπ {Rt |s}, ∀n (which implies ¯ that Eb {Rtλ |s} = Eπ (Rtλ |s}). For n = 0, the statement is trivial. Assuming that it is true for n − 1, we have (n) Eb Rt |s = a ∑b(s, a)∑Pss ρ(s, a) a = s ∑∑ a Pss b(s, a) a s = a ∑π(s, a)∑Pss a (n−1) a rss + (1 − β(s ))Eb Rt+1 |s π(s, a) a ¯ (n−1) r + (1 − β(s ))Eπ Rt+1 |s b(s, a) ss a ¯ (n−1) rss + (1 − β(s ))Eπ Rt+1 |s ¯ (n) = Eπ Rt |s . s Now we are ready to prove the theorem’s main statement. Deﬁning Ωt to be the set of all trajectory components up to state st , we have: Eb {∆θt |s} = ∑ ω∈Ωt Pb (ω|s)Eb (Rtλ − yt )∇θ yt |ω t−1 ∏ ρi (1 − βi+1 ) i=0 πi (1 − βi+1 ) i=0 bi t−1 = t−1 ∑ ∏ bi Psaiisi+1 ω∈Ωt Eb Rtλ |st − yt ∇θ yt ∏ i=0 t−1 = ∑ ∏ πi Psaiisi+1 ω∈Ωt = ∑ ω∈Ωt ¯ Eπ Rtλ |st − yt ∇θ yt (1 − β1 )...(1 − βt ) i=0 ¯ ¯ Pπ (ω|s)Eπ (Rtλ − yt )∇θ yt |ω (1 − β1 )...(1 − βt ) = Eπ ∆θt |s . Note that we are able to use st and ω interchangeably because of the Markov property. ¯ Since we have shown that Eb [∆θt |s] = Eπ [∆θt |s] for any state s, it follows that the expected updates will also be equal for any distribution of the initial state s. When learning the model of options with data generated from the behavior policy b, the starting state distribution with respect to which the learning is performed, I0 is determined by the stationary distribution of the behavior policy, as well as the initiation set of the option I. We note also that the importance sampling corrections only have to be performed for the trajectory since the initiation of the updates for the option. No corrections are required for the experience prior to this point. This should generate updates that have signiﬁcantly lower variance than in the case of learning values of policies (Precup, Sutton & Dasgupta, 2001). Because of the termination condition of the option, β, ∆θ can quickly decay to zero. To avoid this problem, we can use a restart function g : S → [0, 1], such that g(st ) speciﬁes the extent to which the updating episode is considered to start at time t. Adding restarts generates a new forward update: t ∆θt = (Rtλ − yt )∇θ yt ∑ gi ρi ...ρt−1 (1 − βi+1 )...(1 − βt ), (8) i=0 where Rtλ is the same as above. With an adaptation of the proof in Precup, Sutton & Dasgupta (2001), we can show that we get the same expected value of updates by applying this algorithm from the original starting distribution as we would by applying the algorithm without restarts from a starting distribution deﬁned by I0 and g. We can turn this forward algorithm into an incremental, backward view algorithm in the following way: • Initialize k0 = g0 , e0 = k0 ∇θ y0 • At every time step t: δt = θt+1 = kt+1 = et+1 = ρt (rt+1 + (1 − βt+1 )yt+1 ) − yt θt + αδt et ρt kt (1 − βt+1 ) + gt+1 λρt (1 − βt+1 )et + kt+1 ∇θ yt+1 Using a similar technique to that of Precup, Sutton & Dasgupta (2001) and Sutton & Barto (1998), we can prove that the forward and backward algorithm are equivalent (omitted due to lack of space). This algorithm is guaranteed to converge if the variance of the updates is ﬁnite (Precup, Sutton & Dasgupta, 2001). In the case of options, the termination condition β can be used to ensure that this is the case. 5 Learning when the behavior policy is unknown In this section, we consider the case in which the behavior policy is unknown. This case is generally problematic for importance sampling algorithms, but the use of recognizers will allow us to deﬁne importance sampling corrections, as well as a convergent algorithm. Recall that when using a recognizer, the target policy of the option is deﬁned as: c(s, a)b(s, a) π(s, a) = µ(s) and the recognition probability becomes: π(s, a) c(s, a) = b(s, a) µ(s) Of course, µ(s) depends on b. If b is unknown, instead of µ(s), we will use a maximum likelihood estimate µ : S → [0, 1]. The structure used to compute µ will have to be compatible ˆ ˆ with the feature space used to represent the reward model. We will make this more precise below. Likewise, the recognizer c(s, a) will have to be deﬁned in terms of the features used to represent the model. We will then deﬁne the importance sampling corrections as: c(s, a) ˆ ρ(s, a) = µ(s) ˆ ρ(s, a) = We consider the case in which the function approximator used to model the option is actually a state aggregator. In this case, we will deﬁne recognizers which behave consistently in each partition, i.e., c(s, a) = c(p, a), ∀s ∈ p. This means that an action is either recognized or not recognized in all states of the partition. The recognition probability µ will have one ˆ entry for every partition p of the state space. Its value will be: N(p, c = 1) µ(p) = ˆ N(p) where N(p) is the number of times partition p was visited, and N(p, c = 1) is the number of times the action taken in p was recognized. In the limit, w.p.1, µ converges to ˆ ∑s d b (s|p) ∑a c(p, a)b(s, a) where d b (s|p) is the probability of visiting state s from partiˆ ˆ tion p under the stationary distribution of b. At this limit, π(s, a) = ρ(s, a)b(s, a) will be a ˆ well-deﬁned policy (i.e., ∑a π(s, a) = 1). Using Theorem 3, off-policy updates using imˆ portance sampling corrections ρ will have the same expected value as on-policy updates ˆ ˆ using π. Note though that the learning algorithm never uses π; the only quantities needed ˆ are ρ, which are learned incrementally from data. For the case of general linear function approximation, we conjecture that a similar idea can be used, where the recognition probability is learned using logistic regression. The development of this part is left for future work. Acknowledgements The authors gratefully acknowledge the ideas and encouragement they have received in this work from Eddie Rafols, Mark Ring, Lihong Li and other members of the rlai.net group. We thank Csaba Szepesvari and the reviewers of the paper for constructive comments. This research was supported in part by iCore, NSERC, Alberta Ingenuity, and CFI. References Baird, L. C. (1995). Residual algorithms: Reinforcement learning with function approximation. In Proceedings of ICML. Precup, D., Sutton, R. S. and Dasgupta, S. (2001). Off-policy temporal-difference learning with function approximation. In Proceedings of ICML. Sutton, R.S., Precup D. and Singh, S (1999). Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artiﬁcial Intelligence, vol . 112, pp. 181–211. Sutton,, R.S. and Tanner, B. (2005). Temporal-difference networks. In Proceedings of NIPS-17. Sutton R.S., Raffols E. and Koop, A. (2006). Temporal abstraction in temporal-difference networks”. In Proceedings of NIPS-18. Tadic, V. (2001). On the convergence of temporal-difference learning with linear function approximation. In Machine learning vol. 42, pp. 241-267. Tsitsiklis, J. N., and Van Roy, B. (1997). An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control 42:674–690.

3 0.13846801 145 nips-2005-On Local Rewards and Scaling Distributed Reinforcement Learning

Author: Drew Bagnell, Andrew Y. Ng

Abstract: We consider the scaling of the number of examples necessary to achieve good performance in distributed, cooperative, multi-agent reinforcement learning, as a function of the the number of agents n. We prove a worstcase lower bound showing that algorithms that rely solely on a global reward signal to learn policies confront a fundamental limit: They require a number of real-world examples that scales roughly linearly in the number of agents. For settings of interest with a very large number of agents, this is impractical. We demonstrate, however, that there is a class of algorithms that, by taking advantage of local reward signals in large distributed Markov Decision Processes, are able to ensure good performance with a number of samples that scales as O(log n). This makes them applicable even in settings with a very large number of agents n. 1

4 0.13766021 87 nips-2005-Goal-Based Imitation as Probabilistic Inference over Graphical Models

Author: Deepak Verma, Rajesh P. Rao

Abstract: Humans are extremely adept at learning new skills by imitating the actions of others. A progression of imitative abilities has been observed in children, ranging from imitation of simple body movements to goalbased imitation based on inferring intent. In this paper, we show that the problem of goal-based imitation can be formulated as one of inferring goals and selecting actions using a learned probabilistic graphical model of the environment. We ﬁrst describe algorithms for planning actions to achieve a goal state using probabilistic inference. We then describe how planning can be used to bootstrap the learning of goal-dependent policies by utilizing feedback from the environment. The resulting graphical model is then shown to be powerful enough to allow goal-based imitation. Using a simple maze navigation task, we illustrate how an agent can infer the goals of an observed teacher and imitate the teacher even when the goals are uncertain and the demonstration is incomplete.

5 0.13599236 78 nips-2005-From Weighted Classification to Policy Search

Author: Doron Blatt, Alfred O. Hero

Abstract: This paper proposes an algorithm to convert a T -stage stochastic decision problem with a continuous state space to a sequence of supervised learning problems. The optimization problem associated with the trajectory tree and random trajectory methods of Kearns, Mansour, and Ng, 2000, is solved using the Gauss-Seidel method. The algorithm breaks a multistage reinforcement learning problem into a sequence of single-stage reinforcement learning subproblems, each of which is solved via an exact reduction to a weighted-classiﬁcation problem that can be solved using off-the-self methods. Thus the algorithm converts a reinforcement learning problem into simpler supervised learning subproblems. It is shown that the method converges in a ﬁnite number of steps to a solution that cannot be further improved by componentwise optimization. The implication of the proposed algorithm is that a plethora of classiﬁcation methods can be applied to ﬁnd policies in the reinforcement learning problem. 1

6 0.13077261 45 nips-2005-Conditional Visual Tracking in Kernel Space

7 0.12154437 153 nips-2005-Policy-Gradient Methods for Planning

8 0.086214848 186 nips-2005-TD(0) Leads to Better Policies than Approximate Value Iteration

9 0.084194265 82 nips-2005-Generalization Error Bounds for Aggregation by Mirror Descent with Averaging

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

11 0.074056193 95 nips-2005-Improved risk tail bounds for on-line algorithms

12 0.07179559 187 nips-2005-Temporal Abstraction in Temporal-difference Networks

13 0.068675645 91 nips-2005-How fast to work: Response vigor, motivation and tonic dopamine

14 0.068279445 89 nips-2005-Group and Topic Discovery from Relations and Their Attributes

15 0.065250807 50 nips-2005-Convex Neural Networks

16 0.061116088 179 nips-2005-Sparse Gaussian Processes using Pseudo-inputs

17 0.059381686 148 nips-2005-Online Discovery and Learning of Predictive State Representations

18 0.054508757 199 nips-2005-Value Function Approximation with Diffusion Wavelets and Laplacian Eigenfunctions

19 0.052072249 88 nips-2005-Gradient Flow Independent Component Analysis in Micropower VLSI

20 0.051837839 191 nips-2005-The Forgetron: A Kernel-Based Perceptron on a Fixed Budget

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.15), (1, -0.001), (2, 0.264), (3, -0.072), (4, 0.01), (5, -0.045), (6, 0.046), (7, -0.05), (8, 0.019), (9, 0.007), (10, -0.073), (11, 0.093), (12, -0.068), (13, 0.023), (14, 0.021), (15, 0.046), (16, -0.019), (17, -0.07), (18, -0.102), (19, -0.15), (20, -0.167), (21, 0.086), (22, -0.055), (23, -0.053), (24, 0.08), (25, 0.082), (26, -0.024), (27, 0.038), (28, -0.097), (29, 0.094), (30, 0.015), (31, 0.099), (32, -0.068), (33, 0.041), (34, 0.079), (35, -0.0), (36, 0.073), (37, 0.06), (38, 0.046), (39, -0.034), (40, -0.013), (41, -0.03), (42, 0.037), (43, -0.03), (44, 0.017), (45, 0.004), (46, 0.096), (47, -0.035), (48, -0.01), (49, -0.026)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95932782 72 nips-2005-Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation

Author: Jin Yu, Douglas Aberdeen, Nicol N. Schraudolph

2 0.67161733 144 nips-2005-Off-policy Learning with Options and Recognizers

Author: Doina Precup, Cosmin Paduraru, Anna Koop, Richard S. Sutton, Satinder P. Singh

3 0.52814293 78 nips-2005-From Weighted Classification to Policy Search

Author: Doron Blatt, Alfred O. Hero

4 0.5196625 145 nips-2005-On Local Rewards and Scaling Distributed Reinforcement Learning

Author: Drew Bagnell, Andrew Y. Ng

5 0.50210965 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.

6 0.49598977 186 nips-2005-TD(0) Leads to Better Policies than Approximate Value Iteration

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

8 0.44342145 87 nips-2005-Goal-Based Imitation as Probabilistic Inference over Graphical Models

9 0.41013297 153 nips-2005-Policy-Gradient Methods for Planning

10 0.3966893 187 nips-2005-Temporal Abstraction in Temporal-difference Networks

11 0.3911722 82 nips-2005-Generalization Error Bounds for Aggregation by Mirror Descent with Averaging

12 0.35134685 95 nips-2005-Improved risk tail bounds for on-line algorithms

13 0.3445293 91 nips-2005-How fast to work: Response vigor, motivation and tonic dopamine

14 0.33195406 50 nips-2005-Convex Neural Networks

15 0.30505869 60 nips-2005-Dynamic Social Network Analysis using Latent Space Models

16 0.3026171 21 nips-2005-An Alternative Infinite Mixture Of Gaussian Process Experts

17 0.29438549 20 nips-2005-Affine Structure From Sound

18 0.28996295 191 nips-2005-The Forgetron: A Kernel-Based Perceptron on a Fixed Budget

19 0.28753331 179 nips-2005-Sparse Gaussian Processes using Pseudo-inputs

20 0.28552428 68 nips-2005-Factorial Switching Kalman Filters for Condition Monitoring in Neonatal Intensive Care

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(3, 0.028), (6, 0.263), (10, 0.036), (27, 0.083), (31, 0.077), (34, 0.061), (39, 0.02), (55, 0.068), (65, 0.016), (69, 0.061), (73, 0.045), (77, 0.011), (88, 0.08), (91, 0.034)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.84384149 139 nips-2005-Non-iterative Estimation with Perturbed Gaussian Markov Processes

Author: Yunsong Huang, B. Keith Jenkins

Abstract: We develop an approach for estimation with Gaussian Markov processes that imposes a smoothness prior while allowing for discontinuities. Instead of propagating information laterally between neighboring nodes in a graph, we study the posterior distribution of the hidden nodes as a whole—how it is perturbed by invoking discontinuities, or weakening the edges, in the graph. We show that the resulting computation amounts to feed-forward fan-in operations reminiscent of V1 neurons. Moreover, using suitable matrix preconditioners, the incurred matrix inverse and determinant can be approximated, without iteration, in the same computational style. Simulation results illustrate the merits of this approach.

same-paper 2 0.80130368 72 nips-2005-Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation

Author: Jin Yu, Douglas Aberdeen, Nicol N. Schraudolph

3 0.78209734 20 nips-2005-Affine Structure From Sound

Author: Sebastian Thrun

Abstract: We consider the problem of localizing a set of microphones together with a set of external acoustic events (e.g., hand claps), emitted at unknown times and unknown locations. We propose a solution that approximates this problem under a far ﬁeld approximation deﬁned in the calculus of afﬁne geometry, and that relies on singular value decomposition (SVD) to recover the afﬁne structure of the problem. We then deﬁne low-dimensional optimization techniques for embedding the solution into Euclidean geometry, and further techniques for recovering the locations and emission times of the acoustic events. The approach is useful for the calibration of ad-hoc microphone arrays and sensor networks. 1

4 0.51999348 153 nips-2005-Policy-Gradient Methods for Planning

Author: Douglas Aberdeen

Abstract: Probabilistic temporal planning attempts to ﬁnd good policies for acting in domains with concurrent durative tasks, multiple uncertain outcomes, and limited resources. These domains are typically modelled as Markov decision problems and solved using dynamic programming methods. This paper demonstrates the application of reinforcement learning — in the form of a policy-gradient method — to these domains. Our emphasis is large domains that are infeasible for dynamic programming. Our approach is to construct simple policies, or agents, for each planning task. The result is a general probabilistic temporal planner, named the Factored Policy-Gradient Planner (FPG-Planner), which can handle hundreds of tasks, optimising for probability of success, duration, and resource use. 1

5 0.51307559 36 nips-2005-Bayesian models of human action understanding

Author: Chris Baker, Rebecca Saxe, Joshua B. Tenenbaum

Abstract: We present a Bayesian framework for explaining how people reason about and predict the actions of an intentional agent, based on observing its behavior. Action-understanding is cast as a problem of inverting a probabilistic generative model, which assumes that agents tend to act rationally in order to achieve their goals given the constraints of their environment. Working in a simple sprite-world domain, we show how this model can be used to infer the goal of an agent and predict how the agent will act in novel situations or when environmental constraints change. The model provides a qualitative account of several kinds of inferences that preverbal infants have been shown to perform, and also ﬁts quantitative predictions that adult observers make in a new experiment.

6 0.50951833 96 nips-2005-Inference with Minimal Communication: a Decision-Theoretic Variational Approach

7 0.50660235 155 nips-2005-Predicting EMG Data from M1 Neurons with Variational Bayesian Least Squares

8 0.50535893 144 nips-2005-Off-policy Learning with Options and Recognizers

9 0.50325799 200 nips-2005-Variable KD-Tree Algorithms for Spatial Pattern Search and Discovery

10 0.50116587 78 nips-2005-From Weighted Classification to Policy Search

11 0.50105119 109 nips-2005-Learning Cue-Invariant Visual Responses

12 0.50052744 45 nips-2005-Conditional Visual Tracking in Kernel Space

13 0.49839443 48 nips-2005-Context as Filtering

14 0.49813214 100 nips-2005-Interpolating between types and tokens by estimating power-law generators

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

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

17 0.49447733 30 nips-2005-Assessing Approximations for Gaussian Process Classification

18 0.49374941 173 nips-2005-Sensory Adaptation within a Bayesian Framework for Perception

19 0.49145636 199 nips-2005-Value Function Approximation with Diffusion Wavelets and Laplacian Eigenfunctions

20 0.49131703 90 nips-2005-Hot Coupling: A Particle Approach to Inference and Normalization on Pairwise Undirected Graphs