Assignment 5: Naive Bayes Classifier for Text Classification UVA CS 6316 : Machine Learning (Fall) Out: Nov. 12 2019 Due: Nov. 27, midnight 11:59pm, @ Collab a The assignment should be submitted in the PDF format through Collob. If you prefer hand-writing QA parts of answers, please convert them (e.g., by scanning or using an app like Genuis Scan) into PDF form. b For questions and clarifications, please post on Piazza. c Policy on collaboration: Homework should be done individually: each student must hand in their own answers. It is acceptable, however, for students to collaborate in figuring out answers and helping each other solve the problems. We will be assuming that, with the honor code, you will be taking the responsibility to make sure you personally understand the solution to any work arising from such collaboration. d Policy on late homework: Homework is worth full credit at the midnight on the due date. Each student has three extension days to be used at his or her own discretion throughout the entire course. Your grades would be discounted by 10% per day when you use these 3 late days. You could use the 3 days in whatever combination you like. For example, all 3 days on 1 assignment (for a maximum grade of 70%) or 1 each day over 3 assignments (for a maximum grade of 90% on each). After you’ve used all 3 days, you cannot get credit for anything turned in late. e Policy on grading: 1: 82 points in total. 42 points for correct code submission (and able to run). 40 points for discussing and presenting Results in the report. 2: 18 points in total. 8+3+3+3+4 points for answering sub question. The overall grade will be divided by 10 and put in your grade book. 1 Naive Bayes Classifier for Movie Review Text Classification In this programming assignment, you are expected to implement different Naive Bayes Classifiers using python for a text-based movie review classification task. A ZIP file “data sets naive bayes.zip” including two sets of data samples (i.e. training set and test set) for movie reviews is provided to you through collab attachments. Please follow the following naming rules wrt files and functions. We expect you to submit a source-code file named as ”naiveBayes.py” containing the necessary and required functions for training, testing and evaluations. For a naive Bayes classifier, when given an unlabeled document d, the predicted class c∗d = argmax c P(c|d) , where c is the value of the target class variable. For the target movie review classification task, c = pos or neg. For example, if P(c = pos|d) = 34 and P(c = neg|d) = 14 , we use the MAP rule to classify the document d into the “positive” class. The conditional probability P(c|d) is calculated through Bayes’ rule, P(c|d) = P(c)P(d|c) P(d) ∝ P(c)P(d|c) 1 This assignment requires you to implement three types of naive bayes classifiers, among which the first two follow the Multinomial assumption and the third uses the multivariate Bernoulli assumption. 1.1 Preprocessing (Q1) You are required to implement the first choice of preprocessing described as following. You can get 1 point of extra credit if you also implement the second choice of preprocessing and discuss the classification results based on it. • (First choice): to get a consistent result from all the students, please use a predefined dictionary including the following words: {love, wonderful, best, great, superb, still, beautiful, bad, worst, stupid, waste, boring, ?, !, UNK }. – Besides, for the token “love”, you should also consider the tokens “loving”, “loved”, “loves” since their stemmed version will be the same as the token “love”. In other words, the frequency of love should include the words ”love, loving, loves, loved”. In order to do that, you don’t need to use the NLTK. You can do a simple string.replace(”loved”, ”love”), string.replace(”loves”, ”love”), string.replace(”loving”, ”love”). No other preprocessing is necessary (e.g. stemming, stopword removal). – UNK represents unknown words not included in the dictionary. – In summary, thetaPos and thetaNeg are each vectors of length 15. • (Second choice): normally, as the first step, you will build a vocabulary of unique words from the training corpus, being ranked with their frequency. Then you will just use the top K words that appearing more than a certain times (e.g. 3 times) in the whole training corpus. – It is recommended that you use stemming and stopword removal for this (you can use a python package such as NLTK). 1.2 Build “bag of words” (BOW) Document Representation • (Q2) You are required to provide the following function to convert a text document into a feature vector: BOWDj = transfer(fileDj, vocabulary) where fileDj is the location of file j • (Q3) Read in the training and test documents into BOW vector representations using the above func- tion. Then store features into matrix Xtrain and Xtest, and use ytrain and ytest to store the labels. You are required to provide the following function to convert a text document into a feature vector: Xtrain,Xtest, ytrain, ytest = loadData(textDataSetsDirectoryFullPath) – “textDataSetsDirectoryFullPath” is the real full path of the file directory that you get from unzipping the datafile. For instance, it is “/HW/data sets/” on the instructor’s laptop. – loadData should call transfer() Note: Xtrain and Xtest are matrices with each column representing a document (in BOW vector format). ytrain and ytest are vectors with a label at each position. These should all be represented using a python list or numpy matrix. 1.3 Multinomial Naive Bayes Classifier (MNBC) Training Step • We need to learn the P(cj) and P(wi|cj) through the training set. Through MLE, we use the relative- frequency estimation with Laplace smoothing to estimate these parameters. • Since we have the same number of positive samples and negative samples, P(c = −1) = P(c = 1) = 12 . 2 • (Q4) You are required to provide the following function (and module) for grading: thetaPos, thetaNeg = naiveBayesMulFeature train(Xtrain, ytrain) • (Q5) Provide the resulting value of thetaPos and thetaNeg into the writeup. Note: Pay attention to the MLE estimator plus smoothing; Here we choose α = 1. Note: thetaPos and thetaNeg should be python lists or numpy arrays (both 1-d vectors) 1.4 Multinomial Naive Bayes Classifier (MNBC) Testing+Evaluate Step • (Q6) You are required to provide the following function (and module) for grading: yPredict, Accuracy = naiveBayesMulFeature test(Xtest, ytest, thetaPos, thetaNeg) Add the resulting Accuracy into the writeup. • (Q7) Use ”sklearnn˙aive bayes.MultinomialNB” from the scikit learn package to perform training and testing. Compare the results with your MNBC. Add the resulting Accuracy into the writeup. Important: Do not forget perform log in the classification process. 1.5 Multivariate Bernoulli Naive Bayes Classifier (BNBC) • We need to learn the P(cj), P(wi = false|cj) and P(wi = true|cj) through the training. MLE gives the relative-frequency as the estimation of parameters. We will add with Laplace smoothing for estimating these parameters. • Essentially, we simply just do counting to estimate P(wi = true|c). P(wi = true|c) = #files which include wi and are in class c + 1 #files are in class c + 2 P(wi = false|c) = 1− P(wi = true|c) • Since we have the same number of positive samples and negative samples, P(c = −1) = P(c = 1) = 12 . • (Q10) You are required to provide the following function (and module) for grading: thetaPosTrue, thetaNegTrue = naiveBayesBernFeature train(Xtrain, ytrain) • (Q11) Provide the resulting parameter estimations into the writing. • (Q12) You are required to provide the following function (and module) for grading: yPredict, Accuracy = naiveBayesBernFeature test(Xtest, ytest, thetaPosTrue, thetaNegTrue) Add the resulting Accuracy into the writing. 3 1.6 How will your code be checked ? In collab, you will find the sample codes named “naiveBayes.py”. “textDataSetsDirectoryFullPath” and “testFileDirectoryFul
lPath” are string inputs. We will run the command line: “python naiveBayes.py text- DataSetsDirectoryFullPath testFileDirectoryFullPath” to check your code if it can print the result of the following functions in the table. thetaPos, thetaNeg = naiveBayesMulFeature train(Xtrain, ytrain) yPredict, Accuracy= naiveBayesMulFeature test(Xtest, ytest, thetaPos, thetaNeg) thetaPosTrue, thetaNegTrue= naiveBayesBernFeature train(Xtrain, ytrain) yPredict, Accuracy= naiveBayesBernFeature test(Xtest, ytest,thetaPosTrue, thetaNegTrue) Congratulations ! You have implemented a state-of- the-art machine-learning toolset for an important web text mining task ! 4 2 Sample QA Questions: Question 1. Bayes Classifier Suppose you are given the following set of data with three Boolean input variables a, b, and c, and a single Boolean output variable G. a b c G 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 For item (a), assume we are using a naive Bayes classifier to predict the value of G from the values of the other variables. (a) According to the naive Bayes classifier, what is P (G = 1|a = 1 ∧ b = 1)? 5 Please provide a one-sentence justification for the following TRUE/FALSE questions. (b) (True/False) Naive Bayes Classifier and logistic regression both directly model p(C|X). (c) (True/False) Gaussian Naive Bayes Classifier and Gaussian Mixture Model are similar since both assume that p(X|cluster == i) follows Gaussian distribution. (d) (True/False) when you train Gaussian Naive Bayes Classifier on data samples provided in the following Figure, using separate covariance for each class, Σ1 6= Σ2, the decision boundary will be linear. Please provide a one-sentence justification. 6
