nips nips2011 nips2011-67 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 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. [sent-8, score-0.234]
2 It can also represent arbitrary graph structures in the data. [sent-9, score-0.284]
3 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. [sent-12, score-0.268]
4 However, there has been only limited work on obtaining a general-purpose algorithm to automatically extract skeleton graph structures [2]. [sent-19, score-0.554]
5 In this paper, we present such an algorithm by bringing in a topological concept called the Reeb graph to extract skeleton graphs. [sent-20, score-0.591]
6 Given these data, the goal is to automatically reconstruct the road network, which is a graph embedded in a two- dimensional space. [sent-27, score-0.304]
7 This graph in turn can then be used as a starting point for further processing (such as matching) or inference tasks. [sent-32, score-0.28]
8 Generally, there are a number of scenarios where we wish to extract a one-dimensional skeleton from an input space. [sent-33, score-0.312]
9 The goal in this paper is to develop, as well as to demonstrate the use of, a practical and general algorithm to extract a graph structure from input data of any dimensions. [sent-34, score-0.347]
10 Given a set of points P sampling a hidden domain X, we present a simple and practical algorithm to extract a skeleton graph G for X. [sent-36, score-0.683]
11 The input points P do not have to be embedded – we only need their distance matrix or simply a proximity graph as input to our algorithm. [sent-37, score-0.552]
12 Our algorithm is based on using the so-called Reeb graph to model skeleton graphs. [sent-38, score-0.475]
13 Given a continuous function f : X → IR, the Reeb graph tracks the connected components in the level-set f −1 (a) of f as we vary the value a. [sent-39, score-0.336]
14 By bringing the concept of the Reeb graph to machine learning applications, we can leverage the recent algorithms developed to compute and process Reeb graphs [15, 9]. [sent-42, score-0.345]
15 Moreover, combining the Reeb graph with the so-called Rips complex allows us to obtain theoretical guarantees for our algorithm. [sent-43, score-0.299]
16 Our algorithm always outputs a graph G given data. [sent-46, score-0.255]
17 Hence we can decompose the input data into sets, each corresponding to a single branch in the skeleton graph. [sent-48, score-0.262]
18 We developed an accompanying software to not only extract, but also process skeleton graphs from data. [sent-51, score-0.288]
19 Our algorithm is simple and robust, always extracting a graph from the input. [sent-52, score-0.255]
20 We also demonstrate both the effectiveness of our software and the usefulness of skeleton graphs via a sets of experiments on diverse datasets. [sent-55, score-0.288]
21 In this case, we aim to learn a graph structure, which is simply a one-dimensional stratified space, allowing for simple approaches. [sent-64, score-0.255]
22 Intuitively, principal curves are ”self-consistent” curves that pass through the middle of the data. [sent-66, score-0.264]
23 Original principal curves are simple smooth curves with no self-intersections. [sent-71, score-0.264]
24 e represented principal curves as polygonal lines, and proposed a regularized version of principal curves. [sent-73, score-0.357]
25 This algorithm was later extended in [18] into a principal graph algorithm to compute the skeleton graph of hand-written digits and characters. [sent-75, score-0.856]
26 However, this principal graph algo2 rithm could only handle 2D images. [sent-77, score-0.381]
27 Intuitively, imagining the probability density function as a terrain, their principal curves are the mountain ridges. [sent-79, score-0.195]
28 However, the output of the algorithm is only a collection of points with neither connectivity information, nor the information about which points are junction points (graph nodes) and which points belong to the same arc in the principal graph. [sent-83, score-0.516]
29 [2] recently proposed perhaps the first general algorithm to approximate a hidden metric graph from an input graph with theoretical guarantees. [sent-86, score-0.634]
30 Finally we note that the concept of the Reeb graph has been used in a number of applications in graphics, visualization, and computer vision (see [6] for a survey). [sent-91, score-0.276]
31 An exception is the very recent work[20], where the authors propose to use the Reeb graph for point cloud data and show applications for several data-sets still in 3D. [sent-93, score-0.336]
32 The advantage of our approach is that it is based on the Rips complex, which allows for a general and cleaner Reeb graph reconstruction algorithm with theoretical justification (see [9, 15] and Theorem 3. [sent-94, score-0.277]
33 The Reeb graph of f , denoted by Rf (X), is obtained by continuously identifying every connected component in a level set to a single point. [sent-100, score-0.327]
34 Intuitively, as the value a increases, connected components in the level set f −1 (a) appear, disappear, split and merge, and the Reeb graph of f tracks such changes. [sent-102, score-0.356]
35 Its nodes indicate changes in the connected components in level sets, and each arc represents the evolution of a connected component before it is merged, killed, or split. [sent-104, score-0.221]
36 See the right figure for an example, where we show (an embedding of) the Reeb graph of the height function f defined on a topological torus. [sent-105, score-0.366]
37 The Reeb graph Rf (X) provides a simple yet meaningful abstraction of the input domain X w. [sent-106, score-0.343]
38 Assume the input domain is modeled by a simplicial complex K. [sent-110, score-0.268]
39 Given a PL-function f on K, its Reeb graph Rf (K) is decided by all the 0, 1 and 2-simplices from K, which are the vertices, edges, and triangles of K. [sent-117, score-0.255]
40 3 p p ˜ p ˜ Given a PL function defined on a simplicial com- f p ˜ p ˜ p p p ˜ plex domain K, its Reeb graph can be computed efficiently in O(n log n) expected time by a simp p ˜ p p ˜ ple randomized algorithm [15], where n is the size p p ˜ of K. [sent-119, score-0.437]
41 In fact, the algorithm outputs the so-called p ˜ p p augmented Reeb graph R, which contains the imp ˜ p ˜ p ˜ p ˜ p age of all vertices in K under the surjection map Φ : K → R introduced earlier. [sent-120, score-0.319]
42 See figure on the right: the Reeb graph (middle) is an abstract graph with four nodes, while the augmented Reeb graph (on the right) shows the image of all vertices (i. [sent-121, score-0.829]
43 From the augmented Reeb graph R, we can easily extract junction points (graph nodes), the ˜ set of points from the input data that should be mapped to each graph arc, as well as the connectivity between these points along the Reeb graph (e. [sent-123, score-1.123]
44 The input data we consider can be a set of points sampled from a hidden domain or a probabilistic distribution, or it can be the distance matrix, or simply the proximity graph, among a set of points. [sent-127, score-0.33]
45 ) Our goal is to compute (possibly an embedding of) a skeleton graph from the input data. [sent-129, score-0.543]
46 First, we construct an appropriate space approximating the hidden domain that input points are sampled from. [sent-130, score-0.2]
47 Specifically, given input sampled points P and the distance matrix of P , we first construct a proximity graph based on either r-neighborhood or k-nearest neighbors(NN) information; that is, a point p ∈ P is connected either to all its neighbors within r distance to p, or to its k-NNs. [sent-132, score-0.592]
48 We add all points in P and all edges from this proximity graph to the simplicial complex K we are building. [sent-133, score-0.587]
49 Note that if the proximity graph is already given as the input, then we simply fill in a triangle whenever all its three edges are in the proximity graph to obtain the target simplicial complex K. [sent-135, score-0.884]
50 If the proximity graph is built based on r-neighborhood, then the above construction is simply that of the so-called Vietoris-Rips complex, which has been widely used in manifold reconstruction (especially surface reconstruction) community to recover the hidden domain from its point samples. [sent-138, score-0.529]
51 Furthermore, it has been shown that the Reeb graph of a hidden manifold can be approximated with theoretical guarantees from the Rips complex [9]. [sent-146, score-0.383]
52 Now we have a simplicial complex K that approximates the hidden domain. [sent-148, score-0.237]
53 In order to extract the skeleton graph using the Reeb v graph, we need to define a function g on K that respects its shape. [sent-149, score-0.525]
54 If the underlying domain indeed has a branching filamentary structure, then the geodesic distance to b tends to progress along each filament, and branch out at junction points. [sent-154, score-0.212]
55 See the right figure for an example, where the thin curves are level sets of the geodesic distance function to the base point b. [sent-155, score-0.251]
56 (Left): the augmented Reeb graph output by our algorithm. [sent-158, score-0.302]
57 Since the Reeb graph tracks the evolution of the connected components in the level sets, a branching (splitting in the level set) will happen when the level set passes through point v. [sent-162, score-0.45]
58 In our algorithm, the geodesic distance function g to b in K is approximated by the shortest distance in the proximity graph (i. [sent-163, score-0.481]
59 We then perform the algorithm from [15] to compute the Reeb graph of K with respect to g, and denote the resulting Reeb graph as R. [sent-165, score-0.51]
60 Recall that this algorithm in fact outputs the augmented Reeb graph R. [sent-166, score-0.283]
61 Hence we not only obtain a graph structure, but also the set of input points (together with their connectivity) that are mapped to every graph arc in this graph structure. [sent-167, score-0.94]
62 The time complexity of the basic algorithm is the summation of time to compute (A) the proximity graph, (B) the complex K from the proximity graph, (C) the geodesic distance and (D) the Reeb graph. [sent-169, score-0.334]
63 For high dimensional data sets, this is dominated by the computation of the proximity graph O(n2 ). [sent-174, score-0.352]
64 e, the number of independent loops) of the Reeb graph R f (X) may not reflect that of the given domain X. [sent-177, score-0.301]
65 Intuitively, the theorem states that if the hidden space is a graph G, and if our simplicial complex K approximates G both in terms of topology (as captured by homotopy equivalence) and metric (as captured by the ε-approximation), then the Reeb graph captures all loops in G. [sent-179, score-0.955]
66 1 Suppose K is homotopy equivalent to a graph G, and h : K → G is the corresponding homotopy. [sent-182, score-0.279]
67 Assume that the metric is ε-approximated under h; that is, |d K (x, y)−dG (h(x), h(y))| ≤ ε for any x, y ∈ K, Let R be the Reeb graph of K w. [sent-183, score-0.28]
68 If ε < l/4, where l is the length of the shortest arc in G, we have that there is a one-to-one correspondence between loops in R and loops in G. [sent-186, score-0.268]
69 The above result can be made even stronger: (i) There is not only a one-to-one correspondence between loops in R and in G, the ranges of each pair of corresponding loops are also close. [sent-189, score-0.19]
70 Furthermore, even when ε does not satisfy this condition, the reconstructed Reeb graph R can still preserve all loops in G whose range is larger than 2ε. [sent-195, score-0.376]
71 2 Embedding and Visualization The Reeb graph is an abstract graph. [sent-197, score-0.255]
72 To visualize the skeleton graph, we need to embed it in a reasonable way that reflects the geometry of hidden domain. [sent-198, score-0.277]
73 We then connect projected points based on their connectivity given in the 5 augmented Reeb graph R. [sent-200, score-0.401]
74 Each arc of the Reeb graph is now embedded as a polygonal curve. [sent-201, score-0.397]
75 3 Further Post-processing In practice, data can be noisy, and there may be spurious branches or loops in the Reeb graph R constructed no matter how we choose parameter r or k to decide the scale. [sent-205, score-0.382]
76 Following [3], there is a natural way to define “features” in a Reeb graph and measure their “importance”. [sent-206, score-0.255]
77 Specifically, given a function f : X → IR, imagine we plot its Reeb graph Rf (X) such that the height of each point z ∈ Rf (X) is the function value of all those points in X mapped to z. [sent-207, score-0.377]
78 Now we sweep the Reeb graph bottom-up in increasing order of the function values. [sent-208, score-0.299]
79 As we sweep through a point z, we inspect what happens to the part of Reeb graph that we already swept, denoted by R z := {w ∈ f Rf (X) | f (w) ≤ f (z)}. [sent-209, score-0.324]
80 It turns out that these features (and their sizes) correspond to the so-called extended persistence of the Reeb graph Rf (X) with respect to function f [12]. [sent-223, score-0.318]
81 These features and their persistence can be computed in O(n log 2 n) time, where n is the number of nodes and arcs in the Reeb graph [3]. [sent-225, score-0.357]
82 We can now simplify the Reeb graph by merging features whose persistence value is smaller than a given threshold. [sent-226, score-0.318]
83 Finally, there may also be missing data causing missing links in the constructed skeleton graph. [sent-228, score-0.277]
84 This is achieved by connecting pairs of degree-1 nodes (x, y) in the Reeb graph whose distances d(x, y) is smaller than certain distance threshold. [sent-230, score-0.307]
85 Here d(x, y) is the input distance between x and y (if the input points are embedded, or the distance matrix is given), not the distance in the simplicial complex K constructed by our algorithm. [sent-231, score-0.418]
86 We then present three sets of experiments to demonstrate the effectiveness of our software and show potential applications of skeleton graph extraction for data analysis. [sent-237, score-0.495]
87 We compare our approach with three existing comparable algorithms: (1) the principal graph algorithm (PGA) [18]; (2) the local-density principal curve algorithm (LDPC) [22]; and (3) the metric-graph reconstruction algorithm (MGR) [2]. [sent-239, score-0.565]
88 6 In the figure on the right, we show the skeleton graph of the image of a hand-written Chinese character. [sent-242, score-0.475]
89 However, note that the goal of their algorithm is to approximate a graph metric, which is different from extracting a skeleton graph. [sent-250, score-0.475]
90 For the second set of comparisons we build a skeleton graph out of an input metric graph. [sent-251, score-0.542]
91 The input image web graph is shown in light (gray) color in the background. [sent-255, score-0.297]
92 To be fair, MGR does not provide an embedding, so we should focus on comparing graph structure. [sent-257, score-0.255]
93 In Figure 2 (c), we are given a set of points sampled from a hidden surface model (gray points), and the goal is to extract (sharp) feature curves from it automatically. [sent-268, score-0.231]
94 The right panel shows the graph reconstructed by our algorithm by treating the input simply as a set of points (i. [sent-278, score-0.397]
95 5 −2 Next, we combine three utterances of the digit ‘1’ and construct the graph from the resulting point cloud shown in the left panel. [sent-308, score-0.391]
96 The figure on the right shows a 3D-projection of the Reeb graph constructed by our algorithm. [sent-341, score-0.274]
97 However, it turns out that there are several large loops in the Reeb graph close to the native structure (the conformation with lowest energy). [sent-345, score-0.372]
98 In particular, one way is to use our algorithm to first decompose the input data into different arcs of a graph structure, and then use a principal curve algorithm to compute an embedding of this arc in the center of points contributing to it. [sent-349, score-0.638]
99 Alternatively, we can first use the LDPC algorithm [22] to move points to the center of the data, and then perform our algorithm to connect them into a graph structure. [sent-350, score-0.341]
100 Nonlinear principal component analysis based on principal curves and neural networks. [sent-434, score-0.321]
wordName wordTfidf (topN-words)
[('reeb', 0.801), ('graph', 0.255), ('skeleton', 0.22), ('mgr', 0.149), ('simplicial', 0.136), ('principal', 0.126), ('proximity', 0.097), ('loops', 0.095), ('ldpc', 0.084), ('rf', 0.079), ('arc', 0.078), ('curves', 0.069), ('pga', 0.068), ('unorganized', 0.068), ('geodesic', 0.063), ('hidden', 0.057), ('cloud', 0.056), ('points', 0.055), ('utterance', 0.055), ('cech', 0.054), ('connected', 0.052), ('extract', 0.05), ('graphs', 0.048), ('strati', 0.047), ('domain', 0.046), ('ir', 0.045), ('complex', 0.044), ('sweep', 0.044), ('persistence', 0.044), ('height', 0.042), ('input', 0.042), ('junction', 0.041), ('nautilus', 0.041), ('ozertem', 0.041), ('rips', 0.041), ('skeletonization', 0.041), ('merged', 0.039), ('loop', 0.039), ('vertices', 0.036), ('conformational', 0.036), ('polygonal', 0.036), ('curve', 0.036), ('distance', 0.033), ('utterances', 0.033), ('branches', 0.032), ('connectivity', 0.032), ('connect', 0.031), ('gure', 0.031), ('trajectories', 0.03), ('intuitively', 0.03), ('tracks', 0.029), ('branching', 0.029), ('molecular', 0.029), ('structures', 0.029), ('augmented', 0.028), ('embedded', 0.028), ('manifold', 0.027), ('biasotti', 0.027), ('chazal', 0.027), ('edelsbrunner', 0.027), ('safa', 0.027), ('topology', 0.026), ('embedding', 0.026), ('reconstructed', 0.026), ('gl', 0.025), ('simplex', 0.025), ('metric', 0.025), ('point', 0.025), ('topological', 0.024), ('homology', 0.024), ('homotopy', 0.024), ('lamentary', 0.024), ('shades', 0.024), ('trajectory', 0.023), ('belkin', 0.023), ('geometric', 0.023), ('simulation', 0.023), ('reconstruction', 0.022), ('digit', 0.022), ('native', 0.022), ('base', 0.022), ('road', 0.021), ('yellow', 0.021), ('concept', 0.021), ('divergent', 0.021), ('bringing', 0.021), ('level', 0.02), ('protein', 0.02), ('software', 0.02), ('edge', 0.02), ('arcs', 0.02), ('perturb', 0.02), ('ge', 0.02), ('features', 0.019), ('links', 0.019), ('captured', 0.019), ('missing', 0.019), ('right', 0.019), ('output', 0.019), ('nodes', 0.019)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999994 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.
2 0.0799255 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
3 0.069440112 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.
4 0.066158466 146 nips-2011-Learning Higher-Order Graph Structure with Features by Structure Penalty
Author: Shilin Ding, Grace Wahba, Xiaojin Zhu
Abstract: In discrete undirected graphical models, the conditional independence of node labels Y is specified by the graph structure. We study the case where there is another input random vector X (e.g. observed features) such that the distribution P (Y | X) is determined by functions of X that characterize the (higher-order) interactions among the Y ’s. The main contribution of this paper is to learn the graph structure and the functions conditioned on X at the same time. We prove that discrete undirected graphical models with feature X are equivalent to multivariate discrete models. The reparameterization of the potential functions in graphical models by conditional log odds ratios of the latter offers advantages in representation of the conditional independence structure. The functional spaces can be flexibly determined by kernels. Additionally, we impose a Structure Lasso (SLasso) penalty on groups of functions to learn the graph structure. These groups with overlaps are designed to enforce hierarchical function selection. In this way, we are able to shrink higher order interactions to obtain a sparse graph structure. 1
5 0.064201534 263 nips-2011-Sparse Manifold Clustering and Embedding
Author: Ehsan Elhamifar, René Vidal
Abstract: We propose an algorithm called Sparse Manifold Clustering and Embedding (SMCE) for simultaneous clustering and dimensionality reduction of data lying in multiple nonlinear manifolds. Similar to most dimensionality reduction methods, SMCE finds a small neighborhood around each data point and connects each point to its neighbors with appropriate weights. The key difference is that SMCE finds both the neighbors and the weights automatically. This is done by solving a sparse optimization problem, which encourages selecting nearby points that lie in the same manifold and approximately span a low-dimensional affine subspace. The optimal solution encodes information that can be used for clustering and dimensionality reduction using spectral clustering and embedding. Moreover, the size of the optimal neighborhood of a data point, which can be different for different points, provides an estimate of the dimension of the manifold to which the point belongs. Experiments demonstrate that our method can effectively handle multiple manifolds that are very close to each other, manifolds with non-uniform sampling and holes, as well as estimate the intrinsic dimensions of the manifolds. 1 1.1
6 0.063799344 71 nips-2011-Directed Graph Embedding: an Algorithm based on Continuous Limits of Laplacian-type Operators
7 0.062610954 31 nips-2011-An Application of Tree-Structured Expectation Propagation for Channel Decoding
8 0.059318364 296 nips-2011-Uniqueness of Belief Propagation on Signed Graphs
9 0.055522364 199 nips-2011-On fast approximate submodular minimization
10 0.055521313 195 nips-2011-On Learning Discrete Graphical Models using Greedy Methods
11 0.053122044 166 nips-2011-Maximal Cliques that Satisfy Hard Constraints with Application to Deformable Object Model Learning
12 0.052662633 150 nips-2011-Learning a Distance Metric from a Network
13 0.048407041 63 nips-2011-Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
14 0.046804715 274 nips-2011-Structure Learning for Optimization
15 0.046034519 248 nips-2011-Semi-supervised Regression via Parallel Field Regularization
16 0.045696229 76 nips-2011-Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials
17 0.043050218 98 nips-2011-From Bandits to Experts: On the Value of Side-Observations
18 0.04138843 142 nips-2011-Large-Scale Sparse Principal Component Analysis with Application to Text Data
19 0.040344715 186 nips-2011-Noise Thresholds for Spectral Clustering
20 0.039900661 247 nips-2011-Semantic Labeling of 3D Point Clouds for Indoor Scenes
topicId topicWeight
[(0, 0.118), (1, 0.033), (2, -0.035), (3, -0.007), (4, -0.017), (5, -0.027), (6, -0.092), (7, -0.007), (8, 0.057), (9, -0.085), (10, -0.008), (11, 0.019), (12, -0.005), (13, -0.06), (14, 0.031), (15, 0.032), (16, 0.023), (17, 0.003), (18, -0.036), (19, 0.008), (20, -0.04), (21, 0.097), (22, -0.005), (23, 0.08), (24, 0.024), (25, -0.06), (26, -0.049), (27, -0.053), (28, -0.037), (29, 0.042), (30, -0.015), (31, -0.03), (32, -0.03), (33, 0.116), (34, -0.023), (35, -0.022), (36, -0.061), (37, 0.011), (38, -0.019), (39, -0.075), (40, 0.117), (41, 0.007), (42, -0.004), (43, -0.014), (44, -0.06), (45, -0.0), (46, 0.046), (47, -0.014), (48, -0.048), (49, -0.043)]
simIndex simValue paperId paperTitle
same-paper 1 0.93366414 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.
2 0.72077811 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.
3 0.71952593 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.64578205 146 nips-2011-Learning Higher-Order Graph Structure with Features by Structure Penalty
Author: Shilin Ding, Grace Wahba, Xiaojin Zhu
Abstract: In discrete undirected graphical models, the conditional independence of node labels Y is specified by the graph structure. We study the case where there is another input random vector X (e.g. observed features) such that the distribution P (Y | X) is determined by functions of X that characterize the (higher-order) interactions among the Y ’s. The main contribution of this paper is to learn the graph structure and the functions conditioned on X at the same time. We prove that discrete undirected graphical models with feature X are equivalent to multivariate discrete models. The reparameterization of the potential functions in graphical models by conditional log odds ratios of the latter offers advantages in representation of the conditional independence structure. The functional spaces can be flexibly determined by kernels. Additionally, we impose a Structure Lasso (SLasso) penalty on groups of functions to learn the graph structure. These groups with overlaps are designed to enforce hierarchical function selection. In this way, we are able to shrink higher order interactions to obtain a sparse graph structure. 1
5 0.62396967 296 nips-2011-Uniqueness of Belief Propagation on Signed Graphs
Author: Yusuke Watanabe
Abstract: While loopy Belief Propagation (LBP) has been utilized in a wide variety of applications with empirical success, it comes with few theoretical guarantees. Especially, if the interactions of random variables in a graphical model are strong, the behaviors of the algorithm can be difficult to analyze due to underlying phase transitions. In this paper, we develop a novel approach to the uniqueness problem of the LBP fixed point; our new “necessary and sufficient” condition is stated in terms of graphs and signs, where the sign denotes the types (attractive/repulsive) of the interaction (i.e., compatibility function) on the edge. In all previous works, uniqueness is guaranteed only in the situations where the strength of the interactions are “sufficiently” small in certain senses. In contrast, our condition covers arbitrary strong interactions on the specified class of signed graphs. The result of this paper is based on the recent theoretical advance in the LBP algorithm; the connection with the graph zeta function.
6 0.62144655 31 nips-2011-An Application of Tree-Structured Expectation Propagation for Channel Decoding
7 0.59347719 150 nips-2011-Learning a Distance Metric from a Network
8 0.59338802 71 nips-2011-Directed Graph Embedding: an Algorithm based on Continuous Limits of Laplacian-type Operators
9 0.56461459 236 nips-2011-Regularized Laplacian Estimation and Fast Eigenvector Approximation
10 0.54683864 195 nips-2011-On Learning Discrete Graphical Models using Greedy Methods
11 0.49959955 130 nips-2011-Inductive reasoning about chimeric creatures
12 0.49620208 47 nips-2011-Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts
13 0.47933719 274 nips-2011-Structure Learning for Optimization
14 0.47814348 167 nips-2011-Maximum Covariance Unfolding : Manifold Learning for Bimodal Data
15 0.44626904 5 nips-2011-A Denoising View of Matrix Completion
16 0.4393256 81 nips-2011-Efficient anomaly detection using bipartite k-NN graphs
17 0.43728366 263 nips-2011-Sparse Manifold Clustering and Embedding
18 0.41633928 60 nips-2011-Confidence Sets for Network Structure
19 0.40346229 158 nips-2011-Learning unbelievable probabilities
20 0.40162629 7 nips-2011-A Machine Learning Approach to Predict Chemical Reactions
topicId topicWeight
[(0, 0.025), (4, 0.051), (20, 0.037), (26, 0.024), (31, 0.078), (33, 0.033), (43, 0.074), (45, 0.116), (56, 0.269), (57, 0.041), (60, 0.018), (65, 0.019), (74, 0.044), (83, 0.032), (99, 0.036)]
simIndex simValue paperId paperTitle
1 0.87739193 34 nips-2011-An Unsupervised Decontamination Procedure For Improving The Reliability Of Human Judgments
Author: Michael C. Mozer, Benjamin Link, Harold Pashler
Abstract: Psychologists have long been struck by individuals’ limitations in expressing their internal sensations, impressions, and evaluations via rating scales. Instead of using an absolute scale, individuals rely on reference points from recent experience. This relativity of judgment limits the informativeness of responses on surveys, questionnaires, and evaluation forms. Fortunately, the cognitive processes that map stimuli to responses are not simply noisy, but rather are influenced by recent experience in a lawful manner. We explore techniques to remove sequential dependencies, and thereby decontaminate a series of ratings to obtain more meaningful human judgments. In our formulation, the problem is to infer latent (subjective) impressions from a sequence of stimulus labels (e.g., movie names) and responses. We describe an unsupervised approach that simultaneously recovers the impressions and parameters of a contamination model that predicts how recent judgments affect the current response. We test our iterated impression inference, or I3 , algorithm in three domains: rating the gap between dots, the desirability of a movie based on an advertisement, and the morality of an action. We demonstrate significant objective improvements in the quality of the recovered impressions. 1
2 0.82627797 60 nips-2011-Confidence Sets for Network Structure
Author: David S. Choi, Patrick J. Wolfe, Edoardo M. Airoldi
Abstract: Latent variable models are frequently used to identify structure in dichotomous network data, in part because they give rise to a Bernoulli product likelihood that is both well understood and consistent with the notion of exchangeable random graphs. In this article we propose conservative confidence sets that hold with respect to these underlying Bernoulli parameters as a function of any given partition of network nodes, enabling us to assess estimates of residual network structure, that is, structure that cannot be explained by known covariates and thus cannot be easily verified by manual inspection. We demonstrate the proposed methodology by analyzing student friendship networks from the National Longitudinal Survey of Adolescent Health that include race, gender, and school year as covariates. We employ a stochastic expectation-maximization algorithm to fit a logistic regression model that includes these explanatory variables as well as a latent stochastic blockmodel component and additional node-specific effects. Although maximumlikelihood estimates do not appear consistent in this context, we are able to evaluate confidence sets as a function of different blockmodel partitions, which enables us to qualitatively assess the significance of estimated residual network structure relative to a baseline, which models covariates but lacks block structure. 1
3 0.76221699 121 nips-2011-Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Author: Benjamin Recht, Christopher Re, Stephen Wright, Feng Niu
Abstract: Stochastic Gradient Descent (SGD) is a popular algorithm that can achieve stateof-the-art performance on a variety of machine learning tasks. Several researchers have recently proposed schemes to parallelize SGD, but all require performancedestroying memory locking and synchronization. This work aims to show using novel theoretical analysis, algorithms, and implementation that SGD can be implemented without any locking. We present an update scheme called H OGWILD ! which allows processors access to shared memory with the possibility of overwriting each other’s work. We show that when the associated optimization problem is sparse, meaning most gradient updates only modify small parts of the decision variable, then H OGWILD ! achieves a nearly optimal rate of convergence. We demonstrate experimentally that H OGWILD ! outperforms alternative schemes that use locking by an order of magnitude. 1
same-paper 4 0.72340477 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.
5 0.59428984 122 nips-2011-How Do Humans Teach: On Curriculum Learning and Teaching Dimension
Author: Faisal Khan, Bilge Mutlu, Xiaojin Zhu
Abstract: We study the empirical strategies that humans follow as they teach a target concept with a simple 1D threshold to a robot.1 Previous studies of computational teaching, particularly the teaching dimension model and the curriculum learning principle, offer contradictory predictions on what optimal strategy the teacher should follow in this teaching task. We show through behavioral studies that humans employ three distinct teaching strategies, one of which is consistent with the curriculum learning principle, and propose a novel theoretical framework as a potential explanation for this strategy. This framework, which assumes a teaching goal of minimizing the learner’s expected generalization error at each iteration, extends the standard teaching dimension model and offers a theoretical justification for curriculum learning. 1
6 0.58870935 280 nips-2011-Testing a Bayesian Measure of Representativeness Using a Large Image Database
7 0.57274818 15 nips-2011-A rational model of causal inference with continuous causes
8 0.57190979 35 nips-2011-An ideal observer model for identifying the reference frame of objects
9 0.56799442 1 nips-2011-$\theta$-MRF: Capturing Spatial and Semantic Structure in the Parameters for Scene Understanding
10 0.56700307 258 nips-2011-Sparse Bayesian Multi-Task Learning
11 0.56576979 231 nips-2011-Randomized Algorithms for Comparison-based Search
12 0.56569755 180 nips-2011-Multiple Instance Filtering
13 0.56465447 227 nips-2011-Pylon Model for Semantic Segmentation
14 0.56397992 159 nips-2011-Learning with the weighted trace-norm under arbitrary sampling distributions
15 0.56325644 186 nips-2011-Noise Thresholds for Spectral Clustering
16 0.56072605 276 nips-2011-Structured sparse coding via lateral inhibition
17 0.56061977 156 nips-2011-Learning to Learn with Compound HD Models
18 0.56044155 149 nips-2011-Learning Sparse Representations of High Dimensional Data on Large Scale Dictionaries
19 0.56043059 118 nips-2011-High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity
20 0.56007582 84 nips-2011-EigenNet: A Bayesian hybrid of generative and conditional models for sparse learning