Semantic Memory

Citation: Quillian, M. Semantic Memory, in M. Minsky (ed.), Semantic Information Processing, pp 227-270, MIT Press, 1968.
Link: Book @ MIT Press Book @ ACM Portal

Summary

The central question is: what constitutes a reasonable view of how semantic information is organized within a person's memory? In other words, how can meanings or words be stored so that human-like use of these meanings is possible? This text proposes a model for such a memory structure, and explains its use in memory dependent tasks: 1) to compare and contrast meanings of two familiar English language words, 2) processing of English text to 'understand' it.

A library of generic concepts for composing knowledge bases

Citation: K. Barker, B. Porter, and P. Clark. A Library of Generic Concepts for Composing Knowledge Bases. First International Conference on Knowledge Capture, October 21-23, 2001.
Link: ACM Portal

Summary

Building a knowledge base traditionally involves a domain expert and a knowledge engineer. A goal of this research is to eliminate the knowledge engineer from this process, that is, to enable domain experts to build their own knowledge bases. A claim of authors' research is that users without knowledge engineering background will be able to represent knowledge from their domain of expertise by using generic components from a small library.

The authors have chosen to build a small library of components, and aim to use composition of these components as the means to achieve coverage, rather than through enumeration of a large number of components.

The research questions are: is such a system (1) easy to master for users not trained in knowledge engineering?, (2) and sufficient to represent sophisticated domain knowledge?

There are three requirements for library components:

• Coverage: The library should contain sufficient components in the library to allow the user to encode a variety of knowledge from any domain. This means defining a restricted set of components which are generic enough to allow a user to compose them consistently, but also be specific enough to allow use in individual domains.
  
• Access: The interface to the library should assist the user in finding appropriate components from the library.
  
• Semantics: The components in the library should have well defined axioms that encode their meanings as well as information about how the component can consistently interact with other components.
  

The library consists of entities and events (states and actions, where states are relatively static situations brought about or changed by actions).

Composition in this system is the ability to connect components in a way that allows inferences beyond the union of individual axioms of the components involved. By using composition, inferences like conditional rules, definitions (reclassification of instances) and simulations can be drawn. However, to achieve these inferences, composition language (relations and properties) must have predictable semantics. Relations connect entities and events (event-entity, entity-entity, event-event, entity-role). Properties link entities to values (cardinal, scalar, categorical etc.)

Evaluation of this library was done through user sessions and user feedback. The criteria for the feedback were (1) ease of finding relevant components, (2) understanding components, (3) use of components to represent knowledge, (4) ease of relations language, and (5) cast biological knowledge in terms of components and relations in the library. The library showed promising results.

Programming by Example

Citation: Henry Lieberman. Programming by Example. In Communications of the ACM, Vol. 43, No. 3, March 2000.
Link: PBE Home

Summary

Programming by example, PBE, (or programming by demonstration) is a radically different approach to programming. A software agent records the interactions between the user and a conventional 'direct manipulation' interface and writes a program corresponding to the user's actions. The agent can then generalize the program based on other examples. 'Generalization' is the central problem to PBE.

Two notable PBE systems, StageCast Creator and ToonTalk, have children (users unspoiled by conventional programming ideas) as primary users. Acceptance of PBE systems requires more good examples. Researchers are exploring the idea of uniting PBE with the Web.

PBE systems provide more opportunity to apply new AI and machine learning techniques to new software. However, they also incur the risk of making unwanted generalizations.

PBE represents a radical departure from conventional programming, and shows promise, but it will take time to become widespread. It is one of the few technologies with the potential of breaking down the barrier between users and programmers.

On Seeing Robots

Citation: Alan K. Mackworth. On Seeing Robots. Computer Vision: Systems, Theory, and Applications, pp. 1-13, 1993.
Link: CiteSeerX
Status: Incomplete

Summary

The title of the paper allows the author substantial scope to discuss 'robots that see their world' and 'systems that see robots', and also to combine them to talk about 'robots that see robots' and 'robots that see themselves'. Most importantly though, the paper is about how we see robots, and it discusses computational paradigms, assumptions, architectures and tools to design and build robots.

Classical symbol manipulation approach to AI (Good Old Fashioned AI) works on a number of assumptions that are very restrictive for a real world application. For example, if we want to build a robot to play soccer, assumptions like OA (one agent), DW (deterministic world), DSA (discrete sequential action) etc. are clearly violated. Such assumptions lead to a world where perception is quite unnecessary except for finding the initial state of the world. In other words, an agent is allowed to plan its actions by reason alone, thus planning becomes a straight line program without conditions or loops.

Traditional AI approach to robotics does not scale. Cognitive integration, the tight coupling of perception, reasoning and action should dominate the research strategy. The critique of classical approach has given rise to Situated Agent (SA) approaches. In general, a situated agent is a real physical system grounded and embedded in a real world, acting and reacting in real time. Situated agents indulge in action, reasoning as well as perception. Also, consideration of multiple agents in a dynamic world, entails a shift from static perception to situated dynamic perception.

Computer science as empirical inquiry: symbols and search

Citation: Allen Newell, Herbert A Simon. Computer science as empirical inquiry: symbols and search. In Communications of the ACM, Vol 19, No 3, pp 113-126, 1976.
Link: ACM Portal

Summary

The purpose of this paper is to examine the development of basic understanding of computer science by empirical inquiry.

All sciences characterize the nature of their systems through qualitative statements. While such statements or laws are generic in nature, they are of great importance and often set the terms on which a whole science operates.

One of the fundamental contributions of computer science has been to explain what symbols are. Symbols lie at the root of intelligent action, and are a primary topic for computer science.

A physical symbol system consists of a set of symbols, which may be related to each other to form expressions or symbol structures. In addition, a physical symbol system also contains a collection of processes that operate on these expressions to produce other expressions. The notions of designation and interpretation are central to physical symbol systems, along with the requirements of completeness and closure.

The Physical Symbol System Hypothesis: A physical symbol system has the necessary and sufficient means for general intelligent action.

A physical symbol system is an instance of a universal machine. Thus the hypothesis implies that intelligence will be realized by a universal computer. It also asserts that the intelligent machine is a symbol system. The development of symbol systems can be traced through time by examination of formal logic (formal symbol manipulation), Turing machines (automatic formal symbol manipulation), stored programs (interpretations), list processing (designation and dynamic symbol structures).

The authors provide the evidence for the symbol system hypothesis by modeling human symbolic behavior. The symbol system implies that the intelligent behavior of man arises because he has characteristics of a physical symbol system. The search for explanations of man's intelligent behavior in terms of symbols systems has had success over the years. In areas like problem solving, concept attainment and long-term memory, symbol manipulation models are common. While this supports the hypothesis, another evidence is the absence of competing hypotheses in the field of psychology.

The question of how symbol systems provide intelligence behavior leads to the concept of heuristic search.

The Heuristic Search Hypothesis: The solutions to problems are represented as symbol structures. A physical symbol system exercises its intelligence in problem solving by search - that is, by generating and progressively modifying symbol structures until it produces a solution structure.

Since the ability to solve problems is generally taken as an indicator of intelligence, it has been a primary problem for artificial intelligence. During early AI research, study of problem solving was almost synonymous with study of search. When a symbol system that is trying to solve a problem knows enough about what to do, it simply proceeds directly towards its goal; but whenever its knowledge is inadequate, it is faced with large amounts of search to find its way again. The task of intelligence is to avert the threat of exponential explosion of search by extracting and using information about the structure of the problem space.

There are other ways of achieving more information about the problem space: 1) Non local use of information, 2) Semantic Recognition systems and 3) selecting appropriate representation.

Definitions

Designation: An expression designates an object if, given the expression, the system can either affect the object itself or behave in ways dependent on the object.
Interpretation: The system can interpret an expression if the expression designates a process and if, given the expression, the system can carry out the process.

Building Concept Representations from Reusable Components

Citation: Peter Clark, Bruce Porter. Building Concept Representations from Reusable Components. In Proceedings of Fourteenth National Conference on Artificial Intelligence (AAAI), 1997.
Link: CiteSeerX

Summary

The goal of this work is the construction of knowledge-based systems capable of answering a wide range of questions, including questions unanticipated when the knowledge-base was constructed. The fundamental requirement is that the system must be able to dynamically construct new concept representations automatically, and in response to questions posed to it. The approach of this work is to structure a knowledge-base as a set of generalized, representational components, and to develop methods for automatically composing components on demand.

The target domain used for illustration throughout the paper, is bio-remediation. For a system to answer a variety of questions about bio-remediation, it needs a concept representation which states its relationship with other concepts. The concept representation combines properties from numerous abstract concepts. It includes a process of conversion, treatment and digestion. This paper presents a way to construct concept representations by composing their constituents, and to control the process so that only the required portions of concept representation are built.

A standard and intuitive account of automatic concept construction is the use of frame representations with multiple inheritance. The basic representational unit is a frame (or concept), and concepts are organized into a taxonomic hierarchy (lattice). In simplest case, each concept is described by a set of properties, each of which is a pair showing the concept's relationship to other concepts. A concept can be composed from other concepts in two ways: inheritance, and modifying a base concept. This approach achieves composition efficiently, and is intuitive.

There are two major problems that frame-based models fail to address:

• While taxonomic relationships between individual concepts are easy to establish, there appears to be no easy way of composing systems of concepts. We would like to automatically import abstract systems to concepts where they apply, rather than manually enumerating their axioms. This is difficult to do with inheritance. It becomes impossible when same abstract systems can be applied to the same concept in multiple ways.
• Concept interactions are not well-modeled in this method. No adequate methods for composing two concepts by using one to modify a property of the other are available.

The mentioned concerns are addressed in the following two ways:

• Changing the organization of knowledge from one based on individual concepts to one based on systems of interacting concepts. So the system is viewed as a set of mini-theories. These systems of concepts are called components.
• Adding a computational mechanism for composing a concept description from components. This involves applying a repeated cycle of classify and elaborate in a goal-directed way to compute the components' relationships. In this mechanism, classification enables elaboration, and elaboration triggers further classification.

Intuitively, a component encapsulates a coherent system of concepts and their relationships, which can be mapped onto a variety of situations where that pattern is deemed to hold. A component is defined as a triple [P,A,R] where P is a set of participants (denoting the objects involved in the pattern), A is a set of axioms (describing relationships among participants), R is a set of roles with which the participants can be labeled, each role referring to a different participant. A component's interface is the set of role-participant pairs of the component. A component can be instantiated by binding its participants to objects in the target domain. When this happens, the axioms in the component are asserted for those objects. Compound concepts can now be specified as a composition of components. A specification states how the components' interfaces plug together, describing how their roles correspond.

A concept representation is an integration of information from the concept's components, subject to the mapping given in the concept's specification. It is more than a simple union of the components' axioms, as axioms may interact to allow additional information to be inferred about the concept. In general, constructing a compound concept representation in its entirety is intractable. Therefore, by design, this concept construction method is driven by questions posed to the knowledge-base. To answer questions that reference concepts not explicitly in the knowledge-base, the system first creates a scenario, consisting of Skolem individuals denoting parts of the compound concept plus the relationships among them. The system then elaborates the scenario to find the answer to the given question.

The algorithm uses access paths as the language for querying the knowledge base. Given a query expressed as an access path, the composition algorithm applies the Classify-Elaborate cycle (to each Pi(xi-1, xi) in turn) to 'follow the path'. The goal is to compose just the information necessary to answer the query.

Classify: Before search for solutions for the predicate Pi(xi-1, xi), first try to refine the classification of xi-1 from its known class to something more specific, to find its most specific generalization(s). Elaborate: To find solutions for Pi(xi-1, xi), search for axioms that conclude the value(s) of xi, looking in the components in which xi-1 participates. Each of these operations can trigger a recursive call to another Classify-Elaborate cycle.

Definitions

Access Path: An access path is a sequence of binary predicates: P1(C, x1), P2(x1, x2),...,Pn(xn-1,xn) where C is a constant and the xi's are free variables. An access path references the set of values for xn for which there exists at least one value for all other variables in the path.