nips nips2001 nips2001-61 knowledge-graph by maker-knowledge-mining

61 nips-2001-Distribution of Mutual Information

Source: pdf

Author: Marcus Hutter

Abstract: The mutual information of two random variables z and J with joint probabilities {7rij} is commonly used in learning Bayesian nets as well as in many other fields. The chances 7rij are usually estimated by the empirical sampling frequency nij In leading to a point estimate J(nij In) for the mutual information. To answer questions like

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 ch/- marcus Abstract The mutual information of two random variables z and J with joint probabilities {7rij} is commonly used in learning Bayesian nets as well as in many other fields. [sent-4, score-0.402]

2 The chances 7rij are usually estimated by the empirical sampling frequency nij In leading to a point estimate J(nij In) for the mutual information. [sent-5, score-1.001]

3 To answer questions like "is J (nij In) consistent with zero? [sent-6, score-0.079]

4 " or "what is the probability that the true mutual information is much larger than the point estimate? [sent-7, score-0.246]

5 In the Bayesian framework one can answer these questions by utilizing a (second order) prior distribution p( 7r) comprising prior information about 7r. [sent-9, score-0.41]

6 From the prior p(7r) one can compute the posterior p(7rln), from which the distribution p(Iln) of the mutual information can be calculated. [sent-10, score-0.529]

7 We derive reliable and quickly computable approximations for p(Iln). [sent-11, score-0.096]

8 We concentrate on the mean, variance, skewness, and kurtosis , and non-informative priors. [sent-12, score-0.213]

9 1 Introduction The mutual information J (also called cross entropy) is a widely used information theoretic measure for the stochastic dependency of random variables [CT91, SooOO] . [sent-15, score-0.305]

10 The mutual information defined in (1) can be computed if the joint probabilities {7rij} of the two random variables z and J are known. [sent-17, score-0.275]

11 The standard procedure in the common case of unknown chances 7rij is to use the sample frequency estimates n~; instead, as if they were precisely known probabilities; but this is not always appropriate. [sent-18, score-0.187]

12 Furthermore, the point estimate J (n~; ) gives no clue about the reliability of the value if the sample size n is finite. [sent-19, score-0.088]

13 In the Bayesian framework one can answer these questions by utilizing a (second order) prior distribution p(7r),which takes account of any impreciseness about 7r. [sent-23, score-0.286]

14 From the prior p(7r) one can compute the posterior p(7rln), from which the distribution p(Iln) of the mutual information can be obtained. [sent-24, score-0.529]

15 The objective of this work is to derive reliable and quickly computable analytical expressions for p(1ln). [sent-25, score-0.147]

16 Section 2 introduces the mutual information distribution, Section 3 discusses some results in advance before delving into the derivation. [sent-26, score-0.246]

17 Since the central limit theorem ensures that p(1ln) converges to a Gaussian distribution a good starting point is to compute the mean and variance of p(1ln). [sent-27, score-0.391]

18 In section 4 we relate the mean and variance to the covariance structure of p(7rln). [sent-28, score-0.285]

19 An exact expression for the mean (Section 6) and approximate expressions for t he variance (Sections 5) are given for the Dirichlet distribution. [sent-30, score-0.503]

20 More accurate estimates of the variance and higher central moments are derived in Section 7, which lead to good approximations of p(1ln) even for small sample sizes. [sent-31, score-0.509]

21 We show that the expressions obtained in [KJ96, Kle99] by heuristic numerical methods are incorrect. [sent-32, score-0.119]

22 Often one does not know the probabilities 7rij exactly, but one has a sample set with nij outcomes of pair (i,j). [sent-51, score-0.516]

23 The frequency irij := n~j may be used as a first estimate of the unknown probabilities. [sent-52, score-0.087]

24 This leads to a point (frequency) estimate 1(ir) = Lij n~j logn:~:j for the mutual informat ion (per sample). [sent-54, score-0.31]

25 In the Bayesian approach to this problem one assumes a prior (second order) probability density p( 7r) for the unknown probabilities 7rij on the probability simplex. [sent-56, score-0.153]

26 From this one can compute the posterior distribution p( 7rln) cxp( 7r) rr ij7r~;j (the nij are multinomially distributed). [sent-57, score-0.619]

27 This allows to compute the posterior probability density of the mutual information. [sent-58, score-0.363]

28 1 p(Iln) = 2The 80 f 8(1(7r) - I)p(7rln)d TS 7r (2) distribution restricts the integral to 7r for which 1(7r) =1. [sent-59, score-0.07]

29 For large sam- 1 I(7r) denotes the mutual information for the specific chances 7r, whereas I in the context above is just some non-negative real number. [sent-60, score-0.322]

30 I will also denote the mutual information random variable in the expectation E [I] and variance Var[I]. [sent-61, score-0.397]

31 J:mam, pIe size n ---+ 00, p(7rln) is strongly peaked around 7r = it and p(Iln) gets strongly peaked around the frequency estimate I = I(it). [sent-67, score-0.349]

32 The mean E[I] = fooo Ip(Iln) dI = f I(7r)p(7rln)dTs 7r and the variance Var[I] =E[(I - E[I])2] = E[I2]- E[Ij2 are of central interest. [sent-68, score-0.334]

33 In principle this allows to compute the posterior density p(Iln) of the mutual information. [sent-71, score-0.363]

34 In sections 4 and 5 we expand the mean and variance in terms of n- 1 : E[I] ~ nij I nijn L. [sent-72, score-0.841]

35 n ni+n+j 'J + (r - 1)(8 - 1) 2n + O( -2) n , (3) Var[I] The first term for the mean is just the point estimate I(it). [sent-77, score-0.156]

36 The second term is a small correction if n » r· 8. [sent-78, score-0.09]

37 The expression 2E[I]/n they determined for the variance has a completely different structure than ours. [sent-81, score-0.245]

38 +O(n- 2 ), which is strictly positive for large, but finite sample sizes, even if z and J are statistically independent and independence is perfectly represented in the data (I (it) = 0). [sent-83, score-0.084]

39 On the other hand, in this case, the standard deviation u= y'Var(I) '" ~ ",E[I] correctly indicates that the mean is still consistent with zero. [sent-84, score-0.082]

40 Our approximations (3) for the mean and variance are good if T~8 is small. [sent-85, score-0.263]

41 The central limit theorem ensures that p(Iln) converges to a Gaussian distribution with mean E[I] and variance Var[I]. [sent-86, score-0.351]

42 Since I is non-negative it is more appropriate to approximate p(II7r) as a Gamma (= scaled X2 ) or log-normal distribution with mean E[I] and variance Var[I], which is of course also asymptotically correct. [sent-87, score-0.275]

43 A systematic expansion in n -1 of the mean, variance, and higher moments is possible but gets arbitrarily cumbersome. [sent-88, score-0.331]

44 The O(n - 2) terms for the variance and leading order terms for the skewness and kurtosis are given in Section 7. [sent-89, score-0.82]

45 For the mean it is possible to give an exact expression 1 E[I] = - L nij[1jJ(nij + 1) -1jJ(ni+ + 1) -1jJ(n+j + 1) + 1jJ(n + 1)] n . [sent-90, score-0.271]

46 See Section 6 for details and more general expressions for 1jJ for non-integer arguments. [sent-93, score-0.081]

47 There may be other prior information available which cannot be comprised in a Dirichlet distribution. [sent-94, score-0.124]

48 In this general case, the mean and variance of I can still be 3But not all priors which one can argue to be non-informative lead to Dirichlet posteriors. [sent-95, score-0.312]

49 Brand [Bragg] (and others), for instance, advocate the entropic prior p( 7r) ex e-H(rr). [sent-96, score-0.165]

50 4 Approximation of Expectation and Variance of I In the following let fr ij := E[7fij]. [sent-98, score-0.203]

51 Since p( 7fln) is strongly peaked around 7f = fr for large n we may expand J(7f) around fr in the integrals for the mean and the variance. [sent-99, score-0.498]

52 ij :=7fij -frij and using L: ij7fij = 1 = L:ijfrij we get for the expansion of (1) fr . [sent-102, score-0.329]

53 kd = Cov( 7fij ,7fkl) are the covariance of 7f under distribution p(7fln) and are proportional to n- 1 . [sent-130, score-0.094]

54 ( A) [ EJ ] = J7f +-~ (bikbjl - -A- - -A- COV7fij,7fkl ) +On 2 ijkl 7fij 7fi+ 7f+j The Kronecker delta bij is 1 for i = j and order in n - 1 is a otherwise. [sent-135, score-0.081]

55 (6) The variance of J in leading (7) where :t means = up to terms of order n -2. [sent-136, score-0.4]

56 So the leading order variance and the leading and next to leading order mean of the mutual information J(7f) can be expressed in terms of the covariance of 7f under the posterior distribution p(7fln). [sent-137, score-1.277]

57 5 The Second Order Dirichlet Distribution Noninformative priors for p(7f) are commonly used if no additional prior information is available. [sent-138, score-0.164]

58 Many non-informative choices (uniform, Jeffreys' , Haldane's, Perks', prior) lead to a Dirichlet posterior distribution: II 1 n;j N(n) . [sent-139, score-0.116]

59 7fij - 1 b ( 7f++ - 1) with normalization 2J N(n) (8) where r is the Gamma function, and nij = n~j + n~j, where n~j are the number of samples (i,j), and n~j comprises prior information (1 for the uniform prior, ~ for Jeffreys' prior, a for Haldane's prior, -! [sent-141, score-0.62]

60 Strictly speaking we should expand n~l = ~+0(n-2), i. [sent-146, score-0.06]

61 drop the +1, but the exact expression (9) for the covariance suggests to keep the +1. [sent-148, score-0.241]

62 We compared both versions with the exact values (from Monte-Carlo simulations) for various parameters 7r. [sent-149, score-0.095]

63 In most cases the expansion in n~l was more accurate, so we suggest to use this variant. [sent-150, score-0.071]

64 6 Exact Value for E[I] It is possible to get an exact expression for the mean mutual information E[I] under the Dirichlet distribution. [sent-151, score-0.572]

65 By noting that xlogx= d~x,6I,6= l' (x = {7rij,7ri+ ,7r+j}), one can replace the logarithms in the last expression of (1) by powers. [sent-152, score-0.119]

66 Taking the derivative and setting ,8 = 1 we get E[7rij log 7rij] d 1 = d,8E[(7rij) ,6],6=l = ;;: 2:::: nij[1j! [sent-154, score-0.091]

67 n J Inserting this into (1) and rearranging terms we get the exact expression 4 E[I] 1 =- L nij[1j! [sent-167, score-0.276]

68 4This expression has independently been derived in [WW93]. [sent-173, score-0.094]

69 (15) For large sample sizes, 'Ij;(z + 1) ~ logz and (15) approaches the frequency estimate I(7r) as it should be. [sent-174, score-0.194]

70 into (15) we also get the correction term (r - 11~s - 1) of (3). [sent-178, score-0.145]

71 2\ The presented method (with some refinements) may also be used to determine an exact expression for the variance of I(7f). [sent-179, score-0.34]

72 All but one term can be expressed in terms of Gamma functions. [sent-180, score-0.074]

73 7 Generalizations A systematic expansion of all moments of p(Iln) to arbitrary order in n -1 is possible, but gets soon quite cumbersome. [sent-186, score-0.332]

74 For the mean we already gave an exact expression (15), so we concentrate here on the variance, skewness and the kurtosis of p(Iln). [sent-187, score-0.687]

75 The 3rd and 4th central moments of 7f under the Dirichlet distribution are ( )2( ) [27ra7rb7rc - 7ra7rbc5bc - 7rb7rcc5ca - 7rc7rac5ab n+l n+2 + 7rac5abc5bc] (16) ~2 [37ra7rb7rc7rd - jrc! [sent-188, score-0.242]

76 They allow to compute the order n- 2 term of the variance of I(7f). [sent-221, score-0.289]

77 Again, inspection of (16) suggests to expand in [(n+l)(n+2)]-1, rather than in n- 2 . [sent-222, score-0.06]

78 The variance in leading and next to leading order is K - J2 + M + (r - 1)(8 - 1)(~ - J) - Q + O(n - 3) (n + l)(n + 2) n+ 1 M (18) L Var[I] (19) ij (~- _1 _ _ 1 _ _ nij ni+ n+j +~) nij log nijn , n ni+n+j 2 l-L~· Q ij ni+n+j (20) J and K are defined in (12) and (13). [sent-223, score-1.675]

79 Note that the first term ~+f also contains second order terms when expanded in n -1. [sent-224, score-0.163]

80 The leading order terms for the 3rd and 4th central moments of p(Iln) are L . [sent-225, score-0.449]

81 - '""" nij ~- j I og--nij n n 32 [K - J 2 n ni+n+j F+ O(n - 3 ), from which the skewness and kurtosis can be obtained by dividing by Var[Ij3/2 and Var[IF respectively. [sent-226, score-0.819]

82 One can see that the skewness is of order n- 1 / 2 and the kurtosis is 3 + 0 (n - 1). [sent-227, score-0.444]

83 Significant deviation of the skewness from a or the kurtosis from 3 would indicate a non-Gaussian I. [sent-228, score-0.388]

84 They can be used to get an improved approximation for p(Iln) by making, for instance, an ansatz and fitting the parameters b, c, jJ" and (j-2 to the mean, variance, skewness, and kurtosis expressions above. [sent-229, score-0.321]

85 Po is the Normal or Gamma distribution (or any other distribution with Gaussian limit). [sent-230, score-0.084]

86 A systematic expansion of arbitrarily high moments to arbitrarily high order in n- 1 leads, in principle, to arbitrarily accurate estimates. [sent-232, score-0.494]

87 Hence, the computation time for the (central) moments is of the same order O(r·s) as for the point estimate (1). [sent-237, score-0.212]

88 See [PFTV92] how to sample from a Gamma distribution. [sent-240, score-0.056]

89 The variance has been expanded in T~S, so the relative error Var [I]app" o. [sent-241, score-0.184]

90 act of the approximation (11) and (18) are of the order of T'S and Var[Il e• act n (T~S)2 respectively, if z and J are dependent. [sent-244, score-0.056]

91 If they are independent the leading term (11) drops itself down to order n -2 resulting in a reduced relative accuracy O( T~S) of (18). [sent-245, score-0.296]

92 Together with the skewness and kurtosis we have a good description for the distribution of the mutual information p(Iln) for not too small sample bin sizes nij' We want to conclude with some notes on useful accuracy. [sent-251, score-0.776]

93 Since the central moments are expansions in n- 1 , the next to leading order term can be freely adjusted by adjusting n~j E [0 . [sent-254, score-0.459]

94 So one may argue that anything beyond leading order is free to will, and the leading order terms may be regarded as accurate as we can specify our prior knowledge. [sent-258, score-0.623]

95 On the other hand, exact expressions have the advantage of being safe against cancellations. [sent-259, score-0.176]

96 For instance, leading order of E [I] and E[I2] does not suffice to compute the leading order of Var[I]. [sent-260, score-0.474]

97 Structure learning in conditional probability models via an entropic prior and parameter extinction. [sent-273, score-0.165]

98 Learning Bayesian networks under the control of mutual information. [sent-305, score-0.246]

99 The posterior probability of Bayes nets with strong dependences. [sent-310, score-0.128]

100 Estimating functions of distributions from A finite set of samples, part 2: Bayes estimators for mutual information, chisquared, covariance and other statistics. [sent-333, score-0.298]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('iln', 0.438), ('nij', 0.431), ('mutual', 0.246), ('var', 0.232), ('skewness', 0.203), ('dirichlet', 0.191), ('kurtosis', 0.185), ('leading', 0.161), ('variance', 0.151), ('prior', 0.124), ('gamma', 0.124), ('moments', 0.124), ('ni', 0.117), ('fr', 0.108), ('ij', 0.095), ('exact', 0.095), ('expression', 0.094), ('haldane', 0.088), ('perks', 0.088), ('mean', 0.082), ('expressions', 0.081), ('posterior', 0.077), ('central', 0.076), ('marcus', 0.076), ('chances', 0.076), ('expansion', 0.071), ('jeffreys', 0.065), ('expand', 0.06), ('imax', 0.058), ('kleiter', 0.058), ('nijn', 0.058), ('soooo', 0.058), ('inserting', 0.058), ('bayesian', 0.057), ('order', 0.056), ('sample', 0.056), ('arbitrarily', 0.055), ('peaked', 0.055), ('get', 0.055), ('frequency', 0.055), ('covariance', 0.052), ('nets', 0.051), ('logn', 0.051), ('logz', 0.051), ('xij', 0.051), ('correction', 0.048), ('og', 0.046), ('systematic', 0.045), ('instance', 0.044), ('sizes', 0.044), ('term', 0.042), ('distribution', 0.042), ('utilizing', 0.041), ('entropic', 0.041), ('priors', 0.04), ('carlo', 0.04), ('monte', 0.04), ('questions', 0.04), ('compute', 0.04), ('lead', 0.039), ('answer', 0.039), ('comprises', 0.039), ('numerical', 0.038), ('drops', 0.037), ('computable', 0.037), ('log', 0.036), ('gets', 0.036), ('validity', 0.034), ('expanded', 0.033), ('accurate', 0.033), ('estimate', 0.032), ('ion', 0.032), ('ab', 0.032), ('terms', 0.032), ('strongly', 0.031), ('dependency', 0.03), ('indices', 0.03), ('approximations', 0.03), ('rr', 0.029), ('reliable', 0.029), ('theoretic', 0.029), ('probabilities', 0.029), ('concentrate', 0.028), ('integral', 0.028), ('strictly', 0.028), ('ir', 0.027), ('sections', 0.027), ('double', 0.027), ('around', 0.027), ('samples', 0.026), ('logarithms', 0.025), ('app', 0.025), ('noninformative', 0.025), ('fooo', 0.025), ('brand', 0.025), ('dz', 0.025), ('abramowitz', 0.025), ('bij', 0.025), ('dover', 0.025), ('ecipes', 0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999964 61 nips-2001-Distribution of Mutual Information

Author: Marcus Hutter

2 0.10812561 68 nips-2001-Entropy and Inference, Revisited

Author: Ilya Nemenman, F. Shafee, William Bialek

Abstract: We study properties of popular near–uniform (Dirichlet) priors for learning undersampled probability distributions on discrete nonmetric spaces and show that they lead to disastrous results. However, an Occam–style phase space argument expands the priors into their inﬁnite mixture and resolves most of the observed problems. This leads to a surprisingly good estimator of entropies of discrete distributions. Learning a probability distribution from examples is one of the basic problems in data analysis. Common practical approaches introduce a family of parametric models, leading to questions about model selection. In Bayesian inference, computing the total probability of the data arising from a model involves an integration over parameter space, and the resulting “phase space volume” automatically discriminates against models with larger numbers of parameters—hence the description of these volume terms as Occam factors [1, 2]. As we move from ﬁnite parameterizations to models that are described by smooth functions, the integrals over parameter space become functional integrals and methods from quantum ﬁeld theory allow us to do these integrals asymptotically; again the volume in model space consistent with the data is larger for models that are smoother and hence less complex [3]. Further, at least under some conditions the relevant degree of smoothness can be determined self–consistently from the data, so that we approach something like a model independent method for learning a distribution [4]. The results emphasizing the importance of phase space factors in learning prompt us to look back at a seemingly much simpler problem, namely learning a distribution on a discrete, nonmetric space. Here the probability distribution is just a list of numbers {q i }, i = 1, 2, · · · , K, where K is the number of bins or possibilities. We do not assume any metric on the space, so that a priori there is no reason to believe that any q i and qj should be similar. The task is to learn this distribution from a set of examples, which we can describe as the number of times ni each possibility is observed in a set of N = K ni i=1 samples. This problem arises in the context of language, where the index i might label words or phrases, so that there is no natural way to place a metric on the space, nor is it even clear that our intuitions about similarity are consistent with the constraints of a metric space. Similarly, in bioinformatics the index i might label n–mers of the the DNA or amino acid sequence, and although most work in the ﬁeld is based on metrics for sequence comparison one might like an alternative approach that does not rest on such assumptions. In the analysis of neural responses, once we ﬁx our time resolution the response becomes a set of discrete “words,” and estimates of the information content in the response are de- termined by the probability distribution on this discrete space. What all of these examples have in common is that we often need to draw some conclusions with data sets that are not in the asymptotic limit N K. Thus, while we might use a large corpus to sample the distribution of words in English by brute force (reaching N K with K the size of the vocabulary), we can hardly do the same for three or four word phrases. In models described by continuous functions, the inﬁnite number of “possibilities” can never be overwhelmed by examples; one is saved by the notion of smoothness. Is there some nonmetric analog of this notion that we can apply in the discrete case? Our intuition is that information theoretic quantities may play this role. If we have a joint distribution of two variables, the analog of a smooth distribution would be one which does not have too much mutual information between these variables. Even more simply, we might say that smooth distributions have large entropy. While the idea of “maximum entropy inference” is common [5], the interplay between constraints on the entropy and the volume in the space of models seems not to have been considered. As we shall explain, phase space factors alone imply that seemingly sensible, more or less uniform priors on the space of discrete probability distributions correspond to disastrously singular prior hypotheses about the entropy of the underlying distribution. We argue that reliable inference outside the asymptotic regime N K requires a more uniform prior on the entropy, and we offer one way of doing this. While many distributions are consistent with the data when N ≤ K, we provide empirical evidence that this ﬂattening of the entropic prior allows us to make surprisingly reliable statements about the entropy itself in this regime. At the risk of being pedantic, we state very explicitly what we mean by uniform or nearly uniform priors on the space of distributions. The natural “uniform” prior is given by Pu ({qi }) = 1 δ Zu K 1− K qi i=1 , Zu = A dq1 dq2 · · · dqK δ 1− qi (1) i=1 where the delta function imposes the normalization, Zu is the total volume in the space of models, and the integration domain A is such that each qi varies in the range [0, 1]. Note that, because of the normalization constraint, an individual q i chosen from this distribution in fact is not uniformly distributed—this is also an example of phase space effects, since in choosing one qi we constrain all the other {qj=i }. What we mean by uniformity is that all distributions that obey the normalization constraint are equally likely a priori. Inference with this uniform prior is straightforward. If our examples come independently from {qi }, then we calculate the probability of the model {qi } with the usual Bayes rule: 1 K P ({qi }|{ni }) = P ({ni }|{qi })Pu ({qi }) , P ({ni }|{qi }) = (qi )ni . Pu ({ni }) i=1 (2) If we want the best estimate of the probability qi in the least squares sense, then we should compute the conditional mean, and this can be done exactly, so that [6, 7] qi = ni + 1 . N +K (3) Thus we can think of inference with this uniform prior as setting probabilities equal to the observed frequencies, but with an “extra count” in every bin. This sensible procedure was ﬁrst introduced by Laplace [8]. It has the desirable property that events which have not been observed are not automatically assigned probability zero. 1 If the data are unordered, extra combinatorial factors have to be included in P ({ni }|{qi }). However, these cancel immediately in later expressions. A natural generalization of these ideas is to consider priors that have a power–law dependence on the probabilities, the so called Dirichlet family of priors: K Pβ ({qi }) = 1 δ 1− qi Z(β) i=1 K β−1 qi , (4) i=1 It is interesting to see what typical distributions from these priors look like. Even though different qi ’s are not independent random variables due to the normalizing δ–function, generation of random distributions is still easy: one can show that if q i ’s are generated successively (starting from i = 1 and proceeding up to i = K) from the Beta–distribution j

3 0.10071568 195 nips-2001-Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning

Author: Evan Greensmith, Peter L. Bartlett, Jonathan Baxter

Abstract: We consider the use of two additive control variate methods to reduce the variance of performance gradient estimates in reinforcement learning problems. The ﬁrst approach we consider is the baseline method, in which a function of the current state is added to the discounted value estimate. We relate the performance of these methods, which use sample paths, to the variance of estimates based on iid data. We derive the baseline function that minimizes this variance, and we show that the variance for any baseline is the sum of the optimal variance and a weighted squared distance to the optimal baseline. We show that the widely used average discounted value baseline (where the reward is replaced by the difference between the reward and its expectation) is suboptimal. The second approach we consider is the actor-critic method, which uses an approximate value function. We give bounds on the expected squared error of its estimates. We show that minimizing distance to the true value function is suboptimal in general; we provide an example for which the true value function gives an estimate with positive variance, but the optimal value function gives an unbiased estimate with zero variance. Our bounds suggest algorithms to estimate the gradient of the performance of parameterized baseline or value functions. We present preliminary experiments that illustrate the performance improvements on a simple control problem. 1 Introduction, Background, and Preliminary Results In reinforcement learning problems, the aim is to select a controller that will maximize the average reward in some environment. We model the environment as a partially observable Markov decision process (POMDP). Gradient ascent methods (e.g., [7, 12, 15]) estimate the gradient of the average reward, usually using Monte Carlo techniques to cal∗ Most of this work was performed while the authors were with the Research School of Information Sciences and Engineering at the Australian National University. culate an average over a sample path of the controlled POMDP. However such estimates tend to have a high variance, which means many steps are needed to obtain a good estimate. GPOMDP [4] is an algorithm for generating an estimate of the gradient in this way. Compared with other approaches, it is suitable for large systems, when the time between visits to a state is large but the mixing time of the controlled POMDP is short. However, it can suffer from the problem of producing high variance estimates. In this paper, we investigate techniques for variance reduction in GPOMDP. One generic approach to reducing the variance of Monte Carlo estimates of integrals is to use an additive control variate (see, for example, [6]). Suppose we wish to estimate the integral of f : X → R, and we know the integral of another function ϕ : X → R. Since X f = X (f − ϕ) + X ϕ, the integral of f − ϕ can be estimated instead. Obviously if ϕ = f then the variance is zero. More generally, Var(f − ϕ) = Var(f ) − 2Cov(f, ϕ) + Var(ϕ), so that if φ and f are strongly correlated, the variance of the estimate is reduced. In this paper, we consider two approaches of this form. The ﬁrst (Section 2) is the technique of adding a baseline. We ﬁnd the optimal baseline and we show that the additional variance of a suboptimal baseline can be expressed as a weighted squared distance from the optimal baseline. Constant baselines, which do not depend on the state or observations, have been widely used [13, 15, 9, 11]. In particular, the expectation over all states of the discounted value of the state is a popular constant baseline (where, for example, the reward at each step is replaced by the difference between the reward and the expected reward). We give bounds on the estimation variance that show that, perhaps surprisingly, this may not be the best choice. The second approach (Section 3) is the use of an approximate value function. Such actorcritic methods have been investigated extensively [3, 1, 14, 10]. Generally the idea is to minimize some notion of distance between the ﬁxed value function and the true value function. In this paper we show that this may not be the best approach: selecting the ﬁxed value function to be equal to the true value function is not always the best choice. Even more surprisingly, we give an example for which the use of a ﬁxed value function that is different from the true value function reduces the variance to zero, for no increase in bias. We give a bound on the expected squared error (that is, including the estimation variance) of the gradient estimate produced with a ﬁxed value function. Our results suggest new algorithms to learn the optimum baseline, and to learn a ﬁxed value function that minimizes the bound on the error of the estimate. In Section 5, we describe the results of preliminary experiments, which show that these algorithms give performance improvements. POMDP with Reactive, Parameterized Policy A partially observable Markov decision process (POMDP) consists of a state space, S, a control space, U, an observation space, Y, a set of transition probability matrices {P(u) : u ∈ U}, each with components pij (u) for i, j ∈ S, u ∈ U, an observation process ν : S → PY , where PY is the space of probability distributions over Y, and a reward function r : S → R. We assume that S, U, Y are ﬁnite, although all our results extend easily to inﬁnite U and Y, and with more restrictive assumptions can be extended to inﬁnite S. A reactive, parameterized policy for a POMDP is a set of mappings {µ(·, θ) : Y → PU |θ ∈ RK }. Together with the POMDP, this deﬁnes the controlled POMDP (S, U, Y, P , ν, r, µ). The joint state, observation and control process, {Xt , Yt , Ut }, is Markov. The state process, {Xt }, is also Markov, with transition probabilities pij (θ) = y∈Y,u∈U νy (i)µu (y, θ)pij (u), where νy (i) denotes the probability of observation y given the state i, and µu (y, θ) denotes the probability of action u given parameters θ and observation y. The Markov chain M(θ) = (S, P(θ)) then describes the behaviour of the process {Xt }. Assumption 1 The controlled POMDP (S, U, Y, P , ν, r, µ) satisﬁes: For all θ ∈ RK there exists a unique stationary distribution satisfying π (θ) P(θ) = π (θ). There is an R < ∞ such that, for all i ∈ S, |r(i)| ≤ R. There is a B < ∞ such that, for all u ∈ U, y ∈ Y and θ ∈ RK the derivatives ∂µu (y, θ)/∂θk (1 ≤ k ≤ K) exist, and the vector of these derivatives satisﬁes µu (y, θ)/µu (y, θ) ≤ B, where · denotes the Euclidean norm on RK . def T −1 1 We consider the average reward, η(θ) = limT →∞ E T t=0 r(Xt ) . Assumption 1 implies that this limit exists, and does not depend on the start state X0 . The aim is to def select a policy to maximize this quantity. Deﬁne the discounted value function, J β (i, θ) = T −1 t limT →∞ E t=0 β r(Xt ) X0 = i . Throughout the rest of the paper, dependences upon θ are assumed, and dropped in the notation. For a random vector A, we denote Var(A) = E (A − E [A])2 , where a2 denotes a a, and a denotes the transpose of the column vector a. GPOMDP Algorithm The GPOMDP algorithm [4] uses a sample path to estimate the gradient approximation def µu(y) η, but the βη = E β η approaches the true gradient µu(y) Jβ (j) . As β → 1, def variance increases. We consider a slight modiﬁcation [2]: with Jt = def ∆T = 1 T T −1 t=0 2T s=t µUt (Yt ) Jt+1 . µUt (Yt ) β s−t r(Xs ), (1) Throughout this paper the process {Xt , Yt , Ut , Xt+1 } is generally understood to be generated by a controlled POMDP satisfying Assumption 1, with X0 ∼π (ie the initial state distributed according to the stationary distribution). That is, before computing the gradient estimates, we wait until the process has settled down to the stationary distribution. Dependent Samples Correlation terms arise in the variance quantities to be analysed. We show here that considering iid samples gives an upper bound on the variance of the general case. The mixing time of a ﬁnite ergodic Markov chain M = (S, P ) is deﬁned as def τ = min t > 1 : max dT V i,j Pt i , Pt j ≤ e−1 , where [P t ]i denotes the ith row of P t and dT V is the total variation distance, dT V (P, Q) = i |P (i) − Q(i)|. Theorem 1 Let M = (S, P ) be a ﬁnite ergodic Markov chain, with mixing time τ , and 2|S|e and 0 ≤ α < let π be its stationary distribution. There are constants L < exp(−1/(2τ )), which depend only on M , such that, for all f : S → R and all t, Covπ (t) ≤ Lαt Varπ (f), where Varπ (f) is the variance of f under π, and Covπ (t) is f f the auto-covariance of the process {f(Xt )}, where the process {Xt } is generated by M with initial distribution π. Hence, for some constant Ω∗ ≤ 4Lτ , Var 1 T T −1 f(Xt ) t=0 ≤ Ω∗ Varπ (f). T We call (L, τ ) the mixing constants of the Markov chain M (or of the controlled POMDP D; ie the Markov chain (S, P )). We omit the proof (all proofs are in the full version [8]). Brieﬂy, we show that for a ﬁnite ergodic Markov chain M , Covπ (t) ≤ Rt (M )Varπ (f), f 2 t for some Rt (M ). We then show that Rt (M ) < 2|S| exp(− τ ). In fact, for a reversible chain, we can choose L = 1 and α = |λ2 |, the second largest magnitude eigenvalue of P . 2 Baseline We consider an alteration of (1), def ∆T = 1 T T −1 µUt (Yt ) (Jt+1 − Ar (Yt )) . µUt (Yt ) t=0 (2) For any baseline Ar : Y → R, it is easy to show that E [∆T ] = E [∆T ]. Thus, we select Ar to minimize variance. The following theorem shows that this variance is bounded by a variance involving iid samples, with Jt replaced by the exact value function. Theorem 2 Suppose that D = (S, U, Y, P , ν, r, µ) is a controlled POMDP satisfying Assumption 1, D has mixing constants (L, τ ), {Xt , Yt , Ut , Xt+1 } is a process generated by D with X0 ∼π ,Ar : Y → R is a baseline that is uniformly bounded by M, and J (j) has the distribution of ∞ β s r(Xt ), where the states Xt are generated by D starting in s=0 X0 = j. Then there are constants C ≤ 5B2 R(R + M) and Ω ≤ 4Lτ ln(eT ) such that Var 1 T T −1 t=0 µUt (Yt ) Ω (Jt+1 −Ar (Yt )) ≤ Varπ µUt (Yt ) T + Ω E T µu (y) (J (j) − Jβ (j)) µu (y) µu (y) (Jβ (j)−Ar (y)) µu (y) 2 + Ω +1 T C βT , (1 − β)2 where, as always, (i, y, u, j) are generated iid with i∼π, y∼ν(i), u∼µ(y) and j∼P i (u). The proof uses Theorem 1 and [2, Lemma 4.3]. Here we have bounded the variance of (2) with the variance of a quantity we may readily analyse. The second term on the right hand side shows the error associated with replacing an unbiased, uncorrelated estimate of the value function with the true value function. This quantity is not dependent on the baseline. The ﬁnal term on the right hand side arises from the truncation of the discounted reward— and is exponentially decreasing. We now concentrate on minimizing the variance σ 2 = Varπ r µu (y) (Jβ (j) − Ar (y)) , µu (y) (3) which the following lemma relates to the variance σ 2 without a baseline, µu (y) Jβ (j) . µu (y) σ 2 = Varπ Lemma 3 Let D = (S, U, Y, P , ν, r, µ) be a controlled POMDP satisfying Assumption 1. For any baseline Ar : Y → R, and for i∼π, y∼ν(i), u∼µ(y) and j∼Pi (u), σ 2 = σ 2 + E A2 (y) E r r µu (y) µu (y) 2 y − 2Ar (y)E µu (y) µu (y) 2 Jβ (j) y . From Lemma 3 it can be seen that the task of ﬁnding the optimal baseline is in effect that of minimizing a quadratic for each observation y ∈ Y. This gives the following theorem. Theorem 4 For the controlled POMDP as in Lemma 3,  2 µu (y) min σ 2 = σ 2 − E  E Jβ (j) y r Ar µu (y) 2 /E µu (y) µu (y) 2 y and this minimum is attained with the baseline 2 µu (y) µu (y) A∗ (y) = E r Jβ (j) , 2 µu (y) µu (y) /E y  y . Furthermore, the optimal constant baseline is µu (y) µu (y) A∗ = E r 2 Jβ (j) /E µu (y) µu (y) 2 . The following theorem shows that the variance of an estimate with an arbitrary baseline can be expressed as the sum of the variance with the optimal baseline and a certain squared weighted distance between the baseline function and the optimal baseline function. Theorem 5 If Ar : Y → R is a baseline function, A∗ is the optimal baseline deﬁned in r Theorem 4, and σ 2 is the variance of the corresponding estimate, then r∗ µu (y) µu (y) σ 2 = σ2 + E r r∗ 2 (Ar (y) − A∗ (y)) r 2 , where i∼π, y ∼ν(i), and u∼µ(y). Furthermore, the same result is true for the case of constant baselines, with Ar (y) replaced by an arbitrary constant baseline Ar , and A∗ (y) r replaced by A∗ , the optimum constant baseline deﬁned in Theorem 4. r For the constant baseline Ar = E i∼π [Jβ (i)], Theorem 5 implies that σ 2 is equal to r min Ar ∈R σ2 r + E µu (y) µu (y) 2 E [Jβ (j)] − E µu (y) µu (y) 2 2 /E Jβ (j) µu (y) µu (y) 2 . Thus, its performance depends on the random variables ( µu (y)/µu (y))2 and Jβ (j); if they are nearly independent, E [Jβ ] is a good choice. 3 Fixed Value Functions: Actor-Critic Methods We consider an alteration of (1), ˜ def 1 ∆T = T T −1 t=0 µUt (Yt ) ˜ Jβ (Xt+1 ), µUt (Yt ) (4) ˜ for some ﬁxed value function Jβ : S → R. Deﬁne ∞ def β k d(Xk , Xk+1 ) Aβ (j) = E X0 = j , k=0 def ˜ ˜ where d(i, j) = r(i) + β Jβ (j) − Jβ (i) is the temporal difference. Then it is easy to show that the estimate (4) has a bias of µu (y) ˜ Aβ (j) . β η − E ∆T = E µu (y) The following theorem gives a bound on the expected squared error of (4). The main tool in the proof is Theorem 1. Theorem 6 Let D = (S, U, Y, P , ν, r, µ) be a controlled POMDP satisfying Assumption 1. For a sample path from D, that is, {X0∼π, Yt∼ν(Xt ), Ut∼µ(Yt ), Xt+1∼PXt (Ut )}, E ˜ ∆T − βη 2 ≤ Ω∗ Varπ T µu (y) ˜ Jβ (j) + E µu (y) µu (y) Aβ (j) µu (y) 2 , where the second expectation is over i∼π, y∼ν(i), u∼µ(y), and j∼P i (u). ˜ If we write Jβ (j) = Jβ (j) + v(j), then by selecting v = (v(1), . . . , v(|S|)) from the right def null space of the K × |S| matrix G, where G = i,y,u πi νy (i) µu (y)Pi (u), (4) will produce an unbiased estimate of β η. An obvious example of such a v is a constant vector, (c, c, . . . , c) : c ∈ R. We can use this to construct a trivial example where (4) produces an unbiased estimate with zero variance. Indeed, let D = (S, U, Y, P , ν, r, µ) be a controlled POMDP satisfying Assumption 1, with r(i) = c, for some 0 < c ≤ R. Then Jβ (j) = c/(1 − β) and β η = 0. If we choose v = (−c/(1 − β), . . . , −c/(1 − β)) and ˜ ˜ Jβ (j) = Jβ (j) + v(j), then µµu(y) Jβ (j) = 0 for all y, u, j, and so (4) gives an unbiased u(y) estimate of β η, with zero variance. Furthermore, for any D for which there exists a pair y, u such that µu (y) > 0 and µu (y) = 0, choosing ˜β (j) = Jβ (j) gives a variance J greater than zero—there is a non-zero probability event, (Xt = i, Yt = y, Ut = u, Xt+1 = j), such that µµu(y) Jβ (j) = 0. u(y) 4 Algorithms Given a parameterized class of baseline functions Ar (·, θ) : Y → R θ ∈ RL , we can use Theorem 5 to bound the variance of our estimates. Computing the gradient of this bound with respect to the parameters θ of the baseline function allows a gradient optimization of the baseline. The GDORB Algorithm produces an estimate ∆ S of these gradients from a sample path of length S. Under the assumption that the baseline function and its gradients are uniformly bounded, we can show that these estimates converge to the gradient of σ 2 . We omit the details (see [8]). r GDORB Algorithm: Given: Controlled POMDP (S, U, Y, P , ν, r, µ), parameterized baseline Ar . set z0 = 0 (z0 ∈ RL ), ∆0 = 0 (∆0 ∈ RL ) for all {is , ys , us , is+1 , ys+1 } generated by the POMDP do zs+1 = βzs + ∆s+1 = ∆s + end for Ar (ys ) 1 s+1 µus(ys ) µus(ys ) 2 ((Ar (ys ) − βAr (ys+1 ) − r(xs+1 )) zs+1 − ∆s ) ˜ For a parameterized class of ﬁxed value functions {Jβ (·, θ) : S → R θ ∈ RL }, we can use Theorem 6 to bound the expected squared error of our estimates, and compute the gradient of this bound with respect to the parameters θ of the baseline function. The GBTE Algorithm produces an estimate ∆S of these gradients from a sample path of length S. Under the assumption that the value function and its gradients are uniformly bounded, we can show that these estimates converge to the true gradient. GBTE Algorithm: Given: Controlled POMDP (S, U, Y, P , ν, r, µ), parameterized ﬁxed value function ˜β . J set z0 = 0 (z0 ∈ RK ), ∆A0 = 0 (∆A0 ∈ R1×L ), ∆B 0 = 0 (∆B 0 ∈ RK ), ∆C 0 = 0 (∆C 0 ∈ RK ) and ∆D0 = 0 (∆D0 ∈ RK×L ) for all {is , ys , us , is+1 , is+2 } generated by the POMDP do µ s(y ) zs+1 = βzs + µuu(yss ) s µus(ys ) ˜ µus(ys ) Jβ (is+1 ) µus(ys ) µus(ys ) ˜ Jβ (is+1 ) ∆As+1 = ∆As + 1 s+1 ∆B s+1 = ∆B s + 1 s+1 µus(ys ) ˜ µus(ys ) Jβ (is+1 ) ∆C s+1 = ∆C s + 1 s+1 ˜ ˜ r(is+1 ) + β Jβ (is+2 ) − Jβ (is+1 ) zs+1 − ∆C s ∆Ds+1 = ∆Ds + 1 s+1 µus(ys ) µus(ys ) ∆s+1 = end for Ω∗ T ∆As+1 − − ∆B s ˜ Jβ (is+1 ) Ω∗ T ∆B s+1 ∆D s+1 − ∆As − ∆D s − ∆C s+1 ∆Ds+1 5 Experiments Experimental results comparing these GPOMDP variants for a simple three state MDP (described in [5]) are shown in Figure 1. The exact value function plots show how different choices of baseline and ﬁxed value function compare when all algorithms have access to the exact value function Jβ . Using the expected value function as a baseline was an improvement over GPOMDP. Using the optimum, or optimum constant, baseline was a further improvement, each performing comparably to the other. Using the pre-trained ﬁxed value function was also an improvement over GPOMDP, showing that selecting the true value function was indeed not the best choice in this case. The trained ﬁxed value function was not optimal though, as Jβ (j) − A∗ is a valid choice of ﬁxed value function. r The optimum baseline, and ﬁxed value function, will not normally be known. The online plots show experiments where the baseline and ﬁxed value function were trained using online gradient descent whilst the performance gradient was being estimated, using the same data. Clear improvement over GPOMDP is seen for the online trained baseline variant. For the online trained ﬁxed value function, improvement is seen until T becomes—given the simplicity of the system—very large. References [1] L. Baird and A. Moore. Gradient descent for general reinforcement learning. In Advances in Neural Information Processing Systems 11, pages 968–974. MIT Press, 1999. [2] P. L. Bartlett and J. Baxter. Estimation and approximation bounds for gradient-based reinforcement learning. Journal of Computer and Systems Sciences, 2002. To appear. [3] A. G. Barto, R. S. Sutton, and C. W. Anderson. Neuronlike adaptive elements that can solve difﬁcult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13:834–846, 1983. [4] J. Baxter and P. L. Bartlett. Inﬁnite-horizon gradient-based policy search. Journal of Artiﬁcial Intelligence Research, 15:319–350, 2001. [5] J. Baxter, P. L. Bartlett, and L. Weaver. Inﬁnite-horizon gradient-based policy search: II. Gradient ascent algorithms and experiments. Journal of Artiﬁcial Intelligence Research, 15:351–381, 2001. [6] M. Evans and T. Swartz. Approximating integrals via Monte Carlo and deterministic methods. Oxford University Press, 2000. Exact Value Function—Mean Error Exact Value Function—One Standard Deviation 0.4 0.4 GPOMDP-Jβ BL- [Jβ ] BL-A∗ (y) r BL-A∗ r FVF-pretrain Relative Norm Difference Relative Norm Difference 0.25 GPOMDP-Jβ BL- [Jβ ] BL-A∗ (y) r BL-A∗ r FVF-pretrain 0.35 0.3 0.2 0.15 0.1 0.05 ¡ 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 0 1 10 100 1000 10000 100000 1e+06 1e+07 1 10 100 1000 T Online—Mean Error 100000 1e+06 1e+07 Online—One Standard Deviation 1 1 GPOMDP BL-online FVF-online 0.8 Relative Norm Difference Relative Norm Difference 10000 T 0.6 0.4 0.2 0 GPOMDP BL-online FVF-online 0.8 0.6 0.4 0.2 0 1 10 100 1000 10000 100000 1e+06 1e+07 1 10 100 T 1000 10000 100000 1e+06 1e+07 T Figure 1: Three state experiments—relative norm error ∆ est − η / η . Exact value function plots compare mean error and standard deviations for gradient estimates (with knowledge of Jβ ) computed by: GPOMDP [GPOMDP-Jβ ]; with baseline Ar = [Jβ ] [BL- [Jβ ]]; with optimum baseline [BL-A∗ (y)]; with optimum constant baseline [BL-A∗ ]; with pre-trained ﬁxed value r r function [FVF-pretrain]. Online plots do a similar comparison of estimates computed by: GPOMDP [GPOMDP]; with online trained baseline [BL-online]; with online trained ﬁxed value function [FVFonline]. The plots were computed over 500 runs (1000 for FVF-online), with β = 0.95. Ω∗ /T was set to 0.001 for FVF-pretrain, and 0.01 for FVF-online. ¢ ¢ [7] P. W. Glynn. Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM, 33:75–84, 1990. [8] E. Greensmith, P. L. Bartlett, and J. Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. Technical report, ANU, 2002. [9] H. Kimura, K. Miyazaki, and S. Kobayashi. Reinforcement learning in POMDPs with function approximation. In D. H. Fisher, editor, Proceedings of the Fourteenth International Conference on Machine Learning (ICML’97), pages 152–160, 1997. [10] V. R. Konda and J. N. Tsitsiklis. Actor-Critic Algorithms. In Advances in Neural Information Processing Systems 12, pages 1008–1014. MIT Press, 2000. [11] P. Marbach and J. N. Tsitsiklis. Simulation-Based Optimization of Markov Reward Processes. Technical report, MIT, 1998. [12] R. Y. Rubinstein. How to optimize complex stochastic systems from a single sample path by the score function method. Ann. Oper. Res., 27:175–211, 1991. [13] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge MA, 1998. ISBN 0-262-19398-1. [14] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approximation. In Advances in Neural Information Processing Systems 12, pages 1057–1063. MIT Press, 2000. [15] R. J. Williams. Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning. Machine Learning, 8:229–256, 1992.

4 0.095603764 21 nips-2001-A Variational Approach to Learning Curves

Author: Dörthe Malzahn, Manfred Opper

Abstract: We combine the replica approach from statistical physics with a variational approach to analyze learning curves analytically. We apply the method to Gaussian process regression. As a main result we derive approximative relations between empirical error measures, the generalization error and the posterior variance.

5 0.091702871 95 nips-2001-Infinite Mixtures of Gaussian Process Experts

Author: Carl E. Rasmussen, Zoubin Ghahramani

Abstract: We present an extension to the Mixture of Experts (ME) model, where the individual experts are Gaussian Process (GP) regression models. Using an input-dependent adaptation of the Dirichlet Process, we implement a gating network for an inﬁnite number of Experts. Inference in this model may be done efﬁciently using a Markov Chain relying on Gibbs sampling. The model allows the effective covariance function to vary with the inputs, and may handle large datasets – thus potentially overcoming two of the biggest hurdles with GP models. Simulations show the viability of this approach.

6 0.087601632 43 nips-2001-Bayesian time series classification

7 0.085315257 165 nips-2001-Scaling Laws and Local Minima in Hebbian ICA

8 0.081046738 183 nips-2001-The Infinite Hidden Markov Model

9 0.078657329 109 nips-2001-Learning Discriminative Feature Transforms to Low Dimensions in Low Dimentions

10 0.07247933 114 nips-2001-Learning from Infinite Data in Finite Time

11 0.069643639 24 nips-2001-Active Information Retrieval

12 0.066144355 178 nips-2001-TAP Gibbs Free Energy, Belief Propagation and Sparsity

13 0.065763712 107 nips-2001-Latent Dirichlet Allocation

14 0.062366396 29 nips-2001-Adaptive Sparseness Using Jeffreys Prior

15 0.06193402 58 nips-2001-Covariance Kernels from Bayesian Generative Models

16 0.060740564 35 nips-2001-Analysis of Sparse Bayesian Learning

17 0.054775257 174 nips-2001-Spike timing and the coding of naturalistic sounds in a central auditory area of songbirds

18 0.053074773 79 nips-2001-Gaussian Process Regression with Mismatched Models

19 0.051249042 119 nips-2001-Means, Correlations and Bounds

20 0.048997872 127 nips-2001-Multi Dimensional ICA to Separate Correlated Sources

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.158), (1, -0.013), (2, -0.001), (3, -0.078), (4, -0.047), (5, -0.109), (6, 0.104), (7, 0.036), (8, -0.006), (9, -0.053), (10, 0.06), (11, 0.036), (12, -0.061), (13, -0.172), (14, -0.046), (15, 0.001), (16, 0.05), (17, 0.04), (18, 0.023), (19, -0.114), (20, -0.065), (21, 0.01), (22, -0.081), (23, -0.018), (24, 0.031), (25, -0.116), (26, -0.107), (27, 0.008), (28, 0.047), (29, 0.124), (30, -0.156), (31, 0.105), (32, -0.07), (33, 0.062), (34, -0.153), (35, 0.023), (36, -0.001), (37, 0.045), (38, 0.057), (39, 0.114), (40, -0.198), (41, 0.051), (42, -0.002), (43, -0.035), (44, 0.124), (45, -0.006), (46, 0.021), (47, -0.025), (48, 0.066), (49, 0.03)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96615112 61 nips-2001-Distribution of Mutual Information

Author: Marcus Hutter

2 0.7373507 68 nips-2001-Entropy and Inference, Revisited

Author: Ilya Nemenman, F. Shafee, William Bialek

3 0.52084321 21 nips-2001-A Variational Approach to Learning Curves

Author: Dörthe Malzahn, Manfred Opper

4 0.49497584 195 nips-2001-Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning

Author: Evan Greensmith, Peter L. Bartlett, Jonathan Baxter

5 0.4762862 95 nips-2001-Infinite Mixtures of Gaussian Process Experts

Author: Carl E. Rasmussen, Zoubin Ghahramani

6 0.47123387 43 nips-2001-Bayesian time series classification

7 0.43826208 178 nips-2001-TAP Gibbs Free Energy, Belief Propagation and Sparsity

8 0.43054721 165 nips-2001-Scaling Laws and Local Minima in Hebbian ICA

9 0.42597064 114 nips-2001-Learning from Infinite Data in Finite Time

10 0.41270635 79 nips-2001-Gaussian Process Regression with Mismatched Models

11 0.40602234 194 nips-2001-Using Vocabulary Knowledge in Bayesian Multinomial Estimation

12 0.35883871 109 nips-2001-Learning Discriminative Feature Transforms to Low Dimensions in Low Dimentions

13 0.35649088 99 nips-2001-Intransitive Likelihood-Ratio Classifiers

14 0.35456544 117 nips-2001-MIME: Mutual Information Minimization and Entropy Maximization for Bayesian Belief Propagation

15 0.34539813 174 nips-2001-Spike timing and the coding of naturalistic sounds in a central auditory area of songbirds

16 0.34505743 122 nips-2001-Model Based Population Tracking and Automatic Detection of Distribution Changes

17 0.3100864 183 nips-2001-The Infinite Hidden Markov Model

18 0.30209443 185 nips-2001-The Method of Quantum Clustering

19 0.2957086 57 nips-2001-Correlation Codes in Neuronal Populations

20 0.29366201 76 nips-2001-Fast Parameter Estimation Using Green's Functions

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(14, 0.037), (17, 0.03), (19, 0.025), (23, 0.271), (27, 0.119), (30, 0.042), (38, 0.028), (59, 0.048), (72, 0.108), (79, 0.059), (83, 0.018), (91, 0.135)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.82105029 61 nips-2001-Distribution of Mutual Information

Author: Marcus Hutter

2 0.63686395 29 nips-2001-Adaptive Sparseness Using Jeffreys Prior

Author: Mário Figueiredo

Abstract: In this paper we introduce a new sparseness inducing prior which does not involve any (hyper)parameters that need to be adjusted or estimated. Although other applications are possible, we focus here on supervised learning problems: regression and classiﬁcation. Experiments with several publicly available benchmark data sets show that the proposed approach yields state-of-the-art performance. In particular, our method outperforms support vector machines and performs competitively with the best alternative techniques, both in terms of error rates and sparseness, although it involves no tuning or adjusting of sparsenesscontrolling hyper-parameters.

3 0.63650107 95 nips-2001-Infinite Mixtures of Gaussian Process Experts

Author: Carl E. Rasmussen, Zoubin Ghahramani

4 0.63182753 157 nips-2001-Rates of Convergence of Performance Gradient Estimates Using Function Approximation and Bias in Reinforcement Learning

Author: Gregory Z. Grudic, Lyle H. Ungar

Abstract: We address two open theoretical questions in Policy Gradient Reinforcement Learning. The ﬁrst concerns the efﬁcacy of using function approximation to represent the state action value function, . Theory is presented showing that linear function approximation representations of can degrade the rate of convergence of performance gradient estimates by a factor of relative to when no function approximation of is used, where is the number of possible actions and is the number of basis functions in the function approximation representation. The second concerns the use of a bias term in estimating the state action value function. Theory is presented showing that a non-zero bias term can improve the rate of convergence of performance gradient estimates by , where is the number of possible actions. Experimental evidence is presented showing that these theoretical results lead to signiﬁcant improvement in the convergence properties of Policy Gradient Reinforcement Learning algorithms. ¤ ¨ ¦ ¢ ©§¥¤£¡ ¦ ¤ ¨ £¡ ¨ ¤¢ ¢

5 0.63098741 28 nips-2001-Adaptive Nearest Neighbor Classification Using Support Vector Machines

Author: Carlotta Domeniconi, Dimitrios Gunopulos

Abstract: The nearest neighbor technique is a simple and appealing method to address classification problems. It relies on t he assumption of locally constant class conditional probabilities. This assumption becomes invalid in high dimensions with a finite number of examples due to the curse of dimensionality. We propose a technique that computes a locally flexible metric by means of Support Vector Machines (SVMs). The maximum margin boundary found by the SVM is used to determine the most discriminant direction over the query's neighborhood. Such direction provides a local weighting scheme for input features. We present experimental evidence of classification performance improvement over the SVM algorithm alone and over a variety of adaptive learning schemes, by using both simulated and real data sets. 1

6 0.6297918 132 nips-2001-Novel iteration schemes for the Cluster Variation Method

7 0.62847126 88 nips-2001-Grouping and dimensionality reduction by locally linear embedding

8 0.62772286 13 nips-2001-A Natural Policy Gradient

9 0.62635922 58 nips-2001-Covariance Kernels from Bayesian Generative Models

10 0.62328082 69 nips-2001-Escaping the Convex Hull with Extrapolated Vector Machines

11 0.62074894 36 nips-2001-Approximate Dynamic Programming via Linear Programming

12 0.62032384 155 nips-2001-Quantizing Density Estimators

13 0.62026811 131 nips-2001-Neural Implementation of Bayesian Inference in Population Codes

14 0.61989385 188 nips-2001-The Unified Propagation and Scaling Algorithm

15 0.6198082 135 nips-2001-On Spectral Clustering: Analysis and an algorithm

16 0.61896437 84 nips-2001-Global Coordination of Local Linear Models

17 0.61868578 143 nips-2001-PAC Generalization Bounds for Co-training

18 0.61842775 79 nips-2001-Gaussian Process Regression with Mismatched Models

19 0.61826324 122 nips-2001-Model Based Population Tracking and Automatic Detection of Distribution Changes

20 0.6179328 7 nips-2001-A Dynamic HMM for On-line Segmentation of Sequential Data