# Comments on “Two Cultures”: What have changed over 20 years?

Xuming He<EMAIL_ADDRESS>
Department of Statistics
University of Michigan
273 West Hall, Ann Arbor, MI 48109, USA Jingshen Wang
<EMAIL_ADDRESS>
Division of Biostatistics
University of California, Berkeley
5408 Berkeley Way West, CA 94710, USA

###### Abstract

Twenty years ago Breiman (2001) called to our attention a significant cultural
division in modeling and data analysis between the stochastic data models and
the algorithmic models. Out of his deep concern that the statistical community
was so deeply and “almost exclusively” committed to the former, Breiman warned
that we were losing our abilities to solve many real world problems. Breiman
was not the first, and certainly not the only statistician, to sound the
alarm; we may refer to none other than John Tukey who wrote almost 60 years
ago “data analysis is intrinsically an empirical science”. However, the
bluntness and timeliness of Breiman’s article made it uniquely influential. It
prepared us for the data science era and encouraged a new generation of
statisticians to embrace a more broadly defined discipline.

Some might argue that “The cultural division between these two statistical
learning frameworks has been growing at a steady pace in recent years”, to
quote Mukhopadhyay and Wang (2020). In this commentary, we focus on some of
the positive changes over the past 20 years and offer an optimistic outlook
for our profession.

Keywords: Algorithm; Data models; Machine learning, Prediction.

##  1 Diverse evaluation metrics are taking root in statistics

Classical statistical theory relies mostly on probability or stochastic models
and places much emphasis on the accuracy of parameter estimation (e.g., bias,
variance, mean squared error, coverage probability), and the validity and the
power of hypothesis testing on certain parameters of interest. However, we
also routinely use predictive/forecasting accuracy, classification accuracy,
individual/subgroup treatment effects, receiver operating characteristic
curves and so on in statistical assessments, depending on which is more
relevant to the problem being addressed.

The importance of prediction is gaining recognition. We found the use of
“prediction error” in 16 articles (including comments and book reviews)
published in Journal of the American Statistical Association  over a 3-year
period of 1998-2000, and the number rose more than quintupled to 86 over the
most recent 3-year period (2018-2020). To put this in perspective, the same
search engine showed an increase from 79 articles to 138 (just shy of
doubling) over the same time period for “logistic regression”.

Prediction is certainly not the only thing that matters. We do not think it is
fair or even possible to quantify how much we do in statistics should be about
prediction accuracy. Instead, we ask whether more needs to be done to promote
the use of modern statistical and machine learning methods in real world
applications. We share our experience in two areas of applications.

Sport concussion concerns many but accurate diagnosis and good understanding
of recovery and of longer term impact remain challenging. Because concussion
is typically a result of biomechanical forces transmitted to the cerebral
tissues from impacts to the head or torso, clinical researchers have asked
whether biomechanical analyses of impacts can help in developing a diagnostic
model and improving protective equipment for the athletes. Earlier work using
tree-based methods (Broglio et al., 2010) to analyze data collected from the
Head Impact Telemetry System helped quantify importance of the biomecehnical
measurements and the relevant thresholds for concussive injuries sustained
during high school football. Over the years we also learned that accuracy of
concussion diagnosis should not rely on those measurements alone. Furthermore,
machine learning methods including the deep neutral network model was
introduced to clinical researchers for predicting time-to-recovery in
pediatric concussion patients; see Walker et al. (2019). Genetic Fuzzy Trees
(GFT), a modern artificial intelligence tool, was employed in Fleck et al.
(2020) to predict post-concussion symptom recovery in adolescents. When
compared with common linear classification methods, the GFT was shown to have
significantly better overall accuracy than most of its competitors based on
cross-validated measures of sensitivity and specificity. In this particular
study the overall accuracy based on Discriminant Function Analysis (DFA) and
Random Forest was 54.4% and 57.1%, respectively, but increased to 62.3% when
the GFT was used. Studies of this nature in concussion research are still
limited, but our engagement in the Michigan Concussion Center has convinced us
that our colleagues often turn to us as statisticians for help with both
exploratory and confirmatory analysis, and few of them consider us as experts
of ”one culture”. They talk to us about predictive accuracy as well as
significance tests under interpretable models.

Cardiovascular disease (CVD) is a major cause of death worldwide. Multiple
risk factors (i.e, age, gender, smoking status, body mass index, systolic
blood pressure, history of diabetes, and reception of treatments for
hypertension) are associated with CVD. Appropriately accounting for these risk
factors is known to improve accuracy of CVD risk prediction and hence extend
lives. Conventional methods including the Cox proportional hazard models are
still being frequently employed to estimate the CVD risk based on these
familiar risk factors (see Pylypchuk et al., 2018; Kaptoge et al., 2019, for
example). In fact, many current guidelines often recommend calculating the CVD
risk score based on a limited number of predictors: the 2010 American College
of Cardiology/American Heart Association (ACC/AHA) guideline recommended the
Framingham Risk Score (Greenland et al., 2010), the 2016 United Kingdom
National Institute for Health and Care Excellence (NICE) guidelines used the
QRISK3 score (Hippisley-Cox et al., 2017), and the 2016 European Society of
Cardiology (ESC) guidelines included the SCORE model (Members et al., 2016).

Because of restrictive modelling assumptions adopted in traditional CVD risk
score models, these approaches generally exhibit modest predictive
performance. In recent years, modern machine learning tools have begun to be
employed for predicting the CVD risk in the hope of agnostically discovering
novel risk predictors and learning the complex interactions between them (see
Krittanawong et al., 2020, for a comprehensive review). For example,
“AutoPrognosis”, an automated clinical prognostic modeling tool, was able to
correctly predict 368 more cases out of 4,801 CVD cases than a traditional
approach in analyzing UK Biobank data; see Alaa et al. (2019). It was shown in
Sung et al. (2019) that a deep learning prediction model provided some
promising results in predicting the CVD risk. There, the deep learning model
had time-dependent “Area under the ROC Curve” (AUC) of as high as 0.94 for
females and 0.96 for males, while the classical Cox regression model showed
time-dependent AUC of up to 0.79 for females and 0.75 for males. In both
studies cited above, the contribution of each variable to the prediction was
used to rank the possible risk factors, but a variable that contributes more
to prediction is not necessarily causal. Quantification of a risk factor via a
causality study in the machine learning framework remains underdeveloped.
Nevertheless, the capacity of machine learning algorithms to model highly
interactive complex data structures in CVD has gained momentum. By Google
Scholar counts, we found that around 10% of the publications about CVD
discussed machine learning methods in 2010, and the share has risen to about
one third by now.

##  2 Data models and algorithmic models are no longer easily distinguishable

Breiman made a convincing case that stochastic data models used in classical
statistics are not the best, or even appropriate, models for many real world
problems. Algorithmic models often offer a much more flexible framework for
data analysis. We would like to emphasize that data models in statistics are
often used as working models to generate a procedure or algorithm. They do not
need to be correct or even accurate descriptions of the true nature, either
for prediction or for inference. In this sense, data models and algorithmic
models are often two starting points that could end up with friendly hand-
shaking.

There are many examples where mis-specification of the data models are taken
into account in inference. Generalized estimating equations (GEE), originally
designed to account for a possible unknown correlation between outcomes (Zeger
and Liang, 1986), relies on specification of only the moments in a data model.
By using a robust variance-covariance estimates, statistical inference on the
model parameters remain asymptotically valid without stringent assumptions
assumed on part of the models. Another example is the posterior inference in a
Bayesian framework. Yang et al. (2016) showed that by adopting a convenient
working likelihood for quantile regression, Markov Chain Monte Carlo
algorithms can then be used to draw from the posterior distribution to form a
basis for asymptotically valid inference on the quantile regression parameter;
here the assumed data model is really used as an input to the Bayesian
computational framework, and the entire inferential process can be viewed as
an algorithm.

Taking it a little further, we have mixture of experts (Jacobs et al., 1991)
that starts with Gaussian mixture models. The Gaussian components may allow us
to derive and study certain properties of the model but we can take this
supervised learning procedure as algorithmic.

In addition, current research in analyzing the CVD risk often finds data
models and algorithmic models complimentary in identifying important risk
factors. When predicting the risk of CVD by using deep learning models, Sung
et al. (2019) ranked the influence of the input variables by using a Layer-
wise Relevance Propagation (LRP), one of many explainable artificial
intelligence techniques used in neural networks. They found that many risk
factors (including age, gender, blood pressure, smoking, exercise) considered
to be important in classical clinical studies were also shown to be important
by deep learning models. Deep learning has its own limitation in providing the
effect size of those risk factors due to hidden layers used in LRP.
Nevertheless, Alaa et al. (2019) found that the algorithmic models helped
uncover novel risk factors for CVDs that have not been considered in
traditional prospective studies when analyzing the UK Biobank data. For women,
AutoPrognosis identified “ankle spacing width” as an important risk factor.
Clinically, this may be linked to symptoms of poor circulation, such as
swollen legs, which could be predictive of future CVD events. For patients
with history of diabetes, AutoPrognosis has not only maintained high
predictive accuracy but also revealed diabetes-specific risk factors (such as
microalbuminuria) that were not previously captured by the traditional data
models.

We certainly do not intend to claim that the difference between the data
models and the algorithmic models no longer exists. It remains obvious that
both types of models can be mis-used. In fact, dangers have persisted in many
statistical analyses that rely too much on blind trusts of the data models,
which has led to the reproducibility and replicability crisis as some have
called it. There are also many instances where blind use of algorithmic models
and machine learning methods have failed us. The Google Flu Trends (Butler,
2013), IBM’s Watson supercomputer cancer treatment recommendations (Ross and
Swetlitz, 2018), and Apple Card Algorithm (Vigdor, 2019; Pena et al., 2020)
are just some of well-publicized examples. We do not think that these problems
argue against either type of models; rather their co-existence and further
promotion of their better use make statistics a better playground. This leads
us to the next point.

##  3 Statistical learning needs domain expertise

Data analysis is not just about data. Instead, any modeling attempt needs to
incorporate domain knowledge and expertise wherever possible. We think this is
a bigger issue than which modeling approach one takes.

Take statistical downscaling as an example. Statistical downscaling aims to
localize global or regional climate model projections to assess the potential
impact of climate changes based on data-driven models. It requires quantifying
a relationship between climate model outputs ($X$) and local observations
($Y$) from the past. One would naturally attempt to regress $Y$ on $X$ to find
a relationship that can be used for future projections of $Y$ based on the
climate model output. However, the projections from typical climate models are
about “climate”, not daily/weekly/monthly measurements that pair with the
local observations in real time. Without the domain knowledge that we had to
learn from the atmospheric scientists, we would run the risk of making poor
choices of statistical modeling tools, whether it is a simple linear
regression or a more complicated machine learning method. In fact, we need to
turn to regression-type modeling with asynchronous measurements as
demonstrated in He et al. (2012) and Stoner et al. (2013).

In computational medicine, it is no surprise that machine learning algorithms
without incorporating domain knowledge can make mistakes that would appear
trivial to domain experts. In a recent study, CheXNet (Radiologist-Level
Pneumonia Detection on Chest X-Rays with Deep Learning), Rajpurkar et al.
(2017) observed that a convolutional neural network (CNN) outperformed
radiologists in overall diagnostic accuracy. A subsequent study (Zech et al.,
2018) revealed that the CNN built in CheXNet suffers from high generalization
bias. Part of the reasons is that the CNN chooses some hospital site-specific
variables over patient underlying pathology as predictive variables. Such a
choice was made based on a strong correlation displayed in CheXNet between the
pneumonia prevalence and those site-specific variables. In addition to the
site-specific confounding variables that threaten the generalizability of the
CNN, there can be other factors related to medical management that undermines
the clinical applicability of statistical learning methods. Oakden-Rayner
(2020) pointed out since chest tubes are frequently used to treat
pneumothorax, a CNN without context-oriented modelling may not be able to
diagnose patients with pneumothorax since they lacked a chest tube. To make
statistical learning methods more trustworthy in medical research, adapting to
domain knowledge is an important step towards building stronger and more
robust models. Whether one calls this “interpretable machine learning” or
“explainable AI”, we need to be embedded in the relevant domain of science,
business, or medicine.

Data-driven models and prediction have proven to be useful but not without
peril. Things could go wrong easily if data are taken out of context. To
conclude, we reiterate some of the points made earlier. First, data alone, no
matter how big, may not tell the whole story. Any prediction trained on the
existing data without sanity checks based on domain knowledge or even common
sense could turn into a fiasco. Second, a good model needs to incorporate the
dynamic nature of the world, where non-stationarity and heterogeneity of
various forms cannot be ignored. Generalization errors that do not look beyond
the past data are not always trusty measures. Third, we need to understand the
limitations of what we can do with data in any approach to modeling. Context-
oriented modeling is key to make statistical learning more powerful. Looking
back, we statisticians have made significant progresses in the right
direction, and we certainly expect more to come.

Acknowledgments

The research is partially supported by the National Science Foundation Awards
DMS-1914496 and DMS-2015325.

## References

  * Alaa et al. (2019) Ahmed M Alaa, Thomas Bolton, Emanuele Di Angelantonio, James HF Rudd, and Mihaela van der Schaar.  Cardiovascular disease risk prediction using automated machine learning: A prospective study of 423,604 UK biobank participants.  _PloS One_ , 14(5):e0213653, 2019.
  * Breiman (2001) Leo Breiman.  Statistical modeling: the two cultures (with comments and a rejoinder by the author).  _Statistical Science_ , 16(3):199–231, 2001.
  * Broglio et al. (2010) Steven P Broglio, Brock Schnebel, Jacob J Sosnoff, Sunghoon Shin, Xingdong Feng, Xuming He, and Jerrad Zimmerman.  The biomechanical properties of concussions in high school football.  _Medicine and Science in Sports and Exercise_ , 42(11):2064, 2010.
  * Butler (2013) Declan Butler.  When Google got flu wrong.  _Nature News_ , 494(7436):155, 2013.
  * Fleck et al. (2020) David E Fleck, Nicholas Ernest, Ruth Asch, Caleb M Adler, Kelly Cohen, Weihong Yuan, Brandon Kunkel, Robert Krikorian, Shari L Wade, and Lynn Babcock.  Predicting post-concussion symptom recovery in adolescents using a novel artificial intelligence.  _Journal of Neurotrauma_ , 2020.
  * Greenland et al. (2010) Philip Greenland, Joseph S Alpert, George A Beller, Emelia J Benjamin, Matthew J Budoff, Zahi A Fayad, Elyse Foster, Mark A Hlatky, John McB Hodgson, and Frederick G Kushner.  2010 ACCF/AHA guideline for assessment of cardiovascular risk in asymptomatic adults: a report of the american college of cardiology foundation/american heart association task force on practice guidelines.  _Circulation_ , 122(25):e584–e636, 2010.
  * He et al. (2012) Xuming He, Yunwen Yang, and Jingfei Zhang.  Bivariate downscaling with asynchronous measurements.  _Journal of Agricultural, Biological, and Environmental Statistics_ , 17(3):476–489, 2012.
  * Hippisley-Cox et al. (2017) Julia Hippisley-Cox, Carol Coupland, and Peter Brindle.  Development and validation of QRISK3 risk prediction algorithms to estimate future risk of cardiovascular disease: prospective cohort study.  _BMJ_ , 357, 2017.
  * Jacobs et al. (1991) Robert A Jacobs, Michael I Jordan, Steven J Nowlan, and Geoffrey E Hinton.  Adaptive mixtures of local experts.  _Neural Computation_ , 3(1):79–87, 1991.
  * Kaptoge et al. (2019) Stephen Kaptoge, Lisa Pennells, Dirk De Bacquer, Marie Therese Cooney, Maryam Kavousi, Gretchen Stevens, Leanne Margaret Riley, Stefan Savin, Taskeen Khan, and Servet Altay.  World health organization cardiovascular disease risk charts: revised models to estimate risk in 21 global regions.  _The Lancet Global Health_ , 7(10):e1332–e1345, 2019.
  * Krittanawong et al. (2020) Chayakrit Krittanawong, Hafeez Ul Hassan Virk, Sripal Bangalore, Zhen Wang, Kipp W Johnson, Rachel Pinotti, HongJu Zhang, Scott Kaplin, Bharat Narasimhan, and Takeshi Kitai.  Machine learning prediction in cardiovascular diseases: a meta-analysis.  _Scientific Reports_ , 10(1):1–11, 2020.
  * Members et al. (2016) Task Force Members, Massimo F Piepoli, Arno W Hoes, Stefan Agewall, Christian Albus, Carlos Brotons, Alberico L Catapano, Marie-Therese Cooney, Ugo Corrà, and Cosyns.  2016 european guidelines on cardiovascular disease prevention in clinical practice.  _European Journal of Preventive Cardiology_ , 23(11):NP1–NP96, 2016.
  * Mukhopadhyay and Wang (2020) Subhadeep Mukhopadhyay and Kaijun Wang.  Breiman’s “two cultures” revisited and reconciled.  _arXiv preprint arXiv:2005.13596_ , 2020.
  * Oakden-Rayner (2020) Luke Oakden-Rayner.  Exploring large-scale public medical image datasets.  _Academic Radiology_ , 27(1):106–112, 2020.
  * Pena et al. (2020) Alejandro Pena, Ignacio Serna, Aythami Morales, and Julian Fierrez.  Bias in multimodal AI: testbed for fair automatic recruitment.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_ , pages 28–29, 2020.
  * Pylypchuk et al. (2018) Romana Pylypchuk, Sue Wells, Andrew Kerr, Katrina Poppe, Tania Riddell, Matire Harwood, Dan Exeter, Suneela Mehta, Corina Grey, and Billy P Wu.  Cardiovascular disease risk prediction equations in 400 000 primary care patients in new zealand: a derivation and validation study.  _The Lancet_ , 391(10133):1897–1907, 2018.
  * Rajpurkar et al. (2017) Pranav Rajpurkar, Jeremy Irvin, Kaylie Zhu, Brandon Yang, Hershel Mehta, Tony Duan, Daisy Ding, Aarti Bagul, Curtis Langlotz, and Katie Shpanskaya.  Chexnet: Radiologist-level pneumonia detection on chest X-rays with deep learning.  _arXiv preprint arXiv:1711.05225_ , 2017.
  * Ross and Swetlitz (2018) Casey Ross and Ike Swetlitz.  IBM’s Watson supercomputer recommended ‘unsafe and incorrect’ cancer treatments, internal documents show.  _Stat_ , 25, 2018.
  * Stoner et al. (2013) Anne MK Stoner, Katharine Hayhoe, Xiaohui Yang, and Donald J Wuebbles.  An asynchronous regional regression model for statistical downscaling of daily climate variables.  _International Journal of Climatology_ , 33(11):2473–2494, 2013.
  * Sung et al. (2019) Ji Min Sung, In-Jeong Cho, David Sung, Sunhee Kim, Hyeon Chang Kim, Myeong-Hun Chae, Maryam Kavousi, Oscar L Rueda-Ochoa, M Arfan Ikram, and Oscar H Franco.  Development and verification of prediction models for preventing cardiovascular diseases.  _PloS One_ , 14(9):e0222809, 2019.
  * Vigdor (2019) Neil Vigdor.  Apple card investigated after gender discrimination complaints.  _The New York Times_ , 10, 2019.
  * Walker et al. (2019) Gregory Walker, Adam Kiefer, Nathaniel Richards, Emma Klug, Christy Reed, Paula Silva, and Kelly Cohen.  Machine learning for concussion recovery prognosis: a novel tool to empower proactive physician treatments, 2019.
  * Yang et al. (2016) Yunwen Yang, Huixia Judy Wang, and Xuming He.  Posterior inference in bayesian quantile regression with asymmetric laplace likelihood.  _International Statistical Review_ , 84(3):327–344, 2016.
  * Zech et al. (2018) John R Zech, Marcus A Badgeley, Manway Liu, Anthony B Costa, Joseph J Titano, and Eric Karl Oermann.  Variable generalization performance of a deep learning model to detect pneumonia in chest radiographs: a cross-sectional study.  _PLoS Medicine_ , 15(11):e1002683, 2018.
  * Zeger and Liang (1986) Scott L Zeger and Kung-Yee Liang.  Longitudinal data analysis for discrete and continuous outcomes.  _Biometrics_ , pages 121–130, 1986.


:
Learning and Automata (LearnAut 2024)

# Learning Closed Signal Flow Graphs

Ekaterina Piotrovskaya<EMAIL_ADDRESS>
Leo Lobski<EMAIL_ADDRESS>
Fabio Zanasi<EMAIL_ADDRESS>
University College London  UK

###### Abstract

We develop a learning algorithm for closed signal flow graphs – a graphical
model of signal transducers. The algorithm relies on the correspondence
between closed signal flow graphs and weighted finite automata on a singleton
alphabet. We demonstrate that this procedure results in a genuine reduction of
complexity: our algorithm fares better than existing learning algorithms for
weighted automata restricted to the case of a singleton alphabet.

###### keywords:

signal flow graph, automata learning, weighted automaton

##  1 Introduction

Signal flow graphs (SFG) are a graphical language for signal transducers,
which play a foundational role in control theory and engineering (Shannon,
1942). A signal flow graph is typically specified as a circuit, with gates
corresponding to basic signal operations: addition, copying, amplification by
a scalar, and delay. Moreover, signal flow graphs allow for the formation of
feedback loops. From an expressiveness viewpoint, these models capture
precisely rational functions: the Taylor expansion of the function may be
regarded as the signal processed by the signal flow graph.

$c$$+$$x_{0}$$x_{0}$$x_{0}$$1,0,0,\dots$$1,1,2,3,5,\dots$ Figure 1: The signal
flow graph for the Fibonacci sequence. That means, received as input the
sequence $1,0,0,\dots$ of signals, it outputs the Fibonacci numbers
$1,1,2,3,5,\dots$. Note these are the coefficients of the formal power series
expanding the rational function $\frac{1}{1-x-x^{2}}$. The semantics of SFG is
further explained in Subsection 2.2.

In the last decade, there has been a renewed interest in the theory of signal
flow graphs. For readers familiar with category theory, we note that these
structures have been studied through the lenses of (co)algebra (Rutten, 2005,
2008), logic (Milius, 2010), and category theory (Bonchi et al., 2017, 2021,
2014; Baez and Erbele, 2008), with the aim of providing a compositional
perspective on their behaviour. In particular, these works have established a
formal correspondence (in terms of functors) between the syntax of signal flow
graphs — variously represented as a stream calculus, string diagrams, or a
graph formalism — and their semantics — linear relations between streams.

One aspect that such theory leaves mostly to guesswork and intuition is how to
infer the structure of the signal flow graph from the observed behaviour of
the system it represents. More precisely, we are interested in the following
scenario: given a “black box” signal flow graph, we may observe the output
behaviour only, but not the structure of the graph itself, which we wish to
infer in an algorithmic manner.111Of course, one can only hope to learn the
signal flow graph structure up to semantic equivalence. There is a purely
equational theory axiomatising this equivalence, as studied in Bonchi et al.
(2017); Baez and Erbele (2008).

Our contribution lies in studying how formal learning techniques (Angluin,
1987), as developed in the context of automata theory, have the potential to
improve and systematise this process. As a starting point, we will develop
such a learning algorithm for the restricted case of closed signal flow graphs
(cSFG), where no inputs are provided to the system. In order to adapt existing
automata learning techniques, we wish to utilise the fact that cSFGs are
semantically equivalent to weighted finite automata with a singleton alphabet.

_Weighted finite automata_ (WFA), first introduced in Schützenberger (1961),
can be seen as a generalisation of non-deterministic automata, with each
transition having a weight (or a ‘cost’) associated to it. WFAs have found
applications in multiple areas ranging from speech recognition (Mohri et al.,
2005) and image processing (Culik II and Kari, 1993) to control theory
(Isidori, 1985) and financial modelling (Baier et al., 2009). If we restrict
the alphabet of a WFA to a singleton one, we get a rather simple class of
WFAs. It turns out that such automata are equivalent to cSFGs in the sense
that both compute the same subclass of streams (namely, rational streams).

A learning algorithm for WFA has been introduced by Bergadano and Varricchio
(1996), who presented its complexity bound and showed that WFAs over fields
could be learned from a teacher. Another such algorithm for WFA was introduced
in the PhD thesis of van Heerdt (2020), where it can be viewed as a general
weighted adaptation of Angluin’s L∗ (Angluin, 1987) parametric on an arbitrary
semiring. In fact, our algorithm is inspired by van Heerdt (2020), though more
efficient and with an explicit calculation of the complexity bound.

The complexity bound for our algorithm turns out to be better than that for
arbitrary weighted finite automata in the singleton alphabet case. The
improvement is largely due to exploiting the linear algebraic structure of
rational streams.

##  2 Preliminaries

We recall the notions of rational streams, signal flow graphs and weighted
automata. Some of the results stated have references to Rutten (2008) as the
paper nicely condenses them in one place; however, most of them have already
been established in the literature prior to it. The proof of rational series
having finite representations appears in Berstel and Reutenauer (1988). It is
further elaborated on with respect to rational streams in Rutten (2001),
together with their property of having a finite number of linearly independent
derivatives.

###  2.1 Rational Streams

A _stream_ over a field $k$ is an infinite sequence of elements of $k$. Define
the set of $k$-valued streams as the function set $k^{\omega}$. Given a stream
$\sigma\in k^{\omega}$, we denote its values by
$\sigma=(\sigma_{0},\sigma_{1},\sigma_{2},\dots)$, and call $\sigma_{0}$ the
initial value of $\sigma$. The _stream derivative_ of $\sigma$ is defined as
$\sigma^{\prime}\coloneqq(\sigma_{1},\sigma_{2},\sigma_{3},\dots)$.

We refer to a stream $\sigma$ as _polynomial_ if it has a finite number of
non-zero elements, i.e. if it is of the form
$\sigma=(c_{0},c_{1},c_{2},\dots,c_{k},0,0,0,..)$. A stream is _rational_ if
it can be represented as a ratio of two polynomial streams, i.e. a so-called
convolution product of a polynomial stream with an inverse of another
polynomial stream (see Rutten (2005) for details). As an example, take two
polynomial streams $p=(1,0,0,..)$ and $q=(1,0,-1,0,0,..)$; then
$\sigma=p/q=(1,0,1,0,1,0,..)$ is rational. Rational streams are “periodic”, in
the sense that they only have a finite number of linearly independent stream
derivatives:

######  Lemma 2.1 (Rutten (2008)).

For a rational stream $\sigma$, there exists an $n\geq 1$ such that
$\\{\sigma^{(0)},\sigma^{(1)},\sigma^{(2)},\dots,\sigma^{(n-1)}\\}$ are
linearly independent in the vector space $k^{n}$, and
$\sigma^{(n)}=\sum_{i=0}^{n-1}c_{i}\times\sigma^{(i)}$, for some unique
$c_{0},\dots,c_{n-1}\in k$.

Rational streams have long been used as a means to characterise finite
circuits in the field of signal processing (Lathi, 1998, p. 694), and can be
defined via linear recurrent sequences or difference equations (Rutten, 2001).

###  2.2 Signal Flow Graphs

Given a field $k$, we think of its elements as basic units of signals. A
signal flow can then be modelled as an infinite stream of elements from $k$.
The transducers that can add, copy, multiply and delay signals are represented
as signal flow graphs.

Formally, a signal flow graph (SFG) is a finite directed graph whose interior
vertices are labelled with one of the labels $+$, $c$, $a$ or $x_{a}$, where
$a\in k$. Moreover, a $+$-labelled vertex has at least two incoming edges and
one outgoing edge, a $c$-labelled vertex has exactly one incoming edge and at
least two outgoing edges, while $a$ and $x_{a}$-labelled vertices have exactly
one incoming and one outgoing edge. Finally, we require that every feedback
loop (i.e. a cycle in the graph) passes through at least one $x_{a}$-labelled
vertex. We draw the four basic _generators_ (i.e. vertex types) of SFGs below;
note that the input/output labels are not part of the data of a SFG, but
define how it computes a stream function, as discussed below.

$c$$+$$x_{0}$$x_{0}$$x_{0}$$1,0,0,\dots$$1,1,2,3,5,\dots$$+$$c$$a$$x_{a}$$a$$b$$a+b$$a$$a$$a$$b$$ab$$b$$a$

We refer to the above generators as an adder, a copier, a multiplier and a
register. The vertices with no incoming edges are referred to as inputs and
the vertices with no outgoing edges as outputs. SFGs are hence built by
composing such vertices (Bonchi et al., 2021). Writing $i,o\in\mathbb{N}$ for
the number of inputs and outputs of a signal flow graph, the graph implements
a function $\left(k^{\omega}\right)^{i}\rightarrow\left(k^{\omega}\right)^{o}$
as follows: at step $n$, the input vertices are assigned the $n$th element of
the corresponding stream, the labelled vertices pass on the incoming values to
the outgoing values as indicated in the above picture, with the additional
requirement that the register value is updated to $x_{b}$.

Crucially, two SFGs can be composed by plugging (some of) the outputs of one
into (some of) the inputs of the other. We have already given an example of a
composite SFG computing the Fibonacci sequence (Figure 1).

The class of stream functions computed by SFGs is characterised by
multiplication by rational streams (Rutten, 2005; Bonchi et al., 2017). The
simplest case of no inputs and one output can be used to characterise rational
streams.

######  Definition 2.2 (cSFG).

A _closed signal flow graph (cSFG)_ is a SFG with no inputs and exactly one
output.

We give an example of a cSFG below, which computes the stream
$\sigma_{n}=a+n+1$:

$c$$+$$x_{0}$$x_{0}$$x_{0}$$1,0,0,\dots$$1,1,2,3,5,\dots$$+$$c$$a$$x_{a}$$a$$b$$a+b$$a$$a$$a$$b$$ab$$b$$a$$c$$c$$x_{1}$$+$$x_{a}$

The following result shows that cSFGs precisely capture the rational streams.

######  Theorem 2.3 (Rutten (2008)).

A stream $\sigma\in k^{\omega}$ is rational if and only is there exists a cSFG
that implements it.

###  2.3 Weighted Automata

_Weighted finite automata_ (WFA) are a generalisation of non-deterministic
automata, where transitions have a weight. A WFA over a field $k$ with an
alphabet $A$ is a tuple $(Q,\langle o,t\rangle)$, where $Q$ is a finite set of
states, $o:Q\rightarrow k$ is an output function (i.e. the final weights) and
$t:Q\rightarrow(k^{Q})^{A}$ a transition function (Bonchi et al., 2012).

######  Remark 2.4.

WFA are usually defined as a tuple $(Q,i,o,t)$, where $Q,o,t$ are as above and
$i:Q\rightarrow k$ is the initial weights function. We omit the latter from
our definition, as the notion of a stream represented by a state is equivalent
to assigning input $1$ to it, and $0$ to all other states.

In the singleton alphabet case, it is equivalent to work with weighted stream
automata (WSA). The data of a WSA is that of a WFA, except that the transition
function has the type $t:Q\times Q\rightarrow k$ (Rutten, 2008). An example of
a WSA is as below, where we do not draw the transitions labelled with $0$:

$c$$+$$x_{0}$$x_{0}$$x_{0}$$1,0,0,\dots$$1,1,2,3,5,\dots$$+$$c$$a$$x_{a}$$a$$b$$a+b$$a$$a$$a$$b$$ab$$b$$a$$c$$c$$x_{1}$$+$$x_{a}$$q_{1}$$q_{2}$$a+1$$a+2$$1$$-1$$2$

The weight of a path is obtained by multiplying the weights of the individual
transitions in the path and the output weight of the last state. We say that a
state $q$ of a WSA represents a stream $S(q)=(s_{0},s_{1},s_{2},\dots)$, where
$s_{n}$ is the sum of all weights of paths of length $n$ starting at $q$. The
state $q_{1}$ of the above WSA represents the stream $\sigma_{n}=a+n+1$, which
we recognise as the same stream as in our example of a cSFG. In fact, we have
the following result:

######  Theorem 2.5 (Rutten (2008)).

A stream $\sigma\in k^{\omega}$ is rational if and only if there is a
$k$-valued WSA $(Q,\langle o,t\rangle)$ and a state $q\in Q$ representing
$\sigma$.

To construct a WSA from a rational stream $\sigma$, we first find the number
of linearly independent derivatives of $\sigma$, call it $n$; then assign
$\sigma_{i}$ to the output of each state $q_{i}$ (for $i=0,\dots,n-1$) and use
the coefficients $c_{0},\dots,c_{n-1}$ (Lemma 2.1) to define the transition
function. This induces a specific shape of a WSA described in the next
section.

##  3 The Learning Algorithm

We begin by fixing the definitions needed by the algorithm. We largely follow
the notation and terminology from van Heerdt (2020). Throughout this section,
let $k$ be a fixed field and $\sigma\in k^{\omega}$ a stream. We think of
$\sigma$ as the (unknown) stream computed by the cSFG we want to learn. By an
_observation table_ we mean a pair $(S,E)$ of finite subsets of $\omega$.

######  Definition 3.1 (Row function, last row function).

Given an observation table $(S,E)$, let $w$ be the largest element of $S$.
Define the _row function_ $\mathtt{row}:S\rightarrow k^{E}$ by
$\mathtt{row}(v)(e)=\sigma_{v+e}$ for $v\in S$, $e\in E$, and the _last row
function_ $\mathtt{srow}:E\rightarrow k$ by $\mathtt{srow}(e)=\sigma_{w+e+1}$
for $e\in E$.

######  Definition 3.2 (Closedness).

We say that an observation table $(S,E)$ is _closed_ if there exist constants
$c_{s}\in k$ such that $\mathtt{srow}=\sum_{s\in S}c_{s}\cdot\mathtt{row}(s)$.

We next introduce the notion of the _coefficient function_ that outputs the
solution to a system of linear equations if it exists, or returns $\bot$
otherwise. Note that it can be computed efficiently by Lemma 2.1.

######  Definition 3.3 (Coefficient function).

Let $(S,E)$ be an observation table. Define the _coefficient function_
$\mathtt{cs}\in\\{\bot\\}\cup k^{S}$ as the function $\mathtt{cs}:S\rightarrow
k$ such that $\mathtt{srow}=\sum_{s\in S}\mathtt{cs}(s)\cdot\mathtt{row}(s)$
if the table is closed, and as the symbol $\bot$ otherwise.

The algorithm assumes access to an oracle that answers the following types of
queries: (1) _Membership query_ : given an index $n\in\omega$, an oracle
replies with the $n$th element of the corresponding stream; and (2)
_Equivalence query_ : given a cSFG, an oracle replies with “yes” if the cSFG
constructed is correct, and with “no” otherwise.

We now have all the ingredients to define the learning algorithm (Algorithm
1). We create an observation table, with $S$ and $E$ initially only containing
$0$. We also keep a counter $i$, initially assigned $1$, to keep track of the
smallest index not in $S$, which will improve the overall complexity of the
algorithm. We then repeatedly check whether the table is closed (lines 4-8)
and if not, add the index $i$ to $S$ and $E$ (i.e. expanding the table
proportionally) and increment the counter.

We can now construct the hypothesis cSFG (lines 9-14). Thus suppose that the
observation table is closed, so that we have a coefficient function
$\mathtt{cs}:S\rightarrow k$. Note that the set $S=\\{0,\dots,i-1\\}$ has $i$
elements. We define the cSFG as follows:

  * •

it has $i$ registers $r_{0},\dots,r_{i-1}$, whose labels are the solutions to
the linear equations in Theorem 3.5,

  * •

it has $i$ copiers $q_{0},\dots,q_{i-1}$,

  * •

it has $i$ adders $a_{0},\dots,a_{i-2}$ and $a_{final}$,

  * •

it has $2i$ multipliers $m_{0},\dots,m_{i-1}$ and $n_{0},\dots,n_{i-1}$ with
labels $l(m_{j})\coloneqq\mathtt{row}(j)(0)=\sigma_{j}$ and
$l(n_{j})\coloneqq\mathtt{cs}(j)$,

  * •

for each $j\in\\{0,\dots,i-1\\}$, there are edges $(r_{j},q_{j})$,
$(q_{j},m_{j})$ and $(m_{j},a_{final})$,

  * •

for each $j\in\\{0,\dots,i-2\\}$, there are edges $(q_{j},a_{j})$ and
$(a_{j},r_{j+1})$,

  * •

there are edges $(q_{i-1},n_{0})$ and $(n_{0},r_{0})$, and for each
$j\in\\{1,\dots,i-1\\}$, edges $(q_{i-1},n_{j})$ and $(n_{j},a_{j})$,

  * •

there is an edge $(a_{final},o)$, where $o$ is the unique output.

Below, we give a cSFG graph obtained from the above construction for $i=3$. We
denote the label of the vertex inside a box, while its name is put next to it.

$c$$+$$x_{0}$$x_{0}$$x_{0}$$1,0,0,\dots$$1,1,2,3,5,\dots$$+$$c$$a$$x_{a}$$a$$b$$a+b$$a$$a$$a$$b$$ab$$b$$a$$c$$c$$x_{1}$$+$$x_{a}$$+$$x_{r_{0}}$$x_{r_{2}}$$+$$c$$c$$\sigma_{0}$$\sigma_{2}$$\mathtt{cs}(2)$$\mathtt{cs}(0)$$x_{r_{1}}$$+$$c$$\sigma_{1}$$\mathtt{cs}(1)$$q_{0}$$q_{1}$$q_{2}$$m_{0}$$m_{1}$$m_{2}$$a_{final}$$a_{0}$$a_{1}$$n_{1}$$n_{0}$$n_{2}$

######  Remark 3.4.

We note that, when constructing a hypothesis cSFG, we essentially get a WSA
equivalent to it “for free”: the values from the first column are assigned to
the output of each state $s\in S$; each transition from state $s$ to $s+1$ is
assigned value $1$, and the coefficients returned by the coefficient function
are assigned to transitions from the state $i-1$ to each $s\in S$. We
represent the resulting WSA below:

$c$$+$$x_{0}$$x_{0}$$x_{0}$$1,0,0,\dots$$1,1,2,3,5,\dots$$+$$c$$a$$x_{a}$$a$$b$$a+b$$a$$a$$a$$b$$ab$$b$$a$$c$$c$$x_{1}$$+$$x_{a}$$+$$x_{r_{0}}$$x_{r_{2}}$$+$$c$$c$$\sigma_{0}$$\sigma_{2}$$\mathtt{cs}(2)$$\mathtt{cs}(0)$$x_{r_{1}}$$+$$c$$\sigma_{1}$$\mathtt{cs}(1)$$q_{0}$$q_{1}$$q_{2}$$m_{0}$$m_{1}$$m_{2}$$a_{final}$$a_{0}$$a_{1}$$n_{1}$$n_{0}$$n_{2}$$0$$1$$\cdots$$i-1$$\mathtt{row}(0)(0)=\sigma_{0}$$\mathtt{row}(1)(0)=\sigma_{1}$$\mathtt{row}(i-1)(0)=\sigma_{i-1}$$1$$1$$1$$c_{1}$$c_{0}$$c_{i-1}$

Finally, we give the hypothesis cSFG to the oracle as an equivalence query,
which results in oracle either rejecting it, which indicates that the
corresponding stream has more linearly independent derivatives than we have
guessed, thence $i$ is added to $S$ and $E$ and the counter is incremented and
the outer while loop is executed again; or accepting it and hence we have
learnt the cSFG.

1 $S,E\leftarrow\\{0\\}$

2 $i\leftarrow 1$

3 while  _true_ do

4 while  _$\mathtt{cs}$ = $\bot$_ do

5 $S\leftarrow S\cup\\{i\\}$

6 $E\leftarrow E\cup\\{i\\}$

7 $i\leftarrow i+1$

8 end while

9 for  _$s\in S$_ do

10 $o(s)\leftarrow\mathtt{row}(s)(0)$

11 $t(i-1)(s)\leftarrow\mathtt{cs}(s)$

12 $t(s)(s+1)\leftarrow 1$

13 end for

14 $\text{Construct }cSFG$

15 if  _$\text{EQ}(cSFG)=\text{no}$_ then

16 $S\leftarrow S\cup\\{i\\}$

17 $E\leftarrow E\cup\\{i\\}$

18 $i\leftarrow i+1$

19 else

20 return _cSFG_

21 end if

22

23 end while

Algorithm 1 Abstract learning algorithm for a cSFG over $k$

###  3.1 Correctness

We proceed to give a proof of the correctness of our algorithm. This amounts
to showing that the constructed WFA and cSFG indeed compute the stream we
expect them to.

Let us fix the following definitions. A state $q_{R}$ of a WFA $(Q,\langle
o,t\rangle)$ is _reachable_ within $R$ steps from state $q_{0}$ at cost
$C_{R}=\prod_{i=0}^{R}c_{i}$ if, starting from state $q_{0}$, there exist
$q_{1},q_{2},\dots,q_{R-1}$ such that $t(q_{i})(q_{i+1})=c_{i}$ for
$i=0,\dots,R-1$, and $c_{R}=o(q_{R})$. Then the stream _computed_ by the state
$q_{0}$ is defined as $(s_{0},s_{1},s_{2},\dots)$ such that the element
$s_{j}$ is obtained by adding up the costs of all paths of length $j$ from the
state $q_{0}$ to any reachable state.

######  Theorem 3.5.

Let $\sigma$ be the hidden stream fixed at the beginning of Section 3. The
output cSFG returned by Algorithm 1 (and hence the corresponding WFA) compute
$\sigma$.

######  Proof 3.6.

We first prove the statement for the WFA. We know the values
$\sigma_{0},\dots,\sigma_{n-1}$ from the membership queries. Hence, for the
first $n$ elements of the stream computed by the state $q_{0}$ we have:

$\begin{cases}s_{0}=C_{0}=o(q_{0})=\sigma_{0}\\\
s_{1}=C_{1}=t(q_{0})(q_{1})\times
o(q_{1})=1\times\sigma^{(1)}_{0}=\sigma_{1}\\\ \vdots\\\
s_{n-1}=C_{n-1}=t(q_{0})(q_{1})\times\dots\times t(q_{n-2})(q_{n-1})\times
o(q_{n-1})=1\times\dots\times
1\times\sigma^{(n-1)}_{0}=\sigma_{n-1}\end{cases}$

as expected. Until now, there existed a unique path of length $j$ from $q_{0}$
to $q_{j}$, $0\leq j\leq n-1$. Let us then show how an element of the stream,
namely $s_{n}$, is calculated when this isn’t the case anymore, i.e. for
$j\geq n$:

$s_{n}=\sum C_{n}=\sum_{i=0}^{n-1}t(q_{0})(q_{1})\times\dots\times
t(q_{n-2})(q_{n-1})\times t(q_{n-1})(q_{i})\times
o(q_{i})=\sum_{i=0}^{n-1}c_{i}\times\sigma^{(i)}_{0}$

which is precisely the definition of our rational stream $\sigma$. This
concludes the proof for WFA.

Now, recall that our cSFG has $n$ registers. We can think of each register
$r^{i}$, where $i=0,\dots,n-1$, as having a certain stream $\upsilon^{i}$
feeding into it, and a certain stream $\tau^{i}$ coming out of it. We then
have $n$ linear equations in the form $\tau^{i}=r^{i}+X\times\upsilon^{i}$. We
obtain the following set of equations:

$\begin{cases}\tau^{0}=r^{0}+X\times(c_{0}\times\tau^{n-1})\\\
\tau^{1}=r^{1}+X\times(\tau^{0}+c_{1}\times\tau^{n-1})\\\ \vdots\\\
\tau^{n-1}=r^{n-1}+X\times(\tau^{n-2}+c_{n-1}\times\tau^{n-1})\end{cases}$

Notice that we can rewrite each $\tau^{i}$ in terms of $\tau^{n-1}$ and
substitute $\tau^{n-2}$ in the last equation. We then get

$\tau^{n-1}=(r^{n-1},r^{n-2}+c_{n-1}\times\tau^{n-1}_{0},r^{n-3}+c_{n-2}\times\tau^{n-1}_{0}+c_{n-1}\times\tau^{n-1}_{1},\dots)$

We can see that the definition of the stream is recursive and depends on the
values of $r^{i}$. We can calculate each of $\tau^{i}$ in the exact same
manner. Recall that the constructed cSFG, based on its structure in the
algorithm, computes $\sigma$ if
$\sigma_{0}\times\tau^{0}+\sigma_{1}\times\tau^{1}+\dots+\sigma_{n-1}\times\tau^{n-1}=\sigma$.
Hence, by adding up the corresponding elements $\tau^{i}_{j}$ of $n$ streams
and equating the result to the known $\sigma_{j}$, $j=0,\dots,n-1$, we obtain
$n$ equations in $n$ unknowns $r^{0},\dots,r^{n-1}$. This way, we have
$\sigma_{0}\times r^{0}+\dots+\sigma_{n-1}\times r^{n-1}=\sigma_{0}$, and so
on. Having obtained the solution, we now know the initial register values of
our cSFG, and hence, by definition, the resulting cSFG computes the expected
stream $\sigma$.

##  4 Complexity

We first note that the algorithm always terminates. Computing the coefficient
function consists of checking for linear independence of stream derivatives,
of which there are finitely many (Lemma 2.1). Hence, linear dependence is
guaranteed to be reached within a finite number of the main loop executions.

Let $n$ be the number of linearly independent derivatives of the stream that
the cSFG computes (which is also the number of registers in the cSFG we will
learn). Then we have that (1) $|S|\leq n$, (2) $|E|\leq n$, and (3) the main
loop in the algorithm is repeated at most $n$ times. All of these hold by
Lemma 2.1.

Now, let us evaluate complexity bounds of parts of the algorithm inside the
main loop. We begin by determining the complexity of the coefficient function
(line 4). Since it checks whether the row $i$ is a linear combination of rows
corresponding to elements of $S$, each call amounts to solving a system of at
most $n$ linear equations in at most $n$ unknowns, as $S$ and $E$ expand
evenly. This can be done using Gauss’s method with complexity $O(n^{3})$ (Boyd
and Vandenberghe, 2018; Farebrother, 1988, p. 12). Since we make at most $n$
calls to the coefficient function throughout the algorithm (as there are $n$
linearly independent derivatives), we need to solve at most $n$ such systems
of equations. So the overall complexity of closing the table is $O(n^{4})$. As
a side note, the counter on line 7 of the algorithm is introduced precisely to
enable calling the coefficient function as infrequently as possible, as it is
a task of, as we will deduce later, highest computational complexity.

Next, we consider the complexity of filling the table. In the worst case, the
table is of size $|S||E|=n^{2}$. However, since repeated table entries do not
need to be re-queried and each membership query for filling one entry of the
table corresponds to a stream index which is at most $n+n=2n$, the number of
membership queries and hence the complexity of filling the table is $O(n)$. As
the main loop in the algorithm is executed at most $n$ times, the number of
equivalence queries is $O(n)$.

Finally, let us evaluate the complexity of constructing a cSFG (line 14). The
multiplier values come from the first $n$ elements of the stream and from the
coefficients $c_{0},\dots,c_{n-1}$ from Lemma 2.1; all we have to do now is
find the initial register values. There are $n$ registers, so we have to solve
$n$ linear equations in $n$ unknowns (this appears in the proof of Theorem
3.5). It can be done via Gauss’s method of complexity $O(n^{3})$.

We conclude that the task of highest complexity is closing the table,
$O(n^{4})$, which is hence also the overall complexity of our algorithm; i.e.
it runs in polynomial time.

######  Remark 4.1.

We note that the bound can be marginally improved by a slight modification of
the algorithm. Instead of expanding $S$ and $E$ linearly, we could do so
exponentially, i.e. by doubling their sizes whenever the table is not closed
and after each unsuccessful equivalence query. This way, we would make at most
$O(log\text{ }n)$ equivalence queries and would only make $O(log\text{ }n)$
calls to the coefficient function. The overall complexity of the algorithm
would then be $O(n^{3}log\text{ }n)$.

Our algorithm has a strictly lower complexity bound than those of learning
algorithms for WFAs restricted to the singleton alphabet case. Denote by $m$
the size of the longest counterexample provided by oracles in such algorithms.
In Bergadano and Varricchio (1996), the bound is $O(n^{5}m^{2})$ and in Beimel
et al. (2000) the bound is $O(n^{3.376}+mn^{3})$. In the case of the learning
algorithms for _weighted tree automata_ (WTA) – a generalisation of WFA, the
algorithm by Maletti (2007) for deterministic WTA simplifies in our case to
having the complexity $O(n^{3}(n+m))$. We note that the lack of the need for
counterexamples in our algorithm allows for the improvement in complexity, as
counterexamples are provided non-deterministically and can be arbitrarily
large. This, as well as the procedure outlined in Remark 4.1, is the case
precisely due to the rational streams’ property of having a finite number of
linearly independent derivatives.

We also calculated the computational complexity of the algorithm in van Heerdt
(2020). The algorithm is for general WFA and relies on the existence of the
so-called closedness strategy that checks whether an observation table is
closed; it only checks for closedness and not for consistency, as the
counterexamples are handled in a way that the constructed observation table is
always consistent. Said closedness strategy is a rather generic function, and
in order to be able to compare the algorithms, we assume that in the case of a
singleton alphabet it would mirror the behaviour of our coefficient function;
it is, just like in our algorithm, the task of highest complexity. Hence, as
$|E|$ is bounded by $m+1$ (it only expands from suffixes of counterexamples)
and $|S|$ is bounded by $n$, we have that the complexity of solving at most
$m+1$ equations in at most $n$ variables is $O(n(m+1)\text{
min}(n,m+1))=O(nm\text{ min}(n,m))$. Since $\mathtt{cs}$ is called when
assigning values to the transition function for each state whenever a
hypothesis is constructed, and $|S|\leq n$ and the outer loop is repeated at
most $n$ times, the overall complexity of the algorithm is
$O(n^{3}m\min(n,m))$. However, if we assume that $\mathtt{cs}$ is never
recomputed for rows in $S$ during the hypothesis construction even after
adding counterexamples to $E$, the complexity bound is $O(n^{2}m\min(n,m))$.
In both cases, our algorithm has a better bound – as noted earlier, $m$ can be
arbitrarily large. We thus conclude that our algorithm genuinely uses the
structure of cSFGs, rather than just restricting a generic algorithm for WFAs.

##  5 Concluding Remarks

The main contribution of this work is establishing a learning algorithm for
closed signal flow graphs and calculating its computational complexity,
considering both the time complexity and the number of queries made. To the
best of our knowledge, this work introduces the first algorithm of its kind
that allows for learning closed signal flow graphs. Our results show that the
proposed algorithm has a better complexity than that for arbitrary weighted
automata in van Heerdt (2020), even if the latter one is restricted to WFA
over a singleton alphabet. It also has a better computational complexity than
learning algorithms for WFA introduced in Bergadano and Varricchio (1996) and
in Beimel et al. (2000).

An obvious direction for future work is to find a learning algorithm for all
SFGs, but that would require proving their equivalence to some family of
automata first. In their work, Basold et al. (2014) show the equivalence
between open SFGs and Mealy Machines; the authors of this paper would also
wish to establish such equivalence between SFGs and (some subset of) WFAs. An
interesting related question is whether learning respects the compositional
structure of SFGs: is learning a composite SFG equivalent to learning its
parts and composing back?

Automata learning has extensive applications in areas such as network protocol
analysis (Comparetti et al., 2009), software verification (Peled et al., 1999)
and natural language processing (Knight and May, 2009). Learning signal flow
graphs opens the door to exploring similar techniques in control theory as
well as in the design and analysis of related families of systems, such as
digital circuits (Ghica et al., 2024).

## Acknowledgements

The authors would like to thank Wojciech Różowski for reading and providing
helpful feedback on this paper. The authors would also like to thank the
anonymous reviewers of the Learning and Automata workshop (LearnAut 2024) for
their detailed comments and suggestions, especially the ones regarding the
reduction in complexity of the algorithm.

## References

  * Angluin (1987) Dana Angluin.  Learning regular sets from queries and counterexamples.  _Information and Computation_ , 75(2):87–106, 1987.  ISSN 0890-5401.  https://doi.org/10.1016/0890-5401(87)90052-6.  URL https://www.sciencedirect.com/science/article/pii/0890540187900526.
  * Baez and Erbele (2008) John C Baez and Jason Erbele.  Categories in control.  _Theory and Applications of Categories_ , 30, 2008.
  * Baier et al. (2009) Christel Baier, Marcus Größer, and Frank Ciesinski.  Model checking linear-time properties of probabilistic systems.  In _Handbook of Weighted automata_ , pages 519–570. Springer, 2009\.
  * Basold et al. (2014) Henning Basold, Marcello Bonsangue, Helle Hvid Hansen, and Jan Rutten.  (co) algebraic characterizations of signal flow graphs.  _Horizons of the Mind. A Tribute to Prakash Panangaden: Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday_ , pages 124–145, 2014.
  * Beimel et al. (2000) Amos Beimel, Francesco Bergadano, Nader H Bshouty, Eyal Kushilevitz, and Stefano Varricchio.  Learning functions represented as multiplicity automata.  _Journal of the ACM (JACM)_ , 47(3):506–530, 2000\.
  * Bergadano and Varricchio (1996) Francesco Bergadano and Stefano Varricchio.  Learning behaviors of automata from multiplicity and equivalence queries.  _SIAM Journal on Computing_ , 25(6):1268–1280, 1996.
  * Berstel and Reutenauer (1988) Jean Berstel and Christophe Reutenauer.  _Rational series and their languages_ , volume 12.  Springer-Verlag, 1988.
  * Bonchi et al. (2012) Filippo Bonchi, Marcello Bonsangue, Michele Boreale, Jan Rutten, and Alexandra Silva.  A coalgebraic perspective on linear weighted automata.  _Information and Computation_ , 211:77–105, 2012.
  * Bonchi et al. (2014) Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi.  A categorical semantics of signal flow graphs.  In Paolo Baldan and Daniele Gorla, editors, _CONCUR 2014 – Concurrency Theory_ , pages 435–450, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.  ISBN 978-3-662-44584-6.
  * Bonchi et al. (2017) Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi.  The calculus of signal flow diagrams i: Linear relations on streams.  _Information and Computation_ , 252:2–29, 2017.  ISSN 0890-5401.  https://doi.org/10.1016/j.ic.2016.03.002.  URL https://www.sciencedirect.com/science/article/pii/S0890540116000390.
  * Bonchi et al. (2021) Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi.  _A Survey of Compositional Signal Flow Theory_ , pages 29–56.  Springer International Publishing, Cham, 2021.  ISBN 978-3-030-81701-5.  10.1007/978-3-030-81701-5_2.  URL https://doi.org/10.1007/978-3-030-81701-5_2.
  * Boyd and Vandenberghe (2018) Stephen Boyd and Lieven Vandenberghe.  _Introduction to applied linear algebra: vectors, matrices, and least squares_.  Cambridge university press, 2018.
  * Comparetti et al. (2009) Paolo Milani Comparetti, Gilbert Wondracek, Christopher Kruegel, and Engin Kirda.  Prospex: Protocol specification extraction.  In _2009 30th IEEE Symposium on Security and Privacy_ , pages 110–125. IEEE, 2009.
  * Culik II and Kari (1993) Karel Culik II and Jarkko Kari.  Image compression using weighted finite automata.  _Computers & Graphics_, 17(3):305–313, 1993\.
  * Farebrother (1988) Richard William Farebrother.  _Linear least squares computations_.  Statistics, textbooks and monographs ; v. 91. Marcel Dekker, New York, 1988.  ISBN 0824776615.
  * Ghica et al. (2024) Dan R. Ghica, George Kaye, and David Sprunger.  A fully compositional theory of sequential digital circuits: Denotational, operational and algebraic semantics, 2024.
  * Isidori (1985) Alberto Isidori.  _Nonlinear control systems: an introduction_.  Springer, 1985.
  * Knight and May (2009) Kevin Knight and Jonathan May.  Applications of weighted automata in natural language processing.  In _Handbook of Weighted Automata_ , pages 571–596. Springer, 2009\.
  * Lathi (1998) Bhagwandas Pannalal Lathi.  _Signal processing and linear systems_.  Oxford University Press, Oxford, 1998.
  * Maletti (2007) Andreas Maletti.  Learning deterministically recognizable tree series—revisited.  In _International Conference on Algebraic Informatics_ , pages 218–235. Springer, 2007.
  * Milius (2010) Stefan Milius.  A sound and complete calculus for finite stream circuits.  In _Proc. 25th Annual Symposium on Logic in Computer Science (LICS’10)_ , pages 449–458, 2010.
  * Mohri et al. (2005) Mehryar Mohri, Fernando Pereira, and Michael Riley.  Weighted automata in text and speech processing.  _arXiv preprint cs/0503077_ , 2005.
  * Peled et al. (1999) Doron Peled, Moshe Y Vardi, and Mihalis Yannakakis.  Black box checking.  In _International Conference on Protocol Specification, Testing and Verification_ , pages 225–240. Springer, 1999.
  * Rutten (2001) Jan JMM Rutten.  Elements of stream calculus:(an extensive exercise in coinduction).  _Electronic Notes in Theoretical Computer Science_ , 45:358–423, 2001.
  * Rutten (2005) Jan JMM Rutten.  A tutorial on coinductive stream calculus and signal flow graphs.  _Theoretical Computer Science_ , 343(3):443–481, 2005.  ISSN 0304-3975.  https://doi.org/10.1016/j.tcs.2005.06.019.  URL https://www.sciencedirect.com/science/article/pii/S0304397505003683.  Formal Methods for Components and Objects.
  * Rutten (2008) Jan JMM Rutten.  Rational streams coalgebraically.  _Logical Methods in Computer Science_ , Volume 4, Issue 3, sep 2008\.  ISSN 1860-5974.  10.2168/lmcs-4(3:9)2008.  URL http://dx.doi.org/10.2168/LMCS-4(3:9)2008.
  * Schützenberger (1961) Marcel Paul Schützenberger.  On the definition of a family of automata.  _Inf. Control._ , 4(2-3):245–270, 1961.
  * Shannon (1942) Claude E Shannon.  _The Theory and Design of Linear Differential Equation Machines. Report to National Defense Research Council, January, 1942._ , pages 514–559.  Wiley-IEEE Press, 1942.  10.1109/9780470544242.ch33.
  * van Heerdt (2020) Gerco van Heerdt.  _CALF: Categorical automata learning framework_.  Doctoral dissertation, University College London, 2020.