Menu

[ IVLE ]

[ Overview ]
[ Syllabus ]
[ Grading ]
[ Homework
  HW 1
  HW 2
  HW 3
  >HW 4
  HW 5 ]
[ Misc. ]

Last updated: Monday, March 12, 2012 09:54:34 AM SGT

In Homework 4, you will implement a searcher that supports scoring using vector space model. To do this, you can choose to further modify either your solution to Homework 2 or 3 or use Hadi's sample solution to Homework 2.

Commonalities with previous Homeworks

The indexing and query commands will use an identical input format to Homeworks 2 and 3, so that you need not modify any of your code to deal with command line processing. To recap:

Indexing: $ python index.py -i directory-of-documents -d dictionary-file -p postings-file

Searching: $ python search.py -d dictionary-file -p postings-file -q file-of-queries -o output-file-of-results

We will also again use the Reuters training data set provided by NLTK. Depending on where you specified the directory for NLTK data whenyou first installed the NLTK data (recall that the installation is triggered by nltk.download()), this data set is located under a path like: .../nltk_data/corpora/reuters/training/.

As in Homework 2 and 3, your search process must not keep the postings file in memory in answering queries, but instead use a file cursor to randomly access parts of the postings file. However, there is no such restriction for the indexer (you are not asked to implement BSBI or SPIMI). Also, you should continue to employ Porter stemming in your submission, both for document indexing as well as query processing.

Vector Space Model

To implement the VSM, you may choose to implement (you can can do it differently) your dictionary and postings lists in the following format. The only difference between this format and that in Figure 1.4 in the textbook, is that you encode term frequencies in the postings for the purpose of computing tf×idf. The tuple in each posting represents (doc ID, term freq). You don't need to do dictionary/postings compression, although you're welcomed to write in or retain this capability if you are basing on a previous assignment.

term doc freq (df)
postings lists
ambitious 5 (1, 5)→ (7,2) → (21, 7) → ...
... ... ...

In the searching step, you will need to rank documents by cosine similarity based on tf×idf. In terms of SMART notation of ddd.qqq, you will need to implement the lnn.ltc ranking scheme (i.e., log tf and no idf for documents, and log tf and idf for queries. Only the query component needs to be cosine normalized). Compute cosine similarity between the query and each document, with the weights follow the tf×idf calculation, where term freq = 1 + log(tf) and inverse document frequency idf = log(N/df) (for queries). That is,

tf-idf = (1 + log(tf)) * log(N/df).

It's suggested that you use log base 10 for your logarithm calculations (i.e., math.log(x, 10), be careful of cases like math.log(0, 10)). The queries we provide are now free text queries, i.e., you don't need to use query operators like AND, OR, NOT and parentheses, and no phrasal queries. These free text queries are similar to those you type in the Google search bar.

Your searcher should output a list of up to 10 most relevant (less if there are fewer than ten documents that have matching stems to the query) docIDs in response to the query. These documents need to be ordered by relevance, with the first document being most relevant. For those with same relevance, further sort them by the increasing order of the docIDs.

What to turn in?

You are required to submit index.py, search.py, dictionary.txt, and postings.txt. Please do not include the Reuters data in your submission.

Essay questions

You are also asked to answer the following essay questions. These are to test your understanding of the lecture materials. Note that these are open-ended questions and do not have gold standard answers. A paragraph or two are usually sufficient for each question.

  1. In this assignment, we didn't ask you to support phrasal queries, which is a feature that is typically supported in web search engines. Describe how you would support phrasal search in conjunction with the VSM model. A sketch of the algorithm is sufficient. (For those of you who like a challenge, please go ahead and implement this feature in your submission but clearly demarcate it in your code and allow this feature to be turned on or off using the command line switch "-x" (where "-x" means to turn on the extended processing of phrasal queries). We will give a small bonus to submissions that achieve this functionality correctly).
  2. Describe how your search engine reacts to long documents and long queries as compared to short documents and queries. Is the normalization you use sufficient to address the problems (see Section 6.4.4 for a hint)? In your judgement, is the lnc.ltc scheme (n.b., not the ranking scheme you were asked to implement) sufficient for retrieving documents from the Reuters-21578 collection?
  3. Do you think zone or field parametric indices would be useful for practical search in the Reuters collection? Note: the Reuters collection does have metadata for each article but the quality of the metadata is not uniform, nor are the metadata classifications uniformly applied (some documents have it, some don't).

Submission Formatting

The instructions below are repeated for clarity sake.

You are allowed to do this assignment individually or as a team of two. There will be no difference in grading criteria if you do the assignment as a team or individually. Only one student in a team of two need to submit the assignment. For the submission information below, simply replace any mention of a matric number with the two matric numbers concatenated with a separating dash (e.g., U000000X-U000001Y).

For us to grade this assignment in a timely manner, we need you to adhere strictly to the following submission guidelines. They will help me grade the assignment in an appropriate manner. You will be penalized if you do not follow these instructions. Your matric number in all of the following statements should not have any spaces and any letters should be in CAPITALS. You are to turn in the following files:

These files will need to be suitably zipped in a single file called submission-<matric number>.zip. Please use a zip archive and not tar.gz, bzip, rar or cab files. Make sure when the archive unzips that all of the necessary files are found in a directory called submission-<matric number>. Upload the resulting zip file to the IVLE workbin by the due date: Monday, 26 Mar 11:59:59 pm SGT. There absolutely will be no extensions to the deadline of this assignment. Read the late policy if you're not sure about grade penalties for lateness.

Grading Guidelines

The grading criteria for the assignment is tentatively:

Disclaimer: percentage weights may vary without prior notice.

Hints



Min-Yen Kan <kanmy@comp.nus.edu.sg> Thu Mar 17 08:45:44 SGT 2011 | Version: 1.0 | Last modified: Sat Mar 24 12:33:54 2012