Towards an Integrated Discovery System

I Introduction

In recent years, AI researchers have developed a number of systems that operate in the domain of scientific discov­ ery. For instance, BACON [4) discovers numerical laws (e.g., the ideal gas law) and postulates intrinsic proper­ ties of object classes (e.g., atomic weight). ABACUS [2) is similar to BACON, but employs an improved search mech­ anism to find numeric laws in a more efficient manner. It also improves upon BACON by identifying qualitative pre­ conditions on quantitative laws. GLAUBER [6) addresses a different aspect of empirical discovery - the formation of qualitative laws and object taxonomies.

Although each of these systems is successful at its task, each addresses only part of the overall problem of empir­ ical discovery [5). We are developing an integrated dis­ covery system (IDS) that deals with a variety of empiri­ cal discovery tasks, including the formation of qualitative and numeric laws. Historically, qualitative discoveries have tended to lay the foundation for quantitative discoveries, but the latter can in turn lead to higher level qualitative discoveries. Our system operates in the same basic man­ ner, first finding qualitative laws and then using them to aid in discovering quantitative relations.

IDS operates in a simulated world of simple physics and chemistry, thus overcoming one deficiency of previous discovery systems. Previous systems were provided with data* and could not perform their own experiments. In contrast, IDS interacts with the simulated world through a set of ef­ fector& and &en&or&. Using an effector, the system can ac­ tively alter certain attributes of an object, e.g., by changing its location or heating it. Sensors let the program inspect certain attributes, such as the temperature and mass of an object. To carry out an experiment, the system applies effectors to a set of objects and uses its sensors to observe the manner in which those objects change over time.

In the following section, we introduce the representation that IDS employs to state qualitative laws. After this, we examine the mechanisms by which the system discovers qualitative laws and then consider how it uses the resulting schemas to aid itS-diScovery of numeric laws. We close with / some proposals for extending the system.

II Representing Qualitative Schemas

Before one can discover qualitative knowledge about the world, one must first have some way to represent that knowledge. Let us consider an example from the domain of heat phenomena. We might begin with a simple view of what happens when we heat an object, e.g., we expect the temperature of the object to increase. If we actually heat a solid, we will see that this occurs, but after some time we may also observe the appearance of a new liquid object. At this point the temperature increase stops and the mass of the liquid increases while the mass of the solid decreases. When the solid has disappeared, the tempera­ ture of the liquid begins to increase. This process continues until a new gaseous object appears. As before the mass of the gas increases while the mass of the liquid decreases, the temperature of both objects remains constant during this period. Finally, the liquid vanishes and the temperature of the gas increases, but so does its pressure.

IDS represents qualitative knowledge of this type in qual­ itative &chema&. Our representation has been influenced by Forbus' [3) qualitative proceu (QP) theory, with qualita­ tive schemas corresponding to envisionments in QP theory.

----r:eDat's AM (7] is an exception, since it collected ib own data and designs its own experiments. But the mathematical domain of AM allowed methods not easily extendable to "real world" domains.

The schemas can be viewed as finite state diagrams that de- · scribe the behavior of objects over time. States correspond to intervals of time during which objects exhibit some con­ stant behavior. Links specify connections between states, along with the conditions that must be satisfied to enter a successor state.

IDS represents each state as a frame with three slots. The de·cription slot includes one or more classifications of the objects present in the state (e.g., ·olid or acid). This slot also includes structural descriptions (e.g, heater h touches object a, container a is connected to container b). The quantity-condition· slot contains statements about attributes of the objects in the state. These statements are expressed as equalities or inequalities between the quanti­ ties of attributes and limit-point· (see below). The proceu ·lot is a list of zero or more change· that are occurring dur­ ing the state. Like Forbus, we. express a change in terms of the derivative of the changing attribute. For example, an increase in mass of object a is denoted Amass( a) > 0.

A state ends only if the process reaches a limit-point, such as the melting-point, or if the agent intervenes, e.g., by turning off the heat. Limit-points are important be­ cause they are used in the quantity-conditions, and also because they form the basis for quantitative discoveries. Figure 1 presents a graphical illustration of a heat schema with the object description, the quantity-conditions, and the process for each state.

Although qualitative schemas are structurally similar to the envisionments of De Kleer [1] and Forbus, there is a major difference. Envisionments are deduced from struc­ tural or process descriptions, while qualitative schemas are induced from observations. In the following section we de­ scribe this discovery process.

III Inducing Qualitative Schemas

IDS begins with a simple qualitative schema for each of its effectors. For example, the initial schema of the heat effector consists of two states: sO, with one object and no active process, and sl, with an object touched by a heater and with the temperature of the object increasing. This represents IDS' initial knowledge of the results of applying the heat effector to an object.

The system carries out experiments to improve its schemas, which can be refined in several ways. First, if IDS encounters unfamiliar behavior, it adds a new state to the schema along with a link connecting it to the existing states. Second, the system may discover that an existing state can follow another known state; in this case it simply adds a new link connecting the states. Furthermore, any time new limit-points are found, the system adds quantity­ conditions to the states.

Consider again the heat example and the initial heat schema. IDS experiments by applying the heat effector to a block of ice. At first, the temperature of the ice increases, satisfying all conditions of state &1. Eventually, a new ob­ ject (liquid water) appears; after this point the mass of this new object increases, while the mass of the ice decreases. IDS' heat schema does not yet contain a state for this be­ havior, so the system creates a new state ( s.t) and adds it to the schema. This state has a heater and two objects, b and c. The process slot describes the qualitative behavior of the system - that the mass of object b decreases and the mass of object c increases. Since a new limit-point has been found, quantity-conditions are added to states sl and s.t. These conditions specify that the temperature of the object in state sl is less than some limit-point Ct and that the temperatures of the objects in state s.t are equal to Ct.

After the ice disappears, state sl again accurately de­ scribes the current behavior. When the temperature of the liquid reaches the limit-point C1 , state s.t adequately de­ scribes the current behavior, so the system does not change the schema at this point. When the liquid disappears, IDS encounters unseen behavior; not only does the temperature of the object increase, but so does its pressure. Thus the system creates a new state ( ·3) and adds it to the schema. After further experimentation using different objects, IDS discovers that the object in s3 is always a gas, while the object in sl is either a solid or a liquid. The object de­ scription for s! is found in a similar way. This information is added, giving the final schema shown in Figure 1.

One can think of this schema-building process as a data­ driven search through the space of possible schemas. In these terms, adding states and links make schemas more general, while augmenting the state description and adding quantity-conditions makes them more specific.

IV Discovering Quantitative Laws

Once IDS has formulated a qualitative schema, it uses that knowledge to constrain the search for numeric laws. ··

-.-.yn addition schemas provide a context for numeric laws. They describe not oniy the applicability of laws but also specify their pre- Returning to our heat example, the system would use the schema in Figure 1 to run different experiments. The schema was discovered using a block of ice, so one experi­ ment would examine the effect of varying the initial mass of the ice. Other experiments would vary the class of ob­ ject used; for instance, IDS might see if the schema still holds when the heated object is hydrogen chloride or some other acid.

Most of the data used in discovering numeric laws are not directly observable, but are gathered in the form of limit­ points and state durations. This information is recorded as attribute-value pairs during the matching of a schema to an experimental run. Thus, the system records the values of the limit-point 01 for different objects and uses these attribute-value pairs as data in its search for numeric laws. Like BACON, the system formulates a quantitative law upon finding some numeric term with a constant value.

IDS discovers two basically different forms of numeric laws. First it finds numeric terms that are constant for all objects of a given class. Langley et al. [4] have called such terms intrin1ic propertie1. For example, the system notices that all instances of the class of ice have the same value for the limit-point 0 1· Thus it stores an intrinsic value for the property 0 1 and associates this value with the ice class. In fact, this value corresponds to the melting point of water. IDS also discovers that the zero mass is a critical value for all objects, since this is the point when object appear and disappear. This can be viewed as an intrinsic value associated with all objects.

IDS also discovers numeric laws that relate the attributes of different objects within the same instance of a schema. For example, the system notices that the masses of the solid, the liquid, and the gas within the same instance of the heat schema are always equal. Based on this regularity, it postulates a conservation law stating that the mass of an object remains constant as it goes through a phase change.

V Concluding Remarks

In this paper we have described IDS, a system that in­ tegrates the process of qualitative and quantitative dia­ covery. We have focused on a single example - involving heat phenomena - to illustrate the acquisition of qualita­ tive schemas and their role in discovering numeric laws. However, the qualitative schema representation and IDS' discovery methods are general enough to cover a wide range of physical and chemical phenomena. For instance, the system has also induced a schema that describes simple chemical reactions and another that describes Black's law of specific heat. We have also used qualitative achemas to represent the fluid-flow of two connected containers filled with liquids [3] and the osmosis of two liquids with differ­ ent concentrations [8], though IDS has not yet generated this knowledge itself.

We are extending the discovery system on several fronts. Our next step is to incorporate a more robust search mechud pc»&-conditiona.

anism, such as those used in BACON and ABACUS, to support the discovery of more complex numeric laws. In addition, we must currently aupply the system with a con­ cept hierarchy, and are actively extending the system to construct taxonomies on its own initiative. In forming these taxonomies, the next version of IDS will use sym­ bolic attributes, numeric attributes, and information de­ rived from qualitative schemas. As the capabilities of IDS grow, so will the need for an improved agenda mechanism [6] that directs not only the discovery process but also the design of experiments. Even though the IDS project is still in an early phase, it has already led to promising results that have improved our understanding of the complex pro­ cess of scientific discovery.

Acknowledgments

This work was supported in part by Contract N0001484-K-o345 from the Information Sciences Division, Office of Naval Research.

We would like to thank Randy Jones and Don Rose for their help on this work along with others from the UCI machine learning group . who gave us valuable comments on earlier drafts.