In order to develop statistical methods for shapes with a tree-structure, we construct a shape space framework for tree-like shapes and study metrics on the shape space. This shape space has singularities, corresponding to topological transitions in the represented trees. We study two closely related metrics on the shape space, TED and QED. QED is a quotient Euclidean distance arising naturally from the shape space formulation, while TED is the classical tree edit distance. Using Gromov's metric geometry we gain new insight into the geometries defined by TED and QED. We show that the new metric QED has nice geometric properties which facilitate statistical analysis, such as existence and local uniqueness of geodesics and averages. TED, on the other hand, does not share the geometric advantages of QED, but has nice algorithmic properties. We provide a theoretical framework and experimental results on synthetic data trees as well as airway trees from pulmonary CT scans. This way, we effectively illustrate that our framework has both the theoretical and qualitative properties necessary to build a theory of statistical tree-shape analysis.
Statistics on tree-shaped objects receive growing interest in the statistical community. Wang and Marron @cite_18 study metric spaces of trees and define a notion of average tree called the median-mean as well as a version of PCA, which finds modes of variation in terms of , encoding the maximum amount of structural and attributal variation. @cite_6 extend this work by finding efficient algorithms for PCA. This is applied to analysis of brain blood vessels. The metric defined by Wang and Marron does not give a natural geodesic structure on the space of trees, as it places a large emphasis on the tree-topological structure of the trees. The metric has discontinuities in the sense that a sequence of trees with a shrinking branch will not converge to a tree that does not have that branch. Such a metric is not suitable for studying trees with continuous topological variations and noise, such as anatomical tree-structures extracted from medical images, since the emphasis on topology makes the metric sensitive to structural noise.
@cite_18 @cite_6
2102364524 1968399077 2124577064 2768461089 2142420687 2570705339 2259676875 1753705553 2962693999 2964083604 2153419563 2060425093 1982648068 2592698424 1952648253 2017262458 2093171982 1599871777 2789787607 1973011883
In order to develop statistical methods for shapes with a tree-structure, we construct a shape space framework for treelike shapes and study metrics on the shape space. The shape space has singularities, which correspond to topological transitions in the represented trees. We study two closely related metrics, TED and QED. The QED is a quotient euclidean distance arising from the new shape space formulation, while TED is essentially the classical tree edit distance. Using Gromov's metric geometry we gain new insight into the geometries defined by TED and QED. In particular, we show that the new metric QED has nice geometric properties which facilitate statistical analysis, such as existence and local uniqueness of geodesics and averages. TED, on the other hand, has algorithmic advantages, while it does not share the geometric strongpoints of QED. We provide a theoretical framework as well as computational results such as matching of airway trees from pulmonary CT scans and geodesics between synthetic data trees illustrating the dynamic and geometric properties of the QED metric. We study distorted metrics on binary trees in the context of phylogenetic reconstruction. Given a binary tree T on n leaves with a path metric d, consider the pairwise distances d(u,v) between leaves. It is well known that these determine the tree and the d length of all edges. Here, we consider distortions @math of d such that, for all leaves u and v, it holds that @math if either d(u,v)< M + f 2 or @math , where d satisfies f ≤ d(e) ≤ g for all edges e. Given such distortions, we show how to reconstruct in polynomial time a forest T1, ... ,Tα such that the true tree T may be obtained from that forest by adding α-1 edges and α-1 ≤ 2-Ω(M g) n. Our distorted metric result implies a reconstruction algorithm of phylogenetic forests with a small number of trees from sequences of length logarithmic in the number of species. The reconstruction algorithm is applicable for the general Markov model. Both the distorted metric result and its applications to phylogeny are almost tight. Given dissimilarity data on pairs of objects in a set, we study the problem of fitting a tree metric to this data so as to minimize additive error (i.e. some measure of the difference between the tree metric and the given data). This problem arises in constructing an M-level hierarchical clustering of objects (or an ultrametric on objects) so as to match the given dissimilarity data - a basic problem in statistics. Viewed in this way, the problem is a generalization of the correlation clustering problem (which corresponds to M = 1). We give a very simple randomized combinatorial algorithm for the M-level hierarchical clustering problem that achieves an approximation ratio of M+2. This is a generalization of a previous factor 3 algorithm for correlation clustering on complete graphs. The problem of fitting tree metrics also arises in phylogeny where the objective is to learn the evolution tree by fitting a tree to dissimilarity data on taxa. The quality of the fit is measured by taking the l sub p norm of the difference between the tree metric constructed and the given data. Previous results obtained a factor 3 approximation for finding the closest tree tree metric under the l spl infin norm. No nontrivial approximation for general l sub p norms was known before. We present a novel LP formulation for this problem and obtain an O((log n log log n) sup 1 p ) approximation using this. Enroute, we obtain an O((log n log log n) sup 1 p ) approximation for the closest ultrametric under the l sub p norm. Our techniques are based on representing and viewing an ultrametric as a hierarchy of clusterings, and may be useful in other contexts. In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the result of Bartal who gave a bound of O(log n log log n). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Ω(log n)-distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems. We introduce a novel measure called e-four-pointscondition (e-4PC), which assigns a value e ∈ [0,1] to every metric space quantifying how close the metric is to a tree metric. Data-sets taken from real Internet measurements indicate remarkable closeness of Internet latencies to tree metrics based on this condition. We study embeddings of e-4PC metric spaces into trees and prove tight upper and lower bounds. Specifically, we show that there are constants c1 and c2 such that, (1) every metric (X,d) which satisfies the e-4PC can be embedded into a tree with distortion (1+e)c1log|X|, and (2) for every e ∈: [0,1] and any number of nodes, there is a metric space (X,d) satisfying the e-4PC that does not embed into a tree with distortion less than (1+e)c2log|X|. In addition, we prove a lower bound on approximate distance labelings of e-4PC metrics, and give tight bounds for tree embeddings with additive error guarantees. This paper addresses the basic question of how well a tree can approximate distances of a metric space or a graph. Given a graph, the problem of constructing a spanning tree in a graph which strongly preserves distances in the graph is a fundamental problem in network design. We present scaling distortion embeddings where the distortion scales as a function of @math , with the guarantee that for each @math simultaneously, the distortion of a fraction @math of all pairs is bounded accordingly. Quantitatively, we prove that any finite metric space embeds into an ultrametric with scaling distortion @math . For the graph setting, we prove that any weighted graph contains a spanning tree with scaling distortion @math . These bounds are tight even for embedding into arbitrary trees. These results imply that the average distortion of the embedding is constant and that the @math distortion is @math . For probabilistic embedding into spanning trees we prove a scaling distortion of @math , which implies constant @math -distortion for every fixed @math . A prominent tool in many problems involving metric spaces is a notion of randomized low-diameter decomposition. Loosely speaking, ( )-decomposition refers to a probability distribution over partitions of the metric into sets of low diameter, such that nearby points (parameterized by ( >0 )) are likely to be “clustered” together. Applying this notion to the shortest-path metric in edge-weighted graphs, it is known that n-vertex graphs admit an (O( n) )-padded decomposition (Bartal, 37th annual symposium on foundations of computer science. IEEE, pp 184–193, 1996), and that excluded-minor graphs admit O(1)-padded decomposition (, 25th annual ACM symposium on theory of computing, pp 682–690, 1993; Fakcharoenphol and Talwar, J Comput Syst Sci 69(3), 485–497, 2004; , Proceedings of the 46th annual ACM symposium on theory of computing. STOC ’14, pp 79–88. ACM, New York, NY, USA, 2014). We design decompositions to the family of p-path-separable graphs, which was defined by Abraham and Gavoille (Proceedings of the twenty-fifth annual acm symposium on principles of distributed computing, PODC ’06, pp 188–197, 2006) and refers to graphs that admit vertex-separators consisting of at most p shortest paths in the graph. Our main result is that every p-path-separable n-vertex graph admits an (O( (p n)) )-decomposition, which refines the (O( n) ) bound for general graphs, and provides new bounds for families like bounded-treewidth graphs. Technically, our clustering process differs from previous ones by working in (the shortest-path metric of) carefully chosen subgraphs. New representations of tree-structured data objects, using ideas from topological data analysis, enable improved statistical analyses of a population of brain artery trees. A number of representations of each data tree arise from persistence diagrams that quantify branching and looping of vessels at multiple scales. Novel approaches to the statistical analysis, through various summaries of the persistence diagrams, lead to heightened correlations with covariates such as age and sex, relative to earlier analyses of this data set. The correlation with age continues to be signicant even after controlling for correlations from earlier signicant summaries. Statistical phylogenetic inference methods use tree rearrangement operations such as subtree–prune–regraft (SPR) to perform Markov chain Monte Carlo (MCMC) across tree topologies. The structure of the graph induced by tree rearrangement operations is an important determinant of the mixing properties of MCMC, motivating the study of the underlying SPR graph in greater detail. In this paper, we investigate the SPR graph of rooted trees (rSPR graph) in a new way: by calculating the Ricci–Ollivier curvature with respect to uniform and Metropolis–Hastings random walks. This value quantifies the degree to which a pair of random walkers from specified points move towards each other; negative curvature means that they move away from one another on average, while positive curvature means that they move towards each other. In order to calculate this curvature, we develop fast new algorithms for rSPR graph computation. We then develop formulas characterizing how the number of rSPR neighbors of a tree changes after an rSPR operation is applied to that tree. These give bounds on the curvature, as well as a flatness-in-the-limit theorem indicating that paths of small topology changes are easy to traverse. However, we find that large topology changes (i.e. moving a large subtree) give pairs of trees with negative curvature. We show using simulation that mean access time distributions depend on distance, degree, and curvature, demonstrating the relevance of these results to stochastic tree search. The metric Ramsey problem asks for the largest subset S of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor [MN07] devised the so called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems. In this paper we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of Ramsey Spanning Trees. We ask for the largest subset S ⊆ V of a given graph G = (V, E), such that there exists a spanning tree of G that has small stretch for S. Applied iteratively, this provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to all other vertices. The union of these trees serves as a special type of spanner, a tree-padding spanner. We use this spanner to devise the first compact stateless routing scheme with O(1) routing decision time, and labels which are much shorter than in all currently existing schemes. We first revisit the metric Ramsey problem, and provide a new deterministic construction. We prove that for every k, any n-point metric space has a subset S of size at least n1--1 k which embeds into an ultrametric with distortion 8k. We use this result to obtain the state-of-the-art deterministic construction of a distance oracle. Building on this result, we prove that for every k, any n-vertex graph G = (V, E) has a subset S of size at least n1--1 k, and a spanning tree of G, that has stretch O(k log log n) between any point in S and any point in V. We introduce an approach to learn discriminative visual representations while exploiting external semantic knowledge about object category relationships. Given a hierarchical taxonomy that captures semantic similarity between the objects, we learn a corresponding tree of metrics (ToM). In this tree, we have one metric for each non-leaf node of the object hierarchy, and each metric is responsible for discriminating among its immediate subcategory children. Specifically, a Mahalanobis metric learned for a given node must satisfy the appropriate (dis)similarity constraints generated only among its subtree members' training instances. To further exploit the semantics, we introduce a novel regularizer coupling the metrics that prefers a sparse disjoint set of features to be selected for each metric relative to its ancestor (supercategory) nodes' metrics. Intuitively, this reflects that visual cues most useful to distinguish the generic classes (e.g., feline vs. canine) should be different than those cues most useful to distinguish their component fine-grained classes (e.g., Persian cat vs. Siamese cat). We validate our approach with multiple image datasets using the WordNet taxonomy, show its advantages over alternative metric learning approaches, and analyze the meaning of attribute features selected by our algorithm. Abstract A metric on general phylogenetic trees is presented. This extends the work of most previous authors, who constructed metrics for binary trees. The metric presented in this paper makes possible the comparison of the many nonbinary phylogenetic trees appearing in the literature. This provides an objective procedure for comparing the different methods for constructing phylogenetic trees. The metric is based on elementary operations which transform one tree into another. Various results obtained in applying these operations are given. They enable the distance between any pair of trees to be calculated efficiently. This generalizes previous work by Bourque to the case where interior vertices can be labeled, and labels may contain more than one element or may be empty. The mean is often the most important statistic of a dataset as it provides a single point that summarizes the entire set. While the mean is readily defined and computed in Euclidean spaces, no commonly accepted solutions are currently available in more complicated spaces, such as spaces of tree-structured data. In this paper we study the notion of means, both generally in Gromov's CAT(0)-spaces (metric spaces of non-positive curvature), but also specifically in the space of tree-like shapes. We prove local existence and uniqueness of means in such spaces and discuss three different algorithms for computing means. We make an experimental evaluation of the three algorithms through experiments on three different sets of data with tree-like structure: a synthetic dataset, a leaf morphology dataset from images, and a set of human airway subtrees from medical CT scans. This experimental study provides great insight into the behavior of the different methods and how they relate to each other. More importantly, it also provides mathematically well-founded, tractable and robust “average trees”. This statistic is of utmost importance due to the ever-presence of tree-like structures in human anatomy, e.g., airways and vascularization systems. Inferential summaries of tree estimates are useful in the setting of evolutionary biology, where phylogenetic trees have been built from DNA data since the 1960s. In bioinformatics, psychometrics, and data mining, hierarchical clustering techniques output the same mathematical objects, and practitioners have similar questions about the stability and “generalizability” of these summaries. This article describes the implementation of the geometric distance between trees developed by Billera, Holmes, and Vogtmann (2001) equally applicable to phylogenetic trees and hierarchical clustering trees, and shows some of the applications in evaluating tree estimates. In particular, since (2001) have shown that the space of trees is negatively curved (called a CAT(0) space), a collection of trees can naturally be represented as a tree. We compare this representation to the Euclidean approximations of treespace made available through both a classical multidimensional scaling and a Kernel multidimensional... Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution spl mu on them such that the expected stretch of any edge of G in a tree chosen according to spl mu is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming. The real trees form a class of metric spaces that extends the class of trees with edge lengths by allowing behavior such as infinite total edge length and vertices with infinite branching degree. We use Dirichlet form methods to construct Brownian motion on any given locally compact R-tree (T,r) equipped with a Radon measure ν on (T,B(T)). We specify a criterion under which the Brownian motion is recurrent or transient. For compact recurrent R-trees we provide bounds on the mixing time. We introduce and study the notion of the average distortion of a nonexpanding embedding of one metric space into another. Less sensitive than the multiplicative metric distortion, the average distortion captures well the global picture, and, overall, is a quite interesting new measure of metric proximity, related to the concentration of measure phenomenon. We establish close mutual relations between the MinCut- MaxFlow gap in a uniform-demand multicommodity flow, and the average distortion of embedding the suitable (dual) metric into l1. These relations are exploited to show that the shortest-path metrics of special (e.g., planar, bounded treewidth, etc.) graphs embed into l1 with constant average distortion. The main result of the paper claims that this remains true even if l1 is replaced with the line. This result is further sharpened for graphs of a bounded treewidth. Breiman (2001a,b) has recently developed an ensemble classification and regression approach that displayed outstanding performance with regard prediction error on a suite of benchmark datasets. As the base constituents of the ensemble are tree-structured predictors, and since each of these is constructed using an injection of randomness, the method is called ‘random forests’. That the exceptional performance is attained with seemingly only a single tuning parameter, to which sensitivity is minimal, makes the methodology all the more remarkable. The individual trees comprising the forest are all grown to maximal depth. While this helps with regard bias, there is the familiar tradeoff with variance. However, these variability concerns were potentially obscured because of an interesting feature of those benchmarking datasets extracted from the UCI machine learning repository for testing: all these datasets are hard to overfit using tree-structured methods. This raises issues about the scope of the repository. With this as motivation, and coupled with experience from boosting methods, we revisit the formulation of random forests and investigate prediction performance on real-world and simulated datasets for which maximally sized trees do overfit. These explorations reveal that gains can be realized by additional tuning to regulate tree size via limiting the number of splits and or the size of nodes for which splitting is allowed. Nonetheless, even in these settings, good performance for random forests can be attained by using larger (than default) primary tuning parameter values. There are many metrics available to compare phylogenetic trees since this is a fundamental task in computational biology. In this paper, we focus on one such metric, the l∞-cophenetic metric introduced by This metric works by representing a phylogenetic tree with n labeled leaves as a point in ( R ^ n(n+1) 2 ) known as the cophenetic vector, then comparing the two resulting Euclidean points using the l∞ distance. Meanwhile, the interleaving distance is a formal categorical construction generalized from the definition of , originally introduced to compare persistence modules arising from the field of topological data analysis. We show that the l∞-cophenetic metric is an example of an interleaving distance. To do this, we define phylogenetic trees as a category of merge trees with some additional structure, namely, labelings on the leaves plus a requirement that morphisms respect these labels. Then we can use the definition of a flow on this category to give an interleaving distance. Finally, we show that, because of the additional structure given by the categories defined, the map sending a labeled merge tree to the cophenetic vector is, in fact, an isometric embedding, thus proving that the l∞-cophenetic metric is an interleaving distance. Phylogenetic analysis of DNA or other data commonly gives rise to a collection or sample of inferred evolutionary trees. Principal Components Analysis (PCA) cannot be applied directly to collections of trees since the space of evolutionary trees on a fixed set of taxa is not a vector space. This paper describes a novel geometrical approach to PCA in tree-space that constructs the first principal path in an analogous way to standard linear Euclidean PCA. Given a data set of phylogenetic trees, a geodesic principal path is sought that maximizes the variance of the data under a form of projection onto the path. Due to the high dimensionality of tree-space and the nonlinear nature of this problem, the computational complexity is potentially very high, so approximate optimization algorithms are used to search for the optimal path. Principal paths identified in this way reveal and quantify the main sources of variation in the original collection of trees in terms of both topology and branch lengths. The approach is illustrated by application to simulated sets of trees and to a set of gene trees from metazoan (animal) species.