2
$\begingroup$

I am trying to understand how TextRank document summary algorithm works.

A few articles that I've read so far introduce text rank as a modification of page rank (e.g. article in wikipedia). However, they don't clearly explain all nuances.

Therefore, I have a few questions:

  1. When modelling each uni-gram as a vertex, would two identical words in different places be represented as same or different vertices? For example, if the text is:

    Usain Bolt is the fastest runner in the world.
    

    would there be two vertices for word the, or just one?

  2. After calculating the limiting distribution (i.e rank) of every vertex, how do we merge several uni-grams with high rank into one? If the top 3 uni-grams are all far away from each other in the text, what would get merged with what?

  3. Words such as the or is will always have a high rank, simply because they frequently occur in the text. However, they are not key phrases. How to distinguish them from real key words?

  4. How is TextRank better than simply counting each keyword appearing in the text, and merging all words that have the highest count? (Assume that problem 3 is solved separately)

$\endgroup$
1
$\begingroup$

The first question:

When modelling each uni-gram as a vertex, would two identical words in different places be represented as same or different vertices?

It will be represented as the same(just one). (In your example "the" will usually be dropped since it's a stop word). For illustration, please refer to this example from this paper. It is by treating them as the same to draw the edges between it and other different words.

enter image description here

For the text:

Compatibility of systems of linear constraints over the set of natural numbers. Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types systems and systems of mixed types.

The second question:

After calculating the limiting distribution (i.e rank) of every vertex, how do we merge several uni-grams with high rank into one? If the top 3 uni-grams are all far away from each other in the text, what would get merged with what?

Only when they are connected to each other in the original text we should merge them. For instance in the aforementioned example, "linear" and "system" are concatenate in the text, so "linear system" will be treated as a phrase, provided only adj. and n. are considered in this context.

Question 3:

Words such as the or is will always have a high rank, simply because they frequently occur in the text. However, they are not key phrases. How to distinguish them from real key words?

Words such as "the" and "a" or "of" will be deleted. Refer to here. However open class words, such as nouns, adjectives and etc. are important.

The last question:

How is TextRank better than simply counting each keyword appearing in the text, and merging all words that have the highest count? (Assume that problem 3 is solved separately).

By the word occurrence method:

word_list = "Compatibility of systems of linear constraints over the set of natural numbers. Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types systems and systems of mixed types." 
word_list = word_list.lower()
tokenizer = RegexpTokenizer(r'\w+')
tokens = tokenizer.tokenize(word_list)
word_list = [w for w in tokens if not w in stopwords.words('english')]
dic = {i: b.count(i) for i in word_list}
sorted_words = sorted(dic.items(), key=lambda x: x[1], reverse=True)

We can get the following result(a part):

('systems', 4), ('set', 3), ('solutions', 3), ('minimal', 3), ('types', 3), ('linear', 2), ('algorithms', 2), ('constructing', 1), ('numbers.', 1), ('considered.', 1), ('equations,', 1), ('given.', 1), ('inequations,', 1), ('solving', 1), ('system', 1), ('compatibility', 1), ('strict', 1), ('criteria', 1), ('supporting', 1),

It's much bad than the result by the Textrank

linear constraints; linear diophantine equations; natural numbers; nonstrict inequations; strict inequations; upper bounds

Let alone that by human:

linear constraints; linear diophantine equations; minimal generating sets; non−strict inequations; set of natural numbers; strict inequations; upper bounds

As we can see we lost the information given by the context, especially voting or recommendation by the core concept of the Pagerank algorithm. Every connection in a window is a voting for both of the words(in the undirected graph or Markov model).

$\endgroup$
0
$\begingroup$

lerner already provided pretty comprehensive answer, but one technique he didn't mention that is useful in practice is using TF-IDF model.

Words such as the or is will always have a high rank, simply because they frequently occur in the text. However, they are not key phrases. How to distinguish them from real key words?

lerner already mentioned stopword filtering. In addition to that method modern implementations also use information from TF-IDF model. IDFs capture frequencies of words across documents. They naturally scale common words scores, thus making them count less in comparisons. Also they can be used for stopwords removal by thresholding (you can just drop words that occur in more than $n$ sentences).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.