Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
1999-11-19
2002-05-14
Davis, George B. (Department: 2122)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S045000, C706S050000
Reexamination Certificate
active
06389405
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of expert systems and, more specifically, to the field of expert system analysis through structured knowledge representation in single and parallel processing systems including those used for natural language processing
2. Description of the Related Art
A generalized expert system typically includes a language or system for processing instructions and a representation of the data required for the application domain. A system for understanding natural language input from a user additionally includes specific processing instructions for interpreting natural language input and specific data which describes the user's natural language. All of the above components interact tightly with one another, so that the design or selection of such components significantly affects the resulting system's efficiency, correctness, robustness, and extensibility to advanced hardware platforms.
Natural language systems have processed the disambiguation of user input (e.g. deciding which among many possibly similar and plausible interpretations of the user's input is correct) in numerous methods. An important aspect of each of those methods is to “prune” (e.g. reduce) the total number of candidate interpretations from an initial number which is quite large in a real-world implementation down to a very small number which is practical (e.g. time-efficient) to process. Those methods generally fall into two categories. The first defines criteria which each element of the input sentence must meet, usually by characteristics like number of arguments and in what part of a descriptive hierarchy it must reside (e.g. “x must be some kind of machine”). This method requires continuous and precise, time-consuming maintenance whenever an addition or change is made to the application domain's data. The other method utilizes massive statistical computations on existing text to find other words that are often used with a given word, for example “bank” may be used in one sense with “money” and in another sense with “river”. This method is unable to adapt to jargon or highly-specialized application domains while retaining reasonable recognition accuracy. Both of these methods have difficulties such as a decrease in speed of execution when the application domain is large (true for almost every commercial application) and poor success or uncertainty in understanding analogy, metaphor, and user input sentences which do not exactly conform to those expected by the system.
Current implementations for disambiguating natural language input typically are unable to utilize the parallel processing capabilities of multi-processor systems, and therefore create a processing bottleneck on advanced hardware.
The language or system for processing the specific natural language instructions is generally either frame-based, like most expert systems, or a series of sequential statements, often in a specialized language which has special data manipulation facilities like unification and list processing, such as LISP or Prolog.
Current expert systems are typically constructed as a series of “frames” which consist of the equivalent of an “IF” clause, describing the conditions under which this frame is true, and a “THEN” clause that describes the action to take when the “IF” clause is found to be true. Each frame is meant to contain an independent piece of knowledge about the application domain. If a variable, on which any frame depends, changes during execution, the entire frame is automatically placed on the “agenda” (execution list) to fully execute again. This is true whether or not that frame has previously executed. If the frame contains references to external modules written in a procedural language like C, which is usually needed for more complex actions than IF-THEN constructions, those modules are often unable to update the variables which affect the agenda. These expert systems are complex to program, difficult to extend into unique environments, and limited in their ability to combine knowledge from different sources, particularly during runtime.
Specialized languages like CLOS and Prolog do not automatically update any equivalent of an agenda when changing a variable, so that they are unable to have other instructions which depend on that variable updated. Updating is accomplished via such methods as manually-written routines associated with each variable for which this updating is desired. Clearly, this is repetitive and time-consuming.
Certain specialized languages like Prolog have “unification”, or pattern-matching capabilities. Although such systems are somewhat flexible they are very slow in execution, so that special commands and programming methodologies need to be utilized to minimize the amount of unification that is actually done. Thus, these languages result in slow response times and are difficult to expand to large applications.
An issue with current implementations of both expert systems and unification-based languages is the need to introduce some level of sequencing of execution for the purposes of efficiency, initialization, grouping of similar procedures, and ease of constructing the data and instructions for the application. Examples of these are knowledge islands and execution priorities in expert systems and Prolog's backtracking. This added-on sequencing defeats or overrides the automatic features described above and creates a requirement for much greater training and expertise for those who build the application knowledge. This requirement for sequencing also makes executing such a language or expert system ineffective on a multiprocessor computer system (utilized for any application, not just natural language), since the frames or unifications are no longer independent time-wise. This sequencing also makes maintenance more difficult and error-prone, since the time dependencies in current implementations are hidden and inconsistent with the model of supposedly independent pieces of knowledge about the application domain.
Many natural language systems use separate storage and processing methods for data describing linguistic properties of words and for data describing the application domain. Frequently, natural language understanding systems utilize completely separate processing steps, where the linguistic analysis produces an output structure describing the sentence which is then used as input by the independent application domain analysis. Both the data separation and the processing separation introduce inefficiencies in processing and reduced accuracy in understanding the natural language command. This separation also makes the creation and updating of the data for an application more complex because information about a single entity in the application domain must be described in two different places with very different methods. This requires a person with significant expertise in linguistics as well as a person with knowledge of the application domain to design and implement the application. Historically, these have been different persons each with specialized training in their area of expertise and this dichotomy continues to be enforced by the development tools provided with current expert systems and natural language systems.
The data required for natural language understanding systems and general expert systems is complex for large commercial projects. This data is typically represented by some combination of lists, structures, and pointers from one data structure to another, with different types of data being represented by different specialized structures. In most systems, data and executable instructions are also represented in very different formats. This proliferation of formats reduces generality and efficiency, limits extensibility, and restricts the access of one type of data while processing another type of data. The proliferation also makes creation of the data more complex, particularly when lists of alternatives and multiple constraints for each alternative are desi
Herrera Peter J.
Oatman Robert K.
Sanouillet Remy D.
Zimmerman Charles E.
Davis George B.
Fenwick & West LLP
YY Software Corporation
LandOfFree
Processing system for identifying relationships between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processing system for identifying relationships between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing system for identifying relationships between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2885011