Please answer the programming theory questions in the attached PDF.

Please answer the programming theory questions in the attached PDF.


1 1 Structured Perceptrons (28 points) Suppose we are given the following weight matrix Θ: 1. Suppose we are given the following training sentence: Jaco/NN barked/VB (a) (12 points) Use the Viterbi algorithm to compute the best tag sequence. As part of your answer, you should fill in the Viterbi trellis below. You should also keep track of backpointers, either using arrows or in a separate table. Jaco barked NN VB (b) (8 points) Update the weight matrix. Use a constant learning rate η = 1. 2. (12 points) Suppose we are given the following testing sentence: Jaco meowed Use the Viterbi algorithm to compute the best tag sequence. Again, you should fill in the Viterbi trellis below, and keep track of backpointers. Jaco meowed NN VB 2 2 Constituency Parsing (30 points) 2.1 Chomsky Normal Form (15 points) Convert the following grammar to Chomsky Normal Form. Remember to collapse unary rules. 1. S → NP VP 2. S → VP 3. NP → DT NN 4. NP → NN 5. VP → VB IN NP 6. NN → time 7. VB → flies 8. IN → like 9. DT → an 10. NN → arrow 3 2.2 Probabilistic CKY Algorithm (15 points) Using the grammar in Figure 1 below, complete the chart in Figure 2. You don’t need to keep track of backpointers or draw the final tree for the sentence. Figure 1: Grammar for Parsing Figure 2: Finish the Chart 4 3 Dependency Parsing (14 points) Go through the sequence of transitions needed for parsing the sentence “I saw an elephant in my pajamas”. The dependency tree for the sentence is shown below. At each step, give the configuration of the stack and buffer, as well as what transition was applied this step and what new dependency was added (if any). Stack Buffer New dependency Transition [ROOT] [I, saw, an elephant, in, my, pajamas] Initial Configuration 5 4 Attention (28 points) Suppose we are given the following word embeddings: xtime Suppose we are also given the following query, key, and value matrices: 1. (10 points) Compute the query vector qtime, the key vectors ktime and kflies, and the value vectors vtime and vflies, using the equations q = xQ, k = xK, and v = xV . 2. (6 points) Compute the scores (qtime · ktime) and (qtime · kflies). Do not apply a scaling factor. 3. (6 points) Compute the softmax of the above scores. 4. (6 points) Compute the sum ztime as a weighted sum of vtime and vflies, weighted by the above softmax.