skip to main content


Title: A Better Decision Tree: The Max-Cut Decision Tree with Modified PCA Improves Accuracy and Running Time
Abstract

Decision trees are a widely used method for classification, both alone and as the building blocks of multiple different ensemble learning methods. The Max Cut decision tree introduced here involves novel modifications to a standard, baseline variant of a classification decision tree, CART Gini. One modification involves an alternative splitting metric, Max Cut, based on maximizing the distance between all pairs of observations that belong to separate classes and separate sides of the threshold value. The other modification, Node Means PCA, selects the decision feature from a linear combination of the input features constructed using an adjustment to principal component analysis (PCA) locally at each node. Our experiments show that this node-based, localized PCA with the Max Cut splitting metric can dramatically improve classification accuracy while also significantly decreasing computational time compared to the CART Gini decision tree. These improvements are most significant for higher-dimensional datasets. For the example dataset CIFAR-100, the modifications enabled a 49% improvement in accuracy, relative to CART Gini, while providing a$$6.8 \times$$6.8×speed up compared to the Scikit-Learn implementation of CART Gini. These introduced modifications are expected to dramatically advance the capabilities of decision trees for difficult classification tasks.

 
more » « less
Award ID(s):
1760102 2112533
NSF-PAR ID:
10368165
Author(s) / Creator(s):
;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
SN Computer Science
Volume:
3
Issue:
4
ISSN:
2661-8907
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    We study the structure of the Liouville quantum gravity (LQG) surfaces that are cut out as one explores a conformal loop-ensemble$$\hbox {CLE}_{\kappa '}$$CLEκfor$$\kappa '$$κin (4, 8) that is drawn on an independent$$\gamma $$γ-LQG surface for$$\gamma ^2=16/\kappa '$$γ2=16/κ. The results are similar in flavor to the ones from our companion paper dealing with$$\hbox {CLE}_{\kappa }$$CLEκfor$$\kappa $$κin (8/3, 4), where the loops of the CLE are disjoint and simple. In particular, we encode the combined structure of the LQG surface and the$$\hbox {CLE}_{\kappa '}$$CLEκin terms of stable growth-fragmentation trees or their variants, which also appear in the asymptotic study of peeling processes on decorated planar maps. This has consequences for questions that do a priori not involve LQG surfaces: In our paper entitled “CLE Percolations” described the law of interfaces obtained when coloring the loops of a$$\hbox {CLE}_{\kappa '}$$CLEκindependently into two colors with respective probabilitiespand$$1-p$$1-p. This description was complete up to one missing parameter$$\rho $$ρ. The results of the present paper about CLE on LQG allow us to determine its value in terms ofpand$$\kappa '$$κ. It shows in particular that$$\hbox {CLE}_{\kappa '}$$CLEκand$$\hbox {CLE}_{16/\kappa '}$$CLE16/κare related via a continuum analog of the Edwards-Sokal coupling between$$\hbox {FK}_q$$FKqpercolation and theq-state Potts model (which makes sense even for non-integerqbetween 1 and 4) if and only if$$q=4\cos ^2(4\pi / \kappa ')$$q=4cos2(4π/κ). This provides further evidence for the long-standing belief that$$\hbox {CLE}_{\kappa '}$$CLEκand$$\hbox {CLE}_{16/\kappa '}$$CLE16/κrepresent the scaling limits of$$\hbox {FK}_q$$FKqpercolation and theq-Potts model whenqand$$\kappa '$$κare related in this way. Another consequence of the formula for$$\rho (p,\kappa ')$$ρ(p,κ)is the value of half-plane arm exponents for such divide-and-color models (a.k.a. fuzzy Potts models) that turn out to take a somewhat different form than the usual critical exponents for two-dimensional models.

     
    more » « less
  2. Abstract

    We establish rapid mixing of the random-cluster Glauber dynamics on random$$\varDelta $$Δ-regular graphs for all$$q\ge 1$$q1and$$pp<pu(q,Δ), where the threshold$$p_u(q,\varDelta )$$pu(q,Δ)corresponds to a uniqueness/non-uniqueness phase transition for the random-cluster model on the (infinite)$$\varDelta $$Δ-regular tree. It is expected that this threshold is sharp, and for$$q>2$$q>2the Glauber dynamics on random$$\varDelta $$Δ-regular graphs undergoes an exponential slowdown at$$p_u(q,\varDelta )$$pu(q,Δ). More precisely, we show that for every$$q\ge 1$$q1,$$\varDelta \ge 3$$Δ3, and$$pp<pu(q,Δ), with probability$$1-o(1)$$1-o(1)over the choice of a random$$\varDelta $$Δ-regular graph onnvertices, the Glauber dynamics for the random-cluster model has$$\varTheta (n \log n)$$Θ(nlogn)mixing time. As a corollary, we deduce fast mixing of the Swendsen–Wang dynamics for the Potts model on random$$\varDelta $$Δ-regular graphs for every$$q\ge 2$$q2, in the tree uniqueness region. Our proof relies on a sharp bound on the “shattering time”, i.e., the number of steps required to break up any configuration into$$O(\log n)$$O(logn)sized clusters. This is established by analyzing a delicate and novel iterative scheme to simultaneously reveal the underlying random graph with clusters of the Glauber dynamics configuration on it, at a given time.

     
    more » « less
  3. Abstract

    We introduce tools from discrete convexity theory and polyhedral geometry into the theory of West’s stack-sorting map s. Associated to each permutation$$\pi $$πis a particular set$$\mathcal V(\pi )$$V(π)of integer compositions that appears in a formula for the fertility of $$\pi $$π, which is defined to be$$|s^{-1}(\pi )|$$|s-1(π)|. These compositions also feature prominently in more general formulas involving families of colored binary plane trees calledtroupesand in a formula that converts from free to classical cumulants in noncommutative probability theory. We show that$$\mathcal V(\pi )$$V(π)is a transversal discrete polymatroid when it is nonempty. We define thefertilitopeof$$\pi $$πto be the convex hull of$$\mathcal V(\pi )$$V(π), and we prove a surprisingly simple characterization of fertilitopes as nestohedra arising from full binary plane trees. Using known facts about nestohedra, we provide a procedure for describing the structure of the fertilitope of$$\pi $$πdirectly from$$\pi $$πusing Bousquet-Mélou’s notion of the canonical tree of $$\pi $$π. As a byproduct, we obtain a new combinatorial cumulant conversion formula in terms of generalizations of canonical trees that we callquasicanonical trees. We also apply our results on fertilitopes to study combinatorial properties of the stack-sorting map. In particular, we show that the set of fertility numbers has density 1, and we determine all infertility numbers of size at most 126. Finally, we reformulate the conjecture that$$\sum _{\sigma \in s^{-1}(\pi )}x^{\textrm{des}(\sigma )+1}$$σs-1(π)xdes(σ)+1is always real-rooted in terms of nestohedra, and we propose natural ways in which this new version of the conjecture could be extended.

     
    more » « less
  4. Abstract

    We consider thecapacitated cycle covering problem: given an undirected, complete graphGwith metric edge lengths and demands on the vertices, we want to cover the vertices with vertex-disjoint cycles, each serving a demand of at most one. The objective is to minimize a linear combination of the total length and the number of cycles. This problem is closely related to the capacitated vehicle routing problem (CVRP) and other cycle cover problems such as min-max cycle cover and bounded cycle cover. We show that a greedy algorithm followed by a post-processing step yields a$$(2 + \frac{2}{7})$$(2+27)-approximation for this problem by comparing the solution to a polymatroid relaxation. We also show that the analysis of our algorithm is tight and provide a$$2 + \epsilon $$2+ϵlower bound for the relaxation.

     
    more » « less
  5. Abstract

    Two-dimensional electron systems subjected to high transverse magnetic fields can exhibit Fractional Quantum Hall Effects (FQHE). In the GaAs/AlGaAs 2D electron system, a double degeneracy of Landau levels due to electron-spin, is removed by a small Zeeman spin splitting,$$g \mu _B B$$gμBB, comparable to the correlation energy. Then, a change of the Zeeman splitting relative to the correlation energy can lead to a re-ordering between spin polarized, partially polarized, and unpolarized many body ground states at a constant filling factor. We show here that tuning the spin energy can produce fractionally quantized Hall effect transitions that include both a change in$$\nu$$νfor the$$R_{xx}$$Rxxminimum, e.g., from$$\nu = 11/7$$ν=11/7to$$\nu = 8/5$$ν=8/5, and a corresponding change in the$$R_{xy}$$Rxy, e.g., from$$R_{xy}/R_{K} = (11/7)^{-1}$$Rxy/RK=(11/7)-1to$$R_{xy}/R_{K} = (8/5)^{-1}$$Rxy/RK=(8/5)-1, with increasing tilt angle. Further, we exhibit a striking size dependence in the tilt angle interval for the vanishing of the$$\nu = 4/3$$ν=4/3and$$\nu = 7/5$$ν=7/5resistance minima, including “avoided crossing” type lineshape characteristics, and observable shifts of$$R_{xy}$$Rxyat the$$R_{xx}$$Rxxminima- the latter occurring for$$\nu = 4/3, 7/5$$ν=4/3,7/5and the 10/7. The results demonstrate both size dependence and the possibility, not just of competition between different spin polarized states at the same$$\nu$$νand$$R_{xy}$$Rxy, but also the tilt- or Zeeman-energy-dependent- crossover between distinct FQHE associated with different Hall resistances.

     
    more » « less