Scarcity of crossing dependencies: A direct outcome of a specific constraint?

The structure of a sentence can be represented as a network where vertices are words and edges indicate syntactic dependencies. Interestingly, crossing syntactic dependencies have been observed to be infrequent in human languages. This leads to the question of whether the scarcity of crossings in languages arises from an independent and specific constraint on crossings. We provide statistical evidence suggesting that this is not the case, as the proportion of dependency crossings of sentences from a wide range of languages can be accurately estimated by a simple predictor based on a null hypothesis on the local probability that two dependencies cross given their lengths. The relative error of this predictor never exceeds $5\%$ on average, whereas the error of a baseline predictor assuming a random ordering of the words of a sentence is at least six times greater. Our results suggest that the low frequency of crossings in natural languages is neither originated by hidden knowledge of language nor by the undesirability of crossings per se, but as a mere side effect of the principle of dependency length minimization.

Figure 1

Syntactic dependency trees of sentences. (a) A tree without dependency crossings. “John” is the subject of the verbal form “gave.” (b) A tree with one edge crossing (the crossing is formed by the edge linking “ate” and “yesterday” and the edge linking “apple” and “which”). (c) The same sentence after fronting “yesterday.” Notice that the length of the dependency between “ate” and “yesterday” and the dependency between “apple” and “which” have reduced (while the length of other dependencies has remained constant). (a) and (b) are adapted from [10].

Figure 2

Linear arrangements of trees with $n=6$ vertices. (a), (b) A star tree, a tree with a vertex of maximum degree [19]. (c), (d) A linear tree, a tree where vertex degrees do not exceed 2 [19].

Figure 3

$p(C(e_1,e_2)=1|d\left(e_1\right),d\left(e_2\right))$ as a function of $d\left(e_1\right)$ and $d\left(e_2\right)$ for different values of $n$ (tree size in vertices). $d\left(e\right)$ is the length of the edge $e$ and $p(C(e_1,e_2)=1|d\left(e_1\right),d\left(e_2\right))$ is the probability that $e_1$ and $e_2$ (a pair of edges of $Q$) cross in a random linear arrangement of their vertices, knowing their lengths. Brightness is proportional to $p(C(e_1,e_2)=1|d\left(e_1\right),d\left(e_2\right))$ [black for $p(C(e_1,e_2)=1|d\left(e_1\right),d\left(e_2\right))=0$ and white for $p(C(e_1,e_2)=1|d\left(e_1\right),d\left(e_2\right))=1]$. (a) $n=4$. (b) $n=8$. (c) $n=12$. (d) $n=16$. (a) and (b) show the value of the probability.

Figure 4

${\mathrm{\Delta }}_2$, the error of the predictor based on the probability that two edges cross in a random linear arrangement preserving their original length, as a function of $n$, the size of the tree. Points and error bars indicate, respectively, mean values and $\pm 1$ standard deviation over proportions in a collection of treebanks. Tree sizes represented by less than two treebanks are excluded. (a) Stanford annotation. (b) Stanford annotation in log-linear scale. (c) Prague annotation. (d) Prague annotation in log-linear scale.

Figure 5

${\mathrm{\Delta }}_0$, the error of the random linear arrangement predictor, as a function of $n$, the size of the tree. The format is the same as in Fig. 4. A control line has been added to indicate $\frac{1}{3}$, namely, the ${\mathrm{\Delta }}_0$ that is expected when $C_{\mathrm{true}}$ is bounded above by a small constant and $n$ goes to infinity. (a) Stanford annotation. (b) Stanford annotation in log-linear scale. (c) Prague annotation. (d) Prague annotation in log-linear scale.