Introduction¶

This notebook will (hopefully) be the first in a series of notebooks related to work from the Coursera course, Text Retrieval and Search Engines. For the various topics covered in the course, the goal is to impliment some of the methods and tools in order to gain some hands-on experience.

The current plan is to use the same set of data for all of the notebooks. The dataset consists of articles scraped from PhysOrg, which posts news stories related to new developments in various science / technology ares. The articles are associated with a variety of PhysOrg topic areas, though each article is associated with only a simple topic. Method / algorithm evaluation will utilize these categories.

For the first article, as one can observe from the title, we will go over the process for constructing the "Simplest Vector Space Model Instantiation". Key features of this model are:

• Bag of Word feature encoding using binary hits for terms
• No normalization or weighting applied to terms or documents
• Dot product similarity for calculating similarity scores between documents / queries

Term and document preprocessing will be minimal, partially for simplicity, partially to exemplify various shortcomings / strengths of various models. Below is a list of things preprocessing will (not) include:

• No stop word removal
• Tokens / features are words, not phrases
• All words to lowercase
• Remove all punctuation
• Remove all numbers
• No stemming
• No mapping multiple related words onto a single feature / word (e.g., no LSI-like dimensionality reduction)

Given the context of this mini-project, queries (or statements that look like queries) are needed to evaluate performance. As all articles have associated titles, we use the titles to generate queries for each document in the collection.

Load and Preprocess¶

Having already scraped a set of PhysOrg articles and extracted the relevant textual content (see a previous post of for details), all we need to do is load the files from the stored pickle. We can see, below, that there are about 1,200 documents (articles) in this collection.

Each entry has the article URL, article category, the content (i.e., article text), the title, and the source (all are fro PhysOrg in this dataset). The article content will be used to generate the BOW vector, while the title entry will be used to generate the query. For grouping articles, the "category" feature will be used.

Restrict by Category¶

The vast majority of documents are associated with only eight topics, all with the pattern "NEWS_TYPE-news" as the name due to how the articles were originally obtained from PhysOrd. For our analysis, we will restrict the data to articles from the eight major categories ("Major 8"). Note that articles from the "technology-news" category far outnumber content from any other category, while counts from the other seven are fairly close.

Tokenize Content & Titles¶

In order to generate a (simpliest) Vector Space Representation for the content of each article, we must first preprocess the documents. For our simple case, this includes:

• All words to lowercase
• Remove punctuation
• Remove numbers
• No stop word removal
• No stemming
• Word tokenize each document (no "higher-order" features)
• Obtain the set of words contained in each document (ignore word counts)

Removing punctuation and numbers reduces the number of features from an area not likley to provide much benefit. Some methods convert all numbers to a generic placeholder (e.g., "NUMBER", not to be conflated with the word token "number"), but again, our focus is on simplicity.

NLTK is used for tokenization and whitespace / punctuation / number removal all in one step by utilizing the RegexpTokenizer. For large datasets, using regular expressions could be disastrous given the potential for regex to be quite slow (though this may be outdated). In our case, the small dataset being used does not run into any issues.

Why no stop word removal? Again, partially for simplicity and partially to help highlight shortcomings and strengths of the various models. Due to the sheer simplicity of the model in this notebook, much of the "noise" generate by stop words is mitigated, as each word can only contribute a total count of '1' to the Query - Document similarity score. In future models, we will see that stop words are midigated in other ways.

Similarly, the lack of stemming and extracting higher-order phrase features for use in the document vector representation is primarily for simplicity.

Later in the article, we will also be using the binary BOW generated from the title to create queries. Therefore, the title BOW representation is generated now as well. Titles are preprocessed and tokenized using the same methodology as the document content.

The above plots display the distibutions for total document length and unique words per document, respectively. Both appear to be Negative Bionomial distributions, which would make sense (note that neither has been normalized at this point). Simplistically, we can imagine that a document is a sequence of words. With some probabilitiy $p$, we add an additional random term to the document (a success), thereby increasing its length. With probability $1-p$ we decide not to add a new word (failure) to the document, and thus the document ends. In terms of the Negative Binomial, our specified number of failures before halting the process in this case is 1.

At this point, we also pickle the "articles" data frame for use in later articles:

Construct Document & Query BOW Vectors¶

Steps required for this process:

• Generate global vocabulary dictionary
• Convert each Binary BOW Document word into its respective index value generated from the dictionary
• Generate vector for each Document representing the words it contains

To construct the dictionary, document contents and titles are used. Various methods exist for handling unobserved words -- such as those that may arrise from our queries if we did not construct the dictionary using the titles -- but for our method, the outcome is the same regardless. That is, words in queries (titles) that were not observed in any documents do not contribute to a document's score. For making the processing easier, however, we include all terms in the dictionary.

The dictionary (hash table) is then utilized to create a word to integer mapping. From the mapping, each document's binary BOW representation can be converted into an N-dimensional vector, where N is the size of the dictionary. Each word is mapped to a particular dimension in the space. A document containing a particular word will have a value of '1' entered for the word's corresponding dimension in the document's vector representation. If a document does not contain a particular word, a '0' will be entered for that word's respective dimension.

Our particular method takes advantage of the fact that most documents do not contain most of the words in the dictionary by initializing a matrix of 0's with shape (Number of documents, Size of Dictionary). Then, we iterate over each document and replace 0's with 1's in the matrix where appropriate. The result is a (very) sparse matrix of word occurences in documents. We can see that less than 0.8% of the matrix is populated with 1's.

Titles (queries) are converted into the same vector space using the same method. The resulting document and query vectors are then used to calculate query - document similarity scores.

Calculating Query - Document Scores¶

In this section, we use the dot product to compute the pairwise query - document similarity scores. We use document titles to generate a query for each document. Thus, our query - document scores are proxies for document - document similarty scores mapped into a Text Retrieval paradigm.

This makes evaluating the results particularly simple and interesting, as we can make use of each document's associated category to generate the set of "expected" returned document. While this may greatly over-simplify the Text Retrieval problem, it makes for a particularly straight-forward and intuitive analysis.

Python's scipy library is used for easily calculating the pairwise similarities. Specifically, we make use of the "spatial.distance" module, which can be used for a wide variety of distance / similarity computations.

Not so surprisingly given the data, similarity scores top out at 17. This is reasonable given that the maximum score has an upper-bound equal to the maximum title length due to the use of the dot product in calculating the similarity score and the maximum number of unique words in a title (shown below) is 19 words. Most scores are below 10, with only about 1000 hitting 10 or above. This is also in line with the data observed below. Overall, the distribution of scores seems reasonable given the title lengths and the basic idea that most words in the dataset are sparse and therefore not shared between documents (queries / titles).

Evaluation¶

Utilizing the pre-defined groups from PhysOrg, we can compare Query - Document scores for (Query, Document) pairs in which both the Query and the Document are associated with the same category to (Query, Document) pairs in which the Query is associated one category and the Document is associated with a different category.

Since we are performing these analyses within the context of Information Retrieval and Search Engines, we will evaluate the Top 10 highest scoring Documents for each Query in terms of whether the Query and Documents share the same PhysOrg category.

We will first review the fraction of document types returned for all queries from a given category, and then look to evalute the method explored in this article using the F-Measure.

Document Types Returned by Category¶

For this portion of the analysis, we will look into 4 questions:

• What percentage of the time is the highest-scored document the document itself?
• What percentage of the time is the document itself within the top 10 highest scored documents?
• What percentage of the time is a document sharing the document in question's cetegory the top ranked document?
• For each category, what is the categorical break-down of documents in the top 10 list across all documents in that category?

The first three questions are answered directly below. Intuitively, we should expect a "good" method to return the respective document for a query most of the time. 75% of the time seems somewhat reasonable, though it would be reasonable to assume that we could do better. In the same vein, a 90% hit rate for returning the associated document in the Top 10 List is respectable, but also leaves much room for improvement. We will primarily use these values to compare to the next method we impliment.

For a more comprehensive picture of the method's performance, we analyze the fraction of each document type returned in the Top 10 List for each document type. Each square in the heatmap above represents the fraction of the column category's documents returned in the Top 10 List for a query associated with the row category. For example, for queries associated with the "science-news" category (row 2), about 29% of the total documents returned in the Top 10 Lists were from the "technology-news" category (column 6).

While we see a fairly strong diagonal (i.e. queries returning documents from the same category), the overall performance is not particularly encouraging outside of "technology-news", which also happens to have the largest number of documents in the collection by far.

Evaluation with the F-Measure¶

Eyeballing the data is not particularly conducive for comparing results. Luckily, the IR field has provided some useful measures for evaluating an arbitrary method's performance, the most notable of which are Precision and Recall. Precision evaluates the fraction of returned documents that are from the target class or category, while recall looks at the fraction of target documents in the entire collection returned. More precisly:

precision = (total relevant documents returned) / (total documents returned)

recall = (total relevant documents returned) / (total relevant documents in the collection)

While both of these metrics help evaluate a method, having a single value for comparing methods would be even more useful. The F-Measure combines Precision and Recall into a single metric that can be used to compare methods. The traditional -- or balanced -- F-Measure is calculated as follows:

Note that this metric is meant to evaluate a single query. We will calculate the average F-Measure across all queries (1) in each category and (2) in our dataset to obtain average F-Measures.

To do this, we first add the total document counts for each category to the "total_counts" data frame. Then, for each query entry in the "top10" data frame, we calculate the F-Measure. After calculating F-Measures for individual queries, we find the mean F-Measure for all queries in a category, and then calculate the overall mean F-Measure.

At this point, we can compare category performances to one another and see that queries from the "space-news" category obtained better F-Measures and any other category. Overall though, the F-Measures are rather disappointing, as the best possible score is 1.

It should be noted that obtaining a recall of '1' for any of the categories with our current dataset and methodology is impossible. For evaluating queries, the method only retrieves 10 documents. Each category contains at least 73 documents. For the dataset, the maximum possible score obtainable is about 0.24, which could potentially be obtained by the "space-news" category. Other categories have lower maximums because they have a larger number of associated documents in the collection.

Wrap-Up and Next Steps¶

In this notebook, we looked at one method for implimenting the "Simplest Vector Space Model Instantiation" using Python. This simple model has three main features:

• Bag of Word feature encoding using binary hits for terms
• No normalization or weighting applied to terms or documents
• Dot product used for calculating similarity scores between documents and queries

A selection of PhysOrg articles was used to demonstrate the model. In our analysis, the dataset was restricted to articles that were associated with the eight most prevelant categories. Each document was associated with a query that was generated from its title.

In evaluating the method, we looked at the Top 10 highest-scoring documents for each query. Using this subset, we looked at the category breakdowns for the returned documents, as well as the average F-Measure for each category and for the entire dataset. Overall, the "Simplest Vector Space Model Instantiation" looked to be lacking in its ability to return documents associated with the same category as the query (i.e., relevant documents).

In a subsequent notebook, we will look to improve the VSM by implimenting various term and document weighting schemes discussed in lectures from the Text Retrieval and Search Engines Coursera course. We will compare that model's performance to the performance of the model from this notebook.