The expected sum of edge lengths in planar linearizations of trees. Theory and applications

• URL: http://arxiv.org/abs/2207.05564v4
• Date: Mon, 18 Sep 2023 07:50:43 GMT
• Title: The expected sum of edge lengths in planar linearizations of trees. Theory and applications
• Authors: Llu\'is Alemany-Puig and Ramon Ferrer-i-Cancho
• Abstract summary: We show the relationship between the expected sum in planar arrangements and the expected sum in projective arrangements. We derive a $O(n)$-time algorithm to calculate the expected value of the sum of edge lengths. We apply this research to a parallel corpus and find that the gap between actual dependency distance and the random baseline reduces as the strength of the formal constraint on dependency structures increases.
• Score: 0.16317061277456998
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dependency trees have proven to be a very successful model to represent the syntactic structure of sentences of human languages. In these structures, vertices are words and edges connect syntactically-dependent words. The tendency of these dependencies to be short has been demonstrated using random baselines for the sum of the lengths of the edges or its variants. A ubiquitous baseline is the expected sum in projective orderings (wherein edges do not cross and the root word of the sentence is not covered by any edge), that can be computed in time $O(n)$. Here we focus on a weaker formal constraint, namely planarity. In the theoretical domain, we present a characterization of planarity that, given a sentence, yields either the number of planar permutations or an efficient algorithm to generate uniformly random planar permutations of the words. We also show the relationship between the expected sum in planar arrangements and the expected sum in projective arrangements. In the domain of applications, we derive a $O(n)$-time algorithm to calculate the expected value of the sum of edge lengths. We also apply this research to a parallel corpus and find that the gap between actual dependency distance and the random baseline reduces as the strength of the formal constraint on dependency structures increases, suggesting that formal constraints absorb part of the dependency distance minimization effect. Our research paves the way for replicating past research on dependency distance minimization using random planar linearizations as random baseline.

Related papers

• Statistical Advantages of Oblique Randomized Decision Trees and Forests [0.0]
  Generalization error and convergence rates are obtained for the flexible dimension reduction model class of ridge functions. A lower bound on the risk of axis-aligned Mondrian trees is obtained proving that these estimators are suboptimal for these linear dimension reduction models.
  arXiv  Detail & Related papers  (2024-07-02T17:35:22Z)
• Tightness of prescriptive tree-based mixed-integer optimization formulations [2.538209532048867]
  We focus on modeling the relationship between an input feature vector and the predicted outcome of a trained decision tree. We propose tighter mixed-integer optimization formulations than those previously introduced.
  arXiv  Detail & Related papers  (2023-02-28T16:44:10Z)
• The distribution of syntactic dependency distances [0.7614628596146599]
  We contribute to the characterization of the actual distribution of syntactic dependency distances. We propose a new double-exponential model in which decay in probability is allowed to change after a break-point. We find that a two-regime model is the most likely one in all 20 languages we considered.
  arXiv  Detail & Related papers  (2022-11-26T17:31:25Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Implicit Generative Copulas [0.0]
  We propose a flexible, yet conceptually simple alternative based on implicit generative neural networks. Experiments on synthetic and real data from finance, physics, and image generation demonstrate the performance of this approach.
  arXiv  Detail & Related papers  (2021-09-29T17:05:30Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees [1.2944868613449219]
  The sum of distances between syntactically related words has been in the limelight for the past decades. Various random baselines have been defined to carry out related quantitative studies on languages. Here we focus on a popular baseline: random projective permutations of the words of the sentence.
  arXiv  Detail & Related papers  (2021-07-07T15:11:53Z)
• A Parallelizable Lattice Rescoring Strategy with Neural Language Models [62.20538383769179]
  A posterior-based lattice expansion algorithm is proposed for efficient lattice rescoring with neural language models (LMs) for automatic speech recognition. Experiments on the Switchboard dataset show that the proposed rescoring strategy obtains comparable recognition performance. The parallel rescoring method offers more flexibility by simplifying the integration of PyTorch-trained neural LMs for lattice rescoring with Kaldi.
  arXiv  Detail & Related papers  (2021-03-08T21:23:12Z)
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks [66.88252321870085]
  This paper introduces a class of mixed-integer formulations for trained ReLU neural networks. At one extreme, one partition per input recovers the convex hull of a node, i.e., the tightest possible formulation for each node.
  arXiv  Detail & Related papers  (2021-02-08T17:27:34Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings [113.15416137912399]
  We propose and analyze a novel theoretical and algorithmic framework for structured prediction. We study a large class of loss functions that implicitly defines a suitable geometry on the problem. When dealing with output spaces with infinite cardinality, a suitable implicit formulation of the estimator is shown to be crucial.
  arXiv  Detail & Related papers  (2020-02-13T10:30:04Z)

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.