The goal of this study is to introduce and observe analysis by reduction of dependency trees. We focus on formalization of certain minimalistic properties of analysis by reduction of dependency trees, and its complexity issues. ∗The paper reports on the research supported by the grant of GA CˇR No. P202/10/1333.
(v) specially, an application of the shift operation is limited only to cases when a shift is enforced by the correctness preserving principle (ii), i.e., a reduction consisting of some cuts of only would result in an incorrect word order.
We introduce analysis by reduction of D-trees (ARDT) in order to give a new formal tool for study of individual dependency trees in tree-banks, namely for the study of their structural complexity. In this way we give at the same time a tool for observations of properties of the whole treebanks, and their interesting subsets. We work in a way which is close to the formal languages theory. We should be able to study complexity issues of formal D-tree languages.
Analysis by Reduction Based on D-Trees Analysis by reduction on D-trees is derived from analysis by reduction of natural language sentences (AR), see [3], helps one to study AR, and to identify a sentence dependency structure and the corresponding grammatical categories of an analyzed language. ARDT is based upon a stepwise simplification of a correctly composed D-tree (e.g, correctly composed to a correct Czech sentence). It defines possible sequences of reductions in the D-tree – each step of ARDT consists in some cuts of some subtrees from the input D-tree; here, we allow the cuts of to be accompanied by some shifts of (a) word(s) (node(s)) to another horizontal position(s) in the D-tree.
Let us stress the basic constraints imposed on reduction steps of surface ARDT: (i) individual words (word forms), their morphological characteristics and/or their syntactic categories must be preserved in the course of ARDT; (ii) a (grammatically) correct D-tree must remain correct after its simplification; (iii) shortening of any reduction would violate the principle of correctness (iv) a D-tree D which contains a correct D-tree D0 as a subtree, where D and D0 have the same root, must be further reduced;
(
Petr.Sb se.AuxT bojí.Pred o.AuxP otce.Obj ..AuxK
delete delete Petr.Sb se.AuxT bojí.Pred ..AuxK * Se.AuxT bojí.Pred o.AuxP otce.Obj ..AuxK
delete shift * Se.AuxT bojí.Pred ..AuxK Bojí.Pred se.AuxT o.AuxP otce.Obj ..AuxK shift delete
Bojí.Pred se.AuxT ..AuxK
must be preserved in a simplified sentence until all its
dependent words are deleted, see [2]. In other words, the
above described AR of the sentence (
Petr.Sb se.AuxT bojí.Pred o.AuxP
..AuxK otce.Obj
In the following we introduce and study a formal apparatus which allows an algebraic and complexity characterization (of properties) of analysis by reduction of dependency trees informally outlined in the previous chapter. We work with a finite proper alphabet (vocabulary) Σp (modeling individual word forms), an alphabet of categories Σc, and a composed basic alphabet Γ ⊆ Σp × Σc, which models lexico-morphological disambiguations of individual word forms.
To realize a projection from Γ∗ to Σ∗p and Σc∗, respectively, we define two homomorphisms, a proper homomorphism hp : Γ → Σp and a categorial homomorphism hc : Γ → Σc in the obvious way: hp([a, b]) = a, and hc([a, b]) = b for each [a, b] ∈ Γ. Proper inclusions are denoted by ⊂.
Σep ={ Petr, se, bojí , o, otce, . }
Σec = { Sb, AuxT, Pred, AuxP, Obj, AuxK }
Γe = {b1 = [Petr, Sb], b2 = [se, AuxT], b3 = [boj, Pred], b4 = [o, AuxP], b5 = [otce, Obj], b6 = [., AuxK]} In this paragraph, we introduce so-called D-structures (Delete or Dependency structures). A D-structure captures syntactic units (words and their categories used in an corresponding sentence) as nodes of a graph and their mutual syntactic relations as edges; moreover, word order is represented by means of total ordering of the nodes.
A D-structure on Σp, Σc, and Γ is a tuple D = (V, E, ord(V )), where the pair (V, E) is a directed acyclic graph, V is its finite set of nodes, E ⊂ V × V is its finite set of edges. A node u ∈ V is a tuple u = [i, a], where a ∈ Γ is a symbol (word) with a category assigned to the node, and i is a natural number which serves for an unambigous identification of the node u. Finally, ord(V ) is a total ordering of V , usually described as an ordered list of members from V .
Edges are interpreted as representations of syntactic relations between respective lexical units, and ord(V ) serves for a representation of the word order in the modelled sentence. Let ord(V ) = ([i1, a1], · · · , [in, an]), we say that w = a1 · · · an is the string (sentence) of D and write St(D) = w.
Let D = (V, E, ord(V )) be a D-structure, card(V ) = n, and ord(V ) = ([1, a1], [2, a2], · · · , [n, an]) for some a1, · · · , an. We say that D is a normalized Dstructure. Let D = (V, E, ord(V )) be a D-structure, D1 = (V1, E1, ord(V1)) a normalized D-structure, (V, E) and (V1, E1) are isomorphic, and St(D) = St(D1). We say that D1 is a normalization of D.
We say that two D-structures are equivalent if they have equal normalizations.
In the following we usually do not distinquish between equivalent D-structures. Note that to any D-structure is its normalization unambiguously determined.
Further we will work mostly with special D-structures called D-trees. We say that a D-structure D = (V, E, ord(V )) on Σp, Σc, and Γ is a D-tree on Σp, Σc, and Γ if (V, E) is a rooted tree (i.e., all maximal paths in (V, E) end in its single root).
Tr1 = ({[1, b1], [2, b2], [3, b3], [4, b4], [5, b5], [6, b6]}, {([1, b1], [3, b3]), ([2, b2], [3, b3]), ([4, b4], [3, b3]), ([5, b5], [4, b4]), ([6, b6], [3, b3])}, ([1, b1], [2, b2], [3, b3], [4, b4], [5, b5], [6, b6]))
Let D = (V, E, ord(V )), D1 = (V1, E1, ord(V1)), where (V1, E1) is a subtree of (V, E) which contains the root of D, and ord(V1) is a permutation of a subsequence of ord(V ). Then we write D1 ⊂ D.
Tr2 = ({[1, b1], [2, b2], [3, b3], [6, b6]}, {([1, b1], [3, b3]), ([2, b2], [3, b3]), ([6, b6], [3, b3])}, ([1, b1], [2, b2], [3, b3], [6, b6]))
We can see that Tr2 ⊂ Tr1.
We say that a set T of D-trees on Σp, Σc, and Γ is a D-language on Σp, Σc, and Γ. We write T ∈ D(Σp, Σc, Γ).
is the proper language of T , and hc(St(T )) the categorial language of T .
Now we introduce a basic operation for analysis by reduction on D-trees. It is determined by a node u of a D-tree which is not the root of the D-tree We call this operation an u-cut). Note that any node u of a D-tree D, where u is not the root of D, unambiguously determines a partition of D into two subtrees:
1) lower subtree TL(u, D) of D by u, i.e. such a maximal subtree of D containing only nodes on some path leading to u (including the node u),
2) upper subtree TU (u, D) of D by u, i.e. such a maximal subtree of D containing the root of D, and all nodes which are not from TL(u). An u-cut on D transforms D to TU (u, D). We denote such a u-cut (directly) by TU (u, D). We can see that TU (u, D) is again a D-tree .
Now we introduce an operation called shift, suitable for an enhancement of analysis by reduction on D-trees. A shift means a move of a single node of a D-tree to some new place in its ordering, i.e., only the total ordering of the set nodes is changed.
Consider u-cuts and shifts being the only operations allowed on (a set of) D-trees. Based on these operations, we can naturally define a partial order T on a D-language T . We say that t1 is Dt-reduced to t2 in T and write t1 T t2 iff: 1. t2 is is obtained from t1 by a sequence O of u-cuts possibly followed by some shifts (O contains at least
O one u-cut); t1 → t2; 2. the application of any proper subsequence O0 of O on u would end up with a D-tree outside T . 3. Let TU (u, D) be an u-cut from O. Any substitution of TU (u, D) by some TU (v, D) in O such that TU (u, D) ⊂ TU (v, D) ⊂ D would end up with a D-tree outside T . By
T+ we denote transitive, non-reflexive closure of T .
Tr3 = ({[2, b2], [3, b3], [6, b6]}, {([2, b2], [3, b3]), ([6, b6], [3, b3])}, ([3, b3], [2, b2], [6, b6])) Let T1 = {Tr1, Tr2, Tr3}. We can see that
Tr1
T1 Tr2
T1 Tr3, and that the Dt-reduction Tr2
T1 Tr3 uses a shift.
T naturally defines the setLmiTn of minThe partial order imal D-trees in T :
LmiTn = {v ∈ T | ¬∃u ∈ T : v T u}.
Tr4 = ({[2, b2], [3, b3], [4, b4], [5, b5], [6, b6]}, {([2, b2], [3, b3]), ([4, b4], [3, b3]), ([5, b5], [4, b4]), ([6, b6], [3, b3])}, ([3, b3], [2, b2], [4, b4], [5, b5], [6, b6]))
Let T2 = {Tr1, Tr2, Tr3, Tr4}. We can see that
Tr1
T2 Tr2
T2 Tr3, Tr1
T2 Tr4
T2 Tr3, , and that the Dt-reductions Tr2 use a shift.
T2 Tr3, and Tr1
T2 Tr4 Further we can see that LmiTn = {Tr3}.
2 2.1
Analysis by Reduction for a D-Language Let T be a D-language. We write DtP(T ) ={ u T v|u, v ∈ T }. We say that DtP(T ) is the DS-precedence set for T .
for T if AR(T ) = DtP(T ), and T = LmiTn ∪ {v; ∃u, v T u ∈ AR(T )}, and LmiTn ⊆ {v; ∃u, u T v ∈ AR(T )}.
We can see that DtP(T ) is determined unambiguously by T . Therefore, if T have some analysis by reduction, the analysis by reduction AR(T ) is determined unambiguously by T .
AR(T2) = {Tr1 Tr4 T2 Tr3} . T2 Tr2, Tr2 2.2
M. Plátek T2 Tr3, Tr1
T2 Tr4, Let T ∈ D(Σp, Σc, Γ) be a D-language. We suppose in the following that the alphabets (vocabularies) Σp, Σc, Γ are minimal due to T , i.e., any removing of some symbol of some of this alphabets would cause some removing of some D-tree(s) from T . The syntactic analysis of natural languages is from the point of view of computational linguistic a very difficult task. One of the main reasons of this fact is the enormous size of vocabularies corresponding to Σp, Σc,, and Γ. E.g. we have access to vocabulary with circa 700 000 items for Czech word forms. Another source of complexity for the syntactic analysis is the lexical ambiguity in the vocabularies corresponding to Γ. E.g., the Czech word jarní has 28 different morphological disambiguations. In the following paragraph we focus on such type of structural complexity measures which will witnesses relative structural simplicity of dependency trees for Czech sentences. 2.3
With respect to the previous motivation, we focus on the number of cuts and shifts used in individual Dt-reductions, and on the number of nodes deleted in individual Dtreductions. We use particular abbreviations for languages with restriction on these complexity measures. In particular, prefixDt- is used to identify the D-languages without any restriction, and Dc- is used for languages with cuts only. Further, the prefix c(k)- is used to indicate that at most k cut-operations are available in one Dt-reduction. We use the syllable de(i)- for languages with at most i deleted nodes in a single Dt-reduction, and s(j)- for languages with at most j shifts in a single Dt-reduction. For each type X of restrictions, we use D (X) to denote the class of all D-languages with Dt-reductions fullfiling X-restrictions. Further, Dn(X) denote the classes of D-languages which are determined by D-languages with D-trees which can be reduced by Dt-reductions fullfiling X-restrictions at most n-times.
Let T2 be the D-language given by Example 6. We can
see that T2 ∈ D2(c(
Let us consider all purely dependency D-trees from the
Prague Tree-Bank ([1]). We believe (by our observations)
that this set is a subset from D100(c(
We are able to show that there are infinite hierarchies of formal (in)finite D-languages with analysis by reduction based on the measures c(i), s(i), and de(i).
We plan also introduce and study hierarchies based on the degrees of discontinuity and/or non-projectivity of individual Dt-reductions, and all that to model by restarting automata.
We have introduced analysis by reduction of D-trees in order to formally characterize the basic properties of the dependecy based syntactic analysis of Czech sentences. We will show in the close future that it is a fine tool for the description of structural complexity and ambiguity of natural language (Czech) sentences.