Noise and Knowledge Acquisition

Manago, Michel; Kodratoff, Yves

Noise and Knowledge Acquisition

Download BibTeX Cite

Proceedings of the Tenth International Joint Conference on Artificial Intelligence. Knowledge Acquisition. Pages 348-353.

Abstract

In this paper we analyse how noise can affect Knowledge Acquisition from a Machine Learning perspective. We present some methods to detect and treat noise that goes beyond modulating numerical coefficients and show that noise cannot be viewed as a single entity. There are several different types of noise and noise is not only wrong Information.

Alexander et al, 1986) Alexander •. J. H. & Freiling, M. & Shulman, S. & Rehfuss S. & Mess1ck, S. . • "Oothologjcal Analysjs: An Ongojng Expenment_. . f!roc. of the 1st AAAI Workshop on Knowledge Acqws1t1on for Knowledge Based Systems, Banff (Canada) 1986.
Buchanan & Shortlife, 1984)
Buchanan, B. G. & Shortlife, E. H. IN E • t Rule-Based Expert Systems: The M_YC _ xpenmen s of the Stanford Heuristic Programmmg Project, Addisson-Westley 1984.
Charniak, 1977) Chamiak, E. "A framed Painting: The Representation of a Common Sense Knowledge Fragment," Cognitive Science, val 1 #4, pp. 355-394, 1977.
Clancey, 1986)
Clancey, W. "Transcript of plenarv session: Cognition and Expertise," 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.
Corlett, 1983)
Corlett, R. "Explaining induced decision trees." Proc. Expert Systems, pp. 136-142, 1983.
Fu & Buchanan, 1985) Fu, L. M. & Buchanan B. G. "Learnin9 Intermediate Knowledge in Constructing a Hierarchical Knowledge Base", working paper W KSL 85-4, Computer Science Deparment, Stanford University, 1985.
Fu, 1985)
Fu, L. M. "Learning Object Level and Meta Level Knowledge in Expert Systems," Phd dissertation, Department of Computer Science, Stanford University 1985.
Hayes, 1984)
Hayes, P. •~.in Formal Theories of the Commense World~ Hobbs, J. ed Ablex, Hillsdale 1984.
Kodratoff & Ganascia, 1986)
Kodratoff, Y. & Ganascia J.G. "Improving the Generalization Step in Learning," in Machine Learning 2 : An Artificial Intelligence Approach, Michalski R. S., Carbonell J. G., Mitchell T. M. eds, Morgan Kaufmann, Los Altos 1986. (Kodratoff et al, 1986) Kodratoff, Y. & Manago, M. & Blythe, J. S. & Smallman, C. & Andro, T. "Generalization in a Noisy Environment: the Need to Integrate Symbolic and Numeric TechniQues in Learning," Proc. of the 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.
Manago, 1986)
Manago, M. "Object-oriented Generalization: A Tool for Improving Knowledge Based Systems," Proc. of the 1st International Meeting on Advances in Learning, Las Arcs (France) 1986.
Manago & Kodratoff, 1987)
Manago, M. & Kodratoff, Y. "Model prtyen Learning of Disiunctive Concepts," Proc. of the second European Working Session on Symbolic Learning, Bled (Yougoslavia), 1987.
McDermott, 1986)
McDermott, J. "Transcripts of plenary session• Interactive Tools 1 ," 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.
Michalski & Chilauski, 1980)
Michalski, R.S . & Chilauski, R.L. "Learning by Being Told and Learning from Examples: An Experimental Comparison of the Two Methods of Knowledge AcQuisition in the Context of Qeyeloping an Expert System for Soybean Oisease Diagnosis," Policy Analysis and Information Systems, Vol 4:2, 1980. 354 KNOWLEDGE ACQUISITION (Minsky, 1975) Minsky, M. "A framework for representing knowledge," In Irul Psychology of Co"ieyter Vision, Winston P. H. ed , Me Graw~Hill, New Yo 1975. (Mitchell, 1985)
Mitchell, T.~. . . . .. "Genera!jzation as Search", '.n Readmg In ArtifiCial Intelligence, Webber, B.L., N1lsson, N.J. ads, Morgan- Kaufmann, Los Altos (CA), 1985.
Nilsson, 1984)
Nilsson, N.J. ~rinciples of Artificial Intelligence, Morgan-Kaufmann, Los Altos (CA), 1984. .
Pazzani, 1986)
Pazzani, M.J. "Explanation-Based Learning for Knowledge-Based ~vstems," Proc of the 1st AAAI Workshop on now/edge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.
Quinlan, 1983)
Quinlan, J. R. . "Learning efficient classification er_ocedy~s and thEW application to ches~ end games, 1n M~chme ~earnmg 1: An Artificiallntelhgence Approach, M1chalsk1 R. S., Carbonell J. G., Mitchell T. M. ads, Morgan Kaufmann, Los Altos 1983 (Quinlan, 1986)
Quinlan, J. R. "Simplifying decision trees," Proc. of the 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.
Regoczei & Plantinga, 1986) Regoczei, S. & Plantinga, E:.o. "Ontology and lnyentor:y: A Foundation for a Knowledge ACQuisition Methodology,"Proc of the 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.
Shank & Carbonell, 1979) Shank, R. & Carbonell, J. G . "Re: The Gettysbyrg Address• Representing Social and Political Acts," in Associative Networks• Representation and Use of Knowledge by Compyters Findler N. V. ed, Academic Press, New York 1979.
Smith & Medin, 1981)
Smith, E. & Medin, D. Categories and Concepts, Cambridge: Harvard University Press, 1981 .
Utgoff, 1986)
Utgoff, P.E. "Shift of Bias for Inductive Concept Learning," in Machine Learning 2: An Artificial Intelligence Approach, Michalski R. S., Carbonell J. G,, Mitchell T. M. eds, Morgan Kaufmann, Los Altos 1986. (Waltz, 1975)
Waltz, D. L. •~tandi~e Qrawing of Scenes with ShadOWS." in Psychology of Computer Vision,
Winston P. H. ed, Me Graw-Hill, New York 1975.
Winograd, 1972)
Winograd, T. Understanding Natyrallangyage, Academic Press, New York 1972.
Zucker, 1978)
Zucker, S. "Production Systems with Feedback." in Pattern Directed Inference Systems, Waterman D., Hayes-Roth F. ads, Academic Press, New York 1978.

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1 ') Randomness of natural phenomena

As surprising as it may sound, we do not consider this as being an important type of noise. Indeed, wh.en learning from examples we assume that the real hve case will occur in the training set and do not have to worry about this type of noise.

111.8. Wrong information

Wrong information is human intr?duc~d mist~kes. w_e assume that it is not due to unreliable mformat1on. Th1s can be:

2.a) Giving the wrong value to a descriptor

For example, the expert might be distracted when he write the description of an example

2.b) Describing a class and attributing the description to another

This can occur for the same reasons as 2.a. However, the effect for the learning system will be much worse.

2.c) Giving too many descriptors

This can haooen whRn n11r ~>voert uses bv mistake a piant which has several diseases as a reference for a specific disease. It can also happen when the plant presents natural imperfection with are not due to the disease and which are incorrectly identified as a symptom of the disease. Finally, it also happens because people mention concepts that are irrelevant for psychological reasons (Pazzani, 1986).

This can introduce inconsistencies in the knowledge base in which case we can easily detect it and request that the expert solve the problem. Otherwise, errors in the positive examples will cause over-generalizations (Fu, 1985).

A method to handle false positive and negative examples is to allow some uncertainty in the clusters or the rules. This numeric method has been succesfully used in RL (Fu, 1985) or by performing tree-pruning (Quinlan, 1986). In the last one, the error in classification introduced by tree pruning is lower than the error of trees that find total classifications.

2.d) Noise In the background knowledge

We are currently totally empty handed to detect or treat this type of noise. This might be detectable by analysing bad consultations (assuming we have a way of detecting bad consultations, which we do not).

III.C. Incomplete information

This can be:

3.a) Forgetting an example

By asking examples to several experts, this problem will be reduced since it is unlikely that all the experts forget the same example. However, as we have seen in section II.B the system checks that the conclusion he obtain match a full description of a concept and learns incrementally if it does not.

3.b) Forgetting a relevant descriptor

This can happen because of lack of attention, the concept is naturally noisy (see IV.A.) or is a default value (this is solved by inheriting properties in our frames) . It also happens that sometime people simply do not to mention relevant features for no apparent reasons (Pazzani, 1986).

By using questionnaires, we push the experts to give all the information.

3.c) Giving a value for a descriptor which Is too general

This can be treated in a similar manner as when the expert forgets the descriptor

3.d) High level concept Is "fuzzy"

This can be caused by the fact that the outcome of a test which is needed in order to discriminate between some diseases is unknown (lack of information, high cost associated with a test as in 1.d).

For example, finding which virus causes a disease requires some lab tests. The results of these lab tests will never be known by the person who uses the system. Hence, as far as the system is concerned, it IJ!ifl never be able to discriminate between different v1ral diseases. Our solution to the problem consists in collapsing the classes into a single one(VIRUS).

3.e) Missing background knowledge

This can be detected and treated when the experts review the characteristic descriptions that have been automatically generated. When. they disagree with th_e generalization, they must explam why and usually th1s generates new axioms on the domain.

Missing descriptors In the vocabulary Consider the following example:

E1 : [x:<ISA PLANT> <AGE MATURE>] & [spots1 : <1SA SPOT> <NUMBER SEVERAL> <COLOR WHITE> <FORM CONCAVE>] & [fruit1 <ISA FRUIT>] & [face1: <PART-OF fruit1 > <IS EXPOSED-TO-SUN>] ~ SUNBURN

E2: [x: <ISA PLANT> <AGE MATURE>] & [spots1: <ISA SPOT> <NUMBER SEVERAL> <COLOR YELLOW> <FORM CONCAVE>] & [fruit1 <ISA FRUIT>] & {face1: <PART-OF fruit1 > <IS EXPOSED-TO-SUN>] ~ SUNBURN

By climbing the generalization frame, one could conclude that a caracteristic description of SUNBURN is: there are light colored spots on the face of the fruit exposed to the sun.

CE: [x: <ISA PLANT> <AGE MATURE>] & [spots1: <ISA SPOT> <NUMBER SEVERAL> <COLOR GREY BEIGE> <EVOLUTE-INTO spots2> <FORM CONCAVE>] & {spots2: <ISA SPOTS> <COLOR BROWN>] & [fruit1 <ISA FRUIT>] & [face1: <PART-OF fruit1> <IS EXPOSED-TO-SUN>] & [leaves1: <ISA LEAVES>] & [symptom1: <ISA SYMPTOM>] ~ NARCOSIS-OF-FRUIT-EXTREMITY

Since grey-beige is also a light color, the ne!l~tive example is covered. Let us assume that the Ofl{/ln of the problem is the generalization of th~ color a~nbute, One can solve this problem by mtroducmg an intermediary level node G0001 in the frame such that WHITE and YELLOW are sons of G0001, G0001 is a son of LIGHT-COLOR and GREY-BEIGE is not a son of GOOD 1. The generalization then becomes COLOR(GOOO 1 ,spots 1) which rejects the negative example. This is similar to RL symbolization of taxonomy points (Fu & Buchanan, 1985) and shift of bias (Utgoff, 1986).

This might not be the optimal solution (try to find a meaning for GOOD 1 ). The correct solution (obtained through interraction with the experts) is that WHITE and YELLOW belong to another frame which had been overlooked, the TRANSLUCENT frame. WHITE and YELLOW are not only colors but they also color loss (when exposed too long to the sun, the colors fade away and become translucent). While in some case one can clearly see that the white or yellow is a color and not a color loss (this means that the preceeding solution does not hold), in some other cases it is more difficult (in other word, we cannot introduce two new colors such as TRANSLUCENT-WHITE and TRANSLUCENT-YELLOW).Of course, multiple links of this sort generate problems for inheriting properties.

In the present case (the SUNBURN disease), the fact there are no symptoms on leaves is also relevant while the fact that the color does not evolve into brown is not. The correct generalization will then be : there are translucent spots on the part of the fruits exposed to the sun and no symptoms on the leaves.

IV. CONCLUSION

When learning from noisy data, it is often though that nothing but numerical coefficients can take into account this uncertainty. We do not claim that one should never use statistical information, but that:

The symbolic approach to ML (for example the version space approach) may be usefull in noisy situation when noise comes from a lack of training examples
Cross-examination of expertise and comparison of users'descriptions with experts'description can filter noise.
finding good intermediary knowledge and knowledge representation, using domain specific knowledge, collecting examples by means of questionnaires can solve some types of noise
delaying unreliable tests as much as possible in a decision tree when building a decision tree can generate robust rules.
Each time noise is not of numeric nature, as presented in this paper, the introduction of coefficients may lead to some results but that these will not have any significance.

Acknowledgements

We wish to thank Jim Blythe and Rob Corlett at the General Electric Company, Thierry Andre at Cognitech and Jean Jacques Cann~t In our group for all the contribution they made to the work descnbe~ In this paper. Special thanks to Bruce Buchanan and to the Hehx group at Stanford University for the useful comments they have made on this research. The learning tools used for this research are implemented in COMMON LISP on a TI-EXPLORER Lisp machine and on a SUN 3/160 workstation.

Michel Manago, and Yves Kodratoff. 1987. Noise and Knowledge Acquisition. In Proceedings of the Tenth International Joint Conference on Artificial Intelligence, IJCAI-87. IJCAI, 348–353. https://ijcai.org/proceedings/1987/72

@inproceedings{ijcai1987p72,
  title     = {Noise and Knowledge Acquisition},
  author    = {Manago, Michel and Kodratoff, Yves},
  booktitle = {Proceedings of the Tenth International Joint Conference on
               Artificial Intelligence, {IJCAI-87}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {John McDermott},
  pages     = {348--353},
  year      = {1987},
  note      = {Knowledge Acquisition},
  url       = {https://ijcai.org/proceedings/1987/72},
}

TY  - CPAPER
TI  - Noise and Knowledge Acquisition
AU  - Manago, Michel
AU  - Kodratoff, Yves
T2  - Proceedings of the Tenth International Joint Conference on Artificial Intelligence, IJCAI-87
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1987
SP  - 348
EP  - 353
UR  - https://ijcai.org/proceedings/1987/72
ER  -

[1] Alexander et al, 1986) Alexander •. J. H. & Freiling, M. & Shulman, S. & Rehfuss S. & Mess1ck, S. . • "Oothologjcal Analysjs: An Ongojng Expenment_. . f!roc. of the 1st AAAI Workshop on Knowledge Acqws1t1on for Knowledge Based Systems, Banff (Canada) 1986.

[2] Buchanan & Shortlife, 1984)

[3] Buchanan, B. G. & Shortlife, E. H. IN E • t Rule-Based Expert Systems: The M_YC _ xpenmen s of the Stanford Heuristic Programmmg Project, Addisson-Westley 1984.

[4] Charniak, 1977) Chamiak, E. "A framed Painting: The Representation of a Common Sense Knowledge Fragment," Cognitive Science, val 1 #4, pp. 355-394, 1977.

[5] Clancey, 1986)

[6] Clancey, W. "Transcript of plenarv session: Cognition and Expertise," 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.

[7] Corlett, 1983)

[8] Corlett, R. "Explaining induced decision trees." Proc. Expert Systems, pp. 136-142, 1983.

[9] Fu & Buchanan, 1985) Fu, L. M. & Buchanan B. G. "Learnin9 Intermediate Knowledge in Constructing a Hierarchical Knowledge Base", working paper W KSL 85-4, Computer Science Deparment, Stanford University, 1985.

[10] Fu, 1985)

[11] Fu, L. M. "Learning Object Level and Meta Level Knowledge in Expert Systems," Phd dissertation, Department of Computer Science, Stanford University 1985.

[12] Hayes, 1984)

[13] Hayes, P. •~.in Formal Theories of the Commense World~ Hobbs, J. ed Ablex, Hillsdale 1984.

[14] Kodratoff & Ganascia, 1986)

[15] Kodratoff, Y. & Ganascia J.G. "Improving the Generalization Step in Learning," in Machine Learning 2 : An Artificial Intelligence Approach, Michalski R. S., Carbonell J. G., Mitchell T. M. eds, Morgan Kaufmann, Los Altos 1986. (Kodratoff et al, 1986) Kodratoff, Y. & Manago, M. & Blythe, J. S. & Smallman, C. & Andro, T. "Generalization in a Noisy Environment: the Need to Integrate Symbolic and Numeric TechniQues in Learning," Proc. of the 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.

[16] Manago, 1986)

[17] Manago, M. "Object-oriented Generalization: A Tool for Improving Knowledge Based Systems," Proc. of the 1st International Meeting on Advances in Learning, Las Arcs (France) 1986.

[18] Manago & Kodratoff, 1987)

[19] Manago, M. & Kodratoff, Y. "Model prtyen Learning of Disiunctive Concepts," Proc. of the second European Working Session on Symbolic Learning, Bled (Yougoslavia), 1987.

[20] McDermott, 1986)

[21] McDermott, J. "Transcripts of plenary session• Interactive Tools 1 ," 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.

[22] Michalski & Chilauski, 1980)

[23] Michalski, R.S . & Chilauski, R.L. "Learning by Being Told and Learning from Examples: An Experimental Comparison of the Two Methods of Knowledge AcQuisition in the Context of Qeyeloping an Expert System for Soybean Oisease Diagnosis," Policy Analysis and Information Systems, Vol 4:2, 1980. 354 KNOWLEDGE ACQUISITION (Minsky, 1975) Minsky, M. "A framework for representing knowledge," In Irul Psychology of Co"ieyter Vision, Winston P. H. ed , Me Graw~Hill, New Yo 1975. (Mitchell, 1985)

[24] Mitchell, T.~. . . . .. "Genera!jzation as Search", '.n Readmg In ArtifiCial Intelligence, Webber, B.L., N1lsson, N.J. ads, Morgan- Kaufmann, Los Altos (CA), 1985.

[25] Nilsson, 1984)

[26] Nilsson, N.J. ~rinciples of Artificial Intelligence, Morgan-Kaufmann, Los Altos (CA), 1984. .

[27] Pazzani, 1986)

[28] Pazzani, M.J. "Explanation-Based Learning for Knowledge-Based ~vstems," Proc of the 1st AAAI Workshop on now/edge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.

[29] Quinlan, 1983)

[30] Quinlan, J. R. . "Learning efficient classification er_ocedy~s and thEW application to ches~ end games, 1n M~chme ~earnmg 1: An Artificiallntelhgence Approach, M1chalsk1 R. S., Carbonell J. G., Mitchell T. M. ads, Morgan Kaufmann, Los Altos 1983 (Quinlan, 1986)

[31] Quinlan, J. R. "Simplifying decision trees," Proc. of the 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.

[32] Regoczei & Plantinga, 1986) Regoczei, S. & Plantinga, E:.o. "Ontology and lnyentor:y: A Foundation for a Knowledge ACQuisition Methodology,"Proc of the 1st AAAI Workshop on Knowledge Acquisition for Knowledge Based Systems, Banff (Canada) 1986.

[33] Shank & Carbonell, 1979) Shank, R. & Carbonell, J. G . "Re: The Gettysbyrg Address• Representing Social and Political Acts," in Associative Networks• Representation and Use of Knowledge by Compyters Findler N. V. ed, Academic Press, New York 1979.

[34] Smith & Medin, 1981)

[35] Smith, E. & Medin, D. Categories and Concepts, Cambridge: Harvard University Press, 1981 .

[36] Utgoff, 1986)

[37] Utgoff, P.E. "Shift of Bias for Inductive Concept Learning," in Machine Learning 2: An Artificial Intelligence Approach, Michalski R. S., Carbonell J. G,, Mitchell T. M. eds, Morgan Kaufmann, Los Altos 1986. (Waltz, 1975)

[38] Waltz, D. L. •~tandi~e Qrawing of Scenes with ShadOWS." in Psychology of Computer Vision,

[39] Winston P. H. ed, Me Graw-Hill, New York 1975.

[40] Winograd, 1972)

[41] Winograd, T. Understanding Natyrallangyage, Academic Press, New York 1972.

[42] Zucker, 1978)

[43] Zucker, S. "Production Systems with Feedback." in Pattern Directed Inference Systems, Waterman D., Hayes-Roth F. ads, Academic Press, New York 1978.