Accession Number : ADA224442


Title :   Sociopathic Knowledge Bases: Correct Knowledge Can Be Harmful Even Given Unlimited Computation


Descriptive Note : Technical rept.


Corporate Author : ILLINOIS UNIV AT URBANA DEPT OF COMPUTER SCIENCE


Personal Author(s) : Wilkins, David C ; Ma, Yong


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a224442.pdf


Report Date : Aug 1989


Pagination or Media Count : 35


Abstract : This paper studies a situation is which correct knowledge is harmful to a problem solver even given unlimited computational resources. A knowledge base is defined to be sociopathic if all the tuples in the knowledge base are individually judged to be correct and a subset of the knowledge base gives better performance than the original knowledge base independent of the amount of computational resources that are available. Almost all knowledge bases that contain probabilistic rules are shown to be sociopathic and so this problem is very widespread. Sociopathicity has important consequences for the rule induction methods and rule set debugging methods. Sociopathic knowledge bases cannot be properly debugged using the widespread practice of incremental modification and deletion of rules responsible for wrong conclusions a la Teiresias; this approach fails to converge to an optimal solution. The problem of optimally debugging sociopathic knowledge bases is modeled as a bipartite graph minimization problem and shown to be NP-hard. Our heuristic solution approach is called the Sociopathic Reduction Algorithm and experimental results verify its efficacy. (kr)


Descriptors :   *ARTIFICIAL INTELLIGENCE , *PROBLEM SOLVING , MODIFICATION , GRAPHS , SOLUTIONS(GENERAL) , HEURISTIC METHODS , RESOURCES , COMPUTATIONS , OPTIMIZATION , PROBABILITY


Subject Categories : Computer Programming and Software
      Cybernetics


Distribution Statement : APPROVED FOR PUBLIC RELEASE