<commit_before>\chapter{Background \& Related Work\label{chap:background-related}}
  \section{Background}
    This project is built on existing technologies and research. This section gives an overview of the key foundations.

    \tocless\subsection{Automatic Summarization}
      \blockquote{A summary can be loosely defined as a text that is produced from one or more texts, that conveys important information in the original text(s), and that is no longer than half of the original text(s) and usually significantly less than that.} \cite{radev2002introduction}

      Approaches to summarization could be grouped loosely into two groups, extractive and abstractive. Extractive summaries are constructed using content found in the source text. Abstractive summaries are created by performing some form of analysis on the source text before generating new content for the summary. One might also group summarization tasks based on the nature of the source text - approaches tend to summarize either single or multiple documents. This project is more closely related to the summarization of multiple documents, however, it applies both elements of extraction and abstraction.

      \subsubsection{Multi-document Summarization}
        Summarizing text made up of documents from different authors poses an interesting challenge. Using multiple documents introduces repetition and contradictions - this makes summarization selection tasks such as extraction and compression more complex.

        Earlier work on multi-document summarization suggested the task was going to require an abstractive approach because extractive techniques used for single document summaries, not being able to connect information between documents, would lead to incoherent and repetitive summaries \cite{McKeown1999TMS315149315355}. An alternative approach clustered paragraphs on the same topic from multiple documents and then use natural language generation techniques to combine phrases from paragraphs into a coherent summary \cite{McKeown1999TMS315149315355}. A similar approach creates clusters by parsing sentences and using predicate-argument structures to link phrases \cite{barzilay1999information} \textbf{(comment about being similar to our points extraction and grouping?)}. Interestingly, while both methods rely on natural language generation, neither use a semantic representation.

        More recently, MEAD, a centroid-based, multi-document summarization tool has been able to produce good summaries without abstraction and generation \cite{radev2000centroid}. Compared to previous abstractive systems such as SUMMONS that relied on templates \cite{mckeown1995generating}, MEAD was more generally applicable. Both these projects, and indeed most work on the summarization of multi-document sources has focused on news articles. While there are parallels between this and the summarization of online discussion, fundamentally they are different tasks.

        More closely related to this project is Opinion Mining. Opinion Mining or sentiment analysis is an approach often applied to user reviews, `documents' discussing a product or service. Early work in the area focused on the problem as a classification task, categorizing documents based on their sentiment bearing terms \cite{turney2002thumbs}. More recently there as been a greater focus on aspect-based approaches that attempt isolate sentiment terminology to specific topics such as product features \cite{hu2004mining}.

      \subsubsection{Sentence Compression \& Content Unit Size}
        While sentences are often the default content unit used in extractive summarization, often smaller units are more desirable. Sentences found in real documents and discussions can make a number of statements each of which can be useful when creating a summary. Sentences may also include surplus information. In this case sentences can be compressed statistically, in a similar way to documents are in extractive summarization. Both noisy channel and decision based models have used on parsed sentences for the task of sentence compression \cite{knight2000statistics}. Our approach for compression where points are extracted around a verb, does not seem to have been previously documented.

        Selecting the content unit for a summarization is challenging. One might think that sentences could be relied upon as coherent content unit but poor grammar and unresolved co-referring expressions mean this is often not the case \cite{witbrock1999ultra}.

      \subsubsection{Evaluation of Summaries}
        The evaluation of automatically generated summaries is an ongoing discussion. A common approach is to make a comparison against a model summary, typically written by a human. Various metrics such as ROUGE \cite{lin2004rouge} are used to make the comparison between summaries statistically. These are however limited by the assumption that there is a single best model for a summary. Alternative methods have been proposed. The Pyramid Method is one such example, it models content units across the collection of summaries being evaluated to give each content unit a weight based on how commonly it occurs \cite{nenkova2004evaluating}. These weights are used to allocate scores to summaries without an ordering bias.

        Automated methods are used primarily at the Document Understanding Conference when many summaries must be evaluated for a given task. Ideally however summaries could be manually evaluated. This would allow extrinsic attributes such as the utility of a summary for a particular task to also be accounted for. \textbf{(reference to SUMMAC?, automated http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.489)}

        In this project we compare summaries against those generated using the approach outlined here \cite{nenkova2006compositional} as a baseline. Summaries are scored by human judges.

    \tocless\subsection{Argumentation Mining}
      Argumentation Mining is a task that involves the identification of argument components within text such as premises and conclusions. The task also often involves fitting these components into a template or known pattern to enable some form of reasoning. \cite{palau2009argumentation}

      A relatively new research area - combining ideas from natural language processing, information extraction and argumentation theory - Argumentation Mining is based largely on discourse theory. While Argumentation Mining can be applied to structured text (source?), ultimately mining of free text is the goal. This means that argumentation tools often need to model concepts from linguistic research such as rhetoric structure theory \cite{mann1988rhetorical} and local coherence centering \cite{weinstein21centering} to identify structure.

      \subsubsection{Identifying Argumentative Structures in Text}
        When identifying argumentative structures in text the first step is often to classify phrases that are part of an argument. One option is to define rules for argumentative sentences or clauses. This can also be approached as a classification task, statistical methods such naive-bayes have also been used \cite{palau2009argumentation}. The result of this stage is a collection of unrelated clauses potentially spanning many arguments present in the source text.

        The next stage in the analysis is to group identified units together into separate arguments. Sometimes the document structure (chapters and sections) can be used to inform the grouping task, this is hard to generalize. Documents are rarely consistently formatted and arguments will often span many sections. Other options include grouping based on the similarity of the unit's contents such presence of certain words. \cite{palau2009argumentation}

        Once identified units have been grouped into different arguments it becomes possible to start looking into the argument's structure. Different units need to be classified as either premises or conclusions - this can again be approached as a classification task \cite{palau2009argumentation}. Once such as structure for the units has been established it's possible to do analysis on this connected structure such as identifying supporting claims for conclusions.

        A further task is relating arguments within the document to one another, this is a far more challenging task. Fitting the argument structure to allowed patterns defined by a context-free grammar is one proposed approach \cite{palau2009argumentation}.

    \tocless\subsection{Dependencies}
      The approach implemented as part of this project relies on the products of research in the following areas.
      \subsubsection{Topic Modeling}
        Topic modeling covers a set statistical modeling techniques used to identify and group topics in text. Fundamentally, this involves looking for words that are relatively more common on one document vs a collection of documents. Documents often contain multiple topic words that need to be grouped into more conceptual topics. One approach to this is is \textit{Latent Dirichlet Allocation} (LDA), this implements a ``three-level hierarchical Bayesian model" \cite{blei2003latent} and is the approach used for topic modeling in this project.
      \subsubsection{Dependency Parsers}
        Parsing text for dependencies involves building upon a phrasal parse to extract relations between tokens in text. Dependencies are identified using rules applied to phrase structure trees. Various dependency parsers exist, this project makes use of the dependency parser included as part of the Stanford CoreNLP framework \cite{de2006generating} which is based on their probabilistic context-free grammar phrasal parser \cite{klein2003accurate}. The rules used in the Stanford dependency parser based on \textit{Universal Stanford Dependencies} \cite{de2014universal}.
      \subsubsection{Querying Dependency Parses}
        To make use of the dependency parse, a means of querying the graph is required. \textit{Semgrex} is one such approach, this defines a regular expression style syntax for expressing queries on nodes and relations in a dependency graph \cite{Chambers2007}. More generally however, the task about querying nodes and edges in a directional graph. For this project we opted to use \textit{Cypher}\footnote{http://neo4j.com/docs/stable/cypher-introduction.html}, the graph query language implemented by the \textit{Neo4j}\footnote{http://neo4j.com/} graph database. This was chosen for the querying of dependency parses as it allowed many separate graphs to be queried in parallel for the same pattern using a more familiar, declarative syntax.

  \section{Related Work}
    Having covered the technologies and areas of research that underpin this project I will now discuss similar work that comes closer to combining these, as this this project does.

    While most summarization research has been in the newswire domain, some work has been done to summarize more conversational texts. This differs from the speech summarization as source content is typed rather than spoken, removing many additional difficulties. Documented business conversations such as email threads and meeting minutes are a common use case. In email threads (collective message summarization) a common approach to summarization is to identify question and answer pairs \cite{shrestha2007using,shrestha2004detection,carenini2007summarizing}. Questions can be identified using a classifier trained on a corpus that annotates speech acts \cite{shrestha2004detection}. The quotation formatting used in emails can also provide question-answer pairs - one approach used word overlap to link text to quoted segments \cite{carenini2007summarizing}. The use of speech acts for summarization of email appears to have originally been used in the \textit{SmartMail} project \cite{corston2004task}, this technique marks an interesting link between conversation summarization and argumentation.

    More generally, approaches for the summarization of discussions have also been documented. Working on mailing list data, one approach clustered messages into subtopics and used centering to select sentences for an extractive summary \cite{newman2003summarizing}. The goal was to make what was a large collection of archived documents accessible for review - this is closely related to our task. The concept of recurring and related subtopics has been highlighted as being of greater importance to discussion summarization than the summarization of new wire data \cite{zhou2006summarization}. With topics changing more quickly in a question-response structure it is clear that the summarization of discussion requires a different approach to traditional multi-document summarization techniques.

    Moving the discussion towards more subjective texts, Opining Mining - with a view to summarization - is also relevant to the project. While, unlike a discussion, customer reviews are normally written in isolation of each other, research on their summarization offers some relevant ideas. One approach grouped sentences based on the feature discussed then proceeded to use these groups to generate a summary of all the reviews for a product that minimized repetition \cite{hu2004mining}. This task could be grouped under the more general area of `opinion summarization', as introduced at the Text Analysis Conference in 2008. One participating paper \cite{lloret2009towards} highlights the query-centered nature of the task. Opinion summarization work does not seem to go much beyond attaching polarity to features. While the TAC task does encapsulate the idea of `justification' for a given opinion, argumentation features are not the focus.

    More closely linked to our project is the idea of identifying agreement and disagreement, beyond positive and negative opinions. Galley et al. \cite{galley2004identifying} used adjacency pairs to target utterances that had been classified as being an agreement or disagreement. This does rely on the identification of conversation participants (they use a conversation with two speakers), a prerequisite that is harder to satisfy in discussion threads with multiple speakers. Closer to our work is that of Boltuzic and Snajder \cite{boltuzic2015identifying}, they set the challenging goal of identifying the prominent arguments an online debate. They worked with argumentative statements (rather than agreement/disagreement utterances) and used a hierarchical agglomerative clustering algorithm to group them.

    Work in the field of Argumentation Mining also bears similarities to our project. Argumentation schemes for discussions have been outlined \cite{ghosh2014analyzing}, this work sets out a process for identifying and grouping Argument Discourse Units using a two-tiered approach with expert and novice annotators. A key difference between this and our task is the reliance on human annotators.

    Cabrio and Villata \cite{cabrio2012combining} describe an approach based on Textual Entailment to give something of an overview of a debate. They cite that new participants to online discussions need to be updated on the history of accepted arguments made in the debate. Looking for accepted arguments in text goes beyond the argumentation features implemented as part of our project, however the goal of what could be described as debate summarization is highly related to ours.

    Work as has been done to investigate arguments raised in online discussion \cite{boltuzic2015identifying,cabrio2012combining,ghosh2014analyzing}. There has also been interest in the summarization of subjective content in discussions \cite{hu2004mining,lloret2009towards,galley2004identifying}. However, the use of argumentation as a basis for extractive summarization does not appear to have been investigated.

    In this project I explore the intersection of these two areas by generating summaries based on contrasting points made in the discussion.<commit_msg>Proof reading: Bg & Related<commit_after>\chapter{Background \& Related Work\label{chap:background-related}}
  \section{Background}
    This project builds on existing technologies and research. This section is intended to give an overview of past studies and other work relevant to the project.

    \tocless\subsection{Automatic Summarization}
      \blockquote{A summary can be loosely defined as a text that is produced from one or more texts, that conveys important information in the original text(s), and that is no longer than half of the original text(s) and usually significantly less than that.} \cite{radev2002introduction}

      Approaches to Automatic Summarization could be grouped loosely into two groups, extractive and abstractive. Extractive summaries are constructed reusing content found in the source text. Abstractive summaries are created by performing some form of analysis on the source text before generating new content for use in the summary. One might also group summarization tasks based on the nature of the source text - approaches tend to summarize either single or multiple documents. While project is more closely related to the summarization of multiple documents, it applies both elements of extractive and abstractive summarization.

      \subsubsection{Multi-document Summarization}
        Summarizing text made up of documents from different authors poses an interesting challenge. Using multiple documents introduces repetition and contradictions. This makes summarization selection tasks such as extraction and compression more complex.

        Earlier work on multi-document summarization suggested the task was going to require an abstractive approach because not being able to connect information between documents would lead to incoherent and repetitive summaries \cite{McKeown1999TMS315149315355}. An alternative approach clustered paragraphs on the same topic from multiple documents and then use \textit{Natural Language Generation} techniques to combine phrases from paragraphs into a coherent summary \cite{McKeown1999TMS315149315355}. A similar approach creates clusters by parsing sentences and using predicate-argument structures to link phrases \cite{barzilay1999information} making it somewhat related to our approach. Interestingly, while both methods rely on natural language generation, neither use a semantic representation (which is commonly used in NLG tasks).

        More recently, MEAD, a centroid-based, multi-document summarization tool has been able to produce quality summaries without abstraction and generation \cite{radev2000centroid}. Compared to previous abstractive systems such as SUMMONS that relied on templates \cite{mckeown1995generating}, MEAD was more generally applicable. Both these projects, and indeed most work on the summarization of multi-document sources has focused on news articles. While there are parallels between this and the summarization of online discussion, fundamentally they are different tasks.

        More closely related to this project is the topic of Opinion Mining or Sentiment Analysis, this is an approach often applied to user reviews, `documents' discussing a product or service. Early work in the area focused on the problem as a classification task, categorizing documents based on their sentiment bearing terms \cite{turney2002thumbs}. More recently there as been a greater focus on aspect-based approaches that attempt isolate sentiment terminology to specific aspects references in the text \cite{hu2004mining}.

      \subsubsection{Sentence Compression \& Content Unit Size}
        While sentences are the default content unit used in extractive summarization, often smaller units are preferable. Sentences found in real documents and discussions can make a number of statements each of which can be useful when creating a summary. Sentences often include surplus information such as references to other parts of the source text. In this case sentences can be compressed statistically, in a similar way to documents are in extractive summarization. Both noisy channel and decision based models have used on parsed sentences for the task of sentence compression \cite{knight2000statistics}. Our approach for sentence compression, where points are extracted around a verb, does not appear to have been previously documented.

        Selecting the content unit for a summarization task is challenging. One might think that sentences could be relied upon as coherent content unit but poor grammar and unresolved co-referring expressions mean this is often not the case \cite{witbrock1999ultra}.

      \subsubsection{Evaluation of Summaries}
        The evaluation of automatically generated summaries is an ongoing discussion. A common approach is to make a comparison against a model summary, written by a human. Various metrics such as ROUGE \cite{lin2004rouge} are used to make the comparison between summaries statistically. These are however limited by the assumption that there is a single best model for a summary. Alternative methods have been proposed. The Pyramid Method is one such example, it models content units across the collection of summaries being evaluated to give each content unit a weight based on how commonly it occurs \cite{nenkova2004evaluating}. These weights are used to allocate scores to summaries without an ordering bias.

        Automated methods are used primarily at the \textit{Document Understanding Conference} when many summaries must be evaluated for a given task. Ideally however summaries could be manually evaluated. This would allow extrinsic attributes such as the utility of a summary for a particular task to also be accounted for. \textbf{(reference to SUMMAC?, automated http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.489)}

        In this project we compare summaries against those generated using the approach outlined by Nenkova et al. \cite{nenkova2006compositional} as a baseline. Summaries are scored by human judges.

    \tocless\subsection{Argumentation Mining}
      Argumentation Mining is a task that involves the identification of argument components in text, premises and conclusions for example. The task often involves fitting these components into a template or known pattern to enable some form of reasoning. \cite{palau2009argumentation}

      A relatively new research area - combining ideas from natural language processing, information extraction and argumentation theory - Argumentation Mining is based largely on discourse theory. While Argumentation Mining can be applied to structured text (source?), ultimately mining of free text is the goal. This means that argumentation tools often need to model concepts from linguistic research such as rhetoric structure theory \cite{mann1988rhetorical} and local coherence centering \cite{weinstein21centering} to identify structure.

      \subsubsection{Identifying Argumentative Structures in Text}
        When identifying argumentative structures in text the first step is often to classify phrases that are part of an argument. One option is to define rules for argumentative sentences or clauses. This can also be approached as a classification task, statistical methods such naive-bayes have also been used \cite{palau2009argumentation}. The result of this stage is a collection of unrelated clauses potentially spanning many arguments present in the source text.

        The next stage in the analysis is to group identified units together into separate arguments. Sometimes the document structure (chapters and sections) can be used to inform the grouping task, however this is hard to generalize. Documents are rarely consistently formatted and arguments will often span many sections. Other options include grouping based on the similarity of the unit's contents such presence of certain words. \cite{palau2009argumentation}

        Once identified units have been grouped into different arguments it becomes possible to start reasoning on the argument's structure. Different units need to be classified as either premises or conclusions - this can again be approached as a classification task \cite{palau2009argumentation}. Once a structure for the units has been established it's possible to do analysis on this connected graph structure to identify supporting claims for conclusions.

        A further task is relating arguments within the document to one another, this is a far more challenging task. Fitting the argument structure to allowed patterns defined by a context-free grammar is one proposed approach \cite{palau2009argumentation}.

    \tocless\subsection{Dependencies}
      The approach implemented as part of this project relies on the products of research in the areas discussed in this section. While these are not core tot he work presented as part fo this project, it is important to understand their basic behavior.
      \subsubsection{Topic Modeling}
        Topic modeling covers a set statistical modeling techniques used to identify and group topics in text. Fundamentally, this involves identifying words that are relatively more common in one document vs a larger collection of documents. Documents often contain multiple topic words that need to be grouped into more conceptual topics. One approach to this is is \textit{Latent Dirichlet Allocation} (LDA), this implements a ``three-level hierarchical Bayesian model'' \cite{blei2003latent} and is the implementation used for topic modeling in this project.
      \subsubsection{Dependency Parsers}
        Parsing text for dependencies involves building upon a phrasal parse to extract relations between tokens in text - dependencies are identified using rules applied to phrase structure trees. Various dependency parsers exist, this project makes use of the dependency parser included as part of the Stanford CoreNLP framework \cite{de2006generating} which is based on their probabilistic context-free grammar phrasal parser \cite{klein2003accurate}. The rules used in the Stanford dependency parser based on \textit{Universal Stanford Dependencies} \cite{de2014universal}.
      \subsubsection{Querying Dependency Parses}
        To make use of a dependency parse, one needs a means of querying the graph. \textit{Semgrex} is one such approach, this defines a regular expression style syntax for formulating queries on nodes and relations in a dependency graph \cite{Chambers2007}. However, more fundamentally, the task involves querying nodes and edges in a directional graph. For this project we opted to use \textit{Cypher}\footnote{http://neo4j.com/docs/stable/cypher-introduction.html}, the graph query language implemented by the \textit{Neo4j}\footnote{http://neo4j.com/} graph database. This was chosen for the querying of dependency parses as it allowed many separate graphs to be queried in parallel for the same pattern using a declarative syntax.

  \section{Related Work}
    Having covered the technologies and areas of research that underpin this project I will now discuss related work that comes closer to combining these two areas, as this our project does.

    While most summarization research has been in the newswire domain, work has been done to summarize more conversational texts. This differs from speech summarization as source content is typed rather than spoken, removing many additional difficulties. Documented business conversations such as email threads and meeting minutes are a common use case. In email threads (collective message summarization), a common approach to summarization is to identify question and answer pairs \cite{shrestha2007using,shrestha2004detection,carenini2007summarizing}. Questions can be identified using a classifier trained on a corpus that annotates speech acts \cite{shrestha2004detection}. The quotation formatting used in emails can also provide question-answer pairs - one approach used word overlap to link text to quoted segments \cite{carenini2007summarizing}. The use of speech acts for summarization of email appears to have originally been used in the \textit{SmartMail} project \cite{corston2004task}, this technique marks an novel link between conversation summarization and argumentation.

    More generally, approaches for the summarization of discussions have also been documented. Working on mailing list data, one approach clustered messages into subtopics and used centering to select sentences for an extractive summary \cite{newman2003summarizing}. The goal was to make what was a large collection of archived documents accessible for review - this is closely related to our task. The concept of recurring and related subtopics has been highlighted as being of greater importance to discussion summarization than the summarization of new wire data \cite{zhou2006summarization}. With topics changing more quickly in a question-response structure it is clear that the summarization of discussion requires a different approach to traditional multi-document summarization techniques.

    Moving the discussion towards more subjective texts, Opining Mining - with a view to summarization - is also relevant to the project. While, unlike a discussion, customer reviews are normally written in isolation of each other, research on their summarization offers some relevant ideas. One approach grouped sentences based on the feature discussed then proceeded to use these groups to generate a summary of all the reviews for a product that minimized repetition \cite{hu2004mining}. This task could be grouped under the more general area of `opinion summarization', as introduced at the \textit{Text Analysis Conference} in 2008. One participating paper by Lloret et al. \cite{lloret2009towards} highlights the query-centered nature of the task. Opinion summarization work is typically limited to attaching polarity to features. While the TAC task does encapsulate the idea of `justification' for a given opinion, argumentation features are not the focus.

    More closely linked to our project is the idea of identifying agreement and disagreement, beyond positive and negative opinions. Galley et al. \cite{galley2004identifying} used adjacency pairs to target utterances that had been classified as being an agreement or disagreement. This does rely on the identification of conversation participants (they use a conversation with two speakers), a prerequisite that is harder to satisfy in discussion threads. Closer to our work is that of Boltuzic and Snajder \cite{boltuzic2015identifying}, they set the challenging goal of identifying the prominent arguments an online discussions. They worked with argumentative statements (rather than agreement/disagreement utterances) and used a hierarchical agglomerative clustering algorithm to group them.

    Work in the field of Argumentation Mining also bears similarities to our project. Argumentation schemes for discussions have been outlined \cite{ghosh2014analyzing}, this work sets out a process for identifying and grouping \textit{Argument Discourse Units} using a two-tiered approach with expert and novice annotators. A key difference between this and our task is the reliance on human annotators.

    Cabrio and Villata \cite{cabrio2012combining} describe an approach based on Textual Entailment to give something of an overview of a debate. They cite that new participants to online discussions need to be updated on the history of accepted arguments made in the debate. Looking for accepted arguments in text goes beyond the argumentation features implemented as part of our project, however their goal of what might be described as debate summarization is highly related to ours.

    Work as has been done to investigate arguments raised in online discussion \cite{boltuzic2015identifying,cabrio2012combining,ghosh2014analyzing}. There has also been interest in the summarization of subjective content in discussions \cite{hu2004mining,lloret2009towards,galley2004identifying}. However, the use of argumentation as a basis for extractive summarization does not appear to have been investigated.

    In this project I explore the intersection of these two areas by generating summaries based on contrasting points made in discussions.
{'fraction_non_alphanumeric': 0.029272078224429614, 'fraction_numerical': 0.013534067980754306, 'mean_word_length': 4.990330978058758, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7371654', 'n_tokens_mistral': 7124, 'n_tokens_neox': 6421, 'n_words': 4324}