Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: RCRA 2009 Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
Article type: Research Article
Authors: Zanzotto, Fabio Massimo | Dell'Arciprete, Lorenzo | Moschitti, Alessandro
Affiliations: University of Rome “Tor Vergata”, Via del Politecnico 1, 00133 Roma, Italy. zanzotto@info.uniroma2.it; lorenzo.dellarciprete@gmail.com | Department of Information Engineering and Computer Science, Via Sommarive, 38123 Povo, (TN) Italy. moschitti@disi.unitn.it
Note: [] Address for correspondence: University of Rome “Tor Vergata”, Via del Politecnico 1, 00133 Roma, Italy
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, current research is focused on shallow methods combining linguistic models and machine learning techniques. The latter aim at learning semantic models, like those that can detect the entailment between the meaning of two text fragments, by means of training examples described by specific features. These are rather difficult to design since there is no linguistic model that can effectively encode the lexico-syntactic level of a sentence and its corresponding semantic models. Thus, the adopted solution consists in exhaustively describing training examples by means of all possible combinations of sentence words and syntactic information. The latter, typically expressed as parse trees of text fragments, is often encoded in the learning process using graph algorithms. In this paper, we propose 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. These model the matching between two pairs of syntactic trees in terms of all possible graph fragments. Interestingly, since tDAGs encode the association between identical or similar words (i.e. variables), it can be used to represent and learn first-order rules, i.e. rules describable by first-order logic. We prove that our matching function is a valid kernel and we empirically show that, although its evaluation is still exponential in the worst case, it is extremely efficient and more accurate than the previously proposed kernels.
DOI: 10.3233/FI-2011-400
Journal: Fundamenta Informaticae, vol. 107, no. 2-3, pp. 199-222, 2011
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl