Discussion 10: Bayesian Classification with Maps
Today’s discussion focuses on the Set and Map ADTs, which are extremely useful and performant data structures. You’ll get a chance to use several Set and Map methods, analyze their complexities, and think creatively about ways to modify their implementations. All of this will be done through the lens of a Bernoulli Naive Bayes classifier, a useful machine learning tool, foreshadowing some formulas you might see in future CS courses.
Learning Outcomes
- Describe the operations of the
SetandMapADTs, and utilize them in programs. - Compare the efficiency of
Setimplementations backed by arrays, sorted arrays, (balanced) binary search trees, and hash tables. - Identify the steps of hashing and describe the properties of a good hash function.
Exercise 1:
The
getWords() Method
Imagine you're working as an intern at arXiv, an online platform for viewing and sharing research article preprints. Your boss has tasked you with automatically sorting newly submitted research papers based on their abstracts. That is, when given a new paper, your program should automatically decide if it belongs to one of four topics: Astrophysics, Mathematics, Computer Science, or Biology. To help you design a model, your boss gave you a training dataset of 1,000 abstracts for each of the four research areas. They explain that they want you to use your programming skills in Java to make a Naive Bayes classifier (it's alright if you're not already familiar with this term; we explain everything that you'll need to know below) that can complete this task.
You'll create this model in the
You'll create this model in the
Classifier class.
Classifier.java
(a)
First, you'll need a way to parse the inputted text. Implement the
getWords() method, which returns a Set of each space-separated word in a string of text, to help you do that. You should use the split() method from Java's String class, which accepts a String as its argument and returns a String[] that splits the target string into substrings delimited by the argument String. If we called getWords("Attention Is All You Need"), the method should return a HashSet with the words "Attention," "Is," "All," "You," and "Need."
Classifier.java
(b)
What is the expected time complexity of the above method, in terms of the text (character) length \(N\)?
What is the worst-case time complexity? Assume that each word is 5 characters long, on average.
(c)
How would your answer change if the
Set is an (unsorted) ListSet? What if the Set is a (balanced) TreeSet?
Exercise 2:
The
initTopicMap() Method
(a)
The next method you'll implement is
Recall that
initTopicMap(), which initializes the topicMap field of the Classifier.
topicMap maps each topic (String) to a second Map associating words (Strings) with Doubles that count how many documents each word appears in (here, we use a Double rather than an Integer to avoid accidental truncations in the calculations that follow). For instance, topicMap.get("math").get("Euler") returns 50, which means there were 50 documents classified with the topic "math" that featured the word "Euler."
Recall that
data is a Map associating topics (Strings) with ArrayLists of 1,000 abstracts, each in a single String with the full abstract contents. Assume that this field is already initialized. Use the Map method getOrDefault(Object key, V defaultValue), which returns the value to which the specified key is mapped, or defaultValue if the Map contains no mapping for the key, in your implementation.
Classifier.java
Note: executing this code may take several seconds.
(b)
What is the expected time complexity of the above method, in terms of \(N =\) the maximum length of any abstract, \(T =\) the number of topics, and \(A =\) the maximum number of abstracts classified with any topic? Again, assume that each word is 5 characters long, on average.
(c)
Your coworker sees your use of
HashMaps and suggests a custom hashCode() method for the HashMaps of words to document counts. They suggest the product of the Unicode value of each character as a hash code calculation. Is this a good suggestion? Explain why or why not.
(d)
Another intern suggests another
hashCode() method for the same HashMap. They tell you to cycle through the characters in a word, and multiply each character's Unicode value by a random number between -5 and 5, accumulating that result into a hash code. Is this a good suggestion? Explain why or why not.
Exercise 3:
The
classify() Method
The final method you'll need is
This equation gives the probability that the abstract belongs to an Astrophysics paper, given that it contains the words \(\{\text{Sun}, \text{Mars}\}\) (though the formula could be expanded for any number of words). The \(\dots\) in the denominator indicates that the calculation pattern continues for the remaining topics.
Just take this formula as is. If you'd like to know why it's true, take CS 2800 or 3780!
classify(), which takes in an abstract (text) and an array of potential topics (topics), and returns the topic (one of the Strings in topics) that the Naive Bayes classifier predicts.
The Naive Bayes classifier is given by the following formula (simplified via a flat prior):
\(\Pr(\text{Astro} \mid \{\text{Sun}, \text{Mars}\}) = \frac{\Pr(\text{Sun} \mid \text{Astro}) \times \Pr(\text{Mars} \mid \text{Astro})}{\Pr(\text{Sun} \mid \text{Astro}) \times \Pr(\text{Mars} \mid \text{Astro}) + \Pr(\text{Sun} \mid \text{Math}) \times \Pr(\text{Mars} \mid \text{Math}) + \dots}\)
This equation gives the probability that the abstract belongs to an Astrophysics paper, given that it contains the words \(\{\text{Sun}, \text{Mars}\}\) (though the formula could be expanded for any number of words). The \(\dots\) in the denominator indicates that the calculation pattern continues for the remaining topics.
Just take this formula as is. If you'd like to know why it's true, take CS 2800 or 3780!
(a)
\(\Pr(\text{Sun} \mid \text{Astro})\) translates to "what's the probability that an Astrophysics paper has the word "Sun"?" Using the data we have, this is the number of Astrophysics papers that have the word "Sun" divided by the total number of Astrophysics papers.
Using this logic, translate the numerator of the preceding formula for \(\Pr(\text{Astro} \mid \{\text{Sun}, \text{Mars}\})\) into a single line of Java, using the
Using this logic, translate the numerator of the preceding formula for \(\Pr(\text{Astro} \mid \{\text{Sun}, \text{Mars}\})\) into a single line of Java, using the
topicMap field.
(b)
Describe how you would calculate the denominator of the preceding formula for \(\Pr(\text{Astro} \mid \{\text{Sun}, \text{Mars}\})\) in Java, using the
topicMap field. You may notice some potential fraction simplification between this and the previous question.
(c)
Implement the
If a word doesn't appear in a document, you should "pretend" it appears in 0.5 documents, to prevent division-by-zero errors. Use the
classify() method according to its specifications. Since this method is fairly complicated, most of the code is given. All that is left is the "main" loop, which should do two things: set numerators so that numerators[i] is the numerator for topics[i], and calculate the denominator, which is the same for each topic probability. Your code should take inspiration from parts (a) and (b), but it will consider all words in the text (as opposed to just "Sun" and "Mars" in this example).
If a word doesn't appear in a document, you should "pretend" it appears in 0.5 documents, to prevent division-by-zero errors. Use the
Map method getOrDefault(Object key, V defaultValue) to accomplish this.
Classifier.java
Note: executing this code may take several seconds.
Exercise 4:
(Challenge) The
topDiscriminatingFeature() Method
The above classifier would likely get \(>80\%\) accuracy in predicting between these four topics. However, notice how it uses every word in each calculation, including words like "the," "and," and "for," which don't tell you much about the probability of an abstract being one class or another. To get rid of this noise and get higher accuracy, we can restrict our attention to the most "discriminating" words, or words that appear a lot in one topic and not a lot in another. For instance, between "Biology" and "Math," the most discriminating word is "brain," which appears in 0 Math abstracts (within the sample) but 372 Biology abstracts.
We can quantify this "discriminating" quality by dividing the number of documents from topic one in which a word appears by the number of documents from topic two in which a word appears. To prevent division by zero, if a word does not appear in any document for a topic, we "pretend" it appears in 0.5 documents, again using
Implement
We can quantify this "discriminating" quality by dividing the number of documents from topic one in which a word appears by the number of documents from topic two in which a word appears. To prevent division by zero, if a word does not appear in any document for a topic, we "pretend" it appears in 0.5 documents, again using
getOrDefault(Object key, V defaultValue). For the aforementioned "brain" example, the discriminating ratio would be \(\frac{372}{0.5} = 744\).
Implement
topDiscriminatingFeature(), which returns a HashMap with a single key and value, corresponding to the word with the highest discriminating ratio between topicOne and topicTwo, and the actual ratio value itself.
Classifier.java
Note: executing this code may take several seconds.