# Compatibility of Poisson–Lie transformations and symmetries of Generalized
Supergravity Equations

Ladislav<EMAIL_ADDRESS>
Faculty of Nuclear Sciences and Physical Engineering,
Czech Technical University in Prague,
Czech Republic

###### Abstract

We investigate two types of transformations that keep NS-NS Generalized
Supergravity Equations satisfied : $\chi$-symmetry (20) that shifts dilaton
and gauge transformations (30) that change both dilaton and vector field $J$.
Due to these symmetries there is a large set of dilatons and vector fields $J$
that (for a fixed metric and B-field) satisfy Generalized Supergravity
Equations but only some of them can be be used as input for Poisson–Lie
transformations. Conditions that define the admissible dilatons are given and
examples are presented.

###### Contents

  1. 1 Introduction
  2. 2 Poisson–Lie transformations and  Generalized Supergravity Equations
  3. 3 Symmetries of Generalized Supergravity Equations
    1. 3.1 $\chi$-symmetry
      1. 3.1.1 Example 1
      2. 3.1.2 Example 2
    2. 3.2 Gauge transformations
      1. 3.2.1 Example 3, trivial - identical transformation of flat background
  4. 4 Choice of Poisson–Lie compatible gauge
    1. 4.1 Example 1 - continued
    2. 4.2 Example 2 - continued
  5. 5 Conclusion
  6. 6 Appendix: Poisson–Lie transformations of the tensor field

##  1 Introduction

Poisson–Lie transformation of solutions of Generalized Supergravity Equations
must include dilatons and Killing fields. Formula for transformation of
dilaton field $\Phi$ accompanying Poisson–Lie transformation [1, 2] of sigma
model background ${\mathcal{F}}={\mathcal{G}}+{\mathcal{B}}$ was given in [3]
(see also [4, 5, 6]). Formula for Poisson–Lie transformation of Killing field
$J$ was given in [7, 8]. Later it turned out that the the latter formula works
well only for non-Abelian T-duality, i.e. for Poisson–Lie transformations of
sigma models with isotropic backgrounds, and it was extended in [9] for other
type of transformations. Unfortunately, applicability of these formulas is
dependent on choice of initial dilatons related by symmetries of solution
space of Generalized Supergravity Equations. It turns out that transformed
dilatons and vector fields $J$ keep validity of Generalized Supergravity
Equations in dependence on the choice on the initial dilaton. Examples of
these cases are given below.

Goal of this paper is to discuss compatibility of Poisson–Lie transformation
of dilaton and Killing field with transformations that leave invariant (NS-NS
part of) Generalized Supergravity Equations and give conditions for
applicability of the transformations.

##  2 Poisson–Lie transformations and
Generalized Supergravity Equations

Poisson–Lie duality/plurality is based on the possibility to pass between
various decompositions of Drinfel’d double $\mathscr{D}$ that generates
background of investigated sigma models. It is a $2d$-dimensional Lie group
whose Lie algebra ${\mathfrak{d}}$ can be decomposed into double cross sum of
Lie subalgebras ${\mathfrak{g}}$ and $\tilde{\mathfrak{g}}$ that are maximally
isotropic with respect to non-degenerate symmetric bilinear ad-invariant form
$\langle.,.\rangle$. Drinfel’d double with so called Manin triple
$({\mathfrak{d}},{\mathfrak{g}},\tilde{\mathfrak{g}})$ and Lie subgroups
$\mathscr{G},\widetilde{\mathscr{G}}$ corresponding to
${\mathfrak{g}},\tilde{\mathfrak{g}}$ is denoted by
$(\mathscr{G}|\widetilde{\mathscr{G}})$.

Assume that there is $d$-dimensional Lie group $\mathscr{G}$ whose action on
$\mathscr{M}$ is smooth, proper and free. The action of $\mathscr{G}$ is
transitive on its orbits, hence we may locally consider
$\mathscr{M}\approx(\mathscr{M}/\mathscr{G})\times\mathscr{G}=\mathscr{N}\times\mathscr{G}$,
$\dim\mathscr{M}=\dim\mathscr{N}+\dim\mathscr{G}=n+d$ and introduce adapted
coordinates

$\\{y^{\mu}\\}=\\{s_{\alpha},y^{a}\\},$ (1)

where $y^{a}$ are group coordinates and $s_{\alpha}$ label the orbits of
$\mathscr{G}$,

$\mu=1,\ldots\dim\mathscr{M},\ \alpha=1,\ldots,n=\dim\mathscr{N},\ \
a=1,\ldots,d=\dim\mathscr{G}.$ (2)

Coordinates $s_{\alpha}$ are treated as ”spectators” as they do not
participate in Poisson–Lie transformations.

Poisson–Lie dualizable sigma models on $\mathscr{N}\times\mathscr{G}$ are
given by tensor field

${\mathcal{F}}={\mathcal{F}}(y^{\mu})={\mathcal{F}}(s_{\alpha},y^{a}),$ (3)

that satisfy [1, 2]

$({\cal
L}_{v_{i}}{\mathcal{F}})_{\mu\nu}={\mathcal{F}}_{\mu\kappa}v^{\kappa}_{j}\tilde{f}_{i}^{jk}v^{\lambda}_{k}{\mathcal{F}}_{\lambda\nu},\
i=1,\ldots,\dim\mathscr{G},$ (4)

where $v_{i}$ form basis of left–invariant fields on $\mathscr{G}$ and
$\tilde{f}_{i}^{jk}$ are structure coefficients of th Lie group
$\widetilde{\mathscr{G}}$. Explicit form of dualizable tensors ${\mathcal{F}}$
and their Poisson–Lie transformed forms are given in the Appendix.

The NS-NS part of Generalized Supergravity Equations
${GSE({\mathcal{F}},\Phi,J)}$ read [10, 11]

$\displaystyle 0$
$\displaystyle=R_{\mu\nu}-\frac{1}{4}H_{\mu\rho\sigma}H_{\nu}^{\
\rho\sigma}+\nabla_{\mu}X_{\nu}+\nabla_{\nu}X_{\mu},$ (5) $\displaystyle 0$
$\displaystyle=-\frac{1}{2}\nabla^{\rho}H_{\rho\mu\nu}+X^{\rho}H_{\rho\mu\nu}+\nabla_{\mu}X_{\nu}-\nabla_{\nu}X_{\mu},$
(6) $\displaystyle 0$
$\displaystyle=R-\frac{1}{12}H_{\rho\sigma\tau}H^{\rho\sigma\tau}+4\nabla_{\mu}X^{\mu}-4X_{\mu}X^{\mu}$
(7)

where $R_{\mu\nu}$ is Ricci tensor of metric $\mathcal{G}$,
$R=R_{\mu}{}^{\mu}$,

$H_{\rho\mu\nu}=\partial_{\rho}{\mathcal{B}}_{\mu\nu}+\partial_{\mu}{\mathcal{B}}_{\nu\rho}+\partial_{\nu}{\mathcal{B}}_{\rho\mu}$
(8)

and

$X_{\mu}:=\partial_{\mu}\Phi+J^{\kappa}{\mathcal{F}}_{\kappa\mu}.$ (9)

For the NS-NS part of Generalized Supergravity Equations (5)-(7) it is not
necessary to require that $J$ be Killing vector field of $\mathcal{G},H,\phi$
even though it is it is required for their full version containing the R-R
fields. Goal of this section is to define Poisson–Lie transformations of the
fields $\phi,J$ that keep the equations (5)-(7) satisfied.

Let Drinfel’d double has two decomposition
$\mathscr{D}=(\mathscr{G}|\widetilde{\mathscr{G}})=(\widehat{\mathscr{G}}|\bar{\mathscr{G}})$.
Transformation of dilaton under Poisson–Lie T-plurality can be expresed as

$\Phi^{0}(s,y)=:\Phi(s,y)-\frac{1}{2}L(s,y)=\widehat{\Phi}(s,\hat{x})-\frac{1}{2}\widehat{L}(s,\hat{x})$
(10)

where $\Phi(s,y),\widehat{\Phi}(s,\hat{x})$ are dilatons of the initial and
transformed model. Variables $y$ represent coordinates of group $\mathscr{G}$,
$\hat{x}$ are coordinates of group $\widehat{\mathscr{G}}$, and terms
$L(s,y)$, $\widehat{L}(s,\hat{x})$ read

$L(s,y)=\ln\Big{|}\frac{(\det\mathcal{G}(s,y))^{1/2}}{\det
u(y)}\Big{|},\quad\widehat{L}(s,\hat{x})=\ln\Big{|}\frac{(\det\widehat{\mathcal{G}}(s,\hat{x}))^{1/2}}{\det\hat{u}(\hat{x})}\Big{|},$
(11)

where $\mathcal{G}$ and $\widehat{\mathcal{G}}$ are metrics of sigma models on
$\mathscr{N}\times\mathscr{G}$ resp. $\mathscr{N}\times\widehat{\mathscr{G}}$.
Matrices $u$, $\hat{u}$ are components of left-invariant forms of
$\mathscr{G}$ and $\widehat{\mathscr{G}}$.

In cases when the invariant dilaton $\Phi^{0}$ in (10) depends on coordinates
$y$ we have to express $y$ in terms of $\hat{x}$ and $\bar{x}$ to get explicit
form of transformed dilaton $\widehat{\Phi}(s,\hat{x})$. This can be done by
solving relation between two different decompositions of elements of Drinfel’d
double
$\mathscr{D}=(\mathscr{G}|\widetilde{\mathscr{G}})=(\widehat{\mathscr{G}}|\bar{\mathscr{G}})$.

$g(y)\tilde{h}(\tilde{y})=\widehat{g}(\hat{x})\bar{h}(\bar{x}),\quad
g\in\mathscr{G},\ \tilde{h}\in\tilde{\mathscr{G}},\
\widehat{g}\in\widehat{\mathscr{G}},\ \bar{h}\in\bar{\mathscr{G}}$ (12)

so that

$y^{k}=Y^{k}(\hat{x},\bar{x}),\quad\tilde{y}^{k}=\tilde{Y}^{k}(\hat{x},\bar{x}).$
(13)

If $\Phi^{0}(s,y)$ after the insertion (13) into (10) dependends linearly on
dual-coordinates $\bar{x}_{a}$

$\widehat{\Phi}^{0}(s,\hat{x},\bar{x}):=\Phi^{0}(s,Y(\hat{x},\bar{x}))=\widehat{\Phi}^{0}(s,\hat{x})+\bar{d}^{a}\,\bar{x}_{a}$
(14)

then we can transform dilaton $\Phi$ and vector field $J$ in the following way
(see [7, 8]).

$\widehat{\Phi}(s,\hat{x})=\widehat{\Phi}^{0}(s,\hat{x})+\frac{1}{2}\widehat{L}(s,\hat{x})$
(15)
$\widehat{\mathcal{J}}^{\alpha}=0,\qquad\alpha=1,\ldots,n=\dim\mathscr{N},$
$\mathcal{\widehat{J}}^{\dim\mathscr{N}+m}(s,\hat{x})=\left(\frac{1}{2}{{\bar{f}}^{ab}}{}_{b}-\bar{d}^{a}\right){\widehat{v}_{a}}{}^{m}(\hat{x})$
(16)

The above formulas work well for isometric models, i.e. if
$\widetilde{\mathscr{G}}$ is abelian. For some more general type of models
transformation of Killing field must be extended to [9]

$\widehat{\mathcal{J}}^{\alpha}=0,\qquad\alpha=1,\ldots,n=\dim\mathscr{N},$
$\displaystyle\mathcal{\widehat{J}}^{\dim\mathscr{N}+m}(s,\hat{x})=$
$\displaystyle\frac{1}{2}{{\widetilde{f}}^{ab}}{}_{b}\left(\frac{\partial{\widetilde{y}_{a}}}{\partial\bar{x}_{k}}{\widehat{v}_{k}}{}^{m}(\hat{x})-\frac{\partial{\widetilde{y}_{k}}}{\partial\widehat{x}^{a}}\widehat{\mathcal{F}}^{km}\right)+$
$\displaystyle+\left(\frac{1}{2}{{\bar{f}}^{ab}}{}_{b}-\bar{d}^{a}\right){\widehat{v}_{a}}{}^{m}(\hat{x})$
(17)

where $a,b,k,m=1,\ldots,\dim\mathscr{G}$, ${\widetilde{f}}^{ba}{}_{c}$ and
${\bar{f}}^{ba}{}_{c}$ are structure constants of Lie algebras of
$\widetilde{\mathscr{G}},\,\bar{\mathscr{G}}$ and $\widehat{v}_{a}$ are left-
invariant fields of the group $\widehat{\mathscr{G}}$. This modification does
not change results of [8, 12] and [13] because those papers deal with
isotropic initial models whose corresponding Manin triples
$({\mathfrak{d}},{\mathfrak{g}},\tilde{\mathfrak{g}})$ are semiabelian, i.e.
${{\widetilde{f}}^{ab}}{}_{b}=0$.

##  3 Symmetries of Generalized Supergravity Equations

Let $({\mathcal{F}},\Phi,J)$ satisfy Generalized Supergravity Equations and
there is a a symmetry of these equations, i.e. transformation
$({\mathcal{F}},\Phi,J)\mapsto({\mathcal{F}}^{\prime},\Phi^{\prime},J^{\prime})$
that keep the Generalized Supergravity Equations satisfied

$GSE({\mathcal{F}},\Phi,J)\Leftrightarrow
GSE({\mathcal{F}}^{\prime},\Phi^{\prime},J^{\prime}).$ (18)

We shall call this symmetry _Poisson–Lie compatible_ if
$(\widehat{\mathcal{F}}^{\prime},\widehat{\Phi}^{\prime},\widehat{J}^{\prime})$
obtained by Poisson–Lie transformation of
(${\mathcal{F}}^{\prime},\Phi,J^{\prime})$ satisfy Generalized Supergravity
Equations as well, i.e. if

$GSE({\mathcal{F}}^{\prime},\Phi^{\prime},J^{\prime})\Leftrightarrow
GSE(\widehat{\mathcal{F}}^{\prime},\widehat{\Phi}^{\prime},\widehat{J}^{\prime}).$
(19)

Our aim is finding symmetries compatible with Poisson–Lie transformations (15)
and (16) or (17).

###  3.1 $\chi$-symmetry

First symmetry we are going to investigate is shift of form $X$. For
torsionless backgrounds, which are all examples below, it is easy to see that
if $X_{\mu}$ satisfy the Generalized Supergravity Equations, then

$X^{\prime}_{\mu}:=X_{\mu}+\chi_{\mu},$ (20)

where

$\nabla_{\nu}\chi_{\mu}=0,\quad(X_{\mu}+2\,\chi_{\mu})\chi^{\mu}=0,$ (21)

satisfy the equations as well. Due to the former condition form $\chi$ is
(locally) exact so that $\chi=d\psi$ and this symmetry is just
($t,x$-dependent) shift of dilaton

$\Phi^{\prime}=\Phi+\psi.$ (22)

Note that the vector field $J$ remains unchanged.

Unfortunately, in many cases $\chi$-symmetries are not Poisson–Lie compatible.

####  3.1.1 Example 1

Solving the equations (21) for flat metric222We work with four-dimensional
models invariant w.r.t. three-dimensional groups so that $dim\mathscr{N}=1$,
and spectator is denoted as $t$.

$ds^{2}=-dt^{2}+t^{2}\,dy_{1}^{2}+t^{2}\,{e}^{2y_{1}}dy_{2}^{2}+t^{2}\,{e}^{2y_{1}}dy_{3}^{2}$
(23)

with coordinates adapted to its Bianchi 5 symmetry

$[T^{1},T^{2}]=T^{2},\quad[T^{1},T^{3}]=T^{3},$ (24)

and dilaton $\Phi=0$ we get

$\chi_{\mu}=(C_{1}\,e^{y_{1}},C_{1}\,t\,e^{y_{1}},0,0),\quad\Phi^{\prime}=\psi=C_{1}\,t\,e^{y_{1}}+C_{0}$
(25)

By nonabelian T-duality given by the matrix

$C=\left(\begin{array}[]{cccccc}0&0&0&1&0&0\\\ 0&0&0&0&1&0\\\ 0&0&0&0&0&1\\\
1&0&0&0&0&0\\\ 0&1&0&0&0&0\\\ 0&0&1&0&0&0\\\ \end{array}\right)$ (26)

we get (see Appendix)

$\widehat{\mathcal{F}}_{\mu\nu}=\left(\begin{array}[]{cccc}-1&0&0&0\\\
0&\frac{t^{2}}{t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}}&\frac{{\hat{x}}_{2}}{t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}}&\frac{{\hat{x}}_{3}}{t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}}\\\
0&-\frac{{\hat{x}}_{2}}{t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}}&\frac{t^{4}+{\hat{x}}_{3}^{2}}{t^{2}\left(t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}\right)}&-\frac{{\hat{x}}_{2}{\hat{x}}_{3}}{t^{2}\left(t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}\right)}\\\
0&-\frac{{\hat{x}}_{3}}{t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}}&-\frac{{\hat{x}}_{2}{\hat{x}}_{3}}{t^{2}\left(t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}\right)}&\frac{t^{4}+{\hat{x}}_{2}^{2}}{t^{2}\left(t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}\right)}\\\
\end{array}\right)$ (27)

but if $C_{1}\neq 0$ _we cannot apply formulas ( 15) and (16) or (17) for the
non-Abelian T-duality_ (and some other Poisson–Lie T-pluralities) as the
condition (14) for its application does not hold because

$\widehat{\Phi}^{0}\,{}^{\prime}(t,\hat{x},\bar{x})=C_{1}\,t\,e^{\bar{x}_{1}}+C_{0}+\bar{x}_{1}-\frac{3}{2}\log\,t.$

####  3.1.2 Example 2

Background

${\mathcal{F}}_{\mu\nu}=\left(\begin{array}[]{cccc}1&0&0&0\\\
0&0&e^{-y_{1}}y_{1}&e^{-y_{1}}\\\ 0&e^{-y_{1}}y_{1}&e^{-2y_{1}}&0\\\
0&e^{-y_{1}}&0&0\\\ \end{array}\right)$ (28)

that corresponds to the flat metric adapted to Bianchi 4 symmetry satisfy
Generalized Supergravity Equations together with vanishing X-form. Solving the
equations (21) we get

$\displaystyle\Phi^{\prime}=\psi=$ $\displaystyle
C_{0}+{C_{1}}\,t+{C_{2}}e^{-y_{1}}+{C_{3}}\left(y_{1}+e^{-y_{1}}y_{2}\right)$
$\displaystyle+{C_{4}}\left(\frac{1}{2}e^{-y_{1}}y_{2}^{2}+\left(y_{1}-1\right)y_{2}-\frac{e^{y_{1}}}{2}+y_{3}\right)$
(29)

where the latter condition of (21) implies

$C_{1}{}^{2}+C_{3}{}^{2}-2\,C_{2}C_{4}=0.$

The background (28), dilaton (29) and vanishing $J$ satisfy Generalized
Supergravity Equations but once again we cannot apply formulas (15) and (16)
or (17) for non-Abelian T-duality as the condition (14) is satisfied only if
$\Phi^{\prime}=C_{0}.$

###  3.2 Gauge transformations

Another symmetry of NS-NS Generalized Supergravity Equations is gauge
transformation333Note that this symmetry is different from the the
transformation of B-field $B_{\lambda}=B+d\lambda$ investigated e.g. in [14,
15]

${\mathcal{F}}_{\Lambda}:={\mathcal{F}},\quad\Phi_{\Lambda}:=\Phi+\Lambda\quad
J_{\Lambda}:=J-d\Lambda.{\mathcal{F}}^{-1}$ (30)

where $\Lambda$ is arbitrary (differentiable) function of $(s,y)$. It leaves
$X$ invariant, $X=X_{\Lambda}$, so that

${GSE({\mathcal{F}}_{\Lambda},\Phi_{\Lambda},J_{\Lambda})}\Leftrightarrow
GSE({\mathcal{F}},\Phi,J).$ (31)

Contrary to this, formulas (15) and (16) or (17) for Poisson–Lie
transformation of dilaton and Killing field _do not provide solution of
Generalized Supergravity Equations for arbitrary $\Lambda$._

$GSE({\mathcal{F}}_{\Lambda},\Phi_{\Lambda},J_{\Lambda})<\neq>{GSE(\widehat{\mathcal{F}}_{\Lambda},\widehat{\Phi}_{\Lambda},\widehat{J}_{\Lambda})}.$

####  3.2.1 Example 3, trivial - identical transformation of flat background

Let us investigate the simplest Poisson–Lie transformation - identity of the
flat model (23) with $\mathcal{B}$-field vanishing. This background together
with

$\Phi=0,\quad J^{\mu}=(0,0,0,0),\quad X_{\mu}=(0,0,0,0),$ (32)

obviously satisfy Generalized Supergravity Equations. Besides that, identical
Poisson–Lie transformation of (32) gives the same fields $\phi,J,X$.

However, Generalized Supergravity Equations are satisfied also for

$\Phi_{\Lambda}=\Lambda,\quad
J^{\mu}_{\Lambda}=-\partial_{\nu}\Lambda\,\mathscr{G}^{\nu\mu},\quad{\mathcal{F}}_{\Lambda}={\mathcal{F}},\quad
X_{\Lambda}=(0,0,0,0)$ (33)

where $\Lambda$ is arbitrary function of $(t,y_{1},y_{2},y_{3})$. Choosing for
example $\Lambda=y_{1}$ we get

$\Phi=y_{1},\ J^{\mu}=(0,\frac{-1}{t^{2}},0,0).$ (34)

Applying formulas (15) and (16) for identical Poisson–Lie transformation to
(34) we find

$\widehat{\Phi}=\hat{x}_{1},\quad\widehat{J}^{\mu}=(0,0,0,0),\quad\widehat{\mathcal{F}}_{\Lambda}={\mathcal{F}},\quad\widehat{X}_{\Lambda}=(0,1,0,0)$

and Generalized Supergravity Equations are not satisfied.

This simple example shows that _Poisson–Lie transformations are not in general
compatible with gauge transformations_ and that the condition (14) is not
sufficient for applicability of the formulas (15) and (16) or (17).

Note that the field $J$ in (34) in the latter case is not Killing field of the
flat metric. It may give a clue for restriction of the gauge transformations.

##  4 Choice of Poisson–Lie compatible gauge

We have seen that in spite of the fact that due to symmetries there can be
quite large set of dilatons and vector fields $J$ that satisfy Generalized
Supergravity Equations, only very limited subset of them are Poisson–Lie
compatible. By inspection of the formulas (15) and (16) one can see that the
problem is in fulfilling the condition (14) for invariant dilaton $\Phi^{0}$
shifted both by $\chi$-symmetry and gauge transformation

$\Phi^{0}\,{}^{\prime}(s,y)=\Phi^{0}(s,y)+\psi(s,y)+\Lambda(s,y).$ (35)

Fortunately, we can use the arbitrariness of the gauge function $\Lambda$ to
satisfy the condition (14). On the other hand, we know from the example 3.2.1
that gauge transformations in general are not compatible with Poisson–Lie
transformation so that they must be further restricted.

Condition that the field $J$ is Killing vector of the background
${\mathcal{F}}={\mathcal{G}}+{\mathcal{B}}$ (up to an exact 2-form) is not
necessary for satisfying NS-NS Generalized Supergravity Equations but it is
required for their full version containing the R-R fields [11]. Beside that,
dilaton must also be invariant in direction of $J$. Therefore, if
$({\mathcal{F}},\Phi,J)$ satisfy Generalized Supergravity Equations (5)-(7) we
will require for $\Lambda$

$\mathcal{L}_{J_{\Lambda}}{\mathcal{G}}=0,\quad\mathcal{L}_{J_{\Lambda}}{\mathcal{B}}=d\omega,\quad\mathcal{L}_{J_{\Lambda}}\Phi=0$
(36)

where and $J_{\Lambda}:=J-d\Lambda.{\mathcal{F}}^{-1}$. It turns out that
_these additional conditions together with ( 14) are sufficient for
compatibility of Poisson–Lie transformations with symmetries introduced in the
Sec. 3._

###  4.1 Example 1 - continued

Let $\mathcal{B}$-field is vanishing, background is given by the flat metric
(23), vanishing $J$-field and dilaton obtained by $\chi$-symmetry and gauge
transformation

$\Phi^{\prime}(t,y)=C_{1}\,t\,e^{y_{1}}+C_{0}+\Lambda(t,y_{1},y_{2},y_{3}).$
(37)

They satisfy Generalized Supergravity Equations. Condition (14) for non-
Abelian T-duality is fulfilled for

$\Lambda=-C_{1}\,t\,e^{y_{1}}+\Lambda_{0}(t)+\lambda_{1}y_{1}+\lambda_{2}\,y_{2}+\lambda_{3}\,y_{3}.$
(38)

Requiring that $J_{\Lambda}$ is Killing vector of flat metric (23), and
dilaton (37) we get

$\Lambda_{0}(t)=\lambda_{1}=\lambda_{2}=\lambda_{3}=0.$

This gauge is compatible with T-duality of background (23) dilaton (37) and
vanishing $J$-field. This means that only the trivial dilaton
$\Phi^{\prime}=C_{0}$ can be dualized by formulas (15), (16). By the non-
Abelian T-dual given by (26) we get the background (27) and formulas (15),
(16) yield [16]

$\widehat{\Phi}=-\frac{1}{2}\log\left(-t^{2}\left(t^{4}+{\hat{x}}_{2}^{2}+{\hat{x}}_{3}^{2}\right)\right),\quad\widehat{J}^{\mu}=(0,2,0,0).$
(39)

Generalized Supergravity Equations are satisfied for these fields.

Let us note that repeating the Poisson–Lie transformation given by (26) on the
tensor field (27) we return to flat metric (23) but dual dilaton and vector
$J$ given by(15) and (17) are of the form (34) that differ from the initial
ones (32) by gauge transformation $\Lambda=y_{1}$.

###  4.2 Example 2 - continued

Let $\mathcal{B}$-field is vanishing, background is given by the flat metric
(28), vanishing $J$-field and by dilaton

$\displaystyle\Phi^{\prime}=$ $\displaystyle
C_{0}+{C_{1}}\,t+{C_{2}}e^{-y_{1}}+{C_{3}}\left(y_{1}+e^{-y_{1}}y_{2}\right)$
(40)
$\displaystyle+{C_{4}}\left(\frac{1}{2}e^{-y_{1}}y_{2}^{2}+\left(y_{1}-1\right)y_{2}-\frac{e^{y_{1}}}{2}+y_{3}\right)+\Lambda(t,y_{1},y_{2},y_{3}).$
(41)

They satisfy Generalized Supergravity Equations. Condition (14) for T-duality
given by (26) is fulfilled if

$\displaystyle\Lambda=$
$\displaystyle{c_{0}}+{c_{1}}y_{2}+{c_{2}}y_{3}+\frac{1}{2}\left({C_{4}}e^{y_{1}}-e^{-y_{1}}\left(2{C_{2}}+2{C_{3}}y_{2}+{C_{4}}y_{2}^{2}\right)\right)+$
(42) $\displaystyle+y_{1}\left({c_{4}}-{C_{4}}y_{2}\right)+\Lambda_{0}(t).$
(43)

Requiring that $J_{\Lambda}$ is Killing vector of flat metric (28), and
dilaton (40) one gets

$c_{1}=-c_{2}=C_{4},\quad c_{4}=-C_{3},\quad\Lambda_{0}(t)={c_{5}}-{C_{1}}t.$

This gauge eliminates $\chi$-symmetry shift in (40) up to constant and only
the trivial dilaton $\Phi^{\prime}=C_{0}$ can be dualized by formulas (15),
(16). We get

$\widehat{\Phi}=\widehat{C}_{0}-\frac{1}{2}\log\left(\hat{x}_{3}{}^{2}-1\right),\quad\widehat{J}=(0,-2,0,0)$
(44)

that together with

$\widehat{\mathcal{F}}=\left(\begin{array}[]{cccc}1&0&0&0\\\
0&0&0&\frac{1}{1-\hat{x}_{3}}\\\
0&0&1&\frac{\hat{x}_{3}-\hat{x}_{2}}{\hat{x}_{3}-1}\\\
0&\frac{1}{\hat{x}_{3}+1}&\frac{\hat{x}_{3}-\hat{x}_{2}}{\hat{x}_{3}+1}&\frac{(\hat{x}_{2}-\hat{x}_{3})^{2}}{\hat{x}_{3}{}^{2}-1}\\\
\end{array}\right),$ (45)

obtained by (55)-(58), satisfy Generalized Supergravity Equations.

On the other hand, let us note that there are Poisson–Lie transformations that
impose weaker restriction on the gauge transformations and therefore admit a
wider subset of dilatons that can be Poisson–Lie transformed. It is for
example Poisson–Lie T-plurality $(4|1)\rightarrow(6_{-1}|2)$ of (28), (40)
given by

$C=\left(\begin{array}[]{cccccc}-1&0&0&0&0&0\\\ 0&0&0&0&1&0\\\ 0&0&-1&0&0&0\\\
0&0&0&-1&0&0\\\ 0&1&0&0&0&0\\\ 0&0&0&0&0&-1\\\ \end{array}\right)$ (46)

Condition (14) then gives $C_{1}=C_{3}=C_{4}=0$ and

$\Lambda=\Lambda_{1}(t,y_{1},y_{3})+\Lambda_{2}(y_{1},y_{3})+\Lambda_{3}(y_{1})+c_{1}y_{2}.$
(47)

Requiring further that $J_{\Lambda}$ is Killing vector of flat metric (28),
and dilaton (40), i.e. satisfies (36), one gets finally

$\Lambda=c_{2}+c_{3}e^{-y_{1}},\quad\Phi^{\prime}=C_{0}+{C_{2}}\,e^{-y_{1}}+c_{2}+c_{3}e^{-y_{1}}$
(48)

All these dilatons can be pluralized. Poisson–Lie T-plurality induced by (46)
then gives

$\widehat{\mathcal{F}}=\left(\begin{array}[]{cccc}1&0&0&0\\\
0&-{\hat{x}}_{1}^{2}&-e^{-x_{1}}{\hat{x}}_{1}&e^{{\hat{x}}_{1}}\\\
0&e^{-{\hat{x}}_{1}}{\hat{x}}_{1}&e^{-2{\hat{x}}_{1}}&0\\\
0&e^{{\hat{x}}_{1}}&0&0\\\ \end{array}\right)$ (49)
$\widehat{\Phi}=C_{0}+(C_{2}+c_{3})\,e^{{\hat{x}}_{1}},\quad\widehat{J}=(0,0,0,0)$
(50)

and Generalized Supergravity Equations are satisfied.

##  5 Conclusion

We have investigated two types of transformations that keep NS-NS part of
Generalized Supergravity Equations satisfied. They are $\chi$-symmetry (20)
for torsionless sigma models, that shifts dilaton only, and gauge
transformations (30) that change both dilaton and vector field $J$ but leave
the form

$X_{\mu}:=\partial_{\mu}\Phi+J^{\kappa}{\mathcal{F}}_{\kappa\mu}.$

invariant. Due to these symmetries there is a large set of dilatons and vector
fields $J$ that satisfy Generalized Supergravity Equations for fixed tensor
field ${\mathcal{F}}$.

We have shown that Poisson–Lie transformations are not in general compatible
with the above mentioned symmetries - see Examples 1,2,3. In other words,
formulas (15), (16) or (17) for Poisson–Lie transformations of dilatons and
vector fields $J$ can be applied only to a rather narrow subset of dilatons in
order that the transformed fields satisfy Generalized Supergravity Equations.

The applicability of the formulas (15), (16) or (17) is restricted
1) By the condition (14) requiring that the invariant dilaton $\Phi^{0}$ given
by (10) is linear in the dual coordinates $\bar{x}$.
2) By the conditions (36) that fixes the admissible gauges, namely, that gauge
transformed vector field $J_{\Lambda}$ is Killing vector of metric, torsion
and dilaton. It is interesting that this condition of Poisson–Lie
compatibility is identical with condition for full Generalized Supergravity
Equations containing the R-R fields.

Within these restrictions Poisson–Lie transformations keep Generalized
Supergravity Equations satisfied - see Examples 1,2 continued. Typically it
chooses just one dilaton and Killing vector field but it is not a rule as
shown in the subsection 4.2. We have checked several other cases of
Poisson–Lie duality/plurality with equal results.

Besides that we have found that twice applied T-duality produces identical
dilatons but vector fields $J$ only up to a gauge transformation. It means
that, diferently from transformations of tensor fields (55) - (58), the above
mentioned formulas do not provide true representation of $O(d,d)$.

##  6 Appendix: Poisson–Lie transformations of the tensor field

For many Drinfel’d doubles several decompositions may exist. Suppose that we
have sigma model on $\mathscr{N}\times\mathscr{G}$ and tensor field
${\mathcal{F}}$ satisfies equation (4). Let Drinfel’d double
$\mathscr{D}=(\mathscr{G}|\widetilde{\mathscr{G}})$ splits into another pair
of Lie subgroups $\widehat{\mathscr{G}}$ and $\bar{\mathscr{G}}$ so that
$(\mathscr{G}|\widetilde{\mathscr{G}})=(\widehat{\mathscr{G}}|\bar{\mathscr{G}})$.
Then we can apply the full framework of Poisson–Lie T-plurality [1, 3] and
find tensor field $\widehat{\mathcal{F}}$ for sigma model on
$\mathscr{N}\times\widehat{\mathscr{G}}$ in the following way.

Poisson–Lie dualizable sigma models on $\mathscr{N}\times\mathscr{G}$
satisfying (4) are given by tensor field ${\mathcal{F}}$ of the form

${\mathcal{F}}(s,y)=\mathcal{E}(y)\cdot\left(\mathbf{1}_{n+d}+E(s)\cdot\Pi(y)\right)^{-1}\cdot
E(s)\cdot\mathcal{E}^{T}(y)$ (51)

where $E(s)$ is spectator-dependent $(n+d)\times(n+d)$ matrix. Denoting
generators of Manin triple
$({\mathfrak{d}},{\mathfrak{g}},\tilde{\mathfrak{g}})$ as $T,\tilde{T}$,
matrix $\Pi(y)$ is given by submatrices $a(y)$ and $b(y)$ of the adjoint
representation

$ad_{{g}^{-1}}(\widetilde{T})=b(y)\cdot T+a^{-1}(y)\cdot\widetilde{T}$

as

$\Pi(y)=\left(\begin{array}[]{cc}\mathbf{0}_{n}&0\\\ 0&b(y)\cdot
a^{-1}(y)\end{array}\right).$

Matrix $\mathcal{E}(y)$ reads

$\mathcal{E}(y)=\left(\begin{array}[]{cc}\mathbf{1}_{n}&0\\\
0&e(y)\end{array}\right)$ (52)

where $e(y)$ is $d\times d$ matrix of components of right-invariant
Maurer–Cartan form $(dg)g^{-1}$ on $\mathscr{G}$.

Manin triples $({\mathfrak{d}},{\mathfrak{g}},\tilde{\mathfrak{g}})$ and
$({\mathfrak{d}},\hat{\mathfrak{g}},\bar{\mathfrak{g}})$ are two
decompositions of Lie algebra ${\mathfrak{d}}$ into double cross sum of
subalgebras that are maximally isotropic with respect to $\langle.,.\rangle$.
Pairs of mutually dual bases $T_{a}\in{\mathfrak{g}},\
\widetilde{T}^{a}\in\tilde{\mathfrak{g}}$ and
$\widehat{T}_{a}\in\hat{\mathfrak{g}},\ \bar{T}^{a}\in{\bar{\mathfrak{g}}}$,
$a=1,\ldots,d,$ then must be related by transformation

$\begin{pmatrix}\widehat{T}\\\ \bar{T}\end{pmatrix}=C\cdot\begin{pmatrix}T\\\
\widetilde{T}\end{pmatrix}$ (53)

where $C$ is an invertible $2d\times 2d$ matrix. (Non-Abelian) T-duality is
obtained by

$C=\begin{pmatrix}0&\mathbf{1}_{d}\\\ \mathbf{1}_{d}&0\end{pmatrix}.$

Poisson–Lie T-plurality is given by $d\times d$ matrices $P,Q,R,S$ such that

$\begin{pmatrix}T\\\
\widetilde{T}\end{pmatrix}=C^{-1}\cdot\begin{pmatrix}\widehat{T}\\\
\bar{T}\end{pmatrix}=\begin{pmatrix}P&Q\\\
R&S\end{pmatrix}\cdot\begin{pmatrix}\widehat{T}\\\ \bar{T}\end{pmatrix}.$ (54)

For the following formulas it is convenient to extend matrices $P,Q,R,S$ to
$(n+d)\times(n+d)$ matrices

$\mathcal{P}=\begin{pmatrix}\mathbf{1}_{n}&0\\\
0&P\end{pmatrix},\quad\mathcal{Q}=\begin{pmatrix}\mathbf{0}_{n}&0\\\
0&Q\end{pmatrix},\quad\mathcal{R}=\begin{pmatrix}\mathbf{0}_{n}&0\\\
0&R\end{pmatrix},\quad\mathcal{S}=\begin{pmatrix}\mathbf{1}_{n}&0\\\
0&S\end{pmatrix}$

to accommodate the spectator fields.

Sigma model on $\mathscr{N}\times\widehat{\mathscr{G}}$ obtained from (51) via
Poisson–Lie T-plurality is given by tensor field

$\widehat{{\mathcal{F}}}(s,\hat{x})=\mathcal{\widehat{E}}(\hat{x})\cdot\widehat{E}(s,\hat{x})\cdot\mathcal{\widehat{E}}^{T}(\hat{x}),\qquad\mathcal{\widehat{E}}(\hat{x})=\begin{pmatrix}\mathbf{1}_{n}&0\\\
0&\widehat{e}(\hat{x})\end{pmatrix},$ (55)

where $\widehat{e}(\hat{x})$ is $d\times d$ matrix of components of right-
invariant Maurer–Cartan form $(d\hat{g})\hat{g}^{-1}$ on
$\widehat{\mathscr{G}}$ and

$\widehat{E}(s,\hat{x})=\left(\mathbf{1}_{n+d}+\widehat{E}(s)\cdot\widehat{\Pi}(\hat{x})\right)^{-1}\cdot\widehat{E}(s)=\left(\widehat{E}^{-1}(s)+\widehat{\Pi}(\hat{x})\right)^{-1}.$
(56)

The matrix $\widehat{E}(s)$ is obtained from $E(s)$ in (51) by formula

$\widehat{E}(s)=(\mathcal{P}+E(s)\cdot\mathcal{R})^{-1}\cdot(\mathcal{Q}+E(s)\cdot\mathcal{S}),$
(57)

and

$\widehat{\Pi}(\hat{x})=\left(\begin{array}[]{cc}\mathbf{0}_{n}&0\\\
0&\widehat{b}(\hat{x})\cdot\widehat{a}^{-1}(\hat{x})\end{array}\right),$
$ad_{{\hat{g}}^{-1}}(\bar{T})=\widehat{b}(\hat{x})\cdot\widehat{T}+\widehat{a}^{-1}(\hat{x})\cdot\bar{T}.$
(58)

## References

  * [1] C. Klimčík and P. Ševera, _Dual non-Abelian duality and the Drinfeld double_ , Phys. Lett. B 351 (1995) 455, [hep-th/9502122].
  * [2] C. Klimčík, _Poisson–Lie T-duality_ , Nucl. Phys. B (Proc. Suppl.) 46 (1996) 116, [hep-th/9509095].
  * [3] R. von Unge, _Poisson–Lie T-plurality_ , J. High Energ. Phys. 07 (2002) 014, [hep-th/0205245].
  * [4] S. Demulder, F. Hassler, and D. C. Thompson, _An invitation to Poisson-Lie T-duality in Double Field Theory and its applications_ , [arXiv:1904.09992].
  * [5] R. Borsato and L. Wulff, _Quantum correction to generalized T-dualities_ , Phys. Rev. Lett. 125, (2020) 201603, [arXiv:2007.07902].
  * [6] T. Codina and D. Marques, _Generalized Dualities and Higher Derivatives_ , J. High Energ. Phys. 10 (2020) 002, [arXiv:2007.09494].
  * [7] S. Demulder, F. Hassler, D. C. Thompson, _Doubled aspects of generalised dualities and integrable deformations_ , J. High Energ. Phys. 2019, 189 (2019), [arXiv:1810.11446].
  * [8] Y. Sakatani, _Type II DFT solutions from Poisson-Lie T-duality/plurality_ , Progress of Theoretical and Experimental Physics 073B04 (2019), [arXiv:1903.12175].
  * [9] L. Hlavatý and I. Petr, _Poisson-Lie transformations and Generalized Supergravity Equations_ , Eur. Phys. J. C 81 (2021) 484, [arXiv:2101.12053 ].
  * [10] L. Wulff and A. A. Tseytlin, _Kappa-symmetry of superstring sigma model and generalized 10d supergravity equations_ , J. High Energ. Phys. 06 (2016) 174, [arXiv:1605.04884].
  * [11] G. Arutyunov, S. Frolov, B. Hoare, R. Roiban, and A. A. Tseytlin, _Scale invariance of the $\eta$-deformed $AdS_{5}\times S^{5}$ superstring, T-duality and modified type II equations_, Nucl. Phys. B 903 (2016) 262, [arXiv:1511.05795].
  * [12] M. Honga, Y. Kima, and E. Ó Colgáin, _On non-Abelian T-duality for non-semisimple groups_ , Eur. Phys. J. C 78 (2018) 1025, [arXiv:1801.09567].
  * [13] L. Hlavatý and I. Petr, _Poisson–Lie plurals of Bianchi cosmologies and Generalized Supergravity Equations_ , J. High Energ. Phys. 04 (2020) 068, [arXiv:1910.08436].
  * [14] T. Araujo, E. Ó Colgáin, J. Sakamoto, M. M. Sheikh-Jabbari, K. Yoshida, _I in generalized supergravity_ , The European Physical Journal C volume 77, (2017), 739 [arXiv:1708.03163].
  * [15] I. Bakhmatov, Ö. Kelekci, E. Ó Colgáin, M. M. Sheikh-Jabbari _Classical Yang-Baxter Equation from Supergravity_ , Phys. Rev. D 98, (2018) 021901 [arXiv:1710.06784].
  * [16] L. Hlavatý and I. Petr, _Poisson–Lie identities and dualities of Bianchi cosmologies_ , [arXiv:1905.13627]


11institutetext: UC San Diego
11email<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>
# Behavior of k-NN as an Instance-Based Explanation Method

Chhavi Yadav Kamalika Chaudhuri

###### Abstract

Adoption of DL models in critical areas has led to an escalating demand for
sound explanation methods. Instance-based explanation methods are a popular
type that return selective instances from the training set to explain the
predictions for a test sample. One way to connect these explanations with
prediction is to ask the following counterfactual question - how does the loss
and prediction for a test sample change when explanations are removed from the
training set? Our paper answers this question for k-NNs which are natural
contenders for an instance-based explanation method. We first demonstrate
empirically that the representation space induced by last layer of a neural
network is the best to perform k-NN in. Using this layer, we conduct our
experiments and compare them to influence functions (IFs) [6] which try to
answer a similar question. Our evaluations do indicate change in loss and
predictions when explanations are removed but we do not find a trend between
$k$ and loss or prediction change. We find significant stability in the
predictions and loss of MNIST vs. CIFAR-10. Surprisingly, we do not observe
much difference in the behavior of k-NNs vs. IFs on this question. We
attribute this to training set subsampling for IFs.

###### Keywords:

k-NN Explainability Instance-based Interpretability Representations Influence
Functions

##  1 Introduction

Deep Learning (DL) models have shown a great deal of promise in providing high
accuracy predictions; however, these accurate predictions come at the cost of
high opacity. As they are being adopted in critical applications, it is
becoming increasingly important to explain their predictions and interpret
them.

A popular class of explanation methods is instance-based explanations. Here
the goal is to select instances from the training set to explain why an input
is assigned a particular label. k-Nearest Neighbors (k-NN), which provide the
top $k$ most similar instances to a test sample, are natural contenders for
instance-based explanations. The idea of using k-NNs as an explanation method
dates back to the 1990s [2]. It has recently made a come back like in [7].
However, the utility of k-NNs as an instance-explanation method has not been
investigated thoroughly.

One way to establish the connection between explanations and prediction is to
see how the prediction and loss at a test sample change when explanations are
removed from the training set. We call this the ‘counterfactual question’. In
this work, we take a closer look at k-NNs as instance-based explanations in
the context of the above counterfactual question. We compare our k-NN results
with removing the most influential training points according to influence
function (IF) score from [6].

To answer this, we first find what is a good representation space in which to
choose the nearest neighbors? In the case of a neural network $f$,
representation spaces are induced by different layers of $f$. We find that the
last layer is the best – in the sense that k-NN using representations of the
last layer approximates the decision boundary of $f$ the best amongst all
layers.

Section 3 discusses our experimental setups and results in detail. Overall, we
do see a change in loss and predictions sans the $k$ nearest neighbors. We
observe a significant stability in the predictions and loss of MNIST compared
to CIFAR-10. However, we do not observe an increasing trend between the value
of $k$ and loss or prediction change. In terms of k-NN vs. IFs, we do not
observe much difference in their behaviors. We attribute this to subsampling
the training set in the IF case and call for a deeper investigation.

##  2 Related Work

Instance-based explanations are a popular interpretability tool. Several such
methods exist including Counterfactual explanations [9],[3], Prototypes and
Criticisms [4], [8], k-NNs [2], [7] and Influence Functions [6], [5], [1].
Each of them has a different definition and hence a different way of selecting
the instance explanations.

Counterfactual explanation method starts with any training instance & modifies
it to reduce the counterfactual loss. The output explanation instance hence
need not be from the training set. Prototype based explanation methods first
find a representative set of points to describe the data using maximum mean
discrepancy and provide the nearest-prototype as explanations for a given test
instance. Influence functions estimate the influence of a training sample or
set of training samples on a test sample by estimating the change in loss
without those training samples. However, they tend to return outliers as noted
in [1]. Given a test sample, k-NNs simply return the k nearest neighbors in a
specified representation space as explanations. In this work, we dive deeper
into the properties of k-NN as an explanation method.

##  3 Experiments & Results

Our goal in this section is to address the following questions:

  * •

Which representation space induced by the different layers of a neural network
$f$ is best for finding k-NNs?

  * •

How does removing the top $k$ nearest neighbors (offered as explanations) from
the training data affect the prediction on a test input?

These questions are considered in the context of two standard datasets – MNIST
and CIFAR-10. For MNIST we use a custom model as shown in table 1, while for
CIFAR-10 we used a Wide-ResNet [10] with depth and width 10.

###  3.1 The Choice of Representation

Since k-NN is a distance based method, the distance function and
representation space in which these distances are found, are two significant
aspects that affect its output. In a neural network $f$, each layer induces
its own representation space $\phi_{layer}$, giving k-NN an option to choose
amongst these.

#### Label Agreement

: We say that label agreement happens for a test point when the label
predicted by nearest neighbor and the neural network are the same. We find the
fraction of test points for which label agreement happens in different layers
of $f$. As this fraction approaches 1, gap between the decision boundaries of
k-NN and $f$ reduces, becoming approximately the same, when tested with large
number of samples. If this occurs, then k-NN is a global approximator of the
neural network.

#### Setup

: We take 1000 samples from the test set of each dataset, with equal
contributions from all classes. We find the 1-NNs from the training set using
representations from various layers of the neural network. We compare labels
from 1-NN to those predicted by the neural network. We use cosine distance
function.

#### Result

: From tables 1 and 2 it is clear that as we go from first layer to the last,
the fraction of points with label agreement increases. For MNIST, the fraction
approaches 1 at the last layer, while for CIFAR-10, it approaches 0.9. Since
k-NN in the last layer approximates decisions of $f$ the best, we use
$\phi_{last}$ as our k-NN representation space.

Table 1:  Fraction of points for which the label predicted by 1-NN and neural network are same on MNIST Layer | Fraction
---|---
conv_relu | 0.962
conv_relu_maxpool | 0.977
conv_relu | 0.979
conv_relu_maxpool | 0.983
fc | 0.995
relu_drop_fc | 0.997
relu_fc | 0.998
Table 2:  Fraction of points for which the label predicted by 1-NN and neural network are same on CIFAR-10 Layer | Fraction
---|---
conv | 0.328
block1_block2_block3 | 0.756
batchnorm_relu_avgpool | 0.877
fc | 0.881

###  3.2 Effect of Removing Explanatory Instances

Given a test sample $x$, our k-NN explainer (in $\phi_{last}$) would return
the top $k$ nearest neighbors of $x$ from the training set as explanations. In
this section, we want to understand the effect of removing these $k$ samples
from the training set on the prediction and loss at $x$. In [6], the authors
define highly influence points to be those training points that when removed
from the training set, lead to the largest change in loss at $x$. Therefore,
we compare our results to influence functions.

#### Setup

: We take 500 random samples from the test set and find their top $k$ nearest
neighbors from the training set using $\phi_{last}$ and cosine distance
function. $k\in[1,5,10,15,20]$. For each test sample $x$, we remove these k
nearest neighbors from the training set and retrain a model from scratch using
the new training set, keeping other parameters fixed. We note the loss change
(LC) and predicted labels for the test samples before and after retraining. A
Positive LC implies that the loss at $x$ increased due to removal of the $k$
nearest neighbors from the training set. Similarly, a change in predicted
label before and after retraining, which we call a label flip, implies some
effect was caused by removal of the k nearest neighbors.

We compare our results to Influence Functions (IFs). For each test sample $x$,
we find the top $k$ influential points using the definition in [6] and follow
the same procedure as above. Calculating influence is an expensive task since
for each test sample, it takes $O(np+rtp$) time, where $rt=O(n)$, $n$ = size
of dataset, $r$ = repeats, $t$ = iterations & $p$ = model parameters, as
mentioned in [6]. Hence, due to computational constraints, we use some
commonplace tricks. We test using 100 random test samples. When searching for
influential samples in the training set we look in a subsampled training
dataset of size 1000. However, we retrain with the complete training set minus
the top $k$ influential samples. We freeze all but last layer weights.

#### Results

: As is evident from Table 3 and 5, we do see a loss and prediction change
when top $k$ nearest neighbors are removed from training set. However, there
is no particular increasing trend between the value of $k$ and loss change or
label flips. This is counter-intuitive since one would expect removing more
samples would lead to potentially worse learning and hence higher loss change.
A plausible explanation can be that there is enough information in the rest of
the training samples to learn. Hence, removing a few does not matter much,
unless the test sample is noisy or an outlier.

We also note that predictions on MNIST are more stable than CIFAR-10, in the
sense that the loss change and percentage of label flips from table 5 for
MNIST are way lower than that for CIFAR-10. This reiterates the belief that
MNIST is an easier dataset and has less intraclass diversity in the samples.

Contrasting the results of k-NN and Influence functions, we do not observe
much difference in behavior. Removing top $k$ nearest neighbors vs.
influential points has almost similar effects. This maybe due to subsampling
the training set for influence functions for computational reasons & calls for
further investigation.

Table 3: k-NN : For various k, loss change (LC) at test samples between retrained and original models. Average(Avg.) LC is the average across all test samples, Avg. +ve & -ve LC are the average positive & negative loss change across respective test samples, Max. & Min. LC note the maximum & minimum loss change across all test samples, +ve LC % notes the percentage of test samples with a $\geq$ 0 LC.  Dataset | k | Avg. LC | Avg. +ve LC | Avg. -ve LC | Max. LC | Min. LC | +ve LC %
---|---|---|---|---|---|---|---
| 1 | 0.009 $\pm$ 0.177 | 0.015 $\pm$ 0.180 | -0.040 $\pm$ 0.146 | 2.622 | -0.752 | 89.6
| 5 | 0.019 $\pm$ 0.499 | 0.026 $\pm$ 0.525 | -0.040 $\pm$ 0.148 | 11.107 | -0.786 | 89.2
MNIST | 10 | 0.029 $\pm$ 0.452 | 0.036 $\pm$ 0.473 | -0.036 $\pm$ 0.133 | 9.392 | -0.624 | 90.4
| 15 | 0.024 $\pm$ 0.327 | 0.031 $\pm$ 0.340 | -0.040 $\pm$ 0.136 | 5.375 | -0.553 | 91.0
| 20 | 0.034 $\pm$ 0.535 | 0.043 $\pm$ 0.560 | -0.050 $\pm$ 0.163 | 8.354 | -0.747 | 90.4
| 1 | -0.407 $\pm$ 2.018 | 0.751 $\pm$ 1.597 | -0.908 $\pm$ 1.975 | 8.514 | -19.012 | 30.2
| 5 | -0.446 $\pm$ 1.866 | 0.647 $\pm$ 1.238 | -0.928 $\pm$ 1.893 | 6.169 | -15.23 | 30.6
CIFAR-10 | 10 | -0.342 $\pm$ 2.643 | 1.009 $\pm$ 3.227 | -0.954 $\pm$ 2.057 | 35.885 | -19.441 | 31.2
| 15 | -0.075 $\pm$ 3.134 | 1.516 $\pm$ 4.383 | -0.851 $\pm$ 1.844 | 44.61 | -19.101 | 32.8
| 20 | -0.526 $\pm$ 1.954 | 0.483 $\pm$ 1.084 | -0.965 $\pm$ 2.082 | 6.984 | -18.344 | 30.3
Table 4: Influence Functions : For various k, loss change (LC) at test samples between retrained and original models. Average(Avg.) LC is the average across all test samples, Avg. +ve & -ve LC are the average positive & negative loss change across respective test samples, Max. & Min. LC note the maximum & minimum loss change across all test samples, +ve LC % notes the percentage of test samples with a $\geq$ 0 LC.  Dataset | k | Avg. LC | Avg. +ve LC | Avg. -ve LC | Max. LC | Min. LC | +ve LC %
---|---|---|---|---|---|---|---
| 1 | -0.00019 $\pm$ 0.002 | 1.3e-05 $\pm$ 8e-05 | -0.00285 $\pm$ 0.007 | 0.0006 | -0.02 | 93
| 5 | 7e-05 $\pm$ 0.003 | 0.00029 $\pm$ 0.002 | -0.00346 $\pm$ 0.008 | 0.0185 | -0.02 | 94
MNIST | 10 | -0.00021 $\pm$ 0.002 | 2e-06 $\pm$ 2e-05 | -0.00232 $\pm$ 0.006 | 0.0001 | -0.02 | 91
| 15 | -0.00018 $\pm$ 0.002 | 4e-06 $\pm$ 3e-05 | -0.00229 $\pm$ 0.006 | 0.0003 | -0.018 | 92
| 20 | -0.00018 $\pm$ 0.002 | 2e-05 $\pm$ 1e-04 | -0.00343 $\pm$ 0.008 | 0.0007 | -0.02 | 94
| 1 | -0.43 $\pm$ 1.544 | 0.464 $\pm$ 1.039 | -0.87 $\pm$ 1.562 | 5.373 | -8.501 | 33
| 5 | -0.349 $\pm$ 1.334 | 0.666 $\pm$ 1.187 | -0.688 $\pm$ 1.201 | 4.416 | -4.998 | 25
CIFAR-10 | 10 | -0.447 $\pm$ 1.637 | 0.494 $\pm$ 1.037 | -0.89 $\pm$ 1.68 | 4.319 | -8.891 | 32
| 15 | -0.539 $\pm$ 1.623 | 0.378 $\pm$ 0.948 | -1.077 $\pm$ 1.694 | 4.323 | -6.95 | 37
| 20 | -0.475 $\pm$ 1.351 | 0.314 $\pm$ 0.699 | -0.797 $\pm$ 1.418 | 3.398 | -7.776 | 29
Table 5: Percentage of label flips over test samples, between the retrained and original models when the top $k$ nearest neighbors & the top $k$ influential samples are removed from the training set. k | MNIST k-NN | MNIST IF | CIFAR k-NN | CIFAR IF
---|---|---|---|---
1 | 0.8 | 0 | 21.2 | 23
5 | 0.6 | 0 | 23.2 | 19
10 | 1 | 0 | 22.8 | 22
15 | 0.6 | 0 | 23.4 | 19
20 | 0.8 | 0 | 19.48 | 21

##  4 Conclusion

We present an investigation into the behavior of k-NN as an instance-based
explanation method. First, we demonstrate that representation space induced by
the last layer of a neural network is the best to find neighbors in. Following
this, we try to connect explanations and predictions by probing the
counterfactual question - what happens when the k nearest neighbors of a test
sample are removed from the training set? How are the loss and prediction
affected?

From our experiments we do see a change in loss and predictions. However, we
do not find signs of an increasing relationship between the value of $k$ and
loss or prediction change. We also find evidence for stable predictions on
MNIST than CIFAR-10.

We do not observe much difference between the behavior of k-NN vs. IFs. We
believe that this could be due to subsampling the training set for
computational constraints. A future direction can be to investigate this more
thoroughly with the complete training set, though it is a difficult task in
reality.

We conclude by saying that when choosing an explanation method, it’s of utmost
importance to think carefully about what the application is and if the
properties of the explanation method match the requirements. In line of this,
we call for a deeper investigation into the properties of explanation methods.

## References

  * [1] Barshan, E., Brunet, M.E., Dziugaite, G.K.: Relatif: Identifying explanatory training samples via relative influence. In: International Conference on Artificial Intelligence and Statistics. pp. 1899–1909. PMLR (2020)
  * [2] Caruana, R., Kangarloo, H., Dionisio, J.D., Sinha, U., Johnson, D.: Case-based explanation of non-case-based learning methods. In: Proceedings of the AMIA Symposium. p. 212. American Medical Informatics Association (1999)
  * [3] Karimi, A.H., Barthe, G., Balle, B., Valera, I.: Model-agnostic counterfactual explanations for consequential decisions. In: International Conference on Artificial Intelligence and Statistics. pp. 895–905. PMLR (2020)
  * [4] Kim, B., Koyejo, O., Khanna, R., et al.: Examples are not enough, learn to criticize! criticism for interpretability. In: NIPS. pp. 2280–2288 (2016)
  * [5] Koh, P.W., Ang, K.S., Teo, H.H., Liang, P.: On the accuracy of influence functions for measuring group effects. arXiv preprint arXiv:1905.13289 (2019)
  * [6] Koh, P.W., Liang, P.: Understanding black-box predictions via influence functions. In: International Conference on Machine Learning. pp. 1885–1894. PMLR (2017)
  * [7] Rajani, N.F., Krause, B., Yin, W., Niu, T., Socher, R., Xiong, C.: Explaining and improving model behavior with k nearest neighbor representations. arXiv preprint arXiv:2010.09030 (2020)
  * [8] RDUSSEEUN, L., KAUFMAN, P.: Clustering by means of medoids (1987)
  * [9] Wachter, S., Mittelstadt, B., Russell, C.: Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL & Tech. 31, 841 (2017)
  * [10] Zagoruyko, S., Komodakis, N.: Wide residual networks. arXiv preprint arXiv:1605.07146 (2016)


Figure 7: Graphs $G(r)$ as $r$ is varied, for lower bound construction for
pseudodimension of $\mathcal{H}_{r}$.

Now as $r$ is increased to $r_{1}$, the edges $(b_{i},u_{1})$, $i=1,2$ are
added with $b_{i}$ labeled as $f(b_{i})=0$. This results in a fractional label
of $\frac{1}{3}$ for $f(u_{1})$ while $f(u_{k})=1$ for $k\neq 1$. Indeed the
terms involving $f(u_{1})$ in the objective are
$(1-f(u_{1}))^{2}+2f(u_{1})^{2}$, which is minimized at $\frac{1}{3}$. Since
$u_{1}$ has true label $b$, this results in a slightly smaller loss of
$l_{A(G(r_{1}),L)}=:l_{\text{low}}$. This happens when $A$ uses rounding, or
in expectation if $A$ uses randomized prediction with probability $f(u)$.

At the next critical point $r_{2}$, $u_{2}$ gets connected to $b_{i}$’s and
gets incorrectly classified as $b$. This increases the loss again to
$l_{\text{high}}$. The loss function thus alternates as $r$ is varied through
the specified values, between $l_{\text{high}}$ and $l_{\text{low}}$. We
therefore set the witness $w$ to something in between.

$w=\frac{l_{\text{low}}+l_{\text{high}}}{2}.$

∎

###### Proof of Theorem 16.

We will now use Lemma 33 to prove our lower bound. Arbitarily choose
$n^{\prime}=n-5$ (assumed to be a power of 2 just for convenient presentation)
real numbers $r_{[000\dots 01]}<r_{[000\dots 10]}<\dots<r_{[111\dots 11]}$ in
$(1,2)$. The indices are increasing binary numbers of length $m=\log
n^{\prime}$. We create labeling instances using Lemma 33 which can be
shattered by these $r$ values. Instance $S_{i}=(G_{i},L_{i})$ corresponds to
fluctuation of $i$-th bit $b_{i}$ in our $r_{b}$ sequence, where
$b=(b_{1},\dots,b_{m})\in\\{0,1\\}^{m}$, i.e., we apply the lemma by using a
subset of the $r_{b}$ values which correspond to the bit flips in the $i$-th
binary digit. For example, $S_{1}$ just needs a single bit flip (at
$r_{[100\dots 00]}$). The lemma gives us both the instances and corresponding
witnesses $w_{i}$.

This construction ensures
$\text{sign}(l_{A(G_{i}(r_{b}),L_{i})}-w_{i})=b_{i}$, i.e. the set of
instances is shattered. Thus the pseudodimension is at least
$\log(n-5)=\Omega(\log n)$.

∎

See 18

###### Proof.

The plan for the proof is to first construct a graph where the edge weights
are carefully selected, so that we have $2^{N}$ oscillations in the loss
function with $\sigma$ for $N=\Omega(n)$. Then we use this construction to
create $\Theta(n)$ instances, each having a subset of the oscillations so that
each interval leads to a unique labeling of the instances, for a total of
$2^{N}$ labelings, which would imply pseudodimension is $\Omega(n)$. We will
present our discussion in terms of the min-cut objective, for simplicity of
presentation.

Graph construction: First a quick rough overview. We start with a pair of
labeled nodes of each class, and a pair of unlabeled nodes which may be
assigned either label depending on $\sigma$. We then build the graph in
$N=(n-4)/2$ stages, adding two new nodes at each step with carefully chosen
distances from existing nodes. Before adding the $i$th pair $x_{i},y_{i}$ of
nodes, there will be $2^{i-1}$ intervals of $\sigma$ such that the intervals
correspond to distinct min-cuts which result in all possible labelings of
$\\{x_{1},\dots,x_{i-1}\\}$. Moreover, $y_{j}$ will be labeled differently
from $x_{j}$ in each of these intervals. The edges to the new nodes will
ensure that the cuts that differ exactly in $x_{i}$ will divide each of these
intervals giving us $2^{i}$ intervals where distinct mincuts give all
labelings of $\\{x_{1},\dots,x_{i}\\}$, and allowing an inductive proof. The
challenge is that we only get to set $O(i)$ edges but seek properties about
$2^{i}$ cuts, so we must do this carefully.

Let $\varsigma=e^{-1/\sigma^{2}}$. Notice $\varsigma\in(0,1)$, and bijectively
corresponds to $\sigma\in(0,\infty)$ (due to monotonicity) and therefore it
suffices to specify intervals of $\varsigma$ corresponding to different
labelings. Further we can specify distances $d(u,v)$ between pairs of nodes
$u,v$ by specifying the squared distance $d(u,v)^{2}$. For the remainder of
this proof we will refer to $\delta(u,v)=d(u,v)^{2}$ by distance and set
values in $[1.5,1.6]$. Consequently, $d(u,v)\in(1.22,1.27)$ and therefore the
triangle inequality is always satisfied. Notice that with this notation, the
graph weights will be $w(u,v)=\varsigma^{\delta(u,v)}$.

We now provide details of the construction. We have four labeled nodes as
follows. $a_{1},a_{2}$ are labeled 0 and are collectively denoted by
$A=\\{a_{1},a_{2}\\}$, similarly $b_{1},b_{2}$ are labeled 1 and
$B=\\{b_{1},b_{2}\\}$. Note that edges between these nodes are on all or no
cut separating $A,B$, we set the distances to 1.6 and call this graph $G_{0}$.
We further add unlabeled nodes in pairs $(x_{j},y_{j})$ in rounds $1\leq j\leq
N$. In round $i$, we construct graph $G_{i}$ by adding nodes $(x_{i},y_{i})$
to $G_{i-1}$. The distances are set to ensure that for $G_{N}$ there are
$2^{N}$ unique values of $\varsigma$ corresponding to distinct min-cuts, each
giving a unique labeling for $\\{x_{1},\dots,x_{n}\\}$ (and the complementary
labeling for $\\{y_{1},\dots,y_{n}\\}$). Moreover subsets of these points also
obtain the unique labeling for $\\{x_{1},\dots,x_{i}\\}$ for each $G_{i}$.

$A$$B$$y_{1}$$x_{1}$$a_{1}$$a_{2}$$b_{1}$$b_{2}$$1.5\ +\ \epsilon$$1.5\ +\
\epsilon$$1.5$$1.5+12N\epsilon$$1.5+12N\epsilon$$1.5+12N\epsilon$$1.5$$1.5\ +\
\epsilon$$1.5\ +\ \epsilon$ Figure 8: The base case of our inductive
construction.

We set the distances in round 1 such that there are intervals
$I_{0}=(\varsigma_{0},\varsigma^{\prime}_{0})\subset(0,1)$ and
$I_{1}=(\varsigma_{1},\varsigma^{\prime}_{1})\subset(0,1)$ such that
$\varsigma^{\prime}_{0}<\varsigma_{1}$ and $(x_{1},y_{1})$ are labeled
$(l,1-l)$ in interval $I_{l}$. In general, there will be $2^{i-1}$ intervals
at the end of round $i-1$, any interval $I^{(i-1)}$ will be split into
disjoint intervals $I^{(i)}_{0},I^{(i)}_{1}\subset I^{(i-1)}$ where labelings
of $\\{x_{1},\dots,x_{i-1}\\}$ match that of $I^{(i-1)}$ and $(x_{i},y_{i})$
are labeled $(l,1-l)$ in $I^{(i)}_{l}$.

Now we set up the edges to achieve these properties. In round 1, we set the
distances as follows.

$\displaystyle\delta(x_{1},a_{1})=\delta(y_{1},b_{2})$ $\displaystyle=1.5,$
$\displaystyle\delta(x_{1},a_{2})=\delta(y_{1},b_{1})=\delta(x_{1},y_{1})$
$\displaystyle=1.5+12N\epsilon,$
$\displaystyle\delta(x_{1},b_{1})=\delta(x_{1},b_{2})=\delta(y_{1},a_{1})=\delta(y_{1},a_{2})$
$\displaystyle=1.5+\epsilon.$

where $\epsilon$ is a small positive quantity such that the largest distance
$1.5+12N\epsilon<1.6$. It is straightforward to verify that for
$I_{0}=(0,\frac{1}{2}^{1/\epsilon})$ we have that $(x_{1},y_{1})$ are labeled
$(0,1)$ by determining the values of $\varsigma$ for which the corresponding
cut is the min-cut (Figure 8). Indeed, we seek $\varsigma$ such that
$w_{C01}=w(x_{1},b_{1})+w(x_{1},b_{2})+w(x_{1},y_{1})+w(y_{1},a_{1})+w(y_{1},a_{2})$
satisfies

$w_{C01}\leq
w_{C00}=w(x_{1},b_{1})+w(x_{1},b_{2})+w(y_{1},b_{1})+w(y_{1},b_{2}),$
$w_{C01}\leq
w_{C11}=w(x_{1},a_{1})+w(x_{1},a_{2})+w(y_{1},a_{1})+w(y_{1},a_{2}),$
$w_{C01}\leq
w_{C10}=w(x_{1},a_{1})+w(x_{1},a_{2})+w(x_{1},y_{1})+w(y_{1},b_{1})+w(y_{1},b_{2}),$

which simultaneously hold for $\varsigma<\frac{1}{2}^{1/\epsilon}$.

Moreover, we can similarly conclude that $(x_{1},y_{1})$ are labeled $(1,0)$
for the interval $I_{1}=(\varsigma_{1},\varsigma^{\prime}_{1})$ where
$\varsigma_{1}<\varsigma^{\prime}_{1}$ are given by the two positive roots of
the equation

$1-2\varsigma^{\epsilon}+2\varsigma^{12N\epsilon}=0.$

We now consider the inductive step, to set the distances and obtain an
inductive proof of the claim above. In round $i$, the distances are as
specified.

$\displaystyle\delta(x_{i},a_{1})=\delta(y_{i},b_{2})$ $\displaystyle=1.5,$
$\displaystyle\delta(x_{i},a_{2})=\delta(y_{i},b_{1})=\delta(x_{i},y_{i})$
$\displaystyle=1.5+12N\epsilon,$
$\displaystyle\delta(x_{i},b_{1})=\delta(x_{i},b_{2})=\delta(y_{i},a_{1})=\delta(y_{i},a_{2})$
$\displaystyle=1.5+\epsilon,$
$\displaystyle\delta(x_{i},y_{j})=\delta(y_{i},x_{j})$
$\displaystyle=1.5+6(2j-1)\epsilon\;\;\;(1\leq j\leq i-1),$
$\displaystyle\delta(x_{i},x_{j})=\delta(y_{i},y_{j})$
$\displaystyle=1.5+12j\epsilon\;\;\;\;\;\;\;\;\;\;\;\;(1\leq j\leq i-1).$

We denote the (inductively hypothesized) $2^{i-1}$ $\varsigma$-intervals at
the end of round $i-1$ by $I_{\mathbf{b}}^{(i-1)}$, where
$\mathbf{b}=\\{b^{(1)},\dots,b^{(i-1)}\\}\in\\{0,1\\}^{i-1}$ indicates the
labels of $x_{j},j\in[i-1]$ in $I_{\mathbf{b}}^{(i-1)}$. Min-cuts from round
$i-1$ extend to min-cuts of round $i$ depending on how the edges incident on
$(x_{i},y_{i})$ are set (Figure 9). It suffices to consider only those min-
cuts where $x_{j}$ and $y_{j}$ have opposite labels for each $j$. Consider an
arbitrary such min-cut $C_{\mathbf{b}}=(A_{\mathbf{b}},B_{\mathbf{b}})$ of
$G_{i-1}$ which corresponds to the interval $I_{\mathbf{b}}^{(i-1)}$, that is
$A_{\mathbf{b}}=\\{x_{j}\mid b^{(j)}=0\\}\cup\\{y_{j}\mid b^{(j)}=1\\}$ and
$B_{\mathbf{b}}$ contains the remaining unlabeled nodes of $G_{i-1}$. It
extends to $C_{[\mathbf{b}\;0]}$ and $C_{[\mathbf{b}\;1]}$ for $\varsigma\in
I_{\mathbf{b}}^{(i-1)}$ satisfying, respectively,

$\displaystyle E_{\mathbf{b},0}(\varsigma):=$
$\displaystyle\;\;1-2\varsigma^{\epsilon}+F(C_{\mathbf{b}};\varsigma)>0,$
$\displaystyle E_{\mathbf{b},1}(\varsigma):=$
$\displaystyle\;\;1-2\varsigma^{\epsilon}+2\varsigma^{12N\epsilon}+F(C_{\mathbf{b}};\varsigma)<0,$

where $F(C_{\mathbf{b}};\varsigma)=\sum_{z\in
A_{\mathbf{b}}}\varsigma^{\delta(x_{i},z)}-\sum_{z\in
B_{\mathbf{b}}}\varsigma^{\delta(x_{i},z)}=\sum_{z\in
B_{\mathbf{b}}}\varsigma^{\delta(y_{i},z)}-\sum_{z\in
A_{\mathbf{b}}}\varsigma^{\delta(y_{i},z)}$. If we show that the solutions of
the above inequations have disjoint non-empty intersections with $\varsigma\in
I_{\mathbf{b}}^{(i-1)}$, our induction step is complete. We will use an
indirect approach for this.

$A_{\mathbf{b}}$$B_{\mathbf{b}}$$C_{\mathbf{b}}$$A$$B$$x_{i}$$y_{i}$ Figure 9:
The inductive step in our lower bound construction for pseudodimension of
$\mathcal{H}_{\sigma}$. The min-cut $C_{\mathbf{b}}$ is extended to two new
min-cuts (depicted by dashed lines) for which labels of $x_{i},y_{i}$ are
flipped, at controlled parameter intervals.

For $1\leq i\leq N$, given
$\mathbf{b}=\\{b^{(1)},\dots,b^{(i-1)}\\}\in\\{0,1\\}^{i-1}$, let
$E_{\mathbf{b},0}$ and $E_{\mathbf{b},1}$ denote the expressions (exponential
polynomials in $\varsigma$) in round $i$ which determine labels of
$(x_{i},y_{i})$, in the case where for all $1\leq j<i$, $x_{j}$ is labeled
$b^{(j)}$ (and let $E_{\phi,0},E_{\phi,1}$ denote the expressions for round
1). Let $\varsigma_{\mathbf{b},i}\in(0,1)$ denote the smallest solution to
$E_{\mathbf{b},i}=0$. Then we need to show the $\varsigma_{\mathbf{b},i}$’s
are well-defined and follow a specific ordering. This ordering is completely
specified by two conditions:

  1. (i)

$\varsigma_{[\mathbf{b}\;0],1}<\varsigma_{[\mathbf{b}],0}<\varsigma_{[\mathbf{b}],1}<\varsigma_{[\mathbf{b}\;1],0}$,
and

  2. (ii)

$\varsigma_{[\mathbf{b}\;0\;\mathbf{c}],1}<\varsigma_{[\mathbf{b}\;1\;\mathbf{d}],0}$

for all $\mathbf{b},\mathbf{c},\mathbf{d}\in\cup_{i<N}\\{0,1\\}^{i}$ and
$|\mathbf{c}|=|\mathbf{d}|$.

First we make a quick observation that all $\varsigma_{\mathbf{b},i}$’s are
well-defined and less than $(3/4)^{1/\epsilon}$. To do this, it will suffice
to note that $E_{\mathbf{b},i}(0)=1$ and
$E_{\mathbf{b},i}(\frac{3}{4}^{1/\epsilon})<0$ for all $\mathbf{b},i$, since
the functions are continuous in $(0,\frac{3}{4}^{1/\epsilon})$. This holds
because

$\displaystyle
E_{\mathbf{b},0}\left(\frac{3}{4}^{1/\epsilon}\right)<E_{\mathbf{b},1}\left(\frac{3}{4}^{1/\epsilon}\right)$
$\displaystyle=1-\frac{3}{2}+\left(\frac{3}{4}\right)^{12N}+F\left(C_{\mathbf{b}};\frac{3}{4}^{1/\epsilon}\right)$
$\displaystyle\leq-\frac{1}{2}+\left(\frac{3}{4}\right)^{12N}+\sum_{j=1}^{|\mathbf{b}|}\left(\frac{3}{4}\right)^{6j}\left(1-\left(\frac{3}{4}\right)^{6j}\right)$
$\displaystyle<-\frac{1}{2}+\sum_{j=1}^{N}\left(\frac{3}{4}\right)^{6j}$
$\displaystyle<0$

Let’s now consider condition (i). We begin by showing
$\varsigma_{[\mathbf{b}],0}<\varsigma_{[\mathbf{b}],1}$ for any $\mathbf{b}$.
The exponential polynomials $E_{\mathbf{b},0}$ and $E_{\mathbf{b},1}$ both
evaluate to 1 for $\varsigma=0$ (since
$|A_{\mathbf{b}}|=|B_{\mathbf{b}}|=|\mathbf{b}|$) and decrease monotonically
(verified by elementary calculus) till their respective smallest zeros
$\varsigma_{[\mathbf{b}],0},\varsigma_{[\mathbf{b}],1}$. But then
$E_{\mathbf{b},1}(\varsigma_{[\mathbf{b}],0})=2(\varsigma_{[\mathbf{b}],0})^{12N\epsilon}>0$,
which implies $\varsigma_{[\mathbf{b}],0}<\varsigma_{[\mathbf{b}],1}$. Now, to
show $\varsigma_{[\mathbf{b}\;0],1}<\varsigma_{[\mathbf{b}],0}$, note that
$E_{[\mathbf{b}\;0],1}(\varsigma)-E_{[\mathbf{b}],0}(\varsigma)=2\varsigma^{12N\epsilon}+\varsigma^{12i\epsilon}-\varsigma^{(12i-6)\epsilon}=\varsigma^{(12i-6)\epsilon}(2\varsigma^{(12(N-i)+6)\epsilon}+\varsigma^{6\epsilon}-1)$
where $1\leq i=|\mathbf{b}|+1<N$. Since
$\varsigma_{[\mathbf{b}],0}<\frac{3}{4}^{1/\epsilon}$, it follows that
$E_{[\mathbf{b}\;0],1}(\varsigma_{[\mathbf{b}],0})<0$, which implies
$\varsigma_{[\mathbf{b}\;0],1}<\varsigma_{[\mathbf{b}],0}$. Similarly, it is
readily verified that
$\varsigma_{[\mathbf{b}],1}<\varsigma_{[\mathbf{b}\;1],0}$, establishing (i).

Finally, to show (ii), note that
$E_{[\mathbf{b}\;0\;\mathbf{c}],1}(\varsigma)-E_{[\mathbf{b}\;0\;\mathbf{d}],0}(\varsigma)=2\varsigma^{12N\epsilon}+\varsigma^{12i\epsilon}-\varsigma^{(12i-6)\epsilon}+\varsigma^{12i\epsilon}(F(C_{\mathbf{c}};\varsigma)-F(C_{\mathbf{d}};\varsigma))=\varsigma^{(12i-6)\epsilon}(2\varsigma^{(12(N-i)+6)\epsilon}+\varsigma^{6\epsilon}-1+\varsigma^{6\epsilon}(F(C_{\mathbf{c}};\varsigma)-F(C_{\mathbf{d}};\varsigma)))$.
Again, similar to above, we use
$\varsigma_{[\mathbf{b}\;0\;\mathbf{d}],0}<\frac{3}{4}^{1/\epsilon}$ in this
expression to get
$E_{[\mathbf{b}\;0\;\mathbf{c}],1}(\varsigma_{[\mathbf{b}\;0\;\mathbf{d}],0})<0$.
Since the exponential polynomials decay monotonically with $\varsigma$ till
their first roots, (ii) follows.

${{\varsigma_{\phi,1}}}$${{\varsigma_{\phi,0}}}$${{\varsigma_{0,1}}}$${{\varsigma_{0,0}}}$${{\varsigma_{1,1}}}$${{\varsigma_{1,0}}}$${{\varsigma_{[0,0],1}}}$${{\varsigma_{[0,0],0}}}$${{\varsigma_{[0,1],1}}}$${{\varsigma_{[0,1],0}}}$${{\varsigma_{[1,0],1}}}$${{\varsigma_{[1,0],0}}}$${{\varsigma_{[1,1],1}}}$${{\varsigma_{[1,1],0}}}$
Figure 10: Relative positions of critical values of the parameter
$\varsigma=e^{-1/\sigma^{2}}$.

Problem instances: We will now show the graph instances and witnesses to
establish the pseudodimension bound. Our graphs will be $G_{i}$ from the above
construction (padded appropriately such that the min-cut intervals do not
change, if we insist each instance has exactly $n$ nodes), and the shattering
family $\sigma_{b}$ ($b=(b_{1},\dots,b_{N})\in\\{0,1\\}^{N}$) will be $2^{N}$
values of $\sigma$ corresponding to the $2^{N}$ intervals of $\varsigma$ with
distinct min-cuts in $G_{N}$ described above. To obtain the witnesses, we set
the labels so that only the last pair of nodes $(x_{i},y_{i})$ have different
labels (i.e. labels are same for all $(x_{j},y_{j}),j<i$) and therefore the
loss function oscillates $2^{i}$ times as $(x_{i},y_{i})$ are correctly and
incorrectly labeled in alternating intervals. The intervals of successive
$G_{i}$ are nested precisely so that $\sigma_{b}$ shatter the instances for
the above labelings/witnesses. Thus, we have shown that the pseudodimension is
$\Omega(N)=\Omega((n-4)/2)=\Omega(n)$.∎

##  Appendix C Active Learning

See 21

###### Proof.

We first determine values of the graph parameter $\tilde{\alpha}$ for which
two candidate sets $S,T$ have the same heuristic utilities ($u^{S}=u^{T}$) in
Algorithm 5. As noted in the proof of Theorem 11, $f$ and $f^{L_{S}}$ are
rational polynomials in the graph parameter with degree at most $nd$. For
fixed $L_{S}$, we observe that $p^{L_{S}}$ is a rational polynomial in
$\tilde{\alpha}$ with degree $O(nd\ell)$. Putting together, the equation
$u^{S}=u^{T}$ simplifies to a polynomial equation in $\tilde{\alpha}$ with
degree $O(nd\ell 2^{\ell})$. Application of Lemma 24 implies that the
coefficients of the polynomial equation have bounded joint density, and
therefore the roots are $\frac{1}{2}$-dispersed. Accounting for all possible
subset pairs $S,T$ and their respective labelings $L_{S},L_{T}$, we obtain a
maximum of $(2n)^{2\ell}$ such equations. The discontinuities due to the
active learning algorithm $A^{\prime}$ are therefore dispersed.

At the same time, the discontinuities due to the semi-supervised procedure for
label prediction correspond to soft label flips for some $f^{L_{S}}$. This
gives $O((2n)^{\ell})$ polynomial equations of degree at most $nd$ whose roots
collectively contain the possible discontinuities in the loss function due to
algorithm $A$. On any $\epsilon$-interval we can apply Theorem 22 to bound the
number of roots for each of the polynomial equations and apply Theorem 23 to
show that this implies $\frac{1}{2}$-dispersion. ∎