# Total positivity for matroid Schubert varieties

Xuhua He  Department of Mathematics and New Cornerstone Science Laboratory,
The University of Hong Kong, Pokfulam, Hong Kong, Hong Kong SAR, China
<EMAIL_ADDRESS>,  Connor Simpson  Department of Mathematics, University of
Wisconsin—Madison, 480 Lincoln Drive, Madison WI 53706-1388, USA
<EMAIL_ADDRESS>and  Kaitao Xie  Department of Mathematics and New
Cornerstone Science Laboratory, The University of Hong Kong, Pokfulam, Hong
Kong, Hong Kong SAR, China<EMAIL_ADDRESS>
###### Abstract.

We define the totally nonnegative matroid Schubert variety $\mathcal{Y}_{V}$
of a linear subspace $V\subset\mathbb{R}^{n}$. We show that $\mathcal{Y}_{V}$
is a regular CW complex homeomorphic to a closed ball, with strata indexed by
pairs of acyclic flats of the oriented matroid of $V$. This closely resembles
the regularity theorem for totally nonnegative generalized flag varieties. As
a corollary, we obtain a regular CW structure on the real matroid Schubert
variety of $V$.

##  1\. Introduction

###  1.1. Matroids

Matroids model the combinatorics of linear subspaces, and have found broad
application in and out of mathematics [RST20, Rec11, Iri83] since their
formulation by Nakasawa [Nak35] and Whitney [Whi35]. They enjoy a particularly
close relationship with algebraic geometry [Kat14, Ard21].

In this work we study the so-called “matroid Schubert varieties”. If
$V\subset\mathbb{K}^{n}$ is a linear subspace, then its matroid Schubert
variety $Y_{V}$ is the Zariski closure of $V$ in
$(\mathbb{P}_{\mathbb{K}}^{1})^{n}$, which contains $\mathbb{K}^{n}$ as an
open subset. Introduced by [AB16], matroid Schubert varieties are central to
the proof of the Top Heavy Conjecture for realizable matroids [HW17], guide
the conjecture’s resolution for all matroids [Bra+20], and are the geometric
model for matroidal Kazhdan-Lusztig theory [EPW16]. Preceding [AB16], a
neighborhood of the most singular point of a matroid Schubert variety was
studied in [PS06] and [Ter02].

The geometry of $Y_{V}$ is controlled by the flats of $V$; that is, the sets
$F\subset\\{1,\ldots,n\\}$ such that there is $v\in V$ whose zero coordinates
are exactly those indexed by $F$. The flats of $V$ are an example of a
matroid. When $\mathbb{K}=\mathbb{R}$, we may consider the more refined notion
of covectors, which record the combinations of signs that the coordinate
functions of $\mathbb{R}^{n}$ can take on $V$. This data gives an example of
an oriented matroid. Our main theorem says that oriented matroid data controls
the geometry of the totally non-negative matroid Schubert variety
$\mathcal{Y}_{V}:=\overline{V\cap\mathbb{R}_{\geq 0}^{n}}^{\mathrm{an}}$, the
closure of $V\cap\mathbb{R}_{\geq 0}^{n}$ in
$(\mathbb{P}_{\mathbb{R}}^{1})^{n}$ with respect to the analytic topology.

###  1.2. Total positivity

By definition, an invertible real matrix is called totally positive if all the
minors are positive and totally non-negative if all the minors are non-
negative. These notions were introduced in the 1930s by Schoenberg [Sch30].
The theory of totally positive real matrices was further developed by Whitney
and Loewner in the 1950s and found important applications in many different
areas, including, for example, statistics, game theory, mathematical
economics, and stochastic processes. We refer to the book by Karlin [Kar68]
for detailed discussions.

All $n\times n$ invertible matrices form the general linear group, which is an
example of a split reductive group. The theory of total positivity for an
arbitrary split real reductive group was developed by Lusztig in his
foundational work [Lus94] and has had significant impacts on many active
research directions, including, among others,

  * •

the theory of cluster algebras by Fomin and Zelevinsky [FZ02],

  * •

higher Teichmüller theory by Fock and Goncharov [FG06],

  * •

the theory of the amplituhedron by Arkani-Hamed and Trnka [AT14].

It has also been discovered that many spaces with $G$-action have natural
positive structures. A typical example is the (partial) flag variety
$\mathcal{P}$. This has a natural decomposition into (open) Richardson
varieties: $\mathcal{P}=\sqcup_{\alpha}\mathcal{P}_{\alpha}$. This is a
stratification, i.e., the closure of each $\mathcal{P}_{\alpha}$ (under the
Zariski topology) is a disjoint union of other Richardson varieties
$\mathcal{P}_{\beta}$. On the other hand, Lusztig defined the totally non-
negative flag $\mathcal{P}_{\geq 0}$. This is a semi-algebraic subvariety of
$\mathcal{B}$. We then have the decomposition

$\mathcal{P}_{\geq 0}=\bigsqcup_{\alpha}\mathcal{P}_{\alpha,>0},\quad\text{
where }\mathcal{P}_{>0}=\mathcal{P}_{\geq 0}\cap\mathcal{P}_{\alpha}.$

Lusztig refers to the totally non-negative flag as a “remarkable polyhedral
space”. It has been studied by many leading experts: Bao, Galashin, Karp, Lam,
Lusztig, Marsh, Postnikov, Rietsch, Williams, the first-named author, and
others. They have established many remarkable geometric/topological
properties, including the following:

  * •

Connected components: $\mathcal{P}_{\alpha,>0}$ is a connected component of
$\mathcal{P}_{\alpha}(\mathbb{R})$.

  * •

Cell structure:
$\mathcal{P}_{\alpha,>0}\cong\mathbb{R}_{>0}^{\dim\mathcal{P}_{\alpha}}$ is a
semi-algebraic cell.

  * •

Cellular decomposition: $\overline{\mathcal{P}_{\alpha,>0}}^{\mathrm{an}}$ is
a disjoint union of other totally positive cells $\mathcal{P}_{\beta,>0}$.

  * •

Regularity property: $\overline{\mathcal{P}_{\alpha,>0}}^{\mathrm{an}}$ is a
regular CW complex homeomorphic to a closed ball.

###  1.3. Main result

One may expect that matroid Schubert varieties admits a “nice” positive
structure, similar to the flag varieties. This is what we will establish in
this paper.

Let $E$ be a finite set. If $V\subset\mathbb{R}^{E}$ is a linear subspace,
then $Y_{V}\subset(\mathbb{P}_{\mathbb{R}}^{1})^{n}$ can be decomposed as a
disjoint union of locally closed “Richardson varieties”
$Y_{FG}^{\circ}:=Y_{V}\cap(0^{F}\times\mathbb{R}_{\neq 0}^{G\setminus
F}\times\infty^{E\setminus F})$, with $F\subset G\subset E$ running over all
flats of $V$. For any sets $F\subset G\subset E$, we analogously define
$\mathcal{Y}_{FG}^{\circ}:=\mathcal{Y}_{V}\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F}\times\infty^{E\setminus G})$, and let
$\mathcal{Y}_{FG}:=\overline{\mathcal{Y}_{FG}^{\circ}}^{\mathrm{an}}$. Note
that $\mathcal{Y}_{\emptyset,E}=\mathcal{Y}_{V}$ by definition. Call a flat
$F$ of $V$ acyclic if $V\cap(0^{F}\times\mathbb{R}_{>0}^{E\setminus F})$ is
nonempty. The rank of a flat is the codimension in $V$ of the subspace
$V\cap\\{x_{i}=0:i\in F\\}$.

The main result of this paper is that the totally non-negative matroid
Schubert variety is a “remarkable polyhedral space”. More precisely,

######  Theorem 1.1.

Let $V\subset\mathbb{R}^{E}$, with matroid Schubert variety $Y_{V}$ and
totally non-negative Schubert variety $\mathcal{Y}_{V}$.

  1. (i)

$\mathcal{Y}_{FG}^{\circ}$ is nonempty if and only if $F\subset G$ are acyclic
flats of $V$. In this case, $\mathcal{Y}_{FG}^{\circ}$ is a single connected
component of $Y_{FG}^{\circ}$, and is a semi-algebraic cell isomorphic to
$(\mathbb{R}_{>0})^{\operatorname{rk}(G)-\operatorname{rk}(F)}$.

  2. (ii)

The closure $\mathcal{Y}_{FG}$ of a nonempty cell $\mathcal{Y}_{FG}^{\circ}$
decomposes as the disjoint union of cells
$\mathcal{Y}_{F^{\prime},G^{\prime}}^{\circ}$ with $F\subset F^{\prime}\subset
G^{\prime}\subset G$.

  3. (iii)

This decomposition makes $\mathcal{Y}_{FG}$ a regular CW complex homeomorphic
to a closed ball.

Some comparison is due. Combinatorially, we see a new phenomenon in the
matroid setting. The cells of $\mathcal{P}_{\geq 0}$ and $\mathcal{Y}_{V}$ are
obtained by intersecting these sets with real Richardson strata of
$\mathcal{P}$ and $Y_{V}$, respectively. The poset of boundary strata of
$\mathcal{P}$ is thin—that is, every interval of length two has exactly four
elements—and $\mathcal{P}_{\geq 0}$ contains exactly one connected component
of every stratum. Hence, the poset of cells in the boundary of
$\mathcal{P}_{\geq 0}$ is also thin, a fact which is helpful for establishing
the regularity property. On the other hand, the poset of boundary strata of
$Y_{V}$ is _not_ thin. However, $\mathcal{Y}_{V}$ fails to meet all strata of
$Y_{V}$, and surprisingly, its cell poset _is_ thin. As in the Lie-theoretic
setting, this fact helps us to establish regularity.

Geometrically, the Richardson strata of matroid Schubert varieties are simpler
than those of flag varieties. In the matroid Schubert case, each Richardson
stratum is a hyperplane arrangement complement. Every connected component of a
real hyperplane arrangement complement is homeomorphic to an open ball.
However, a real open Richardson variety in a flag variety may have connected
components with nontrivial topology (see, e.g. [MR00]). The relative
simplicity of the matroid case’s geometry allows us to show that
$\mathcal{Y}_{V}$ is a ball by directly exhibiting it as a cone over a closed
ball in its boundary, bypassing such high-powered tools as the Poincaré
conjecture, which underpins the known proofs of 1.1’s Lie-theoretic analogues.

######  Example 1.2.

Let $V\subset\mathbb{R}^{5}$ be the linear subspace cut out by

$\displaystyle x_{1}+x_{2}-x_{3}=x_{3}-x_{4}-x_{5}=0.$

The poset of flats of $V$ (below left) is _not_ thin, so its interval poset,
which indexes strata of $Y_{V}$, is also _not_ thin. On the other hand, the
subposet of acyclic flats (below right) _is_ thin, so its interval poset,
which indexes cells of $\mathcal{Y}_{V}$ is also thin.

$E$$123$$14$$24$$25$$15$$345$$1$$2$$3$$4$$5$$\emptyset$

$E$$14$$24$$15$$25$$1$$2$$4$$5$$\emptyset$

The non-negative matroid Schubert variety $\mathcal{Y}_{V}$ (below) is
homeomorphic to a closed 3-ball. Cells of $\mathcal{Y}_{V}$ are indexed by
intervals in the poset of acyclic flats, ordered by inclusion. Hence, the
cells structure of $\mathcal{Y}_{V}$ has ten 0-cells and sixteen 1-cells
(labelled), along with eight 2-cells and one 3-cell (unlabelled). One sees
immediately that the closure of any cell is homeomorphic to a closed ball, so
the cell structure is regular.

$\diamondsuit$

### Acknowledgements

XH is partially supported by the New Cornerstone Foundation through the New
Cornerstone Investigator Program and the Xplorer prize, and by Hong Kong RGC
Grant 14300023. CS thanks: Xuhua for his support & hospitality during the
visits that enabled this collaboration, Botong Wang for helpful conversation,
and both CUHK and BICMR for pleasant working environments.

##  2\. Matroids and oriented matroids

We review aspects of (oriented) matroid theory, comprehensively explored in
[Whi86] and [Bjö+99], and state the main properties of matroid Schubert
varieties.

### 2.1.

We may omit braces when writing one-element sets, e.g. “$\\{1,2\\}\cup i$”
means “$\\{1,2\\}\cup\\{i\\}$” and “$\\{1,2\\}\times 0$” means
“$\\{1,2\\}\times\\{0\\}$”. If $E$ and $K$ are sets, with $E$ finite, then
$K^{E}:=\prod_{i\in E}K$. If $F\subset E$, then $\pi_{F}:K^{E}\to K^{F}$ is
the projection. If all factors in a product are single-element sets, then we
may omit notation for the product, e.g. “$\\{0\\}\times\\{1\\}\times\\{1\\}$”
will be written $0^{\\{1\\}}1^{\\{2,3\\}}$, and $0^{E}$ represents the origin
of $\mathbb{R}^{E}$. Both conventions on singletons will be violated as
necessary to avoid confusion.

Throughout this paper, $E$ will denote a finite set.

In addition to sets, we will need to work with signed sets; that is, elements
of $\\{-,0,+\\}^{E}$. If $X$ is a signed set, write $X^{-}$, $X^{0}$, and
$X^{+}$ for the coordinates of $X$ that have value $-$, $0$, and $+$,
respectively. We define $-X$ to be the signed set with $(-X)^{-}:=X^{+}$,
$(-X)^{0}:=X^{0}$, and $(-X)^{+}:=X^{-}$. If $X$ and $Y$ are signed sets, then
their composition is given by

$(X\circ Y)_{i}:=\begin{cases}X_{i},&\text{if $X_{i}\neq 0$}\\\
Y_{i},&\text{otherwise.}\end{cases}$

Say $X$ is contained in $Y$, and write $X\leq Y$, if $X^{+}\subset Y^{+}$ and
$X^{-}\subset Y^{-}$.

For most terminology on posets, we refer to [Sta11]. The opposite of a poset
$P$ is $P^{op}$, the poset on the same underlying set as $P$, but with order
reversed.

### 2.2.

A matroid on a finite set $E$ is defined by a collection of flats $F\subset E$
such that (i) $E$ is a flat, (ii) the intersection of two flats is a flat, and
(iii) if $F$ is a flat and $i\in E\setminus F$, then there is a unique
smallest flat containing $F\cup i$. The flats of a linear subspace, defined in
Section 1.1, satisfy these properties, giving us a recipe for producing a
matroid from a linear subspace.

When ordered by inclusion, the flats of a matroid $\underline{M}$ form a
graded lattice. The rank of $\underline{M}$, denoted
$\operatorname{rk}(\underline{M})$, is the length of any maximal chain in this
poset. More generally, the rank of a flat $F$ of $\underline{M}$ is the length
of any maximal chain of flats contained in $F$, and is denoted
$\operatorname{rk}(F)$. The loops of $\underline{M}$ are the elements of the
minimal flat of $\underline{M}$. Call $\underline{M}$ loopless if its minimum
flat is empty.

If $F\subset E$ is a flat of $\underline{M}$, then we can form the restriction
$\underline{M}|_{F}$ and contraction $\underline{M}/F$, matroids on $F$ and
$E$, respectively, with flats

$\\{G\subset F:\text{$G$ is a flat of
$\underline{M}$}\\}\quad\text{and}\quad\\{G\supset F:\text{$G\supset F$ is a
flat of $\underline{M}$}\\}.$

######  Remark 2.1 (Matroids and linear algebra).

If $\mathbb{K}$ is a field and $V\subset\mathbb{K}^{E}$ is a linear subspace,
then the flats of $V$ defined in Section 1.1 are the flats of a matroid
$\underline{M}$. The rank of $\underline{M}$ is $\dim V$. Any matroid that
arises in this manner is realizable, and $V$ is its realization.

Let $\pi_{F}:\mathbb{K}^{E}\to\mathbb{K}^{F}$ be the coordinate projection.
The restriction of $\underline{M}$ to $F$ is realized by
$\pi_{F}(V)\subset\mathbb{K}^{F}$, and the contraction $\underline{M}/F$ is
realized by $V\cap\ker(\pi_{F})$. The element $i\in E$ is a loop of
$\underline{M}$ if and only if $\pi_{i}(V)=\\{0\\}$.

Let $\mathbb{K}$ be a field and $V\subset\mathbb{K}^{E}$. Recall (from Section
1.1) that the matroid Schubert variety $Y_{V}$ associated to a linear subspace
$V\subset\mathbb{K}^{E}$ is the Zariski closure of $V$ in
$(\mathbb{K}\cup\infty)^{E}=(\mathbb{P}_{\mathbb{K}}^{1})^{E}$. For each pair
of flats $F\subset G$ of $V$, let
$Y_{FG}^{\circ}:=Y_{V}\cap(0^{F}\times(\mathbb{K}_{\neq 0})^{G\setminus
F}\times\infty^{E\setminus G})$, and let $Y_{FG}$ be the Zariski closure of
$Y_{FG}^{\circ}$.

######  Theorem 2.2.

[PXY18, Section 7] Let $\mathbb{K}$ be a field. Let $V\subset\mathbb{K}^{E}$
be a linear subspace, with associated matroid $\underline{M}$.

  1. (i)

The intersection $Y_{V}\cap(\mathbb{K}^{F}\times\infty^{E\setminus F})$ is
nonempty if and only if $F$ is a flat, in which case the intersection is equal
to $\pi_{F}(V)\times\infty^{E\setminus F}$.

  2. (ii)

If $F$ is a flat, then
$Y_{V}\cap\big{(}(\mathbb{P}^{1}_{\mathbb{K}})^{F}\times\infty^{E\setminus
F}\big{)}=Y_{\pi_{F}(V)}\times\infty^{E\setminus F}$.

  3. (iii)

If $F$ is a flat, then
$Y_{V}\cap\big{(}0^{F}\times(\mathbb{P}^{1}_{\mathbb{K}})^{E\setminus
F}\big{)}=Y_{V\cap\ker(\pi_{F})}$.

  4. (iv)

$Y_{FG}$ is the disjoint union of all $Y_{F^{\prime}G^{\prime}}^{\circ}$ with
$F\subset F^{\prime}\subset G^{\prime}\subset G$.

If $L$ is the set of loops of $V$’s matroid, then $Y_{V}=0^{L}\times
Y_{\pi_{E\setminus L}(V)}$, so we lose little by assuming the matroid of $V$
is loopless.

### 2.3.

An oriented matroid $M$ on a finite set $E$ is the data of a collection of
covectors $\mathcal{C}\subset\\{-,0,+\\}^{E}$ such that

  1. (i)

$0^{E}\in\mathcal{C}$,

  2. (ii)

$\mathcal{C}$ is closed under composition and negation

  3. (iii)

If $X,Y\in\mathcal{C}$ and $X(i)=-Y(i)\neq 0$, then there exists
$Z\in\mathcal{C}$ such that $Z(i)=0$ and $Z(j)=(X\circ Y)_{j}=(Y\circ X)_{j}$
for all $j$ such that $X_{j}=Y_{j}$.

The above axioms imply the collection $\\{X^{0}:X\in\mathcal{C}\\}$ is the
flats of a matroid $\underline{M}$, the underlying matroid of $M$. Flats and
loops of an oriented matroid are those of its underlying matroid.

Ordering $\\{-,0,+\\}$ by $0<-$ and $0<+$, we induce a partial order on
$\mathcal{C}$. The poset $\mathcal{C}\cup\\{\hat{1}\\}$, formed by adjoining a
maximum to $\mathcal{C}$, is a graded lattice. Maximal covectors are called
topes.

Fix $A\subset E$. By negating in each covector the coordinates indexed by $A$,
we obtain a new subset $\mathcal{C}^{\prime}\subset\\{-,0,+\\}^{E}$. In fact,
$\mathcal{C}^{\prime}$ the covectors of an oriented matroid $M^{\prime}$,
called a reorientation of $M$. Evidently, $\mathcal{C}$ and
$\mathcal{C}^{\prime}$ are isomorphic as posets, and the underlying matroids
of $M$ and $M^{\prime}$ are equal.

Given $F\subset E$ a flat of an oriented matroid $M$ on $E$, the restriction
of $M$ to $F$ and contraction of $M$ by $F$ are the oriented matroids $M|_{F}$
and $M/F$ defined by

$\mathcal{C}(M|_{F}):=\\{\pi_{F}(X):X\in\mathcal{C}(M)\\}\quad\text{ and
}\quad\mathcal{C}(M/F):=\\{X:X\in\mathcal{C}(M),\;F\subset X^{0}\\}.$

From this description, one sees that the topes of $M/F$ are the covectors $X$
with $X^{0}=F$. The underlying matroids of $M|_{F}$ and $M/F$ are
$\underline{M}|_{F}$ and $\underline{M}/F$, respectively.

######  Remark 2.3 (Oriented matroids and linear algebra).

The sign map is $s:\mathbb{R}^{E}\to\\{-,0,+\\}^{E}$ defined by

$s(v)_{i}=\begin{cases}-,&\pi_{i}(v)<0,\\\ 0,&\pi_{i}(v)=0,\\\
+,&\pi_{i}(v)>0.\end{cases}$

The sign map explains composition: if $v,w\in\mathbb{R}^{E}$, then $s(v)\circ
s(w)=s(v+\epsilon w)$ for small $\epsilon>0$. If $V\subset\mathbb{R}^{E}$ is a
linear subspace, then $\\{s(v):v\in V\\}$ is the covectors of an oriented
matroid. An oriented matroid $M$ that arises in this way is called realizable,
and $V$ its realization. Reorientations of $M$ are obtained by negating some
of the coordinate functions on $\mathbb{R}^{E}$.

By intersecting the coordinate hyperplanes of $\mathbb{R}^{E}$ with $V$, we
obtain a hyperplane arrangement in $V$. The topes of $M$ correspond to the
connected components of the arrangement complement. More generally, each
region of the arrangement is the preimage under $s$ of a covector of $M$. The
poset of the regions’ closures, ordered by containment, is isomorphic to the
poset of covectors of $M$.

### 2.4.

An acyclic flat111Acyclic flats may be called “positive flats” elsewhere in
the literature, e.g. [ARW06, AKW04]. of an oriented matroid $M$ is a flat $F$
of $M$ such that $0^{F}+^{E\setminus F}$ is a covector of $M$. When ordered by
containment, the acyclic flats form a lattice $\mathcal{L}$, called the Las
Vergnas face lattice of $M$.

######  Proposition 2.4.

Let $F$ be a flat of an oriented matroid $M$.

  1. (i)

$H\supset F$ is an acyclic flat of $M/F$ if and only if $H$ is an acyclic flat
of $M$.

  2. (ii)

If $F$ is an acyclic flat, then $G\subset F$ is an acyclic flat of $M|_{F}$ if
and only if $G$ is an acyclic flat of $M$.

###### Proof.

  1. (i)

If $H\supset F$, then $0^{H}+^{E\setminus H}$ is a covector of $M$ if and only
if it is a covector of $M/F$.

  2. (ii)

Suppose $F$ is an acyclic flat. If $G\subset F$ is an acyclic flat of $M$,
then $0^{G}+^{E\setminus G}$ is a covector of $M$, so $0^{G}+^{F\setminus G}$
is an acyclic flat of $M|_{F}$.

Conversely, suppose $G$ is an acyclic flat of $M|_{F}$; in other words, there
is a covector $Y$ of $M$ such that $Y^{0}\supset G$ and $Y^{+}\supset
F\setminus G$. Since $F$ is an acyclic flat, there is also a covector $X$ of
$M$ with $X^{0}=F$ and $X^{+}=E\setminus F$. Their composition satisfies
$(X\circ Y)^{0}=F\cap G=G$ and

$(X\circ Y)^{+}=X^{+}\cup(Y^{+}\setminus X^{-})\supset(E\setminus
F)\cup((F\setminus G)\setminus\emptyset)=E\setminus G,$

so $G$ is an acyclic flat of $M$.∎

When $M$ is realized by $V\subset\mathbb{R}^{E}$, one can check the acyclicity
of a flat $F$ using the equations of $V$.

######  Proposition 2.5.

Let $M$ be the oriented matroid of a linear subspace $V\subset\mathbb{R}^{E}$.
A flat $F$ is acyclic if and only if there is no linear function
$f=\sum_{i}\alpha_{i}x_{i}$ that vanishes on $V$, satisfies $\alpha_{i}\geq 0$
for all $i\in E\setminus F$, and has $\alpha_{i}>0$ for at least one $i\in
E\setminus F$.

###### Proof.

If such an $f$ exists, then $V\cap(0^{F}\times\mathbb{R}_{>0}^{E\setminus
F})=\emptyset$ because $f$ is strictly positive on
$0^{F}\times\mathbb{R}_{>0}^{E\setminus F}$. The converse holds by [Bjö+99,
Proposition 3.4.8(i) & (ii)], applied to $M/F$. ∎

######  Example 2.6.

2.4ii can fail if $F$ is not an acyclic flat. Let $E=\\{1,2,3,4\\}$,
$V\subset\mathbb{R}^{E}$ be defined by $x_{1}-x_{2}-x_{3}-x_{4}=0$, and $M$
the associated oriented matroid. The flats of $M$ are $E$, and all subsets of
$E$ of size $\leq 2$. In particular, $F=\\{1,2\\}$ is a flat of $M$, but is
not an acyclic flat because the system

$\displaystyle x_{1}=x_{2}=0$ $\displaystyle x_{1}-x_{2}-x_{3}-x_{4}=0$

has no solutions with $x_{3},x_{4}>0$. For similar reasons, $G=\\{1\\}$ is a
flat, but not an acyclic flat of $M$.

On the other hand, $G$ is an acyclic flat of $M|_{F}$. This is because the
point $(0,2,-1,-1)$, for example, is in $V$, so $(0,+,-,-)$ is a covector of
$M$, so $(0,+)$ is a covector of $M|_{F}$. $\diamondsuit$

######  Remark 2.7.

If $V\subset\mathbb{R}^{n}$, then $V\cap\mathbb{R}_{\geq 0}^{n}$ is a
polyhedral cone. The face lattice of $V\cap\mathbb{R}_{\geq 0}^{n}$ is known
as the Edmonds-Mandel lattice of $M$, and the opposite poset is the Las
Vergnas face lattice of $M$.

A graded poset is thin if all of its length-two intervals have exactly four
elements.

######  Theorem 2.8.

[Bjö+99, Theoerem 4.1.14] The poset of covectors is thin. In particular, the
Las Vergnas face lattice is thin.

##  3\. Strata of $\mathcal{Y}_{V}$

Let $V\subset\mathbb{R}^{E}$ be a linear subspace with oriented matroid $M$.
Let $L$ be the set of loops of $M$. Recall from Section 1.3: the non-negative
matroid Schubert variety $\mathcal{Y}_{V}$ is the analytic closure of
$V\cap(0^{L}\times\mathbb{R}^{E\setminus L}_{>0})$ in
$(\mathbb{P}_{\mathbb{R}}^{1})^{n}$. For each $F\subset G\subset E$,
$\mathcal{Y}_{FG}^{\circ}:=\mathcal{Y}_{V}\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F}\times\infty^{E\setminus G})$, and
$\mathcal{Y}_{FG}:=\overline{\mathcal{Y}_{FG}^{\circ}}^{\mathrm{an}}$.
222Careful readers will have noticed that in Section 1.1, we defined
$\mathcal{Y}_{V}$ as the closure of $V\cap\mathbb{R}_{\geq 0}^{E}$. The two
definitions agree because $V\cap\mathbb{R}_{\geq 0}^{E}$ is in the closure of
$V\cap(0^{L}\times\mathbb{R}_{>0}^{E\setminus L})$.

In this section, we prove Theorems 1.1i and ii, which say that the subsets
$\mathcal{Y}_{FG}^{\circ}$ indexed by acyclic flats form a stratification of
$\mathcal{Y}_{V}$, and that the closure poset is isomorphic to the interval
poset of the Las Vergnas face lattice of the oriented matroid of $V$.

######  Lemma 3.1.

Let $V\subset\mathbb{R}^{E}$ be a linear subspace defining an oriented matroid
$M$. If $F\subset G\subset E$ are flats of $M$, then

$Y_{V}\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus F}\times\infty^{E\setminus
G})=\big{(}\pi_{G}(V)\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F})\big{)}\times\infty^{E\setminus G}.$

In particular, $Y_{V}\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F}\times\infty^{E\setminus G})$ is nonempty if and only if $F$ is an acyclic
flat of $M|_{G}$.

###### Proof.

The equality follows from 2.2ii. For the statement on non-emptiness, recall
(from Section 2.3) that the oriented matroid of $\pi_{G}(V)$ is $M|_{G}$. Non-
emptiness of $\pi_{G}(V)\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus F})$ is
equivalent to $0^{F}\times+^{G\setminus F}$ being a covector of $M|_{G}$, in
turn equivalent to acyclicity of $F$ in $M|_{G}$. ∎

######  Lemma 3.2.

Let $V\subset\mathbb{R}^{E}$ be a linear subspace defining an oriented matroid
$M$. Let $F\subset E$. If $F$ is not an acyclic flat, then
$\mathcal{Y}_{V}\cap(\mathbb{R}_{\geq 0}^{F}\times\infty^{E\setminus
F})=\emptyset$.

###### Proof.

If $F$ is not a flat, then $\mathcal{Y}_{V}\cap(\mathbb{R}_{\geq
0}^{F}\times\infty^{E\setminus F})=\emptyset$ by 2.2i. Otherwise, suppose $F$
is a flat, but not an acyclic flat and let $w\in\mathbb{R}_{\geq
0}^{F}\times\infty^{E\setminus F}$. By 2.5, there is a linear functional
$f=\sum_{i}\alpha_{i}x_{i}$ that vanishes on $V$ and satisfies $\alpha_{i}\geq
0$ for all $i\not\in F$, with at least one such $\alpha_{i}$ nonzero. When
$N\gg 0$, $f$ does not vanish at any point of $\prod_{i\in
F}(w_{i}-\frac{1}{N},w_{i}+\frac{1}{N})\times\prod_{j\in E\setminus
F}(N,\infty)$. Hence, the neighborhood $\prod_{i\in
F}(w_{i}-\frac{1}{N},w_{i}+\frac{1}{N})\times\prod_{j\in E\setminus
F}(N,\infty]$ of $w$ does not intersect $V\cap\mathbb{R}^{E}_{>0}$, meaning
that $w\not\in\mathcal{Y}_{V}$. ∎

######  Lemma 3.3.

Let $V\subset\mathbb{R}^{E}$ be a linear space defining an oriented matroid
$M$. If $F\subset E$ is an acyclic flat, then

$Y_{V}\cap(\mathbb{R}_{\geq 0}^{F}\times\infty^{E\setminus
F})=\mathcal{Y}_{V}\cap(\mathbb{R}_{\geq 0}^{F}\times\infty^{E\setminus F}).$

###### Proof.

Let $w\in Y_{V}\cap(\mathbb{R}_{\geq 0}^{F}\times\infty^{E\setminus F})$. By
2.2i, there is $w^{\prime}\in V$ such that
$\pi_{F}(w^{\prime})\times\infty^{E\setminus F}=w$. Since $F$ is acyclic,
there is also $u\in V\cap(0^{F}\times\mathbb{R}_{>0}^{E\setminus F})$. For
large $t>0$, $w^{\prime}+tu\in V_{\geq 0}$, and
$\lim_{t\to\infty}w^{\prime}+tu=w$, so $w\in\overline{V\cap\mathbb{R}_{\geq
0}^{E}}^{\mathrm{an}}=\overline{V\cap\mathbb{R}_{>0}^{E}}^{\mathrm{an}}=\mathcal{Y}_{V}$.
This shows

$Y_{V}\cap(\mathbb{R}_{\geq 0}^{F}\times\infty^{E\setminus
F})\subset\mathcal{Y}_{V}\cap(\mathbb{R}_{\geq 0}^{F}\times\infty^{E\setminus
F}),$

and the reverse inclusion is obvious, so the two sets are equal. ∎

We are now ready to prove the first part of the main result.

###### Proof of 1.1i.

If $G$ is not an acyclic flat, then $\mathcal{Y}_{FG}^{\circ}$ is empty by
3.2. If $G$ is an acyclic flat, but $F$ is not, then $F$ is not acyclic in
$M|_{G}$ by ii, so $\mathcal{Y}_{FG}^{\circ}$ is empty by 3.1.

Conversely, if both $F$ and $G$ are acyclic flats, then

$\mathcal{Y}_{FG}^{\circ}=Y_{V}\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F}\times\infty^{E\setminus
F})=\big{(}\pi_{G}(V)\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F})\big{)}\times\infty^{E\setminus G}$

by 3.1 and 3.3. Consequently, $\mathcal{Y}_{FG}^{\circ}$ is the interior of a
polyhedral cone of dimension $\operatorname{rk}(G)-\operatorname{rk}(F)$. Via
the equalities

$Y_{FG}^{\circ}=Y_{V}\cap(0^{F}\times\mathbb{R}_{\neq 0}^{G\setminus
F}\times\infty^{E\setminus
G})=\big{(}\pi_{G}(V)\cap(0^{F}\times\mathbb{R}_{\neq 0}^{G\setminus
F})\big{)}\times\infty^{E\setminus G},$

we see $Y_{FG}^{\circ}$ is the complement of a real hyperplane arrangement in
$V\cap\\{x_{i}=0:i\in F\\}$. Since $F$ and $G$ are acyclic,
$0^{F}+^{G\setminus F}$ is a tope of the oriented matroid associated to this
arrangement; the corresponding connected component of the arrangement
complement is $\mathcal{Y}_{FG}^{\circ}$. ∎

The following two corollaries of 1.1i provide geometric interpretations for
restriction and contraction at the level of totally non-negative matroid
Schubert varieties. They closely resemble 2.2i and iii.

######  Corollary 3.4.

Let $V\subset\mathbb{R}^{E}$ be a linear subspace defining an oriented matroid
$M$. If $G\subset E$ is an acyclic flat of $M$, then

$\mathcal{Y}_{V}\cap((\mathbb{P}^{1})^{G}\times\infty^{E\setminus
G})=\mathcal{Y}_{\pi_{G}(V)}\times\infty^{E\setminus G}.$

###### Proof.

By 3.3 and 3.1,
$\mathcal{Y}_{V}\cap((\mathbb{P}^{1})^{G}\times\infty^{E\setminus G})$
contains $(\pi_{G}(V)\cap\mathbb{R}_{>0}^{G})\times\infty^{E\setminus G}$, the
closure of which is $\mathcal{Y}_{\pi_{G}(V)}\times\infty^{E\setminus G}$.
This proves the “$\supset$” containment. For the reverse: by 1.1i the nonempty
strata of $\mathcal{Y}_{V}$ are of the form
$\mathcal{Y}_{V}\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F}\times\infty^{E\setminus G})$, with $F\subset G$ acyclic flats of $M$. By
2.4ii, $F$ and $G$ are also acyclic flats of $M|_{G}$, the oriented matroid
represented by $\pi_{G}(V)$. Hence,

$\mathcal{Y}_{V}\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F}\times\infty^{E\setminus
G})=\big{(}\pi_{G}(V)\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F})\big{)}\times\infty^{E\setminus
G}=\big{(}\mathcal{Y}_{\pi_{G}(V)}\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F})\big{)}\times\infty^{E\setminus G}$

by 3.3 and 3.1, which completes the proof. ∎

A proof along the same lines shows:

######  Corollary 3.5.

Let $V\subset\mathbb{R}^{E}$ be a linear subspace defining an oriented matroid
$M$. If $F$ is an acyclic flat, then
$\mathcal{Y}_{V}\cap(0^{F}\times(\mathbb{P}^{1})^{E\setminus
F})=\mathcal{Y}_{V\cap\ker(\pi_{F})}$.

Together, these corollaries yield a short proof of the main result’s second
part.

###### Proof of 1.1ii.

By Corollary 3.4 and Corollary 3.5, $\mathcal{Y}_{FG}$ is equal to
$0^{F}\times\mathcal{Y}_{\pi_{G}(V\cap\ker(\pi_{F}))}\times\infty^{E\setminus
G}$, in turn the closure of
$0^{F}\times\big{(}\pi_{G}(V\cap\ker(\pi_{F}))\cap(0^{F}\times\mathbb{R}_{>0}^{G\setminus
F})\big{)}\times\infty^{E\setminus G}$. The latter set is equal to
$\mathcal{Y}_{FG}^{\circ}$. Strata of
$\mathcal{Y}_{\pi_{G}(V\cap\ker(\pi_{F}))}$ correspond to pairs
$F^{\prime}\subset G^{\prime}$ of acyclic flats of $(M/F)|_{G}$. By 2.4, such
$F^{\prime}\subset G^{\prime}$ are precisely the acyclic flats of $M$ such
that $[F^{\prime},G^{\prime}]\subset[F,G]$, as desired. ∎

##  4\. Topology of $\mathcal{Y}_{V}$

In this section, we prove 1.1iii, which says that $\mathcal{Y}_{V}$ is a
regular CW complex homeomorphic to a closed Euclidean ball. For basics on CW
complexes, we refer the reader to [LW69].

###  4.1. Shellings and topology

A CW complex is regular if the closure of any of its cells is homeomorphic to
a closed Euclidean ball. A $d$-complex is a finite regular CW complex with all
maximal cells of dimension $d$. Maximal closed cells of a $d$-complex $\Delta$
are facets. Following [Bjö84] or [Bjö+99, Appendix 4.7], a shelling of
$\Delta$ is an ordering of its facets $(F_{1},\ldots,F_{m})$ such that the
boundary complex of $F_{1}$ has a shelling, $F_{j}\cap(\cup_{i=1}^{j-1}F_{i})$
is $(d-1)$-complex for $1<j\leq m$, and the boundary of $F_{j}$ has a shelling
in which the facets of $F_{j}\cap(\cup_{i=1}^{j-1}F_{i})$ come first for
$1<j\leq m$.

######  Example/Theorem 4.1.

[BW83, Theorem 4.5] The boundary complex of any convex polytope is shellable.

A shellable complex satisfies the so-called “Property S” of [BW83]. It is
equivalent to shellability for simplicial complexes.

######  Proposition 4.2.

If $(F_{1},\ldots,F_{m})$ is a shelling of a $d$-complex $\Delta$, then for
all $i>j$ there exists $k<i$ such that $F_{i}\cap F_{j}\subset F_{k}$ and
$F_{k}\cap F_{j}$ has dimension $d-1$.

###### Proof.

If $i>j$ then each cell of $F_{i}\cap F_{j}$ is contained in a cell $G$ of
$\Delta$, maximal among those contained in
$C_{i}:=F_{i}\cap(F_{1}\cup\cdots\cup F_{i-1})$. Since $G$ cannot be written
as a union of its proper faces, it must be contained in some $F_{k}$ with
$k<i$. The dimension of $G$ is $d-1$ because $C_{i}$ is pure of dimension
$d-1$. ∎

The following result is our main topological tool.

######  Proposition 4.3.

[Bjö84, Proposition 4.3] A shellable $d$-complex is homeomorphic to a closed
Euclidean ball if each of its $(d-1)$-cells is a face of at most two
$d$-cells, and some $(d-1)$-cell is contained in only one $d$-cell.

###  4.2. Proof of 1.1iii

Let $\mathcal{Y}_{0}$ be the set of all points in $\mathcal{Y}_{V}$ with at
least one coordinate zero, and fix $w\in\mathcal{Y}_{\emptyset E}^{\circ}$.
Define

$\mu:(\mathbb{R}_{\geq
0}\cup\infty)^{n}\to[0,1],\quad(y_{1},\ldots,y_{n})\mapsto
1-\exp(-\min_{i}\\{y_{i}/w_{i}\\})$

The value $\mu(y)$ is the largest value of $t\in[0,1]$ such that $y-\ln(1-t)w$
has non-negative coordinates. The map

$\psi:\mathcal{Y}_{V}\to\mathcal{Y}_{0}\times[0,1]/(\mathcal{Y}_{0}\times\\{1\\}),\quad
y\mapsto(y+\ln(1-\mu(y))w,\mu(y))\ $

is a (non-cellular) homeomorphism, with inverse $(x,t)\mapsto x-\ln(1-t)w$. To
show $\mathcal{Y}$ is a ball, it now suffices to show that $\mathcal{Y}_{0}$
is a ball. This follows from 4.3 and 4.4, whose proof is below. By induction,
it is now proved that all closed strata of $\mathcal{Y}_{V}$ are homeomorphic
to closed balls, so $\mathcal{Y}_{V}$ is a regular CW complex.

######  Lemma 4.4.

$\partial\mathcal{Y}_{V}:=\mathcal{Y}_{V}\setminus\mathcal{Y}_{\emptyset,E}$
is a regular shellable CW complex in which all $(d-1)$-cells are contained in
exactly two $d$-cells. The shelling can be chosen such that all the cells of
$\mathcal{Y}_{0}$ come first, and there are $(d-1)$-cells of $\mathcal{Y}_{0}$
that are contained in only one $d$-cell of $\mathcal{Y}_{0}$.

###### Proof.

Let $M$ be the oriented matroid of $V$, $\dim V=d+1$, and $\mathcal{L}$ its
Las Vergnas face lattice. We first check the containment assertions. The
statement that every $(d-1)$-cell is contained in exactly two $d$-cells
follows easily from the description of cells given by 1.1, combined with 2.8,
which says that $\mathcal{L}$ is thin.

The $d$-cells of $\mathcal{Y}_{0}$ are $\mathcal{Y}_{F,E}$ with $F$ of rank 1.
If $G$ is a corank 1 acyclic flat containing $F$, then
$\mathcal{Y}_{F,E}\supset\mathcal{Y}_{F,G}$, but no other $d$-cell of
$\mathcal{Y}_{0}$ contains $\mathcal{Y}_{F,G}$.

Next, we check the shellability statements. The Las Vergnas face lattice of
$M$ is dual to the face poset of the polyhedral cone $V_{\geq 0}$; therefore,
$\mathcal{L}^{op}$ and $\mathcal{L}$ are the face posets of convex polytopes
$P^{op}_{M}$ and $P_{M}$ with facets in bijection with the rank 1 and corank 1
acyclic flats of $M$, respectively. By 4.1, let $(F_{1},\ldots,F_{s})$ and
$(G_{1},\ldots,G_{t})$ be shellings of $P^{op}_{M}$ and $P_{M}$, respectively.
We will show by induction on $d$ that
$([F_{1},E],\ldots,[F_{s},E],[\emptyset,G_{1}],\ldots,[\emptyset,G_{t}])$
indexes a shelling of $\partial\mathcal{Y}_{V}$.

The statement holds when $d=1$; suppose $d>1$. The boundary of
$\mathcal{Y}_{F_{1},E}\cong\mathcal{Y}_{V\cap\\{x_{i}=0:i\in F_{1}\\}}$ is
shellable by the induction hypothesis. For later cells, we break into two
cases. First consider

$C_{j}:=\mathcal{Y}_{F_{j},E}\cap(\cup_{i<j}\mathcal{Y}_{F_{i},E})=\cup_{i<j}\mathcal{Y}_{F_{i}\vee
F_{j},E}.$

Since $(F_{1},\ldots,F_{s})$ is a shelling of $P^{op}_{M}$, for each $i<j$,
there is $k$ such that $\mathcal{Y}_{F_{i}\vee
F_{k},E}\supset\mathcal{Y}_{F_{i}\vee F_{k},E}$ and $F_{i}\vee F_{k}$ has rank
2 by 4.2. This shows $C_{j}$ is a $(d-1)$-complex.

Let $P^{op}_{M}(F)$ be the face of $P_{M}^{op}$ corresponding to an acyclic
flat $F$ in $\mathcal{L}^{op}$. By hypothesis, $P_{M}^{op}(F_{j})$ has a
shelling in which the facets $P_{M}^{op}(F_{j}\vee F_{i})$, $i<j$ and
$\operatorname{rk}(F_{j}\vee F_{i})=2$ come first. The face poset of
$P_{M}^{op}(F_{j})$ is the same as that of $P_{M/F_{j}}^{op}$, the polytope
associated to the oriented matroid of $V\cap\\{x_{j}=0\\}$. Hence, by
induction
$\partial\mathcal{Y}_{V\cap\\{x_{j}=0\\}}\cong\partial\mathcal{Y}_{F_{j},E}$
has a shelling in which the $(d-1)$-cells of $C_{j}$ come first.

We now consider

$D_{j}:=\mathcal{Y}_{\emptyset,G_{j}}\cap\big{(}\mathcal{Y}_{0}\cup(\cup_{i<j}\mathcal{Y}_{\emptyset
F_{i}})\big{)}=(\cup_{F_{k}\subset
G_{j}}\mathcal{Y}_{F_{k},G_{j}})\cup(\cup_{i<j}\mathcal{Y}_{\emptyset,G_{i}\cap
G_{j}}).$

All cells of the form $\mathcal{Y}_{F_{k},G_{j}}$ are dimension $d-1$, and
$\cup_{i<j}\mathcal{Y}_{\emptyset,G_{i}\cap G_{j}}$ is a $(d-1)$-complex by
4.2, as above, so $D_{j}$ is a $(d-1)$-complex. Observing that
$\mathcal{Y}_{\emptyset,G_{j}}\cong\mathcal{Y}_{\pi_{G_{j}}(V)}$, shellability
follows as above. ∎

######  Remark 4.5.

Our proof relies on the fact that both $\mathcal{L}$ and $\mathcal{L}^{op}$
are face lattices of polytopes, hence CL-shellable (see [BW83]). It is known
that $\mathcal{L}$ is CL-shellable even when $M$ is not realizable [Bjö+99,
Theorem 4.3.5], but remains open whether $\mathcal{L}^{op}$ is.

######  Remark 4.6.

A slightly different route to 1.1iii: the order complex of a poset is the
simplicial complex whose faces are chains in the poset, and a poset is
shellable if its order complex is. By [Bjö+99, Theorem 4.3.5],
$\mathcal{L}^{op}$ is shellable, so $\mathcal{L}$ is also shellable, so the
interval poset of $\mathcal{L}$ is shellable by [BW83, Theorem 8.5]. Every
length 2 interval in the interval poset of $\mathcal{L}$ has cardinality 4, so
$\partial\mathcal{Y}_{V}$ is homeomorphic to a sphere by [DK74, Propositions
1.1, 1.2] and [LW69, Theorem III.1.7]. In fact, by [Bjö+99, Proposition
4.7.26], $\partial\mathcal{Y}_{V}$ is a PL sphere. The link of a vertex of a
PL sphere is also a PL sphere; in particular, the equator
$\mathcal{Y}_{\ominus}:=\mathcal{Y}_{0}\setminus V_{\geq 0}$ is a PL sphere
because it is the link of $\mathcal{Y}_{E,E}$. The star of a point is a cone
over its link, so $\mathcal{Y}_{0}$ is a cone over $\mathcal{Y}_{\ominus}$, so
$\mathcal{Y}_{0}$ is a closed ball. The proof may now be completed as above.

##  5\. Topology of $Y_{V}$

Let $V\subset\mathbb{R}^{E}$. In this section, we will show that $Y_{V}$
admits a regular cell decomposition.

We first record a consequence of 1.1. Let $M$ be the oriented matroid of $V$,
and $s:\mathbb{R}^{E}\to\\{-,0,+\\}^{E}$ the sign map (see 2.3). Fix a tope
$T$ of $M$. A flat is relatively acyclic in $T$ if it is the zero set of a
covector contained in $T$. Define
${}_{T}\mathcal{Y}_{V}:=\overline{s^{-1}(T)}^{\mathrm{an}}$, the analytic
closure of $s^{-1}(T)$ in $(\mathbb{P}_{\mathbb{R}}^{1})^{E}$. For each pair
of sets $F\subset G\subset E$, let

${}_{T}\mathcal{Y}_{FG}^{\circ}:={}_{T}\mathcal{Y}_{V}\cap(0^{F}\times\mathbb{R}_{>0}^{(G\setminus
F)\cap T^{+}}\times\mathbb{R}_{<0}^{(G\setminus F)\cap
T^{-}}\times\infty^{E\setminus G}).$

Finally, set
${}_{T}\mathcal{Y}_{V}:=\overline{{}_{T}\mathcal{Y}_{V}^{\circ}}^{\mathrm{an}}$.

######  Corollary 5.1.

Fix a tope $T$ of the oriented matroid of $V\subset\mathbb{R}^{E}$. Then

  1. (i)

${}_{T}\mathcal{Y}_{FG}^{\circ}$ is nonempty if and only if $F\subset G$ are
acyclic flats in $T$. In this case, ${}_{T}\mathcal{Y}_{FG}^{\circ}$ is a
single connected component of $Y_{FG}^{\circ}$, and is a semi-algebraic cell
isomorphic to $(\mathbb{R}_{>0})^{\operatorname{rk}(G)-\operatorname{rk}(F)}$.

  2. (ii)

The closure ${}_{T}\mathcal{Y}_{FG}$ of a nonempty cell
${}_{T}\mathcal{Y}_{FG}^{\circ}$ decomposes as the disjoint union of cells
${}_{T}\mathcal{Y}_{F^{\prime},G^{\prime}}^{\circ}$ with $F\subset
F^{\prime}\subset G^{\prime}\subset G$.

  3. (iii)

This decomposition makes ${}_{T}\mathcal{Y}_{V}$ a shellable regular CW
complex homeomorphic to a closed ball.

###### Proof.

For $A\subset E$, let
$-_{A}:(\mathbb{P}_{\mathbb{R}}^{1})^{E}\to(\mathbb{P}_{\mathbb{R}}^{1})^{E}$
be the map that negates the coordinates indexed by $E$. The result follows
from 1.1 because $-_{T^{-}}(s^{-1}(T))=-_{T^{-}}(V)\cap\mathbb{R}_{\geq
0}^{E}$. ∎

######  Remark 5.2.

A tope in the matroid-theoretic setting is akin to a pinning in the Lie-
theoretic setting, as defined in [Lus94]. Indeed, $\operatorname{SL}(2)$ has
just one negative simple root. Choosing an isomorphism $y:\mathbb{R}\to
U_{-\alpha}$ up to positive scalars in each factor of
$\operatorname{SL}(2)^{n}$ is the same as choosing which side of
$\mathbb{R}\subset\mathbb{P}^{1}_{\mathbb{R}}$ will be regarded as positive,
hence is the same as choosing a positive side for each hyperplane in
$V\subset\mathbb{R}^{n}$ obtained by intersecting $V$ with a coordinate
hyperplane of $\mathbb{R}^{n}$.

The various subsets ${}_{T}\mathcal{Y}_{V}$ are not disjoint. The following
statement characterizes their intersections.

######  Lemma 5.3.

Let $M$ be the oriented matroid of $V\subset\mathbb{R}^{E}$. Define an
equivalence relation on the set of all triples $(F,G,T)$, with $F\subset G$
flats relatively acyclic in the tope $T$ of $M$, by
$(F,G,T)\sim(F^{\prime},G^{\prime},T^{\prime})$ if and only if
$(F,G)=(F^{\prime},G^{\prime})$ and $\pi_{G\setminus F}(T)=\pi_{G\setminus
F}(T^{\prime})$. The intersection of ${}_{T}\mathcal{Y}_{FG}^{\circ}$ and
${}_{T^{\prime}}\mathcal{Y}_{F^{\prime}G^{\prime}}^{\circ}$ is empty unless
$(F,G,T)\sim(F^{\prime},G^{\prime},T^{\prime})$, in which case
${}_{T}\mathcal{Y}_{FG}^{\circ}={}_{T^{\prime}}\mathcal{Y}_{F^{\prime}G^{\prime}}^{\circ}$.

###### Proof.

Reorienting, applying 3.1 and 3.3, then reverting to the original orientation,
we see

($*$) $\displaystyle{}_{T}\mathcal{Y}^{\circ}_{FG}$
$\displaystyle=(\pi_{G}(V)\cap(0^{F}\times\mathbb{R}_{>0}^{T^{+}\cap(G\setminus
F)}\times\mathbb{R}_{<0}^{T^{-}\cap(G\setminus F)}))\times\infty^{E\setminus
G}\quad\text{and}$
$\displaystyle{}_{T^{\prime}}\mathcal{Y}^{\circ}_{F^{\prime}G^{\prime}}$
$\displaystyle=(\pi_{G^{\prime}}(V)\cap(0^{F^{\prime}}\times\mathbb{R}_{>0}^{{T^{\prime}}^{+}\cap(G^{\prime}\setminus
F^{\prime})}\times\mathbb{R}_{<0}^{{T^{\prime}}^{-}\cap(G^{\prime}\setminus
F^{\prime})}))\times\infty^{E\setminus G^{\prime}}.$

The result follows. ∎

For each pair of flats $F\subset G\subset E$ and tope $T$ of $(M/F)|_{G}$, let
$Y_{FGT}^{\circ}$ be the connected component of $Y_{FG}^{\circ}$ corresponding
to the tope $T$. Explicitly,
$Y_{FGT}^{\circ}:=Y_{V}\cap(0^{F}\times\mathbb{R}_{>0}^{T^{+}}\times\mathbb{R}_{<0}^{T^{-}}\times\infty^{E\setminus
G})$. As usual, let $Y_{FGT}:=\overline{Y_{FGT}^{\circ}}^{\mathrm{an}}$.

######  Lemma 5.4.

The equivalence classes of $\sim$ (defined as in 5.3) are in bijection with
cells $Y_{FGT}^{\circ}$. If $[S,I,J]$ is the equivalence classes corresponding
to $Y_{FGT}^{\circ}$, then $Y_{FGT}^{\circ}={}_{S}\mathcal{Y}_{IJ}^{\circ}$.
Explicitly, $Y_{FGT}^{\circ}={}_{S}\mathcal{Y}_{IJ}^{\circ}$ if and only if
$(F,G)=(I,J)$ and $\pi_{G\setminus F}(S)=\pi_{G\setminus F}(T)$.

###### Proof.

Given ${}_{S}\mathcal{Y}_{IJ}^{\circ}$, take $F:=I$, $G:=J$, and
$T:=\pi_{G}(X)$, where $X$ is the unique covector contained in $S$ with
$X^{0}=F$. Evidently, $Y_{FGT}$ is independent of the representative of
$[S,I,J]$.

For the inverse: let $F\subset G$ be flats of $M$ and let $T$ be a tope of
$(M/F)|_{G}$. There are covectors $\tilde{F},\tilde{G}$ of $M$ satisfying
$\tilde{F}^{0}=F$, $\pi_{G}(\tilde{F})=T$, and $\tilde{G}^{0}=G$. The
composition $X:=\tilde{G}\circ\tilde{F}$ then satisfies $\tilde{G}\leq X$,
$X^{0}=F$, and $\pi_{G}(X)=T$. Both $F$ and $G$ are relatively acyclic with
respect to any tope $S\geq X$ of $M$, so there is an equivalence class
$[S,F,G]$. This class is independent of $S$ because $\pi_{G\setminus
F}(S)=\pi_{G\setminus F}(T)$.

Under the bijection described above, we see that $Y_{FGT}$ corresponds to
$[S,I,J]$ if and only if $(F,G)=(I,J)$ and $\pi_{G\setminus
F}(S)=\pi_{G\setminus F}(T)$. In this case,
${}_{S}\mathcal{Y}_{IJ}^{\circ}=Y_{FGT}$ by Eq. $*$. ∎

######  Corollary 5.5.

Let $M$ be the oriented matroid of $V\subset\mathbb{R}^{E}$.

  1. (i)

$Y_{FGT}$ contains $Y_{F^{\prime}G^{\prime}T^{\prime}}^{\circ}$ if and only if
$F\subset F^{\prime}\subset G^{\prime}\subset G$ and there is a tope $S$ of
$M$ satisfying: $F,G,F^{\prime},G^{\prime}$ are all relatively acyclic in $S$,
$\pi_{G\setminus F}(S)=\pi_{G\setminus F}(T)$ and $\pi_{G^{\prime}\setminus
F^{\prime}}(S)=\pi_{G^{\prime}\setminus F^{\prime}}(T^{\prime})$.

  2. (ii)

The cells $Y_{F,G,T}^{\circ}$, where $F\subset G$ run over flats of $M$ and
$T$ runs over topes of $(M/F)|_{G}$, form a regular CW decomposition of
$Y_{V}$.

###### Proof.

We prove the second statement first. The set $\cup_{T}\,{}_{T}\mathcal{Y}_{V}$
is closed in $(\mathbb{P}_{\mathbb{R}}^{1})^{E}$ and contains $V$; therefore,
it is equal to $Y_{V}$. Together with 5.3 and Corollary 5.1, this implies the
collection $\\{{}_{S}\mathcal{Y}_{IJ}^{\circ}\\}_{I,J,S}$ is a regular cell
decomposition of $Y_{V}$. The cells in this decomposition are in fact the sets
$Y_{FGT}^{\circ}$ by 5.4, completing the proof of Corollary 5.5ii.

We now prove the first statement. The closure of any cell is contained in some
set ${}_{S}\mathcal{Y}_{V}$. Hence, the closure of $Y_{FGT}^{\circ}$ contains
$Y_{F^{\prime}G^{\prime}T^{\prime}}^{\circ}$ if and only if there is a tope
$S$ of $M$ such that $Y_{FGT}^{\circ}={}_{S}\mathcal{Y}^{\circ}_{FG}$,
$Y_{F^{\prime}G^{\prime}T^{\prime}}^{\circ}={}_{S}\mathcal{Y}^{\circ}_{F^{\prime}G^{\prime}}$,
and
${}_{S}\mathcal{Y}_{FG}\supset{}_{S}\mathcal{Y}^{\circ}_{F^{\prime}G^{\prime}}$.
By Corollary 5.1 and 5.4, this is equivalent to the conditions specified by
Corollary 5.5i. ∎

######  Remark 5.6.

If $V\subset\mathbb{R}^{3}$ is defined by $x_{1}+x_{2}-x_{3}=0$, then $Y_{V}$
has nontrivial first homology. This means $Y_{V}$ is not a shellable cell
complex, since a shellable $d$-complex always has the homotopy type of a wedge
of $d$-spheres [Bjö84, Proposition 4.3].

## References

  * [AB16] Federico Ardila and Adam Boocher  “The closure of a linear space in a product of lines”  In _J. Algebraic Combin._ 43.1, 2016, pp. 199–235
  * [AKW04] Federico Ardila, Caroline J. Klivans and Lauren K. Williams  “The positive Bergman complex of an oriented matroid”  In _Eur. J. Comb._ 27, 2004, pp. 577–591
  * [Ard21] Federico Ardila  “The geometry of geometries: matroid theory, old and new”, 2021  arXiv:2111.08726 [math.CO]
  * [ARW06] Federico Ardila, Vic Reiner and Lauren Williams  “Bergman complexes, Coxeter arrangements, and graph associahedra”  In _Euro. J. Combinatorics_ 27.4, 2006, pp. 577–591
  * [AT14] N. Arkani-Hamed and J. Trnka  “The amplituhedron”  In _Journal of High Energy Physics_ , 2014
  * [Bjö+99] A. Björner et al.  “Oriented matroids” 46, Encyclopedia of mathematics and its applications  Cambridge University Press, 1999
  * [Bjö84] A Björner  “Posets, regular CW complexes, and Bruhat order”  In _Euro. J. Combinatorics_ 5, 1984, pp. 7–16
  * [Bra+20] Tom Braden et al.  “Singular Hodge theory for combinatorial geometries”  In _arXiv e-prints_ , 2020  arXiv:2010.06088 [math.CO]
  * [BW83] Anders Björner and Michelle Wachs  “On lexicographically shellable posets”  In _Trans. of the AMS_ 277.1, 1983
  * [DK74] Gopal Danaraj and Victor Klee  “Shellings of spheres and polytopes”  In _Duke Math. J._ 41, 1974, pp. 443–451
  * [EPW16] Ben Elias, Nicholas Proudfoot and Max Wakefield  “The Kazhdan–Lusztig polynomial of a matroid”  In _Advances in Mathematics_ 299, 2016, pp. 36–70
  * [FG06] V. Fock and A. Goncharov  “Moduli spaces of local systems and higher Teichmüller theory”  In _Publ. Math. I.H.E.S. 103_ , 2006, pp. 1–211
  * [FZ02] S. Fomin and A. Zelevinksy  “Cluster algebras. I. Foundations”  In _J. Amer. Math. Soc._ 15.2, 2002, pp. 497–529
  * [HW17] June Huh and Botong Wang  “Enumeration of points, lines, planes, etc”  In _Acta Math._ 218.2, 2017, pp. 297–317
  * [Iri83] M. Iri  “Applications of Matroid Theory”  In _Mathematical Programming The State of the Art: Bonn 1982_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1983, pp. 158–201
  * [Kar68] S. Karlin  “Total positivity”  Stanford, CA: Stanford University Press, 1968
  * [Kat14] Eric Katz  “Matroid theory for algebraic geometers”, 2014  arXiv:1409.3503 [math.AG]
  * [Lus94] G. Lusztig  “Total positivity in reductive groups”  In _Lie theory and geometry_ 123, Progr. Math.  Boston, MA: Birkhäuser Boston, 1994, pp. 531–568
  * [LW69] Albert Lundell and Stephen Weingram  “The topology of CW complexes”  New York: Litton Educational Publishing Inc., 1969
  * [MR00] Bethany Rose Marsh and Konstanze Rietsch  “The Intersection of Opposed Big Cells in The Real Flag Variety of Type $G_{2}$”  In _Proceedings of the London Mathematical Society_ 85, 2000
  * [Nak35] T. Nakasawa  “Zur axiomatik der linearen abhängigkeit”  In _Science Reports of the Tokyo Bunrika Daigaku_ 2.43, 1935
  * [PS06] Nicholas Proudfoot and David Speyer  “A broken circuit ring”  In _Beitraäge zue algebra and geometrie_ 47.1, 2006, pp. 161–166
  * [PXY18] Nicholas Proudfoot, Yuan Xu and Ben Young  “The Z-polynomial of a matroid”  In _Electronic J. Combin._ 25.1, 2018
  * [Rec11] AndrÁs Recski  “Engineering Applications of Matroids - A Survey”  In _Matroid Theory and its Applications_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 300–321
  * [RST20] Zvi Rosen, Jessica Sidman and Louis Theran  “Algebraic matroids in action”  In _The American Mathematical Monthly_ 127.3, 2020, pp. 199–216  arXiv:1809.00865 [math.CO]
  * [Sch30] I. Schoenberg  “Über variationsvermindernde lineare Transformationen”  In _Math. Z._ 32.1, 1930, pp. 321–328
  * [Sta11] Richard P. Stanley  “Enumerative Combinatorics”  Cambridge University Press, 2011
  * [Ter02] Hiroaki Terao  “Algebras generated by reciprocals of linear forms”  In _Journal of Algebra_ 2.250, 2002, pp. 549–558
  * [Whi35] H. Whitney  “On abstract properties of linear dependence”  In _Amer. J. Math._ , 1935, pp. 509–533
  * [Whi86] Neil White  “Theory of matroids” 26, Encyclopedia of mathematics and its applications  New York: Cambridge University Press, 1986


# Tell Model Where to Attend: Improving Interpretability of Aspect-Based
Sentiment Classification via Small Explanation Annotations

###### Abstract

Gradient-based explanation methods play an important role in the field of
interpreting complex deep neural networks for NLP models. However, the
existing work has shown that the gradients of a model are unstable and easily
manipulable, which impacts the model’s reliability largely. According to our
preliminary analyses, we also find the interpretability of gradient-based
methods is limited for complex tasks, such as aspect-based sentiment
classification (ABSC). In this paper, we propose an Interpretation-Enhanced
Gradient-based framework for ABSC via a small number of explanation
annotations, namely IEGA. Particularly, we first calculate the word-level
saliency map based on gradients to measure the importance of the words in the
sentence towards the given aspect. Then, we design a gradient correction
module to enhance the model’s attention on the correct parts (e.g., opinion
words). Our model is model agnostic and task agnostic so that it can be
integrated into the existing ABSC methods or other tasks. Comprehensive
experimental results on four benchmark datasets show that our IEGA can improve
not only the interpretability of the model but also the performance and
robustness.

Index Terms—  Interpretability, aspect-based sentiment classification,
gradient-based

##  1 Introduction

Interpreting complex deep neural networks to understand the reasoning behind
the decision of NLP models has attached much attention [1, 2]. Understanding
how such models work is an important research with wide applications such as
deployment [3] and helping developers improve the quality of the models [4].
Recently, post-hoc explanation techniques have been widely used, categorized
into black-box and white-box methods. In this paper, we improve upon the
gradient-based explanation method [5, 6], which is one of the main methods in
white-box models. Gradient-based explanation method calculates the word
importance explainability by estimating the contribution of input sentence $x$
towards output $y$ [7, 8, 9]. It calculates the first derivative of $y$ with
respect to $x$ to obtain the saliency map, which is a popular technique
applicable to various deep learning models.

However, the existing literature has shown that the gradient-based model is
easily manipulable [10] and unreliable [11]. Moreover, we also find that the
gradient-based methods perform poorly on complex NLP tasks, such as aspect-
based sentiment classification (ABSC). ABSC aims to judge the sentiment
polarity of the given aspect in the sentence, which may contain multiple
aspects whose sentiments may be opposite. For example, in the sentence "I can
say that I am fully satisfied with the performance that the computer has
supplied.", the user expresses a positive sentiment towards the aspect
"performance" using the opinion words "satisfied" (Fig. 1). We can find that
the BERT-SPC model focuses on the unrelated words (e.g., "say", "I", "of",
"is") via the standard gradient. Here, we hope the model can capture the most
relevant words (e.g., "satisfied", "disappointment") for predicting based on
small additional explanation annotations because labeling the fine-grained
opinions is expensive.

Fig. 1: Two examples of interpretability. The words marked with [] and
underline are aspects and opinion words respectively. Pos and neg mean
positive and negative sentiments of the aspects. Color depth indicates the
importance of the words.  Fig. 2: The architecture of our IEGA proposed model.

Particularly, to enhance the model doing the "right thing”, we propose an
Interpretation-Enhanced Grandient-based method (IEGA) for ABSC via small
annotations. First, we use gradients to obtain the word-level saliency map,
which measures the importance of the words for the predictions. Since labeling
the opinion words toward the given aspects is time-consuming, we then aim to
guide the model via small explainable annotations. Specifically, we design a
gradient correction module to enforce the model to focus on the most related
words (e.g., opinion words). We also conduct a series of experiments on four
popular datasets for the ABSC task. The results indicate that our IEGA can
improve not only the interpretability but also the performance of the model.
Additionally, we also investigate the robustness of our model.

The main contributions of this paper can be summarized as follows. 1) We
propose a novel framework to improve the interpretation of gradient-based
methods for ABSC via a small number of additional explanation samples; 2) We
design a gradient correction module to enable the model to capture the most
related words based on the word-level saliency map; 3) We conduct extensive
experiments to verify the great advantages of our IEGA framework, which can
improve the explanation, performance, and robustness of the model.

##  2 Approaches

In this paper, we propose an IEGA framework for ABSC to enhance the
interpretation of the model using small annotations (Fig. 2). First, we
compute the gradients of $y$ with respect to $x$ based on a sentiment
classifier. Second, we introduce a gradient correction module to make the
word-level saliency map obtained by gradients close to the truth distributions
of opinion words.

Formally, given a sentence $s=\\{w_{1},...,w_{i},...,w_{|s|}\\}$ and an aspect
$a$, where aspect $a$ is a subsequence of $s$, $w_{i}$ is the $i$-th word in
$s$, and $|s|$ is the number of the words in the sentence. The word embeddings
of the sentence $s$ are $x=\\{x_{1},...,x_{i},...,x_{|s|}\\}$, where $x_{i}$
is the word embedding of $w_{i}$. This task aims to predict the sentiment
polarity $y\in\\{P,N,O\\}$ of the sentence towards the given aspect $a$. $P$,
$N$, $O$ represent positive, negative, and neutral, respectively. Moreover, we
aim to explain the model by extracting the opinion words $o$ that express the
sentiment w.r.t the aspect $a$.

###  2.1 Gradient Calculation

First, we train a sentiment classifier for ABSC, which aims to infer the
sentiment of the sentence w.r.t. the given aspect. Let $\mathcal{F}$ be a
sentiment classifier which predict the sentiment distribution $P(y|s,a)$ based
on the sentence $s$ and aspect $a$.

$P(y|s,a)=\mathcal{F}(s,a)$ (1)

The loss function is the cross-entropy between the predicted probability and
the true label,

$\mathcal{L}_{c}(y,s,a)=-{\log P(y|s,a)}.$ (2)

Particularly, the sentiment classifier $\mathcal{F}$ can be any existing
aspect-level sentiment classifier models, such as BERT-SPC [12], RGAT-BERT
[13].

If we slightly perturb the word $w_{i}$’s embedding $\mathbf{x_{i}}$ to
$\mathbf{x_{i}}^{\prime}$ with
$\|\mathbf{x_{i}}^{\prime}-\mathbf{x_{i}}\|\leq\varepsilon$, we can use the
first-order approximation of $\mathcal{L}_{c}(y,s,a)_{\mathbf{x_{i}}}$ to
compute the absolute change of the loss function, which indicates the
importance of the word $w_{i}$. rl & |L_c(y, s, a)_x_i’ - L_c(y, s, a)_x_i|
≈|∇_x_iL_c(y, s, a)_x_i)^T (x_i’ - x_i)|
≤∥∇_x_iL_c(y, s, a)_x_i∥ ∥x_i’ - x_i∥
≤ε∥∇_x_iL_c(y, s, a)_x_i∥.

Thus, it is a natural approximation to metric what tokens are most relevant
for a prediction using the gradient [5, 14]. The gradient of the $i$-th word
$w_{i}$ is calculated as follows:

$g_{i}=\nabla_{\mathbf{x_{i}}}\mathcal{L}_{c}(y,s,a)_{\mathbf{x_{i}}}=\frac{\partial\mathcal{F}\left(s,a\right)}{\partial
x_{i}}$ (3)

which can be computed automatically via machine learning frameworks, such as
Pytorch and Tensorflow.

###  2.2 Gradient Correction

In order to enhance the model to focus on the correct parts (e.g., opinion
words), we introduce a gradient correction module. We first calculate the
importance of the words in the sentence based on the gradients to obtain the
word-level saliency map. The magnitude of the gradient’s norm $\|g_{i}\|$
could be a sign of how sensitive the sentiment label is to $w_{i}$: to get the
correct prediction we will prefer not to perturb those words with large
gradient norms. It suggests that words with large gradient norm are
contributing most towards the correct sentiment label and might be the opinion
words of the aspect. Thus, we define the attribution for the word $w_{i}$ as

$\alpha_{i}=\frac{\mathrm{score}(w_{i})}{\sum_{j}(\mathrm{score}(w_{j}))},$

where $\mathrm{score}(w_{i})=\left|g_{i}\cdot x_{i}\right|$ converts the word
gradients into weights by the dot product of the gradient $g_{i}$ and word
embedding $x_{i}$. Gradients (of the output with respect to the input) are a
natural analog of the model coefficients for a deep network. Therefore the
product of the gradient and feature values is a proper importance score
function [5, 14].

We use small labeled samples to make the word-level saliency map close to the
distributions of opinion words.

$\mathcal{L}_{g}=-\sum_{j=1}^{|s|}y^{o}_{j}\alpha_{j}$ (4)

where $y^{o}_{j}=1$ if word $w_{j}$ is opinion word, else $y^{o}_{j}=0$.

Finally, we add the classification loss $\mathcal{L}_{c}$ and gradient
correction loss $\mathcal{L}_{g}$ with a weight $\lambda$,
$\mathcal{L}=\mathcal{L}_{c}+\lambda\mathcal{L}_{g}$.

##  3 Experiments

###  3.1 Experimental Setups

Datasets. To verify the effectiveness of IEGA, we conduct extensive
experiments on four typical datasets: Res14, Lap14, Res15, and Res16 [15]. We
follow the setting of [15], which labeled the opinion words for each aspect.

Metrics.  To assess the models’ performance, we use two popular metrics,
Accuracy and Macro-F1. To investigate the faithfulness of explanations, follow
[10], we used Mean Reciprocal Rank (MRR) and Hit Rate (HR) to verify whether
opinion words get higher scores in attribution. We also adopt the area over
the perturbation curve (AOPC) [16, 17] and Post-hoc Accuracy (Ph-Acc) [18],
which are widely used for explanations [19]. AOPC calculates the average
change of accuracy over test data by deleting top $K$ words via the word-level
saliency map. For Post-hoc Accuracy, we select the top $K$ words based on
their importance weights as input to make a prediction and compare it with the
ground truth. We set $K=5$ value in our experiments.

Baselines.  We select four state-of-the-art baselines for aspect-based
sentiment classification to investigate the performance: BERT-SPC [12], AEN-
BERT [20], LCF-BERT [21], RGAT-BERT [13]. For the limitation of space, please
see more details about the baselines on the original papers.

Implementation Details.  While conducting our experiments, we adopt the BERT
base as the pre-trained model of our sentiment classifier. Some
hyperparameters like batch size, maximum epochs, and learning rate are set to
32, 20, and 2e-5. The weight $\lambda$ of gradient correction loss is fixed at
0.01.

Fig. 3: The results of interpretability. Table 1: The results of interpretability in terms of AOPC and Post-hoc Acc.  4 Model | Lap14 | Res14 | Res15 | Res16
---|---|---|---|---
AOPC$\uparrow$ |  Ph Acc$\uparrow$ |  AOPC$\uparrow$ |  Ph Acc$\uparrow$ |  AOPC$\uparrow$ |  Ph Acc$\uparrow$ |  AOPC$\uparrow$ |  Ph Acc$\uparrow$
BERT-SPC | 07.24 | 33.70 | 07.95 | 56.87 | 06.50 | 64.84 | 03.82 | 65.44
BERT-SPC${}_{\texttt{IEGA}}$ (10%) |  15.04(+7.80) |  42.18(+8.48) |  11.13(+3.18) |  69.18(+12.31) |  08.26(+1.76) |  70.78(+5.94) |  10.48(+6.66) |  75.49(+10.05)
BERT-SPC${}_{\texttt{IEGA}}$ (20%) |  18.54(+11.30) |  42.38(+8.68) |  12.35(+4.40) |  74.17(+17.30) |  09.65(+3.15) |  71.98(+7.14) |  11.49(+7.67) |  76.27(+10.83)
BERT-SPC${}_{\texttt{IEGA}}$ (50%) |  18.57(+11.33) |  55.67(+21.97) |  16.78(+8.83) |  75.29(+18.42) |  10.50(+4.00) |  73.50(+8.66) |  12.41(+8.59) |  78.17(+12.73)
BERT-SPC${}_{\texttt{IEGA}}$ (100%) |  21.90(+14.66) |  59.73(+26.03) |  20.47(+12.52) |  76.12(+19.25) |  11.98(+5.48) |  74.65(+9.81) |  15.87(+12.05) |  79.82(+14.38)
RGAT-BERT | 05.28 | 54.38 | 12.70 | 51.64 | 08.06 | 64.51 | 08.31 | 71.05
RGAT-BERT${}_{\texttt{IEGA}}$ (10%) |  13.58(+8.30) |  66.52(+12.14) |  15.67(+2.97) |  63.29(+11.65) |  16.07(+8.01) |  72.98(+8.47) |  12.71(+4.40) |  80.04(+8.99)
RGAT-BERT${}_{\texttt{IEGA}}$ (20%) |  13.92(+8.64) |  67.89(+13.51) |  15.88(+3.18) |  68.82(+17.18) |  17.97(+9.91) |  77.89(+13.38) |  12.80(+4.49) |  80.70(+9.65)
RGAT-BERT${}_{\texttt{IEGA}}$ (50%) |  14.56(+9.28) |  72.59(+18.21) |  16.23(+3.53) |  73.29(+21.65) |  21.65(+13.59) |  81.33(+16.82) |  12.94(+4.63) |  83.11(+12.06)
RGAT-BERT${}_{\texttt{IEGA}}$ (100%) |  16.49(+11.21) |  72.80(+18.42) |  16.25(+3.55) |  75.65(+24.01) |  23.50(+15.44) |  82.95(+18.44) |  13.60(+5.29) |  85.09(+14.04)
4 |  |  |  |  |  |  |  |

###  3.2 Experimental Analysis

Interpretability Analysis.  We apply our IEGA framework to two classical ABSC
models to explore the explanations of the models with different proportions of
labeled opinion words (Fig. 3 and Table 1). The results show that our model
captures the explanations (opinion words) more accurately. For example, both
BERT-SPC${}_{\texttt{IEGA}}$ and RGAT-BERT${}_{\texttt{IEGA}}$ obtain higher
HR and MRR, which indicates that they find opinion words more effectively than
the corresponding models without IEGA. This is because the model can better
capture the opinion words corresponding to the aspect with the help of
gradient correction. For Post-hoc Accuracy, we compute the accuracy by
selecting the top $5$ words based on their importance weights to make a
prediction. Our model gains an increase of five points over all datasets in
terms of Post-hoc Accuracy using only 10% (about 150) training samples
annotated with opinion words. Also, models with IEGA perform better than ones
without IEGA in terms of AOPC despite only partial training samples labeled
opinion words. In summary, the improvement of these metrics shows that the
interpretability of the model can be largely boosted with the help of our IEGA
framework even if only 10% of the opinion words are annotated.

Table 2: Performance of our models and baselines. 4 Model | Lap14 | Res14 | Res15 | Res16
---|---|---|---|---
Acc. | F1 | Acc. | F1 | Acc. | F1 | Acc. | F1
AEN-BERT | 81.80 | 56.07 | 88.59 | 64.90 | 86.44 | 63.73 | 88.60 | 65.06
LCF-BERT | 81.83 | 58.23 | 90.00 | 72.69 | 85.94 | 67.53 | 89.91 | 69.98
BERT-SPC | 81.07 | 62.84 | 89.34 | 67.91 | 85.02 | 56.44 | 88.02 | 56.23
RGAT-BERT | 82.58 | 65.10 | 91.64 | 77.50 | 87.09 | 69.36 | 90.78 | 67.34
BERT-SPC${}_{\texttt{IEGA}}$ | 82.28 | 62.93 | 90.62 | 72.75 | 85.40 | 59.39 | 88.56 | 62.60
Improvement | (+1.21) | (+0.09) | (+1.28) | (+4.84) | (+0.38) | (+2.95) | (+0.54) | (+6.37)
RGAT-BERT${}_{\texttt{IEGA}}$ | 83.08 | 65.56 | 92.36 | 79.30 | 88.25 | 72.49 | 91.76 | 76.02
Improvement | (+0.50) | (+0.46) | (+0.72) | (+1.80) | (+1.17) | (+3.13) | (+0.98) | (+8.68)
4 |  |  |  |  |  |  |  |

Performance Analysis.  We compare our models with several ABSC models to
evaluate the performance of our framework (Table 2). From the results, we
obtain the following observations. First, our model performs better than the
baselines over all the datasets in terms of accuracy and F1. RGAT-
BERT${}_{\texttt{IEGA}}$ obtains the best results compared with all the
existing state-of-the-art baselines (e.g., RGAT-BERT). Second, our IEGA
framework can improve the performance of the base model. For instance, F1
improved by 3 and 8 points on Res15 and Res16 by integrating IEGA with RGAT-
BERT.

Table 3: The results of robustness analysis. 4 | Model | AddDiff | RevNon
---|---|---|---
| Acc. | F1 | Acc. | F1
Lap14 | BERT-SPC | 45.21 | 32.01 | 50.20 | 41.61
BERT-SPC${}_{\texttt{IEGA}}$ | 48.74 | 35.81 | 52.47 | 44.47
Res14 | BERT-SPC | 64.84 | 50.98 | 62.44 | 41.61
BERT-SPC${}_{\texttt{IEGA}}$ | 67.10 | 52.28 | 66.03 | 58.16
Res15 | BERT-SPC | 46.38 | 33.38 | 56.58 | 38.45
BERT-SPC${}_{\texttt{IEGA}}$ | 53.26 | 39.22 | 58.00 | 40.94
Res16 | BERT-SPC | 43.04 | 36.57 | 56.95 | 43.05
BERT-SPC${}_{\texttt{IEGA}}$ | 52.19 | 39.68 | 59.07 | 43.60
4 |  |  |  |  |

Robustness Analysis.  We also analyze the robustness of our proposed IEGA
framework (Table 3). We test our model on two robustness testing datasets
released by TextFlint [22]. RevNon reverses the sentiment of the non-target
aspects with originally the same sentiment as the target aspect’s, and AddDiff
adds a new non-target aspect whose sentiment is opposite to the target aspect
of the sentence. We find that BERT-SPC${}_{\texttt{IEGA}}$ outperforms BERT-
SPC over all datasets in terms of accuracy and F1. It shows that the model
infers the sentiment based on the opinion words w.r.t the aspect stably. These
observations suggest that our framework does have a large improvement in the
robustness of the model.

##  4 Related Work

Gradient-based Analysis Models.  Recently, studies on explanation methods has
grown, including perturbation-based [3], gradient-based [23] and
visualization-based [24] methods. We focus on the gradient-based method [5], a
popular algorithm applicable to different neural network models. Gradient-
based methods [25] have been widely applied into CV and NLP [24, 26]. The
gradient-based approach is also used to understand the predictions of the text
classification models from the token level [27, 28]. In addition, Rei et al.
[29] adopted a gradient-based approach to detect the critical tokens in the
sentence via the sentence-level label. The existing work also found that the
gradient-based models are easily manipulable [10] and unreliable [11]. In this
paper, we design an IEGA algorithm to force the model to discover the target-
aware opinion words using the gradient.

Aspect-based Sentiment Classification.  In recent years, thanks to the
introduction of pre-trained language models, it has made tremendous progress
in many NLP tasks, including aspect-based sentiment classification (ABSC)
[30]. By simply connecting the aspect words with the original sentence and
then inputting them into BERT for training, researchers obtain excellent
results in ABSC tasks [12]. Furthermore, Song et al.[20] proposed AEN-BERT,
which adopts attention-based encoders to model the interaction between context
and aspect. Zeng et al. [21] proposed LCF-BERT, which uses multi-head self-
attention to make the model focus on the local context words. Wang et al. [13]
proposed a relation-aware graph attention network to model the tree structure
knowledge for sentiment classification. However, most of them focus on
improving performance, while the explanation of ABSC is not well studied.
Yadav et al. [31] proposed a human-interpretable learning approach for ABSC,
but there is still a big gap in accuracy compared to the state-of-the-art
methods.

##  5 Conclusions and Future Work

In this paper, we introduce an IEGA framework to improve the explanations of
the gradient-based methods for ABSC. We design a gradient correction algorithm
based on the word-level saliency map via a tiny amount of labeled samples. We
conduct extensive experimental results with various metrics over four popular
datasets to verify the interpretation, performance, and robustness of the
models using our IEGA. We also explore the influence of sample numbers and
find that our framework can effectively improve the interpretation with small
samples. It would be interesting to explore the performance of our model on
more existing methods and tasks because IEGA is model agnostic and task
agnostic.

## Acknowledge

The authors wish to thank the reviewers for their helpful comments and
suggestions. This research is funded by the National Key Research and
Development Program of China (No. 2021ZD0114002), the National Natural Science
Foundation of China (No. 61907016) and the Science and Technology Commission
of Shanghai Municipality Grant (No. 22511105901 & No. 21511100402).

## References

  * [1] Marina Danilevsky, Kun Qian, Ranit Aharonov, Yannis Katsis, Ban Kawas, and Prithviraj Sen,  “A survey of the state of explainable AI for natural language processing,”  in Proceedings of AACL, 2020.
  * [2] Jie Zhou, Yuanbin Wu, Qin Chen, Xuan-Jing Huang, and Liang He,  “Attending via both fine-tuning and compressing,”  in Proceedings of ACL, 2021, pp. 2152–2161.
  * [3] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin,  “" why should i trust you?" explaining the predictions of any classifier,”  in Proceedings of SIGKDD, 2016, pp. 1135–1144.
  * [4] Eric Wallace, Jens Tuyls, Junlin Wang, Sanjay Subramanian, Matt Gardner, and Sameer Singh,  “Allennlp interpret: A framework for explaining predictions of nlp models,”  in Proceedings of EMNLP, 2019, pp. 7–12.
  * [5] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman,  “Deep inside convolutional networks: Visualising image classification models and saliency maps,”  in Proceedings of ICLR, 2014.
  * [6] Mukund Sundararajan, Ankur Taly, and Qiqi Yan,  “Axiomatic attribution for deep networks,”  in Proceedings of ICML, 2017, pp. 3319–3328.
  * [7] Malika Aubakirova and Mohit Bansal,  “Interpreting neural networks to improve politeness comprehension,”  in Proceedings of EMNLP, 2016, pp. 2035–2041.
  * [8] Sweta Karlekar, Tong Niu, and Mohit Bansal,  “Detecting linguistic characteristics of alzheimer’s dementia by interpreting neural models,”  in Proceedings of NAACL, 2018, pp. 701–707.
  * [9] Jie Zhou, Yuanbin Wu, Changzhi Sun, and Liang He,  “Is “hot pizza” positive or negative? mining target-aware sentiment lexicons,”  in Proceedings of EACL, 2021, pp. 608–618.
  * [10] Junlin Wang, Jens Tuyls, Eric Wallace, and Sameer Singh,  “Gradient-based analysis of nlp models is manipulable,”  in Proceedings of EMNLP, 2020, pp. 247–258.
  * [11] Pieter-Jan Kindermans, Sara Hooker, Julius Adebayo, Maximilian Alber, Kristof T Schütt, Sven Dähne, Dumitru Erhan, and Been Kim,  “The (un) reliability of saliency methods,”  in Explainable AI: Interpreting, Explaining and Visualizing Deep Learning, pp. 267–280. Springer, 2019.
  * [12] Hu Xu, Bing Liu, Lei Shu, and Philip Yu,  “BERT post-training for review reading comprehension and aspect-based sentiment analysis,”  in Proceedings of NAACL, 2019, pp. 2324–2335.
  * [13] Kai Wang, Weizhou Shen, Yunyi Yang, Xiaojun Quan, and Rui Wang,  “Relational graph attention network for aspect-based sentiment analysis,”  in Proceedings of ACL, 2020, pp. 3229–3238.
  * [14] David Baehrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus-Robert Müller,  “How to explain individual classification decisions,”  JMLR, vol. 11, pp. 1803–1831, 2010.
  * [15] Zhifang Fan, Zhen Wu, Xin-Yu Dai, Shujian Huang, and Jiajun Chen,  “Target-oriented opinion words extraction with target-fused neural sequence labeling,”  in Proceedings of NAACL, June 2019, pp. 2509–2518.
  * [16] Dong Nguyen,  “Comparing automatic and human evaluation of local explanations for text classification,”  in Proceedings of NAACL, 2018, pp. 1069–1078.
  * [17] Wojciech Samek, Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, and Klaus-Robert Müller,  “Evaluating the visualization of what a deep neural network has learned,”  IEEE TNNLS, vol. 28, no. 11, pp. 2660–2673, 2016.
  * [18] Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan,  “Learning to explain: An information-theoretic perspective on model interpretation,”  in Proceedings of ICML, 10–15 Jul 2018, vol. 80, pp. 883–892.
  * [19] Hanjie Chen and Yangfeng Ji,  “Learning variational word masks to improve the interpretability of neural text classifiers,”  in Proceedings of EMNLP, 2020, pp. 4236–4251.
  * [20] Youwei Song, Jiahai Wang, Tao Jiang, Zhiyue Liu, and Yanghui Rao,  “Attentional encoder network for targeted sentiment classification,”  arXiv preprint arXiv:1902.09314, 2019.
  * [21] Biqing Zeng, Heng Yang, Ruyang Xu, Wu Zhou, and Xuli Han,  “Lcf: A local context focus mechanism for aspect-based sentiment classification,”  Applied Sciences, vol. 9, no. 16, pp. 3389, 2019.
  * [22] Xiao Wang, Qin Liu, Tao Gui, Qi Zhang, Yicheng Zou, Xin Zhou, Jiacheng Ye, Yongxin Zhang, Rui Zheng, Zexiong Pang, et al.,  “Textflint: Unified multilingual robustness evaluation toolkit for natural language processing,”  in Proceedings of ACL, 2021, pp. 347–355.
  * [23] Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, Klaus-Robert Müller, and Wojciech Samek,  “Layer-wise relevance propagation for neural networks with local renormalization layers,”  in Proceedings of ICANN, 2016, pp. 63–71.
  * [24] Matthew D. Zeiler and Rob Fergus,  “Visualizing and understanding convolutional networks,”  in ECCV, 2014, vol. 8689 of Lecture Notes in Computer Science, pp. 818–833.
  * [25] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy,  “Explaining and harnessing adversarial examples,”  in Proceedings of ICLR, 2015.
  * [26] Bin Liang, Hongcheng Li, Miaoqiang Su, Pan Bian, Xirong Li, and Wenchang Shi,  “Deep text classification can be fooled,”  in Proceedings of IJCAI, 2018, pp. 4208–4215.
  * [27] Jiwei Li, Xinlei Chen, Eduard H. Hovy, and Dan Jurafsky,  “Visualizing and understanding neural models in NLP,”  in Proceedings of NAACL, 2016, pp. 681–691.
  * [28] Dimitrios Alikaniotis, Helen Yannakoudakis, and Marek Rei,  “Automatic text scoring using neural networks,”  in Proceedings of ACL, 2016.
  * [29] Marek Rei and Anders Søgaard,  “Zero-shot sequence labeling: Transferring knowledge from sentences to tokens,”  in Proceedings of NAACL, 2018, pp. 293–302.
  * [30] Jie Zhou, Jimmy Xiangji Huang, Qin Chen, Qinmin Vivian Hu, Tingting Wang, and Liang He,  “Deep learning for aspect-level sentiment classification: survey, vision, and challenges,”  IEEE access, vol. 7, pp. 78454–78483, 2019.
  * [31] Rohan K Yadav, Lei Jiao, Ole-Christoffer Granmo, and Morten Goodwin,  “Human-level interpretable learning for aspect-based sentiment analysis,”  in Proceedings of AAAI, 2021, vol. 35, pp. 14203–14212.