Questions MEMM - ufal/NPFL095 GitHub Wiki

Andrew McCallum, Dayne Freitag, Fernando Pereira: Maximum Entropy Markov Models for Information Extraction and Segmentation

1. Explain (roughly) how the new formula for α_t+1(s) is derived (i.e. Formula 1 in the paper).

2. Section 2.1 states “we will split P(s|s',o) into |S| separately trained transition functions”. What are the advantages and disadvantages of this approach?

3. Let S= {V,N} (verb and non-verb)
   Training data = he/N can/V can/V a/N can/N
   Observation features are:
   b1 = current word is “he”
   b2 = current word is “can”
   b3 = current word is “a” and next word is “can”
   When implementing MEMM you need to define s₀, i.e. the previous state before the first token. It may be a special NULL, but for simplicity let’s define it as N.

• 3a) What are the states (s) and observations (o) for this training data?

• 3b) Equation (2) defines features f_a based on observation features b. How many such f_a features do we have?

• 3c) Equation (3) defines constraints. How many such constraints do we have?

• 3d) List all the constraints involving feature b2, i.e. substitute (whenever possible) concrete numbers into Equation (3).

• 3e) In step 3 of the GIS algorithm you need to compute P_s’^(j)(s|o). Compute P_N⁽⁰⁾(N|can) and P_N⁽⁰⁾(V|can).

Hint : You might be confused by the m_s' variable (and t₁, …, t_ms') in Equation (3). For a given s', t₁, …, t_ms' are the time stamps where the previous state (with time stamp t_i - 1) is s'. For example, in our training data:
for s'=N, t₁=1 (because s₀=N), t₂=2 (because s₁=N) and t₃=5 (because s₄=N), i.e. m_s'=3;
for s'=V, t₁=3 (because s₂=V), t₂=4 (because s₃=V), i.e. m_s'=2.

OPTIONAL (These papers may or may not help you with the questions and to learn more about Maximum Entropy Markov Models):
http://www.cs.cmu.edu/afs/cs/user/aberger/www/html/tutorial/tutorial.html
http://www.mit.edu/~6.863/spring2011/jmnew/6.pdf
http://www.cs.cornell.edu/courses/cs6784/2010sp/lecture/09-McCallumEtAl00.pdf
http://see.stanford.edu/materials/aimlcs229/cs229-hmm.pdf