In this paper a technique that enables the dialogbased construction and refinement of operationalized ontologies is proposed. An agent learns classification knowledge through a dialog with a teacher. In this dialog the agent is forced to provide logical explanations of why it classifies (or fails to classify) an instance to various ontology concepts. The teacher is able to give immediate and very focused feedback through these dialogs. This enables the agent to be taught classification knowledge through the treatment of only a handful of examples. And the teacher's feedback is through conversational point, click, and field-filling interactions. What differentiates this approach is that this work leverages off of, and builds on previous work in which a complete system of concept equations may be solved over a practical subset of relational schemas. The ability to syntactically compute query difference enables the calculation of concept intersections and differences, and the determination of concept subsumption and disjointness. The knowledge repair algorithms outlined in this paper require this capability.
Keywords: Knowledge Acquisition, Query Difference Operator, Explanation, Universal Relation.
Unfortunately real world data does not usually come with class membership data attached. Much real world data simply describes low-level situations or events. To employ similarity-based learning techniques, a large, representative sample of the data must first be manually labeled by an expert. Moreover, if the target concepts are subjective (e.g. GoodRestaurant or BadCreditRisk), then this labeling phase will need to be performed by multiple individuals to suit their own unique purposes.
Though the idea is not new, it still stands that using prior knowledge is helpful in the task of acquiring concrete classification knowledge. Through operationalizing such background knowledge, it is possible to teach an agent how to classify events and situations using just a handful of examples.
This is especially pertinent when we consider that ontologies will capture more and more high-level background knowledge, but will often capture such knowledge in general forms that will need to be mapped down to the actual databases available in practice.
The notion of an ontology in this paper, is that of a lattice of general and domain concepts and their relationships. These concepts may have logical definitions connecting them to the extensional schema in which instances (facts) are represented. Alternatively the ontology may not have operationalized definitions. In the later case the techniques here attempt to aid in the construction of an operationalized ontology. In the former case, these techniques may be employed to refine an existing, operationalized ontology.
Let us start this paper out with a very simple example of an agent trying to build the concept of speeding 1. Assume a simple schema or record, along with a target concept speeding: report(vin, speed, color, type, date) speeding(vin, date)
This schema also comes annotated, informing us that vin (vehicle identification number) and date are the keys, and that vin, color, and type are no-orders, and date and speed are total orders.
Aside from access to this input information, let us assume that the agent is a virtual tableau rosa. There is no knowledge of what speeding is - except for the fact that it is assigned to specific vehicles on specific dates. report(001, 78 mph, white, mazda, 01-01) (1) Agent: This is not speeding. (2) Teacher: Wrong classification. (3) Agent: OK - This is speeding because the speed is 78 mph, color is white, and the type is mazda. (4) Teacher: The color and type are not relevant to why this car was judged to be speeding. (5) Agent: This is speeding because the speed is 78 mph (6) Teacher: Correct. report(002, 74 mph, black, BMW, 01-02) (7) Agent: This is not speeding because the speed is not 78 mph. (8) Teacher: Wrong classification (9) Agent: OK - This is speeding because the speed is less than or equal to 78 mph.
1More complex examples will be discussed below, but this example illustrates the basic approach being proposed here.
Section 2 illustrates the basic approach through showing the workings of the agent over the example dialog above. Section 3 discusses scale up to larger domains. Section 4 discusses the formal under-pining of this work - the Query Difference Operator. Section 5 discusses this work in relation to some prior and ongoing work in knowledge acquisition and ontology learning. Section 6 proposes the further plans for the development and refinement of this system. 2
There is a semi-rigid protocol that is observed between the teacher and the agent. Teacher input is constrained to be in a very simple form. This obviates the need for sophisticated front-end interpretors over the teachers input and feedback. In addition all expressions that the agent produces are in natural language. This is possible because the representations within the agent are forms from which it is relatively easy to generate lucid, non-ambiguous natural language.
Figure 1 shows the conversational flow between the agent and the teacher. There are three distinct phases of the conversation. The first phase is the observation phase and it always occurs. In this phase an example instance and target concept are presented to the agent. The agent calculates whether the example is a member of the target concept and then provides a positive (or negative) minimal explanation of its classification back to the teacher. If the teacher agrees with the classification decision and also finds the explanation adequate, then the process concludes and the agent will await the next trial.
If the teacher disagrees with the classification, then the agent is informed of this with a disagreement indication. This opens the correction phase of the conversation. In this phase the teacher directs the agent to repair its knowledge structures and to then provide a new (correct) classification and explanation based on the repaired knowledge structure. This, when the teacher has been less than consistent in prior training, may AGENT example instance
target concept classification and
explataion wrong classification clarification question(s) classification and explataion refinement classification and explataion general questions
observation phase TEACHER correction phase
(optional) refinement phase (repeat) generate a (set of) clarifying question(s) from the agent. After this phase the agent will be classifying the example properly2 and the refinement phase is entered.
Upon entering the refinement phase, the agent will be properly classifying the example but it may be relying on irrelevant conditions in the example to perform the deduction. The explanation provided from the observation or correction phase starts out the interaction. The teacher may identify conditions in the explanation which are irrelevant or incorrect. The teacher may provide repairs to incorrect conditions or simply let the agent search out an alternative condition. Alternatively the teacher may request that a deeper explanation, with more conditions, be provided. During the refinement phase the agent may also ask general questions about the domain. These true/false questions, if answered by the teacher, enable the agent to further constrain the hypothesis space. At the end of the refinement phase the agent will still be able to account for the example (and past examples) but will, through, interaction with the teacher, have more specific, closer to the truth, knowledge structures. This type of confidence building through dialog takes us a step toward more complete and consistent ontologies[3]. 2.2
The approach here is a mix of version-spaces[
As mentioned in the introduction, the knowledge input to the system is a schema, and a set of target concepts that should be learned. In this case the relation report(vin, speed, color, type, date) plus the concept speeding(vin, date) is provided. In addition we know whether an attributes domain is either a totalorder or a no-order. Finally we have functional dependency knowledge that vin and date, together, functionally determine all the other attributes.
2Unless, in the face of the clarifying questions, the teacher decides to abort the trial.
We associate the target concept ci to be learned with three expressions:Ci?,Ci>, and Ci. As is customary, Ci? indicates the logically most specific possible version of ci, Ci> the most general possible version of the concept, and Ci the current, best guess, as to what ci is.
Note that all of these expressions are in the form that will be defined in section 4. The important point to note here is that these expressions resemble relational algebra (over a universal relation [2]) and are closed under a difference operator. From this it follows that we are able to compute conceptual differences, intersections, and compliments. In addition we are able to compute subsumption, disjointness, and concept equivalence. The operations of the agent, sketched in section 2.4, require these capabilities.
The following tables report the contents of the agent’s knowledge-base after each step in the dialog3. Note that the j-th instance added is tj .
First we consider the knowledge the agent has about C1> and C1? through the dialog. type=P olice 26 vviinn;;ddaattee vviinn;;ddaattee tsyppeee=dP6o5lice vin;date speed<65 vin;date speed<65 vin;date speed<65 vin;date speed<65 = ; = C1> C1? and C1? C1> ;. Section 4 discusses how vin;date type=P olice vin;date speed<65 vin;date type=P olice
C1> C1? 9731103 vvvvvviiiiiinnnnnn;;;;;;ddddddaaaaaatttttteeeeee vviinn;;ddaatteefftt21gg ;;vvvviiiinnnn;;;;ddddaaaatttteeeefffftttt1111;;ggtt22gg 15 vviinn;;ddaatteeft3g vviinn;;ddaatteefftt13;gt2; t4g 17 vviinn;;ddaatteeft3g vviinn;;ddaatteefftt31;gt2g 22 vviinn;;ddaatteeft3; t4g vviinn;;ddaatteefftt31;; tt42gg 24 vviinn;;ddaatteeft4g vviinn;;ddaatteefftt41;gt2g
As we can see, until the agent issues the general questions to the teacher, there is little, other than the actual instances themselves, that constrain the hypothesis space. The equivalence of C1> and C1? is established by verifying that this is achieved. The equivalence of C1? and C1> at step 26 licenses the agent to make the statement at step 27.
Next we show the calculated guess that the agent has about the actual concept C1. We will discuss below how the system arrives at these guesses below. Note that these guesses are always legal. That is C1 C1? and C1> C1.
There is an additional data structure Ri associated with each concept. This structure records the relevance feedback that has been gathered on the concept. This structure consists of a set of relevant attribute sets paired with query expressions. This indicates that the variables within the set are relevant to determining the concept ci when the instance falls under the associated query expression. The following table shows the contents of R1 for the example in the introduction.
Note that this structure is a logical consequence of the operations carried out by the teacher.
The teacher, who guides the sessions, is able to apply operations. The structures Ci, Ci>, Ci?, and Ri are accessed and altered during these operations.
The Classify operation simply tests whether the instance meets the current definition of the concept. If it does then the minimal set of attribute values that make it so are reported. This is the positive explanation for why the instance is a member of the concept. If the instance is not a member of the concept then the minimal set of attribute values, which, if changed, would make it a member of the concept, are reported. This is the negative explanation for why the instance is not a member of the concept. These techniques are described in [6]. Explanation services for general description logic systems are discussed in [5]. The results from this operation are shown in every agent utterance before step 21 in the introductory dialog.
The operation WrongClassification starts the correction phase in which the agent’s conceptual structures are repaired. If the disagreement is with a positive explanation, then the initial repair is to subtract the instance from all three Ci, Ci>, and Ci? structures (e.g. step 16). If the disagreement is with a negative explanation then the initial repair is to add the instance to the three structures (e.g. steps 2 and 8). In either case for the Ci expression the agent immediately adopts a value-oriented view of the instance, expressing the instance as a conjunction of conditions, one for each relevant attribute. The relevance of an attribute is decided by consulting the relevance structure Ri. See heuristic #2 below to see how relevant attributes are decided. This produces an immediate generalized repair to the structure. However this repair will be generalized only enough to apply to the current instance, so re-testing prior instances is not necessary.
Note that contradictions are possible when the teacher has given inconsistent responses. However this is only the case when the agent has issued a set of general questions to the teacher to constrain Ci> and Ci? . When a correction violates the boundaries of the Ci> or Ci? the agent will issue a (set of) clarifying question(s) to re-extend the boundary.
In all the operations of the refinement phase, the structure Ci is altered. If it is generalized then it is necessary to re-test all of the prior negative examples. If it is specialized then all prior positive examples need to be re-tested. By reasoning over the concept and relevance expressions one does not, in practice, need to do this full calculation at each step. Still, logically, the new structure must account for all past examples. In the case of a conflict the operation is disallowed, along with an explanation of why. Refinements that carry Ci outside the boundary determined by Ci> and Ci? generate clarifying questions to the teacher to ask if the boundary may be extended.
The operation Irrelevant identifies when and where an explanation is using an irrelevant condition. In the case of a positive explanation, the condition is removed (e.g. step 4) from Ci. In the case of a negative explanation, Irrelevant, we remove conditions in a way similar to the case for positive explanations, but in this case for terms which are being subtracted within Ci (e.g. step 18).
The operation Wrong identifies a condition that has been generalized improperly (e.g. step 10). This then precipitates an alternative generalization strategy to be applied to the condition. See heuristic #3 below. The operation Change lets the teacher directly alter a constant value within a condition in the knowledge structure (e.g. step 14).
The operation MoreReasons is a call for more specificity around why the instance was (or was not) classified to the concept. In either case this leads to the full (i.e. all conditions) value-oriented version of the instance to be either added to or subtracted from Ci.
After the new version of Ci is confirmed consistent with all the prior examples, the Classify(instance) operation is re-run and the correct classification and its explanation are reported to the teacher. This may in turn result in another round of refinement.
The above operations employ the following heuristics:
Heuristic #1: The values of keys are not relevant to classifying the instances. Though this heuristic could easily be discarded, it seems to hold for many potential domains.
Heuristic #2: A relevant attribute of an instance is an attribute whose query expression in Ri does not preclude the instance. If no relevant attributes may be determined, then all of the non-key attributes are deemed relevant. The intuition here is that the repairs in the correction phase must only apply to the current instance, yet should be generalized, and should exploit prior determinations of relevant attributes. Using this the agent concludes that all the non-key attributes are relevant in step 2, only speed after step 8, and again all nonkey attributes after step 16.
Heuristic #3: For total orders, if more than one value is true (or false) the agent will attempt to generalize the condition over the entire domain of the total order. Currently the agent (arbitrarily) decides to generalize by assuming that the attribute is to the highest element in the set of known values (e.g. step 9). If this fails the agent generalizes by assuming that the attribute is to the lowest element in the set (e.g. step 11). Next the agent attempts to generalize over the range from the lowest to the highest. If all these generalizations fail, then the agent falls back to just known values. 3
In the presence of already known concepts we convert the
concept values to boolean attributes on new instances. The
system will then neglect the attributes that were deemed
relevant to decide the known concept. Of course the teacher may
force a more specific analysis that include the concept
variables. Still this initial treatment helps promote the building
of hierarchical knowledge structures in the agent. Note that
this makes the order of the concepts presented to the agent
very important - where each concept builds on the subsequent
ones. Techniques from concept exploration[
The above system can accommodate an example where the teacher gives incorrect or misleading instruction. The approach is simply to state the conflict to the teacher. The response of the teacher decides how and if the knowledge structure is repaired. 3.3
STATUS_RPT MAINTENANCAEI_RRPPTORTINDVAENTTAOBRYA_SREPT WEATHER_RPT ACTIVITY_RPT BUSY_RUN[FWU]AELY_SLO[W] INFA[,N]TERXYT_RTEHMREE_AW[T]HEATHER STORAGE_EX[]HAUSTED PANZER[_,T]HREAT
EXCESS_[F]UEL BOMB[E,R]_THREAT CONCEPTUAL VALUE NODESEXCESSB_AS[DT]O_MRAAGINETENA[N]CE EMPTYS_[ER]NUSNIWTIAVYE[_SI]NVENTORY
OVER_UTILIZED []
NOTIFY_LOGIS[T]ICS_SGT A B C
X=(AandB)orC X
It may be that this approach in this paper is only possible within knowledge representations of the form described below. Still, even within these systems, interesting and practical ontologies may be operationalized. Work is currently be P laying at city=Austin. The same extension occurs for Movie city=Austin [ Movie city=LA. But in the language Movie city=Austin Movie city=LA is equivalent to Movie city=Austin of query difference. For example Movie;Show city=Austin yields the empty set. (4) Finally Movie city=Austin here you can also express queries like the difference operator. In Relational Algebra this again requires that queries have equivalent projection sets. Not so here, the operator expresses this extended notion there is a special negation semantics of such queries where the query Movie city<>0Austin0 is not equivalent to the query people :(city=0Austin0). The former query gives the Movies which play somewhere other than Austin. The later query expresses the query giving the movies that do not play anywhere in Austin. This later query is expressing a form of universal quantification through a not-exists constraint. in queries here are sub-relations of the universal relation R.
In the Relation Algebra projections are over sets of attributes – this requirement could easily be relaxed, but it helps simplify some applications. (3) We extend the notion of difference and union over what in the standard relational algebra are non-union compatible projection sets. The expression q2 indicates this extended form of union. In the standard conducted to employ these methods to teach agents structures such as the one within figure 2. \ Similarly, q1 q2 is “Give show times in Austin for PG-13
In an earlier paper[7] it is shown that the set difference of the queries q1 and q2 may be computed as a syntactic manipulation of the expressions q1 and q2 for a well defined subset of the relational algebra over a restricted class of relational schemas. With this, one may, without materializing data, take the expressions for q1 and q2, apply the query difference formula to yield q3, and be guaranteed that q3 is logically equivalent to q1 q2. With query set difference handled, the ability to compute query intersection, subsumption, disjointness, and equivalence follow.
To illustrate let us take as an example the movie schema in table 1. Consider q1 being the query “Give the show times in Austin for G or PG-13 movies with 4 or 5 star evaluations” and q2 being the query “Give the show times in Austin or San Antonio for PG-13 or R movies with 3 or 4 star evaluations.” The logical result of q1 q2 is the query “Give show times in Austin for G movies with 4 or 5 star evaluations plus show times in Austin for PG-13 movies with 5 star evaluations.” movies with 4 star evaluations.” Clearly neither query subsumes the other, nor are they equivalent.
X X c1^:::^cn where identifies a set of sub-relations from Show city=Austin For example retrieves the show-times for :::; Assume a set of relations fR1; Rmg where we have, a :::; R. The conditions c1; cn are simple, non-join conditions. priori, decided on a set of equi-joins that connect these relations together so that there are no cycles in the resulting graph. In the example in table1 we pick the equi-join between MOVIE and SHOW through the attribute title, the equi-join of SHOW and THEATER through the attribute Theater, and the equi-join of MOVIE and REVIEW through title. When we outer join all the relations together, we get the universal relation R.
A query is represented as an expression of the form those movies playing in Austin. 4.1
:::; is always R, the outer join of all the relations fR1; Rmg
Though these queries have a similar appearance and semantics to simple relational algebra, they differs in several key ways. (1) The “relation” that these queries are applied over . Because this is always the case, ‘R’ is omitted from the notation. And because of this single implied relation argument, self-join queries are precluded. (2) The projection sets
Here follows the central theorem that we may use under the assumptions above. The query difference formula says that for the simple queries of the type proposed, one may solve for query difference by manipulating query expressions directly. Theorem 1 (Query Difference Formula)
Let us consider some examples of this operator in use: First consider, Theorem 2 (Query Difference is distributive over compound queries) q2)
(q3 (q1 q3) q4) ((q2 q3) q4) , = and equivalence follows from q1 q2 q2 q1 = q2 ;. Queries are disjoint if their intersection , = ; Note that subsumption follows from q1 q2 q2 q1 ; ^ q1 is empty.
The following three theorems assist in the simplification of query expressions. In many applications queries will be conveyed to users. No matter the method (e.g. Natural language, graphical display, etc.), we should like to minimized the number of terms in the expression. These three theorems give a complete method by which to search for simpler, but equivalent, query expressions.
Theorem 4 (Horizontal Merge) 5
The work here follows in the same spirit as
propose-andrevise systems such as SALT system[
This work shares some goals with[
A prototype of this system exists, however this prototype needs to be further developed. The current system is able to account for dialogs such as the one described in the introduction. Still there are some further heuristics that need to be added to reduce instance order sensitivity and to properly trigger the agent to ask general questions of the teacher. But work continues and progress is being made. I look forward to receiving feedback from the community to focus and guide the scale-up of this prototype.
In addition I will be investigating how these techniques may applied over widely used ontology representations (OIL, F-Logic, OKBC, etc.). Once a suitable match is found this prototype will be ported to that representation language and larger scale experiments with ontology operationalization will be undertaken. 8
In this paper proposed an approach towards the complete acquisition of conceptual knowledge from a teacher. At its heart the approach relies on the query difference operator to solve concept equations.