1. (motivational) Consider the example sentence from the previous lecture:
   he/N can/V can/V a/N can/N
   HMM is a generative model, meaning that it models the join probability P(o,s), so it can generate the most probable tag sequence.
   Consider the observation b₃ from last lecture?

Is there any way to employ such observation in HMM (meaning that if observation b₃ is true it will influence the tag prediction) without changing the states (i.e. tags)?

2. Make sure that you understand shortcut notation: P(Y_v|X,Y_w,w~v) in the definition of CRF in Section 3
   Compare the definition, Figure 2 on page 4 and the Figure below.
   

Which of those Figures corresponds with the definition?
What is missing in Figure 2 in the paper?

Suppose the CRF above (there are only those 3 Ys).
Express the probability P(Y_i-1|X, Y_i, Y_i+1) for the CRF in Figure above (use the definition).

**Hint:** If you don't understand the shortcut notation, just ignore it and use your intuition (vertices connected by edges are not independent).

3. MEMMs suffer from Label Bias Problem. What about HMMs? Why?

4. Which of the following features are useful? Why?
   4a) X_i = "can"
   4b) X_i = "can" & Y_i = N
   4c) X_i = "can" & Y_i-1 = N
   4d) X_i-1 = "can" & Y_i = N & Y_i-1 = V
   4e) X_i-1 = "can" & Y_i = N & Y_i+1 = V
   4f) X_i-2 = "can" & Y_i = V & Y_i-1 = N
   4g) X_i+3 = "can" & Y_i = N & Y_i-2 = V
   4h) X₁ = "The" & Y_i-1 = N & Y_i = N
   4i) X_i has more letters than X_i-1 & Y_i = N
   4j) X contains word "dog" & (Y_i = N or Y_i = V)
   

5. CRFs have been specifically designed to overcome the Label Bias Problem. From Figure 2 you may observe that the only difference between CRF and MEMM is that the orientation of edges is discarded. The paper states that "CRFs use the observation-dependent normalization Z(x) for conditional distributions" which is then later described as and then the notation is not used in the formula below (just to add more confusion to the paper).

Let us now recall the formula used in MMEM.
The first formula predicts the probability of the tag sequence, while the second one predicts only probability of one tag, given the word and previous tag.
Suppose that MEMM is given observation sequence o₁, o₂, ... o_n. Using the formula above write down formula for the probability of the whole tag sequence, that is
**Hint:** It is simple. Just use the formula from the previous paper written above.
If s = s_i then s' = s_?

6. Compare your formula from the 4th question and the formula from the paper (the first formula in the 4th question).
   What is the main difference?
   
   Hint: Notation is different but note that the numerators are quite similar.

7. Let's suppose that we have a CRF for the data "he/N can/V can/V a/N can/N" and these features:
   f₁: X_i = can & Y_i = V && (Y_i-1 = N || Y_i-1 = V)
   f₂: X_i = can & (Y_i = N || Y_i = V) & Y_i-1 = N
   g₁: X_i = he & Y_i = N
   

7a) |Y| = ?
7b) Simplify (as much as possible) the

expression in Formula 1, given the above definitions of f₁, f₂ and g₁.

7c) (bonus question) Let's suppose, that λ₁=1, λ₂=1, μ₁=1.
Explain (either in the rigorous math way, or just your own words) why the

expression in Formula 1 (page 3) and

(numerator in the formula on page 4) give the same result.

**Hint:** The alpha-like symbol ∝ means "is directly proportional", i.e. A∝B ⇔ A=k*B & k≠0. See [Wikipedia](http://en.wikipedia.org/wiki/Proportionality_%28mathematics%29#Direct_proportionality).
The vertical bar in "y|_v" does not mean conditional probability, see its definition under Formula 1.