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

9 nips-2009-A Game-Theoretic Approach to Hypergraph Clustering

Source: pdf

Author: Samuel R. Bulò, Marcello Pelillo

Abstract: Hypergraph clustering refers to the process of extracting maximally coherent groups from a set of objects using high-order (rather than pairwise) similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a user-deﬁned number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this paper, we provide a radically different perspective to the problem. In contrast to the classical approach, we attempt to provide a meaningful formalization of the very notion of a cluster and we show that game theory offers an attractive and unexplored perspective that serves well our purpose. Speciﬁcally, we show that the hypergraph clustering problem can be naturally cast into a non-cooperative multi-player “clustering game”, whereby the notion of a cluster is equivalent to a classical game-theoretic equilibrium concept. From the computational viewpoint, we show that the problem of ﬁnding the equilibria of our clustering game is equivalent to locally optimizing a polynomial function over the standard simplex, and we provide a discrete-time dynamics to perform this optimization. Experiments are presented which show the superiority of our approach over state-of-the-art hypergraph clustering techniques.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 it Abstract Hypergraph clustering refers to the process of extracting maximally coherent groups from a set of objects using high-order (rather than pairwise) similarities. [sent-3, score-0.378]

2 Traditional approaches to this problem are based on the idea of partitioning the input data into a user-deﬁned number of classes, thereby obtaining the clusters as a by-product of the partitioning process. [sent-4, score-0.21]

3 In contrast to the classical approach, we attempt to provide a meaningful formalization of the very notion of a cluster and we show that game theory offers an attractive and unexplored perspective that serves well our purpose. [sent-6, score-0.517]

4 Speciﬁcally, we show that the hypergraph clustering problem can be naturally cast into a non-cooperative multi-player “clustering game”, whereby the notion of a cluster is equivalent to a classical game-theoretic equilibrium concept. [sent-7, score-1.053]

5 From the computational viewpoint, we show that the problem of ﬁnding the equilibria of our clustering game is equivalent to locally optimizing a polynomial function over the standard simplex, and we provide a discrete-time dynamics to perform this optimization. [sent-8, score-0.623]

6 Experiments are presented which show the superiority of our approach over state-of-the-art hypergraph clustering techniques. [sent-9, score-0.727]

7 1 Introduction Clustering is the problem of organizing a set of objects into groups, or clusters, in a way as to have similar objects grouped together and dissimilar ones assigned to different groups, according to some similarity measure. [sent-10, score-0.214]

8 Objects similarities are typically expressed as pairwise relations, but in some applications higherorder relations are more appropriate, and approximating them in terms of pairwise interactions can lead to substantial loss of information. [sent-12, score-0.201]

9 Consider for instance the problem of clustering a given set of d-dimensional Euclidean points into lines. [sent-13, score-0.299]

10 The problem of clustering objects using high-order similarities is usually referred to as the hypergraph clustering problem. [sent-17, score-1.073]

11 Both approaches transform the similarity hypergraph into an edge-weighted graph, whose edge-weights are a function of the hypergraph’s original weights. [sent-20, score-0.504]

12 This way they are able to tackle 1 the problem with standard pairwise clustering algorithms. [sent-21, score-0.343]

13 Bolla [6] deﬁnes a Laplacian matrix for an unweighted hypergraph and establishes a link between the spectral properties of this matrix and the hypergraph’s minimum cut. [sent-22, score-0.448]

14 Zhou and co-authors [23] generalize their earlier work on regularization on graphs and deﬁne a hypergraph normalized cut criterion for a k-partition of the vertices, which can be achieved by ﬁnding the second smallest eigenvector of a normalized Laplacian. [sent-24, score-0.421]

15 This approach generalizes the well-known “Normalized cut” pairwise clustering algorithm [19]. [sent-25, score-0.343]

16 It is worth noting that the approaches mentioned above are devised for dealing with higher-order relations, but can all be reduced to standard pairwise clustering approaches [1]. [sent-27, score-0.447]

17 A different formulation is introduced in [18], where the clustering problem with higher-order (super-symmetric) similarities is cast into a nonnegative factorization of the closest hyper-stochastic version of the input afﬁnity tensor. [sent-28, score-0.338]

18 All the afore-mentioned approaches to hypergraph clustering are partition-based. [sent-29, score-0.716]

19 This renders these approaches vulnerable to applications where the number of classes is not known in advance, or where data is affected by clutter elements which do not belong to any cluster (as in ﬁgure/ground separation problems). [sent-31, score-0.192]

20 In this paper, following [14, 20] we offer a radically different perspective to the hypergraph clustering problem. [sent-35, score-0.74]

21 Instead of insisting on the idea of determining a partition of the input data, and hence obtaining the clusters as a by-product of the partitioning process, we reverse the terms of the problem and attempt instead to derive a rigorous formulation of the very notion of a cluster. [sent-36, score-0.172]

22 This allows one, in principle, to deal with more general problems where clusters may overlap and/or outliers may get unassigned. [sent-37, score-0.223]

23 We found that game theory offers a very elegant and general mathematical framework that serves well our purposes. [sent-38, score-0.228]

24 The basic idea behind our approach is that the hypergraph clustering problem can be considered as a multi-player non-cooperative “clustering game”. [sent-39, score-0.693]

25 Within this context, the notion of a cluster turns out to be equivalent to a classical equilibrium concept from (evolutionary) game theory, as the latter reﬂects both the internal and external cluster conditions alluded to before. [sent-40, score-0.88]

26 Experiments on two standard hypergraph clustering problems show the superiority of the proposed approach over state-of-the-art hypergraph clustering techniques. [sent-42, score-1.42]

27 2 Basic notions from evolutionary game theory Evolutionary game theory studies models of strategic interactions (called games) among large numbers of anonymous agents. [sent-43, score-0.654]

28 A game can be formalized as a triplet Γ = (P, S, π), where P = {1, . [sent-44, score-0.251]

29 , n} is the set of pure strategies (in the terminology of game-theory) available to each player and π : S k → R is the payoff function, which assigns a payoff to each strategy proﬁle, i. [sent-50, score-0.484]

30 The payoff function π is assumed to be invariant to permutations of the strategy proﬁle. [sent-53, score-0.204]

31 It is worth noting that in general games, each player may have its own set of strategies and own payoff function. [sent-54, score-0.315]

32 For a comprehensive introduction to evolutionary game theory we refer to [22]. [sent-55, score-0.398]

33 By undertaking an evolutionary setting we assume to have a large population of non-rational agents, which are randomly matched to play a game Γ = (P, S, π). [sent-56, score-0.571]

34 Evolution in the population takes place, because we assume that there exists a selection mechanism, which, by analogy with a Darwinian process, spreads the ﬁttest strategies in the population to the detriment of the weakest one, which will in turn be driven to extinction. [sent-59, score-0.403]

35 2 The state of the population at a given time t can be represented as a n-dimensional vector x(t), where xi (t) represents the fraction of i-strategists in the population at time t. [sent-61, score-0.373]

36 The set of all possible states describing a population is given by ∆= x ∈ Rn : xi = 1 and xi ≥ 0 for all i ∈ S , i∈S which is called standard simplex. [sent-62, score-0.227]

37 In the sequel we will drop the time reference from the population state, where not necessary. [sent-63, score-0.198]

38 , the set of strategies still alive in population x ∈ ∆: σ(x) = {i ∈ S : xi > 0}. [sent-66, score-0.257]

39 If y(i) ∈ ∆ is the probability distribution identifying which strategy the ith player will adopt if drawn to play the game Γ, then the average payoff obtained by the agents can be computed as k u(y(1) , . [sent-67, score-0.625]

40 Assuming that the agents are randomly and independently drawn from a population x ∈ ∆ to play the game Γ, the population average payoff is given by u(xk ), where xk is a shortcut for x, . [sent-78, score-1.019]

41 Furthermore, the average payoff that an i-strategist obtains in a population x ∈ ∆ is given by u(ei , xk−1 ), where ei ∈ ∆ is a vector with xi = 1 and zero elsewhere. [sent-82, score-0.492]

42 An important notion in game theory is that of equilibrium [22]. [sent-83, score-0.361]

43 A population x ∈ ∆ is in equilibrium when the distribution of strategies will not change anymore, which intuitively happens when every individual in the population obtains the same average payoff and no strategy can thus prevail on the other ones. [sent-84, score-0.767]

44 (2) In other words, every agent in the population performs at most as well as the population average payoff. [sent-86, score-0.449]

45 , all the agents that survived the evolution obtain the same average payoff, which coincides with the population average payoff. [sent-89, score-0.429]

46 A key concept pertaining to evolutionary game theory is that of an evolutionary stable strategy [7, 22]. [sent-90, score-0.608]

47 Such a strategy is robust to evolutionary pressure in an exact sense. [sent-91, score-0.21]

48 Assume that in a population x ∈ ∆, a small share ǫ of mutant agents appears, whose distribution of strategies is y ∈ ∆. [sent-92, score-0.386]

49 The resulting postentry population is given by wǫ = (1 − ǫ)x + ǫy. [sent-93, score-0.21]

50 Biological intuition suggests that evolutionary forces select against mutant individuals if and only if the average payoff of a mutant agent in the postentry population is lower than that of an individual from the original population, i. [sent-94, score-0.818]

51 (4) A population x ∈ ∆ is evolutionary stable (or an ESS) if inequality (4) holds for any distribution of mutant agents y ∈ ∆ \ {x}, granted the population share of mutants ǫ is sufﬁciently small (see, [22] for pairwise contests and [7] for n-wise contests). [sent-97, score-0.78]

52 An alternative, but equivalent, characterization of ESSs involves a leveled notion of evolutionary stable strategies [7]. [sent-98, score-0.266]

53 3 3 The hypergraph clustering game The hypergraph clustering problem can be described by an edge-weighted hypergraph. [sent-111, score-1.614]

54 Formally, an edge-weighted hypergraph is a triplet H = (V, E, s), where V = {1, . [sent-112, score-0.444]

55 In this paper, we cast the hypergraph clustering problem into a game, called (hypergraph) clustering game, which will be played in an evolutionary setting. [sent-118, score-1.214]

56 Clusters are then derived from the analysis of the ESSs of the clustering game. [sent-119, score-0.272]

57 Speciﬁcally, given a k-graph H = (V, E, s) modeling a hypergraph clustering problem, where V = {1, . [sent-120, score-0.693]

58 , n} is the set of objects to cluster and s is the similarity function over the set of objects in E, we can build a game involving k players, each of them having the same set of (pure) strategies, namely the set of objects to cluster V . [sent-123, score-0.857]

59 Under this setting, a population x ∈ ∆ of agents playing a clustering game represents in fact a cluster, where xi is the probability for object i to be part of it. [sent-124, score-0.854]

60 Indeed, any cluster can be modeled as a probability distribution over the set of objects to cluster. [sent-125, score-0.246]

61 The payoff function of the clustering game is deﬁned in a way as to favour the evolution of agents supporting highly coherent objects. [sent-126, score-0.817]

62 Intuitively, this is accomplished by rewarding the k players in proportion to the similarity that the k played objects have. [sent-127, score-0.228]

63 , vk ) ∈ V k to be the tuple of objects selected by k players, the payoff function can be simply deﬁned as 1 s ({v1 , . [sent-131, score-0.282]

64 An ESS of a clustering game incorporates the properties of internal coherency and external incoherency of a cluster: internal coherency: since ESSs are Nash equilibria, from (3), it follows that every object contributing to the cluster, i. [sent-144, score-0.932]

65 , every object in σ(x), has the same average similarity with respect to the cluster, which in turn corresponds to the cluster’s overall average similarity. [sent-146, score-0.232]

66 Hence, the cluster is internally coherent; external incoherency: from (2), every object external to the cluster, i. [sent-147, score-0.393]

67 , every object in V \ σ(x), has an average similarity which does not exceed the cluster’s overall average similarity. [sent-149, score-0.232]

68 There may still be cases where the average similarity of an external object is the same as that of an internal object, mining the cluster’s external incoherency. [sent-150, score-0.416]

69 However, since x is an ESS, from (7) we see that whenever we try to extend a cluster with small shares of external objects, the cluster’s overall average similarity drops. [sent-151, score-0.387]

70 This guarantees the external incoherency property of a cluster to be also satisﬁed. [sent-152, score-0.336]

71 Finally, it is worth noting that this theory generalizes the dominant-sets clustering framework which has recently been introduced in [14]. [sent-153, score-0.33]

72 clustering games deﬁned on graphs, correspond to the dominant-set clusters [20, 17]. [sent-156, score-0.384]

73 4 Evolution towards a cluster In this section we will show that the ESSs of a clustering game are in one-to-one correspondence with (strict) local solution of a non-linear optimization program. [sent-158, score-0.669]

74 Let H = (V, E, s) be a hypergraph clustering problem and Γ = (P, V, π) be the corresponding clustering game. [sent-160, score-0.965]

75 The problem of extracting ESSs of our hypergraph clustering game can thus be cast into the problem of ﬁnding strict local solutions of (9). [sent-167, score-0.994]

76 Since f (x) is a homogeneous polynomial in the variables xi , we can use the transformation of Theorem 1 in order to ﬁnd a local solution x ∈ ∆ of (9), which in turn provides us with an ESS of the hypergraph clustering game. [sent-179, score-0.759]

77 The complexity of ﬁnding a cluster is thus O(ρ|E|), where |E| is the number of edges of the hypergraph describing the clustering problem and ρ is the average number of iteration needed to converge. [sent-181, score-0.928]

78 In order to obtain the clustering, in principle, we have to ﬁnd the ESSs of the clustering game. [sent-183, score-0.272]

79 By now, we adopt a naive peeling-off strategy for our cluster extraction procedure. [sent-185, score-0.209]

80 Namely, we iteratively ﬁnd a cluster and remove it from the set of objects, and we repeat this process on the remaining objects until a desired number of clusters have been extracted. [sent-186, score-0.325]

81 We also compare against Super-symmetric Non-negative Tensor Factorization (S NTF) [18], because it is the only approach, other than ours, which does not approximate the hypergraph to a graph. [sent-193, score-0.421]

82 Figure 1: Results on clustering 3, 4 and 5 lines perturbed with increasing levels of Gaussian noise (σ = 0, 0. [sent-245, score-0.395]

83 Moreover, we evaluated the quality of a clustering by computing the average F-measure of each cluster in the ground-truth with the most compatible one in the obtained solution (according to a one-to-one correspondence). [sent-251, score-0.507]

84 1 Line clustering We consider the problem of clustering lines in spaces of dimension greater than two, i. [sent-253, score-0.596]

85 A ﬁrst experiment consists in clustering 3, 4 and 5 lines generated in the 5-dimensional space [−2, 2]5 . [sent-261, score-0.324]

86 With this setting there are no outliers and every point should be assigned to a line (e. [sent-267, score-0.179]

87 This is due to the fact that points deviating too much from the overall cluster average collinearity will be excluded as they undermine the cluster’s internal coherency. [sent-275, score-0.328]

88 Figure 2: Results on clustering 2, 3 and 4 lines with an increasing number of outliers (0, 10, 20, 40). [sent-313, score-0.468]

89 The second experiment consists in clustering 2, 3 and 4 slightly perturbed lines (with ﬁxed local noise σ = 0. [sent-316, score-0.395]

90 Indeed, our method is not inﬂuenced by outliers and therefore it performs almost perfectly, whereas C AVERAGE and S NTF perform well only without outliers and with the optimal K. [sent-326, score-0.288]

91 However, since outliers are not mutually similar and intuitively they do not form a cluster, we have that the performance of C AVERAGE and S NTF drop drastically as the number of outliers increases. [sent-329, score-0.313]

92 2 Illuminant-invariant face clustering In [5] it has been shown that images of a Lambertian object illuminated by a point light source lie in a three dimensional subspace. [sent-332, score-0.365]

93 We use this dissimilarity measure for the face clustering problem and we consider as dataset the Yale Face Database B and its extended version [8, 12]. [sent-334, score-0.369]

94 The case with outliers consists in 10 additional faces each from a different individual. [sent-338, score-0.171]

95 The results are consistent with those obtained in the case of line clustering with the exception of S NTF, which performs worse than the other approaches on this real-world application. [sent-401, score-0.33]

96 C AVERAGE and our algorithm perform comparably well when clustering 4 individuals without outliers. [sent-402, score-0.313]

97 In both the experiments of line and face clustering the execution times of our approach were higher than those of C AVERAGE, but considerably lower than S NTF. [sent-407, score-0.36]

98 The main reason why C AVERAGE run faster is that our approach and S NTF work directly on the hypergraph without resorting to pairwise relations, which is indeed what C AVERAGE does. [sent-408, score-0.523]

99 6 Discussion In this paper, we offered a game-theoretic perspective to the hypergraph clustering problem. [sent-410, score-0.717]

100 Within our framework the clustering problem is viewed as a multi-player non-cooperative game, and classical equilibrium notions from evolutionary game theory turn out to provide a natural formalization of the notion of a cluster. [sent-411, score-0.888]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('hypergraph', 0.421), ('ntf', 0.317), ('sntf', 0.317), ('clustering', 0.272), ('esss', 0.261), ('game', 0.228), ('population', 0.173), ('evolutionary', 0.17), ('cluster', 0.169), ('payoff', 0.164), ('outliers', 0.144), ('ess', 0.139), ('hoclugame', 0.131), ('xk', 0.124), ('equilibrium', 0.094), ('coherency', 0.093), ('external', 0.092), ('agents', 0.091), ('clusters', 0.079), ('objects', 0.077), ('bul', 0.075), ('incoherency', 0.075), ('rota', 0.075), ('pairwise', 0.071), ('internal', 0.066), ('average', 0.066), ('baum', 0.065), ('mutant', 0.065), ('ei', 0.062), ('similarity', 0.06), ('strategies', 0.057), ('hypergraphs', 0.056), ('partitioning', 0.054), ('face', 0.053), ('nash', 0.053), ('lines', 0.052), ('equilibria', 0.049), ('players', 0.047), ('dissimilarity', 0.044), ('played', 0.044), ('clique', 0.042), ('individuals', 0.041), ('perturbed', 0.041), ('vk', 0.041), ('strategy', 0.04), ('object', 0.04), ('polynomial', 0.039), ('notion', 0.039), ('strict', 0.038), ('agent', 0.037), ('contests', 0.037), ('eagon', 0.037), ('postentry', 0.037), ('torsello', 0.037), ('venice', 0.037), ('vlsi', 0.037), ('player', 0.036), ('cast', 0.035), ('line', 0.035), ('dynamics', 0.035), ('superiority', 0.034), ('formalization', 0.034), ('evolution', 0.033), ('games', 0.033), ('belhumeur', 0.033), ('gibson', 0.033), ('multilevel', 0.033), ('rodr', 0.033), ('zass', 0.033), ('agarwal', 0.032), ('similarities', 0.031), ('indeed', 0.031), ('overlapping', 0.03), ('noise', 0.03), ('noting', 0.029), ('worth', 0.029), ('coherent', 0.029), ('relations', 0.028), ('notions', 0.028), ('kkt', 0.028), ('expansion', 0.028), ('xi', 0.027), ('spectral', 0.027), ('faces', 0.027), ('points', 0.027), ('drop', 0.025), ('maximizer', 0.025), ('triplets', 0.025), ('perspective', 0.024), ('illumination', 0.023), ('radically', 0.023), ('approaches', 0.023), ('pure', 0.023), ('classical', 0.023), ('lighting', 0.023), ('triplet', 0.023), ('hu', 0.023), ('playing', 0.023), ('robustness', 0.022), ('tensor', 0.022)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999988 9 nips-2009-A Game-Theoretic Approach to Hypergraph Clustering

Author: Samuel R. Bulò, Marcello Pelillo

2 0.14536609 221 nips-2009-Solving Stochastic Games

Author: Liam M. Dermed, Charles L. Isbell

Abstract: Solving multi-agent reinforcement learning problems has proven difﬁcult because of the lack of tractable algorithms. We provide the ﬁrst approximation algorithm which solves stochastic games with cheap-talk to within absolute error of the optimal game-theoretic solution, in time polynomial in 1/ . Our algorithm extends Murray’s and Gordon’s (2007) modiﬁed Bellman equation which determines the set of all possible achievable utilities; this provides us a truly general framework for multi-agent learning. Further, we empirically validate our algorithm and ﬁnd the computational cost to be orders of magnitude less than what the theory predicts. 1

3 0.13178295 232 nips-2009-Strategy Grafting in Extensive Games

Author: Kevin Waugh, Nolan Bard, Michael Bowling

Abstract: Extensive games are often used to model the interactions of multiple agents within an environment. Much recent work has focused on increasing the size of an extensive game that can be feasibly solved. Despite these improvements, many interesting games are still too large for such techniques. A common approach for computing strategies in these large games is to ﬁrst employ an abstraction technique to reduce the original game to an abstract game that is of a manageable size. This abstract game is then solved and the resulting strategy is played in the original game. Most top programs in recent AAAI Computer Poker Competitions use this approach. The trend in this competition has been that strategies found in larger abstract games tend to beat strategies found in smaller abstract games. These larger abstract games have more expressive strategy spaces and therefore contain better strategies. In this paper we present a new method for computing strategies in large games. This method allows us to compute more expressive strategies without increasing the size of abstract games that we are required to solve. We demonstrate the power of the approach experimentally in both small and large games, while also providing a theoretical justiﬁcation for the resulting improvement. 1

4 0.12139 161 nips-2009-Nash Equilibria of Static Prediction Games

Author: Michael Brückner, Tobias Scheffer

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

5 0.088627093 156 nips-2009-Monte Carlo Sampling for Regret Minimization in Extensive Games

Author: Marc Lanctot, Kevin Waugh, Martin Zinkevich, Michael Bowling

Abstract: Sequential decision-making with multiple agents and imperfect information is commonly modeled as an extensive game. One efﬁcient method for computing Nash equilibria in large, zero-sum, imperfect information games is counterfactual regret minimization (CFR). In the domain of poker, CFR has proven effective, particularly when using a domain-speciﬁc augmentation involving chance outcome sampling. In this paper, we describe a general family of domain-independent CFR sample-based algorithms called Monte Carlo counterfactual regret minimization (MCCFR) of which the original and poker-speciﬁc versions are special cases. We start by showing that MCCFR performs the same regret updates as CFR on expectation. Then, we introduce two sampling schemes: outcome sampling and external sampling, showing that both have bounded overall regret with high probability. Thus, they can compute an approximate equilibrium using self-play. Finally, we prove a new tighter bound on the regret for the original CFR algorithm and relate this new bound to MCCFR’s bounds. We show empirically that, although the sample-based algorithms require more iterations, their lower cost per iteration can lead to dramatically faster convergence in various games. 1

6 0.086623393 234 nips-2009-Streaming k-means approximation

7 0.086475566 163 nips-2009-Neurometric function analysis of population codes

8 0.08032345 252 nips-2009-Unsupervised Feature Selection for the $k$-means Clustering Problem

9 0.079867586 102 nips-2009-Graph-based Consensus Maximization among Multiple Supervised and Unsupervised Models

10 0.074821383 122 nips-2009-Label Selection on Graphs

11 0.071383536 18 nips-2009-A Stochastic approximation method for inference in probabilistic graphical models

12 0.069511689 53 nips-2009-Complexity of Decentralized Control: Special Cases

13 0.067536354 107 nips-2009-Help or Hinder: Bayesian Models of Social Goal Inference

14 0.066731833 155 nips-2009-Modelling Relational Data using Bayesian Clustered Tensor Factorization

15 0.064202927 182 nips-2009-Optimal Scoring for Unsupervised Learning

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

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

18 0.055785775 211 nips-2009-Segmenting Scenes by Matching Image Composites

19 0.052631181 126 nips-2009-Learning Bregman Distance Functions and Its Application for Semi-Supervised Clustering

20 0.05083951 40 nips-2009-Bayesian Nonparametric Models on Decomposable Graphs

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.162), (1, 0.001), (2, 0.046), (3, -0.063), (4, -0.111), (5, 0.015), (6, -0.051), (7, 0.01), (8, 0.071), (9, 0.006), (10, -0.155), (11, -0.194), (12, -0.008), (13, -0.132), (14, -0.048), (15, -0.164), (16, -0.025), (17, -0.061), (18, -0.03), (19, -0.019), (20, -0.049), (21, 0.093), (22, -0.041), (23, -0.012), (24, 0.118), (25, -0.028), (26, 0.01), (27, -0.035), (28, -0.09), (29, -0.008), (30, 0.185), (31, -0.032), (32, -0.045), (33, 0.037), (34, 0.158), (35, -0.007), (36, 0.05), (37, 0.027), (38, 0.026), (39, -0.002), (40, -0.02), (41, 0.029), (42, 0.025), (43, 0.025), (44, 0.038), (45, -0.077), (46, 0.076), (47, 0.002), (48, 0.074), (49, -0.04)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95060474 9 nips-2009-A Game-Theoretic Approach to Hypergraph Clustering

Author: Samuel R. Bulò, Marcello Pelillo

2 0.66038084 232 nips-2009-Strategy Grafting in Extensive Games

Author: Kevin Waugh, Nolan Bard, Michael Bowling

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

Author: Michael Brückner, Tobias Scheffer

4 0.59624368 221 nips-2009-Solving Stochastic Games

Author: Liam M. Dermed, Charles L. Isbell

5 0.52775478 234 nips-2009-Streaming k-means approximation

Author: Nir Ailon, Ragesh Jaiswal, Claire Monteleoni

Abstract: We provide a clustering algorithm that approximately optimizes the k-means objective, in the one-pass streaming setting. We make no assumptions about the data, and our algorithm is very light-weight in terms of memory, and computation. This setting is applicable to unsupervised learning on massive data sets, or resource-constrained devices. The two main ingredients of our theoretical work are: a derivation of an extremely simple pseudo-approximation batch algorithm for k-means (based on the recent k-means++), in which the algorithm is allowed to output more than k centers, and a streaming clustering algorithm in which batch clustering algorithms are performed on small inputs (ﬁtting in memory) and combined in a hierarchical manner. Empirical evaluations on real and simulated data reveal the practical utility of our method. 1

6 0.5160898 156 nips-2009-Monte Carlo Sampling for Regret Minimization in Extensive Games

7 0.49263802 252 nips-2009-Unsupervised Feature Selection for the $k$-means Clustering Problem

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

9 0.40791512 102 nips-2009-Graph-based Consensus Maximization among Multiple Supervised and Unsupervised Models

10 0.39564872 51 nips-2009-Clustering sequence sets for motif discovery

11 0.3364104 163 nips-2009-Neurometric function analysis of population codes

12 0.3311547 40 nips-2009-Bayesian Nonparametric Models on Decomposable Graphs

13 0.32734931 244 nips-2009-The Wisdom of Crowds in the Recollection of Order Information

14 0.29891905 226 nips-2009-Spatial Normalized Gamma Processes

15 0.2903451 122 nips-2009-Label Selection on Graphs

16 0.28754696 243 nips-2009-The Ordered Residual Kernel for Robust Motion Subspace Clustering

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

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

19 0.28409877 48 nips-2009-Bootstrapping from Game Tree Search

20 0.2816242 53 nips-2009-Complexity of Decentralized Control: Special Cases

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(7, 0.014), (21, 0.01), (24, 0.079), (25, 0.07), (35, 0.032), (36, 0.073), (39, 0.091), (56, 0.273), (58, 0.088), (61, 0.016), (71, 0.054), (81, 0.015), (86, 0.078), (91, 0.03)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.8132776 103 nips-2009-Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation

Author: Yusuke Watanabe, Kenji Fukumizu

Abstract: We propose a new approach to the analysis of Loopy Belief Propagation (LBP) by establishing a formula that connects the Hessian of the Bethe free energy with the edge zeta function. The formula has a number of theoretical implications on LBP. It is applied to give a sufﬁcient condition that the Hessian of the Bethe free energy is positive deﬁnite, which shows non-convexity for graphs with multiple cycles. The formula clariﬁes the relation between the local stability of a ﬁxed point of LBP and local minima of the Bethe free energy. We also propose a new approach to the uniqueness of LBP ﬁxed point, and show various conditions of uniqueness. 1

same-paper 2 0.78749031 9 nips-2009-A Game-Theoretic Approach to Hypergraph Clustering

Author: Samuel R. Bulò, Marcello Pelillo

3 0.57282662 155 nips-2009-Modelling Relational Data using Bayesian Clustered Tensor Factorization

Author: Ilya Sutskever, Joshua B. Tenenbaum, Ruslan Salakhutdinov

Abstract: We consider the problem of learning probabilistic models for complex relational structures between various types of objects. A model can help us “understand” a dataset of relational facts in at least two ways, by ﬁnding interpretable structure in the data, and by supporting predictions, or inferences about whether particular unobserved relations are likely to be true. Often there is a tradeoff between these two aims: cluster-based models yield more easily interpretable representations, while factorization-based approaches have given better predictive performance on large data sets. We introduce the Bayesian Clustered Tensor Factorization (BCTF) model, which embeds a factorized representation of relations in a nonparametric Bayesian clustering framework. Inference is fully Bayesian but scales well to large data sets. The model simultaneously discovers interpretable clusters and yields predictive performance that matches or beats previous probabilistic models for relational data.

4 0.57276487 112 nips-2009-Human Rademacher Complexity

Author: Xiaojin Zhu, Bryan R. Gibson, Timothy T. Rogers

Abstract: We propose to use Rademacher complexity, originally developed in computational learning theory, as a measure of human learning capacity. Rademacher complexity measures a learner’s ability to ﬁt random labels, and can be used to bound the learner’s true error based on the observed training sample error. We ﬁrst review the deﬁnition of Rademacher complexity and its generalization bound. We then describe a “learning the noise” procedure to experimentally measure human Rademacher complexities. The results from empirical studies showed that: (i) human Rademacher complexity can be successfully measured, (ii) the complexity depends on the domain and training sample size in intuitive ways, (iii) human learning respects the generalization bounds, (iv) the bounds can be useful in predicting the danger of overﬁtting in human learning. Finally, we discuss the potential applications of human Rademacher complexity in cognitive science. 1

5 0.57059997 148 nips-2009-Matrix Completion from Power-Law Distributed Samples

Author: Raghu Meka, Prateek Jain, Inderjit S. Dhillon

Abstract: The low-rank matrix completion problem is a fundamental problem with many important applications. Recently, [4],[13] and [5] obtained the ﬁrst non-trivial theoretical results for the problem assuming that the observed entries are sampled uniformly at random. Unfortunately, most real-world datasets do not satisfy this assumption, but instead exhibit power-law distributed samples. In this paper, we propose a graph theoretic approach to matrix completion that solves the problem for more realistic sampling models. Our method is simpler to analyze than previous methods with the analysis reducing to computing the threshold for complete cascades in random graphs, a problem of independent interest. By analyzing the graph theoretic problem, we show that our method achieves exact recovery when the observed entries are sampled from the Chung-Lu-Vu model, which can generate power-law distributed graphs. We also hypothesize that our algorithm solves the matrix completion problem from an optimal number of entries for the popular preferential attachment model and provide strong empirical evidence for the claim. Furthermore, our method is easy to implement and is substantially faster than existing methods. We demonstrate the effectiveness of our method on random instances where the low-rank matrix is sampled according to the prevalent random graph models for complex networks and present promising preliminary results on the Netﬂix challenge dataset. 1

6 0.56869411 169 nips-2009-Nonlinear Learning using Local Coordinate Coding

7 0.56222188 59 nips-2009-Construction of Nonparametric Bayesian Models from Parametric Bayes Equations

8 0.561225 158 nips-2009-Multi-Label Prediction via Sparse Infinite CCA

9 0.55911726 40 nips-2009-Bayesian Nonparametric Models on Decomposable Graphs

10 0.55766618 122 nips-2009-Label Selection on Graphs

11 0.55682659 86 nips-2009-Exploring Functional Connectivities of the Human Brain using Multivariate Information Analysis

12 0.55633581 3 nips-2009-AUC optimization and the two-sample problem

13 0.55536312 44 nips-2009-Beyond Categories: The Visual Memex Model for Reasoning About Object Relationships

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

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

16 0.5542711 260 nips-2009-Zero-shot Learning with Semantic Output Codes

17 0.55382347 230 nips-2009-Statistical Consistency of Top-k Ranking

18 0.5532704 226 nips-2009-Spatial Normalized Gamma Processes

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

20 0.55242413 229 nips-2009-Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data