Constraint Reasoning in Parsing

Constraint reasoning is used throughout the parsing process shown in Words to Knowledge. It starts as soon as the parse chain is created. Word objects are strung between PARSE operators using ANDPARSE operators, and they are linked to the base vocabulary and its structure, so each word object acquires all the alternatives available to it through its invocations and member functions. Constraint reasoning continues through the building of the semantic structure.

Constraint Reasoning in a dynamic environment full of hierarchies and relations takes on a rather different hue to the conventional approach, of compiling a program with sets on nodes for some static problem. Here, the structure is changing all the time, and in some places, properties are added due to context - the concept of only pruning excess alternatives is just too threadbare to handle the complexity of the situation. This fits with the overall approach - truth and falsity, existence and nonexistence, inclusion and exclusion - need to be handled symmetrically, and adding/pruning is no exception.

Parsing

Word Level

wordlevel.jpg (38540 bytes)

For many words, there are alternative parts of speech – "while" can be a noun, a verb, a (special kind of) adverb. These alternatives would complicate parsing, so as many as possible are removed with reference to the neighbouring words – if the word preceding "while" is "a", then "while" cannot be a verb or an adverb. What the PARSE operator does is first find every possible alternative that either side can be, then find every possible pair available from STRUCTURE templates (the templates can have from two to more than ten legs – only adjacent ones are checked by the PARSE operator).

The alternatives that have no match across the operator are removed. alternatives.jpg (33376 bytes)

While the diagram indicates that only two words are compared at a time, the change in alternatives is propagated out of the PARSE operator into its neighbour, so the cutting may propagate all along the chain, and become cumulative with other cutting. The result is that each word is compared with at least two words, and more if cutting crosses the operators.

The STRUCTURE templates are good at adding general cases, but are not good at enumerating a number of special cases that deviate from a general case. One operator (NOTCONSISTENT) behaves as a NOT rather than as an adder of possibilities. If it is encountered from one side, and would link to the other side of the PARSE, it is used to remove alternatives. For example, "being" can be a noun, a verb auxiliary or a present participle. If "being" is the first word in a sentence, then it cannot be a noun. Rather than have multiple structures for every possible case, it is easier to enumerate the few cases that are not possible.

Bridge Level

When cutting has settled at the word level, a control pin on the PARSE operator is signalled and it sends values to its symbol pin (pin 1) and to a BRIDGE operator connected to it. The BRIDGE operator looks for structures that would bridge to nearby symbols (a full match on all the symbols of each STRUCTURE is now performed, so there may be many fewer possibilities).

If no structure is found, the grammar is incomplete. If multiple structures are found, either they are insufficiently discriminatory or the sentence is ambiguous. If only one possible structure is found, a copy of the STRUCTURE is built across the PARSE symbols, and the STRUCTURE activates its own BRIDGE operator. The STRUCTURE also reduces the alternatives that the PARSE node is radiating for connection from the other direction, to reflect the symbol it has taken up on one side. Only alternatives that can link to that symbol can be permitted to remain.

At the next level up, symbols on top of structures normally only have one value (see ADDPROPERTY), but they also acquire alternatives for matching against other structures, and these alternatives need to be constrained to match any connection already made.

An example of constraint reasoning at the structure level, where there are multiple InterimVerbPhrases, only one of which can be the active verb -

The tenant evicted by the manager charged with fraud sued for damages.

There are multiple possibilities for the active verb - a structure is built and used to disambiguate the sentence.

evicted.jpg (154276 bytes)

All possibilities that could be pruned without building have been done so - "fraud" can't be a subject of "sued". Some things "fit" better - a tenant can be evicted, but not  a manager. As each InterimVerbPhrase is tried in turn as an active verb, the consequences are evaluated - a preposition cannot connect across the verb, but can across a participial.

See Cutting and Healing for how the parse chain is cut and changed. See INSERTMARKER for how new symbols are added into the parse chain.

Prepositional Maps are another area where Constraint Reasoning is used.

Conclusion

As one would expect, Constraint Reasoning is occurring at many levels in the parsing process. The process relies on putting in every possible alternative, then taking most of them out again by using reasoning from general cases implemented as structure templates, or by looking up special cases that are accessed based on word combinations. Of course, Constraint Reasoning would be of little use without simultaneous topological manipulation, and that would be of little use without...

See Active Structure Grammar

Dynamic Constraint Reasoning for Prepositions

        NLP