Revisiting Centrality-as-Relevance: Support Sets and Similarity as Geometric Proximity: Extended abstract

1 Introduction

A summary conveys to the end user the most relevant content of one or more information sources, in a concise and comprehensible manner. Several difficulties arise when addressing this problem, but one of utmost importance is how to assess the significant content. Usually, approaches vary in complexity if processing text or speech. While in text

formation, such as syntactic [Vanderwende et al., 2007], semantic [Tucker and Sp¨arck Jones, 2005], and discourse information [Harabagiu and Lacatusu, 2005; Uzˆeda et al., 2010], either to assess relevance or reduce the length of the output, common approaches to speech summarization try to cope with speech-related issues by using speech-specific information (for example, prosodic features [Maskey and Hirschberg, 2005], or recognition confidence scores [Zechner and Waibel, 2000]) or by improving the intelligibility of the output of an automatic speech recognition system (by using related information [Ribeiro and de Matos, 2008a]). Nonetheless, shallow text summarization approaches such as Latent Semantic Analysis [Landauer et al., 1998; Gong and Liu, 2001] and Maximal Marginal Relevance [Carbonell and Goldstein, 1998] seem to achieve performances comparable to the ones using specific speech-related features [Penn and Zhu, 2008].

∗This paper is an extended abstract of the JAIR publication [Ribeiro and de Matos, 2011].

A common family of approaches to the identification of the relevant content is the centrality family. These methods base the detection of the most salient passages on the identification of the central passages of the input source(s). Centroid-based methods build on the idea of a pseudo-passage that represents the central topic of the input source (the centroid) selecting as passages (x) to be included in the summary the ones that are close to the centroid. Pioneer work (on multi-document summarization) by Radev et al. [1999] and Radev et al. [2000] creates clusters of documents by representing each document as a tf-idf vector; the centroid of each cluster is also defined as a tf-idf vector, with the coordinates corresponding to the weighted average of the tf-idf values of the documents of the cluster; finally, sentences that contain the words of the centroids are presumably the best representatives of the topic of the cluster, thus being the best candidates to belonging to the summary.centrality(x) = similarity(x, centroid) (1)

Another approach to centrality estimation is to compare each candidate passage to every other passage (y) and select the ones with higher scores (the ones that are closer to every other passage). One simple way to do this is to represent passages as vectors using a weighting scheme like the aforementioned tf-idf ; then, passage similarity can be assessed using, for instance, the cosine, assigning to each passage a centrality score as defined in Eq. 2.

These scores are then used to create a sentence ranking: sentences with highest scores are selected to create the summary.

A major problem of this relevance paradigm is that by taking into account the entire input source in this manner, either to estimate centroids or average distances of input source passages, we may be selecting extracts that being central to the input source are, however, not the most relevant ones. In cognitive terms, the information reduction techniques in the summarization process are quite close to the discourse understanding process [Endres-Niggemeyer, 1998], which, at a certain level, works by applying rules that help uncovering the macrostructure of the discourse. One of these rules, deletion, is used to eliminate from the understanding process propositions that are not relevant to the interpretation of the subsequent ones. This means that it is common to find, in the input sources to be summarized, lateral issues or considerations that are not relevant to devise the salient information (discourse structure-based summarization is based on the relevance of nuclear text segments, [Marcu, 2000; Uzˆeda et al., 2010]), and that may affect centrality-based summarization methods by inducing inadequate centroids or decreasing the scores of more suitable sentences.

As argued by previous work [Gong and Liu, 2001; Steyvers and Griffiths, 2007], we also assume that input sources are mixtures of topics, and propose to address that aspect using the input source itself as guidance. By associating to each passage of the input source a support set consisting only of the most semantically related passages in the same input source, groups of related passages are uncovered, each one constituting a latent topic (the union of the supports sets whose intersection is not empty). In the creation of these support sets, semantic relatedness is assessed by geometric proximity. Moreover, while similar work usually explores different weighting schemes to address specific issues of the task under research [Or˘asan et al., 2004; Murray and Renals, 2007; Ribeiro and de Matos, 2008b], we explore different geometric distances as similarity measures, analyzing their performance in context (the impact of different metrics from both theoretical and empirical perspectives in a clustering setting was shown in [Aggarwal et al., 2001]). To build the summary, we select the sentences that occur in the largest number of support sets-hence, the most central sentences, without the problem that affects previous centrality-based methods.

Our method produces generic, language- and domainindependent summaries, with low computational requirements. We test our approach both in speech and text data. In the empirical evaluation of the model over text data, we used an experimental setup previously used in published work [Mihalcea and Tarau, 2005; Antiqueira et al., 2009], which enabled an informative comparison to the existing approaches. In what concerns the speech experiments, we also used a corpus collected in previous work [Ribeiro and de Matos, 2008a], as well as the published results. This allowed us to compare our model to state-of-the-art work.

2 Support Sets and Geometric Proximity

The leading concept in our model is the concept of support set: the first step of our method to assess the relevant content is to create a support set for each passage of the input source by computing the similarity between each passage and the remaining ones, selecting the closest passages to belong to the support set. The most relevant passages are the ones that occur in the largest number of support sets.

Given a segmented information source I ≜ p1, p2, ..., pN, support sets Si associated with each passage pi are defined as indicated in Eq. 3 (sim() is a similarity function, and εi is a

The most relevant segments are given by selecting the passages that satisfy Eq. 4.

A major difference from previous centrality models and the main reason to introduce the support sets is that by allowing different thresholds to each set (εi), we let centrality be influenced by the latent topics that emerge from the groups of related passages. In the degenerate case where all εi are equal, we fall into the degree centrality model proposed by Erkan and Radev [2004]. But using, for instance, a na¨ıve approach of having dynamic thresholds (εi) set by limiting the cardinality of the support sets (a kNN approach), centrality is changed because each support set has only the most semantically related passages of each passage. From a graph theory perspective, this means that the underlying representation is not undirected, and the support set can be interpreted as the passages recommended by the passage associated to the support set. This contrasts with both LexRank [Erkan and Radev, 2004] models, which are based on undirected graphs. On the other hand, the models proposed by Mihalcea and Tarau [2005] are closer to our work in the sense that they explore directed graphs, although only in a simple way (graphs can only be directed forward or backward). Nonetheless, semantic relatedness (content overlap) and centrality assessment (performed by the graph ranking algorithms HITS [Kleinberg, 1999] and PageRank [Brin and Page, 1998]) is quite different from our proposal. Although not addressing automatic summarization, considering the kNN approach to the definition of the support set size, the work of Kurland and Lee [2005; 2010] is the most similar to our model. However, Kurland and Lee base neighborhood definition on generation probabilities, while we explore geometric proximity. Nevertheless, from the perspective of our model, the kNN approach to support set definition is only a possible strategy (others can be used): our model can be seen as a generalization of both kNN and εNN approaches, since what we propose is the use of differentiated thresholds (εi) for each support set (Eq. 3).

3 Evaluation

Despite the number of approaches to summary evaluation, the most widely used metric is still ROUGE [Lin, 2004] and is the one we use in our study. We chose ROUGE not only owing to its wide adoption, but also because one of the data sets used in our evaluation has been used in published studies, allowing us to easily compare the performance of our model with other known systems. Namely, we use the ROUGE-1 score, known to correlate well with human judgment [Lin, 2004]. Moreover, we estimate confidence intervals using non-parametric bootstrap with 1000 resamplings [Mooney and Duval, 1993].

Since we are proposing a generic summarization model, we conducted experiments both in text and speech data.

3.1 Experiment 1: Text

In this section, we describe the experiments performed and analyze the corresponding results when using as input source written text.

Data

The used corpus, known as TeM´ario, consists of 100 newspaper articles in Brazilian Portuguese [Pardo and Rino, 2003]. Although our model is general and language-independent, this corpus was used in several published studies, allowing us to perform an informed comparison of our results. The articles in the corpus cover several domains, such as "world", "politics", and "foreign affairs". For each of the 100 newspaper articles, there is a reference human-produced summary. The text was tokenized and punctuation removed, maintaining sentence boundary information.

Evaluation Setup

Considering the preprocessing step we applied to the corpus and the observed differences in the published results, we found it important to evaluate centrality approaches under the same conditions. Thus, we implemented the following centrality models:

• Uniform Influx (corresponds to the non-recursive, unweighted version of the model), proposed by Kurland and Lee for re-ranking in document retrieval (we experimented with several k in graph definition, the sames used for support set cardinality in the kNN strategy, and µ-10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000);
• PageRank, proposed by both Mihalcea and Tarau and Erkan and Radev (passage similarity metrics differ and Mihalcea and Tarau also explore directed graphs);
• Degree centrality as proposed by Erkan and Radev (we experimented with several thresholds δ, ranging from 0.01 to 0.09); and,
• Baseline, in which the ranking is defined by the order of the sentences in the news article, with relevance decreasing from the begining to the end.

Concerning summary size, the number of words in the generated summaries directly depends on the number of words of the reference abstracts, which consisted in compressing the input sources to 25-30% of the original size.

Results

Overall, the best performing configuration of the proposed model is significantly better, using the directional Wilcoxon signed rank test with continuity correction, than TextRank Undirected, (W = 2584, p < 0.05), Uniform Influx (W = 2740, p < 0.05), and also Continuous LexRank (W = 2381.5, p < 0.1). 1

1 Statistical tests were computed using R [R Development Core Team, 2009].

3.2 Experiment 2: Speech

In this section, we describe the experiments performed and analyze the corresponding results when using as input source automatically transcribed speech.

Data

To evaluate our ideas in the speech processing setting, we used the same data of Ribeiro and de Matos [2008a]: the automatic transcriptions of 15 broadcast news stories in European Portuguese, part of a news program. Subject areas include "society", "politics", "sports", among others. The average word recognition error rate is 19.5% and automatic sentence segmentation attained a slot error rate (SER, commonly used to evaluate this kind of task) of 90.2%.

Evaluation Setup

Given the implemented models, in this experiment we compare the support sets relevance model to the following systems:

• An LSA baseline.
• The following graph-based methods: Uniform Influx [Kurland and Lee, 2005; 2010], Continuous LexRank and Degree centrality [Erkan and Radev, 2004], and TextRank [Mihalcea and Tarau, 2004; 2005].
• The method proposed by Ribeiro and de Matos, which explores the use of additional related information, less prone to speech-related errors (e.g. from online newspapers), to improve speech summarization (MixedSource).
• Two human summarizers (extractive) using as source the automatic speech transcriptions of the news stories (Human Extractive).

To be able to perform a good assessment of the automatic models, we conducted two experiments: in the first one, the number of sentence-like units (SUs) extracted to compose the automatic summaries was defined in accordance to the number of sentences of the reference human abstracts (which consisted in compressing the input source to about 10% of the original size); in the second experiment, the number of extracted SUs of the automatic summaries was determined by the size of the shortest corresponding human extractive summary.

Results

Overal results show that the proposed model achieved the best performance when using the abstracts size. Although not achieving the best performance in the experiment using the extracts size, there is no significant difference between the best support sets-based relevance model configuration and the ones achieved by human summarizers: applying the directional Wilcoxon signed rank test with continuity correction, the test values when using the shortest human extracts size are W = 53, p = 0.5.

The proposed model has a better performance with statistical significance than Degree (W = 53.5, p < 0.005 when using the abstracts size; W = 54, p < 0.005 when using the shortest human extracts size), TextRank Undirected (W = 92.5, p < 0.05 when using the abstracts size; W = 96, p < 0.05 when using the shortest human extracts size), and Uniform Influx (W = 60, p < 0.01 when using the abstracts size; W = 51, p < 0.06 when using the shortest human extracts size).

Further, comparing our model to more complex (not centrality-based), state-of-the-art models [Lin et al., 2010] suggests that at least similar performance is attained: the relative performance increment of our model over LexRank is of 57.4% and 39.8% (both speech experiments), whereas the relative gain of the best variant of the model proposed by Lin et al. over LexRank is of 39.6%. Note that this can only be taken as indicative, since an accurate comparison is not possible because data sets differ, Lin et al. do not explicit which variant of LexRank is used, and do not address statistical significance.

4 Conclusions

In our work, we assessed the main approaches of the centrality-as-relevance paradigm, and introduced a new centrality-based relevance model for automatic summarization. Our model uses support sets to better characterize the information sources to be summarized, leading to a better estimation of the relevant content. In fact, we assume that input sources comprehend several topics that are uncovered by associating to each passage a support set composed by the most semantically related passages. Building on the ideas of Ruge [1992], [...] the model of semantic space in which the relative position of two terms determines the semantic similarity better fits the imagination of human intuition [about] semantic similarity [...], semantic relatedness was computed by geometric proximity. We explore several metrics and analyze their impact on the proposed model as well as (to a certain extent) on the related work. Centrality (relevance) is determined by taking into account the whole input source, and not only local information, using the support sets-based representation. Moreover, although not formally analyzed, notice that the proposed model has low computational requirements.

We conducted a thorough automatic evaluation, experimenting our model both on written text and transcribed speech summarization. The obtained results suggest that the model is robust, being able to detect the most relevant content without specific information of where it should be found and performing well in the presence of noisy input, such as automatic speech transcriptions. However, it must be taken into consideration that the use of ROUGE in summary evaluation, although generalized, allowing to easily compare results and replicate experiments, is not an ideal scenario, and consequently, results should be corroborated by a perceptual evaluation. The outcome of the performed trials show that the proposed model achieves state-of-the-art performance in both text and speech summarization, even when compared to considerably more complex approaches.

Acknowledgments

This work was partially supported by national funds through FCT - Fundac¸ ˜ao para a Ciˆencia e a Tecnologia, under project PEst-OE/EEI/LA0021/2011.