(1) Definition of CRF in Section 3 contains a formula with a shortcut notation: <latex>P(Y_v | X, Y_w, w \neq v) = P(Y_v | X, Y_w, w \sim v)</latex>.

a) Try to rewrite this general formula using some more clear notation (or explain it in your words).
b) Rewrite the formula for the chain-structured case of CRF.

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

(2) MEMMs suffer from Label Bias Problem. What about HMMs? Why?

(3) Which of the following features are meaningful? Why?

a) <latex>X_i</latex> == can
b) <latex>X_i</latex> == can && <latex>Y_i</latex> == N
c) <latex>X_i</latex> == can && <latex>Y_{i-1}</latex> == N
d) <latex>X_{i-1}</latex>== can && <latex>Y_i</latex> == N && <latex>Y_{i-1}</latex> == V
e) <latex>X_{i-1}</latex> == can && <latex>Y_i</latex> == N && <latex>Y_{i+1}</latex> == V
f) <latex>X_{i-2}</latex> == can && <latex>Y_i</latex> == V && <latex>Y_{i-1}</latex> == N
g) <latex>X_{i+3}</latex> == can && <latex>Y_i</latex> == N && <latex>Y_{i-2}</latex> == V
h) <latex>X_1</latex> == The && <latex>Y_{i-1}</latex> == N && <latex>Y_i</latex> == N
i) <latex>X_i</latex> has more letters than <latex>X_{i-1}</latex> && <latex>Y_i</latex> == N
j) <latex> X</latex> contains word “dog” && (<latex>Y_i</latex> == N || <latex>Y_i</latex> == V)

(4) Let's suppose, that we have a CRF for the data “he/N can/V can/V a/N can/N” and these features:

<latex>f_1</latex>: <latex>X_i</latex> == can && <latex>Y_i</latex> == V && (<latex>Y_{i-1}</latex> == N || <latex>Y_{i-1}</latex> == V)
<latex>f_2</latex>: <latex>X_i</latex> == can && (<latex>Y_i</latex> == N || <latex>Y_i</latex> == V) && <latex>Y_{i-1}</latex> == N
<latex>g_1</latex>: <latex>X_i</latex> == he && <latex>Y_i</latex> = N

a) |<latex>\cal{Y}</latex>| = ?
b) Draw a CRF for given data!
c) Simplify (as much as possible) the exp(…) expression in Formula 1, given the above definitions of <latex>f_1</latex>, <latex>f_2</latex> and <latex>g_1</latex>.

Hint1: The alpha-like symbol means “is directly proportional”, i.e. <latex>A \propto B \Leftrightarrow A = k * B</latex> && <latex>k \neq 0</latex>
http://en.wikipedia.org/wiki/Proportionality_%28mathematics%29#Direct_proportionality

Hint2: The vertical bar in <latex>y|_v</latex> does not mean conditional probability, see its definition under Formula 1.

d) Let's suppose, that
   <latex>\lambda_1</latex> = 1
   <latex>\lambda_2</latex> = 1
   <latex>\mu_1</latex> = 1

Show, that exp(…) expression in Formula 1 (page 3) and <latex>\prod_{i=1}^{n+1} M_i(y_{i-1}, y_i | x))</latex> in formula on page 4
give the same result.