Automatic Cost Estimation for Tree Edit Distance Using Particle Swarm Optimization
By Yashar Mehdad. 2009
40 citations recorded by the source corpus.
Recently, there is a growing interest in working with tree-structured data in different applications and domains such as computational biology and natural language processing. Moreover, many applications in computational linguistics require the computation of similarities over pair of syntactic or semantic trees. In this context, Tree Edit Distance (TED) has been widely used for many years. However, one of the main constraints of this method is to tune the cost of edit operations, which makes it difficult or sometimes very challenging in dealing with complex problems. In this paper, we propose an original method to estimate and optimize the operation costs in TED, applying the Particle Swarm Optimization algorithm. Our experiments on Recognizing Textual Entailment show the success of this method in automatic estimation, rather than manual assignment of edit costs.
Subfields: Artificial Intelligence, Molecular Biology, Mathematical Optimization, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Andreas Vlachos
- Sebastian Riedel
- Ion Androutsopoulos
- Prodromos Malakasiotis
- Ido Dagan
- Amrith Krishna
- Asher Stern
- Ariel Felner
In Molecular Biology
- Andreas Vlachos
- Ion Androutsopoulos
- Prodromos Malakasiotis
- Ariel Felner
- Asher Stern
- Roni Stern
- Amrith Krishna
- Sebastian Riedel
In Mathematical Optimization
- Ion Androutsopoulos
- Prodromos Malakasiotis
- Andreas Vlachos
- Ariel Felner
- Asher Stern
- Roni Stern
- Amrith Krishna
- Sebastian Riedel
In Algorithms & Complexity
- Ion Androutsopoulos
- Prodromos Malakasiotis
- Andreas Vlachos
- Ariel Felner
- Asher Stern
- Roni Stern
- Amrith Krishna
- Sebastian Riedel
Citations in the corpus
- ProoFVer: Natural Logic Theorem Proving for Fact Verification (2021, methodology): “Similar proof systems have used mutations in the form of tree-edit operations (Mehdad, 2009), transformations over syntactic parses (Heilman and Smith, 2010; Harmeling, 2009), knowledge-based transformations in the form of lexical mutations, entailment rules, rewrite rules, or their combinations (Ba”
- Efficient Search for Transformation-based Inference (2012, methodology): “These transformations were used by the open-source system EDITS (Mehdad, 2009), and by (Wang and Manning, 2010).”
- A Survey of Paraphrasing and Textual Entailment Methods (2009, background): “…or edge) with the minimum cost that turns one tree into the other.14 To obtain more accurate predictions, it is important to devise an appropriate inventory of operators and assign appropriate costs to the operators during a training stage (Kouylekov & Magnini, 2005; Mehdad, 2009; Harmeling, 2009).”