In order to make the formalism general enough to include these parsers, we define items in terms of sets of partial dependency trees as shown in Figure 1.

Such spans cannot be represented by a single dependency tree .

Therefore, our formalism allows items to be sets of forests of partial dependency trees , instead of sets of trees.

In this paper, we investigate the problem of character-level Chinese dependency parsing, building dependency trees over characters.

In this formulation, a character-level dependency tree satisfies the same constraints as the traditional word-based dependency tree for Chinese, including proj ectiVity.

The character-level dependency trees hold to a specific word segmentation standard, but are not limited to it.

Chinese dependency trees were conventionally defined over words (Chang et al., 2009; Li et al., 2012), requiring word segmentation and POS-tagging as preprocessing steps.

Such annotations enable dependency parsing on the character level, building dependency trees over Chinese characters.

(a) a word-based dependency tree

The state-of—the-art dependency parsing techniques, the Eisner algorithm and maximum spanning tree (MST) algorithm, are adopted to parse an optimal discourse dependency tree based on the arc-factored model and the large—margin learning techniques.

Here we follow the arc factored method and define the score of a dependency tree as the sum of the scores of all the arcs in the tree.

Thus, the optimal dependency tree for T is a spanning tree with the highest score and obtained through the function DT(T,w): DT(T, w) = argmaxGT gVXRMO score(T, GT)

and maximum spanning tree (MST) algorithm are used respectively to parse the optimal projective and non-projective dependency trees with the large-margin learning technique (Crammer and Singer, 2003).

According to the definition, we illustrate all the 9 possible unlabeled dependency trees for a text containing three EDUs in Figure 2.

The dependency trees 1’ to 7’ are projective while 8’ and 9’ are non-projective with crossing arcs.

Since dependency trees contain much fewer nodes and on average they are simpler than constituency based trees, the current dependency parsers can have a relatively low computational complexity.

In our work, we adopt the graph based dependency parsing techniques learned from large sets of annotated dependency trees .

This paper proposes a nonparametric Bayesian method for inducing Part-of-Speech (POS) tags in dependency trees to improve the performance of statistical machine translation (SMT).

In particular, we extend the monolingual infinite tree model (Finkel et al., 2007) to a bilingual scenario: each hidden state (POS tag) of a source-side dependency tree emits a source word together with its aligned target word, either jointly (joint model), or independently (independent model).

Evaluations of J apanese-to-English translation on the NTCIR-9 data show that our induced Japanese POS tags for dependency trees improve the performance of a forest-to-string SMT system.

Specifically, the proposed model introduces bilingual observations by embedding the aligned target words in the source-side dependency trees .

We have assumed a completely unsupervised way of inducing POS tags in dependency trees .

Specifically, we introduce an auxiliary variable ut for each node in a dependency tree to limit the number of possible transitions.

Note that the dependency accuracies are measured on the automatically parsed dependency trees , not on the syntactically correct gold standard trees.

Since we focus on the word-level POS induction, each bunsetsu-based dependency tree is converted into its corresponding word-based dependency tree using the following heuristic9: first, the last function word inside each bunsetsu is identified as the head wordlo; then, the remaining words are treated as dependents of the head word in the same bunsetsu; finally, a bunsetsu-based dependency structure is transformed to a word-based dependency structure by preserving the head/modifier relationships of the determined head words.

9We could use other word-based dependency trees such as trees by the infinite PCFG model (Liang et al., 2007) and syntactic-head or semantic-head dependency trees in Nakazawa and Kurohashi (2012), although it is not our major focus.

In this step, we train a Japanese dependency parser from the 10,000 Japanese dependency trees with the induced POS tags which are derived from Step 2.

Experiments are carried out on the NTCIR-9 Japanese-to-English task using a binarized forest-to-string SMT system with dependency trees as its source side.

In this section we present a novel transition-based parser for projective dependency trees , implementing a dynamic parsing strategy.

A dependency tree for w is a directed, ordered tree Tu, = (Vw, Aw), where Vw = | z' E

Figure 2: A dependency tree with left spine (2114, 2112,2111) and right spine (2114, 7.07).

The training data set consists of pairs (212,149), where w is a sentence and A9 is the set of arcs of the gold (desired) dependency tree for 212.

We remark here that this abstraction also makes the feature representation more similar to the ones typically found in graph-based parsers, which are centered on arcs or subgraphs of the dependency tree .

Poon & Domingos (2009, 2010) induce a meaning representation by clustering synonymous lambda-calculus forms stemming from partitions of dependency trees .

USP defines a probabilistic model over the dependency tree and semantic parse using Markov logic (Domingos and Lowd, 2009), and recursively clusters and composes synonymous dependency treelets using a hard EM-like procedure.

Top: the dependency tree of the sentence is annotated with latent semantic states by GUSP.

GUSP produces a semantic parse of the question by annotating its dependency tree with latent semantic states.

Second, in contrast to most existing approaches for semantic parsing, GUSP starts directly from dependency trees and focuses on translating them into semantic parses.

To combat this problem, GUSP introduces a novel dependency-based meaning representation with an augmented state space to account for semantic relations that are nonlocal in the dependency tree .

GUSP starts with the dependency tree of a sentence and produces a semantic parse by annotating the nodes and edges with latent semantic states derived from the database.

As the algorithm generates dependency trees for partial translations left-to-right in decoding, it allows for efficient integration of both n-gram and dependency language models.

4. exploiting syntactic information: as the shift-reduce parsing algorithm generates target language dependency trees in decoding, dependency language models (Shen et al., 2008; Shen et al., 2010) can be used to encourage linguistically-motivated reordering.

5. resolving local parsing ambiguity: as dependency trees for phrases are memorized in rules, our approach avoids resolving local parsing ambiguity and explores in a smaller search space than parsing word-by-word on the fly in decoding (Galley and Manning, 2009).

Figure 1 shows a training example consisting of a (romanized) Chinese sentence, an English dependency tree , and the word alignment between them.

2.1 Dependency tree

We follow the definition of dependency graph and dependency tree as given in (McDonald and Nivre, 2011).

A dependency graph G for sentence 3 is called a dependency tree when it satisfies, (1) the nodes cover all the words in s besides the ROOT; (2) one node can have one and only one head (word) with a determined syntactic role; and (3) the ROOT of the graph is reachable from all other nodes.

For example, using the constituent-to-dependency conversion approach proposed by J ohansson and Nugues (2007), we can easily yield dependency trees from PCFG style trees.

We annotate a corpus of children’s stories with temporal dependency trees , achieving agreement (Krippendorff’s Alpha) of 0.856 on the event words, 0.822 on the links between events, and of 0.700 on the ordering relation labels.

For temporal dependency trees , we assume each operation costs 1.0.

It has been argued that graph-based models like the maximum spanning tree parser should be able to produce more globally consistent and correct dependency trees , yet we do not observe that here.

The temporal language in a text often fails to specify a total ordering over all the events, so we annotate the timelines as temporal dependency structures, where each event is a node in the dependency tree , and each edge between nodes represents a temporal ordering relation such as BEFORE, AFTER, OVERLAP 01‘ IDENTITY.

W6 construct an evaluation corpus by annotating such temporal dependency trees over a set of children’s stories.

0 We propose a new approach to characterizing temporal structure via dependency trees .

.70” is a sequence of event words, and 7r 6 H is a dependency tree 7r 2 (V, E) where:

o TREE E (OF —> H) is a function that extracts a dependency tree 7r from a final parser state CF

o c 2 (L1, L2, Q, E) is a parser configuration, where L1 and L2 are lists for temporary storage, Q is the queue of input words, and E is the set of identified edges of the dependency tree .

It consists of a set of unordered labelled syntactic dependency trees whose nodes are labelled with word forms, part of speech categories, partial morphosyntactic information such as tense and number and, in some cases, a sense tag identifier.

The chunking was performed by retrieving from the Penn Treebank (PTB), for each phrase type, the yields of the constituents of that type and by using the alignment between words and dependency tree nodes provided by the organisers of the SR Task.

Using this chunked data, we then ran the generator on the corresponding SR Task dependency trees and stored separately, the input dependency trees for which generation succeeded and the input dependency trees for which generation failed.

For instance, when generating sentences from dependency trees , as was proposed recently in the Generation Challenge Surface Realisation Task (SR Task, (Belz et al., 2011)), it would be useful to be able to apply error mining on the input trees to find the most likely causes of generation failure.

We adapt an existing algorithm for tree mining which we then use to mine the Generation Challenge dependency trees and identify the most likely causes of generation failure.

First, dependency trees are converted to Breadth—First Canonical Form whereby lexicographic order can apply to the word forms labelling tree nodes, to their part of speech, to their dependency relation or to any combination thereof3.

3For convenience, the dependency relation labelling the edges of dependency trees is brought down to the daughter node of the edge.

In the next section, we will show how to modify this algorithm to mine for errors in dependency trees .

We thus propose to combine the advantages of both, and present a novel constituency-to-dependency translation model, which uses constituency forests on the source side to direct the translation, and dependency trees on the target side (as a language model) to ensure grammaticality.

a novel constituency-to-dependency model, which uses constituency forests on the source side to direct translation, and dependency trees on the target side to guarantee grammaticality of the output.

Our new constituency-to-dependency model (Section 2) extracts rules from word-aligned pairs of source constituency forests and target dependency trees (Section 3), and translates source constituency forests into target dependency trees with a set of features (Section 4).

Figure 1 shows a word-aligned source constituency forest FC and target dependency tree De, our constituency to dependency translation model can be formalized as:

2.2 Dependency Trees on the Target Side

A dependency tree for a sentence represents each word and its syntactic dependents through directed arcs, as shown in the following examples.

dependency trees , as illustrated in Figure 1.

In a proj ective dependency tree , the yield of every subtree is a contiguous substring of the sentence.

But allowing non-projective dependency trees also makes parsing empirically harder, because it requires that we model relations between nonadjacent structures over potentially unbounded distances, which often has a negative impact on parsing accuracy.

The system Sp 2 (C,Tp,cs,Ct) is sound and complete for the set of projective dependency trees (over some label set L) and has been used, in slightly different variants, by a number of transition-based dependency parsers (Yamada and Matsumoto, 2003; Nivre, 2004; Attardi, 2006;

Given the simplicity of the extension, it is rather remarkable that the system Su 2 (G, Tu, cs, Gt) is sound and complete for the set of all dependency trees (over some label set L), including all non-projective trees.

For completeness, we note first that projectiv-ity is not a property of a dependency tree in itself, but of the tree in combination with a word order, and that a tree can always be made projective by reordering the nodes.

A dependency tree is a lightweight syntactic representation that attempts to capture functional relationships between words.

We define the set of legal dependency parse trees of at (denoted 34:10)) as the set of O-arborescences of D, i.e., we admit each arborescence as a potential dependency tree .

Let y 6 32(30) be a legal dependency tree for at; if the arc a = (i,j> E y, we refer to i as the parent of j (denoted i = 7t(j)) and j as a child of i.

A subgraph y = (V, B) is a legal dependency tree (i.e., y E y(m)) if and only if the following conditions are met:

Furthermore, the integer points of Z are precisely the incidence vectors of dependency trees in 32(30); these are obtained by replacing Eq.

Figure l: The dependency tree for sentence the boy will find it interesting

1.2 Dependency Trees

Dependency trees reveal long-distance relations between words.

In one kind, we keep dependency trees with a sub-root, where all the children of the sub-root are complete.

Figure 5: A dependency tree with flexible combination

Figure 1 shows a traditional dependency tree .

(2009) present a dependency-spanning tree algorithm for word ordering, which first builds dependency trees to decide linear precedence between heads and modifiers then uses an n-gram language model to order siblings.

two techniques: the first is dividing the entire dependency tree into one-depth sub-trees and solving linearization in sub-trees; the second is the determination of relative positions between dependents and heads according to dependency relations.

In Section 2, we describe the idea of dividing the realization procedure for an entire dependency tree into a series of sub-procedures for sub-trees.

A conditional log-linear model for the probability of a realization r given the dependency tree t, has the general parametric form

And Y(t) gives the set of all possible realizations of the dependency tree t.

In our dependency tree representations, dependency relations are represented as arcs pointing from a head to a dependent.

Figure 1 gives an example of dependency tree representation for the sentence:

Our sentence realizer takes such an unordered dependency tree as input, determines the linear order of the words

This is quite high, but still, it is one of the lowest among other more frequent tags, and thus verbs tend to be the roots of the dependency trees .

A random projective dependency tree is assigned to each sentence in the corpus.

For each sentence, we sample a new dependency tree based on all other trees that are currently in the corpus.

Parsing: Based on the collected counts, we compute the final dependency trees using the Chu-Liu/Edmonds’ algorithm (1965) for finding maximum directed spanning trees.

1The adjacent-word baseline is a dependency tree in which each word is attached to the previous (or the following) word.

Figure 1: Example of a dependency tree .

Figure 1 shows an example of a dependency tree .

The probability of the whole dependency tree T is the following:

A complete analysis of a sentence is given by a dependency tree : a set of dependencies that forms a rooted, directed tree spanning the words of the sentence.

Every dependency tree is rooted at a special “*” token, allowing the

A common strategy, and one which forms the focus of this paper, is to factor each dependency tree into small parts, which can be scored in isolation.

The first type of parser we describe uses a “first-order” factorization, which decomposes a dependency tree into its individual dependencies.

These parsing algorithms share an important characteristic: they factor dependency trees into sets of parts that have limited interactions.

By exploiting the additional constraints arising from the factorization, maximizations or summations over the set of possible dependency trees can be performed efficiently and exactly.

A crucial limitation of factored parsing algorithms is that the associated parts are typically quite small, losing much of the contextual information within the dependency tree .

The first parser, Model 0, factors each dependency tree into a set of grandchild parts—pairs of dependencies connected head-to-tail.

Given an input sentence x = wowl...wn, the goal of dependency parsing is to build a dependency tree as depicted in Figure 1, denoted by d = {(h,m) :0 S h S 71,0 < m S n},where (h,m) indicates a directed arc from the head word 21);, to the modifier mm, and we is an artificial node linking to the root of the sentence.

The graph-based method views the problem as finding an optimal tree from a fully-connected directed graph (McDonald et al., 2005; McDonald and Pereira, 2006; Carreras, 2007; K00 and Collins, 2010), while the transition-based method tries to find a highest-scoring transition sequence that leads to a legal dependency tree (Yamada and Matsumoto, 2003; Nivre, 2003; Zhang and Nivre, 2011).

In this work, we adopt the graph-based paradigm because it allows us to naturally derive conditional probability of a dependency tree (1 given a sentence X, which is required to compute likelihood of both labeled and unlabeled data.

As described previously, the score of a dependency tree given by a word-pair classifier can be factored into each candidate dependency edge in this tree.

The constituent trees in the two treebanks are transformed to dependency trees according to the head-finding rules of Yamada and Matsumoto (2003).

For a dependency tree with n words, only n —1 positive dependency instances can be extracted.

The English sentences are then parsed by an implementation of 2nd-ordered MST model of McDonald and Pereira (2006), which is trained on dependency trees extracted from WSJ.

Jiang and Liu (2009) refer to alignment matrix and a dynamic programming search algorithm to obtain better projected dependency trees .

Because of the free translation, the word alignment errors, and the heterogeneity between two languages, it is reluctant and less effective to project the dependency tree completely to the target language sentence.

y denotes the dependency tree for sentence x, and (i, j) E y represents a dependency edge from word :10,- to word as], where :10, is the parent of ccj.

Follow the edge based factorization method (Eisner, 1996), we factorize the score of a dependency tree s(x, y) into its dependency edges, and design a dynamic programming algorithm to search for the candidate parse with maximum score.

Where 3/ is searched from the set of well-formed dependency trees .

In this paper, we present a transition system for 2-planar dependency trees — trees that can be decomposed into at most two planar graphs — and show that it can be used to implement a classifier-based parser that runs in linear time and outperforms a state-of-the-art transition-based parser on four data sets from the CoNLL-X shared task.

One of the unresolved issues in this area is the proper treatment of non-projective dependency trees , which seem to be required for an adequate representation of predicate-argument structure, but which undermine the efficiency of dependency parsing (Neuhaus and Broker, 1997; Buch-Kromann, 2006; McDonald and Satta, 2007).

(2009) have shown how well-nested dependency trees with bounded gap degree can be parsed in polynomial time, the best time complexity for lexicalized parsing of this class remains a prohibitive 0(n7), which makes the practical usefulness questionable.

In this paper, we explore another characterization of mildly non-projective dependency trees based on the notion of multiplanarity.

Such a forest is called a dependency tree .

Projective dependency trees correspond to the set of structures that can be induced from lexicalised context-free derivations (Kuhlmann, 2007; Gaif-man, 1965).

Like context-free grammars, projective dependency trees are not sufficient to represent all the linguistic phenomena observed in natural languages, but they have the advantage of being efficiently parsable: their parsing problem can be solved in cubic time with chart parsing techniques (Eisner, 1996; Gomez-Rodriguez et al., 2008), while in the case of general non-projective dependency forests, it is only tractable under strong independence assumptions (McDonald et al., 2005b; McDonald and Satta, 2007).

Given a sentence X = (x1, ..., sun) (cc,- denotes each word in the sentence), we are interested in computing a directed dependency tree , Y, over X.

We assume that a directed dependency tree Y consists of ordered pairs (sci —> any) of words in X such that each word appears in at least one pair and each word has in-degree at most one.

Dependency trees are assumed to be projective here, which means that if there is an arc (cc,- —> 553-), then :0,- is an ancestor of all the words

For experiment on English, we used the English Penn Treebank (PTB) (Marcus et al., 1993) and the constituency structures were converted to dependency trees using the same rules as (Yamada and Matsumoto, 2003).

Figure l: A dependency tree

As mentioned in Section 3, a dependency tree Yj is represented as an adjacency matrix.

Thus we need to enforce some constraints in the adjacency matrix to make sure that each Yj satisfies the dependency tree constraints.

1We assume all the dependency trees are projective in our work (just as some other researchers do), although in the real word, most languages are non-projective.

We represent a dependency tree as a k x k adjacency matrix.

(2010) also mentioned their method yielded no improvement when applied to dependency trees in their initial experiments.

Genzel (2010) dealt with the data sparseness problem by using window heuristic, and learned reordering pattern sequence from dependency trees .

For English, we train a dependency parser as (Nivre and Scholz, 2004) on WSJ portion of Penn Tree-bank, which are converted to dependency trees using Stanford Parser (Marneffe et al., 2006).

2In our experiments, there are nodes with more than 10 children for English dependency trees .

For English-to-Japanese task, we extract features from Stanford English Dependency Tree (Marneffe et al., 2006), including lexicons, Part-of-Speech tags, dependency labels, punc-tuations and tree distance between head and dependent.

For J apanese-to-English task, we use a chunk-based Japanese dependency tree (Kudo and Matsumoto, 2002).

We use children to denote direct descendants of tree nodes for constituent trees; while for dependency trees , children of a node include not only all direct dependents, but also the head word itself.

Constituent tree is shown above the source sentence; arrows below the source sentences show head-dependent arcs for dependency tree ; word alignment links are lines without arrow between the source and target sentences.

For example, consider the node rooted at trying in the dependency tree in Figure 1.

Human usually compress sentences by dropping the intermediate nodes in the dependency tree .

0 We revealed that in compressing Japanese sentences, humans usually ignore syntactic structures; they drop intermediate nodes of the dependency tree and drop words within bansetsa,

For Japanese, dependency trees are trimmed instead of full parse trees (Takeuchi and Matsumoto, 2001; Oguro et al., 2002; Nomoto, 2008)1 This parsing approach is reasonable because the compressed output is grammatical if the

It treats a sentence as a sequence of words and structural information, such as a syntactic or dependency tree , is encoded in the sequence as features.

However, they still rely on syntactic information derived from fully parsed syntactic or dependency trees .

For Japanese sentences, instead of using full parse trees, existing sentence compression methods trim dependency trees by the discrim-inative model (Takeuchi and Matsumoto, 2001; Nomoto, 2008) through the use of simple linear combined features (Oguro et a1., 2002).

They simply regard a sentence as a word sequence and structural information, such as full parse tree or dependency trees , are encoded in the sequence as features.

However, they still rely on syntactic information derived from full parsed trees or dependency trees .

For a given tweet, we first convert its dependency tree for the interested target.

SVM-conn: The words, punctuations, emoti-cons, and #hashtags included in the converted dependency tree are used as the features for SVM.

RNN: It is performed on the converted dependency tree Without adaptive composition selection.

RNN is also based on the converted dependency tree .

The dependency tree indicates the dependency relations between words.

Algorithm 1 Convert Dependency Tree Input: Target node, Dependency tree Output: Converted tree 1: function CONV(7“) 2: E. <— SORT(dep edges connected with 7“) v <— 7“ for (7“ A 77/77 A 7“) in Er do if 7“ is head of u then 712 <— node with CONV(u), v as children else 712 <— node with v, CONV(u) as children

As illustrated in the Algorithm 1, we recursively convert the dependency tree starting from the target node.

(2008), to score entire dependency trees .

Let y be a dependency tree for ac and H be a set that includes the words that have at least one dependent.

For a dependency tree , we calculate the probability as follows:

Given the dependency trees , we estimate the probability distribution by relative frequency:

The basic idea behind is that we use the DLM to evaluate whether a valid dependency tree (McDonald and Nivre, 2007)

The parsing model searches for the final dependency trees by considering the original scores and the scores of DLM.

Let T(Gx) be the set of all the subgraphs of Ga; that are valid dependency trees (McDonald and Nivre, 2007) for sentence :10.

The formulation defines the score of a dependency tree y E T(Gx) to be the sum of the edge scores,

We add syntax to this process with a cohesion constraint based on a dependency tree for the source sentence.

The decoder stores the flat sentence in the original sentence data structure, and the head-encoded dependency tree in an attached tree data structure.

Next, we introduce our source dependency tree T. Each source token e,- is also a node in T. We define T(ei) to be the subtree of T rooted at 61-.

spanS 6-, T, am 2 min a -, max ak, ( z 1 > {j|€j€T(€i)} j {k|€k€T(€i)} Consider the simple phrasal translation shown in Figure 1 along with a dependency tree for the English source.

This algorithm was used to implement a soft cohesion constraint for the Moses decoder, based on a source-side dependency tree .

Since we require source dependency trees , all experiments test English to French translation.

English dependency trees are provided by Minipar (Lin, 1994).

Figure 1: An example dependency tree .

Dependency trees represent syntactic relationships through labeled directed edges between heads and their dependents.

For example, Figure 1 shows a dependency tree for the sentence, Economic news had little efi‘ect on financial markets, with the sentence’s root-symbol as its root.

In this paper, we will use the following notation: :13 represents a generic input sentence, and y represents a generic dependency tree .

It contains projective dependency trees that were automatically derived from the latest status of the French Treebank (Abeille and Barrier, 2004), which consists of constituency trees for sentences from the

Figure 1: French dependency tree for L’abus de biens sociaux fut de’nonce’ en vain (literally the misuse of assets social was denounced in vain, meaning The misuse of corporate assets was denounced in vain), containing two MWEs (in red).

In the dependency trees , there is no “node” for a MWE as a whole, but one node per MWE component (more generally one node per token).

While the realistic scenario of syntactic parsing with automatic MWE recognition (either done jointly or in a pipeline) has already been investigated in constituency parsing (Green et al., 2011; Constant et al., 2012; Green et al., 2013), the French dataset of the SPMRL 2013 Shared Task (Seddah et al., 2013) only recently provided the opportunity to evaluate this scenario within the framework of dependency syntax.2 In such a scenario, a system predicts dependency trees with marked groupings of tokens into MWEs.

The trees show syntactic dependencies between semantically sound units (made of one or several tokens), and are thus particularly appealing for downstream semantic-oriented applications, as dependency trees are considered to be closer to predicate-argument structures.

To our knowledge, the first works3 on predicting both MWEs and dependency trees are those presented to the SPMRL 2013 Shared Task that provided scores for French (which is the only dataset containing MWEs).

It can be viewed as a structured prediction problem, where a semantic parse is formed by partitioning the input sentence (or a syntactic analysis such as a dependency tree ) into meaning units and assigning each unit to the logical form representing an entity or relation (Figure 1).

Bottom: a semantic parse consists of a partition of the dependency tree and an assignment of its parts.

Recently, we developed the USP system (Poon and Domingos, 2009), the first unsupervised approach for semantic parsing.2 USP inputs dependency trees of sentences and first transforms them into quasi-logical forms (QLFs) by converting each node to a unary atom and each dependency edge to a binary atom (e.g., the node for “induces” becomes induces(e1) and the subject dependency becomes nsubj(e1, e2), where ei’s are Skolem constants indexed by the nodes.

USP (Poon and Domingos, 2009) parses the input text using the Stanford dependency parser (Klein and Manning, 2003; de Marneffe et al., 2006), learns an MLN for semantic parsing from the dependency trees , and outputs this MLN and the MAP semantic parses of the input sentences.

Given the dependency tree T of a sentence, the conditional probability of a semantic parse L is given by P7“(L|T) oc exp (2, wini(T, The MAP semantic parse is simply

OntoUSP uses the same learning objective as USP, i.e., to find parameters 6 that maximizes the log-likelihood of observing the dependency trees T, summing out the unobserved semantic parses L:

Unlike previous work, which primarily leverages syntactic analysis through dependency tree matching, we focus on improving the performance using models of lexical semantic resources.

Moreover, our best system also outperforms pervious work that makes use of the dependency tree structure by a wide margin.

Smith (2010) proposed a discriminative approach that first computes a tree kernel function between the dependency trees of the question and candidate sentence, and then learns a classifier based on the tree-edit features extracted.

Typically, the “ideal” alignment structure is not available in the data, and previous work exploited mostly syntactic analysis (e.g., dependency trees ) to reveal the latent mapping structure.

(2007) proposed a syntax-driven approach, where each pair of question and sentence are matched by their dependency trees .

Heilman and Smith (2010) proposed a discriminative approach that first computes a tree kernel function between the dependency trees of the question and candidate sentence, and then learns a classifier based on the tree-edit features extracted.

Fortunately we can simply convert DEP-DTs to obtain dependency trees between sentences.

After the document tree is obtained, we use a dependency parser to obtain the syntactic dependency trees of sentences.

We added two types of constraints to our model to extract a grammatical sentence subtree from a dependency tree:

recently transformed RST trees into dependency trees and used them for single document summarization (Hirao et al., 2013).

They formulated the summarization problem as a tree knapsack problem with constraints represented by the dependency trees .

Extracting a subtree from the dependency tree of words is one approach to sentence compression (Tomita et al., 2009; Qian and Liu, 2013; Morita et al., 2013; Gillick and Favre, 2009).

Our work stands in between traditional dependency tree parsing and deep linguistic processing.

There are two differences of the head word passing between our GR extraction and a “normal” dependency tree extraction.

These measures correspond to attachment scores (LASflJAS) in dependency tree parsing.

graphs than syntactic dependency trees .

Transition-based parsers utilize transition systems to derive dependency trees together with treebank-induced statistical models for predicting transitions.

Developing features has been shown crucial to advancing the state-of-the-art in dependency tree parsing (Koo and Collins, 2010; Zhang and Nivre, 2011).

For the protein pair IL-8 and CXCR1 in Figure 4, a dependency parser outputs a dependency tree shown in Figure 1.

From this dependency tree , we can extract a dependency path shown in Figure 5, which appears to be a strong clue in knowing that these proteins are mentioned as interacting.

CoNLL The dependency tree format used in the 2006 and 2007 CoNLL shared tasks on dependency parsing.

Figure 1 shows a dependency tree for the sentence “IL-8 recognizes and activates CXCRl.” An advantage of dependency parsing is that dependency trees are a reasonable approximation of the semantics of sentences, and are readily usable in NLP applications.

Figure l: CoNLL-X dependency tree

The algorithm proceeds until only one subtree left which is the dependency tree of the input sentence (see the example in figure 2).

Once an incorrect action is selected, it can never yield the correct dependency tree .

Finally, it returns the dependency tree built by the top action sequence in Bn_1.

The easy-first dependency parsing algorithm (Goldberg and Elhadad, 2010) builds a dependency tree by performing two types of actions LEFT(i) and RIGHT(i) to a list of subtree structures p1,.

Input: sentence x of n words, beam width s Output: one best dependency tree

4 As shown in (Goldberg and Nivre 2012), most transition-based dependency parsers (Nivre et al., 2003; Huang and Sagae 2010;Zhang and Clark 2008) ignores spurious ambiguity by using a static oracle which maps a dependency tree to a single action sequence.

To this end, we build a trie of dependency trees (which we call a tree-trie) by scanning all the dependency parses in the news training

Algorithm 2 STORE(T, I): store the dependency tree T in the tree-trie I. : /* Entry p0int/* L <— T.LINEARIZE() STORERECURSION(I.R00T(), L, 0) return M /* Procedures /* : procedure STORERECURSION(n, L, 0) ifo 2: L.LENGTH() then n.ADDTREESTRUCTURE(L.STRUCTURE()) return 10: if not n.HAsCHILD(L.TOKEN(o)) then 11: n.ADDCHILD(L.TOKEN(o))

First, each dependency tree (a) is linearized, resulting in a data structure that consists of two aligned sequences (b).

1) is formulated over weighted edges in a transformed dependency tree and is subject to a number of constraints.

We use a vector model based on dependency trees obtained from parsing the English Gigaword corpus (LDC2003T05).

We modify the dependency trees by “folding” prepositions into the edge labels to make the relation between a head word and the head noun of a prepositional phrase explicit.

Figure l: Co-occurrence graph of a small sample corpus of dependency trees .

Figure 1 shows the co-occurrence graph of a small sample corpus of dependency trees : Words are represented as nodes in the graph, possible dependency relations between them are drawn as labeled edges, with weights corresponding to the observed frequencies.

In the simplest case, a) would denote the frequency in a corpus of dependency trees of w occurring together with w’ in relation r. In the experiments reported below, we use pointwise mutual information (Church and Hanks, 1990) instead as it proved superior to

Second, dependency trees contain exactly one node per word, which contributes to cutting down the search space during parsing: indeed, the task of the parser is merely to connect existing nodes rather than hypothesizing new ones.

Figure 1: A dependency tree with directed edges going from heads to modifiers.

Their algorithm exploits the special properties of dependency trees to reduce the worst-case complexity of bilexical parsing, which otherwise requires 0(n4) for bilexical constituency-based parsing.

The parsing literature presents faster alternatives for both phrase-structure and dependency trees , e.g., 0(n) shift-reduce parsers and variants ((Ratnaparkhi, 1997; Nivre, 2003), inter alia).

The dominating solution in treebank design is to introduce artificial rules for the encoding of coordination structures within dependency trees using the same means that express dependencies, i.e., by using edges and by labeling of nodes or edges.

Even this simplest case is difficult to represent within a dependency tree because, in the words of Lombardo and Lesmo (1998): Dependency paradigms exhibit obvious difi‘iculties with coordination because, diflerently from most linguistic structures, it is not possible to characterize the coordination construct with a general schema involving a head and some modifiers of it.

In accordance with the usual conventions, we assume that each sentence is represented by one dependency tree , in which each node corresponds to one token (word or punctuation mark).

Apart from that, we deliberately limit ourselves to CS representations that have shapes of connected subgraphs of dependency trees .

We limit our inventory of means of expressing CSs within dependency trees to (i) tree topology (presence or absence of a directed edge between two nodes, Section 3.1), and (ii) node labeling (additional attributes stored insided nodes, Section 3.2).8 Further, we expect that the set of possible variations can be structured along several dimensions, each of which corresponds to a certain simple characteristic (such as choosing the leftmost conjunct as the CS head, or attaching shared modifiers below the nearest conjunct).

In Japanese, syntactic subtrees that contain the root of the dependency tree of the original sentence often make grammatical sentences.

In this joint model, we generate a compressed sentence by extracting an arbitrary subtree from a dependency tree of a sentence.

To avoid generating such ungrammatical sentences, we need to detect and retain the obligatory dependency relations in the dependency tree .

(2008) used WSJ section 19 from the Penn Treebank to extract DS to PS conversion rules and then produced dependency trees from WSJ section 22 for evaluation of their DS to PS conversion algorithm.

For comparison with their work, we conducted experiments in the same setting as theirs: using WSJ section 19 (1844 sentences) as Ops, producing dependency trees from WSJ section 22 (1700 sentences) as CD35, and using labeled bracketing f-scores from the tool

Our conversion method achieves 93.8% f-score on dependency trees produced from WSJ section 22, resulting in 42% error reduction over the previous best result for DS to PS conversion.

Previous DS to PS conversion methods built a converted tree by iteratively attaching nodes and edges to the tree with the help of conversion rules and heuristic rules, based on current head-dependent pair from a source dependency tree and the structure of the built tree (Collins et al., 1999; Covington, 1994; Xia and Palmer, 2001; Xia et al., 2008).

Moreover, they presented two strategies to solve the problem that there might be multiple conversion rules matching the same input dependency tree pattern: (1) choosing the most frequent rules, (2) preferring rules that add fewer number of nodes and attach the subtree lower.

(2012), adapted to dependency trees .

For dependency trees , the input corpus is permuted as follows:

For example in the trees in figure 2, assigning any other head than the root to the PRED nodes directly dominated by the root will result in invalid (cyclic and unconnected) dependency trees .

Figure 1: Transformation of dependency trees before comparison

Therefore we remove the leaf nodes in the case of phrase structure trees, and in the case of dependency trees we compare trees whose edges are unlabelled and nodes are labelled with the dependency relation between that word and its head; the root node receives the label 6.

From line 4-9, the objective is optimized with a generic optimization step in the subroutine climb(-, -, -, -, For each sentence we parse its dependency tree , and update the tree into the treebank (step 3).

The source sentences are then parsed by an implementation of 2nd-ordered MST model of McDonald and Pereira (2006), which is trained on dependency trees extracted from Penn Treebank.

The monolingual likelihood is similar to the optimization objectives of conventional unsupervised models, while the bilingually-projected likelihood is the product of the projected probabilities of dependency trees .

Z(d€ij) : 2 WM: )‘n ° f’n(d€ij 7 (2) y n Given a sentence E, parsing a dependency tree is to find a dependency tree D E with maximum probability PE:

Figure 2: Projecting a Chinese dependency tree to English side according to DPA.

The linear constraints in (3) will ensure that the arc variables for each sentence es encode a valid latent dependency tree , and that the f variables count up the features of these trees.

This generative model defines a joint distribution over the sentences and their dependency trees .

The constraints must declaratively specify that the arcs form a valid dependency tree and that the resulting feature values are as defined by the DMV.

To simplify the extraction process, we can convert auto-parsed constituency trees into dependency trees by using Penn2Malt.

2 From the dependency trees , we extract bigram lexical dependencies (2121,2122, L/R) where the symbol L (R) means that w1 (2112) is the head of ’LU2 (wl).

Formally, given a dependency tree 3/ of an input sentence :5, we can denote by H the set of words that have at least one dependent.

and Matsumoto, 2003) to convert the phrase structure syntax of the Treebank into a dependency tree representation, dependency labels were obtained via the ”Malt” hard-coded setting.8 We split the Treebank into a training set (Sections 2-2l), a development set (Section 22), and several test sets (Sections 0,9 l, 23, and 24).

Figure 2: An example of a labeled dependency tree .

In this paper we generalize the adjacency and dependency models by including the pointwise mutual information (Church and Hanks, 1900) between all pairs of words in the dependency tree:

tween the three words in the dependency tree:

For a given sentence, we first obtain its dependency tree .

Figure 1 gives a dependency tree example generated by Minipar (Lin, 1998).

Figure l: The dependency tree of the sentence “The style of the screen is gorgeous”.

contain non-projective dependency trees .

We denote sentences by ac and the corresponding dependency trees by y E 3?

is the set of valid (projective or non-projective) dependency trees for sentence cc.

The decoding problem consists of finding a valid dependency tree y 6 32(53) that maximizes the score s(:c,y) = 6 - f (:c,y) with parameters 6.

Specifically, we assume MINIPAR-style (Lin, 1993) dependency trees where nodes represent text expressions and edges represent the syntactic relations between them.

Dependency trees are a popular choice in RTE since they offer a fairly semantics-oriented account of the sentence structure that can still be constructed robustly.

Transformations create revised trees that cover previously uncovered target components in H. The output of each transformation, T1, is comprised of copies of the components used to construct it, and is appended to the discourse forest, which includes the dependency trees of all sentences and their generated consequents.

We assume that we have access to a dependency tree for H, a dependency forest for T and its discourse context, as well as the output of a perfect discourse processor, i.e., a complete set of both coreference and bridging relations, including the type of bridging relation (e. g. part-0f, cause).

Figure 1 shows two dependency trees for the sentence “the camera is great” in the camera domain and the sentence “the movie is excellent” in the movie domain, respectively.

Figure 1: Examples of dependency tree structure.

More specifically, we use the shortest path between a topic word and a sentiment word in the corresponding dependency tree to denote the relation between them.

If a projective dependency graph is connected, we call it a dependency tree , and if not, a dependency forest.

Head-comer parsing algorithm (Kay, 1989) creates dependency tree top-down, and in this our algorithm has similar spirit to it.

where t’ is a POS-tag, Tree is a correct dependency tree which eXists in Corpus, a function lmdescendant(Tree, t’) returns the set of the leftmost descendant node 1d of each nodes in Tree whose POS-tag is t’, and ld.t denotes a POS-tag of 1d.

The first column is the dependency parser with supervised training only and the last column is the constituent parser (after converting to dependency trees .)

Dependency trees are built by processing the words left-to-right and the classifier assigns a distribution over the actions at each step.

The baseline score b(w, a) can be a feature, yielding the dot product notation: S(w,a) = (a,<l>(a,w,sl,...,sm)) Our LM uses features from the dependency tree and part of speech (POS) tag sequence.

The analytical layer roughly corresponds to the surface syntax of the sentence; the annotation is a single-rooted dependency tree with labeled nodes.

Again, the annotation is a dependency tree with labeled nodes (Hajicova 1998).

The representation of the tectogrammatical annotation of a sentence is a rooted dependency tree .

“Dependency Tree Features” encode the grammatical relations in which each word is involved as a dependent.

For the “Syntactic Tree”, “Dependency Tree” and “Rule-Based” features, we also include features for the two words that precede and the two that follow the current word.

Dependency Tree Features in NP/VP/ADVP/ADJP chunk?

That is to say, despite them all being dependency treebanks, which annotate each sentence with a dependency tree , they subscribe to different annotation schemes.

A sample dependency tree from the French data set is shown in Figure 1.

For English, we used the Stanford parser (v1.6.8) (Klein and Manning, 2003) to convert the Wall Street J our-nal section of the Penn Treebank (Marcus et al., 1993) to basic dependency trees , including punctuation and with the copula verb as head in copula constructions.

In this paper, we adopt a model that posits correspondence between the words in the two sentences, defining it in loose syntactic terms: if two sentences are paraphrases, we expect their dependency trees to align closely, though some divergences are also expected, with some more likely than others.

A dependency tree on a sequence w 2 (ml, ..., wk) is a mapping of indices of words to indices of syntactic parents, 7p : {1, —> {0, ..., k}, and a mapping of indices of words to dependency relation types in £, 7] : {1, ..., k} —> £.

(2005), trained on sections 2—21 of the WSJ Penn Treebank, transformed to dependency trees following Yamada and Matsumoto (2003).

This structure is represented by a source sentence dependency tree .

The algorithm is as follows: given the source sentence and its dependency tree, during the translation process, once a hypothesis is extended, check if the source dependency tree contains a subtree T such that:

(Cherry, 2008) uses information from dependency trees to make the decoding process keep syntactic cohesion.

Let a(y) E {0, 1}” denote the incidence vector of tokens contained in the n-gram sequence y and ,6(z) E {0, 1}” denote the incidence vector of words contained in the dependency tree 2.

Linear constraints are introduced to produce dependency structures that are close to the optimal dependency trees .

In order to avoid cycles in the dependency tree , we include additional variables to establish single-commodity flow (Magnanti and Wolsey, 1994) between all pairs of tokens.

Since our system uses an off-the-shelf dependency parser, and semantic representations are obtained from simple rule-based conversion from dependency trees , there will be only one (right or wrong) interpretation in face of ambiguous sentences.

DCS trees has been proposed to represent natural language semantics with a structure similar to dependency trees (Liang et al., 2011) (Figure 1).

We obtain DCS trees from dependency trees , to bypass the need of a concrete database.

Given an input sentence x = wowl...wn and its POS tag sequence 1; = totl...tn, the goal of dependency parsing is to build a dependency tree as depicted in Figure l, denoted by d = {(h, m, l) : 0 g h 3 72,0 < m g n,l E L}, where (h,m, l) indicates an directed arc from the head word (also called father) w, to the modifier (also called child or dependent) wm with a dependency label l, and L is the label set.

To guarantee the efficiency of the decoding algorithms, the score of a dependency tree is factored into the scores of some small parts (subtrees).

During both the training and test phases, the target parser are inspired by the source annotations, and the score of a target dependency tree becomes

3.2 Non-Projective Dependency Tree CRFs

3.3 GE for Non-Projective Dependency Tree CRFs

In this paper we use a non-projective dependency tree CRF (Smith and Smith, 2007).