# SparCAssist: A Model Risk Assessment Assistant Based on Sparse Generated
Counterfactuals

Zijian Zhang<EMAIL_ADDRESS>0000-0001-9000-4678 L3S Research CenterAppelstr.
9aHannoverLower SaxonyGermany30167 ,  Vinay Setty  0000-0002-9777-6758
<EMAIL_ADDRESS>L3S Research CenterGermany University of
StavangerStavangerNorway and  Avishek Anand<EMAIL_ADDRESS>0000-0002-0163-0739 L3S Research CenterGermany Delft University of
technologyDelftNetherlands

(2022)

###### Abstract.

We introduce SparCAssist, a general-purpose risk assessment tool for the
machine learning models trained for language tasks. It evaluates models’ risk
by inspecting their behavior on counterfactuals, namely out-of-distribution
instances generated based on the given data instance. The counterfactuals are
generated by replacing tokens in rational subsequences identified by ExPred,
while the replacements are retrieved using HotFlip or Masked Language Model
based algorithms. The main purpose of our system is to help the human
annotators to assess the model’s risk on deployment. The counterfactual
instances generated during the assessment are the by-product and can be used
to train more robust NLP models in the future.

Interpretable Machine Learning, Counterfactual Interpretation, Data-annotation
tools, Human-in-the-loop Machine Learning

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
45th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 11–15, 2022; Madrid, Spain††booktitle: Proceedings
of the 45th International ACM SIGIR Conference on Research and Development in
Information Retrieval (SIGIR ’22), July 11–15, 2022, Madrid, Spain††price:
15.00††doi: 10.1145/3477495.3531677††isbn: 978-1-4503-8732-3/22/07††ccs:
Information systems Online analytical processing††ccs: Human-centered
computing User interface toolkits††ccs: Computing methodologies Reasoning
about belief and knowledge

##  1\. Introduction

In this paper we present a demonstration of SparCAssist: a tool for human-
assisted debugging of machine learning (ML) models for language tasks.
Debugging machine learning models in terms of estimating if a trained model is
fit for deployment is considered more of an art than a science with a lot
depending on the heuristics employed by the model developer (Bhatt et al.,
2020). Standard deployment checks often involve heavy reliance on performance
metrics on validation and test sets to evaluate the generalization and
robustness of systems. That means there is heavy focus on inspecting
incorrectly predicted instances. We argue that ensuring good performance is
not enough. Deep neural networks for language tasks are known to be
particularly fragile on out-of-distribution instances even if they deliver
impressive validation set accuracy (Ross et al., 2021).

Some of the known risks of deploying such over-parameterized models such as
transformers is that they tend to memorize undesirable shortcuts in the
training data that lead to reasonable validation performance but leads to
failures in real-world scenarios (Zheng et al., 2021). Unlike common practice
of ML metrics, we propose to provide a system that uses counterfactuals as
examples to help the user, in this case the model developer, to understand the
risks of the model under consideration. Specifically, given a trained ML
model, our intention is to allow the user to identify instances that have
potential risk during deployment. An instance is considered risky if its minor
human-understandable modifications result in undesirable predictions.

Consider a document classification task of classifying review text of movies
into positive and negative sentiments. Say a trained sentiment classifier
classifies the input “the movie was awesome” as a positive sentiment. However,
by slightly perturbing it to a counterfactual sentence “the movie was is
awesome” results in a negative sentiment. This counterfactual sentence exposes
two potential risks in the model, firstly, the model focuses on non-essential
words towards making a prediction and secondly, the model is not robust under
non-decisive perturbation. Other approaches that provide insights into the
reasons behind predictions of complex machine learning models, a large variety
of post-hoc explanation methods have been proposed (Ribeiro et al., 2016;
Lundberg and Lee, 2017; Sundararajan et al., 2017). However, all these
explanation approaches operate on existing instances on the training or the
test set. Therefore they cannot effectively assess the potential risk when the
models are deployed in the field.

The aim of SparCAssist is to modify existing counterfactual generation
approaches to help humans identify instances that might be particularly risky.
We allow users enough control to choose input instances that are of interest
and pieces of text out of them within that might be important for the task
under consideration. In allowing a fine-grained control to the inputs choosing
and feedback providing, the users are able to both get a sense of the
functioning of the model as well as be educated about the potential risks it
might possess. In SparCAssist, we work on the task of sentiment classification
as an example but in principle SparCAssist can be extended to a large set of
language tasks, for example question answering, fact checking, textual
entailment etc.

The system then provides multiple “perturbations” of the input sentence that
result in a change in the prediction. The perturbations should be small enough
so that we can effectively assess the model’s local risk, specifically in the
close vicinity surrounding a given instance. Therefore, we are only interested
in sparse perturbations or we only allow a small number of perturbations to
the original input. The users’ role is to assess whether the generated
counterfactual is plausible, natural and if the model’s prediction is correct
on counterfactuals. Plausible here means that the input text is believed to be
written or conceived by a human. In terms of approach we start from a trained
model and identify sentences that need to be scrutinized. We choose this
subset of sentences using ExPred(Zhang et al., 2021a), a select-then-predict
system that is interpretable by design. We then use adversarial approaches
like HotFlip (Ebrahimi et al., 2018) and Masked Language Model approaches to
generate counterfactuals. These generated counterfactuals are then shown to
humans who in turn interact with the suggestions to establish its plausibility
and validity. Finally, we compute the risk of the model under consideration
from the trail of user interactions.

The primary goal is to assess the model’s deficiencies using the
perturbations, and then our secondary goal is to generate a dataset of
counterfactual explanations, which are grammatically plausible and meaningful
from human perspective, could be the by-product of the system.

###  1.1. Related Work

We divide the related work into two parts – counterfactual generation, and
automated approaches for model debugging. The counterfactual generation
approaches can be categorized into two classes: automatic approaches and
human-annotation approaches. Automatic approaches for generating
counterfactuals are predominantly based on gradient-based optimization to
generate adversarial examples like HotFlip (Ebrahimi et al., 2018), AutoPrompt
(Shin et al., 2020a), and Imitation Attacks (Wallace et al., 2020). Another
set of approaches to automatically generate counterfactuals is to use prompt-
based approaches like Polyjuice (Wu et al., 2021). However, the main
disadvantage of automatic approaches is that the generated counterfactuals are
not natural, i.e., likely to be not plausible from human perspective. Prompt-
based approaches are slightly more natural that gradient-based approaches, but
they rely on heuristic prompts that have to be manually provided.

On the other hand, some approaches conduct user-study with crowd workers to
obtain human-understandable counterfactual datasets (McDonnell et al., 2016;
Kaushik et al., 2020). These approaches are understandably non-scalable and
exhibit high variance due to subjectivity and the well-known Rashomon effect
(Davis et al., 2015). We use both gradient-based and prompt-based approaches
for counterfactual generation but instead use humans-in-the-loop methods for
quality assessment. More precisely, we take a hybrid approach for producing
counterfactuals with utility of the counterfactual as the most desirable
outcome.

The second piece of related work is regarding debugging ML models that have
been used in text classification (Monarch, 2021), search (Singh and Anand,
2018; Singh et al., 2021; Singh and Anand, 2020), and many language tasks in
general (Idahl et al., 2021; Funke et al., 2021) by using explanations or
interpretable machine learning approaches called explanation-based human
debugging (EBHD). Lertvittayakumjorn and Toni (2021) recently review EBHD
approaches that exploit explanations to enable humans to give feedback and
debug NLP models. Unlike adversarial algorithms (Misra, 2019; Wallace et al.,
2020) the goals of these systems is to explicitly expose model’s deployment
risk by ensuring that models are _right for the right reason_. In addition to
academic efforts, model debugging tools like (Zhang et al., 2021b; Singh and
Anand, 2019),
SageMaker111https://docs.aws.amazon.com/sagemaker/latest/dg/train-
debugger.html provided by Amazon are also available. Other human-in-the loop
systems include (Singh et al., 2016; Holzmann and Anand, 2016) to update
models and knowledge bases. However, they mostly focus on training process and
do not provide a post-hoc model risk assessment.

##  2\. Solution Approach

The primary goal of our SparCAssist tool is to assist users to assess the
deployment risk of the NLP classification model trained on specific datasets
using counterfactual instances (counterfactuals). The input to SparCAssist is
a model together with a dataset using which the risk assessment of the model
is to be performed. The SparCAssist generates counterfactuals based on a
selected data instance and tries to flip the model’s prediction for that
instance. The tool assesses the risks of the model based on the user’s
feedback on the plausibility and meaningfulness of the counterfactuals. The
secondary output SparCAssist tool is plausible and meaningful counterfactual
dataset for future training. In this section, we state our problem by first
defining the counterfactual formally with its three essential properties and
then formalize the model’s risk.

###  2.1. Interpretation Using Counterfactuals

Interpretation-by-Counterfactuals, also known as interpretation using minimal
contrastives (Ross et al., 2021) is a model-interpretation technique that
allows humans to understand the reason behind prediction by investigating
models’ behavior under counterfactual inputs (Miller, 2019; Lipton, 1990).
According to (Ross et al., 2021; Hilton, 2017), in order to assess the risk of
the models, the counterfactuals need to satisfy following rules:

  * 1

The number of replaced tokens should be as few as possible.

  * 2

The counterfactual instance should be plausible and meaningful (Chomsky,
2009).

Like in HotFlip (Ebrahimi et al., 2018) and Polyjuice (Wu et al., 2021), we
mainly focus on the counterfactual generated by replacing the tokens. These
two approaches, however, do not constrain the number of replaceable tokens
while generating the counterfactuals. This will result in an overwhelming
number of alternative counterfactuals for human annotators. In SparCAssist, we
address this issue by firstly focusing on sentences containing rationale
subsequences identified by the ExPred model (Zhang et al., 2021a). We then
only allow _rationale_ tokens identified by ExPred in the selected sentence to
be replaced, while the other tokens are kept fixed. Alternatively to the
ExPred, users can manually select the tokens allowed to be replaced in the
rationale sentences.

More formally, we use $\mathbf{x}=[x_{0},x_{1},\cdots,x_{l}]$ to represent the
input sequence (rationale sentence) to our tool and the model to be assessed
is represented as $\mathcal{M}$, while it’s predicted label for a given
instance $x$ is denoted as $\hat{y}=\mathcal{M}(\mathbf{x}\odot\mathbf{m})$,
where $\mathbf{m}\in\\{0,1\\}^{l}$ is the rationale mask, $\odot$ stands for
element-wise multiplication. We then define a counterfactual generation
function $C_{x_{i}\to v}$ which replaces the rationale token $x_{i}$ with a
counterfactual token $v$ from the vocabulary $V$. A counterfactual with only
one token replaced is called 1-counterfactual and represented as
$\mathbf{c}^{1}_{\mathbf{x}}=C_{x_{i}\to v|i\in\mathbb{1}(m),v\in
V}(\mathbf{m}\odot\mathbf{x})$. The condition $i\in\mathbb{1}(m)$ restricts
the tokens to be replaced to the rational mask $\mathbf{m}$. We repeat the
above processes until the prediction on the counterfactual sentence changes.

###  2.2. Model Risk Assessment

We consider a model as “risky”, when its behavior on the counterfactuals doe
not match domain experts’ (users’) decision, despite its high accuracy on the
given, or inside-distribution, instances, including instances from the train,
dev-test, and test set (Koyama and Yamaguchi, 2020). Since the global risk is
usually intractable (Ribeiro et al., 2018), we consider its local counterpart
instead, namely how wrong does the model predict on the counterfactuals
sampled from the vicinity of an instance in the dataset.

Figure 1. Risk and unexpected behavior in the vicinity of an inside-
distribution-instance $\mathbf{x}$. The dark gray area is the risky area.

As illustrated in Fig. 1, for a counterfactual $\mathbf{x}^{c}$ sampled from
the vicinity of an inside-distribution instance $\mathbf{x}^{c}\in
S(\mathbf{x})$, if the decision of the model $\mathcal{M}(\mathbf{x}^{c})$ is
dissonant with the decision of domain experts’, we call this an “risky
behavior” and the area resulting in risky behavior “risky volume”. The local
risk score of the model is the ratio between risky volume and the volume of
$S$. In more detail, we assume an “optimal” decision boundary $B^{*}$ as a
hyperplane resulting in decisions aligning with domain experts’ prediction,
while $B$ is the decision boundary of the model. The model’s local risk in $S$
is then the ratio between the volume of $V$ and $\mathcal{S}$, where $V$ is
the interior enclosed by $S$ and both decision boundaries as $V$, namely
$\partial{V}=(B^{*}\cup B)\cap S$. We can estimate it by dividing the number
of samples resulting in risky behaviors with the number of samples drawn
universally from $S$ using the Monte-Carlo strategy. However, it is difficult
to draw samples from such vicinity due to the discreetness of human language
sentences. Therefore, instead of drawing counterfactual samples universally,
we focus on such counterfactuals resulting in the model’s prediction flipping.
Such examples locate right across the model’s decision boundary and will most
likely expose the model’s risk.

For example, the sentiment classifier should predict $\mathbf{x}=$“I love this
movie.” as positive and the counterfactuals $\mathbf{x}^{c}_{2}=$“I love
_hate_ this movie.” to negative. Because this is in accord with users’
decisions, the model’s risk does not increase. But if the model predicts
$\mathbf{x}^{c}_{1}=$“I like this movie  _film_.” to negative, the risk score
increases, as users will not agree with this prediction. We ask the annotator
to rate the prediction ($f\in{1-5}$, $f$ for faithfulness) by asking to how
much extent does the model predicts in concord with her expectation. We do not
ask for a binary rating because the optimal decision boundaries are vague and
subjective. Then for each annotator, we calculate her risk score around the
instance $\mathbf{x}$ by:
$\text{risk}=\sum_{\mathbf{x}^{c}\in\mathcal{X}^{c}}(5-f(\mathbf{x}^{c}))/|\mathcal{X}^{c}|$,
where $\mathcal{X}^{c}$ represents the set of counterfactual samples provided
by this annotator. The final risk of the model in $S$ is estimated by the
weighted average of risk scores from all annotators, where the weight is the
number of the counterfactuals generated in her/his session. It is worth
mentioning that it requires further research to decide the exact number of
counterfactuals needed to effectively evaluate the model’s risk.

##  3\. System Design

Figure 2. The system diagram of the counterfactual generation assistant Figure
3. The screenshot of the SparCAssist user interface

As illustrated in Figure 2, we decompose the SparCAssist system into three
components: Rationale Selection, Position Attribution and Word Replacement.
The SparCAssist generates counterfactuals are as follows:

  1. (1)

It first randomly selects an instance $\mathbf{x}$ from the given dataset
which may or may not be labeled. For the demo, we use the “Movies” datasets
for the sentiment analysis task (DeYoung et al., 2020).

  2. (2)

It then leverages the ExPred model (Zhang et al., 2021a) which is a two-phase
select-then-predict model pre-trained on the movies dataset to select the
rationale tokens.

  3. (3)

For all those rationale tokens, we attribute their positions and select
candidate position(s) based on the attribution. In our SparCAssist, we are
only interested in such counterfactuals changes the model’s prediction
($\mathcal{M}(\mathbf{c})\neq\hat{y}$), therefore:

  4. (4)

It replaces the tokens on each selected position so that the estimated loss
regarding the alternative label other than the original prediction is
minimized.

  5. (5)

It then selects the final single counterfactual with only one token replaced
based on their actual prediction loss.

  6. (6)

We repeat steps 3 to 5 until the prediction changes or the number of word
replacements exceeds a pre-defined upper limit. Based on our empirical
observation, the set the upper limit to five replacements.

We integrate two counterfactual generation approaches to SparCAssist, the
Taylor-expansion based HotFlip and a Masked Language Model (MLM)-based
algorithm used in Polyjuice. These two approaches are decomposed into two
phases, namely position attribution and token selection as step 3 and 4
introduced above. We explain these two approaches below:

#### HotFlip approach:

For this approach, we follow (Ebrahimi et al., 2018) to search for positions
and words using the beam search. More formally. we attribute positions with
the dot-product of corresponding token embedding with the partial derivative
of the loss regarding the alternated prediction label with respect to the
token embedding, i.e. $\frac{\partial}{\partial
x_{i}}l(\hat{y},\bar{\hat{y}}\neq\hat{y})\cdot\mathbf{e_{i}}$, where
$\mathbf{e_{i}}$ represents the embedding of the i-th token. We select the
top-$p$, $p\leq r$ of the position, where $r$ is the number of rationale
tokens. Then in token selection, for each select position we choose the token
that maximizes the dot-product of the new token’s embedding with the partial
derivation, i.e. $v_{replace}=argmax_{v\in V}\frac{\partial}{\partial
x_{i}}l(\hat{y},\bar{\hat{y}}\neq\hat{y})\mathbf{e^{v}}$.

#### Masked Language Modelling-based approach:

For this method, we first construct the MLM model’s input with the prompt
template as suggested in (Liu et al., 2021; Shin et al., 2020b; Lester et al.,
2021) as follows: _“¡masked sequence¿” the sentiment of this review is
“¡alternative label¿”_. For example, _“this movie is[mask]” the sentiment of
this review is “negative”_.

Unlike in the hotflip, where the positions are attributed with the product of
gradient and the embedding, there is no such close-form position attribution
in the MLM-based method. Therefore we trivially attribute all tokens with the
same score For the token replacement, we mask each rationale word and apply
the prompt template, then predict the masked word using a pre-trained blank-
filling model based on RoBERTa (Liu et al., 2019) (with pre-trained weights
from the Huggingface framework222https://huggingface.co/roberta-large). For
each word position, we keep the token with the highest score, then we select
the final counterfactual which minimizes the loss with respect to the
alternative label.

A screenshot of our system is illustrated in Fig. 3. The top part shows
widgets to upload the model and the corresponding dataset. The lower part is
split into two columns:

1\. The left part (“1. Select a sentence”) presents a document selected from
the dataset, where rationale tokens are highlighted with boldface font. By
default, all sentences containing at least one rationale token are displayed.
The users can expand the full review by clicking the “Expand all” button. Even
after restricting the sentences using the rationale masks, the length of the
whole review document is still large, users can therefore select a single
sentence at a time to inspect its counterfactuals.

2\. In the right hand side, (“2. How do you like the counterfactuals?”) the
counterfactuals are displayed following the order of word replacement, with a
replaced word highlighted. As introduced in the previous section, the users
are asked to evaluate the plausibility and meaningfulness, together with the
faithfulness of the prediction, if the user is satisfied with the current
counterfactual generation. The users may also choose to use the default ExPred
rationale masks or provide a custom mask by selecting the alternative
rationale tokens according to their preference.

##  4\. Conclusion and Future Work

In this paper, we propose SparCAssist, an ML model debugging tool. SparCAssist
allows users to construct word-replacement-based counterfactual instances of
rationale masked sentences. These counterfactuals are helpful for better
understanding of model’s behavior and identifying deployment risks of the
underlying the model. The SparCAssist prunes the choices of counterfactuals by
restricting the range of variable tokens to rationale tokens only. This
minimizes the number of counterfactual choices presented to the users.
Optionally, the users can also specify custom masks for the variable tokens.
We implement HotFlip and Masked Language Model-based approaches to retrieve
out-of-distribution (OOD) tokens and enable the users to evaluate generation
results. It is also possible to deploy the SparCAssist system and gather
counterfactual annotations with evaluations from large crowd-workers through
web browsers. Another advantage of our tool is that it is flexible and
generic. It allows debugging any ML model with a user chosen dataset. It
easily supports replacing the rationale-masking, position attribution and OOD
tokens selection components with other methods.

As for the future work, as mentioned in Sect. 2, we plan to conduct the user
study to figure out the exact number of counterfactual samples needed to
evaluate models. Furthermore, a visualization of all counterfactual generated
by current user, nominated with their softmax score, would be helpful to get a
better understanding of the model’s local behavior. Finally, we plan to
collect and release a large-scale human plausible counterfactual dataset using
the crowd-sourcing deployment of our tool.

##  5\. Acknowledgment

This work is partially funded by project MIRROR under grant agreement No.
832921 (project MIRROR from the European Commission: Migration-Related Risks
caused by misconceptions of Opportunities and Requirement) and project
ROXANNE, the European Union’s Horizon 2020 research and innovation program
under grant agreement No. 833635.

## References

  * (1)
  * Bhatt et al. (2020) Umang Bhatt, Alice Xiang, Shubham Sharma, Adrian Weller, Ankur Taly, Yunhan Jia, Joydeep Ghosh, Ruchir Puri, José M. F. Moura, and Peter Eckersley. 2020.  Explainable Machine Learning in Deployment. In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ (Barcelona, Spain) _(FAT* ’20)_. Association for Computing Machinery, New York, NY, USA, 648–657.  https://doi.org/10.1145/3351095.3375624
  * Chomsky (2009) Noam Chomsky. 2009\.  _Syntactic structures_.  De Gruyter Mouton.
  * Davis et al. (2015) Blair Davis, Robert Anderson, and Jan Walls. 2015\.  _Rashomon effects: Kurosawa, Rashomon and their legacies_.  Routledge.
  * DeYoung et al. (2020) Jay DeYoung, Sarthak Jain, Nazneen Fatema Rajani, Eric Lehman, Caiming Xiong, Richard Socher, and Byron C. Wallace. 2020.  ERASER: A Benchmark to Evaluate Rationalized NLP Models. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Online, 4443–4458.  https://doi.org/10.18653/v1/2020.acl-main.408
  * Ebrahimi et al. (2018) Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. 2018\.  HotFlip: White-Box Adversarial Examples for Text Classification. In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_. Association for Computational Linguistics, Melbourne, Australia, 31–36.  https://doi.org/10.18653/v1/P18-2006
  * Funke et al. (2021) Thorben Funke, Megha Khosla, and Avishek Anand. 2021\.  Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks.  _arXiv preprint arXiv:2105.08621_ (2021).
  * Hilton (2017) Denis Hilton. 2017\.  Social attribution and explanation.  (2017).
  * Holzmann and Anand (2016) Helge Holzmann and Avishek Anand. 2016.  Tempas: Temporal archive search based on tags. In _Proceedings of the 25th International Conference Companion on World Wide Web_. 207–210.
  * Idahl et al. (2021) Maximilian Idahl, Lijun Lyu, Ujwal Gadiraju, and Avishek Anand. 2021.  Towards benchmarking the utility of explanations for model debugging.  _arXiv preprint arXiv:2105.04505_ (2021).
  * Kaushik et al. (2020) Divyansh Kaushik, Eduard Hovy, and Zachary Lipton. 2020\.  Learning The Difference That Makes A Difference With Counterfactually-Augmented Data. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=Sklgs0NFvr
  * Koyama and Yamaguchi (2020) Masanori Koyama and Shoichiro Yamaguchi. 2020.  When is invariance useful in an Out-of-Distribution Generalization problem?  _arXiv preprint arXiv:2008.01883_ (2020).
  * Lertvittayakumjorn and Toni (2021) Piyawat Lertvittayakumjorn and Francesca Toni. 2021.  Explanation-Based Human Debugging of NLP Models: A Survey.  _Transactions of the Association for Computational Linguistics_ 9 (12 2021), 1508–1528.  https://doi.org/10.1162/tacl_a_00440
  * Lester et al. (2021) Brian Lester, Rami Al-Rfou, and Noah Constant. 2021\.  The Power of Scale for Parameter-Efficient Prompt Tuning. In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Online and Punta Cana, Dominican Republic, 3045–3059.  https://doi.org/10.18653/v1/2021.emnlp-main.243
  * Lipton (1990) Peter Lipton. 1990\.  Contrastive Explanation.  _Royal Institute of Philosophy Supplement_ 27 (1990), 247–266.  https://doi.org/10.1017/S1358246100005130
  * Liu et al. (2021) Xiao Liu, Yanan Zheng, Zhengxiao Du, Ming Ding, Yujie Qian, Zhilin Yang, and Jie Tang. 2021.  GPT Understands, Too.  _CoRR_ abs/2103.10385 (2021).  arXiv:2103.10385 https://arxiv.org/abs/2103.10385
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ (2019).
  * Lundberg and Lee (2017) Scott M Lundberg and Su-In Lee. 2017.  A unified approach to interpreting model predictions. In _Proceedings of the 31st international conference on neural information processing systems_. 4768–4777.
  * McDonnell et al. (2016) Tyler McDonnell, Matthew Lease, Mucahid Kutlu, and Tamer Elsayed. 2016.  Why is that relevant? collecting annotator rationales for relevance judgments. In _Proceedings of the AAAI Conference on Human Computation and Crowdsourcing_ , Vol. 4.
  * Miller (2019) Tim Miller. 2019\.  Explanation in artificial intelligence: Insights from the social sciences.  _Artificial Intelligence_ 267 (2019), 1–38.  https://doi.org/10.1016/j.artint.2018.07.007
  * Misra (2019) Vedant Misra. 2019\.  Black box attacks on transformer language models. In _ICLR 2019 Debugging Machine Learning Models Workshop_.
  * Monarch (2021) Robert Munro Monarch. 2021\.  _Human-in-the-Loop Machine Learning: Active learning and annotation for human-centered AI_.  Simon and Schuster.
  * Ribeiro et al. (2016) Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016\.  ”Why Should I Trust You?”: Explaining the Predictions of Any Classifier.  _CoRR_ abs/1602.04938 (2016).  arXiv:1602.04938 http://arxiv.org/abs/1602.04938
  * Ribeiro et al. (2018) Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2018\.  Anchors: High-precision model-agnostic explanations. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 32.
  * Ross et al. (2021) Alexis Ross, Ana Marasović, and Matthew Peters. 2021\.  Explaining NLP Models via Minimal Contrastive Editing (MiCE). In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_. Association for Computational Linguistics, Online, 3840–3852.  https://doi.org/10.18653/v1/2021.findings-acl.336
  * Shin et al. (2020a) Taylor Shin, Yasaman Razeghi, Robert L. Logan IV au2, Eric Wallace, and Sameer Singh. 2020a.  AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts.  arXiv:2010.15980 [cs.CL]
  * Shin et al. (2020b) Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Eric Wallace, and Sameer Singh. 2020b.  AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Online, 4222–4235.  https://doi.org/10.18653/v1/2020.emnlp-main.346
  * Singh and Anand (2018) Jaspreet Singh and Avishek Anand. 2018.  Posthoc Interpretability of Learning to Rank Models using Secondary Training Data.  _arXiv preprint arXiv:1806.11330_ (2018).
  * Singh and Anand (2019) Jaspreet Singh and Avishek Anand. 2019.  EXS: Explainable Search Using Local Model Agnostic Interpretability. In _ACM WSDM_.
  * Singh and Anand (2020) Jaspreet Singh and Avishek Anand. 2020.  Model agnostic interpretability of rankers via intent modelling. In _Conference on Fairness, Accountability, and Transparency_.
  * Singh et al. (2016) Jaspreet Singh, Johannes Hoffart, and Avishek Anand. 2016\.  Discovering entities with just a little help from you. In _Proceedings of the 25th ACM International on Conference on Information and Knowledge Management_. 1331–1340.
  * Singh et al. (2021) Jaspreet Singh, Megha Khosla, Zhenye Wang, and Avishek Anand. 2021.  Extracting per Query Valid Explanations for Blackbox Learning-to-Rank Models. In _ICTIR ’21: The 2021 ACM SIGIR International Conference on the Theory of Information Retrieval, Virtual Event, Canada, July 11, 2021_ , Faegheh Hasibi, Yi Fang, and Akiko Aizawa (Eds.). ACM, 203–210.  https://doi.org/10.1145/3471158.3472241
  * Sundararajan et al. (2017) Mukund Sundararajan, Ankur Taly, and Qiqi Yan. 2017.  Axiomatic Attribution for Deep Networks.  _CoRR_ abs/1703.01365 (2017).  arXiv:1703.01365 http://arxiv.org/abs/1703.01365
  * Wallace et al. (2020) Eric Wallace, Mitchell Stern, and Dawn Song. 2020.  Imitation Attacks and Defenses for Black-box Machine Translation Systems. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Online, 5531–5546.  https://doi.org/10.18653/v1/2020.emnlp-main.446
  * Wu et al. (2021) Tongshuang Wu, Marco Túlio Ribeiro, Jeffrey Heer, and Daniel S. Weld. 2021.  Polyjuice: Automated, General-purpose Counterfactual Generation.  _CoRR_ abs/2101.00288 (2021).  arXiv:2101.00288 https://arxiv.org/abs/2101.00288
  * Zhang et al. (2021a) Zijian Zhang, Koustav Rudra, and Avishek Anand. 2021a.  Explain and Predict, and Then Predict Again. In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ (Virtual Event, Israel) _(WSDM ’21)_. Association for Computing Machinery, New York, NY, USA, 418–426.  https://doi.org/10.1145/3437963.3441758
  * Zhang et al. (2021b) Zijian Zhang, Koustav Rudra, and Avishek Anand. 2021b.  FaxPlainAC: A Fact-Checking Tool Based on EXPLAINable Models with HumAn Correction in the Loop. In _CIKM ’21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 - 5, 2021_ , Gianluca Demartini, Guido Zuccon, J. Shane Culpepper, Zi Huang, and Hanghang Tong (Eds.). ACM, 4823–4827.  https://doi.org/10.1145/3459637.3481985
  * Zheng et al. (2021) Yiming Zheng, Serena Booth, Julie Shah, and Yilun Zhou. 2021\.  The Irrationality of Neural Rationale Models.  _arXiv preprint arXiv:2110.07550_ (2021).


# Circuit Model Reduction with Scaled Relative Graphs

Thomas Chaffey1 Alberto Padoan2 1University of Cambridge, Department of
Engineering, Trumpington Street, Cambridge CB2 1PZ<EMAIL_ADDRESS>Zürich, Department of Information Technology and Electrical Engineering,
Physikstrasse 3, 8092, Zürich, Switzerland<EMAIL_ADDRESS>
###### Abstract

Continued fractions are classical representations of complex objects (for
example, real numbers) as sums and inverses of simpler objects (for example,
integers). The analogy in linear circuit theory is a chain of series/parallel
one-ports: the port behavior is a continued fraction containing the port
behaviors of its elements. Truncating a continued fraction is a classical
method of approximation, which corresponds to deleting the circuit elements
furthest from the port. We apply this idea to chains of series/parallel one-
ports composed of arbitrary nonlinear relations. This gives a model reduction
method which automatically preserves properties such as incremental
positivity. The Scaled Relative Graph (SRG) gives a graphical representation
of the original and truncated port behaviors. The difference of these SRGs
gives a bound on the approximation error, which is shown to be competitive
with existing methods.

##  I Introduction

Continued fractions are classical in the theory of approximation [1], and are
closely related to Padé approximants [2], which have had a broad impact in
areas such as theoretical physics [3], fluid mechanics [4], and control theory
[5, 6, 7, 8]. Continued fractions also have a long and rich history in linear
circuit theory [9]. They have been used extensively for synthesis and
approximation, beginning in the seminal works of Foster [10], Cauer [11],
Bott, Duffin [12], and Kalman [5], among others. The Cauer normal forms for RC
and RL circuits are continued fractions of transfer functions [9], and the
truncation of a continued fraction corresponds to deleting elements from a
series/parallel one-port. The nonlinear counterpart of this fruitful circle of
ideas, however, is largely unexplored. In this context, this paper proposes
the truncation of a “continued fraction” of nonlinear relations as a paradigm
for model reduction of nonlinear series/parallel one-ports.

The aim of model reduction is to approximate a complex model by a simpler one,
whilst retaining the important behavior. In particular, one may require that
properties of the model (such as stability or passivity) are preserved by the
approximation. For linear systems, the literature on the subject is vast, see,
for example, [8] and references therein. In contrast, the problem is largely
open for nonlinear systems. Some progress has been made in [13], [14] and
[15], and in the recent papers [16] and [17], the Lur’e structure is exploited
to reduce a nonlinear model, while preserving incremental dissipativity
properties. A nonlinear system is represented as a linear time invariant (LTI)
state space model in feedback with a static nonlinearity. The LTI component is
then approximated using standard methods, such as balanced truncation and
Hankel norm approximation [8]. Although computationally effective, this
procedure does not leverage the structure of the underlying physical system,
and it is difficult, in general, to guarantee that the approximate system
exhibits desired properties, such as positivity (a close relative of passivity
[18, Lemma 2, p. 200]). In contrast, we propose that a system be modelled from
the very beginning as an interconnection of physical components, and the
system be approximated by deleting the components which are least important.
Properties which are preserved by physical interconnection, such as positivity
[18, $\S 5$, Chap. 6], are then naturally retained in the approximate system.
The choice of electrical terminology is purely a matter of preference:
series/parallel electrical circuits have analogies in domains such as
mechanics, hydraulics and thermodynamics [19, 20].

This paper proposes the Scaled Relative Graph (SRG) as a tool for quantifying
the errors introduced by an approximation. The SRG has recently been
introduced in the theory of convex optimization [21], and allows simple,
graphical proofs of algorithm convergence, and the derivation of tight
convergence bounds [22]. The SRG gives a graphical representation of the
incremental behavior of a nonlinear operator, and generalizes the Nyquist
diagram of an LTI transfer function [23]. Interconnections of operators
correspond to graphical combinations of their SRGs [21], and applying this
graphical algebra to the study of feedback systems gives rise to a nonlinear
Nyquist criterion, which generalizes many existing results on incremental
input/output stability [23, 24]. Properties such as incremental gain and
incremental positivity can be read directly from the SRG, and as such the SRG
may be used to measure the error introduced in such quantities. Plotting an
SRG for the error system, that is, the difference between a system and its
approximation, allows us to bound the incremental gain from input to
approximation error. This bound is shown to compare favourably with other
bounds in the literature.

We begin this paper in Section II with a motivating example, which illustrates
the main ideas. We then define the model class and propose a truncation
procedure in Section III. Section IV introduces the SRG, and how it may be
used to certify approximation error bounds. Equipped with these tools, we
revisit the example circuit in Section V, and compare our method with the
method described in [25]. Section VI concludes the paper with a summary of our
main results, and poses open questions for future research.

##  II A motivating example

The running example of this paper is the circuit illustrated in Figure 1.
$G_{RC}$ is the admittance of an LTI RC filter, and $R$ is an arbitrary
nonlinear resistor $v=R(i)$ which, for all $v_{1},v_{2},i_{1},i_{2}$,
satisfies the incremental sector bound

$\displaystyle\mu\Delta i^{2}\leq\Delta i\Delta v\leq\lambda\Delta i^{2},$ (1)

for some $0\leq\mu\leq\lambda$, where $\Delta i=i_{1}-i_{2}$ and $\Delta
v=v_{1}-v_{2}$.

Figure 1: A nonlinear lattice circuit, configured as a one-port.

The circuit consists of a chain $n$ repeated three element units, and an
additional RC filter at the port. A first attempt at approximating the circuit
might simply be to remove the units furthest from the port. This corresponds
to truncating a “continued fraction” in the circuit elements (to be made
precise in Section III). A better method might be to only remove the
capacitors furthest from the port, and resolve the remaining (linear and
nonlinear) resistors into a single nonlinear resistor. This gives the same
continued fraction truncation, with an additional nonlinear resistance. If $R$
is LTI, one can show that the approximation error is always bounded by the $H$
norm of the original circuit’s transfer function [26]. We generalize this
result to the case where $R$ is nonlinear, using SRGs.

The SRG of a circuit of length $n$ is shown in Figure 2. The value
$\lambda_{n}$ (defined in Section V) bounds the incremental secant gain [27,
$\S$2] of the circuit, and we will show that it also bounds the gain in the
error, $\norm{v-\hat{v}}/\norm{i}$, where $i$ is an input current, $v$ is the
output voltage of the original circuit and $\hat{v}$ is the output voltage of
any circuit with the last $r<n$ capacitors removed.

Figure 2: SRG for the current to voltage relation of the circuit of Figure 1.

##  III Truncating series/parallel one-port circuits

###  III-A Circuit elements as relations

Let $L_{2}$ denote the set of finite energy signals
$u:[0,\infty)\to\mathbb{R}$ such that
${\int_{0}|u^{2}(t)|\mathrm{d}t<\infty.}$ The inner product on $L_{2}$ is
defined by

$\displaystyle\bra{u}\ket{y}\coloneqq\int_{0}u(t)y(t)\mathrm{d}t,$

which induces the norm $\norm{u}\coloneqq\sqrt{\bra{u}\ket{u}}$.

We consider circuits formed by the parallel and series interconnection of one-
port elements. A one-port has two terminals, across which a voltage $v$ is
measured, and through which a current $i$ flows. We assume that these currents
and voltages belong to $L_{2}$, and a one-port $R$ is described by a relation
on $L_{2}$, that is, a set $R\subseteq L_{2}\times L_{2}$ of ordered
voltage/current pairs. If a one-port is described by a relation from voltage
to current, it is an _admittance_ , and if a one-port is described by a
relation from current to voltage, it is an _impedance_. If $(u,y)\in R$, we
write $y\in R(u)$.

The usual operations on functions can be extended to relations:

$\displaystyle S^{-1}$ $\displaystyle=$ $\displaystyle\\{(y,u)\;|\;y\in
S(u)\\}$ $\displaystyle S+R$ $\displaystyle=$
$\displaystyle\\{(x,y+z)\;|\;(x,y)\in S,\;(x,z)\in R\\}$ $\displaystyle SR$
$\displaystyle=$ $\displaystyle\\{(x,z)\;|\;\exists\,y\text{ s.t. }(x,y)\in
R,\;(y,z)\in S\\}.$

The relational inverse always exists, but is not an inverse in the usual sense
– in particular, it is in general not the case that $R^{-1}R=I$. If, however,
$R$ is an invertible function, its functional inverse coincides with its
relational inverse, so the notation $R^{-1}$ is not ambiguous. If $R$ is an
impedance, mapping $i$ to $v$, then $R^{-1}$ is an admittance, mapping $v$ to
$i$.

######  Definition 1.

A relation $R$ on $L_{2}$, mapping $u$ to $y$, is said to be

  1. 1.

incrementally positive (or monotone) if
$\bra{u_{1}-u_{2}}\ket{y_{1}-y_{2}}\geq 0$ for all $u_{1},u_{2},y_{1}\in
R(u_{1}),y_{2}\in R(u_{2})$;

  2. 2.

$\mu$-input strictly incrementally positive (or $\mu$-coercive) if
$\bra{u_{1}-u_{2}}\ket{y_{1}-y_{2}}\geq\mu\norm{u_{1}-u_{2}}^{2}$ for all
$u_{1},u_{2},y_{1}\in R(u_{1}),y_{2}\in R(u_{2})$;

  3. 3.

$1/\gamma$-output strictly incrementally positive (or $1/\gamma$-cocoercive)
if $\gamma\bra{u_{1}-u_{2}}\ket{y_{1}-y_{2}}\geq\norm{y_{1}-y_{2}}^{2}$ for
all $u_{1},u_{2},y_{1}\in R(u_{1}),y_{2}\in R(u_{2})$. $\gamma$ is called the
_incremental secant gain_.

  4. 4.

$R$ is said to have an incremental gain bound (or Lipschitz constant) of
$\lambda$ if $\norm{y_{1}-y_{2}}\leq\lambda\norm{u_{1}-u_{2}}$ for all
$u_{1},u_{2},y_{1}\in R(u_{1}),y_{2}\in R(u_{2})$.

The incremental secant gain of a system is also an incremental gain bound.

Incremental positivity is closely related to incremental passivity – the two
are equivalent for causal operators (this follows from an easy adaptation of
the proof of [18, Lemma 2, p. 200]). Examples of incrementally positive
circuit elements include resistors with nondecreasing $i-v$ characteristics
and LTI capacitors and inductors [28].

###  III-B Series/parallel one-port circuits

A series interconnection of two impedances $R_{1}$ and $R_{2}$ defines a new
one-port impedance, $R_{1}+R_{2}$:

$\displaystyle v\in R_{1}(i)+R_{2}(i).$

Likewise, the parallel interconnection of two admittances $G_{1}$ and $G_{2}$
defines the one-port admittance $G_{1}+G_{2}$:

$\displaystyle i\in G_{1}(v)+G_{2}(v).$

Interconnecting an impedance and an admittance, either in series or in
parallel, requires one of the relations to be inverted. We will assume
throughout this paper that any relations which are added have compatible
domains. For a circuit-theoretic interpretation of this assumption, see [28,
Thm. 2].

These interconnection rules give rise to the class of one-port circuits
consisting of arbitrary series/parallel interconnections, which have the
general form shown in Figure 3 (allowing admittances to be open circuits,
$\\{(v,0)\;|\;v\in\mathbb{R}\\}$, and impedances to be short circuits,
$\\{(i,0)\;|\;i\in\mathbb{R}\\}$).

Figure 3: Circuit structure with nested series and parallel interconnections.
$R_{n}$ represents an impedance, $G_{n}$ represents an admittance.

The $v-i$ relation of this general circuit is given by

$\displaystyle v_{0}$ $\displaystyle=$
$\displaystyle(R_{0}+(G_{0}+(\ldots+(R_{n-1}+R_{n})^{-1}\ldots)^{-1})^{-1})(i_{0}).$

Note that this form generalizes a continued fraction of transfer functions:
when all the elements $R_{j}$ and $G_{j}$ are LTI, taking the Laplace
transform gives

$\displaystyle
v_{0}(s)=R_{0}(s)+\cfrac{1}{G_{0}(s)+\cfrac{1}{\ldots+\cfrac{1}{R_{n-1}(s)+R_{n}(s)}}}\,i_{0}(s).$

When every element is incrementally positive, such circuits are closely
related to the splitting algorithms of monotone operator theory, and may be
solved efficiently using the recently introduced class of _nested splitting
algorithms_ [28].

###  III-C Truncated approximate circuits

Consider the problem of approximating the one-port circuit in Figure 3, whose
port behavior is given by $v_{0}=C(i_{0})$, by a simpler one-port. A natural
solution is to delete the circuit elements furthest from the port terminals,
as they contribute the least to the port behavior of the circuit. This gives a
truncated circuit $\hat{C}$ with $i-v$ relation, defined by

$\displaystyle\hat{v}_{0}=(R_{0}+(G_{0}+(\ldots+(R_{r-1}+R_{r})^{-1}\ldots)^{-1})^{-1})(i_{0}),$

where $r<n$. This procedure corresponds to truncating the continued fraction
of the circuit. The relation from current to voltage has been chosen
arbitrarily, and it is straightforward to verify that the truncation of
$C^{-1}$ is $\hat{C}^{-1}$. We will also consider the case where the final
impedance $R_{r}$ is modified to some $\hat{R}_{r}$ – for example, the lumped
resistance which remains when only capacitors are removed from the circuit in
Figure 1.

In the case that all the circuit elements $R_{j}$, $G_{j}$ are incrementally
positive, both the original and truncated circuits are automatically
incrementally positive – this follows from the preservation of incremental
positivity under series and parallel interconnections [28, Prop. 1]. In the
case that the circuit elements have stronger positivity properties, these are
also preserved in the truncated circuit, as shown in the following
proposition.

######  Proposition 1.

Consider the circuit in Figure 3. Suppose that each admittance $G_{j}$ is
input-strictly incrementally positive, and each impedance $R_{j}$ is output-
strictly incrementally positive. Then the circuit is input-strictly
incrementally positive from voltage to current, and output-strictly
incrementally positive from current to voltage.

###### Proof.

The proof follows from induction, and the following basic results (see, for
example, [29, Chap. 2]). Let $A$ and $B$ be relations on an arbitrary Hilbert
space. Then:

  1. 1.

If $A$ and $B$ are input-strictly incrementally positive, then $A+B$ is input-
strictly incrementally positive.

  2. 2.

If $A$ and $B$ are output-strictly incrementally positive, then $A+B$ is
output-strictly incrementally positive.

  3. 3.

If $A$ is input-strictly incrementally positive, $A^{-1}$ is output-strictly
incrementally positive.

  4. 4.

If $A$ is output-strictly incrementally positive, $A^{-1}$ is input-strictly
incrementally positive.∎

As the series/parallel structure of a circuit is preserved as elements are
removed, Proposition 1 shows that truncation preserves strict incremental
positivity. In the following section, we will develop several numerical
estimates of the accuracy of an approximation, using the circuit’s SRG.

##  IV Graphical truncation errors

We begin this section with a brief overview of the theory of SRGs. For a full
treatment, we refer the reader to [21].

###  IV-A Scaled Relative Graphs

The SRG of an operator is a region in the extended complex plane from which
the dynamic properties of the operator can be easily read. We define the SRG
formally as follows.

The angle between $u,y\in L_{2}$ is defined as

$\displaystyle\angle(u,y)\coloneqq\acos\frac{\bra{u}\ket{y}}{\norm{u}\norm{y}}\in[0,\pi).$

Let $R\subseteq L_{2}\times L_{2}$. Given $u_{1},u_{2}\in L_{2}$, $u_{1}\neq
u_{2}$, we define the set of complex numbers $z_{R}(u_{1},u_{2})$ by

$\displaystyle\left\\{\frac{\norm{y_{1}-y_{2}}}{\norm{u_{1}-u_{2}}}e^{\pm
j\angle(u_{1}-u_{2},y_{1}-y_{2})}\middle|\;y_{1}\in R(u_{1}),y_{2}\in
R(u_{2})\right\\}.$

If $u_{1}=u_{2}$ and there exist corresponding outputs $y_{1}\in
R(u_{1}),y_{2}\in R(u_{2}),y_{1}\neq y_{2}$, then $z_{R}(u_{1},u_{2})$ is
defined to be $\\{\infty\\}$. If $R$ is single valued at $u_{1}$,
$z_{R}(u_{1},u_{1})$ is the empty set.

The _Scaled Relative Graph_ (SRG) of $R$ over $L_{2}$ is then given by

$\displaystyle\operatorname{SRG}_{\,}({R})\coloneqq\tbigcup\slimits@_{u_{1},u_{2}\in\,L_{2}}z_{R}(u_{1},u_{2}).$

######  Proposition 2.

The SRG of a relation belongs to one of the regions illustrated below if and
only if the relation obeys the corresponding input/output property. Clockwise
from top left: finite incremental gain, $1/\gamma$-output strict incremental
positivity, $\mu$-input strict incremental positivity.

###  IV-B SRGs of series/parallel one-ports

Connecting elements in series and parallel involves adding and inverting their
relations. In this section, we describe the corresponding graphical operations
on their SRGs.

If $C,D\subseteq\mathbb{C}$, we define the operation $C+D$ to be the Minkowski
sum of $C$ and $D$, that is,

$\displaystyle C+D\coloneqq\\{c+d\,|\,c\in C,d\in D\\}.$

We define inversion in the extended complex plane by
$re^{j\omega}\mapsto(1/r)e^{j\omega}$. This maps points outside the unit
circle to the inside, and vice versa. The points $0$ and are exchanged under
inversion. The complex conjugate would normally be taken; this is left out for
convenience, and has no effect as the SRG is symmetric about the real axis.

Define the line segment between $z_{1},z_{2}\in\mathbb{C}$ as
$[z_{1},z_{2}]\coloneqq\\{\alpha z_{1}+(1-\alpha)z_{2}\,|\,\alpha\in[0,1]\\}$.
A region $G\subseteq\mathbb{C}$ is said to satisfy the _chord property_ if
$z\in G$ implies $[z,\bar{z}]\subseteq G$. If $A$ is a relation, we denote by
$\overline{\operatorname{SRG}_{\,}({A})}$ any region in $\mathbb{C}$ such that
$\operatorname{SRG}_{\,}({A})\subseteq\overline{\operatorname{SRG}_{\,}({A})}$
and $\overline{\operatorname{SRG}_{\,}({A})}$ satisfies the chord property.

######  Proposition 3.

If $A$ is an operator, then
$\operatorname{SRG}_{\,}({-A})=-\operatorname{SRG}_{\,}({A})$.

######  Proposition 4.

If $A$ is an operator, then
$\operatorname{SRG}_{\,}({A^{-1}})=(\operatorname{SRG}_{\,}({A}))^{-1}$.

######  Proposition 5.

Let $A$ and $B$ be relations whose SRGs are bounded. Then
$\operatorname{SRG}_{\,}({A+B})\subseteq\operatorname{SRG}_{\,}({A})+\overline{\operatorname{SRG}_{\,}({B})}$.

Unbounded SRGs can be allowed by setting
$\operatorname{SRG}_{\,}({A+B})=\\{\infty\\}$ if
$\operatorname{SRG}_{\,}({A})=\varnothing$ and
$\infty\in\operatorname{SRG}_{\,}({B})$.

###  IV-C Graphical truncation errors for series/parallel one-ports

To evaluate the error introduced by truncating a circuit, we can compute a
bounding SRG for the error relation, $C-\hat{C}$, which maps $u$ to
$e\coloneqq y-\hat{y}$. It follows from Proposition 2 that the maximum modulus
of $\operatorname{SRG}_{\,}({C-\hat{C}})$ bounds the incremental error gain,

$\displaystyle\sup_{u_{1},u_{2}\in L_{2},u_{1}\neq
u_{2}}\frac{\norm{e_{1}-e_{2}}}{\norm{u_{1}-u_{2}}}.$

If this quantity is bounded, the error relation is continuous on $L_{2}$:
small changes in the input result in small changes in the error. Under the
assumption that $0\in C(0)$ and $0\in\hat{C}(0)$, the incremental error gain,
in turn, bounds

$\displaystyle\sup_{u\in L_{2},\norm{u}\neq
0}\frac{\norm{y-\hat{y}}}{\norm{u}}.$

If this quantity is bounded, the error relation is bounded on $L_{2}$: bounded
inputs result in bounded errors.

Using the SRGs of the original and truncated circuits, we can furthermore
measure the error in various dynamic properties, such as incremental gain and
positivity. Figure 4, for example, shows how the error in the secant gain can
be measured from the original and truncated SRGs.

Figure 4: Suppose the light grey region bounds the SRG of the original
circuit, and the dark grey region bounds the SRG of the truncated circuit. The
original circuit has a secant gain of $\gamma$, and the truncated circuit has
a secant gain of $\hat{\gamma}$. The error $\gamma-\hat{\gamma}$ in the
truncated secant gain is the distance between the two marked points on the
real axis.

##  V Example revisited

Armed with the graphical tools of the previous section, we revisit the example
of Section II. We begin by deriving an SRG for the circuit in Figure 1, for an
arbitrary number of units $n$. Recall that $R$ is an arbitrary nonlinear
resistor which satisfies the incremental sector bound (1), and suppose the
capacitor and linear resistor both have unit value, $C=G=1$. The SRGs of $R$
and $G_{RC}$ are illustrated below (following [23, Thm. 4, Prop. 9]).

We then apply the SRG sum and inversion rules (Propositions 5 and 4) to obtain
the SRG for the $i-v$ relation of a circuit with $n=1$, shown below
(incidentally, we also obtain an SRG for the $v-i$ relation).

Carrying on with this procedure, we obtain the following SRG for a circuit
with $n$ units.

$\lambda_{n}$ is defined recursively111If $\lambda=1$, $\lambda_{n}\to
1/\phi=2/(1+\sqrt{5})$, the inverse of the golden ratio, as $n\to\infty$. by

$\displaystyle\lambda_{n}$ $\displaystyle=$
$\displaystyle\begin{cases}\frac{1}{1+\frac{1}{\lambda+1}}&n=1\\\
\frac{1}{1+\frac{1}{\lambda+\lambda_{n-1}}}&n>1.\end{cases}$

Repeating this procedure for a circuit $\hat{C}$ with the last $n-r$
capacitors removed produces an identical SRG. We can compute an SRG for the
error relation $C-\hat{C}$ by subtracting $\operatorname{SRG}_{\,}({\hat{C}})$
from $\operatorname{SRG}_{\,}({C})$. This is bounded by the disc illustrated
below.

It follows from Proposition 2 that the error relation, which maps $i\coloneqq
i_{0}$ to $e\coloneqq v_{0}-\hat{v}_{0}$, has an incremental gain bound of
$\lambda_{n}$:

$\displaystyle\sup_{i\in L_{2},\norm{i}\neq
0}\frac{\norm{v_{0}-\hat{v}_{0}}}{\norm{i}}$
$\displaystyle\sup_{i_{1},i_{2}\in L_{2},i_{1}\neq
i_{2}}\frac{\norm{e_{1}-e_{2}}}{\norm{i_{1}-i_{2}}}\leq\lambda_{n}.$

This bound depends only on $\lambda$ and $n$, and approaches a constant as
$n\to\infty$.

Comparing the SRGs of $C$ and $\hat{C}$ shows that both circuits are output-
strictly incrementally passive, with an incremental secant gain of
$\lambda_{n}$.

By way of comparison, applying the balanced truncation method presented in
[25], with $R^{-1}(v)=\tanh(v)+v$, results in a pure truncation of the
continued fraction of the circuit, by removing $n-r$ repeated units, and gives
an error bound

$\displaystyle\sup_{i\in L_{2},\norm{i}\neq
0}\frac{\norm{v_{0}-\hat{v}_{0}}}{\norm{i}}$
$\displaystyle\frac{n-r}{(1-\gamma)^{2}},$

where $\gamma=l\lambda$, and $l$ is the largest eigenvalue of the $n\times n$
matrix

$\displaystyle\begin{pmatrix}-2&1&0&\ldots&0\\\ 1&-2&1&\ldots&0\\\
0&1&-2&\ldots&0\\\ \@vdots&\@vdots&\@vdots&\ddots&\@vdots\\\
0&0&0&\ldots&0\end{pmatrix}.$

Note that the eigenvalue $l$ converges to $4$ as $n\to\infty$. This bound is
tighter than $\lambda_{n}$ for small $n$, but diverges as $n\to\infty$. The
two bounds are plotted in Figure 5.

Figure 5: Maximum modulus of $\operatorname{SRG}_{\,}({C-\hat{C}})$ (orange,
dashed) and the error bound obtained from [25] (blue, dotted). The truncated
circuit has length $r=3$, and $\lambda=2$.

The performance of the two truncations is compared in Figure 6, for an input
of $i_{0}(t)=\sin(t)$, and Figure 7, for an input of $i_{0}(t)=\sin(2t)$. Both
simulations use an initial condition of $1$ V across each capacitor. The
original circuit length is $n=50$, and the truncated circuit length is $r=3$.
For the method we present here, the $n-r$ nonlinear resistors which remain
after the capacitors are removed are approximated by piecewise-linear
functions. The method we present here has lower error in both cases, both in
absolute magnitude and in phase shift.

Figure 6: Top: Time history of the output of the circuit in Figure 1 with
$n=50$ (solid black) and those of the reduced order models of order ${r=3}$
using the method we present here (dashed orange) and the differential balanced
truncation method of [25] (dotted blue). The initial condition is $1$ V across
each capacitor, and the input is $i_{0}(t)=\sin(t)$. Bottom: Time history of
the corresponding output errors in absolute value (logarithmic scale).

Figure 7: The same experiment as Figure 6, with $i_{0}(t)=\sin(2t)$.

In contrast with the balanced truncation method of [25], $R$ can be non-
differentiable and non-invertible (for example, a unit ideal saturation), does
not have to be a function (for example, an ideal diode) and need not be time-
invariant; the element closest to the port can be linear or nonlinear; and the
voltage to current relation is just as easily analysed as the current to
voltage relation.

##  VI Conclusions

This paper explores a simple method for approximating systems which are
modelled as the port behavior of a series/parallel interconnection of
nonlinear relations. Deleting the elements furthest from the port corresponds
to truncating a continued fraction. Resistances can be left in place and
lumped into a single element. This procedure automatically guarantees the
preservation of properties such as incremental positivity (regular, input-
strict and output-strict) and finite incremental gain.

The error introduced by the truncation can be evaluated using the SRGs of the
original and truncated systems. Distances between the two SRGs correspond to
errors in quantities such as the incremental secant gain. Furthermore, an SRG
can be computed for the error relation, and this gives a bound on the
incremental gain from the input to the truncation error.

A natural open question concerns the generality of the series/parallel
structure: when can a system be modelled as a series/parallel one-port? This
is a nonlinear version of one of the earliest questions in circuit theory:
when can a transfer function be realised as the port behavior of an RLC one-
port? This question arose in the work of Foster [10], Cauer [11], and Brune
[30], and a constructive solution was provided by Bott and Duffin [12]. The
Bott-Duffin construction is still the subject of active research [31, 32]. We
leave the equivalent nonlinear construction as a question for future research.

## References

  * [1] W.. Jones and W.. Thron  “Continued fractions: Analytic theory and applications”  Cambridge, U.K.: Cambridge Univ. Press, 1984
  * [2] G.. Baker and P. Graves-Morris  “Padé approximants (2nd edition)”  Cambridge, U.K.: Cambridge Univ. Press, 1996
  * [3] G.. Baker and J.. Gammel  “The Padé approximant in theoretical physics”  New York, NY, USA: Academic Press, 1970
  * [4] Henri Cabannes  “Padé approximants method and its applications to mechanics”  Heidelberg, Germany: Springer-Verlag, 1976
  * [5] R.. Kalman  “On partial realizations, transfer functions and canonical forms”  In _Acta Polytechnica Scandinavica_ 31, 1979, pp. 9–32
  * [6] A. Antoulas  “On recursiveness and related topics in linear systems”  In _IEEE Transactions on Automatic Control_ 31.12, 1986, pp. 1121–1135  DOI: 10.1109/TAC.1986.1104191
  * [7] A. Bultheel and B. De Moor  “Rational approximation in linear systems and control”  In _J. Comp. Appl. Math._ 121.1-2, 2000, pp. 355–378
  * [8] A.. Antoulas  “Approximation of large-scale dynamical systems”  Philadelphia, PA, USA: SIAM, 2005
  * [9] R.. Newcomb  “Linear multiport synthesis”  NEw York, NY, USA: McGraw-Hill, 1966
  * [10] Ronald M. Foster  “A Reactance Theorem”  In _Bell System Technical Journal_ 3.2, 1924, pp. 259–267  DOI: 10.1002/j.1538-7305.1924.tb01358.x
  * [11] Wilhelm Cauer  “Die Verwirklichung von Wechselstromwiderständen Vorgeschriebener Frequenzabhängigkeit”  In _Archiv für Elektrotechnik_ 17.4, 1926, pp. 355–388  DOI: 10.1007/BF01662000
  * [12] R. Bott and R.. Duffin  “Impedance Synthesis without Use of Transformers”  In _Journal of Applied Physics_ 20.8, 1949, pp. 816–816  DOI: 10.1063/1.1698532
  * [13] Jacqueline Maria Aleida Scherpen  “Balancing for nonlinear systems”  In _Systems & Control Letters_ 21.2 Elsevier, 1993, pp. 143–153
  * [14] Alessandro Astolfi  “Model reduction by moment matching for linear and nonlinear systems”  In _IEEE Transactions on Automatic Control_ 55.10 IEEE, 2010, pp. 2321–2336
  * [15] A. Padoan  “Model reduction by least squares moment matching for linear and nonlinear systems” under review  In _IEEE Transactions on Automatic Control_ , 2021
  * [16] Bart Besselink, Nathan Wouw and Henk Nijmeijer  “Model reduction for nonlinear systems with incremental gain or passivity properties”  In _Automatica_ 49.4 Elsevier, 2013, pp. 861–872
  * [17] A. Padoan, F. Forni and R. Sepulchre  “Model reduction of dominant feedback systems”  In _Automatica_ 130.109695, 2021, pp. 1–8  DOI: 10.1016/j.automatica.2021.109695
  * [18] Charles A. Desoer and Mathukumalli Vidyasagar  “Feedback Systems: Input–Output Properties”  Elsevier, 1975  DOI: 10.1016/b978-0-12-212050-3.x5001-4
  * [19] M.. Smith  “Synthesis of Mechanical Networks: The Inerter”  In _IEEE Transactions on Automatic Control_ 47.10, 2002, pp. 1648–1662  DOI: 10.1109/tac.2002.803532
  * [20] Arjan Schaft and Dimitri Jeltsema  “Port-Hamiltonian Systems Theory: An Introductory Overview”  In _Foundations and Trends in Systems and Control_ 1.2-3, 2014, pp. 173–378  DOI: 10.1561/2600000002
  * [21] Ernest K. Ryu, Robert Hannah and Wotao Yin  “Scaled Relative Graphs: Nonexpansive Operators via 2D Euclidean Geometry”  In _Mathematical Programming_ , 2021  DOI: 10.1007/s10107-021-01639-w
  * [22] Xinmeng Huang, Ernest K. Ryu and Wotao Yin  “Tight Coefficients of Averaged Operators via Scaled Relative Graph”, 2020  arXiv:1912.01593 [math]
  * [23] Thomas Chaffey, Fulvio Forni and Rodolphe Sepulchre  “Graphical Nonlinear System Analysis”, 2021  arXiv:2107.11272 [cs, eess, math]
  * [24] Thomas Chaffey  “A Rolled-off Passivity Theorem”  In _Systems & Control Letters_ 162, 2022, pp. 105198  DOI: 10.1016/j.sysconle.2022.105198
  * [25] Bart Besselink, Nathan Wouw, Jacquelien M.. Scherpen and Henk Nijmeijer  “Model Reduction for Nonlinear Systems by Incremental Balanced Truncation”  In _IEEE Transactions on Automatic Control_ 59.10, 2014, pp. 2739–2753  DOI: 10.1109/TAC.2014.2326548
  * [26] B. Srinivasan and P. Myszkorowski  “Model Reduction of Systems with Zeros Interlacing the Poles”  In _Systems & Control Letters_ 30.1, 1997, pp. 19–24  DOI: 10.1016/S0167-6911(96)00072-2
  * [27] Eduardo D. Sontag  “Passivity Gains and the “Secant Condition” for Stability”  In _Systems & Control Letters_ 55.3, 2006, pp. 177–183  DOI: 10.1016/j.sysconle.2005.06.010
  * [28] Thomas Chaffey and Rodolphe Sepulchre  “Monotone One-Port Circuits”, 2021  arXiv:2111.15407 [cs, eess, math]
  * [29] Ernest K. Ryu and Wotao Yin  “Large-Scale Convex Optimization via Monotone Operators”, 2022
  * [30] Otto Brune  “Synthesis of a Finite Two-Terminal Network Whose Driving-Point Impedance Is a Prescribed Function of Frequency”, 1931
  * [31] Timothy H. Hughes and Malcolm C. Smith  “On the Minimality and Uniqueness of the Bott–Duffin Realization Procedure”  In _IEEE Transactions on Automatic Control_ 59.7, 2014, pp. 1858–1873  DOI: 10.1109/TAC.2014.2312471
  * [32] Timothy H. Hughes  “Why RLC Realizations of Certain Impedances Need Many More Energy Storage Elements Than Expected”  In _IEEE Transactions on Automatic Control_ 62.9, 2017, pp. 4333–4346  DOI: 10.1109/TAC.2017.2667585