Qualitative Knowledge, Casual Reasoning and the Localization of Failures

This report investigates some techinques appropriate to representing the knowledge necessary for understanding a class of electronic machines -- radio receivers. A computational performance model - WATSON - is presented. WATSONs task is to isolate failures in radio receivers whose principles of operation have been appropriately described in his knowledge base. The thesis of the report is that hierarchically organized representational structures are essential to the understanding of complex mechanisms. Such structures lead not only to descriptions of machine operation at many levels of detail, but also offer a powerful means of organizing "specialist" knowledge for the repair of machines when they are broken.

Causal and Teleological Reasoning in Circuit Recognition

This thesis presents a theory of human-like reasoning in the general domain of designed physical systems, and in particular, electronic circuits. One aspect of the theory, causal analysis, describes how the behavior of individual components can be combined to explain the behavior of composite systems. Another aspect of the theory, teleological analysis, describes how the notion that the system has a purpose can be used to aid this causal analysis. The theory is implemented as a computer program, which, given a circuit topology, can construct by qualitative causal analysis a mechanism graph describing the functional topology of the system. This functional topology is then parsed by a grammar for common circuit functions. Ambiguities are introduced into the analysis by the approximate qualitative nature of the analysis. For example, there are often several possible mechanisms which might describe the circuit's function. These are disambiguated by teleological analysis. The requirement that each component be assigned an appropriate purpose in the functional topology imposes a severe constraint which eliminates all the ambiguities. Since both analyses are based on heuristics, the chosen mechanism is a rationalization of how the circuit functions, and does not guarantee that the circuit actually does function. This type of coarse understanding of circuits is useful for analysis, design and troubleshooting.

A Multiple-Context Equality-Based Reasoning System

Expert systems are too slow. This work attacks that problem by speeding up a useful system component that remembers facts and tracks down simple consequences. The redesigned component can assimilate new facts more quickly because it uses a compact, grammar-based internal representation to deal with whole classes of equivalent expressions at once. It can support faster hypothetical reasoning because it remembers the consequences of several assumption sets at once. The new design is targeted for situations in which many of the stored facts are equalities. The deductive machinery considered here supplements stored premises with simple new conclusions. The stored premises include permanently asserted facts and temporarily adopted assumptions. The new conclusions are derived by substituting equals for equals and using the properties of the logical connectives AND, Or, and NOT. The deductive system provides supporting premises for its derived conclusions. Reasoning that involves quantifiers is beyond the scope of its limited and automatic operation. The expert system of which the reasoning system is a component is expected to be responsible for overall control of reasoning.

Combining Functional and Structural Reasoning for Safety Analysis of Electrical Designs

C.J.Price, D.R.Pugh, N.A.Snooke, J.E.Hunt, M.S.Wilson, Combining Functional and Structural Reasoning for Safety Analysis of Electrical Designs, Knowledge Engineering Review, vol 12:3, pp.271-287, 1997.

Model-Based Reasoning: A Principled Approach for Software Engineering

Lee M.H., Model-Based Reasoning: A Principled Approach for Software Engineering, Software - Concepts and Tools,19(4), pp179-189, 2000.

On Models, Modelling and the Distinctive Nature of Model-Based Reasoning

M.H. Lee, On Models, Modelling and the Distinctive Nature of Model-Based Reasoning, AI Communications, 12 (3), pp127-137.1999.

Qualitative Circuit Models in Failure Analysis Reasoning

Lee M.H., Qualitative Circuit Models in Failure Analysis Reasoning, AI Journal. vol 111, pp239-276.1999.

Characterising Model-Based Reasoning

Lee M.H., Characterising Model-Based Reasoning, Proc. 10th Int. Workshop on Principles of Diagnosis, (DX'99), Loch Awe, Scotland, 1999, pp140-146.

The Use of Graph Grammars for Model-based Reasoning in Diagnostic Expert Systems

Flasinski M. and Lee M.H., The Use of Graph Grammars for Model-based Reasoning in Diagnostic Expert Systems, Prace Informatyczne, Zeszyty Naukowe Uniwersytetu Jagiellonskiego, 9, 1999, pp147-165.

On the use of qualitative reasoning to simulate and identify metabolic pathways

King, R.D., Garrett, S.M., Coghill, G.M. (2005). On the use of qualitative reasoning to simulate and identify metabolic pathways. Bioinformatics 21(9):2017-2026 RAE2008

Fuzzy interpolative reasoning via scale and move transformation

Z. Huang and Q. Shen. Fuzzy interpolative reasoning via scale and move transformation. IEEE Transactions on Fuzzy Systems, 14(2):340-359.

Scale and move transformation-based fuzzy interpolative reasoning: A revisit

Z. Huang and Q. Shen. Scale and move transformation-based fuzzy interpolative reasoning: A revisit. Proceedings of the 13th International Conference on Fuzzy Systems, pages 623-628, 2004.

Lightweight Formal Verification in Classroom Instruction of Reasoning about Functional Code

In college courses dealing with material that requires mathematical rigor, the adoption of a machine-readable representation for formal arguments can be advantageous. Students can focus on a specific collection of constructs that are represented consistently. Examples and counterexamples can be evaluated. Assignments can be assembled and checked with the help of an automated formal reasoning system. However, usability and accessibility do not have a high priority and are not addressed sufficiently well in the design of many existing machine-readable representations and corresponding formal reasoning systems. In earlier work [Lap09], we attempt to address this broad problem by proposing several specific design criteria organized around the notion of a natural context: the sphere of awareness a working human user maintains of the relevant constructs, arguments, experiences, and background materials necessary to accomplish the task at hand. We report on our attempt to evaluate our proposed design criteria by deploying within the classroom a lightweight formal verification system designed according to these criteria. The lightweight formal verification system was used within the instruction of a common application of formal reasoning: proving by induction formal propositions about functional code. We present all of the formal reasoning examples and assignments considered during this deployment, most of which are drawn directly from an introductory text on functional programming. We demonstrate how the design of the system improves the effectiveness and understandability of the examples, and how it aids in the instruction of basic formal reasoning techniques. We make brief remarks about the practical and administrative implications of the system’s design from the perspectives of the student, the instructor, and the grader.

Efficient Support for Common Relations in Lightweight Formal Reasoning Systems

In work that involves mathematical rigor, there are numerous benefits to adopting a representation of models and arguments that can be supplied to a formal reasoning or verification system: reusability, automatic evaluation of examples, and verification of consistency and correctness. However, accessibility has not been a priority in the design of formal verification tools that can provide these benefits. In earlier work [Lap09a], we attempt to address this broad problem by proposing several specific design criteria organized around the notion of a natural context: the sphere of awareness a working human user maintains of the relevant constructs, arguments, experiences, and background materials necessary to accomplish the task at hand. This work expands one aspect of the earlier work by considering more extensively an essential capability for any formal reasoning system whose design is oriented around simulating the natural context: native support for a collection of mathematical relations that deal with common constructs in arithmetic and set theory. We provide a formal definition for a context of relations that can be used to both validate and assist formal reasoning activities. We provide a proof that any algorithm that implements this formal structure faithfully will necessary converge. Finally, we consider the efficiency of an implementation of this formal structure that leverages modular implementations of well-known data structures: balanced search trees and transitive closures of hypergraphs.

Accurate and Efficient Gesture Spotting via Pruning and Subgesture Reasoning

Gesture spotting is the challenging task of locating the start and end frames of the video stream that correspond to a gesture of interest, while at the same time rejecting non-gesture motion patterns. This paper proposes a new gesture spotting and recognition algorithm that is based on the continuous dynamic programming (CDP) algorithm, and runs in real-time. To make gesture spotting efficient a pruning method is proposed that allows the system to evaluate a relatively small number of hypotheses compared to CDP. Pruning is implemented by a set of model-dependent classifiers, that are learned from training examples. To make gesture spotting more accurate a subgesture reasoning process is proposed that models the fact that some gesture models can falsely match parts of other longer gestures. In our experiments, the proposed method with pruning and subgesture modeling is an order of magnitude faster and 18% more accurate compared to the original CDP algorithm.