Entanglement Classification via Operator Size

Qi-Feng Wu1,2,3$\star$

1 Department of Physics and Center for Field Theory and Particle Physics,
Fudan University, Shanghai, 200433, China

2 Yau Mathematical Sciences Center, Tsinghua University, Beijing 100084, China

3 Department of Physics and Astronomy, Ghent University, 9000 Ghent, Belgium

$\star$<EMAIL_ADDRESS>
## Abstract

In this work, multipartite entanglement is classified by polynomials. I show
that the operator size is closely related to the entanglement structure. Given
a generic quantum state, I define a series of subspaces generated by operators
of different sizes acting on it. The information about the entanglement is
encoded into these subspaces. With the dimension of these subspaces as
coefficients, I define a polynomial which I call the entanglement polynomial.
The entanglement polynomial induces a homomorphism from quantum states to
polynomials. It implies that we can characterize and find the building blocks
of entanglement by polynomial factorization. Two states share the same
entanglement polynomial if they are equivalent under the stochastic local
operations and classical communication. To calculate the entanglement
polynomial practically, I construct a series of states, called renormalized
states, whose ranks are related to the coefficients of the entanglement
polynomial.

###### Contents

  1. 1 Introduction
  2. 2 Entanglement polynomial
  3. 3 Isomorphism
  4. 4 Symmetry
  5. 5 Renormalized state
  6. 6 Conclusion
  7. A Proof of $f(|\psi\rangle\otimes|\phi\rangle)=f(|\psi\rangle)\cdot f(|\phi\rangle)$
  8. B Size additivity and polynomial factorization
    1. B.1 State-dependent operator size
    2. B.2 Size additivity
  9. C Proof of Theorem 3
  10. D Proof of $W_{k}=\text{Im}(\rho_{k})$

##  1 Introduction

Operator size is a measure of local degrees of freedom on which an operator
has a nontrivial action [1, 2]. It is also a characteristic of operator
scrambling [3, 4]. In AdS/CFT, it was conjectured that the size of a boundary
operator is related to the bulk radial momentum [5, 6, 7]. However, there is
an ambiguity that operators of different sizes can map a given state to
another same state, which can be understood in terms of stabilizer formalism
[8, 9]. A similar issue occurs in AdS/CFT due to its quantum error correction
property [10]. To fix such an ambiguity, I generalize the operator size to be
state-dependent, such that operators have the same size if they have the same
action on a given state [11]. For a given state $|\psi\rangle$, the state-
dependent operator size of an operator $\mathcal{O}$ can be defined as the
expectation value of a state-dependent operator $n_{|\psi\rangle}$ called size
operator,

$\mathcal{S}_{|\psi\rangle}(\mathcal{O})\equiv\frac{\langle\psi|\mathcal{O}^{\dagger}n_{|\psi\rangle}\mathcal{O}|\psi\rangle}{\langle\psi|\mathcal{O}^{\dagger}\mathcal{O}|\psi\rangle}.$
(1)

A similar definition of state-dependent operator size is proposed in [12].

In this paper, I will not discuss the entanglement dynamics mentioned above
but focus on the classification of entanglement structures. Entanglement
classification is a long-standing open problem in quantum information theory.
Various methods were proposed [13, 14, 15, 16, 17, 18, 19, 20], but our
understanding of multipartite entanglement is still limited. I show that the
entanglement structure of $|\psi\rangle$ is encoded into eigenspaces of
$n_{|\psi\rangle}$. As we will see, the dimensions of these eigenspaces are
characteristics of entanglement. They form the coefficients of a polynomial
which can classify multipartite entanglement. So I call it the entanglement
polynomial.

I prove that the entanglement polynomial is a SLOCC invariant and thus is a
characteristic of the entanglement [13]. Here the SLOCC stands for stochastic
local operations and classical communication. As a map from quantum states to
polynomials, the entanglement polynomial preserves the product structure,
which means the entanglement polynomial of the tensor product of two states is
the product of the entanglement polynomials of these two states. In other
words, entanglement polynomial induces a homomorphism. More precisely, we will
see that it is a monoid homomorphism. Since product states are mapped to
reducible polynomials, we can find and characterize the building blocks of
entanglement by polynomial factorization.

We can construct an isomorphism by taking the quotient over the kernel of
homomorphism. Applying this fact to the entanglement polynomial, we obtain an
isomorphism from equivalence classes of states to polynomials. Since
entanglement polynomial is a SLOCC invariant, states of the same equivalence
class share a similar entanglement structure. Thus, the entanglement
polynomial induces a classification of entanglement. It can be shown that the
number of these classes is finite if the Hilbert space is finite-dimensional.

This paper is organized as follows. In Section 2, we introduce some relevant
concepts and define the entanglement polynomial. In Section 3, we show that
the entanglement polynomial induces a homomorphism from quantum states to
polynomials. By taking the quotient over the kernel of this homomorphism, we
obtain an isomorphism from entanglement classes to polynomials. In Section 4,
we show that there exists a class of operators preserving the entanglement
polynomial of any state. Two examples of such operators are local invertible
operators and permutation operators. We call these operators the symmetries of
the entanglement polynomial. In Section 5, we construct a series of states
called renormalized states. We show that the ranks of these states are related
to the coefficients of entanglement polynomials. We can use this relation to
calculate the entanglement polynomial practically. In Section 6, we summarize
the results of this paper. In Appendix A, we prove that entanglement
polynomial preserves the product structure. In Appendix B, we illustrate how
the factorization of the entanglement polynomials is related to the size
additivity. In Appendix C, a theorem about the symmetry of the entanglement
polynomial is proven. In Appendix D, the relation between renormalized states
and coefficients of the entanglement polynomial is proven.

##  2 Entanglement polynomial

We first review several relevant notions and then define the entanglement
polynomial. For simplicity, we consider quidts.

The Hilbert space of $N$ qudits is given by

$\mathcal{H}=\bigotimes_{i=1}^{N}\mathcal{H}_{i},\quad\mathcal{H}_{i}\cong\mathbb{C}^{d}.$
(2)

$\mathcal{H}_{i}$ is the Hilbert space of the $i$-th qudit. Suppose that $B$
is a subset of these qudits and $|B|$ is the number of qudits of it. We denote
the linear space of operators acting on $B$ nontrivially as

$\mathcal{A}_{B}=\\{\mathcal{O}_{B}\otimes
I_{\bar{B}}\,|\,\mathcal{O}_{B}\in\mathrm{End}(\mathcal{H}_{B}),\,\mathcal{H}_{B}=\bigotimes_{i\in
B}\mathcal{H}_{i}\\}.$ (3)

$\bar{B}$ denotes the complement of $B$. $I_{\bar{B}}$ is the identity acting
on $\mathcal{H}_{\bar{B}}$. Then we define a linear space of operators as

$V^{k}\equiv\sum_{|B|=k}\mathcal{A}_{B}.$ (4)

The summation here means that $V^{k}$ is spanned by the elements in
$\mathcal{A}_{B}$’s. We set $V^{0}\equiv\textrm{Span}\\{I\\}$. Operators in
$V^{k}$ are called $k$-local operators. We can see that a $k$-local operator
can always be written as a linear combination of the tensor products of $k$
local operators. Given a state $|\psi\rangle$, we can construct the subspace

$W_{k}\equiv\textrm{Span}\\{\mathcal{O}|\psi\rangle\,\big{|}\,\mathcal{O}\in
V^{k}\\}.$ (5)

$W_{k}$ can be decomposed as follows

$W_{k}=\Delta W_{k}\oplus W_{k-1},\quad\Delta W_{k}\perp W_{k-1},\quad 0\leq
k\leq N_{|\psi\rangle}.$ (6)

$N_{|\psi\rangle}$ is the minimal value of $k$ such that $W_{k+1}=W_{k}$. We
set $W_{-1}$ as the empty set. The meaning of $\Delta W_{k}$ is that we only
need $k$-local operators acting on $|\psi\rangle$ to generate $\Delta W_{k}$
which cannot be generated by $(k-1)$-local operators. Each state in $\Delta
W_{k}$ can be perfectly distinguished from states that can be generated by
$(k-1)$-local operators acting on $|\psi\rangle$. Then we can say that there
are $k$ local d.o.f. that are changed when $|\psi\rangle$ evolves to a state
in $\Delta W_{k}$. For this reason, we call $\Delta W_{k}$ the $k$-local
subspace. In [11], the eigenspaces of the size operator in Eq. (1) are defined
as the $k$-local subspaces. For more details, see Appendix B.

Then we define the entanglement polynomial as

$f(|\psi\rangle)\equiv\sum_{k=0}^{N_{|\psi\rangle}}|\Delta W_{k}|x^{k}.$ (7)

$|\Delta W_{k}|$ is the dimension of $\Delta W_{k}$. $x$ is a symbol. This
polynomial encodes the information about the number of states that can be
generated by $k$-local operators, which is a property closely related to the
entanglement structure.

##  3 Isomorphism

A monoid is a set that is closed under an associative binary operation and has
an identity element. As mentioned in the introduction, the entanglement
polynomial induces a monoid homomorphism from states to polynomials.

To illustrate it, we consider an infinite number of qudits in this section.
Denote the set of quantum states of all of the subsystems of these qudits as
$S$. We can show that $S$ is a monoid with the tensor product as the
associative binary operation. To check it, we first note that the tensor
product between two quantum states is a binary operation and it is
associative. Since two non-overlapping subsystems still form a subsystem, $S$
is closed under the tensor product. To specify the identity, we note that the
empty set $\emptyset$ is also a subsystem of qudits, and the union of
$\emptyset$ and an arbitrary subsystem $B$ is still $B$. So the quantum state
of $\emptyset$ is the identity w.r.t. the tensor product. We denote it as
$|\emptyset\rangle$. Note that the Hilbert space dimension of $n$ qudits is
$d^{n}$. Since $\emptyset$ is the set of zero qudits, its Hilbert space is
one-dimensional. So $|\emptyset\rangle$ is unique. Then we have

$|\psi\rangle\otimes|\emptyset\rangle=|\emptyset\rangle\otimes|\psi\rangle=|\psi\rangle,\quad|\psi\rangle,|\emptyset\rangle\in
S.$ (8)

Putting these facts together, we can see that $S$ is indeed a monoid.

The entanglement polynomial maps $S$ to a set of polynomials denoted by
$f(S)$. $f(S)$ is also a monoid. To see this, we note that no nontrivial
operator acts on the Hilbert space of zero qudits, so we have

$f(|\emptyset\rangle)=1.$ (9)

Thus $f(|\emptyset\rangle)$ is the identity w.r.t. the polynomial
multiplication “ $\cdot$ ". Obviously, “ $\cdot$ " is an associative binary
operation. In Appendix A, I prove that

$f(|\psi\rangle\otimes|\phi\rangle)=f(|\psi\rangle)\cdot f(|\phi\rangle)$ (10)

for arbitrary two states. Thus, $f(S)$ is closed under “ $\cdot$ ". Collecting
these facts, we can see that $f(S)$ is also a monoid. Eq. (10) also implies
that $f$ preserves the product structure, so we have the following theorem.

###### Theorem 1

The entanglement polynomial induces a monoid homomorphism from the state
monoid $S$ to the polynomial monoid $f(S)$.

We can construct an isomorphism by taking quotient over the kernel of the
homomorphism. To take the quotient, we define an equivalence relation “$\sim$"
over $S$ such that $|\psi\rangle\sim|\phi\rangle$ if
$f(|\psi\rangle)=f(|\phi\rangle)$. Obviously, we have

$|\psi\rangle\sim|\psi\rangle,$ (11a)
$|\psi\rangle\sim|\phi\rangle\Rightarrow|\phi\rangle\sim|\psi\rangle,$ (11b)
$|\psi\rangle\sim|\phi\rangle,\,|\phi\rangle\sim|\chi\rangle\Rightarrow|\psi\rangle\sim|\chi\rangle.$
(11c)

So “$\sim$" is indeed an equivalence relation. In fact, it is a congruence
relation, which means that

$|\psi_{1}\rangle\sim|\phi_{1}\rangle,\,|\psi_{2}\rangle\sim|\phi_{2}\rangle\Rightarrow|\psi_{1}\rangle\otimes|\psi_{2}\rangle\sim|\phi_{1}\rangle\otimes|\phi_{2}\rangle$
(12)

is further satisfied. The equivalence class of $|\psi\rangle$ under “$\sim$"
is denoted by $[|\psi\rangle]$. Since “$\sim$" is a congruence relation, the
“tensor product" between $[|\psi\rangle]$ and $[|\phi\rangle]$ can be uniquely
defined by

$[|\psi\rangle]\otimes[|\phi\rangle]\equiv[|\psi\rangle\otimes|\phi\rangle].$
(13)

Now we can define the quotient monoid $S/\ker f$ by

$S/\ker f\equiv\\{[|\psi\rangle]\,\big{|}\,|\psi\rangle\in S\\}$ (14)

with the tensor product defined in Eq. (13) as the associative binary
operation. According to the first isomorphism theorem, the polynomial monoid
$f(S)$ is isomorphic to $S/\ker f$,

$f(S)\cong S/\ker f.$ (15)

To specify the isomorphism map, we define the entanglement polynomial of an
equivalence class by

$f([|\psi\rangle])\equiv f(|\psi\rangle).$ (16)

Since equivalent states have the same entanglement polynomial, this definition
is unique. Then we have

###### Theorem 2

The entanglement polynomial induces an isomorphism from the quotient monoid
$S/\text{ker}f$ to the polynomial monoid $f(S)$.

According to Eq. (10), product states are mapped to reducible polynomials in
$f(S)$, so we can find basic building blocks of entanglement by polynomial
factorization. For this reason, we call elements in $S/\text{ker}f$ the
entanglement classes.

##  4 Symmetry

Besides calculating by definition, symmetries of entanglement polynomials can
determine whether two states are in the same entanglement class. By symmetry,
I mean an operator $g$ satisfying

$f(g|\psi\rangle)=f(|\psi\rangle).$ (17)

Unlike the case of groups, the kernel of a monoid homomorphism cannot be
determined by the preimage of the identity. So the symmetry generally depends
on the specific state $|\psi\rangle$. However, we can still find some state-
independent symmetries. Define the adjoint action of an invertible operator
$g$ by

$\text{ad}_{g}\mathcal{O}\equiv g^{-1}\mathcal{O}g,$ (18)

The adjoint action on an operator space $M$ is defined by

$\text{ad}_{g}M\equiv\\{\text{ad}_{g}\mathcal{O}\,\big{|}\,\mathcal{O}\in
M\\}.$ (19)

Then we have the following theorem (for the proof, see Appendix C).

###### Theorem 3

If $\forall k\in\mathbb{N}$, adg induces an automorphism on $V^{k}$, then $g$
keeps entanglement polynomials invariant, i.e.

$\text{ad}_{g}V^{k}=V^{k},\,\forall k\Rightarrow
f(g|\psi\rangle)=f(|\psi\rangle),\,\forall\,|\psi\rangle.$ (20)

As an explicit example, we show that if two states are equivalent under
stochastic local operations and classical communication (SLOCC), they are in
the same entanglement class. In [13], it was proven that $|\psi\rangle$ and
$|\phi\rangle$ are equivalent under SLOCC if and only if there exists an
invertible local operator $L$ such that

$|\psi\rangle=L|\phi\rangle.$ (21)

Given a set of $N$ qudits, an invertible local operator $L$ is an operator of
the following form

$L=\bigotimes_{i=1}^{N}L_{i},\quad L_{i}\in\textrm{Aut}(\mathcal{H}_{i}).$
(22)

$L_{i}$ is an invertible operator acting on the $i$-th qudit. By definition,
operators in $V^{k}$ can be expressed as

$\mathcal{O}=\sum_{|B|=k}c_{B}I_{\bar{B}}\otimes\bigotimes_{i\in
B}\mathcal{O}_{i}.$ (23)

$B$ labels subsets of $N$ qudits. $|B|$ is the number of qudits in $B$.
$\mathcal{O}_{i}\in\textrm{End}(\mathcal{H}_{i})$, $c_{B}\in\mathbb{C}$. Then
we have

$\textrm{ad}_{L}\mathcal{O}\equiv
L^{-1}\mathcal{O}L=\sum_{|B|=k}c_{B}I_{\bar{B}}\otimes\bigotimes_{i\in
B}L_{i}^{-1}\mathcal{O}_{i}L_{i}.$ (24)

Note that $L_{i}^{-1}\mathcal{O}_{i}L_{i}\in\text{End}(\mathcal{H}_{i})$ and
$L$ is invertible, so $\textrm{ad}_{L}$ induces an automorphism on $V^{k}$ for
all $k$. Thus, Theorem 3 implies the following theorem.

###### Theorem 4

If two states are equivalent under SLOCC, then their entanglement polynomials
are equal.

Another example of the symmetry is the permutation. A permutation can be
generated by a series of swap operators $X_{i}$ satisfying

$X_{i}|a\rangle_{i}|b\rangle_{i+1}=|b\rangle_{i}|a\rangle_{i+1},$ (25)

for all $|a\rangle_{i},\,|b\rangle_{i}\in\mathcal{H}_{i}$ and
$|a\rangle_{i+1},\,|b\rangle_{i+1}\in\mathcal{H}_{i+1}$. Then the action of
$\text{ad}_{X_{i}}$ on $\mathcal{O}$ is to swap $\mathcal{O}_{i}$ and
$\mathcal{O}_{i+1}$, such that $X_{i}^{-1}\mathcal{O}X_{i}\in V^{k}$. Since
$X_{i}$ is invertible, $\textrm{ad}_{X_{i}}$ induces an automorphism. So swap
operators are symmetries of entanglement polynomials. Since each permutation
in the permutation group SymN is the product of a series of $X_{i}$’s, it also
keeps the entanglement polynomials invariant. So two states in the same SLOCC
class or SymN class must belong to the same entanglement class.

According to Eq. (5), the coefficients of an entanglement polynomial is an
integer partition of the Hilbert space dimension, which means it can always
classify states into a finite number of entanglement classes if the Hilbert
space is finite-dimensional.

##  5 Renormalized state

To calculate the entanglement polynomial efficiently, we construct a series of
states whose ranks are related to entanglement polynomials. Given a state
$\rho$, we define the renormalized states as

$\rho_{k}\equiv\frac{\sum_{|B|=k}\rho_{\bar{B}}}{\sum_{|B|=k}\text{tr}(\rho_{\bar{B}})}.$
(26)

$\rho_{\bar{B}}\in\mathcal{A}_{\bar{B}}$ is the reduced density matrix
satisfying

$\textrm{tr}(\mathcal{O}_{\bar{B}}\rho)=\textrm{tr}(\mathcal{O}_{\bar{B}}\rho_{\bar{B}}),\,\forall\mathcal{O}_{\bar{B}}\in\mathcal{A}_{\bar{B}}.$
(27)

To illustrate the physical meaning of $\rho_{k}$, suppose the system is in a
state $\rho$, and we try to measure the operator $\mathcal{O}$ in a noisy
laboratory. The effect of the noise is to disturb our observation such that we
cannot access some parts of the system. The noise is stochastic, so the
position of the lost part $B$ is random. At each observation, the expectation
value of $\mathcal{O}$ is

$\langle\mathcal{O}\rangle_{\textrm{noise}}=\textrm{tr}(\mathcal{O}\rho_{\bar{B}}).$
(28)

If we perform many experiments, the average of the expectation value is 111
Here we suppose the probability distribution of the lost parts is flat. We can
consider general distribution, see Appendix D.

$\overline{\langle\mathcal{O}\rangle_{\textrm{noise}}}=\frac{\sum_{B}\textrm{tr}(\mathcal{O}\rho_{\bar{B}})}{\sum_{B}\textrm{tr}(\rho_{\bar{B}})}.$
(29)

If the size of the lost part is always equal to $k$, then we have

$\overline{\langle\mathcal{O}\rangle_{\textrm{noise}}}=\textrm{tr}(\mathcal{O}\rho_{k}).$
(30)

So the renormalized states are effective states under the random noise of a
given size.

Then we can show that, given a pure state $\rho=|\psi\rangle\langle\psi|$,

$|W_{k}|=\text{Rank}(\rho_{k}).$ (31)

See Appendix D for the proof. As an example, we apply Eq. (31) to qubits.
According to Theorem 4, we only need to perform calculations for
representatives of SLOCC classes and permutation classes. Up to three qubits,
they are $|0\rangle$,

$|\textrm{Bell}\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle),$ (32a)
$|\textrm{W}\rangle=\frac{1}{\sqrt{3}}(|100\rangle+|010\rangle+|001\rangle),$
(32b) $|\textrm{GHZ}\rangle=\frac{1}{\sqrt{2}}(|000\rangle+|111\rangle),$
(32c)

and tensor products of them, i.e. $|00\rangle$, $|000\rangle$,
$|0\rangle|\textrm{Bell}\rangle$. The results are listed in Table 1 and Table
2.

$|\psi\rangle$ | $|0\rangle$ | $|\text{Bell}\rangle$ | $|\text{W}\rangle$ | $|\text{GHZ}\rangle$
---|---|---|---|---
$f(|\psi\rangle)$ | $1+x$ | $1+3x$ | $1+6x+x^{2}$ | $1+7x$
Table 1: Entanglement polynomials of genuinely entangled states up to three qubits. $|\psi\rangle$ | $|00\rangle$ | $|000\rangle$ | $|0\rangle|\text{Bell}\rangle$
---|---|---|---
$f(|\psi\rangle)$ | $(1+x)^{2}$ | $(1+x)^{3}$ | $(1+x)(1+3x)$
Table 2: Entanglement polynomials of product states up to three qubits.

We can see that the entanglement polynomial clearly distinguishes the states
of different entanglement structures.

##  6 Conclusion

We have defined the entanglement polynomial which induces a monoid isomorphism
from entanglement classes to polynomials. The tensor product among states is
mapped to the polynomial product, which implies that we can find the basic
building blocks of entanglement by polynomial factorization. If an operator
induces automorphisms on all the subspaces of $k$-local operators, then it
keeps the entanglement polynomial invariant. As a consequence, the
entanglement polynomial is proven to be a SLOCC invariant. We then construct
the renormalized states and show that, by calculating their ranks, we can
calculate the entanglement polynomial practically.

## Acknowledgements

I would like to thank Ling-Yan Hung, Xiao-Liang Qi, Yong-Shi Wu, Xin-Yang Yu,
and Si-Nong Liu for their helpful discussions. I acknowledge the financial
support of Fudan University, Tsinghua University and Ghent University .

##  Appendix A Proof of
$f(|\psi\rangle\otimes|\phi\rangle)=f(|\psi\rangle)\cdot f(|\phi\rangle)$

For later convenience, we define the action of an operator space $M$ on a
Hilbert space $\mathcal{H}$ by

$M\mathcal{H}\equiv\textrm{Span}\\{\mathcal{O}|\psi\rangle\,\big{|}\,\mathcal{O}\in
M,\,|\psi\rangle\in\mathcal{H}\\},$ (33)

Denote the space spanned by $|\psi\rangle$ as $\mathcal{H}^{|\psi\rangle}$ .
We can rewrite the subspace defined by Eq. (5) as

$W_{k}^{|\psi\rangle}=V^{k}\mathcal{H}^{|\psi\rangle}.$ (34)

Notice that we add a superscript to $W_{k}$ to indicate its dependence on
$|\psi\rangle$. $V^{k}\mathcal{H}$ can be obtained by $V$ acting on
$\mathcal{H}$ $k$ times, which is

$V^{k}\mathcal{H}=(V)^{k}\mathcal{H}\equiv\underbrace{VV\dots
V}_{k}\mathcal{H}.$ (35)

$V$ is the space of 1-local operators. We can also define the multiplication
between two operator spaces $V_{1}$ and $V_{2}$

$V_{1}V_{2}\equiv\textrm{Span}\\{\mathcal{O}_{1}\mathcal{O}_{2}\,\big{|}\,\mathcal{O}_{1}\in
V_{1},\,\mathcal{O}_{2}\in V_{2}\\},$ (36)

such that we have

$V^{k}=(V)^{k}\equiv\underbrace{VV\dots V}_{k}.$ (37)

So we can rewrite $(V)^{k}$ as $V^{k}$ for simplicity. The symbol “$\Delta$”
in Eq. (6) can be defined as an operator $\Delta_{k}$ acting the the Hilbert
space with the index $k$, i.e.

$W_{k}=\Delta_{k}W_{k}\oplus W_{k-1},\quad\Delta_{k}W_{k}\perp W_{k-1}.$ (38)

Suppose a system is divided into two parts, $B$ and $\bar{B}$. Denote the
space of 1-local operators acting on $B$ and $\bar{B}$ as $V_{B}$ and
$V_{\bar{B}}$ respectively. Then we have

$V=V_{B\cup\bar{B}}=V_{B}+V_{\bar{B}}.$ (39)

Take the $k$-th power

$V^{k}=(V_{B}+V_{\bar{B}})^{k}=\sum_{l+m=k}(V_{\bar{B}})^{m}(V_{B})^{l}.$ (40)

Given a state $|\psi\rangle\otimes|\phi\rangle$ with
$|\psi\rangle\in\mathcal{H}_{B}$ and $|\phi\rangle\in\mathcal{H}_{\bar{B}}$.
Using Eq. (40), we have

$\begin{split}V^{k}(\mathcal{H}^{|\psi\rangle}\otimes\mathcal{H}^{|\phi\rangle})&=\sum_{l+m=k}(V_{\bar{B}})^{m}(V_{B})^{l}(\mathcal{H}^{|\psi\rangle}\otimes\mathcal{H}^{|\phi\rangle})\\\
&=\sum_{l+m=k}V_{\bar{B}}^{m}V_{B}^{l}\,(\mathcal{H}^{|\psi\rangle}\otimes\mathcal{H}^{|\phi\rangle})\\\
&=\sum_{l+m=k}V^{m}_{\bar{B}}\bigoplus_{p=0}^{l}\Delta_{p}(V^{p}_{B}(\mathcal{H}^{|\psi\rangle}\otimes\mathcal{H}^{|\phi\rangle}))\\\
&=\sum_{l+m=k}V^{m}_{\bar{B}}\bigoplus_{p=0}^{l}\Delta_{p}(V^{p}_{B}\mathcal{H}^{|\psi\rangle})\otimes\mathcal{H}^{|\phi\rangle}\\\
&=\sum_{l+m=k}\bigoplus_{p=0}^{l}\Delta_{p}(V^{p}_{B}\mathcal{H}^{|\psi\rangle})\otimes
V^{m}_{\bar{B}}\mathcal{H}^{|\phi\rangle}\\\
&=\sum_{l+m=k}\bigoplus_{p=0}^{l}\bigoplus_{q=0}^{m}\Delta_{p}(V^{p}_{B}\mathcal{H}^{|\psi\rangle})\otimes\Delta_{q}(V^{q}_{\bar{B}}\mathcal{H}^{|\phi\rangle})\\\
&=\bigoplus_{l+m=k}\bigoplus_{p=0}^{l}\bigoplus_{q=0}^{m}\Delta_{p}(V^{p}_{B}\mathcal{H}^{|\psi\rangle})\otimes\Delta_{q}(V^{q}_{\bar{B}}\mathcal{H}^{|\phi\rangle})\\\
&=\bigoplus_{l+m=k}\bigoplus_{p=0}^{l}\bigoplus_{q=0}^{m}\Delta_{p}W_{p}^{|\psi\rangle}\otimes\Delta_{q}W_{q}^{|\phi\rangle}.\end{split}$
(41)

In the first equality, we used Eq. (40). In the second equality, we rewrite
$(V_{\bar{B}})^{m}$ and $(V_{B})^{l}$ as $V_{\bar{B}}^{m}$ and $V_{B}^{l}$
respectively for simplicity. In the third equality, We used Eq. (38) to expand
$V_{B}^{l}\,(\mathcal{H}^{|\psi\rangle}\otimes\mathcal{H}^{|\phi\rangle})$ in
terms of
$\Delta_{p}(V^{p}_{B}(\mathcal{H}^{|\psi\rangle}\otimes\mathcal{H}^{|\phi\rangle}))$’s.
In the forth equality, we used the fact that the action of $V_{B}^{p}$ on
$\mathcal{H}^{|\psi\rangle}$ is trivial. In the fifth equality, we used the
fact that the action of $V_{\bar{B}}^{m}$ on $\mathcal{H}^{|\phi\rangle}$ is
trivial. In the sixth equality, we expand
$V^{m}_{\bar{B}}\mathcal{H}^{|\phi\rangle}$ in terms of
$\Delta_{q}(V^{q}_{\bar{B}}\mathcal{H}^{|\phi\rangle})$’s. The seventh
equality holds, because
$\Delta_{p}(V^{p}_{B}\mathcal{H}^{|\psi\rangle})\otimes\Delta_{q}(V^{q}_{\bar{B}}\mathcal{H}^{|\phi\rangle})$
with different values of $p$ and $q$ are orthogonal to each other. In the
eighth line, we used Eq. (34).

Let $\Delta_{k}$ act on the left side and the last line of Eq. (41), we get

$\Delta_{k}W_{k}^{|\psi\rangle|\phi\rangle}=\bigoplus_{l+m=k}\Delta_{l}W_{l}^{|\psi\rangle}\otimes\Delta_{m}W_{m}^{|\phi\rangle}.$
(42)

Then compute the dimension

$\begin{split}|\Delta_{k}W_{k}^{|\psi\rangle|\phi\rangle}|&=\sum_{l+m=k}|\Delta_{l}W_{l}^{|\psi\rangle}\otimes\Delta_{m}W_{m}^{|\phi\rangle}|\\\
&=\sum_{l+m=k}|\Delta_{l}W_{l}^{|\psi\rangle}||\Delta_{m}W_{m}^{|\phi\rangle}|.\end{split}$
(43)

Remind that these are coefficients of entanglement polynomials

$\begin{split}f(|\psi\rangle)f(|\phi\rangle)&=(\sum_{l=0}^{N_{|\psi\rangle}}|\Delta_{l}W_{l}^{|\psi\rangle}|x^{l})(\sum_{m=0}^{N_{|\phi\rangle}}|\Delta_{m}W_{m}^{|\phi\rangle}|x^{m})\\\
&=\sum_{k}^{N_{|\psi\rangle}+N_{|\phi\rangle}}x^{k}\sum_{l+m=k}|\Delta_{l}W_{l}^{|\psi\rangle}||\Delta_{m}W_{m}^{|\phi\rangle}|\\\
&=\sum_{k}^{N_{|\psi\rangle}+N_{|\phi\rangle}}|\Delta_{k}W_{k}^{|\psi\rangle|\phi\rangle}||x^{k}\\\
&=\sum_{k}^{N_{|\psi\rangle\otimes|\phi\rangle}}|\Delta_{k}W_{k}^{|\psi\rangle|\phi\rangle}|x^{k}\\\
&=f(|\psi\rangle\otimes|\phi\rangle).\end{split}$ (44)

In the third equality, Eq. (43) is used. In the forth equality, we used
$N_{|\psi\rangle\otimes|\phi\rangle}=N_{|\psi\rangle}+N_{|\phi\rangle}$. Thus
Eq. (10) is proven. Note that if Eq. (10) is assumed, then we can derive Eq.
(43) by comparing the coefficients of the second line and that of the forth
line of Eq. (44). So Eq. (43) is equivalent to Eq. (10).

##  Appendix B Size additivity and polynomial factorization

Eq. (10) can be interpreted as a stronger form of the additivity of the state-
dependent operator size. To illustrate it, we first briefly review several
related notions.

###  B.1 State-dependent operator size

Given a state $|\psi\rangle$, we can costruct a series of subspaces $\Delta
W_{k}$ defined by Eq. (6). As mentioned in Section 2, states in $\Delta W_{k}$
cannot be generated by $k-1$-local operators acting on $|\psi\rangle$ but can
be generated by $k$-local operators. For this reason, if an operator
$\mathcal{O}$ transforms $|\psi\rangle$ into a state in $\Delta W_{k}$, then
we are tempted to say that there are $k$ qudits are changed by $\mathcal{O}$
on average. This is not a rigorous statement at this stage, but it is an
appropriate interpretation of $\Delta W_{k}$. In fact, this interpretation is
my original motivation to design the definition of the state-dependent
operator size [11].

Denote the projector onto $W_{k}$ as $P_{k}$. According to Eq. (6), the
projector onto $\Delta W_{k}$ is given by

$\Delta P_{k}=P_{k}-P_{k-1}.$ (45)

Suppose $|\psi\rangle$ is transformed into $|\phi\rangle$. According to the
above interpretation, if $|\phi\rangle\in\Delta W_{k}$ for some $k$, we say
that $k$ qudits are changed on average. In other words, there should be a size
operator such that $\Delta W_{k}$ is its eigenspace with eigenvalue equal to
$k$, i.e.

$n_{|\psi\rangle}=\sum_{k=0}^{N}k\Delta P_{k}.$ (46)

This is the size operator mentioned in Eq. (1). The subscript of
$n_{|\psi\rangle}$ indicates the dependence on $|\psi\rangle$ 222The range of
$k$ starting from 0 in Eq. (46) is chosen for later convenience. One may
notice that the subscript of $N_{|\psi\rangle}$ is omitted in Eq. (46). This
does not contradict with Eq. (6). According to Eq. (45), $\Delta P_{k}=0$ for
$k>N_{|\psi\rangle}$. This subscript will also be omitted in the following
formulas for the same reason. . $N$ is the number of all qudits. For a general
state $|\phi\rangle$, the expectation value of the number of changed qudits is

$\mathcal{S}(|\phi\rangle,|\psi\rangle)=\langle\phi|n_{|\psi\rangle}|\phi\rangle.$
(47)

We can call it the size of $|\phi\rangle$ relative to $|\psi\rangle$. Note
that if we replace $|\phi\rangle$ by
$\mathcal{O}|\psi\rangle/\langle\psi|\mathcal{O}^{\dagger}\mathcal{O}|\psi\rangle^{1/2}$,
then the state-dependent operator size mentioned in Eq. (1) is recovered.

###  B.2 Size additivity

Since the relative size defined in Eq. (47) is interpreted as the average
number of changed qudits, if there are two independent systems $B_{1}$ and
$B_{2}$, then the relative size should satisfy the additivity

$\mathcal{S}(|\phi_{1}\rangle|\phi_{2}\rangle,|\psi_{1}\rangle|\psi_{2}\rangle)=\mathcal{S}(|\phi_{1}\rangle,|\psi_{1}\rangle)+\mathcal{S}(|\phi_{2}\rangle,|\psi_{2}\rangle).$
(48)

$|\phi_{i}\rangle,\,|\psi_{i}\rangle\in\mathcal{H}_{B_{i}}$ with $i=1,\,2$.
$|\phi_{1}\rangle$ and $|\phi_{2}\rangle$ are arbitrary, so Eq. (48) is
equivalent to

$n_{|\psi_{1}\rangle|\psi_{2}\rangle}=n_{|\psi_{1}\rangle}+n_{|\psi_{2}\rangle}.$
(49)

Before proving it, let me illustrate a stronger condition that should hold.
Using Eq. (46) and Eq. (47), the relative size can be expressed as

$\mathcal{S}(|\phi_{i}\rangle,|\psi_{i}\rangle)=\sum_{k=0}^{N}k\langle\phi_{i}|\Delta
P_{k}^{|\psi_{i}\rangle}|\phi_{i}\rangle.$ (50)

The superscript of $\Delta P_{k}^{|\psi_{i}\rangle}$ indicates its dependence
on $|\psi_{i}\rangle$. $\langle\phi_{i}|\Delta
P_{k}^{|\psi_{i}\rangle}|\phi_{i}\rangle$ can be interpreted as the
probability that $k$ qudits are changed on average. We denote it as
$\textrm{Pr}_{i}(k)$ for later convenience,

$\textrm{Pr}_{i}(k)\equiv\langle\phi_{i}|\Delta
P_{k}^{|\psi_{i}\rangle}|\phi_{i}\rangle.$ (51)

We further denote the probability that $k_{1}$ qudits of $B_{1}$ and $k_{2}$
qudits of $B_{2}$ changed on average as $\textrm{Pr}(k_{1},\,k_{2})$. Since we
assume $B_{1}$ and $B_{2}$ are independent, we have

$\textrm{Pr}(k_{1},\,k_{2})=\textrm{Pr}_{1}(k_{1})\,\textrm{Pr}_{2}(k_{2}).$
(52)

Then the probability, $\textrm{Pr}(k_{1}+k_{2}=k)$, that the total number of
changed qudits of $B_{1}$ and $B_{2}$ is equal to $k$ should be given by

$\textrm{Pr}(k_{1}+k_{2}=k)=\sum_{k_{1}+k_{2}=k}\textrm{Pr}(k_{1},\,k_{2})=\sum_{k_{1}+k_{2}=k}\textrm{Pr}_{1}(k_{1})\,\textrm{Pr}_{2}(k_{2}).$
(53)

Using Eq. (51), we get

$\langle\phi_{1}|\langle\phi_{2}|\Delta
P_{k}^{|\psi_{1}\rangle|\psi_{2}\rangle}|\phi_{1}\rangle|\phi_{2}\rangle=\sum_{k_{1}+k_{2}=k}\langle\phi_{1}|\Delta
P_{k_{1}}^{|\psi_{1}\rangle}|\phi_{1}\rangle\langle\phi_{2}|\Delta
P_{k_{2}}^{|\psi_{2}\rangle}|\phi_{2}\rangle.$ (54)

Since $|\phi_{1}\rangle$ and $|\phi_{2}\rangle$ are arbitrary, we get

$\Delta P_{k}^{|\psi_{1}\rangle|\psi_{2}\rangle}=\sum_{k_{1}+k_{2}=k}\Delta
P_{k_{1}}^{|\psi_{1}\rangle}\Delta P_{k_{2}}^{|\psi_{2}\rangle}.$ (55)

I should emphasize that, until now, we have not proven or derived Eq. (48) or
Eq. (55). Instead, we are discussing what properties should hold for a proper
definition of relative size.

To prove them, note that $\Delta P_{k}$ is the projector onto $\Delta W_{k}$,
so Eq. (55) is equivalent to Eq. (42) which is proven in Section A. Eq. (48)
can be derived from Eq. (55). To see it, note that

$\begin{split}\mathcal{S}(|\phi_{1}\rangle|\phi_{2}\rangle,|\psi_{1}\rangle|\psi_{2}\rangle)&=\sum_{k=0}^{|B_{1}|+|B_{2}|}k\langle\phi_{1}|\langle\phi_{2}|\Delta
P_{k}^{|\psi_{1}\rangle|\psi_{2}\rangle}|\phi_{1}\rangle|\phi_{2}\rangle\\\
&=\sum_{k=0}^{|B_{1}|+|B_{2}|}k\sum_{k_{1}+k_{2}=k}\langle\phi_{1}|\Delta
P_{k_{1}}^{|\psi_{1}\rangle}|\phi_{1}\rangle\langle\phi_{2}|\Delta
P_{k_{2}}^{|\psi_{2}\rangle}|\phi_{2}\rangle\\\
&=\sum_{k=0}^{|B_{1}|+|B_{2}|}\sum_{k_{1}+k_{2}=k}(k_{1}+k_{2})\langle\phi_{1}|\Delta
P_{k_{1}}^{|\psi_{1}\rangle}|\phi_{1}\rangle\langle\phi_{2}|\Delta
P_{k_{2}}^{|\psi_{2}\rangle}|\phi_{2}\rangle\\\
&=\sum_{k_{1}=0}^{|B_{1}|}\sum_{k_{2}=0}^{|B_{2}|}(k_{1}+k_{2})\langle\phi_{1}|\Delta
P_{k_{1}}^{|\psi_{1}\rangle}|\phi_{1}\rangle\langle\phi_{2}|\Delta
P_{k_{2}}^{|\psi_{2}\rangle}|\phi_{2}\rangle\\\
&=\sum_{k_{1}=0}^{|B_{1}|}\sum_{k_{2}=0}^{|B_{2}|}k_{1}\langle\phi_{1}|\Delta
P_{k_{1}}^{|\psi_{1}\rangle}|\phi_{1}\rangle\langle\phi_{2}|\Delta
P_{k_{2}}^{|\psi_{2}\rangle}|\phi_{2}\rangle+\sum_{k_{2}=0}^{|B_{2}|}\sum_{k_{1}=0}^{|B_{1}|}k_{2}\langle\phi_{1}|\Delta
P_{k_{1}}^{|\psi_{1}\rangle}|\phi_{1}\rangle\langle\phi_{2}|\Delta
P_{k_{2}}^{|\psi_{2}\rangle}|\phi_{2}\rangle\\\
&=\sum_{k_{1}=0}^{|B_{1}|}k_{1}\langle\phi_{1}|\Delta
P_{k_{1}}^{|\psi_{1}\rangle}|\phi_{1}\rangle\sum_{k_{2}=0}^{|B_{2}|}\langle\phi_{2}|\Delta
P_{k_{2}}^{|\psi_{2}\rangle}|\phi_{2}\rangle+\sum_{k_{2}=0}^{|B_{2}|}k_{2}\langle\phi_{2}|\Delta
P_{k_{2}}^{|\psi_{2}\rangle}|\phi_{2}\rangle\sum_{k_{1}=0}^{|B_{1}|}\langle\phi_{1}|\Delta
P_{k_{1}}^{|\psi_{1}\rangle}|\phi_{1}\rangle\\\
&=\sum_{k_{1}=0}^{|B_{1}|}k_{1}\langle\phi_{1}|\Delta
P_{k_{1}}^{|\psi_{1}\rangle}|\phi_{1}\rangle+\sum_{k_{2}=0}^{|B_{2}|}k_{2}\langle\phi_{2}|\Delta
P_{k_{2}}^{|\psi_{2}\rangle}|\phi_{2}\rangle\\\
&=\mathcal{S}(|\phi_{1}\rangle,|\psi_{1}\rangle)+\mathcal{S}(|\phi_{2}\rangle,|\psi_{2}\rangle).\end{split}$
(56)

In the second equality, we used Eq. (54). $|B_{i}|$ is the number of qudits in
$B_{i}$. So Eq. (55) is a stronger condition than Eq. (48). For this reason,
we call Eq. (55) the strong additivity. Remind that Eq. (55) is equivalent to
Eq. (42) and Eq. (42) implies Eq. (43) which is equivalent to Eq. (10). Thus,
the strong additivity implies Eq. (10) and the size additivity Eq. (48).

Note that the entanglement polynomial is equal to the trace 333The subscript
of $N_{|\psi\rangle}$ is omitted for the same reason mentioned in footnote 2.

$f(|\psi\rangle)=\textrm{tr}(\sum_{k=0}^{N}x^{k}\Delta P_{k}^{|\psi\rangle}).$
(57)

We define an operator

$F^{|\psi\rangle}\equiv\sum_{k=0}^{N}x^{k}\Delta P_{k}^{|\psi\rangle}.$ (58)

Then Eq. (55) is equivalent to

$F_{|\psi_{1}\rangle|\psi_{2}\rangle}=F_{|\psi_{1}\rangle}F_{|\psi_{2}.\rangle}$
(59)

Eq. (10) can be derived by taking the trace. The size operator is related to
$F$ by

$n_{|\psi\rangle}=\partial_{x}F_{|\psi\rangle}|_{x=1}.$ (60)

Using Eq. (59), we get

$\begin{split}n_{|\psi_{1}\rangle|\psi_{2}\rangle}&=\partial_{x}(F_{|\psi_{1}\rangle|\psi_{2}\rangle})|_{x=1}\\\
&=[(\partial_{x}F_{|\psi_{1}\rangle})F_{|\psi_{2}\rangle}]|_{x=1}+[F_{|\psi_{1}\rangle}(\partial_{x}F_{|\psi_{2}\rangle})]|_{x=1}\\\
&=\partial_{x}F_{|\psi_{1}\rangle}|_{x=1}+\partial_{x}F_{|\psi_{2}\rangle}|_{x=1}\\\
&=n_{|\psi_{1}\rangle}+n_{|\psi_{2}\rangle}.\end{split}$ (61)

In the third equality, we used the fact that $F_{|\psi\rangle}|_{x=1}$ is
equal to the identity. This is a simpler derivation of the size additivity.

##  Appendix C Proof of Theorem 3

Note that

$\begin{split}|V^{k}\mathcal{H}^{g|\psi\rangle}|&=|V^{k}g\mathcal{H}^{|\psi\rangle}|\\\
&=|gg^{-1}V^{k}g\mathcal{H}^{|\psi\rangle}|\\\
&=|g^{-1}V^{k}g\mathcal{H}^{|\psi\rangle}|\\\
&=|V^{k}\mathcal{H}^{|\psi\rangle}|.\end{split}$ (62)

In the first equality, we defined the operator action on the Hilbert space

$gW\equiv\textrm{Span}\\{g|\psi\rangle\,\big{|}\,|\psi\rangle\in W\\}.$ (63)

In the third equality, we used the fact that an invertible operator induces an
automorphism on the vector space. Eq. (6) implies

$|\Delta
W_{k}|=|V^{k}\mathcal{H}^{|\psi\rangle}|-|V^{k-1}\mathcal{H}^{|\psi\rangle}|.$
(64)

Collecting Eq. (7), Eq. (62) and Eq. (64), Theorem 3 is proven.

##  Appendix D Proof of $W_{k}=\text{Im}(\rho_{k})$

In this section, we prove Eq. (31). We first prove two lemmas.

###### Lemma 1

Suppose that $\rho,\sigma\in\text{End}\,(W)$ are positive semi-definite
operators and denote their image by $\textrm{Im}(\rho)$ and
$\textrm{Im}(\sigma)$ respectively. We have

$\text{Im}(\rho+\sigma)=\textrm{Im}(\rho)+\textrm{Im}(\sigma).$ (65)

###### Proof 1

By definition, a positive semi-definite operator $\mathcal{O}$ satisfies

$\langle\psi|\mathcal{O}|\psi\rangle=0\iff|\psi\rangle\in\textrm{Ker}(\mathcal{O}).$
(66)

$\textrm{Ker}(\mathcal{O})$ is the kernel of $\mathcal{O}$. Notice that

$\langle\psi|\rho+\sigma|\psi\rangle\iff\langle\psi|\rho|\psi\rangle=0,\langle\psi|\sigma|\psi\rangle=0.$
(67)

Thus their kernel satisfy

$\textrm{Ker}(\rho+\sigma)=\textrm{Ker}(\rho)\cap\textrm{Ker}(\sigma).$ (68)

Since the kernel of a hermitian operator is the orthogonal complement of its
image, Eq. (65) is proven.

Remind that, given a state $\rho$, the reduced density matrix
$\rho_{\bar{B}}\in\mathcal{A}_{\bar{B}}$ is defined by

$\textrm{tr}(\mathcal{O}\rho_{\bar{B}})=\textrm{tr}(\mathcal{O}\rho),\quad\forall\mathcal{O}\in\mathcal{A}_{\bar{B}}.$
(69)

###### Lemma 2

Suppose $U\in\mathcal{A}_{B}$ is unitary and $dU$ is the normalized Haar
measure. Given a state $\rho$, we have

$\int_{U\in\mathcal{A}_{B}}U\rho U^{\dagger}dU=\rho_{\bar{B}}.$ (70)

###### Proof 2

Given an arbitrary operator $\mathcal{O}\in\mathcal{A}_{\bar{B}}$, we have

$\begin{split}\textrm{tr}(\mathcal{O}\int_{U\in\mathcal{A}_{B}}U\rho
U^{\dagger}dU)&=\int_{U\in\mathcal{A}_{B}}\textrm{tr}(\mathcal{O}U\rho
U^{\dagger})dU\\\ &=\int_{U\in\mathcal{A}_{B}}\textrm{tr}(U\mathcal{O}\rho
U^{\dagger})dU\\\
&=\int_{U\in\mathcal{A}_{B}}\textrm{tr}(U^{\dagger}U\mathcal{O}\rho)dU\\\
&=\textrm{tr}(\mathcal{O}\rho)\int_{U\in\mathcal{A}_{B}}dU\\\
&=\textrm{tr}(\mathcal{O}\rho).\end{split}$ (71)

Since operators in $\mathcal{A}_{B}$ and $\mathcal{A}_{\bar{B}}$ commute, we
have the second equality. In the last equality, we used the normalization

$\int_{U\in\mathcal{A}_{B}}dU=1.$ (72)

Now we only need to prove $\int_{U\in\mathcal{A}_{B}}U\rho
U^{\dagger}dU\in\mathcal{A}_{\bar{B}}$. Suppose $W$ is a unitary operator in
$\mathcal{A}_{B}$ 444This “$W$” should not be confused with the symbol of the
$k$-local subspace.. Denote $WU$ by $U_{W}$, so $U=W^{\dagger}U_{W}$. Then we
have

$\begin{split}W\int_{U\in\mathcal{A}_{B}}U\rho
U^{\dagger}dU&=\int_{U\in\mathcal{A}_{B}}U_{W}\rho U^{\dagger}dU\\\
&=\int_{U\in\mathcal{A}_{B}}U_{W}\rho(W^{\dagger}U_{W})^{\dagger}d(W^{\dagger}U_{W})\\\
&=\int_{U\in\mathcal{A}_{B}}U_{W}\rho U_{W}^{\dagger}Wd(W^{\dagger}U_{W})\\\
&=(\int_{U\in\mathcal{A}_{B}}U_{W}\rho U_{W}^{\dagger}dU_{W})W\\\
&=(\int_{U\in\mathcal{A}_{B}}U\rho U^{\dagger}dU)W.\end{split}$ (73)

Since any operator can be expressed as a linear combination of unitary
operators, we have

$[\mathcal{O},\int_{U\in\mathcal{A}_{B}}U\rho
U^{\dagger}dU]=0,\quad\forall\mathcal{O}\in\mathcal{A}_{B}.$ (74)

Since the Hilbert space is factorized, we conclude that
$\int_{U\in\mathcal{A}_{B}}U\rho U^{\dagger}dU$ is in $\mathcal{A}_{\bar{B}}$.

Combine the above two lemmas, we can prove the following identity for a pure
state $\rho$,

$W_{k}=\textrm{Im}(\rho_{k}).$ (75)

To prove it, we note that

$\begin{split}\textrm{Im}(\rho_{k})&=\textrm{Im}(\sum_{|B|=k}\rho_{\bar{B}})\\\
&=\sum_{|B|=k}\textrm{Im}(\rho_{\bar{B}})\\\
&=\sum_{|B|=k}\textrm{Im}(\int_{U\in\mathcal{A}_{B}}U\rho U^{\dagger}dU)\\\
&=\sum_{|B|=k}\sum_{U\in\mathcal{A}_{B}}\textrm{Im}(U\rho U^{\dagger})\\\
&=\sum_{|B|=k}\textrm{Span}\\{U|\psi\rangle\,\big{|}\,U\in\mathcal{A}_{B}\\}\\\
&=\sum_{|B|=k}\mathcal{A}_{B}\mathcal{H}^{|\psi\rangle}\\\
&=V^{k}\mathcal{H}^{|\psi\rangle}\\\ &=W_{k}.\end{split}$ (76)

In the second, fourth, and fifth equality, we used Lemma 1. In the third
equality, we used Lemma 2. Since any operator can be expanded by unitary
operators, we have the sixth equality. The other equalities hold by
definition. Eq. (75) implies Eq. (31) immediately.

There are different ways to define renormalized states. Remind that
renormalized states defined in Eq. (26) correspond to the uniform probability
distribution. Now we consider general distributions. Denote the probability
distribution of lost part $B$ as $p(B)$. Then for a given state $\rho$, the
average of the expectation value of $\mathcal{O}$ in the noisy laboratory is

$\overline{\langle\mathcal{O}\rangle_{\textrm{noise}}}=\sum_{B}p(B)\textrm{tr}(\mathcal{O}\rho_{\bar{B}}).$
(77)

Define the renormalized state

$\rho_{k}\equiv\sum_{|B|=k}p(B)\rho_{\bar{B}}.$ (78)

If the measure of lost part is fixed to be $k$, then we have

$\overline{\langle\mathcal{O}\rangle_{\textrm{noise}}}=\textrm{tr}(\mathcal{O}\rho_{k}).$
(79)

Using Lemma 1, note that

$\textrm{Im}(\rho_{k})=\sum_{|B|=k}\textrm{Im}[p(B)\rho_{\bar{B}}]=\sum_{|B|=k}\textrm{Im}(\rho_{\bar{B}})$
(80)

for positive definite $p(B)$. Thus, the derivation of Eq. (76) applies to the
case of any positive definite distribution.

## References

  * [1] L. Susskind and Y. Zhao,  _Switchbacks and the Bridge to Nowhere_ (2014),  1408.2823.
  * [2] D. A. Roberts, D. Stanford and L. Susskind,  _Localized shocks_ ,  JHEP 03, 051 (2015),  10.1007/JHEP03(2015)051,  1409.8180.
  * [3] D. A. Roberts, D. Stanford and A. Streicher,  _Operator growth in the SYK model_ ,  JHEP 06, 122 (2018),  10.1007/JHEP06(2018)122,  1802.02633.
  * [4] X.-L. Qi and A. Streicher,  _Quantum Epidemiology: Operator Growth, Thermal Effects, and SYK_ ,  JHEP 08, 012 (2019),  10.1007/JHEP08(2019)012,  1810.11958.
  * [5] L. Susskind,  _Why do Things Fall?_ (2018),  1802.01198.
  * [6] A. R. Brown, H. Gharibyan, A. Streicher, L. Susskind, L. Thorlacius and Y. Zhao,  _Falling Toward Charged Black Holes_ ,  Phys. Rev. D 98(12), 126016 (2018),  10.1103/PhysRevD.98.126016,  1804.04156.
  * [7] L. Susskind,  _Complexity and Newton’s Laws_ ,  Front. in Phys. 8, 262 (2020),  10.3389/fphy.2020.00262,  1904.12819.
  * [8] D. Gottesman,  _A Class of quantum error correcting codes saturating the quantum Hamming bound_ ,  Phys. Rev. A 54, 1862 (1996),  10.1103/PhysRevA.54.1862,  quant-ph/9604038.
  * [9] D. Gottesman,  _Stabilizer codes and quantum error correction_ (1997),  quant-ph/9705052.
  * [10] A. Almheiri, X. Dong and D. Harlow,  _Bulk Locality and Quantum Error Correction in AdS/CFT_ ,  JHEP 04, 163 (2015),  10.1007/JHEP04(2015)163,  1411.7041.
  * [11] Q.-F. Wu,  _Sectional curvatures distribution of complexity geometry_ (2021),  2108.11621.
  * [12] A. Mousatov,  _Operator Size for Holographic Field Theories_ (2019),  1911.05089.
  * [13] W. Dur, G. Vidal and J. I. Cirac,  _Three qubits can be entangled in two inequivalent ways_ ,  Phys. Rev. A 62, 062314 (2000),  10.1103/PhysRevA.62.062314,  quant-ph/0005115.
  * [14] F. Verstraete, J. Dehaene, B. De Moor and H. Verschelde,  _Four qubits can be entangled in nine different ways_ ,  Physical Review A 65(5), 052112 (2002).
  * [15] T. Bastin, S. Krins, P. Mathonet, M. Godefroid, L. Lamata and E. Solano,  _Operational families of entanglement classes for symmetric n-qubit states_ ,  Physical review letters 103(7), 070503 (2009).
  * [16] P. Ribeiro and R. Mosseri,  _Entanglement in the symmetric sector of n qubits_ ,  Physical review letters 106(18), 180502 (2011).
  * [17] X. Li and D. Li,  _Classification of general n-qubit states under stochastic local operations and classical communication in terms of the rank of coefficient matrix_ ,  Physical review letters 108(18), 180502 (2012).
  * [18] G. Gour and N. R. Wallach,  _Classification of multipartite entanglement of all finite dimensionality_ ,  Physical review letters 111(6), 060502 (2013).
  * [19] M. Gharahi, S. Mancini and G. Ottaviani,  _Fine-Structure Classification of Multiqubit Entanglement by Algebraic Geometry_ ,  Phys. Rev. Res. 2(4), 043003 (2020),  10.1103/PhysRevResearch.2.043003,  1910.09665.
  * [20] C. Harney, S. Pirandola, A. Ferraro and M. Paternostro,  _Entanglement classification via neural network quantum states_ ,  New Journal of Physics 22(4), 045001 (2020).


∎

11institutetext: F. Luque 22institutetext: Universidad Nacional de Córdoba &
CONICET
22email<EMAIL_ADDRESS>
# Atalaya at TASS 2019: Data Augmentation and Robust Embeddings for Sentiment
Analysis

Franco M. Luque

(Received: date / Accepted: date)

###### Abstract

In this article we describe our participation in TASS 2019, a shared task
aimed at the detection of sentiment polarity of Spanish tweets. We combined
different representations such as bag-of-words, bag-of-characters, and tweet
embeddings. In particular, we trained robust subword-aware word embeddings and
computed tweet representations using a weighted-averaging strategy. We also
used two data augmentation techniques to deal with data scarcity: two-way
translation augmentation, and instance crossover augmentation, a novel
technique that generates new instances by combining halves of tweets. In
experiments, we trained linear classifiers and ensemble models, obtaining
highly competitive results despite the simplicity of our approaches.

###### Keywords:

Sentiment Analysis Polarity Classification Embeddings Data Augmentation Linear
Models

##  1 Introduction

TASS is a shared task organized every year, since 2012, with challenges
related to Sentiment Analysis in Spanish. In TASS 2019 overview_tass2019 , the
proposed task is to label tweets according to the general sentiment polarity
they express, classifying them into four classes: P (positive), N (negative),
NEU (neutral, undecided) and NONE (no sentiment).

Five datasets are offered for the task, each one from a different Spanish
speaking country: CR (Costa Rica), ES (Spain), MX (México), PE (Perú) and UY
(Uruguay). Each corpus is divided into train, development and test sections.
No other supervised datasets can be used, but external linguistic resources
such as embeddings and lexicons are allowed.

The challenge is divided into two subtasks. In monolingual subtask 1, systems
must be trained and tested on the same dataset. In cross-lingual subtask 2,
systems must be trained using datasets from countries others than the one used
for testing.

In this article, we describe our participation in TASS 2019 as team Atalaya.
We based our systems on our previous work atalaya_tass2018  for TASS 2018
overview_tass2018 . For this edition, we focused our work on data augmentation
and robust representations.

To represent tweets, we used a combined approach of bag-of-words, bag-of-
characters and tweet embeddings. Tweet embeddings were computed from word
embeddings using a weighted averaging scheme. For word embeddings, we used
fastText subword-aware vectors bojanowski16  specifically trained for
sentiment analysis over Spanish tweets.

Our fastText embeddings are robust to noise since they can compute embeddings
for unseen words by using subword embeddings. Moreover, we trained them using
a database of 90M tweets from various Spanish-speaking countries, giving wide
domain-specific vocabulary coverage. We achieved additional robustness by
doing preprocessing using several text normalization and noise reduction
techniques.

To cope with training data scarcity, we experimented with data augmentation
techniques. As in our previous work, we did augmentation using machine
translation to and from several other languages.

We also tried a novel augmentation technique we called instance crossover,
loosely inspired by the crossover operation from genetic algorithms. This
technique combines halves of tweets to generate new instances. Despite its
simplicity, this idea showed to be useful in our experiments.

For the classifying models, we used logistic regressions and also bagging
ensembles of logistic regressions.

The rest of the paper is as follows. The next section presents the components
of our systems and the ideas we used to build them. Section 3 presents the
experiments and results for both subtasks. Section 4 concludes the work with
some observations about our experience.

##  2 Techniques and Resources

The components and general architecture of our systems is shown in Fig. 1. In
this section, we describe the techniques and resources we used to build them.

Training Data Translation Augmented Data Crossover Augmented Data Preprocess
BoC BoW Embedding Classifier Figure 1:  General architecture of our systems,
including the input used in training time. Dotted lines denote precomputed
processes.

###  2.1 Preprocessing

Preprocessing is important to reduce noise from tweets. We follow our previous
work, applying two levels of preprocessing. Basic tweet preprocessing includes
tokenization, replacement of handles, URLs, and e-mails, and shortening of
repeated letters. Further preprocessing is done, aimed at semantic tasks. It
includes removal of punctuation, stopword and numbers, lowercasing,
lemmatization, and negation handling.

For negation handling, we followed a simple approach das01 ; pang02 : We find
negation words and add the prefix NOT_ to the following tokens. Up to three
tokens are negated, or less if a non-word token is found.

No treatment was performed to hashtags, emojis, interjections and
onomatopoeias. Moreover, no spelling correction nor any other additional
normalization was applied.

###  2.2 Bags of Words and Characters

A simple way to represent textual data as feature vectors is to use bag-of-
words (BoWs). A bag-of-words represents a tweet as a vector with the counts of
words occurring in it. Resulting vectors are high-dimensional and sparse. The
BoW representation can be extended to count also word n-grams. In this work,
we used BoWs, together with count binarization and TF-IDF re-weighting, both
useful for semantic tasks such as sentiment analysis.

For more robustness, we also used a bag-of-characters (BoC) representation.
BoCs have exactly the same properties and variants than BoWs but are applied
to characters instead of word tokens. Character usage in tweets holds useful
information for sentiment analysis. In our work, the BoC representation is
computed over the original raw text of tweets, with no preprocessing at all.

###  2.3 Word Embeddings

A more interesting way to represent text is using embeddings. Word embeddings
are low-dimensional dense vector representations of words. These
representations are learned in an unsupervised fashion using large quantities
of plain text, providing high vocabulary coverage.

For our systems, we used fastText embeddings bojanowski16 , that introduces
additional robustness by learning also subword-level embeddings and using them
to compute vectors for unseen words. With subword-aware embeddings, the need
for normalization of highly noisy text in preprocessing is greatly alleviated.

We did not use a pretrained fastText model but trained our own using a big
preprocessed dataset of $\sim 90$ million tweets from various Spanish-speaking
countries. This dataset is mostly composed of tweets we collected for previous
work, and also includes the tweets from all sections of all TASS 2019
datasets.

###  2.4 Tweet Embeddings

To use word embeddings in sentiment analysis, the embeddings of the individual
tokens must be aggregated in some way to obtain a complete tweet
representation.

A simple approach is to do averaging to obtain a single vector. A bit more
interesting is to add weights to the averaging scheme. This way, some words
may be considered more relevant than others for the classification task.

In this work, we used Smooth Inverse Frequency (SIF), a simple weighted
averaging scheme from arora17  inspired by TF-IDF re-weighting. In SIF, words
$w$ are weighted with $\frac{a}{a+p(w)}$, where $p(w)$ is the word unigram
probability, and $a>0$ is a smoothing hyperparameter. Big values of $a$ mean
more smoothing towards plain averaging. We model the unigram probability using
unigram counts from our preprocessed $\sim 90$ million tweets dataset.

In arora17  a final transformation is applied to tweet embeddings by
subtracting from them a common component shared by all the vectors.
Preliminary experiments with this idea, however, showed it to be harmful to
our systems, so we did not use it in our final experiments.

An important limitation of this tweet embedding scheme is that word order is
completely ignored. Only preprocessing may allow the influence of ordering in
the result. In particular, the negation handling trick from section 2.1 is a
useful, although naive, way to let words be affected by previous negations.

###  2.5 Data Augmentation with Two-Way Translation

One of the main successful approaches from our previous work on TASS was the
use of data augmentation techniques. Data augmentation helps to cope with
training data scarcity. Augmentation aims at the introduction of data
variability using label-preserving transformations on real data. When
correctly used, it contributes to data robustness and acts as a regularizer
for the models.

Our approach for TASS 2018 (also as team Atalaya) was to use two-way
translation augmentation. In two-way translation, an external machine
translation service is used to translate tweets to other “pivot” languages and
then back to Spanish. This augmentation technique helps to introduce lexical
and syntactical variations to tweets, most times preserving their meaning.

In atalaya_tass2018  we used two-way translation to augment the training data
using four pivot languages (English, French, Portuguese and Arabic). This
augmentation was found to be useful for the ES and CR datasets, but not for
PE.

In this work, we explored two-way translation further, applying it to all the
datasets using 20 different pivot languages. To get translations, we used
Google’s Cloud Translation API service.

Pivot languages were selected by hand from the list of available languages
that the API can translate from/to Spanish. The selection was done trying to
pick representative languages from different language families.

###  2.6 Data Augmentation with Instance Crossover

We also tried a new augmentation idea that aims at the generation of new data
by combining pairs of instances with the same label. We call it the instance
crossover augmentation technique, inspired by the chromosome crossover
operation from genetic algorithms.

Our approach is simply to split tokenized tweets into two halves, and then
randomly sample and combine first halves with second halves. Resulting
instances will probably be ungrammatical and semantically unsound, but our
hypothesis is that what is left of semantics, for instance at the lexical
level, will preserve sentiment polarity most of the times.111 Grammaticality
and semantic soundness are already rare in the original tweets, so it is not
something we should worry about very much.

Fig. 2 shows an example of instance crossover using two tweets with positive
sentiment. In this example, crossover is successful in the sense that the
resulting instances can be clearly judged as having a positive sentiment. In
other cases, crossover may fail to preserve polarity, for instance, because of
an unfortunate combination involving a negation. Resulting instances may even
be completely nonsensical, introducing noise to the data.

For this work, we chose to directly validate in experiments this augmentation
idea. In our experiments, we applied augmentation over the training tweets
after basic preprocessing and before semantic preprocessing (as defined in
section 2.1). We tried different levels of augmentation, multiplying the size
of original training datasets by factors of 4, 8, 12, 16 and 20. We preserved
the original distribution over labels and therefore the class imbalance.

Instance crossover is a very rough and naive augmentation technique. However,
it may be useful to introduce more data variability than two-way translation.
With translation, new data points may fall very close to the original ones,
while crossover introduces new points in the “spaces” between the original
ones. Moreover, this is done in a representation agnostic fashion. It can be
used with bag-of-words, embeddings, or even neural based representations.

Another clear advantage of instance crossover is that it does not rely on any
external resource or system. Unlike this, translation requires an external
service, at a cost, and other techniques such as synonym replacement require
thesauruses or word similarity databases.

ORIGINALAUGMENTED@USER fue genial debemosorganizar más cosas asíptsin
necesidad de quenadie abandone el país@USER me alegro mucho ! !es importante
darnos cuentaptdel gran valor que podemosaportar y encontrar nuestra
misión@USER fue genial debemosorganizar más cosas asíptdel gran valor que
podemosaportar y encontrar nuestra misión@USER me alegro mucho ! !es
importante darnos cuentaptsin necesidad de quenadie abandone el país Figure 2:
Instance crossover augmentation example using two tweets with positive (P)
sentiment polarity. The original tweets are on the left. The first half of one
tweet is combined with the second half of the other, resulting in the new
instances on the right. The dotted lines show the division in halves.

##  3 Experiments

In this section, we describe our experiments. We implemented all our systems
using scikit-learn scikit-learn . In the preprocessing stage, we used an NLTK-
based tokenizer bird2004nltk  and TreeTagger for lemmatization schmid95 .

###  3.1 System Development

For simplicity, most of our work was centered on subtask 1 and on the ES
dataset, looking for model configurations and hyperparameter values that gave
the best results over the development section of the ES dataset. The
optimization process was done using a mixed approach of grid search and by-
hand tuning.

We targeted the maximization of both macro-F1 and accuracy scores. The
macro-F1 score is the main metric of TASS 2019, but it is very unstable and
sensible to small changes in predictions for minority classes. On the other
hand, accuracy is more stable and reliable for the development process.

As a starting point, we used our optimal model and configuration from TASS
2018 atalaya_tass2018 . This model is a logistic regression over a combination
of bag-of-words (BoW), bag-of-characters (BoC) and tweet embeddings as
follows:

  * •

Augmentation: Two-way translation with English, French, Portuguese and Arabic
(EN+FR+PT+AR) as pivot languages.

  * •

BoW: All word n-grams for $n\leq 5$.

  * •

BoC: All character n-grams for $n\leq 6$.

  * •

Tweet embeddings: 50 dimension fastText vectors. Weighted averaging with
$a=0.1$.

  * •

Logistic regression: liblinear solver with primal formulation, L2
regularization with inverse strength $C=1.0$, and class-balanced reweighting.

Table 1 shows a detailed evaluation of this baseline model.

The first idea we explored was augmentation using two-way translation with the
new 20 pivot languages. We tried adding all new data, but also adding some
subsets of it, by grouping pivot languages in packs of four datasets. However,
we could not find any improvement from the original EN+FR+PT+AR augmentation,
sometimes finding important drops in model quality.

Next, we explored augmentation using instance crossover. We tried 4x, 8x, 12x,
16x and 20x factor augmentations from the original ES training corpus, with
and without additional translation-based augmentation. In every case results
were improved w.r.t. not using crossover augmentation. The best result was
found for 8x augmentation.

Last, we tuned the hyperparameters of the logistic regression. The best
configuration found was a liblinear solver with primal formulation, L2
regularization with inverse strength $C=0.2$, with no class-balanced
reweighting.

We also tried an ensemble of logistic regressions by using bagging. Bagging
was found to be useful for the ES dataset. The best configuration found was
using a bag of 40 logistic regressions.

Table 2 shows a detailed evaluation for our best model for ES found following
the development process.

###  3.2 Subtask 1: Monolingual Experiments

To build a submission for subtask 1, we first ran the final test on the ES
dataset using the best model described in the previous section.

To build submissions for the other datasets, we followed a similar development
approach, but with most hyperparameters fixed with the optimal values for ES.
We focused the optimization process in the usage of translation and crossover
augmentations, in the logistic regression hyperparameters and in the usage of
bagging. Tuning was done mostly by hand and sometimes using grid-search. Table
3 shows the optimal configurations found for each dataset.

The final results for the complete submission for subtask 1 are shown in Table
4.

| Prec. | Rec. | F1
---|---|---|---
P | 60.64 | 67.86 | 64.04
N | 67.82 | 80.83 | 73.76
NEU | 21.05 | 4.82 | 7.84
NONE | 38.60 | 34.38 | 36.36
macro avg | 47.03 | 46.97 | 47.00
Accuracy: 61.10 |  |

| P | N | NEU | NONE
---|---|---|---|---
P | 114 | 36 | 5 | 13
N | 28 | 215 | 8 | 15
NEU | 29 | 43 | 4 | 7
NONE | 17 | 23 | 2 | 22

Table 1: Subtask 1: Detailed results for our baseline system on the ES
development set. Left: Classification report. Right: Confusion matrix.

| Prec. | Rec. | F1
---|---|---|---
N | 66.38 | 87.59 | 75.53
NEU | 50.00 | 2.41 | 4.60
NONE | 60.71 | 26.56 | 36.96
P | 61.62 | 72.62 | 66.67
macro avg | 59.68 | 47.30 | 52.77
Accuracy: 64.37 |  |

| P | N | NEU | NONE
---|---|---|---|---
P | 122 | 42 | 1 | 3
N | 27 | 233 | 1 | 5
NEU | 29 | 49 | 2 | 3
NONE | 20 | 27 | 0 | 17

Table 2: Subtask 1: Detailed results for our best system on the ES development set. Left: Classification report. Right: Confusion matrix. | augmentation | logistic regression |
---|---|---|---
| translation | crossover | C | class-weight | bagging
ES | EN+FR+PT+AR | 8x | 0.2 | no | 40
PE | EN+FR+PT+AR | 4x | 0.22 | balanced | no
CR | no | 8x | 1.15 | balanced | no
UY | no | 8x | 0.6 | no | no
MX | EN+FR+PT+AR | 16x | 0.125 | balanced | no
Table 3: Subtask 1: Best system configurations found for each dataset. Optimization was done using the development sections. Hyperparameters and their values are described in section 3.1.  | dev | test |
---|---|---|---
| Acc. | M-F1 | Acc. | M-F1 | Rank
ES | 64.37 | 52.77 | 60.67 | 48.42 | 2
PE | 51.41 | 47.90 | 45.36 | 45.38 | 1
CR | 61.28 | 53.36 | 57.20 | 46.91 | 3
UY | 61.93 | 54.81 | 60.64 | 49.86 | 3
MX | 67.65 | 53.88 | 68.87 | 48.46 | 4
Table 4:  Subtask 1: Final results for each dataset, on development and test
sections. Rank is the official final rank in the competition.

###  3.3 Subtask 2: Crosslingual Experiments

To build submissions for subtask 2 we did a minimal set of experiments. For
each language, we started from the optimal model configuration found for
subtask 1 and then trained it using the union of the training datasets of
every other language. We then proceeded to optimize the main hyperparameters
of the logistic regression, mostly doing by-hand tuning.

We did some preliminary experiments with data augmentation and bagging for the
ES dataset. However, results were not improved, so we didn’t do further
experimentation with the other datasets.

The final results for the complete submission for subtask 2 are shown in Table
5. Results are surprisingly good, considering that we did limited
experimentation because of lack of time.

| dev | test |
---|---|---|---
| Acc. | M-F1 | Acc. | M-F1 | Rank
ES | 63.68 | 53.57 | 61.55 | 45.42 | 3
PE | 41.97 | 43.71 | 54.64 | 47.42 | 1
CR | 57.69 | 48.77 | 57.12 | 47.41 | 2
UY | 60.91 | 53.15 | 61.20 | 51.35 | 1
MX | 64.90 | 50.18 | 68.13 | 47.25 | 1
Table 5: Subtask 2: Final results for each dataset, on development and test
sections. Rank is the official final rank in the competition.

###  3.4 Ablation Tests

As a complementary post-competition experiment, we performed ablation tests
for each of the components of our systems, to assess the relevance of each of
the techniques used in this work.

The ablation tests were done using the best system for subtask 1 on the ES
dataset. The results are displayed in Table 6.

It can be seen that all the techniques have a positive impact. Among
representations, tweet embedding is the most important representation, way
above BoW and BoC representations. Also, it is interesting to observe that
crossover augmentation has an impact on the F1 but not on the accuracy,
indicating that it is helping mostly on the minority classes NEU and NONE.

|  | Acc. | M-F1
---|---|---|---
full system |  | 64.37 | 52.77
augmentation: | no translation | 62.99 | 48.05
no crossover | 64.37 | 47.57
representation: | no BoW | 62.99 | 49.89
no BoC | 62.65 | 50.80
no BoW+BoC | 62.13 | 48.26
no embeddings | 58.52 | 41.83
classifier: | no bagging | 64.03 | 51.94
Table 6: Ablation tests for several techniques used in our final system.
Results are for subtask 1 on the ES development set.

##  4 Conclusions

Robust representations and data augmentation play a strong role in sentiment
analysis with small-sized training datasets. As in our previous experience
with TASS 2018, we are still able to obtain top ranking results without having
to resort to complex models such as deep neural networks.

We observe that, for this edition of TASS, most of our work was on the
application of general ML techniques, and not on particular task/domain
specific engineering. In particular, we successfully tried instance crossover
augmentation, a novel technique that, despite its simplicity, showed a
positive impact on results. This idea can be useful to augment small datasets
for other short text classification tasks without the need for external
resources.

###### Acknowledgements.

This work was partially supported by a research grant from SeCyT, Universidad
Nacional de Córdoba.

## References

  * (1) Arora, S., Liang, Y., Ma, T.: A simple but tough-to-beat baseline for sentence embeddings.  In: International Conference on Learning Representations (2017)
  * (2) Bird, S., Loper, E.: Nltk: the natural language toolkit.  In: Proceedings of the ACL 2004 on Interactive poster and demonstration sessions, p. 31. Association for Computational Linguistics (2004)
  * (3) Bojanowski, P., Grave, E., Joulin, A., Mikolov, T.: Enriching word vectors with subword information.  arXiv preprint arXiv:1607.04606 (2016)
  * (4) Das, S.R., Chen, M.Y., Agarwal, T.V., Brooks, C., shee Chan, Y., Gibson, D., Leinweber, D., Martinez-jerez, A., Raghubir, P., Rajagopalan, S., Ranade, A., Rubinstein, M., Tufano, P.: Yahoo! for amazon: Sentiment extraction from small talk on the web.  In: 8th Asia Pacific Finance Association Annual Conference (2001)
  * (5) Díaz-Galiano, M.C., et al.: Overview of TASS 2019.  CEUR-WS, Bilbao, Spain (2019)
  * (6) Luque, F.M., Pérez, J.M.: Atalaya at TASS 2018: Sentiment analysis with tweet embeddings and data augmentation.  In: E. Martínez-Cámara, Y. Almeida Cruz, M.C. Díaz-Galiano, S. Estévez Velarde, M.A. García-Cumbreras, M. García-Vega, Y. Gutiérrez Vázquez, A. Montejo Ráez, A. Montoyo Guijarro, R. Muñoz Guillena, A. Piad Morffis, J. Villena-Román (eds.) Proceedings of TASS 2018: Workshop on Semantic Analysis at SEPLN (TASS 2018), _CEUR Workshop Proceedings_ , vol. 2172, pp. 29–35. CEUR-WS, Sevilla, Spain (2018)
  * (7) Martínez-Cámara, E., Almeida Cruz, Y., Díaz-Galiano, M.C., Estévez Velarde, S., García-Cumbreras, M.A., García-Vega, M., Gutiérrez Vázquez, Y., Montejo Ráez, A., Montoyo Guijarro, A., Muñoz Guillena, R., Piad Morffis, A., Villena-Román, J.: Overview of TASS 2018: Opinions, health and emotions.  In: E. Martínez-Cámara, Y. Almeida Cruz, M.C. Díaz-Galiano, S. Estévez Velarde, M.A. García-Cumbreras, M. García-Vega, Y. Gutiérrez Vázquez, A. Montejo Ráez, A. Montoyo Guijarro, R. Muñoz Guillena, A. Piad Morffis, J. Villena-Román (eds.) Proceedings of TASS 2018: Workshop on Semantic Analysis at SEPLN (TASS 2018), _CEUR Workshop Proceedings_ , vol. 2172. CEUR-WS, Sevilla, Spain (2018)
  * (8) Pang, B., Lee, L., Vaithyanathan, S.: Thumbs up? sentiment classification using machine learning techniques.  In: Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing, pp. 79–86. Association for Computational Linguistics (2002)
  * (9) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research 12, 2825–2830 (2011)
  * (10) Schmid, H.: Improvements in part-of-speech tagging with an application to german.  In: Proceedings of the ACL SIGDAT-Workshop, pp. 47–50 (1995)