Efficient Graph Kernels for Textual Entailment Recognition
Fundamenta InformaticaePublished 1 January 2011
Fabio Massimo Zanzotto, Lorenzo Dell’Arciprete, Alessandro Moschitti
Citations12
SJR quartileQ3
SJR score0.29
SNIP0.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A class of graphs, the tripartite directed acyclic graphs (tDAGs), which can be efficiently used to design algorithms for graph kernels for semantic natural language tasks involving sentence pairs are proposed and it is proved that the matching function is a valid kernel and empirically shown that its evaluation is still exponential in the worst case.
Abstract
One of the most important research area in Natural Language Processing concerns the modeling of semantics expressed in text. Since foundational work in Natural Language Understanding has shown that a deep semantic approach is still not feasible, curr
Keywords
Computer Science
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
C4.5: Programs for Machine Learning
23,665 Citations1992J. R. Quinlan
A complete guide to the C4.5 system as implemented in C for the UNIX environment, which starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting.
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
Building a Large Annotated Corpus of English: The Penn Treebank
7,528 Citations1993Mitchell P. Marcus
arXiv (Cornell University)Semantic Similarity Based on Corpus Statistics and Lexical Taxonomy
2,224 Citations1997Jay J. Jiang, David W. Conrath
Computational LinguisticsHead-Driven Statistical Models for Natural Language Parsing
1,860 Citations2003Michael Collins
Three statistical models for natural language parsing are described, leading to approaches in which a parse tree is represented as the sequence of decisions corresponding to a head-centered, top-down derivation of the tree.
Computational LinguisticsAutomatic Labeling of Semantic Roles
1,647 Citations2002Daniel Gildea, Daniel Jurafsky
Lecture notes in computer scienceThe PASCAL Recognising Textual Entailment Challenge
1,626 Citations2006Ido Dagan, Oren Glickman +1 more
A maximum-entropy-inspired parser
1,496 Citations2000Eugene Charniak
A new parser for parsing down to Penn tree-bank style parse trees that achieves 90.1% average precision/recall for sentences of length 40 and less and 89.5% when trained and tested on the previously established sections of the Wall Street Journal treebank is presented.
Éléments de syntaxe structurale
1,067 Citations1959Lucien Tesnière
WordNet::Similarity
817 Citations2004Ted Pedersen, Siddharth Patwardhan +1 more
WordNet::Similarity is a freely available software package that makes it possible to measure the semantic similarity and relatedness between a pair of concepts (or synsets).
Language<b>Meaning and grammar:</b> An introduction to semantics. By Gennaro Chierchia and Sally McConnell-Ginet. Cambridge, MA: MIT Press, 1990. Pp. xiii, 460. $29.95.
814 Citations1991Greg N. Carlson
This self-contained introduction to natural language semantics addresses the major theoretical questions in the field and introduces the systematic study of linguistic meaning through a sequence of formal tools and their linguistic applications.
Publication Server of Goethe University Frankfurt am Main (Goethe University Frankfurt)The CoNLL 2007 Shared Task on Dependency Parsing
662 Citations2007Joakim Nivre, Johan Hall +5 more
The logic of typed feature structures
607 Citations1992Bob Carpenter
The Seventh PASCAL Recognizing Textual Entailment Challenge.
578 Citations2008Luisa Bentivogli, Peter E. Clark +2 more
This paper presents the Seventh Recognizing Textual Entailment (RTE-7) challenge, which replicated the exercise proposed in RTE-6, consisting of a Main Task, a Main subtask aimed at detecting novel information; and a KBP Validation Task, in which RTE systems had to validate the output of systems participating in the KBP Slot Filling Task.
DIRT @SBT@discovery of inference rules from text
548 Citations2001Dekang Lin, Patrick Pantel
This paper proposes an unsupervised method for discovering inference rules from text, based on an extended version of Harris' Distributional Hypothesis, which states that words that occurred in the same contexts tend to be similar.
Espresso
535 Citations2006Patrick Pantel, Marco Pennacchiotti
Experimental results show that the exploitation of generic patterns substantially increases system recall with small effect on overall precision, and a principled measure of pattern and instance reliability enabling the filtering algorithm.
New ranking algorithms for parsing and tagging
505 Citations2001Michael Collins, Nigel Duffy
New learning algorithms for natural language processing based on the perceptron algorithm are introduced, showing how the algorithms can be efficiently applied to exponential sized representations of parse trees, such as the "all subtrees" (DOP) representation described by (Bod 1998).
ACM SIGKDD Explorations NewsletterA survey of kernels for structured data
450 Citations2003Thomas Gärtner
This survey describes several approaches of defining positive definite kernels on structured instances directly on the basis of areal vector space and thus in a single table.
The Graph Isomorphism Problem : Its Structural Complexity
401 Citations1993Johannes Köbler, Uwe Schöning +1 more
Measuring the semantic similarity of texts
352 Citations2005Courtney D. Corley, Rada Mihalcea
A method that combines word- to-word similarity metrics into a text-to-text metric is introduced, and it is shown that this method outperforms the traditional text similarity metrics based on lexical matching.
Natural Language EngineeringApplied morphological processing of English
347 Citations2001Guido Minnen, John M. Carroll +1 more
Two newly developed computational tools for morphological processing are described: a program for analysis of English inflectional morphology, and a morphological generator, automatically derived from the analyser, which are fast, being based on finite-state techniques, and robust, in that they are able to deal effectively with unknown words.
A study on convolution kernels for shallow semantic parsing
246 Citations2004Alessandro Moschitti
Novel convolution kernels for automatic classification of predicate arguments are designed and experiments on FrameNet data have shown that SVMs are appealing for the classification of semantic roles even if the proposed kernels do not produce any improvement.
Learning non-isomorphic tree mappings for machine translation
243 Citations2003Jason Eisner
This work reformulates synchronous TSG to permit dependency trees, and sketch EM/Viterbi algorithms for alignment, training, and decoding.
Methods for using textual entailment in open-domain question answering
232 Citations2006Sanda M. Harabagiu, Andrew Hickl
It is demonstrated how computational systems designed to recognize textual entailment can be used to enhance the accuracy of current open-domain automatic question answering (Q/A) systems.
Robust textual inference via graph matching
159 Citations2005Aria Haghighi, Andrew Y. Ng +1 more
A learned graph matching approach to approximate entailment using the amount of the sentence's semantic content which is contained in the text, which outperforms Bag-Of-Words and TF-IDF models.
Computational LinguisticsTree Kernels for Semantic Role Labeling
156 Citations2008Alessandro Moschitti, Daniele Pighin +1 more
Several kernel functions to model parse tree properties in kernel-based machines, for example, perceptrons or support vector machines are proposed and tree kernels allow for a general and easily portable feature engineering method which is applicable to a large family of natural language processing tasks.
Lirias (KU Leuven)Expressivity versus efficiency of graph kernels
151 Citations2003Jan Ramon, Thomas Gaertner
The trade-off between expressivity and efficiency of graph kernels is studied and a new graph kernel based on subtree patterns is proposed, arguing that while a little more computationally expensive, this kernel is more expressive than kernels based on walks.
ArXiv.orgA Robust Parsing Algorithm For Link Grammars
86 Citations1995Dennis Grinberg, John Lafferty +1 more
A robust parsing algorithm based on the link grammar formalism for parsing natural languages, a natural extension of the original dynamic programming recognition algorithm which recursively counts the number of linkages between two words in the input sentence that is able to run efficiently with cubic worst-case complexity.
Natural Language EngineeringA machine learning approach to textual entailment recognition
84 Citations2009Fabio Massimo Zanzotto, Marco Pennacchiotti +1 more
This paper proposes syntactic and shallow semantic feature spaces, which allow supervised machine learning algorithms to derive first-order rewrite rules from annotated examples, and compares them to standard ones.
Automatic learning of textual entailments with cross-pair similarities
71 Citations2006Fabio Massimo Zanzotto, Alessandro Moschitti
A novel similarity measure is defined between examples of textual entailments and it is used as a kernel function in Support Vector Machines (SVMs) to automatically learn the rewrite rules that describe a non trivial set of entailment cases.
Hierarchical directed acyclic graph kernel
62 Citations2003Jun Suzuki, Tsutomu Hirao +2 more
The proposed HDAG Kernel directly accepts several levels of both chunks and their relations, and then efficiently computes the weighed sum of the number of common attribute sequences of the HDAGs.
Lecture notes in computer scienceOverview of the Answer Validation Exercise 2007
55 Citations2008Anselmo Peñas, Álvaro Rodrigo +1 more
The exercise description, the changes in the evaluation with respect to the last edition and the results show an evidence of the potential gain that more sophisticated AV modules might introduce in the task of QA.
National Conference on Artificial IntelligenceRecognizing textual entailment using a subsequence kernel method
44 Citations2007Rui Wang, Günter Neumann
This work presents a novel approach to recognizing Textual Entailment by using machine learning techniques using a limited data set, no external knowledge bases, and no handcrafted inference rules to learn whether an entailment relation holds between two texts.
Robust Textual Inference using Diverse Knowledge Sources
42 Citations2005Rajat Raina, Aria Haghighi +8 more
A machine learning approach to robust textual inference is presented, in which parses of the text and the hypothesis sentences are used to measure their asymmetric “similarity”, and thereby to decide if the hypothesis can be inferred.
Fast and effective kernels for relational learning from texts
42 Citations2007Alessandro Moschitti, Fabio Massimo Zanzotto
An efficient computation of such models is provided by optimizing the dynamic programming algorithm of the kernel evaluation by defining a family of syntactic kernels for automatic relational learning from pairs of natural language sentences.
Discovering <i>asymmetric</i> entailment relations between verbs using selectional preferences
40 Citations2006Fabio Massimo Zanzotto, Marco Pennacchiotti +1 more
A novel method to detect asymmetric entailment relations between verbs using Word-Net as a gold standard and using this method, used in combination with other approaches, significantly increases the performance of entailment detection.
Information Processing & ManagementSatisfying information needs with multi-document summaries
39 Citations2007Sanda M. Harabagiu, Andrew Hickl +1 more
This novel framework for summarization has the advantage of producing highly responsive summaries, as indicated by the evaluation results.
Lecture notes in computer scienceExperimenting a “General Purpose” Textual Entailment Learner in AVE
4 Citations2007Fabio Massimo Zanzotto, Alessandro Moschitti
The use of a "general purpose" textual entailment recognizer in the Answer Validation Exercise (AVE) task and results show that entailment rules can be learned are quite promising and improvable in the future.