Maximal Consistent Interpretations of Errorful Data in Hierarchically Modeled Domains

Abstract

A method is presented for constructing maximal consistent intepretations of errorful data. The method appears applicable to many tasks (sP.eech understanding, natural language understan1iing, vision, medical diagnosis) requiring partial-matching of errorful data against complex, hierarchically defined patterns. The data is represented as symbolic structures (word sequences, line segment configurations, disease symptoms). Errors consist of missing data (unrecognized words, occluded lines, undetected symptoms) and extra (Rossibly inconsistent) data (incorrectly recognized words, visual noise, spurious symptoms). Data interpretations correspond to substructures of a hierarchy of predefined concepts. Constraints on consistent conceptual structures are embedded in the hierarchy. An implementation of the l'lethod has correctly interpreted errorful sets of sentence fragments recognized by the HEARSAY-II speech understanding sys tern. The implementation has also correctly interpreted typed-in ungrammatical sentences. Detailed examples illustrate operation of the method on real d.ata.