Note that there separate sets of assignments for CS 451/651 and CS 431/631. Make sure you work on the correct asssignments!

CS 451/651 Assignments

Assignment 6 due 2:30pm March 27

In this assignment, you will build a spam classifier trained using stochastic gradient descent in Spark, replicating the work described in Efficient and Effective Spam Filtering and Re-ranking for Large Web Datasets by Cormack, Smucker, and Clarke. We will draw your attention to specific sections of the paper that are directly pertinent to the assignment, but you should read the entire paper for background.

Downloading Data

If you're working on your laptop, grab the training and test data:

wget https://www.student.cs.uwaterloo.ca/~cs451/spam/spam.train.group_x.txt.bz2
wget https://www.student.cs.uwaterloo.ca/~cs451/spam/spam.train.group_y.txt.bz2
wget https://www.student.cs.uwaterloo.ca/~cs451/spam/spam.train.britney.txt.bz2
wget https://www.student.cs.uwaterloo.ca/~cs451/spam/spam.test.qrels.txt.bz2

Otherwise, the datasets are at ~cs451/public_html/spam/ in the Linux Student CS environment.

Just to verify what you've downloaded:

After you've downloaded the data, unpack:

bunzip2 spam.train.group_x.txt.bz2
bunzip2 spam.train.group_y.txt.bz2
bunzip2 spam.train.britney.txt.bz2
bunzip2 spam.test.qrels.txt.bz2

Verify the unpacked data:

Next, download the two files you'll need for evaluating the output of the spam classifier (links below):

• compute_spam_metrics.c
• spam_eval.sh
• spam_eval_hdfs.sh

Compile the C program:

gcc -O2 -o compute_spam_metrics compute_spam_metrics.c -lm

You might get some warnings but don't worry—the code should compile fine. The actual evaluation script spam_eval.sh (and spam_eval_hdfs.sh) calls compute_spam_metrics, so make sure they're in the same directory.

Note on local vs. Altiscale: for this assignment, your code must (eventually) work in Altiscale, but feel free to develop locally or in the Linux Student CS environment. The instructions below are written for running locally, but in a separate section later we will cover details specific to Altiscale.

Basic Spam Classifier

In this assignment, we'll take you through building spam classifiers of increasing complexity, but let's start with a basic implementation using stochastic gradient descent. Build the spam classifier in exactly the way we describe below, because later parts of the assignment will depend on the setup.

First, let's write the classifier trainer. The classifier trainer takes all the training instances, runs stochastic gradient descent, and produces a model as output.

Look at the Cormack, Smucker, and Clarke paper: the entire algorithm is literally 34 lines of C, shown in Figure 2 on page 10. The stochastic gradient descent update equations are in equations (11) and (12) on page 11. We actually made things even simpler for you: the features used in the spam classifier are hashed byte 4-grams (thus, integers)—we've pre-computed the features for you.

Take a look at spam.train.group_x.txt. The first line begins as follows:

clueweb09-en0094-20-13546 spam 387908 697162 426572 161118 688171 ...

In the file, each training instance is on a line. Each line begins with a document id, the string "spam" or "ham" (the label), and a list of integers (the features).

Therefore, your spam classifier will look something like this:

// w is the weight vector (make sure the variable is within scope)
val w = Map[Int, Double]()

// Scores a document based on its list of features.
def spamminess(features: Array[Int]) : Double = {
  var score = 0d
  features.foreach(f => if (w.contains(f)) score += w(f))
  score
}

// This is the main learner:
val delta = 0.002

// For each instance...
val isSpam = ...   // label
val features = ... // feature vector of the training instance

// Update the weights as follows:
val score = spamminess(features)
val prob = 1.0 / (1 + exp(-score))
features.foreach(f => {
  if (w.contains(f)) {
    w(f) += (isSpam - prob) * delta
  } else {
    w(f) = (isSpam - prob) * delta
   }
})

We've given you the code fragment for the learner above as a starting point—it's your job to understand exactly how it works and turn it into a complete classifier trainer in Spark.

For the structure of the Spark trainer program, take a look at slide 13 in the Part 06b, slide 13 deck. We're going to build the configuration shown there (even though the slide says MapReduce, we're implementing it in Spark). Specifically, we're going run a single reducer to make sure we pump all the training instances through a single learner on the reducer end. The overall structure of your program is going to look something like this:

val textFile = sc.textFile("/path/to/training/data")

val trained = textFile.map(line =>{
  // Parse input
  // ..
  (0, (docid, isSpam, features))
  }).groupByKey(1)
  // Then run the trainer...

trained.saveAsTextFile(...)

Note the mappers are basically just parsing the feature vectors and pushing them over to the reducer side for additional processing. We emit "0" as a "dummy key" to make sure all the training instances get collected at the reducer end via groupByKey()... after which you run the trainer (which applies the SGD updates, per above). Of course, it's your job to figure out how to connect the pieces together. This is the crux of the assignment.

Putting everything together, you will write a trainer program called TrainSpamClassifier that we will execute in the following manner:

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.TrainSpamClassifier \
 target/assignments-1.0.jar --input spam.train.group_x.txt --model cs451-lintool-a6-model-group_x

The --input option specifies the input training instances (from above); the --model option specifies the output directory where the model goes. Inside the model directory cs451-lintool-a6-model-group_x, there should be a single file, part-00000, that contains the trained model. The trained model should be a sequence of tuples, one on each line; each tuple should contain a feature and its weight (a double value). Something like:

$ head -5 cs451-lintool-a6-model-group_x/part-00000
(547993,2.019484093190069E-4)
(577107,5.255371091500805E-5)
(12572,-4.40967560913553E-4)
(270898,-0.001340150007664197)
(946531,2.560528666942676E-4)

Next, you will write another Spark program named ApplySpamClassifier that will apply the trained spam classifier to the test instances. That is, the program will read in each input instance, compute the spamminess score (from above), and make a prediction: if the spamminess score is above 0, classify the document as spam; otherwise, classify the document as ham.

We will run the program in the following manner:

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.ApplySpamClassifier \
 target/assignments-1.0.jar --input spam.test.qrels.txt \
 --output cs451-lintool-a6-test-group_x --model cs451-lintool-a6-model-group_x

The --input option specifies the input test instances; the --model option specifies the classifier model; and the --output option specifies the output directory. The test data is organized in exactly the same way as the training data. The output of ApplySpamClassifier should be organized as follows:

$ cat cs451-lintool-a6-test-group_x/* | sort | head -5
(clueweb09-en0000-00-00142,spam,2.601624279252943,spam)
(clueweb09-en0000-00-01005,ham,2.5654162439491004,spam)
(clueweb09-en0000-00-01382,ham,2.5893946346394188,spam)
(clueweb09-en0000-00-01383,ham,2.6190102258752614,spam)
(clueweb09-en0000-00-03449,ham,1.500142758578532,spam)

The first field in each tuple is the document id and the second field is the test label. These are just copied from the test data. The third field is the spamminess score, and the fourth field is the classifier's prediction.

Important: It is absolutely critical that your classifier does not use the label in the test data when making its predictions. The only reason the label is included in the output is to facilitate evaluation (see below).

Finally, you can evaluate your results:

$ ./spam_eval.sh cs451-lintool-a6-test-group_x
1-ROCA%: 17.25

The eval script prints the evaluation metric, which is the area under the receiver operating characteristic (ROC) curve. This is a common way to characterize classifier error. The lower this score, the better.

If you've done everything correctly up until now, you should be able to replicate the above results.

You should then be able to train on the group_y training set:

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.TrainSpamClassifier \
 target/assignments-1.0.jar --input spam.train.group_y.txt --model cs451-lintool-a6-model-group_y

And make predictions:

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.ApplySpamClassifier \
 target/assignments-1.0.jar --input spam.test.qrels.txt \
 --output cs451-lintool-a6-test-group_y --model cs451-lintool-a6-model-group_y

And evaluate:

$ ./spam_eval.sh cs451-lintool-a6-test-group_y
1-ROCA%: 12.82

Finally, train on the britney training set:

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.TrainSpamClassifier \
 target/assignments-1.0.jar --input spam.train.britney.txt --model cs451-lintool-a6-model-britney

And make predictions:

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.ApplySpamClassifier \
 target/assignments-1.0.jar --input spam.test.qrels.txt \
 --output cs451-lintool-a6-test-britney --model cs451-lintool-a6-model-britney

And evaluate:

$ ./spam_eval.sh cs451-lintool-a6-test-britney
1-ROCA%: 15.96

There may be some non-determinism in running over the britney dataset, so you might get something slightly different.

Here's a placeholder for question 1 that you're going to answer below (see Altiscale section).

Ensemble Spam Classifier

Next, let's build an ensemble classifier. Start by gathering all the models from each of the individual classifiers into a common directory:

mkdir cs451-lintool-a6-model-fusion
cp cs451-lintool-a6-model-group_x/part-00000 cs451-lintool-a6-model-fusion/part-00000
cp cs451-lintool-a6-model-group_y/part-00000 cs451-lintool-a6-model-fusion/part-00001
cp cs451-lintool-a6-model-britney/part-00000 cs451-lintool-a6-model-fusion/part-00002

With these three separate classifiers, implement two different ensemble techniques:

• Score averaging: Average the spamminess score from each individual classifier. If the average score is above 0, classify the document as spam; otherwise, classify the document as ham.
• Voting: Each classifier gets a vote on spam/ham. Majority wins. The spamminess score in this case is # spam - # ham (so the possible scores are -3, -1, 1, 3).

Write a program ApplyEnsembleSpamClassifier that we will execute in the following manner:

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.ApplyEnsembleSpamClassifier \
 target/assignments-1.0.jar --input spam.test.qrels.txt \
 --output cs451-lintool-a6-test-fusion-average --model cs451-lintool-a6-model-fusion --method average

The --input option specifies the input test instances. The --model option specifies the base directory of all the classifier models; in this directory your program should expect each individual model in a part-XXXXX file; it's okay to hard code the part files for convenience. The --output option specifies the output directory. Finally, the --method option specifies the ensemble technique, either "average" or "vote" per above.

Your prediction program needs to load all three models, apply the specified ensemble technique, and make predictions. Hint: Spark broadcast variables are helpful in this implementation.

The output format of the predictions should be the same as the output of the ApplySpamClassifier program. You should be able to evaluate with spam_eval.sh in the same way. Go ahead and predict with the two ensemble techniques and evaluate the predictions. Note that ensemble techniques can sometimes improve on the best classifier; sometimes not.

Here's a placeholder for questions 2 and 3 that you're going to answer below (see Altiscale section).

How does the ensemble compare to just concatenating all the training data together and training a single classifier? Let's find out:

cat spam.train.group_x.txt spam.train.group_y.txt spam.train.britney.txt > spam.train.all.txt

Now train on this larger test set, predict, and evaluate.

Here's a placeholder for question 4 that you're going to answer below (see Altiscale section).

The Effects of Data Shuffling

In class, we talked about how a model trained using stochastic gradient descent is dependent on the order in which the training instances are presented to the trainer. Let's explore this effect.

Modify the TrainSpamClassifier to implement a new option --shuffle. With this option, the program will randomly shuffle the training instances before running the trainer:

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.TrainSpamClassifier \
 target/assignments-1.0.jar --input spam.train.britney.txt --model cs451-lintool-a6-model-britney-shuffle --shuffle

You must shuffle the data using Spark. The way to accomplish this in Spark is to generate a random number for each instance and then sort the instances by the value. That is, you cannot simply read all the training instances into memory in the driver, shuffle, and then parallelize.

Obviously, the addition of the --shuffle option should not break existing functionality; that is, without the option, the program should behave exactly as before.

Note that in this case we're working with the britney data because the two other datasets have very few examples—random shuffles can lead to weird idiosyncratic effects.

You should be able to evaluate the newly trained model in exactly the same way as above. If you are getting a wildly different 1-ROCA% scores each time, you're doing something wrong.

Here's a placeholder for question 5 that you're going to answer below (see Altiscale section).

Running on Altiscale

You are free to develop locally on your own machine or in the Linux Student CS environment (and in fact, the instructions above assume so), but you must make sure that your code runs in Altiscale also. This is just to verify that your Spark programs will work in a distributed environment, and that you are not inadvertently taking advantage of some local feature.

All training and test data are located in /shared/uwaterloo/cs451/data/ on HDFS. Note that spam.train.all.txt has already been prepared for you in that directory also.

For example, training, predicting, and evaluating on the group_x dataset in Altiscale:

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.TrainSpamClassifier \
 target/assignments-1.0.jar --input /shared/uwaterloo/cs451/data/spam.train.group_x.txt \
 --model cs451-lintool-a6-model-group_x

spark-submit --driver-memory 2g --class ca.uwaterloo.cs451.a6.ApplySpamClassifier \
 target/assignments-1.0.jar --input /shared/uwaterloo/cs451/data/spam.test.qrels.txt \
 --output cs451-lintool-a6-test-group_x --model cs451-lintool-a6-model-group_x

./spam_eval_hdfs.sh cs451-lintool-a6-test-group_x

The major differences are:

• Location of the training/test data (on HDFS).
• All input/output from/to HDFS.
• Use of spam_eval_hdfs.sh for the evaluation script.

Refer back to the placeholders above and answer the following questions, running your code on the Altiscale cluster:

Question 1: For each individual classifiers trained on group_x, group_y, and britney, what are the 1-ROCA% scores? You should be able to replicate our results on group_x, group_y, but there may be some non-determinism for britney, which is why we want you to report the figures.

Question 2: What is the 1-ROCA% score of the score averaging technique in the 3-classifier ensemble?

Question 3: What is the 1-ROCA% score of the voting technique in the 3-classifier ensemble?

Question 4: What is the 1-ROCA% score of a single classifier trained on all available training data concatenated together?

Question 5: Run the shuffle trainer 10 times on the britney dataset, predict and evaluate the classifier on the test data each time. Report the 1-ROCA% score in each of the ten trials and compute the overall average.

Turning in the Assignment

Please follow these instructions carefully!

Make sure your repo has the following items:

• Put the answers to all the questions above in bigdata2018w/assignment6.md.
• Your implementations should go in package ca.uwaterloo.cs451.a6. At the minimum, you should have TrainSpamClassifier, ApplySpamClassifier, and ApplyEnsembleSpamClassifier. Feel free to include helper code also.

Make sure your implementation runs on the Altiscale cluster. The following check script is provided for you (check the source for the relevant flags):

• check_assignment6_public.py

When you've done everything, commit to your repo and remember to push back to origin. You should be able to see your edits in the web interface. Before you consider the assignment "complete", we would recommend that you verify everything above works by performing a clean clone of your repo and run the public check scripts.

That's it!

Grading

The entire assignment is worth 60 points:

• Getting your code to compile is worth 4 points.
• A correct implementation of the basic TrainSpamClassifier is worth 15 points.
• A correct implementation of ApplySpamClassifier is worth 5 points.
• A correct implementation of ApplyEnsembleSpamClassifier is worth 6 points.
• A correct implementation of the --shuffle option in TrainSpamClassifier is worth 5 points.
• The answers to questions 1-5 are worth 3 points each.
• Being able to successfully run all your code on Altiscale is worth 10 points. We will begin by testing all your code on Altiscale. If everything works there, you will get full marks. If we can't get your code to run successfully on Altiscale, we will try running your code in the Linux Student CS environment, as part of confirming that the implementations above are correct. However, if your code works in the Linux Student CS environment but not on Altiscale, you will still receive zero marks for this item.

Back to top