C(n 1 , n 2 ) counts the number of common descending paths rooted at nodes n 1 and n 2 : C(n 1 , n 2 ) can be computed in polynomial time by the following recursive rules: Rule 1: If n 1 and n 2 have different labels (e.g., "DT" versus "NN"), then C(n1, n2) = 0; Rule 2: Else if n 1 and n 2 have the same labels and are both pre-terminals (POS tags), then where term(n) is the terminal symbol under n; Rule 3: Else if n 1 and n 2 have the same labels and they are not both pre-terminals, then: where children(m) are the child nodes of m. As in other tree kernel approaches (Collins and Duffy, 2001;Moschitti, 2006), we use a discount parameter λ to control for the disproportionately large similarity values of large tree structures.
rule 2 becomes: and rule 3 becomes: Note that Eq.