# Noncommutative Gröbner Bases and Ext groups; Application to the Steenrod
Algebra

Weinan Lin

###### Abstract.

We consider a theory of noncommutative Gröbner bases on decreasingly filtered
algebras whose associated graded algebras are commutative. We transfer many
algorithms that use commutative Gröbner bases to this context. As an important
application, we implement very efficient algorithms to compute the Ext groups
over the Steenrod algebra ${\mathscr{A}}$ at the prime $2$. Especially, the
cohomology of the Steenrod algebra
$\mathrm{Ext}_{\mathscr{A}}^{*,*}({\mathbb{F}}_{2},{\mathbb{F}}_{2})$, which
plays an important role in algebraic topology, is calculated up to total
degree of 261, including the ring structure in this range.

###### Contents

  1. 1 Introduction
  2. 2 Filtered-Commutative Algebras
  3. 3 Bases and Monomial Orderings
  4. 4 Gröbner bases over Filtered-Commutative Algebras
  5. 5 Modules
  6. 6 Syzygies
  7. 7 Ext Groups
  8. 8 The Steenrod Algebra
  9. 9 Computing the Ext Groups over the Steenrod Algebra

††Project funded by China Postdoctoral Science Foundation, 2021TQ0015

##  1\. Introduction

The commutative Gröbner basis theory [7] has been a very powerful tool in
different areas of mathematics such as commutative algebra, algebraic
geometry, homological algebra and applied mathematics. There are several works
on generalizing the Gröbner bases to noncommutative algebras, including [2]
for enveloping algebras of Lie algebras, [3] and [17] for two-sided ideals in
noncommutative free algebras and [10] exploring the relationship between
commutative and noncommutative Gröbner bases.

However, most of the Gröbner basis theories rely on restrictive monomial
orderings that require $M\geq N$ when a monomial $M$ is a multiple of another
monomial $N$. This paper introduces a different type of monomial orderings
(Definition 3.1) which allows us to apply the theory of Gröbner bases to
broader noncommutative algebras including the Steenrod algebra more
effectively.

We define a noncommutative Gröbner basis theory on a class of algebras called
filtered-commutative algebras (Definition 2.1). The main results are the
following.

######  Theorem 1.1 (Algorithm 4.5).

Given a finite generating set $H$ ($0\notin H$) of a left ideal $J$ of a
filtered-commutative algebra $A$, there is a generalized Buchberger’s
algorithm that expands $H$ to a Gröbner basis of $J$.

######  Theorem 1.2 (Algorithm 7.3).

Let $N=A^{r}/M$ be a graded left module over a filtered-commutative graded
algebra $A$ where $M$ is a left submodule of $A^{r}$. There is an algorithm
that constructs the first $s+1$ terms $F_{0},\dots,F_{s}$ of a free
$A$-resolution

$\cdots\to
F_{s}\xrightarrow{d_{s}}\cdots\xrightarrow{d_{3}}F_{2}\xrightarrow{d_{2}}F_{1}\xrightarrow{d_{1}}F_{0}=A^{r}\xrightarrow{\epsilon}N$

for any $s$.

The algorithms above have many applications and we focus on developing an
algorithm for computing $\mathrm{Ext}$ groups which is important in
homological algebra and algebraic topology. We then apply the algorithm to the
mod 2 Steenrod algebra ${\mathscr{A}}$ which yields the following
computational result.

######  Theorem 1.3.

The bigraded algebra

$\bigoplus_{t\leq
261}\mathrm{Ext}_{{\mathscr{A}}}^{s,t}({\mathbb{F}}_{2},{\mathbb{F}}_{2})$

in total degrees up to 261 is an algebra with 2914 indecomposables, 23822
basis elements and 227498 indecomposable relations. The complete charts are in
given in [13].

This algebra is the $E_{2}$ page of the Adams spectral sequence converging to
the stable homotopy groups of spheres completed at the prime 2 (See [1]). It
plays a fundamental role in the stable homotopy theory and is related to many
important problems such as the Hopf invariant one problem and the Kervaire
invariant one problem. The computation of the stable homotopy groups of
spheres relies on these machine outputs for the Adams $E_{2}$ page. We refer
the interested readers to Isaksen, Wang and Xu [6] for the most up to date
calculation.

Previously, the most extensive and publicly available calculation of
$\mathrm{Ext}_{{\mathscr{A}}}^{*,*}({\mathbb{F}}_{2},{\mathbb{F}}_{2})$ is
done by Bruner and Rognes [4], who compute the Ext up to dimension of 200.
There are other computer programs made by Nassau [18] and Wang [21]. Our new
algorithm is very efficient in both memory and time, which can compute the
resolution in the range of 200 within one day on a personal computer and we
spent 88+63 days to obtain the resolution and products for Theorem 1.3 on a
64-core CPU machine. This extends their calculation by a few magnitudes. The
interested reader can find the latest implementation of the algorithm on
Github [11], which can run twice as fast as the old version does for Theorem
1.3.

##  2\. Filtered-Commutative Algebras

Let $k$ be any field and $A$ an algebra defined below.

######  Definition 2.1.

An algebra $A$ over $k$ is called a _(decreasingly-) filtered-commutative
algebra_ if it satisfies the following conditions.

  1. (1)

The algebra $A$ is equipped with a filtration of ideals

$A=F_{0}A\supset F_{1}A\supset F_{2}A\supset\cdots$

such that

$F_{p}A\cdot F_{q}A\subset F_{p+q}A$

and $F_{{p_{\mathrm{nul}}}}A=0$ for some number ${p_{\mathrm{nul}}}>0$.

  2. (2)

The associated graded algebra $\mathrm{gr}(A)$ defined by

$\mathrm{gr}_{p}(A)=F_{p}A/F_{p+1}A$

is commutative.

######  Definition 2.2.

We say that a nonzero element $a\in A$ projects to $f\in\mathrm{gr}_{p}(A)$,
if $p$ is the maximal number such that $a\in F_{p}A$ and $f$ is the image of
$a$ via the map $F_{p}A\to F_{p}A/F_{p+1}A$. We write

$v(a)=p\text{ and }\mathrm{pr}(a)=f.$

If $a$ is zero, we define

$v(0)=\infty\text{ and }\mathrm{pr}(0)=0.$

We also call $a$ a _lift_ of $f$.

It is easy to see that another element $a^{\prime}\in A$ projects to the same
element $f\in\mathrm{gr}_{p}(A)$ if and only if $a-a^{\prime}\in F_{p+1}A$.
The projection map is _not_ a linear map between vector spaces since
$\mathrm{pr}(a-a^{\prime})$ here could be nonzero.

######  Proposition 2.3.

For nonzero elements $a,b\in A$, we have

$v(ab)\geq v(a)+v(b)$

or equivalently,

$|\mathrm{pr}(ab)|\geq|\mathrm{pr}(a)|+|\mathrm{pr}(b)|$

where $|\cdot|$ is the degree of elements of $\mathrm{gr}(A)$. The equality
holds if and only if

$\mathrm{pr}(a)\mathrm{pr}(b)\neq 0$

in $\mathrm{gr}(A)$.

###### Proof.

This is the direct consequence of the condition $F_{p}A\cdot F_{q}A\subset
F_{p+q}A$. ∎

The condition $F_{{p_{\mathrm{nul}}}}A=0$ in Definition 2.1 makes sure that a
basis of $\mathrm{gr}(A)$ can lift to a basis of $A$. More precisely, if
${\mathscr{B}}=\\{m_{i}\\}$ is a $k$-basis of $\mathrm{gr}(A)$, and
$\tilde{m}_{i}\in A$ projects to $m_{i}$, then
$\tilde{\mathscr{B}}=\\{\tilde{m}_{i}\\}$ is a $k$-basis of $A$.

######  Remark 2.4.

The definition of a filtered-commutative algebra is a generalization of
commutative algebras since if $A$ is commutative, we can filter it with

$A=F_{0}A\subset F_{1}A=\\{0\\}.$

It is obvious that $A$ satisfies the conditions in Definition 2.1. There are
also non-commutative examples. The important ones that we will study in this
paper are the truncated Steenrod algebra at the prime 2.

From now on, we study filtered-commutative algebras $A$ such that
$\mathrm{gr}(A)$ is finitely generated. Hence the associated graded algebra
can be presented by

$\mathrm{gr}(A)=k[x_{1},\dots,x_{n}]/I$

for some $n$ and some ideal $I$ of the polynomial ring
$P=k[x_{1},\dots,x_{n}]$. Since $\mathrm{gr}(A)$ is graded, we assume that
$x_{i}$ and $I$ are homogeneous. The degree of a homogeneous element $f\in P$
is denoted by $|f|$.

##  3\. Bases and Monomial Orderings

In order to develop a theory of Gröbner bases over $A$, we want to choose a
basis for $A$ and a well-order on the basis. Since $\mathrm{gr}(A)$ is a
commutative algebra, we will do it on $\mathrm{gr}(A)$ first and then lift it
to $A$.

######  Definition 3.1.

A _degree-reversed admissible monomial ordering_ for the graded polynomial
ring $P=k[x_{1},\dots,x_{n}]$ is a total ordering on the monomials such that
for any monomials $M,N,L$,

  1. (1)

$M\leq N\Longleftrightarrow ML\leq NL$,

  2. (2)

$|L|=0\Longrightarrow M\leq ML$.

  3. (3)

$|M|>|N|\Longrightarrow M<N$.

######  Remark 3.2.

This is not a conventional monomial ordering because it is not a well-order on
all monomials. However, we have $F_{p_{\mathrm{nul}}}A=0$ for some
${p_{\mathrm{nul}}}>0$ and hence $\mathrm{gr}_{i}(A)=0$ for all
$i\geq{p_{\mathrm{nul}}}$. The conditions (1)(2) make sure that it is a well-
order in each degree, and the condition (3) makes sure that it is a well-order
on all monomials in degrees less than ${p_{\mathrm{nul}}}$.

Assume that $P=k[x_{1},\dots,x_{n}]$ is equipped with a degree-reversed
admissible monomial ordering defined above. We denote the leading monomial of
$f\in P$ by $\mathrm{LM}(f)$, which is the largest monomial in $f$. The
leading term $\mathrm{LT}(f)$ is the leading monomial together with its
coefficient in $f$. Recall the following definition of a commutative Gröbner
basis.

######  Definition 3.3.

A Gröbner basis $G$ of an ideal $I$ of $P$ is a finite generating set of $I$
such that the following two ideals of $P$ are equal:

$(\mathrm{LM}(f):f\in I)=(\mathrm{LM}(g):g\in G).$

Assume that $G$ is a Gröbner basis of the ideal $I$. Let ${\mathscr{M}}$ be
the set of all monomials in $P$. The definition of Gröbner bases indicates
that the set

${\mathscr{B}}=\\{m\in{\mathscr{M}}:\mathrm{LM}(g)\nmid m\text{ for all }g\in
G\\}$

(modulo $I$) is a basis of $\mathrm{gr}(A)=P/I$ as a vector space. Note that
if $m\in{\mathscr{B}}$, then all monomials that divide $m$ also belong to
${\mathscr{B}}$ by definition.

######  Definition 3.4.

For any nonzero $f\in\mathrm{gr}(A)=P/I$, it can be uniquely written as

$f=c_{1}m_{1}+\cdots+c_{l}m_{l}\mod I$

where $c_{i}\in k$, $m_{i}\in{\mathscr{B}}$ and $m_{1}>\cdots>m_{l}$. The
leading monomial of $f$ is defined to be $\mathrm{LM}_{\mathrm{gr}}(f)=m_{1}$,
while the leading term of $f$ is defined to be
$\mathrm{LT}_{\mathrm{gr}}(f)=c_{1}m_{1}$.

Note that if $m\notin{\mathscr{B}}$, then $\mathrm{LM}_{\mathrm{gr}}(m)<m$.

We choose and fix $X_{i}\in A$ such that $X_{i}$ projects to $x_{i}$ in the
associated graded algebra for each $i$. Then for $m=x_{1}^{r_{1}}\cdots
x_{n}^{r_{n}}\in{\mathscr{B}}$, the product

$\tilde{m}=X_{1}^{r_{1}}\cdots X_{n}^{r_{n}}\in A$

projects to $m+I$ since $m+I$ is non-trivial in $\mathrm{gr}(A)=P/I$. Hence
the set

$\tilde{\mathscr{B}}=\\{\tilde{m}:m\in{\mathscr{B}}\\}$

is a basis of $A$. We order $\tilde{\mathscr{B}}$ the same way as we order
${\mathscr{B}}$ via the lifting. Note that both ${\mathscr{B}}$ and
$\tilde{\mathscr{B}}$ are well-ordered.

######  Definition 3.5.

For any $f\in\mathrm{gr}(A)$, we write

$f=c_{1}m_{1}+\cdots+c_{l}m_{l}\mod I$

where $c_{i}\in k$ and $m_{i}\in{\mathscr{B}}$. We define

$\tilde{f}=c_{1}\tilde{m}_{1}+\cdots+c_{l}\tilde{m}_{l}\in A$

which is a lift of $f$. Sometimes we also write $\ell(f)=\tilde{f}$.

######  Definition 3.6.

For any nonzero $a\in A$, we can write $a$ in the form of

$a=c_{1}\tilde{m}_{1}+\cdots+c_{l}\tilde{m}_{l}$

where $c_{i}\in k$, $m_{i}\in{\mathscr{B}}$ and $m_{1}>\cdots>m_{l}$. We call
$\mathrm{LM}_{A}(a)=\tilde{m}_{1}\in\tilde{\mathscr{B}}$ the _leading
monomial_ of $a$, and $\mathrm{LT}_{A}(a)=c_{1}\tilde{m}_{1}$ the _leading
term_ of $a$. For convenience we also define
$\mathrm{LM}_{\\!{\mathscr{B}}}(a)=m_{1}\in{\mathscr{B}}$ and we see that
$\mathrm{LM}_{\\!{\mathscr{B}}}=\mathrm{pr}\circ\mathrm{LM}_{A}$.

######  Proposition 3.7.

For any nonzero $a\in A$, we have

$\mathrm{LM}_{\\!{\mathscr{B}}}(a)=\mathrm{pr}(\mathrm{LM}_{A}(a))=\mathrm{LM}_{\mathrm{gr}}(\mathrm{pr}(a))$

or equivalently

$\mathrm{LM}_{A}=\ell\circ\mathrm{LM}_{\mathrm{gr}}\circ\mathrm{pr}$

###### Proof.

If

$a=c_{1}\tilde{m}_{1}+\cdots+c_{l}\tilde{m}_{l}$

where $c_{i}\in k$, $m_{i}\in{\mathscr{B}}$ and

$m_{1}>\cdots>m_{l},$

then it is clear that $\mathrm{pr}(a)=\sum\limits_{\begin{subarray}{c}1\leq
i\leq l\\\ |m_{i}|=|m_{1}|\end{subarray}}m_{i}$. Therefore
$\mathrm{LM}_{\mathrm{gr}}(\mathrm{pr}(a))=m_{1}$. ∎

The following propositions show that the ordering on $\tilde{\mathscr{B}}$ is
“admissible” meaning that it behaves well with the multiplication. For our
convenience, when the context is clear, sometimes we omit “modulo $I$” and
consider some elements of $P$ as elements of $\mathrm{gr}(A)=P/I$.

######  Proposition 3.8.

Assume that $m_{1},m_{2}\in{\mathscr{B}}$ and $\tilde{m}_{1}\tilde{m}_{2}\neq
0$. We have

$\mathrm{LM}_{\\!{\mathscr{B}}}(\tilde{m}_{1}\tilde{m}_{2})\leq m_{1}m_{2}.$

The equality holds if and only if $m_{1}m_{2}\in{\mathscr{B}}$.

###### Proof.

By the previous proposition, we have

$\mathrm{LM}_{\\!{\mathscr{B}}}(\tilde{m}_{1}\tilde{m}_{2})=\mathrm{LM}_{\mathrm{gr}}(\mathrm{pr}(\tilde{m}_{1}\tilde{m}_{2})).$

If $m_{1}m_{2}$ is trivial in $\mathrm{gr}(A)$, then
$|\mathrm{pr}(\tilde{m}_{1}\tilde{m}_{2})|>|m_{1}m_{2}|$. Therefore

$\mathrm{LM}_{\mathrm{gr}}(\mathrm{pr}(\tilde{m}_{1}\tilde{m}_{2}))<m_{1}m_{2}.$

If $m_{1}m_{2}$ is nontrivial in $\mathrm{gr}(A)$, we have

$\mathrm{LM}_{\mathrm{gr}}(\mathrm{pr}(\tilde{m}_{1}\tilde{m}_{2}))=\mathrm{LM}_{\mathrm{gr}}(m_{1}m_{2})\leq
m_{1}m_{2}.$

The last equality holds if and only $m_{1}m_{2}\in{\mathscr{B}}$. ∎

This proposition directly implies the following.

######  Corollary 3.9.

Assume $a\in A$, $\mathrm{LM}_{A}(a)=\tilde{m}$ and $q\in{\mathscr{B}}$. If
$qm\in{\mathscr{B}}$, then $\mathrm{LM}_{\\!{\mathscr{B}}}(\tilde{q}a)=qm$.
Otherwise $\mathrm{LM}_{\\!{\mathscr{B}}}(\tilde{q}a)<qm$.

##  4\. Gröbner bases over Filtered-Commutative Algebras

Let $A$ be a filtered-commutative algebra and we proceed with notations
defined in the previous section. We focus on left ideals of $A$ first. We will
consider left modules over $A$ in the next section.

######  Definition 4.1.

A Gröbner basis $H$ of a left ideal $J$ of $A$ is a finite generating set of
$J$ such that the following two ideals of $P$ are equal:

$(\mathrm{LM}_{\\!{\mathscr{B}}}(a):a\in
J)=(\mathrm{LM}_{\\!{\mathscr{B}}}(h):h\in H).$

In order to give an algorithm that calculates a Gröbner basis of $J\subset A$
starting from a given generating set of $J$, we need to define reductions in
$A$.

######  Definition 4.2.

Given $a,b\in A$, we write

$a=c_{1}\tilde{m}_{1}+\cdots+c_{l}\tilde{m}_{l}$

where $c_{i}\in k$, $m_{i}\in{\mathscr{B}}$ and $m_{1}>\cdots>m_{l}$. Let
$c\tilde{m}=\mathrm{LT}_{A}(b)$ for some $c\in k$ and $m\in{\mathscr{B}}$. One
says that $a$ is _reducible_ by $b$ if $m_{i}$ is divisible by $m$ for some
$i$. In this case we choose the smallest $i$ and define the _one-step
reduction_ of $a$ by $b$ by

$\mathrm{red}_{1}(a,b)=a-\frac{c_{i}}{c}\widetilde{\left(\frac{m_{i}}{m}\right)}b.$

Note that compared with $a$, $\mathrm{red}_{1}(a,b)$ replaces
$c_{i}\tilde{m}_{i}$ in $a$ with other summands strictly less than
$\tilde{m}_{i}$ since

$\mathrm{LT}_{\mathrm{gr}}(\mathrm{pr}(\frac{c_{i}}{c}\widetilde{\left(\frac{m_{i}}{m}\right)}b))=\frac{c_{i}}{c}\frac{m_{i}}{m}cm=c_{i}m_{i}.$

######  Definition 4.3.

For $a\in A$ and a finite ordered subset $H\subset A$, we say that $a$ is
_reducible_ by $H$ if $a$ is reducible by some $h\in H$. In this case we
assume that $\tilde{m}$ is the largest summand of $a$ that is reducible by
$H$, and $h\in H$ is the first element of $H$ that reduces $\tilde{m}$. We
define the one-step reduction of $a$ by $H$ by

$\mathrm{red}_{1}(a,H)=\mathrm{red}_{1}(a,h).$

We replace $a$ with $\mathrm{red}_{1}(a,H)$ and iterate this until $a$ is not
reducible by $H$. This will terminate because the monomial ordering is well-
ordered on $\tilde{\mathscr{B}}$. We call the final outcome the _reduction of
$a$ by $H$_, denoted by $\mathrm{red}(a,H)$.

######  Remark 4.4.

By the definition of reductions, if $\mathrm{red}(a,H)=0$, we can write

$a=c_{1}\tilde{m}_{1}h_{1}+\cdots+c_{l}\tilde{m}_{l}h_{l}$

where $c_{i}\in k$, $m_{i}\in{\mathscr{B}}$ and $h_{i}\in H$ such that
$m_{i}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{i})\in{\mathscr{B}}$ and

$m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})>\cdots>m_{l}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{l}).$

We can see
$\mathrm{LM}_{\\!{\mathscr{B}}}(a)=m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$.

The following is a generalized Buchberger’s algorithm that calculates a
Gröbner basis of an ideal of $A$.

######  Algorithm 4.5.

Given a finite ordered generating set $H$ ($0\notin H$) of a left ideal $J$ of
$A$, we can expand $H$ to a Gröbner basis of $J$ by doing the following

  1. (1)

For $a\in H$ and $g\in G$, let $L$ be the least common multiple

$L=\mathrm{lcm}(\mathrm{LM}_{\\!{\mathscr{B}}}(a),\mathrm{LM}(g))$

and

$q=\frac{L}{\mathrm{LM}_{\\!{\mathscr{B}}}(a)}.$

If $\mathrm{red}(\tilde{q}a,H)$ is nontrivial, append it to $H$.

  2. (2)

For $a,b\in H$, let

$L=\mathrm{lcm}(\mathrm{LM}_{\\!{\mathscr{B}}}(a),\mathrm{LM}_{\\!{\mathscr{B}}}(b))$

and

$t_{1}=\frac{L}{\mathrm{LT}_{\mathrm{gr}}(\mathrm{pr}(a))},~{}t_{2}=\frac{L}{\mathrm{LT}_{\mathrm{gr}}(\mathrm{pr}(b))}.$

If $\mathrm{red}(\tilde{t}_{1}a-\tilde{t}_{2}b,H)$ is nontrivial, append it to
$H$.

  3. (3)

Repeat (1)(2) until no more elements can be added to $H$.

We verify the correctness of the algorithm by the following two propositions.

######  Proposition 4.6.

Algorithm 4.5 always terminates.

###### Proof.

It is clear that the new elements added to $H$ belong to $J$. Since each new
element is reduced before it is added to $H$, the ideal

$(\mathrm{LM}_{\\!{\mathscr{B}}}(h):h\in H)$

of $P$ will be strictly larger when the element is added. This cannot continue
infinitely because $P=k[x_{1},\dots,x_{n}]$ is a Noetherian ring. ∎

######  Proposition 4.7.

When Algorithm 4.5 terminates, for any $a\in J$, we have

$\mathrm{LM}_{\\!{\mathscr{B}}}(a)\in(\mathrm{LM}_{\\!{\mathscr{B}}}(h):h\in
H).$

###### Proof.

Since $H$ is a generating set of $J$, it suffices to prove that for all
$c_{i}\in k$, $m_{i}\in{\mathscr{B}}$ and $h_{i}\in H$, $1\leq i\leq l$, such
that

$m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})\geq\cdots\geq
m_{l}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{l}),$

the proposition is true for

(4.1) $a=c_{1}\tilde{m}_{1}h_{1}+\cdots+c_{l}\tilde{m}_{l}h_{l}.$

Without loss of generality, we assume that the leading coefficient of any
$h\in H$ is one which implies that $\mathrm{LT}_{A}(h)=\mathrm{LM}_{A}(h)$.

If $l=0$, the proof is done since this only happens when $a=0$.

If $m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})\notin{\mathscr{B}}$, then there
exists $g\in G$ such that
$\mathrm{LM}(g)~{}|~{}m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$. Let

$L=\mathrm{lcm}(\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1}),\mathrm{LM}(g))$

and

$q=\frac{L}{\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})}.$

We have $q|m_{1}$ and by the termination of Algorithm 4.5,

$\mathrm{red}(\tilde{q}h_{1},H)=0.$

Thus by Remark 4.4 we can write

$\tilde{q}h_{1}=c_{1}^{\prime}\tilde{m}_{1}^{\prime}h_{1}^{\prime}+\cdots+c_{s}^{\prime}\tilde{m}_{s}^{\prime}h_{s}^{\prime}$

for some $c_{i}^{\prime}\in k$, $m_{i}^{\prime}\in{\mathscr{B}}$ and
$h_{i}^{\prime}\in H$ such that

$m_{1}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1}^{\prime})>\cdots>m_{s}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{s}^{\prime}).$

We have

$m_{j}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{j}^{\prime})\leq
m_{1}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1}^{\prime})=\mathrm{LM}_{\\!{\mathscr{B}}}(\tilde{q}h_{1})<q\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$

for all $1\leq j\leq s$.

Now we consider

(4.2)
$\displaystyle\begin{split}\tilde{m}_{1}h_{1}&=\Big{(}\tilde{m}_{1}-\widetilde{\left(\frac{m_{1}}{q}\right)}\tilde{q}\Big{)}h_{1}+\widetilde{\left(\frac{m_{1}}{q}\right)}(\tilde{q}h_{1})\\\
&=\Big{(}\tilde{m}_{1}-\widetilde{\left(\frac{m_{1}}{q}\right)}\tilde{q}\Big{)}h_{1}+\sum_{j=1}^{s}c_{j}^{\prime}\widetilde{\left(\frac{m_{1}}{q}\right)}\tilde{m}_{j}^{\prime}h_{j}^{\prime}.\end{split}$

Since $\mathrm{gr}(A)$ is commutative, we have

$v\Big{(}\tilde{m}_{1}-\widetilde{\left(\frac{m_{1}}{q}\right)}\tilde{q}\Big{)}>v(\tilde{m}_{1}).$

Thus

$\mathrm{LM}_{\\!{\mathscr{B}}}\Big{(}\tilde{m}_{1}-\widetilde{\left(\frac{m_{1}}{q}\right)}\tilde{q}\Big{)}\cdot\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})<m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1}).$

We also have

$\displaystyle\mathrm{LM}_{\\!{\mathscr{B}}}\Big{(}\widetilde{\left(\frac{m_{1}}{q}\right)}\tilde{m}_{j}^{\prime}\Big{)}\cdot\mathrm{LM}_{\\!{\mathscr{B}}}(h_{j}^{\prime})$
$\displaystyle\leq\frac{m_{1}}{q}\cdot
m_{j}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{j}^{\prime})$
$\displaystyle<\frac{m_{1}}{q}\cdot q\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$
$\displaystyle=m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$

for all $1\leq j\leq s$. The above two equalities and (4.2) show that
$\tilde{m}_{1}h_{1}$ can be rewritten as a linear combination of elements in
the form of $\tilde{m}h$ where $m\in{\mathscr{B}}$, $h\in H$ and
$m\mathrm{LM}_{\\!{\mathscr{B}}}(h)<m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$.
We can keep doing the rewriting on (4.1) as long as
$m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})\notin{\mathscr{B}}$ and this has
to stop at some point because
$|m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})|<2{p_{\mathrm{nul}}}$ and the
monomial ordering is always a well-order on monomials up to a finite degree.

Now we can always assume that
$m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})\in{\mathscr{B}}$ on (4.1). If
$l>1$ and

$m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})=m_{2}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{2}),$

we can rewrite (4.1) in a way similar to the previous part of this proof. In
fact, let

$L=\mathrm{lcm}(\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1}),\mathrm{LM}_{\\!{\mathscr{B}}}(h_{2}))$

and

$q_{1}=\frac{L}{\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})},~{}q_{2}=\frac{L}{\mathrm{LM}_{\\!{\mathscr{B}}}(h_{2})}.$

It is easy to see that there exists $m^{\prime}\in{\mathscr{B}}$ such that
$m_{1}=m^{\prime}q_{1}$ and $m_{2}=m^{\prime}q_{2}$. By the termination of
Algorithm 4.5,

$\mathrm{red}(\tilde{q}_{1}h_{1}-\tilde{q}_{2}h_{2},H)=0.$

Thus we can write

$\tilde{q}_{1}h_{1}-\tilde{q}_{2}h_{2}=c_{1}^{\prime}\tilde{m}_{1}^{\prime}h_{1}^{\prime}+\cdots+c_{s}^{\prime}\tilde{m}_{s}^{\prime}h_{s}^{\prime}$

for some $c_{i}^{\prime}\in k$, $m_{i}^{\prime}\in{\mathscr{B}}$ and
$h_{i}^{\prime}\in H$ such that

$m_{1}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1}^{\prime})>\cdots>m_{s}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{s}^{\prime}).$

We have

$m_{j}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{j}^{\prime})\leq
m_{1}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1}^{\prime})=\mathrm{LM}_{\\!{\mathscr{B}}}(\tilde{q}_{1}h_{1}-\tilde{q}_{2}h_{2})<q_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$

for all $1\leq j\leq s$.

Now we consider

(4.3) $\displaystyle\begin{split}&\tilde{m}_{1}h_{1}-\tilde{m}_{2}h_{2}\\\
=&\Big{(}\tilde{m}_{1}-\tilde{m}^{\prime}\tilde{q}_{1}\Big{)}h_{1}-\Big{(}\tilde{m}_{2}-\tilde{m}^{\prime}\tilde{q}_{2}\Big{)}h_{2}+\tilde{m}^{\prime}(\tilde{q}_{1}h-\tilde{q}_{2}h)\\\
=&\Big{(}\tilde{m}_{1}-\tilde{m}^{\prime}\tilde{q}_{1}\Big{)}h_{1}-\Big{(}\tilde{m}_{2}-\tilde{m}^{\prime}\tilde{q}_{2}\Big{)}h_{2}+\sum_{j=1}^{s}c_{j}^{\prime}\tilde{m}^{\prime}\tilde{m}_{j}^{\prime}h_{j}^{\prime}.\end{split}$

Again, for $i=1,2$ we have

$v\Big{(}\tilde{m}_{i}-\tilde{m}^{\prime}\tilde{q}_{i}\Big{)}>v(\tilde{m}_{i}).$

Thus

$\mathrm{LM}_{\\!{\mathscr{B}}}\Big{(}\tilde{m}_{i}-\tilde{m}^{\prime}\tilde{q}_{i}\Big{)}\cdot\mathrm{LM}_{\\!{\mathscr{B}}}(h_{i})<m_{i}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{i})=m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1}).$

We also have

$\displaystyle\mathrm{LM}_{\\!{\mathscr{B}}}\Big{(}\tilde{m}^{\prime}\tilde{m}_{j}^{\prime}\Big{)}\cdot\mathrm{LM}_{\\!{\mathscr{B}}}(h_{j}^{\prime})$
$\displaystyle\leq\frac{m_{1}}{q}\cdot
m_{j}^{\prime}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{j}^{\prime})$
$\displaystyle<\tilde{m}^{\prime}\cdot q\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$
$\displaystyle=m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$

for all $1\leq j\leq s$. The above two equalities and (4.3) show that
$\tilde{m}_{1}h_{1}$ can be rewritten as a linear combination of
$\tilde{m}_{2}h_{2}$ and elements in the form of $\tilde{m}h$ where
$m\in{\mathscr{B}}$, $h\in H$ and
$m\mathrm{LM}_{\\!{\mathscr{B}}}(h)<m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})$.
We can keep doing the rewriting on (4.1) as long as
$m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})=m_{2}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{2})$
and this will stop at some point.

Eventually we get $l=0$ or
$m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})\in{\mathscr{B}}$ and
$m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})>m_{2}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{2})$
(when $l>1$). In the second case

$\mathrm{LM}_{\\!{\mathscr{B}}}(a)=m_{1}\mathrm{LM}_{\\!{\mathscr{B}}}(h_{1})\in(\mathrm{LM}_{\\!{\mathscr{B}}}(h):h\in
H).$

∎

The Gröbner bases over $A$ behave very similarly to commutative Gröbner bases.
It is quite straightforward to see that $H$ is a Gröbner bases of $J\subset A$
if and only if $\mathrm{red}(a,H)=0$ for any $a\in J$, and the set

$\\{\tilde{m}\in\tilde{\mathscr{B}}:\mathrm{LM}_{\\!{\mathscr{B}}}(h)\nmid
m\text{ for all }h\in H\\}$

(modulo $J$) is a $k$-basis of the left $A$-module $A/J$.

##  5\. Modules

In previous sections, we study the Gröbner bases of left ideals of $A$. Now we
consider a finitely generated left module $N$ over $A$. We can find a number
$r$ and a left submodule $M$ of $A^{r}$ such that $N\cong A^{r}/M$. Therefore
we can study left submodules of $A^{r}$ in order to study finitely generated
left modules over $A$.

Consider the truncated graded ring
${\mathbb{A}}={\mathbb{A}}_{0}\oplus{\mathbb{A}}_{1}=A\oplus A^{r}$, where the
multiplication is given by

$(a_{1},x_{1})\cdot(a_{2},x_{2})=(a_{1}a_{2},a_{1}x_{2}+a_{2}x_{1})$

for $a_{i}\in A$, $x_{i}\in A^{r}$, $i=1,2$. We can see that left submodules
of $A^{r}$ over $A$ are in one-to-one correspondence to left ideals of
${\mathbb{A}}$ that are contained in ${\mathbb{A}}_{1}$. We can filter
${\mathbb{A}}$ by

$F_{p}{\mathbb{A}}=F_{p}A\oplus(F_{p}A)^{r}\subset{\mathbb{A}}.$

Then ${\mathbb{A}}$ is actually a filtered-graded commutative algebra and

$\mathrm{gr}({\mathbb{A}})=\mathrm{gr}(A)\oplus\mathrm{gr}(A)^{r}\cong
k[x_{1},\dots,x_{n},e_{1},\dots,e_{r}]/(I,e_{i}e_{j}:1\leq i\leq j\leq r)$

where $\\{\tilde{e}_{i}\\}$ is the $A$-basis of the free $A$-module
${\mathbb{A}}_{1}=A^{r}$ and $\mathrm{pr}(\tilde{e}_{i})=e_{i}$.

Since $M\subset{\mathbb{A}}_{1}$, we are only concerned with monomials in the
following set

${\mathbb{B}}=\\{me_{i}:m\in{\mathscr{M}},1\leq i\leq r\\}.$

A monomial ordering on those monomials should satisfy

$m_{1}e_{i}<m_{2}e_{i}\Longleftrightarrow m_{1}<m_{2}\text{ for all }i.$

One example of such orderings could be

(5.1) $m_{1}e_{i}<m_{2}e_{j}\Longleftrightarrow i>j\text{ or }(i=j\text{ and
}m_{1}<m_{2}).$

There are many other examples but we assume that we have chosen one of them
for ${\mathbb{B}}$. Note that the set
$\tilde{\mathbb{B}}=\\{\tilde{m}\tilde{e}_{i}:m\in{\mathscr{M}},1\leq i\leq
r\\}$ is a $k$-basis of $A^{r}$. If $\tilde{m}\tilde{e}_{i}$ is the leading
monomial of $x\in A^{r}$, we write $\mathrm{LM}_{{\mathbb{B}}}(x)=me_{i}$.

######  Definition 5.1.

A Gröbner basis $H$ of a left submodule $M\subset A^{r}$ over $A$ is a Gröbner
basis of $M\subset{\mathbb{A}}_{1}$ as a left ideal of the filtered-
commutative algebra ${\mathbb{A}}$.

If we expand the definition in terms of $A$, we get the following.

######  Proposition 5.2.

A Gröbner basis $H$ of a left submodule $M\subset A^{r}$ over $A$ is a finite
generating set of $M$ such that the following two ideals of
$k[x_{1},\dots,x_{n},e_{1},\dots,e_{r}]$ are equal:

$(\mathrm{LM}_{{\mathbb{B}}}(x):x\in M)=(\mathrm{LM}_{{\mathbb{B}}}(h):h\in
H).$

Since $M\subset A^{r}$ can be considered as an ideal of ${\mathbb{A}}$,
Algorithm 4.5 can be used to compute the Gröbner bases of $M$ if we replace
$A$ with ${\mathbb{A}}$. Here we rewrite the algorithm in terms of $A$ and the
auxiliary symbols $e_{1},\dots,e_{r}$.

######  Algorithm 5.3.

Given a finite ordered generating set $H$ ($0\notin H$) of a left submodule
$M\subset A^{r}$ over $A$, we can expand $H$ to a Gröbner basis of $M$ by
doing the following.

  1. (1)

For $a\in H$ and $g\in G$, let $L$ be the least common multiple

$L=\mathrm{lcm}(\mathrm{LM}_{{\mathbb{B}}}(a),\mathrm{LM}(g))$

and

$q=\frac{L}{\mathrm{LM}_{{\mathbb{B}}}(a)}.$

If $\mathrm{red}(\tilde{q}a,H)$ is nontrivial, append it to $H$.

  2. (2)

For $a,b\in H$ such that $\mathrm{LM}_{{\mathbb{B}}}(a)$ and
$\mathrm{LM}_{{\mathbb{B}}}(b)$ contain the same $e_{i}$ factor, let

$L=\mathrm{lcm}(\mathrm{LM}_{{\mathbb{B}}}(a),\mathrm{LM}_{{\mathbb{B}}}(b))$

and

$t_{1}=\frac{L}{\mathrm{LT}_{\mathrm{gr}({\mathbb{A}})}(\mathrm{pr}(a))},~{}t_{2}=\frac{L}{\mathrm{LT}_{\mathrm{gr}({\mathbb{A}})}(\mathrm{pr}(b))}.$

If $\mathrm{red}(\tilde{t}_{1}a-\tilde{t}_{2}b,H)$ is nontrivial, append it to
$H$.

  3. (3)

Repeat (1)(2) until no more elements can be added to $H$.

##  6\. Syzygies

######  Definition 6.1.

Let $(x_{1},\cdots,x_{s})$ be a tuple of elements of $A^{r}$.

  1. (1)

A _syzygy_ of $(x_{1},\dots,x_{s})$ is a tuple $(a_{1},\dots,a_{s})\in A^{s}$
such that $a_{1}x_{1}+\cdots+a_{s}x_{s}=0$.

  2. (2)

The set of all syzygies of $(x_{1},\cdots,x_{s})$ is call the _(first) syzygy
module_ of $(x_{1},\cdots,x_{s})$, denoted by
$\mathrm{Syz}(x_{1},\cdots,x_{s})$.

It is obvious that $\mathrm{Syz}(x_{1},\cdots,x_{s})$ is a left submodule of
$A^{s}$. Our goal in this section is to find a generating set of
$\mathrm{Syz}(x_{1},\cdots,x_{s})$.

######  Definition 6.2.

Let $H=(h_{1},\dots,h_{s})$ be an ordered Gröbner basis of $M\subset A^{r}$.
For $1\leq i\leq s$ and $g\in G$, let

$L=\mathrm{lcm}(\mathrm{LM}_{{\mathbb{B}}}(h_{i}),\mathrm{LM}(g))$

and

$q=\frac{L}{\mathrm{LM}_{{\mathbb{B}}}(h_{i})}.$

We have $\mathrm{red}(\tilde{q}h_{i},H)=0$ and it expands to

$\tilde{q}h_{i}=a_{1}h_{1}+\cdots+a_{s}h_{s}$

for some $a_{l}\in A$, $1\leq l\leq s$. This implies that

$(-a_{1},\dots,-a_{i-1},\tilde{q}-a_{i},-a_{i+1},\dots,-a_{s})$

is a syzygy of $H$. We denote this syzygy of $H$ by $\sigma_{i,g}$.

######  Definition 6.3.

Let $H=(h_{1},\dots,h_{s})$ be an ordered Gröbner basis of $M\subset A^{r}$.
For $1\leq i<j\leq s$, let

$L=\mathrm{lcm}(\mathrm{LM}_{{\mathbb{B}}}(h_{i}),\mathrm{LM}_{{\mathbb{B}}}(h_{j}))$

and

$t_{i}=\frac{L}{\mathrm{LT}_{\mathrm{gr}({\mathbb{A}})}(\mathrm{pr}(h_{i}))},~{}t_{j}=\frac{L}{\mathrm{LT}_{\mathrm{gr}({\mathbb{A}})}(\mathrm{pr}(h_{j}))}.$

We have $\mathrm{red}(\tilde{t}_{i}h_{i}-\tilde{t}_{j}h_{j},H)=0$ and it
expands to

$\tilde{t}_{i}h_{i}-\tilde{t}_{j}h_{j}=a_{1}h_{1}+\cdots+a_{s}h_{s}$

for some $a_{l}\in A$, $1\leq l\leq s$. This implies that

$(-a_{1},\dots,-a_{i-1},\tilde{t}_{i}-a_{i},a_{i+1},\dots,-a_{j-1},-\tilde{t}_{j}-a_{j},-a_{j+1},\dots,-a_{s})$

is a syzygy of $H$. We denote this syzygy of $H$ by $\sigma_{i,j}$.

The following proposition finds a generating set of
$\mathrm{Syz}(h_{1},\dots,h_{s})$ for a Gröbner basis $(h_{1},\dots,h_{s})$.

######  Theorem 6.4.

If $H=(h_{1},\dots,h_{s})$ is an ordered Gröbner basis of some left submodule
$M\subset A^{r}$, then the syzygy module $\mathrm{Syz}(H)$ is generated by the
following two sets of elements.

$\\{\sigma_{i,g}\\}_{1\leq i\leq s,g\in G},~{}\\{\sigma_{i,j}\\}_{1\leq i\leq
s,1\leq j\leq s}.$

###### Proof.

This actually follows from the proof of Proposition 4.7 when we replace $A$
with ${\mathbb{A}}$ and consider the case $a=0$ in (4.1). We can see that the
right-hand side of (4.1) becomes zero after we rewrite it by linear relations
between $H$ that correspond to $m\sigma_{i,g}$ or $m\sigma_{i,j}$ for some
$m\in{\mathscr{M}}$. ∎

For any tuple $X=(h_{1},\dots,h_{t})$ of elements of $A^{r}$, we can use the
generalized Buchberger’s algorithm to compute a Gröbner basis
$H=(h_{1},\dots,h_{s})$ of the submodule of $A^{r}$ generated by
$h_{1},\dots,h_{t}$ ($s\geq t$). Since all elements of $H$ belong to the
submodule, we can find a matrix $Q=\begin{pmatrix}I_{t}\\\
Q^{\prime}\end{pmatrix}\in M_{s\times t}(A)$ such that

$H^{T}=QX^{T}.$

Where $I_{t}$ is the $t\times t$ identity matrix and $(\cdot)^{T}$ is the
transposition of matrices.

######  Theorem 6.5.

If $S$ is a matrix such that the row vectors of $S$ generate the syzygy module
$\mathrm{Syz}(H)$, then the row vectors of $SQ$ generate $\mathrm{Syz}(X)$.

###### Proof.

Since $SQX^{T}=SH^{T}=0$ we know that the row vectors of $SQ$ belong to
$Syz(X)$. On the other hand, assume $vX^{T}=0$ for some row vector $v\in
R^{t}$. Let

$P=\begin{pmatrix}I_{t}&0\end{pmatrix}\in M_{t\times s}(A).$

Then we have $X^{T}=PX^{T}$ and $PQ=I_{t}$. Thus

$0=vX^{T}=(vPQ)X^{T}=vPH^{T}\implies vP\in\mathrm{Syz}(H).$

Therefore $vP$ lies in span of row vectors of $S$ and $v=vPQ$ lies in the span
of row vectors of $SQ$. ∎

Combining the two theorems above solves the computation of $\mathrm{Syz}(X)$
for any tuple $X$.

##  7\. Ext Groups

In this section, we further assume that $A=\oplus_{i\geq 0}A_{i}$ is a
connected graded algebra, which means that $A_{0}=k$. The degree of a
(homogeneous) element $a\in A$ is denoted by $\deg(a)$. We require the
filtration $F_{\bullet}A$ to be homogeneous. Thus the associated graded
algebra $\mathrm{gr}(A)$ has two gradings. To avoid confusion, the degree
function on $\mathrm{gr}(A)$ induced by the grading of $A$ is also denoted by
$\deg(\cdot)$ while the degree function induced by the filtration is denoted
by $|\cdot|$ as before.

Let $N=A^{r}/M$ be a graded left $A$-module. Here
$A^{r}=A\\{\tilde{v}_{i}:1\leq i\leq r\\}$ is a direct sum of shifts of $A$
where the degrees of basis $\deg(\tilde{v}_{i})$ are integers. The goal of
this section is to compute the Ext groups $\mathrm{Ext}^{*}_{A}(N,k)$ by
constructing a minimal free resolution of $N$. Most of the algorithms are
adapted from the theory of commutative Gröbner bases (See [8]). The only
differences are the steps that construct noncommutative Gröbner bases.

First we have to make sure that the number $r$ in the representation
$N=A^{r}/M$ is as small as possible. Let $A_{+}=\oplus_{i>0}A_{i}$ be the
“graded maximal ideal” of $A$. By Nakayama’s lemma, we see that a minimal
generating set of the graded left module $N$ of $A$ corresponds to a basis of
the $k$-vector space $N/A_{+}N$. Hence we can use the following algorithm to
minimize $r$.

######  Algorithm 7.1.

Let $N$ be a graded left submodule over $A$ with the following presentation

$N=A\\{\tilde{v}_{1},\dots,\tilde{v}_{r}\\}/(Ax_{1}+\cdots+Ax_{l})$

where $x_{i}$ are $A$-linear combinations of $\tilde{v}_{j}$. We can minimize
$r$ in the presentation by the following steps.

  1. (1)

For $1\leq i\leq l$, let $y_{i}$ be the sum of all monomials in $x_{i}$ that
equals $\tilde{v}_{j}$ for some $j$. In other words, we remove monomials in
$A_{+}\\{\tilde{v}_{1},\dots,\tilde{v}_{r}\\}$ from summands of $x_{i}$. Then
we have

$N/A_{+}N\cong
k\\{\tilde{v}_{1},\dots,\tilde{v}_{r}\\}/(ky_{1}+\cdots+ky_{l}).$

  2. (2)

Assume that $\dim_{k}(N/A_{+}N)=r^{\prime}$ for some $r^{\prime}\leq r$.
Perform row reductions on $y_{i}$ to find a subset of
$\\{\tilde{v}_{1},\dots,\tilde{v}_{r}\\}$ that generates $N/A_{+}N$. Without
loss of generality we assume that
$\\{\tilde{v}_{1},\dots,\tilde{v}_{r^{\prime}}\\}$ generates $N/A_{+}N$ and we
can write $\tilde{v}_{j}$ as a $k$-linear combination of
$\tilde{v}_{1},\dots,\tilde{v}_{r^{\prime}}$ for $j>r^{\prime}$ in $N/A_{+}N$.

  3. (3)

Perform the exact same row reductions on $x_{i}$ instead of $y_{i}$. Then in
$N$ we can write $\tilde{v}_{j}$ as a $k$-linear combination of
$\tilde{v}_{1},\dots,\tilde{v}_{r^{\prime}}$ and other monomials in
$A_{+}\\{\tilde{v}_{1},\dots,\tilde{v}_{r}\\}$ for $j>r^{\prime}$. By
iterating this process $\tilde{v}_{j}$ can be further rewritten as an
$A$-linear combination of $\tilde{v}_{1},\dots,\tilde{v}_{r^{\prime}}$. Thus
we can replace $x_{i}$ with

$x_{i}^{\prime}\in Av_{1}+\cdots+Av_{r^{\prime}}$

such that

$N\cong
A\\{\tilde{v}_{1},\dots,\tilde{v}_{r^{\prime}}\\}/(Ax_{1}^{\prime}+\cdots+Ax_{l}^{\prime})$

where $\\{\tilde{v}_{1},\dots,\tilde{v}_{r^{\prime}}\\}$ is a minimal
generating set of $N$.

Next we need the following simple algorithm which computes a minimal
generating set of of a submodule $M\subset A^{r}$.

######  Algorithm 7.2.

Let $M$ be a graded left submodule of $A^{r}$ generated by
$x_{1},\dots,x_{l}$. We can find a subset of $\\{x_{1},\dots,x_{l}\\}$ that is
a minimal generating set of $M$ by the following steps.

  1. (1)

Order $x_{1},\dots,x_{l}$ by degrees such that

$\deg(x_{1})\leq\cdots\leq\deg(x_{l}).$

  2. (2)

Compute the Gröbner basis $H_{i}$ of the submodule generated by
$x_{1},\dots,x_{i}$ for $0\leq i\leq l$ ($H_{0}=\emptyset$). We can apply
Algorithm 5.3 on $H_{i-1}\cup\\{\mathrm{red}(x_{i},H_{i-1})\\}$ to obtain
$H_{i}$.

  3. (3)

When $\mathrm{red}(x_{i},H_{i-1})=0$, mark $x_{i}$ as redundant for $1\leq
i\leq l$.

  4. (4)

Remove the redundant elements from $x_{1},\dots,x_{l}$. The remaining elements
form a minimal generating set of of $M$.

Now we have all the ingredients to construct a minimal resolution of
$N=A^{r}/M$.

######  Algorithm 7.3.

Let $N=A^{r}/M$ be a graded left $A$-module where $M\subset A^{r}$ is
generated by $x_{1},\dots,x_{l}$. We construct the first $s+1$ terms
$F_{0},\dots,F_{s}$ of a free resolution

$\cdots\to
F_{s}\xrightarrow{d_{s}}\cdots\xrightarrow{d_{3}}F_{2}\xrightarrow{d_{2}}F_{1}\xrightarrow{d_{1}}F_{0}=A^{r}\xrightarrow{\epsilon}N$

by the following steps.

  1. (1)

Apply Algorithm 7.1 to minimize $r$ in the presentation of $N$.

  2. (2)

Let $d_{0}=\epsilon:F_{0}=A^{r}\to N$ be the quotient map. Apply Algorithm 7.2
on $M=\ker(d_{0})$ to obtain a minimal generating set
$\\{x_{11},\dots,x_{1l_{1}}\\}$ of $M$.

  3. (3)

For $i=1,2,\dots,s$, assume that $\\{x_{i1},\dots,x_{il_{i}}\\}$ is a minimal
generating set of $\ker(d_{i-1})$. Define

$F_{i}=A\\{v_{i1},\dots,v_{il_{i}}\\},~{}\deg(v_{ij})=\deg(x_{ij})$

and

$d_{i}(v_{ij})=x_{ij},\text{ for }1\leq j\leq l_{i}.$

Apply Theorem 6.5 to compute a minimal generating set of
$\ker(d_{i})\cong\mathrm{Syz}(x_{i1},\dots,x_{il_{i}})$.

By executing the algorithm we can find that

$\mathrm{Ext}_{A}^{i}(N,k)\cong\begin{cases}k^{r}&i=0,\\\ k^{l_{i}}&1\leq
i\leq s.\end{cases}$

We call this algorithm a vertical method for computing a minimal resolution.
We can write a horizontal version of this algorithm which executes this
algorithm degree by degree (from the grading of $A$). We leave it for the
reader to write up this version. We refer the reader to [8, Theorem 4.8.16] of
a commutative version of a horizontal method which incorporates the
elimination algorithm as an optimization and it can be directly transferred to
our case.

##  8\. The Steenrod Algebra

In the rest of this paper, we would like to apply our noncommutative Gröbner
bases to the Steenrod algebra at the prime 2 and compute the Ext groups over
it. In this section we recall some facts about the Steenrod algebra.

Let ${\mathscr{A}}$ be the Steenrod algebra at the prime 2. It is a Hopf
algebra generated by symbols $Sq^{n}$, $n\geq 1$ in degree $n$ with relations
given by

$Sq^{i}Sq^{j}=\sum_{k=0}^{[i/2]}\binom{j-k-1}{i-2k}Sq^{i+j-k}Sq^{k}\hskip
14.22636pt(Sq^{0}=1)$

for all $i,j>0$ such that $i<2j$. They are call the Adem relations. The
coproduct is given by

$\psi(Sq^{n})=\sum_{i=0}^{n}Sq^{i}\otimes Sq^{n-i}.$

In order to define a suitable filtration for ${\mathscr{A}}$, first we
consider the dual of ${\mathscr{A}}$. By the work of Milnor [15], the dual of
the Steenrod algebra ${\mathscr{A}}_{*}$ can be characterized by

${\mathscr{A}}_{*}={\mathbb{F}}_{2}[\xi_{1},\xi_{2},\dots],\hskip
14.22636pt\deg(\xi_{i})=2^{i}-1$

with coproduct given by

$\psi(\xi_{n})=\sum_{i=0}^{n}\xi_{n-i}^{2^{i}}\otimes\xi_{i}.\hskip
14.22636pt(\xi_{0}=1)$

The dual basis of the monomial basis of ${\mathscr{A}}_{*}$ is denoted by
$\\{P(R)\\}$ where $R=(r_{1},r_{2},\dots)$ range over all sequences of non-
negative integers which are almost all zero, and $P(R)$ is dual to

$\xi(R)=\xi_{1}^{r_{1}}\xi_{2}^{r_{2}}\cdots.$

Milnor gives a product formula which computes a product $P(R_{1})\cdot
P(R_{2})$ as a linear combination of $P(R)$ again.

We define a weight function $w$ on ${\mathscr{A}}$ by

$w(P(r_{1},r_{2},\dots))=\sum_{k,i}(2k-1)a_{k,i}$

where $r_{k}=\sum_{i}a_{k,i}2^{i}$ is the 2-adic expansion. We define a
decreasing filtration on ${\mathscr{A}}$ by

$F_{p}{\mathscr{A}}=k\\{P(R):w(P(R))\geq p\\}.$

It is not hard to check via the coproduct formula in the dual that
$F_{\bullet}{\mathscr{A}}$ satisfies

$F_{p}{\mathscr{A}}\cdot F_{q}{\mathscr{A}}\subset F_{p+q}{\mathscr{A}}$

and in each degree $n$, we have $F_{p}{\mathscr{A}}_{n}=0$ when $p$ is large
enough.

######  Proposition 8.1.

The associated graded algebra of the Steenrod algebra is isomorphic to an
exterior algebra

$\mathrm{gr}({\mathscr{A}})\cong E[P^{i}_{j}:i\geq 0,j>0]$

where the symbol $P^{i}_{j}$ is the projection of

$\tilde{P}^{i}_{j}=P(0,\dots,0,\overset{j}{2^{i}},0,\dots)$

which is dual to $\xi_{j}^{2^{i}}$. The gradings of
$\mathrm{gr}({\mathscr{A}})$ are given by

$\deg(P^{i}_{j})=2^{i}(2^{j}-1),~{}|P^{i}_{j}|=2j-1.$

The reader can find a proof of this theorem from the proof of [20, Theorem
3.2.2].

######  Remark 8.2.

This associated graded algebra here is actually the same as the associated
homogeneous Koszul algebra (defined by Priddy [19]) of May’s associated graded
algebra of the Steenrod algebra (see [14]).

######  Remark 8.3.

For prime $p>2$, there is a similar filtration for the Steenrod algebra at the
prime $p$ such that the associated graded algebra is a product of exterior
algebras and truncated polynomial algebras of height $p$ (see the remarks
before [20, Lemma 3.2.4]). Therefore we can also apply our algorithms to the
Steenrod algebras at odd primes. However, the author has not implemented these
algorithms into computer programs yet.

Although $\mathrm{gr}({\mathscr{A}})$ is not a finitely generated commutative
algebra, the truncated graded algebra ${\mathscr{A}}_{\leq n}$ is finitely
generated and so is $\mathrm{gr}({\mathscr{A}}_{\leq n})$. When we want to
compute a minimal resolution of a left ${\mathscr{A}}$-module up to degree
$n$, it suffices to use ${\mathscr{A}}_{\leq n}$ instead of ${\mathscr{A}}$.

For our convenience, in the rest of this section, we implicitly consider
everything truncated to some degree so that Gröbner bases are still well-
defined.

When $A={\mathscr{A}}$, consider

$\mathrm{gr}({\mathscr{A}})=k[P^{i}_{j}:i\geq 0,j>0]/I$

where the ideal is generated by the set of squares

$G=\\{(P^{i}_{j})^{2}:i\geq 0,j>0\\}.$

It is obvious that $G$ is a Gröbner basis of $I$. We order the generators
$P^{i}_{j}$ by degree. In other words, we have

$P^{i}_{j}<P^{s}_{t}\Longleftrightarrow\deg(P^{i}_{j})<\deg(P^{s}_{t}).$

This is well defined since all $P^{i}_{j}$ have different degrees. We order
monomials of $P^{i}_{j}$ such that

$\displaystyle m<m^{\prime}\Longleftrightarrow$
$\displaystyle|m|<|m^{\prime}|\text{ or }$
$\displaystyle|m|=|m^{\prime}|\text{ and }m\text{ is \emph{greater} than
}m^{\prime}\text{ lexicographically}.$

The author uses this particular monomial ordering because the corresponding
computer program is faster than other versions the author has tried so far.
For left submodules of ${\mathscr{A}}^{r}$ we use (5.1) as our monomial
ordering.

The set

${\mathscr{B}}=\\{\text{square-free monomials in variables }P^{i}_{j}\\}$

is a ${\mathbb{F}}_{2}$-basis of $\mathrm{gr}({\mathscr{A}})$ while the set

$\tilde{\mathscr{B}}=\\{\tilde{P}^{i_{1}}_{j_{1}}\cdots\tilde{P}^{i_{l}}_{j_{l}}:\tilde{P}^{i_{1}}_{j_{1}}<\cdots<\tilde{P}^{i_{l}}_{j_{l}},l\geq
0\\}$

is a ${\mathbb{F}}_{2}$-basis of ${\mathscr{A}}$. The basis
$\tilde{\mathscr{B}}$ is similar to the “$P^{s}_{t}$ basis” in Monks [16] with
a different orderings of generators.

##  9\. Computing the Ext Groups over the Steenrod Algebra

In the previous section, we have shown that the truncated graded algebra
${\mathscr{A}}_{\leq n}$ is a finitely generated filtered-commutative algebra.
Therefore we can apply the noncommutative Gröbner bases to compute the Ext
groups $\mathrm{Ext}_{\mathscr{A}}^{*,*}(N,k)$ for a finitely generated graded
left ${\mathscr{A}}$-module $N$.

The author has implemented the algorithms into computer programs to compute
$\mathrm{Ext}_{\mathscr{A}}^{*,*}(N,k)$ for various $N$ up to some degree. The
program code can be found on Github [11]. In addition to Algorithm 7.3, the
computer programs incorporate the following optimizations in commutative
algebras which can be easily adapted to our noncommutative case.

  1. (1)

Use Buchberger triple to reduce the number of steps needed to compute a
Gröbner basis. (See [9, Tutorial 25])

  2. (2)

Build the resolution degree by degree and use eliminations. (See [8, Theorem
4.8.16])

Since ${\mathscr{A}}$ is a Hopf algebra,
$\mathrm{Ext}_{\mathscr{A}}^{*,*}({\mathbb{F}}_{2},{\mathbb{F}}_{2})$ is
actually a commutative algebra over ${\mathbb{F}}_{2}$. After we obtain a
resolution by the programs above, we can use methods described in [5, 6] to
compute the products in
$\mathrm{Ext}_{\mathscr{A}}^{*,*}({\mathbb{F}}_{2},{\mathbb{F}}_{2})$ and
module structures of $\mathrm{Ext}_{\mathscr{A}}^{*,*}(N,{\mathbb{F}}_{2})$
over $\mathrm{Ext}_{\mathscr{A}}^{*,*}({\mathbb{F}}_{2},{\mathbb{F}}_{2})$ for
$A$-modules $N$. However, we always use Gröbner bases to do linear algebra
other than enumerating ${\mathbb{F}}_{2}$-bases of free
${\mathscr{A}}$-modules. The elimination algorithm mentioned above is
especially efficient for building maps between chain complexes, which is used
to compute products in Ext.

We have computed the cohomology of the Steenrod algebra
$\mathrm{Ext}_{\mathscr{A}}^{*,*}({\mathbb{F}}_{2},{\mathbb{F}}_{2})$ with
outcomes described in Theorem 1.3. The computed range is very large and
contains $h_{7}^{2}$ and $h_{8}$. The reader can find a graphical diagram of
$\mathrm{Ext}_{{\mathscr{A}}}^{*,*}({\mathbb{F}}_{2},{\mathbb{F}}_{2})$ on the
webpage [12].

## References

  * [1] J. F. Adams.  On the structure and applications of the Steenrod algebra.  Comment. Math. Helv., 32:180–214, 1958.
  * [2] J. Apel and W. Lassner.  An extension of Buchberger’s algorithm and calculations in enveloping fields of Lie algebras.  volume 6, pages 361–370. 1988.  Computational aspects of commutative algebra.
  * [3] George M. Bergman.  The diamond lemma for ring theory.  Adv. in Math., 29(2):178–218, 1978.
  * [4] R. R. Bruner and J. Rognes.  The cohomology of the mod 2 steenrod algebra.  arXiv:2109.13117.
  * [5] Robert R. Bruner.  Calculation of large Ext modules.  In Computers in geometry and topology (Chicago, IL, 1986), volume 114 of Lecture Notes in Pure and Appl. Math., pages 79–104. Dekker, New York, 1989.
  * [6] Robert R. Bruner.  ${\rm Ext}$ in the nineties.  In Algebraic topology (Oaxtepec, 1991), volume 146 of Contemp. Math., pages 71–90. Amer. Math. Soc., Providence, RI, 1993.
  * [7] Bruno Buchberger.  An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal.  J. Symbolic Comput., 41(3-4):475–511, 2006.  Translated from the 1965 German original by Michael P. Abramson.
  * [8] Martin Kreuzer and Lorenzo Robbiano.  Computational commutative algebra 2.  Springer-Verlag, Berlin, 2005.
  * [9] Martin Kreuzer and Lorenzo Robbiano.  Computational commutative algebra 1.  Springer-Verlag, Berlin, 2008.  Corrected reprint of the 2000 original.
  * [10] Huishi Li.  Noncommutative Gröbner bases and filtered-graded transfer, volume 1795 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2002.
  * [11] Weinan Lin.  Github repo.  https://github.com/WayneLin92/SSeqCpp.
  * [12] Weinan Lin.  Interactive diagram of the Adams spectral sequence.  https://waynelin92.github.io/ss/index.html.
  * [13] Weinan Lin.  Cohomology of the mod 2 Steenrod algebra (t261.0) [data set], March 2023\.  Availabel at Zenodo, https://doi.org/10.5281/zenodo.7786290.
  * [14] J. Peter May.  The cohomology of restricted lie algebras and of hopf algebras: application to the steenrod algebra.  ProQuest LLC, Ann Arbor, MI, 1964.  Thesis (Ph.D.)–Princeton University.
  * [15] John Milnor.  The Steenrod algebra and its dual.  Ann. of Math. (2), 67:150–171, 1958.
  * [16] Kenneth G. Monks.  Change of basis, monomial relations, and $P^{s}_{t}$ bases for the Steenrod algebra.  J. Pure Appl. Algebra, 125(1-3):235–260, 1998.
  * [17] Teo Mora.  An introduction to commutative and noncommutative Gröbner bases.  volume 134, pages 131–173. 1994.  Second International Colloquium on Words, Languages and Combinatorics (Kyoto, 1992).
  * [18] Christian Nassau.  https://www.nullhomotopie.de.
  * [19] Stewart B. Priddy.  Koszul resolutions and the Steenrod algebra.  Bull. Amer. Math. Soc., 76:834–839, 1970.
  * [20] Douglas C. Ravenel.  Complex cobordism and stable homotopy groups of spheres, volume 121 of Pure and Applied Mathematics.  Academic Press, Inc., Orlando, FL, 1986.
  * [21] Guozhen Wang.  https://github.com/pouiyter/morestablestems.

Weinan Lin, School of Mathematical Sciences, Peking University, 5 Yi He Yuan
Road, Haidian District, Beijing, 100871, China.

_Email address_<EMAIL_ADDRESS>


# Contrastive Learning with Prompt-derived Virtual Semantic Prototypes for
Unsupervised Sentence Embedding

Jiali Zeng1, Yongjing Yin2, Yufan Jiang1, Shuangzhi Wu1, Yunbo Cao1
1Tencent Cloud Xiaowei, Beijing, China
2Westlake University, Zhejiang, China
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
Corresponding author.

###### Abstract

Contrastive learning has become a new paradigm for unsupervised sentence
embeddings. Previous studies focus on instance-wise contrastive learning,
attempting to construct positive pairs with textual data augmentation. In this
paper, we propose a novel Contrastive learning method with Prompt-derived
Virtual semantic Prototypes (ConPVP). Specifically, with the help of prompts,
we construct virtual semantic prototypes to each instance, and derive negative
prototypes by using the negative form of the prompts. Using a prototypical
contrastive loss, we enforce the anchor sentence embedding to be close to its
corresponding semantic prototypes, and far apart from the negative prototypes
as well as the prototypes of other sentences. Extensive experimental results
on semantic textual similarity, transfer, and clustering tasks demonstrate the
effectiveness of our proposed model compared to strong baselines. Code is
available at https://github.com/lemon0830/promptCSE.

##  1 Introduction

High-quality sentence embeddings can boost the performance of pre-trained
language models (PLMs) on many downstream tasks Kiros et al. (2015);
Logeswaran and Lee (2018); Reimers and Gurevych (2019a). Recent research
focuses on learning sentence embeddings in an unsupervised manner due to lack
of large scale labeled data Hill et al. (2016); Pagliardini et al. (2018);
Wang et al. (2021b). Among these methods, contrastive learning has been
extensively explored and achieved remarkable success Gao et al. (2021b); Wu et
al. (2021); Yan et al. (2021); Giorgi et al. (2021). Specifically, most of
them construct a positive pair by operating various textual data augmentation
methods, while regard two independent sentences sampled uniformly from the
training data as a negative pair. In spite of effectiveness in easing the
anisotropy problem, such instance-wise optimization leads to a locally smooth
embedding space, and ignores semantic relevance to some extent Li et al.
(2020b). Moreover, due to the discrete nature of language, data augmentation
can change sentence semantics significantly, and thus a positive sample are
possibly turned into a negative one Wang et al. (2021a).

Figure 1:  Paradigm of prompt learning.

To alleviate the issues, we introduce the idea of prototypical contrastive
learning to unsupervised sentence embeddings learning, which is proven
effective to learn structural visual embedding space Li et al. (2020b); Caron
et al. (2020). The motivation lies in that when encoding sentences into the
embedding space, the sentences with similar semantics cluster together around
the corresponding prototype. Nevertheless, the acquisition of prototypes is
inefficient if we directly apply the clustering algorithms used in Li et al.
(2020b); Caron et al. (2020), due to the requirement of extra forward pass
over the training set or weak correlation with semantics Caron et al. (2020).
This makes us wonder whether there exists a dedicated method of mining the
semantic prototypes for sentence embeddings especially based on PLMs?

To answer this question, we attempt to think from the perspective of prompt
learning Brown et al. (2020). Intuitively, on sentence-level NLP tasks such as
classification, the neural models encode and map each input to a corresponding
semantic prototype in the embedding space. For example, the sentiment analysis
models divide instances into semantic prototypes related to sentiment
polarity. In addition, the sentence-level tasks can be solved by providing
task-specific prompts to PLMs as a condition even without any fine-tuning
Brown et al. (2020); Sanh et al. (2021); Wei et al. (2021). As illustrated in
Figure 1, PLMs can directly generate reasonable label words (e.g., “positive”)
for a sentence <$S$> by answering the query of the “[MASK]” token, when fed a
prompt-wrapped sequence (e.g., “<S> is this review positive ? [MASK]”). Thus,
we argue that the representations of the “[MASK]” token derived by task-
specific templates can be viewed as virtual semantic prototypes, which can be
obtained without using label information Lan et al. (2021) and clustering
algorithms Li et al. (2020b); Caron et al. (2020). Besides the commonly-used
templates, we manually convert each template to its negation, and use them to
induce negative prototypes. Back to Figure 1, with the template “<S> is not a
[MASK] one”, the word “bad” can be derived from PLMs.

Figure 2:  Illustration of contrastive learning with prompt-derived virtual
semantic prototypes.

In this paper, we propose ConPVP (Contrastive learning with Prompt-derived
Virtual Semantic Prototypes) (ConPVP) for unsupervised sentence representation
learning. Specifically, given an input sentence, we generate the positive and
negative prototypical embeddings by using a task-specific template and its
negative counterpart, respectively. We use the contrastive loss to enforce the
sentence embedding to be close to its positive prototype, and far apart from
the negative prototype as well as the prototypes of other sentences. As
illustrated in Figure 2, the issue of local smoothness can be alleviated by
exploiting the semantic regularization induced by task-specific prompts, and
the sentences with similar semantics are closer. We empirically evaluate our
proposed ConPVP on a range of semantic textual similarity tasks, and the
experimental results show the substantial improvements compared with strong
baselines. Further,the extensive analysis and applications to transfer and
clustering tasks confirm the effectiveness and robustness of our ConPVP.

##  2 Related Work

###  2.1 Prototypical Contrastive Learning

Recently, prototypical contrastive learning has shown its power in computer
vision Li et al. (2020b); Caron et al. (2020); Sharma et al. (2020) and NLP
tasks Wei et al. (2022); Ding et al. (2021), which discover the underlying
semantic structure by clustering the learned embeddings. Compared with them,
we propose a more efficient and dedicated method to find prototypes for
sentence embeddings, without using clustering algorithms or label information.
To the best of our knowledge, we are the first to explore the prototypical
contrastive learning in unsupervised sentence representation learning.

###  2.2 Prompt-based Learning

Prompt-based Learning has become a new paradigm in NLP, bridging the gap
between pretraining tasks and downstream tasks Brown et al. (2020); Schick and
Schütze (2021a); Sanh et al. (2021). It reformulates various NLP tasks as
cloze-style questions, and by doing so, the knowledge stored in PLMs can be
fully exploited, making PLMs achieve impressive performance in few-shot and
zero-shot settings. Along this research line, various types of prompts are
explored including discrete and continuous prompts Gao et al. (2021a); Shin et
al. (2020); Hu et al. (2021); Liu et al. (2021); Cui et al. (2021); Si et al.
(2021); Li and Liang (2021); Schick and Schütze (2021b). In this work, we
exploit prompts of different downstream tasks to assign various virtual
semantic prototypes to each instance.

###  2.3 Unsupervised Sentence Embedding

Unsupervised learning has been used to improve the sentence embedding learning
Reimers and Gurevych (2019b); Li et al. (2020a); Su et al. (2021); Zhang et
al. (2020), and contrastive learning has attracted extensive attention due to
the promising performance Gao et al. (2021b); Giorgi et al. (2021); Wu et al.
(2020); Yan et al. (2021); Meng et al. (2021); Carlsson et al. (2021). Wu et
al. (2021) augment positive pairs with word repetition and introduce a
momentum encoder for negative pairs. Wang et al. (2022) use soft negative
samples which have highly similar textual but opposite meaning to the input
sentence. Jiang et al. (2022) use a discrete template to obtain sentence
embeddings. Unlike these studies, we introduce prototypical contrastive
learning and implicitly encode semantic structure induced by task-specific
prompts into the embedding space, enhancing PLMs’ ability of modeling semantic
similarity. Furthermore, our prototypical contrastive loss is orthogonal to
the instance-wise one, and the performance can be further improved by
combining ConPVP with the above studies.

Figure 3:  The overall framework of our proposed ConPVP.

##  3 Method

In this section, we elaborate the proposed ConPVP, a novel contrastive
learning approach implicitly encoding semantic structure into the embedding
space. As illustrated in Figure 3, ConPVP is based on the popular SimCSE
framework Gao et al. (2021b) and further leverages the concept of semantic
prototypes.

###  3.1 Prompt-derived Virtual Semantic Prototypes

Semantic prototype is defined as a representative embedding for a group of
semantically similar instances Li et al. (2020b). Given the fact that PLMs are
able to perform well on various NLP tasks when provided with suitable task-
specific templates Brown et al. (2020); Sanh et al. (2021); Wei et al. (2021),
we can induce the semantic prototypes of sentences from PLMs with the help of
prompts. In this work, we construct a template set $\mathcal{T}^{+}$ using
four NLP tasks (i.e., classification, summarization, natural language
inference, and sentence embedding), and assign each task 2 templates. Please
note that we select the templates without deliberation, and we leave the other
choices as future work. Furthermore, we construct another template set
$\mathcal{T}^{-}$, in which the templates are the negative form of those in
$\mathcal{T}^{+}$ and possibly induces semantically opposite response from
PLMs. All the templates are illustrated in Table 1.

Basic Templates
---
Given “<S>” , we assume that “[MASK]”
“ <S> ” , is this review positive ? [MASK] .
“ <S> ” , is [MASK] news
“ <S> ” , is a [MASK] one
“ <S> ” . In summary : “ [MASK] ”
By “ <S> ” they mean [MASK] .
Article “ <S> ” belongs to a [MASK] topic
This sentence : “ <S> ” means [MASK] .
Semantically Opposite Templates
“ <S> ” , is this review negative ? [MASK] .
Without “ <S> ” , they mean [MASK] .
“ <S> ” is inconsistent with “ [MASK] ”
“ <S> ” is totally different from : “ [MASK] ”
“ <S> ” which does not denote [MASK]
“ <S> ” is not a [MASK] one
This sentence : “ <S> ” does not mean [MASK] .
Article “ <S> ” is definitely not about the [MASK] topic
Table 1:  Templates for inducing semantic prototypes.

After obtaining the template sets, we convert an input sentence $x_{i}$ to
$\hat{x}_{i}$=[$x_{i}$; $\mathcal{T}^{+}_{i}$], where $\mathcal{T}^{+}_{i}$ is
a template sampled from $\mathcal{T}^{+}$. We feed $\hat{x}_{i}$ to a PLM and
take the hidden state of the “[MASK]” token $h_{\rm[MASK]}$ as the positive
prototypical embedding $c_{i}^{+}$. In this same way, we generate the negative
prototypical embedding $c^{-}_{i}$ using a sampled template
$\mathcal{T}^{-}_{i}\in\mathcal{T}^{-}$. Notably, unlike the conventional
prototypes Li et al. (2020b); Caron et al. (2020); Sharma et al. (2020), our
method of obtaining prototypes may not seem intuitive, since there is no
explicit partitioning of the embedding space. In order to distinguish our
method from the previous studies, we name the prototypes in this work virtual
prototypes.

###  3.2 Prototypical Contrastive Learning

To obtain the embedding of an anchor sentence $x_{i}$, we feed
$[x_{i};t_{1};...;t_{l};$[MASK]$]$ to a PLM to obtain its contextualized
representations, where $t_{1};...;t_{l}$ is a continuous prompt. The
representation vector of the “[MASK]” token is taken as the sentence embedding
$v_{i}$. Given the embedding of the anchor sentence and the corresponding
positive and negative prototype embeddings, we integrate them into the InfoNCE
based contrastive loss 111In practice, in order to reduce the influence of the
template, we follow Jiang et al. (2022) to use debiased sentence embeddings
during training. Please ref Jiang et al. (2022) for more detailed.:

$l_{i}=-\log\frac{e^{{\rm sim}(v_{i},c^{+}_{i})/\tau}}{\sum^{N}_{k=1}(e^{{\rm
sim}(v_{i},c^{+}_{k})/\tau}+e^{{\rm sim}(v_{i},c^{-}_{k})/\tau})}$ (1)

where $N$ is the number of sentences in a mini-batch. With this loss function,
we pull the embedding of the anchor sentence $v_{i}$ close to its positive
prototypical embedding $c^{+}_{i}$, and push $v_{i}$ and the irrelevant
prototypical embeddings apart.

PLM | Batch Size | Learning Rate
---|---|---
BERT-base | 128 | 3e-5
BERT-large | 128 | 1e-5
RoBERTa-base | 128 | 1e-5
RoBERTa-large | 256 | 1e-5
Table 2:  Training Settings for STS.  Model | STS12 | STS13 | STS14 | STS15 | STS16 | STS-B | SICK-R | Avg.
---|---|---|---|---|---|---|---|---
BERT-base
ConSERT † | 64.64 | 78.49 | 69.07 | 79.72 | 75.95 | 73.97 | 67.31 | 72.74
SimCSE † | 68.40 | 82.41 | 74.38 | 80.91 | 78.56 | 76.85 | 72.23 | 76.25
ESimCSE † | 73.40 | 83.27 | 77.25 | 82.66 | 78.81 | 80.17 | 72.30 | 78.27
PromptBERT † | 71.56 | 84.58 | 76.98 | 84.47 | 80.60 | 81.60 | 69.87 | 78.54
ConPVP | 71.72 | 84.95 | 77.68 | 83.64 | 79.76 | 80.82 | 73.38 | 78.85
BERT-large
ConSERT † | 70.69 | 82.96 | 74.13 | 82.78 | 76.66 | 77.53 | 70.37 | 76.45
SimCSE † | 70.88 | 84.16 | 76.43 | 84.50 | 79.76 | 79.26 | 73.88 | 78.41
ESimCSE † | 73.21 | 85.37 | 77.73 | 84.30 | 78.92 | 80.73 | 74.89 | 79.31
PromptBERT | 71.55 | 86.83 | 78.63 | 85.10 | 79.79 | 82.20 | 72.19 | 79.47
ConPVP | 72.63 | 86.68 | 78.14 | 85.50 | 80.13 | 82.18 | 74.79 | 80.01
RoBERTa-base
SimCSE † | 70.16 | 81.77 | 73.24 | 81.36 | 80.65 | 80.22 | 68.56 | 76.57
ESimCSE † | 69.90 | 82.50 | 74.68 | 83.19 | 80.30 | 80.99 | 70.54 | 77.44
PromptBERT † | 73.94 | 84.74 | 77.28 | 84.99 | 81.74 | 81.88 | 69.50 | 79.15
ConPVP | 73.20 | 83.22 | 76.24 | 83.37 | 81.49 | 82.18 | 74.59 | 79.18
RoBERTa-large
SimCSE † | 72.86 | 83.99 | 75.62 | 84.77 | 81.80 | 81.98 | 71.26 | 78.90
EsimCSE † | 73.20 | 84.93 | 76.88 | 84.86 | 81.21 | 82.79 | 72.27 | 79.45
PromptBERT | 72.89 | 86.44 | 78.10 | 85.09 | 79.37 | 81.52 | 70.85 | 79.18
ConPVP | 74.75 | 84.09 | 77.88 | 83.13 | 83.44 | 83.64 | 74.31 | 80.18
Table 3:  Experimental results on unsupervised STS tasks. Methods with †
denote that we directly report the scores from corresponding paper, and others
are from our implementation. We run 4 times with different random seeds and
report the best Avg. for fair comparison.

##  4 Experiments

To verify the effectiveness of our proposed method, we conduct experiments and
empirical analysis on Semantic Textual Similarity (STS) tasks under the
unsupervised setting.

###  4.1 Settings

Following Gao et al. (2021b), we conduct experiments on 7 semantic textual
similarity (STS) tasks, including STS 2012-2016 Agirre et al. (2012, 2013,
2014, 2015, 2016), STS Benchmark Cer et al. (2017), and SICK-R Marelli et al.
(2014). The similarity scores of sentence pairs in these datasets are labeled
from 0 to 5. Our implementation is based on SimCSE
222https://github.com/princeton-nlp/SimCSE Gao et al. (2021b), and we take
BERT-base Devlin et al. (2019), BERT-large Devlin et al. (2019), RoBERTa-base
Liu et al. (2019), and RoBERTa-large Liu et al. (2019) as our
backbones333https://github.com/huggingface/transformers. All our experiments
are conducted on a NVIDIA V100 GPU. We set the length of the continuous prompt
as 4. Following previous studies Gao et al. (2021b); Wu et al. (2021), we use
1 million sentences randomly sampled from English Wikipedia as training
sentences. We train 1 epoch, and evaluate every 125 steps and choose model
parameters with highest performance on STS-B development set. The batch size
and learning rate are listed in Table 2.

Model | STS12 | STS13 | STS14 | STS15 | STS16 | STS-B | SICK-R | Avg.
---|---|---|---|---|---|---|---|---
RoBERTa-large
SimCSE | 69.36±1.16 | 82.39±0.70 | 74.33±1.06 | 83.03±1.34 | 81.19±0.45 | 81.10±0.77 | 70.17±0.91 | 77.37±0.88
PromptBERT | 72.00±1.16 | 83.54±1.85 | 77.05±1.02 | 83.32±1.15 | 80.82±0.98 | 82.54±0.79 | 70.31±0.82 | 78.51±0.77
ConPVP | 74.57±0.54 | 83.62±0.59 | 77.77±0.29 | 83.18±0.85 | 82.85±0.37 | 82.85±0.46 | 74.47±0.44 | 79.90±0.32
w/ manual | 72.61±1.26 | 82.31±0.72 | 77.19±0.55 | 84.85±1.00 | 81.48±0.44 | 82.31±0.48 | 73.50±0.54 | 79.18±0.49
w/o $c^{-}$ | 73.80±0.93 | 82.38±0.58 | 76.72±0.50 | 82.53±0.77 | 81.94±0.54 | 82.32±0.31 | 69.75±0.58 | 78.49±0.33
w/o $c^{+}$ & $c^{-}$ | 72.81±0.75 | 81.51±0.63 | 74.94±0.77 | 79.83±0.81 | 80.50±0.55 | 81.06±0.40 | 70.30±0.43 | 77.28±0.25
Table 4:  Ablation Study. We run each experiment 4 times with different random
seeds and report mean and standard deviation.

###  4.2 Main Results

We compare our ConPVP to the recent related methods which are based on
instance-wise contrastive learning, including 1) ConSERT Yan et al. (2021)
which exploits four data augmentation strategies to construct positive
samples; 2) SimCSE Gao et al. (2021b) which directly uses Dropout to generate
positive pairs; 3) ESimCSE Wu et al. (2021) which introduces word repetition
augmented positive pairs and momentum negative pairs; 4) PromptBERT Jiang et
al. (2022) which reformulates the sentence embeddings task as a prompt-based
learning paradigm.

Figure 4:  Distribution of predicted cosine similarity. The correlation
diagram between the gold similarity scores (x-axis) and model predicted cosine
similarity scores (y-axis) on the STS-B dataset. We scale the predicted scores
to 0 to 1.

For fair comparison, we report the best performance from 4 runs in Table 3.
Compared with SimCSE, ConPVP brings significant improvements across the board.
Specifically, ConPVP achieves average improvements of 2.60, 1.60, 2.61, and
1.28 points over BERT-base, BERT-large, RoBERTa-base and RoBERTa-large,
respectively, showing the superiority of our prototypical contrastive method.
Besides, ConPVP surpasses ConSERT and ESimCSE, which carefully design positive
samples with various textual data augmentation. This demonstrates that
although the textual data augmentation can provide different views of the
anchor, these methods based on it still suffers the local smooth problem. In
contrast, our model shows that textual data augmentation is possibly
unnecessary, and the improvement can be achieved by encoding more structural
information into the embedding space, e.g., finding semantic prototypes.
Finally, our ConPVP achieves consistently better performance than PromptBERT,
demonstrating the effectiveness of the proposed prototypical contrastive loss.

###  4.3 Ablation Study

To analyze the impact of different components of ConPVP, we investigate the
following three variants: 1) ConPVP w/ manual, where we obtain the anchor
sentence embeddings with the searched discrete templates from Jiang et al.
(2022); 2) ConPVP w/o $c^{-}$, where we remove the negative prototypes in the
prototypical contrastive loss; 3) ConPVP w/o $c^{+}$ & $c^{-}$, which is
equivalent to SimCSE but uses continuous prompts for sentence embeddings.
Notably, ConPVP w/o $c^{+}$ & $c^{-}$ is also a variant of PromptBERT Jiang et
al. (2022), where the discrete templates are replaced by the continuous ones.
We take RoBERTa-large as the backbone.

Figure 5:  Analysis of embedding space. The average spearman correlation on
STS tasks w.r.t the number of removed top-k frequent tokens. The frequency of
each token is calculated through the test split of the STS Benchmark dataset.

The results on STS tasks are listed in Table 4 and the conclusions are as
follows: 1) ConPVP obtains better results against ConPVP w/ manual. This may
be because one manually-designed prompt cannot fit different PLMs and training
strategies at the same time, and continuous prompts are more flexible and
effective in comparison. Besides, the improvement of ConPVP w/ manual over
PromptBERT validates the advantage of the prototypical contrastive loss. 2)
Removing the negative prototypes (i.e., ConPVP w/o $c^{-}$) leads to a
performance degradation of 1.41 point against ConPVP. The underlying reason is
that the negative prototypes here serve as a type of hard negatives—the
semantics of the negative prototypes are essentially different from the
positive prototypes but the prompts used to induce them are similar in text.
3) We find that ConPVP w/o $c^{+}$ & $c^{-}$ does not give an improvement
against SimCSE. These observations show that the gain of our method entirely
comes from the cooperation between the prompt-derived virtual prototypes and
the prototypical contrastive loss, rather than the usage of the prompt-based
sentence embeddings.

###  4.4 Distribution of Cosine Similarity

In this section, we investigate the similarity distributions learned by
different methods. As shown in Figure 4, the native sentence representations
of RoBERTa-large suffer from the collapse issue Chen and He (2021), and
therefore we get high similarity scores for all sentence pairs. By contrast,
both ConPVP and SimCSE alleviate the collapse issue, and the predicted cosine
similarity scores for positive pairs of ConPVP are more certain. For example,
for the positive pairs whose similarity scores range from 4 to 5, the scores
predicted by ConPVP (0.6 to 1.0) is more concentrated than the scores
predicted by SimCSE (0.4 to 1.0).

Figure 6:  Visualization of learned embeddings. We visualize 10 sentence pairs whose similarity scores are 0 in  orange (ids from 0 to 9), 10 pairs whose similarity scores are 3 in  blue (ids from 10 to 19), and 10 pairs whose similarity scores are 5 in  green (ids from 20 to 29). The sentences are sampled from the STS-B test set.  Model | MR | CR | SUBJ | MPQA | SST | TREC | MRPC | Avg.
---|---|---|---|---|---|---|---|---
GloVe † | 77.25 | 78.30 | 91.17 | 87.85 | 80.18 | 83.00 | 72.87 | 81.52
Skip-thought ♡ | 76.50 | 80.10 | 93.60 | 87.10 | 82.00 | 92.20 | 73.00 | 83.50
IS-BERT ♡ | 81.09 | 87.18 | 94.96 | 88.75 | 85.96 | 88.64 | 74.24 | 85.83
RoBERTa-base
SimCSE † | 81.04 | 87.74 | 93.28 | 86.94 | 86.60 | 84.60 | 73.68 | 84.84
SimCSE | 81.75±0.19 | 87.23±0.08 | 93.18±0.13 | 87.13±0.06 | 86.98±0.39 | 85.40±0.71 | 73.78±0.11 | 85.06±0.13
Ours | 82.44±0.17 | 88.30±0.16 | 93.20±0.11 | 88.74±0.06 | 87.70±0.07 | 87.33±0.25 | 76.15±0.19 | 86.27±0.11
RoBERTa-large
SimCSE † | 82.74 | 87.87 | 93.66 | 88.22 | 88.58 | 92.00 | 69.68 | 86.11
SimCSE | 83.17±0.41 | 88.46±0.43 | 93.73±0.10 | 88.33±0.10 | 88.52±0.29 | 91.40±0.71 | 71.34±1.17 | 86.42±0.23
ConPVP | 85.65±0.28 | 90.73±0.32 | 94.13±0.13 | 90.03±0.23 | 89.81±0.29 | 93.40±0.16 | 76.47±0.29 | 88.60±0.14
Table 5:  Experimental results on Transfer tasks with RoBERTa-base and
RoBERTa-large backbones. †: results from Gao et al. (2021b). ♡: results from
Zhang et al. (2020). We run 4 times with different random seeds and report the
average accuracy and standard deviation.

###  4.5 Analysis of Embedding Space

Previous studies indicated that the collapse issue is mainly due to anisotropy
of the learned embedding space, which is sensitive to token frequency Yan et
al. (2021); Jiang et al. (2022). We follow Yan et al. (2021) to remove the
embeddings of K most frequent tokens and explore the relation between the
number of removed tokens and the average spearman correlation on STS tasks.

From Figure 5, we can observe that the performance of native BERT-base and
SimCSE improves when removing the most frequent tokens. By contrast, ConPVP
achieves its best performance without removing any tokens, showing that our
approach reshapes the BERT’s original embedding space, reducing the influence
of common tokens on sentence representations. In addition, the performance of
both SimCSE and ConPVP drops as the number of removed tokens increases but
ConPVP performs significantly better, demonstrating the robustness of ConPVP
to incomplete input.

###  4.6 Visualization of Learned Embeddings

We visualize a few variants of RoBERTa-large sentence embeddings to grasp an
intuition on the effectiveness of our method. Specifically, we sample 3 groups
of samples from the STS-B test set, and the similarity score of each group is
0 (orange), 3 (blue), and 5 (green), respectively. Each group has 10 sentence
pairs. We visualize their embeddings generated by different models using t-SNE
van der Maaten and Hinton (2008) in Figure 6.

Due to the collapse issue, the sentence embeddings obtained from RoBERTa-large
[CLS] cluster together whether they are similar or not. For SimCSE, the
sentence embeddings of the positive pairs are well-clustered. However, the
sentences pairs with similarity scores of 3 or 5 are very close in the
embedding space. In contrast, the embeddings learned by our ConPVP are more
discriminative, forming more separated clusters (e.g., the sentence pairs in
green are more clustered than those in blue, while the pairs in orange are
more dispersed).

Figure 7:  Few-shot learning evaluation on Transfer tasks with RoBERTa-base and RoBERTa-large as the backbones. For each task, we randomly sample 16 labeled instances per class and draw violin plots of the performance of 10 runs with different random seeds.  Model | AG | Bio | Go-S | G-T | G-TS | SS | SO | Tweet | Avg.
---|---|---|---|---|---|---|---|---|---
BERT-base
BERT | 79.56 | 32.46 | 54.35 | 47.12 | 61.61 | 64.04 | 21.87 | 45.35 | 50.80
SimCSE ♣ | 74.36 | 35.89 | 58.90 | 57.28 | 65.03 | 64.32 | 50.57 | 54.28 | 57.58
ConPVP | 77.21 | 41.84 | 61.98 | 59.87 | 67.56 | 73.28 | 73.06 | 56.06 | 63.86
BERT-large
BERT | 83.13 | 30.52 | 56.34 | 46.11 | 61.51 | 66.54 | 26.10 | 44.20 | 51.81
SimCSE ♣ | 80.23 | 43.47 | 61.87 | 61.05 | 65.78 | 68.97 | 68.03 | 55.08 | 63.06
ConPVP | 82.50 | 41.26 | 63.82 | 58.87 | 68.34 | 74.39 | 66.59 | 57.34 | 64.14
Table 6:  Clustering accuracy reported on short text clustering datasets with
BERT-base and BERT-large as the backbones. $\clubsuit$: results evaluated on
the checkpoints provided by Gao et al. (2021b). We report the clustering
accuracy averaged over 10 independent runs.

##  5 Application to Transfer Learning Tasks

We evaluate the quality of the sentence embeddings learned by ConPVP on
transfer learning tasks, including MR Pang and Lee (2005), CR Hu and Liu
(2004), SUBJ Pang and Lee (2004), MPQA Wiebe et al. (2005), SST-2 Socher et
al. (2013), TREC Li and Roth (2002) and MRPC Dolan et al. (2004). A logistic
regression classifier is trained using frozen sentence embeddings produced by
different methods. We follow default configurations from SentEval Conneau and
Kiela (2018). In addition, based on the principle that good representations
can be transferred well with limited supervision and fine-tuning, we extend
the evaluation to few-shot setting and follow Zhang et al. (2021) to uniformly
sample 16 labeled instances per class for each task.

Table 5 presents the results under the full data setting. As we can see, the
performance gap between ConPVP and SimCSE is significant and consistent.
Furthermore, we can observe more obvious gap under the few-shot setting
(Figure 7). The results reveal the robustness and effectiveness of our
approach under the data scarcity scenarios, which is important in real-world
applications.

##  6 Application to Clustering Tasks

We follow Zhang et al. (2021) to consider 8 benchmark datasets for short text
clustering, including SearchSnippets (SS) Phan et al. (2008), StackOverflow
(SO) Xu et al. (2017), Biomedical (Bio) Xu et al. (2017), AgNews (AG) Zhang
and LeCun (2015), Tweet Yin and Wang (2016) and GoogleNews (G-T, G-S, G-TS)
Yin and Wang (2016). We follow default settings of Zhang et al. (2021) and use
BERT-base and BERT-large as the backbones. We run K-Means Pedregosa et al.
(2011) on the sentence embeddings and report the clustering accuracy averaged
over 10 independent runs. As illustrated in Table 6, in comparison with
SimCSE, ConPVP obtains an averaged improvement of 1.21 and 2.18, respectively,
which validates our motivation in leveraging the implicit grouping effect of
the prompt-derived semantic prototypes to encode more semantic structure into
representations.

##  7 Conclusion

In this work, we take the first step to explore the prototypical contrastive
learning on unsupervised sentence embedding learning, and consider more
semantic views for each instance than the recent instance-wise contrastive
methods. In particular, we make use of the prompting in PLMs to generate the
positive and negative prototypical embeddings with task-specific templates.
The experiments and extensive analysis validate the effectiveness and
robustness of our ConPVP.

##  8 Limitations

We only tried 16 task specific prompts in this paper, which is possibly sub-
optimal to induce semantic prototypes. Besides, the usage of prompts reduces
the maximum effective lengths that the pretrained language models can process.

## Acknowledgements

We would like to thank anonymous reviewers for their suggestions and comments.

## References

  * Agirre et al. (2015) Eneko Agirre, Carmen Banea, Claire Cardie, Daniel Cer, Mona Diab, Aitor Gonzalez-Agirre, Weiwei Guo, Iñigo Lopez-Gazpio, Montse Maritxalar, Rada Mihalcea, German Rigau, Larraitz Uria, and Janyce Wiebe. 2015.  SemEval-2015 task 2: Semantic textual similarity, English, Spanish and pilot on interpretability.  In _Proceedings of the 9th International Workshop on Semantic Evaluation (SemEval 2015)_ , pages 252–263, Denver, Colorado. Association for Computational Linguistics.
  * Agirre et al. (2014) Eneko Agirre, Carmen Banea, Claire Cardie, Daniel Cer, Mona Diab, Aitor Gonzalez-Agirre, Weiwei Guo, Rada Mihalcea, German Rigau, and Janyce Wiebe. 2014\.  SemEval-2014 task 10: Multilingual semantic textual similarity.  In _Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014)_ , pages 81–91, Dublin, Ireland. Association for Computational Linguistics.
  * Agirre et al. (2016) Eneko Agirre, Carmen Banea, Daniel Cer, Mona Diab, Aitor Gonzalez-Agirre, Rada Mihalcea, German Rigau, and Janyce Wiebe. 2016.  SemEval-2016 task 1: Semantic textual similarity, monolingual and cross-lingual evaluation.  In _Proceedings of the 10th International Workshop on Semantic Evaluation (SemEval-2016)_ , pages 497–511, San Diego, California. Association for Computational Linguistics.
  * Agirre et al. (2012) Eneko Agirre, Daniel Cer, Mona Diab, and Aitor Gonzalez-Agirre. 2012.  SemEval-2012 task 6: A pilot on semantic textual similarity.  In _*SEM 2012: The First Joint Conference on Lexical and Computational Semantics – Volume 1: Proceedings of the main conference and the shared task, and Volume 2: Proceedings of the Sixth International Workshop on Semantic Evaluation (SemEval 2012)_ , pages 385–393, Montréal, Canada. Association for Computational Linguistics.
  * Agirre et al. (2013) Eneko Agirre, Daniel Cer, Mona Diab, Aitor Gonzalez-Agirre, and Weiwei Guo. 2013\.  *SEM 2013 shared task: Semantic textual similarity.  In _Second Joint Conference on Lexical and Computational Semantics (*SEM), Volume 1: Proceedings of the Main Conference and the Shared Task: Semantic Textual Similarity_ , pages 32–43, Atlanta, Georgia, USA. Association for Computational Linguistics.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Carlsson et al. (2021) Fredrik Carlsson, Amaru Cuba Gyllensten, Evangelia Gogoulou, Erik Ylipää Hellqvist, and Magnus Sahlgren. 2021.  Semantic re-tuning with contrastive tension.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Caron et al. (2020) Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. 2020.  Unsupervised learning of visual features by contrasting cluster assignments.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Cer et al. (2017) Daniel Cer, Mona Diab, Eneko Agirre, Iñigo Lopez-Gazpio, and Lucia Specia. 2017\.  SemEval-2017 task 1: Semantic textual similarity multilingual and crosslingual focused evaluation.  In _Proceedings of the 11th International Workshop on Semantic Evaluation (SemEval-2017)_ , pages 1–14, Vancouver, Canada. Association for Computational Linguistics.
  * Chen and He (2021) Xinlei Chen and Kaiming He. 2021.  Exploring simple siamese representation learning.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021_ , pages 15750–15758. Computer Vision Foundation / IEEE.
  * Conneau and Kiela (2018) Alexis Conneau and Douwe Kiela. 2018.  Senteval: An evaluation toolkit for universal sentence representations.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation, LREC 2018, Miyazaki, Japan, May 7-12, 2018_. European Language Resources Association (ELRA).
  * Cui et al. (2021) Leyang Cui, Yu Wu, Jian Liu, Sen Yang, and Yue Zhang. 2021.  Template-based named entity recognition using BART.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 1835–1845, Online. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _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 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Ding et al. (2021) Ning Ding, Xiaobin Wang, Yao Fu, Guangwei Xu, Rui Wang, Pengjun Xie, Ying Shen, Fei Huang, Hai-Tao Zheng, and Rui Zhang. 2021.  Prototypical representation learning for relation extraction.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Dolan et al. (2004) Bill Dolan, Chris Quirk, and Chris Brockett. 2004.  Unsupervised construction of large paraphrase corpora: Exploiting massively parallel news sources.  In _COLING 2004, 20th International Conference on Computational Linguistics, Proceedings of the Conference, 23-27 August 2004, Geneva, Switzerland_.
  * Gao et al. (2021a) Tianyu Gao, Adam Fisch, and Danqi Chen. 2021a.  Making pre-trained language models better few-shot learners.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3816–3830, Online. Association for Computational Linguistics.
  * Gao et al. (2021b) Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021b.  SimCSE: Simple contrastive learning of sentence embeddings.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6894–6910, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Giorgi et al. (2021) John Giorgi, Osvald Nitski, Bo Wang, and Gary Bader. 2021.  DeCLUTR: Deep contrastive learning for unsupervised textual representations.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 879–895, Online. Association for Computational Linguistics.
  * Hill et al. (2016) Felix Hill, Kyunghyun Cho, and Anna Korhonen. 2016.  Learning distributed representations of sentences from unlabelled data.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1367–1377, San Diego, California. Association for Computational Linguistics.
  * Hu and Liu (2004) Minqing Hu and Bing Liu. 2004.  Mining and summarizing customer reviews.  In _Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, Washington, USA, August 22-25, 2004_ , pages 168–177. ACM.
  * Hu et al. (2021) Shengding Hu, Ning Ding, Huadong Wang, Zhiyuan Liu, Juanzi Li, and Maosong Sun. 2021\.  Knowledgeable prompt-tuning: Incorporating knowledge into prompt verbalizer for text classification.  _arXiv preprint arXiv:2108.02035_.
  * Jiang et al. (2022) Ting Jiang, Shaohan Huang, Zihan Zhang, Deqing Wang, Fuzhen Zhuang, Furu Wei, Haizhen Huang, Liangjie Zhang, and Qi Zhang. 2022.  Promptbert: Improving bert sentence embeddings with prompts.  _arXiv preprint arXiv:2201.04337_.
  * Kiros et al. (2015) Ryan Kiros, Yukun Zhu, Ruslan Salakhutdinov, Richard S. Zemel, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. 2015.  Skip-thought vectors.  In _Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada_ , pages 3294–3302.
  * Lan et al. (2021) Jinhe Lan, Qingyuan Zhan, Chenhao Jiang, Kunping Yuan, and Desheng Wang. 2021.  CLLD: contrastive learning with label distance for text classificatioin.  _CoRR_ , abs/2110.13656.
  * Li et al. (2020a) Bohan Li, Hao Zhou, Junxian He, Mingxuan Wang, Yiming Yang, and Lei Li. 2020a.  On the sentence embeddings from pre-trained language models.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9119–9130, Online. Association for Computational Linguistics.
  * Li et al. (2020b) Junnan Li, Pan Zhou, Caiming Xiong, and Steven CH Hoi. 2020b.  Prototypical contrastive learning of unsupervised representations.  _Proceedings of ICLR 2021_.
  * Li and Liang (2021) Xiang Lisa Li and Percy Liang. 2021.  Prefix-tuning: Optimizing continuous prompts for generation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4582–4597, Online. Association for Computational Linguistics.
  * Li and Roth (2002) Xin Li and Dan Roth. 2002.  Learning question classifiers.  In _19th International Conference on Computational Linguistics, COLING 2002, Howard International House and Academia Sinica, Taipei, Taiwan, August 24 - September 1, 2002_.
  * Liu et al. (2021) Xiao Liu, Yanan Zheng, Zhengxiao Du, Ming Ding, Yujie Qian, Zhilin Yang, and Jie Tang. 2021.  Gpt understands, too.  _arXiv preprint arXiv:2103.10385_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Logeswaran and Lee (2018) Lajanugen Logeswaran and Honglak Lee. 2018.  An efficient framework for learning sentence representations.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net.
  * Marelli et al. (2014) Marco Marelli, Stefano Menini, Marco Baroni, Luisa Bentivogli, Raffaella Bernardi, and Roberto Zamparelli. 2014.  A SICK cure for the evaluation of compositional distributional semantic models.  In _Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)_ , pages 216–223, Reykjavik, Iceland. European Language Resources Association (ELRA).
  * Meng et al. (2021) Yu Meng, Chenyan Xiong, Payal Bajaj, Paul Bennett, Jiawei Han, Xia Song, et al. 2021\.  Coco-lm: Correcting and contrasting text sequences for language model pretraining.  _Advances in Neural Information Processing Systems_ , 34.
  * Pagliardini et al. (2018) Matteo Pagliardini, Prakhar Gupta, and Martin Jaggi. 2018.  Unsupervised learning of sentence embeddings using compositional n-gram features.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 528–540, New Orleans, Louisiana. Association for Computational Linguistics.
  * Pang and Lee (2004) Bo Pang and Lillian Lee. 2004.  A sentimental education: Sentiment analysis using subjectivity summarization based on minimum cuts.  In _Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, 21-26 July, 2004, Barcelona, Spain_ , pages 271–278. ACL.
  * Pang and Lee (2005) Bo Pang and Lillian Lee. 2005.  Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales.  In _ACL 2005, 43rd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, 25-30 June 2005, University of Michigan, USA_ , pages 115–124. The Association for Computer Linguistics.
  * Pedregosa et al. (2011) Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake VanderPlas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesnay. 2011.  Scikit-learn: Machine learning in python.  _J. Mach. Learn. Res._ , 12:2825–2830.
  * Phan et al. (2008) Xuan Hieu Phan, Minh Le Nguyen, and Susumu Horiguchi. 2008.  Learning to classify short and sparse text & web with hidden topics from large-scale data collections.  In _Proceedings of the 17th International Conference on World Wide Web, WWW 2008, Beijing, China, April 21-25, 2008_ , pages 91–100. ACM.
  * Reimers and Gurevych (2019a) Nils Reimers and Iryna Gurevych. 2019a.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , pages 3980–3990. Association for Computational Linguistics.
  * Reimers and Gurevych (2019b) Nils Reimers and Iryna Gurevych. 2019b.  Sentence-BERT: Sentence embeddings using Siamese BERT-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3982–3992, Hong Kong, China. Association for Computational Linguistics.
  * Sanh et al. (2021) Victor Sanh, Albert Webson, Colin Raffel, Stephen H. Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, Manan Dey, M. Saiful Bari, Canwen Xu, Urmish Thakker, Shanya Sharma, Eliza Szczechla, Taewoon Kim, Gunjan Chhablani, Nihal V. Nayak, Debajyoti Datta, Jonathan Chang, Mike Tian-Jian Jiang, Han Wang, Matteo Manica, Sheng Shen, Zheng Xin Yong, Harshit Pandey, Rachel Bawden, Thomas Wang, Trishala Neeraj, Jos Rozen, Abheesht Sharma, Andrea Santilli, Thibault Févry, Jason Alan Fries, Ryan Teehan, Stella Biderman, Leo Gao, Tali Bers, Thomas Wolf, and Alexander M. Rush. 2021.  Multitask prompted training enables zero-shot task generalization.  _CoRR_ , abs/2110.08207.
  * Schick and Schütze (2021a) Timo Schick and Hinrich Schütze. 2021a.  Exploiting cloze-questions for few-shot text classification and natural language inference.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 255–269, Online. Association for Computational Linguistics.
  * Schick and Schütze (2021b) Timo Schick and Hinrich Schütze. 2021b.  Few-shot text generation with natural language instructions.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 390–402, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Sharma et al. (2020) Vivek Sharma, Makarand Tapaswi, M. Saquib Sarfraz, and Rainer Stiefelhagen. 2020\.  Clustering based contrastive learning for improving face representations.  In _15th IEEE International Conference on Automatic Face and Gesture Recognition, FG 2020, Buenos Aires, Argentina, November 16-20, 2020_ , pages 109–116. IEEE.
  * Shin et al. (2020) Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Eric Wallace, and Sameer Singh. 2020.  AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 4222–4235, Online. Association for Computational Linguistics.
  * Si et al. (2021) Jinghui Si, Xutan Peng, Chen Li, Haotian Xu, and Jianxin Li. 2021.  Generating disentangled arguments with prompts: A simple event extraction framework that works.  _arXiv preprint arXiv:2110.04525_.
  * Socher et al. (2013) Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. 2013.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, EMNLP 2013, 18-21 October 2013, Grand Hyatt Seattle, Seattle, Washington, USA, A meeting of SIGDAT, a Special Interest Group of the ACL_ , pages 1631–1642. ACL.
  * Su et al. (2021) Jianlin Su, Jiarun Cao, Weijie Liu, and Yangyiwen Ou. 2021.  Whitening sentence representations for better semantics and faster retrieval.  _arXiv preprint arXiv:2103.15316_.
  * van der Maaten and Hinton (2008) Laurens van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-sne.  _Journal of Machine Learning Research_ , 9(86):2579–2605.
  * Wang et al. (2021a) Dong Wang, Ning Ding, Piji Li, and Haitao Zheng. 2021a.  CLINE: Contrastive learning with semantic negative examples for natural language understanding.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 2332–2342, Online. Association for Computational Linguistics.
  * Wang et al. (2022) Hao Wang, Yangguang Li, Zhen Huang, Yong Dou, Lingpeng Kong, and Jing Shao. 2022\.  Sncse: Contrastive learning for unsupervised sentence embedding with soft negative samples.  _arXiv preprint arXiv:2201.05979_.
  * Wang et al. (2021b) Kexin Wang, Nils Reimers, and Iryna Gurevych. 2021b.  TSDAE: using transformer-based sequential denoising auto-encoderfor unsupervised sentence embedding learning.  In _Findings of the Association for Computational Linguistics: EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 16-20 November, 2021_ , pages 671–688. Association for Computational Linguistics.
  * Wei et al. (2021) Jason Wei, Maarten Bosma, Vincent Y. Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M. Dai, and Quoc V. Le. 2021.  Finetuned language models are zero-shot learners.  _CoRR_ , abs/2109.01652.
  * Wei et al. (2022) Yinyi Wei, Tong Mo, Yongtao Jiang, Weiping Li, and Wen Zhao. 2022.  Eliciting knowledge from pretrained language models for prototypical prompt verbalizer.  _CoRR_ , abs/2201.05411.
  * Wiebe et al. (2005) Janyce Wiebe, Theresa Wilson, and Claire Cardie. 2005.  Annotating expressions of opinions and emotions in language.  _Lang. Resour. Evaluation_ , 39(2-3):165–210.
  * Wu et al. (2021) Xing Wu, Chaochen Gao, Liangjun Zang, Jizhong Han, Zhongyuan Wang, and Songlin Hu. 2021.  Esimcse: Enhanced sample building method for contrastive learning of unsupervised sentence embedding.  _CoRR_ , abs/2109.04380.
  * Wu et al. (2020) Zhuofeng Wu, Sinong Wang, Jiatao Gu, Madian Khabsa, Fei Sun, and Hao Ma. 2020.  Clear: Contrastive learning for sentence representation.  _arXiv preprint arXiv:2012.15466_.
  * Xu et al. (2017) Jiaming Xu, Bo Xu, Peng Wang, Suncong Zheng, Guanhua Tian, and Jun Zhao. 2017.  Self-taught convolutional neural networks for short text clustering.  _Neural Networks_ , 88:22–31.
  * Yan et al. (2021) Yuanmeng Yan, Rumei Li, Sirui Wang, Fuzheng Zhang, Wei Wu, and Weiran Xu. 2021.  ConSERT: A contrastive framework for self-supervised sentence representation transfer.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 5065–5075, Online. Association for Computational Linguistics.
  * Yin and Wang (2016) Jianhua Yin and Jianyong Wang. 2016.  A model-based approach for text clustering with outlier detection.  In _32nd IEEE International Conference on Data Engineering, ICDE 2016, Helsinki, Finland, May 16-20, 2016_ , pages 625–636. IEEE Computer Society.
  * Zhang et al. (2021) Dejiao Zhang, Shang-Wen Li, Wei Xiao, Henghui Zhu, Ramesh Nallapati, Andrew O. Arnold, and Bing Xiang. 2021.  Pairwise supervised contrastive learning of sentence representations.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021_ , pages 5786–5798. Association for Computational Linguistics.
  * Zhang and LeCun (2015) Xiang Zhang and Yann LeCun. 2015.  Text understanding from scratch.  _CoRR_ , abs/1502.01710.
  * Zhang et al. (2020) Yan Zhang, Ruidan He, Zuozhu Liu, Kwan Hui Lim, and Lidong Bing. 2020.  An unsupervised sentence embedding method by mutual information maximization.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1601–1610, Online. Association for Computational Linguistics.