Inherent Dependency Displacement Bias of Transition-Based Algorithms
- URL: http://arxiv.org/abs/2003.14282v1
- Date: Tue, 31 Mar 2020 15:11:12 GMT
- Title: Inherent Dependency Displacement Bias of Transition-Based Algorithms
- Authors: Mark Anderson, Carlos G\'omez-Rodr\'iguez
- Abstract summary: We show that the similarity of an algorithm's inherent distribution to a treebank's displacement distribution is clearly correlated to the algorithm's parsing performance.
We also obtain results which show a more discrete analysis of dependency displacement does not result in any meaningful correlations.
- Score: 3.7311680121118345
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A wide variety of transition-based algorithms are currently used for
dependency parsers. Empirical studies have shown that performance varies across
different treebanks in such a way that one algorithm outperforms another on one
treebank and the reverse is true for a different treebank. There is often no
discernible reason for what causes one algorithm to be more suitable for a
certain treebank and less so for another. In this paper we shed some light on
this by introducing the concept of an algorithm's inherent dependency
displacement distribution. This characterises the bias of the algorithm in
terms of dependency displacement, which quantify both distance and direction of
syntactic relations. We show that the similarity of an algorithm's inherent
distribution to a treebank's displacement distribution is clearly correlated to
the algorithm's parsing performance on that treebank, specifically with highly
significant and substantial correlations for the predominant sentence lengths
in Universal Dependency treebanks. We also obtain results which show a more
discrete analysis of dependency displacement does not result in any meaningful
correlations.
Related papers
- Separation and Collapse of Equilibria Inequalities on AND-OR Trees without Shape Constraints [0.0]
directional algorithms are known to achieve the randomized complexity.
We show that for any AND-OR tree, randomized depth-first algorithms have the same equilibrium as that of the directional algorithms.
arXiv Detail & Related papers (2024-05-30T15:13:46Z) - 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) - Improving Out-of-Distribution Generalization of Neural Rerankers with
Contextualized Late Interaction [52.63663547523033]
Late interaction, the simplest form of multi-vector, is also helpful to neural rerankers that only use the [] vector to compute the similarity score.
We show that the finding is consistent across different model sizes and first-stage retrievers of diverse natures.
arXiv Detail & Related papers (2023-02-13T18:42:17Z) - Regularized impurity reduction: Accurate decision trees with complexity
guarantees [20.170305081348328]
We propose a tree-induction algorithm that gives a logarithmic approximation guarantee on the tree complexity.
The enhanced algorithms strike an excellent balance between predictive accuracy and tree complexity.
arXiv Detail & Related papers (2022-08-23T13:15:19Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
Machine learning has emerged as a promising paradigm for branching.
We propose retro branching; a simple yet effective approach to RL for branching.
We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
arXiv Detail & Related papers (2022-05-28T06:08:07Z) - A Closer Look at Branch Classifiers of Multi-exit Architectures [103.27533521196817]
Constant-complexity branching keeps all branches the same, while complexity-increasing and complexity-decreasing branching place more complex branches later or earlier in the backbone respectively.
We investigate a cause by using knowledge consistency to probe the effect of adding branches onto a backbone.
Our findings show that complexity-decreasing branching yields the least disruption to the feature abstraction hierarchy of the backbone.
arXiv Detail & Related papers (2022-04-28T08:37:25Z) - Biaffine Discourse Dependency Parsing [0.0]
We use the biaffine model for neural discourse dependency parsing and achieve significant performance improvement compared with the baselines.
We compare the Eisner algorithm and the Chu-Liu-Edmonds algorithm in the task and find that using the Chu-Liu-Edmonds generates deeper trees.
arXiv Detail & Related papers (2022-01-12T12:56:13Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
We design and analyze an algorithm that boosts the error exponent by at least 40% when $rho$ is at least $0.8$.
Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph.
arXiv Detail & Related papers (2021-10-27T10:45:21Z) - Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
We analyze the output of state-of-the-arts on many languages from the Universal Dependency Treebank.
The worst constraint-violation rate we observe is 24%.
arXiv Detail & Related papers (2020-10-06T08:31:14Z) - Uncovering Feature Interdependencies in High-Noise Environments with
Stepwise Lookahead Decision Forests [0.0]
"Stepwise lookahead" variation of random forest algorithm is presented for its ability to better uncover binary feature interdependencies.
A long-short trading strategy for copper futures is then backtested by training both greedy and lookahead random forests to predict the signs of daily price returns.
arXiv Detail & Related papers (2020-09-30T11:31:10Z) - 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)
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.