jmlr jmlr2005 jmlr2005-68 knowledge-graph by maker-knowledge-mining

68 jmlr-2005-Tree-Based Batch Mode Reinforcement Learning

Source: pdf

Author: Damien Ernst, Pierre Geurts, Louis Wehenkel

Abstract: Reinforcement learning aims to determine an optimal control policy from interaction with a system or from observations gathered from a system. In batch mode, it can be achieved by approximating the so-called Q-function based on a set of four-tuples (xt , ut , rt , xt+1 ) where xt denotes the system state at time t, ut the control action taken, rt the instantaneous reward obtained and xt+1 the successor state of the system, and by determining the control policy from this Q-function. The Q-function approximation may be obtained from the limit of a sequence of (batch mode) supervised learning problems. Within this framework we describe the use of several classical tree-based supervised learning methods (CART, Kd-tree, tree bagging) and two newly proposed ensemble algorithms, namely extremely and totally randomized trees. We study their performances on several examples and ﬁnd that the ensemble methods based on regression trees perform well in extracting relevant information about the optimal control policy from sets of four-tuples. In particular, the totally randomized trees give good results while ensuring the convergence of the sequence, whereas by relaxing the convergence constraint even better accuracy results are provided by the extremely randomized trees. Keywords: batch mode reinforcement learning, regression trees, ensemble methods, supervised learning, ﬁtted value iteration, optimal control

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Littman Abstract Reinforcement learning aims to determine an optimal control policy from interaction with a system or from observations gathered from a system. [sent-11, score-0.386]

2 Within this framework we describe the use of several classical tree-based supervised learning methods (CART, Kd-tree, tree bagging) and two newly proposed ensemble algorithms, namely extremely and totally randomized trees. [sent-14, score-0.578]

3 We study their performances on several examples and ﬁnd that the ensemble methods based on regression trees perform well in extracting relevant information about the optimal control policy from sets of four-tuples. [sent-15, score-0.667]

4 In particular, the totally randomized trees give good results while ensuring the convergence of the sequence, whereas by relaxing the convergence constraint even better accuracy results are provided by the extremely randomized trees. [sent-16, score-0.511]

5 Keywords: batch mode reinforcement learning, regression trees, ensemble methods, supervised learning, ﬁtted value iteration, optimal control 1. [sent-17, score-0.536]

6 The standard RL protocol considers a performance agent operating in discrete time, observing at time t the environment state xt , taking an action ut , and receiving back information from the environment (the next state xt+1 and the instantaneous reward rt ). [sent-22, score-0.526]

7 In on-line learning the performance agent is also the learning agent which at each time step can revise its control policy with the objective of converging as quickly as possible to an optimal control policy. [sent-24, score-0.442]

8 When the state and action spaces are ﬁnite and small enough, the Q-function can be represented in tabular form, and its approximation (in batch and in on-line mode) as well as the control policy derivation are straightforward. [sent-28, score-0.614]

9 The ﬁtted Q iteration algorithm is a batch mode reinforcement learning algorithm which yields an approximation of the Q-function corresponding to an inﬁnite horizon optimal control problem with discounted rewards, by iteratively extending the optimization horizon (Ernst et al. [sent-34, score-0.449]

10 In particular, we will see that ensembles of totally randomized trees (i. [sent-51, score-0.402]

11 , 2004), will be found to perform consistently better than totally randomized trees even though it does not strictly ensure the convergence of the sequence of Q-function approximations. [sent-55, score-0.402]

12 We formulate hereafter the batch mode reinforcement learning problem in this context and we restate some classical results stemming from Bellman’s dynamic programming approach to optimal control theory (introduced in Bellman, 1957) and from which the ﬁtted Q iteration algorithm takes its roots. [sent-64, score-0.473]

13 2 To the transition from t to t + 1 is associated an instantaneous reward signal rt = r(xt , ut , wt ) where r(x, u, w) is the reward function supposed to be bounded by some constant Br . [sent-68, score-0.39]

14 µ Let µ(·) : X → U denote a stationary control policy and J∞ denote the expected return obtained over an inﬁnite time horizon when the system is controlled using this policy (i. [sent-69, score-0.605]

15 In other words, the probability P(wt = w|xt = x, ut = u) of occurrence of wt = w given that the current state xt and the current control ut are x and u respectively, is equal to Pw (w|x, u), ∀t = 0, 1, · · · . [sent-74, score-0.388]

16 Since, except for very special conditions, it is not possible to determine exactly an optimal control policy from a ﬁnite sample of such transitions, we aim at computing an approximation of such a µ∗ from a set l F = {(xtl , utl , rtl , xt+1 ), l = 1, · · · , #F } of such four-tuples. [sent-84, score-0.451]

17 We call this problem the batch mode reinforcement learning problem because the algorithm is allowed to use a set of transitions of arbitrary size to produce its control policy in a single step. [sent-87, score-0.616]

18 An N-step optimal policy π∗ is a policy which among all possible N π a such policies maximizes JNN for any x. [sent-93, score-0.571]

19 Figure 1: Fitted Q iteration algorithm Notice that at the ﬁrst iteration the ﬁtted Q iteration algorithm is used in order to produce an approximation of the expected reward Q1 (x, u) = Ew [r(x, u, w)]. [sent-129, score-0.397]

20 4 Control Policy Derivation When the stopping conditions - whatever they are - are reached, the ﬁnal control policy, seen as an approximation of the optimal stationary closed loop control policy is derived by ˆ µ∗ (x) = arg maxQN (x, u). [sent-154, score-0.442]

21 Some of these methods will produce from the training set a model composed of one single regression tree while the others build an ensemble of regression trees. [sent-220, score-0.404]

22 The tree-based algorithms that we consider differ by the number of regression trees they build (one or an ensemble), the way they grow a tree from a training set (i. [sent-240, score-0.377]

23 1 K D -T REE In this method the regression tree is built from the training set by choosing the cut-point at the local median of the cut-direction so that the tree partitions the local training set into two subsets of the same cardinality. [sent-250, score-0.401]

24 Each tree of the ensemble is grown from a training set by ﬁrst creating a bootstrap replica (random sampling with replacement of the same number of elements) of the training set and then building an unpruned CART tree using that replica. [sent-271, score-0.425]

25 6 D ISCUSSION Table 1 classiﬁes the different tree-based algorithms considered according to two criteria: whether they build one single or an ensemble of regression trees and whether the tests computed in the trees depend on the output values of the elements of the training set. [sent-299, score-0.453]

26 This also implies that the tree structure has just to be built at the ﬁrst iteration and that in the subsequent iterations, only the values of the terminal leaves have to be refreshed. [sent-321, score-0.386]

27 Hence, in our experiments, we will build the set of totally randomized trees only at the ﬁrst iteration and then only refresh predictions at terminal nodes at subsequent iterations. [sent-325, score-0.665]

28 To measure the quality of a solution given by a RL algorithm, we can use the stationary policy it produces, compute the expected return of this stationary policy and say that the higher this expected return is, the better the RL algorithm performs. [sent-363, score-0.512]

29 The score of a policy assesses the quality of a policy through its expected return. [sent-373, score-0.626]

30 In the “Bicycle Balancing” control problem, we also assess the quality of a policy through its ability to avoid crashing the bicycle during a certain period of time. [sent-374, score-0.753]

31 Note that during these 1000 episodes the reward r(xt , ut , wt ) = 1 (corresponding to an arrival of the car at the top of the hill with a speed comprised in [−3, 3]) has been observed only 18 times. [sent-723, score-0.531]

32 As the action space is binary, we ˆ ˆ again model the functions QN (x, −4) and QN (x, 4) by two ensembles of 50 trees each, and nmin = 2. [sent-826, score-0.395]

33 In this section, the same types of approximation architectures are also considered and, for each type of approximation architecture, the policy µ∗ has been computed for different grid resolutions ˆ 50 (a 10 × 10 grid, a 11 × 11 grid, · · · , a 50 × 50 grid). [sent-963, score-0.384]

34 If we compare the score curves corresponding to piecewise-linear grids as approximation architectures, we observe also that the highest score produced by ﬁtted Q iteration (over the different grids), is higher than the highest score produced by Q-learning. [sent-1098, score-0.494]

35 Trees Nb of irrelevant variables Kd-Tree (Best nmin ) kNN (k = 2) Figure 17: Score of µ∗ when four-tuples are gathered during 1000 episodes and some variables that do not ˆ 50 contain any information about the position and the speed of the car are added to the state vector. [sent-1120, score-0.471]

36 On Figure 17, we have drawn the evolution of the score when using four-tuples gathered during 1000 episodes and adding progressively irrelevant variables to the state-vector. [sent-1139, score-0.391]

37 Among them, Tree Bagging and Extra-Trees which are based on the averaging of several trees are almost totally immune, since even with 10 irrelevant variables (leading to the a 12-dimensional input space) their score decrease is almost insigniﬁcant. [sent-1150, score-0.434]

38 6 I NFLUENCE OF THE N UMBER OF R EGRESSION T REES IN AN E NSEMBLE In this paper, we have chosen to build ensembles of regression trees composed of 50 trees (M = 50, Section 4. [sent-1154, score-0.378]

39 Note that since the CPU times required to compute the solution grow linearly with the number of trees built, computational requirements of the regression tree based ensemble methods could be adjusted by choosing a value of M. [sent-1158, score-0.425]

40 20000 30000 p Nb of four-tuples 40000 ˆ 50 (b) Inﬂuence of #F on the score of the policy µ∗ Figure 19: Car on the Hill with continuous action space. [sent-1192, score-0.502]

41 We see that the control policy obtained is not far the absolute value of the control signal |ˆ 50 µ from a “bang-bang” policy. [sent-1196, score-0.442]

42 The two upper curves correspond to the score of the policy µ∗ obtained when considering a ˆ 50 discrete action space U = {−4, 4}. [sent-1206, score-0.502]

43 Indeed, it just requires building one single tree structure at the ﬁrst iteration and refresh its terminal nodes in the aftermath. [sent-1292, score-0.393]

44 • Concerning Pruned CART Tree, it may be noticed that tree pruning by ten-fold cross validation requires to build in total eleven trees which explains why the CPU times for building 50 trees with Tree Bagging is about ﬁve times greater than the CPU times required for Pruned CART Tree. [sent-1293, score-0.499]

45 534 T REE -BASED BATCH M ODE R EINFORCEMENT L EARNING • The MB task for Totally Randomized Trees is much faster than the MB task for Extra-Trees, mainly because the totally randomized tree structures are built only at the ﬁrst iteration. [sent-1297, score-0.465]

46 Note that, when totally randomized trees are built at the ﬁrst iteration, branch development is not stopped when the elements of the local training set have the same value, because it can not be assumed that these elements would still have the same value in subsequent iterations. [sent-1298, score-0.429]

47 This also implies that totally randomized trees are more complex than trees built by Extra-Trees and explains why the TSB task with Totally Randomized Trees is more time consuming. [sent-1299, score-0.562]

48 2 S IMULATION R ESULTS First, we consider the set of four-tuples gathered when using the ε-greedy policy to control the system. [sent-1335, score-0.386]

49 The ε-greedy policy chooses with probability 1 − ε the control action ut at random in the set {u ∈ U|u = ˆ arg maxu∈U Q(xt , u)}) and with probability ε at random in U. [sent-1344, score-0.543]

50 We can also observe from this table that the scores obtained while using the set of four-tuples corresponding to the totally random policy are much worse than those obtained when using an ε-greedy policy. [sent-1374, score-0.416]

51 This is certainly because the use of a totally random policy leads to very little 537 E RNST, G EURTS AND W EHENKEL information along the optimal trajectories starting from elements of X i . [sent-1375, score-0.535]

52 5 The Bicycle We consider two control problems related to a bicycle which moves at constant speed on a horizontal plane (Figure 23). [sent-1379, score-0.47]

53 For the second problem, he has not only to learn how to balance the bicycle but also how to drive it to a speciﬁc goal. [sent-1381, score-0.403]

54 Four are related to the bicycle itself and three to the position of the bicycle on the plane. [sent-1386, score-0.754]

55 The state variables related to the ˙ bicycle are ω (the angle from vertical to the bicycle), ω, θ (the angle the handlebars are displaced ˙ from normal) and θ. [sent-1387, score-0.49]

56 If |ω| becomes larger than 12 degrees, then the bicycle is supposed to have fallen down and a terminal state is reached. [sent-1388, score-0.546]

57 The three state variables related to the position of the bicycle on the plane are the coordinates (xb , yb ) of the contact point of the back tire with the horizontal plane and the angle ψ formed by the bicycle frame and the x-axis. [sent-1389, score-0.922]

58 As is usually the case when dealing with these bicycle control problems, we suppose that the state variables xb and yb cannot be observed. [sent-1396, score-0.6]

59 The reward function for the “Bicycle Balancing” control problem (Eqn (56), page 553) is such that zero rewards are always observed, except when the bicycle has fallen down, in which case the reward is equal to -1. [sent-1398, score-0.798]

60 For the “Bicycle Balancing and Riding” control problem, a reward of −1 is also observed when the bicycle has fallen down. [sent-1399, score-0.629]

61 However, this time, non-zero rewards are also observed when the bicycle is riding (Eqn (57), page 553). [sent-1400, score-0.489]

62 Indeed, the reward rt when the bicycle is supposed not to have fallen down, is now equal to creward (dangle (ψt ) − dangle (ψt+1 )) with 22. [sent-1401, score-0.68]

63 Several other papers treat the problems of balancing and/or balancing and riding a bicycle (e. [sent-1402, score-0.608]

64 In particular, he could refer to Randløv and Alstrøm (1998) to get an idea of the performances of SARSA(λ), an on-line algorithm, on these bicycle control problems and to Lagoudakis and Parr (2003b) to see how the Least-Square Policy Iteration (LSPI), a batch mode RL algorithm, performs. [sent-1406, score-0.666]

65 = (xgoal , ygoal )) (a) (b) Figure 23: Figure (a) represents the bicycle seen from behind. [sent-1415, score-0.406]

66 θ is the angle the handlebars are displaced from normal, ψ the angle formed by the bicycle frame and the xaxis and ψgoal the angle between the bicycle frame and the line joining the back - wheel ground contact and the center of the goal. [sent-1423, score-0.947]

67 Positive rewards are therefore observed when the bicycle frame gets closer to the position ψ = 0 and negative rewards otherwise. [sent-1428, score-0.496]

68 With such a choice for the reward function, the optimal policy µ∗ tends to control the bicycle so that it moves to the right with its frame parallel to the x-axis. [sent-1429, score-0.897]

69 Such an optimal policy or a good approximate µ∗ of it can then be used to drive the ˆ bicycle to a speciﬁc goal. [sent-1430, score-0.659]

70 If ψgoalt represents the angle between the bicycle frame and a line joining the point (xb , yb ) to the center of the goal (xgoal , ygoal ) (Figure 23b), this is achieved by selecting at ˙ ˙ ˙ ˙ time t the action µ∗ (ωt , ωt , θt , θt , ψgoalt ), rather than µ∗ (ωt , ωt , θt , θt , ψt ). [sent-1431, score-0.667]

71 In this way, we proceed ˆ ˆ as if the line joining (xb , yb ) to (xgoal , ygoal ) were the x-axis when selecting control actions, which makes the bicycle moving towards the goal. [sent-1432, score-0.55]

72 All episodes used to generate the four-tuples start from a state selected at random in ˙ ˙ ˙ ˙ {(ω, ω, θ, θ, xb , yb , ψ) ∈ R7 |ψ ∈ [−π, π] and ω = ω = θ = θ = xb = yb = 0}, and end when a terminal state is reached, i. [sent-1438, score-0.545]

73 when the bicycle is supposed to have fallen down. [sent-1440, score-0.406]

74 The policy considered during the four-tuples generation phase is a policy that selects at each instant an action at random in U. [sent-1441, score-0.644]

75 If no terminal state has been reached before t = 50, 000, that is if the policy was able to avoid crashing the bicycle during 500 seconds (the discretization time step is 0. [sent-1454, score-0.773]

76 Figure 24b gives an idea of the trajectories of the bicycle on the horizontal plane when starting from the different elements of X i and being controlled by µ∗ . [sent-1479, score-0.496]

77 ˆ 300 To assess the inﬂuence of the number of four-tuples on the quality of the policy computed, we have drawn on Figure 24d the number of successful trajectories when different number of episodes are used to generate F . [sent-1480, score-0.616]

78 As mentioned earlier, with the reward function chosen, the policy computed by our algorithm should be able to drive the bicycle to the right, parallel to the x-axis, provided that the policy is a good approximation of the optimal policy. [sent-1495, score-1.045]

79 To assess this ability, we have simulated, for each x0 ∈ X i , the system with the policy µ∗ and have represented on Figure 25b the different trajectories of the ˆ 300 back tire. [sent-1496, score-0.402]

80 As one may see, the policy tends indeed to drive the bicycle to the right, parallel to the x-axis. [sent-1497, score-0.659]

81 Figure (b) sketches trajectories of the bicycle on the xb − yb plane when controlled by µ∗ . [sent-1513, score-0.587]

82 ˆ 300 Figure (c) represents the number of times (out of 90 trials) the policy µ∗ (Extra-Trees, 1000 ˆN episodes) manages to balance the bicycle during 50,000 time steps, i. [sent-1515, score-0.633]

83 It is clear that these good performances in terms of the policy ability to drive the bicycle to the goal depend on the choice of the reward function. [sent-1525, score-0.851]

84 This can be explained by the fact that, in this case, the large positive rewards obtained for moving the frame of the bicycle parallel to the x-axis lead to a control policy that modiﬁes too rapidly the bicycle riding direction which tends to destabilize it. [sent-1528, score-1.256]

85 On this ﬁgure, we may also clearly observe that after leaving the goal, the control policies tend to drive again the bicycle to it. [sent-1534, score-0.555]

86 1 manages at each loop to bring the bicycle back to the goal while it is not the case with the policy corresponding to creward = 0. [sent-1536, score-0.706]

87 This is due to the fact that a smaller value of γ tends to increase the importance of short-term rewards over long-term ones, which favors actions that turn rapidly the bicycle frame, even if they may eventually lead to a fall of the bicycle. [sent-1542, score-0.416]

88 Rather than relying only on the score to assess the performances of a policy, let us now associate to a policy a value that depends on its ability to drive the bicycle to the goal within a certain time ˙ ˙ interval, when (ω, ω, θ, θ, ψgoal ) is the state signal considered. [sent-1543, score-0.901]

89 Figure (b) sketches trajectories when µ∗ (Extra-Trees, ˆN ˆ 300 1000 episodes) controls the bicycle (trajectories drawn from t = 0 till t = 50, 000). [sent-1573, score-0.496]

90 Figure (c) represents trajectories when µ∗ (Extra-Trees, 1000 episodes) controls the bicycle with ˆ 300 ˙ ˙ (ωt , ωt , θt , θt , ψgoalt ) used as input signal for the policy (trajectories drawn from t = 0 till t = 50, 000). [sent-1574, score-0.752]

91 Figure (d) represents the inﬂuence on creward on the trajectories (ˆ ∗ , Extra-Trees, µ300 1000 episodes and trajectories drawn from t = 0 till t = 100, 000). [sent-1575, score-0.495]

92 Figure (e) lists the number of times the policy µ∗ manages to bring the bicycle to the goal in less than 50, 000 time steps (highˆN est possible value for “Number of successful trajectories” is 90). [sent-1576, score-0.663]

93 Whatever the set of four-tuples used, the top score has always been reached by a method building an ensemble of regression trees, and furthermore, the larger the state space, the better these regression tree ensemble methods behave compared to methods building only one single tree. [sent-1584, score-0.568]

94 Among the single tree methods, Pruned CART Tree, which adapts the tree structure to the output variable, offers typically the same performances as Kd-Tree, except in the case of irrelevant variables where it is signiﬁcantly more robust. [sent-1590, score-0.427]

95 Conclusions and Future Work In this paper, we have considered a batch mode approach to reinforcement learning, which consists of reformulating the reinforcement learaning problem as a sequence of standard supervised learning problems. [sent-1614, score-0.453]

96 They are also very grateful to Bruno Scherrer for reviewing an earlier version of this work, to Mania Pavella for her helpful comments and to Michail Lagoudakis for pointing out relevant information about the bicycle control problems. [sent-1638, score-0.47]

97 When |ωt+1 | > 180 π, the bicycle is supposed to have fallen down and a terminal state is reached. [sent-1753, score-0.546]

98 12 180 π (56) The reward function for “Bicycle Balancing and Riding” control problem is: r(xt , ut , wt ) = −1 creward (dangle (ψt ) − dangle (ψt+1 )) if |ωt+1 | > otherwise 12 180 π (57) where creward = 0. [sent-1760, score-0.51]

99 Remark: The bicycle dynamics is based on the one found in Randløv and Alstrøm (1998) and in their corresponding simulator available at http://www. [sent-1764, score-0.432]

100 Learning to drive a bicycle using reinforcement learning and shaping. [sent-1962, score-0.536]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('bicycle', 0.377), ('qn', 0.336), ('policy', 0.256), ('tted', 0.206), ('episodes', 0.184), ('bagging', 0.18), ('tree', 0.169), ('totally', 0.16), ('ree', 0.155), ('pruned', 0.14), ('reinforcement', 0.133), ('trees', 0.133), ('action', 0.132), ('ehenkel', 0.131), ('eurts', 0.131), ('rnst', 0.131), ('nmin', 0.13), ('reward', 0.13), ('einforcement', 0.126), ('trajectories', 0.119), ('score', 0.114), ('randomized', 0.109), ('ode', 0.105), ('bellman', 0.105), ('terminal', 0.101), ('batch', 0.094), ('xt', 0.094), ('control', 0.093), ('iteration', 0.089), ('cart', 0.088), ('ensemble', 0.087), ('balancing', 0.079), ('eqn', 0.077), ('xtl', 0.077), ('grid', 0.076), ('creward', 0.073), ('riding', 0.073), ('utl', 0.073), ('knn', 0.069), ('grids', 0.063), ('ernst', 0.063), ('hill', 0.063), ('ut', 0.062), ('performances', 0.062), ('policies', 0.059), ('geurts', 0.058), ('dynamics', 0.055), ('car', 0.054), ('supervised', 0.053), ('architectures', 0.052), ('yb', 0.051), ('earning', 0.05), ('ormoneit', 0.049), ('residual', 0.045), ('trajectory', 0.043), ('dangle', 0.041), ('frame', 0.041), ('acrobot', 0.041), ('mode', 0.04), ('architecture', 0.04), ('xb', 0.04), ('build', 0.039), ('rewards', 0.039), ('state', 0.039), ('fitted', 0.039), ('lagoudakis', 0.039), ('maxqn', 0.039), ('wt', 0.038), ('composed', 0.037), ('angle', 0.037), ('gathered', 0.037), ('cpu', 0.037), ('regression', 0.036), ('kt', 0.034), ('goalt', 0.034), ('refresh', 0.034), ('tsb', 0.034), ('successful', 0.03), ('nb', 0.03), ('rt', 0.03), ('evolution', 0.029), ('fallen', 0.029), ('ol', 0.029), ('rtl', 0.029), ('xgoal', 0.029), ('ygoal', 0.029), ('sen', 0.029), ('irrelevant', 0.027), ('gordon', 0.027), ('assess', 0.027), ('built', 0.027), ('drive', 0.026), ('rl', 0.026), ('pruning', 0.025), ('mb', 0.025), ('tests', 0.025), ('node', 0.024), ('alstr', 0.024), ('boyan', 0.024), ('hereafter', 0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999946 68 jmlr-2005-Tree-Based Batch Mode Reinforcement Learning

Author: Damien Ernst, Pierre Geurts, Louis Wehenkel

2 0.15572824 61 jmlr-2005-Prioritization Methods for Accelerating MDP Solvers

Author: David Wingate, Kevin D. Seppi

Abstract: The performance of value and policy iteration can be dramatically improved by eliminating redundant or useless backups, and by backing up states in the right order. We study several methods designed to accelerate these iterative solvers, including prioritization, partitioning, and variable reordering. We generate a family of algorithms by combining several of the methods discussed, and present extensive empirical evidence demonstrating that performance can improve by several orders of magnitude for many problems, while preserving accuracy and convergence guarantees. Keywords: Markov Decision Processes, value iteration, policy iteration, prioritized sweeping, dynamic programming

3 0.074027039 12 jmlr-2005-An MDP-Based Recommender System

Author: Guy Shani, David Heckerman, Ronen I. Brafman

Abstract: Typical recommender systems adopt a static view of the recommendation process and treat it as a prediction problem. We argue that it is more appropriate to view the problem of generating recommendations as a sequential optimization problem and, consequently, that Markov decision processes (MDPs) provide a more appropriate model for recommender systems. MDPs introduce two beneﬁts: they take into account the long-term effects of each recommendation and the expected value of each recommendation. To succeed in practice, an MDP-based recommender system must employ a strong initial model, must be solvable quickly, and should not consume too much memory. In this paper, we describe our particular MDP model, its initialization using a predictive model, the solution and update algorithm, and its actual performance on a commercial site. We also describe the particular predictive model we used which outperforms previous models. Our system is one of a small number of commercially deployed recommender systems. As far as we know, it is the ﬁrst to report experimental analysis conducted on a real commercial site. These results validate the commercial value of recommender systems, and in particular, of our MDP-based approach. Keywords: recommender systems, Markov decision processes, learning, commercial applications

4 0.070932433 54 jmlr-2005-Managing Diversity in Regression Ensembles

Author: Gavin Brown, Jeremy L. Wyatt, Peter Tiňo

Abstract: Ensembles are a widely used and effective technique in machine learning—their success is commonly attributed to the degree of disagreement, or ‘diversity’, within the ensemble. For ensembles where the individual estimators output crisp class labels, this ‘diversity’ is not well understood and remains an open research issue. For ensembles of regression estimators, the diversity can be exactly formulated in terms of the covariance between individual estimator outputs, and the optimum level is expressed in terms of a bias-variance-covariance trade-off. Despite this, most approaches to learning ensembles use heuristics to encourage the right degree of diversity. In this work we show how to explicitly control diversity through the error function. The ﬁrst contribution of this paper is to show that by taking the combination mechanism for the ensemble into account we can derive an error function for each individual that balances ensemble diversity with individual accuracy. We show the relationship between this error function and an existing algorithm called negative correlation learning, which uses a heuristic penalty term added to the mean squared error function. It is demonstrated that these methods control the bias-variance-covariance trade-off systematically, and can be utilised with any estimator capable of minimising a quadratic error function, for example MLPs, or RBF networks. As a second contribution, we derive a strict upper bound on the coefﬁcient of the penalty term, which holds for any estimator that can be cast in a generalised linear regression framework, with mild assumptions on the basis functions. Finally we present the results of an empirical study, showing signiﬁcant improvements over simple ensemble learning, and ﬁnding that this technique is competitive with a variety of methods, including boosting, bagging, mixtures of experts, and Gaussian processes, on a number of tasks. Keywords: ensemble, diversity, regression estimators, neural networks, hessia

5 0.058984268 31 jmlr-2005-Estimation of Non-Normalized Statistical Models by Score Matching

Author: Aapo Hyvärinen

Abstract: One often wants to estimate statistical models where the probability density function is known only up to a multiplicative normalization constant. Typically, one then has to resort to Markov Chain Monte Carlo methods, or approximations of the normalization constant. Here, we propose that such models can be estimated by minimizing the expected squared distance between the gradient of the log-density given by the model and the gradient of the log-density of the observed data. While the estimation of the gradient of log-density function is, in principle, a very diﬃcult non-parametric problem, we prove a surprising result that gives a simple formula for this objective function. The density function of the observed data does not appear in this formula, which simpliﬁes to a sample average of a sum of some derivatives of the log-density given by the model. The validity of the method is demonstrated on multivariate Gaussian and independent component analysis models, and by estimating an overcomplete ﬁlter set for natural image data. Keywords: statistical estimation, non-normalized densities, pseudo-likelihood, Markov chain Monte Carlo, contrastive divergence

6 0.057317562 67 jmlr-2005-Stability of Randomized Learning Algorithms

7 0.05325963 51 jmlr-2005-Local Propagation in Conditional Gaussian Bayesian Networks

8 0.051239874 52 jmlr-2005-Loopy Belief Propagation: Convergence and Effects of Message Errors

9 0.045362704 17 jmlr-2005-Change Point Problems in Linear Dynamical Systems

10 0.045331836 35 jmlr-2005-Frames, Reproducing Kernels, Regularization and Learning

11 0.043950155 42 jmlr-2005-Large Margin Methods for Structured and Interdependent Output Variables

12 0.042734493 55 jmlr-2005-Matrix Exponentiated Gradient Updates for On-line Learning and Bregman Projection

13 0.042014353 33 jmlr-2005-Fast Kernel Classifiers with Online and Active Learning

14 0.040833309 63 jmlr-2005-Quasi-Geodesic Neural Learning Algorithms Over the Orthogonal Group: A Tutorial

15 0.040132567 5 jmlr-2005-A Generalization Error for Q-Learning

16 0.037087154 70 jmlr-2005-Universal Algorithms for Learning Theory Part I : Piecewise Constant Functions

17 0.031944238 66 jmlr-2005-Smooth ε-Insensitive Regression by Loss Symmetrization

18 0.031001909 32 jmlr-2005-Expectation Consistent Approximate Inference

19 0.030934948 27 jmlr-2005-Dimension Reduction in Text Classification with Support Vector Machines

20 0.029231265 53 jmlr-2005-Machine Learning Methods for Predicting Failures in Hard Drives: A Multiple-Instance Application

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.186), (1, 0.068), (2, 0.116), (3, -0.22), (4, -0.108), (5, 0.189), (6, 0.236), (7, -0.049), (8, 0.381), (9, -0.14), (10, -0.161), (11, -0.03), (12, 0.029), (13, 0.089), (14, 0.056), (15, 0.033), (16, -0.075), (17, 0.069), (18, -0.16), (19, 0.092), (20, -0.064), (21, -0.095), (22, -0.075), (23, 0.032), (24, -0.021), (25, 0.012), (26, 0.042), (27, -0.007), (28, 0.003), (29, 0.015), (30, -0.066), (31, -0.043), (32, -0.097), (33, -0.012), (34, 0.085), (35, -0.118), (36, 0.102), (37, 0.192), (38, 0.026), (39, -0.082), (40, -0.106), (41, 0.174), (42, 0.072), (43, 0.084), (44, -0.032), (45, -0.044), (46, -0.052), (47, -0.0), (48, -0.033), (49, -0.026)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97151941 68 jmlr-2005-Tree-Based Batch Mode Reinforcement Learning

Author: Damien Ernst, Pierre Geurts, Louis Wehenkel

2 0.62246615 61 jmlr-2005-Prioritization Methods for Accelerating MDP Solvers

Author: David Wingate, Kevin D. Seppi

3 0.30312935 54 jmlr-2005-Managing Diversity in Regression Ensembles

Author: Gavin Brown, Jeremy L. Wyatt, Peter Tiňo

4 0.28541097 12 jmlr-2005-An MDP-Based Recommender System

Author: Guy Shani, David Heckerman, Ronen I. Brafman

5 0.25096393 51 jmlr-2005-Local Propagation in Conditional Gaussian Bayesian Networks

Author: Robert G. Cowell

Abstract: This paper describes a scheme for local computation in conditional Gaussian Bayesian networks that combines the approach of Lauritzen and Jensen (2001) with some elements of Shachter and Kenley (1989). Message passing takes place on an elimination tree structure rather than the more compact (and usual) junction tree of cliques. This yields a local computation scheme in which all calculations involving the continuous variables are performed by manipulating univariate regressions, and hence matrix operations are avoided. Keywords: Bayesian networks, conditional Gaussian distributions, propagation algorithm, elimination tree

6 0.2448701 67 jmlr-2005-Stability of Randomized Learning Algorithms

7 0.23833604 31 jmlr-2005-Estimation of Non-Normalized Statistical Models by Score Matching

8 0.21286961 35 jmlr-2005-Frames, Reproducing Kernels, Regularization and Learning

9 0.20334239 52 jmlr-2005-Loopy Belief Propagation: Convergence and Effects of Message Errors

10 0.19636188 42 jmlr-2005-Large Margin Methods for Structured and Interdependent Output Variables

11 0.18413717 63 jmlr-2005-Quasi-Geodesic Neural Learning Algorithms Over the Orthogonal Group: A Tutorial

12 0.17239423 33 jmlr-2005-Fast Kernel Classifiers with Online and Active Learning

13 0.17029229 17 jmlr-2005-Change Point Problems in Linear Dynamical Systems

14 0.13364241 70 jmlr-2005-Universal Algorithms for Learning Theory Part I : Piecewise Constant Functions

15 0.13154607 55 jmlr-2005-Matrix Exponentiated Gradient Updates for On-line Learning and Bregman Projection

16 0.12764493 58 jmlr-2005-Multiclass Classification with Multi-Prototype Support Vector Machines

17 0.11741771 5 jmlr-2005-A Generalization Error for Q-Learning

18 0.11608315 66 jmlr-2005-Smooth ε-Insensitive Regression by Loss Symmetrization

19 0.10779612 44 jmlr-2005-Learning Module Networks

20 0.10765246 72 jmlr-2005-What's Strange About Recent Events (WSARE): An Algorithm for the Early Detection of Disease Outbreaks

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.021), (17, 0.029), (19, 0.026), (36, 0.014), (37, 0.088), (42, 0.02), (43, 0.044), (47, 0.016), (52, 0.073), (59, 0.018), (68, 0.44), (70, 0.04), (88, 0.059), (90, 0.016), (94, 0.021)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.75379521 68 jmlr-2005-Tree-Based Batch Mode Reinforcement Learning

Author: Damien Ernst, Pierre Geurts, Louis Wehenkel

2 0.29261163 7 jmlr-2005-A Unifying View of Sparse Approximate Gaussian Process Regression

Author: Joaquin Quiñonero-Candela, Carl Edward Rasmussen

Abstract: We provide a new unifying view, including all existing proper probabilistic sparse approximations for Gaussian process regression. Our approach relies on expressing the effective prior which the methods are using. This allows new insights to be gained, and highlights the relationship between existing methods. It also allows for a clear theoretically justiﬁed ranking of the closeness of the known approximations to the corresponding full GPs. Finally we point directly to designs of new better sparse approximations, combining the best of the existing strategies, within attractive computational constraints. Keywords: Gaussian process, probabilistic regression, sparse approximation, Bayesian committee machine Regression models based on Gaussian processes (GPs) are simple to implement, ﬂexible, fully probabilistic models, and thus a powerful tool in many areas of application. Their main limitation is that memory requirements and computational demands grow as the square and cube respectively, of the number of training cases n, effectively limiting a direct implementation to problems with at most a few thousand cases. To overcome the computational limitations numerous authors have recently suggested a wealth of sparse approximations. Common to all these approximation schemes is that only a subset of the latent variables are treated exactly, and the remaining variables are given some approximate, but computationally cheaper treatment. However, the published algorithms have widely different motivations, emphasis and exposition, so it is difﬁcult to get an overview (see Rasmussen and Williams, 2006, chapter 8) of how they relate to each other, and which can be expected to give rise to the best algorithms. In this paper we provide a unifying view of sparse approximations for GP regression. Our approach is simple, but powerful: for each algorithm we analyze the posterior, and compute the effective prior which it is using. Thus, we reinterpret the algorithms as “exact inference with an approximated prior”, rather than the existing (ubiquitous) interpretation “approximate inference with the exact prior”. This approach has the advantage of directly expressing the approximations in terms of prior assumptions about the function, which makes the consequences of the approximations much easier to understand. While our view of the approximations is not the only one possible, it has the advantage of putting all existing probabilistic sparse approximations under one umbrella, thus enabling direct comparison and revealing the relation between them. In Section 1 we brieﬂy introduce GP models for regression. In Section 2 we present our unifying framework and write out the key equations in preparation for the unifying analysis of sparse c 2005 Joaquin Qui˜ onero-Candela and Carl Edward Rasmussen. n ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN algorithms in Sections 4-7. The relation of transduction and augmentation to our sparse framework is covered in Section 8. All our approximations are written in terms of a new set of inducing variables. The choice of these variables is itself a challenging problem, and is discussed in Section 9. We comment on a few special approximations outside our general scheme in Section 10 and conclusions are drawn at the end. 1. Gaussian Processes for Regression Probabilistic regression is usually formulated as follows: given a training set D = {(xi , yi ), i = 1, . . . , n} of n pairs of (vectorial) inputs xi and noisy (real, scalar) outputs yi , compute the predictive distribution of the function values f∗ (or noisy y∗ ) at test locations x∗ . In the simplest case (which we deal with here) we assume that the noise is additive, independent and Gaussian, such that the relationship between the (latent) function f (x) and the observed noisy targets y are given by yi = f (xi ) + εi , where εi ∼ N (0, σ2 ) , noise (1) where σ2 is the variance of the noise. noise Deﬁnition 1 A Gaussian process (GP) is a collection of random variables, any ﬁnite number of which have consistent1 joint Gaussian distributions. Gaussian process (GP) regression is a Bayesian approach which assumes a GP prior2 over functions, i.e. assumes a priori that function values behave according to p(f|x1 , x2 , . . . , xn ) = N (0, K) , (2) where f = [ f1 , f2 , . . . , fn ] is a vector of latent function values, fi = f (xi ) and K is a covariance matrix, whose entries are given by the covariance function, Ki j = k(xi , x j ). Note that the GP treats the latent function values fi as random variables, indexed by the corresponding input. In the following, for simplicity we will always neglect the explicit conditioning on the inputs; the GP model and all expressions are always conditional on the corresponding inputs. The GP model is concerned only with the conditional of the outputs given the inputs; we do not model anything about the inputs themselves. Remark 2 Note, that to adhere to a strict Bayesian formalism, the GP covariance function,3 which deﬁnes the prior, should not depend on the data (although it can depend on additional parameters). As we will see in later sections, some approximations are strictly equivalent to GPs, while others are not. That is, the implied prior may still be multivariate Gaussian, but the covariance function may be different for training and test cases. Deﬁnition 3 A Gaussian process is called degenerate iff the covariance function has a ﬁnite number of non-zero eigenvalues. 1. By consistency is meant simply that the random variables obey the usual rules of marginalization, etc. 2. For notational simplicity we exclusively use zero-mean priors. 3. The covariance function itself shouldn’t depend on the data, though its value at a speciﬁc pair of inputs of course will. 1940 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION Degenerate GPs (such as e.g. with polynomial covariance function) correspond to ﬁnite linear (-in-the-parameters) models, whereas non-degenerate GPs (such as e.g. with squared exponential or RBF covariance function) do not. The prior for a ﬁnite m dimensional linear model only considers a universe of at most m linearly independent functions; this may often be too restrictive when n m. Note however, that non-degeneracy on its own doesn’t guarantee the existence of the “right kind” of ﬂexibility for a given particular modelling task. For a more detailed background on GP models, see for example that of Rasmussen and Williams (2006). Inference in the GP model is simple: we put a joint GP prior on training and test latent values, f and f∗ 4 , and combine it with the likelihood5 p(y|f) using Bayes rule, to obtain the joint posterior p(f, f∗ )p(y|f) . p(y) p(f, f∗ |y) = (3) The ﬁnal step needed to produce the desired posterior predictive distribution is to marginalize out the unwanted training set latent variables: p(f∗ |y) = Z 1 p(y) p(f, f∗ |y)df = Z p(y|f) p(f, f∗ ) df , (4) or in words: the predictive distribution is the marginal of the renormalized joint prior times the likelihood. The joint GP prior and the independent likelihood are both Gaussian p(f, f∗ ) = N 0, Kf,f K∗,f Kf,∗ K∗,∗ , and p(y|f) = N (f, σ2 I) , noise (5) where K is subscript by the variables between which the covariance is computed (and we use the asterisk ∗ as shorthand for f∗ ) and I is the identity matrix. Since both factors in the integral are Gaussian, the integral can be evaluated in closed form to give the Gaussian predictive distribution p(f∗ |y) = N K∗,f (Kf,f + σ2 I)−1 y, K∗,∗ − K∗,f (Kf,f + σ2 I)−1 Kf,∗ , noise noise (6) see the relevant Gaussian identity in appendix A. The problem with the above expression is that it requires inversion of a matrix of size n × n which requires O (n3 ) operations, where n is the number of training cases. Thus, the simple exact implementation can handle problems with at most a few thousand training cases. 2. A New Unifying View We now seek to modify the joint prior p(f∗ , f) from (5) in ways which will reduce the computational requirements from (6). Let us ﬁrst rewrite that prior by introducing an additional set of m latent variables u = [u1 , . . . , um ] , which we call the inducing variables. These latent variables are values of the Gaussian process (as also f and f∗ ), corresponding to a set of input locations Xu , which we call the inducing inputs. Whereas the additional latent variables u are always marginalized out in the predictive distribution, the choice of inducing inputs does leave an imprint on the ﬁnal solution. 4. We will mostly consider a vector of test cases f∗ (rather than a single f∗ ). 5. You may have been expecting the likelihood written as p(y|f∗ , f) but since the likelihood is conditionally independent of everything else given f, this makes no difference. 1941 ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN The inducing variables will turn out to be generalizations of variables which other authors have referred to variously as “support points”, “active set” or “pseudo-inputs”. Particular sparse algorithms choose the inducing variables in various different ways; some algorithms chose the inducing inputs to be a subset of the training set, others not, as we will discuss in Section 9. For now consider any arbitrary inducing variables. Due to the consistency of Gaussian processes, we know that we can recover p(f∗ , f) by simply integrating (marginalizing) out u from the joint GP prior p(f∗ , f, u) p(f∗ , f) = Z p(f∗ , f, u) du = Z p(f∗ , f|u) p(u) du, where p(u) = N (0, Ku,u ) . (7) This is an exact expression. Now, we introduce the fundamental approximation which gives rise to almost all sparse approximations. We approximate the joint prior by assuming that f∗ and f are conditionally independent given u, see Figure 1, such that p(f∗ , f) q(f∗ , f) = Z q(f∗ |u) q(f|u) p(u) du . (8) The name inducing variable is motivated by the fact that f and f∗ can only communicate though u, and u therefore induces the dependencies between training and test cases. As we shall detail in the following sections, the different computationally efﬁcient algorithms proposed in the literature correspond to different additional assumptions about the two approximate inducing conditionals q(f|u), q(f∗ |u) of the integral in (8). It will be useful for future reference to specify here the exact expressions for the two conditionals training conditional: test conditional: −1 p(f|u) = N (Kf,u Ku,u u, Kf,f − Qf,f ) , −1 p(f∗ |u) = N (K∗,u Ku,u u, K∗,∗ − Q∗,∗ ) , (9a) (9b) −1 where we have introduced the shorthand notation6 Qa,b Ka,u Ku,u Ku,b . We can readily identify the expressions in (9) as special (noise free) cases of the standard predictive equation (6) with u playing the role of (noise free) observations. Note that the (positive semi-deﬁnite) covariance matrices in (9) have the form K − Q with the following interpretation: the prior covariance K minus a (non-negative deﬁnite) matrix Q quantifying how much information u provides about the variables in question (f or f∗ ). We emphasize that all the sparse methods discussed in the paper correspond simply to different approximations to the conditionals in (9), and throughout we use the exact likelihood and inducing prior p(y|f) = N (f, σ2 I) , and p(u) = N (0, Ku,u ) . (10) noise 3. The Subset of Data (SoD) Approximation Before we get started with the more sophisticated approximations, we mention as a baseline method the simplest possible sparse approximation (which doesn’t fall inside our general scheme): use only a subset of the data (SoD). The computational complexity is reduced to O (m3 ), where m < n. We would not generally expect SoD to be a competitive method, since it would seem impossible (even with fairly redundant data and a good choice of the subset) to get a realistic picture of the 6. Note, that Qa,b depends on u although this is not explicit in the notation. 1942 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION u u e ¡ ¡ e e ¡ e ¡ e ¡ e ¡ r r r r r fn f1 f2 f∗ e ¡ ¡ e e ¡ e ¡ e ¡ e ¡ r r r r r fn f1 f2 f∗ Figure 1: Graphical model of the relation between the inducing variables u, the training latent functions values f = [ f1 , . . . , fn ] and the test function value f∗ . The thick horizontal line represents a set of fully connected nodes. The observations y1 , . . . , yn , y∗ (not shown) would dangle individually from the corresponding latent values, by way of the exact (factored) likelihood (5). Left graph: the fully connected graph corresponds to the case where no approximation is made to the full joint Gaussian process distribution between these variables. The inducing variables u are superﬂuous in this case, since all latent function values can communicate with all others. Right graph: assumption of conditional independence between training and test function values given u. This gives rise to the separation between training and test conditionals from (8). Notice that having cut the communication path between training and test latent function values, information from f can only be transmitted to f∗ via the inducing variables u. uncertainties, when only a part of the training data is even considered. We include it here mostly as a baseline against which to compare better sparse approximations. In Figure 5 top, left we see how the SoD method produces wide predictive distributions, when training on a randomly selected subset of 10 cases. A fair comparison to other methods would take into account that the computational complexity is independent of n as opposed to other more advanced methods. These extra computational resources could be spent in a number of ways, e.g. larger m, or an active (rather than random) selection of the m points. In this paper we will concentrate on understanding the theoretical foundations of the various approximations rather than investigating the necessary heuristics needed to turn the approximation schemes into actually practical algorithms. 4. The Subset of Regressors (SoR) Approximation The Subset of Regressors (SoR) algorithm was given by Silverman (1985), and mentioned again by Wahba et al. (1999). It was then adapted by Smola and Bartlett (2001) to propose a sparse greedy approximation to Gaussian process regression. SoR models are ﬁnite linear-in-the-parameters models with a particular prior on the weights. For any input x∗ , the corresponding function value f∗ is given by: f∗ = K∗,u wu , with −1 p(wu ) = N (0, Ku,u ) , (11) where there is one weight associated to each inducing input in Xu . Note that the covariance matrix for the prior on the weights is the inverse of that on u, such that we recover the exact GP prior on u, 1943 ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN which is Gaussian with zero mean and covariance u = Ku,u wu ⇒ uu = Ku,u wu wu Ku,u = Ku,u . (12) −1 Using the effective prior on u and the fact that wu = Ku,u u we can redeﬁne the SoR model in an equivalent, more intuitive way: −1 f∗ = K∗,u Ku,u u , with u ∼ N (0, Ku,u ) . (13) We are now ready to integrate the SoR model in our unifying framework. Given that there is a deterministic relation between any f∗ and u, the approximate conditional distributions in the integral in eq. (8) are given by: −1 qSoR (f|u) = N (Kf,u Ku,u u, 0) , and −1 qSoR (f∗ |u) = N (K∗,u Ku,u u, 0) , (14) with zero conditional covariance, compare to (9). The effective prior implied by the SoR approximation is easily obtained from (8), giving qSoR (f, f∗ ) = N 0, Qf,f Qf,∗ Q∗,f Q∗,∗ , (15) −1 where we recall Qa,b Ka,u Ku,u Ku,b . A more descriptive name for this method, would be the Deterministic Inducing Conditional (DIC) approximation. We see that this approximate prior is degenerate. There are only m degrees of freedom in the model, which implies that only m linearly independent functions can be drawn from the prior. The m + 1-th one is a linear combination of the previous. For example, in a very low noise regime, the posterior could be severely constrained by only m training cases. The degeneracy of the prior causes unreasonable predictive distributions. Indeed, the approximate prior over functions is so restrictive, that given enough data only a very limited family of functions will be plausible under the posterior, leading to overconﬁdent predictive variances. This is a general problem of ﬁnite linear models with small numbers of weights (for more details see Rasmussen and Qui˜ onero-Candela, 2005). Figure 5, top, right panel, illustrates the unreasonable n predictive uncertainties of the SoR approximation on a toy dataset.7 The predictive distribution is obtained by using the SoR approximate prior (15) instead of the true prior in (4). For each algorithm we give two forms of the predictive distribution, one which is easy to interpret, and the other which is economical to compute with: qSoR (f∗ |y) = N Q∗,f (Qf,f + σ2 I)−1 y, Q∗,∗ − Q∗,f (Qf,f + σ2 I)−1 Qf,∗ , noise noise = N σ K∗,u Σ Ku,f y, K∗,u ΣKu,∗ , −2 (16a) (16b) where we have deﬁned Σ = (σ−2 Ku,f Kf,u + Ku,u )−1 . Equation (16a) is readily recognized as the regular prediction equation (6), except that the covariance K has everywhere been replaced by Q, which was already suggested by (15). This corresponds to replacing the covariance function k with −1 kSoR (xi , x j ) = k(xi , u)Ku,u k(u, x j ). The new covariance function has rank (at most) m. Thus we have the following 7. Wary of this fact, Smola and Bartlett (2001) propose using the predictive variances of the SoD, or a more accurate computationally costly alternative (more details are given by Qui˜ onero-Candela, 2004, Chapter 3). n 1944 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION Remark 4 The SoR approximation is equivalent to exact inference in the degenerate Gaussian −1 process with covariance function kSoR (xi , x j ) = k(xi , u)Ku,u k(u, x j ). The equivalent (16b) is computationally cheaper, and with (11) in mind, Σ is the covariance of the posterior on the weights wu . Note that as opposed to the subset of data method, all training cases are taken into account. The computational complexity is O (nm2 ) initially, and O (m) and O (m2 ) per test case for the predictive mean and variance respectively. 5. The Deterministic Training Conditional (DTC) Approximation Taking up ideas already contained in the work of Csat´ and Opper (2002), Seeger et al. (2003) o recently proposed another sparse approximation to Gaussian process regression, which does not suffer from the nonsensical predictive uncertainties of the SoR approximation, but that interestingly leads to exactly the same predictive mean. Seeger et al. (2003), who called the method Projected Latent Variables (PLV), presented the method as relying on a likelihood approximation, based on −1 the projection f = Kf,u Ku,u u: p(y|f) −1 q(y|u) = N (Kf,u Ku,u u, σ2 I) . noise (17) The method has also been called the Projected Process Approximation (PPA) by Rasmussen and Williams (2006, Chapter 8). One way of obtaining an equivalent model is to retain the usual likelihood, but to impose a deterministic training conditional and the exact test conditional from eq. (9b) −1 qDTC (f|u) = N (Kf,u Ku,u u, 0), and qDTC (f∗ |u) = p(f∗ |u) . (18) This reformulation has the advantage of allowing us to stick to our view of exact inference (with exact likelihood) with approximate priors. Indeed, under this model the conditional distribution of f given u is identical to that of the SoR, given in the left of (14). A systematic name for this approximation is the Deterministic Training Conditional (DTC). The fundamental difference with SoR is that DTC uses the exact test conditional (9b) instead of the deterministic relation between f∗ and u of SoR. The joint prior implied by DTC is given by: qDTC (f, f∗ ) = N 0, Qf,f Qf,∗ Q∗,f K∗,∗ , (19) which is surprisingly similar to the effective prior implied by the SoR approximation (15). The fundamental difference is that under the DTC approximation f∗ has a prior variance of its own, given by K∗,∗ . This prior variance reverses the behaviour of the predictive uncertainties, and turns them into sensible ones, see Figure 5 for an illustration. The predictive distribution is now given by: qDTC (f∗ |y) = N (Q∗,f (Qf,f + σ2 I)−1 y, K∗,∗ − Q∗,f (Qf,f + σ2 I)−1 Qf,∗ noise noise = N σ K∗,u Σ Ku,f y, K∗,∗ − Q∗,∗ + K∗,u ΣK∗,u , −2 (20a) (20b) where again we have deﬁned Σ = (σ−2 Ku,f Kf,u + Ku,u )−1 as in (16). The predictive mean for the DTC is identical to that of the SoR approximation (16), but the predictive variance replaces the Q∗,∗ from SoR with K∗,∗ (which is larger, since K∗,∗ − Q∗,∗ is positive deﬁnite). This added term is the predictive variance of the posterior of f∗ conditioned on u. It grows to the prior variance K∗,∗ as x∗ moves far from the inducing inputs in Xu . 1945 ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN u e ¡ ¡ e e ¡ e ¡ e ¡ e ¡ r r r f1 f2 fn f∗ Figure 2: Graphical model for the FITC approximation. Compared to those in Figure 1, all edges between latent function values have been removed: the latent function values are conditionally fully independent given the inducing variables u. Although strictly speaking the SoR and DTC approximations could also be represented by this graph, note that both further assume a deterministic relation between f and u. Remark 5 The only difference between the predictive distribution of DTC and SoR is the variance. The predictive variance of DTC is never smaller than that of SoR. Note, that since the covariances for training cases and test cases are computed differently, see (19), it follows that Remark 6 The DTC approximation does not correspond exactly to a Gaussian process, as the covariance between latent values depends on whether they are considered training or test cases, violating consistency, see Deﬁnition 1. The computational complexity has the same order as for SoR. 6. The Fully Independent Training Conditional (FITC) Approximation Recently Snelson and Ghahramani (2006) proposed another likelihood approximation to speed up Gaussian process regression, which they called Sparse Gaussian Processes using Pseudo-inputs (SGPP). While the DTC is based on the likelihood approximation given by (17), the SGPP proposes a more sophisticated likelihood approximation with a richer covariance p(y|f) −1 q(y|u) = N (Kf,u Ku,u u, diag[Kf,f − Qf,f ] + σ2 I) , noise (21) where diag[A] is a diagonal matrix whose elements match the diagonal of A. As we did in (18) for the DTC, we provide an alternative equivalent formulation called Fully Independent Training Conditional (FITC) based on the inducing conditionals: n qFITC (f|u) = ∏ p( fi |u) = N i=1 −1 Kf,u Ku,u u, diag[Kf,f −Qf,f ] , and qFITC ( f∗ |u) = p( f∗ |u) . (22) We see that as opposed to SoR and DTC, FITC does not impose a deterministic relation between f and u. Instead of ignoring the variance, FITC proposes an approximation to the training conditional distribution of f given u as a further independence assumption. In addition, the exact test conditional from (9b) is used in (22), although for reasons which will become clear towards the end of this 1946 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION section, we initially consider only a single test case, f∗ . The corresponding graphical model is given in Figure 2. The effective prior implied by the FITC is given by qFITC (f, f∗ ) = N 0, Qf,f − diag[Qf,f − Kf,f ] Qf,∗ Q∗,f K∗,∗ . (23) Note, that the sole difference between the DTC and FITC is that in the top left corner of the implied prior covariance, FITC replaces the approximate covariances of DTC by the exact ones on the diagonal. The predictive distribution is qFITC ( f∗ |y) = N Q∗,f (Qf,f + Λ)−1 y, K∗,∗ − Q∗,f (Qf,f + Λ)−1 Qf,∗ (24a) = N K∗,u ΣKu,f Λ−1 y, K∗,∗ − Q∗,∗ + K∗,u ΣKu,∗ , (24b) where we have deﬁned Σ = (Ku,u + Ku,f Λ−1 Kf,u )−1 and Λ = diag[Kf,f − Qf,f + σ2 I ]. The compunoise tational complexity is identical to that of SoR and DTC. So far we have only considered a single test case. There are two options for joint predictions, either 1) use the exact full test conditional from (9b), or 2) extend the additional factorizing assumption to the test conditional. Although Snelson and Ghahramani (2006) don’t explicitly discuss joint predictions, it would seem that they probably intend the second option. Whereas the additional independence assumption for the test cases is not really necessary for computational reasons, it does affect the nature of the approximation. Under option 1) the training and test covariance are computed differently, and thus this does not correspond to our strict deﬁnition of a GP model, but Remark 7 Iff the assumption of full independence is extended to the test conditional, the FITC approximation is equivalent to exact inference in a non-degenerate Gaussian process with covariance function kFIC (xi , x j ) = kSoR (xi , x j ) + δi, j [k(xi , x j ) − kSoR (xi , x j )], where δi, j is Kronecker’s delta. A logical name for the method where the conditionals (training and test) are always forced to be fully independent would be the Fully Independent Conditional (FIC) approximation. The effective prior implied by FIC is: qFIC (f, f∗ ) = N 0, Qf,f − diag[Qf,f − Kf,f ] Qf,∗ Q∗,f Q∗,∗ − diag[Q∗,∗ − K∗,∗ ] . (25) 7. The Partially Independent Training Conditional (PITC) Approximation In the previous section we saw how to improve the DTC approximation by approximating the training conditional with an independent distribution, i.e. one with a diagonal covariance matrix. In this section we will further improve the approximation (while remaining computationally attractive) by extending the training conditional to have a block diagonal covariance: −1 qPITC (f|u) = N Kf,u Ku,u u, blockdiag[Kf,f − Qf,f ] , and qPITC (f∗ |u) = p(f∗ |u) . (26) where blockdiag[A] is a block diagonal matrix (where the blocking structure is not explicitly stated). We represent graphically the PITC approximation in Figure 3. Developing this analogously to the FITC approximation from the previous section, we get the joint prior qPITC (f, f∗ ) = N 0, Qf,f − blockdiag[Qf,f − Kf,f ] Qf,∗ Q∗,f K∗,∗ 1947 , (27) ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN u e ¡ ¡ e e ¡ e ¡ e ¡ e ¡ r r r fI fI fI f∗ 1 2 k Figure 3: Graphical representation of the PITC approximation. The set of latent function values fIi indexed by the the set of indices Ii is fully connected. The PITC differs from FITC (see graph in Fig. 2) in that conditional independence is now between the k groups of training latent function values. This corresponds to the block diagonal approximation to the true training conditional given in (26). and the predictive distribution is identical to (24), except for the alternative deﬁnition of Λ = blockdiag[Kf,f − Qf,f + σ2 I ]. An identical expression was obtained by Schwaighofer and Tresp noise (2003, Sect. 3), developing from the original Bayesian committee machine (BCM) by Tresp (2000). The relationship to the FITC was pointed out by Lehel Csat´ . The BCM was originally proposed as o a transductive learner (i.e. where the test inputs have to be known before training), and the inducing inputs Xu were chosen to be the test inputs. We discuss transduction in detail in the next section. It is important to realize that the BCM proposes two orthogonal ideas: ﬁrst, the block diagonal structure of the partially independent training conditional, and second setting the inducing inputs to be the test inputs. These two ideas can be used independently and in Section 8 we propose using the ﬁrst without the second. The computational complexity of the PITC approximation depends on the blocking structure imposed in (26). A reasonable choice, also recommended by Tresp (2000) may be to choose k = n/m blocks, each of size m × m. The computational complexity remains O (nm2 ). Since in the PITC model the covariance is computed differently for training and test cases Remark 8 The PITC approximation does not correspond exactly to a Gaussian process. This is because computing covariances requires knowing whether points are from the training- or test-set, (27). One can obtain a Gaussian process from the PITC by extending the partial conditional independence assumption to the test conditional, as we did in Remark 7 for the FITC. 8. Transduction and Augmentation The idea of transduction is that one should restrict the goal of learning to prediction on a prespeciﬁed set of test cases, rather than trying to learn an entire function (induction) and then evaluate it at the test inputs. There may be no universally agreed upon deﬁnition of transduction. In this paper we use Deﬁnition 9 Transduction occurs only if the predictive distribution depends on other test inputs. This operational deﬁnition excludes models for which there exist an equivalent inductive counterpart. According to this deﬁnition, it is irrelevant when the bulk of the computation takes place. 1948 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION u f∗ e ¡ ¡ e e ¡ ¡ e e ¡ e ¡ r r r fI fI fI 1 2 k Figure 4: Two views on Augmentation. One view is to see that the test latent function value f∗ is now part of the inducing variables u and therefore has access to the training latent function values. An equivalent view is to consider that we have dropped the assumption of conditional independence between f∗ and the training latent function values. Even if f∗ has now direct access to each of the training fi , these still need to go through u to talk to each other if they fall in conditionally independent blocks. We have in this ﬁgure decided to recycle the graph for PITC from Figure 3 to show that all approximations we have presented can be augmented, irrespective of what the approximation for the training conditional is. There are several different possible motivations for transduction: 1) transduction is somehow easier than induction (Vapnik, 1995), 2) the test inputs may reveal important information, which should be used during training. This motivation drives models in semi-supervised learning (studied mostly in the context of classiﬁcation) and 3) for approximate algorithms one may be able to limit the discrepancies of the approximation at the test points. For exact GP models it seems that the ﬁrst reason doesn’t really apply. If you make predictions at the test points that are consistent with a GP, then it is trivial inside the GP framework to extend these to any other input points, and in effect we have done induction. The second reason seems more interesting. However, in a standard GP setting, it is a consequence of the consistency property, see Remark 2, that predictions at one test input are independent of the location of any other test inputs. Therefore transduction can not be married with exact GPs: Remark 10 Transduction can not occur in exact Gaussian process models. Whereas this holds for the usual setting of GPs, it could be different in non-standard situations where e.g. the covariance function depends on the empirical input densities. Transduction can occur in the sparse approximation to GPs, by making the choice of inducing variables depend on the test inputs. The BCM from the previous section, where Xu = X∗ (where X∗ are the test inputs) is an example of this. Since the inducing variables are connected to all other nodes (see Figure 3) we would expect the approximation to be good at u = f∗ , which is what we care about for predictions, relating to reason 3) above. While this reasoning is sound, it is not necessarily a sufﬁcient consideration for getting a good model. The model has to be able to simultaneously explain the training targets as well and if the choice of u makes this difﬁcult, the posterior at the points of interest may be distorted. Thus, the choice of u should be governed by the ability to model the conditional of the latents given the inputs, and not solely by the density of the (test) inputs. The main drawback of transduction is that by its nature it doesn’t provide a predictive model in the way inductive models do. In the usual GP model one can do the bulk of the computation 1949 ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN involved in the predictive distributions (e.g. matrix inversion) before seeing the test cases, enabling fast computation of test predictions. It is interesting that whereas other methods spend much effort trying to optimize the inducing variables, the BCM simply uses the test set. The quality of the BCM approximation depends then on the particular location of the test inputs, upon which one usually does not have any control. We now see that there may be a better method, eliminating the drawback of transduction, namely use the PITC approximation, but choose the u’s carefully (see Section 9), don’t just use the test set. 8.1 Augmentation An idea closely related to transduction, but not covered by our deﬁnition, is augmentation, which in contrast to transduction is done individually for each test case. Since in the previous sections, we haven’t assumed anything about u, we can simply augment the set of inducing variables by f∗ (i.e. have one additional inducing variable equal to the current test latent), and see what happens in the predictive distributions for the different methods. Let’s ﬁrst investigate the consequences for the test conditional from (9b). Note, the interpretation of the covariance matrix K∗,∗ − Q∗,∗ was “the prior covariance minus the information which u provides about f∗ ”. It is clear that the augmented u (with f∗ ) provides all possible information about f∗ , and consequently Q∗,∗ = K∗,∗ . An equivalent view on augmentation is that the assumption of conditional independence between f∗ and f is dropped. This is seen trivially by adding edges between f∗ and the fi in the graphical model, Figure 4. Augmentation was originally proposed by Rasmussen (2002), and applied in detail to the SoR with RBF covariance by Qui˜ onero-Candela (2004). Because the SoR is a ﬁnite linear model, and n the basis functions are local (Gaussian bumps), the predictive distributions can be very misleading. For example, when making predictions far away from the center of any basis function, all basis functions have insigniﬁcant magnitudes, and the prediction (averaged over the posterior) will be close to zero, with very small error-bars; this is the opposite of the desired behaviour, where we would expect the error-bars to grow as we move away from the training cases. Here augmentation makes a particularly big difference turning the nonsensical predictive distribution into a reasonable one, by ensuring that there is always a basis function centered on the test case. Compare the nonaugmented to the augmented SoR in Figure 5. An analogous Gaussian process based ﬁnite linear model that has recently been healed by augmentation is the relevance vector machine (Rasmussen and Qui˜ onero-Candela, 2005). n Although augmentation was initially proposed for a narrow set of circumstances, it is easily applied to any of the approximations discussed. Of course, augmentation doesn’t make any sense for an exact, non-degenerate Gaussian process model (a GP with a covariance function that has a feature-space which is inﬁnite dimensional, i.e. with basis functions everywhere). Remark 11 A full non-degenerate Gaussian process cannot be augmented, since the corresponding f∗ would already be connected to all other variables in the graphical model. But augmentation does make sense for sparse approximations to GPs. The more general process view on augmentation has several advantages over the basis function view. It is not completely clear from the basis function view, which basis function should be used for augmentation. For example, Rasmussen and Qui˜ onero-Candela (2005) successfully apply augn mentation using basis functions that have a zero contribution at the test location! In the process view 1950 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION however, it seems clear that one would chose the additional inducing variable to be f∗ , to minimize the effects of the approximations. Let us compute the effective prior for the augmented SoR. Given that f∗ is in the inducing set, the test conditional is not an approximation and we can rewrite the integral leading to the effective prior: Z qASoR (f∗ , f) = qSoR (f| f∗ , u) p( f∗ , u) du . (28) It is interesting to notice that this is also the effective prior that would result from augmenting the DTC approximation, since qSoR (f| f∗ , u) = qDTC (f| f∗ , u). Remark 12 Augmented SoR (ASoR) is equivalent to augmented DTC (ADTC). Augmented DTC only differs from DTC in the additional presence of f∗ among the inducing variables in the training conditional. We can only expect augmented DTC to be a more accurate approximation than DTC, since adding an additional inducing variable can only help capture information from y. Therefore Remark 13 DTC is a less accurate (but cheaper) approximation than augmented SoR. We saw previously in Section 5 that the DTC approximation does not suffer from the nonsensical predictive variances of the SoR. The equivalence between the augmented SoR and augmented DTC is another way of seeing how augmentation reverses the misbehaviour of SoR. The predictive distribution of the augmented SoR is obtained by adding f∗ to u in (20). Prediction with an augmented sparse model comes at a higher computational cost, since now f∗ directly interacts with all of f and not just with u. For each new test case, updating the augmented Σ in the predictive equation (for example (20b) for DTC) implies computing the vector matrix product K∗,f Kf,u with complexity O (nm). This is clearly higher than the O (m) for the mean, and O (m2 ) for the predictive distribution of all the non-augmented methods we have discussed. Augmentation seems to be only really necessary for methods that make a severe approximation to the test conditional, like the SoR. For methods that make little or no approximation to the test conditional, it is difﬁcult to predict the degree to which augmentation would help. However, one can see by giving f∗ access to all of the training latent function values in f, one would expect augmentation to give less under-conﬁdent predictive distributions near the training data. Figure 5 clearly shows that augmented DTC (equivalent to augmented SoR) has a superior predictive distribution (both mean and variance) than standard DTC. Note however that in the ﬁgure we have purposely chosen a too short lengthscale to enhance visualization. Quantitatively, this superiority was experimentally assessed by Qui˜ onero-Candela (2004, Table 3.1). Augmentation hasn’t been n compared to the more advanced approximations FITC and PITC, and the ﬁgure would change in the more realistic scenario where the inducing inputs and hyperparameters are learnt (Snelson and Ghahramani, 2006). Transductive methods like the BCM can be seen as joint augmentation, and one could potentially use it for any of the methods presented. It seems that the good performance of the BCM could essentially stem from augmentation, the presence of the other test inputs in the inducing set being probably of little beneﬁt. Joint augmentation might bring some computational advantage, but won’t change the scaling: note that augmenting m times at a cost of O (nm) apiece implies the same O (nm2 ) total cost as the jointly augmented BCM. 1951 ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN SoD SoR 1.5 1.5 1 1 0.5 0.5 0 0 −0.5 −0.5 −1 −1 −1.5 −15 −10 −5 0 5 10 15 −1.5 −15 −10 −5 DTC 0 5 10 15 5 10 15 5 10 15 ASoR/ADTC 1.5 1.5 1 1 0.5 0.5 0 0 −0.5 −0.5 −1 −1 −1.5 −15 −10 −5 0 5 10 15 −1.5 −15 −10 −5 FITC 0 PITC 1.5 1.5 1 1 0.5 0.5 0 0 −0.5 −0.5 −1 −1 −1.5 −15 −10 −5 0 5 10 15 −1.5 −15 −10 −5 0 Figure 5: Toy example with identical covariance function and hyperparameters. The squared exponential covariance function is used, and a slightly too short lengthscale is chosen on purpose to emphasize the different behaviour of the predictive uncertainties. The dots are the training points, the crosses are the targets corresponding to the inducing inputs, randomly selected from the training set. The solid line is the mean of the predictive distribution, and the dotted lines show the 95% conﬁdence interval of the predictions. Augmented DTC (ADTC) is equivalent to augmented SoR (ASoR), see Remark 12. 1952 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION 9. On the Choice of the Inducing Variables We have until now assumed that the inducing inputs Xu were given. Traditionally, sparse models have very often been built upon a carefully chosen subset of the training inputs. This concept is probably best exempliﬁed in the popular support vector machine (Cortes and Vapnik, 1995). In sparse Gaussian processes it has also been suggested to select the inducing inputs Xu from among the training inputs. Since this involves a prohibitive combinatorial optimization, greedy optimization approaches have been suggested using various selection criteria like online learning (Csat´ and o Opper, 2002), greedy posterior maximization (Smola and Bartlett, 2001), maximum information gain (Seeger et al., 2003), matching pursuit (Keerthi and Chu, 2006), and probably more. As discussed in the previous section, selecting the inducing inputs from among the test inputs has also been considered in transductive settings. Recently, Snelson and Ghahramani (2006) have proposed to relax the constraint that the inducing variables must be a subset of training/test cases, turning the discrete selection problem into one of continuous optimization. One may hope that ﬁnding a good solution is easier in the continuous than the discrete case, although ﬁnding the global optimum is intractable in both cases. And perhaps the less restrictive choice can lead to better performance in very sparse models. Which optimality criterion should be used to set the inducing inputs? Departing from a fully Bayesian treatment which would involve deﬁning priors on Xu , one could maximize the marginal likelihood (also called the evidence) with respect to Xu , an approach also followed by Snelson and Ghahramani (2006). Each of the approximate methods proposed involves a different effective prior, and hence its own particular effective marginal likelihood conditioned on the inducing inputs q(y|Xu ) = ZZ p(y|f) q(f|u) p(u|Xu )du df = Z p(y|f) q(f|Xu )df , (29) which of course is independent of the test conditional. We have in the above equation explicitly conditioned on the inducing inputs Xu . Using Gaussian identities, the effective marginal likelihood is very easily obtained by adding a ridge σ2 I (from the likelihood) to the covariance of effective noise prior on f. Using the appropriate deﬁnitions of Λ, the log marginal likelihood becomes 1 log q(y|Xu ) = − 2 log |Qf,f + Λ| − 1 y (Qf,f + Λ)−1 y − n log(2π) , 2 2 (30) where ΛSoR = ΛDTC = σ2 I, ΛFITC = diag[Kf,f − Qf,f ] + σ2 I, and ΛPITC = blockdiag[Kf,f − noise noise Qf,f ] + σ2 I. The computational cost of the marginal likelihood is O (nm2 ) for all methods, that of noise its gradient with respect to one element of Xu is O (nm). This of course implies that the complexity of computing the gradient wrt. to the whole of Xu is O (dnm2 ), where d is the dimension of the input space. It has been proposed to maximize the effective posterior instead of the effective marginal likelihood (Smola and Bartlett, 2001). However this is potentially dangerous and can lead to overﬁtting. Maximizing the whole evidence instead is sound and comes at an identical computational cost (for a deeper analysis see Qui˜ onero-Candela, 2004, Sect. 3.3.5 and Fig. 3.2). n The marginal likelihood has traditionally been used to learn the hyperparameters of GPs in the non fully Bayesian treatment (see for example Williams and Rasmussen, 1996). For the sparse approximations presented here, once you are learning Xu it is straightforward to allow for learning hyperparameters (of the covariance function) during the same optimization, and there is no need to interleave optimization of u with learning of the hyperparameters as it has been proposed for example by Seeger et al. (2003). 1953 ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN 10. Other Methods In this section we brieﬂy mention two approximations which don’t ﬁt in our unifying scheme, since one doesn’t correspond to a proper probabilistic model, and the other one uses a particular construction for the covariance function, rather than allowing any general covariance function. 10.1 The Nystr¨ m Approximation o The Nystr¨ m Approximation for speeding up GP regression was originally proposed by Williams o and Seeger (2001), and then questioned by Williams et al. (2002). Like SoR and DTC, the Nystr¨ m o Approximation for GP regression approximates the prior covariance of f by Qf,f . However, unlike these methods, the Nystr¨ m Approximation is not based on a generative probabilistic model. The o prior covariance between f∗ and f is taken to be exact, which is inconsistent with the prior covariance on f: Qf,f Kf,∗ . (31) q(f, f∗ ) = N 0, K∗,f K∗,∗ As a result we cannot derive this method from our unifying framework, nor represent it with a graphical model. Worse, the resulting prior covariance matrix is not even guaranteed to be positive deﬁnite, allowing the predictive variances to be negative. Notice that replacing Kf,∗ by Qf,∗ in (31) is enough to make the prior covariance positive deﬁnite, and one obtains the DTC approximation. Remark 14 The Nystr¨ m Approximation does not correspond to a well-formed probabilistic model. o Ignoring any quibbles about positive deﬁniteness, the predictive distribution of the Nystr¨ m Apo proximation is given by: p( f∗ |y) = N Kf,∗ [Qf,f + σ2 I]−1 y, K∗,∗ − Kf,∗ [Qf,f + σ2 I]−1 Kf,∗ , noise noise (32) but the predictive variance is not guaranteed to be positive. The computational cost is O (nm2 ). 10.2 The Relevance Vector Machine The relevance vector machine, introduced by Tipping (2001), is a ﬁnite linear model with an independent Gaussian prior imposed on the weights. For any input x∗ , the corresponding function output is given by: f∗ = φ∗ w , with p(w|A) = N (0, A) , (33) where φ∗ = [φ1 (x), . . . , φm (x)] is the (row) vector of responses of the m basis functions, and A = diag(α1 , . . . , αm ) is the diagonal matrix of joint prior precisions (inverse variances) of the weights. The αi are learnt by maximizing the RVM evidence (obtained by also assuming Gaussian additive iid. noise, see (1)), and for the typical case of rich enough sets of basis functions many of the precisions go to inﬁnity effectively pruning out the corresponding weights (for a very interesting analysis see Wipf et al., 2004). The RVM is thus a sparse method and the surviving basis functions are called relevance vectors. Note that since the RVM is a ﬁnite linear model with Gaussian priors on the weights, it can be seen as a Gaussian process: Remark 15 The RVM is equivalent to a degenerate Gaussian process with covariance function kRVM (xi , x j ) = φi A−1 φ j = ∑m α−1 φk (xi ) φk (x j ), k=1 k 1954 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION q(f∗ |u) q(f|u) GP exact exact SoR determ. determ. DTC exact determ. FITC (exact) fully indep. PITC exact partially indep. Method joint prior covariance Kf,f Kf,∗ K∗,f K∗,∗ Qf,f Qf,∗ Q∗,f Q∗,∗ Qf,f Qf,∗ Q∗,f K∗,∗ Qf,f − diag[Qf,f − Kf,f ] Qf,∗ Q∗,f K∗,∗ Qf,f − blokdiag[Qf,f − Kf,f ] Qf,∗ Q∗,f K∗,∗ GP? √ √ √ ( ) Table 1: Summary of the way approximations are built. All these methods are detailed in the previous sections. The initial cost and that of the mean and variance per test case are respectively n2 , n and n2 for the exact GP, and nm2 , m and m2 for all other methods. The “GP?” column indicates whether the approximation is equivalent to a GP. For FITC see Remark 7. as was also pointed out by Tipping (2001, eq. (59)). Whereas all sparse approximations we have presented until now are totally independent of the choice of covariance function, for the RVM this choice is restricted to covariance functions that can be expressed as ﬁnite expansions in terms of some basis functions. Being degenerate GPs in exactly the same way as the SoR (presented in Section 4), the RVM does also suffer from unreasonable predictive variances. Rasmussen and Qui˜ onero-Candela (2005) show that the predictive distributions of RVMs can also be healed by n augmentation, see Section 8. Once the αi have been learnt, denoting by m the number of surviving relevance vectors, the complexity of computing the predictive distribution of the RVM is O (m) for mean and O (m2 ) for the variance. RVMs are often used with radial basis functions centered on the training inputs. One potentially interesting extension to the RVM would be to learn the locations of the centers of the basis functions, in the same way as proposed by Snelson and Ghahramani (2006) for the FITC approximation, see Section 6. This is a curious reminiscence of learning the centers in RBF Networks. 11. Conclusions We have provided a unifying framework for sparse approximations to Gaussian processes for regression. Our approach consists of two steps, ﬁrst 1) we recast the approximation in terms of approximations to the prior, and second 2) we introduce inducing variables u and the idea of conditional independence given u. We recover all existing sparse methods by making further simpliﬁcations of the covariances of the training and test conditionals, see Table 1 for a summary. Previous methods were presented based on different approximation paradigms (e.g. likelihood approximations, projection methods, matrix approximations, minimization of Kullback-Leibler divergence, etc), making direct comparison difﬁcult. Under our unifying view we deconstruct methods, making it clear which building blocks they are based upon. For example, the SGPP by Snelson 1955 ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN and Ghahramani (2006) contains two ideas, 1) a likelihood approximation and 2) the idea of varying the inducing inputs continuously; these two ideas could easily be used independently, and incorporated in other methods. Similarly, the BCM by Tresp (2000) contains two independent ideas 1) a block diagonal assumption, and 2) the (transductive) idea of choosing the test inputs as the inducing variables. Finally we note that although all three ideas of 1) transductively setting u = f∗ , 2) augmentation and 3) continuous optimization of Xu have been proposed in very speciﬁc settings, in fact they are completely general ideas, which can be applied to any of the approximation schemes considered. We have ranked the approximation according to how close they are to the corresponding full GP. However, the performance in practical situations may not always follow this theoretical ranking since the approximations might exhibit properties (not present in the full GP) which may be particularly suitable for speciﬁc datasets. This may make the interpretation of empirical comparisons challenging. A further complication arises when adding the necessary heuristics for turning the theoretical constructs into practical algorithms. We have not described full algorithms in this paper, but are currently working on a detailed empirical study (in preparation, see also Rasmussen and Williams, 2006, chapter 8). We note that the order of the computational complexity is identical for all the methods considered, O (nm2 ). This highlights that there is no computational excuse for using gross approximations, such as assuming deterministic relationships, in particular one should probably think twice before using SoR or even DTC. Although augmentation has attractive predictive properties, it is computationally expensive. It remains unclear whether augmentation could be beneﬁcial on a ﬁxed computational budget. We have only considered the simpler case of regression in this paper, but sparseness is also commonly sought in classiﬁcation settings. It should not be difﬁcult to cast probabilistic approximation methods such as Expectation Propagation (EP) or the Laplace method (for a comparison, see Kuss and Rasmussen, 2005) into our unifying framework. Our analysis suggests that a new interesting approximation would come from combining the best possible approximation (PITC) with the most powerful selection method for the inducing inputs. This would correspond to a non-transductive version of the BCM. We would evade the necessity of knowing the test set before doing the bulk of the computation, and we could hope to supersede the superior performance reported by Snelson and Ghahramani (2006) for very sparse approximations. Acknowledgments Thanks to Neil Lawrence for arranging the 2005 Gaussian Process Round Table meeting in Shefﬁeld, which provided much inspiration to this paper. Special thanks to Olivier Chapelle, Lehel Csat´ , o Zoubin Ghahramani, Matthias Seeger, Ed Snelson and Chris Williams for helpful discussions, and to three anonymous reviewers. Both authors were supported by the German Research Council (DFG) through grant RA 1030/1. This work was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778. 1956 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION Appendix A. Gaussian and Matrix Identities In this appendix we provide identities used to manipulate matrices and Gaussian distributions throughout the paper. Let x and y be jointly Gaussian x y µx µy ∼ N , A C C B , (34) then the marginal and the conditional are given by x ∼ N (µx , A) , and x|y ∼ N µx +C B−1 (y − µy ), A −C B−1C (35) Also, the product of a Gaussian in x with a Gaussian in a linear projection P x is again a Gaussian, although unnormalized N (x|a, A) N (P x|b, B) = zc N (x|c,C) , (36) where C = A−1 + P B−1 P −1 c = C A−1 a + P B−1 b . , The normalizing constant zc is gaussian in the means a and b of the two Gaussians: m 1 1 zc = (2 π)− 2 |B + P A P |− 2 exp − 2 (b − P a) B+PAP −1 (b − P a) . (37) The matrix inversion lemma, also known as the Woodbury, Sherman & Morrison formula states that: (Z +UWV )−1 = Z −1 − Z −1U(W −1 +V Z −1U)−1V Z −1 , (38) assuming the relevant inverses all exist. Here Z is n × n, W is m × m and U and V are both of size n × m; consequently if Z −1 is known, and a low rank (ie. m < n) perturbation are made to Z as in left hand side of eq. (38), considerable speedup can be achieved. References Corinna Cortes and Vladimir Vapnik. Support-vector network. Machine Learning, 20(3):273–297, 1995. Lehel Csat´ and Manfred Opper. Sparse online Gaussian processes. Neural Computation, 14(3): o 641–669, 2002. Sathiya Keerthi and Wei Chu. A Matching Pursuit approach to sparse Gaussian process regression. In Y. Weiss, B. Sch¨ lkopf, and J. Platt, editors, Advances in Neural Information Processing o Systems 18, Cambridge, Massachussetts, 2006. The MIT Press. Malte Kuss and Carl Edward Rasmussen. Assessing approximate inference for binary Gaussian process classiﬁcation. Journal of Machine Learning Research, pages 1679–1704, 2005. Joaquin Qui˜ onero-Candela. Learning with Uncertainty – Gaussian Processes and Relevance Vecn tor Machines. PhD thesis, Technical University of Denmark, Lyngby, Denmark, 2004. Carl Edward Rasmussen. Reduced rank Gaussian process learning. Technical report, Gatsby Computational Neuroscience Unit, UCL, 2002. 1957 ˜ Q UI NONERO -C ANDELA AND R ASMUSSEN Carl Edward Rasmussen and Joaquin Qui˜ onero-Candela. Healing the relevance vector machine by n augmentation. In International Conference on Machine Learning, 2005. Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. The MIT press, 2006. Anton Schwaighofer and Volker Tresp. Transductive and inductive methods for approximate Gaussian process regression. In Suzanna Becker, Sebastian Thrun, and Klaus Obermayer, editors, Advances in Neural Information Processing Systems 15, pages 953–960, Cambridge, Massachussetts, 2003. The MIT Press. Matthias Seeger, Christopher K. I. Williams, and Neil Lawrence. Fast forward selection to speed up sparse Gaussian process regression. In Christopher M. Bishop and Brendan J. Frey, editors, Ninth International Workshop on Artiﬁcial Intelligence and Statistics. Society for Artiﬁcial Intelligence and Statistics, 2003. Bernhard W. Silverman. Some aspects of the spline smoothing approach to non-parametric regression curve ﬁtting. J. Roy. Stat. Soc. B, 47(1):1–52, 1985. (with discussion). Alexander J. Smola and Peter L. Bartlett. Sparse greedy Gaussian process regression. In Todd K. Leen, Thomas G. Dietterich, and Volker Tresp, editors, Advances in Neural Information Processing Systems 13, pages 619–625, Cambridge, Massachussetts, 2001. The MIT Press. Edward Snelson and Zoubin Ghahramani. Sparse Gaussian processes using pseudo-inputs. In Y. Weiss, B. Sch¨ lkopf, and J. Platt, editors, Advances in Neural Information Processing Systems o 18, Cambridge, Massachussetts, 2006. The MIT Press. Michael E. Tipping. Sparse Bayesian learning and the Relevance Vector Machine. Journal of Machine Learning Research, 1:211–244, 2001. Volker Tresp. A Bayesian committee machine. Neural Computation, 12(11):2719–2741, 2000. Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer Verlag, 1995. Grace Wahba, Xiwu Lin, Fangyu Gao, Dong Xiang, Ronald Klein, and Barbara Klein. The biasvariance tradeoff and the randomized GACV. In Michael S. Kerns, Sara A. Solla, and David A. Cohn, editors, Advances in Neural Information Processing Systems 11, pages 620–626, Cambridge, Massachussetts, 1999. The MIT Press. Christopher K. I. Williams and Carl Edward Rasmussen. Gaussian processes for regression. In David S. Touretzky, Michael C. Mozer, and Michael E. Hasselmo, editors, Advances in Neural Information Processing Systems 8, pages 514–520, Cambridge, Massachussetts, 1996. The MIT Press. Christopher K. I. Williams, Carl Edward Rasmussen, Anton Schwaighofer, and Volker Tresp. Observations of the Nystr¨ m method for Gaussiam process prediction. Technical report, University o of Edinburgh, Edinburgh, Scotland, 2002. 1958 S PARSE A PPROXIMATE G AUSSIAN P ROCESS R EGRESSION Christopher K. I. Williams and Mathias Seeger. Using the Nystr¨ m method to speed up kernel o machines. In Todd K. Leen, Thomas G. Dietterich, and Volker Tresp, editors, Advances in Neural Information Processing Systems 13, pages 682–688, Cambridge, Massachussetts, 2001. The MIT Press. David Wipf, Jason Palmer, and Bhaskar Rao. Perspectives on sparse Bayesian learning. In Sebastian Thrun, Lawrence Saul, and Bernhard Sch¨ lkopf, editors, Advances in Neural Information o Processing Systems 16, Cambridge, Massachussetts, 2004. The MIT Press. 1959

3 0.28807133 61 jmlr-2005-Prioritization Methods for Accelerating MDP Solvers

Author: David Wingate, Kevin D. Seppi

4 0.28629252 5 jmlr-2005-A Generalization Error for Q-Learning

Author: Susan A. Murphy

Abstract: Planning problems that involve learning a policy from a single training set of ﬁnite horizon trajectories arise in both social science and medical ﬁelds. We consider Q-learning with function approximation for this setting and derive an upper bound on the generalization error. This upper bound is in terms of quantities minimized by a Q-learning algorithm, the complexity of the approximation space and an approximation term due to the mismatch between Q-learning and the goal of learning a policy that maximizes the value function. Keywords: multistage decisions, dynamic programming, reinforcement learning, batch data

5 0.26933151 33 jmlr-2005-Fast Kernel Classifiers with Online and Active Learning

Author: Antoine Bordes, Seyda Ertekin, Jason Weston, Léon Bottou

Abstract: Very high dimensional learning systems become theoretically possible when training examples are abundant. The computing cost then becomes the limiting factor. Any efﬁcient learning algorithm should at least take a brief look at each example. But should all examples be given equal attention? This contribution proposes an empirical answer. We ﬁrst present an online SVM algorithm based on this premise. LASVM yields competitive misclassiﬁcation rates after a single pass over the training examples, outspeeding state-of-the-art SVM solvers. Then we show how active example selection can yield faster training, higher accuracies, and simpler models, using only a fraction of the training example labels.

6 0.26835507 46 jmlr-2005-Learning a Mahalanobis Metric from Equivalence Constraints

7 0.26670751 36 jmlr-2005-Gaussian Processes for Ordinal Regression

8 0.2635715 49 jmlr-2005-Learning the Kernel with Hyperkernels (Kernel Machines Section)

9 0.26055074 19 jmlr-2005-Clustering on the Unit Hypersphere using von Mises-Fisher Distributions

10 0.2585384 31 jmlr-2005-Estimation of Non-Normalized Statistical Models by Score Matching

11 0.25789478 3 jmlr-2005-A Classification Framework for Anomaly Detection

12 0.25757948 71 jmlr-2005-Variational Message Passing

13 0.2567699 45 jmlr-2005-Learning Multiple Tasks with Kernel Methods

14 0.25675595 64 jmlr-2005-Semigroup Kernels on Measures

15 0.2560297 63 jmlr-2005-Quasi-Geodesic Neural Learning Algorithms Over the Orthogonal Group: A Tutorial

16 0.25375888 39 jmlr-2005-Information Bottleneck for Gaussian Variables

17 0.25355154 24 jmlr-2005-Core Vector Machines: Fast SVM Training on Very Large Data Sets

18 0.253075 52 jmlr-2005-Loopy Belief Propagation: Convergence and Effects of Message Errors

19 0.2515173 54 jmlr-2005-Managing Diversity in Regression Ensembles

20 0.25040936 35 jmlr-2005-Frames, Reproducing Kernels, Regularization and Learning