CS 539 Spring 2007

Computer Science Department

CS539 Machine Learning - Spring 2007
Project 5 - Bayesian Learning

PROF. CAROLINA RUIZ

Due Date: Tuesday March 13, 2007. Slides are due at 3:00 pm and the written report is due at 4:00 pm.

Project Description
Project Assignment
Report Submission and Due Date

PROJECT DESCRIPTION

Experiment with Naive Bayes and Bayesian Net classifiers for each of the following problems:

Predicting the class attribute in the Covertype data available at the UCI Machine Learning Repository.
Predicting whether the income of a given person is >50K or <= 50K using the census-income dataset from the US Census Bureau which is available at the Univ. of California Irvine Repository.
The census-income dataset contains census information for 48,842 people. It has 14 attributes for each person (age, workclass, fnlwgt, education, education-num, marital-status, occupation, relationship, race, sex, capital-gain, capital-loss, hours-per-week, and native-country) and a boolean attribute class classifying the input of the person as belonging to one of two categories >50K, <=50K.
A dataset of your choice. This dataset can consist of data that you use for your own research or work, a dataset taken from a public data repository (e.g., UCI Machine Learning Repository, or from the UCI KDD Archive), or data that you collect from public data sources. THIS DATASET SHOULD BE LARGE IN TERMS OF THE NUMBER OF INSTANCES AND ATTRIBUTES SO IT CANNOT BE ONE OF THOSE INCLUDED IN THE WEKA SYSTEM.

PROJECT ASSIGNMENT

Read Sections 6.1, 6.2, 6.7, 6.8, 6.9, 6.10, 6.11, 6.12, 6.13 of your textbook in great detail.

Solve Exercises 6.1, and 6.6 of your textbook (pages 198-199). Include your solution in your written report (and not in your oral report).

Read the NaiveBayes and the BayesNets code in the Weka system.

The following are guidelines for the construction of your Naive Bayes and Bayesian Net Classifiers:
- Algorithm Options:
  
  Naive Bayes: Run experiments with and without the supervised discretization option. Contrast the results obtained.
  Bayesian Nets: Run experiments with different search methods (including at least K2 and HillClimber), different upper bounds on the number of parents, and different orderings of the predicting attributes. For a description of the K2 algorithm see G. F. Cooper & E. Herskovits. "A Bayesian Method for the Induction of Probabilistic Networks from Data". For an illustration of the K2 algorithm over the toy dataset in that paper, see Prof. Ruiz's K2 handout
- Evaluation and Testing: Use n-fold cross-validation.
- Comparison of the Algorithms:
- Use stratified sampling to select a subset S of 1000 data instances from the Cover Type dataset. Piotr's script can be used for this purpose - thanks Piotr! or you can load the entire dataset into Weka and use the Sampling filter.
  1. Learn a Naive Bayes model m with the best parameters settings you can over S using a 75% split. That is, use 75% of the data in S to build the model and the remaining 25% to calculate the error_S(m). Use this error_S(m) to estimate the 95% confidence interval of the error_D(m) (i.e., the error of t over the entire distribution D of cover type instances).
  2. Learn a Bayesian network Bn (with the best parameters settings you can) with default parameters over the dataset S using a 75% split. That is, use 75% of the data in S to build the net and the remaining 25% to calculate the error_S(Bn). Compare the Naive Bayes model m from above and the Bayesian network Bn by estimating the 95% confidence interval of the difference d between the true errors of these two hypotheses using error_S(t) and error_S(Bn).
  3. Compare Naive Bayes and Bayesian Nets over the Cover Type dataset by estimating the difference in error between these two learning methods over the Cover Type dataset with an approximate confidence interval of 95%. Do this by using a paired t test with k=11 with the data subset S from above as D₀. Show your work and all calculations on the written report.

REPORT AND DUE DATE

Written Report.
Your report should contain the following sections with the corresponding discussions:
1. Algorithm Description: Describe IN YOUR OWN WORDS the Naive Bayes algorithm and the K2 Bayesian Net learning algorithm. Explain each algorithm in terms of the input it receives, the output it produces, and the main steps it follows to produce this output from the input.
2. Data: Describe the dataset that you selected in terms of the attributes present in the data, the number of instances, missing values, and other relevant characteristics.
  Provide a detail description of the preprocessing of your data. Justify the preprocessing you apply and why the resulting data is the appropriate one for each experiment you run.
  Describe your 3-5 guiding questions/conjectures.
3. Experiments: For each experiment you ran describe:
  - Which of your 3-5 specific questions/conjectures about the dataset domain you aim to answer/validate with your experiments.
  - Data: What data did you use to construct and test your classifier?
  - Any additional pre or post processing done to the data or the classifier's output in order to improve the accuracy of your classifier.
  - Accuracy of the resulting classifier.
  - Comment on the structure (or topology) of the resulting Bayesian nets.
  - What was the answer that this experiment provided to your guiding question(s)?
4. Comparison of the Algorithms: Include the results of the comparisons between the approximate errors of Naive Bayes and Bayesian Nets over the CoverType data as described above. Remember to show your work and all the calculations.
5. Summary of Results
  - For each dataset, what was the accuracy of the most accurate classifier constructed in your project?
  - Discuss how this accuracy compares with that of your most accurate ZeroR experiment, decision trees, and neural nets from the previous assignments (on the datasets that are in common between this and previous assignments).
  - Strengths and the Weaknesses of _your_ project.
Oral Report. We will discuss the results from the individual projects during the class on March 13th. Your oral report should summarize the different sections of your written report as described above. Each of you will have 5 minutes to explain your results and to discuss your project in class. Be prepared!
Submission and Due Date.
1. Please submit the following file by email by Tuesday March 13 at 3:00 pm.
2. [your-lastname]_proj5_slides.[ext] containing your slides for your oral report. This file should be either a PDF file (ext=pdf) or a PowerPoint file (ext=ppt). Please use only lower case letters in the name file. For instance my file would be named ruiz_proj5_slides.ppt
3. Please bring a hardcopy of your report to class on March 13, 2007.

CS539 Machine Learning - Spring 2007 Project 5 - Bayesian Learning

PROF. CAROLINA RUIZ

PROJECT DESCRIPTION

PROJECT ASSIGNMENT

REPORT AND DUE DATE

CS539 Machine Learning - Spring 2007
Project 5 - Bayesian Learning