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

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

Source: pdf

Author: Matthias Bethge, Eero P. Simoncelli, Fabian H. Sinz

Abstract: We introduce a new family of distributions, called Lp -nested symmetric distributions, whose densities are expressed in terms of a hierarchical cascade of Lp norms. This class generalizes the family of spherically and Lp -spherically symmetric distributions which have recently been successfully used for natural image modeling. Similar to those distributions it allows for a nonlinear mechanism to reduce the dependencies between its variables. With suitable choices of the parameters and norms, this family includes the Independent Subspace Analysis (ISA) model as a special case, which has been proposed as a means of deriving ﬁlters that mimic complex cells found in mammalian primary visual cortex. Lp -nested distributions are relatively easy to estimate and allow us to explore the variety of models between ISA and the Lp -spherically symmetric models. By ﬁtting the generalized Lp -nested model to 8 × 8 image patches, we show that the subspaces obtained from ISA are in fact more dependent than the individual ﬁlter coefﬁcients within a subspace. When ﬁrst applying contrast gain control as preprocessing, however, there are no dependencies left that could be exploited by ISA. This suggests that complex cell modeling can only be useful for redundancy reduction in larger image patches. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 de Abstract We introduce a new family of distributions, called Lp -nested symmetric distributions, whose densities are expressed in terms of a hierarchical cascade of Lp norms. [sent-8, score-0.234]

2 This class generalizes the family of spherically and Lp -spherically symmetric distributions which have recently been successfully used for natural image modeling. [sent-9, score-0.306]

3 Similar to those distributions it allows for a nonlinear mechanism to reduce the dependencies between its variables. [sent-10, score-0.082]

4 Lp -nested distributions are relatively easy to estimate and allow us to explore the variety of models between ISA and the Lp -spherically symmetric models. [sent-12, score-0.201]

5 By ﬁtting the generalized Lp -nested model to 8 × 8 image patches, we show that the subspaces obtained from ISA are in fact more dependent than the individual ﬁlter coefﬁcients within a subspace. [sent-13, score-0.155]

6 This suggests that complex cell modeling can only be useful for redundancy reduction in larger image patches. [sent-15, score-0.091]

7 It forms the basis not only for the design of more advanced image processing algorithms and compression schemes, but also for a better comprehension of the operations performed by the early visual 1 system and how they relate to the properties of the natural stimuli that are driving it. [sent-18, score-0.098]

8 Firstly, several authors have demonstrated that ﬁlter responses of ICA ﬁlters on natural images are not statistically independent [20; 23; 6]. [sent-23, score-0.097]

9 Secondly, after whitening, the optimum of ICA in terms of statistical independence is very shallow or, in other words, all whitening ﬁlters yield almost the same redundancy reduction [5; 2]. [sent-24, score-0.166]

10 A possible explanation for that ﬁnding is that, after whitening, densities of local image features are approximately spherical [24; 23; 12; 6]. [sent-25, score-0.167]

11 This implies that those densities cannot be made independent by ICA because (i) all whitening ﬁlters differ only by an orthogonal transformation, (ii) spherical densities are invariant under orthogonal transformations, and (iii) the only spherical and factorial distribution is the Gaussian. [sent-26, score-0.511]

12 Once local image features become more distant from each other, the contour lines of the density deviates from spherical and become more star-shaped. [sent-27, score-0.211]

13 In order to capture this star-shaped contour lines one can use the more general Lp -spherically symmetric distributions which are characterized by densities of the form χ(y) = g( y p ) with y p = ( yi p )1 p and p > 0 [9; 10; 21]. [sent-28, score-0.247]

14 5 Figure 1: Scatter plots and marginal histograms of neighboring (left) and distant (right) symmetric whitening ﬁlters which are shown at the top. [sent-32, score-0.274]

15 The dashed Contours indicate the unit sphere for the optimal p of the best ﬁtting non-factorial (dashed line) and factorial (solid line) Lp -spherically symmetric distribution, respectively. [sent-33, score-0.205]

16 While close ﬁlters exhibit p = 2 (spherically symmetric distribution), the value of p decreases for more distant ﬁlters. [sent-34, score-0.176]

17 As illustrated in Figure 1, the relationship between local bandpass ﬁlter responses undergoes a gradual transition from L2 -spherical for nearby to star-shaped (Lp -spherical with p < 2) for more distant features [12; 21]. [sent-35, score-0.143]

18 Ultimately, we would expect extremely distant features to become independent, having a factorial density with p 0 8. [sent-36, score-0.129]

19 When using a single Lp -spherically symmetric model for the joint distribution of nearby and more distant features, a single value of p can only represent a compromise for the whole variety of iso-probability contours. [sent-37, score-0.243]

20 This raises the question whether a combination of local spherical models, as opposed to a single Lp -spherical model, yields a better characterization of the statistics of natural image patches. [sent-38, score-0.137]

21 Possible ways to join several local models are Independent Subspace Analysis (ISA) [10], which uses a factorial combination of locally Lp spherical densities, or Markov Random Fields (MRFs) [18; 13]. [sent-39, score-0.177]

22 In principle, ISA could choose its subspaces such that nearby features are grouped into a joint subspace which can then be well described by a spherical symmetric model (p = 2) while more distant pixels, living in different subspaces, are assumed to be independent. [sent-41, score-0.482]

23 In fact, previous studies have found ISA to perform better than ICA for image patches as small as 8 8 and to yield an optimal p 2 for the local density models [10]. [sent-42, score-0.145]

24 On the other hand, the ISA model assumes a binary partition into either a Lp -spherical or a factorial distribution which does not seem to be fully justiﬁed considering the gradual transition described above. [sent-43, score-0.132]

25 2 Here, we propose a new family of hierarchical models by replacing the Lp -norms in the Lp -spherical models by Lp -nested functions, which consist of a cascade of nested Lp -norms and therefore allow for different values of p for different groups of ﬁlters. [sent-44, score-0.149]

26 While this family includes the Lp -spherical family and ISA models, it also includes densities that avoid the hard partition into either factorial or Lp -spherical. [sent-45, score-0.211]

27 At the same time, parameter estimation for these models can still be similarly efﬁcient and robust as for Lp -spherically symmetric models. [sent-46, score-0.149]

28 Preliminary results on 16 × 16 patches exhibit a more pronounced difference between the Lp -nested and the Lp -spherically symmetric distribution, suggesting that the change in p becomes more important for modelling densities over a larger spatial range. [sent-49, score-0.232]

29 Lp -nested symmetric distributions are a special case of the ν-spherical distributions which have a density characterized by the form ρ(y) = g(ν(y)) where ν : Rn → R is a positively homogeneous function of degree one, i. [sent-61, score-0.264]

30 Therefore, an Lp -nested function f in its general form can be visualized by a tree in which each inner node corresponds to an Lp -norm while the leaves stand for the coefﬁcients of the vector y. [sent-66, score-0.202]

31 For a general ν, it is difﬁcult to determine the distribution of U since the partition function involves the surface area of the ν-unit sphere which is not analytically tractable in most cases. [sent-71, score-0.105]

32 The function values at individual inner nodes I are denoted by fI , the vector of function values of the children of an inner node I by f I,1: I = (fI,1 , . [sent-76, score-0.302]

33 By deﬁnition, parents and children are related via fI = f I,1: I pI . [sent-80, score-0.098]

34 The number of children of a particular node I is denoted by I . [sent-81, score-0.145]

35 Lp -nested symmetric distributions are a very general class of densities. [sent-82, score-0.175]

36 For instance, since every Lp norm · p is an Lp -nested function, Lp -nested distributions includes the family of Lp -spherically symmetric distributions including (for p = 2) the family of spherically symmetric distributions. [sent-83, score-0.456]

37 setting f = · 2 or f = ( · p ) , and choosing the radial distribution appropriately, 2 −1 one can recover the Gaussian ρ(y) = Z exp − y 2 or the generalized spherical Gaussian 2 ρ(y) = Z −1 exp (− y p ), respectively. [sent-86, score-0.281]

38 On the other hand, when choosing the Lp -nested function 2 f as in equation (1) and to be the radial distribution of a p-generalized Normal distribution (r) = 3 Z −1 rn−1 exp (−rp∅ /s) [8; 22], the inner nodes f 1: ∅ become independent and we can recover an ISA model. [sent-87, score-0.351]

39 Note, however, that not all ISA models are also Lp -nested since Lp -nested symmetry requires the radial distribution to be that of a p-generalized Normal. [sent-88, score-0.231]

40 This means that the partition function of a general Lp -nested symmetric distribution is the partition function of the radial distribution normalized by the surface area of the Lp -nested sphere with radius f (y). [sent-90, score-0.486]

41 Therefore, if the partition function of the radial distribution can be computed easily, so can the partition function of the multivariate Lp -nested distribution. [sent-92, score-0.271]

42 Since, for a given f , an Lp -nested distribution is fully speciﬁed by a radial distribution, changing the radial distribution also changes the Lp -nested distribution. [sent-95, score-0.41]

43 This procedure is then repeated recursively for each of the children until the leaves of the tree are reached. [sent-98, score-0.198]

44 In particular, we are interested in the joint distribution of the children f I,1: I of a node I (e. [sent-101, score-0.194]

45 Just from the form of an Lp -nested function one might guess that those children are Lp -spherically symmetric distributed. [sent-104, score-0.221]

46 For example, the children f 1: ∅ of the root node (assuming that none of them is a leaf) follow the distribution ρ(f 1: ∅ ) = This implies that f 1: u = f 1: ∅ / f 1: ∅ p∅ ∅ ∅( S · f 1: ∅ ( f 1: p∅ p∅ ) ∅ ∅ p∅ ) i=1 n fi i −1 . [sent-106, score-0.223]

47 A similar form can be shown for the joint distribution of leaves and inner nodes (summarizing the whole subtree below them). [sent-115, score-0.241]

48 Unfortunately, only the children f 1: ∅ of the root node are really DSM distributed. [sent-116, score-0.178]

49 We were not able to analytically calculate the marginal distribution of an arbitrary node’s children f I,1: I , but we suspect it to have a similar form. [sent-117, score-0.121]

50 For that reason we ﬁt DSMs to those children f I,1: ∅ in the experiments below and use the estimated model to assess the dependencies between them. [sent-118, score-0.128]

51 We also use it for measuring the dependencies between the subspaces of ISA. [sent-119, score-0.145]

52 Lp -Spherically Symmetric Distributions and Independent Subspace Analysis The family of Lp -spherically symmetric distributions are a special case of Lp -nested distributions for which f (y) = y p [9]. [sent-121, score-0.263]

53 We use the ISA model by [10] where the ﬁlter responses y are modelled by a factorial combination of Lp -spherically symmetric distributions sitting on each subspace K ρ(y) = ρk ( yIk pk ). [sent-122, score-0.358]

54 k=1 3 Experiments Given an image patch x, all models used in this paper deﬁne densities over ﬁlter responses y = W x of linear ﬁlters. [sent-123, score-0.169]

55 Hyv¨ rinen and K¨ ster a o [10] report that ISA already ﬁnds several subspaces for 8 × 8 image patches. [sent-131, score-0.155]

56 We use the same whitening procedure as in [21; 6]: Each dataset is centered on the mean over examples and dimensions and rescaled such that whitening becomes volume conserving. [sent-133, score-0.196]

57 1 On the remaining n − 1 dimensions, we perform symmetric whitening (SYM) with S = C − 2 where C denotes the covariance matrix of the DC-corrected data C = cov [P X]. [sent-135, score-0.221]

58 The ALL equals the entropy if the model distribution equals the true distribution and is larger otherwise. [sent-137, score-0.08]

59 Since the ALL is theoretically always larger than the true joint entropy (ignoring estimation errors) using the ALL instead of the joint entropy should underestimate the true MI, which is still sufﬁcient for our purpose. [sent-144, score-0.12]

60 Parameter Estimation For all models (ISA, DSM, Lp -spherical and Lp -nested), we estimate the parameters ϑ for the radial distribution as described above in Section 2. [sent-145, score-0.231]

61 , pq ) and for the Lp -spherically symmetric distributions we use Golden Search over the single p. [sent-153, score-0.193]

62 The radial distribution is estimated independently as described above. [sent-159, score-0.205]

63 When ﬁtting the ﬁlters W to the different models (ISA, Lp -spherical and Lp -nested), we use a gradient ascent on the log-likelihood over the orthogonal group by alternating between optimizing the parameters p and ϑ and optimizing for W . [sent-160, score-0.094]

64 When optimizing for W we use a radial Γ-distribution for the Lp -spherically symmetric models and a radial χp distribution ( yIk pk is Γ-distributed) for pk the models on the single single subspaces of ISA, which is closer to the one used by [10]. [sent-165, score-0.744]

65 After optimization, we make a ﬁnal optimization for p and ϑ using a mixture of log normal distributions (log N ) with K = 6 mixture components on the radial distribution(s). [sent-166, score-0.251]

66 Lp -Nested Symmetric Distributions As for the Lp -spherically symmetric models, we use a radial Γ-distribution for the optimization of W and a mixture of log N distributions for the ﬁnal ﬁt. [sent-167, score-0.357]

67 We use two different kind of tree structures for our experiments with Lp -nested symmetric distributions. [sent-168, score-0.209]

68 Afterwards, we group those blocks again in a quadtree manner until we reached the root node (see Figure 2A). [sent-170, score-0.08]

69 Here, we simply group the ﬁlter within each subspace and joined them at the root node afterwards (see Figure 2B). [sent-172, score-0.174]

70 In order to speed up parameter estimation, each layer of the tree shared the same value of p. [sent-173, score-0.177]

71 Multi-Information Measurements For the ISA models, we estimated the MI between the ﬁlter responses within each subspace and between the Lp -radii yIk pk , 1 ≤ k ≤ K. [sent-174, score-0.128]

72 In the former case we used the ALL of an Lp -spherically symmetric distribution with especially optimized p and ϑ, in the latter a DSM with optimized radial and Dirichlet distribution as a surrogate for the joint entropy. [sent-175, score-0.433]

73 For the Lp -nested distribution, we estimate the MI between the children f I,1: I of all inner nodes I. [sent-176, score-0.2]

74 In case the children are leaves, we use the ALL of an Lp -spherically symmetric distribution as surrogate for the joint entropy, in case the children are inner nodes themselves, we use the ALL of an DSM. [sent-177, score-0.47]

75 4 Results and Discussion Figure (2) shows the optimized ﬁlters for the DT and the PND16 tree structure (we included the ﬁlters optimized on the ﬁrst of ten datasets for all tree structures in the Additional Material). [sent-179, score-0.211]

76 For both tree structures, the ﬁlters on the lowest level are grouped according to spatial frequency and orientation, whereas the variation in orientation is larger for the PND16 tree structure and some ﬁlters are unoriented. [sent-180, score-0.158]

77 The next layer of inner nodes, which is only present in the DT tree structure, roughly joins spatial location, although each of those inner nodes has one child whose leaves are global ﬁlters. [sent-181, score-0.386]

78 When looking at the various values of p at the inner nodes, we can observe that nodes which are higher up in the tree usually exhibit a smaller value of p. [sent-182, score-0.195]

79 Surprisingly, as can be seen in Figure 3 B and C, a smaller value of p does not correspond to a larger independence between the subtrees, which are even more correlated because almost every subtree contains global ﬁlters. [sent-183, score-0.076]

80 The small value of p is caused by the fact that the DSM (the distribution of the subtree values) has to account for this correlation which it can only do by decreasing the value of p (see Figure 3 and the DSM in 6 A p2=1. [sent-184, score-0.082]

81 77071 B Layer 1 Layer 2 Layer 3 Figure 2: Examples for the tree structures of Lp -nested distributions used in the experiments: (A) shows the DT structure with the corresponding optimized values. [sent-189, score-0.166]

82 (B) shows the PND16 tree structure with the corresponding values of p at the inner nodes and the optimized ﬁlters. [sent-191, score-0.199]

83 Note that this ﬁnding is exactly opposite to the assumptions in the ISA model which can usually not generate such a behavior (Figure 3A) as it models the two subtrees to be independent. [sent-193, score-0.079]

84 While the ISA2 model spreads out the radii almost over the whole positive quadrant due to the independence assumption the samples from the Lp -nested subtrees are more concentrated around the diagonal like the true data. [sent-196, score-0.127]

85 The Lp -nested model can achieve this behavior since (i) it does not assume a radial distribution that leads to independent radii on the subtrees and (ii) the subtree values f1 and f2 are DSM[n1 /p∅ , n2 /p∅ , ] distributed. [sent-197, score-0.395]

86 Except for the ISA models on WO-data, all performances are similar, whereas the Lp -nested models usually achieve the lowest ALL independent of the particular tree structure used. [sent-200, score-0.142]

87 For the other ISA models on WO-data the ALL gets worse with increasing number of subspaces (bold font number in Table 1). [sent-202, score-0.162]

88 This reﬂects the effect described above: Contrary to the assumptions of the ISA model, the responses of the different subspaces become in fact more correlated than the single ﬁlter responses. [sent-203, score-0.148]

89 003 for the Lp spherical model on WO-data), however, show a more pronounced improvement with for the Lp nested model, indicating that a single p does not sufﬁce anymore to capture all dependencies when going to larger patch sizes. [sent-212, score-0.162]

90 When looking at the MI measurements between the ﬁlters/subtrees at different levels of the hierarchy in the Lp -nested, Lp -spherically symmetric and ISA models, we can observe that for the WO-data, the MI actually increases when going from lower to higher layers. [sent-213, score-0.168]

91 This means that the MI between the direct ﬁlter responses (layer 3 for DT and layer 2 for all others) is in fact lower than the MI between the subspace radii or the inner nodes of the Lp -nested tree (layer 1-2 for DT, layer 1 for all others). [sent-214, score-0.548]

92 The highest MI is achieved between the children of the root node for the DT tree structure (DT layer 1). [sent-215, score-0.355]

93 Furthermore, the single ﬁlter responses inside a particular subspace or subtree are now more dependent than the subtrees or subspaces themselves. [sent-218, score-0.331]

94 Taken together, the ALL and the MI measurements suggest that ISA is not the best way to join multiple local models into a single joint model. [sent-223, score-0.093]

95 The basic assumption of the ISA model for natural images is that ﬁlter coefﬁcients can either be dependent within a subspace or must be independent between different subspaces. [sent-224, score-0.135]

96 However, the increasing ALL for an increasing number of subspaces and the fact that the MI between subspaces is actually higher than within the subspaces, demonstrates that this hard partition is not justiﬁed when the data is only whitened. [sent-225, score-0.263]

97 The ALL for the Lp -nested models is almost equal for all tree structures and a bit lower compared to the Lp -spherical and the ISA models. [sent-347, score-0.112]

98 For the whitened only data, the ALL increases signiﬁcantly with the number of subspaces (bold font). [sent-348, score-0.136]

99 Nonlinear extraction of ’independent components’ of natural images using radial Gaussianization. [sent-401, score-0.225]

100 Reducing statistical dependencies in natural signals using radial Gaussianization. [sent-404, score-0.233]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('lp', 0.679), ('isa', 0.455), ('cgc', 0.221), ('radial', 0.182), ('mi', 0.167), ('symmetric', 0.123), ('subspaces', 0.115), ('layer', 0.108), ('dsm', 0.104), ('lters', 0.102), ('children', 0.098), ('whitening', 0.098), ('spherical', 0.076), ('subspace', 0.071), ('lter', 0.069), ('tree', 0.069), ('ica', 0.063), ('subtree', 0.059), ('patches', 0.058), ('radii', 0.057), ('inner', 0.055), ('factorial', 0.055), ('distant', 0.053), ('sf', 0.053), ('subtrees', 0.053), ('distributions', 0.052), ('densities', 0.051), ('dt', 0.051), ('redundancy', 0.051), ('node', 0.047), ('nodes', 0.047), ('son', 0.046), ('image', 0.04), ('sinz', 0.039), ('nested', 0.037), ('family', 0.036), ('entropy', 0.034), ('yik', 0.034), ('spherically', 0.034), ('root', 0.033), ('responses', 0.033), ('partition', 0.033), ('leaves', 0.031), ('dependencies', 0.03), ('orthogonal', 0.03), ('optimized', 0.028), ('sphere', 0.027), ('lyu', 0.026), ('models', 0.026), ('joint', 0.026), ('dsms', 0.026), ('golden', 0.026), ('spemannstra', 0.026), ('pi', 0.025), ('pk', 0.024), ('cascade', 0.024), ('looking', 0.024), ('dirichlet', 0.023), ('distribution', 0.023), ('fabian', 0.023), ('afterwards', 0.023), ('whiten', 0.023), ('fi', 0.022), ('matthias', 0.022), ('images', 0.022), ('surface', 0.022), ('density', 0.021), ('independent', 0.021), ('measurements', 0.021), ('dc', 0.021), ('gradual', 0.021), ('sym', 0.021), ('font', 0.021), ('whitened', 0.021), ('natural', 0.021), ('child', 0.021), ('argmax', 0.021), ('contour', 0.021), ('orientation', 0.02), ('radius', 0.02), ('compression', 0.02), ('pii', 0.02), ('join', 0.02), ('optimizing', 0.019), ('patch', 0.019), ('entropies', 0.018), ('dec', 0.018), ('bandpass', 0.018), ('nearby', 0.018), ('pq', 0.018), ('normal', 0.017), ('layers', 0.017), ('independence', 0.017), ('preprocessing', 0.017), ('structures', 0.017), ('visual', 0.017), ('robustly', 0.017), ('arrows', 0.016), ('positively', 0.016), ('mrfs', 0.016)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0 111 nips-2009-Hierarchical Modeling of Local Image Features through $L p$-Nested Symmetric Distributions

Author: Matthias Bethge, Eero P. Simoncelli, Fabian H. Sinz

2 0.35453236 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

3 0.28038767 31 nips-2009-An LP View of the M-best MAP problem

Author: Menachem Fromer, Amir Globerson

Abstract: We consider the problem of ﬁnding the M assignments with maximum probability in a probabilistic graphical model. We show how this problem can be formulated as a linear program (LP) on a particular polytope. We prove that, for tree graphs (and junction trees in general), this polytope has a particularly simple form and diﬀers from the marginal polytope in a single inequality constraint. We use this characterization to provide an approximation scheme for non-tree graphs, by using the set of spanning trees over such graphs. The method we present puts the M -best inference problem in the context of LP relaxations, which have recently received considerable attention and have proven useful in solving diﬃcult inference problems. We show empirically that our method often ﬁnds the provably exact M best conﬁgurations for problems of high tree-width. A common task in probabilistic modeling is ﬁnding the assignment with maximum probability given a model. This is often referred to as the MAP (maximum a-posteriori) problem. Of particular interest is the case of MAP in graphical models, i.e., models where the probability factors into a product over small subsets of variables. For general models, this is an NP-hard problem [11], and thus approximation algorithms are required. Of those, the class of LP based relaxations has recently received considerable attention [3, 5, 18]. In fact, it has been shown that some problems (e.g., ﬁxed backbone protein design) can be solved exactly via sequences of increasingly tighter LP relaxations [13]. In many applications, one is interested not only in the MAP assignment but also in the M maximum probability assignments [19]. For example, in a protein design problem, we might be interested in the M amino acid sequences that are most stable on a given backbone structure [2]. In cases where the MAP problem is tractable, one can devise tractable algorithms for the M best problem [8, 19]. Speciﬁcally, for low tree-width graphs, this can be done via a variant of max-product [19]. However, when ﬁnding MAPs is not tractable, it is much less clear how to approximate the M best case. One possible approach is to use loopy max-product to obtain approximate max-marginals and use those to approximate the M best solutions [19]. However, this is largely a heuristic and does not provide any guarantees in terms of optimality certiﬁcates or bounds on the optimal values. LP approximations to MAP do enjoy such guarantees. Speciﬁcally, they provide upper bounds on the MAP value and optimality certiﬁcates. Furthermore, they often work for graphs with large tree-width [13]. The goal of the current work is to leverage the power of LP relaxations to the M best case. We begin by focusing on the problem of ﬁnding the second best solution. We show how it can be formulated as an LP over a polytope we call the “assignment-excluding marginal polytope”. In the general case, this polytope may require an exponential number of inequalities, but we prove that when the graph is a tree it has a very compact representation. We proceed to use this result to obtain approximations to the second best problem, and show how these can be tightened in various ways. Next, we show how M best assignments can be found by relying on algorithms for 1 second best assignments, and thus our results for the second best case can be used to devise an approximation algorithm for the M best problem. We conclude by applying our method to several models, showing that it often ﬁnds the exact M best assignments. 1 The M-best MAP problem and its LP formulation Consider a function on n variables deﬁned as: f (x1 , . . . , xn ; θ) = θij (xi , xj ) + ij∈E θi (xi ) (1) i∈V where V and E are the vertices and nodes of a graph G with n nodes. We shall be interested in the M assignments with largest f (x; θ) value.1 Denote these by x(1) , . . . , x(M) , so that x(1) is the assignment that maximizes f (x; θ), x(2) is the 2nd best assignment, etc. The MAP problem (i.e., ﬁnding x(1) ) can be formulated as an LP as follows [15]. Let µ be a vector of distributions that includes {µij (xi , xj )}ij∈E over edge variables and {µi (xi )}i∈V over nodes. The set of µ that arise from some joint distribution is known as the marginal polytope [15] and is denoted by M(G). Formally: M(G) = {µ | ∃p(x) ∈ ∆ s.t. p(xi , xj ) = µij (xi , xj ) , p(xi ) = µi (xi )} . where ∆ is the set of distributions on x. The MAP problem can then be shown to be equivalent to the following LP:2 max f (x; θ) = max µ · θ , (2) x µ∈M(G) It can be shown that this LP always has a maximizing µ that is a vertex of M(G) and is integral. Furthermore, this µ corresponds to the MAP assignment x(1) . Although the number of variables in this LP is only O(|E| + |V |), the diﬃculty comes from an exponential number of linear inequalities generally required to describe the marginal polytope M(G). We shall ﬁnd it useful to deﬁne a mapping between assignments x and integral vertices of the polytope. Given an integral vertex v ∈ M(G), deﬁne x(v) to be the assignment that maximizes vi (xi ). And, given an assignment z deﬁne v(z) to be the integral vertex in M(G) corresponding to the assignment z. Thus the LP in Eq. 2 will be maximized by v(x(1) ). One simple outer bound of the marginal polytope is the local polytope ML (G), which only enforces pairwise constraints between variables:     µi (xi ) = 1 (3) µij (xi , xj ) = µj (xj ), µij (xi , xj ) = µi (xi ), ML (G) = µ ≥ 0   x x x i j i The LP relaxation is then to maximize µ · θ where µ ∈ ML (G). For tree structured graphs, ML (G) = M(G) [15] and thus the LP relaxation yields the exact MAP x(1) . An LP Formulation for the 2nd -best MAP 2 Assume we found the MAP assignment x(1) and are now interested in ﬁnding x(2) . Is there a simple LP whose solution yields x(2) ? We begin by focusing on the case where G is a tree so that the local LP relaxation is exact. We ﬁrst treat the case of a connected tree. To construct an LP whose solution is x(2) , a natural approach is to use the LP for x(1) (i.e., the LP in Eq. 2) but somehow eliminate the solution x(1) using additional constraints. This, however, is somewhat trickier than it sounds. The key diﬃculty is that the new constraints should not generate fractional vertices, so that the resulting LP is still exact. We begin by deﬁning the polytope over which we need to optimize in order to obtain x(2) . 1 2 This is equivalent to ﬁnding P maximum probability assignments for a model p(x) ∝ ef (x;θ) . the P P P We use the notation µ · θ = ij∈E xi ,xj µij (xi , xj )θij (xi , xj ) + i xi µi (xi )θi (xi ) 2 Deﬁnition 1. The assignment-excluding marginal polytope is deﬁned as: ˆ M(G, z) = {µ | ∃p(x) ∈ ∆ s.t. p(z) = 0, p(xi , xj ) = µij (xi , xj ), p(xi ) = µi (xi )} . ˆ M(G, z) is simply the convex hull of all (integral) vectors v(x) for x = z. (4) ˆ The following result shows that optimizing over M(G, x(1) ) will yield the second best soluˆ tion x(2) , so that we refer to M(G, x(1) ) as the second-best marginal polytope. Lemma 1. The 2nd best solution is obtained via the following LP: maxx=x(1) f (x; θ) = maxµ∈M(G,x(1) ) µ · θ. Furthermore, the µ that maximizes the LP on ˆ the right is integral and corresponds to the second-best MAP assignment x(2) . The proof is similar to that of Eq. 2: instead of optimizing over x, we optimize over distributions p(x), while enforcing that p(x(1) ) = 0 so that x(1) is excluded from the maximization. The key question which we now address is how to obtain a simple characterization of ˆ ˆ M(G, z). Intuitively, it would seems that M(G, z) should be “similar” to M(G), such that it can be described as M(G) plus some constraints that “block” the assignment z. To illustrate the diﬃculty in ﬁnding such “blocking” constraints, consider the following constraint, originally suggested by Santos [10]: i µi (zi ) ≤ n − 1. This inequality is not satisﬁed by µ = v(z) since v(z) attains the value n for the LHS of the above. Furthermore, for any x = z and µ = v(x), the LHS would be n − 1 or less. Thus, this inequality separates ˆ v(z) from all other integral vertices. One might conclude that we can deﬁne M(G, z) by adding this inequality to M(G). The diﬃculty is that the resulting polytope has fractional vertices,3 and maximizing over it won’t generally yield an integral solution. It turns out that there is a diﬀerent inequality that does yield an exact characterization of ˆ M(G, z) when G is a tree. We now deﬁne this inequality and state our main theorem. Deﬁnition 2. Consider the functional I(µ, z) (which is linear in µ): (1 − di )µi (zi ) + I(µ, z) = i µij (zi , zj ) (5) ij∈E where di is the degree of node i in the tree graph G. ˆ Theorem 1. Adding the single inequality I(µ, z) ≤ 0 to M(G) yields M(G, z). ˆ M(G, z) = {µ | µ ∈ M(G), I(µ, z) ≤ 0 } (6) The theorem is proved in the appendix. Taken together with Lemma 1, it implies that x(2) may be obtained via an LP that is very similar to the MAP-LP, but has an additional constraint. We note the interesting similarity between I(µ, z) and the Bethe entropy [20]. The only diﬀerence is that in Bethe, µi , µij are replaced by H(Xi ), H(Xi , Xj ) respectively.4 The theorem also generalizes to the case where G is not a tree, but we have a junction tree for G. In this case, the theorem still holds if we deﬁne a generalized I(µ, z) inequality as: (1 − dS )µS (zS ) + S∈S µC (zC ) ≤ 0 (7) C∈C where C and S are the junction tree cliques and their separators, respectively, and dS is the number of cliques that intersect on separator S. In this case, the marginal polytope should enforce consistency between marginals µC (zC ) and their separators µS (zS ). However, such a characterization requires variables whose cardinality is exponential in the tree-width and is thus tractable only for graphs of low tree-width. In the next section, we address approximations for general graphs. A corresponding result exists for the case when G is a forest. In this case, the inequality in Eq. 6 is modiﬁed to: I(µ, z) ≤ |P | − 1, where |P | denotes the number of connected components of G. Interestingly, for a graph without edges, this gives the Santos inequality. 3 Consider the case of a single edge between 2 nodes where the MAP assignment is (0, 0). Adding the inequality µ1 (0) + µ2 (0) ≤ 1 produces the fractional vertex (0.5, 0.5). 4 The connection to Bethe can be more clearly understood from a duality-based proof of Theorem 1. We will cover this in an extended version of the manuscript. 3 2nd best LPs for general graphs - Spanning tree inequalities 3 When the graph G is not a tree, the marginal polytope M(G) generally requires an exponential number of inequalities. However, as mentioned above, it does have an exact description in terms of marginals over cliques and separators of a junction tree. Given such marginals on ˆ junction tree cliques, we also have an exact characterization of M(G, z) via the constraint in Eq. 7. However, in general, we cannot aﬀord to be exponential in tree-width. Thus a common strategy [15] is to replace M(G) with an outer bound that enforces consistency between marginals on overlapping sets of variables. The simplest example is ML (G) in Eq. 3. ˆ In what follows, we describe an outer-bound approximation scheme for M(G, z). We use ML (G) as the approximation for M(G) (more generally ML (G) can enforce consistency between any set of small regions, e.g., triplets). When G is not a tree, the linear constraint in ˆ Eq. 6 will no longer suﬃce to derive M(G, z). Moreover, direct application of the inequality will incorrectly remove some integral vertices. An alternative approach is to add inequalities that separate v(z) from the other integral vertices. This will serve to eliminate more and more fractional vertices, and if enough constraints are added, this may result in an integral solution. One obvious family of such constraints are those corresponding to spanning trees in G and have the form of Eq. 5. Deﬁnition 3. Consider any T that is a spanning tree of G. Deﬁne the functional I T (µ, z): (1 − dT )µi (zi ) + i I T (µ, z) = i µij (zi , zj ) (8) ij∈T where dT is the degree of i in T . We refer to I T (µ, z) ≤ 0 as a spanning tree inequality. i For any sub-tree T of G, the corresponding spanning tree inequality separates the vertex v(z) from the other vertices. This can be shown via similar arguments as in the proof of Theorem 1. Note, however, that the resulting polytope may still have fractional vertices. The above argument shows that any spanning tree provides a separating inequality for ˆ M(G, z). In principle, we would like to use as many such inequalities as possible. Deﬁnition 4. The spanning tree assignment-excluding marginal polytope is deﬁned as: ˆ MST (G, z) = µ | µ ∈ ML (G), L ∀ tree T ⊆ E I T (µ, z) ≤ 0 (9) where the ST notation indicates the inclusion of all spanning tree inequalities for G.5 Thus, we would actually like to perform the following optimization problem: max ˆ µ∈MST (G,z) L µ·θ ˆ as an approximation to optimization over M(G, z); i.e., we seek the optimal µ subject to all spanning tree inequalities for G with the ambition that this µ be integral and thus provide the non-z MAP assignment, with a certiﬁcate of optimality. Although the number of spanning trees is exponential in n, it turns out that all spanning inequalities can be used in practice. One way to achieve this is via a cutting plane algorithm [12] that ﬁnds the most violated spanning tree inequality and adds it to the LP. To implement this eﬃciently, we note that for a particular µ and a spanning tree T , the value of I T (µ, z) can be decomposed into a sum over the edges in T (and a T -independent constant): I T (µ, z) = µi (zi ) µij (zi , zj ) − µi (zi ) − µj (zj ) + (10) i ij∈T The tree maximizing the above is the maximum-weight spanning tree with edge-weights wij = µij (zi , zj ) − µi (zi ) − µj (zj ). It can thus be found eﬃciently. The cutting plane algorithm proceeds as follows. We start by adding an arbitrary spanning tree. Then, as long as the optimal µ is fractional, we ﬁnd the spanning tree inequality that µ most violates (where this is implemented via the maximum-weight spanning tree). This constraint will necessarily remove µ from the polytope. If there are no violated inequalities 5 ˆ ˆL Note that M(G, z) ⊆ MST (G, z) ⊂ ML (G). 4 but µ is still fractional, then spanning tree inequalities do not suﬃce to ﬁnd an integral solution (but see below on hypertree constraints to add in this case). In practice, we found that only a relatively small number of inequalities are needed to successfully yield an integral solution, or determine that all such inequalities are already satisﬁed. An alternative approach for solving the all spanning-tree problem is to work via the dual. The dual variables roughly correspond to points in the spanning tree polytope [16], optimization over which can be done in polynomial time, e.g., via the ellipsoid algorithm. We do not pursue this here since the cutting plane algorithm performed well in our experiments. ˆ As mentioned earlier, we can exactly characterize M(G, z) using Eq. 7, albeit at a cost exponential in the tree-width of the graph. A practical compromise would be to use inequalities over clique trees of G, where the cliques are relatively small, e.g., triplets. The corresponding constraint (Eq. 7 with the small cliques and their separators) will necessarily separate v(z) from the other integral vertices. Finding the maximally violated such inequality is an NP-hard problem, equivalent to a prize collecting Steiner tree problem, but recent work has found that such problems are often exactly solvable in practice [7]. It thus might be practical to include all such trees as constraints using a cutting plane algorithm. 4 From 2nd -best to M-best Thus far, we only dealt with the 2nd best case. As we show now, it turns out that the 2nd -best formalism can be used to devise an algorithm for M best. We begin by describing an algorithm for the exact M best and then show how it can be used to approximate those via the approximations for 2nd best described above. Fig. 1 describes our scheme, which we call Partitioning for Enumerating Solutions (or PES) for solving the M best problem. The scheme is general and only assumes that MAP-“like” problems can be solved. It is inspired by several pre-existing M best solution schemes [4, 6, 8, 19] but diﬀers from them in highlighting the role of ﬁnding a second best solution within a given subspace. for m ← 1 to M do if m = 1 then Run MAP solver to obtain the best assignment: x(1) ≡ arg max f (x; θ) CONSTRAINTS1 ← ∅ else k ←− arg max ′ k′ ∈{1,...,m−1} f (y(k ) ; θ) // sub-space containing mth best assignment x(m) ← y(k) // mth best assignment // A variable choice that distinguishes x(m) from x(k) : (m) (v, a) ← any member of the set {(i, xi (m) ) : xi (k) = xi } CONSTRAINTSm ← CONSTRAINTSk ∪ {xv = a} // Eliminate x(k) (as MAP) from subspace m CONSTRAINTSk ← CONSTRAINTSk ∪ {xv = a} // Eliminate x(m) (as 2nd -best) from subspace k y(k) ← CalcNextBestSolution(CONSTRAINTSk , x(k) ) end y(m) ← CalcNextBestSolution(CONSTRAINTSm , x(m) ) end return {x(m) }M m=1 /* Find next best solution in sub-space defined by CONSTRAINTS */ Function CalcNextBestSolution(CONSTRAINTS, x(∗) ) // x(∗) is the MAP in the sub-space defined by CONSTRAINTS: Run MAP solver to obtain the second-best solution: y ≡ arg max f (x; θ), and return y. x=x(∗) ,CONSTRAINTS end Figure 1: Pseudocode for the PES algorithm. The modus operandi of the PES algorithm is to eﬃciently partition the search space while systematically excluding all previously determined assignments. Signiﬁcantly, any MAP 5 Attractive Grids Ranks Run-times 1 50 Mixed Grids Ranks Run-times 1 50 0.5 0 S N B 0 Hard Protein SCP Ranks Run-times 1 50 0.5 S N B 0 0 S+R N+R B+R 0.5 S+R N+R B+R 0 S+R B B+R 0 S+R B B+R Figure 2: Number of best ranks and normalized run-times for the attractive and mixed grids, and the more diﬃcult protein SCP problems. S, N, and B denote the STRIPES, Nilsson, and BMMF algorithms. Algorithms marked with +R denote that regions of variables were added for those runs. solver can be plugged into it, on the condition that it is capable of solving the arg max in the CalcNextBestSolution subroutine. The correctness of PES can be shown by observing that at the M th stage, all previous best solutions are excluded from the optimization and no other assignment is excluded. Of note, this simple partitioning scheme is possible due to the observation that the ﬁrst-best and second-best MAP assignments must diﬀer in the assignment of at least one variable in the graph. The main computational step of the PES algorithm is to maximize f (x; θ) subject to x = x(∗) and x ∈ CONSTRAINTS (see the CalcNextBestSolution subroutine). The CONSTRAINTS set merely enforces that some of the coordinates of x are either equal to or diﬀerent from speciﬁed values.6 Within the LP, these can be enforced by setting µi (xi = a) = 1 or µi (xi = a) = 0. It can be shown that if one optimizes µ · θ with ˆ these constraints and µ ∈ M(G, x(∗) ), the solution is integral. Thus, the only element ˆ requiring approximation in the general case is the description of M(G, x(∗) ). We choose as ˆ this approximation the polytope MST (G, x(∗) ) in Eq. 9. We call the resulting approximaL tion algorithm Spanning TRee Inequalities and Partitioning for Enumerating Solutions, or STRIPES. In the next section, we evaluate this scheme experimentally. 5 Experiments We compared the performance of STRIPES to the BMMF algorithm [19] and the Lawler/Nilsson algorithm [6, 8]. Nilsson’s algorithm is equivalent to PES where the 2nd best assignment is obtained from maximizations within O(n) partitions, so that its runtime is O(n) times the cost of ﬁnding a single MAP. Here we approximated each MAP with its LP relaxation (as in STRIPES), so that both STRIPES and Nilsson come with certiﬁcates of optimality when their LP solutions are integral. BMMF relies on loopy BP to approximate the M best solutions.7 We used M = 50 in all experiments. To compare the algorithms, we pooled all their solutions, noting the 50 top probabilities, and then counted the fraction of these that any particular algorithm found (its solution rank). For run-time comparisons, we normalized the times by the longest-running algorithm for each example. We begin by considering pairwise MRFs on binary grid graphs of size 10 × 10. In the ﬁrst experiment, we used an Ising model with attractive (submodular) potentials, a setting in which the pairwise LP relaxation is exact [14]. For each grid edge ij, we randomly chose Jij ∈ [0, 0.5], and local potentials were randomized in the range ±0.5. The results for 25 graphs are shown in Fig. 2. Both the STRIPES and Nilsson algorithms obtained the 50 optimal solutions (as learned from their optimality certiﬁcates), while BMMF clearly fared less well for some of the graphs. While the STRIPES algorithm took < 0.5 to 2 minutes to run, the Nilsson algorithm took around 13 minutes. On the other hand, BMMF was quicker, taking around 10 seconds per run, while failing to ﬁnd a signiﬁcant portion of the top solutions. Overall, the STRIPES algorithm was required to employ up to 19 spanning tree inequalities per calculation of second-best solution. 6 This is very diﬀerent from the second best constraint, since setting x1 = 1 blocks all assignments with this value, as opposed to setting x = 1 which blocks only the assignment with all ones. 7 For BMMF, we used the C implementation at http://www.cs.huji.ac.il/~ talyam/ inference.html. The LPs for STRIPES and Nilsson were solved using CPLEX. 6 Next, we studied Ising models with mixed interaction potentials (with Jij and the local potentials randomly chosen in [−0.5, 0.5]). For almost all of the 25 models, all three algorithms were not able to successfully ﬁnd the top solutions. Thus, we added regions of triplets (two for every grid face) to tighten the LP relaxation (for STRIPES and Nilsson) and to perform GBP instead of BP (for BMMF). This resulted in STRIPES and Nilsson always provably ﬁnding the optimal solutions, and BMMF mostly ﬁnding these solutions (Fig. 2). For these more diﬃcult grids, however, STRIPES was the fastest of the algorithms, taking 0.5 - 5 minutes. On the other hand, the Nilsson and BMMF algorithms took 18 minutes and 2.5 7 minutes, respectively. STRIPES added up to 23 spanning tree inequalities per iteration. The protein side-chain prediction (SCP) problem is to to predict the placement of amino acid side-chains given a protein backbone [2, 18]. Minimization of a protein energy function corresponds to ﬁnding a MAP assignment for a pairwise MRF [19]. We employed the dataset of [18] (up to 45 states per variable, mean approximate tree-width 50), running all algorithms to calculate the optimal side-chain conﬁgurations. For 315 of 370 problems in the dataset, the ﬁrst MAP solution was obtained directly as a result of the LP relaxation having an integral solution (“easy” problems). STRIPES provably found the subsequent top 50 solutions within 4.5 hours for all but one of these cases (up to 8 spanning trees per calculation), and BMMF found the same 50 solutions for each case within 0.5 hours; note that only STRIPES provides a certiﬁcate of optimality for these solutions. On the other hand, only for 146 of the 315 problems was the Nilsson method able to complete within ﬁve days; thus, we do not compare its performance here. For the remaining 55 (“hard”) problems (Fig. 2), we added problem-speciﬁc triplet regions using the MPLP algorithm [13]. We then ran the STRIPES algorithm to ﬁnd the optimal solutions. Surprisingly, it was able to exactly ﬁnd the 50 top solutions for all cases, using up to 4 standard spanning tree inequalities per second-best calculation. The STRIPES run-times for these problems ranged from 6 minutes to 23 hours. On the other hand, whether running BMMF without these regions (BP) or with the regions (GBP), it did not perform as well as STRIPES in terms of the number of high-ranking solutions or its speed. To summarize, STRIPES provably found the top 50 solutions for 369 of the 370 protein SCP problems. 6 Conclusion ˆ In this work, we present a novel combinatorial object M(G, z) and show its utility in obtaining the M best MAP assignments. We provide a simple characterization of it for tree structured graphs, and show how it can be used for approximations in non-tree graphs. As with the marginal polytope, many interesting questions arise about the properties of ˆ M(G, z). For example, in which non-tree cases can we provide a compact characterization (e.g., as for the cut-polytope for planar graphs [1]). Another compelling question is in which problems the spanning tree inequalities are provably optimal. An interesting generalization of our method is to predict diverse solutions satisfying some local measure of “distance” from each other, e.g., as in [2]. Here we studied the polytope that results from excluding one assignment. An intriguing question is to characterize the polytope that excludes M assignments. We have found that it does not simply correspond to adding M constraints I(µ, z i ) ≤ 0 for i = 1, . . . , M , so its ˆ geometry is apparently more complicated than that of M(G, z). Here we used LP solvers to solve for µ. Such generic solvers could be slow for large-scale problems. However, in recent years, specialized algorithms have been suggested for solving MAP-LP relaxations [3, 5, 9, 17]. These use the special form of the constraints to obtain local-updates and more scalable algorithms. We intend to apply these schemes to our method. Finally, our empirical results show that our method indeed leverages the power of LP relaxations and yields exact M best optimal solutions for problems with large tree-width. Acknowledgements We thank Nati Linial for his helpful discussions and Chen Yanover and Talya Meltzer for their insight and help in running BMMF. We also thank the anonymous reviewers for their useful advice. 7 A Proof of Theorem 1 Recall that for any µ ∈ M(G), there exists a probability density p(x) s.t. µ = x p(x)v(x). Denote pµ (z) as the minimal value of p(z) among all p(x) that give µ. We prove that ˆ pµ (z) = max(0, I(µ, z)), from which the theorem follows (since pµ (z) = 0 iﬀ µ ∈ M(G, z)). The proof is by induction on n. For n = 1, the node has degree 0, so I(µ, z) = µ1 (z1 ). Clearly, pµ (z) = µ1 (z1 ), so pµ (z) = I(µ, z). For n > 1, there must exist a leaf in G ˆ (assume that its index is n and its neighbor’s is n − 1). Denote G as the tree obtained ˆ by removing node n and its edge with n − 1. For any assignment x, denote x as the corresponding sub-assignment for the ﬁrst n − 1 variables. Also, any µ can be derived by ˆ ˆ adding appropriate coordinates to a unique µ ∈ M(G). For an integral vertex µ = v(x), ˆˆ ˆ ˆ ˆ ˆ x denote its projected µ as v (ˆ ). Denote by I(µ, z ) the functional in Eq. 5 applied to G. For ˆ any µ and its projected µ, it can be seen that: ˆˆ ˆ I(µ, z) = I(µ, z ) − α (11) where we deﬁne α = xn =zn µn−1,n (zn−1 , xn ) (so 0 ≤ α ≤ 1). The inductive assumption ˆ ˆ ˆ gives a p(ˆ ) that has marginals µ and also p(ˆ ) = max(0, I(µ, z )). We next use p(ˆ ) to ˆx ˆz ˆx construct a p(x) that has marginals µ and the desired minimal pµ (z). Consider three cases: ˆˆ ˆ I. I(µ, z) ≤ 0 and I(µ, z ) ≤ 0. From the inductive assumption, pµ (ˆ ) = 0, so we deﬁne: ˆˆ z µn−1,n (xn−1 , xn ) p(x) = p(ˆ ) ˆx (12) µn−1 (xn−1 ) which indeed marginalizes to µ, and p(z) = 0 so that pµ (z) = 0 as required. If µn−1 (xn−1 ) = 0, then p(ˆ ) is necessarily 0, in which case we deﬁne p(x) = 0. Note that this construction ˆx is identical to that used in proving that ML (G) = M(G) for a tree graph G. ˆˆ ˆ II. I(µ, z) > 0. Based on Eq. 11 and α ≥ 0, we have I(µ, z ) > 0. Applying the inductive ˆ µ, z ) = pµ (ˆ ) > 0. Now, deﬁne p(x) so that p(z) = I(µ, z): ˆ assumption to µ, we obtain I( ˆ ˆ ˆˆ z xl , l ≤ n − 2 δ(xn−1 = zn−1 ) δ(xn = zn ) p(x) no constraint 0 no constraint As in Eq. 12 0 0 ∃ l x l = zl 1 ∀ l x l = zl 1 µn−1,n (zn−1 , xn ) 1 1 p(ˆ ) ˆx 0 I(µ, z) Simple algebra shows that p(x) is non-negative and has µ as marginals. We now show that p(z) is minimal. Based on the inductive assumption and Eq. 11, it can easily be shown that I(v(z), z) = 1, I(v(x), z) ≤ 0 for x = z. For any p(x) s.t. µ = x p(x)v(x), from linearity, I(µ, z) = p(z) + x=z p(x)I(v(x), z) ≤ p(z) (since I(v(x), z) ≤ 0 for x = z). Since the p(z) we deﬁne achieves this lower bound, it is clearly minimal. ˆˆ ˆ ˆ III. I(µ, z) ≤ 0 but I(µ, z ) > 0. Applying the inductive assumption to µ, we see that ˆ µ, z ) > 0; Eq. 11 implies α − I(µ, z ) ≥ 0. Deﬁne β = µn−1 (zn−1 ) − pµ (ˆ ), which ˆˆ ˆ ˆˆ z pµ (ˆ ) = I( ˆ ˆ ˆˆ z ˆ is non-negative since µn−1 (zn−1 ) = µn−1 (ˆ n−1 ) and p marginalizes to µ. Deﬁne p(x) as: ˆ z ˆ xl , l ≤ n − 2 δ(xn−1 = zn−1 ) δ(xn = zn ) no constraint 0 no constraint ∃ l x l = zl As in Eq. 12 0 ˆ ˆ z µ (z ,x ) p(ˆ ) n−1,n βn−1 n α−I(µ,ˆ ) ˆx α µ (z ,z ) p(ˆ ) n−1,n βn−1 n ˆx (z ,x ) ˆˆ ˆ µ I(µ, z ) n−1,n αn−1 n 1 0 0 1 1 ∀ l x l = zl p(x) 1 which indeed marginalizes to µ, and p(z) = 0 so that pµ (z) = 0, as required. 8 References [1] F. Barahona. On cuts and matchings in planar graphs. Math. Program., 60(1):53–68, 1993. [2] M. Fromer and C. Yanover. Accurate prediction for atomic-level protein design and its application in diversifying the near-optimal sequence space. Proteins: Structure, Function, and Bioinformatics, 75:682–705, 2009. [3] A. Globerson and T. Jaakkola. Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 21. MIT Press, Cambridge, MA, 2007. [4] E. Kloppmann, G. M. Ullmann, and T. Becker. An extended dead-end elimination algorithm to determine gap-free lists of low energy states. Journal of Comp. Chem., 28:2325–2335, 2007. [5] N. Komodakis and N. Paragios. Beyond loose LP-relaxations: Optimizing MRFs by repairing cycles. In D. Forsyth, P. Torr, and A. Zisserman, editors, ECCV, pages 806–820, Heidelberg, Germany, 2008. Springer. [6] E. L. Lawler. A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18(7):401–405, 1972. [7] I. Ljubic, R. Weiskircher, U. Pferschy, G. W. Klau, P. Mutzel, and M. Fischetti. An algorithmic framework for the exact solution of the prize-collecting steiner tree problem. Mathematical Programming, 105:427–449, Feb 2006. [8] D. Nilsson. An eﬃcient algorithm for ﬁnding the M most probable conﬁgurations in probabilistic expert systems. Statistics and Computing, 8:159–173, Jun 1998. [9] P. Ravikumar, A. Agarwal, and M. Wainwright. Message-passing for graph-structured linear programs: proximal projections, convergence and rounding schemes. In Proc. of the 25th international conference on Machine learning, pages 800–807, New York, NY, USA, 2008. ACM. [10] E. Santos. On the generation of alternative explanations with implications for belief revision. In Proc. of the 7th Annual Conference on Uncertainty in Artiﬁcial Intelligence, 1991. [11] Y. Shimony. Finding the MAPs for belief networks is NP-hard. 68(2):399–410, 1994. Aritiﬁcal Intelligence, [12] D. Sontag and T. Jaakkola. New outer bounds on the marginal polytope. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 1393–1400. MIT Press, Cambridge, MA, 2007. [13] D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss. Tightening LP relaxations for MAP using message passing. In Proc. of the 24th Annual Conference on Uncertainty in Artiﬁcial Intelligence, pages 503–510, 2008. [14] B. Taskar, S. Lacoste-Julien, and M. I. Jordan. Structured prediction, dual extragradient and bregman projections. J. Mach. Learn. Res., 7:1627–1653, 2006. [15] M. Wainwright and M. Jordan. Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn., 1(1-2):1–305, 2008. [16] M. J. Wainwright, T. Jaakkola, and A. S. Willsky. A new class of upper bounds on the log partition function. IEEE Transactions on Information Theory, 51(7):2313–2335, 2005. [17] T. Werner. A linear programming approach to max-sum problem: A review. IEEE Trans. Pattern Anal. Mach. Intell., 29(7):1165–1179, 2007. [18] C. Yanover, T. Meltzer, and Y. Weiss. Linear programming relaxations and belief propagation – an empirical study. Journal of Machine Learning Research, 7:1887–1907, 2006. [19] C. Yanover and Y. Weiss. Finding the M most probable conﬁgurations using loopy belief propagation. In Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004. [20] J. Yedidia, W. W.T. Freeman, and Y. Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Trans. on Information Theory, 51(7):2282– 2312, 2005. 9

4 0.13114026 212 nips-2009-Semi-Supervised Learning in Gigantic Image Collections

Author: Rob Fergus, Yair Weiss, Antonio Torralba

Abstract: With the advent of the Internet it is now possible to collect hundreds of millions of images. These images come with varying degrees of label information. “Clean labels” can be manually obtained on a small fraction, “noisy labels” may be extracted automatically from surrounding text, while for most images there are no labels at all. Semi-supervised learning is a principled framework for combining these different label sources. However, it scales polynomially with the number of images, making it impractical for use on gigantic collections with hundreds of millions of images and thousands of classes. In this paper we show how to utilize recent results in machine learning to obtain highly efﬁcient approximations for semi-supervised learning that are linear in the number of images. Speciﬁcally, we use the convergence of the eigenvectors of the normalized graph Laplacian to eigenfunctions of weighted Laplace-Beltrami operators. Our algorithm enables us to apply semi-supervised learning to a database of 80 million images gathered from the Internet. 1

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

Author: Sanja Fidler, Marko Boben, Ales Leonardis

Abstract: Multi-class object learning and detection is a challenging problem due to the large number of object classes and their high visual variability. Specialized detectors usually excel in performance, while joint representations optimize sharing and reduce inference time — but are complex to train. Conveniently, sequential class learning cuts down training time by transferring existing knowledge to novel classes, but cannot fully exploit the shareability of features among object classes and might depend on ordering of classes during learning. In hierarchical frameworks these issues have been little explored. In this paper, we provide a rigorous experimental analysis of various multiple object class learning strategies within a generative hierarchical framework. Speciﬁcally, we propose, evaluate and compare three important types of multi-class learning: 1.) independent training of individual categories, 2.) joint training of classes, and 3.) sequential learning of classes. We explore and compare their computational behavior (space and time) and detection performance as a function of the number of learned object classes on several recognition datasets. We show that sequential training achieves the best trade-off between inference and training times at a comparable detection performance and could thus be used to learn the classes on a larger scale. 1

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

7 0.056142449 213 nips-2009-Semi-supervised Learning using Sparse Eigenfunction Bases

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

9 0.053602189 129 nips-2009-Learning a Small Mixture of Trees

10 0.050915383 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

11 0.050418142 137 nips-2009-Learning transport operators for image manifolds

12 0.046748817 255 nips-2009-Variational Inference for the Nested Chinese Restaurant Process

13 0.046518955 69 nips-2009-Discrete MDL Predicts in Total Variation

14 0.04529947 151 nips-2009-Measuring Invariances in Deep Networks

15 0.044388879 199 nips-2009-Ranking Measures and Loss Functions in Learning to Rank

16 0.044075619 95 nips-2009-Fast subtree kernels on graphs

17 0.043645076 16 nips-2009-A Smoothed Approximate Linear Program

18 0.043099392 118 nips-2009-Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions

19 0.041105855 43 nips-2009-Bayesian estimation of orientation preference maps

20 0.03851337 58 nips-2009-Constructing Topological Maps using Markov Random Fields and Loop-Closure Detection

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.153), (1, -0.051), (2, -0.033), (3, 0.051), (4, -0.043), (5, -0.007), (6, 0.019), (7, 0.085), (8, 0.011), (9, -0.194), (10, -0.232), (11, 0.114), (12, -0.023), (13, 0.143), (14, 0.084), (15, -0.02), (16, 0.015), (17, 0.077), (18, 0.104), (19, 0.418), (20, 0.044), (21, -0.135), (22, -0.035), (23, 0.047), (24, -0.111), (25, 0.047), (26, -0.031), (27, -0.007), (28, 0.101), (29, -0.02), (30, 0.095), (31, 0.037), (32, 0.025), (33, 0.062), (34, 0.11), (35, -0.038), (36, 0.035), (37, 0.029), (38, -0.07), (39, -0.022), (40, -0.071), (41, -0.041), (42, 0.031), (43, 0.003), (44, -0.01), (45, 0.053), (46, 0.172), (47, 0.051), (48, -0.087), (49, -0.019)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96808535 111 nips-2009-Hierarchical Modeling of Local Image Features through $L p$-Nested Symmetric Distributions

Author: Matthias Bethge, Eero P. Simoncelli, Fabian H. Sinz

2 0.7960096 241 nips-2009-The 'tree-dependent components' of natural scenes are edge filters

Author: Daniel Zoran, Yair Weiss

3 0.67418039 31 nips-2009-An LP View of the M-best MAP problem

Author: Menachem Fromer, Amir Globerson

4 0.43278635 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.40956602 219 nips-2009-Slow, Decorrelated Features for Pretraining Complex Cell-like Networks

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

6 0.38109842 129 nips-2009-Learning a Small Mixture of Trees

7 0.33065847 249 nips-2009-Tracking Dynamic Sources of Malicious Activity at Internet Scale

8 0.29401824 212 nips-2009-Semi-Supervised Learning in Gigantic Image Collections

9 0.27765512 172 nips-2009-Nonparametric Bayesian Texture Learning and Synthesis

10 0.27642468 255 nips-2009-Variational Inference for the Nested Chinese Restaurant Process

11 0.27609387 69 nips-2009-Discrete MDL Predicts in Total Variation

12 0.26310128 206 nips-2009-Riffled Independence for Ranked Data

13 0.25318238 237 nips-2009-Subject independent EEG-based BCI decoding

14 0.24972725 7 nips-2009-A Data-Driven Approach to Modeling Choice

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

16 0.22961453 6 nips-2009-A Biologically Plausible Model for Rapid Natural Scene Identification

17 0.22762759 137 nips-2009-Learning transport operators for image manifolds

18 0.22733548 40 nips-2009-Bayesian Nonparametric Models on Decomposable Graphs

19 0.22613192 198 nips-2009-Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions

20 0.22487038 247 nips-2009-Time-rescaling methods for the estimation and assessment of non-Poisson neural encoding models

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(7, 0.021), (21, 0.188), (24, 0.059), (25, 0.046), (35, 0.056), (36, 0.072), (39, 0.053), (58, 0.082), (61, 0.011), (68, 0.099), (71, 0.065), (81, 0.028), (86, 0.088), (91, 0.025)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.87549812 246 nips-2009-Time-Varying Dynamic Bayesian Networks

Author: Le Song, Mladen Kolar, Eric P. Xing

Abstract: Directed graphical models such as Bayesian networks are a favored formalism for modeling the dependency structures in complex multivariate systems such as those encountered in biology and neural science. When a system is undergoing dynamic transformation, temporally rewiring networks are needed for capturing the dynamic causal inﬂuences between covariates. In this paper, we propose time-varying dynamic Bayesian networks (TV-DBN) for modeling the structurally varying directed dependency structures underlying non-stationary biological/neural time series. This is a challenging problem due the non-stationarity and sample scarcity of time series data. We present a kernel reweighted 1 -regularized auto-regressive procedure for this problem which enjoys nice properties such as computational efﬁciency and provable asymptotic consistency. To our knowledge, this is the ﬁrst practical and statistically sound method for structure learning of TVDBNs. We applied TV-DBNs to time series measurements during yeast cell cycle and brain response to visual stimuli. In both cases, TV-DBNs reveal interesting dynamics underlying the respective biological systems. 1

same-paper 2 0.8671158 111 nips-2009-Hierarchical Modeling of Local Image Features through $L p$-Nested Symmetric Distributions

Author: Matthias Bethge, Eero P. Simoncelli, Fabian H. Sinz

3 0.84948784 31 nips-2009-An LP View of the M-best MAP problem

Author: Menachem Fromer, Amir Globerson

4 0.84584987 241 nips-2009-The 'tree-dependent components' of natural scenes are edge filters

Author: Daniel Zoran, Yair Weiss

5 0.76120275 32 nips-2009-An Online Algorithm for Large Scale Image Similarity Learning

Author: Gal Chechik, Uri Shalit, Varun Sharma, Samy Bengio

Abstract: Learning a measure of similarity between pairs of objects is a fundamental problem in machine learning. It stands in the core of classiﬁcation methods like kernel machines, and is particularly useful for applications like searching for images that are similar to a given image or ﬁnding videos that are relevant to a given video. In these tasks, users look for objects that are not only visually similar but also semantically related to a given object. Unfortunately, current approaches for learning similarity do not scale to large datasets, especially when imposing metric constraints on the learned similarity. We describe OASIS, a method for learning pairwise similarity that is fast and scales linearly with the number of objects and the number of non-zero features. Scalability is achieved through online learning of a bilinear model over sparse representations using a large margin criterion and an efﬁcient hinge loss cost. OASIS is accurate at a wide range of scales: on a standard benchmark with thousands of images, it is more precise than state-of-the-art methods, and faster by orders of magnitude. On 2.7 million images collected from the web, OASIS can be trained within 3 days on a single CPU. The nonmetric similarities learned by OASIS can be transformed into metric similarities, achieving higher precisions than similarities that are learned as metrics in the ﬁrst place. This suggests an approach for learning a metric from data that is larger by orders of magnitude than was handled before. 1

6 0.72619051 188 nips-2009-Perceptual Multistability as Markov Chain Monte Carlo Inference

7 0.70165205 210 nips-2009-STDP enables spiking neurons to detect hidden causes of their inputs

8 0.68548584 168 nips-2009-Non-stationary continuous dynamic Bayesian networks

9 0.65777677 28 nips-2009-An Additive Latent Feature Model for Transparent Object Recognition

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

11 0.65537888 250 nips-2009-Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference

12 0.65307248 247 nips-2009-Time-rescaling methods for the estimation and assessment of non-Poisson neural encoding models

13 0.64732975 35 nips-2009-Approximating MAP by Compensating for Structural Relaxations

14 0.64566058 137 nips-2009-Learning transport operators for image manifolds

15 0.64255381 224 nips-2009-Sparse and Locally Constant Gaussian Graphical Models

16 0.64162719 3 nips-2009-AUC optimization and the two-sample problem

17 0.63743162 72 nips-2009-Distribution Matching for Transduction

18 0.63588166 155 nips-2009-Modelling Relational Data using Bayesian Clustered Tensor Factorization

19 0.6353696 212 nips-2009-Semi-Supervised Learning in Gigantic Image Collections

20 0.63490456 158 nips-2009-Multi-Label Prediction via Sparse Infinite CCA