Lab 4: Part of Speech Tagging

As discussed above, the starter code contains a near-complete implementation of the Viterbi dynamic programming algorithm, with only a single "hole" missing inside the predict function, which has been marked with a TODO. Conceptually, the missing part of the code is supposed to fill in a costs matrix so we can compute the log probabilities associated with transitions to each possible tag.

You should see that, inside the predict function, we have already written a loop over all the tokens in the the document (i.e., the indices \( i \)). Furthermore, we have already written code that computes the max and fills in the pointers that will allow us to reconstruct the solution.

Recall that the equation for filling in each cell of the DP table is:

$$ D_{j,i} = \text{max}_{j' = 1}^{N} \log(B_{j,\text{index}(w_i)}) + \log(A_{j',j}) + D_{j',i-1} $$

And we've already written the code that takes the max...so the part you need to implement is all the stuff inside the max; that is, the \( \log(B_{j,\text{index}(w_i)}) + \log(A_{j',j}) + D_{j',i-1} \). For convenience, to avoid having to keep writing out all that math, let's name that thing costs.

Notice that in the code we've already initialized a matrix called costs, but the values in it aren't quite complete yet. You will need to figure out a series of matrix additions such that costs table ends up storing the values \( \log(B_{j,\text{index}(w_i)}) + \log(A_{j',j}) + D_{j',i-1} \) (for the current token \( w_i \)).

HINT: The reason the only provided for-loop is over token indices \( i \) is that you should be letting numpy automatically handle the iteration over tag indices \( j \) and \( j' \). In other words: you should not write any additional for-loops. You instead want to let numpy compute all the necessary sums at once, by leveraging numpy's ability to directly add matrices together.

If you're stuck, think about the fact that if \( i \) is a given (which it is, because it's the loop variable), then you end up selecting one column from \( B \) corresponding to \( B_{j,\text{index}(w_i)} \), giving you a vector indexed by \( j \). Likewise, you select one column from \( D \) corresponding to \( D_{j', i-1} \), giving you another vector indexed by \( j' \). So you have one vector indexed by \( j \) and one vector indexed by \( j' \)...and those just happen to correspond to the indices of \( A_{j', j} \)! So the indices already line up for a neat matrix addition—you might just need to do some rotations.

HINT: Be careful about your matrix dimensions! In particular, notice in the image above that the code stores the Dynamic Programming matrix such that the columns are tags and the rows are tokens. This is the opposite of how the indices are ordered in the original mathematical formula, where rows were tags and columns were indices. As long as you do your indexing correctly this should not affect the math at all (but we did it this way in the code to make the indexing slightly easier for you).

HINT: numpy can "broadcast" operations, so you can do things like adding a vector to every row of a matrix:

>>> a = numpy.ones((3, 4))
>>> b = numpy.random.random(4)
>>> b
array([0.36427943, 0.49914536, 0.1735815 , 0.35321266])
>>> a + b
array([[1.36427943, 1.49914536, 1.1735815 , 1.35321266],
       [1.36427943, 1.49914536, 1.1735815 , 1.35321266],
       [1.36427943, 1.49914536, 1.1735815 , 1.35321266]])

You might find that you want to add a vector to each column instead of each row, in which case, a quick solution may be to either transpose the matrix or reshape the vector. Finally, keep in mind that your matrix is square (e.g., number of tags x number of tags), so it's possible it won't throw errors if you swap your rows and columns. It might be good to use a Python interpreter to play around with rectangular matrices to make sure you're doing operations the way you want to.

Analysis Question #1

Train an HMMTagger on the Brown Corpus (/courses/cs159/data/pos/brown) and test it on the Wall Street Journal training data set (/courses/cs159/data/pos/wsj/train). In your journal, report the accuracy you got. For this question only, you do not need to do any further analysis of the accuracy (we will do some analysis in the upcoming analysis questions!)

(When logged in, completion status appears here.)