Interactive ontology debugging incorporates a user who answers queries about entailments of their intended ontology. In order to minimize the amount of user interaction in a debugging session, a user must choose an appropriate query selection strategy. However, the choice of an unsuitable strategy may result in tremendous overhead in terms of time and cost. We present a learning method for query selection which unites the advantages of existing approaches while overcoming their flaws. Our tests show the utility of our approach when applied to a large set of real-world ontologies, its scalability and adequate reaction time allowing for continuous interactivity.
be seen as constraints Ot must satisfy and are therefore used to gradually reduce the search space for valid diagnoses. Simply put, the overall procedure consists of (1) computing a predefined fixed number of diagnoses (the set of leading diagnoses D, usually jDj 10) as an approximation of all diagnoses, (2) gathering additional information by querying the user, i.e. adding a positive or negative test case, (3) incorporating this information to cut irrelevant areas off the search space, i.e. eliminating diagnoses not complying with the newly specified test case. This loop is continued until the search space is reduced to a single (target) diagnosis Dt. The goal is to achieve this with a minimal number of queries to the user.
The best currently known interactive debugging systems pursue active learning
strategies for query generation exploiting meta information in terms of fault
probabilities of the user who formulates the ontology. Such a system is described in [
As an alternative, one might prefer to rely on an approach with constant
performance which pursues a no-risk strategy without taking into account any meta
information. One such strategy is split-in-half (SPL) [
Therefore, we introduce a method with high potential and low risk, which can be seen as a hybrid risk optimization method (RIO) exploiting positive aspects of both ENT and SPL. On the one hand, our method takes advantage of the given probabilities as long as good performance is achieved. On the other hand, it gradually gets more independent of meta information if suboptimal behavior is measured. This is accomplished by constantly adapting a reinforcement learning parameter c 2 [0; 0:5], which can be seen as the minimal postulated "cautiousness" of the next selected query. The cautiousness of a query is equivalent to its worst case elimination rate w.r.t. the set of leading diagnoses D. E.g., if jDj = 10 and a query Q1 eliminates 1 (9) leading diagnoses for positive (negative) answer, the cautiousness of Q1 is 110 , whereas a query Q2 with 5 (5) has an elimination rate of 150 . W.r.t., e.g. c = 0:3, Q1 would be a high-risk-query since it eliminates less than 0:3 100% of leading diagnoses in the worst case. Thus, it would be dismissed by RIO as a candidate for the next query. By contrast, Q2 is a non-highrisk-query as it eliminates more diagnoses than claimed by c anyway. Actually, Q2 is even a no-risk-query because it eliminates 50% of diagnoses in D in any case. Given a query Q3 with 7 (3), we call Q3 more cautious than Q1 and less cautious than Q2.
More concretely, RIO works as follows: Select the same query QENT as ENT would
select, if the cautiousness of QENT is greater or equal c. Otherwise, select the query with
best entropy-measure among all (if more than one) least cautious non-high-risk-queries.
In the (rare) situation that no such query exists, select QENT. E.g., let current c = 0:3
and QENT = Q1, then RIO would select Q3 since it has cautiousness 0:3 = c and is
thus the only least cautious non-high-risk-query. After each answered query, the new
information is taken into account by updating the diagnosis probabilities according to
the Bayesian rule [
The following evaluation will demonstrate that, independently of the quality of specified meta information, RIO exhibits superior average performance compared to ENT and SPL w.r.t. the amount of user interaction required. Furthermore, experiments will show that RIO scales well and that the reaction time measured is well suited for an interactive debugging approach. %
EXP-1 EXP-2 EXP-3 EXP-4 qSPL < qENT 11% 37% 0% 29% qENT < qSPL 81% 56% 100% 71% qSPL = qENT 7% 7% 0% 0% qRIO < min 4% 26% 29% 71% qRIO min 74% 74% 100% 100% d a e h r e v o (a) (b) Fig. 1. (a) Percentage rates indicating which strategy performed better w.r.t. number of queries. qstr denotes the number of queries needed by strategy str and min is an abbreviation for min(qSPL; qENT). (b) Box-Whisker Plots presenting the distribution of overhead (qw qb)=qb 100 (in %) per debugging session of the worse strategy qw := max(qSPL; qENT) compared to the better strategy qb := min(qSPL; qENT).
EXP-1 EXP-2 EXP-3 EXP-4 45,00 40,00 35,00 30,00 q 2205,,0000 15,00 10,00 5,00 0,00 12,00 10,00 8,00 q 6,00 4,00 2,00 0,00
HMatch
Falcon-AO OWL-Ctxmatch COMA++
(a) (b) Fig. 2. The bars show the avg. number of queries (q) needed by RIO, grouped by matching tools. The distance from the bar to the lower (upper) end of the whisker indicates the avg. difference between q and the queries needed by the per-session better (worse) strategy qb (qw). Notation as in Figure 1.
Evaluation:
We performed four experiments EXP-i(i = 1; : : : ; 4) where we applied RIO to a set of
incoherent ontologies produced by automatic ontology matchers.2 As data source for
EXP-1 and EXP-2 we used a superset of the dataset3 used in [
Available reference alignments enabled to fix a target diagnosis Dt for each incoherent ontology. Throughout all experiments, unlike state-of-the-art alignment debuggers, we considered the most general problem where the search for the target diagnosis is not restricted to the alignment. In each test run we measured the number of required queries until Dt was identified. All tests were executed on a Core-i7 (3930K) 3.2Ghz, 32GB RAM and with Ubuntu Server 11.04 and Java 6 installed. In EXP-1/EXP-3 fault probabilities were chosen reasonably (good case), whereas in EXP-2/EXP-4, they were specified in a way Dt got very improbable (bad case). Queries were answered by an automatic oracle by means of the target ontology obtained through Dt.
Results of hEXP-1,EXP-2i and hEXP-3,EXP-4i, are summarized in Figure 2(a) and Figure 2(b), respectively. The results illustrate clearly that avg. performance achieved by RIO was always substantially closer to the better than to the worse strategy. In both EXP-1 and EXP-2, throughout 74% of 27 debugging sessions, RIO worked as efficiently as the best strategy (Figure 1(a)). In more than 25% of the cases in EXP-2, RIO even outperformed both other strategies; in these cases, RIO could save more than 20% of user interaction on average compared to the best other strategy. In one scenario in EXP-1, it took ENT 31 and SPL 13 queries to finish, whereas RIO required only 6 queries (improvement of > 80% and 53%, respectively). In hEXP-3,EXP-4i, the savings achieved by RIO were even more substantial (superior behavior to both other strategies in 29% and 71% of cases, respectively). Not less remarkable, in 100% of the tests in EXP-3 and EXP-4, RIO was at least as efficient as the best other strategy. Concerning average number of queries per strategy, RIO is the best choice in all experiments. Consequently, RIO is suitable for both good meta information (EXP-1/EXP-3) and poor meta information (EXP-2/EXP-4). Moreover, assuming a user being capable of reading and answering a query in, e.g., half a minute on average, RIO shows best perfromance w.r.t. overall debugging time with savings of up to 50% compared to ENT/SPL. Reaction time of RIO, i.e. avg. time between two successive queries, was always < 12:9s. For SPL and ENT strategies, the difference w.r.t. the number of queries per test run between the better and the worse strategy was absolutely significant, with a maximum of 2300% in EXP-4 and averages of 190% to 1145% throughout all four experiments (Figure 1(b)). Moreover, results show that the different quality of probabilities in {EXP-1,EXP-3} versus {EXP-2,EXP-4} clearly affected performance of ENT and SPL strategies (Figure 1(a)). This perfectly motivates the application of RIO.