An official website of the United States government
A decision tree recursively splits a feature space Rd and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine- learning toolkit for decades. A large body of work treats heuristic algorithms to compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space. We show that it can be solved in O(n2d+1d) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f (d) · no(d/ log d) running time, where n is the number of training examples. The problem is solvable in (dR)O(dR) · n1+o(1) time, if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.
more »
« less
Simultaneous Drawing of Layered Trees
We study the crossing-minimization problem in a layered graph drawing of planar-embedded rooted trees whose leaves have a given total order on the first layer, which adheres to the embedding of each individual tree. The task is then to permute the vertices on the other layers (respecting the given tree embeddings) in order to minimize the number of crossings. While this problem is known to be NP-hard for multiple trees even on just two layers, we describe a dynamic program running in polynomial time for the restricted case of two trees. If there are more than two trees, we restrict the number of layers to three, which allows for a reduction to a shortest-path problem. This way, we achieve XP-time in the number of trees.
more »
« less
- Award ID(s):
- 2212130
- PAR ID:
- 10493396
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- 18th International Conference and Workshop on Algorithms and Computation (WALCOM)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Parallel computing algorithms benefit from in- creases in concurrency when the hardware capacity is being under utilized. For likelihood-based molecular evolution in- ferences this can be due to small problem sizes, or because hardware capacity has increased beyond dataset sizes. A central concept in this domain is a bifurcating tree, which represents evolutionary relationships. The topology of the tree being evaluated directly affects the degree of parallelism that can be exploited by likelihood-based algorithms. For time-reversible evolutionary models we can reroot an unbalanced tree in order to make it more symmetric, without affecting the likelihood. Based on the reduction in number of concurrent operation sets, we define a best-case theoretical expectations, based on tree size and topology, for speedup due to rerooting which approaches 2-fold as the number of tip nodes increases for pectinate trees, and much higher values for some random topologies as the number of tip nodes increases. Empirical results using the NVIDIA CUDA implementation of the BEAGLE library confirm the merit of this approach. For pectinate trees we observe speedups of up to 1.93-fold due to rerooting and even larger speedups for random trees for the core likelihood-evaluation function in BEAGLE.more » « less
-
One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits. Reproducibility: Our source code and data are available at https://github.com/cameton/HPEC2022_ContractionTrees.more » « less
-
One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits. Reproducibility: Our source code and data are available at https://github.com/cameton/HPEC2022_ContractionTrees.more » « less
-
One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits. Reproducibility: Our source code and data are available at https://github.com/cameton/HPEC2022 ContractionTrees.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-981-97-0566-5_5
