J.N.PECHERSKY, S.J.SOLOWIEV and G.M.SOLOWIEVA
THE PRINCIPLES OF EXPERT RECOGNITION SYSTEMS DESIGN
Institute of Mathematics and Computing Centre|
Moldavian SSR Academy of Sciences
Ul. Grosul 5, Kishinev
Received 25 March 1988|
Revised 1 June 1988
Keywords: Expert system; Knowledge representation; Alternative method.
The recognition devices (RD) and expert systems (ES) are united by one
problem: both ES and RD operate with objects which have insufficiently
formalized structures. In spite of attempts to generate strong
formalisms in the algorithms of pattern recognition, all those
algorithms are nevertheless concerned with heuristics. For example,
in the majority of the decision rules the alternative choices are
determined according to the threshold value selected by the expert.
In every recognition system with learning, an expert system is
obviously present. In other words the problems of recognition
as well as their formal ways of solving are accompanied, within
the context, based on concrete nonformal knowledge.
In spite of the definite proximity of the problems, which are
reserved simularity and analogous methodological aspects, RD and ES
have essential distinctions in their inner organization. In this
paper on the example of the expert system FIACR (designed in the
Institute of Mathematics of the Moldavian Academy of Sciences) the
considerations on the principles of construction systems are given.
2. THE EXPERT SYSTEM FIACR
The system FIACR makes possible the creation of interactive consulting
systems in such problem domains (PD) where the descriptions of external
attributes, intermediate statements and goal states may be represented
in the form of a set of attributes, having a finite number of
incompatible values. The ranges of possible values of attributes are
fixed in the knowledge base (KB) in the process of creation of the
problem domain models. The set of attributes is separated
in nonintersecting classes, which are called subsystems.
It is well known that attributes and their values are used for
the description of declarative knowledge. The possibility of
representing procedural knowledge in the system FIACR is connected
with the fact that particular attributes are identified with the names
of programs. When the system opens the value of such attributes by
the agency of logical inference, the interface with the user
interrupts for a while and the call of indicative program takes place.
In this case the value of the received attribute is passed
to the program as the argument.
The triplet of the form (SUBSYSTEM, ATTRIBUTE, VALUE) is called
the descriptor of property and is used for description of the
characteristics of the problem domain. The descriptors of properties
represent the particular case of statements incorporated in the KB.
So called flags form the singular class of statements.
The KB controls the work of ES by means of flags.
In the process of logical inference every statement is characterised by its state which may be changed. There are four characteristics of statements, corresponding to the four values of clot state in the system FIACR. The statements may be fixed (established), refuted, indefinite and conflicted. Most of the statements, including all descriptors of properties, are in an undefined state before the beginning of the consultation; the rest of the statements are considered as established a priori. The statements may be refuted or fixed after receiving information about the object of consultation. The case of conflicted state reflects the fact that there are two independent inferences in KB, one which refutes the statement and another which fixes it.
The KB of the system FIACR is created by means of accumulation of particular modules of knowledge. Every module unifies the limited set of statements, which is concerned with the rules of state computations. This system contains five standard types of modules: alternatives, inconsistencies, prohibitions, productions and modules of implication. From the theoretical point of view such sets of modules are abundant2; however, elimination of the abundance makes sense only at the level of KB implementation. It is advantageous in every way to extend the expressible power for knowledge representation in this case.
The module of alternative acts in two ways: it either refutes all the rest of the statements in the presence of only one statement which is fixed, or it establishes the statement, provided all the rest of the statements have been refuted. The alternative gives the complete row of paired incompatible properties, and for every object from PD exactly one property takes place. The modules of inconsistencies allows determination of the incomplete rows of incompatible properties, therefore only the first type of action of the alternative module is possible for them. The prohibition module refutes one statement from the statements included provided the rest are fixed.
The last two modules mentioned represent the different kinds of dependences "IF . . . THEN . . .". The module of implication allows refutation of one of the premises, provided the consequence is refuted and the rest of the sendings are established. For the production of such a rule, anything contrary is impossible. Usually the module of implication is used in order to determine in the KB causal consequences, having the character of law. But the production module is intended mainly to express singly directed and often subjective instructions.
Until now we have supposed implicitly that the model PD is described
by an indivisible assembly of attributes. However this assumption is
not very strong because for certain objects from the external world
some attributes may be absent. The traditional exit from this situation
consists in the following: in the range of attributes the special value
is reserved, this being interpreted as an indication of absence of the
attribute. In the system FIACR another method is used where to every
attribute of the KB is automatically ascribed the flag of existence of
the attribute. The application of such a flag allows, in particular,
the description in the KB of the hierarchical classifications of the
The "limited" version of the representation of some objects can be explained by the fact, that for such objects whole subsystems are absent. In this connection, for every subsystem of the KB the flag of existence of the subsystem can be set such that in the process of logical inference the subsystem acts as a specific module of knowledge. This module of knowledge establishes the flag of existence of the subsystem if and only if the flags of existence for all attributes included in this subsystem are established.
In every stage of consultation the system knows which attributes of given objects have guaranty, although the system may not know the exact values of these attributes. The set of such attributes make up the compulsory structure of the object. The ES asks and constructs the chains of logical inference. The compulsory structure is determined by the fixed flags of existence of the attributes.
The set of modules, which may be represented in the KB of the system, is divided into definite groups which we call expert groups. The expert group is characterised by a name and the flag of activation. In the general case the module used depends on two causes. First, it depends on the flag of activation of its group; and secondly, it depends on the flags of existence for attributes, which correspond to the descriptors of properties included in the module.
The role of attributes in the process of logical inference may be different. Some attributes are used as questions to the user. The values of the rest of the attributes are discovered only as a result of logical inference.
Some inferenced attributes are declared in the system as potentially possible goals of consultation. Generally speaking the user may be interested only in the values of some individual goal attributes. This circumstance must be taken into account when organizing the interface with the user. Therefore, for the goal attributes in the KB, so called flags of goals are created. In the stage of initialisation of the interface with the user, the system proposes specifying the goals for those attributes which at a given moment the user is interested in receiving consultation on and the rest of the flags of goals are in an undefined state.
The problem of the organization of the interface with the user as well as the problem of adequate knowledge representation is of great importance to the practical application of the system. In the system FIACR the interface with the user is founded on the mechanism of questionnaire changing. The questionnaire presents the group of the characteristics under observation. The flags of interrogation correspond to every one of such groups.
The means of interface control consist of two parts. The first part is concerned with the flags of interrogation, and the second part is the procedure of choice of the next questionnaire with the established flag of interrogation. This procedure is included in the system.
In the general case, when the information about all the
characteristics included in the questionnaire is received, the system,
at first, goes through the list of as yet unused questionnaires. In
order to continue the interface the first questionnaire with an
established flag of interrogation is selected. Therefore the order of
the following questionnaires determines their use.
The flags of interrogation are established by the modules of knowledge which are responsible for the control of the interface. The modules of control, besides the descriptors of properties, may use the flags of goals and the flags of existence. As a matter of fact, the modules controlling the interface reflect the process of generation of hypotheses about the state of the object of consultation, although the final conclusion of the system is formed by other modules-the modules of problem filling of the KB.
The interpretation of the KB content realises the software of the sysetm FIACR3. In the structure of software two components are distinguished. The first realises the regime of the expert which allows creation of the KB. The second is intended for the practical exploitation of ES in the user regime.
The systems KB is arranged in the files which have definite size and inner structure. Besides, used widely in the system are nontraditional means of interface organization, connected with the singularities of displays implementation. The special service block supports the physical organization of the KB. In particular, this block creates the empty structures of the KB and allocates them in memory.
The main method of ES design takes into account considerably the fact that the knowledge is described in the entry language of system FIACR, and is then put down in the KB by the translator. The main notational structures are based on the principle of the positional term interpretation. In other words, the description of the KB in entry language represents the linear sequence of modules. The whole description of the language is placed in documentation accompanying the description of the system FIACR.
The process of debugging the expert system demands operative correction of the KB. The means of correction includes use of the editor of the PD model, the editor of modules and questionnaires and also the block of reordering.
The editor of the model is intended for the modification
of the subsystems, the attributes and their values. Besides
the editor allows change of the role requisitions of attributes:
In every subsystem the combination of values is established
in order to simplify the process of requisites specification.
Every new attribute of the subsystem inherits these values.
The values of requisites for particular attributes may be
corrected if necessary.
- the type of values scale (enumerating or nominal);
- the relation of an attribute to a priori structure of an object (compulsory or noncompulsory);
- the role of attributes in the process of logical inference (observed or inferenced);
- the possibility of using an attribute as a goal attribute (goal or nongoal);
- the type of an attribute (procedural or declarative).
The editor of modules and questionnaires allows correction and
creation of available and new modules of knowledge. Special attention
is given to the procedure of building the modules, focussing on
presenting the information in such a form that every attribute with
its value occupies one line of the display. If the attribute demands
more than one line, then the editor will attempt to decrease the
lengths of the names by abbreviating them. In the extreme case, part
of the values are substituted by dots, and the system provides the
periodical renovation of the information. On the instruction of the
expert, the horizontal line may be displayed which allows separation
of the premises from the conclusions.
The procedure creating the module of knowledge looks for the expert as the process of manipulation by the strings-attributes and values as substrings is shown on the display. The set of editor functions relating to strings allows arrangement of them in necessary order and eliminates those strings which are of no interest at the given moment. Moreover, there are means for eliminating the superfluous values of attributes. It is established that just the method of creation of the modules promotes the most complete extraction of the knowledge of the expert. Therefore the procedure of the editor of modules carries out the functions of a method of extracting the expert's knowledge simultaneously.
Generally speaking, for the expert the order in which subsystems, attributes and modules are enumerated in KB is distant. This circumstance is connected with the fact that in particular applications there are traditional schemes of classification of the characteristics. The analogical remark remains true with respect to the flags. The block of reordering allows organization of any set of elements of the KB in the order needed.
The documentator included in the system FIACR is intended for inference of the modified modules according to the agreements of the entry language.
The user regime in the system FIACR is intended for including the ES in the process of the practical work of the problem specialists. The appeal to the ES for consultation takes place at the moment when the user understands the necessity of receiving the explanation of some complicated or disputed question.
The block of consultation supports the interface with the user. In a general case the consultation represents the sequence of the performances which consisting of a definite number of the questions of the system and the user's answers. The performance begins when the system proposes to the user to enlarge the expert groups structure taking part in the consultation. The exception is the choice of the expert groups structure with a request about the specification of the goals of the consultation.
In every question the system asks for the indication of the values of some attribute. The attribute may be used as a question if, at first, it is compulsory, if, at the second, it is the attribute under observation and is a nongoal characteristic, and at the third, if it has, at least, two elements in the range of the possible values in the given state. The task of the user at this time consists in giving the most exact values of the object characteristics. In the difficult cases multivalued responses are admitted where groups of values of characteristics are enumerated.
In the process of consultation, besides the direct answer on the question produced the user may apply to the system with the request to help or he can refuse to give the answer at all. The system then begins the next performance with the question at which the interruption had taken place.
The situation when the user receives the value demanded is
the normal ending of the consultation. In this case the system
outputs the resulting conclusion into a table with three columns:
in the first column is indicated the name of the subsystem, in
the second, the name of the goal attribute and in the third, the
From the theoretical point of view the ES may interrupt
the consultation when the set of questions is exhausted. As usual
the possibility of such an ending is explained by the imperfectness
of the knowledge system or the insufficiently definite answers of
the user. We note that the deadlock is not absolutely hopeless
because to the user remains the chance to include new expert groups
and to receive the consultation of the system by any means. When at
least one statement passes in the conflicting state, it leads to
the ultimate interruption of the consultation.
The main demand of ES is that the conclusions of the systems must be motivated. Moreover, the alternative of this thesis does not exist, as the knowledge of the system is subjective as a rule. The conclusion may be accepted, if the explanation received is satisfactory.
In the system FIACR the subsystem of the explanation is based on the interaction of two schemes. The first is the universal scheme of access to the statements of the KB. By means of this scheme the problem specialist may go through the hierarchial framework of the KB (subsystem-attribute-value; group-module, etc.). The second scheme is the scheme of the tracing which is allowed to go alone on the chain of reason-consequence bounds arising as a result of logical inference. In this case the subsystem remembers the route made by the user and provides the return to the particular points of this route. In the process of tracing the system, it shows to the user from time to time, some module of knowledge and explains its work in the particular situation.
In system FIACR the non-back-tracking procedure of the logical
inference is realised. The possibilities of returning to the particular
stages of the interface with the aim of correction or specification
of the answers are necessary in the consulting systems. As a consequence,
the software of the user regime includes the supplement block
of imitation which allows the opening of the whole motion of
the consultation to be carried out and the change of some answers.
Applying this block gives the possibility, in particular, of going
out of conflicts and deadlocks arising in the process of the consultation.
The system FIACR is realised in the language PASCAL.
The design and verification of the real possibilities of the system
have been carried out on the model problem concerning the diagnostics
of tomatoes. The KB of the ES contains about 600 modules of knowledge
and about 150 attributes of which about 100 are intended for
the description of external characteristics.
K.A.Najdenova and J.N.Pechersky,
Expert systems: state and problems,
preprint Inst. Mat. Akad. Nauk MSSR, Kishinev,
1987, 38 pp. (in Russian).
S.J.Solowiev and G.M.Solowieva,
"Problems on alternative methods for the knowledge
representation", Izv. Akad. Nauk SSSR.
Tehn. Kibern. 5 (1987) 80-92 (in Russian).
S.J.Solowiev and G.M.Solowieva, Expert system's shell
for minicomputers, preprint Inst. Mat. Akad. Nauk MSSR,
Kishinev, 1986, 36 pp. (in Russian).
Sergey J.Solowiev is a research scientist
at the Institute of Mathematics,
Moldavian Academy of Sciences, Kishinev.
He is a Moscow State University graduate.
In 1981 he received his Candidate's Degree (Ph.D.)
in computer science from the same university.
His research interests include artificial
intelligence, cognitive science and knowledge
representation. He has published about
Pechersky J.N., Solowiev S.J., Solowieva G.M.
The principles of expert recognition systems design
// International Journal of Pattern Recognition and
Artificial intelligence Vol.3 No.1 (1989) 113-119