The Characteristic Error Approach to Conflict Resolution

1. INTRODUCTION

Conflict reeolution is the integration of alternate opinions about the state of the world into a single coherent world view. This operation is often performed by a separate entity (knowledge eource) specifically designed for this purpose. For example, a system which performs surface material classification in a remote sen· ing application may encounter conflicts when knowledge sources have differing opinions about the most appropriate classification of a given region. Remote sensing experts attempting to resolve these conflicts may employ such knowledge as ·the spectral signature of a road may have been shifted due to the presence of vehi­ cles or an oil slick on the surface· or ·a portion of the road may have been obscured by trees". Their approach to conflict resolution therefore consists of evaluating the cla&'lification errors which are most likely to occur in the given context.

Conflict resolution has been treated by a number of different authors who use various techniques and termi­ ?ology . such as reasoning about uncertainty or ·the mtegration of knowledge from disparate sources · [4]. Most of this work takes a numeric approach to conflict resolution using, for example, Bayesian or Dempster­ Schaefer techniques [5). However, Bayesian techniques assume the ability to generate a priori a table of condi­ tional probabilities (i.e. the probability of A given B), and only allow the source to posit a single probability at source is, to some extent, the best judge of its own per­ formance. The motivation for this becomes apparent if one considen the facton which are normally embedded in the process of developing any given expert system:

• The knowledge of the context in which it expects to operate; i.e., an expectation of the form which the environment will take and the types of interrela­ tionships that may occur.
• The type of boundary or limiting conditions it expects to encounter; i.e., what information can occur in the environment which is close to what is expected but is actually different.
• The type of misclassifications it postulates can occur; i.e., what information may be present in the environment that is often confused with the desired information.

Implementing the concept of characteristic error requires that each knowledge source posit an a priori estimate of the error classes which it might encounter. This estimate is an explicit ranking of its expectations for the immediately local context, and is independent of the strength of the knowledge source's opinion in any particular instance of its application. It is based only upon the expert's knowledge of the underlying structure of its environment and decisions. For example, a region growing knowledge source, designed for road finding within an image understanding system, will know that local classification error may occur because a portion of the road may be partially obscured by trees. By the same token, it will also be aware of the fact that it is very uncharacteristic for any region designated as deep water to actually be a road. The same source will, how­ ever, have no real opinion as to the likely misclassification of shallow water. These considerations are independent of its specific belief of the existence of roads in any particular instance.

This error class information is dependent only upon the context assJUIIed by the knowledge source. It is independent of the actual context of any particular instance in which the knowledge source is utilized. In other words, the knowledge source's characteristic error list explicitly states the context which was assumed to be part of the underlying structure of the environment dur­ ing knowledge acquisition. Therefore, no a priori con­ trols need be imposed upon the overall system using the knowledge source, since all context information is expli­ citly stated by the knowledge source itself.

To illustrate these points, Table 1 shows the struc­ ture of two road finden. The road finder which anticipates being called upon to process satellite information might expect partial road covering by treetops. The ground level road finder on the other hand, has no expectation of such a conflict.

Such a priori identification of erron also promotes the graceful performance degradation of a group of knowledge sources, if and when any knowledge source is operating outside of its area of expertise. A source operating in an unfamiliar area should not have the conflicting class appearing anywhere in its characteristic error list. This absence serves as an immediate flag for the conflict resolver to investigate the situation further.

The minimum implementation of the characteristic error technique requires the following information:

• The characteristic a priori erron expected to be encountered by the knowledge source in the environment
• The knowledge source's strength of opinion in a particular instance .
• A methodology for evaluating the error list and determining the context.

The system works by comparing the characteristic error lists of the conflicting knowledge sources. This deter­ mines the conflict's local context. This context is, in essence, an indicator of the similarity and structure of these error lists. The implementation is such that similar error lists create a context controlling the relative strength of opinion necessary from the knowledge sources to alter a decision. For example, if all sources agree that a given error is characteristic of the situation, it will not take a large (absolute) opinion strength to ahift the decision in another direction. By the same token, if the context is relatively incoherent, a knowledge source's opinion must be stronger for the opinion to change. The interaction of these two facton is the basis for the implementation of the most likely error approach.

The items listed above serve as basic information for knowledge (rule) based management of the conflict. However, given the existence of a central (top level) conflict resolving system, additional rule based manipula­ tion is possible. The rules used for this manipulation/management of the conflict will be specific to a given system, and perhaps even a specific instance of its use. It should be noted that these manipulations

• Sidewalb would not appear on the overhead expert due to lack of reaolution

require no overall ranking of the knowledge sources in the system. Their general thrust is to drive the system results in a specific direction thereby establishing a stra­ tegy for the system. This strategy embodies more gen­ eral criteria i.e. always err on the side of caution. Stra­ tegy setting is implemented by moving error terms from characteristic to uncharacteristic or neutral, thereby altering the source's a priori opinion toward this error type.

3. AN APPLICATION OF CHARACTERISTIC ERROR

This section presents an example application of the characteristic error concept. The focus of our applica­ tion is T ASC's Multi-Spectral Image Analysis System (MSIAS) [3]. MSIAS is a knowledge-based system that interprets cartographic surface attributes using information obtained from remotely sensed imagery. The MSIAS classifier utilizes the relative spectral signa­ ture of an individual pixel location (i.e., its relative inten­ sity in various spectral bands). to determine its surface material class e.g. concrete, vegetation, water. Conflicts will only . occur when new knowledge sources, using other criteria, are introduced into the system. These knowledge sources may start with the latter spectral identification, but may base their own classification opin­ ion upon some alternate criteria (e.g. structural meas­ ures). The important feature of these knowledge sources is that they use the same initial information (the spectral classification), but apply independent criteria to obtain their individual results. These results generate alternate possible classifications for any given pixeVregion. In the example below, alternate classifications represent the conflicts. The process of obtaining a final classification is conflict resolution. Using the nomenclature of Clancy [1] this is a problem of heuristic classification.

It is planned that the conflict resolver will be activated late in the image classification process. The late activation occurs because a number of different knowledge sources must be polled for a conflict to occur. Conflict resolution is only applied to those objects which are the subject of conflicting opinions. The frequency of these conflicts will increase as the semantic level of the program increases. That is, the use of the resolver will be lower, on a percentage basis for pixels than for regions. Upon activation, the resolver first looks at the pixels/regions· immediately adjacent to the one currently under investigation and searches for other opinions as to this pixel's classification. Every adjacent pixel is marked with both a specific classification and characteristic error list. The list summarizes the characteristic error classes posited by the knowledge source which identified it. This information serves as the basis for conflict resolu­ tion, attempting to address such issues as:

• How do the other conflicts and their characteristic error classes relate to the identification of this pixel?

· Although the term pixela will be uaed few the remainder of the en. CUIIion, the proc:e~~ appliel equaDy to ~giona.

• Do they reinforce the current designation or con­ test it and in what way.
• The error classes may also be completely mute about this possible pixel classification.

As shown in Figure 1, a pixel can have up to eight nearest neighbors in a digitized image.

There are two extreme cases for the possible opin­ ions of these neighbors: First the original pixel classification (at x) may be a member of the ·uncharac­ teristic· error class of each and every neighboring pixel; second, the pixel's class appears in the ·characteristic· error class of all neighboring pixels.

In the first case, the conflict resolver would not, under any circumstances, alter the pixel's classification, as as all of the knowledge sources agree that it is unlikely that this pixel is misclassified. Therefore, even if all knowledge sources felt that their regions were worthy of extension, no regions would be extended as they all have preagreed to abide by this pixel designation. That is, they have all agreed that an ·x- class pixel is both something which they expect to see in the environment and something which could be a boundary of their regions. This corresponds to the general case in which an expert would say W{ use x as an indicator of this con­ dition, y is an indicator of an other condition, x and y are rarely confused·.

In the second case however, the conflict resolver will change the classification of this pixel to the compet­ ing class with the highest relative likelihood (opinion strength). Such a change will occur even if the relative likelihood is fairly low in an absolute sense. This is because there is complete agreement that initial misclassification of this pixel is often characteristic of the situation. This corresponds to the general case in which an expert would say W{ use x as an indicator of this con­ dition, however y is often confused with x, so if you have doubts about y you may also use it as an indicator-.

Fundamentally, the characteristic error paradigm gives one a methodology for juggling cases intermediate between these two extremes. For example, for seven neighbors to agree is less strong a case than all eight, or if one bas the class on its uncharacteristic error list it can possibly be excluded.

There are three basic ways of performing this integration. The simplest method merely tabulates fre­ quency of appearance for the pixel class in question, combines the two frequencies (characteristic and uncharacteristic) and decides to go with the highest com­ bination of relative frequency and opinion strength.

This is a relatively simple approach with weights being heuristically determined.

The second approach judges the relative coherence of these opinions. For example, if three divergent region types had found that the class in question was on their characteristic error list, it is a stronger case for misclassification than if a single type of region bad reached the same conclusion three times. This approach attempts to compensate for systematic bias on the part of the experts.

The third method which might be considered involves merely discounting the opinion of any region having this class on its uncharacteristic error list. This is however not a valid method as in such a situation a region is actually giving a strong vote for retaining the current classification.

The characteristic error paradigm allows the extrac­ tion of information about the characteristics of the knowledge source itself. Fint, it is important to recall that although we have been discussing three classes there actually are four specific class lists in existence. The fourth class being the class(es) for which the structural knowledge source (region grower) was actually designed. For example, a road grower would have concrete/asphalt in this class, some other examples appear in Table 2.

The characteristic error class is a group of pixel identifications in which one would expect an error to occur in the environment. As shown in the table, if one was growing highways, it would be expected that some road areas may have been misclassified due to overhang­ ing trees, oil slicks etc. The ·uncharacteristic" error classes are the ones which are expected to form a hard boundary between the given class and an alternate. These would be such classes as deep water and rock for roads. Neutral classes are classes which may exist in the expected environment but about which no intelligent statement may be made i.e. very shallow water, patchy mow for roads etc.. As was discussed in section 2, manipulation of this list can be a significant action in and of itself and may also serve as an ideal place for chang­ ing context. For example, if we know that an area had recently been flooded, we would move shallow water to the characteristic error set for all low lying classes.

The explicit designation of the classes expected to occur in the environment has a very useful side effect: It is now possible to determine that a knowledge source is oper~ting outside of its area of expertise. For example, an atrport hangar area grower would expect fuel storage tanks appearing next to it as a hard boundary. The high­ way expert, on the other hand, would not expect such a structure in any immediately adjacent pixel*. Fuel storage tanks would therefore not appear anywhere on a highway grower's list of error classes; not in ·charac­ teristic· ·uncharacteristic" nor in ·neutral·. Therefore if the conflict resolution process retained the storage tank classification, the conflict resolver ·would disregard the results of the highway finder in the abutting region. It would then try to find alternate explanations of the region/pixel which it had designated as ·highway-, by eliminating the highway designation and asking for alter­ nate opinions.

· AU ~ c:ll:-' pertain to the c:harac:tcristic:a of immediately adja­ cent pmclalrcg~ona.

4. CONCLUSIONS/FUTURE WORK

The characteristic error paradigm allows for other types of contextural and programmatic information to be easily added to the system. For example, if it were very important to catch the existence of highways in a particular application, we would move more classes into the highway grower's ·characteristic· list. These actions alter the relative ·push· given to a particular classification and can substantially alter the final charac­ teristics of the classified image.

This paper presents a unique means of combining the opinions of divergent experts in a uniform manner using only their own a priori knowledge about their own characteristics. The characteristic error method is a planned enhancement to the MSIAS system. It is planned that the upgraded MSIAS will serve as the testbed for this technique, after it is given the ability to evaluate structural information.

ACKNOWLEDGEMENTS

The author wishes to thank M. J. Carlotto, J-M Pomarede, and V. T. Tom for comments on earlier drafts of this paper. Discussions with L. A. Staub and R.A. Upton were invaluable in refining the concept of characteristic error.

5. REFERENCES

1. ClaacJ, W .J., ·classlfleatioa Problem Soh·iag" Proceedings of tM Natio'fllll Conference on Artifidallntel­ ligence 1984.
2. Cohea, P.R., ·nearistic Reuoaiaa A boat Uacertaiat,: Aa Artificial latelllgeaee Approach· PhD. TMsis Stan­ ford University, Staaford Ca. 1983.
3. Ferraate, R.D., Carlotta, M.J., Pomarede, J.M., Balm, P.W., ·Malti.Spectral Image Aaal1lil S)'ltem· IEEE Conference on Applicatiotu of Artificial Intelligence December 1984.
4. 4 GarveJ, T. et al. ·Aa lafereace Tecbalqae For Iategrat­ ia& Kaowledp From Disparate Soarca" Proceedings Of TM Seventh InteT'fllltio'fllll Joint Conference On Artificial Intelligence. Vaacoaver, British Columbia, Caaada.
5. Shafer, G. A MatMmatical TMory of Evidence Priace­ toa Ualvenit, Pre., Priacetoa, New JeneJ. 1976.
6. Teaeabaam, J.M., aad Barrow, B.G., ~xperlmeata Ia Iaterpretatioa-Galded Segmeatatioa· Artificial Intelli­ gence Vol. 8 pp. 241- 274 1977.