% TEMPLATE SECTION - 132 LINES % TECHREPORT: TEMPLATE - 14 LINES % KEYWORDS: @TECHREPORT{LABEL, AUTHOR = {}, TITLE = {}, INSTITUTION = {}, YEAR = {}, % OPTIONAL FIELDS: TYPE = {}, NUMBER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = {} } % ARTICLE: TEMPLATE - 14 LINES % KEYWORDS: @ARTICLE{LABEL, AUTHOR = {}, TITLE = {}, JOURNAL = {}, YEAR = {}, % OPTIONAL FIELDS: VOLUME = {}, NUMBER = {}, PAGES = {}, MONTH = {}, NOTE = {}, ANNOTE = {} } % INPROCEEDINGS SECTION - 16 LINES % KEYWORDS: @INPROCEEDINGS{LABEL, AUTHOR = {}, TITLE = {}, BOOKTITLE = {}, YEAR = {}, % OPTIONAL FIELDS: EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = {} } % PROCEEDINGS: TEMPLATE - 13 LINES % KEYWORDS: @PROCEEDINGS{LABEL, TITLE = {}, YEAR = {}, % OPTIONAL FIELDS: EDITOR = {}, PUBLISHER = {}, ORGANIZATION = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = {} } % TEXT/BOOK: TEMPLATE - 16 LINES % KEYWORDS: @BOOK{LABEL, AUTHOR = {}, % EDITOR = {Instead of Author}, TITLE = {}, PUBLISHER = {}, YEAR = {}, % OPTIONAL FIELDS: VOLUME = {}, SERIES = {}, ADDRESS = {}, EDITION = {}, MONTH = {}, NOTE = {}, ANNOTE = {} } % INBOOK: TEMPLATE - 18 LINES % KEYWORDS: @INBOOK{LABEL, AUTHOR = {}, % EDITOR = {Instead of Author}, TITLE = {}, CHAPTER = {}, PAGES = {}, PUBLISHER = {}, YEAR = {}, % OPTIONTAL FIELDS: VOLUME = {}, SERIES = {}, ADDRESS = {}, EDITION = {}, MONTH = {}, NOTE = {}, ANNOTE = {} } % PHDTHESIS: TEMPLATE % KEYWORDS: @PHDTHESIS{LABEL, AUTHOR = {}, TITLE = {}, SCHOOL = {}, YEAR = {}, % OPTIONAL FIELDS: ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = {} } % MISC: TEMPLATE - 11 LINES % KEYWORDS: @MISC{LABEL, % OPTIONAL FIELDS: AUTHOR = {}, TITLE = {}, HOWPUBLISHED = {}, MONTH = {}, YEAR = {}, NOTE = {}, ANNOTE = {} } % BIBLIOGRAPHY SECTION % KEYWORDS: ABDUCTION; ABDUCTIVE INFERENCE; APPLICATIONS OF ABDUCTION; @PROCEEDINGS{AAAI90, TITLE = {Working Notes of the 1990 Spring Symposium on Automated Abduction}, YEAR = {1990}, EDITOR = {}, PUBLISHER = {}, ORGANIZATION = {Stanford University}, ADDRESS = {}, MONTH = {March}, NOTE = {}, ANNOTE = { Describes the applications of abduction. Also looks at different ways to optimise abduction. } } % KEYWORDS: @MISC{ASBJOERN, AUTHOR = {Asbjoern}, TITLE = {}, HOWPUBLISHED = {Newsgroups: comp.theory,sci.op-research,comp.ai}, MONTH = {September}, YEAR = {1995}, NOTE = {}, ANNOTE = { Reply-to: ambonvik@mtl.mit.edu Message-id: <9509061441.AA04135@hierarchy.mit.edu> Organization: MIT Microsystems Technology Laboratories X-Organization: MIT Microsystems Technology Laboratories Content-type: text Content-transfer-encoding: 7BIT Content-length: 3188 Newsgroups: comp.theory,sci.op-research,comp.ai Status: OR In article <42j54t$pg1@harbinger.cc.monash.edu.au> you write: >Can anyone tell me (simply) the difference between >PSPACE, PSAPCE-compelte,NP-complete, NP-hard (am i missing any buzz words >here...?) Well, explain is one thing, explain simply another. Here's my attempt: P is the set of all problems we know how to solve in time bounded above by some polynomial function of the problem size. The problem size is usually stated at the number of bits required to express an instance of the problem. NP is the set of all problems that we know how to solve in time bounded by some non-polynomial (e.g., exponential) function of the problem size. Obviously, P is contained in NP, since any polynomial can be bounded above by some exponential function. There are also problems that are not in NP, for instance the undecidable ones, such as the Turing halting problem and the problem of deciding whether a polynomial has integral roots. Now, there are problems in NP that are believed not to be in P. That is, we know how to solve them, but not how to solve them efficiently. These are called NP-hard. One particular subgroup of NP-hard problems are the NP-complete problems that have a very interesting property: If an efficient (i.e., polynomial) algorithm is found for one of these, any other NP-complete problem can be solved by this algorithm + a polynomial time transformation between the original problem and the one for which we have found an algorithm. Several notorious problems, such as the traveling salesman, belong to this set. PSPACE is the set of problems that can be solved in memory that is bounded by a polynomial function of the problem size. It seems that NP is contained in PSPACE. I have no idea about PSPACE-complete. You left out co-NP, which is the class of problems where we can verify that a solution is optimal in polynomial time. The set P resides in the intersection of NP and co-NP. Example: Linear programming solutions can be checked in polynomial time by inspecting the dual variables, but the usual simplex algorithm runs in exponential time in the worst case. Linear programming is therefore in the intersection of NP and co-NP. Eventually, a polynomial algorithm for solving the problem was found, proving that linear programming is indeed in P. Another example: To prove that a traveling salesman tour is optimal, we need to look at all other solutions one by one and demonstrate that no other tour is better. This takes as long as solving the problem in the first place, so TSP is in NP but not in co-NP. This was just regurgitating from memory, so I may be mistaken on some crucial point. Also, I have not defined what it means to "solve" a problem. If this is important, you should definitely check out a reference book like Nemhauser and Wolsey: Combinatorial optimization. (The usual definition of "important" in this context is that you have been assigned to write a program to solve some problem, but the obvious algorithms are s l o w . If you then can prove that the problem is NP-hard, you can argue that your boss should not fire you, since all those other bright people don't know how to solve it either. :-)) Have fun, - Asbjoern } } % KEYWORDS: PROBLEM SOLVING @INPROCEEDINGS{BREUKER94, AUTHOR = {Joost Breuker}, TITLE = {Components of Problem Solving and Types of Problems}, BOOKTITLE = {A Future for Knowledge Acquisition: 8th European Knowledge Aquisition Workshop, EKAW 1994}, YEAR = {1994}, EDITOR = {Luc Steels and Guus Shreiber and Walter Van de Velde}, PAGES = {118--136}, ORGANIZATION = {}, PUBLISHER = {Springer-Verlag}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: ABDUCTION @ARTICLE{BYLANDER91, AUTHOR = {Tom Bylander and Dean Allemang and Michael C. Tanner and John R. Josephson}, TITLE = {The computational complexity of abduction}, JOURNAL = {Artificial Intelligence}, YEAR = {1991}, VOLUME = {49}, NUMBER = {}, PAGES = {25--60}, MONTH = {}, NOTE = {}, ANNOTE = { This article explains how one type of abduction in which the best explanation is the most plausible combination of hypotheses that explains all the data, is intractible (NP-hard) in general. I found it very difficult to follow this article. I was totally lost half way through this article. } } % KEYWORDS: EVA SYSTEM; @ARTICLE{CHANG90, AUTHOR = {C. L. Chang and J. B. Combs and R. A. Stachowitz}, TITLE = {A report on the expert systems validation associate (EVA)}, JOURNAL = {Expert Systems with Applications}, YEAR = {1990}, VOLUME = {1}, NUMBER = {3}, PAGES = {217--230}, MONTH = {}, NOTE = {}, ANNOTE = {Essential Reading} } % KEYWORDS: MODEL; OPERATORS @ARTICLE{CLANCEY92, AUTHOR = {William J. Clancey}, TITLE = {Model construction operators}, JOURNAL = {Artificial Intelligence}, YEAR = {1992}, VOLUME = {53}, NUMBER = {}, PAGES = {1--115}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: INDUCTIVE LEARNING @INPROCEEDINGS{CLARK93, AUTHOR = {Peter Clark and Stan Matwin}, TITLE = {Using Qualitative Models to Guide Inductive Learning}, BOOKTITLE = {Proceedings of the Tenth International Machine Learning Conference, ML-93}, YEAR = {1993}, EDITOR = {P. Utgoff}, PAGES = {49--56}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Department of Computer Science, Ottawa University, Canada (Address of Authors)}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: @ARTICLE{COMPTON90, AUTHOR = {P. Compton and R. Jansen}, TITLE = {A philosophical basis for knowledge acquisition}, JOURNAL = {Knowledge Aquisition}, YEAR = {1990}, VOLUME = {2}, NUMBER = {}, PAGES = {241--257}, MONTH = {}, NOTE = {}, ANNOTE = { The purpose of this article is not clear. This article argues that consideration of epistomology (study of the source and limitations of knowledge) may be important for developing appropriate knowledge aquisition tools. The prevailing epistomology is the physical symbol hypothesis of Nowell and Simon (1981). The extension of the physical symbol hypothesis is the "knowledge principle". This article argues that problems encountered in knowledge bases is not out of stupidity or lack of common sense of the expert system designer(s), but problems related to how knowledge is presented. It is argued that even the knowledge provided by some single experts changes as the context in which this knowledge is required changes. When rules provided by the expert are added to the expert system, they may subsume and conflict with pre-existing rules and must therefore be extensively manipulated before they can be added to the knowledge base. This problem is not just caused by the influence of the inference strategy used on the structure of the knowledge base, but in the knowledge provided by the experts, regardless of the simplicity of the rules. It is argued that the context in which questions are asked to the expert will influence the answers obtained from the expert. The physical symbol hypothesis, however, suggests that there should be underlying rules that provide a more absolute foundation for the knowledge (i.e. context free rules). The experience with GARVAN-ES1 suggests that the knowledge acquisition process is an ongoing task rather than arriving at the ultimate goad/structure. The rule base has doubled in size in trying to achieve an accuracy of 99.7% from an accuracy of 96%. It is argued that knowledge is context dependent. It is suggested that the knowledge that experts provide is essentially a justification of why they are right, and not the reasons they reached this right conclusion. It is argued that if all knowledge is true only in a context, then all knowledge is relative, and thus there is no underlying knowledge on which the rest of the knowledge is built. It is argued that sense data cannot be viewed as providing the primitives out of which other knowledge is built, since the sense data available is determined by the mind, by personal knowledge and the context that this provides for perception. It is philosophically unsound to design a vast body of expert knowledge separate from its context and as general as possible. It can be argued that mathematics theory is a counterexample to this article.(?) It is proposed that where knowledge is elicited from experts, it should be recorded in context (this is not always possible). } } % KEYWORDS: @INPROCEEDINGS{COMPTON93, AUTHOR = {Paul Compton and Byeong Kang and Phillip Preston and Mary Mulholland}, TITLE = {Knowledge Acquisition without Analysis}, BOOKTITLE = {Knowledge Acquisition for Knowledge-Based Systems: 7th European Workshop, EKAW 1993}, YEAR = {1993}, EDITOR = {N. Aussenac and G. Boy and B. Gaines and M. Linster and J. G. Ganascia and Y. Kodratoff}, PAGES = {277--299}, ORGANIZATION = {}, PUBLISHER = {Springer-Verlag}, ADDRESS = {}, MONTH = {September}, NOTE = {}, ANNOTE = {} } % KEYWORDS: ABDUCTION; ABDUCTIVE INFERENCE; DIAGNOSIS; INCOMPLETE CAUSAL MODELS; @INPROCEEDINGS{CONSOLE89, AUTHOR = {Luca Console and Daniele Theseider Dupre and Pietro Torasso}, TITLE = {A theory of diagnosis for incomplete causal models}, BOOKTITLE = {Eleventh International Joint Conference on Artificial Intelligence (IJCAI '89)}, YEAR = {1989}, EDITOR = {}, PAGES = {1311--1317}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Detroit, Michigan USA}, MONTH = {August}, NOTE = {}, ANNOTE = { ``...the completeness of the model is a common assumption in first principles diagnostic systems (which have been successfully applied to the solution of problems such as electronic troubleshooting[ref]). This assumption is not adequate for the application of ontological approaches to complex problems (such as medical diagnosis or mechanical troubleshooting) [ref] since in these cases a complete model is either not available or intractible.'' Discussion relating to best assessment operator: ``The basic justification supporting the "minimal cardinality" parsimony criterion is the assumption that faults are independent. Such an assumption can be questioned in many real world domains. in many cases, in fact, two faults (diseases or diagnostic hypotheses) can be causally correlated (e.g. "burnout" and "melting" in figure1). On the other hand, the "minimality" (irredundancy) parsimony criterion seems to be much more widely applicable since it does not require any a-priori assumption on the nature of the diagnostic hypotheses being considered. Of course this criterion is weaker, since it is based on a partial order, where we may have different (and incomparable) minimal elements (while in the other case two different solutions of minimum cardinality can be considered equally good). Incompleteness can be divided into two main classes: - Abstracted knowledge: initial causes and abstracted conditions fall within such a class. A hypothetical reasoning scheme has been designed in order to deal with abstracted knowledge. - Missing knowledge: in order to draw conclusions from incomplete models, different forms of circumscriptive reasoning have been used on the causal model itself and on thte findings observed in a specific case under examination. This article discusses Console and Torasso's abductive framework. Very confusing, especially when they try to define their framework using first order logic. } } % KEYWORDS: ABDUCTION; SPECTRUM OF DEFINITIONS; @ARTICLE{CONSOLE91a, AUTHOR = {Luca Console and Pietro Torasso}, TITLE = {A Spectrum of Logical Definitions of Model-based Diagnosis}, JOURNAL = {Computational Intelligence}, YEAR = {1991}, VOLUME = {7}, NUMBER = {3}, PAGES = {78--88}, MONTH = {}, NOTE = {}, ANNOTE = { The purpose of this paper is to propose a unified framework in which different logical definitions of diagnosis on models of the correct and faulty behaviour of a system can be represented and compared. In particular, this article proposes the integration of consistency-based and abductive reasoning (diagnoses). This article discusses when abduction can be used, in a plausible way, to reduce the space of candidate solutions provided by consistency-based diagnoses. It is argued that a diagnostic problem is characterized by different types of data and that such different types of data must be treated in different ways in the diagnostic process. Note that contextual data is very similar to the philosophy of JUSTIN's justification in context. "...diagnoses can be characterised as the process of generating `explanations' for a set of observations in a given context." Note that Psi- is equivalent to invariants in HT4. Note that Psi+ is equivalent to OUT in HT4 or IN union OUT? "One way to specify incomplete knowledge is to provide negative information about the observations." (since not all observations are definite?). "The central task of abductive reasoning is to identify these behavioural modes of the components whose consequences cover Psi+ (OUTS in HT4?) consistently with Psi- (invariants in HT4)." "Definition 5 and 6 clearly correspond to two extreme choices in the sense that they impose that either all the observations or no observation must be covered." Section 5 of this article is essential for my literature review. The authors argue that abduction can be regarded as deduction on a complete theory. The authors argue that when a model is "complete", only covering provides plausible explanations. The authors argue that when a model is not "complete", then the "restrictiveness provided by covering is not justified, and it may lead to the exclusion of some perfectly plausible explanations. In such cases, the use of consistency-based approaches is recommended." "...Abduction can be used also when knowledge is incomplete but all the sources of incompleteness have been recognized, and explicitly represented in the model." "In general, given a system description, one can choose which is the set of observable parameters (symbols) whose instances must be covered and which is the subset of the observable parameters (symbols) whose instances need not be covered...The discussion in this section suggests that such a choice should be based on the analysis of the completeness of the part of the model concerning the condition represented by each observable parameter (atom)." Note that "if one has a `complete' fault model and only part of the model of the correct behaviour, then one can choose a definition in which only (part of) the abnormality observations have to be covered (definition 7)...On the other hand, if one has a `complete' model of the correct behaviour and only part of the fault model, then one can choose a definition in which only (part of) the normality observations have to be covered (definition 8)." } } %KEYWORDS: ABDUCTIVE REASONING; ABDUCTION THROUGH DEDUCTION; % PREDICATE COMPLETION @ARTICLE{CONSOLE91b, AUTHOR = {Luca Console and Daniele Theseider Dupre and Pietro Torasso}, TITLE = {On the Relationship Between Abduction and Deduction}, JOURNAL = {Journal of Logic Programming}, YEAR = {1991}, VOLUME = {1}, NUMBER = {5}, PAGES = {661--690}, MONTH = {}, NOTE = {}, ANNOTE = { The paper tries to explain abduction in terms of deduction. I find it very difficult to understand sometimes, especially the theorems. |__ |__ This symbol is not understood. | This article is not as difficult to understand as Bylander's article. } } % KEYWORDS: ATMS; @ARTICLE{DEKLEER86a, AUTHOR = {Johan de Kleer}, TITLE = {An assumption-based "TMS"}, JOURNAL = {Artificial Intelligence}, YEAR = {1986}, VOLUME = {28}, NUMBER = {}, PAGES = {127--162}, MONTH = {}, NOTE = {}, ANNOTE = { ABSTRACT: ``This paper presents a new view of problem solving motivated by a new kind of truth maintenance system. Unlike previous truth maintenance systems which were based on manipulating justifications, this truth maintenance system is, in addition, based on manipulating assumption sets. As a consequence it is possible to work effectively and efficiently with inconsistent information, context switching is free, and most backtracking (and all retraction) is avoided. These capabilities motivate a different kind of problem-solving architecture in which multiple potential solutions are explored simultaneously. This archittecture is particularly well suited for tasks where a reasonable fraction of the potential solutions must be explored.'' This abstract sounds similar to the objectives of HT4. deKleers ATMS framework attempts to overcome the following problems faced by conventional truth maintenance systems (TMS): The single state problem: ``Given a set of assumptions which admits multiple solutions, the TMS algorithms only allow one solution to be considered at a time. This makes it extremely difficult to compare two equally plausible solutions....However, this is often exactly what one wants to do in problem solving -- differential diagnosis to determine the best solution.'' ``As the assumption-based approach does not require a notion of current global context, multiple, mutually contradictory, solutions may coexist. Thus it is simple to compare two solutions.'' Overzealous contradiction avoidance: ``Suppose $A$ and $B$ are contradictory. The TMS will guarantee that either $A$ or $B$ will be worked on, but not both. This is not necessarily the best problem-solving tactic. All a contradiction between $A$ and $B$ indicates is that inferences dependent on both $A$ and $B$ be avoided. But it is still important to draw inferences from $A$ and $B$ independently.'' ``The presence of two contradictory data does not terminate work on the overall knowledge state, rather only other data which depend on both contradicting data are removed. This is exactly the result desired from a contradiction -- no more, no less. The nogood database guarantees that mutually contradictory data will never be combined. Said differently, the nogood database, in effect, provides the partitioning of the database into the consistent solutions.'' Switching states is difficult: There is no efficient way to facilitate a temporary change in an assumption, not resulting in a contradiction. The only way to change assumptions in a conventional TMS is to introduce a contradiction, but once added, it cannot be removed, so the knowledge state of the problem solver is irreconcilably altered. ``Changing state is now trivial or irrelevant. A state is completely specified by a set of assumptions. Problem solving can be restricted to a current context (i.e. a set of assumptions) or all states that can be explored simultaneously. In either case, data obtained in one state are "automatically" transferred to another.'' The dominance of justifications: ``What Doyle calls an assumption is context-dependent: an assumption is any node whose current supporting justification depends on some other node being out. As problem solving proceeds, the underlying support justifications and hence the set of nodes considered assumptions changes. This is problematic for problem solvers which frequently consult the assumptions and justifications for data.'' ``As assumptions, not justifications, are the dominant representational mode, it is easy to compare sets of assumptions underlying data. For example, it is easy to find the datum with the most assumptions or the least; it is easy to determine whether the presence of one datum implies the presence of another ($a$ implies $b$ if every environment of $a$ is a superset of one of the environments of $b$). Also, the justifications underlying a datum never change.'' The machinery is cumbersome: ``The TMS algorithm can spend a surprising amount of resources finding a solution that satisfies all the justifications. Determining the well-founded support for a node requires a global constraint satisfaction process. Detecting loops of odd numbers of nonmonotonic justifications (which provoke infinite computation loops) is expensive. The dependency-directed backtracking in response to a contradiction may require extensive search, and the resolution of the contradiction often results in other contradictions. Eventually, all contradictions are resolved, but have changed between in (believed) and out (not believed) many times.'' ``The underlying mechanism is simple. There is no backtracking of any kind within the ATMS -- let alone dependency-directed backtracking. The assumptions underlying a contradiction are directly identifiable. It is not necessary to explicitly mark data as believed or disbelieved, or signal the problem solver when the statuses of data change.'' Unouting: As problem solving progresses a datum can be derived, retracted, when a contradiction occurs, and then reasserted when a second contradiction causes the current context to switch again (a common occurrence in problem solving). The process of determining which retracted, previously derived, data can be reasserted is called unouting. The maintenance of dependency records avoid having to rediscover these inferences. Unfortunately, unless greate care is taken at the problem- solver-TMS interface, some previously discovered data will be rederived.'' ``For those tasks requiring all solutions (or where there is only one solution), the ATMS completely finesses the earlier unouting problem. Unlike with a conventional TMS, the ATMS allows the problem solver to explore all solutions at once. There is no backtracking, no retraction, and no context switching.'' The ATMS architecture adopts that same view of problem solving as a conventional TMS. The reasoning system (or overall problem solver) consists of two components: a problem solver and a TMS. The problem solver includes all domain knowledge and inference procedures. Every inference made is communicated to the TMS. The TMS's job is to determine what data are to be believed and disbelieved, given the justifications recorded thus far. Note that the ATMS architecture is incremental, updating only the changed contexts. ``It is critical to distinguish the thing assumed from the decision to assume....An assumptions is restricted to designate a decision to assume without any commitment as to what is assumed. An assumed datum is the problem-solver datum that has been assumed to hold. Assumptions are connected to assumed data via justifications as discussed in the next section.'' ``An ATMS node corresponds to a problem-sover datum. An assumption is a special kind of node.'' ``An ATMS justification describes how a node is derivable from other nodes. A justification has three parts: the node being justified, called the consequent; a list of nodes, called the antecedents, and the problem solver's description of the justification, called the informant.'' Justifications are written as: $x_1, x_2, ... \Longrightarrow n$. Here $x_1, x_2, ...$ are the antecedent nodes and $n$ is the consequent node. A justification is a material implication, $x_1 \bigwedge x_2 \bigwedge ... \longrightarrow n$, where $x_1, x_2, ..., n$ are atoms. Thus the justifications are propositional Horn clauses. ``The nonlogical notation "=>" is used because the ATMS does not allow negated literals and treats implication unconventionally.'' ``An ATMS environment is a set of assumptions. Logically, an environment is a conjuction of assumptions. A node $n$ is said to hold in environment \textbf{E} if $n$ can be derived from \textbf{E} and the current set of justifications \textbf{J}. Derivability is defined in terms of the usual propositional calculus, $E, J \vtick n$, where $E$ is viewd as a conjuction of atoms and $J$ is viewed as a set of implications.'' ``An environment is inconsistent if false is derivable propositionally: $E, J \vtick \perp$.'' ``An ATMS context is the set fromed by the assumption of a consistent environment combined with all nodes derivable from those assumptions.'' ``A characterizing environment for a context is a set of assumptions from which every node of the context can be derived. Every context has at least one characterizing environment. Usually (when assumptions have no justifications) every context has exactly one characterizing environment.'' ``An ATMS label is a set of environments associated with every node. Every environment $E$ of $n$'s label is consistent and has the property that, $E, J \vtick n$. More intuitively, $J \vtick E \longrightarrow n$.'' ``While a justification describes how the datum is derived from immediately preceding antecedents, a label environment describes how the datum ultimately depends on assumptions.'' ``Each context implicitly seperates all the nodes into three categories: nodes necessarily present, nodes necessarily absent, and nodes currently absent, but which may become necessarily present or absent with subsequent justifications.'' For efficiency reasons, sets are represented by bit-vectors: each assumption is assigned a unique position so that a one bit in a position indicates the presence of the corresponding assumption in the set. This is exactly the same structures used to represent sets in the HT4 framework. ``The ATMS is given a set of assumptions $A$, a set of nodes $N$ ($N \supset A$), and a set of justifications $J$ in terms of $N$ (which include $A$). The triple $$ implicitly defines a set of contexts where a context is defined as a consistent set of assumptions ($A' \subset A$) and nodes ($N' \subset N$) derivable from $A'$ using $J$.'' This sounds similar to the definition of abduction. \begin{quote} \textit{Label consistency} ensures all inconsistent environments are identified and defined not to have context and do not appear in node labels. \textit{Label soundness} ensures that no context will contain a datum it should not. Thus, nodes which hold in no context will have empty labels. This property is important to problem solving because it ensures that the problem solver will not mistakenly work on irrelevant nodes which do not hold in any context. \textit{Label completeness} guarantees that every context will contain every datum it should. Thus, all nodes which hold in any context have nonempty labels. This property is important to problem solving because it ensures that the problem solver can easily identify all relevant nodes (i.e. those which hold in at least one context). \textit{Label minimality} states that each node label has the fewest disjuncts and that each disjunct has the fewest assumptions. This property is important to the problem solver because it ensures that changing any label assumption affects the node's status. This property is true by definition for the basic ATMS, but becomes an important consideration for dealing with disjunction axioms. \end{quote} } } % KEYWORDS: EXTENDING ATMS; @ARTICLE{DEKLEER86b, AUTHOR = {Johan de Kleer}, TITLE = {Extending the "ATMS"}, JOURNAL = {Artificial Intelligence}, YEAR = {1986}, VOLUME = {28}, NUMBER = {}, PAGES = {163--196}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: PROBLEM SOLVING; ATMS; @ARTICLE{DEKLEER86c, AUTHOR = {Johan de Kleer}, TITLE = {Problem solving with the "ATMS"}, JOURNAL = {Artificial Intelligence}, YEAR = {1986}, VOLUME = {28}, NUMBER = {}, PAGES = {197--224}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: ATMS; GENERAL DIAGNOSTIC ENGINE; SHERLOCK; DIAGNOSIS; @INPROCEEDINGS{DEKLEER89, AUTHOR = {J. deKleer and B. C. Williams}, TITLE = {Diagnosis with behavioral modes}, BOOKTITLE = {Eleventh International Joint Conference on Artificial Intelligence (IJCAI '89)}, YEAR = {1989}, EDITOR = {}, PAGES = {1324--1330}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Detroit, Michigan USA}, MONTH = {August}, NOTE = {}, ANNOTE = { Early approaches to diagnosis used fault models to identify failure modes of faulty components that explain the observations made. The ability to predict failing components' behaviours provided a powerful diagnostic discrimination. deKleer and Williams argue, however, that these techniques depend on the assumption that all failure modes are known a priori, resulting in redundant fault modes being developed, but never used. The model-based diagnostic approach, on the other hand, provides a framework for diagnosing a device from correct behaviour only. What is lost, however, is the additional diagnostic discrimination derived from knowing the likely ways a component fails, and the ability to determine whether these failure modes are consistent with the observations. deKleer's framework also uses fault models, however, with all other modes of (correct or faulty) behaviour, it includes an unknown mode which makes no predictions, and therefore can never conflict with the evidence. deKleer argues that this unknown mode is crucial because early diagnostic algorithms, when confronted with an unforeseen fault mode, either start making useless probes or simply give up. deKleer's approach pinpoints the failing component as behaving in an unknown mode. deKleer and Williams discuss their Sherlock framework, and compare it to their General Diagnostic Engine (GDE). Sherlock uses probability and Bayes theorem to cull the search space of its inference process. This is because its inference process can cause a combinatorial explosion of behavioural modes to reason about. The potential combinatorial explosion manifests itself in two ways: 1) The set of conflicts, as well as the sets of behavioural modes underlying possible outcomes causes the prediction phase of Sherlock to explode. 2) The number of possible diagnoses is exponential, causing candidate generation to explode. deKleer argues that the consequences of incompleteness are not catastrophic and usually result in only a minimal degradation in diagnostic perfomance. In their definition of abductive inference, deKleer assumes that all observations be consistent with a diagnosis. (Observation coverage is weak). } } % KEYWORDS: @INBOOK{DIERKER86, AUTHOR = {Paul F. Dierker and William L. Voxman}, TITLE = {Discrete Mathematics}, CHAPTER = {1}, PAGES = {44-54}, PUBLISHER = {Harcourt Brace Jovanovich, Publishers}, YEAR = {1986}, VOLUME = {}, SERIES = {}, ADDRESS = {}, EDITION = {}, MONTH = {}, NOTE = {}, ANNOTE = { Chapter 1: Section 7 Computational Complexity is the term used to describe the efficiency of algorithms, in terms of compter time and storage. An algorithm's complexity is usually described by a function S(n) where n is the number of items in a list, for example. The value of the function S(n) may be the number of comparisons necessary to sort a list of n items, for example. If the chances that the worst-case (of an algorithm) occuring are very low, then ti may be misleading to consider the efficiency of an algorithm in terms of its function (complexity). The simplex method is an example of this: this algorithm is very inefficient under a worst-case analysis, however, in practice it is amazingly efficient. "Instead of a worst-case analysis, an average-case analysis...sometimes yields a more appropriate evaluation of an algorithm." The complexity or efficiency of an algorithm in terms of the average case is measured in an average-case analysis. The "Big-O" notation is used to describe the complexity of algorithms. "This notation provides an easy way to compare the `size' of various functions." Definition: Suppose that f and g are two functions, each with domain in Z+. If there is a positive constant c and an integer N such that |f(n)| <= c|g(n)| for each n >= N, then f is said to be of order g. If f is of order g, then we say f is O(g), or f E O(g)....Frequently, f and g are replaced by f(n) and g(n). "An algorithm is of polynomial complexity if the complexity function S(n) is of polynomial order (i.e. S(n) E O(n^k), for some positive integer k." "An algorithm is of exponential complexity if the complexity function S(n) is of exponential order (i.e. S(n) E O(a^n), for some constant a > 1)." Polynomial complexity algorithms are prefered over exponential complexity algorithms, in general. "For small values of n, an algorithm of exponential complexity may prove to be more efficient than an algorithm of polynomial complexity." } } % KEYWORDS: @ARTICLE{DURAN84, AUTHOR = {J. W. Duran and S. C. Ntafos}, TITLE = {An evaluation of random testing}, JOURNAL = {{IEEE} {T}ransactions on {S}oftware {E}ngineering}, YEAR = {1984}, VOLUME = {10}, NUMBER = {4}, PAGES = {438--443}, MONTH = {}, NOTE = {}, ANNOTE = { The authors have found that random test case generation have uncovered errors at a rate at least comparable to other more structured methods of testing. } } % KEYWORDS: @ARTICLE{EASTERBROOK91, AUTHOR = {Steve Easterbrook}, TITLE = {Handling conflict between domain descriptions with computer-supported negotiation}, JOURNAL = {Knowledge Aquisition}, YEAR = {1991}, VOLUME = {3}, NUMBER = {}, PAGES = {255--289}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: @INPROCEEDINGS{FALTINGS92, AUTHOR = {Boi Faltings}, TITLE = {Qualitative Models in Conceptual Design: A Case Study}, BOOKTITLE = {Symposium: Reasoning with Diagrammatic Representations}, YEAR = {1992}, EDITOR = {N. Hari Narayanan}, PAGES = {72--77}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Stanford University}, MONTH = {March}, NOTE = {}, ANNOTE = { This areticle demonstrates that qualitative functional attibutes can not be mapped into corresponding attributes of a device that achieves them, and consequently that qualitative functions can not be computed based solely on a qualitative object model. Sketches do not represent a single qualitative model; they must be interpreted as a set of possible precise models. The author claims that the metric diagram is a required part of any shape representation which is to be related to a model of mechanism kinematics. "...subsumptions (invariants in HT4) point to even deeper problems with the mapping between qualitative models of function and objects...[Subsumptions] fail to take into account interference between object constructs: a particular state may in reality be impossible because it would create an overlap of other, not directly related, parts of the mechanism." I say that some contraversial assumptions in HT4 may be impossible in reality! Subsumptions (or invariants in HT4) can be reasoned about, if a precise object model is used. Note that neuroendocrinology is not a precise object model! Hope for Tim's Thesis: "...Even kinematic topology depends crucially on the existence or absence of global subsumptions..." "Because of the degree of abstraction, the amount of ambiguity which results when subsumption conditions cannot be evaluated is manageably low." } } % KEYWORDS: @INPROCEEDINGS{FELDMAN89, AUTHOR = {B. Z. Feldman and P. J. Compton and G. A. Smythe}, TITLE = {Towards Hypothesis Testing: JUSTIN, a prototype system using justification in context}, BOOKTITLE = {Proceedings of the Joint Australian Conference on Artificial Intelligence, AI '89}, YEAR = {1989}, EDITOR = {}, PAGES = {319--331}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { Problems associated with published scientific papers: * It is impossible to scan all the material published. * As a result, some hypotheses/material may be inconsistent with other published hypotheses/material. * This inconsistency can go unnoticed since authors tend to focus on a particular hypothesis of interest. "QSIM (Qualitative SIMulation) uses a mathematical approach to find qualitative solutions to a series of equations which describe the system". QSIM provides no causality in the qualitative description, which poses as a problem since medical researchers use causal language. The lack of causality motivated Feldman et al, to develop a system which provided more causal reasoning. This lead them to develop QMOD. QMOD (Qualitative MODel) is a model builder. JUSTIN (JUSTification IN context) is a model tester. Together, with a method for describing experiments, they would provide a prototype environment for hypothesis testing. Note that Menzies PhD Thesis argues that there is a limit to the QMOD/JUSTIN objective of hypothesis testing. } } % KEYWORDS: @INPROCEEDINGS{FORBUS92, AUTHOR = {Kenneth D. Forbus}, TITLE = {Qualitative Spatial Reasoning: Framework and Frontiers}, BOOKTITLE = {Symposium: Reasoning with Diagrammatic Representations}, YEAR = {1992}, EDITOR = {N. Hari Narayanan}, PAGES = {207--211}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Stanford University, California}, MONTH = {March}, NOTE = {}, ANNOTE = { This paper discusses the progress being made in qualitative spatial reasoning about motion, and how they might be applied broadly. Qualitative representations can fail! The combination of metric diagrams and place vocabularies is necessary for spatial reasoning about motion. Qualitative information needs to be strongly coupled with detail information for it to be useful (or for it to be used in sophisticated spatial reasoning)! "...Numerical information allows spatial queries to be answered by calculation rather than inference, while the physical information guides the selection and interpretation of results." } } % KEYWORDS: KNOWLEDGE-BASE REDUCTION; KB-REDUCER; @INPROCEEDINGS{GINSBERG87, AUTHOR = {Allen Ginsberg}, TITLE = {A new approach to checking knowledge base for inconsistency and redundancy}, BOOKTITLE = {The Third Annual Expert Systems in Government Conferences}, YEAR = {1987}, EDITOR = {}, PAGES = {102--111}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Washington D.C.}, MONTH = {}, NOTE = {}, ANNOTE = { Ginsberg argues that with knowledge-base reduction, one can, in principle, detect all inconsistencies, redundancies, and "potential" contradictions existing in a knowledge-base. "Inconsistencies and redundancy may be viewed as properties of large sets of rules, indeed sometimes as properties of an entire knowledge base, as opposed to properties of pairs of rules as has been the case with previous work." Knowledge Base Reduction can only be applied to an acyclic network of rules. A label of an hypothesis is restricted to known causes. In HT4 terms, a world is defined by its causes and base assumptions. HT4 can never detect contradictions detected by Knowledge Base Reduction, since proofs with consistent environments will be sorted into the same world. One method to overcome this would be to write a post-processing routine to check the consistency among output vertices sorted into one world. This may, or may not be in the form of a BEST assessment operator. Ginsberg argues that in general, if one is not in possession of a fair portion of semantic constraints for a domain, it is not worthwhile to calculate all the potential contradictions for the knowledge base, since there will simply be too many. He goes on to add that this is not a problem, since many of the semantic constraints needed are very general and may be applied to any domain. For example, environments having findings that represent distinct values for the same attribute are invalid (same as for HT4). Also, the knowledge engineer will usually acquire enough knowledge of these constraints, in the course of the knowledge acquisition process, to make the generation of potential contradictions a useful procedure. Complexity of Knowledge-Base Reduction: Applying a coarse analysis of the knowledge base reduction algorithm on a prototype knowledge base, revealed that an estimated time of 3 years would be required to complete the algorithm, whereas the actual time was 10 minutes. This demonstrates that the worst case assumption of no environment produced, subsumes any other environment, is not applicable in this instance since many subsumable (and hence discardable) environments were being created. Ginsberg speculates that a knowledge base with a small number of findings and a large number of rules is likely to produce subsumable environments since the findings are more likely to have repreated occurrences in the rules, and this is one of the main causes of subsumption. } } % KEYWORDS: KNOWLEDGE-BASE REDUCTION; KB-REDUCER; @INPROCEEDINGS{GINSBERG88a, AUTHOR = {Allen Ginsberg}, TITLE = {Knowledge-base reduction: A new approach to checking knowledge bases for inconsistency and redundancy}, BOOKTITLE = {The Seventh National Conference on Artificial Intelligence (AAAI 88)}, YEAR = {1988}, EDITOR = {}, PAGES = {585--589}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { This paper presents a new approach called knowledge base reduction, to the problem of checking knowledge bases for inconsistency and redundancy. The KB-Reducer is monotonic: if a certain set of input data, $\alpha$ causes the inference engine to conclude $C$, then any superset of $\alpha$ leads to $C$ being asserted; moreover, there is no possibility of retracting conclusions or data from working momory. The KB-Reducer is non-selective: there is no conflict- resolution strategy; every satisfied rule is fired exactly once and its conclusions are deposited into working memory. The KB-Reducer is said to be strongly data-driven: rules which are satisfied by matching agains the input data, together with the other contents of working memory, are fired. ``KB-Reducer analyzes KB's written in a canonical rule representation language that is based on literals having an object-attribute-value type of syntax.'' This is similar to HT4 models. ``In terms of formal logic, we may say that a set of propositions $P$ is consistent iff there is some way of interpreting the propositional symbols of $P$ so that a contradiction is not entailed.'' (See example). ``A set of rules $R$ is said to be \textit{irredundant} if no $r \in R$ follows from the other members of $R$, and if no $r \in R$ is such that $r$ can never be satisfied by any valid input set.'' ``We say that an input set \textbf{E} to a KB is valid iff \textbf{E} does not violate any oof the \textit{semantic constraints} that exist for the domain in question.'' ``An important example of a general type of semantic constraint is \textit{single-valuedness} of object attributes, e.g. a particular person has one and only weight (at a given time).'' ``Domain independent constraints, such as logical constraints, e.g., a person cannot both be a male and a non-male, and mathematical constraints, e.g., an object cannot both weigh more than 50 ounces and less than 20 ounces, must also be satisfied for an input set to be valid.'' ``We...say that a KB is \textit{potentially inconsistent} for some agent $\gamma$ iff there is at least one set of inputs \textbf{E} that does not violate any semantic constraints \textit{known to} $\gamma$, and which is such that the KB will assert conflicting conclusions if \textbf{E} is given as input.'' ``A \textit{finding} is any literal that appears only on the left hand side of rules and is not the logical negation of any literal on the right hand side of any rule.'' ``A \textit{hypothesis} is any literal that either occurs solely on the right hand side of rules or on the right hand side of some rules and [on] the left hand side of others.'' ``A \textit{default-hypothesis} is any literal that only occurs on the left hand side of rules and is the logical negation of some hypothesis. If $D$ is a default-hypothesis we refer to the hypothesis that it negates as its \textit{counter-hypothesis}.'' ``Since default-hypotheses, by definition, are not asserted by any rules in a KB, an environment \textit{E} for a default-hypothesis $D$ is interpreted to be a set of findings which will prevent the KB from concluding the counter- hypothesis of $D$.'' The fact that KB-Reducer (and many other deductive rule bases in general) cannot deal with inconsistency, leaves them open to criticism. They will fail where abductive inference engines will succeed. Note that the KB-Reducer is based on deKleers ATMS framework, although it cannot deal with inconsistency like the ATMS framework can. } } % KEYWORDS: REDUCED THEORY LEARNING SYSTEM @INPROCEEDINGS{GINSBERG88b, AUTHOR = {A. Ginsberg and S. Weiss and P. Politakis}, TITLE = {Theory revision via prior operationalization}, BOOKTITLE = {The Seventh National Conference on Artificial Intelligence (AAAI'88)}, YEAR = {1988}, EDITOR = {}, PAGES = {585--589}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = {Essential Reading} } % KEYWORDS: @INPROCEEDINGS{GINSBERG90, AUTHOR = {Allen Ginsberg}, TITLE = {Theory Reduction, Theory Revision, and Retranslation}, BOOKTITLE = {The Eighth National Conference on Artificial Intelligence (AAAI'90)}, YEAR = {1990}, EDITOR = {}, PAGES = {777--782}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { Complete reading this article. This paper presents an approach to retranslation, the third and final step of the theory reduction approach to solving theory revision problems. Retranslation involves converting a revised rule base, or a reduced version of the revised rule base, back into the entire language of the original theory. Note that this article is not so important for my literature review. } } % KEYWORDS: @INPROCEEDINGS{GOLDMAN90, AUTHOR = {Robert P. Goldman and Eugene Charniak}, TITLE = {Incremental Construction of Probabilistic Models for Language Abduction}, BOOKTITLE = {Working Notes of the 1990 Spring Symposium on Automated Abduction}, YEAR = {1990}, EDITOR = {}, PAGES = {1--4}, ORGANIZATION = {Stanford University}, PUBLISHER = {}, ADDRESS = {}, MONTH = {March}, NOTE = {}, ANNOTE = { This is a morbid article. Objective of article not clear. The authors argue that plan-recognition and text- understanding are a particular case of abduction. The authors' interests are in plan-recognition since it is needed in text-understanding. } } % KEYWORDS: ALGORITHMS; COMPUTATIONAL COMPLEXITY; @BOOK{HAREL88, AUTHOR = {David Harel}, TITLE = {Algorithms: The Spirit of Computing}, PUBLISHER = {Addison-Wesley}, YEAR = {1988}, VOLUME = {}, SERIES = {}, ADDRESS = {}, EDITION = {}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: @INPROCEEDINGS{HERNANDEZ92, AUTHOR = {Daniel Hernandez}, TITLE = {Diagrammatic Aspects of Qualitative Representations of Space}, BOOKTITLE = {Symposium: Reasoning with Diagrammatic Representations}, YEAR = {1992}, EDITOR = {N. Hari Narayanan}, PAGES = {225--228}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Stanford University, California}, MONTH = {March}, NOTE = {}, ANNOTE = { Diagrammatic representations are qualitative in nature since: * they only make as many commitments as necessary * they are underdetermined and context dependent * they allow reasoning at various levels of granularity The desirable properties of both propositional and pictorial representations can be combined. Purpose of article not clear. } } % KEYWORDS: ABDUCTION; INTERPRETATION; @INPROCEEDINGS{HOBBS90, AUTHOR = {Jerry R. Hobbs}, TITLE = {An Integrated Abductive Framework for Discourse Interpretation}, BOOKTITLE = {Working Notes of the 1990 Spring Symposium on Automated Abduction}, YEAR = {1990}, EDITOR = {}, PAGES = {10--12}, ORGANIZATION = {Stanford University}, PUBLISHER = {}, ADDRESS = {}, MONTH = {March}, NOTE = {}, ANNOTE = { Hobbs discusses interpretation in terms of abduction. He describes abduction as inference to the best explanation. This article was very confusing, as many other articles in this symposium on automated abduction. } } % KEYWORDS: PLANNING; @INPROCEEDINGS{KANOVICH91, AUTHOR = {M. I. Kanovich}, TITLE = {Efficient Program Synthesis: Semantics, Logic, Complexity}, BOOKTITLE = {Theoretical Aspects of Computer Software}, YEAR = {1991}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Sendai, Japan}, MONTH = {September}, NOTE = {}, ANNOTE = { Essential Reading. In this article, Kanovich describes his framework for planning. } } % KEYWORDS: EXPLANATION; @ARTICLE{LEAKE91, AUTHOR = {D. B. Leake}, TITLE = {Goal-Based Explanation Evaluation}, JOURNAL = {Cognitive Science}, YEAR = {1991}, VOLUME = {15}, NUMBER = {}, PAGES = {509--545}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading Leake outlines his explanation framework in this article. } } % KEYWORDS: EXPLANATION; ABDUCTION; @INPROCEEDINGS{LEAKE93, AUTHOR = {D. B. Leake}, TITLE = {Focusing Construction and Selection of Abductive Hypotheses}, BOOKTITLE = {IJCAI '93}, YEAR = {1993}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading Leake note the connection between his work on explanation and abduction in this article. } } % KEYWORDS: TEST CASE GENERATION; ONCOCIN KB; SCRIPTGEN; @ARTICLE{MARS87, AUTHOR = {N. J. I. Mars and P. L. Miller}, TITLE = {Knowledge acquisition and verification tools for medical expert systems}, JOURNAL = {Medical Decision Making}, YEAR = {1987}, VOLUME = {7}, NUMBER = {}, PAGES = {6--11}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading Test case generation is a knowledge base activity, and therefore a test case generator requires its own knowledge base. Note that the ONCOCIN ScriptGen system is based on this approach. } } % KEYWORDS: @BOOK{HOGGER90, AUTHOR = {Christopher John Hogger}, TITLE = {Essentials of Logic Programming}, PUBLISHER = {Clarendon Press}, YEAR = {1990}, VOLUME = {}, SERIES = {}, ADDRESS = {Oxford}, EDITION = {}, MONTH = {}, NOTE = {}, ANNOTE = {Introduction to Logic Theory} } % KEYWORDS: QUALITATIVE COMPARTMENTAL MODELLING (QCM); @PHDTHESIS{KENG96, AUTHOR = {Keng Ng}, TITLE = {Honours Thesis}, SCHOOL = {Monash University}, YEAR = {1996}, ADDRESS = {Caulfield East, Victoria}, MONTH = {October}, NOTE = {}, ANNOTE = { Keng is developing the user interface of HT4. Included in the package are the hypothesis builder, model compiler, and results generator. } } % KEYWORDS: @BOOK{MENDELSON79, AUTHOR = {E. Mendelson}, TITLE = {Introduction to Mathematical Logic}, PUBLISHER = {Van Nostrand}, YEAR = {1979}, VOLUME = {}, SERIES = {}, ADDRESS = {}, EDITION = {}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading Re: Definition of Substitution of rules. } } % KEYWORDS: @INPROCEEDINGS{MENZIES92a, AUTHOR = {Tim Menzies and John Black and Joel Fleming and Murray Dean}, TITLE = {An Expert System for Raising Pigs}, BOOKTITLE = {The first Conference on Practical Applications of Prolog}, YEAR = {1992}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {London, England}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: @INPROCEEDINGS{MENZIES92b, AUTHOR = {Tim Menzies and Ashesh Mahidadia and Paul Compton}, TITLE = {Using Causality as a Generic Knowledge Representation, or Why and How Centralised Knowledge Servers Can Use Causality}, BOOKTITLE = {Proceedings of the 7th AAAI-Sponsored Banff Knowledge Aquisition for Knowledge-Based Systems Workshop}, YEAR = {1992}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Banff, Canada}, MONTH = {October}, NOTE = {}, ANNOTE = {} } % KEYWORDS: @INPROCEEDINGS{MENZIES92c, AUTHOR = {Tim Menzies and Paul Compton and Bart Feldman}, TITLE = {Qualitative Compartmental Modelling}, BOOKTITLE = {Symposium: Reasoning with Diagrammatic Representations}, YEAR = {1992}, EDITOR = {N. Hari Narayanan}, PAGES = {233--236}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Stanford University, California}, MONTH = {March}, NOTE = {}, ANNOTE = { Article contains bad expressions. Objective of article not clear. QMOD uses diagrams to represent qualitative compartmental models. Its purpose is to check for consistency between models. The JUSTIN component of QMOD checks for inconsistencies. QMOD can fault published models using data to support these models. JUSTIN views the QMOD model as a set of constraints. QMOD was designed for checking inconsistencies between data and models. } } % KEYWORDS: @INPROCEEDINGS{MENZIES94a, AUTHOR = {Tim Menzies and Windy Gambetta}, TITLE = {Exhaustive Abduction: A Practical Model Validation Tool}, BOOKTITLE = {ECAI '94 Workshop on Validation of Knowledge-Based Systems}, YEAR = {1994}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { Conclusion: (1) Exhaustive Abduction (EA) has some practical utility as a validation tool. (2) The Pendrith limit is not a practical limit to EA in neuroendocrinology. EA is closest in internal data structures to the CTMS-validation procedure of Zlatareva (1993). There are two theoretical limits to EA: (1) the Pendrith limit to the critiquing power of the process. (2) a runtime limit due to the possibly intractible nature of the search. Experiments continue to confirm/refute the exponential nature of HT4's EA inference. EA provides a significant level of critique, however, after an average fanout of 4, it loses its critiquing power. Pretty much the same results obtained in Menzies' thesis. } } % KEYWORDS: @INPROCEEDINGS{MENZIES94b, AUTHOR = {Tim Menzies and Philip Haynes}, TITLE = {The Methodology of Methodologies; or Evaluating Current Methodologies: Why and How}, BOOKTITLE = {Tools Pacific '94}, YEAR = {1994}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Melbourne, Australia}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: @INPROCEEDINGS{MENZIES94c, AUTHOR = {Tim Menzies}, TITLE = {Maintaining Procedural Knowledge: Ripple-Down-Functions}, BOOKTITLE = {Proceedings of AI '94}, YEAR = {1994}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Hobart, Australia}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: COMMON SENSE REASONING; KNOWLEDGE AQUISITION; % KNOWLEDGE REPRESENTATION; KNOWLEDGE SHARING TECHNOLOGY; % QUALITATIVE REASONING; REASONING ABOUT PHYSICAL SYSTEMS; % SITUATED COGNITION; TRUTH MAINTENANCE; DIAGRAMMATIC REASONING; % CAUSALITY; ABDUCTION; @INPROCEEDINGS{MENZIES94d, AUTHOR = {Tim Menzies and Paul Compton}, TITLE = {A Precise Semantics for Vague Diagrams}, BOOKTITLE = {Proceedings of AI '94}, YEAR = {1994}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { This article discusses what semantics can be obtained from Vague Causal Diagrams, without having to request more information from the expert or the domain. This article also discusses abduction and introduces exhaustive abduction (HT4), and how it can be applied to Vague Causal Diagrams to demonstrate what behaviours are categorically impossible. Note that exhaustive abduction (HT4) can only be applied to finite domains. This article also discusses some experimental results obtained by applying exhaustive abduction (HT4) to the Smythe 1989 model, and the infamous results obtained by the mutation study. (Note that in this article |V|=800 and |E|/|V|=4). } } % KEYWORDS: @INPROCEEDINGS{MENZIES94e, AUTHOR = {Tim Menzies and Paul Compton}, TITLE = {Knowledge Acquisition for Performance Systems; or: When can "Tests" Replace "Tasks"?}, BOOKTITLE = {Proceedings of the 8th AAAI-Sponsored Banff Knowledge Acquisition for Knowledge-Based Systems Workshop}, YEAR = {1994}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Banff, Canada}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: EXPERT SYSTEMS; KNOWLEDGE ENGINEERING; KNOWLEDGE AQUISITION; % ABDUCTION @TECHREPORT{MENZIES95a, AUTHOR = {Tim Menzies}, TITLE = {An Overview of Abduction as a General Framework for Knowledge-Based Systems}, INSTITUTION = {Monash University}, YEAR = {1995}, TYPE = {Article}, NUMBER = {}, ADDRESS = {Department of Software Development, Monash University, Caulfield East, Melbourne, VIC., 3145}, MONTH = {}, NOTE = {}, ANNOTE = { This article explains how abduction and the HT4 algorithm can be applied to many domains, namely prediction, classification, explanation, planning, monitoring, diagnosis, qualitative reasoning, validation, verification, diagrammatic reasoning, multiple-expert knowledge aquisition and decision support systems. This article also discusses the implementation and the practicality of the HT4 algorithm. This article will be a good reference for the relevance section of the proposal, since it has a related work section. } } % KEYWORDS: @TECHREPORT{MENZIES95b, AUTHOR = {Tim Menzies}, TITLE = {An Overview of Limits to Knowledge Level-B Modelling (and KADS)}, INSTITUTION = {Monash University}, YEAR = {1995}, TYPE = {Article}, NUMBER = {}, ADDRESS = {Department of Software Development, Monash University, Caulfield East, Melbourne, VIC., 3145}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: ABDUCTION; MODEL TESTING; LIMITS TO TESTING @INPROCEEDINGS{MENZIES95c, AUTHOR = {Tim Menzies}, TITLE = {Situated Semantics is a Side-Effect of the Computational Complexity of Abduction}, BOOKTITLE = {Australian Cognitive Science Society, 3rd Conference}, YEAR = {1995}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { The purpose of this article is to demonstrate that there is a limit to model construction and that this limit is the same as the limit to testing (i.e. the limit to model testing is the limit to model construction). Testing models cannot be conducted exhaustively. Some subset of the possible tests are chosen and executed. If tests result in model refinement, then different tests can result in different models. This leads to the hypothesis that different individuals form different "opinions" (models). Tim uses and-or graphs in this article. I found and-or graphs a bit confusing, until Tim was able to explain them. } } % KEYWORDS: @INPROCEEDINGS{MENZIES95d, AUTHOR = {Tim Menzies and Paul Compton}, TITLE = {The (Extensive) Implications of Evaluation on the Development of Knowledge-Based Systems}, BOOKTITLE = {Proceedings of the 9th AAAI-Sponsored Banff Knowledge Aquisition for Knowledge Based Systems}, YEAR = {1995}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { It is argued that most KBS domains are vague, and if domains can be characterised accurately, then the heuristic approach that characterises KBS would not be required. It is argued that testing be an on-going procedure for the entire life-cycle of a model. It is argued that coverage of a test suite is more important than internal assessment (i.e. external testing is more important than internal testing). This article discusses the limits to testing, and the infamous results obtained by the HT4 algorithm. This article also discusses some applications of abduction and generalized testing (HT4). } } % KEYWORDS: ABDUCTION; VALIDATION; HT4; @TECHREPORT{MENZIES95e, AUTHOR = {Tim Menzies}, TITLE = {Applications of Abduction No. 2: Knowledge-Level Modelling}, INSTITUTION = {Monash University, Caulfield}, YEAR = {1995}, TYPE = {Article}, NUMBER = {}, ADDRESS = {Department of Software Development, Monash University, Caulfield East, Melbourne, VIC., 3145}, MONTH = {}, NOTE = {}, ANNOTE = {Essential Reading} } % KEYWORDS: ABDUCTION, MODELLING, KNOWLEDGE-BASES @PHDTHESIS{MENZIESPHD, AUTHOR = {Tim Menzies}, TITLE = {Principles for Generalised Testing of Knowledge Bases}, SCHOOL = {School of Computer Science and Engineering}, YEAR = {1995}, ADDRESS = {University of New South Wales P.O. Box 1, Kensington, NSW, Australia, 2033}, MONTH = {January}, NOTE = {Tim Menzies' PhD Thesis}, ANNOTE = { Chapter 1: * "Truth" is socially constructed. * Modelling is an accurate representation of the object being modelled. * The modelling process introduces errors into the representation of the modelled object. * Statement of hypothesis. * Description of Thesis structure. Chapter 2: * Discusses quantitative hypotheses, and gives an example of how to construct a mathematical compartmental model suitable for quantitative hypothesis testing. * Measurements in the quantitative domain can be vast and expensive to collect. Consequently, not all entities are fully measured. * The problems encountered with quantitative modelling in poorly-measured domains encouraged Feldman and Compton to explore qualitative approaches to modelling. * QMOD is a Qualitative Hypothesis Tester. * QMOD (Qualitative MODelling) is an on-line knowledge-base that checks a new model for consistency with those models that already exist in the knowledge-base. * QMOD models are assessed on the basis of their ablity to reproduce known behaviour (as expressed in the database of observations). * JUSTIN is a Model Error Detection facility. * JUSTIN (JUSTification IN context) tests for effects in terms of changes in contexts (i.e. it tests for some pathway through the model starting at a cause and ending in an effect). If such pathways traverse compartments for which no measurements exist, then a value for that compartment that is required for the pathway is assumed. If a model cannot be used to explain changes in the observations after making every assumption possible, and generating all pathways possible, then the model is deemed faulty. } } % KEYWORDS: GENERIC TESTING METHOD (GTM); @ARTICLE{MILLER90, AUTHOR = {L. A. Miller}, TITLE = {Dynamic testing of knowledge bases using the heuristic testing approach}, JOURNAL = {Expert Systems with Applications}, YEAR = {1990}, VOLUME = {1}, NUMBER = {3}, PAGES = {249--269}, MONTH = {}, NOTE = {}, ANNOTE = {Essential Reading} } % KEYWORDS: ABDUCTION; @INPROCEEDINGS{MORRIS90, AUTHOR = {Steven Morris and Paul O'Rorke}, TITLE = {An Approach to Theory Revision Using Abduction}, BOOKTITLE = {Working Notes of the 1990 Spring Symposium on Automated Abduction}, YEAR = {1990}, EDITOR = {}, PAGES = {33--37}, ORGANIZATION = {Stanford University}, PUBLISHER = {}, ADDRESS = {}, MONTH = {March}, NOTE = {}, ANNOTE = {} } % KEYWORDS: @ARTICLE{NAZARETH91, AUTHOR = {Derek L. Nazareth and Miles H. Kennedy}, TITLE = {Verification of rule-based knowledge using directed graphs}, JOURNAL = {Knowledge Aquisition}, YEAR = {1991}, VOLUME = {3}, NUMBER = {}, PAGES = {229--360}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: KNOWLEDGE LEVEL MODELLING; @ARTICLE{NEWELL82, AUTHOR = {A. Newell}, TITLE = {The Knowledge Level}, JOURNAL = {Artificial Intelligence}, YEAR = {1982}, VOLUME = {18}, NUMBER = {}, PAGES = {87--127}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading } } % KEYWORDS: KNOWLEDGE LEVEL MODELLING; @ARTICLE{NEWELL93, AUTHOR = {A. Newell}, TITLE = {Reflections on the Knowledge Level}, JOURNAL = {Artificial Intelligence}, YEAR = {1993}, VOLUME = {59}, NUMBER = {}, PAGES = {31--38}, MONTH = {February}, NOTE = {}, ANNOTE = { Essential Reading } } % KEYWORDS: ABDUCTION; EXPLANATION; @INPROCEEDINGS{NG90, AUTHOR = {Hwee Tou Ng and Raymond J. Mooney}, TITLE = {The Role of Coherence in Constructing and Evaluating Abductive Explanations}, BOOKTITLE = {Working Notes of the 1990 Spring Symposium on Automated Abduction}, YEAR = {1990}, EDITOR = {}, PAGES = {13--17}, ORGANIZATION = {Stanford University}, PUBLISHER = {}, ADDRESS = {}, MONTH = {March}, NOTE = {}, ANNOTE = { Hwee Tou Ng cautions against using Occam's Razor, since it is not sufficient by itself to select the best explanation. HT4's BEST4 assessment operator may be described as using Occam's Razor to select the best "explanations". ``Another problem in constructing a good explanation is determining the appropriate level of specificity of an abductive proof. Previous approaches fall into one of three categories: most specific abduction, least specific abduction, and weighted abduction. ``In most specific abduction, the assumptions made must be basic, i.e. they cannot be "intermediate" assumptions that are themselves provable by assuming some other (more basic) assumptions....In least specific abduction, the only allowable assumptions are literals in the input observations. Stickel (1988) claims that least specific abduction is best suited for natural language interpretation. It is argued that what one learns from reading a piece of text is often close to its surface form, and that assuming deeper causes is unwarranted. In weighted abduction, weights (or costs) are assigned to the antecedents of backward-chaining rules in order to influence the decision on whether to backchain on a rule. in this case, the best interpretation is the one with assumptions that have the lowest combined total cost.'' Hwee Tou Ng argues that there are some problems with using weighted abduction, as the following quote suggests: ``The weighted abduction of Hobbs et. al. (1988) would presumably arrive at the correct interpretation given the "appropriate" set of weights. However, it is unclear how to characterize the "semantic contribution" of each antecedent in a rule in order to assign the appropriate weights....It also provides too many degrees of freedom, which can lead to the knowledge engineer "hacking up" arbitrary weights in order to get the system to produce the desired explanation.'' Hwee Tou Ng have successfully implemented a form of beam search that has successfully computed the preferred interpretation of a number of examples, very efficiently. This was done, primarily to solve the intractible nature of abduction. This approach appears to be similar to HT4's marking relevant vertices in the forward sweep. In general, this article discusses some problems faced by abductive inference. } } % KEYWORDS: ABDUCTION; @INPROCEEDINGS{NORVIG90, AUTHOR = {Peter Norvig and Robert Wilensky}, TITLE = {Problems with Abductive Language Understanding Models}, BOOKTITLE = {Working Notes of the 1990 Spring Symposium on Automated Abduction}, YEAR = {1990}, EDITOR = {}, PAGES = {18--22}, ORGANIZATION = {Stanford University}, PUBLISHER = {}, ADDRESS = {}, MONTH = {March}, NOTE = {}, ANNOTE = { Yeah, I had problems understanding this, as the title of this article suggests! Norvig and Wilensky also argue that a single number cannot represent event the cost and quality of an explanation. This article discusses problems faced with using abductive inference for explaination. HERE } } % KEYWORDS: @INPROCEEDINGS{ORORKE90, AUTHOR = {Paul O'Rorke}, TITLE = {Integrating Abduction and Learning}, BOOKTITLE = {Working Notes of the 1990 Spring Symposium on Automated Abduction}, YEAR = {1990}, EDITOR = {}, PAGES = {30--32}, ORGANIZATION = {Stanford University}, PUBLISHER = {}, ADDRESS = {}, MONTH = {March}, NOTE = {}, ANNOTE = {} } % KEYWORDS: EITHER SYSTEM; @INPROCEEDINGS{OURSTON90, AUTHOR = {D. Ourston and R. Mooney}, TITLE = {Changing the rules: A comprehensive approach to theory refinement}, BOOKTITLE = {Proceedings of the Eighth Natinal Conference on Artificial Intelligence (AAAI '90)}, YEAR = {1990}, EDITOR = {}, PAGES = {815--820}, ORGANIZATION = {}, PUBLISHER = {Morgan-Kaufman}, ADDRESS = {Boston}, MONTH = {August}, NOTE = {}, ANNOTE = { There are two forms of incorrectness, namely overgenerality and overspecificity. Overgenerality is caused by either 1) an incorrect rule is present in the theory, or 2) an existing rule is missing a constraint from its premise. Overspecificity is caused by either 1) a rule in the theory has an additional incorrect constraint, or 2) the theory is missing a rule which is necessary in the proof of certain examples. Generally, an incorrect theory can have both overly- general and overly-specific aspects. EITHER is a theory revision system that detects and corrects the above faults, using one or more failing examples to learn single or multiple corrections to the theory, as appropriate. The objective is to remove all of all of the provable negative examples. Because EITHER starts with an initial theory, fewer examples are required to obtain an accurate theory compared with a purely inductive approach. ``...an assumption is an assertion which, if assumed about a particular example, would allow the proof of the example to be completed.'' ``More importantly, from our point of view, assumptions are literals which, if removed from the premises of the rule in which they are used, would generalize the theory in such a way that the proof attempt would succeed. Constructing partial proofs is a form of abduction.'' Ourston and Mooney adopt the Occam's razor heuristic of finding the minimum number of assumptions required to cover all of the failing examples. } } % KEYWORDS: EXPLANATION; @INPROCEEDINGS{PARIS87, AUTHOR = {C. Paris}, TITLE = {Combining discourse strategies to generate descriptions along a naive/expert spectrum.}, BOOKTITLE = {IJCAI '87}, YEAR = {1987}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Milan, Italy}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading. In this article, Paris describes her framework for explanation. } } % KEYWORDS: CAUSAL REASONING; EXPECTATION-EVOKING; EXPLANATION-EVOKING; @INPROCEEDINGS{PEARL87, AUTHOR = {J. Pearl}, TITLE = {Embraciing causality in formal reasoning}, BOOKTITLE = {AAAI}, YEAR = {1987}, EDITOR = {}, PAGES = {369--373}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { This article contains an example, which Console et. al. use to demonstrate the definition of abduction. The purpose of this paper is to draw attention to certain aspects of default causal reasoning, namely expectation- evoking reasoning and explanation-evoking reasoning. The former describes associations among events in the outside world (e.g. fire is typically accompanied by smoke), while the latter describes how we reason about the world (e.g. smoke normally suggests fire). Given B-->A, Pearl suggests a mechanism that is sensitive to how B was established. If B was established by direct observation or by strong evidence supporting it, the default rule B-->A should be invoked. If, on the other hand, B was established by EXPECTATION, ANTICIPATION, or PREDICTION, then B-->A should not be invoked, no matter how strong the expectation. ``The mental act of imagining the likely consequences of an hypothesis does not activate other, remotely related, hypotheses just because the latter could also cause the imagined consequence. For an extreme example, we would not interject the possibility of a lung cancer in the context of a car accident just because the two (accidents or cancer) could lead to the same eventual consequences -- death.'' ``The essence of the causal assymmetry stems from the fact that two causes of a common consequence interact differently than two consequences of a common cause; the former COMPLETE with each other, the latter SUPPORT each other. Moreover, the former interact when their connecting proposition is CONFIRMED, the latter interact only when their connecting proposition is UNCONFIRMED.'' ``Prediction facilities are also essential in interpretive tasks such as language understanding because they help explain behavior of other planning agents around.'' Pearl attempts to propose a method to implement retraction of rules in a knowledge base, without introducing exceptions. This article is very falsifiable. Note that HT4 does not distinguish between the effect of causal asymmetry as defined by Pearl. } } % KEYWORDS: SEEK SYSTEM; @BOOK{POLITAKIS85, AUTHOR = {P. Politakis}, TITLE = {Empirical analysis for expert systems}, PUBLISHER = {Pitman}, YEAR = {1985}, VOLUME = {}, SERIES = {}, ADDRESS = {London}, EDITION = {}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading Note that I am not certain whether this reference is a book title or article. } } % KEYWORDS: ABDUCTION; @INPROCEEDINGS{POOLE89, AUTHOR = {David Poole}, TITLE = {Normality and faults in logic-based diagnosis}, BOOKTITLE = {Eleventh International Joint Conference on Artificial Intelligence (IJCAI '89)}, YEAR = {1989}, EDITOR = {}, PAGES = {1304--1310}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Detroit, Michigan USA}, MONTH = {August}, NOTE = {}, ANNOTE = { Poole argues that there are two models of diagnosis: 1) Consistency-based diagnosis: this is a minimal set of abnormalities such that the observations are consistent with all other components acting normally (reference to Reiter 1987). 2) Abductive diagnosis: this is a minimal set of assumptions which, with the background knowledge implies the observations (reference to Poole 89). In terms of the Theorist framework, consistency based diagnosis can be described as corresponding to an extension (in particular, the set of abnormalities in an extension), where * F is the domain model together with the observations, * H is the set of normality assumptions. In terms of the Theorist framework, abductive diagnosis can be described as a minimal explanation of the observations, where * F is the domain model, * H is the set of normality and fault assumptions. The main difference is that in abductive model, the diagnoses entail the observations, whereas in the consistency based model, the observations entail the (disjuct of the) diagnoses. Poole argues that the proposals to formalise the notion of diagnostic reasoning have generally considered two extremes of the diagnostic problem: 1) There is knowledge about how components are structured and work normally. There is no knowledge as to how malfunctions occur and manifest themselves. Diagnosis consists of isolating deviations from normal behaviour. This has normally been the preserve of consistency based approaches (reference to Genesereth 1984, and deKleer 1987). 2) We have just information on faults (diseases) and their symptoms, and want to account for abnormal observations. This has traditionally been the preserve of abductive approaches (reference to Pople 1973, Reggia 1983, and Poole 1989). Poole combines these two formalisms of diagnoses, in his Theorist framework. ``For the abductive diagnosis and consistency-based diagnoses where we just assume the absence of faults, if there is no fault information, we have to treat abnormality as a fault.'' Poole argues that consistency-based diagnosis relies on complete knowledge. Consequently, this makes it very difficult to add new knowledge about faults. ``Complexity is a property of a problem and an algorithm, it is not a property of a programming language.'' Consistency based diagnosis requires observations to be a conjunct of observations, whereas abductive diagnosis requires the implication of observations. The simplest explanation is that both systems require the input to be a fact (see example 5.1). Poole argues that there is no one representation which can lay claim to be the ``one true logical definition of diagnosis''. ``One major difference between the diagnostic approaches is that in the abductive systems normality and faults are treated symmetrically, whereas in the consistency (based) approaches, they are treated as opposites.'' In his definition of abductive inference, Poole assumes that all the observations must be covered by a diagnosis. In HT4 terms, Poole is using $BEST_4$. Note that HT4 does not cater for noise in the measurements. } } % KEYWORDS: ABDUCTION; @ARTICLE{POOLE90, AUTHOR = {David Poole}, TITLE = {A Methodology for Using a Default and Abductive Reasoning System}, JOURNAL = {International Journal of Intelligent Systems}, YEAR = {1990}, VOLUME = {5}, NUMBER = {}, PAGES = {521--548}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading Note that Poole's abductive definition is consistent with Menzies'. } } % KEYWORDS: ABDUCTION; DIAGNOSIS; @INPROCEEDINGS{POPLE73, AUTHOR = {H. E. Pople}, TITLE = {On the mechanization of abductive logic}, BOOKTITLE = {IJCAI}, YEAR = {1973}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading Pople first noted the connection between abduction and diagnosis. } } % KEYWORDS: KNOWLEDGE-BASE SYSTEMS; VERIFICATION; TESTING; TOOLS; @INPROCEEDINGS{PREECE92a, AUTHOR = {Alun D. Preece and Rajjan Shinghal}, TITLE = {Verifying Knowledge Bases by Anomaly Detection: An Experience Report}, BOOKTITLE = {10th European Conference on Artificial Intelligence}, YEAR = {1992}, EDITOR = {B Neumann}, PAGES = {835--839}, ORGANIZATION = {}, PUBLISHER = {John Wiley and Sons, Ltd.}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { Preece and Shinghal report on the complexity of detecting most knowledge base system anomalies. Although knowledge base extension checks (e.g. reported by Reggia in his KB-Reducer algorithm) have been criticized in the past for their theoretical complexity limitations, there is evidence to suggest that these techniques will very often be practical in real-world systems development. The reason for this is that the extension checks are when inference chains are fairly short. Preece's experience, and anecdotal evidence suggests that short inference chains may be far more common in practice that long inference chains. } } % KEYWORDS: @ARTICLE{PREECE92b, AUTHOR = {Alun D. Preece and Rajjan Shinghal and Aida Batarekh}, TITLE = {Principles and practice in verifying rule-based systems}, JOURNAL = {The Knowledge Engineering Review}, YEAR = {1992}, VOLUME = {7}, NUMBER = {2}, PAGES = {115--141}, MONTH = {}, NOTE = {}, ANNOTE = { This article argues that verification cannot replace empirical testing of expert systems, however, it can increase the productivity of testing by eliminating many of the errors prior to testing. This article restricts its discussion to knowledge bases that do not contain certainty factors (similar to Menzies' vague domains). The objective of this article is to identify and formalize rule base anomalies, so as to provide a well defined basis for developing automatic procedures for detecting them. This article identifies and formalizes four types of anomolies, namely redundancy, ambivalence, circularity and deficiency. The article then analyses five verification tools, namely the Rule Checker Program, the CHECK Program, the KB-Reduction Algorithm, the EVA system, and the COVER tool, in context of the anomalies. The authors admit that full verification of redundancy, ambivalence, circularity, and deficiency is intractable. "Two methods of overcomming this are: providing methods for modularizing and paritioning knowledge bases, so as to check the less complex components separately; or by using heuristics to focus the search for likely anomalies." The authors recommend that procedural and declarative knowledge be clearly separated in all knowledge bases. } } % KEYWORDS: ABDUCTION; @INPROCEEDINGS{REGGIA85, AUTHOR = {James A. Reggia}, TITLE = {Abductive Inference}, BOOKTITLE = {Proceedings of the Expert Systems in Government Symposium}, YEAR = {1985}, EDITOR = {}, PAGES = {484--489}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { Note that Reggia's definition of abduction is consistent with Menzies'. Reggia realizes the connection between diagnosis, natural language processing, and abduction. ``Abductive inference can be described as probabilistic, parsimoneous and context-sensitive disambiguation using associative knowledge. Its goal is the derivation of solutions that best account for given data. Typically, a non-monotonic reasoning process is used to construct these solutions rather than just to select them from predefined alternatives.'' ``First, it is clear that both diagnostic reasoning and natural language processing involve the use of associative knowledge, i.e. associations between conceptual units.'' ``A second feature that characterizes the structure of the information underlying abductive inferences is ambiguity. In other words, for any given concept there are typically multiple associations with other related concepts that can be viewed as alternatives.'' ``A third feature characterizing the information used in both diagnostic problem solving and natural language processing is its inherently probabilistic nature.'' The following quote supports the fact that HT4 uses a global network to derive its abductive inferences: ``Disambiguation of a cue A (manifestation, word, letter, etc.) is also dependent upon other cues that form the context of cue A. As a result, inferences made during abductive information processing are inherently a global function of the available cues.'' ``Finally, real-world diagnostic problem solving and natural language processing usually occur in the face of incomplete information (incomplete specification of a specific problem and incomplete or imprecise underlying associative knowledge). Any inferences made necessarily involve a great deal of "default reasoning" that may subsequently have to be revised.'' ``Abductive inference thus centers on probabilistic, parsimoneous and context-sensitive disambiguation, and it involves the construction of solutions rather than just selection from predefined alternatives.'' Note that reading this article (and Hwee Tou Ng's article) has made me realize that HT4's best assessment operators are parsimoneous, reflecting "Occam's Razor": the simplest explanation is the preferable one. Hwee Tou Ng cautions against using such parsimoneous explanations. Note that "generators" in this article, are equivalent to HT4's cross product of proofs. Reggia's abductive inference engine lacks probabilistic knowledge! Furthermore, it fails to discuss explanations in context! The reason Reggia's abductive inference engine lacks probabilistic knowledge, could be explained by his following quote: ``At the present time, parsimonious covering in its most general form appears to be a leading contender as a formal model for abductive problem solving. Probability theory and statistical pattern classification methods appear inadequate, at least in isolation, to capture such features of abduction as its constructive nature.'' } } % KEYWORDS: @TECHREPORT{RUSHBY90, AUTHOR = {J. Rushby and J. Crow}, TITLE = {Evaluation of an expert system for fault detection, isolation, and recovery in the manned maneuvering unit}, INSTITUTION = {NASA Contractor Report CR-187466}, YEAR = {1990}, TYPE = {}, NUMBER = {}, ADDRESS = {Menlo Park, CA}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading Rushby and Crow \cite{RUSHBY90} have demonstrated that, using symmetric equivalence classes, the reduced set of randomly generated test cases is adequate to test the equivalence class fully. } } % KEYWORDS: @INPROCEEDINGS{SCARL92, AUTHOR = {Ethan Scarl}, TITLE = {The Utility of Diagrammatic Representation for Model-Based Reasoning}, BOOKTITLE = {Symposium: Reasoning with Diagrammatic Representations}, YEAR = {1992}, EDITOR = {N. Hari Narayanan}, PAGES = {237--240}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Stanford University, California}, MONTH = {March}, NOTE = {}, ANNOTE = { Diagrammatic Representations offer more advantages over usual system representations (such as assertional representational methods) in some cases. Direct representations are comparable to analog representations for monitoring, simulation, and hypothesis testing. Direct representations appear to be more difficult to use for hypothesis generation tasks. There exist circumscribed but important conditions in which Diagrammatic Representations can usefully supplement assertional representations for determining unexpected interaction pathways. (Two examples are given, namely rotor blades and solder splashes.) Diagrammatic Representations are most appropriate for geometric and kinematic domains. The terms (Direct/Analog) models are used interchangeably with the terms (Direct/Analog) domains respectively. Diagrammatic Respresentations are generally more difficult to use for Model-Based Reasoning than comparable assertional representations. } } % KEYWORDS: @BOOK{SEDGEWICK88, AUTHOR = {Robert Sedgewick}, TITLE = {Algorithms}, PUBLISHER = {Addison-Wesley}, YEAR = {1988}, VOLUME = {}, SERIES = {}, ADDRESS = {Reading, Massachusetts}, EDITION = {Second}, MONTH = {}, NOTE = {}, ANNOTE = {} } % KEYWORDS: @INBOOK{SEDGEWICK88a, AUTHOR = {Robert Sedgewick}, TITLE = {Algorithms}, CHAPTER = {6}, PAGES = {67--79}, PUBLISHER = {Addison-Wesley}, YEAR = {1988}, VOLUME = {}, SERIES = {}, ADDRESS = {Reading, Massachusetts}, EDITION = {Second}, MONTH = {}, NOTE = {}, ANNOTE = { Chapter 6: Analysis of Algorithms "The goal of the study of computational complexity of an algorithm is to show that its running time is O(f(N)) for some function f, and there can be no algorithm with a running time of O(g(N)) for any `smaller' function g(N) (a function with lim(n->infinity) g(N)/f(N) = 0)." When computational studies show that the upper bounds of an algorithm matches its lower bounds, then it is useless to try and develop an algorithm wich is fundamentally faster. No-one should blindingly follow the complexity result expressed in O-notation. Computational complexity is designed to avoid problems associated with differences in execution times between computers. } } % KEYWORDS: @INBOOK{SEDGEWICK88b, AUTHOR = {Robert Sedgewick}, TITLE = {Algorithms}, CHAPTER = {45}, PAGES = {633--641}, PUBLISHER = {Addison-Wesley}, YEAR = {1988}, VOLUME = {}, SERIES = {}, ADDRESS = {Reading, Massachusetts}, EDITION = {Second}, MONTH = {}, NOTE = {}, ANNOTE = { Chapter 45: NP-Complete Problems P: the set of all problems that can be solved by deterministic algorithms in polynomial time. NP: the set of all problems that can be solved by non-deterministic algorithms in polynomial time. Note that any problem in P is also in NP. "...The time taken by an algorithm obviously depends on the computer used, but it turns out that using a different computer affects the running time by only a polynomial factor..." (This statement is in context of deterministic algorithms with completely specified models of computation). If it can be proved that a problem does not belong to P, then the search for an efficient algorithm can be abandoned. Dimensions in Literature Review: - Deterministic vs. Non-Deterministic - HT4 is a non-deterministic algorithm (or more precisely, problems solved by HT4 are non-deterministic). - Tim has attempted to make HT4 as efficient as possible on a deterministic machine! NP-complete problems are non-deterministic problems that can be solved in polynomial time on a deterministic machine. The method used to prove that problems are NP-complete use the idea of polynomial reducability (see p. 636). "...To prove that a problem in NP is NP-complete, we need only show that some known NP-complete problem is polynomially reducible to it: that is, a polynomial-time algorithm for the new problem can be used to solve the NP-complete problem, and can then...be used to solve all problems in NP." Does this imply that HT4 can be used to solve other problems in NP (if HT4 is indeed NP-complete)? "...Polynomial reduction can be applied to quite dissimilar problems." "Each problem that is proven NP-complete provides another potential basis for proving yet another future problem NP-complete." "The fact that no good algorithm has been found for any of these problems (NP-complete problems) is surely strong evidence that P <> NP....On the other hand, the fact that no-one has been able to prove that any of these problems (NP-complete problems) do belong ot P could be construed to comprise a similar body of circumstantial evidence on the other side." } } % KEYWORDS: ATMS; ABDUCTION; DEFAULT REASONING; EXPLANATION; ASSUMPTION-BASED ABDUCTION; GOAL-DIRECTED ABDUCTION; @INPROCEEDINGS{SELMAN90, AUTHOR = {Bart Selman and Hector J. Levesque}, TITLE = {Abductive and Default Reasoning: A Computational Core}, BOOKTITLE = {AAAI 90}, YEAR = {1990}, EDITOR = {}, PAGES = {343--348}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {}, MONTH = {}, NOTE = {}, ANNOTE = { Selman and Levesque report that using abduction to explain some propositional letter q, can be calculated in polynomial time (NP-Complete). Selman and Levesque report that assumption-based abduction and goal-directed abduction are both NP-hard, even when theories are restricted to acyclic Horn clauses, and a single explanation is required. Selman and Levesque also report a strong connection between computing explanations and computing extensions in default logic. They argue that their Support Selection Task is at the core of both procedures. Selman and Levesque argue that their Support Selection Task (abductive inference) is at the core of both assumption based abductive reasoning and goal-directed abductive reasoning. Note that Selman's abductive definition is consistent with Menzies'. Reading this article has made me realize that HT4 employs an ATMS style reasoning, to validating theories. Future work for HT4: Develop a PWFP instance, as described in this article, using the model compiler, and obtain the runtimes using HT4. } } % KEYWORDS: ONCOCIN KB; SCRIPTGEN; @ARTICLE{SHWE89, AUTHOR = {M. A. Shwe and S. W. Tu and L. M. Fagan}, TITLE = {Validating the knowledge base of a therapy planning system}, JOURNAL = {Methods of Information in Medicine}, YEAR = {1989}, VOLUME = {28}, NUMBER = {1}, PAGES = {36--50}, MONTH = {}, NOTE = {}, ANNOTE = { Validation may be classified under two categories: 1) Static analysis: embraces the validation methods that do not require execution of the program (e.g. examining the code of a program), 2) Dynamic analysis: embraces the validation methods that do requrire execution of the program (e.g. system testing). ``A medical consultation system must demonstrate a high degree of accuracy to gain acceptance.'' The author argues that static validation techniques are not a practical means of demonstrating the correctness of ONCOCIN. In addition, the authors argue that program verification (static validation) is not well suited for the size of typical AI programs and their associated knowledge bases. Thus the authors restrict validation to dynamic methods. The manual method for developing scripts (test cases generated from templates), has several drawbacks, two of which are: 1) The creator of the test script has to painstakingly specify each of the patient parameters for each visit: a typical script of 10 visits with 20 patient parameters, requires 200 data items. 2) The manual approach is not systematic, and thus can lead to important test cases being missed. Methods for test-data generation can be classified into three primary categories: 1) pathwise test-data generators, 2) data-specification systems, 3) random test-data generators. Pathwise test-data generation consists of four steps: 1) A directed (digraph) of the program is constructed. 2) Paths in the program graph are selected. 3) Each of the program paths is symbolically executed to determine the constraints on the input data for traversal of the path. 4) The symbolic constraints are interpreted to construct test data. ``The most challenging step is the second one -- selection of program paths. A possible goal might be to select paths such that each statement in the program is executed at least once. Huang points out that a data set that satisfies this criterion may fail to test certain paths of a program; flow control errors may go undetected.'' (Note that Jacobson has also pointed this out in his text book publication of Object Oriented Software Engineering). Testing all paths in a program might seem like a good solution, however, this approach may lead to a prohibitively large number of test cases, since programs may contain loops. (This point is also argued by Jacobson). Another approach entails traversing every edge, in a directed graph, at least once. A data set that satisfies this criterion is called minimally thorough. A data-specification system, on the other hand, provides the user with a language for specifying the input test data. It may be useful for dynamic testing of a program when a pathwise generation approach is not satisfactory. A program to be tested may be so large and complex that minimally thorough testing is not practical even as a minimal criterion. ``Random test-data generators randomly select data points from the domains of the program's paths of each input variable. Demillo reports that for a generator to produce good random testing, it must have some information about the particular, so that it can restrict the intervals from which it selects data. Nonetheless, a study by Duran and Ntafos revealed that purely random testing is likely to uncover errors at a rate comparable to that realized by more structured methods (e.g. pathwise-generation).'' The authors classify the thoroughness of a dynamic validation system into the following four categories: 1) Testing of all permutations of paths 2) Minimally thorough testing 3) Testing of certain paths 4) Testing of random paths ``Because of the large number of test cases necessary to cover all path permutations, we cannot practically test the ONCOCIN KB according to the criterion of category 1.'' ``Despite the favorable random-testing results of Duran and Ntafos, we avoid random testing of protocols because of the difficulty in reviewing the behavior of the expert system being tested with the randomly generated data.'' ``Because the time of an oncologist reviewing the ouptut of ONCOCIN is limited, we find it more practical to concentrate on the test cases that contain plausible patterns of patient response to therapy.'' Hence the authors adopt the criterion of testing category 3. This is also the reason they abandon testing category 2. ``For the purpose of validating the ONCOCIN KB, we do not use the white-box approach to generate test cases. in validating the ONCOCIN KB, we are seeking instances where the KB exhibits behaviour that deviates from that dictated by the specifications -- the cancer therapy protocols. If the KB itself is used, we will test at most only those cases that can be generated from the information in the KB. Thus, if the ONCOCIN protocol fails to contain all the information contained in the protocol document that it represents, white-box testing will omit cases that should be tested.'' ``Because of the hazards of deriving test data from the ONCOCIN KB itself, it is best to construct a parallel model of the ONCOCIN protocol, according to the protocol documentation. Furthermore, the constructor of the parallel model should not be the knowledge engineer who created the KB protocol. If the knowledge engineer constructs both the original KB and the parallel model, then the errorrs in the original KB probably will appear in the parallel KB.'' ``It is possible to think of the parallel KB in the ScriptGen system as a functional specification.'' ``ScriptGen employs equivalence partitioning and boundary-value analysis to create values for patient data.'' ``Multiple scripts created for the same protocol and from the same template should produce the same ONCOCIN recommendations, because the variations in numbers are within equivalence classes....It is possible, however, for the sequence of recommendations to deviate from the template if the ONCOCIN KB and the ScriptGen KB are functionally discordant (e.g. due to an error in the ONCOCIN KB or in the ScriptGen KB).'' ``A common criticism of the data specifications method is that it preserves the biases of the person who makes the specifications.'' The evaluation study suggests the types of errors in the ONCOCIN KB that are not detected by ScriptGen are: 1) Rules that contain a patient variable that is not found in the script for testing the given protocol. 2) Errors that give rise to discordant behaviour not exhibited in ONCOCIN's output report (e.g. number of drug doses). 3) Redundant rules. 4) Circularity. Note that the presence of redundant rules makes it possible that deliberate changes to one of the redundant rules will be erroneously overridden by the unchanged counterpart. The authors' experience with ScriptGen shows that the system is likely to detect the following types of errors: 1) Rules that query patient parameters contained in the ScriptGen script. 2) Rules that erroneously pertain to a less-restricted subset of the protocol (e.g. a rule for POCC that erroneously also fires in the VAM cycle). 3) Rules that contain errors in the boundary values of patient parameters. 4) Missing rules. ``Another shortcomming of the ScriptGen methodology is the system's lack of understanding of the physiology underlying the patient's response to chemotherapy. Because of this limitation, ScriptGen may produce data that are physiologically unlikely or even impossible.'' A similar thing can be said about the data compiler of HT4. It can produce test cases (a set of behaviours) that are unlikely or even impossible. ``...It would be useful to catch obscure errors in the ONCOCIN KB (i.e. errors that would arise only in bizarre patterns of patient responses). Subject to the constraint on the number of scripts, however, it seems prudent to construct scripts that are most clinically relevant.'' ``The ScriptGen system is a tool that allows a consulting oncologist to create test cases for validating the ONCOCIN KB. Since ScriptGen is a data-specification system, it allows an oncologist-user to specify what she or he believes to be likely patterns of patient responses to therapy. Because of the complexity of protocols in the ONCOCIN KB, we find that it is most practical to generate and test the clinically relevant cases -- as opposed to creating a minimally thorough test set, which would comprise a sizable number of test cases and would include a large proportion of clinically remote patterns. Although a data specification system allows the biases of the user of the system to appear in the test cases, it is still prudent to concentrate on the likely scenarios. A knowledge base validation tool such as ScriptGen allows us to expedite the creation of these cases.'' Note that ScriptGen uses a parallel model to generate tests cases to test the ONCOCIN KB. Menzies cautions against this since the parallel model is a surrogate of the entity being modelled, and furthermore, it may contain errors. } } % KEYWORDS: @ARTICLE{SILVERMAN92, AUTHOR = {Barry G. Silverman}, TITLE = {Survey of Expert Critiquing Systems: Practical and Theoretical Frontiers}, JOURNAL = {Communications of the ACM}, YEAR = {1992}, VOLUME = {35}, NUMBER = {4}, PAGES = {106--127}, MONTH = {April}, NOTE = {}, ANNOTE = { The purpose of this article is to survey the developments of critiquing systems to date. This article also discusses the latest advances in critiquing theory to date. The author's definition of critics will include programs that first cause their users to maximize the falsifiability of their statements and then proceed to check if errors exist. Critiquing in an electronic work environment occurs when one is attempting to complete a specific task. The input of the environment consists of (1) the problem description (e.g. the patient's symptoms, design requirements, or type of document to be created). (2) The second input is the proposed solution to the problem, such as a completed diagnosis, a final design, or a finished document. The output of the environment is critisism of the proposed solution. The critic functions by using a "differential analyser" and "dialogue generator": The differential analyser infers the user's goal and compares the user's task result (proposed solution) to that produced by an expert module which is often a knowledge base of rules that an expert would run to perform the task. The dialogue generator receives a file of errors from the differential analyzer, parses it into a user- presentable form, and displays it on the screen. Critics can be programmed to perform the following four credibility conditions which are tests for clarity, coherence, correspondence, and workability on a body of knowledge. Note that a body of knowledge can be rejected if it fails any of these four tests. Clarity Testing: Clear statements are easier to falsify than ambiguous ones. This makes them more testable. Clarity testing tests whether or not a statement is falsifiable. A statement passes the clarity test if it is falsifiable. Coherence Testing: This deals with the logical structure of of sentences and statements. Coherence testing tests whether the result omits knowledge about the problem at hand. It checks for completeness and consistency. Note that verification equates to coherence testing. Correspondence Testing: This concerns the agreement of statements with reality. It is a test to find out if a body of knowledge omits situations, experience, and/or empirical information that one knows to be relevant for practical problems of the real world. Note that validation equates to correspondence testing. Workability Testing: This concerns checking whether a body of knowledge leads to descriptions or prescriptions that are unworkable (e.g. errors of ommission or commission). Miller's research (references 17 and 18) suggest that differences in the kinds of problems to be solved leads to the importance of different critic architectures and algorithms in the critic's differential analyser. His principle finding was that simpler differential analyzer algorithms apply to domains where the possible number of correct answers on any given task were few. Critiquing by reacting occurs when: (1) specific rules can be written for each type of wrong answer; (2) the rules for assessing user solution optimally are objective and few; (3) only one or two possible correct outcomes exist for that task; and (4) each subtask can be critiqued independently of the others. Critiquing by local risk analysis: This occurs when conditions (1) to (3) deteriorate and the domain has numerous feasible solutions and primarily subjective standards for evaluation of the risks and benefits of a number of alternative solutions. These are dynamically instantiated with the values with the values of the current problem to determine if the user-proposed solution falls within the envelope of acceptable solution sets. Critiquing by global plan analysis: This occurs when condition (4) does not hold for a given domain, and critiquing cannot simply address an isolated portion of the proposed solution. Under such circumstances, critiquing must adopt a global view to examine the totality of what the user is suggesting. Experiments on the value of during- versus after-task critiquing have so far proved inconclusive. } } % KEYWORDS: @BOOK{SMYTHE89, AUTHOR = {G. A. Smythe}, TITLE = {Brain-hypothalmus, Pituitary and the Endocrine Pancreas}, PUBLISHER = {Raven Press}, YEAR = {1989}, VOLUME = {}, SERIES = {}, ADDRESS = {New York}, EDITION = {}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading Note that Feldman and Compton were able to fault the Smythe 89 model on brain regulation of glucose. } } % KEYWORDS: @ARTICLE{SMYTHE92, AUTHOR = {G. A. Smythe}, TITLE = {Concerning Errors in the Smythe '87 model}, JOURNAL = {Personal Communication}, YEAR = {1992}, VOLUME = {}, NUMBER = {}, PAGES = {}, MONTH = {}, NOTE = {}, ANNOTE = {Essential Reading} } % KEYWORDS: @INPROCEEDINGS{STICKEL90, AUTHOR = {Mark E. Stickel}, TITLE = {A Method for Abductive Reasoning in Natural Language}, BOOKTITLE = {Working Notes of the 1990 Spring Symposium on Automated Abduction}, YEAR = {1990}, EDITOR = {}, PAGES = {5--9}, ORGANIZATION = {American Association for Artificial Intelligence and Office of Naval Research}, PUBLISHER = {}, ADDRESS = {}, MONTH = {March}, NOTE = {}, ANNOTE = { This article discusses the abductive explanations of conjunctions of positive literals from Horn clause knowledge bases. The authors argue that predicate specific abduction is not ideal for natural language interpretation. "[The authors] attach numeric assumption costs to assumable literals, and compute minimum-cost abductive explanations in an effort to influence the abductive reasoning system towards favouring the intended explanations." "An abductive proof is complete when all literals are either proved or assumed." } } % KEYWORDS: @BOOK{STROUSTRUP95, AUTHOR = {Bjarne Stroustrup}, TITLE = {The C++ Programming Language}, PUBLISHER = {Addison Wesley}, YEAR = {1995}, VOLUME = {}, SERIES = {}, ADDRESS = {Reading, Massachusetts}, EDITION = {Second Edition}, MONTH = {August}, NOTE = {}, ANNOTE = { Stroustrup argues that intrusive lists are more efficient than template lists. } } % KEYWORDS: ABDUCTION; GENERAL DIAGNOSTIC ENGINE (GDE); MODEL BASED DIAGNOSIS; FAULT MODELS; @INPROCEEDINGS{STRUSS89, AUTHOR = {P. Struss and O. Dressler}, TITLE = {Physical negation - integrating fault models into the general diagnostic engine.}, BOOKTITLE = {Eleventh International Joint Conference on Artificial Intelligence (IJCAI '89)}, YEAR = {1989}, EDITOR = {}, PAGES = {1319--1323}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Detroit, Michigan USA}, MONTH = {August}, NOTE = {}, ANNOTE = { In model-based diagnosis, the model of the device under consideration captures only the normal, or intended behaviour of its components. The General Diagnostic Engine (GDE), proposed by deKleer, exploits the Assumption-Based Truth Mainenance system (ATMS) to provide a general framework for model-based diagnosis. ``The advantages of GDE, besides being model-based, are that it can handle multiple faults, and it does not require fault models. On the other hand, GDE does not exploit knowledge about the faulty behaviour of components.'' GDE+ assumes that only one component is faulty, in order to reduce the search space. GDE appears to do the same processing as HT4. Note that GDE iteratively performs the following steps: 1) Prediction: based on the assumptions that each component works correctly, compute values for system parameters. (This appears to be equivalent to HT4's marking relevant vertices in the forward sweep). 2) Conflict detection: identify those correctness assumptions that are involved in the computation of contradictory values for parameters. (This appears to be equivalent to HT4's marking controversial assumptions in the forward sweep). 3) Candidate generation: construct sets of correctness assumptions that account for the known conflicts (i.e. their conjunctive retraction would remove the contradictions). (This appears to be equivalent to HT4's proof generation and world sweep). 4) Measurement suggestion: propose measurements that are likely to help discriminate among the candidates. (This appears to be equivalent to HT4's best assessment operator, or best selection). GDE+ attempts to integrate fault models in order to diagnose faulty behaviour of a component. Since fault models are applied under the assumption that the respective component is not correct, and since a component is either correct or not, an extended version of the ATMS that is capable of handling negation and disjunction, must be used. Based on this, the authors are able to make inferences like: ``if none of the fault models of a component is consistent with the observations, then it is correct'', or ``if each of the fault models of a component is inconsistent with the observations and the correctness of some other component, then it is not a candidate for a single fault.'' One question raised by this is how do we know that we have specified all of the fault models? The authors go on to state that the completeness of fault models is an essential condition for the inference mechanism presented. If a faulty component exhibits a behaviour that is not captured by one of the fault views, wrong conclusions may be drawn. The following is a definition of controversial assumptions that is equivalent to HT4's controversial assumptions: ``If two contradictory values are computed for the same parameter, the correctness assumptions underlying these computations establish a conflict.'' In their definition of abductive reasoning, Struss assumes that all observations be consistent with a diagnosis. (Observation coverage is weak). } } % KEYWORDS: RULE CHECKER PROGRAM (RCP); @ARTICLE{SUWA82, AUTHOR = {M. Suwa and A. C. Scott and E. H. Shortliffe}, TITLE = {An approach to verifying completeness and consistency in a rule-base expert system}, JOURNAL = {AI Magazine}, YEAR = {1982}, VOLUME = {3}, NUMBER = {4}, PAGES = {16--21}, MONTH = {}, NOTE = {}, ANNOTE = {Essential Reading} } % KEYWORDS: @INPROCEEDINGS{ZLATAREVA92, AUTHOR = {Neli Zlatareva}, TITLE = {A framework for knowledge-based systems verification, validation, and refinement: The VVR system}, BOOKTITLE = {Proceedings of the 4th Florida AI Research Symposium (FLAIRS'92)}, YEAR = {1992}, EDITOR = {}, PAGES = {}, ORGANIZATION = {}, PUBLISHER = {}, ADDRESS = {Ft. Lauderdale, Florida}, MONTH = {}, NOTE = {}, ANNOTE = { Essential Reading The VVR system can generate totally synthetic test cases. } } % KEYWORDS: VVR SYSTEM; @ARTICLE{ZLATAREVA93, AUTHOR = {Neli Zlatareva}, TITLE = {"CTMS": A general framework for plausible reasoning}, JOURNAL = {International Journal of Expert Systems}, YEAR = {1992}, VOLUME = {5}, NUMBER = {3}, PAGES = {229--247}, MONTH = {}, NOTE = {}, ANNOTE = { ABSTRACT: ``In this paper we introduce the Contradiction-tolerant Truth Maintenance System (CTMS) as an alternative to existing knowledge representations formalisms which are intended to simulate only certain types of human reasoning. We claim that in order for the computer to model human intelligence, it must be able to perform a variety of reasoning patterns, as well as to explicitly maintain contradictions, and provide explanations for its beliefs. CTMS can handle knowledge that might be uncertain, incomplete, and inconsistent. It is a non-monotonic system, but unlike other non-monotonic systems its inference rules are monotonic; the non-monotonicity of the reasoning process is a result of the way the rules are applied. On the other hand, similar to methods for handling uncertain knowledge, CTMS propagates uncertainty during the reasoning process, and the evaluation of the plausibility of uncertain beliefs is performed only when the reasoning process is completed, that is when all the evidence relevant to those beliefs is available.'' Methods for handling uncertain knowledge: ``Most of the methods for representing uncertain knowledge and reasoning under uncertainty are based to one extent or another on probability theory.'' Bayes' rule works under the assumption that all pieces of evidence are independent. If this assumption is violated, then Bayes' rule can lead to incorrect results. ``Another problem with probability theory is that it does not provide a way to distinguish between ignorance and uncertainty; it is not always clear whether the degree of belief in a given proposition is defined directly from evidence or indirectly from the absence of evidence.'' (See example). Methods for handling incomplete knowledge: Non-Monotonic Logic (NML) has been developed by (McCarthy 1980; Reiter 1980; McDermott & Doyle 1980) to handle the modelling of incomplete knowledge. An assumption that NML is based on, is that each proposition that belongs to the agent's set of beliefs can be classified as either true or false. This assumption, however, leads to the multiple extension problem, which causes the knowledge base to conclude both a proposition and its negation, depending on the way its reasoning is carried out. NML treats all beliefs in the same way without making any difference between those established evidentually (i.e. by observation), and those established causally (i.e. by different derivations, or by expectation). (See Pearl 1988 and PEARL87, above, for details of causal asymmetry). To summarize the items of concern regarding NML: \begin{itemize} \item{Although NML provides the most natural way to represent and reason with incomplete knowledge, it fails to express any kind of uncertainty, and this leads to the multiple extension problem.} \item{NML is not able to capture the effect of causal asymmetry because it does not recognize how the given belief has been established -- evidentially or causally.} \item{NML employs some sort of conditional independence assumption which can sometimes be a reason for generating wrong conclusions.} \item{NML does not keep track of the evidence related to inferred beliefs; once inferred the conclusion is no longer related to its evidence.} \end{itemize} Methods for handling inconsistent knowledge: ``The common feature of all the methods discussed so far is that none of them can handle inconsistent knowledge. Plausibility theory (Rescher 1976) and the Truth Maintenance System (TMS) (Doyle 1979) address this problem in their intended domain of application; the former copes with inconsistencies originating from the uncertainty of knowledge, while the latter copes with the inconsistencies originating from the incompleteness of knowledge.'' HT4 seems to fit into the latter category. To cope with inconsistencies, a conventional TMS employs a special facility called dependency directed backtracking (DDB). ``Note that there is an important assumption upon which DDB is based: at least one of the elements of the set $\{A_1,...,A_n\}$ must be an assumption node, that is, a node whose justification has a nonempty set of counter-arguments, because one of these counter-arguments must be selected as a culprit for the detected contradiction.'' ``TMS is not able to cope with two other common types of contradictions, namely contradictions originating from contradictory data and contradictions originating from the existence of alternative models of the problem domain. The resolution of such contradictions would require the retraction of premise nodes and nodes supported by monotonic justifications, respectively.'' An alternative approach: (Note that this is quoted) The Contradiction-tolerant TMS (CTMS), which is based on the truth maintenance theory presented in Popchev et. al. 1990, extends the original truth maintenance approach so that it: \begin{itemize} \item{Makes the truth maintenance system able to represent and reason with knowledge which might be both incomplete and uncertain.} \item{Makes it possible for the truth maintenance system to explicitly maintain uncertainty during the reasoning process, as do systems for handling uncertain knowledge.} \item{Makes it possible for the truth maintenance system to handle different types of inconsistencies without trying to resolve them before the reasoning process is completed.} \end{itemize} ``The Contradiction-tolerant TMS additionally extends the notion of plausibility by lifting some of the restrictions imposed on the structure of inference rules, which allows it to capture the effect of causal asymmetry.'' ``The resolution of the detected conflicts should be initiated only after the reasoning process is completed and all the evidence relevant to conflicting beliefs is available.'' Note that HT4 works in a similar fashion. Zlatareva goes on to define terms and definitions that support the CTMS framework. Too many to list here, however, if I should decide to outline the CTMS framework in my literature review, I will need to come back to this. Reading this article has made me realize that HT4 does not distinguish between the effect of causal asymmetry as defined by Pearl 1988. } } % KEYWORDS: @ARTICLE{ZLATAREVA94, AUTHOR = {Neli Zlatareva and Alun Preece}, TITLE = {State of the Art in Automated Validation of Knowledge-Based Systems}, JOURNAL = {Expert Systems With Applications}, YEAR = {1994}, VOLUME = {7}, NUMBER = {2}, PAGES = {151--167}, MONTH = {}, NOTE = {}, ANNOTE = { This article defines the desirable components of an automated validation system: refinement facility, validation facility, and test case generation facility. These components operate from two sources: knowledge base, and test case set. There are two types of validation activities: dynamic validation, and static validation. "Dynamic Validation: describes the activity of using the validation and refinement facilities with a set of test cases (real and/or synthetic) to measure and, if necessary, improve on the performance of the knowledge base." "Static Validation: describes the activity of using the validation and test case generation facilities to create or improve the set of test cases available for validation." To be performed before dynamic validation, or when there is an inadequate set of test cases. "The most common reason for functional (performance) errors in Knowledge Base Systems (KBS) are overgeneralization and overspecification." "Errors that are due to overgeneralization are manifested in the generation of wrong conclusions (false positives)." "Errors that are due to overspecialization are manifested in the failure to generate the expected conclusions." } }