A Novel ILP Framework for Summarizing Content with High Lexical Variety

Abstract: Summarizing content contributed by individuals can be challenging, because people make different lexical choices even when describing the same events. However, there remains a significant need to summarize such content. Examples include the student responses to post-class reflective questions, product reviews, and news articles published by different news agencies related to the same events. High lexical diversity of these documents hinders the system's ability to effectively identify salient content and reduce summary redundancy. In this paper, we overcome this issue by introducing an integer linear programming-based summarization framework. It incorporates a low-rank approximation to the sentence-word co-occurrence matrix to intrinsically group semantically-similar lexical items. We conduct extensive experiments on datasets of student responses, product reviews, and news documents. Our approach compares favorably to a number of extractive baselines as well as a neural abstractive summarization system. The paper finally sheds light on when and why the proposed framework is effective at summarizing content with high lexical variety.

Summarization is a promising technique for reducing information overload. It aims at converting long text documents to short, concise summaries conveying the essential content of the source documents BIBREF0 . Extractive methods focus on selecting important sentences from the source and concatenating them to form a summary, whereas abstractive methods can involve a number of high-level text operations such as word reordering, paraphrasing, and generalization BIBREF1 . To date, summarization has been successfully exploited for a number of text domains, including news articles BIBREF2 , BIBREF3 , BIBREF4 , BIBREF5 , product reviews BIBREF6 , online forum threads BIBREF7 , meeting transcripts BIBREF8 , scientific articles BIBREF9 , BIBREF10 , student course responses BIBREF11 , BIBREF12 , and many others.
Summarizing content contributed by multiple authors is particularly challenging. This is partly because people tend to use different expressions to convey the same semantic meaning. In a recent study of summarizing student responses to post-class reflective questions, Luo et al., Luo:2016:NAACL observe that the students use distinct lexical items such as “bike elements” and “bicycle parts” to refer to the same concept. The student responses frequently contain expressions with little or no word overlap, such as “the main topics of this course” and “what we will learn in this class,” when they are prompted with “describe what you found most interesting in today's class.” A similar phenomenon has also been observed in the news domain, where reporters use different nicknames, e.g., “Bronx Zoo” and “New York Highlanders,” to refer to the baseball team “New York Yankees.” Luo et al., Luo:2016:NAACL report that about 80% of the document bigrams occur only once or twice for the news domain, whereas the ratio is 97% for student responses, suggesting the latter domain has a higher level of lexical diversity. When source documents contain diverse expressions conveying the same meaning, it can hinder the summarization system's ability to effectively identify salient content from the source documents. It can also increase the summary redundancy if lexically-distinct but semantically-similar expressions are included in the summary.
Existing neural encoder-decoder models may not work well at summarizing such content with high lexical variety BIBREF13 , BIBREF14 , BIBREF15 , BIBREF16 . On one hand, training the neural sequence-to-sequence models requires a large amount of parallel data. The cost of annotating gold-standard summaries for many domains such as student responses can be prohibitive. Without sufficient labelled data, the models can only be trained on automatically gathered corpora, where an instance often includes a news article paired with its title or a few highlights. On the other hand, the summaries produced by existing neural encoder-decoder models are far from perfect. The summaries are mostly extractive with minor edits BIBREF16 , contain repetitive words and phrases BIBREF17 and may not accurately reproduce factual details BIBREF18 , BIBREF19 . We examine the performance of a state-of-the-art neural summarization model in Section § SECREF28 .
In this work, we propose to augment the integer linear programming (ILP)-based summarization framework with a low-rank approximation of the co-occurrence matrix, and further evaluate the approach on a broad range of datasets exhibiting high lexical diversity. The ILP framework, being extractive in nature, has demonstrated considerable success on a number of summarization tasks BIBREF20 , BIBREF21 . It generates a summary by selecting a set of sentences from the source documents. The sentences shall maximize the coverage of important source content, while minimizing the redundancy among themselves. At the heart of the algorithm is a sentence-concept co-occurrence matrix, used to determine if a sentence contains important concepts and whether two sentences share the same concepts. We introduce a low-rank approximation to the co-occurrence matrix and optimize it using the proximal gradient method. The resulting system thus allows different sentences to share co-occurrence statistics. For example, “The activity with the bicycle parts" will be allowed to partially contain “bike elements" although the latter phrase does not appear in the sentence. The low-rank matrix approximation provides an effective way to implicitly group lexically-diverse but semantically-similar expressions. It can handle out-of-vocabulary expressions and domain-specific terminologies well, hence being a more principled approach than heuristically calculating similarities of word embeddings.
Our research contributions of this work include the following.
In the following sections we first present a thorough review of the related work (§ SECREF2 ), then introduce our ILP summarization framework (§ SECREF3 ) with a low-rank approximation of the co-occurrence matrix optimized using the proximal gradient method (§ SECREF4 ). Experiments are performed on a collection of eight datasets (§ SECREF5 ) containing student responses to post-class reflective questions, product reviews, peer reviews, and news articles. Intrinsic evaluation (§ SECREF20 ) shows that the low-rank approximation algorithm can effectively group distinct expressions used in similar semantic context. For extrinsic evaluation (§ SECREF28 ) our proposed framework obtains competitive results in comparison to state-of-the-art summarization systems. Finally, we conduct comprehensive studies analyzing the characteristics of the datasets and suggest critical factors that affect the summarization performance (§ SECREF7 ).
Extractive summarization has undergone great development over the past decades. It focuses on extracting relevant sentences from a single document or a cluster of documents related to a particular topic. Various techniques have been explored, including maximal marginal relevance BIBREF22 , submodularity BIBREF23 , integer linear programming BIBREF24 , BIBREF25 , BIBREF26 , BIBREF27 , BIBREF4 , minimizing reconstruction error BIBREF28 , graph-based models BIBREF29 , BIBREF30 , BIBREF31 , BIBREF32 , determinantal point processes BIBREF33 , neural networks and reinforcement learning BIBREF34 , BIBREF35 among others. Nonetheless, most studies are bound to a single dataset and few approaches have been evaluated in a cross-domain setting. In this paper, we propose an enhanced ILP framework and evaluate it on a broad range of datasets. We present an in-depth analysis of the dataset characteristics derived from both source documents and reference summaries to understand how domain-specific factors may affect the applicability of the proposed approach.
Neural summarization has seen promising improvements in recent years with encoder-decoder models BIBREF13 , BIBREF14 . The encoder condenses the source text to a dense vector, whereas the decoder unrolls the vector to a summary sequence by predicting one word at a time. A number of studies have been proposed to deal with out-of-vocabulary words BIBREF16 , improve the attention mechanism BIBREF36 , BIBREF37 , BIBREF38 , avoid generating repetitive words BIBREF16 , BIBREF17 , adjust summary length BIBREF39 , encode long text BIBREF40 , BIBREF41 and improve the training objective BIBREF42 , BIBREF15 , BIBREF43 . To date, these studies focus primarily on single-document summarization and headline generation. This is partly because training neural encoder-decoder models requires a large amount of parallel data, yet the cost of annotating gold-standard summaries for most domains can be prohibitive. We validate the effectiveness of a state-of-the-art neural summarization system BIBREF16 on our collection of datasets and report results in § SECREF28 .
In this paper we focus on the integer linear programming-based summarization framework and propose enhancements to it to summarize text content with high lexical diversity. The ILP framework is shown to perform strongly on extractive summarization BIBREF20 , BIBREF44 , BIBREF21 . It produces an optimal selection of sentences that (i) maximize the coverage of important concepts discussed in the source, (ii) minimize the redundancy in pairs of selected sentences, and (iii) ensure the summary length does not exceed a limit. Previous work has largely focused on improving the estimation of concept weights in the ILP framework BIBREF45 , BIBREF46 , BIBREF47 , BIBREF48 , BIBREF4 . However, distinct lexical items such as “bike elements” and “bicycle parts” are treated as different concepts and their weights are not shared. In this paper we overcome this issue by proposing a low-rank approximation to the sentence-concept co-occurrence matrix to intrinsically group lexically-distinct but semantically-similar expressions; they are considered as a whole when maximizing concept coverage and minimizing redundancy.
Our work is also different from the traditional approaches using dimensionality reduction techniques such as non-negative matrix factorization (NNMF) and latent semantic analysis (LSA) for summarization BIBREF49 , BIBREF50 , BIBREF51 , BIBREF52 , BIBREF53 . In particular, Wang et al. wang2008multi use NNMF to group sentences into clusters; Conroy et al. conroy-EtAl:2013:MultiLing explore NNMF and LSA to obtain better estimates of term weights; Wang et al. wang2016low use low-rank approximation to cast sentences and images to the same embedding space. Different from the above methods, our proposed framework focuses on obtaining a low-rank approximation of the co-occurrence matrix embedded in the ILP framework, so that diverse expressions can share co-occurrence frequencies. Note that out-of-vocabulary expressions and domain-specific terminologies are abundant in our datasets, therefore simply calculating the lexical overlap BIBREF54 or cosine similarity of word embeddings BIBREF55 cannot serve our goal well.
This manuscript extends our previous work on summarizing student course responses BIBREF11 , BIBREF56 , BIBREF12 submitted after each lecture via a mobile app named CourseMIRROR BIBREF57 , BIBREF58 , BIBREF59 . The students are asked to respond to reflective prompts such as “describe what you found most interesting in today's class” and “describe what was confusing or needed more detail.” For large classes with hundreds of students, it can be quite difficult for instructors to manually analyze the student responses, hence the help of automatic summarization. Our extensions of this work are along three dimensions: (i) we crack the “black-box” of the low-rank approximation algorithm to understand if it indeed allows lexically-diverse but semantically-similar items to share co-occurrence statistics; (ii) we compare the ILP-based summarization framework with state-of-the-art baselines, including a popular neural encoder-decoder model for summarization; (iii) we expand the student feedback datasets to include responses collected from materials science and engineering, statistics for industrial engineers, and data structures. We additionally experiment with reviews and news articles. Analyzing the unique characteristics of each dataset allows us to identify crucial factors influencing the summarization performance.
With the fast development of Massive Open Online Courses (MOOC) platforms, more attention is being dedicated to analyzing educationally-oriented language data. These studies seek to identify student leaders from MOOC discussion forums BIBREF60 , perform sentiment analysis on student discussions BIBREF61 , improve student engagement and reducing student retention BIBREF62 , BIBREF63 , and using language generation techniques to automatically generate feedback to students BIBREF64 . Our focus of this paper is to automatically summarizing student responses so that instructors can collect feedback in a timely manner. We expect the developed summarization techniques and result analysis will further summarization research in similar text genres exhibiting high lexical variety.
Let INLINEFORM0 be a set of documents that consist of INLINEFORM1 sentences in total. Let INLINEFORM2 , INLINEFORM3 indicate if a sentence INLINEFORM4 is selected ( INLINEFORM5 ) or not ( INLINEFORM6 ) in the summary. Similarly, let INLINEFORM7 be the number of unique concepts in INLINEFORM8 . INLINEFORM9 , INLINEFORM10 indicate the appearance of concepts in the summary. Each concept INLINEFORM11 is assigned a weight of INLINEFORM12 , often measured by the number of sentences or documents that contain the concept. The ILP-based summarization approach BIBREF20 searches for an optimal assignment to the sentence and concept variables so that the selected summary sentences maximize coverage of important concepts. The relationship between concepts and sentences is captured by a co-occurrence matrix INLINEFORM13 , where INLINEFORM14 indicates the INLINEFORM15 -th concept appears in the INLINEFORM16 -th sentence, and INLINEFORM17 otherwise. In the literature, bigrams are frequently used as a surrogate for concepts BIBREF24 , BIBREF21 . We follow the convention and use `concept' and `bigram' interchangeably in this paper.
Two sets of linear constraints are specified to ensure the ILP validity: (1) a concept is selected if and only if at least one sentence carrying it has been selected (Eq. ), and (2) all concepts in a sentence will be selected if that sentence is selected (Eq. ). Finally, the selected summary sentences are allowed to contain a total of INLINEFORM0 words or less (Eq. ). DISPLAYFORM0 
The above ILP can be transformed to matrix representation: DISPLAYFORM0 
We use boldface letters to represent vectors and matrices. INLINEFORM0 is an auxiliary matrix created by horizontally stacking the concept vector INLINEFORM1 INLINEFORM2 times. Constraint set (Eq. ) specifies that a sentence is selected indicates that all concepts it carries have been selected. It corresponds to INLINEFORM3 constraints of the form INLINEFORM4 , where INLINEFORM5 .
As far as we know, this is the first-of-its-kind matrix representation of the ILP framework. It clearly shows the two important components of this framework, including 1) the concept-sentence co-occurrence matrix INLINEFORM0 , and 2) concept weight vector INLINEFORM1 . Existing work focus mainly on generating better estimates of concept weights ( INLINEFORM2 ), while we focus on improving the co-occurrence matrix INLINEFORM3 .
Because of the lexical diversity problem, we suspect the co-occurrence matrix INLINEFORM0 may not establish a faithful correspondence between sentences and concepts. A concept may be conveyed using multiple bigram expressions; however, the current co-occurrence matrix only captures a binary relationship between sentences and bigrams. For example, we ought to give partial credit to “bicycle parts” given that a similar expression “bike elements” appears in the sentence. Domain-specific synonyms may be captured as well. For example, the sentence “I tried to follow along but I couldn't grasp the concepts” is expected to partially contain the concept “understand the”, although the latter did not appear in the sentence.
The existing matrix INLINEFORM0 is highly sparse. Only 3.7% of the entries are non-zero in the student response data sets on average (§ SECREF5 ). We therefore propose to impute the co-occurrence matrix by filling in missing values (i.e., matrix completion). This is accomplished by approximating the original co-occurrence matrix using a low-rank matrix. The low-rankness encourages similar concepts to be shared across sentences.
The ILP with a low-rank approximation of the co-occurrence matrix can be formalized as follows. DISPLAYFORM0 
The low-rank approximation process makes two notable changes to the existing ILP framework.
Concretely, given the co-occurrence matrix INLINEFORM0 , we aim to find a low-rank matrix INLINEFORM1 whose values are close to INLINEFORM2 at the observed positions. Our objective function is DISPLAYFORM0 
where INLINEFORM0 represents the set of observed value positions. INLINEFORM1 denotes the trace norm of INLINEFORM2 , i.e., INLINEFORM3 , where INLINEFORM4 is the rank of INLINEFORM5 and INLINEFORM6 are the singular values. By defining the following projection operator INLINEFORM7 , DISPLAYFORM0 
our objective function (Eq. EQREF10 ) can be succinctly represented as DISPLAYFORM0 
where INLINEFORM0 denotes the Frobenius norm.
Following Mazumder et al. Mazumder:2010, we optimize Eq. EQREF12 using the proximal gradient descent algorithm. The update rule is DISPLAYFORM0 
where INLINEFORM0 is the step size at iteration k and the proximal function INLINEFORM1 is defined as the singular value soft-thresholding operator, INLINEFORM2 , where INLINEFORM3 is the singular value decomposition (SVD) of INLINEFORM4 and INLINEFORM5 .
Since the gradient of INLINEFORM0 is Lipschitz continuous with INLINEFORM1 ( INLINEFORM2 is the Lipschitz continuous constant), we follow Mazumder et al. Mazumder:2010 to choose fixed step size INLINEFORM3 , which has a provable convergence rate of INLINEFORM4 , where INLINEFORM5 is the number of iterations.
To demonstrate the generality of the proposed approach, we consider three distinct types of corpora, ranging from student response data sets from four different courses to three sets of reviews to one benchmark of news articles. The corpora are summarized in Table TABREF14 .
Student responses. Research has explored using reflection prompts/muddy cards/one-minute papers to promote and collect reflections from students BIBREF65 , BIBREF66 , BIBREF67 . However, it is expensive and time consuming for humans to summarize such feedback. It is therefore desirable to automatically summarize the student feedback produced in online and offline environments, although it is only recently that a data collection effort to support such research has been initiated BIBREF58 , BIBREF57 . In our data, one particular type of student response is considered, named “reflective feedback” BIBREF68 , which has been shown to enhance interaction between instructors and students by educational researchers BIBREF69 , BIBREF70 . More specifically, students are presented with the following prompts after each lecture and asked to provide responses: 1) “describe what you found most interesting in today's class,” 2) “describe what was confusing or needed more detail,” and 3) “describe what you learned about how you learn.” These open-ended prompts are carefully designed to encourage students to self-reflect, allowing them to “recapture experience, think about it and evaluate it" BIBREF68 .
To test generality, we gathered student responses from four different courses, as shown in Table TABREF14 . The first one was collected by Menekse et al. Menekse:2011 using paper-based surveys from an introductory materials science and engineering class (henceforth Eng) taught in a major U.S. university, and a subset is made public by us BIBREF11 , available at the link: http://www.coursemirror.com/download/dataset. The remaining three courses are collected by us using a mobile application, CourseMIRROR BIBREF57 , BIBREF58 and then the reference summaries for each course are created by human annotators with the proper background. The human annotators are allowed to create abstract summaries using their own words in addition to selecting phrases directly from the responses. While the 2nd and 3rd data sets are from the same course, Statistics for Industrial Engineers, they were taught in 2015 and 2016 respectively (henceforth Stat2015 and Stat2016), at the Boǧaziçi University in Turkey. The course was taught in English while the official language is Turkish. The last one is from a fundamental undergraduate Computer Science course (data structures) at a local U.S. university taught in 2016 (henceforth CS2016).
Another reason we choose the student responses is that we have advanced annotation allowing us to perform an intrinsic evaluation to test whether the low-rank approximation does capture similar concepts or not. An example of the annotation is shown in Table TABREF15 , where phrases in the student responses that are semantically the same as the summary phrases are highlighted with the same color by human annotators. For example, “error bounding" (S2), “error boundary" (S4), “finding that error" (S3), and “determining the critical value for error" (S7) are semantically equivalent to “Error bounding" in the human summary. Details of the intrinsic evaluation are introduced in SECREF20 .
Product and peer reviews. The review data sets are provided by Xiong and Litman xiong-litman:2014:Coling, consisting of 3 categories. The first one is a subset of product reviews from a widely used data set in review opinion mining and sentiment analysis, contributed by Jindal and Liu jindal2008opinion. In particular, it randomly sampled 3 set of reviews from a representative product (digital camera), each with 18 reviews from an individual product type (e.g. “summarizing 18 camera reviews for Nikon D3200"). The second one is movie reviews crawled from IMDB.com by the authors themselves. The third one is peer reviews collected in a college-level history class from an online peer-review reciprocal system, SWoRD BIBREF71 . The average number of sentences per review set is 85 for camera reviews, 328 for movie reviews and 80 for peer review; the average number of words per sentence in the camera, movie, and peer reviews are 23, 24 and 19, respectively. The human summaries were collected in the form of online surveys (one survey per domain) hosted by Qualtrics. Each human summary contains 10 sentences from users' reviews. Example movie reviews are shown in Table TABREF17 .
News articles. Most summarization work focuses on news documents, as driven by the Document Understanding Conferences (DUC) and Text Analysis Conferences (TAC). For comparison, we select DUC 2004 to evaluate our approach (henceforth DUC04), which is widely used in the literature BIBREF72 , BIBREF73 , BIBREF74 , BIBREF75 , BIBREF76 . It consists of 50 clusters of Text REtrieval Conference (TREC) documents, from the following collections: AP newswire, 1998-2000; New York Times newswire, 1998-2000; Xinhua News Agency (English version), 1996-2000. Each cluster contained on average 10 documents. The task is to create a short summary ( INLINEFORM0 665 bytes) of each cluster. Example news sentences are shown in Table TABREF19 .
In this section, we evaluate the proposed method intrinsically in terms of whether the co-occurrence matrix after the low-rank approximation is able to capture similar concepts on student response data sets, and also extrinsically in terms of the end task of summarization on all corpora. In the following experiments, summary length is set to be the average number of words in human summaries or less. For the matrix completion algorithm, we perform grid search (on a scale of [0, 5] with stepsize 0.5) to tune the hyper-parameter INLINEFORM0 (Eq. EQREF10 ) with a leave-one-lecture-out (for student responses) or leave-one-task-out (for others) cross-validation.
When examining the imputed sentence-concept co-occurrence matrix, we notice some interesting examples that indicate the effectiveness of the proposed approach, shown in Table TABREF21 .
We want to investigate whether the matrix completion (MC) helps to capture similar concepts (i.e., bigrams). Recall that, if a bigram INLINEFORM0 is similar to another bigram in a sentence INLINEFORM1 , the sentence INLINEFORM2 should assign a partial score to the bigram INLINEFORM3 after the low-rank approximation. For instance, “The activity with the bicycle parts" should give a partial score to “bike elements" since it is similar to “bicycle parts". Note that, the co-occurrence matrix INLINEFORM4 measures whether a sentence includes a bigram or not. Without matrix completion, if a bigram INLINEFORM5 does not appear in a sentence INLINEFORM6 , INLINEFORM7 . After matrix completion, INLINEFORM8 ( INLINEFORM9 is the low-rank approximation matrix of INLINEFORM10 ) becomes a continuous number ranging from 0 to 1 (negative values are truncated). Therefore, INLINEFORM11 does not necessarily mean the sentence contains a similar bigram, since it might also give positive scores to non-similar bigrams. To solve this issue, we propose two different ways to test whether the matrix completion really helps to capture similar concepts.
H1.a: A bigram receives a higher partial score in a sentence that contains similar bigram(s) to it than a sentence that does not. That is, if a bigram INLINEFORM0 is similar to one of bigrams in a sentence INLINEFORM1 , but not similar to any bigram in another sentence INLINEFORM2 , then after matrix completion, INLINEFORM3 .
H1.b: A sentence gives higher partial scores to bigrams that are similar to its own bigrams than bigrams that are different from its own. That is, if a sentence INLINEFORM0 has a bigram that is similar to INLINEFORM1 , but none of its bigrams is similar to INLINEFORM2 , then, after matrix completion, INLINEFORM3 .
In order to test these two hypotheses, we need to construct gold-standard pairs of similar bigrams and pairs of different bigrams, which can be automatically obtained with the phrase-highlighting data (Table TABREF15 ). We first extract a candidate bigram from a phrase if and only if a single bigram can be extracted from the phrase. In this way, we discard long phrases if there are multiple candidate bigrams among them in order to avoid ambiguity as we cannot validate which of them match another target bigram. A bigram is defined as two words and at least one of them is not a stop word. We then extract every pair of candidate bigrams that are highlighted in the same color as similar bigrams. Similarly, we extract every pair of candidate bigrams that are highlighted as different colors as different bigrams. For example, “bias reduction" is a candidate phrase, which is similar to “bias correction" since they are in the same color.
To test H1.a, given a bigram INLINEFORM0 , a bigram INLINEFORM1 that is similar to it, and a bigram INLINEFORM2 that is different from it, we can select the bigram INLINEFORM3 , and the sentence INLINEFORM4 that contains INLINEFORM5 , and the sentence INLINEFORM6 that contains INLINEFORM7 . We ignore INLINEFORM8 if it contains any other bigram that is similar to INLINEFORM9 to eliminate the compounded case that both similar and different bigrams are within one sentence. Note, if there are multiple sentences containing INLINEFORM10 , we consider each of them. In this way, we construct a triple INLINEFORM11 , and test whether INLINEFORM12 . To test H1.b, for each pair of similar bigrams INLINEFORM13 , and different bigrams INLINEFORM14 , we select the sentence INLINEFORM15 that contains INLINEFORM16 so that we construct a triple INLINEFORM17 , and test whether INLINEFORM18 . We also filtered out INLINEFORM19 that contains similar bigram(s) to INLINEFORM20 to remove the compounded effect. In this way, we collected a gold-standard data set to test the two hypotheses above as shown in Table TABREF24 .
The results are shown in Table TABREF25 . INLINEFORM0 significantly on all three courses. That is, a bigram does receive a higher partial score in a sentence that contains similar bigram(s) to it than a sentence that does not. Therefore, H1.a holds. For H1.b, we only observe INLINEFORM1 significantly on Stat2016 and there is no significant difference between INLINEFORM2 and INLINEFORM3 on the other two courses. First, the gold-standard data set is still small in the sense that only a limited portion of bigrams in the entire data set are evaluated. Second, the assumption that phrases annotated by different colors are not necessarily unrelated is too strong. For example, “hypothesis testing" and “H1 and Ho conditions" are in different colors in the example of Table TABREF15 , but one is a subtopic of the other. An alternative way to evaluate the hypothesis is to let humans judge whether two bigrams are similar or not, which we leave for future work. Third, the gold standards are pairs of semantically similar bigrams, while matrix completion captures bigrams that occurs in a similar context, which is not necessarily equivalent to semantic similarity. For example, the sentence “graphs make it easier to understand concepts" in Table TABREF25 is associated with “hard to".
Our proposed approach is compared against a range of baselines. They are 1) MEAD BIBREF30 , a centroid-based summarization system that scores sentences based on length, centroid, and position; 2) LexRank BIBREF29 , a graph-based summarization approach based on eigenvector centrality; 3) SumBasic BIBREF77 , an approach that assumes words occurring frequently in a document cluster have a higher chance of being included in the summary; 4) Pointer-Generator Networks (PGN) BIBREF16 , a state-of-the-art neural encoder-decoder approach for abstractive summarization. The system was trained on the CNN/Daily Mail data sets BIBREF78 , BIBREF14 . 5) ILP BIBREF21 , a baseline ILP framework without matrix completion.
The Pointer-Generator Networks BIBREF16 describes a neural encoder-decoder architecture. It encourages the system to copy words from the source text via pointing, while retaining the ability to produce novel words through the generator. It also contains a coverage mechanism to keep track of what has been summarized, thus reducing word repetition. The pointer-generator networks have not been tested for summarizing content contributed by multiple authors. In this study we evaluate their performance on our collection of datasets.
For the ILP-based approaches, we use bigrams as concepts (bigrams consisting of only stopwords are removed) and term frequency as concept weights. We leverage the co-occurrence statistics both within and across the entire corpus. We also filtered out bigrams that appear only once in each corpus, yielding better ROUGE scores with lower computational cost. The results without using this low-frequency filtering are shown in the Appendix for comparison. In Table TABREF26 , we present summarization results evaluated by ROUGE BIBREF72 and human judges.
To compare with the official participants in DUC 2004 BIBREF79 , we selected the top-5 systems submitted in the competition (ranked by R-1), together with the 8 human annotators. The results are presented in Table TABREF27 .
ROUGE. It is a recall-oriented metric that compares system and reference summaries based on n-gram overlaps, which is widely used in summarization evaluation. In this work, we report ROUGE-1 (R-1), ROUGE-2 (R-2), ROUGE-SU4 (R-SU4), and ROUGE-L (R-L) scores, which respectively measure the overlap of unigrams, bigrams, skip-bigram (with a maximum gap length of 4), and longest common subsequence. First, there is no winner for all data sets. MEAD is the best one on camera; SumBasic is best on Stat2016 and mostly on Stat2015; ILP is best on DUC04. The ILP baseline is comparable to the best participant (Table TABREF27 ) and even has the best R-2. PGN is the worst, which is not surprising since it is trained on a different data set, which may not generalize to our data sets. Our method ILP+MC is best on peer review and mostly on Eng and CS2016. Second, compared with ILP, our method works better on Eng, CS2016, movie, and peer.
These results show our proposed method does not always better than the ILP framework, and no single summarization system wins on all data sets. It is perhaps not surprising to some extent. The no free lunch theorem for machine learning BIBREF80 states that, averaged overall possible data-generating distributions, every classiﬁcation algorithm has the same error rate when classifying previously unobserved points. In other words, in some sense, no machine learning algorithm is universally any better than any other BIBREF81 .
Human Evaluation. Because ROUGE cannot thoroughly capture the semantic similarity between system and reference summaries, we further perform a human evaluation. For each task, we present a pair of system outputs in a random order, together with one human summary to five Amazon turkers. If there are multiple human summaries, we will present each human summary and the pair of system outputs to turkers. For student responses, we also present the prompt. An example Human Intelligence Task (HIT) is illustrated in Fig. FIGREF32 .
The turkers are asked to indicate their preference for system A or B based on the semantic resemblance to the human summary on a 5-Likert scale (`Strongly preferred A', `Slightly preferred A', `No preference', `Slightly preferred B', `Strongly preferred B'). They are rewarded $0.04 per task. We use two strategies to control the quality of the human evaluation. First, we require the turkers to have a HIT approval rate of 90% or above. Second, we insert some quality checkpoints by asking the turkers to compare two summaries of same text content but in different sentence orders. Turkers who did not pass these tests are filtered out. Due to budget constraints, we conduct pairwise comparisons for three systems. The total number of comparisons is 3 system-system pairs INLINEFORM0 5 turkers INLINEFORM1 (36 tasks INLINEFORM2 1 human summaries for Eng + 44 INLINEFORM3 2 for Stat2015 + 48 INLINEFORM4 2 for Stat2016 + 46 INLINEFORM5 2 for CS2016 + 3 INLINEFORM6 8 for camera + 3 INLINEFORM7 5 for movie + 3 INLINEFORM8 2 for peer + 50 INLINEFORM9 4 for DUC04) = 8,355. The number of tasks for each corpus is shown in Table TABREF14 . To elaborate as an example, for Stat2015, there are 22 lectures and 2 prompts for each lecture. Therefore, there are 44 tasks (22 INLINEFORM10 2) in total. In addition, there are 2 human summaries for each task. We selected three competitive systems (SumBasic, ILP, and ILP+MC) and therefore we have 3 system-system pairs (ILP+MC vs. ILP, ILP+MC vs. SumBasic, and ILP vs. SumBasic) for each task and each human summary. Therefore, we have 44 INLINEFORM11 2 INLINEFORM12 3=264 HITs for Stat2015. Each HIT will be done by 5 different turkers, resulting in 264 INLINEFORM13 5=1,320 comparisons. In total, 306 unique turkers were recruited and on average 27.3 of HITs were completed by one turker. The distribution of the human preference scores is shown in Fig. FIGREF34 .
We calculate the percentage of “wins” (strong or slight preference) for each system among all comparisons with its counterparts. Results are reported in the last column of Table TABREF26 . ILP+MC is preferred significantly more often than ILP on Stat2015, CS2016, and DUC04. There is no significant difference between ILP+MC and SumBasic on student response data sets. Interestingly, a system with better ROUGE scores does not necessarily mean it is more preferred by humans. For example, ILP is preferred more on all three review data sets. Regarding the inter-annotator agreement, we find 48.5% of the individual judgements agree with the majority votes. The agreement scores decomposed by data sets and system pairs are shown in Table TABREF35 . Overall, the agreement scores are pretty low, compared to an agreement score achieved by randomly clicking (45.7%). It has several possibilities. The first one is that many turkers did click randomly (39 out of 160 failed our quality checkpoints). Unfortunately, we did not check all the turkers as we inserted the checkpoints randomly. The second possibility is that comparing two system summaries is difficult for humans, and thus it has a low agreement score. Xiong and Litman xiong-litman:2014:Coling also found that it is hard to make humans agree on the choice of summary sentences. A third possibility is that turkers needed to see the raw input sentences which are not shown in a HIT.
An interesting observation is that our approach produces summaries with more sentences, as shown in Table TABREF39 . The number of words in the summaries is approximately the same for all methods for a particular corpus, which is constrained by Eq. . For camera, movie and peer reviews, the number of sentences in human summary is 10, and SumBasic and ILP+MC produce more sentences than ILP. It is hard for people to judge which system summaries is closer to a human summary when the summaries are long (216, 242, and 190 words for camera, movie, and peer reviews respectively). For inter-annotator agreement, 50.3% of judgements agree with the majority votes for student response data sets, 47.6% for reviews, and only 46.3% for news documents. We hypothesize that for these long summaries, people may prefer short system summaries, and for short summaries, people may prefer long system summaries. We leave the examination of this finding to future work.
Table TABREF40 presents example system outputs. This offers an intuitive understanding of our proposed approach.
In this section, we want to investigate the impact of the low-rank approximation process to the ILP framework. Therefore, in the following experiments, we focus on the direct comparison with the ILP and ILP+MC and leave the comparison to other baselines as future work. The proposed method achieved better summarization performance on Eng, CS2016, movie, and peer than the ILP baseline. Unfortunately, it does not work as expected on two courses for student responses (Stat2015 and Stat2016), review camera and news documents. This leaves the research question when and why the proposed method works better. In order to investigate what are key factors that impact the performance, we would like to perform additional experiments using synthesized data sets.
A variety of attributes that might impact the performance are summarized in Table TABREF41 , categorized into two types. The input attributes are extracted from the input original documents and the summaries attributes are extracted from human summaries and the input documents as well. Here are some important attributes we expect to have a big impact on the performance.
The attributes extracted from the corpora are shown in Table TABREF42 . Note, a bigram that appears more often in original documents has a better chance to be included in human summaries as indicated by INLINEFORM0 , INLINEFORM1 , INLINEFORM2 , and INLINEFORM3 . This verifies our choice to cut low-frequency bigrams.
According to the ROUGE scores, our method works better on Eng, CS2016, movie, and peer (Table TABREF26 ). If we group each attribute into two groups, corresponding to whether ILP+MC works better, we do not find significant differences among these attributes. To further understand which factors impact the performance and have more predictive power, we train a binary classification decision tree by treating the 4 working corpora as positive examples and the remaining 4 as negative examples.
According to the decision tree model, there is only one decision point in the tree: INLINEFORM0 , the ratio of bigrams in human summaries that are in the input only once. Generally, our proposed method works if INLINEFORM1 , except for camera. When INLINEFORM2 is low, it means that annotators either adopt concepts that appear multiple times or just use their own. In this case, the frequency-based weighting (i.e., INLINEFORM3 in Eq. EQREF5 ) can capture the concepts that appear multiple times. On the other hand, when INLINEFORM4 is high, it means that a big number of bigrams appeared only once in the input document. In this case, annotators have difficulty selecting a representative one due to the ambiguous choice. Therefore, we hypothesize,
To test the predictive power of this attribute, we want to test it on new data sets. Unfortunately, creating new data sets with gold-standard human summaries is expensive and time-consuming, and the new data set may not have the desired property within a certain range of INLINEFORM0 . Therefore, we propose to manipulate the ratio and create new data sets using the existing data sets without additional human annotation. INLINEFORM1 can be represented as follows, DISPLAYFORM0 
where INLINEFORM0 INLINEFORM1 
There are two different ways to control the ratio, both involving removing input sentences with certain constraints.
In this way, we obtained different levels of INLINEFORM0 by deleting sentences. The ROUGE scores on the synthesized corpus are shown in Table TABREF52 .
Our hypothesis H2 is partially valid. When increasing the ratio, ILP+MC has a relative advantage gain over ILP. For example, for Stat2015, ILP+MC is not significantly worse than ILP any more when increasing the ratio from 11.9 to 18.1. For camera, ILP+MC becomes better than ILP when increasing the ratio from 84.9 to 85.8. For Stat2016, CS2016, Eng, more improvements or significant improvements can be found for ILP+MC compared to ILP when increasing the ratio. However, for movie and peer review, ILP+MC is worse than ILP when increasing the ratio.
We have investigated a number of attributes that might impact the performance of our proposed method. Unfortunately, we do not have a conclusive answer when our method works better. However, we would like to share some thoughts about it.
First, our proposed method works better on two student responses courses (Eng and CS2016), but not the other two (Stat2015 and Stat2016). An important factor we ignored is that the students from the other two courses are not native English speakers, resulting in significantly shorter responses (4.3 INLINEFORM0 6.0 INLINEFORM1 8.8, 9.1, INLINEFORM2 , Table TABREF42 , the row with id=11). With shorter sentences, there will be less context to leverage the low-rank approximation.
Second, our proposed method works better on movie and peer reviews, but not camera reviews. As pointed out by Xiong xiong2015helpfulness, both movie reviews and peer reviews are potentially more complicated than the camera reviews, as the review content consists of both the reviewer's evaluations of the subject (e.g., a movie or paper) and the reviewer's references of the subject, where the subject itself is full of content (e.g., movie plot, papers). In contrast, such references in product reviews are usually the mentions of product components or properties, which have limited variations. This characteristic makes review summarization more challenging in these two domains.
We made the first effort to summarize student feedback using an Integer Linear Programming framework with a low-rank matrix approximation, and applied it to different types of data sets including news articles, product, and peer reviews. Our approach allows sentences to share co-occurrence statistics and alleviates sparsity issue. Our experiments showed that the proposed approach performs better against a range of baselines on the student response Eng and CS2016 on ROUGE scores, but not other courses.
ROUGE is often adopted in research papers to evaluate the quality of summarization because it is fast and is correlated well to human evaluation BIBREF72 , BIBREF82 . However, it is also criticized that ROUGE cannot thoroughly capture the semantic similarity between system and reference summaries. Different alternatives have been proposed to enhance ROUGE. For example, Graham rankel2016statistical proposed to use content-oriented features in conjunction with linguistic features. Similarly, Cohan and Goharian COHAN16.1144 proposed to use content relevance. At the same time, many researchers supplement ROUGE with a manual evaluation. This is why we conduct evaluations using both ROUGE and human evaluation in this work.
However, we found that a system with better ROUGE scores does not necessarily mean it is more preferred by humans (§ SECREF28 ). For example, ILP is preferred more on all three review data sets even if it got lower ROUGE scores than the other systems. It coincides with the fact that the ILP generated shorter summaries in terms of the number of sentences than the other two systems (Table TABREF39 ).
We also investigated a variety of attributes that might impact the performance on a range of data sets. Unfortunately, we did not have a conclusive answer when our method will work better.
In the future, we would like to conduct a large-scale intrinsic evaluation to examine whether the low-rank matrix approximation captures similar bigrams or not and want to investigate more attributes, such as new metrics for diversity. We would like to explore the opportunities by combing a vector sentence representation learned by a neural network and the ILP framework.

Figure and table captions:
Table 1. Selected summarization data sets. Publicly available data sets are marked with an asterisk (*). The statistics involve the number of summarization tasks (Tasks), average number of documents per task (Docs/task), average word count per task (WC/task), average word count per sentence (WC/sen), and average number of words in human summaries (Length).
Table 2. Example prompt, student responses, and one human summary. ‘S1’–‘S10’ are student IDs. The summary and phrase highlights are manually created by annotators. Phrases that bear the same color belong to the same issue. The superscripts of the phrase highlights are imposed by the authors to differentiate colors when
Table 3. Example movie reviews.
Table 4. Example sentences from news.
Table 5. Associated bigrams that do not appear in the sentence, but after Matrix Completion, yield a decent correlation (cell value greater than 0.9) with the corresponding sentence.
Table 6. A gold-standard data set was extracted from three student response corpora that have phrase-highlighting annotation. Statistics include: the number of bigrams, the number of pairs of similar bigrams and pairs of different bigrams, the number of tuples 〈i, j+, j−〉, and the number of 〈i+, i−, j〉. i is a bigram, j+ is a sentence with a bigram similar to i, and j− is a sentence with a bigram different from i. j is a sentence, i+ is a bigram that is similar to a bigram in j, and i− is a bigram that is different from any bigram in j.
Table 7. Hypothesise testing: whether the matrix completion (MC) helps to capture similar concepts. ∗ means p < 0.05 using a two-tailed paired t-test.
Table 8. Summarization results evaluated by ROUGE and human judges. Best results are shown in bold for each data set. ∗ indicates that the performance difference with ILP+MC is statistically significant (p < 0.05) using a two-tailed paired t-test. Underline means that ILP+MC is better than ILP.
Table 9. A comparison with official participants in DUC 2004, including 8 human annotators (1-8) and the top-5 offical participants (A-E). ‘-’ means a metric is not available.
Fig. 1. An example HIT from Stat2015, ‘System A’ is ILP+MC and ‘System B’ is SumBasic.
Fig. 2. Distribution of human preference scores
Table 10. Inter-annotator agreement measured by the percentage of individual judgements agreeing with the majority votes. ∗ means the human preference to the two systems are significantly different and the system in parenthesis is the winner. Underline means that it is lower than random choices (45.7%).
Table 11. Number of sentences in the output summaries. ∗ means it is significantly different to ILP+MC (p < 0.05) using a two-tailed paired t-test.
Table 13. Attributes description, extracted from the input and the human reference summaries.
Table 14. Attributes extracted from the input and the human reference summaries. The numbers in the row of M ∗ N are divided by 106. The description of each attribute is shown in Table 13.
Table 15. ROUGE scores on synthesized corpora. Bold scores indicate our approach ILP+MC is better than ILP. + and − mean a score is significantly better and worse respectively (p < 0.05) using a two-tailed paired t-test.
Table 16. Summarization results without removing low-frequency bigrams. That is, all bigrams are used in the matrix approximation process. Compared to Table 8, by using the cutoff technique, both ILP and ILP+MC get better.

Questions about this paper:
Do they build one model per topic or on all topics?
Do they quantitavely or qualitatively evalute the output of their low-rank approximation to verify the grouping of lexical items?

Answers:
One model per topic.
They evaluate quantitatively.