# A cutting plane algorithm for globally solving
low dimensional k-means clustering problems

Martin Ryner, Jan Kronqvist, Johan Karlsson
Division of Numerical Analysis, Optimization and Systems Theory,
Department of Mathematics,
KTH Royal Institute of Technology, Stockholm, Sweden
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Clustering is one of the most fundamental tools in data science and machine
learning, and k-means clustering is one of the most common such methods. There
is a variety of approximate algorithms for the k-means problem, but computing
the globally optimal solution is in general NP-hard. In this paper we consider
the k-means problem for instances with low dimensional data and formulate it
as a structured concave assignment problem. This allows us to exploit the low
dimensional structure and solve the problem to global optimality within
reasonable time for large data sets with several clusters. The method builds
on iteratively solving a small concave problem and a large linear programming
problem. This gives a sequence of feasible solutions along with bounds which
we show converges to zero optimality gap. The paper combines methods from
global optimization theory to accelerate the procedure, and we provide
numerical results on their performance.

_K_ eywords Clustering $\cdot$ k-means keyword $\cdot$ Global optimization
$\cdot$ Cutting plane method

##  1 Introduction

###  1.1 Background

Clustering is a fundamental problem in the field of machine learning and data
analysis for partitioning a dataset in order to discover underlying patterns
or structures. One of the most widely used models is the k-means problem [1,
2], which builds on describing the data as well as possible using centroids.
More specifically, for a data set
$\\{x_{i}\\}_{i=1}^{n}\subset\mathbb{R}^{d}$, and a specified number of
clusters $k$, the goal is to find centroids
$\\{y_{j}\\}_{j=1}^{k}\subset\mathbb{R}^{d}$ that minimize the sum of squared
distances between the data points and their respective centroids, i.e.,

$\displaystyle\min_{\\{y_{j}\\}_{j=1}^{k}\subset\mathbb{R}^{d}}\sum_{i=1}^{n}\min_{j\in\\{1,\ldots,k\\}}\|x_{i}-y_{j}\|^{2}.$
(1)

A commonly used method is the so called k-means algorithm, which iteratively
adjusts the locations of the centroids, $\\{y_{j}\\}_{j=1}^{k}$, and reassigns
data points to the nearest centroid until convergence. This was introduced by
Lloyd in 1957 (however, first published in [2]) and guarantees that the
objective function in (1) is non-increasing in each step. However, as pointed
out in the original article, the method is not aiming or shouldn’t be
considered to be a near optimal solution to the problem, but to give the user
suggestions about how their data is organized.

Recent development of local methods involves smart seeding of the centroid
positions. One widely used such method is the k-means++ algorithm [3], which
has a $\mathcal{O}(\log k)$ multiplicative error bound to the optimal
solution. However, there is also a theoretical bound [4] of how good such
local search methods may become, which motivates research on global methods.

###  1.2 Contributions

In this paper we propose an algorithm that globally solves the k-means problem
and which is computationally feasible for small $k$ (# clusters) and $d$ (data
dimension). The main contributions in this paper can be summarized as follows:

  * •

We formulate the $k$-means problem as a concave assignment problem with
dimension depending on $k$ and $d$.

  * •

We propose a new method to solve the k-means problem (1), which involves
solving a sequence of alternating optimization problems, one which is linear
with polynomial complexity in $n$ and one which is low-dimensional if $k$ and
$d$ are small.

  * •

We give a proof showing that the solution converges to a global optimal
solution. Furthermore, the method provides an optimality gap for which the
user can terminate the problem at a given accuracy and retrieve a solution.

  * •

We explore features such as symmetry breaking, various cuts and integer
constraints in order to accelerate the algorithm.

  * •

We illustrate the results of the method numerically and compare with state of
the art global optimizers.

###  1.3 Related work

Modern implementations of the k-means algorithm often incorporate
optimizations and enhancements to improve efficiency and performance. Some of
the algorithms used today are Lloyd’s Algorithm [2], Mini-Batch K-Means [5]
and K-Means++ initialization [3]. More recent work include [6, 7, 8, 9, 10, 4]
which aim to improve the understanding, error bounds, performance and scale.
The intense research of methods to solve the problem and the vast amount of
publications where it is used shows that this idea of dividing experimental
data is popular.

The existing algorithms cater to various data sizes, computational resources,
and efficiency requirements. The choice of algorithm depends on the specific
problem, data characteristics, and available resources. While the core k-means
concept remains the same, these modern variations have helped address some of
the limitations and challenges of the original algorithm.

The original Lloyd’s algorithm and its variations converge to a local minimum.
However, the quality of the obtained solution heavily depends on the initial
placement of centroids. Poor initialization might lead to suboptimal solutions
or slow convergence. K-means++ initialization, introduced to mitigate this
initialization problem, improves convergence guarantees in practice by
selecting initial centroids that are well spread out in the data space. This
initialization technique provides probabilistic bounds on the quality of the
solution in terms of the approximation factor compared to the optimal
solution. More specifically, Kanungo [4] showed a multiplicative
$(9+\epsilon)$ error bound, also showing that local search methods utilizing a
finite amount of swaps of the assignments cannot improve the approximation
below $(9-\epsilon)$ bounds. Ahmadian et al. [10] [Theorem 3.4] showed a
multiplicative error bound of 6.3574 to the globally optimal solution. On the
same topic, Lattanzi [9] [Theorem 1] showed a local search method that, when
the gap to optimality is large enough, there is a probability to find a better
solution, resulting in a solution in par with the globally optimal in
$\mathcal{O}(dnk^{2}\log\log k)$ iterations. Lee et al. [11] showed that it is
NP-hard to solve the problem below a multiplicative error of $1.0013$.

To determine a proper $k$ for the data at hand, there are several methods to
compare the result when varying the parameter, such as the elbow method [12]
or the Silhouette method [13]. These methods can help the analyst to determine
which clustering is the most appropriate with their respective objective
function. However, since the above mentioned algorithms are not guaranteed to
find the global optimum for each $k$, it becomes a challenge to compare the
result between different parameter settings.

###  1.4 Introduction to the method and structure of the paper

The main idea that this paper builds on is by rewriting the problem as a low
dimensional concave assignment problem, described in Section 2. Since a
concave objective function attains its minimum at an extreme point of the
bounding feasible set, we may relax the set of binary assignment matrices to
real valued matrices with the same marginal constraints, without changing the
optimal value or solution.

Even though the problem can be formulated in a low dimensional space, the
feasible set in this image space becomes increasingly complex with increasing
$n$. The idea is then to approximate this set with linear constraints where
necessary, for which the problem is solvable in tractable time, see
illustration in Figure 1.

Figure 1: A convex set (ellipse drawn with a solid line) is approximated by
with linear cutting planes tangential to the convex set. A concave objective
function (with level curves described by thin dashed ellipses) attains its
minimum in an extreme point $E$ of the outer linear approximation which is
lower than any value in the ellipse. A new constraint (thick dashed line),
refines the outer approximation by removing a part which contains $E$.

In the procedure, a lower bound of the problem is found by solving the relaxed
problem. The optimal point in the relaxed problem is then used to find an
assignment matrix using linear programming. The least upper bound of the
objective in these visited assignment matrices is then an upper bound of the
problem. In Section 3, we show in the setting of general smooth concave
objective functions that the gap between the upper and lower bounds converge
to zero, hence one globally optimal solution is found.

In Section 4 we introduce methods that accelerate the convergence of the
method, and finally, in Section 5 we show with examples how the method
performs in terms of accuracy and computational complexity.

##  2 Problem formulation and proposed algorithm

###  2.1 Formulation as a low dimensional concave problem

In order to rewrite (1) as a concave assignment problem, we first note that it
can be written as

$\displaystyle\min_{\\{y_{j}\\}_{j=1}^{k}\subset\mathbb{R}^{d},\Gamma\in\mathcal{A}}\quad\sum_{i=1}^{n}\sum_{j=1}^{k}\|x_{i}-y_{j}\|^{2}\Gamma_{i,j},$
(2)

where we let $\mathcal{A}=\\{\Gamma\in\\{0,1\\}^{n\times k},\Gamma{\bf 1}={\bf
1},\Gamma^{T}{\bf 1}\geq{\bf 1}\\}$ be a set of assignment matrices that
assigns each point to a centroid. The objective function

$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{k}\|x_{i}-y_{j}\|^{2}\Gamma_{i,j}$
$\displaystyle=\sum_{i=1}^{n}\|x_{i}\|^{2}+\sum_{j=1}^{k}\left(\sum_{i=1}^{n}\|y_{j}\|^{2}\Gamma_{i,j}-\sum_{i=1}^{n}2\langle
y_{j},x_{i}\rangle\Gamma_{i,j}\right)$
$\displaystyle=c_{0}+\sum_{j=1}^{k}\left(\|y_{j}\|^{2}{\bf 1}^{T}\Gamma
e_{j}-2\langle y_{j},X\Gamma e_{j}\rangle\right)$
$\displaystyle{=c_{0}+\sum_{j=1}^{k}\Big{(}{\bf 1}^{T}\Gamma
e_{j}\|y_{j}-X\Gamma e_{j}/({\bf 1}^{T}\Gamma e_{j})\|^{2}}$
$\displaystyle\qquad\qquad\qquad{-\|X\Gamma e_{j}\|^{2}/({\bf 1}^{T}\Gamma
e_{j})\Big{)}}$ (3)

where $c_{0}=\sum_{i=1}^{n}\|x_{i}\|^{2}$ and
$X=\begin{pmatrix}x_{1},\ldots,x_{n}\end{pmatrix}\in{\mathbb{R}}^{d\times n}$,
and thus the minimizing ${y_{j}}^{\prime}s$ can be expressed explicitly as
$y_{j}=X\Gamma e_{j}/({\bf 1}^{T}\Gamma e_{j})$. By substituting this into
(3), we get that (2) can be reformulated as

$\displaystyle\min_{\Gamma\in\mathcal{A}}\quad c_{0}-\sum_{j=1}^{k}\|X\Gamma
e_{j}\|^{2}/({\bf 1}^{T}\Gamma e_{j}).$ (4)

Next, note that each term in the sum in (4) is a composition of a linear
function and a norm on the form $h(\alpha,\beta):=\|\alpha\|^{2}/\beta$. Since
$h(\alpha,\beta)$ is jointly convex in $\alpha\in{\mathbb{R}}^{n}$ and
$\beta\in{\mathbb{R}}_{+}$ ([14, p.89]), it follows that the objective of (4)
is concave function.

Now, consider the relaxed problem, where the feasible set $\mathcal{A}$ is
extended to its convex hull

$\displaystyle\overline{\mathcal{A}}:=\\{\Gamma\in[0,1]^{n\times k},\Gamma{\bf
1}={\bf 1},\Gamma^{T}{\bf 1}\geq{\bf 1}\\}.$

Since the objective is concave, this does not change the minimum value. We
have thus shown the following proposition.

######  Proposition 2.1.

The k-means problem (2) is equivalent to the concave problem

$\displaystyle\min_{\Gamma\in\overline{\mathcal{A}}}\quad
c_{0}-\sum_{j=1}^{k}\|X\Gamma e_{j}\|^{2}/({\bf 1}^{T}\Gamma e_{j})$ (5)

in the sense that there is a $\Gamma\in\mathcal{A}$ that is minimizes both
problems, and their corresponding minimum values coincide.

######  Remark 2.2.

The space of assignments can be generalized to a case when each cluster has a
least $n_{0}$ points. We would then consider the set of assignment matrices
$\mathcal{A}_{n_{0}}=\\{\Gamma\in\\{0,1\\}^{n\times k},\Gamma{\bf 1}={\bf
1},\Gamma^{T}{\bf 1}\geq n_{0}{\bf 1}\\}$. It is straightforward to generalize
our method to this case.

###  2.2 Relaxation and iterative scheme

Note that by moving all the dependence on $\Gamma$ to the constraints the
problem (5) can be (trivially) reformulated as

$\displaystyle\min_{\begin{subarray}{c}\\{\hat{z}_{j}\\}_{j=1}^{k}\subset{\mathbb{R}}^{d}\\\
\\{n_{j}\\}_{j=1}^{k}\subset{\mathbb{R}},\Gamma\end{subarray}}$ $\displaystyle
c_{0}-\sum_{j=1}^{k}\|\hat{z}_{j}\|^{2}/n_{j}$ (6a) subject to
$\displaystyle\begin{pmatrix}\hat{z}_{j}\\\
n_{j}\end{pmatrix}=\begin{pmatrix}X\Gamma e_{j}\\\ {\bf 1}^{T}\Gamma
e_{j}\end{pmatrix},\;j=1,\ldots,k$ (6b)
$\displaystyle\Gamma\in\overline{\mathcal{A}}.$ (6c)

For convenience of notation we let

$Z=\begin{pmatrix}z_{1}&\ldots&z_{k}\end{pmatrix},\quad
z_{j}=\begin{pmatrix}\hat{z}_{j}\\\ n_{j}\end{pmatrix}\quad\mbox{ and
}\quad\mathcal{X}:=\begin{pmatrix}X\\\ {\bf 1}^{T}\end{pmatrix}$

in which case (6) becomes

$\displaystyle\min_{{Z\in{\mathbb{R}}^{(d+1)\times k}},\Gamma}\;$
$\displaystyle c_{0}-\sum_{j=1}^{k}\|Cz_{j}\|^{2}/(Dz_{j})$ (7a) subject to
$\displaystyle{Z=\mathcal{X}\Gamma}$ (7b)
$\displaystyle\Gamma\in\overline{\mathcal{A}}$ (7c)

where $C:=\begin{pmatrix}I_{d\times d}&0_{d\times 1}\end{pmatrix}$ and
$D:=\begin{pmatrix}0_{1\times d}&1\end{pmatrix}$.

The set
$\mathcal{F}:=\\{\mathcal{X}\Gamma\mid\Gamma\in\overline{\mathcal{A}}\\}$ may
contain exponentially many (in $n$) extreme points and facets seen by counting
the basic feasible solutions of $\overline{\mathcal{A}}$. Therefore, we
consider the relaxation of (7), in terms of the constraints as

$\displaystyle\min_{{Z\in\mathbb{R}^{(d+1)\times k}}}\quad$ $\displaystyle
c_{0}-\sum_{j=1}^{k}\|Cz_{j}\|^{2}/(Dz_{j})$ (8a) subject to
$\displaystyle\langle A_{r},Z\rangle\leq b_{r},r=1,\ldots,N.$ (8b)

Even though (8) is a nonconvex problem, it is low-dimensional and can be
solved when $k$ and $d$ are small. The main approach then builds on
iteratively approximating and refining the feasible set $\mathcal{F}$ using
constraints on the form (8b). To this end, we first select constraints so that
(8b) is an outer approximation of $\mathcal{F}$. Then, we solve (8) which
gives a lower bound of the problem. To refine the lower bound, we find an
assignment matrix which gives an upper bound of the problem and that defines a
cutting plane which refines the approximation of the feasible set. The
detailed steps are described next, and the procedure is described in pseudo
code in Algorithm 1.

To initially construct an outer approximation of $\mathcal{F}$ we consider a
simplex described by the constraints

$\displaystyle\min_{\Gamma\in\overline{\mathcal{A}}}\left(\mathcal{X}\Gamma\right)_{ij}\leq
Z_{ij}\mbox{ for }i=1,...,d+1\mbox{ and }j=1,...,k,$ $\displaystyle\langle{\bf
1}_{(d+1)\times
k},Z\rangle\leq\max_{\Gamma\in\overline{\mathcal{A}}}\langle{\bf
1}_{(d+1)\times k},\mathcal{X}\Gamma\rangle.$ (9)

Geometrically, this simplex is described by lower bounds in every element of
$Z$ and a “diagonal” hyperplane describing the upper bound.

To solve (8), we use a half plane/vertex representation of the polytope (8b)
which effectively can be refined with new linear constraints. This method was
used in [15] to represent polytopes in order to solve a low rank concave
quadratic assignment problem.

Before we continue, we note that the terms in the sum of the objective of (8)
can be formulated using

$\displaystyle f(z_{j}):=-\|Cz_{j}\|^{2}/(Dz_{j}).$

Assuming that the optimal point to (8) is
$Z_{N}=\begin{pmatrix}z_{1}^{N}&\cdots&z_{k}^{N}\end{pmatrix}$, we use the
local gradient of the objective in this point,

$\displaystyle\mathcal{D}_{N}:=\begin{pmatrix}\nabla
f(z_{1}^{N})&\cdots&\nabla f(z_{k}^{N})\end{pmatrix}$ (10)

where $\nabla
f(z)=-\left(2C^{T}Cz/(Dz)-\frac{\|Cz\|^{2}}{(Dz)^{2}}D^{T}\right)$ to define a
cutting plane. In particular, we let the normal vector of the cutting plane,
$A_{N+1}:=\mathcal{D}_{N}$, be the gradient and let

$\displaystyle
b_{N+1}:=\min_{\Gamma\in\overline{\mathcal{A}}}\langle\mathcal{D}_{N},\mathcal{X}\Gamma\rangle,$
(11)

and we let $\Gamma_{N}\in\mathcal{A}$ be an optimal solution to (11). By this
construction, the cutting plane separates $Z_{N}$ from $\mathcal{F}$ and
intersects $\mathcal{F}$, in particular

$\displaystyle\langle\mathcal{D}_{N},\mathcal{X}\Gamma-\mathcal{X}\Gamma_{N}\rangle\geq
0\mbox{ for all }\Gamma\in\overline{\mathcal{A}}.$

To summarize, the procedure has the following properties:

  * •

It finds an assignment matrix $\Gamma_{N}$ which gives an upper bound for the
k-means problem.

  * •

If $Z_{N}\notin\mathcal{F}$, then the cutting plane makes $Z_{N}$ infeasible,
and the constraint is added to (8b).

  * •

If $Z_{N}\in\mathcal{F}$, then the point is optimal and $\Gamma_{N}$ is
optimal to the k-means problem (5).

Algorithm 1 Global k-means algorithm

Input $X\in{\mathbb{R}}^{d\times n}$, $\epsilon>0$ (Define point cloud and
give tolerance level)

$L_{\rm bound}\leftarrow-\infty$, and $U_{\rm bound}\leftarrow\infty$ (Set
lower and upper bounds)

$(A_{r},b_{r})$ for $r=1,\ldots,1+(d+1)k$ from (9) (Set initial constraints)

repeat

$Z_{N}$ $\leftarrow$ Optimal solution to (8) (Solve (8))

$L_{\rm bound}\leftarrow c_{0}-\sum_{j=1}^{k}\|Cz_{j,N}\|^{2}/(Dz_{j,N})$
(Update lower bound)

$\Gamma_{N}$ $\leftarrow$ Optimal solution to (11) (Solve (11))

$\hat{Z}\leftarrow\mathcal{X}\Gamma_{N}$

$U_{\rm bound}\\!\\!\leftarrow\\!\\!\min(U_{\rm
bound},\\!c_{0}\\!-\sum_{j=1}^{k}\\!\|C\hat{z}_{j,N}\|^{2}/(D\hat{z}_{j,N}))$
(Update upper bound)

$(A_{N+1},b_{N+1})\leftarrow$ Optimal solution to (11) (Calculate new
constraints from 11)

$N\leftarrow N+1$ (Update iteration number)

until $U_{\rm bound}-L_{\rm bound}<\epsilon$

##  3 Convergence

The main result considering convergence is presented in the following theorem.

######  Theorem 3.1.

The gap between the upper bound and lower bound in the algorithm converges to
$0$ (if the tolerance is $\epsilon=0$).

###### Proof.

Consider the $N$th iteration. Let $Z_{N}$ be an optimal solution to the
relaxed problem (8), and $\Gamma_{N}$ is an optimal solution to the linearized
problem (11) with corresponding point $\hat{Z}=\mathcal{X}\Gamma_{N}$. Note
that the new constraint is given by

$\displaystyle\langle\nabla F_{Z_{N}},Z-\hat{Z}\rangle\geq 0,$ (12)

where $F(Z)=c_{0}-\sum_{j}\|Cz_{j}\|/D^{T}z_{j}$ is the objective function.
Further, due to concavity of $F$ we have

$\displaystyle F(\hat{Z})\leq F(Z_{N})+\langle\nabla
F_{Z_{N}},\hat{Z}-Z_{N}\rangle.$ (13)

Next, assume that the gap in the objective function between $\hat{Z}$ and
$Z_{N}$ is

$\displaystyle\epsilon_{N}=F(\hat{Z})-F(Z_{N}).$ (14)

Then, by plugging in (13) and (12) into (14) we obtain

$\displaystyle\epsilon_{N}$ $\displaystyle=F(\hat{Z})-F(Z_{N})$
$\displaystyle\leq\langle\nabla F_{Z_{N}},\hat{Z}-Z_{N}\rangle$
$\displaystyle=\langle\nabla F_{Z_{N}},\hat{Z}-Z+Z-Z_{N}\rangle$
$\displaystyle=\langle\nabla F_{Z_{N}},Z-Z_{N}\rangle+\langle\nabla
F_{Z_{N}},\hat{Z}-Z\rangle$ $\displaystyle\leq\langle\nabla
F_{Z_{N}},Z-Z_{N}\rangle$ $\displaystyle\leq\|\nabla
F_{Z_{N}}\|_{2}\|Z-Z_{N}\|_{2}$

where we in the last step have used the Cauchy-Schwarz inequality.

For any iteration number $N+k$ with $\ell>0$, we have that $Z_{N+\ell}$ is
feasible for $\langle A_{N+1},Z\rangle\leq b_{N+1}$, and thus the Euclidean
distance between $Z_{N}$ and $Z_{N+\ell}$ is at least $\epsilon_{N}/\|\nabla
F_{Z_{N}}\|_{2}$. If the gap in the algorithm does not converge to $0$, then
there is an $\epsilon>0$ for which $\epsilon_{N}\geq\epsilon$ for all $N$ and
thus the distance between any two points in the sequence $\\{z_{N}\\}_{N}$ is
bounded from below by $\epsilon/(\max_{Z\in B}\ \|\nabla F_{z}\|)$, where $B$
is the initial bounding simplex for the relaxed problem. However, since the
infinite sequence of points $\\{Z_{N}\\}_{N}$ belong to a bounded set defined
by $B$, there must be a convergent subsequence, which contradicts that there
is a positive lower bound on the distance between any two points.

Since assuming that there is a lower bound $\epsilon>0$ leads to a
contradiction, it must hold that the gap between the upper and lower bound
converges to zero, and thus the solution converges to a global optimum. ∎

##  4 Accelerating methods

In this section we introduce methods that accelerates Algorithm 1. Some
methods are well known in the field of global optimization, and some of the
methods utilize the structure of the k-means problem. All methods involve
additional cutting planes and fits with the algorithm architecture.

###  4.1 One fixed marginal constraint

Since $\Gamma{\bf 1}={\bf 1}$ and $Z=\mathcal{X}\Gamma$ we obtain that
$Z1=\mathcal{X}1$. This reduces the problem with $d+1$ dimensions and can be
implemented as $\langle A_{j},Z\rangle=b_{j}$ where the matrix elements
$A_{j}-e_{j}{\bf 1}^{T}$ and $b_{j}=(\mathcal{X}1)_{j}$.

###  4.2 Symmetry breaking

Symmetry breaking is a known an powerful tool in global optimization, see for
instance [16, 17]. One obvious symmetry is that the ordering of clusters may
be arbitrary. To avoid this, one may consider a fixed but arbitrary linear
ordering of $z_{j}$, namely $a^{T}z_{j}\leq a^{T}z_{j+1}$, which creates $k-1$
constraints. For simplicity, the ordering chosen is $a={\bf 1}$.

###  4.3 Branching

A spatial hyperplane branching can be defined by $B\in\mathbb{R}^{(d+1)\times
k}$ and $0\leq\beta\ll 1$, such that, $\langle B,Z\rangle\leq\beta$ forms one
child node and $\langle B,Z\rangle\geq-\beta$ the other. We can utilize
spatial branching to reduce memory consumption when solving the low
dimensional concave optimization problem (8), by dividing it into two
problems. As our method for solving (8) uses a vertex representation,
branching reduces the number of vertexes we need to store in memory during the
search. The role of $\beta$ is to have a small overlap of the sets to prevent
numerical instability.

Division of the branches was done by diving the set of extreme points in two
parts using the constraint $\langle v,Z\rangle\leq\langle b,v\rangle$ where
$b$ is the mean value of the vertices and $v$ was constructed by analyzing the
second moments of the distribution of extreme points, using singular value
decomposition, SVD.

###  4.4 Constrained centroid positioning

Consider the convex hull of $\\{x_{i}\\}_{i=1}^{n}$, constituted by the subset
of points $\\{\hat{x}_{k}\\}_{k}$. Since the centroids $Y=X\Gamma\oslash
1^{T}\Gamma$ is a convex combination of the data points, they must be included
in the set described by the convex hull, and we could restrict the centroids
to this set. Handling the convex hull is computationally expensive as $n$ and
$d$ increases. Let $S_{i}=\max_{j}(x_{j})_{i}$ denote the largest value in
coordinate $i$ and $s_{i}=\min_{j}(x_{j})_{i}$ the smallest value in
coordinate $i$. A coarse approximation with the bounding box is a suitable
choice,

$\displaystyle Dz_{j}s_{i}\leq(z_{j})_{i}\leq Dz_{j}S_{i},\mbox{ for all
}i=1,\ldots,d.$

###  4.5 Integer constraints

The elements $(z_{j})_{d+1}\in\\{1,\ldots,n-(k-1)\\}$ for $j=1,\ldots,k$,
since these elements contain the number of data points in each cluster.
Therefore, in every iteration additional pruning of the set. That is, if the
extreme points in a branch are $\\{\bar{Z}_{i}\\}_{i}$, we can construct cuts
$\lceil\min_{i}((\bar{z}_{j})_{d+1})_{i}\rceil\leq(z_{j})_{d+1}\leq\lfloor\max_{i}((\bar{z}_{j})_{d+1})_{i}\rfloor$,
so that the bounds are integer. In combination with branching, this gave a
stronger effect in our experiments.

###  4.6 Tight constraints

By exploring some fundamental properties of LP, we can derive an additional
set of valid constraints. A standard LP problem can be written on the form

$\displaystyle\min_{x}\qquad$ $\displaystyle c^{T}x$ subject to $\displaystyle
Ax=b,x\geq 0.$

Suppose $x^{*}$ is a basic feasible solution to the LP, with basis $B$ (the
complement is $B^{\prime}$). Then by the optimality conditions the dual
$y=(A_{B}^{T})^{-1}c_{B}$ and

$s_{B^{\prime}}=c_{B^{\prime}}-A_{B^{\prime}}^{T}y>0.$

Any perturbation in $c_{B^{\prime}}$ that makes $(s_{B^{\prime}})_{k}<0$ for
any element index $k$ is a perturbation that changes the optimal assignment.

The problem (11) can be stated on standard form according to

$\displaystyle x=\begin{pmatrix}\operatorname*{vec}(\Gamma)\\\
x_{s}\end{pmatrix},$ $\displaystyle
c=-\begin{pmatrix}\operatorname*{vec}(\mathcal{X}^{T}A_{N})\\\
0_{k}\end{pmatrix},$ $\displaystyle A=\begin{pmatrix}{\bf 1}_{k}^{T}\otimes
I_{n\times n}&0_{n\times k}\\\ I_{k\times k}\otimes{\bf 1}_{n}^{T}&-I_{k\times
k}\end{pmatrix},$ $\displaystyle b=\begin{pmatrix}{\bf 1}_{n}\\\ {\bf
1}_{k}\end{pmatrix}$

where $x_{s}$ are slack variables for the inequality constraint
$x_{s}^{T}={\bf 1}_{n}^{T}\Gamma-{\bf 1}^{T}_{k}\geq 0$.

A change in the objective in the low dimensional space will change $\partial
c=\operatorname*{vec}(\mathcal{X}^{T}\partial A_{N})$. Thus, there is a closed
form expression of the dual, namely

$\displaystyle s_{B^{\prime}}=V\operatorname*{vec}(A_{N})$

where
$V:=(J_{B^{\prime}}-A_{B^{\prime}}^{T}(A_{B}^{T})^{-1})J_{B})\begin{pmatrix}I_{k}\otimes\mathcal{X}^{T}\\\
0_{(m+1)k,k}\end{pmatrix}$ and $J_{B}$ and $J_{B^{\prime}}$ are selection
matrices for the set $B$ and $B^{\prime}$ respectively, meaning that
$(J_{B})_{i,j}=1$ if and only if $B_{i}=j$. Lets take a subset of the rows in
$V$ denoted $B_{2}$, it is possible to find a vector $t$ such that
$V_{B_{2}}\operatorname*{vec}(t)=0$ and
$V_{B^{\prime}_{2}}\operatorname*{vec}(t)>0$. If this is possible, then
$A_{N}+t$ is an objective for the LP, for which the same $\Gamma_{N}$ is
optimal, but not unique, since we may take an index $i\in B_{2}$ and add
$B^{\prime}_{i}$ to $B$ and remove some other base. Which one is directly
determined by $\Gamma{\bf 1}_{k}={\bf 1}_{n}$, i.e., which point that is moved
from one cluster to another. Thus it is possible to create a set of new
constraints $\partial A_{k}$ by the optimization problem

$\displaystyle\min_{s_{B^{\prime}},\partial A_{k}}\;$
$\displaystyle\begin{pmatrix}{\bf
1}^{T}&0^{T}\end{pmatrix}\begin{pmatrix}s_{B^{\prime}}\\\
\operatorname*{vec}(\partial A_{k})\end{pmatrix}$ subject to $\displaystyle
s_{B^{\prime}}=V\operatorname*{vec}(\partial A_{k})$ $\displaystyle\partial
A_{k}^{T}\partial A_{j}\leq\alpha\mbox{ for }j=1,\ldots,k-1$ $\displaystyle
s_{B^{\prime}}\geq 0.$

The tight constrains are then defined by $A_{N}+\partial A_{j}$. the role of
$\alpha$ is to find new constraints that differs from each other.

###  4.7 Local optimum

Necessary optimality conditions requires that

$\displaystyle\Gamma^{*}=\operatorname*{argmin}_{\Gamma\in\overline{\mathcal{A}}}\langle\mathcal{X}^{T}\mathcal{D^{*}},\Gamma\rangle$

where $\mathcal{D}^{*}$ is the gradient of the objective function 10 in the
points $Z^{*}=\mathcal{X}\Gamma^{*}$. In each iteration a local search by
iterating over $j$

$\displaystyle\Gamma_{j+1}^{*}:=\operatorname*{argmin}_{\Gamma\in\overline{\mathcal{A}}}\langle\mathcal{X}^{T}\mathcal{D}_{j}^{*},\Gamma\rangle$

until convergence can be applied. A fix point with this sequence is not the
same as for the alternating sequence in Lloyds algorithm. However, there is no
need for a distance evaluation between all centroids and points. A tight
constraint surrounding the local optimum can be added to the approximate
cover.

###  4.8 Least squares approximation

Instead of the half plane cut generated by the LP problem (11), one may
consider a least square fitting by finding the point on the projected
assignment matrix closest to the point in the outer approximation by

$\displaystyle\min_{z}\qquad$ $\displaystyle\|z-z_{N}\|_{F}^{2}$ subject to
$\displaystyle z=\mathcal{X}\Gamma$
$\displaystyle\Gamma\in\overline{\mathcal{A}}.$

We denote $\hat{z}$ the optimal argument of the above optimization problem. By
iteratively adding the half plane described by

$\displaystyle\langle z_{N}-\hat{z},z-\hat{z}\rangle\leq 0$

an approximation of the projected assignment matrix is found. Convergence of
an outer half plane approximation of a convex set is well known, by
iteratively applying the separating hyperplane theorem. Briefly, when
$\|\hat{z}-z_{N}\|=0$ the optimal assignment is found. If
$\|\hat{z}-z_{N}\|\geq\epsilon$, there is a half plane separating the point
$z_{N}$ to $\hat{z}$, namely the plane described above because of the Hahn-
Banach theorem. Suppose the distance $\|\hat{z}-z_{N}\|\geq\epsilon$ for all
$N\geq K$, then each point in the infinite sequence has a distance between
them. Hence, the sequence does not contain a convergent subsequence, which
contradicts that the outer approximation is bounded.

##  5 Numerical Results

Here, we present numerical results on the method. The method was implemented
in Matlab, on a standard PC where the polytope connectivity was calculated on
a Nvidia GTX1660 using OpenCL. The LP problem (11) was solved using Gurobi 10
[18].

###  5.1 Performance study

We study a model problem with simulated data by considering samples taken from
three normal distributions $\mathcal{N}(0,\sigma)$,
$\mathcal{N}((0,2),\sigma)$ and $\mathcal{N}((2,0),\sigma)$, see Figure 2.
With $\sigma=1$, this problem has no clear separability of the clusters,
making the problem far more challenging.

Figure 2: A model problem with simulated data. Left: Exact solution to the
k-means problem using the proposed algorithm. Right: Approximate solution of
the problem using k-means++.

####  5.1.1 Performance of accelerating methods

In this section we describe the effect on the accelerating methods when 50
points were taken from the model problem. Results are shown in Table 2. The
effect of utilizing the fixed marginal which reduces the problem by $m+1$
dimensions is implemented in all examples. All experiments were run until the
relative error on the gap $g$ was $10^{-4}$. The example show that the
accelerating methods makes the performance up to 3 times better. Also,
decisions of when during the sequence a strategy is put into practice affects
the overall performance. No branching was performed on this particular
problem, as it comes to use for large scale problems where memory consumption
becomes a bottle neck.

Some observations on this particular problem include

  * •

Tight cuts drive computational cost, and should be used carefully at the very
end surrounding local optima.

  * •

The least squares method complements the LP method for coarse cuts, but is
redundant in this case to the constrained centroid cuts.

As an alternative, a restatement of the problem into a mixed integer nonlinear
problem (MINLP) is as follows:

$\displaystyle\min_{\Gamma,\alpha,y}\;$
$\displaystyle\langle\alpha,\Gamma\rangle$ subject to
$\displaystyle\|x_{i}-y_{j}\|^{2}\leq\alpha_{i,j}$
$\displaystyle\Gamma\in\\{0,1\\}^{n\times k}$
$\displaystyle\alpha\in[0,\max_{i,j}\|x_{i}-x_{j}\|^{2}]^{n\times k}$
$\displaystyle(y_{i})_{j}\in[\min_{l}(x_{l})_{j},\max_{l}(x_{l})_{j}]$
$\displaystyle\;\mbox{ for }j=1,\ldots,d,\mbox{ and }\;i=1,\ldots,k.$

This above problem was implemented in the commercial solver Gurobi 10.
However, it requires more than $10000$ seconds to solve the problem to a
$25\%$ gap, which highlights the problem complexity for solving this with
standard solvers. The results are well aligned with other studies that clearly
show the difficulty of solving k-means by MINLP [19, 20].

Table 1: Scaling performance of the method. Presented values are the relative
gap at termination (rel. gap) and the sum of all branches for the number of
iterations (Iters.), number of constraints at termination (No. constr.),
number of extreme points in the approximate polytope at termination (Extr.
points) and computational time (Comp. time) in seconds on a standard PC.
|  |  |  |  | Proposed method | Gurobi
---|---|---|---|---|---|---
n | k | d | rel. gap | $\sigma$ | Iters. | No. constr. | Extr. points | Branches | Comp. time | Comp. time
50 | 3 | 2 | $10^{-4}$ | 1 | 267 | 366 | 121600 | 1 | 54s |  $>10000$s
500 | 3 | 2 | $10^{-4}$ | 1 | 310 | 407 | 161760 | 1 | 78s | -
5000 | 3 | 2 | $10^{-4}$ | 1 | 419 | 465 | 210856 | 1 | 1873s | -
50 | 3 | 3 | $10^{-3}$ | 1 | 1696 | 13931 | 18502128 | 45 | 6389s | -
50 | 4 | 2 | $10^{-3}$ | 0.1 | 251 | 3583 | 2745616 | 5 | 672s | -
50 | 4 | 2 | $10^{-3}$ | 0.5 | 2381 | 73680 | 52238384 | 150 | 1313s | -
Table 2: Effect of adding various acceleration techniques. The strategies were
also tested to be activated at various gaps. In the last test the strategies
were active for different levels of relative gap, denoted $g$. Abbreviations
are Symmetry breaking (SB), Least squares (LS), Constrained centroid (CC) and
tight local optimum (TO). Presented values are number of iterations (Iters.),
number of constraints at termination (No. constr.) and computational time
(Comp. time) in seconds on a standard PC.
| Iters. | No. | Comp.
---|---|---|---
|  | constr. | time
Original | 546 | 552 | 151s
SB | 406 | 414 | 83s
SB + LS | 189 | 370 | 71s
SB + CC | 293 | 313 | 54s
SB + CC +LS | 150 | 298 | 52s
SB + CC +LS ($g>1$) | 267 | 366 | 54s
+TO ($g<0.01$) |  |  |

####  5.1.2 Cluster separability

The complexity of finding the optimal clustering depends on the separation
between the clusters as described in Table 3. The test was performed on the
model problem with 500 sampled points.

Table 3: Effect on the separability of clusters. With increased separability
the computational effort is reduced significantly.
$\sigma$ | Iters. | No. | Comp.
---|---|---|---
|  | constr. | time
1 (no separability) | 310 | 407 | 78s
0.5 (visible separability) | 96 | 152 | 23s
0.2 (clear separability) | 24 | 72 | 9s

####  5.1.3 Scaling

Here, we describe scaling of our method. As the QP problem has exponential
complexity in $d$ and $k$ this is the bottleneck. The LP scales polynomially
in $n$ having less impact on the computational time and memory consumption.
The branching was performed when the number of extreme points exceeded $5\cdot
10^{5}$ in a branch to match memory constraints on the computer on which the
tests were run. We used the same test problems, and the results are shown in
Table 1 .

###  5.2 MNIST numerals

In this section we compare the global solution of the k-means problem on MNIST
[21] numerals "7" and "9" compared to k-means++. As an underlying distance we
use the Wasserstein distance, and the distance map is then subject to a doubly
stochastic diffusion [22] to reduce noise and to separate intertwined
distributions. Representative low dimensional point clouds preserving the
distances are generated using multidimensional scaling, i.e. with a distance
between numerals $x_{i}$ and $x_{j}$ $d(x_{i},x_{j})$ we create a Euclidean
point cloud representation $d(x_{i},x_{j})^{2}=\|y_{i}-y_{j}\|_{2}^{2}$.
Results in terms of the k-means objective score, Purity and NMI are presented
in Table 4 and the clustering is presented in Figure 3. The example shows that
when the clusters are not well separated, there are close to optimal
assignments that differs significantly in their structure.

Table 4: K-means clustering of 100 examples of the numerals "7" and 100
examples of "9".
| k-means | Purity | NMI
---|---|---|---
| objective |  |
Proposed algorithm | 278.2523 | 0.81 | 0.2985
K-means++ | 281.9968 | 0.67 | 0.0915

Figure 3: Clustering differences using exact solution of the k-means problem
and k-means++. The images show the two most significant dimensions of the
multi dimensional scaling. Left image: Ground truth, middle image: Exact
solution, right image: k-means++. The exact solution tends to follow the
ground truth, whilst the k-means++ has found a local optimum which is not
describing the clusters correctly.

##  6 Discussion

This paper describes a method to globally solve low dimensional k-means
problems. The numerical results indicate that local optimization algorithms
may find local solutions far from the global optimum. For the MNIST test
problem, the global solution achieved a significantly better correspondence
with the intended classification compared to the local method. Keep in mind,
if the data is not well suited for k-means classification, then there are no
guarantees that a global solution gives a better classification.

In order to further strengthen the methodology, the area of polytope
approximations and pruning should be investigated. The linear optimizaton
problem (11) could be further accelerated using Sinkhorn iterations with a
positive dual for the inequality constrained marginal $\Gamma^{T}{\bf
1}\geq{\bf 1}$, requiring a cross over methodology to transfer from an
interior point estimate to a binary extreme point, e.g., by modifying the
ideas in [23]. The branching technique was implemented in series for the
numerical examples. A parallel implementation would increase the performance
linearly.

## References

  * [1] James MacQueen et al.  Some methods for classification and analysis of multivariate observations.  In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281–297. Oakland, CA, USA, 1967\.
  * [2] Stuart Lloyd.  Least squares quantization in PCM.  IEEE transactions on information theory, 28(2):129–137, 1982.
  * [3] David Arthur and Sergei Vassilvitskii.  K-means++ the advantages of careful seeding.  In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027–1035, 2007.
  * [4] Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu.  A local search approximation algorithm for k-means clustering.  In Proceedings of the eighteenth annual symposium on Computational geometry, pages 10–18, 2002.
  * [5] David Sculley.  Web-scale k-means clustering.  In Proceedings of the 19th international conference on World wide web, pages 1177–1178, 2010.
  * [6] Charles Elkan.  Using the triangle inequality to accelerate k-means.  In Proceedings of the 20th international conference on Machine Learning (ICML-03), pages 147–153, 2003.
  * [7] Ankit Aggarwal, Amit Deshpande, and Ravi Kannan.  Adaptive sampling for k-means clustering.  In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 15–28. Springer, 2009.
  * [8] Jiří Matoušek.  On approximate geometric k-clustering.  Discrete & Computational Geometry, 24(1):61–84, 2000.
  * [9] Silvio Lattanzi and Christian Sohler.  A better k-means++ algorithm via local search.  In International Conference on Machine Learning, pages 3662–3671. PMLR, 2019.
  * [10] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward.  Better guarantees for k-means and euclidean k-median by primal-dual algorithms.  SIAM Journal on Computing, 49(4):FOCS17–97, 2019.
  * [11] Euiwoong Lee, Melanie Schmidt, and John Wright.  Improved and simplified inapproximability for k-means.  Information Processing Letters, 120:40–43, 2017.
  * [12] Robert L Thorndike.  Who belongs in the family?  Psychometrika, 18(4):267–276, 1953.
  * [13] Peter J Rousseeuw.  Silhouettes: a graphical aid to the interpretation and validation of cluster analysis.  Journal of computational and applied mathematics, 20:53–65, 1987\.
  * [14] Stephen P Boyd and Lieven Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * [15] Martin Ryner, Jan Kronqvist, and Johan Karlsson.  Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional euclidean spaces.  In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
  * [16] Toby Walsh.  General symmetry breaking constraints.  In International Conference on Principles and Practice of Constraint Programming, pages 650–664. Springer, 2006.
  * [17] Christopher Hojny and Marc E Pfetsch.  Polytopes associated with symmetry handling.  Mathematical Programming, 175(1-2):197–240, 2019.
  * [18] Gurobi Optimization, LLC.  Gurobi Optimizer Reference Manual, 2023.
  * [19] Dimitri J Papageorgiou and Francisco Trespalacios.  Pseudo basic steps: bound improvement guarantees from lagrangian decomposition in convex disjunctive programming.  EURO Journal on Computational Optimization, 6:55–83, 2018.
  * [20] Jan Kronqvist, Ruth Misener, and Calvin Tsay.  Between steps: Intermediate relaxations between big-m and convex hull formulations.  In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 299–314. Springer, 2021.
  * [21] Yann LeCun.  The MNIST database of handwritten digits.  http://yann. lecun. com/exdb/mnist/, 1998.
  * [22] Boris Landa, Ronald R Coifman, and Yuval Kluger.  Doubly stochastic normalization of the Gaussian kernel is robust to heteroskedastic noise.  SIAM journal on mathematics of data science, 3(1):388–413, 2021\.
  * [23] T. Kaijser.  Computing the Kantorovich distance for images.  Journal of Mathematical Imaging and Vision, 9(2):173–191, 1998\.


# SemEval-2020 Task 6: Definition extraction from free text with the DEFT
corpus

Sasha Spala1, Nicholas A Miller1, Franck Dernoncourt2, Carl Dockhorn1
1Adobe Inc., 2Adobe Research
345 Park Ave
San Jose, CA 95110-2704
<EMAIL_ADDRESS>

###### Abstract

Research on definition extraction has been conducted for well over a decade,
largely with significant constraints on the type of definitions considered. In
this work, we present DeftEval, a SemEval shared task in which participants
must extract definitions from free text using a term-definition pair corpus
that reflects the complex reality of definitions in natural language.
Definitions and glosses in free text often appear without explicit indicators,
across sentences boundaries, or in an otherwise complex linguistic manner.
DeftEval involved 3 distinct subtasks: 1) Sentence classification, 2) sequence
labeling, and 3) relation extraction.

##  1 Introduction

Definition extraction as a complex, real-world task is currently an emerging
field of study. Traditional definition extraction approaches mostly rely on
simple, syntactically straight-forward examples with relatively little
variance in vocabulary. Corpora, including the WCL [Navigli et al. (2010] and
ukWaC [Ferraresi et al. (2008], typically consist of “definition sentences”
which follow a standard X is a (type) Y or X, such as Y syntactic structure.
Many also contain definitors [Navigli and Velardi (2010], such as “means”,
“is”, or “is defined by”. We provide a complete review of the existing state
of definition extraction in ?).

##  2 Data

Tag Name |  Description
---|---
Term |  A primary term
Alias Term |  A secondary, less common name for the primary term. Links to a term tag.
Ordered Term |  Multiple terms that have matching sets of definitions which cannot be separated from each other without creating an non-contiguous sequence of tokens. E.g. x and y represent positive and negative versions of the definition, respectively
Referential Term |  An NP reference to a previously mentioned term tag. Typically this/that/these + NP
Definition |  A primary definition of a term. May not exist without a matching term.
Secondary Definition |  Supplemental information that may qualify as a definition sentence or phrase, but crosses a sentence boundary.
Ordered Definition |  Multiple definitions that have matching sets of terms which cannot be separated from each other. See Ordered Term.
Referential Definition |  NP reference to a previously mentioned definition tag. See Referential Term.
Qualifier |  A specific date, location, or condition under which the definition holds
Table 1: Tag schema Relation Name |  Description
---|---
Direct-defines |  Links definition to term.
Indirect-defines |  Links definition to referential term or term to referential definition.
Refers-to |  Links referential term to term or referential definition to definition.
AKA |  Links alias term to term.
Supplements |  Links secondary definition to definition.
Table 2: Relation schema

The DeftEval task provided data from the DEFT corpus for training, development
and testing. Introduced in Spala et al [Spala et al. (2019], the DEFT corpus
is currently the largest and most comprehensive corpus explicitly for
definition extraction. In addition to the typical definition-type sentences
discussed in the introduction, the corpus also contains sentence and “sentence
windows” of wide variance in syntactic and semantic construction. Sentences
for the corpus were retrieved from the open source textbook website cnx.org,
as well as from various 2017 SEC contract filings from the publicly available
US Securities and Exchange Commission EDGAR (SEC) database. For the DeftEval
shared task, participants were only required to use sentences extracted from
textbooks. EDGAR annotations were provided on request, but not required for
participation in the shared task.

The DEFT corpus provides sentence “context windows” for textbook data from
cnx.org to narrow the search space for possible definitions. A context window
is defined as a set of three sentences: one sentence before a sentence
containing a potential term (e.g. a bold word), the main sentence with the
potential term, and one sentence after. Though it is certainly possible that
some definitions may occur further away from the bolded mention of the term,
for the purposes of the shared task, definitions that occur outside of the
three-sentence window around a potential term are out of scope.

The corpus contains 9 different token labels (see Table1), and 5 different
types of relations (see Table2). This expanded annotation schema allows for a
wide range of data collection, as well as a better understanding of “non-
traditional” definition types (i.e. beyond the typical x is a y structure).
With this annotation, it is possible to observe long-distance (e.g. cross-
sentence) term-definition relationships, as well as supplemental definition
content. Term and definition tags in the schema are treated largely similar to
Storrer and Wellinghoff’s definiens and definitor tags, respectively [Storrer
and Wellinghoff (2006]. A term is defined as a primary term in a sentence
which is accompanied by a definition phrase or sentence within the sentence
context window. Terms are most commonly expressed as noun phrases:

> The scientific method is a method of research with defined steps that
> include experiments and careful observation.111https://github.com/adobe-
> research/deft_corpus/blob/master/data/deft_files/dev/t1_biology_0_0.deft

Occasionally, terms may appear as verb phrases or other constituent phrases
(e.g. adjective phrases):

> Many crystals and solutions rotate the plane of polarization of light
> passing through them. Such substances are said to be optically
> active.222https://github.com/adobe-
> research/deft_corpus/blob/master/data/deft_files/dev/t3_physics_1_101.deft

Not including minor tokenization and sentence break fixes made during the
shared task, there were no major modifications to the dataset before use in
the DeftEval task. Complete details on the dataset is discussed in ?).

##  3 DeftEval Task

The DeftEval shared task focused on fostering an expanded understanding of
definition extraction for complex data, while keeping results comparable to
traditional definition extraction tasks. The shared task, which ran from 4
Sept 2019 to 13 March 2020, was comprised of three subtasks: sentence
classification, sequence labeling, and relation extraction.

Participants were provided data in accordance with the DeftEval timeline:

  * •

15 Aug 2019: Practice data released

  * •

4 Sept 2019: Training data released

  * •

19 Feb 2020: Beginning of Subtask 1 and 2 evaluation period, unlabeled test
data for Subtask 1 and 2 released

  * •

1 March 2020: Beginning of Subtask 3 evaluation period, unlabeled test data
for Subtask 3 released

  * •

13 March 2020: End of competition period, labeled test data for all subtasks
released

DeftEval was administered using Codalab Competitions, a free, open-source
platform for machine learning competitions and data challenges. Instructions
for participation, including details about the annotation schema and
information about the evaluation process, were made available during the
practice and training periods of the shared task. All data and scripts were
disseminated through the DEFT Github repository333https://github.com/adobe-
research/deft_corpus, and linked to on the Codalab landing
page444https://competitions.codalab.org/competitions/22759. Inconsistencies in
the data, bug fixes, and updates to tokenization errors were made regularly
throughout the training period as participants surfaced questions and
potential problems with the dataset.

###  3.1 Subtask 1: Sentence classification

In keeping with previous definition extraction tasks, we believed it to be
important that the DeftEval shared task included a sentence classification
subtask. Participants were provided a script555https://github.com/adobe-
research/deft_corpus/blob/master/task1_converter.py to convert the existing
dataset in its sequence-labeling format to individual sentences with a binary
label indicating whether or not the sentence contained a definition. For the
purposes of this subtask, only sentences which contained token sequences
labeled as definition in the annotated data were considered ”definition
sentences”. Sentences containing only secondary definitions were given a 0
label. Unlabeled test data for the evaluation period was provided pre-
converted in the sentence classification format; participants were only
required to predict the label of each sentence at test time.

###  3.2 Subtask 2: Sequence labeling

Because of the nature of the expanded annotation in the DEFT corpus in
comparison to previous definition extraction corpora, we believed it to be
particularly important that the DeftEval shared task include a sequence
labeling task. The DEFT corpus contains a large amount of auxiliary labels not
previously seen in existing corpora, and the ability to reliably extract these
labels could indicate a model with a broader cabability to identify complex
and lengthy definition relationships. Ultimately, we hope for models that
could both extract and pair (as seen in Subtask 33.3) related term and
definition labels together, but given the potential for these two tasks to be
particularly difficult and the novel nature of the DEFT corpus, the tasks were
split into two subtasks for DeftEval.

The default format of the DEFT corpus data is similar to the CoNLL 2003 format
[Tjong Kim Sang and De Meulder (2003] and formatted as BIO data [Ramshaw and
Marcus (1995]. Therefore, participants did not need to convert any of the data
for Subtask 2. At test time, participants were provided sentences where each
line contained a token, source text file, lower char bound and upper char
bound. Participants were required to predict only the appropriate BIO tag.

###  3.3 Subtask 3: Relation Extraction

The final DeftEval subtask focused on extracting individual term-definition
pairs, as well as matching auxiliary labels to their appropriate root. Without
having a precedent for this particular task in the definition extraction
domain, it was difficult to predict the level of difficulty for this task.
Given the nature of existing relation extraction tasks, we expected this task
to be particularly complex.

Participants were again able use the default format of the DEFT data for
training. At test time, participants were provided sentences where each line
contained a token, source text file, lower char bound, upper char bound, BIO
tag, and tag ID. Participants were required to predict both the tag ID of the
sister relation and the relationship tag.

###  3.4 Task Logistics

All participants were required to use the provided data for training, but were
allowed to add additional resources to their training data (e.g. other
definition extraction resources, such as WCL, or general purpose models such
as BERT). Additional hand-labeled definition extraction data, proprietary
datasets, or unpublished data not universally accessible was explicitly
disallowed. Participants were required to use the DEFT data as intended, using
dev and training data only for training and development. Though it was only
made available during the evaluation periods, participants were also informed
that test data was to be used solely for testing purposes.

During the training period, participants were allowed unlimited submissions to
the Codalab practice and training phases. The practice phase evaluated against
the sample ”practice” data, consisting of three ”dummy” files, one for each
subtask. The training phase evaluated against the dev set data. Exact copies
of these evaluation data were provided in the Github repository. Participants
were able to submit as many subtasks together as desired, though the
evaluation process required that all files in a particular subtask be present
for evaluation. In other words, participants must submit all files in the
subtask evaluation set in order to be evaluated.

Evaluation scripts were also made available on the Github repository so that
participants had access to understand and test the evalaution methods.
Participants were encouraged to test their models locally on their own
machines, then compare those results to those provided by the Codalab portal
to ensure the formatting of their submissions were consistent with the Codalab
requirements. Participants were also provided access to sample submissions via
the Github repository for both the practice and training phases.

Each evaluation period ran for 12 days in which participants were able to
submit their results through the Codalab submission process. Because of the
nature of the relation extraction task potentially providing data for the
sequence labeling task, the evaluation periods for Subtask 1 and 2 ran
concurrently for 12 days, followed by the 12 day evaluation period for Subtask
3. Each participant was allowed 5 submissions per subtask, primarily to allow
for any complications in the submission process. The vast majority of
participants who submitted to the evaluation period used all 5 submissions. We
suspect that many participants used these 5 submission attempts strategically
in order to achieve higher results on the test sets, which should be taken
into account for future tasks.

##  4 Shared Task Results

Over the course of the shared task competition period, 279 submissions were
made through the Codalab training phase, with many participants additionally
developing and testing their systems locally. The evaluation periods brought
217 submissions for Subtask 1, 220 for Subtask 2, and 113 for Subtask 3.
Results are based on the evaluation metrics described in Section 3.

Figure 1: Subtask 1 results; 56 participants, 217 total successful submissions

Figure 2: Subtask 2 results; 51 participants, 220 total successful submissions

Figure 3: Subtask 3 results; 27 participants, 113 total successful submissions Rank |  Team Name |  Submission Name |  Reference |  Models
---|---|---|---|---
5 |  ∗ |  davletov-aa |  ?) |  Multi-task BERT
6 |  ACNLP |  caspa |  ?) |  RoBERTa + Stochastic Weight Averaging
12 |  UNIXLONG |  unixlong |  ?) |  Joint classification and sequence labeling pre-trained model with MLP and CRF layer
16 |  Cardiff University |  Shsabah |  ?) |  BERT with two-step fine tuning
18 |  BERTatDE |  zhangh2020 |  ?) |  BERT with BiLSTM + attention
26 |  RGCL |  tharindu |  ?) |  XLNet
32 |  UPB |  andrei.avram |  ?) |  RoBERTa with finetuning
40 |  DSC IIT-ISM |  kpriyanshu256 |  ?) |  BERT with fine-tuned language model
46 |  DeftPunk |  deftpunk |  ?) |  FastText and ELMo embeddings with RNN ensemble
47 |  TüKaPo |  haemanth |  ?) |  Concatenated GloVe and on-the-fly POS embeddings with BiLSTM and 1D-Conv + MaxPool layers
Table 3: Subtask 1 submissions and system descriptions.
∗Team name not specified Rank | Team Name | Submission Name | Reference | Models
---|---|---|---|---
23 | ∗ | davletov-aa |  ?) | BERT
27 | defx | marchbnr |  ?) | CRF tagger
34 | RGCL | tharindu |  ?) | XLNet - large
37 | UPB | andrei.avram |  ?) | RoBERTa + CRF with finetuning
Table 4: Subtask 2 submissions and system descriptions.
∗Team name not specified Rank | Team Name | Submission Name | Ref | Models
---|---|---|---|---
1 | UNIXLONG | unixlong |  ?) | BERT + hand crafted rules
4 | ACNLP | caspa |  ?) | Random Forest
Table 5: Subtask 3 submissions and system descriptions.

Participants in DeftEval 2020 used a various array of methods for the three
subtasks. For Subtasks 1 and 2 (see Tables 3 and 4), many participants opted
simply to use a pre-trained language model, especially BERT, RoBERTa, and
XLNet (see ?), ?), ?), ?), ?), and ?)). Other implementations incorporated
various LSTM layers in addition to the use of BERT or other transformer
architecture (see ?)).

Participants were also particularly interested in multi-task solutions for
Subtasks 1 and 2, to varying degrees of success (see ?), ?), ?)). ?) used pre-
trained embeddings, then ”projected the contextualized embeddings generated by
the RoBERTa model in three vectors”, making predictions for all three subtasks
with a cohesive architecture.

Some “classic” neural architectures were also used in participant submissions
to Subtask 1, including ?)’s LSTM, RNN, and “hybrid” CNN solution, which
leverages “the implicit local feature-extraction performed by the
convolutional layers to refine the final representations passed to the
reccurant layer, which accounts for global features.” ?) also used CNN and RNN
methods on Subtask 1, in addition to other pretrained architectures.

Subtask 3 submissions (see Table 5) were generally more simple in nature,
perhaps due to the issues discussed in Section 5.2. ?) used a pre-trained BERT
model with some rule-based layers, and ?) used a random forest approach with
additional post-processing.

In addition to an array of architectures, DeftEval also sparked conversation
around the annotation schema. ?) point out that the complexity of the schema
make this task, as expected, more difficult than previous definition
extraction tasks. They also note that some annotations conflict with each
other in the training and test sets, which may be due to the nature of the
schema, as well as the complicated content of the documents annotated. We
recognized this issue, and recommend that future definition extraction tasks
and tasks using the DEFT data consider this. Others mentioned they found that
their initial model explorations came up short; ?) mention that “owing to the
complexity of the DEFT corpus” their “syntactically aware neural networks”
performed lower than expected.

Overall, participants employed a variety of different models, especially those
based on pre-trained transformer architectures for Subtasks 1 and 2 and more
“classic” approaches for Subtask 3. Participants also pointed out
discrepancies and issues with the source dataset, which will be accounted for
in future work.

##  5 Complications

###  5.1 Ammendments to the DEFT Corpus

The source data for DEFT was extracted by an automatic script that collected
and sentence tokenized content from cnx.org. While modern automatic
tokenization methods generally work well in clean environments, content
scraped from cnx.org often unintentionally includes raw urls, incorrectly
parsed text, and errant html code. Because of this, the tokenization process
for the textbook data was particularly error prone. Though our annotators and
developers spent significant time manually adjusting tokenization errors, many
still existed at the time of release on Github. Many participants discovered
these tokenziation errors during training, which were then verified and fixed
via Github issues. Because of the mixed nature of the source problem for
tokenization errors, many caused incorrect sentence tokenization, which in
turn meant that the actual number of sentences in the corpus was different
from the reported number in [Spala et al. (2019]. With the existing
tokenziation fixes at publication time, the textbook corpus contains 16056
sentences (695627 tokens) and 9439 2-3 sentence context windows.

###  5.2 Subtask 3 difficulty

In organizing Subtask 3, we believed the task of matching term-definition
pairs to be particularly difficult, especially considering the number of
additional possible tags in the DEFT corpus. Given the precedence of previous
performance on other more constrained relation extraction tasks (see also ?),
?), ?), etc.), we predicted this task would see mostly low performing scores.

However, participants in the subtask received a median F1 score of 0.9043,
with 16 of the 27 participants scoring above 0.9. Upon further inspection, we
realize this is due to the narrow search space of the three-sentence context
windows. In designing the subtasks, we decided to keep the context windows in
the test set so that the format of the data remained the same between released
training data and test data and to minimize confusion for an already
complicated task. Unfortunately, most context windows only include one set of
term, definition, and matching auxiliary tags, meaning that this task was in
fact particularly easy. F1 scores of 1 and near 1 make sense given the fact
that models had to predict scenarios which in many cases only had one possible
answer. Only cases that had more than one term-definition pair had a search
space larger than 1.

We recommend that future iterations of this particular task provide sentences
in context with the entire document. Though this does not work with the
current format of the DEFT corpus, providing annotated data in context with
the rest of the source textbook is a trivial task. While context windows only
show the range of three sentences and possible distance between term-
definition pairs would remain within those three sentences, providing the full
context of the textbook would mean that models would have to discern term-
definition pairs that cross context windows or appear in neighboring
sentences. Future tasks may also consider combining Subtasks 2 and 3 in order
to create a more comprehensive and challenging task overall.

###  5.3 Concurrent subtask evaluation periods

The evaluation periods for Subtasks 1 and 2 were scheduled to run concurrently
in order to maximize the amount of time alloted for each subtask without
extending the official SemEval evaluation period and to account for the data
needs of Subtask 3. While Codalab’s interface allowed for scheduling of two
separate phases which had concurrent dates, the implementation in fact only
allows for one phase. As a solution, we merged the two subtask evaluation
phases into one phase which accepted both subtasks’ submissions.
Unfortunately, this also meant that individuals were now only provided 5 total
submissions for both subtasks. To handle this, participants were instructed to
complete submissions for their Subtask 1 evaluation first, then contact the
task organizers to open additional submissions for Subtask 2 evaluation,
keeping their best scoring Subtask 1 results in their submission files so that
both Subtask 1 and Subtask 2 scores would be available on the leaderboard.
Participants were warned that if their submissions for Subtask 1 changed with
their Subtask 2 data after their 5 alloted submissions, the results would be
removed and they would be subject to removal from the leaderboard.

We recommend future tasks with multiple subtasks using Codalab to either run
these subtasks on separate, non-overlapping dates, or to provide the total
number of submissions needed for both subtasks in the phase instructions, and
remove any submissions that exceed the alloted submissions for the individual
subtasks.

##  6 Conclusion

Overall, we believe the DeftEval shared task was a successful first
exploration of definition extraction with the DEFT corpus. With more than 400
submissions and 149 registered participants, definition extraction as a
complex, real-world task is clearly of interest to many. We believe that the
results from this shared task provide a baseline for expectations for more
complicated definition extraction tasks.

Though this task does not test a production-ready or real-life scenario, where
models may have to predict term-definition pairs in a large document or in a
wider context, the task does provide an initial look at how models perform on
broad, non-standard definition extraction annotations. We recommend that
future iterations of this task pay close attention to the effect of the DEFT
corpus’ three sentence context windows at test time, especially as it relates
to the differences between an artificially narrow search space and documents
“in the wild”. We also recommend that future research includes a critical
examination of conflicting annotations in the DEFT corpus.

Overall, we believe DeftEval has surfaced questions and research directions
relevant to expanding definition extraction into more complicated linguistic
environments, where data is particularly messy and the natural language it
stems from is particularly complex. DeftEval provided a launching point for
the exploration of this type of problem in definition extraction, proved the
field interest for such a task, and laid groundwork for future iterations of
definition extraction tasks.

## References

  * [Avram et al. (2020]  Andrei-Marius Avram, Dumitru-Clementin Cercel, and Costin Chiru.  2020\.  Upb at semeval-2020 task 6: Pretrained language models for definition extraction.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Caspani et al. (2020]  Fabien Caspani, Pirashanth Ratnamogan, Mathis Linger, and Mhamed Hajaiej.  2020\.  Cnlp at semeval 2020 task 6: A supervised approach for definition extraction.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Davletov et al. (2020]  Adis Davletov, Alexander Shatilov, Nikolay Arefyev, Denis Gordeev, and Alexey Rey.  2020\.  Multi-task learning for definition extraction.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Ferraresi et al. (2008]  Adriano Ferraresi, Eros Zanchetta, Silvia Bernardini, and Marco Baroni.  2008\.  Introducing and evaluating ukwac, a very large web-derived corpus of english.  01\.
  * [Hübner et al. (2020]  Marc Hübner, Christoph Alt, Robert Schwarzenberg, and Leonhard Hennig.  2020\.  marchbnr at semeval-2020 task 6: Joint extraction of concepts and relations for definition extraction.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Jeawak et al. (2020]  Shelan Jeawak, Luis Espinosa-Anke, and Steven Schockaert.  2020\.  Cardiff university at semeval-2020 task 6: Fine-tuning bert for domain-specific definition classification.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Kannan and Ponnusamy (2020]  Madeeswaran Kannan and Haemanth Santhi Ponnusamy.  2020\.  Ui at sem-eval 2020 task 6 : Definition mining.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Lin et al. (2016]  Yankai Lin, Shiqi Shen, Zhiyuan Liu, Huanbo Luan, and Maosong Sun.  2016\.  Neural relation extraction with selective attention over instances.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2124–2133.
  * [Navigli and Velardi (2010]  Roberto Navigli and Paola Velardi.  2010\.  Learning word-class lattices for definition and hypernym extraction.  In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, ACL ’10, pages 1318–1327, Stroudsburg, PA, USA. Association for Computational Linguistics.
  * [Navigli et al. (2010]  Roberto Navigli, Paola Velardi, and Juana Ruiz-MartÃnez.  2010\.  An annotated dataset for extracting definitions and hypernyms from the web.  In Proceedings of the International Conference on Language Resources and Evaluation, LREC 2010, 01.
  * [Ramshaw and Marcus (1995]  Lance Ramshaw and Mitch Marcus.  1995\.  Text chunking using transformation-based learning.  In Third Workshop on Very Large Corpora.
  * [Ranasinghe et al. (2020]  Tharindu Ranasinghe, Alistair Plum, Constantin Orasan, and Ruslan Mitkov.  2020\.  Rgcl at semeval-2020 task 6: Neural approaches to definitionextraction.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Shen and Huang (2016]  Yatian Shen and Xuan-Jing Huang.  2016\.  Attention-based convolutional neural network for semantic relation extraction.  In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 2526–2536.
  * [Singh et al. (2020]  Aadarsh Singh, Priyanshu Kumar, and Aman Sinha.  2020\.  Dsc iit-ism at semeval-2020 task 6: Boosting bert with dependencies for definition extraction.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Soboleva and Kaparina (2020]  Anna Soboleva and Jekaterina Kaparina.  2020\.  Deftpunk at semeval-2020 task 6: using rnn-ensemble for the sentence classification.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Sorokin and Gurevych (2017]  Daniil Sorokin and Iryna Gurevych.  2017\.  Context-aware representations for knowledge base relation extraction.  In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1784–1789, Copenhagen, Denmark, September. Association for Computational Linguistics.
  * [Spala et al. (2019]  Sasha Spala, Nicholas A. Miller, Yiming Yang, Franck Dernoncourt, and Carl Dockhorn.  2019\.  DEFT: A corpus for definition extraction in free- and semi-structured text.  In Proceedings of the 13th Linguistic Annotation Workshop, pages 124–131, Florence, Italy, August. Association for Computational Linguistics.
  * [Storrer and Wellinghoff (2006]  Angelika Storrer and Sandra Wellinghoff.  2006\.  Automated detection and annotation of term definitions in german text corpora.  In Proceedings of the Conference on Language Resources and Evaluation (LREC).
  * [Tjong Kim Sang and De Meulder (2003]  Erik F. Tjong Kim Sang and Fien De Meulder.  2003\.  Introduction to the conll-2003 shared task: Language-independent named entity recognition.  In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003 - Volume 4, CONLL ’03, page 142–147, USA. Association for Computational Linguistics.
  * [Xie et al. (2020]  ShuYi Xie, Jian Ma, Haiqin Yang, Jiang Lianxin, Mo Yang, and Jianping Shen.  2020\.  Unixlong at semeval-2020 task6: A joint model for definition extraction.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.
  * [Zhang and Ren (2020]  Huihui Zhang and Feilang Ren.  2020\.  Bertatde at semeval-2020 task 6: Extracting term-definition pairs in free text using pre-trained model.  In Proceedings of the 14th International Workshop on Semantic Evaluation, Barcelona, Spain, December.