nips nips2008 nips2008-134 knowledge-graph by maker-knowledge-mining

134 nips-2008-Mixed Membership Stochastic Blockmodels

Source: pdf

Author: Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, Eric P. Xing

Abstract: In many settings, such as protein interactions and gene regulatory networks, collections of author-recipient email, and social networks, the data consist of pairwise measurements, e.g., presence or absence of links between pairs of objects. Analyzing such data with probabilistic models requires non-standard assumptions, since the usual independence or exchangeability assumptions no longer hold. In this paper, we introduce a class of latent variable models for pairwise measurements: mixed membership stochastic blockmodels. Models in this class combine a global model of dense patches of connectivity (blockmodel) with a local model to instantiate node-speciﬁc variability in the connections (mixed membership). We develop a general variational inference algorithm for fast approximate posterior inference. We demonstrate the advantages of mixed membership stochastic blockmodel with applications to social networks and protein interaction networks. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 EDU Abstract In many settings, such as protein interactions and gene regulatory networks, collections of author-recipient email, and social networks, the data consist of pairwise measurements, e. [sent-6, score-0.498]

2 In this paper, we introduce a class of latent variable models for pairwise measurements: mixed membership stochastic blockmodels. [sent-10, score-0.76]

3 We develop a general variational inference algorithm for fast approximate posterior inference. [sent-12, score-0.229]

4 We demonstrate the advantages of mixed membership stochastic blockmodel with applications to social networks and protein interaction networks. [sent-13, score-1.303]

5 1 Introduction The problem of modeling relational information among objects, such as pairwise relations represented as graphs, arises in a number of settings in machine learning. [sent-14, score-0.328]

6 For example, scientiﬁc literature connects papers by citation, the Web connects pages by links, and protein-protein interaction data connect proteins by physical interaction records. [sent-15, score-0.467]

7 Recently proposed models aim at resolving relational information into a collection of connectivity motifs. [sent-20, score-0.237]

8 For instance, exponential random graph models [11] summarize the variability in a collection of paired measurements with a set of relational motifs, but do not provide a representation useful for making unit-speciﬁc predictions. [sent-22, score-0.289]

9 Stochastic blockmodels [8, 6] resolve paired measurements into groups and connectivity between pairs of groups, but constrain each unit to instantiate the connectivity patterns of a single group as observed in most applications. [sent-24, score-0.463]

10 Mixed membership models, such as latent Dirichlet allocation [1], have emerged in recent years as a ﬂexible modeling tool for data where the single group assumption is violated by the heterogeneity within a unit of analysis—e. [sent-25, score-0.5]

11 Mixed membership models associate each unit of analysis with multiple groups rather than a single groups, via a membership ∗ A longer version of this work is available online, at http://jmlr. [sent-29, score-0.773]

12 The concurrent membership of a data in different groups can capture its different aspects, such as different underlying topics for words constituting each document. [sent-34, score-0.413]

13 The mixed membership formalism is a particularly natural idea for relational data, where the objects can bear multiple latent roles or cluster-memberships that inﬂuence their relationships to others. [sent-35, score-0.893]

14 Existing mixed membership models, however, are not appropriate for relational data because they assume that the data are conditionally independent given their latent membership vectors. [sent-36, score-1.187]

15 Conditional independence assumptions that technically instantiate mixed membership in recent work, however, are inappropriate for the relational data settings. [sent-37, score-0.775]

16 Thus assuming that the ensemble of mixed membership vectors help govern the relationships of each object would be more appropriate. [sent-39, score-0.615]

17 Here we develop mixed membership models for relational data and we describe a fast variational inference algorithm for inference and estimation. [sent-40, score-0.879]

18 Our model captures the multiple roles that objects exhibit in interaction with others, and the relationships between those roles in determining the observed interaction matrix. [sent-41, score-0.331]

19 We apply our model to protein interaction and social networks. [sent-42, score-0.316]

20 We summarize a collection of pairwise measurements with a mapping from nodes to sets of nodes, called blocks, and pairwise relations among the blocks themselves. [sent-48, score-0.567]

21 Intuitively, the inference process aims at identifying nodes that are similar to one another in terms of their connectivity to blocks of nodes. [sent-49, score-0.205]

22 Individual nodes are allowed to instantiate connectivity patterns of multiple blocks. [sent-51, score-0.204]

23 Thus, the goal of the analysis with a Mixed Membership Blockmodel (MMB) is to identify (i) the mixed membership mapping of nodes, i. [sent-52, score-0.591]

24 , the units of analysis, to a ﬁxed number of blocks, K, and (ii) the pairwise relations among the blocks. [sent-54, score-0.208]

25 Pairwise measurements among N nodes are then generated according to latent distributions of block-membership for each node and a matrix of block-to-block interaction strength. [sent-55, score-0.439]

26 Each node is associated with a randomly drawn vector, say πi for node i, where πi,g denotes the probability of node i belonging to group g. [sent-57, score-0.261]

27 The probabilities of interactions between different groups are deﬁned by a matrix of Bernoulli rates B(K×K) , where B(g, h) represents the probability of having a connection from a node in group g to a node in group h. [sent-59, score-0.463]

28 The indicator vector zp→q denotes the speciﬁc block membership of node p when it connects to node q, while zp←q denotes the speciﬁc block membership of node q when it is connected from node p. [sent-60, score-1.141]

29 The complete generative process for a graph G = (N , Y ) is as follows: • For each node p ∈ N : – Draw a K dimensional mixed membership vector πp ∼ Dirichlet α . [sent-61, score-0.662]

30 • For each pair of nodes (p, q) ∈ N × N : – Draw membership indicator for the initiator, zp→q ∼ Multinomial πp . [sent-62, score-0.411]

31 – Draw membership indicator for the receiver, zq→p ∼ Multinomial πq . [sent-63, score-0.36]

32 Note that the group membership of each node is context dependent, i. [sent-65, score-0.479]

33 , each node may assume different membership when interacting with different peers. [sent-67, score-0.431]

34 π 2 z 2→1 y 21 z 2→2 z 3←1 y 22 z 2→3 z 3←2 y 23 z 2→N z 3←3 y 2N B Figure 1: The graphical model of the mixed membership blockmodel (MMB). [sent-78, score-0.987]

35 It is useful to distinguish two sources of non- interaction: they may be the result of the rarity of interactions in general, or they may be an indication that the pair of relevant blocks rarely interact. [sent-110, score-0.288]

36 In applications to social sciences, for instance, nodes may represent people and blocks may represent social communities. [sent-111, score-0.326]

37 A good estimate of the portion of zeros that should not be explained by the blockmodel B reduces the bias of the estimates of B’s elements. [sent-114, score-0.453]

38 This is the result of assuming that the probability of a non- interaction comes from a mixture, 1 − σpq = (1 − ρ) · zp→q (1 − B) zp←q + ρ, where the weight ρ capture the portion zeros that should not be explained by the blockmodel B. [sent-118, score-0.56]

39 A large value of ρ will cause the interactions in the matrix to be weighted more than non- interactions, in determining plausible values for {α, B, π1:N }. [sent-119, score-0.172]

40 (1) π1:N zp←q ,zp→q We appeal to mean- ﬁeld variational methods [5] to approximate the posterior of interest. [sent-125, score-0.229]

41 The main idea behind variational methods is to posit a simple distribution of the latent variables with free parameters, which are ﬁt to make the approximation close in Kullback- Leibler divergence to the true posterior of interest. [sent-126, score-0.321]

42 We specify q as the mean- ﬁeld fully- factorized family, q(π1:N , Z→ , Z← | γ1:N , Φ→ , Φ← ), where {γ1:N , Φ→ , Φ← } is the set of free variational parameters that must be set to tighten the bound. [sent-128, score-0.192]

43 We 3 tighten the bound with respect to the variational parameters, to minimize the KL divergence between q and the true posterior. [sent-129, score-0.192]

44 The update for the variational multinomial parameters is ˆ φp→q,g ∝ e Eq log πp,g B(g, h)Y (p,q) · 1 − B(g, h) 1−Y (p,q) B(g, h)Y (p,q) · · 1 − B(g, h) 1−Y (p,q) φp←q,h (3) h ˆ φp←q,h ∝ e Eq log πq,h · φp→q,g , (4) g for g, h = 1, . [sent-130, score-0.196]

45 The update for the variational Dirichlet parameters γp,k is γp,k = αk + ˆ φp→q,k + φp←q,k , q (5) q for all nodes p = 1, . [sent-134, score-0.219]

46 To improve convergence, we developed a nested variational inference scheme based on an alternative schedule of updates to the traditional ordering [5]. [sent-142, score-0.229]

47 At each variational inference cycle one needs to allocate N K + 2N 2 K scalars. [sent-144, score-0.196]

48 The nested variational inference ı algorithm retains portion of this dependence across iterations by following a particular path to convergence. [sent-147, score-0.26]

49 We keep the block of free parameters (φp→q , φp←q ) at their optimal values conditionally on the other variational parameters. [sent-148, score-0.244]

50 At each variational cycle we allocate N K + 2K scalars only. [sent-151, score-0.196]

51 , to latent sources other than the block model B or the mixed membership vectors π1:N . [sent-165, score-0.76]

52 When summarizing data, we could integrate out the Zs analytically; this leads to numerical optimization of a smaller set of variational parameters, Γs. [sent-174, score-0.199]

53 When de-noising, the Zs are instrumental in estimating posterior expectations of each interactions individually—a network analog to the Kalman Filter. [sent-176, score-0.289]

54 The posterior expectations of an interaction is computed as πp B πq , and φp→q B φp←q , in the two cases. [sent-177, score-0.2]

55 Results on simulated data sampled accordingly to the model show that variational EM accurately recovers the mixed membership map, π1:N , and the blockmodel, B. [sent-179, score-0.786]

56 Nested variational scheduling of parameter updates makes inference parallelizable and a typically reaches a better solution than the na¨ve scheduling. [sent-181, score-0.237]

57 ı First we consider, whom-do-like relations among 18 novices in a New England monastery. [sent-182, score-0.191]

58 He made a strong case for the existence of tight factions among the novices: the loyal opposition (whose members joined the monastery ﬁrst), the young turks (who joined later on), the outcasts (who were not accepted in the two main factions), and the waverers (who did not take sides). [sent-186, score-0.521]

59 The events that took place during Sampson’s stay at the monastery supported his observations— members of the young turks resigned or were expelled over religious differences (John and Gregory). [sent-187, score-0.195]

60 Using the nested variational EM algorithm above, we ﬁt an array of mixed membership blockmodels with different values of K, and collected model estimates {ˆ , B} and posterior mixed membership vectors π1:18 for the novices. [sent-189, score-1.532]

61 Figure 2 shows the patterns that the mixed ˆ membership blockmodel with K = 3 recovers from data. [sent-192, score-1.04]

62 In particular, the top-left panel shows a ˆ graphical representation of the blockmodel B. [sent-193, score-0.427]

63 The block that we can identify a-posteriori with the loyal opposition is portrayed as central to the monastery, while the block identiﬁed with the outcasts shows the lowest internal coherence, in accordance with Sampson’s observations. [sent-194, score-0.26]

64 The top-right panel illustrates the posterior means of the mixed membership scores, E[π|Y ], for the 18 monks in the monastery. [sent-195, score-0.735]

65 The bottom panels contrast the different resolution of the original adjacency matrix of whom-do-like sociometric relations (left panel) obtained with the two analyses MMB enables. [sent-198, score-0.198]

66 Top- Right: Posterior mixed membership vectors, ˆ ˆ π1:18 , projected in the simplex. [sent-200, score-0.591]

67 Bottom: Original adjacency matrix of whom- do- like sociometric relations (left), relations predicted using approximate MLEs for π1:N and B (center), and relations de- noised using the model including Zs indicators (right). [sent-205, score-0.396]

68 If the goal of the analysis if to ﬁnd a parsimonious summary of the data, the amount of relational information that is captured by in α, B, and E[π|Y ] leads to a coarse reconstruction of the original ˆ ˆ sociomatrix (central panel). [sent-206, score-0.187]

69 Second, we consider a friendship network among a group of 69 students in grades 7–12. [sent-209, score-0.34]

70 The data is a collection of friendship relations among 69 students in a school surveyed in the National Study of Adolescent Health. [sent-211, score-0.37]

71 Two students expressed no friendship preferences and were excluded from the analysis. [sent-213, score-0.185]

72 We used variational EM algorithm to ﬁt an array of mixed membership blockmodels with different values of K, collected model estimates, and used an approximation to BIC to select K. [sent-214, score-0.819]

73 Conditionally on such a mapping, we assign students to the grade they are most associated with, according to their posterior- mean mixed membership vectors, E[πn |Y ]. [sent-217, score-0.776]

74 To be fair in the comparison with competing models, we assign students with a unique grade—despite MMB allows for mixed membership. [sent-218, score-0.372]

75 Table 1 computes the correspondence of grades to blocks by quoting the number of students in each grade- block pair, for MMB versus the mixture blockmodel (MB) in [2], and the latent space cluster model (LSCM) in [3]. [sent-219, score-0.822]

76 The extra- ﬂexibility MMB offers over MB and LSCM reduces bias in the prediction of the membership of students to blocks, in this problem. [sent-223, score-0.476]

77 In other words, mixed membership does not absorb noise in this example, rather it accommodates variability in the friendship relation that is instrumental in producing better predictions. [sent-224, score-0.713]

78 MMSB is the proposed mixed membership stochastic blockmodel, MSB is the mixture blockmodel in [2], and LSCM is the latent space cluster model in [3]. [sent-226, score-1.079]

79 Third, we consider physical interactions among 871 proteins in yeast. [sent-227, score-0.391]

80 Precision The pairwise measurements consist of a hand-curated collection of physical protein interactions made available by the Munich Institute of Protein Sequencing (MIPS). [sent-229, score-0.57]

81 The yeast genome database provides independent functional annotations for each protein, which we use for evaluating the functional content of the protein networks estimated with the MMB from the MIPS data, as detailed below. [sent-230, score-0.341]

82 225, and used ﬁve-fold cross-validation to identify a blockmodel B that reduces the dimensionality of the physical interactions among proteins in the training set, while revealing robust aspects of connectivity that can be leveraged to predict physical interactions among proteins in the test set. [sent-234, score-1.241]

83 We determined that a fairly parsimonious model, K = 50, provides a good description of the observed physical interaction network. [sent-235, score-0.204]

84 This ﬁnding supports the hypothesis that proteins derived from the MIPS data are interpretable in terms functional biological contexts. [sent-236, score-0.18]

85 Alternatively, the blocks might encode signal at a ﬁner resolution, such as that of protein complexes. [sent-237, score-0.208]

86 If that was the case, however, we would expect the optimal number of blocks to be signiﬁcantly higher; 871/5 ≈ 175, given an average size of ﬁve proteins in a protein complex. [sent-238, score-0.331]

87 The goal is to assess to what extent MMB reveals substantive information about the functionality of proteins that can be used to inform subsequent analyses. [sent-240, score-0.177]

88 Thresholding such expectations at q, for instance, leads to a collection of binary physical interactions that are at reliable with probability p ≥ q. [sent-243, score-0.322]

89 org) to decide which interactions are functionally meaningful; namely those between pairs of proteins that share at least one functional annotation. [sent-246, score-0.393]

90 7 to the model that reveals functionally relevant interactions according to SGD. [sent-248, score-0.213]

91 Figure 3 shows the functional content of the original MIPS collection of physical interactions (point no. [sent-249, score-0.394]

92 2), and of the collections of interactions computed using (B, Πs), the light blue (−×) line, and using (B, Zs), the dark blue (−+) line, thresholded at ten different levels—precision-recall curves. [sent-250, score-0.212]

93 The posterior means of Πs provide a parsimonious representation for the MIPS collection, and lead to precise protein interaction estimates, in moderate amount (−× line). [sent-251, score-0.318]

94 The posterior means of Zs provide a richer representation for the data, and describe most of the functional content of the MIPS collection with high precision (−+ line). [sent-252, score-0.219]

95 This means that the proposed latent block structure is helpful in effectively denoising the collection of interactions—by ranking them properly. [sent-256, score-0.198]

96 In conclusion, our results suggest that MMB successfully reduces the dimensionality of the data, while discovering information about the multiple functionality of proteins that can be used to inform follow-up analyses. [sent-258, score-0.177]

97 In the relational setting, cross-validation is feasible if the blockmodel estimated on training data can be expected to hold on test data; for this to happen the network must be of reasonable size, so that we can expect members of each block to be in both training and test sets. [sent-261, score-0.603]

98 In this setting, scheduling of variational updates is important; nested variational scheduling leads to efﬁcient and parallelizable inference. [sent-262, score-0.505]

99 This is not the case, however, as the blockmodel B captures global/asymmetric relations, while the mixed membership vectors Πs capture local/symmetric relations. [sent-265, score-0.987]

100 For instance, technologies for measuring interactions between pairs of proteins, such as mass spectrometry and tandem afﬁnity puriﬁcation, which return a probabilistic assessment about the presence of interactions, thus setting the range of Y ∈ [0, 1]. [sent-272, score-0.172]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('blockmodel', 0.396), ('mmb', 0.396), ('membership', 0.36), ('mixed', 0.231), ('zp', 0.209), ('mips', 0.172), ('interactions', 0.172), ('variational', 0.168), ('sampson', 0.155), ('proteins', 0.123), ('relational', 0.12), ('protein', 0.117), ('students', 0.116), ('interaction', 0.107), ('relations', 0.099), ('zs', 0.093), ('social', 0.092), ('latent', 0.092), ('blocks', 0.091), ('measurements', 0.086), ('pairwise', 0.077), ('grades', 0.075), ('node', 0.071), ('memberships', 0.069), ('friendship', 0.069), ('grade', 0.069), ('lscm', 0.069), ('monastery', 0.069), ('sociometric', 0.069), ('instantiate', 0.064), ('physical', 0.064), ('connectivity', 0.063), ('nested', 0.061), ('posterior', 0.061), ('novices', 0.06), ('blockmodels', 0.06), ('qh', 0.06), ('functional', 0.057), ('qg', 0.055), ('collection', 0.054), ('groups', 0.053), ('block', 0.052), ('anthropological', 0.052), ('factions', 0.052), ('loyal', 0.052), ('monks', 0.052), ('opposition', 0.052), ('outcasts', 0.052), ('turks', 0.052), ('nodes', 0.051), ('group', 0.048), ('content', 0.047), ('mb', 0.041), ('functionally', 0.041), ('collections', 0.04), ('objects', 0.039), ('young', 0.039), ('scheduling', 0.039), ('eq', 0.038), ('bic', 0.037), ('na', 0.036), ('members', 0.035), ('annotations', 0.035), ('mmsb', 0.034), ('raftery', 0.034), ('sociomatrix', 0.034), ('waverers', 0.034), ('parsimonious', 0.033), ('mle', 0.033), ('connects', 0.033), ('dirichlet', 0.033), ('among', 0.032), ('expectations', 0.032), ('summarizing', 0.031), ('portion', 0.031), ('panel', 0.031), ('parallelizable', 0.03), ('inform', 0.03), ('simplicial', 0.03), ('adjacency', 0.03), ('variability', 0.029), ('bernoulli', 0.028), ('multinomial', 0.028), ('yeast', 0.028), ('allocate', 0.028), ('gregory', 0.028), ('exchangeability', 0.028), ('roles', 0.027), ('recovers', 0.027), ('patterns', 0.026), ('joined', 0.026), ('zeros', 0.026), ('fair', 0.025), ('sources', 0.025), ('instrumental', 0.024), ('tighten', 0.024), ('functionality', 0.024), ('conditionally', 0.024), ('relationships', 0.024), ('draw', 0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 134 nips-2008-Mixed Membership Stochastic Blockmodels

Author: Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, Eric P. Xing

2 0.081887446 225 nips-2008-Supervised Bipartite Graph Inference

Author: Yoshihiro Yamanishi

Abstract: We formulate the problem of bipartite graph inference as a supervised learning problem, and propose a new method to solve it from the viewpoint of distance metric learning. The method involves the learning of two mappings of the heterogeneous objects to a uniﬁed Euclidean space representing the network topology of the bipartite graph, where the graph is easy to infer. The algorithm can be formulated as an optimization problem in a reproducing kernel Hilbert space. We report encouraging results on the problem of compound-protein interaction network reconstruction from chemical structure data and genomic sequence data. 1

3 0.078232884 221 nips-2008-Stochastic Relational Models for Large-scale Dyadic Data using MCMC

Author: Shenghuo Zhu, Kai Yu, Yihong Gong

Abstract: Stochastic relational models (SRMs) [15] provide a rich family of choices for learning and predicting dyadic data between two sets of entities. The models generalize matrix factorization to a supervised learning problem that utilizes attributes of entities in a hierarchical Bayesian framework. Previously variational Bayes inference was applied for SRMs, which is, however, not scalable when the size of either entity set grows to tens of thousands. In this paper, we introduce a Markov chain Monte Carlo (MCMC) algorithm for equivalent models of SRMs in order to scale the computation to very large dyadic data sets. Both superior scalability and predictive accuracy are demonstrated on a collaborative ﬁltering problem, which involves tens of thousands users and half million items. 1 Stochastic Relational Models Stochastic relational models (SRMs) [15] are generalizations of Gaussian process (GP) models [11] to the relational domain, where each observation is a dyadic datum, indexed by a pair of entities. They model dyadic data by a multiplicative interaction of two Gaussian process priors. Let U be the feature representation (or index) space of a set of entities. A pair-wise similarity in U is given by a kernel (covariance) function Σ : U × U → R. A Gaussian process (GP) deﬁnes a random function f : U → R, whose distribution is characterized by a mean function and the covariance function Σ, denoted by f ∼ N∞ (0, Σ)1 , where, for simplicity, we assume the mean to be the constant zero. GP complies with the intuition regarding the smoothness — if two entities ui and uj are similar according to Σ, then f (ui ) and f (uj ) are similar with a high probability. A domain of dyadic data must involve another set of entities, let it be represented (or indexed) by V. In a similar way, this entity set is associated with another kernel function Ω. For example, in a typical collaborative ﬁltering domain, U represents users while V represents items, then, Σ measures the similarity between users and Ω measures the similarity between items. Being the relation between a pair of entities from different sets, a dyadic variable y is indexed by the product space U × V. Then an SRM aims to model y(u, v) by the following generative process, Model 1. The generative model of an SRM: 1. Draw kernel functions Σ ∼ IW ∞ (δ, Σ◦ ), and Ω ∼ IW ∞ (δ, Ω◦ ); 2. For k = 1, . . . , d: draw random functions fk ∼ N∞ (0, Σ), and gk ∼ N∞ (0, Ω); 1 We denote an n dimensional Gaussian distribution with a covariance matrix Σ by Nn (0, Σ). Then N∞ (0, Σ) explicitly indicates that a GP follows an “inﬁnite dimensional” Gaussian distribution. 1 3. For each pair (u, v): draw y(u, v) ∼ p(y(u, v)|z(u, v), γ), where d 1 z(u, v) = √ fk (u)gk (v) + b(u, v). d k=1 In this model, IW ∞ (δ, Σ◦ ) and IW ∞ (δ, Ω◦ ) are hyper priors, whose details will be introduced later. p(y|z, γ) is the problem-speciﬁc noise model. For example, it can follow a Gaussian noise distribution y ∼ N1 (z, γ) if y is numerical, or, a Bernoulli distribution if y is binary. Function b(u, v) is the bias function over the U × V. For simplicity, we assume b(u, v) = 0. In the limit d → ∞, the model converges to a special case where fk and gk can be analytically marginalized out and z becomes a Gaussian process z ∼ N∞ (0, Σ ⊗ Ω) [15], with the covariance between pairs being a tensor kernel K ((ui , vs ), (uj , vt )) = Σ(ui , uj )Ω(vs , vt ). In anther special case, if Σ and Ω are both ﬁxed to be Dirac delta functions, and U, V are ﬁnite sets, it is easy to see that the model reduces to probabilistic matrix factorization. The hyper prior IW ∞ (δ, Σ◦ ) is called inverted Wishart Process that generalizes the ﬁnite ndimensional inverted Wishart distribution [2] IW n (Σ|δ, Σ◦ ) ∝ |Σ| − 1 (δ+2n) 2 1 etr − Σ−1 Σ◦ , 2 where δ is the degree-of-freedom parameter, and Σ◦ is a positive deﬁnite kernel matrix. We note that the above deﬁnition is different from the popular formulation [3] or [4] in the machine learning community. The advantage of this new notation is demonstrated by the following theorem [2]. Theorem 1. Let A ∼ IW m (δ, K), A ∈ R+ , K ∈ R+ , and A and K be partitioned as A= A11 , A12 , A21 , A22 K= K11 , K12 K21 , K22 where A11 and K11 are two n × n sub matrices, n < m, then A11 ∼ IW n (δ, K11 ). The new formulation of inverted Wishart is consistent under marginalization. Therefore, similar to the way of deriving GPs from Gaussian distributions, we deﬁne a distribution of inﬁnite-dimensional kernel functions, denoted by Σ ∼ IW ∞ (δ, Σ◦ ), such that any sub kernel matrix of size m × m follows Σ ∼ IW m (δ, Σ◦ ), where both Σ and Σ◦ are positive deﬁnite kernel functions. In case when U and V are sets of entity indices, SRMs let Σ◦ and Ω◦ both be Dirac delta functions, i.e., any of their sub kernel matrices is an identity matrix. Similar to GP regression/classiﬁcation, the major application of SRMs is supervised prediction based on observed relational values and input features of entities. Formally, let YI = {y(u, v)|(u, v) ∈ I} be the set of noisy observations, where I ⊂ U × V, the model aims to predict the noise-free values ZO = {z(u, v)|(u, v) ∈ O} on O ⊂ U × V. As our computation is always on a ﬁnite set containing both I and O, from now on, we only consider the ﬁnite subset U0 × V0 , a ﬁnite support subset of U × V that contains I ∪ O. Accordingly we let Σ be the covariance matrix of Σ on U0 , and Ω be the covariance matrix of Ω on V0 . Previously a variational Bayesian method was applied to SRMs [15], which computes the maximum a posterior estimates of Σ and Ω, given YI , and then predicts ZO based on the estimated Σ and Ω. There are two limitations of this empirical Bayesian approach: (1) The variational method is not a fully Bayesian treatment. Ideally we wish to integrate Σ and Ω; (2) The more critical issue is, the algorithm has the complexity O(m3 + n3 ), with m = |U0 | and n = |V0 |, is not scalable to a large relational domain where m or n exceeds several thousands. In this paper we will introduce a fully Bayesian inference algorithm using Markov chain Monte Carlo sampling. By deriving equivalent sampling processes, we show the algorithms can be applied to a dataset, which is 103 times larger than the previous work [15], and produce an excellent accuracy. In the rest of this paper, we present our algorithms for Bayesian inference of SRMs in Section 2. Some related work is discussed in Section 3, followed by experiment results of SRMs in Section 4. Section 5 concludes. 2 2 Bayesian Models and MCMC Inference In this paper, we tackle the scalability issue with a fully Bayesian paradigm. We estimate the expectation of ZO directly from YI using Markov-chain Monte Carlo (MCMC) algorithm (speciﬁcally, Gibbs sampling), instead of evaluating that from estimated Σ or Ω. Our contribution is in how to make the MCMC inference more efﬁcient for large scale data. We ﬁrst introduce some necessary notation here. Bold capital letters, e.g. X, indicate matrices. I(m) is an identity matrix of size m × m. Nd , Nm,d , IW m , χ−2 are the multivariate normal distribution, the matrix-variate normal distribution, the inverse-Wishart distribution, and the inverse chi-square distribution, respectively. 2.1 Models with Non-informative Priors Let r = |I|, m = |U0 | and n = |V0 |. It is assumed that d min(m, n), and the observed set, I, is sparse, i.e. r mn. First, we consider the case of Σ◦ = αI(m) and Ω◦ = βI(n) . Let {fk } on U0 denoted by matrix variate F of size m × d, {gk } on V0 denoted by matrix variate G of size n × d. Then the generative model is written as Model 2 and depicted in Figure 1. Model 2. The generative model of a matrix-variate SRM: Σ 1. Draw Σ ∼ IW m (δ, αI(m) ) and Ω ∼ IW n (δ, βI(n) ); Ω I(d) G F 2. Draw F|Σ ∼ Nm,d (0, Σ ⊗ I(d) ) and G|Ω ∼ Nn,d (0, Ω ⊗ I(d) ); I(d) Z 3. Draw s2 ∼ χ−2 (ν, σ 2 ) ; 4. Draw Y|F, G, s2 ∼ Nm,n (Z, s2 I(m) ⊗ I(n) ), where Z = FG . s2 Y where Nm,d is the matrix-variate normal distribution of size m × d; α, Figure 1: Model 2 β, δ, ν and σ 2 are scalar parameters of the model. A slight difference √ between this ﬁnite model and Model 1 is that the coefﬁcient 1/ d is ignored for simplicity because this coefﬁcient can be absorbed by α or β. As we can explicitly compute Pr(Σ|F), Pr(Ω|G), Pr(F|YI , G, Σ, s2 ), Pr(G|YI , F, Ω, s2 ), Pr(s2 |YI , F, G), we can apply Gibbs sampling algorithm to compute ZO . However, the computational time complexity is at least O(m3 + n3 ), which is not practical for large scale data. 2.2 Gibbs Sampling Method To overcome the inefﬁciency in sampling large covariance matrices, we rewrite the sampling process using the property of Theorem 2 to take the advantage of d min(m, n). αI(d) αI(m) Theorem 2. If 1. Σ ∼ IW m (δ, αI(m) ) and F|Σ ∼ Nm,d (0, Σ ⊗ I(d) ), 2. K ∼ IW d (δ, αI(d) ) and H|K ∼ Nm,d (0, I(m) ⊗ K), then, matrix variates, F and H, have the same distribution. Proof sketch. Matrix variate F follows a matrix variate t distribution, t(δ, 0, αI(m) , I(d) ), which is written as 1 Σ I(d) F → I(m) K F Figure 2: Theorem 2 1 p(F) ∝ |I(m) + (αI(m) )−1 F(I(d) )−1 F |− 2 (δ+m+d−1) = |I(m) + α−1 FF |− 2 (δ+m+d−1) Matrix variate H follows a matrix variate t distribution, t(δ, 0, I(m) , αI(d) ), which can be written as 1 1 p(H) ∝ |I(m) + (I(m) )−1 H(αI(d) )−1 H |− 2 (δ+m+d−1) = |I(m) + α−1 HH |− 2 (δ+m+d−1) Thus, matrix variates, F and H, have the same distribution. 3 This theorem allows us to sample a smaller covariance matrix K of size d × d on the column side instead of sampling a large covariance matrix Σ of size m × m on the row side. The translation is depicted in Figure 2. This theorem applies to G as well, thus we rewrite the model as Model 3 (or Figure 3). A similar idea was used in our previous work [16]. Model 3. The alternative generative model of a matrix-variate SRM: I(m) I(n) K R 1. Draw K ∼ IW d (δ, αI(d) ) and R ∼ IW d (δ, βI(d) ); G F 2. Draw F|K ∼ Nm,d (0, I(m) ⊗ K), and G|R ∼ Nn,d (0, I(n) ⊗ R), 3. Draw s2 ∼ χ−2 (ν, σ 2 ) ; Z 4. Draw Y|F, G, s2 ∼ Nm,n (Z, s2 I(m) ⊗ I(n) ), where Z = FG . s2 Y Let column vector f i be the i-th row of matrix F, and column vector gj Figure 3: Model 3 be the j-th row of matrix G. In Model 3, {f i } are independent given K, 2 G and s . Similar independence applies to {gj } as well. The conditional posterior distribution of K, R, {f i }, {gj } and s2 can be easily computed, thus the Gibbs sampling for SRM is named BSRM (for Bayesian SRM). We use Gibbs sampling to compute the mean of ZO , which is derived from the samples of FG . Because of the sparsity of I, each iteration in this sampling algorithm can be computed in O(d2 r + d3 (m + n)) time complexity2 , which is a dramatic reduction from the previous time complexity O(m3 + n3 ) . 2.3 Models with Informative Priors An important characteristic of SRMs is that it allows the inclusion of certain prior knowledge of entities into the model. Speciﬁcally, the prior information is encoded as the prior covariance parameters, i.e. Σ◦ and Ω◦ . In the general case, it is difﬁcult to run sampling process due to the size of Σ◦ and Ω◦ . We assume that Σ◦ and Ω◦ have a special form, i.e. Σ◦ = F◦ (F◦ ) + αI(m) , where F◦ is an m × p matrix, and Ω◦ = G◦ (G◦ ) + βI(n) , where G◦ is an n × q matrix, and the magnitude of p and q is about the same as or less than that of d. This prior knowledge can be obtained from some additional features of entities. Although such an informative Σ◦ prevents us from directly sampling each row of F independently, as we do in Model 3, we can expand matrix F of size m × d to (F, F◦ ) of size m × (d + p), and derive an equivalent model, where rows of F are conditionally independent given F◦ . Figure 4 illustrates this transformation. Theorem 3. Let δ > p, Σ◦ = F◦ (F◦ ) + αI(m) , where F◦ is an m × p matrix. If 1. Σ ∼ IW m (δ, Σ◦ ) and F|Σ ∼ Nm,d (0, Σ ⊗ I(d) ), K11 K12 ∼ IW d+p (δ − p, αI(d+p) ) and K21 K22 H|K ∼ Nm,d (F◦ K−1 K21 , I(m) ⊗ K11·2 ), 22 2. K = αI(d+p) Σ0 Σ I(d) F → I(m) K (F, F0 ) Figure 4: Theorem 3 where K11·2 = K11 − K12 K−1 K21 , then F and H have the same distribution. 22 Proof sketch. Consider the distribution (H1 , H2 )|K ∼ Nm,d+p (0, I(m) ⊗ K). (1) Because H1 |H2 ∼ Nm,d (H2 K−1 K21 , I(m) ⊗ K11·2 ), p(H) = p(H1 |H2 = F◦ ). On the other 22 hand, we have a matrix-variate t distribution, (H1 , H2 ) ∼ tm,d+p (δ − p, 0, αI(m) , I(d+p) ). By Theorem 4.3.9 in [4], we have H1 |H2 ∼ tm,d (δ, 0, αI(m) + H2 H2 , I(d) ) = tm,d (δ, 0, Σ◦ , I(d) ), which implies p(F) = p(H1 |H2 = F◦ ) = p(H). 2 |Y − FG |2 can be efﬁciently computed in O(dr) time. I 4 The following corollary allows us to compute the posterior distribution of K efﬁciently. Corollary 4. K|H ∼ IW d+p (δ + m, αI(d+p) + (H, F◦ ) (H, F◦ )). Proof sketch. Because normal distribution and inverse Wishart distribution are conjugate, we can derive the posterior distribution K from Eq. (1). Thus, we can explicitly sample from the conditional posterior distributions, as listed in Algorithm 1 (BSRM/F for BSRM with features) in Appendix. We note that when p = q = 0, Algorithm 1 (BSRM/F) reduces to the exact algorithm for BSRM. Each iteration in this sampling algorithm can be computed in O(d2 r + d3 (m + n) + dpm + dqn) time complexity. 2.4 Unblocking for Sampling Implementation Blocking Gibbs sampling technique is commonly used to improve the sampling efﬁciency by reducing the sample variance according to the Rao-Blackwell theorem (c.f. [9]). However, blocking Gibbs sampling is not necessary to be computationally efﬁcient. To improve the computational efﬁciency of Algorithm 1, we use unblocking sampling to reduce the major computational cost is Step 2 and Step 4. We consider sampling each element of F conditionally. The sampling process is written as Step 4 and Step 9 of Algorithm 2, which is called BSRM/F with conditional Gibss sampling. We can reduce the computational cost of each iteration to O(dr + d2 (m + n) + dpm + dqn), which is comparable to other low-rank matrix factorization approaches. Though such a conditional sampling process increases the sample variance comparing to Algorithm 1, we can afford more samples within a given amount of time due to its faster speed. Our experiments show that the overall computational cost of Algorithm 2 is usually less than that of Algorithm 1 when achieving the same accuracy. Additionally, since {f i } are independent, we can parallelize the for loops in Step 4 and Step 9 of Algorithm 2. 3 Related Work SRMs fall into a class of statistical latent-variable relational models that explain relations by latent factors of entities. Recently a number of such models were proposed that can be roughly put into two groups, depending on whether the latent factors are continuous or discrete: (1) Discrete latent-state relational models: a large body of research infers latent classes of entities and explains the entity relationship by the probability conditioned on the joint state of participating entities, e.g., [6, 14, 7, 1]. In another work [10], binary latent factors are modeled; (2) Continuous latent-variable relational models: many such models assume relational data underlain by multiplicative effects between latent variables of entities, e.g. [5]. A simple example is matrix factorization, which recently has become very popular in collaborative ﬁltering applications, e.g., [12, 8, 13]. The latest Bayesian probabilistic matrix factorization [13] reported the state-of-the-art accuracy of matrix factorization on Netﬂix data. Interestingly, the model turns out to be similar to our Model 3 under the non-informative prior. This paper reveals the equivalence between different models and offers a more general Bayesian framework that allows informative priors from entity features to play a role. The framework also generalizes Gaussian processes [11] to a relational domain, where a nonparametric prior for stochastic relational processes is described. 4 Experiments Synthetic data: We compare BSRM under noninformative priors against two other algorithms: the fast max-margin matrix factorization (fMMMF) in [12] with a square loss, and SRM using variational Bayesian approach (SRM-VB) in [15]. We generate a 30 × 20 random matrix (Figure 5(a)), then add Gaussian noise with σ 2 = 0.1 (Figure 5(b)). The root mean squared noise is 0.32. We select 70% elements as the observed data and use the rest of the elements for testing. The reconstruction matrix and root mean squared errors (RMSEs) of predictions on the test elements are shown in Figure 5(c)-5(e). BSRM outperforms the variational approach of SRMs and fMMMF. Note that because of the log-determinant penalty of the inverse Wishart prior, SRM-VB enforces the rank to be smaller, thus the result of SRM-VB looks smoother than that of BSRM. 5 5 5 5 5 5 10 10 10 10 10 15 15 15 15 15 20 20 20 20 20 25 25 25 25 30 30 2 4 6 8 10 12 14 16 18 20 30 2 4 6 8 10 12 14 16 18 20 25 30 2 4 6 8 10 12 14 16 18 20 30 2 4 6 8 10 12 14 16 18 20 (a) Original Matrix (b) With Noise(0.32) (c) fMMMF (0.27) (d) SRM-VB(0.22) 2 4 6 8 10 12 14 16 18 20 (e) BSRM(0.19) Figure 5: Experiments on synthetic data. RMSEs are shown in parentheses. RMSE MAE User Mean 1.425 1.141 Movie Mean 1.387 1.103 fMMMF [12] 1.186 0.943 VB [8] 1.165 0.915 Table 1: RMSE (root mean squared error) and MAE (mean absolute error) of the experiments on EachMovie data. All standard errors are 0.001 or less. EachMovie data: We test the accuracy and the efﬁciency of our algorithms on EachMovie. The dataset contains 74, 424 users’ 2, 811, 718 ratings on 1, 648 movies, i.e. about 2.29% are rated by zero-to-ﬁve stars. We put all the ratings into a matrix, and randomly select 80% as observed data to predict the remaining ratings. The random selection was carried out 10 times independently. We compare our approach against several competing methods: 1) User Mean, predicting ratings by the sample mean of the same user’s ratings; 2) Move Mean, predicting rating by the sample mean of ratings on the same movie; 3) fMMMF [12]; 4) VB introduced in [8], which is a probabilistic lowrank matrix factorization using variational approximation. Because of the data size, we cannot run the SRM-VB of [15]. We test the algorithms BSRM and BSRM/F, both following Algorithm 2, which run without and with features, respectively. The features used in BSRM/F are generated from the PCA result of the binary indicator matrix that indicates whether the user rates the movie. The 10 top factors of both the user side and the movie side are used as features, i.e. p = 10, q = 10. We run the experiments with different d = 16, 32, 100, 200, 300. The hyper parameters are set to some trivial values, δ = p + 1 = 11, α = β = 1, σ 2 = 1, and ν = 1. The results are shown in Table 1 and 2. We ﬁnd that the accuracy improves as the number of d is increased. Once d is greater than 100, the further improvement is not very signiﬁcant within a reasonable amount of running time. rank (d) BSRM RMSE MAE BSRM/F RMSE MAE 16 1.0983 0.8411 1.0952 0.8311 32 1.0924 0.8321 1.0872 0.8280 100 1.0905 0.8335 1.0848 0.8289 200 1.0903 0.8340 1.0846 0.8293 300 1.0902 0.8393 1.0852 0.8292 Table 2: RMSE (root mean squared error) and MAE (mean absolute error) of experiments on EachMovie data. All standard errors are 0.001 or less. RMSE To compare the overall computational efﬁciency of the two Gibbs sampling procedures, Algorithm 1 and Algorithm 2, we run both algorithms 1.2 and record the running time and accuracy Algorithm 1 Algorithm 2 in RMSE. The dimensionality d is set to 1.18 be 100. We compute the average ZO and burn-in ends evaluate it after a certain number of itera1.16 tions. The evaluation results are shown in Figure 6. We run both algorithms for 100 1.14 burn-in ends iterations as the burn-in period, so that we 1.12 can have an independent start sample. After the burn-in period, we restart to compute 1.1 the averaged ZO and evaluate them, therefore there are abrupt points at 100 iterations 1.08 in both cases. The results show that the 0 1000 2000 3000 4000 5000 6000 7000 8000 overall accuracy of Algorithm 2 is better at Running time (sec) any given time. Figure 6: Time-Accuracy of Algorithm 1 and 2 6 Netﬂix data: We also test the algorithms on the large collection of user ratings from netﬂix.com. The dataset consists of 100, 480, 507 ratings from 480, 189 users on 17, 770 movies. In addition, Netﬂix also provides a set of validation data with 1, 408, 395 ratings. In order to evaluate the prediction accuracy, there is a test set containing 2, 817, 131 ratings whose values are withheld and unknown for all the participants. The features used in BSRM/F are generated from the PCA result of a binary matrix that indicates whether or not the user rated the movie. The top 30 user-side factors are used as features, none of movie-side factors are used, i.e. p = 30, q = 0. The hyper parameters are set to some trivial values, δ = p + 1 = 31, α = β = 1, σ 2 = 1, and ν = 1. The results on the validation data are shown in Table 3. The submitted result of BSRM/F(400) achieves RMSE 0.8881 on the test set. The running time is around 21 minutes per iteration for 400 latent dimensions on an Intel Xeon 2GHz PC. RMSE VB[8] 0.9141 BPMF [13] 0.8920 100 0.8930 BSRM 200 0.8910 400 0.8895 100 0.8926 BSRM/F 200 400 0.8880 0.8874 Table 3: RMSE (root mean squared error) of experiments on Netﬂix data. 5 Conclusions In this paper, we study the fully Bayesian inference for stochastic relational models (SRMs), for learning the real-valued relation between entities of two sets. We overcome the scalability issue by transforming SRMs into equivalent models, which can be efﬁciently sampled. The experiments show that the fully Bayesian inference outperforms the previously used variational Bayesian inference on SRMs. In addition, some techniques for efﬁcient computation in this paper can be applied to other large-scale Bayesian inferences, especially for models involving inverse-Wishart distributions. Acknowledgment: We thank the reviewers and Sarah Tyler for constructive comments. References [1] E. Airodi, D. Blei, S. Fienberg, and E. P. Xing. Mixed membership stochastic blockmodels. In Journal of Machine Learning Research, 2008. [2] A. P. Dawid. Some matrix-variate distribution theory: notational considerations and a Bayesian application. Biometrika, 68:265–274, 1981. [3] A. Gelman, J. B. Carlin, H. S. Stern, and D. B. Rubin. Bayesian Data Analysis. Chapman & Hall, New York, 1995. [4] A. K. Gupta and D. K. Nagar. Matrix Variate Distributions. Chapman & Hall/CRC, 2000. [5] P. Hoff. Multiplicative latent factor models for description and prediction of social networks. Computational and Mathematical Organization Theory, 2007. [6] T. Hofmann. Latent semantic models for collaborative ﬁltering. ACM Trans. Inf. Syst., 22(1):89–115, 2004. [7] C. Kemp, J. B. Tenenbaum, T. L. Grifﬁths, T. Yamada, and N. Ueda. Learning systems of concepts with an inﬁnite relational model. In Proceedings of the 21st National Conference on Artiﬁcial Intelligence (AAAI), 2006. [8] Y. J. Lim and Y. W. Teh. Variational Bayesian approach to movie rating prediction. In Proceedings of KDD Cup and Workshop, 2007. [9] J. S. Liu. Monte Carlo Strategies in Scientiﬁc Computing. Springer, 2001. [10] E. Meeds, Z. Ghahramani, R. Neal, and S. T. Roweis. Modeling dyadic data with binary latent factors. In Advances in Neural Information Processing Systems 19, 2007. [11] C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006. [12] J. D. M. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative prediction. In ICML, 2005. 7 [13] R. Salakhutdinov and A. Mnih. Bayeisna probabilistic matrix factorization using Markov chain Monte Carlo. In The 25th International Conference on Machine Learning, 2008. [14] Z. Xu, V. Tresp, K. Yu, and H.-P. Kriegel. Inﬁnite hidden relational models. In Proceedings of the 22nd International Conference on Uncertainty in Artiﬁcial Intelligence (UAI), 2006. [15] K. Yu, W. Chu, S. Yu, V. Tresp, and Z. Xu. Stochastic relational models for discriminative link prediction. In Advances in Neural Information Processing Systems 19 (NIPS), 2006. [16] S. Zhu, K. Yu, and Y. Gong. Predictive matrix-variate t models. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, NIPS ’07: Advances in Neural Information Processing Systems 20, pages 1721–1728. MIT Press, Cambridge, MA, 2008. Appendix Before presenting the algorithms, we introduce the necessary notation. Let Ii = {j|(i, j) ∈ I} and Ij = {i|(i, j) ∈ I}. A matrix with subscripts indicates its submatrix, which consists its entries at the given indices in the subscripts, for example, XIj ,j is a subvector of the j-th column of X whose row indices are in set Ij , X·,j is the j-th column of X (· indicates the full set). Xi,j denotes the (i, j)-th 2 entry of X. |X|2 is the squared sum of elements in set I, i.e. (i,j)∈I Xi,j . We ﬁll the unobserved I elements in Y with 0 for simplicity in notation Algorithm 1 BSRM/F: Gibbs sampling for SRM with features 1: Draw K ∼ IW d+p (δ + m, αI(d+p) + (F, F◦ ) (F, F◦ )); 2: For each i ∈ U0 , draw f i ∼ Nd (K(i) (s−2 G Y i,· + K−1 K12 K−1 f ◦ ), K(i) ), 11·2 22 i −1 where K(i) = s−2 (GIi ,· ) GIi ,· + K−1 ; 11·2 3: Draw R ∼ IW d+q (δ + n, βI(d+q) + (G, G◦ ) (G, G◦ )); 4: For each j ∈ V0 , draw gj ∼ Nd (R(j) (s−2 F Y ·,j + R−1 R12 R−1 g◦ ), R(j) ), 11·2 22 j −1 where R(j) = s−2 (FIj ,· ) FIj ,· + R−1 ; 11·2 5: Draw s2 ∼ χ−2 (ν + r, σ 2 + |Y − FG |2 ). I Algorithm 2 BSRM/F: Conditional Gibbs sampling for SRM with features 1: ∆i,j ← Yi,j − k Fi,k Gj,k , for (i, j) ∈ I; 2: Draw Φ ∼ Wd+p (δ + m + d + p − 1, (αI(d+p) + (F, F◦ ) (F, F◦ ))−1 ); 3: for each (i, k) ∈ U0 × {1, · · · , d} do 4: Draw f ∼ N1 (φ−1 (s−2 ∆i,Ii GIi ,k − Fi,· Φ·,k ), φ−1 ), where φ = s−2 (GIi ,k ) GIi ,k + Φk,k ; 5: Update Fi,k ← Fi,k + f , and ∆i,j ← ∆i,j − f Gj,k , for j ∈ Ii ; 6: end for 7: Draw Ψ ∼ Wd+q (δ + n + d + q − 1, (βI(d+q) + (G, G◦ ) (G, G◦ ))−1 ); 8: for each (j, k) ∈ V0 × {1, · · · , d} do 9: Draw g ∼ N1 (ψ −1 (s−2 ∆Ij ,j FIj ,k −Gj,· Ψ·,k ), ψ −1 ), where ψ = s−2 (FIj ,k ) FIj ,k +Ψk,k ; 10: Update Gj,k ← Gj,k + g and ∆i,j ← ∆i,j − gFi,k , for i ∈ Ij ; 11: end for 12: Draw s2 ∼ χ−2 (ν + r, σ 2 + |∆|2 ). I 8

4 0.075758599 197 nips-2008-Relative Performance Guarantees for Approximate Inference in Latent Dirichlet Allocation

Author: Indraneel Mukherjee, David M. Blei

Abstract: Hierarchical probabilistic modeling of discrete data has emerged as a powerful tool for text analysis. Posterior inference in such models is intractable, and practitioners rely on approximate posterior inference methods such as variational inference or Gibbs sampling. There has been much research in designing better approximations, but there is yet little theoretical understanding of which of the available techniques are appropriate, and in which data analysis settings. In this paper we provide the beginnings of such understanding. We analyze the improvement that the recently proposed collapsed variational inference (CVB) provides over mean ﬁeld variational inference (VB) in latent Dirichlet allocation. We prove that the difference in the tightness of the bound on the likelihood of a document decreases as O(k − 1) + log m/m, where k is the number of topics in the model and m is the number of words in a document. As a consequence, the advantage of CVB over VB is lost for long documents but increases with the number of topics. We demonstrate empirically that the theory holds, using simulated text data and two text corpora. We provide practical guidelines for choosing an approximation. 1

5 0.075693205 36 nips-2008-Beyond Novelty Detection: Incongruent Events, when General and Specific Classifiers Disagree

Author: Daphna Weinshall, Hynek Hermansky, Alon Zweig, Jie Luo, Holly Jimison, Frank Ohl, Misha Pavel

Abstract: Unexpected stimuli are a challenge to any machine learning algorithm. Here we identify distinct types of unexpected events, focusing on ’incongruent events’ when ’general level’ and ’speciﬁc level’ classiﬁers give conﬂicting predictions. We deﬁne a formal framework for the representation and processing of incongruent events: starting from the notion of label hierarchy, we show how partial order on labels can be deduced from such hierarchies. For each event, we compute its probability in different ways, based on adjacent levels (according to the partial order) in the label hierarchy. An incongruent event is an event where the probability computed based on some more speciﬁc level (in accordance with the partial order) is much smaller than the probability computed based on some more general level, leading to conﬂicting predictions. We derive algorithms to detect incongruent events from different types of hierarchies, corresponding to class membership or part membership. Respectively, we show promising results with real data on two speciﬁc problems: Out Of Vocabulary words in speech recognition, and the identiﬁcation of a new sub-class (e.g., the face of a new individual) in audio-visual facial object recognition.

6 0.06986443 248 nips-2008-Using matrices to model symbolic relationship

7 0.06928768 77 nips-2008-Evaluating probabilities under high-dimensional latent variable models

8 0.061160795 216 nips-2008-Sparse probabilistic projections

9 0.061133415 127 nips-2008-Logistic Normal Priors for Unsupervised Probabilistic Grammar Induction

10 0.060253665 135 nips-2008-Model Selection in Gaussian Graphical Models: High-Dimensional Consistency of \boldmath$\ell 1$-regularized MLE

11 0.058757715 229 nips-2008-Syntactic Topic Models

12 0.054562043 26 nips-2008-Analyzing human feature learning as nonparametric Bayesian inference

13 0.052845486 236 nips-2008-The Mondrian Process

14 0.051695284 183 nips-2008-Predicting the Geometry of Metal Binding Sites from Protein Sequence

15 0.051374197 172 nips-2008-Optimal Response Initiation: Why Recent Experience Matters

16 0.049370367 249 nips-2008-Variational Mixture of Gaussian Process Experts

17 0.047425613 129 nips-2008-MAS: a multiplicative approximation scheme for probabilistic inference

18 0.047001611 152 nips-2008-Non-stationary dynamic Bayesian networks

19 0.04644819 231 nips-2008-Temporal Dynamics of Cognitive Control

20 0.046190247 224 nips-2008-Structured ranking learning using cumulative distribution networks

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.154), (1, -0.025), (2, 0.069), (3, -0.004), (4, 0.045), (5, -0.08), (6, 0.025), (7, 0.099), (8, -0.03), (9, -0.01), (10, -0.064), (11, 0.014), (12, 0.015), (13, 0.032), (14, -0.001), (15, 0.063), (16, 0.032), (17, -0.06), (18, 0.002), (19, 0.035), (20, -0.02), (21, -0.017), (22, 0.052), (23, 0.01), (24, -0.008), (25, -0.062), (26, -0.127), (27, 0.045), (28, 0.02), (29, 0.013), (30, -0.028), (31, 0.004), (32, -0.032), (33, -0.026), (34, 0.019), (35, 0.147), (36, 0.035), (37, 0.101), (38, 0.016), (39, -0.034), (40, 0.044), (41, 0.023), (42, -0.074), (43, -0.137), (44, -0.076), (45, 0.093), (46, -0.035), (47, 0.012), (48, -0.029), (49, -0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.92945611 134 nips-2008-Mixed Membership Stochastic Blockmodels

Author: Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, Eric P. Xing

2 0.6408062 221 nips-2008-Stochastic Relational Models for Large-scale Dyadic Data using MCMC

Author: Shenghuo Zhu, Kai Yu, Yihong Gong

3 0.6104883 236 nips-2008-The Mondrian Process

Author: Daniel M. Roy, Yee W. Teh

Abstract: We describe a novel class of distributions, called Mondrian processes, which can be interpreted as probability distributions over kd-tree data structures. Mondrian processes are multidimensional generalizations of Poisson processes and this connection allows us to construct multidimensional generalizations of the stickbreaking process described by Sethuraman (1994), recovering the Dirichlet process in one dimension. After introducing the Aldous-Hoover representation for jointly and separately exchangeable arrays, we show how the process can be used as a nonparametric prior distribution in Bayesian models of relational data. 1

4 0.59890002 248 nips-2008-Using matrices to model symbolic relationship

Author: Ilya Sutskever, Geoffrey E. Hinton

Abstract: We describe a way of learning matrix representations of objects and relationships. The goal of learning is to allow multiplication of matrices to represent symbolic relationships between objects and symbolic relationships between relationships, which is the main novelty of the method. We demonstrate that this leads to excellent generalization in two different domains: modular arithmetic and family relationships. We show that the same system can learn ﬁrst-order propositions such as (2, 5) ∈ +3 or (Christopher, Penelope) ∈ has wife, and higher-order propositions such as (3, +3) ∈ plus and (+3, −3) ∈ inverse or (has husband, has wife) ∈ higher oppsex. We further demonstrate that the system understands how higher-order propositions are related to ﬁrst-order ones by showing that it can correctly answer questions about ﬁrst-order propositions involving the relations +3 or has wife even though it has not been trained on any ﬁrst-order examples involving these relations. 1

5 0.49921867 225 nips-2008-Supervised Bipartite Graph Inference

Author: Yoshihiro Yamanishi

6 0.49140859 77 nips-2008-Evaluating probabilities under high-dimensional latent variable models

7 0.47627097 197 nips-2008-Relative Performance Guarantees for Approximate Inference in Latent Dirichlet Allocation

8 0.47261807 234 nips-2008-The Infinite Factorial Hidden Markov Model

9 0.46829554 233 nips-2008-The Gaussian Process Density Sampler

10 0.43327117 216 nips-2008-Sparse probabilistic projections

11 0.43013781 70 nips-2008-Efficient Inference in Phylogenetic InDel Trees

12 0.4210937 10 nips-2008-A rational model of preference learning and choice prediction by children

13 0.41740361 26 nips-2008-Analyzing human feature learning as nonparametric Bayesian inference

14 0.41128969 152 nips-2008-Non-stationary dynamic Bayesian networks

15 0.40574384 31 nips-2008-Bayesian Exponential Family PCA

16 0.40357971 183 nips-2008-Predicting the Geometry of Metal Binding Sites from Protein Sequence

17 0.4006125 82 nips-2008-Fast Computation of Posterior Mode in Multi-Level Hierarchical Models

18 0.40039119 154 nips-2008-Nonparametric Bayesian Learning of Switching Linear Dynamical Systems

19 0.39643103 64 nips-2008-DiscLDA: Discriminative Learning for Dimensionality Reduction and Classification

20 0.39312989 224 nips-2008-Structured ranking learning using cumulative distribution networks

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(6, 0.034), (7, 0.057), (12, 0.021), (14, 0.058), (15, 0.016), (21, 0.217), (27, 0.011), (28, 0.175), (57, 0.106), (59, 0.038), (63, 0.04), (71, 0.022), (77, 0.028), (78, 0.017), (83, 0.076)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.90656698 46 nips-2008-Characterizing response behavior in multisensory perception with conflicting cues

Author: Rama Natarajan, Iain Murray, Ladan Shams, Richard S. Zemel

Abstract: We explore a recently proposed mixture model approach to understanding interactions between conﬂicting sensory cues. Alternative model formulations, differing in their sensory noise models and inference methods, are compared based on their ﬁt to experimental data. Heavy-tailed sensory likelihoods yield a better description of the subjects’ response behavior than standard Gaussian noise models. We study the underlying cause for this result, and then present several testable predictions of these models. 1

2 0.88925499 13 nips-2008-Adapting to a Market Shock: Optimal Sequential Market-Making

Author: Sanmay Das, Malik Magdon-Ismail

Abstract: We study the proﬁt-maximization problem of a monopolistic market-maker who sets two-sided prices in an asset market. The sequential decision problem is hard to solve because the state space is a function. We demonstrate that the belief state is well approximated by a Gaussian distribution. We prove a key monotonicity property of the Gaussian state update which makes the problem tractable, yielding the ﬁrst optimal sequential market-making algorithm in an established model. The algorithm leads to a surprising insight: an optimal monopolist can provide more liquidity than perfectly competitive market-makers in periods of extreme uncertainty, because a monopolist is willing to absorb initial losses in order to learn a new valuation rapidly so she can extract higher proﬁts later. 1

same-paper 3 0.84691215 134 nips-2008-Mixed Membership Stochastic Blockmodels

Author: Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, Eric P. Xing

4 0.84418094 153 nips-2008-Nonlinear causal discovery with additive noise models

Author: Patrik O. Hoyer, Dominik Janzing, Joris M. Mooij, Jan R. Peters, Bernhard Schölkopf

Abstract: The discovery of causal relationships between a set of observed variables is a fundamental problem in science. For continuous-valued data linear acyclic causal models with additive noise are often used because these models are well understood and there are well-known methods to ﬁt them to data. In reality, of course, many causal relationships are more or less nonlinear, raising some doubts as to the applicability and usefulness of purely linear methods. In this contribution we show that the basic linear framework can be generalized to nonlinear models. In this extended framework, nonlinearities in the data-generating process are in fact a blessing rather than a curse, as they typically provide information on the underlying causal system and allow more aspects of the true data-generating mechanisms to be identiﬁed. In addition to theoretical results we show simulations and some simple real data experiments illustrating the identiﬁcation power provided by nonlinearities. 1

5 0.71089613 48 nips-2008-Clustering via LP-based Stabilities

Author: Nikos Komodakis, Nikos Paragios, Georgios Tziritas

Abstract: A novel center-based clustering algorithm is proposed in this paper. We ﬁrst formulate clustering as an NP-hard linear integer program and we then use linear programming and the duality theory to derive the solution of this optimization problem. This leads to an efﬁcient and very general algorithm, which works in the dual domain, and can cluster data based on an arbitrary set of distances. Despite its generality, it is independent of initialization (unlike EM-like methods such as K-means), has guaranteed convergence, can automatically determine the number of clusters, and can also provide online optimality bounds about the quality of the estimated clustering solutions. To deal with the most critical issue in a centerbased clustering algorithm (selection of cluster centers), we also introduce the notion of stability of a cluster center, which is a well deﬁned LP-based quantity that plays a key role to our algorithm’s success. Furthermore, we also introduce, what we call, the margins (another key ingredient in our algorithm), which can be roughly thought of as dual counterparts to stabilities and allow us to obtain computationally efﬁcient approximations to the latter. Promising experimental results demonstrate the potentials of our method.

6 0.70706934 116 nips-2008-Learning Hybrid Models for Image Annotation with Partially Labeled Data

7 0.7013039 176 nips-2008-Partially Observed Maximum Entropy Discrimination Markov Networks

8 0.6978662 26 nips-2008-Analyzing human feature learning as nonparametric Bayesian inference

9 0.69227892 197 nips-2008-Relative Performance Guarantees for Approximate Inference in Latent Dirichlet Allocation

10 0.68943024 63 nips-2008-Dimensionality Reduction for Data in Multiple Feature Representations

11 0.68878269 208 nips-2008-Shared Segmentation of Natural Scenes Using Dependent Pitman-Yor Processes

12 0.68781883 235 nips-2008-The Infinite Hierarchical Factor Regression Model

13 0.68703043 95 nips-2008-Grouping Contours Via a Related Image

14 0.68692797 62 nips-2008-Differentiable Sparse Coding

15 0.68642426 92 nips-2008-Generative versus discriminative training of RBMs for classification of fMRI images

16 0.68532401 66 nips-2008-Dynamic visual attention: searching for coding length increments

17 0.68451536 100 nips-2008-How memory biases affect information transmission: A rational analysis of serial reproduction

18 0.68438959 200 nips-2008-Robust Kernel Principal Component Analysis

19 0.68417376 231 nips-2008-Temporal Dynamics of Cognitive Control

20 0.68393409 138 nips-2008-Modeling human function learning with Gaussian processes