Efficient Tree-based Approximation for Entailment Graph Learning
Berant, Jonathan and Dagan, Ido and Adler, Meni and Goldberger, Jacob

Article Structure

Abstract

Learning entailment rules is fundamental in many semantic-inference applications and has been an active field of research in recent years.

Introduction

Performing textual inference is in the heart of many semantic inference applications such as Question Answering (QA) and Information Extraction (IE).

Background

Until recently, work on learning entailment rules between predicates considered each rule independently of others and did not exploit global dependencies.

Forest-reducible Graphs

The entailment relation, described by entailment graphs, is typically from a “semantically-specific” predicate to a more “general” one.

Sequential Approximation Algorithms

In this section we present Tree-Node-F ix, an efficient approximation algorithm for Max-Trans-Forest, as well as Graph-Node-F ix, an approximation for Max-Trans-Graph.

Experiments and Results

In this section we empirically demonstrate that TNF is more efficient than other baselines and its output quality is close to that given by the optimal solution.

Conclusion

_ Learning large and accurate resources of entailment

Topics

ILP

Appears in 18 sentences as: ILP (21)
In Efficient Tree-based Approximation for Entailment Graph Learning
  1. Since finding the optimal set of edges respecting transitivity is NP-hard, they employed Integer Linear Programming ( ILP ) to find the exact solution.
    Page 1, “Introduction”
  2. (Berant et al., 2011) introduced a more efficient exact algorithm, which decomposes the graph into connected components and then applies an ILP solver over each component.
    Page 1, “Introduction”
  3. proved that this optimization problem, which we term Max-Trans-Graph, is NP-hard, and so described it as an Integer Linear Program ( ILP ).
    Page 2, “Background”
  4. Let 137;]- be a binary variable indicating the eXistence of an edge 73 —> j in E. Then, X = {mij : 73 7E j} are the variables of the following ILP for Max-Trans-Graph:
    Page 2, “Background”
  5. Since ILP is NP-hard, applying an ILP solver directly does not scale well because the number of variables is O( | V |2) and the number of constraints is O( | V|3).
    Page 2, “Background”
  6. Consequently, in (Berant et al., 2011), they proposed a method that efficiently decomposes the graph into smaller components and applies an ILP solver on each component separately using a cutting-plane procedure (Riedel and Clarke, 2006).
    Page 2, “Background”
  7. In LP relaxation, the constraint 307;]- E {0, 1} is replaced by 0 S 307;]- S 1, transforming the problem from an ILP to a Linear Program (LP), which is polynomial.
    Page 3, “Background”
  8. In these experiments we show that exactly solving Max-Trans-Graph and Max-Trans-Forest (with an ILP solver) results in nearly identical performance.
    Page 4, “Forest-reducible Graphs”
  9. An ILP formulation for Max-Trans-Forest is simple — a transitive graph is an FRG if all nodes in its reduced graph have no more than one parent.
    Page 4, “Forest-reducible Graphs”
  10. Therefore, the ILP is formulated by adding this linear constraint to ILP (l):
    Page 4, “Forest-reducible Graphs”
  11. This is dramatically more efficient and scalable than applying an ILP solver.
    Page 6, “Sequential Approximation Algorithms”

See all papers in Proc. ACL 2012 that mention ILP.

See all papers in Proc. ACL that mention ILP.

Back to top.

objective function

Appears in 5 sentences as: objective function (5)
In Efficient Tree-based Approximation for Entailment Graph Learning
  1. The objective function is the sum of weights over the edges of g and the constraint 137;]- + mjk — mik g 1 on the binary variables enforces that whenever 137; j = mjk = 1, then also 137;], = 1 (transitivity).
    Page 2, “Background”
  2. Then, at each iteration a single node v is reattached (see below) to the FRG in a way that improves the objective function .
    Page 4, “Sequential Approximation Algorithms”
  3. This is repeated until the value of the objective function cannot be improved anymore by reattaching a node.
    Page 4, “Sequential Approximation Algorithms”
  4. Clearly, at each reattachment the value of the objective function cannot decrease, since the optimization algorithm considers the previous graph as one of its candidate solutions.
    Page 5, “Sequential Approximation Algorithms”
  5. Thus, the ILP is formulated by adding the following constraints to the objective function (3):
    Page 6, “Sequential Approximation Algorithms”

See all papers in Proc. ACL 2012 that mention objective function.

See all papers in Proc. ACL that mention objective function.

Back to top.

distributional similarity

Appears in 3 sentences as: distributional similarity (3)
In Efficient Tree-based Approximation for Entailment Graph Learning
  1. Most methods utilized the distributional similarity hypothesis that states that semantically similar predicates occur with similar arguments (Lin and Pantel, 2001; Szpektor et al., 2004; Yates and Etzioni, 2009; Schoenmackers et al., 2010).
    Page 2, “Background”
  2. For every pair of predicates i, j, an entailment score wij was learned by training a classifier over distributional similarity features.
    Page 2, “Background”
  3. The data set also contains, for every pair of predicates i, j in every graph, a local score 87;], which is the output of a classifier trained over distributional similarity features.
    Page 7, “Experiments and Results”

See all papers in Proc. ACL 2012 that mention distributional similarity.

See all papers in Proc. ACL that mention distributional similarity.

Back to top.

gold standard

Appears in 3 sentences as: gold standard (3)
In Efficient Tree-based Approximation for Entailment Graph Learning
  1. We sampled 7 gold standard entailment graphs from the data set
    Page 4, “Forest-reducible Graphs”
  2. described in Section 5, manually transformed them into FRGs by deleting a minimal number of edges, and measured recall over the set of edges in each graph (precision is naturally 1.0, as we only delete gold standard edges).
    Page 4, “Forest-reducible Graphs”
  3. We evaluate algorithms by comparing the set of gold standard edges with the set of edges learned by each algorithm.
    Page 7, “Experiments and Results”

See all papers in Proc. ACL 2012 that mention gold standard.

See all papers in Proc. ACL that mention gold standard.

Back to top.

Linear Program

Appears in 3 sentences as: Linear Program (2) Linear Programming (1)
In Efficient Tree-based Approximation for Entailment Graph Learning
  1. Since finding the optimal set of edges respecting transitivity is NP-hard, they employed Integer Linear Programming (ILP) to find the exact solution.
    Page 1, “Introduction”
  2. proved that this optimization problem, which we term Max-Trans-Graph, is NP-hard, and so described it as an Integer Linear Program (ILP).
    Page 2, “Background”
  3. In LP relaxation, the constraint 307;]- E {0, 1} is replaced by 0 S 307;]- S 1, transforming the problem from an ILP to a Linear Program (LP), which is polynomial.
    Page 3, “Background”

See all papers in Proc. ACL 2012 that mention Linear Program.

See all papers in Proc. ACL that mention Linear Program.

Back to top.

optimization problem

Appears in 3 sentences as: optimization problem (3)
In Efficient Tree-based Approximation for Entailment Graph Learning
  1. (2010) formulated the problem of learning entailment rules as a graph optimization problem , where nodes are predicates and edges represent entailment rules that respect transitivity.
    Page 1, “Introduction”
  2. proved that this optimization problem , which we term Max-Trans-Graph, is NP-hard, and so described it as an Integer Linear Program (ILP).
    Page 2, “Background”
  3. Consequently, a natural variant of the Max-Trans-Graph problem is to restrict the required output graph of the optimization problem (1) to an FRG.
    Page 4, “Forest-reducible Graphs”

See all papers in Proc. ACL 2012 that mention optimization problem.

See all papers in Proc. ACL that mention optimization problem.

Back to top.

PDF available from www.aclweb.org.
Send us an email