# A new graph decomposition method
for bipartite graphs

Béla Csaba

###### Abstract

Given a sufficiently large and sufficiently dense bipartite graph $G=(A,B;E),$
we present a novel method for decomposing the majority of the edges of $G$
into quasirandom graphs so that the vertex sets of these quasirandom graphs
partition the majority of $A.$ The method works for relatively small or sparse
graphs, and can be used to substitute the Regularity lemma of Szemerédi in
some graph embedding problems.

Extended Abstract

##  1 Introduction

All graphs considered in this paper are simple. The Szemerédi Regularity lemma
[10] is one of the most powerful tools of graph111There are also hypergraph
versions that play crucial role in extremal hypergraph theory and
combinatorial number theory, see eg., [6] or [9]. theory. It is also used in
many areas outside graph theory, for example in number theory and algorithms.

######  Theorem 1.1 (Szemerédi).

For every $\varepsilon>0$ there exists a $n_{0}=n_{0}(\varepsilon)>0$ such
that if $G$ is a simple graph on $n\geq n_{0}$ vertices $G$ admits an
$\varepsilon$-regular equipartition of its vertex set into at most
$k=k(\varepsilon)$ parts.

We will give a short introduction to the necessary notions in the next
section. Here we only mention that $\varepsilon$-regularity is a notion of
quasirandomness, and equipartition means, roughly, the partition of the vast
majority of the vertex set of $G$ into equal sized subsets so that all, but an
$\varepsilon$ proportion of the pairs of subsets span an $\varepsilon$-regular
bipartite subgraph of $G.$

The dependence of $n_{0}$ on $\varepsilon$ in Theorem 1.1 is determined by a
tower function $T$ evaluated at $1/\varepsilon^{5},$ where $T$ can be defined
inductively as follows: $T(1)=2,$ and for $i>1$ we have $T(i)=2^{T(i-1)}.$
Hence, the value of $n_{0}$ makes the Regularity lemma essentially
impractical. It is also well-known that we cannot hope for a much better
bound, since as was proven by Gowers [4] and more recently by Conlon and Fox
[2], there are graphs for which the number of clusters in the Regularity lemma
is necessarily a tower function of $1/\varepsilon.$ Note also, that the lemma
is only meaningful for so called dense graphs, that is, graphs that contain a
constant proportion of the possible edges.

In this paper we present a new graph decomposition method for bipartite
graphs, which can be applied for graphs of practical size and for graphs
having vanishing density. While the Regularity lemma is useful in many areas
of mathematics and computer science, our contribution may not be so widely
applicable. Still, it can be used for finding certain subgraphs in a host
graph. As an illustration we will give the details of a tree embedding
algorithm that uses this graph decomposition method. Let us mention that
Gowers in [5] presented a decomposition for bipartite graphs that is somewhat
similar to the one discussed here, and used it for a problem in number theory.
That decomposition has different parameters and a much longer and harder
proof.

Due to the importance of the Regularity lemma several researchers found
weakened versions ([1], [3], etc.) in which the dependence of $\varepsilon$
and $n_{0}$ is not determined by a tower function. These are important
developments with several applications, still, none of them seems to be so
widely applicable as the original one. The so called absorption method [11] is
also a choice for avoiding the use of the Regularity lemma in some embedding
problems.

The outline of the paper is as follows. First, we provide the necessary
notions for the decomposition and then describe the decomposition method in
the next section. In the subsequent section we provide an application, namely,
we show that we can find a large subtree in a graph on $n$ vertices having
$\Omega(n^{2}\log\log n/{\log n})$ edges.

##  2 Definitions, main result

Given a graph $G$ with vertex set $V$ and edge set $E$ we let $deg_{G}(v)$
denote the degree of $v\in V.$ If it is clear from the context, the
subscription may be omitted. The neighborhood of $v$ is denoted by $N(v),$ so
$deg(v)=|N(v)|.$ The minimum degree of $G$ is denoted by $\delta(G).$ If
$S\subset V,$ then $deg(v;S)=|N(v)\cap S|.$ The set of edges between two
disjoint sets $S,T\subset V$ is denoted by $E(S,T),$ and we let
$e(S,T)=|E(S,T)|.$ We also let $e(G)=|E(G)|.$

Let $G=G(A,B;E)$ be a bipartite graph. The density $d_{G}(A,B)$ or, if $G$ is
clear from the context, $d(A,B),$ is defined as follows:

$d(A,B)=\frac{e(G)}{|A|\cdot|B|}.$

Given a number $\varepsilon\in(0,1)$ we say that $G$ is an
$\varepsilon$-regular pair if the following holds for every $A^{\prime}\subset
A,$ $|A^{\prime}|\geq\varepsilon|A|$ and $B^{\prime}\subset B,$
$|B^{\prime}|\geq\varepsilon|B|$:

$|d_{G}(A,B)-d_{G}(A^{\prime},B^{\prime})|\leq\varepsilon.$

The $\varepsilon$-regular equipartition of a graph $G$ on $n$ vertices means
that there exists a number $k=k(\varepsilon)$ and $V(G)=V_{0}\cup
V_{1}\cup\ldots\cup V_{k}$ such that $V_{i}\cap V_{j}=\emptyset$ for $i\neq
j,$ $|V_{0}|\leq\varepsilon n,$ $||V_{i}|-|V_{j}||\leq 1$ for every $1\leq
i,j\leq k$ and all but at most $\varepsilon k^{2}$ pairs $V_{i}V_{j}$ are
$\varepsilon$-regular for $1\leq i,j.$ The $V_{i}$ sets are called clusters,
and $V_{0}$ is the exceptional cluster.

Roughly speaking, the Regularity lemma asserts that every graph can be well
approximated by a collection of quasirandom graphs that are defined between
the non-exceptional clusters. Unfortunately, the number of non-exceptional
clusters is a tower function of $1/\varepsilon.$

While our goal is to provide an alternative for the Regularity lemma, we will
also make use of the regularity concept. Our definition is slightly more
permissive than the usual one above, this enables us to give a very short
proof of our decomposition, and it is still powerful enough to be applicable
in several embedding problems. It is called lower regularity, and is used by
other researchers as well.

######  Definition 2.1.

Given a bipartite graph $G=G(A,B)$ we say that $G$ is a lower
$(\varepsilon,\eta,\gamma)$-regular pair, if for any $A^{\prime}\subset
A,B^{\prime}\subset B$ with $|A^{\prime}|\geq\varepsilon|A|,$
$|B^{\prime}|\geq\eta|B|$ we have
$e(A^{\prime},B^{\prime})\geq\gamma\cdot|A^{\prime}|\cdot|B^{\prime}|.$

Note that in the usual definition of an $\varepsilon$-regular pair one has
$\varepsilon=\eta,$ and the edge density between two sufficiently large
subsets is between $d_{G}-\varepsilon$ and $d_{G}+\varepsilon.$ We want to
have flexibility in this notion, and allow sub-pairs with relatively low
density, and the $\varepsilon\neq\eta$ case, too.

We are ready to state our main result, the precise formulation is as follows.

######  Theorem 2.2.

Let $G=G(A,B)$ be a bipartite graph with vertex classes $A$ and $B$ such that
$|A|=n$ and $|B|=m,$ and every vertex of $A$ has at least $\delta m$ neighbors
in $B.$ Let $0<\varepsilon,\eta,\gamma<1$ be numbers so that $\eta\leq 1/6$
and $\gamma\leq\min\\{\eta/4,\delta/20\\}.$ Then there exists a partition
$A=A_{0}\cup A_{1}\cup\ldots\cup A_{k},$ and $k$ not necessarily disjoint
subsets of $B,$ $B_{1},\ldots,B_{k}$ such that
$|A_{i}|\geq\varepsilon\cdot\exp\left(-2\log(\frac{1}{\varepsilon})\log(\frac{2}{\delta})/\eta\right)n$
for $i\geq 1,$ $|A_{0}|\leq\epsilon n,$ the subgraphs $G[A_{i},B_{i}]$ for
$1\leq i\leq k$ are all lower $(\varepsilon,\eta,\gamma)$-regular, and

$\sum_{i=1}^{k}e(G[A_{i},B_{i}])\geq e(G)-(\varepsilon+2\gamma)nm.$

Moreover,

$k\leq\frac{2}{\varepsilon\delta}e^{2\log(\frac{1}{\varepsilon})\log(\frac{2}{\delta})/\eta}.$

##  3 Proof of Theorem 2.2

Let us remark that we will not be concerned with floor signs, divisibility,
and so on in the proof. This makes the notation simpler, easier to follow.

As we have seen edge density plays an important role in regularity. We need a
simple fact which is called convexity of density (see eg. in [7]), the proof
is left for the reader.

######  Claim 3.1.

Let $F=F(A,B)$ be a bipartite graph, and let $1\leq k\leq|A|$ and $1\leq
m\leq|B|.$ Then

$d_{F}(A,B)=\frac{1}{\binom{|A|}{k}\binom{|B|}{m}}\sum_{X\in\binom{A}{k},Y\in\binom{B}{m}}d(X,Y).$

In order to prove Theorem 2.2 we need a lemma that is the basic building block
of our decomposition method.

######  Lemma 3.2.

Let $F=F(A,B)$ be a bipartite graph with vertex classes $A$ and $B$ such that
$|A|=a$ and $|B|=b,$ and every vertex of $A$ has at least $\delta b$ neighbors
in $B.$ Let $0<\varepsilon,\eta,\gamma<1$ be numbers so that $\eta\leq 1/6$
and $\gamma\leq\min\\{\eta/4,\delta/20\\}.$ Then $F$ contains a lower
$(\varepsilon,\eta,\gamma)$-regular pair $F[X,Y]$ such that
$|X|\geq\exp\left(-2\log(\frac{2}{\varepsilon})\log(\frac{2}{\delta})/\eta\right)a$
and $|Y|\geq(\delta(1-\eta)-2\gamma)b.$

Proof: We prove the lemma by finding two sequences of sets
$X_{0}=A,X_{1},\ldots,X_{l}$ and $Y_{0}=B,Y_{1},$ …, $Y_{l}$ such that for
every $1\leq i\leq l$ we have that $X_{i}\subset X_{i-1}$ and $Y_{i}\subset
Y_{i-1}$ and

$\varepsilon|X_{i-1}|/2\leq|X_{i}|\leq\varepsilon|X_{i-1}|$

and

$|Y_{i}|=(1-\eta)|Y_{i-1}|,$

moreover, the last pair $F[X_{l},Y_{l}]$ is lower
$(\varepsilon,\eta,\gamma)$-regular. Hence, we may choose $X=X_{l}$ and
$Y=Y_{l}.$

We find the set sequences $\\{X_{i}\\}_{i\geq 1}$ and $\\{Y_{i}\\}_{i\geq 1}$
by the help of an iterative procedure. This procedure stops in the $l$th step,
if $F[X_{l},Y_{l}]$ is lower $(\varepsilon,\eta,\gamma)$-regular. We have
another stopping rule: if $|Y_{l}|\leq(\delta(1+\eta/2)-2\gamma)b$ for some
$l,$ we stop. Later we will see that in this case we have found what is
desired, $F[X_{l},Y_{l}]$ must be a lower $(\varepsilon,\eta,\gamma)$-regular
pair.

In the beginning we check if $F[X_{0},Y_{0}]$ is a lower
$(\varepsilon,\eta,\gamma)$-regular pair. If it is, we stop. If not then
$X_{0}$ has a subset $X^{\prime}_{1}$ precisely of size $\varepsilon|X_{0}|$
and $Y_{0}$ has a subset $Y^{\prime}_{1}$ precisely of size $\eta|Y_{0}|$ such
that
$e(F[X^{\prime}_{1},Y^{\prime}_{1}])<\gamma|X^{\prime}_{1}|\cdot|Y^{\prime}_{1}|,$
here we used Claim 3.1 in order to obtain the sizes of $X^{\prime}_{1}$ and
$Y^{\prime}_{1}.$

Let $X^{\prime\prime}_{1}$ be the set of those vertices of $X^{\prime}_{1}$
that have more than $2\gamma|Y^{\prime}_{1}|$ neighbors in $|Y^{\prime}_{1}|.$
Simple counting shows that $|X^{\prime\prime}_{1}|\leq|X^{\prime}_{1}|/2.$ Let
$X_{1}=X^{\prime}_{1}-X^{\prime\prime}_{1},$ those vertices of
$X^{\prime}_{1}$ that have less than $2\gamma|Y^{\prime}_{1}|$ neighbors in
$|Y^{\prime}_{1}|.$ By the above we have
$|X^{\prime}_{1}|/2\leq|X_{1}|\leq|X^{\prime}_{1}|.$ Set
$Y_{1}=Y_{0}-Y^{\prime}_{1}.$

For $i\geq 2$ the above is generalized. If $F[X_{i-1},Y_{i-1}]$ is not a lower
$(\varepsilon,\eta,\gamma)$-regular pair then we do the following. First find
$X^{\prime}_{i}\subset X_{i-1}$ and $Y^{\prime}_{i}\subset Y_{i-1}$ such that
$|X^{\prime}_{i}|=\varepsilon|X_{i-1}|$ and $|Y^{\prime}_{i}|=\eta|Y_{i-1}|$
and
$e(F[X^{\prime}_{i},Y^{\prime}_{i}])<\gamma|X^{\prime}_{i}|\cdot|Y^{\prime}_{i}|.$
Similarly to the above we define $X_{i}\subset X^{\prime}_{i}$ to be the set
of those vertices of $X^{\prime}_{i}$ that have less than
$2\gamma|Y^{\prime}_{i}|$ neighbors in $Y^{\prime}_{i}.$ As before, we have
$|X^{\prime}_{i}|/2\leq|X_{i}|\leq|X^{\prime}_{i}|.$ Finally, we let
$Y_{i}=Y_{i-1}-Y^{\prime}_{i}.$

Using induction one can easily verify that the claimed bounds for $|X_{i}|$
and $|Y_{i}|$ hold for every $i.$ It might not be so clear that this process
stops in a relatively few iteration steps. For that we first find an upper
bound for the number of edges that connect the vertices of $X_{i}$ with
$B-Y_{i}.$ If $u\in X_{i}$ then $u$ have at most
$2\gamma(|Y^{\prime}_{1}|+\ldots+|Y^{\prime}_{i}|)\leq 2\gamma b$ neighbors in
$B-Y_{i}$ using that $Y^{\prime}_{s}\cap Y^{\prime}_{t}=\emptyset$ for every
$s\neq t.$

Next we show that if
$(\delta(1+\eta/2)-2\gamma)(1-\eta)b<|Y_{l}|\leq(\delta(1+\eta/2)-2\gamma)b$
then $F[X_{l},Y_{l}]$ must be lower regular. Assume that $u\in X_{l}.$ Then
$deg(u;Y_{l})\geq(\delta-2\gamma)b,$ using our argument above, hence, the
number of non-neighbors of $u$ in $Y_{l}$ is at most
$(\delta(1+\eta/2)-2\gamma)b-(\delta-2\gamma)b=\delta\eta b/2.$ Let
$Y^{\prime}\subset Y_{l}$ be arbitrary with $|Y^{\prime}|=\eta|Y_{l}|.$ Then

$\frac{5}{6}\eta(\delta(1+\eta/2)-2\gamma)b\leq|Y^{\prime}|\leq\eta(\delta(1+\eta/2)-2\gamma)b,$

using that $\eta\leq 1/6.$ We have

$deg(u;Y^{\prime})\geq|Y^{\prime}|-\delta\eta
b/2\geq\frac{5}{6}\eta(\delta(1+\eta/2)-2\gamma)b-\delta\eta b/2.$

Using the upper bounds we imposed on $\eta$ and $\gamma,$ one easily obtains
that

$deg(u;Y^{\prime})\geq(\delta\eta/3+5\delta\eta^{2}/12-5/3\gamma\eta)b\geq\gamma|Y^{\prime}|.$

Hence, for every $X^{\prime}\subset X_{l}$ and $Y^{\prime}\subset Y_{l}$ with
$|Y^{\prime}|=\eta|Y_{l}|$ we have

$e(X^{\prime},Y^{\prime})\geq\gamma|X^{\prime}|\cdot|Y^{\prime}|,$

that is, if the procedure stopped because we applied the stopping rule, then
the resulting pair must always be lower $(\varepsilon,\eta,\gamma)$-regular.
Of course, this means that no matter how the procedure stops, it finds a lower
regular pair.

Next we upper bound the number of iteration steps. In every step the $Y$-side
shrinks by a factor of $(1-\eta).$ We also have that
$|Y_{l}|>(\delta(1+\eta/2)-2\gamma)(1-\eta)b.$ Putting these together we get
that

$(1-\eta)^{l}>(\delta(1+\eta/2)-2\gamma)(1-\eta)>\delta/2.$

Hence,

$l<\frac{\log(2/\delta)}{\log(1/(1-\eta))}<2\frac{\log(2/\delta)}{\eta},$

here we used elemantary calculus (in particular, the Taylor series expansion
of $\log(1+x)$) and our condition that $\eta$ is less than 1/6.

What is left is to show the lower bound for $|X_{l}|.$ Note, that
$|X_{i}|/|X_{i-1}|\geq\varepsilon/2$ for every $i\geq 1.$ Hence,

$|X_{l}|\geq\left(\frac{\varepsilon}{2}\right)^{l}a=e^{-2\log(2/\varepsilon)\log(2/\delta)/\eta}a.$

$\Box$

We are ready to prove the main result of the paper.

Proof (of Theorem 2.2): The proof is based on iteratively applying Lemma 3.2.
First we apply Lemma 3.2 for $G$ and find a lower
$(\varepsilon,\eta,\gamma)$-regular pair $G[X_{l},Y_{l}],$ where $X_{l}\subset
A$ and $Y_{l}\subset B.$ Let $A_{1}=X_{l}$ and $B_{1}=Y_{l}.$ Next we repeat
this procedure for the graph $G[A-A_{1},B].$ Similarly to the above we define
the $A_{2}$ and $B_{2}$ sets, where $A_{2}\subset A-A_{1},$ $B_{2}\subset B,$
and $G[A_{2},B_{2}]$ is a lower $(\varepsilon,\eta,\gamma)$-regular pair.

Continue this way, finding the lower regular pairs $G[A_{i},B_{i}]$ using
Lemma 2.2 such that $A_{i}\subset A-(A_{1}\cup\ldots\cup A_{i-1}),$
$B_{i}\subset B,$ and $G[A_{i},B_{i}]$ is a lower
$(\varepsilon,\eta,\gamma)$-regular pair. We stop when

$|A-(A_{1}\cup\ldots\cup A_{i})|<\varepsilon|A|.$

At this point set $A_{0}=A-(A_{1}\cup\ldots\cup A_{i}).$

Let us now prove the upper bound for the number of pairs in the decomposition.
As we have shown earlier
$|A_{i}|\geq\exp\left(-2\log(\frac{2}{\varepsilon})\log(\frac{2}{\delta})/\eta\right)n$
for $i\geq 1.$ The number of edges in an $A_{i}B_{i}$ pair is at least
$|A_{i}|(\delta-2\gamma)m>|A_{i}|\delta m/2.$ For any $1\leq i\neq j\leq k$
the edge sets of the pairs $A_{i}B_{i}$ and $A_{j}B_{j}$ are disjoint, and the
total number of edges in lower regular pairs is at most $nm.$ Hence, we have

$k\leq\frac{2nme^{2\log(\frac{1}{\varepsilon})\log(\frac{2}{\delta})/\eta}}{\varepsilon\delta
nm}=\frac{2}{\varepsilon\delta}e^{2\log(\frac{1}{\varepsilon})\log(\frac{2}{\delta})/\eta}.$

There is only one question left, bounding the total number of edges that
belong to the lower regular pairs. Assume first that $u\in A-A_{0}.$ We saw
earlier in Lemma 2.2 that $u$ lost at most $2\gamma|B|$ edges. This explains
the $2\gamma mn$ term in the theorem. If $u\in A_{0},$ none of the edges
incident to it belongs to any of the lower regular pairs, however,
$|A_{0}|\leq\varepsilon n,$ therefore, the total number of edges incident to
vertices of $A_{0}$ is at most $\varepsilon nm.$ With this we found the
decomposition of $G$ what was desired. $\Box$

Let us finish this section with a remark. Without the lower bound for the
sizes of the $A_{i}$ sets, Theorem 2.2 would be trivial: every vertex $v\in A$
could be a “subset” $A_{v}$ (a singleton), and its neighborhood $N(v)$ is the
corresponding $B_{v}.$ The result is interesting only when the $A_{i}$ sets
are large. For example, let $G$ be the following. It is a sparse bipartite
graph with vertex classes $A$ and $B$ such that $|A|=|B|=n.$ Set
$\varepsilon=\eta=1/10,$ $\delta=\log\log n/\log n,$ and $\gamma=\delta/20.$
Then $G$ has $O(n^{2}\log\log n/\log n)$ edges, and the $A_{i}$ sets for
$i\geq 1$ have size $\Omega(n/(\log n)^{c}),$ where $c<60,$ and every
$(A_{i},B_{i})$ pair is a lower $(0.1,0.1,\log\log n/(20\log n))$-regular
pair.

##  4 An application

The main advantage of Theorem 2.2 is that, as the above example shows, it can
be applied for graphs having “real-life” size, or for relatively sparse
graphs, unlike the Szemerédi Regularity lemma. Therefore, it may extend the
scope when usual methods for graph embedding (eg. counting lemma or the Blow-
up lemma [8]) can be applied.

Given a tree $T$ rooted at $r$ its level sets are defined as follows:
$L_{1}=r,$ $L_{2}=N(r),$ in general, $L_{i+1}=N^{i}(r),$ etc., where
$N^{i}(r)$ denotes those vertices of $T$ that are exactly at distance $i$ from
$r$ in $T.$

######  Proposition 4.1.

Let $0<\varepsilon,\eta,\gamma<1/10$ such that $\eta=4\gamma$ and
$\varepsilon=\gamma^{2}/10.$ Assume $G[A,B]$ is a lower
$(\varepsilon,\eta,\gamma)$-regular pair. Let $T$ be a tree rooted at $r,$
having color classes $X$ and $Y$ such that $r\in X,$ $|X|\leq(1-10\gamma)|A|$
and $|Y|\leq(1-10\gamma)|B|.$ Assume further that for every $i\geq 1$ we have
$|L_{2i}|\leq\varepsilon|A|$ and $|L_{2i+1}|\leq\eta|B|.$ Then $T\subset
G[A,B].$

Let us remark that $T$ does not have to have bounded degree, unlike in many
tree embedding results. In fact, it can have vertices with linearly large
degrees, if $\delta$ and the other parameters are constants. The statement
holds for every $G$ for which Lemma 3.2 can be applied, hence, $G$ can have
$o(n^{2})$ edges.

We need the following simple claim, the proof is left for the reader.

######  Claim 4.2.

Let $F=F(U,V)$ be a lower $(\varepsilon,\eta,\gamma)$-regular pair. Let
$U^{\prime}\subset U$ and $V^{\prime}\subset V$ such that
$|U^{\prime}|\geq\varepsilon|U|$ and $|V^{\prime}|\geq\eta|V|.$ Then
$U^{\prime}$ can have at most $\varepsilon|U|$ vertices that have less than
$\gamma|V^{\prime}|$ neighbors in $V^{\prime}.$ Similarly, $V^{\prime}$ can
have at most $\eta|V|$ vertices that have less than $\gamma|U^{\prime}|$
neighbors in $U^{\prime}.$

Proof of the proposition: We prove via an embedding algorithm. Let
$X=\\{x_{1},\ldots,x_{k}\\}$ and $Y=\\{y_{1},\ldots,y_{m}\\},$ where
$r=x_{1}.$ We will find the images of the vertices of $T$ so that we embed
height-2 subtrees of $T$ in every step, having vertices from $Y$ in the middle
level.

Denote $\varphi:V(T)\longrightarrow A\cup B$ the edge-preserving mapping that
we construct. Let $A^{f},$ respectively, $B^{f}$ denote the free (ie. vacant)
vertices of $A,$ respectively, $B.$ These sets are shrinking as the embedding
of $T$ proceeds, but due to the conditions of Proposition 4.1 we always have
that $|A^{f}|\geq 10\gamma|A|$ and $|B^{f}|\geq 10\gamma|B|.$ Divide $A^{f}$
randomly into three disjoint, approximately equal-sized subsets
$A^{f}_{1},A^{f}_{2}$ and $A^{f}_{3}.$ Let $B_{1}^{\prime}\subset B^{f}$ be
the set of those vertices that have less than $\gamma|A|$ neighbors in
$A^{f}_{1},$ the sets $B_{2}^{\prime}$ and $B_{3}^{\prime}$ are defined
analogously. Then
$|B_{1}^{\prime}|,|B_{2}^{\prime}|,|B_{3}^{\prime}|\leq\eta|B|.$

Let $v$ be an arbitrary vertex of, say, $A^{f}_{1}$ that has at least
$\gamma|B^{f}-B_{1}^{\prime}-B_{2}^{\prime}-B_{3}^{\prime}|$ neighbors in
$B^{f}-B_{1}^{\prime}-B_{2}^{\prime}-B_{3}^{\prime}.$ By Claim 4.2 we know
that $A^{f}_{1}$ has many such vertices. By the definition of the
$B_{i}^{\prime}$ sets we have that every vertex in $N(v)$ has at least
$\gamma|A^{f}_{i}|/4$ neighbors in $A^{f}_{i}$ for $i=1,2,3.$ Pick the largest
of the $A^{f}_{i}$ sets, say, it is $A^{f}_{2}.$ Then the height-2 subtree
originating at $r$ will be embedded so that the neighbors of $r$ will be
mapped onto $N(v)$ arbitrarily ($|L_{2}|$ is smaller, than $|N(v)|$), and by
construction every vertex of $N(v)$ will have many neighbors in $A^{f}_{2}.$
Now we redetermine the subsets $B_{1}^{\prime},B_{2}^{\prime},B_{3}^{\prime},$
as some vertices have become covered in $A$ and in $B.$ For the third level of
the height-2 subtree originating at $r$ we take those vertices of $A^{f}_{2}$
that are neighboring with at least a $\gamma$ proportion of
$B^{f}-B_{1}^{\prime}-B_{2}^{\prime}-B_{3}^{\prime}.$ Note that for every
$\phi(y)$ where $y$ is in the middle level we have many choices: except at
most $\varepsilon|A|$ vertices of $A^{f}_{2}$ the neighborhood $N(\phi(y))$
contains vertices with large degrees into
$B^{f}-B_{1}^{\prime}-B_{2}^{\prime}-B_{3}^{\prime}.$ This means that we are
able to map the third level. Next we continue this process so that we embed
the height-2 subtrees originating at the vertices of the third level one-by-
one.

There is only one missing detail here, the reason why we divided $A^{f}$
randomly in the beginning: if we have three $A^{f}_{i}$ sets, then the active
level belongs to one of them, say, it is $A^{f}_{i}.$ Then we map the vertices
of $T$ that are exactly two levels below them into the larger $A^{f}_{j}$-set,
where $j\in\\{1,2,3\\}-i.$ This way we never eat up any of the $A^{f}_{i}$
sets at any point in time. Since the color classes of $T$ are sufficiently
small, this procedure never gets stuck. $\Box$

We have just showed how to embed an almost spanning tree into one lower
regular pair. This can be used to approximately tile the edge set of a
sufficiently dense (say, having $\Omega(n^{2}\log\log n/\log n)$ edges and $n$
vertices) graph $G$ by large edge-disjoint subtrees. The rough sketch of this
approximate decomposition is as follows. Apply Theorem 2.2 for the graph $G,$
and then using Proposition 4.1 find one-one almost spanning subtree in the
lower regular pairs. Delete the edges used for the subtrees. If the resulting
graph has sufficiently many edges then one can use Theorem 2.2 again, and then
Proposition 4.1 for every lower regular pair. The process stops when the
remaining vacant subgraph of $G$ is too sparse, and therefore one cannot find
many large degree vertices in it. Hence, with this method one can tile the
vast majority of edges of a graph having sufficiently large density by large
subtrees. We leave the details for the reader.

## References

  * [1] N. Alon, R. A. Duke, H. Lefmann, V. Rödl and R. Yuster, The algorithmic aspects of the Regularity Lemma, Journal of Algorithms 16, (1994) 80–109.
  * [2] D. Conlon and J. Fox, Bounds for graph regularity and removal lemmas, GAFA 22 (2012), 1191-1256.
  * [3] A. M. Frieze and R. Kannan, Quick approximations to matrices and applications, Combinatorica, 19 (1999) 175–220.
  * [4] T. Gowers, Lower bounds of tower type for Szemerédi’s uniformity lemma, Geometric and Functional Analysis 7 (1997), 322–337.
  * [5] W. T. Gowers, Bipartite graphs of approximate rank one, preprint.
  * [6] W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. 166 (2007), 897–946.
  * [7] J. Komlós, M. Simonovits, Szemerédi’s Regularity Lemma and its Applications in Graph Theory, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 295–352. J. Komlós, M. Simonovits, Szemerédi’s Regularity lemma and its applications in graph theory
  * [8] J. Komlós, G.N. Sárközy and E. Szemerédi, Blow-up Lemma, Combinatorica, 17 (1997), 109–123.
  * [9] V. Rödl, B. Nagle, J. Skokan, M. Schacht and Y. Kohayakawa, The hypergraph regularity method and its applications, P. Natl. Acad. Sci. USA 102 (2005), 8109–8113.
  * [10] E. Szemerédi, Regular Partitions of Graphs, Colloques Internationaux C.N.R.S No 260 \- Problèmes Combinatoires et Théorie des Graphes, Orsay, (1976) 399–401
  * [11] E. Szemerédi, Is laziness paying off? (Absorbing method) In: Zannier U. (eds) Colloquium De Giorgi 2010-2012. Publications of the Scuola Normale Superiore, vol 4. Edizioni della Normale, Pisa (2013) 17–34.


# Redefining part-of-speech classes with distributional semantic models

Andrey Kutuzov
Department of Informatics
University of Oslo
<EMAIL_ADDRESS>
Erik Velldal
Department of Informatics
University of Oslo
<EMAIL_ADDRESS>
Lilja Øvrelid
Department of Informatics
University of Oslo
<EMAIL_ADDRESS>
###### Abstract

This paper studies how word embeddings trained on the British National Corpus
interact with part of speech boundaries. Our work targets the Universal PoS
tag set, which is currently actively being used for annotation of a range of
languages. We experiment with training classifiers for predicting PoS tags for
words based on their embeddings. The results show that the information about
PoS affiliation contained in the distributional vectors allows us to discover
groups of words with distributional patterns that differ from other words of
the same part of speech.

This data often reveals hidden inconsistencies of the annotation process or
guidelines. At the same time, it supports the notion of ‘soft’ or ‘graded’
part of speech affiliations. Finally, we show that information about PoS is
distributed among dozens of vector components, not limited to only one or two
features.

##  1 Introduction

Parts of speech (PoS) are useful abstractions, but still abstractions.
Boundaries between them in natural languages are flexible. Sometimes, large
open classes of words are situated on the verge between several parts of
speech: for example, participles in English are in many respects both verbs
and adjectives. In other cases, closed word classes ‘intersect’, e.g., it is
often difficult to tell a determiner from a possessive pronoun. As ?) puts it,
‘Grammatical categories exist along a continuum which does not exhibit sharp
boundaries between the categories’.

When annotating natural language texts for parts of speech, the choice of a
PoS tag in many ways depends on the human annotators themselves, but also on
the quality of linguistic conventions behind the division into different word
classes. That is why there have been several attempts to refine the
definitions of parts of speech and to make them more empirically grounded,
based on corpora of real texts: see, among others, the seminal work of ?). The
aim of such attempts is to identify clusters of words occurring naturally and
corresponding to what we usually call ‘parts of speech’. One of the main
distance metrics that can be used in detecting such clusters is a distance
between distributional features of words (their contexts in a reference
training corpus).

In this paper, we test this approach using predictive models developed in the
field of distributional semantics. Recent achievements in training
distributional models of language using machine learning allow for robust
representations of natural language semantics created in a completely
unsupervised way, using only large corpora of raw text. Relations between
dense word vectors (embeddings) in the resulting vector space are as a rule
used for semantic purposes. But can they be employed to discover something new
about grammar and syntax, particularly parts of speech? Do learned embeddings
help here? Below we show that such models do contain a lot of interesting data
related to PoS classes.

The rest of the paper is organized as follows. In Section 2 we briefly cover
the previous work on the subject of parts of speech and distributional models.
Section 3 describes data processing and the training of a PoS predictor based
on word embeddings. In Section 4 errors of this predictor are analyzed and
insights gained from them described. Section 5 introduces an attempt to build
a full-fledged PoS tagger within the same approach. It also analyzes the
correspondence between particular word embedding components and PoS
affiliation, before we conclude in Section 6.

##  2 Related work

Traditionally, 3 types of criteria are used to distinguish different parts of
speech: formal (or morphological), syntactic (or distributional) and semantic
[Aarts and McMahon (2008]. Arguably, syntactic and semantic criteria are not
very different from each other, if one follows the famous distributional
hypothesis stating that meaning is determined by context [Firth (1957]. Below
we show that unsupervised distributional semantic models contain data related
to parts of speech.

For several years already it has been known that some information about
morphological word classes is indeed stored in distributional models. Words
belonging to different parts of speech possess different contexts: in English,
articles are typically followed by nouns, verbs are typically accompanied by
adverbs and so on. It means that during the training stage, words of one PoS
should theoretically cluster together or at least their embeddings should
retain some similarity allowing for their separation from words belonging to
other parts of speech. Recently, among others, ?) and ?) have demonstrated how
word embeddings can improve supervised PoS-tagging.

?) showed that there also exist regular relations between words from different
classes: the vector of ‘Brazil’is related to ‘Brazilian’ in the same way as
‘England’ is related to ‘English’ and so on. Later, ?) demonstrated how words
of the same part of speech cluster into distinct groups in a distributional
model, and ?) proved that dimensions of distributional models are correlated
with different linguistic features, releasing an evaluation dataset based on
this.

Various types of distributional information has also played an important role
in previous work done on the related problem of unsupervised PoS acquisition.
As discussed in ?), we can separate at least three main directions within this
line of work: _Disambiguation_ approaches [Merialdo (1994, Toutanova and
Johnson (2007, Ravi and Knight (2009] that start out from a dictionary
providing possible tags for different words; _prototype-driven_ approaches
[Haghighi and Klein (2006, Christodoulopoulos et al. (2010] based on a small
number of prototypical examples for each PoS; _induction_ approaches that are
completely unsupervised and make no use of prior knowledge. This is also the
main focus of the comparative survey provided by [Christodoulopoulos et al.
(2010].

Work on PoS induction has a long history – including the use of distributional
methods – going back at least to ?), and recent work has demonstrated that
word embeddings can be useful for this task as well [Yatbaz et al. (2012, Lin
et al. (2015, Ling et al. (2015a].

In terms of positioning this study relative to previous work, it falls
somewhere in between the distinctions made above. It is perhaps closest to
disambiguation approaches, but it is not unsupervised given that we make use
of existing tag annotations when training our embeddings and predictors. The
goal is also different; rather than performing PoS acquisition or tagging for
its own sake, the main focus here is on analyzing the boundaries of different
PoS classes. In Section 5, this analysis is complemented by experiments with
using word embeddings for PoS prediction on unlabeled data, and here our
approach can perhaps be seen as related to previous so-called prototype-driven
approaches, but in these experiments we also make use of labeled data when
defining our prototypes.

It seems clear that one can infer data about PoS classes of words from
distributional models in general, including embedding models. As a next step
then, these models could also prove useful for deeper analysis of part of
speech boundaries, leading to discovery of separate words or whole classes
that tend to behave in non-typical ways. Discovering such cases is one
possible way to improve the performance of existing automatic PoS taggers
[Manning (2011]. These ‘outliers’ may signal the necessity to revise the
annotation strategy or classification system in general. Section 3 describes
the process of constructing typical PoS clusters and detecting words that
belong to a cluster different from their traditional annotation.

##  3 PoS clusters in distributional models

Our hypothesis is that for the majority of words their parts of speech can be
inferred from their embeddings in a distributional model. This inference can
be considered a classification problem: we are to train an algorithm that
takes a word vector as input and outputs its part of speech. If the word
embeddings do contain PoS-related data, the properly trained classifier will
correctly predict PoS tags for the majority of words: it means that these
lexical entities conform to a dominant distributional pattern of their part of
speech class. At the same time, the words for which the classifier outputs
incorrect predictions, are expected to be ‘outliers’, with distributional
patterns different from other words in the same class. These cases are the
points of linguistic interest, and in the rest of the paper we mostly
concentrate on them.

To test the initial hypothesis, we used the XML Edition of British National
Corpus (BNC), a balanced and representative corpus of English language of
about 98 million word tokens in size. As stated in the corpus documentation,
‘it was [PoS-]tagged automatically, using the CLAWS4 automatic tagger
developed by Roger Garside at Lancaster, and a second program, known as
Template Tagger, developed by Mike Pacey and Steve Fligelstone’ [Burnard
(2007]. The corpus authors report a precision of 0.96 and recall of 0.99 for
their tools, based on a manually checked sample. For this research, it is
important that BNC is an established and well-studied corpus of English with
PoS-tags and lemmas assigned to all words.

We produced a version of BNC where all the words were replaced with their
lemmas and PoS-tags converted into the Universal Part-of-Speech Tagset [Petrov
et al. (2012]111We used the latest version of the tagset available at
http://universaldependencies.org. Thus, each token was represented as a
concatenation of its lemma and PoS tag (for example, ‘love_VERB’ and
‘love_NOUN’ yield different word types). The mappings between BNC tags and
Universal tags were created by us and released online222http://bit.ly/291BlpZ.

The main motivation for the use of the Universal PoS tag set was that this is
a newly emerging standard which is actively being used for annotation of a
range of different languages through the community-driven Universal
Dependencies effort [Nivre et al. (2016]. Additionally, this tag set is
coarser than the original BNC one: it simplifies the workflow and eliminates
the necessity to merge ‘inflectional’ tags into one (e.g., singular and plural
nouns into one ‘noun’ class). This conforms with our interest in parts of
speech proper, not inflectional forms within one PoS. We worked with the
following 16 Universal tags: ADJ, ADP, ADV, AUX, CONJ, DET, INTJ, NOUN, NUM,
PART, PRON, PROPN, SCONJ, SYM, VERB, X (punctuation tokens marked with the
PUNCT tag were excluded).

Then, a Continuous Skipgram embedding model [Mikolov et al. (2013a] was
trained on this corpus, using a vector size of 300, 10 negative samples, a
symmetric window of 2 words, no down-sampling, and 5 iterations over the
training data. Words with corpus frequency less than 5 were ignored. This
model represents the semantics of the words it contains. But at the same time,
for each word, a PoS tag is known (from the BNC annotation). It means that is
is possible to test how good the word embeddings are in grouping words
according to their parts of speech.

To this end, we extracted vectors for the 10 000 most frequent words from the
resulting model (roughly, these are the words with corpus frequency more than
500). Then, these vectors were used to train a simple logistic regression
multinomial classifier aimed to predict the word’s part of speech.

It is important that we applied classification, not clustering here. Naive
K-Means clustering of word embeddings in our model into 16 groups showed very
poor performance (adjusted Rand index of 0.52 and adjusted Mutual Information
score of 0.61 in comparison to the original BNC tags). This is because PoS-
related features form only a part of embeddings, and in the fully unsupervised
setting, the words tend to cluster into semantic groups rather than
‘syntactic’ ones. But when we train a classifier, it locates exactly the
features (or combinations of features) that correspond to parts of speech, and
uses them subsequently.

Note that during training (and subsequent testing), each word’s vector was
used several times, proportional to frequency of the word in the corpus, so
the classifier was trained on 177 343 (sometimes repeating) instances, instead
of the original 10 000. This was done to alleviate classification bias due to
class imbalance: there are much fewer word types in the closed PoS classes
(pronouns, conjunctions, etc.) than in the open ones (nouns, verbs, etc.), so
without considering word frequency, the model does not have a chance to learn
good predictors for ‘small’ classes and ends up never predicting them. At the
same time, words from closed classes occur very frequently in the running
text, so after ‘weighting’ training instances by corpus frequency, the balance
is restored and the classifier model has enough training instances to learn to
predict closed PoS classes as well. As an additional benefit, by this
modification we make frequent words from all classes more ‘influential’ in
training the classifier.

The resulting classifier showed a weighted macro-averaged F-score (over all
PoS classes) and accuracy equal to 0.98, with 10-fold cross-validation on the
training set. This is a significant improvement over the one-feature baseline
classifier (classify using only one vector dimension with maximum F-value in
relation to class tags), with F-score equal to only 0.22. Thus, the results
support the hypothesis that word embeddings contain information that allows us
to group words together based on their parts of speech. At the same time, we
see that this information is not restricted to some particular vector
component: rather, it is distributed among several axis of the vector space.

After training the classifier, we were able to use it to detect ‘outlying’
words in the BNC (judging by the distributional model). So as not to
experiment on the same data we had trained our classifier on, we compiled
another test set of 17 000 vectors for words with the BNC frequencies between
100 and 500. They were weighted by word frequencies in the same way as the
training set, and the resulting test set contained 30 710 instances. Compared
to the training error reported above we naturally observe a drop in
performance when predicting PoS for this unseen data, but the classifier still
appears quite robust, yielding an F-score of 0.91. However, some of the drop
is also due to the fact that we are applying the classifier to words with
lower frequency, and hence we have somewhat less training data for the input
embeddings.

Furthermore, to make sure that the results can potentially be extended to
other texts, we applied the trained classifier to all lemmas from the human-
annotated Universal Dependencies English Treebank [Silveira et al. (2014]. The
words not present in the distributional model were omitted (they sum to 27% of
word types and 10% of word tokens). The classifier showed an F-Score equal to
0.99, further demonstrating the robustness of the classifier. Note, however,
that part of this performance is because the UD Treebank contains many words
from the classifier training set. Essentially, it means that the decisions of
the UD human annotators are highly consistent with the distributional patterns
of words in the BNC.

In sum, the vast majority of words are classified correctly, which means that
their embeddings enable the detection of their parts of speech. In fact, one
can visualize ‘centroid’ vectors for each PoS by simply averaging vectors of
words belonging to this part of speech. We did this for 10 000 words from our
training set.

Figure 1: Centroid embedding for coordinating conjunctions Figure 2: Centroid
embedding for subordinating conjunctions

Plots for centroid vectors of coordinating and subordinating conjunctions are
shown in Figures 1 and 2 respectively. Even visually one can notice a very
strongly expressed feature near the ‘100’ mark in the horizontal axis
(component number 94). In fact, this is indeed an idiosyncratic feature of
conjunctions: none of the other parts of speech shows such a property. More
details about what vector components are relevant to part of speech
affiliation are given in Section 5.

Additionally, with centroid PoS vectors we can find out how similar different
parts of speech are to each other, by simply measuring cosine similarity
between them. If we rank PoS pairs according to their similarity (Table 1),
what we see is that nominative parts of speech are close to each other,
determiners and pronouns are also similar, as well as prepositions and
subordinating conjunctions; quite in accordance with linguistic intuition.
Proper nouns are not very similar to common nouns, with cosine similarity
between them only 0.67 (even adverbs are closer). Arguably, this is explained
by co-occurrences together with the definite article, and as we show below,
this helps the model to successfully separate the former from the latter.

Table 1: Distributional similarity between parts of speech (fragment) Cosine similarity | PoS pair
---|---
0.81 | NOUN ADJ
0.77 | ADV PRON
0.73 | DET PRON
0.73 | ADV ADJ
… | …
… | …
0.37 | INTJ NUM
0.36 | AUX NUM

Despite generally good performance of the classifier, if we look at our BNC
test set, 1741 word types (about 10% of the whole test set vocabulary) were
still classified incorrectly. Thus, they are somehow dissimilar to
‘prototypical’ words of their parts of speech. These are the ‘outliers’ we
were after. We analyze the patterns found among them in the next section.

##  4 Not from this crowd: analyzing outliers

First, we filtered out misclassified word types with ‘X’ BNC annotation (they
are mostly foreign words or typos). This leaves us with 1558 words for which
the classifier assigned part of speech tags different from the ones in the
BNC. It probably means that these words’ distributional patterns differ
somehow from what is more typically observed, and that they tend to exhibit
behavior similar to another part of speech. Table 2 shows the most frequent
misclassification cases, together accounting for more than 85% of errors.

Table 2: Most frequent PoS misclassifications of the distributional predictor. The # column lists the number of word types. # | Actual PoS | Predicted PoS
---|---|---
347 | PROPN | NOUN
313 | ADJ | NOUN
190 | NOUN | ADJ
91 | NOUN | PROPN
87 | PROPN | ADJ
57 | VERB | ADJ
55 | NOUN | NUM
52 | NUM | NOUN
45 | NUM | PROPN
28 | ADV | PROPN
25 | ADV | NOUN
25 | ADJ | PROPN
20 | ADV | ADJ

Additionally, we ranked misclassification cases by ‘part of speech coverage’,
that is by the ratio of the words belonging to a particular PoS for which our
classifier outputs this particular type of misclassification. For example,
proper nouns misclassified as common nouns constitute the most numerous error
type in Table 2, but in fact only 9% of all proper nouns in the test set were
misclassified in this way. There are parts of speech with a much larger
portion of word-types predicted erroneously: e.g., 22% of subordinate
conjunctions were classified as adverbs. Table 3 lists error types with the
highest coverage (we excluded error types with absolute frequency equal to 1,
as it is impossible to speculate on solitary cases).

We now describe some of the interesting cases. Almost 30% of error types
(judging by absolute amount of misclassified words) consist of proper nouns
predicted to be common ones and vice versa. These cases do not tell us
anything new, as it is obvious that distributionally these two classes of
words are very similar, take the same syntactic contexts and hardly can be
considered different parts of speech at all. At the same time, it is
interesting that the majority of proper nouns in the test set (88%) was
correctly predicted as such. It means that in spite of contextual similarity,
the distributional model has managed to extract features typical for proper
names. Errors mostly cover comparatively rare names, such as ‘luftwaffe’,
‘stasi’, ‘stonehenge’, or ‘himalayas’. Our guess is that the model was just
not presented with enough contexts for these words to learn meaningful
representations. Also, they are mostly not personal names but toponyms or
organization names, probably occurring together with the definite article the,
unlike personal names.

Another 30% of errors are due to vague boundaries between nominal and
adjectival distribution patterns in English: nouns can be modified by both (it
seems that cases where a proper noun is mistaken for an adjective are often
caused by the same factor). Words like ‘materialist_NOUN’, ‘starboard_NOUN’ or
‘hypertext_NOUN’ are tagged as nouns in the BNC, but they often modify other
nouns, and their contexts are so ‘adjectival’ that the distributional model
actually assigned them semantic features highly similar to those of
adjectives. Vice versa, ‘white-collar_ADJ’ (an adjective in BNC) is regarded
as a noun from the point of view of our model. Indeed, there can be
contradicting views on the correct part of speech for this word in phrases
like ‘and all the other white-collar workers’. Thus, in this case the
distributional model highlights the already known similarity between two word
classes.

The cases of verbs mistaken for adjectives seem to be caused mostly by passive
participles (‘was overgrown’, ‘is indented’), which intuitively are indeed
very adjective-like. So, this gives us a set of verbs dominantly (or almost
exclusively, like ‘to intertwine’ or ‘to disillusion’) used in passive. Of
course, we will hardly announce such verbs to be adjectives based on that
evidence, but at least we can be sure that this sub-class of verbs is clearly
semantically and distributionally different from other verbs.

The next numerous type of errors consists of common nouns predicted to be
numerals. A quick glance at the data reveals that 90% of these ‘nouns’ are in
fact currency amounts and percentages (‘£70’, ‘33%’, ‘$1’, etc). It seems
reasonable to classify these as numerals, even though they contain some kind
of nominative entities inside. Judging by the decisions of the classifier,
their contexts do not differ much from those of simple numbers, and their
semantics is similar. The Universal Dependencies Treebank is more consistent
in this respect: it separates entities like ‘1$’ into two tokens: a numeral
(NUM) and a symbol (SYM). Consequently, when our classifier was tested on the
words from the UD Treebank, there was only one occurrence of this type of
error.

Related to this is the inverse case of numerals predicted to be common or
proper nouns. It is interesting that this error type also ranks quite high in
terms of coverage: if we combine numerals predicted to be common and proper
nouns, we will see that 17% of all numerals in the test set were subject to
this error. The majority of these ‘numerals’ are years (‘1804’, ‘1776’,
‘1822’) and decades (‘1820s’, ‘60s’ and even ‘twelfths’). Intuitively, such
entities do indeed function as nouns (‘I’d like to return to the sixties’).
Anyway, it is difficult to invent a persuasive reason for why ‘fifty pounds’
should be tagged as a noun, but ‘the year 1776’ as a numeral. So, this points
to possible (minor) inconsistencies in the annotation strategy of the BNC.
Note that a similar problem exists in the Penn Treebank as well [Manning
(2011].

Adverbs classified as nouns (53 words in total for both common and proper
nouns) are possibly the ones often followed by verbs or appearing in company
of adjectives (examples are ‘ultra’ and ‘kinda’). This made the model treat
them as close to the nominative classes. Interestingly, most ‘adverbs’
predicted to be proper nouns are time indicators (‘7pm’, ‘11am’); this also
raises questions about what adverbial features are really present in these
entities. Once again, unlike the BNC, the UD Treebank does not tag them as
adverbs.

Table 3: Coverage of misclassifications with distributional predictor, i.e., ratio of errors over all word types of a given PoS. The absolute type count is given by #. Coverage | Actual PoS | Predicted PoS | #
---|---|---|---
0.22 | SCONJ | ADV | 2
0.17 | INTJ | PROPN | 8
0.11 | ADP | ADJ | 3
0.09 | ADJ | NOUN | 313
0.09 | PROPN | NOUN | 347
0.09 | NUM | NOUN | 52
0.08 | NUM | PROPN | 45

The cases we described above revealed some inconsistencies in the BNC
annotation. However, it seems that with adverbs mistaken for adjectives, we
actually found a systematic error in the BNC tagging: these cases are mostly
connected to adjectives like ‘plain’, ‘clear’ or ‘sharp’ (including
comparative and superlative forms) erroneously tagged in the corpus as
adverbs. These cases are not rare: just the three adjectives we mentioned
alone appear in the BNC about 600 times with an adverb tag, mostly in clauses
of the kind ‘the author makes it plain that…’, so-called small clauses [Aarts
(2012]. Sometimes these tokens are tagged as ambiguous, and the adjective tag
is there as a second variant; however, the corpus documentation states that in
such cases the first variant is always more likely. Thus, distributional
models can actually detect outright errors in PoS-tagged corpora, when
incorrectly tagged words strongly tend to cluster with another part of speech.
In the UD treebank such examples can also be observed, but they are much fewer
and more ‘adverbial’, like ‘it goes clear through’.

Turning to Table 3, most of the entries were already covered above, except the
first 3 cases. These relate to closed word classes (functional words), which
is why the absolute number of influenced word types is low, but the coverage
(ratio of all words of this PoS) is quite high.

First, out of 9 distinct subordinate conjunctions in the test set, 2 were
predicted to be adverbs. This is not surprising, as these words are ‘seeing’
and ‘immediately’. For ‘seeing’ the prediction seems to be just a random guess
(the prediction confidence was as low as 0.3), but with ‘immediately’ the
classifier was actually more correct than the BNC tagger (the prediction
confidence was about 0.5). In BNC, these words are mostly tagged as
subordinate conjunctions in cases when they occur sentence-initially
(‘Immediately, she lowered the gun’). The other words marked as SCONJ in the
test set are really such, and the classifier made correct predictions matching
the BNC tags.

Interjections mistaken for proper names do not seem very interpretable
(examples are ‘gee’, ‘oy’ and ‘farewell’). At the same time, 3 prepositions
predicted to be adjectives clearly form a separate group: they are ‘cross’,
‘pre’ and ‘pro’. They are not often used as separate words, but when they are
(‘Did anyone encounter any trouble from Hibs fans in Edinburgh pre season?’),
they are very close to adjectives or adverbs, so the predictions of the
distributional classifier once again suggest shifting parts of speech
boundaries a bit.

Error analysis on the vocabulary from the Universal Dependencies Treebank
showed pretty much the same results, except for some differences already
mentioned above.

There exists another way to retrieve this kind of data: to process tagged data
with a conventional PoS tagger and analyze the resulting confusion matrix. We
tested this approach by processing the whole BNC with the Stanford PoS Tagger
[Toutanova et al. (2003]. Note that as an input to the tagger we used not the
whole sentences from the corpora, but separate tokens, to mimic our workflow
with the distributional predictor. Prior to this, BNC tags were converted to
the Penn Treebank tagset333https://www.cis.upenn.edu/~treebank/ to match the
output of the tagger. As we are interested in coarse, ‘overarching’ word
classes, inflectional forms were merged into one tag. That was easy to
accomplish by dropping all characters of the tags after the first two
(excluding proper noun tags, which were all converted to NNP).

Analysis of the confusion matrix (cases where the tag predicted by the
Stanford tagger was different from the BNC tag) revealed the most frequent
error types shown in Table 4. Despite similar top positions of errors types
‘proper noun predicted as common noun’ and ‘nouns and adjectives mistaken for
each other’, there are also very frequent errors of types ‘verb to noun’ and
‘adjective to verb’, not observed in the distributional confusion matrix
(Table 2). We would not be able to draw the same insights that we did from the
distributional confusion matrix: the case with verbs mistaken for adjective is
ranked only 12th, adverbs mistaken for nouns - 13th, etc.

Table 4: Most frequent PoS misclassifications with the Stanford tagger (counting word types). # | Actual | Predicted
---|---|---
172675 | NNP | NN
47202 | VB | NN
40218 | JJ | NN
24075 | NN | JJ
9723 | JJ | VB

Table 5 shows top misclassification types by their word type coverage. Once
again, interesting cases we discovered with the distributional confusion
matrix (like subordinating conjunctions mistaken for adverbs and prepositions
mistaken for adjectives) did not show up. Obviously, a lot of other insights
can be extracted from the Stanford Tagger errors (as has been shown in
previous work), but it seems that employing a distributional predictor reveals
different error cases and thus is useful in evaluating the sanity of tag sets.

Table 5: Coverage of misclassifications (from all word types of this PoS) with the Stanford tagger. Coverage | Actual | Predicted | #
---|---|---|---
0.91 | NNP | NN | 172675
0.8 | UH | NN | 576
0.79 | DT | NN | 217
0.78 | EX | JJ | 11
0.78 | PR | NN | 517

To sum up, the analysis of ‘boundary cases’ detected by a classifier trained
on distributional vectors, indeed reveals sub-classes of words lying on the
verge between different parts of speech. It also allows for quickly
discovering systematic errors or inconsistencies in PoS annotations, whether
they be automatic or manual. Thus, discussions about PoS boundaries would
benefit from taking this kind of data into consideration.

##  5 Embeddings as PoS predictors

In the experiment described in the previous section, we used a model trained
on words concatenated with their PoS tags. Thus, our ‘classifier’ was a bit
artificial in that it required a word plus a tag as an input, and then its
output is a judgment about what tag is most applicable to this combination
from the point of view of the BNC distributional patterns. This was not a
problem for us, as our aim was exactly to discover lexical outliers.

But is it possible to construct a proper predictor in the same way, which is
able to predict a PoS tag for a word without any pre-existing tags as hints?
Preliminary experiments seem to indicate that it is.

We trained a Continuous Skipgram distributional model on the BNC lemmas
without PoS tags. After that, we constructed a vocabulary of all unambiguous
lemmas from the UD Treebank training set. ‘Unambiguous’ here means that the
lemma either was always tagged with one and the same PoS tag in the Treebank,
or has one ‘dominant’ tag, with frequencies of other PoS assignments not
exceeding 1/2 of the dominant assignment frequency. Our hypothesis was that
these words are prototypical examples of their PoS classes, with corresponding
prototypical features most pronounced; this approach is conceptually similar
to [Haghighi and Klein (2006]. We also removed words with frequency less than
10 in the Treebank. This left us with 1564 words from all Universal Tag
classes (excluding PUNCT, X and SYM, as we hardly want to predict punctuation
or symbol tag).

Then the same simple logistic regression classifier was trained on the
distributional vectors from the model for these 1564 words only, using UD
Treebank tags as class labels (the training instances were again weighted
proportionally to the words’ frequencies in the Treebank). The resulting
classifier showed an accuracy of 0.938 after 10-fold cross-validation on the
training set.

We then evaluated the classifier on tokens from the UD Treebank test set. Now
the input to the classifier consisted of these tokens’ lemmas only. Lemmas
which were missing from the model’s vocabulary were omitted (860 of a total of
21759 tokens in the test set). The model reached an accuracy of 0.84 (weighted
precision 0.85, weighted recall 0.84).

These numbers may not seem very impressive in comparison with the performance
of current state-of-the-art PoS taggers. However, one should remember that
this classifier knows absolutely nothing about a word’s context in the current
sentence. It assigns PoS tags based solely on the proximity of the word’s
distributional vector in an unsupervised model to those of prototypical PoS
examples. The classifier was in fact based only on knowledge of what words
occurred in the BNC near other words within a symmetric window of 2 words to
the left and to the right. It did not even have access to the information
about exact word order within this sliding window, which makes its performance
even more impressive.

It is also interesting that one needs as few as a thousand example words to
train a decent classifier. Thus, it seems that PoS affiliation is expressed
quite strongly and robustly in word embeddings. It can be employed, for
example, in preliminary tagging of large corpora of resource-poor languages.
Only a handful of non-ambiguous words need to be manually PoS-tagged, and the
rest is done by a distributional model trained on the corpus.

Note that applying a K-neighbors classifier instead of logistic regression
returned somewhat lower results, with 0.913 accuracy on 10-fold cross-
validation with the training set, and 0.81 accuracy on the test set. This
seems to support our hypothesis that several particular embedding components
correspond to part of speech affiliation, but not all of them. As a result,
K-neighbors classifier fails to separate these important features from all the
others and predicts word class based on its nearest neighbors with all
dimensions of the semantic space equally important. At the same time, logistic
regression learns to pay more attention to the relevant features, neglecting
unimportant ones.

To find out how many features are important for the classifier, we used the
same training and test set, and ranked all embedding components (features,
vector dimensions) by their ANOVA F-value related to PoS class. Then we
successively trained the classifier on increasing amounts of top-ranked
features (top $k$ best) and measured the training set accuracy.

Figure 3: Classifier accuracy depending on the number of used vector
components ($k$)

The results are shown in Figure 3. One can see that the accuracy smoothly
grows with the number of used features, eventually reaching almost ideal
performance on the training set. It is difficult to define the point where the
influence of adding features reaches a plateau; it may lie somewhere near
$k=100$. It means that the knowledge about PoS affiliation is distributed
among at least one hundred components of the word embeddings, quite consistent
with the underlying idea of embedding models.

One might argue that the largest gap in performance is between $k=2$ and $k=3$
(from 0.38 to 0.51) and thus most PoS-related information is contained in the
3 components with the largest F-value (in our case, these 3 features were
components 31, 51 and 11). But an accuracy of 0.51 is certainly not an
adequate result, so even if important, these components are not sufficient to
robustly predict part of speech affiliation for a word. Further research is
needed to study the effects of adding features to the classifier training.

Regardless, an interesting finding is that part of speech affiliation is
distributed among many components of the word embeddings, not concentrated in
one or two specific features. Thus, the strongly expressed component 94 in the
average vector of conjunctions (Figures 1 and 2) seems to be a solitary case.

##  6 Conclusion

Distributional semantic vectors trained on word contexts from large text
corpora can learn knowledge about part of speech clusters. Arguably, they are
good at this precisely because part of speech boundaries are not strict, and
even sometimes considered to be a non-categorical linguistic phenomenon
[Manning (2015].

In this paper we have demonstrated that semantic features derived in the
process of training a PoS prediction model on word embeddings can be employed
both in supporting linguistic hypotheses about part of speech class changes
and in detecting and fixing possible annotation errors in corpora. The
prediction model is based on simple logistic regression and the word
embeddings are trained using Continuous Skip-Gram model over PoS-tagged
lemmas. We show that the word embeddings contain robust data about the PoS
classes of the corresponding words, and that this knowledge seems to be
distributed among several components (at least a hundred in our case of
300-dimensional model). We also report preliminary results for predicting PoS
tags using a classifier trained on a small number of prototypical members
(words with a dominant PoS class) and applying it to embeddings estimated from
unlabeled data. A detailed error analysis and experimental results are
reported for both the BNC and the UD Treebank.

The reported experiment form part of ongoing research, and we plan to extend
it, particularly conducting similar experiments with other languages
typologically different from English. We also plan to continue studying the
issue of correspondence between particular embedding components and part of
speech affiliation. Another direction of future work is finding out how
different hyperparameters for training distributional models (including
training corpus pre-processing) influence their performance in PoS
discrimination, and also comparing the results to using structured embedding
models like those of ?).

## References

  * [Aarts and McMahon (2008]  Bas Aarts and April McMahon.  2008\.  The handbook of English linguistics.  John Wiley & Sons.
  * [Aarts (2012]  Bas Aarts.  2012\.  Small Clauses in English. The Nonverbal Types.  De Gruyter Mouton, Boston.
  * [Biber et al. (1999]  Douglas Biber, Stig Johansson, Geoffrey Leech, Susan Conrad, Edward Finegan, and Randolph Quirk.  1999\.  Longman grammar of spoken and written English, volume 2.  MIT Press.
  * [Burnard (2007]  Lou Burnard.  2007\.  Users Reference Guide for British National Corpus (XML Edition).  Oxford University Computing Services, UK.
  * [Christodoulopoulos et al. (2010]  Christos Christodoulopoulos, Sharon Goldwater, and Mark Steedman.  2010\.  Two decades of unsupervised POS induction: How far have we come?  In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 575–584. Association for Computational Linguistics.
  * [Firth (1957]  John Firth.  1957\.  A synopsis of linguistic theory, 1930-1955.  Blackwell.
  * [Haghighi and Klein (2006]  Aria Haghighi and Dan Klein.  2006\.  Prototype-driven learning for sequence models.  In Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, pages 320–327. Association for Computational Linguistics.
  * [Houston (1985]  Ann Celeste Houston.  1985\.  Continuity and change in English morphology: The variable (ING).  Ph.D. thesis, University of Pennsylvania.
  * [Lin et al. (2015]  Chu-Cheng Lin, Waleed Ammar, Chris Dyer, and Lori Levin.  2015\.  Unsupervised POS induction with word embeddings.  arXiv preprint arXiv:1503.06760.
  * [Ling et al. (2015a]  Wang Ling, Lin Chu-Cheng, Yulia Tsvetkov, and Silvio Amir.  2015a.  Not all contexts are created equal: Better word representations with variable attention.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing.
  * [Ling et al. (2015b]  Wang Ling, Chris Dyer, Alan W. Black, and Isabel Trancoso.  2015b.  Two/too simple adaptations of word2vec for syntax problems.  In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics – Human Language Technologies, pages 1299–1304, Denver, Colorado.
  * [Liu et al. (2016]  Quan Liu, Zhen-Hua Ling, Hui Jiang, and Yu Hu.  2016\.  Part-of-speech relevance weights for learning word embeddings.  arXiv preprint arXiv:1603.07695.
  * [Manning (2011]  Christopher D Manning.  2011\.  Part-of-speech tagging from 97% to 100%: is it time for some linguistics?  In Computational Linguistics and Intelligent Text Processing, pages 171–189. Springer.
  * [Manning (2015]  Christopher D Manning.  2015\.  Computational linguistics and deep learning.  Computational Linguistics, 41:701–707.
  * [Merialdo (1994]  Bernard Merialdo.  1994\.  Tagging english text with a probabilistic model.  Computational Linguistics, 20(2):155–172.
  * [Mikolov et al. (2013a]  Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  2013a.  Distributed representations of words and phrases and their compositionality.  In Advances in neural information processing systems, pages 3111–3119.
  * [Mikolov et al. (2013b]  Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig.  2013b.  Linguistic regularities in continuous space word representations.  In Proceedings of NAACL-HLT 2013, pages 746–751.
  * [Nivre et al. (2016]  Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajič, Christopher D. Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty, and Daniel Zeman.  2016\.  Universal Dependencies v1: A multilingual treebank collection.  In Proceedings of the International Conference on Language Resources and Evaluation (LREC).
  * [Petrov et al. (2012]  Slav Petrov, Dipanjan Das, and Ryan McDonald.  2012\.  A universal part-of-speech tagset.  In LREC 2012.
  * [Plank et al. (2016]  Barbara Plank, Anders Søgaard, and Yoav Goldberg.  2016\.  Multilingual part-of-speech tagging with bidirectional long short-term memory models and auxiliary loss.  arXiv preprint arXiv:1604.05529.
  * [Ravi and Knight (2009]  Sujith Ravi and Kevin Knight.  2009\.  Minimized models for unsupervised part-of-speech tagging.  In Proceedings of ACL-IJCNLP 2009, pages 504–512, Singapore.
  * [Schütze (1995]  Hinrich Schütze.  1995\.  Distributional part-of-speech tagging.  In Proceedings of the seventh conference on European chapter of the Association for Computational Linguistics, pages 141–148. Morgan Kaufmann Publishers Inc.
  * [Silveira et al. (2014]  Natalia Silveira, Timothy Dozat, Marie-Catherine de Marneffe, Samuel Bowman, Miriam Connor, John Bauer, and Christopher D. Manning.  2014\.  A gold standard dependency corpus for English.  In Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC-2014).
  * [Toutanova and Johnson (2007]  Kristina Toutanova and Mark Johnson.  2007\.  A Bayesian LDA-based model for semi-supervised part-of-speech tagging.  In Proceedings of the Neural Information Processing Systems Conference (NIPS).
  * [Toutanova et al. (2003]  Kristina Toutanova, Dan Klein, Christopher D Manning, and Yoram Singer.  2003\.  Feature-rich part-of-speech tagging with a cyclic dependency network.  In Proceedings of the 2003 NAACL-HLT Conference-Volume 1, pages 173–180. Association for Computational Linguistics.
  * [Tsuboi (2014]  Yuta Tsuboi.  2014\.  Neural networks leverage corpus-wide information for part-of-speech tagging.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 938–950.
  * [Tsvetkov et al. (2015]  Yulia Tsvetkov, Manaal Faruqui, Wang Ling, Guillaume Lample, and Chris Dyer.  2015\.  Evaluation of word vector representations by subspace alignment.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, Lisbon, Portugal, 17-21 September 2015, pages 2049–2054.
  * [Yatbaz et al. (2012]  Mehmet Ali Yatbaz, Enis Sert, and Deniz Yuret.  2012\.  Learning syntactic categories using paradigmatic representations of word context.  In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 940–951. Association for Computational Linguistics.