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

226 nips-2009-Spatial Normalized Gamma Processes

Source: pdf

Author: Vinayak Rao, Yee W. Teh

Abstract: Dependent Dirichlet processes (DPs) are dependent sets of random measures, each being marginally DP distributed. They are used in Bayesian nonparametric models when the usual exchangeability assumption does not hold. We propose a simple and general framework to construct dependent DPs by marginalizing and normalizing a single gamma process over an extended space. The result is a set of DPs, each associated with a point in a space such that neighbouring DPs are more dependent. We describe Markov chain Monte Carlo inference involving Gibbs sampling and three different Metropolis-Hastings proposals to speed up convergence. We report an empirical study of convergence on a synthetic dataset and demonstrate an application of the model to topic modeling through time. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 uk Abstract Dependent Dirichlet processes (DPs) are dependent sets of random measures, each being marginally DP distributed. [sent-7, score-0.208]

2 We propose a simple and general framework to construct dependent DPs by marginalizing and normalizing a single gamma process over an extended space. [sent-9, score-0.403]

3 We describe Markov chain Monte Carlo inference involving Gibbs sampling and three different Metropolis-Hastings proposals to speed up convergence. [sent-11, score-0.211]

4 We report an empirical study of convergence on a synthetic dataset and demonstrate an application of the model to topic modeling through time. [sent-12, score-0.14]

5 Much of this effort has focussed on deﬁning priors on collections of dependent random probability measures. [sent-19, score-0.108]

6 [6] expounded on the notion of dependent DPs, that is, a dependent set of random measures that are all marginally DPs. [sent-20, score-0.318]

7 In this paper, we propose a simple and general framework for the construction of dependent DPs on arbitrary spaces. [sent-24, score-0.153]

8 The idea is based on the fact that just as Dirichlet distributions can be generated by drawing a set of independent gamma variables and normalizing, the DP can be constructed by drawing a sample from a gamma process (ΓP) and normalizing (i. [sent-25, score-0.486]

9 This implies the following easy construction of a set of dependent DPs: deﬁne a ΓP over an extended space, associate each DP with a different region of the space, and deﬁne each DP by normalizing the restriction of the ΓP on the associated region. [sent-30, score-0.329]

10 This produces a set of dependent DPs, with the amount of overlap among the regions controlling the amount of dependence. [sent-31, score-0.154]

11 We call this model a spatial normalized gamma process (SNΓP). [sent-32, score-0.332]

12 More generally, our construction can be extended to normalizing restrictions of any completely random measure, and we call the resulting dependent random measures spatial normalized random measures (SNRMs). [sent-33, score-0.415]

13 2 Gamma Processes We brieﬂy describe the gamma process (ΓP) here. [sent-38, score-0.239]

14 (1) Here α is a measure on the space (Θ, Ω) and is called the base measure of the ΓP. [sent-44, score-0.18]

15 A sample from this Poisson process will yield an inﬁnite set of atoms {θi , wi }∞ since Θ⊗[0,∞) µ(dθdw) = ∞. [sent-45, score-0.129]

16 G= (2) i=1 ∞ It can be shown that the total mass G(S) = i=1 wi 1(θi ∈ S) of any measurable subset S ⊂ Θ is simply gamma distributed with shape parameter α(S), thus the natural name gamma process. [sent-47, score-0.418]

17 (3) Here we used an atypical parameterization of the DP in terms of the base measure α. [sent-50, score-0.138]

18 The usual (equivalent) parameters of the DP are: strength parameter α(Θ) and base distribution α/α(Θ). [sent-51, score-0.096]

19 The gamma process is an example of a completely random measure [9]. [sent-53, score-0.281]

20 Firstly, if S ∈ Ω then the restriction G (dθ) = G(dθ ∩ S) onto S is a ΓP with base measure α (dθ) = α(dθ ∩ S). [sent-62, score-0.138]

21 Secondly, if Θ = Θ1 ⊗ Θ2 is a two dimensional space, then the projection G (dθ1 ) = Θ2 G(dθ1 dθ2 ) onto Θ1 is also a ΓP with base measure α (dθ1 ) = Θ2 α(dθ1 dθ2 ). [sent-63, score-0.138]

22 3 Spatial Normalized Gamma Processes In this section we describe our proposal for constructing dependent DPs. [sent-64, score-0.198]

23 We wish to construct a set of dependent random measures over (Θ, Ω), one Dt for each t ∈ T such that each Dt is marginally DP. [sent-66, score-0.21]

24 Our approach is to deﬁne a gamma process G over an extended space and let each Dt be a normalized restriction/projection of G. [sent-67, score-0.277]

25 Because restrictions and projections of gamma processes are also gamma processes, each Dt will be DP distributed. [sent-68, score-0.451]

26 Now let α be a base measure over the product space Θ ⊗ Y and consider a gamma process G ∼ ΓP(α) 2 (5) over Θ ⊗ Y. [sent-72, score-0.377]

27 Since restrictions and projections of ΓPs are ΓPs as well, Gt will be a ΓP over Θ with base measure αt : G(dθdy) ∼ ΓP(αt ) Gt (dθ) = (6) Yt Now normalizing, Dt = Gt /Gt (Θ) ∼ DP(αt ) (7) We call the resulting set of dependent DPs {Dt }t∈T spatial normalized gamma processes (SNΓPs). [sent-73, score-0.599]

28 Let H be a base distribution over Θ and γ > 0 be a concentration parameter. [sent-80, score-0.125]

29 The base measure αt works out to be: t+L αt (dθ) = γH(dθ)dy/2L = γH(dθ), (8) t−L so that each Dt ∼ DP(γH) with concentration parameter γ and base distribution H. [sent-84, score-0.263]

30 As a result, two DPs Ds and Dt will share more atoms the closer s and t are to each other, and no atoms if |s − t| > 2L. [sent-87, score-0.162]

31 The second example generalizes the ﬁrst one by allowing different atoms to have different window lengths. [sent-89, score-0.128]

32 Each atom now has a time-stamp y and a window length l, so that it appears in DPs in the window [y − l, y + l]. [sent-90, score-0.094]

33 Now Ds and Dt will always be dependent with the amount of dependence decreasing as |s − t| increases. [sent-95, score-0.108]

34 For each R ∈ R deﬁne GR (dθ) = G(dθ ⊗ R) (10) We see that each GR is a ΓP with base measure αR (dθ) = α(dθ ⊗ R). [sent-104, score-0.138]

35 Further, the mixing proportions are Dirichlet distributed and independent from the components by virtue of each GR (Θ) being gamma distributed and independent from DR . [sent-113, score-0.218]

36 Figure 1 shows the regions for the second example corresponding to observations at three times. [sent-115, score-0.094]

37 The mixture of DPs construction is related to the hierarchical Dirichlet process deﬁned in [11] (not the one deﬁned by Teh et al [3]). [sent-116, score-0.151]

38 4 Inference in the SNΓP The mixture of DPs interpretation of the SNΓP makes sampling from the model, and consequently inference via Markov chain Monte Carlo sampling, easy. [sent-119, score-0.162]

39 In what follows, we describe both Gibbs sampling and Metropolis-Hastings based updates for a hierarchical model in which the dependent DPs act as prior distributions over a collection of inﬁnite mixture models. [sent-120, score-0.228]

40 Formally, our observations now lie in a measurable space (X, Σ) equipped with a set of probability measures Fθ parametrized by θ ∈ Θ. [sent-121, score-0.126]

41 Observation i at time tj is denoted xji , lies in region rji and is drawn from mixture component parametrized by θji . [sent-122, score-0.54]

42 Thus to augment (12), we have rji ∼ Mult({πjR : R ∈ Rj }) θji ∼ Drji xji ∼ Fθji (13) where rji = R with probability πjR for each R ∈ Rj . [sent-123, score-0.461]

43 In words, we ﬁrst pick a region rji from the set Rj , then a mixture component θji , followed by drawing xji from the mixture distribution. [sent-124, score-0.603]

44 1 Gibb Sampling We derive a Gibbs sampler for the SNΓP where the region DPs DR are integrated out and replaced by Chinese restaurants. [sent-126, score-0.158]

45 Let cji denote the index of the cluster in Drji to which observation xji is assigned. [sent-127, score-0.38]

46 We also assume that the base distribution H is conjugate to the mixture distributions Fθ so that the cluster parameters are integrated out as well. [sent-128, score-0.268]

47 The Gibbs sampler iteratively resamples the 4 latent variables left: rji ’s, cji ’s and gR ’s. [sent-129, score-0.269]

48 In the following, let mjRc be the number of observations ¬ji from time tj assigned to cluster c in the DP DR in region R, and let fRc (xji ) be the density of observation xji conditioned on the other variables currently assigned to cluster c in DR , with its cluster parameters integrated out. [sent-130, score-0.798]

49 We denote marginal counts with dots, for example m·Rc is the number of observations (over all times) assigned to cluster c in region R. [sent-131, score-0.316]

50 2 Metropolis-Hastings Proposals To improve convergence and mixing of the Markov chain, we introduce three Metropolis-Hastings (MH) proposals in addition to the Gibbs sampling updates described above. [sent-137, score-0.196]

51 These propose nonincremental changes in the assignment of observations to clusters and regions, allowing the Markov chain to traverse to different modes that are hard to reach using Gibbs sampling. [sent-138, score-0.165]

52 The ﬁrst proposal (Algorithm 1) proceeds like the split-merge proposal of [12]. [sent-139, score-0.18]

53 It either splits an existing cluster in a region into two new clusters in the same region, or merges two existing clusters in a region into a single cluster. [sent-140, score-0.504]

54 To improve the acceptance probability, we use 5 rounds of restricted Gibbs sampling [12]. [sent-141, score-0.195]

55 The second proposal (Algorithm 2) seeks to move a picked cluster from one region to another. [sent-142, score-0.365]

56 The new region is chosen from a region neighbouring the current one (for example in Figure 1 the neigbors are the four regions diagonally neighbouring the current one). [sent-143, score-0.42]

57 To improve acceptance probability we also resample the gR ’s associated with the current and proposed regions. [sent-144, score-0.098]

58 The move can be invalid if the cluster contains an observation from a time point not associated with the new region; in this case the move is simply rejected. [sent-145, score-0.196]

59 The third proposal (Algorithm 3) we considered seeks to combine into one step what would take two steps under the previous two proposals: splitting a cluster and moving it to a new region (or the reverse: moving a cluster into a new region and merging it with a cluster therein). [sent-146, score-0.702]

60 We modelled this data as a collection of ﬁve DP mixture of Gaussians, with a SNΓP prior over the ﬁve dependent DPs. [sent-151, score-0.166]

61 To encourage clusters to be shared across times (i. [sent-153, score-0.106]

62 to avoid similar clusters with non-overlapping timespans), we chose the distribution over window lengths β(w) to give larger probabilities to larger timespans. [sent-155, score-0.122]

63 Figure 2 shows the evolution of the log-likelihood for 5 different samplers: plain Gibbs sampling, Gibbs sampling augmented with each of MH proposals 1, 2 and 3, and ﬁnally a sampler that interleaved all three MH samplers with Gibbs sampling. [sent-157, score-0.267]

64 Not surprisingly, the complete sampler converged fastest, with Gibbs sampling with MH-proposal 2 (Gibbs+MH2) performing nearly as well. [sent-158, score-0.1]

65 The fact that Gibbs+MH2 performs so well can be explained by the easy clustering structure of the problem, so that exploring region assignments of clusters rather than cluster assignments of observations was the challenge faced by the sampler (note its high acceptance rate in Figure 4). [sent-160, score-0.493]

66 To demonstrate how the additional MH proposals help mixing, we examined how the cluster assignment of observations varied over iterations. [sent-161, score-0.269]

67 6 Figure 4: Acceptance rates of the MH proposals for Gibbs+MH1+MH2+MH3 after burn-in (percentages). [sent-165, score-0.107]

68 This is because the latter is simultaneously exploring the region assignment of clusters as well. [sent-176, score-0.195]

69 In Gibbs+MH1, clusters split and merge frequently since they stay in the same regions, causing the cluster matrix to vary rapidly. [sent-177, score-0.267]

70 In Gibbs+MH1+MH2+MH3, after a split the new clusters often move into separate regions; so it takes longer before they can merge again. [sent-178, score-0.194]

71 Nonetheless, this demonstrates the importance of split/merge proposals like MH1 and MH3; [12] studied this in greater detail. [sent-179, score-0.107]

72 We next examined how well the proposals explore the region assignment of clusters. [sent-180, score-0.227]

73 In particular, at each step of the Markov chain, we pick the cluster with mean closest to the mean of one of the true Gaussian mixture components, and tracked how its timespan evolved. [sent-181, score-0.291]

74 Figure 5 shows that without MH proposal 2, the clusters remain essentially frozen in their initial regions. [sent-182, score-0.165]

75 We used a model that involves both the SNΓP (to capture changes in topic distributions across the years) and the hierarchical Dirichlet process (HDP) [3] (to capture differences among documents). [sent-185, score-0.188]

76 Each document is modeled using a different DP, with the DPs in year i sharing the same base distribution Di . [sent-186, score-0.149]

77 Consequently, each topic is associated with a distribution i=1 over words, and has a particular timespan. [sent-189, score-0.14]

78 Each document in year i is a mixture over the topics whose timespan include year i. [sent-190, score-0.268]

79 Instead of all DPs having the same base distribution, we have 13 dependent base distributions drawn from the SNΓP. [sent-192, score-0.3]

80 The concentration parameters of our DPs were chosen to encourage shared topics, their magnitude chosen to produce about a 100 topics over the whole corpus on average. [sent-193, score-0.093]

81 For inference, we used Gibbs sampling, interleaved with all three MH proposals to update the SNΓP. [sent-195, score-0.107]

82 the Markov chain was initialized randomly except that all clusters were assigned to the top-most region (spanning the 13 years). [sent-196, score-0.271]

83 When trying to split a large cluster (or merge 2 large clusters), MH proposal 1 can still be fairly expensive because of the rounds of restricted Gibbs sampling. [sent-205, score-0.317]

84 However we ﬁnd that after the burn-in period it tends to have low acceptance rate. [sent-207, score-0.098]

85 We believe we need to redesign MH proposal 3 to produce more intelligent splits to increase the acceptance rate. [sent-208, score-0.188]

86 Finally, MH-proposal 2 is the cheapest, both in terms of computation and book-keeping, and has reasonably high acceptance rate. [sent-209, score-0.098]

87 The acceptance rates of the MH proposals (given in Figure 4) are slightly lower than those reported by [12], where a plain DP mixture model was applied to a simple synthetic data set, and where split/merge acceptance rates were on the order of 1 to 5 percent. [sent-211, score-0.386]

88 6 Discussion We described a conceptually simple and elegant framework for the construction of dependent DPs based on normalized gamma processes. [sent-212, score-0.409]

89 The resulting collection of random probability measures has a number of useful properties: the marginal distributions are DPs and the weights of shared atoms can vary across DPs. [sent-213, score-0.154]

90 We developed auxiliary variable Gibbs and Metropolis-Hastings samplers for the model and applied it to time-varying topic modelling where each topic has its own time-span. [sent-214, score-0.347]

91 Since [6] there has been strong interest in building dependent sets of random measures. [sent-215, score-0.108]

92 Interestingly, the property of each random measure being marginally DP, as originally proposed by [6], is often not met in the literature, where dependent stochastic processes are deﬁned through shared and random parameters [3, 14, 15, 11]. [sent-216, score-0.281]

93 Useful dependent DPs had not been found [16] until recently, when a ﬂurry of models were proposed [17, 18, 19, 20, 21, 22, 23]. [sent-217, score-0.108]

94 However most of these proposals have been deﬁned only for the real line (interpreted as the time line) and not for arbitrary spaces. [sent-218, score-0.107]

95 [24, 25, 26, 13] proposed a variety of spatial DPs where the atoms and weights of the DPs are dependent through Gaussian processes. [sent-219, score-0.244]

96 This model differs from ours in the content of these shared regions (breaks of a stick in that case vs a (restricted) Gamma process in ours) and the construction of the DPs (they use the stick breaking construction of the DP, we normalize the restricted Gamma process). [sent-221, score-0.25]

97 First, we can allow, at additional complexity, the locations of atoms to vary using the spatial DP approach [13]. [sent-224, score-0.136]

98 Third, although we have only described spatial normalized gamma processes, it should be straightforward to extend the approach to spatial normalized random measures [7, 8]. [sent-228, score-0.419]

99 A split-merge Markov chain Monte Carlo procedure for the Dirichlet process mixture model. [sent-314, score-0.148]

100 The Ornstein-Uhlenbeck Dirichlet process and other time-varying processes for Bayesian nonparametric inference. [sent-360, score-0.131]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('dps', 0.469), ('gr', 0.322), ('gibbs', 0.258), ('dp', 0.206), ('rj', 0.204), ('gamma', 0.191), ('xji', 0.177), ('mh', 0.168), ('sn', 0.15), ('rji', 0.142), ('topic', 0.14), ('dt', 0.139), ('ytj', 0.124), ('dr', 0.12), ('region', 0.12), ('cluster', 0.114), ('dependent', 0.108), ('proposals', 0.107), ('dirichlet', 0.101), ('acceptance', 0.098), ('base', 0.096), ('ji', 0.091), ('proposal', 0.09), ('cji', 0.089), ('atoms', 0.081), ('aj', 0.08), ('jr', 0.08), ('clusters', 0.075), ('dtj', 0.071), ('timespan', 0.071), ('neighbouring', 0.067), ('yt', 0.066), ('mj', 0.062), ('sampling', 0.062), ('marginally', 0.06), ('mixture', 0.058), ('normalizing', 0.056), ('spatial', 0.055), ('year', 0.053), ('merge', 0.052), ('dy', 0.05), ('ds', 0.049), ('observations', 0.048), ('process', 0.048), ('dl', 0.048), ('pick', 0.048), ('window', 0.047), ('warwick', 0.047), ('regions', 0.046), ('construction', 0.045), ('nonparametric', 0.043), ('tj', 0.043), ('measures', 0.042), ('measure', 0.042), ('chain', 0.042), ('ps', 0.042), ('move', 0.041), ('words', 0.041), ('sj', 0.04), ('grif', 0.04), ('processes', 0.04), ('normalized', 0.038), ('sampler', 0.038), ('measurable', 0.036), ('drji', 0.035), ('frc', 0.035), ('icer', 0.035), ('kottas', 0.035), ('timespans', 0.035), ('restricted', 0.035), ('samplers', 0.035), ('markov', 0.034), ('assigned', 0.034), ('topics', 0.033), ('auxiliary', 0.032), ('shared', 0.031), ('dunson', 0.031), ('kent', 0.031), ('launch', 0.031), ('adaptor', 0.031), ('coloured', 0.031), ('bayesian', 0.031), ('merging', 0.03), ('restrictions', 0.029), ('concentration', 0.029), ('poisson', 0.029), ('accept', 0.029), ('nonparametrics', 0.028), ('gt', 0.027), ('mixing', 0.027), ('elegant', 0.027), ('grammars', 0.027), ('masses', 0.027), ('ys', 0.027), ('documents', 0.026), ('split', 0.026), ('plain', 0.025), ('dw', 0.025), ('others', 0.025), ('state', 0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 226 nips-2009-Spatial Normalized Gamma Processes

Author: Vinayak Rao, Yee W. Teh

2 0.14685234 205 nips-2009-Rethinking LDA: Why Priors Matter

Author: Andrew McCallum, David M. Mimno, Hanna M. Wallach

Abstract: Implementations of topic models typically use symmetric Dirichlet priors with ﬁxed concentration parameters, with the implicit assumption that such “smoothing parameters” have little practical effect. In this paper, we explore several classes of structured priors for topic models. We ﬁnd that an asymmetric Dirichlet prior over the document–topic distributions has substantial advantages over a symmetric prior, while an asymmetric prior over the topic–word distributions provides no real beneﬁt. Approximation of this prior structure through simple, efﬁcient hyperparameter optimization steps is sufﬁcient to achieve these performance gains. The prior structure we advocate substantially increases the robustness of topic models to variations in the number of topics and to the highly skewed word frequency distributions common in natural language. Since this prior structure can be implemented using efﬁcient algorithms that add negligible cost beyond standard inference techniques, we recommend it as a new standard for topic modeling. 1

3 0.1391228 217 nips-2009-Sharing Features among Dynamical Systems with Beta Processes

Author: Alan S. Willsky, Erik B. Sudderth, Michael I. Jordan, Emily B. Fox

Abstract: We propose a Bayesian nonparametric approach to the problem of modeling related time series. Using a beta process prior, our approach is based on the discovery of a set of latent dynamical behaviors that are shared among multiple time series. The size of the set and the sharing pattern are both inferred from data. We develop an efﬁcient Markov chain Monte Carlo inference method that is based on the Indian buffet process representation of the predictive distribution of the beta process. In particular, our approach uses the sum-product algorithm to efﬁciently compute Metropolis-Hastings acceptance probabilities, and explores new dynamical behaviors via birth/death proposals. We validate our sampling algorithm using several synthetic datasets, and also demonstrate promising results on unsupervised segmentation of visual motion capture data.

4 0.13656577 40 nips-2009-Bayesian Nonparametric Models on Decomposable Graphs

Author: Francois Caron, Arnaud Doucet

Abstract: Over recent years Dirichlet processes and the associated Chinese restaurant process (CRP) have found many applications in clustering while the Indian buffet process (IBP) is increasingly used to describe latent feature models. These models are attractive because they ensure exchangeability (over samples). We propose here extensions of these models where the dependency between samples is given by a known decomposable graph. These models have appealing properties and can be easily learned using Monte Carlo techniques. 1 Motivation The CRP and IBP have found numerous applications in machine learning over recent years [5, 10]. We consider here the case where the data we are interested in are ‘locally’ dependent; these dependencies being represented by a known graph G where each data point/object is associated to a vertex. These local dependencies can correspond to any conceptual or real (e.g. space, time) metric. For example, in the context of clustering, we might want to propose a prior distribution on partitions enforcing that data which are ‘close’ in the graph are more likely to be in the same cluster. Similarly, in the context of latent feature models, we might be interested in a prior distribution on features enforcing that data which are ‘close’ in the graph are more likely to possess similar features. The ‘standard’ CRP and IBP correspond to the case where the graph G is complete; that is it is fully connected. In this paper, we generalize the CRP and IBP to decomposable graphs. The resulting generalized versions of the CRP and IBP enjoy attractive properties. Each clique of the graph follows marginally a CRP or an IBP process and explicit expressions for the joint prior distribution on the graph is available. It makes it easy to learn those models using straightforward generalizations of Markov chain Monte Carlo (MCMC) or Sequential Monte Carlo (SMC) algorithms proposed to perform inference for the CRP and IBP [5, 10, 14]. The rest of the paper is organized as follows. In Section 2, we review the popular Dirichlet multinomial allocation model and the Dirichlet Process (DP) partition distribution. We propose an extension of these two models to decomposable graphical models. In Section 3 we discuss nonparametric latent feature models, reviewing brieﬂy the construction in [5] and extending it to decomposable graphs. We demonstrate these models in Section 4 on two applications: an alternative to the hierarchical DP model [12] and a time-varying matrix factorization problem. 2 Prior distributions for partitions on decomposable graphs Assume we have n observations. When performing clustering, we associate to each of this observation an allocation variable zi ∈ [K] = {1, . . . , K}. Let Πn be the partition of [n] = {1, . . . , n} deﬁned by the equivalence relation i ↔ j ⇔ zi = zj . The resulting partition Πn = {A1 , . . . , An(Πn ) } 1 is an unordered collection of disjoint non-empty subsets Aj of [n], j = 1, . . . , n(Πn ), where ∪j Aj = [n] and n(Πn ) is the number of subsets for partition Πn . We also denote by Pn be the set of all partitions of [n] and let nj , j = 1, . . . , n(Πn ), be the size of the subset Aj . Each allocation variable zi is associated to a vertex/site of an undirected graph G, which is assumed to be known. In the standard case where the graph G is complete, we ﬁrst review brieﬂy here two popular prior distributions on z1:n , equivalently on Πn . We then extend these models to undirected decomposable graphs; see [2, 8] for an introduction to decomposable graphs. Finally we brieﬂy discuss the directed case. Note that the models proposed here are completely different from the hyper multinomial-Dirichlet in [2] and its recent DP extension [6]. 2.1 Dirichlet multinomial allocation model and DP partition distribution Assume for the time being that K is ﬁnite. When the graph is complete, a popular choice for the allocation variables is to consider a Dirichlet multinomial allocation model [11] θ θ , . . . , ), zi |π ∼ π (1) K K where D is the standard Dirichlet distribution and θ > 0. Integrating out π, we obtain the following Dirichlet multinomial prior distribution π ∼ D( Pr(z1:n ) = K j=1 Γ(θ) Γ(nj + θ K) (2) θ Γ(θ + n)Γ( K )K and then, using the straightforward equality Pr(Πn ) = PK where PK = {Πn ∈ Pn |n(Πn ) ≤ K}, we obtain K! (K−n(Πn ))! Pr(z1:n ) valid for for all Πn ∈ n(Π ) Pr(Πn ) = θ Γ(θ) j=1n Γ(nj + K ) K! . θ (K − n(Πn ))! Γ(θ + n)Γ( K )n(Πn ) (3) DP may be seen as a generalization of the Dirichlet multinomial model when the number of components K → ∞; see for example [10]. In this case the distribution over the partition Πn of [n] is given by [11] n(Π ) θn(Πn ) j=1n Γ(nj ) . (4) Pr(Πn ) = n i=1 (θ + i − 1) Let Π−k = {A1,−k , . . . , An(Π−k ),−k } be the partition induced by removing item k to Πn and nj,−k be the size of cluster j for j = 1, . . . , n(Π−k ). It follows from (4) that an item k is assigned to an existing cluster j, j = 1, . . . , n(Π−k ), with probability proportional to nj,−k / (n − 1 + θ) and forms a new cluster with probability θ/ (n − 1 + θ). This property is the basis of the CRP. We now extend the Dirichlet multinomial allocation and the DP partition distribution models to decomposable graphs. 2.2 Markov combination of Dirichlet multinomial and DP partition distributions Let G be a decomposable undirected graph, C = {C1 , . . . , Cp } a perfect ordering of the cliques and S = {S2 , . . . , Cp } the associated separators. It can be easily checked that if the marginal distribution of zC for each clique C ∈ C is deﬁned by (2) then these distributions are consistent as they yield the same distribution (2) over the separators. Therefore, the unique Markov distribution over G with Dirichlet multinomial distribution over the cliques is deﬁned by [8] Pr(zC ) S∈S Pr(zS ) C∈C Pr(z1:n ) = (5) where for each complete set B ⊆ G, we have Pr(zB ) given by (2). It follows that we have for any Πn ∈ PK Γ(θ) K! Pr(Πn ) = (K − n(Πn ))! C∈C Γ(θ) S∈S 2 K j=1 θ Γ(nj,C + K ) θ Γ(θ+nC )Γ( K )K K j=1 θ Γ(nj,S + K ) θ Γ(θ+nS )Γ( K )K (6) where for each complete set B ⊆ G, nj,B is the number of items associated to cluster j, j = 1, . . . , K in B and nB is the total number of items in B. Within each complete set B, the allocation variables deﬁne a partition distributed according to the Dirichlet-multinomial distribution. We now extend this approach to DP partition distributions; that is we derive a joint distribution over Πn such that the distribution of ΠB over each complete set B of the graph is given by (4) with θ > 0. Such a distribution satisﬁes the consistency condition over the separators as the restriction of any partition distributed according to (4) still follows (4) [7]. G Proposition. Let Pn be the set of partitions Πn ∈ Pn such that for each decomposition A, B, and any (i, j) ∈ A × B, i ↔ j ⇒ ∃k ∈ A ∩ B such that k ↔ i ↔ j. As K → ∞, the prior distribution G over partitions (6) is given for each Πn ∈ Pn by Pr(Πn ) = θn(Πn ) n(ΠC ) Γ(nj,C ) j=1 nC i=1 (θ+i−1) n(ΠS ) Γ(nj,S ) j=1 nS (θ+i−1) i=1 C∈C S∈S (7) where n(ΠB ) is the number of clusters in the complete set B. Proof. From (6), we have θ n(ΠC ) K(K − 1) . . . (K − n(Πn ) + 1) Pr(Πn ) = K C∈C n(ΠC )− S∈S n(ΠS ) C∈C θ n(ΠS ) S∈S n(ΠC ) θ Γ(nj,C + K ) j=1 nC (θ+i−1) i=1 n(ΠS ) θ Γ(nj,S + K ) j=1 nS (θ+i−1) i=1 Thus when K → ∞, we obtain (7) if n(Πn ) = C∈C n(ΠC ) − S∈S n(ΠS ) and 0 otherwise. We have n(Πn ) ≤ C∈C n(ΠC ) − S∈S n(ΠS ) for any Πn ∈ Pn and the subset of Pn verifying G n(Πn ) = C∈C n(ΠC ) − S∈S n(ΠS ) corresponds to the set Pn . Example. Let the notation i ∼ j (resp. i j) indicates an edge (resp. no edge) between two sites. Let n = 3 and G be the decomposable graph deﬁned by the relations 1 ∼ 2, 2 ∼ 3 and 1 3. G The set P3 is then equal to {{{1, 2, 3}}; {{1, 2}, {3}}; {{1}, {2, 3}}; {{1}, {2}, {3}}}. Note that G the partition {{1, 3}, {2}} does not belong to P3 . Indeed, as there is no edge between 1 and 3, they cannot be in the same cluster if 2 is in another cluster. The cliques are C1 = {1, 2} and C2 = {2, 3} Pr(ΠC1 ) Pr(ΠC2 ) hence we can and the separator is S2 = {2}. The distribution is given by Pr(Π3 ) = Pr(ΠS ) 2 check that we obtain Pr({1, 2, 3}) = (θ + 1)−2 , Pr({1, 2}, {3}) = Pr({1, 2}, {3}) = θ(θ + 1)−2 and Pr({1}, {2}, {3}) = θ2 (θ + 1)−2 . Let now deﬁne the full conditional distributions. Based on (7) the conditional assignment of an item k is proportional to the conditional over the cliques divided by the conditional over the separators. G Let denote G−k the undirected graph obtained by removing vertex k from G. Suppose that Πn ∈ Pn . G−k If Π−k ∈ Pn−1 , then do not change the value of item k. Otherwise, item k is assigned to cluster j / where j = 1, . . . , n(Π−k ) with probability proportional to {C∈C|n−k,j,C >0} n−k,j,C {S∈S|n−k,j,S >0} n−k,j,S (8) and to a new cluster with probability proportional to θ, where n−k,j,C is the number of items in the set C \ {k} belonging to cluster j. The updating process is illustrated by the Chinese wedding party process1 in Fig. 1. The results of this section can be extended to the Pitman-Yor process, and more generally to species sampling models. Example (continuing). Given Π−2 = {A1 = {1}, A2 = {3}}, we have −1 Pr( item 2 assigned to A1 = {1}| Π−2 ) = Pr( item 2 assigned to A2 = {3}| Π−2 ) = (θ + 2) −1 and Pr( item 2 assigned to new cluster A3 | Π−2 ) = θ (θ + 2) . Given Π−2 = {A1 = {1, 3}}, item 2 is assigned to A1 with probability 1. 1 Note that this representation describes the full conditionals while the CRP represents the sequential updat- ing. 3 (a) (b) (d) (c) (e) Figure 1: Chinese wedding party. Consider a group of n guests attending a wedding party. Each of the n guests may belong to one or several cliques, i.e. maximal groups of people such that everybody knows everybody. The belonging of each guest to the different cliques is represented by color patches on the ﬁgures, and the graphical representation of the relationship between the guests is represented by the graphical model (e). (a) Suppose that the guests are already seated such that two guests cannot be together at the same table is they are not part of the same clique, or if there does not exist a group of other guests such that they are related (“Any friend of yours is a friend of mine”). (b) The guest number k leaves his table and either (c) joins a table where there are guests from the same clique as him, with probability proportional to the product of the number of guests from each clique over the product of the number of guests belonging to several cliques on that table or (d) he joins a new table with probability proportional to θ. 2.3 Monte Carlo inference 2.3.1 MCMC algorithm Using the full conditionals, a single site Gibbs sampler can easily be designed to approximate the posterior distribution Pr(Πn |z1:n ). Given a partition Πn , an item k is taken out of the partition. If G−k Π−k ∈ Pn−1 , item k keeps the same value. Otherwise, the item will be assigned to a cluster j, / j = 1, . . . , n(Π−k ), with probability proportional to p(z{k}∪Aj,−k ) × p(zAj,−k ) {C∈C|n−k,j,C >0} n−k,j,C {S∈S|n−k,j,S >0} n−k,j,S (9) and the item will be assigned to a new cluster with probability proportional to p(z{k} ) × θ. Similarly to [3], we can also deﬁne a procedure to sample from p(θ|n(Πn ) = k)). We assume that θ ∼ G(a, b) and use p auxiliary variables x1 , . . . , xp . The procedure is as follows. • For j = 1, . . . , p, sample xj |k, θ ∼ Beta(θ + nSj , nCj − nSj ) • Sample θ|k, x1:p ∼ G(a + k, b − j log xj ) 2.3.2 Sequential Monte Carlo We have so far only treated the case of an undirected decomposable graph G. We can formulate a sequential updating rule for the corresponding perfect directed version D of G. Indeed, let (a1 , . . . a|V | ) be a perfect ordering and pa(ak ) be the set of parents of ak which is by deﬁnition complete. Let Πk−1 = {A1,k−1 , . . . , An(Πk−1 ),k−1 } denote the partition of the ﬁrst k−1 vertices a1:k−1 and let nj,pa(ak ) be the number of elements with value j in the set pa(ak ), j = 1, . . . , n(Πk−1 ). Then the vertex ak joins the set j with probability nj,pa(ak ) / θ + cluster with probability θ/ θ + q q nq,pa(ak ) and creates a new nq,pa(ak ) . One can then design a particle ﬁlter/SMC method in a similar fashion as [4]. Consider a set of (i) (i) (i) (i) N N particles Πk−1 with weights wk−1 ∝ Pr(Πk−1 , z1:k−1 ) ( i=1 wk−1 = 1) that approximate (i) the posterior distribution Pr(Πk−1 |z1:k−1 ). For each particle i, there are n(Πk−1 ) + 1 possible 4 (i,j) allocations for component ak . We denote Πk the partition obtained by associating component ak (i,j) to cluster j. The weight associated to Πk is given by  nj,pa(ak ) (i)  if j = 1, . . . , n(Πk−1 ) θ+ q nq,pa(ak ) (i,j) (i) p(z{ak }∪Aj,k−1 ) wk−1 = wk−1 × (10) (i) θ  θ+ n p(zAj,k−1 ) if j = n(Πk−1 ) + 1 q q,pa(ak ) (i,j) Then we can perform a deterministic resampling step by keeping the N particles Πk with highest (i,j) (i) (i) weights wk−1 . Let Πk be the resampled particles and wk the associated normalized weights. 3 Prior distributions for inﬁnite binary matrices on decomposable graphs Assume we have n objects; each of these objects being associated to the vertex of a graph G. To K each object is associated a K-dimensional binary vector zn = (zn,1 , . . . , zn,K ) ∈ {0, 1} where zn,i = 1 if object n possesses feature i and zn,i = 0 otherwise. These vectors zt form a binary n × K matrix denoted Z1:n . We denote by ξ1:n the associated equivalence class of left-ordered matrices and let EK be the set of left-ordered matrices with at most K features. In the standard case where the graph G is complete, we review brieﬂy here two popular prior distributions on Z1:n , equivalently on ξ1:n : the Beta-Bernoulli model and the IBP [5]. We then extend these models to undirected decomposable graphs. This can be used for example to deﬁne a time-varying IBP as illustrated in Section 4. 3.1 Beta-Bernoulli and IBP distributions The Beta-Bernoulli distribution over the allocation Z1:n is K Pr(Z1:n ) = α + K )Γ(n − nj + 1) α Γ(n + 1 + K ) α K Γ(nj j=1 (11) where nj is the number of objects having feature j. It follows that Pr(ξ1:n ) = K K! 2n −1 h=0 α K Γ(nj α + K )Γ(n − nj + 1) α Γ(n + 1 + K ) Kh ! j=1 (12) where Kh is the number of features possessing the history h (see [5] for details). The nonparametric model is obtained by taking the limit when K → ∞ Pr(ξ1:n ) = αK K+ + 2n −1 h=1 Kh ! exp(−αHn ) where K + is the total number of features and Hn = 3.2 (n − nj )!(nj − 1)! n! j=1 n 1 k=1 k . (13) The IBP follows from (13). Markov combination of Beta-Bernoulli and IBP distributions Let G be a decomposable undirected graph, C = {C1 , . . . , Cp } a perfect ordering of the cliques and S = {S2 , . . . , Cp } the associated separators. As in the Dirichlet-multinomial case, it is easily seen that if for each clique C ∈ C, the marginal distribution is deﬁned by (11), then these distributions are consistent as they yield the same distribution (11) over the separators. Therefore, the unique Markov distribution over G with Beta-Bernoulli distribution over the cliques is deﬁned by [8] Pr(ZC ) S∈S Pr(ZS ) C∈C Pr(Z1:n ) = (14) where Pr(ZB ) given by (11) for each complete set B ⊆ G. The prior over ξ1:n is thus given, for ξ1:n ∈ EK , by Pr(ξ1:n ) = K! 2n −1 h=0 Kh ! α K α Γ(nj,C + K )Γ(nC −nj,C +1) α Γ(nC +1+ K ) α α Γ(nj,S + K )Γ(nS −nj,S +1) K K α j=1 Γ(nS +1+ K ) K j=1 C∈C S∈S 5 (15) where for each complete set B ⊆ G, nj,B is the number of items having feature j, j = 1, . . . , K in the set B and nB is the whole set of objects in set B. Taking the limit when K → ∞, we obtain after a few calculations Pr(ξ1:n ) = α + K[n] exp [−α ( C HnC − 2n −1 h=1 Kh ! HnS )] × C∈C + KC (nC −nj,C )!(nj,C −1)! j=1 nC ! S∈S S + KS (nS −nj,S )!(nj,S −1)! j=1 nS ! + + + + if K[n] = C KC − S KS and 0 otherwise, where KB is the number of different features possessed by objects in B. G Let En be the subset of En such that for each decomposition A, B and any (u, v) ∈ A × B: {u and v possess feature j} ⇒ ∃k ∈ A ∩ B such that {k possesses feature j}. Let ξ−k be the left-ordered + matrix obtained by removing object k from ξn and K−k be the total number of different features in G−k + ξ−k . For each feature j = 1, . . . , K−k , if ξ−k ∈ En−1 then we have   b C∈C nj,C if i = 1 S∈C nj,S Pr(ξk,j = i) = (16)  b C∈C (nC −nj,C ) if i = 0 (nS −nj,S ) S∈C nS where b is the appropriate normalizing constant then the customer k tries Poisson α {S∈S|k∈S} nC {C∈C|k∈C} new dishes. We can easily generalize this construction to a directed version D of G using arguments similar to those presented in Section 2; see Section 4 for an application to time-varying matrix factorization. 4 4.1 Applications Sharing clusters among relative groups: An alternative to HDP Consider that we are given d groups with nj data yi,j in each group, i = 1, . . . , nj , j = 1, . . . , d. We consider latent cluster variables zi,j that deﬁne the partition of the data. We will use alternatively the notation θi,j = Uzi,j in the following. Hierarchical Dirichlet Process [12] (HDP) is a very popular model for sharing clusters among related groups. It is based on a hierarchy of DPs G0 ∼ DP (γ, H), Gj |G0 ∼ DP (α, G0 ) j = 1, . . . d θi,j |Gj ∼ Gj , yi,j |θi,j ∼ f (θi,j ) i = 1, . . . , nj . Under conjugacy assumptions, G0 , Gj and U can be integrated out and we can approximate the marginal posterior of (zi,j ) given y = (yi,j ) with Gibbs sampling using the Chinese restaurant franchise to sample from the full conditional p(zi,j |z−{i,j} , y). Using the graph formulation deﬁned in Section 2, we propose an alternative to HDP. Let θ0,1 , . . . , θ0,N be N auxiliary variables belonging to what we call group 0. We deﬁne each clique Cj (j = 1, . . . , d) to be composed of elements from group j and elements from group 0. This deﬁnes a decomposable graphical model whose separator is given by the elements of group 0. We can rewrite the model in a way quite similar to HDP G0 ∼ DP (α, H), θ0,i |G0 ∼ G0 i = 1, ..., N α α Gj |θ0,1 , . . . , θ0,N ∼ DP (α + N, α+N H + α+N θi,j |Gj ∼ Gj , yi,j |θi,j ∼ f (θi,j ) i = 1, . . . , nj N i=1 δθ0,i ) j = 1, . . . d, N For any subset A and j = k ∈ {1, . . . , p} we have corr(Gj (A), Gk (A)) = α+N . Again, under conjugacy conditions, we can integrate out G0 , Gj and U and approximate the marginal posterior distribution over the partition using the Chinese wedding party process deﬁned in Section 2. Note that for latent variables zi,j , j = 1, . . . , d, associated to data, this is the usual CRP update. As in HDP, multiple layers can be added to the model. Figures 2 (a) and (b) resp. give the graphical DP alternative to HDP and 2-layer HDP. 6 z0 root z0 root corpora docs z1 z2 z1 z2 z3 z1,1 z1,2 z2,1 z2,2 z2,3 docs (a) Graphical DP alternative to HDP (b) Graphical DP alternative to 2-layer HDP Figure 2: Hierarchical Graphs of dependency with (a) one layer and (b) two layers of hierarchy. If N = 0, then Gj ∼ DP (α, H) for all j and this is equivalent to setting γ → ∞ in HDP. If N → ∞ then Gj = G0 for all j, G0 ∼ DP (α, H). This is equivalent to setting α → ∞ in the HDP. One interesting feature of the model is that, contrary to HDP, the marginal distribution of Gj at any layer of the tree is DP (α, H). As a consequence, the total number of clusters scales logarithmically (as in the usual DP) with the size of each group, whereas it scales doubly logarithmically in HDP. Contrary to HDP, there are at most N clusters shared between different groups. Our model is in that sense reminiscent of [9] where only a limited number of clusters can be shared. Note however that contrary to [9] we have a simple CRP-like process. The proposed methodology can be straightforwardly extended to the inﬁnite HMM [12]. The main issue of the proposed model is the setting of the number N of auxiliary parameters. Another issue is that to achieve high correlation, we need a large number of auxiliary variables. Nonetheless, the computational time used to sample from auxiliary variables is negligible compared to the time used for latent variables associated to data. Moreover, it can be easily parallelized. The model proposed offers a far richer framework and ensures that at each level of the tree, the marginal distribution of the partition is given by a DP partition model. 4.2 Time-varying matrix factorization Let X1:n be an observed matrix of dimension n × D. We want to ﬁnd a representation of this matrix in terms of two latent matrices Z1:n of dimension n × K and Y of dimension K × D. Here Z1:n 2 is a binary matrix whereas Y is a matrix of latent features. By assuming that Y ∼ N 0, σY IK×D and 2 X1:n = Z1:n Y + σX εn where εn ∼ N 0, σX In×D , we obtain p(X1:n |Z1:n ) ∝ −D/2 2 2 + Z+T Z+ + σX /σY IKn 1:n 1:n + (n−Kn )D σX exp − + Kn D σY 2 2 + where Σ−1 = I − Z+ Z+T Z+ + σX /σY IKn n 1:n 1:n 1:n −1 1 T −1 2 tr X1:n Σn X1:n 2σX (17) + Z+T , Kn the number of non-zero columns of 1:n + Z1:n and Z+ is the ﬁrst Kn columns of Z1:n . To avoid having to set K, [5, 14] assume that Z1:n 1:n follows an IBP. The resulting posterior distribution p(Z1:n |X1:n ) can be estimated through MCMC [5] or SMC [14]. We consider here a different model where the object Xt is assumed to arrive at time index t and we want a prior distribution on Z1:n ensuring that objects close in time are more likely to possess similar features. To achieve this, we consider the simple directed graphical model D of Fig. 3 where the site numbering corresponds to a time index in that case and a perfect numbering of D is (1, 2, . . .). The set of parents pa(t) is composed of the r preceding sites {{t − r}, . . . , {t − 1}}. The time-varying IBP to sample from p(Z1:n ) associated to this directed graph follows from (16) and proceeds as follows. At time t = 1 + new new • Sample K1 ∼Poisson(α), set z1,i = 1 for i = 1, ..., K1 and set K1 = Knew . At times t = 2, . . . , r n + new ∼Poisson( α ). • For k = 1, . . . Kt , sample zt,k ∼ Ber( 1:t−1,k ) and Kt t t 7 ? ? - t−r - t−r+1 - . . . - t−1 - t - t+1 6 6 Figure 3: Directed graph. At times t = r + 1, . . . , n n + α new ∼Poisson( r+1 ). • For k = 1, . . . Kt , sample zt,k ∼ Ber( t−r:t−1,k ) and Kt r+1 + Here Kt is the total number of features appearing from time max(1, t − r) to t − 1 and nt−r:t−1,k the restriction of n1:t−1 to the r last customers. Using (17) and the prior distribution of Z1:n which can be sampled using the time-varying IBP described above, we can easily design an SMC method to sample from p(Z1:n |X1:n ). We do not detail it here. Note that contrary to [14], our algorithm does not require inverting a matrix whose dimension grows linearly with the size of the data but only a matrix of dimension r × r. In order to illustrate the model and SMC algorithm, we create 200 6 × 6 images using a ground truth Y consisting of 4 different 6 × 6 latent images. The 200 × 4 binary matrix was generated from Pr(zt,k = 1) = πt,k , where πt = ( .6 .5 0 0 ) if t = 1, . . . , 30, πt = ( .4 .8 .4 0 ) if t = 31, . . . , 50 and πt = ( 0 .3 .6 .6 ) if t = 51, . . . , 200. The order of the model is set to r = 50. The feature occurences Z1:n and true features Y and their estimates are represented in Figure 4. Two spurious features are detected by the model (features 2 and 5 on Fig. 3(c)) but quickly discarded (Fig. 4(d)). The algorithm is able to correctly estimate the varying prior occurences of the features over time. Feature1 Feature2 Feature1 Feature2 Feature3 20 20 40 40 60 60 Feature4 80 100 Feature4 Feature5 Feature6 Time Feature3 Time 80 100 120 120 140 140 160 160 180 200 180 1 2 3 200 4 Feature (a) 1 2 3 4 5 6 Feature (b) (c) (d) Figure 4: (a) True features, (b) True features occurences, (c) MAP estimate ZM AP and (d) associated E[Y|ZM AP ] t=20 t=50 t=20 t=50 t=100 t=200 t=100 t=200 (a) (b) Figure 5: (a) E[Xt |πt , Y] and (b) E[Xt |X1:t−1 ] at t = 20, 50, 100, 200. 5 Related work and Discussion The ﬁxed-lag version of the time-varying DP of Caron et al. [1] is a special case of the proposed model when G is given by Fig. 3. The bivariate DP of Walker and Muliere [13] is also a special case when G has only two cliques. In this paper, we have assumed that the structure of the graph was known beforehand and we have shown that many ﬂexible models arise from this framework. It would be interesting in the future to investigate the case where the graphical structure is unknown and must be estimated from the data. Acknowledgment The authors thank the reviewers for their comments that helped to improve the writing of the paper. 8 References [1] F. Caron, M. Davy, and A. Doucet. Generalized Polya urn for time-varying Dirichlet process mixtures. In Uncertainty in Artiﬁcial Intelligence, 2007. [2] A.P. Dawid and S.L. Lauritzen. Hyper Markov laws in the statistical analysis of decomposable graphical models. The Annals of Statistics, 21:1272–1317, 1993. [3] M.D. Escobar and M. West. Bayesian density estimation and inference using mixtures. Journal of the American Statistical Association, 90:577–588, 1995. [4] P. Fearnhead. Particle ﬁlters for mixture models with an unknown number of components. Statistics and Computing, 14:11–21, 2004. [5] T.L. Grifﬁths and Z. Ghahramani. Inﬁnite latent feature models and the Indian buffet process. In Advances in Neural Information Processing Systems, 2006. [6] D. Heinz. Building hyper dirichlet processes for graphical models. Electonic Journal of Statistics, 3:290–315, 2009. [7] J.F.C. Kingman. Random partitions in population genetics. Proceedings of the Royal Society of London, 361:1–20, 1978. [8] S.L. Lauritzen. Graphical Models. Oxford University Press, 1996. [9] P. M¨ ller, F. Quintana, and G. Rosner. A method for combining inference across related nonu parametric Bayesian models. Journal of the Royal Statistical Society B, 66:735–749, 2004. [10] R.M. Neal. Markov chain sampling methods for Dirichlet process mixture models. Journal of Computational and Graphical Statistics, 9:249–265, 2000. [11] J. Pitman. Exchangeable and partially exchangeable random partitions. Probability theory and related ﬁelds, 102:145–158, 1995. [12] Y.W. Teh, M.I. Jordan, M.J. Beal, and D.M. Blei. Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101:1566–1581, 2006. [13] S. Walker and P. Muliere. A bivariate Dirichlet process. Statistics and Probability Letters, 64:1–7, 2003. [14] F. Wood and T.L. Grifﬁths. Particle ﬁltering for nonparametric Bayesian matrix factorization. In Advances in Neural Information Processing Systems, 2007. 9

5 0.12507637 123 nips-2009-Large Scale Nonparametric Bayesian Inference: Data Parallelisation in the Indian Buffet Process

Author: Finale Doshi-velez, Shakir Mohamed, Zoubin Ghahramani, David A. Knowles

Abstract: Nonparametric Bayesian models provide a framework for ﬂexible probabilistic modelling of complex datasets. Unfortunately, the high-dimensional averages required for Bayesian methods can be slow, especially with the unbounded representations used by nonparametric models. We address the challenge of scaling Bayesian inference to the increasingly large datasets found in real-world applications. We focus on parallelisation of inference in the Indian Buffet Process (IBP), which allows data points to have an unbounded number of sparse latent features. Our novel MCMC sampler divides a large data set between multiple processors and uses message passing to compute the global likelihoods and posteriors. This algorithm, the ﬁrst parallel inference scheme for IBP-based models, scales to datasets orders of magnitude larger than have previously been possible. 1

6 0.11944861 65 nips-2009-Decoupling Sparsity and Smoothness in the Discrete Hierarchical Dirichlet Process

7 0.10195772 255 nips-2009-Variational Inference for the Nested Chinese Restaurant Process

8 0.08834479 204 nips-2009-Replicated Softmax: an Undirected Topic Model

9 0.085907623 59 nips-2009-Construction of Nonparametric Bayesian Models from Parametric Bayes Equations

10 0.080493301 167 nips-2009-Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations

11 0.080059201 132 nips-2009-Learning in Markov Random Fields using Tempered Transitions

12 0.077075645 155 nips-2009-Modelling Relational Data using Bayesian Clustered Tensor Factorization

13 0.07585483 96 nips-2009-Filtering Abstract Senses From Image Search Results

14 0.071564637 114 nips-2009-Indian Buffet Processes with Power-law Behavior

15 0.068154141 104 nips-2009-Group Sparse Coding

16 0.06776385 140 nips-2009-Linearly constrained Bayesian matrix factorization for blind source separation

17 0.067534775 18 nips-2009-A Stochastic approximation method for inference in probabilistic graphical models

18 0.066775844 4 nips-2009-A Bayesian Analysis of Dynamics in Free Recall

19 0.066252738 201 nips-2009-Region-based Segmentation and Object Detection

20 0.06297864 197 nips-2009-Randomized Pruning: Efficiently Calculating Expectations in Large Dynamic Programs

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.183), (1, -0.079), (2, -0.044), (3, -0.165), (4, 0.1), (5, -0.159), (6, 0.068), (7, 0.016), (8, -0.029), (9, 0.059), (10, -0.03), (11, 0.002), (12, 0.021), (13, -0.021), (14, -0.067), (15, -0.012), (16, -0.048), (17, -0.057), (18, 0.095), (19, 0.11), (20, -0.024), (21, 0.086), (22, -0.052), (23, -0.027), (24, 0.024), (25, -0.044), (26, 0.003), (27, 0.013), (28, -0.06), (29, 0.084), (30, 0.104), (31, -0.074), (32, 0.032), (33, -0.076), (34, -0.057), (35, -0.037), (36, 0.03), (37, 0.13), (38, -0.01), (39, -0.064), (40, 0.054), (41, -0.069), (42, -0.087), (43, -0.029), (44, -0.016), (45, -0.063), (46, 0.069), (47, -0.005), (48, 0.139), (49, -0.008)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96071655 226 nips-2009-Spatial Normalized Gamma Processes

Author: Vinayak Rao, Yee W. Teh

2 0.64355284 40 nips-2009-Bayesian Nonparametric Models on Decomposable Graphs

Author: Francois Caron, Arnaud Doucet

3 0.57393658 217 nips-2009-Sharing Features among Dynamical Systems with Beta Processes

Author: Alan S. Willsky, Erik B. Sudderth, Michael I. Jordan, Emily B. Fox

4 0.57082093 205 nips-2009-Rethinking LDA: Why Priors Matter

Author: Andrew McCallum, David M. Mimno, Hanna M. Wallach

5 0.55867815 65 nips-2009-Decoupling Sparsity and Smoothness in the Discrete Hierarchical Dirichlet Process

Author: Chong Wang, David M. Blei

Abstract: We present a nonparametric hierarchical Bayesian model of document collections that decouples sparsity and smoothness in the component distributions (i.e., the “topics”). In the sparse topic model (sparseTM), each topic is represented by a bank of selector variables that determine which terms appear in the topic. Thus each topic is associated with a subset of the vocabulary, and topic smoothness is modeled on this subset. We develop an efﬁcient Gibbs sampler for the sparseTM that includes a general-purpose method for sampling from a Dirichlet mixture with a combinatorial number of components. We demonstrate the sparseTM on four real-world datasets. Compared to traditional approaches, the empirical results will show that sparseTMs give better predictive performance with simpler inferred models. 1

6 0.5425297 114 nips-2009-Indian Buffet Processes with Power-law Behavior

7 0.54180735 51 nips-2009-Clustering sequence sets for motif discovery

8 0.51693642 123 nips-2009-Large Scale Nonparametric Bayesian Inference: Data Parallelisation in the Indian Buffet Process

9 0.50980592 155 nips-2009-Modelling Relational Data using Bayesian Clustered Tensor Factorization

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

11 0.48476669 204 nips-2009-Replicated Softmax: an Undirected Topic Model

12 0.45953208 153 nips-2009-Modeling Social Annotation Data with Content Relevance using a Topic Model

13 0.45375076 172 nips-2009-Nonparametric Bayesian Texture Learning and Synthesis

14 0.42526978 132 nips-2009-Learning in Markov Random Fields using Tempered Transitions

15 0.42161283 69 nips-2009-Discrete MDL Predicts in Total Variation

16 0.40968516 59 nips-2009-Construction of Nonparametric Bayesian Models from Parametric Bayes Equations

17 0.4009451 18 nips-2009-A Stochastic approximation method for inference in probabilistic graphical models

18 0.39697409 167 nips-2009-Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations

19 0.39458442 186 nips-2009-Parallel Inference for Latent Dirichlet Allocation on Graphics Processing Units

20 0.39279744 5 nips-2009-A Bayesian Model for Simultaneous Image Clustering, Annotation and Object Segmentation

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(7, 0.033), (24, 0.037), (25, 0.09), (35, 0.056), (36, 0.108), (39, 0.068), (58, 0.064), (61, 0.014), (66, 0.019), (71, 0.108), (81, 0.018), (86, 0.057), (91, 0.025), (93, 0.208)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.93507385 194 nips-2009-Predicting the Optimal Spacing of Study: A Multiscale Context Model of Memory

Author: Harold Pashler, Nicholas Cepeda, Robert Lindsey, Ed Vul, Michael C. Mozer

Abstract: When individuals learn facts (e.g., foreign language vocabulary) over multiple study sessions, the temporal spacing of study has a signiﬁcant impact on memory retention. Behavioral experiments have shown a nonmonotonic relationship between spacing and retention: short or long intervals between study sessions yield lower cued-recall accuracy than intermediate intervals. Appropriate spacing of study can double retention on educationally relevant time scales. We introduce a Multiscale Context Model (MCM) that is able to predict the inﬂuence of a particular study schedule on retention for speciﬁc material. MCM’s prediction is based on empirical data characterizing forgetting of the material following a single study session. MCM is a synthesis of two existing memory models (Staddon, Chelaru, & Higa, 2002; Raaijmakers, 2003). On the surface, these models are unrelated and incompatible, but we show they share a core feature that allows them to be integrated. MCM can determine study schedules that maximize the durability of learning, and has implications for education and training. MCM can be cast either as a neural network with inputs that ﬂuctuate over time, or as a cascade of leaky integrators. MCM is intriguingly similar to a Bayesian multiscale model of memory (Kording, Tenenbaum, & Shadmehr, 2007), yet MCM is better able to account for human declarative memory. 1

same-paper 2 0.85553378 226 nips-2009-Spatial Normalized Gamma Processes

Author: Vinayak Rao, Yee W. Teh

3 0.69674152 40 nips-2009-Bayesian Nonparametric Models on Decomposable Graphs

Author: Francois Caron, Arnaud Doucet

4 0.69086266 154 nips-2009-Modeling the spacing effect in sequential category learning

Author: Hongjing Lu, Matthew Weiden, Alan L. Yuille

Abstract: We develop a Bayesian sequential model for category learning. The sequential model updates two category parameters, the mean and the variance, over time. We deﬁne conjugate temporal priors to enable closed form solutions to be obtained. This model can be easily extended to supervised and unsupervised learning involving multiple categories. To model the spacing effect, we introduce a generic prior in the temporal updating stage to capture a learning preference, namely, less change for repetition and more change for variation. Finally, we show how this approach can be generalized to efﬁciently perform model selection to decide whether observations are from one or multiple categories.

5 0.69057399 174 nips-2009-Nonparametric Latent Feature Models for Link Prediction

Author: Kurt Miller, Michael I. Jordan, Thomas L. Griffiths

Abstract: As the availability and importance of relational data—such as the friendships summarized on a social networking website—increases, it becomes increasingly important to have good models for such data. The kinds of latent structure that have been considered for use in predicting links in such networks have been relatively limited. In particular, the machine learning community has focused on latent class models, adapting Bayesian nonparametric methods to jointly infer how many latent classes there are while learning which entities belong to each class. We pursue a similar approach with a richer kind of latent variable—latent features—using a Bayesian nonparametric approach to simultaneously infer the number of features at the same time we learn which entities have each feature. Our model combines these inferred features with known covariates in order to perform link prediction. We demonstrate that the greater expressiveness of this approach allows us to improve performance on three datasets. 1

6 0.68974757 217 nips-2009-Sharing Features among Dynamical Systems with Beta Processes

7 0.68661833 260 nips-2009-Zero-shot Learning with Semantic Output Codes

8 0.68633854 97 nips-2009-Free energy score space

9 0.68624341 215 nips-2009-Sensitivity analysis in HMMs with application to likelihood maximization

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

11 0.68255645 56 nips-2009-Conditional Neural Fields

12 0.68126714 162 nips-2009-Neural Implementation of Hierarchical Bayesian Inference by Importance Sampling

13 0.67975414 204 nips-2009-Replicated Softmax: an Undirected Topic Model

14 0.67899811 132 nips-2009-Learning in Markov Random Fields using Tempered Transitions

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

16 0.67745763 18 nips-2009-A Stochastic approximation method for inference in probabilistic graphical models

17 0.67713749 188 nips-2009-Perceptual Multistability as Markov Chain Monte Carlo Inference

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

19 0.67578912 150 nips-2009-Maximum likelihood trajectories for continuous-time Markov chains

20 0.6756255 187 nips-2009-Particle-based Variational Inference for Continuous Systems