Kuhlmann & Nivre (2006): Mildly Non-Projective Dependency Structures #
This file formalizes the paper's comparison of the constraints proposed for mildly
non-projective dependency structures: planarity, well-nestedness, gap degree, and the edge
degree of [Niv06]. The first three, with the dominance and projection they are stated
through, are the substrate of Syntax/DependencyGrammar/, whose definitions follow the paper;
edge degree, the number of constituents an edge spans without dominating, is edgeDegree, and
edgeDegree_eq_zero_iff proves for it the paper's observation that degree zero is
projectivity, as Graph.isProjective_iff_gapDegree_eq_zero proves it for gap degree. The
hierarchy projective ⊂ planar ⊂ well-nested is the substrate's, proved there for the paper's
dependency forests, of which Figure 1 is one with two roots (fig1_isForest_not_isTree); the
paper's figures supply the witnesses that keep the inclusions strict, that separate the two
graded measures, and that show well-nestedness independent of both.
The counts of Table 1 are the rows of Data/Treebank/Coverage/KuhlmannNivre2006.json, over
which the paper's percentages are recomputed: about 15% of the Danish and 23% of the Prague
trees are non-projective (nonProjective_share), a degree bound of one covers more than 98% of
both treebanks on either measure (degreeLe1_coverage), and among the non-projective trees
planarity covers fewer than a quarter while well-nestedness covers more than 99%
(nonProjective_binary).
Implementation notes #
Positions are zero-based, so node i of a figure is position i - 1. A connected component
of the subgraph an edge's span induces is identified by its root, the position of the span with
no head inside it, so the degree of an edge counts those positions its head does not dominate.
The trees of the figures are read off the drawings, and the paper's remarks about them, the
projections of the nodes marked i, the edges of degree one, and the interleaving subtrees, are
proved of the reconstructions.
Percentages are recomputed from the rows as rounded hundredths of a percent, the precision the
paper prints, and the subtable over non-projective trees is the difference from the projective
row, since planarity and well-nestedness each contain projectivity.
TODO #
- The paper gives the coverage of edge degree at most one on DDT as 98.24%, the sum of the printed 84.95% and 13.29%; the rows give 98.25%.
References #
Edge degree (Definition 9) #
The roots of the connected components of the subgraph induced by the span of the arc from
h to d: the positions of the span with no head inside it.
Equations
- KuhlmannNivre2006.componentRoots g h d = {v ∈ Finset.uIcc h d | ∀ (u : Fin n), g.Adj u v → u ∉ Finset.uIcc h d}
Instances For
The degree of the arc from h to d: the number of components of the subgraph induced by
its span whose root h does not dominate.
Equations
- KuhlmannNivre2006.edgeDegreeAt g h d = {v ∈ KuhlmannNivre2006.componentRoots g h d | ¬DependencyGrammar.Dominates g h v}.card
Instances For
The edge degree of a graph: the maximum degree of its arcs.
Equations
- KuhlmannNivre2006.edgeDegree g = {p : Fin n × Fin n | g.Adj p.1 p.2}.sup fun (p : Fin n × Fin n) => KuhlmannNivre2006.edgeDegreeAt g p.1 p.2
Instances For
An arc has degree zero exactly when its head dominates every position it spans.
Degree zero is projectivity, for edge degree as for gap degree: a tree has edge degree zero exactly when it is projective.
Figure 1: a dependency forest #
The analysis of Není proto zapotřebí uzavírat nové nájemní smlouvy. leaves proto and the final punctuation mark without a head, so it is a forest and not a tree, and the yield of není skips proto.
An unlabelled position.
Equations
Instances For
Figure 1: nodes 2 and 8 have no head.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Figure 1 is not projective: the projection of node 1 lacks node 2.
Figure 2: planarity #
Figure 2a is planar but not projective, its root inside the gap where the substrate's
Graph.IsPlanar.root_mem_gap says a planar tree's root has to be; Figure 2b is not planar,
its two named edges crossing.
Figure 2a: the yield of node 1, {1, 3}, skips the root.
Equations
Instances For
Figure 2b: the edges (1, 4) and (3, 5) cross.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Planar but not projective, with the root strictly inside the gap of node 1.
Figure 2b is not planar: the edges (1, 4) and (3, 5) cross, and no other pair does.
Figure 3: gap degree, edge degree, and well-nestedness #
Figure 3a: the projection of node 2 is the interval (2, 3, 4).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Figure 3b: the projection of node 2 is (2, 3, 6), with the gap (3, 6).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Figure 3c: the projection of node 2 is (2, 4, 6), with the gaps (2, 4) and (4, 6).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Node 2 has gap degree 0, 1, and 2 across the figure, and in each graph the maximum.
Edge degree 0, 1, and 1: the edge (1, 5) of Figure 3a spans the component {2, 3, 4},
which its head dominates; the edge (3, 6) of Figure 3b and the edges (2, 4), (3, 5), and
(4, 6) of Figure 3c each span one component their head does not dominate.
Figures 3a and 3b are well-nested; Figure 3c is not, the disjoint subtrees at nodes 2 and 3 interleaving through the positions 2, 4 and 3, 5.
The hierarchy projective ⊂ planar ⊂ well-nested is strict: Figure 2a is planar and not projective, Figure 3b well-nested and not planar.
Figure 4: gap degree against edge degree #
Figure 4a: the subtree at node 2 has two gaps, each of its edges spanning one component node 2 does not dominate.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Figure 4b: the subtree at node 2 has one gap, containing two components node 2 does not dominate.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Gap degree measures the discontinuities of a subtree, edge degree the constituents an edge spans: the two orders of Figure 4 reverse.
Table 1: coverage on the Danish and Prague treebanks #
The rows of Table 1.
Instances For
The number of trees of a treebank meeting a constraint.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The number of trees of a treebank.
Equations
- KuhlmannNivre2006.total treebank = match List.find? (fun (x : Data.Treebank.Coverage.Row) => decide (x.treebank = treebank)) KuhlmannNivre2006.rows with | some r => r.total | none => 0
Instances For
The number of trees of degree at most k on a graded measure.
Equations
- KuhlmannNivre2006.atMost treebank measure k = (List.map (fun (d : ℕ) => KuhlmannNivre2006.count treebank (measure d)) (List.range (k + 1))).sum
Instances For
The number of non-projective trees of a treebank.
Equations
- KuhlmannNivre2006.nonProjective treebank = KuhlmannNivre2006.total treebank - KuhlmannNivre2006.count treebank Data.Treebank.Coverage.Constraint.projective
Instances For
Gap degree at most one covers 99.84% of DDT and 99.57% of PDT, edge degree at most one 98.25% and 99.54%.
Among the non-projective trees, planarity covers 9.68% of DDT and 22.93% of PDT, well-nestedness 99.24% and 99.54%.