Natural Language Processing CS224N/Ling237
Christopher Manning
Word-sense Disambiguation Project, HW#4
Due: Wednesday April 28, 2004, 5 pm

Word-sense disambiguation

Read this assignment soon, and especially if you are less familiar with programming, start working on it, discover stumbling blocks, and ask questions early. If anything is unclear or you need some kind of assistance, feel free to send a question to cs224n-spr0304-staff@lists.  However, before you do that, you should look for any FAQs on the website:

http://cs224n.stanford.edu

The aim of this assignment is to write a system that does context-based disambiguation.  The materials that you need for this assignment are in the following directory in AFS on the Sweet Hall machines:

	/afs/ir/class/cs224n/wsdp

Assignment Description

You will write a program that will disambiguate the senses of an ambiguous word. You will be provided with tagged training data and test data for several words. You should probably begin by making a straightforward implementation of some previously-tried technique for word sense disambiguation (some suggestions follow), and then seeing if you can improve it - the aim being to make this program as good at word sense disambiguation as possible. Your final submission should consist of a single system that performs as well as possible, or applies an interesting machine learning technique to disambiguation. The program may require tagged training instances or other lexical resources that you make use of.

The Data

The data for developing your program is located in /afs/ir/class/cs224n/wsdp/data. The files in wsd/ contain word sense data.

For each file in wsd/, there will be one sentence/context per line. In each line of the tagged training data (all filenames ending in .train), exactly one word to be disambiguated will be marked with an underscore, and followed by a sense identifier. The identifier will simply be an integer denoting the correct sense number for that occurrence. There will be no other underscores in the data. You may assume that there are no more than 30 senses for any given word; however, we will look more favorably on code that does not depend upon a hard-wired maximum number of senses.  

For the test data (all filenames ending in .test), the senses will be marked with only an underscore. The idea is that you should use each word's tagged training data to learn about the word's senses, and then predict the senses for the underscored words in the test data. Note that, in context, the actual word to be disambiguated may be a morphologically inflected or capitalized form of the word in the training data. The correct answers for each line of the test data are in the .ans files - of course, these are to be used only for evaluating the program's final performance! All the same, you can use all the given data for the provided words in any test / train combination you like; you may also create a validation set out of these. We will test the program on different words, with test and train files similar to those provided.

For example:

	Training data format: bank_2
	Test data format: bank_  

There are a few Java classes available to help you get started. These are in /afs/ir/class/cs224n/wsdp/src. The file WSD.java contains the main function that reads the training and test data, and may provide a convenient starting framework. Look at some of the comments there for further details.

The program should output for the testing data which sense (integer) it regards the example as (one per line).  Your program should not output any additional information. The training and testing data will guarantee a context of at least 5 "orthographic words" to the left and right of the test word, but note that punctuation marks, function words, etc. can all count as orthographic words, and that in some cases we have padded the document with the “dummy” words “xtrainx” in order to achieve this 5 word context. You may choose to ignore these dummy words. The test word will be present at least once in each line. Even if the word appears more than once in the line, you should still disambiguate the occurrence marked with an underscore.

Note: The data provided is from the Senseval competitions. We will be using further data from these competitions to test your programs. It is our intention that this data is previously unseen; therefore, it will be considered an honor code violation to seek out and use extra Senseval data when creating your program. You should use only the WSD data provided (but feel free to use other lexical or corpus resources, such as newswire, wordnet, etc.)

Submission Instructions

For the final submission, you need to submit both your program (electronically) and a written report. Details for the report are found at the end of this handout.

Submission of the program code will be via a script.  To submit your program, put all the needed files (including all source files, scripts and a Makefile, if necessary) in one directory on a Sweet Hall machine (or, possibly, another machine with AFS on it and with you being correctly authenticated) and, from that directory, type:

	/afs/ir/class/cs224n/bin/submit-wsdp

If you need to resubmit it type
	/afs/ir/class/cs224n/bin/submit-wsdp -replace

You should include a Unix shell scripts named runwsd that compile and run your program when executed. The script should take two arguments: the first argument is the name of the training file, and the second argument is the name of the test file. The output for runwsd should be a list of word senses (integers), one per line, corresponding to each line of the test data. 

runwsd should run the word sense disambiguation program  There is a  sample shell scripts in the wsdp/src/ directory called runwsd. Note that on a single run of the word sense disambiguation program, it will be disambiguating only one word.

We will be running programs on further unseen data on the Sweet Hall systems, and your program should run without problems there.  

The program can be written in a language of your choice, but Java is recommended, as we will only answer questions about Java code. In addition, there are some helper files available only in Java. 

The Report

The report should detail the method used by your program, the architecture of your program, testing you did, dead-end paths, and model revisions you pursued.  What we're looking for in the grading is:

•	A clear discussion of the algorithms/method used.
•	A discussion of the testing you did and results you obtained.  If you redivided the provided data into training and testing portions, mention it in the report.
•	Data analysis, especially of errors, and insights you gained from that which you used to improve your program.
•	Experiments and observations on the strengths and weaknesses of the machine learning technique(s) that you implemented.
•	A discussion of alternatives or things you tried to improve performance, and how they fared.
•	The performance of the system: it should perform decently above baseline performance (that simply assigns the most frequent sense in the training data to each word).
•	Clean, intelligible code.
•	Concise, clear reporting is highly preferred. Lengthy, rambling explanations is highly undesirable. 
•	
•	And in particular a clear (but brief) statement in answer to the following questions:
•	
•	Question 1. The WSD program works better at disambiguating some words than others. What are the factors that seem to be determining performance, and what is their relative weight?
•	
•	Question 2. Discuss the machine learning technique(s) that you implemented. If you implemented more than one, did they perform well on the same test sets? Did they depend on the amount of training data available? What were the major differences between the methods?
•	
•	The report shouldn't be longer than 4 pages, but it should be only as long as needed.
•	
•	Contest!
•	
•	We will run your systems on other test data.  We will award a prize and bonus points of up to 10% to the best performing system or systems!  (For this contest, we’re just going to look at how systems perform on our data - we’re not going to test whether superiority of one system over another is statistically significant.)  But please note that in general there isn’t a linear relationship between performance and your grade.  In general, we expect reasonable above baseline performance, but your grade is more dependent on the quality of your thinking and write-up than on the exact performance figure.  For example, we would look favorably on someone who proposes a sensible-sounding different approach to word sense disambiguation, tries it out and who finds out that it doesn’t work that well in practice.
•	
•	As an example system, a baseline contestant (written in Perl) is available in 
•	
•	  /afs/ir/class/cs224n/wsdp/baseline.pl
•	
•	It always returns the most frequent sense in the training data (or sense 1 if no tagged training data is read in).  It takes two arguments, the training and testing files. You can run it on some of the data using the commands below:
•		
•	  cd /afs/ir/class/cs224n/wsdp/
•	  perl ./baseline.pl wsd/bar.train wsd/bar.test 
•	
•	To evaluate how well it does, try:
•	
•	  perl ./baseline.pl wsd/bar.train wsd/bar.test | perl ./eval.pl bar.ans
•	
•	The script eval.pl compares the output of a system (a list of senses, one on each line) with the real answers (stored in the .ans file) and provides a confusion matrix for your results. You can use this script to evaluate your own system, if you would like.
•	
•	Basic Methods  
•	
•	We have specifically chosen the word data given to you to represent the range in the amount of training data we will provide for each word during evaluation. You will notice that some words have more training data than others; some machine learning techniques may work well with larger amounts of training data, but poorly with the kind of data we have. Experiment with these considerations before choosing your algorithms.
•	
•	Here are some of the kinds of methods that you could start off with:
•	
•	1. A straight implementation of a Naive Bayes bag-of-words-based method of the kind used by Gale, Church, and Yarowsky (Section 7.2.1 of the text.)
•	
•	2. An n-gram word model.  (Two things that suggest that this method does not perform too horribly are (i) Kaplan (1950) found that humans were almost as good at disambiguation having seen only one or two words on each side as the whole sentence, and (ii) about half of the decision list items in Yarowsky's (1995) approach appear to involve adjacent words (based on his examples).)
•	
•	3. Using a naive Bayes model based on a thesaurus (Sec 7.3.2). It's not the one that Yarowsky/AT&T used, but a slightly extended version of the 1911 (!) printing of Roget's thesaurus (which is in the public domain) is contained in: 
•	
•		/afs/ir/class/cs224n/wsdp/roget13a.txt
•	
•	However, it would need a certain amount of parsing up....
•	
•	4. Using a vector space model of contexts -- a method widely used in Information Retrieval for measuring contextual similarity.  Such vector space measures are discussed in both Section 8.5 and Chapter 15 of M&S.
•	
•	5. A Bernoulli Naive Bayes model based on word presence/absence in the context rather than the model in Section 7.2.1 which uses a multinomial distribution over each word that does appear in the context.  If you use this method, you probably need to do feature selection to achieve decent results.  Mutual information between context words and senses can be used to identify good features.
•	
•	6. Using a memory-based learning / k-nearest neighbor approach.
•	
•	7. Other ideas in Chapter 7 of M&S, or papers cited there, such as the review of WSD systems in Computational Linguistics (Ide and Veronis 1998).
•	
•	8. Any other supervised machine learning method with which you are familiar.
•	
•	Things to think about:
•	
•	Using prior probability of senses
•	Combining models
•	Using word classes
•	If you multiply too many probabilities, the numbers get too small and become zero on a computer. You should probably use logs and add them (as in equation (7.5) for Naive Bayes). 
•	Probabilities frequently need smoothing.  Zero probabilities are very harmful, since they say something is impossible. Even if you didn't happen to see a word in the context of a certain sense, you probably wouldn't want to say that that occurrence is impossible. The simplest method of 	smoothing is the "add one" method, which you can find in Section 6.2.2.  In it, you add one to each count, and then add the size of the vocabulary to the denominator (so that things are normalized and probabilities that sum to 1 still result). However, you may want to try using other smoothing methods to see if they improve your performance.

If there are other natural language process lexical resources or tools that you'd like to try incorporating, feel free to ask if they're available.  There are a bunch of morphological analyzers, language model tools, and textual data that we could also make available.