The most iconic duality of machine learning models is symbolic learning versus functional learning. While functional learning is based on a numerical approach to knowledge extraction and modelling, the purpose of symbolic machine learning is to extract knowledge from data in such a form that it can be understood, discussed, modified, and applied by humans, as well as serve as the basis of artificial intelligence applications. The typical problems associated with machine learning are classification and rule extraction; while classification can be dealt with using both functional and symbolic learning, rule extraction is essentially symbolic. One element common to nearly all definitions and tools for rule extraction is that they are applied to static datasets and based on propositional logic; unfortunately, very often real-world applications give rise to non-static sets of data (e.g., temporal, spatial, graph-based data) and may require more-than-propositional expressive power. In order to extract association rules from non-static data, in this paper we propose a definition of modal association rules based on modal logic, and we study how a standard rule extraction algorithm such as APRIORI can be generalized to the modal case while keeping the properties of the canonical, non-modal case, namely, correctness and completeness.
The most iconic and fundamental separation between the sub-fields of machine learning is the
one between functional and symbolic learning. Functional learning is the process of learning a
function that represents the theory underlying a certain phenomenon. Symbolic learning, on
the other hand, is the process of learning a logical description that represents that phenomenon.
Whether one or the other approach should be preferred raised a long-standing debate among
experts, which roots in the fact that functional methods tend to be more versatile and statistically
accurate than symbolic ones, while symbolic methods are able to extract models that can be
interpreted, explained, and then enhanced using human-expert knowledge. These characteristics
of symbolic methods, both for political reasons (consider, for example, the recent General
Data Protection Regulation (GDPR) [
From a logical standpoint, canonical symbolic learning methods are mostly characterized by
being based on propositional logic, and by being designed for static data, in which every instance
is described by the value of attributes. Non-static data, such as dimensional (temporal, spatial,
spatio-temporal) data, graph-based data, or textual data, however, cannot be successfully dealt
with within the same schema in a native way. The standard approach is to pre-process such
data, so that their aspect becomes static again (e.g., by averaging the value of attributes along
all dimensions), and that of-the-shelf static symbolic methods can be used. Modal symbolic
learning [
This paper is organized as follows. First, in Section 2, we lay down some basic preliminaries, and we define the concept of modal datasets. Then, in Section 3, we define modal association rules from a logical viewpoint, and in Section 4 we extend APRIORI to extract modal frequent sets and we study its properties, namely, correctness and completeness. In Section 5 we give examples of possible applications of modal association rules, before concluding.
(ML) are obtained by the following grammar: Given a set of propositional letters , the well-formed formulas of the propositional modal logic
::= | ¬ | ∧ | ♢ , where the remaining classic Boolean operators can be obtained as shortcuts. In what follows, we use □ to denote ¬♢ ¬ , and ≡ to denote the logical equivalence. The modality ♢ (resp., □ ) is usually referred to as it is possible that (resp., it is necessary that). Modal logic is considered as archetypal of temporal, spatial, and spatio-temporal logics, and it is an extension of propositional logic (PL). Its semantics is given in terms of Kripke models. A (finite) Kripke model = Instance/Kripke model 1 2 3 4 0 0 . . .
1 1 2 2 3 3 (, , ) is composed by a finite set of worlds (which contains a distinguished world 0, called initial world), a binary accessibility relation ⊆ × : → 2 , which associates each world with the set of propositional letters that are true on it. The truth relation , ⊩ for a generic model and a generic world in that model is , and a valuation function given by the following clauses: , ⊩ , ⊩ , ⊩ ♢ , ⊩ ∧ ¬ if if if if ∈ (); , ⊮ ; , ⊩ and , ⊩ ; ∃ s.t. and , ⊩ .
Most classic temporal [
Definition 1
(modal dataset). Given a set of propositional letters , a modal dataset ℐ = {1, . . . , } is a finite collection of instances, each of which is a finite Kripke model = The above definition generalizes the conventional notion of propositional, or static, dataset, in which each of the instances is associated to the value of distinct numerical attributes. An example of modal dataset is illustrated in Fig. 1. In machine learning, several problems are associated to a dataset ℐ. The most common one is the classification/regression however, we are interested in the equally common learning problem known as association rule problem; here, extraction: in a generic dataset, it is the problem of extracting meaningful associations among the values of the attributes.
In the following, we first define the concept of meaningful association rule, and then we focus our attention to the problem of extracting (all) meaningful rules from a modal dataset.
Rule-based methods are ubiquitous in modern machine learning and data mining
applications [
Let be an alphabet on ℐ. In its simplest form, propositional association rules are objects of
the type [
: 1 ∧ . . . ∧ ⇒ +1,
where 1, . . . , , +1 ∈ are positive propositional literals (or simply propositional literals);
recalling the standard nomenclature in the association rule mining literature, propositional
literals are also known as items [
: ⇒ ,
where = {1, . . . , } is called antecedent, = {+1} is called consequent, and ∩ = ∅.
Association analysis must be interpreted with caution: causality is not implied in the inference
process by an association rule as it simply represents strong co-occurrence relationship of
the literals in the antecedent with those in the consequent [
In order to formalize the modal association rule mining problem, where instances of a modal dataset are generic, finite Kripke models, we must first lift the concept of literals to the modal case.
Definition 2 (modal literals). For a fixed alphabet , the set of positive modal literals (or simply modal literals) Λ over is defined by the grammar:
::= | ♢ | □ , where ∈ .
Modal literals of the type are called propositional, as in the propositional case, and modal literals of the type ♢ (resp., □ ) are called existential (resp., universal). (1) (2) Definition 3 (modal association rules). For a fixed set of modal literals Λ , modal association rules are objects of the type: : 1 ∧ . . . ∧ ⇒ +1, (3) where 1, . . . , , +1 ∈ Λ .
Note that (3) has the same structure as (1), except that has been replaced by Λ . Non-empty
subsets of Λ are called modal patterns, and we sometimes write a rule in its set-theoretical
notation, that is, ⇒ , where both and are modal patterns and is a singleton.
Similarly to the propositional case, modal rules are not modal formulas; when treated like that,
they belong to the Horn fragment of modal logic MLHorn. There are several, although very
similar, proposals for a Horn fragment of modal logic. Bresolin et al. [
Not all rules are interesting or meaningful. As for the propositional case, in order to capture
the notion of meaningfulness in logical terms, in [
|ℐ| Similarly to the propositional case, we can define popular interestingness measures for modal rules in such a way to be (local and global) support-dependent.
Definition 5 (confidence, lift) . Let ℐ be a modal dataset, and : ⇒ a modal rule. The local confidence of on some instance ∈ ℐ is defined as: (, ⇒ ) = (, ∪ ) (, ) , and, given a certain local support ∈ (0, 1] ⊂ R, the global confidence of on ℐ relatively to is defined as: (ℐ, ⇒ ) = (ℐ, ∪ ) .
(ℐ, ) Similarly, the local lift of on some instance ∈ ℐ is defined as: (, ⇒ ) =
(, ∪ ) (, ) · (, ) , and, given a certain local support ∈ (0, 1] ⊂ defined as:
R, the global lift of on ℐ relatively to is (ℐ, ⇒ ) =
(ℐ, ∪ ) (ℐ, ) · (ℐ, ) .
Confidence measures how frequently items in appear in instances (in the global setting) or worlds (in the local setting) that contain . Similarly, lift measures the dependence between and . From the above examples, we can derive a general notion of support-dependent interestingness measure; we say that a measure is local support-dependent (resp., global supportdependent) if and only if it can be computed by a function of the local support (resp., global support) of its set of worlds (resp., instances). We denote by (resp., ) a generic local (resp., global) support-dependent measure.
Definition 6 (holding). Let ℐ be a modal dataset, : ⇒ a modal rule, a ( + 1)-vector of values in (0, 1] ⊂ R (indexed from 0 to ), and let 1, . . . , be local supportdependent measures. We say that -holds on ∈ ℐ if and only if: (i) (, ∪ ) ≥ [0], and (ii) for each 1 ≤ ≤ , (, ) ≥ []. We denote such a situation by: ⊩ .
ℐ ⊩ .
Similarly, given ∈ (0, 1] ⊂ R, if is a ( + 1)-vector of values in (0, 1] ⊂ R (indexed from 0 to ), and 1, . . . , are global support-dependent measures, we say that -holds on ℐ if and only if: (i) (ℐ, ∪ ) ≥ [0], and (ii) for each 1 ≤ ≤ , (ℐ, ) ≥ []. We denote such a situation by: As defined in the literature, the association rules mining problem has two parts: frequent patterns mining and extraction of interesting rules. Therefore, in both settings, local and global, the first conditions, (, ∪ ) ≥ [0] and (ℐ, ∪ ) ≥ [0], enforces a rule to be frequent in terms of their supports, locally and globally, respectively. The remaining conditions can be arbitrarily combined but they cannot be separated from imposing a minimal support. Observe that, the notion of a rule holding on a single instance collapses to the standard notion of truth when instances are propositional (that is, with a single world); similarly, in the same case, the notion of a rule holding on a dataset collapses to the (implicit) notion of propositional rule holding on a dataset (driven by the classical support and confidence/lift/. . . ). The definition of such generalized notions is not unique, as diferent constraints could be enforced. However, not every combination makes sense. For example, forcing a rule to be globally supported if and only if it is locally supported on every instance would imply requiring perfect global support, which is rather restrictive and possibly non-adherent to the intended use of rules.
In the next section we shall focus on solving the following natural problem: given a modal dataset ℐ and a vector of ( + 1) values in (0, 1] ⊂ R for some ∈ (0, 1] ⊂ R, extract (or mine) all and only modal rules that -hold on ℐ, which we regard to as interesting.
As a consequence of focusing on support-dependent interestingness measures only, it turns
out that extracting interesting rules can be achieved by simply extracting sets of literals with
a relatively high support, which in the classic terminology are called frequent sets. To see
-holds on a
this, consider a rule : ⇒ , and assume that we want to check if it [, ]
certain dataset ℐ, where is the minimum requested global confidence. To this end, it must
hold that (ℐ, ∪ ) ≥ and that (ℐ, ) ≥ . To compute the latter, one
has to compute, first, (ℐ, ∪ ) and (ℐ, ), which are both by-products of
computing (ℐ, ∪ ). Therefore, being able to extract all frequent sets of literals is
necessary and suficient to be able to extract all interesting rules as we have defined them. This
phenomenon occurred at the propositional level too, obviously; it is interesting to observe that
it still holds at the modal one by inheriting exactly the same procedure (see again, e.g., [
The problem of enumerating all sets of frequent literals has been studied in the literature [
Naturally, there are a potentially exponential number of frequent sets of a given dataset ℐ, even
at the propositional level. Focusing on maximal frequent sets of literals does not change this,
and the complexity of the problem of extracting them becomes therefore interesting. As proved
in [
ALGORITHM 1: Modal extension of the APRIORI algorithm for mining frequent modal patterns.
APRIORI has been the first pruning-based algorithm for mining sets of propositional literals. Borrowing the same concept from the propositional level, the global support models the (relative) frequency of instances in ℐ that satisfy the modal pattern , whereas the local support, in the more general modal setting that we present here, models the frequency of worlds in ∈ ℐ that satisfy the modal pattern . Observe that the anti-monotonic property (the APRIORI principle) also holds for the local support, as longer modal patterns hold on fewer worlds, which is a consequence of the logical conjunction in the definition of the truth , ⊩ . The modal extension of APRIORI is based on the following assumption, which also holds in its propositional version of APRIORI: modal literals in modal patterns can be lexicographically ordered. The reason behind such an assumption, that works in synergy with the APRIORI principle, is to avoid useless computation during the learning routine. Algorithm 1 generalizes the APRIORI algorithm to the modal case and takes as input a modal dataset ℐ, an alphabet defined on ℐ, three user-specified thresholds , ∈ (0, 1] ⊂ R, and ∈ N for the minimum local support, minimum global support, and maximum modal depth of modal literals, respectively. Setting a maximum modal depth is a necessary step for the algorithm to work and terminate, as there is no anti-monotonic property that holds for modal literals; it should be noticed, however, that modal rules with too long modal literals would disfavour their interpretability. In Algorithm 1, and denote the set of frequent modal patterns and the set of generated candidates of modal patterns of length , for ≥ 1 ∈ N, respectively. The algorithm starts by computing the set of modal literals Λ from and . Then, it computes 1 whose patterns are frequent from 1. Next, the repeat-until loop block of the algorithm computes iteratively , with > 1. The (· ) procedure generates candidate modal patterns by joining1 − 1 with itself: two lexicographically ordered frequent ( − 1)-length modal patterns { 1, . . . , − 1, − 1} and { 1, . . . , − 2, ′− 1} of − 1 are merged together if they have the same modal patterns in the first − 2 positions and if − 1 < ′− 1 to form a candidate -length modal pattern { 1, . . . , − 2, − 1, ′− 1}. The candidates from are then pruned by the (· ) function based on the APRIORI principle. It is important to stress the fact that, both (· ) and (· ) are identical as in the canonical APRIORI algorithm. At this stage, the algorithm produces whose elements are from which are frequent. Termination is guaranteed by the anti-monotonic property of the support.
We now study correctness and completeness of our approach. It is important to stress the fact that completeness is parametric in .
Theorem 1 (correctness). is correct.
Proof. We want to show that , for each ≥ 1, is the set of frequent -length modal patterns. The proof is by induction on . If = 1, then 1 contains singleton sets of modal literals of the type { }, where ∈ Λ , that are frequent. Thus, by construction, 1 is made of frequent 1-length modal patterns. If > 1, to obtain the set of frequent sets of modal literals , the algorithm generates candidates by combining elements of − 1, which are frequent by inductive hypothesis. Let { 1, . . . , − 2, − 1} and { 1, . . . , − 2, ′− 1} be elements of − 1 used by the candidate generation procedure to generate ∈ , such that = { 1, . . . , − 2, − 1, ′− 1}. If is frequent, that is, meets the support, then ∈ . Therefore, is made of -length frequent patterns.
Theorem 2 (completeness). is complete.
Proof. Let be the set of frequent sets of modal literals and let be the set of candidate frequent sets of modal literals, whose modal patterns have length . We want to show that ⊆ , for all ≥ 1. The proof is by induction on . If = 1, then 1 is the set of singleton sets of the type { }, and 1 ⊆ holds since 1 is defined as the subset of that are frequent. If > 1, assume, by inductive hypothesis, that − 1 ⊆ − 1. We must show that ⊆ . Let = { 1, . . . , − 2, − 1, ′− 1}. The pattern is generated by two ( − 1)-length modal patterns, say { 1, . . . , − 2, − 1} and { 1, . . . , − 2, ′− 1}, such that − 1 < ′− 1, which are necessarily frequent, by inductive hypothesis. Thus, ∈ must hold and if meets the support, then ∈ , obtaining the thesis.
Modal logics are, as we have observed, archetypal of many temporal, spatial, and spatiotemporal logics. The purpose of modal symbolic learning is designing symbolic machine learning 1This is the original nomenclature. techniques to deal with non-static data. Non-static data include, among others, dimensional data (that is, data with temporal and/or spatial components), graph-based data (that is, data natively in the form of graphs, such as social networks, or gene expression networks), and textual data (that is, data in the form of natural language text). The most basic advantage of modal symbolic learning is that of reuniting all such non-static data under the same viewpoint, that is, seeing them all as modal data. How this is done in all cases is outside the scope of this paper; by way of example we take here the dimensional, temporal case to show how the modal framework emerges naturally.
Dimensional datasets can be regarded as modal datasets in which the Kripke model associated
to an instance is implicit and presented in tabular form; this corresponds to the typical
presentation of dimensional data, as in Fig. 2, left-hand side. While in the classical sense instances
correspond to lines, more than one line make up for a real-world instance. So, for example, each
instance of the left-hand side of the picture may be the status of a patient under observation,
each being described by two attributes 1 and 2, over the course of four time points 1 through
4. Thus, the intended meaning of such a dataset is that we have in fact four patients (being
distinguished by their names 1 through 4), which become four multivariate time series,
denoted by 1 through 4, each composed by four values per attribute, as in Fig. 2, right-hand
side. By regarding each interval in the temporal domain 1, . . . , 4 as a world, one ends up
building a Krikpe structure from each time series (in this example, each structure has 6 worlds,
that is, 6 non-instantaneous intervals). Connecting each pair of such intervals there is exactly
one of 12 Allen’s relations [
Observe, now, that each interval in this setting accounts for a set of values for each attribute; for example, in Fig 2, the instance 1 has values 111, 112, 113 for 1 in the interval [1, 3]. By applying suitable feature extraction function(s) one can, at this point, aggregate such set of values in a single one; typical aggregations include the average, the maximum, and the minimum, but in the literature of learning from temporal data one finds several more, and less trivial, examples. Let us call any such aggregation function; by applying to every possible interval for the attribute , one ends up with a new set of values, that is, the domain ( ()). At this point, it is possible to extract a propositional alphabet, of the type:
1 ≤ () ≤ 2, with 1, 2 ∈ ( ()). By labeling each world (interval) with the truth value of each of the propositional letters, we extract from a dimensional, temporal dataset a modal one.
The explicit knowledge that can be extracted from electroencephalogram recording (EEG) of subjects that are in certain conditions or are carrying on certain activities is of uttermost importance in the scientific enquiry of those conditions and activities. The current approaches to this problem are entirely functional, but, despite the terminological afinity, black-box classification models such as neural networks cannot be considered models of the human mind. EEG is a real-world example of dimensional data that could be used for modal association rule extraction. A typical EEG is performed with a head-set that accommodates several electrodes (typically, in the fifties), each one of which records, during a single experiment, the voltage that is expressed by a specific area of the human brain; the signal of each electrode is then preprocessed through Fourier-like transformations, so that each signal gives rise to several components at diferent frequency intervals (typically, in the tens). All in all, a single EEG recording generates anywhere between 500 and 2000 temporal attributes (pairs electrode-frequency) over the course of the experiment. A recent trend in neurobiology is focusing on how diferent experimental situations can be distinguished by the form and the values of the corresponding EEG recording, which helps neurobiologists to understand the nature of the diferent brain areas in diferent settings. While most often these problems are designed as classification problems, understanding how the several attributes relate to each other through time in a specific situation may turn out to be very interesting. Temporal relationships can be extracted as modal rules, specifically HS rules, which would have the form of assertions of the type: if the value of the voltage in this sensor at this frequency is within this interval of values during an interval of time, then the value of the voltage in this other sensor at this other frequency must be within this other interval immediately after it.
Symbolic learning is the sub-field of machine learning that deals with symbolic algorithms and models, which have been known for decades and successfully applied to a variety of contexts. The main limitation of current symbolic models is the fact that they are essentially based on classical propositional logic, which implies that dimensional data, graph-based data, or textual data must be pre-processed in order to be dealt with within the classic framework, at the expenses of decreasing the interpretability of the result and loosing information.
Modal symbolic learning is the modal logic generalization of symbolic learning; in this paper we considered the problem of defining the concept of modal association rules and their logical characterization, and we devised a correct and complete algorithm, ModalAPRIORI, which is able to extract frequent sets of modal literals both at the global and local level, and therefore modal symbolic rules. We also discussed potential applications of modal symbolic rules.