Advanced Computational Methods

The uK project is experimenting with a number of computational techniques which aim to make it an efficient processor and, perhaps more importantly, a robust one which can handle a wide variety of input language, even language not specifically anticipated in the lexicon.

In addition to the microtheories that will be developed in the coming months to address specific language problems, the analyzer utilizes an opportunistic, ``bulletin-board'' processing scheme which takes advantage of the following computational techniques:

1. Dependency Analysis. The key difficulty in natural language processing is the complex interplay of constraints present in even the simplest texts. Choosing one particular sense of a word may seem locally optimal, but it may create problems elsewhere which may ultimately lead to failure. In fact, in a typical problem, there are chains of dependency, where one choice eliminates choices at other points, which in turn eliminates other choices, etc.. The solution to these difficulties is a dependency-directed analysis which systematically tracks dependencies (Beale 94, Beale and Nirenburg 95) and can 1) propagate related constraints forward automatically, 2) automatically detect inconsistent solutions, and 3) be used in failure processing to determine the cause of failures and suggest recoveries.

2. ``Best First'' Processing. uK uses statistical data to determine the most likely senses of the input words. These senses are tested first, and if a result that ``satisfices'' is obtained, processing ends. This ``best first'' approach is extended to every aspect of processing, including failure recovery and ambiguity resolution.

3. ``Failure Recovery'' Techniques. Failures can arise from various sources. The actual input text can contain spelling errors. The syntactic analysis which is the input to uK can be in error. The lexicon and/or ontology can be erroneous or lack needed information. The analyzer itself can make incorrect decisions. uK tries to deal with these problems by:
   • using the dependency analysis to see why failures occurred
   • checking for metonymic/metaphoric language
   • if missing slot fillers, positing gaps (ellipsis)
   • changing syntactic analysis, including trying different attachments
   • relaxing thresholds
   • ordering possible recoveries using a sophisticated ``best first'' approach.

4. Ambiguity Resolution. If the basic semantic constraints cannot fully disambiguate, uK can:
   • use collocational preferences stored in the lexicon
   • use statistical methods to determine the most likely meanings
   • allow the ambiguity to remain. Subsequent clauses combined with coreferences might resolve the problem.
   • apply attachment rules such as ``referential success'' and/or ``minimal attachment''
   • Use ``expectations'' to moderate. For instance, in the current example, if one of the ``adquirir'' senses expected an INSTRUMENT slot (which ``a-traves-de'' adds), favor that sense.