Homework 6: Information Theory

_Due: Tuesday, November 3 at 11:59 PM _

Overview

In this homework, you will use entropy in two ways: to encode text using variable-length binary codes, and to identify informative features in a labeled dataset. You will implement Shannon encoding, calculate conditional entropy and information gain, and compare feature selection by information gain with feature selection by training accuracy.

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

• estimate a character probability distribution from text;
• construct a Shannon code and encode and decode messages;
• calculate entropy and the expected length of a code;
• calculate conditional entropy and information gain; and
• explain why information gain and classification accuracy can favor different features.

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

Getting started

The assignment uses the following starter files and datasets. Use the HW06 starter materials distributed through Piazza.

Shannon.py
encode_decode.py
Partition.py
best_feature.py
test_hw06.py
README.md
HW06_written_problems.pdf
HW06_written_problems.tex
data/
  vaccine_tweets_codes_source.csv
  vaccine_tweets_to_encode.csv
  secrete_message_to_decode.txt
  tennis_train.arff
  movies_train.arff
  heart_train.arff
  diabetes_train.arff

The input filename secrete_message_to_decode.txt preserves the spelling in the original materials. The output filename is secret_message_decoded.txt.

Implement the encoding and information-theory calculations yourself. Do not use library implementations of Shannon coding, entropy, or information gain. Standard Python tools for file handling, sorting, counting, and logarithms are allowed.

Keep reusable calculations in functions or methods, with type annotations for their parameters and return values. Importing a module must not run the experiments; call each program’s main() beneath an if __name__ == "__main__": guard.

Implement the NotImplementedError stubs in Shannon.py, Partition.py, and process_contents(contents: str) -> dict[str, float] in encode_decode.py. File helpers, ARFF preprocessing, argument parsing, and experiment drivers are provided. Keep the supplied signatures and read their docstrings for error handling and edge cases. Use Python 3.9 or newer.

Shannon.get_binary_codes() returns a copy of the codebook, and expected_length() returns its probability-weighted bits per character. Partition exposes entropy(), conditional_entropy(feature), information_gain(feature), classification_accuracy(feature), best_feature(), and best_feature_by_accuracy() for independent testing. The reader uses labels -1/+1 and converts numeric features to string-valued threshold indicators. Selection by accuracy uses the same first-feature tie rule.

Run python3 -m unittest -v test_hw06 from the homework directory. These 20 public checks illustrate the contracts and intentionally fail until the TODOs are implemented; passing them does not replace checking all four datasets.

Use base-2 logarithms throughout this homework, so entropy and code lengths are measured in bits. This differs from HW05’s natural-log scores.

Written component

Complete the written worksheet covering information content, entropy, Shannon code construction, prefix-free decoding, information gain, feature selection, and runtime analysis. The starter materials include:

• HW06_written_problems.pdf, which you may print and complete by hand; and
• HW06_written_problems.tex, which you may edit to typeset your answers.

Choose one approach. Show your work and clearly label final answers. Use base-2 logarithms and report entropy and information gain in bits. A calculator is allowed; do not use Python or another programming language to solve the written problems.

Scan handwritten answers into one legible PDF, or compile your completed LaTeX source. Name the finished file HW06_written_problems.pdf and include it with your Gradescope submission.

Part 1: Shannon encoding

Work in Shannon.py and encode_decode.py. You will construct a codebook from one source text and use that same codebook to encode and decode other messages.

Background: why use different numbers of bits?

An encoding assigns a bit string, called a codeword, to each character. Encoding a message means replacing its characters with their codewords; decoding reverses that process. This is lossless compression: the goal is to recover the original message exactly, not to hide its contents.

A fixed-length code for four characters could use 00, 01, 10, and 11, spending two bits on every character. If some characters occur much more often than others, we can instead give frequent characters shorter codewords and rare characters longer ones. What matters is the average number of bits, weighted by how often each character appears.

The information content of a character with probability p is -log2(p) bits. A character occurring half the time has information content 1 bit; one occurring one eighth of the time has information content 3 bits. Entropy is the average information content across the character distribution:

H(C) = sum over characters c of p(c) * (-log2(p(c)))

Shannon encoding turns these possibly fractional information values into whole-number codeword lengths, then assigns bit strings of those lengths. The construction below is all you need for this assignment; no prior coverage of Shannon encoding is assumed.

Prefix-free codes: decoding without separators

Different-length codewords must have recognizable boundaries. Consider A → 0 and B → 01. Here the codeword for A is the beginning of the codeword for B, so reading a 0 does not immediately tell you whether to output A or wait for another bit.

A prefix-free code avoids this problem: no complete codeword is the beginning of another codeword. For example:

C → 0      A → 10      B → 110      D → 111

Reading from left to right, you can emit a character as soon as a complete codeword is recognized, then start again. No separator bits are necessary. The boundaries in 10 | 110 | 0 | 111 reveal the message ABCD; the actual encoded string is just 101100111.

Construct a Shannon codebook

Use the cumulative-probability construction below. Start with a nonempty character-probability dictionary whose values are positive and sum to one. For now, assume it contains at least two distinct characters.

1. Sort the characters from most probable to least probable. For equal probabilities, preserve their order in the input dictionary. When building that dictionary from text, insert characters in first-occurrence order.
2. For each character, calculate L = ceil(-log2(p)). The ceiling rounds up to the nearest integer. For instance, p = 0.3 gives -log2(p) ≈ 1.737, so L = 2.
3. Calculate q, the sum of the probabilities of all characters before the current character in the sorted order. The first character has q = 0. Do not include the current character’s probability yet.
4. Write q as a binary fraction and take its first L digits after the binary point. Those digits are the codeword. Keep leading zeros and append trailing zeros if the binary expansion terminates early.
5. Store the character/codeword pair, add the current probability to the cumulative sum, and continue to the next character.

Sorting, using the cumulative probability before the current character, and retaining the prescribed number of digits are all necessary parts of this construction. The result is prefix-free. This is Shannon’s cumulative construction, not the recursive splitting algorithm sometimes called Shannon–Fano coding. See the source-coding discussion in Shannon’s original paper for additional background; reading the paper is optional.

How to obtain digits of a binary fraction

Binary places after the point have values 1/2, 1/4, 1/8, and so on. For example, 0.101 in binary means 1/2 + 0/4 + 1/8 = 0.625.

You can generate the first L digits of q without a special conversion library. Start with a remainder equal to q. Repeat the following L times:

• double the remainder;
• record its integer part, which will be 0 or 1; and
• subtract that integer part to obtain the next remainder.

For q = 0.625 and L = 3:

The resulting digits are 101. If the remainder becomes zero before you have L digits, the remaining digits are zeros.

An equivalent approach is to compute the integer floor(q * 2**L) and write it in binary using exactly L digits, padding on the left with zeros. Truncate rather than round. For example, q = 0.4 and L = 2 gives floor(1.6) = 1, whose two-digit representation is 01, not 1. Python’s bin() accepts an integer, not a fractional probability, and its 0b prefix is not part of a codeword.

Worked example: from probabilities to codewords

Suppose the input probabilities are A: 1/4, B: 1/8, C: 1/2, and D: 1/8. Sorting gives C, A, B, D; the tied characters B and D keep their input order.

For B, the cumulative probability is 1/2 + 1/4 = 3/4, whose binary expansion is 0.11000…. Keeping three digits produces 110. This is why the cumulative sum, rather than the character’s own probability, determines its particular bit string.

The expected codeword length is:

(1/2 × 1) + (1/4 × 2) + (1/8 × 3) + (1/8 × 3) = 1.75 bits/character

For this distribution, that is shorter than the two-bit fixed-length code. This comparison counts the message bits and assumes the codebook is already shared; storing or transmitting the codebook would add overhead. It also equals the entropy because all the information contents are already integers. For other distributions, rounding the lengths up can add some cost; Shannon’s expected length is at least the entropy and less than one bit above it.

This is an expectation under the source distribution, not a promise that every particular message gets shorter. A message containing only Ds would use three bits per character with this codebook.

Implement the Shannon class

The constructor should receive a dictionary mapping characters to their probabilities. The encoding and decoding methods should accept and return strings:

class Shannon:
    def __init__(self, char_probs: dict[str, float]) -> None:
        ...

    def encode(self, text: str) -> str:
        ...

    def decode(self, bits: str) -> str:
        ...

Construct and store the codebook during initialization using the steps above. You may find math.log2, math.ceil, sorting, and dictionaries useful. Implement the construction and your helper methods yourself. Keep codewords as strings so that leading zeros are preserved. Do not round the probabilities or cumulative sums for display before using them to construct codewords; rounding can change the resulting bits.

Do not rebuild a different codebook for each input message. The decoder must use exactly the encoder’s character probabilities and tie ordering. If a supplied message was created with a different ordering convention, follow its accompanying starter instructions so that the codebooks match.

For this example:

char_probs = {"A": 0.25, "B": 0.125, "C": 0.5, "D": 0.125}
shannon = Shannon(char_probs)

the reference codebook is:

{"A": "10", "B": "110", "C": "0", "D": "111"}

Check that encode("ABCD") returns "101100111" and that decoding those bits returns "ABCD". Then verify a longer round trip:

original = "ABAACDDBACCDAAABDBBABCDDCBA"
encoded = shannon.encode(original)
decoded = shannon.decode(encoded)
assert decoded == original

Decode one codeword at a time

For encoding, look up each input character’s codeword and concatenate the results. For decoding, a reverse dictionary maps complete codewords back to characters. Keep a buffer that is initially empty:

1. Add the next input bit to the buffer.
2. If the buffer matches a complete codeword, emit the corresponding character and clear the buffer.
3. Otherwise, keep reading bits until a complete codeword is recognized.

With the example codebook, reading 1 is not enough to emit anything; reading 10 completes A. The prefix-free property guarantees that you will not need to undo a completed match. A decoding tree is another valid implementation: follow a branch for each bit, emit a character at a leaf, and return to the root.

The recovered text must match exactly, including spaces, punctuation, and line breaks. Treat an unrecognized character, a nonbinary input digit, an impossible prefix, or an incomplete codeword left at the end as an error; do not silently discard it. Encoding or decoding an empty message should return an empty string.

For a source alphabet containing just one character, the length formula would produce zero bits and lose the number of repetitions. Use the one-bit codeword 0 for that special case. An empty source cannot supply a probability distribution. The tweet source has many distinct characters, so neither special case affects its expected-length comparison.

Estimate character probabilities

In encode_decode.py, read data/vaccine_tweets_codes_source.csv as one long string, using the supplied read_file() helper with encoding ISO-8859-1. Although the filename ends in .csv, this part treats it as raw text rather than a table of records.

Write a function that counts characters and converts their counts into probabilities:

P(character) = occurrences of that character / total characters

Count all characters, including spaces and newlines. Do not strip whitespace or discard punctuation. Check that your probabilities sum to approximately one. In the source dataset, space should be the most common character, followed by e.

Create one Shannon instance from this distribution. The source text supplies the codebook; the smaller message to encode does not supply a new probability distribution.

Encode the tweets and decode the secret message

Your program should perform these steps:

1. Read data/vaccine_tweets_to_encode.csv with ISO-8859-1 and encode the complete text using the source codebook.
2. Create output/ if needed, and use write_file() with its default encoding to save the bit string as output/vaccine_tweets_encoded.txt.
3. Read data/secrete_message_to_decode.txt using the helper’s default encoding. Decode it using the same codebook and save the result as output/secret_message_decoded.txt.
4. Decode your own encoded tweets and verify that they exactly match the original input text. Also inspect the decoded secret message: it should be readable text.

The provided driver uses these paths by default and accepts --source, --message, --secret, and --output-dir overrides. Run the experiment from the homework folder:

python3 encode_decode.py

The encoded file is a textual representation of bits: it contains the characters 0 and 1. Its file size on disk is not the size of a packed binary encoding. Use codeword lengths when calculating bits per character.

Part 2: Selecting informative features

Work in Partition.py and best_feature.py. This part uses the tennis, movies, heart disease, and diabetes datasets. The medical datasets originate from the UCI Machine Learning Repository; the original lab uses ARFF versions prepared by Mark Craven at the University of Wisconsin.

Use the supplied ARFF reader and its conversion of continuous features into categories. Inspect how it represents labels and feature values before implementing your calculations. Use only training data to select features.

Calculate entropy

Begin with a method for the entropy of the class label Y:

H(Y) = -sum over classes k of P(Y = k) * log2(P(Y = k))

Estimate class probabilities from their frequencies in the partition. A class with probability zero contributes zero to entropy; skip that term rather than evaluating log2(0). Do not apply HW05’s Laplace smoothing here: these calculations use the observed class proportions.

Useful checks are:

• a partition containing only one class has entropy 0;
• two equally common classes have entropy 1 bit; and
• a binary class distribution has entropy between 0 and 1 bit.

Calculate conditional entropy and information gain

For a categorical feature X, split the partition by feature value. Compute the label entropy within each nonempty group, then weight each group’s entropy by its fraction of all examples:

H(Y | X) = sum over values v of P(X = v) * H(Y | X = v)
IG(Y, X) = H(Y) - H(Y | X)

Use each group’s own size when computing its class proportions. Use the full partition’s size when computing its weight. Do not take an unweighted average of group entropies unless all group sizes are equal. A possible feature value with no examples contributes zero to the weighted sum.

Implement best_feature() inside Partition. It should compute the information gain for each feature and return the name of a feature with the largest gain. Use helper methods for the intermediate calculations so you can check them independently. If gains tie exactly, choose the first feature in the partition’s feature order, including when all gains are zero.

Run and check feature selection

The provided parse_args() and main() in best_feature.py accept the required -r/--train_filename argument and print each feature’s information gain, training accuracy, and the selected features. Implement the calculations in Partition.py; keep them free of printing and interactive prompts.

python3 best_feature.py -r data/tennis_train.arff
python3 best_feature.py -r data/movies_train.arff
python3 best_feature.py -r data/heart_train.arff
python3 best_feature.py -r data/diabetes_train.arff

The original lab provides these reference values, rounded to six decimal places. Small floating-point differences are acceptable.

The selected tennis feature should be Outlook.

The selected movies feature should be Director.

Compare with classification accuracy

Add a separate method to Partition that selects a feature by its single-feature training accuracy. For each candidate feature:

1. Group the training examples by that feature’s value.
2. Assign each group its majority class label.
3. Count how many training examples those group predictions classify correctly, and divide by the total number of training examples.

Equivalently, each group contributes the count of its most frequent class to the number of correct predictions. A tie between majority labels does not change that group’s number of correct predictions.

Calculate and print this accuracy for every feature, and identify the feature that maximizes it. Document how you resolve ties between features. Run both feature-selection methods on all four datasets and save the results in README.md.

These are training accuracies used to compare selection criteria. They are not held-out estimates of a model’s performance on new examples.

Part 3: Analysis

Answer the following questions in README.md:

1. What is the expected number of bits per character for your source-based Shannon code? Compute sum(p(c) * length(code(c))) using the source character probabilities. Is this higher or lower than you expected? Explain what you used as a comparison. As a check, compare the expected length with the source entropy: a Shannon code satisfies H(C) <= expected length < H(C) + 1 for this nontrivial source alphabet.
2. For each of tennis, movies, heart, and diabetes, report the feature selected by information gain, its gain, the feature selected by training accuracy, and its accuracy. Include any ties. Did the two criteria ever select different features? Explain your results for each dataset, considering the class distributions within the feature-value groups.

Complete the short, ungraded questionnaire in the starter README as well.

Submission

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

Shannon.py
encode_decode.py
Partition.py
best_feature.py
test_hw06.py
README.md
HW06_written_problems.pdf
output/
  vaccine_tweets_encoded.txt
  secret_message_decoded.txt

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

Before submitting:

• verify the small reference codebook and both encoding/decoding round trips;
• regenerate both required output files and inspect the decoded message;
• check that character probabilities sum to approximately one;
• use base-2 logarithms and handle zero-probability entropy terms;
• verify the reference information gains for tennis and movies;
• run both feature-selection criteria on all four datasets;
• complete the written worksheet and include HW06_written_problems.pdf;
• complete the analysis in README.md; and
• confirm that importing your modules does not execute the experiments.

Academic integrity

Follow the course collaboration and attribution policies. Submitted code and analysis must be your own unless the assignment is explicitly designated as collaborative. Credit any permitted sources or assistance.