# Evaluating Active Learning Heuristics for Sequential Diagnosis

Patrick Rodler1 Wolfgang Schmid1
1Alpen-Adria Universität Klagenfurt
e-mail<EMAIL_ADDRESS>
###### Abstract

Given a malfunctioning system, sequential diagnosis aims at identifying the
root cause of the failure in terms of abnormally behaving system components.
As initial system observations usually do not suffice to deterministically pin
down just one explanation of the system’s misbehavior, additional system
measurements can help to differentiate between possible explanations. The goal
is to restrict the space of explanations until there is only one (highly
probable) explanation left. To achieve this with a minimal-cost set of
measurements, various (active learning) heuristics for selecting the best next
measurement have been proposed.

We report preliminary results of extensive ongoing experiments with a set of
selection heuristics on real-world diagnosis cases. In particular, we try to
answer questions such as “Is some heuristic always superior to all others?”,
“On which factors does the (relative) performance of the particular heuristics
depend?” or “Under which circumstances should I use which heuristic?”

##  1 Introduction

If the actual behavior of a system does not match its expected behavior, the
task of _fault localization_ is to determine the _actual diagnosis_ , i.e.
those system components whose faultiness is responsible for the system’s
improper functioning. A major challenge regarding real-world systems such as
hardware, software or knowledge bases in this context is the often enormous
number of possible explanations (_diagnoses_) for an observed system failure
to begin with. In the presence of the initial observations, each of these
diagnoses might correspond to the sought actual one. _Sequential diagnosis
(SD)_ approaches [?] address this fault localization problem by suggesting a
sequence of system measurements (e.g. electrical measurements in hardware,
test cases in software, or questions to a domain expert in knowledge-based
systems). The aim of these measurements is to narrow down the space of
diagnoses until only one (highly probable) diagnosis persists. Since the
realization of such measurements often involves resources in terms of
manpower, time or costly equipment, SD methods attempt to minimize the overall
accruing measurement costs. Unfortunately, the global optimization of these
costs (i.e. coming up with the cost-minimal _sequence of measurements_
revealing the actual diagnosis) has been proved to be NP-hard [?; ?]. As a
result, SD methods have to confine themselves to a local optimization (i.e.
computing the best _next_ measurement). To this end, a one-step lookahead
evaluation of measurements (i.e. how favorable is the expected situation after
making _one_ measurement?) proved to be an already very good trade-off between
gained information and necessary effort [?]. Hence, most, if not all, state-
of-the-art SD approaches leverage such one-step-lookahead heuristics.

In this work we focus on one-step lookahead heuristics, called _query
selection measures (QSMs)_ , that try to optimize measurements formulated as
binary true-false tests, called _queries_ [?; ?]. For instance, all of the
following can be viewed as queries: a test of a system such as hardware or
software [?; ?; ?; ?] (given inputs $I$, do we get the expected outputs $O$?),
the inspection of system components [?; ?] (are all tested components
normal?), a question to an expert [?; ?] (is statement $X$ true in domain
$D$?), or a probe [?] (is the value at measurement point $P$ equal to $v$?).

Popular QSMs currently adopted in SD are the _expected information gain_ [?;
?; ?; ?] and the _split-in-half heuristic_ [?; ?]. A range of new QSMs, most
of them originally suggested in the field of active learning [?], have
recently been introduced to SD in our previous work [?]. Complementary to the
analyses in [?] – mostly addressing the efficient computation of optimal
queries wrt. QSMs – we want to bring light to the performance of the QSMs wrt.
measurement cost throughout an SD session in the present work.

For this purpose, we are currently conducting extensive evaluations where we
investigate the particular QSMs under varying conditions regarding

  1. (a)

diagnoses probability distributions,

  2. (b)

quality (meaningfulness) of the probabilities,

  3. (c)

available diagnostic evidence (size of the diagnoses sample) for query
computation, and

  4. (d)

diagnostic structure (i.e. system size; number and cardinality of diagnoses;
reasoning complexity)

using real-world diagnosis problems. The data of the (already finished)
experiments shall be exploited to approach i.a. the following questions:

  * •

Do the factors (a) – (d) have an influence on the (relative) performance of
the QSMs?

  * •

Which QSM is preferable under which circumstances?

  * •

Is there a (clear) winner among the QSMs?

  * •

What about the difference (variance) between QSM performances under different
conditions?

The rest of the paper is organized as follows. Sec. 2 briefly introduces
technical basics wrt. SD. Sec. 3 recaps the QSMs used in the experiments. The
evaluation setting is described in Sec. 4, and results discussed in Sec. 5.
Sec. 6 concludes.

##  2 Preliminaries

In this section we briefly characterize the basic technical concepts used
throughout this work, based on the framework of [?; ?] which is slightly more
general [?] than Reiter’s theory [?].

Diagnosis Problem Instance (DPI). A system to be diagnosed, consisting of a
set of components $\left\\{c_{1},\dots,c_{k}\right\\}$, is described by a
finite set of logical sentences $\mathcal{K}\cup\mathcal{B}$, where
$\mathcal{K}$ (retractable knowledge) characterizes the behavior of the system
components, and $\mathcal{B}$ (correct background knowledge) comprises any
additional available system knowledge and system observations. More precisely,
there is a one-to-one relationship between sentences
$\mathit{ax}_{i}\in\mathcal{K}$ and components $c_{i}$, where
$\mathit{ax}_{i}$ describes the nominal behavior of $c_{i}$. E.g., if $c_{i}$
is an OR-gate in a circuit, then
$\mathit{ax}_{i}:=out(c_{i})=or(in1(c_{i}),in2(c_{i}))$; $\mathcal{B}$ in this
context might subsume sentences stating, e.g., which components are connected
by wires, or observed outputs of the circuit. The inclusion of a sentence
$\mathit{ax}_{i}$ in $\mathcal{K}$ corresponds to the implicit assumption that
$c_{i}$ is healthy. Evidence about the system behavior is captured by sets of
positive ($\mathit{P}$) and negative ($\mathit{N}$) measurements [?; ?; ?].
Each measurement is a logical sentence; positive ones
$\mathit{p}\in\mathit{P}$ must be true and negative ones
$\mathit{n}\in\mathit{N}$ must not be true. We call
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$ a
_diagnosis problem instance (DPI)_.

Diagnoses. Given that the system description along with the positive
measurements (under the assumption $\mathcal{K}$ that all components are
healthy) is inconsistent, i.e.
$\mathcal{K}\cup\mathcal{B}\cup\mathit{P}\models\bot$, or some negative
measurement is entailed, i.e.
$\mathcal{K}\cup\mathcal{B}\cup\mathit{P}\models\mathit{n}$ for some
$\mathit{n}\in\mathit{N}$, some assumption(s) about the healthiness of
components, i.e. some sentences in $\mathcal{K}$, must be retracted. We call
such a set of sentences $\mathcal{D}\subseteq\mathcal{K}$ a _diagnosis_ for
the DPI
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$ iff
$(\mathcal{K}\setminus\mathcal{D})\cup\mathcal{B}\cup\mathit{P}\not\models x$
for all $x\in\mathit{N}\cup\left\\{\bot\right\\}$. We say that $\mathcal{D}$
is a _minimal diagnosis_ for $\mathit{dpi}$ iff there is no diagnosis
$\mathcal{D}^{\prime}\subset\mathcal{D}$ for $\mathit{dpi}$. A sample
$\mathbf{D}$ of minimal diagnoses, the _leading diagnoses_ , is often used as
an input for measurement selection algorithms, serving as a basis for
measurement quality assessment. We call $\mathcal{D}^{*}$ _the actual
diagnosis_ iff all $\mathit{ax}\in\mathcal{D}^{*}$ are faulty and all
$\mathit{ax}\in\mathcal{K}\setminus\mathcal{D}^{*}$ are healthy.

If component fault probabilities are available – formalized as
$p(\mathit{ax}_{i})$ for $\mathit{ax}_{i}\in\mathcal{K}$ and defining how
likely is it that the nominal behavior description $\mathit{ax}_{i}$ of
$c_{i}$ does not apply – probabilities of diagnoses $\mathcal{D}\in\mathbf{D}$
(of being the actual diagnosis) can be computed as

$p(\mathcal{D})=\prod_{\mathit{ax}\in\mathcal{D}}p(\mathit{ax})\prod_{\mathit{ax}\in\mathcal{K}\setminus\mathcal{D}}(1-p(\mathit{ax}))$

and updated by means of Bayes’ Rule (see [?, p. 130]) after a new measurement
is added. Sometimes $p(\mathit{ax})$ for $\mathit{ax}\in\mathcal{K}$ might not
be directly given, e.g., if components have an internal structure in that they
constitute an aggregation of several sub-components $sc_{i}$. In such a case,
$p(\mathit{ax})$ can be computed from fault probabilities $p(sc_{i})$ of sub-
components as [?]:

$p(\mathit{ax})=1-\prod_{sc_{i}\text{ occurs in }\mathit{ax}}(1-p(sc_{i}))$

Queries and Q-Partition. Let $\mathbf{D}$ be a set of leading diagnoses for
$\mathit{dpi}=\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$.
A _query_ (wrt. $\mathbf{D}$) is a logical sentence $q$ that rules out at
least one diagnosis in $\mathbf{D}$, both if $q$ is classified as a positive
measurement ($\mathit{P}\leftarrow\mathit{P}\cup\left\\{q\right\\}$), and if
$q$ is classified as negative measurement
($\mathit{N}\leftarrow\mathit{N}\cup\left\\{q\right\\}$). That is, at least
one $\mathcal{D}_{i}\in\mathbf{D}$ is not a diagnosis for
$\left\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\left\\{q\right\\},\mathit{N}\right\rangle$
and at least one diagnosis $\mathcal{D}_{j}\in\mathbf{D}$ is not a diagnosis
for
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\cup\left\\{q\right\\}\right\rangle$.
The classification of a query $q$ to either $\mathit{P}$ or $\mathit{N}$ is
accomplished by an oracle, e.g. an engineer performing measurements or a
domain expert answering questions. The _oracle_ is a function
$\mathsf{class}:\mathbf{Q}\to\left\\{\mathit{P},\mathit{N}\right\\}$ where
$\mathbf{Q}$ is the relevant query space (a set of logical sentences).

An expedient tool towards the verification and goodness estimation of query
candidates $q$ is the notion of a q-partition. Namely, every logical sentence
$q$ partitions a set of leading diagnoses $\mathbf{D}$ into three subsets:

  * •

${\bf D}_{q}^{+}$: includes all $\mathcal{D}\in\mathbf{D}$ where $\mathcal{D}$
is not a diagnosis for
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\cup\left\\{q\right\\}\right\rangle$
(diagnoses predicting that $q$ is a positive measurement)

  * •

${\bf D}_{q}^{-}$: includes all $\mathcal{D}\in\mathbf{D}$ where $\mathcal{D}$
is not a diagnosis for
$\left\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\left\\{q\right\\},\mathit{N}\right\rangle$
(diagnoses predicting that $q$ is a negative measurement)

  * •

${\bf D}_{q}^{0}=\mathbf{D}\setminus({\bf D}_{q}^{+}\cup{\bf D}_{q}^{-})$:
includes all $\mathcal{D}\in\mathbf{D}$ where $\mathcal{D}$ is a diagnosis for
both
$\left\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\left\\{q\right\\},\mathit{N}\right\rangle$
and
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\cup\left\\{q\right\\}\right\rangle$
(_uncommitted diagnoses_ , no prediction about $q$)

A $3$-partition $\mathfrak{P}$ of $\mathbf{D}$ is called _q-partition (QP)_
iff there is a query $q$ for $\mathbf{D}$ such that
$\mathfrak{P}=\left\langle{\bf D}_{q}^{+},{\bf D}_{q}^{-},{\bf
D}_{q}^{0}\right\rangle$. According to the definition of a query, it holds
that $q$ is a query iff both ${\bf D}_{q}^{+}$ and ${\bf D}_{q}^{-}$ are non-
empty sets. This fact can be taken advantage of for _query verification_.

Coupled with diagnoses probabilities, the QP provides useful hints [?] about
_query quality_ in that it enables to

  1. (1)

test whether $q$ is a _strong query_ , i.e. one without uncommitted diagnoses
(${\bf D}_{q}^{0}=\emptyset$),

  2. (2)

estimate the impact $q$’s classification $\mathsf{class}(q)$ has in terms of
diagnoses elimination (potential a-posteriori change of the diagnoses space),
and

  3. (3)

assess the probability of $q$’s positive and negative classification (e.g. to
compute the uncertainty of $q$).

As per [?], given a set of leading diagnoses $\mathbf{D}$, we estimate
$p(\mathsf{class}(q)=\mathit{P})=p({\bf D}_{q}^{+})+\frac{1}{2}p({\bf
D}_{q}^{0})$ and $p(\mathsf{class}(q)=\mathit{N})=p({\bf
D}_{q}^{-})+\frac{1}{2}p({\bf D}_{q}^{0})$ where
$p(\mathbf{D}_{q}^{X})=\sum_{\mathcal{D}\in\mathbf{D}_{q}^{X}}p(\mathcal{D})$
for $X\in\left\\{+,-,0\right\\}$ and $p(\mathcal{D})$ for
$\mathcal{D}\in\mathbf{D}$ is the probability of $\mathcal{D}$ normalized over
$\mathbf{D}$ (i.e. $\sum_{\mathcal{D}\in\mathbf{D}}p(\mathcal{D})=1$).

Sequential Diagnosis. Formally, the (optimal) SD problem can be stated as
follows:

######  Problem 1 ((Optimal) SD).

Given: A DPI
$\left\langle\mathcal{K},\mathcal{B},\mathit{P},\mathit{N}\right\rangle$.
Find: An (optimal-cost) set of measurements
$\mathit{P}^{\prime}\cup\mathit{N}^{\prime}$ such that there is only a single
minimal diagnosis for
$\left\langle\mathcal{K},\mathcal{B},\mathit{P}\cup\mathit{P}^{\prime},\mathit{N}\cup\mathit{N}^{\prime}\right\rangle$.

Query Selection Measures (QSMs). The said query properties (1) – (3)
characterized by the QP are essentially what QSMs take into account to
quantitatively rate the query quality. Formally, a QSM is a function
$m:\mathbf{Q}\to\mathbb{R}$ that assigns a value $m(q)$ to each query
$q\in\mathbf{Q}$. All QSMs are heuristics towards Optimal SD (Problem 1). That
is, their goal is to minimize the expected cost
$\sum_{\mathcal{D}}p(\mathcal{D})\mathsf{cost}(\mathcal{D})$ of locating the
actual diagnosis $\mathcal{D}^{*}$. At this, $\mathsf{cost}(\mathcal{D})$ is
usually conceived of as the sum of individual query costs over all queries
required to unambiguously isolate $\mathcal{D}$. For the purpose of this paper
we assume $\mathsf{cost}(\mathcal{D})$ represents the number of queries to
isolate $\mathcal{D}^{*}$ (all queries assumed equally costly).

QSM $m$ | $m(q)$ | opt.
---|---|---
$\mathsf{ENT}$ | $\sum_{c\in\left\\{\mathit{P},\mathit{N}\right\\}}p(\mathsf{class}(q)=c)\log_{2}p(\mathsf{class}(q)=c)$ | $\searrow$
$\mathsf{SPL}$ | $\left|\,|{\bf D}_{q}^{+}|-|{\bf D}_{q}^{-}|\,\right|$ | $\searrow$
$\mathsf{KL}$ | $-\sum_{X\in\left\\{{\bf D}_{q}^{+},{\bf D}_{q}^{-}\right\\}}\frac{|X|}{|{\bf D}_{q}^{+}\cup{\bf D}_{q}^{-}|}\log_{2}\frac{p(X)}{p({\bf D}_{q}^{+}\cup{\bf D}_{q}^{-})}$ | $\nearrow$
$\mathsf{EMCb}$ | $p(\mathsf{class}(q)=\mathit{P})|{\bf D}_{q}^{-}|+p(\mathsf{class}(q)=\mathit{N})|{\bf D}_{q}^{+}|$ | $\nearrow$
$\mathsf{MPS}$ |  $p(\mathbf{D}_{q,\min})$ if $|\mathbf{D}_{q,\min}|=1$,$\quad 0$ else ${}_{\textbf{1)}}$ | $\nearrow$
$\mathsf{BME}$ |  $|\mathbf{D}_{q,p,\min}|$ ${}_{\textbf{2)}}$ | $\nearrow$
$\mathsf{RIO}^{\prime}$ |  $\frac{\mathsf{ENT}(Q)}{2}+\mathbf{D}_{q,n}$ ${}_{\textbf{3)}}$ | $\searrow$

1): |  $\mathbf{D}_{q,\min}:=\operatorname*{arg\,min}_{X\in\left\\{{\bf D}_{q}^{+},{\bf D}_{q}^{-}\right\\}}(|X|)$.
---|---
2): |  $\mathbf{D}_{q,p,\min}:=\begin{cases}{\bf D}_{q}^{-}&\mbox{if }p({\bf D}_{q}^{-})<p({\bf D}_{q}^{+})\\\ {\bf D}_{q}^{+}&\mbox{if }p({\bf D}_{q}^{+})<p({\bf D}_{q}^{-})\\\ 0&\mbox{else}\end{cases}$
3): |  $\mathbf{D}_{q,n}:=\begin{cases}{c}_{q}-n&\mbox{if }{c}_{q}\geq n\\\ |\mathbf{D}|&\mbox{else }\end{cases}$
|  where ${c}_{q}:=\min\\{|{\bf D}_{q}^{+}|,|{\bf D}_{q}^{-}|\\}$ and $n$
denotes the minimal number of diagnoses the selected query must eliminate [?]

Table 1: ([?, Tab. 2]) QSM designators (col. 1) and according functions $m(q)$
(col. 2). Col. 3 indicates whether QSM is optimized by maximization
($\nearrow$) or minimization ($\searrow$).

##  3 The Evaluated Heuristics

In this section we briefly revisit and explain the QSMs – originally
introduced in other works – we use in our experiments. These include the
“classical” ones [?; ?] frequently used in SD (cf. Sec. 1) and the newer ones
proposed in [?] and [?] and discussed in-depth in [?]. Since we employ a query
computation and selection method [?] that guarantees to produce only (the more
favorable, cf. [?, Sec. 2.4.1]) strong queries, [?, Tab. 3] tells us that we
have to deal with seven (non-equivalent) QSMs in this case. We next illustrate
the rough idea behind these heuristics, listed in Tab. 1.

Information Gain $\mathsf{ENT}$: Chooses a query with the highest expected
information gain or, equivalently, with the lowest expected posterior entropy
wrt. the diagnoses set $\mathbf{D}$. As derived in [?], $\mathsf{ENT}(q)$ is
the better, the closer the probabilities for positive and negative
classification of $q$ are to $0.5$ (cf. formula in Tab. 1).

Split-In-Half $\mathsf{SPL}$: Chooses a query $q$ whose QP best splits the
diagnoses set $\mathbf{D}$ in half, i.e. where both $|{\bf D}_{q}^{+}|$ and
$|{\bf D}_{q}^{-}|$ are closest to $\frac{1}{2}|\mathbf{D}|$. Intuitively, an
optimal $q$ wrt. $\mathsf{SPL}$ guarantees that a half of the (known)
diagnoses are eliminated by querying $q$’s classification.

Kullback-Leibler Divergence $\mathsf{KL}$: Chooses a query with largest
average disagreement between query-classification predictions of single
diagnoses $\mathcal{D}\in\mathbf{D}$ and the consensus (prediction) of all
$\mathcal{D}\in\mathbf{D}$, based on an information-theoretic measure of the
difference between two probability distributions [?]. As demonstrated in [?,
Prop. 26], this QSM can be represented in terms of the formula given in Tab.
1.

Expected Model Change $\mathsf{EMCb}$: Chooses a query for which the expected
number of invalidated diagnoses in $\mathbf{D}$ is maximized.

Most Probable Singleton $\mathsf{MPS}$: Chooses a query $q$ for which the
minimum-cardinality set among $\left\\{{\bf D}_{q}^{+},{\bf
D}_{q}^{-}\right\\}$ is a singleton $\left\\{\mathcal{D}\right\\}$ where
$\mathcal{D}$ has maximal probability. Intuitively, $\mathsf{MPS}$ seeks to
eliminate, with a maximal probability, the maximal possible number of
$|\mathbf{D}|-1$ diagnoses in $\mathbf{D}$.

Biased Maximal Elimination $\mathsf{BME}$: Chooses a query with a bias
(probability > 0.5) towards one classification ($\mathit{P}$ or $\mathit{N}$)
such that this more likely classification rules out an as high as possible
number of diagnoses in $\mathbf{D}$.

Risk Optimization $\mathsf{RIO}^{\prime}$: Chooses a query with optimal
information gain ($\mathsf{ENT}$-value) among those that, in the worst case,
eliminate (at least) $n\leq\frac{1}{2}|\mathbf{D}|$ diagnoses in $\mathbf{D}$.
At this, the parameter $n$ is learned by reinforcement based on the diagnoses
elimination performance achieved so far during an SD session.111Note, we
consider the slightly modified version $\mathsf{RIO}^{\prime}$ of the original
QSM $\mathsf{RIO}$ [?], as suggested in [?].

In addition to these informed QSMs, we used a random QSM in our evaluations as
a baseline:

Random $\mathsf{RND}$: Samples one element uniformly at random from the
considered query space $\mathbf{Q}$.

$q$ | ${\bf D}_{q}^{+}$ | ${\bf D}_{q}^{-}$ | $p({\bf D}_{q}^{+})$ | $p({\bf D}_{q}^{-})$
---|---|---|---|---
$\mathit{ax}_{1}$ | $\left\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3},\mathcal{D}_{4},\mathcal{D}_{6}\right\\}$ | $\left\\{\mathcal{D}_{5}\right\\}$ | 0.59 | 0.41
$\mathit{ax}_{2}$ | $\left\\{\mathcal{D}_{5},\mathcal{D}_{6}\right\\}$ | $\left\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3},\mathcal{D}_{4}\right\\}$ | 0.45 | 0.55
$\mathit{ax}_{3}$ | $\left\\{\mathcal{D}_{2},\mathcal{D}_{3},\mathcal{D}_{4},\mathcal{D}_{5}\right\\}$ | $\left\\{\mathcal{D}_{1},\mathcal{D}_{6}\right\\}$ | 0.95 | 0.05
$\mathit{ax}_{4}$ | $\left\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3},\mathcal{D}_{4}\right\\}$ | $\left\\{\mathcal{D}_{5},\mathcal{D}_{6}\right\\}$ | 0.55 | 0.45
$\mathit{ax}_{5}$ | $\left\\{\mathcal{D}_{1},\mathcal{D}_{3},\mathcal{D}_{4},\mathcal{D}_{5},\mathcal{D}_{6}\right\\}$ | $\left\\{\mathcal{D}_{2}\right\\}$ | 0.67 | 0.33
$\mathit{ax}_{6}$ | $\left\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{4},\mathcal{D}_{5},\mathcal{D}_{6}\right\\}$ | $\left\\{\mathcal{D}_{3}\right\\}$ | 0.86 | 0.14
$\mathit{ax}_{7}$ | $\left\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3}\right\\}$ | $\left\\{\mathcal{D}_{4},\mathcal{D}_{5},\mathcal{D}_{6}\right\\}$ | 0.48 | 0.52
Table 2: Q-partitions for the queries $q_{i}:=\mathit{ax}_{i}$ in Ex. 2.

We next illustrate these different selection principles:

Example 1 Consider a DPI (cf. [?, Tab. 1+2]) with
$\mathcal{K}=\left\\{1,\dots,7\right\\}$ (where numbers $i$ denote sentences
$\mathit{ax}_{i}$) which gives rise to the minimal diagnoses $\mathbf{D}$
given by

$\left\\{\mathcal{D}_{1},\dots,\mathcal{D}_{6}\right\\}=\left\\{[2,3],[2,5],[2,6],[2,7],[1,4,7],[3,4,7]\right\\}$

and diagnoses probabilities

$\left\\{p(\mathcal{D}_{1}),\dots,p(\mathcal{D}_{6})\right\\}=\left\\{0.01,0.33,0.14,0.07,0.41,0.04\right\\}$

Let, for simplicity, the possible queries be direct tests of components
$c_{i}$. That is, there are seven queries $q_{i}:=\mathit{ax}_{i}$
($i=1,\dots,7$) where their QPs are shown in Tab. 2. Then, the query choice of
the discussed QSMs is as follows:

  * •

$\mathsf{ENT}$: $q_{7}$, as $p({\bf D}_{q_{7}}^{+})$ and $p({\bf
D}_{q_{7}}^{-})$ are closest to $0.5$.

  * •

$\mathsf{SPL}$: $q_{7}$, as $|{\bf D}_{q_{7}}^{+}|$ and $|{\bf
D}_{q_{7}}^{-}|$ are equal to $\frac{|\mathbf{D}|}{2}=3$.

  * •

$\mathsf{KL}$: $q_{3}$, as $\mathsf{KL}(q_{3})=1.48$ is maximal over all
queries.

  * •

$\mathsf{EMCb}$: $q_{7}$, as the expected number of eliminated diagnoses is
$3$ (and lower for all other queries).

  * •

$\mathsf{MPS}$: $q_{1}$, as $|{\bf
D}_{q_{1}}^{-}|=|\left\\{\mathcal{D}_{5}\right\\}|=1$ and
$p(\mathcal{D}_{5})=0.41>0.33(\text{cf. }q_{5})>0.14(\text{cf. }q_{6})$.

  * •

$\mathsf{BME}$: $q_{7}$, as it has a $\mathsf{BME}$-value of $3$ (larger than
the value of all other queries).

  * •

$\mathsf{RIO}^{\prime}$ (with $n=2$): $q_{2}$ or $q_{4}$, as these are the
queries with best $\mathsf{ENT}$-value among all queries ($q2,q3,q4$) which
eliminate $n$ diagnoses in $\mathbf{D}$ in the worst case.

[t]  $j$ KB $\mathcal{K}_{j}$ $|\mathcal{K}_{j}|$ reasoning complexity a
#D/min/max b 1 University (U) c 50 $\mathcal{SOIN}^{(D)}$ 90/3/4 2 MiniTambis
(M) c 173 $\mathcal{ALCN}$ 48/3/3 3 Transportation (T) c 1300
$\mathcal{ALCH}^{(D)}$ 1782/6/9 4 Economy (E) c 1781 $\mathcal{ALCH}^{(D)}$
864/4/8

  * a

Description Logic expressivity, cf. [?, p. 525ff.].

  * b

#D, min, max denote the number, the min. and max. size of diagnoses _for the
initial DPI_ (the actual diagnoses search space explored in an SD session
might be substantially larger due to a change of the DPI after each
measurement addition; also, diagnoses sizes can only increase during an SD
session [?]).

  * c

Sufficiently complex systems (#D $\geq 40$) used in [?].

Table 3: Dataset used in experiments.

##  4 Experimental Settings

The Dataset. Tab. 3 depicts the (part of the overall) dataset investigated in
the already finished experiments. The underlying systems are faulty
(inconsistent) real-world knowledge bases (KBs). The DPIs $\mathit{dpi}_{j}$
we extracted from these KBs $\mathcal{K}_{j}$ were
$\left\langle\mathcal{K}_{j},\emptyset,\emptyset,\emptyset\right\rangle$, i.e.
the background $\mathcal{B}$, positive ($\mathit{P}$) and negative
($\mathit{N}$) measurements were (initially) empty.

Please note that using KBs as test cases does not restrict the generality [?]
of the results – any MBD problem can be modeled as a faulty KB. It is rather
the diagnostic structure (e.g. system size, number and size of diagnoses,
reasoning complexity) and the used meta information (e.g. probabilities) that
have a major influence. The diagnostic structure for the used test cases is
given in Tab. 3.

Concerning the system components, note that each $\mathit{ax}\in\mathcal{K}$
is (interpreted as) describing a complex component, consisting of sub-
components, where the latter are given by the logical operators occurring in
$\mathit{ax}$, as done in [?]. This interpretation helped us to obtain a self-
consistent ascription of component and diagnoses probabilities by specifying
the probabilities of the sub-components (cf. Sec. 2).

The Factors. To test the behavior and robustness of the discussed QSMs under
various scenarios, we – in addition to the DPI – varied the following factors
in our experiments:

  1. (F1)

the type of (sub-component) probability distribution (_non-biased_ ,
_moderately biased_ , _strongly biased_);

  2. (F2)

$3$ different random choices of assigned probabilities for each distribution
type (to average out potential peculiarities of a specific probability
assignment),

  3. (F3)

the plausibility of the probabilities (simulated by _plausible_ , _random_ ,
_implausible_ oracle behavior),

  4. (F4)

the amount of information available for query selection (number of leading
diagnoses $\mathit{ld}\in\left\\{6,10,14\right\\}$), and

  5. (F5)

the actual diagnosis $\mathcal{D}^{*}$ (i.e. the target solution of the SD
sessions).

_Ad (F1)_ : Let $\mathit{SC}$ denote the set of all sub-components occurring
in some $\mathit{ax}\in\mathcal{K}$ and $E_{\lambda}(x)=\lambda e^{-\lambda
x}$ the probability density function of the exponential distribution. Three
probability distribution types were modeled, by assigning to each sub-
component in $\mathit{SC}\dots$

  * •

_all-equal (EQ)_ : $\dots$an equal (random) value $r\in[0,1]$

  * •

_moderately biased (MOD)_ : $\dots$the probability $E_{\lambda}(x_{i})$ for a
random $x_{i}\in[i-\frac{1}{2},i+\frac{1}{2})$ where $i$ is randomly chosen
(without replacement) from $\left\\{1,\dots,|\mathit{SC}|\right\\}$ and
$\lambda:=0.5$ (cf. [?])

  * •

_strongly biased (STR)_ : $\dots$the probability $E_{\lambda}(x_{i})$ for a
random $x_{i}\in[i-\frac{1}{2},i+\frac{1}{2})$ where $i$ is randomly chosen
(without replacement) from $\left\\{1,\dots,|\mathit{SC}|\right\\}$ and
$\lambda:=1.75$ (cf. [?])

Intuitively, one can view both MOD and STR to (1) precompute a sequence
$p_{1}>\dots>p_{|\mathit{SC}|}$ of values in $(0,1)$ where, on average, the
ratio between each value $p_{i}$ and the next smaller one $p_{i+1}$ is
$p_{i}/p_{i+1}=e^{\lambda}$, i.e. $\approx 1.6$ for MOD and $\approx 5.8$ for
STR, and (2) assign to each $sc\in\mathit{SC}$ a randomly chosen probability
$p_{i}$ from this sequence without replacement. Hence, if sorted from large to
small, the sub-component probabilities are completely uniform for EQ (_no
bias_), moderately descending for MOD (_moderate bias_) and steeply descending
for STR (_strong bias_).

For instance, EQ could model a situation where a novel device gets defect or a
novice knowledge/software engineer obtains faulty code, and there is no
relevant fault information about device parts or code at hand. On the other
hand, MOD can be interpreted to simulate a moderate tendency in the fault
information, i.e. a non-negligible number of (sub-)components that have a non-
negligible fault probability. For example, assume a car mechanic who knows
from experience that, say, a dozen of parts are mostly responsible for
failures whereas all others must be very rarely replaced. STR reflects cases
where the differences in fault likeliness are substantial, i.e. very few
(sub-)components have a non-negligible probability of being abnormal, whereas
most of the (sub-)components are practically always nominal. An example is a
knowledge engineer that, in the past, has made almost only errors regarding
quantifiers.

_Ad (F3)_ : Let $q$ be a query with $p(\mathsf{class}(q)=\mathit{P})=x$ (cf.
Sec. 2). The plausibility of the given probabilistic information was modeled
by different oracle functions $\mathsf{class}$, simulating different
strategies of query classification:

  * •

_plausible_ : classify $q$ to $\mathit{P}$ with probability $x$

  * •

_random_ : classify $q$ to $\mathit{P}$ with probability $0.5$

  * •

_implausible_ : classify $q$ to $\mathit{P}$ with probability $1-x$

Recall (Sec. 2),
$p(\mathsf{class}(q)=\mathit{N})=1-p(\mathsf{class}(q)=\mathit{P})$. The idea
is that, given (un)reasonable fault information, the estimated query
classification probabilities should be good (bad) approximations of the real
likeliness of getting a respective outcome. The plausible scenario reflects
the case where given probabilities are useful and provide a rational bias,
e.g. for mass products that have been on the market for a long time. The
random strategy aims at estimating the average number of queries needed to pin
down $\mathcal{D}^{*}$, assuming we cannot make useful predictions about the
oracle. The implausible strategy represents a misleading fault model, where
probabilities turn out to be opposite to what the given information suggests,
e.g., when using subjective estimates or historical data that does not apply
to the present scenario. As QSMs utilize fault information for query
suggestion, we want to assess their robustness under changing fault
information quality [?; ?].

_Ad (F5)_ : We specified the target solution $\mathcal{D}^{*}$ in the
different SD sessions implicitly through the oracle answer strategies, see
(F3). That is, each SD session continued until positive
($\mathit{P}^{\prime}$) and negative ($\mathit{N}^{\prime}$) measurements were
collected such that there was just a single minimal diagnosis for the DPI
$\left\langle\mathcal{K}_{j},\emptyset,\mathit{P}^{\prime},\mathit{N}^{\prime}\right\rangle$
(resulting from the initial DPI by adding $\mathit{P}^{\prime}$ and
$\mathit{N}^{\prime}$, cf. Problem 1). This implicit definition of
$\mathcal{D}^{*}$ has the advantage of higher generality and closeness to
reality over a prior explicit fixation of some $\mathcal{D}^{*}$ among the
minimal diagnoses for the initial DPI
$\left\langle\mathcal{K}_{j},\emptyset,\emptyset,\emptyset\right\rangle$ [?].
Because, in the latter case only one specific class of SD problems is
considered, namely those where the actual solution is already a minimal
diagnosis for the start problem. In practice, it might well be the case that
the actual solution is a superset of an initial minimal diagnosis.

The Tests. For each of the DPIs $\mathit{dpi}_{1},\dots,\mathit{dpi}_{4}$, for
each of the $8$ QSMs explicated in Sec. 3, and for each of the $3^{4}$ factor
level combinations of factors (F1) – (F4) we performed $20$ SD sessions.
Factor (F5) was implicitly varied in these $20$ runs through the randomized
oracle behavior (F3), yielding in most cases a different $\mathcal{D}^{*}$. In
case some $\mathcal{D}^{*}$ happened to occur repeatedly throughout the $20$
sessions, we discarded such duplicate runs.222For logs, etc. see
http://isbi.aau.at/ontodebug/evaluation.

##  5 Experimental Results

###  5.1 Representation

The obtained results are shown by Figures LABEL:fig:eval_university_overall –
LABEL:fig:eval_economy which graph the number of queries required by the
tested QSMs until $\mathcal{D}^{*}$ could be isolated. At this, the green /
yellow / red bars depict the situation of a plausibly / randomly / implausibly
answering oracle (F3). Each bar represents an average over (up to) $20$
sequential diagnosis sessions (F5) and $3$ random choices of probabilities
(F2). Each figure summarizes the results for one case in Tab. 3; the plots for
the U and T cases are more comprehensive, including all combinations of factor
levels for (F1), (F2) and (F4), whereas the depictions of M and E are kept
shorter due to space restrictions, showing only the $\mathit{ld}=10$ case of
(F4) for all settings of (F1) and (F2). Along the x-axes of the figures we
have the $8$ different QSMs, grouped by manifestations of factor (F4) in
Figures LABEL:fig:eval_university_overall and
LABEL:fig:eval_transportation_overall, and by instantiations of factor (F1) in
Figures LABEL:fig:eval_minitambis and LABEL:fig:eval_economy.

###  5.2 Observations

Interesting gained insights are discussed next.

Is there a Clear Winner? This question can be answered negatively pretty
clearly. For instance, have a look at the MOD, $\mathit{ld}=14$ case in Fig.
LABEL:fig:eval_university_overall. Here we see that $\mathsf{MPS}$ performs
really good compared to all other QSMs for all oracle types. In fact, it is
better than all others in the plausible and random configurations, and loses
just narrowly against $\mathsf{RND}$ given implausible answers. However, if we
draw our attention to, e.g., the EQ case in the same figure, we recognize that
$\mathsf{MPS}$ comes off significantly worse than other heuristics under a
plausible oracle behavior. Similar argumentations apply for all other
potential winner QSMs. For $\mathit{ld}=10$, Tab. 4, which lists the best QSMs
in all the different settings we investigated, confirms that there is no
single best QSM.

Sensitivity to Fault Information. That there is no QSM which always outmatches
all others is not a great surprise, as we evaluate under various types of
given probabilistic information $p(.)$ and the different measures exploit
$p(.)$ to a different extent when selecting a query. As a result, we can
observe probability-independent QSMs such as $\mathsf{SPL}$ outperform (lose
against) strongly probability-reliant ones such as $\mathsf{ENT}$ in
situations where the fault information is wrongly (reasonably) biased, e.g.,
see the implausible (plausible) cases for MOD and STR in Figures
LABEL:fig:eval_university_overall and LABEL:fig:eval_transportation_overall.
So, e.g., $\mathsf{SPL}$ can never benefit from high-quality meta information
about faults, but cannot effect a significant overhead given low-quality
probabilities either. The behavior of, e.g., $\mathsf{ENT}$, is diametrically
opposite. To verify this, check the difference between the green and red bars
for both $\mathsf{SPL}$ and $\mathsf{ENT}$ for MOD and STR; for $\mathsf{SPL}$
they are hardly different at all, whereas for $\mathsf{ENT}$ they diverge
rapidly as we raise the bias (EQ $\to$ MOD $\to$ STR) in the underlying
distribution. In contrast to these extreme cases, there is, e.g.,
$\mathsf{RIO}^{\prime}$ which incorporates both the diagnoses elimination rate
and fault probabilities in its calculations. The consequence is a behavior
that mostly lies in between the performances of $\mathsf{SPL}$ and
$\mathsf{ENT}$. Based on the data in the figures, which is quite consistent in
this regard, one could impose the following _qualitative ordering from most to
least probability-sensitive_ on the QSMs:

$\displaystyle\left\langle\mathsf{EMCb},\mathsf{BME},\mathsf{ENT},\mathsf{KL},\mathsf{MPS},\mathsf{RIO}^{\prime},\mathsf{RND},\mathsf{SPL}\right\rangle$
(1)

Impact of the DPI / Diagnostic Structure. Trivially, the overall number of
diagnoses to discriminate between impacts the average number of queries
required. Thus, for M (48 diagnoses), U (90), E (864) and T (1782),
respectively, the min/avg/max number of queries over all QSMs and sessions is
(rounded) $3$/$7$/$18$, $4$/$8$/$19$, $6$/$10$/$19$ and $4$/$12$/$29$. The
difference between M and E, for instance, can be quite well seen by comparing
the length of the bars in Figures LABEL:fig:eval_minitambis and
LABEL:fig:eval_economy which are placed side by side. On the contrary and as
one would expect, there are no indications of the system size
$|\mathcal{K}_{j}|$ (3rd column, Tab. 3) having a remarkable influence on QSM
performance (as the system size has generally no bearing on the diagnoses
number). The reasoning complexity (4th column, Tab. 3), in contrast, affects
the query computation time, which was, over all runs and QSMs, maximally
$0.18$/$0.13$/$0.18$/$0.14$ sec (per query) for the cases M/U/E/T. The
relative behavior of the QSMs under varying DPI (but otherwise same
conditions) appears to be quite stable. To see this, compare, e.g., the EQ,
the MOD and the STR cases between Figures LABEL:fig:eval_university_overall
and LABEL:fig:eval_transportation_overall, or Figures
LABEL:fig:eval_minitambis and LABEL:fig:eval_economy. From the pragmatic point
of view, if this consistency of QSM performances irrespective of the
particular DPI generalizes (as needs to be verified using a larger dataset), a
nice implication thereof would be the possibility to recommend (against) QSMs
independently of (the structure of) the problem at hand.

Impact of the Leading Diagnoses. As Figures LABEL:fig:eval_university_overall
and LABEL:fig:eval_transportation_overall indicate quite well, and numbers
confirm, there is no significant average difference in the numbers of queries
for varying $\mathit{ld}\in\left\\{6,10,14\right\\}$. This is in line with the
findings of [?]. What we can realize, though, is an exacerbation of the
discrepancy between the plausible (green bars) and implausible (red bars)
cases when $\mathit{ld}$ increases. The random case (yellow bars), on the
other hand, is mostly stable. The reason for this intensification of the
effect of good or bad bias with larger diagnoses samples is that more extreme
decisions might be made in this case. A simple illustration of this is to
compare a “risky” [?] query (one that might invalidate very few diagnoses)
wrt. a sample of $3$ and $100$ diagnoses; in the former case, this would be
one eliminating either $1$ or $2$, in the latter one ruling out either $1$ or
$99$ known hypotheses. We see that the former query is similar to a “risk-
less” split-in-half choice, while the latter is far off being that
conservative. A practical consequence of this is that it might make sense to
try generating a higher number of diagnoses per iteration (if feasible in
reasonable time) if a probability-based measure, e.g. $\mathsf{EMCb}$ or
$\mathsf{ENT}$, is used and the trust in the given (biased) fault information
is high (e.g. if reliable historical data is available). Verify this by
considering $\mathsf{EMCb}$ and $\mathsf{ENT}$ in the MOD and STR cases for
$\mathit{ld}\in\left\\{6,14\right\\}$ in Figures
LABEL:fig:eval_university_overall and LABEL:fig:eval_transportation_overall.
By contrast, when adopting a probability-insensitive QSM, say $\mathsf{SPL}$,
one seems to be mostly better off when relying on a smaller $\mathit{ld}$.
That is, when the meta information is vague, a good option is to rely on a
“cautious” [?] measure such as $\mathsf{SPL}$ _and_ a small diagnoses sample.
Note, the latter is doubly beneficial as it also decreases computation times.

| PLAUSIBLE |  | RANDOM |  | IMPLAUSIBLE
---|---|---|---|---|---
| EQ | MOD | STR |  | EQ | MOD | STR |  | EQ | MOD | STR
M | $\mathsf{KL}$ |  $\mathsf{RIO}^{\prime}$, $\mathsf{ENT}$, $\mathsf{BME}$ |  $\mathsf{MPS}$, $\mathsf{ENT}$ |  | $\mathsf{MPS}$ | $\mathsf{MPS}$ | $\mathsf{MPS}$ |  | $\mathsf{MPS}$ | $\mathsf{RND}$ | $\mathsf{RND}$
63 | 176 | 144 |  | 46 | 47 | 48 |  | 118 | 131 | 277
U | $\mathsf{BME}$ | $\mathsf{BME}$ |  $\mathsf{MPS}$, $\mathsf{BME}$ |  | $\mathsf{MPS}$ | $\mathsf{MPS}$ | $\mathsf{MPS}$ |  | $\mathsf{RND}$ | $\mathsf{RND}$ |  $\mathsf{RND}$, $\mathsf{KL}$
59 | 129 | 151 |  | 42 | 50 | 53 |  | 67 | 149 | 220
E | $\mathsf{BME}$ | $\mathsf{ENT}$ |  $\mathsf{EMCb}$, $\mathsf{RIO}^{\prime}$, $\mathsf{BME}$ |  |  $\mathsf{ENT}$, $\mathsf{MPS}$ | $\mathsf{MPS}$ |  $\mathsf{ENT}$, $\mathsf{RIO}^{\prime}$, $\mathsf{BME}$, $\mathsf{MPS}$ |  | $\mathsf{MPS}$ | $\mathsf{KL}$ | $\mathsf{RND}$
64 | 93 | 90 |  | 30 | 33 | 37 |  | 121 | 191 | 93
T | $\mathsf{EMCb}$ |  $\mathsf{EMCb}$, $\mathsf{RIO}^{\prime}$, $\mathsf{ENT}$ |  $\mathsf{ENT}$, $\mathsf{BME}$, $\mathsf{EMCb}$, $\mathsf{MPS}$ |  | $\mathsf{MPS}$ | $\mathsf{MPS}$ | $\mathsf{MPS}$ |  | $\mathsf{MPS}$ | $\mathsf{RND}$ | $\mathsf{RND}$
62 | 125 | 174 |  | 45 | 40 | 38 |  | 93 | 102 | 123
Table 4: Shows which QSM(s) exhibited best performance in the various
scenarios in (F1)$\times$(F3) for all DPIs (1st column) in Tab. 3 and the
setting $\mathit{ld}=10$ of (F4). The QSM(s) with lowest $\\#$ of queries (per
scenario) are underlined. All stated non-underlined QSMs lay within $3\%$ of
the best QSM wrt. $\\#$ of queries. The number below the QSM(s) gives the
possible overhead
$(\\#q_{\mathit{worstQSM(S),S}}/\\#q_{\mathit{bestQSM(S),S}}-1)*100$ in $\%$
incurred by using a non-optimal QSM in a scenario $S$, where $\\#q_{X,S}$
refers to the $\\#$ of required queries of QSM $X$ in scenario $S$, and
$\mathit{bestQSM(S)}$ / $\mathit{worstQSM(S)}$ denote the best / worst QSM in
scenario $S$. The colors signify criticality of QSM choice based on the
overhead, from lowest=green to highest=red.

Importance of Using a Suitable QSM. To quantify the importance of QSM choice
we compute the _degree of criticality of choosing the right QSM in a scenario_
as the overhead in oracle cost (number of queries) when employing the worst
instead of the best QSM in this scenario, see (the caption of) Tab. 4. At
this, a scenario is one factor level combination in (F1)$\times$(F3). We learn
from Tab. 4 that, even in the least critical cases (green-colored), we might
experience a worst-case overhead in oracle effort of at least $30\%$ when
opting for the wrong QSM. This overhead is drastically higher in other cases
and reaches figures of over $250\%$. That is, more than triple the effort
might be necessary to locate a fault under an inopportune choice of QSM
heuristic. However, we emphasize that even a $30\%$ overhead must be
considered serious given that usually oracle inquiries are very costly. Hence,
appropriate QSM selection _is_ an important issue to be addressed in all
scenarios.

As a predictor of the criticality, the scenario (columns in Tab. 4) appears to
be a reasonable candidate, as the colors already suggest. In fact, the
coefficients of variance, one computed for each column in Tab. 4, are fairly
low, ranging from $3\%$ to $26\%$ (except for the last column with $47\%$).
So, the negative effect of a bad QSM choice is similar in equal scenarios, and
does not seem to be dependent on the DPI.

|  | $\mathsf{ENT}$ | $\mathsf{SPL}$ | $\mathsf{KL}$ | $\mathsf{EMCb}$ | $\mathsf{MPS}$ | $\mathsf{BME}$ | $\mathsf{RIO}^{\prime}$ | $\mathsf{RND}$
---|---|---|---|---|---|---|---|---|---
ALL | among best | 7 | 0 | 3 | 4 | 18 | 8 | 4 | 8
_the_ best | 4 | 0 | 2 | 4 | 16 | 4 | 2 | 8
PLAUSIBLE | among best | 5 | 0 | 1 | 4 | 3 | 7 | 3 | 0
_the_ best | 2 | 0 | 1 | 4 | 3 | 4 | 1 | 0
Table 5: Number of times each QSM is (among) the best in Tab. 4.

Which QSM to use in which Scenario? To approach this question, we have, for
all four DPIs, analyzed all the nine settings in (F1)$\times$(F3) regarding
the optimal choice of a QSM. The result is presented in Tab. 4. We now discuss
various insights from this analysis.

_Overall Picture._ $\mathsf{SPL}$ is never a (nearly) optimal option. This is
quite natural because, intuitively, going for no “risk” at all means at the
same time excluding the chance to perform extraordinarily well. All other QSMs
appear multiple times among those QSMs which are $\leq 3\%$ off the observed
optimal number of queries. Tab. 5 (rows 1+2) lists how often each QSM is
(among) the best. It shows that $\mathsf{MPS}$ is close to the optimum in a
half of the cases, significantly more often than all other heuristics.
However, blindly deciding for $\mathsf{MPS}$ is not a rational way to go.
Instead, one must consider the numbers at a more fine-grained level,
distinguishing between the quality of the given fault distribution (blocks in
Tab. 4), to get a clearer and more informative picture.

_The Implausible Cases:_ Here $\mathsf{RND}$ distinctly prevails. It occurs in
all but four optimal QSM sets, and is often _much_ better than other measures,
e.g., see the STR setting in Fig. LABEL:fig:eval_minitambis. At first sight,
it might appear counterintuitive that a random selection outweighs all others.
One explanation is simply that the randomness prevents $\mathsf{RND}$ from
getting misled by the (wrong) fault information. Remarkable is, however, that
in quasi all cases $\mathsf{RND}$ significantly outperforms $\mathsf{SPL}$,
which acts independently of the given probabilities as well. The conclusion
from this is that, whenever the prior distribution is wrongly biased,
introducing randomness into the query selection procedure saves oracle effort.

_The Random Cases:_ These cases are strongly dominated by $\mathsf{MPS}$ which
occurs in each set of best QSMs per scenario. Therefore, whenever the given
fault information does neither manifest a tendency towards nor against the
actual diagnosis, $\mathsf{MPS}$ is the proper heuristic. Moreover, the
benefit of using $\mathsf{MPS}$ seems to increase the more leading diagnoses
are available for query selection (see Figures
LABEL:fig:eval_university_overall and LABEL:fig:eval_transportation_overall).
Since $\mathsf{MPS}$, in attempt to invalidate _a maximal number of diagnoses_
, suggests very “risky” queries (see above), a possible explanation for this
is that acting on a larger diagnoses sample allows to guarantee a higher risk
than when relying on a smaller sample (cf. discussion above). However, as all
Figures LABEL:fig:eval_university_overall – LABEL:fig:eval_economy clearly
reveal, $\mathsf{MPS}$ is definitely the wrong choice in any situation where
we have a plausible, but unbiased probability distribution. In such cases it
manifests sometimes significantly worse results than other heuristics do. But,
as soon as a bias is given, the performance of MPS gets really good.

_The Plausible Cases:_ Throughout these cases we have the highest variation
concerning the optimal QSM. Actually, all QSMs except for $\mathsf{RND}$ and
$\mathsf{SPL}$ do appear as winners in certain cases. The distribution of the
number of appearances as (or among) the best QSM(s) over all QSMs is displayed
by Tab. 5 (rows 3+4). That, e.g., $\mathsf{ENT}$ is rather good in these cases
and $\mathsf{RND}$ is no good choice (see also the Figures
LABEL:fig:eval_university_overall – LABEL:fig:eval_economy) is in agreement
with the findings of [?]. However, we realize that $\mathsf{BME}$ is (among)
the best QSMs more often than $\mathsf{ENT}$. Comparing only these two, we
find that $\mathsf{BME}$ outdoes $\mathsf{ENT}$ $7$ times, $\mathsf{ENT}$ wins
against $\mathsf{BME}$ $4$ times, and they are equally good once. A reason for
the strength of $\mathsf{BME}$ could be the fact that it will in most cases
achieve only a minor bias towards one query outcome, as the maximization of
the diagnoses elimination rate requires an as small as possible number of
diagnoses with a probability sum $>0.5$. Thence, there is on the one hand a
bias increasing the expected diagnoses invalidation rate, and on the other
hand a near 50-50 outcome distribution implying a good entropy value of the
query. Unsurprisingly, if we sort the QSMs from most to least times being
(among) the best based on Tab. 5 (rows 3+4), the resulting order coincides
quite well with Eq. (1). In other words, in the plausible scenarios,
probability-sensitive heuristics perform best.

Towards new QSMs / Meta-Heuristics. Exploiting the discussed results, one
could endeavor to devise new QSMs that are superior to the investigated ones.
For instance, in the implausible cases, only $\mathsf{RND}$, $\mathsf{MPS}$
and $\mathsf{KL}$ occur as best QSMs. Thus, an optimal heuristic for these
cases should likely adopt or unify selection principles of these three QSMs.
One idea could be, e.g., to sample a few queries using $\mathsf{RND}$ and then
choose the best one among them using (a weighted combination of)
$\mathsf{MPS}$ and/or $\mathsf{KL}$. Generally, one could use a meta heuristic
that resorts to an appropriately (possibly dynamically re-)weighted sum of the
QSM-functions (Tab. 1, 2nd column). Also, a QSM selecting queries based on a
majority voting of multiple heuristics is thinkable, e.g., in Ex. 2 the query
selected by such a QSM would be $q_{7}$.

##  6 Conclusions

Results of extensive evaluations on both classical and recently suggested
query selection measures (QSMs) for sequential diagnosis (SD) are presented.
Main findings are: Using an appropriate QSM is essential, as otherwise SD cost
overheads of over $250\%$ are possible. The one and only best QSM does not
exist (or has not yet been found). Besides the size of the solution space,
main factors influencing SD cost are the bias in and the quality of the fault
probability distribution, but not the diagnosis problem as such or the size of
the diagnoses sample used for query selection. Different QSMs prevail in the
various probability distribution scenarios. Interestingly, the very popular
entropy measure only manifested good (albeit not best) behavior in a single
set of scenarios.

Future work topics include in-depth analyses of the (full) results and the
design of new QSMs, e.g. meta-heuristics, based on the lessons learned.
Moreover, machine learning techniques could be adopted to recommend optimal
QSMs based on a classification of a diagnosis scenario wrt. the QSM-relevant
factors we found. And, we plan to integrate the investigated QSMs into our
Protégé ontology debugging plug-in.333http://isbi.aau.at/ontodebug/plugin

## References

  * [1] L Hyafil and R L Rivest.  Constructing optimal binary decision trees is NP-complete.  Information processing letters, 5(1):15–17, 1976.
  * [2] K R Pattipati and M G Alexandridis.  Application of heuristic search and information theory to sequential fault diagnosis.  IEEE Transactions on Systems, Man, and Cybernetics, 20(4):872–887, 1990.
  * [3] J de Kleer, O Raiman, and M Shirley.  One step lookahead is pretty good.  In Readings in model-based diagnosis, pp. 138–142, 1992.
  * [4] K Shchekotykhin, G Friedrich, P Fleiss, and P Rodler.  Interactive Ontology Debugging: Two Query Strategies for Efficient Fault Localization.  JWS, 12-13:88–103, 2012.
  * [5] B Settles.  Active Learning.  M&C Publishers, 2012.
  * [6] M Shakeri, V Raghavan, K R Pattipati, and A Patterson-Hine.  Sequential testing algorithms for multiple fault diagnosis.  IEEE Trans. Systems, Man, and Cybernetics, Part A, 30(1):1–14, 2000.
  * [7] A Feldman, G M Provan, and A J C van Gemund.  A model-based active testing approach to sequential diagnosis.  JAIR, 39:301–334, 2010.
  * [8] C Mateis, M Stumptner, D Wieland, and F Wotawa.  Model-Based Debugging of Java Programs.  In AADEBUG’00, 2000.
  * [9] D Heckerman, J S Breese, and K Rommelse.  Decision-theoretic troubleshooting.  Communications of the ACM, 38(3):49–57, 1995.
  * [10] M Brodie, I Rish, S Ma, and N Odintsova.  Active probing strategies for problem diagnosis in distributed systems.  In IJCAI’03, pp. 1337–1338, 2003.
  * [11] P Rodler.  Interactive Debugging of Knowledge Bases.  PhD thesis, Alpen-Adria Universität Klagenfurt, 2015.  http://arxiv.org/pdf/1605.05950v1.pdf.
  * [12] J de Kleer and B C Williams.  Diagnosing multiple faults.  Artif. Intell., 32(1):97–130, 1987.
  * [13] A Gonzalez-Sanchez, R Abreu, H G Gross, and A J C van Gemund.  Spectrum-based sequential diagnosis.  In AAAI’11, pp. 189–196, 2011.
  * [14] P Rodler.  On active learning strategies for sequential diagnosis.  In DX’17, pp. 264–283, 2018.
  * [15] P Rodler and K Schekotihin.  Reducing model-based diagnosis to knowledge base debugging.  In DX’17, pp. 284–296, 2018.
  * [16] R Reiter.  A Theory of Diagnosis from First Principles.  Artif. Intell., 32(1):57–95, 1987.
  * [17] A Felfernig, G Friedrich, D Jannach, and M Stumptner.  Consistency-based diagnosis of configuration knowledge bases.  Artif. Intell., 152(2):213–234, 2004.
  * [18] P Rodler, K Shchekotykhin, P Fleiss, and G Friedrich.  RIO: Minimizing User Interaction in Ontology Debugging.  In RR’13, pp. 153–167, 2013.
  * [19] P Rodler.  Towards better response times and higher-quality queries in interactive knowledge base debugging.  Technical report, Alpen-Adria Universität Klagenfurt, 2016.  http://arxiv.org/pdf/1609.02584v2.pdf.
  * [20] P Rodler, W Schmid, and K Schekotihin.  Inexpensive cost-optimized measurement proposal for sequential model-based diagnosis.  In DX’17, pp. 200–218, 2018.
  * [21] P Rodler, W Schmid, and K Schekotihin.  A generally applicable, highly scalable measurement computation and optimization approach to sequential model-based diagnosis.  CoRR, abs/1711.05508, 2017.
  * [22] F Baader, et al.  The Description Logic Handbook: Theory, Implementation, and Applications.  Cambridge University Press, 2007.
  * [23] J de Kleer and O Raiman.  Trading off the costs of inference vs. probing in diagnosis.  In IJCAI’95, pp. 1736–1741, 1995.


[a]Konstantin Stankevich

# Collective neutrino oscillations accounting for neutrino quantum decoherence

Alexander Studenikin

###### Abstract

In our previous studies (see [1] and references therein) we developed a new
theoretical framework that enabled one to consider a new mechanism of neutrino
quantum decoherence engendered by the neutrino radiative decay. In parallel,
another framework was developed (see [2] and references therein) for the
description of the neutrino quantum decoherence due to the non-forward
neutrino scattering processes. Both mechanisms are described by the master
equations in the Lindblad form.

In the present studies we are are not interested in a specific mechanism of
neutrino quantum decoherence. Therefore, we use the general Lindblad master
equation for the description of the neutrino quantum decoherence and do not
fix an analytical expressions for the decoherence and relaxation parameters.

We study the influence of the neutrino quantum decoherence on collective
neutrino oscillations. Collective neutrino oscillations is a phenomenon
engendered by neutrino-neutrino interaction. It is significant in different
astrophysical environments where the neutrino density is extremely high.
Examples of such environments are the early universe, supernovae explosions,
binary neutron stars, accretion discs of black holes. The effect of collective
neutrino oscillations attracts the growing interest in sight of appearance of
multi-messenger astronomy and constructing of new large-volume neutrino
detectors that will be highly efficient for observing neutrino fluxes from
supernovae explosions. Previously, it was shown that neutrino quantum
decoherence can significantly modify the neutrino fluxes from reactors and the
sun. Here below we study the influence of the neutrino quantum decoherence on
supernovae neutrino fluxes. The peculiarity of the supernovae fluxes is that
one of the main modes of neutrino oscillations in supernovae is engendered by
the collective effects. Note, in the previous studies dedicated to the
collective neutrino oscillations only the kinematical decoherence (see [3] and
references therein) was accounted for.

Consider the two-flavor neutrino mixing scenarios, i.e. the mixing between
$\nu_{e}$ and $\nu_{x}$ states where $\nu_{x}$ stands for $\nu_{\mu}$ or
$\nu_{\tau}$. Here below we focus on the derivation of the neutrino
oscillation probability and highlight the interplay between collective
neutrino oscillations and neutrino quantum decoherence. We use the simplified
model of supernova neutrinos that was considered in [4, 5]. In such a model
neutrinos are produced and emitted with a single energy and a single emission
angle.

The neutrino evolution in supernovae environment that accounts for neutrino
quantum decoherence is determined by the following equations

$i\dfrac{d\rho_{f}}{dt}=[H,\rho_{f}]+D[\rho_{f}]\ ,\ \ \ \ \ \ \ \
i\dfrac{d\bar{\rho}_{f}}{dt}=[\bar{H},\bar{\rho}_{f}]+D[\bar{\rho}_{f}],$ (1)

where $\rho_{f}$ ($\bar{\rho}_{f}$) is the density matrix for neutrino
(antineutrino) in the flavour basis and $H$ ($\bar{H}$) are total neutrino
(antineutrino) Hamiltonian. Neutrino quantum decoherence is described by the
dissipation term $D[\rho]$ that we define in the next section.

Hamiltonian $H$ contains the three terms $H=H_{vac}+H_{M}+H_{\nu\nu}$, where
$H_{vac}$ is the vacuum Hamiltonian, $H_{M}$ and $H_{\nu\nu}$ are Hamiltonians
that describe matter potential and neutrino-neutrino interaction
correspondingly. The exact expressions one can find in [4, 5]. The dissipation
term $D[\rho]$ we write in the Lindblad form

$D\left[\rho_{\tilde{m}}(t)\right]=\dfrac{1}{2}\sum^{3}_{k=1}\left[V_{k},\rho_{\tilde{m}}V^{\dagger}_{k}\right]+\left[V_{k}\rho_{\tilde{m}},V_{k}^{\dagger}\right],$
(2)

where $V_{k}$ are the dissipative operators that arise from interaction
between the neutrino system and the external environment, $\rho_{\tilde{m}}$
is the neutrino density matrix in the effective mass basis. Here below, we
omit index “$\tilde{m}$” in order not overload formulas. The operators
$V_{k}$, $\rho_{f}$ and $H$ can be expanded over the Pauli matrices
$O=a_{\mu}\sigma_{\mu}$, where $\sigma_{\mu}$ are composed by an identity
matrix and the Pauli matrices. In this case eq. (1) can be written in the
following form

$\dfrac{\partial P_{k}(t)}{\partial
t}\sigma_{k}=2\epsilon_{ijk}H_{i}P_{j}(t)\sigma_{k}+D_{kl}P_{l}(t)\sigma_{k},$
(3)

where the matrix $D_{ll}=-diag\\{\Gamma_{1},\Gamma_{1},\Gamma_{2}\\}$ and
$\Gamma_{1}$, $\Gamma_{2}$ are the parameters that describe two dissipative
effects: 1) the decoherence effect and 2) the relaxation effect,
correspondingly. In the case of the energy conservation in the neutrino system
there is an additional requirement on a dissipative operators [6]
$[H_{S},V_{k}]=0$. In this case the relaxation parameter is equal to zero
$\Gamma_{2}=0$. Here below, we consider only the case of the energy
conservation, i.e. $\Gamma_{2}=0$.

Here below, we consider analytical conditions for the occurrence of the
neutrino collective effects. The onset of these collective effects has been
related to the presence of an instability (see [4] and references therein). In
order to study this instabilities we will apply to eq. (1) the linearization
procedure described in [4, 7]. Consider a time dependent small amplitude
variation $\delta P_{k}$ around the initial configuration $P^{0}_{k}$ and a
corresponding variation of the density dependent Hamiltonian $\delta H_{k}$
around the initial Hamiltonian $H^{0}_{k}$: $P_{k}=P_{k}^{0}+\delta P_{k}$
where $\delta P_{k}=P_{k}^{\prime}e^{-i\omega t}+H.c.$ and
$H_{k}=H_{k}^{0}+\delta H_{k}$ where $\delta H_{k}=H_{k}^{\prime}e^{-i\omega
t}+H.c.$. Where one can write $H_{k}^{\prime}=\dfrac{\partial H_{k}}{\partial
P_{k}}P_{k}^{\prime}+\dfrac{\partial
H_{k}}{\partial\bar{P}_{k}}\bar{P}_{k}^{\prime}$. In the case of high electron
density the in-medium eigenstates initially coincide with the flavor states.
Therefore, the initial conditions are given by
$H_{k}^{0}=\left(0,0,H^{0}\right)^{T}$ and
$P_{k}^{0}=\left(0,0,P^{0}\right)^{T}$. Putting everything together and
considering only the non-diagonal elements ($\rho_{12}=P_{x}+iP_{y}$) one
obtains the following equation for eigenvalues (we neglect the higher-order
corrections)

$(\omega-i\Gamma_{1})\left(\begin{matrix}\rho_{12}^{\prime}\\\
\bar{\rho}_{21}^{\prime}\end{matrix}\right)=\left(\begin{matrix}A_{12}&B_{12}\\\
\bar{A}_{21}&\bar{B}_{21}\end{matrix}\right)\left(\begin{matrix}\rho_{12}^{\prime}\\\
\bar{\rho}_{21}^{\prime}\end{matrix}\right),$ (4)

where on the right-hand side of equation is the stability matrix that
coincides with one from [4, 7]. In case of a single energy and single emission
angle it is expressed as

$\begin{matrix}A_{12}=(H^{0}_{11}-H^{0}_{22})-\dfrac{\partial
H_{12}}{\partial\rho_{12}}(\rho_{11}^{0}-\rho_{22}^{0}),\ \ \ \ \ \ \ \ \
B_{12}=\dfrac{\partial
H_{12}}{\partial\bar{\rho}_{21}^{0}}(\rho_{22}^{0}-\rho_{11}^{0}),\\\
\bar{A}_{21}=(\bar{H}^{0}_{22}-\bar{H}^{0}_{11})-\dfrac{\partial\bar{H}_{21}}{\partial\bar{\rho}_{21}}(\bar{\rho}_{22}^{0}-\bar{\rho}_{11}^{0}),\
\ \ \ \ \ \ \ \
\bar{B}_{21}=\dfrac{\partial\bar{H}_{21}}{\partial\rho_{12}^{0}}(\bar{\rho}_{11}^{0}-\bar{\rho}_{22}^{0}).\end{matrix}$
(5)

The eigenvalues are given by
$\omega=i\Gamma_{1}+\dfrac{1}{2}\left(A_{12}+\bar{A}_{21}\pm\sqrt{(A_{12}-\bar{A}_{21})^{2}+4B_{12}\bar{B}_{21}}\right)$.
One can see that if the eigenvalues have an imaginary part, the non-diagonal
elements of the neutrino density matrix can grow exponentially and thus the
system become unstable, that is, if

$\begin{cases}(A_{12}-\bar{A}_{21})^{2}+4B_{12}\bar{B}_{21}<0,\\\
\mathcal{I}m\left((A_{12}-\bar{A}_{21})^{2}+4B_{12}\bar{B}_{21}\right)>\Gamma_{1}.\end{cases}$
(6)

The first condition is the same as was derived in [4, 7]. The second term is a
new one that was not considered before. From eq. (6) one can see, that
neutrino quantum decoherence prevents a system from an exponential growth of
non-diagonal elements, i.e. neutrino quantum decoherence leads to the damping
of the neutrino collective oscillations.

In this paper we considered for the first time the effect of the neutrino
quantum decoherence in supernovae fluxes. We derive new conditions of the
collective neutrino oscillations accounting for neutrino quantum decoherence
which can appear as a result of the physics beyond the Standard Model. This
work was supported by the Russian Foundation for Basic Research under Grant
No. 20-52-53022-GFEN-a. The work of KS was also supported by the Russian
Foundation for Basic Research under Grant No. 20-32-90107.

## References

  * [1] K. Stankevich, A. Studenikin, Neutrino quantum decoherence engendered by neutrino radiative decay, Phys. Rev. D 101 (2020) no.5, 056004.
  * [2] J. F. Nieves and S. Sahu, Phys. Rev. D 102 (2020) no.5, 056007.
  * [3] F. Capozzi, G. Raffelt, T. Stirner, JCAP 09 (2019), 002.
  * [4] D. Vaananen, G. McLaughlin, Phys. Rev. D 93 (2016) no.10, 105044.
  * [5] C. J. Stapleford, D. J. Väänänen, J. P. Kneller, G. C. McLaughlin, B. T. Shapiro, Phys. Rev. D 94 (2016) no.9, 093007.
  * [6] R. L. N. Oliveira, Eur. Phys. J. C 76 (2016) no.7, 417.
  * [7] D. Vaananen and C. Volpe, Phys. Rev. D 88 (2013), 065003.