Create a New Summarizer for the Yioop Search Engine

As stated in the aim, my first objective was to find a good summarizer to implement. I felt it had to be something completely different compared to the existing summarizers in the Yioop search engine. The existing summarizers are covered in Deliverable 1. I came across a worthy algorithm known as Luhn's algorithm. Dr. Pollett did not feel the same way, so I searched further. I eventually stumbled upon a graph based algorithm that looked promising. This time my summarizer suggestion passed Dr. Pollett's evaluation and I proceeded to dig into it.
Furthermore, in order to prove I understood the algorithm, Dr. Pollett had me create a short PowerPoint presentation summarizing the algorithm. Once the presentation was complete, Dr. Pollett and I discussed the presentation thoroughly. After the discussion, we both felt we had a good handle on the algorithm and what it would take to implement it. For our own sake we also calculated the order in which the algorithm ran. "The algorithm is O(n²) not counting the outer while loop / for loop" (Dr. Pollett). Now for the details on the Graph Based Ranking Summarizer I implemented. I will first describe the algorithm as it is stated in the paper Multi-Document Summarization Using Graph-Based Iterative Ranking Algorithms and Information Theoretical Distortion Measures to give more detail than what is in the 8 slide presentation. Next I will detail the changes made in our implementation and what I had to do to add the algorithm to the Yioop search engine plus I will showcase the ROUGE results of the new summarizer.

The Graph Based Ranking Summarizer uses and extraction based model. It constructs a weighted graph out of the text where the sentences are the nodes. So how does it work you ask? First the file has to be read entirely into memory. Next the non-ASCII characters are removed. This is because non-ASCII characters can make summarizing more difficult since it would need stemmers for many different languages. This lends me to believe the algorithm is only to target English or English-like languages. The next module replaces all new lines with spaces to help when it is time to split up the text into sentences.

Next the sentences are separated using the following regular expression; (?<!\w\.\w.)(?<![A-Z][a-z]\.)(?<=\.|\?). You should take note that it does not handle the exclamation point. After the sentences are split, they remove the stop words. "Such words are usually not relevant to the semantics of the sentences" (Samei2014). Furthermore, the punctuation is removed from the sentences. Now a porter stemmer is used to stem the remaining words. Stemmers were also covered in a previous deliverable; Deliverable 2. The last trivial part is the frequency computation. A vector is created that holds each word and the count of how many times the word occurs in the text.

Moreover, the next phases are the most important. This is where the algorithm creates the weighted graph called the adjacency matrix. The calculation to generate the values is known as the distortion measure (DM). In short, each value or DM is the sum of the frequencies of all the words in common divided by the sum of words that are not in common. Here is the algorithm as stated in (Semei2014) below along with the an image of what the graph may look like:

Check each word in sentence1 to see if it exists in sentence2. If the word X of sentence1 does not exist in sentence2, square the score of word X and add to the sum and increase the number of not-common words by one. In case the word X is common between sentence1 and sentence2, calculate its frequency in sentence2 and subtract it from the score of word X, then square and add to sum. Then check the sentence2 to find its not-common words with sentence1, in case the word Y is not in sentence1, square the score of word Y and add to sum and increase the number of not-common words by one. At the end, calculate the distortion between sentence1 and sentence2 by dividing sum by the number of not-common words.

Those four steps may sound confusing and they are. The last step after computing the adjacency matrix is to extract the summaries. This is done by leveraging the page rank algorithm created by Larry Page and Sergey Brin, the founders of Google. It was intended to be sued for ranking web pages but it appears to have use here too. Basically it computes an initial vector of equal probabilities. For example, if there are 5 sentences, the initial vector would have 5 items all set to 1/5. The adjacency matrix is multiplied by the probability vector to generate a new probability vector. Then the squared difference of the old probability vector and the new probability vector are compared. The process is repeated until the squared difference is below some threshold. This algorithm deviates from the original page rank algorithm. It does not use the squared difference method. They only iterate 10 times. "As few as 10 iterations produced a good approximate ordering, competitive with the exact ordering produced by the traditional convergence measure" (Langville2006). When the 10 iterations are complete, the probability vector is returned and is used to generate the summary. Each sentences is added to the summary in order of highest probability to lowest probability until the allowed summary length has been reached.

As I did in Deliverable 1, they also used ROUGE to evaluate how well or how not so well their summarizer performs. The ROUGE-N test was used with N set to 1. Two tests were ran against the Document Understanding Conference (DUC) 2002 data set. The DUC 2002 data set contains "organized yearly evaluation of document summarization" (Samei). The first test had the summarizer's settings to their maximum values. The resulting value was 0.3224. The second test was run with the settings set to average settings. The result was 0.3547. The top 6 benchmark values in ROUGE range from 0.2992 - 0.3588. If the results are accurate as claimed in the paper, the Graph Based Ranking summarizer is one that should be evaluated when choosing a summarization algorithm.

A tremendous amount of information was just covered. I hope you are still with me. We saw that the algorithm has a lot of moving parts which is what made it was fun to dissect. Now let us talk about our implementation. The first thing we changed was filtering non-ASCII characters. Dr. Pollett and I felt, since the Yioop search engine has many locales (with stemmers and stop word removers including ones like Dutch that include non-ASCII characters), we can support them. The other deviation is how we chose to weigh the sentences. It was unclear how the sentences were weighted so we decided to normalize the frequency values and not weight them further.

Once the code was written for the Graph Based Ranking summarizer (GBS), it had to be integrated into the Yioop search engine. Thanks to a tip by Dr. Pollett of how to search the code base, I was able to find all of the places I needed to inject code to get the summarizer integrated. First I ran "php code_tool.php search .. centroid" from the Yioop repository bin directory. It found all of the places the word centroid was located in the code base that may or may not have applied to my objective. As I took a look at each line, I either added the appropriate code or left it alone. I ended up modifying fetcher.php, crawl_component.php, crawl_constants.php, graph_based_summarizer.php, phrase_parser.php, html_processor.php, page_processor.php, text_processor.php and the English locale configure.ini file. When I tried my new summarizer for the first time I had errors all over the screen. I started adding echo lines throughout the code, spending hours tweaking the code until the errors were gone. In order to find some of the hidden hooks, I walked the stack trace backwards. There were some places that could not be found by text searches because they were loaded dynamically. Once I was confident the code was ready, I submitted an issue and a patch to the Mantis BT repository manager (Dr. Pollett) for review. Hopefully this summarizer will make it into the Yioop search engine also.

Results

In conclusion the Graph Based Summarizer work was some of the most interesting work I have done in a while. The results I got were just below the results stated in the paper. However the results were dramatically lower than the BS and CBS already in the Yioop search engine. It is probably because of the way we chose to weight each sentence. The highest result here is not anywhere near the lowest on either of the other summarizers. For example, in the ROUGE-1 test the CBS 95%-conf int value was 0.76663, the BS value was 0.80587, and the GBS value was 0.32603. It seems that there is more work to do here.

• configure.ini
• crawl_component.php
• crawl_constants.php
• fetcher.php
• graph_based_summarizer.php
• html_processor.php
• page_processor.php
• phrase_parser.php
• text_processor.php

References

[Samei2014] Multi-Document Summarization Using Graph-Based Iterative Ranking Algorithms and Information Theoretical Distortion Measures. Borhan Samei, Marzieh Eshtiagh, Fazel Keshtkar and Sattar Hashemi, The Florida AI Research Society. 2014.
[Agrawal2014] A Graph Based Ranking Strategy for Automated Text Summarization. Nitin Agrawal, Shikhar Sharma, Prashant Sinha, Shobha Bagai, DU Journal of Undergraduate Research and Innovation. 2014.
[Langvielle2006] Google's PageRank and Beyond: The Science of Search Engine Rankings. Amy Langville and Carl Meyer.Princeton University Press.2006.