Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing

• URL: http://arxiv.org/abs/2403.00143v2
• Date: Tue, 05 Nov 2024 21:04:23 GMT
• Title: Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing
• Authors: Behzad Shayegh, Yuqiao Wen, Lili Mou,
• Abstract summary: 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.
• Score: 23.091613114955543
• License:
• Abstract: We address unsupervised discontinuous constituency parsing, where we observe a high variance in the performance of the only previous model in the literature. We propose to build an ensemble of different runs of the existing discontinuous parser by averaging the predicted trees, to stabilize and boost performance. To begin with, we provide comprehensive computational complexity analysis (in terms of P and NP-complete) for tree averaging under different setups of binarity and continuity. We then develop an efficient exact algorithm to tackle the task, which runs in a reasonable time for all samples in our experiments. Results on three datasets show our method outperforms all baselines in all metrics; we also provide in-depth analyses of our approach.

Related papers

• A Unified Approach to Extract Interpretable Rules from Tree Ensembles via Integer Programming [2.1408617023874443]
  Tree ensemble methods are known for their effectiveness in supervised classification and regression tasks. Our work aims to extract an optimized list of rules from a trained tree ensemble, providing the user with a condensed, interpretable model.
  arXiv  Detail & Related papers  (2024-06-30T22:33:47Z)
• 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)
• On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem [0.0]
  We contribute to the efficient approximation of the $mathcalNP$-hard multi-objective minimum spanning tree problem (moMST) adopting evolutionary computation. We design several highly biased sub-graph-based mutation operators founded on the gained insights. Our results confirm that the sub-graph based operators beat baseline algorithms from the literature.
  arXiv  Detail & Related papers  (2023-05-31T22:35:17Z)
• Parallel Tree Kernel Computation [0.0]
  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.
  arXiv  Detail & Related papers  (2023-05-12T18:16:45Z)
• Will Bilevel Optimizers Benefit from Loops [63.22466953441521]
  Two current popular bilevelimats AID-BiO and ITD-BiO naturally involve solving one or two sub-problems. We first establish unified convergence analysis for both AID-BiO and ITD-BiO that are applicable to all implementation choices of loops.
  arXiv  Detail & Related papers  (2022-05-27T20:28:52Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• 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)
• Stochastic Optimization Forests [60.523606291705214]
  We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm. We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
  arXiv  Detail & Related papers  (2020-08-17T16:56:06Z)
• A General Method for Robust Learning from Batches [56.59844655107251]
  We consider a general framework of robust learning from batches, and determine the limits of both classification and distribution estimation over arbitrary, including continuous, domains. We derive the first robust computationally-efficient learning algorithms for piecewise-interval classification, and for piecewise-polynomial, monotone, log-concave, and gaussian-mixture distribution estimation.
  arXiv  Detail & Related papers  (2020-02-25T18:53:25Z)

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.