Algorithm::VSM --- A Perl module for retrieving files and documents from a software library with the VSM (Vector Space Model) and LSA (Latent Semantic Analysis) algorithms in response to search words and phrases.
# FOR CONSTRUCTING A VSM MODEL FOR RETRIEVAL: use Algorithm::VSM; my $corpus_dir = "corpus"; my @query = qw/ program ListIterator add ArrayList args /; my $stop_words_file = "stop_words.txt"; my $vsm = Algorithm::VSM->new( break_camelcased_and_underscored => 1, case_sensitive => 0, corpus_directory => $corpus_dir, file_types => ['.txt', '.java'], max_number_retrievals => 10, min_word_length => 4, stop_words_file => $stop_words_file, use_idf_filter => 1, want_stemming => 1, ); $vsm->get_corpus_vocabulary_and_word_counts(); $vsm->display_corpus_vocab(); $vsm->display_corpus_vocab_size(); $vsm->write_corpus_vocab_to_file("vocabulary_dump.txt"); $vsm->display_inverse_document_frequencies(); $vsm->generate_document_vectors(); $vsm->display_doc_vectors(); $vsm->display_normalized_doc_vectors(); my $retrievals = $vsm->retrieve_for_query_with_vsm( \@query ); $vsm->display_retrievals( $retrievals ); The purpose of each constructor option and what is accomplished by the method calls should be obvious by their names. If not, they are explained in greater detail elsewhere in this documentation page. Note that the methods display_corpus_vocab() and display_doc_vectors() are there only for testing purposes with small corpora. If you must use them for large libraries/corpora, you might wish to redirect the output to a file. By default, a call to a constructor calculates normalized term-frequency vectors for the documents. Normalization consists of first calculating the term frequency tf(t) of a term t in a document as a proportion of the total numbers of words in the document and then multiplying it by idf(t), where idf(t) stands for the inverse document frequency associated with that term. Note that 'word' and 'term' mean the same thing. # FOR CONSTRUCTING AN LSA MODEL FOR RETRIEVAL: my $lsa = Algorithm::VSM->new( break_camelcased_and_underscored => 1, case_sensitive => 0, corpus_directory => $corpus_dir, file_types => ['.txt', '.java'], lsa_svd_threshold => 0.01, max_number_retrievals => 10, min_word_length => 4, stop_words_file => $stop_words_file, use_idf_filter => 1, want_stemming => 1, ); $lsa->get_corpus_vocabulary_and_word_counts(); $lsa->display_corpus_vocab(); $lsa->display_corpus_vocab_size(); $lsa->write_corpus_vocab_to_file("vocabulary_dump.txt"); $lsa->generate_document_vectors(); $lsa->construct_lsa_model(); my $retrievals = $lsa->retrieve_for_query_with_lsa( \@query ); $lsa->display_retrievals( $retrievals ); The initialization code before the constructor call and the calls for displaying the vocabulary and the vectors after the call remain the same as for the VSM case shown previously in this Synopsis. In the call above, the constructor parameter 'lsa_svd_threshold' determines how many of the singular values will be retained after we have carried out an SVD decomposition of the term-frequency matrix for the documents in the corpus. Singular values smaller than this threshold fraction of the largest value are rejected. # FOR MEASURING PRECISION VERSUS RECALL FOR VSM: my $corpus_dir = "corpus"; my $stop_words_file = "stop_words.txt"; my $query_file = "test_queries.txt"; my $relevancy_file = "relevancy.txt"; # All relevancy judgments # will be stored in this file my $vsm = Algorithm::VSM->new( break_camelcased_and_underscored => 1, case_sensitive => 0, corpus_directory => $corpus_dir, file_types => ['.txt', '.java'], min_word_length => 4, query_file => $query_file, relevancy_file => $relevancy_file, relevancy_threshold => 5, stop_words_file => $stop_words_file, want_stemming => 1, ); $vsm->get_corpus_vocabulary_and_word_counts(); $vsm->generate_document_vectors(); $vsm->estimate_doc_relevancies(); $vsm->display_doc_relevancies(); # used only for testing $vsm->precision_and_recall_calculator('vsm'); $vsm->display_precision_vs_recall_for_queries(); $vsm->display_average_precision_for_queries_and_map(); Measuring precision and recall requires a set of queries. These are supplied through the constructor parameter 'query_file'. The format of the this file must be according to the sample file 'test_queries.txt' in the 'examples' directory. The module estimates the relevancies of the documents to the queries and dumps the relevancies in a file named by the 'relevancy_file' constructor parameter. The constructor parameter 'relevancy_threshold' is used to decide which of the documents are considered to be relevant to a query. A document must contain at least the 'relevancy_threshold' occurrences of query words in order to be considered relevant to a query. # FOR MEASURING PRECISION VERSUS RECALL FOR LSA: my $lsa = Algorithm::VSM->new( break_camelcased_and_underscored => 1, case_sensitive => 0, corpus_directory => $corpus_dir, file_types => ['.txt', '.java'], lsa_svd_threshold => 0.01, min_word_length => 4, query_file => $query_file, relevancy_file => $relevancy_file, relevancy_threshold => 5, stop_words_file => $stop_words_file, want_stemming => 1, ); $lsa->get_corpus_vocabulary_and_word_counts(); $lsa->generate_document_vectors(); $lsa->construct_lsa_model(); $lsa->estimate_doc_relevancies(); $lsa->display_doc_relevancies(); $lsa->precision_and_recall_calculator('lsa'); $lsa->display_precision_vs_recall_for_queries(); $lsa->display_average_precision_for_queries_and_map(); We have already explained the purpose of the constructor parameter 'query_file' and about the constraints on the format of queries in the file named through this parameter. As mentioned earlier, the module estimates the relevancies of the documents to the queries and dumps the relevancies in a file named by the 'relevancy_file' constructor parameter. The constructor parameter 'relevancy_threshold' is used in deciding which of the documents are considered to be relevant to a query. A document must contain at least the 'relevancy_threshold' occurrences of query words in order to be considered relevant to a query. We have previously explained the role of the constructor parameter 'lsa_svd_threshold'. # FOR MEASURING PRECISION VERSUS RECALL FOR VSM USING FILE-BASED RELEVANCE JUDGMENTS: my $corpus_dir = "corpus"; my $stop_words_file = "stop_words.txt"; my $query_file = "test_queries.txt"; my $relevancy_file = "relevancy.txt"; my $vsm = Algorithm::VSM->new( break_camelcased_and_underscored => 1, case_sensitive => 0, corpus_directory => $corpus_dir, file_types => ['.txt', '.java'], min_word_length => 4, query_file => $query_file, relevancy_file => $relevancy_file, stop_words_file => $stop_words_file, want_stemming => 1, ); $vsm->get_corpus_vocabulary_and_word_counts(); $vsm->generate_document_vectors(); $vsm->upload_document_relevancies_from_file(); $vsm->display_doc_relevancies(); $vsm->precision_and_recall_calculator('vsm'); $vsm->display_precision_vs_recall_for_queries(); $vsm->display_average_precision_for_queries_and_map(); Now the filename supplied through the constructor parameter 'relevancy_file' must contain relevance judgments for the queries that are named in the file supplied through the parameter 'query_file'. The format of these two files must be according to what is shown in the sample files 'test_queries.txt' and 'relevancy.txt' in the 'examples' directory. # FOR MEASURING PRECISION VERSUS RECALL FOR LSA USING FILE-BASED RELEVANCE JUDGMENTS: my $corpus_dir = "corpus"; my $stop_words_file = "stop_words.txt"; my $query_file = "test_queries.txt"; my $relevancy_file = "relevancy.txt"; my $lsa = Algorithm::VSM->new( break_camelcased_and_underscored => 1, case_sensitive => 0, corpus_directory => $corpus_dir, file_types => ['.txt', '.java'], lsa_svd_threshold => 0.01, min_word_length => 4, query_file => $query_file, relevancy_file => $relevancy_file, stop_words_file => $stop_words_file, want_stemming => 1, ); $lsa->get_corpus_vocabulary_and_word_counts(); $lsa->generate_document_vectors(); $lsa->upload_document_relevancies_from_file(); $lsa->display_doc_relevancies(); $lsa->precision_and_recall_calculator('vsm'); $lsa->display_precision_vs_recall_for_queries(); $lsa->display_average_precision_for_queries_and_map(); As mentioned for the previous code block, the filename supplied through the constructor parameter 'relevancy_file' must contain relevance judgments for the queries that are named in the file supplied through the parameter 'query_file'. The format of this file must be according to what is shown in the sample file 'relevancy.txt' in the 'examples' directory. We have already explained the roles played by the constructor parameters such as 'lsa_svd_threshold'. # FOR MEASURING THE SIMILARITY MATRIX FOR A SET OF DOCUMENTS: my $corpus_dir = "corpus"; my $stop_words_file = "stop_words.txt"; my $vsm = Algorithm::VSM->new( break_camelcased_and_underscored => 1, case_sensitive => 0, corpus_directory => $corpus_dir, file_types => ['.txt', '.java'], min_word_length => 4, stop_words_file => $stop_words_file, want_stemming => 1, ); $vsm->get_corpus_vocabulary_and_word_counts(); $vsm->generate_document_vectors(); # code for calculating pairwise similarities as shown in the # script calculate_similarity_matrix_for_all_docs.pl in the # examples directory. This script makes calls to # # $vsm->pairwise_similarity_for_docs($docs[$i], $docs[$j]); # # for every pair of documents.
Version 1.70: All of the changes made in this version affect only that part of the module that is used for calculating precision-vs.-recall curve for the estimation of MAP (Mean Average Precision). The new formulas that go into estimating MAP are presented in the author's tutorial on significance testing. Additionally, when estimating the average retrieval precision for a query, this version explicitly disregards all documents that have zero similarity with the query.
Version 1.62 removes the Perl version restriction on the module. This version also fixes two bugs, one in the file scanner code and the other in the precision-and-recall calculator. The file scanner bug was related to the new constructor parameter case_sensitive that was introduced in Version 1.61. And the precision-and-recall calculator bug was triggered if a query consisted solely of non-vocabulary words.
case_sensitive
Version 1.61 improves the implementation of the directory scanner to make it more platform independent. Additionally, you are now required to specify in the constructor call the file types to be considered for computing the database model. If, say, you have a large software library and you want only Java and text files to be scanned for creating the VSM (or the LSA) model, you must supply that information to the module by setting the constructor parameter file_types to the anonymous list ['.java', '.txt']. An additional constructor parameter introduced in this version is case_sensitive. If you set it to 1, that will force the database model and query matching to become case sensitive.
file_types
['.java', '.txt']
Version 1.60 reflects the fact that people are now more likely to use this module by keeping the model constructed for a corpus in the fast memory (as opposed to storing the models in disk-based hash tables) for its repeated invocation for different queries. As a result, the default value for the constructor option save_model_on_disk was changed from 1 to 0. For those who still wish to store on a disk the model that is constructed, the script retrieve_with_VSM_and_also_create_disk_based_model.pl shows how you can do that. Other changes in 1.60 include a slight reorganization of the scripts in the examples directory. Most scripts now do not by default store their models in disk-based hash tables. This reorganization is reflected in the description of the examples directory in this documentation. The basic logic of constructing VSM and LSA models and how these are used for retrievals remains unchanged.
save_model_on_disk
retrieve_with_VSM_and_also_create_disk_based_model.pl
examples
Version 1.50 incorporates a couple of new features: (1) You now have the option to split camel-cased and underscored words for constructing your vocabulary set; and (2) Storing the VSM and LSA models in database files on the disk is now optional. The second feature, in particular, should prove useful to those who are using this module for large collections of documents.
Version 1.42 includes two new methods, display_corpus_vocab_size() and write_corpus_vocab_to_file(), for those folks who deal with very large datasets. You can get a better sense of the overall vocabulary being used by the module for file retrieval by examining the contents of a dump file whose name is supplied as an argument to write_corpus_vocab_to_file().
display_corpus_vocab_size()
write_corpus_vocab_to_file()
Version 1.41 downshifts the required version of the PDL module. Also cleaned up are the dependencies between this module and the submodules of PDL.
Version 1.4 makes it easier for a user to calculate a similarity matrix over all the documents in the corpus. The elements of such a matrix express pairwise similarities between the documents. The pairwise similarities are based on the dot product of two document vectors divided by the product of the vector magnitudes. The 'examples' directory contains two scripts to illustrate how such matrices can be calculated by the user. The similarity matrix is output as a CSV file.
Version 1.3 incorporates IDF (Inverse Document Frequency) weighting of the words in a document file. What that means is that the words that appear in most of the documents get reduced weighting since such words are non-discriminatory with respect to the retrieval of the documents. A typical formula that is used to calculate the IDF weight for a word is the logarithm of the ratio of the total number of documents to the number of documents in which the word appears. So if a word were to appear in all the documents, its IDF multiplier would be zero in the vector representation of a document. If so desired, you can turn off the IDF weighting of the words by explicitly setting the constructor parameter use_idf_filter to zero.
use_idf_filter
Version 1.2 includes a code correction and some general code and documentation cleanup.
With Version 1.1, you can access the retrieval precision results so that you can compare two different retrieval algorithms (VSM or LSA with different choices for some of the constructor parameters) with significance testing. (Version 1.0 merely sent those results to standard output, typically your terminal window.) In Version 1.1, the new script significance_testing.pl in the 'examples' directory illustrates significance testing with Randomization and with Student's Paired t-Test.
Algorithm::VSM is a perl5 module for constructing a Vector Space Model (VSM) or a Latent Semantic Analysis Model (LSA) of a collection of documents, usually referred to as a corpus, and then retrieving the documents in response to search words in a query.
VSM and LSA models have been around for a long time in the Information Retrieval (IR) community. More recently such models have been shown to be effective in retrieving files/documents from software libraries. For an account of this research that was presented by Shivani Rao and the author of this module at the 2011 Mining Software Repositories conference, see http://portal.acm.org/citation.cfm?id=1985451.
VSM modeling consists of: (1) Extracting the vocabulary used in a corpus. (2) Stemming the words so extracted and eliminating the designated stop words from the vocabulary. Stemming means that closely related words like 'programming' and 'programs' are reduced to the common root word 'program' and the stop words are the non-discriminating words that can be expected to exist in virtually all the documents. (3) Constructing document vectors for the individual files in the corpus --- the document vectors taken together constitute what is usually referred to as a 'term-frequency' matrix for the corpus. (4) Normalizing the document vectors to factor out the effect of document size and, if desired, multiplying the term frequencies by the IDF (Inverse Document Frequency) values for the words to reduce the weight of the words that appear in a large number of documents. (5) Constructing a query vector for the search query after the query is subject to the same stemming and stop-word elimination rules that were applied to the corpus. And, lastly, (6) Using a similarity metric to return the set of documents that are most similar to the query vector. The commonly used similarity metric is one based on the cosine distance between two vectors. Also note that all the vectors mentioned here are of the same size, the size of the vocabulary. An element of a vector is the frequency of occurrence of the word corresponding to that position in the vector.
LSA modeling is a small variation on VSM modeling. Now you take VSM modeling one step further by subjecting the term-frequency matrix for the corpus to singular value decomposition (SVD). By retaining only a subset of the singular values (usually the N largest for some value of N), you can construct reduced-dimensionality vectors for the documents and the queries. In VSM, as mentioned above, the size of the document and the query vectors is equal to the size of the vocabulary. For large corpora, this size may involve tens of thousands of words --- this can slow down the VSM modeling and retrieval process. So you are very likely to get faster performance with retrieval based on LSA modeling, especially if you store the model once constructed in a database file on the disk and carry out retrievals using the disk-based model.
This module has only been tested for software retrieval. For more general text retrieval, you would need to replace the simple stemmer used in the module by one based on, say, Porter's Stemming Algorithm. You would also need to vastly expand the list of stop words appropriate to the text corpora of interest to you. As previously mentioned, the stop words are the commonly occurring words that do not carry much discriminatory power from the standpoint of distinguishing between the documents. See the file 'stop_words.txt' in the 'examples' directory for how such a file must be formatted.
It is not uncommon for large software libraries to consist of tens of thousands of documents that include source-code files, documentation files, README files, configuration files, etc. The bug-localization work presented recently by Shivani Rao and this author at the 2011 Mining Software Repository conference (MSR11) was based on a relatively small iBUGS dataset involving 6546 documents and a vocabulary size of 7553 unique words. (Here is a link to this work: http://portal.acm.org/citation.cfm?id=1985451. Also note that the iBUGS dataset was originally put together by V. Dallmeier and T. Zimmermann for the evaluation of automated bug detection and localization tools.) If V is the size of the vocabulary and M the number of the documents in the corpus, the size of each vector will be V and size of the term-frequency matrix for the entire corpus will be VxM. So if you were to duplicate the bug localization experiments in http://portal.acm.org/citation.cfm?id=1985451 you would be dealing with vectors of size 7553 and a term-frequency matrix of size 7553x6546. Extrapolating these numbers to really large libraries/corpora, we are obviously talking about very large matrices for SVD decomposition. For large libraries/corpora, it would be best to store away the model in a disk file and to base all subsequent retrievals on the disk-stored models. The 'examples' directory contains scripts that carry out retrievals on the basis of disk-based models. Further speedup in retrieval can be achieved by using LSA to create reduced-dimensionality representations for the documents and by basing retrievals on the stored versions of such reduced-dimensionality representations.
V
M
The performance of a retrieval algorithm is typically measured by two properties: Precision at rank and Recall at rank. As mentioned in my tutorial https://engineering.purdue.edu/kak/Tutorials/SignificanceTesting.pdf, at a given rank r, Precision is the ratio of the number of retrieved documents that are relevant to the total number of retrieved documents up to that rank. And, along the same lines, Recall at a given rank r is the ratio of the number of retrieved documents that are relevant to the total number of relevant documents. The Average Precision associated with a query is the average of all the Precision-at-rank values for all the documents relevant to that query. When query specific Average Precision is averaged over all the queries, you get Mean Average Precision (MAP) as a single-number characterizer of the retrieval power of an algorithm for a given corpus. For an oracle, the value of MAP should be 1.0. On the other hand, for purely random retrieval from a corpus, the value of MAP will be inversely proportional to the size of the corpus. (See the discussion in https://engineering.purdue.edu/kak/Tutorials/SignificanceTesting.pdf for further explanation on these retrieval precision evaluators.)
Precision at rank
Recall at rank
r
Precision
Recall
This module includes methods that allow you to carry out these retrieval accuracy measurements using the relevancy judgments supplied through a disk file. If human-supplied relevancy judgments are not available, the module will be happy to estimate relevancies for you just by determining the number of query words that exist in a document. Note, however, that relevancy judgments estimated in this manner cannot be trusted. That is because ultimately it is the humans who are the best judges of the relevancies of documents to queries. The humans bring to bear semantic considerations on the relevancy determination problem that are beyond the scope of this module.
The module provides the following methods for constructing VSM and LSA models of a corpus, for using the models thus constructed for retrieval, and for carrying out precision versus recall calculations for the determination of retrieval accuracy on the corpora of interest to you.
A call to new() constructs a new instance of the Algorithm::VSM class:
new()
Algorithm::VSM
my $vsm = Algorithm::VSM->new( break_camelcased_and_underscored => 1, case_sensitive => 0, corpus_directory => "", corpus_vocab_db => "corpus_vocab_db", doc_vectors_db => "doc_vectors_db", file_types => $my_file_types, lsa_svd_threshold => 0.01, max_number_retrievals => 10, min_word_length => 4, normalized_doc_vecs_db => "normalized_doc_vecs_db", query_file => "", relevancy_file => $relevancy_file, relevancy_threshold => 5, save_model_on_disk => 0, stop_words_file => "", use_idf_filter => 1, want_stemming => 1, );
The values shown on the right side of the big arrows are the default values for the parameters. The value supplied through the variable $my_file_types would be something like ['.java', '.txt'] if, say, you wanted only Java and text files to be included in creating the database model. The following nested list will now describe each of the constructor parameters shown above:
$my_file_types
The parameter break_camelcased_and_underscored when set causes the underscored and camel-cased words to be split. By default the parameter is set. So if you don't want such words to be split, you must set it explicitly to 0.
When set to 1, this parameter forces the module to maintain the case of the terms in the corpus files when creating the vocabulary and the document vectors. Setting case_sensitive to 1 also causes the query matching to become case sensitive. (This constructor parameter was introduced in Version 1.61.)
The parameter corpus_directory points to the root of the directory of documents for which you want to create a VSM or LSA model.
The parameter corpus_vocab_db is for naming the DBM in which the corpus vocabulary will be stored after it is subject to stemming and the elimination of stop words. Once a disk-based VSM model is created and stored away in the file named by this parameter and the parameter to be described next, it can subsequently be used directly for speedier retrieval.
The database named by doc_vectors_db stores the document vector representation for each document in the corpus. Each document vector has the same size as the corpus-wide vocabulary; each element of such a vector is the number of occurrences of the word that corresponds to that position in the vocabulary vector.
This parameter tells the module what types of files in the corpus directory you want scanned for creating the database model. The value supplied for this parameter is an anonymous list of the file suffixes for the file types. For example, if you wanted only Java and text files to be scanned, you will set this parameter to ['.java', '.txt']. The module throws an exception if this parameter is left unspecified. (This constructor parameter was introduced in Version 1.61.)
The parameter lsa_svd_threshold is used for rejecting singular values that are smaller than this threshold fraction of the largest singular value. This plays a critical role in creating reduced-dimensionality document vectors in LSA modeling of a corpus.
The constructor parameter max_number_retrievals stands for what it means.
The parameter min_word_length sets the minimum number of characters in a word in order for it to be included in the corpus vocabulary.
The database named by normalized_doc_vecs_db stores the normalized document vectors. Normalization consists of factoring out the size of the documents by dividing the term frequency for each word in a document by the number of words in the document, and then multiplying the result by the idf (Inverse Document Frequency) value for the word.
The parameter query_file points to a file that contains the queries to be used for calculating retrieval performance with Precision and Recall numbers. The format of the query file must be as shown in the sample file test_queries.txt in the 'examples' directory.
test_queries.txt
This option names the disk file for storing the relevancy judgments.
The constructor parameter relevancy_threshold is used for automatic determination of document relevancies to queries on the basis of the number of occurrences of query words in a document. You can exercise control over the process of determining relevancy of a document to a query by giving a suitable value to the constructor parameter relevancy_threshold. A document is considered relevant to a query only when the document contains at least relevancy_threshold number of query words.
The constructor parameter save_model_on_disk will cause the basic information about the VSM and the LSA models to be stored on the disk. Subsequently, any retrievals can be carried out from the disk-based model.
The parameter stop_words_file is for naming the file that contains the stop words that you do not wish to include in the corpus vocabulary. The format of this file must be as shown in the sample file stop_words.txt in the 'examples' directory.
stop_words.txt
The constructor parameter use_idf_filter is set by default. If you want to turn off the normalization of the document vectors, including turning off the weighting of the term frequencies of the words by their idf values, you must set this parameter explicitly to 0.
The boolean parameter want_stemming determines whether or not the words extracted from the documents would be subject to stemming. As mentioned elsewhere, stemming means that related words like 'programming' and 'programs' would both be reduced to the root word 'program'.
You call this subroutine for constructing an LSA model for your corpus after you have extracted the corpus vocabulary and constructed document vectors:
$vsm->construct_lsa_model();
The SVD decomposition that is carried out in LSA model construction uses the constructor parameter lsa_svd_threshold to decide how many of the singular values to retain for the LSA model. A singular is retained only if it is larger than the lsa_svd_threshold fraction of the largest singular value.
lsa_svd_threshold
The Average Precision for a query is the average of the Precision-at-rank values associated with each of the corpus documents relevant to the query. The mean of the Average Precision values for all the queries is the Mean Average Precision (MAP). The Average Precision values for the queries and the overall MAP can be printed out by calling
Average Precision
MAP
$vsm->display_average_precision_for_queries_and_map();
If you would like to see corpus vocabulary as constructed by the previous call, make the call
$vsm->display_corpus_vocab();
Note that this is a useful thing to do only on small test corpora. If you need to examine the vocabulary for a large corpus, call the two methods listed below.
If you would like for the module to print out in your terminal window the size of the vocabulary, make the call
$vsm->display_corpus_vocab_size();
If you would like to see the document relevancies generated by the previous method, you can call
$vsm->display_doc_relevancies()
If you would like to see the document vectors constructed by the previous call, make the call:
$vsm->display_doc_vectors();
Note that this is a useful thing to do only on small test corpora. If you must call this method on a large corpus, you might wish to direct the output to a file.
You can display the idf value associated with each word in the corpus by
$vsm->display_inverse_document_frequencies();
The idf of a word in the corpus is calculated typically as the logarithm of the ratio of the total number of documents in the corpus to the number of documents in which the word appears (with protection built in to prevent division by zero). Ideally, if a word appears in all the documents, its idf would be small, close to zero. Words with small idf values are non-discriminatory and should get reduced weighting in document retrieval.
If you would like to see the normalized document vectors, make the call:
$vsm->display_normalized_doc_vectors();
See the comment made previously as to what is meant by the normalization of a document vector.
A call to precision_and_recall_calculator() will normally be followed by the following call
precision_and_recall_calculator()
$vsm->display_precision_vs_recall_for_queries();
for displaying the Precision@rank and Recall@rank values.
Precision@rank
Recall@rank
You can display the retrieved document names by calling this method using the syntax:
$vsm->display_retrievals( $retrievals );
where $retrievals is a reference to the hash returned by a call to one of the retrieve methods. The display method shown here respects the retrieval size constraints expressed by the constructor parameter max_number_retrievals.
$retrievals
retrieve
max_number_retrievals
Before you can carry out precision and recall calculations to test the accuracy of VSM and LSA based retrievals from a corpus, you need to have available the relevancy judgments for the queries. (A relevancy judgment for a query is simply the list of documents relevant to that query.) Relevancy judgments are commonly supplied by the humans who are familiar with the corpus. But if such human-supplied relevance judgments are not available, you can invoke the following method to estimate them:
$vsm->estimate_doc_relevancies();
For the above method call, a document is considered to be relevant to a query if it contains several of the query words. As to the minimum number of query words that must exist in a document in order for the latter to be considered relevant, that is determined by the relevancy_threshold parameter in the VSM constructor.
relevancy_threshold
But note that this estimation of document relevancies to queries is NOT for serious work. The reason for that is because ultimately it is the humans who are the best judges of the relevancies of documents to queries. The humans bring to bear semantic considerations on the relevancy determination problem that are beyond the scope of this module.
The generated relevancies are deposited in a file named by the constructor parameter relevancy_file.
relevancy_file
If you want to get hold of all the filenames in the corpus in your own script, you can call
my @docs = @{$vsm->get_all_document_names()};
The array on the left will contain an alphabetized list of the files.
This is a necessary step after the vocabulary used by a corpus is constructed. (Of course, if you will be doing document retrieval through a disk-stored VSM or LSA model, then you do not need to call this method. You construct document vectors through the following call:
$vsm->generate_document_vectors();
After you have constructed a new instance of the Algorithm::VSM class, you must now scan the corpus documents for constructing the corpus vocabulary. This you do by:
$vsm->get_corpus_vocabulary_and_word_counts();
The only time you do NOT need to call this method is when you are using a previously constructed disk-stored VSM model for retrieval.
If you want to run significance tests on the retrieval accuracies you obtain on a given corpus and with different algorithms (VSM or LSA with different choices for the constructor parameters), your own script would need access to the average precision data for a set of queries. You can get hold of this data by calling
$vsm->get_query_sorted_average_precision_for_queries();
The script significance_testing.pl in the 'examples' directory shows how you can use this method for significance testing.
significance_testing.pl
If you would like to compare in your own script any two documents in the corpus, you can call
my $similarity = $vsm->pairwise_similarity_for_docs("filename_1", "filename_2"); or my $similarity = $vsm->pairwise_similarity_for_normalized_docs("filename_1", "filename_2");
Both these calls return a number that is the dot product of the two document vectors normalized by the product of their magnitudes. The first call uses the regular document vectors and the second the normalized document vectors.
After you have created or obtained the relevancy judgments for your test queries, you can make the following call to calculate Precision@rank and Recall@rank:
$vsm->precision_and_recall_calculator('vsm'); or $vsm->precision_and_recall_calculator('lsa');
depending on whether you are testing VSM-based retrieval or LSA-based retrieval.
After you have built an LSA model through the call to construct_lsa_model(), you can retrieve the document names most similar to the query by:
construct_lsa_model()
my $retrievals = $vsm->retrieve_with_lsa( \@query );
Subsequently, you can display the retrievals by calling the display_retrievals($retrieval) method described previously.
display_retrievals($retrieval)
After you have constructed a VSM model, you call this method for document retrieval for a given query @query. The call syntax is:
@query
my $retrievals = $vsm->retrieve_with_vsm( \@query );
The argument, @query, is simply a list of words that you wish to use for retrieval. The method returns a hash whose keys are the document names and whose values the similarity distance between the document and the query. As is commonly the case with VSM, this module uses the cosine similarity distance when comparing a document vector with the query vector.
When human-supplied relevancies are available, you can upload them into the program by calling
$vsm->upload_document_relevancies_from_file();
These relevance judgments will be read from a file that is named with the relevancy_file constructor parameter.
When you invoke the methods get_corpus_vocabulary_and_word_counts() and generate_document_vectors(), that automatically deposits the VSM model in the database files named with the constructor parameters corpus_vocab_db, doc_vectors_db and normalized_doc_vecs_db. Subsequently, you can carry out retrieval by directly using this disk-based VSM model for speedier performance. In order to do so, you must upload the disk-based model by
get_corpus_vocabulary_and_word_counts()
generate_document_vectors()
corpus_vocab_db
doc_vectors_db
normalized_doc_vecs_db
$vsm->upload_normalized_vsm_model_from_disk();
Subsequently you call
my $retrievals = $vsm->retrieve_with_vsm( \@query ); $vsm->display_retrievals( $retrievals );
for retrieval and for displaying the results.
This is the method to call for large text corpora if you would like to examine the vocabulary created. The call syntax is
$vsm->write_corpus_vocab_to_file($filename);
where $filename is the name of the file that you want the vocabulary to be written out to. This call will also show the frequency of each vocabulary word in your corpus.
$filename
This module requires the following modules:
SDBM_File Storable PDL File::Basename File::Spec::Functions
The first two of these are needed for creating disk-based database records for the VSM and LSA models. The third is needed for calculating the SVD of the term-frequency matrix. (PDL stands for Perl Data Language.) The last two are needed by the directory scanner to make pathnames platform independent.
See the 'examples' directory in the distribution for the scripts listed below:
For basic VSM-based model construction and retrieval, run the script:
retrieve_with_VSM.pl
Starting with version 1.60, this script does not store away the VSM model in disk-based hash tables. If you want your model to be stored on the disk, you must run the script retrieve_with_VSM_and_also_create_disk_based_model.pl for that.
If you want to run an infinite loop for repeated retrievals from a VSM model, run the script
continuously_running_VSM_retrieval_engine.pl
You can create a script similar to this for doing the same with LSA models.
For storing the model information in disk-based DBM files that can subsequently be used for both VSM and LSA retrieval, run the script:
For basic LSA-based model construction and retrieval, run the script:
retrieve_with_LSA.pl
Starting with version 1.60, this script does not store away the model information in disk-based hash tables. If you want your model to be stored on the disk, you must run the script retrieve_with_VSM_and_also_create_disk_based_model.pl for that.
If you have previously run a script like retrieve_with_VSM_and_also_create_disk_based_model.pl, you can run the script
retrieve_with_disk_based_VSM.pl
for repeated VSM-based retrievals from a disk-based model.
retrieve_with_disk_based_LSA.pl
for repeated LSA-based retrievals from a disk-based model.
To experiment with precision and recall calculations for VSM retrieval, run the script:
calculate_precision_and_recall_for_VSM.pl
Note that this script will carry out its own estimation of relevancy judgments --- which in most cases would not be a safe thing to do.
To experiment with precision and recall calculations for LSA retrieval, run the script:
calculate_precision_and_recall_for_LSA.pl
Precision and recall calculations for retrieval accuracy determination are best carried out with human-supplied judgments of relevancies of the documents to queries. If such judgments are available, run the script:
calculate_precision_and_recall_from_file_based_relevancies_for_VSM.pl
This script will print out the average precisions for the different test queries and calculate the MAP metric of retrieval accuracy.
If human-supplied relevancy judgments are available and you wish to experiment with precision and recall calculations for LSA-based retrieval, run the script:
calculate_precision_and_recall_from_file_based_relevancies_for_LSA.pl
significance_testing.pl randomization
or
significance_testing.pl t-test
Significance testing consists of forming a null hypothesis that the two retrieval algorithms you are considering are the same from a black-box perspective and then calculating what is known as a p-value. If the p-value is less than, say, 0.05, you reject the null hypothesis.
p-value
calculate_similarity_matrix_for_all_docs.pl
calculate_similarity_matrix_for_all_normalized_docs.pl
The former uses regular document vectors for calculating the similarity between every pair of documents in the corpus. And the latter uses normalized document vectors for the same purpose. The document order used for row and column indexing of the matrix corresponds to the alphabetic ordering of the document names in the corpus directory.
None by design.
You have to be careful when carrying out Precision verses Recall calculations if you do not wish to lose the previously created relevancy judgments. Invoking the method estimate_doc_relevancies() in your own script will cause the file relevancy.txt to be overwritten. If you have created a relevancy database and stored it in a file called, say, relevancy.txt, you should make a backup copy of this file before executing a script that calls estimate_doc_relevancies().
estimate_doc_relevancies()
relevancy.txt
Please notify the author if you encounter any bugs. When sending email, please place the string 'VSM' in the subject line to get past my spam filter.
Download the archive from CPAN in any directory of your choice. Unpack the archive with a command that on a Linux machine would look like:
tar zxvf Algorithm-VSM-1.70.tar.gz
This will create an installation directory for you whose name will be Algorithm-VSM-1.70. Enter this directory and execute the following commands for a standard install of the module if you have root privileges:
Algorithm-VSM-1.70
perl Makefile.PL make make test sudo make install
If you do not have root privileges, you can carry out a non-standard install the module in any directory of your choice by:
perl Makefile.PL prefix=/some/other/directory/ make make test make install
With a non-standard install, you may also have to set your PERL5LIB environment variable so that this module can find the required other modules. How you do that would depend on what platform you are working on. In order to install this module in a Linux machine on which I use tcsh for the shell, I set the PERL5LIB environment variable by
setenv PERL5LIB /some/other/directory/lib64/perl5/:/some/other/directory/share/perl5/
If I used bash, I'd need to declare:
export PERL5LIB=/some/other/directory/lib64/perl5/:/some/other/directory/share/perl5/
Many thanks are owed to Shivani Rao and Bunyamin Sisman for sharing with me their deep insights in IR. Version 1.4 was prompted by Zahn Bozanic's interest in similarity matrix characterization of a corpus. Thanks, Zahn!
Several of the recent changes to the module are a result of the feedback I have received from Naveen Kulkarni of Infosys Labs. Thanks, Naveen!
Version 1.62 was a result of Slaven Rezic's recommendation that I remove the Perl version restriction on the module since he was able to run it with Perl version 5.8.9. Another important reason for v. 1.62 was the discovery of the two bugs mentioned in Changes, one of them brought to my attention by Naveen Kulkarni.
The author, Avinash Kak, recently finished a 17-year long "Objects Trilogy" project with the publication of the book "Designing with Objects" by John-Wiley. If interested, check out his web page at Purdue to find out what the Objects Trilogy project was all about. You might like "Designing with Objects" especially if you enjoyed reading Harry Potter as a kid (or even as an adult, for that matter). The other two books in the trilogy are "Programming with Objects" and "Scripting with Objects".
For all issues related to this module, contact the author at kak@purdue.edu
kak@purdue.edu
If you send email, please place the string "VSM" in your subject line to get past the author's spam filter.
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
Copyright 2015 Avinash Kak
To install Algorithm::VSM, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::VSM
CPAN shell
perl -MCPAN -e shell install Algorithm::VSM
For more information on module installation, please visit the detailed CPAN module installation guide.