Department of Computer Science and Engineering
University of California, San Diego
CSE 254
Spring 2007

Assignment 1

DUE AT THE START OF CLASS ON TUESDAY APRIL 24, 2007


Important: Please use this discussion board to ask questions.

 This assignment is a warm-up project for the main project for 254.  The objective, like for the main project, is to reproduce results from a published paper.  The particular paper to follow now is Supervised naive Bayes parameters by H. Wettig, P. Grünwald, T. Roos, P. Myllymäki, and H. Tirri, published in Proceedings of the tenth Finnish artificial intelligence conference, 2002.  

Specifically, you should try to reproduce some of the results in Table 1.  Choose three to six datasets that you expect to be particularly informative.  Implement standard naive Bayes and discriminatively trained naive Bayes, as described in the tutorial by Klein and Manning.  Use the discretized datasets available at http://www.cs.helsinki.fi/u/pkontkan/Data/ and write your code in Matlab.  For this project, you do not need to replicate the methods of Tirri et al. precisely.  In particular, you may use a different numerical optimization algorithm, different regularization, and a different crossvalidation procedure.

Answer some or all of the following questions:

(1) Is the discriminatively trained naive Bayes of Klein and Manning exactly the same as the "supervised NB" of Wettig et al.?  The answer is not immediately clear, because the notation in the paper by Wettig et al. is rather complicated.  The results in this 2002 paper are a special case of those in a later paper, On Discriminative Bayesian Network Classifiers and Logistic Regression by T. Roos, H. Wettig, P. Grünwald, P. Myllymäki, and H. Tirri, Machine Learning 59:3, pp. 267-296 (2005), which uses simpler notation.

(2) Compare pseudocount smoothing for standard naive Bayes and L2 regularization (i.e. a Gaussian prior on parameters) for discriminative naive Bayes.  Note that making each pseudocount be 1 is called Laplace smoothing.  Often this is excessive smoothing and sometimes 0.1 is recommended instead of 1.  Investigate this issue.  For discriminative NB, investigate what the optimal strength of the prior is.

(3) Compare different nonlinear optimization algorithms for discriminative naive Bayes training.  For software choices see here.

(4) Compare standard and discriminative NB according to multiple loss functions: 0/1 accuracy, mean squared error, log loss, and/or area under the ROC curve.  Compare the two NB methods with and without calibration, i.e. with and without adjusting their output scores to be well-calibrated probability values.  (Note:  You can find a Matlab function for calibration in the Spider toolbox.)  Optional:  Try different loss functions as the objective for discriminative training.

What to submit.  To quote Sanjoy Dasgupta, "Discuss your results in precise and lucid prose.  Content is king, but looks matter too!"  For further advice, see the article Crafting Papers on Machine Learning by Pat Langley and Three Sins of Authors in Computer Science and Math by Jonathan Shewchuk.