Efficient kernels for sentence pair classification

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 91–100, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Efficient kernels for sentence pair classification Fabio Massimo Zanzotto DISP University of Rome “Tor Vergata” Via del Politecnico 1 00133 Roma, Italy zanzotto@info.uniroma2.it Lorenzo Dell’Arciprete University of Rome “Tor Vergata” Via del Politecnico 1 00133 Roma, Italy lorenzo.dellarciprete@gmail.com Abstract In this paper, we propose a novel class of graphs, the tripartite directed acyclic graphs (tDAGs), to model first-order rule feature spaces for sentence pair classifi- cation. We introduce a novel algorithm for computing the similarity in first-order rewrite rule feature spaces. Our algorithm is extremely efficient and, as it computes the similarity of instances that can be rep- resented in explicit feature spaces, it is a valid kernel function. 1 Introduction Natural language processing models are generally positive combinations between linguistic models and automatically learnt classifiers. As trees are extremely important in many linguistic theories, a large amount of works exploiting machine learn- ing algorithms for NLP tasks has been developed for this class of data structures (Collins and Duffy, 2002; Moschitti, 2004). These works propose ef- ficient algorithms for determining the similarity among two trees in tree fragment feature spaces. Yet, some NLP tasks such as textual entail- ment recognition (Dagan and Glickman, 2004; Dagan et al., 2006) and some linguistic theories such as HPSG (Pollard and Sag, 1994) require more general graphs and, then, more general al- gorithms for computing similarity among graphs. Unfortunately, algorithms for computing similar- ity among two general graphs in term of com- mon subgraphs are still exponential (Ramon and G¨artner, 2003). In these cases, approximated al- gorithms have been proposed. For example, the one proposed in (G¨artner, 2003) counts the num- ber of subpaths in common. The same happens for the one proposed in (Suzuki et al., 2003) that is applicable to a particular class of graphs, i.e. the hierarchical directed acyclic graphs. These algo- rithms do not compute the number of subgraphs in common between two graphs. Then, these al- gorithms approximate the feature spaces we need in these NLP tasks. For computing similarities in these feature spaces, we have to investigate if we can define a particular class of graphs for the class of tasks we want to solve. Once we focused the class of graph, we can explore efficient similarity algorithms. A very important class of graphs can be de- fined for tasks involving sentence pairs. In these cases, an important class of feature spaces is the one that represents first-order rewrite rules. For example, in textual entailment recognition (Da- gan et al., 2006), we need to determine whether a text T implies a hypothesis H, e.g., whether or not “Farmers feed cows animal extracts” entails “Cows eat animal extracts” (T1, H1). If we want to learn textual entailment classifiers, we need to exploit first-order rules hidden in training in- stances. To positively exploit the training instance “Pediatricians suggest women to feed newborns breast milk” entails “Pediatricians suggest …

Content truncated to 500 words