rehbold@uklirb (Robert Rehbold AG Richter) (04/24/89)
When I visited a workshop on diagnostic expert systems some weeks ago the discussion came to the topic of a "good and expressive" measure for the size and complexity of an expert system. Most participants disliked the idea to use the number of rules as the only characterization even for purely rule-based systems, since some systems use variables in their rules and some don't, thus needing a rule for each possible value of each variable. Some other interesting criterions may be - number and complexity of the database objects - in diagnosis: number of symptoms used and diagnoses included - ability to explain - ... In the March issue of the CACM V.E.Barker and D.E.O'Connor give a case study on "XCON and beyond". As a characterization of the X... expert systems the mention not only the rule counts and type (OPS-5), but also the average number of condition and action elements per rule. Moreover they give the average number of attributes per condition element and the size and attribute-per- object complexity of the database. This description seems sufficient, since most readers will know OPS-5 and its expressiveness. Difficulties may arise when using not-so-common rule systems or expert systems not mainly based on rules, such as model-based systems (i.e. systems that draw their conclusions from knowledge of structure, function and behavior). I would like to start a discussion on what YOU think a "good" measure for expert system complexity. Maybe we should stick to rule-based systems first, but ideas for a more general measurement are welcome too! Since this is comp.ai.shells, we should also discuss the influence of different shells on the solutions of a given problem, which may be quite different in approach and complexity. Robert Rehbold | e-mail: rehbold@uklirb.UUCP or ..!mcvax!unido!uklirb!rehbold | | real name: Robert Rehbold, University of Kaiserslautern | | Department of Computer Science | | PO-Box 3049, D-6750 Kaiserslautern, West-Germany |
roberts@studguppy.lanl.gov (Doug Roberts) (04/25/89)
In-reply-to: rehbold@uklirb's message of 23 Apr 89 17:40:02 GMT Sorry if duplicates of this appear. inews seems to be reluctant in accepting this... In article <4638@uklirb.UUCP> rehbold@uklirb (Robert Rehbold AG Richter) writes: > In the March issue of the CACM V.E.Barker and D.E.O'Connor give a case study on > "XCON and beyond". As a characterization of the X... expert systems the > mention not only the rule counts and type (OPS-5), but also the average number > of condition and action elements per rule. Moreover they give the average > number of attributes per condition element and the size and attribute-per- > object complexity of the database. This description seems sufficient, since > most readers will know OPS-5 and its expressiveness. Difficulties may arise > when using not-so-common rule systems or expert systems not mainly based > on rules, such as model-based systems (i.e. systems that draw their > conclusions from knowledge of structure, function and behavior). > I believe that the number of objects in an object oriented shell environment is also an important measure of an expert system's complexity. Also, some AI shells like KEE (Knowledge Engineering Environment) allow the use of user written methods (LISP code) within the body of a rule. Therefore, I feel the following comprises a more comlete list of the measures of an expert system's complexity: 1. The number of objects being manipulated by the system 2. The number of attributes of each object 3. The number of rules in the system 4. The number of condition and action elements per rule 5. The amount of user written code required to support the application --Doug -- =============================================================== Douglas Roberts Los Alamos National Laboratory Box 1663, MS F-602 Los Alamos, New Mexico 87545 (505)667-4569 dzzr@lanl.gov ===============================================================
u-dmfloy@ug.utah.edu (Daniel M Floyd) (04/25/89)
In article <4638@uklirb.UUCP> rehbold@uklirb (Robert Rehbold AG Richter) writes: >I would like to start a discussion on what YOU think a "good" measure for >expert system complexity. I think complexity could be measured by the number and type of operations to be performed and whether or not parts are free or bound. I don't know about what the trade off would be. For example, Something with a (or this that) would rank lower than a (and this that) because in the first case the rule is less restrictive than the second, unless we start to deal with unbound conditions. (or this that) would be *more* restrictive than an (and this _unboundThat) because here the second case clearly could fire on several cases. It is hard to say if it *will* match more, but I think the complexity is higher for the bound case. I think that a (not _unboundThis) is more restrictive than a (_unboundThis) because it limits the number of choices severely in the first case while providing many choices in the second. "If and only if" consturcts obviously would be more restrictive than simple "if". Like I said I don't know about the trade off - I'm refering to combinations. I think it would be some sort of inversion or square maybe for the nots, multiply for ands, and addition for ors, while treating unbounds as ors. So, to give some 'value' to it, supose we have (done in FROLIC a prolog like syntax): (*- (exist a b)) ;This trivial data base is here just to get the idea. (*- (exist c d)) ;It has nothing to do with complexity ... yet. (?- (exist a b) (exist x y)) ; Complexity = ; (exist a b) = 3 ; (exist x y) = 3 ; total = 3 * 3 = 9 (?- (or (exist a b) (exist x y))) ;I think I goofed on syntax, but you get the idea. ; Complexity = 3 + 3 = 6 (?- (exist a b) (not (exist x y))) ;Syntax? ; Complexity = 3 * (square 3) = 27 (?- (exist a _b)) ;Complexity = 2 (?- (exist a b) (not (exist x _unbound))) ;Syntax? ; Complexity = 3 * (square 2) = 12 We could also throw in a factor for each predicate so that the more facts there are to match a predicate, the less complex the predicate itself is deemed. Thus exist would get maybe a factor of -2 since it has 2 facts while (a-no-fact-predicate) might get 0 since it has no facts to work with. Ops5 rules or any other system would have similar ranking system. There's my half-baked 2 cents worth. Dan Floyd 8<D=