#  Continuous hidden shift problem on $\mathbb{R}^{n}$

Eunok Bae<EMAIL_ADDRESS>Department of Mathematics and Research Institute
for Basic Sciences, Kyung Hee University, Seoul 02447, Korea  Soojoon Lee
<EMAIL_ADDRESS>Department of Mathematics and Research Institute for Basic
Sciences, Kyung Hee University, Seoul 02447, Korea

###### Abstract

There have been several research works on the hidden shift problem, quantum
algorithms for the problem, and their applications. However, all the results
have focused on discrete groups. So, we define a continuous hidden shift
problem on $\mathbb{R}^{n}$ as an extension of the hidden shift problem, and
construct a quantum computing algorithm for solving this problem efficiently.

##  I Introduction

Quantum computers can solve certain problems exponentially faster than
classical computers by taking advantage of the quantum mechanical properties
such as quantum interference and superposition. Many researchers have been
studying algebraic problems which can be solved efficiently on a quantum
computer, for instance, hidden subgroup problem Simon (1997); Shor (1997);
Ettinger and Høyer (2000); Ettinger et al. (2004); Kuperberg (2005); Hallgren
(2005); Schmidt and Vollmer (2005); Kuperberg (2013), hidden shift problem
Friedl et al. (2003); van Dam et al. (2006); Childs and van Dam (2007);
Ivanyos (2008), hidden polynomial problem Childs and Wocjan (2007); Decker et
al. (2009, 2014), and hidden symmetry subgroup problem Decker et al. (2013);
Kim et al. . In particular, the hidden shift problem has provided a frame work
to solve various problems such as the shift Legendre symbol problem van Dam et
al. (2006), Gauss sum estimation van Dam and Seroussi , and the stabilizer
problem Friedl et al. (2003). It has been shown that several interesting and
important problems have been related to the hidden shift problem. For example,
it was proved that the hidden shift problem for the abelian group
$\mathbb{Z}_{N}$ can be used to solve some lattice problem over
$\mathbb{Z}_{N}$ Ettinger and Høyer (2000); Regev (2002), and it was also
discovered that an efficient algorithm of the hidden shift problem for the
symmetric group $S_{n}$ would yield an efficient algorithm for the graph
isomorphic problem Childs and Wocjan (2007).

The hidden shift problem can be cast in the following terms: Let $f_{0}$ and
$f_{1}$ be two injective functions from a finite group $G$ to a finite set
satisfying that there exits an element $u$ in $G$ such that the equality
$f_{0}(x)=f_{1}(xu)$ holds for all $x$ in $G$. The task is to find the _hidden
shift_ $u$. Although there is no general algorithm to solve the hidden shift
problem even for abelian groups, it has been known that there are efficient
algorithms to solve the problem for some groups. Friedl et. al Friedl et al.
(2003) found an efficient quantum algorithm for the hidden shift problem over
$\mathbb{Z}_{p}^{n}$ for any fixed prime number $p$, and a similar work for
the problem over the group $\mathbb{Z}_{p^{k}}^{n}$ has been done by Ivanyos
Ivanyos (2008), where $p^{k}$ is any fixed prime power. However, when $m$ is
not a prime power, the hidden shift problem for the group $\mathbb{Z}_{m}^{n}$
still remains unsolved.

All known results on the hidden shift problem have been concerned with only
discrete groups. Thus, it is natural to ask whether there exits an efficient
quantum algorithm for solving a continuous hidden shift problem, which is the
hidden shift problem on a continuous group. Considering a continuous version
of a certain problem can be helpful to solve unsolved problems as in the
results of Eisenträger et. al Eisenträger et al. (2014). They found an
efficient quantum algorithm for solving a continuous hidden subgroup problem
to compute the unit group of an arbitrary degree number field. It was also
shown that the algorithm can pose a threat to certain lattice-based
cryptosystems. In this paper, we consider a hidden shift problem for a
continuous group, and answer the question.

Our paper is organized as follows. In Sec. II, we give a definition of hidden
shift problem on the continuous group $\mathbb{R}^{n}$, and present our
algorithm to solve the problem. In Sec. III, we analyze the efficiency of our
algorithm, and conclude with discussion on our results in Sec. IV.

##  II Hidden shift problem on a continuous group

To deal with the hidden shift problem on a continuous group, we need a
suitable definition. The following definition can be considered as a
continuous version of the original problem.

######  Definition 1 (Continuous hidden shift problem over $\mathbb{R}^{n}$).

Let $S$ be the set of unit vectors in a Hilbert space. For two injective
functions $f_{0},f_{1}:\mathbb{R}^{n}\rightarrow S$, let
$f:\mathbb{R}^{n}\times\mathbb{Z}_{2}\rightarrow S$ be defined by
$f_{a}(x)=f(x,a)$, with the following promises:

  1. 1.

$f(x,0)=f(x+u,1)$ for all $x\in\mathbb{R}^{n}$ and for some
$u\in\mathbb{R}^{n}$;

  2. 2.

There exists $\alpha>0$ such that
$\left\Arrowvert\ket{f(x,a)}-\ket{f(y,b)}\right\Arrowvert\leq\alpha\cdot|x-y-(a-b)u|$
for all $x,y\in\mathbb{R}^{n}$ and $a,b\in\mathbb{Z}_{2}$,

where $\ket{f(\cdot,\cdot)}$ is a pure state corresponding to
$f(\cdot,\cdot)$.

The goal of the problem is to find $u$, which is called the _hidden shift_.

Note that the given oracle function $f$ is efficiently computable, and the
positive constant $\alpha$ in condition 2 is called a _Lipschitz constant_ of
the function $f$.

As in Ref. [20], let us first define a window function
$\omega:\mathbb{R}\rightarrow\mathbb{C}$ as

$\omega(x)=\begin{cases}\sqrt{2}\sin(\pi x)&\mathrm{if}~{}x\in[0,1],\\\
0&\mathrm{otherwise}.\end{cases}$

Then $\omega$ is a Lipschitz function with unit $L^{2}$-norm supported on
$[0,1]$. For a sufficiently large number $\Delta$ and a sufficiently small
number $\delta=\Delta^{-1}$, let us define

$w(x_{1},\dots,x_{n})=\frac{1}{\Delta^{n/2}}\prod_{j=1}^{n}\omega\left(\frac{x_{j}}{\Delta}\right)$

for $x=(x_{1},\dots,x_{n})\in\mathbb{R}^{n}$. For convenience, we assume that
$\Delta=\sqrt{2^{q}}$ for sufficiently large $q$ with $u_{i}^{2}\leq\Delta$
for all $i$.

Now, we are ready to construct our algorithm for solving the hidden shift
problem with the above materials as follows.

######  Algorithm 2 (Quantum algorithm for the hidden shift problem on the
group $\mathbb{R}^{n}$).

_Input_ : The oracle function $f:\mathbb{R}^{n}\times\mathbb{Z}_{2}\rightarrow
S$ that hides the shift $u=(u_{1},\dots,u_{n})\in\mathbb{R}^{n}$.

  1. 0.

If $f(0,0)=f(0,1)$, then output $0$.

  2. 1.

Create the initial state

$\sqrt{\frac{\delta^{n}}{2}}\sum_{\tilde{x}\in\mathbb{Z}^{n}}\sum_{c\in\mathbb{Z}_{2}}w(x)\ket{\tilde{x}}\ket{c}$

with $x=\delta\tilde{x}$.

  3. 2.

Apply the oracle function $f$.

  4. 3.

Perform the $QFT_{\mathbb{Z}^{n}\times\mathbb{Z}_{2}}$, which can be
implemented by the phase estimation technique as in Ref. Eisenträger et al.
(2014), and measure on the first two registers.

  5. 4.

Consider the samples $(\tilde{y},1)$.

  6. 5.

Use the values of $\tilde{y}$ non-orthogonal to $\tilde{u}$ among the samples
$(\tilde{y},1)$ to find $\tilde{u}$.

  7. 6.

Compute $u=\delta\tilde{u}$.

_Output_ : u

######  Remark 3.

Since it is difficult to compute continuous variables, we need to truncate and
discretize the continuous domain $\mathbb{R}^{n}$ of the oracle functions by
using the window function $w$ and the small number $\delta$. As in Ref.
Eisenträger et al. (2014), we use the following variables in our calculations;
Real Domain: $x=\delta\tilde{x}\in\delta\mathbb{Z}^{n}$ and Fourier Domain:
$y=\delta^{-1}\tilde{y}\in\mathbb{R}^{n}/\delta^{-1}\mathbb{Z}^{n}$

  * •

In Step 2, the state becomes

$\ket{\psi_{\delta}}=\sqrt{\frac{\delta^{n}}{2}}\sum_{\tilde{x}\in\mathbb{Z}^{n}}\sum_{c\in\mathbb{Z}_{2}}w(x)\ket{\tilde{x}}\ket{c}\ket{f(x,c)}.$

  * •

In Step 3, $QFT_{\mathbb{Z}^{n}\times\mathbb{Z}_{2}}$ means the quantum
Fourier transform performing over the group
$\mathbb{Z}^{n}\times\mathbb{Z}_{2}$. As in the original hidden shift problem,
it is necessary to perform the Fourier transform and measure in the standard
basis for the continuous hidden shift problem as well. However, the Fourier
transform over any infinite group cannot be implemented by a quantum computer.
So, we can perform the approximate quantum Fourier transform on the infinite
group by means of a variation of the phase estimation algorithm on the
register on the group and ancillary register, which was used in Ref.
Eisenträger et al. (2014).

  * •

In Step 5, we reduce the hidden shift problem to the random-linear-
disequations problem to find the hidden shift $u$ as in the method of Ref.
Ivanyos (2008).

##  III Analysis of our algorithm

In this section, we analyze our quantum algorithm presented in the above
section. As in the way of Ref. Eisenträger et al. (2014), instead of directly
measuring in the Fourier basis of the continuous group directly, we use the
phase estimation to approximate the probability distribution $p_{\delta}(y,1)$
of the variable $\delta^{-1}\tilde{y}$ by the distribution of $p(y,1)$, when
$\delta$ is close to $0$. We can derive these two distributions from the
following quantum states:

$\displaystyle\ket{\psi_{\delta}}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{\delta^{n}}{2}}\sum_{\tilde{x}\in\mathbb{Z}^{n}}\sum_{c\in\mathbb{Z}_{2}}\ket{\tilde{x}}\ket{c}\ket{\psi(x,c)},$
$\displaystyle\ket{\psi}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\int_{\mathbb{R}^{n}}\sum_{c\in\mathbb{Z}_{2}}\ket{x}\ket{c}\ket{\psi(x,c)}dx,$

where $\ket{\psi(x,c)}=w(x)\ket{f(x,c)}$. Precisely, $p_{\delta}$ and $p$ are
from the Fourier transform of $\psi_{\delta}$ and $\psi$, respectively:

$\displaystyle p_{\delta}(y,1)$ $\displaystyle=$
$\displaystyle\left\langle{\hat{\psi_{\delta}}(y,1)}|{\hat{\psi_{\delta}}(y,1)}\right\rangle,$
$\displaystyle p(y,1)$ $\displaystyle=$
$\displaystyle\left\langle{\hat{\psi}(y,1)}|{\hat{\psi}(y,1)}\right\rangle$

with $\hat{\psi_{\delta}}=F_{\delta\mathbb{Z}^{n}}\psi_{\delta}$ and
$\hat{\psi}=F_{\mathbb{R}^{n}}\psi$. We can show that $p_{\delta}$ goes to $p$
as $\delta$ approaches $0$.

So, it is enough to focus on the distribution $p(y,1)$ which can be calculated
precisely as follows.

$\displaystyle p(y,1)$ $\displaystyle=$
$\displaystyle\left\langle{\hat{\psi}(y,1)}|{\hat{\psi}(y,1)}\right\rangle$
$\displaystyle=$
$\displaystyle\frac{1}{4}\int_{\mathbb{R}^{n}}\left|w(x)-e^{2\pi
i\left<x,y\right>}w(x+u)\right|^{2}dx$ $\displaystyle=$
$\displaystyle\frac{1}{4}\left[\int_{[0,\Delta]^{m}}w(x)^{2}+w(x+u)^{2}dx-2\cos
2\pi\left<u,y\right>\int_{[0,\Delta]^{m}}w(x)w(x+u)dx\right]$ $\displaystyle=$
$\displaystyle\frac{1}{2}-\frac{1}{2}\cos(2\pi\left<u,y\right>)\prod_{i=1}^{n}\cos\left(\frac{\pi
u_{i}}{\Delta}\right).$

Although the probability that a sample $y$ is orthogonal to $u$ is not zero,
which is different from the original hidden shift problem, it can be shown
that the probability is (exponentially) small when $n$ is large enough by the
following Propositions and Lemma. In other words, the samples $(y,1)$ after
the Fourier sampling subroutine are mostly non-orthogonal to $u$.

In order to show that the probability that a sample $y$ is orthogonal to $u$
is small enough when $n$ is sufficiently large, we consider the case when the
number of $y$ satisfying the equation $\left<u,y\right>=0$ attains a maximum
value. Note that we actually get the samples $\tilde{y}$ instead of $y$ to
return $\tilde{u}$ first and recover $u$ from $\tilde{u}$ in the practical
implementation of our algorithm.

We first show that if $\tilde{u}$ has the same coordinates, the number of
$\tilde{y}$ satisfying the equation $\left<\tilde{u},\tilde{y}\right>=0$ in
$\mathbb{Z}_{2^{q}}$ becomes less than when we make one of the same
coordinates of $\tilde{u}$ twice.

######  Proposition 4.

For any $n,k\in\mathbb{N}$, let $q=4k$. The number of
$\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ which is orthogonal to
$\tilde{u}=(\tilde{u}_{1},\dots,\tilde{u}_{n})$ with
$\tilde{u}_{i}=\tilde{u}_{j}$ for some $i\neq j$ is less than or equal to the
number of $\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ which is orthogonal to
$\tilde{u}^{\prime}=(\tilde{u}_{1}^{\prime},\dots,\tilde{u}_{n}^{\prime})=(\tilde{u}_{1},\dots,2\tilde{u}_{i},\dots,\tilde{u}_{n})$
or $(\tilde{u}_{1},\dots,2\tilde{u}_{j},\dots,\tilde{u}_{n})$

###### Proof.

Without loss of generality, we may assume that $\tilde{u}_{1}=\tilde{u}_{2}$.
We want to show that the number of $\tilde{y}$ satisfying
$\left<\tilde{u},\tilde{y}\right>=0$ mod $2^{q}$ for
$\tilde{u}=(\tilde{u}_{1},\tilde{u}_{1},\tilde{u}_{3},\dots,\tilde{u}_{n})$ is
less than or equal to the number of $\tilde{y}$ satisfying
$\left<\tilde{u}^{\prime},\tilde{y}\right>=0$ mod $2^{q}$ for
$\tilde{u}^{\prime}=(2\tilde{u}_{1},\tilde{u}_{1},\tilde{u}_{3},\dots,\tilde{u}_{n})$.
We can establish an injective function from the solutions
$\tilde{y}=(\tilde{y_{1}},\dots,\tilde{y_{n}})$ of the equation
$\left<\tilde{u},\tilde{y}\right>=\sum_{i=1}^{n}\tilde{u_{i}}\tilde{y_{i}}=0$
mod $2^{q}$ to the solutions
$\tilde{y}^{\prime}=(\tilde{y}_{1}^{\prime},\dots,\tilde{y}_{n}^{\prime})$ of
the equation $\left<\tilde{u}^{\prime},\tilde{y}^{\prime}\right>=0$ mod
$2^{q}$ as follows.

$(\tilde{y}_{1},\dots,\tilde{y}_{n})\longrightarrow(\tilde{y}_{1}^{\prime},\dots,\tilde{y}_{n}^{\prime})=\begin{cases}(m_{1},y_{2},\dots,y_{n})&\textrm{if}~{}~{}\tilde{y}_{1}=2m_{1},\\\
(m_{1},y_{2}-1,\dots,y_{n})&\textrm{if}~{}~{}\tilde{y}_{1}=2m_{1}-1.\end{cases}$

Then it can be easily shown that
$\left<\tilde{u},\tilde{y}\right>=\left<\tilde{u}^{\prime},\tilde{y}^{\prime}\right>$.
In fact, if $\tilde{y}_{1}=2m_{1}$, then

$\displaystyle\left<\tilde{u}^{\prime},\tilde{y}^{\prime}\right>=\tilde{u}_{1}^{\prime}m_{1}+\tilde{u}_{2}^{\prime}\tilde{y}_{2}^{\prime}+\cdots+\tilde{u}_{n}^{\prime}\tilde{y}_{n}^{\prime}=2\tilde{u}_{1}m_{1}+\tilde{u}_{2}\tilde{y}_{2}+\cdots+\tilde{u}_{n}\tilde{y}_{n}=\left<\tilde{u},\tilde{y}\right>.$

Similary, if $\tilde{y}_{1}=2m_{1}-1$, then

$\displaystyle\left<\tilde{u}^{\prime},\tilde{y}^{\prime}\right>$
$\displaystyle=$
$\displaystyle\tilde{u}_{1}^{\prime}m_{1}+\tilde{u}_{2}^{\prime}(\tilde{y}_{2}-1)+\cdots+\tilde{u}_{n}^{\prime}\tilde{y}_{n}^{\prime}$
$\displaystyle=$ $\displaystyle
2\tilde{u}_{1}m_{1}+\tilde{u}_{1}\tilde{y}_{2}-\tilde{u}_{1}+\cdots+\tilde{u}_{n}\tilde{y}_{n}$
$\displaystyle=$
$\displaystyle\tilde{u}_{1}(2m_{1}-1)+\tilde{u}_{1}\tilde{y}_{2}+\cdots+\tilde{u}_{n}\tilde{y}_{n}=\left<\tilde{u},\tilde{y}\right>.$

∎

For the next step, we show that if all coordinates of $\tilde{u}$ has the form
of $2^{t}$, the number of $\tilde{y}$ which is orthogonal to $\tilde{u}$
becomes less than when we change the smallest coordinates of $\tilde{u}$ to
the second smallest one.

######  Proposition 5.

For any $n,k\in\mathbb{N}$, let $q=4k$ and let
$\tilde{u}=(2^{t_{1}},\dots,2^{t_{n}})$ such that $t_{i}\leq k$ for all $i$
and $t_{i}$’s are all distinct, say $t_{i_{1}}<\cdots<t_{i_{n}}$ with
$i_{j}\in[n]$. The number of $\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ which is
orthogonal to $\tilde{u}=(2^{t_{1}},\dots,2^{t_{n}})$ is less than or equal to
the number of $\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ which is orthogonal to
$\tilde{u}^{\prime}=(\tilde{u}_{1}^{\prime},\dots,\tilde{u}_{n}^{\prime})$
with

$\tilde{u}_{i}^{\prime}=\begin{cases}2^{t_{i_{2}}}&i=i_{1},\\\ 2^{t_{i}}&i\neq
i_{1}.\end{cases}$

###### Proof.

Suppose that $\tilde{u_{i}}^{\prime}$ are all distinct. Without loss of
generality, assume that $t_{1}<t_{2}<\cdots<t_{n}$, where $t_{i}\leq k$ for
all $i$. Then we can construct an injective functions from the solutions
$\tilde{y}=(\tilde{y}_{1},\dots,\tilde{y}_{n})$ of the equation
$\left<\tilde{u},\tilde{y}\right>=0$ mod $2^{q}$ for
$\tilde{u}=(2^{t_{1}},\dots,2^{t_{n}})$ to the solutions
$\tilde{y}^{\prime}=(\tilde{y}_{1}^{\prime},\dots,\tilde{y}_{n}^{\prime})$ of
the equation $\left<\tilde{u}^{\prime},\tilde{y}^{\prime}\right>=0$ mod
$2^{q}$ for $\tilde{u}^{\prime}=(2^{t_{2}},2^{t_{2}},\dots,2^{t_{n}})$ as
follows.

$(\tilde{y}_{1},\dots,\tilde{y}_{n})\longrightarrow(\tilde{y}_{1}^{\prime},\dots,\tilde{y}_{n}^{\prime})=(2^{t_{1}-t_{2}}\tilde{y}_{1},\tilde{y}_{2},\dots,\tilde{y}_{n}).$

Note that $\tilde{y}_{1}$ is a multiple of $2^{t_{2}-t_{1}}$. Indeed, since
the condition $\left<\tilde{u},\tilde{y}\right>=0$ mod $2^{q}$ implies that

$\displaystyle\tilde{y}_{1}+2^{t_{2}-t_{1}}\left(\tilde{y}_{2}+2^{t_{3}-t_{2}+t_{1}}\tilde{y}_{3}+\dots+2^{t_{n}-t_{2}+t_{1}}\tilde{y}_{n}\right)=l2^{q-t_{1}}~{}~{}\mathrm{for}~{}~{}l=0,1,\dots,\sum_{i=1}^{n}\tilde{u}_{i}-1,$

it is clearly true that $2^{t_{2}-t_{1}}|\tilde{y}_{1}$ and hence,
$\tilde{y}_{1}^{\prime}$ belongs to $\mathbb{Z}_{2^{q}}$.

Also, we have

$\left<\tilde{u}^{\prime},\tilde{y}^{\prime}\right>=2^{t_{2}}(2^{t_{1}-t_{2}}\tilde{y}_{1})+2^{t_{2}}\tilde{y}_{2}+\cdots+2^{t_{n}}\tilde{y}_{n}=\left<\tilde{u},\tilde{y}\right>.$

∎

On the other hand, when $\tilde{u}$ has at least one coordinate which cannot
be written as the form of $2^{t}$, we can show that the number of $\tilde{y}$
which is orthogonal to $\tilde{u}$ is exactly the same as the number of
$\tilde{y}$ which is orthogonal to $\tilde{u}^{\prime}$ whose all coordinates
are in the form of $2^{t}$.

######  Proposition 6.

For any $n,k\in\mathbb{N}$, let $q=4k$ and
$\tilde{u}\in\mathbb{Z}_{2^{q}}^{n}$. If there is $j$ such that
$\tilde{u}_{j}=v2^{t}$ with $\mathrm{gcd}(v,2)=1$ and $t\geq 0$, the number of
$\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ which is orthogonal to $\tilde{u}$ is
exactly the same with the number of $\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ which
is orthogonal to
$\tilde{u}^{\prime}=(\tilde{u}_{1}^{\prime},\dots,\tilde{u}_{n}^{\prime})$
with

$\tilde{u}_{i}^{\prime}=\begin{cases}2^{t}&i=j,\\\ \tilde{u}_{i}&i\neq
j.\end{cases}$

###### Proof.

Without loss of generality, we may assume that $u_{1}\nmid 2^{q}$. Then we can
construct a one-to-one correspondence between the solutions
$\tilde{y}=(\tilde{y}_{1},\dots,\tilde{y}_{n})$ of the equation
$\left<\tilde{u},\tilde{y}\right>=0$ mod $2^{q}$ for
$\tilde{u}=(2^{t}v,\tilde{u}_{2},\dots,\tilde{u}_{n})$ to the solutions
$\tilde{y}^{\prime}=(\tilde{y}_{1}^{\prime},\dots,\tilde{y}_{n}^{\prime})$ of
the equation $\left<\tilde{u}^{\prime},\tilde{y}^{\prime}\right>=0$ mod
$2^{q}$ for $\tilde{u}^{\prime}=(2^{t},\tilde{u}_{2},\dots,\tilde{u}_{n})$ as
follows.

$(\tilde{y}_{1},\dots,\tilde{y}_{n})\longrightarrow(\tilde{y}_{1}^{\prime},\dots,\tilde{y}_{n}^{\prime})=(\tilde{y}_{1}^{\prime},\tilde{y}_{2},\dots,\tilde{y}_{n}),$

where, if $\lfloor
l\frac{2^{q-t}}{v}\rfloor\leq\tilde{y}_{1}<\lfloor(l+1)\frac{2^{q-t}}{v}\rfloor$
for $l=0,1,\dots,\tilde{u}_{1}-1$,

$\tilde{y}_{1}^{\prime}=v\left(\tilde{y}_{1}-\left\lfloor
l\frac{2^{q-t}}{v}\right\rfloor\right)-r_{l}$

with $r_{l}=l2^{q-t}-v\lfloor l\frac{2^{q-t}}{v}\rfloor$ for
$l=0,\dots,\tilde{u}_{1}-1$.

Note that $r_{0}=0$ and $r_{l}\equiv lr_{1}~{}\textrm{mod}~{}v$ for each
$l=1,\dots,\tilde{u}_{1}-1$. Since

$\mathrm{gcd}(v,r_{1})=\mathrm{gcd}(2^{q-t},v)=1,$

$r_{1}\neq 0$ and $r_{l}$’s must be all distinct for each $l\neq 0$. So the
above mapping is bijective. Furthermore, it can be shown that
$\sum_{i=2}^{n}\tilde{u_{i}}\tilde{y_{i}}=\sum_{i=2}^{n}\tilde{u_{i}}^{\prime}\tilde{y_{i}}^{\prime}$
and hence, when $\tilde{y}_{1}$ is fixed, the rest part of $\tilde{y}$,
$(\tilde{y}_{2},\dots,\tilde{y}_{n})$, is exactly same with that of
$\tilde{y}^{\prime}$, $(\tilde{y}_{2}^{\prime},\dots,\tilde{y}_{n}^{\prime})$.
Indeed, for any nonzero $\tilde{y}_{1}$, we can write it as
$\tilde{y}_{1}=\lfloor l\frac{2^{q-t}}{v}\rfloor+m_{l}$ with
$m_{l}\in\\{1,2,\dots,\lfloor(l+1)\frac{2^{q-t}}{v}\rfloor-\lfloor
l\frac{2^{q-t}}{v}\rfloor\\}$. Then

$\displaystyle\tilde{u}_{1}\tilde{y}_{1}=2^{t}\left(v\lfloor
l\frac{2^{q-t}}{v}\rfloor+vm_{l}\right)=2^{t}(l2^{q-t}-r_{l}+vm_{l})=l2^{q}+2^{t}(vm_{l}-r_{l})=l2^{q}+\tilde{u}_{1}^{\prime}\tilde{y}_{1}^{\prime}.$

Since
$\left<\tilde{u},\tilde{y}\right>=\left<\tilde{u}^{\prime},\tilde{y}^{\prime}\right>=0$
mod $2^{q}$, we can get

$\displaystyle\sum_{i=2}^{n}\tilde{u_{i}}\tilde{y_{i}}=(l+a)2^{q}-\tilde{u_{1}}\tilde{y_{1}}=a2^{q}-\tilde{u_{1}}^{\prime}\tilde{y_{1}}^{\prime}=\sum_{i=2}^{n}\tilde{u_{i}}^{\prime}\tilde{y_{i}}^{\prime},$

where $a\in\\{1,2,\dots,\sum_{i=2}^{n}\tilde{u_{i}}\tilde{y_{i}}\\}$. ∎

Combining the above propositions, we finally prove that the number of
$\tilde{y}$ which is orthogonal to $\tilde{u}$ attains a maximum value when
all coordinate of $\tilde{u}$ has the maximum value, $2^{k}$, and thus we can
get an upper bound of the probability that $\tilde{y}$ is orthogonal to
$\tilde{u}$.

######  Lemma 7.

For any $n,k\in\mathbb{N}$, let $q=4k$, $\Delta=2^{q/2}$ and
$\tilde{u}\in\mathbb{Z}_{2^{q}}^{n}$. The number of
$\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ which is orthogonal to $\tilde{u}$ has
the maximum value, $2^{k(4n-3)}$, when
$\tilde{u}=(\tilde{u}_{1},\dots,\tilde{u}_{n})=(\sqrt{\Delta},\dots,\sqrt{\Delta})$.
Moreover, the probability that $\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ is
orthogonal to $\tilde{u}$ is at most $1/2^{3k}$ in our algorithm.

###### Proof.

By repeated use of Proposition 6, we know that the number of solutions
$\tilde{y}$ satisfying the equation $\left<\tilde{u},\tilde{y}\right>=0$ mod
$2^{q}$ when there is $j$ such that $\tilde{u}_{j}\nmid 2^{q}$ is always equal
to the number of that when $\tilde{u}=(2^{t_{1}},\dots,2^{t_{n}})$ for some
$(t_{1},\dots,t_{n})$ with $t_{i}\leq k$ for all $i$.

Now, let us consider the case when $\tilde{u}=(2^{t_{1}},\dots,2^{t_{n}})$
with $t_{i}\leq k$ for all $i$. Without loss of generality, we may assume that
$t_{1}\leq\cdots\leq t_{n}$ with $i_{j}\in[n]$. If $t_{i}$’s are all distinct,
it follows from Proposition 5 that the number of the solutions $\tilde{y}$
satisfying the equation $\left<\tilde{u},\tilde{y}\right>=0$ mod $2^{q}$ is
less than or equal to the number of the solutions in the case when we raise
$t_{1}$ up to $t_{2}$. If $t_{i}=t_{j}$ for some $i\neq j$, by applying
Proposition 4 and Proposition 5 repeatedly, we can show that the number of the
solutions $\tilde{y}$ satisfying the equation
$\left<\tilde{u},\tilde{y}\right>=0$ mod $2^{q}$ is less than or equal to the
number of solutions in the case when we raise $t_{i}$ up to $\max_{i}t_{i}$
for all $i$. Therefore, the number of $\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$
which is orthogonal to $\tilde{u}$ has the maximum value when
$\tilde{u}=(2^{k},\dots,2^{k})$.

For the next step, we want to calculate the exact number of $\tilde{y}$
satisfying $\left<\tilde{u},\tilde{y}\right>=0$ mod $2^{q}$ when
$\tilde{u}=(2^{k},\dots,2^{k})$. Note that
$\tilde{y}_{i}\in\mathbb{Z}_{2^{q}}^{n}$ so that $0\leq\tilde{y}_{i}\leq
2^{q}-1$ for all $i$. We can prove that the number of integer solutions
$\tilde{y}$, $0\leq\tilde{y}_{i}\leq 2^{q}-1$ for all $i$, of the equation
$2^{k}\tilde{y}_{1}+\cdots+2^{k}\tilde{y}_{n}=0$ mod $2^{q}$ is

$2^{k}\sum_{i=0}^{n-1}(-1)^{i}\binom{n-1}{i}\binom{n-1+(n-i)2^{4k}-2^{3k}}{n-1}=2^{k}2^{4k(n-1)}=2^{k(4n-3)}$

by induction on $n\geq 1$ (See Appendix A for the detailed proof).

Since the number of all possible $\tilde{y}$ is $2^{qn}$, the probability that
$\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ is orthogonal to $\tilde{u}$ is at most
$2^{k(4n-3)}/2^{qn}$ which is equal to $1/2^{3k}$.

∎

Thus, we can apply the classical method in Ref. Ivanyos (2008) to find the
hidden shift $u$ with high probability in polynomial time in $n$, and we have
the following theorem.

######  Theorem 8.

There is a quantum algorithm for solving the continuous hidden shift problem
on $\mathbb{R}^{n}$ in polynomial time in $n$.

###### Proof.

In the problem, we first set the number $\Delta$ as $\sqrt{2^{q}}$ with some
sufficiently large $q$ which makes the condition $u_{i}^{2}\leq\Delta$ hold
for all $i$. As we can see in Ref. Eisenträger et al. (2014), we can perform
the approximate Fourier transformation to get approximate samples with the
desired precision. It follows from Lemma 7 that the probability that the
samples are non-orthogonal to the hidden shift $u$ is bounded above by some
small constant number. Now, we can use the method in Ref. Ivanyos (2008) to
calculate $u$ in quantum polynomial time in $n$. In detail, the hidden shift
problem over $\mathbb{Z}_{2^{q}}^{n}$ can be reduced to the decision version
of Random Linear Disequations$(\mathbb{Z}_{2^{q}}^{n},2)$. The authour of Ref.
Ivanyos (2008) shows that the decision version of Random Linear Disequations
is reducible to its decision version in the abelian group $\mathbb{Z}_{m}^{n}$
for any numbers $n$ and $m$. Thus, we can get the hidden shift $u$ as the
output of the search version of Random Linear Disequations in
$\mathbb{Z}_{2^{q}}^{n}$. Here, all reductions can be done in the polynomial
time in $n$. ∎

##  IV Discussion

It has been known that the hidden shift problem over discrete groups can
affect cryptosystems Alagic and Russell (2017); Bonnetain and Naya-Plasencia
(2018). In particular, Bonnetain and Naya-Plasencia Bonnetain and Naya-
Plasencia (2018) recently constructed an efficient quantum algorithm to solve
the hidden shift problem over the abelian group $\mathbb{Z}_{2^{p}}^{w}$, and
proved that the algorithm can be used to establish a quantum attack in a
cryptosystem claimed to be secure quantumly.

In this work, we have defined a continuous hidden shift problem over the group
$\mathbb{R}^{n}$, and have shown that a quantum computer can efficiently solve
the problem. Thus it is natural to consider whether the continuous version of
this problem can also have any crypto-related applications. In fact, a similar
consideration has been involved in the previous results. In Refs. Eisenträger
et al. (2014); Biasse and Song (2016), it has been shown that a continuous
hidden subgroup problem induces a quantum attack on cryptosystems based on the
hardness of finding a short generator of a principal ideal, although the
discrete hidden subgroup problem cannot break them Hallgren (2005, 2007).
Inspired by these results, we expect that our result could have an application
related to cryptography.

Whereas the original hidden shift problem restricts the oracle function to be
injective, the hidden shift problem without this restriction can be also
considered. van Dam _et al._ van Dam et al. (2006) gave three types of the
hidden shift problems with non-injective oracle functions, and one of them is
the _shift Legendre symbol problem_ which has an application to any
algebraically homomorphic encryption van Dam et al. (2006). Therefore, it
would be meaningful to consider a continuous version of the hidden shift
problem without the injectivity assumption for the next step.

###### Acknowledgements.

This work was supported by Basic Science Research Program through the National
Research Foundation of Korea (NRF) funded by the Ministry of Science and ICT
(NRF-2016R1A2B4014928) and the MSIT (Ministry of Science and ICT), Korea,
under the ITRC (Information Technology Research Center) support program
(IITP-2018-2018-0-01402) supervised by the IITP (Institute for Information &
communications Technology Promotion). S. L. acknowledges support from Research
Leave Program of Kyung Hee University in 2018.

## References

  * Simon (1997) D. R. Simon, SIAM Journal on Computing 26, 1474 (1997).
  * Shor (1997) P. W. Shor, SIAM Journal on Computing 26, 1484 (1997).
  * Ettinger and Høyer (2000) M. Ettinger and P. Høyer, Advances in Applied Mathematics 25, 239 (2000).
  * Ettinger et al. (2004) M. Ettinger, P. Høyer, and E. Knill, Information Processing Letters 91, 43 (2004).
  * Kuperberg (2005) G. Kuperberg, SIAM Journal on Computing 35, 170 (2005).
  * Hallgren (2005) S. Hallgren, in _Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC’05_ (2005), pp. 468–474.
  * Schmidt and Vollmer (2005) A. Schmidt and U. Vollmer, in _Proceedings of the 37th ACM Symposium on Theory of Computing, STOC’05_ (2005), pp. 475–480.
  * Kuperberg (2013) G. Kuperberg, in _Leibniz International Proceedings in Informatics, LIPIcs’13_ (2013), vol. 22, pp. 20–34.
  * Friedl et al. (2003) K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen, in _Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC’03_ (2003), pp. 1–9.
  * van Dam et al. (2006) W. van Dam, S. Hallgren, and L. Ip, SIAM Journal on Computing 36, 763 (2006).
  * Childs and van Dam (2007) A. M. Childs and W. van Dam, in _Proceedings of the 18th Symposium on Discrete Algorithms, SODA’07_ (2007), pp. 1225–1232.
  * Ivanyos (2008) G. Ivanyos, Quantum Information & Computation 8, 579 (2008).
  * Childs and Wocjan (2007) A. M. Childs and P. Wocjan, Quantum Information & Computation 7, 504 (2007).
  * Decker et al. (2009) T. Decker, J. Draisma, and P. Wocjan, Quantum Information & Computation 9, 215 (2009).
  * Decker et al. (2014) T. Decker, P. Høyer, G. Ivanyos, and M. Santha, Quantum Information & Computation 14, 790 (2014).
  * Decker et al. (2013) T. Decker, G. Ivanyos, M. Santha, and P. Wocjan, SIAM Journal on Computing 42, 1987 (2013).
  * (17) J. S. Kim, E. Bae, and S. Lee, arXiv:1307.1183.
  * (18) W. van Dam and G. Seroussi, arXiv:quant-ph/0207131.
  * Regev (2002) O. Regev, SIAM Journal on Computing 33, 738 (2002).
  * Eisenträger et al. (2014) K. Eisenträger, S. Hallgren, A. Kitaev, and F. Song, in _Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC’14_ (2014), pp. 293–302.
  * Alagic and Russell (2017) G. Alagic and A. Russell, in _Advances in Cryptology, EUROCRYPT’17_ (2017), pp. 65–93.
  * Bonnetain and Naya-Plasencia (2018) X. Bonnetain and M. Naya-Plasencia, Lecture Notes in Computer Science 11272, 560 (2018), ePrint Archive, Report 2018/432 (2018), https://eprint.iacr.org/2018/432.
  * Biasse and Song (2016) J.-F. Biasse and F. Song, in _Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’16_ (2016).
  * Hallgren (2007) S. Hallgren, Journal of the ACM 54, 1 (2007).

## Appendix A

In this appendix, we prove that the number of integer solutions
$\tilde{y}\in\mathbb{Z}^{n}$, $0\leq\tilde{y}_{i}\leq 2^{q}-1$ for all $i$, of
the equation $2^{k}\tilde{y}_{1}+\cdots+2^{k}\tilde{y}_{n}=0$ mod $2^{q}$ is

$2^{k}\sum_{i=0}^{n-1}(-1)^{i}\binom{n-1}{i}\binom{n-1+(n-i)2^{4k}-i2^{3k}}{n-1}=2^{k}2^{4k(n-1)}=2^{k(4n-3)}$
(1)

by induction on $n\geq 1$.

To do this, we need the following propositions.

######  Proposition 9.

For any fixed numbers $L,l$ with $L\geq nl$ and $n\geq 0$,

$\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{L-il}{n}=\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{L-il-1}{n}$
(2)

###### Proof.

We use the induction on $n$. If $n=0$, the statement is clearly true. Thus let
us suppose that Eq. (2) holds for a certain $n\geq 0$. Observe that

$\displaystyle\sum_{i=0}^{n+1}(-1)^{i}\binom{n+1}{i}\binom{L-il}{n+1}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{n+1}(-1)^{i}\binom{n+1}{i}\left[\binom{L-il-1}{n+1}+\binom{L-il-1}{n}\right]$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{n+1}(-1)^{i}\binom{n+1}{i}\binom{L-il-1}{n+1},$

and hence Eq. (2) holds for $n+1$ as well. Here, the last equality holds since

$\displaystyle\sum_{i=0}^{n+1}(-1)^{i}\binom{n+1}{i}\binom{L-il-1}{n}$
$\displaystyle=$
$\displaystyle\binom{n}{0}\binom{L-1}{n}+(-1)^{n+1}\binom{n}{n}\binom{L-(n+1)l-1}{n}$
$\displaystyle+\sum_{i=1}^{n+1}(-1)^{i}\
\left[\binom{n}{i}+\binom{n}{i-1}\right]\binom{L-il-1}{n}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{L-il-1}{n}-\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{L-(i+1)l-1}{n}$
$\displaystyle=$ $\displaystyle 0,$

by using the induction hypothesis $l$ times. ∎

Now, using Proposition 9, we can prove the following proposition, which can be
directly used to prove the Eq. (1).

######  Proposition 10.

For each $i=1,2,\dots,2^{k}$ and $n\geq 1$,

$\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n-1+(n-j)2^{4k}-i2^{3k}}{n-1}=2^{4k(n-1)}$
(3)

###### Proof.

We prove this proposition by induction on $n\geq 1$. It is easy to check that
the statement is true for $n=1$. Now, suppose that it is true for a fixed
$n\geq 1$. It follows from the Pascal’s triangle that

$\displaystyle\mathcal{L}$ $\displaystyle\equiv$
$\displaystyle\sum_{j=0}^{n}(-1)^{j}\binom{n}{j}\binom{n+(n+1-j)2^{4k}-i2^{3k}}{n}$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n+(n+1-j)2^{4k}-i2^{3k}}{n}$
$\displaystyle-\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n+(n-j)2^{4k}-i2^{3k}}{n}.$

By applying the Pascal’s triangle to the second binomial coefficient term in
the first summation,

$\displaystyle\mathcal{L}$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n-1+(n+1-j)2^{4k}-i2^{3k}}{n}+\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n-1+(n+1-j)2^{4k}-i2^{3k}}{n-1}$
$\displaystyle-\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n+(n-j)2^{4k}-i2^{3k}}{n}$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n-1+(n+1-j)2^{4k}-i2^{3k}}{n}+2^{4k(n-1)}-\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n+(n-j)2^{4k}-i2^{3k}}{n}$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n-2+(n+1-j)2^{4k}-i2^{3k}}{n}+2\cdot
2^{4k(n-1)}-\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n+(n-j)2^{4k}-i2^{3k}}{n},$

where the second and the last equalities come from the induction hypothesis.
Continuing this procedure $2^{4k}$ times, it can be shown that

$\displaystyle\mathcal{L}$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n+(n-j)2^{4k}-i2^{3k}}{n}+2^{4k}2^{4k(n-1)}-\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n+(n-j)2^{4k}-i2^{3k}}{n}$
$\displaystyle=$ $\displaystyle 2^{4kn},$

which completes the proof.

∎

Now, we show that the number of integer solutions
$\tilde{y}\in\mathbb{Z}^{n}$, $0\leq\tilde{y}_{i}\leq 2^{q}-1$ for all $i$, of
the equation $2^{k}\tilde{y}_{1}+\cdots+2^{k}\tilde{y}_{n}=0$ mod $2^{q}$ is

$\sum_{i=1}^{2^{k}}\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n-1+(n-j)2^{4k}-i2^{3k}}{n-1}.$
(4)

Then it follows from Proposition 10 that Eq. (4) equals the value
$2^{k}2^{4k(n-1)}$, or equivalently, $2^{k(4n-3)}$.

Let
$S=\\{(\tilde{y}_{1},\dots,\tilde{y}_{n})\in\mathbb{Z}^{n}~{}|~{}2^{k}\tilde{y}_{1}+\cdots+2^{k}\tilde{y}_{n}=0~{}\textrm{mod}~{}2^{q},\tilde{y}_{i}\geq
0\\}$ and $A_{i}=\\{(\tilde{y}_{1},\dots,\tilde{y}_{n})\in
S~{}|~{}\tilde{y}_{i}\geq 2^{q}\\}$ for each $i=1,\dots,n$. Then by the
inclusion-exclusion principle, the number of integer solutions
$\tilde{y}\in\mathbb{Z}_{2^{q}}^{n}$ of the equation
$2^{k}\tilde{y}_{1}+\cdots+2^{k}\tilde{y}_{n}=0$ mod $2^{q}$ is
$|A_{1}^{c}\cap\cdots\cap A_{n}^{c}|$ which can be exactly calculated as

$\displaystyle|S|+\sum_{i=1}^{n}\sum_{I\subseteq[n]}(-1)^{|I|}\left|\bigcap_{j\in
I}A_{j}\right|$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{n-1}\left[\sum_{l=0}^{j}(-1)^{l}\binom{n}{l}\sum_{i=1}^{2^{k}}\binom{n-1+(n-j)2^{4k}-i2^{3k}}{n-1}\right]$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\sum_{i=1}^{2^{k}}\binom{n-1+(n-j)2^{4k}-i2^{3k}}{n-1}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{2^{k}}\sum_{j=0}^{n-1}(-1)^{j}\binom{n-1}{j}\binom{n-1+(n-j)2^{4k}-i2^{3k}}{n-1}.$


# Incorporating Temporal Information in Entailment Graph Mining

Liane Guillou†∗, Sander Bijl De Vroe†∗, Mohammad Javad Hosseini†‡,
Mark Johnson§, and Mark Steedman†
†University of Edinburgh, ‡ The Alan Turing Institute, UK, §Macquarie
University
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We present a novel method for injecting temporality into entailment graphs to
address the problem of spurious entailments, which may arise from similar but
temporally distinct events involving the same pair of entities. We focus on
the sports domain in which the same pairs of teams play on different
occasions, with different outcomes. We present an unsupervised model that aims
to learn entailments such as win/lose $\rightarrow$ play, while avoiding the
pitfall of learning non-entailments such as win $\not\rightarrow$ lose. We
evaluate our model on a manually constructed dataset, showing that
incorporating time intervals and applying a temporal window around them, are
effective strategies.

00footnotetext:  This work is licensed under a Creative Commons Attribution
4.0 International Licence. Licence details:
http://creativecommons.org/licenses/by/4.0/. **footnotetext: The first two
authors contributed equally to this work

##  1 Introduction

Recognising textual entailment and paraphrases is core to many downstream NLP
applications such as question answering and semantic parsing. In the case of
open-domain question answering over unstructured data, the answer to a
question may not be explicitly stated in the text, but may be recovered via
paraphrases and/or entailment rules.

Entailment graphs [Berant et al. (2011, Berant et al. (2015, Hosseini et al.
(2018], in which nodes represent predicates and edges are entailment
relations, have been proposed as a means to answer such questions. They can be
mined using unsupervised methods applied over large collections of text, by
keeping track of which entity pairs occur with which predicates. One common
error made by these graphs, however, is that they assert spurious associations
between similar but temporally distinct events that occur with the same entity
pairs. For example, both the predicates beat and lost against will apply to
sports team entity pairs such as (Arsenal, Man United). This is likely to
mislead the current methods into incorrectly assigning an entailment relation
between these two predicates.

In this paper we extend the framework of ?) to incorporate the temporal
location of events, with the aim of mitigating these spurious entailments.
Temporal information can be used to disentangle these groups of highly
correlated predicates, because although they will share entity pairs, they
will never occur at the same time. For example, in Figure 1 Arsenal and Man
United played each other three times in 2019, with three different outcomes:
win (beat), lose (lost against), tie (tied with).

Arsenal-played and lost against-Man United 1-3 (25/01/2019)
---
Arsenal-played and beat-Man United 2-0 (10/03/2018)
Arsenal-played and tied with-Man United 1-1 (30/09/2019)

Figure 1: Example sentences (left) and their resulting (collapsed)
entailment/non-entailment graph (right)

In previous methods, the context in which the predicates occur appears to be
the same, because they only consider entity pairs as context. Therefore they
mistakenly take the examples in Figure 1 as evidence of entailments or
paraphrases between the three outcome predicates (win, lose, and tie),
depending on the distributions found in the data. Our method enriches this
context to include time interval information, thereby filtering out
combinations that are not temporally near each other. Thus we hope to avoid
learning that beat $\rightarrow$ lost against, while still learning that beat
$\rightarrow$ play.

As an initial test domain, we focus on the sports news genre, using extracted
relations that involve two sports teams. We evaluate on a manually constructed
dataset of 1,312 entailment pairs based on paraphrases of the predicates in
the graph on the right hand side of Figure 1. Our goal is to recover the
structure of this graph in an unsupervised way, separating each of the highly
correlated outcome predicates while predicting that they all entail play.

The contributions of this work are: 1) a model for incorporating relation-
level time intervals into an entailment graph mining procedure, outperforming
non-temporal models, and 2) a manually constructed evaluation dataset of
sports domain predicates. To our knowledge this is the first attempt to
incorporate temporal information for learning entailment graphs.

##  2 Related Work

###  2.1 Entailment Graphs

Entailment graphs have been constructed for a range of domains, including
newswire [Hosseini et al. (2018], health [Levy et al. (2014], and commonsense
[Yu et al. (2020]. In order to leverage temporal information, our work focuses
on the news domain, in which each article has a known publication date and
temporal expressions are commonly used.

A range of node representations have been explored, including Open-IE
propositions [Levy et al. (2014], typed predicates [Berant et al. (2011,
Hosseini et al. (2018], and eventualities [Yu et al. (2020]. In this work we
use typed predicates, leveraging the second level in the FIGER hierarchy [Ling
and Weld (2012], to enable a close examination of events that take place
between two sports teams.

Whether predicates in the graph entail each other may be determined using a
variety of similarity measures. These are inspired by the Distributional
Inclusion Hypothesis, which states that a predicate p entails another
predicate q if for any context in which p can be used, q may be used in its
place [Dagan et al. (1999, Geffet and Dagan (2005]. They include the symmetric
Lin’s similarity measure [Lin (1998], the directional Weeds’ precision and
recall measures [Weeds and Weir (2003], and the Balanced Inclusion score
(BInc) [Szpektor and Dagan (2008]. BInc, the geometric mean of Lin’s
similarity and Weed’s precision, combines the desirable behaviors of symmetric
and directional measures. We adapt and examine each of these similarity
measures using our evaluation dataset.

Alternatively, ?) performed link prediction on the set of relation triples
extracted from the text, and showed improvements over BInc by augmenting the
data with additional predicted triples. We consider this link prediction model
to be beyond the scope of this work.

###  2.2 Evaluating Entailment Graphs

The construction of entailment datasets has been framed as a number of manual
annotation tasks including image captioning [Bowman et al. (2015] and question
answering [Levy and Dagan (2016].

The dataset creation method used by ?) aims to address the bias towards real
world knowledge. They ask human annotators to mark possible answers to
questions as True/False (entailment/non-entailment), with entities in the
answer replaced using tokens representing their type (e.g. London becomes
city). The method also aims to address the bias of other datasets such as
Zeichner’s dataset [Zeichner et al. (2012] and the SherLIic dataset [Schmitt
and Schütze (2019], in which candidate entailments were automatically pre-
selected for manual annotation according to a similarity measure. Entailments
that exist, but are not captured by these similarity measures will therefore
be excluded.

There has been very little work on the specific problem of evaluating
entailment of a temporal nature. The FraCas test suite [Cooper et al. (1996]
contains a small section of which only a few examples are entailments between
predicates. The TEA dataset [Kober et al. (2019] consists of pairs of
sentences in which temporally ordered predicates have varying tense and
aspect, such as is visiting $\rightarrow$ has arrived, but does not include
non-entailments that can be learned through the temporal separation of events
(such as the outcome predicates win and lose that we are interested in). Since
there is no dataset to evaluate this phenomenon, we construct our own (Section
4.1). Our method for dataset construction is similar to that of ?). They
manually annotated all edges in 10 typed entailment graphs, resulting in 3,427
edges (entailments) and 35,585 non-edges (non-entailments).

##  3 Method

###  3.1 Relation Extraction

We use a pipeline based on a Combinatory Categorial Grammar (CCG, [Steedman
(2000]) parser to extract binary relations with time intervals. These
relations are used to construct typed entailment graphs using the unsupervised
method of ?), adapted to compare only pairs of relations that are temporally
near each other. We extract binary relations of the form arg1-predicate-arg2
(e.g. Arsenal-beat-Man United), following the example of ?) and ?). We use a
pipeline approach similar to that described by ?), which allows us to extract
open-domain relations. Relations are extracted from the NewsSpike corpus
[Zhang and Weld (2013] of news articles collected from multiple sources over a
period of approximately six weeks.

We traverse dependency graphs generated over the output of the Rotating CCG
parser [Stanojević and Steedman (2019], starting from verb and preposition
nodes, until we reach an argument leaf node. The traversed nodes are used to
form (lemmatised) predicate strings, and arguments are classified as either a
Named Entity (extracted by the CoreNLP Named Entity recogniser), or a general
entity (all other nouns and noun phrases). Predicate strings may include (non-
auxiliary) verbs, verb particles, adjectives, and prepositions. Negation nodes
are detected via string match (“not”, “n’t”, and “never”), and are included in
the predicate if there is a path between the negation node and a node in the
predicate. We map passive predicates to active ones. Modifiers such as
“managed to” as in the example “Arsenal managed to beat Man United” are also
extracted and included in the predicate. As the modifiers may be rather
sparse, we extract the relation both with and without the modifier.

We extract and resolve time expressions in the document text, using SUTime
[Chang and Manning (2012], available via CoreNLP. If there is a path in the
CCG dependency graph between the time expression and a node in the predicate,
the relation is assigned a time interval. Entities are mapped to types by
linking to their Freebase [Bollacker et al. (2008] IDs using AIDA-Light
[Nguyen et al. (2014], and subsequently mapping these IDs to their fine-
grained FIGER types [Ling and Weld (2012].

To restrict the data to the sports domain we filter the set of output
relations, accepting only those involving two entities of the fine-grained
FIGER type organization/sports_team. This results in a set of 78,439 binary
relations extracted from 24,147 articles, of which 14,664 (approximately 19%)
have time intervals derived from SUTime. The sports domain has the advantage
that events are similar and should be easily separable in time, and it
provides the straightforward win-lose-tie outcome set. Sports data is common
in NewsSpike, and sports teams have reliable Named Entity linking, making it
suitable for an initial investigation. In the future we will apply this method
to other entity type pairs.

###  3.2 Graph Construction

The input to the graph construction step is the set of typed binary relations
paired with their time intervals. As we focus on events that involve two
sports teams, the output is a single organization-organization graph, rather
than the typical set of graphs (one for every pair of types). Note that these
graphs contain only locally learned entailments, and that global inference
across graphs is not performed. This is sufficient to demonstrate the benefit
of incorporating time intervals.

In the original method for computing local entailment scores, ?) extract a
feature vector for each typed predicate (e.g. play with type pair
organization-organization). The entity pairs from the binary relations (e.g.
Arsenal, Man United) are used as the feature types, and the pointwise mutual
information (PMI) between the predicate and the entity pair is the value.
These feature vectors are then used to compute local similarity scores.

We extend this method to consider the time intervals for each of the binary
relations, with the goal of comparing only those events that are temporally
near each other. To achieve this, we filter the counts of predicate q
according to whether each event’s time interval overlaps with any of p’s. In
other words, an event in q is retained if it is close enough to any event in
p. We consider new local similarity scores based on both the filtered counts,
and scaled PMI scores.

Algorithm 1 describes the process of filtering counts using time intervals.
The process uses a set of edges $\mathcal{E}$ between predicate nodes to store
filtered count information. We loop through each entity pair ep and get the
list of predicates that occur with that entity pair (line 4). Then, for each
pair of predicates, we instantiate edgeObjects (line 7) between predicates p
and q (in both directions), to store the filtered count information. We also
retrieve p and q’s timeObjects, containing a list of the time intervals at
which the predicate and entity pair co-occurred (lines 8–9). For each pair of
time intervals we compute whether there is an overlap (lines 12–19). The
filtered count is the total number of events in predicate p that temporally
overlap with any event in predicate q.

The count is stored in the edgeObject $edge_{p,q}$. Once all counts have been
collected, they are used to compute the similarity measures. The computation
of temporal measures is identical to that of the non-temporal counterparts,
but they use the filtered counts as input instead of the regular counts. Each
edgeObject populates a cell in $\mathbf{W}$, the sparse matrix of all
similarity scores between predicates p and q, as presented by ?). The filtered
counts are also used to scale the PMI scores (see section 4.2).

Consider the following minimal worked example: Two matches between Arsenal and
Man United, one where Arsenal wins (on 10/03/2018), and one where they lose
(on 25/01/2019). This initially results in the following extracted predicates
and counts: play (2), win (1), lose (1). After filtering, we add a count of 1
to both the win $\rightarrow$ play and lose $\rightarrow$ play edges, and a
count of 0 to the win $\rightarrow$ lose edge (and its reverse).

We consider three possible sources of time intervals: 1) the resolved time
expressions extracted from raw text using SUTime, 2) the document creation
date (provided as metadata in the NewsSpike corpus), and 3) a combination of
the two – using resolved time expressions where these are available, and
backing off to the document creation date where they are not. The intuition
behind using time expressions extracted from the article text is that these
ought to more accurately pinpoint the time interval of the events. However, as
such expressions may be sparse, we also investigate the use of the document
creation date, under the assumption that sports news is likely to be reported
very close the day of the event.

We also consider a temporal window to extend the time intervals by N days
either side. This would mitigate the problem of sports events being reported
several days after the event, especially when we fall back to the document
creation date. For sports matches we would expect to see a benefit in using a
small window of a few days, and a detrimental effect as that window grows
increasingly larger. Specifically, we expect that larger windows would render
temporal information useless, preventing our model from being able to
distinguish between two different matches involving the same pair of teams.
Time interval source and window size are event-specific parameters that we
experiment with in Section 5.1.

Algorithm 1 Temporal filtering in local graph computation

1:procedure TemporalFilter($entity\\_pairs,predicates$)

2: $\mathcal{E}\leftarrow initialiseAllEdgeObjects(predicates)$
$\triangleright$ Initialise set of edges

3: for ep in entity_pairs do

4: $predicates_{ep}\leftarrow getPredicatesForEntityPair(predicates,ep)$

5: for $p\leftarrow 0$ to $length(predicates_{ep})$ do

6: for $q\leftarrow p+1$ to $length(predicates_{ep})$ do

7: $edge_{p,q},edge_{q,p}\leftarrow getEdgeObjects(\mathcal{E},p,q)$

8: $time\\_objects_{ep,p}\leftarrow getTimeObjects(ep,p)$

9: $time\\_objects_{ep,q}\leftarrow getTimeObjects(ep,q)$

10: $overlap_{p}\leftarrow
initialiseVectorOfZeros(length(time\\_objects_{ep,p}))$

11: $overlap_{q}\leftarrow
initialiseVectorOfZeros(length(time\\_objects_{ep,q}))$

12: for $i\leftarrow 0$ to $length(time\\_objects_{ep,p})$ do

13: for $j\leftarrow 0$ to $length(time\\_objects_{ep,q})$ do

14: if $compareIntervals(time\\_objects_{ep,p}[i],time\\_objects_{ep,q}[j])=1$
then

15: $overlap_{p}.set(i,1)$

16: $overlap_{q}.set(j,1)$

17: end if

18: end for

19: end for

20: $edge_{p,q}.addEdgeCounts(sum(overlap_{p}))$$\triangleright$ Events in p
that temporally overlap with any q

21: $edge_{q,p}.addEdgeCounts(sum(overlap_{q}))$

22: end for

23: $\mathcal{E}.update(edge_{p,q},edge_{q,p})$

24: end for

25: end for

26: return $\mathcal{E}$

27:end procedure

##  4 Evaluation

###  4.1 Dataset Construction

We propose a semi-automatic method to construct a small evaluation dataset
based on manually constructed paraphrase clusters. We start with a small set
of predicates for which we know the entailment pattern, in our case
$\\{win,play,lose$ and $tie\\}$. We restrict the dataset to include only those
binary relations that involve two sports teams, by filtering on the fine-
grained FIGER [Ling and Weld (2012] type organization/sports_team. We then
order the predicates by their frequency in the corpus, and manually select
paraphrases of our small set with a count of at least 20 (the 235 most
frequent predicates). This results in four clusters of paraphrases, with sizes
of 26, 8, 3 and 5 respectively for win, lose, tie and play. We then
automatically generate entailment pairs (1,312 in total), labelling them
according to the pattern in Table 1, with premises in the rows and hypotheses
in the columns.

We include the paraphrase category for completeness, although we are more
interested in the effect of separating temporally disjoint sports match
outcomes. The paraphrase category contains predicates of varying gradation,
such as crush suggesting a strong victory or eliminate indicating that a team
is knocked out of a tournament. We wish to avoid specific predicates such as
eliminate entailing non-specific predicates like beat. To avoid this issue we
manually annotated the predicates for specificity, and for the paraphrase
entailments subset we only generate pairs for non-specific predicates. More
generally, a set of paraphrase clusters with a total of $n$ predicates yields
$n^{2}-n$ pairs (not taking into account the paraphrase subsets
reduction).111The subtracted term comes from duplicate pairs like defeat-
defeat The dataset of 1,312 entailment pairs is available  here.

(a) 1 = entailment, 0 = non-entailment. Blue = base (entailments, and non-entailments from temporally disjoint outcomes), orange = directional non-entailment, green = paraphrases | win | lose | tie | play
---|---|---|---|---
win | 1 | 0 | 0 | 1
lose | 0 | 1 | 0 | 1
tie | 0 | 0 | 1 | 1
play | 0 | 0 | 0 | 1

(b) Examples from the evaluation dataset Category | Examples | Size
---|---|---
|  defeat $\rightarrow$ vs |
entailment 1 |  crush $\rightarrow$ face | 272
|  beat $\rightarrow$ fall to |
outcome 0 |  outscore $\rightarrow$ lose | 446
|  play $\rightarrow$ win |
directional 0 |  go against $\rightarrow$ tie | 272
|  top $\rightarrow$ knock off |
paraphrase 1 |  defeat $\rightarrow$ outplay | 322

Table 1: Entailment pairs evaluation dataset

###  4.2 Similarity Measures

We compute both symmetric and directional similarity measures to learn
entailments, making use of the temporally filtered counts and PMI scores
described in Section 3.2. Specifically, we adapted Lin’s similarity measure
[Lin (1998], Weeds’ precision and recall measures [Weeds and Weir (2003], and
BInc [Szpektor and Dagan (2008]. The adaptations of these measures are:

Temporal count-based measures using the temporally filtered counts: Weeds’
precision, recall, and similarity (harmonic average of precision and recall);
Lin’s similarity; BInc using Weed’s precision and count-based Lin’s
similarity.

Temporal PMI-based measures: As a proxy to computing Conditional PMI between
an entity pair, predicate p, and predicate q, which would be computationally
expensive (if not infeasible) given the existing graph construction framework,
we scale the original PMI scores. We apply two strategies: 1) Ratio: scale the
original PMI scores according to the ratio of filtered counts to regular
counts, 2) Binary: use the original PMI score if any of the events in
predicate p overlap with any event in predicate q, otherwise set the score to
zero. The following measures use the Ratio and Binary PMI strategies: Weeds’
precision, recall, and similarity; Lin’s similarity; BInc using Weed’s PMI
precision and Lin’s similarity.

Temporal hybrid BInc measures: Computed using count-based Weeds’ precision and
PMI-based Lin’s similarity, using the temporally filtered counts. We do this
for both Ratio and Binary PMI.

We also ensure that for every temporal measure, its non-temporal counterpart
is also included, and we include cosine similarity as a symmetric baseline. In
total, we experiment with 29 similarity measures.

##  5 Experiments, Results and Analysis

###  5.1 Experimental Settings

As described in Section 3.1 we extract all possible relations from the
NewsSpike corpus and map their entities to types using the FIGER hierarchy. We
construct a typed entailment graph for the organization/organization type pair
using the subset of these relations where both entities are sports teams. We
compute entailment scores using the set of 29 similarity measures described in
Section 4.2. Due to space constraints we highlight results for eight of these
measures: BInc and cosine similarity baselines, and the best performing
temporal measures and their non-temporal counterparts.

We experimented with different values for the event-specific time information
source and temporal window described in Section 3.2. We constructed typed
entailment graphs using only time expressions (timexOnly), only the document
creation date (docDateOnly), and using time expressions where available,
otherwise backing off to the document creation date (timexAndDocDate). For
each of the time interval sources, we also applied windows of 1, 2, 3, 4, 5,
6, 7, 30 and 3,650 days, as well as no window.

We used the evaluation dataset described in Section 4.1 and Table 1 to
evaluate entailments captured under each of these experimental settings. We
evaluate on three different configurations of the dataset: Base (entailment 1
and outcome 0), Directional (entailment 1 and directional 0), and All
(entailment 1, outcome 0, directional 0, paraphrase 1). When we introduce
parameter tuning in future work, we plan to assign a development/test split to
the dataset.

###  5.2 Temporal Information Source

See Table 2 for area under the curve (AUC) scores for each of the three
temporal information sources, for a range of temporal (T) and non-temporal
similarity measures. To evaluate the similarity measures fairly we calculate
AUC under a recall threshold (a recall of 0.75 is reached by all non-timexOnly
measures). The timexOnly source has the weakest performance, since it has
access to a sparser set of time intervals (with only 19% of relations linked
to a time expression in the text). When we focus on the low recall range ($<$
0.15), however, we find that the temporal measures outperform the non-temporal
ones. This is especially promising as it highlights the benefit of using the
more accurate time intervals resolved from time expressions in the text; these
give temporal measures a larger increase than the document date. When using
only the document creation date (docDateOnly), we find that temporal and non
temporal measures perform similarly. Results for the timexAndDocDate source
show that leveraging both time expression and document time information
together leads to the most effective model.

Similarity measure | timexOnly | docDateOnly | timexAndDocDate
---|---|---|---
|  rec $<$ 0.15 |  rec $<$ 0.75 |  rec $<$ 0.75 |  rec $<$ 0.75
T. BInc (Count) | 0.111 | 0.127 | 0.467 | 0.469
BInc (Count) | 0.106 | 0.467 | 0.467 | 0.467
T. BInc (Ratio PMI) | 0.108 | 0.108 | 0.446 | 0.449
T. BInc (Binary PMI) | 0.114 | 0.114 | 0.446 | 0.448
BInc | 0.093 | 0.444 | 0.444 | 0.444
T. Weed’s Pr (Count) | 0.113 | 0.129 | 0.436 | 0.436
Weed’s Pr (Count) | 0.087 | 0.436 | 0.436 | 0.436
Cosine Sim | 0.100 | 0.420 | 0.420 | 0.420
Table 2: Temporal information source: AUC scores for the base evaluation
dataset, and a temporal window size of 4 days

###  5.3 Temporal Window Size

In Figure 2 we can see that there is a sharp improvement in AUC score for all
of the temporally-informed similarity measures when a window of one day is
applied222With no window, the temporally informed similarity measures perform
poorly (between 0.24 and 0.26). This is likely due to data sparsity and
because sports articles report on the same event on different days. The
horizontal lines represent the non-temporally-informed similarity measures. We
can also see that the choice of window size depends on the similarity measure.
For the majority of the temporally-informed similarity measures, a window size
between one and four days works well. For this class of predicates a window
size of 4 seems suitable, as it avoids conflating games that happen on
consecutive weekends, while giving some leeway. We discuss the possibility of
using a dynamic window in Section 6.

Figure 2: Effects of window size for the timexAndDocDate temporal information
source

###  5.4 Comparing Similarity Measures

We can see from Figure 3 that BInc, a state-of-the-art measure for relation
entailment, does not perform well within the temporal setting and is
outperformed by a number of the temporal measures. Of those, T. BInc count
sims, the version of BInc that uses the temporally filtered counts, produces
the best results on the base subset of the evaluation dataset. The two
temporally informed measures that use scaled PMI scores (T. Ratio BInc sims
and T. Binary BInc sims) also outperform BInc but to a lesser degree. This may
be due to sparsity in the set of binary relations making it difficult to
estimate accurate scaled PMI scores. We hope to alleviate this problem by
moving to a larger corpus in future work333We have already compiled a dataset
of 10 years worth of news data from multiple sources. In more general terms,
for each similarity measure, the temporal version performs better (with the
exception of Weed’s probabilistic precision, for which there is no change).

###  5.5 Performance on Data Subsets

Our main interest is in performance on the base dataset, but for completeness
and comparison to previous work, which tests directionality more, we also
evaluated on the all and directional subsets (see Table 3).

To investigate the challenge of directionality in entailment we consider the
set of entailments and their reverse, e.g. play $\rightarrow$ win (“entailment
1” and “directional 0” in Table 1(b)). We find that in general the temporal
similarity measures still perform strongly. T. Weeds’ precision, the only
purely directional measure in the set, performs comparably to its non-temporal
counterpart on the directional subset. The second best measure is BInc which
is unsurprising given that it also captures directionality, and that the
dataset no longer tests temporality.

We also evaluate on the complete dataset (all) which includes paraphrases
(“paraphrase 1” in Table 1(b)). Here we find that T. Weeds’ precision is again
the best measure, closely followed by the PMI-based T. BInc scores (Binary and
Ratio). We expect that the strong performance of T. Weeds’ precision is due to
correctly identifying the directional entailments in the dataset, and that the
drop in performance between the directional and all subsets is due to the
inclusion of paraphrases, which are challenging for all measures, but
particularly for the Weed’s precision measures which have no symmetric
component. BInc also performs reasonably well on this subset, showing that
temporally-uninformed measures remain competitive when multiple phenomena are
tested. In general we find that at least one temporally-informed similarity
measure still performs strongly for each of the subsets in the dataset.

Figure 3: Best results on the base evaluation dataset: timexAndDocDate with a temporal window size of 4 days. For calculating AUC the recall threshold is set to $<$ 0.75 for all similarity measures Similarity measure | Base | Dir | All
---|---|---|---
T. BInc (Count) | 0.469 | 0.433 | 0.433
BInc (Count) | 0.467 | 0.433 | 0.434
T. BInc (Ratio PMI) | 0.449 | 0.449 | 0.442
T. BInc (Binary PMI) | 0.448 | 0.449 | 0.442
BInc | 0.444 | 0.447 | 0.442
T. Weed’s Pr (Count) | 0.436 | 0.491 | 0.448
Weed’s Pr (Count) | 0.436 | 0.492 | 0.447
Cosine Sim | 0.420 | 0.372 | 0.397
Table 3: AUC scores for different subsets of the evaluation dataset. Temporal
information source is timexAndDocDate, temporal window size is 4 days

###  5.6 Effects of Using Temporal Information

To see the benefits of including temporal information, we compare the AUC
scores for the temporal and non-temporal similarity measures. We use the
timexAndDocDate temporal information source, and a window size of four days
(see Figure 3). The organization-organization graph has 46,899 nodes and
between 7,888,372 and 8,256,182 edges depending on the similarity measure. We
can see that the temporal similarity measure T. BInc count outperforms BInc,
the state-of-the-art non-temporal similarity measure for relation entailment
employed by ?) and ?). We conclude that incorporating temporal information is
beneficial for accurately predicting entailments and non-entailments for
highly correlated predicates that are part of distinct events.

##  6 Discussion and Future Work

The NewsSpike corpus covers a period of approximately six weeks so the
outcomes of two matches between two teams within this period may be fairly
similar (as there will have been few changes to the teams management, players,
etc.). In future work we plan to move to a corpus covering a larger time
period, for which we would expect to observe a greater effect. Expanding
beyond the sports team domain would also allow us to study events with longer
duration, such as a president holding office, preceded by their campaign, and
election.

Expanding the domain will also give us a collection of local graphs of types
beyond just organization-organization, across which we can then learn globally
consistent similarity scores (as in ?)). We can then also collapse cliques in
the graph into paraphrase clusters with a single relation identifier, which we
hope will improve performance, especially on sparser predicates. Our dataset
is perfectly suited to evaluating benefits from this addition due to its
origin in paraphrase clusters.

Whilst we can observe a positive effect when using temporal information, the
effect is modest. Upon closer inspection we found that this was due to
relatively few events being filtered. An analysis of a subset of sentences
revealed that relations were being extracted spuriously due to various
linguistic phenomena. Issues are caused by conditionals (e.g. “if Arsenal
win”), modals (“I still expect Arsenal…”), incorrect future predictions
(“Arsenal will win”) and counterfactuals (“had Arsenal won,…”). These types of
predictions appear to be especially common in the sports domain. Another issue
arose due to an incorrect application of passive to active conversion
(Arsenal-lost to-Man United from “Man United lost to Arsenal”) resulting from
incorrect verb feature labels in the CCG parses. Finally, SUTime sometimes
provides partial time information which can result in a whole year being used
as an interval, creating spurious overlaps444Focusing only on short time
intervals failed to offset the other sources of spurious overlaps. Addressing
these issues should lead to a larger effect from using temporal information,
because it would reduce overlaps and allow more filtering.

Our algorithm lends itself naturally to mining entailments with a temporal
relation such as visit $\rightarrow$ arrived. We plan to achieve this by
splitting the window into a before and after frame, producing separate
entailment scores for different orderings. We also plan to investigate setting
the window dynamically. In the current setup, events stay relevant for a
similar amount of time, but different predicates should allow comparison for
different granularities of time. For example, the window around a person being
president should be larger than a person visiting a location. Initially we
might aim to learn a different window size per predicate (for example by
taking into account average predicate duration and granularity). Dynamic
windowing could become particularly valuable with a broader domain.

More generally, our method could incorporate in its filtering any function of
the contextualised events to determine whether their co-occurrence should
contribute to an entailment score. Currently a binary decision is made based
on time interval overlap, but one might use features such as (lexical) aspect,
tense, the presence of other entities, etc. Previous work was limited to using
the presence of two entities as a proxy for entailment relevance; with our
refinements we could expand to involving not only time but also other features
of the contextualised events.

We will also explore the use of other temporal resolution systems and aim to
develop more sophisticated ways of linking times to events, which currently
only occurs through CCG dependencies. More time intervals might be propagated
using the TempEval [UzZaman et al. (2013] ordering approach or through other
means, for instance by reasoning about tense, Reichenbachian reference time
[Reichenbach (1947], or event coreference (within, or across documents).

##  7 Conclusions

We injected temporal information into the local entailment graph construction
method of ?), with the goal of comparing only those events that are temporally
near each other. This is achieved by filtering the counts of predicate p
according to whether its events’ time intervals overlap with the those of
predicate q. We considered a range of new local similarity scores based on
both temporally filtered counts and scaled PMI scores, which we evaluate on a
semi-automatically constructed dataset, based on manually constructed
paraphrase clusters.

Our temporal similarity measures outperform their non-temporal counterparts,
including BInc, the state-of-the-art measure for relation entailment. We also
show that using a combination of time expressions recovered from the text and
the document creation date performed better than using only one of these
sources, and that adding a temporal window around the time intervals of the
events is essential. The performance of the temporal similarity measures over
the non-temporal measures is particularly strong at the low recall range when
only time expressions from the text are used. This is especially promising as
it suggests that there is much room for improvement in using more
sophisticated temporal resolution systems and methods for linking times to
events.

## Acknowledgements

We thank Miloš Stanojević for assistance with the Rotating CCG parser, Nick
McKenna and Ian Wood for helpful discussions, and the reviewers for their
valuable feedback. This work was funded by the ERC H2020 Advanced Fellowship
GA 742137 SEMANTAX, a grant from The University of Edinburgh and Huawei
Technologies, and The Alan Turing Institute under EPSRC grant EP/N510129/1.

## References

  * [Berant et al. (2011]  Jonathan Berant, Ido Dagan, and Jacob Goldberger.  2011\.  Global learning of typed entailment rules.  In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 610–619, Portland, Oregon, USA, June. Association for Computational Linguistics.
  * [Berant et al. (2015]  Jonathan Berant, Noga Alon, Ido Dagan, and Jacob Goldberger.  2015\.  Efficient global learning of entailment graphs.  Computational Linguistics, 41(2):221–263, June.
  * [Bollacker et al. (2008]  Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor.  2008\.  Freebase: A collaboratively created graph database for structuring human knowledge.  In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD ’08, page 1247–1250, New York, NY, USA. Association for Computing Machinery.
  * [Bowman et al. (2015]  Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning.  2015\.  A large annotated corpus for learning natural language inference.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 632–642, Lisbon, Portugal. Association for Computational Linguistics.
  * [Chang and Manning (2012]  Angel X. Chang and Christopher Manning.  2012\.  SUTime: A library for recognizing and normalizing time expressions.  In Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC’12), pages 3735–3740, Istanbul, Turkey, May. European Language Resources Association (ELRA).
  * [Cooper et al. (1996]  Robin Cooper, Dick Crouch, Jan Van Eijck, Chris Fox, Josef Van Genabith, Jan Jaspars, Hans Kamp, David Milward, Manfred Pinkal, Massimo Poesio, Steve Pulman, Ted Briscoe, Holger Maier, and Karsten Konrad.  1996\.  Using the framework.
  * [Dagan et al. (1999]  Ido Dagan, Lillian Lee, and Fernando C. N. Pereira.  1999\.  Similarity-based models of word cooccurrence probabilities.  Machine Learning, 34:43–69.
  * [Geffet and Dagan (2005]  Maayan Geffet and Ido Dagan.  2005\.  The distributional inclusion hypotheses and lexical entailment.  In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 107–114, Ann Arbor, Michigan, June. Association for Computational Linguistics.
  * [Hosseini et al. (2018]  Mohammad Javad Hosseini, Nathanael Chambers, Siva Reddy, Xavier R. Holt, Shay B. Cohen, Mark Johnson, and Mark Steedman.  2018\.  Learning typed entailment graphs with global soft constraints.  Transactions of the Association for Computational Linguistics, 6:703–717.
  * [Hosseini et al. (2019]  Mohammad Javad Hosseini, Shay B. Cohen, Mark Johnson, and Mark Steedman.  2019\.  Duality of link prediction and entailment graph induction.  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4736–4746, Florence, Italy, July. Association for Computational Linguistics.
  * [Kober et al. (2019]  Thomas Kober, Sander Bijl de Vroe, and Mark Steedman.  2019\.  Temporal and aspectual entailment.  In Proceedings of the 13th International Conference on Computational Semantics - Long Papers, pages 103–119, Gothenburg, Sweden, May. Association for Computational Linguistics.
  * [Levy and Dagan (2016]  Omer Levy and Ido Dagan.  2016\.  Annotating relation inference in context via question answering.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 249–255, Berlin, Germany, August. Association for Computational Linguistics.
  * [Levy et al. (2014]  Omer Levy, Ido Dagan, and Jacob Goldberger.  2014\.  Focused entailment graphs for open IE propositions.  In Proceedings of the Eighteenth Conference on Computational Natural Language Learning, pages 87–97, Ann Arbor, Michigan, June. Association for Computational Linguistics.
  * [Lewis and Steedman (2013]  Mike Lewis and Mark Steedman.  2013\.  Combined distributional and logical semantics.  Transactions of the Association for Computational Linguistics, 1:179–192.
  * [Lin (1998]  Dekang Lin.  1998\.  An information-theoretic definition of similarity.  In Proceedings of the Fifteenth International Conference on Machine Learning, ICML ’98, page 296–304, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
  * [Ling and Weld (2012]  Xiao Ling and Daniel S. Weld.  2012\.  Fine-grained entity recognition.  In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI’12, page 94–100. AAAI Press.
  * [Nguyen et al. (2014]  Dat Ba Nguyen, Johannes Hoffart, Martin Theobald, and Gerhard Weikum.  2014\.  Aida-light: High-throughput named-entity disambiguation.  Workshop on Linked Data on the Web, 1184:1–10.
  * [Reichenbach (1947]  Hans Reichenbach.  1947\.  The tenses of verbs.  Time: From Concept to Narrative Construct: a Reader.
  * [Schmitt and Schütze (2019]  Martin Schmitt and Hinrich Schütze.  2019\.  SherLIiC: A typed event-focused lexical inference benchmark for evaluating natural language inference.  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 902–914, Florence, Italy, July. Association for Computational Linguistics.
  * [Stanojević and Steedman (2019]  Miloš Stanojević and Mark Steedman.  2019\.  CCG parsing algorithm with incremental tree rotation.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 228–239, Minneapolis, Minnesota, June. Association for Computational Linguistics.
  * [Steedman (2000]  Mark Steedman.  2000\.  The Syntactic Process.  MIT Press, Cambridge, MA, USA.
  * [Szpektor and Dagan (2008]  Idan Szpektor and Ido Dagan.  2008\.  Learning entailment rules for unary templates.  In Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 849–856, Manchester, UK, August. Coling 2008 Organizing Committee.
  * [UzZaman et al. (2013]  Naushad UzZaman, Hector Llorens, Leon Derczynski, James Allen, Marc Verhagen, and James Pustejovsky.  2013\.  Semeval-2013 task 1: Tempeval-3: Evaluating time expressions, events, and temporal relations.  In Second Joint Conference on Lexical and Computational Semantics (* SEM), Volume 2: Proceedings of the Seventh International Workshop on Semantic Evaluation (SemEval 2013), volume 2, pages 1–9.
  * [Weeds and Weir (2003]  Julie Weeds and David Weir.  2003\.  A general framework for distributional similarity.  In Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing, pages 81–88.
  * [Yu et al. (2020]  Changlong Yu, Hongming Zhang, Yangqiu Song, Wilfred Ng, and Lifeng Shang.  2020\.  Enriching large-scale eventuality knowledge graph with entailment relations.  In Automated Knowledge Base Construction.
  * [Zeichner et al. (2012]  Naomi Zeichner, Jonathan Berant, and Ido Dagan.  2012\.  Crowdsourcing inference-rule evaluation.  In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 156–160, Jeju Island, Korea, July. Association for Computational Linguistics.
  * [Zhang and Weld (2013]  Congle Zhang and Daniel S Weld.  2013\.  Harvesting parallel news streams to generate paraphrases of event relations.  In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1776–1786.