Aron Culotta, Jeffrey Sorensen: Dependency Tree Kernels for Relation Extraction, ACL 2004.

1. Given Figure 1, what is the smallest common subtree that includes both t1 (Troops) and t2 (near)?
2. Section 5: “Therefore, d(a)=l(a).” When is this true and why? (Assume this holds for the following questions.)
3. Let <latex>\phi_m</latex> = {general-pos-tag, entity-type, relation-arguments} (in accordance with the paper). Let <latex>\phi_s = \phi_m</latex> (unlike in the paper). Based on Figure 2 and Section 5, compute the following matching functions and similarity functions:
   • m(t0,u0)=? m(t1,u1)=? m(t2,u2)=?
   • s(t0,u0)=? s(t1,u1)=? s(t2,u2)=?
4. Let <latex>\lambda=0.5</latex>. Compute the contiguous kernel for the two trees in Figure 2: <latex>K_1(T,U)=?</latex>. Provide the final number and some counts along the way, so its clear how you got the number. Optionally, compute also the sparse kernel <latex>K_0(T,U)=?</latex>.
5. Let DT be a function that assigns the correct augmented dependency tree to a sentence. Compute (estimate) contiguous kernel and bag-of-words kernel for the following sentences:
   • <latex>K_1</latex>(DT(“Peter sleeps”), DT(“Bob runs”))=?
   • <latex>K_2</latex>(DT(“Peter sleeps”), DT(“Bob runs”))=?
6. Lets have a pair of sentences:
   • “Bob saw US troops that moved towards Baghdad”
   • “US troops that moved towards Baghdad were seen by Bob”

You want to check the relation between entities “US” and “Baghdad”. Compute (estimate) <latex>K_1</latex> and <latex>K_2</latex>.