Discussion 10: Bayesian Classification with Maps
Exercise 1:
The
getWords() Method
(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.
The
The worst-case runtime complexity for
split() method has time complexity \(O(N)\), for a String of length \(N\) (intuitively, it will need to copy each character of the String into one entry of the String[] that it returns). Though there are only assumed to be \(\frac{N}{5}\) words, this is still \(O(N)\) words, so the loop itself will run for \(O(N)\) operations. Within the loop, the add() method for a HashSet has an expected time complexity of \(O(1)\), so the total expected time complexity of this method is \(O(N + N \cdot 1)\), which is \(O(N)\).
The worst-case runtime complexity for
add() in a HashSet is \(O(N)\). Therefore, the total worst-case time complexity of this method is \(O(N + N \cdot N) = O(N^2)\).
(c)
How would your answer change if the
Set is an (unsorted) ListSet? What if the Set is a (balanced) TreeSet?
The only operation that changes is
With a balanced
add(). With an unsorted ListSet, add() is always an \(O(N)\) operation, since we need to check if an element is already stored before adding, so both the expected time complexity and worst-case time complexities are \(O(N + N \cdot N) = O(N^2)\).
With a balanced
TreeSet, both expected and worst-case time complexities of add() are the same: \(O(\log N)\), so the full method is always \(O(N + N \cdot \log N) = O(N\log N)\).
Exercise 2:
The
initTopicMap() Method
(a)
The next method you'll implement is
Recall that
Note: executing this code may take several seconds.
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
(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.
First, we recall that
put() and get() (as well as getOrDefault() by similar reasoning) are expected \(O(1)\) operations on HashMaps. Now, let’s consider the number of iterations of each of the three nested loops. First, we loop over topics, which is an \(O(T)\) operation. Within that, we loop over data.get(topic), which is a collection of size \(O(A)\) step. From the previous exercise, getWords(text) is expected \(O(N)\). We then loop over the getWords() set, which is an \(O(N)\) operation. Within this innermost loop, we perform an expected \(O(1)\) work, as noted above. In total, this method is \(O(T \cdot (1 + A \cdot (N + N \cdot 1)))\), which simplifies to \(O(T \cdot A \cdot N)\).
(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.
This is not a good hash code method. While this uses all of the information in the
String, multiplication in this manner is a commutative operation, which means that anagrams (words that use the same combination of letters, like “lemon” and “melon”) will give the same hashCode(), despite them being different words.
(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.
This is also not a good hash code method. While this solves the previous problem for anagrams, this hash code fails the determinism requirement for
hashCode()s in Java. Determinism states that hashCode() being called on the same object (without modifications) should return the same hash code. This is clearly false in this case, since the randomness means we will very likely get different hash codes when running the method twice on the same object.
Exercise 3:
The
classify() Method
(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.
Note that we don’t actually need the division by 1,000, since it cancels out with the same division in the denominator (see the next part).
(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.
We’d repeat the line in the previous question for every other topic, then add them together. Since each term in the sum would feature the same division by 1,000, it cancels out, and we can remove it entirely from the calculations.
More precisely, the numerator would become:
and the denominator:
More generally, we could write a loop over the keys of
topicMap to compute this denominator.
(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
Note: executing this code may take several seconds.
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
Exercise 4:
(Challenge) The
topDiscriminatingFeature() Method
Classifier.java