DepStructureProperties < TFlex

TFlex Web>Proposals>DeepGRs>DepStructureProperties (01 Sep 2008, MarkMcConville) (raw view)EditAttach

<!--
  This is a comment, in the HTML sense of the word, but Wiki directives still work, so you could put
  access control statements here to restrict access to your new topic, and they won't show up in the
  published page.
  Please think carefully when creating a new topic, and use a GoodWikiName
-->

---+++ Definition of dependency structures

A dependency structure over sentence S = w<sub>1</sub> w<sub>2</sub> ... w<sub>n</sub> is an ordered triple &lt;N,f,R&gt; where:
   * N is a finite, non-empty set of nodes
   * f is a (possibly partial) function from N to {i | W<sub>i</sub> &isin; S}, i.e. every node is labelled with exactly one token from the sentence (but nothing stops the same token labelling more than one node)
   * R is an irreflexive, rooted relation on N, i.e. no self-arcs, and there is exactly one element of N which is a source but not a target. 

---+++ Optional constraints

An 'acyclic' dependency structure over sentence S is a dependency structure &lt;N,f,R&gt; over S where:
   * if there is a sequence of R-arcs from node n<sub>1</sub> to node n<sub>2</sub>, then there is no sequence of R-arcs from n<sub>2</sub> to n<sub>1</sub>.

A dependency 'tree' over sentence S is an acyclic dependency structure &lt;N,f,R&gt; over S where:
   * every node is a target of at most one arc, i.e. no re-entrancy.

A 'projective' dependency tree over sentence S = w<sub>1</sub> w<sub>2</sub> ... w<sub>n</sub> is a dependency tree &lt;N,f,R&gt; over S, where:
   * for all n<sub>i,j,k</sub>&isin;N, if n<sub>i</sub>Rn<sub>k</sub> and f(n<sub>i</sub>) &lt; f(n<sub>j</sub>) &lt; f(n<sub>k</sub>), then n<sub>i</sub>R*n<sub>j</sub>, where R* is the reflexive transitive closure of R, i.e. no corssing dependencies.

A 'surjective' dependency structure over sentence S is a dependency structure &lt;N,f,R&gt; over S where:
   * f is a surjective function, i.e. every token in S labels at LEAST one node in N.

An 'injective' dependency structure over sentence S is a dependency structure &lt;N,f,R&gt; over S where:
   * f is an injective function, i.e. every token in S labels at MOST one node in N.

A 'bijective' dependency structure over sentence S is a surjective, injective dependency structure &lt;N,f,R&gt; over S, i.e. every token in S labels EXACTLY one node in N.

Most dependency parsers assume bijective, projective dependency trees. Recent work (based on the Prague Dependency Treebank and the Danish Dependency Treebank) has relaxed both the projective constraint (i.e. bijective dependency trees) and then the tree constraint (i.e. bijective acyclic dependency structures). There are good reasons for relaxing the surjective constraint (expletive pronouns) and the injective constraint (argument cluster coordination, noun modifier coordination).

<table border="1">
<tr><td>&nbsp;</td><th>proj tree</th><th>non-proj tree</th><th>acyclic non-tree</th><th>non-acyclic</th></tr>
<tr><th>bij</th><td>1</td><td>2</td><td>3</td><td>-</td></tr>
<tr><th>surj/non-inj</th><td>-</td><td>-</td><td>-</td><td>-</td></tr>
<tr><th>inj/non-surj</th><td>-</td><td>-</td><td>-</td><td>-</td></tr>
<tr><th>non-surj/non-inj</th><td>-</td><td>-</td><td>-</td><td>-</td></tr>
</table>

Note: it is also possible that we might want to relax the constraint that f is a function. Existence of multi-word expressions make the possibility of a 'total mapping' interesting.

---+++ Definition of typed dependency structures

A 'typed' dependency structure over sentence S = w<sub>1</sub> w<sub>2</sub> ... w<sub>n</sub> and vocabulary &Sigma; of dependency symbols is an ordered pair &lt;N,f,R,g&gt; where:
   * &lt;N,f,R&gt; is a dependency structure over S
   * g is a function from R to &Sigma;, i.e. every arc is labelled with exactly one dependency symbol.


---+++ Others

*Functionality* - for each word W and each dependency label T, there is no more than one dependency from W labelled with T 





-- Main.MarkMcConville - 14 Aug 2008

Topic revision: r6 - 01 Sep 2008 - 11:32:00 - MarkMcConville

TFlex

Webs
- ANC
- Android4EDU
- BDEteam
- CSTR
- CogsciTeach
- ComputingStrategy
- DICE
- DReaM
- DSOClets
- DatabaseGroup
- DistributedComputing
- DiyDice
- Dizzy
- DocsByUsers
- ECCOModelling
- ECHOES
- EyeTracking
- F4K
- FC3upgrade
- Ftlwiki
- INFBase
- Inf2aWiki
- JastProject
- LINCS
- LTG
- MATCH
- MLforNLP
- Main
- MusIC
- PG
- Prism
- RaviProgress
- SDP
- SDPGroup1
- SDPGroup10
- SDPGroup3
- SDPGroup5
- SDPGroup6
- SDPGroup7
- SDPGroup8
- SDPGroup9
- SEOC
- Sandbox
- SecurityProgramme
- SelfManaged
- Seminars
- StudioLab
- TFlex
- TWiki
- TheBeast
- Ug30708
- Vademecum
- VerbClasses
- WebExp
- YouTute

My links
My home page

edit

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback
This Wiki uses Cookies