# Decorrelation with Conditional Normalizing Flows

Samuel Klein
University of Geneva
<EMAIL_ADDRESS>
&Tobias Golling
University of Geneva
<EMAIL_ADDRESS>

###### Abstract

The sensitivity of many physics analyses can be enhanced by constructing
discriminants that preferentially select signal events. Such discriminants
become much more useful if they are uncorrelated with a set of protected
attributes. In this paper we show that a normalizing flow conditioned on the
protected attributes can be used to find a decorrelated representation for any
discriminant. As a normalizing flow is invertible the separation power of the
resulting discriminant will be unchanged at any fixed value of the protected
attributes. We demonstrate the efficacy of our approach by building supervised
jet taggers that produce almost no sculpting in the mass distribution of the
background.

##  1 Introduction

To study particular signal processes many analyses in high energy physics
(HEP) will generate both signal and background samples using a simulator and
define a discriminant for preferentially selecting signal [1, 2, 3, 4, 5, 6].
Once a discriminant has been constructed it is used in an event selection to
create a signal enriched data sample. In a HEP analysis this selection will
only ever be one step in a chain of procedures. A common downstream task is
the study of the invariant mass spectrum, which is of interest because it
typically falls smoothly for the background but not the signal. The
discriminant is invariably correlated with the invariant mass and this
typically means the smooth background assumption is violated in the signal
enriched sample. Therefore the discriminant is required to satisfy smoothness
criteria with respect to the changes it induces in the mass distribution of
the background.

In this work we introduce a method that removes the mass correlation from a
discriminant after it has been constructed and leaves its separation power
unchanged at every mass value. This method can be used to decorrelate any
number of variables from any number of protected attributes and is
complementary to other decorrelation methods. We study supervised machine
learning models on a supervised task and demonstrate the proposed method
significantly improves the decorrelation performance of existing approaches.

##  2 Method

The method introduced here will be described as a procedure for decorrelating
discriminants, but it can be applied to decorrelate any set of variables from
any set of protected attributes, though this may come with a cost (App. A).
When combined with a machine learning model the methods we present can be seen
as additional layers that calibrate the output of the model to enforce uniform
background rejection as a function of the protected attributes.

### Existing approaches

Existing methods often perform decorrelation during the construction of the
discriminant. This can be done by minimizing a measure of the correlation
between the discriminant $s$ and the protected attributes $\boldsymbol{m}$
while training a machine learning model [7, 8, 9, 10]. The construction of
such a discriminant is performed by minimizing the expectation over some
objective function of the form

$\centering\mathcal{L}=\mathcal{L}_{\textrm{class}}(s_{\phi}(\boldsymbol{x}),y)+\alpha\mathcal{L}_{\textrm{decor}}(s_{\phi}(\boldsymbol{x}),\boldsymbol{m}),\@add@centering$
(1)

where $\phi$ parameterizes the discriminant and $y$ is the class label for the
sample described by features $\boldsymbol{x}$. Minimizing the loss function
$\mathcal{L}_{\textrm{class}}$ maximizes the utility of the discriminant while
minimizing $\mathcal{L}_{\textrm{decor}}$ reduces the correlation between
$\boldsymbol{m}$ and $s_{\phi}(\boldsymbol{x})$. The parameter $\alpha$
controls the relative contribution of each of the loss functions and is the
minimal additional parameter that can appear in such loss functions, though
more parameters can appear in $\mathcal{L}_{\textrm{decor}}$.

Decorrelation methods that use Eq. 1 require additional work when building the
discriminant. Both moment decomposition (MoDe) [8] and distance correlation
(DisCo) [7] methods have some small overhead in terms of training, but only
introduce the single hyper parameter $\alpha$ into the optimization. All of
these methods can be composed with the decorrelation method we propose. Other
approaches are detailed in App. B.

### Decorrelation with conditional normalizing flows

A normalizing flow [11] is an invertible map between two distributions – a
data distribution from which we have samples and a base distribution for which
we know the likelihood. A conditional normalizing flow $p_{\theta}$ can
approximate a data distribution $p_{D}(s(\boldsymbol{x})|\boldsymbol{m})$ by
defining a neural network $f_{\theta}(s(\boldsymbol{x}),\boldsymbol{m})$ that
is invertible given $\boldsymbol{m}$ and a base distribution $p$ that is
independent of $\boldsymbol{m}$. The model is fit to data by maximizing the
log-likelihood under the change of variables formula,

$\log p_{\theta}(s(\boldsymbol{x})|\boldsymbol{m})=\log
p(f_{\theta}(s(\boldsymbol{x}),\boldsymbol{m}))+\log\left|\det
J_{f_{\theta}}(s(\boldsymbol{x}),\boldsymbol{m})\right|,$ (2)

where $J_{f_{\theta}}$ is the Jacobian of $f_{\theta}$. If this function is
fit perfectly the distribution of
$f_{\theta}(s(\boldsymbol{x}),\boldsymbol{m})$ will be the same as $p$ and
therefore independent of the mass by definition. In this case
$f_{\theta}(s(\boldsymbol{x}),\boldsymbol{m})$ will be a decorrelated
representation of $s(\boldsymbol{x})$ with the same signal separation power as
$s(\boldsymbol{x})$ at every value of $\boldsymbol{m}$ and therefore
$f_{\theta}(s(\boldsymbol{x}),\boldsymbol{m})$ can be used in place of
$s(\boldsymbol{x})$.

In the case of discriminants the function $f_{\theta}$ is required to be
monotonically increasing to ensure the ordering remains unchanged at all
values of $\boldsymbol{m}$. In one dimension this condition can always be
explicitly enforced post training of a flow using reflections of $f_{\theta}$
about the center of $p$ as discussed in App. C. As $f_{\theta}$ is an
invertible transformation with positive slope, the discriminatory power of $s$
and $f_{\theta}$ will be the same for every value of $\boldsymbol{m}$.

### Decorrelation with quantile regression

Quantile regression [12] is the task of finding the quantiles of a given
distribution as a function of explanatory variables. Typically we know what
quantiles we want to use for a given discriminant before it is constructed
[13], and by learning these quantiles as a function of $\boldsymbol{m}$ we can
use the conditional quantiles to perform event selections such that the
distribution of $\boldsymbol{m}$ does not change. Regressing quantiles is
easier than training a conditional flow which has to learn the entire
conditional cumulative distribution function. The definition of quantiles was
recently generalised to greater than one dimension [14, 15] and for
decorrelating discriminants in more than one dimension this is the formulation
that should be used to preserve the ordering that makes the discriminant
useful. This is discussed further in App. D.

##  3 Experiments

In this section we will demonstrate the efficacy of the proposed method on a
supervised classification problem. The task is to separate multijet background
events from hadronically decaying boosted W bosons. The samples we use were
provided by Refs [7, 16] to emulate those used in an earlier ATLAS study on
mass decorrelation techniques [17]. The same set of ten jet substructure
variables as used in these studies were used as features to train the
classifier. Both signal and background were generated by Pythia at
$s=\sqrt{13}$ TeV with a detector simulated by Delphes. Jets are reconstructed
using FastJet [18, 19] and clustered using the anti-kt algorithm [20] with
$R=1.0$. Each jet is required to have transverse momentum $p_{T}\in[300,400]$
GeV and mass $m\in[50,300]$. For each jet ten substructure variables are
calculated and used as input to the machine learning classifiers, these
variables are the same as those used in previous studies of decorrelation [17,
8, 7]. The invariant mass distribution is shown in Fig. 1.

Figure 1: The invariant mass distribution for the background samples without
applying any selection.

For this task the invariant mass is the protected attribute $\boldsymbol{m}$.

### Model settings

For MoDe and DisCo models the discriminant is parameterized by a DNN with
three hidden layers with $64$ nodes in each hidden layer and Swish activations
[21] with a batch normalization layer after the first fully connected layer
and a sigmoid activation on the output. This is the same model as used in the
experiments of MoDe [8]. We also consider a more standard classifier with the
same structure but with ReLU activations [22] and no batch normalization, this
will be referred to as a vDNN. The training procedure of the classifiers used
in this paper is different to the trainings in the MoDe and DisCo papers and
leads to classifiers that are more difficult to decorrelate. In particular the
classifiers we use have the learning rate annealed to zero during training and
are trained without reweighting the $p_{T}$ distribution. However, the
decorrelation method developed here can be used with any training pipeline, in
particular on top of the output of publicly available code such as that
provided by DisCo [7], the result of this is shown in App. F. All conditional
normalizing flows are constructed with rational quadratic splines [23] and
trained on the background only. Further training details are provided in App.
E.

Figure 2: The AUC, background rejection and signal efficiency in bins of mass
for a vDNN and the discriminant constructed by a conditional normalizing flow
using the output of the vDNN (cf-vDNN). The binned rejection and efficiency
are calculated using a threshold on the mass inclusive discriminant that gives
$50\%$ signal efficiency. In the case of the vDNN some high mass bins do not
have enough statistics to calculate background rejection and signal efficiency
at an inclusive $50\%$ signal efficiency threshold.

### Signal separation

A conditional flow decorrelated vDNN model (cf-vDNN) has the same separation
power in bins of mass and modulates the background and signal mass
distributions less than a vDNN with no decorrelation as shown in Fig. 2. The
difference in background rejection for mass inclusive thresholds means that
the signal separation using these thresholds is different. This is reflected
in the mass inclusive AUC which is $0.90$ for a vDNN and $0.84$ for the cf-
vDNN. This is discussed further in App. G.

### Decorrelation

The output distribution of a vDNN classifier trained without decorrelation
changes significantly in different mass bins as shown in Fig. 3. In contrast
the cf-vDNN model has approximately the same distribution in all mass bins.
Using the vDNN output directly results in preferentially selecting samples in
a certain mass range, while the cf-vDNN output exhibits no such preference.

Figure 3:  The invariant mass distribution for the background samples without
applying any selection and a threshold rejecting $50\%$ of the signal for
different discriminants applied to the background (left) and the distribution
of the discriminant over QCD (background) samples for a vDNN (middle) and a
conditional flow trained on the vDNN output (cf-vDNN, right) in bins of the
mass.

To compare the conditional flow decorrelation to existing methods we study the
inverse of the Jensen-Shannon divergence $1/\mathrm{JSD}_{50}$ and background
rejection power (inverse false positive rate) $R_{50}$ at $50\%$ signal
efficiency. The $\mathrm{JSD}$ is computed between samples that pass and fail
the selection. These metrics are correlated in the regime of finite statistics
with an optimal trade off that can be estimated from data by applying random
selections with the same proportions defined by $R_{50}$, we will refer to
this optimal tradeoff as ideal.

In comparison to other explicit decorrelation methods, using a conditional
normalizing flow performs significantly better in terms of the trade off
between $1/\mathrm{JSD}_{50}$ and $R_{50}$ as shown in Fig. 4. The conditional
flow decorrelator applied to a model trained with MoDe [8] and DisCo [7]
decorrelation approaches the ideal limit. While the inclusive background
rejection power of the conditional flow decorrelated classifiers has
decreased, Fig. 4 shows that the background rejection in the signal
region111Defined to be centered on the signal peak and include $80\%$ of the
signal. has increased. This occurs because correlated classifiers are biased
towards accepting background in the signal region. With reduced inclusive
background rejection power the background estimation based on sideband fits is
expected to improve for conditional flow decorrelated models. In combination
with improved background rejection in the signal region, conditional flow
decorrelated classifiers should significantly improve the performance of
resonant searches.

A conditional normalizing flow can also be used to directly decorrelate the
input features to find a new representation on which a DNN classifier (DNN cf-
inputs) can be trained (App. H). As this decorrelation is performed on all of
the input variables directly some correlation with the mass remains in the
classifier output, this is why the performance improves when training another
conditional normalizing flow on the resulting discriminant as seen in Fig. 4.

The Disco and MoDe classifiers are trained with $\alpha=0,25,50,...,300$, with
each point in Fig. 4 indexing an $\alpha$ which increases from right to left.
The simpler vDNN classifier is easier to decorrelate than the classifier used
with DisCo and Mode without decorrelation ($\alpha=0$). The improved
performance of the DisCo and MoDe models as $\alpha$ increases demonstrates
the utility of combining conditional normalizing flow decorrelation with
explicit decorrelation during training. Without decorrelation during training
it is possible that the classifier discriminant becomes overly complex and the
conditional flow would need significant resources to decorrelate the
discriminant.

Searching the space of architectures for a point that is easy to decorrelate
is much more complicated than choosing the single parameter $\alpha$ to use in
MoDe [8] and DisCo [7]. The conditional flow clearly improves upon the
performance of these models while reducing the need to fine tune the value of
$\alpha$. It is also possible that further development in training conditional
normalizing flows will remove the need for explicit decorrelation during the
training of the classifier.

Figure 4:  The inclusive background rejection at $50\%$ signal efficiency
($R_{50}$) and the inverse of the Jensen-Shannon divergence between the mass
distribution of events that do and do not pass the cut at the same threshold
($1/\mathrm{JSD}_{50}$) in the left plot. The background rejection in the mass
window $[70-100]$ GeV at $50\%$ inclusive signal efficiency
($R_{50}^{70-100}$) and the inverse Jensen-Shannon divergence in the same mass
bin ($1/\mathrm{JSD}_{50}^{70-100}$). The filled circles denote a discriminant
constructed using a conditional normalizing flow. The shaded bands capture the
maximum and minimum across ten different trainings. Models with the cf prefix
have been decorrelated with a conditional normalizing flow.

Quantile regression cannot be added to Fig. 4 because the quantiles are
trained on the background only and so no threshold can be found for $50\%$
signal efficiency. However, an additional benefit of both conditional
normalizing flows and quantile regression is their improved behaviour at
higher levels of background rejection as shown in Fig. 5. Here, even though
the quantile regression does not accurately predict the quantile thresholds,
the resulting discriminant is still decorrelated from the mass. Due to the
discontinuous nature of the quantiles, and the poor quantile predictions, it
is hard to consistently quantify the decorrelation performance of quantile
regression across runs. The JSD is calculated between the mass distribution
over the background after applying the classifier threshold and a random
sample from the background with the same number of points as passed the
classifier threshold. An ideal upper bound on the JSD is calculated by
randomly sampling from the mass distribution without replacement.

Figure 5: The performance of a DisCo trained classifier with $\alpha=200$ and
both quantile regression (qr-DisCo) and a flow decorrelated output at
$50,90,95,99\%$ background rejection. Error bars capture the maximum and
minimum across ten different runs on the same DisCo trained classifier.

##  4 Conclusion

In this paper we presented a novel method for performing decorrelation using
conditional normalizing flows. The approaches we developed were benchmarked
against other state of the art methods in a supervised setting and can be seen
to perform well in conjunction with these approaches where the conditional
flow reduces the hyper parameter optimization burden while improving the
decorrelation performance. The approach we develop can also be applied to
unsupervised settings and it was shown to be successful for decorrelating
variables other than discriminants by building mass decorrelated feature
representations (cf-inputs). The approach we develop could be particularly
useful in anomaly detection settings which rely on decorrelation [24, 25]. The
approach we develop can also be applied outside of the high energy physics
domain to data anonymity and fairness.

While the method we propose can be seen to be effective here, there is no
explicit smoothness enforced on the distribution of the mass after applying a
conditional normalizing flow. There is evidence that conditional normalizing
flows do implicitly impose some kind of smoothness criteria [26, 27, 28], but
explicitly enforcing this could significantly improve the performance of
conditional flow decorrelation and further work in this direction would be
worthwhile. Conditional normalizing flows for decorrelation is a promising
direction for allowing state of the art machine learning methods to be applied
to high energy physics analyses.

Both quantile regression and conditional normalizing flows can be used to
decorrelate discriminants, with quantile regression providing a fast
alternative that still significantly reduces the amount of mass sculpting,
even in the situation where it does not learn the correct quantiles. Both of
these approaches can in theory perform perfect decorrelation, however this can
be difficult to achieve in practice if the correlations between the variable
of interest and the protected attributes is very strong. In practice it
appears that some level of decorrelation during the construction of the
discriminant is desireable to ensure the conditional distribution can be
accurately modelled by the flow.

All code is publicly available at https://github.com/sambklein/dequantile.

## Acknowledgements

The authors would like to acknowledge funding through the SNSF Sinergia grant
called Robust Deep Density Models for High-Energy Particle Physics and Solar
Flare Analysis (RODEM) with funding number CRSII$5\\_193716$. We would also
like to thank Benjamin Nachman, David Shih and Gregor Kasieczka for useful
feedback on the manuscript and John Andrew Raine for useful discussions and
feedback on the manuscript.

## References

  * Baldi et al. [2014] Pierre Baldi, Peter Sadowski, and Daniel Whiteson.  Searching for exotic particles in high-energy physics with deep learning.  _Nature communications_ , 5(1):1–9, 2014.
  * de Oliveira et al. [2016] Luke de Oliveira, Michael Kagan, Lester Mackey, Benjamin Nachman, and Ariel Schwartzman.  Jet-images—deep learning edition.  _Journal of High Energy Physics_ , 2016(7):1–32, 2016.
  * CMS collaboration [2017] CMS collaboration.  Identification of heavy-flavour jets with the cms detector in pp collisions at 13 tev.  _arXiv preprint arXiv:1712.07158_ , 2017.
  * Butter et al. [2018] Anja Butter, Gregor Kasieczka, Tilman Plehn, and Michael Russell.  Deep-learned top tagging with a lorentz layer.  _SciPost Physics_ , 5(3):028, 2018.
  * Moreno et al. [2020] Eric A Moreno, Thong Q Nguyen, Jean-Roch Vlimant, Olmo Cerri, Harvey B Newman, Avikar Periwal, Maria Spiropulu, Javier M Duarte, and Maurizio Pierini.  Interaction networks for the identification of boosted h→ b b decays.  _Physical Review D_ , 102(1):012010, 2020.
  * ATL [2017] Quark versus Gluon Jet Tagging Using Jet Images with the ATLAS Detector.  Technical report, CERN, Geneva, Jul 2017.  URL http://cds.cern.ch/record/2275641.
  * Kasieczka and Shih [2020a] Gregor Kasieczka and David Shih.  Robust jet classifiers through distance correlation.  _Physical Review Letters_ , 125(12), sep 2020a.  doi: 10.1103/physrevlett.125.122001.  URL https://doi.org/10.1103%2Fphysrevlett.125.122001.
  * Kitouni et al. [2021] Ouail Kitouni, Benjamin Nachman, Constantin Weisser, and Mike Williams.  Enhancing searches for resonances with machine learning and moment decomposition.  _Journal of High Energy Physics_ , 2021(4), apr 2021.  doi: 10.1007/jhep04(2021)070.  URL https://doi.org/10.1007%2Fjhep04%282021%29070.
  * Shimmin et al. [2017] Chase Shimmin, Peter Sadowski, Pierre Baldi, Edison Weik, Daniel Whiteson, Edward Goul, and Andreas Søgaard.  Decorrelated jet substructure tagging using adversarial neural networks.  _Physical Review D_ , 96(7), oct 2017.  doi: 10.1103/physrevd.96.074034.  URL https://doi.org/10.1103%2Fphysrevd.96.074034.
  * Louppe et al. [2016] Gilles Louppe, Michael Kagan, and Kyle Cranmer.  Learning to pivot with adversarial networks.  2016\.  doi: 10.48550/ARXIV.1611.01046.  URL https://arxiv.org/abs/1611.01046.
  * Tabak and Turner [2013] E. G. Tabak and Cristina V. Turner.  A family of nonparametric density estimation algorithms.  _Communications on Pure and Applied Mathematics_ , 66(2):145–164, 2013.  doi: https://doi.org/10.1002/cpa.21423.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.21423.
  * Koenker and Bassett [1978] Roger Koenker and Gilbert Bassett.  Regression quantiles.  _Econometrica_ , 46(1):33–50, 1978.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/1913643.
  * ATLAS collaboration [2020] ATLAS collaboration.  Dijet resonance search with weak supervision using $\sqrt{s}=13$ tev pp collisions in the atlas detector.  _Physical review letters_ , 125(13):131801, 2020\.
  * Carlier et al. [2020] Guillaume Carlier, Victor Chernozhukov, Gwendoline De Bie, and Alfred Galichon.  Vector quantile regression and optimal transport, from theory to numerics.  _Empirical Economics_ , 62(1):35–62, aug 2020\.  doi: 10.1007/s00181-020-01919-y.  URL https://doi.org/10.1007%2Fs00181-020-01919-y.
  * Chernozhukov et al. [2017] Victor Chernozhukov, Alfred Galichon, Marc Hallin, and Marc Henry.  Monge–kantorovich depth, quantiles, ranks and signs.  _The Annals of Statistics_ , 45(1):223–256, 2017\.
  * Kasieczka and Shih [2020b] Gregor Kasieczka and David Shih.  Datasets for boosted w tagging, January 2020b.  URL https://doi.org/10.5281/zenodo.3606767.
  * ATL [2018] Performance of mass-decorrelated jet substructure observables for hadronic two-body decay tagging in ATLAS.  Technical report, CERN, Geneva, Jul 2018.  URL https://cds.cern.ch/record/2630973.
  * Cacciari et al. [2012] Matteo Cacciari, Gavin P Salam, and Gregory Soyez.  Fastjet user manual.  _The European Physical Journal C_ , 72(3):1–54, 2012.
  * Cacciari and Salam [2006] Matteo Cacciari and Gavin P Salam.  Dispelling the n3 myth for the kt jet-finder.  _Physics Letters B_ , 641(1):57–61, 2006.
  * Cacciari et al. [2008] Matteo Cacciari, Gavin P Salam, and Gregory Soyez.  The anti-kt jet clustering algorithm.  _Journal of High Energy Physics_ , 2008(04):063, 2008.
  * Ramachandran et al. [2017] Prajit Ramachandran, Barret Zoph, and Quoc V Le.  Searching for activation functions.  _arXiv preprint arXiv:1710.05941_ , 2017.
  * Fukushima [1975] Kunihiko Fukushima.  Cognitron: A self-organizing multilayered neural network.  _Biological Cybernetics_ , 20(3):121–136, 1975\.  doi: 10.1007/BF00342633.  URL https://doi.org/10.1007/BF00342633.
  * Durkan et al. [2019] Conor Durkan, Artur Bekasov, Iain Murray, and George Papamakarios.  Neural spline flows.  _Advances in neural information processing systems_ , 32, 2019.
  * Kamenik and Szewc [2022] Jernej F Kamenik and Manuel Szewc.  Null hypothesis test for anomaly detection.  _arXiv preprint arXiv:2210.02226_ , 2022.
  * Kasieczka et al. [2021] Gregor Kasieczka, Benjamin Nachman, Matthew D. Schwartz, and David Shih.  Automating the abcd method with machine learning.  _Phys. Rev. D_ , 103:035021, Feb 2021.  doi: 10.1103/PhysRevD.103.035021.  URL https://link.aps.org/doi/10.1103/PhysRevD.103.035021.
  * Hallin et al. [2021] Anna Hallin, Joshua Isaacson, Gregor Kasieczka, Claudius Krause, Benjamin Nachman, Tobias Quadfasel, Matthias Schlaffer, David Shih, and Manuel Sommerhalder.  Classifying anomalies through outer density estimation (cathode).  _arXiv preprint arXiv:2109.00546_ , 2021.
  * Raine et al. [2022] John Andrew Raine, Samuel Klein, Debajyoti Sengupta, and Tobias Golling.  Curtains for your sliding window: Constructing unobserved regions by transforming adjacent intervals, 2022.  URL https://arxiv.org/abs/2203.09470.
  * Klein et al. [2022] Samuel Klein, John Andrew Raine, and Tobias Golling.  Flows for flows: Training normalizing flows between arbitrary distributions with maximum likelihood estimation, 2022.  URL https://arxiv.org/abs/2211.02487.
  * Dolen et al. [2016] James Dolen, Philip Harris, Simone Marzani, Salvatore Rappoccio, and Nhan Tran.  Thinking outside the ROCs: Designing decorrelated taggers (DDT) for jet substructure.  _Journal of High Energy Physics_ , 2016(5), may 2016.  doi: 10.1007/jhep05(2016)156.  URL https://doi.org/10.1007%2Fjhep05%282016%29156.
  * Dudani [1976] Sahibsingh A. Dudani.  The distance-weighted k-nearest-neighbor rule.  _IEEE Transactions on Systems, Man, and Cybernetics_ , SMC-6(4):325–327, 1976.  doi: 10.1109/TSMC.1976.5408784.
  * Huang et al. [2020] Chin-Wei Huang, Ricky T. Q. Chen, Christos Tsirigotis, and Aaron Courville.  Convex potential flows: Universal probability distributions with optimal transport and convex optimization, 2020.  URL https://arxiv.org/abs/2012.05942.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Loshchilov and Hutter [2016] Ilya Loshchilov and Frank Hutter.  Sgdr: Stochastic gradient descent with warm restarts.  _arXiv preprint arXiv:1608.03983_ , 2016.
  * Durkan et al. [2020] Conor Durkan, Artur Bekasov, Iain Murray, and George Papamakarios.  nflows: normalizing flows in PyTorch, November 2020.  URL https://doi.org/10.5281/zenodo.4296287.
  * Koenker [2005] Roger Koenker.  _Quantile Regression_.  Econometric Society Monographs. Cambridge University Press, 2005.  doi: 10.1017/CBO9780511754098.
  * Koenker and Hallock [2001] Roger Koenker and Kevin F. Hallock.  Quantile regression.  _Journal of Economic Perspectives_ , 15(4):143–156, December 2001.  doi: 10.1257/jep.15.4.143.  URL https://www.aeaweb.org/articles?id=10.1257/jep.15.4.143.
  * Hallin et al. [2022] Anna Hallin, Gregor Kasieczka, Tobias Quadfasel, David Shih, and Manuel Sommerhalder.  Resonant anomaly detection without background sculpting, 2022.  URL https://arxiv.org/abs/2210.14924.

##  Appendix A Task agnostic decorrelation

Normalizing flows can be used to find a decorrelated representation of generic
variables from generic conditions. However, this can come at a price in terms
of performance on a given task, in particular if the decorrelation is task
agnostic. To illustrate this consider a dataset with a binary conditional
variable $m=\\{0,1\\}$ and a single scalar $x$ that is intended to be used to
be used to discriminate signal from background. In this dummy example we take

$\displaystyle p_{\mathrm{signal}}(x|m=0)=\mathcal{N}(2,0.3)~{}~{}~{}~{}$
$\displaystyle~{}~{}~{}~{}p_{\mathrm{signal}}(x|m=1)=\mathcal{N}(-12,0.3),$
$\displaystyle p_{\mathrm{background}}(x|m=0)=\mathcal{N}(0,1)~{}~{}~{}~{}$
$\displaystyle~{}~{}~{}~{}p_{\mathrm{background}}(x|m=1)=\mathcal{N}(-10,1),$

as illustrated in Fig. 6.

Figure 6: A dummy dataset for illustrating possible pathologies with task
agnostic decorrelation.

There are two invertible functions that could decorrelate the background in
this setting. These functions can be defined piecewise as

$\displaystyle f_{1}(x,m)$ $\displaystyle=\begin{cases}x&m=0\\\
x+10&m=1\end{cases}$ $\displaystyle f_{2}(x,m)$
$\displaystyle=\begin{cases}x&m=0\\\ -x-10&m=1.\end{cases}$

Where the two functions both produce a representation of the data such that
the background is perfectly perfectly decorrelated from the feature $m$.
However, the two representations are not equivalent for separating signal from
background. Given that we know the likelihoods of the data we can directly
construct the likelihood ratio between the signal and background which is the
optimal test statistic in this setting as stated by the Neyman-Pearson lemma.
The separation of each of the possible representations is shown in Fig. 7
where the area under the receiver operating characteristic is also calculated
to quantify the separation performance of each of the representations of the
data. We observe that the function $f_{1}$ has a significantly reduced signal
discrimination power due to the increased mixing of signal and background at
different mass values.

Figure 7: The joint distributions of each of the possible decorrelated
representations.

In general task agnostic decorrelation leads to many degenerate solutions with
different performance on the proposed task. A simple approach to this dilemma
is to first construct a network to perform a given task and then decorrelate.
An alternative would be to define a class conditional base distribution such
that the representation $f_{\theta(\boldsymbol{m})}(\boldsymbol{x})$ is still
class independent but the signal is always clustered in the representation and
the previous degeneracy is removed. Such a representation could be used by
maximizing

$\log p_{\theta}(\boldsymbol{x}|\boldsymbol{m},c)=\log
p(f_{\theta(\boldsymbol{m})}(\boldsymbol{x})|c)+\log\left|\det
J_{f_{\theta(\boldsymbol{m})}}(\boldsymbol{x})\right|.$

##  Appendix B Existing approaches

Designed decorrelated taggers (DDTs) [29] apply a handcrafted linear
transformation to the discriminant to ensure decorrelation. A generalization
of this to non-linear dependence on $\boldsymbol{m}$ is given by fixed
efficiency regression where the expected response for background examples is
subtracted from each value of the discriminant [17] with the expected response
estimated using k-nearest neighbors [30]. By subtracting the expected value of
$s$ this method does not account for the different shape of $s$ as a function
of $\boldsymbol{m}$ and is therefore only decorrelated when rejecting $50\%$
of the background. These approaches are similar to what we propose in that
they are invertible, but we consider decorrelation from a more general
perspective and account for the shape of the distribution of $s$ at all values
of $\boldsymbol{m}$ as well as providing a procedure that can be extended to
higher dimensions, many variables in $\boldsymbol{m}$ and highly non-linear
dependence between $s$ and $\boldsymbol{m}$.

##  Appendix C Monotonically increasing flows

Normalizing flows are by definition monotonic and in one dimension it is easy
to test if they have positive slope at any value of the condition $m$ by
encoding two points $x_{0},x_{1}$ such that $x_{0}<x_{1}$ and ensuring
$f_{\theta}(x_{0},m)<f_{\theta}(x_{1},m)$. If a base density that is symmetric
about its mean $c$ is used to train the flow then a point $x^{*}$ that does
not satisfy this condition can be forced to transform under some function with
positive slope by applying the transformation $x^{*}=-f_{\theta}(x^{*},m)+2c$.
As normalizing flows typically use a base density that is symmetric about the
mean this restriction does not impose strong constraints on the flows
flexibility.

##  Appendix D Decorrelation with quantile regression.

Quantile regression [12] is the task of finding the quantiles of a given
distribution as a function of explanatory variables. When the base
distribution $p$ of a normalizing flow is taken to be the uniform distribution
on $[0,1]$ and $f_{\theta}$ is restricted to being monotonically increasing
then $f_{\theta}^{-1}$ will be the quantile function. However, a normalizing
flow must learn all quantiles simultaneously, while quantile regression
targets the simpler task of learning prescribed intervals. Typically we know
what quantiles we want to use for a given discriminant before it is
constructed, and by learning these quantiles as a function of $\boldsymbol{m}$
we can use the conditional quantiles to perform event selections such that the
distribution of $\boldsymbol{m}$ does not change. Quantile regression is
useful in the case of discriminants, but it is not a general tool for
decorrelation as only the predefined quantiles will be decorrelated from the
data. Given the conditional quantiles a spline approximation to the quantile
function can be constructed, but this is not explored here as a normalizing
flow learns this function directly.

The definition of quantiles was recently generalised to greater than one
dimension [14, 15] with a fast non-linear method now available [15]. A
normalizing flow can be used to learn the higher dimensional quantile function
if $f_{\theta}$ is defined to be the gradient of a complex potential as has
been developed by convex potential flows [31]. For decorrelating discriminants
in more than one dimension this is the formulation that should be used to
preserve the ordering that makes the discriminant useful.

##  Appendix E Model settings

The classifiers are trained for $100$ epochs using the Adam optimizer [32]
with an initial learning rate of $0.001$ annealed to zero following a cosine
schedule [33]. All classifiers are trained using binary cross entropy for
$\mathcal{L}_{\textrm{class}}$. Following the prescriptions of the respective
papers, models trained with MoDe decorrelation use a batch size of $2^{14}$
and $2048$ for DisCo models. The vDNN uses a batch size of $256$.

The conditional normalizing flow used to decorrelate discriminants are
parameterized by three rational quadratic spline layers [23] with $8$ bins in
each layer and the knot placements parameterized by two residual blocks with
$64$ hidden nodes as implemented in the nflows library [34]. The base
distribution is chosen to be uniform with support on $[0,1]$. The quantiles
are regressed using the pinball loss [35, 36] where the quantiles are
predicted using a DNN with three hidden layers with $64$ nodes. Both quantile
regressors and normalizing flows are trained using the same set up as the
vDNN. The conditional normalizing flow decorrelator is trained on the
background only.

A conditional normalizing flow will also be used to decorrelate the input
features directly. This flow is constructed from four autoregressive rational
quadratic spline flow layers [23] with $10$ bins in each layer and two
residual blocks with $64$ nodes per layer to learn the knot placements. The
base density is standard normal distribution and a tail bound of $3$ was used.

The hyperparameters specified here were not tuned in any way and classifier
architectures were copied from existing papers. The predefined training,
testing and validation data sets were used.

For all experiments ten models with different random seeds were trained.
Training a single model comprises training a classifier, a flow and a quantile
regressor. All experiments ran for $<2.5$ hours on a single Nvidia RTX $3090$
GPU card.

##  Appendix F DisCo

The training procedure used in the original DisCo paper is more optimised than
the classifiers trained with DisCo shown in the body of this work. The code
used to produce the results of the DisCo classifier as trained in Ref. [7] is
publicly available at https://github.com/davidshih17/DisCo. Training
classifiers using this framework and saving the predictions on the training,
validation and test sets allows a conditional normalizing flow to be trained
on these predictions. The result of this procedure, evaluated in the same
manner as in the body of this work, can be seen in Fig. 8. This demonstrates
the utility of optimising the classifier training further to improve the
performance of the conditional flow decorrelation. While the classifier
trained on a decorrelated representation of the features (DNN (cf-inputs))
slightly outperforms the DisCo trained classifiers in this setting the
conditional flow decorrelated DisCo is significantly better and doesn’t rely
on a complex flow model for decorrelating the input features.

Figure 8: The performance of a DisCo classifier using the training pipeline of
Ref. [7] and a flow decorrelated output trained on top of this model’s
prediction (cf-DisCo).

##  Appendix G Signal separation

The separation performance of a given discriminant can be quantified by
various different metrics $f_{s}$. In all cases the mass unconditional values
of these metrics is easy to calculate, but as we are assuming that resonant
physics will be localised in the resonant variable, this does not measure how
useful the discriminant will be for a bump hunt. An alternative approach would
be to consider the metrics as a function of the mass $f_{s}(m)$ and calculate
the expected value of the metric
$p_{f_{s}}=\mathbb{E}_{p(m)}\left[f_{s}(m)\right]$ for some mass distribution
$p(m)$. This expectation can be taken with respect to the signal mass
distribution and produce a score that is weighted towards mass regions with
large signal densities.

A particular example of this is shown in Fig. 2 for the area under the
receiver operator curve (AUC). In bins of mass the AUC is the same for a vDNN
and a conditional flow deccorelated vDNN (cf-vDNN), while the mass inclusive
AUC for a vDNN is $0.90$ and $0.84$ for the cf-vDNN. The difference in these
AUC values is due to the different levels of mass sculpting. Small thresholds
on the vDNN discriminant will reject both background and signal events at high
mass values where there is very little signal, while the cf-vDNN rejects
background uniformly across the mass spectrum. In contrast to the mass unaware
AUCs the expected AUC over the signal mass distribution is $0.84$ for both the
DNN and cf-DNN. The uneven background rejection of the DNN is clearly
reflected in the binned background rejection power $R_{50}$ and signal
rejection at $50\%$ signal rejection.

##  Appendix H Decorrelating the input features

Given a set of features $\boldsymbol{x}$ that are conditionally dependent on
$\boldsymbol{m}$ a decorrelated representation
$f_{\phi}(\boldsymbol{x}|\boldsymbol{m})$ of $\boldsymbol{x}$ can be found by
replacing $s(\boldsymbol{x})$ in Eq. 2 with $\boldsymbol{x}$. As described in
App. A this will inevitably lead to a reduction of the performance of the
classifier, which is empirically reinforced in Fig. 4 where the cf-inputs
model has been trained on a mass decorrelated representation of the input
features. This approach provides a generic perspective on Ref. [37] which
focusses on anomaly detection and also observes a drop in performance when
using a decorrelated representation.

##  Appendix I Extended discussion

An additional benefit of both conditional normalizing flows and quantile
regression is their improved behaviour at higher levels of background
rejection as shown in Fig. 9. As can be seen in this plot, even though the
quantile regression does not correctly predict the quantile thresholds, the
resulting discriminant is still decorrelated from the mass. Due to the
discontinuous nature of the quantiles, and the poor quantile predictions, it
is hard to consistently quantify the decorrelation performance of quantile
regression across runs.

Figure 9: The mass distribution for different levels of rejection as defined
by the thresholds of the quantile regression, which regressed the
$50,90,95,99$th quantiles. The mass distribution after applying cuts from a
classifier trained with DisCo decorrelation ($\alpha=200$) and corrected with
a conditional normalizing flow (cf-DisCo) and conditional quantile regression
(qr-DisCo). Random bounds are defined by sampling the same number of
statistics randomly $100$ times per threshold.

For the model in Fig. 9 we can see that both the conditional flow decorrelated
output and the quantile regressor perform very well at decorrelating a
classifier trained with DisCo decorrelation across several cuts in Fig. 5. The
JSD is calculated between the mass distribution over the background after
applying the classifier threshold and a random sample from the background with
the same number of points as passed the classifier threshold. An ideal upper
bound on the JSD is calculated by randomly sampling from the mass distribution
without replacement. Errors are estimated by calculating the JSD $10$ times.


# When Redundancy Matters:
Machine Teaching of Representations111This project is supported by NRC project
(329745) Machine Teaching for Explainable AI

Cèsar Ferri  VRAIN, Universitat Politècnica de València, València, Spain
Dario Garigliotti  Department of Informatics, University of Bergen, Norway
Brigt Arve Toppe Håvardstun  Department of Informatics, University of Bergen,
Norway  Josè Hernández-Orallo  VRAIN, Universitat Politècnica de València,
València, Spain  Jan Arne Telle  Department of Informatics, University of
Bergen, Norway

(June 2023)

###### Abstract

In traditional machine teaching, a teacher wants to teach a concept to a
learner, by means of a finite set of examples, the witness set. But concepts
can have many equivalent representations. This redundancy strongly affects the
search space, to the extent that teacher and learner may not be able to easily
determine the equivalence class of each representation. In this common
situation, instead of teaching concepts, we explore the idea of teaching
representations. We work with several teaching schemas that exploit
representation and witness size (Eager, Greedy and Optimal) and analyze the
gains in teaching effectiveness for some representational languages (DNF
expressions and Turing-complete P3 programs). Our theoretical and experimental
results indicate that there are various types of redundancy, handled better by
the Greedy schema introduced here than by the Eager schema, although both can
be arbitrarily far away from the Optimal. For P3 programs we found that
witness sets are usually smaller than the programs they identify, which is an
illuminating justification of why machine teaching from examples makes sense
at all.

##  1 Introduction

In formal models of _machine learning_ we have a concept class $C$ of possible
hypotheses, an unknown target concept $c^{*}\in C$ and training data given by
correctly labelled random examples. In formal models of machine teaching a
collection of labelled examples, a witness set $w$, is instead carefully
chosen by a teacher $T$, i.e., $w=T(c^{*})$, so the learner can reconstruct
$c^{*}$, i.e., $c^{*}=L(w)$. In recent years, the field of machine teaching
has seen various applications in fields like pedagogy [15], trustworthy AI
[20] and explainable AI [18, 12].

In reality, concepts are expressed in a representational language, and most
languages have redundancy, with several representations mapping to the same
concept; this is one common kind of language bias. For some languages, teacher
and learner may not know whether two representations are equivalent —it may
not even be computable. Because of this, we may end up teaching more than one
representation of a concept. For example, the ‘powers of 2’, the ‘number of
subsets of an $n$-element set’, and the ‘number of $n$-bit binary strings’,
all denote the same subset of natural numbers, but teacher and learner may not
know they fall in the same equivalence class.

This situation is common in most languages with which humans and machines
represent concepts, from natural languages to artificial neural networks.
Consequently, studying how this relation between representations and concepts
affects teaching has important implications not only for teaching, but also in
machine learning in general (see, e.g., Hadley et al. [11]), where the notions
of syntactic, semantic and search bias (any language bias) are explored to
make a language more suitable for learning than another (see e.g., Muggleton
and De Raedt [13], Whigham [17], Nédellec et al. [14]). The issue is important
in any area of AI where there is a non-injective correspondence from concepts
to representations, such as explainable AI. Several notions of redundancy,
density or compactness in semantics, syntax or representations have been
studied in the literature [19, 5, 1], but they do not focus on quantifying
redundancy or concentration over the equivalence classes, as we define them in
this paper.

We explore the idea of teaching representations, where the teacher has a
representation in mind and wants the learner to identify it. Different
representations $r_{1}$ and $r_{2}$ can be in the same equivalence class, a
concept $c$, denoted by $[r_{1}]=[r_{2}]=c$. We model this much as in the
traditional concept teaching scenario, but now by a set of representations $R$
expressed in a language, and the teacher $T:R\rightarrow W$ being a partial
injective mapping of representations to witnesses. We do not require the
mapping to be total to accommodate, e.g., the case $|R|>|W|$. As in the
classical concept teaching setting, we assume the learner is able to check the
consistency between a representation and a given witness.

We assume the learner has simplicity functions on the set of representations
and on witnesses. A similar assumption appears in various models of machine
teaching, e.g., the Preference-Based teaching model assumes an ordering on
concepts and the Recursive teaching model assumes a partial ordering on
witnesses. Furthermore, in the teacher/learner algorithm of [16], which we
call Eager, the learner employs an ordering on concepts called the learning
prior while the teacher wants to minimize the ‘teaching size’, which
implicitly sets an order on witnesses. In the Eager algorithm, the learner,
when given a witness, will employ Occam’s razor and guess the simplest
consistent representation, and the teacher will always provide the smallest
witness that suffices to learn the target representation. Note this implies
the learner will learn at most one representation per concept, namely the
simplest one. But the main issue is that if the teacher does not know that
$r_{1}$ and $r_{2}$ are equivalent, and $r_{1}$ is simpler than $r_{2}$, then
the teacher will be looking for a witness set for $r_{2}$ that distinguishes
it from $r_{1}$, something the teacher will never find.

How to alter the Eager algorithm in a natural way so that all the
representations of a concept will be taught, not only the simplest one? When
teaching a target it is quite common to give the smallest observation that
suffices to learn it, and the learner could actually expect this from the
teacher, and thus rule out representations that could have been taught with a
witness smaller than what was given. Herein lies the simple idea behind the
slight change to the Eager algorithm into what we call the Greedy algorithm.
The teacher uses the smallest consistent witness to teach the simplest
representation, removes this witness and representation from further
consideration, and repeats. Likewise, the learner, when given a witness, will
know the teacher behaves in the above way and be able to guess the correct
representation.

We also introduce another protocol that we call Optimal, as it represents the
graph-theoretical best possible under the minimal constraint that a
representation must be taught by a consistent witness and that two distinct
representations must be taught by two distinct witnesses. In Section 3 we show
several formal results about the strengths of the three algorithms: Eager,
Greedy and Optimal. In particular, on concepts taught by both Eager and
Greedy, the latter will never use a larger witness, and often a smaller
witness. However, Theorem 3 shows that for any concept class, adding redundant
representations with small spread in the order, can level out this difference
between Eager and Greedy. Moreover, there are situations where the max size
witness used by Greedy will be much larger than the Optimal. Finally, in
arguing for a lower bound on the performance of Greedy we arrive at a question
about which binary matrix on $k$ distinct rows achieves the smallest number of
’projection vectors’ (see Section 3 for details). This question seems to be of
combinatorial interest, and we conjecture that its solution is given by the
matrix containing the binary representations of the numbers from zero to
$k-1$.

In Section 4 we report on experiments with these three algorithms, on several
representation languages with various kinds of redundancy. Tables 4.1, 4.1 and
4.1 in the last section summarize the results. The main finding is that while
Greedy needs more witness sets to teach all representations, it uses them more
effectively to also teach more concepts, and it does so while teaching several
common concepts by a smaller witness. The experiments were furthermore chosen
to answer the following question: what characterizes a language where Greedy
teaches only a few common concepts by a smaller witness than Eager? We show
that this is not directly related to the amount of redundancy, but rather to
the spread of the redundant representations in the order, see Figure 2, with
Eager performing better the lower the Redundancy Spread. In Figure 3 we see
that for P3 programs the witness sets are usually smaller than the programs
they identify, which is an illuminating justification of why machine teaching
from examples makes sense at all.

Teaching representations rather than concepts is a natural setting as teachers
represent concepts in a given language, and size preferences (e.g., Occam’s
razor) apply to all representations and not only to the canonical one in the
equivalence class, which teacher and learner may not know. The Eager and
Greedy protocols are two extremes (one teaching a single representation per
concept and the other teaching all representations) in a spectrum of
approaches that can shed light to important phenomena such as the effect of
redundancy in inductive search, the actual bias in size-related priors and the
relevance of syntax over semantics in explanations.

There are many practical situations where representations rather than concepts
matters. For instance, the Promptbreeder from GoogleMind [7] that generates
various prompts (representations) to get the same answer (concept), or the use
of Codex in teaching [8] which produces various programs (representations)
having the same behaviour (concept). Having said that, our main contribution
is not practical, it is rather the insight about highlighting the distinction
between concepts and representations, and showing theoretically and
experimentally how small witness sets can be when teaching, given the existing
redundancy. We conclude with a discussion in Section 5.

##  2 Machine Teaching definitions

Various models of machine teaching have been proposed, e.g., the classical
teaching dimension model [10], the optimal teacher model [2], recursive
teaching [21], preference-based teaching [9], or no-clash teaching [6]. These
models differ mainly in the restrictions they impose on the learner and the
teacher to avoid collusion. The common goal is to keep the teaching dimension,
i.e., the size of the largest teaching set, $\max_{c\in C}|T(c)|$, as small as
possible.

In all these models, we have a set $C$ of concepts, with each concept being a
subset of a domain $X$. In this paper we consider more than one representation
for the same concept, thus with $R$ being a set of representations that
constitute a multiset of the concepts $C$ that are the subsets of $X$. The
teacher $T:R\rightarrow W$ is now a partial injective mapping from
representations $r\in R$ to a set of observations $w\in W$ (often $W\subseteq
2^{X\times\\{0,1\\}}$ so that $w$ is a set of negatively or positively
labelled examples from $X$) and the learner $L:W\rightarrow R$ is a partial
mapping in the opposite direction. As usual, teacher and learner share the
consistency graph $G_{R}$ on vertex set $R\cup W$ with a representation $r\in
R$ adjacent to a witness $w\in W$ (and thus $rw\in E(G_{R})$ an edge) if $r$
and $w$ are consistent, i.e., with positive (resp. negative) examples in $w$
being members (resp. non-members) of $r$. Naturally, $r$ must be consistent
with $T(r)$ and $L(w)$ must be consistent with $w$, and a successful teacher-
learner pair must have $L(T(r_{1}))=r_{2}$ such that $[r_{1}]=[r_{2}]$. In
what follows, we will assume $L$ and $T$ use the same representation language
and we will impose that $L(T(r))=r$.

Let us take the graph theoretical view. The teacher and learner mappings are
matchings in $G_{R}$ between representations and witnesses. Two vertices are
called twins if they have the same set of neighbors. Usually there is a
bijection between the equivalence classes of twins of $R$ in the graph
$G_{R}$, that we denote by $R/W$, and the set of concepts $C$. However, if the
witness set $W$ is too sparse then $R/W$ may be a coarsening of $C$.

We will be comparing two models for teaching representations, that we call
Eager and Greedy. Both assume some natural size functions on representations
$R$ and on witnesses $W$, and use these to arrive at two total orderings
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$ on $R$ and
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$ on $W$. For example, if the
representations in $R$ are expressed in some description language, which can
be English, or a programming language, or some set of mathematical formulas,
then a representation consists of finite strings of symbols drawn from some
fixed alphabet $\Sigma$, given with a total order which will be used to derive
a lexicographic order on strings over this alphabet, with shorter strings
always smaller, sometimes called shortlex. To define a total ordering on
witnesses, we can do something similar.

Thus, the input to these algorithms is what we call an ordered consistency
graph consisting of the 3-tuple
$(G_{R},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W})$
and when we talk about a vertex (or representation/witness) appearing earlier
than another we mean in these orderings. In the Eager model we have $L(w)=r$
for $r$ being the earliest representation (in the order
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$) consistent with $w$. The
teacher, knowing that the learner behaves in this way, will construct the
mapping $T:R\rightarrow W$ iteratively as follows: go through $W$ in the order
of $\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$, and for a given witness
$w$ find the earliest $r\in R$ with $rw\in E(G_{R})$, and if $T(r)$ not yet
defined then set $T(r)=w$ else continue with next witness. In [16] the Eager
model was used to teach programs in the Turing-complete language P3, by
witnesses containing specified I/O-pairs. Many P3 programs have equivalent
I/O-specifications, and we can observe that in the Eager model only the
earliest representation (program) of any concept (I/O-specification) is
taught.

In order to teach all representations we introduce the Greedy model, where we
make a slight change to the way the teacher constructs its mapping, as
follows: go through $W$ in the order of
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$, and for a given witness $w$
find the earliest $r\in R$ with $rw\in E(G_{R})$ such that $T(r)$ is not yet
defined, then set $T(r)=w$ and continue with next witness (if no such $r$
exists then drop this $w$). Teaching and Learning in the Greedy model is thus
done following an order, similar to what happens in the Recursive teaching
model of [21] (teach sequentially and remove concepts that have already been
taught), using also an order on the representations, similar to what is done
in the Preference-Based teaching model of [9] (return the most preferred
remaining concept consistent with a given witness).

In classical machine teaching, the goal is to minimize the teaching dimension
of a concept class, i.e. to find a legal teacher mapping $T:C\rightarrow W$
where the maximum of $|T(c)|$ over all $c\in C$ is minimized. When there is a
total mapping $T:R\rightarrow W$ we do the same for teaching representations,
except we use $size(T(c))$ rather than cardinality, as in Optimal-1 defined
below. However, a total mapping may not exist, and in that case we will in
this paper define an alternative measure, as in Optimal-2 below, being the
maximum number of representations covered when constrained to partial teacher
mappings covering the maximum number of concepts. We thus define the Optimal
model in two flavors.

Optimal-1 : this is the minimum max size witness used over all teacher
mappings, under the sole restriction that the teacher mapping is injective and
assigns a consistent witness to every representation. This value can be
computed in polynomial time by a binary search for the smallest $k$ such that
the induced subgraph $G_{R}^{k}$ of $G_{R}$, on $R$ and all witnesses of size
at most $k$, has a matching saturating $R$, i.e., containing all of $R$.

Optimal-2 : as Optimal-1 is undefined when $G_{R}$ has no matching saturating
$R$, we define Optimal-2 as the maximum number of representations covered by
any matching that maximizes the number of concepts covered. It is not clear
that this number is computable in polynomial time, but for most graphs in the
experimental section we could compute it.

##  3 Formal comparisons

We show several results comparing the performance of the three algorithms
Eager, Greedy and Optimal. We start with Figure 1 giving the simplest possible
consistency graph where Eager, Greedy and Optimal-1 behave differently.

The teacher mapping $T:R\rightarrow W$ for Greedy, as defined in previous
section, is computed by an iterative procedure whose outer loop follows the
witness ordering (and inner loop representation ordering). Let us call it
$T_{W}:R\rightarrow W$. Consider the alternative $T_{R}:R\rightarrow W$ which
switches these two: go through $R$ in the order of
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$, and for a given
representation $r$ find the earliest $w\in W$ with $rw\in E(G_{R})$ such that
$T_{R}^{-1}(w)$ is not yet defined, then set $T_{R}(r)=w$ and continue with
the next representation (if no such $w$ exists then drop this $r$).

######  Theorem 1.

The teacher mappings returned by Greedy following
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$ versus the alternative
following $\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$ are the same.

###### Proof.

We prove, by induction on $\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$,
the statement (*): ”for any $w\in W$ if $T_{W}(r)=w$ then also $T_{R}(r)=w$”.
Let $w_{1}$ be the earliest witness. We have $T_{W}(r^{\prime})=w_{1}$ and
when assigning $T_{R}$ clearly $w_{1}$ is the earliest neighbor of
$r^{\prime}$ with $T_{R}^{-1}(w_{1})$ undefined so that
$T_{R}(r^{\prime})=w_{1}$. For the inductive step, we assume the statement (*)
for all witnesses earlier than $w$, and assume that $T_{W}(r)=w$. By the
inductive assumption (*) we know that no witness earlier than $w$ will by
$T_{R}$ be assigned to $r$. This means that when assigning $T_{R}(r)$ then $w$
is the earliest neighbor of $r$ with $T_{R}^{-1}(w)$ undefined, and thus we
have $T_{R}(r)=w$ as desired. ∎

Since the Greedy teaching is only a slight change to the Eager teaching, it is
easy to see that for any $r\in R$, if Eager assigns $T_{E}(r)=w_{E}$ then
Greedy will also assign some $T_{G}(r)=w_{G}$, and in the order
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$ we could have $w_{G}$ earlier
than $w_{E}$, but not the other way around.

######  Theorem 2.

On representations/concepts taught by Eager, Greedy will never use a larger
witness.

###### Proof.

This since $T_{E}(r)=w_{E}$ implies that $r$ is the earliest representation
consistent with $w_{E}$, so when the Teacher mapping of Greedy is computed
then when reaching $w_{E}$ the first representation tried will be $r$, and if
$T_{G}(r)$ has already been defined it will be for an earlier and thus no
larger witness. ∎

We show that for any concept class we can add redundant copies of
representations consecutive in
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$ to make Eager and Greedy
perform almost identical.

######  Theorem 3.

For any concept class $R$ (i.e. each concept has a unique representation) on
witness set $W$ and orders
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$,
we can add less than a total of $|W|$ copies of representations to get
$R^{\prime}$, and make
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R^{\prime}}$ an extension of
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$ with all copies consecutive,
such that Eager teaches the same on
$(G_{R},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W})$
as on
$(G_{R^{\prime}},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R^{\prime}},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W})$
and using the same witnesses as Greedy on
$(G_{R^{\prime}},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R^{\prime}},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W})$
on all common concepts.

###### Proof.

Consider the ordered consistency graph
$(G_{R},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W})$
and for each representation $r\in R$ compute $f_{r}=|\\{w\in W:rw\in
E(G_{R})\wedge(r^{\prime}w\in E(G_{R})\Rightarrow
r\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}r^{\prime})\\}|$, i.e. the
number of witnesses for which $r$ is the earliest neighbor. Let $R^{\prime}$
be the representation class corresponding to the ordered consistency graph
$(G_{R^{\prime}},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R^{\prime}},\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W})$
where for each $r\in R$ we add $f_{r}-1$ copies of $r$ and extend the order
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$ to
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R^{\prime}}$ by putting all the
copies consecutively right after $r$, so there are $f_{r}$ consecutive copies
total of $r$. Note that, as the sum of $f_{r}$ over all $r\in R$ is $|W|$
(each witness has a single earliest $r$) we add less than $|W|$ new
representations.

For each $w\in W$ define $r_{w}$ to be the earliest neighbor of $w$ in $G_{R}$
and let $r^{\prime}_{w}$ be the earliest neighbor in $G_{R^{\prime}}$. For
simplicity, when we say $G_{R},G_{R^{\prime}}$ we mean the ordered consistency
graphs. We prove the following loop invariant on any witness $w\in W$ by
induction over $\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$: ”Knowing
$r_{w}$ has $f_{r_{w}}$ witnesses for which it is the earliest, let $w$ be the
$k$th such witness. Both on $G_{R}$ and $G_{R^{\prime}}$, if $k=1$ then Eager
will assign $r_{w}$ to $w$, and if $k>1$ Eager will not use $w$. Greedy on
$G_{R^{\prime}}$ will assign $r$ to $w$ for $r$ being the $k$th copy of
$r_{w}$ in the $\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R^{\prime}}$
order.” The loop invariant is trivially true for the first witness. For the
inductive step, we know $r_{w}$ is the earliest neighbor of $w$ and that $w$
shares this property with $f_{r_{w}}$ witnesses. If $w$ is the first of these
witnesses, then it is clear that both Eager and Greedy will assign $r_{w}$ to
$w$, as the loop invariant tells us no earlier witness has been assigned to
$r_{w}$. If $w$ is the $k$th copy of $r_{w}$ for $k\geq 2$ then Eager will not
use $w$, neither on $G_{R}$ nor $G_{R^{\prime}}$, while for Greedy on
$G_{R^{\prime}}$ as there are at least $k$ copies of $r_{w}$ all in
consecutive order then Greedy will assign $w$ to the $k$th copy as it must be
available by the loop invariant. We have thus proven the loop invariant, and
this implies the statement of the Theorem as it encompasses all
representations taught by both algorithms. ∎

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$
---

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$ |  $c_{1}$$c_{2}$$c_{3}$$c_{4}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$ |  $c_{1}$$c_{2}$$c_{3}$$c_{4}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$
---|---|---
Eager | Greedy | Optimal-1

Figure 1: Simplest possible ordered consistency graph
($\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$ and
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$ given by the indices) showing
that Eager, Greedy and Optimal-1 can require different maximum teaching sizes
(witnesses of size 6, 5 and 4 respectively), assuming witness $w_{i}$ has size
$i$.

When we allow the size of ground elements to vary, we can show the following.

######  Theorem 4.

When there is a bound on the number of witnesses of any size, then for any
$t$, there exists a size ordered consistency graph where Greedy uses a witness
of size $G_{max}$ while Optimal-1 will not use a witness of size larger than
$O_{max}$ and where $G_{max}-O_{max}\geq t$.

###### Proof.

We prove this statement by construction, for a graph where we have only one
representation for each concept. Assume there are at most $s$ witnesses of any
size. Let concept ordering be $c_{1},c_{2},...c_{k}$, and let witness ordering
be $w_{1},w_{2},w_{3},...w_{st+k},...$ with $s(w_{i})\leq s(w_{i+1})$, for any
choice of $k$. Let $c_{1}$ be consistent with $w_{1}$ and $w_{2}$, and let
$c_{2}$ be consistent with $w_{1}$ and $w_{st+k}$ (but not consistent with any
witness in between, which could happen if e.g. there are that many ground
elements) and let $c_{i}$ for $3\leq i\leq k$ be consistent with
$w_{i},w_{i+1},...,w_{i+st}$. The Optimal matching will assign $c_{1}$ to
$w_{2}$ and $c_{2}$ to $w_{1}$ and $c_{i}$ to $w_{i}$ for any $3\leq i\leq k$,
thus using maximum size witness with index $k$. Greedy will assign almost the
same matching except it starts with $c_{1}$ to $w_{1}$ and then $c_{2}$ to
$w_{st+k}$ since this is the only one available, thus using maximum size
witness with index $st+k$. As we have at most $s$ witnesses of each size, we
have that $s(w_{st+k})-s(w_{k})\geq t$. ∎

Finally, we would like to give lower bounds on the performance of Greedy, in
the setting where size of witnesses is simply cardinality, i.e. the
traditional teaching dimension. Let us consider two extremes, one where we
have many representations of the same single concept (i.e. $|C|=1$) and
another where each concept has a single representation (i.e. $R=C$).

In the former case, it is easy to see that Greedy will perform as well as
Optimal-1 , since Greedy goes through witnesses by increasing cardinality and
assigns them to the next representation (all of the same single concept) if
consistent. Thus if Greedy assigns a witness of size $q$ then so must
Optimal-1 .

In the latter case, with only one representation per concept, we argue that if
Greedy assigns a witness of cardinality $q$ to some concept $c$ then this
implies a lower bound on $|C|$ given as follows. Let us start by asking, why
was $c$ not taught by a smaller witness? Assuming there are $|X|=n$ examples,
then any subset $Q\subseteq X$ of size $q-1$ when labelled consistent with $r$
has already been tried by Greedy, and hence some other concept must already
have been assigned to any such $Q$, and all these concepts are distinct. This
means we must have taught ${n\choose q-1}=k$ other concepts already. But then
we have already taught at least $k+1$ concepts and we can again ask why were
any of these not taught by a smaller witness of size $q-2$? It must be that
any such witnesses (labelled to be consistent with some concept among the k+1
we already have) must have been used to teach other, again distinct, concepts.

Consider the binary matrix $M$ where concepts are rows and columns are given
by $X$ and $M(c,x)=1$ if and only if $c$ consistent with $x$ labelled 1. Note
that, to verify how many distinct witnesses exists, corresponding to new
concepts, that are labelled consistently with one of these $k+1$ concepts, one
must sum up the number of distinct rows when projecting on $q-2$ columns, for
all choices of these columns. Note that the number of distinct rows, i.e
witnesses and hence number of concepts, when projecting on $q-2$ columns, for
all choices of these columns, depends on the matrix $M$ we do the projection
on. Thus, we need to find the matrix $M$ minimizing the sum of unique rows
after doing the projection. To achieve a lower bound on the size of $C$ when
Greedy uses a witness of size $q$, we thus arrive at the following
combinatorial question. What is the binary matrix $M$ on $k$ distinct rows and
$n$ columns that would give the smallest sum when projecting on $q$ columns?

We have not been able to answer this question, and until we answer it we are
not able to carry out the final steps of the lower bound argument. However, we
conjecture that it is achieved by the matrix consisting of the $k$ rows
corresponding to the binary representations of the numbers between zero and
$k-1$, with leading 0s to give them length $n$.

##  4 Experiments

In this section we observe quantitatively how each teaching protocol behaves
in a variety of languages with various types of redundancy. Table 4.1
summarizes the key features. Let us first describe the metrics used, before
describing the languages. To estimate how redundant a language is, we define
_Redundancy_ as $1-Uniqueness$, where $Uniqueness$ is computed as the average
for all concepts of $1/{|R_{c}|}$, with ${R_{c}}$ the set of all equivalent
representations for concept $c$. Formally:

$\mathrm{Redundancy}=1-{\frac{1}{|C|}\sum_{c\in C}{\frac{1}{|R_{c}|}}}~{}.$
(1)

From the result of Theorem 3 we suspect that Eager performs well compared to
Greedy when, for each witness $w$, if we look at the set $R^{i}_{w}$ of the
$i$ earliest representations consistent with $w$, then there are few different
concepts in $R^{i}_{w}$. Assuming the
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$ ordering is $w_{1},w_{2},...$
we define _Redundancy Spread_ as the average number of different concepts in
$R^{i}_{w_{i}}$. We use $R^{i}_{w_{i}}$ for $w_{i}$ because $\leq i$ values of
$T:R\rightarrow W$ have been defined when Greedy or Eager consider $w_{i}$.
Formally, if for each witness $w_{i}$ we let $r^{j}_{w_{i}}$ be the $j$-th
representation consistent with $w_{i}$, and recalling that $[r]$ is the
concept equivalence class $r$ belongs to, the definition of Redundancy Spread
becomes:

$\displaystyle\frac{1}{|W|}\sum_{w_{i}\in
W}\left|\\{[r^{j}_{w_{i}}]:j\in[1\ldots i]\right\\}|$

###  4.1 Boolean Expressions

We experiment with Boolean expressions, since in this domain it is possible to
decide whether two representations belong to the same equivalence class, i.e.,
correspond to the same concept. Furthermore, in this language, we are able to
measure the degree of redundancy present in the set of representations. In all
our experiments, we consider the ordered alphabet of 3 Boolean variables
$\\{a,b,c\\}$ and every representation in $R$ is expressed in DNF (Disjunctive
Normal Form), i.e. OR of AND-terms. Every variable occurs at most once in a
term, possibly preceded by the negation operator $\neg$. For example,
$(a\wedge b\wedge\neg c)$ is a valid ground term.

Let us first describe the witnesses, which are similar across all experiments.
Each example is a pair consisting of a binary string of length three (the
input) and a bit (the output), such as $(001,1)$ indicating that when
$a=0,b=0,c=1$ the value of the function should be $1$. There are thus 16
witnesses of cardinality one, and $16*14/2=112$ witnesses of cardinality two,
as we do not allow for self-incongruent witnesses and the order of examples is
irrelevant. For these experiments we use witnesses of cardinality up to $5$,
and only positive examples, which implies $|W|=3,448$.

$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$: The witnesses in the
collection $W$ are ordered by their increasing teaching size. The size
function $s:W\rightarrow\mathbb{N}$ is defined for a witness $w$ as the number
of examples in $w$ times 4 (the number of bits) plus the number of 1s in the
inputs of the examples. This scheme would be useful for a situation with many
variables, where it could be more efficient to just identify the position of
the 1s in a long binary string.

In the first experiment, _3-DNF_ , we build a scenario without redundancy. We
consider all 256 Boolean functions on three variables as the set $R=C$, as
follows. A Boolean function $\phi$ on $a,b,c$ is uniquely defined by a truth
table that gives the truth values for the 8 possible truth assignments to the
three variables. For any assignment $(v_{a},v_{b},v_{c})$ to $(a,b,c)$ where
$\phi(v_{a},v_{b},v_{c})=1$ we include the corresponding term in the
representation $r_{\phi}$ of $\phi$ in $R$. For instance, if $\phi$ is
logically equivalent to “$a$ and $b$” then this is represented as
$r_{\phi}=(a\wedge b\wedge c)\vee(a\wedge b\wedge\neg c)$.

In our second experiment, _3-term DNF_ , we introduce redundancy in $R$, and
do this in a way that will shrink the concept space to have smaller
cardinality $|C|=246$. Every representation is now a disjunction of up to $3$
ground terms, and each term contains one, two or three distinct variables,
each possibly negated. For a single term we have six representations of one
variable, $12=6*4/2$ representations of two variables, and $8$ representations
for three variables, thus $26$ in total. For two terms we have $26*25/2=325$
representations, and for three terms we have $26*25*24/3!=2,600$. We also have
a single representation (False) with no terms, and thus
$|R|=1+26+325+2,600=2,952$.

For the third experiment, _3-term DNF with permutations_ , we want to increase
Redundancy and decrease Redundancy Spread. The set of representations is
similar to 3-term DNF, but here we allow for any permutation of variables
within each term. For example, if $(b\wedge\neg c)\in R$, also $(\neg c\wedge
b)\in R$. This drastically increases the cardinality of $R$, while Redundancy
also increases substantially and Redundancy Spread decreases. This third
experiment is carried out also against a smaller witness set, with witnesses
of cardinality 5 only, to see the effects of a large decrease in Redundancy
Spread.

Finally, the last Boolean experiment, _3-term DNF with permutations and
duplicates_ , is similar to the previous one, 3-term DNF with permutations,
but here each representation occurs consecutively twice in the ordered
collection $R$, for yet another variation of redundancy.

$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$: Representations in $R$ are
ordered by increasing size $s(r)$ defined as the number of literals in $r$
plus the number of negated variables plus the number of disjunction symbols;
e.g., $s((a\wedge b\wedge c)\vee(a\wedge b\wedge\neg c))=8$. Two
representations of same size are further ordered by the increasing number of
terms, and by the $\langle a,b,c,\neg,\vee\rangle$-induced lexicographic
order.

Domain |  $|R|$ |  $|C|$ |  Witness |  $|W|$ |  Redundancy |  Redundancy  Spread
---|---|---|---|---|---|---
3-DNF | 256 | 256 |  $|w|\leq 5$ | 3,488 | 0 | 15.13
3-Term DNF | 2,952 | 246 |  $|w|\leq 5$ | 3,488 | 0.727 | 13.28
3-Term DNF with permutations | 79,158 | 246 | $|w|\leq 5$ | 3,488 | 0.9896 | 11.41
$|w|=5$ | 1,792 | 0.9896 | 7.04
3-Term DNF with permuts. and duplicates | 158,316 | 246 | $|w|\leq 5$ | 3,488 | 0.9948 | 10.42
P3 | $1.9*10^{9}$ | ? | $s(w)\leq 6$ | 6,548 | ? | ?
small-P3 | 1,267 | 106* | $s(w)\leq 4$ | 260 | 0.331 | 2.97

Table 1:  Domain features: ‘Witness’ is the size of each witness. For P3 we do
not know $G_{R}$ nor $C$. *For small-P3 we do not know $|C|$ so we show
$|R/W|$.

Domain |  Witness |  Algorithm |  Reps. taught |  Concepts taught |  Max. $\\{s(w)\\}$ |  Max. $\\{i(w)\\}$
---|---|---|---|---|---|---
3-DNF | $|w|\leq 5$ | Eager | 219 | 219 | 30 | 3,488
Greedy | 256 | 256 | 16 | 328
Optimal-1 | 256 | 256 | 16 | 256
3-Term DNF | $|w|\leq 5$ | Eager | 170 | 170 | 30 | 3,466
Greedy | 2,895 | 246 | 30 | 3,481
Optimal-1 | 2,952 | 246 | 28 | 2,952
3-Term DNF  with permutations | $|w|\leq 5$ | Eager | 170 | 170 | 30 | 3,466
Greedy | 3,488 | 189 | 30 | 3,488
Optimal-2 | 3,488 | 246 | 30 | 3,488
$|w|=5$ | Eager | 170 | 170 | 30 | 1,770
Greedy | 1,792 | 177 | 30 | 1,792
Optimal-2 | 1,792 | 246 | 30 | 1,792
3-Term DNF  with permutations and duplicates | $|w|\leq 5$ | Eager | 170 | 170 | 30 | 3,466
Greedy | 3,488 | 178 | 30 | 3,488
Optimal-2 | 3,488 | 246 | 30 | 3,488
P3 | $s(w)\leq 6$ | Eager | 2,032 | 2,032 | 6 | 6,512
Greedy | 6,548 |  | 6 | 6,548
small-P3 | $s(w)\leq 4$ | Eager | 53 | 53 | 4 | 202
Greedy | 225 | 65 | 4 | 260
Optimal-2 |  $\geq 214$* | 106 | 4 | 260

Table 2: Overview of results for the teaching frameworks across all domains.
$s(w)$ is the size of a witness $w$; $i(w)$ is the index of witness $w$ in the
order $\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$. * For Optimal-2 and
small-P3 ‘Reps. taught’ not known exactly.

Domain |  Witness |  $\%$ Witness Index Lower |  $\%$ Witness Size Smaller
---|---|---|---
3-DNF | $|w|\leq 5$ | 94.98% | 94.06%
3-term DNF | $|w|\leq 5$ | 97.65% | 97.06%
3-Term DNF with permutations | $|w|\leq 5$ | 90.59% | 88.24%
$|w|=5$ | 40.00% | 30.00%
3-Term DNF w/ permuts. and duplicates | $|w|\leq 5$ | 84.12% | 81.18%
P3 | $s(w)\leq 6$ | 13.98% | 6.55%
small-P3 | $s(w)\leq 4$ | 24.53% | 18.87%

Table 3: Greedy beating Eager: Common concepts with earlier (lower index) and
simpler (smaller size) witness.

###  4.2 Universal Language

We also analyze the new teaching frameworks for the Turing-complete language
P3. P3 is a simple string manipulation language inspired by P”, introduced by
Corrado Böhm ([3]), the first GOTO-less imperative language proved Turing-
complete, i.e., universal. The most popular variant (Brainfuck) has 8
instructions in total. We employ another version called P3, also universal and
having just 7 instructions: $<>$+-[]o. We consider P3-programs that take
binary inputs and generate binary outputs. A representation is a P3 program,
such as the following one, which performs the left shift operation (e.g., on
input 10010 we get output 00101): $>$[o$>$]$<$[$<$]$>$o. Regarding the
semantics of P3, we refer to [16].

A witness is a set of pairs of binary strings defining an input and an output,
and we use only positive examples. For example, the witness $w=\\{\langle
0100,00\rangle,\langle 001,\rangle,\langle 00,00\rangle\\}$ is consistent with
any program that on input 0100 outputs 00, on input 001 has no output and on
input 00 outputs 00.

$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{W}$: We use a simple encoding of
example sets (the number of bits) as the size function $s(w)$, and break ties
in a deterministic way. The witness $w$ above has size $s(w)=13$.

$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$: We use the lexicographic
order on instructions $<>$+-[]o to define the
$\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$ length-lexicographic ordering
of P3 programs.

We perform two experiments, which we call P3 and small-P3. In P3 we repeat the
experiment from [16]. Note that computing equivalence classes of programs is
undecidable in general, and we cannot decide if a program enters an infinite
loop. We limit the number of timesteps for the computation of each program
before breaking. In the P3 experiment, the set of representations/programs $R$
is a potentially infinite set, but Eager and Greedy end up never going beyond
the $1.9*10^{9}$ first programs. The witness set $W$ contains all sets of size
at most 6. Since we cannot compute the consistency graph and run any version
of Optimal, we conduct a second experiment, small-P3.

In small-P3 we start with all self-congruent witnesses of size at most 4, and
the first 10,000 programs in $\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}_{R}$.
We filter out every witness without consistent program and every program
without consistent witness. A set of 1,267 programs is then $R$, and a set of
260 witnesses is $W$. We compute the consistency graph $G_{R}$ and use $R/W$
as the concept class, i.e., considering two programs equivalent if they are
consistent with the exact same subset of $W$.

###  4.3 Experimental Results

In Table 4.1 we present an overview of selected results for all the
experimental domains described in subsections 4.1 and 4.2. Table 4.1 reports
on % of cases where Greedy is able to teach concepts with earlier and simpler
witnesses than those used by Eager, and Figure 2 shows that Redundancy Spread
to a large degree explains this behavior.

As Table 4.1 shows, for most of the Boolean experiments, Greedy manages to
teach as many representations as the amount of witness sets available. This
aligns with the suitability of Greedy for teaching in a scenario of redundant
representations. Moreover, we can observe that Greedy is always able to teach
more concepts than a method like Eager that specializes in teaching unique
concepts. Since Greedy teaches many more concepts and representations,
sometimes it does so by making use of witnesses that are larger or later in
the order. Yet, even in scenarios without redundancy, such as 3-DNF, where
Eager might be considered more suitable, Greedy still teaches some more
concepts, and does it with earlier and smaller witnesses. Greedy performs
almost as good as Optimal-1 and Optimal-2 in terms of the number of
representations taught, and the largest size and highest index of witnesses
used. However, Optimal-2 (which is used rather than Optimal-1 whenever not all
of $R$ can be covered) always covers a higher amount of concepts than Greedy.
The correlation between the percentage of cases where Greedy outperforms Eager
and the Redundancy Spread is shown in Figure 2, and confirms the latter as a
strong metric for predicting these performance comparisons. A more detailed
analysis can be found in Supplement.

Analyzing now the universal language domain, we see that Greedy allows to
teach over three times more (almost five for small-P3) programs than Eager.
For P3 we do not have the consistency graph and thus cannot compute any
version of Optimal. Quite remarkably, in Figure 3 we see that for P3 programs
the witness sets of Greedy are usually smaller than the programs they
identify. A similar behavior for fewer programs was noted for Eager in [16].
For small-P3 we use $R/W$ as a proxy for $C$ and note that Optimal-2 is able
to cover all these 106 concepts, but seemingly at the price of fewer
representations (214 versus 225 for Greedy). However, note that our
implementation of Optimal-2 is actually only able to optimize the number of
concepts covered. The further maximization of representations that Optimal-2
requires may in fact be NP-hard, but we must leave this as an open problem. On
concepts common to Eager and Greedy, we have the latter finding smaller
witnesses on a relatively small percentage of the total for Small-P3 (see
Figure 2) but even more so for P3. For P3 we do not have the consistency
graph, so we cannot compute Redundancy Spread, but we hypothesize that the
small values of 13.98% and 6.55%, still in favor of Greedy, which we observe
for P3, are due to an even lower Redundancy Spread of its underlying
consistency graph.

Figure 2: Relation between Redundancy Spread, and % Greedy better than Eager.
Data from Tables 4.1 and 4.1. The red line is the best fit linear
approximation.

.

Figure 3: Greedy: Program length versus witness size, using Elias coding
([4]). Circles above the unit diagonal denote witness smaller than program,
with size of circle = number of programs.

##  5 Discussion

The notion of redundancy we explore in this paper is very old, dating back to
numeral systems (e.g., IIII and IV being two alternative representations of
the number 4 in Roman numerals). Leibniz was interested in prime decomposition
as a tool for his characteristica universalis in which the representations and
concepts could have a bijective mapping. In numeration systems, this is
possible. Indeed, it was Böhm himself (the ’father’ of P3) who proved that
every natural number has a unique representation in bijective base-$k$ ($k\geq
1$) [3]. However, we also know that in many other languages, such as Turing-
complete languages, this is not possible.

The more realistic view of teaching adopted in this paper modifies some key
elements of the traditional machine teaching setting and gives more relevance
to the representation language. Given the high predictiveness for some
teaching indicators, the new metric of redundancy spread introduced in this
paper, could be used to anticipate what language representations are better
than others for teaching and learning. The size of representations becomes a
natural way of imposing an order on them, which can be used in the teaching
protocols. Of course, all this comes at a cost, and some of the protocols seen
here, such as Greedy, are computationally expensive. However, none of them
requires the calculation of equivalence classes, which may also be expensive
(or undecidable) for some formal languages. The most surprising finding is
that a protocol such as Greedy that is designed to teach all representations
ends up teaching more concepts than Eager, which aims at only teaching
concepts. The experimental and theoretical results indicate that there is a
wide spectrum between these two protocols, and future work could explore some
other teaching protocols for representations that are somewhat in between
these two, or have better theoretical or statistical properties.

## References

  * [1] María Alpuente, Marco Comini, Santiago Escobar, Moreno Falaschi, and José Iborra.  A compact fixpoint semantics for term rewriting systems.  Theoretical Computer Science, 411(37):3348–3371, 2010.
  * [2] Frank J Balbach.  Measuring teachability using variants of the teaching dimension.  Theoretical Computer Science, 397(1-3):94–113, 2008.
  * [3] Corrado Böhm.  On a family of Turing machines and the related programming language.  ICC Bulletin, 3(3):187–194, 1964.
  * [4] Peter Elias.  Universal codeword sets and representations of the integers.  IEEE Trans. Inf. Theory, 21(2):194–203, 1975.
  * [5] Per Enflo, Andrew Granville, Jeffrey Shallit, and Sheng Yu.  On sparse languages l such that ll= $\sigma$.  Discrete Applied Mathematics, 52(3):275–285, 1994.
  * [6] Shaun Fallat, David Kirkpatrick, Hans U Simon, Abolghasem Soltani, and Sandra Zilles.  On batch teaching without collusion.  Journal of Machine Learning Research, 24:1–33, 2023.
  * [7] Chrisantha Fernando, Dylan Banarse, Henryk Michalewski, Simon Osindero, and Tim Rocktäschel.  Promptbreeder: Self-referential self-improvement via prompt evolution.  CoRR, abs/2309.16797, 2023.
  * [8] James Finnie-Ansley, Paul Denny, Brett A. Becker, Andrew Luxton-Reilly, and James Prather.  The robots are coming: Exploring the implications of openai codex on introductory programming.  In Judy Sheard and Paul Denny, editors, ACE ’22: Australasian Computing Education Conference, Virtual Event, Australia, February 14 - 18, 2022, pages 10–19. ACM, 2022.
  * [9] Ziyuan Gao, Christoph Ries, Hans Ulrich Simon, and Sandra Zilles.  Preference-based teaching.  Journal of Machine Learning Research, 18:31:1–31:32, 2017.
  * [10] Sally A Goldman and Michael J Kearns.  On the complexity of teaching.  Journal of Computer and System Sciences, 50(1):20–31, 1995.
  * [11] Robert F Hadley and Vlad C Cardei.  Language acquisition from sparse input without error feedback.  Neural Networks, 12(2):217–235, 1999.
  * [12] Brigt Arve Toppe Håvardstun, C. Ferri, José Hernández-Orallo, Pekka Parviainen, and Jan Arne Telle.  XAI with machine teaching when humans are (not) informed about the irrelevant features.  In ECML/PKDD, 2023.
  * [13] Stephen Muggleton and Luc De Raedt.  Inductive logic programming: Theory and methods.  The Journal of Logic Programming, 19:629–679, 1994.
  * [14] Claire Nédellec, Céline Rouveiro, Hilde Adé, Francesco Bergadano, and Birgit Tausend.  Declarative bias in ILP.  1995\.
  * [15] Patrick Shafto, Noah D. Goodman, and Thomas L. Griffiths.  A rational account of pedagogical reasoning: Teaching by, and learning from, examples.  Cognitive Psychology, 71:55 – 89, 2014.
  * [16] Jan Arne Telle, José Hernández-Orallo, and Cèsar Ferri.  The teaching size: computable teachers and learners for universal languages.  Machine Learning, 108(8-9):1653–1675, 2019.
  * [17] Peter A Whigham.  Search bias, language bias, and genetic programming.  Genetic Programming, 1996:230–237, 1996.
  * [18] Scott Cheng-Hsin Yang, Wai Keen Vong, Ravi B Sojitra, Tomas Folke, and Patrick Shafto.  Mitigating belief projection in explainable artificial intelligence via bayesian teaching.  Scientific reports, 11(1):1–17, 2021.
  * [19] Sheng Yu.  Can the catenation of two weakly sparse languages be dense?  Discrete applied mathematics, 20(3):265–267, 1988.
  * [20] Xiaojin Zhu, Adish Singla, Sandra Zilles, and Anna N Rafferty.  An overview of machine teaching.  arXiv preprint arXiv:1801.05927, 2018.
  * [21] Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich.  Models of cooperative teaching and learning.  Journal of Machine Learning Research, 12(Feb):349–384, 2011.