1 Introduction
This research focuses on finding a way to provide useful automatically generated summaries of discussions held on Internet fora. From a user's perspective it would be helpful to be pointed to relevant messages in such discussions. This would not only save reading time, but also make it easier to learn from the discussion content, lower the threshold for participation and improve the overall quality of contributions (Farell Reference Farell2002). Existing forum search facilities can assist in finding discussions with interesting topics. Frequently, the title of a discussion clearly represents the main question or statement. Nevertheless, to find the actual answer(s), or the most relevant reactions, the entire discussion needs to be read. Instead of this tedious process, we postulate that it would be highly useful to obtain a summary of a discussion automatically.
The term thread refers to the structuring of messages in a discussion. This structure also appears in other types of researched Internet communication such as e-mail (Lam et al. Reference Lam, Rohall, Schmandt and Stern2002; Rambow et al. Reference Rambow, Shrestha, Chen and Lauridsen2004; Wan and McKeown Reference Wan and McKeown2004) and newsgroups (Lang Reference Lang1995). However, few researchers have focused on discussion fora in this context (Farell, Fait-weather and Snyder Reference Farell, Fait-weather and Snyder2001; Klaas Reference Klaas2005; Weimer, Gurevych and Mühlhäuser Reference Weimer, Gurevych and Mühlhäuser2007). This is important since different types of Internet communication yield threads with different characteristics, for example: e-mail threads tend to have few participants and, according to Dalli et al. (Reference Dalli, Yunqing and Wilks2004), these threads are also relatively short. Studies exist that exploit discussion fora for different purposes than summarisation. For example, semi-automation of grading, automatically finding unanswered questions and thread topic detection (Feng et al. Reference Feng, Shaw, Kim and Hovy2006; Kim et al. Reference Kim, Chem, Feng, Shaw and Hovy2006a; Reference Kim, Chem, Feng, Shaw and Hovy2006b).
The central task in this research also relates to document summarisation. However, methods that work well for the traditional single-document summarisation task appear to fare poorly for threads. Treating a thread as one monolithic document simply does not work (Klaas Reference Klaas2005). At first glance our interests seem to match with multi-document summarisation. Nevertheless, the traditional multi-document summarisation task is defined as summarising multiple monologue documents covering the same subject. This significantly differs from the task at hand that targets threads which are essentially dialogues formed by message ‘exchange’.
People use fora for many other purposes than pure discussion (Baldwin, Martinez and Penman Reference Baldwin, Martinez and Penman2007). We focus exclusively on threads of the following types in this paper:
• Problem–solution: A main question is posed, replies are posted and (optionally) follow-up questions are asked.
• Statement–discussion: An (opinion) statement is voiced, replies are posted and stances are clarified and revised.
For problem–solution threads the ideal output would be a clear problem definition and one or more possible solutions. This is similar to the concept of conversation focus as presented by Feng et al. (Reference Feng, Shaw, Kim and Hovy2006). For statement–discussion threads, the main statement and the major stances of authors in the discussion should be output.
Statement–discussion threads are generally wide. As follow-up to the initial post, many authors respond to give their insights. Problem–solution threads are usually narrow and involve more contributions of the initial author to refine the problem and work towards the solution. Nevertheless, both type of threads have a main focus which the summarisation process should capture.
Farell et al. (Reference Farell, Fait-weather and Snyder2001) specifically focus on creating a summary of each message in a thread individually as opposed to generating one large, combined, summary. In this research we concentrate on the latter instead. For generating one summary we adopt the term monolithic (as opposed to manifold). The summaries that we generate use only text that already exists. Therefore, they are extractive. They are also not generated based on a user query, but rather based on the available data. As such, their content is determined by the data combined with algorithms and heuristics, making them data-focused. Generating indicative summaries is not so useful given that we already know that a user is interested in a specific thread. However, making full-coverage informative summaries is difficult (Hovy Reference Hovy2004). Therefore, we restrict ourselves to finding the main focus of a discussion. The summaries produced as a result of this we term semi-informative. Finally, threads consist of hierarchically arranged messages that express a dialogue. With all these terms defined we can now state the prime focus of this research: the creation of monolithic extractive data-focused semi-informative summaries of hierarchical dialogues.
Threads are not static. They develop over time as new messages are posted. We are interested in threads that have already developed over some time and that consist of at least several posts. Threads may also contain images, but with the exception of emoticons we do not consider such multimedia content in this research. Furthermore, we detect references to external sources contained in messages, but do not give them preferential treatment. Finally, the developed prototype supports both Dutch and American English, but evaluations were done using only Dutch fora. However, keep in mind that many important techniques discussed in this paper are for the main part language independent.
We define the following research questions:
(1) What are the structural characteristics of threads and how can these be exploited for automatically building summaries of threads?
(2) What is the performance and usefulness of a thread summarisation system?
We answered these questions by developing a method and implementing it in a prototype system that we evaluated. We regard this system as a black box and define its primary inputs and outputs as follows:
• Input: a thread and the size of the desired summary.
• Output: a summary of the input thread with the desired size.
The insights presented in this paper are based on real data. We manually examined forty threads on a technical discussion forum.Footnote 1 Half of these were of statement–discussion type, the other half of problem–solution type. We also used threads from several other fora for refinements, fine-tuning and checksFootnote 2 and to prevent making the derived heuristics too specific to technical fora.
The difference of the summarisation approach in this paper, over general summarisation, is in the exploitation of characteristics specific to threads. Our most important contributions are as follows: (1) an approach to find and weight the referential structure of a thread; (2) a summarisation algorithm specifically for threads.
The rest of this paper is arranged as follows: related work is discussed in Section 2; Section 3 describes how threads are structured, how this structure can be found and weighted and how surface message characteristics can be exploited; Section 4 treats several technologies used in the final summarisation process; this is followed by Section 5 which describes the actual summarisation process; the prototype and its evaluation are presented in Section 6; the paper concludes with Section 7. The appendices (A and B) show how the algorithm is applied to two example threads that were also used during evaluation, including example summaries.
2 Related Work
Farell et al. (Reference Farell, Fait-weather and Snyder2001) were the first to write about summarisation in the specific context of discussion groups. They found that human summarisers use the structural discourse relationships between postings to guide their choice of sentences when creating a summary. Based on this finding, they developed a hierarchical discussion summarisation algorithm that uses term salience. Sadly, they did no concrete user evaluation, that specifically measures summarisation performance, in their initial and follow-up paper. They seem to focus mostly on issues surrounding the user interface and interaction (Farell et al. Reference Farell, Fait-weather and Snyder2001; Farell Reference Farell2002).
The work of Klaas Klaas (Reference Klaas2005) is close to our research. He argues that traditional summarisation does not apply to threads. Instead, according to him, we have to look for other approaches that exploit characteristics unique to threads. Similar to Farell et al. (Reference Farell, Fait-weather and Snyder2001) he identifies salient terms in messages. His use of the thread referential structure, by recursively scoring messages, is interesting. In this paper, we build upon this idea. Klaas also performed a small user evaluation. One of his results is that even for summaries with a high compression ratio, smaller than 5 per cent, users can still identify the thread's topic. User perception of his system was mixed. Some users felt his system produced consistent results, others were unsure or thought that the output was ‘garbage-filled’.
There have also been studies that specifically analyse on-line discussions, but not in the context of summarisation. Kim et al. (Reference Kim, Chem, Feng, Shaw and Hovy2006b) focus on finding a way to semi-automate grading based on the quality of discussion participation. Their corpus consists of discussion threads from university undergraduate computer science students. In a related paper they use speech acts to find threads with unanswered questions and confusions (Kim et al. Reference Kim, Chem, Feng, Shaw and Hovy2006a). Instructors can use this information to help determine where to focus their attention. Some interesting findings are as follows: about 95 per cent of all threads start with a question post and an answer directly follows that question in 84 per cent of all cases. They also found that acknowledgements are usually found at the end of a thread (73 per cent). Nevertheless, they use a domain specific corpus which consists predominantly of threads that have only two messages: question-answer pairs. Such threads are less interesting to summarise, since the need for a summary becomes more pressing as the thread length increases.
3 Discovering, weighting and filtering the data structure
Before we can proceed, we first need to understand our data. A thread consists of two parts. First, an outer structure: the relation between messages. Second, an inner structure: the content of the messages. In this section we explore how we can determine the outer structure and exploit surface characteristics of the inner structure.
3.1 Discovering the outer structure of threads
Many fora display flat lists of messages. The only explicitly encoded information in such lists is usually the date and time of each posted message. This throws away a lot of structural information. Authors in a thread usually reply to (one or more) specific messages. We broadly distinguish between two types of references:
(1) Explicit mentioning of author names, for example: ‘but as Mohinder said . . .’
(2) Quote blocks: literal citations of earlier messages that usually include explicit references to the source message (Carenini, Ng and Zhou Reference Carenini, Ng and Zhou2007).
Using these references we can find the relations between messages. Based on the example thread in Figure 1 the conceptual task is illustrated in Figure 2. We want to go from Figure 2(a) to discovery of the relations as depicted in Figure 2(b). Thus transforming a linear temporal message chain, based on message metadata, into a directed acyclic graph by using semantic information contained within the messages. Implicit temporal ordering still exists in Figure 2(b), namely that c 1 was posted after b 1 depicted by placing c 1 to the right of b 1. Time is thus visually represented by top–bottom and left–right ordering which maps onto an earlier–later scale.
A fictive example thread corresponding structurally to Figure 2. The authors are Alpert (a), Ben (b) and Carlos (c). The left column shows message identifiers; the column on the right the actual message text. Italicised phrases indicate usage in structure discovery.
Conceptual thread structure discovery. Nodes represent messages. In the node name each character represents a unique author and each number a unique post by that author. Edges in (a) represent temporal links (c 1 was posted after b 1) whereas edges in (b) indicate references (a 2 refers to b 1 and c 1).
To detect reply structure, based on explicit mentioning of author names, we first collect the names of all the authors in the thread. The next step is finding all candidate matching words in a post. We do this by first looking for exact matches. This leaves misspellings of author names for which we employ the Ratcliff/Obershelp (RO) algorithm to perform loose matching (Ratcliff and Metzener Reference Ratcliff and Metzener1988). This algorithm is rather expensive: cubic in worst case, normally quadratic and linear in best case. Since false positives can occur, we need to restrict ourselves to candidate words in each post that likely match. For this we consider words Part-of-Speech tagged as proper nouns, words following an @-sign (copes with ‘@nickname’ references) and words before the word ‘wrote’. If an author name is mentioned in a post, we assume that post refers to the last post made by that author (Schuth, Marx and de Rijke Reference Schuth, Marx and de Rijke2007). This can cause false positives if an author name is used in a different context which really refers to a different person. However, we have never seen this happen in any of our reference threads. Author names on fora tend to be very distinguishable.
Quote blocks are recognisable by either ‘>’ marks or HTML blockquote tags. Quotations are usually made up of fragments of the source message. Quote blocks can appear in several forms: with an explicit link to the source message (most common), and/or with explicit mentioning of the author name and without any references. The approach described in the previous paragraph covers author names. The presence of explicit links provides a more detailed reference and thus always overrides mentioning of author names. To find the source of quote blocks without an explicit link, we compare each line in a quote block to the lines in preceding messages. Lines in messages are traversed bottom to top; messages chronologically from most recent to first post. We also conduct this comparison using the RO algorithm. Once a line in the quote matches a line in a preceding message, we create a reference to that message. The quote count of the source line is also increased, this count is used later during actual summarisation. This process of creating references continues until either all lines in the quote match or no more messages remain to match against. When looking at previous posts, we skip quote blocks in those posts.
We can apply the described structure discovery methods to Figure 1. The link between message b 1 and a 1 is explicit. Even if the message identifier a 1 was not explicitly mentioned in b 1, we could have found the link by parsing the author name: ‘Alpert wrote:’. The link between message c 1 and a 1 is implicit. We compare the text in c 1's quote block, ‘Is it good?’, to previous messages. We skip the quoted text in message b 1 and find matching text in a 1. Hence, a link between a 1 and c 1 is created. Finally, message a 2 mentions two author names: Ben and Carlos. These are Part-of-Speech tagged as proper nouns. Based on this we create links to the most recent messages of Ben and Carlos which are b 1 and c 1. These messages are found by comparing the author names in message a 2 to the author name metadata of each message. This completes the transformation from (a) to (b) in Figure 2.
There is still another situation to consider. We regularly observed no quoting at all in replies to original texts. So, what assumptions should we make for messages without such references? We studied several threads and made the following observations:
• If a message of the initiating author of the thread refers to no other message, then he always responds to the most recently posted message. When these are messages of himself they usually elaborate or report on advancements made towards solving a problem.
• Messages of other authors almost always follow-up to the last message of the initiating author in the thread. Alternatively, they respond to the message they themselves were last quoted in or referred to by name. Some exceptions to this heuristic exist, like people responding to an older message of the initiating author, usually to give extra suggestions. However, we can not automatically detect these exceptions without actually interpreting the text. The heuristic appears to cover most of the cases quite well.
To discover the structure of threads we use a combination of clues (explicit mentioning of author names and quote block recognition) and rules based on the above two observations. At the end of the discovery process, all messages in a thread, except the first post, have at least one reference to an other message.
3.2 Weighting messages within threads
We now know which messages refer to which other messages. This knowledge can be exploited to find the relative importance of the individual messages in the discussion. Kim et al. (Reference Kim, Chem, Feng, Shaw and Hovy2006b) found that the number of responses to a message indicates its importance. Some additional phenomena are as follows: the beginning of the thread is important since it contains a description of the actual problem or statement; the end of the thread too because it is populated by working solutions and summaries of preceding posts; and messages posted by the initiating author are informative (even if they are leaf nodes). We derived the Positional Message Relevance (PMR) formula for this, based on insights by Klaas (Reference Klaas2005) and our own observations:
where P m is the set of parent messages that message m points to; C m the set of child messages that point to m; A m is 0 normally and −1 if the message is a leaf whose author is not the thread initiator;H(m) the height in the tree (relative to the first post at height one) at which m is; and HT the height of the entire thread. The height of a message H(m) is always that of the longest path between the first post and message m. The purpose of the height term is to slightly discount messages earlier in the thread and to give some extra weight to those at the end of the thread. This can cause PMR values to drop below 0 in which case we fix them to zero. The extra multiplier 2 was determined by experiment to be useful for helping representation of messages near the end of the thread. We think it would be good to automatically tune this parameter, possibly by using the average width of the thread or a branching factor.
Besides the relative height, the fourth term in the formula, the sum of the other parts of the formula equate to 0 for normal leaf nodes. The exceptions to this are as follows: the leaf message was posted by the thread initiator (in which case 1 is added) or a leaf node has multiple parent nodes (each extra parent adds 1 to the weight of the node). This captures the fact that strongly referring leaf nodes are interesting for summarisation, since they are usually already partial summaries by themselves.
Besides the factors represented in the PMR there are other phenomena to consider. Especially in longer discussions, those of statement–discussion type, some authors post more messages than others. They have a higher degree of participation. Linked to this, some authors contribute more substantial amounts of text. They have a higher talkativity. Authors with a high participation degree and talkativity usually have a much larger steering influence on the discussion. Hence, it is important that their contributions are well represented. This idea, applied to spoken discussions, is also treated in the work of Rienks (Reference Rienks2007).
To cope with this, we calculate the participation degree of each unique author in the thread. This is expressed as the proportion of messages of a specific author relative to the total number of messages a thread consists of:
where M is the set of all messages; m is a specific message; and the isauthor function determines if author a is the author of message m.
Similarly, we also calculate the talkativity for each unique author in the thread. We define this as the number of words an author contributed to the total number of words a thread consists of (excluding quotations):
where length(m) is the length in words of message m.
During assignment of summarisation weights to messages we would like to give extra weight to authors that exhibit both a high talkativity and a high participation degree. The ‘maximised’ case, both having value 1, would only be true for a thread with one author, which we do not consider in this research. However, we should assign more weight to authors that lean towards this case. Therefore, we express the weight preference in a simple weighted combined function (with β = 
:
We term this the Participation–Talkativity (PT) factor. Just like the PMR, we use it later for message weighting.
Feng et al. (Reference Feng, Shaw, Kim and Hovy2006) also model the relevance of contributions of specific authors in a discussion in their research on conversation focus. However, they use speech acts combined with a graph based algorithm called HITS (Kleinberg Reference Kleinberg1999). Specifically, they rate an author's value based on the positivity of the reactions on his posts. This approach works well on a manually annotated corpus. However, reliably finding the polarity direction and type of post automatically is a difficult task with much domain specificity. Our approach is more simplistic, but scales better because it is completely automatic. The PMR is intended to take care of determining the less relevant information at the message level rather than at the author level.
3.3 Filtering based on message surface characteristics
Readability is an important aspect of texts that can be used for filtering messages. A wide variety of metrics exist for this. These are frequently based on the word count per sentence and number of syllables per word. Determining the latter automatically is difficult for a machine. Several alternative formulas exist that use the number of characters in words as opposed to the number of syllables (DuBay Reference DuBay2004).
We calculate the average length of words based on such character counts and the average length of sentences based on word counts within a post. Conceptually, our approach is close to that of Coleman and Liau (Reference Coleman and Liau1975), with the exception that no single combined score is created. It remains somewhat dubious to compare these Average Word Length (AWL) and Average Sentence Length (ASL) statistics among posts because the messages differ in length. Nevertheless, we assume that the AWL and ASL can be used to measure the (un)importance of a single message with respect to the other messages in a thread. This targets posts that are unusually terse or very lengthy with respect to word usage and sentence length. These posts suffer from low readability and users are less likely to read them compared with the other messages.
The quality of a post is hard to define. In fact, properly rating post quality would require exhaustive semantic knowledge. Intuitively, certain formatting characteristics of a message can be indicative of poor quality. The suggestion of using such surface features was initially inspired by comments made by Steven de Jong, a moderator of the NRC weblog (http://weblogs2.nrc.nl/discussie/). He independently observed the same phenomena as Weimer et al. (Reference Weimer, Gurevych and Mühlhäuser2007). They investigated the effectivity of several types of surface features for a good versus bad classification task of forum posts. Weimer et al. based their research on a corpus of human rated posts. We use four surface features similar to theirs, shown in Table 1. We calculate a grand global score, termed the Message Formatting Score (MFS), based on these four characteristics. An MFS of 1.0 indicates a well-formatted message whereas an MFS of 0.0 indicates a very poorly formatted one.
Formatting characteristic formulas. m is a message (a list of sentences); s is a sentence within a message (a list of words); and w is a word within a sentence
4 Technologies
4.1 Preprocessing
We build upon several foundational Natural Language Processing (NLP) technologies and implementations thereof. We, in particular, use parts of the Natural Language Toolkit (NLTK) (Bird, Klein and Loper Reference Bird, Klein and Loper2008). Other NLP system components are briefly mentioned in this section. The performance of each is summarised in Table 2.
Performance of preprocessing tools
We use the tokeniser from Kiss and Strunk (Reference Kiss and Strunk2006) included in the NLTK. It has intelligent handling for some tricky issues in tokenisation. Kiss and Strunk show that the accuracy of this tokeniser on a Dutch newspaper corpus, named The Limburger, exceeds 99 per cent. For Part-of-Speech tagging we use a Hidden Markov Model trigram tagger from the Hammer Tagger Toolkit with some extensions specific to web fora content (Stegeman Reference Stegeman2007). We created taggers based on the Spoken Dutch Corpus (SDC) for Dutch and on the Brown corpus for US English (Francis and Kûcera Reference Francis and Kûcera1979; van Eynde Reference van Eynde2004). We projected the tags of these corpora onto a self-developed unified tagset consisting of twenty-six tags. Our tests revealed the accuracy of the SDC tagger to be 97.5 per cent, on par with state-of-the-art tagging performance (Manning and Schütze Reference Manning and Schütze1999). We do partial parsing using the built-in regular expression based chunker of the NLTK. Chunking rules for Dutch and US English were written manually based on an existing grammar previously created by one of the authors for other purposes. We tested our partial parser against the Dutch Alpino Treebank corpus (Bouma, van Noord and Malouf Reference Bouma, van Noord and Malouf2000). The performance is around 87 per cent precision and 95 per cent recall.
We perform Named Entity Recognition (NER) to find the names of people, organisations and locations using gazetteer lists augmented with some manual heuristics inspired by Bogers (Reference Bogers2004). We evaluated this against the CoNLL2002 newspaper data (Sang Reference Sang2005). NER precision is about 87 per cent and recall 42 per cent. Finally, we also do additional semantic tagging to recognise URL's, e-mail addresses, dates, times, quantities and emoticons. Lam et al. (Reference Lam, Rohall, Schmandt and Stern2002), who use regular expressions to find semantic units, served as inspiration for our approach.
4.2 Anaphora resolution
An anaphor is a specific type of reference pointing back to an antecedent in a text. When making extractive summaries, sentences are ‘cherry picked’ out of a larger body of text. However, sentences frequently depend on the preceding sentences by referring to them. This makes the summary unreadable if those previous sentences are not included in it. This phenomenon is known as dangling anaphora.
The concept of anaphora is frequently confused with coreference which is a related, but different, concept. An anaphor depends on its antecedent for correct interpretation. A coreference essentially stands alone and thus needs no additional context to be understood (van Deemter and Kibble Reference van Deemter and Kibble2000).
We are interested in indicative anaphoric resolution. This means instead of replacing an anaphoric reference, we augment it with a likely antecedent. We always place this ‘suspected’ antecedent behind the anaphoric expression, in parentheses, since this still leaves the possibility for a user to detect wrong anaphoric resolutions. An example:
I bought a videocard today. The card [videocard] is noiseless.
Anaphora resolution consists of two parts: the identification of an anaphoric expression and finding a noun phrase it refers to. We focus on finding three types of anaphora: pronouns (like: it, he, she), generalisations (videocard→card, big house→house) and acronyms (Free Software Foundation→FSF). Naturally, we do not resolve references within the same sentence.
We walk through the entire text, accumulating all noun phrases in sentences. These are used as candidates for anaphoric resolution. To detect anaphoric expressions we employ the following strategies:
• Using a lists of common pronouns in the third person: he, she, they, et cetera. For example: ‘Niels got cabin fever. He ran around frantically’.
• Partial matching between (suffixes of) heads of noun phrases (Hoste and van den Bosch Reference Hoste and van den Bosch2007). For example: ‘The stinging behaviour of worker bees is very effective. But, the bees who do . . .’
• Detection of acronyms build from the previously seen noun phrases (Hoste and Daelemans Reference Hoste and Daelemans2005). For example: ‘Sponsored by the British Broadcasting Corporation. The BBC has . . .‘
We then score anaphoric expressions against the candidates using heuristics: distance restrictions (Mitkov Reference Mitkov1999); weighting based on definiteness and the presence of prepositions (op den Akker et al. Reference op den Akker, Hospers, Kroezen, Nijholt and Lie2002); number agreement (Jurafsky and Martin Reference Jurafsky and Martin2000); the position of the noun phrase in the sentence and the presence of surrounding parentheses. We do not consider word gender.
Novel is the usage of thread specific characteristics in the anaphoric resolution. We allow references to cross post boundaries. The first several lines of a post may refer anaphorically to the last lines of a post that chronologically precedes it. Additionally, the first lines may also refer to one or more other previous ‘parent’ posts as determined by the discovery of the outer thread structure. For resolving pronouns in the first (I, me, mine) and second (you, your) person, sometimes called deictic references, we also exploit the thread structure. Self references (first person) resolve to the name of the poster of the message. Second person references resolve to the author of the post the current post is a reply to, provided only one such message exists.
4.3 Sentence type detection
Detecting the type of sentences in a post is useful for a variety of purposes. Firstly, for filtering out less relevant sentences, and secondly, for finding links between sentences across messages (Farell Reference Farell2002). For filtering we restrict our detection to a few basic sentence types:
• Openers: ‘dear . . .’
• Closers: ‘thanks!’
• References: ‘http://. . .’
• Lists: ‘1. x, 2. y, . . .’
These types of sentences are assigned a lower priority during summarisation. Besides these, a major important group of sentences are questions. We detect these based on the presence of question marks and sentences constructed in the interrogative form, looking for words such as who, where, when, et cetera (McKeown, Shrestha and Rambow Reference McKeown, Shrestha and Rambow2007). Although this does not capture all question sentences, and may even capture some that are not, we believe it is a good starting point.
4.4 Question–answer linking
We use a small question typology for classifying question sentences based on Webclopedia (Hovy, Hermjakob and Ravichandran Reference Hovy, Hermjakob and Ravichandran2002). It specifies for several types of questions what kind of answer one would expect. For a ‘who’ question we would anticipate the answer to be a person or an organisation, for ‘when’ we would expect some specific time or date. This information allows us to create a link between a question sentence and a possible answer.
The identification of question and corresponding answer blocks is a more objective task than that of summarisation (McKeown et al. Reference McKeown, Shrestha and Rambow2007). Kim et al. (Reference Kim, Chem, Feng, Shaw and Hovy2006a) showed that, on specific corpora, a significant portion of forum posts consists of questions (36 per cent) and answers (43 per cent). The usefulness of linking questions and answers was established by Zechner (Reference Zechner2002). He concludes that while such linking does not significantly affect the informativeness of dialogue summaries, it does significantly increase the coherence.
The procedure for finding question-answer pairs is as follows:
(1) For a specific message m find out what messages it refers back to using the thread structure.
(2) In the referred messages identify all question sentences that have an expected answer type. For example the sentence ‘Where did the Kahana go?’, would have answer type ‘location’.
(3) Find all sentences in message m that contain a noun(phrase) with a semantic tag (person, date, et cetera) that matches the answer type in the previous step. For example ‘The ship went to an Island’, where the italicised expression has the semantic tag ‘location’.
(4) Increase the question-answer score of both the set of sentences found in the previous step, as well as the original sentence that contained the question.
We prefer sentences with a high question-answer score for inclusion in the summary. One might argue that for summarisation purposes it would be best to always include both the question and answer part of a pair. However, doing this is tricky since there can be multiple pairings. It would also conflict with weighting at the message level. We did not investigate this further.
5 Summarisation process
The summarisation algorithm consists of several steps. These are as follows: filtering, distributing message weight, distributing sentence weight and finally selecting sentences.
Message filtering is done based on the average sentence and word length. If either of these differs sufficiently from the average in the thread none of their content is included in the summary. This is based on z-scoring with z between −3 and +3. Additionally, we filter out messages with a poor, below 0.40, Message Formatting Score (see Table 1, Section 3.3). The first message of a thread is never filtered out.
The remaining messages in the thread are each assigned a weight which determines how much of their content will be included in the summary. The weight of a message is determined based on the PMR (equation 1, Section 3.2) and PT factor (equation 4).
Figure 3 shows an example thread and Table 3 shows the results for the steps that we describe for this thread. We work from PMR/PT values on the left to the final sentence weights on the right of the table. The PMR values for each message derive from the thread structure. The PT values for each author are fictive. In the example the PT and normalised PT are the same, since all messages are selected.
An example thread. Messages are represented by nodes, arrows indicate references. In the node name each character represents a unique author and each number a unique post by that author. The PMR of each node is shown between parentheses behind the node name.
Example thread sentence assignments. Shows how we calculate the number of assigned sentences for each message of the thread in Figure 3. Messages are listed in the first column, each subsequent column shows the results of a formula described in this section. Note that ptnorm is a value assigned to each unique author and is repeated for each author in the table. The last two columns show the number of assigned sentences assuming a thirteen sentence summary. The select column shows select n sentences out of message length m as n/m. Since the left values in this column do not add up to thirteen, an extra pass is made that removes sentence weight from messages. The rightmost column, labelled r, shows the final sentence count assignments
We first normalise the PMR over all selected messages of the thread:
where N is the set of all selected messages (N ⊆ M where M is the set of all messages in the thread) and m is the message to calculate the pmr norm for.
Next, we normalise the PT of each author over all selected messages as follows:
where a is the author we want to calculate it for; the author function gives the author of a message and b iterates over all authors of the selected messages.
We use both of the preceding formulas to calculate the PT at the message level, rather than at the author level. This PT factor is distributed inversely with respect to the PMR of the messages posted by the author. Meaning that the PT weight for a specific author shifts towards messages that have a low (or zero) PMR from that author. We express this formally as:
where a is the author of message m. This formula is applied only if more than one message of an author has been selected for inclusion in the summary.
Finally, we calculate the weight for each message based on both the normalised PMR and PT as follows:
where m is the message to calculate the weight for. We set the value for β to 
determined to yield good results by experiment. Thus, the PMR has more influence on the final message weight than the PT factor.
The total number of sentences that the summary should consist of is an input to the summariser. The calculated message weights can now be used to calculate for each message what ‘slice’ it contributes to the summary ‘pie’. We do this as follows:
where m is a message and sentences is the number of requested summary sentences.
While the message weights always sum to one, the number of sentences must be a whole number. For this reason we apply the ceiling function. Since this can cause the sum of sentence weights to exceed one, a second pass is made over the final sentence weight values. In this pass we remove sentence weight from messages that already have a low weight. The r column in Table 3 shows the result. We penalise messages, with the same weight, posted earlier more than those posted later. The effect is a bias both towards messages with a high weight, increasing coherency, and towards messages at the end of the thread, increasing coverage.
One remaining problem is that short messages may get too many sentences assigned. For example: a message consisting of only two sentences gets five assigned. To handle this, a final pass is made that removes excess sentence weight. The excess sentences are then assigned to the messages from highest to lowest weight until there are no more sentences to redistribute. If at this point there is still sentence weight left, the resulting summary will be shorter than requested.
We know now how many sentences we can select from each message for our summary. However, we still need to decide which sentences we will select. We use the following priority heuristics for this: firstly, sentences in a message are selected that are marked as either being an answered question or an answer to a question. Secondly, the longest question sentence, in sense of character length, is preferred. Lines cited in one or more separate messages have third priority: the more a particular line is cited, the more it is preferred over other cited lines. Sentences with the same citation count are considered in bottom-to-top order. If no other heuristics are applicable, the system falls back on the top–bottom interleave: from the sentences that remain we simply pick the first one, than the last one, than the second one, et cetera. Finally, the low priority lines are considered in long to short order. This includes the greeters, list items, et cetera.
Both Klaas (Reference Klaas2005) and Farell et al. (Reference Farell, Fait-weather and Snyder2001) demand that some part of each message should be included in a summary. We take a different approach and allow the system to exclude all content of a message. Sentences are always included in the summary in their original message order to increase coherence. Resolved anaphoric references are included to further aid in understanding the context.
6 Evaluation
To evaluate the summarisation method presented we implemented our ideas described as a prototype system. The inputs to this prototype system are as follows: the thread URL; the language (Dutch or English); the compression ratio as a percentage or the absolute number of sentences to retain; and finally: the forum type which refers to the forum software used at the mentioned thread URL. We transform forum content, from the HTML page(s) a thread consists of, to an internal data structure.
It is quite difficult to evaluate summaries. We chose a user evaluation as we believe the actual target user group should judge the created summaries. We conducted the evaluation via an on-line webform. Confronting users with just a thread and the summariser output for that thread did not seem like a good approach. We reasoned that this does not encourage people to thoroughly read the thread. We concluded that it would be better to first actively engage users with its content. Therefore, each participant in the evaluation first had to make some assignments with regard to the thread content. This was really only to ‘prime’ the users sufficiently as to enable them to better judge the machine generated summaries.
The exact evaluation procedure was as follows: after an introductory screen each user was confronted with the same two threads in turn. First, a problem–solution thread consisting of twelve messages and hundred unique sentences (see Appendix A). Second, a statement–discussion thread consisting of eight messages and thirty unique sentences (see Appendix B). These two test threads were not used during development of the system and were from two different fora. We showed them unaltered, with their original mark-up from the source page, to recreate a familiar environment as close to real usage as possible. We requested participants to make two small assignments for each thread:
(1) Select the five most important messages in the thread and rank them in order of importance.
(2) Create your own extractive summary by pasting a selection of sentences in a textbox: twelve for the first thread and ten for the second. Percentagewise this roughly conforms to the lower (15 per cent) and upper bounds (35 per cent) for a useful summary according to Hovy (Reference Hovy2004).
After these priming assignments we confronted the users with a machine generated summary of each thread. They were requested to judge various aspects of these summaries such as the coverage and coherence. Next, we asked users several opinion questions regarding the usefulness of automatic summarisation and various features. Finally, users were asked some demographic questions that closed the evaluation.
Eighteen people participated in the evaluation. This makes it hard to draw statistically significant conclusions, but is enough to give a general impression. Participants were predominantly male (72 per cent) and nearly all in the 21–30 age range. Half of the respondents read threads in webfora at least once a week, but only 17 per cent posted with this frequency. Respondents mostly visited between one and four different fora at least once a month. Most respondents claim to have above average Internet searching skills (~90 per cent). However, they are less confident about their own Internet fora searching skills (~50 per cent above average). This supports the idea that there is a difference between these tasks.
The primary objective of the evaluation was to find out how humans judge the machine generated summaries. Comparing human and machine summarisation performance was not a goal. Nevertheless, we did record the message orderings and extractive summaries created by the participants. This data can give some insight into the relation between real human summarisation and the judgements.
The machine summarisation algorithm produces a weight for each message in each thread. Based on this score, messages can be ranked by importance. The participants directly ranked the messages in each thread. We wanted to find out the degree of resemblance between the machine ranking and the rankings produced by the participants. We used Kendall's tau-b correlation score to compare the human and machine rankings. This score is defined as follows (Agresti Reference Agresti2002):
where C is the set of concordant pairs between two rankings R 1 and R 2; D is the set of discordant pairs; T 1 is the number of ties only in ranking R 1 and T 2 is the number of ties only in ranking R 2. The score is in the range [−1, +1]. A negative score indicates the two rankings are inversely related. The maximum positive score denotes the two rankings are identical. Whereas a score of 0 means no correlation exists.
We first compared the rankings for each discussion among humans by leaving one ranking out. This ranking was used to calculate the average Kendall's tau-b score against the remaining human rankings. The same approach was used to compare humans and the machine. This time comparing against the machine ranking instead of the human one left out. We only asked participants to rank the five most important messages. Therefore, the remaining messages, seven for the first discussion and three for the second, are all tied at rank six. Results are shown on the first row of Table 4 for each discussion.
Human–human agreement and human-machine agreement for various aspects. Ranking is measured with the Kendall's tau-b Kτb correlation (range [−1, +1). Content overlap is measured with various ROUGE variants (range [0, 1]). For ranking all 18 human summaries were used, whereas for overlap only 16 were used for each discussion (two outliers were removed)
For both discussions the machine ranking positively correlates with the human rankings on average. Especially for the second discussion the correlation is quite strong. The humans agree more with the machine ranking for this discussion than with each other. However, this discussion was also shorter than the first. We also observed that many people agree on what the most important message is in the thread. However, the agreement becomes lower as the rank decreases.
The machine produced an extractive summary for each of the two threads. We asked participants to do exactly the same. We wondered how similar the machine produced summary of each thread is to the human summaries. All summaries have the same length restriction. Therefore, we are comparing the recall of the machine with that of the human participants. Hence, we used the Recall-Oriented Understudy for Gisting Evaluation (ROUGE) overlap metric to compare the extractive summaries, which we interpreted as follows (Lin Reference Lin2004):
where c is the candidate summary; R the set of reference summaries and n the n-value for n-gramming. The gram(a, n) function yields the n-grams for text a.
To compare the extractive summaries we did two leave-one-out tests for each discussion. First, in the human–human test, one human summary was left out and used as candidate summary, the remaining summaries formed the reference set. This process was repeated for each human summary and the resulting ROUGE scores were averaged. The outcome gives an impression of the extent to which humans agree with each other on the summary content. The second test was the human-machine test which also leaves each human summary out once. However, here the machine summary was used as candidate instead of the left-out human summary.
Table 4 shows the results for each discussion in the second to fourth rows. Note that we only used sixteen of the eighteen human summaries, since two summaries did not meet the length and content criteria we set. Scores shown are for ROUGE-1 (unigram), ROUGE-2 (bigram) and ROUGE-3 (trigram) overlap (values of n of 1, 2 and 3 in (equation 11)). If the scores seem high, remember that participants were asked to create an extractive summary and not to rephrase content, in essence ‘pasting’ sentences of the original discussion.
The first discussion seems more troublesome for humans than the second. A similar pattern can be observed for the machine. However, the machine performs much worse on the first discussion. Still, in the second discussion it achieves about 84 per cent of the human score on average, which is good. However, keep in mind that the second discussion thread was smaller and that its summary was allowed to be larger relative to its total size.
We made several observations regarding the human summaries: participants ordered the sentences in a non-chronological way with respect to the order in the original thread. The automatic summariser does not do this. Similar to the message ordering, we saw agreement among participants. This time on the few most important sentences in the thread based on the sentence selection frequency. However, frequently selected messages in the ordering task did not get a proportionally higher amount of selected sentences in this second task. This supports the idea that the PMR alone is not enough to distribute sentence weight. Hence, the addition of the PT factor is justified.
So, what are the judgements of the participants themselves: what did they think of the machine generated summary for each of the two threads? This is shown in Figure 4. We asked users to grade the machine summaries, as if judging summaries created by students, on a ten-point scale. A one is very bad, a six is sufficient and a ten is considered excellent. The summary of the first thread was rated with a 5.89 average score (median 6), the second was rated with a 6.83 (median 7). Note that for most users it took about 15 minutes to manually make an extractive summary of a thread. The developed prototype does this in several seconds.
Automatic summary grades (n = 18⋅2). Grades were given for the first discussion D1 and second discussion D2 on a scale from one (low) to ten (high). A six is considered sufficient.
We asked users to rate the coverage and coherence of the summaries on a five-point scale. Figure 5 shows that users rated coherence higher than the coverage.
Automatic summary user judgements (n = 18⋅4). Coverage and coherence were judged for discussions D1 and D2 on a scale from one (bad) to five (good).
Most respondents, 95 per cent, indicated an automatic thread summariser as either a useful or very useful tool. Half of the respondents would use the summariser every now and then, the other half would use it regularly or always when visiting fora. This is promising and shows there is genuine interest in the developed technology as well as a potential user base.
7 Conclusion
This paper shows a promising way to build automatic summaries of threads. We used a combination of heuristics and traditional Natural Language Processing technologies. Core parts of the presented methodology rely on existing metadata in threads. We have developed heuristics for recognising the referential structure between messages in threads, for filtering messages and for recognising the importance of contributions of authors. Finding sentence types and linking questions and answers aided sentence selection. Finally, we combined everything into one summarisation algorithm, implemented in a prototype system.
The performance of modules of the prototype system, that we could evaluate on external datasets, is on par with the state-of-the-art performance for Dutch. Results of the evaluation of the prototype system show promise. Little can be concluded about the thread types, this requires more quantitative evaluation. The grades can be subjectively interpreted as acceptable. However, we can objectively see from Kendall's Tau-b and ROUGE scores that the summariser does a fair job with message ranking and sentence selection compared with humans. Even though user judgements scores show that the coverage could be improved, the scores for coherence are high. This suggests that presenting the summary as a dialogue with anaphoric references expanded is a good approach.
Nevertheless, room for improvements exists and several aspects deserve more attention. In our opinion, the ideas behind question-answer coupling are sound, but a more generic, less domain data dependent, solution would be useful. Speech act analysis may be a good starting point for this. For sentence selection the fallback interleaving heuristic is a bit basic. The approach used for message filtering works well and correctly identifies messages with poor formatting characteristics by using the Message Formatting Score (MFS). However, the usage of Average Word Length and Sentence Length is not so fruitful in hindsight. The MFS almost always already identifies messages picked out by deviations of these length statistics.
The summarisation approach in its entirety has been tested only on a limited number of threads of specific types. To what extent this generalises to other threads is an open question. However, this research paints a clear picture of what is important in forum discussions. We conclude that creating automatic summaries of on-line discussions in Internet fora in the way presented in this paper is a promising idea. People that use fora can use it as an effective time saving technology. A good next step would be investigating this further by creating annotations on larger datasets with many participants. The outcome can be used for refining the heuristics and, possibly, for finding new patterns.
Acknowledgements
Thanks goes to Ruben Wassink for his thorough review of the thesis that forms the basis for this paper. We also thank Maarten Fokkinga, Marco Gerards, Paul Bakker, Dirk Heylen, Mariët Theune, Anton Nijholt, Maurice van Keulen and Gert Bolmer for their comments.
Appendix A: First discussion
This discussion is started by author w who is currently considering dropping out of university and looking for a job with his previously obtained diploma. He posts to a forum to get the opinions of others on the possibility of jobs with his diploma. This is a thread of Problem–Solution type. The original thread title is ‘Working in ICT with senior secondary vocational education (in ict system administration)’.
Messages
The following listing shows all source message in chronological order. The original thread was in Dutch, so the messages were translated to English. In the translation as much of the original wording and casing is preserved as possible, this includes subtle errors. In the original experiment the discussion was shown in full mark-up as used on the source forum. This listing merely shows the message text.
Properties and structure
Figure 6 shows the discovered structure of the thread. The discussion is ‘wide’, meaning that the first post yields many reactions. Most positional relevance is assigned to the first post w 1, the deeper part of the discussion between w and r and the chronologically final posts in the thread. Although r 2 cites m 1 in the original thread, this is not recognised, because the cited paragraph in r 2 is not marked up as citation. Message r 2 is linked to w 1 as fallback. Table A1 shows how the pmr values in Figure 6 were determined. See equation (1) in Section 3.2 for the pmr formula.
First discussion thread structure.
Calculation of pmr values for the first discussion. Each term in the pmr formula is shown as a column. The final column is the sum of the other columns and represents the final pmr value as shown in Figure 6. Messages with the same term values are shown in one row
Table A2 shows other properties of authors and messages in the first thread. The numbers shown are based on the Dutch version of the thread, not the English translation. However, the MFS and pmr norm are exactly the same for the English version, since these are language independent measures. The pt norm is approximately the same, since it is partially based on the number of words in a message which may differ slightly in the translation. The pmr norm values are simply normalised values of those in the rightmost column of Table A1. We have omitted the Average Word Length and Average Sentence Length because they are specific to Dutch.
Author and message properties for the first thread including sentences assignments. The pt norm values apply to authors and sum to one. The other metrics apply to individual messages. The last two columns show the number of assigned sentences assuming a twelve sentence summary. The select column shows select n sentences out of message length m as n/m. Since the left values in this column do not add up to twelve, an extra pass is made that removes sentence weight from messages. The rightmost column, labelled r, shows the final sentence count assignments. The structure of this table is the same as Table 3 in Section 5
Summary
The requested summary size was twelve sentences. The result is shown below: source message identifiers on the left, the chosen sentence(s) from each message, numbered, on the right. Anaphoric references are shown between square parentheses.
Why were these specific sentences selected? We give the heuristic which triggered the selection for each sentence:
There are some surface problems with the summary: for example in the summary part of r 1 the sentence boundary is incorrectly detected, as a consequence the word ‘years’ is missing after ‘4(?)’. Also h 1 repeats a sentence from the initial post which was not marked as citation. The summary contains the main question, some clarification and some concrete answers. The difficulty with this discussion is the number of questions and answers. The main question appears to be whether there is sufficient work at the level of w. The last line in the summary provides an answer to that question. A strongly related question, expressed in sentence 04, is detected by the question-answer scoring module and an answer to it is also included.
Appendix B: Second discussion
This is a discussion started by author s who supports the stance that people who are injured (or sick) because of their own fault should pay for their expenses themselves. This is a thread of Statement–Discussion type. The thread title is: ‘Sick due to your own doing? Then you should pay the costs yourself’.
Messages
The following table shows all source message in chronological order. The original thread was in Dutch, so the messages were translated to English. In the translation as much of the original wording and casing is preserved as possible, this includes subtle errors. In the original experiment the discussion was shown in full mark-up as used on the source forum. This list merely shows the text of each message.
Properties and structure
All citations contained complete reference to the source message. Based on this and the heuristics the thread structure was inferred as shown in Figure 7. This discussion is ‘deep’: most messages refer to one specific post and are only referred to once. Message p 1 is determined to be the most important in the discussion. All links in the citations in this thread are explicit and thus the thread structure is correctly found. Table B1 shows how the pmr values in Figure 7 were determined. See equation (1) in Section 3.2 for the pmr formula.
Second discussion thread structure.
Calculation of pmr values for the second discussion. Each term in the pmr formula is shown as a column. The final column is the sum of all columns and represents the final pmr value as shown in Figure 7
Table B2 shows other properties of authors and messages in the second thread. As for the first discussion these are based on the Dutch version, but most of them are the same for the English version except for pt norm. The pmr norm values are normalised values of those in the rightmost column of Table B1.
Author and message properties for the second discussion. The pt norm values apply to authors and sum to one. The other metrics apply to individual messages. The last two columns show the number of assigned sentences assuming a ten sentence summary. The select column shows select n sentences out of message length m as n/m. Since the left values in this column do not add up to ten, an extra pass is made that removes sentence weight from messages. The rightmost column, labelled r, shows the final sentence count assignments. The structure of this table is the same as Table 3 in Section 5
Summary
The requested summary size was ten sentences. The result of the automatic summariser is shown below: source message identifiers on the left, the chosen sentence(s) from each message on the right. Anaphoric references are shown between square parentheses.
Why were these specific sentences selected? We give the heuristic which triggered the selection for each sentence:
Many messages are cited in full one or more times in this thread. This leads to the situation where all sentences in a message, that are not a citation themselves, have the same citation count. Selection among such sentences is based on the sentence index: sentences that occur later in the message are preferred over earlier ones. This mechanism is the way that most of the sentences were selected in this thread. Although, there are some exceptions. For example, even though message p 1 contains as much as three question sentences, the first one, selected sentence 03 in the summary, is the longest question sentence that stands on itself.
The main statement really is in the thread title and there is some support for this in the sentences selected from the first message s 1. The thread is short and the summary relatively long. This increases the chance of picking good summary sentences. Nevertheless, there are still some potential pitfalls such as short sentences and sentences that add little to the discussion like the one in message h 1. The algorithm manages to prevent these sentences from being included in the summary.
