Wyniki wyszukiwania - Biblioteka Nauki

Ten serwis zostanie wyłączony 2025-02-11.

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

1 Journal of Language Modelling

1 2024

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The expected sum of edge lengthsin planar linearizations of trees

100%

Alemany-Puig L. , Ferrer-i-Cancho R.

Journal of Language Modelling

2024

tom Vol. 12, No. 1

1--42

Dependency trees have proven to be a very successful model to rep-resent the syntactic structure of sentences of human languages. Inthese structures, vertices are words and edges connect syntactically-dependent words. The tendency of these dependencies to be short hasbeen demonstrated using random baselines for the sum of the lengthsof the edges or their variants. A ubiquitous baseline is the expectedsum in projective orderings (wherein edges do not cross and the rootword of the sentence is not covered by any edge), that can be com-puted in timeO(n). Here we focus on a weaker formal constraint,namely planarity. In the theoretical domain, we present a characteri-zation of planarity that, given a sentence, yields either the number ofplanar permutations or an efficient algorithm to generate uniformlyrandom planar permutations of the words. We also show the relation-ship between the expected sum in planar arrangements and the ex-pected sum in projective arrangements. In the domain of applications,we derive aO(n)-time algorithm to calculate the expected value ofthe sum of edge lengths. We also apply this research to a parallel cor-pus and find that the gap between actual dependency distance and therandombaselinereducesasthestrengthoftheformalconstraintonde-pendency structures increases, suggesting that formal constraints ab-sorbpartofthedependencydistanceminimizationeffect.Ourresearchpaves the way for replicating past research on dependency distanceminimization using random planar linearizations as random baseline.