nips nips2011 nips2011-213 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Morteza Alamgir, Ulrike V. Luxburg
Abstract: We study the family of p-resistances on graphs for p 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p = 1 the p-resistance coincides with the shortest path distance, for p = 2 it coincides with the standard resistance distance, and for p ! 1 it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase transition takes place. There exist two critical thresholds p⇤ and p⇤⇤ such that if p < p⇤ , then the p-resistance depends on meaningful global properties of the graph, whereas if p > p⇤⇤ , it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p⇤ = 1 + 1/(d 1) and p⇤⇤ = 1 + 1/(d 2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p⇤ and p⇤⇤ is an artifact of our proofs). We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1/p⇤ + 1/q = 1. 1
Reference: text
sentIndex sentText sentNum sentScore
1 de Abstract We study the family of p-resistances on graphs for p 1. [sent-6, score-0.238]
2 We prove that for any fixed graph, for p = 1 the p-resistance coincides with the shortest path distance, for p = 2 it coincides with the standard resistance distance, and for p ! [sent-8, score-0.888]
3 Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. [sent-10, score-0.533]
4 There exist two critical thresholds p⇤ and p⇤⇤ such that if p < p⇤ , then the p-resistance depends on meaningful global properties of the graph, whereas if p > p⇤⇤ , it only depends on trivial local quantities and does not convey any useful information. [sent-12, score-0.445]
5 1 Introduction The graph Laplacian is a popular tool for unsupervised and semi-supervised learning problems on graphs. [sent-15, score-0.154]
6 It is used in the context of spectral clustering, as a regularizer for semi-supervised learning, or to compute the resistance distance on graphs. [sent-16, score-0.55]
7 (2010) proved that as the number of points increases, the resistance distance converges to a meaningless limit function. [sent-21, score-0.779]
8 The main object under study in this paper is the family of p-resistances, which is a generalization of the standard resistance distance. [sent-26, score-0.527]
9 The general picture is that the smaller p is, the more the resistance is concentrated on “short paths”. [sent-28, score-0.482]
10 In particular, the case p = 1 corresponds to the shortest path distance in the graph, the case p = 2 to the standard resistance distance, and the case p ! [sent-29, score-0.831]
11 Second, we study the behavior of p-resistances in the setting of random geometric graphs like lattice graphs, "-graphs or k-nearest neighbor graphs. [sent-31, score-0.351]
12 As there is a tight relationship between p-resistances and graph Laplacians, we can reformulate the artifacts described in Nadler et al. [sent-37, score-0.32]
13 2 Intuition and main results Consider an undirected, weighted graph G = (V, E) with n vertices. [sent-40, score-0.154]
14 The length of a path in the weighted graph is defined as e2 1/we . [sent-43, score-0.264]
15 In the electrical network interpretation, a graph is considered as a network where each edge e 2 E has resistance re = 1/we . [sent-44, score-0.654]
16 The effective resistance (or resistance distance) R(s, t) between two vertices s and t in the network is defined as the overall resistance one obtains when connecting a unit volt battery to s and t. [sent-45, score-1.431]
17 (2010) it has been proved that in many random graph models, the resistance distance R(s, t) between two vertices s and t converges to the trivial limit expression 1/ds + 1/dt as the size of the graph increases. [sent-50, score-1.149]
18 For a subset M ⇢ E of edges we define the contribution of M to the resistance R(s, t) as the part of the sum in (1) that runs over the edges in M . [sent-52, score-0.606]
19 The part R(s, t)local stands for the contribution of i⇤ that stems from the edges in small neighborhoods around s and t, whereas R(s, t)global is the contribution of the remaining edges (exact definition given below). [sent-55, score-0.27]
20 A useful distance function is supposed to encode the global geometry of the graph, for example its cluster properties. [sent-56, score-0.306]
21 However, in case of the standard resistance distance the contribution of the global part becomes negligible as n ! [sent-58, score-0.752]
22 This effect happens because as the graph increases, there are so many different paths between s and t that once the flow has left the neighborhood of s, electricity can flow “without considerable resistance”. [sent-60, score-0.225]
23 The “bottleneck” for the flow is the part that comes from the edges in the local neighborhoods of s and t, because here the flow has to concentrate on relatively few edges. [sent-61, score-0.19]
24 In order to define a useful distance function, we have to ensure that the global part has a significant contribution to the overall resistance. [sent-63, score-0.317]
25 Definition 1 (p-resistance) On any weighted graph G, for any p 1 we define nP o Rp (s, t) := min re |ie |p i = (ie )e2E unit flow from s to t . [sent-68, score-0.219]
26 The smaller p, the more the flow concentrates along the shortest path. [sent-75, score-0.171]
27 We can see that the smaller p is, the more the flow is concentrated along the shortest path between s and t. [sent-78, score-0.328]
28 Our first question is how the family Rp (s, t) behaves as a function of p (that is, on a fixed graph and for fixed s, t). [sent-80, score-0.246]
29 Theorem 2 (Family of p-resistances) For any weighted graph G the following statements are true: 1. [sent-82, score-0.231]
30 For p = 1, the p-resistance coincides with the shortest path distance on the graph. [sent-83, score-0.482]
31 For p = 2, the p-resistance reduces to the standard resistance distance. [sent-85, score-0.435]
32 1, Rp (s, t)p 1 converges to 1/m where m is the unweighted s-t-mincut. [sent-88, score-0.214]
33 The extreme case is p = 1, which yields the shortest path distance. [sent-91, score-0.281]
34 Moreover, the theorem above suggests that for p close to 1, Rp encodes global information about the part of the graph that is concentrated around the shortest path. [sent-93, score-0.603]
35 As p increases, global information is still present, but now describes a larger portion of the graph, say, its cluster structure. [sent-94, score-0.16]
36 The larger p becomes, the less global information is present in Rp (because flows even use extremely long paths that take long detours), and in the extreme case p ! [sent-96, score-0.194]
37 The next question, inspired by the results of von Luxburg et al. [sent-100, score-0.243]
38 (2010), is what happens to Rp (s, t) if we fix p but consider a family (Gn )n2N of graphs such that the number n of vertices in Gn tends to 1. [sent-101, score-0.335]
39 Let us consider geometric graphs such as k-nearest neighbor graphs or "-graphs. [sent-102, score-0.428]
40 We now give exact definitions of the local and global contributions to the p-resistance. [sent-103, score-0.197]
41 We define P local Rp (s) := e2N (s) re |i⇤ |p , e local local local global local Rp (s, t) := Rp (s) + Rp (t), and Rp (s, t) := Rp (s, t) Rp (s, t). [sent-109, score-0.529]
42 Our next result conveys that the behavior of the family of p-resistances shows an interesting phase transition. [sent-110, score-0.197]
43 The statements involve a term ⌧n that should be interpreted as the average degree in the graph Gn (exact definition see later). [sent-111, score-0.231]
44 Theorem 3 (Phase transition for p-resistances in large geometric graphs) Consider a family (Gn )n2N of unweighted geometric graphs on Rd , d > 2 that satisfies some general assumptions (see Section 4 for definitions and details). [sent-116, score-0.6]
45 1, that is the global contribution dominates the local one. [sent-122, score-0.236]
46 Theorem 3 is a substantial extension of the work of von Luxburg et al. [sent-131, score-0.243]
47 We can see that there is a range of values for p for which presistance distances convey very important information about the global topology of the graph, even in extremely large graphs. [sent-134, score-0.372]
48 1, the shortest path distance corresponding to p = 1 converges to the (geodesic) distance of s and t in the underlying space (Tenenbaum et al. [sent-137, score-0.7]
49 (2010) proved that the standard resistance distance (p = 2) converges to the trivial local limit. [sent-140, score-0.79]
50 Theorem 3 now identifies the point of phase transition p⇤ between the boundary cases p = 1 and p = 2. [sent-141, score-0.146]
51 It is widely believed that the minimal s-t cut in geometric graphs converges to the minimum of the degrees of s and t as n ! [sent-144, score-0.403]
52 All graphs in this section are considered to be weighted. [sent-150, score-0.146]
53 If we set p = 1, Problem (⇤) coincides with the well-known linear programming formulation of the shortest path problem, see Chapter 12 of Bazaraa et al. [sent-164, score-0.466]
54 e=(u,v) This coincides with the well-known linear programming formulation of the min-cut problem in unweighted graphs. [sent-171, score-0.21]
55 1 Cp (s, t) C1 (s, t) s-t-mincut 4 Geometric graphs and the Proof of Theorem 3 In this section we consider the class of geometric graphs. [sent-175, score-0.241]
56 The vertices of such graphs consist of points X1 , . [sent-176, score-0.284]
57 , Xn 2 Rd , and vertices are connected by edges if the corresponding points are “close” (for example, they are k-nearest neighbors of each other). [sent-178, score-0.223]
58 General Assumptions: Consider a family (Gn )n2N of unweighted geometric graphs where Gn is based on X1 , . [sent-183, score-0.457]
59 The boundary @M is regular in the sense that there exist positive constants ↵ > 0 and "0 > 0 such that if " < "0 , then for all points x 2 @M we have vol(B" (x) \ M ) ↵ vol(B" (x)) (where vol denotes the Lebesgue volume). [sent-196, score-0.156]
60 It is a straightforward consequence of these assumptions that there exists some function ⌧ (n) =: ⌧n such that r and R are both of the order ⇥((⌧n /n)1/d ) and all degrees in the graph are of order ⇥(⌧n ). [sent-198, score-0.19]
61 1 Lower and upper bounds and the proof of Theorem 3 local global To prove Theorem 3 we need to study the balance between Rp and Rp . [sent-200, score-0.291]
62 p(1+1/d) 1 k (d 2)(p 1) np(1 1/d) 1 ⌧n ⌧n k=1 5 local global Theorem 5 (General bounds on Rp and Rp ) Consider a family (Gn )n2N of unweighted geometric graphs that satisfies the general assumptions. [sent-202, score-0.692]
63 Then the following statements are true for any fixed pair s, t of vertices in Gn : local 4C > Rp (s, t) 1 dp s 1 + 1 dp t 1 and T1 + T2 global Rp (s, t) T1 . [sent-203, score-0.459]
64 To derive lower bounds on Rp (s, t) we construct a second graph G0 which is a contracted version of Gn . [sent-206, score-0.192]
65 To get upper bounds on Rp (s, t) we P exploit the fact that the p-resistance in an unweighted graph can be upper bounded by e2E ip , e where i is any unit flow from s to t. [sent-208, score-0.401]
66 Finally, investigating the properties of lower and upper bounds we can derive the individual bounds local global on Rp and Rp . [sent-210, score-0.301]
67 2 Applications Our general results can directly be applied to many standard geometric graph models. [sent-214, score-0.249]
68 Points are connected by unweighted edges in the graph if their Euclidean distances are smaller than ". [sent-222, score-0.455]
69 We connect each point to its k nearest neighbors by an undirected, unweighted edge. [sent-237, score-0.158]
70 Consider uniform lattices such as the square lattice or triangular lattice in Rd . [sent-246, score-0.175]
71 Note that while the lower bounds of Theorem 3 can be applied to the lattice case, our current upper bounds do not hold because they require that ⌧n ! [sent-250, score-0.173]
72 , l (2) where yi 2 {±1}, C(x) := 'T L' is the energy function involving the standard (p = 2) graph Laplacian L. [sent-257, score-0.154]
73 We now present a simple theorem that connects these findings to those concerning the resistance distance. [sent-262, score-0.503]
74 Theorem 6 (Laplacian regularization in terms of resistance distance) Consider a semi-supervised classification problem with one labeled point per class: '(s) = 1, '(t) = 1. [sent-263, score-0.49]
75 It is easy to verify that '⇤ = L† (es et ) and R2 (s, t) = (es et )T L† (es et ) where L† is the pseudo-inverse of the Laplacian matrix L. [sent-267, score-0.297]
76 Therefore we have '⇤ (v) = (ev )T L† (es et ) and '⇤ (v) '⇤ (t) > '⇤ (s) (a) () (ev '⇤ (v) () (ev et )T L† (ev et ) > (ev et )T L† (es es )T L† (ev et ) > (es ev )T L† (es et ) es ) () R2 (v, t) > R2 (v, s). [sent-268, score-0.818]
77 Here in step (a) we use the symmetry of L† to state that eT L† es = eT L† ev . [sent-269, score-0.186]
78 dv dt dv ds Hence, the theorem states that if we threshold the function '⇤ at 0 to separate the two classes, then all the points will be assigned to the labeled vertex with larger degree. [sent-273, score-0.204]
79 In particular, using q-regularization for the value q with 1/q + 1/p⇤ = 1 would resolve the artifacts of Laplacian regularization described in Nadler et al. [sent-279, score-0.221]
80 The usual Laplacian regularization term as in Zhu et al. [sent-282, score-0.154]
81 6 Related families of distance functions on graphs In this section we sketch some relations between p-resistances and other families of distances. [sent-285, score-0.359]
82 (H) e2E 7 Now it is easy to see that the main difference between Herbster’s definition (H) and our definition (⇤) is that (H) takes the power p 1 of the resistances re , while we keep the resistances with H power 1. [sent-296, score-0.182]
83 2 Other families of distances There also exist other families of distances on graphs that share some of the properties of presistances. [sent-300, score-0.456]
84 We will only discuss the ones that are most related to our work, for more references see von Luxburg et al. [sent-301, score-0.243]
85 The first such family was introduced by Yen et al. [sent-303, score-0.191]
86 This family is parameterized by a parameter ✓, contains the shortest path distance at one end (✓ ! [sent-305, score-0.488]
87 1) and the standard resistance distance at the other end (✓ ! [sent-306, score-0.55]
88 Even though its derivation is complicated, it has a closed form solution and can be interpreted intuitively: The contribution of a path to the overall distance is “discounted” by a factor (1/↵)l where l is the length of the path. [sent-310, score-0.264]
89 0, the logarithmic forest distance distance converges to the shortest path distance, for ↵ ! [sent-312, score-0.601]
90 At the time of writing this paper, the major disadvantage of both the families introduced by Yen et al. [sent-314, score-0.148]
91 (2008) and Chebotarev (2011) is that it is unknown how their distances behave as the size of the graph increases. [sent-315, score-0.246]
92 It is clear that on the one end (shortest path), they convey global information, whereas on the other end (resistance distance) they depend on local quantities only when n ! [sent-316, score-0.3]
93 In particular, for p = 1 it coincides with the shortest path distance, for p = 2 with the standard resistance distance and for p ! [sent-324, score-0.917]
94 For this value of p, the p-resistances encode those global properties of the graph that are most important for machine learning, namely the cluster structure of the graph. [sent-328, score-0.314]
95 They go much beyond the work of von Luxburg et al. [sent-330, score-0.243]
96 (2010) (which only studied the case p = 2) and lead to an intuitive explanation of the artifacts of Laplacian regularization discovered in Nadler et al. [sent-331, score-0.221]
97 For p = 2, the resistance distance u can be expressed in terms of the eigenvalues and eigenvectors of the Laplacian. [sent-334, score-0.55]
98 A class of graph-geodetic distances generalizing the shortets path and the resistance distances. [sent-354, score-0.637]
99 Predicting the labelling of a graph via minimum p-seminorm interpolation. [sent-369, score-0.154]
100 Semi-supervised learning with the graph Laplacian: The limit of infinite unlabelled data. [sent-375, score-0.182]
wordName wordTfidf (topN-words)
[('resistance', 0.435), ('rp', 0.374), ('ow', 0.244), ('herbster', 0.193), ('luxburg', 0.177), ('shortest', 0.171), ('gn', 0.167), ('laplacian', 0.16), ('graph', 0.154), ('ev', 0.148), ('graphs', 0.146), ('von', 0.144), ('unweighted', 0.124), ('global', 0.123), ('ie', 0.123), ('nadler', 0.118), ('distance', 0.115), ('path', 0.11), ('et', 0.099), ('vertices', 0.097), ('geometric', 0.095), ('distances', 0.092), ('family', 0.092), ('converges', 0.09), ('coincides', 0.086), ('statements', 0.077), ('local', 0.074), ('resistances', 0.073), ('yen', 0.073), ('convey', 0.073), ('paths', 0.071), ('phase', 0.07), ('lattice', 0.069), ('theorem', 0.068), ('np', 0.067), ('artifacts', 0.067), ('hler', 0.064), ('lever', 0.064), ('vol', 0.059), ('regularization', 0.055), ('conjecture', 0.053), ('families', 0.049), ('bazaraa', 0.049), ('chebotarev', 0.049), ('presistance', 0.049), ('ows', 0.048), ('transition', 0.048), ('concentrated', 0.047), ('edges', 0.046), ('trivial', 0.045), ('dp', 0.044), ('cp', 0.042), ('rd', 0.042), ('points', 0.041), ('neighbor', 0.041), ('intuition', 0.041), ('part', 0.04), ('morteza', 0.039), ('rayleigh', 0.039), ('doyle', 0.039), ('meaningless', 0.039), ('connected', 0.039), ('critical', 0.039), ('contribution', 0.039), ('bounds', 0.038), ('es', 0.038), ('lattices', 0.037), ('cluster', 0.037), ('re', 0.036), ('minimal', 0.036), ('degrees', 0.036), ('vertex', 0.035), ('topology', 0.035), ('conveys', 0.035), ('zhu', 0.034), ('connect', 0.034), ('straight', 0.033), ('thresholds', 0.033), ('hein', 0.032), ('bingen', 0.032), ('supposed', 0.031), ('supp', 0.031), ('ndings', 0.031), ('proved', 0.031), ('xn', 0.03), ('proposition', 0.03), ('neighborhoods', 0.03), ('monotonicity', 0.03), ('dv', 0.03), ('unlabeled', 0.03), ('whereas', 0.03), ('edge', 0.029), ('url', 0.029), ('unit', 0.029), ('sch', 0.028), ('exist', 0.028), ('proof', 0.028), ('limit', 0.028), ('boundary', 0.028), ('upper', 0.028)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999982 213 nips-2011-Phase transition in the family of p-resistances
Author: Morteza Alamgir, Ulrike V. Luxburg
Abstract: We study the family of p-resistances on graphs for p 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p = 1 the p-resistance coincides with the shortest path distance, for p = 2 it coincides with the standard resistance distance, and for p ! 1 it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase transition takes place. There exist two critical thresholds p⇤ and p⇤⇤ such that if p < p⇤ , then the p-resistance depends on meaningful global properties of the graph, whereas if p > p⇤⇤ , it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p⇤ = 1 + 1/(d 1) and p⇤⇤ = 1 + 1/(d 2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p⇤ and p⇤⇤ is an artifact of our proofs). We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1/p⇤ + 1/q = 1. 1
2 0.12439222 118 nips-2011-High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity
Author: Po-ling Loh, Martin J. Wainwright
Abstract: Although the standard formulations of prediction problems involve fully-observed and noiseless data drawn in an i.i.d. manner, many applications involve noisy and/or missing data, possibly involving dependencies. We study these issues in the context of high-dimensional sparse linear regression, and propose novel estimators for the cases of noisy, missing, and/or dependent data. Many standard approaches to noisy or missing data, such as those using the EM algorithm, lead to optimization problems that are inherently non-convex, and it is difficult to establish theoretical guarantees on practical algorithms. While our approach also involves optimizing non-convex programs, we are able to both analyze the statistical error associated with any global optimum, and prove that a simple projected gradient descent algorithm will converge in polynomial time to a small neighborhood of the set of global minimizers. On the statistical side, we provide non-asymptotic bounds that hold with high probability for the cases of noisy, missing, and/or dependent data. On the computational side, we prove that under the same types of conditions required for statistical consistency, the projected gradient descent algorithm will converge at geometric rates to a near-global minimizer. We illustrate these theoretical predictions with simulations, showing agreement with the predicted scalings. 1
3 0.11526298 251 nips-2011-Shaping Level Sets with Submodular Functions
Author: Francis R. Bach
Abstract: We consider a class of sparsity-inducing regularization terms based on submodular functions. While previous work has focused on non-decreasing functions, we explore symmetric submodular functions and their Lov´ sz extensions. We show that the Lov´ sz a a extension may be seen as the convex envelope of a function that depends on level sets (i.e., the set of indices whose corresponding components of the underlying predictor are greater than a given constant): this leads to a class of convex structured regularization terms that impose prior knowledge on the level sets, and not only on the supports of the underlying predictors. We provide unified optimization algorithms, such as proximal operators, and theoretical guarantees (allowed level sets and recovery conditions). By selecting specific submodular functions, we give a new interpretation to known norms, such as the total variation; we also define new norms, in particular ones that are based on order statistics with application to clustering and outlier detection, and on noisy cuts in graphs with application to change point detection in the presence of outliers.
4 0.11016531 114 nips-2011-Hierarchical Multitask Structured Output Learning for Large-scale Sequence Segmentation
Author: Nico Goernitz, Christian Widmer, Georg Zeller, Andre Kahles, Gunnar Rätsch, Sören Sonnenburg
Abstract: We present a novel regularization-based Multitask Learning (MTL) formulation for Structured Output (SO) prediction for the case of hierarchical task relations. Structured output prediction often leads to difficult inference problems and hence requires large amounts of training data to obtain accurate models. We propose to use MTL to exploit additional information from related learning tasks by means of hierarchical regularization. Training SO models on the combined set of examples from multiple tasks can easily become infeasible for real world applications. To be able to solve the optimization problems underlying multitask structured output learning, we propose an efficient algorithm based on bundle-methods. We demonstrate the performance of our approach in applications from the domain of computational biology addressing the key problem of gene finding. We show that 1) our proposed solver achieves much faster convergence than previous methods and 2) that the Hierarchical SO-MTL approach outperforms considered non-MTL methods. 1
5 0.10955969 186 nips-2011-Noise Thresholds for Spectral Clustering
Author: Sivaraman Balakrishnan, Min Xu, Akshay Krishnamurthy, Aarti Singh
Abstract: Although spectral clustering has enjoyed considerable empirical success in machine learning, its theoretical properties are not yet fully developed. We analyze the performance of a spectral algorithm for hierarchical clustering and show that on a class of hierarchically structured similarity matrices, this algorithm can tolerate noise that grows with the number of data points while still perfectly recovering the hierarchical clusters with high probability. We additionally improve upon previous results for k-way spectral clustering to derive conditions under which spectral clustering makes no mistakes. Further, using minimax analysis, we derive tight upper and lower bounds for the clustering problem and compare the performance of spectral clustering to these information theoretic limits. We also present experiments on simulated and real world data illustrating our results. 1
6 0.10880911 117 nips-2011-High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions
7 0.1063251 258 nips-2011-Sparse Bayesian Multi-Task Learning
8 0.091177419 195 nips-2011-On Learning Discrete Graphical Models using Greedy Methods
9 0.087771095 242 nips-2011-See the Tree Through the Lines: The Shazoo Algorithm
10 0.085393086 248 nips-2011-Semi-supervised Regression via Parallel Field Regularization
11 0.085340202 9 nips-2011-A More Powerful Two-Sample Test in High Dimensions using Random Projection
12 0.082810208 71 nips-2011-Directed Graph Embedding: an Algorithm based on Continuous Limits of Laplacian-type Operators
13 0.08199843 47 nips-2011-Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts
14 0.081866927 199 nips-2011-On fast approximate submodular minimization
15 0.080486283 231 nips-2011-Randomized Algorithms for Comparison-based Search
16 0.0799255 67 nips-2011-Data Skeletonization via Reeb Graphs
17 0.076508999 146 nips-2011-Learning Higher-Order Graph Structure with Features by Structure Penalty
18 0.072100602 236 nips-2011-Regularized Laplacian Estimation and Fast Eigenvector Approximation
19 0.070785984 54 nips-2011-Co-regularized Multi-view Spectral Clustering
20 0.067101076 198 nips-2011-On U-processes and clustering performance
topicId topicWeight
[(0, 0.188), (1, 0.001), (2, -0.082), (3, -0.071), (4, -0.059), (5, -0.013), (6, -0.167), (7, -0.001), (8, 0.053), (9, -0.075), (10, -0.027), (11, 0.068), (12, -0.009), (13, -0.06), (14, 0.01), (15, 0.085), (16, 0.051), (17, 0.004), (18, -0.019), (19, 0.013), (20, -0.011), (21, 0.118), (22, 0.007), (23, 0.172), (24, 0.056), (25, -0.07), (26, -0.032), (27, 0.006), (28, -0.026), (29, -0.012), (30, 0.065), (31, -0.02), (32, -0.011), (33, 0.164), (34, 0.012), (35, -0.094), (36, 0.079), (37, 0.091), (38, -0.048), (39, -0.025), (40, 0.004), (41, 0.05), (42, 0.027), (43, 0.019), (44, -0.101), (45, -0.097), (46, 0.003), (47, 0.009), (48, -0.009), (49, -0.199)]
simIndex simValue paperId paperTitle
same-paper 1 0.96933961 213 nips-2011-Phase transition in the family of p-resistances
Author: Morteza Alamgir, Ulrike V. Luxburg
Abstract: We study the family of p-resistances on graphs for p 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p = 1 the p-resistance coincides with the shortest path distance, for p = 2 it coincides with the standard resistance distance, and for p ! 1 it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase transition takes place. There exist two critical thresholds p⇤ and p⇤⇤ such that if p < p⇤ , then the p-resistance depends on meaningful global properties of the graph, whereas if p > p⇤⇤ , it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p⇤ = 1 + 1/(d 1) and p⇤⇤ = 1 + 1/(d 2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p⇤ and p⇤⇤ is an artifact of our proofs). We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1/p⇤ + 1/q = 1. 1
2 0.74149102 67 nips-2011-Data Skeletonization via Reeb Graphs
Author: Xiaoyin Ge, Issam I. Safa, Mikhail Belkin, Yusu Wang
Abstract: Recovering hidden structure from complex and noisy non-linear data is one of the most fundamental problems in machine learning and statistical inference. While such data is often high-dimensional, it is of interest to approximate it with a lowdimensional or even one-dimensional space, since many important aspects of data are often intrinsically low-dimensional. Furthermore, there are many scenarios where the underlying structure is graph-like, e.g, river/road networks or various trajectories. In this paper, we develop a framework to extract, as well as to simplify, a one-dimensional ”skeleton” from unorganized data using the Reeb graph. Our algorithm is very simple, does not require complex optimizations and can be easily applied to unorganized high-dimensional data such as point clouds or proximity graphs. It can also represent arbitrary graph structures in the data. We also give theoretical results to justify our method. We provide a number of experiments to demonstrate the effectiveness and generality of our algorithm, including comparisons to existing methods, such as principal curves. We believe that the simplicity and practicality of our algorithm will help to promote skeleton graphs as a data analysis tool for a broad range of applications.
3 0.67903781 236 nips-2011-Regularized Laplacian Estimation and Fast Eigenvector Approximation
Author: Patrick O. Perry, Michael W. Mahoney
Abstract: Recently, Mahoney and Orecchia demonstrated that popular diffusion-based procedures to compute a quick approximation to the first nontrivial eigenvector of a data graph Laplacian exactly solve certain regularized Semi-Definite Programs (SDPs). In this paper, we extend that result by providing a statistical interpretation of their approximation procedure. Our interpretation will be analogous to the manner in which 2 -regularized or 1 -regularized 2 -regression (often called Ridge regression and Lasso regression, respectively) can be interpreted in terms of a Gaussian prior or a Laplace prior, respectively, on the coefficient vector of the regression problem. Our framework will imply that the solutions to the MahoneyOrecchia regularized SDP can be interpreted as regularized estimates of the pseudoinverse of the graph Laplacian. Conversely, it will imply that the solution to this regularized estimation problem can be computed very quickly by running, e.g., the fast diffusion-based PageRank procedure for computing an approximation to the first nontrivial eigenvector of the graph Laplacian. Empirical results are also provided to illustrate the manner in which approximate eigenvector computation implicitly performs statistical regularization, relative to running the corresponding exact algorithm. 1
4 0.67763388 117 nips-2011-High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions
Author: Animashree Anandkumar, Vincent Tan, Alan S. Willsky
Abstract: We consider the problem of Ising and Gaussian graphical model selection given n i.i.d. samples from the model. We propose an efficient threshold-based algorithm for structure estimation based on conditional mutual information thresholding. This simple local algorithm requires only loworder statistics of the data and decides whether two nodes are neighbors in the unknown graph. We identify graph families for which the proposed algorithm has low sample and computational complexities. Under some transparent assumptions, we establish that the proposed algorithm is −4 structurally consistent (or sparsistent) when the number of samples scales as n = Ω(Jmin log p), where p is the number of nodes and Jmin is the minimum edge potential. We also develop novel non-asymptotic techniques for obtaining necessary conditions for graphical model selection. Keywords: Graphical model selection, high-dimensional learning, local-separation property, necessary conditions, typical sets, Fano’s inequality.
5 0.55270547 47 nips-2011-Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts
Author: Matthias Hein, Simon Setzer
Abstract: Spectral clustering is based on the spectral relaxation of the normalized/ratio graph cut criterion. While the spectral relaxation is known to be loose, it has been shown recently that a non-linear eigenproblem yields a tight relaxation of the Cheeger cut. In this paper, we extend this result considerably by providing a characterization of all balanced graph cuts which allow for a tight relaxation. Although the resulting optimization problems are non-convex and non-smooth, we provide an efficient first-order scheme which scales to large graphs. Moreover, our approach comes with the quality guarantee that given any partition as initialization the algorithm either outputs a better partition or it stops immediately. 1
6 0.54536897 296 nips-2011-Uniqueness of Belief Propagation on Signed Graphs
7 0.54519933 9 nips-2011-A More Powerful Two-Sample Test in High Dimensions using Random Projection
8 0.5325219 81 nips-2011-Efficient anomaly detection using bipartite k-NN graphs
9 0.53242922 195 nips-2011-On Learning Discrete Graphical Models using Greedy Methods
10 0.518493 31 nips-2011-An Application of Tree-Structured Expectation Propagation for Channel Decoding
11 0.51758707 146 nips-2011-Learning Higher-Order Graph Structure with Features by Structure Penalty
12 0.48624843 71 nips-2011-Directed Graph Embedding: an Algorithm based on Continuous Limits of Laplacian-type Operators
13 0.48289064 118 nips-2011-High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity
14 0.48085237 114 nips-2011-Hierarchical Multitask Structured Output Learning for Large-scale Sequence Segmentation
15 0.4653568 274 nips-2011-Structure Learning for Optimization
16 0.4504697 150 nips-2011-Learning a Distance Metric from a Network
17 0.44603676 251 nips-2011-Shaping Level Sets with Submodular Functions
18 0.44299075 186 nips-2011-Noise Thresholds for Spectral Clustering
19 0.43341905 263 nips-2011-Sparse Manifold Clustering and Embedding
20 0.42889389 242 nips-2011-See the Tree Through the Lines: The Shazoo Algorithm
topicId topicWeight
[(0, 0.039), (4, 0.397), (20, 0.037), (26, 0.033), (31, 0.071), (33, 0.016), (43, 0.089), (45, 0.062), (48, 0.013), (57, 0.029), (74, 0.059), (83, 0.029), (99, 0.055)]
simIndex simValue paperId paperTitle
1 0.96058112 130 nips-2011-Inductive reasoning about chimeric creatures
Author: Charles Kemp
Abstract: Given one feature of a novel animal, humans readily make inferences about other features of the animal. For example, winged creatures often fly, and creatures that eat fish often live in the water. We explore the knowledge that supports these inferences and compare two approaches. The first approach proposes that humans rely on abstract representations of dependency relationships between features, and is formalized here as a graphical model. The second approach proposes that humans rely on specific knowledge of previously encountered animals, and is formalized here as a family of exemplar models. We evaluate these models using a task where participants reason about chimeras, or animals with pairs of features that have not previously been observed to co-occur. The results support the hypothesis that humans rely on explicit representations of relationships between features. Suppose that an eighteenth-century naturalist learns about a new kind of animal that has fur and a duck’s bill. Even though the naturalist has never encountered an animal with this pair of features, he should be able to make predictions about other features of the animal—for example, the animal could well live in water but probably does not have feathers. Although the platypus exists in reality, from a eighteenth-century perspective it qualifies as a chimera, or an animal that combines two or more features that have not previously been observed to co-occur. Here we describe a probabilistic account of inductive reasoning and use it to account for human inferences about chimeras. The inductive problems we consider are special cases of the more general problem in Figure 1a where a reasoner is given a partially observed matrix of animals by features then asked to infer the values of the missing entries. This general problem has been previously studied and is addressed by computational models of property induction, categorization, and generalization [1–7]. A challenge faced by all of these models is to capture the background knowledge that guides inductive inferences. Some accounts rely on similarity relationships between animals [6, 8], others rely on causal relationships between features [9, 10], and others incorporate relationships between animals and relationships between features [11]. We will evaluate graphical models that capture both kinds of relationships (Figure 1a), but will focus in particular on relationships between features. Psychologists have previously suggested that humans rely on explicit mental representations of relationships between features [12–16]. Often these representations are described as theories—for example, theories that specify a causal relationship between having wings and flying, or living in the sea and eating fish. Relationships between features may take several forms: for example, one feature may cause, enable, prevent, be inconsistent with, or be a special case of another feature. For simplicity, we will treat all of these relationships as instances of dependency relationships between features, and will capture them using an undirected graphical model. Previous studies have used graphical models to account for human inferences about features but typically these studies consider toy problems involving a handful of novel features such as “has gene X14” or “has enzyme Y132” [9, 11]. Participants might be told, for example, that gene X14 leads to the production of enzyme Y132, then asked to use this information when reasoning about novel animals. Here we explore whether a graphical model approach can account for inferences 1 (a) slow heavy flies (b) wings hippo 1 1 0 0 rhino 1 1 0 0 sparrow 0 0 1 1 robin 0 0 1 1 new ? ? 1 ? o Figure 1: Inductive reasoning about animals and features. (a) Inferences about the features of a new animal onew that flies may draw on similarity relationships between animals (the new animal is similar to sparrows and robins but not hippos and rhinos), and on dependency relationships between features (flying and having wings are linked). (b) A graph product produced by combining the two graph structures in (a). about familiar features. Working with familiar features raises a methodological challenge since participants have a substantial amount of knowledge about these features and can reason about them in multiple ways. Suppose, for example, that you learn that a novel animal can fly (Figure 1a). To conclude that the animal probably has wings, you might consult a mental representation similar to the graph at the top of Figure 1a that specifies a dependency relationship between flying and having wings. On the other hand, you might reach the same conclusion by thinking about flying creatures that you have previously encountered (e.g. sparrows and robins) and noticing that these creatures have wings. Since the same conclusion can be reached in two different ways, judgments about arguments of this kind provide little evidence about the mental representations involved. The challenge of working with familiar features directly motivates our focus on chimeras. Inferences about chimeras draw on rich background knowledge but require the reasoner to go beyond past experience in a fundamental way. For example, if you learn that an animal flies and has no legs, you cannot make predictions about the animal by thinking of flying, no-legged creatures that you have previously encountered. You may, however, still be able to infer that the novel animal has wings if you understand the relationship between flying and having wings. We propose that graphical models over features can help to explain how humans make inferences of this kind, and evaluate our approach by comparing it to a family of exemplar models. The next section introduces these models, and we then describe two experiments designed to distinguish between the models. 1 Reasoning about objects and features Our models make use of a binary matrix D where the rows {o1 , . . . , o129 } correspond to objects, and the columns {f 1 , . . . , f 56 } correspond to features. A subset of the objects is shown in Figure 2a, and the full set of features is shown in Figure 2b and its caption. Matrix D was extracted from the Leuven natural concept database [17], which includes 129 animals and 757 features in total. We chose a subset of these features that includes a mix of perceptual and behavioral features, and that includes many pairs of features that depend on each other. For example, animals that “live in water” typically “can swim,” and animals that have “no legs” cannot “jump far.” Matrix D can be used to formulate problems where a reasoner observes one or two features of a new object (i.e. animal o130 ) and must make inferences about the remaining features of the animal. The next two sections describe graphical models that can be used to address this problem. The first graphical model O captures relationships between objects, and the second model F captures relationships between features. We then discuss how these models can be combined, and introduce a family of exemplar-style models that will be compared with our graphical models. A graphical model over objects Many accounts of inductive reasoning focus on similarity relationships between objects [6, 8]. Here we describe a tree-structured graphical model O that captures these relationships. The tree was constructed from matrix D using average linkage clustering and the Jaccard similarity measure, and part of the resulting structure is shown in Figure 2a. The subtree in Figure 2a includes clusters 2 alligator caiman crocodile monitor lizard dinosaur blindworm boa cobra python snake viper chameleon iguana gecko lizard salamander frog toad tortoise turtle anchovy herring sardine cod sole salmon trout carp pike stickleback eel flatfish ray plaice piranha sperm whale squid swordfish goldfish dolphin orca whale shark bat fox wolf beaver hedgehog hamster squirrel mouse rabbit bison elephant hippopotamus rhinoceros lion tiger polar bear deer dromedary llama giraffe zebra kangaroo monkey cat dog cow horse donkey pig sheep (a) (b) can swim lives in water eats fish eats nuts eats grain eats grass has gills can jump far has two legs has no legs has six legs has four legs can fly can be ridden has sharp teeth nocturnal has wings strong predator can see in dark eats berries lives in the sea lives in the desert crawls lives in the woods has mane lives in trees can climb well lives underground has feathers has scales slow has fur heavy Figure 2: Graph structures used to define graphical models O and F. (a) A tree that captures similarity relationships between animals. The full tree includes 129 animals, and only part of the tree is shown here. The grey points along the branches indicate locations where a novel animal o130 could be attached to the tree. (b) A network capturing pairwise dependency relationships between features. The edges capture both positive and negative dependencies. All edges in the network are shown, and the network also includes 20 isolated nodes for the following features: is black, is blue, is green, is grey, is pink, is red, is white, is yellow, is a pet, has a beak, stings, stinks, has a long neck, has feelers, sucks blood, lays eggs, makes a web, has a hump, has a trunk, and is cold-blooded. corresponding to amphibians and reptiles, aquatic creatures, and land mammals, and the subtree omitted for space includes clusters for insects and birds. We assume that the features in matrix D (i.e. the columns) are generated independently over O: P (f i |O, π i , λi ). P (D|O, π, λ) = i i i i The distribution P (f |O, π , λ ) is based on the intuition that nearby nodes in O tend to have the same value of f i . Previous researchers [8, 18] have used a directed graphical model where the distribution at the root node is based on the baserate π i , and any other node v with parent u has the following conditional probability distribution: i P (v = 1|u) = π i + (1 − π i )e−λ l , if u = 1 i π i − π i e−λ l , if u = 0 (1) where l is the length of the branch joining node u to node v. The variability parameter λi captures the extent to which feature f i is expected to vary over the tree. Note, for example, that any node v must take the same value as its parent u when λ = 0. To avoid free parameters, the feature baserates π i and variability parameters λi are set to their maximum likelihood values given the observed values of the features {f i } in the data matrix D. The conditional distributions in Equation 1 induce a joint distribution over all of the nodes in graph O, and the distribution P (f i |O, π i , λi ) is computed by marginalizing out the values of the internal nodes. Although we described O as a directed graphical model, the model can be converted into an equivalent undirected model with a potential for each edge in the tree and a potential for the root node. Here we use the undirected version of the model, which is a natural counterpart to the undirected model F described in the next section. The full version of structure O in Figure 2a includes 129 familiar animals, and our task requires inferences about a novel animal o130 that must be slotted into the structure. Let D′ be an expanded version of D that includes a row for o130 , and let O′ be an expanded version of O that includes a node for o130 . The edges in Figure 2a are marked with evenly spaced gray points, and we use a 3 uniform prior P (O′ ) over all trees that can be created by attaching o130 to one of these points. Some of these trees have identical topologies, since some edges in Figure 2a have multiple gray points. Predictions about o130 can be computed using: P (D′ |D) = P (D′ |O′ , D)P (O′ |D) ∝ O′ P (D′ |O′ , D)P (D|O′ )P (O′ ). (2) O′ Equation 2 captures the basic intuition that the distribution of features for o130 is expected to be consistent with the distribution observed for previous animals. For example, if o130 is known to fly then the trees with high posterior probability P (O′ |D) will be those where o130 is near other flying creatures (Figure 1a), and since these creatures have wings Equation 2 predicts that o130 probably also has wings. As this example suggests, model O captures dependency relationships between features implicitly, and therefore stands in contrast to models like F that rely on explicit representations of relationships between features. A graphical model over features Model F is an undirected graphical model defined over features. The graph shown in Figure 2b was created by identifying pairs where one feature depends directly on another. The author and a research assistant both independently identified candidate sets of pairwise dependencies, and Figure 2b was created by merging these sets and reaching agreement about how to handle any discrepancies. As previous researchers have suggested [13, 15], feature dependencies can capture several kinds of relationships. For example, wings enable flying, living in the sea leads to eating fish, and having no legs rules out jumping far. We work with an undirected graph because some pairs of features depend on each other but there is no clear direction of causal influence. For example, there is clearly a dependency relationship between being nocturnal and seeing in the dark, but no obvious sense in which one of these features causes the other. We assume that the rows of the object-feature matrix D are generated independently from an undirected graphical model F defined over the feature structure in Figure 2b: P (oi |F). P (D|F) = i Model F includes potential functions for each node and for each edge in the graph. These potentials were learned from matrix D using the UGM toolbox for undirected graphical models [19]. The learned potentials capture both positive and negative relationships: for example, animals that live in the sea tend to eat fish, and tend not to eat berries. Some pairs of feature values never occur together in matrix D (there are no creatures that fly but do not have wings). We therefore chose to compute maximum a posteriori values of the potential functions rather than maximum likelihood values, and used a diffuse Gaussian prior with a variance of 100 on the entries in each potential. After learning the potentials for model F, we can make predictions about a new object o130 using the distribution P (o130 |F). For example, if o130 is known to fly (Figure 1a), model F predicts that o130 probably has wings because the learned potentials capture a positive dependency between flying and having wings. Combining object and feature relationships There are two simple ways to combine models O and F in order to develop an approach that incorporates both relationships between features and relationships between objects. The output combination model computes the predictions of both models in isolation, then combines these predictions using a weighted sum. The resulting model is similar to a mixture-of-experts model, and to avoid free parameters we use a mixing weight of 0.5. The structure combination model combines the graph structures used by the two models and relies on a set of potentials defined over the resulting graph product. An example of a graph product is shown in Figure 1b, and the potential functions for this graph are inherited from the component models in the natural way. Kemp et al. [11] use a similar approach to combine a functional causal model with an object model O, but note that our structure combination model uses an undirected model F rather than a functional causal model over features. Both combination models capture the intuition that inductive inferences rely on relationships between features and relationships between objects. The output combination model has the virtue of 4 simplicity, and the structure combination model is appealing because it relies on a single integrated representation that captures both relationships between features and relationships between objects. To preview our results, our data suggest that the combination models perform better overall than either O or F in isolation, and that both combination models perform about equally well. Exemplar models We will compare the family of graphical models already described with a family of exemplar models. The key difference between these model families is that the exemplar models do not rely on explicit representations of relationships between objects and relationships between features. Comparing the model families can therefore help to establish whether human inferences rely on representations of this sort. Consider first a problem where a reasoner must predict whether object o130 has feature k after observing that it has feature i. An exemplar model addresses the problem by retrieving all previouslyobserved objects with feature i and computing the proportion that have feature k: P (ok = 1|oi = 1) = |f k & f i | |f i | (3) where |f k | is the number of objects in matrix D that have feature k, and |f k & f i | is the number that have both feature k and feature i. Note that we have streamlined our notation by using ok instead of o130 to refer to the kth feature value for object o130 . k Suppose now that the reasoner observes that object o130 has features i and j. The natural generalization of Equation 3 is: P (ok = 1|oi = 1, oj = 1) = |f k & f i & f j | |f i & f j | (4) Because we focus on chimeras, |f i & f j | = 0 and Equation 4 is not well defined. We therefore evaluate an exemplar model that computes predictions for the two observed features separately then computes the weighted sum of these predictions: P (ok = 1|oi = 1, oj = 1) = wi |f k & f i | |f k & f j | + wj . i| |f |f j | (5) where the weights wi and wj must sum to one. We consider four ways in which the weights could be set. The first strategy sets wi = wj = 0.5. The second strategy sets wi ∝ |f i |, and is consistent with an approach where the reasoner retrieves all exemplars in D that are most similar to the novel animal and reports the proportion of these exemplars that have feature k. The third strategy sets wi ∝ |f1i | , and captures the idea that features should be weighted by their distinctiveness [20]. The final strategy sets weights according to the coherence of each feature [21]. A feature is coherent if objects with that feature tend to resemble each other overall, and we define the coherence of feature i as the expected Jaccard similarity between two randomly chosen objects from matrix D that both have feature i. Note that the final three strategies are all consistent with previous proposals from the psychological literature, and each one might be expected to perform well. Because exemplar models and prototype models are often compared, it is natural to consider a prototype model [22] as an additional baseline. A standard prototype model would partition the 129 animals into categories and would use summary statistics for these categories to make predictions about the novel animal o130 . We will not evaluate this model because it corresponds to a coarser version of model O, which organizes the animals into a hierarchy of categories. The key characteristic shared by both models is that they explicitly capture relationships between objects but not features. 2 Experiment 1: Chimeras Our first experiment explores how people make inferences about chimeras, or novel animals with features that have not previously been observed to co-occur. Inferences about chimeras raise challenges for exemplar models, and therefore help to establish whether humans rely on explicit representations of relationships between features. Each argument can be represented as f i , f j → f k 5 exemplar r = 0.42 7 feature F exemplar (wi = |f i |) (wi = 0.5) r = 0.44 7 object O r = 0.69 7 output combination r = 0.31 7 structure combination r = 0.59 7 r = 0.60 7 5 5 5 5 5 3 3 3 3 3 3 all 5 1 1 0 1 r = 0.06 7 conflict 0.5 1 1 0 0.5 1 r = 0.71 7 1 0 0.5 1 r = −0.02 7 1 0 0.5 1 r = 0.49 7 0 5 5 5 5 3 3 3 3 1 5 3 0.5 r = 0.57 7 5 3 1 0 0.5 1 r = 0.51 7 edge 0.5 r = 0.17 7 1 1 0 0.5 1 r = 0.64 7 1 0 0.5 1 r = 0.83 7 1 0 0.5 1 r = 0.45 7 1 0 0.5 1 r = 0.76 7 0 5 5 5 5 3 3 3 3 1 5 3 0.5 r = 0.79 7 5 3 1 1 0 0.5 1 r = 0.26 7 other 1 0 1 0 0.5 1 r = 0.25 7 1 0 0.5 1 r = 0.19 7 1 0 0.5 1 r = 0.25 7 1 0 0.5 1 r = 0.24 7 0 7 5 5 5 5 5 3 3 3 3 1 5 3 0.5 r = 0.33 3 1 1 0 0.5 1 1 0 0.5 1 1 0 0.5 1 1 0 0.5 1 1 0 0.5 1 0 0.5 1 Figure 3: Argument ratings for Experiment 1 plotted against the predictions of six models. The y-axis in each panel shows human ratings on a seven point scale, and the x-axis shows probabilities according to one of the models. Correlation coefficients are shown for each plot. where f i and f k are the premises (e.g. “has no legs” and “can fly”) and f k is the conclusion (e.g. “has wings”). We are especially interested in conflict cases where the premises f i and f j lead to opposite conclusions when taken individually: for example, most animals with no legs do not have wings, but most animals that fly do have wings. Our models that incorporate feature structure F can resolve this conflict since F includes a dependency between “wings” and “can fly” but not between “wings” and “has no legs.” Our models that do not include F cannot resolve the conflict and predict that humans will be uncertain about whether the novel animal has wings. Materials. The object-feature matrix D includes 447 feature pairs {f i , f j } such that none of the 129 animals has both f i and f j . We selected 40 pairs (see the supporting material) and created 400 arguments in total by choosing 10 conclusion features for each pair. The arguments can be assigned to three categories. Conflict cases are arguments f i , f j → f k such that the single-premise arguments f i → f k and f j → f k lead to incompatible predictions. For our purposes, two singlepremise arguments with the same conclusion are deemed incompatible if one leads to a probability greater than 0.9 according to Equation 3, and the other leads to a probability less than 0.1. Edge cases are arguments f i , f j → f k such that the feature network in Figure 2b includes an edge between f k and either f i or f j . Note that some arguments are both conflict cases and edge cases. All arguments that do not fall into either one of these categories will be referred to as other cases. The 400 arguments for the experiment include 154 conflict cases, 153 edge cases, and 120 other cases. 34 arguments are both conflict cases and edge cases. We chose these arguments based on three criteria. First, we avoided premise pairs that did not co-occur in matrix D but that co-occur in familiar animals that do not belong to D. For example, “is pink” and “has wings” do not co-occur in D but “flamingo” is a familiar animal that has both features. Second, we avoided premise pairs that specified two different numbers of legs—for example, {“has four legs,” “has six legs”}. Finally, we aimed to include roughly equal numbers of conflict cases, edge cases, and other cases. Method. 16 undergraduates participated for course credit. The experiment was carried out using a custom-built computer interface, and one argument was presented on screen at a time. Participants 6 rated the probability of the conclusion on seven point scale where the endpoints were labeled “very unlikely” and “very likely.” The ten arguments for each pair of premises were presented in a block, but the order of these blocks and the order of the arguments within these blocks were randomized across participants. Results. Figure 3 shows average human judgments plotted against the predictions of six models. The plots in the first row include all 400 arguments in the experiment, and the remaining rows show results for conflict cases, edge cases, and other cases. The previous section described four exemplar models, and the two shown in Figure 3 are the best performers overall. Even though the graphical models include more numerical parameters than the exemplar models, recall that these parameters are learned from matrix D rather than fit to the experimental data. Matrix D also serves as the basis for the exemplar models, which means that all of the models can be compared on equal terms. The first row of Figure 3 suggests that the three models which include feature structure F perform better than the alternatives. The output combination model is the worst of the three models that incorporate F, and the correlation achieved by this model is significantly greater than the correlation achieved by the best exemplar model (p < 0.001, using the Fisher transformation to convert correlation coefficients to z scores). Our data therefore suggest that explicit representations of relationships between features are needed to account for inductive inferences about chimeras. The model that includes the feature structure F alone performs better than the two models that combine F with the object structure O, which may not be surprising since Experiment 1 focuses specifically on novel animals that do not slot naturally into structure O. Rows two through four suggest that the conflict arguments in particular raise challenges for the models which do not include feature structure F. Since these conflict cases are arguments f i , f j → f k where f i → f k has strength greater than 0.9 and f j → f k has strength less than 0.1, the first exemplar model averages these strengths and assigns an overall strength of around 0.5 to each argument. The second exemplar model is better able to differentiate between the conflict arguments, but still performs substantially worse than the three models that include structure F. The exemplar models perform better on the edge arguments, but are outperformed by the models that include F. Finally, all models achieve roughly the same level of performance on the other arguments. Although the feature model F performs best overall, the predictions of this model still leave room for improvement. The two most obvious outliers in the third plot in the top row represent the arguments {is blue, lives in desert → lives in woods} and {is pink, lives in desert → lives in woods}. Our participants sensibly infer that any animal which lives in the desert cannot simultaneously live in the woods. In contrast, the Leuven database indicates that eight of the twelve animals that live in the desert also live in the woods, and the edge in Figure 2b between “lives in the desert” and “lives in the woods” therefore represents a positive dependency relationship according to model F. This discrepancy between model and participants reflects the fact that participants made inferences about individual animals but the Leuven database is based on features of animal categories. Note, for example, that any individual animal is unlikely to live in the desert and the woods, but that some animal categories (including snakes, salamanders, and lizards) are found in both environments. 3 Experiment 2: Single-premise arguments Our results so far suggest that inferences about chimeras rely on explicit representations of relationships between features but provide no evidence that relationships between objects are important. It would be a mistake, however, to conclude that relationships between objects play no role in inductive reasoning. Previous studies have used object structures like the example in Figure 2a to account for inferences about novel features [11]—for example, given that alligators have enzyme Y132 in their blood, it seems likely that crocodiles also have this enzyme. Inferences about novel objects can also draw on relationships between objects rather than relationships between features. For example, given that a novel animal has a beak you will probably predict that it has feathers, not because there is any direct dependency between these two features, but because the beaked animals that you know tend to have feathers. Our second experiment explores inferences of this kind. Materials and Method. 32 undergraduates participated for course credit. The task was identical to Experiment 1 with the following exceptions. Each two-premise argument f i , f j → f k from Experiment 1 was converted into two one-premise arguments f i → f k and f j → f k , and these 7 feature F exemplar r = 0.78 7 object O r = 0.54 7 output combination r = 0.75 7 structure combination r = 0.75 7 all 5 5 5 5 5 3 3 3 3 3 1 1 0 edge 0.5 1 r = 0.87 7 1 0 0.5 1 r = 0.87 7 1 0 0.5 1 r = 0.84 7 1 0 0.5 1 r = 0.86 7 0 5 5 5 3 3 3 1 5 3 0.5 r = 0.85 7 5 3 1 1 0 0.5 1 r = 0.79 7 other r = 0.77 7 1 0 0.5 1 r = 0.21 7 1 0 0.5 1 r = 0.74 7 1 0 0.5 1 r = 0.66 7 0 5 5 5 5 3 3 3 3 1 r = 0.73 7 5 0.5 3 1 1 0 0.5 1 1 0 0.5 1 1 0 0.5 1 1 0 0.5 1 0 0.5 1 Figure 4: Argument ratings and model predictions for Experiment 2. one-premise arguments were randomly assigned to two sets. 16 participants rated the 400 arguments in the first set, and the other 16 rated the 400 arguments in the second set. Results. Figure 4 shows average human ratings for the 800 arguments plotted against the predictions of five models. Unlike Figure 3, Figure 4 includes a single exemplar model since there is no need to consider different feature weightings in this case. Unlike Experiment 1, the feature model F performs worse than the other alternatives (p < 0.001 in all cases). Not surprisingly, this model performs relatively well for edge cases f j → f k where f j and f k are linked in Figure 2b, but the final row shows that the model performs poorly across the remaining set of arguments. Taken together, Experiments 1 and 2 suggest that relationships between objects and relationships between features are both needed to account for human inferences. Experiment 1 rules out an exemplar approach but models that combine graph structures over objects and features perform relatively well in both experiments. We considered two methods for combining these structures and both performed equally well. Combining the knowledge captured by these structures appears to be important, and future studies can explore in detail how humans achieve this combination. 4 Conclusion This paper proposed that graphical models are useful for capturing knowledge about animals and their features and showed that a graphical model over features can account for human inferences about chimeras. A family of exemplar models and a graphical model defined over objects were unable to account for our data, which suggests that humans rely on mental representations that explicitly capture dependency relationships between features. Psychologists have previously used graphical models to capture relationships between features, but our work is the first to focus on chimeras and to explore models defined over a large set of familiar features. Although a simple undirected model accounted relatively well for our data, this model is only a starting point. The model incorporates dependency relationships between features, but people know about many specific kinds of dependencies, including cases where one feature causes, enables, prevents, or is inconsistent with another. An undirected graph with only one class of edges cannot capture this knowledge in full, and richer representations will ultimately be needed in order to provide a more complete account of human reasoning. Acknowledgments I thank Madeleine Clute for assisting with this research. This work was supported in part by the Pittsburgh Life Sciences Greenhouse Opportunity Fund and by NSF grant CDI-0835797. 8 References [1] R. N. Shepard. Towards a universal law of generalization for psychological science. Science, 237:1317– 1323, 1987. [2] J. R. Anderson. The adaptive nature of human categorization. Psychological Review, 98(3):409–429, 1991. [3] E. Heit. A Bayesian analysis of some forms of inductive reasoning. In M. Oaksford and N. Chater, editors, Rational models of cognition, pages 248–274. Oxford University Press, Oxford, 1998. [4] J. B. Tenenbaum and T. L. Griffiths. Generalization, similarity, and Bayesian inference. Behavioral and Brain Sciences, 24:629–641, 2001. [5] C. Kemp and J. B. Tenenbaum. Structured statistical models of inductive reasoning. Psychological Review, 116(1):20–58, 2009. [6] D. N. Osherson, E. E. Smith, O. Wilkie, A. Lopez, and E. Shafir. Category-based induction. Psychological Review, 97(2):185–200, 1990. [7] D. J. Navarro. Learning the context of a category. In J. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R.S. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems 23, pages 1795–1803. 2010. [8] C. Kemp, T. L. Griffiths, S. Stromsten, and J. B. Tenenbaum. Semi-supervised learning with trees. In Advances in Neural Information Processing Systems 16, pages 257–264. MIT Press, Cambridge, MA, 2004. [9] B. Rehder. A causal-model theory of conceptual representation and categorization. Journal of Experimental Psychology: Learning, Memory, and Cognition, 29:1141–1159, 2003. [10] B. Rehder and R. Burnett. Feature inference and the causal structure of categories. Cognitive Psychology, 50:264–314, 2005. [11] C. Kemp, P. Shafto, and J. B. Tenenbaum. An integrated account of generalization across objects and features. Cognitive Psychology, in press. [12] S. E. Barrett, H. Abdi, G. L. Murphy, and J. McCarthy Gallagher. Theory-based correlations and their role in children’s concepts. Child Development, 64:1595–1616, 1993. [13] S. A. Sloman, B. C. Love, and W. Ahn. Feature centrality and conceptual coherence. Cognitive Science, 22(2):189–228, 1998. [14] D. Yarlett and M. Ramscar. A quantitative model of counterfactual reasoning. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 123–130. MIT Press, Cambridge, MA, 2002. [15] W. Ahn, J. K. Marsh, C. C. Luhmann, and K. Lee. Effect of theory-based feature correlations on typicality judgments. Memory and Cognition, 30(1):107–118, 2002. [16] D. C. Meehan C. McNorgan, R. A. Kotack and K. McRae. Feature-feature causal relations and statistical co-occurrences in object concepts. Memory and Cognition, 35(3):418–431, 2007. [17] S. De Deyne, S. Verheyen, E. Ameel, W. Vanpaemel, M. J. Dry, W. Voorspoels, and G. Storms. Exemplar by feature applicability matrices and other Dutch normative data for semantic concepts. Behavior Research Methods, 40(4):1030–1048, 2008. [18] J. P. Huelsenbeck and F. Ronquist. MRBAYES: Bayesian inference of phylogenetic trees. Bioinformatics, 17(8):754–755, 2001. [19] M. Schmidt. UGM: A Matlab toolbox for probabilistic undirected graphical models. 2007. Available at http://people.cs.ubc.ca/∼schmidtm/Software/UGM.html. [20] L. J. Nelson and D. T. Miller. The distinctiveness effect in social categorization: you are what makes you unusual. Psychological Science, 6:246–249, 1995. [21] A. L. Patalano, S. Chin-Parker, and B. H. Ross. The importance of being coherent: category coherence, cross-classification and reasoning. Journal of memory and language, 54:407–424, 2006. [22] S. K. Reed. Pattern recognition and categorization. Cognitive Psychology, 3:393–407, 1972. 9
2 0.93130487 193 nips-2011-Object Detection with Grammar Models
Author: Ross B. Girshick, Pedro F. Felzenszwalb, David A. McAllester
Abstract: Compositional models provide an elegant formalism for representing the visual appearance of highly variable objects. While such models are appealing from a theoretical point of view, it has been difficult to demonstrate that they lead to performance advantages on challenging datasets. Here we develop a grammar model for person detection and show that it outperforms previous high-performance systems on the PASCAL benchmark. Our model represents people using a hierarchy of deformable parts, variable structure and an explicit model of occlusion for partially visible objects. To train the model, we introduce a new discriminative framework for learning structured prediction models from weakly-labeled data. 1
same-paper 3 0.91605783 213 nips-2011-Phase transition in the family of p-resistances
Author: Morteza Alamgir, Ulrike V. Luxburg
Abstract: We study the family of p-resistances on graphs for p 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p = 1 the p-resistance coincides with the shortest path distance, for p = 2 it coincides with the standard resistance distance, and for p ! 1 it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase transition takes place. There exist two critical thresholds p⇤ and p⇤⇤ such that if p < p⇤ , then the p-resistance depends on meaningful global properties of the graph, whereas if p > p⇤⇤ , it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p⇤ = 1 + 1/(d 1) and p⇤⇤ = 1 + 1/(d 2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p⇤ and p⇤⇤ is an artifact of our proofs). We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1/p⇤ + 1/q = 1. 1
4 0.90349835 39 nips-2011-Approximating Semidefinite Programs in Sublinear Time
Author: Dan Garber, Elad Hazan
Abstract: In recent years semidefinite optimization has become a tool of major importance in various optimization and machine learning problems. In many of these problems the amount of data in practice is so large that there is a constant need for faster algorithms. In this work we present the first sublinear time approximation algorithm for semidefinite programs which we believe may be useful for such problems in which the size of data may cause even linear time algorithms to have prohibitive running times in practice. We present the algorithm and its analysis alongside with some theoretical lower bounds and an improved algorithm for the special problem of supervised learning of a distance metric. 1
5 0.84841573 139 nips-2011-Kernel Bayes' Rule
Author: Kenji Fukumizu, Le Song, Arthur Gretton
Abstract: A nonparametric kernel-based method for realizing Bayes’ rule is proposed, based on kernel representations of probabilities in reproducing kernel Hilbert spaces. The prior and conditional probabilities are expressed as empirical kernel mean and covariance operators, respectively, and the kernel mean of the posterior distribution is computed in the form of a weighted sample. The kernel Bayes’ rule can be applied to a wide variety of Bayesian inference problems: we demonstrate Bayesian computation without likelihood, and filtering with a nonparametric statespace model. A consistency rate for the posterior estimate is established. 1
6 0.82263875 279 nips-2011-Target Neighbor Consistent Feature Weighting for Nearest Neighbor Classification
7 0.73601943 127 nips-2011-Image Parsing with Stochastic Scene Grammar
8 0.65069383 64 nips-2011-Convergent Bounds on the Euclidean Distance
9 0.62528783 242 nips-2011-See the Tree Through the Lines: The Shazoo Algorithm
10 0.62085831 75 nips-2011-Dynamical segmentation of single trials from population neural data
11 0.61712921 204 nips-2011-Online Learning: Stochastic, Constrained, and Smoothed Adversaries
12 0.60701019 154 nips-2011-Learning person-object interactions for action recognition in still images
13 0.60072172 166 nips-2011-Maximal Cliques that Satisfy Hard Constraints with Application to Deformable Object Model Learning
14 0.58760262 233 nips-2011-Rapid Deformable Object Detection using Dual-Tree Branch-and-Bound
15 0.58733618 231 nips-2011-Randomized Algorithms for Comparison-based Search
16 0.57144696 236 nips-2011-Regularized Laplacian Estimation and Fast Eigenvector Approximation
17 0.56595457 168 nips-2011-Maximum Margin Multi-Instance Learning
18 0.56565988 29 nips-2011-Algorithms and hardness results for parallel large margin learning
19 0.563052 303 nips-2011-Video Annotation and Tracking with Active Learning
20 0.56131095 150 nips-2011-Learning a Distance Metric from a Network