2 Related work

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 (Carbonell and Goldstein Reference Carbonell and Goldstein1998), submodularity (Lin and Bilmes Reference Lin and Bilmes2010), ILP (Gillick, Favre and Hakkani-Tür Reference Gillick, Favre and Hakkani-Tür2008; Almeida and Martins Reference Almeida and Martins2013; Li et al. Reference Li, Liu, Weng and Liu2013, Reference Li, Liu, Liu, Zhao and Weng2014; Durrett, Berg-Kirkpatrick and Klein Reference Durrett, Berg-Kirkpatrick and Klein2016), minimizing reconstruction error (He et al. Reference He, Chen, Bu, Wang, Zhang, Cai and He2012), graph-based models (Erkan and Radev Reference Erkan and Radev2004; Radev et al. Reference Radev, Jing, Styś and Tam2004; Cohan and Goharian Reference Cohan and Goharian2015, Reference Cohan and Goharian2017), determinantal point processes (Kulesza and Taskar Reference Kulesza and Taskar2012), neural networks and reinforcement learning (Yasunaga et al. Reference Yasunaga, Zhang, Meelu, Pareek, Srinivasan and Radev2017; Narayan, Cohen and Lapata Reference Narayan, Cohen and Lapata2018) 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 (Rush et al. Reference Rush, Chopra and Weston2015; Nallapati et al. Reference Nallapati, Xiang and Zhou2016). 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 (See et al. Reference See, Liu and Manning2017), improve the attention mechanism (Chen et al. Reference Chen, Zhu, Ling, Wei and Jiang2016; Tan, Wan and Xiao Reference Tan, Wan and Xiao2017; Zhou et al. Reference Zhou, Yang, Wei and Zhou2017), avoid generating repetitive words (See et al. Reference See, Liu and Manning2017; Suzuki and Nagata Reference Suzuki and Nagata2017), adjust summary length (Kikuchi et al. Reference Kikuchi, Neubig, Sasano, Takamura and Okumura2016), encode long text (Celikyilmaz et al. Reference Celikyilmaz, Bosselut, He and Choi2018; Cohan et al. Reference Cohan, Dernoncourt, Kim, Bui, Kim, Chang and Goharian2018), and improve the training objective (Ranzato et al. Reference Ranzato, Chopra, Auli and Zaremba2016; Paulus et al. Reference Paulus, Xiong and Socher2017; Guo, Pasunuru and Bansal Reference Guo, Pasunuru and Bansal2018). 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 (See et al. Reference See, Liu and Manning2017) on our collection of datasets and report results in Section 6.2.

In this paper, we focus on the ILP-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 (Gillick and Favre Reference Gillick and Favre2009; Martins and Smith Reference Martins and Smith2009; Berg-Kirkpatrick et al. Reference Berg-Kirkpatrick, Gillick and Klein2011). 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 (Galanis, Lampouras and Androutsopoulos Reference Galanis, Lampouras and Androutsopoulos2012; Qian and Liu Reference Qian and Liu2013; Boudin, Mougard and Favre Reference Boudin, Mougard and Favre2015; Li et al. Reference Li, Liu and Zhao2015; Durrett et al. Reference Durrett, Berg-Kirkpatrick and Klein2016). 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 cooccurrence 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 and latent semantic analysis for summarization (Wang et al. Reference Wang, Li, Zhu and Ding2008; Lee et al. Reference Lee, Park, Ahn and Kim2009; Conroy et al. Reference Conroy, Davis, Kubina, Liu, O’Leary and Schlesinger2013; Conroy and Davis Reference Conroy and Davis2015; Wang et al. Reference Wang, Nishino, Hirao, Sudoh and Nagata2016a). In particular, Wang et al. (Reference Wang, Li, Zhu and Ding2008) use non-negative matrix factorization to group sentences into clusters; Conroy et al. (Reference Conroy, Davis, Kubina, Liu, O’Leary and Schlesinger2013) explore non-negative matrix factorization and latent semantic analysis to obtain better estimates of term weights; Wang et al. Reference Wang, Nishino, Hirao, Sudoh and Nagata2016a) 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 cooccurrence matrix embedded in the ILP framework, so that diverse expressions can share cooccurrence frequencies. Note that out-of-vocabulary expressions and domain-specific terminologies are abundant in our datasets, therefore simply calculating the lexical overlap (Rus et al. Reference Rus, Lintean, Banjade, Niraula and Stefanescu2013) or cosine similarity of word embeddings (Goldberg and Levy Reference Goldberg and Levy2014) cannot serve our goal well.

This manuscript extends our previous work on summarizing student course responses (Luo and Litman Reference Luo and Litman2015; Luo, Liu and Litman Reference Luo, Liu and LitmanLuo et al.2016a; Luo et al. Reference Luo, Liu, Liu and Litman2016b) submitted after each lecture via a mobile app named CourseMIRROR (Luo et al. Reference Luo, Fan, Menekse, Wang and Litman2015; Fan et al. Reference Fan, Luo, Menekse, Litman and Wang2015, Reference Fan, Luo, Menekse, Litman and Wang2017). 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 cooccurrence statistics; (ii) we compare the ILP-based summarization framework with the 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 platforms, more attention is being dedicated to analyzing educationally oriented language data. These studies seek to identify student leaders from Massive Open Online Courses discussion forums (Moon, Potdar and Martin Reference Moon, Potdar and Martin2014), perform sentiment analysis on student discussions (Wen, Yang and Ros Reference Wen, Yang and Rosé2014b), improve student engagement and reducing student retention (Wen, Yang and Rose Reference Wen, Yang and Rose2014a; Rose and Siemens Reference Rose and Siemens2014), and using language generation techniques to automatically generate feedback to students (Gkatzia et al. Reference Gkatzia, Hastie, Janarthanam and Lemon2013). 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.

3 ILP formulation

Let $\mathcal {D}$ be a set of documents that consist of M sentences in total. Let y _j ∈ {0, 1}, j = {1, . . ., M} indicate if a sentence j is selected (y _j = 1) or not (y _j = 0) in the summary. Similarly, let N be the number of unique concepts in $\mathcal {D}$. z _i ∈ {0, 1}, i = {1, . . ., N} indicate the appearance of concepts in the summary. Each concept i is assigned a weight of w _i, often measured by the number of sentences or documents that contain the concept. The ILP-based summarization approach (Gillick and Favre Reference Gillick and Favre2009) 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 $A \in \mathbb {R}^{N \times M}$, where A _ij = 1 indicates the ith concept appears in the jth sentence, and A _ij = 0 otherwise. In the literature, bigrams are frequently used as a surrogate for concepts (Gillick et al. Reference Gillick, Favre and Hakkani-Tür2008; Berg-Kirkpatrick et al. Reference Berg-Kirkpatrick, Gillick and Klein2011). 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. (2)), and (2) all concepts in a sentence will be selected if that sentence is selected (Eq. (3)). Finally, the selected summary sentences are allowed to contain a total of L words or less (Eq. (4)).

(1) \begin{align} \max _{\boldsymbol{y},\boldsymbol{z}} & \textstyle \quad \sum _{i=1}^{N} w_i z_i \end{align}

(2) \begin{align} s.t. & \textstyle \quad \sum _{j=1}^{M} A_{ij} \, y_j \ge z_i \end{align}

(3) \begin{align} & \quad A_{ij} \, y_j \le z_i \end{align}

(4) \begin{align} & \textstyle \quad \sum _{j=1}^{M} l_j y_j \le L \end{align}

(5) \begin{align} & \quad y_j \in \lbrace 0,1\rbrace \end{align}

(6) \begin{align} & \quad z_i \in \lbrace 0,1\rbrace \end{align}

The above ILP can be transformed to matrix representation:

(7) \begin{align} \max _{\boldsymbol{y},\boldsymbol{z}} & \quad \boldsymbol{w}^\top \boldsymbol{z} \end{align}

(8) \begin{align} s.t. & \quad \boldsymbol{A} \, \boldsymbol{y} \ge \boldsymbol{z} \end{align}

(9) \begin{align} & \quad \boldsymbol{A} \, \text{diag}(\boldsymbol{y}) \le \boldsymbol{Z} \\ \nonumber \end{align}

(10) \begin{align} & \quad \boldsymbol{\eta }^{\top }\boldsymbol{y} \le L \end{align}

(11) \begin{align} & \quad \boldsymbol{y} \in \lbrace 0,1\rbrace ^{M} \end{align}

(12) \begin{align} & \quad \boldsymbol{z} \in \lbrace 0,1\rbrace ^{N} \end{align}

We use boldface letters to represent vectors and matrices. $\boldsymbol{Z} = [\boldsymbol{z}, \ldots , \boldsymbol{z}] \in \mathbb {R}^{N \times M}$ is an auxiliary matrix created by horizontally stacking the concept vector $\boldsymbol{z} \in \mathbb {R}^N$ M times. Constraint set (Eq. (9)) specifies that a sentence is selected indicates that all concepts it carries have been selected. It corresponds to N × M constraints of the form $\textstyle A_{i,j} \, y_j \le z_i$, where i ∈ [N], j ∈ [M].

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 cooccurrence matrix $\boldsymbol{A}$, and (2) concept weight vector $\boldsymbol{w}$. Existing work focus mainly on generating better estimates of concept weights ($\boldsymbol{w}$), while we focus on improving the cooccurrence matrix $\boldsymbol{A}$.

4 Our approach

Because of the lexical diversity problem, we suspect the cooccurrence matrix $\boldsymbol{A}$ may not establish a faithful correspondence between sentences and concepts. A concept may be conveyed using multiple bigram expressions; however, the current cooccurrence 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 $\boldsymbol{A}$ is highly sparse. Only 3.7 per cent of the entries are non-zero in the student response datasets on average (Section 5). We therefore propose to impute the cooccurrence matrix by filling in missing values (i.e., matrix completion (MC)). This is accomplished by approximating the original cooccurrence 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 cooccurrence matrix can be formalized as follows:

(13) \begin{align} \max _{\boldsymbol{y},\boldsymbol{z}} & \quad \boldsymbol{w}^\top \boldsymbol{z} \end{align}

(14) \begin{align} s.t. & \quad \boldsymbol{\skew 6\hat{A}} \, \boldsymbol{y} \ge \boldsymbol{z} \end{align}

(15) \begin{align} & \quad \boldsymbol{\skew 6\hat{A}} \, \text{diag}(\boldsymbol{y}) \le \boldsymbol{Z} \end{align}

(16) \begin{align} & \quad \boldsymbol{\eta }^{\top }\boldsymbol{y} \le L \end{align}

(17) \begin{align} & \quad \boldsymbol{y} \in \lbrace 0,1\rbrace ^{M} \end{align}

(18) \begin{align} & \quad \boldsymbol{z} \in [0,1]^{N} \end{align}

The low-rank approximation process makes two notable changes to the existing ILP framework.

• • It extends the domain of A _ij from binary to a continuous scale [0,1] (Eqs. (14) and (15)), which offers a better sentence-level semantic representation.

• • The binary concept variables (z _i) are also relaxed to continuous domain [0,1] (Eq. (18)), which allows the concepts to be ‘partially’ included in the summary.

Concretely, given the cooccurrence matrix $\boldsymbol{A} \in \mathbb {R}^{N \times M}$, we aim to find a low-rank matrix $\boldsymbol{\skew 6\hat{A}} \in \mathbb {R}^{N \times M}$ whose values are close to $\boldsymbol{A}$ at the observed positions. Our objective function is

(19) \begin{align} \displaystyle \min _{\skew 6\hat{A} \in \mathbb {R}^{N \times M}} \frac{1}{2}\sum _{(i,j) \in \Omega } (A_{ij} - \skew 6\hat{A}_{ij})^2 + \lambda \left\Vert \skew 6\hat{A} \right\Vert _{*} , \end{align}

$\Vert \skew 6\hat{A}\Vert _*$

$\skew 6\hat{A}$

$\Vert \skew 6\hat{A}\Vert _* = \sum _{i=1}^r \sigma _i$

$\skew 6\hat{A}$

(20) \begin{align} \displaystyle [P_{\Omega }(\skew 6\hat{A})]_{ij} = \left\lbrace \begin{array}{lr}\skew 6\hat{A}_{ij} & (i,j) \in \Omega \\ 0 & (i,j) \notin \Omega \end{array} \right. \end{align}

(21) \begin{align} \min _{\skew 6\hat{A} \in \mathbb {R}^{N \times M}} \frac{1}{2} \Vert P_{\Omega }(A) - P_{\Omega }(\skew 6\hat{A}) \Vert _{F}^2 + \lambda \Vert \skew 6\hat{A} \Vert _{*} \end{align}

Following Mazumder, Hastie and Tibshirani (Reference Mazumder, Hastie and Tibshirani2010), we optimize Eq. (21) using the proximal gradient descent algorithm. The update rule is

(22) \begin{equation} \skew 6\hat{A}^{(k+1)} = \mbox{prox}_{\lambda \rho _k} \Big ( \skew 6\hat{A}^{(k)} + \rho _k \big ( P_{\Omega }(A) - P_{\Omega }(\skew 6\hat{A}) \big ) \Big ) \end{equation}

$\mbox{prox}_{t}(\skew 6\hat{A})$

$\mbox{prox}_{t}(\skew 6\hat{A}) = U \cdot \mbox{diag}((\sigma _i - t)_+) \cdot V^\top$

$\skew 6\hat{A} = U \mbox{diag}(\sigma _1,\ldots ,\sigma _r)V^\top$

$\skew 6\hat{A}$

Since the gradient of $\frac{1}{2} \Vert P_{\Omega }(A) - P_{\Omega }(\skew 6\hat{A}) \Vert _{F}^2$ is Lipschitz continuous with L = 1 (L is the Lipschitz continuous constant), we follow Mazumder et al. (Reference Mazumder, Hastie and Tibshirani2010) to choose fixed step size ρ_k = 1, which has a provable convergence rate of O(1/k), where k is the number of iterations.

5 Datasets

To demonstrate the generality of the proposed approach, we consider three distinct types of corpora, ranging from student response datasets from four different courses to three sets of reviews to one benchmark of news articles. The corpora are summarized in Table 1.

Table 1.

Selected summarization datasets

Publicly available datasets 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).

Student responses. Research has explored using reflection prompts/muddy cards/1-minute papers to promote and collect reflections from students (Wilson Reference Wilson1986; Mosteller Reference Mosteller1989; Harwood Reference Harwood1996). 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 (Fan et al. Reference Fan, Luo, Menekse, Litman and Wang2015; Luo et al. Reference Luo, Fan, Menekse, Wang and Litman2015). In our data, one particular type of student response is considered, named reflective feedback (Boud et al. Reference Boud, Keogh and Walker2013), which has been shown to enhance interaction between instructors and students by educational researchers (Van den Boom et al. Reference Boom, Paas, Van Merrienboer and Van Gog2004; Menekse et al. Reference Menekse, Stump, Krause and Chi2011). 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’ (Boud et al. Reference Boud, Keogh and Walker2013).

To test generality, we gathered student responses from four different courses, as shown in Table 1. The first one was collected by Menekse et al. (Reference Menekse, Stump, Krause and Chi2011) 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 (Luo and Litman Reference Luo and Litman2015), available at the link: http://www.coursemirror.com/download/dataset. The remaining three courses are collected by us using a mobile application, CourseMIRROR (Luo et al. Reference Luo, Fan, Menekse, Wang and Litman2015; Fan et al. Reference Fan, Luo, Menekse, Litman and Wang2015) 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 second and third datasets 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.Footnote ² 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 2, 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 6.1.

Product and peer reviews. The review datasets are provided by Xiong and Litman (Reference Xiong and Litman2014), consisting of three categories. The first one is a subset of product reviews from a widely used dataset in review opinion mining and sentiment analysis, contributed by Jindal and Liu (Reference Jindal and Liu2008). In particular, it randomly sampled three set of reviews from a representative product (digital camera), each with eighteen reviews from an individual product type (e.g., summarizing eighteen 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 (Cho Reference Cho2008). The average number of sentences per review set is eighty-five for camera reviews, 328 for movie reviews, and eighty for peer review; the average number of words per sentence in the camera, movie, and peer reviews are twenty three, twenty-four, and nineteen, respectively. The human summaries were collected in the form of online surveys (one survey per domain) hosted by Qualtrics. Each human summary contains ten sentences from users’ reviews. Example movie reviews are shown in Table 3.

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 printed in grayscale (y: yellow, g: green, r: red, b: blue, and m: magenta).

Table 3.

Example movie reviews

News articles. Most summarization work focuses on news documents, as driven by the Document Understanding Conferences (DUC) and Text Analysis Conferences. For comparison, we select DUC 2004Footnote ³ to evaluate our approach (henceforth DUC04), which is widely used in the literature (Lin Reference Lin2004; Hong et al. Reference Hong, Conroy, Favre, Kulesza, Lin, Nenkova, Calzolari, Choukri, Declerck, Loftsson, Maegaard, Mariani, Moreno, Odijk and Piperidis2014; Ren et al. Reference Ren, Wei, Chen, Ma and Zhou2016; Takase et al. Reference Takase, Suzuki, Okazaki, Hirao and Nagata2016; Wang et al. Reference Wang, Nishino, Hirao, Sudoh and Nagata2016b). It consists of fifty clusters of Text REtrieval Conference 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 ten documents. The task is to create a short summary (⩽665 bytes) of each cluster. Example news sentences are shown in Table 4.

Table 4.

Example sentences from news

6 Experiments

In this section, we evaluate the proposed method intrinsically in terms of whether the cooccurrence matrix after the low-rank approximation is able to capture similar concepts on student response datasets, 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 MC algorithm, we perform grid search (on a scale of [0, 5] with stepsize 0.5) to tune the hyper-parameter λ (Eq. (19)) with a leave-one-lecture-out (for student responses) or leave-one-task-out (for others) cross-validation.

6.1 Intrinsic evaluation

When examining the imputed sentence-concept cooccurrence matrix, we notice some interesting examples that indicate the effectiveness of the proposed approach, shown in Table 5.

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

We want to investigate whether the MC helps to capture similar concepts (i.e., bigrams). Recall that, if a bigram i is similar to another bigram in a sentence j, the sentence j should assign a partial score to the bigram i 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 cooccurrence matrix $\boldsymbol{A}$ measures whether a sentence includes a bigram or not. Without MC, if a bigram i does not appear in a sentence j, A _ij = 0. After MC, $\skew 6\hat{A}_{ij}$ ($\skew 6\hat{A}$ is the low-rank approximation matrix of A) becomes a continuous number ranging from 0 to 1 (negative values are truncated). Therefore, $\skew 6\hat{A}_{ij}>0$ 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 MC 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 i is similar to one of bigrams in a sentence j ⁺, but not similar to any bigram in another sentence j ⁻, then after MC, $\skew 6\hat{A}_{ij^+} > \skew 6\hat{A}_{ij^-}$.

• • 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 j has a bigram that is similar to i ⁺, but none of its bigrams is similar to i ⁻, then, after MC, $\skew 6\hat{A}_{i^+j} > \skew 6\hat{A}_{i^-j}$.

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 2). 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 i, a bigram i ⁺ that is similar to it, and a bigram i ⁻ that is different from it, we can select the bigram i, and the sentence j ⁺ that contains i ⁺, and the sentence j ⁻ that contains i ⁻. We ignore j ⁻ if it contains any other bigram that is similar to i to eliminate the compounded case that both similar and different bigrams are within one sentence. Note, if there are multiple sentences containing i ⁺, we consider each of them. In this way, we construct a triple 〈i, j ⁺, j ⁻〉, and test whether $\skew 6\hat{A}_{ij^+} > \skew 6\hat{A}_{ij^-}$. To test H1.b, for each pair of similar bigrams 〈i, i ⁺〉 and different bigrams 〈i, i ⁻〉, we select the sentence j that contains i so that we construct a triple 〈i ⁺, i ⁻, j〉, and test whether $\skew 6\hat{A}_{i^+j} > \skew 6\hat{A}_{i^-j}$. We also filtered out j that contains similar bigram(s) to i ⁻ to remove the compounded effect. In this way, we collected a gold-standard dataset to test the two hypotheses above as shown in Table 6.

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.

The results are shown in Table 7. $\skew 6\hat{A}_{ij^+} > \skew 6\hat{A}_{ij^-}$ 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 $\skew 6\hat{A}_{i^+j} > \skew 6\hat{A}_{i^-j}$ significantly on Stat2016 and there is no significant difference between $\skew 6\hat{A}_{i^+j}$ and $\skew 6\hat{A}_{i^-j}$ on the other two courses. First, the gold-standard dataset is still small in the sense that only a limited portion of bigrams in the entire dataset 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 2, 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 MC 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 7 is associated with ‘hard to.’

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.

6.2 Extrinsic evaluation

Our proposed approach is compared against a range of baselines. They are (1) MEAD (Radev et al. Reference Radev, Jing, Styś and Tam2004), a centroid-based summarization system that scores sentences based on length, centroid, and position; (2) LexRank (Erkan and Radev Reference Erkan and Radev2004), a graph-based summarization approach based on eigenvector centrality; (3) SumBasic (Vanderwende et al. Reference Vanderwende, Suzuki, Brockett and Nenkova2007), 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) (See et al. Reference See, Liu and Manning2017), a state-of-the-art neural encoder–decoder approach for abstractive summarization. The system was trained on the CNN/Daily Mail datasets (Hermann et al. Reference Hermann, Kocisky, Grefenstette, Espeholt, Kay, Suleyman and Blunsom2015; Nallapati et al. Reference Nallapati, Xiang and Zhou2016). (5) ILP (Berg-Kirkpatrick et al. Reference Berg-Kirkpatrick, Gillick and Klein2011), a baseline ILP framework without MC.

The PGN (See et al. Reference See, Liu and Manning2017) 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 PGN 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 removedFootnote ⁴) and term frequency as concept weights. We leverage the cooccurrence statistics both within and across the entire corpus.Footnote ⁵ 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 8, we present summarization results evaluated by ROUGE (Lin Reference Lin2004) and human judges.Footnote ⁶

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.

To compare with the official participants in DUC 2004 (Paul and James Reference Paul and James2004), we selected the top-five systems submitted in the competition (ranked by R-1), together with the eight human annotators. The results are presented in Table 9.

Table 9.

A comparison with official participants in DUC 2004, including eight human annotators (1–8) and the top-five offical participants (A–E)

‘–’ means a metric is not available.

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 datasets. 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 9) and even has the best R-2. PGN is the worst, which is not surprising since it is trained on a different dataset, which may not generalize to our datasets. 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 datasets. It is perhaps not surprising to some extent. The no free lunch theorem for machine learning (Wolpert Reference Wolpert1996) states that, averaged overall possible data-generating distributions, every classification 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 (Goodfellow et al. Reference Goodfellow, Bengio and Courville2016).

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 Figure 1.

Fig. 1.

An example HIT from Stat2015, ‘System A’ is ILP+MC and ‘System B’ is SumBasic.

The turkers are asked to indicate their preference for system A or B based on the semantic resemblance to the human summary on a five-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 ninety per cent 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 × 5 turkers × (36 tasks × 1 human summaries for Eng + 44×2 for Stat2015 + 48×2 for Stat2016 + 46×2 for CS2016 + 3×8 for camera + 3×5 for movie + 3×2 for peer + 50 × 4 for DUC04) = 8,355. The number of tasks for each corpus is shown in Table 1. To elaborate as an example, for Stat2015, there are twenty-two lectures lectures and two prompts for each lecture. Therefore, there are forty-four tasks (22×2) in total. In addition, there are two human summaries for each task. We selected three competitive systems (SumBasic, ILP, and ILP+MC) and therefore we have three 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× 2 ×3=264 HITs for Stat2015. Each HIT will be done by five different turkers, resulting in 264×5=1,320 comparisons. In total, 306 unique turkers were recruitedFootnote ⁷ and on average 27.3 of HITs were completed by one turker. The distribution of the human preference scores is shown in Figure 2.

Fig. 2.

Distribution of human preference scores.

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 8.Footnote ⁸ILP+MC is preferred significantlyFootnote ⁹ more often than ILP on Stat2015, CS2016, and DUC04. There is no significant difference between ILP+MC and SumBasic on student response datasets. 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 datasets. Regarding the inter-annotator agreement, we find 48.5 per cent of the individual judgments agree with the majority votes. The agreement scores decomposed by datasets and system pairs are shown in Table 10. Overall, the agreement scores are pretty low, compared to an agreement score achieved by randomly clicking (45.7 per cent).Footnote ¹⁰ 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 (Reference Xiong and Litman2014) 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.

Table 10.

Inter-annotator agreement measured by the percentage of individual judgments 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%).

An interesting observation is that our approach produces summaries with more sentences, as shown in Table 11. The number of words in the summaries is approximately the same for all methods for a particular corpus, which is constrained by Eq. (16). 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 per cent of judgments agree with the majority votes for student response data sets, 47.6 per cent for reviews, and only 46.3 per cent 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 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 12 presents example system outputs. This offers an intuitive understanding of our proposed approach.

Table 12.

Example reference and system summaries

7 Analysis of influential factors

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 datasets.

A variety of attributes that might impact the performance are summarized in Table 13, 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.

• • M*N is the size of the summarization task, represented by the size of the co-occurrence matrix A, as shown in Eqs. (2) and (3). Generally, the bigger the matrix, the more difficult it is to find an optimal solution of low-rank approximation as there are more parameters. Note, A is an N × M matrix, where N is the number of unique concepts, and M is the number of sentences.

• • For the sparsity ratio s, if the matrix is too sparse, there will not be enough information within A to have a good estimate of the completed matrix after imputation. In contrast, if the matrix is not sparse at all (e.g., all authors use the same term for a concept), there will be no benefit to performing low-rank approximation.

• • The Shannon’s diversity index H measures the degree of bigram diversity. The more diverse the bigram distribution, the smaller the corresponding Shannon entropy.

• • The abstraction ratios α_{b = 0}, α_{b = 1}, α_{b > 1} capture in what degree annotators use words from the input or use their own.

• • β_{b = 1}, β_{b = 2}, β_{b = 3}, β_{b = 4}, β_{b > 1} intend to capture how humans create the summaries in terms of whether more frequent bigrams are more likely to be selected by humans.

Table 13.

Attributes description, extracted from the input and the human reference summaries

The attributes extracted from the corpora are shown in Table 14. Note, a bigram that appears more often in original documents has a better chance to be included in human summaries as indicated by β_{b = 1}, β_{b = 2}, β_{b = 3}, and β_{b = 4}. This verifies our choice to cut low-frequency bigrams.

Table 14.

Attributes extracted from the input and the human reference summaries

The numbers in the row of M*N are divided by 10⁶. The description of each attribute is shown in Table 13.

According to the ROUGE scores, our method works better on Eng, CS2016, movie, and peer (Table 8). 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 four working corpora as positive examples and the remaining four as negative examples.

According to the decision tree model, there is only one decision point in the tree: α_{b = 1}, the ratio of bigrams in human summaries that are in the input only once. Generally, our proposed method works if α_{b = 1} > 23.2 per cent, except for camera. When α_{b = 1} 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., w _i in Eq. (1)) can capture the concepts that appear multiple times. On the other hand, when α_{b = 1} 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

• • H2: The ILP framework benefits more from low-rank approximation when α_{b = 1} is higher.

To test the predictive power of this attribute, we want to test it on new datasets. Unfortunately, creating new datasets with gold-standard human summaries is expensive and time-consuming, and the new dataset may not have the desired property within a certain range of α_{b = 1}. Therefore, we propose to manipulate the ratio and create new datasets using the existing datasets without additional human annotation. α_{b = 1} can be represented as follows:

(23) \begin{align} \displaystyle \alpha _{b=1} = \frac{\sum _i \sigma _i \cdot \phi _{w_i=1}}{\sum _i \sigma _i} \end{align}

\begin{equation*} \sigma _i = \left\lbrace \begin{array}{@{}l@{\quad }l@{}}1 & \text{if bigram $i$ appears in the human summary}\\ 0 & else \end{array}\right. \end{equation*}

\begin{equation*} \phi _{w_i=1} = \left\lbrace \begin{array}{@{}l@{\quad }l@{}}1 & \text{if } w_i=1, w_i\text{ is the weight of the bigram }\ i\\ 0 & else \end{array}\right. \end{equation*}

There are two different ways to control the ratio, both involving removing input sentences with certain constraints.

• • To increase this ratio, we remove sentences with bigrams that appear multiple times so that there will be more bigrams that appear once (i.e., increase $\sigma _i \cdot \phi _{w_i=1}$) and thus increase the numerator. For example, if a bigram in a human summary appears in two input sentences (e.g., S1 and S2), we can randomly remove one of them (either S1 or S2) to make the bigram appear only once in the input. Note that we keep sentences that have bigrams appearing multiple times and a bigram appearing only once as well, so that we guarantee that all the input sentences with a unique bigram in human summaries are kept and removing other sentences can only increase the ratio.

• • To decrease this ratio, we remove the sentences with bigrams that appear only once in order to decrease the numerator. This will reduce the bigram frequency w _i from 1 to 0. Similarly, we keep sentences that contain bigrams appearing multiple times so that removing sentences will not increase the ratio.

In this way, we obtained different levels of α_{b = 1} by deleting sentences. The ROUGE scores on the synthesized corpus are shown in Table 15.

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.

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 < 6.0 < 8.8, 9.1, p < 0.01, Table 14, 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 (Reference Xiong2015), 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 and 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.