Phase 8: Using Your HashMultiset<T> to Finish the Machine Learning Code

At this point, you should have a fully working HashMultiset<T> implementation. So now, at long last, we can return to the machine learning demo code and use your HashMultiset<T> to implement the actual, well, learning part of the code!

In this phase, we'll be mainly working with the files nbclassifier.hpp and nbclassifier.cpp, which together define an NBClassifier class. You will see that the vast majority of the code is already provided for you. There are only two TODOs left for you to fill in: one in the fit function (which implements training) and one in the transform function (which implements running the trained model, and is called both in evaluation mode and interactive mode).

Both TODOs relate to the part of the algorithm that counts features and computes probabilities, because that's where a multiset comes in handy. Specifically, NBClassifier contains a private member variable classFeatureCounts_ whose type is HashMultiset<std::string>. For the TODOs, we basically just stripped out all the code that uses classFeatureCounts_ and we're having you fill it back in.

Background: What Probabilities are we Computing?

Recall from Phase 1 that our machine learning approach is based on the probability of each feature in a given class. For example, the algorithm needs to know: "how likely is the feature "eon" to appear in a Pokemon name?" and also "how likely is the feature "eon" to appear in a software/app/tech-startup name?"

Suppose you've counted how many times "eon" appears in all Pokemon names. How do you then turn that into a probability? Well, you need to know how that count compares to the count of all other features in Pokemon names. In other words, you should divide this count by the sum of all the counts:

$$ P(\mathrm{eon}|\mathrm{Pokemon}) = \frac{\text{# of times "eon" appears in all Pokemon names}}{\text{Sum of the counts of all features in all Pokemon names}} $$

More generally, for any feature \( f \in F \) (where \( F \) is the set of all features) and class \( c \):

$$ P(f|c) = \frac{\text{# of times } f \text{ appears in examples labeled } c}{\sum_{f' \in F}\text{# of times } f' \text{ appears in examples labeled } c} $$

So, your job in this phase is twofold: store the necessary counts (as seen in the equation above) in classFeatureCounts_, and then implement a function to turn those counts into probabilities (using the above equation).

Perhaps the most "proper" way to keep track of the counts is by keeping a vector of multisets, one for each class. But we didn't want to overcomplicate the code, since that would distract from the learning goal of getting familiar with using hash tables.

Instead, we'll use a bit of a trick: modifying the key itself before we insert it. One way to distinguish between "'eon' in Pokemon" and "'eon' in software" is by adding the class label as a suffix. So, we'll use the key "eon|Pokemon" to store the count of the feature "eon" in the "Pokemon" class (and likewise for the "software" class with "eon|software"). We've provided a helper function formatFeature(feature, class) that does this suffixing for you. For example, calling formatFeature("eon", "software"); returns "eon|software".

We'll use a similar trick to streamline computing the denominator in the above equation. Naively, taking the sum of the counts of all features requires looping over all features and summing their counts (that is, after all, how the equation is written). But that's a lot of work and again makes the code more complicated. The trick is that we can iteratively update the total while we're counting features! Every time we increment the count of a feature f|c, we can ALSO increment the count of a "fake" feature "ANY"|c. By doing this, when we're done counting features, the key "ANY|Pokemon" will contain the sum total of feature counts in the "Pokemon" class, and likewise for "software" with the key "ANY|software".

Now that you know what to count and what to compute, let's actually do it!

Your Task, Part A: Count Features in fit

The fit function already contains a loop over features feat and class labels label. In the body of the loop there is a TODO where you need to use these variables to increment the necessary counts in classFeatureCounts_. Specifically, as described above, you should perform the following insertions:

• Increment the count of the feature feat in the class label
• Increment the count of the "fake feature" "ANY" in the class label

You should use the helper function formatFeature to properly format the keys for insertion.

In addition, you will also need to perform two other insertions not related to the previously discussed equation (if you want to know why these are needed, we give a detailed explanation in the Deeper Dive below).

• Increment the count of the class label. The algorithm will use this to determine how much bias there should be towards a particular class.
• Increment the count of the feature feat without any class suffix (i.e., just insert feat directly as a key). This is actually only for bookkeeping purposes (knowing what features are present makes some other parts of the code easier).

In total, you should only need to write four lines of code to finish this TODO.

Your Task, Part B: Turn the Counts into Probabilities

The function logProb, which is currently unimplemented, is supposed to implement the equation we showed you earlier.

The slight catch is that in machine learning we typically do all calculations in log space. This is because the probabilities involved are often very small, and we want to avoid floating-point underflow. Going to log space solves this because the log of a very small number is a very big negative number.

In log space, division becomes subtraction. So we get:

$$ \log P(f|c) = \log(\text{# of times } f \text{ appears in examples labeled } c) - \log(\sum_{f' \in F}\text{# of times } f' \text{ appears in examples labeled } c) $$

But there's a problem here: what if \( f \) never appears in \( c \) (i.e., it has a count of 0)? In that case, you would take a log of 0, which is against the rules! We fix this through a method called smoothing: we pretend every feature has been seen once more than it actually was, so anything with a count of 0 gets treated as 1. We could just add 1 to the numerator, but if we don't modify the denominator as well, this will no longer be a valid probability. We'll skip the proof here, but it turns out the correct thing to add is the total number of features. So, letting \( N \) represent the total number of features, the thing logProb actually needs to return is:

$$ \log(1 + \text{ # of times } f \text{ appears in examples labeled } c) - \log(N + \sum_{f' \in F}\text{# of times } f' \text{ appears in examples labeled } c) $$

Your Task, Part C: Change a Setting in nbclassifier-demo.cpp

Now that NBClassifier is fully implemented, we can tell the demo code to use it instead of the basic dummy classifier. Near the top of nbclassifier-demo.cpp, find the following line:

#define DEMO_USE_NBCLASSIFIER 0

And change the 0 to a 1, so the line now reads:

#define DEMO_USE_NBCLASSIFIER 1

Now Run the Code!

Once you've made all your changes, run make to recompile the code. Now try evaluation mode again:

./nbclassifier-demo -t dataset-train.txt -e dataset-test.txt

If everything went right, this should print:

Test set accuracy: 69%

Finally, have some fun with the demo! You can try interactive mode again:

./nbclassifier-demo -t dataset-train.txt

And this time you should find that the model sometimes guesses "Pokemon" and sometimes guesses "software". It even gives some explanation for its "reasoning"! We'll also do some guided exploration in the written questions.

INITIALIZE bestScore = -inf
INITIALIZE bestClass = ""
foreach possible class c:
    foreach feature in input:
        COMPUTE score using the above equation
        if score > bestScore:
            UPDATE bestScore = score
            UPDATE bestClass = c
RETURN bestClass

(When logged in, completion status appears here.)