* Whittier and Light [1999] Gregory S. Whittier and John C. Light.  Quantum/classical time-dependent self-consistent field treatment of Ar+HCO inelastic and dissociative scattering.  _Journal of Chemical Physics_ , 110(9):4280–4290, 1999.  doi: 10.1063/1.478291.
  * Wiebe et al. [2010] Nathan Wiebe, Dominic Berry, Peter Høyer, and Barry C Sanders.  Higher order decompositions of ordered operator exponentials.  _Journal of Physics A_ , 43(6):065203, 2010.  doi: 10.1088/1751-8113/43/6/065203.  arXiv:0812.0562.
  * Wilde [2017] Mark M. Wilde.  _Quantum Information Theory_.  Cambridge University Press, 2017.  doi: 10.1017/9781316809976.

##  Appendix A Continuous qDRIFT and Hamiltonian averaging

Poulin, Qarry, Somma, and Verstraete developed an algorithm for time-dependent
Hamiltonian simulation based on techniques of Hamiltonian averaging and Monte
Carlo estimation [42]. In this section, we discuss the relation between their
algorithm and our continuous qDRIFT.

Let $H(\tau)$ be a time-dependent Hamiltonian defined for $0\leq\tau\leq t$.
Assume that $H(\tau)$ is continuous, nonzero everywhere, and efficiently
simulable for each particular $\tau$. Then, Poulin et al.’s approach simulates
$H(\tau)$ for time $\tau\in[0,t]$ in two steps: (i) they replace the evolution
$\exp_{\mathcal{T}}\big{(}{-}i\int_{0}^{t}\mathrm{d}\tau\,H(\tau)\big{)}$ by
an ordinary matrix exponential $e^{-itH_{\text{av}}}$ of the average
Hamiltonian $H_{\text{av}}:=\frac{1}{t}\int_{0}^{t}\mathrm{d}\tau\,H(\tau)$
with an error that scales like $O\big{(}(t\left\lVert
H\right\rVert_{\infty,\infty})^{2}\big{)}$; (ii) they further implement
$\int_{0}^{t}\mathrm{d}\tau\,H(\tau)$ with Monte Carlo estimation by picking
$m$ random times and approximating $\int_{0}^{t}\mathrm{d}\tau\
H(\tau)\approx\frac{1}{m}\sum_{k=1}^{m}H(\tau_{k})$ with error
$O\big{(}t\left\lVert H\right\rVert_{\infty,\infty}/\sqrt{m}\big{)}$, the
result of which is further approximated by product formulas.

The approach of [42] is essentially a sampling-based algorithm and thus
similar in spirit to our continuous qDRIFT, except for a notable difference:
their algorithm scales with the $L^{\infty}$ norm instead of the $L^{1}$ norm.
Unfortunately, this drawback cannot be remedied merely by a better analysis of
the same algorithm. Indeed, they use a uniform distribution to pick random
times during the Monte Carlo estimation. This sampling ignores the
instantaneous norm $\left\lVert H(\tau)\right\rVert_{\infty}$ of the
Hamiltonian and therefore the resulting algorithm cannot scale with the
$L^{1}$ norm $\int_{0}^{t}\mathrm{d}\tau\left\lVert
H(\tau)\right\rVert_{\infty}$.

Instead, continuous qDRIFT uses a probability distribution that biases toward
those times with larger instantaneous norm. In Section 3, we proved that such
a sampling gives a direct simulation of time-dependent Hamiltonians with
complexity that scales with the $L^{1}$ norm. We now give an indirect
implementation: (i’) we show in Appendix A.1 that the error of replacing
$\exp_{\mathcal{T}}\big{(}-i\int_{0}^{t}\mathrm{d}\tau\,H(\tau)\big{)}$ by an
ordinary matrix exponential of $H_{\text{av}}$ scales like
$O\big{(}\left\lVert H\right\rVert_{\infty,1}^{2}\big{)}$, improving the
analysis of [42]; (ii’) we further prove in Appendix A.2 that the average
Hamiltonian can be simulated by continuous qDRIFT with $L^{1}$-norm scaling.
Combining these two steps, we see that the Monte Carlo estimation approach of
[42] is superseded by continuous qDRIFT.

###  A.1 Hamiltonian averaging

Let $H(\tau)$ be a time-dependent Hamiltonian defined for $0\leq\tau\leq t$
and assume that it is continuous and nonzero everywhere. Define

$\mathrm{E}(s,0):=\exp_{\mathcal{T}}\bigg{(}-i\int_{0}^{s}\mathrm{d}\tau\,H(\tau)\bigg{)},\qquad\mathrm{E}_{\text{av}}(s):=e^{-isH_{\text{av}}},$
(155)

where $H_{\text{av}}:=\frac{1}{t}\int_{0}^{t}\mathrm{d}\tau\,H(\tau)$ is the
average Hamiltonian. Our goal is to bound the distance between
$\mathrm{E}(s,0)$ and $\mathrm{E}_{\text{av}}(s)$ at $s=t$. Using the initial
condition $\mathrm{E}(0,0)=\mathrm{E}_{\text{av}}(0)=I$, we have

$\displaystyle\left\lVert\mathrm{E}(t,0)-\mathrm{E}_{\text{av}}(t)\right\rVert_{\infty}=$
$\displaystyle\left\lVert\mathrm{E}_{\text{av}}^{\dagger}(t)\mathrm{E}(t,0)-I\right\rVert_{\infty}=\left\lVert\int_{0}^{t}\mathrm{d}s\frac{\mathrm{d}}{\mathrm{d}s}\big{[}\mathrm{E}_{\text{av}}^{\dagger}(s)\mathrm{E}(s,0)\big{]}\right\rVert_{\infty}.$
(156)

By the Schrödinger equation

$\frac{\mathrm{d}}{\mathrm{d}s}\mathrm{E}_{\text{av}}(s)=-iH_{\text{av}}\mathrm{E}_{\text{av}}(s),\qquad\frac{\mathrm{d}}{\mathrm{d}s}\mathrm{E}(s,0)=-iH(s)\mathrm{E}(s,0),$
(157)

we obtain

$\displaystyle\int_{0}^{t}\mathrm{d}s\frac{\mathrm{d}}{\mathrm{d}s}\big{[}\mathrm{E}_{\text{av}}^{\dagger}(s)\mathrm{E}(s,0)\big{]}$
$\displaystyle=\int_{0}^{t}\mathrm{d}s\left\\{\mathrm{E}_{\text{av}}^{\dagger}(s)\big{[}iH_{\text{av}}\big{]}\mathrm{E}(s,0)+\mathrm{E}_{\text{av}}^{\dagger}(s)\big{[}{-iH(s)}\big{]}\mathrm{E}(s,0)\right\\}$
(158)
$\displaystyle=\frac{1}{t}\int_{0}^{t}\mathrm{d}s\int_{0}^{t}\mathrm{d}\tau\left\\{\mathrm{E}_{\text{av}}^{\dagger}(s)\big{[}iH(\tau)\big{]}\mathrm{E}(s,0)+\mathrm{E}_{\text{av}}^{\dagger}(s)\big{[}{-iH(s)}\big{]}\mathrm{E}(s,0)\right\\}$
$\displaystyle=\frac{1}{t}\int_{0}^{t}\mathrm{d}s\int_{0}^{t}\mathrm{d}\tau\left\\{\mathrm{E}_{\text{av}}^{\dagger}(s)\big{[}iH(\tau)\big{]}\mathrm{E}(s,0)+\mathrm{E}_{\text{av}}^{\dagger}(\tau)\big{[}{-iH(\tau)}\big{]}\mathrm{E}(\tau,0)\right\\},$

which implies, by telescoping, that

$\displaystyle\left\lVert\int_{0}^{t}\mathrm{d}s\frac{\mathrm{d}}{\mathrm{d}s}\big{[}\mathrm{E}_{\text{av}}^{\dagger}(s)\mathrm{E}(s,0)\big{]}\right\rVert_{\infty}$
$\displaystyle\leq\frac{1}{t}\int_{0}^{t}\mathrm{d}s\int_{0}^{t}\mathrm{d}\tau\,\big{(}\left\lVert\mathrm{E}_{\text{av}}(s)-\mathrm{E}_{\text{av}}(\tau)\right\rVert_{\infty}\left\lVert
H(\tau)\right\rVert_{\infty}$ (159)
$\displaystyle\qquad\qquad\qquad\quad+\left\lVert\mathrm{E}(s,0)-\mathrm{E}(\tau,0)\right\rVert_{\infty}\left\lVert
H(\tau)\right\rVert_{\infty}\big{)}.$

By the fundamental theorem of calculus, the first term of the integrand can be
bounded as

$\left\lVert\mathrm{E}_{\text{av}}(s)-\mathrm{E}_{\text{av}}(\tau)\right\rVert_{\infty}\leq\left\lVert
H_{\text{av}}\right\rVert_{\infty}|s-\tau|\leq\frac{1}{t}\int_{0}^{t}\mathrm{d}u\left\lVert
H(u)\right\rVert_{\infty}|s-\tau|\leq\left\lVert H\right\rVert_{\infty,1}.$
(160)

To handle the second term, we use Lemma 1. Observe that the generator of
$\mathrm{E}(s,0)$ is $H(u),\ 0\leq u\leq s$, whereas the generator of
$\mathrm{E}(\tau,0)$ is $H(u),\ 0\leq u\leq\tau$. So they only differ on the
interval $\big{[}\min\\{s,\tau\\},\max\\{s,\tau\\}\big{]}$. Consequently,

$\left\lVert\mathrm{E}(s,0)-\mathrm{E}(\tau,0)\right\rVert_{\infty}\leq\int_{\min\\{s,\tau\\}}^{\max\\{s,\tau\\}}\mathrm{d}u\left\lVert
H(u)\right\rVert_{\infty}\leq\int_{0}^{t}\mathrm{d}u\left\lVert
H(u)\right\rVert_{\infty}=\left\lVert H\right\rVert_{\infty,1}.$ (161)

Altogether, we have

$\displaystyle\left\lVert\mathrm{E}(t,0)-\mathrm{E}_{\text{av}}(t)\right\rVert_{\infty}$
$\displaystyle=\left\lVert\int_{0}^{t}\mathrm{d}s\frac{\mathrm{d}}{\mathrm{d}s}\big{[}\mathrm{E}_{\text{av}}(s)^{\dagger}\mathrm{E}(s,0)\big{]}\right\rVert_{\infty}$
(162)
$\displaystyle\leq\frac{1}{t}\int_{0}^{t}\mathrm{d}s\int_{0}^{t}\mathrm{d}\tau\
\left(\left\lVert\mathrm{E}_{\text{av}}(s)-\mathrm{E}_{\text{av}}(\tau)\right\rVert_{\infty}\left\lVert
H(\tau)\right\rVert_{\infty}\right.$
$\displaystyle\qquad\qquad\qquad\quad\left.+\left\lVert\mathrm{E}(s,0)-\mathrm{E}(\tau,0)\right\rVert_{\infty}\left\lVert
H(\tau)\right\rVert_{\infty}\right)$ $\displaystyle\leq 2\left\lVert
H\right\rVert_{\infty,1}^{2}.$

######  Theorem 11 (Hamiltonian simulation by averaging (spectral-norm
distance)).

Let $H(\tau)$ be a time-dependent Hamiltonian defined for $0\leq\tau\leq t$
and assume that it is continuous and nonzero everywhere. Define
$\mathrm{E}(t,0):=\exp_{\mathcal{T}}\big{(}-i\int_{0}^{t}\mathrm{d}\tau\,H(\tau)\big{)}$
and $\mathrm{E}_{\text{av}}(t):=e^{-itH_{\text{av}}}$, where
$H_{\text{av}}:=\frac{1}{t}\int_{0}^{t}\mathrm{d}\tau\,H(\tau)$ is the average
Hamiltonian. Then,

$\left\lVert\mathrm{E}(t,0)-\mathrm{E}_{\text{av}}(t)\right\rVert_{\infty}\leq
2\left\lVert H\right\rVert_{\infty,1}^{2}.$ (163)

The above bound on the spectral-norm error can be converted to a bound on the
diamond-norm error using Lemma 2.

######  Theorem 11′ (Hamiltonian simulation by averaging (diamond-norm
distance)).

Let $H(\tau)$ be a time-dependent Hamiltonian defined for $0\leq\tau\leq t$
and assume that it is continuous and nonzero everywhere. Define unitary
operators
$\mathrm{E}(t,0):=\exp_{\mathcal{T}}\big{(}-i\int_{0}^{t}\mathrm{d}\tau\
H(\tau)\big{)}$, $\mathrm{E}_{\text{av}}(t):=e^{-itH_{\text{av}}}$ and let
$\mathcal{E}(t,0)(\cdot):=\mathrm{E}(t,0)(\cdot)\mathrm{E}(t,0)^{\dagger}$,
$\mathcal{E}_{\text{av}}(t)(\cdot)=\mathrm{E}_{\text{av}}(t)(\cdot)\mathrm{E}_{\text{av}}(t)^{\dagger}$
be the corresponding channels. Then,

$\left\lVert\mathcal{E}(t,0)-\mathcal{E}_{\text{av}}(t)\right\rVert_{\diamond}\leq
4\left\lVert H\right\rVert_{\infty,1}^{2}.$ (164)

###  A.2 Implementing Hamiltonian averaging by continuous qDRIFT

Let $H(\tau)$ be a time-dependent Hamiltonian defined for $0\leq\tau\leq t$
and assume that it is continuous and nonzero everywhere. We have showed that
the ideal evolution can be approximated by an evolution under the average
Hamiltonian with error that scales with the $L^{1}$ norm. We now show that
such a Hamiltonian averaging can be implemented by continuous qDRIFT, again
with $L^{1}$-norm scaling. This improves over the algorithm of [42] which
scales with the $L^{\infty}$ norm.

######  Theorem 12 (Hamiltonian averaging by continuous qDRIFT).

Let $H(\tau)$ be a time-dependent Hamiltonian defined for $0\leq\tau\leq t$
and assume that it is continuous and nonzero everywhere. Define
$\mathrm{E}_{\text{av}}(t):=e^{-itH_{\text{av}}}$ and let
$\mathcal{E}_{\text{av}}(t)(\cdot)=\mathrm{E}_{\text{av}}(t)(\cdot)\mathrm{E}_{\text{av}}(t)^{\dagger}$
be the corresponding channels. Let $\mathcal{U}(t,0)$ be the continuous qDRIFT
channel

$\mathcal{U}(t,0)(\rho)=\int_{0}^{t}\mathrm{d}\tau\
p(\tau)e^{-i\frac{H(\tau)}{p(\tau)}}\rho e^{i\frac{H(\tau)}{p(\tau)}},$ (165)

where $p(\tau)=\left\lVert H(\tau)\right\rVert_{\infty}/\left\lVert
H\right\rVert_{\infty,1}$. Then,

$\left\lVert\mathcal{E}_{\text{av}}(t)-\mathcal{U}(t,0)\right\rVert_{\diamond}\leq
4\left\lVert H\right\rVert_{\infty,1}^{2}.$ (166)

Note that by applying the triangle inequality to Theorem 5 and Theorem 11′, we
obtain

$\left\lVert\mathcal{E}_{\text{av}}(t)-\mathcal{U}(t,0)\right\rVert_{\diamond}\leq
8\left\lVert H\right\rVert_{\infty,1}^{2}.$ (167)

Theorem 12 improves the constant prefactor from $8$ to $4$.

###### Proof of Theorem 12.

We parametrize the two channels $\mathcal{E}_{\text{av}}(t)$, $\mathcal{U}(t)$
and define

$\displaystyle\mathcal{E}_{\text{av},u}(t)(\rho):=e^{-iu\int_{0}^{t}\mathrm{d}\tau
H(\tau)}\rho e^{iu\int_{0}^{t}\mathrm{d}\tau
H(\tau)},\quad\mathcal{U}_{u}(t,0)(\rho):=\int_{0}^{t}\mathrm{d}\tau\
p(\tau)e^{-iu\frac{H(\tau)}{p(\tau)}}\rho e^{iu\frac{H(\tau)}{p(\tau)}}.$
(168)

Since $\mathcal{E}_{\text{av},0}(t)(\rho)=\rho$,
$\mathcal{E}_{\text{av},1}(t)(\rho)=\mathcal{E}_{\text{av}}(t)(\rho)$,
$\mathcal{U}_{0}(t,0)(\rho)=\rho$, and
$\mathcal{U}_{1}(t,0)(\rho)=\mathcal{U}(\rho)$, the first derivative of
$\mathcal{E}_{\text{av},u}(t)(\rho)$ and $\mathcal{U}_{u}(t,0)(\rho)$ agrees
with each other at $u=0$

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}u}\mathcal{E}_{\text{av},u}(t)(\rho)\bigg{|}_{u=0}=\bigg{[}{-i}\int_{0}^{t}\mathrm{d}\tau\,H(\tau),\rho\bigg{]}=\frac{\mathrm{d}}{\mathrm{d}u}\mathcal{U}_{u}(t,0)(\rho)\bigg{|}_{u=0}.$
(169)

Applying the fundamental theorem of calculus twice, we obtain

$\displaystyle\ \mathcal{E}_{\text{av}}(t)(\rho)-\mathcal{U}(t,0)(\rho)$ (170)
$\displaystyle=$ $\displaystyle\
\big{(}\mathcal{E}_{\text{av},1}(t)(\rho)-\mathcal{E}_{\text{av},0}(t)(\rho)\big{)}-\big{(}\mathcal{U}_{1}(t,0)(\rho)-\mathcal{U}_{0}(t,0)(\rho)\big{)}$
$\displaystyle=$ $\displaystyle\
\int_{0}^{1}\mathrm{d}u\int_{0}^{u}\mathrm{d}v\
\frac{\mathrm{d}^{2}}{\mathrm{d}v^{2}}\big{[}\mathcal{E}_{\text{av},v}(t)(\rho)-\mathcal{U}_{v}(t,0)(\rho)\big{]}$
$\displaystyle=$ $\displaystyle\
\int_{0}^{1}\mathrm{d}u\int_{0}^{u}\mathrm{d}v\
\bigg{\\{}e^{-iv\int_{0}^{t}\mathrm{d}\tau
H(\tau)}\bigg{[}-i\int_{0}^{t}\mathrm{d}\tau
H(\tau),\bigg{[}-i\int_{0}^{t}\mathrm{d}\tau
H(\tau),\rho\bigg{]}\bigg{]}e^{iv\int_{0}^{t}\mathrm{d}\tau H(\tau)}$
$\displaystyle\ \qquad\qquad\qquad-\int_{0}^{t}\mathrm{d}\tau\
p(\tau)e^{-iv\frac{H(\tau)}{p(\tau)}}\bigg{[}-i\frac{H(\tau)}{p(\tau)},\bigg{[}-i\frac{H(\tau)}{p(\tau)},\rho\bigg{]}\bigg{]}e^{iv\frac{H(\tau)}{p(\tau)}}\bigg{\\}}.$

We take $\sigma$ to be a state on the joint system of the original register
and an ancilla register with the same dimension. Using properties of the
Schatten norms, we have

$\displaystyle\left\lVert\big{(}\mathcal{E}_{\text{av}}(t)\otimes\mathds{1}\big{)}(\sigma)-\big{(}\mathcal{U}(t)\otimes\mathds{1}\big{)}(\sigma)\right\rVert_{1}$
(171) $\displaystyle\leq$
$\displaystyle\int_{0}^{1}\mathrm{d}u\int_{0}^{u}\mathrm{d}v\
\bigg{\\{}\left\lVert\bigg{[}-i\int_{0}^{t}\mathrm{d}\tau
H(\tau)\otimes\mathds{1},\bigg{[}-i\int_{0}^{t}\mathrm{d}\tau
H(\tau)\otimes\mathds{1},\sigma\bigg{]}\bigg{]}\right\rVert_{1}$
$\displaystyle\qquad\qquad\quad+\int_{0}^{t}\mathrm{d}\tau\
p(\tau)\left\lVert\bigg{[}-i\frac{H(\tau)}{p(\tau)}\otimes\mathds{1},\bigg{[}-i\frac{H(\tau)}{p(\tau)}\otimes\mathds{1},\sigma\bigg{]}\bigg{]}\right\rVert_{1}\bigg{\\}}$
$\displaystyle\leq$
$\displaystyle\int_{0}^{1}\mathrm{d}u\int_{0}^{u}\mathrm{d}v\
\bigg{[}4\left\lVert H\right\rVert_{\infty,1}^{2}+4\int_{0}^{t}\mathrm{d}\tau\
\frac{\left\lVert H(\tau)\right\rVert_{\infty}^{2}}{p(\tau)}\bigg{]}.$

Using the definition $p(\tau)=\left\lVert
H(\tau)\right\rVert_{\infty}/\left\lVert H\right\rVert_{\infty,1}$, the second
term of the integrand can be further simplified as

$\displaystyle\int_{0}^{t}\mathrm{d}\tau\ \frac{\left\lVert
H(\tau)\right\rVert_{\infty}^{2}}{p(\tau)}=\left\lVert
H\right\rVert_{\infty,1}^{2},$ (172)

giving

$\left\lVert\big{(}\mathcal{E}_{\text{av}}(t)\otimes\mathds{1}\big{)}(\sigma)-\big{(}\mathcal{U}(t,0)\otimes\mathds{1}\big{)}(\sigma)\right\rVert_{1}\leq
4\left\lVert H\right\rVert_{\infty,1}^{2}.$ (173)

Optimizing over $\sigma$ proves the claimed bound. ∎


# A logarithmic approximation of linearly-ordered colourings††thanks: This
work was supported by UKRI EP/X024431/1, by a Clarendon Fund Scholarship and
by the Knut and Alice Wallenberg Foundation. For the purpose of Open Access,
the authors have applied a CC BY public copyright licence to any Author
Accepted Manuscript version arising from this submission. All data is provided
in full in the results section of this paper.

Johan Håstad
KTH
<EMAIL_ADDRESS>Björn Martinsson
KTH
<EMAIL_ADDRESS>Tamio-Vesa Nakajima
University of Oxford
<EMAIL_ADDRESS>Stanislav Živný
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

A linearly ordered (LO) $k$-colouring of a hypergraph assigns to each vertex a
colour from the set $\\{0,1,\ldots,k-1\\}$ in such a way that each hyperedge
has a unique maximum element. Barto, Batistelli, and Berg conjectured that it
is -hard to find an LO $k$-colouring of an LO 2-colourable 3-uniform
hypergraph for any constant $k\geq 2$ [STACS’21] but even the case $k=3$ is
still open. Nakajima and Živný gave polynomial-time algorithms for finding,
given an LO 2-colourable 3-uniform hypergraph, an LO colouring with
$O^{*}(\sqrt{n})$ colours [ICALP’22] and an LO colouring with
$O^{*}(\sqrt[3]{n})$ colours [ACM ToCT’23]. Very recently, Louis, Newman, and
Ray gave an SDP-based algorithm with $O^{*}(\sqrt[5]{n})$ colours. We present
two simple polynomial-time algorithms that find an LO colouring with
$O(\log_{2}(n))$ colours, which is an exponential improvement.

##  1 Introduction

Given a graph $G$, the _graph $k$-colouring_ problem asks to find a colouring
of the vertices of $G$ by colours from the set $\\{0,1,\ldots,k-1\\}$ in such
a way that no edge is monochromatic. The _approximate graph colouring problem_
asks, given a $k$-colourable graph $G$, to find an $\ell$-colouring of $G$,
where $\ell\geq k$. For $k=3$, the state-of-the-art results are -hardness of
the case $\ell=5$ [BBKO21] and a polynomial-time algorithm for finding a
colouring with $\ell=O(n^{0.19996})$ colours, where $n$ is the number of
vertices of the input graph $G$ [KT17]. For non-monochromatic colourings of
hypergraphs, it is known that finding an $\ell$-colouring of a $k$-colourable
$r$-uniform hypergraph is -hard for any constant $\ell\geq k\geq 2$ and $r\geq
3$ [DRS05], and also some positive results are known for colourings with
super-constantly many colours, e.g. [KS03, KNS01, CS08].

A new variant of hypergraph colourings was identified in [BBB21]. Given a
3-uniform hypergraph $H$, a colouring of the vertices of $H$ with colours from
the set $\\{0,1,\ldots,k-1\\}$ is called a _linearly ordered_ (LO)
$k$-colouring if every edge $e$ of $H$ satisfies the following: if two
vertices of $e$ have the same colour then the third colour is larger. More
generally, a colouring of an $r$-uniform hypergraph $H$ is an LO colouring if
every edge of $H$ has a unique maximum colour. (Note that the two definitions
coincide for $r=3$.) Barto et al. conjectured that finding an LO
$\ell$-colouring of a 3-uniform hypergraph that admits an LO $k$-colouring is
-hard for every constant $\ell\geq k\geq 2$ [BBB21] but even the case $k=2$
and $\ell=3$ is open. Nakajima and Živný established -hardness for some
regimes of the parameters $k,\ell,r$ [NŽ22, NŽ23] and, very recently,
Filakovký et al. [FNO+24] showed -hardness of the case $k=3$, $\ell=4$, $r=3$.
More importantly for this paper, Nakajima and Živný also considered finding an
LO $f(n)$-colouring of an LO 2-colourable 3-uniform hypergraph with $n$
vertices and presented polynomial-time algorithms with $f(n)=O(\sqrt{n\log\log
n}/\log n)$ [NŽ22] and $f(n)=O(\sqrt[3]{n\log\log n/\log n})$ [NŽ23]. Very
recently, Louis, Newman, and Ray [LNR24] have given a polynomial-time SDP-
based algorithm with $f(n)=O^{*}(\sqrt[5]{n})$ colours.

As our main result, we improve their results by an exponential factor.

######  Theorem 1.

There is an algorithm which, if given a 3-uniform hypergraph $H$ with $n$
vertices and $m$ edges that admits an LO 2-colouring, finds an LO
$\log_{2}(n)$-colouring of $H$ in time $O(n^{3}+nm)$.

In fact we present two different algorithms that return colourings using
$O(\log n)$ colours. Both are based on solving the natural system of linear
equations implied by the existence of an LO 2-colouring. In one case, the
system is solved modulo 2, and in the other case, the system is solved over
the rationals.

For each edge $(x,y,z)$ of $H$, we write an equation $v_{x}+v_{y}+v_{z}=1$
where we initially use equality modulo 2 but as stated above we later use the
same system over the rational numbers. Let $A$ be this set of equations,
written as a matrix with $m$ rows and $n$ columns. Thus $v$ is a solution if
and only if $Av=1^{m}$. Clearly a valid LO 2-colouring gives one solution but
in the general case, the system has a large dimensional affine space as its
set of solutions and the desired solution is hard to find.

Some variables might be determined by this linear system of equations and as a
preliminary step we fix these variables once and for all. Thus, we have found
the correct colour of a vertex in _any_ LO 2-colouring and we simply assign
this colour. As any vertex given the colour 1 forces the colours of two other
vertices in its edges to be 0, these are now efficiently eliminated. Vertices
forced to be coloured 0 may reduce the size of some edges from three to two,
but this is not a problem as one of the other two vertices gets a colour
larger than 0\. From now on we assume that no variables are fixed to a
constant by the system $Av=1^{m}$.

##  2 Algorithm based on equations modulo 2

In this section all linear equations are taken modulo 2. We first prove the
following subprocedure of the main algorithm.

######  Lemma 2.

There is an algorithm which, if given a hypergraph $H$ with $n$ vertices and
$m$ edges that admits an LO 2-colouring and such that implied linear system of
equations $Av=1^{m}$ does not fix the value of any variable, outputs a subset
$T$ of vertices that intersects each edge of size three in zero or two
vertices and edges of size two in exactly one vertex. Moreover, we have
$|T|\geq n/2$. The algorithm runs in $O(n^{3}+nm)$ time.

###### Proof.

We first describe a randomised version of our algorithm, and then derandomise
it. The set of solutions to $Av=1^{m}$ is an affine space and hence a generic
solution can be written as $v=v^{0}+\sum_{i=1}^{r}a_{i}v^{i}$ for a basic
solution $v^{0}$, linearly independent solutions to the homogeneous system
$v^{i}$, and random field elements (in this case bits) $a_{i}$. The fact that
no variable is fixed implies that for each vertex $x$ there is some positive
$i$ such that $v^{i}_{x}=1$.

For the randomised algorithm we let $a_{i}$ be random bits and set $T$ to be
the set of variables, $x$, such that $v_{x}=0$. Clearly $T$ satisfies the
conclusion of the lemma as in each edge we have an odd number of ones. It is
easy to see that each coordinate of the resulting solution is a random bit and
thus, on average, $T$, contains half the vertices.

Now, we derandomise this algorithm using the method of conditional
expectations. Go through the variables $a_{i}$ in increasing order and fix its
value once and for all. Fixing the value of $a_{i}$ determines the value of
some $v_{x}$ while other values remain undetermined. For each value being
determined $v_{x}^{i}=1$ and hence one value of $a_{i}$ gives the final value
0 and the other gives final value 1. Set $a_{i}$ such that at least half the
determined values are 0. After we have fixed all $a_{i}$ this way, we have a
final solution with at least $n/2$ zeroes.

The bottleneck of the running time of this algorithm is solving the linear
system of equations. This can be done in the advertised running time since
every equation has $O(1)$ entries. ∎

###### Proof of Theorem 1.

Consider the following algorithm.

  1. 1.

If the hypergraph $H$ has at most, say, 20 vertices, find an LO 2-colouring by
brute force.

  2. 2.

Otherwise, find the subsets $T$ guaranteed by Lemma 2.

  3. 3.

Colour $T$ by a smallest available colour (i.e. all future colours are greater
than this one). Eliminate all edges that intersect $T$.

  4. 4.

Repeat.

Note that $|T|\geq n/2$ and thus within $-4+\log_{2}n$ repetitions we reach
the first case. Each step adds one colour and we get two additional colours
from the final brute-force colouring for a total of at most $\log_{2}n$
colours. The output is correct as the first time some vertex in an edge is
coloured, for edges with three vertices exactly one more vertex in the same
edge is coloured at the same time, and for edges with two vertices only that
vertex is coloured at that time. The remaining vertex is given a higher colour
and hence the edge is correctly coloured. Note that the colours used in the
preprocessing can be reused and resulting edges of size two are eliminated by
the $T$ chosen in the first round. For the time complexity, we again note that
it is dominated by the time needed to solve the linear system of equations. ∎

Clearly the number 20 can be increased to any constant or even any number that
is $O(\log n)$ and the algorithm remains polynomial time. This decreases the
number of colours by an additive factor of up to $\Theta(1)+\log{\log n}$.

A slight variant can be obtained by instead counting the number of remaining
edges with no coloured vertex. Once we have no more such vertices, we colour
all remaining vertices with the next colour. For each edge a random solution
$v$ gives the four sets of values $(0,0,1)$, $(0,1,0)$, $(1,0,0)$ and
$(1,1,1)$ with equal probabilities. Thus the number of edges decreases, on
average, by a factor 4 for each interaction. It is easy to achieve this
deterministically by conditional expectations. We state the conclusion as a
theorem.

######  Theorem 3.

There is an algorithm which, if given a 3-uniform hypergraph $H$ with $n$
vertices and $m$ edges that admits an LO 2-colouring, finds an LO
$\frac{1}{2}\log_{2}(m)$-colouring of $H$ in time $O(n^{3}+nm)$.

######  Remark 4.

Our algorithm has some similarity with algorithms for _temporal_ CSPs [BK10].
Note that an LO $\omega$-colouring (which means an LO-colouring, but with no
restriction on the number of colours) is a temporal CSP; to solve it, one
finds a subset that could be the smallest colour (by solving mod-2 equations
as above), sets that colour, then continues recursively. The difference is
that for an LO $\omega$-colouring one does not care about the number of
colours, so one can find any nonempty set of vertices to set the lowest colour
to, whereas in our problem we are trying to find a large set of this kind. We
note that the algorithm of [NŽ23] also uses this approach when setting “small
colours”.

######  Remark 5.

We remark that the subprocedure of our algorithm computes the exclusive or of
two vectors of bits. Thus the algorithm runs very fast in practice — on most
architectures hundreds of operations of this kind are done at one time by (i)
packing the bits within a larger word and (ii) using SIMD instructions.

##  3 Algorithm using $\mathbb{Q}$

In this section we present a more complicated algorithm which uses more
colours. This might seem pointless, and indeed it might be. On the other hand
the ideas used are slightly different and hence there might be situations
where the ideas of this section can turn out to be useful. It is also curious
to see that we can use the same system of linear equations, now over the
rationals, in a rather different way. The algorithm here is in fact
essentially saying that we can always use the unbalanced case of [LNR24]. As
this eliminates many complications and in particular makes it possible to
completely avoid any semi-definite programming, we state all facts needed in
the current section rather than refer to the very similar statements in
[LNR24]. As already stated, all arithmetic in this section is over the
rational numbers. In this situation, no variables can be determined as we can
set $v^{0}$ to have all coordinates equal to $1/3$.

We study the homogeneous system $Av=0$ and by the assumption of LO
2-colourability it has a solution, $w$, with coordinates either $-\frac{1}{3}$
or $\frac{2}{3}$. Let us first show how solutions over the rational numbers
can be used to find LO-colourings. This is the same lemma used in the
unbalanced case of [LNR24].

######  Lemma 6.

Suppose we have a solution, $u$, to the homogeneous system where $M$ is the
maximal value of the absolute value of a coordinate and $m>0$ is the minimal
absolute value. Then we can LO-colour with $2+\log_{2}{(M/m)}$ colours.

###### Proof.

For notational convenience let us instead require that the minimal colour in
each edge should be unique. We can simply reverse the order of the colours at
the end. By scaling we can assume $M=1$. We use even colours for positive
coordinates and we give $x$ the colour $2\ell$ if $v_{x}$ is at most
$2^{-(2\ell-1)}$ and strictly larger than $2^{-(2\ell+1)}$. For negative
coordinates we use $2\ell+1$ as the colour if $v_{x}$ is between $-2^{-2\ell}$
(inclusive) and $-2^{-(2\ell+2)}$ (non-inclusive). Let us verify that this
gives a correct colouring.

Take an edge $(x,y,z)$ and suppose both $x$ and $y$ get the same colour
$2\ell$. Then by the linear equation of the edge $v_{z}<-2^{-2\ell}$ and thus
$z$ has a colour below $2\ell$. The case of two vertices of odd colour is
similar and as the bound on the number of colours is immediate, the lemma
follows. ∎

Let us choose the vectors $(v^{i})_{i=1}^{r}$ giving the solutions to the
homogeneous system to be of unit length and orthogonal. Define
$u=\sum_{i=1}^{r}y_{i}v^{i}$ where $y_{i}$ are independent normal variables
with mean 0 and standard deviation 1. The length of $u$ is very close to
$\sqrt{r}$ but to be crude we use that $E[\|u\|^{2}]=r$ and hence with
probability $\frac{3}{4}$ the length of $u$ is at most $2\sqrt{r}$.

Let $c^{j}=(v^{1}_{j},v^{2}_{j},\ldots v_{j}^{r})$ be the vector of dimension
$r$ given by the $j$th coordinates of each vector $v^{i}$. Using this notation
we see that the $j$th coordinate of $u$ is a normal variable with standard
deviation $\|c^{j}\|$. Recall that $w$ is our assumed solution to $Av=0$ with
all coordinates either $-\frac{1}{3}$ or $\frac{2}{3}$. We can write
$w=\sum_{i=1}^{r}a_{i}v^{i}$ for some numbers $a_{i}$, and by orthonormality
$\|a\|=\|w\|$ which is at most $\frac{2}{3}\sqrt{n}$. As

$|w_{j}|=|(c^{j},a)|\leq\|c^{j}\|\|a\|,$

using that $|w_{j}|$ is at least $\frac{1}{3}$ we conclude that

$\|c^{j}\|\geq 1/(2\sqrt{n}).$

The probability that a normal variable with standard deviation $\sigma$ is of
absolute value at most $\delta$ is at most $2\delta/(\sqrt{2\pi}\sigma)$. We
conclude that for a suitable constant $d$ the probability that $|u_{j}|$ is
below $dn^{-3/2}$ is at most $1/(2n)$. Thus with probability at least 1/2 the
absolute value of any coordinate of $u$ is at least $dn^{-3/2}$. Thus with
probability at least $\frac{1}{4}$, we can apply Lemma 6 with $M=2n^{1/2}$ and
$m=dn^{-3/2}$ and we conclude.

######  Theorem 7.

Using the system of linear equations over the rational numbers we can find,
with probability at least $\frac{1}{4}$ and in polynomial time, an LO-
colouring with $O(1)+2\log_{2}n$ colours.

This algorithm is less efficient compared to the algorithm of the previous
section. The main computational cost is still solving a linear system but this
is more complicated over the rational numbers as coefficients are likely to
grow. Our bound for the number of colours is also worse. Heuristically one
could hope to have the ratio of the smallest and largest coordinate of $u$ to
be $\Theta(n)$ but not better. Thus it is possible that we could eliminate the
multiplicative constant 2 in the theorem but to get substantially fewer than
$\log n$ colours by this method sounds unlikely.

As a final observation in this section let us note that defining a colouring
by the sign of the vector $u$ we get a standard (non-monochromatic)
2-colouring of the hypergraph. This gives an alternative algorithm to that of
[BG21, BG19].

##  4 Concluding remarks

Our algorithms indicate that LO 2-colouring is quite different from many other
colouring problems. The key property that we use in our algorithm is that the
constraint implies a linear constraint. The analysis of the algorithms also
heavily relies on the fact that we study 3-uniform hypergraphs.

It is tempting to think that the proposed methods would extend to other
constraint satisfaction problems where we are guaranteed that a solution must
satisfy a linear constraint. We have so far been unable to find an interesting
such example.

### Acknowledgement.

This paper is a merger of independent work by Håstad and Martinsson, and by
Nakajima and Živný respectively. We are grateful to Venkat Guruswami for
noting and informing the authors of the fact that we independently had found
the same algorithm.

## References

  * [BBB21] Libor Barto, Diego Battistelli, and Kevin M. Berg.  Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case.  In Proc. 38th International Symposium on Theoretical Aspects of Computer Science (STACS’21), volume 187 of LIPIcs, pages 10:1–10:16, 2021\.  arXiv:2010.04623, doi:10.4230/LIPIcs.STACS.2021.10.
  * [BBKO21] Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal.  Algebraic approach to promise constraint satisfaction.  J. ACM, 68(4):28:1–28:66, 2021.  arXiv:1811.00970, doi:10.1145/3457606.
  * [BG19] Joshua Brakensiek and Venkatesan Guruswami.  An algorithmic blend of LPs and ring equations for promise CSPs.  In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’19), pages 436–455, 2019.  arXiv:1807.05194, doi:10.1137/1.9781611975482.28.
  * [BG21] Joshua Brakensiek and Venkatesan Guruswami.  Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.  SIAM J. Comput., 50(6):1663–1700, 2021.  arXiv:1704.01937, doi:10.1137/19M128212X.
  * [BK10] Manuel Bodirsky and Jan Kára.  The complexity of temporal constraint satisfaction problems.  J. ACM, 57(2):9:1–9:41, 2010.  doi:10.1145/1667053.1667058.
  * [CS08] Eden Chlamtac and Gyanit Singh.  Improved approximation guarantees through higher levels of SDP hierarchies.  In Proc. 11th International Workshiop on Approximation, Randomization and Combinatorial Optimization (APPROX’08), volume 5171 of Lecture Notes in Computer Science, pages 49–62. Springer, 2008.  doi:10.1007/978-3-540-85363-3\\_5.
  * [DRS05] Irit Dinur, Oded Regev, and Clifford Smyth.  The hardness of 3-uniform hypergraph coloring.  Comb., 25(5):519–535, September 2005.  doi:10.1007/s00493-005-0032-4.
  * [FNO+24] Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner.  Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.  In Proc. 41st International Symposium on Theoretical Aspects of Computer Science (STACS’24), volume 289 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:19, 2024.  arXiv:2312.12981, doi:10.4230/LIPIcs.STACS.2024.34.
  * [KNS01] Michael Krivelevich, Ram Nathaniel, and Benny Sudakov.  Approximating coloring and maximum independent sets in 3-uniform hypergraphs.  J. Algorithms, 41(1):99–113, 2001.  doi:10.1006/jagm.2001.1173.
  * [KS03] Michael Krivelevich and Benny Sudakov.  Approximate coloring of uniform hypergraphs.  J. Algorithms, 49(1):2–12, 2003.  doi:10.1016/S0196-6774(03)00077-4.
  * [KT17] Ken-ichi Kawarabayashi and Mikkel Thorup.  Coloring 3-colorable graphs with less than $n^{1/5}$ colors.  J. ACM, 64(1):4:1–4:23, 2017.  doi:10.1145/3001582.
  * [LNR24] Anand Louis, Alantha Newman, and Arka Ray.  Improved linearly ordered colorings of hypergraphs via SDP rounding.  Technical report, 2024.  arXiv:2405.00427.
  * [NŽ22] Tamio-Vesa Nakajima and Stanislav Živný.  Linearly Ordered Colourings of Hypergraphs.  In Proc. 49th International Colloquium on Automata, Languages, and Programming (ICALP’22 ), volume 229 of LIPIcs, pages 128:1–128:18, 2022.  doi:10.4230/LIPIcs.ICALP.2022.128.
  * [NŽ23] Tamio-Vesa Nakajima and Stanislav Živný.  Linearly Ordered Colourings of Hypergraphs.  ACM Trans. Comput. Theory, 13(3–4), 2023.  arXiv:2204.05628, doi:10.1145/3570909.


capbtabboxtable[][]

# Non-Parametric Few-Shot Learning for Word Sense Disambiguation

Howard Chen, Mengzhou Xia, Danqi Chen
Princeton University
{howardchen, mengzhou<EMAIL_ADDRESS>

###### Abstract

Word sense disambiguation (WSD) is a long-standing problem in natural language
processing. One significant challenge in supervised all-words WSD is to
classify among senses for a majority of words that lie in the long-tail
distribution. For instance, $84\%$ of the annotated words have less than $10$
examples in the SemCor training data. This issue is more pronounced as the
imbalance occurs in both word and sense distributions. In this work, we
propose MetricWSD, a non-parametric few-shot learning approach to mitigate
this data imbalance issue. By learning to compute distances among the senses
of a given word through episodic training, MetricWSD transfers knowledge (a
learned metric space) from high-frequency words to infrequent ones. MetricWSD
constructs the training episodes tailored to word frequencies and explicitly
addresses the problem of the skewed distribution, as opposed to mixing all the
words trained with parametric models in previous work. Without resorting to
any lexical resources, MetricWSD obtains strong performance against parametric
alternatives, achieving a $75.1$ F1 score on the unified WSD evaluation
benchmark Raganato et al. (2017b). Our analysis further validates that
infrequent words and senses enjoy significant improvement.111Our code is
publicly available at: https://github.com/princeton-nlp/metric-wsd.

##  1 Introduction

Figure 1: Top: the long-tail distribution of words in the training data
(SemCor). Bottom: percentage of examples whose target senses are the most
frequent sense for a given word (only words with $\geq 10$ examples are
considered). All single-sense words are excluded.

Word sense disambiguation (WSD) (Navigli, 2009) is a widely studied problem
that aims to assign words in text to their correct senses. Despite advances
over the years, a major challenge remains to be the naturally present data
imbalance issue. Models suffer from extreme data imbalance, rendering learning
the long-tail examples a major focus. In the English all-words WSD task
(Raganato et al., 2017b), $84\%$ of the annotated words222Here we use “word”
for simplicity. In WSD datasets, a word is a combination of its stem and part-
of-speech tag. have less than $10$ occurrences in the training data and the
most frequent sense (MFS) accounts for a large portion of the examples,
resulting in a $65.2$ test F1 score by simply predicting MFS (Figure 1).

Recent approaches tackle this problem by resorting to extra sense information
such as gloss (sense definition) and semantic relations to mitigate the issue
of rare words and senses (Luo et al., 2018b, a; Kumar et al., 2019; Huang et
al., 2019; Blevins and Zettlemoyer, 2020; Bevilacqua and Navigli, 2020).
However, most work sticks to the parametric models that share parameters
between words and adopts standard supervised learning mixing all the words of
different frequencies. We argue that this accustomed paradigm exposes a
missing opportunity to explicitly address the data imbalance issue.

In this work, we propose MetricWSD, a simple non-parametric model coupled with
episodic training to solve the long-tail problem, drawing inspiration from
few-shot learning methods such as Prototypical Networks (Snell et al., 2017).
Given a word, the model represents its senses by encoding a sampled subset
(support set) of the training data and learns a distance metric between these
sense representations and the representations from the remaining subset (query
set). This lightens the load for a model by learning an effective metric space
instead of learning a sense representation from scratch. By sharing only the
parameters in the text encoder, the model will trickle the knowledge of the
learned metric space down from high-frequency words to infrequent ones. We
devise a sampling strategy that takes word and sense frequency into account
and constructs support and query sets accordingly. In combination, this non-
parametric approach naturally fits in the imbalanced few-shot problems, which
is a more realistic setting when learning from a skewed data distribution as
in WSD.

We evaluate MetricWSD on the unified WSD evaluation benchmark (Raganato et
al., 2017b), achieving a $75.1\%$ test F1 and outperforming parametric
baselines using only the annotated sense supervision. A further breakdown
analysis shows that the non-parametric model outperforms the parametric
counterparts in low-frequency words and senses, validating the effectiveness
of our approach.

##  2 Related Work

Word sense disambiguation has been studied extensively as a core task in
natural language processing. Early work computes relatedness through concept-
gloss lexical overlap without supervision (Lesk, 1986; Banerjee and Pedersen,
2003). Later work designs features to build word-specific classifiers (word
expert) (Zhong and Ng, 2010; Shen et al., 2013; Iacobacci et al., 2016). All-
words WSD unifies the datasets and training corpora by collecting large scale
annotations (Raganato et al., 2017b), which becomes the standard testbed for
the WSD task. However, due to the naturally present long-tail annotation, word
expert approaches fall short in utilizing information across different words.

Recent supervised neural approaches prevail word-independent classifiers by
more effective sentence feature extraction and achieve higher performance
(Kågebäck and Salomonsson, 2016; Raganato et al., 2017a). Approaches that use
large pre-trained language models Peters et al. (2018); Devlin et al. (2019)
further boost the performance (Hadiwinoto et al., 2019). Recent work turns to
incorporate gloss information (Luo et al., 2018b, a; Huang et al., 2019;
Loureiro and Jorge, 2019; Blevins and Zettlemoyer, 2020). Other work explores
more lexical resources such as knowledge graph structures (Kumar et al., 2019;
Bevilacqua and Navigli, 2020; Scarlini et al., 2020b, a). All the above
approaches mix words in the dataset and are trained under a standard
supervised learning paradigm. Another close work to ours is Holla et al.
(2020), which converts WSD into an $N$-way, $K$-shot few-shot learning problem
and explores a range of meta-learning algorithms. This setup assumes disjoint
sets of words between meta-training and meta-testing and deviates from the
standard WSD setting.

##  3 Method

###  3.1 Task Definition

Given an input sentence $x=x_{1},x_{2},\ldots,x_{n}$, the goal of the all-
words WSD task is to assign a sense $y_{i}$ for every word $x_{i}$, where
$y_{i}\in\mathcal{S}_{x_{i}}\subset\mathcal{S}$ for a given sense inventory
such as the WordNet. In practice, not all the words in a sentence are
annotated, and only a subset of positions are identified
$\mathcal{I}\subseteq\\{1,2,\ldots,n\\}$ to be disambiguated. The goal is to
predict $y_{i}$ for $i\in\mathcal{I}$.

We regard all the instances of a word $w\in\mathcal{W}$ as a classification
task $\mathcal{T}_{w}$, since only the instances of word $w$ share the output
label set $\mathcal{S}_{w}$. We define input $\bar{x}=(x,t)$ where $x$ is an
input sentence, and $1\leq t\leq n$ is the position of the target word and the
output is $y_{t}$ for $x_{t}$. A WSD system is a function $f$ such that
$y=f(\bar{x})$. Our method groups the training instances by word $w$:
$\mathcal{A}(w)=\\{(\bar{x}^{(i)},y^{(i)}):x^{(i)}_{t^{(i)}}=w\\}_{i=1}^{\mathcal{N}(w)}$
where $\mathcal{N}(w)$ is the number of training instances for
$\mathcal{T}_{w}$. It allows for word-based sampling as opposed to mixing all
words in standard supervised training.

###  3.2 Episodic Sampling

We construct episodes by words with a tailored sampling strategy to account
for the data imbalance issue. In each episode, all examples $\mathcal{A}(w)$
of a word $w$ are split into a support set $\mathcal{S}(w)$ containing $J$
distinct senses and a query set $\mathcal{Q}(w)$ by a predefined ratio $r$
(splitting $r\%$ into the support set). When the support set is smaller than a
predefined size $K$, we use the sets as they are. This split maintains the
original sense distribution of the infrequent words as they will be used fully
as support instances during inference. On the other hand, frequent words
normally have abundant examples to form the support set. To mimic the few-shot
behavior, we sample a balanced number of examples per sense in the support set
for frequent words (referred to as the $P_{b}$ strategy). We also compare to
the strategy where the examples of all senses of the word are uniformly
sampled (referred to as the $P_{u}$ strategy). We present the complete
sampling strategy in Algorithm 1.

Algorithm 1 Episodic Sampling

1:$K$: maximum sample number for support set

2:$r$: support to query splitting ratio

3:$P$: sampling strategy $\in\\{P_{b},P_{u}\\}$

4:Initialize empty dataset $\mathcal{D}=\emptyset$

5:for all $w\in\mathcal{W}$ do

6: Retrieve $\mathcal{A}(w)$ and randomly split $\mathcal{A}(w)$ into
$\tilde{\mathcal{S}}(w)$ and $\tilde{\mathcal{Q}}(w)$ with a ratio $r$.

7: if $|\tilde{\mathcal{S}}(w)|\leq K$ then

8: $\mathcal{S}(w)\leftarrow\tilde{\mathcal{S}}(w)$;
$\mathcal{Q}(w)\leftarrow\tilde{\mathcal{Q}}(w)$

9: else

10: $J\leftarrow$ # of senses in $\tilde{\mathcal{S}}(w)$

11: $\tilde{\mathcal{S}}_{j}(w)\leftarrow$ examples of sense $j$ in
$\tilde{\mathcal{S}}(w)$

12: for $k=1\dots|\tilde{\mathcal{S}}(w)|$ do

13: $j\leftarrow$ the sense of $k$-th example

14:
$\alpha_{k}\leftarrow\begin{cases}\frac{1}{|\tilde{\mathcal{S}_{j}}(w)|\times
J},&\text{if }P=P_{b}\text{ (balanced)}\\\
\frac{1}{|\tilde{\mathcal{S}}(w)|},&\text{if }P=P_{u}\text{
(uniform)}\end{cases}$

15:
${\mathcal{S}}(w)\leftarrow\textsc{RandChoice}(\tilde{\mathcal{S}}(w),K,\alpha)$

16:
${\mathcal{Q}}(w)\leftarrow\tilde{\mathcal{Q}}(w)\cup(\tilde{\mathcal{S}}(w)\setminus\mathcal{S}(w))$

17: $\mathcal{D}\leftarrow\mathcal{D}\cup\\{\mathcal{S}(w),\mathcal{Q}(w)\\}$

18:return $\mathcal{D}$

###  3.3 Learning Distance Metric

We use BERT-base (uncased) (Devlin et al., 2019) as the context encoder. We
follow Blevins and Zettlemoyer (2020) closely and denote context encoding as
$f_{\theta}(\bar{x})={\tt{BERT}}(x)[t]$ where the context encoder is
parameterized by $\theta$. If a word $x_{t}$ is split into multiple word
pieces, we take the average of their hidden representations. In each episode,
the model encodes the contexts in the support set $\mathcal{S}(w)$ and the
query set $\mathcal{Q}(w)$, where the encoded support examples will be taken
average and treated as the sense representations (prototypes). For word $w$,
the prototype for sense $j$ among the sampled $J$ senses is computed from the
support examples:

$\displaystyle\mathbf{c}_{j}=\frac{1}{\lvert\mathcal{S}_{j}(w)\rvert}\sum_{(\bar{x},y)\in\mathcal{S}_{j}(w)}f_{\theta}(\bar{x}),$
(1)

where
$\mathcal{S}_{j}(w)=\\{(\bar{x}^{(i)},y^{(i)}):y^{(i)}=j\\}_{i=1}^{\lvert\mathcal{S}_{j}\rvert}\subset\mathcal{S}(w)$.
We compute dot product333We experiment with negative squared $l_{2}$ distance
as suggested in Snell et al. (2017) as the scoring function and find no
improvement. as the scoring function $s(\cdot,\cdot)$ between the prototypes
and the query representations to obtain the probability of predicting sense
$j$ given an example $(\bar{x}^{\prime},y^{\prime})$:

$\displaystyle
p(y=j\mid\bar{x}^{\prime})=\frac{\exp(s(\mathbf{c}_{j},f_{\theta}(\bar{x}^{\prime}))}{\sum_{k}\exp(s(\mathbf{c}_{k},f_{\theta}(\bar{x}^{\prime})))}.$
(2)

The loss is computed using negative log-likelihood and is minimized through
gradient descent. During inference, we randomly sample
$\min(I_{S},\lvert\mathcal{A}_{j}(w)\rvert)$ examples in the training set for
sense $j$ as the support set, where $I_{S}$ is a hyperparameter. We also
experimented with a cross-attention model which learns a scoring function for
every pair of instances, similar to the BERT-pair model in Gao et al. (2019);
however, we didn’t find it to perform better than the dual-encoder model.

###  3.4 Relation to Prototypical Networks

Our non-parametric approach is inspired and closely related to Prototypical
Networks (Snell et al., 2017) with several key differences. First, instead of
using disjoint tasks (i.e., words in our case) for training and testing,
MetricWSD leverages the training data to construct the support set during
inference. Second, we control how to sample the support set using a tailored
sampling strategy (either balanced or uniform sense distribution). This
encourages learning an effective metric space from frequent examples to lower-
frequency ones, which is different from adapting between disjoint tasks as in
the typical meta-learning setup.

|  | Dev | Test Datasets | Concatenation of Test Datasets
---|---|---|---|---
| Gloss? | SE07 | SE02 | SE03 | SE13 | SE15 | Nouns | Verbs | Adj. | Adv. | ALL
WordNet S1 | ✗ | 55.2 | 66.8 | 66.2 | 63.0 | 67.8 | 67.6 | 50.3 | 74.3 | 80.9 | 65.2
Most frequent sense (MFS) | ✗ | 54.5 | 65.6 | 66.0 | 63.8 | 67.1 | 67.7 | 49.8 | 73.1 | 80.5 | 65.5
Bi-LSTM Raganato et al. (2017a) | ✗ | 64.8 | 72.0 | 69.1 | 66.9 | 71.5 | 71.5 | 57.5 | 75.0 | 83.8 | 69.9
BERT-kNN | ✗ | 64.6 | 74.7 | 73.5 | 70.3 | 73.9 | 74.7 | 61.6 | 77.7 | 85.3 | 72.6
BERT-classifier | ✗ | 68.6 | 75.2 | 74.7 | 70.6 | 75.2 | 74.6 | 63.6 | 78.6 | 87.0 | 73.5
1sent Hadiwinoto et al. (2019) | ✗ | 67.0 | 75.0 | 71.6 | 69.7 | 74.4 | - | - | - | - | 72.7
1sent+1sur† Hadiwinoto et al. (2019) | ✗ | 69.3 | 75.9 | 73.4 | 70.4 | 75.1 | - | - | - | - | 73.7
MetricWSD (ours) | ✗ | 71.4 | 77.3 | 75.6 | 71.9 | 76.6 | 77.1 | 64.9 | 79.9 | 85.3 | 75.1
EWISE Kumar et al. (2019) | ✓ | 67.3 | 73.8 | 71.1 | 69.4 | 74.5 | 74.0 | 60.2 | 78.0 | 82.1 | 71.8
GlossBERT Huang et al. (2019) | ✓ | 72.5 | 77.7 | 75.2 | 76.1 | 80.4 | 79.8 | 67.1 | 79.6 | 87.4 | 77.0
EWISER Bevilacqua and Navigli (2020) | ✓ | 71.0 | 78.9 | 78.4 | 78.9 | 79.3 | 81.7 | 66.3 | 81.2 | 85.8 | 78.3
BEM Blevins and Zettlemoyer (2020) | ✓ | 74.5 | 79.4 | 77.4 | 79.7 | 81.7 | 81.4 | 68.5 | 83.0 | 87.9 | 79.0

Table 1: F1 scores for fine-grained all-words WSD task. We compare our non-
parametric model against models without access to gloss information. We take
results from EWISER where only supervised data and gloss are used but not
WordNet examples. $\dagger$: surrounding sentences are used as extra context.
Our system uses the sampling strategy in Algorithm 1 with
$K=40,r=0.4,I_{S}=30,P=P_{b}$.  Figure 2: Accuracy breakdown by word frequency
and sense frequency on the test set.

##  4 Experiments

We evaluate our approach with the WSD framework proposed by Raganato et al.
(2017b). We train our model on SemCor 3.0 and use SemEval-2007 (SE07) for
development and the rest: Senseval-2 (SE02), Senseval-3 (SE03), SemEval-2013
(SE13), and SemEval-2015 (SE15) for testing. Following standard practice, we
report performance on the separate test sets, the concatenation of all test
sets, and the breakdown by part-of-speech tags. For all the experiments, we
use the BERT-base (uncased) model as the text encoder.

#### Baselines

We first compare to two simple baselines: WordNet S1 always predicts the first
sense and MFS always predicts the most frequent sense in the training data. We
compare our approach to BERT-classifier: a linear classifier built on top of
BERT (all the weights are learned together). As opposed to our non-parametric
approach, the BERT-classifier has to learn the output weights from scratch. We
compare to another supervised baseline using contextualized word
representations that extends the input context text with its surrounding
sentences in the SemCor dataset (Hadiwinoto et al., 2019). We also compare to
a non-parametric nearest neighbor baseline BERT-kNN, which obtains sense
representations by averaging BERT encoded representations from training
examples of the same sense. It predicts the nearest neighbor of the input
among the sense representations. The BERT weights are frozen which, different
from our approach, does not learn the metric space. Models using only
supervised WSD data fall back to predicting the most frequent sense (MFS) when
encountering unseen words. For reference, we also list the results of recent
state-of-the-art methods that incorporate gloss information including EWISE
Kumar et al. (2019), EWISER Bevilacqua and Navigli (2020), GlossBERT Huang et
al. (2019), and BEM Blevins and Zettlemoyer (2020). More implementation
details are given in Appendix A.

Figure 3: t-SNE visualization of the learned representations
$f_{\theta}(\bar{x})$ for the examples of note (v) and provide (v) in the
SemCor dataset. It shows that MetricWSD is better than BERT-classifier in
grouping different senses.

Context |  BERT-classifier prediction |  MetricWSD prediction
---|---|---
The art of change-ringing is peculiar to the English, and, like most English peculiarities, unintelligible to the rest of the world. |  art%1:06:00:: (freq = 48) |  art%1:09:00:: (freq = 6)
the products of human creativity; works of art collectively |  a superior skill that you can learn by study and practice and observation
Eyes that were clear, but also bring with a strange intensity, a sort of cold fire burning behind him. |  clear%3:00:00:: (freq = 45) |  clear%3:00:02:: (freq = 4)
readily apparent to the mind |  allowing light to pass through
And, according to reports from US broadcaster CNBC, Citigroup is also planning to replay the state support. |  report%1:10:03:: (freq = 50) |  report%1:10:00:: (freq = 9)
a written document describing the findings of some individual or group |  a short account of the news

Table 2: Examples of contexts and model predictions. The bold italic words in
the contexts are disambiguated by BERT-classifier and MetricWSD. We present
the predicted sense key, the corresponding sense definition, and the sense
frequency in the training set.

#### Overall results

Table 1 presents the overall results on the WSD datasets. Comparing against
systems without using gloss information, MetricWSD achieves strong performance
against all baselines. In particular, MetricWSD outperforms BERT-classifier by
$1.4$ points and BERT-kNN by $2.5$ points respectively in F1 score on the test
set. Using gloss information boosts the performance by a large margin
especially for unseen words, where systems without access to gloss can only
default to the first sense. We believe adding gloss has the potential to
enhance the performance for our non-parametric approach and we leave it to
future work.

#### Performance on infrequent words and senses

The performance breakdown for words and senses of different frequency groups
is given in Figure 2. The non-parametric methods (both MetricWSD and BERT-kNN)
are better at handling infrequent words and senses. In particular, our
approach outperforms BERT-classifier $3.5\%$ for the words with $\leq 10$
occurrences and $6.6\%$ for the senses with $\leq 10$ occurrences. It
demonstrates the effectiveness of MetricWSD to handle scarce examples.

#### Ablation on sampling strategies

We provide an ablation study for the sampling strategy on the development set.
The system using the balanced strategy ($P_{b}$) achieves a $71.4$ F1 on the
development set and drops to $69.2$ F1 when the uniform strategy ($P_{u}$) is
used. Balancing the sampled senses achieves significantly higher performance
than sampling with the uniform distribution and this observation is consistent
across different hyper-parameter settings.

##  5 Analysis

#### Qualitative analysis

Table 2 shows the examples which are correctly predicted by our method but
incorrectly predicted by BERT-classifier. We see that MetricWSD is able to
correctly predict the sense art%1:09:00:: (a superior skill that you can learn
by study and practice and observation), which has only $6$ training examples.
The BERT-classifier model incorrectly predicts the sense art%1:06:00:: (the
products of human creativity; works of art collectively) that has many more
training examples.

#### Visualization of learned representations

We conduct a qualitative inspection of the learned representations for the
BERT-classifier model and MetricWSD. Figure 3 shows the encoded
representations of all $105$ examples in the SemCor dataset of the word note
(with part-of-speech tag v). We see that the BERT-classifier model fails to
learn distinct grouping of the senses while MetricWSD forms clear clusters.
Note that even for the sense (red) with only few examples, our method is able
to learn representations that are meaningfully grouped. Similarly, MetricWSD
separates senses more clearly than BERT-classifier for the word provide (with
part-of-speech tag v, especially on the rare sense (pink).

##  6 Conclusion

In this work, we introduce MetricWSD, a few-shot non-parametric approach for
solving the data imbalance issue in word sense disambiguation. Through
learning the metric space and episodic training, the model learns to transfer
knowledge from frequent words to infrequent ones. MetricWSD outperforms
previous methods only using the standard annotated sense supervision and shows
significant improvements on low-frequency words and senses. In the future, we
plan to incorporate lexical information to further close the performance gap.

## Acknowledgement

We thank the members of the Princeton NLP group and the anonymous reviewers
for their valuable comments and feedback. We also thank Terra Blevins at
University of Washington for providing code and checkpoints for the baselines.
Both HC and MX are supported by a Graduate Fellowship at Princeton University.

## Ethical Considerations

We identify areas where the WSD applications and our proposed approach will
impact or benefit users. WSD systems are often used as an assistive submodule
for other downstream tasks, rendering the risk of misuse less pronounced.
However, it might still exhibit risk when biased data incurs erroneous
disambiguation. For example, the word “shoot” might have a higher chance to be
interpreted as a harmful action among other possible meanings when the context
contains certain racial or ethnic groups that are biasedly presented in
training data. Our proposed method does not directly address this issue.
Nonetheless, we identify the opportunity for our approach to alleviate the
risk by providing an easier way to inspect and remove biased prototypes
instead of making prediction using learned output weights that are hard to
attribute system’s biased behavior. We hope future work extends the approach
and tackles the above problem more explicitly.

## References

  * Banerjee and Pedersen (2003) Satanjeev Banerjee and Ted Pedersen. 2003.  Extended gloss overlaps as a measure of semantic relatedness.  In _International Joint Conference on Artificial Intelligence (IJCAI)_.
  * Bevilacqua and Navigli (2020) Michele Bevilacqua and Roberto Navigli. 2020.  Breaking through the 80% glass ceiling: Raising the state of the art in word sense disambiguation by incorporating knowledge graph information.  In _Association for Computational Linguistics (ACL)_ , pages 2854–2864.
  * Blevins and Zettlemoyer (2020) Terra Blevins and Luke Zettlemoyer. 2020.  Moving down the long tail of word sense disambiguation with gloss informed bi-encoders.  In _Association for Computational Linguistics (ACL)_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _North American Association for Computational Linguistics (NAACL)_ , pages 4171–4186.
  * Gao et al. (2019) Tianyu Gao, Xu Han, Hao Zhu, Zhiyuan Liu1, Peng Li, Maosong Sun, and Jie Zhou. 2019\.  Fewrel 2.0: Towards more challenging few-shot relation classification.  In _Empirical Methods in Natural Language Processing (EMNLP)_.
  * Hadiwinoto et al. (2019) Christian Hadiwinoto, Hwee Tou Ng, and Wee Chung Gan. 2019.  Improved word sense disambiguation using pre-trained contextualized word representations.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5297–5306.
  * Holla et al. (2020) Nithin Holla, Pushkar Mishra, Helen Yannakoudakis, and Ekaterina Shutova. 2020.  Learning to learn to disambiguate: Meta-learning for few-shot word sense disambiguation.  In _Findings of the Empirical Methods in Natural Language Processing (EMNLP Findings)_.
  * Huang et al. (2019) Luyao Huang, Chi Sun, Xipeng Qiu, and Xuan-Jing Huang. 2019.  GlossBERT: BERT for word sense disambiguation with gloss knowledge.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 3500–3505.
  * Iacobacci et al. (2016) Ignacio Iacobacci, Mohammad Taher Pilehvar, and Roberto Navigli. 2016.  Embeddings for word sense disambiguation: An evaluation study.  In _Association for Computational Linguistics (ACL)_.
  * Kumar et al. (2019) Sawan Kumar, Sharmistha Jat, Karan Saxena, and Partha Talukdar. 2019.  Zero-shot word sense disambiguation using sense definition embeddings.  In _Association for Computational Linguistics (ACL)_ , pages 5670–5681.
  * Kågebäck and Salomonsson (2016) Mikael Kågebäck and Hans Salomonsson. 2016.  Word sense disambiguation using a bidirectional lstm.  In _International Conference on Computational Linguistics (COLING)_.
  * Lesk (1986) Michael Lesk. 1986.  Automatic sense disambiguation using machine readable dictionaries: How to tell a pine cone from an ice cream cone.  In _Conference on Systems Documentation (SIGDOC)_.
  * Loureiro and Jorge (2019) Daniel Loureiro and Alípio Jorge. 2019.  Language modelling makes sense: Propagating representations through wordnet for full-coverage word sense disambiguation.  In _Association for Computational Linguistics (ACL)_.
  * Luo et al. (2018a) Fuli Luo, Tianyu Liu, Zexue He, Qiaolin Xia, Zhifang Sui, and Baobao Chang. 2018a.  Leveraging gloss knowledge in neural word sense disambiguation by hierarchical co-attention.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1402–1411.
  * Luo et al. (2018b) Fuli Luo, Tianyu Liu, Qiaolin Xia, Baobao Chang, and Zhifang Sui. 2018b.  Incorporating glosses into neural word sense disambiguation.  In _Association for Computational Linguistics (ACL)_ , pages 2473–2482.
  * Navigli (2009) Roberto Navigli. 2009.  Word sense disambiguation: A survey.  _ACM computing surveys (CSUR)_ , 41(2):1–69.
  * Peters et al. (2018) Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.  In _North American Association for Computational Linguistics (NAACL)_ , volume 1, pages 2227–2237.
  * Raganato et al. (2017a) Alessandro Raganato, Claudio Delli Bovi, and Roberto Navigli. 2017a.  Neural sequence learning models for word sense disambiguation.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1156–1167.
  * Raganato et al. (2017b) Alessandro Raganato, Jose Camacho-Collados, and Roberto Navigli. 2017b.  Word sense disambiguation: A unified evaluation framework and empirical comparison.  In _European Chapter of the Association for Computational Linguistics (EACL)_.
  * Scarlini et al. (2020a) Bianca Scarlini, Tommaso Pasini, and Roberto Navigli. 2020a.  Sensembert: Context-enhanced sense embeddings for multilingual word sense disambiguation.  In _Conference on Artificial Intelligence (AAAI)_.
  * Scarlini et al. (2020b) Bianca Scarlini, Tommaso Pasini, and Roberto Navigli. 2020b.  With more contexts comes better performance: Contextualized sense embeddings for all-round word sense disambiguation.  In _Empirical Methods in Natural Language Processing (EMNLP)_.
  * Shen et al. (2013) Hui Shen, Razvan Bunescu, and Rada Mihalcea. 2013.  Coarse to fine grained sense disambiguation in wikipedia.  In _Conference on Lexical and Computational Semantics (SEM)_.
  * Snell et al. (2017) Jake Snell, Kevin Swersky, and Richard Zemel. 2017.  Prototypical networks for few-shot learning.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 4077–4087.
  * Zhong and Ng (2010) Zhi Zhong and Hwee Tou Ng. 2010.  It makes sense: A wide-coverage word sense disambiguation system for free text.  In _Association for Computational Linguistics (ACL)_.

##  Appendix A Appendix

### Implementation Details

When constructing support and query sets, we skip words that contain only one
sense or words that have only one example per sense since they cannot be split
into meaningful support and query sets (e.g., only two senses and one example
each for a word). During inference, all the aforementioned examples are used
as supports.

For BERT-classifier, all parameters are fine-tuned during supervised training.
We use batch size of $4$ sentences, and runs for $20$ epochs. Our non-
parametric model constructs an episode for each word type, accumulate
gradients for $5$ episodes before performing gradient update, runs for $100$
epochs. All models use the AdamW optimizer with learning rate 1e-5.


# Real-Time Remote Control via VR over Limited Wireless Connectivity

H.P. Madushanka1, Rafaela Scaciota12,
Sumudu Samarakoon12, , and Mehdi Bennis1  This work was supported by NSF-AKA
CRUISE (GA 24304406), VERGE (GA 101096034), and Infotech-R2D2. Views and
opinions expressed are however those of the author(s) only and do not
necessarily reflect those of the European Union. Neither the European Union
nor the granting authority can be held responsible for them. 1Centre for
Wireless Communication, University of Oulu, Finland
2Infortech Oulu, University of Oulu, Finland
email: {madushanka.hewapathiranage, rafaela.scaciotatimoesdasilva,
sumudu.samarakoon<EMAIL_ADDRESS>
###### Abstract

This work introduces a solution to enhance human-robot interaction over
limited wireless connectivity. The goal is to enable remote control of a robot
through a virtual reality (VR) interface, ensuring a smooth transition to
autonomous mode in the event of connectivity loss. The VR interface provides
access to a dynamic 3D virtual map that undergoes continuous updates using
real-time sensor data collected and transmitted by the robot. Furthermore, the
robot monitors wireless connectivity and automatically switches to a
_autonomous mode_ in scenarios with limited connectivity. By integrating four
key functionalities: real-time mapping, remote control through glasses VR,
continuous monitoring of wireless connectivity, and autonomous navigation
during limited connectivity, we achieve seamless end-to-end operation.

###### Index Term:

Remote Control, Virtual Reality, Autonomous Navigation

##  I Introduction

In the domain of semi-autonomous robotics, addressing the significant
challenge of efficient navigation and operation in environments with limited
connectivity between robots and humans is imperative [1]. Creating a semi-
autonomous system that provides a user-friendly experience to control robots
in varied and challenging environments involves the integration of control
systems, communication networks, and computation servers. In this view, we
consider a remote control setting with limited wireless connectivity where a
human operator controls a robot using a virtual reality (VR) interface that is
updated in real time from the sensory data obtained from the robot [2].
However, due to the stochastic nature of wireless connectivity, the sensing
and controlling links are expected to suffer occasional losses, in which the
robot’s navigation task and the corresponding real-time updates in the VR
space are likely to be interrupted.

In this work, we showcase the remote operation of a robot by a human operator
in a dynamic environment. The operator uses a VR interface, including a 3D
map, which is updated in real-time. If the connection between the robot and
the operator is lost while navigating toward the target destination, the robot
autonomously identifies the connectivity issue. Afterward, the robot processes
the sensor data onboard and adeptly navigates toward its last known
destination while safely avoiding obstacles until the connection is restored.

In this view, our results highlight the adaptability of our semi-autonomous
system, ensuring seamless transitions between remote control and autonomous
navigation. Successful navigation to the last known destination during limited
connectivity underscores the efficiency of our approach, promising improved
human-robot interaction in dynamic environments.

Figure 1: The robotic platform highlighting the components and wireless
connectivity. The red and blue lines represent the connection between each
device, with dashed lines showing wireless connections and continuous lines
showing wired connections.

##  II System Architecture & Hardware

We consider the demo setup shown in Fig. 1 to consist of a robot remotely
controlled by a human using VR glasses. Communication between the robot and
the VR glasses takes place through a WiFi network. We use the Waveshare JetBot
robot operating system (ROS) artificial intelligence (AI) Kit as a mobile
robot equipped with a 2D light detection and ranging (LiDAR) sensor, an
inertial measurement unit (IMU) sensor, and motor encoder sensors. The LiDAR
model is RPLiDAR A1, which has a scanning frequency of $5.5$ Hz and offers a
range distance of $0.15\sim 12$ m with an accuracy of $1\%$ for distances less
than $3$ m, comprising $1147$ sample points per scan [3].

In this setting, we use two servers referred to as $S_{\alpha}$, and
$S_{\beta}$, as shown in Fig. 1. The server $S_{\alpha}$ provides remote
access to the robot and thus is used only to monitor and visualize the robot’s
point of view. On the server $S_{\alpha}$ we use ROS visualization (RViz), a
tool built by ROS, to visualize the robot’s navigation and sensor data. A Dell
i3 laptop running on the Ubuntu operating system (OS) and ROS framework is
used as $S_{\alpha}$.

The server $S_{\beta}$ running Windows 11 OS is used to connect the Varjo VR-1
headset [4], which acts as an interface to the human operator. In this way, we
use Unity software to visualize the robot on a virtual 3D map with the
connection facilitated through Varjo Unity extended reality (XR) software
development kit (SDK) [5]. The virtual 3D map that is processed via Unity
software is used to visualize the environment through VR glasses. To enable
communication between the robot publishing sensing data on ROS topics and the
Unity software running on a Windows machine $S_{\beta}$, it is essential to
appropriately convert the ROS topics into custom messages compatible with
Unity ROS.

The robot communicates with servers $S_{\alpha}$ and $S_{\beta}$ using the
publish-subscribe framework of ROS for data exchange.The data published
includes information about obstacle locations, path planning information, live
video feed, and the robot’s odometer readings. Data are sent to the remote
server $S_{\beta}$ in a custom ROS message format. To facilitate data
transfer, we utilize the Unity ROS transmission control protocol (TCP)
connectoron server $S_{\beta}$.

Figure 2: The visualization of SLAM showing different areas: collision-free
(light gray), unexplored (dark green), occupied and inaccessible areas
(black).

##  III System Implementation

This demo is composed of four key software solutions: (i) creating a 2D map
for navigation, (ii) remote control through VR glasses, (iii) detection of the
status of robot-sever connectivity, and (iv) autonomous navigation. The
following sections provide detailed information on each of these aspects.

###  III-A Creating a 2D Map for Navigation

Our demo project showcases scenarios where a robot is remotely controlled
under occasional changes in the destination set by a human operator in unknown
areas. To facilitate a better experience for the operator as well as to be
able to autonomously navigate under possible losses in remote connectivity, it
is essential to generate a map of its operating environment. To this end, we
implement a simultaneous localization and mapping (SLAM) technique that can
adapt to dynamic changes in the environment. SLAM plays a central role in the
field of robotics and autonomous systems. It enables autonomous vehicles to
create maps of their surroundings while simultaneously determining their own
position within these maps.

Here, we utilize the TurtleBot3 SLAM gmapping package ROS [6] to create the 2D
environment map. As illustrated in Fig. 1, our test area contains several
obstacles. Then, as the robot moves around this test area, SLAM uses the 2D
LiDAR data to create the environment map. We can visualize the creation of the
2D map using $S_{\alpha}$, as shown in Fig. 2. In $S_{\alpha}$ we can observe
the different areas of the 2D maps, such as collision-free, unexplored,
occupied, and inaccessible areas. Fig. 2 shows the real-time discovery and
construction of the 2D map with each area represented by a different color.
The map is constructed as a 2D occupancy grid map (OGM), commonly used in the
ROS community. After exploring the test area, the robot saves the OGM map
locally for future use.

###  III-B Remote control via VR glasses

Figure 3: Initial position of the robot on a) the physical test area and b)
the virtual map.

In this section, we explore remotely maneuvering the robot to a specified
destination using VR glass, referred to as the _remote control mode_. We use a
3D virtual map of our test area [7] and set the robot’s initial position
approximately the same on both the virtual map and the physical test area, as
illustrated in Fig. 3. Afterward, the operator sets a destination on the
previously created 2D map.

In the 3D virtual map, the position and orientation of the virtual robot are
continuously updated using the odometry data received from the physical robot.
Meanwhile, the LiDAR data offers insight into obstacles within the test area
to $S_{\beta}$. Although $S_{\beta}$ does not have object recognition
capability, it is crucial to provide obstacle information through the VR
interface to the human operator for remote control. In this view, obstacles
are visualized as brown wall segments in the virtual map, which are updated in
real-time on both the 3D map and on the VR headset view, as illustrated in
Figs. 4a and 4b, respectively. To validate the accuracy of the real-time
visualization, the robot’s live video feed is also projected on the VR view,
as shown in Fig. 4b.

It is worth highlighting that real-time remote control and virtual map
updating are based on the wireless connectivity between the robot and
$S_{\beta}$. During a loss of connectivity, both sensing and controlling fail,
and thus, the navigation procedure gets interrupted. To ensure seamless
operation, it is essential to devise mechanisms to detect connectivity loss
and to be able to switch from remote control to autonomous mode (and vice
versa).

Figure 4: The 3D virtual environment at the operator’s end.

###  III-C Detection of the robot-server connectivity status

Here, we discuss the process of identifying the loss of connectivity between
the robot and the server $S_{\beta}$. To identify the quality of the
connection between the robot and the server $S_{\beta}$, the robot
periodically sends a ping command with an interval of $0.1$s directly to a
known internet protocol (IP) address of $S_{\beta}$. If the response code from
server $S_{\beta}$ is $0$, it indicates a good connectivity status, otherwise
it suggests poor or no connectivity. As long as the connection status is good,
the robot operates in the remote control mode and can be operated by the human
operator. In any other case, the robot switches from remote control mode to
_autonomous mode_ , which is discussed next.

###  III-D Autonomous navigation

The _autonomous mode_ allows the robot to operate seamlessly in the absence of
connectivity to the remote operator. Here, navigation is based on computing
the shortest path from the current position to the last known target location
using the TurtleBot3 Navigation ROS package [6]. Upon detecting a loss of
connection between the robot and the $S_{\beta}$, the robot publishes the
target location data using geometry_msgs/PoseStamped ROS message type from the
/move_base_simple/goal rostopic to enable the functionality of autonomous
navigation.

It is worth highlighting that any real-time changes taking place in the
environment are perceived by the LiDAR sensors, and therefore the OGM and the
cost map are updated simultaneously. The cost map is a grid in which every
cell is assigned a value (cost) that determines the distance from the
obstacle, where a higher value means a closer distance. The cost map is
provided by the TurtleBot3 Navigation package ROS. With OGM and the dynamic
information from the cost map, the robot continuously refines its planned
trajectory, focusing on the shortest collision-free path, ensuring collision-
free navigation. Fig. 5 shows a snapshot on the server $S_{\alpha}$ during
autonomous navigation mode, illustrating the calculated shortest path that the
robot follows. Since the robot simultaneously checks the connectivity status,
upon restoring the connection with $S_{\beta}$, the operation mode is switched
back to _remote control_ and the procedure defined in Sec. III-B is carried
out with the modifications made by the human operator.

During the _autonomous mode_ , no sensing data are available at $S_{\beta}$,
yet the virtual robot on the virtual map is designed to follow the last
computed shortest path at a constant speed to mimic the behavior of the
physical robot. Displaying the last computed shortest path through VR glasses
serves two purposes in enhancing the seamless experience for the human
operator: (i) The continuous updates in the virtual world are used to avoid
lags and freezes in the VR interface and (ii) the risk and the degree of the
virtual robot’s teleportation (sudden jump from one location to another) upon
the connection restoration is reduced.

Figure 5: A snapshot at the $S_{\alpha}$ during the autonomous mode. Since
there is no remote connectivity and control, the robot (black square) follows
the calculated trajectory (black curve) towards the last known destination
(red arrow).

###  III-E Demo, Resources, and Future Developments

The software related to the robot and servers is available at
https://github.com/ICONgroupCWC/Real-Time_VR_RemoteControl. Future directions
include the fusion of 3D LiDAR point cloud data and depth camera information
and the development/improvement of 3D SLAM methods to improve accuracy and
understanding of the environment for real-time robotic navigation. This demo
in action can be seen from https://youtu.be/1Hd78-bGPe0

## References

  * [1] M. Selvaggio _et al._ , “Autonomy in physical human-robot interaction: A brief survey,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 4, pp. 7989–7996, 2021.
  * [2] S. Kalamkar _et al._ , “Remote monitoring and teleoperation of autonomous vehicles—is virtual reality an option?” in _2023 IEEE International Symposium on Mixed and Augmented Reality_. Los Alamitos, CA, USA: IEEE Computer Society, 2023, pp. 463–472.
  * [3] SLAMKit, “RPLIDAR A1,” Available at https://www.slamtec.com/en/Lidar/A1/, 2016.
  * [4] Varjo, “VR-1 headset,” Available at https://varjo.com/, 2019.
  * [5] Varjo, “Unity XR SDK,” Available at https://developer.varjo.com/docs/unity-xr-sdk/unity-xr-sdk, 2019.
  * [6] ROBOTIS e-manual, “TurtleBot3,” Available at https://emanual.robotis.com/docs/en/platform/turtlebot3/overview/#overview.
  * [7] UBICOMP, “Virtual Campus,” Available at https://ubicomp.oulu.fi/infrastructure-virtual-campus, 2016.