On the adoption of abductive reasoning for time series
interpretation
T. Teijeiro, P. Félix

arXiv:1609.05632v2 [] 20 Dec 2017

Centro Singular de Investigación en Tecnoloxı́as da Información (CITIUS), University of
Santiago de Compostela, Santiago de Compostela, Spain

Abstract
Time series interpretation aims to provide an explanation of what is observed in
terms of its underlying processes. The present work is based on the assumption
that the common classification-based approaches to time series interpretation
suffer from a set of inherent weaknesses, whose ultimate cause lies in the monotonic nature of the deductive reasoning paradigm. In this document we propose
a new approach to this problem, based on the initial hypothesis that abductive
reasoning properly accounts for the human ability to identify and characterize
the patterns appearing in a time series. The result of this interpretation is a
set of conjectures in the form of observations, organized into an abstraction hierarchy and explaining what has been observed. A knowledge-based framework
and a set of algorithms for the interpretation task are provided, implementing a
hypothesize-and-test cycle guided by an attentional mechanism. As a representative application domain, interpretation of the electrocardiogram allows us to
highlight the strengths of the proposed approach in comparison with traditional
classification-based approaches.
Keywords: Abduction, Interpretation, Time Series, Temporal Abstraction,
Temporal Reasoning, Non-monotonic Reasoning, Signal Abstraction

1. Introduction
The interpretation and understanding of the behavior of a complex system
involves the deployment of a cognitive apparatus aimed at guessing the processes
and mechanisms underlying what is observed. The human ability to recognize
patterns plays a paramount role as an instrument for highlighting evidence which
should require an explanation, by matching information from observations with
information retrieved from memory. Classification naturally arises as a pattern
recognition task, defined as the assignment of observations to categories.
Let us first state precisely at this point what is the problem under consideration: we wish to interpret the behavior of a complex system by measuring a
physical quantity along time. This quantity is represented as a time series.

Preprint submitted to Artificial Intelligence

December 21, 2017

The Artificial Intelligence community has devoted a great deal of effort on
different paradigms, strategies, methodologies and techniques for time series
classification. Nonetheless, in spite of the wide range of proposals for building
classifiers, either by eliciting domain knowledge or by induction from a set of
observations, the resulting classifier behaves as a deductive system. The present
work is premised on the assumption that some of the important weaknesses of
this approach lie in its deductive nature, and that an abductive approach can
address these shortcomings.
Let us remember that a deduction contains in its conclusions information
that is already implicitly contained in the premises, and thus it is truth-preserving.
In this sense, a classifier ultimately assigns a label or a set of labels to observations. This label can designate a process or a mechanism of the system being
observed, but it is no more than a term that summarizes the premises satisfied
by the observations. Conversely, abduction, or inference to the best explanation,
is a form of inference that goes from data to a hypothesis that best explains
or accounts for the data [21]. Abductive conclusions contain new information
not contained in the premises, and are capable of predicting new evidence, although they are fallible. Abductions are thus truth-widening, and they can
make the leap from the language of observations to the language of the underlying processes and mechanisms, responding to the aforementioned problem in
a natural way [24]. For example, consider a simple rule stating that if a patient
experiences a sudden tachycardia and a decrease in blood pressure, then we can
conclude that is suffering from shock due to a loss of blood volume. From a deductive perspective, loss of blood volume is just a name provided by the rule for
the satisfaction of the two premises. However, from an abductive perspective,
loss of blood volume is an explanatory hypothesis, a conjecture, that expands
the truth contained in the premises, enabling the observer to predict additional
consequences such as, for example, pallid skin, faintness, dizziness or thirst.
Of course, the result of a classifier can be considered as a conjecture, but
always from an external agent, since a classifier is monotonic as a logical system
and its conclusions cannot be refuted from within. Classifier ensembles aim to
overcome the errors of individual classifiers by combining different classification
instances to obtain a better result; thus, a classifier can be amended by others in
the final result of the ensemble. However, even an ensemble represents a bottomup mapping, and classification invariably fails above a certain level of distortion
within the data. The interpretation and understanding of a complex system
usually unfolds along a set of abstraction layers, where at each layer the temporal
granularity of the representation is reduced from below. A classification strategy
provides an interpretation as the result of connecting a set of classifiers along the
abstraction structure, and the monotonicity of deduction entails a propagation
of errors from the first abstraction layers upwards, narrowing the capability of
making a proper interpretation as new abstraction layers are successively added.
Following an abductive process instead, an observation is conjectured at each
abstraction layer as the best explanatory hypothesis for the data from the layer
or layers below, within the context of information from above, and the nonmonotonicity of abduction supports the retraction of any observation at any
2

abstraction layer in the search for the best global explanation. Thus, bottomup and top-down processing complement one another and provide a joint result.
As a consequence, abduction can guess the underlying processes from corrupted
data or even in the temporary absence of data.
On the other hand, a classifier is based on the assumption that the underlying processes or mechanisms are mutually exclusive. Superpositions of two or
more processes are excluded; they must be represented by a new process, corresponding to a new category which is different and usually unrelated to previous
ones. Therefore, an artificial casuistry-based heuristics is adopted, increasing
the complexity of the interpretation and reducing its adaptability to the variability of observations. In contrast, abduction can reach a conclusion from the
availability of partial evidence, refining the result by the incremental addition of
new information. This makes it possible to discern different processes just from
certain distinguishable features, and at the end to infer a set of explanations as
far as the available evidence does not allow us to identify the best one, and they
are not incompatible with each other.
In a classifier, the truth of the conclusion follows from the truth of all the
premises, and missing data usually demand an imputation strategy that results
in a conjecture: a sort of abducing to go on deducing. In contrast, an abductive
interpretation is posed as a hypothesize-and-test cycle, in which missing data
is naturally managed, since a hypothesis can be evoked by every single piece of
evidence in isolation and these can be incrementally added to reasoning. This
fundamental property of abduction is well suited to the time-varying requirements of the interpretation of time series, where future data can compel changes
to previous conclusions, and the interpretation task may be requested to provide
the current result as the best explanation at any given time.
Abduction has primarily been proposed for diagnostic tasks [10, 33], but also
for question answering [15], language understanding [22], story comprehension
[6], image understanding [36] or plan recognition [28], amongst others. Some
studies have proposed that perception might rely on some form of abduction.
Even though abductive reasoning has been proven to be NP-complete, a compiled form of abduction based on a set of pre-stored hypotheses could narrow
the generation of hypotheses [24]. The present work takes this assumption as
a starting point and proposes a model-based abductive framework for time series interpretation supported on a set of temporal abstraction patterns. An
abstraction pattern represents a set of constraints that must be satisfied by
some evidence in order to be interpreted as the hypothetical observation of a
certain process, together with an observation procedure providing a set of measurements for the features of the conjectured observation. A set of algorithms is
devised in order to achieve the best explanation through a process of successive
abstraction from raw data, by means of a hypothesize-and-test strategy.
Some previous proposals have adopted a non-monotonic schema for time
series interpretation. TrenDx system detects significant trends in time series
by matching data to predefined trend patterns [19, 20]. One of these patterns
plays the role of the expected or normal pattern, and the other patterns are
fault patterns. A matching score of each pattern is based on the error between
3

the pattern and the data. Multiple trend patterns can be maintained as competing hypotheses according to their matching score; as additional data arrive
some of the patterns can be discarded and new patterns can be triggered. This
proposal has been applied to diagnose pediatric growth trends. A similar proposal can be found in [27], taking a step further by providing complex temporal
abstractions, the result of finding out specific temporal relationships between
a set of significant trends. This proposal has been applied to the infectious
surveillance of heart transplanted patients. Another example is the Résumé
system, a knowledge-based temporal abstraction framework [42, 39]. Its goal
is to provide, from time-stamped input data, a set of interval-based temporal
abstractions, distinguishing four output abstraction types: state, gradient, rate
and pattern. It uses a truth maintenance system to retract inferred intervals
that are no longer true, and propagate new abstractions. Furthermore, this
framework includes a non-monotonic interpolation mechanism for trend detection [41]. This proposal has been applied to several clinical domains (protocolbased care, monitoring of children’s growth and therapy of diabetes) and to an
engineering domain (monitoring of traffic control).
The present work includes several examples and results from the domain
of electrocardiography. The electrocardiogram (ECG) is the recording at the
body’s surface of the electrical activity of the heart as it changes with time,
and is the primary method for the study and diagnosis of cardiac disease, since
the processes involved in cardiac physiology manifest in characteristic temporal
patterns on the ECG trace. In other words, a correct reading of the ECG has
the potential to provide valuable insight into cardiac phenomena. Learning to
interpret the ECG involves the acquisition of perceptual skills from an extensive
bibliography with interpretation criteria and worked examples. In particular,
pattern recognition is especially important in order to build a bottom-up representation of cardiac phenomena in multiple abstraction levels. This has encouraged extensive research on classification techniques for interpreting the ECG;
however, in spite of all these efforts, this is still considered an open problem.
We shall try to demonstrate that the problem lies in the nature of deduction
itself.
The rest of this paper is structured as follows: Section 2 introduces the main
concepts and terminology used in the paper in an informal and intuitive way.
Following this, in Sections 3, 4 and 5 we formally describe all the components
of the interpretation framework, including the knowledge representation model
and the algorithms used to obtain effective interpretations within an affordable
time. Section 6 illustrates the capabilities of the framework in overcoming some
of the most important shortcomings of deductive classifiers. Section 7 presents
the main experimental results derived from this work. Finally, in section 8 we
discuss the properties of the model compared with other related approaches and
draw several conclusions.

4

2. Interpretation as a process-guessing task
We propose a knowledge-based interpretation framework upon the principles
of abductive reasoning, on the basis of a strategy of hypothesis formation and
testing. Taking as a starting point a time series of physical measurements, a set
of observations are guessed as conjectures of the underlying processes, through
successive levels of abstraction. Each new observation will be generated from
previous levels as the underlying processes aggregate, superimpose or concatenate to form more complex processes with greater duration and scope, and are
organized into an abstraction hierarchy.
The knowledge of the domain is described as a set of abstraction patterns
as follows:
hψ ((Ah , Thb , The ) = Θ(A1 , T1 , ..., An , Tn )) abstracts m1 (A1 , T1 ), ..., mn (An , Tn )
{C(Ah , Thb , The , A1 , T1 , ..., An , Tn )}
where hψ (Ah , Thb , The ) is an observable of the domain playing the role of a
hypothesis on the observation of an underlying process ψ, where Ah represents a set of attributes, and its temporal support is represented by two instants Thb and The , corresponding to the beginning and the end of the observable; m1 (A1 , T1 ), . . . , mn (An , Tn ) is a set of observables of the domain which
plays the role of the evidence suggesting the observation of hψ , where each of
these has its own set of attributes Ai and temporal support Ti , represented
here as a single instant for the sake of simplicity, although this may also be
an interval; C is a set of constraints among the variables involved in the abstraction pattern, which are interpreted as necessary conditions in order for
the evidence m1 (A1 , T1 ), . . . , mn (An , Tn ) to be abstracted into hψ (Ah , Thb , The );
Θ(A1 , T1 , . . . , An , Tn ) is an observation procedure that gives as a result an
observation of hψ (Ah , Thb , The ) from a set of observations for m1 (A1 , T1 ), . . . ,
mn (An , Tn ).
To illustrate this concept, consider the sequence of observations in Figure 1.
Each of these observations is an instance of an observable we call point (p),
represented as p(A = {V }, T ), where T determines the temporal location of the
observation and V is a value attribute.
If we analyze these observations visually, we may hypothesize the presence
of an underlying sinusoidal process. Let us define an observable sinus for such
a sinusoidal process, with two attributes: the amplitude of the process (α) and
its frequency (ω). The knowledge necessary to conjecture this hypothesis is
collected in the following abstraction pattern:
hsinus ({α, ω}, Thb , The ) = Θ(V1 , T1 , ..., Vn , Tn )) abstracts p(V1 , T1 ), ..., p(Vn , Tn )
{C(α, ω, Thb , The , V1 , T1 , ..., Vn , Tn )}
We can estimate the attribute values (α, ω, Thb , The ) of this process by a simple
observation procedure Θ that calculates α = max(|Vi |), for 1 ≤ i ≤ n, i.e., the
amplitude α is obtained as the maximum absolute value of the observations; ω =
5

30
20

v

10
0
10

20
30
0

20

40

T

60

80

100

V 3.4 17.6 12.9 2.6 -17.5 -20 -10.5 -0.8 7.8 17.5 19.4 19.4 17.6 7.8 -14.9 -16.3 -11.6 15.6 17.1 -15.8 7.7 13.7 2.7 -19.8 -19.6 -3.1 0.2 8.1 9.6 0
T
1
4
8 10
14 15
19 21 22 24 26 27 28 30
34
35
40 45 47
55 64 70 73
78
80 83 84 85 86 94

Figure 1: Initial temporal observations.

peak
π/mean(Tjpeak −Tj−1
), where Tjpeak are point observations representing a peak,
satisfying (Vjpeak = Vk , Tjpeak = Tk ) ∧ sign(Vk − Vk−1 ) 6= sign(Vk+1 − Vk ), so
that the frequency ω is obtained as the inverse of the mean temporal separation
between consecutive peaks in the sequence of observations; and Thb = T1 , The =
Tn , i.e., the temporal support of the hypothesis is the time interval between the
first and the last evidence points.
We can impose the following constraint C(α, ω, Thb , The , V1 , T1 , . . . , Vn , Tn ) for
every pair (Vi , Ti ) in the sequence:

max(|α · sin(ω · Ti ) − Vi |) ≤ ,
This constraint provides a model of a sinusoidal process and a measure of
how well it fits a set of observations by means of a maximum error . Figure 2
shows the continuous representation of the abstracted process, whose resulting
observation is hsinus (α = 20, ω = 0.3, Thb = 1, The = 94). A value of α/3 has
been chosen for .
30
20
10

v

0
10

20
30
0

20

40

T

60

80

100

Figure 2: Abstracted sinusoidal process.

Of course, various observation procedures can be devised in order to estimate the same or different characteristics of the process being guessed. These
procedures can provide one or several valid estimations in terms of their consistency with the abovementioned necessary constraints. In addition, different
processes can be guessed from the same set of observations, all of them being

6

valid in terms of their consistency. Hence, further criteria may be needed in
order to rank the set of interpretations.
This simple example summarizes the common approach to the interpretation of experimental results in science and technology, when the knowledge is
available as a model or a set of models. The challenge is to assume that this
knowledge is not available in an analytical but in a declarative form, as a pattern or a set of patterns, and that the interpretation task is expected to mimic
certain mechanisms of human perception.
3. Definitions
In this section we formally define the main pieces of our interpretation framework: observables and observations for representing the behavior of the system
under study, and abstraction patterns for representing the knowledge about this
system.
3.1. Representation entities
An observation is the result of observing something with the quality of being
observable. We call Q = {q0 , q1 , ..., qn } the set of observables of a particular
domain.
Definition 1. We define an observable as a tuple q = hψ, A, T b , T e i, where ψ
is a name representing the underlying process being observable, A = {A1 , ..., Anq }
is a set of attributes to be valued, and T b and T e are two temporal variables
representing the beginning and the end of the observable.
We call Vq (Ai ) the domain of possible values for the attribute Ai . We assume a discrete representation of the time domain τ , isomorphic to the set of
natural numbers N. For any observable, we implicitly assume the constraint
T b < T e . In the case of an instantaneous observable, this is represented as
q = hψ, A, T i. Some observables can be dually represented from the temporal
perspective, as either an observable supported by a temporal interval or as an
observable supported by a temporal instant, according to the task to be carried
out. A paradigmatic example is found in representing the heart beat, since it
can be represented as a domain entity with a temporal extension comprising its
constituent waves, and it can also be represented as an instantaneous entity for
measuring heart rate.
Example 3.1. In the ECG signal, several distinctive waveforms can be identified, corresponding to the electrical activation-recovery cycle of the different
heart chambers. The so-called P wave represents the activation of the atria,
and is the first wave of the cardiac cycle. The next group of waves recorded is
the QRS complex, representing the simultaneous activation of the right and left
ventricles. Finally, the wave that represents the ventricular recovery is called
the T wave. Together, these waveforms devise the characteristic pattern of the
heart cycle, which is repeated in a normal situation with every beat [46]. An
example of a common ECG strip is shown in Figure 3.
7

According to this description, the observable qP w = hatrial activation,
{amplitude}, T b , T e i represents a P wave resulting from an atrial activation
process with an unknown amplitude, localized in a still unknown temporal interval.

P

T

Figure 3: Example of the ECG basic waveforms. [Source: MIT-BIH arrhythmia DB [18],
recording: 123, between 12:11.900 and 12:22.400]

Definition 2. We define an observation as a tuple o = hq, v, tb , te i, an instance
of the observable q resulting from assigning a specific value to each attribute
and to the temporal variables, where v = (v1 , . . . , vnq ) is the set of attribute
values such that v ∈ Vq (A1 ) × . . . × Vq (Anq ) and tb , te ∈ τ are two precise
instants limiting the beginning and the end of the observation.
We also use the notation (A1 = v1 , . . . , Anq = vnq ) to represent the assignment of values to the attributes of the observable and T b = tb and T e = te for
representing the assignment of temporal limits to the observation.
Example 3.2. The tuple o = hqP w , 0.17mV, 12 : 16.977, 12 : 17.094i represents
the particular occurrence of the P wave observable highlighted in Figure 3.
Some notions involving observables and observations are defined below that
will be useful in describing certain properties and constraints of the domain
concepts, as well as in temporally arranging the interpretation process.
Definition 3. Given a set of observables Q, a generalization relation can be
defined between two different observables q = hψ, A, T b , T e i and q 0 = hψ 0 , A0 ,
T 0b , T 0e i, denoted by q 0 is a q, meaning that q generalizes q 0 if and only if
A ⊆ A0 and Vq0 (Ai ) ⊆ Vq (Ai ) ∀Ai ∈ A.
The generalization relation is reflexive, antisymmetric and transitive. The
inverse of a generalization relation is a specification relation. From a logical
perspective, a generalization relation can be read as an implication q 0 → q,
meaning that q 0 is more specific than q. It holds that every observation o =
hq 0 , v, tb , te i of the observable q 0 is also an observation of q.
Example 3.3. A common example of a generalization relation can be defined from a domain partition of an attribute. For example, the observable
q1 = hSinus Rhythm, {RR ∈ [200ms, 4000ms]}, T b , T e i is a generalization of the
observables q2 = hSinus Tachycardia, {RR ∈ [200ms, 600ms]}, T b , T e i, q3 =
hNormal Rhythm, {RR ∈ [600ms, 1000ms]}, T b , T e i and q4 = hSinus Bradycardia,
{RR ∈ [1000ms, 4000ms]}, T b , T e i. The RR attribute represents the measure of
the mean time distance between consecutive beats, while q2 , q3 and q4 represent
the normal cardiac rhythm denominations according to the heart rate [46].
8

Definition 4. Given a set of observables Q, an exclusion relation can be
defined between two different observables q = hψ, A, T b , T e i and q 0 = hψ 0 , A0 ,
T 0b , T 0e i, denoted by q excludes q 0 , meaning that they are mutually exclusive
if and only if their respective processes ψ and ψ 0 cannot concurrently occur.
The exclusion relation is defined extensionally from the knowledge of the
domain, and its rationale lies in the nature of the underlying processes and
mechanisms. In so far as the occurrence of a process can only be hypothesized
as long as it is observable, the exclusion relation behaves as a restriction on observations. Thus, given two observables q and q 0 , q excludes q 0 entails that they
cannot be observed over two overlapping intervals, i.e., every two observations
o = hq, v, tb , te i and o0 = hq 0 , v0 , t0b , t0e i satisfy either te < t0b or t0e < tb . The opposite is not generally true. The exclusion relation is symmetric and transitive.
As an example, in the domain of electrocardiography, the knowledge about the
physiology of the heart precludes the observation of a P wave during an episode
of Atrial fibrillation [46], so these two observables are mutually exclusive.
We call O the set of observations available for the observables in Q. In
order to index this set of observations, they will be represented as a sequence
by defining an order relation between them. This ordering aims to prioritize the
interpretation of the observations as they appear.
Definition 5. Let < be an order relation between two observations oi =
hqi , vi , tbi , tei i and oj = hqj , vj , tbj , tej i such that (oi < oj ) ⇔ (tbi < tbj ) ∨ ((tbi =
tbj ) ∧ (tei < tej )) ∨ ((tbi = tbj ) ∧ (tei = tej ) ∧ (qi < qj )), assuming a lexicographical
order between observable names.
A sequence of observations is an ordered set of observations O = (o1 , ..., oi , ...)
where for all i < j then oi < oj . Every subset of a sequence of observations
is also a sequence. The q-sequence of observations from O, denoted as O(q),
is the subset of the observations for the observable q. The exclusion relation
forces that any two observations oi = hq, vi , tbi , tei i and oj = hq, vj , tbj , tej i in O(q)
satisfy oi < oj ⇒ tei < tbj for the current application domain. By succ(oi )
we denote the successor of the observation oi in the sequence O, according to
the order relation <. By q-succ(oi ) we denote the successor of the observation
oi ∈ O(q) in its q-sequence O(q). Conversely to this notation, we denote by
q(oi ) the observable corresponding to the oi observation.
3.2. Abstraction patterns
We model an abstraction process as an abduction process, based on the conjectural relation m ← h [21], which can be read as ‘the observation of the
finding m allows us to conjecture the observation of h as a possible explanatory hypothesis’. For example, a very prominent peak in the ECG signal allows
us to conjecture the observation of a heartbeat. A key aspect of the present
proposal is that both the hypothesis and the finding are observables, and therefore formally identical, i.e., there exists qi , qj ∈ Q, with qi 6= qj , such that
h ≡ qi = hψi , Ai , Tib , Tie i and m ≡ qj = hψj , Aj , Tjb , Tje i. In general, an abstraction process can involve a number of different findings, even multiple findings of
9

the same observable, and a set of constraints among them; thus, for example, a
regular sequence of normal heartbeats allows us to conjecture the observation of
a sinus rhythm. Additionally, an observation procedure is required in order to
produce an observation of the hypothesis from the observation of those findings
involved in the abstraction process.
We devise an abstraction process as a knowledge-based reasoning process,
supported by the notion of abstraction pattern, which brings together those
elements required to perform an abstraction. Formally:
Definition 6. An abstraction pattern P = hh, MP , CP , ΘP i consists of
a hypothesis h, a set of findings MP = {m1 , . . . , mn }, a set of constraints
CP = {C1 , . . . , Ct } among the findings and the hypothesis, and an observation
procedure ΘP (A1 , T1b , T1e , . . . , An , Tnb , Tne ) ∈ O(h).
Every constraint Ci ∈ CP is a relation defined on a subset of the set of
variables taking part in the set of findings and the hypothesis {Ah , Thb , The , A1 ,
T1b , T1e , . . . , An , Tnb , Tne }. Thus, a constraint is a subset of the Cartesian product of the respective domains, and represents the simultaneously valid assignments to the variables involved. We will denote each constraint by making
reference to the set of variables being constrained, as in CP (Ah , Thb , The , A1 ,
T1b , T1e , . . . , An , Tnb , Tne ) for the whole abstraction pattern.
An abstraction pattern establishes, through the set CP , the conditions for
conjecturing the observation of h from a set of findings MP , and through the
observation procedure ΘP , the calculations for producing a new observation oh ∈
O(h) from the observation of these findings. We call MSPq = {mq1 , mq2 , ..., mqs }
the set of findings of the observable q in P , being MP = q∈Q MPq . Thus, a set
of findings allows the elements of a multiset of observables to be distinguished.
The interpretation procedure will choose, as we will see later, from the available
observations for every observable q satisfying the constraints CP , which are to
be assigned to the findings in MPq in order to calculate oh .
The set of findings MP is divided into two sets AP and EP , being AP ∩EP =
∅, where AP is the set of findings that is said to be abstracted in oh , and EP is
the set of findings that constitute the observation environment of oh , that is, the
set of findings needed to properly conjecture oh , but which are not synthesized
in oh .
A temporal covering assumption can be made as a default assumption [36] on
a hypothesis h = hψh , Ah , Thb , The i with respect to those findings m = hψm , Am ,
b
e
Tm
, Tm
i appearing in an abstraction pattern:
Default Assumption 1. (Temporal covering) Given an abstraction pattern P ,
b
e
≤ The , for all m ∈ AP ⊆ MP .
it holds that Thb ≤ Tm
and Tm
The temporal covering assumption allows us to define the exclusiveness of
an interpretation as the impossibility of including competing abstractions in the
same interpretation.
Example 3.4. According to [11], in the electrocardiography domain a “wave” is
a discernible deviation from a horizontal reference line called baseline, where at
10

least two opposite slopes can be identified. The term discernible means that both
the amplitude and the duration of the deviation must exceed some minimum values, agreed as 20 µV and 6 ms respectively. A wave can be completely described
by a set of attributes: its amplitude (A), voltage polarity (V P ∈ {+, −}) and
its main turning point T tp , resulting in the following observable:
qwave = helectrical activity, {A, V P, T tp }, T b , T e i
Let us consider the following abstraction pattern:
Pwave = hwave, MP = {mECG
, . . . , mECG
}, CPwave , wave observation()i
0
n
where mECG
is a finding representing an ECG sample, with a single attribute
i
Vi representing the sample value, and a temporal variable Ti representing its
time point. We set the onset and end of a wave to the time of the second
ECG
as
mECG
and second-to-last mECG
and mECG
n
1
n−1 samples, considering m0
environmental observations which are used to check the presence of a slope
change just before and after the wave; thus EPwave = {mECG
, mECG
}, and
n
0
ECG
ECG
APwave = {m1
, . . . , mn−1 }.
A set of temporal constraints are established between the temporal variables:
c1 = {T e − T b ≥ 6ms}, c2 = {T b = T1 }, c3 = {T e = Tn−1 } and c4 = {T b <
T tp < T e }. Another set of constraints limit the amplitude and slope changes
of the samples included in a wave: c5 = {sign(V1 − V0 ) 6= sign(V2 − V1 )},
c6 = {sign(Vn − Vn−1 ) 6= sign(Vn−1 − Vn−2 )}, c7 = {sign(Vtp − Vtp−1 ) =
−sign(Vtp+1 −Vtp )} and c8 = {min{|Vtp −V1 |, |Vtp −Vn−1 |} ≥ 20µV }. These two
sets form the complete set of constraints of the pattern CPwave = {c1 , . . . , c8 }.
Once a set of ECG samples has satisfied these constraints, they support the
observation of a wave: owave = hqwave , (a, vp, ttp ), tb , te i. The values of tb and
te are completely determined by the constraints c2 and c3 , while the observation
procedure wave observation() provides a value for the attributes as follows:
vp = sign(Vtp − V1 ), a = max{|Vtp − V1 |, |Vtp − Vn−1 |}, and ttp = tb + tp, where
tp = arg mink {Vk |1 ≤ k ≤ n − 1}, if V1 < V0 , or tp = arg maxk {Vk |1 ≤ k ≤
n − 1}, if V1 > V0 .
3.3. Abstraction grammars
According to the definition, an abstraction pattern is defined over a fixed
set of evidence findings MP . In general, however, an abstraction involves an
undetermined number of pieces of evidence -in the case of an ECG wave, the
number of samples-. Hence we provide a procedure for dynamically generating
abstraction patterns, based on formal language theory. The set Q of observables
can be considered as an alphabet. Given an alphabet Q, the special symbols ∅
(empty set), and λ (empty string), and the operators | (union), · (concatenation),
and ∗ (Kleene closure), a formal grammar G denotes a pattern of symbols of
the alphabet, describing a language L(G) ⊆ Q∗ as a subset of the set of possible
strings of symbols of the alphabet.
Let Gap be the class of formal grammars of abstraction patterns. An abstraction grammar G ∈ Gap is syntactically defined as a tuple (VN , VT , H, R).
11

For the production rules in R the expressiveness of right-linear grammars is
adopted [23]:
H → qD
D → qF | q | λ
H is the initial symbol of the grammar, and this plays the role of the hypothesis guessed by the patterns generated by G. VN is the set of non-terminal
symbols of the grammar, satisfying H ∈ VN , although H cannot be found on the
right-hand side of any production rule, since a hypothesis cannot be abstracted
by itself. VT is the set of terminal symbols of the grammar, representing the set
of observables QG ⊆ Q that can be abstracted by the hypothesis.
Given a grammar G ∈ Gap , we devise a constructive method for generating
a set of abstraction patterns PG = {P1 , . . . , Pi , . . .}. Since a formal grammar
is simply a syntactic specification of a set of strings, every grammar G ∈ Gap
is semantically extended to an attribute grammar [1], embedded with a set of
actions to be performed in order to incrementally build an abstraction pattern by
the application of production rules. An abstraction grammar is represented as
G = ((VN , VT , H, R), B, BR), where B(α) associates each grammar symbol α ∈
VN ∪VT with a set of attributes, and BR(r) associates each rule r ∈ R with a set
of attribute computation rules. An abstraction grammar associates the following
attributes: i) P (attern), with each non-terminal symbol of the grammar; this
will be assigned an abstraction pattern; ii) A(bstracted), with each terminal
symbol corresponding to an observable q ∈ QG ; this allows us to assign each
finding either to the set AP or EP , depending on its value of true or false; iii)
C(onstraint), with each terminal symbol corresponding to an observable; this
will be assigned a set of constraints. There are proposals in the bibliography
dealing with different descriptions of Constraint Satisfaction Problems and their
semantic expression in different formalisms [2, 5, 12]. By explicitly specifying a
constraint as a relation a clear description is provided on its underlying meaning,
but this can lead to cumbersome knowledge representation processes. Multiple
mathematical conventions can concisely and conveniently describe a constraint
as a boolean-valued function over the variables of a set of observables. However,
we will focus on the result of applying a set of constraints among the variables
involved.
In the following, the set of attribute computation rules associated with the
grammar productions is specified to provide a formal method for building abstraction patterns P ∈ PGh from a grammar Gh ∈ Gap . PGh gathers the set
of abstraction patterns that share the same observable h as a hypothesis; thus,
these represent the different ways to conjecture h. Using this method, the application of every production incrementally adds a new observable as a finding
and a set of constraints between this finding and previous entities, as follows:

12

1. The initial production H → qD entails:
PH := hh, MH = ∅, CH = ∅, ΘH = ∅i
Cq := C(Ah , Thb , The , A1 , T1b , T1e )
Aq ∈ {true, f alse}
PD := hh, MD = MH ∪ {mq1 }, CD = CH ∪ Cq , ΘD (A1 , T1b , T1e )i
2. All the productions of the form D → qF entail:
PD := hh, MD , CD , ΘD (A1 , T1b , T1e , . . . , Ak , Tkb , Tke )i
b
e
Cq := C(Ah , Thb , The , A1 , . . . , Ak+1 , Tk+1
, Tk+1
)

Aq ∈ {true, f alse}
b
e
PF := hh, MF = MD ∪ {mqk+1 }, CF = CD ∪ Cq , ΘF (A1 , T1b , T1e , . . . , Ak+1 , Tk+1
, Tk+1
)i

3. Productions of the form D → q conclude the generation of a pattern
P ∈ PG h :
PD := hh, MD , CD , ΘD (A1 , T1b , T1e , . . . , Ak , Tkb , Tke )i
b
e
Cq := C(Ah , Thb , The , A1 , . . . , Ak+1 , Tk+1
, Tk+1
)

Aq ∈ {true, f alse}
b
e
P := hh, MP = MD ∪ {mqk+1 }, CP = CD ∪ Cq , ΘP (A1 , T1b , T1e , . . . , Ak+1 , Tk+1
, Tk+1
)i

4. Productions of the form D → λ also conclude the generation of a pattern:
PD := hh, MD , CD , ΘD (A1 , T1b , T1e , . . . , Ak , Tkb , Tke )i
P := PD
This constructive method enables the incremental addition of new constraints as new findings are included in the representation of the abstraction
pattern, providing a dynamic mechanism for knowledge assembly by language
generation. The final constraints in CP are obtained from the conjunction of the
constraints added at each step. Moreover, it is possible to design an adaptive
observation procedure as new evidence becomes available, since the observation
procedure may be different at each step.
In the case that no temporal constraints are attributed to a production, a
’hereafter’ temporal relationship will be assumed by default to exist between
the new finding and the set of previous findings. For instance, a production of
b
the form D → qF entails that CF = CP ∪ {Tib ≤ Tk+1
| mi ∈ MP }.
Hence, in the absence of any temporal constraint, an increasing temporal order among consecutive findings in every abstraction pattern is assumed. Moreover, every temporal constraint must be consistent with this temporal order.
According to the limitation imposed on observations of the same observable
which prevents two different observations from occurring at the same time, an
additional constraint is added on any two findings of the same observable, and
thus ∀mqi , mqj ∈ MPq , (Tie < Tjb ∨ Tje < Tib ).
13

Several examples of abstraction pattern grammars modeling common knowledge in electrocardiography are given below, in order to illustrate the expressiveness of the Gap grammars.
Example 3.5. The grammar GN = (VN , VT , H, R) is designed to generate an
abstraction pattern for a normal cardiac cycle, represented by the observable
qN , including the descriptions of common durations and intervals [46]. In this
grammar, VN = {H, D, E}, VT = {qP w , qQRS , qT w }, and R is given by:
H → qP w D

{PH := hqN ,MH =∅,CH =∅,ΘH =∅i,
b
CP w := {TN
=TPb w ; 50ms≤TPe w −TPb w ≤120ms},

AP w := true,
PD := hqN ,MD ={mP w },CD =CP w ,ΘD =∅i
}

D → qQRS E

{PD := hqN ,MD ={mP w },CD =CP w ,ΘD =∅i,
e
b
b
CQRS := {50ms≤TQRS
−TQRS
≤150ms; 100ms≤TQRS
−TPb w ≤210ms},

AQRS := true,
PE := hqN ,ME =MD ∪{mQRS },CE =CD ∪CQRS ,ΘE =∅i
}

E → qT w

{PE := hqN ,ME ={mP w ,mQRS },CE ,ΘE =∅i,
e
b
e
CT w := {80ms≤TTb w −TQRS
≤120ms; TTe w −TQRS
≤520ms; TN
=TTe w },

AT w := true,
P := hqN ,MP =ME ∪{mT w },CP =CE ∪CT w ,ΘP =∅i
}

This grammar generates a single abstraction pattern, which allows us to interpret
the sequence of a P wave, a QRS complex, and a T wave as the coordinated
contraction and relaxation of the heart muscle, from the atria to the ventricles.
Some additional temporal constraints are required and specified in the semantic
description of the production rules. In this case, an observation procedure Θ is
not necessary since the attributes of the hypothesis are completely determined
by the constraints in the grammar, and do not require additional calculus.
The next example shows the ability of an abstraction grammar to generate
abstraction patterns dynamically with an undefined number of findings.
Example 3.6. A bigeminy is a heart arrhythmia in which there is a continuous
alternation of long and short heart beats. Most often this is due to ectopic heart
beats occurring so frequently that there is one after each normal beat, typically
premature ventricular contractions (PVCs) [46]. For example, a normal beat
is followed shortly by a PVC, which is then followed by a pause. The normal
beat then returns, only to be followed by another PVC. The grammar GV B =
(VN , VT , H, R) generates a set of abstraction patterns for ventricular bigeminy,
where VN = {H, D, E, F }, VT = {qN , qV }, and R is given by:

14

H → qN D

{PH := hqV B ,MH =∅,CH =∅,ΘH =∅i,
CN := {TVb B =T1 },
AN := true,
PD := hqV B ,MD ={mN
1 },CD =CN ,ΘD =∅i
}

D → qV E

{PD := hqV B ,MD ={mN
1 },CD =CN ,ΘD =∅i,
CV := {200ms≤T2 −T1 ≤800ms},
AV := true,
PE := hqV B ,ME =MD ∪{mV
2 },CE =CD ∪CV ,ΘE =∅i
}

E → qN F

V
{PE := hqV B ,ME ={mN
1 ,...,mk−1 },CE ,ΘE =∅i,

CN := {1.5·200ms≤Tk −Tk−1 ≤4·800ms},
AN := true,
PF := hqV B ,MF =ME ∪{mN
k },CF =CE ∪CN ,ΘF =∅i
}

F → qV E

V
N
{PF := hqV B ,MF ={mN
1 ,m2 ,...,mk },CF ,ΘF =∅i,

CV := {200ms≤Tk+1 −Tk ≤800ms},
AV := true,
PE := hqV B ,ME =MF ∪{mV
k+1 },CE =CF ∪CV ,ΘF =∅i
}

F → qV

V
N
{PF := hqV B ,MF ={mN
1 ,m2 ,...,mn−1 },CF ,ΘF =∅i,

CV := {200ms≤Tn −Tn−1 ≤800ms; TVe B =Tn },
AV := true,
P := hqV B ,MP =MF ∪{mV
n },CP =CF ∪CV ,ΘP =∅i
}

For simplicity, we have referenced each N and V heart beat with a single
temporal variable. Thus Ti represents the time point of the ith heart beat, and
is a normal beat if i is odd, and a PVC if i is even. With the execution of
these production rules, an unbounded sequence of alternating normal and premature ventricular QRS complexes is generated, described above as ventricular
bigeminy. Note that in terms of the {N, V } symbols the GV B grammar is syntactically equivalent to the regular expression N V (N V )+ .
In this example, as in 3.5, an observation procedure ΘP is not necessary,
since the constraints in the grammar completely determine the temporal endpoints of the hypothesis and there are no more attributes to be valued. Figure 4
shows an example of a ventricular bigeminy pattern.
4. An interpretation framework
In this section, we define and characterize an interpretation problem. Informally, an interpretation problem arises from the availability of a set of initial
15

N

V

N

V

N

V

N

V

N

V

Figure 4: Example of ventricular bigeminy. [Source: MIT-BIH arrhythmia DB, recording:
106, between 25:06.350 and 25:16.850]

observations from a given system, and of domain knowledge formalized as a
set G = {Gq1 , . . . , Gqn } of Gap grammars. Every abstraction grammar Gh ∈ G
generates a set of abstraction patterns that share the same hypothesis h. The
whole set of abstraction patterns that can be generated by G is denoted by P.
Definition 7. Let Q be a set of observables and G a set of abstraction grammars. We say G induces an abstraction relation in Q × Q, denoted by qi qj
if and only if there exists an abstraction pattern P generated by some Gh ∈ G
such that:
1. qj = h
2. MPqi ∩ AP 6= ∅
3. qi + qi , where

+

is the transitive closure of

The relation qi qj is a sort of conjectural relation that allows us to conjecture the presence of qj from the observation of qi . The transitive closure of
the abstraction relation is a strict partial order relation between the domain
observables, such that qi < qj ⇔ qi +qj ; that is, if and only if ∃qk0 , . . . , qkn ∈ Q
such that qk0 = qi , qkn = qj and for all m, with 0 ≤ m < n, it holds that
...
qkn = qj an abstraction
qkm qkm+1 . We denote by qi = qk0 qk1
sequence in n steps that allows the conjecture of qj from qi . This order relation
defines an abstraction hierarchy among the observables in Q. From the definition of a strict partial order, there must be at the base of this hierarchy at least
one observable we call q0 , corresponding in the domain of electrocardiography
to the digital signal.
Example 4.1. Let Q = {qP w , qQRS , qT w , qN , qV , qV B } and G = {GN , GV B },
containing the knowledge represented in examples 3.5 and 3.6. The derived abstraction relation states that qP w , qQRS , qT w qN , and qN , qV qV B . Intuitively,
we can see that this relation splits the observables into three abstraction levels:
the wave level, describing the activation/recovery of the different heart chambers; the heartbeat level, describing each cardiac cycle by its origin in the muscle
tissue; and the rhythm level, describing the dynamic behavior of the heart over
multiple cardiac cycles. These levels match those commonly used by experts in
electrocardiogram analysis [46].
It is worth noting that the abstraction relation is only established between
observables in the AP set. This provides flexibility in defining the evidence
forming the context of a pattern, as this may belong to different abstraction
levels.
16

Definition 8. We define an abstraction model as a tuple M = hQ, , Gi,
where Q is the set of domain observables, is an abstraction relation between
such observables, and G is the available knowledge as a set of abstraction grammars.
The successive application of the available abstraction grammars results in
a series of observations organized in a hierarchy of abstraction, according to the
order relation between observables as described above. We are able to define an
interpretation problem as follows.
Definition 9. We define an interpretation problem as a tuple IP = hO, Mi,
where O = (o1 , o2 , . . . , oi , . . .) is a sequence of observations requiring interpretation and M is an abstraction model of the domain.
It is worth mentioning that this definition of an abductive interpretation
problem differs from the common definition of an abductive diagnosis problem,
where the difference between normal and faulty behaviors is explicit, leading to
the role of faulty manifestations. Only when a faulty manifestation is detected is
the abductive process of diagnosis started. In contrast, in the present framework
all the observations have the same status, and the objective of the interpretation
process is to provide an interpretation of what is observed at the highest possible
abstraction level in terms of the underlying processes. As we will see later,
some observables may stand out amongst others regarding the efficiency of the
interpretation process, as salient features that can draw some sort of perceptual
attention.
As discussed above, any observable q ∈ QP can appear multiple times as
different pieces of evidence for an abstraction pattern P , in the form of findings
collected in the set MP . As a consequence, P can predict multiple observations
of the set O for a given observable q ∈ QP , each of these corresponding to
one of the findings of the set MP through a matching relation. This matching
relation is a matter of choice for the agent in charge of the interpretation task,
by selecting from the evidence the observation corresponding to each finding in
a given pattern.
Definition 10. Given an interpretation problem IP , a matching relation for
a pattern P ∈ P is an injective relation in MP × O, defined by mq  o if and
only if o = hq, v, tb , te i ∈ O(q) ⊆ O and mq = hψ, A, T b , T e i ∈ MP , such that
(A1 = v1 , . . . , Anq = vnq ), T b = tb and T e = te .
A matching relation makes an assignment of a set of observations to a set
of findings of a certain pattern, leading us to understand the interpretation
problem as a search within the available evidence for a valid assignment for the
constraints represented in an abstraction pattern.
From the notion of matching relation we can design a mechanism for abductively interpreting a subset of observations in O through the use of abstraction
patterns. Thus, a matching relation for a given pattern allows us to hypothesize new observations from previous ones, and to iteratively incorporate new
evidence into the interpretation by means of a hypothesize-and-test cycle. The
17

notion of abstraction hypothesis defines those conditions that a subset of observations must satisfy in order to be abstracted by a new observation, and makes
it possible to incrementally build an interpretation from the incorporation of
new evidence.
Definition 11. Given an interpretation problem IP , we define an abstraction
hypothesis as a tuple ~ = hoh , P, i, where P = hh, MP , CP , ΘP i ∈ P, ⊆
MP × O, and we denote O~ = codomain(), satisfying:
1. oh ∈ O(h).
2. oh = ΘP (O~ ).
3. CP (Ah , Thb , The , A1 , T1b , T1e , . . . , An , Tnb , Tne )|oh ,o1 ,...,on ∈O~ is satisfied.
These conditions entail: (1) an abstraction hypothesis guesses an observation
of the observable hypothesized by the pattern; (2) a new observation is obtained
from the application of the observation procedure to those observations being
assigned to the set of findings MP by the matching relation; and (3) the observations taking part in an abstraction hypothesis must satisfy those constraints
of the pattern whose variables are assigned a value by the observations.
Even though the matching relation is a matter of choice, and therefore a
conjecture in itself, some additional constraints may be considered as default
assumptions. An important default assumption in the abstraction of periodic
processes states that consecutive observations are related by taking part in the
same hypothesis, defining the basic period of the process. This assumption
functions as a sort of operative hypothesis of the abstraction task:
Default Assumption 2. (Basic periodicity) Periodic findings in an abstraction
pattern must be assigned consecutive observations by any matching relation:
∀mqi , mqi+1 ∈ MPq , mqi  oj ∧ q−succ(oj ) ∈ O~ ⇒ mqi+1  q−succ(oj )
This default assumption allows us to avoid certain combinations of abstraction hypotheses that, although formally correct, are meaningless from an interpretation point of view. For example, without the assumption of basic periodicity, a normal rhythm fragment might be abstracted by two alternating
bradycardia hypotheses, as shown in Figure 5.
obradycardia
1

obradycardia
2

Figure 5: Motivation for the assumption of basic periodicity. [Source: MIT-BIH arrhythmia
DB, recording: 103, between 00:40.700 and 00:51.200]

18

The set of observations that may be abstracted in an interpretation problem
IP is O(domain( )), that is, observations corresponding to observables involved
in the set of findings to be abstracted by some abstraction pattern. An abstraction hypothesis defines in the set of observations O a counterpart of the subsets
AP and EP of the set of findings MP of a pattern P , resulting from the selection of a set of observations O~ ⊆ O by means of a matching relation, satisfying
those requirements shown in the definition 11.
Definition 12. Given an interpretation problem IP and an abstraction hypothesis ~ = hoh , P, i, we define the following sets of observations:
• abstracted by(oh ) = {o ∈ O~ | mqi  o ∧ mqi ∈ AP }.
• environment of(oh ) = {o ∈ O~ | mqi  o ∧ mqi ∈ EP }.
• evidence of(oh ) = abstracted by(oh ) ∪ environment of(oh ).
We denote by abstracted by(oh ) the set of observations abstracted by oh
and which are somehow its constituents, while environment of(oh ) denotes
the evidential context of oh . We denote by evidence of(oh ) the set of all
observations supporting a specific hypothesis. Since the matching relation is
injective, it follows that abstracted by(oh ) ∩ environment of(oh ) = ∅.
The definition of these sets can be generalized to include as arguments a set of
observations O = {oh1 , ..., ohm } from a set of abstraction hypotheses ~1 , ..., ~m :
S
• abstracted by(O) = oh ∈O abstracted by(oh )
S
• environment of(O) = oh ∈O environment of(oh ).
S
• evidence of(O) = oh ∈O evidence of(oh ).
As a result of an abstraction hypothesis, a new observation oh is generated
which can be included in the set of domain observations, so that O = O ∪ {oh }.
In this way, an interpretation can be incrementally built from the observations,
by means of the aggregation of abstraction hypotheses.
Definition 13. Given an interpretation problem IP , an interpretation is
defined as a set of abstraction hypotheses I = {~1 , . . . , ~m }.
An interpretation can be rewritten as I = hOI , PI , I i, where OI = {oh1 , . . .
, ohm } is the set of observations guessed by performing multiple abstraction
hypotheses; PI = {P1 , . . . , Pm } is the set of abstraction patterns used in the
interpretation; and I =~1 ∪ . . . ∪ ~m ⊆ (M1 ∪ . . . ∪ Mm ) × O is the global
matching relation. We should note that the global matching relation I is
not necessarily injective, since some observations may simultaneously belong to
both the abstracted by() and environment of() sets of different observations.
From a given interpretation problem IP , multiple interpretations can be
abductively proposed through different sets of abstraction hypotheses. Indeed,
the definition of interpretation is actually weak, since even an empty set I = ∅
19

is formally a valid interpretation. Thus, we need additional criteria in order
to select the solution to the interpretation problem as the best choice among
different possibilities [33].
Definition 14. Given an interpretation problem IP , an interpretation I is a
cover of IP if the set of observations to be interpreted O(domain( )) ⊆ O is
included in the set of observations abstracted by I, that is, O(domain( )) ⊆
abstracted by(OI ).
Definition 15. Given an interpretation problem IP , two different abstraction
hypotheses ~ and ~0 of the mutually exclusive observables qh and qh0 are alternative hypotheses if and only if abstracted by(oh ) ∩ abstracted by(oh0 ) 6=
∅.
Example 4.2. A ventricular trigeminy is an infrequent arrhythmia very similar
to ventricular bigeminy, except that the ectopic heart beats occur after every pair
of normal beats instead of after each one. The grammar for hypothesizing a
ventricular trigeminy qV T would therefore be very similar to that described in
example 3.6, with the difference that each qV finding would appear after every
pair of qN findings. These two processes are mutually exclusive, insofar as the
heart can develop just one of these activation patterns at a given time. For this
reason, in the event of an observation of qV , this may be abstracted by either a
qV B or a qV T hypothesis, but never by both simultaneously.
Definition 16. Given an interpretation problem IP , a cover I for IP is exclusive if and only if it contains no alternative hypotheses.
Thus, two or more different hypotheses of mutually exclusive observables
abstracted from the same observation will be incompatible in the same interpretation, since inferring both a statement and its negation is logically prevented,
and therefore only one of them can be selected.
On the other hand, a parsimony criterion is required, in order to disambiguate the possible interpretations to select as the most plausible those of
which the complexity is minimum [33]. We translate this minimum complexity
in terms of minimal cardinality.
Definition 17. Given an interpretation problem IP , a cover I for IP is minimal, if and only if its cardinality is the smallest among all covers for IP .
Minimality introduces a parsimony criterion on hypothesis generation, promoting temporally maximal hypotheses, that is, those hypotheses of a larger
scope rather than multiple equivalent hypotheses of smaller scope. For example,
consider an abstraction pattern that allows the conjecture of a regular cardiac
rhythm from the presence of three or more consecutive heart beats. Without a
parsimony criterion, a sequence of nine consecutive beats could be abstracted
by up to three consecutive rhythm observations, even when a single rhythm
observation would be sufficient and better.
Definition 18. The solution of an interpretation problem IP is the set of all
minimal and exclusive covers of IP .
20

This definition of solution is very conservative and has limited practical
value, since the usual objective is to obtain a small set of interpretations explaining what has been observed (and ideally only a single one). However, it
allows us to characterize the problem in terms of complexity. Abduction has
been formulated under different frameworks according to the task to be addressed, but has always been found an intractable problem in the general case
[24]. The next theorem proves that an interpretation problem is also an intractable problem.
Theorem 1. Finding the solution to an interpretation problem is NP-hard.
Proof: We will provide a polynomial-time reduction of the well-known set covering problem to an interpretation problem. Given a set of elements U =
{u1 , . . . , um } and a set S of subsets of U , a cover is a set C ⊆ S of subsets
of S whose union is U . In terms of complexity analysis, two different problems
of interest are identified:
• A set covering decision problem, stating that given a pair (U, S) and an
integer k the question is whether there is a set covering of size k or less.
This decision version of set covering is NP-complete.
• A set covering optimization problem, stating that given a pair (U, S) the
task is to find a set covering that uses the fewest sets. This optimization
version of set covering is NP-hard.
We will therefore reduce the set covering problem to an interpretation problem
by means of a polynomial-time function ϕ. Thus, we shall prove that ϕ(U, S)
is an interpretation problem, and there is a set covering of ϕ(U, S) of size k or
less if and only if there is a set covering of U in S of size k or less.
Given a pair (U, S), let ϕ(U, S) = hO, Mi where:
1. O = U = {u1 , . . . , um }, such that ui = hq, true, ii and q = hψ, present, T i.
2. M = hQ, , Pi, such that domain( ) = q.
3. ∀s = {ui1 , . . . , uin } ∈ S, ∃P ∈ P, being P = hqP , MP , CP , ΘP i, where:
• q

qP and P 6= P 0 ⇒ qP 6= qP 0 .

• MP = AP = MPq = {mq1 = hψ, present1 , T1 i, . . . , mqn }.
Vn
• CP = { k=1 Tk = k; Thb = min{Tk }; The = max{Tk }}.
Vn
• presentP = ΘP (mq1 , . . . , mqn ) = k=1 presentk .
Thus, ϕ(U, S) is an interpretation problem according to this definition. On the
other hand, ϕ(U, S) can be built in polynomial time. In addition, for all s ∈ S
there exists an abstraction hypothesis ~ = hoh , P, i such that:
1. oh = hh, true, minui ∈s {i}, maxui ∈s {i}i.
2. ui ∈ s ⇒ ui ∈ codomain().
3.  provides a valid assignment, since the set of observations satisfying
ΘP = true also satisfies the constraints in CP .
21

Since each abstraction hypothesis involves a different abstraction pattern
there are no alternative hypotheses in any interpretation of ϕ(U, S).
Suppose there is a set covering C ⊆ S of U of size k or less. For all u ∈ U
there exists ci ∈ C − {∅} such that u ∈ ci and, by the above construction, there
) = {u ∈ codomain(~i )} =
exists ~i ∈ I such that abstracted by(ohS
i
S {u ∈
ci } = ci , and therefore, O(domain( )) ⊆ ~i ∈I abstracted by(ohi ) = i ci =
C. That is, the set of abstraction hypotheses I is an exclusive cover of the
interpretation problem ϕ(U, S) of size k or less.
Following the same reasoning as for the set covering optimization problem,
finding a minimal and a exclusive cover of an interpretation problem ϕ(U, S) is
NP-hard, since we can use the solution of this problem to check whether there
is an exclusive cover of the interpretation problem of size k or less, and this has
been proven above to be NP-complete. 
5. Solving an interpretation problem: A heuristic search approach
The solution set for an interpretation problem IP consists of all exclusive
covers of IP having the minimum possible number of abstraction hypotheses.
Obtaining this solution set can be stated as a search on the set of interpretations of IP . The major source of complexity of searching for a solution is the
local selection, from the available evidence in O, of the most appropriate matching relation for a number of abstraction hypotheses that can globally shape a
minimal and exclusive cover of IP .
Nevertheless, the whole concept of solution must be revised in practical
terms, due to the intractability of the task and the incompleteness of the abstraction model, that is, of the available knowledge. Indeed, we assume that
any realistic abstraction model can hardly provide a cover for every possible
interpretation problem. Hence the objective should shift from searching for a
solution to searching for an approximate solution.
Certain principles applicable to the interpretation problem can be exploited
in order to approach a solution in an iterative way, bounding the combinatorial
complexity of the search. These principles can be stated as a set of heuristics
that make it possible to evaluate and discriminate some interpretations against
others from the same base evidence:
• A coverage principle, which states the preference for interpretations explaining more initial observations.
• A simplicity principle, which states the preference for interpretations with
fewer abstraction hypotheses.
• An abstraction principle, which states the preference for interpretations
involving higher abstraction levels.
• A predictability principle, which states the preference for interpretations
that properly predict future evidence.

22

The coverage and simplicity principles are used to define a cost measure
for the heuristic search process [14], while the abstraction and predictability
principles are used to guide the reasoning process, in an attempt to emulate the
same shortcuts used by humans.
Given an interpretation problem IP , a heuristic vector for a certain interpretation I can be defined to guide the search, as (I) = (1 − ς(I), κ(I)), where
ς(I) = |abstracted by(OI )|/|O(domain( ))| is the covering ratio of I, and
κ(I) = |OI | is the complexity of I. The main goal of the search strategy is to
approach a solution with a maximum covering ratio and a minimum complexity,
which is equivalent to the minimization of the heuristic vector. The covering
ratio will be considered the primary heuristic, and complexity will be considered
for ranking interpretations with the same covering ratio. The (I) heuristic is
intuitive and very easy to calculate, but as a counterpart it is a non-admissible
heuristic, since it is not monotone and may underestimate or overestimate the
true goal covering. Therefore optimality cannot be guaranteed and we require
an algorithm efficient with this type of heuristic. We propose the CONSTRUE()
algorithm, whose pseudocode is shown in Algorithm 1. This algorithm is a minor variation of the K-Best First Search algorithm [14], with partial expansion
to reduce the number of explored nodes.
Algorithm 1 CONSTRUE search algorithm.
1: function CONSTRUE(IP )
2:
var I0 = ∅
3:
var K = max(|{qj ∈ Q | qi qj , qi ∈ Q}|)
4:
set focus(I0 , o1 )
5:
var open = sorted([h(I0 ), I0 i])
6:
var closed = sorted([])
7:
while open 6= ∅ do
8:
for all I ∈ open[0 . . . K] do
9:
I 0 = next(get descendants(I))
10:
if I 0 is null then
11:
open = open − {h(I), Ii}
12:
closed = closed ∪ {h(I), Ii}
13:
else if ς(I 0 ) = 1.0 then
14:
return I 0
15:
else
16:
open = open ∪ {h(I 0 ), I 0 i}
17:
end if
18:
end for
19:
end while
20:
return min(closed)
21: end function

The CONSTRUE() algorithm takes as its input an interpretation problem IP ,
and returns the first interpretation found with full coverage, or the interpretation with the maximum covering ratio and minimum complexity if no covers
are found, using the abstraction and predictability principles in the searching
23

process. To do this, it manages two ordered lists of interpretations, named open
and closed. Each interpretation is annotated with the computed values of the
heuristic vector. The open list contains those partial interpretations that can
further evolve by (1) appending new hypotheses or (2) extending previously
conjectured hypotheses to subsume or predict new evidence. This open list is
initialized with the trivial interpretation I0 = ∅. The closed list contains those
interpretations that cannot explain more evidence.
At each iteration, the algorithm selects the K most promising interpretations
according to the heuristic vector (line 8), and partially expands each one of them
to obtain the next descendant node I 0 . If this node is a solution, then the process
ends by returning it (line 13), otherwise it is added to the open list. The partial
expansion ensures that the open list grows at each iteration by at most K new
nodes, in order to save memory. When a node cannot expand further, it is added
to the closed list (line 12), from which the solution is taken if no full coverages
are found (line 20).
The selection of a value for the K parameter depends on the problem at
hand. We select its value as K = max(|{qj ∈ Q | qi qj , qi ∈ Q}|), that is, as
the maximum number of observables that can be abstracted from any observable
qi . The intuition behind this choice is that at any point in the interpretation
process, and with the same heuristic values, the same chance is given to any
plausible abstraction hypothesis in order to explain a certain observation.
In order to expand the current set of interpretations, the GET DESCENDANTS() function relies on different reasoning modes, that is, different forms of
abduction and deduction, which are brought into play under the guidance of an
attentional mechanism. Since searching for a solution finally involves the election of a matching relation, both observations and findings should be included
in the scope of this mechanism. Hence, a focus of attention can be defined to
answer the following question: which is the next observation or finding to be
processed? The answer to this question takes the form of a hypothesize-and-test
cycle: if the attention focuses on an observation, then an abstraction hypothesis explaining this observation should be generated (hypothesize); however, if
the attention focuses on a finding predicted by some hypothesis, an observation
should be sought to match such finding (test). Thus, the interpretation problem
is solved by a reasoning strategy that progresses incrementally over time, coping with new evidence through the dynamic generation of abstraction patterns
from a finite number of abstraction grammars, and bounding the theoretical
complexity by a parsimony criterion.
To illustrate and motivate the reasoning modes implemented in building
interpretations and supporting the execution of the CONSTRUE() algorithm,
we use a simple, but complete, interpretation problem.
Example 5.1. Let Q = {qwave , qP w , qQRS , qT w , qN }, G = {Gw , GN , GT w }, where
Gw models the example 3.4, GN is described in example 3.5, and GT w =
({H, D}, {qQRS , qwave }, H, R) describes the knowledge to conjecture a T wave
with the following rules:

24

H → qQRS D

{PH := hqT w ,MH =∅,CH =∅,ΘH =∅i,
e
b
CQRS := {80ms≤TTb w −TQRS
≤120ms; TTe w −TQRS
≤520ms},

AQRS := f alse,
PD := hqT w ,MD ={mQRS },CD =CQRS ,ΘD =∅i
}

D → qwave

{PD := hqT w ,MD ={mQRS },CD =CQRS ,ΘD =∅i,
b
e
Cwave := {TTb w =Twave
; TTe w =Twave
; max(diff(sig[mwave ])≤0.7·max(diff(sig[mQRS ]))},

Awave := true,
b
e
b
e
,TQRS
,Twave
,Twave
)i
P := hqT w ,MP =MD ∪{mwave },CP =CD ∪Cwave ,ΘP =Tw delin(TQRS
}

This grammar hypothesizes the observation of a T wave from a wave appearing shortly after the observation of a QRS complex, requiring a significant
decrease in the maximum slope of the signal (in the constraint definition Cwave ,
the expression “max(diff(sig[m])” stands for the maximum absolute value of the
e
b
). The observation procedure of
and Tm
derivative of the ECG signal between Tm
the generated pattern is denoted as Tw delin(), and may be any of the methods
described in the literature for the delineation of T waves, such as in [26].
In addition to the Pwave pattern generated by Gw and detailed in example 3.4,
GN and GT w generate the following abstraction patterns:
PN = hqN , APN = {mP w , mQRS , mT w } ∪ EPN = ∅, CPN , ΘPN = ∅i
PT w = hqT w , APT w = {mwave } ∪ EPT w = {mQRS }, CQRS ∪ Cwave , Tw delin()i
Finally, let O = {owave
= hqwave , ∅, 0.300, 0.403i, owave
= hqwave , ∅, 0.463,
1
2
Pw
0.549i, o
= hqP w , ∅, 0.300, 0.403i, oQRS = hqQRS , ∅, 0.463, 0.549i} be a set of
initial observations including a P wave and a QRS complex abstracting two wave
observations located at specific time points.
Given this interpretation problem, Figure 6 shows the starting point for the
interpretation, where the root of the interpretation process is the trivial interpretation I0 , and the attention is focused on the first observation. The sequence
of reasoning steps towards the resolution of this interpretation problem will be
explained in the following subsections.
5.1. Focus of attention
The focus of attention is modeled as a stack; thus, once the focus is set
on a particular observation (or finding), any observation that was previously
under focus will not return to be focused on until the reasoning process on the
current observation is finished. Algorithm 2 shows how the different reasoning
modes are invoked based on the content of the focus of attention, resulting in a
hypothesize-and-test cycle.
Lines 4-8 generate the descendants of an interpretation I when there is an
observation at the top of the stack. These descendants are the result of two
possible reasoning modes: the deduction of new findings, performed by the

25

Algorithm 2 Method for obtaining the descendants of an interpretation using different reasoning modes based on the content of the focus of attention.
1: function get descendants(I)
2:
var f ocus = get focus(I).top()
3:
var desc = ∅
4:
if is observation(f ocus) then
5:
if f ocus = oh | ~ ∈ I then
6:
desc = deduce(I, f ocus)
7:
end if
8:
desc = desc ∪ abduce(I, f ocus) ∪ advance(I, f ocus)
9:
else if is finding(f ocus) then
10:
desc = subsume(I, f ocus) ∪ predict(I, f ocus)
11:
end if
12:
return desc
13: end function

DEDUCE() function, provided that the observation being focused on is an ab-

straction hypothesis; and the abduction of a new hypothesis explaining the
observation being focused on, performed by the ABDUCE() function. A last
descendant is obtained using the ADVANCE() function, which simply restores
the previous focus of attention by means of a POP() operation. If the focus is
then empty, ADVANCE() inserts the next observation to explain, which may be
selected by temporal order in the general case, or by some domain-dependent
saliency criterion to prioritize certain observations over others. By removing the
observation at the top of the focus of attention, the ADVANCE() function sets
aside that observation as unintelligible in the current interpretation, according
to the available knowledge.
If the top of the stack contains a finding, then Algorithm 2 obtains the
descendants of the interpretation from the SUBSUME() and PREDICT() functions (line 10). The first of these functions looks for an existing observation
satisfying the constraints on the finding focused on, while the second makes
predictions about observables that have not yet been observed. All of these reasoning modes are described separately and detailed below; we will illustrate how
the CONSTRUE() algorithm combines these in order to solve the interpretation
problem in Example 5.1.
5.2. Building an interpretation: Abduction
Algorithm 3 enables the abductive generation of new abstraction hypotheses. It is applied when the attention is focused on an observation that can
be abstracted by some abstraction pattern, producing a new observation at a
higher level of abstraction.
The result of ABDUCE() is a set of interpretations I 0 , each one adding a new
abstraction hypothesis with respect to the parent interpretation I. To generate
these hypotheses, we iterate through those grammars that can make a conjecture from the observation oi under focus (line 3). Then, for each grammar, each
production including the corresponding observable q(oi ) (line 4) initializes an
26

Algorithm 3 Moving forward an interpretation through abduction.
1: function abduce(I, oi )
2:
var desc = ∅
3:
for all Gh = hVN , VT , H, Ri ∈ G | q(oi ) h do
4:
for all (U → qV ) ∈ R | q(oi ) is a q ∧ Aq = true do
5:
PV = hh, MV = {mq }, CV , ΘV i
6:
~ = hoh , PV , ~ = {mq  oi }i
7:
L~ = [(U → qV )]; B~ = U ; E~ = V
8:
I 0 = hOI ∪ {oh }, PI ∪ {PV }, I ∪ ~ i
9:
O = O ∪ {oh }
10:
get focus(I 0 ).pop()
11:
get focus(I 0 ).push(oh )
12:
desc = desc ∪ {I 0 }
13:
end for
14:
end for
15:
return desc
16: end function

abstraction pattern with a single finding of this observable (line 5), and a new
hypothesis is conjectured with a matching relation involving both the observation under focus and the finding (line 6). A list structure L~ and two additional
variables B~ and E~ are initialized to trace the sequence of productions used to
generate the findings in the abstraction pattern; these will play an important
role in subsequent reasoning steps (line 7). Finally the new hypothesis opens a
new interpretation (lines 8-9) focused on this hypothesis (line 11).
In this way, the ABDUCE() function implements, from a single piece of evidence, the hypothesize step of the hypothesize-and-test cycle. Below we explain
the reasoning modes involved in the test step of the cycle.
Example 5.2. Let us consider the interpretation problem set out in example 5.1
and the interpretation I0 shown in Figure 6. According to Algorithm 2, the ABDUCE() function is used to move forward the interpretation, since the focus
of attention points to an observation oP w . The abstraction pattern that supports this operation is PN , and a matching relation is established with the mP w
finding. As a result, the following hypothesis is generated:
~1 = hoN , PN , {mP w  oP w }i
Figure 6 shows the result of this reasoning process, in a new interpretation
called I1 . Note that the focus of attention has been moved to the newly created
hypothesis (lines 10-11 of the ABDUCE() function).
5.3. Building an interpretation: Deduction
This reasoning mode is applied when the attention is focused on an observation oh previously conjectured as part of an abstraction hypothesis ~ (see Algorithm 4). The DEDUCE() function takes the evidence that has led to conjecture
oh and tries to extend it with new findings which can be expected, i.e., deduced,
27

Algorithm 4 Moving forward an interpretation through the deduction of new findings.
1: function deduce(I, oh )
2:
var desc = ∅
3:
if B~ 6= H then
4:
for all (X → qB~ ) ∈ R do
5:
PB~ = hh, MB~ = {mq }, CB~ , ΘB~ i
6:
for all (U → q 0 V ) ∈ L~ do
0

7:
PV = hh, MU ∪ {mq }, CU ∪ CV , ΘV i
8:
end for
9:
~ = hoh , PE~ , ~ i
10:
I 0 = hOI , PI ∪ {PE~ }, I i
11:
insert(L~ , (X → qB~ ), begin); B~ = X
12:
get focus(I 0 ).push(mq )
13:
desc = desc ∪ {I 0 }
14:
end for
15:
else
16:
for all (E~ → qX) ∈ R do
17:
PX = hh, ME~ ∪ {mq }, CE~ ∪ CX , ΘX i
18:
~ = hoh , PX , ~ i
19:
I 0 = hOI , PI \ {PE~ } ∪ {PX }, I i
20:
insert(L~ , (E~ → qX), end); E~ = X
21:
get focus(I 0 ).push(mq )
22:
desc = desc ∪ {I 0 }
23:
end for
24:
end if
25:
return desc
26: end function

from the abstraction grammar Gh used to guess the observation. The key point
is that this deduction process follows an iterative procedure, as the corresponding abstraction pattern is dynamically generated from the grammar. Hence the
DEDUCE() function aims to extend a partial matching relation by providing the
next finding to be tested, as part of the test step of the hypothesize-and-test
cycle.
Since the first finding leading to conjecture oh does not necessarily appear at
the beginning of the grammar description, the corresponding abstraction pattern
will not, in general, be generated incrementally from the first production of the
grammar. Taking as a starting point the production used to conjecture oh (line 4
in Algorithm 3), the goal is to add a new finding by applying a new production
at both sides, towards the beginning and the end of the grammar, using the
information in the L~ list. The B~ variable represents the non-terminal at the
left-hand side of the first production in L~ , while E~ represents the non-terminal
at the right-hand side of the last production in L~ . Hence, this list has the form
L~ = [(B~ → q 0 V 0 ), (V 0 → q 00 V 00 ), . . . , (V 0n−1 → q 0n E~ )]. In case L~ is empty,
both variables B~ and E~ represent the H non-terminal. With this information
the sequence of findings supporting the hypothesis ~ can be updated in two

28

opposite directions:
• Towards the beginning of the grammar (lines 3-14): we explore the set
of observables that may occur before the first finding according to the
productions of the grammar (line 4), and a new finding is deduced for
each of these in different descendant interpretations. A new pattern PB~
associated with the B~ non-terminal is initialized with the new finding
(line 5), and by moving along the sequence of productions generating the
previous set of findings (lines 6-8) the pattern associated to the rightmost non-terminal PE~ is updated with a new set of findings containing
mq . Consequently, the hypothesis and the interpretation are also updated
(lines 9 and 10), and the applied production is inserted at the beginning
of L~ (line 11). Finally the newly deduced finding is focused on (line 12).
• Towards the end of the grammar (lines 15-23): for each one of the observables that may occur after the last finding, a new finding mq is deduced,
expanding the abstraction pattern associated with the new rightmost nonterminal X. After updating the hypothesis ~, the previous pattern PE~
in the resulting interpretation I 0 is replaced by the new one, PX , and the
applied production is inserted at the end of L~ . Finally, the new finding
is focused on (line 21).
Example 5.3. Let us consider the interpretation problem set out in example 5.1
and the interpretation I1 shown in Figure 6. Remember that the grammar used
to generate the hypothesis in the focus of attention, GN , has the following form:
H → qP w D
D → qQRS E
E → qT w
In this situation, it is possible to deduce new findings from the oN hypothesis.
Following Algorithm 3 we can check that B~ = H and E~ = D, since the only
finding in the matching relation is mP w . Deduction then has to be performed
after this last finding, using the production D → qQRS E. After constraint checking, the resulting finding is as follows:
b
e
mqn+1 = mQRS = hqQRS , ∅, TQRS
∈ [0.400, 0.520], TQRS
∈ [0.450, 0.660]i

Figure 6 illustrates the outcome of this reasoning process and the uncertainty
in the temporal limits of the predicted finding, which is now focused on in the
interpretation I2 .
5.4. Building an interpretation: Subsumption
Subsumption is performed when the attention is focused on a finding previously deduced from some abstraction grammar (see Algorithm 5). This reasoning mode avoids the generation of a new hypothesis for every piece of available
evidence if it can be explained by a previous hypothesis. The SUBSUME()
29

function explores the set of observations O and selects those consistent with
the constraints on the finding in the focus of attention (line 3), expanding the
matching relation of the corresponding hypothesis in different descendant interpretations (line 4). The focus of attention is then restored to its previous state
(line 5), allowing the deduction of new findings from the same hypothesis. The
SUBSUME() function clearly enforces the simplicity principle.
Algorithm 5 Moving forward an interpretation through subsumption.
1: function subsume(I, mi )
2:
var desc = ∅
3:
for all oj ∈ O | mi  oj do
4:
I 0 = hOI , PI , I ∪ {mi  oj }i
5:
get focus(I 0 ).pop(mi )
6:
desc = desc ∪ {I 0 }
7:
end for
8:
return desc
9: end function

Example 5.4. Let us consider the interpretation I2 shown in Figure 6. If we
apply the subsumption procedure, it is possible to set a matching relation between oQRS and mQRS , since this observation satisfies all the constraints on
the finding. The result is shown in the interpretation I3 . Note that the uncertainty in the end time of the oN hypothesis is now reduced after the matching,
having TNe ∈ [0.631, 1.030]. Following this, the attention focuses once again on
this hypothesis, and a new deduction operation may therefore be performed.
5.5. Building an interpretation: Prediction
This reasoning mode is also performed when the attention is focused on a
finding deduced from some abstraction grammar (see Algorithm 6). In this case,
if a finding previously deduced has not yet been observed, it will be predicted.
The goal of the PREDICT() function is to conjecture a new observation to
match the focused finding. For this, the abstraction model is explored and those
grammars whose hypothesized observable is more specific than the predicted observable are selected (line 3). Then, a new pattern is initialized with no evidence
supporting it, and a new abstraction hypothesis with an empty matching relation is generated (lines 4-5). Finally, the attention focuses on the observation
being guessed (lines 9-10) to enable the DEDUCE() function to start a new test
step at a lower abstraction level. Since L~ is initialized as an empty list (line 6),
B~ and E~ point to the initial symbol of the grammar, and the corresponding
abstraction pattern will be generated only towards the end of the grammar.
Example 5.5. Starting from the I3 interpretation shown in Figure 6, the next
step we can take to move forward the interpretation is a new deduction on the
oN hypothesis, generating a new finding mT w and leading to the I4 interpretation. Since there is no available observation of the T wave, a matching with
this new finding mT w cannot be made by the SUBSUME() function, thus, the
30

Algorithm 6 Moving forward an interpretation through the prediction of nonavailable evidence.
1: function predict(I, mi )
2:
var desc = ∅
3:
for all Gh = hVN , VT , H, Ri ∈ G | h is a q(mi ) do
4:
PH = hh, MH = ∅, CH = ∅, ΘH = ∅i
5:
~ = hoh , PH , ~ = ∅i
6:
L~ = ∅; B~ = E~ = H
7:
I 0 = hOI ∪ {oh }, PI ∪ {PH }, I ∪ {mi  oh }i
8:
O = O ∪ {oh }
9:
get focus(I 0 ).pop(mi )
10:
get focus(I 0 ).push(oh )
11:
desc = desc ∪ {I 0 }
12:
end for
13:
return desc
14: end function

only option for moving forward this interpretation is through prediction. Following the PREDICT() function, the GT w grammar can be selected, and a new
observation oT w can be conjectured, generating the I5 interpretation.
From I5 we can continue the deduction on the oT w hypothesis. If we ap0
ply the DEDUCE() function we obtain the mQRS finding from the environment,
shown in Figure 6 as I6 . To move on, we can apply the SUBSUME() function,
0
establishing the matching relation {mQRS  oQRS }. This leads to the I7 interpretation, in which the uncertainty on the oT w observation is reduced; however,
the evidence for the PT w pattern is not yet complete. A new DEDUCE() step is
necessary, which deduces the mwave necessary finding in the I8 interpretation.
This finding is also absent, so another PREDICT() step is required. In this last
step, the Pwave pattern can be applied to observe the deviation in the raw ECG
signal, generating the owave
observation and completing the necessary evidence
3
for the oT w observation and thus also for oN . Constraint solving assigns the
value of tbT w , teT w and teN , so the result is a cover of the initial interpretation
problem in which all the hypotheses have a necessary and sufficient set of evidence. This solution is depicted in I9 .
It is worth noting that in this example the global matching relation I is
0
not injective, since mQRS  oQRS and mQRS  oQRS . Also note that each
interpretation only generates one descendant; in a more complex scenario, however, the possibilities are numerous, and the responsibility of finding the proper
sequence of reasoning steps lies with the CONSTRUE() algorithm.
5.6. Improving the efficiency of interpretation through saliency
Starting a hypothesize-and-test cycle for every single sample is not feasible
for most of the time series interpretation problems. Still, many problems may
benefit from certain saliency features that can guide the attention focus to
some limited temporal fragments that can be easily interpretable. Thus, the

31

oN
oPw

oN

focus

focus

oPw

oQRS

oPw

(mwave) (mwave)
owave
owave
1
2

oQRS

(m ) (mwave)
owave
owave
1
2
wave

I0 = Initial evidence
mQRS
oN

(mPw)

ABDUCE(I0 , oP w )

I1 =

oN

oN

(m ) m ?

(m ) (m )

Pw

Pw

QRS

oN

focus

focus

oPw

oQRS

oPw

(m ) (m )
owave
owave
1
2
wave

(m ) (mwave)
owave
owave
1
2
SUBSUME(I2 , mQRS )

I3 =

oN
(mPw) (mQRS)

oN
oTw
oN

mTw?

focus

oQRS

oPw

(m ) (m )
owave
owave
1
2
wave

I5 =

(m ) (m )
mQRS’ ?
QRS

oQRS

I6 =

m ?

focus

focus

(m ) (m )
(mQRS’ )
Pw

oPw

oTw

DEDUCE(I5 , oT w )

I7 =

oQRS

(m ) (m )
owave
owave
1
2
wave

I8 =

wave

oQRS

mTw?
oTw

wave

0

SUBSUME(I6 , mQRS )

oN

oPw

QRS

(m ) (m )
owave
owave
1
2
wave

wave

(mPw) (mQRS)
(mQRS’ )

oTw

wave

oN
oTw
oN

Tw

(m ) (m )
owave
owave
1
2
wave

oQRS

PREDICT(I4 , mT w )

oN
Pw

oPw

mwave
oTw
oN

mTw?

(m ) (m )
owave
owave
1
2
wave

wave

DEDUCE(I3 , oN )

I4 =

focus

(mPw) (mQRS)

focus

oPw

mQRS’
oTw
oN

oQRS

wave

wave

DEDUCE(I1 , oN )

I2 =
mTw
oN

QRS

oN
oTw
oN

mTw?

focus

oTw
m

wave

(mPw) (mQRS)
(mQRS’ )
oPw

oQRS

(m ) (m )
owave
owave
1
2

?

wave

DEDUCE(I7 , oT w )

I9 =

wave

(mTw)
oTw
(mwave)
owave
3

PREDICT(I8 , mwave )

Figure 6: Sequence of reasoning steps for solving a simple interpretation problem.

32

interpretation of the whole time series can pivot on a reduced number of initial
observations, thereby speeding up the interpretation process.
A saliency-based attentional strategy can be devised from the definition of
abstraction patterns using a subset of their constraints as a coarse filter to
identify a set of plausible observations. For example, in the ECG interpretation
problem the most common strategy is to begin the analysis by considering a
reduced set of time points showing a significant slope in the signal, consistent
with the presence of QRS complexes [47]. This small set of evidence allows us
to focus the interpretation on the promising signal segments, in the same way
that a cardiologist focuses on the prominent peaks to start the analysis [46]. It
should be noted that this strategy is primarily concerned with the behavior of
the focus of attention, and that it does not discard the remaining, non-salient
observations, as these are included later in the interpretation by means of the
subsumption and prediction reasoning modes.
6. Some strengths of the framework
In this section we provide several practical examples which illustrate some of
the strengths of the proposed interpretation framework and its ability to tackle
with typical weaknesses of strategies based solely on a classification approach.
6.1. Avoiding a casuistry-based interpretation
In the time domain, classification-based recognition of multiple processes occurring concurrently usually leads to a casuistry-based proliferation of classes, in
which a new class is usually needed for each possible superposition of processes
in order to properly identify all situations. It is common to use a representation
in the transform domain, where certain regular processes are easily separable,
although at the expense of a cumbersome representation of the temporal information [30]. In contrast, in the present framework, the hypothesize-and-test
cycle aims to conjecture those hypotheses that best explain the available evidence, including simultaneous hypotheses in a natural way as long as these are
not mutually exclusive.
ECG interpretation provides some interesting examples of this type of problem. Atrial fibrillation, a common heart arrhythmia caused by the independent
and erratic contractions of the atrial muscle fibers, is characterized by an irregularly irregular heart rhythm [46]. Most of the classification techniques for the
identification of atrial fibrillation are based on the analysis of the time interval
between consecutive beats, and attempt to detect this irregularity [34]. These
techniques offer good results in those situations in which atrial fibrillation is
the only anomaly, but they fail to properly identify complex scenarios which go
beyond the distinction between atrial fibrillation and normal rhythm. In the
strip shown in Figure 7, obtained during a pilot study for the home follow-up of
patients with cardiac diseases [38], such a classifier would wrongly identify this
segment as an atrial fibrillation episode, since the observed rhythm variability
is consistent with the description of this arrhythmia. In contrast, the present

33

interpretation framework properly explains the first five beats as a sinus bradycardia, compatible with the presence of a premature ectopic beat in the second
position, followed by a trigeminy pattern during six beats, and finally another
ectopic beat with a morphology change. The reason to choose this interpretation, despite being more complex than the atrial fibrillation explanation, is
that it is able to abstract some of the small P waves before the QRS complexes,
increasing the interpretation coverage.

Figure 7: False atrial fibrillation episode. [Source: Mobiguide Project [38], private recording]

6.2. Coping with ignorance
Most of the classifiers solve a separability problem among classes, either by
learning from a training set or by eliciting prior knowledge, and these are implicitly based on the closed-world assumption, i.e., every new instance to be
classified is assigned to one of the predefined classes. Such classifiers may additionally include a ’reject’ option for all those instances that could be misclassified
since they appear too close to the classification boundaries [7, 17]. This reject
option is added as another possible answer expressing doubt. However, such
classifiers fail to classify new instances of unknown classes, since they cannot
express ignorance. An approach to this problem can be found in novelty detection proposals [35], which can detect when a new instance does not fit any of
the predefined classes as it substantially differs from those instances available
during training. Still, these are limited to a common feature representation for
every instance, hindering the identification of what is unintelligible from the
available knowledge.
The present framework provides an expression of ignorance as a common
result of the interpretation problem. As long as the abstraction model is incomplete, the non-coverage of some piece of evidence by any interpretation is
an expression of partial ignorance. In the extreme case, the trivial interpretation I0 may be a proper solution for an interpretation problem, expressing total
ignorance. Furthermore, abduction naturally includes the notion of ignorance
in the reasoning process, since any single piece of evidence can be sufficient to
guess an interpretation, and the hypothesize-and-test cycle can be understood
as a process of incremental addition of evidence against an initial state of ignorance, while being able to provide an interpretation at any time based on the
available evidence.
As an example, consider the interpretation problem illustrated in Figure 8.
Let the initial evidence be the set of QRS annotations obtained by a state-of-the
art detection algorithm [47]. In this short strip, the eighth and ninth annotations

34

correspond to false positives caused by the presence of noise. A classificationbased strategy processes these two annotations as true QRS complexes, and the
monotone nature of the reasoning prevents their possible refutation, probably
leading to beat misclassification and false arrhythmia detection, with errors
propagating onwards to the end of the processing. In contrast, the present
framework provides a single normal rhythm as the best interpretation, which
explains all but the two aforementioned annotations, which are ignored and
considered unintelligible in the available model. It is also worth noting the
ability of this framework to integrate the results of an available classifier as a
type of constraint specification in the interpretation cycle.

Figure 8: Unintelligible evidence due to noise. [Source: MIT-BIH arrhythmia DB, recording:
112, between 13:46.200 and 13:56.700]

6.3. Looking for missing evidence
The application of the classification paradigm to pattern detection also entails the potential risk of providing false negative results. In the worst case,
a false negative result may be interpreted by a decision maker as evidence of
absence, leading to interpretation errors with their subsequent costs, or in the
best case as an absence of evidence caused by the lack of a proper detection
instrument.
Even though abduction is fallible, and false negative results persist, the
hypothesize-and-test cycle involves a prediction mechanism that points to missing evidence that is expected and, moreover, estimates when it should appear.
Both the bottom-up and top-down processing performed in this cycle reinforces
confidence in the interpretation, since the semantics of any conclusion is widened
according to its explanatory power.
As an example, consider the interpretation problem illustrated in Figure 9.
The initial evidence is again a set of QRS annotations obtained by a stateof-the-art detection algorithm [47]. Note that the eighth beat has not been
annotated, due to a sudden decrease in the signal amplitude. This error can be
amended in the hypothesize-and-test cycle, since the normal rhythm hypothesis
that abstracts the first seven QRS annotations predicts the following QRS to
be in the position of the missing annotation, and the PREDICT() procedure can
look for this (e.g., checking an alternative set of constraints).
The capability of abduction to ignore or look for new evidence has been
tested with a simplified version of the present framework in the QRS detection
problem [43], leading to a statistically significant improvement over a state-ofthe art algorithm.

35

Figure 9: Missing evidence that may be discovered by prediction. [Source: MIT-BIH normal
sinus rhythm DB, recording: 18184, between 09:12:45.000 and 09:12:55.500]

6.4. Interpretability of the reasoning process and the results
The interpretability of a reasoning formalism, defined as the ability to understand and evaluate its conclusions, is an essential feature for achieving an
adequate confidence in decision making [31]. In this sense, there are a number
of classification methods with good interpretability; however, the methods that
typically offer the best performance belong to the so-called black box approaches.
The present interpretation framework is able to provide a justification of any
result in relation to the available model. Given any solution or partial solution
of an interpretation problem, the searching path up to I0 gives full details of all
the reasoning steps taken to this end, and any abstraction hypothesis can be
traced back to the information supporting it.
This interpretation framework is also able to answer the question of why a
certain hypothesis has been rejected or neglected at any reasoning step. This is
done by exploring the branches outside the path between I0 and the solution.
Since the K exploration parameter within the CONSTRUE() algorithm has been
chosen as the maximum number of hypotheses that may explain a given observable, it is possible to reproduce the reasoning steps taken in the conjecture of any
abstraction hypothesis, and to check why this did not succeed (non-satisfaction
of pattern constraints, lower coverage, etc.). This can be useful in building and
refining the knowledge base.
7. Experimental evaluation: beat labeling and arrhythmia detection
The interpretation of the electrocardiogram has served both as a challenge
and as an inspiration for the AI community almost since its inception, due to a
number of factors that can be summarized as: (1) the complexity of the physiological processes underlying what is observed; and (2) the absence of an accurate
model of the heart and the hardly formalizable knowledge that constitutes the
experience of the cardiologist. There are numerous problems falling within the
scope of ECG interpretation, the most relevant being heartbeat labeling [29].
We have tested the present framework by abductively identifying and measuring
a set of qualitative morphological and rhythm attributes for each heartbeat, and
using a rule-based classifier to assign a label to clusters of similar heartbeats [44].
It is noteworthy that an explicit representation of knowledge has been adopted,
namely the kind of knowledge that can be found in an ECG handbook. Table 1
reproduces the performance comparison between this approach and the most

36

Table 1: VEB and SVEB classification performance of the abductive approach and comparison
with the most relevant automatic and assisted methods of the state-of-the-art

Dataset

Method

VEB
Se
P+

SVEB
Se
P+

MIT-BIH Arrhythmia
DS1+DS2

Teijeiro et al. - Automatic 92.82 92.23 85.10 84.51
Llamedo et al. - Assisted
90±1 97±0 89±2 88±3
Kiranyaz et al. - Assisted
93.9
90.6
60.3
63.5
Ince et al. - Assisted
84.6
87.4
63.5
53.7
Llamedo et al. - Automatic 80±2 82±3 76±2 43±2

MIT-BIH Arrhythmia
DS2

Teijeiro et al. - Automatic 94.63 96.79 87.17
Llamedo et al. - Assisted
93±1 97±1 92±1
Kiranyaz et al. - Assisted
95.0
89.5
64.6
Chazal et al. - Assisted
93.4
97.0
94.0
Zhang et al. - Automatic
85.48 92.75 79.06
Llamedo et al. - Automatic 89±1 87±1 79±2
Chazal et al. - Automatic
77.7
81.9
75.9

83.98
90±3
62.1
62.5
35.98
46±2
38.5

relevant automatic and assisted approaches of the state-of-the art, using sensitivity and positive predictivity of ventricular and supraventricular ectopic beat
classes.
As it can be seen, this method significantly outperforms any other automatic
approaches in the state-of-the-art, and even improves most of the assisted approaches that require expert aid. The most remarkable improvement concerns
the classification of supraventricular ectopic beats, which are usually hard to
distinguish using only morphological features. The abductive interpretation in
multiple abstraction levels, including a rhythm description of signal, is what
enables a more precise classification of each individual heartbeat.
Furthermore, the abductive interpretation approach has been used for arrhythmia detection in short single-lead ECG records, focusing on atrial fibrillation [45]. The interpretation results are combined with machine learning
techniques to obtain an arrhythmia classifier, achieving the best score in the
2017 Physionet/CinC Challenge dataset and outperforming some of the most
popular techniques such as deep learning and random forests [8].
8. Discussion
A new model-based framework for time series interpretation is proposed.
This framework relies on some basic assumptions: (i) interpretation of the behavior of a system from the set of available observations is a sort of conjecturing,
and as such follows the logic of abduction; (ii) the interpretation task involves
both bottom-up and top-down processing of information along a set of abstraction levels; (iii) at the lower levels of abstraction, the interpretation task is a
form of precompiled knowledge-based pattern recognition; (iv) the interpretation task involves both the representation of time and reasoning about time and
along time.

37

Model-based representation in the present framework is based on the notion
of abstraction pattern, which defines an abstraction relation between observables
and provides the knowledge and methods to conjecture new observations from
previous ones. Let us deepen in both the backward and forward logical meaning
of an abstraction pattern, following a reasoning similar to that of [4]:
• Backward meaning. From the backward reading of an abstraction pattern P , a hypothesis h is a possible abstraction of m1 , . . . , mn , provided
that the constraints in CP hold. An abstraction pattern satisfies the compositionality principle of abductive reasoning, and hence an abstraction
hypothesis can be conjectured from a single piece of evidence, and new
pieces of evidence can be added later [16]. On the other hand, if there
are multiple ways of observing h by means of multiple patterns, and their
respective constraints are inconsistent with the evidence, we do not conclude ¬h, interpreted as failure to prove h; we will only conclude ¬h in all
those interpretations conjecturing an observation of a different h0 , where
h and h0 are mutually exclusive.
• Forward meaning. An abductive observation is built upon an archetypical
representation of a hypothesis h, creating an observation as an instance of
h by estimating, from the available evidence, its attribute values A and
its temporal location T b and T e by means of an observation procedure
ΘP . From a forward reading, assuming h is true, there is an observation
for each observable of the set m1 , . . . , mn such that the constraints in
CP hold. However, the estimated nature of abstraction does not usually
allow us to infer, from the observation of h, the same observations of
m1 , . . . , mn that have been abstracted into h. We must presume instead
that assuming h is true entails the occurrence of an observation for each
observable of m1 , . . . , mn , without necessarily entailing its attribute values
and its temporal location.
Both the forward and the backward meanings of an abstraction pattern support the incremental building of an interpretation in the present framework.
Thus, what initially was defined as a set covering problem of a time series fragment -a completely intractable problem as it moves away from a toy examplecan be feasibly solved if it is properly structured in a set of abstraction levels, on which four reasoning modes (abduction, deduction, subsumption and
prediction) can make a more efficient search of the best explanation under a
parsimony criterion. Moreover, this incremental reasoning primarily follows the
time direction, since the available knowledge is usually compiled in the form of
a set of processes that can be expected to be found in a certain sequence, which
underscores the anticipatory information contained in the evidence.
An abstraction model, built on a set of abstraction patterns, establishes a
causal responsibility for the behavior observed in a complex system [24]. This
responsibility is expressed in the language of processes: a process is said to be
observable if it is assumed that it causes a recognizable trace in the physical
quantity to be interpreted. This notion of causality is behind perception, i.e.,
38

concerned with the explanation of sensory data, in contrast with the notion of
causality in diagnosis, concerned with the explanation of abnormality [10].
Representing and reasoning about context is a relevant issue in model-based
diagnosis [4, 10, 33, 40]. A contextual observation is nothing more than another observation that need not be explained by a diagnosis. In most of the
bibliography, the distinction between these two roles must be defined beforehand. Several other works enable the same observation to play different roles
in different causal patterns, thus providing some general operations for expressing common changes made by the context in a diagnostic pattern [25, 32]. In
the present interpretation framework, an observation can either be part of the
evidence to be explained in a certain abstraction pattern, or can be part of the
environment in another abstraction pattern. Both types of observation play a
part in the hypothesize-and-test cycle, with the only difference that observations
of the environment of an abstraction pattern are not expected to be abstracted
by this pattern. Hence, observations of the environment are naturally included
in the deduction, subsumption and prediction modes of reasoning.
An important limitation of the present framework is its knowledge-intensive
nature, requiring a non-trivial elicitation of expert knowledge. It is worth exploring different possibilities for the inclusion of machine learning strategies,
both for the adaption and the definition of the knowledge base. A first approach may address the automatic adjustment of the initial constraints among
recurrent findings in abstraction grammars. In this manner, for example, temporal constraints between consecutive heartbeats in a normal rhythm abstraction
grammar could be adapted to the characteristics of the subject whose ECG is
being interpreted, allowing the identification of possible deviations from normality with greater sensitivity. On the other hand, the discovery of new abstraction
patterns and abstraction grammars by data mining methods appears as a key
challenge. In this regard, the CONSTRUE() algorithm should be extended by
designing an INDUCE() procedure aimed at conjecturing new observables after
an inductive process. To this end, new default assumptions should be made in
order to define those grammar structures that should rule the inductive process.
These grammar structures may lead to discovery new morphologies or rhythms
not previously included in the knowledge base.
The proposed framework formulates an interpretation problem as an abduction problem with constraints, targeted at finding a set of hypotheses covering
all the observations while satisfying a set of constraints on their attribute and
temporal values. Thus, consistency is the only criterion to evaluate the plausibility of a hypothesis, resulting in a true or false value, and any evoked hypothesis
(no matter how unusual it is) for which inconsistent evidence cannot be found is
considered as plausible and, consequently, it will be explored in the interpretation cycle. Even though this simple approach has provided remarkable results,
it can be expected that the inclusion of a hypothesis evaluation scheme, typically based on probability [33, 37] or possibility [13, 32] theories, will allow us
to better discriminate between plausible and implausible hypotheses, leading to
better explanations with fewer computational requirements.
The expressiveness of the present framework should also be enhanced to
39

support the representation of the absence of some piece of evidence, in the form
of negation, so that ¬q represents the absence of q. The exclusion relation is a
first approach to manage with the notion of absence in the hypothesize-and-test
cycle, since the occurrence of a process is negated by the concurrent occurrence
of any of the processes related to it by the exclusion relation. On the other hand,
an inhibitory relation can enable us to represent a certain process preventing
another from occurring under some temporal constraints, providing a method to
insert the prediction of the absence of some observable in the hypothesize-andtest cycle. Furthermore, other forms of interaction between processes, possibly
modifying the respective initial patterns of evidence, should be modeled.
Further efforts should be made to improve the efficiency of the interpretation
process. To this end, two main strategies are currently being explored. On the
one hand, the model structure is exploited to identify necessary and sufficient
conditions for every hypothesis to be conjectured; the necessary conditions avoid
the expansion of the hypotheses that can be ruled out because they are inconsistent with observations, while sufficient conditions avoid the construction of
redundant interpretations [9]. A different strategy entails additional restrictions
in the amount of computer memory and time needed to run the algorithm, resulting in a selective pruning of the node expansion while sacrificing optimality;
this strategy is similar to the one used in the K-Beam algorithm [14].
The CONSTRUE() algorithm is based on the assumption that all the evidence to be explained is available at the beginning of the interpretation task. A
new version of the algorithm should be provided to cope with a wide range of
problems, where the interpretation must be updated as new evidence becomes
available over time. Examples of such problems are continuous biosignal monitoring or plan execution monitoring [3]. At the emergence of a new piece of evidence, two reasoning modes may come into play triggered by the CONSTRUE()
algorithm: a new explanatory hypothesis can be conjectured by means of the
ABDUCE() procedure, or the evidence can be incorporated in an existing hypothesis by means of the SUBSUME() procedure. In this way, the incorporation
of new evidence over time is seamlessly integrated into the hypothesize-andtest cycle. Furthermore, to properly address these interpretation scenarios, the
heuristics used to guide the search must be updated to account for the timing
of the interpretation process, which will lead to the definition of a covering ratio
until time t, and a complexity until time t.
Implementation
With the aim of supporting reproducible research, the full source code of the
algorithms presented in this paper has been published under an Open Source
License1 , along with a knowledge base for the interpretation of the ECG signal
strips of all examples in this paper.
1 https://github.com/citiususc/construe

40

Acknowledgments
This work was supported by the Spanish Ministry of Economy and Competitiveness under project TIN2014-55183-R. T. Teijeiro was funded by an FPU
grant from the Spanish Ministry of Education (MEC) (ref. AP2010-1012).
References
[1] A.V. Aho, M.S. Lam, R. Sethi, and J.D. Ullman. Compilers: Principles,
Techniques and Tools. Pearson Education, Inc., 2006.
[2] S. Barro, R. Marı́n, J. Mira, and A. Patón. A model and a language for
the fuzzy representation and handling of time. Fuzzy Sets and Systems,
61:153–175, 1994.
[3] R. Barták, R. A. Morris, and K. B. Venable. An Introduction to ConstraintBased Temporal Reasoning. Synthesis Lectures on Artificial Intelligence
and Machine Learning, 8(1):1–121, feb 2014.
[4] V. Brusoni, L. Console, P. Terenziani, and D. Theseider Dupré. A spectrum
of definitions for temporal model-based diagnosis. Artificial Intelligence,
102(1):39–79, 1998.
[5] S. Chakravarty and Y. Shahar. CAPSUL: A constraint-based specification
of repeating patterns in time-oriented data. Annals of Mathematics and
Artificial Intelligence, 30:3–22, 2000.
[6] E. Charniak. Motivation analysis, abductive unification and nonmonotonic
equality. Artificial Intelligence, 34(3):275–295, 1989.
[7] C.K. Chow. On optimum recognition error and reject tradeoff. IEEE
Transaction on Information Theory, 16(1):41–46, 1970.
[8] G. Clifford, C. Liu, B. Moody, I. Silva, Q. Li, A. Johnson, and R. Mark.
AF Classification from a Short Single Lead ECG Recording: the PhysioNet
Computing in Cardiology Challenge. In Proceedings of the 2017 Computing
in Cardiology Conference (CinC), volume 47, 2017.
[9] L. Console, L. Portinale, and D. Theseider Dupré. Using compiled knowledge to guide and focus abductive diagnosis. IEEE Transactions on Knowledge and Data Engineering, 8(5):690–706, 1996.
[10] L. Console and P. Torasso. A spectrum of logical definitions of model-based
diagnosis. Computational Intelligence, 3(7):133–141, 1991.
[11] Working Party CSE. Recommendations for measurement standards in
quantitative electrocardiography. European Heart Journal, 6(10):815–825,
1985.
[12] R. Dechter. Constraint Processing. Morgan Kaufmann Publishers, 2003.
41

[13] D. Dubois and H. Prade. Fuzzy relation equations and causal reasoning.
Special Issue on ”Equations and Relations on Ordered Structures : Mathematical Aspects and Applications” (A. Di Nola, W. Pedrycz, S. Sessa,
eds.), Fuzzy Sets and Systems, 75:119–134, 1995.
[14] S. Edelkamp and S. Schrödl. Heuristic Search: Theory and Applications.
Morgan Kaufmann, 2011.
[15] D. Ferrucci, A. Levas, S. Bagchi, D. Gondek, and E.T. Mueller. Watson:
Beyond Jeopardy. Artificial Intelligence, 199–200:93–105, 2012.
[16] P. Flach. Abduction and induction: Syllogistic and inferential perspectives. In Abductive and Inductive Reasoning Workshop Notes, pages 31–35.
University of Bristol, 1996.
[17] G. Fumera, F. Roli, and G. Giacinto. Reject option with multiple thresholds. Pattern Recognition, (33):2099–2101, 2000.
[18] A. L. Goldberger et al. PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals. Circulation, 101(23):215–220, June 2000.
[19] I.J. Haimowitz and I.S. Kohane. Automated Trend Detection with Alternate Temporal Hypotheses. In Proceedings of the 13th International Joint
Conference of Artificial Intelligence, volume 1, pages 146–151, 1993.
[20] I.J. Haimowitz, P.P. Le, and I.S. Kohane. Clinical monitoring using
regression-based trend templates. Artificial Intelligence in Medicine,
7(6):473–496, 1995.
[21] C. Hartshorn et al. Collected papers of Charles Sanders Peirce. Harvard
University Press, 1931.
[22] J.R. Hobbs, M. Stickel, and P. Martin. Interpretation as abduction. Artificial Intelligence, 63:69–142, 1993.
[23] J. Hopcroft, R. Motwani, and J. Ullman. Introduction to automata theory,
languages and computation. Addison-Wesley, 2001.
[24] J.R. Josephson and S.G. Josephson. Abductive inference. Computation,
philosophy, technology. Cambridge University Press, 1994.
[25] J. M. Juárez, M. Campos, J. Palma, and R. Marı́n. Computing contextdependent temporal diagnosis in complex domains. Expert Systems with
Applications, 35(3):991–1010, 2008.
[26] P. Laguna, R. Jané, and P. Caminal. Automatic detection of wave boundaries in multilead ECG signals: validation with the CSE database. Computers and Biomedical Research, 27:45–60, 1994.

42

[27] C. Larizza, G. Bernuzzi, and M. Stefanelli. A general framework for building patient monitoring systems. In Proceedings of the 5th Conference on
Artificial intelligence in Medicine, pages 91–102, 1995.
[28] D. Litman and J. Allen. A plan recognition model for subdialogues in
conversation. Cognitive Science, 11:163–200, 1987.
[29] E. J. S. Luz, W. R. Schwartz, G. Cámara-Chávez, and D. Menotti. ECGbased Heartbeat Classification for Arrhythmia Detection: A Survey. Computer Methods and Programs in Biomedicine, 2016.
[30] F. Mörchen. Time series feature extraction for data mining using DWT and
DFT. Technical Report no. 33, Department of Mathematics and Computer
Science, University of Marburg, 2003.
[31] D. Nauck and R. Kruse. Obtaining interpretable fuzzy classification rules
from medical data. Artificial Intelligence in Medicine, 16(2):149–169, 1999.
[32] J. Palma, J. M. Juárez, M. Campos, and R. Marı́n. Fuzzy theory approach
for temporal model-based diagnosis: An application to medical domains.
Artificial Intelligence in Medicine, 38(2):197, 2006.
[33] Y. Peng and J.A. Reggia. Abductive inference models for diagnostic
problem-solving. Springer-Verlag, 1990.
[34] A. Petrenas, V. Marozas, and L. Sörnmo. Low-complexity detection of
atrial fibrillation in continuous long-term monitoring. Computers in biology
and medicine, 65:184–91, oct 2015.
[35] M.A.F. Pimentel, D.A. Clifton, L. Clifton, and L. Tarassenko. A review of
novelty detection. Signal Processing, (99):215–249, 2014.
[36] D. Poole. A methodology for using a default and abductive reasoning
system. International Journal of Intelligent Systems, 5(5):521–548, 1990.
[37] D. Poole. Learning, Bayesian Probability, Graphical Models, and Abduction. In Abduction and Induction: Essays on their Relation and Integration,
pages 153–168. Springer Netherlands, 2000.
[38] L. Sacchi, E. Parimbelli, S. Panzarasa, N. Viani, E. Rizzo, C. Napolitano,
R. Ioana Budasu, and S. Quaglini. Combining Decision Support SystemGenerated Recommendations with Interactive Guideline Visualization for
Better Informed Decisions. In Artificial Intelligence in Medicine, pages
337–341. Springer International Publishing, 2015.
[39] Y. Shahar. A framework for knowledge-based temporal abstraction. Artificial intelligence, 90(1–2):79–133, 1997.
[40] Y. Shahar. Dynamic temporal interpretation contexts for temporal abstraction. Annals of Mathematics and Artificial Intelligence, 22(1–2):159–192,
1998.
43

[41] Y. Shahar. Knowledge-based temporal interpolation. Journal of experimental and theoretical artificial intelligence, 11:123–144, 1999.
[42] Y. Shahar and M.A. Musen. Knowledge-based temporal abstraction in
clinical domains. Artificial Intelligence in Medicine, 8(3):267–298, 1996.
[43] T. Teijeiro, P. Félix, and J. Presedo. Using Temporal Abduction for Biosignal Interpretation: A Case Study on QRS Detection. In 2014 IEEE International Conference on Healthcare Informatics, pages 334–339, 2014.
[44] T. Teijeiro, P. Félix, J. Presedo, and D. Castro. Heartbeat classification
using abstract features from the abductive interpretation of the ECG. IEEE
Journal of Biomedical and Health Informatics, 2016.
[45] T. Teijeiro, C.A. Garcı́a, D. Castro, and P. Félix. Arrhythmia Classification
from the Abductive Interpretation of Short Single-Lead ECG Records. In
Proceedings of the 2017 Computing in Cardiology Conference (CinC), volume 47, 2017.
[46] Galen S. Wagner. Marriott’s Practical Electrocardiography. Wolters Kluwer
Health/Lippincott Williams & Wilkins, 11 edition, 2008.
[47] W. Zong, G.B. Moody, and D. Jiang. A robust open-source algorithm to
detect onset and duration of QRS complexes. In Computers in Cardiology,
pages 737–740, 2003.

44

