Discovering patterns for classification of sequential data is of key importance for a variety of fields, ranging from genomics to fraud detection. In this short paper, we propose a diferentiable method to discover both local and global patterns for rule-based binary classification. Key to this end-to-end diferentiable approach is that the patterns used in the rules are learned alongside the rules themselves.
Sequence classification using rules composed of
“classiifcation relevant patterns” is a problem that has received
considerable attention in statistical machine learning and
data mining due to its applications in e.g. speech
processing, fraud detection or genomics. There exists a wide
literature that combines (un)supervised pattern mining
techniques with sequence classification. Sequential
pattern mining has focused to a great extent on mining
frequent symbolic subsequences [
In this paper, we propose a diferentiable rule learning classification model for sequential data where the conditions are composed of sequence-dependent patterns that are discovered alongside the classification task itself.
More precisely, we aim at learning a rule of the following
structure: if pattern then class = 1 else class = 0. In
particular we consider two types of patterns: local and global
patterns as introduced in [
Model The base rule model (Figure 1) we invoke is
composed of two consecutive layers that respectively
mimic logical AND and OR operators (inspired by the
rule learning modules in [
This model has a direct equivalence with a binary classification rule like if (∧)∨ then class = 1 else class = 0, where , and are binary input features (atoms in logical terms) 1.
In this paper, we apply the base rule model as a 1Dconvolutional window of fixed length over a sequence and retrieve all outputs as input for an additional disjunctive layer which we refer to as the Conv-OR layer. The base rule model learns a boolean expression over the window size length and the Conv-OR layer indicates where along the sequence that logical expression is valid. If the evaluation of the logical expression is valid all along the sequence then it can be described as a global pattern, otherwise the learned pattern represents a local pattern.
Expressivity With this approach, diferent sequencedependent expressions can be extracted and their nature depends on the learned weights of the Conv-OR layer (Figure 1).
• If all the weights of the Conv-OR layer are activated (i.e. equal to 1), the logical expression learned by the base model is valid in all the sequence: a global pattern is learned. • If only some of the weight of the Conv-OR layer are activated, the logical expression learned by the base model is valid only in the window associated to that weight: a local pattern is learned. The 1A natural extension of this architecture for sequential data would be to extend this base rule model with an explicit recursion of the base rule model, similar to a RNN. This approach was tested but faced the same limitations as any classical RNNs, i.e., vanishing gradients and only captures short-term dependencies. base model logical expression is modified accordingly to match that shift (see example in Figure 1 with a shift of 3 sequential steps).
The obtained weights thus translate to rules with the following grammar: global pattern is an expression describing the presence of a pattern anywhere in the sequence, for example B-D in sequence, where “− " sign refers to “followed by" in global patterns. global pattern over window B-*-D [t-6; t-3] in window local pattern is a boolean expression composed of atoms that are TRUE at a specific position, for example A at t-15. rule expr → → if expr then class = 1 else class = 0 local pattern | global pattern | sequence prop
We introduce , the position when the last observation
in a sequence was made. With being our reference, in a
sequence of size ∈ N, − refers to the moment of the
th observation before (0 ≤ ≤ − 1). , , and
are toy binary input features, for simplicity of the ex- Those expressions could then be used as input to another
ample those features can not be activated simultaneously AND/OR layer model for instance, for extending the rule
at the same position in the sequence but the method is complexity.
still valid for complex symbolic sequences [
With those definitions, we list below examples of
different sequence-dependent atoms that can be expressed
with the proposed architecture (See Figure 1):
condition on sequence property is a condition on
the sequence length for example 4 ≤ length
of sequence ≤ 6 (not shown on the figure but
it corresponds to a specific case where the base
model has learned an empty rule.)
Sparsity Requirements In order to learn those
expressions, especially the global ones, the model needs
to generalize without observing all possible instances at
training time. The first requirement for that matter is
sparsity in the base model. The approach taken follows
a sparsify-during-training method [
Preliminary results Experiments with synthetic toy examples containing ground-truth patterns as those expressed in Figure 1 can be discovered from moderately small samples sizes (See Appendix A for details). Variations and extensions of these pattern have shown promising results and further tests need to be pursued to scope the range of discoverable patterns with this approach.
Limitations There are limitations to this architecture.
The main one being that the window size is fixed and that it limits the size of the patterns that can be found. There is a trade-of between the maximum size of patterns and the training complexity that has to be further investigated.
Conclusion To conclude, we presented a
1Dconvolutional neural architecture to discover local and
global patterns in sequences while learning binary
classification rules. This architecture is fully diferentiable
and requires sparsity that is enforced dynamically. Its
main limitation is its dependence to the window size
parameter. Further work will consist in integrating
this block into more complex architectures to augment
the expressivity of the learned rules. Moreover, the
algorithm will be tested on concrete datasets such as
UCI splice dataset or E. Coli promoter gene sequences
dataset [
Acknowledgments This work has been partially funded by the French government as part of project PSPC AIDA 2019-PSPC-09, in the framework of the “Programme d’Investissement d’Avenir”.