Assignment Overview

The purpose of this assignment is to gain experience with the TermVector index and query rewriting using pseudo relevance feedback (PRF).

• Add query rewriting with pseudo relevance feedback to the QryEval search engine.
• Conduct experiments with your search engine.
• Write a report about your work.
• Upload your work to the course website for grading.

1. New Retrieval Capabilities

Query rewriting with pseudo relevance feedback requires that you add three new capabilities to your search engine: i) a Rewriter class, ii) the Okapi pseudo relevance feedback algorithm, and iii) the query likelihood (Indri, RM3) relevance feedback algorithm. Capabilities that you expect to be general should be implemented in the Rewriter class. Capabilities that you expect to be specific to a particular algorithm should be implemented in a class for that algorithm (e.g., RewriteWithPrf).

Query rewriting with pseudo relevance feedback must meet the following requirements.

1. It must use Okapi or query likelihood pseudo relevance feedback (PRF) to rewrite queries (i.e., replace the original query with a new query).
2. The PRF algorithm must use text from the field identified by the prf:expansionField parameter and write a query for that same field.
3. If the prf:rm3:origWeight parameter is specified, the expanded query must be a weighted combination (#WSUM) of the original query and the learned query created by PRF. If the parameter is not specified, the expanded query must be the learned query.
4. The learned query must be written to a .qryOut file for grading.

See the Design Guide for details.

Your source code must run within the homework testing service.

2. Experiments

Conduct three experiments that investigate the effects of query rewriting with pseudo relevance feedback on retrieval accuracy and efficiency, as described below. HW2 uses a subset of the HW1 bag of words to help your experiments run a little faster.

This assignment introduces a win:tie:loss metric. Report the number of queries that win, tie, or lose an experiment, as measured using relative MAP difference with a baseline.
     (MAP_experiment - MAP_baseline) / MAP_baseline
A query wins if the relative difference ≥ 2.0% and loses if the relative difference ≤ -2.0%. Otherwise, it is a tie.

2.1. Experiment 1: Number of Feedback Documents

Examine the effects of varying the number of feedback documents on pseudo relevance feedback. The baseline algorithm is BM25. The experimental systems use the top 10, 20, 30, and 50 documents for relevance feedback to produce a new query with 10 terms for each PRF algorithm.

2.2. Experiment 2: Number of Feedback Terms

Examine the interaction between the number of feedback documents and feedback terms on ranking quality. Examine six configurations: {10, 20, 30} documents × {20, 30} terms for each PRF algorithm.

2.3. Experiment 3: Exploration

The third experiment is of your own design. Experiments 1 and 2 taught you a little about PRF. Now, develop one or two hypotheses about PRF that interest you. Create and test five custom PRF configurations that investigate your hypotheses. You may use one or both PRF algorithm(s) for this experiment.

Grading of this experiment is based more on the quality of your ideas than the quality of your results. It is okay for your hypotheses to fail as long as they are interesting and show an understanding of the task.

2.4. Advice

Parameter files: As suggested for HW1, you may find it faster and more accurate to use a .csv file and a script to generate .param files automatically. There are 26 experiments. That's a lot of .param files to write manually.

.inRank files: Most of your experiments use the same BM25 initial ranking. Create it once, save it to an .inRank file, and reuse it to make your experiments run more quickly. We strongly recommend that you use .inRank files for your experiments.

Automation: Each of the experiments may take several minutes to run. The full set of experiments may take 2-3 hours. We use a script that runs experiments in the background while we do other tasks. You may find it productive to do something similar.

3. The Report

11-442 students must submit a one-page report that contains a statement of collaboration and originality. A template is provided in Microsoft Word and pdf formats. The report must follow the structure provided in the template.

11-642 students must write a report that describes their work and their analysis of the experimental results. A report template is provided in Microsoft Word and pdf formats. The report must follow the structure provided in the template.

See the grading information document for information about how experiments and reports are graded.

4. Submission Instructions

Create a .zip file that contains your software, following the same requirements used for interim software submissions. Name your report yourAndrewID-HW2-Report.pdf and place it in the same directory that contains your software (e.g., the directory that contains QryEval.java).

Reproducibility: Your submission must include files in the QryEval directory that enable all of your experiments to be reproduced. They must follow a naming convention so that the homework testing service can find them. The naming convention is approximately <hwid>-Exp-<experiment id>.<filetype>, for example, HW1-Exp-3.1a.qry and HW1-Exp-3.1a.param. See the report template (above) for guidance about how to name the files for each experiment.

Submit your homework by checking the "Final Submission" box in the homework testing service. We will run a complete set of tests on your software, so you do not need to select tests to run. If you make several final submissions, we will grade your last submission.

FAQ

If you have questions not answered here, see the HW2 FAQ and the Homework Testing FAQ.