Coverage for nltk.sem.hole : 25%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
# Natural Language Toolkit: Logic # # Author: Peter Wang # Updated by: Dan Garrette <dhgarrette@gmail.com> # # Copyright (C) 2001-2012 NLTK Project # URL: <http://www.nltk.org> # For license information, see LICENSE.TXT
An implementation of the Hole Semantics model, following Blackburn and Bos, Representation and Inference for Natural Language (CSLI, 2005).
The semantic representations are built by the grammar hole.fcfg. This module contains driver code to read in sentences and parse them according to a hole semantics grammar.
After parsing, the semantic representation is in the form of an underspecified representation that is not easy to read. We use a "plugging" algorithm to convert that representation into first-order logic formulas. """
ExistsExpression, IffExpression, ImpExpression, LambdaExpression, NegatedExpression, OrExpression)
# Note that in this code there may be multiple types of trees being referred to: # # 1. parse trees # 2. the underspecified representation # 3. first-order logic formula trees # 4. the search space when plugging (search tree) #
EXISTS: lambda v,e: ExistsExpression(v.variable, e), NOT: NegatedExpression, AND: AndExpression, OR: OrExpression, IMP: ImpExpression, IFF: IffExpression, PRED: ApplicationExpression}
""" This class holds the broken-down components of a hole semantics, i.e. it extracts the holes, labels, logic formula fragments and constraints out of a big conjunction of such as produced by the hole semantics grammar. It then provides some operations on the semantics dealing with holes, labels and finding legal ways to plug holes with labels. """ """ Constructor. `usr' is a ``sem.Expression`` representing an Underspecified Representation Structure (USR). A USR has the following special predicates: ALL(l,v,n), EXISTS(l,v,n), AND(l,n,n), OR(l,n,n), IMP(l,n,n), IFF(l,n,n), PRED(l,v,n,v[,v]*) where the brackets and star indicate zero or more repetitions, LEQ(n,n), HOLE(n), LABEL(n) where l is the label of the node described by the predicate, n is either a label or a hole, and v is a variable. """ self.holes = set() self.labels = set() self.fragments = {} # mapping of label -> formula fragment self.constraints = set() # set of Constraints self._break_down(usr) self.top_most_labels = self._find_top_most_labels() self.top_hole = self._find_top_hole()
""" Return true if x is a node (label or hole) in this semantic representation. """ return x in (self.labels | self.holes)
""" Extract holes, labels, formula fragments and constraints from the hole semantics underspecified representation (USR). """ if isinstance(usr, AndExpression): self._break_down(usr.first) self._break_down(usr.second) elif isinstance(usr, ApplicationExpression): func, args = usr.uncurry() if func.variable.name == Constants.LEQ: self.constraints.add(Constraint(args[0], args[1])) elif func.variable.name == Constants.HOLE: self.holes.add(args[0]) elif func.variable.name == Constants.LABEL: self.labels.add(args[0]) else: label = args[0] assert label not in self.fragments self.fragments[label] = (func, args[1:]) else: raise ValueError(usr.node)
top_nodes = node_list.copy() for f in compat.itervalues(self.fragments): #the label is the first argument of the predicate args = f[1] for arg in args: if arg in node_list: top_nodes.discard(arg) return top_nodes
""" Return the set of labels which are not referenced directly as part of another formula fragment. These will be the top-most labels for the subtree that they are part of. """ return self._find_top_nodes(self.labels)
""" Return the hole that will be the top of the formula tree. """ top_holes = self._find_top_nodes(self.holes) assert len(top_holes) == 1 # it must be unique return top_holes.pop()
""" Calculate and return all the legal pluggings (mappings of labels to holes) of this semantics given the constraints. """ record = [] self._plug_nodes([(self.top_hole, [])], self.top_most_labels, {}, record) return record
""" Plug the nodes in `queue' with the labels in `potential_labels'.
Each element of `queue' is a tuple of the node to plug and the list of ancestor holes from the root of the graph to that node.
`potential_labels' is a set of the labels which are still available for plugging.
`plug_acc' is the incomplete mapping of holes to labels made on the current branch of the search tree so far.
`record' is a list of all the complete pluggings that we have found in total so far. It is the only parameter that is destructively updated. """ if queue != []: (node, ancestors) = queue[0] if node in self.holes: # The node is a hole, try to plug it. self._plug_hole(node, ancestors, queue[1:], potential_labels, plug_acc, record) else: assert node in self.labels # The node is a label. Replace it in the queue by the holes and # labels in the formula fragment named by that label. args = self.fragments[node][1] head = [(a, ancestors) for a in args if self.is_node(a)] self._plug_nodes(head + queue[1:], potential_labels, plug_acc, record) else: raise Exception('queue empty')
plug_acc0, record): """ Try all possible ways of plugging a single hole. See _plug_nodes for the meanings of the parameters. """ # Add the current hole we're trying to plug into the list of ancestors. assert hole not in ancestors0 ancestors = [hole] + ancestors0
# Try each potential label in this hole in turn. for l in potential_labels0: # Is the label valid in this hole? if self._violates_constraints(l, ancestors): continue
plug_acc = plug_acc0.copy() plug_acc[hole] = l potential_labels = potential_labels0.copy() potential_labels.remove(l)
if len(potential_labels) == 0: # No more potential labels. That must mean all the holes have # been filled so we have found a legal plugging so remember it. # # Note that the queue might not be empty because there might # be labels on there that point to formula fragments with # no holes in them. _sanity_check_plugging will make sure # all holes are filled. self._sanity_check_plugging(plug_acc, self.top_hole, []) record.append(plug_acc) else: # Recursively try to fill in the rest of the holes in the # queue. The label we just plugged into the hole could have # holes of its own so at the end of the queue. Putting it on # the end of the queue gives us a breadth-first search, so that # all the holes at level i of the formula tree are filled # before filling level i+1. # A depth-first search would work as well since the trees must # be finite but the bookkeeping would be harder. self._plug_nodes(queue + [(l, ancestors)], potential_labels, plug_acc, record)
""" Return True if the `label' cannot be placed underneath the holes given by the set `ancestors' because it would violate the constraints imposed on it. """ for c in self.constraints: if c.lhs == label: if c.rhs not in ancestors: return True return False
""" Make sure that a given plugging is legal. We recursively go through each node and make sure that no constraints are violated. We also check that all holes have been filled. """ if node in self.holes: ancestors = [node] + ancestors label = plugging[node] else: label = node assert label in self.labels for c in self.constraints: if c.lhs == label: assert c.rhs in ancestors args = self.fragments[label][1] for arg in args: if self.is_node(arg): self._sanity_check_plugging(plugging, arg, [label] + ancestors)
""" Return the first-order logic formula tree for this underspecified representation using the plugging given. """ return self._formula_tree(plugging, self.top_hole)
if node in plugging: return self._formula_tree(plugging, plugging[node]) elif node in self.fragments: pred,args = self.fragments[node] children = [self._formula_tree(plugging, arg) for arg in args] return reduce(Constants.MAP[pred.variable.name], children) else: return node
""" This class represents a constraint of the form (L =< N), where L is a label and N is a node (a label or a hole). """ self.lhs = lhs self.rhs = rhs if self.__class__ == other.__class__: return self.lhs == other.lhs and self.rhs == other.rhs else: return False return not (self == other) return hash(repr(self)) return '(%s < %s)' % (self.lhs, self.rhs)
if not grammar_filename: grammar_filename = 'grammars/sample_grammars/hole.fcfg'
if verbose: print('Reading grammar file', grammar_filename)
parser = load_parser(grammar_filename)
# Parse the sentence. tokens = sentence.split() trees = parser.nbest_parse(tokens) if verbose: print('Got %d different parses' % len(trees))
all_readings = [] for tree in trees: # Get the semantic feature from the top of the parse tree. sem = tree.node['SEM'].simplify()
# Print the raw semantic representation. if verbose: print('Raw: ', sem)
# Skolemize away all quantifiers. All variables become unique. while isinstance(sem, LambdaExpression): sem = sem.term skolemized = skolemize(sem)
if verbose: print('Skolemized:', skolemized)
# Break the hole semantics representation down into its components # i.e. holes, labels, formula fragments and constraints. hole_sem = HoleSemantics(skolemized)
# Maybe show the details of the semantic representation. if verbose: print('Holes: ', hole_sem.holes) print('Labels: ', hole_sem.labels) print('Constraints: ', hole_sem.constraints) print('Top hole: ', hole_sem.top_hole) print('Top labels: ', hole_sem.top_most_labels) print('Fragments:') for (l,f) in hole_sem.fragments.items(): print('\t%s: %s' % (l, f))
# Find all the possible ways to plug the formulas together. pluggings = hole_sem.pluggings()
# Build FOL formula trees using the pluggings. readings = list(map(hole_sem.formula_tree, pluggings))
# Print out the formulas in a textual format. if verbose: for i,r in enumerate(readings): print() print('%d. %s' % (i, r)) print()
all_readings.extend(readings)
return all_readings
for r in hole_readings('a dog barks'): print(r) print() for r in hole_readings('every girl chases a dog'): print(r)
|