# Distillation of encoder-decoder transformers for sequence labelling

Marco Farina 1 Duccio Pappadopulo11footnotemark: 1 1 Anant Gupta1
Leslie Huang1 Ozan İrsoy1 Thamar Solorio 1,2
1Bloomberg 2Department of Computer Science, University of Houston
{mfarina19, dpappadopulo, agupta968, lhuang328<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Equal contribution Research completed during
sabbatical at Bloomberg

###### Abstract

Driven by encouraging results on a wide range of tasks, the field of NLP is
experiencing an accelerated race to develop bigger language models. This race
for bigger models has also underscored the need to continue the pursuit of
practical distillation approaches that can leverage the knowledge acquired by
these big models in a compute-efficient manner. Having this goal in mind, we
build on recent work to propose a hallucination-free framework for sequence
tagging that is especially suited for distillation. We show empirical results
of new state-of-the-art performance across multiple sequence labelling
datasets and validate the usefulness of this framework for distilling a large
model in a few-shot learning scenario.

Distillation of encoder-decoder transformers for sequence labelling

Marco Farina††thanks:  Equal contribution 1 Duccio Pappadopulo11footnotemark:
1 1 Anant Gupta1 Leslie Huang1 Ozan İrsoy1 Thamar Solorio††thanks:  Research
completed during sabbatical at Bloomberg 1,2 1Bloomberg 2Department of
Computer Science, University of Houston {mfarina19, dpappadopulo, agupta968,
lhuang328<EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Sequence labelling (SL) can be defined as the task of assigning a label to a
span in the input text. Some examples of SL tasks are: i) named entity
recognition (NER), where these labelled spans refer to people, places, or
organizations, and ii) slot-filling, where these spans or slots of interest
refer to attributes relevant to complete a user command, such as song name and
playlist in a dialogue system. In general, these spans vary semantically
depending on the domain of the task.

Despite the strong trend in NLP to explore the use of large language models
(LLMs) there is still limited work evaluating prompting and decoding
mechanisms for SL tasks. In this paper we propose and evaluate a new inference
approach for SL that addresses two practical constraints:

  * •

Data scarcity: The lack of vast amounts of annotated, and sometimes even the
lack of unlabelled data, in the domain/language of interest.

  * •

Restricted computing resources at inference time: LLMs are very effective, but
deploying them to production-level environments is expensive, especially in
contexts with latency constraints, such as in a live dialogue system.

Original text
---
play | wow | by | jon | theodore |
Encoder input for SenT′ format
<extra_id_0> play |  <extra_id_1> wow |  <extra_id_2> by |  <extra_id_3> jon |  <extra_id_4> theodore | <extra_id_5>
Expected decoder output for SenT′ format
<extra_id_0> O |  <extra_id_1> TRACK |  <extra_id_2> O |  <extra_id_3> ARTIST |  <extra_id_4> I | <extra_id_5>

Table 1: An example of how an original input text (from the SNIPS dataset) is
transformed into the SenT′ input for the model, and the format for the
expected output. We use the explicit form of the special token strings used by
T5. The addition of the extra token at the end of the input differentiates
SenT′ from SentT. Notice the modified BIO scheme (sBIO) that we use in our
experiments: a unique I tag is used for each of the output tags; so if the
original tag set is $T$, the tags generated by the model are
$\overline{T}\equiv T\cup\\{I,O\\}$.

Data scarcity leads us to consider high-performing encoder-decoder based LLMs.
We address deployment concerns by considering distillation of such models into
much smaller SL architectures, for instance Bi-Directional Long Short Memory
(BiLSTM) (Hochreiter and Schmidhuber, 1997) units, through the use of both
labelled and unlabelled data.

A standard distillation approach, knowledge distillation (KD) (Hinton et al.,
2015), requires access to the probability that the teacher network assigns to
each of the possible output tags. This probability distribution is typically
unavailable at inference time for LLMs; thus, distillation of encoder-decoder
models needs to resort to pseudo-labels:111In this paper, we refer to
distillation with pseudo-labels as the process by which a student model is
trained on the one-hot labels (and only those labels) generated by a teacher
model on an unlabeled dataset. We wish to distinguish this from KD, in which
the probability distribution over labels is also used. See also Shleifer and
Rush (2020). the student is trained on the one-hot labels that the teacher
assigns to examples in an unlabelled dataset. This prevents the student model
from learning those relationships among the probabilities of the incorrect
classes that the teacher has learned. Similar arguments apply to decoder-only
models.

In this paper, we propose SenT′, a simple modification of the _Simplified
Inside Sentinel $+$Tag_ (SenT) format by Raman et al. (2022). We combine our
target sequence format with a scoring mechanism for decoding, which we
collectively call SenTScore. This combination results in an effective
framework that allows us to employ a language model to perform sequence
labelling and knowledge distillation. We show that SenTScore is an
hallucination-free decoding scheme, and that even with smaller models it
outperforms the original SenT format across a variety of standard SL datasets.

Our proposed SenTScore method defines a sequence of scores over the output
tags that can be aligned with those generated by the sequence tagging student
network, making KD possible. We find an advantage in terms of performance in
using KD as opposed to just pseudo-labels as a distillation objective,
especially for smaller distillation datasets.

In sum, our contributions are:

  * •

A new, hallucination-free, inference algorithm for sequence labelling with
encoder-decoder (and possibly decoder only) transformer models, SenTScore,
that achieves new state-of-the-art results on multiple English datasets.

  * •

Empirical evidence showing an advantage of SenTScore when distilling into a
smaller student model. This approach is particularly promising in the few-shot
setting, which makes it even more appealing and practical.

##  2 Related work

Using LLMs to perform sequence tagging is discussed by Athiwaratkun et al.
(2020); Yan et al. (2021); Paolini et al. (2021); Qin and Joty (2021); Xue et
al. (2022) and Raman et al. (2022). While these previous works have minor
differences in the prompting format of the models, all but the last one
include input tokens as part of the target sequence. Different from our work,
all previous models are prone to hallucinate.

Distillation refers to training a small student model from scratch using
supervision from a large pretrained model (Bucilua et al., 2006; Hinton et
al., 2015). Distillation of transformer-based models for different NLP tasks
is typically discussed in the context of encoder-only models (e.g. Tang et
al., 2019; Mukherjee and Hassan Awadallah, 2020; Jiao et al., 2020), with a
few exceptions looking at distillation of decoder-only models (e.g. Artetxe et
al., 2021).

In this paper we will discuss two approaches to distillation: _pseudo-labels_
and _knowledge distillation_ (KD). In the first approach the student model is
trained on the hard labels generated by the teacher on some (unlabelled)
dataset. In the second approach additional soft information provided by the
teacher is used: typically the probability distribution the teacher assigns to
the labels.

In the context of sequence labelling, using pseudo-labels allows us to perform
distillation on any teacher-student architecture pair. KD, on the other hand,
requires access to the teacher’s probability distribution over the output
tags. These are not usually available in language models for which the output
distribution is over the whole vocabulary of tokens. We are not aware of other
works which modify the decoder inference algorithm to generate such
probabilities. However, there is recent work distilling internal
representations of the teacher model, with the most closely related work to us
being Mukherjee and Hassan Awadallah (2020). In that work the authors distill
a multilingual encoder-only model into a BiLSTM architecture using a two-stage
training process. This two-stage process, however, assumes a large unlabelled
set for distilling internal model representations, embedding space, and
teacher logits, and another significant amount of labelled data for directly
training the student model using cross-entropy loss.

##  3 Datasets

We select seven English datasets that have been used in recent work on slot
labelling: ATIS (Hemphill et al., 1990), SNIPS (Coucke et al., 2018), MIT
corpora (Movie, MovieTrivia, and Restaurant)222The MIT datasets were
downloaded from: https://groups.csail.mit.edu/sls/ , and the English parts of
mTOP (Li et al., 2021) and of mTOD (Schuster et al., 2019). Some statistics
about the datasets are shown in Table 2. Some of these datasets (ATIS, SNIPS,
mTOP, and mTOD) come from dialogue-related tasks, while the MIT ones have been
used for NER.

We use the original training, development, and test sets of the SNIPS, mTOP,
and mTOD datasets. For the ATIS dataset we use the splits established in the
literature by Goo et al. (2018), in which a part of the original training set
is used as the dev set. Similarly, we follow Raman et al. (2022)333Private
communication with authors to obtain a dev set out of the original training
set for each of the MIT datasets.

We notice that all datasets, with the exception of MovieTrivia, contain some
duplicates. Among these, all apart from Restaurant contain examples in the
test set that are also duplicated in the train and dev sets. This happens for
fewer than 30 instances, with the exception of mTOD, where more than 20% of
the test set examples are also found in the train and dev sets. How these
duplicates are handled varies across the literature; we do not remove
duplicates from the datasets used in our main results.

However, for mTOD, we also obtained results on a version of the dataset that
was deduplicated as follows: If an example is duplicated, we retain it in the
highest priority (defined below) split and removed from the others. To ensure
the test set is as close as possible to the original test set, we order the
splits in ascending order of priority as follows: test, dev, and train. We
found that the F1 scores on the deduped mTOD dataset are within 0.5 points
those on the original mTOD dataset across all experiments; as such, we do not
report the deduped results in the following sections.

In addition to covering different domains, there are noticeable differences
across the datasets in terms of the number of tags and the number of labelled
examples for evaluation and testing, as can be seen in Table 2. This set of
seven datasets allows us to gather robust empirical evidence for the proposed
work that we present in what follows.

Datasets | # tags | # train | # dev | # test
---|---|---|---|---
ATIS | 83 | 4478 | 500 | 893
SNIPS | 39 | 13084 | 700 | 700
MovieTrivia | 12 | 7005 | 811 | 1953
Movie | 12 | 8722 | 1053 | 2443
Restaurant | 8 | 6845 | 815 | 1521
mTOP (en) | 75 | 15667 | 2235 | 4386
mTOD (en) | 16 | 30521 | 4181 | 8621
Table 2: Number of examples per partition and number of unique tags in the SL
datasets we used.

##  4 Score-based sequence labelling

Using LLMs for sequence tagging requires reframing the problem as a sequence-
to-sequence task. In Raman et al. (2022), the strategy that proved the most
effective, at least when applied to the mT5 encoder-decoder architecture, was
the _Simplified Inside Sentinel $+$Tag_ (SenT in this paper). In this format
(see Table 1), the original text is first tokenized according to some
pretokenization strategy (whitespace splitting for all the datasets
considered), and each of the tokens is prepended with one of the extra token
strings provided by mT5 (the _sentinel_ tokens). The resulting concatenation
is then tokenized using the mT5 tokenizer and fed to the encoder-decoder
model. The output that the decoder is expected to generate is the same input
sequence of special token strings, which are now alternated with the tags
corresponding to the original tokens.

Given the set $T$ of string labels to be used to annotate a span of text, the
scheme used to associate tags across tokens is a modification of the standard
BIO scheme: we use $t\in T$ for any token that starts a labelled span, a
single tag I for each token that _continues_ a labelled span, and O to tag
tokens that do not belong to labelled spans. We refer to this scheme as
_Simplified Inside BIO_ (sBIO), and we indicate with $\overline{T}\equiv
T\cup\\{I,O\\}$ the tag set associated to it.

Raman et al. (2022) argue that the success of SenT can be attributed to two
factors: 1) on the one hand, the use of sentinel tokens mimics the denoising
objective that is used to pretrain mT5; 2) on the other hand, when compared to
other decoding strategies, SenT does not require the decoder to copy parts of
the input sentences and also produces shorter outputs. Both these facts
supposedly make the task easier to learn and reduce the number of errors from
the decoder (_hallucinations_ , as they are often referred to in the
literature).

We remark however that any output format among those described in the
literature can be made completely free of hallucinations by constraining
decoding (either greedy or beam search based) through a finite state machine
enforcing the desired output format (see for instance De Cao et al., 2020). In
what follows we describe our proposed decoding approach that builds on this
previous work.

###  4.1 SenTScore

Regardless of possible constraints imposed during generation, both SenT and
the other algorithms described in Raman et al. (2022) use the decoder
autoregressively at inference time to generate the target sequence. Since
generation proceeds token by token and the textual representation of a tag is
a variable length sequence of tokens, it is nontrivial to extract the scores
and probabilities that the model assigns to individual tags.

We propose a different approach to inference, one in which the decoder is used
to score sequences of tags. For this purpose, we consider a sequence tagging
task with a label set $T$, and the associated sBIO tag set $\overline{T}$.
Given an input sentence $S$, we use a pre-tokenizer (such as whitespace
splitting) to turn $S$ into a sequence of token strings $x_{1}\ldots x_{L}$,
of size $L$. The SenT format is obtained by interleaving these tokens with
special token strings to obtain the input string
$S_{\textrm{in}}=s_{0}x_{1}s_{1}\ldots x_{L}$. We use juxtaposition to
indicate string concatenation. In what follows, we will work with SenT′, a
modification of SenT in which an additional special token is appended at the
end, $S_{\textrm{in}}\leftarrow S_{\textrm{in}}s_{L}$. The reason for doing
this will become clear in what follows.

The valid output strings that can be generated by the decoder are the
$|\overline{T}|^{L}$ sequences of the form
$S_{\textrm{out}}=s_{0}t_{1}s_{1}\ldots t_{L}s_{L}\in\mathcal{O}$ where
$t\in\overline{T}\equiv T\cup\\{I,O\\}$ consistent with the sBIO scheme
convention. The encoder-decoder model can be used to calculate the log-
likelihood of each of such strings
${\log\mathcal{L}_{\theta}}(S_{\textrm{out}};S_{\textrm{in}})$, where $\theta$
represents the model parameters, and the best output will be:

$S_{\textrm{out}}^{*}=\arg\max_{S\in\mathcal{O}}{\log\mathcal{L}}(S;S_{\textrm{in}})$

Exact inference is infeasible but can be approximated using beam search as
described in Algorithm 1. The outputs of the algorithm are the top-K output
strings and the score distribution associated with each of the output tags. As
is evident from Table 1, it is simple to map back the final output string
$S^{*}$ to the sequence of output tags and labelled spans.

Encoder-decoder parameters $\theta$, input $S_{\textrm{in}}$ with $L$ tokens,
sBIO tag set $\overline{T}$, beam size $K$

Approximate top-$K$ output sequences $\mathcal{B}_{\textrm{text}}$ and their
sBIO tag scores, $\mathcal{B}_{\textrm{scores}}$

$\mathcal{B}_{\textrm{text}}\leftarrow[\,s_{0}\,]_{i=1\ldots K}$

$\mathcal{B}_{\textrm{scores}}\leftarrow[\,[~{}]\,]_{i=1\ldots K}$

for $i=1$ to $L$ do

$\mathcal{H}\leftarrow[\,z\,t\,s_{i}\,]_{z\in\mathcal{B}_{\textrm{text}},\,t\in\overline{T}}$
$\triangleright$ Generate hypotheses

$\mathcal{S}\leftarrow[\,{\log\mathcal{L}}_{\theta}(h;S_{\textrm{in}})\,]_{h\in\mathcal{H}}$
$\triangleright$ Score hypotheses

$\Pi\leftarrow\textrm{K-argsort}\,\mathcal{S}$ $\triangleright$ top-K args

$\mathcal{B}_{\textrm{text}}\leftarrow\textsc{Take}(\mathcal{H};\Pi)$
$\triangleright$ Update text beam

$\widetilde{\mathcal{S}}\leftarrow{\textsc{Reshape}}(\mathcal{S};K,|\overline{T}|);$
$\triangleright$ Reshape scores

for $k=0$ to $K-1$ do $\triangleright$ Update score beam

$\widetilde{k}\leftarrow\Pi[k]\mod K$

$\mathcal{B}_{\textrm{scores}}[k]\leftarrow\textsc{Append}(\mathcal{B}_{\textrm{scores}}[\widetilde{k}];\mathcal{S}[\widetilde{k}])$

end for

end for

return $\mathcal{B}_{\textrm{text}}$, $\mathcal{B}_{\textrm{scores}}$

Algorithm 1 SenTScore beam search

At decoding time the output string is initialized with the first sentinel
token $s_{0}$. At the $i$-th step, SenTScore uses the model likelihood to
score each of the $|\overline{T}|$ possible continuations of the output
sequence

$t\,s_{i}~{}~{}{\textrm{with}}~{}~{}t\in\overline{T},$ (1)

picks the highest scoring one, and keeps track of the score distribution.
$s_{i}$ in Eq. 1, the _next_ sentinel token, plays the crucial role of an EOS
token at each step. This is needed to normalize the probability distribution:
the likelihood of the string $s_{0}t_{1}\ldots s_{k-1}t^{\prime}_{k}$ is
always bounded by that of the string $s_{0}t_{1}\ldots s_{k-1}t_{k}$ if $t$ is
a prefix of $t^{\prime}$, and we would never predict $t^{\prime}$ as a
continuation of $s_{0}t_{1}\ldots s_{k-1}$. This explains why we prefer using
SenT′ over SenT.

Finally, while SenTScore changes the inference algorithm, the finetuning
objective we use throughout is still the original language modelling one.

###  4.2 Distillation

The main advantage of SenTScore is in the distillation setting. At each
inference step, the algorithm assigns a likelihood to each sBIO tag. This
distribution can be used to train the student network by aligning it to the
teacher’s pre-softmax logits, in a standard knowledge distillation setup.

In detail, given an input sequence $S_{\textrm{in}}$, let
$(\mathbf{y}^{*}_{i})_{i=1\ldots L}$ be the sequence of sBIO output tags (as
$|\overline{T}|$-dimensional one-hot vectors) as inferred by the teacher
model, and let $(\mathbf{u}^{*}_{i})_{i=1\ldots L}$ (also
$|\overline{T}|$-dim. vectors) be the associated sequence of log-likelihoods.
We indicate with $\mathbf{p}^{*}_{i}$ the probability obtained by softmaxing
$\mathbf{u}^{*}_{i}$ and by $\mathbf{q}_{i}$ the output of the softmax layer
from the student. The contribution of each of the tags to the distillation
objective that we use to train the student sequence tagger is

$-\sum_{k}(y^{*}_{i})_{k}\log\mathbf{(}p^{*}_{i})_{k}+\lambda_{KL}\,KL(\mathbf{p}^{*}_{i}||\mathbf{q}_{i})\,.$
(2)

The first term is the standard cross-entropy contribution from the pseudo-
labels, while the second is the knowledge distillation term, implemented with
a KL divergence with $\lambda_{KL}$ its associated positive weight.

We stress that we are allowed to write the second term only because SenTScore
provides us with the tag scores. This is not the case for any of the formats
proposed in Raman et al. (2022) or, as far as we know, elsewhere.444Strictly
speaking the student defines $p(\cdot|t_{1}^{*}\ldots
t_{i-1}^{*};S_{\textrm{in}})$ (star means predicted) while $\mathbf{q}_{i}$
corresponds to $p(s_{0}t_{1}^{*}\ldots
t^{*}_{i-1}s_{i-1}\cdot|S_{\textrm{in}})$. This discrepancy is resolved by the
invariance of the softmax under constant shifts of its arguments.

##  5 Experimental settings

We evaluate the models by computing the F1 score on the test set of each
dataset. F1 is calculated following the CoNLL convention as defined by Tjong
Kim Sang and De Meulder (2003), where an entity is considered correct iff the
entity is predicted exactly as it appears in the gold data. We show micro-
averaged F1 scores.

The first set of experiments we performed are intended to investigate whether
our proposed SentTScore approach is competitive with respect to recent results
on the same datasets (Table 3). Our SentTScore model is a pretrained T5-base
model (220M parameters) finetuned on each of the datasets.555All our results
are in the greedy setting. We find very small differences in performance by
using beam search, while inference time grows considerably. We trained each
model for 20 epochs, with patience 5, learning rate of $10^{-3}$, and batch
size 32. We also want to know how the proposed framework compares against the
following strong baselines:
BiLSTM: Our first baseline is a BiLSTM tagger Lample et al. (2016).666We do
not include a CRF layer. The BiLSTM has a hidden dimension of size $200$. Its
input is the concatenation of 100d pretrained GloVE6B embeddings (Pennington
et al., 2014) from StanfordNLP  with the 50d hidden state of a custom
character BiLSTM. We trained each model for 100 epochs, with patience 25,
learning rate of $10^{-3}$, and batch size 16.
BERT: We finetune a pretrained BERT-base cased model (Devlin et al., 2019)
(110M parameters) for the SL task and report results for each of the seven
datasets. While we consider BERT a baseline model, we note that this
pretrained architecture continues to show good performance across a wide range
of NLP tasks, and for models in this size range BERT is still a reasonable
choice. In preliminary experiments we compared results from the case and
uncased versions of BERT and we found negligible differences. We decided to
use the cased version for all experiments reported here. We trained each model
for 30 epochs, with patience 10, learning rate of $5\times 10^{-5}$, and batch
size 64.
SentT′: The pretrained model is the same as that used for SentTScore. The goal
of this baseline is to assess improvements attributed to our proposed decoding
mechanism. This model is also the closest model to prior SOTA. The main
difference between our results and those in Raman et al. (2022) is the
pretrained model. They used a multilingual T5 model Xue et al. (2021) with
580M parameters, whereas we use a smaller monolingual version (Raffel et al.,
2020).

All the above models were trained with the AdamW optimizer (Loshchilov and
Hutter, 2017). The best checkpoint for each training job was selected based on
highest micro-F1 score on the validation set. All pretrained transformer
models are downloaded from Huggingface .

Dataset | BiLSTM [1M] | BERT [110M] | T5 [220M] (SenT′) | T5 (SenTScore) | mT5 [580M] (SenT)
---|---|---|---|---|---
Perfect | F1 | Perfect | F1 | Perfect | F1 | Perfect | F1 | Perfect | F1
ATIS | 89.06 | 95.56 | 88.57 | 95.27 | 86.56 | 94.77 | 89.81 | 95.99 | 90.07 | 95.96
SNIPS | 87.24 | 95.02 | 89.71 | 95.47 | 89.86 | 95.43 | 91.00 | 96.07 | 89.81 | 95.53
MovieTrivia | 32.41 | 69.81 | 36.2 | 69.15 | 36.35 | 70.76 | 39.58 | 71.99 | 39.85 | 73.01
Movie | 69.79 | 86.72 | 69.46 | 85.83 | 71.88 | 87.53 | 74.29 | 88.35 | 72.74 | 87.56
Restaurant | 58.32 | 77.39 | 58.97 | 77.69 | 58.65 | 78.77 | 63.77 | 80.91 | 62.93 | 80.39
mTOP (en) | 81.10 | 88.94 | 84.4 | 90.98 | 84.18 | 90.64 | 86.66 | 92.29 | 86.56 | 92.28
mTOD (en) | 91.70 | 95.62 | 92.35 | 95.83 | 92.24 | 96.04 | 92.94 | 96.24 | 93.19 | 96.42
Table 3: Our results comparing BERT-base and a BiLSTM against a T5-base model
using SenT′ and SenTScore on different SL datasets are shown in the first 4
columns. Number in square brackets are model sizes in terms of number of
parameters. Results from Raman et al. (2022) are copied in the last column.
Bold scores represent our best results; underlined scores in the last column
highlight those cases in which Raman et al. (2022) outperforms us.

Dataset - F1 | BiLSTM | BERT | T5 |  BiLSTM (distilled)
---|---|---|---|---
ATIS | 79.93 | 79.43 | 85.01 | 86.75
SNIPS | 51.63 | 52.16 | 54.33 | 57.18
MovieTrivia | 48.26 | 50.26 | 55.74 | 57.85
Movie | 60.82 | 61.80 | 67.09 | 70.51
Restaurant | 47.26 | 53.17 | 56.87 | 61.13
mTOP (en) | 43.12 | 46.08 | 51.94 | 54.77
mTOD (en) | 68.68 | 76.95 | 79.43 | 82.26
(a) Gold train/dev split of size 100/50

Dataset - F1 | BiLSTM | BERT | T5 |  BiLSTM (distilled)
---|---|---|---|---
ATIS | 86.43 | 84.95 | 89.33 | 90.25
SNIPS | 69.19 | 72.77 | 76.34 | 79.84
MovieTrivia | 57.64 | 58.41 | 63.60 | 65.34
Movie | 73.54 | 73.76 | 77.39 | 79.20
Restaurant | 61.62 | 62.97 | 68.52 | 68.62
mTOP (en) | 57.22 | 63.28 | 67.73 | 69.62
mTOD (en) | 83.46 | 85.51 | 88.68 | 89.82
(b) Gold train/dev split of size 300/150

Table 4: Distillation results and comparisons with baselines. The distillation
results use the full objective function in Eq. 2 with $\lambda_{KL}=1$.

###  5.1 Distillation experiment

We apply SentTScore and the loss function described in Section 4.2, to distill
a finetuned T5 model into a BiLSTM architecture to perform sequence tagging.
To mimic a low-resource setting, we randomly downsample the train/dev splits
of all the datasets. We consider two sets of sizes for these gold train/dev
splits: a 100/50 split and a 300/150 one. In both settings the remainder of
the original training set is used for the distillation component using pseudo-
labels.

We then finetune T5 using the SenT′ format on each of these two gold splits.
The resulting model is used as the teacher in a distillation setting in which
the student is a BiLSTM. The BiLSTM student is trained on the full training
set by using the downsampled gold labels, but pseudo-labels and scores
generated by the T5 teacher using SenTScore with $K=1$ in the rest of the
training data. We use a temperature parameter $\tau$ to rescale the
distribution SenTScore defines over $\overline{T}$. We use $\tau=10$ in all
the distillation experiments.

The training schedule we follow is the same we use to train the BiLSTM
baseline model, with the only exception that the best checkpoint is selected
on the reduced dev set.

##  6 Results

The comparisons between baselines, SenT′, and SenTScore are shown in Table 3.
SenTScore is used with a $K=1$ beam size. Larger beams result in very similar
performance and a considerable slowdown of inference time. SenTScore
consistently outperforms SenT′ with constrained decoding, and all other
baselines. Our intuition is that one advantage of SenTScore comes from the
fact that decoding happens tag-wise as opposed to token-wise (as in pure beam
search). The last column of Table 3 shows the performance of the SenT
implementation of Raman et al. (2022). Perfect scores are also reported for
completeness. They are evaluated at the sentence level and correspond to the
fraction of perfectly predicted examples. However these results are not
directly comparable: Raman et al. (2022) use a different and larger model
(mT5-base with 580M parameters) and different optimization details.
Nevertheless SenTScore achieves better performance in a majority of cases.

###  6.1 Distillation results

Dataset - F1 | No silver | 250 silver | 500 silver
---|---|---|---
$\lambda_{KL}=0$ | $\lambda_{KL}=1$ | $\lambda_{KL}=0$ | $\lambda_{KL}=1$ | $\lambda_{KL}=0$ | $\lambda_{KL}=1$
ATIS | 79.93 (0.85) |  82.35 (0.44) | 83.09 (1.49) |  84.42 (1.42) | 83.75 (1.74) |  85.10 (1.54)
SNIPS | 51.63 (1.25) |  55.65 (1.38) | 54.34 (0.71) |  56.02 (1.71) | 55.66 (1.21) |  57.00 (1.17)
MovieTrivia | 48.26 (0.95) |  51.86 (1.09) | 53.11 (1.26) |  55.19 (0.50) | 53.97 (1.55) |  56.00 (0.38)
Movie | 60.82 (0.67) |  64.20 (1.07) | 67.04 (0.66) |  69.41 (0.66) | 67.73 (1.28) |  70.12 (0.60)
Restaurant | 47.26 (0.83) |  50.19 (0.81) | 54.24 (1.17) |  56.20 (0.94) | 56.29 (1.11) |  57.95 (0.88)
mTOP (en) | 43.12 (1.84) |  46.43 (1.01) | 46.68 (2.31) |  49.08 (1.65) | 49.57 (0.47) |  50.33 (2.17)
mTOD (en) | 68.68 (2.68) |  70.40 (0.97) | 76.12 (1.07) |  77.86 (1.45) | 77.86 (0.85) |  79.77 (0.82)
Table 5:  Distillation experiments with varying silver dataset size and ablation of the KD term in Eq. 2. The gold data split is the same as in Table 4(a), with train/dev sizes of 100/50. The numbers in parentheses represent the standard deviation of the scores obtained by varying all the random seeds that appear at training time: BiLSTM weight initialization, batch scheduling, and the choice of the silver data set. Dataset - F1 | No silver | 250 silver | 500 silver
---|---|---|---
$\lambda_{KL}=0$ | $\lambda_{KL}=1$ | $\lambda_{KL}=0$ | $\lambda_{KL}=1$ | $\lambda_{KL}=0$ | $\lambda_{KL}=1$
ATIS | 86.43 (1.09) |  88.42 (0.48) | 89.15 (0.65) |  89.39 (0.49) | 89.73 (0.66) |  89.98 (0.31)
SNIPS | 69.19 (0.74) |  73.06 (0.54) | 72.11 (1.11) |  75.02 (1.16) | 73.99 (0.81) |  75.73 (1.47)
MovieTrivia | 57.64 (0.45) |  60.30 (0.34) | 60.25 (0.37) |  62.11 (0.54) | 61.38 (0.46) |  62.89 (0.52)
Movie | 73.54 (0.40) |  76.30 (0.33) | 75.88 (0.44) |  76.96 (0.44) | 76.52 (0.58) |  77.58 (0.26)
Restaurant | 61.62 (0.43) |  63.78 (0.27) | 64.33 (0.90) |  65.33 (0.66) | 65.20 (0.80) |  66.24 (0.63)
mTOP (en) | 57.22 (0.73) |  60.36 (0.50) | 60.81 (0.92) |  62.70 (0.69) | 62.02 (0.94) |  64.37 (0.84)
mTOD (en) | 83.46 (0.59) |  85.52 (0.20) | 86.35 (0.40) |  87.08 (0.50) | 86.82 (0.33) |  87.89 (0.40)
Table 6:  Distillation experiments with varying silver dataset size and
ablation of the KD term in Eq. 2. The gold data split is the same as in Table
4(b), with a train/dev size given by 300/150. All experimental details are
common with Table 5.

Tables 4(a) and 4(b) show the result of the distillation experiments with
100/50 and 300/150 train/dev gold splits, respectively. While a BiLSTM tagger
trained on the gold data significantly underperforms a finetuned T5-base
model, once the BiLSTM is distilled on the silver data generated using
SenTScore, it outperforms even the original teacher model. We notice that the
difference between student and teacher decreases for larger gold set size,
suggesting that the effect is related to regularization properties of the
distillation process. A similar phenomenon has been observed elsewhere, for
instance in Furlanello et al. (2018) albeit with teacher and student sharing
the same architecture.

In order to isolate the benefits of training the teacher model using KD as
opposed to just pseudo-labels, we perform a set of ablation studies. For each
dataset, we distill a BiLSTM student on a training set
$\mathcal{T}=\mathcal{G}\cup\mathcal{S}$, where $\mathcal{G}$ is the original
gold set and $\mathcal{S}$ is a random sample from the complement of
$\mathcal{G}$. We choose $|\mathcal{S}|=0,250,500$. The student is distilled
using Eq. 2 with two choices of the loss multipliers: $\lambda_{KL}=1$ and
$\lambda_{KL}=0$. The first setting is the same used in Tables 4(a) and 4(b),
while the second drops the KD loss and only keeps the pseudo-labels for
distillation. Whenever pseudo-labels and scores are used, they are generated
by the SenTScore algorithm.

The results are shown in Tables 5 and 6. We see a consistent trend in which KD
outperforms training the student using only pseudo-labels. This in particular
motivates SenTScore as an inference algorithm. The results also show that for
our choice of teacher and student architectures, and datasets, the gap between
KD and pseudo-labels is reduced when more silver data are used. Figure 1
further explores the relationship between amount of pseudo-labeled data and
gains from KD with $|\mathcal{S}|=0,250,500,2000$.

Figure 1: A graphical representation of the distillation results in Table 4(a)
(100/50 gold train/dev split) as a function of the size of the silver dataset.
Knowledge distillation using SenTScore generated scores outperforms pseudo-
labels.

The trend with more pseudo-labeled data remains unchanged.

##  7 Limitations and future work

A reasonable critique to our focus on real-world constraints is the simple
fact the datasets we are using are not real-world ones. From noise to
tokenization choices, many issues arise when considering datasets outside of
the academic domain. However, we believe our methods are simple enough to be
applicable to real-world scenarios and our results to be independent of these
various subtleties.

Some issues that could be addressed in future work have to do with the
exploration of even larger models and different architectures such as decoder-
only ones Radford et al. (2018, 2019); Brown et al. (2020); Zhang et al.
(2022); Chowdhery et al. (2022); Black et al. (2021). We note, however, that
in all our experiments we finetune all the weights of the pretrained models we
use. When using extremely large models this becomes impractical. Recent work
Turc et al. (2019) suggests that KD with compact encoder-only student models,
such as BERT, is a promising avenue for further research. Exploring the pure
few-shot scenario, or only finetuning a subnetwork, for instance by using
adapters à la Houlsby et al., 2019, would be also interesting.

##  8 Conclusion

Real-time systems need to find a trade-off between performances and computing
resources, the latter constraint coming either from budget or some other
service requirement. Such trade-offs become particularly evident with large
pretrained transformer models, which achieve SOTA results on many NLP tasks at
the cost of being extremely hard and expensive to deploy in a real-world
setting.

The standard solution for this is distillation. In this paper we have
revisited these issues for the SL task, which is often the first crucial step
in many real-world NLP pipelines. We propose a new inference algorithm,
SenTScore, that allows us to leverage the performance of arbitrarily large
encoder-decoder transformer architectures by distilling them into simpler
sequence taggers using KD as opposed to just pseudo-labelling.

## Ethical considerations

The intended use of our proposed approach is related to sequence labelling
tasks where there are latency constraints and limited labelled data available.
While it is not impossible to identify potential misuses of this technology,
it is not immediately clear what those malicious uses would be. On the
contrary, this paper contributes to the body of work investigating efficient
solutions for deployment of live systems.

### Computing infrastructure and computational budget

All of our experiments were run on single V100 GPU machines with 32GB. The
most expensive experiments relate to finetuning a model, including best
checkpoint selection. In this case, the running time is directly related to
the dataset size. For the experiments using the full train/dev set, running
time varies from 45 minutes (mATIS corpus) to a few hours (mTOD corpus) for a
T5-base model. Training a model takes, on average, around 4 iterations per
second with batch size 32. For the generation of pseudo-labels, we did not
implement batch processing and it takes around 0.15 seconds to annotate each
sample.

## References

  * (1) SLS corpora.  https://groups.csail.mit.edu/sls/downloads/.  Accessed: 2022-09-09.
  * Artetxe et al. (2021) Mikel Artetxe, Shruti Bhosale, Naman Goyal, Todor Mihaylov, Myle Ott, Sam Shleifer, Xi Victoria Lin, Jingfei Du, Srinivasan Iyer, Ramakanth Pasunuru, Giri Anantharaman, Xian Li, Shuohui Chen, Halil Akin, Mandeep Baines, Louis Martin, Xing Zhou, Punit Singh Koura, Brian O’Horo, Jeff Wang, Luke Zettlemoyer, Mona Diab, Zornitsa Kozareva, and Ves Stoyanov. 2021.  Efficient large scale language modeling with mixtures of experts.
  * Athiwaratkun et al. (2020) Ben Athiwaratkun, Cicero Nogueira dos Santos, Jason Krone, and Bing Xiang. 2020\.  Augmented natural language for generative sequence labeling.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 375–385, Online. Association for Computational Linguistics.
  * Black et al. (2021) Sid Black, Gao Leo, Phil Wang, Connor Leahy, and Stella Biderman. 2021.  GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh-Tensorflow.  If you use this software, please cite it using these metadata.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Bucilua et al. (2006) Cristian Bucilua, Rich Caruana, and Alexandru Niculescu-Mizil. 2006.  Model compression.  In _Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’06, page 535–541, New York, NY, USA. Association for Computing Machinery.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_.
  * Coucke et al. (2018) Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy, Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone, Thibaut Lavril, Maël Primet, and Joseph Dureau. 2018.  Snips voice platform: an embedded spoken language understanding system for private-by-design voice interfaces.
  * De Cao et al. (2020) Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. 2020.  Autoregressive entity retrieval.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Furlanello et al. (2018) Tommaso Furlanello, Zachary C. Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar. 2018.  Born again neural networks.
  * Goo et al. (2018) Chih-Wen Goo, Guang Gao, Yun-Kai Hsu, Chih-Li Huo, Tsung-Chieh Chen, Keng-Wei Hsu, and Yun-Nung Chen. 2018.  Slot-gated modeling for joint slot filling and intent prediction.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 753–757, New Orleans, Louisiana. Association for Computational Linguistics.
  * Hemphill et al. (1990) Charles T. Hemphill, John J. Godfrey, and George R. Doddington. 1990.  The ATIS spoken language systems pilot corpus.  In _Speech and Natural Language: Proceedings of a Workshop Held at Hidden Valley, Pennsylvania, June 24-27,1990_.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015.  Distilling the knowledge in a neural network.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.
  * Houlsby et al. (2019) Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. 2019.  Parameter-efficient transfer learning for NLP.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2790–2799. PMLR.
  * (17) Huggingface.  Models - Hugging Face.
  * Jiao et al. (2020) Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. 2020.  TinyBERT: Distilling BERT for natural language understanding.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 4163–4174, Online. Association for Computational Linguistics.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016.  Neural architectures for named entity recognition.
  * Li et al. (2021) Haoran Li, Abhinav Arora, Shuohui Chen, Anchit Gupta, Sonal Gupta, and Yashar Mehdad. 2021.  MTOP: A comprehensive multilingual task-oriented semantic parsing benchmark.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 2950–2962, Online. Association for Computational Linguistics.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Fixing weight decay regularization in adam.  _ArXiv_ , abs/1711.05101.
  * Mukherjee and Hassan Awadallah (2020) Subhabrata Mukherjee and Ahmed Hassan Awadallah. 2020.  XtremeDistil: Multi-stage distillation for massive multilingual models.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2221–2234, Online. Association for Computational Linguistics.
  * Paolini et al. (2021) Giovanni Paolini, Ben Athiwaratkun, Jason Krone, Jie Ma, Alessandro Achille, Rishita Anubhai, Cicero Nogueira dos Santos, Bing Xiang, and Stefano Soatto. 2021\.  Structured prediction as translation between augmented natural languages.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  GloVe: Global vectors for word representation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1532–1543, Doha, Qatar. Association for Computational Linguistics.
  * Qin and Joty (2021) Chengwei Qin and Shafiq Joty. 2021.  Lfpt5: A unified framework for lifelong few-shot language learning based on prompt tuning of t5.
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, and Tim Salimansand Ilya Sutskever. 2018.  Improving language understanding by generative pre-training.  https://www.cs.ubc.ca/~amuham01/LING530/papers/radford2018improving.pdf.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Stuskever. 2019.  Language models are unsupervised multitask learners.  Technical report, OpenAI.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Raman et al. (2022) Karthik Raman, Iftekhar Naim, Jiecao Chen, Kazuma Hashimoto, Kiran Yalasangi, and Krishna Srinivasan. 2022.  Transforming sequence tagging into a seq2seq task.
  * Schuster et al. (2019) Sebastian Schuster, Sonal Gupta, Rushin Shah, and Mike Lewis. 2019.  Cross-lingual transfer learning for multilingual task oriented dialog.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 3795–3805, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Shleifer and Rush (2020) Sam Shleifer and Alexander M. Rush. 2020.  Pre-trained summarization distillation.
  * (32) StanfordNLP.  GloVe: Global Vectors for Word Representation.
  * Tang et al. (2019) Raphael Tang, Yao Lu, Linqing Liu, Lili Mou, Olga Vechtomova, and Jimmy Lin. 2019\.  Distilling task-specific knowledge from bert into simple neural networks.
  * Tjong Kim Sang and De Meulder (2003) Erik F. Tjong Kim Sang and Fien De Meulder. 2003.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003_ , pages 142–147.
  * Turc et al. (2019) Iulia Turc, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Well-read students learn better: On the importance of pre-training compact models.
  * Xue et al. (2022) Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. 2022.  Byt5: Towards a token-free future with pre-trained byte-to-byte models.  _Transactions of the Association for Computational Linguistics_ , 10:291–306.
  * Xue et al. (2021) Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. 2021.  mT5: A massively multilingual pre-trained text-to-text transformer.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 483–498, Online. Association for Computational Linguistics.
  * Yan et al. (2021) Hang Yan, Tao Gui, Junqi Dai, Qipeng Guo, Zheng Zhang, and Xipeng Qiu. 2021.  A unified generative framework for various NER subtasks.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 5808–5822, Online. Association for Computational Linguistics.
  * Zhang et al. (2022) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. 2022.  Opt: Open pre-trained transformer language models.


# About block-parallel Boolean networks: a position paper

Jacques Demongeot1, Sylvain Sené2
${}^{1}~{}$Université Grenoble Alpes, AGEIS EA 7407, 38000, Grenoble, France
${}^{2}~{}$Aix-Marseille Univ., Toulon Univ., CNRS, LIS UMR7020, Marseille,
France

###### Abstract

In automata networks, it is well known that the way entities update their
states over time has a major impact on their dynamics. In particular,
depending on the chosen update schedule, the underlying dynamical systems may
exhibit more or less asymptotic dynamical behaviours such as fixed points or
limit cycles. Since such mathematical models have been used in the framework
of biological networks modelling, the question of choosing appropriate update
schedules has arised soon. In this note, focusing on Boolean networks, our aim
is to emphasise that the adequate way of thinking regulations and genetic
expression over time is certainly not to consider a wall segregating
synchronicity from asynchronicity because they actually complement rather
well. In particular, we highlight that specific update schedules, namely
block-parallel update schedules, whose intrinsic features are still not known
from a theoretical point of view, admit realistic and pertinent properties in
the context of biological modelling and deserve certainly more attention from
the community.
_Keywords:_ Discrete dynamical systems Automata networks Threshold Boolean
networks Block-parallel updating schedules.

##  1 Introduction

Automata networks (ANs) are discrete dynamical systems, introduced in 1943 by
McCulloch and Pitts [MP43], widely used to model genetic control networks and
more generally biological networks since the end of the 1970’s and the seminal
works of Kauffman [Kau69a, Kau69b, Kau74] and Thomas [Tho73, Tho78, Tho81]. In
this context of molecular systems biology, the ANs considered are finite,
_i.e._ , they are composed of a finite number of nodes (or automata) that
interact with each other over a discrete time.

As soon as they have been used as models of genetic regulation networks, the
way that nodes had to be updated over time was discussed. Indeed, when
Kauffman introduced them at the end of the 1960’s by scheduling nodes in
parallel (certainly due to mathematical usabilities), biological arguments
were highlighted notably by Thomas arguing that parallelism was not likely
because of the impossibility for genetic expressions to occur simultaneously.
Of course, the links between parallelism and simultaneity could be discussed
further in the context of modelling but this is not the purpose of this note.
So, other ways of updating ANs were introduced that are located at the other
end of the spectrum, based on the concept of asynchronicity such as the
asynchronous method of Thomas et al. [RR08, Tho73, Tho91], and random
sequential ANs [Dem87, Ger03, HB97, SS05]. This created a strong separation
between the synchronous and sequential ways of considering ANs, to such an
extent that the schedules mixing together synchronicity and asynchronicity
were set aside for decades in the context of modelling. Fortunately, it was
not the case in mathematics and computer science, as shown in the works of
Robert [Rob69, Rob80, Rob86] on block-sequential update schedules, that were
used in [MAB98] in the framework of the modelling of the floral morphogenesis
of the plant _Arabidopsis thaliana_ and began to be studied in depth from the
second half of the 2000’s [AGMS09, DES08, Ele09].

In this note, following a natural computing approach that consists in using
the well known biologically-inspired computational model of ANs, and studying
instances of them to model real biological phenomena, our wish is to highlight
that the update schedules studied until now (all belonging to the family of
block-sequential update schedules), even if they are interesting
theoretically, are far from being sufficient to capture specific biological
intricacies. In particular, biological timers (classically called “Zeitgebers”
in biology and medicine) and clocks that can be of genetic or physiological
nature/origin [HHR90, HA92] need other ways of thinking updatings to be
modelled. Here, our very aim is to put the emphasis on block-parallel update
schedules, introduced initially in [Sen08] and never studied _per se_ until
now, by giving insights essentially, and to highlight that they have
interesting theoretical properties because of their intrinsic complexity, and
pertinent features from a modelling point of view since they allow to model
biological timers.

Section 2 recalls the basics related to ANs, and some of the seminal results
obtained in the past. In Section 3, block-parallel update schedules are
presented together with some of their very basic properties. Through two
examples coming from distinct areas of biology, Section 4 underlines the
ability of block-parallel modes to model biological timers. Finally, open
questions are given in Section 5.

##  2 Preliminary

This section presents the classical notions and definitions used and widely
studied in the literature related to Boolean networks. Of course, all of these
can be easily generalised for other alphabets and multi-valued automata
networks. Moreover, for the sake of simplicity without losing generality, we
reduce the set of Boolean networks considered to threshold Boolean networks.

#### Threshold Boolean networks

Let $V=\\{1,...,n\\}$ a set of nodes (often called automata in the
literature). A _configuration_ on $V$ is a one-to-one function
$x:V\to\mathbb{B}=\\{0,1\\}$ so that a Boolean value is associated with each
node of $V$. In other terms, a configuration $x=(x_{1},x_{2},...,x_{n})$ is a
Boolean vector of dimension $n$, where any of the $x_{i}\in\mathbb{B}$ is the
_state_ of node $i$ in configuration $x$. The discrete evolution of the local
state of node $i$ is defined as a _local transition function_

$f_{i}:\left\\{\begin{array}[]{cll}\mathbb{B}^{n}&\to&\mathbb{B}\\\
x&\mapsto&H(\sum_{j=1}^{n}w_{i,j}\cdot x_{j}(t)-\theta_{i})\\\
\end{array}\right.\text{,}$

where $W$ is the _interaction matrix_ , _i.e._ , the real-valued square matrix
of order $n$ such that coefficient $w_{i,j}$ is the weight of the influence
that node $j$ has on node $i$, $\Theta$ is the _activation vector_ , _i.e._ ,
the real-valued vector of dimension $n$ such that $\theta_{i}$ is the
activation threshold of node $i$, and $H$ is the Heaviside step function such
that $H(x)=0$ if $x<0$, and $1$ otherwise. Consequently,
$f=(f_{i})_{i\in\\{1,...,n\\}}$ is such that

$f:\left\\{\begin{array}[]{cll}\mathbb{B}^{n}&\to&\mathbb{B}^{n}\\\
x&\mapsto&H(W\cdot x-\Theta)\\\ \end{array}\right.\text{,}$

and defines the threshold Boolean network.

#### Interaction graphs

Let $f$ be a threshold Boolean network. From its interaction matrix $W$, we
can derive the _interaction graph_ $G(f)=(V,I)$, with $I\subseteq
V\times\mathbb{R}\times V$, where $(i,w_{j,i},j)\in I$ if $w_{j,i}\neq 0$.
When $w_{j,i}>0$ (resp. $w_{j,i}<0$, $w_{j,i}=0$), node $i$ tends to activate
(resp. tends to inhibit, has no influence on) node $j$. We generally speak of
positive or negative influences. Figure 1 depicts a threshold Boolean network
composed of $3$ nodes whose interaction graph is a cycle of size $3$. Notice
that this network is more precisely a canonical _positive cycle_ [DNS12,
Nou12, Sen12, Tho81], which means a cycle composed of an even number of
negative influences (not to be confused with a _negative cycle_ which would be
composed of an odd number of negative influences).

$f:$ $W=\begin{pmatrix}0&0&1\\\ 1&0&0\\\ 0&1&0\\\ \end{pmatrix}$
$\Theta=\begin{pmatrix}+\varepsilon\\\ +\varepsilon\\\ +\varepsilon\\\
\end{pmatrix}$ $+1$$+1$$3$$1$$2$$G(f):$$+1$

Figure 1: (left) Definition of a network $f$ with its interaction matrix $W$
and its threshold vector $\Theta$; (right) its associated interaction graph
$G(f)$.

#### Update schedules

In any configuration of a network, one or several punctual events may take
place. Here, we consider events that consist in the update of at least one
node state. Supposing that the network is currently in configuration
$x\in\mathbb{B}^{n}$, node $i\in V$ is _scheduled_ if its state switches from
$x_{i}$ to $f_{i}(x)$. Remark that, possibly, $f_{i}(x)=x_{i}$ so that the
update of $i$ is not effective in $x$. In any case, this local event that we
call a _transition_ yields a global network configuration change (possibly not
effective) which is described by the _$i$ -update function_
$F_{i}:\mathbb{B}^{n}\to\mathbb{B}^{n}$ such that

$\forall x\in\mathbb{B}^{n},\ F_{i}(x)=(x_{1},\ldots
x_{i-1},f_{i}(x),x_{i+1},\ldots,x_{n})\text{.}$

This transition is said to be atomic because it involves only one automaton.
We also consider non-atomic transitions that correspond to the synchronous
update of several nodes. In the general case, the _$B$ -update
function_111$\forall i\in V,\,F_{i}$ obviously equals $F_{\\{i\\}}$.
$F_{B}:\mathbb{B}^{n}\to\mathbb{B}^{n}$ describes the network configuration
change that results in the update of all the nodes of the subset (or block)
$B$ of $V$ such that

$\forall x\in\mathbb{B}^{n},\ \forall i\in V,\
F_{B}(x)_{i}=\begin{cases}f_{i}(x)&\text{if }i\in B\\\
x_{i}&\text{otherwise}\end{cases}\text{.}$

An _update schedule_ $\delta$ of a network whose set of nodes is $V$ is
defined by an ordered (finite or infinite) sequence
$(B_{i})_{i\in\\{0,\ldots,t-1\\}}$ of $t$ non-empty subsets of nodes. We write
$\delta=(B_{i})_{i\in\\{0,\ldots,t-1\\}}$ or just
$\delta=(B_{0},B_{1},\ldots,B_{t-1})$. Under an update schedule $\delta$,
starting in configuration $x\in\mathbb{B}^{n}$, a network takes sequentially
the configurations $x^{0}=F_{B_{0}}(x)$, $x^{1}=F_{B_{1}}\circ F_{B_{0}}(x)$,
$\ldots$, $x^{t-1}=F_{B_{t-1}}\circ\ldots\circ F_{B_{0}}(x)$.

_Periodic update schedules_ of arbitrary period $p\in\mathbb{N}$ are infinite
periodic sequences
$(B_{0},B_{1},\ldots,B_{p-1},B_{0},B_{1},\ldots,B_{p-1},\ldots)$. For the sake
of simplicity, they are rather defined by finite ordered lists
$(B_{i})_{i\in\mathbb{N}/p\mathbb{N}}$ of size $p$:
$\delta=(B_{0},B_{1},\ldots,B_{p-1})$. When $\bigcup_{i=0}^{p-1}B_{i}=V$, such
update schedules are called _fair update schedules_ and are strong ergodic
update schedules, the latter being defined as: there exists $m\in\mathbb{N}$
such that every node is updated in the time interval $\llbracket
k;k+m\rrbracket,\ \forall k\in\mathbb{N}$. _Global transition functions_
$F[\delta]:\mathbb{B}^{n}\to\mathbb{B}^{n}$ related to such periodic update
schedules are defined as

$\forall x\in\mathbb{B}^{n},\ F[\delta](x)=F_{B_{p-1}}\circ\ldots\circ
F_{B_{1}}\circ F_{B_{0}}(x)\text{.}$

Such very update schedule has never been studied in depth, certainly because
of their inherent generality and underlying complexity. Remark nevertheless
that they have been mentioned in [GN12].

Well known instances of periodic update schedules are _block-sequential
schedules_ [DES08, Ele09, GN10, GN12, Rob86, Rob95]. Their particularity lies
in that their periodic sequence of updates involves exactly once each
automaton of the network. Formally, a block-sequential update schedule of a
network of node set $V$ is an ordered partition $P$ of $V$. With our
notations, it can be defined as a finite sequence
$(B_{i})_{i\in\mathbb{N}/p\mathbb{N}}$ such that
$V=\bigsqcup_{{i\in\mathbb{N}/p\mathbb{N}}}B_{i}$. It can also be defined as a
function $\delta:V\to\mathbb{N}/p\mathbb{N}$. The _parallel update schedule_
is the unique block-sequential update schedule of period $p=1$ ($\forall i\in
V,\ \delta(i)=1$). It updates all the nodes of the network at each time step,
simultaneously. The $n!$ _sequential update schedules_ [MR01, Rei06] are
block-sequential update schedules with period equal to the size of the network
($p=n$). They update only one node of the network at a time ($\forall
i\in\mathbb{N}/p\mathbb{N},\ |B_{i}|=1$). For the sake of clarity, when a
network is subjected to a block-sequential schedule
$\delta=(B_{i})_{i\in\mathbb{N}/p\mathbb{N}}$, the nodes inside a subset of
$P$ are updated simultaneously and the subsets are iterated sequentially at
each time step, from $B_{0}$ to $B_{p-1}$.

$\geq$$\geq$$3$$1$$2$$\geq$ $<$$\geq$$3$$1$$2$$\geq$ $<$$\geq$$3$$1$$2$$<$

Figure 2: Update graphs of the network $f$ defined in Figure 1: (left)
Parallel update graph $\mathscr{U}_{(\\{1,2,3\\})}(f)$; (centre) Block-
sequential update graph $\mathscr{U}_{(\\{1,2\\},\\{3\\})}(f)$; (right)
Sequential update graph $\mathscr{U}_{(\\{1\\},\\{2\\},\\{3\\})}(f)$.

A non-classical way (but quite useful for proofs related to robustness of
update schedules) to represent a block-sequential update schedule is the
update graph introduced by Aracena et al. in [ADFM13a, ADFM13b, AFMN11,
AGMS09, AGS13]. On the basis of $f$ a threshold Boolean network and the
unlabelled version of its interaction graph $G^{\prime}(f)=(V,I^{\prime})$,
where $I^{\prime}=\\{(i,j)\ |\ (i,w_{j,i},j)\in I\\}_{i,j\in V}$, a labelled
graph $(G^{\prime}(f),\text{lab})$ is defined, with
$\text{lab}:I^{\prime}\to\\{<,\geq\\}$. Given a block-sequential update
schedule $\delta$ (seen as a function $\delta:V\to\mathbb{N}/p\mathbb{N}$),
$U_{\delta}(f)=(G^{\prime}(f),\text{lab})$ is the update graph associated with
$\delta$ if:

$\forall(i,j)\in I^{\prime},\ \text{lab}(i,j)=\begin{cases}\geq&\text{if
}\delta(i)\geq\delta(j)\\\ <&\text{if }\delta(i)<\delta(j)\end{cases}\text{.}$

An illustration of the concept of update graphs is given in Figure 2. From
this update graph, Aracena et al. obtained the following very interesting
result that gives strong insights on the role of block-sequential update
schedules on the possible dynamical behaviours of a network.

######  Theorem 1 (Aracena et al. [AGMS09]).

Let $f$ be a Boolean network. Let $\delta_{1}$ and $\delta_{2}$ be two block-
sequential update schedules. If $U_{\delta_{1}}(f)=U_{\delta_{2}}(f)$ then
$F[\delta_{1}]=F[\delta_{2}]$.

#### Transition graphs

Given a network $f$ and a block-sequential update schedule $\delta$, the
related _transition graph_ is
$\mathscr{G}_{\delta}(f)=(\mathbb{B}^{n},T_{\delta})$, whose nodes are network
configurations and arcs are network transitions such that
$T_{\delta}\subseteq\mathbb{B}^{n}\times\mathbb{B}^{n}$. Formally, if
$\delta=(B_{i})_{i\in\mathbb{N}/p\mathbb{N}}$,

$\mathscr{G}_{\delta}(f)=(\mathbb{B}^{n},T_{\delta})\text{ where
}T_{\delta}=\\{(x,F[\delta](x))\ |\ x\in\mathbb{B}^{n}\\}\text{.}$

A transition graph $\mathscr{G}_{\delta}(f)$ represents the dynamics over time
of network $f$ associated with update schedule $\delta$ (see Figure 3). From
this graph, given a configuration $x\in\mathbb{B}^{n}$, the _trajectory_ of
$x$ is the path (_i.e._ , the transition sequence) that starts in $x$. Since
the number of configurations is finite and $F[\delta]$ is a deterministic one-
to-one function mapping $\mathbb{B}^{n}$ to itself, the trajectory of $x$
necessary ends up in a cycle of configurations, called an attractor. In this
framework, an _attractor_ can be either a _fixed point_ of $F[\delta]$ (_i.e._
, a stable configuration that repeats endlessly), or a _limit cycle_ of
$F[\delta]$ (_i.e._ , a sequence of recurrent configurations that repeats
endlessly). Remark that, from a more applied point of view, a transition graph
could be restricted to specific strict subsets of $V$ depending on the
observability of the node states from which it could be relevant to compute
and/or extract the related restricted attractors. Moreover, notice also that a
transition graph can be extended by integrating all the intermediary visited
configurations resulted from the application of $F_{B_{i}}$, $\forall
B_{i}\in(B_{i})_{i\in\mathbb{N}/p\mathbb{N}}$. It is then called a _complete
transition graph_.

Let us recall now seminal and general theoretical results on _(i)_ the
computable features and _(ii)_ the relations between the static (syntactic)
and dynamical (semantic) properties of networks.

######  Theorem 2 (Goles and Martinez [GM90]).

The computational model of Boolean networks is Turing-complete.

######  Theorem 3 (Goles and Martinez [GM90]).

Let $f$ be a Boolean network, $\pi$ the parallel update schedule and $\delta$
an arbitrary update schedule. If $x\in\mathbb{B}^{n}$ is a fixed point of
$F[\pi]$, then $x$ is a fixed point of $F[\delta]$.

Notice that the reciprocal of Theorem 3 is not true. A simple illustration of
this consists in considering the positive cycle presented in Figure 1 that
admits two fixed points, $000$ and $111$, when scheduled block-sequentially,
and that admits the four following fixed points $000$, $010$, $101$, and $111$
when scheduled according to $\delta=(\\{2,3\\},\\{1,3\\},\\{1,2\\})$.

######  Theorem 4 (Robert [Rob86, Rob95]).

Let $f$ be a Boolean network associated with a directed acyclic interaction
graph. Whatever the update schedule $\delta$, $F[\delta]$ admits a unique
attractor that is a stable configuration.

The following theorem gives a strong global relation between interaction
graphs and the existence of multi-stationarity of the underlying dynamical
systems. It originally comes from a conjecture of Thomas presented in [Tho81],
was proven in the context of block-sequential update schedules by Aracena
[ADG04] and then in the context of Thomas’ asynchronous representation in
[RRT08, RC07] before it was proven generally for any kind of update schedule
by Noual and Sené in [Nou12, Sen12].

######  Theorem 5.

Let $f$ be a Boolean network and $G(f)$ its associated interaction graph.
Whatever the update schedule $\delta$, if $F[\delta]$ admits several stable
configurations then $G(f)$ contains a positive cycle.

$111$$011$$101$$110$$000$$001$$100$$010$
$000$$111$$100$$011$$010$$101$$001$$110$
$000$$111$$010$$100$$110$$001$$011$$101$

Figure 3: Periodic dynamics of the network $f$ defined in Figure 1: (left)
Parallel graph transition $\mathscr{G}_{(\\{1,2,3\\})}(f)$; (centre) Block-
sequential graph transition $\mathscr{G}_{(\\{1,2\\},\\{3\\})}(f)$; (right)
Sequential graph transition $\mathscr{G}_{(\\{1\\},\\{2\\},\\{3\\})}(f)$.

##  3 Block-parallel threshold Boolean networks

In the previous section, we have emphasised that fair update schedules are
very interesting from a theoretical point of view. Indeed, given a network $f$
and its interaction graph $G(f)=(V,I)$, they can make emerge peculiar
asymptotic dynamics, such as stable configurations that are not fixed points
of the parallel global transition function $F[(V)]$. However, on the one hand,
such an intrinsic mathematical richness seems to be too much important from a
more applied point of view directed toward the qualitative modelling of
genetic regulation networks. Conversely, on the other hand, block-sequential
update schedules are not sufficiently rich to model specific observed
biological abilities. In particular, there exist some examples of genetic
regulation networks in which a specific subnetwork plays a role of “Zeitgeber”
(_i.e._ , a timer) having its own clock. For instance, in Drosophila, this
subnetwork consists in a small set of genes like TIME and PER [Gol95, HHR90,
SPMY94] exhibiting as its unique attractor a limit cycle with its proper free-
run period. This subnetwork influences other groups of genes, each of them
having their own biological functionalities. Such a time command cannot be
modelled by the classically studied block-sequential update schedules, simply
because they prevent from having update repetitions of nodes in a same period
of updates. Nevertheless, it can be modelled by another family of fair update
schedules that we call block-parallel update schedules which are the topic of
this note.

Where a network $f$ scheduled block-sequentially evolves so that the nodes are
updated simultaneously inside a block and the blocks themselves are iterated
sequentially, a network scheduled block-parallelly evolves conversely. The
blocks are iterated simultaneously and the nodes inside them are updated
sequentially. In other terms, where a block-sequential update schedule is
defined by an ordered partition of $V$ (_i.e._ , a finite sequence of non-
empty and disjoint subsets of $V$ recovering $V$), a block-parallel update
schedule is defined by a set of non-empty and disjoint finite sub-sequences
$S_{i}$ of $V$ whose union of elements recovers $V$. Thus, a block-parallel
update schedule can be formally defined as
$\delta=\\{S_{i}\\}_{i\in\\{0,\ldots,|\delta|-1\\}}$, such that
$1\leq|\delta|\leq|V|$. Remark that if $|\delta|=1$ (resp. $|\delta|=|V|$),
$\delta$ is a sequential (resp. the parallel) update schedule. Furthermore,
notice that this definition satisfies the assumptions of a fair update
schedule. Indeed, there exists a rewriting of any block-parallel update
schedule into a finite sequence of subsets of $V$, complying with the
dynamical properties of the underlying network. For instance, consider an
arbitrary network of size $6$ with $V=\\{1,...,6\\}$ and the following block-
parallel update schedule: $\\{(1),(2,3),(4,5,6)\\}$. The updatings along time
of node states follow Figure 4(left), which corresponds exactly to the
following finite sequence of subsets of $V$:

$(\\{1,2,4\\},\\{1,3,5\\},\\{1,2,6\\},\\{1,3,4\\},\\{1,2,5\\},\\{1,3,6\\})\text{.}$

A block-parallel update schedule can also be represented by a graph
$\delta\equiv(V,A)$ that is simply the partial order graph associated with the
partial order of the anteriorities defined by $\delta$ (see Figure 4(right)).

$1$$0$$2$$1$$1$$1$$1$$1$$1$$1$$1$$1$$3$$2$$2$$2$$2$$3$$3$$3$$5$$6$$4$$4$$4$$5$$5$$6$$6$$5$$t$$1$$2$$3$$4$$5$$6$

Figure 4: (left) Time diagram of the updates and (right) partial order graph
of the anteriorities defined from the block-parallel update schedule
$\delta=\\{(1),(2,3),(4,5,6)\\}$.

Remark that block-parallel and block-sequential update schedules are distinct
families of fair update schedules having a non-empty intersection made only of
the block-sequential update schedules whose subsets have the same cardinality.
Moreover, the union of these two families does not coincide with fair update
schedules. Consider for instance a network $f$ of $3$ elements and
$\delta=\\{(0,1),(1,2),(0,1,2)\\}$ that is not a block-parallel one since the
sub-sequences are not disjoint. Its rewriting as a sequence of subsets is
$(\\{0,1\\},\\{1,2\\},\\{0,1,2\\},\\{0,1,2\\},\\{0,1\\},\\{1,2\\})$ which does
not correspond to a block-sequential update schedule. However, it respects the
definition of a fair update schedule.

##  4 Applications to biology

Now the block-parallel update schedules have been introduced, let us highlight
their relevance in the qualitative modelling of biological regulation
networks. We present two applications, the first one in genetics and the
second one in physiology.

###  4.1 Genetic control of plant growth

The first example of a timer is the biological clock ruling the plant growth.
A very schematic view of the functioning of the genetic control of the plant
growth is to consider two components evolving independently. The first one can
be modelled as a sub-network made of three genes that correspond to the
localised expressions of the protein auxin (one of the plant growth
regulators). The first gene AUX$a$ corresponds to the apical localisation, the
others correspond to the axillary bud localisations, AUX$\ell$ for the left
bud and AUX$r$ for the right bud. The second one can be modelled as a sub-
network localised in the cotyledon and composed of two genes: CCA (Circadian
Clock Associated gene) and TOC (Timing Of CAB expression gene).

$f:$ $W=\begin{pmatrix}1&-2&-2&-2&0\\\ -2&1&-2&-2&0\\\ -2&-2&1&-2&0\\\
0&0&0&1&-2\\\ 0&0&0&1&0\end{pmatrix}$ $\Theta=\begin{pmatrix}-\varepsilon\\\
-\varepsilon\\\ -\varepsilon\\\ -\varepsilon\\\ \varepsilon\end{pmatrix}$
$-2$$-2$$-2$$-2$$+1$$4$$5$$+1$$+1$$-2$$-2$$-2$$-2$$-2$$-2$$+1$$+1$$G(f):$$3$$1$$2$

Figure 5: (left) Definition of the genetic network controlling the plant
growth $f$ with its interaction matrix $W$ and its threshold vector $\Theta$;
(right) its associated interaction graph $G(f)$.

The dynamics of the plant growth is governed by the threshold Boolean network
$f$ where AUX$a\equiv 1$, AUX$\ell\equiv 2$, AUX$r\equiv 3$, CCA $\equiv 4$
and TOC $\equiv 5$, defined in Figure 5 which is derived from [BMH15, TDN+04].
Now, the idea is to focus only on the most realistic initial conditions for
computing the dynamical behaviour. These conditions have to integrate the
following biological observations:

  * •

In the first component, the apical auxin is the first expressed during the
plant growth. The other left and right bud auxins start at state $0$ because
the axillary buds are still not existing.

  * •

In the second component, CCA is induced by photosynthesis (it starts at state
$1$) and activates secondarily TOC [BMH15].

As a consequence, the most realistic initial configuration is $100\,10$. Let
us consider now the update schedule. First of all, concerning the timer
component, whatever the local update schedule, its dynamics remains the same.
So, for the sake of simplicity, we have chosen that CCA and TOC evolve
simultaneously. Now, concerning the auxin component, the messages transmitted
from AUX$a$ to AUX$\ell$ corresponds to the diffusion along the stem of the
auxin expressed by the gene AUX$a$. The same process can be observed between
AUX$\ell$ and AUX$r$. As a consequence, a natural local update schedule for
this component is the sequential one
$(\\{\text{AUX}a\\},\\{\text{AUX}\ell\\},\\{\text{AUX}r\\})$. To sum up, a
realistic global update schedule of $f$ is the following block-parallel one:

$\delta=\\{(1,2,3),(4),(5)\\}\ \iff\
\delta=(\\{1,4,5\\},\\{2,4,5\\},\\{3,4,5\\})\text{,}$

whose partial order graph is

$4$$5$$1$$2$$3$

Exploiting all the knowledge given above about the networks, its interaction
graph and block-parallel update schedule, the trajectory of the initial
configuration is given in Figure 6(left). It leads to a limit cycle of period
$4$ (resp. of period $12$ if we consider it in the complete transition graph
as it is the case in Figure 6 (left)) starting in $01\,000$, whose internal
structure made of every intermediary configuration comes from the combination
of the three fixed points of the auxin component and of the limit cycle of
period $4$ of the timer component. Notice also that the sequential growth of
the three parts of the plant is correctly induced, in a uniform way. This
regular scheme of growth could correspond to the quasi-perfect growth of
_Araucaria araucana_ which consists in the succession of triplets made of a
central and two lateral stems, as illustrated in Figure 6(right).

$100\,10{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>000\,11\to 000\,01}\\\
\to\mathbf{010\,00}{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\to\mathbf{010\,10}\to\mathbf{010\,11}}\\\
\to\mathbf{000\,01}{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\to\mathbf{100\,00}\to\mathbf{100\,10}}\\\
\to\mathbf{100\,11}{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\to\mathbf{000\,01}\to\mathbf{001\,00}}\\\
\to\mathbf{001\,10}{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\to\mathbf{001\,11}\to\mathbf{000\,01}}\\\
\to 010\,00$

Figure 6: (left) Trajectory of configuration $100\,10$ of network modelling
the genetic control of plant growth governed by the biological timer made of
CCA and TOC; (right) Example of the growth of _Araucaria araucana_ made by the
succession the triplets corresponding to an apical and two lateral stems.

###  4.2 Cardio-respiratory regulation

The second example of a timer is the biological clock ruling the cardio-
respiratory regulation. As for the plant growth, the functioning of the
physiological process of this regulation can be described by two components.
The first one corresponds to the central vegetative system and plays the role
of a timer. It comprises inspiratory ($I$) and expiratory ($E$) neurons. The
second component is peripheral. It comprises the sino-atrial node ruling the
heart activity ($S$) and the baroreceptor located at the exit the left
ventricle ($B$).

The dynamics of the cardio-respiratory regulation is governed by the network
$g$ where $E\equiv 1$, $I\equiv 2$, $B\equiv 3$, and $S\equiv 4$, defined in
Figure 7 and derived from [Bea01, DKI+, DGNM10, MMZ14]. Here also, let us
consider the realistic initial condition $00\,00$ that corresponds to the end
of an expiration just before the activity start of inspiratory neurons, and to
low levels of the sino-atrial and baroreceptor activities.

The local updating schedule of the timer is similar to that of a plant growth.
That of the second component comes from the information transmission from $S$
to $B$ thanks to the blood flow. It is consequently sequential and defined by
$(\\{S\\},\\{B\\})$. To sum up, the realistic global update schedule of $g$ is
the following block-parallel one:

$\delta=\\{(1),(2),(4,3)\\}\ \iff\ \delta=(\\{1,2,4\\},\\{1,2,3\\})\text{.}$

The trajectory of initial realistic configuration $00\,00$ is

$00\,00{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>01\,00}\to
11\,00{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>10\,01}\\\
\to\mathbf{00\,11}{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\to\mathbf{01\,11}}\to\mathbf{11\,01}{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\to\mathbf{10\,01}}\\\
\to 00\,11\text{.}$

It suggests that the cardio-respiratory network presents a limit-cycle of
period $2$ (resp. of period $4$ if we consider it in the complete transition
graph as it is the case above with black and gray bold configurations)
decomposed into two phases as in the real biological functioning. It is
composed of the succession of the activity periods of the two families of
central neurons ($E$ and $I$) that are both inactive and then active, and that
can hence trigger the two intermediary inspiratory and expiratory phases. For
the peripheral activity, we can observe a constant sino-atrial activity
inducing an important cardiac activity at the end of the expiration and during
the inspiration that is reduced after the inspiration and during the
expiration. Such an observation could refer to the idea of a qualitative model
for the well known phenomenon called cardiac sinusal arrhythmia.

A relevant characteristics of the network $g$ is that the reduction of the
influence of the sino-atrial node on itself, by changing $w_{4,4}=2$ to
$w_{4,4}=1$ suffices to retrieve the normal cardiac functioning with no sinus
arrhythmia. Indeed, in this case, the trajectory of $00\,00$ becomes:

$00\,00{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>01\,00}\to\mathbf{11\,00}{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\to\mathbf{10\,01}}\\\
\to\mathbf{00\,11}{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\to\mathbf{01\,10}}\to
11\,00\text{.}$

However, this trajectory highlights a phase shifting of the cardiac activity
with respect to the firing of respiratory neurons of the vegetative system,
which does not comply with the biological assumptions. As a consequence, a
refining of the model seems to be required, which paves the way for further
modelling studies.

$g:$ $W=\begin{pmatrix}0&2&0&-1\\\ -2&1&1&0\\\ 0&-1&0&1\\\ 1&0&-1&2\\\
\end{pmatrix}$ $\Theta=\begin{pmatrix}\varepsilon\\\ -\varepsilon\\\
\varepsilon\\\ \varepsilon\\\ \end{pmatrix}$
$3$$G(g):$$+1$$2$$+1$$+1$$4$$1$$-1$$-2$$+2$$-1$$+1$$-1$$+1$

Figure 7: (left) Definition of the physiologic network $g$ controlling the
cardio-respiratory regulation with its interaction matrix $W$ and its
threshold vector $\Theta$; (right) its associated interaction graph $G(g)$.

##  5 Conclusion and open problems/questions

This position paper aimed at putting the focus on block-parallel schedules and
highlighting especially their ability to model autonomous timers that govern
the dynamics of impacted sub-networks, for underlining their pertinence from a
biological modelling point of view with respect to “Zeitgebers” (timers).
Beyond the modelling interest, these modes seem also to have very interesting
theoretical properties that deserve without any doubt to be studied in depth
from mathematical and theoretical computer science points of view, as it has
been the case for block-sequential update schedules. Eventually, in order to
illustrate our purpose, let us present open problems/questions which, if
addressed, could lead to relevant advances in both theoretical and applied
frameworks:

  * •

In [GN10], the authors showed that any block-sequential isolated positive or
negative cycle can be simulated by a smaller parallel cycle of same sign. So,
a natural question is to understand if a similar property holds for block-
parallel and another schedule that the parallel one. Indeed, it is easy to see
that the repetition of at least one node updating is a lock here and that
consequently, generally speaking, a block-parallel cycle cannot be simulated
by a smaller parallel cycle. As a consequence, the open question is: as the
parallel is the canonical block-sequential update schedule for Boolean cycles,
does there exist a canonical block-parallel update schedule?

  * •

In [DNS12], by basing themselves on the result of [GN10], the authors proved
all the combinatorial transient and asymptotic properties of parallel Boolean
cycles. If a positive answer is found to the previous open question leading to
the definition of a canonical block-parallel update schedules, it will be
crucial to lead a similar combinatorial study to obtain a perfect knowledge of
cycles in this context since the latter remain important in this framework in
terms of dynamical complexity.

  * •

As presented in the note, in [ADFM13b, AFMN11, AGMS09], the authors introduced
block-sequential update graphs. This graph is of real interest since it allows
to know efficiently if a network associated with two block-sequential update
schedules admits an equivalent dynamics (see Theorem 1). In order to prove
similar equivalence properties in the context of block-parallel update
schedules, it seems that it would be of great interest to develop the concept
of block-parallel update graphs. Can such a concept be found? If yes, given a
network $f$ and a block-parallel update schedule $\delta$, is it as easy to
define/construct as for block-sequential update schedules?

  * •

Concerning the attractors of block-parallel models with timers of real
biological networks, are the _complete limit cycles_ (_i.e._ , the limit
cycles including intermediary configurations) always made of an alternation of
the attractors projected on the nodes of the peripheral sub-networks provoked
by the period of the limit cycle(s) of the timer(s)? Even if it seems to be
efficient, does nature tend to classically use such timers/processes to make
biological networks able to oscillate between attraction basins and thus
create functional rhythms? To answer to these questions, a statistical study
in depth of well known networks modelling biological rhythms will be
necessary.

#### Acknowledgements

The present work has been partially supported by the ANR-13-TECS-0011 project
“e-swallhome” (JD), and by the ANR-18-CE40-0002 “FANs”, the PACA-15-APEX-01134
“FRI” and the ECOS C16E01 projects (SS).

## References

  * [ADFM13a] J. Aracena, J Demongeot, É Fanchon, and M. Montalva.  On the number of different dynamics in Boolean networks with deterministic update schedules.  Mathematical Biosciences, 242:188–194, 2013.
  * [ADFM13b] J. Aracena, J Demongeot, É Fanchon, and M. Montalva.  On the number of update digraphs and its relation with the feedback arc sets and tournaments.  Discrete Applied Mathematics, 161:1345–1355, 2013.
  * [ADG04] J. Aracena, J. Demongeot, and E. Goles.  Positive and negative circuits in discrete neural networks.  IEEE Transactions on Neural Networks, 15:77–83, 2004.
  * [AFMN11] J. Aracena, É Fanchon, M. Montalva, and M. Noual.  Combinatorics on update digraphs in Boolean networks.  Discrete Applied Mathematics, 159:401–409, 2011.
  * [AGMS09] J. Aracena, E. Goles, A. Moreira, and L. Salinas.  On the robustness of update schedules in Boolean networks.  Biosystems, 97:1–8, 2009.
  * [AGS13] J. Aracena, L. Gómez, and L. Salinas.  Limit cycles and update digraphs in Boolean networks.  Discrete Applied Mathematics, 161:1–12, 2013.
  * [Bea01] T. Beauchaine.  Vagal tone, development, and Gray’s motivational theory: toward an integrated model of autonomic nervous system functioning in psychopathology.  Development and Psychopathology, 13:183–214, 2001.
  * [BMH15] C. Bendix, C. M. Marshall, and F. G. Harmon.  Circadian clock genes universally control key agricultural traits.  Molecular Plant, 8:1135–1152, 2015.
  * [Dem87] J. Demongeot.  Random automata networks.  In Automata Networks in Computer Science: Theory and Applications, pages 47–57. Princeton University Press, 1987.
  * [DES08] J. Demongeot, A. Elena, and S. Sené.  Robustness in regulatory networks: a multi-disciplinary approach.  Acta Biotheoretica, 56:27–49, 2008.
  * [DGNM10] O. Dergacheva, K. J. Griffioen, R. A. Neff, and D. Mendelowitz.  Respiratory modulation of premotor cardiac vagal neurons in the brainstem.  Respiratory Physiology & Neurobiology, 174:102–110, 2010.
  * [DKI+] J. Demongeot, H. Khlaifi, D. Istrate, L. Mégret, C. Taramasco, and R. Thomas.  From conservative to dissipative non-linear differential systems. An application to the cardio-respiratory regulation.  Submitted to _Discrete and Continuous Dynamical Systems_.
  * [DNS12] J. Demongeot, M. Noual, and S. Sené.  Combinatorics of Boolean automata circuits dynamics.  Discrete Applied Mathematics, 160:398–415, 2012.
  * [Ele09] A. Elena.  Robustesse des réseaux d’automates booléens à seuil aux modes d’itération. Application à la modélisation des réseaux de régulation génétique.  PhD thesis, Université Joseph Fourier – Grenoble, 2009.
  * [Ger03] C. Gershenson.  Classification of random Boolean networks.  In Proceedings of ICAL’03, pages 1–8. MIT Press, 2003.
  * [GM90] E. Goles and S. Martínez.  Neural and automata networks: dynamical behavior and applications.  Kluwer Academic Publishers, 1990.
  * [GN10] E. Goles and M. Noual.  Block-sequential update schedules and Boolean automata circuits.  In Proceedings of AUTOMATA’2010, DMTCS, pages 41–50, 2010.
  * [GN12] E. Goles and M. Noual.  Disjunctive networks and update schedules.  Advances in Applied Mathematics, 48:646–662, 2012.
  * [Gol95] A. Goldbeter.  A model for circadian oscillations in the Drosophila period protein (PER).  Proceedings of the Royal Society of London B: Biological Sciences, 261:319–324, 1995.
  * [HA92] J. C. Hanse and J. Ausio.  Chromatin dynamics and the modulation of genetic activity.  Trends in Biochemical Sciences, 17:187–191, 1992.
  * [HB97] I. Harvey and T. Bossomaier.  Time out of joint: attractors in asynchronous random Boolean networks.  In Proceedings of ECAL’97, pages 67–75. MIT Press, 1997.
  * [HHR90] P. E. Hardin, J. C. Hall, and M. Rosbash.  Feedback of the Drosophila period gene product on circadian cycling of its messenger RNA levels.  Nature, 343:536–540, 1990.
  * [Kau69a] S. A. Kauffman.  Homeostasis and differentiation in random genetic control networks.  Nature, 224:177–178, 1969.
  * [Kau69b] S. A. Kauffman.  Metabolic stability and epigenesis in randomly constructed genetic nets.  Journal of Theoretical Biology, 22:437–467, 1969.
  * [Kau74] S. A. Kauffman.  The large scale structure and dynamics of gene control circuits: An ensemble approach.  Journal of Theoretical Biology, 44:167–190, 1974.
  * [MAB98] L. Mendoza and E. R. Alvarez-Buylla.  Dynamics of the genetic regulatory network for Arabidopsis thaliana flower morphogenesis.  Journal of Theoretical Biology, 193:307–319, 1998.
  * [MMZ14] D. J. A Moraes, B. H. Machado, and D. B. Zoccal.  Coupling of respiratory and sympathetic activities in rats submitted to chronic intermittent hypoxia.  Progress in Brain Research, 212:25–38, 2014.
  * [MP43] W. S. McCulloch and W. H. Pitts.  A logical calculus of the ideas immanent in nervous activity.  Bulletin of Mathematical Biophysics, 5:115–133, 1943.
  * [MR01] H. S. Mortveit and C. M. Reidys.  Discrete, sequential dynamical systems.  Discrete Mathematics, 226:281–295, 2001.
  * [Nou12] M. Noual.  Updating automata networks.  PhD thesis, École normale supérieure de Lyon, 2012.
  * [RC07] A. Richard and J.-P. Comet.  Necessary conditions for multistationarity in discrete dynamical systems.  Discrete Applied Mathematics, 155:2403–2413, 2007.
  * [Rei06] C. M. Reidys.  Sequential dynamical systems over words.  Annals of Combinatorics, 10:481–498, 2006.
  * [Rob69] F. Robert.  Blocs-H-matrices et convergence des méthodes itératives classiques par blocs.  Linear Algebra and its Applications, 2:223–265, 1969.
  * [Rob80] F. Robert.  Itérations sur des ensembles finis et automates cellulaires contractants.  Linear Algebra and its Applications, 29:393–412, 1980.
  * [Rob86] F. Robert.  Discrete iterations: a metric study.  Springer, 1986.
  * [Rob95] F. Robert.  Les systèmes dynamiques discrets.  Springer, 1995.
  * [RR08] É. Remy and P. Ruet.  From minimal signed circuits to the dynamics of Boolean regulatory networks.  Bioinformatics, 24:i220–i226, 2008.
  * [RRT08] É. Remy, P. Ruet, and D. Thieffry.  Graphic requirement for multistability and attractive cycles in a Boolean dynamical framework.  Advances in Applied Mathematics, 41:335–350, 2008.
  * [Sen08] S. Sené.  Influence des conditions de bord dans les réseaux d’automates booléens à seuil et application à la biologie.  PhD thesis, Université Joseph Fourier – Grenoble, 2008.
  * [Sen12] S. Sené.  Sur la bio-informatique des réseaux d’automates.  Habilitation thesis, Université d’Évry – Val d’Essonne, 2012\.
  * [SPMY94] A. Sehgal, J. L. Price, B. Man, and M. W. Young.  Loss of circadian behavioral rhythms and per RNA oscillations in the Drosophila mutant timeless.  Science, 263:1603–1606, 1994.
  * [SS05] N. Saint Savage.  The effects of state dependent and state independent probabilistic updating on Boolean network dynamics.  PhD thesis, University of Manchester, 2005.
  * [TDN+04] M. Thellier, J. Demongeot, V. Norris, J. Guespin, C. Ripoll, and R. Thomas.  A logical (discrete) formulation for the storage and recall of environmental signals in plants.  Plant Biology, 6:590–597, 2004.
  * [Tho73] R. Thomas.  Boolean formalization of genetic control circuits.  Journal of Theoretical Biology, 42:563–585, 1973.
  * [Tho78] R. Thomas.  Logical analysis of systems comprising feedback loops.  Journal of Theoretical Biology, 73:631–656, 1978.
  * [Tho81] R. Thomas.  On the relation between the logical structure of systems and their ability to generate multiple steady states or sustained oscillations.  In Numerical methods in the study of critical phenomena, volume 9 of Springer Series in Synergetics, pages 180–193. Springer, 1981\.
  * [Tho91] R. Thomas.  Regulatory networks seen as asynchronous automata: a logical description.  Journal of THeoretical Biology, 153:1–23, 1991.