Flexible tree ensemble learning framework supports arbitrary loss functions and multi-task learning.
problem Limited modeling capabilities of existing tree ensemble learning toolkits.
method Differentiable tree ensembles with tensor-based formulation for efficient training.
result Our framework leads to 100x more compact and 23% more expressive tree ensembles.
Integrates differentiable decision trees into neural networks for faster training and inference.
problem Combining differentiability and conditional computation in tree ensembles for neural networks.
method Sparse activation function and specialized forward/backward propagation algorithms for efficient training and inference.
result 10x speed-ups and 20x reduction in parameters compared to existing methods, while maintaining performance.
Attention augments forest for tabular data accuracy.
problem Training tabular data models with high accuracy and efficiency.
method Tree Attention Block (TAB) in differentiable forest framework.
result Attention augmented differentiable forest achieves comparable and sometimes higher accuracy than GBDT models.
Regression trees learn gradients of differentiable functions.
problem Understanding gradients of differentiable functions using regression trees.
method Developed a method to estimate gradients of differentiable functions using regression trees and exposed quantities from tree learning libraries.
result Gradient estimates from regression trees can be used to improve predictive analysis and solve tasks in uncertainty quantification.
Paper introduces algorithms for private decision tree learning.
problem Private decision tree learning in distributed settings.
method Proposes DP-TopDown, NoisyCounts, and LocalRNM.
result First utility guarantees for private decision tree learning.
Differentiable optimization bridges arbitrary metrics to tree metrics.
problem Designing algorithms to convert arbitrary metrics to tree metrics with guarantees.
method DeltaZero framework, leveraging differentiable Gromov hyperbolicity.
result DeltaZero consistently achieves state-of-the-art distortion on synthetic and real-world datasets.
We introduce a semiparametric approach to neighbor-based classification. We build off the recently proposed Boundary Trees algorithm by Mathy et al.(2015) which enables fast neighbor-based classification, regression and retrieval in large datasets. While boundary trees use an Euclidean measure of similarity, the Differ…
New method learns binary decision trees efficiently.
problem Learning binary decision trees for data partitioning.
method Argmin differentiation for discrete and continuous parameters.
result Produces competitive binary trees with fast training.
The paper proposes a method to infer differentiation trees from RNA velocity data.
problem Reconstructing dynamic cellular processes from sequencing data.
method Defining varifold distances between RNA velocity curves to approximate shortest-path distances in a tree.
result The varifold distance method approximates the shortest-path distance in a tree isomorphic to the target differentiation tree.
A novel gradient-based method optimizes decision trees for complex tasks.
problem Training decision trees with arbitrary differentiable loss functions.
method Gradient-based optimization using first and second derivatives of loss functions.
result Improves accuracy and flexibility in decision tree optimization.
Decision trees are ubiquitous in machine learning for their ease of use and interpretability. Yet, these models are not typically employed in reinforcement learning as they cannot be updated online via stochastic gradient descent. We overcome this limitation by allowing for a gradient update over the entire tree that i…
A new approach to Morse theory using folded ribbon trees.
problem Applying Morse theory on symmetric products of surfaces.
method Introducing an A-infinity category with objects as κ-tuples of Morse functions, and showing conditions for the endomorphism to be a Hecke algebra.
result The endomorphism of a specific type of κ-tuple of Morse functions on T*R^2 is the Hecke algebra associated to the symmetric group.
GeoPhy uses geometric gradients to efficiently infer phylogenetic trees from molecular data.
problem Challenges in accurately inferring species relationships from molecular data due to combinatorially vast tree topologies.
method Introduces a novel, fully differentiable formulation of phylogenetic inference using geometric spaces and variational Bayesian methods.
result Significantly outperforms other approximate Bayesian methods in inferring phylogenetic trees.
New spanning tree model connects knot homology, s-invariant, and exotic discs.
problem Understanding exotic discs in the 4-ball for knots.
method Explicitly defined differential in spanning tree complex, described Rasmussen's s-invariant.
result Identified new infinite family of knots bounding exotic discs.
Paper uses CMAB to improve NAS efficiency and accuracy.
problem Improving efficiency and accuracy of NAS for DNNs.
method Formulated NAS as CMAB, used Nested Monte-Carlo Search.
result Discovered cell structure achieves comparable accuracy to state-of-the-art, 20x faster.
DiPriMe forests use private medians to create balanced tree splits for privacy-protected data.
problem Privacy concerns in training random forests due to multiple data queries.
method Proposes DiPriMe forests, which use a private median to generate balanced splits, ensuring differential privacy.
result DiPriMe forests achieve high utility while maintaining differential privacy, as shown both theoretically and empirically.
TREX explains tree ensembles by identifying key training examples.
problem Identifying which training examples most influence tree ensemble predictions.
method TREX builds a surrogate model using a kernel that captures tree ensemble structure, approximating the original model.
result TREX provides accurate and effective explanations for tree ensembles.
The Gradient Boosting Decision Tree (GBDT) is a popular machine learning model for various tasks in recent years. In this paper, we study how to improve model accuracy of GBDT while preserving the strong guarantee of differential privacy. Sensitivity and privacy budget are two key design aspects for the effectiveness o…
A new deep learning model for tabular data improves accuracy over GBDT.
problem Improving accuracy in tabular data classification.
method Differentiable forest with sparse attention mechanism.
result The differentiable forest achieves higher accuracy than GBDT on tabular datasets.
The theme in this paper is the recombining binomial tree to price American put option when the underlying stock follows constant elasticity of variance(CEV) process. Recombining nodes of binomial tree are decided from finite difference scheme to emulate CEV process and the tree has a linear complexity. Also it is deriv…
The Jones polynomial can be expressed in terms of spanning trees of the graph obtained by checkerboard coloring a knot diagram. We show there exists a complex generated by these spanning trees whose homology is the reduced Khovanov homology. The spanning trees provide a filtration on the reduced Khovanov complex and a …
Bayesian GBMs improve predictive uncertainty calibration for tabular data.
problem Lack of well-calibrated predictive uncertainties in gradient boosting machines.
method Variational inference with soft decision trees.
result Variational soft GBMs provide useful uncertainty estimates and maintain good predictive performance.
TF Boosted Trees (TFBT) is a new open-sourced frame-work for the distributed training of gradient boosted trees. It is based on TensorFlow, and its distinguishing features include a novel architecture, automatic loss differentiation, layer-by-layer boosting that results in smaller ensembles and faster prediction, princ…
New KD-tree based method for private synthetic data generation.
problem Creating private synthetic data that accurately represents real data.
method KD-trees combined with noise perturbation for differentially private synthetic data generation.
result Our data-dependent approach improves utility over prior work and scales well.
We study the limits of holonomy representations of complex projective structures on a compact Riemann surface in the Morgan-Shalen compactification of the character variety. We show that the dual R-trees of the quadratic differentials associated to a divergent sequence of projective structures determine the Morgan-Shal…
This paper introduces TNTK to study infinite soft tree ensembles.
problem Understanding the behavior of infinite soft tree ensembles.
method Introduced Tree Neural Tangent Kernel (TNTK) to analyze infinite soft tree ensembles.
result Identified several non-trivial properties of infinite soft tree ensembles.
Until recently, transcriptomics was limited to bulk RNA sequencing, obscuring the underlying expression patterns of individual cells in favor of a global average. Thanks to technological advances, we can now profile gene expression across thousands or millions of individual cells in parallel. This new type of data has …
We study the combinatorial geometry of "lattice" Jenkins--Strebel differentials with simple zeroes and simple poles on CP1 and of the corresponding counting functions. Developing the results of M. Kontsevich we evaluate the leading term of the symmetric polynomial counting the number of such "lattice" Jenki…
The isoresidual fibration maps Riemann sphere strata to resonance arrangements.
problem Mapping Riemann sphere strata to resonance arrangements.
method Defining isoresidual fibration and studying its properties using tree structures.
result The isoresidual fibration is an unramified cover of degree a!/(a+2-p)! above the complement of a hyperplane arrangement.
Single tree outperforms random forest in testing accuracy.
problem The challenge of improving single decision tree performance.
method Gradient-based entire tree optimization framework, scaled sigmoid approximation, numerical stability algorithm, subtree polish strategy.
result Optimized single tree outperforms classic random forest by 2.03% on average.
Most decision tree induction algorithms are based on a greedy top-down recursive partitioning strategy for tree growth. In this paper, we propose several methods for induction of decision trees and their ensembles based on evolutionary algorithms. The main difference of our approach is using real-valued vector represen…
Minimal diffeomorphisms extend uniquely with L1 Hopf differential.
problem Extending minimal diffeomorphisms between disks with specific properties.
method Uniqueness of solutions for a Plateau problem in a product of trees.
result Minimal diffeomorphisms extend uniquely with L1 Hopf differential. Paper finds how Steklov eigenvalues change on graphs and trees.
problem Understanding how Steklov eigenvalues vary on graphs and trees.
method Analyzes monotonicity of Steklov eigenvalues on graphs and trees.
result Extends Steklov eigenvalue results to higher eigenvalues and trees.
Improved DP KDE with better privacy and efficiency.
problem Kernel density estimation with differential privacy.
method Refined search tree construction for DP KDE.
result Improved query time and approximation ratio.
Develops a variational method for ultrametric phylogenetic trees.
problem Accurate and efficient approximation of posterior distributions over trees in Bayesian phylogenetics.
method Variational Bayesian approach based on coalescent times of a single-linkage clustering.
result Achieves competitive accuracy with significantly fewer gradient evaluations.
Ensembles of classification and regression trees remain popular machine learning methods because they define flexible non-parametric models that predict well and are computationally efficient both during training and testing. During induction of decision trees one aims to find predicates that are maximally informative …
Federated Extra-Trees protects privacy while improving machine learning performance.
problem Scattered data and privacy concerns in machine learning.
method Local differential privacy in federated trees model.
result Improved accuracy and robustness in federated machine learning.
Combining deep model-free reinforcement learning with on-line planning is a promising approach to building on the successes of deep RL. On-line planning with look-ahead trees has proven successful in environments where transition models are known a priori. However, in complex environments where transition models need t…
We consider certain groups of tree automorphisms as so-called diffeological groups. The notion of diffeology, due to Souriau, allows to endow non-manifold topological spaces, such as regular trees that we look at, with a kind of a differentiable structure that in many ways is close to that of a smooth manifold; a suita…
Study of non-Archimedean Hitchin map for SL2(F) characters.
problem Characterizing representations of SL2(F) characters.
method Equivariant harmonic maps into R-trees, Jenkins-Strebel differentials.
result The non-Archimedean Hitchin map is continuous and its image is contained in Jenkins-Strebel differentials.
We study compositional generalization, viz., the problem of zero-shot generalization to novel compositions of concepts in a domain. Standard neural networks fail to a large extent on compositional learning. We propose Tree Stack Memory Units (Tree-SMU) to enable strong compositional generalization. Tree-SMU is a recurs…
The Mondrian process represents an elegant and powerful approach for space partition modelling. However, as it restricts the partitions to be axis-aligned, its modelling flexibility is limited. In this work, we propose a self-consistent Binary Space Partitioning (BSP)-Tree process to generalize the Mondrian process. Th…
We iterate Manolescu's unoriented skein exact triangle in knot Floer homology with coefficients in the field of rational functions over Z/2Z. The result is a spectral sequence which converges to a stabilized version of delta-graded knot Floer homology. The (E2,d2) page of this spectral sequence …
AD-HOC simplifies high-order derivative calculations in C++.
problem Efficiently computing high-order derivatives in C++.
method A C++ package that calculates derivatives of arbitrary order without code generation.
result Derivatives of arbitrary order computed in a single pass.
Derives Black-Scholes model without stochastic calculus or PDEs.
problem Deriving the Black-Scholes model without advanced math.
method Continuum limit of Binomial tree approach.
result Derives Black-Scholes model and exchange-option generalization.
sGBM speeds up gradient boosting by parallelizing and adapting base learners.
problem Infeasibility of parallelizing GBM training and sub-optimal performance in online settings.
method Integrates multiple differentiable base learners, jointly optimizing them with linear speed-up.
result sGBM achieves higher time efficiency and better accuracy than traditional GBM.
Infinitesimal gradient boosting is a new algorithm derived from gradient boosting.
problem Improving the efficiency and smoothness of gradient boosting.
method Introduced a new class of randomized regression trees and used a limit process in vanishing-learning-rate asymptotic.
result Convergence of the stochastic algorithm and characterization of the limiting procedure as a unique solution of a nonlinear ODE.
Since its inception in the 1980s, ID3 has become one of the most successful and widely used algorithms for learning decision trees. However, its theoretical properties remain poorly understood. In this work, we introduce a novel metric of a decision tree algorithm's performance, called mean iteration statistical consis…