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.

The Drinking Philosophers Problem

Citation: K M Chandy, J Misra. The Drinking Philosophers Problem. In ACM Transactions on Programming Languages and Systems, pp 632-646, v 6, No 4, October 1984.
Link: ACM Portal

Summary

The problem of resolving conflicts between processes in distributed systems is of practical importance. A conflict can be resolved only if there is some property by which one process in the set of conflicting processes can be distinguished and selected for favorable treatment. In order to guarantee fairness, the distinguishing property must be such that the process selected for favorable treatment is not always the same.

Two paradigms are presented to make the problem concrete: the well-known distributed dining philosophers problem and a generalization of it, the distributed drinking philosophers problem, which captures the essence of conflict resolution problems in distributed systems.

In order to come up with deterministic conflict resolution strategy, we must ensure that these two properties hold; (1) distinguishability and (2) fairness. A distributed system is represented by an undirected graph G with a one-to-one correspondence between vertices of G and the processes in the system. An edge between two vertices means that a conflict between those two vertices can happen. Precedences between pairs of potentially conflicting processes are represented by a directed precedence graph H. H is identical to G except that each edge in H has a direction such that the edge is directed away from the process with greater precedence toward the one with lower precedence.

Starting with an acyclic H, our requirements are that (1) H remains acyclic at all times, (2) H changes in such a way that every conflicting process eventually rises to top in H, and (3) each change to H is done locally at a process. In order to achieve these requirements, we use the following rules:

• Acyclicity: All edges incident on a process may be atomically redirected toward p. (This transformation preserves acyclicity).
  
• Fairness: Within finite time after a conflict is resolved in favor of a process, that process must yield precedence to all its neighbors.
  

The Drinking Philosophers Problem: Processes, called philosophers, are placed at the vertices of a finite undirected graph G with one philosopher at each vertex. A philosopher is in one of 3 states: (1) tranquil, (2) thirsty, or (3) drinking. Associated with each edge in G is a bottle, or a resource. A philosopher can drink only from bottles associated with his incident edges. A tranquil philosopher may become thirsty. A thirsty philosopher needs a non-empty set of bottles that he wishes to drink from. He may need different sets of bottles for different drinking sessions. On holding all needed bottles, a thirsty philosopher starts drinking; a thirsty
philosopher remains thirsty until he gets all bottles he needs to drink. On entering the drinking state a philosopher stays in that state for a finite period, after which he becomes tranquil. A philosopher may be in tranquil state for an arbitrary period of time.

Two philosophers are neighbors if and only if there is an edge between them in G. Neighbors may send messages to one another. Messages are delivered in arbitrary but finite time. Resources, such as bottles, are also encoded and transmitted as messages. The problem is to devise a nonprobabilistic solution that (1) fairly treats all philosophers, (2) is symmetric between all philosophers, (3) is economical in terms of messages sent/received between state transitions for a philosopher, (4) allows concurrent drinking by different philosophers from different bottles, and (5) keeps the number of messages in transit at any time and the size of messages bounded.

The Dining Philosophers Problem: It is a special case of the drinkers problem in which every thirsty philosopher needs bottles associated with all its incident edges for all drinking sessions. A solution with all the properties mentioned above is presented. However, in order to distinguish between the two problems, the following terms have been used for the diners problem, with the corresponding term for the drinkers problem in parenthesis: thinking (tranquil), hungry (thirsty), eating (drinking), fork (bottle).

Time, Clocks, and the Ordering of Events in a Distributed System

Citation: Leslie Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. In Communications of the ACM, v 21, No 7, July 1978.
Link: ACM Portal

Summary

The concept of an event happening before another event in a distributed system is examined and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events.

In a distributed system, it is sometimes impossible to say that one of two events occurred first. The relation 'happened before' is therefore only a partial ordering of the events in the system.

What is 'happened before'? Assume that our system is composed of a collection of processes. Each process consists of a sequence of events that are totally defined. We also assume that sending or receiving a message is an event in a process. We can then define the 'happened before' relation (->) as: (1) if a and b are events in the same process, and a comes before b, then a -> b, (2) If a is the sending of a message by one process and b is the receipt of the same message by another process, then a -> b, and (3) If a -> b and b -> c then a -> c.

Logical Clocks: In the simplest case, the clock is just a way of assigning a number to an event, where the number is thought of as the time at which the event occurred. More precisely, we define a clock Ci for each process Pi to be a function which assigns a number Ci(a) to any
event a in that process.

For such a system to be considered correct, the strongest reasonable condition (called Clock condition) is: For any events a, b, if a -> b then C(a) < C(b).

To guarantee that the system of clocks satisfies the Clock condition, we will insure that: (1) Each process Pi increments Ci between any two successive events, and (2) If event a is the sending of a message m by process Pi, then the message m contains a timestamp Tm = Ci(a). Upon receiving a message m, process Pj sets Cj greater than or equal to its present value and greater than Tm.

Definitions

Distributed System: A distributed system consists of a collection of distinct processes which are spatially separated, and which communicate with one another by exchanging messages.

Globally distributed object identification for biological knowledgebases

Citation: Tim Clark, Sean Martin, Ted Liefeld. Globally distributed object identification for biological knowledgebases. Briefings in Bioinformatics 2004 5(1):59-70; doi:10.1093/bib/5.1.59
Link: Oxford Journals

Summary

The Web provides a globally distributed communication framework this is essential for almost all scientific collarboration, including bioinformatics. However, several limits and inadequacies have become apparent, one of which is the inability to programmatically identify locally named objects that may be widely distributed over the network. This shortcoming limits our ability to integrate multiple knowledgebases, each of which gives partial information of a shared domain, as is commonly seen in bioinformatics. Fundamentally, we must be able to solve the following problems to fully integrate web-distributed databases: (a) define the link interfaces formally so that they may be understood programmatically; (b) encapsulate the link interfaces so that they are not addresses, but names; (c) locally specify and control object identifiers while guaranteeing them to be globally unique; (d) describe the object attributes using a formal ontology.

Life Science Identifiers (LSIDs) and the LSID Resolution System (LSRS) form the most useful system evolved to date for meeting the above mentioned requirements for biological databases. This system is based on existing IETF and W3C technologies, with some judicious extension, while being compatible with Web services and semantic Web.

LSIDs are a special form of Universal Resource Names (URNs). They have their own resolution protocol, and are persistent, global, location-independent object names. LSIDs can be used to persistently name resources such as individual proteins or genes, transcripts, experimental data sets, annotations, ontologies, publications, biological knowledgebases or objects within them. The syntax of an LSID is: <LSID> ::= 'urn:' 'lsid:' <Authority ID> ':' <Authority Namespace ID> ':' . Once assigned, an LSID is permanent and is never reassigned. Also, as unique identifiers, they can specify only one object for all time.

Any organization assigning LSIDs has several responsibilities: (1) It must identify itself with an Authority ID string, which must be globally unique. Typically it is an Internet domain name it owns. (2) It must ensure the uniqueness of the string created from the namespace, object and revision identifications within any given authority's domain.

Resolution of LSIDs works as follows: (1) A client has an LSID and knows the appropriate resolution service, or contacts the LSID Resolution Discovery Service to find the appropriate resolution service. (2) The client contacts the resolution service to get information on services available on LSID, where they are located, how to call them etc. (3) After getting this information, client calls the desired data retrieval services to submit requests. (4) The service executes the requests and sends the results back to the client.

The current LSID specification allows for accessing the LSID services using simple protocols such as HTTP and FTP. It also utilizes important web services standards like SOAP and WSDL, to allow Web-service like access. The current open source implementations of LSID Resolution Discovery make use of DNS.

Definitions

Ontology: An ontology is the specification of a conceptualization of a knowledge domain. It is a controlled vocabulary that describes objects and the relations between them in a formal way, and has a grammar for using the vocabulary terms to express something meaningful within a specified domain of interest. The vocabulary is used to make queries and assertions.
Gene Ontology: The Gene Ontology, or GO, is a trio of controlled vocabularies that are being developed to aid the description of the molecular functions of gene products, their placement in and as cellular components, and their participation in biological processes. Terms in each of the vocabularies are related to one another within a vocabulary in a polyhierarchical (or directed acyclic graph) manner; terms are mutually exclusive across the three vocabularies.

Ontologies in Biology: Design, Applications and Future Challenges

Citation: Jonathan B L Bard, Seung Y Rhee. Ontologies in Biology: Design, Applications and Future Challenges. In Nature Reviews: Genetics, 2004.
Link: Nature Reviews
Status: Incomplete

Summary

Until recently, the most important task of bioinformatics was thought to be the storage, retrieval and analysis of molecular data. However, as experimental technologies move from producing relatively simple data to more complex data, we need comparable advances in bioinformatics to manage and relate these data. There is also a great deal of sophisticated biological knowledge, often hierarchical in nature, that needs to be integrated with other data. One way to represent such biological knowledge is by using ontologies. The resulting biological ontologies are formal representations of areas of knowledge in which the essential terms are combined with structuring rules that describe the relationship between the terms. Knowledge that is structured within a biological ontology can then be linked to the molecular databases.

For any ontology to be of public value, it has to be widely disseminated and accepted by the field that it aims to summarize. Sociological factors are important in ontology production and acceptance, and a strong community involvement is also crucial.

Definitions

Phenotype: The observable traits or characteristics of an organism, for example hair color, weight, or the presence or absence of a disease. Phenotypic traits are not necessarily genetic.
Systematics: This is an umbrella term to describe the processes that describe species. There are three disciplines which are united under this broad locution: description of species (identification), the naming of names (taxonomy) and description of the relationships among and between taxa (phylogenetics).

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.

QIS: A Framework for Biomedical Database Federation

Citation: Luis Marenco, Tzuu-Yi Wang, Gordon Shepherd, Perry L Miller, Prakash Nadkarni. QIS: A Framework for Biomedical Database Federation. In Journal of the American Medical Informatics Association, Vol 11 No 6, pp 523-534, Nov/Dec 2004.
Link: NCBI PubMed

Summary

Query Integrator System (QIS) is a database mediator framework intended to address robust data integration from continuously changing heterogeneous data sources in the biosciences. This paper outlines barriers to interoperability of bioscience databases, summarizes previous interoperation approaches, and describes QIS.

The QIS architecture is based on a set of distributed network-based servers, data source servers, integration servers, and ontology servers, that exchange metadata as well as mappings of both metadata and data elements to elements in an ontology. Metadata version difference determination coupled with decomposition of stored queries is used as the basis for partial query recovery when the schema of data sources alters.

Bioscience schemas evolve significantly and rapidly because of scientific progress, changing research goals and discovery of better data representation techniques. Due to this nature, federation of bioscience databases faces these major barriers:

• Databases do not usually support unstructured SQL for performance and safety reasons. Therefore, predefined parametrized queries are generally used. Any alterations to the database can cause these queries to break.
• Interoperation between databases becomes difficult in the presence of synonymy and polysemy. Such issues require presence of a controlled vocabulary, and that data and metadata must be mapped to concepts in the controlled vocabulary.
• Federated search mechanisms must appropriately exclude data that are still preliminary and not available for public access beyond the research group creating an individual database.

Major existing approaches to database federation are the following. The global schema approach is based on an agreed-upon and infrequently revised standard definition of domain-specific data types and classes and their interrelationships. Anyone using this standard must not deviate from it. Therefore, its applicability in rapidly evolving areas seems doubtful. In contrast, mediator systems allow a single query to be translated into the language recognized by heterogeneous databases, extracting their information and integrating the results in a single dataset. Managing such systems becomes enormously complex in the presence of autonomous and frequently changing heterogeneous databases. In bioscience domain, we would like to address data mediation and schema adaptation together in order to achieve robust evolvable data integration.

The objectives underlying the creation of QIS are: (1) to integrate data sources, (2) to devise a scalable approach to schema evolution in a loosely coupled database federation, (3) to devise robust mechanisms for metadata exchange, (4) to address the problem of breaking-up of federated queries by automatic detection of schema evolution, (5) to support interoperation with a separation between public and private data, (6) to facilitate recording of system semantics, and (7) to devise an open-source, low-cost, lightweight system to facilitate research work.

QIS uses a distributed architecture that is composed of three main functional units: integrator servers (ISs), data source servers (DSSs), and the ontology server (OS). These units form the system's middle tier, connecting data consumers with data providers and knowledge sources.

Definitions

Synonymy: It is the semantic relation that holds between two words that can, in a given context, express the same meaning.
Polysemy: It is defined as the ambiguity of an individual word or phrase that can be used, in different contexts, to express two or more different meanings.

From XML to RDF: how semantic web technologies will change the design of 'omic' standards

Citation: Xiaoshu Wang, Robert Gorlitsky, Jonas S Almeida. From XML to RDF: how semantic web technologies will change the design of 'omic' standards. In Nature Technology, Vol 23, No 9, pp 1099-1103, Sep 2005.
Link: NCBI PubMed

Summary

Developing a data standard addresses two major concerns: (1) the content - what should be standardized, and (2) methodology - how the standard should be formatted. A data standard is more than just a medium to uniform data representation. By laying out the overall structure of relationships of the encoded data, a data standard will effectively define a schema for a particular area of domain knowledge. The purpose of this article is to discuss how the above issues affect the choice of methodologies to establish data standards. More specifically, it discusses why there is a need to go beyond XML as a standard technology to represent biological data.

Examples of XML documents show that compatibility cannot be achieved by XML alone because the language can be used in more than one way to encode the same information. Although, different parties can agree on a single XML format, but in most scientific disciplines data relationships are bound to change with the development of new experimental methods. In case of such change, the standard must adjust to reflect the newly established relationship. Unfortunately, this is very difficult to achieve using XML.

The problems with XML-based standards are:

• XML restrics what type of data can and cannot be in what places. Although it allows XML-encoded message to be validated easily, it makes it harder to extend the vocabulary of the system beyond the original specifications. Techniques for allowing extensibility exist in XML, but they make schema design harder to manage.
• Since no rules can be specified to manage the extension of system, separately developed applications are very likely to develop different dialects of extension. Also, since XML-based applications rely on the correct document structure to operate properly, any change in structure may potentially break the application.
• Newly extended features can be grouped into a new namespace, but they are unlikely to be structurally cohesive with existing structure. This brings the issues of schema integration along with it.

The problems with XML originate from the limited expressiveness of the XML language. XML, designed as a language for message encoding, is only self-descriptive about the following structural relationships: containment, adjacency, co-occurrence, attribute and opaque reference. These relationships are useful for serialization, but are not optimal for objects of a problem domain.

Meaningful data exchange involves communication both at message level (data encoded in a standard format to applications can know how to convert bytes into objects), and at algorithmic level (relationships between objects specified explicitly to enable applications to process data accordingly). XML is designed to standardize message level communication. What appears to be missing is the description of semantic relationships between nested content holders that are required to invoke appropriate algorithms.

What is needed for solving this interoperability issue is a knowledge representation technology that can explicitly describe the data semantics. The foundation Semantic Web technology is RDF. The semantics of an RDF model are obtained via reference to RDFS and OWL. RDFS and OWL are layered on top of RDF to offer support for inference and axioms.

Comparing RDF to XML reveals three important differences:

• Unlike the namespaces in XML, which ultimately are unique character strings for grouping related concepts, the ontology URI in RDF must be retrievable.
• The description of semantic relationship is explicit in RDF.
• The unique identifier attribute used in XML is no longer needed. Since RDF uses URIs, the uniqueness is ensured globally instead of just within the document.

Three distinct features of RDF make it very helpful to omic sciences:

1. The data structure for RDF is a directed labeled graph (DLG). Adding nodes and edges does not change the structure of any existing subgraph, so RDF does not suffer from the unpredictable extension-induced changes problem.
2. RDF has an open world assumption in that is 'allows anyone to make statements about any resource'. It is monotonic in that new statements do not negate the validity to previous assertions, making it particularly suitable in an academic environment, where consensus and disagreement have a useful coexistence that needs to be formally recorded.
3. All RDF terms share a global naming scheme in URI, making distributed data and ontologies possible.

Just like any other emerging technology, RDF is not without issues.

• One particular problem is the vagueness of 'resource' definition. When using URLs, instead of URIs, to represent resources of multiple dimensionalities an identity crisis occurs. In practice, the problem can be conveniently avoided by using LSIDs which couple a naming scheme with data-retrieving framework.
• Bristling alternative ontologies may emerge at the initial stage of ontological development for a particular domain. But as field matures, it is expected that ontology usage will converge to the most comprehensive subset. The use of URIs helps in this regard. By assigning each concept a globally unique URI, RDF becomes immune to dialects that vexed XML. Whether an ontology becomes a standard or not, is usually determined by its usefulness for a community.

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.