Parallel Tree Kernel Computation

• URL: http://arxiv.org/abs/2305.07717v1
• Date: Fri, 12 May 2023 18:16:45 GMT
• Title: Parallel Tree Kernel Computation
• Authors: Souad Taouti, Hadda Cherroun and Djelloul Ziadi
• Abstract summary: We devise a parallel implementation of the sequential algorithm for the computation of some tree kernels of two finite sets of trees. Results show that the proposed parallel algorithm outperforms the sequential one in terms of latency.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tree kernels are fundamental tools that have been leveraged in many applications, particularly those based on machine learning for Natural Language Processing tasks. In this paper, we devise a parallel implementation of the sequential algorithm for the computation of some tree kernels of two finite sets of trees (Ouali-Sebti, 2015). Our comparison is narrowed on a sequential implementation of SubTree kernel computation. This latter is mainly reduced to an intersection of weighted tree automata. Our approach relies on the nature of the data parallelism source inherent in this computation by deploying the MapReduce paradigm. One of the key benefits of our approach is its versatility in being adaptable to a wide range of substructure tree kernel-based learning methods. To evaluate the efficacy of our parallel approach, we conducted a series of experiments that compared it against the sequential version using a diverse set of synthetic tree language datasets that were manually crafted for our analysis. The reached results clearly demonstrate that the proposed parallel algorithm outperforms the sequential one in terms of latency.

Related papers

• Terminating Differentiable Tree Experts [77.2443883991608]
  We propose a neuro-symbolic Differentiable Tree Machine that learns tree operations using a combination of transformers and Representation Products. We first remove a series of different transformer layers that are used in every step by introducing a mixture of experts. We additionally propose a new termination algorithm to provide the model the power to choose how many steps to make automatically.
  arXiv  Detail & Related papers  (2024-07-02T08:45:38Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing [23.091613114955543]
  We propose to build an ensemble of different runs of the existing discontinuous by averaging the predicted trees. We then develop an efficient exact algorithm to tackle the task, which runs in a reasonable time for all samples. Results on three datasets show our method outperforms all baselines in all metrics.
  arXiv  Detail & Related papers  (2024-02-29T21:49:31Z)
• Optimal estimation of Gaussian (poly)trees [25.02920605955238]
  We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery) The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently. The second approach is a modification of the PC algorithm for polytrees that uses partial correlation as a conditional independence tester for constraint-based structure learning.
  arXiv  Detail & Related papers  (2024-02-09T12:58:36Z)
• New Linear-time Algorithm for SubTree Kernel Computation based on Root-Weighted Tree Automata [0.0]
  We propose a new linear time algorithm based on the concept of weighted tree automata for SubTree kernel computation. Key idea behind the proposed algorithm is to replace DAG reduction and nodes sorting steps. Our approach has three major advantages: it is output-sensitive, it is free sensitive from the tree types (ordered trees versus unordered trees), and it is well adapted to any incremental tree kernel based learning methods.
  arXiv  Detail & Related papers  (2023-02-02T13:37:48Z)
• Single MCMC Chain Parallelisation on Decision Trees [0.9137554315375919]
  We propose a method to parallelise a single MCMC decision tree chain on an average laptop or personal computer. Experiments showed that we could achieve 18 times faster running time provided that the serial and the parallel implementation are statistically identical.
  arXiv  Detail & Related papers  (2022-07-26T07:07:51Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Learning Binary Decision Trees by Argmin Differentiation [34.9154848754842]
  We learn binary decision trees that partition data for some downstream task. We do so by relaxing a mixed-integer program for the discrete parameters. We derive customized algorithms to efficiently compute the forward and backward passes.
  arXiv  Detail & Related papers  (2020-10-09T15:11:28Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree. How to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. We demonstrate how proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms.
  arXiv  Detail & Related papers  (2020-06-15T21:36:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.