How to define abstraction models
This tutorial describes how new abstraction models can be defined so that the Construe algorithm can be used for the interpretation of different time series, beyond the electrocardiogram (ECG). As an example, the T wave abstraction pattern is used.
You should understand the terminology and formalism supporting the framework. It might be painful, but you really should read the main paper [1] to understand the intuition and ideas behind each concept.
Besides, currently the framework only supports abstraction models implemented in Python, so a proper knowledge of the language is required.
According to the definition [1], an abstraction model of a domain consists of a set of Abstraction Grammars defining an abstraction relation between a set of Observables. The first step is then to define a set of Observables for our domain.
The framework provides two base classes to define Observables: construe.model.observable.Observable and construe.model.observable.EventObservable. The first one represents observables whose observations have a certain duration, and EventObservable represents instantaneous observables. They define three attributes, all of them of the Variable type. A Variable may take a value that is an Interval, so we can represent uncertainty in the value of a given attribute. All three attributes are related to the temporal location of the observable:
-
start: Represents the beginning of the observable. -
time: Represents the reference time for the observable. It is usually equal to thestartattribute. -
end: Represents the end of the observable.
For EventObservable instances, all three attributes take always the same value.
The first step is then to define the set of observables for our problem, by subclassing the appropriate Observable base class. For example, to conjecture a T wave we require the observation of a leading environment QRS complex and a signal Deflection that is abstracted in the T wave hypothesis. These entities are defined as follows:
from construe.model import Observable
class TWave(Observable):
"""
Observable that represents a T Wave
Attributes
----------
amplitude:
Dictionary with the amplitude in mV of the T wave in each lead, indexed
by lead.
"""
def __init__(self):
super(TWave, self).__init__()
#The single reference will correspond to the start time
self.time = self.start
self.amplitude = {}
class QRS(Observable):
"""
Observable that represents a QRS complex
Attributes
----------
shape:
Dictionary with the shape of the QRS complex in each lead, indexed
by lead.
"""
def __init__(self):
super(QRS, self).__init__()
self.shape = {}
class Deflection(Observable):
"""
This class represents a signal deviation consistent with the electrical
activity of the cardiac muscle fibers. It is associated with a certain
energy level derived from the wavelet decomposition/reconstruction of the
signal.
"""
def __init__(self):
"""Creates a new Deflection instance, at level 0"""
super(Deflection, self).__init__()
#The single reference will correspond to the start variable
self.time = self.start
self.level = {}As you can see, an Observable may define new attributes to represent specific information.
The most important element in an abstraction model is the set of abstraction grammars generating the abstraction patterns that will support the hypothesize-and-test cycle implemented by the Construe algorithm. As defined in [1], an abstraction grammar is a right-linear formal attributed grammar, describing a sort of regular expression in the observables alphabet and allowing the description of temporal and value constraints between them.
To make it simpler the definition of grammars, they are described as the equivalent finite automaton, where non-terminals are replaced by states, and rules are described as transitions between states. For example, the grammar to describe the T wave abstraction pattern has the following form:
H = qTw → qQRS [c1] D
D → qDeflection [c2]
where c1 describes the constraints involving the QRS observation, and c2 describes the constraints involving the Deflection observation. The equivalent automaton has the following form:
where # means the observable is in the environment evidence EP and @ means the observable is in the abstracted evidence AP.
For the definition of abstraction grammars through their equivalent automata, the framework provides the construe.model.automata.PatternAutomata class. As a public API, this class provides the following add_transition() method:
def add_transition(self, istate = None, fstate = None, observable = None,
abstracted = ABSTRACTED, tconst = NULL_CONST,
gconst = NULL_CONST):
"""
Adds a new *Transition* to this automata.
Parameters
----------
istate:
Initial state of the transition.
fstate:
Final state of the transition.
observable:
Observable type that allows the transition.
abstracted:
Flag that indicates if the observation that allows the transition
should be considered as an Abstracted observation or an Environment
observation.
tconst:
Function that receives as a parameter the AbstractionPattern object,
and adds the temporal constraints introduced by this transition
with the rest of the variables of the pattern, including the
hypothesis. These constraints are added before the matching of the
predicted finding with an actual observation.
gconst:
Function that receives as a parameter the AbstractionPattern object,
and checks any additional constraint in the value of the
observations. These constraints are checked after the matching of
the finding with an actual observation.
"""This function allows to define the transitions in the pattern automaton (equivalent to the rules in an abstraction grammar), describing the evidence observable, its membership to AP or EP, and the temporal and value constraints. Constraints are defined as functions receiving an AbstractionPattern instance and the Observable observed in the transition, and they are expected to raise an InconsistencyError exception if constraints are not satisfied, or finish silently if they do. As a result, they may assign values to the attributes of the hypothesized observable, so they also define the observation procedure of the pattern. Let's see an example to make things more clear:
import construe.knowledge.observables as o
###########################
### Automata definition ###
###########################
TWAVE_PATTERN = PatternAutomata()
TWAVE_PATTERN.name = 'T Wave'
TWAVE_PATTERN.Hypothesis = o.TWave
TWAVE_PATTERN.add_transition(0, 1, o.QRS, ENVIRONMENT, _t_qrs_tconst)
TWAVE_PATTERN.add_transition(1, 2, o.Deflection, ABSTRACTED, _t_defl_tconst,
_t_gconst)
TWAVE_PATTERN.final_states.add(2)In these lines, we define a pattern automaton to conjecture a Twave from the observation of an environment QRS complex and an abstracted Deflection. Temporal and value constraints between these observables are defined in the _t_qrs_tconst, _t_eint_tconst and _t_gconst functions. For example, the temporal constraints between the environment QRS complex and the abstracted Twave are the following:
from construe.model import Interval as Iv
from construe.utils.units_helper import msec2samples as m2s
################################
### T Wave related constants ###
################################
TW_DURATION = Iv(m2s(80), m2s(450)) #T Wave duration limits
ST_INTERVAL = Iv(m2s(0), m2s(250)) #ST segment duration limits
QT_INTERVAL = Iv(m2s(250), m2s(900))#QT maximum limits (not normal)
#Maximum limits from the end of the QRS to the end of the T Wave (not normal)
SQT_INTERVAL = Iv(m2s(150), m2s(750))
def _t_qrs_tconst(pattern, qrs):
"""
Temporal constraints wrt the leading QRS complex.
"""
BASIC_TCONST(pattern, qrs)
twave = pattern.hypothesis
tc = pattern.tnet
tc.add_constraint(qrs.end, twave.start, ST_INTERVAL)
tc.add_constraint(qrs.start, twave.end, QT_INTERVAL)
tc.add_constraint(qrs.end, twave.end, SQT_INTERVAL)
tc.add_constraint(twave.start, twave.end, TW_DURATION)As we can see, the framework provides some utility functions to define temporal constraints following the Simple Temporal Problem (STP) formalism [2]. It is possible to define an interval constraining the minimum and maximum temporal distance between two temporal variables, and these constraints are automatically enforced during the interpretation. The pattern parameter corresponds to an AbstractionPattern instance, and qrs is an instance of the o.QRS observable for which the matching relation is set. The BASIC_TCONST function simply sets the constraint that the beginning of the qrs instance must be before its end, and it should be added to any temporal constraints description function. Then, specific constraints are added to the pattern temporal network, aka pattern.tnet. For example, the first constraint requires the distance between the end of the QRS complex and the beginning of the T wave to be between 0 and 250 milliseconds.
Now, let's take a look to a more complex procedure, corresponding to the value constraints of the T wave pattern, also involving the interpretation procedure:
#Factor limiting the maximum slope of a T Wave wrt the corresponding QRS.
TQRS_MAX_DIFFR = 0.7
#Temporal margin for measurement discrepancies (1 mm in standard ECG scale)
TMARGIN = int(math.ceil(m2s(40)))
def _t_gconst(pattern, defl):
"""
T Wave abstraction pattern general constraints, checked when all the
evidence has been observed.
"""
twave = pattern.hypothesis
if defl.earlystart != defl.latestart or not pattern.evidence[o.QRS]:
return
qrs = pattern.evidence[o.QRS][0]
#Wave limits
beg = int(twave.earlystart)
end = int(twave.lateend)
ls_lim = int(twave.latestart - beg)
ee_lim = int(twave.earlyend - beg)
#Start and end estimation.
endpoints = {}
for lead in sorted(qrs.shape, key= lambda l: qrs.shape[l].amplitude,
reverse=True):
baseline, _ = characterize_baseline(lead, beg, end)
sig = sig_buf.get_signal_fragment(beg, end, lead=lead)[0]
verify(len(sig) == end-beg+1)
ep = _delimit_t(sig, baseline, ls_lim, ee_lim, qrs.shape[lead])
if ep is not None:
endpoints[lead] = ep
verify(endpoints)
limits = max(endpoints.iteritems(), key= lambda ep:ep[1][1])[1][0]
#We verify that in all leads the maximum slope of the T wave fragment does
#not exceed the threshold.
for lead in endpoints:
sig = sig_buf.get_signal_fragment(beg+limits.start, beg+limits.end,
lead=lead)[0]
verify(np.max(np.abs(np.diff(sig))) <=
qrs.shape[lead].maxslope * TQRS_MAX_DIFFR)
#Amplitude measure
if lead in endpoints:
twave.amplitude[lead] = np.ptp(sig)
twave.start.value = Iv(beg+limits.start, beg+limits.start)
twave.end.value = Iv(beg+limits.end, beg+limits.end)
#The duration of the T Wave must be greater than the QRS
#(with a security margin)
verify(twave.earlyend-twave.latestart >
qrs.earlyend-qrs.latestart-TMARGIN)
#The overlapping between the energy interval and the T Wave must be at
#least the half of the duration of the energy interval.
verify(Iv(twave.earlystart, twave.lateend).intersection(
Iv(defl.earlystart, defl.lateend)).length >=
(defl.lateend-defl.earlystart)/2.0)The first line, gets the reference to the Twave instance, just for convenience. The second line checks that all the necessary evidence has been observed, and otherwise the function ends without performing any action. Then, the specific beginning and end of the hypothesis is estimated in each signal lead where the QRS complex has been also observed, and these limits are stored in the endpoints dictionary (for this, the _delimit_t() function is used, that might be any T wave delineation method). The success of this stage is enforced by using the verify() function, which raises an InconsistencyError exception if the checked condition is not satisfied.
After the T wave delineation ends, some additional constraints are checked, for example forcing the maximum slope of the signal during the T wave does not exceed 70% of the maximum slope during the QRS complex. If this condition is satisfied, the corresponding amplitude attribute in the hypothesized observation is set.
As can be seen, the definition of abstraction grammars offers great flexibility to include external methods for constraint enforcement or observation procedures.
[1]: T. Teijeiro and P. Félix (2018). On the adoption of abductive reasoning for time series interpretation. Artificial Intelligence, 262, 163–188. https://doi.org/10.1016/j.artint.2018.06.005
[2]: M. Dechter, J. Meiri, and J. Pearl, “Temporal constraint networks,” Artificial Intelligence, vol. 49, pp. 61–95, 1991.