nips nips2009 nips2009-219 knowledge-graph by maker-knowledge-mining

219 nips-2009-Slow, Decorrelated Features for Pretraining Complex Cell-like Networks

Source: pdf

Author: Yoshua Bengio, James S. Bergstra

Abstract: We introduce a new type of neural network activation function based on recent physiological rate models for complex cells in visual area V1. A single-hiddenlayer neural network of this kind of model achieves 1.50% error on MNIST. We also introduce an existing criterion for learning slow, decorrelated features as a pretraining strategy for image models. This pretraining strategy results in orientation-selective features, similar to the receptive ﬁelds of complex cells. With this pretraining, the same single-hidden-layer model achieves 1.34% error, even though the pretraining sample distribution is very different from the ﬁne-tuning distribution. To implement this pretraining strategy, we derive a fast algorithm for online learning of decorrelated features such that each iteration of the algorithm runs in linear time with respect to the number of features. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 ca Abstract We introduce a new type of neural network activation function based on recent physiological rate models for complex cells in visual area V1. [sent-5, score-0.572]

2 We also introduce an existing criterion for learning slow, decorrelated features as a pretraining strategy for image models. [sent-8, score-0.782]

3 This pretraining strategy results in orientation-selective features, similar to the receptive ﬁelds of complex cells. [sent-9, score-0.603]

4 34% error, even though the pretraining sample distribution is very different from the ﬁne-tuning distribution. [sent-11, score-0.443]

5 To implement this pretraining strategy, we derive a fast algorithm for online learning of decorrelated features such that each iteration of the algorithm runs in linear time with respect to the number of features. [sent-12, score-0.608]

6 1 Introduction Visual area V1 is the ﬁrst area of cortex devoted to handling visual input in the human visual system (Dayan & Abbott, 2001). [sent-13, score-0.258]

7 One convenient simpliﬁcation in the study of cell behaviour is to ignore the timing of individual spikes, and to look instead at their frequency. [sent-14, score-0.153]

8 Some cells in V1 are described well by a linear ﬁlter that has been rectiﬁed to be non-negative and perhaps bounded. [sent-15, score-0.154]

9 These so-called simple cells are similar to sigmoidal activation functions: their activity (ﬁring frequency) is greater as an image stimulus looks more like some particular linear ﬁlter. [sent-16, score-0.494]

10 However, these simple cells are a minority in visual area V1 and the characterization of the remaining cells there (and even beyond in visual areas V2, V4, MT, and so on) is a very active area of ongoing research. [sent-17, score-0.566]

11 This non-linear response has been modeled by quadrature pairs (Adelson & Bergen, 1985; Dayan & Abbott, 2001): pairs of linear ﬁlters with the property that the sum of their squared responses is constant for an input image with particular spatial frequency and orientation (i. [sent-20, score-0.16]

12 More recently, it has been argued that V1 cells exhibit a range of behaviour that blurs distinctions between simple and complex cells and between energy models and max-pooling models (Rust et al. [sent-24, score-0.495]

13 Another theme in neural modeling is that cells do not react to single images, they react to image sequences. [sent-26, score-0.32]

14 It is a gross approximation to suppose that each cell implements a function from image to activity level. [sent-27, score-0.18]

15 The principle of identifying slowly moving/changing factors in temporal/spatial data has been investigated by many (Becker & Hinton, 1993; Wiskott & Sejnowski, 2002; Hurri & Hyv¨ rinen, 2003; K¨ rding a o et al. [sent-30, score-0.176]

16 , 2004; Cadieu & Olshausen, 2009) as a principle for ﬁnding useful representations of images, 1 and as an explanation for why V1 simple and complex cells behave the way they do. [sent-31, score-0.274]

17 However, models that have been pretrained with appropriate unsupervised learning procedures (such as RBMs and various forms of auto-encoders) generalize better (Hinton et al. [sent-35, score-0.241]

18 Recent work in the pretraining of neural networks has taken a generative modeling perspective. [sent-44, score-0.443]

19 Reconstruction error is an even poorer approximation of the maximum likelihood gradient, and sometimes works better than CD (with additional twists like sparsity or the denoising of (Vincent et al. [sent-48, score-0.172]

20 The temporal coherence and decorrelation criterion is an alternative to training generative models such as RBMs or auto-encoder variants. [sent-50, score-0.502]

21 , 2009) demonstrated that a slowness criterion regularizing the top-most internal layer of a deep convolutional network during supervised learning helps their model to generalize better. [sent-52, score-0.497]

22 Our model is similar in spirit to pre-training with the semi-supervised embedding criterion at each level (Weston et al. [sent-53, score-0.163]

23 , 2009), but differs in the use of decorrelation as a mechanism for preventing trivial solutions to a slowness criterion. [sent-55, score-0.303]

24 Whereas RBMs and denoising autoencoders are deﬁned for general input distributions, the temporal coherence and decorrelation criterion makes sense only in the context of data with slowly-changing temporal or spatial structure, such as images, video, and sound. [sent-56, score-0.639]

25 In the same way that simple cell models were the inspiration for sigmoidal activation units in artiﬁcial neural networks and validated simple cell models, we investigate in artiﬁcial neural network classiﬁers the value of complex cell models. [sent-57, score-0.773]

26 This paper builds on these results by showing that the principle of temporal coherence is useful for ﬁnding initial conditions for the hidden layer of a neural network that biases it towards better generalization in object recognition. [sent-58, score-0.362]

27 We introduce temporal coherence and decorrelation as a pretraining algorithm. [sent-59, score-0.791]

28 In order for this criterion to be useful in the context of large models, we derive a fast online algorithm for decorrelating units and maximizing temporal coherence. [sent-61, score-0.233]

29 1 Algorithm Slow, decorrelated feature learning algorithm (K¨ rding et al. [sent-63, score-0.24]

30 , 2004) introduced a principle (and training criterion) to explain the formation of o complex cell receptive ﬁelds. [sent-64, score-0.359]

31 They based their analysis on the complex-cell model of (Adelson & Bergen, 1985), which describes a complex cell as a pair of half-rectiﬁed linear ﬁlters whose outputs are squared and added together and then a square root is applied to that sum. [sent-65, score-0.238]

32 Suppose x is an input image and we have F complex cells h1 , . [sent-66, score-0.307]

33 This makes the criterion too slow for use with large datasets. [sent-74, score-0.16]

34 At the same time, the size of the covariance matrix is quadratic in the number of features, so it is computationally expensive (perhaps prohibitively) to apply the criterion to train large numbers of features. [sent-75, score-0.156]

35 One way to apply the criterion to large or inﬁnite datasets is by estimating the covariance (and variance) from consecutive minibatches of N movie frames. [sent-79, score-0.21]

36 ¯ ¯ hi (t) = ρhi (t − 1) + (1 − ρ)hi (t) For good results, ρ should be chosen so that the estimates change very slowly. [sent-82, score-0.227]

37 L(t) = α N2 F |Z(t)Z (t)|2 − N ( zi (τ )2 )2 + i=1 τ =1 1 N −1 N −1 F (zi (τ ) − zi (τ − 1))2 (3) τ =1 i=1 The time complexity of computing L(t) using Equation 3 from Z(t) is O(N N F ). [sent-95, score-0.248]

38 2 Complex-cell activation function Recently, (Rust et al. [sent-100, score-0.226]

39 , 2005) have argued that existing models, such as that of (Adelson & Bergen, 1985) cannot account for the variety of behaviour found in visual area V1. [sent-101, score-0.174]

40 Some complex cells behave like simple cells to some extent and vice versa; there is a continuous range of simple to complex cells. [sent-102, score-0.47]

41 They put forward a similar but more involved expression that can capture the simple and complex cells as special cases, but ultimately parameterizes a larger class of cell-response functions (Eq. [sent-103, score-0.235]

42 β max(0, wx)2 + a+ I (i) 2 i=1 (u x) 1 + γ max(0, wx)2 + ζ I (i) 2 i=1 (u x) −δ ζ + J (j) 2 x) j=1 (v ζ J (j) x)2 j=1 (v ζ (4) The numerator in Eq 4 describes the difference between an excitation term and a shunting inhibition term. [sent-105, score-0.173]

43 Parameters w, u(i) , v (j) have the same shape as the input image x, and can be thought of as image ﬁlters like the ﬁrst layer of a neural network or the codebook of a sparse-coding model. [sent-107, score-0.252]

44 The parameters a, β, δ, γ, , ζ are scalars that control the range and shape of the activation function, given all the ﬁlter responses. [sent-108, score-0.165]

45 The range of this activation function (as a function of x) is a connected set on the (−1, 1) interval. [sent-119, score-0.165]

46 If the inhibition term is always 0 for example, then the activation function will be non-negative. [sent-121, score-0.226]

47 Each hidden unit had one linear ﬁlter w, a bias b, two quadratic excitatory ﬁlters u1 , u2 and two quadratic inhibitory ﬁlters v1 , v2 . [sent-126, score-0.233]

48 The computational cost of evaluating each unit was thus ﬁve times the cost of evaluating a normal sigmoidal activation function of the form tanh(w x + b). [sent-127, score-0.268]

49 Figure 1: Four of the three hundred activation functions learned by training our model from random initialization to perform classiﬁcation. [sent-136, score-0.257]

50 Bottom row: the red and blue channels are the two quadratic ﬁlters of the shunting inhibition term. [sent-138, score-0.177]

51 2 Pretraining with natural movies Under the hypothesis that the matched Gabor functions (see Fig. [sent-141, score-0.207]

52 1) allowed our model to generalize better across slight translations of the image, we appealed to a pretraining process to initialize our model with values better than random noise. [sent-142, score-0.443]

53 We pretrained the hidden layer according to the online version of the cost in Eq. [sent-143, score-0.205]

54 3, using movies (MIXED-movies) made by sliding a 28 x 28 pixel window across large photographs. [sent-144, score-0.291]

55 Each of these movies was short (just four frames long) and ten movies were used in each minibatch (N = 40). [sent-145, score-0.597]

56 The sliding initial position was sampled uniformly from image coordinates. [sent-149, score-0.156]

57 The shunting inhibition ﬁlters (v1 , v2 ) learned after ﬁve hundred thousand movies (ﬁfty thousand iterations of stochastic gradient descent) are shown in Figure 2. [sent-155, score-0.47]

58 The ﬁlters shown in ﬁgure 2 have fairly global receptive ﬁelds, but smaller more local receptive ﬁelds were obtained by applying 1 weight-penalization during pretraining. [sent-157, score-0.158]

59 The α parameter that balances decorrelation and slowness was chosen manually on the basis of the trained ﬁlters. [sent-158, score-0.303]

60 The excitatory ﬁlters learned similar Gabor pairs but the receptive ﬁelds tended to be both smaller (more localized) and lower-frequency. [sent-160, score-0.163]

61 3 Pretraining with MNIST movies We also tried pretraining with videos whose frames follow a similar distribution to the images used for ﬁne-tuning and testing. [sent-165, score-0.818]

62 We created MNIST movies by sampling an image from the training set, and moving around (translating it) according to a Brownian motion. [sent-166, score-0.369]

63 Changes in that velocity between each 5 Figure 2: Filters from some of the units of the model, pretrained on small sliding image patches from two large images. [sent-169, score-0.316]

64 Furthermore, the digit image in each frame was modiﬁed according to a randomly chosen elastic deformation, as in (Loosli et al. [sent-176, score-0.179]

65 As before, movies of four frames were created in this way and training was conducted on minibatches of ten movies (N = 4 ∗ 10 = 40). [sent-178, score-0.635]

66 Unlike the mnist frames in MIXED-movies, the frames of MNIST-movies contain a single digit that is approximately centered. [sent-179, score-0.308]

67 The activation functions learned by minimizing Equation 3 on these MNIST movies were qualitatively different from the activation functions learned from the MIXED movies. [sent-180, score-0.617]

68 The inhibitory weights (v1 , v2 ) learned from MNIST movies are shown in 3. [sent-181, score-0.291]

69 Figure 3: Filters of our model, pretrained on movies of centered MNIST training images subjected to Brownian translation. [sent-189, score-0.402]

70 6 Table 1: Generalization error (% error) from 100 labeled MNIST examples after pretraining on MIXED-movies and MNIST-movies. [sent-193, score-0.443]

71 Pre-training Dataset Number of pretraining iterations (×104 ) 0 1 2 3 4 5 MIXED-movies MNIST-movies 4 23. [sent-194, score-0.443]

72 A single-hidden layer neural network of sigmoidal units can achieve 1. [sent-207, score-0.268]

73 A single-hidden layer sigmoidal neural network pretrained as a denoising auto-encoder (and then ﬁne-tuned) can achieve 1. [sent-210, score-0.39]

74 4%; our pretraining strategy allows our single-layer model be better than Gaussian SVMs (Decoste & Sch¨ lkopf, 2002). [sent-215, score-0.443]

75 In future work, we will explore strategies for combining these methods and with our decorrelation criterion to train deep networks of models with quadratic input interactions. [sent-224, score-0.48]

76 The value of pretraining is evident right away: after two unsupervised passes over the MNIST training data (100K movies and 10K iterations), the weights have been initialized better. [sent-232, score-0.779]

77 Further pretraining offers a diminishing marginal return, although after ten unsupervised passes through the training data (500K movies) there is no evidence of over-pretraining. [sent-236, score-0.61]

78 A larger test set would be required to make a strong conclusion about a downward trend in test set scores for larger numbers of pretraining iterations. [sent-240, score-0.443]

79 2 Slowness in normalized features encourages binary activations Somewhat counter-intuitively, the slowness criterion requires movement in the features h. [sent-243, score-0.359]

80 Suppose a feature hi has activation levels that are normally distributed around 0. [sent-244, score-0.392]

81 2, but the activation at each frame of a movie is independent of previous frames. [sent-246, score-0.262]

82 Since the features has a small variance, then the normalized feature zi will oscillate in the same way, but with unit variance. [sent-247, score-0.186]

83 This will cause zi (t) − zi (t − 1) to be relatively high, and for our slowness criterion not to be well satisﬁed. [sent-248, score-0.483]

84 In this way the lack of variance in hi can actually make for a relatively fast normalized feature zi rather than a slow one. [sent-249, score-0.409]

85 However, if hi has activation levels that are normally distributed around . [sent-250, score-0.392]

86 9 for other image sequences, the marginal variance in hi will be larger. [sent-254, score-0.299]

87 In this sense, the slowness objective can be maximally satisﬁed by features hi (t) that take near-minimum and near-maximum values for most movies, and never transition from a near-minimum to a near-maximum value during a movie. [sent-258, score-0.422]

88 Perhaps this is one of the roles of saccades in the visual system: to suspend the normal objective of temporal coherence during a rapid widespread change of activation levels. [sent-260, score-0.41]

89 3 Eigenvalue interpretation of decorrelation term What does our unsupervised cost mean? [sent-262, score-0.247]

90 One way of thinking about the decorrelation term (ﬁrst term in Eq. [sent-263, score-0.17]

91 =j Covt (hi , hj )2 =2 Var(hi )Var(hj ) F −1  F F  F Covt (zi , zj )2 =  Covt (zi , zj )2  − F i=1 j=1 i=1 j=i+1 If we use C to denote the matrix whose i, j entry is Covt (zi , zj ), and we use U ΛU to denote the eigen-decomposition of C, then we can transform this sum over i! [sent-267, score-0.183]

92 1 as penalizing the squared eigenvalues of the covariance matrix between features in a normalized feature space (z as opposed to h), or as minimizing the squared eigenvalues of the correlation matrix between features h. [sent-270, score-0.222]

93 5 Conclusion We have presented an activation function for use in neural networks that is a simpliﬁcation of a recent rate model of visual area V1 complex cells. [sent-271, score-0.375]

94 Temporal coherence and decorrelation has been put forward as a principle for explaining the functional behaviour of visual area V1 complex cells. [sent-273, score-0.568]

95 Pretraining our model with this unsupervised criterion yields even lower generalization error: better than Gaussian SVMs, and competitive with deep denoising auto-encoders and 3-layer deep belief networks. [sent-275, score-0.563]

96 Slow feature analysis yields a rich repertoire of complex cell properties. [sent-299, score-0.189]

97 The difﬁculty of training deep architectures and the effect of unsupervised pre-training. [sent-325, score-0.337]

98 Computational diversity in complex cells of cat primary visual cortex. [sent-332, score-0.302]

99 How are complex cell properties o a o adapted to the statistics of natural stimuli? [sent-353, score-0.189]

100 An empirical evaluation of deep architectures on problems with many factors of variation. [sent-368, score-0.208]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('pretraining', 0.443), ('lters', 0.235), ('hi', 0.227), ('movies', 0.207), ('decorrelation', 0.17), ('activation', 0.165), ('mnist', 0.16), ('cells', 0.154), ('deep', 0.154), ('covt', 0.142), ('slowness', 0.133), ('zi', 0.124), ('cell', 0.108), ('coherence', 0.104), ('pretrained', 0.103), ('sigmoidal', 0.103), ('decorrelated', 0.103), ('criterion', 0.102), ('sliding', 0.084), ('bergen', 0.083), ('rust', 0.083), ('complex', 0.081), ('erhan', 0.08), ('var', 0.079), ('receptive', 0.079), ('unsupervised', 0.077), ('denoising', 0.076), ('adelson', 0.076), ('wiskott', 0.076), ('rding', 0.076), ('frames', 0.074), ('temporal', 0.074), ('image', 0.072), ('rbms', 0.071), ('minibatch', 0.071), ('mobahi', 0.071), ('poggio', 0.067), ('visual', 0.067), ('layer', 0.065), ('tr', 0.065), ('features', 0.062), ('stripes', 0.062), ('shunting', 0.062), ('area', 0.062), ('et', 0.061), ('ranzato', 0.061), ('inhibition', 0.061), ('bengio', 0.06), ('slow', 0.058), ('minibatches', 0.057), ('units', 0.057), ('hinton', 0.054), ('quadratic', 0.054), ('architectures', 0.054), ('hj', 0.054), ('vincent', 0.054), ('videos', 0.054), ('decoste', 0.053), ('gabor', 0.052), ('training', 0.052), ('movie', 0.051), ('thousand', 0.05), ('excitation', 0.05), ('squared', 0.049), ('larochelle', 0.048), ('abbott', 0.048), ('ewx', 0.047), ('finn', 0.047), ('loosli', 0.047), ('react', 0.047), ('frame', 0.046), ('weston', 0.046), ('behaviour', 0.045), ('excitatory', 0.044), ('inhibitory', 0.044), ('wx', 0.043), ('network', 0.043), ('zj', 0.043), ('dayan', 0.041), ('featuring', 0.041), ('windowed', 0.041), ('fty', 0.041), ('cadieu', 0.041), ('kouh', 0.041), ('manzagol', 0.041), ('ferster', 0.041), ('hurri', 0.041), ('learned', 0.04), ('images', 0.04), ('digits', 0.04), ('spatial', 0.039), ('lter', 0.039), ('principle', 0.039), ('photograph', 0.038), ('moving', 0.038), ('ten', 0.038), ('hidden', 0.037), ('yielded', 0.037), ('berkes', 0.035), ('poorer', 0.035)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 219 nips-2009-Slow, Decorrelated Features for Pretraining Complex Cell-like Networks

Author: Yoshua Bengio, James S. Bergstra

2 0.20832877 151 nips-2009-Measuring Invariances in Deep Networks

Author: Ian Goodfellow, Honglak Lee, Quoc V. Le, Andrew Saxe, Andrew Y. Ng

Abstract: For many pattern recognition tasks, the ideal input feature would be invariant to multiple confounding properties (such as illumination and viewing angle, in computer vision applications). Recently, deep architectures trained in an unsupervised manner have been proposed as an automatic method for extracting useful features. However, it is difﬁcult to evaluate the learned features by any means other than using them in a classiﬁer. In this paper, we propose a number of empirical tests that directly measure the degree to which these learned features are invariant to different input transformations. We ﬁnd that stacked autoencoders learn modestly increasingly invariant features with depth when trained on natural images. We ﬁnd that convolutional deep belief networks learn substantially more invariant features in each layer. These results further justify the use of “deep” vs. “shallower” representations, but suggest that mechanisms beyond merely stacking one autoencoder on top of another may be important for achieving invariance. Our evaluation metrics can also be used to evaluate future work in deep learning, and thus help the development of future algorithms. 1

3 0.20589311 241 nips-2009-The 'tree-dependent components' of natural scenes are edge filters

Author: Daniel Zoran, Yair Weiss

Abstract: We propose a new model for natural image statistics. Instead of minimizing dependency between components of natural images, we maximize a simple form of dependency in the form of tree-dependencies. By learning ﬁlters and tree structures which are best suited for natural images we observe that the resulting ﬁlters are edge ﬁlters, similar to the famous ICA on natural images results. Calculating the likelihood of an image patch using our model requires estimating the squared output of pairs of ﬁlters connected in the tree. We observe that after learning, these pairs of ﬁlters are predominantly of similar orientations but different phases, so their joint energy resembles models of complex cells. 1 Introduction and related work Many models of natural image statistics have been proposed in recent years [1, 2, 3, 4]. A common goal of many of these models is ﬁnding a representation in which components or sub-components of the image are made as independent or as sparse as possible [5, 6, 2]. This has been found to be a difﬁcult goal, as natural images have a highly intricate structure and removing dependencies between components is hard [7]. In this work we take a different approach, instead of minimizing dependence between components we try to maximize a simple form of dependence - tree dependence. It would be useful to place this model in context of previous works about natural image statistics. Many earlier models are described by the marginal statistics solely, obtaining a factorial form of the likelihood: p(x) = pi (xi ) (1) i The most notable model of this approach is Independent Component Analysis (ICA), where one seeks to ﬁnd a linear transformation which maximizes independence between components (thus ﬁtting well with the aforementioned factorization). This model has been applied to many scenarios, and proved to be one of the great successes of natural image statistics modeling with the emergence of edge-ﬁlters [5]. This approach has two problems. The ﬁrst is that dependencies between components are still very strong, even with those learned transformation seeking to remove them. Second, it has been shown that ICA achieves, after the learned transformation, only marginal gains when measured quantitatively against simpler method like PCA [7] in terms of redundancy reduction. A different approach was taken recently in the form of radial Gaussianization [8], in which components which are distributed in a radially symmetric manner are made independent by transforming them non-linearly into a radial Gaussian, and thus, independent from one another. A more elaborate approach, related to ICA, is Independent Subspace Component Analysis or ISA. In this model, one looks for independent subspaces of the data, while allowing the sub-components 1 Figure 1: Our model with respect to marginal models such as ICA (a), and ISA like models (b). Our model, being a tree based model (c), allows components to belong to more than one subspace, and the subspaces are not required to be independent. of each subspace to be dependent: p(x) = pk (xi∈K ) (2) k This model has been applied to natural images as well and has been shown to produce the emergence of phase invariant edge detectors, akin to complex cells in V1 [2]. Independent models have several shortcoming, but by far the most notable one is the fact that the resulting components are, in fact, highly dependent. First, dependency between the responses of ICA ﬁlters has been reported many times [2, 7]. Also, dependencies between ISA components has also been observed [9]. Given these robust dependencies between ﬁlter outputs, it is somewhat peculiar that in order to get simple cell properties one needs to assume independence. In this work we ask whether it is possible to obtain V1 like ﬁlters in a model that assumes dependence. In our model we assume the ﬁlter distribution can be described by a tree graphical model [10] (see Figure 1). Degenerate cases of tree graphical models include ICA (in which no edges are present) and ISA (in which edges are only present within a subspace). But in its non-degenerate form, our model assumes any two ﬁlter outputs may be dependent. We allow components to belong to more than one subspace, and as a result, do not require independence between them. 2 Model and learning Our model is comprised of three main components. Given a set of patches, we look for the parameters which maximize the likelihood of a whitened natural image patch z: N p(yi |ypai ; β) p(z; W, β, T ) = p(y1 ) (3) i=1 Where y = Wz, T is the tree structure, pai denotes the parent of node i and β is a parameter of the density model (see below for the details). The three components we are trying to learn are: 1. The ﬁlter matrix W, where every row deﬁnes one of the ﬁlters. The response of these ﬁlters is assumed to be tree-dependent. We assume that W is orthogonal (and is a rotation of a whitening transform). 2. The tree structure T which speciﬁes which components are dependent on each other. 3. The probability density function for connected nodes in the tree, which specify the exact form of dependency between nodes. All three together describe a complete model for whitened natural image patches, allowing likelihood estimation and exact inference [11]. We perform the learning in an iterative manner: we start by learning the tree structure and density model from the entire data set, then, keeping the structure and density constant, we learn the ﬁlters via gradient ascent in mini-batches. Going back to the tree structure we repeat the process many times iteratively. It is important to note that both the ﬁlter set and tree structure are learned from the data, and are continuously updated during learning. In the following sections we will provide details on the speciﬁcs of each part of the model. 2 β=0.0 β=0.5 β=1.0 β=0.0 β=0.5 β=1.0 2 1 1 1 1 1 1 0 −1 0 −1 −2 −1 −2 −3 0 x1 2 0 x1 2 0 x1 2 −2 −3 −2 0 x1 2 0 −1 −2 −3 −2 0 −1 −2 −3 −2 0 −1 −2 −3 −2 0 x2 3 2 x2 3 2 x2 3 2 x2 3 2 x2 3 2 x2 3 −3 −2 0 x1 2 −2 0 x1 2 Figure 2: Shape of the conditional (Left three plots) and joint (Right three plots) density model in log scale for several values of β, from dependence to independence. 2.1 Learning tree structure In their seminal paper, Chow and Liu showed how to learn the optimal tree structure approximation for a multidimensional probability density function [12]. This algorithm is easy to apply to this scenario, and requires just a few simple steps. First, given the current estimate for the ﬁlter matrix W, we calculate the response of each of the ﬁlters with all the patches in the data set. Using these responses, we calculate the mutual information between each pair of ﬁlters (nodes) to obtain a fully connected weighted graph. The ﬁnal step is to ﬁnd a maximal spanning tree over this graph. The resulting unrooted tree is the optimal tree approximation of the joint distribution function over all nodes. We will note that the tree is unrooted, and the root can be chosen arbitrarily - this means that there is no node, or ﬁlter, that is more important than the others - the direction in the tree graph is arbitrary as long as it is chosen in a consistent way. 2.2 Joint probability density functions Gabor ﬁlter responses on natural images exhibit highly kurtotic marginal distributions, with heavy tails and sharp peaks [13, 3, 14]. Joint pair wise distributions also exhibit this same shape with varying degrees of dependency between the components [13, 2]. The density model we use allows us to capture both the highly kurtotic nature of the distributions, while still allowing varying degrees of dependence using a mixing variable. We use a mix of two forms of ﬁnite, zero mean Gaussian Scale Mixtures (GSM). In one, the components are assumed to be independent of each other and in the other, they are assumed to be spherically distributed. The mixing variable linearly interpolates between the two, allowing us to capture the whole range of dependencies: p(x1 , x2 ; β) = βpdep (x1 , x2 ) + (1 − β)pind (x1 , x2 ) (4) When β = 1 the two components are dependent (unless p is Gaussian), whereas when β = 0 the two components are independent. For the density functions themselves, we use a ﬁnite GSM. The dependent case is a scale mixture of bivariate Gaussians: 2 πk N (x1 , x2 ; σk I) pdep (x1 , x2 ) = (5) k While the independent case is a product of two independent univariate Gaussians: 2 πk N (x1 ; σk ) pind (x1 , x2 ) = k 2 πk N (x2 ; σk ) (6) k 2 Estimating parameters πk and σk for the GSM is done directly from the data using Expectation Maximization. These parameters are the same for all edges and are estimated only once on the ﬁrst iteration. See Figure 2 for a visualization of the conditional distribution functions for varying values of β. We will note that the marginal distributions for the two types of joint distributions above are the same. The mixing parameter β is also estimated using EM, but this is done for each edge in the tree separately, thus allowing our model to theoretically capture the fully independent case (ICA) and other degenerate models such as ISA. 2.3 Learning tree dependent components Given the current tree structure and density model, we can now learn the matrix W via gradient ascent on the log likelihood of the model. All learning is performed on whitened, dimensionally 3 reduced patches. This means that W is a N × N rotation (orthonormal) matrix, where N is the number of dimensions after dimensionality reduction (see details below). Given an image patch z we multiply it by W to get the response vector y: y = Wz (7) Now we can calculate the log likelihood of the given patch using the tree model (which we assume is constant at the moment): N log p(yi |ypai ) log p(y) = log p(yroot ) + (8) i=1 Where pai denotes the parent of node i. Now, taking the derivative w.r.t the r-th row of W: ∂ log p(y) ∂ log p(y) T = z ∂Wr ∂yr (9) Where z is the whitened natural image patch. Finally, we can calculate the derivative of the log likelihood with respect to the r-th element in y: ∂ log p(ypar , yr ) ∂ log p(y) = + ∂yr ∂yr c∈C(r) ∂ log p(yr , yc ) ∂ log p(yr ) − ∂yr ∂yr (10) Where C(r) denote the children of node r. In summary, the gradient ascent rule for updating the rotation matrix W is given by: t+1 t Wr = Wr + η ∂ log p(y) T z ∂yr (11) Where η is the learning rate constant. After update, the rows of W are orthonormalized. This gradient ascent rule is applied for several hundreds of patches (see details below), after which the tree structure is learned again as described in Section 2.1, using the new ﬁlter matrix W, repeating this process for many iterations. 3 Results and analysis 3.1 Validation Before running the full algorithm on natural image data, we wanted to validate that it does produce sensible results with simple synthetic data. We generated noise from four different models, one is 1/f independent Gaussian noise with 8 Discrete Cosine Transform (DCT) ﬁlters, the second is a simple ICA model with 8 DCT ﬁlters, and highly kurtotic marginals. The third was a simple ISA model - 4 subspaces, each with two ﬁlters from the DCT ﬁlter set. Distribution within the subspace was a circular, highly kurtotic GSM, and the subspaces were sampled independently. Finally, we generated data from a simple synthetic tree of DCT ﬁlters, using the same joint distributions as for the ISA model. These four synthetic random data sets were given to the algorithm - results can be seen in Figure 3 for the ICA, ISA and tree samples. In all cases the model learned the ﬁlters and distribution correctly, reproducing both the ﬁlters (up to rotations within the subspace in ISA) and the dependency structure between the different ﬁlters. In the case of 1/f Gaussian noise, any whitening transformation is equally likely and any value of beta is equally likely. Thus in this case, the algorithm cannot ﬁnd the tree or the ﬁlters. 3.2 Learning from natural image patches We then ran experiments with a set of natural images [9]1 . These images contain natural scenes such as mountains, ﬁelds and lakes. . The data set was 50,000 patches, each 16 × 16 pixels large. The patches’ DC was removed and they were then whitened using PCA. Dimension was reduced from 256 to 128 dimensions. The GSM for the density model had 16 components. Several initial 1 available at http://www.cis.hut.ﬁ/projects/ica/imageica/ 4 Figure 3: Validation of the algorithm. Noise was generated from three models - top row is ICA, middle row is ISA and bottom row is a tree model. Samples were then given to the algorithm. On the right are the resulting learned tree models. Presented are the learned ﬁlters, tree model (with white edges meaning β = 0, black meaning β = 1 and grays intermediate values) and an example of a marginal histogram for one of the ﬁlters. It can be seen that in all cases all parts of the model were correctly learned. Filters in the ISA case were learned up to rotation within the subspace, and all ﬁlters were learned up to sign. β values for the ICA case were always below 0.1, as were the values of β between subspaces in ISA. conditions for the matrix W were tried out (random rotations, identity) but this had little effect on results. Mini-batches of 10 patches each were used for the gradient ascent - the gradient of 10 patches was summed, and then normalized to have unit norm. The learning rate constant η was set to 0.1. Tree structure learning and estimation of the mixing variable β were done every 500 mini-batches. All in all, 50 iterations were done over the data set. 3.3 Filters and tree structure Figures 4 and 5 show the learned ﬁlters (WQ where Q is the whitening matrix) and tree structure (T ) learned from natural images. Unlike the ISA toy data in ﬁgure 3, here a full tree was learned and β is approximately one for all edges. The GSM that was learned for the marginals was highly kurtotic. It can be seen that resulting ﬁlters are edge ﬁlters at varying scales, positions and orientations. This is similar to the result one gets when applying ICA to natural images [5, 15]. More interesting is Figure 4: Left: Filter set learned from 16 × 16 natural image patches. Filters are ordered by PCA eigenvalues, largest to smallest. Resulting ﬁlters are edge ﬁlters having different orientations, positions, frequencies and phases. Right: The “feature” set learned, that is, columns of the pseudo inverse of the ﬁlter set. 5 Figure 5: The learned tree graph structure and feature set. It can be seen that neighboring features on the graph have similar orientation, position and frequency. See Figure 4 for a better view of the feature details, and see text for full detail and analysis. Note that the ﬁgure is rotated CW. 6 Optimal Orientation Optimal Frequency 3.5 Optimal Phase 7 3 0.8 6 2.5 Optimal Position Y 0.9 6 5 5 0.7 0.6 3 Child 1.5 4 Child 2 Child Child 4 3 2 1 1 0.4 0.3 2 0.5 0.5 0.2 0 1 0.1 0 0 1 2 Parent 3 4 0 0 2 4 Parent 6 8 0 0 1 2 3 Parent 4 5 6 0 0.2 0.4 0.6 Parent 0.8 1 Figure 6: Correlation of optimal parameters in neighboring nodes in the tree graph. Orientation, frequency and position are highly correlated, while phase seems to be entirely uncorrelated. This property of correlation in frequency and orientation, while having no correlation in phase is related to the ubiquitous energy model of complex cells in V1. See text for further details. Figure 7: Left: Comparison of log likelihood values of our model with PCA, ICA and ISA. Our model gives the highest likelihood. Right: Samples taken at random from ICA, ISA and our model. Samples from our model appear to contain more long-range structure. the tree graph structure learned along with the ﬁlters which is shown in Figure 5. It can be seen that neighboring ﬁlters (nodes) in the tree tend to have similar position, frequency and orientation. Figure 6 shows the correlation of optimal frequency, orientation and position for neighboring ﬁlters in the tree - it is obvious that all three are highly correlated. Also apparent in this ﬁgure is the fact that the optimal phase for neighboring ﬁlters has no signiﬁcant correlation. It has been suggested that ﬁlters which have the same orientation, frequency and position with different phase can be related to complex cells in V1 [2, 16]. 3.4 Comparison to other models Since our model is a generalization of both ICA and ISA we use it to learn both models. In order to learn ICA we used the exact same data set, but the tree had no edges and was not learned from the data (alternatively, we could have just set β = 0). For ISA we used a forest architecture of 2 node trees, setting β = 1 for all edges (which means a spherical symmetric distribution), no tree structure was learned. Both models produce edge ﬁlters similar to what we learn (and to those in [5, 15, 6]). The ISA model produces neighboring nodes with similar frequency and orientation, but different phase, as was reported in [2]. We also compare to a simple PCA whitening transform, using the same whitening transform and marginals as in the ICA case, but setting W = I. We compare the likelihood each model gives for a test set of natural image patches, different from the one that was used in training. There were 50,000 patches in the test set, and we calculate the mean log likelihood over the entire set. The table in Figure 7 shows the result - as can be seen, our model performs better in likelihood terms than both ICA and ISA. Using a tree model, as opposed to more complex graphical models, allows for easy sampling from the model. Figure 7 shows 20 random samples taken from our tree model along with samples from the ICA and ISA models. Note the elongated structures (e.g. in the bottom left sample) in the samples from the tree model, and compare to patches sampled from the ICA and ISA models. 7 40 40 30 30 20 20 10 1 10 0.8 0.6 0.4 0 0.2 0 0 1 2 3 Orientation 4 0 0 2 4 6 Frequency 8 0 2 4 Phase Figure 8: Left: Interpretation of the model. Given a patch, the response of all edge ﬁlters is computed (“simple cells”), then at each edge, the corresponding nodes are squared and summed to produce the response of the “complex cell” this edge represents. Both the response of complex cells and simple cells is summed to produce the likelihood of the patch. Right: Response of a “complex cell” in our model to changing phase, frequency and orientation. Response in the y-axis is the sum of squares of the two ﬁlters in this “complex cell”. Note that while the cell is selective to orientation and frequency, it is rather invariant to phase. 3.5 Tree models and complex cells One way to interpret the model is looking at the likelihood of a given patch under this model. For the case of β = 1 substituting Equation 4 into Equation 3 yields: 2 2 ρ( yi + ypai ) − ρ(|ypai |) log L(z) = (12) i 2 Where ρ(x) = log k πk N (x; σk ) . This form of likelihood has an interesting similarity to models of complex cells in V1 [2, 4]. In Figure 8 we draw a simple two-layer network that computes the likelihood. The ﬁrst layer applies linear ﬁlters (“simple cells”) to the image patch, while the second layer sums the squared outputs of similarly oriented ﬁlters from the ﬁrst layer, having different phases, which are connected in the tree (“complex cells”). Output is also dependent on the actual response of the “simple cell” layer. The likelihood here is maximized when both the response of the parent ﬁlter ypai and the child yi is zero, but, given that one ﬁlter has responded with a non-zero value, the likelihood is maximized when the other ﬁlter also ﬁres (see the conditional density in Figure 2). Figure 8 also shows an example of the phase invariance which is present in the learned

4 0.15564391 2 nips-2009-3D Object Recognition with Deep Belief Nets

Author: Vinod Nair, Geoffrey E. Hinton

Abstract: We introduce a new type of top-level model for Deep Belief Nets and evaluate it on a 3D object recognition task. The top-level model is a third-order Boltzmann machine, trained using a hybrid algorithm that combines both generative and discriminative gradients. Performance is evaluated on the NORB database (normalized-uniform version), which contains stereo-pair images of objects under diﬀerent lighting conditions and viewpoints. Our model achieves 6.5% error on the test set, which is close to the best published result for NORB (5.9%) using a convolutional neural net that has built-in knowledge of translation invariance. It substantially outperforms shallow models such as SVMs (11.6%). DBNs are especially suited for semi-supervised learning, and to demonstrate this we consider a modiﬁed version of the NORB recognition task in which additional unlabeled images are created by applying small translations to the images in the database. With the extra unlabeled data (and the same amount of labeled data as before), our model achieves 5.2% error. 1

5 0.1291049 119 nips-2009-Kernel Methods for Deep Learning

Author: Youngmin Cho, Lawrence K. Saul

Abstract: We introduce a new family of positive-deﬁnite kernel functions that mimic the computation in large, multilayer neural nets. These kernel functions can be used in shallow architectures, such as support vector machines (SVMs), or in deep kernel-based architectures that we call multilayer kernel machines (MKMs). We evaluate SVMs and MKMs with these kernel functions on problems designed to illustrate the advantages of deep architectures. On several problems, we obtain better results than previous, leading benchmarks from both SVMs with Gaussian kernels as well as deep belief nets. 1

6 0.1129203 231 nips-2009-Statistical Models of Linear and Nonlinear Contextual Interactions in Early Visual Processing

7 0.11186948 137 nips-2009-Learning transport operators for image manifolds

8 0.10200758 70 nips-2009-Discriminative Network Models of Schizophrenia

9 0.088125803 253 nips-2009-Unsupervised feature learning for audio classification using convolutional deep belief networks

10 0.087921381 164 nips-2009-No evidence for active sparsification in the visual cortex

11 0.085630894 236 nips-2009-Structured output regression for detection with partial truncation

12 0.084053092 237 nips-2009-Subject independent EEG-based BCI decoding

13 0.084009722 84 nips-2009-Evaluating multi-class learning strategies in a generative hierarchical framework for object detection

14 0.077871583 88 nips-2009-Extending Phase Mechanism to Differential Motion Opponency for Motion Pop-out

15 0.077845417 13 nips-2009-A Neural Implementation of the Kalman Filter

16 0.072090782 47 nips-2009-Boosting with Spatial Regularization

17 0.069472253 38 nips-2009-Augmenting Feature-driven fMRI Analyses: Semi-supervised learning and resting state activity

18 0.068138056 176 nips-2009-On Invariance in Hierarchical Models

19 0.066959053 172 nips-2009-Nonparametric Bayesian Texture Learning and Synthesis

20 0.064180017 111 nips-2009-Hierarchical Modeling of Local Image Features through $L p$-Nested Symmetric Distributions

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.23), (1, -0.142), (2, -0.008), (3, 0.068), (4, -0.026), (5, 0.107), (6, 0.034), (7, 0.119), (8, 0.002), (9, -0.054), (10, 0.01), (11, 0.009), (12, -0.254), (13, 0.162), (14, 0.148), (15, 0.001), (16, 0.059), (17, -0.017), (18, 0.002), (19, 0.106), (20, -0.009), (21, -0.023), (22, 0.011), (23, -0.103), (24, 0.029), (25, 0.047), (26, -0.093), (27, -0.003), (28, 0.068), (29, 0.017), (30, 0.022), (31, -0.096), (32, 0.032), (33, 0.062), (34, 0.043), (35, -0.051), (36, -0.008), (37, -0.005), (38, -0.005), (39, 0.045), (40, -0.098), (41, 0.001), (42, -0.05), (43, 0.023), (44, -0.047), (45, 0.075), (46, -0.027), (47, 0.075), (48, -0.055), (49, 0.039)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.94279915 219 nips-2009-Slow, Decorrelated Features for Pretraining Complex Cell-like Networks

Author: Yoshua Bengio, James S. Bergstra

2 0.71755588 151 nips-2009-Measuring Invariances in Deep Networks

Author: Ian Goodfellow, Honglak Lee, Quoc V. Le, Andrew Saxe, Andrew Y. Ng

3 0.68017668 241 nips-2009-The 'tree-dependent components' of natural scenes are edge filters

Author: Daniel Zoran, Yair Weiss

4 0.65546679 231 nips-2009-Statistical Models of Linear and Nonlinear Contextual Interactions in Early Visual Processing

Author: Ruben Coen-cagli, Peter Dayan, Odelia Schwartz

Abstract: A central hypothesis about early visual processing is that it represents inputs in a coordinate system matched to the statistics of natural scenes. Simple versions of this lead to Gabor–like receptive ﬁelds and divisive gain modulation from local surrounds; these have led to inﬂuential neural and psychological models of visual processing. However, these accounts are based on an incomplete view of the visual context surrounding each point. Here, we consider an approximate model of linear and non–linear correlations between the responses of spatially distributed Gaborlike receptive ﬁelds, which, when trained on an ensemble of natural scenes, uniﬁes a range of spatial context effects. The full model accounts for neural surround data in primary visual cortex (V1), provides a statistical foundation for perceptual phenomena associated with Li’s (2002) hypothesis that V1 builds a saliency map, and ﬁts data on the tilt illusion. 1

5 0.57187152 2 nips-2009-3D Object Recognition with Deep Belief Nets

Author: Vinod Nair, Geoffrey E. Hinton

6 0.55246329 237 nips-2009-Subject independent EEG-based BCI decoding

7 0.518049 111 nips-2009-Hierarchical Modeling of Local Image Features through $L p$-Nested Symmetric Distributions

8 0.5155676 84 nips-2009-Evaluating multi-class learning strategies in a generative hierarchical framework for object detection

9 0.5052653 137 nips-2009-Learning transport operators for image manifolds

10 0.49264589 253 nips-2009-Unsupervised feature learning for audio classification using convolutional deep belief networks

11 0.48050216 203 nips-2009-Replacing supervised classification learning by Slow Feature Analysis in spiking neural networks

12 0.47829708 6 nips-2009-A Biologically Plausible Model for Rapid Natural Scene Identification

13 0.47272393 189 nips-2009-Periodic Step Size Adaptation for Single Pass On-line Learning

14 0.46981326 176 nips-2009-On Invariance in Hierarchical Models

15 0.42996815 13 nips-2009-A Neural Implementation of the Kalman Filter

16 0.42783973 119 nips-2009-Kernel Methods for Deep Learning

17 0.42738581 164 nips-2009-No evidence for active sparsification in the visual cortex

18 0.40830252 172 nips-2009-Nonparametric Bayesian Texture Learning and Synthesis

19 0.39758649 56 nips-2009-Conditional Neural Fields

20 0.38923055 81 nips-2009-Ensemble Nystrom Method

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(21, 0.033), (24, 0.024), (25, 0.069), (35, 0.382), (36, 0.074), (39, 0.045), (42, 0.019), (58, 0.075), (62, 0.012), (71, 0.039), (81, 0.021), (86, 0.107)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.97593796 10 nips-2009-A Gaussian Tree Approximation for Integer Least-Squares

Author: Jacob Goldberger, Amir Leshem

Abstract: This paper proposes a new algorithm for the linear least squares problem where the unknown variables are constrained to be in a ﬁnite set. The factor graph that corresponds to this problem is very loopy; in fact, it is a complete graph. Hence, applying the Belief Propagation (BP) algorithm yields very poor results. The algorithm described here is based on an optimal tree approximation of the Gaussian density of the unconstrained linear system. It is shown that even though the approximation is not directly applied to the exact discrete distribution, applying the BP algorithm to the modiﬁed factor graph outperforms current methods in terms of both performance and complexity. The improved performance of the proposed algorithm is demonstrated on the problem of MIMO detection.

2 0.96187162 42 nips-2009-Bayesian Sparse Factor Models and DAGs Inference and Comparison

Author: Ricardo Henao, Ole Winther

Abstract: In this paper we present a novel approach to learn directed acyclic graphs (DAGs) and factor models within the same framework while also allowing for model comparison between them. For this purpose, we exploit the connection between factor models and DAGs to propose Bayesian hierarchies based on spike and slab priors to promote sparsity, heavy-tailed priors to ensure identiﬁability and predictive densities to perform the model comparison. We require identiﬁability to be able to produce variable orderings leading to valid DAGs and sparsity to learn the structures. The effectiveness of our approach is demonstrated through extensive experiments on artiﬁcial and biological data showing that our approach outperform a number of state of the art methods. 1

3 0.9525826 236 nips-2009-Structured output regression for detection with partial truncation

Author: Andrea Vedaldi, Andrew Zisserman

Abstract: We develop a structured output model for object category detection that explicitly accounts for alignment, multiple aspects and partial truncation in both training and inference. The model is formulated as large margin learning with latent variables and slack rescaling, and both training and inference are computationally efﬁcient. We make the following contributions: (i) we note that extending the Structured Output Regression formulation of Blaschko and Lampert [1] to include a bias term signiﬁcantly improves performance; (ii) that alignment (to account for small rotations and anisotropic scalings) can be included as a latent variable and efﬁciently determined and implemented; (iii) that the latent variable extends to multiple aspects (e.g. left facing, right facing, front) with the same formulation; and (iv), most signiﬁcantly for performance, that truncated and truncated instances can be included in both training and inference with an explicit truncation mask. We demonstrate the method by training and testing on the PASCAL VOC 2007 data set – training includes the truncated examples, and in testing object instances are detected at multiple scales, alignments, and with signiﬁcant truncations. 1

4 0.93261039 209 nips-2009-Robust Value Function Approximation Using Bilinear Programming

Author: Marek Petrik, Shlomo Zilberstein

Abstract: Existing value function approximation methods have been successfully used in many applications, but they often lack useful a priori error bounds. We propose approximate bilinear programming, a new formulation of value function approximation that provides strong a priori guarantees. In particular, this approach provably ﬁnds an approximate value function that minimizes the Bellman residual. Solving a bilinear program optimally is NP-hard, but this is unavoidable because the Bellman-residual minimization itself is NP-hard. We therefore employ and analyze a common approximate algorithm for bilinear programs. The analysis shows that this algorithm offers a convergent generalization of approximate policy iteration. Finally, we demonstrate that the proposed approach can consistently minimize the Bellman residual on a simple benchmark problem. 1 Motivation Solving large Markov Decision Problems (MDPs) is a very useful, but computationally challenging problem addressed widely in the AI literature, particularly in the area of reinforcement learning. It is widely accepted that large MDPs can only be solved approximately. The commonly used approximation methods can be divided into three broad categories: 1) policy search, which explores a restricted space of all policies, 2) approximate dynamic programming, which searches a restricted space of value functions, and 3) approximate linear programming, which approximates the solution using a linear program. While all of these methods have achieved impressive results in many domains, they have signiﬁcant limitations. Policy search methods rely on local search in a restricted policy space. The policy may be represented, for example, as a ﬁnite-state controller [22] or as a greedy policy with respect to an approximate value function [24]. Policy search methods have achieved impressive results in such domains as Tetris [24] and helicopter control [1]. However, they are notoriously hard to analyze. We are not aware of any theoretical guarantees regarding the quality of the solution. Approximate dynamic programming (ADP) methods iteratively approximate the value function [4, 20, 23]. They have been extensively analyzed and are the most commonly used methods. However, ADP methods typically do not converge and they only provide weak guarantees of approximation quality. The approximation error bounds are usually expressed in terms of the worst-case approximation of the value function over all policies [4]. In addition, most available bounds are with respect to the L∞ norm, while the algorithms often minimize the L2 norm. While there exist some L2 -based bounds [14], they require values that are difﬁcult to obtain. Approximate linear programming (ALP) uses a linear program to compute the approximate value function in a particular vector space [7]. ALP has been previously used in a wide variety of settings [2, 9, 10]. Although ALP often does not perform as well as ADP, there have been some recent 1 efforts to close the gap [18]. ALP has better theoretical properties than ADP and policy search. It is guaranteed to converge and return the closest L1 -norm approximation v of the optimal value func˜ tion v ∗ up to a multiplicative factor. However, the L1 norm must be properly weighted to guarantee a small policy loss, and there is no reliable method for selecting appropriate weights [7]. To summarize, the existing reinforcement learning techniques often provide good solutions, but typically require signiﬁcant domain knowledge [20]. The domain knowledge is needed partly because useful a priori error bounds are not available, as mentioned above. Our goal is to develop a more robust method that is guaranteed to minimize an actual bound on the policy loss. We present a new formulation of value function approximation that provably minimizes a bound on the policy loss. Unlike in some other algorithms, the bound in this case does not rely on values that are hard to obtain. The new method uniﬁes policy search and value-function search methods to minimize the L∞ norm of the Bellman residual, which bounds the policy loss. We start with a description of the framework and notation in Section 2. Then, in Section 3, we describe the proposed Approximate Bilinear Programming (ABP) formulation. A drawback of this formulation is its computational complexity, which may be exponential. We show in Section 4 that this is unavoidable, because minimizing the approximation error bound is in fact NP-hard. Although our focus is on the formulation and its properties, we also discuss some simple algorithms for solving bilinear programs. Section 5 shows that ABP can be seen as an improvement of ALP and Approximate Policy Iteration (API). Section 6 demonstrates the applicability of ABP using a common reinforcement learning benchmark problem. A complete discussion of sampling strategies–an essential component for achieving robustness–is beyond the scope of this paper, but the issue is brieﬂy discussed in Section 6. Complete proofs of the theorems can be found in [19]. 2 Solving MDPs using ALP In this section, we formally deﬁne MDPs, their ALP formulation, and the approximation errors involved. These notions serve as a basis for developing the ABP formulation. A Markov Decision Process is a tuple (S, A, P, r, α), where S is the ﬁnite set of states, A is the ﬁnite set of actions. P : S × S × A → [0, 1] is the transition function, where P (s , s, a) represents the probability of transiting to state s from state s, given action a. The function r : S × A → R is the reward function, and α : S → [0, 1] is the initial state distribution. The objective is to maximize the inﬁnite-horizon discounted cumulative reward. To shorten the notation, we assume an arbitrary ordering of the states: s1 , s2 , . . . , sn . Then, Pa and ra are used to denote the probabilistic transition matrix and reward for action a. The solution of an MDP is a policy π : S × A → [0, 1] from a set of possible policies Π, such that for all s ∈ S, a∈A π(s, a) = 1. We assume that the policies may be stochastic, but stationary [21]. A policy is deterministic when π(s, a) ∈ {0, 1} for all s ∈ S and a ∈ A. The transition and reward functions for a given policy are denoted by Pπ and rπ . The value function update for a policy π is denoted by Lπ , and the Bellman operator is denoted by L. That is: Lπ v = Pπ v + rπ Lv = max Lπ v. π∈Π The optimal value function, denoted v ∗ , satisﬁes v ∗ = Lv ∗ . We focus on linear value function approximation for discounted inﬁnite-horizon problems. In linear value function approximation, the value function is represented as a linear combination of nonlinear basis functions (vectors). For each state s, we deﬁne a row-vector φ(s) of features. The rows of the basis matrix M correspond to φ(s), and the approximation space is generated by the columns of the matrix. That is, the basis matrix M , and the value function v are represented as:   − φ(s1 ) −   M = − φ(s2 ) − v = M x. . . . Deﬁnition 1. A value function, v, is representable if v ∈ M ⊆ R|S| , where M = colspan (M ), and is transitive-feasible when v ≥ Lv. We denote the set of transitive-feasible value functions as: K = {v ∈ R|S| v ≥ Lv}. 2 Notice that the optimal value function v ∗ is transitive-feasible, and M is a linear space. Also, all the inequalities are element-wise. Because the new formulation is related to ALP, we introduce it ﬁrst. It is well known that an inﬁnite horizon discounted MDP problem may be formulated in terms of solving the following linear program: minimize v c(s)v(s) s∈S v(s) − γ s.t. P (s , s, a)v(s ) ≥ r(s, a) ∀(s, a) ∈ (S, A) (1) s ∈S We use A as a shorthand notation for the constraint matrix and b for the right-hand side. The value c represents a distribution over the states, usually a uniform one. That is, s∈S c(s) = 1. The linear program in Eq. (1) is often too large to be solved precisely, so it is approximated to get an approximate linear program by assuming that v ∈ M [8], as follows: minimize cT v x Av ≥ b s.t. (2) v∈M The constraint v ∈ M denotes the approximation. To actually solve this linear program, the value function is represented as v = M x. In the remainder of the paper, we assume that 1 ∈ M to guarantee the feasibility of the ALP, where 1 is a vector of all ones. The optimal solution of the ALP, v , satisﬁes that v ≥ v ∗ . Then, the objective of Eq. (2) represents the minimization of v − v ∗ 1,c , ˜ ˜ ˜ where · 1,c is a c-weighted L1 norm [7]. The ultimate goal of the optimization is not to obtain a good value function v , but a good policy. ˜ The quality of the policy, typically chosen to be greedy with respect to v , depends non-trivially on ˜ the approximate value function. The ABP formulation will minimize policy loss by minimizing L˜ − v ∞ , which bounds the policy loss as follows. v ˜ Theorem 2 (e.g. [25]). Let v be an arbitrary value function, and let v be the value of the greedy ˜ ˆ policy with respect to v . Then: ˜ 2 v∗ − v ∞ ≤ ˆ L˜ − v ∞ , v ˜ 1−γ In addition, if v ≥ L˜, the policy loss is smallest for the greedy policy. ˜ v Policies, like value functions, can be represented as vectors. Assume an arbitrary ordering of the state-action pairs, such that o(s, a) → N maps a state and an action to its position. The policies are represented as θ ∈ R|S|×|A| , and we use the shorthand notation θ(s, a) = θ(o(s, a)). Remark 3. The corresponding π and θ are denoted as π θ and θπ and satisfy: π θ (s, a) = θπ (s, a). We will also consider approximations of the policies in the policy-space, generated by columns of a matrix N . A policy is representable when π ∈ N , where N = colspan (N ). 3 Approximate Bilinear Programs This section shows how to formulate minv∈M Lv − v ∞ as a separable bilinear program. Bilinear programs are a generalization of linear programs with an additional bilinear term in the objective function. A separable bilinear program consists of two linear programs with independent constraints and are fairly easy to solve and analyze. Deﬁnition 4 (Separable Bilinear Program). A separable bilinear program in the normal form is deﬁned as follows: T T minimize f (w, x, y, z) = sT w + r1 x + xT Cy + r2 y + sT z 1 2 w,x y,z s.t. A1 x + B1 w = b1 A2 y + B2 z = b2 w, x ≥ 0 y, z ≥ 0 3 (3) We separate the variables using a vertical line and the constraints using different columns to emphasize the separable nature of the bilinear program. In this paper, we only use separable bilinear programs and refer to them simply as bilinear programs. An approximate bilinear program can now be formulated as follows. minimize θT λ + λ θ λ,λ ,v Bθ = 1 z = Av − b s.t. θ≥0 z≥0 (4) λ+λ1≥z λ≥0 θ∈N v∈M All variables are vectors except λ , which is a scalar. The symbol z is only used to simplify the notation and does not need to represent an optimization variable. The variable v is deﬁned for each state and represents the value function. Matrix A represents constraints that are identical to the constraints in Eq. (2). The variables λ correspond to all state-action pairs. These variables represent the Bellman residuals that are being minimized. The variables θ are deﬁned for all state-action pairs and represent policies in Remark 3. The matrix B represents the following constraints: θ(s, a) = 1 ∀s ∈ S. a∈A As with approximate linear programs, we initially assume that all the constraints on z are used. In realistic settings, however, the constraints would be sampled or somehow reduced. We defer the discussion of this issue until Section 6. Note that the constraints in our formulation correspond to elements of z and θ. Thus when constraints are omitted, also the corresponding elements of z and θ are omitted. To simplify the notation, the value function approximation in this problem is denoted only implicitly by v ∈ M, and the policy approximation is denoted by θ ∈ N . In an actual implementation, the optimization variables would be x, y using the relationships v = M x and θ = N y. We do not assume any approximation of the policy space, unless mentioned otherwise. We also use v or θ to refer to partial solutions of Eq. (4) with the other variables chosen appropriately to achieve feasibility. The ABP formulation is closely related to approximate linear programs, and we discuss the connection in Section 5. We ﬁrst analyze the properties of the optimal solutions of the bilinear program and then show and discuss the solution methods in Section 4. The following theorem states the main property of the bilinear formulation. ˜˜ ˜ ˜ Theorem 5. b Let (θ, v , λ, λ ) be an optimal solution of Eq. (4) and assume that 1 ∈ M. Then: ˜ ˜ ˜ θT λ + λ = L˜ − v v ˜ ∞ ≤ min v∈K∩M Lv − v ∞ ≤ 2 min Lv − v v∈M ∞ ≤ 2(1 + γ) min v − v ∗ v∈M ∞. ˜ In addition, π θ minimizes the Bellman residual with regard to v , and its value function v satisﬁes: ˜ ˆ 2 min Lv − v ∞ . v − v∗ ∞ ≤ ˆ 1 − γ v∈M The proof of the theorem can be found in [19]. It is important to note that, as Theorem 5 states, the ABP approach is equivalent to a minimization over all representable value functions, not only the transitive-feasible ones. Notice also the missing coefﬁcient 2 (2 instead of 4) in the last equation of Theorem 5. This follows by subtracting a constant vector 1 from v to balance the lower bounds ˜ on the Bellman residual error with the upper ones. This modiﬁed approximate value function will have 1/2 of the original Bellman residual but an identical greedy policy. Finally, note that whenever v ∗ ∈ M, both ABP and ALP will return the optimal value function. The ABP solution minimizes the L∞ norm of the Bellman residual due to: 1) the correspondence between θ and the policies, and 2) the dual representation with respect to variables λ and λ . The theorem then follows using techniques similar to those used for approximate linear programs [7]. 4 Algorithm 1: Iterative algorithm for solving Eq. (3) (x0 , w0 ) ← random ; (y0 , z0 ) ← arg miny,z f (w0 , x0 , y, z) ; i←1; while yi−1 = yi or xi−1 = xi do (yi , zi ) ← arg min{y,z A2 y+B2 z=b2 y,z≥0} f (wi−1 , xi−1 , y, z) ; (xi , wi ) ← arg min{x,w A1 x+B1 w=b1 x,w≥0} f (w, x, yi , zi ) ; i←i+1 return f (wi , xi , yi , zi ) 4 Solving Bilinear Programs In this section we describe simple methods for solving ABPs. We ﬁrst describe optimal methods, which have exponential complexity, and then discuss some approximation strategies. Solving a bilinear program is an NP-complete problem [3]. The membership in NP follows from the ﬁnite number of basic feasible solutions of the individual linear programs, each of which can be checked in polynomial time. The NP-hardness is shown by a reduction from the SAT problem [3]. The NP-completeness of ABP compares unfavorably with the polynomial complexity of ALP. However, most other ADP algorithms are not guaranteed to converge to a solution in ﬁnite time. The following theorem shows that the computational complexity of the ABP formulation is asymptotically the same as the complexity of the problem it solves. Theorem 6. b Determining minv∈K∩M Lv − v ∞ < is NP-complete for the full constraint representation, 0 < γ < 1, and a given > 0. In addition, the problem remains NP-complete when 1 ∈ M, and therefore minv∈M Lv − v ∞ < is also NP-complete. As the theorem states, the value function approximation does not become computationally simpler even when 1 ∈ M – a universal assumption in the paper. Notice that ALP can determine whether minv∈K∩M Lv − v ∞ = 0 in polynomial time. The proof of Theorem 6 is based on a reduction from SAT and can be found in [19]. The policy in the reduction determines the true literal in each clause, and the approximate value function corresponds to the truth value of the literals. The approximation basis forces literals that share the same variable to have consistent values. Bilinear programs are non-convex and are typically solved using global optimization techniques. The common solution methods are based on concave cuts [11] or branch-and-bound [6]. In ABP settings with a small number of features, the successive approximation algorithm [17] may be applied efﬁciently. We are, however, not aware of commercial solvers available for solving bilinear programs. Bilinear programs can be formulated as concave quadratic minimization problems [11], or mixed integer linear programs [11, 16], for which there are numerous commercial solvers available. Because we are interested in solving very large bilinear programs, we describe simple approximate algorithms next. Optimal scalable methods are beyond the scope of this paper. The most common approximate method for solving bilinear programs is shown in Algorithm 1. It is designed for the general formulation shown in Eq. (3), where f (w, x, y, z) represents the objective function. The minimizations in the algorithm are linear programs which can be easily solved. Interestingly, as we will show in Section 5, Algorithm 1 applied to ABP generalizes a version of API. While Algorithm 1 is not guaranteed to ﬁnd an optimal solution, its empirical performance is often remarkably good [13]. Its basic properties are summarized by the following proposition. Proposition 7 (e.g. [3]). Algorithm 1 is guaranteed to converge, assuming that the linear program solutions are in a vertex of the optimality simplex. In addition, the global optimum is a ﬁxed point of the algorithm, and the objective value monotonically improves during execution. 5 The proof is based on the ﬁnite count of the basic feasible solutions of the individual linear programs. Because the objective function does not increase in any iteration, the algorithm will eventually converge. In the context of MDPs, Algorithm 1 can be further reﬁned. For example, the constraint v ∈ M in Eq. (4) serves mostly to simplify the bilinear program and a value function that violates it may still be acceptable. The following proposition motivates the construction of a new value function from two transitive-feasible value functions. Proposition 8. Let v1 and v2 be feasible value functions in Eq. (4). Then the value function ˜ ˜ v (s) = min{˜1 (s), v2 (s)} is also feasible in Eq. (4). Therefore v ≥ v ∗ and v ∗ − v ∞ ≤ ˜ v ˜ ˜ ˜ min { v ∗ − v1 ∞ , v ∗ − v2 ∞ }. ˜ ˜ The proof of the proposition is based on Jensen’s inequality and can be found in [19]. Proposition 8 can be used to extend Algorithm 1 when solving ABPs. One option is to take the state-wise minimum of values from multiple random executions of Algorithm 1, which preserves the transitive feasibility of the value function. However, the increasing number of value functions used to obtain v also increases the potential sampling error. ˜ 5 Relationship to ALP and API In this section, we describe the important connections between ABP and the two closely related ADP methods: ALP, and API with L∞ minimization. Both of these methods are commonly used, for example to solve factored MDPs [10]. Our analysis sheds light on some of their observed properties and leads to a new convergent form of API. ABP addresses some important issues with ALP: 1) ALP provides value function bounds with respect to L1 norm, which does not guarantee small policy loss, 2) ALP’s solution quality depends signiﬁcantly on the heuristically-chosen objective function c in Eq. (2) [7], and 3) incomplete constraint samples in ALP easily lead to unbounded linear programs. The drawback of using ABP, however, is the higher computational complexity. Both the ﬁrst and the second issues in ALP can be addressed by choosing the right objective function [7]. Because this objective function depends on the optimal ALP solution, it cannot be practically computed. Instead, various heuristics are usually used. The heuristic objective functions may lead to signiﬁcant improvements in speciﬁc domains, but they do not provide any guarantees. ABP, on the other hand, has no such parameters that require adjustments. The third issue arises when the constraints of an ALP need to be sampled in some large domains. The ALP may become unbounded with incomplete samples because its objective value is deﬁned using the L1 norm on the states, and the constraints are deﬁned using the L∞ norm of the Bellman residual. In ABP, the Bellman residual is used in both the constraints and objective function. The objective function of ABP is then bounded below by 0 for an arbitrarily small number of samples. ABP can also improve on API with L∞ minimization (L∞ -API for short), which is a leading method for solving factored MDPs [10]. Minimizing the L∞ approximation error is theoretically preferable, since it is compatible with the existing bounds on policy loss [10]. In contrast, few practical bounds exist for API with the L2 norm minimization [14], such as LSPI [12]. L∞ -API is shown in Algorithm 2, where f (π) is calculated using the following program: minimize φ φ,v s.t. (I − γPπ )v + 1φ ≥ rπ −(I − γPπ )v + 1φ ≥ −rπ (5) v∈M Here I denotes the identity matrix. We are not aware of a convergence or a divergence proof of L∞ -API, and this analysis is beyond the scope of this paper. 6 Algorithm 2: Approximate policy iteration, where f (π) denotes a custom value function approximation for the policy π. π0 , k ← rand, 1 ; while πk = πk−1 do vk ← f (πk−1 ) ; ˜ πk (s) ← arg maxa∈A r(s, a) + γ s ∈S P (s , s, a)˜k (s) ∀s ∈ S ; v k ←k+1 We propose Optimistic Approximate Policy Iteration (OAPI), a modiﬁcation of API. OAPI is shown in Algorithm 2, where f (π) is calculated using the following program: minimize φ φ,v s.t. Av ≥ b (≡ (I − γPπ )v ≥ rπ ∀π ∈ Π) −(I − γPπ )v + 1φ ≥ −rπ (6) v∈M In fact, OAPI corresponds to Algorithm 1 applied to ABP because Eq. (6) corresponds to Eq. (4) with ﬁxed θ. Then, using Proposition 7, we get the following corollary. Corollary 9. Optimistic approximate policy iteration converges in ﬁnite time. In addition, the Bellman residual of the generated value functions monotonically decreases. OAPI differs from L∞ -API in two ways: 1) OAPI constrains the Bellman residuals by 0 from below and by φ from above, and then it minimizes φ. L∞ -API constrains the Bellman residuals by φ from both above and below. 2) OAPI, like API, uses only the current policy for the upper bound on the Bellman residual, but uses all the policies for the lower bound on the Bellman residual. L∞ -API cannot return an approximate value function that has a lower Bellman residual than ABP, given the optimality of ABP described in Theorem 5. However, even OAPI, an approximate ABP algorithm, performs comparably to L∞ -API, as the following theorem states. Theorem 10. b Assume that L∞ -API converges to a policy π and a value function v that both φ satisfy: φ = v − Lπ v ∞ = v − Lv ∞ . Then v = v + 1−γ 1 is feasible in Eq. (4), and it is a ﬁxed ˜ point of OAPI. In addition, the greedy policies with respect to v and v are identical. ˜ The proof is based on two facts. First, v is feasible with respect to the constraints in Eq. (4). The ˜ Bellman residual changes for all the policies identically, since a constant vector is added. Second, because Lπ is greedy with respect to v , we have that v ≥ Lπ v ≥ L˜. The value function v is ˜ ˜ ˜ v ˜ therefore transitive-feasible. The full proof can be found in [19]. To summarize, OAPI guarantees convergence, while matching the performance of L∞ -API. The convergence of OAPI is achieved because given a non-negative Bellman residual, the greedy policy also minimizes the Bellman residual. Because OAPI ensures that the Bellman residual is always non-negative, it can progressively reduce it. In comparison, the greedy policy in L∞ -API does not minimize the Bellman residual, and therefore L∞ -API does not always reduce it. Theorem 10 also explains why API provides better solutions than ALP, as observed in [10]. From the discussion above, ALP can be seen as an L1 -norm approximation of a single iteration of OAPI. L∞ -API, on the other hand, performs many such ALP-like iterations. 6 Empirical Evaluation As we showed in Theorem 10, even OAPI, the very simple approximate algorithm for ABP, can perform as well as existing state-of-the art methods on factored MDPs. However, a deeper understanding of the formulation and potential solution methods will be necessary in order to determine the full practical impact of the proposed methods. In this section, we validate the approach by applying it to the mountain car problem, a simple reinforcement learning benchmark problem. We have so far considered that all the constraints involving z are present in the ABP in Eq. (4). Because the constraints correspond to all state-action pairs, it is often impractical to even enumerate 7 (a) L∞ error of the Bellman residual Features 100 144 OAPI 0.21 (0.23) 0.13 (0.1) ALP 13. (13.) 3.6 (4.3) LSPI 9. (14.) 3.9 (7.7) API 0.46 (0.08) 0.86 (1.18) (b) L2 error of the Bellman residual Features 100 144 OAPI 0.2 (0.3) 0.1 (1.9) ALP 9.5 (18.) 0.3 (0.4) LSPI 1.2 (1.5) 0.9 (0.1) API 0.04 (0.01) 0.08 (0.08) Table 1: Bellman residual of the ﬁnal value function. The values are averages over 5 executions, with the standard deviations shown in parentheses. them. This issue can be addressed in at least two ways. First, a small randomly-selected subset of the constraints can be used in the ABP, a common approach in ALP [9, 5]. The ALP sampling bounds can be easily extended to ABP. Second, the structure of the MDP can be used to reduce the number of constraints. Such a reduction is possible, for example, in factored MDPs with L∞ -API and ALP [10], and can be easily extended to OAPI and ABP. In the mountain-car benchmark, an underpowered car needs to climb a hill [23]. To do so, it ﬁrst needs to back up to an opposite hill to gain sufﬁcient momentum. The car receives a reward of 1 when it climbs the hill. In the experiments we used a discount factor γ = 0.99. The experiments are designed to determine whether OAPI reliably minimizes the Bellman residual in comparison with API and ALP. We use a uniformly-spaced linear spline to approximate the value function. The constraints were based on 200 uniformly sampled states with all 3 actions per state. We evaluated the methods with the number of the approximation features 100 and 144, which corresponds to the number of linear segments. The results of ABP (in particular OAPI), ALP, API with L2 minimization, and LSPI are depicted in Table 1. The results are shown for both L∞ norm and uniformly-weighted L2 norm. The runtimes of all these methods are comparable, with ALP being the fastest. Since API (LSPI) is not guaranteed to converge, we ran it for at most 20 iterations, which was an upper bound on the number of iterations of OAPI. The results demonstrate that ABP minimizes the L∞ Bellman residual much more consistently than the other methods. Note, however, that all the considered algorithms would perform signiﬁcantly better given a ﬁner approximation. 7 Conclusion and Future Work We proposed and analyzed approximate bilinear programming, a new value-function approximation method, which provably minimizes the L∞ Bellman residual. ABP returns the optimal approximate value function with respect to the Bellman residual bounds, despite the formulation with regard to transitive-feasible value functions. We also showed that there is no asymptotically simpler formulation, since ﬁnding the closest value function and solving a bilinear program are both NP-complete problems. Finally, the formulation leads to the development of OAPI, a new convergent form of API which monotonically improves the objective value function. While we only discussed approximate solutions of the ABP, a deeper study of bilinear solvers may render optimal solution methods feasible. ABPs have a small number of essential variables (that determine the value function) and a large number of constraints, which can be leveraged by the solvers [15]. The L∞ error bound provides good theoretical guarantees, but it may be too conservative in practice. A similar formulation based on L2 norm minimization may be more practical. We believe that the proposed formulation will help to deepen the understanding of value function approximation and the characteristics of existing solution methods, and potentially lead to the development of more robust and widely-applicable reinforcement learning algorithms. Acknowledgements This work was supported by the Air Force Ofﬁce of Scientiﬁc Research under Grant No. FA955008-1-0171. We also thank the anonymous reviewers for their useful comments. 8 References [1] Pieter Abbeel, Varun Ganapathi, and Andrew Y. Ng. Learning vehicular dynamics, with application to modeling helicopters. In Advances in Neural Information Processing Systems, pages 1–8, 2006. [2] Daniel Adelman. A price-directed approach to stochastic inventory/routing. Operations Research, 52:499–514, 2004. [3] Kristin P. Bennett and O. L. Mangasarian. Bilinear separation of two sets in n-space. Technical report, Computer Science Department, University of Wisconsin, 1992. [4] Dimitri P. Bertsekas and Sergey Ioffe. Temporal differences-based policy iteration and applications in neuro-dynamic programming. Technical Report LIDS-P-2349, LIDS, 1997. [5] Guiuseppe Calaﬁore and M.C. Campi. Uncertain convex programs: Randomized solutions and conﬁdence levels. Mathematical Programming, Series A, 102:25–46, 2005. [6] Alberto Carpara and Michele Monaci. Bidimensional packing by bilinear programming. Mathematical Programming Series A, 118:75–108, 2009. [7] Daniela P. de Farias. The Linear Programming Approach to Approximate Dynamic Programming: Theory and Application. PhD thesis, Stanford University, 2002. [8] Daniela P. de Farias and Ben Van Roy. The linear programming approach to approximate dynamic programming. Operations Research, 51:850–856, 2003. [9] Daniela Pucci de Farias and Benjamin Van Roy. On constraint sampling in the linear programming approach to approximate dynamic programming. Mathematics of Operations Research, 29(3):462–478, 2004. [10] Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efﬁcient solution algorithms for factored MDPs. Journal of Artiﬁcial Intelligence Research, 19:399–468, 2003. [11] Reiner Horst and Hoang Tuy. Global optimization: Deterministic approaches. Springer, 1996. [12] Michail G. Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of Machine Learning Research, 4:1107–1149, 2003. [13] O. L. Mangasarian. The linear complementarity problem as a separable bilinear program. Journal of Global Optimization, 12:1–7, 1995. [14] Remi Munos. Error bounds for approximate policy iteration. In International Conference on Machine Learning, pages 560–567, 2003. [15] Marek Petrik and Shlomo Zilberstein. Anytime coordination using separable bilinear programs. In Conference on Artiﬁcial Intelligence, pages 750–755, 2007. [16] Marek Petrik and Shlomo Zilberstein. Average reward decentralized Markov decision processes. In International Joint Conference on Artiﬁcial Intelligence, pages 1997–2002, 2007. [17] Marek Petrik and Shlomo Zilberstein. A bilinear programming approach for multiagent planning. Journal of Artiﬁcial Intelligence Research, 35:235–274, 2009. [18] Marek Petrik and Shlomo Zilberstein. Constraint relaxation in approximate linear programs. In International Conference on Machine Learning, pages 809–816, 2009. [19] Marek Petrik and Shlomo Zilberstein. Robust value function approximation using bilinear programming. Technical Report UM-CS-2009-052, Department of Computer Science, University of Massachusetts Amherst, 2009. [20] Warren B. Powell. Approximate Dynamic Programming. Wiley-Interscience, 2007. [21] Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, Inc., 2005. [22] Kenneth O. Stanley and Risto Miikkulainen. Competitive coevolution through evolutionary complexiﬁcation. Journal of Artiﬁcial Intelligence Research, 21:63–100, 2004. [23] Richard S. Sutton and Andrew Barto. Reinforcement learning. MIT Press, 1998. [24] Istvan Szita and Andras Lorincz. Learning Tetris using the noisy cross-entropy method. Neural Computation, 18(12):2936–2941, 2006. [25] Ronald J. Williams and Leemon C. Baird. Tight performance bounds on greedy policies based on imperfect value functions. In Yale Workshop on Adaptive and Learning Systems, 1994. 9

same-paper 5 0.9171353 219 nips-2009-Slow, Decorrelated Features for Pretraining Complex Cell-like Networks

Author: Yoshua Bengio, James S. Bergstra

6 0.89905596 34 nips-2009-Anomaly Detection with Score functions based on Nearest Neighbor Graphs

7 0.71084523 159 nips-2009-Multi-Step Dyna Planning for Policy Evaluation and Control

8 0.69169044 23 nips-2009-Accelerating Bayesian Structural Inference for Non-Decomposable Gaussian Graphical Models

9 0.67604131 30 nips-2009-An Integer Projected Fixed Point Method for Graph Matching and MAP Inference

10 0.67370015 28 nips-2009-An Additive Latent Feature Model for Transparent Object Recognition

11 0.67304301 113 nips-2009-Improving Existing Fault Recovery Policies

12 0.67258656 131 nips-2009-Learning from Neighboring Strokes: Combining Appearance and Context for Multi-Domain Sketch Recognition

13 0.67077017 100 nips-2009-Gaussian process regression with Student-t likelihood

14 0.6689356 167 nips-2009-Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations

15 0.66747087 187 nips-2009-Particle-based Variational Inference for Continuous Systems

16 0.66255379 151 nips-2009-Measuring Invariances in Deep Networks

17 0.65832055 3 nips-2009-AUC optimization and the two-sample problem

18 0.65392447 250 nips-2009-Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference

19 0.65382195 31 nips-2009-An LP View of the M-best MAP problem

20 0.64247823 162 nips-2009-Neural Implementation of Hierarchical Bayesian Inference by Importance Sampling