# Factoring numbers with elliptic curves

Jorge Jiménez Urroz  Departamento de Matemáticas
Universidad Politécnica de Madrid
Madrid, Spain<EMAIL_ADDRESS> and  Jacek Pomykała  Institute of
Mathematics, Faculty of Mathematics, Informatics and Mechanics
University of Warsaw
Poland<EMAIL_ADDRESS>
###### Abstract.

In the present paper we provide a probabilistic polynomial time algorithm that
reduces the complete factorization of any squarefree integer $n$ to counting
points on elliptic curves modulo $n$, succeeding with probability
$1-\varepsilon$, for any $\varepsilon>0$.

###### Key words and phrases:

Integer actorization, Elliptic curves, 11A51, 11G07

##  1\. introduction

The importance of factorization is something already we all agree. Since the
creation of RSA cryptosystem, and its strong consequences in society, not only
mathematicians, but even the public community follow the updates in the
problem with great enthusiasm. The security of our systems depend heavily in
the difficulty of finding the factors of certain known integer $n$.

Despite the efforts of the best mathematicians in the area, the fastest
algorithms for factoring, the general number field sieve, suceeds in finding
the factors only in subexponential time which, in particular, makes nowadays
extremely hard to factor numbers of $1024$ digits. It would need more than $1$
year of continuos working of $1,5$ million computers with $2.1$Ghz of speed.
And still, given the delicacy of the matter, the NIST recommends keys of
$2048$ bits at least since $2015$.

One way of dealing with the factorization is to find problems with equivalent
difficulty, i.e. mathematical problems which solutions would give a polynomial
time algorithm to factor integer numbers. The first of these instances is due
to Miller [10], who proved under GRH that factoring an integer $n$ is
equivalent to compute the Euler function $\varphi(n)$.

Since then, there have been many attempts to find equivalent problems. Bach,
et all in [3] relate factorization of an integer $n$ with the problem of
counting the sum of the divisors of $n$, in [2] consider the computation of
cyclotomic polynomials, and in [1] provides a probabilistic polynomial time
algorithm to reduce factorization to the discrete logarithm problem on
composite integers $n$. It is worth to note that in all these problems,
isolating certain multiple of $(p-1)$ is of interest, for some $p|n$.

In $1987$ the strategy changes with the introduction of elliptic curves into
the problem with the extraordinary paper by Lenstra [8], in which he produces
an algorithm to factor the integer $n$ by using the number of points of an
elliptic curve modulo $n$. Since then, many articles relate elliptic curves
with factorization. In [7] the authors prove that counting points on elliptic
curves modulo $n$ is randomly computationally equivalent to factoring $n$,
assuming somehow uniform distribution of the order of points of random
elliptic curves over the Hasse interval. In [9] the authors relate the problem
of factoring with computing the order of points on elliptic curves modulo $n$
and give a random polynomial time reduction between both problems, while [11]
provides an algorithm reducing in polynomial time factorization to the
computation of the exponent of the group of points $E(\mathbb{Z}/n\mathbb{Z})$
for elliptic curves modulo $n$.

In [4] the authors prove a deterministic algorithm to reduce the factorization
of any RSA modulus, $n$, to counting affine points on elliptic curves modulo
$n$. For general squarefree the authors of [5], among other things, give an
algorithm reducing the factorization of $n$ to counting points on elliptic
curves modulo $n$, valid for $n$ outside an exceptional set depending on the
number of prime factors of $n$. For the particular case of RSA modulus this
set is of size $o(x\log\log x/\log x)$. The argument is based on the idea of
finding traces of elliptic curves coprime to $p+1$ for some prime factor
$p|n$. However, to exploit the idea, they also need to assume uniform
distribution of the traces of elliptic curves, in a particular way as $p$
varies.

The goal of this paper is to give a probabilistic polynomial time algorithm
succesfull with probability $1-\varepsilon$ for any $\varepsilon>0$, valid for
all squarefree integers $n$ with no exception. Concretely we prove the
following result.

######  Theorem 1.

Let $n$ be a squarefree integer. Then, assuming GRH, counting the number of
points on elliptic curves modulo $n$ allows to find the complete factorization
of $n$ with probability bigger than $1-\varepsilon$ for any $\varepsilon>0$.

The argument also uses the idea of counting traces coprime to $p+1$ where
$p|n$, but instead we do not need to assume extra hypothesis on the traces.
Instead, our argument uses the unconditional bounds of Lenstra for the
distribution of the number of points as $E$ varies randomly over all elliptic
curves over $\mathbb{F}_{p}$. To do so, Lenstra uses the class number formula,
and the bounds for the special value $L(1,\chi)$ where $\chi$ is the quadratic
character associated to the Frobenius field when varying the curve. In this
sense one is tempted to assume that no Siegel zero exists, but this only would
save a logarithm with no effect in the result. On the other hand, we do need
to assume the general Riemann Hypothesis, GRH, to bound the size of the least
non square residue modulo $p$.

##  2\. Lemmata

We want to factorize $n=p_{1}\dots p_{r}$ an squarefree integer. As usual, for
$E/\mathbb{Z}$ we let $E_{n}=\prod_{p|n}E_{p}$, where $E_{p}$ is the reduction
of $E$ modulo $p$. Clearly we can give to $E_{n}$ group structure isomorphic
to $\prod_{p|n}E_{p}$ as groups. We denote $|E_{n}|$ the number of points of
the elliptic curve modulo $n$. Now, for any $(d,n)=1$ consider $E_{n}^{d}$ the
quadratic twist of $E_{n}$ and let $|E_{n}^{d}|$ its number of points modulo
$n$. Then,

$|E_{n}|=\prod_{p|n}(p+1-a_{p}),\quad|E_{n}^{d}|=\prod_{p|n}\left(p+1-\left(\frac{d}{p}\right)a_{p}\right),$

where $\left(\frac{d}{p}\right)$ is the Legendre symbol, and $a_{p}$ is the
trace of the Frobenius endomorphism $\varphi_{p}:E_{p}\to E_{p}$ which
verifies $|a_{p}|\leq 2\sqrt{p}$ by Hasse’s Theorem [6]. We will denote
$I_{p}=[p+1-2\sqrt{p},p+1+2\sqrt{p}]$ the Hasse’s interval. For the proof of
the theorem we need the following lemmata.

######  Lemma 2.

Let $m$ be an integer and $p$ a prime $p\nmid m$. Assuming GRH, there exist
$d\ll(\log mp)^{2}$ such that $\left(\frac{d}{p}\right)=-1$ and
$\left(\frac{d}{m}\right)=1$.

###### Proof.

This is just a consequence of Theorem 1.4 of [13], considering the coset $aH$
of the subgroup $H\subset(\mathbb{Z}/pm)^{*}$ of the quadratic residues modulo
$pm$, and $a$ a quadratic non-residue modulo $p$ and a quadratic residue
modulo $m$. ∎

######  Lemma 3.

Let $D\in\mathbb{N}$, $p$ a prime number and $S_{p,D}$ be the number of
isomorphic classes over $\mathbb{F}_{p}$ of elliptic curves over
$\mathbb{F}_{p}$ with trace $a$ such that the gcd $(a,p+1)\leq D$. Then

$S_{p,D}\geq C\max\left\\{\frac{p}{\log p}-\frac{p}{D\log
p}\tau(p+1)-\tau(p+1)^{2}\frac{\sqrt{p}}{\log p},\frac{p}{(\log
p)^{2}}\right\\},$

for some explicit constant $C$.

###### Proof.

By Proposition $1.9$ of [8], we know that given any set $S\subset I_{p}$ with
$|S|\geq 3$, then the number of isomorphism classes over $\mathbb{F}_{p}$ of
elliptic curves modulo $p$ with number of points in $S$ is bigger than
$|S|\frac{c\sqrt{p}}{\log p}$, for some explicit constant $c$. So we just have
to count the number of integers $1\leq a\leq 2\sqrt{p}$ such that $(a,p+1)=d$
for some $d\leq D$. Let us call $\varphi_{p,D}$ to this number. Note that the
number of traces with $(a_{p},p+1)\leq D$ is exactly 2$\varphi_{p,D}$ since
$(a,p+1)=d$ if and only if $(-a,p+1)=d$. Now,

$\displaystyle\varphi_{p,D}$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}d|p+1\\\ d\leq
D\end{subarray}}\sum_{\begin{subarray}{c}a\leq 2\sqrt{p}\\\
(a,p+1)=d\end{subarray}}1=\sum_{\begin{subarray}{c}d|p+1\\\ d\leq
D\end{subarray}}\sum_{\begin{subarray}{c}a\leq
2\sqrt{p}/d\end{subarray}}\sum_{k|(a,(p+1)/d)}\mu(k)$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}d|p+1\\\ d\leq
D\end{subarray}}\sum_{\begin{subarray}{c}k|(p+1)/d\end{subarray}}\mu(k)\sum_{\begin{subarray}{c}a\leq\frac{2\sqrt{p}}{kd}\end{subarray}}1=\sum_{\begin{subarray}{c}d|p+1\\\
d\leq
D\end{subarray}}\sum_{\begin{subarray}{c}k|(p+1)/d\end{subarray}}\mu(k)\left[\frac{2\sqrt{p}}{kd}\right]$
$\displaystyle=$ $\displaystyle 2\sqrt{p}\sum_{\begin{subarray}{c}d|p+1\\\
d\leq
D\end{subarray}}\frac{1}{d}\sum_{\begin{subarray}{c}k|(p+1)/d\end{subarray}}\frac{\mu(k)}{k}-\sum_{\begin{subarray}{c}d|p+1\\\
d\leq
D\end{subarray}}\sum_{\begin{subarray}{c}k|(p+1)/d\end{subarray}}\mu(k)\left\\{\frac{2\sqrt{p}}{kd}\right\\}$
$\displaystyle=$
$\displaystyle\frac{2\sqrt{p}}{p+1}\sum_{\begin{subarray}{c}d|p+1\\\ d\leq
D\end{subarray}}\varphi((p+1)/d)-\sum_{\begin{subarray}{c}d|p+1\\\ d\leq
D\end{subarray}}\sum_{\begin{subarray}{c}k|(p+1)/d\end{subarray}}\mu(k)\left\\{\frac{2\sqrt{p}}{kd}\right\\},$

and noting that

$\sum_{\begin{subarray}{c}d|p+1\end{subarray}}\varphi((p+1)/d)=\sum_{\begin{subarray}{c}d|p+1\end{subarray}}\varphi(d)=p+1.$

we get

(1)
$\varphi_{p,D}=2\sqrt{p}-\frac{2\sqrt{p}}{p+1}\sum_{\begin{subarray}{c}d|p+1\\\
d>D\end{subarray}}\varphi((p+1)/d)-\sum_{\begin{subarray}{c}d|p+1\\\ d\leq
D\end{subarray}}\sum_{\begin{subarray}{c}k|(p+1)/d\end{subarray}}\mu(k)\left\\{\frac{2\sqrt{p}}{kd}\right\\}.$

Using the trivial upper bound $\varphi(n)<n$ we get for the first sum in (1)

$\frac{2\sqrt{p}}{p+1}\sum_{\begin{subarray}{c}d|p+1\\\
d>D\end{subarray}}\varphi((p+1)/d)<{2\sqrt{p}}\sum_{\begin{subarray}{c}d|p+1\\\
d>D\end{subarray}}\frac{1}{d}<\frac{2\sqrt{p}}{D}\tau(p+1).$

The last sum in (1) can be bounded in the following way

$\displaystyle\left|\sum_{\begin{subarray}{c}d|p+1\\\ d\leq
D\end{subarray}}\sum_{\begin{subarray}{c}k|(p+1)/d\end{subarray}}\mu(k)\left\\{\frac{2\sqrt{p}}{kd}\right\\}\right|\leq\sum_{\begin{subarray}{c}d|p+1\\\
d\leq D\end{subarray}}2^{\omega((p+1)/d)}=\sum_{\begin{subarray}{c}d|p+1\\\
d\geq(p+1)/D\end{subarray}}2^{\omega(d)}$ $\displaystyle\leq$
$\displaystyle\prod_{q^{\alpha}||p+1}\sum_{\begin{subarray}{c}d|q^{\alpha}\end{subarray}}2^{\omega(d)}=\prod_{q^{\alpha}||p+1}(1+2\alpha)=\tau((p+1)^{2}).$

and hence

(2) $\varphi_{p,D}\geq
2\sqrt{p}-\frac{2\sqrt{p}}{D}\tau(p+1)-\tau((p+1)^{2}).$

On the other hand, we trivially have

$\varphi_{p,D}\geq\varphi_{p,1}$

and

$\displaystyle\varphi_{p,1}$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}a\leq 2\sqrt{p}\\\
(a,p+1)=1\end{subarray}}1=\sum_{\begin{subarray}{c}a\leq 2\sqrt{p}\\\
(a,p+1)=1\\\ 2\nmid a\end{subarray}}1=\sum_{\begin{subarray}{c}a\leq
2\sqrt{p}\\\ 2\nmid
a\end{subarray}}\sum_{k|(a,p+1)}\mu(k)=\sum_{\begin{subarray}{c}k|p+1\\\
2\nmid
k\end{subarray}}\mu(k)\sum_{\begin{subarray}{c}a\leq\frac{2\sqrt{p}}{k}\\\
2\nmid a\end{subarray}}1$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}k|p+1\\\ 2\nmid
k\end{subarray}}\mu(k)\left[\frac{\sqrt{p}}{k}+\frac{1}{2}\right]=\sqrt{p}\sum_{\begin{subarray}{c}k|p+1\\\
2\nmid
k\end{subarray}}\frac{\mu(k)}{k}+\frac{1}{2}\sum_{\begin{subarray}{c}k|p+1\\\
2\nmid k\end{subarray}}\mu(k)+\sum_{\begin{subarray}{c}k|p+1\\\ 2\nmid
k\end{subarray}}\mu(k)\left\\{\frac{2\sqrt{p}}{d}+\frac{1}{2}\right\\}$
$\displaystyle=$
$\displaystyle\sqrt{p}\frac{\varphi{(P)}}{P}+\sum_{k|P}\mu(k)\left\\{\frac{2\sqrt{p}}{d}+\frac{1}{2}\right\\}$

where $p+1=2^{k}P$ with $2\nmid P$. As before, for the last sum we have
trivially the upper bound

$\left|\sum_{k|P}\mu(k)\left\\{\frac{2\sqrt{p}}{d}+\frac{1}{2}\right\\}\right|\leq
2^{\omega(P)}$

since the sum only counts squarefree integers, and hence

(3) $\varphi_{p,D}\geq\sqrt{p}\frac{\varphi(P)}{P}-2^{\omega(P)}.$

Now, if $\omega(P)=l$, then $P\geq\prod_{p\leq p_{l}}p$. From Corollary $2$ of
Rosser and Shoenfeld [12] we obtain that $p_{l}>el$ for any $p_{l}>113$, so in
particular $\prod_{p\leq p_{l}}p\geq l^{l}$. Indeed we just need Maple to
check it is true for $13\leq l\leq 31$ and for $l>31$ we will prove it by
induction. So, suppose it is true that $\prod_{p\leq
p_{l-1}}p\geq(l-1)^{(l-1)}$. Then,

$\prod_{p\leq p_{l}}p=p_{l}\prod_{p\leq p_{l-1}}p\geq
p_{l}(l-1)^{(l-1)}>el(l-1)^{(l-1)},$

but since $a_{l}=(1+\frac{1}{l})^{l}$ is an increasing sequence with
$\lim_{n\to\infty}a_{l}=e$, we have

$el(l-1)^{(l-1)}>l(1+\frac{1}{l-1})^{l-1}(l-1)^{(l-1)}=l^{l}$

Hence, taking $l=16$ we see than $P\geq l^{l}>16^{l}=(2^{l})^{4}$ so, in
particular, we have $P>(2^{\omega(P)})^{4}$ and

$\varphi_{p,1}>\sqrt{p}\frac{\varphi(P)}{P}-p^{1/4}\geq\frac{\sqrt{p}}{8\log
p},$

for any $p\geq 10^{8}$, where we have used the trivial inequality
$\varphi(n)>\frac{n}{4\log n}$. ∎

##  3\. Proof of Theorem 1

Let $D\leq(\log n)^{k}$ for some fixed $k$. We select an elliptic curve
$E_{n}:=y^{2}=x^{3}+ax+b$ modulo $n$ at random. Suppose
$(a_{p_{1}},p_{1}+1)=d_{E}\leq D$. Take $d$ as in Lemma 2, for $p=p_{1}$ and
$m=n/p_{1}$. Then, $|E_{p_{1}}^{d}|=p_{1}+1+a_{p_{1}}$ while
$|E_{p_{i}}^{d}|=p_{i}+1-a_{p_{i}}$ for any $i=2\dots r$ and, hence

$\frac{|E_{n}|}{|E_{n}^{d}|}=\frac{p_{1}+1-a_{p_{1}}}{p_{1}+1+a_{p_{1}}}.$

Let $\frac{|E_{n}|}{|E_{n}^{d}|}=\frac{a}{b}$ where $(a,b)=1$. Then

$\frac{a}{b}=\frac{\frac{p_{1}+1-a_{p_{1}}}{d}}{\frac{p_{1}+1+a_{p_{1}}}{d}},$

and hence $a=(p_{1}+1-a_{p_{1}})d$, $b=(p_{1}+1+a_{p_{1}})d$. So we just have
to mulptiply $a$ by all the integers up to $D$ in order to recover
$p_{1}+1-a_{p_{1}}$ and mulptiply $b$ by all the integers up to $D$ to recover
$p_{1}+1+a_{p_{1}}$. Adding both number we get $2(p_{1}+1)$ and, hence, we
have found a factor of $n$.

If the algorithm does not return $p_{1}$, in $(\log n)^{k}$ steps, then stop,
and select a new elliptic curve $E^{\prime}_{n}:=y^{2}=x^{3}+Ax+B$ non
isomorphic to $E_{n}$. Note that we can assume $A\not\equiv 0\pmod{p}$ neither
$B\not\equiv 0\pmod{p}$ for $p|n$ since otherwise we find a factor of $n$.
Then, if we would get an elliptic curve isomorphic to $E_{n}$ over
$\mathbb{F}_{p}$ for some $p|n$ then $\lambda^{4}A\equiv a\pmod{p}$ and
$\lambda^{6}B\equiv b\pmod{p}$, so $\lambda^{4}\equiv\frac{a}{A}$ and
$\lambda^{6}\equiv\frac{b}{B}\pmod{p}$, or
$\lambda^{2}\equiv\frac{bA}{aB}\pmod{p}$ and then $b^{2}A^{3}-a^{3}B^{2}\equiv
0\pmod{p}$ and we would find a factor.

Now, repeating the process $k(\log n)^{2}$ times, for non isomorphic classes
of elliptic curves, the probality that none of them has the trace $a$ so that
$(a,p+1)\leq D$ is bounded above by

$\left(1-\frac{c}{(\log p)^{2}}\right)^{k(\log n)^{2}}<\
\left(1-\frac{c}{(\log p)^{2}}\right)^{k(\log
p)^{2}}<e^{-\frac{k}{c}}<\frac{c}{k}<\varepsilon,$

for $k\gg(1/\varepsilon)$. Finally note that checking that none of them is
isomorphic to the previous ones would take $O\left(k^{2}(\log n)^{4}\right)$
steps.

## References

  * [1] E. Bach, Discrete logarithms and factoring, Technical Report No. UCB/CSD- 84-186, EECS Dept., Univ. of California,, 1984.
  * [2] E. Bach and J. Shallit, Factoring with cyclotomic polynomials, Math. Comp., 185, 52, 201-219, 1989.
  * [3] E. Bach and G. Miller and J. Shallit, Sums of divisors, perfect numbers and factoring, SIAM J. Comput., 15, 4, 1143–1154, 1986.
  * [4] L. Dieulefait and J. Urroz, Factorization and Malleability of RSA Moduli, and Counting Points on Elliptic Curves Modulo $N$, Mathematics, 12, 8, 2020.
  * [5] R. Dryło and J. Pomykała, Integer factoring problem and elliptic curves over the ring $\mathbb{Z}_{n}$, Colloq. Math., Volume = 159, 2, 259–284, 2020.
  * [6] H. Hasse, Zur Theorie der abstrakten elliptischen Funktionenkörper III. Die Struktur des Meromorphismenrings. Die Riemannsche Vermutung, J. Reine Angew. Math., 175, 193–208, 1936.
  * [7] N. Kunihiro and K. Koyama, Equivalence of counting the number of points on elliptic curve over the ring $Z_{n}$ and factoring $n$, Advances in cryptology—EUROCRYPT ’98 (Espoo), Lecture Notes in Comput. Sci., 1998.
  * [8] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math., 126, 649-673, 1987.
  * [9] S. Martin and P. Morillo and J. L. Villar,Computing the order of points on an elliptic curve modulo N is as difficult as factoring N,Appl. Math. Lett.,14,341-346,2001.
  * [10] G. L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci., 13, 3, 300-317, 1976.
  * [11] T. Okamoto and S. Uchiyama, Security of an identity-based cryptosystem and the related reductions,Advances in Cryptology—EUROCRYPT ’98 (Espoo),546–560, 1998\.
  * [12] J. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math., 6, 64–94, 1962.
  * [13] Y. Lamzouri and X. Li and K. Soundararajan, Conditional bounds for the least quadratic non-residue and related problems, Math. Comp., 84, 295, 2391–2412, 2015.

##  4\. Statements and Declarations

The first author is supported by the Grant PID2019-110224RB-I00 of the Spanish
Government. The authors have no relevant financial or non-financial interests
to disclose. All authors contributed to the study, conception and design of
the paper. All authors read and approved the final manuscript.


* [EW16] Hélène Esnault and Olivier Wittenberg.  On the cycle class map for zero-cycles over local fields.  Ann. Sci. Éc. Norm. Supér. (4), 49(2):483–520, 2016.  With an appendix by Spencer Bloch.
  * [FM94] E. M. Friedlander and B. Mazur.  Correspondence homomorphisms for singular varieties.  Ann. Inst. Fourier (Grenoble), 44(3):703–727, 1994.
  * [Fri91] Eric M. Friedlander.  Algebraic cycles, Chow varieties, and Lawson homology.  Compositio Math., 77(1):55–93, 1991.
  * [Gei00] Thomas Geisser.  Applications of de Jong’s theorem on alterations.  In Resolution of singularities (Obergurgl, 1997), volume 181 of Progr. Math., pages 299–314. Birkhäuser, Basel, 2000.
  * [HB18] D. R. Heath-Brown.  Zeros of pairs of quadratic forms.  J. Reine Angew. Math., 739:41–80, 2018.
  * [Hof07] Norbert Hoffmann.  Rationality and Poincaré families for vector bundles with extra structure on a curve.  Int. Math. Res. Not. IMRN, (3):Art. ID rnm010, 30, 2007.
  * [HW20] Yonatan Harpaz and Olivier Wittenberg.  Zéro-cycles sur les espaces homogènes et problème de Galois inverse.  J. Amer. Math. Soc., 33(3):775–805, 2020.
  * [Kel17] Shane Kelly.  Voevodsky motives and $l$dh-descent.  Astérisque, (391):125, 2017.
  * [KMM92] János Kollár, Yoichi Miyaoka, and Shigefumi Mori.  Rationally connected varieties.  J. Algebraic Geom., 1(3):429–448, 1992.
  * [Kol96] János Kollár.  Rational curves on algebraic varieties, volume 32 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics].  Springer-Verlag, Berlin, 1996.
  * [KS99] Alastair King and Aidan Schofield.  Rationality of moduli of vector bundles on curves.  Indag. Math. (N.S.), 10(4):519–535, 1999.
  * [KT23] János Kollár and Zhiyu Tian.  Stable maps of curves and algebraic equivalence of $1$-cycles.  arXiv preprint, https://arxiv.org/abs/2302.07069, 2023.
  * [Law89] H. Blaine Lawson, Jr.  Algebraic cycles and homotopy theory.  Ann. of Math. (2), 129(2):253–291, 1989.
  * [LF94] Paulo Lima-Filho.  The topological group structure of algebraic cycles.  Duke Math. J., 75(2):467–491, 1994.
  * [Lia13] Yongqi Liang.  Arithmetic of 0-cycles on varieties defined over number fields.  Ann. Sci. Éc. Norm. Supér. (4), 46(1):35–56 (2013), 2013\.
  * [New75] P. E. Newstead.  Rationality of moduli spaces of stable bundles.  Math. Ann., 215:251–268, 1975.
  * [New80] P. E. Newstead.  Correction to: “Rationality of moduli spaces of stable bundles” [Math. Ann. 215 (1975), 251–268; MR 54 #7468].  Math. Ann., 249(3):281–282, 1980.
  * [Pan18] Xuanyu Pan.  Spaces of conics on low degree complete intersections.  Trans. Amer. Math. Soc., 370(8):5381–5400, 2018.
  * [PS16] Raman Parimala and Venapally Suresh.  Degree 3 cohomology of function fields of surfaces.  Int. Math. Res. Not. IMRN, (14):4341–4374, 2016.
  * [Sai89] S. Saito.  Some observations on motivic cohomology of arithmetic schemes.  Invent. Math., 98(2):371–404, 1989.
  * [Sai91] Shuji Saito.  On the cycle map for torsion algebraic cycles of codimension two.  Invent. Math., 106(3):443–460, 1991.
  * [Sca22] Federico Scavia.  Autour de la conjecture de Tate entière pour certains produits de dimension 3 sur un corps fini.  Épijournal Géom. Algébrique, 6:Art. 11, 28, 2022.
  * [Sch98] Chad Schoen.  An integral analog of the Tate conjecture for one-dimensional cycles on varieties over finite fields.  Math. Ann., 311(3):493–500, 1998.
  * [SS91] P. Salberger and A. N. Skorobogatov.  Weak approximation for surfaces defined by two quadratic forms.  Duke Math. J., 63(2):517–536, 1991.
  * [SS22] Federico Scavia and Fumiaki Suzuki.  Non-algebraic geometrically trivial cohomology classes over finite fields.  2022\.
  * [STZ22] Jason M. Starr, Zhiyu Tian, and Runhong Zong.  Weak approximation for Fano complete intersections in positive characteristic.  Ann. Inst. Fourier (Grenoble), 72(4):1503–1534, 2022.
  * [Sus00] Andrei A. Suslin.  Higher Chow groups and etale cohomology.  In Cycles, transfers, and motivic homology theories, volume 143 of Ann. of Math. Stud., pages 239–254. Princeton Univ. Press, Princeton, NJ, 2000.
  * [SV96] Andrei Suslin and Vladimir Voevodsky.  Singular homology of abstract algebraic varieties.  Invent. Math., 123(1):61–94, 1996.
  * [SV00] Andrei Suslin and Vladimir Voevodsky.  Relative cycles and Chow sheaves.  In Cycles, transfers, and motivic homology theories, volume 143 of Ann. of Math. Stud., pages 10–86. Princeton Univ. Press, Princeton, NJ, 2000.
  * [Tia17] Zhiyu Tian.  Hasse principle for three classes of varieties over global function fields.  Duke Math. Journal, 166(17):3349–3424, 2017.
  * [Tia20] Zhiyu Tian.  Zero cycles on rationally connected varieties over laurent fields.  arXiv preprint, https://arxiv.org/abs/2010.04996, 2020.
  * [TZ18] Zhiyu Tian and Letao Zhang.  Weak approximation for cubic hypersurfaces and degree 4 del Pezzo surfaces.  Int. Math. Res. Not. IMRN, (3):762–784, 2018.
  * [Voi08] Mircea Voineagu.  Semi-topological $K$-theory for certain projective varieties.  J. Pure Appl. Algebra, 212(8):1960–1983, 2008.
  * [Voi22] Claire Voisin.  On the coniveau of rationally connected threefolds.  Geom. Topol., 26(6):2731–2772, 2022.
  * [Wal07] Mark E. Walker.  The morphic Abel-Jacobi map.  Compos. Math., 143(4):909–944, 2007.
  * [Wit07] Olivier Wittenberg.  Intersections de deux quadriques et pinceaux de courbes de genre 1/Intersections of two quadrics and pencils of curves of genus 1, volume 1901 of Lecture Notes in Mathematics.  Springer, Berlin, 2007.
  * [Wit18] Olivier Wittenberg.  Rational points and zero-cycles on rationally connected varieties over number fields.  In Algebraic geometry: Salt Lake City 2015, volume 97 of Proc. Sympos. Pure Math., pages 597–635. Amer. Math. Soc., Providence, RI, 2018.


# Putting words in context:
LSTM language models and lexical ambiguity

Laura Aina Kristina Gulordava Gemma Boleda
Universitat Pompeu Fabra
Barcelona, Spain
<EMAIL_ADDRESS>
###### Abstract

In neural network models of language, words are commonly represented using
context-invariant representations (word embeddings) which are then put in
context in the hidden layers. Since words are often ambiguous, representing
the contextually relevant information is not trivial. We investigate how an
LSTM language model deals with lexical ambiguity in English, designing a
method to probe its hidden representations for lexical and contextual
information about words. We find that both types of information are
represented to a large extent, but also that there is room for improvement for
contextual information.

##  1 Introduction

Examples |  LexSub |  $\mathbf{w}$ nn |  $\mathbf{s}$ nn |  $\mathbf{w\&s}$ nn
---|---|---|---|---
(1) …I clapped her shoulder to show I was not laughing at her… |  demonstrate, display, indicate, prove, clarify |  demonstrate, exhibit, indicate, offer, reveal |  indicate, demonstrate, suggest, prove, |  indicate, demonstrate, prove, ensure, suggest
(2) …The show […] revolutionized the way America cooks and eats… |  program, series, broadcast, presentation |  demonstrate, exhibit, indicate, offer, reveal |  series, program, production, miniseries, trilogy |  series, program, production, broadcast
(3) …The inauguration of Dubai Internet City coincides with the opening of an annual IT show in Dubai…. |  exhibition, conference, convention, demonstration |  demonstrate, exhibit, indicate, offer, reveal |  conference, event, convention, symposium, exhibition |  conference, event, exhibition, symposium, convention
Table 1: Examples from the LexSub dataset Kremer et al. (2014) and nearest
neighbors for target representations.

In language, a word can contribute a very different meaning to an utterance
depending on the context, a phenomenon known as lexical ambiguity Cruse
(1986); Small et al. (2013). This variation is pervasive and involves both
morphosyntactic and semantic aspects. For instance, in the examples in Table
1, show is used as a verb in Ex. (1), and as a noun in Ex. (2-3), in a
paradigmatic case of morphosyntactic ambiguity in English. Instead, the
difference between Ex. (2) and (3) is semantic in nature, with show denoting a
TV program and an exhibition, respectively. Semantic ambiguity covers a broad
spectrum of phenomena, ranging from quite distinct word senses (e.g. mouse as
animal or computer device) to more subtle lexical modulation (e.g. visit a
city / an aunt / a doctor; Cruse, 1986). This paper investigates how deep
learning models of language, and in particular Long Short-Term Memory Networks
(LSTMs) trained on Language Modeling, deal with lexical ambiguity.111Code at:
https://github.com/amore-upf/LSTM_ambiguity

In neural network models of language, words in a sentence are commonly
represented through word-level representations that do not change across
contexts, that is, “static” word embeddings. These are then passed to further
processing layers, such as the hidden layers in a recurrent neural network
(RNN). Akin to classic distributional semantics Erk (2012), word embeddings
are formed as an abstraction over the various uses of words in the training
data. For this reason, they are apt to represent context-invariant information
about a word —its lexical information— but not the contribution of a word in a
particular context —its contextual information Erk (2010). Indeed, word
embeddings subsume information relative to various senses of a word (e.g.,
mouse is close to words from both the animal and computer domain; Camacho-
Collados and Pilehvar, 2018).

Classic distributional semantics attempted to do composition to account for
contextual effects, but it was in general unable to go beyond short phrases
Baroni (2013); newer-generation neural network models have supposed a big step
forward, as they can natively do composition Westera and Boleda (2019). In
particular, the hidden layer activations in an RNN can be seen as putting
words in context, as they combine the word embedding with information coming
from the context (the adjacent hidden states). The empirical success of RNN
models, and in particular LSTM architectures, at fundamental tasks like
Language Modeling Jozefowicz et al. (2015) suggests that they are indeed
capturing relevant contextual properties. Moreover, contextualized
representations derived from such models have been shown to be very
informative as input for lexical disambiguation tasks (e.g. Melamud et al.,
2016; Peters et al., 2018).

We here present a method to probe the extent to which the hidden layers of an
LSTM language trained on English data represent lexical and contextual
information about words, in order to investigate how the model copes with
lexical ambiguity. Our work follows a recent strand of research that purport
to identify what linguistic properties deep learning models are able to
capture (Linzen et al., 2016; Adi et al., 2017; Gulordava et al., 2018;
Conneau et al., 2018; Hupkes et al., 2018, a.o.). We train diagnostic models
on the tasks of retrieving the embedding of a word and a representation of its
contextual meaning, respectively —the latter obtained from a Lexical
Substitution dataset Kremer et al. (2014). Our results suggest that LSTM
language models heavily rely on the lexical information in the word
embeddings, at the expense of contextually relevant information. Although
further analysis is necessary, this suggests that there is still much room for
improvement to account for contextual meanings. Finally, we show that the
hidden states used to predict a word – as opposed to those that receive it as
input – display a bias towards contextual information.

##  2 Method

#### Language model.

As our base model, we employ a word-level bidirectional LSTM Schuster and
Paliwal (1997); Hochreiter and Schmidhuber (1997) language model (henceforth,
LM) with three hidden layers. Each input word at timestep $t$ is represented
through its word embedding $\mathbf{w}_{t}$; this is fed to both a forward and
a backward stacked LSTMs, which process the sequence left-to-right and right-
to-left, respectively (Eqs. (1-2) describe the forward LSTM). To predict the
word at $t$, we obtain output weights by summing the activations of the last
hidden layers of the forward and backward LSTMs at timesteps $t-1$ and $t+1$,
respectively, and applying a linear transformation followed by softmax (Eq. 3,
where $L$ is the number of hidden layers). Thus, a word is predicted using
both its left and right context jointly, akin to the context2vec architecture
Melamud et al. (2016) but differently from, e.g., the BiLSTM architecture used
for ELMo Peters et al. (2018).

$\displaystyle\mathbf{h}_{t}^{1}=\text{LSTM}^{1}(\mathbf{w}_{t},\mathbf{h}_{t-1}^{1})$
(1)
$\displaystyle\mathbf{h}_{t}^{i}=\text{LSTM}^{i}(\mathbf{h}_{t}^{i-1},\mathbf{h}_{t-1}^{i})$
(2)
$\displaystyle\mathbf{o}_{t}=softmax(f(\overrightarrow{\mathbf{h}}^{L}_{t-1}+\overleftarrow{\mathbf{h}}^{L}_{t+1}))$
(3)

We train the LM on the concatenation of English text data from a Wikipedia
dump222From 2018/01/03, https://dumps.wikimedia.org/enwiki/, the British
National Corpus Leech (1992), and the UkWaC corpus Ferraresi et al.
(2008).33350M tokens from each corpus, in total 150M (train/valid/test:
80/10/10%); vocabulary size: 50K. More details about the training setup are
specified in Appendix A.1. The model achieves satisfying performances on test
data (perplexity: 18.06).

For our analyses, we deploy the trained LM on a text sequence and extract the
following activations of each hidden layer; Eq. (4) and Fig. 1.

$\displaystyle\\{\overrightarrow{\mathbf{h}}^{i}_{t}|i\leq
L\\}\cup\\{\overleftarrow{\mathbf{h}}^{i}_{t}|i\leq L\\}$ (4)
$\displaystyle\mathbf{h}_{t}^{i}=[\overrightarrow{\mathbf{h}}^{i}_{t};\overleftarrow{\mathbf{h}}^{i}_{t}]$
(5) $\displaystyle\mathbf{h}_{t\pm
1}^{i}=[\overrightarrow{\mathbf{h}}^{i}_{t-1};\overleftarrow{\mathbf{h}}^{i}_{t+1}]$
(6)

At timestep $t$, for each layer, we concatenate the forward and backward
hidden states; Eq. (5). We refer to these vectors as current hidden states. As
they are obtained processing the word at $t$ as input and combining it with
information from the context, we can expect them to capture the relevant
contribution of such word (e.g., in Fig. 1 the mouse-as-animal sense). As a
comparison, we also extract activations obtained by processing the text
sequence up to $t-1$ and $t+1$ in the forward and backward LSTM, respectively,
hence excluding the word at $t$. We concatenate the forward and backward
states of each layer; Eq. (6). While these activations do not receive the word
at $t$ as input, they are relevant because they are used to predict that word
as output. We refer to them as predictive hidden states. These may capture
some aspects of the word (e.g., in Fig. 1, that it is a noun and denotes
something animate), but are likely to be less accurate than the current
states, since they do not observe the actual word.

Figure 1: Language model and extracted representations. The different shades
across layers reflect the different performances in the probe tasks (darker =
higher)

#### Probe tasks.

We aim to assess to what extent the hidden states in the LM carry over the
lexical and context-invariant information in the input word embedding, and how
much they instead represent the contextual meaning of the word. To this end,
we rely on vector representations of lexical and contextual word information.
As for the former, we can directly use the word embeddings of the LM (w); it
is instead more challenging to find a representation of the contextual
meaning.

Our solution is to use Lexical Substitution data McCarthy and Navigli (2009)
and, in particular, the large dataset by Kremer et al., 2014 (henceforth,
LexSub; see Table 1). In this dataset, words in context (up to 3 sentences)
are annotated with a set of paraphrases given by human subjects. Since
contextual substitutes reflect differences among uses of a word (for instance,
demonstrate paraphrases show in a context like Ex. (1), but not in Ex. (2)),
this type of data is often used as an evaluation benchmark for contextual
representations of words (e.g., Erk and Padó, 2008; Melamud et al., 2016; Garí
Soler et al., 2019). We leverage LexSub to build proxies for ground-truth
representations of the contextual meaning of words. We define two types of
representations, inspired by previous work that proposed simple vector
operations to combine word representations (Mitchell and Lapata, 2010; Thater
et al., 2011, a.o.): the average embedding of the substitute words
(henceforth, $\mathbf{s}$), and the average embedding of the union of the
substitute words and the target word ($\mathbf{w\&s}$). As Table 1
qualitatively shows, the resulting representations tend to be close to the
substitute words and reflect the contextual nuance conveyed by the word; in
the case of $\mathbf{w\&s}$, they also retain a strong similarity to the
embedding of the target word.444These vectors are close to the related word
embedding (0.45 and 0.66 mean cosine, see Table 2, row $\mathbf{w}_{t}$), but
also different from it: on average, $\mathbf{s}$ and $\mathbf{w\&s}$ share 17
and 25% of the top-10 neighbors with $\mathbf{w}$, respectively (statistics
from training data, excluding the word itself from neighbors).

We frame our analyses as supervised probe tasks: a diagnostic model learns to
“retrieve” word representations out of the hidden states; the rate of success
of the model is taken to measure the amount of information relevant to the
task that its input contains. Given current or predictive states as inputs, we
define three diagnostic tasks:

  * -

Word: predict $\mathbf{w}$

  * -

Sub: predict $\mathbf{s}$

  * -

Word&Sub: predict $\mathbf{w\&s}$

The Word task is related to the probe tasks introduced in Adi et al. (2017)
and Conneau et al. (2018), which, given a hidden state, require to predict the
words that a sentence encoder has processed as input. Note that, while these
authors predict words by their discrete index, we are predicting the complete
multi-dimensional embedding of the word. Our test quantifies not only whether
the model is tracking the identity of the input word, but also how much of its
information it retains.

We train distinct probe models for each task and type of input ($\mathbf{i}$;
e.g., current hidden state at layer 1). A model consists of a non-linear
transformation from an input vector $\mathbf{i}$ (extracted from the LM) to a
vector with the dimensionality of the word embeddings (Eq. 7, where
$\mathbf{\hat{r}}$ is one of $\mathbf{\hat{w}}$, $\mathbf{\hat{s}}$,
$\mathbf{\hat{w\&s}}$ for Word, Sub, and Word&Sub tasks, respectively). The
models are trained through max-margin loss, optimizing the cosine similarity
between $\mathbf{\hat{r}}$ and the target representation against the
similarities between $\mathbf{\hat{r}}$ and 5 negative samples (details in
Appendix A.2).

$\mathbf{\hat{r}}=tanh(W\ \mathbf{i}+b)\vspace{-0.1cm}$ (7)

We adapt the LexSub data to our setup as follows. Since substitutes are
provided in their lemmatized form, we only consider datapoints where the word
form is identical to the lemma so as to exclude effects due to morphosyntax
(e.g., asking the models to recover play when they observe played).555We also
exclude substitutes that are multi-word expressions and the datapoints
involving words that are part of a compound (e.g., fast in fast-growing). We
require that at least 5 substitutes per datapoint are in the LM vocabulary to
ensure quality in the target representations. LexSub data come with a
validation/test split; since we need training data, we create a new random
partitioning into train/valid/test (70/10/20%, with no overlapping contexts
among splits). The final data consist of 4.7K/0.7K/1.3K datapoints for
train/valid/test.

##  3 Results

The results of the probe tasks on test data are presented in Table 2. We
report the mean and standard deviation of the cosine similarity between the
output representations ($\mathbf{\hat{w}}$, $\mathbf{\hat{s}}$,
$\mathbf{\hat{w\&s}}$) and the target ones ($\mathbf{w}$, $\mathbf{s}$,
$\mathbf{w\&s}$). This evaluates the degree to which the word representations
can be retrieved from the hidden states. For comparison, we also report the
cosine scores between the targets and two baseline representations: the word
embedding itself and the average of word embeddings of a 10-word window around
the target word ($avg_{ctxt}$).666We exclude out-of-vocabulary words and
punctuation. Overall, the models do better than these unsupervised baselines,
with exceptions.777The first cell is 1 as it involves the same representation.

input | Word | Sub | Word&Sub
---|---|---|---
$\mathbf{w}_{t}$ | 1 | .45 ($\pm.14$) | .66 ($\pm.09$)
$avg_{ctxt}$ | .35 ($\pm.10$) | .16 ($\pm.11$) | .24 ($\pm.12$)
$\mathbf{h}_{t}^{1}$ |  .84 ($\pm.2$) |  .61 ($\pm.14$) |  .71 ($\pm.11$)
$\mathbf{h}_{t}^{2}$ | .74 ($\pm.12$) | .60 ($\pm.13$) | .69 ($\pm.11$)
$\mathbf{h}_{t}^{3}$ | .64 ($\pm.12$) | .58 ($\pm.13$) | .65 ($\pm.11$)
$\mathbf{h}_{t\pm 1}^{1}$ | .25 ($\pm.16$) | .36 ($\pm.16$) | .38 ($\pm.16$)
$\mathbf{h}_{t\pm 1}^{2}$ | .27 ($\pm.16$) | .39 ($\pm.16$) | .41 ($\pm.16$)
$\mathbf{h}_{t\pm 1}^{3}$ |  .29 ($\pm.15$) |  .41 ($\pm.16$) |  .43 ($\pm.16$)
Table 2: Results of probe tasks for current ($\mathbf{h}^{i}_{t}$) and predictive ($\mathbf{h}_{t\pm 1}^{i}$) hidden states. Figure 2: Similarity of lexical and contextual vector ($\mathbf{w}$ \- $\mathbf{s}$) vs. similarity of target and prediction in Sub for $\mathbf{h}_{t}^{1}$. Context |  LexSub |  Word: $\mathbf{\hat{w}}$ nn |  Sub: $\mathbf{\hat{s}}$ nn |  Word&Sub: $\mathbf{w\hat{\&}s}$ nn
---|---|---|---|---
(4) … The financial-services company will pay 0.82 share for each Williams share … |  stock, dividend, interest, stake, unit |  stake, owe, discuss, coincide, reside |  portion, amount, percentage, fraction |  stake, percentage, portion, spend, proportion
(5) … Sony’s effort to hire producers Jon Peters and Peter Guber to run the studio… |  business, company, facility, film, lot |  lab, troupe, classroom, apartment, booth |  room, gallery, troupe, journal, house |  room, troupe, lab, audience, department
(6) … I had […] told her that we needed other company than our own … |  friend, acquaintance, visitor, accompaniment, associate |  retailer, trader, firm, maker, supplier |  firm, corporation, organisation, conglomerate, retailer |  corporation, firm, conglomerate, retailer, organisation
Table 3: Examples with nearest neighbours of the representations predicted in
the first current hidden layer.

#### Current hidden states.

Both lexical and contextual representations can be retrieved from the current
hidden states ($\mathbf{h}^{i}_{t}$) to a large extent (cosines .58-.84), but
retrieving the former is much easier than the latter (.64-.84 vs. .58-71).
This suggests that the information in the word embedding is better represented
in the hidden states than the contextually relevant one. In all three tasks,
performance degrades closer to the output layer (from $\mathbf{h}_{t}^{1}$ to
$\mathbf{h}_{t}^{3}$), but the effect is more pronounced for the Word task
(84/.74/.64). Word embeddings are part of the input to the hidden state, and
the transformation learned for this task can be seen as a decoder in an auto-
encoder, reconstructing the original input; the further the hidden layer is
from the input, the more complex the function is to reverse-engineer.
Crucially, the high performance at reconstructing the word embedding suggests
that lexical information is retained in the hidden layers, possibly including
also contextually irrelevant information (e.g., in Ex. (4) in Table 3
$\mathbf{\hat{w}}$ is close to verbs, even if share is here a noun).

Contextual information ($\mathbf{s}$ and $\mathbf{w\&s}$) seems to be more
stable across processing layers, although overall less present (cf. lower
results). Table 3 reports one example where the learned model displays
relevant contextual aspects (Ex. (4), share) and one where it does not (Ex.
(5), studio). Qualitative analysis shows that morphosyntactic ambiguity (e.g.,
share as a noun vs. verb) is more easily discriminated, while semantic
distinctions pose more challenges (e.g., studio as a room vs. company). This
is not surprising, since the former tends to correlate with clearer contextual
cues. Furthermore, we find that the more the contextual representation is
aligned to the lexical one, the easier it is to retrieve the former from the
hidden states (e.g., correlation $\cos(\mathbf{w},\mathbf{s})$ \-
$\cos(\mathbf{\hat{s}},\mathbf{s})$, for $\mathbf{h}_{t}^{1}$: Pearson’s
$\rho=.62^{***}$; Fig. 2): that is, it is harder to resolve lexical ambiguity
when the contextual meaning is less represented in the word embedding (e.g.,
less frequent uses). This suggests that the LM heavily relies on the
information in the word embedding, making it challenging to diverge from it
when contextually relevant (see Ex. (6) in Table 3).

#### Current vs. predictive hidden states.

The predictive hidden states are obtained without observing the target word;
hence, recovering word information is considerably harder than for current
states. Indeed, we observe worse results in this condition (e.g., below
$avg_{ctxt}$ in the word task); we also observe two patterns that are opposite
to those observed for current states, which shed light on how LSTM LMs track
word information.

For predictive states, results improve closer to the output (from layer 1 to
3; they instead degrade for current states). We link this to the double
objective that a LM has when it comes to word information: to integrate a word
passed as input, and to predict one as output. Our results suggest that the
hidden states keep track of information for both words, but lower layers focus
more on the processing of the input and higher ones on the predictive aspect
(see Fig. 1). This is in line with previous work showing that activations
close to the output tend to be task-specific Liu et al. (2019).

Moreover, from predictive states, it is easier to retrieve contextual than
lexical representations (.41/.43 vs. .29; the opposite was true for current
states). Our hypothesis is that this is due to a combination of two factors.
On the one hand, predictive states are based solely on contextual information,
which highlights only certain aspects of a word; for instance, the context of
Ex. (2) in Table 1 clearly signals that a noun is expected, and the predictive
states in a LM should be sensitive to this kind of cue, as it affects the
probability distribution over words. On the other hand, lexical
representations are underspecified; for instance, the word embedding for show
abstracts over both verbal and nominal uses of the word. Thus, it makes sense
that the predictive state does not capture contextually irrelevant aspects of
the word embedding, unlike the current state (note however that, as stated
above, the overall performance of the current state is better, because it has
access to the word actually produced).

##  4 Future work

We introduced a method to study how deep learning models of language deal with
lexical ambiguity. Though we focused on LSTM LMs for English, this method can
be applied to other architectures, objective tasks, and languages;
possibilities to explore in future work. We also plan to carry out further
analyses aimed at individuating factors that challenge the resolution of
lexical ambiguity (e.g., morphosyntactic vs. semantic ambiguity, frequency of
a word or sense, figurative uses), as well as clarifying the interaction
between prediction and processing of words within neural LMs.

## Acknowledgements

This project has received funding from the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 715154), and from the Ramón y Cajal programme (grant
RYC-2015-18907). We gratefully acknowledge the support of NVIDIA Corporation
with the donation of GPUs used for this research, and the computer resources
at CTE-POWER and the technical support provided by Barcelona Supercomputing
Center (RES-FI-2018-3-0034). This paper reflects the authors’ view only, and
the EU is not responsible for any use that may be made of the information it
contains.

## References

  * Adi et al. (2017) Yossi Adi, Einat Kermany, Yonatan Belinkov, Ofer Lavi, and Yoav Goldberg. 2017.  Fine-grained analysis of sentence embeddings using auxiliary prediction tasks.  In _Proceedings of 5th ICLR International Conference on Learning Representations_.
  * Baroni (2013) Marco Baroni. 2013.  Composition in distributional semantics.  _Language and Linguistics Compass_ , 7(10):511–522.
  * Camacho-Collados and Pilehvar (2018) Jose Camacho-Collados and Taher Pilehvar. 2018.  From word to sense embeddings: A survey on vector representations of meaning.  _Journal of Artificial Intelligence_ , 63(1):743–788.
  * Conneau et al. (2018) Alexis Conneau, Germán Kruszewski, Guillaume Lample, Loïc Barrault, and Marco Baroni. 2018.  What you can cram into a single $&!#* vector: Probing sentence embeddings for linguistic properties.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics_ , pages 2126–2136.
  * Cruse (1986) Alan Cruse. 1986.  _Lexical semantics_.  Cambridge University Press.
  * Erk (2010) Katrin Erk. 2010.  What is word meaning, really? (and how can distributional models help us describe it?).  In _Proceedings of the 2010 Workshop on Geometrical Models of Natural Language Semantics_ , pages 17–26.
  * Erk (2012) Katrin Erk. 2012.  Vector space models of word meaning and phrase meaning: A survey.  _Language and Linguistics Compass_ , 6(10):635–653.
  * Erk and Padó (2008) Katrin Erk and Sebastian Padó. 2008.  A structured vector space model for word meaning in context.  In _Proceedings of the EMNLP Conference on Empirical Methods in Natural Language Processing_ , pages 897–906.
  * Ferraresi et al. (2008) Adriano Ferraresi, Eros Zanchetta, Marco Baroni, and Silvia Bernardini. 2008.  Introducing and evaluating ukWac, a very large web-derived corpus of English.  In _Proceedings of the 4th Web as Corpus Workshop (WAC-4) Can we beat Google_ , pages 47–54.
  * Garí Soler et al. (2019) Aina Garí Soler, Anne Cocos, Marianna Apidianaki, and Chris Callison-Burch. 2019.  A comparison of context-sensitive models for lexical substitution.  In _Proceedings of the 13th International Conference on Computational Semantics (IWCS)_.
  * Gulordava et al. (2018) Kristina Gulordava, Piotr Bojanowski, Edouard Grave, Tal Linzen, and Marco Baroni. 2018.  Colorless green recurrent networks dream hierarchically.  In _Proceedings of the 2018 NAACL-HLT Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1195–1205.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780.
  * Hupkes et al. (2018) Dieuwke Hupkes, Sara Veldhoen, and Willem Zuidema. 2018.  Visualisation and ’diagnostic classifiers’ reveal how recurrent and recursive neural networks process hierarchical structure.  _Journal of Artificial Intelligence Research_ , 61:907–926.
  * Jozefowicz et al. (2015) Rafal Jozefowicz, Wojciech Zaremba, and Ilya Sutskever. 2015.  An empirical exploration of recurrent network architectures.  In _International Conference on Machine Learning_ , pages 2342–2350.
  * Kingma and Ba (2014) Diederik P. Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Kremer et al. (2014) Gerhard Kremer, Katrin Erk, Sebastian Padó, and Stefan Thater. 2014.  What substitutes tell us-analysis of an” all-words” lexical substitution corpus.  In _Proceedings of the 14th EACL Conference of the European Chapter of the Association for Computational Linguistics_ , pages 540–549.
  * Leech (1992) Geoffrey Neil Leech. 1992.  100 million words of English: the British National corpus (BNC).
  * Linzen et al. (2016) Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. 2016.  Assessing the ability of LSTMs to learn syntax-sensitive dependencies.  _Transactions of the Association for Computational Linguistics_ , 4:521–535.
  * Liu et al. (2019) Nelson F Liu, Matt Gardner, Yonatan Belinkov, Matthew Peters, and Noah A Smith. 2019\.  Linguistic knowledge and transferability of contextual representations.  In _Proceedings of the 2019 NAACL-HLT Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_.
  * McCarthy and Navigli (2009) Diana McCarthy and Roberto Navigli. 2009.  The English lexical substitution task.  _Language resources and evaluation_ , 43(2):139–159.
  * Melamud et al. (2016) Oren Melamud, Jacob Goldberger, and Ido Dagan. 2016.  context2vec: Learning generic context embedding with bidirectional lstm.  In _Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning_ , pages 51–61.
  * Mitchell and Lapata (2010) Jeff Mitchell and Mirella Lapata. 2010.  Composition in distributional models of semantics.  _Cognitive science_ , 34(8):1388–1429.
  * Paszke et al. (2017) Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017.  Automatic differentiation in PyTorch.  In _NIPS Autodiff Workshop_.
  * 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 _Proceedings of the 2018 NAACL-HLT Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2227–2237.
  * Schuster and Paliwal (1997) Mike Schuster and Kuldip K Paliwal. 1997.  Bidirectional recurrent neural networks.  _IEEE Transactions on Signal Processing_ , 45(11):2673–2681.
  * Small et al. (2013) Steven L Small, Garrison W Cottrell, and Michael K Tanenhaus. 2013.  _Lexical Ambiguity Resolution: Perspective from Psycholinguistics, Neuropsychology and Artificial Intelligence_.  Elsevier.
  * Thater et al. (2011) Stefan Thater, Hagen Fürstenau, and Manfred Pinkal. 2011.  Word meaning in context: A simple and effective vector model.  In _Proceedings of 5th International Joint Conference on Natural Language Processing_ , pages 1134–1143.
  * Westera and Boleda (2019) Matthijs Westera and Gemma Boleda. 2019.  Don’t blame distributional semantics if it can’t do entailment.  In _Proceedings of the 13th International Conference on Computational Semantics (IWCS)_ , pages 120–133.

##  Appendix A Appendix

###  A.1 Language model

The hidden layers are of sizes 600/600/300 respectively, while the word
embeddings are of size 300. The language model was trained optimizing the log-
likelihood of a target word given its surrounding context, with stochastic
gradient descent for 20 epochs with decaying learning rate using Adam
optimiser Kingma and Ba (2014). The initial learning rate was 0.0005 for batch
size of 32. Dropout was set to 0.2 and applied to the input embedding, and the
outputs of the LSTM layers. At training time, the text data is fed to the
model in sequences of 100 tokens.

###  A.2 Diagnostic models

We train separate models for each combination of task and input type. Each
model consist of a linear transformation and a $tahn$ non-linearity, trained
using Cosine Embedding Loss (PyTorch 0.4, Paszke et al., 2017) and Adam
optimiser, with early stopping based on validation loss. We carried out
hyperparameter search based on validation loss for each of the model types in
order to set batch size and initial learning rate. We report the final
settings for each combination of input and task in Table 4.

At training time, for each positive target word, we obtain 5 negative targets
by sampling words from the frequency quartile of the postive target (frequency
is computed on the training corpus of the language model). We always exclude
the target word, as well as the substitute words in the sub and word&sub
conditions, from the negative samples. Given the input vector, we maximize the
margin of the resulting output vector $\hat{r}$ to the embeddings of the
negative samples ($i=-1$), and minimize the distance of the output vector to
the target representation of the positive instance ($i=1$; Eq. 8).

$L(\hat{r},r,i)=\\\ \begin{cases}1-cos(\hat{r},r)\hskip 56.9055pt\text{if
}i=1\\\ \\\ \hskip 113.81102pt\text{if }i=-1\\\
max(0,cos(\hat{r},r)-\text{margin})\end{cases}$ (8)

At each training epoch, new negative instances are sampled, and the data is
shuffled.

input | Word | sub | Word&sub
---|---|---|---
$\mathbf{h}_{t}^{1}$ | $16,5\times 10^{-5}$ | $32,1\times 10^{-4}$ | $32,5\times 10^{-5}$
$\mathbf{h}_{t}^{2}$ | $16,5\times 10^{-5}$ | $64,5\times 10^{-4}$ | $64,5\times 10^{-4}$
$\mathbf{h}_{t}^{3}$ | $16,5\times 10^{-5}$ | $128,5\times 10^{-4}$ | $16,5\times 10^{-5}$
$\mathbf{h}_{t\pm 1}^{1}$ | $128,1\times 10^{-3}$ | $128,1\times 10^{-3}$ | $128,5\times 10^{-4}$
$\mathbf{h}_{t\pm 1}^{2}$ | $16,1\times 10^{-4}$ | $64,5\times 10^{-4}$ | $16,5\times 10^{-4}$
$\mathbf{h}_{t\pm 1}^{3}$ | $128,1\times 10^{-3}$ | $16,1\times 10^{-4}$ | $128,5\times 10^{-4}$
Table 4: Hyperparameter settings in the diagnostic models (batch size, initial
learning rate)