Homework 5: Naive Bayes

Due: Tuesday, October 27 at 11:59 PM EDT

Overview

In this homework you will implement a Naive Bayes classifier for categorical data and investigate how a protected attribute can be encoded in other features. Using a cleaned version of the 1994 Adult Census Income dataset, you will predict the recorded sex attribute from the remaining columns and consider what this reveals about the limits of simply removing protected attributes from a model’s inputs.

By the end of the homework, you should be able to:

• estimate class priors and conditional probabilities from training data;
• implement Naive Bayes for binary and multiclass classification;
• use Laplace smoothing and log probabilities;
• evaluate a classifier against simple baselines; and
• explain redundant encoding and interpret balanced error rate.

Credit: Adapted materials from Thao Nguyen and Sara Mathieson, modified from materials created by Ameet Soni and Allison Gong.

Getting started

Start with the HW05 programming tips for help working with the starter’s data structures, CSV/ARFF readers, probability tables, log scores, and tests.

Download the Homework 5 starter files from Piazza. Your working folder should contain:

NaiveBayes.py
Partition.py
run_NB.py
tests.py
README.md
HW05_written_problems.pdf
HW05_written_problems.tex
data/
  tennis_train.arff
  tennis_test.arff
  zoo_train.arff
  zoo_test.arff
  1994_census_cleaned_train.csv
  1994_census_cleaned_test.csv
  1994_census_cleaned_corrected_train.csv
  1994_census_cleaned_corrected_test.csv

Use Python 3.9 or newer. No third-party packages are required.

Implement the classifier yourself rather than using a library implementation of Naive Bayes. You may reuse your argument parsing and ARFF-reading code from HW04, adapting it to the interfaces and multiclass labels described below. The command-line parser, file-format dispatch, output formatting, and main program are provided. Complete the NotImplementedError placeholders and preserve the supplied type annotations and interfaces.

Keep the model in NaiveBayes.py. Use run_NB.py to read data, train the model, make predictions, and report results. Importing either module must not run the analysis; call main() only beneath an if __name__ == "__main__": guard.

Written component

Complete the included HW05_written_problems.pdf worksheet. Its six sections cover joint and conditional probabilities, Bayes’ rule and base rates, Laplace smoothing, Naive Bayes predictions and log scores, conditional independence, and multiclass prediction and runtime analysis.

You may print and complete the worksheet by hand or typeset your answers in the supplied HW05_written_problems.tex. Show your calculations and clearly label final answers. A calculator is allowed, but do not use Python or another programming language to solve the written problems. Keep exact fractions until the final step or round final decimals to four places.

Submit one legible PDF named HW05_written_problems.pdf, either scanned from your handwritten work or compiled from your completed LaTeX source. These problems are separate from the experiment analysis in README.md.

Part 1: Read the data

Command-line arguments

The provided parse_args(argv=None) in run_NB.py accepts:

• -r/--train_filename: the training-data path; and
• -e/--test_filename: the test-data path.

Both arguments are required. The provided read_data() selects the reader based on the input file extension. For example:

python3 run_NB.py \
    -r data/1994_census_cleaned_train.csv \
    -e data/1994_census_cleaned_test.csv

python3 run_NB.py -r data/zoo_train.arff -e data/zoo_test.arff

Data structures

The starter code defines Example and Partition in Partition.py and imports them into run_NB.py:

• Example.features is a dictionary mapping feature names to values.
• Example.label is an integer in {0, 1, ..., K - 1}.
• Partition.data is a list of examples, and Partition.n is its length.
• Partition.F maps each feature name to its possible values.
• Partition.K is the number of classes.

All input features are discrete and unordered. Treat even numeric-looking feature values as categories. Your model must support any number of classes, including the seven classes in the zoo dataset.

ARFF reader

Complete read_arff(filename) so that it returns a Partition. Read feature names and possible values from the attribute declarations and examples from the data section. The final attribute is the class label.

Unlike HW04, labels must be integers from 0 through K - 1, rather than -1 and +1. Use the declared class values to determine K, and keep the class mapping consistent between training and test data. Test this reader with both the tennis and zoo datasets.

CSV reader

Complete read_csv(filename) so that it also returns a Partition. The first row contains column names. Collect the observed values for each feature in F; CSV files do not provide the attribute declarations found in ARFF files. Python’s csv module is useful here.

For the census files, use sex as the label, with Male represented by 0 and Female by 1. Exclude sex from both Example.features and Partition.F. These are the categories recorded in the supplied dataset. The income column remains an input feature, even though income was the prediction target in the original dataset.

Preserve a consistent feature order when reading the files. A regular Python dictionary preserves insertion order; you may also use OrderedDict.

For the original census files, verify that your reader produces:

num train = 28998, num classes = 2
num test  = 7419, num classes = 2

Fit the model using only the training partition. Do not use test examples to estimate probabilities or choose the majority class.

Part 2: Establish baselines

Before implementing Naive Bayes, answer these questions in README.md:

1. What fractions of the original census training examples are labeled Male and Female?
2. Suppose a classifier independently flips a fair coin for every test example. What is its expected confusion matrix and expected accuracy? Compute expectations rather than reporting a single random simulation; expected matrix entries need not be integers.
3. Suppose a classifier always predicts the majority class from the training data. What confusion matrix and accuracy does it obtain on the test data?

For every confusion matrix, use rows for actual labels and columns for predicted labels. Clearly identify the label order.

Part 3: Implement Naive Bayes

Complete the NaiveBayes class in NaiveBayes.py. Preserve these interfaces:

from Partition import FeatureValues, Partition

class NaiveBayes:
    def __init__(self, partition: Partition) -> None:
        ...

    def predict_log_scores(self, x_test: FeatureValues) -> list[float]:
        ...

    def classify(self, x_test: FeatureValues) -> int:
        ...

    def predict(self, examples: list[FeatureValues]) -> list[int]:
        ...

The constructor receives the training Partition. The classify() method receives one example’s feature dictionary and returns an integer class label. Here FeatureValues means dict[str, str]. Complete the supplied counting and log-probability helper methods as well. You may add other helpers.

Model and smoothing

Naive Bayes assumes that the features are conditionally independent given the class. For each candidate class k, its score is proportional to:

P(y = k) × product over features j of P(x_j | y = k)

Let n be the number of training examples, K the number of classes, N_k the number of training examples in class k, and N_k,j,v the number of training examples in class k whose feature j has value v. Let |F_j| be the number of possible values of feature j.

Use add-one Laplace smoothing for both priors and likelihoods:

P(y = k)           = (N_k + 1) / (n + K)
P(x_j = v | y = k) = (N_k,j,v + 1) / (N_k + |F_j|)

Include every possible value of each feature, even when its count within a particular class is zero.

Train in log space

Compute and store all model probabilities in the constructor, using natural logarithms. Do not recount training examples or recompute probabilities each time you classify a test example.

Store the log priors in log_class[k]. Store likelihoods in log_feature[feature_name][feature_value][k], a nested dictionary whose innermost values are lists indexed by class. These named attributes allow individual training calculations to be tested independently.

Taking a logarithm turns a ratio into a difference of logarithms:

log P(y = k)           = log(N_k + 1) - log(n + K)
log P(x_j = v | y = k) = log(N_k,j,v + 1) - log(N_k + |F_j|)

For the original census training data, the smoothed log priors should be approximately:

[-0.39003307271614496, -1.1302097192251246]

Classify examples

In predict_log_scores(), compute a score for every class:

score(k) = log P(y = k) + sum over features j of log P(x_j | y = k)

Return a list of scores in class order. In classify(), return the class with the largest score, choosing the smallest class label in a tie. You do not need to exponentiate the scores or normalize them into posterior probabilities. Implement predict() to return predictions for a list of feature dictionaries, preserving input order.

Missing required features and values outside the training domain must raise KeyError. Ignore extra feature keys. Do not expand feature domains using test data. The supplied census test values all occur in their corresponding training domains.

The supplied main program trains one model and classifies the test examples. An individual prediction can also be tested directly:

nb_model = NaiveBayes(train_partition)
y_hat = nb_model.classify(example.features)

Complete these independently testable functions in run_NB.py:

def confusion_matrix(y_true: list[int], y_pred: list[int], K: int) -> list[list[int]]:
    ...

def accuracy(y_true: list[int], y_pred: list[int]) -> float:
    ...

def balanced_error_rate(matrix: list[list[int]]) -> float:
    ...

The confusion matrix must contain integer counts in a K by K list of lists. Compute accuracy as the fraction of correct predictions. BER is the mean of the class-specific error rates; see Part 4 for the binary formula. Follow each function’s docstring for empty inputs and invalid arguments.

These functions and the model methods must return values without printing or mutating their inputs. The provided main program prints the confusion matrix, accuracy, correct prediction count, and BER when it is defined.

Check your implementation

Run the public tests from your homework folder:

python3 tests.py

The eight sample tests check readers, smoothing, scores, multiclass predictions, tie breaking, and metrics on small examples. They fail until you complete the relevant methods. Passing them does not guarantee full credit; also test cases of your own and run the complete experiments.

Run the small datasets before the census experiments:

python3 run_NB.py -r data/tennis_train.arff -e data/tennis_test.arff
python3 run_NB.py -r data/zoo_train.arff -e data/zoo_test.arff

The reference results from the original lab are:

For tennis, the confusion matrix is:

                  predicted
                    0   1
actual       0      4   1
             1      0   9

For zoo, the confusion matrix is:

                  predicted
                    0   1   2   3   4   5   6
actual       0     13   0   0   1   0   0   0
             1      0   7   0   0   0   0   0
             2      0   1   0   0   1   0   0
             3      0   0   0   4   0   0   0
             4      0   0   0   0   1   0   0
             5      0   0   0   0   0   3   0
             6      0   0   0   0   0   2   2

Part 4: Census experiments and analysis

Run your model on the original census files, then train a new model and evaluate it using the corrected files:

python3 run_NB.py \
    -r data/1994_census_cleaned_corrected_train.csv \
    -e data/1994_census_cleaned_corrected_test.csv

Answer the following questions in README.md. Include the confusion matrix and accuracy for each census experiment.

1. Temporarily remove the Laplace smoothing counts and run the original census experiment again. What error, warning, or non-finite log value do you encounter? What does it tell you about the data? Restore smoothing before completing the remaining experiments and submitting your code.
2. How accurate is Naive Bayes at predicting the recorded sex attribute in the original census test data? Compare it with both baselines from Part 2.
3. What accuracy do you obtain on the corrected census data? Inspect the files, explain what differs between the original and corrected datasets, and discuss why the resulting change in accuracy makes sense.

4. Compute the balanced error rate (BER) on the corrected census test data. For this binary problem, BER is the mean of the two class-specific error rates. Taking class 1 as positive:

   BER = 0.5 × (FP / (FP + TN) + FN / (FN + TP))
   

   Show your calculation and interpret the result. What does BER tell you that overall accuracy alone may obscure when class sizes differ?

5. What concerns arise when other features predict a protected attribute, even with a model that assumes conditional independence? If the intended prediction were whether to hire someone, how would you address redundant encoding of protected attributes? Explain why excluding the protected column alone may be insufficient. Distinguish evidence of predictability from a conclusion that a particular hiring model is fair or unfair.

Complete the short, ungraded questionnaire at the end of README.md as well.

Optional extensions

• Propose a method to identify the features, or particular feature values, that are most predictive of the recorded sex attribute. Describe your strategy and, optionally, implement it and report results.
• Explain how you could adapt Naive Bayes to continuous features. You may also implement your approach.

Document any extension in README.md and keep the required categorical classifier usable with the supplied datasets.

Submission

Submit one .zip file to the HW05 assignment on Gradescope containing:

NaiveBayes.py
Partition.py
run_NB.py
README.md
HW05_written_problems.pdf

Include any additional helper modules needed to run your code. You do not need to include data/ unless Gradescope’s submission instructions explicitly request it.

Before submitting:

• run your program on tennis, zoo, and both census dataset pairs;
• check the original census partition sizes and smoothed log priors;
• verify that your model supports multiclass labels;
• verify that smoothing is enabled and probabilities are stored in log space;
• label confusion-matrix rows and columns clearly;
• answer all Part 2 and Part 4 questions in README.md;
• complete the written worksheet and include HW05_written_problems.pdf; and
• confirm that importing either module does not run the analysis.

Academic integrity

Follow the course collaboration and attribution policies. You may discuss approaches at the level permitted by the course policy, but submitted code and analysis must be your own unless the assignment is explicitly designated as collaborative. Credit any permitted sources or assistance.