# Contextuality and inductive bias in quantum machine learning

Joseph Bowles<EMAIL_ADDRESS>Xanadu, Toronto, ON, M5G 2C8, Canada Victoria J
Wright  ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of
Science and Technology, 08860 Castelldefels, Spain  Máté Farkas  ICFO-Institut
de Ciencies Fotoniques, The Barcelona Institute of Science and Technology,
08860 Castelldefels, Spain
Nathan Killoran  Xanadu, Toronto, ON, M5G 2C8, Canada Maria Schuld  Xanadu,
Toronto, ON, M5G 2C8, Canada

###### Abstract

Generalisation in machine learning often relies on the ability to encode
structures present in data into an inductive bias of the model class. To
understand the power of quantum machine learning, it is therefore crucial to
identify the types of data structures that lend themselves naturally to
quantum models. In this work we look to quantum contextuality—a form of
nonclassicality with links to computational advantage—for answers to this
question. We introduce a framework for studying contextuality in machine
learning, which leads us to a definition of what it means for a learning model
to be contextual. From this, we connect a central concept of contextuality,
called operational equivalence, to the ability of a model to encode a linearly
conserved quantity in its label space. A consequence of this connection is
that contextuality is tied to expressivity: contextual model classes that
encode the inductive bias are generally more expressive than their
noncontextual counterparts. To demonstrate this, we construct an explicit toy
learning problem—based on learning the payoff behaviour of a zero-sum game—for
which this is the case. By leveraging tools from geometric quantum machine
learning, we then describe how to construct quantum learning models with the
associated inductive bias, and show through our toy problem that they
outperform their corresponding classical surrogate models. This suggests that
understanding learning problems of this form may lead to useful insights about
the power of quantum machine learning.

##  1 Introduction

In order for a learning model to generalise well from training data, it is
often crucial to encode some knowledge about the structure of the data into
the model itself [1, 2, 3]. Convolutional neural networks [4, 5, 6] are a
classic illustration of this principle, whose success at image related tasks
is often credited to the existence of model structures that relate to label
invariance of the data under translation symmetries [7]. Together with the
choice of loss function and hyperparameters, these structures form part of the
basic assumptions that a learning model makes about the data, which is
commonly referred to as the _inductive bias_ of the model.

One of the central challenges facing quantum machine learning is to identify
data structures that can be encoded usefully into quantum learning models; in
other words, what are the forms of inductive bias that naturally lend
themselves to quantum computation [8, 9, 10, 11]? In answering this question,
we should be wary of hoping for a one-size-fits-all approach in which quantum
models outperform neural network models at generic learning tasks. Rather,
effort should be placed in understanding how the Hilbert space structure and
probabilistic nature of the theory suggest particular biases for which quantum
machine learning may excel. Indeed, an analogous perspective is commonplace in
quantum computation, where computational advantages are expected only for
specific problems that happen to benefit from the peculiarities of quantum
logic.

In the absence of large quantum computers and in the infancy of quantum
machine learning theory, how should we look for insight on this issue? One
possibility is to turn to complexity theory [12, 13], where asymptotic
advantages of quantum learning algorithms have been proven [14, 15, 16, 17].
These results are few and far between however, and the enormous gap between
what is possible to prove in a complexity-theoretic sense, and the types of
advantages that may be possible in practice, means that there are growing
doubts about the practical relevance of these results. Indeed, progress in
machine learning is often the result of good ideas built on intuition, rather
than worst-case complexity theoretic analysis. To repeat a common quip: many
problems in machine learning are NP-hard, but neural networks don’t know that
so they solve them anyway.

We will take a different route, and lean on the field of quantum foundations
to guide us. Quantum foundations is predominantly concerned with understanding
the frontier between the quantum and classical world, and typically values a
clear qualitative understanding of a phenomenon over purely mathematical
knowledge. For these reasons it is well suited to identify features of quantum
theory that may advance quantum machine learning in useful directions. In
particular, we focus on the phenomenon of contextuality [18, 19, 20], which is
perhaps the most prominent form of nonclassicality studied in the literature.
Contextuality has a considerable tradition of being studied in relation to
quantum computation [21, 22, 23, 24, 25, 26, 27], where it is closely
connected to the possibility of computational speed-up. Despite this, it has
had relatively little attention in quantum machine learning, with only a
couple of works [28, 29] linking contextuality to implications for learning.

Figure 1: A. An example of the type of learning problem we consider in this
work. Labels are generated for input training data $\boldsymbol{x}_{i}$ via a
conditional process $P(\boldsymbol{y}_{i}|\boldsymbol{x}_{i})$. Here, the
labels take the form
$\boldsymbol{y}_{i}=(y_{i}^{(1)},y_{i}^{(2)},y_{i}^{(3)})=(\pm 1,\pm 1,\pm
1)$. The learning problem is to infer three probabilistic models
$\mathcal{P}_{1}(y^{(1)}|\boldsymbol{x})$,
$\mathcal{P}_{2}(y^{(2)}|\boldsymbol{x})$,
$\mathcal{P}_{3}(y^{(3)}|\boldsymbol{x})$ that sample the individual labels
for unseen input data. B. The data is assumed to satisfy a particular bias,
which can be seen as a linear conservation law on the label space. Here, the
sum of the expectation values of the labels is equal to zero for all $x$. We
show that if a model encodes this as an inductive bias and is noncontextual,
this implies constraints on the distributions $\mathcal{P}_{k}$, amounting to
a limit on expressivity of model classes that are restricted to only
noncontextual learning models.

We adopt a notion of contextuality called _generalised contextuality_ [20],
introduced by Spekkens in 2004. Loosely speaking, it refers to the fact that
(i) there are different experimental procedures (called contexts) in the
theory that are indistinguishable111For example, one can prepare a maximally
mixed stated of a qubit by mixing states in the $z$ or $x$ basis; both
procedures result in the same density matrix and are therefore
indistinguishable., and (ii) any statistical model that reproduces the
predictions of the theory must take these contexts into account. With this
choice, our first task will then be to introduce a framework to talk about
generalised contextuality in machine learning (Section 2). This was missing in
previous works [28, 29], which prove consequences for learning based on
phenomena originating from contextuality, but do not attempt to define a
notion of contextuality for machine learning that captures a wide range of
models. Our general philosophy will be that the framework should depend purely
on what a learning model can do, and not on the details of how it does it;
i.e., the framework should be independent of the theory on which the models
are built. This is necessary to have a framework that treats quantum and
classical algorithms on the same footing, and ultimately involves adopting
definitions in a similar spirit to the notion of operational contextuality as
recently described in [30].

We mostly focus on a paradigm of machine learning called multi-task learning
[31, 32], in which the aim is to simultaneously learn a number of separate
models for a collection of different (but typically correlated) tasks. Multi-
task learning scenarios are conceptually similar to commonly studied
contextuality scenarios, and this similarity leads us to a definition of what
it means for a multi-task model to be contextual (Section 3). Although the
focus on multi-class learning problems appears restrictive, as the separation
between tasks is arbitrary at the mathematical level, we also arrive at a
notion of contextuality in the single task setting (Section 6). In particular,
we argue that it makes sense to think of contextuality as a property relative
to a particular inductive bias of a model, rather than a property of the model
as a whole.

Once we have described our framework, our second task will be to identify
specific learning problems for which contextuality plays a role (Section 4).
We show that this is the case when learning probabilistic models from data
sets which feature a linearly conserved quantity in a discrete label space
(see Figure 1). Such data sets can arise naturally from experiments involving
conserved quantities, zero-sum game scenarios [33, 34], logistics with
conserved resources, substance diffusion [35, 36, 37] in biological systems,
and human mobility [38] and migration [39]. We show that the ability of a
model to encode the conserved quantity as an inductive bias directly links to
a central concept in generalised contextuality, called _operational
equivalence_. This results in a constraint on noncontextual learning models
that encode the desired bias, which amounts to a limit on the expressivity of
noncontextual model classes. For certain data sets, this limitation can
negatively impact generalisation performance due to the lack of a suitable
model within the class that matches the underlying data distribution; in such
cases contextuality may therefore be required for learning. To illustrate this
point, in Section 5 we construct a toy problem based on the rock, paper,
scissors zero-sum game and prove precise limits on the expressivity of
noncontextual model classes that attempt to learn the payoff behaviour of the
game.

In the final part of the work, we study the performance of quantum models for
problems that involve our contextuality-inspired bias (Section 7). We first
describe two approaches to construct quantum ansätze encoding the bias. The
first of these encodes the bias into the state structure of the ansatz, and
exploits tools from geometric quantum machine learning [40, 41, 42]. The
second approach encodes the bias into the measurement structure, and we
present a new family of measurements to this end that may be of independent
interest. We then use these tools in a simple numerical investigation (Section
8), inspired by a recent work of Schreiber et al. [11]. Using the fact that
quantum machine learning models are equivalent to truncated Fourier series
[43, 44], the authors of [11] define the notion of a classical surrogate
model: a linear Fourier features model that has access to the same frequencies
of the quantum model, but which lacks its specific inductive bias. The authors
found that classical surrogate model classes perform better than quantum model
classes on a wide range of regression tasks, the message being that it is
still unclear what the inductive bias of quantum machine learning is useful
for. In our numerical study, we show that a quantum model class that encodes
our contextuality-inspired bias achieves a lower generalisation error than the
corresponding surrogate model classes at a specific learning task, even after
allowing for regularisation in the surrogate model. We argue that this is due
to the fact that the bias cannot be easily encoded into the surrogate model
class, which therefore cannot exploit this information during learning.

In Section 9 we elaborate on a number of areas where contextuality-inspired
inductive bias can be expected to play a role in learning. Many of these areas
are classical in nature, and therefore suggests that quantum machine learning
may be suited to tackling classical learning problems with a specific
structure. Finally, in Section 10, we outline our vision for this line of
research and the possible next steps to take. Overall, we hope our approach
and framework will lead to a new way of thinking about quantum machine
learning, and ultimately lead to the identification of impactful problems
where the specific structure of quantum theory makes quantum models the
machine learning models of choice.

###### Contents

  1. 1 Introduction
  2. 2 Generalised contextuality
    1. 2.1 Procedures, preparations and effects
    2. 2.2 Operational statistics
    3. 2.3 Convex mixtures
    4. 2.4 Operational equivalences
    5. 2.5 Ontological models
    6. 2.6 Generalised noncontextuality of ontological models
  3. 3 Contextuality of multi-task machine learning models
  4. 4 Inductive bias and limits of expressivity
    1. 4.1 Summary of main result
    2. 4.2 Linking inductive bias to operational equivalence
    3. 4.3 Bounding noncontextual learning models
  5. 5 Learning the rock, paper, scissors game
    1. 5.1 The game
    2. 5.2 The data set
    3. 5.3 The learning problem
  6. 6 Contextuality of general learning models
    1. 6.1 Connecting multi-task and single-task models
    2. 6.2 Contextuality relative to a bias
  7. 7 Encoding inductive bias into quantum learning models
    1. 7.1 State-based approach
    2. 7.2 Measurement-based approach
    3. 7.3 Nonlinear biases
  8. 8 Outperforming classical surrogates
    1. 8.1 The learning problem
    2. 8.2 The quantum model class
    3. 8.3 Classical surrogates of quantum models
    4. 8.4 Training and evaluation
    5. 8.5 Results
  9. 9 Avenues for contextuality-inspired inductive bias
    1. 9.1 Zero-sum games with larger payoff dimension
    2. 9.2 Conserved substances in networks
    3. 9.3 Quantum control under a conserved quantity
    4. 9.4 Possible extensions to our framework
  10. 10 Outlook
  11. 11 Acknowledgements
  12. A The problem with using the physical theory as an operational scenario
  13. B Proof of Theorem 4.1 for $\eta=1$
  14. C Example of a model without preparation equivalences
  15. D Higher dimensional measurements satisfying the zero-sum bias condition
  16. E Details of the unbiased quantum model
  17. F Data generation and training details

##  2 Generalised contextuality

In this section we lay the theoretical groundwork that will lead us to a
definition of contextuality for learning models. Some readers may wish to read
section 4.1 first, which presents an overview of our main theoretical results,
and can be understood without precise knowledge of the definitions presented
here or in Section 3.

To define contextuality in machine learning we must first decide on a
framework of contextuality, since there exist inequivalent frameworks in the
literature. We have chosen to adopt that of _generalised contextuality_ [20],
which from hereon we will often often refer to as simply ‘contextuality’. This
is a modern version of contextuality that is commonly adopted in current
foundations research [45, 46, 47, 48]. Like the more orthodox notion of
Kochen-Specker contextuality [49], generalised contextuality has also been
connected to speedup in quantum computation [schmid2022uniqueness, 27], where
it has been shown to be necessary for computational advantage. It is also
based on a single, simple principle (described in section 2.6) that subsumes
older notions of contextuality such as Kochen-Specker contextuality [49], as
well as Bell nonlocality [50]. For this reason it is particularly attractive
from a theoretical perspective.

Following our philosophy that contextuality for machine learning should
reflect what the learning model does, rather than how it does it222For
example, our notion of contextuality should not differentiate between a
quantum model and a classical simulation of the same model, since the two are
computationally equivalent from the perspective of the user. This perspective
is normal in computation; for example, the concept of run-time is ignorant of
the underlying theory., this will lead us to a definition that is inline with
the concept of operational contextuality that was recently defined by Gitton
and Woods [30]. For this reason we will follow quite closely the notation and
language of [30], and we encourage motivated readers to read the associated
sections of that article, which give a more detailed introduction to
generalised contextuality than we attempt here. In order to tailor the
discussion to the machine learning audience, we introduce contextuality based
on a user interacting with a machine learning model, however we remark that
the framework of contextuality extends beyond this to general experimental
scenarios.

###  2.1 Procedures, preparations and effects

The simplest and most commonly studied scenario of contextuality is the
prepare-and-measure scenario (see Figure 2A). For our purposes, we imagine a
user with access to a machine learning model, who can prepare the model in a
specific state by inputting data into it. In contextuality, this is called a
_preparation_ , denoted $\textbf{S}\in\texttt{Preps}$ (the letter S is used
since a preparation can be thought of as a state), and is described via a
_procedure_ , denoted $L$. A procedure is simply a list of actions describing
in words what the user does, e.g., ‘input the data point $\boldsymbol{x}$ into
the model’. We also assume that the user can query the model for different
tasks and observe the corresponding predictions. These events are described by
_effects_ in contextuality. An effect, denoted
$\textbf{E}=\omega|L\in\texttt{Effects}$ is a procedure $L$ together with a
specific observation $\omega\in W_{L}$ that signals success, where $W_{L}$ is
the set of all observations that may follow $L$. For example ‘query the model
for task 1’ (procedure) and ‘observe the label +1’ (observation). An effect
can therefore be thought of as a binary yes/no question related to a specific
procedure333Whereas preparations can be thought of as the analogue of quantum
states, effects can be thought of as the analogue of measurement operators..

Note that at this level of description we have not specified anything about
how the model works (it could be quantum or classical for example), and are
concerned only with descriptions of the actions and observations of the user
that interacts with it. For this reason, this approach is often called an
_operational_ approach; hence the common appearance of the term ‘operational’
in the proceeding sections.

Figure 2: A. (top) A prepare-and-measure scenario. A preparation S is a
procedure (a list of actions) that a user carries out. In this example, the
procedure is to input the data $\boldsymbol{x}$ into the machine learning
model. (bottom) An effect E is another procedure that additionally has an
observation that signals success of the procedure. Here, the procedure is to
query the model with some task (labelled $k$) and success corresponds to a
particular label being returned. B. An ontological model is a particular
causal model to explain the statistics of a prepare-and-measure scenario. The
preparation results in some probabilistic mixture $\mu_{\textbf{S}}(\lambda)$
over a set of ontic states $\lambda$. The effect is a function
$\xi_{\textbf{E}}(\lambda)$ that returns the probability of the successful
outcome given the ontic state $\lambda$. For us, $\lambda$ can be thought of a
specific memory state of the learning model, and $\xi_{\textbf{E}}(\lambda)$ a
function that gives the probability of the learning model returning a specific
label for some task.

###  2.2 Operational statistics

For every $\textbf{S}\in\texttt{Preps}$ and every
$\textbf{E}\in\texttt{Effects}$, we assume there is a corresponding
probability $P(\textbf{E}|\textbf{S})$ that describes the likelihood of the
successful outcome of E given S, and we call the set of all
$P(\textbf{E}|\textbf{S})$ the _operational statistics_. In our case,
$P(\textbf{E}|\textbf{S})$ is simply the probability to observe a particular
label for some task (given by E) conditioned on certain data being input into
the model (given by $\textbf{S})$. In addition to the effects that correspond
to the possible predictions of the model, we also include the trivial effect
$\Omega$ that always occurs for any preparation,

$\displaystyle
P(\Omega|\textbf{S})=1\quad\forall\,\textbf{S}\in\texttt{Preps},$ (1)

and the null effect $\emptyset$ that never occurs,

$\displaystyle
P(\emptyset|\textbf{S})=0\quad\forall\,\textbf{S}\in\texttt{Preps}.$ (2)

Operationally speaking, these effects correspond to the user simply ignoring
the model and declaring either a successful or failed observation. We
naturally assume that probabilities of effects corresponding to two mutually
incompatible observations are additive. For example, if $\textbf{E}_{0\lor
1}=0\lor 1|L$ is an effect corresponding to observing a label prediction $0$
or $1$ and $\textbf{E}_{0}=0|L$ and $\textbf{E}_{1}=1|L$ are those for labels
$0$ and $1$ independently, then

$\displaystyle P(\textbf{E}_{0\lor
1}|\textbf{S})=P(\textbf{E}_{0}|\textbf{S})+P(\textbf{E}_{1}|\textbf{S}).$ (3)

With this, we can now define a measurement

$\displaystyle\textbf{M}=\\{\textbf{E}_{1},\textbf{E}_{2},\cdots,\textbf{E}_{d}\\}$
(4)

to be a collection of effects corresponding to the same procedure
$L_{\textbf{M}}$ with mutually incompatible observations $\omega_{i}$ whose
probabilities sum to 1:

$\displaystyle\textbf{E}_{i}=\omega_{i}|L_{\textbf{M}},\quad\sum_{i}P(\textbf{E}_{i}|\textbf{S})=1\quad\forall\,\textbf{S}\in\texttt{Preps}.$
(5)

we call the triple
$\\{\texttt{Preps},\texttt{Effects},P(\textbf{E}|\textbf{S})\\}$ of possible
preparations, effects and operational statistics, an _operational scenario_
444This is analogous to the concept of ‘operational theory’ encountered in the
generalized contextuality literature; here we use the word ‘scenario’ instead
since we are not concerned with an entire physical theory..

###  2.3 Convex mixtures

A key ingredient of generalised contextuality is the ability to perform convex
mixtures; i.e., the user is assumed to have access to a trusted source of
randomness that they can use to probabilistically mix procedures. For example,
given two preparations $\textbf{S}_{1}$ and $\textbf{S}_{2}$ with procedures
$L_{1}$ and $L_{2}$, the user may flip a biased coin (with bias $p$) and
perform either $L_{1}$ or $L_{2}$. We call the resulting preparation a
_preparation density_ , written

$\displaystyle s=p\textbf{S}_{1}+(1-p)\textbf{S}_{2},$ (6)

which results in a corresponding mixture of operational statistics,

$\displaystyle
P(\textbf{E}|p\textbf{S}_{1}+(1-p)\textbf{S}_{2})=pP(\textbf{E}|\textbf{S}_{1})+(1-p)P(\textbf{E}|\textbf{S}_{2})\quad\forall\textbf{E}\in\texttt{Effects}.$
(7)

Similarly given two effects $\textbf{E}_{1}=\omega_{1}|L_{1}$ and
$\textbf{E}_{2}=\omega_{2}|L_{2}$, the user can flip a biased coin and realise
the _effect density_

$\displaystyle e=p\textbf{E}_{1}+(1-p)\textbf{E}_{2},$ (8)

such that

$\displaystyle
P(p\textbf{E}_{1}+(1-p)\textbf{E}_{2}|\textbf{S})=pP(\textbf{E}_{1}|\textbf{S})+(1-p)P(\textbf{E}_{2}|\textbf{S})\quad\forall\textbf{S}\in\texttt{Preps}.$
(9)

By allowing arbitrary probabilistic mixtures of preparations and effects, we
can therefore prepare any preparation density
$s\in\text{conv}(\texttt{Preps})$ and any effect density
$e\in\text{conv}(\texttt{Effects})$, where conv denotes the convex hull of a
set.

###  2.4 Operational equivalences

At the heart of generalised contextuality is the notion of operational
equivalence, which relates to the possibility of distinguishing between pairs
of preparation or effect densities. We say that two preparation densities
$s_{1},s_{2}$ are _operationally equivalent_ , denoted $\sim$, iff they give
identical predictions for all effects,

$\displaystyle s_{1}\sim s_{2}\iff
P(\textbf{E}|s_{1})=P(\textbf{E}|s_{2})\quad\forall\,\textbf{E}\in\texttt{Effects}.$
(10)

Similarly, two effect densities $e_{1},e_{2}$ are operationally equivalent iff
they have the same probability of success for all preparations,

$\displaystyle e_{1}\sim e_{2}\iff
P(e_{1}|\textbf{S})=P(e_{2}|\textbf{S})\quad\forall\,\textbf{S}\in\texttt{Preps}.$
(11)

Thus, a pair of preparations or effects are operationally equivalent if and
only if they are indistinguishable with respect to any of the possible
procedures and observations in the operational scenario.

###  2.5 Ontological models

An ontological model is a specific causal model (see Figure 2B) to describe
the operational statistics of an operational scenario. In an ontological
model, each preparation S is assigned a probability density function
$\mu_{\textbf{S}}(\lambda)$ called an _ontic state distribution_ over a set of
so-called _ontic states_ 555One could also call these hidden variables.
$\lambda\in\Lambda$. The idea here is that the set $\Lambda$ of ontic states
represents the set of all possible accessible physical states in some
underlying theory. Returning to our machine learning motivation, we can think
of $\lambda$ as being a specific memory state of the learning model and
$\Lambda$ the set of all such memory states. For example, if the model is a
neural network then $\lambda$ denotes the physical memory state of the
computer on which it is stored. $\mu_{\textbf{S}}(\lambda)$ is therefore the
probability distribution over memory states induced by some data preparation
S.

The probability of an effect given some preparation is causally mediated
through the variable $\lambda$. Each effect E is assigned a function
$\xi_{\textbf{E}}(\lambda):\Lambda\rightarrow[0,1]$ called an _ontic response
function_ that returns the probability of E given $\lambda$. In a machine
learning setting $\xi_{\textbf{E}}(\lambda)$ typically corresponds to the
probability of returning a particular label for some task given the memory
state $\lambda$. From the law of total probability we therefore have

$\displaystyle
P(\textbf{E}|\textbf{S})=\int_{\Lambda}\text{d}\lambda\,\mu_{\textbf{S}}(\lambda)\xi_{\textbf{E}}(\lambda).$
(12)

Ontic state distributions and ontic response functions for preparation and
effect densities are defined using the same additivity relations as (7), (9),

$\displaystyle\mu_{p\textbf{S}_{1}+(1-p)\textbf{S}_{2}}(\lambda)=p\mu_{\textbf{S}_{1}}(\lambda)+(1-p)\mu_{\textbf{S}_{2}}(\lambda),\quad\xi_{p\textbf{E}_{1}+(1-p)\textbf{E}_{2}}(\lambda)=p\xi_{\textbf{E}_{1}}(\lambda)+(1-p)\xi_{\textbf{E}_{2}}(\lambda).$
(13)

An _ontological model_ of an operational scenario is defined by a triple
$\\{\Lambda,\\{\mu_{\textbf{S}}(\lambda)\\},\\{\xi_{\textbf{E}}(\lambda)\\}\\}$
of ontic states, ontic state distributions and ontic response functions that
reproduce the operational statistics via (12).

###  2.6 Generalised noncontextuality of ontological models

Generalised noncontextuality is a constraint, called _ontological equivalence_
, that is imposed on ontological models. Within a given ontological model of
some operational scenario, we say that two preparation densities $s_{1}$ and
$s_{2}$ are ontologically equivalent if

$\displaystyle\mu_{s_{1}}(\lambda)=\mu_{s_{2}}(\lambda)\quad\forall\,\lambda,$
(14)

i.e., they result in the same probability density over ontic states.
Similarly, two effect densities $e_{1}$ and $e_{2}$ are ontologically
equivalent if they have the same ontic response function:

$\displaystyle\xi_{e_{1}}(\lambda)=\xi_{e_{2}}(\lambda)\quad\forall\,\lambda.$
(15)

Generalised noncontextuality can now be understood as the following principle,
which is often motivated by Leibniz’s principle of the identity of
indiscernibles [51]:

operational equivalence $\iff$ ontological equivalence,

or equivalently

$\displaystyle s_{1}\sim s_{2}$
$\displaystyle\iff\mu_{s_{1}}(\lambda)=\mu_{s_{2}}(\lambda)\quad\forall\,\lambda,$
(16) $\displaystyle e_{1}\sim e_{2}$
$\displaystyle\iff\xi_{e_{1}}(\lambda)=\xi_{e_{2}}(\lambda)\quad\forall\,\lambda.$
(17)

In other words, _if two preparation of effect densities are indistinguishable,
then they should be described in the same way in the ontological model_. At
this point it can be useful to make a link to Kochen-Specker noncontextuality
for those that are familiar. In Kochen-Specker noncontextuality, one assigns
the same deterministic response function to projectors that appear in
different measurement contexts. This follows from an application of (16) and
(17), where the projector that appears in two different measurements is
understood as two distinct but operationally equivalent effects, and the
determinism of the response functions is a consequence of preparation
noncontextuality [52]. As we will see however, there are other operational
equivalences that are not of this form. As a result, the framework is
applicable to scenarios beyond the Kochen-Specker setting; hence the name
_generalised_ contextuality.

A noncontextual ontological model of an operational scenario can now be
defined as follows.  A noncontextual ontological model of an operational
scenario $\\{\texttt{Preps},\texttt{Effects},P(\textbf{E}|\textbf{S})\\}$ is a
triple
$\displaystyle\\{\Lambda,\mu_{\textbf{S}}(\lambda),\xi_{\textbf{E}}(\lambda)\\}$
(18) of ontic states, ontic state distributions and ontic response functions
satisfying the constraints (16) and (17) such that $\displaystyle
P(\textbf{E}|\textbf{S})=\int_{\Lambda}\text{d}\lambda\,\mu_{\textbf{S}}(\lambda)\xi_{\textbf{E}}(\lambda)\quad\forall\textbf{S}\in\texttt{Preps},\;\forall\textbf{E}\in\texttt{Effects}.$
(19) In prepare-and-measure scenarios where operational equivalences exist,
the constraints (16) and (17) limit the set of operational statistics that
admit a noncontextual ontological model to a subset of all possible
statistics. If the operational statistics lie outside of this set, they are
therefore called _contextual_.

##  3 Contextuality of multi-task machine learning models

We now have all the necessary ingredients we need to define a notion of
contextuality for machine learning. As in the previous section, we consider a
scenario that involves a user with access to a learning model, who can input
data $\boldsymbol{x}$ into the model and observe predictions $y$ for $m$
different tasks. A learning model in this scenario is therefore a device that
samples from one of the $m$ conditional probability distributions
$\mathcal{P}_{\theta}^{1}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(y|\boldsymbol{x}),\cdots,\mathcal{P}_{\theta}^{m}(y|\boldsymbol{x})$,
and we denote the model by

$\displaystyle
h(\theta)=\\{\mathcal{P}_{\theta}^{1}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(y|\boldsymbol{x}),\cdots,\mathcal{P}_{\theta}^{m}(y|\boldsymbol{x})\\}.$
(20)

Here, $\theta$ denotes some specific fixed parameters of the associated model
class $H$,

$\displaystyle
H=\\{h(\theta)\\}_{\theta}=\\{\\{\mathcal{P}_{\theta}^{1}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(y|\boldsymbol{x}),\cdots,\mathcal{P}_{\theta}^{m}(y|\boldsymbol{x})\\}\\}_{\theta},$
(21)

which are chosen according to some data-dependent figure-of-merit, such as
empirical risk minimisation.

Since the model $h(\theta)$ is capable of inference for a number of different
tasks, we call it a _multi-task model_ , and $H$ a _multi-task model class_.
Multi-task models are an active area of machine learning research [31, 32],
and in well-aligned tasks, can lead to improved performance and lower data
size requirements than an approach in which models are learned independently.
In this section we focus on multi-task models to define our notion of
contextuality. The reason for this is that this paradigm most naturally fits
the existing contextuality literature, where the relevant scenarios involve a
choice of measurements that we map to separate tasks. However, since what
defines a task is rather ambiguous (i.e. a group of tasks could be thought of
as a single task), this leads to a notion of contextuality of learning models
in the single task setting as well. Since this is quite a subtle point that
will benefit from understanding the multi-task case, we defer the discussion
and the corresponding definition for single-task models until Section 6.

We now imagine a user interacting with a trained multi-task model $h(\theta)$.
Our definition of contextuality will apply to $h(\theta)$ rather than be a
property of the entire model class $H$. The reason for this is that we aim to
connect contextuality to the behaviour of the model at inference time, which
is the job of a single trained multi-task model, rather than the entire
class666That is not to say that definitions of contextuality that take into
account the full model class are not interesting, however the interpretation
would be somewhat different.. With this choice we may now define the
corresponding operational scenario in which to study contextuality. Following
the logic of Section 2, this consists of all the actions and observations
related to a user interacting with the model $h(\theta)$ at inference time.

An operational scenario of a multi-task model is a triple
$\\{\texttt{Preps},\texttt{Effects},P(\textbf{E}|\textbf{S})\\}$. The set
Preps consists of preparations $\textbf{S}_{\boldsymbol{x}}$, where
$\textbf{S}_{\boldsymbol{x}}$ corresponds to a procedure whereby a user inputs
data $\boldsymbol{x}$ into the memory of the model. The set Effects consists
of the effects $\textbf{E}^{k}_{y}$, $\Omega$, $\emptyset$, where
$\textbf{E}^{k}_{y}$ corresponds to a procedure whereby the user queries the
model for task $k$ and observes the label $y$, and $\Omega$ and $\emptyset$
are the trivial and null effects respectively. The operational statistics are
given by the model predictions
$P(\textbf{E}^{k}_{y}|\textbf{S}_{\boldsymbol{x}})=\mathcal{P}_{\theta}^{k}(y|\boldsymbol{x})$.

This choice of operational scenario then leads to a natural definition of
noncontextuality for multi-task models.  A multi-task model $\displaystyle
h(\theta)=\\{\mathcal{P}_{\theta}^{1}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(y|\boldsymbol{x}),\cdots,\mathcal{P}_{\theta}^{m}(y|\boldsymbol{x})\\}$
(22) is noncontextual iff the operational statistics
$P(\textbf{E}|\textbf{S})$ of the associated operational scenario (given by
Definition 3) admits a noncontextual ontological model. If such an ontological
model does not exist, the learning model is said to be contextual. With this
definition, we now define a noncontextual model class to be any class that
contains only noncontextual multi-task models.

A multi-task model class $\displaystyle
H=\\{\\{\mathcal{P}_{\theta}^{1}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(y|\boldsymbol{x}),\cdots,\mathcal{P}_{\theta}^{m}(y|\boldsymbol{x})\\}\\}_{\theta}$
(23) is noncontextual if every multi-task model in the class is noncontextual
in the sense of Definition 3.

We remark that the theory-independent approach we have taken above is
different to the common perspective of generalised contextuality, where the
operational scenario corresponds to the entire underlying physical theory. In
Appendix A we expand on this point and explain why our approach is necessary
to arrive at a reasonable definition of contextuality for machine learning.

##  4 Inductive bias and limits of expressivity

In this section we present our main theoretical insights by connecting the
concept of inductive bias in machine learning to generalised contextuality. We
use upper case Roman characters to denote random variables and lower case to
denote fixed values of that variable, i.e., $P(a|x)\equiv P(A=a|X=x)$.
Superscript in parentheses refers to a particular element of a vector, i.e.,
$\boldsymbol{x}^{(k)}$ is the $k^{\text{th}}$ element of $\boldsymbol{x}$.

###  4.1 Summary of main result

We first give a summary of our main result, leading to Theorem 4.1. We focus
on a class of learning problems with the following form (see also Figure 1).

Consider a data set
$\displaystyle\chi=\\{\boldsymbol{x}_{i},\boldsymbol{y}_{i}\\}$ (24) of input
data points $\boldsymbol{x}_{i}\in\mathbb{R}^{d}$ and labels
$\boldsymbol{y}_{i}\in\\{-1,1\\}^{m}$ sampled from a data distribution
$\mathcal{D}(\boldsymbol{x},\boldsymbol{y})$ that satisfies a linear
constraint
$\displaystyle\mathbb{E}[Y^{(1)}|\boldsymbol{x}]+\mathbb{E}[Y^{(2)}|\boldsymbol{x}]+\cdots+\mathbb{E}[Y^{(m)}|\boldsymbol{x}]=0\quad\forall\boldsymbol{x},$
(25) where $Y^{(k)}$ is the random variable corresponding to the
$k^{\text{th}}$ element of $\boldsymbol{y}$. Construct a multi-task model
$\displaystyle
h(\theta)=\\{\mathcal{P}_{\theta}^{1}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(y|\boldsymbol{x}),\cdots,\mathcal{P}_{\theta}^{m}(y|\boldsymbol{x})\\}$
(26) that samples from the $m$ marginal conditional distributions
$\mathcal{D}(y^{(k)}|\boldsymbol{x})$ $(k=1,\cdots,m)$ for unseen instances of
$\boldsymbol{x}$.

Figure 3: A. If a multi-task model encodes the bias (28), the behaviours
$\boldsymbol{v}_{\boldsymbol{x}}=(\mathcal{P}_{\theta}^{1}(+1|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(+1|\boldsymbol{x}),\mathcal{P}_{\theta}^{3}(+1|\boldsymbol{x}))$
must lie in the yellow hexagon formed by the convex hull of six extremal
points. The orange space denotes the convex hull of $V$, the set of possible
behaviours for some specific multi-task model. If this space lies outside of
the dashed inner hexagon (described in Theorem 4.1), the multi-task model is
necessarily contextual in the sense of Definition 3. B. The crosses mark the
ground truth behaviours of inputs from a test data set. Since the convex hull
of the set of behaviours of a noncontextual model (orange space) cannot
contain the inner hexagon, any such model will be unable to sample the correct
label distribution for all inputs in the test set. In this case, the
noncontextual model will fail to approximately sample the correct label
distributions for those test points with behaviours far from the orange space.

The constraint (25) can be seen as a statistical conservation law on the label
space: for any $\boldsymbol{x}$ the sum of their expectation values is equal
to a constant. As we will see in section 4.2, noncontextual model classes that
encode biases of this form have limited expressivity, which may impact
learning from certain data sets. This is due to the inductive bias acting as
an operational equivalence (Section 2.4) in the contextuality scenario, which
amounts to a constraint on every model in the class through the principle of
generalised contextuality (Section 2.6).

To illustrate how this works in practice, we study the particular case of
Problem 4.1 for $m=3$. Consider a data set $\chi$ as described in problem 4.1,
and a multi-task model class $H$. We assume that the model class encodes the
bias (25) that is present in the data, so that (25) holds for each multi-task
model $h(\theta)$ in $H$. Translating the expectation values
$\mathbb{E}[Y^{(k)}|\boldsymbol{x}]=\mathcal{P}_{\theta}^{k}(+1|\boldsymbol{x})-\mathcal{P}_{\theta}^{k}(-1|\boldsymbol{x})$
into probabilities, this implies

$\displaystyle\mathcal{P}_{\theta}^{1}(+1|\boldsymbol{x})+\mathcal{P}_{\theta}^{2}(+1|\boldsymbol{x})+\mathcal{P}_{\theta}^{3}(+1|\boldsymbol{x})=\mathcal{P}_{\theta}^{1}(-1|\boldsymbol{x})+\mathcal{P}_{\theta}^{2}(-1|\boldsymbol{x})+\mathcal{P}_{\theta}^{3}(-1|\boldsymbol{x})\quad\forall\,\theta\;\forall\,\boldsymbol{x},$
(27)

or using
$\mathcal{P}_{\theta}^{k}(+1|\boldsymbol{x})=1-\mathcal{P}_{\theta}^{k}(-1|\boldsymbol{x})$,

$\displaystyle\mathcal{P}_{\theta}^{1}(+1|\boldsymbol{x})+\mathcal{P}_{\theta}^{2}(+1|\boldsymbol{x})+\mathcal{P}_{\theta}^{3}(+1|\boldsymbol{x})=\frac{3}{2}\quad\forall\theta\;\forall\,\boldsymbol{x}.$
(28)

In order to describe how the bias (28) leads to constraints on noncontextual
models, we now give a geometric interpretation to each multi-task model in the
class. Consider a specific multi-task model (with fixed parameters $\theta$)
and define the vector

$\displaystyle\boldsymbol{v}_{\boldsymbol{x}}=(\mathcal{P}_{\theta}^{1}(+1|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(+1|\boldsymbol{x}),\mathcal{P}_{\theta}^{3}(+1|\boldsymbol{x})).$
(29)

We call $\boldsymbol{v}_{\boldsymbol{x}}$ a _behaviour_ for input
$\boldsymbol{x}$. Since
$\mathcal{P}_{\theta}^{k}(-1|\boldsymbol{x})=1-\mathcal{P}_{\theta}^{k}(+1|\boldsymbol{x})$,
the set of possible behaviours that can be produced by the model is

$\displaystyle
V=\\{\boldsymbol{v}_{\boldsymbol{x}}|\boldsymbol{v}_{\boldsymbol{x}}\in
D_{\boldsymbol{x}}\\},$ (30)

where $D_{x}$ is the domain of the input data. Since each probability in
$\boldsymbol{v}_{\boldsymbol{x}}$ is bounded in $[0,1]$, the set $V$ generally
forms a three-dimensional subspace of the cube. The bias (28) however is a
linear constraint that restricts $V$ to live in a to a two-dimensional hexagon
that is the convex hull of the six extremal behaviours (see Figure 3A)

$\displaystyle\boldsymbol{v}_{1}=(1,0,\scalebox{0.9}{$\frac{1}{2}$}),\quad\boldsymbol{v}_{2}=(0,1,\scalebox{0.9}{$\frac{1}{2}$}),\quad\boldsymbol{v}_{3}=(\scalebox{0.9}{$\frac{1}{2}$},1,0),\quad\boldsymbol{v}_{4}=(\scalebox{0.9}{$\frac{1}{2}$},0,1),\quad\boldsymbol{v}_{5}=(0,\scalebox{0.9}{$\frac{1}{2}$},1),\quad\boldsymbol{v}_{6}=(1,\scalebox{0.9}{$\frac{1}{2}$},0).\quad$
(31)

In Figure 3A, the orange space shows the convex hull of $V$ for such a model.
We now consider another space $V_{\eta}$ that is the convex hull of the six
behaviours

$\displaystyle\boldsymbol{u}_{i}(\eta)=\eta\boldsymbol{v}_{i}+(1-\eta)(\scalebox{0.9}{$\frac{1}{2}$},\scalebox{0.9}{$\frac{1}{2}$},\scalebox{0.9}{$\frac{1}{2}$})\quad
i=1,\cdots,6$ (32)

where $0<\eta<1$. This space also forms a (smaller) hexagon, which for
$\eta=\frac{2}{3}$ is shown by the dashed lines in Figure 3A. As we will show
shortly, if the set $V_{2/3}$ is strictly contained in the convex hull of $V$,
then the corresponding multi-task model is necessarily contextual. This is
made precise by the following theorem.

Consider a multi-task model
$\\{\mathcal{P}_{\theta}^{1}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{3}(y|\boldsymbol{x})\\}$
that encodes the bias (28). If the set $V_{2/3}$ given by the convex hull of
points
$\displaystyle\boldsymbol{u}_{i}(\eta)=\eta\boldsymbol{v}_{i}+(1-\eta)(\scalebox{0.9}{$\frac{1}{2}$},\scalebox{0.9}{$\frac{1}{2}$},\scalebox{0.9}{$\frac{1}{2}$})\quad
i=1,\cdots,6$ (33) for $\eta=\frac{2}{3}$ is strictly contained the convex
hull of $\displaystyle V=\\{\boldsymbol{v}_{\boldsymbol{x}}|\boldsymbol{x}\in
D_{\boldsymbol{x}}\\}=\\{(\mathcal{P}_{\theta}^{1}(+1|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(+1|\boldsymbol{x}),\mathcal{P}_{\theta}^{3}(+1|\boldsymbol{x}))|\boldsymbol{x}\in
D_{\boldsymbol{x}}\\}$ (34) then the multi-task model is contextual in the
sense of Definition 3.

Phrased in the contra-positive, this implies that if a multi-task model
encodes the bias (28) and is noncontextual, the convex hull of possible
behaviours cannot contain $V_{2/3}$. This amounts to a limit on the
expressivity of noncontextual multi-task model classes, since each model in
the class is subject to this restriction. For certain data sets this may
impact the generalisation ability of the model class (see Figure 3B). For
example, consider a test data set that contains a significant fraction of
inputs $\boldsymbol{x}_{i}$ whose ground truth behaviours are sufficiently
close to the six points $\boldsymbol{v}_{i}$. Then since the set of behaviours
of any noncontextual model cannot contain $V_{2/3}$, all models in the class
will struggle to approximately sample the correct label distributions on some
of the inputs, which may hinder generalisation ability.

###  4.2 Linking inductive bias to operational equivalence

In this subsection and the next we prove Theorem 4.1. To do this we will
connect the inductive bias of the model to the notion of operational
equivalence of generalised contextuality. Our first task is to identify the
relevant operational scenario. Following Definition 3, the set Preps contains
the preparations $\textbf{S}_{\boldsymbol{x}}$ that correspond to inputting a
data point $\boldsymbol{x}\in D_{x}$ into the model. The set Effects contains
the trivial effect $\Omega$, null effect $\emptyset$, and the six effects
$\textbf{E}_{\pm}^{1}$, $\textbf{E}_{\pm}^{2}$, $\textbf{E}_{\pm}^{3}$, which
correspond to observing the label $y=\pm 1$ for the three tasks. The
operational statistics are simply the model predictions

$\displaystyle
P(\textbf{E}^{k}_{y}|\textbf{S}_{\boldsymbol{x}})=\mathcal{P}_{\theta}^{k}(y|\boldsymbol{x})\quad
k=1,2,3.$ (35)

An operational equivalence connected to the bias (28) can be found as follows.
Imagine we choose one of the tasks uniformly at random and observe the label
of that task. In the operational scenario this is described by a measurement

$\displaystyle\textbf{M}=\\{e_{+},e_{-}\\}=\\{\frac{1}{3}\textbf{E}^{1}_{+}+\frac{1}{3}\textbf{E}^{2}_{+}+\frac{1}{3}\textbf{E}^{3}_{+},\frac{1}{3}\textbf{E}^{1}_{-}+\frac{1}{3}\textbf{E}^{2}_{-}+\frac{1}{3}\textbf{E}^{3}_{-}\\}.$
(36)

Let us look at the probability of obtaining the first outcome of this
measurement when performed on some preparation $\textbf{S}_{\boldsymbol{x}}$.
Since the bias is satisfied, it follows from (28) that

$\displaystyle P(e_{+}|\textbf{S}_{\boldsymbol{x}})$
$\displaystyle=\frac{1}{3}(P(\textbf{E}^{1}_{+}|\textbf{S}_{\boldsymbol{x}})+P(\textbf{E}^{2}_{+}|\textbf{S}_{\boldsymbol{x}})+P(\textbf{E}^{3}_{+}|\textbf{S}_{\boldsymbol{x}}))$
$\displaystyle=\frac{1}{3}(\mathcal{P}_{\theta}^{1}(+1|\boldsymbol{x})+\mathcal{P}_{\theta}^{2}(+1|\boldsymbol{x})+\mathcal{P}_{\theta}^{3}(+1|\boldsymbol{x}))=\frac{1}{2}\quad\forall\;\textbf{S}_{\boldsymbol{x}}.$
(37)

Similarly, the probability of the second outcome is

$\displaystyle P(e_{-}|\textbf{S}_{\boldsymbol{x}})$
$\displaystyle=\frac{1}{3}(P(\textbf{E}^{1}_{-}|\textbf{S}_{\boldsymbol{x}})+P(\textbf{E}^{2}_{-}|\textbf{S}_{\boldsymbol{x}})+P(\textbf{E}^{3}_{-}|\textbf{S}_{\boldsymbol{x}}))$
$\displaystyle=\frac{1}{3}(\mathcal{P}_{\theta}^{1}(-1|\boldsymbol{x})+\mathcal{P}_{\theta}^{2}(-1|\boldsymbol{x})+\mathcal{P}_{\theta}^{3}(-1|\boldsymbol{x}))$
$\displaystyle=1-\frac{1}{3}(\mathcal{P}_{\theta}^{1}(+1|\boldsymbol{x})+\mathcal{P}_{\theta}^{2}(+1|\boldsymbol{x})+\mathcal{P}_{\theta}^{3}(+1|\boldsymbol{x}))=\frac{1}{2}\quad\forall\;\textbf{S}_{\boldsymbol{x}}.$
(38)

This means that if we chose a task at random, we are equally likely to observe
a positive or negative label. The two effect densities $e_{+}$ and $e_{-}$ in
this measurement are therefore operationally equivalent777One could use the
operational equivalence
$\frac{1}{3}\textbf{E}^{1}_{+}+\frac{1}{3}\textbf{E}^{2}_{+}+\frac{1}{3}\textbf{E}^{3}_{+}\sim\frac{1}{2}\Omega+\frac{1}{2}\emptyset$
here instead to the same effect.,

$\displaystyle\frac{1}{3}\textbf{E}^{1}_{+}+\frac{1}{3}\textbf{E}^{2}_{+}+\frac{1}{3}\textbf{E}^{3}_{+}\sim\frac{1}{3}\textbf{E}^{1}_{-}+\frac{1}{3}\textbf{E}^{2}_{-}+\frac{1}{3}\textbf{E}^{3}_{-}.$
(39)

An operational equivalence related to the preparations can be found as
follows. Since the set $V_{2/3}$ is strictly contained in the convex hull of
$V$, it follows that the convex hull of $V$ contains the six points
$\boldsymbol{u}_{i}(\eta)$ for some $\eta>\frac{2}{3}$. We therefore have

$\displaystyle\boldsymbol{u}_{i}(\eta)=(P(\textbf{E}_{+}^{1}|s_{i}),P(\textbf{E}_{+}^{2}|s_{i}),P(\textbf{E}_{+}^{3}|s_{i}))\quad
i=1,\cdots,6$ (40)

for some preparation densities $s_{1},\cdots,s_{6}$. Note that we also have

$\displaystyle\frac{1}{2}(\boldsymbol{u}_{1}(\eta)+\boldsymbol{u}_{2}(\eta))=\frac{1}{2}(\boldsymbol{u}_{3}(\eta)+\boldsymbol{u}_{4}(\eta))=\frac{1}{2}(\boldsymbol{u}_{5}(\eta)+\boldsymbol{u}_{6}(\eta))=(\frac{1}{2},\frac{1}{2},\frac{1}{2}).$
(41)

It follows from (9) that

$\displaystyle(P(\textbf{E}_{+}^{1}|\scalebox{0.9}{$\frac{1}{2}$}s_{i}+\scalebox{0.9}{$\frac{1}{2}$}s_{i+1}),P(\textbf{E}_{+}^{2}|\scalebox{0.9}{$\frac{1}{2}$}s_{i}+\scalebox{0.9}{$\frac{1}{2}$}s_{i+1}),P(\textbf{E}_{+}^{3}|\scalebox{0.9}{$\frac{1}{2}$}s_{i}+\scalebox{0.9}{$\frac{1}{2}$}s_{i+1}))=(\frac{1}{2},\frac{1}{2},\frac{1}{2})$
(42)

for $i=1,3,5$. From this we can conclude that equally mixing any of the pairs
of preparation densities $(s_{1},s_{2})$, $(s_{3},s_{4})$, or $(s_{5},s_{6})$
results in another preparation density that returns uniformly random labels
for the three tasks. These mixtures are therefore indistinguishable and we
have the operational equivalences

$\displaystyle\frac{1}{2}s_{1}+\frac{1}{2}s_{2}\sim\frac{1}{2}s_{3}+\frac{1}{2}s_{4}\sim\frac{1}{2}s_{5}+\frac{1}{2}s_{6}.$
(43)

###  4.3 Bounding noncontextual learning models

Assuming noncontextuality, we now derive constraints on the operational
statistics via the operational equivalences (39) and (43), leading to the
result of Theorem 4.1. To do this, we use the following lemma.

Consider an operational scenario of a multi-task model for Problem 4.1 with
$m=3$, that satisfies the operational equivalences (39) and (43). If the
multi-task model is noncontextual, then the operational statistics satisfy the
inequality $\displaystyle
P(\textbf{E}_{+}^{1}|s_{1})+P(\textbf{E}_{+}^{2}|s_{3})+P(\textbf{E}_{+}^{3}|s_{5})\leq\frac{5}{2},$
(44)

Consider a noncontextual ontological model of the operational scenario. This
consists of ontic state distributions $\mu_{s}(\lambda)$ for every preparation
density $s$ and ontic response functions $\xi_{e}(\lambda)$ for every effect
density $e$. The effect densities are convex mixtures of the eight effects
$\textbf{E}^{1}_{+},\textbf{E}^{2}_{+},\textbf{E}^{3}_{+},\textbf{E}^{1}_{-},\textbf{E}^{2}_{-},\textbf{E}^{3}_{-},\Omega,\emptyset$.
We define the vectors

$\displaystyle\boldsymbol{\xi}(\lambda)=(\xi_{\textbf{E}^{1}_{+}}(\lambda),\xi_{\textbf{E}^{2}_{+}}(\lambda),\xi_{\textbf{E}^{3}_{+}}(\lambda),\xi_{\textbf{E}^{1}_{-}}(\lambda),\xi_{\textbf{E}^{2}_{-}}(\lambda),\xi_{\textbf{E}^{3}_{-}}(\lambda),\xi_{\Omega}(\lambda),\xi_{\emptyset}(\lambda))$
(45)

for each $\lambda$. These vectors are constrained as follows. From the
properties of the trivial and null effect we have $\xi_{\Omega}(\lambda)=1$
and $\xi_{\emptyset}(\lambda)=0$ for all $\lambda$. We also have the
positivity constraints $0\leq\xi_{\textbf{E}^{k}_{\pm}}(\lambda)\leq 1$ and
constraints stemming from the normalisation conditions
$\xi_{\textbf{E}^{k}_{+}}(\lambda)+\xi_{\textbf{E}^{k}_{-}}(\lambda)=1$ for
all $\lambda$. Finally, due to noncontextuality, the operational equivalence
(39) implies the constraints

$\displaystyle\xi_{\textbf{E}^{1}_{+}}(\lambda)+\xi_{\textbf{E}^{2}_{+}}(\lambda)+\xi_{\textbf{E}^{3}_{+}}(\lambda)=\xi_{\textbf{E}^{1}_{-}}(\lambda)+\xi_{\textbf{E}^{2}_{-}}(\lambda)+\xi_{\textbf{E}^{3}_{-}}(\lambda)\quad\forall\lambda.$
(46)

Combining these constraints we find that the vectors
$\boldsymbol{\xi}(\lambda)$ can be characterised by the two-dimensional
hexagon in Fig. 4. Each point in the polygon gives the values
$\xi_{\textbf{E}^{1}_{+}}(\lambda)$ and $\xi_{\textbf{E}^{2}_{+}}(\lambda)$
with the other entries of $\boldsymbol{\xi}(\lambda)$ following from Eq. (46)
and the normalisation conditions.

Figure 4: The six extremal vectors $\boldsymbol{\xi}_{i}$ can be characterised
by the first two values, $\xi_{\textbf{E}_{+}^{1}}(\lambda)$ and
$\xi_{\textbf{E}_{+}^{2}}(\lambda)$ in (45).

We therefore have

$\displaystyle\boldsymbol{\xi}(\lambda)=\sum_{i=1}^{6}p_{\lambda}(i)\boldsymbol{\xi}^{i}$
(47)

where $p_{\lambda}(i)$ is a probability distribution for each $\lambda$.
Denoting by $\xi^{i}_{\textbf{E}}$ the element of $\boldsymbol{\xi}^{i}$
corresponding to the effect E, the operational statistics for preparation
density $s$ and effect E predicted by the ontological model are

$\displaystyle
P(\textbf{E}|s)=\int_{\Lambda}\text{d}\lambda\mu_{s}(\lambda)\sum_{i}p_{\lambda}(i)\xi^{i}_{\textbf{E}}$
$\displaystyle=\sum_{i}\left(\int_{\Lambda}\text{d}\lambda\mu_{s}(\lambda)p_{\lambda}(i)\right)\xi^{i}_{\textbf{E}}$
$\displaystyle=:\sum_{i}\nu_{s}(i)\;\xi^{i}_{\textbf{E}},$ (48)

Where we have defined
$\nu_{s}(i):=\int_{\Lambda}\text{d}\lambda\mu_{s}(\lambda)p_{\lambda}(i)$.
Note that we have

$\displaystyle\sum_{i}\nu_{s}(i)=1,\quad\nu_{s}(i)\geq 0,$ (49)

and by noncontextuality and the operational equivalence (43),

$\displaystyle\nu_{1}(i)+\nu_{2}(i)=\nu_{3}(i)+\nu_{4}(i)=\nu_{5}(i)+\nu_{6}(i),$
(50)

where $\nu_{j}=\nu_{s_{j}}$. A decomposition (48) satisfying (49) and (50) is
necessary and sufficient for the existence of a noncontextual ontological
model, since the decomposition (48) can itself be seen as such a model by
viewing the index $i$ as an ontic state. Together, (48), (49) and (50)
therefore give us a characterisation of the set of possible noncontextual
statistics for the preparation densities $s_{j}$ $(j=1,\cdots,6)$ that
consists of linear equalities and inequalities in the finite set of variables
$\nu_{j}(i)$. From these, it follows that the inequality (44) is satisfied by
the operational statistics of any multi-task learning model. This can be
proven via linear quantifier elimination methods as in [53]; the list of all
such inequalities for this set of operational equivalences can be found in
[53, 54]. Here we give a pen-and-paper proof of the inequality, which may
itself be of interest to the contextuality community.

First, using the notation $\nu_{s_{i}}\equiv\nu_{i}$ and using (48), (49), we
express the left hand side of the inequality (44) in terms of the variables
$\nu_{j}$, which gives

$\displaystyle\sum_{j=2,3}\nu_{1}(j)-\nu_{5}(j)+\sum_{k=1,6}\nu_{3}(k)-\nu_{5}(k)$
$\displaystyle\quad\quad\quad+\frac{1}{2}\left[\nu_{1}(1)+\nu_{1}(4)+\nu_{3}(2)+\nu_{3}(5)-\sum_{l=1,2,4,5}\nu_{5}(l)\right]+\frac{3}{2}.$
(51)

Using the normalisation and non-negativity constraints we can upper bound the
following three quantities in the square brackets as follows:

$\displaystyle\nu_{1}(1)+\nu_{1}(4)\leq 1-\nu_{1}(2)-\nu_{1}(3),$ (52)
$\displaystyle\nu_{3}(2)+\nu_{3}(5)\leq 1-\nu_{3}(1)-\nu_{3}(6),\quad\text{
and}$ (53) $\displaystyle-$
$\displaystyle\sum_{l=1,2,4,5}\nu_{5}(l)\leq-\sum_{l=4,5}\nu_{5}(l)=\sum_{l=1,2,3,6}\nu_{5}(l)-1.$
(54)

Rearranging, we obtain the following upper bound for the expression in (4.3):

$\displaystyle\frac{1}{2}+\frac{1}{2}\left[\nu_{3}(1)+\nu_{1}(2)+\nu_{1}(3)+\nu_{3}(6)-\sum_{j=1,2,3,6}\nu_{5}(j)\right]+\frac{3}{2}.$
(55)

From the operational equivalences (50) and non-negativity we have

$\displaystyle\sum_{j=1,2,3,6}\nu_{5}(j)+\nu_{6}(j)=$
$\displaystyle\nu_{3}(1)+\nu_{4}(1)+\nu_{1}(2)+\nu_{2}(2)+\nu_{1}(3)+\nu_{2}(3)+\nu_{3}(6)+\nu_{4}(6)$
(56) $\displaystyle\geq$
$\displaystyle\nu_{3}(1)+\nu_{1}(2)+\nu_{1}(3)+\nu_{3}(6).$ (57)

It follows that

$\displaystyle
1\geq\sum_{j=1,2,3,6}\nu_{6}(j)\geq\nu_{3}(1)+\nu_{1}(2)+\nu_{1}(3)+\nu_{3}(6)-\sum_{j=1,2,3,6}\nu_{5}(j).$
(58)

Using this in (55) we obtain the bound $\frac{5}{2}$, which proves the
inequality (44).

We now consider a multi-task model described in Theorem 4.1. From (40) and the
definition of $\boldsymbol{u}_{i}(\eta)$ one finds that the left hand side of
the inequality (44) is

$\displaystyle 3\eta+\frac{3}{2}(1-\eta)=\frac{3}{2}(\eta+1).$ (59)

This results in a violation of the inequality for $\eta>\frac{2}{3}$, implying
contextuality of the learning model and therefore proving the claim of Theorem
4.1. We note that (44) more constraints on the model that are not covered by
Theorem 4.1 or the inequality (44) can be found in [53, 54]. The advantage of
the phrasing of Theorem 4.1 however is that it can be understood easily via
the geometric perspective of Figure 3. We also present a proof for the zero-
noise case ($\eta=1$) in Appendix B. Although less general, this proof may be
useful to gain more intuition on the limitations of noncontextual models.

##  5 Learning the rock, paper, scissors game

We now introduce a specific toy data set and learning problem—based on
learning the payoff behaviour of a zero-sum game—to which Theorem 4.1 applies.
Aside from bringing life to Theorem 4.1, this problem will also be the subject
of the numerical investigation of section 8.

###  5.1 The game

The data set is based on the well known rock, paper, scissors (RPS) game. Our
game features three players that play a variant of the RPS game via a referee
(Figure 5A). In every round, each player plays either rock ($\mathtt{R}$),
paper ($\mathtt{P}$) or scissors ($\mathtt{S}$), and we denote the choice of
actions of the three players by the vector
$\boldsymbol{a}\in\\{\mathtt{R},\mathtt{P},\mathtt{S}\\}^{3}$. Each player
also has a special action whose role we will describe shortly. For Player 1,
the special action is $\mathtt{R}$, for Player 2 it is $\mathtt{P}$ and for
Player 3 it is $\mathtt{S}$. Following the actions, each player either
receives receives €1 or must pay €1 to the referee, which we refer to as their
pay-off, and denote the three payoffs as $\boldsymbol{y}=(\pm 1,\pm 1,\pm 1)$.
The payoffs are decided probabilistically based on the actions of the players.
More precisely, the payoff of Player $k$ is such that

$\displaystyle\mathbb{E}[Y^{(k)}]=\frac{\ell_{k}(\boldsymbol{a})}{2},$ (60)

where $\ell_{k}(\boldsymbol{a})\in\\{-2,-1,0,1,2\\}$ is equal to the number of
players that Player $k$ beat in that round minus the number of players that
beat Player $k$. This rule ensures that if a player beats (or loses to) all
others, they are sure to win (or lose) the round.

The rules for who beats whom are as follows. If two players choose different
actions, the rule is the well-known rule:

$\displaystyle\mathtt{R}_{k}>\mathtt{S}_{l},\quad\mathtt{P}_{k}>\mathtt{R}_{l},\quad\mathtt{S}_{k}>\mathtt{P}_{l}\quad\forall\;k,l,$
(61)

where $\mathtt{R}_{k}>\mathtt{S}_{l}$ means “Player $k$ plays rock beats
Player $l$ plays scissors”. If two players play the same action, one player
beats the other if the common action is their special action. For example, if
players 1 and 2 both play $\mathtt{R}$, then Player 1 beats Player 2 since
$\mathtt{R}$ is Player 1’s special action. These rules can be summarised as

$\displaystyle\mathtt{R}_{1}>\mathtt{R}_{k},\;\;k=2,3\quad\quad\mathtt{P}_{2}>\mathtt{P}_{k},\;\;k=1,3\quad\quad\mathtt{S}_{3}>\mathtt{S}_{k},\;\;k=1,2.$
(62)

In any other case it is a draw. Note that this game satisfies a zero-sum
condition. Mathematically, since we must have
$\sum_{k}\ell_{k}(\boldsymbol{a})=0$ it follows from (60) that

$\displaystyle\mathbb{E}[Y^{1}|\boldsymbol{a}]+\mathbb{E}[Y^{2}|\boldsymbol{a}]+\mathbb{E}[Y^{3}|\boldsymbol{a}]=0.$
(63)

Figure 5: Three players play a variant of the rock, paper, scissors game with
a referee. The referee determines (probabilistically) whether each player wins
or loses the round based on their choice of action.

###  5.2 The data set

In the zero-sum game literature, it is common to introduce the concept of a
_strategy_. A strategy $\boldsymbol{x}(k)$ for Player $k$ is simply a list of
probabilities that the player performs each possible action,

$\displaystyle\boldsymbol{x}(k)=(P(A^{(k)}=\texttt{R}),P(A^{(k)}=\texttt{P}),P(A^{(k)}=\texttt{S})).$
(64)

We denote by $\boldsymbol{x}\in D_{\boldsymbol{x}}$ the $3\times 3$ matrix
whose $k^{\text{th}}$ row is $\boldsymbol{x}(k)$, where $D_{\boldsymbol{x}}$
is the space of valid strategy matrices, i.e. positive-valued matrices whose
rows sum to $1$. Some of these strategies correspond to the six extremal
behaviours in Figure 3. Consider for example the strategy

$\displaystyle\boldsymbol{x}=\begin{pmatrix}1&0&0\\\ 0&0&1\\\
0&0&1\end{pmatrix},$ (65)

i.e. a deterministic strategy where Player 1 plays R and Player 2 and 3 play
S. Following the rules of the game, the probabilities of a positive payoff for
the three players are given by the vector
$\boldsymbol{v}_{1}=(1,0,\frac{1}{2})$, which is one of the extremal
behaviours in Figure 3. The other five extremal behaviours
$\boldsymbol{v}_{i}$ are obtained by the deterministic strategies that
correspond to the deterministic choice of actions
$\texttt{SPP},\texttt{RPR},\texttt{SRS},\texttt{PPS}$ and RRP.

The data set consists of pairs of strategies $\boldsymbol{x}$ and payoffs
$\boldsymbol{y}$. We sample a number of strategies $\\{\boldsymbol{x}_{i}\\}$
following a distribution $\mathcal{D}(\boldsymbol{x})$ that corresponds to
generating a random positive matrix and normalising the rows (see Appendix F
for more details). The corresponding payoffs $\boldsymbol{y}_{i}$ are sampled
according to the rules of the game given the strategy $\boldsymbol{x}_{i}$.
That is, a choice of actions is sampled according to $\boldsymbol{x}_{i}$ and
the corresponding pay-offs $\boldsymbol{y}_{i}$ is sampled via (60). We
therefore have the conditional distribution

$\displaystyle\mathcal{D}(\boldsymbol{y}|\boldsymbol{x})=\sum_{\boldsymbol{a}\in\\{\texttt{R},\texttt{P},\texttt{S}\\}^{3}}P(\boldsymbol{a}|\boldsymbol{x})P(\boldsymbol{y}|\boldsymbol{a})$
(66)

which defines our data distribution
$\mathcal{D}(\boldsymbol{x},\boldsymbol{y})=\mathcal{D}(\boldsymbol{x})\mathcal{D}(\boldsymbol{y}|\boldsymbol{x})$.
Note that the actions of the players are not explicit in the data, only the
strategies $\boldsymbol{x}_{i}$. For a fixed $\boldsymbol{x}$, from (66) the
conditional distribution $\mathcal{D}(\boldsymbol{y}|\boldsymbol{x})$ can be
seen as a probabilistic mixture over the distributions
$P(\boldsymbol{y}|\boldsymbol{a})$. It follows from (63) that the data
distribution $\mathcal{D}(\boldsymbol{x},\boldsymbol{y})$ satisfies the bias

$\displaystyle\mathbb{E}[Y^{1}|\boldsymbol{x}]+\mathbb{E}[Y^{2}|\boldsymbol{x}]+\mathbb{E}[Y^{3}|\boldsymbol{x}]=0,$
(67)

for all $\boldsymbol{x}$, and is of the form described in Theorem 4.1. Since
this follows from the zero-sum property of the game, any data set constructed
from a zero-sum game in the same fashion will satisfy (67).

###  5.3 The learning problem

We now describe a concrete problem that features the RPS data set. Consider a
learning algorithm that has access to the RPS data
$\\{\boldsymbol{x}_{i},\boldsymbol{y}_{i}\\}$ and knows only that it was
generated via a zero-sum game scenario, i.e. the bias (67) is assumed but the
underlying game is unknown. The task we consider is to learn the pay-off
behaviour of the game in the following sense.  Consider a data set
$\displaystyle\chi=\\{\boldsymbol{x}_{i},\boldsymbol{y}_{i}\\}$ (68) of
strategies $\boldsymbol{x}_{i}\in D_{x}$ and corresponding payoffs
$\boldsymbol{y}_{i}\in\\{\pm 1\\}^{3}$ sampled from a data distribution
$\mathcal{D}(\boldsymbol{x},\boldsymbol{y})$ that respects the zero-sum bias
(67). Construct a multi-task model
$\displaystyle\\{\mathcal{P}_{\theta}^{1}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{3}(y|\boldsymbol{x})\\}$
(69) that samples from the marginal payoff distributions
$\mathcal{D}(y^{(k)}|\boldsymbol{x})$ for unseen strategies $\boldsymbol{x}$.

We can now interpret Theorem 4.1 in the context of this learning problem. A
multi-task model class that encodes the zero-sum bias contains models that are
restricted to behaviours in the yellow hexagon of Figure 3B. Furthermore, if
the model class is noncontextual, then the convex hull of these behaviours
cannot contain the dashed hexagon. Thus, no noncontextual multi-task model
that satisfies the zero-sum bias will be able to sample the correct payoff
distributions for all possible strategies. In particular, if a test data set
contains strategies close to the deterministic strategies corresponding to the
choice of actions
$\texttt{RSS},\texttt{SPP},\texttt{RPR},\texttt{SRS},\texttt{PPS}$ and RRP,
then, as described in Figure 3B, it will necessarily fail at sampling the
correct payoff distribution for some strategies in the set, thus contributing
to the expected generalisation error. We note that it is not too difficult to
construct other data sets with the same structure by considering different
scenarios in which a similar bias is present. In section 9 we outline a number
of these in more detail.

##  6 Contextuality of general learning models

Starting from the multi-task case, in this section we describe how one can
arrive at a consistent definition of noncontextuality for single-task models
(Definition 6.2). We argue that in order to do this, it is more natural to
think of contextuality relative to a particular bias of the model, rather than
a property of the model as a whole. This is quite a subtle point that is
important if trying to use our framework beyond this work. However, it is not
necessary for understanding the rest of the paper, and some readers may wish
to skip the section and return to it at a later time.

###  6.1 Connecting multi-task and single-task models

The definition of a noncontextual multi-task learning model (Definition 3)
considers all preparations and effects related to a user that interacts with
the model at inference time. While this is a suitable perspective for multi-
task problems such as 5.3, if one wishes to define a consistent notion of
noncontextuality that applies to more general, single-task models, considering
the full set of preparations and effects can be overkill. To understand this
issue, consider the modification to Problem 4.1 for $m=3$, in which the task
is to learn the joint distribution of labels rather than the marginal
distributions.  Consider a data set
$\chi=\\{\boldsymbol{x}_{i},\boldsymbol{y}_{i}\\}$ of input data
$\boldsymbol{x}_{i}\in\mathbb{R}^{d}$ and label vectors
$\boldsymbol{y}_{i}\in\\{\pm 1\\}^{3}$ sampled from a data distribution
$\mathcal{D}(\boldsymbol{x},\boldsymbol{y})$ satisfying
$\displaystyle\mathbb{E}[Y^{(1)}|\boldsymbol{x}]+\mathbb{E}[Y^{(2)}|\boldsymbol{x}]+\mathbb{E}[Y^{(3)}|\boldsymbol{x}]=0.$
(70) Construct a model $\mathcal{P}_{\theta}(\boldsymbol{y}|\boldsymbol{x})$
that samples from the distribution
$\mathcal{D}(\boldsymbol{y}|\boldsymbol{x})$ for unseen $\boldsymbol{x}$.

We will call the model $\mathcal{P}_{\theta}(\boldsymbol{y}|\boldsymbol{x})$ a
_joint model_ in order to contrast it to the multi-task model that is
concerned only with the marginal statistics. A joint model can clearly be used
to construct an associated multi-task model
$\\{\mathcal{P}_{\theta}^{1}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(y|\boldsymbol{x}),\mathcal{P}_{\theta}^{3}(y|\boldsymbol{x})\\}$
via three coarse-grainings that associate each element of the output label
$\boldsymbol{y}$ to different tasks. In this way, a sufficiently expressive
joint model can trivially simulate any multi-task model, and in practice one
can use the joint model class to tackle Problem 4.1. Suppose that a multi-task
model constructed in this way satisfies the same operational equivalences (43)
and (39) as before, and is contextual by virtue of violating the inequality
(44). Since this multi-task model is contextual and is obtained via a trivial
post-processing of the joint model, it is natural to conclude that there is
some form of contextuality present in the original joint model. However, if we
blindly adopt Definition 3, this is not necessarily the case.

To see this, consider a user with access to the joint model
$\mathcal{P}(\boldsymbol{y}|\boldsymbol{x})$. In the corresponding operational
scenario the preparations are the same as before, however since we have a
single task the effects are now

$\displaystyle\\{\textbf{E}_{+++},\textbf{E}_{++-},\textbf{E}_{+-+},\textbf{E}_{+--},\textbf{E}_{-++},\textbf{E}_{-+-},\textbf{E}_{--+},\textbf{E}_{---}\\}\cup\\{\Omega,\emptyset\\},$
(71)

corresponding to the eight possible values of the label vector
$\boldsymbol{y}$. Since the coarse-grained multi-task model satisfies the
operational equivalence (39) there is an operational equivalence between the
coarse-grained effects

$\displaystyle\textbf{E}_{\pm}^{1}=\sum_{i,j\in\\{+,-\\}}\textbf{E}_{\pm
ij},\quad\textbf{E}_{\pm}^{2}=\sum_{i,j\in\\{+,-\\}}\textbf{E}_{i\pm
j},\quad\textbf{E}_{\pm}^{3}=\sum_{i,j\in\\{+,-\\}}\textbf{E}_{ij\pm}$ (72)

that correspond to observing a label $\pm 1$ for each element of
$\boldsymbol{y}$. We therefore have

$\displaystyle\textbf{E}_{+}^{1}+\textbf{E}_{+}^{2}+\textbf{E}_{+}^{3}\sim\textbf{E}_{-}^{1}+\textbf{E}_{-}^{2}+\textbf{E}_{-}^{3}$
(73)

as before.

The issue arises when one considers the preparation equivalences
$\eqref{opeqv_prep}$. Since the coarse-grained multi-task model satisfies
$\eqref{opeqv_prep}$, it follows that

$\displaystyle
P(\textbf{E}_{\pm}^{k}|\scalebox{0.9}{$\frac{1}{2}$}s_{1}+\scalebox{0.9}{$\frac{1}{2}$}s_{2})=P(\textbf{E}_{\pm}^{k}|\scalebox{0.9}{$\frac{1}{2}$}s_{3}+\scalebox{0.9}{$\frac{1}{2}$}s_{4})=P(\textbf{E}_{\pm}^{k}|\scalebox{0.9}{$\frac{1}{2}$}s_{5}+\scalebox{0.9}{$\frac{1}{2}$}s_{6})$
(74)

for $k=1,2,3$, i.e., the mixtures of preparations are indistinguishable if one
observes marginal statistics only. However, in order to be operationally
equivalent, the preparations must give identical statistics for all effects:

$\displaystyle
P(\textbf{E}_{ijk}|\scalebox{0.9}{$\frac{1}{2}$}s_{1}+\scalebox{0.9}{$\frac{1}{2}$}s_{2})=P(\textbf{E}_{ijk}|\scalebox{0.9}{$\frac{1}{2}$}s_{3}+\scalebox{0.9}{$\frac{1}{2}$}s_{4})=P(\textbf{E}_{ijk}|\scalebox{0.9}{$\frac{1}{2}$}s_{5}+\scalebox{0.9}{$\frac{1}{2}$}s_{6}),\quad
i,j,k\in\\{\pm 1\\}.$ (75)

Even if (74) is satisfied, it may be the case that (75) is not. This will be
the case, for example, when the preparation densities
$\frac{1}{2}s_{1}+\frac{1}{2}s_{2}$, $\frac{1}{2}s_{3}+\frac{1}{2}s_{4}$, and
$\frac{1}{2}s_{5}+\frac{1}{2}s_{6}$ have identical marginal statistics, but
differ in their joint statistics (see Appendix C for an explicit example). In
such cases we cannot conclude that

$\displaystyle\frac{1}{2}s_{1}+\frac{1}{2}s_{2}\sim\frac{1}{2}s_{3}+\frac{1}{2}s_{4}\sim\frac{1}{2}s_{5}+\frac{1}{2}s_{6}.$
(76)

As a result, the ontological model will lack the constraints implied by these
equivalences, and we may be unable to prove contextuality888In fact, in
quantum models, if one cannot identify any operational equivalences related to
the preparations, there is always a noncontextual model [20].. Considering the
full set of preparations and effects therefore seems problematic in order to
arrive at a consistent notion of contextuality across the single-task and
multi-task settings.

###  6.2 Contextuality relative to a bias

The moral of this story is that it may be more natural to think about
contextuality relative to a particular bias of the model, rather than as a
property of the model as a whole. Indeed, when studying contextuality it is
always necessary to specify the procedures and observations that most
accurately reflect the spirit of the nonclassicality one is wishing to probe,
and different choices can lead to different conclusions [30]. The solution to
this conundrum therefore comes from considering contextuality with respect to
those preparations and effects that play a role in a specific bias. In this
way, one can identify a type of contextuality present in the operational
statistics that is related to the non-existence of a noncontextual ontological
model for these preparations and effects only.

In particular, we may consider a general learning model
$\mathcal{P}_{\theta}(\boldsymbol{y}|\boldsymbol{x})$ with associated
operational scenario
$\\{\texttt{Preps},\texttt{Effects},P(\textbf{E}|\textbf{S})\\}$ for which
there exists an inductive bias that can be written as

$\displaystyle\sum_{\textbf{E}_{i}\in\mathfrak{E}_{1}}p_{i}P(\textbf{E}_{i}|\textbf{S}_{\boldsymbol{x}})=\sum_{\textbf{E}_{j}\in\mathfrak{E}_{2}}q_{j}P(\textbf{E}_{j}|\textbf{S}_{\boldsymbol{x}})\quad\forall\textbf{S}_{\boldsymbol{x}}$
(77)

where $\mathfrak{E}_{1},\mathfrak{E}_{2}\subseteq\texttt{Effects}$ and
$p_{i},q_{j}$ are convex weights. This implies the operational equivalence

$\displaystyle\sum_{\textbf{E}_{i}\in\mathfrak{E}_{1}}p_{i}\textbf{E}_{i}\sim\sum_{\textbf{E}_{j}\in\mathfrak{E}_{1}}q_{j}\textbf{E}_{j}.$
(78)

We can now define noncontextuality relative to the bias as follows.  Consider
a learning model $\mathcal{P}(\boldsymbol{y}|\boldsymbol{x})$ with associated
operational scenario
$\displaystyle\\{\texttt{Preps},\texttt{Effects},P(\textbf{E}|\textbf{S})\\}$
(79) that satisfies an inductive bias of the form (77). The learning model is
noncontextual relative to the bias (77) if the operational statistics of the
operational scenario
$\displaystyle\\{\texttt{Preps},\mathfrak{E}_{1}\cup\mathfrak{E}_{2},P(\textbf{E}|\textbf{S})\\}$
(80) admits a noncontextual ontological model. Using this definition, if the
coarse-grained multi-task model is contextual in the sense of Definition 3,
the joint model is contextual relative to the bias (28), which unifies the
multi-task and single-task approaches. We note that one could also consider
biases that are satisfied by a subset of preparations, and consider a similar
definition to the above involving these preparations only, but we do not
consider this in this work.

##  7 Encoding inductive bias into quantum learning models

Until now, we have only been concerned with abstract representations of
learning models in the form of preparations and effects of an operational
scenario. In this section we present methods to construct classes of multi-
task quantum machine learning models
$\\{\\{\mathcal{P}^{k}_{\theta}(y|\boldsymbol{x})\\}_{k=1,\cdots,m}\\}_{\theta}$
with $\boldsymbol{x}\in\mathbb{R}^{d}$ and $y\in\\{-1,+1\\}$ that encode the
inductive bias

$\displaystyle\mathbb{E}[Y^{(1)}|\boldsymbol{x}]+\mathbb{E}[Y^{(2)}|\boldsymbol{x}]+\cdots+\mathbb{E}[Y^{(m)}|\boldsymbol{x}]=0\quad\forall\boldsymbol{x}$
(81)

for all parameters $\theta$ in the class. We consider a bias of the above form
due to its simplicity and relevance to this work, but much of what we say can
be straightforwardly extended to biases expressed as general linear
combinations of the probabilities $\mathcal{P}_{\theta}^{k}(y|\boldsymbol{x})$
for arbitrary finite label dimension, and even to certain forms of nonlinear
biases (as we explain in Section 7.3). We remind the reader that since quantum
theory is known to be contextual in the generalised sense [20, 54], the
constraints on noncontextual models related to this bias do not apply to
quantum models.

The type of quantum models we consider correspond to parameterised quantum
circuits [55],

$\displaystyle\mathcal{P}^{k}_{\boldsymbol{\theta}}(y|\boldsymbol{x})=\bra{\psi_{0}}U^{\dagger}(\boldsymbol{x},\boldsymbol{\theta})\mathcal{M}_{y|k}U(\boldsymbol{x},\boldsymbol{\theta})\ket{\psi_{0}},$
(82)

where $\ket{\psi_{0}}$ is some $n$-qubit initial state, $U$ is a parameterised
unitary that depends on the input data and some trainable parameters
$\boldsymbol{\theta}$, and
$\\{\\{\mathcal{M}_{+1|k},\mathcal{M}_{-1|k}\\}\\}_{k}$ is a set of two-
outcome measurements that sample the label for task $k$. Denoting by
$\mathcal{O}_{k}=\mathcal{M}_{+1|k}-\mathcal{M}_{-1|k}$ the corresponding
observable for task $k$, from (81) our aim is to find choices of
$\mathcal{O}_{k}$, $\ket{\psi_{0}}$ and $U$ such that

$\displaystyle\sum_{k}\bra{\psi_{0}}U^{\dagger}(\boldsymbol{x},\boldsymbol{\theta})\mathcal{O}_{k}U(\boldsymbol{x},\boldsymbol{\theta})\ket{\psi_{0}}=\bra{\psi_{0}}U^{\dagger}(\boldsymbol{x},\boldsymbol{\theta})\mathcal{H}U(\boldsymbol{x},\boldsymbol{\theta})\ket{\psi_{0}}=0\quad\forall\boldsymbol{x},\boldsymbol{\theta},$
(83)

where we call $\mathcal{H}=\sum_{k}\mathcal{O}_{k}$ the _bias operator_. Note
that from the above, $\mathcal{H}$ has to have at least one non-positive
eigenvalue. We explore two methods that we call the state-based and
measurement-based approaches. As we will see, the linearity of quantum theory
plays an important role, and provides a rather natural way of encoding such
biases.

Figure 6: Two methods for encoding the inductive bias (81) into a quantum
machine learning model. A. The state-based approach. The first unitary creates
states that satisfy the bias for the chosen measurement operators
$\mathcal{M}_{y|k}$. The second unitary is a bias-invariant layer that
performs rotations that preserve the bias for all input states. B. The
measurement-based approach. Here, an arbitrary input state and unitary can be
chosen, but the measurement observables are chosen to have a specific
structure that enforces the bias.

###  7.1 State-based approach

The first step of this approach is to fix a choice of observables
$\\{\mathcal{O}_{k}\\}$. A simple choice we will use in the next section is to
take $\mathcal{O}_{k}=\sigma_{z}^{(k)}$, so that a computational basis
measurement on the $k^{\text{th}}$ qubit samples the label for task $k$. Given
such a choice, the question then is how to construct $U$ and $\ket{\psi_{0}}$
such that (83) holds. The method we propose is to build the quantum model from
a sequence of two subcircuits $V(\boldsymbol{\theta})$ and
$W(\boldsymbol{\boldsymbol{x},\theta})$ (see Figure 6A). The first circuit is
a parameterised unitary that we call the _input preparation unitary_ , whose
role is to prepare a state for the next circuit that satisfies the bias, i.e.
such that $\langle\mathcal{H}\rangle=0$. The second circuit is a _bias-
invariant layer_ , meaning that it preserves the quantity
$\langle\mathcal{H}\rangle$ for arbitrary input states from the first layer.

We first focus on the second circuit $W(\boldsymbol{\boldsymbol{x},\theta})$.
In order to be bias-invariant, unitaries in this circuit must belong to the
set

$\displaystyle
G=\\{U\;|\;\bra{\psi}U^{\dagger}\mathcal{H}U\ket{\psi}=\bra{\psi}\mathcal{H}\ket{\psi}\;\forall\ket{\psi}\\},$
(84)

which forms a matrix Lie group under matrix multiplication. The associated
matrix Lie algebra999Here we use the ‘physicist’ convention where we include a
factor of $i$ so that the matrices $X$ are Hermitian; in the mathematics
literature the $i$ is usually absorbed into the matrix $X$. is equivalent to
the vector space of matrices that exponentiate to elements of $G$:

$\displaystyle\mathfrak{g}=\\{X\;|\;\exp{(itX)}\in G\;\forall
t\in\mathbb{R}\\}.$ (85)

For the group $G$, this is just equal to those Hermitian operators that
commute with $\mathcal{H}$,

$\displaystyle\mathfrak{g}=\\{X\;|\;X^{\dagger}=X,[X,\mathcal{H}]=0\\}.$ (86)

It follows that the bias $\langle\mathcal{H}\rangle$ is conserved by any data-
encoding unitary of the form $W(\boldsymbol{x})=\exp{(iXf(\boldsymbol{x}}))$
and any trainable unitary of the form
$W(\boldsymbol{\theta})=\exp{(iXg(\boldsymbol{\theta}))}$, where
$X\in\mathfrak{g}$ and $f$, $g$ are arbitrary real functions. Any number of
unitaries of this form can therefore be combined in sequence to construct a
bias-invariant circuit $W(\boldsymbol{\boldsymbol{x},\theta})$. The main
challenge here is determining the set (86) and judiciously choosing the
generators $X$ from which $W$ is defined. For choices of $\mathcal{O}_{k}$
with a lot of structure this may be relatively easy however. For example, for
the choice $\mathcal{O}_{k}=\sigma_{z}^{(k)}$, one finds that any generator
$X$ that is diagonal in the computational basis, as well as those of the form
$X=\sigma_{x}^{(i)}\sigma_{x}^{(j)}+\sigma_{y}^{(i)}\sigma_{y}^{(j)}$,
$i,j\in\\{1,\cdots,m\\},i\neq j$ commute with $\mathcal{H}$. These may be
combined linearly to create new generators that also commute with
$\mathcal{H}$.

We now turn to the input preparation circuit $V(\boldsymbol{\theta})$. This
should prepare a state that satisfies the bias, i.e. it consists of unitaries
in the set

$\displaystyle
G^{\prime}=\\{U\;|\;\bra{\psi_{0}}U^{\dagger}\mathcal{H}U\ket{\psi_{0}}=0\\}.$
(87)

In general this does not form a group (since it is not closed) and therefore
may be more difficult to characterise than $G$. Note that even if
$\ket{\psi_{0}}$ satisfies the bias, unitaries in $G^{\prime}$ do not
necessarily commute with $\mathcal{H}$. An example of such a unitary for the
case $\mathcal{O}_{k}=\sigma_{z}^{(k)}$ and $\ket{\psi_{0}}=\ket{+}^{\otimes
n}$ is

$\displaystyle
V(\theta)=\exp{(i\sigma_{x}^{(1)}\theta)}\exp{(-i\sigma_{x}^{(2)}\theta)}$
(88)

for any $\theta\in(0,\pi]$. We are unaware of general methods to construct
parameterised unitaries in $G^{\prime}$, so at the moment we rely on ad-hoc
approaches like the above.

###  7.2 Measurement-based approach

The second approach (Figure 6B) is based on encoding the bias into the
structure of the measurement operators rather than the parameterised unitary.
In this case, one can consider an arbitrary input state $\ket{\psi_{0}}$ and
arbitrary parameterised unitary $U(\boldsymbol{x},\boldsymbol{\theta})$. The
observables however must be chosen so that

$\displaystyle\mathcal{O}_{1}+\mathcal{O}_{2}+\cdots+\mathcal{O}_{m}=\mathcal{H}=0.$
(89)

From the linearity of the trace it follows that this choice ensures (81) is
satisfied. An example of observables that satisfy (89) for a qubit and $m=3$
are any three equally spaced ‘trine’ observables in a plane of the Bloch
sphere, e.g., $\mathcal{O}_{k}=\boldsymbol{v}_{k}\cdot\boldsymbol{\sigma}$
with $\boldsymbol{v}_{k}=(\cos\theta_{k},\sin\theta_{k},0)$ and
$\theta_{k}=2k\pi/3$. However, to the best of our knowledge, observables of
this form for larger dimension are not known and further research is required
in this direction. Here, one may expect that mathematical tools from other
constructions of symmetric measurements such as mutually unbiased bases and
SIC-POVMs to be useful [56]. In Appendix D we give a previously unknown
construction for the case $m=3$ for all even dimensions that satisfies (89).

Finally we comment that for both the state and measurement based approaches,
it may be beneficial to construct models that sample from classical
probabilistic mixtures of such circuits by combining them with stochastic
neural network models (see e.g. [57]), but we do not consider this here.

###  7.3 Nonlinear biases

The same techniques can also be used to encode nonlinear biases if they can be
expressed through a bias operator as $\langle\mathcal{H}\rangle=0$ in the
quantum model. Consider for example a bias of the form

$\displaystyle\mathbb{E}[f_{1}(Y^{(1)})|\boldsymbol{x}]+\mathbb{E}[f_{2}(Y^{(2)})|\boldsymbol{x}]+\cdots+\mathbb{E}[f_{m}(Y^{(m)})|\boldsymbol{x}]=0\quad\forall\boldsymbol{x}$
(90)

where the $f_{k}$ are potentially nonlinear functions of the labels. If the
observables $\mathcal{O}_{k}$ are of the form
$\mathcal{O}_{k}=\sum_{y}y\mathcal{M}_{y|k}$ with $\mathcal{M}_{y|k}$ the
projector corresponding to label $y$ of task $k$, then the left hand side of
the above is given by (83) where

$\displaystyle\mathcal{H}=f_{1}(\mathcal{O}_{1})+f_{2}(\mathcal{O}_{2})+\cdots+f_{m}(\mathcal{O}_{m}),$
(91)

and $f_{k}(\mathcal{O}_{k})=\sum_{y}f_{k}(y)\mathcal{M}_{y|k}$. Thus, one can
use the state-based or measurement-based approach described with this bias
operator in order to construct model classes that encode (90). Of course, the
difficult task to find the corresponding generators $X$ in (86) or a
collection of measurements satisfying (89) for a given nonlinear bias. It
would be interesting to understand which biases admit efficient model
constructions in this way.

##  8 Outperforming classical surrogates

In this section we construct a class of quantum models that encode the bias
(81) for $m=3$, using the state-based approach of Section 7.1. We then train
the model class using the RPS data set described in Section 5. In order to
investigate the effect of the encoded bias, we compare the quantum models to a
class of classical surrogate models recently introduced in [11]. As we will
see, the quantum model class achieves a lower generalisation error than its
associated surrogate model class, which we claim to be due to the ability of
the quantum class to encode the relevant inductive bias. We stress that we are
not claiming that this is evidence of ‘quantum advantage’ since the quantum
models we consider are small enough to be easily simulated on a laptop
computer. Code used to generate the plots of this section can be found at
https://github.com/XanaduAI/Contextual-ML.

###  8.1 The learning problem

The learning problem we consider is that of learning the payoff behaviour of
an unknown zero-sum game, as described in Problem 5.3. We use the RPS data set

$\displaystyle\chi=\\{\boldsymbol{x}_{i},\boldsymbol{y}_{i}\\},$ (92)

containing $1500$ strategies $\boldsymbol{x}_{i}\in D_{x}$ and payoffs
$\boldsymbol{y}_{i}$. Since from normalisation the last entry of each row of
$\boldsymbol{x}$ is linearly dependent on the first two, we compress each
$\boldsymbol{x}_{i}$ into a matrix of size $3\times 2$, and scale the data by
$\frac{\pi}{2}$ so that the input data points correspond to the matrix

$\displaystyle\boldsymbol{x}=\frac{\pi}{2}\begin{pmatrix}P(A_{1}=\texttt{R})&P(A_{1}=\texttt{P})-P(A_{1}=\texttt{S})\\\
P(A_{2}=\texttt{P})&P(A_{2}=\texttt{S})-P(A_{2}=\texttt{R})\\\
P(A_{3}=\texttt{S})&P(A_{3}=\texttt{R})-P(A_{3}=\texttt{P})\end{pmatrix}=\begin{pmatrix}x_{1}&x_{4}\\\
x_{2}&x_{5}\\\ x_{3}&x_{6}\end{pmatrix}.$ (93)

Figure 7: The three-qubit quantum model class we use in our numerical
investigation that encodes the bias (81) using the state-based approach of
section 7 (here we use the notation $Z\equiv\sigma_{z}$). The bias operator
for this ansatz is $\mathcal{H}=\sigma_{z}^{1}+\sigma_{z}^{2}+\sigma_{z}^{3}$.
The input preparation unitary $V_{\theta}$ prepares a state such that
$\langle\mathcal{H}\rangle=0$, where single-qubit Y rotations on the first and
second qubit are correlated to have a difference of $\pi$. The following
layers are bias-invariant layers. Each parameterised gate appearing in a
unitary $U_{\boldsymbol{\theta}}$ has its own parameter (i.e. the unitaries
$U_{\boldsymbol{\theta}}$ can have different parameter values). Boxes
connected by a line in $S^{2}_{\boldsymbol{x}}$ and $U_{\boldsymbol{\theta}}$
correspond to parameterised rotations
$\exp(ix_{k}x_{l}\sigma_{z}\otimes\sigma_{z})$ and
$\exp(i\theta\sigma_{z}\otimes\sigma_{z})$ respectively, and SWAP is the usual
two qubit swap operator.

###  8.2 The quantum model class

We consider a simple class of three-qubit quantum models, described in Figure
7, which encode the bias using the state-based method of section 7. This class
contains models of the form
$\mathcal{P}_{\theta}(\boldsymbol{y}|\boldsymbol{x})$ which we view as a
multi-task model
$\\{\mathcal{P}^{1}_{{\theta}}(y|\boldsymbol{x}),\mathcal{P}^{2}_{{\theta}}(y|\boldsymbol{x}),\mathcal{P}^{3}_{{\theta}}(y|\boldsymbol{x})\\}$
by associating each element of $\boldsymbol{y}$ with a separate task.
Following [44], the expectation value of the final $\sigma_{z}$ measurement on
any of the qubits is equivalent to a truncated Fourier series of the form

$\displaystyle
f_{\theta}(\boldsymbol{x})=\sum_{\boldsymbol{\omega}\in\Omega}c_{\boldsymbol{\omega}}(\theta)e^{i\boldsymbol{\omega}\cdot\boldsymbol{z}(\boldsymbol{x})},$
(94)

where
$\boldsymbol{z}(\boldsymbol{x})=(x_{1},x_{2},x_{3},x_{4}x_{5},x_{4}x_{6},x_{5}x_{6}).$
The frequency spectrum $\Omega$ is determined by the eigenspectra of the data-
encoding gates. In our case one finds

$\displaystyle\Omega_{L}=\\{(\omega_{1},\omega_{2},\cdots,\omega_{6})\;|\;\omega_{i}\in\\{-L,-L+1,\cdots,L-1,L\\}\;\forall
i\\},$ (95)

giving a total of $(2L+1)^{6}$ vectors $\omega$. The coefficients
$c_{\boldsymbol{\omega}}(\theta)$ are determined by the structure of the rest
of the circuit; note that we have
$c_{\boldsymbol{-\omega}}=c^{*}_{\boldsymbol{\omega}}$ so that $f$ is real-
valued. The model therefore samples labels $\boldsymbol{y}$ such that

$\displaystyle(\mathbb{E}[Y^{(1)}|\boldsymbol{x}],\mathbb{E}[Y^{(2)}|\boldsymbol{x}],\mathbb{E}[Y^{(3)}|\boldsymbol{x}])=(f^{1}_{\theta}(\boldsymbol{x}),f^{2}_{\theta}(\boldsymbol{x}),f^{3}_{\theta}(\boldsymbol{x})),$
(96)

where each $f^{k}_{\theta}$ is of the form (94). Note that each of the
generators of the gates in the circuit commute with the bias operator
$\mathcal{H}=\sigma_{z}^{(1)}+\sigma_{z}^{(2)}+\sigma_{z}^{(3)}$ and that the
input preparation unitary $V_{\theta}$ always prepares a state such that
$\langle\mathcal{H}\rangle=0$. The values of the coefficients of the three
Fourier series $f^{k}_{\theta}(\boldsymbol{x})$ are therefore correlated by
the circuit structure in such a way that the zero-sum bias is always
satisfied.

Figure 8: left: The average KL divergence estimated via (103) for the four
models we consider. The solid lines denote the average over $20$ random
initialisations of the weights (light curves). The best performance is
achieved by the biased quantum model. Both surrogate models suffer from
overfitting, as can be seen from the increase in KL divergence, and non-
convergence of the negative log likelihood (101) (right).

###  8.3 Classical surrogates of quantum models

The idea of constructing a classical surrogate model of a quantum model was
recently introduced in [11] to study the inductive bias of quantum models for
regression tasks, i.e. models of the form
$f_{\theta}(\boldsymbol{x})\in\mathbb{R}$. A surrogate model class is simply a
linear model in the same Fourier features of the quantum model. For example,
consider a quantum model class of the form (94). The surrogate class is the
parameterised truncated Fourier series

$\displaystyle
g_{\boldsymbol{a},\boldsymbol{\beta}}(\boldsymbol{x})=\sum_{\boldsymbol{\omega}\in\Omega}\alpha_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\cdot\boldsymbol{z(\boldsymbol{x}}))+\beta_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\cdot\boldsymbol{z}(\boldsymbol{x})),$
(97)

where the $\alpha_{\boldsymbol{\omega}}$ and $\beta_{\boldsymbol{\omega}}$ are
real-valued trainable parameters and $\Omega$ is the same as in (95). We have
chosen this parameterisation rather than the exponential form since we know
the model must produce a real number and can therefore avoid using complex
numbers. The surrogate model class is larger than the quantum model class
since it contains all models in (94), however it lacks the specific bias of
the quantum class that is encoded in the structure of the Fourier
coefficients. Interestingly, surrogate model classes often perform better than
generic quantum models for regression on a range of data sets [11].

Since our problem is not a regression problem but involves sampling the payoff
labels, we need to define a natural notion of a classical surrogate to compare
the quantum model (96) against. The logic we will follow is as above: view
each $f^{k}_{\theta}(\boldsymbol{x})$ of the quantum model as a truncated
Fourier series and construct a surrogate model by ignoring the structure in
the coefficients. To this end, we consider a collection of three linear models

$\displaystyle(g^{1}_{\boldsymbol{\alpha}_{1},\boldsymbol{\beta}_{1}}(\boldsymbol{x}),g^{2}_{\boldsymbol{\alpha}_{2},\boldsymbol{\beta}_{2}}(\boldsymbol{x}),g^{3}_{\boldsymbol{\alpha}_{3},\boldsymbol{\beta}_{3}}(\boldsymbol{x})),$
(98)

where each
$g^{k}_{\boldsymbol{\alpha}_{k},\boldsymbol{\beta}_{k}}(\boldsymbol{x})$ is of
the form (97) and has the spectrum $\Omega_{L}$. In analogy to (96) we would
like to interpret these values as expectation values
$\mathbb{E}[Y^{(k)}|\boldsymbol{x}]$, however this is not immediately possible
since $g^{k}_{\boldsymbol{\alpha}_{k},\boldsymbol{\beta}_{k}}$ is not bounded
in $[-1,1]$. To remedy this, we use a HardTanh function

$\displaystyle h(x)=\begin{cases}-1&\text{if }x<-1\\\ x&\text{if }-1\leq x\leq
1\\\ 1&\text{if }x>1\end{cases}$ (99)

so that payoffs are sampled from the model as

$\displaystyle(\mathbb{E}[Y^{(1)}|\boldsymbol{x}],\mathbb{E}[Y^{(2)}|\boldsymbol{x}],\mathbb{E}[Y^{(3)}|\boldsymbol{x}])=(h(g^{1}_{\boldsymbol{\alpha}_{1},\boldsymbol{\beta}_{1}}(\boldsymbol{x})),h(g^{2}_{\boldsymbol{\alpha}_{2},\boldsymbol{\beta}_{2}}(\boldsymbol{x})),h(g^{3}_{\boldsymbol{\alpha}_{3},\boldsymbol{\beta}_{3}}(\boldsymbol{x}))).$
(100)

This surrogate model class has access to the same frequency spectra as the
quantum model class and by virtue of being less constrained, contains the
quantum class as a specific subset of its parameters. The surrogate model does
not however encode the zero-sum bias (81). This is because the constraint is
related in a complex manner to the weights
$\boldsymbol{\alpha}_{k},\boldsymbol{\beta}_{k}$ and it is therefore not clear
how to enforce it. Moreover, attempting to enforce the constraint via a
postprocessing of the $g^{k}$’s seems cumbersome, and we were unable to
identify a general method that would scale to larger label dimensions, unlike
in the quantum case. We therefore expect that it is infeasible to encode this
kind of bias into a linear Fourier features model, and indeed it is this
difference that we expect to lead to a lower generalisation error in the
quantum model.

Figure 9: The effect of adding L2 regularisation to the cost function for the
surrogate model for $L=2$ for different regularisation strengths (lighter
curves imply stronger regularisation). This controls overfitting but does not
result in better generalisation.

###  8.4 Training and evaluation

To train the models we minimise the negative log likelihood of the labels
given the strategies

$\displaystyle\mathcal{L}=-\sum_{(\boldsymbol{x}_{i},\boldsymbol{y}_{i})\in\chi}\left(\log(\mathcal{P}^{1}_{\theta}(y_{i}^{(1)}|\boldsymbol{x}_{i}))+\log(\mathcal{P}^{2}_{\theta}(y_{i}^{(2)}|\boldsymbol{x}_{i}))+\log(\mathcal{P}^{3}_{\theta}(y_{i}^{(3)}|\boldsymbol{x}_{i}))\right)$
(101)

using the Adam gradient-descent optimiser. Full details on the data sampling
and training can be found in Appendix F. We acknowledge that this training
method does not scale well for quantum models since it requires the ability to
efficiently estimate log probabilities, which becomes infeasible for large
circuits. Indeed, a crucial challenge of quantum machine learning is to
develop scalable methods that perform well on generative tasks, but we do not
focus on this problem in this work.

To evaluate the trained models we consider the sum of the Kullback–Leibler
divergences between the trained models
$\mathcal{P}^{k}_{\theta}(y|\boldsymbol{x})$ and the true data distributions
$\mathcal{D}_{k}(y|\boldsymbol{x})\equiv\mathcal{D}(y^{(k)}|\boldsymbol{x})$,
averaged over $\mathcal{D}(\boldsymbol{x})$:

$\displaystyle\mathbb{E}_{\mathcal{D}(\boldsymbol{x})}\left[\frac{1}{3}\sum_{k=1}^{3}D_{\text{KL}}(\mathcal{D}_{k}(Y|\boldsymbol{x})||\mathcal{P}^{k}_{\theta}(Y|\boldsymbol{x}))\right]=\mathbb{E}_{\mathcal{D}(\boldsymbol{x})}\left[\frac{1}{3}\sum_{k=1}^{3}\left(\sum_{y=\pm
1}\mathcal{D}_{k}(y|\boldsymbol{x})\log\left(\frac{\mathcal{D}_{k}(y|\boldsymbol{x})}{\mathcal{P}^{k}_{\theta}(y|\boldsymbol{x})}\right)\right)\right].$
(102)

We sample $N=10000$ strategies $\boldsymbol{x}_{i}^{\text{test}}$ via
$\mathcal{D}(\boldsymbol{x})$ and estimate the average (102) with the sum

$\displaystyle\frac{1}{3N}\sum_{\boldsymbol{x}_{i}^{\text{test}}}\sum_{k=1}^{3}D_{\text{KL}}(\mathcal{D}_{k}(Y|\boldsymbol{x}_{i}^{\text{test}})||\mathcal{P}_{k}(Y|\boldsymbol{x}_{i}^{\text{test}})),$
(103)

which we calculate to machine precision using symbolic expressions of the
model probabilities.

###  8.5 Results

In our study we consider four model classes: (i) The biased quantum model
given in Figure 7 with $L=2$ and $B=2$, (ii) a generic quantum model with
approximately the same number of parameters, the details of which we give in
appendix E, (iii) a surrogate model corresponding to a $L=1$ quantum model,
(iv) a surrogate corresponding to a $L=2$ quantum model. The results are given
in Figure 8. As has been observed before [11], the surrogate models are able
to outperform a generic quantum model class. The best performance is achieved
by the biased quantum model class however, which we conclude is due to the
ability of the quantum model to naturally encode the zero-sum bias. Note that
the surrogate models suffer severely from over-fitting, as can be seen from
the decrease in the negative log likelihood and increase of generalisation
error. This is due to the large number of parameters the surrogate models have
relative to the quantum models. To try and counter this, we also optimised the
surrogate models using a $L2$ weight penalty term added to the cost (101).
Although this alleviates the problem of overfitting, we did not find that it
improved generalisation performance (see Figure 9 for the case $L=2$ and
Figure 11 of the appendix for $L=1$). This suggests that the lower
generalisation error of the quantum model over the surrogate originates from
the inductive bias rather than overfitting in the surrogate model.

##  9 Avenues for contextuality-inspired inductive bias

In this work we have focused on a single, simple inductive bias and shown that
contextuality plays a role in learning. Our ultimate goal however is to
identify complex problems of practical interest for which contextuality is
crucial, and for which the structure of quantum models makes them the model of
choice. In this section, we suggest a number of scenarios with this goal in
mind, and finish by discussing possible extensions to our framework.

###  9.1 Zero-sum games with larger payoff dimension

Most real-life zero-sum game scenarios involve payoffs that take more values
than only $\pm 1$ as we considered here. For example, one could consider a
zero-sum game scenario with $N$ players and conditional payoff distributions
$\mathcal{P}(\boldsymbol{y}|\boldsymbol{x})$ with each element of
$\boldsymbol{y}$ in $[-C,\cdots,C]$ for some integer $C$. From the zero-sum
condition it follows that $\sum_{k=1}^{N}\mathbb{E}(Y^{(k)}|\boldsymbol{x})=0$
$\forall\;\boldsymbol{x}$ as before. To see how this leads to a constraint on
noncontextual models, we first shift the values of the payoffs by $C$ so that
they are in the range $[0,2C]$. This does not change the nature of the problem
since it is just a shift of the label data. The zero-sum condition then
becomes

$\displaystyle\sum_{k=1}^{N}\sum_{y=0}^{2C}\mathcal{P}^{k}_{\theta}(y|\boldsymbol{x})y=C\quad\forall\boldsymbol{x}\implies\frac{1}{N}\sum_{k=1}^{N}\sum_{y=0}^{2C}p_{y}\mathcal{P}^{k}_{\theta}(y|\boldsymbol{x})=\frac{1}{N(2C+1)}\quad\forall\boldsymbol{x},$
(104)

where $p_{y}=y/\sum_{y}y=\frac{y}{C(2C+1)}$ is a probability distribution.

The right-hand side of the above allows us to identify an operational
equivalence in the corresponding operational scenario of a multi-task model.
Consider the following two effect densities: ($e_{1}$) A player is chosen at
random. A $2C$-sided die with probabilities $p_{i}$ is rolled with outcome $y$
and the payoff of Player $k$ is observed, and success corresponds to the model
returning the payoff value $y$; ($e_{2}$) The model is ignored and success is
declared with probability $q=1/(N(2C+1))$. These two procedures correspond to
the left and right sides of the equality in the right hand side of (104). It
follows that the two measurement procedures give identical statistics for all
strategies. Since $e_{2}=q\Omega+(1-q)\emptyset$ this implies the operational
equivalence

$\displaystyle\frac{1}{N}\sum_{k=1}^{N}\sum_{y=1}^{2C}p_{y}\textbf{E}_{y|k}\sim
q\Omega+(1-q)\emptyset,$ (105)

where $\textbf{E}_{y|k}$ is the effect corresponding to observing payoff $y$
of Player $k$. This leads to the constraint

$\displaystyle\sum_{k=1}^{N}\sum_{y=1}^{2C}\xi_{\textbf{E}_{y|k}}(\lambda)p_{y}=\frac{1}{2C+1}\quad\forall\;\lambda$
(106)

on the noncontextual ontological model. This will limit the expressivity of
the model as before, however a clear picture of the structure of these
constraints and how they affect learning is needed. We note that one need not
necessarily consider only zero-sum games; similar constraints can be found in
the same manner in any constant-sum game as well.

###  9.2 Conserved substances in networks

Biases of the form (81) become relevant when modelling the behaviour of
conserved substances in networks, which may have relevance to problems in
biology (e.g. a network of cells sharing a conserved substance), population
modelling (a network of locations sharing a conserved number of
people/animals), manufacturing logistics (a network of factories sharing a
conserved number of resources). To formalise these settings, consider a
network consisting of $N$ cells that share some substance. We denote the
amount of the substance in cell $j$ by $y_{j}$, which we assume to take
discrete values. We also consider some parameters $\boldsymbol{x}$ (e.g. time,
network connectivity) that affect the exchange of the substance throughout the
network, and assume that the total amount of substance is conserved on
average:

$\displaystyle\mathbb{E}[Y_{1}|\boldsymbol{x}]+\mathbb{E}[Y_{2}|\boldsymbol{x}]+\cdots+\mathbb{E}[Y_{N}|\boldsymbol{x}]=C.$
(107)

Consider a multi-task model whose aim is to model the amount of substance in a
given cell given parameters $\boldsymbol{x}$. That is, it is a probabilistic
model $\mathcal{P}^{k}_{\theta}(y|\boldsymbol{x})$ that from (107) satisfies

$\displaystyle\sum_{k}\sum_{y}\mathcal{P}^{k}_{\theta}(y|\boldsymbol{x})y=C.$
(108)

This is of the same from as the left hand side of (104), and so an analogous
constraint to (106) can be derived on the corresponding noncontextual
ontological model.

###  9.3 Quantum control under a conserved quantity

Consider a quantum control scenario where a multipartite intial state
$\rho_{0}$ is evolved to a final state $\rho(\boldsymbol{x})$ and one of a
number of measurements $\\{\textbf{E}_{y|k}\\}$ is made with outcome
$y=0,1,\cdots,M$. Here, $\boldsymbol{x}$ are some parameters of the control
scenario, for example strengths of various interactions and interaction time.
Suppose there exists an operator of the form

$\displaystyle\mathcal{O}=\sum_{yk}\textbf{E}_{y|k}g_{y}$ (109)

with $g_{y}\geq 0$ that is conserved during the control process, i.e.
$\langle\mathcal{O}\rangle=C\;\forall\boldsymbol{x}$. For example,
$\mathcal{O}$ could be the energy of the system, and control operations are
known to conserve energy. If we wish to construct a multi-task model to learn
the experimental behaviour, this conservation law translates to the desirable
inductive bias

$\displaystyle\sum_{y,k}\mathcal{P}^{k}_{\theta}(y|\boldsymbol{x})g_{y}=C\implies\frac{1}{N}\sum_{y,k}\mathcal{P}^{k}_{\theta}(y|\boldsymbol{x})p_{y}=\frac{C}{NG}$
(110)

where $G=\sum_{y}g_{y}$, $p_{y}=g_{y}^{k}/G$. Similarly to the examples above,
this allows us to identify an operational equivalence that leads to a
constraint

$\displaystyle\sum_{k}\sum_{y}\xi_{\textbf{E}_{y|k}}(\lambda)p_{y}=\frac{C}{G}\quad\forall\;\lambda,$
(111)

on a noncontextual learning model.

###  9.4 Possible extensions to our framework

A significant challenge of this work involved deciding on how to cast machine
learning in the language of contextuality, and the framework we present here
is by no means the only option, nor the most general framework possible. For
example, it is possible to define a notion of contextuality for
transformations [20], in addition to the preparations and effects we consider
in this work. This notion of contextuality may be more suited, for example, to
studying the non-classically of layers in models with a sequential structure.
Another option would be to consider a definition of contextuality that is
defined with respect to the full model class, rather than a single model in
the class as in Definition 3. Doing this, one could study operational
equivalences across different models in the class, although care would be
needed to connect these equivalences to relevant concepts in learning. It is
also worth stating clearly that the noncontextual constraints we consider in
this work are qualitatively different from the constraints in Kochen-Specker
type contextuality [49], which is studied in most works connecting quantum
computation to contextuality. Kocken-Specker type contextuality can still
exist within our framework, but follows from qualitatively different
operational equivalences (that we briefly described in Section 2.6). For this
reason our work is something of a departure from the usual perspective of
contextuality and could potentially find applications in the wider field of
quantum computation.

Generalised contextuality has also recently been connected to the framework of
generalised probabilistic theories [58, 59, 60, 61] (see also [62] for an
application to associative memories). This framework is commonly used in
foundations research and allows one to transform any probabilistic theory,
such as classical and quantum theory, into a simple linear structure in which
the states and effects are represented as vectors in a vector space101010this
is essentially what we have done in the geometric picture of section 4.2 and
Figure 3.. In the generalised probability theory framework, noncontextuality
becomes equivalent to a simple geometric condition, called simplex
embedability [60], which relates to the possibility of embedding the state
space into a higher dimensional simplex, and the effect space into its dual.
Understanding this structural limitation in the context of learning models may
therefore lead to general insights about the structural difference between
contextual and noncontextual learners, and could potentially be used to define
a measure of contextuality that goes beyond the binary
contextual/noncontextual framework we assume.

##  10 Outlook

Although quantum machine learning has progressed in many ways, it nevertheless
remains unclear why a machine learning practitioner would reach for the
quantum toolbox amongst the vast array of classical tools on offer. In order
to transform quantum machine learning into a science that has real-world
impact, it is therefore crucial that we identify the features of quantum
models that make them a powerful paradigm for learning. Historically, this
power has often been viewed through the lens of quantum computation, and this
has led to a program of searching for quantum advantage in terms of asymptotic
complexity-theoretic analysis.

Whereas it is true that some form of computational hardness is required to go
beyond the capabilities of classical models, taking this perspective as a
starting point may be overly restrictive due to the general difficulty of
proving complexity-theoretic separations, and the highly specific and complex
mathematical structures they use. Our work offers a fresh perspective however:
perhaps an alternative way to view the value of quantum machine learning is
not in terms of computation, but through the ability to parameterise
expressive model classes that encode certain data structures. As we have
shown, contextuality offers an interesting perspective with which to view this
question, and has led us to a specific data structure that can be naturally
encoded in quantum models. In order to make further progress in this
direction, we believe that greater effort is needed to __

  1. i

_Identify mathematical structures that are characteristic of quantum theory
and understand how these connect to structures present in data;_

  2. ii

_Determine which of these structures are connected to non-classicality and
thus are likely to be difficult to emulate classically;_

  3. iii

_Understand the kinds of learning problem where these non-classical structures
plays a useful role._

The nascent field of geometric quantum machine learning [40, 41, 42]—the study
of encoding symmetry structures into quantum models—may be a useful framework
in which to tackle the first of these points. Other insights may also be
possible by borrowing ideas from the quantum foundations literature,
particularly for point (ii). For example, how does our framework of
contextuality (or extensions thereof) connect to the notion of invariance and
equivariance in geometric machine learning? What other common structures in
contextuality (such as Kochen-Specker sets [49] and antidistinguishability
[63]) can be connected to biases in data? Is the non-signalling multi-partite
structure of Bell nonlocality useful for learning certain data sets? Do
concepts in quantum foundations suggest how to build a non-classical ‘quantum
neuron’? Answers to these questions will generally not lead to statements of
quantum advantage in the language of complexity theory. What they reveal in
terms of understanding and intuition may however be valuable in the search for
practical uses for quantum machine learning models.

Perhaps the most pertinent question regarding this particular work is whether
the linearly conserved quantities we consider (for potentially larger label
dimension) can be usefully encoded in classical models using a tractable
amount of resources. The fact that neural networks are nonlinear functions of
the input data is actually problematic here, since it becomes difficult to
impose linear constraints on the nonlinear output variables [64]. The linear
structure of quantum theory is particularly useful however, as it provides a
model in which the output label probabilities are nonlinear in the input data,
but the linear bias is nevertheless enforced. Furthermore, classical mechanics
is already used as a framework to encode conserved quantities in continuous-
valued data [65, 66]. Since quantum theory can be seen as a generalisation of
classical mechanics that deals with discrete variables (quanta), this does
suggest that quantum theory is a very natural structure in which to encode
conserved quantities of discrete data.

##  11 Acknowledgements

We thank Richard East, Gillermo Alonso, Chae-Yeun Park and Flavien Hirsch for
useful discussions, and Evan Peters, Richard East and Korbinian Kottmann for
comments on the draft. This project has received funding from the European
Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreement No. 754510. VJW and MF acknowledge support
from the Government of Spain (FIS2020-TRANQI, Severo Ochoa CEX2019-000910-S),
Fundació Cellex, Fundació Mir-Puig and Generalitat de Catalunya (CERCA, AGAUR
SGR 1381).

## References

  * [1] Tom M Mitchell  “The need for biases in learning generalizations”  Department of Computer Science, Laboratory for Computer Science Research …, 1980
  * [2] Stuart Geman, Elie Bienenstock and René Doursat  “Neural networks and the bias/variance dilemma”  In _Neural computation_ 4.1 MIT Press One Rogers Street, Cambridge, MA 02142-1209, USA journals-info …, 1992, pp. 1–58
  * [3] Peter W Battaglia et al.  “Relational inductive biases, deep learning, and graph networks”  In _arXiv preprint arXiv:1806.01261_ , 2018
  * [4] Yann LeCun, Léon Bottou, Yoshua Bengio and Patrick Haffner  “Gradient-based learning applied to document recognition”  In _Proceedings of the IEEE_ 86.11 Ieee, 1998, pp. 2278–2324
  * [5] Keiron O’Shea and Ryan Nash  “An introduction to convolutional neural networks”  In _arXiv preprint arXiv:1511.08458_ , 2015
  * [6] Jiuxiang Gu et al.  “Recent advances in convolutional neural networks”  In _Pattern recognition_ 77 Elsevier, 2018, pp. 354–377
  * [7] Michael M Bronstein et al.  “Geometric deep learning: going beyond euclidean data”  In _IEEE Signal Processing Magazine_ 34.4 IEEE, 2017, pp. 18–42
  * [8] Jonas Kübler, Simon Buchholz and Bernhard Schölkopf  “The inductive bias of quantum kernels”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 12661–12673
  * [9] M Cerezo et al.  “Challenges and opportunities in quantum machine learning”  In _Nature Computational Science_ 2.9 Nature Publishing Group, 2022, pp. 567–576
  * [10] Abdulkadir Canatar et al.  “Bandwidth enables generalization in quantum kernel models”  In _arXiv preprint arXiv:2206.06686_ , 2022
  * [11] Franz J Schreiber, Jens Eisert and Johannes Jakob Meyer  “Classical surrogates for quantum learning models”  In _arXiv preprint arXiv:2206.11740_ , 2022
  * [12] Haoyuan Cai, Qi Ye and Dong-Ling Deng  “Sample Complexity of Learning Quantum Circuits”  In _arXiv preprint arXiv:2107.09078_ , 2021
  * [13] Marcel Hinsche et al.  “A single $T$-gate makes distribution learning hard”  In _arXiv preprint arXiv:2207.03140_ , 2022
  * [14] Yunchao Liu, Srinivasan Arunachalam and Kristan Temme  “A rigorous and robust quantum speed-up in supervised machine learning”  In _Nature Physics_ 17.9 Nature Publishing Group, 2021, pp. 1013–1017
  * [15] Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter and Jens Eisert  “On the quantum versus classical learnability of discrete distributions”  In _Quantum_ 5 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 417
  * [16] Niklas Pirnay, Ryan Sweke, Jens Eisert and Jean-Pierre Seifert  “A super-polynomial quantum-classical separation for density modelling”  In _arXiv preprint arXiv:2210.14936_ , 2022
  * [17] Casper Gyurik and Vedran Dunjko  “On establishing learning separations between classical and quantum machine learning with classical data”  In _arXiv preprint arXiv:2208.06339_ , 2022
  * [18] Costantino Budroni et al.  “Quantum contextuality”  In _arXiv preprint arXiv:2102.13036_ , 2021
  * [19] Adán Cabello, Simone Severini and Andreas Winter  “Graph-theoretic approach to quantum correlations”  In _Physical review letters_ 112.4 APS, 2014, pp. 040401
  * [20] Robert W Spekkens  “Contextuality for preparations, transformations, and unsharp measurements”  In _Physical Review A_ 71.5 APS, 2005, pp. 052108
  * [21] Mark Howard, Joel Wallman, Victor Veitch and Joseph Emerson  “Contextuality supplies the ‘magic’for quantum computation”  In _Nature_ 510.7505 Nature Publishing Group, 2014, pp. 351–355
  * [22] Robert Raussendorf  “Contextuality in measurement-based quantum computation”  In _Physical Review A_ 88.2 APS, 2013, pp. 022322
  * [23] Juan Bermejo-Vega et al.  “Contextuality as a resource for models of quantum computation with qubits”  In _Physical review letters_ 119.12 APS, 2017, pp. 120505
  * [24] Nicolas Delfosse, Philippe Allard Guerin, Jacob Bian and Robert Raussendorf  “Wigner function negativity and contextuality in quantum computation on rebits”  In _Physical Review X_ 5.2 APS, 2015, pp. 021003
  * [25] Shane Mansfield and Elham Kashefi  “Quantum advantage from sequential-transformation contextuality”  In _Physical review letters_ 121.23 APS, 2018, pp. 230401
  * [26] Markus Frembs, Sam Roberts, Earl T Campbell and Stephen D Bartlett  “Hierarchies of resources for measurement-based quantum computation”  In _arXiv preprint arXiv:2203.09965_ , 2022
  * [27] Farid Shahandeh  “Quantum computational advantage implies contextuality”  In _arXiv preprint arXiv:2112.00024_ , 2021
  * [28] Xun Gao et al.  “Enhancing generative models via quantum correlations”  In _Physical Review X_ 12.2 APS, 2022, pp. 021037
  * [29] Eric R Anschuetz, Hong-Ye Hu, Jin-Long Huang and Xun Gao  “Interpretable Quantum Advantage in Neural Sequence Learning”  In _arXiv preprint arXiv:2209.14353_ , 2022
  * [30] Victor Gitton and Mischa P Woods  “On the system loophole of generalized noncontextuality”  In _arXiv preprint arXiv:2209.04469_ , 2022
  * [31] Sebastian Ruder  “An overview of multi-task learning in deep neural networks”  In _arXiv preprint arXiv:1706.05098_ , 2017
  * [32] Chris Fifty et al.  “Efficiently identifying task groupings for multi-task learning”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 27503–27516
  * [33] Chun Kai Ling, Fei Fang and J Zico Kolter  “What game are we playing? end-to-end learning in normal and extensive form games”  In _arXiv preprint arXiv:1805.02777_ , 2018
  * [34] James P Bailey and Georgios Piliouras  “Multi-agent learning in network zero-sum games is a Hamiltonian system”  In _arXiv preprint arXiv:1903.01720_ , 2019
  * [35] Jaime Clark et al.  “Generalization of the Ehrenfest urn model to a complex network”  In _Physical Review E_ 92.1 APS, 2015, pp. 012103
  * [36] Nikolay K. Vitanov and Kaloyan N. Vitanov  “Statistical distributions connected to motion of substance in a channel of a network”  In _Physica A: Statistical Mechanics and its Applications_ 527.1 North-Holland, 2019, pp. 121174
  * [37] Zlatinka I Dimitrova  “Flows of Substances in Networks and Network Channels: Selected Results and Applications”  In _Entropy_ 24.10 MDPI, 2022, pp. 1485
  * [38] Laura Alessandretti et al.  “Evidence for a conserved quantity in human mobility”  In _Nature human behaviour_ 2.7 Nature Publishing Group, 2018, pp. 485–491
  * [39] Nikolay K Vitanov and Kaloyan N Vitanov  “On the Motion of Substance in a Channel of a Network and Human Migration”  In _Physica A: Statistical Mechanics and its Applications_ 490 Elsevier, 2018, pp. 1277–1294
  * [40] Michael Ragone et al.  “Representation theory for geometric quantum machine learning”  In _arXiv preprint arXiv:2210.07980_ , 2022
  * [41] Quynh T Nguyen et al.  “Theory for equivariant quantum neural networks”  In _arXiv preprint arXiv:2210.08566_ , 2022
  * [42] Johannes Jakob Meyer et al.  “Exploiting symmetry in variational quantum machine learning”  In _arXiv preprint arXiv:2205.06217_ , 2022
  * [43] Francisco Javier Gil Vidal and Dirk Oliver Theis  “Input redundancy for parameterized quantum circuits”  In _Frontiers in Physics_ 8 Frontiers Media SA, 2020, pp. 297
  * [44] Maria Schuld, Ryan Sweke and Johannes Jakob Meyer  “Effect of data encoding on the expressive power of variational quantum-machine-learning models”  In _Physical Review A_ 103.3 APS, 2021, pp. 032430
  * [45] Markus P Mueller and Andrew JP Garner  “Testing quantum theory with generalized noncontextuality”  In _arXiv preprint arXiv:2112.09719_ , 2021
  * [46] John H Selby et al.  “Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality”  In _arXiv preprint arXiv:2112.04521_ , 2021
  * [47] Lorenzo Catani et al.  “What is nonclassical about uncertainty relations?”  In _Physical Review Letters_ 129.24 APS, 2022, pp. 240401
  * [48] Matteo Lostaglio and Gabriel Senno  “Contextual advantage for state-dependent cloning”  In _Quantum_ 4 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2020, pp. 258
  * [49] Costantino Budroni et al.  “Kochen-Specker Contextuality”  In _arXiv preprint arXiv:2102.13036_ , 2021
  * [50] Victoria Wright and Máté Farkas  “An invertible map between Bell non-local and contextuality scenarios”  In _arXiv preprint arXiv:2211.12550_ , 2022
  * [51] Robert W Spekkens  “The ontological identity of empirical indiscernibles: Leibniz’s methodological principle and its significance in the work of Einstein”  In _arXiv preprint arXiv:1909.04628_ , 2019
  * [52] Ravi Kunjwal and Robert W Spekkens  “From the Kochen-Specker theorem to noncontextuality inequalities without assuming determinism”  In _Physical review letters_ 115.11 APS, 2015, pp. 110403
  * [53] David Schmid, Robert W Spekkens and Elie Wolfe  “All the noncontextuality inequalities for arbitrary prepare-and-measure experiments with respect to any fixed set of operational equivalences”  In _Physical Review A_ 97.6 APS, 2018, pp. 062103
  * [54] Anubhav Chaturvedi, Máté Farkas and Victoria J Wright  “Characterising and bounding the set of quantum behaviours in contextuality scenarios”  In _Quantum_ 5 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 484
  * [55] Marco Cerezo et al.  “Variational quantum algorithms”  In _Nature Reviews Physics_ 3.9 Nature Publishing Group, 2021, pp. 625–644
  * [56] Ingemar Bengtsson and Karol Życzkowski  “Geometry of quantum states: an introduction to quantum entanglement”  Cambridge university press, 2017
  * [57] Guillaume Verdon et al.  “Quantum Hamiltonian-based models and the variational quantum thermalizer algorithm”  In _arXiv preprint arXiv:1910.02071_ , 2019
  * [58] Jonathan Barrett  “Information processing in generalized probabilistic theories”  In _Physical Review A_ 75.3 APS, 2007, pp. 032304
  * [59] Markus Müller  “Probabilistic theories and reconstructions of quantum theory”  In _SciPost Physics Lecture Notes_ , 2021, pp. 028
  * [60] David Schmid et al.  “Characterization of noncontextuality in the framework of generalized probabilistic theories”  In _PRX Quantum_ 2.1 APS, 2021, pp. 010331
  * [61] Farid Shahandeh  “Contextuality of general probabilistic theories”  In _PRX Quantum_ 2.1 APS, 2021, pp. 010330
  * [62] Ludovico Lami, Daniel Goldwater and Gerardo Adesso  “A Post-Quantum Associative Memory”  In _arXiv preprint arXiv:2201.12305_ , 2022
  * [63] Matthew Leifer and Cristhiano Duarte  “Noncontextuality inequalities from antidistinguishability”  In _Physical Review A_ 101.6 APS, 2020, pp. 062113
  * [64] Anand Rangarajan et al.  “Expressing linear equality constraints in feedforward neural networks”  In _arXiv preprint arXiv:2211.04395_ , 2022
  * [65] Samuel Greydanus, Misko Dzamba and Jason Yosinski  “Hamiltonian neural networks”  In _Advances in neural information processing systems_ 32, 2019
  * [66] Miles Cranmer et al.  “Lagrangian neural networks”  In _arXiv preprint arXiv:2003.04630_ , 2020

##  Appendix A The problem with using the physical theory as an operational
scenario

The most common perspective on generalised contextuality is that it is a
property of a physical theory. This makes sense if your motivation is to
answer the question ‘is quantum theory contextual?’, however one runs into
problems if this perspective is carried over into potential definitions of
contextuality within machine learning where the focus is not on a specific
theory but on the capabilities of a learning model. To illustrate this issue,
consider the following two multi-task models, where we consider the domain
$D_{x}$ of possible inputs to be a finite.

  1. 1.

A quantum multi-task model where the preparations and effects correspond to
density matrices $\rho_{\boldsymbol{x}}$ and measurement operators $M_{y}^{k}$
acting on $\mathcal{H}_{d}$.

  2. 2.

A quantum multi-task model that simulates the above model exactly using
diagonal density matrices $\tilde{\rho}_{\boldsymbol{x}}$ and diagonal
measurement operators $\tilde{M}_{y}^{k}$ acting on $\mathcal{H}_{d^{\prime}}$
with $d^{\prime}\geq d$.

The second model always exists since any quantum model can be simulated with
enough classical resources, and this classical simulation can be encoded into
the computational basis states of a quantum system of larger dimension. In
particular, one can use the choice
$\tilde{\rho}_{\boldsymbol{x}}=\ket{i(\boldsymbol{x})}\bra{i(\boldsymbol{x})}$,
$i(\boldsymbol{x})\in\\{1,\cdots,|D_{x}|\\}$ (so that the inputs are uniquely
indexed by computational basis states), and
$\tilde{M}_{y}^{k}=\sum_{i}\text{tr}(\rho_{\boldsymbol{x}(i)}M_{y}^{k})\ket{i}\bra{i}$.
One finds
$\text{tr}(\tilde{\rho}_{\boldsymbol{x}}\tilde{M}_{y}^{k})=\text{tr}({\rho}_{\boldsymbol{x}}{M}_{y}^{k})$
as desired.

If one takes the perspective that the operational scenario should correspond
to the underlying theory (in this case, quantum theory), then one will arrive
at different conclusions regrading the contextuality of the above two models.
This is most easily seen by noting that there can be no preparation
equivalences in model 2, since any diagonal state has a unique decomposition
in terms of computational basis states. In the absence of preparation
equivalences it is impossible to have generalised contextuality, as can be
shown by constructing an explicit noncontextual ontological model where the
ontic space corresponds to the set of density matrices, i.e.
$\Lambda=\\{\rho\\}$, and the measurement response functions are given by the
Born rule. It follows that the model 2 can never exhibit contextuality,
whereas model 1 in principle can due to existing proofs of generalised
contextuality in finite dimensional quantum theory.

If we take the underlying physical theory to define the operational scenario
we are therefore forced to accept that our notion of contextuality should
depend on physical details that are entirely irrelevant for the actual
behaviour of the model. This is unreasonable in our opinion since it doesn’t
allow one to connect contextuality to the behaviour of the device; hence the
route we propose.

##  Appendix B Proof of Theorem 4.1 for $\eta=1$

Recall from that

$\displaystyle\boldsymbol{v}_{\boldsymbol{x}}=(\mathcal{P}_{\theta}^{1}(+1|\boldsymbol{x}),\mathcal{P}_{\theta}^{2}(+1|\boldsymbol{x}),\mathcal{P}_{\theta}^{3}(+1|\boldsymbol{x}))=(P(\textbf{E}^{1}_{+}|\textbf{S}_{\boldsymbol{x}}),P(\textbf{E}^{2}_{+}|\textbf{S}_{\boldsymbol{x}}),P(\textbf{E}^{3}_{+}|\textbf{S}_{\boldsymbol{x}}))$
(112)

and $V=\\{\boldsymbol{v}_{x}|\boldsymbol{x}\in D_{\boldsymbol{x}}\\}$. Since
we have $\eta=1$, $V$ contains the points

$\displaystyle\boldsymbol{v}_{1}=(1,0,\frac{1}{2}),\;\boldsymbol{v}_{2}=(0,1,\frac{1}{2}),\;\boldsymbol{v}_{3}=(\frac{1}{2},1,0),\;\boldsymbol{v}_{4}=(\frac{1}{2},0,1),\;\boldsymbol{v}_{5}=(0,\frac{1}{2},1),\;\boldsymbol{v}_{6}=(1,\frac{1}{2},0).$
(113)

It follows that there exist inputs $\boldsymbol{x}_{i}$ such that
$\boldsymbol{v}_{\boldsymbol{x}_{i}}=\boldsymbol{v}_{i}$. Since the vectors
$\boldsymbol{v}_{i}$ are extremal in the space of models that satisfy the
bias, any $\boldsymbol{v}_{x_{i}}$ can be written as a convex combination of
them. Thus, any preparation $\textbf{S}_{\boldsymbol{x}}$ is operationally
equivalent to a convex mixture of the six preparations
$\textbf{S}_{i}\equiv\textbf{S}_{x_{i}}$,

$\displaystyle\textbf{S}_{\boldsymbol{x}}\sim\sum_{i}p_{i}(\boldsymbol{x})\textbf{S}_{i}\quad\forall\boldsymbol{x}$
(114)

for some convex weights $p_{i}(\boldsymbol{x})$.

We now consider an ontological model of the operational scenario. Assuming
operational noncontextuality, the operational equivalence (43) implies

$\displaystyle\frac{1}{2}(\mu_{\textbf{S}_{1}}(\lambda)+\mu_{\textbf{S}_{2}}(\lambda))=\frac{1}{2}(\mu_{\textbf{S}_{3}}(\lambda)+\mu_{\textbf{S}_{4}}(\lambda))=\frac{1}{2}(\mu_{\textbf{S}_{5}}(\lambda)+\mu_{\textbf{S}_{6}}(\lambda))\quad\forall\lambda.$
(115)

Using

$\displaystyle\text{supp}\,\frac{1}{2}(\mu_{\textbf{S}_{i}}+\mu_{\textbf{S}_{j}})=\text{supp}\,\mu_{\textbf{S}_{i}}\cup\text{supp}\,\mu_{\textbf{S}_{j}}$
(116)

it follows from (115) that

$\displaystyle\text{supp}\,\mu_{\textbf{S}_{1}}\cup\text{supp}\,\mu_{\textbf{S}_{2}}=\text{supp}\,\mu_{\textbf{S}_{3}}\cup\text{supp}\,\mu_{\textbf{S}_{4}}=\text{supp}\,\mu_{\textbf{S}_{5}}\cup\text{supp}\,\mu_{\textbf{S}_{6}},$
(117)

where supp is the support of the ontic distribution; i.e. the set of $\lambda$
which have non-zero probability. The set of ontic states is the union of
possible ontic states for each strategy,

$\displaystyle\Lambda=\bigcup_{\boldsymbol{x}\in
D_{\boldsymbol{x}}}\text{supp}\,\mu_{\textbf{S}_{\boldsymbol{x}}}.$ (118)

From (114) it follows

$\displaystyle\text{supp}\,\mu_{\textbf{S}_{\boldsymbol{x}}}\subseteq\bigcup_{i}\text{supp}\,\mu_{\textbf{S}_{i}},$
(119)

and so from (117)

$\displaystyle\Lambda=\bigcup_{i}\text{supp}\,\mu_{\textbf{S}_{i}}=\text{supp}\,\mu_{\textbf{S}_{1}}\cup\text{supp}\,\mu_{\textbf{S}_{2}}=\text{supp}\,\mu_{\textbf{S}_{3}}\cup\text{supp}\,\mu_{\textbf{S}_{4}}=\text{supp}\,\mu_{\textbf{S}_{5}}\cup\text{supp}\,\mu_{\textbf{S}_{6}}.$
(120)

Next, consider the first elements of $\boldsymbol{v}_{1}$ and
$\boldsymbol{v}_{2}$. These imply

$\displaystyle P(\textbf{E}^{1}_{+}|\textbf{S}_{1})=1,\quad
P(\textbf{E}^{1}_{+}|\textbf{S}_{2})=0.$ (121)

Since

$\displaystyle\int_{\lambda\in\text{supp}\,\mu_{\textbf{S}_{1}}}\text{d}\lambda\,\mu_{\textbf{S}_{1}}(\lambda)=1$
(122)

if follows from

$\displaystyle
P(\textbf{E}^{1}_{+}|\textbf{S}_{1})=\int_{\lambda\in\text{supp}\,\mu_{\textbf{S}_{1}}}\text{d}\lambda\,\mu_{\textbf{S}_{1}}(\lambda)\xi_{\textbf{E}^{1}_{+}}(\lambda)=1$
(123)

that $\xi_{\textbf{E}^{1}_{+}}(\lambda)=1$ for
$\lambda\in\text{supp}\,\mu_{\textbf{S}_{1}}$. In a similar fashion

$\displaystyle