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

46 nips-2009-Bilinear classifiers for visual recognition

Source: pdf

Author: Hamed Pirsiavash, Deva Ramanan, Charless C. Fowlkes

Abstract: We describe an algorithm for learning bilinear SVMs. Bilinear classiﬁers are a discriminative variant of bilinear models, which capture the dependence of data on multiple factors. Such models are particularly appropriate for visual data that is better represented as a matrix or tensor, rather than a vector. Matrix encodings allow for more natural regularization through rank restriction. For example, a rank-one scanning-window classiﬁer yields a separable ﬁlter. Low-rank models have fewer parameters and so are easier to regularize and faster to score at run-time. We learn low-rank models with bilinear classiﬁers. We also use bilinear classiﬁers for transfer learning by sharing linear factors between different classiﬁcation tasks. Bilinear classiﬁers are trained with biconvex programs. Such programs are optimized with coordinate descent, where each coordinate step requires solving a convex program - in our case, we use a standard off-the-shelf SVM solver. We demonstrate bilinear SVMs on difﬁcult problems of people detection in video sequences and action classiﬁcation of video sequences, achieving state-of-the-art results in both. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract We describe an algorithm for learning bilinear SVMs. [sent-3, score-0.315]

2 Bilinear classiﬁers are a discriminative variant of bilinear models, which capture the dependence of data on multiple factors. [sent-4, score-0.315]

3 We also use bilinear classiﬁers for transfer learning by sharing linear factors between different classiﬁcation tasks. [sent-10, score-0.433]

4 Such programs are optimized with coordinate descent, where each coordinate step requires solving a convex program - in our case, we use a standard off-the-shelf SVM solver. [sent-12, score-0.197]

5 We demonstrate bilinear SVMs on difﬁcult problems of people detection in video sequences and action classiﬁcation of video sequences, achieving state-of-the-art results in both. [sent-13, score-0.709]

6 We focus here on the task of visual recognition in video - “does this spatiotemporal window contain an object”? [sent-18, score-0.293]

7 More generally, one can deﬁne multilinear models [25] that are linear in one factor conditioned on the others. [sent-24, score-0.202]

8 Inspired by the success of bilinear models in data modeling, we introduce discriminative bilinear models for classiﬁcation. [sent-25, score-0.63]

9 We describe a method for training bilinear (multilinear) SVMs with biconvex (multiconvex) programs. [sent-26, score-0.55]

10 A function f : X × Y → R is called biconvex if f (x, y) is convex in y for ﬁxed x ∈ X and is convex in x for ﬁxed y ∈ Y . [sent-27, score-0.307]

11 While not convex, they admit efﬁcient coordinate descent algorithms that solve a convex program at each step. [sent-29, score-0.144]

12 We show bilinear SVM classiﬁers can be optimized with an off-the-shelf linear SVM solver. [sent-30, score-0.346]

13 This is advantageous because we can leverage large-scale, highly-tuned solvers (we use [13]) to learn bilinear classiﬁers with tens of thousands of features with hundreds of millions of examples. [sent-31, score-0.315]

14 While bilinear models are often motivated from the perspective of increasing the ﬂexibility of a linear model, our motivation is reversed - we use them to reduce the number of parameters of a 1 Figure 1: Many approaches for visual recognition employ linear classiﬁers on scanned windows. [sent-32, score-0.399]

15 [26] show that one can produce more meaningful schemes for regularization and parameter reduction through low-rank approximations of a tensor model. [sent-37, score-0.138]

16 Our contribution involves casting the resulting learning problem as a biconvex optimization. [sent-38, score-0.235]

17 We also demonstrate that bilinear models have additional advantages for transfer learning and run-time efﬁciency. [sent-40, score-0.396]

18 weight vector that is naturally represented as a matrix or tensor W . [sent-41, score-0.138]

19 Finally, by sharing factors across different classiﬁcation problems, we introduce a novel formulation of transfer learning. [sent-48, score-0.162]

20 We believe that transfer through shared factors is an important beneﬁt of multilinear classiﬁers which can help ameliorate overﬁtting. [sent-49, score-0.317]

21 We then explicitly deﬁne our bilinear classiﬁer in Sec. [sent-52, score-0.315]

22 We illustrate several applications and motivations for the bilinear framework in Sec. [sent-54, score-0.315]

23 5, We describe extensions to our model for the multilinear and multiclass case. [sent-57, score-0.202]

24 We provide several experiments on visual recognition in the video domain in Sec. [sent-58, score-0.192]

25 6, signiﬁcantly improving on the state-of-the-art system for ﬁnding people in video sequences [7] both in performance and speed. [sent-59, score-0.144]

26 We also illustrate our approach on the task of action recognition, showing that transfer learning can ameliorate the small-sample problem that plagues current benchmark datasets [18, 19]. [sent-60, score-0.224]

27 2 Related Work Tenenbaum and Freeman [23] introduced bilinear models into the vision community to model data generated from multiple linear factors. [sent-61, score-0.315]

28 Such methods have been extended to the multilinear setting, e. [sent-62, score-0.202]

29 Recent work has explored extensions of tensor models to discriminant analysis [22, 27], while our work focuses on an efﬁcient max-margin formulation of multilinear models. [sent-65, score-0.384]

30 They analyze the VC dimension of rank constrained linear classiﬁers and demonstrate an iterative weighting algorithm for approximately solving an SVM problem in which the rank of W acts as a regularizer. [sent-77, score-0.15]

31 The Dalal and Triggs detector [6] is a particularly popular pedestrian detector where x is naturally represented as a concatenation of histogram of gradient (HOG) feature vectors extracted from a spatial grid of ny × nx , where each local HOG descriptor is itself composed of nf features. [sent-91, score-0.584]

32 In this case, it is natural to represent an example x as a tensor X ∈ Rny ×nx ×nf . [sent-92, score-0.138]

33 For ease of exposition, we develop the mathematics for a simpler matrix representation, ﬁxing nf = 1. [sent-93, score-0.175]

34 We show that one can obtain a biconvex objective function by enforcing a hard restriction on the rank. [sent-99, score-0.281]

35 Speciﬁcally, we enforce the rank of W to be at most d ≤ min(ny , nx ). [sent-100, score-0.212]

36 This allows us to write the ﬁnal predictor explicitly as the following bilinear function: T T fWy ,Wx (X) = Tr(Wy Wx X) = Tr(Wy XWx ). [sent-102, score-0.315]

37 1 (3) (4) Learning Assume we are given a set of training data and label pairs {xn , yn }. [sent-104, score-0.139]

38 We can rewrite the linear SVM formulation for w and xn with matrices W and Xn using the trace operator. [sent-107, score-0.182]

39 (5) 2 n L(W ) = 1 Tr(W T W ) + C 2 max(0, 1 − yn Tr(W T Xn )). [sent-109, score-0.139]

40 n 3 (6) The above formulations are identical when w and xn are the vectorized elements of matrices W and T Xn . [sent-110, score-0.217]

41 Plugging in W = Wy Wx , we obtain our biconvex objective function: 1 T T T L(Wy , Wx ) = Tr(Wx Wy Wy Wx ) + C max(0, 1 − yn Tr(Wx Wy Xn )). [sent-113, score-0.374]

42 2 Coordinate descent We can optimize (7) with a coordinate descent algorithm that solves for one set of parameters holding the other ﬁxed. [sent-117, score-0.151]

43 Speciﬁcally, consider min L(Wy , Wx ) = Wy 1 T Tr(Wy AWy ) + C 2 T max(0, 1 − yn Tr(Wy Xn Wx )). [sent-119, score-0.139]

44 To do so, let us reparametrize Wy as Wy : 1 ˜ ˜T ˜ min L(Wy , Wx ) = Tr(Wy Wy ) + C ˜ 2 Wy where 1 ˜ Wy = Wy A 2 and ˜T ˜ max(0, 1 − yn Tr(Wy Xn )) (9) n 1 ˜ Xn = Xn Wx A− 2 and T A = Wx Wx . [sent-121, score-0.139]

45 4 Motivation We outline here a number of motivations for the biconvex objective function deﬁned above. [sent-127, score-0.235]

46 Image windows are naturally represented as a 3D tensor X ∈ Rny ×nx ×nf , where nf is the dimensionality of a HOG feature. [sent-133, score-0.313]

47 Let us “reshape” X into a 2D matrix X ∈ Rnxy ×nf where nxy = nx ny . [sent-134, score-0.216]

48 Wxy ∈ Rnxy ×d is equivalent to a vectorized spatial template deﬁned over d features at each spatial location, while Wf ∈ Rnf ×d deﬁnes a set of d basis vectors spanning Rnf . [sent-136, score-0.206]

49 In our biconvex formulation, the basis vectors are not constrained to be orthogonal, but they are learned discriminatively and jointly with the template Wxy . [sent-138, score-0.374]

50 For example, the product Tr(W T X) can be computed for all image windows X with nf convolutions. [sent-143, score-0.175]

51 One can further improve efﬁciency by using the same 4 d-dimensional feature space for a large number of different object templates - this is precisely the basis of our transfer approach in Sec. [sent-145, score-0.152]

52 For example, spatio-temporal templates for ﬁnding objects in video tend to have large nf since multiple features are extracted from each time-slice. [sent-149, score-0.391]

53 This can result in signiﬁcant savings because computing the score at the window is now O(nx + ny ) rather than O(nx ny ). [sent-154, score-0.122]

54 3 Transfer m Assume we wish to train M predictors and are given {xm , yn } training data pairs for each prediction n problem 1 ≤ m ≤ M . [sent-156, score-0.139]

55 , W M ) = Tr(W m W m ) + Cm max(0, 1 − yn Tr(W m Xn )). [sent-160, score-0.139]

56 To transfer knowledge between the classiﬁcation tasks, we require all tasks to use the same low-dimensional subspace projection by sharing the same feature matrix: m T W m = Wxy Wf m Note that the leading dimension of can depend on m. [sent-163, score-0.152]

57 Given a ﬁxed set of Wxy , a single matrix Wf is learned for all classes by computing: 1 m 1 M ˜T ˜ ˜ T ˜m ˜ Cm max(0, 1 − yn Tr(Wf Xn )) min L(Wf , Wxy , . [sent-170, score-0.139]

58 In practice, nf can be large for spatio-temporal features extracted from multiple temporal windows. [sent-176, score-0.212]

59 The above formulation is convenient in that we can use data examples from many classiﬁcation tasks to learn a good subspace for spatiotemporal features. [sent-177, score-0.147]

60 For example, spatio-temporal templates are naturally represented as a 4th -order tensor capturing the width, height, temporal extent, and the feature dimension of a spatio-temporal window. [sent-180, score-0.209]

61 (11) ijk With the above deﬁnition, we can generalize our trace-based objective function (6) to higher-order tensors: 1 W, W + C max(0, 1 − yn W, Xn ). [sent-184, score-0.139]

62 (12) L(W ) = 2 n 5 We wish to impose a rank restriction on the tensor W . [sent-185, score-0.259]

63 The notion of rank for tensors of order greater than two is subtle - for example, there are alternate approaches for deﬁning a high-order SVD [25, 15]. [sent-186, score-0.125]

64 For our purposes, we follow [20] and deﬁne W as a rank d tensor by writing it as product of matrices W y ∈ Rny ×d , W x ∈ Rnx ×d , W t ∈ Rnt ×d : d y x t wis wjs wks . [sent-187, score-0.213]

65 This rank restriction forces the spatio-temporal template W to be separable in along the x, y, and t axes, allowing for window-scan scoring by three onedimensional convolutions. [sent-193, score-0.296]

66 Structural SVMs learn models that predict a structured label yn given a data point xn . [sent-197, score-0.277]

67 Given training data of the form {xn , yn }, the learning problem is: L(w) = where 1 T w w+C 2 max(l(yn , y) − wT ∆φ(xn , yn , y)) n y (14) ∆φ(xn , yn , y) = φ(xn , yn ) − φ(xn , y), and where l(yn , y) is the loss of assigning example i with label y given that its true label is yn . [sent-198, score-0.695]

68 The corresponding φ(x, y) will be a sparse vector with nx nonzero values at those indices associated with the y th class. [sent-205, score-0.137]

69 We can enforce W to be T of rank d < min(nc , nx ) by deﬁning W = Wc Wx where Wc ∈ Rnc ×d and Wx ∈ Rnx ×d . [sent-207, score-0.212]

70 For example, one may expect template classiﬁers that classify nc different human actions to reside in a d dimensional subspace. [sent-208, score-0.145]

71 The resulting biconvex objective function is L(Wc , Wx ) = 1 T T Tr(Wx Wc Wc Wx ) + C 2 T max(l(yn , y) − Tr(Wx Wc Φ(Xn , yn , y)). [sent-209, score-0.374]

72 y n (15) Using our previous arguments, it is straightforward to show that the above objective is biconvex and that each step of the coordinate descent algorithm reduces to a standard structural SVM problem. [sent-210, score-0.372]

73 We illustrate our method on two challenging tasks using two benchmark datasets - detecting pedestrians in video sequences from the INRIA-Motion database [7] and classifying human actions in UCF-Sports dataset [18]. [sent-213, score-0.188]

74 We model features computed from frame pairs x as matrices X ∈ Rnxy ×nf , where nxy = nx ny is the vectorized spatial template and nf is the dimensionality of our combined gradient and ﬂow feature space. [sent-214, score-0.565]

75 Our bilinear model T learns a classiﬁer of the form Wxy Wf where Wxy ∈ Rnxy ×d and Wf ∈ Rnf ×d . [sent-216, score-0.315]

76 Typical values include ny = 14, nx = 6, nf = 84, and d = 5 or 10. [sent-217, score-0.357]

77 We opt for the scoring criteria outlined by the widely-acknowledged PASCAL competition [10], which looks at average precision (AP) results obtained after running the detector on cluttered video sequences and suppressing overlapping detections. [sent-221, score-0.228]

78 Surprisingly, when scoring AP for person detection in the INRIA-motion dataset, we ﬁnd the spatiotemporal model performed worse than the static-image model. [sent-224, score-0.134]

79 We also compare results with an additional rank-reduced baseline obtained by setting wf to the basis returned by a PCA projection of the feature space from nf to d dimensions. [sent-228, score-0.426]

80 We use this PCA basis to initialize our coordinate descent algorithm when training our bilinear models. [sent-229, score-0.423]

81 We refer the reader to the caption for a detailed analysis, but our bilinear optimization seems to produce the state-of-the-art system for ﬁnding people in video sequences, while being an order-of-magnitude faster than previous approaches. [sent-232, score-0.423]

82 2 Human action classiﬁcation Action classiﬁcation requires labeling a video sequence with one of nc action labels. [sent-234, score-0.373]

83 We do this by training nc 1-vs-all action templates. [sent-235, score-0.156]

84 Template detections from a video sequence are pooled together to output a ﬁnal action label. [sent-236, score-0.249]

85 Our future plan is to integrate the video class directly into the training procedure using our bilinear structural SVM formulation. [sent-238, score-0.452]

86 Using 2-fold cross validation (and hence signiﬁcantly less training data), our bilinear template achieves a score of 64. [sent-245, score-0.413]

87 We consider a smallsample scenario when one has only two example video sequences of each action class. [sent-252, score-0.253]

88 Under this scenario, we train one bilinear model in which the feature basis Wf is optimized independently for each action class, and another where the basis is shared across all classes. [sent-253, score-0.455]

89 7 Conclusion We have introduced a generic framework for multilinear classiﬁers that are efﬁcient to train with existing linear solvers. [sent-256, score-0.202]

90 Multilinear classiﬁers exploit the natural matrix and/or tensor representation of spatiotemporal data. [sent-257, score-0.207]

91 In our future experiments, we wish to demonstrate transfer between domains such as pedestrian detection and action classiﬁcation. [sent-260, score-0.277]

92 Using our bilinear formulation with the same low-dimensional restriction, we obtain better performance than the original detector while being 10X faster. [sent-277, score-0.411]

93 We show example detections on video clips on the right. [sent-278, score-0.14]

94 Our bilinear model provides a strong improvement over both the linear and PCA baselines. [sent-284, score-0.315]

95 356 Figure 4: We show results for transfer learning on the UCF action recognition dataset with limited training data - 2 training videos for each of 12 action classes. [sent-293, score-0.347]

96 In the top table row, we show results for independently learning a subspace for each action class. [sent-294, score-0.143]

97 Note that the head and shoulders of the model are blurred out in iteration 1 which uses PCA, but after the biconvex training procedure discriminatively updates the basis, the ﬁnal model is sharper at the head and shoulders. [sent-299, score-0.276]

98 Biconvex sets and optimization with biconvex functions: a survey and extensions. [sent-386, score-0.235]

99 Non-negative tensor factorization with applications to statistics and computer vision. [sent-430, score-0.138]

100 General tensor discriminant analysis and Gabor features for gait recognition. [sent-447, score-0.138]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('bilinear', 0.315), ('wy', 0.308), ('wxy', 0.286), ('wf', 0.251), ('wx', 0.244), ('biconvex', 0.235), ('multilinear', 0.202), ('nf', 0.175), ('golf', 0.151), ('yn', 0.139), ('xn', 0.138), ('tensor', 0.138), ('nx', 0.137), ('front', 0.118), ('action', 0.109), ('video', 0.108), ('hog', 0.107), ('tr', 0.102), ('kick', 0.101), ('swing', 0.101), ('template', 0.098), ('svm', 0.085), ('ide', 0.084), ('ucf', 0.084), ('ron', 0.081), ('wc', 0.081), ('transfer', 0.081), ('ers', 0.076), ('id', 0.076), ('rank', 0.075), ('walk', 0.074), ('rnx', 0.074), ('templates', 0.071), ('classi', 0.069), ('spatiotemporal', 0.069), ('rnxy', 0.067), ('coordinate', 0.065), ('side', 0.064), ('lf', 0.063), ('rny', 0.059), ('ck', 0.056), ('pedestrian', 0.054), ('pca', 0.053), ('detector', 0.052), ('ol', 0.05), ('bench', 0.05), ('dive', 0.05), ('ick', 0.05), ('nch', 0.05), ('ont', 0.05), ('rnf', 0.05), ('skate', 0.05), ('swkate', 0.05), ('tensors', 0.05), ('ap', 0.049), ('recognition', 0.048), ('dalal', 0.048), ('ow', 0.047), ('nc', 0.047), ('restriction', 0.046), ('ny', 0.045), ('separable', 0.045), ('ors', 0.044), ('pedestrians', 0.044), ('ride', 0.044), ('vectorized', 0.044), ('formulation', 0.044), ('descent', 0.043), ('wolf', 0.042), ('discriminatively', 0.041), ('histograms', 0.04), ('extracted', 0.037), ('svms', 0.037), ('sharing', 0.037), ('visual', 0.036), ('sequences', 0.036), ('convex', 0.036), ('formulations', 0.035), ('wt', 0.035), ('subspace', 0.034), ('sports', 0.034), ('horse', 0.034), ('iv', 0.034), ('ameliorate', 0.034), ('ando', 0.034), ('grenoble', 0.034), ('nxy', 0.034), ('rnc', 0.034), ('xijk', 0.034), ('felzenszwalb', 0.033), ('sw', 0.033), ('detection', 0.033), ('scoring', 0.032), ('spatial', 0.032), ('window', 0.032), ('detections', 0.032), ('optimized', 0.031), ('fr', 0.03), ('fw', 0.029), ('structural', 0.029)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 46 nips-2009-Bilinear classifiers for visual recognition

Author: Hamed Pirsiavash, Deva Ramanan, Charless C. Fowlkes

2 0.15344742 50 nips-2009-Canonical Time Warping for Alignment of Human Behavior

Author: Feng Zhou, Fernando Torre

Abstract: Alignment of time series is an important problem to solve in many scientiﬁc disciplines. In particular, temporal alignment of two or more subjects performing similar activities is a challenging problem due to the large temporal scale difference between human actions as well as the inter/intra subject variability. In this paper we present canonical time warping (CTW), an extension of canonical correlation analysis (CCA) for spatio-temporal alignment of human motion between two subjects. CTW extends previous work on CCA in two ways: (i) it combines CCA with dynamic time warping (DTW), and (ii) it extends CCA by allowing local spatial deformations. We show CTW’s effectiveness in three experiments: alignment of synthetic data, alignment of motion capture data of two subjects performing similar actions, and alignment of similar facial expressions made by two people. Our results demonstrate that CTW provides both visually and qualitatively better alignment than state-of-the-art techniques based on DTW. 1

3 0.12812354 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.11862829 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

5 0.1136813 23 nips-2009-Accelerating Bayesian Structural Inference for Non-Decomposable Gaussian Graphical Models

Author: Baback Moghaddam, Emtiyaz Khan, Kevin P. Murphy, Benjamin M. Marlin

Abstract: We make several contributions in accelerating approximate Bayesian structural inference for non-decomposable GGMs. Our ﬁrst contribution is to show how to efﬁciently compute a BIC or Laplace approximation to the marginal likelihood of non-decomposable graphs using convex methods for precision matrix estimation. This optimization technique can be used as a fast scoring function inside standard Stochastic Local Search (SLS) for generating posterior samples. Our second contribution is a novel framework for efﬁciently generating large sets of high-quality graph topologies without performing local search. This graph proposal method, which we call “Neighborhood Fusion” (NF), samples candidate Markov blankets at each node using sparse regression techniques. Our third contribution is a hybrid method combining the complementary strengths of NF and SLS. Experimental results in structural recovery and prediction tasks demonstrate that NF and hybrid NF/SLS out-perform state-of-the-art local search methods, on both synthetic and real-world datasets, when realistic computational limits are imposed.

6 0.089680389 137 nips-2009-Learning transport operators for image manifolds

7 0.078598194 208 nips-2009-Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

8 0.074361928 61 nips-2009-Convex Relaxation of Mixture Regression with Efficient Algorithms

9 0.064946592 158 nips-2009-Multi-Label Prediction via Sparse Infinite CCA

10 0.064446978 201 nips-2009-Region-based Segmentation and Object Detection

11 0.061706085 87 nips-2009-Exponential Family Graph Matching and Ranking

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

13 0.056676127 64 nips-2009-Data-driven calibration of linear estimators with minimal penalties

14 0.055406537 169 nips-2009-Nonlinear Learning using Local Coordinate Coding

15 0.053315282 147 nips-2009-Matrix Completion from Noisy Entries

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

17 0.051652476 57 nips-2009-Conditional Random Fields with High-Order Features for Sequence Labeling

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

19 0.049950276 89 nips-2009-FACTORIE: Probabilistic Programming via Imperatively Defined Factor Graphs

20 0.049778361 47 nips-2009-Boosting with Spatial Regularization

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.176), (1, -0.007), (2, -0.053), (3, -0.01), (4, -0.052), (5, 0.046), (6, 0.009), (7, -0.007), (8, 0.065), (9, -0.027), (10, 0.09), (11, 0.002), (12, -0.045), (13, -0.001), (14, -0.083), (15, -0.008), (16, 0.103), (17, 0.005), (18, -0.027), (19, -0.095), (20, 0.029), (21, -0.095), (22, 0.093), (23, -0.053), (24, -0.123), (25, 0.077), (26, 0.043), (27, -0.072), (28, 0.101), (29, -0.115), (30, 0.102), (31, 0.069), (32, 0.04), (33, 0.04), (34, 0.057), (35, 0.129), (36, -0.006), (37, -0.103), (38, 0.113), (39, 0.008), (40, -0.019), (41, 0.029), (42, -0.061), (43, -0.049), (44, 0.073), (45, 0.013), (46, 0.118), (47, 0.061), (48, -0.006), (49, 0.197)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.91094935 46 nips-2009-Bilinear classifiers for visual recognition

Author: Hamed Pirsiavash, Deva Ramanan, Charless C. Fowlkes

2 0.55619985 50 nips-2009-Canonical Time Warping for Alignment of Human Behavior

Author: Feng Zhou, Fernando Torre

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

Author: Andrea Vedaldi, Andrew Zisserman

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

Author: Marek Petrik, Shlomo Zilberstein

5 0.45092571 158 nips-2009-Multi-Label Prediction via Sparse Infinite CCA

Author: Piyush Rai, Hal Daume

Abstract: Canonical Correlation Analysis (CCA) is a useful technique for modeling dependencies between two (or more) sets of variables. Building upon the recently suggested probabilistic interpretation of CCA, we propose a nonparametric, fully Bayesian framework that can automatically select the number of correlation components, and effectively capture the sparsity underlying the projections. In addition, given (partially) labeled data, our algorithm can also be used as a (semi)supervised dimensionality reduction technique, and can be applied to learn useful predictive features in the context of learning a set of related tasks. Experimental results demonstrate the efﬁcacy of the proposed approach for both CCA as a stand-alone problem, and when applied to multi-label prediction. 1

6 0.43495649 23 nips-2009-Accelerating Bayesian Structural Inference for Non-Decomposable Gaussian Graphical Models

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

8 0.41662169 182 nips-2009-Optimal Scoring for Unsupervised Learning

9 0.40196383 148 nips-2009-Matrix Completion from Power-Law Distributed Samples

10 0.37770814 16 nips-2009-A Smoothed Approximate Linear Program

11 0.37219718 208 nips-2009-Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

12 0.37195286 87 nips-2009-Exponential Family Graph Matching and Ranking

13 0.3663151 195 nips-2009-Probabilistic Relational PCA

14 0.3634041 76 nips-2009-Efficient Learning using Forward-Backward Splitting

15 0.35439977 108 nips-2009-Heterogeneous multitask learning with joint sparsity constraints

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

17 0.34455201 97 nips-2009-Free energy score space

18 0.34073272 191 nips-2009-Positive Semidefinite Metric Learning with Boosting

19 0.33761281 89 nips-2009-FACTORIE: Probabilistic Programming via Imperatively Defined Factor Graphs

20 0.3351042 33 nips-2009-Analysis of SVM with Indefinite Kernels

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(7, 0.01), (21, 0.017), (24, 0.021), (25, 0.059), (35, 0.102), (36, 0.125), (39, 0.053), (47, 0.266), (55, 0.019), (58, 0.105), (61, 0.018), (71, 0.044), (81, 0.012), (86, 0.066), (91, 0.011)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.8099786 46 nips-2009-Bilinear classifiers for visual recognition

Author: Hamed Pirsiavash, Deva Ramanan, Charless C. Fowlkes

2 0.77038866 252 nips-2009-Unsupervised Feature Selection for the $k$-means Clustering Problem

Author: Christos Boutsidis, Petros Drineas, Michael W. Mahoney

Abstract: We present a novel feature selection algorithm for the k-means clustering problem. Our algorithm is randomized and, assuming an accuracy parameter ϵ ∈ (0, 1), selects and appropriately rescales in an unsupervised manner Θ(k log(k/ϵ)/ϵ2 ) features from a dataset of arbitrary dimensions. We prove that, if we run any γ-approximate k-means algorithm (γ ≥ 1) on the features selected using our method, we can ﬁnd a (1 + (1 + ϵ)γ)-approximate partition with high probability. 1

3 0.76210374 161 nips-2009-Nash Equilibria of Static Prediction Games

Author: Michael Brückner, Tobias Scheffer

Abstract: The standard assumption of identically distributed training and test data is violated when an adversary can exercise some control over the generation of the test data. In a prediction game, a learner produces a predictive model while an adversary may alter the distribution of input data. We study single-shot prediction games in which the cost functions of learner and adversary are not necessarily antagonistic. We identify conditions under which the prediction game has a unique Nash equilibrium, and derive algorithms that will ﬁnd the equilibrial prediction models. In a case study, we explore properties of Nash-equilibrial prediction models for email spam ﬁltering empirically. 1

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

Author: Marius Leordeanu, Martial Hebert, Rahul Sukthankar

Abstract: Graph matching and MAP inference are essential problems in computer vision and machine learning. We introduce a novel algorithm that can accommodate both problems and solve them efﬁciently. Recent graph matching algorithms are based on a general quadratic programming formulation, which takes in consideration both unary and second-order terms reﬂecting the similarities in local appearance as well as in the pairwise geometric relationships between the matched features. This problem is NP-hard, therefore most algorithms ﬁnd approximate solutions by relaxing the original problem. They ﬁnd the optimal continuous solution of the modiﬁed problem, ignoring during optimization the original discrete constraints. Then the continuous solution is quickly binarized at the end, but very little attention is put into this ﬁnal discretization step. In this paper we argue that the stage in which a discrete solution is found is crucial for good performance. We propose an efﬁcient algorithm, with climbing and convergence properties, that optimizes in the discrete domain the quadratic score, and it gives excellent results either by itself or by starting from the solution returned by any graph matching algorithm. In practice it outperforms state-or-the art graph matching algorithms and it also signiﬁcantly improves their performance if used in combination. When applied to MAP inference, the algorithm is a parallel extension of Iterated Conditional Modes (ICM) with climbing and convergence properties that make it a compelling alternative to the sequential ICM. In our experiments on MAP inference our algorithm proved its effectiveness by signiﬁcantly outperforming [13], ICM and Max-Product Belief Propagation. 1

5 0.61263591 158 nips-2009-Multi-Label Prediction via Sparse Infinite CCA

Author: Piyush Rai, Hal Daume

6 0.61054289 100 nips-2009-Gaussian process regression with Student-t likelihood

7 0.61030412 35 nips-2009-Approximating MAP by Compensating for Structural Relaxations

8 0.60963249 254 nips-2009-Variational Gaussian-process factor analysis for modeling spatio-temporal data

9 0.60847265 224 nips-2009-Sparse and Locally Constant Gaussian Graphical Models

10 0.60829717 162 nips-2009-Neural Implementation of Hierarchical Bayesian Inference by Importance Sampling

11 0.60814619 61 nips-2009-Convex Relaxation of Mixture Regression with Efficient Algorithms

12 0.6078167 167 nips-2009-Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations

13 0.60752654 174 nips-2009-Nonparametric Latent Feature Models for Link Prediction

14 0.60702765 23 nips-2009-Accelerating Bayesian Structural Inference for Non-Decomposable Gaussian Graphical Models

15 0.60221362 113 nips-2009-Improving Existing Fault Recovery Policies

16 0.60204518 70 nips-2009-Discriminative Network Models of Schizophrenia

17 0.60098314 250 nips-2009-Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference

18 0.60070401 228 nips-2009-Speeding up Magnetic Resonance Image Acquisition by Bayesian Multi-Slice Adaptive Compressed Sensing

19 0.60018402 41 nips-2009-Bayesian Source Localization with the Multivariate Laplace Prior

20 0.59887582 18 nips-2009-A Stochastic approximation method for inference in probabilistic graphical models