nips nips2001 nips2001-118 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Marcello Pelillo
Abstract: Motivated by our recent work on rooted tree matching, in this paper we provide a solution to the problem of matching two free (i.e., unrooted) trees by constructing an association graph whose maximal cliques are in one-to-one correspondence with maximal common subtrees. We then solve the problem using simple replicator dynamics from evolutionary game theory. Experiments on hundreds of uniformly random trees are presented. The results are impressive: despite the inherent inability of these simple dynamics to escape from local optima, they always returned a globally optimal solution.
Reference: text
sentIndex sentText sentNum sentScore
1 it Abstract Motivated by our recent work on rooted tree matching, in this paper we provide a solution to the problem of matching two free (i. [sent-3, score-0.403]
2 , unrooted) trees by constructing an association graph whose maximal cliques are in one-to-one correspondence with maximal common subtrees. [sent-5, score-0.963]
3 We then solve the problem using simple replicator dynamics from evolutionary game theory. [sent-6, score-0.601]
4 Experiments on hundreds of uniformly random trees are presented. [sent-7, score-0.203]
5 The results are impressive: despite the inherent inability of these simple dynamics to escape from local optima, they always returned a globally optimal solution. [sent-8, score-0.262]
6 1 Introduction Graph matching is a classic problem in computer vision and pattern recognition, instances of which arise in areas as diverse as object recognition, motion and stereo analysis [1]. [sent-9, score-0.173]
7 , [2, 11, 19]) the graphs at hand have a peculiar structure: they are connected and acyclic, i. [sent-12, score-0.078]
8 Note that, unlike “rooted” trees, in free trees there is no distinguished node playing the role of the root, and hence no hierarchy is imposed on them. [sent-15, score-0.324]
9 Standard graph matching techniques, such as [8], yield solutions that are not constrained to preserve connectedness and hence cannot be applied to free trees. [sent-16, score-0.457]
10 A classic approach to solving the graph matching problem consists of transforming it into the equivalent problem of finding a maximum clique in an auxiliary graph structure, known as the association graph [1]. [sent-17, score-1.252]
11 This framework is attractive because it casts graph matching as a pure graph-theoretic problem, for which a solid theory and powerful algorithms have been developed. [sent-18, score-0.305]
12 Note that, although the maximum clique problem is known to be hard, powerful heuristics exist which efficiently find good approximate solutions [4]. [sent-19, score-0.512]
13 ¡ ¢ Motivated by our recent work on rooted tree matching [15], in this paper we propose a solution to the free tree matching problem by providing a straightforward way of deriving an association graph from two free trees. [sent-20, score-1.019]
14 We prove that in the new formulation there is a one-to-one correspondence between maximal (maximum) cliques in the derived association graph and maximal (maximum) subtree isomorphisms. [sent-21, score-1.13]
15 As an obvious corollary, the computational complexity of finding a maximum clique in such graphs is therefore the same as the subtree isomorphism problem, which is known to be polynomial in the number of nodes [7]. [sent-22, score-1.365]
16 Following [13, 15], we use a recent generalization of the Motzkin-Straus theorem [12] to formulate the maximum clique problem as a quadratic programming problem. [sent-23, score-0.606]
17 To (approximately) solve it we employ replicator equations, a class of simple continuous- and discretetime dynamical systems developed and studied in evolutionary game theory [10, 17]. [sent-24, score-0.565]
18 The results are impressive: despite the counter-intuitive maximum clique formulation of the tree matching problem, and the inherent inability of these simple dynamics to escape from local optima, they always found a globally optimal solution. [sent-26, score-1.023]
19 2 Subtree isomorphisms and maximal cliques © wxq v u q w ui xq v ¡ § £ ¥tsq r § £ CYSGVg phCY SGVg U fe ¡ VdE@TU HHP@I GF£ SED@ RCPBQ A H" 1 cbQ `a1 "YP@P@@ 7 XW I @ 3 8 1 §§ 79 ¡ 431 0 5432¦0£)¡ '(& ! [sent-27, score-0.303]
20 1 " #¤ %$" 6 ¥ ¥ ©¨§§ ¦¥¤¢ ¥ £ ¡ Let be a graph, where is the set of nodes and is the set of (undirected) edges. [sent-28, score-0.15]
21 The order of is the number of nodes in , while its size is the number of edges. [sent-29, score-0.15]
22 Two nodes are said to be adjacent (denoted ) if they are connected by an edge. [sent-30, score-0.269]
23 The adjacency matrix of is the symmetric matrix defined as if otherwise The degree of a node , denoted , is the number of nodes adjacent to it. [sent-31, score-0.419]
24 A path is such that for all , ; in this any sequence of distinct nodes case, the length of the path is . [sent-32, score-0.352]
25 A graph is said to be connected if any two nodes are joined by a path. [sent-34, score-0.414]
26 The distance between two nodes and , denoted by , is the length of the shortest path joining them (by convention , if there is no such path). [sent-35, score-0.343]
27 Given a subset of nodes , the induced is the graph having as its node set, and two nodes are adjacent in subgraph if and only if they are adjacent in . [sent-36, score-0.626]
28 A connected graph with no cycles is called a free tree, or simply a tree. [sent-37, score-0.286]
29 One which turns out to be very useful for our characterization is that in a tree any two nodes are connected by a unique path. [sent-39, score-0.29]
30 Any bijection , with and , is called a subtree isomorphism if it preserves both the adjacency relationships between the nodes and the connectedness of the matched subgraphs. [sent-41, score-0.971]
31 A subtree isomorphism addition, the induced subgraphs is maximal if there is no other subtree isomorphism with a strict subset of , and maximum if has largest cardinality. [sent-43, score-1.739]
32 The maximal (maximum) subtree isomorphism problem is to find a maximal (maximum) subtree isomorphism between two trees. [sent-44, score-1.704]
33 Despite name similarity, we are not addressing the so-called subtree isomorphism problem, which consists of determining whether a given tree is isomorphic to a subtree of a larger one. [sent-46, score-1.172]
34 In fact, we are dealing with a generalization thereof, the maximum common subtree problem, which consists of determining the largest isomorphic subtrees of two given trees. [sent-47, score-0.498]
35 We shall continue to use our own terminology, however, as it emphasizes the role of the isomorphism . [sent-48, score-0.32]
36 A subset of vertices of is said to be a clique if all its nodes are mutually adjacent. [sent-51, score-0.674]
37 A maximal clique is one which is not contained in any larger clique, while a maximum clique is a clique having largest cardinality. [sent-52, score-1.543]
38 The maximum clique problem is to find a maximum clique of . [sent-53, score-1.024]
39 The following theorem, which is the basis of the work reported here, establishes a one-toone correspondence between the maximum subtree isomorphism problem and the maximum clique problem. [sent-54, score-1.362]
40 Theorem 1 Any maximal (maximum) subtree isomorphism between two trees induces a maximal (maximum) clique in the corresponding FTAG, and vice versa. [sent-55, score-1.638]
41 Q c £ £ 2a ¡ q faS ¥ r ¡q Q ny ¡q Q Y CG£S § a hFg¢2aFg $ §f £ £ ¡ § £ Q £ § £ ¢ ¥¤ $ r¡ bYHGS ar£y ¡ ¡ q Q ©X8£h¥§ ¢ be a maximal subtree isomorphism between trees denote the corresponding FTAG. [sent-56, score-1.028]
42 From the definition of a subtree isomorphism it follows that maps the path between any two nodes onto the path joining and . [sent-58, score-1.084]
43 Trivially, is a maximal clique because is maximal, and this proves the first part of the theorem. [sent-60, score-0.61]
44 Let and , and let is a maximal clique of , and let and . [sent-63, score-0.668]
45 From the definition of the FTAG and the hypothesis that is a clique, it for all is simple to see that is a one-to-one and onto correspondence between and , which trivially preserves the adjacency relationships between nodes. [sent-65, score-0.188]
46 The fact that is a maximal isomorphism is a straightforward consequence of the maximality of . [sent-66, score-0.535]
47 Suppose by contradiction that this is not the case, and let be two nodes which are not joined by a path in . [sent-70, score-0.31]
48 Since both and are nodes of , however, there must exist a path joining them in . [sent-71, score-0.32]
49 Let , for some , be a node on this path which is not in . [sent-72, score-0.159]
50 Moreover, let be the -th node on the path which joins and in (remember that , and hence ). [sent-73, score-0.188]
51 It is easy to show that the set is a clique, thereby contradicting the hypothesis that is a maximal clique. [sent-74, score-0.189]
52 This can be proved by exploiting the obvious fact that if is a node on the path joining any two nodes and , then . [sent-75, score-0.405]
53 , the socalled distance matrix which, for an arbitrary graph of order , is the matrix where , the distance between nodes and . [sent-82, score-0.426]
54 Note also that the distance matrix of a graph can easily be constructed from its adjacency matrix . [sent-84, score-0.349]
55 In fact, denoting by the -th entry of the matrix , the -th power of , we have that equals the least for which (there must be such an since a tree is connected). [sent-85, score-0.138]
56 Given a subset of vertices of , we will denote by its characteristic vector which is the point in defined as 8 ¡ 8 8 § ( 8 ' & 8 ¨#8£ ' ¦ ¡ 7 q qdpW § q § 79 6 ¡ 1 ¤ ¥£ ¤ ¢ q ¤ ¤ q U6 where denotes the cardinality of if otherwise . [sent-87, score-0.149]
57 Now, consider the following quadratic function (3) £ 13 a0g¡ ' & is the adjacency matrix of . [sent-88, score-0.165]
58 The following theorem, recently proved where by Bomze [3], expands on the Motzkin-Straus theorem [12], a remarkable result which establishes a connection between the maximum clique problem and quadratic programming. [sent-89, score-0.66]
59 8 ¨8 U6 '¦ q q Theorem 2 Let be a subset of vertices of a graph , and let be its characteristic vector. [sent-90, score-0.309]
60 Then, is a maximal (maximum) clique of if and only if is a local (global) maximizer in . [sent-91, score-0.748]
61 Moreover, all local (and hence global) maximizers of in are strict and are characteristic vectors of maximal cliques of . [sent-92, score-0.548]
62 U6 '¦ © Unlike the original Motzkin-Straus formulation, which is plagued by the presence of “spuon rious” solutions [14], the previous result guarantees us that all maximizers of are strict, and are characteristic vectors of maximal/maximum cliques in . [sent-93, score-0.258]
63 In a formal sense, therefore, a one-to-one correspondence exists between maximal cliques and local maximizers of in on the one hand, and maximum cliques and global maximizers on the other hand. [sent-94, score-0.784]
64 U H6 ' ¦ U6 '¦ We now turn our attention to a class of simple dynamical systems that we use for solving our quadratic optimization problem. [sent-95, score-0.092]
65 U3 & X ( £V Y£1 Y£V ¡ 7 1 1 where (5) (6) Both (4) and (5) are called replicator equations in evolutionary game theory, since they are used to model evolution over time of relative frequencies of interacting, self-replicating entities [10, 17]. [sent-99, score-0.573]
66 It is readily seen that the simplex is invariant under these dynamics, which means that every trajectory starting in will remain in for all future times, and their stationary points coincide. [sent-100, score-0.081]
67 U R6 U U 6 6 We are now interested in the dynamical properties of replicator dynamics; it is these properties that will allow us to solve our original tree matching problem. [sent-101, score-0.654]
68 8 8 i ¡ Theorem 3 If then the function is strictly increasing along any nonconstant trajectory under both continuous-time (4) and discrete-time (5) replicator dynamics. [sent-105, score-0.375]
69 Finally, a vector is asymptotically stable under (4) and (5) if and only if is a strict local maximizer of on . [sent-107, score-0.209]
70 U H6 8 U 6 R8 $8 8 In light of their dynamical properties, replicator equations naturally suggest themselves as a simple heuristic for solving the maximal subtree isomorphism problem. [sent-108, score-1.292]
71 Indeed, let and be two free trees, and let denote the adjacency matrix of their FTAG . [sent-109, score-0.28]
72 As stated in Theorem 1, this will in turn induce a maximal subtree isomorphism between and . [sent-111, score-0.882]
73 Clearly, in theory there is no guarantee that the converged solution will be a global maximizer of , and therefore that it will induce a maximum isomorphism between the two original trees, but see below. [sent-112, score-0.604]
74 ' ¦ Hy '¦ Qy Recently, there has been much interest around the following exponential version of replicator equations, which arises as a model of evolution guided by imitation [9, 10, 17]: © ¨ ¦ ¤ ¥§¥£ § 7 (8) ©§¤ £ ¦ Y£ 3 Q "! [sent-113, score-0.451]
75 As tends to 0, the orbits of this dynamics approach those of the standard, “first-order” replicator model (4), slowed down by the factor ; moreover, for large values of the model approximates the so-called “best-reply” dynamics [9, 10]. [sent-115, score-0.536]
76 3 ¡ Y 1£ U & X 7 ( 1£ From a computational perspective, exponential replicator dynamics are particularly attractive as they may be considerably faster and even more accurate than the standard, first-order model (see [13] and the experiments reported in the next section). [sent-121, score-0.496]
77 A hundred 100-node free trees were generated uniformly at random using a procedure described by Wilf in [18]. [sent-125, score-0.266]
78 , percentage of node deletion) were used, namely 2%, 10%, 20%, 30% and 40%. [sent-129, score-0.114]
79 This means that the order of the pruned trees ranged from 98 to 60. [sent-130, score-0.176]
80 Overall, therefore, 500 pairs of trees were obtained, for each of which the corresponding FTAG was constructed as described in Section 2. [sent-131, score-0.176]
81 To keep the order of the association graph as low as possible, its vertex set was constructed as follows: © ¥ ¥ § ¤ xGkfPDB A ¡HGVPDC d# d xkar7)¥ ¤ ¤ ¤ £ £ B A ¥ ¥ § £ ¢ ¡¤ assuming , the edge set being defined as in (2). [sent-132, score-0.251]
82 It is straightforward to see that when the first tree is isomorphic to a subtree of the second, Theorem 1 continues to hold. [sent-133, score-0.535]
83 Both the discrete-time first-order dynamics (5) and its exponential counterpart (9) (with ) were used. [sent-136, score-0.181]
84 The algorithms were started from the simplex barycenter and stopped ) was found or the distance when either a maximal clique (i. [sent-137, score-0.685]
85 , a local maximizer of between two successive points was smaller than a fixed threshold. [sent-139, score-0.138]
86 , the ratio between the cardinality of the clique found and the order of the smaller subtree, and then we averaged. [sent-145, score-0.448]
87 Figure 1(a) shows the results obtained using the linear dynamics (5) as a function of the corruption level. [sent-146, score-0.189]
88 As can be seen, the algorithm was always able to find a correct maximum isomorphism, i. [sent-147, score-0.114]
89 In Figure 2, the results pertaining to the exponential dynamics (8) are shown. [sent-151, score-0.125]
90 Before concluding, we note that our approach can easily be extended to tackle the problem of matching attributed (free) trees. [sent-154, score-0.19]
91 In this case, the attributes result in weights being placed on the nodes of the association graph, and a conversion of the maximum clique problem to a maximum weight clique problem [15, 5]. [sent-155, score-1.267]
92 Moreover, it is straightforward to formulate errortolerant versions of our framework along the lines suggested in [16] for rooted attributed trees, where many-to-many node correspondences are allowed. [sent-156, score-0.191]
93 Finally, we think that the results presented in this paper (together with those reported in [13, 15]) raise intriguing questions concerning the connections between (standard) notions of computational complexity and the “elusiveness” of global optima in continuous settings. [sent-158, score-0.104]
94 Figure 1: Results obtained over 100-node random trees with various levels of corruption, using the first-order dynamics (5). [sent-207, score-0.271]
95 Bottom: Average computational time taken by the replicator equations. [sent-209, score-0.346]
96 Maxima for graphs and a new proof of a theorem of Tur´ n. [sent-261, score-0.101]
97 Figure 2: Results obtained over 100-node random trees with various levels of corruption, using the exponential dynamics (9) with . [sent-266, score-0.301]
98 Bottom: Average computational time taken by the replicator equations. [sent-268, score-0.346]
99 Feasible and infeasible maxima in a quadratic program for maximum clique. [sent-276, score-0.15]
100 Many-to-many matching of attributed trees using association graphs and game dynamics. [sent-295, score-0.565]
wordName wordTfidf (topN-words)
[('clique', 0.421), ('replicator', 0.346), ('subtree', 0.343), ('isomorphism', 0.32), ('maximal', 0.189), ('trees', 0.176), ('graph', 0.158), ('ftag', 0.151), ('nodes', 0.15), ('matching', 0.147), ('cliques', 0.114), ('pelillo', 0.113), ('maximizer', 0.108), ('tree', 0.102), ('path', 0.101), ('adjacency', 0.096), ('dynamics', 0.095), ('corruption', 0.094), ('evolutionary', 0.094), ('association', 0.093), ('maximum', 0.091), ('free', 0.09), ('maximizers', 0.087), ('vg', 0.075), ('hy', 0.075), ('strict', 0.071), ('joining', 0.069), ('game', 0.066), ('bomze', 0.065), ('rooted', 0.064), ('isomorphic', 0.064), ('theorem', 0.061), ('dynamical', 0.059), ('node', 0.058), ('characteristic', 0.057), ('counterpart', 0.056), ('percentage', 0.056), ('simplex', 0.052), ('optima', 0.051), ('pw', 0.048), ('yk', 0.047), ('sg', 0.045), ('correspondence', 0.044), ('adjacent', 0.043), ('cy', 0.043), ('imitation', 0.043), ('lvg', 0.043), ('pardalos', 0.043), ('secs', 0.043), ('siddiqi', 0.043), ('venezia', 0.043), ('attributed', 0.043), ('cpu', 0.043), ('vertices', 0.041), ('graphs', 0.04), ('connected', 0.038), ('said', 0.038), ('connectedness', 0.038), ('subgraphs', 0.038), ('matrix', 0.036), ('equations', 0.035), ('qw', 0.034), ('quadratic', 0.033), ('bq', 0.032), ('escape', 0.032), ('inability', 0.032), ('evolution', 0.032), ('hg', 0.031), ('induce', 0.03), ('terminology', 0.03), ('joined', 0.03), ('local', 0.03), ('exponential', 0.03), ('trajectory', 0.029), ('let', 0.029), ('global', 0.028), ('hundreds', 0.027), ('establishes', 0.027), ('cardinality', 0.027), ('converged', 0.027), ('proved', 0.027), ('classic', 0.026), ('maxima', 0.026), ('despite', 0.026), ('straightforward', 0.026), ('perturbed', 0.025), ('fg', 0.025), ('di', 0.025), ('reported', 0.025), ('preserves', 0.024), ('subset', 0.024), ('de', 0.024), ('constrained', 0.024), ('inherent', 0.024), ('trivially', 0.024), ('structures', 0.024), ('nition', 0.024), ('correct', 0.023), ('distance', 0.023), ('globally', 0.023)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000005 118 nips-2001-Matching Free Trees with Replicator Equations
Author: Marcello Pelillo
Abstract: Motivated by our recent work on rooted tree matching, in this paper we provide a solution to the problem of matching two free (i.e., unrooted) trees by constructing an association graph whose maximal cliques are in one-to-one correspondence with maximal common subtrees. We then solve the problem using simple replicator dynamics from evolutionary game theory. Experiments on hundreds of uniformly random trees are presented. The results are impressive: despite the inherent inability of these simple dynamics to escape from local optima, they always returned a globally optimal solution.
2 0.19355595 190 nips-2001-Thin Junction Trees
Author: Francis R. Bach, Michael I. Jordan
Abstract: We present an algorithm that induces a class of models with thin junction trees—models that are characterized by an upper bound on the size of the maximal cliques of their triangulated graph. By ensuring that the junction tree is thin, inference in our models remains tractable throughout the learning process. This allows both an efficient implementation of an iterative scaling parameter estimation algorithm and also ensures that inference can be performed efficiently with the final model. We illustrate the approach with applications in handwritten digit recognition and DNA splice site detection.
3 0.18244298 189 nips-2001-The g Factor: Relating Distributions on Features to Distributions on Images
Author: James M. Coughlan, Alan L. Yuille
Abstract: We describe the g-factor, which relates probability distributions on image features to distributions on the images themselves. The g-factor depends only on our choice of features and lattice quantization and is independent of the training image data. We illustrate the importance of the g-factor by analyzing how the parameters of Markov Random Field (i.e. Gibbs or log-linear) probability models of images are learned from data by maximum likelihood estimation. In particular, we study homogeneous MRF models which learn image distributions in terms of clique potentials corresponding to feature histogram statistics (d. Minimax Entropy Learning (MEL) by Zhu, Wu and Mumford 1997 [11]) . We first use our analysis of the g-factor to determine when the clique potentials decouple for different features . Second, we show that clique potentials can be computed analytically by approximating the g-factor. Third, we demonstrate a connection between this approximation and the Generalized Iterative Scaling algorithm (GIS), due to Darroch and Ratcliff 1972 [2], for calculating potentials. This connection enables us to use GIS to improve our multinomial approximation, using Bethe-Kikuchi[8] approximations to simplify the GIS procedure. We support our analysis by computer simulations. 1
4 0.11895403 56 nips-2001-Convolution Kernels for Natural Language
Author: Michael Collins, Nigel Duffy
Abstract: We describe the application of kernel methods to Natural Language Processing (NLP) problems. In many NLP tasks the objects being modeled are strings, trees, graphs or other discrete structures which require some mechanism to convert them into feature vectors. We describe kernels for various natural language structures, allowing rich, high dimensional representations of these structures. We show how a kernel over trees can be applied to parsing using the voted perceptron algorithm, and we give experimental results on the ATIS corpus of parse trees.
5 0.089398377 105 nips-2001-Kernel Machines and Boolean Functions
Author: Adam Kowalczyk, Alex J. Smola, Robert C. Williamson
Abstract: We give results about the learnability and required complexity of logical formulae to solve classification problems. These results are obtained by linking propositional logic with kernel machines. In particular we show that decision trees and disjunctive normal forms (DNF) can be represented by the help of a special kernel, linking regularized risk to separation margin. Subsequently we derive a number of lower bounds on the required complexity of logic formulae using properties of algorithms for generation of linear estimators, such as perceptron and maximal perceptron learning.
6 0.085637242 192 nips-2001-Tree-based reparameterization for approximate inference on loopy graphs
7 0.081248999 34 nips-2001-Analog Soft-Pattern-Matching Classifier using Floating-Gate MOS Technology
8 0.078847617 169 nips-2001-Small-World Phenomena and the Dynamics of Information
9 0.076098517 115 nips-2001-Linear-time inference in Hierarchical HMMs
10 0.071454093 149 nips-2001-Probabilistic Abstraction Hierarchies
11 0.07056208 52 nips-2001-Computing Time Lower Bounds for Recurrent Sigmoidal Neural Networks
12 0.066144377 188 nips-2001-The Unified Propagation and Scaling Algorithm
13 0.06560979 110 nips-2001-Learning Hierarchical Structures with Linear Relational Embedding
14 0.065278105 89 nips-2001-Grouping with Bias
15 0.062960386 106 nips-2001-Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
16 0.061570667 193 nips-2001-Unsupervised Learning of Human Motion Models
17 0.049134526 165 nips-2001-Scaling Laws and Local Minima in Hebbian ICA
18 0.047919326 187 nips-2001-The Steering Approach for Multi-Criteria Reinforcement Learning
19 0.046203569 32 nips-2001-An Efficient, Exact Algorithm for Solving Tree-Structured Graphical Games
20 0.045209523 178 nips-2001-TAP Gibbs Free Energy, Belief Propagation and Sparsity
topicId topicWeight
[(0, -0.156), (1, -0.006), (2, 0.014), (3, -0.02), (4, -0.012), (5, -0.146), (6, -0.109), (7, -0.054), (8, -0.092), (9, 0.002), (10, -0.095), (11, -0.124), (12, 0.118), (13, 0.043), (14, -0.011), (15, -0.061), (16, -0.232), (17, 0.237), (18, -0.021), (19, -0.037), (20, -0.117), (21, -0.013), (22, -0.009), (23, 0.077), (24, -0.115), (25, 0.16), (26, -0.02), (27, -0.021), (28, 0.083), (29, 0.182), (30, 0.158), (31, -0.036), (32, 0.106), (33, -0.086), (34, -0.075), (35, 0.065), (36, 0.145), (37, -0.061), (38, 0.078), (39, 0.016), (40, -0.044), (41, 0.035), (42, -0.08), (43, 0.053), (44, -0.015), (45, 0.066), (46, 0.031), (47, -0.039), (48, -0.116), (49, -0.025)]
simIndex simValue paperId paperTitle
same-paper 1 0.96706468 118 nips-2001-Matching Free Trees with Replicator Equations
Author: Marcello Pelillo
Abstract: Motivated by our recent work on rooted tree matching, in this paper we provide a solution to the problem of matching two free (i.e., unrooted) trees by constructing an association graph whose maximal cliques are in one-to-one correspondence with maximal common subtrees. We then solve the problem using simple replicator dynamics from evolutionary game theory. Experiments on hundreds of uniformly random trees are presented. The results are impressive: despite the inherent inability of these simple dynamics to escape from local optima, they always returned a globally optimal solution.
2 0.6569494 190 nips-2001-Thin Junction Trees
Author: Francis R. Bach, Michael I. Jordan
Abstract: We present an algorithm that induces a class of models with thin junction trees—models that are characterized by an upper bound on the size of the maximal cliques of their triangulated graph. By ensuring that the junction tree is thin, inference in our models remains tractable throughout the learning process. This allows both an efficient implementation of an iterative scaling parameter estimation algorithm and also ensures that inference can be performed efficiently with the final model. We illustrate the approach with applications in handwritten digit recognition and DNA splice site detection.
3 0.63712633 189 nips-2001-The g Factor: Relating Distributions on Features to Distributions on Images
Author: James M. Coughlan, Alan L. Yuille
Abstract: We describe the g-factor, which relates probability distributions on image features to distributions on the images themselves. The g-factor depends only on our choice of features and lattice quantization and is independent of the training image data. We illustrate the importance of the g-factor by analyzing how the parameters of Markov Random Field (i.e. Gibbs or log-linear) probability models of images are learned from data by maximum likelihood estimation. In particular, we study homogeneous MRF models which learn image distributions in terms of clique potentials corresponding to feature histogram statistics (d. Minimax Entropy Learning (MEL) by Zhu, Wu and Mumford 1997 [11]) . We first use our analysis of the g-factor to determine when the clique potentials decouple for different features . Second, we show that clique potentials can be computed analytically by approximating the g-factor. Third, we demonstrate a connection between this approximation and the Generalized Iterative Scaling algorithm (GIS), due to Darroch and Ratcliff 1972 [2], for calculating potentials. This connection enables us to use GIS to improve our multinomial approximation, using Bethe-Kikuchi[8] approximations to simplify the GIS procedure. We support our analysis by computer simulations. 1
4 0.46494111 169 nips-2001-Small-World Phenomena and the Dynamics of Information
Author: Jon M. Kleinberg
Abstract: unkown-abstract
5 0.41334403 149 nips-2001-Probabilistic Abstraction Hierarchies
Author: Eran Segal, Daphne Koller, Dirk Ormoneit
Abstract: Many domains are naturally organized in an abstraction hierarchy or taxonomy, where the instances in “nearby” classes in the taxonomy are similar. In this paper, we provide a general probabilistic framework for clustering data into a set of classes organized as a taxonomy, where each class is associated with a probabilistic model from which the data was generated. The clustering algorithm simultaneously optimizes three things: the assignment of data instances to clusters, the models associated with the clusters, and the structure of the abstraction hierarchy. A unique feature of our approach is that it utilizes global optimization algorithms for both of the last two steps, reducing the sensitivity to noise and the propensity to local maxima that are characteristic of algorithms such as hierarchical agglomerative clustering that only take local steps. We provide a theoretical analysis for our algorithm, showing that it converges to a local maximum of the joint likelihood of model and data. We present experimental results on synthetic data, and on real data in the domains of gene expression and text.
6 0.39509502 192 nips-2001-Tree-based reparameterization for approximate inference on loopy graphs
7 0.39422905 56 nips-2001-Convolution Kernels for Natural Language
8 0.35968336 110 nips-2001-Learning Hierarchical Structures with Linear Relational Embedding
9 0.35410362 193 nips-2001-Unsupervised Learning of Human Motion Models
10 0.3040964 105 nips-2001-Kernel Machines and Boolean Functions
11 0.30396649 99 nips-2001-Intransitive Likelihood-Ratio Classifiers
12 0.29890984 115 nips-2001-Linear-time inference in Hierarchical HMMs
13 0.29257154 90 nips-2001-Hyperbolic Self-Organizing Maps for Semantic Navigation
14 0.28572154 120 nips-2001-Minimax Probability Machine
15 0.28218994 34 nips-2001-Analog Soft-Pattern-Matching Classifier using Floating-Gate MOS Technology
16 0.28153074 106 nips-2001-Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
17 0.25992092 89 nips-2001-Grouping with Bias
18 0.25757974 76 nips-2001-Fast Parameter Estimation Using Green's Functions
19 0.23997538 188 nips-2001-The Unified Propagation and Scaling Algorithm
20 0.23283887 165 nips-2001-Scaling Laws and Local Minima in Hebbian ICA
topicId topicWeight
[(14, 0.042), (17, 0.017), (19, 0.032), (27, 0.11), (30, 0.08), (38, 0.019), (59, 0.03), (68, 0.3), (72, 0.062), (79, 0.067), (83, 0.041), (91, 0.108)]
simIndex simValue paperId paperTitle
1 0.81695998 90 nips-2001-Hyperbolic Self-Organizing Maps for Semantic Navigation
Author: Jorg Ontrup, Helge Ritter
Abstract: We introduce a new type of Self-Organizing Map (SOM) to navigate in the Semantic Space of large text collections. We propose a “hyperbolic SOM” (HSOM) based on a regular tesselation of the hyperbolic plane, which is a non-euclidean space characterized by constant negative gaussian curvature. The exponentially increasing size of a neighborhood around a point in hyperbolic space provides more freedom to map the complex information space arising from language into spatial relations. We describe experiments, showing that the HSOM can successfully be applied to text categorization tasks and yields results comparable to other state-of-the-art methods.
same-paper 2 0.81496751 118 nips-2001-Matching Free Trees with Replicator Equations
Author: Marcello Pelillo
Abstract: Motivated by our recent work on rooted tree matching, in this paper we provide a solution to the problem of matching two free (i.e., unrooted) trees by constructing an association graph whose maximal cliques are in one-to-one correspondence with maximal common subtrees. We then solve the problem using simple replicator dynamics from evolutionary game theory. Experiments on hundreds of uniformly random trees are presented. The results are impressive: despite the inherent inability of these simple dynamics to escape from local optima, they always returned a globally optimal solution.
3 0.81136698 17 nips-2001-A Quantitative Model of Counterfactual Reasoning
Author: Daniel Yarlett, Michael Ramscar
Abstract: In this paper we explore two quantitative approaches to the modelling of counterfactual reasoning – a linear and a noisy-OR model – based on information contained in conceptual dependency networks. Empirical data is acquired in a study and the fit of the models compared to it. We conclude by considering the appropriateness of non-parametric approaches to counterfactual reasoning, and examining the prospects for other parametric approaches in the future.
4 0.54751265 13 nips-2001-A Natural Policy Gradient
Author: Sham M. Kakade
Abstract: We provide a natural gradient method that represents the steepest descent direction based on the underlying structure of the parameter space. Although gradient methods cannot make large changes in the values of the parameters, we show that the natural gradient is moving toward choosing a greedy optimal action rather than just a better action. These greedy optimal actions are those that would be chosen under one improvement step of policy iteration with approximate, compatible value functions, as defined by Sutton et al. [9]. We then show drastic performance improvements in simple MDPs and in the more challenging MDP of Tetris. 1
5 0.5448786 56 nips-2001-Convolution Kernels for Natural Language
Author: Michael Collins, Nigel Duffy
Abstract: We describe the application of kernel methods to Natural Language Processing (NLP) problems. In many NLP tasks the objects being modeled are strings, trees, graphs or other discrete structures which require some mechanism to convert them into feature vectors. We describe kernels for various natural language structures, allowing rich, high dimensional representations of these structures. We show how a kernel over trees can be applied to parsing using the voted perceptron algorithm, and we give experimental results on the ATIS corpus of parse trees.
6 0.54059958 162 nips-2001-Relative Density Nets: A New Way to Combine Backpropagation with HMM's
7 0.53866661 29 nips-2001-Adaptive Sparseness Using Jeffreys Prior
8 0.53825945 27 nips-2001-Activity Driven Adaptive Stochastic Resonance
9 0.53783 131 nips-2001-Neural Implementation of Bayesian Inference in Population Codes
10 0.53773201 95 nips-2001-Infinite Mixtures of Gaussian Process Experts
12 0.53609359 161 nips-2001-Reinforcement Learning with Long Short-Term Memory
13 0.53579617 77 nips-2001-Fast and Robust Classification using Asymmetric AdaBoost and a Detector Cascade
14 0.53436589 132 nips-2001-Novel iteration schemes for the Cluster Variation Method
15 0.53428996 63 nips-2001-Dynamic Time-Alignment Kernel in Support Vector Machine
16 0.53426063 190 nips-2001-Thin Junction Trees
17 0.53269362 8 nips-2001-A General Greedy Approximation Algorithm with Applications
18 0.53261334 121 nips-2001-Model-Free Least-Squares Policy Iteration
19 0.53208613 46 nips-2001-Categorization by Learning and Combining Object Parts
20 0.5313257 102 nips-2001-KLD-Sampling: Adaptive Particle Filters