2 Related work

Many discourse frameworks have been proposed in the literature of discourse modeling. Among them, there are the cohesive devices described by Halliday and Hasan Reference Halliday and Hasan1976, Hobbs’ inventory of coherence relations based on abductive reasoning (Hobbs , Reference Hobbs1985), the Rhetorical Structure Theory (RST) proposed by Grosz and Sidner (Reference Grosz and Sidner1986) and Mann and Thompson's Reference Mann and Thompson1988 models, which aim to associate speakers’ intentions with their focus of attention in discourse, the Linguistic Discourse Model (LDM) proposed by Polanyi and Scha (Reference Polanyi and Scha1984) and Scha and Polanyi (Reference Polanyi1988), the Lexicalized Tree Adjoining Grammar for Discourse (D-LTAG) by Webber and Joshi (Reference Webber and Joshi1998), Forbes et al. (Reference Forbes, Miltsakaki, Prasad, Sarkar, Joshi and Webber2003), and Webber (Reference Webber2004), the Segmented Discourse Representation Theory (SDRT) by Asher and Lascarides Reference Asher and Lascarides2003, which provides a logically precise dynamic semantic interpretation, and the discourse model that associates discourse relations in a graph structure (Wolf and Gibson , Reference Wolf and Gibson2005). In the following, we will review a number of automatic systems that are based on these discourse frameworks. Readers are referred to Webber, Egg and Kordoni (Reference Webber, Egg and Kordoni2011) for a more complete review on discourse frameworks, algorithms for discourse structures, and discourse applications in language technology.

Mann and Thompson Reference Mann and Thompson1988 proposed RST which takes a nucleus-satellite view on rhetorical relations, in which the satellite text span plays a subordinate role to the main nucleus. RST defines a set of rhetorical relations as well as discourse schemas for the structural constituency arrangements of text. As the RST schemas are recursive, they enable the embedding of relations, leading to a tree structure of the text. RST falls into the category that associates discourse relations with text structures.

Marcu Reference Marcu1997 formalized an algorithm to automatically parse an unrestricted text into its discourse tree using the RST framework. He made use of cue phrases to split a sentence into elementary discourse units (edus), designed algorithms that are able to recognize discourse relations with or without the signals of cue phrases, and proposed four algorithms for determining the valid discourse tree giving the relations of adjacent edus.

Continuing in this vein, Soricut and Marcu Reference Soricut and Marcu2003 introduced probabilistic models to segment a sentence into edus, and to derive their corresponding sentence-level discourse structure, using lexical and syntactic features. They experimented with their models using the RST Discourse Treebank (RST-DT) corpus (Carlson, Marcu and Okurowski, Reference Carlson, Marcu and Okurowski2001), which is annotated in the RST framework and covers a small subset of the Wall Street Journal (WSJ), comprising 385 texts.

Huong, Abeysinghe and Huyck Reference Huong, Abeysinghe and Huyck2004 divided the discourse parsing process into two steps: First, they used syntactic information and cue phrases to segment sentences into edus and to generate discourse structures at sentence-level, and then generated text-level structure from the sentence-level ones in a constrained, bottom-up manner. They experimented with the RST-DT corpus and showed promising system performance on four different component tasks of (1) sentence-level edu segmentation, (2) sentence- and text-level relation connection of text spans, (3) relation orientation (i.e., nucleus vs. satellite), and (4) relation sense classification. In our system experiments, we also perform component-wise evaluations in a similar fashion.

Recently, duVerle and Prendinger Reference duVerle and Prendinger2009 made use of a support vector machine (SVM) approach, using a rich set of shallow lexical, syntactic, and structural features, to train two separate classifiers on identifying the rhetorical structures and labeling the rhetorical roles drawn from the RST-DT.

Wolf and Gibson Reference Wolf and Gibson2005 proposed to use more complex discourse structures of chain graphs to represent discourse relations. They released an annotation of 135 articles in a corpus called Discourse Graphbank, which includes annotations for both Explicit and Implicit relations.

Wellner et al. Reference Wellner, Pustejovsky, Havasi, Rumshisky and Sauri2006 used multiple knowledge sources to produce syntactic and lexico-semantic features, which were then used to automatically identify and classify Explicit and Implicit discourse relations in the Discourse Graphbank. Their experiments show that discourse connectives and the distance between two text spans have the most impact, and that event-based features also contribute to the performance. As they did not separate the experimental results for Explicit and Implicit relations, it is not possible to draw a conclusion on the performance on classifying Implicit relations.

Baldridge and Lascarides Reference Baldridge and Lascarides2005 proposed to represent the discourse structures of SDRT (Asher and Lascarides, Reference Asher and Lascarides2003) in headed trees and model them with probabilistic head-driven parsing techniques. They showed that dialogue-based features can improve the models in both segmentation and relation recognition.

Subba and Di Eugenio Reference Subba and Di Eugenio2009 presented a first-order learning approach to determine rhetorical relations between discourse segments and a modified shift-reduce parsing algorithm to build discourse parse trees. They showed improvements by exploiting compositional semantics and segment discourse structure data.

Webber Reference Webber2004 developed the Discourse Lexicalized Tree Adjoining Grammar (D-LTAG), which associates discourse relations with lexical elements. In D-LTAG, discourse relations are triggered by lexical elements (i.e., explicit or implicit discourse connectives), focusing on low-level discourse structures and semantics of monologues.

The PDTB is the first annotation that follows the lexically grounded, predicate-argument approach in the D-LTAG framework. The scope of the annotation is much larger in comparison with the RST-DT and the Discourse Graphbank, as it covers all Wall Street Journal sections in the PTB. With the advent of the PDTB, some recent works have attempted to recognize discourse connectives, relation senses, and argument spans in this newer corpus. In a preliminary study, Miltsakaki et al. Reference Miltsakaki, Dinesh, Prasad, Joshi and Webber2005 used syntactic features and a Maximum Entropy model to classify the relation senses of three explicit connectives – ‘since’, ‘while’, and ‘when’. Using syntactic features extracted from the parse trees, Pitler and Nenkova Reference Pitler and Nenkova2009 introduced a model that is able to disambiguate the discourse usage of connectives and recognize Explicit relations. They extracted syntactic features from the constituent parses with regard to the connectives, and showed that it significantly outperforms the baselines on a ten-fold cross validation.

Dinesh et al. Reference Dinesh, Lee, Miltsakaki, Prasad, Joshi and Webber2005 observed the connection between the syntactic structures and the annotation of argument spans for intra-sentential subordinating explicit connectives, and proposed an automatic algorithm that applies parse tree subtraction to locate such argument spans. Wellner and Pustejovsky Reference Wellner and Pustejovsky2007 and Wellner Reference Wellner2009 proposed machine learning approaches to identify the head words of the two arguments for discourse connectives in the PDTB. They utilized constituent features, dependency features, lexico-syntactic features, as well as the connective and its contextual features. Elwell and Baldridge Reference Elwell and Baldridge2008 followed this work with the use of general and connective-specific rankers and their combinations. Although their method is capable of locating the positions of the arguments, it is not able to label the span of these arguments. Prasad, Joshi and Webber (Reference Prasad, Joshi and Webber2010) proposed a set of heuristics to locate the position of the Arg1 sentences for Explicit relations in cases that the two arguments are not in the same sentence. Ghosh et al. Reference Ghosh, Johansson, Riccardi and Tonelli2011 designed the argument segmentation task for Explicit relations as a token-level sequence labeling task using conditional random fields (CRFs). They assumed gold standard discourse connectives and used a set of syntactic features in two classifiers designed for the two arguments.

Machine learning approaches have been applied on the PDTB to identify Implicit relations (i.e., discourse relations that are not signaled explicitly by discourse connectives such as ‘because’) in Pitler, Louis and Nenkova (Reference Pitler, Louis and Nenkova2009) and our previous work (Lin, Kan and Ng Reference Lin, Kan and Ng2009). Pitler et al. (Reference Pitler, Louis and Nenkova2009) performed classification of Implicit discourse relations using several linguistically informed features, such as word polarity, verb classes, and word pairs, showing an increase in performance over a random classification baseline. Our classifier considers the context of the two arguments, word pair information, as well as the arguments’ internal constituent and dependency parses, and the results yield a significant improvement over the majority baseline. Wang, Su and Tan (Reference Wang, Su and Tan2010) subsequently employed the tree kernel and added temporal ordering information to automatically recognize and classify Explicit and Implicit discourse relations. Zhou et al. Reference Zhou, Xu, Niu, Lan, Su and Tan2010 used a language model to automatically generate Implicit connectives and presented two methods to use these connectives for recognition of Implicit relations.

All of these research efforts on the PDTB can be viewed as isolated components of a full parser. Our work differs from these prior efforts in that we design a parsing algorithm that connects all of these subtasks into a single pipeline, and we implement this pipeline into an end-to-end parser in the PDTB style. Our parser attempts to recognize explicit discourse connectives, identify relation senses and argument spans for both Explicit and Non-Explicit relations, and recognize attribution spans for these relations. Component-wise, we introduce two novel approaches to accurately locate and label arguments, and to label attribution spans. We also significantly improve on the current state-of-the-art connective classifier with newly introduced features.

3 The Penn Discourse Treebank (PDTB)

The PDTB covers the set of Wall Street Journal articles in the PTB – approximately one million words – which is much larger than previous annotations such as the RST-DT. The PDTB adopts a binary predicate-argument view on discourse relations, where a connective acts as a predicate that takes two text spans as its arguments. The span to which the connective is syntactically attached is called Arg2, while the other is called Arg1. The PDTB provides annotation for each discourse connective and its two arguments. Example 1 in Figure 2 shows one Explicit relation extracted from the excerpt in Figure 1, where the connective is underlined, Arg1 is italicized, and Arg2 is bolded. Figure 1 is an excerpt containing two consecutive paragraphs extracted from WSJ-0034, which will be used as a running example throughout this paper.

Figure 1.

An excerpt from the article WSJ_0034. Each sentence is preceded with its superscripted sentence number. All discourse and non-discourse connectives are italicized, with discourse connectives further underlined. All relations annotated in this excerpt are also shown in Examples 1–9 in Figure 2.

Figure 2.

The nine discourse and non-discourse relations annotated on the excerpt in Figure 1. We underline connectives, and italicize Arg1s, and bold Arg2s. The last line of each example shows the relation sense and the file in the PDTB where the example is taken from. The relation sense is shown in the format of Level-1-class.Level-2-type.Level-3-subtype.

The PDTB also examined sentence pairs within paragraphs for discourse relations other than Explicit relations. Example 4 shows such an Implicit relation where the annotator inferred an implicit connective ‘for example’ that most intuitively connects Arg1 and Arg2. Some relations in the PDTB are alternatively lexicalized by non-connective expressions, i.e., expressions that are not in the pre-defined, closed set of discourse connectives. Example 5 is such an AltLex relation with the non-connective expression ‘Another concern’.

If no Implicit or AltLex relation exists between a sentence pair, annotators then checked whether an entity transition (EntRel) holds. EntRel captures cases where the same entity is realized in both sentences. If no EntRel is found, annotators labeled it as no relation (NoRel). Examples 2 and 10 show an EntRel and a NoRel relation, respectively. Explicit, Implicit, and AltLex relations are discourse relations, whereas EntRel and NoRel are non-discourse relations.Footnote ³

1. (10) A record date hasn't been set. Bell, based in Los Angeles, makes and distributes electronic, computer and building products.

   (NoRel – WSJ-0202)

For each discourse relation, the PDTB also provides annotation for attribution (i.e., the agent that expresses the argument) for Arg1, Arg2, and the relation as a whole. For example, the text span in the box in Example 3 – ‘declared San Francisco batting coach Dusty Baker after game two’ – is the attribution span for the relation.

1. (11) “I believe in the law of averages”,

   declared San Francisco batting coach Dusty Baker after game two.

   Implicit = accordingly“I'd rather see a so-so hitter who's hot come up for the other side than a good hitter who's cold.”

   (Contingency.Cause.Result – WSJ-2202)

Aside from annotating all discourse and non-discourse relations, the annotators of the PDTB provided a three-level hierarchy of relation senses. The first level consists of four major relation classes: Temporal, Contingency, Comparison, and Expansion. ‘Temporal’ is used when the events or situations in Arg1 and Arg2 are related temporally. The ‘Contingency’ relation is used to mark when one argument causally influences the other. A ‘Comparison’ relation results when the events in Arg1 and Arg2 are compared to highlight differences. ‘Expansion’ relations result when the semantics/discourse of one argument is continued or expanded in the other argument.

For each class, a second level of sixteen types is defined to provide finer semantic distinctions. They are listed in Table 1. For example, there are six types defined under the Expansion class: Conjunction, Instantiation, Restatement, Alternative, Exception, and List. A relation is labeled as ‘Restatement’ when one argument reiterates the semantics of the other argument. In contrast, ‘Conjunction’ is used when Arg2 provides additional information that is related to that in Arg1.

Table 1.

Level 1 classes and level 2 types of the discourse relations in the PDTB. Level 3 subtypes are not shown

A third level of subtypes is defined to specify the semantic contribution of each argument. Nine out of the sixteen types are refined into subtypes. For example, the sense labeled for Example 4 is Expansion. Restatement.Specification, meaning that there is a Restatement relation between Arg1 and Arg2, and Arg2 (instead of Arg1) is the argument that provides specific details. In this work, we follow our previous work (Lin et al., Reference Lin, Kan and Ng2009) and focus on the Level 2 types, as we feel that the Level 1 classes are too general and coarse-grained for downstream applications, while the Level 3 subtypes are too fine-grained and are only provided for some types.

4 System overview

We designed our parsing algorithm as a sequential pipeline to mimic the annotation procedure performed by the PDTB annotators. Figure 3 shows the pseudocode. The input to the parser is a free text T, whereas the output is the discourse structure of T in the PDTB style. The algorithm consists of three steps, which sequentially label Explicit relations, Non-Explicit relations, and attribution spans. Non-Explicit relations include all relations that are not Explicit, i.e., Implicit, AltLex, EntRel, and NoRel.

Figure 3.

Pseudocode for the discourse parsing algorithm.

We first give a quick overview of the parser's three steps. The first step is to identify discourse connectives, label their Arg1 and Arg2 spans, and recognize their Explicit relation senses. The parser starts by identifying all connective occurrences in T (line 2 in Figure 3), and labeling them as to whether they function as discourse connectives or not (lines 3–4). When a connective occurrence C is determined to be a discourse connective, its Arg1 and Arg2 spans are then identified, and the parser classifies the tuple (C, Arg1, Arg2) into one of the Explicit relation senses (lines 5–7). The second step then examines all adjacent sentence pairs within each paragraph. For each pair (S_i, S_j) that is not identified in any Explicit relation from Step 1, the parser then classifies the pair into EntRel, NoRel, or one of the Implicit/AltLex relation senses (lines 12–15). Following the PDTB annotation convention, our parser also ignores inter-paragraph relations, i.e., it ignores the adjacent sentence pair in between two paragraphs. In the third step, the parser first splits the text into clauses (line 21), and for each clause U that appears in any discourse relations (i.e., Explicit, Implicit, and AltLex relations; we term EntRel and NoRel as non-discourse relations), it checks whether U is an attribution span (lines 22–24). In this step, the parser also follows the PDTB representation to only identify attribution spans appearing in discourse relations. It will not examine spans that are outside the text of the detected discourse relations.

In our work, we adopt a sequential pipeline to parse a text, instead of following a top-down or bottom-up approach that is common in determining the RST discourse trees (Marcu , Reference Marcu1997). The reason for this design is twofold. First, the algorithm mimics the annotation procedure performed by the PDTB annotators, in which they labeled argument spans, identified relation senses, and annotated attribution spans in a step-by-step manner. Second, as the PDTB makes no commitments as to what kinds of high-level structures may be built up from the low-level units, we do not presume a tree-like structure or adopt a corresponding tree parsing algorithm. Note that this design allows a relation to be embedded within the argument of another relation, as well as an argument to be shared between two adjacent relations (i.e., the Arg1 of the current relation is the Arg2 of the previous relation). For instance, Example 6 is embedded in the Arg2 of Example 7, and sentence 4 is shared between Examples 3 and 4 as a common argument. Lee et al. Reference Lee, Prasad, Joshi, Dinesh and Webber2006 provides detailed discussion on such types of relation dependencies.

The pipeline of the parser is shown in Figure 4, which consists of the connective classifier, argument labeler, explicit classifier, non-explicit classifier, and attribution span labeler. The first three components correspond to step 1 in Figure 3, while the last two correspond to steps 2 and 3, respectively. There are two sub-components in the argument labeler: an argument position classifier and an argument extractor. A detailed description of these components follows in the next section.

Figure 4.

System pipeline for the discourse parser.

To illustrate the complete flow of the parsing algorithm, we look at how an ideal parser parses the excerpt of two paragraphs in Figure 1. In the first step, after comparing the text against the list of one hundred discourse connectives defined in the PDTB, ten connective occurrences are identified, which are italicized in Figure 1. The connective classifier then checks these occurrences and labels six of them as discourse connectives, as indicated by those underlined in Figure 1. The argument labeler follows by labeling the Arg1 and Arg2 spans for each discourse connective. In Example 6, the Arg1 and Arg2 spans for the connective ‘when’ labeled by the argument labeler are ‘for . . . 16%’ and ‘the . . . 13’. The tuple (when, ‘for . . . 16%’, ‘the . . . 13’) is next propagated to the explicit classifier, which classifies the relation sense as Synchrony. In the second step, the parser examines all adjacent sentence pairs within paragraphs 1 and 2 separately, i.e., the inter-paragraph sentence pair (S ₃, S ₄) is exempt from checking. Since there are Explicit relations already assigned to the pairs (S ₁, S ₂) in paragraph 1 and (S ₆, S ₇) and (S ₇, S ₈) in paragraph 2 (see Examples 1, 7, and 9), they are also exempt from further classification. The non-explicit classifier then classifies the remaining pairs (S ₂, S ₃), (S ₄, S ₅), and (S ₅, S ₆) as EntRel, Implicit, and AltLex relations, respectively, as shown in Examples 2, 4, and 5. In the last step, the attribution span labeler will examine all discourse relations to label their attribution spans. As there are no such spans in Figure 1, the reader is referred to Example 11 for a sentence with an attribution span that would be labeled.

We now refine this overview by detailing the individual components’ structure and processing workflow.

5 Components

Our system takes a fully data-driven, supervised learning approach. As such, the annotated data are processed into binary feature vectors that are suitable input to a maximum entropy learning model. In the following descriptions, we describe the component designs as well as the derived feature classes.

5.2 Argument labeler

The parser now labels the Arg1 and Arg2 spans of every connective labeled in the previous step as a discourse connective, in two steps: (1) identifying the locations of Arg1 and Arg2, and (2) labeling the spans. We note that Arg2 is the argument with which the connective is syntactically associated, and thus its position is fixed once we locate the connective. The remaining problem of the first step is in identifying the location of Arg1. We implement this as a classification task to recognize the relative position of Arg1, with respect to the connective (line 2 in Figure 5). According to the different relative positions of Arg1, the argument extractor then attempts to extract the Arg1 and Arg2 spans in the second step (lines 5–11 in Figure 5). Figure 5 gives the pseudocode for the argument labeler, which corresponds to line 6 in Figure 3 and is further discussed in the following.

Figure 5.

Pseudocode for the argument labeler, which corresponds to line 6 in Figure 3.

5.2.1 Argument position classifier

Prasad et al. Reference Prasad, Dinesh, Lee, Miltsakaki, Robaldo, Joshi and Webber2008 described the breakdown of positions of Arg1 in their study of the PDTB annotations. They showed that Arg1 can be located within the same sentence as the connective (SS), in some previous sentence of the connective (PS), or in some sentence following the sentence containing the connective (FS). When Arg1 is located in some previous sentence, it can either be in the immediately previous sentence of the connective (IPS), or in some non-adjacent previous sentence of the connective (NAPS). Example 8 is a relation where the arguments and connective appear in the same sentence, while Example 1 shows a case in which Arg2 immediately follows Arg1. The distribution from Prasad et al. Reference Prasad, Dinesh, Lee, Miltsakaki, Robaldo, Joshi and Webber2008 shows that 60.9 percent of Explicit relations are SS, 39.1 percent are PS, and less than 0.1 percent are FS (only eight instances).

Motivated by this observation, we design an argument position classifier to identify the relative position of Arg1 as SS or PS. We ignore FS since there are too few training instances. We notice that the connective string itself is a very good feature. For example, when the connective token is ‘And’ (i.e., ‘and’ with its first letter capitalized, as in Example 1), it is a continuation from the previous sentence and thus Arg1 is likely in PS; whereas when the connective token is in lowercase ‘and’, Arg1 is likely the clause at the left-hand side of ‘and’ and thus it is in SS (Example 8). Furthermore, some connectives always take a particular position. For example, ‘when’ always indicates an SS case, whereas ‘additionally’ always indicates PS.

Aside from the connective string, we also use contextual feature classes in the classifier for connective C with its first and second previous words prev ₁ and prev ₂. The list below gives the feature classes used in our supervised classifier.

• — C string

• — position of C in the sentence: start, middle, or end

• — C POS

• — prev ₁

• — prev ₁ POS

• — prev ₁ + C

• — prev ₁ POS + C POS

• — prev ₂

• — prev ₂ POS

• — prev ₂ + C

• — prev ₂ POS + C POS

After the relative position of Arg1 is identified, the result is propagated to the argument extractor, which employs different strategies to extract the Arg1 and Arg2 spans, depending on whether the result is SS or PS.

5.2.2 Argument extractor

When the relative position of Arg1 is classified as PS from the previous stage, Arg1 is located in one of the previous sentences of the connective, while Arg2 is in the same sentence as the connective. A majority classifier labels the immediately previous sentence as Arg1, which already gives an F ₁ of 76.90 percent under the gold standard setting on the entire PDTB. In this paper, we focus on extracting the argument spans for the SS case and do not focus on identifying the Arg1 sentences for the PS case. As such, we employ the majority classifier as our classifier for the PS case. Next, we describe our approach to extract the arguments for the SS case in detail.

When Arg1 is classified as in SS, this means that Arg1, Arg2, and the connective itself are in SS. This can be further divided into four situations depending on the overlap and position of two arguments in the sentence:

1. (1) Arg1 precedes Arg2,

2. (2) Arg2 precedes Arg1,

3. (3) Arg2 is embedded within Arg1, or

4. (4) Arg1 is embedded within Arg2.

These four situations are illustrated by Examples 8, 6, 12, and 13, respectively. One possible approach is to split the sentence into clauses before deciding which clause is Arg1 or Arg2. The problem with this approach is that it is not able to recognize the last two cases, where one argument divides the other into two parts. Another challenge is to exclude the text spans that are not in the relation, such as the span ‘It's the . . . American’ in Example 12.

1. (12) It's the petulant complaint of an impudent American whom Sony hosted for a year whilehe was on a Luce Fellowship in Tokyo – to the regret of both parties.

   (Temporal.Synchrony – WSJ-0037)

2. (13) The prime minister, whose hair is thinning and gray and whose face has a perpetual pallor, nonethelesscontinues to display an energy, a precision of thought and a willingness to say publicly what most other Asian leaders dare say only privately.

   (Comparison.Concession.Contra-expectation – WSJ-0296)

Dinesh et al. Reference Dinesh, Lee, Miltsakaki, Prasad, Joshi and Webber2005 showed that Arg1 and Arg2 in the same sentence for subordinating connectives are always syntactically related as shown in Figure 6(a), where Arg1 and Arg2 nodes are the lowest nodes that cover the respective spans. They demonstrated that a rule-based algorithm is capable of extracting Arg1 and Arg2 in such cases for subordinating connectives. By using tree subtraction, the third case mentioned above can be easily recognized and the text spans that are not in the relation can be excluded. In Figure 6(a), Span 3 is labeled as Arg2 that divides Arg1 into two noncontinuous Spans 2 and 4. The out-of-relation spans (Spans 1 and 5) are also excluded by subtracting the subtree root at the Arg1 node from the entire tree starting from the root.

Figure 6.

Syntactic relations of Arg1 and Arg2 subtree nodes in the parse tree. (a) Arg2 contains span 3 that divides Arg1 into two spans 2 and 4. (b)–(c) Two syntactic relations of Arg1 and Arg2 for coordinating connectives.

However, dealing with only the subordinating connectives is not sufficient. Subordinating connectives only take up 40.93 percent for SS cases; the percentages of coordinating connectives and discourse adverbials in the whole PDTB for SS cases are 37.50 percent and 21.57 percent, respectively. We observe that coordinating connectives (‘and’, ‘or’, ‘but’, etc.) usually constrain Arg1 and Arg2 to be syntactically related in one of the two ways as shown in Figures 6(b)–(c), where CC is the connective POS. Example 12 and Figure 7 give an example to illustrate Figure 6(c). Discourse adverbials do not demonstrate such syntactic constraints as strongly as subordinating and coordinating connectives do, but their Arg1 and Arg2 are also syntactically bound by the positions of and path between the two argument nodes. For example, Figure 8 shows the syntactic relation of the Arg1 and Arg2 nodes for the discourse adverbial ‘still’ in Example 12. Furthermore, the rule-based algorithm in Dinesh et al. (Reference Dinesh, Lee, Miltsakaki, Prasad, Joshi and Webber2005) does not recognize the fourth case where the Arg1 span is embedded within the Arg2 span. The ratio of the third case to the fourth case occurrences in the entire PDTB corpus is approximately 1:1. Thus, we believe that the fourth case also needs to be taken care of.

1. (14) The figures in both reports were adjusted to remove the effects of usual seasonal patterns, butweren't adjusted for inflation.

   (Comparison.Contrast – WSJ-0036)

2. (15) The ultimate result came in Hymowitz v. Lilly, where the highest New York court expanded the market-share approach for the first time

   to say

   that drug makers that could prove Mindy Hymowitz's mother didn't use their pill muststillpay their share of any damages.

   (Comparison.Concession.Contra-expectation – WSJ-0130)

Figure 7.

The parse tree for Example 12 to illustrate Figure 6(c).

Figure 8.

Part of the parse tree for Example 12 with Arg1 and Arg2 nodes labeled.

Given these observations, we design an automatic argument node identifier to first identify the Arg1 and Arg2 subtree nodes within the sentence parse tree for all subordinating connectives, coordinating connectives, and discourse adverbials; and then apply tree subtraction to extract the Arg1 and Arg2 spans. The argument node identifier labels each internal node (except the POS node) of the tree with three probabilities: functioning as Arg1-node, Arg2-node, and None. The internal node with the highest Arg1-node probability is chosen as the Arg1 node, and likewise for the Arg2 node. If the Arg1 node is the ancestor of the Arg2 node, the subtree under the Arg2 node is then subtracted from the Arg1 subtree to obtain the Arg1 span, and conversely when the Arg2 node is the ancestor of the Arg1 node. Motivated by the observed syntactic properties, we use the following feature classes for node N under consideration with regard to connective C:

• — C string

• — C's syntactic category: subordinating, coordinating, or discourse adverbial

• — number of left siblings of C

• — number of right siblings of C

• — the path P of C's parent → N

• — the path P and whether the number of C's left sibling is greater than one

• — the relative position of N to C: left, middle, or right

The syntactic category (subordinating, coordinating, or discourse adverbial) of the connective is a useful clue of the locations of the Arg1 and Arg2 nodes. We obtain the corresponding categories for the connectives from the list provided in Knott (Reference Knott1996). Appendix C shows the list of discourse connectives and their syntactic categories from Knott's thesis. The path from C's parent node to node N under consideration is also an informative feature, as it reflects how N is related to C syntactically. The following are two paths for the actual Arg2 node and the MD node in Figure 8:

• RB ↑ ADVP ↑ VP

• RB ↑ ADVP ↑ VP ↓ MD

The relative position of N to C is medial when N is on the path of C to root; it can also be left or right depending on whether it is located on the left- or right-hand side of this path. This feature also models to some extent the syntactic relation of C and N. To label each internal node with three probabilities, we adopt a maximum entropy classifier, as it is capable of estimating class probabilities.

To illustrate how the argument position classifier and argument extractor work together to label arguments, let us look at Example 12. After examining the features for the connective ‘while’, the argument position classifier will decide that Arg1 and Arg2 are in SS, and pass it to argument extractor. Since the class is SS, the argument extractor invokes the argument node identifier to locate the internal node that covers the Arg1 span (i.e., ‘whom Sony . . . both parties’) and that covers Arg2 and the connective (i.e., ‘while he . . . in Tokyo’). Finally, tree subtraction is applied to clean up and remove the Arg2 span from the Arg1 span.

5.4 Non-Explicit classifier

The PDTB also provides annotation for Implicit and AltLex relations, EntRel, and otherwise no relation (NoRel), which are lumped together as Non-Explicit relations. The Non-Explicit relations are annotated for all adjacent sentence pairs within paragraphs. If there is already an Explicit relation from the previous step between two adjacent sentences, they are exempt from further examination.

Similar to the explicit classifier, we adopt the Level 2 types for Implicit and AltLex relations. As there are too few training instances for Condition, Pragmatic Condition, Pragmatic Contrast, Pragmatic Concession, and Exception relations (in total only nine training instances), these five types are removed, resulting in eleven Level 2 types. Thus, our Non-Explicit classifier assigns candidate sentence pairs to one of the thirteen types (eleven Level 2 types plus EntRel and NoRel). We apply the three feature classes from our previous work (Lin et al., Reference Lin, Kan and Ng2009):

• — constituent parse features

• — dependency parse features

• — word-pair features

Constituent parse and dependency parse features include production rules and dependency rules from the parse trees of the arguments. From our observation of the PDTB relations, the syntactic structure within one argument may constrain the relation sense and the syntactic structure of the other argument. For Arg1 and Arg2 of each relation, we extract the corresponding constituent and dependency parses. As an argument can be a single sentence or a clause, this results in a whole constituent/dependency tree or parts of a tree. From these parses, we extract all possible production rules and dependency rules, and represent each rule as three binary features to check whether it appears in Arg1, Arg2, or both arguments. For instance, the production rules for the subtree in Figure 9(a) are S → NP VP, NP → PRP, PRP → ‘We’, etc.; the dependency rules for the dependency subtree in Figure 9(b) are ‘had’ ← nsubj dobj, ‘problems’ ← det nn advmod, ‘at’ ← dep. Word-pair features are word pairs in which one word is extracted from Arg1 and another from Arg2, i.e., all (w_i, wj) where w_i is a word from Arg1 and w_j is a word from Arg2.

Figure 9.

(a) A constituent subtree, and (b) a dependency subtree for Arg1 of an Implicit relation from WSJ-2224.

AltLex relations are very similar to their counterpart Explicit relations, except that they are alternatively lexicalized by some non-connective expressions, instead of being expressed by one of the one hundred PDTB pre-defined discourse connectives. Such non-connective expressions are usually attached at the beginning of Arg2 (e.g., such as ‘Another concern’ in Arg2 of Example 5). To distinguish AltLex relations, we use three feature classes that represent the first three stemmed terms of Arg2. For the example above, the features that are turned on will be term₁=another, term₂=concern, and term₃=the.

6 Evaluation

In all of our experiments, we follow the recommendation from PDTB-Group (2007) to use Sections 02– 21 in the PDTB for training, Section 22 for development, and Section 23 for testing. All classifiers are trained with the OpenNLP maximum entropy packageFootnote ⁴ without smoothing and with one hundred iterations.

For each component, the experiments are carried out when there is no error propagated from the previous components (i.e., using gold standard annotation for the previous components), and also when there is error propagation. As the PDTB was aligned with the PTB, we can either directly use the gold standard parse trees and sentence boundaries from the PTB files, or we can apply an automatic parser and sentence splitter. The experiments are carried out under three settings for each component:

1. (1) GS + no EP: using gold standard (GS) parses and sentence boundaries without error propagation (EP).

2. (2) GS + EP: using GS with EP.

3. (3) Auto + EP: using both automatic parsing and sentence splitting (Auto) with EP.

Thus, GS + no EP corresponds to a clean, per-component evaluation, whereas the Auto + EP setting assesses end-to-end fully automated performance (as would be expected on new and unseen text input). We use the NIST text segmenterFootnote ⁵ to insert sentence boundaries and the Charniak parserFootnote ⁶ to parse sentences in Auto setting. As there are no gold standard dependency parses for the PTB files, we employ the Stanford dependency parserFootnote ⁷ in both GS and Auto settings.

The main focus of this work is designing an end-to-end discourse parser joined by all components and not on improving a specific component. As such, we only re-implement Pitler and Nenkova's (Reference Pitler, Louis and Nenkova2009) system to compare with our connective classifier. For other components, we do not re-implement other systems mentioned in the related work section.

6.1 Results for connective classifier

On the connective classifier task, Pitler and Nenkova Reference Pitler and Nenkova2009 (hereafter, P&N) reported an accuracy of 96.26 percent and F ₁ of 94.19 percent with a ten-fold cross validation (CV) on Sections 02– 22. To compare with P&N, we also run a ten-fold CV on Sections 02– 22 using their features and obtain replicated accuracy of 96.09 percent and replicated F ₁ of 93.57 percent. Adding in our lexico-syntactic and path features, the performance is increased to 97.25 percent accuracy and 95.36 percent F ₁, yielding improvements of 0.99 percent and 1.17 percent over the reported results and 1.16 percent and 1.79 percent over the replicated results. A paired t-test shows that the improvements over our replication of P&N's results are significant with p<0.001.Footnote ⁸

In Table 2, we report results from the connective classifiers trained on Sections 02– 21 and tested on Section 23. As there is no error propagated into the connective classifier since it is the first component, we report results for just the GS and Auto settings. The second and third columns show the accuracy and F ₁ using the features of P&N, whereas the last two columns show the results when we add in the lexico-syntactic and path features (+new). Introducing new features significantly (all with p<0.001) increases the accuracy and F ₁ by 2.04 percent and 3.01 percent under the GS setting, and 1.81 percent and 2.62 percent under the Auto setting. This confirms the usefulness of integrating the contextual and syntactic information. As the connective classifier is the first component in the pipeline, good performance is crucial to mitigate the effect of cascaded errors downstream.

Table 2.

Results for the connective classifier. No EP as this is the first component in the pipeline

When we look into the incorrectly labeled connectives, we find that the connective with the highest number of incorrect labels is ‘and’ (eight false negatives and four false positives for the GS setting). This is not surprising, as ‘and’ is always regarded as an ambiguous connective. A solution to this problem is to separately train one model for each highly ambiguous connective and another generic model to identify the remaining connectives.

6.2 Results for argument labeler

We next perform evaluation on the argument position classifier, and report micro precision, recall, and F ₁, as well as the per-class F ₁, in Table 3. The GS + no EP setting gives a high F ₁ of 97.94 percent, which drops to 3.59 percent and another 2.26 percent when error propagation and full automation are added in. The per-class F ₁ shows that the performance degradation is mostly due to the SS class (Arg1 and Arg2 in SS): the drops for SS are 5.36 percent and 3.35 percent, compared with 1.07 percent and 0.68 percent for PS. When we look into the contingency table for the GS + EP setting, we note that out of the thirty-six false positives propagated from the connective classifier, thirty of them are classified as SS; for the Auto + EP setting, there are forty-six out of fifty-two classified as SS. This shows that the difference in the performance drops for SS and PS is largely due to error propagation from the connective classifier, and not to the classes themselves. Although not strictly comparable, these results are consistent with the results in Prasad et al. (Reference Prasad, Joshi and Webber2010), which reported an accuracy of 93 percent on classifying discourse adverbials into intra- and inter-sentential. Three feature classes were used in Prasad et al. (Reference Prasad, Joshi and Webber2010): connective head, connective position, and syntactic path from the connective to the root of the sentence.

Table 3.

Results for the argument position classifier

We next evaluate the performance of the argument extractor. Table 4 illustrates the results of identifying the Arg1 and Arg2 subtree nodes for the SS case for the three connective categories. The last column shows the Arg1 & Arg2 F ₁ which requires both Arg1 and Arg2 nodes to be identified correctly. We only show the results for the GS + no EP setting. As expected, Arg1 and Arg2 nodes for subordinating connectives are the easiest ones to identify and give a high Arg2 F ₁ of 97.93 percent and a Arg1 & Arg2 Level F ₁ of 86.98 percent. We note that the Arg1 F ₁ and Arg2 F ₁ for coordinating connectives are the same, which is unexpected, as we expect Arg2 nodes to be easier to classify since Arg2 and the connective are syntactically associated. Error analysis shows that the Arg2 spans for coordinating connectives tend to include extra text that causes the Arg2 nodes to move lower down in the parse tree. For example, “. . . and Mr. Simpson said he resigned in 1988” contains the extra span “Mr. Simpson said” which causes the Arg2 node (which covers “he resigned in 1988”) moving two levels down the tree. The system erroneously labels “Mr. Simpson . . . 1988” as Arg2.

Table 4.

Results for identifying the Arg1 and Arg2 subtree nodes for the SS case under the GS + no EP setting for the three categories

Also as we discussed, discourse adverbials are difficult to identify as their Arg1 and Arg2 nodes are not strongly bound in the parse trees. However, as they do not take up a large percentage in the test data (only 5.38 percent of the test data is for identifying the Arg1 and Arg2 nodes for discourse adverbials under the GS + no EP setting), they do not lead to a large degradation as shown in the last row of the overall performance of the three categories.

Miltsakaki, Prasad, Joshi and Webber Reference Miltsakaki, Prasad, Joshi and Webber2004 reported human agreements on both exact and partial matches to be 90.2 percent and 94.5 percent, respectively. We follow this work and report both exact and partial matches. When checking an exact match, we require two spans to match identically, excluding any leading and ending punctuation symbols. A partial match is credited if there is any overlap between the verbs and nouns of the two spans. The results for the overall performance for both SS and PS cases are shown in Table 5. The GS + no EP setting gives a satisfactory F ₁ of 86.24 percent for partial matching on Arg1 & Arg2 F ₁. On the other hand, the results for exact matching are much lower than the human agreement. In Miltsakaki et al.'s (Reference Miltsakaki, Prasad, Joshi and Webber2004) work, most disagreements for exact match were reported to come from partial overlaps which do not show significant semantic difference. Similarly, in our analysis, we observed that most misses are due to small portions of text being deleted from or added to the spans by the annotators to follow the minimality principle. The minimality principle states that the annotation should include in the argument the minimal span of text that is sufficient for the interpretation of the relation. This requires deep semantic analysis and poses difficulties for machines to follow.

Table 5.

Overall results for argument extractor

6.3 Results for explicit classifier

Following the pipeline, we then evaluate the explicit classifier, with its performance shown in Table 6. Recall that human agreement on Level 2 types is 84.00 percent and a baseline classifier that uses only connectives as features already yields an F ₁ of 86.00 percent under the GS + no EP setting on Section 23. Adding our new features improves F ₁ to 86.77 percent (but which is not a statistically significant improvement). With full automation and error propagation, we obtain an F ₁ of 80.61 percent. Pitler and Nenkova Reference Pitler and Nenkova2009 show that using the same syntactic features as their connective classifier is able to improve the explicit classifier on a ten-fold cross validation on Sections 02– 22. We have trained the classifier on Sections 02– 21 using their features and tested on Section 23, but it actually performs worse than the baseline. Therefore, we do not include their features in the explicit classifier.

Table 6.

Results for explicit classifier

6.4 Results for non-explicit classifier

For the non-explicit classifier, a majority class baseline that labels all instances as EntRel yields an F ₁ in the low 20s, as shown in the last column of Table 7. The percentage of EntRel is slightly higher than the most frequent Implicit Cause relations (21.34 percent vs. 21.24 percent in Implicit relations). A single component evaluation (GS + no EP) shows a micro F ₁ of 39.63 percent. Although the F ₁ scores for the GS + EP and Auto + EP settings are unsatisfactory, they still significantly (p<0.01) outperform the majority class baseline by about 6 percent. This performance is in line with the difficulties of classifying Implicit relations discussed in detail in our previous work (Lin et al., Reference Lin, Kan and Ng2009).

Table 7.

Results for non-explicit classifier

6.5 Results for attribution span labeler

The final component, the attribution span labeler, is evaluated under both partial and exact match, similar to the argument extractor. From Table 8, we see that the GS + no EP setting achieves F ₁ scores of 79.68 percent and 65.95 percent for partial and exact matches, respectively. When error propagation is introduced, the degradation of F ₁ is largely due to the drop in precision. This is not surprising as at this point the test data contains a number of false positives propagated from the previous components. This has an effect on the precision calculation but not recall (the recall scores do not change). When full automation is further added, the degradation is largely due to the drop in recall. This is because the automatic parser introduces noise that causes errors in the clause splitting step.

Table 8.

Results for the attribution span labeler

6.6 Overall performance

In order to evaluate the whole pipeline, we look at the Explicit and Non-Explicit relations that are correctly identified. We define a relation as correct if its relation sense is classified correctly, and both its Arg1 and Arg2 are partially or exactly matched. The overall performance is shown in Table 9. Under partial matching, the GS + EP setting gives an overall system F ₁ of 46.80 percent, while under exact matching, it achieves an F ₁ of 33.00 percent. Auto + EP gives 38.18 percent F ₁ for partial match and 20.64 percent F ₁ for exact match. A large portion of the misses comes from the Non-Explicit relations, as these are more difficult to classify in comparison with the Explicit relations. The GS + EP F ₁ is close to the system F ₁ of 44.3 percent of an RST parser reported in duVerle and Prendinger (Reference duVerle and Prendinger2009).

Table 9.

Overall performance for both Explicit and Non-Explicit relations. GS + no EP setting is not included, as this is not a component-wise evaluation