# Presentation: 150927

## A Clustering Based Approach to CreatingMulti-Document Summaries

- Endre Boros, Paul B. Kantor, David J. Neu
- Rutgers University

## Assumptions:

- Each document collection is considered to consists of a small finite number of “themes”
- A “good” summary should cover as many of these themes as length constraints permit
- Themes can be ordered by how “important” it is that they be covered in the summary
- Each complete sentence in a collection document, is considered to cover at most one “theme”

- Approach:

- Summaries will consist of complete sentences selected from collection documents

**Notes:**
Our approach is based on the following notions ...
Approach: utilize these assumptions, sentence extraction

## Manually Selected “Themes” from d01: Clarence Thomas

- -nominated to the Supreme Court on July 1, 1991
- -conservative
- -republican
- -controversial civil rights record
- -second African-American to be appointed
- -nominated by President Bush
- -position on affirmative action
- -position on abortion
- -Roman Catholic
- -Anita Hill accused him of sexual harassment
- -contentious confirmation process
- -confirmed on October 16, 1991

**Notes:**
This is what we had HOPED “themes” would look like

## Model

- Parse the _document collection_ into a _set of sentences_.
- Utilize classic (unsupervised) _cluster analysis_ techniques to partition the _set of sentences_ into _theme clusters_, i.e. disjoint subsets of sentences, such that each sentence in a cluster is “about” the same theme.
- Compute the _cluster centers_ as (μ1, ..., μn) , where μi is  the average frequency of the itih term.
- For each cluster, compute the _distance _from each _sentence_ *s*, to its _cluster center_ *c*, as *1-cos(s,c)*.
- Consider the _document collection center_ (modeling what the collection is “about”) to be the term frequency vector of the entire collection.
- Compute the _distance_ from each _cluster center_ *c*, to the _document collection center_ *d* as *1-cos(d,c)*.

**Notes:**
Using vector space representations
Home grown sentence boundary algorithm: end-of-sentence punctuation, period, exclamation point, question mark, created a list of abbreviations.  Documents were parsed into sentences
using the end of sentence punctuation (i.e. ".", "!", "?") as markers except
in cases in which the "." was immediately preceded by an abbreviation.
An abbreviation list was constructed by manually inspecting all strings
in the trial set which began with a capital letter and were immediately
followed by a ".". Only sentences with between ve and thirty words
are used. The rational was that sentences with more than thirty word
probably would not get be used by the summary generation procedure
due to length limitations and that sentences with less than ve words
probably do not carry much information.

## Model

- = sentences

**Notes:**
1. Parse the document collection into a set of sentences.

## Model

- Parse the _document collection_ into a _set of sentences_.
- Utilize classic (unsupervised, seeded) _cluster analysis_ techniques to partition the _set of sentences_ into _theme clusters_, i.e. disjoint subsets of sentences, such that each sentence in a cluster is “about” the same theme.
- Compute the _cluster centers_ as (μ1, ..., μn) , where μi is  the average frequency of the itih term.
- For each cluster, compute the _distance _from each _sentence_ *s*, to its _cluster center_ *c*, as *1-cos(s,c)*.
- Consider the _document collection center_ (modeling what the collection is “about”) to be the term frequency vector of the entire collection.
- Compute the _distance_ from each _cluster center_ *c*, to the _document collection center_ *d* as *1-cos(d,c)*.

**Notes:**
K-means with k=30

## Model

- Theme 1

- Theme 2

- Theme k

- = sentences

- Theme 3

**Notes:**
K-means with k=30

## Model

- Parse the _document collection_ into a _set of sentences_.
- Utilize classic (unsupervised) _cluster analysis_ techniques to partition the _set of sentences_ into _theme clusters_, i.e. disjoint subsets of sentences, such that each sentence in a cluster is “about” the same theme.
- Compute the _cluster centers_ as (μ1, ..., μn) , where μi is  the average frequency of the ith term.
- For each cluster, compute the _distance _from each _sentence_ *s*, to its _cluster center_ *c*, as *1-cos(s,c)*.
- Consider the _document collection center_ (modeling what the collection is “about”) to be the term frequency vector of the entire collection.
- Compute the _distance_ from each _cluster center_ *c*, to the _document collection center_ *d* as *1-cos(d,c)*.

## Model

- Theme 1

- Theme 2

- Theme k

- = sentences

- = theme cluster centers

- Theme 3

**Notes:**
Wanted cluster center to be as in the Clarence Thomas manually extracted themes

## Model

- Parse the _document collection_ into a _set of sentences_.
- Utilize classic (unsupervised) _cluster analysis_ techniques to partition the _set of sentences_ into _theme clusters_, i.e. disjoint subsets of sentences, such that each sentence in a cluster is “about” the same theme.
- Compute the _cluster centers_ as (μ1, ..., μn) , where μi is  the average frequency of the ith term.
- For each cluster, compute the _distance _from each _sentence_ *s*, to its _cluster center_ *c*, as *1-cos(s,c)*.
- Consider the _document collection center_ (modeling what the collection is “about”) to be the term frequency vector of the entire collection.
- Compute the _distance_ from each _cluster center_ *c*, to the _document collection center_ *d* as *1-cos(d,c)*.

**Notes:**
1 minus the cosine similarity

## Model

- Theme 1

- Theme 2

- Theme k

- = sentences

- = theme cluster centers

- Theme 3

## Model

- Parse the _document collection_ into a _set of sentences_.
- Utilize classic (unsupervised) _cluster analysis_ techniques to partition the _set of sentences_ into _theme clusters_, i.e. disjoint subsets of sentences, such that each sentence in a cluster is “about” the same theme.
- Compute the _cluster centers_ as (μ1, ..., μn) , where μi is  the average frequency of the ith term.
- For each cluster, compute the _distance _from each _sentence_ *s*, to its _cluster center_ *c*, as *1-cos(s,c)*.
- Consider the _document collection center_ (modeling what the _entire_ collection is “about”) to be the term frequency vector of the entire collection.
- Compute the _distance_ from each _cluster center_ *c*, to the _document collection center_ *d* as *1-cos(d,c)*.

**Notes:**
Document collection center – a single model of what the collection is “about”
So we can rank the theme clusters by how “important” it is that they appear in a summary

## Collection Center

| 1. thomas | 11. nomination | 21. bush |
| --- | --- | --- |
| 2. judge | 12. rights | 22. people |
| 3. court | 13. marshall | 23. man |
| 4. senate | 14. law | 24. charges |
| 5. supreme | 15. confirmation | 25. conservative |
| 6. clarence | 16. case | 26. life |
| 7. justice | 17. thomas's | 27. harassment |
| 8. hearings | 18. president | 28. washington |
| 9. black | 19. nominee | 29. vote |
| 10. committee | 20. views | 30. sexual |

## Model

- Theme 1

- Theme 2

- Theme k

- Collection
- Center

- = sentences

- = theme cluster centers

- Theme 3

## Model

- Parse the _document collection_ into a _set of sentences_.
- Utilize classic (unsupervised) _cluster analysis_ techniques to partition the _set of sentences_ into _theme clusters_, i.e. disjoint subsets of sentences, such that each sentence in a cluster is “about” the same theme.
- Compute the _cluster centers_ as (μ1, ..., μn) , where μi is  the average frequency of the ith term.
- For each cluster, compute the _distance _from each _sentence_ *s*, to its _cluster center_ *c*, as *1-cos(s,c)*.
- Consider the _document collection center_ (modeling what the _entire_ collection is “about”) to be the term frequency vector of the entire collection.
- Compute the _distance_ from each _cluster center_ *c*, to the _document collection center_ *d* as *1-cos(d,c)*.

## Model

- Theme 1

- Theme 2

- Theme k

- Collection
- Center

- = sentences

- = theme cluster centers

- Theme 3

## Sentences within each cluster, are ranked in increasing order of their distance from the cluster center.  Represents similarity of sentences and the theme which the cluster is “about”.
Clusters are ordered by their distance to the document collection.  Represent how “important” it is for a theme to be included in the summary.
One sentence is repeatedly selected from each cluster and added to the summary, until the length constraint is violated.

- Clusters are ordered by their distance to the document collection.  Represent how “important” it is for a theme to be included in the summary.
- One sentence is repeatedly selected from each cluster and added to the summary, until the length constraint is violated.

- Summary Creation

**Notes:**
Given this model, how do we proceed to a model for creating summaries

## Summary Creation

- Theme 1

- Sentence 3
- Sentence 25
- Sentence 7
- Sentence 16

- Theme 2

- Sentence 45
- Sentence 2
- Sentence 78
- Sentence 11
- Sentence 18
- Sentence 95

- Theme 3

- Sentence 9
- Sentence 21

- Theme k

- Sentence 32
- Sentence 99
- Sentence 5

## Sentences within each cluster, are ranked in increasing order of their distance from the cluster center.  Represents similarity of sentences and the theme which the cluster is “about”.
Clusters are ordered by their distance to the document collection center.  Represent how “important” it is for a theme to be included in the summary.
One sentence is repeatedly selected from each cluster and added to the summary, until the length constraint is violated.

- Clusters are ordered by their distance to the document collection center.  Represent how “important” it is for a theme to be included in the summary.
- One sentence is repeatedly selected from each cluster and added to the summary, until the length constraint is violated.

- Summary Creation

## Summary Creation

- Sentence 3
- Sentence 25
- Sentence 7
- Sentence 16

- Theme 2

- Sentence 45
- Sentence 2
- Sentence 78
- Sentence 11
- Sentence 18
- Sentence 95

- Theme 3

- Sentence 9
- Sentence 21

- Theme k

- Sentence 32
- Sentence 99
- Sentence 5

- Summary Creation

## Sentences within each cluster, are ranked in increasing order of their distance from the cluster center.  Represents similarity of sentences and the theme which the cluster is “about”.
Clusters are ordered by their distance to the document collection center.  Represent how “important” it is for a theme to be included in the summary.
Using a “round-robin” approach, one sentence is repeatedly selected from each cluster and added to the summary, until the length constraint is violated.

- Clusters are ordered by their distance to the document collection center.  Represent how “important” it is for a theme to be included in the summary.
- Using a “round-robin” approach, one sentence is repeatedly selected from each cluster and added to the summary, until the length constraint is violated.

- Summary Creation

## Summary Creation

- Sentence 3
- Sentence 25
- Sentence 7
- Sentence 16

- Theme 2

- Sentence 45
- Sentence 2
- Sentence 78
- Sentence 11
- Sentence 18
- Sentence 95

- Theme 3

- Sentence 9
- Sentence 21

- Theme k

- Sentence 32
- Sentence 99
- Sentence 5

- Summary Creation

- Sentence 45,
- Sentence 32,
- Sentence 3,
- Sentence 9,
- Sentence 2
- .
- .
- .

- Summary

## Details and Refinements

- Terms must appear in more than 2% of sentences to be used in clustering.
- Only sentences having between 5 and 30 words are used.

## 20-20 Hindsight

- Clustering of sentences did not yield intuitively encouraging results. Why?
- Need to do a better job of “noise” removal, i.e. feature selection (e.g. in the collection center) only the most important terms should have been used. Might help in ordering the clusters.

## Example 50 Word Summary

- If the effort against Judge Thomas fizzles and the organizations are seen to have grossly overreached, their credibility will be badly damaged in any future battles. Can Clarence Thomas be confirmed to the Supreme Court? Studied for priesthood; Thomas attended Roman Catholic schools through college and studied for the priesthood.

## Evaluation

- The data for each topic/system/size (T/S/S) combination end with a set of triples (*x,y,z) * of which *y* seems to represent the degree to which the unit, for this triple, “covers” the model concept to which it is most closely aligned.
- For each T/S/S we compute the average *<y> * over all triples

## Evaluation (2)

- For each T/S/S we then sort the average value, and assign to each T/S/S the rank of that average (1=highest value).
- The performance of a system, for a given size of summary, is the average, over T, of the rank.  Call this <r>/S/S.
- Our average rank is about 23 or so.  Discouraging

## Evaluation (3)

- There are some difficulties:
- the number of cases for each -/S/S is not the same for all topics
- This can be used to establish confidence levels for differences between systems
- it is a Friedman type test.

## Histogram of the ranks we achieved (Multi-doc): U all sizes together

-    3  ******
-    4  *
-    5  *****
-    6  ***
-    7  ******
-    8  *******
-    9  *********
-   10  *******
-   11  *****
-   12  *****
-   13  ********
-   14  *******
-   15  **********
-   16  ******************
-   17  *******************

## Thank you!