# Solving the Turbine Balancing Problem using Quantum Annealing

Arnold Unterauer  0009-0009-6758-1093 Aqarios GmbHPrinzregentenstraße
120MunichBavariaGermany81677<EMAIL_ADDRESS>,  David Bucher
0009-0002-0764-9606 Aqarios GmbHPrinzregentenstraße
120MunichBavariaGermany81677<EMAIL_ADDRESS>,  Matthias Knoll
0009-0007-2767-7969 Aqarios GmbHPrinzregentenstraße
120MunichBavariaGermany81677<EMAIL_ADDRESS>,  Constantin
Economides  0009-0004-1022-7249 Aqarios GmbHPrinzregentenstraße
120MunichBavariaGermany81677<EMAIL_ADDRESS>,  Michael
Lachner  0009-0008-6874-8329 Aqarios GmbHPrinzregentenstraße
120MunichBavariaGermany81677<EMAIL_ADDRESS>,  Thomas Germain
0009-0007-0289-1686 MTU Aero Engines AGDachauer Straße
665MunichBavariaGermany80995<EMAIL_ADDRESS>,  Moritz Kessel
0009-0002-3423-6532 MTU Aero Engines AGDachauer Straße
665MunichBavariaGermany80995<EMAIL_ADDRESS>,  Smajo Hajdinovic
0009-0004-0381-1957 MTU Aero Engines AGDachauer Straße
665MunichBavariaGermany80995<EMAIL_ADDRESS>and  Jonas Stein
0000-0001-5727-9151 Aqarios GmbHPrinzregentenstraße
120MunichBavariaGermany81677<EMAIL_ADDRESS>
(2024)

###### Abstract.

Quantum computing has the potential for disruptive change in many sectors of
industry, especially in materials science and optimization. In this paper, we
describe how the Turbine Balancing Problem can be solved with quantum
computing, which is the NP-hard optimization problem of analytically balancing
rotor blades in a single plane as found in turbine assembly. Small yet
relevant instances occur in industry, which makes the problem interesting for
early quantum computing benchmarks. We model it as a Quadratic Unconstrained
Binary Optimization problem and compare the performance of a classical rule-
based heuristic and D-Wave Systems’ Quantum Annealer Advantage_system4.1. In
this case study, we use real-world as well as synthetic datasets and observe
that the quantum hardware significantly improves an actively used heuristic’s
solution for small-scale problem instances with bare disk imbalance in terms
of solution quality. Motivated by this performance gain, we subsequently
design a quantum-inspired classical heuristic based on simulated annealing
that achieves extremely good results on all given problem instances,
essentially solving the optimization problem sufficiently well for all
considered datasets, according to industrial requirements.

Quantum Computing, Quantum Annealing, Aerospace, Turbine Balancing Problem

††journalyear: 2024††copyright: acmlicensed††conference: Genetic and
Evolutionary Computation Conference; July 14–18, 2024; Melbourne, VIC,
Australia††booktitle: Genetic and Evolutionary Computation Conference (GECCO
’24 Companion), July 14–18, 2024, Melbourne, VIC, Australia††doi:
10.1145/3638530.3664107††isbn: 979-8-4007-0495-6/24/07††ccs: Hardware Quantum
computation††ccs: Mathematics of computing Combinatorial optimization

##  1\. Introduction

The Turbine Balancing Problem (TBP) is an NP-hard combinatorial optimization
problem (Amiouny, 1993) central to the assembly process of turbines. It
describes the problem of assigning the positions of a set of blades to fixed
positions (called _slots_ in the remainder of this paper) of the rotor disk or
hub to minimize the imbalance resulting from differently weighted blades
caused by imperfect fabrication. _Static imbalance_ , i.e., any deviation from
the turbine’s center of gravity to the axis of rotation, causes vibrations and
stress on the bearings and thus shortens the effective lifespan of the
turbine. In practice, manufacturers typically compensate this imbalance by
adding weights to the turbine fan, which is also called _static balancing_
(Anonymous, 1990). As any additional weight is undesirable in aircraft
engines, and to reduce time spent in the balancing task, many heuristic
approaches to the TBP have been developed (Amiouny et al., 2000; Mason and
Rönnqvist, 1997; Choi and Storer, 2004; Sun et al., 2021).

A less investigated case is the bare imbalance of the rotor disk, which can
significantly contribute to the resulting imbalance. Many actively utilized
heuristics must be explicitly extended to account for it. In practice, these
considerations demand for time consuming, manual adjustments which in turn
slow down the manufacturing process and hence increase costs. Moreover, nearly
all employed TBP solvers are focused on fast runtime, as this problem
typically needs to be solved with real-time performance to not slow down the
production process. However, as the number of blades on a turbine increase,
existing heuristic approaches often struggle to provide sufficiently good
solutions (i.e., assignments that do not necessitate subsequent static
balancing) (Amiouny et al., 2000), especially when including the imbalance of
the bare rotor disk.

An emerging technology that has shown the potential to solve optimization
problems advantageously compared to known heuristics is quantum computing
(Denchev et al., 2016; Ebadi et al., 2022; Albash and Lidar, 2018). Exploiting
the richer, efficient algorithmic toolset provided by the laws of quantum
mechanics, existing quantum computers like _Quantum Annealers_ already allow
to solve small real world optimization problem instances. A key benefit of
using a quantum optimization approach like _Quantum Annealing_ (QA) (which is
the algorithmic procedure a Quantum Annealer executes) is its flexibility in
regards to runtime: The longer it can run, the better the results will
generally get. The combination of this feature with the prospect of
potentially better solution quality motivates us to investigate the
performance of quantum optimization techniques for solving the TBP.

Our contributions to this performance evaluation are summarized in the
following:

  * •

A Quadratic Unconstrained Binary Optimization (QUBO) formulation of the TBP
while considering a possible imbalance of the bare disk, being the necessary
input for Quantum Annealers.

  * •

A case study evaluating the performance of an industrially employed, classical
rule-based heuristic (described in Sec. 3), Qbsolv, and the D-Wave
Advantage_system4.1 Quantum Annealer.

  * •

The development of a quantum-inspired classical heuristic based on simulated
annealing.

The following sections are structured into five parts. Sec. 2 shows how QUBO
problems can be solved on Quantum Annealers. Sec. 3 describes the process of
formulating the TBP in QUBO form. Sec. 4 introduces our novel quantum-inspired
solver. Sec. 5 displays the conducted experiments and interprets the results.
Sec. 6 ultimately concludes our findings.

##  2\. Background

In this section, we introduce the mechanics underlying QA and how formulating
an optimization problem as Quadratic Unconstrained Binary Optimization (QUBO)
helps with solving it on a quantum computer.

The _adiabatic theorem_ in quantum mechanics states that whenever one
Hamiltonian transitions to another Hamiltonian, the physical system remains in
the instantaneous ground state, as long as it was prepared in the ground state
of the initial Hamiltonian and the evolution happens sufficiently slowly (Born
and Fock, 1928). This is essentially the basis of Adiabatic Quantum
Computation (AQC), the underlying computation paradigm of Quantum Annealing
(QA), which differs fundamentally from the standard gate-based quantum
computing model, by conducting time evolution continuously rather than
discrete. AQC starts with a Hamiltonian whose ground state can typically be
prepared easily, e.g., the $H_{I}=-\sum_{i}X_{i}$ with the ground state
$\ket{+}$. Here $X_{i}$ and in the following $Z_{i}$ denote the Pauli
$\sigma_{x}$ and $\sigma_{z}$ operators acting on the qubit with index $i$. In
AQC, this Hamiltonian now undergoes a slow change towards an Ising spin-glass
Hamiltonian (Farhi et al., 2001), which is described in Eq. 1.

(1) $\displaystyle H_{P}=-\sum_{i}h_{i}Z_{i}-\sum_{i,j}J_{ij}Z_{i}Z_{j},$

so that the Hamiltonian describing the time evolution has the form
$H(t)=(1-t)H_{I}+tH_{P}$, where $t\in[0,1]$. Given that the evolution is slow
enough such that the adiabatic theorem holds, we are guaranteed to arrive in
the ground state of $H_{P}$. As $H_{P}$ is strictly diagonal, the ground state
will not be entangled and can be expressed solely through the $z$-basis. Thus,
$H_{P}$ is purely classical and can also be described through the classical
spin values $Z_{i}\rightarrow s_{i}\in\\{-1,+1\\}$.

A convenient property of the Ising spin-glass problem is, that finding its
ground state is generally NP-hard (Barahona, 1982). Therefore, mapping various
hard problems to the Ising model and running QA emerges as a viable
optimization technique. Conveniently, the classical Ising spin-glass is
isomorphic to QUBO via the mapping $s_{i}=2x_{i}-1$, where $x_{i}$ are the
binary variables of the QUBO, i.e.,
$\operatorname*{arg\,min}_{x\in\left\\{0,1\right\\}^{n}}x^{\top}Qx$ where
$Q\in\mathbb{R}^{n\times n}$. Due to its often more convenient $0/1$ encoding,
QUBO has developed to a standard for specifying optimization problems for QC
and many optimization problems have already been formulated in that way
(Glover et al., 2022; Lucas, 2014).

Since today’s hardware is typically error-prone and one has to perform fast
time evolution in order not to lose information to state decoherence, the
final state will not fully be in the ground state and the optimal solution is
merely obtained probabilistically (Bapst et al., 2013). Therefore, instead of
running QA once, we repeatedly sample from the final state and pick the best
outcome.

QA also inspired the Quantum Approximate Optimization Algorithm (QAOA) (Farhi
et al., 2014), which essentially is a timestep-parameterized Trotterization of
the annealing process. This discretization is necessary to conduct the AQC-
based quantum optimization in the quantum gate-model. Most notably, quantum
gate-based computation models are already capable of solving higher-order
problems beyond the quadratic realm (so called _Polynomial_ Unconstrained
Binary Optimization (PUBO)), as the therefore necessary multi-qubit
interactions can be decomposed into single- and two-qubit gates. This has
shown promising performance, even for naturally quadratic problems like the
TSP, as specific space-efficient binary encodings can increase the order of
the objective function as opposed to the more widespread one-hot encodings
(Salehi et al., 2022; Stein et al., 2023).

##  3\. Problem Formulation

The problem of placing $N$ blades in $N$ slots, such that the overall
imbalance of the turbine assembly is minimized, is an assignment problem. We
want to find an optimal assignment
$\sigma:\\{1,\dotsc,N\\}\rightarrow\\{1,\dotsc,N\\}$, such that the distance
$d$, of the center of mass and center of rotation, is minimal. Of course, we
can only place a single blade in a certain slot, i.e., the assignment has a
permutation character, therefore, $\sigma\in S_{N}$, where $S_{N}$ denotes the
symmetric group of degree $N$.

In our problem formulation, we assume that the blades are placed perfectly on
the same plane of rotation, i.e., we restrict ourselves to a two-dimensional
version of the problem, as the three dimensional version would significantly
complicate the cost function and hence exceed the pursued proof of concept.
Furthermore, similar to (Kirkpatrick et al., 1983), we do not contemplate the
inertial characteristics of the single blades but design the fans as point
masses $m_{i}$ located at a constant radius $r>0$. Without loss of generality,
we set $r=1$.

The slots are spread around the central disk in equidistant angular steps,
i.e., $\Delta\phi=\frac{2\pi}{N}$. Without loss of generality, we can assume
that the first slot is positioned at angle $\phi_{1}=0$. The subsequent
positions can then be computed as follows

(2) $\displaystyle\phi_{j}=(j-1)\Delta\phi=\frac{2\pi(j-1)}{N}\quad\forall
j\in\\{1,\dotsc,N\\}.$

The central disk on which the blades are mounted will also have an bare disk
imbalance due to inaccuracies in manufacturing. The imbalance can be described
by its $x-$ and $y-$components through $\mathbf{y}\in\mathbb{R}^{2}$.
Alternatively, it may also be referred to in polar coordinates as angle
$\phi_{0}$ with mass $m_{0}$.

Figure 1. Visualization of placing a blade at a certain angle on the disk. The
added imbalance (blue arrow) can be split into $x$\- and $y$-components (red
and green arrows, respectively).

Defining that the center of rotation is at the origin $(0,0)^{\top}$, the
distance of the center of mass from the origin without any blades attached is
$\|\mathbf{y}\|_{2}$, where $\|\cdot\|_{2}$ is the Euclidian norm. When
mounting blade $i$ with mass $m_{i}$ at slot $j$, i.e., angle $\phi_{j}$, the
distance becomes

(3) $\displaystyle d=\left\|\mathbf{y}+m_{i}\begin{pmatrix}\cos\phi_{j}\\\
\sin\phi_{j}\end{pmatrix}\
\right\|_{2}=\|\mathbf{y}+m_{i}\mathbf{z}_{j}\|_{2}.$

A visualization of the above quantity can be seen in Fig. 1. Considering all
blades placed according to the assignment $\sigma$, the objective quantity can
be expressed as follows

(4) $\displaystyle d$
$\displaystyle=\left\|\mathbf{y}+\sum_{i=1}^{N}m_{i}\mathbf{z}_{\sigma(i)}\right\|_{2},$

and since $\mathbf{z}_{i}^{\top}\mathbf{z}_{j}=\cos(\phi_{i}-\phi_{j})$ by
trigonometric identities, we can simplify the above expression:

(5)
$\begin{split}d^{2}=m_{0}^{2}&+2m_{0}\sum_{i=1}^{N}m_{i}\cos(\phi_{0}-\phi_{\sigma(i)})\\\
&+\sum_{i,j=1}^{N}m_{i}m_{j}\cos(\phi_{\sigma(i)}-\phi_{\sigma(j)}).\end{split}$

Thus the overall optimization of finding the best placement of the blades is
described by the following problem

(6) $\displaystyle\sigma^{*}=\operatorname*{arg\,min}_{\sigma\in
S_{N}}d^{2}(\sigma),$

since squaring is monotonic for positive numbers and per definition $d>0$,
choosing the linear or squared distance does not make a difference. However,
the squared distance is easier to translate into QUBO formalism, as we will
see in the next section.

Figure 2. Total imbalance of the solutions from different solvers: The
resulting imbalances from the placement of all blades on the disk are shown.
This comparison includes the heuristic, D-Wave QPUs, custom simulated
annealing (here denoted as Imbalance SA) and D-Wave’s Qbsolv with simulated
annealing (from left to right).

###  3.1. QUBO mapping

The TBP has already been transformed into QUBO in (Mason and Rönnqvist, 1997),
however, this work did not contemplate the bare disk imbalance. We will
present a formulation including the bare disk imbalance in the following.

Likewise to other permutation-based optimization problems, like the Travelling
Salesperson Problem (TSP) with known QUBO formulations (Lucas, 2014), we
choose a one-hot-encoding basis using $N^{2}$ binary variables. Instead of
considering cities and positions in the cycle as in the TSP, we consider
blades with mass $m_{i}$ attached to slots at angle $\phi_{j}$. The binary
variables $x\in\\{0,1\\}^{N\times N}$ encode whether blade $i$ is actually
attached to slot $j$, i.e., $x_{ij}=1$. Therefore, the optimization objective
from Eq. 5 turns into

(7)
$\begin{split}H(x)&=2m_{0}\sum_{i=1}^{N}m_{i}\sum_{j=1}^{N}x_{ij}\cos(\phi_{0}-\phi_{j})\\\
&+\sum_{i,k=1}^{N}m_{i}m_{j}\sum_{j,\ell=1}^{N}x_{ij}x_{k\ell}\cos(\phi_{j}-\phi_{\ell}),\end{split}$

and the solution to $\operatorname*{arg\,min}_{x}H(x)$ encodes the perfect
best mapping of blades. However, so far, the one-hot constraints of the
encoding are not considered.

Of course, the above expression can also be written in classical QUBO
formalism by $H(x)=x^{\top}Qx$, with $Q\in\mathbb{R}^{N^{2}\times N^{2}}$. To
do so, one has to transform the binary variables into an $N^{2}$ dimensional
vector and introduce the matrix
$q=[m_{1}\mathbf{z}_{1}\;m_{2}\mathbf{z}_{1}\cdots
m_{N}\mathbf{z}_{N}]\in\mathbb{R}^{2\times N^{2}}$. Then the QUBO matrix of
the Hamiltonian (as defined in equation 7) looks like

(8) $\displaystyle Q=q^{\top}q+2\operatorname*{diag}(\mathbf{y}^{\top}q).$

###  3.2. Constraints

The one-hot constraints can be enforced by introducing Hamiltonians that
penalize violations of the constraint. In order for $x$ to represent a
permutation matrix, each row and column can only contain a single 1, i.e., one
blade can only be positioned at one slot and one slot can only hold one blade.
Therefore, the Hamiltonian $H_{C}(x)$ is employed, as defined in equation 9:

(9)
$\begin{split}H_{C}(x)=\sum_{i=1}^{N}\lambda_{1}^{(i)}\left(\sum_{j=1}^{N}x_{ij}-1\right)^{2}\\\
+\lambda_{2}\sum_{j=1}^{N}\left(\sum_{i=1}^{N}x_{ij}-1\right)^{2},\end{split}$

Using $H_{C}(x)$, every bit-combination that deviates from the one-hot
constraint receives a penalty. The penalty factors
$\lambda_{1}^{(i)}\in\mathbb{R}$ and $\lambda_{2}\in\mathbb{R}$ have to be
chosen such that the energy gain in $H$ by violating a constraint is absorbed
by the penalty: In the case of $\lambda_{1}^{(i)}$, the penalty term has to be
at least $\lambda_{1}^{(i)}>2m_{0}m_{i}+m^{2}_{i}$ in order to ensure that no
blade will be placed more than once. Here $\lambda_{1}^{(i)}$ needs to exceed
the maximum gain that can be acquired by inserting a blade twice, which arises
if the second blade is assigned to the opposing slot to the first blade:
$-2m_{0}m_{i}-m_{i}^{2}$. In order to guarantee that each slot only contains a
single blade, $\lambda_{2}$ is required to be at least
$\lambda_{2}>\max_{i}(2m_{0}m_{i}+m_{i}^{2})$. This will ensure that even if
the heaviest blade is positioned twice, which would yield a maximum gain of
$-\max_{i}2m_{0}m_{i}+m_{i}^{2}$, the hard constraint remains valid. In our
experiments, we set the penalty factors to ten times the minimum requirement
based on empirical preliminary tests that have indicated better performance
with heavier weighted penalty terms.

Combining all discussed parts, the complete optimization problem can be
written as

(10) $\displaystyle\operatorname*{arg\,min}_{x\in\\{0,1\\}^{N\times
N}}H(x)+H_{C}(x).$

##  4\. Custom Simulated Annealing Solver

Due to the one-hot encoding utilized in our QUBO, it is possible that invalid
solutions may occur which do not conform to the physically realizable states.
In order to prevent this from happening, we defined the hard constraints in
Eq. 9 to ensure compliance. As optimization algorithms mostly find suboptimal
results in practice, these constraints may still not satisfied, even though
valid solutions yield provably better results. Therefore, we propose an
approach to avoid this issue, which we base on the established meta-heuristic
simulated annealing. This approach can be tailored towards the optimization of
solutions while restricting the solution space to valid solutions. This
coincides with a significant reduction of the search space when compared to
the QUBO approach using one-hot encoding.

As part of our work, we have implemented a custom simulated annealing solver,
which starts with a random initial solution that satisfies the hard
constraints. Based on this initial state, the corresponding energy is
calculated by utilizing the function $H(x)=x^{\top}Qx$, providing a reference
value for our optimization. In the next step, the solution is modified by
swapping the corresponding one-hot representations of two random blades,
ensuring that the hard constraints are always satisfied:

$\displaystyle x=(0\ 0\ 1\ \quad 0\ 1\ 0\ \quad 1\ 0\ 0\ )$
$\displaystyle\rightarrow\ $ $\displaystyle x=(1\ 0\ 0\ \quad 0\ 1\ 0\ \quad
0\ 0\ 1\ )$

Thereby, the mere exchanging of blades enables us to remain within the valid
solution landscape. The energy is then calculated again for the new candidate
and the solution with the minimal energy is preserved. Whether the new
solution candidate is considered for future permutations is determined by the
applied annealing schedule. For our purposes, we make use of the Metropolis-
Hastings algorithm for this schedule (Metropolis et al., 1953; Hastings,
1970).

We repeat this process for a predefined number of iterations
$iter\in[1000,10000]$, after which the best solution will be returned.

##  5\. Experiments

Figure 3. Total imbalance of the solutions from different solvers (with bare
disk imbalances): The resulting imbalances from the placement of all blades on
the disk are shown. Additionally, the bare disk imbalance is visualized as a
dashed horizontal line. This comparison includes the heuristic, D-Wave’s QPU,
custom simulated annealing (here denoted as Imbalance SA) and D-Wave’s Qbsolv
with simulated annealing (from left to right).

We used different synthetic and real world datasets, which are directly
extracted from an industry use case specifically curated for our experiments.
These were initially solved using an industrially employed classical
heuristic. The chosen heuristic algorithm sorts all of the blades based on
their masses and places the two heaviest blades on opposite sides, alternating
with the two lightest ones. This procedure is then repeated until all of the
blades have been assigned a slot (for a detailed description, see (Mason and
Rönnqvist, 1997)). Note that for our purposes we executed all solvers ten
times on each instance to balance statistical relevance with needed
computational resources.

###  5.1. Dataset

To allow for meaningful evaluation, we use real world datasets combined with
specifically designed synthetic datasets, that aim to capture the
fundamentally underlying structure observed real world datasets. Our synthetic
dataset consists of the following instances: `BETA20_0000`, `BETA39_0000`,
`BETA40_0000`, `NORM20_0000`, `NORM39_0000`, and `NORM40_0000`, where each is
composed of $20$, $39$, and $40$ blades, respectively. Here, the `BETA`
instances reflect a beta distribution while the `NORM` ones represent a normal
distribution of the blade weights. In contrast, the `F22_0000`, `STG_18649`
and `STG2_08859` instances have been taken from real world datasets consisting
of $22$, $84$ and $86$ blades, which exhibit similarly distributed data
compared to the synthetic instances. All synthetic and real datasets have been
scaled to show a fixedmean of $10^{4}$ and a standard deviation of $100$ and
are unitless to preserve anonymity. The underlying distribution of the blade
weights is an important factor when solving the respective problem since it
may have a significant influence on the strategies employed to obtain a
solution.

###  5.2. Solvers

In addition to the heuristic algorithm and the custom simulated annealing
solver, we have also applied multiple classical QUBO solvers, such as
simulated annealing (Kirkpatrick et al., 1983), tabu search (Glover, 1986),
SAGA (Gabor et al., 2022) and Qbsolv with simulated annealing (Inc., 2023) and
compared them with each other. In the process, we focused on the number of
valid solutions of the solvers as the problem size increased. We found that
nearly all of the solvers, beginning at a blade count of $40$, barely returned
any valid solutions. Since Qbsolv showed a comparatively high number of valid
solutions and reasonably decent performance for larger problem instances, we
will only focus on this solver in the following. Lastly, we have also used
D-Wave’s Advantage_system4.1 QPU in order to solve the balancing QUBOs. As
current hardware does not yet have sufficient resources to handle larger
problem instances of the TBP, we have split these problem instances into sub-
problems beforehand to be able to solve these on the quantum hardware.
Currently, modern hardware can handle up to $5000$ physical, which corresponds
to $119$ fully-connected logical qubits (McGeoch and Farré, 2022). While this
enables us to embed a TBP with $13$ blades in princple, the obtained solution
quality is rather poor. One reason for this lies in the hardware noise, which
significantly impacts the performance and accuracy (Zaborniak and de Sousa,
2021). As the number of qubits and utilized couplings increases, errors
accumulate (McGeoch and Farré, 2022). This noise can result in inaccuracies in
the solutions obtained from quantum algorithms, which in turn can degrade the
overall performance of the system. Therefore, based on preliminary tests, the
maximum problem size that can be reliably solved on the QPU is $5$ blades. To
compensate for this constraint, we have divided the problem in two separate
groups (assuming the blades are arranged according to the heuristic solution
within a list, where each blade is assigned a unique index): one group
containing slots and blades with even index numbers, and another group
containing slots and blades with odd index numbers. This partitioning
procedure was repeated until each of the sub-problems contained at most $M=5$
rotor blades. After solving the sub-problems, the imbalances from the partial
solutions were treated as a new TBP and solved, resulting in the complete
solution.

###  5.3. Results

The results of the different solvers for the TBP without and with bare disk
imbalances are shown in the figures Fig. 2 and Fig. 3. For the case without
the additional bare disk imbalance (Fig. 2), the heuristic algorithm shows
decent performance. However, it is surpassed by the custom simulated annealing
solver introduced above in all of the instances. Likewise, Qbsolv performs on
par with the heuristics. In general, we observe comparably worse solutions
with the D-Wave QPU in regard to the resulting imbalances, although it can
still outperform the baseline ”Heuristic” in some instances, such as
`NORM20_0000` or `STG2_08859`, especially when including bare disc imbalances
(see Fig. 3).

Note that, as the ”Heuristic” solution does not consider the bare disk
imbalance, it generally performs worse on these instances. When examining the
solutions obtained by Qbsolv, we observe that in nearly all of the cases, it
achieves significantly better solutions than the heuristic. Meanwhile, for
very large problem instances such as `STG1_18649` with $84$ and `STG2_08859`
with $86$ blades, Qbsolv performs comparably bad, even finding no valid
solution at all for `STG2_08859`. One possible explanation for this might be
that the number invalid solutions grows quadratically with the number of
nodes, while the number of valid solutions merely grows linearly. Not
experiencing this shortcoming by definition, the custom simulated annealing
presented in Sec. 4 yields excellent results for all instances, achieving the
industrial requirement for our regarded use case for a maximum total imbalance
value of $3$, corresponding to the overall dataset unit scaling, for all
cases. More precisely, the resulting total imbalances from the placement of
the blades for the custom simulated annealing solver are merely $1.29\pm
0.82$.

Finally, examining the D-Wave QPU results, its inferior performance for
problem instances without bare disc imbalances is clearly evident. However,
when including bare disc imbalances, as needed in real world application, it
performed better then the previously practically employed heuristic.
Nevertheless, when comparing the D-Wave solutions to those produced by Qbsolv
and our quantum-inspired approach, it is evident that the latter methods yield
significantly improved results in terms of the resulting imbalance.
Consequently no quantum advantage can be claimed when using our setup, i.e., a
quantum annealer solving small scale, decomposed QUBO problems.

##  6\. Conclusion

This article demonstrates how Quantum Annealing can be used to solve the
Turbine Balancing Problem (TBP). While current quantum hardware already
succeeds in surpassing the previously employed heuristic baseline when
including the bare disk imbalance, it is outperformed by Qbsolv and the
proposed quantum-inspired approach in almost every problem instance.
Correspondingly it must be assessed, that the necessity of formulating the TBP
as QUBO in order to be solved with the help of a quantum annealing approach
does cause multiple challenges, most importantly, substantial qubit count
requirements. Consequently, limited qubit capacity of current quantum hardware
demands employing additional problem decomposition techniques in order to
properly handle medium and large scale real world TBP instances. Furthermore,
strong evidence was given, that the ratio between valid and invalid solutions,
caused by the representation of the problem as a QUBO, introduces additional
obstacles. These issues led to the proposal of a novel, quantum-inspired
approach, which successfully solves the TBP to the extent that it meets the
industry requirements for all instances. This in turn raises prospects of
finding an effective way to solve this problem utilizing quantum computing
when reducing the search-space to only-valid solutions, by employing binary
encoding instead of one-hot encoding. As this leads to a PUBO rather than a
QUBO problem formulation, quantum optimization algorithms beyond quantum
annealing (such as the QAOA) should be investigated for solving the TBP in
future work.

## References

  * (1)
  * Albash and Lidar (2018) Tameem Albash and Daniel A. Lidar. 2018.  Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing.  _Phys. Rev. X_ 8 (Jul 2018), 031016.  Issue 3. https://doi.org/10.1103/PhysRevX.8.031016
  * Amiouny (1993) Samir Amiouny. 1993.  _Combinatorial mechanics_.  Ph. D. Dissertation. Georgia Institute of Technology, Atlanta, GA, USA.
  * Amiouny et al. (2000) Samir V. Amiouny, John J. Bartholdi, and John H. Vande Vate. 2000.  Heuristics for Balancing Turbine Fans.  _Operations Research_ 48, 4 (2000), 591–602.  https://doi.org/10.1287/opre.48.4.591.12413 arXiv:https://doi.org/10.1287/opre.48.4.591.12413
  * Anonymous (1990) Anonymous. 1990.  _Fundamentals of Balancing_ (3 ed.).  Schenck Trebel, Deer Park, NY.
  * Bapst et al. (2013) Victor Bapst, Laura Foini, Florent Krzakala, Guilhem Semerjian, and Francesco Zamponi. 2013.  The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective.  _Physics Reports_ 523, 3 (Feb. 2013), 127–205.  https://doi.org/10.1016/j.physrep.2012.10.002 arXiv:1210.0811 [cond-mat, physics:quant-ph].
  * Barahona (1982) F. Barahona. 1982.  On the computational complexity of Ising spin glass models.  _Journal of Physics A: Mathematical and General_ 15, 10 (Oct. 1982), 3241.  https://doi.org/10.1088/0305-4470/15/10/028
  * Born and Fock (1928) M. Born and V. Fock. 1928.  Beweis des Adiabatensatzes.  _Zeitschrift für Physik_ 51, 3 (March 1928), 165–180.  https://doi.org/10.1007/BF01343193
  * Choi and Storer (2004) Wonjoon Choi and Robert H. Storer. 2004.  Heuristic algorithms for a turbine-blade-balancing problem.  _Computers & Operations Research_ 31, 8 (2004), 1245–1258.  https://doi.org/10.1016/S0305-0548(03)00078-9
  * Denchev et al. (2016) Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven. 2016.  What is the Computational Value of Finite-Range Tunneling?  _Phys. Rev. X_ 6 (Aug 2016), 031015.  Issue 3. https://doi.org/10.1103/PhysRevX.6.031015
  * Ebadi et al. (2022) S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletić, and M. D. Lukin. 2022.  Quantum optimization of maximum independent set using Rydberg atom arrays.  _Science_ 376, 6598 (2022), 1209–1215.  https://doi.org/10.1126/science.abo6587 arXiv:https://www.science.org/doi/pdf/10.1126/science.abo6587
  * Farhi et al. (2014) Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014.  A Quantum Approximate Optimization Algorithm.  http://arxiv.org/abs/1411.4028 Number: arXiv:1411.4028 arXiv:1411.4028 [quant-ph].
  * Farhi et al. (2001) Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. 2001.  A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem.  _Science_ 292, 5516 (April 2001), 472–475.  https://doi.org/10.1126/science.1057726
  * Gabor et al. (2022) Thomas Gabor, Michael Lachner, Nico Kraus, Christoph Roch, Jonas Stein, Daniel Ratke, and Claudia Linnhoff-Popien. 2022.  Modifying the Quantum-Assisted Genetic Algorithm. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ (Boston, Massachusetts) _(GECCO ’22)_. Association for Computing Machinery, New York, NY, USA, 2205–2213.  https://doi.org/10.1145/3520304.3534034
  * Glover (1986) Fred Glover. 1986.  Future paths for integer programming and links to artificial intelligence.  _Computers & Operations Research_ 13, 5 (1986), 533–549.  https://doi.org/10.1016/0305-0548(86)90048-1 Applications of Integer Programming.
  * Glover et al. (2022) Fred Glover, Gary Kochenberger, Rick Hennig, and Yu Du. 2022.  Quantum bridge analytics I: a tutorial on formulating and using QUBO models.  _Ann. Oper. Res._ 314, 1 (2022), 141–183.  https://doi.org/10.1007/s10479-022-04634-2
  * Hastings (1970) W. K. Hastings. 1970.  Monte Carlo sampling methods using Markov chains and their applications.  _Biometrika_ 57, 1 (April 1970), 97–109.  https://doi.org/10.1093/biomet/57.1.97
  * Inc. (2023) D-Wave Systems Inc. accessed: 2023.  D-Wave Ocean Documentation: Samplers.  https://docs.ocean.dwavesys.com/en/stable/docs_samplers/index.html.
  * Kirkpatrick et al. (1983) S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983.  Optimization by Simulated Annealing.  _Science_ 220, 4598 (1983), 671–680.  https://doi.org/10.1126/science.220.4598.671 arXiv:https://www.science.org/doi/pdf/10.1126/science.220.4598.671
  * Lucas (2014) Andrew Lucas. 2014.  Ising formulations of many NP problems.  _Frontiers in Physics_ 2 (2014), 74887.  https://doi.org/10.3389/fphy.2014.00005
  * Mason and Rönnqvist (1997) Andrew Mason and Mikael Rönnqvist. 1997.  Solution methods for the balancing of jet turbines.  _Computers & Operations Research_ 24, 2 (1997), 153–167.  https://doi.org/10.1016/S0305-0548(96)00047-0
  * McGeoch and Farré (2022) Catherine McGeoch and Pau Farré. 2022.  Advantage Processor Overview: TECHNICAL REPORT.  https://www.dwavesys.com/media/3xvdipcn/14-1058a-a_advantage_processor_overview.pdf.
  * Metropolis et al. (1953) Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. 1953.  Equation of State Calculations by Fast Computing Machines.  _The Journal of Chemical Physics_ 21, 6 (June 1953), 1087–1092.  https://doi.org/10.1063/1.1699114 Publisher: American Institute of Physics.
  * Salehi et al. (2022) Özlem Salehi, Adam Glos, and Jarosław Adam Miszczak. 2022.  Unconstrained binary models of the travelling salesman problem variants for quantum optimization.  _Quantum Inf. Process._ 21, 2 (2022), 67.  https://doi.org/10.1007/s11128-021-03405-5
  * Stein et al. (2023) Jonas Stein, Farbod Chamanian, Maximilian Zorn, Jonas Nüßlein, Sebastian Zielinski, Michael Kölle, and Claudia Linnhoff-Popien. 2023.  Evidence That PUBO Outperforms QUBO When Solving Continuous Optimization Problems with the QAOA. In _Proceedings of the Companion Conference on Genetic and Evolutionary Computation_ (Lisbon, Portugal) _(GECCO ’23 Companion)_. Association for Computing Machinery, New York, NY, USA, 2254–2262.  https://doi.org/10.1145/3583133.3596358
  * Sun et al. (2021) Chuanzhi Sun, Pinghuan Xiao, Xiaoming Wang, and Yongmeng Liu. 2021.  Blade Sorting Method for Unbalance Minimization of an Aeroengine Concentric Rotor.  _Symmetry_ 13, 5 (2021), 832.  https://doi.org/10.3390/sym13050832
  * Zaborniak and de Sousa (2021) Tristan Zaborniak and Rogerio de Sousa. 2021.  Benchmarking Hamiltonian Noise in the D-Wave Quantum Annealer.  _IEEE Transactions on Quantum Engineering_ 2 (2021), 1–6.  https://doi.org/10.1109/tqe.2021.3050449


# OpenIE6: Iterative Grid Labeling and Coordination Analysis for Open
Information Extraction

Keshav Kolluru1*, Vaibhav Adlakha1*, Samarth Aggarwal1,
Mausam1, and Soumen Chakrabarti2
1 Indian Institute of Technology Delhi
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
2 Indian Institute of Technology Bombay
<EMAIL_ADDRESS>
###### Abstract

A recent state-of-the-art neural open information extraction (OpenIE) system
generates extractions iteratively, requiring repeated encoding of partial
outputs. This comes at a significant computational cost. On the other hand,
sequence labeling approaches for OpenIE are much faster, but worse in
extraction quality. In this paper, we bridge this trade-off by presenting an
iterative labeling-based system that establishes a new state of the art for
OpenIE, while extracting 10$\times$ faster. This is achieved through a novel
Iterative Grid Labeling (IGL) architecture, which treats OpenIE as a 2-D grid
labeling task. We improve its performance further by applying coverage (soft)
constraints on the grid at training time.

Moreover, on observing that the best OpenIE systems falter at handling
coordination structures, our OpenIE system also incorporates a new
coordination analyzer built with the same IGL architecture. This IGL based
coordination analyzer helps our OpenIE system handle complicated coordination
structures, while also establishing a new state of the art on the task of
coordination analysis, with a 12.3 pts improvement in F1 over previous
analyzers. Our OpenIE system, OpenIE6111 https://github.com/dair-iitd/openie6,
beats the previous systems by as much as 4 pts in F1, while being much faster.

††*Equal Contribution

##  1 Introduction

Open Information Extraction (OpenIE) is an ontology-free information
extraction paradigm that generates extractions of the form (subject; relation;
object). Built on the principles of domain-independence and scalability Mausam
(2016), OpenIE systems extract open relations and arguments from the sentence,
which allow them to be used for a wide variety of downstream tasks like
Question Answering Yan et al. (2018); Khot et al. (2017), Event Schema
Induction Balasubramanian et al. (2013) and Fact Salience Ponza et al. (2018).

Figure 1: The extractions (Rome; [is] the capital of; Italy) and (Rome; is known for; it’s rich history) can be seen as the output of grid labeling. We additionally introduce a token [is] to the input. Sentence |  | Other signs of lens subluxation include mild conjunctival redness, vitreous humour degeneration,
---
and an increase or decrease of anterior chamber depth .
IGL |  | (Other signs of lens subluxation; include; mild conjunctival redness, vitreous humour degeneration)
---
| IGL
---
+Constraints
| (Other signs of lens subluxation; include; mild conjunctival redness,
vitreous humour degeneration,
---
and an increase or decrease of anterior chamber depth)
| IGL
---
+Constraints
+Coordination
Analyzer
| (Other signs of lens subluxation; include; mild conjunctival redness)
---
(Other signs of lens subluxation; include; vitreous humour degeneration)
(Other signs of lens subluxation; include; an increase of anterior chamber
depth)
(Other signs of lens subluxation; include; an decrease of anterior chamber
depth)
Table 1: For the given sentence, IGL based OpenIE extractor produces an
incomplete extraction. Constraints improve the recall by covering the
remaining words. Coordination Analyzer handles hierarchical conjunctions.

End-to-end neural systems for OpenIE have been found to be more accurate
compared to their non-neural counterparts, which were built on manually
defined rules over linguistic pipelines. The two most popular neural OpenIE
paradigms are _generation_ (Cui et al., 2018; Kolluru et al., 2020) and
_labeling_ (Stanovsky et al., 2018; Roy et al., 2019).

_Generation_ systems generate extractions one word at a time. IMoJIE Kolluru
et al. (2020) is a state-of-the-art OpenIE system that re-encodes the partial
set of extractions output thus far when generating the next extraction. This
captures dependencies among extractions, reducing the overall redundancy of
the output set. However, this repeated re-encoding causes a significant
reduction in speed, which limits use at Web scale.

On the other hand, _labeling_ -based systems like RnnOIE Stanovsky et al.
(2015) are much faster (150 sentences per second, compared to 3 sentences of
IMoJIE) but relatively less accurate. They label each word in the sentence as
either S (Subject), R (Relation), O (Object) or N (None) for each extraction.
However, as the extractions are predicted independently, this does not model
the inherent dependencies among the extractions.

We bridge this trade-off though our proposed OpenIE system that is both fast
and accurate. It consists of an OpenIE extractor based on a novel iterative
labeling-based architecture — Iterative Grid Labeling (IGL). Using this
architecture, OpenIE is modeled as a 2-D grid labeling problem of size $(M,N)$
where $M$ is a pre-defined maximum number of extractions and $N$ is the
sentence length, as shown in Figure 1. Each extraction corresponds to one row
in the grid. Iterative assignment of labels in the grid helps IGL capture
dependencies among extractions without the need for re-encoding, thus making
it much faster than generation-based approaches.

While IGL gives high precision, we can further improve recall by incorporating
(soft) global coverage constraints on this 2-D grid. We use constrained
training Mehta et al. (2018) by adding a penalty term for all constraint
violations. This encourages the model to satisfy these constraints during
inference as well, leading to improved extraction quality, without affecting
running time.

Furthermore, we observe that existing neural OpenIE models struggle in
handling coordination structures, and do not split conjunctive extractions
properly. In response, we first design a new coordination analyzer Ficler and
Goldberg (2016b). It is built with the same IGL architecture, by interpreting
each row in the 2-D grid as a coordination structure. This leads to a new
state of the art on this task, with a 12.3 pts improvement in F1 over previous
best reported result Teranishi et al. (2019), and a 1.8 pts gain in F1 over a
strong BERT baseline.

We then combine the output of our coordination analyzer with our OpenIE
extractor, resulting in a further increase in performance (Table 1). Our final
OpenIE system — OpenIE6 — consists of IGL-based OpenIE extractor (trained with
constraints) and IGL-based coordination analyzer. We evaluate OpenIE6 on four
metrics from the literature and find that it exceeds in three of them by at
least 4.0 pts in F1. We undertake manual evaluation to reaffirm the gains. In
summary, this paper describes OpenIE6, which

  * •

is based on our novel IGL architecture,

  * •

is trained with constraints to improve recall,

  * •

handles conjunctive sentences with our new state-of-art coordination analyzer,
which is 12.3 pts better in F1, and

  * •

is 10$\times$ faster compared to current state of the art and improves F1
score by as much as 4.0 pts.

##  2 Related Work

Banko et al. (2007) introduced the Open Information Extraction paradigm
(OpenIE) and proposed TextRunner, the first model for the task. Following
this, many statistical and rule-based systems have been developed Fader et al.
(2011); Etzioni et al. (2011); Christensen et al. (2011); Mausam et al.
(2012); Del Corro and Gemulla (2013); Angeli et al. (2015); Pal and Mausam
(2016); Stanovsky et al. (2016); Saha et al. (2017); Gashteovski et al.
(2017); Saha and Mausam (2018); Niklaus et al. (2018).

Recently, supervised neural models have been proposed, which are either
trained on extractions bootstrapped from earlier non-neural systems Cui et al.
(2018), or on SRL annotations adapted for OpenIE Stanovsky and Dagan (2016).
These systems are primarily of three types, as follows.

Labeling-based systems like RnnOIE Stanovsky et al. (2018), and SenseOIE Roy
et al. (2019) identify words that can be syntactic heads of relations, and,
for each head word, perform a single labeling to get the extractions. Jiang et
al. (2020) extend these to better calibrate confidences across sentences.
Generation-based systems Cui et al. (2018); Sun et al. (2018) generate
extractions sequentially using seq2seq models. IMoJIE Kolluru et al. (2020),
the current state of art in OpenIE, uses a BERT-based encoder and an iterative
decoder that re-encodes the extractions generated so far. This re-encoding
captures dependencies between extractions, increasing overall performance, but
also makes it 50x slower than RnnOIE. Recently, span-based models Jiang et al.
(2020) have been proposed, e.g., SpanOIE Zhan and Zhao (2020), which uses a
predicate module to first choose potential candidate relation spans, and for
each relation span, classifies all possible spans of the sentence as subject
or object.

Concurrent to our work Ro et al. (2020) proposed Multi2OIE, a sequence-
labeling model for OpenIE, which first predicts all the relation arguments
using BERT, and then predicts subject and object arguments associated with
each relation using multi-head attention blocks. Their model cannot handle
nominal relations and conjunctions in arguments, which can be extracted in our
iterative labeling scheme.

OpenIE Evaluation: Several datasets have been proposed to automatically
evaluate OpenIE systems. OIE2016 Stanovsky and Dagan (2016) introduced an
automatically generated reference set of extractions, but it was found to be
too noisy with significant missing extractions. Re-OIE2016 Zhan and Zhao
(2020) manually re-annotated the corpus, but did not handle conjunctive
sentences adequately. Wire57 Léchelle et al. (2018) contributed high-quality
expert annotations, but for a small corpus of 57 sentences. We use the CaRB
dataset Bhardwaj et al. (2019), which re-annotated OIE2016 corpus via crowd-
sourcing.

The benchmarks also differ in their scoring functions along two dimensions:
(1) computing similarity for each (gold, system) extraction pair, (2) defining
a mapping between system and gold extractions using this similarity. OIE16
computes similarity by serializing the arguments into a sentence and finding
the number of matching words. It maps each system extraction to one gold (one-
to-one mapping) to compute both precision and recall. Wire57 uses the same
one-to-one mapping but computes similarity at an argument level. CaRB uses
one-to-one mapping for precision but maps multiple gold to the same system
extraction (many-to-one mapping) for recall. Like Wire57, CaRB computes
similarity at an argument level.

OpenIE for Conjunctive Sentences: Performance of OpenIE systems can be further
improved by identifying coordinating structures governed by conjunctions
(e.g., ‘and’), and splitting conjunctive extractions (see Table 1). We follow
CalmIE Saha and Mausam (2018), which is part of OpenIE5 system – it splits a
conjunctive sentence into smaller sentences based on detected coordination
boundaries, and runs OpenIE on these split sentences to increase overall
recall.

For detecting coordination boundaries, Ficler and Goldberg (2016a) re-annotate
the Penn Tree Bank corpus with coordination-specific tags. Neural parsers
trained on this data use similarity and replacability of conjuncts as features
Ficler and Goldberg (2016b); Teranishi et al. (2017). The current state-of-
the-art system (Teranishi et al., 2019) independently detects coordinator,
begin, and end of conjuncts, and does joint inference using
Cocke–Younger–Kasami (CYK) parsing over context-free grammar (CFG) rules. Our
end-to-end model obtains better accuracy than this approach.

Figure 2: 2-D grid for OpenIE with extraction as rows and words as columns.
The values represent the labels (S)ubject, (R)elation, (O)bject. The empty
cells represent (N)one. Constraints are applied across rows (HVE) and columns
(POSC).

Constrained Training: Constraining outputs of the model is a way to inject
prior knowledge into deep neural networks Hu et al. (2016); Xu et al. (2018);
Nandwani et al. (2019). These constraints can be applied either during
training or inference or both. We follow Mehta et al. (2018), which models an
output constraint as a differentiable penalty term defined over output
probabilities given by the network. This penalty is combined with the original
loss function for better training.

Bhutani et al. (2019) propose an OpenIE system to get extractions from
question-answer pairs. Their decoder enforces vocabulary and structural
constraints on the output both during training and inference. In contrast, our
system uses constraints only during training.

##  3 Iterative Grid Labeling for OpenIE

Given a sentence with word tokens $\\{w_{1},w_{2},\ldots,w_{N}\\}$ the task of
OpenIE is to output a set of extractions, say
$\\{E_{1},E_{2},\ldots,E_{M}\\}$, where each extraction is of the form
(subject; relation; object). For a labeling-based system, each word is labeled
as S (Subject), R (Relation), O (Object), or N (None) for every extraction. We
model this as a 2-D grid labeling problem of size $(M,N)$, where the words
represent the columns and the extractions represent the rows (Figure 2). The
output at position $(m,n)$ in the grid ($L_{m,n}$) represents the label
assigned to the $n^{th}$ word in the $m^{th}$ extraction.

We propose a novel Iterative Grid Labeling (IGL) approach to label this grid,
filling up one row after another iteratively. We refer to the OpenIE extractor
trained using this approach as IGL-OIE.

IGL-OIE is based on a BERT encoder, which computes contextualized embeddings
for each word. The input to the BERT encoder is $\\{w_{1},$
$w_{2},\ldots,w_{N},\emph{[is]},\emph{[of]},\emph{[from]}\\}$. The last three
tokens (referred as $st_{i}$ in Figure 3) are appended because, sometimes,
OpenIE is required to predict tokens that are not present in the input
sentence.222‘is’, ‘of’ and ‘from’ are the most frequent such tokens. E.g., “US
president Donald Trump gave a speech on Wednesday.” will have one of the
extractions as (Donald Trump; [is] president [of]; US). The appended tokens
make such extractions possible in a labeling framework.

Figure 3: Model architecture for IGL. BERT-embeddings of the words are
iteratively passed through self-attention layers. $st_{1}$, $st_{2}$, $st_{3}$
refer to the appended tokens _[is]_ , _[of]_ , _[from]_ , respectively. At
every iteration, we get an extraction by labeling the words using a fully-
connected layer. Embeddings of the generated labels are added to the iterative
layer embeddings before passing them to the next iteration.

The contextualized embeddings for each word or appended token are iteratively
passed through a 2-layer transformer to get their IL embeddings at different
levels, until a maximum level $M$, i.e. a word $w_{n}$ has a different
contextual embedding $IL_{m,n}$ for every row (level) $m$. At every level $m$,
each $IL_{m,n}$ is passed though a fully-connected labeling layer to get the
labels for words at that level (Figure 3). Embeddings of the predicted labels
are added to the IL embeddings before passing them to the next iteration.
This, in principle, maintains the information of the extractions output so
far, and hence can capture dependencies among labels of different extractions.
For words that were broken into word-pieces by BERT, only the embedding of the
first word-piece is retained for label prediction. We sum the cross-entropy
loss between the predicted labels and the gold labels at every level to get
the final loss, denoted by $J_{CE}$.

OpenIE systems typically assign a confidence value to an extraction. In IGL,
at every level, the respective extraction is assigned a confidence value by
adding the log probabilities of the predicted labels (S, R, and O), and
normalizing this by the extraction length.

We believe that IGL architecture has value beyond OpenIE, and can be helpful
in tasks where a set of labelings for a sentence is desired, especially when
labelings have dependencies amongst them.333IGL is a generalization of Ju et
al. (2018). Their model can only label spans which are subsets of one another.
We showcase another application of IGL for the task of coordination analysis
in Section 5.

Figure 4: The final OpenIE system. IGL-CA identifies conjunct boundaries by
labeling a 2-D grid. This generates simple sentences and CIGL-OIE emits the
final extractions.

##  4 Grid Constraints

Our preliminary experiments revealed that IGL-OIE has good precision, but
misses out important extractions. In particular, we observed that the set of
output extractions did not capture all the information from the sentence
(Table 1). We formulate constraints over the 2-D grid of extractions (as shown
in Figure 2) which act as an additional form of supervision to improve the
coverage. We implement these as soft constraints, by imposing additional
violation penalties in the loss function. This biases the model to learn to
satisfy the constraints, without explicitly enforcing them at inference time.

To describe the constraints, we first define the notion of a _head verb_ as
all verbs except light verbs (do, be, is, has, etc.). We run a POS tagger on
the input sentence, and find all head verbs in the sentence by removing all
light verbs.444We used the light verbs listed by Jain and Mausam (2016). For
example, for the sentence, “Obama gained popularity after Oprah endorsed him
for the presidency”, the head verbs are gained and endorsed. In order to cover
all valid extractions like (Obama; gained; popularity) and (Oprah; endorsed
him for; the presidency), we design the following coverage constraints:

  * •

POS Coverage (POSC): All words with POS tags as nouns (N), verbs (V),
adjectives (JJ), and adverbs (RB) should be part of at least one extraction.
E.g. the words Obama, gained, popularity, Oprah, endorsed, presidency must be
covered in the set of extractions.

  * •

Head Verb Coverage (HVC): Each head verb should be present in the relation
span of some (but not too many) extractions. E.g. (Obama; gained; popularity),
(Obama; gained; presidency) is not a comprehensive set of extractions.

  * •

Head Verb Exclusivity (HVE): The relation span of one extraction can contain
at most one head verb. E.g. gained popularity after Oprah endorsed is not a
good relation as it contains two head verbs.

  * •

Extraction Count (EC): The total number of extractions with head verbs in the
relation span must be no fewer than the number of head verbs in the sentence.
In the example, there must be at least two extractions containing head verbs,
as the sentence itself has two head verbs.

Notation: We now describe the penalty terms for these constraints. Let $p_{n}$
be the POS tag of $w_{n}$. We define an indicator $x^{imp}_{n}=1$ if
$p_{n}\in\\{\text{N, V, JJ, RB}\\}$, and $0$ otherwise. Similarly, let
$x_{n}^{hv}=1$ denote that $w_{n}$ is a head verb. At each extraction level
$m$, the model computes $Y_{mn}(k)$, the probability of assigning the $n^{th}$
word the label $k\in\\{\text{S, R, O, N}\\}$. We formulate the penalties
associated with our constraints as follows:

  * •

POSC \- To ensure that the $n^{th}$ word is covered, we compute its maximum
probability ($posc_{n}$) of belonging to any extraction. We introduce a
penalty if this value is low. This penalty is aggregated over words with
important POS tags, $J_{posc}=\sum_{n=1}^{N}x^{imp}_{n}\cdot posc_{n}$, where

$\displaystyle
posc_{n}=1-\max_{m\in[1,M]}\left(\max_{k\in\\{\text{S,R,O}\\}}Y_{mn}(k)\right)$

  * •

HVC \- A penalty is imposed for the $n^{th}$ word, if it is not present in
relation of any extraction or if it is present in relation of many
extractions. This penalty is aggregated over head verbs,
$J_{hvc}=\sum_{n=1}^{N}x^{hv}_{n}\cdot hvc_{n}$, where
$hvc_{n}=\left|1-\sum_{m=1}^{M}Y_{mn}(R)\right|$.

  * •

HVE \- A penalty is imposed if the relation span of an extraction contains
more than one head verb. This penalty is summed over all extractions. I.e.,
$J_{hve}=\sum_{m=1}^{M}hve_{m}$, where

$\displaystyle hve_{m}=\max\left(0,\left(\sum\limits_{n=1}^{N}x^{hv}_{n}\cdot
Y_{mn}(R)\right)-1\right)$

  * •

EC \- $ec_{m}$ denotes the score $\in[0,1]$ of the $m^{th}$ extraction
containing a head verb, i.e. $ec_{m}=\max_{n\in[1,N]}\left(x^{hv}_{n}\cdot
Y_{mn}(R)\right)$. A penalty is imposed if the sum of these scores is less
than the actual number of head verbs in the sentence.

$\displaystyle
J_{ec}=\max\left(0,\sum_{n=1}^{N}x^{hv}_{n}-\sum_{m=1}^{M}ec_{m}\right)$

Ideally, no constraint violations of HVC and HVE would imply that EC would
also never gets violated. However, as these are soft constraints, this
scenario is never materialized in practice. We find that our model performs
better and results in fewer constraint violations when trained with POSC, HVC,
HVE and EC combined. The full loss function is
$J=J_{CE}+\lambda_{posc}J_{posc}+\lambda_{hvc}J_{hvc}+\lambda_{hve}J_{hve}+\lambda_{ec}J_{ec}$,
where $\lambda_{\star}$ are hyperparameters. We refer to the OpenIE extractor
trained using this constrained loss as Constrained Iterative Grid Labeling
OpenIE Extractor (CIGL-OIE).

The model is initially trained without constraints for a fixed warmup number
of iterations, followed by constrained training till convergence.

##  5 Coordination Boundary Detection

Coordinated conjunctions (CC) are conjunctions such as “and”, “or” that
connect, or coordinate words, phrases, or clauses (they are called the
conjuncts). The goal of coordination analysis is to detect coordination
structures — the coordinating conjunctions along with their constituent
conjuncts. In this section we build a novel coordination analyzer and use its
output downstream for OpenIE.

Sentences can have hierarchical coordinations, i.e., some coordination
structures nested within the conjunct span of others Saha and Mausam (2018).
Therefore, we pose coordination analysis as a hierarchical labeling problem,
as illustrated in Figure 4. We formulate a 2-D grid labeling problem, where
all coordination structures at the same hierarchical level are predicted in
the same row.

Specifically, we define a grid of size $(M,N)$, where $M$ is the maximum depth
of hierarchy and $N$ is the number of words in the sentence. The value at
$(m,n)^{th}$ position in the grid represents the label assigned to the
$n^{th}$ word in the $m^{th}$ hierarchical level, which can be CC (coordinated
conjunction), CONJ (belonging to a conjunct span), or N (None). Using IGL
architecture for this grid gives an end-to-end Coordination Analyzer that can
detect multiple coordination structures, with two or more conjuncts. We refer
to this Coordination Analyzer as IGL-CA.

Coordination Analyzer in OpenIE: Conjuncts in a coordinate structure exhibit
_replaceability_ – a sentence is still coherent and consistent, if we replace
a coordination structure with any of its conjuncts Ficler and Goldberg
(2016b). Following CalmIE’s approach, we generate simple (non-conjunctive)
sentences using IGL-CA. We then run CIGL-OIE on these simple sentences to
generate extractions. These extractions are de-duplicated and merged to yield
the final extraction set (Figure 4). This pipelined approach describes our
final OpenIE system — OpenIE6.

For a conjunctive sentence, CIGL-OIE’s confidence values for extractions will
be with respect to multiple simple sentences, and may not be calibrated across
them. We use a separate confidence estimator, consisting of a BERT encoder and
an LSTM decoder trained on (sentence, extraction) pairs. It computes a log-
likelihood for every extraction w.r.t. the original sentence — this serves as
a better confidence measure for OpenIE6.

##  6 Experimental Setup

System | CaRB | CaRB(1-1) | OIE16-C | Wire57-C | Speed
---|---|---|---|---|---
| F1 | AUC | F1 | AUC | F1 | AUC | F1 |  Sentences/sec.
MinIE | 41.9 | - | 38.4 | - | 52.3 | - | 28.5 | 8.9
ClausIE | 45.0 | 22.0 | 40.2 | 17.7 | 61.0 | 38.0 | 33.2 | 4.0
OpenIE4 | 51.6 | 29.5 | 40.5 | 20.1 | 54.3 | 37.1 | 34.4 | 20.1
OpenIE5 | 48.0 | 25.0 | 42.7 | 20.6 | 59.9 | 39.9 | 35.4 | 3.1
SenseOIE | 28.2 | - | 23.9 | - | 31.1 | - | 10.7 | -
SpanOIE | 48.5 | - | 37.9 | - | 54.0 | - | 31.9 | 19.4
RnnOIE | 49.0 | 26.0 | 39.5 | 18.3 | 56.0 | 32.0 | 26.4 | 149.2
Cui et al. (2018) | 51.6 | 32.8 | 38.7 | 19.8 | 53.5 | 37.0 | 33.3 | 11.5
IMoJIE | 53.5 | 33.3 | 41.4 | 22.2 | 56.8 | 39.6 | 36.0 | 2.6
IGL-OIE | 52.4 | 33.7 | 41.1 | 22.9 | 55.0 | 36.0 | 34.9 | 142.0
CIGL-OIE | 54.0 | 35.7 | 42.8 | 24.6 | 59.2 | 40.0 | 36.8 | 142.0
CIGL-OIE + IGL-CA (OpenIE6) | 52.7 | 33.7 | 46.4 | 26.8 | 65.6 | 48.4 | 40.0 | 31.7
Table 2: Evaluation of OpenIE. Using constrained learning, CIGL-OIE gives
better scores on all metrics compared to IMoJIE. Adding a coordination
analyzer, CIGL-OIE + IGL-CA (OpenIE6) gives the best scores in 3 of the 4
metrics. MinIE, SenseOIE, SpanOIE do not output confidences. Code of SenseOIE
is not available to compute speed.

We train OpenIE6 using the OpenIE4 training dataset used to train
IMoJIE555Available from github:dair-iitd/imojie. It has 190,661 extractions
from 92,774 Wikipedia sentences. We convert each extraction to a sequence of
labels over the sentence. This is done by looking for an exact string match of
the words in the extraction with the sentence. In case there are multiple
string matches for one of the arguments of the extraction, we choose the
string match closest to the other arguments. This simple heuristic covers
almost 95% of the training data. We ignore the remaining extractions that have
multiple string matches for more than one argument.

We implement our models using Pytorch Lightning Falcon (2019). We use pre-
trained weights of “BERT-base-cased”666github:huggingface/transformers for
OpenIE extractor and “BERT-large-cased” for coordination analysis. We do not
use BERT-large for OpenIE extractor as we observe almost same performance with
a significant increase in computational costs. We set the maximum number of
iterations, $M$=5 for OpenIE and $M$=3 for Coordination Analysis. We use the
SpaCy POS tagger777https://spacy.io for enforcing constraints. The various
hyper-parameters used are mentioned in Appendix B.

Comparison Systems: We compare OpenIE6 against several recent neural and non-
neural systems. These include generation (IMoJIE and Cui et al. (2018)888We
use the BERT implementation available at github:dair-iitd/imojie), labeling
(RnnOIE, SenseOIE) and span-based (SpanOIE) systems. We also compare against
non-neural baselines of MinIE Gashteovski et al. (2017), ClausIE Del Corro and
Gemulla (2013), OpenIE4 Christensen et al. (2011)999github:allenai/openie-
standalone and OpenIE5 Saha et al. (2017); Saha and Mausam
(2018).101010github:dair-iitd/openie-standalone We use open-source
implementations for all systems except SenseOIE, for which the code is not
available and we use the system output provided by the authors.

Evaluation Dataset and Metrics: We evaluate all systems against CaRB’s
reference extractions, as they have higher coverage and quality compared to
other datasets. Apart from CaRB’s scoring function, we also use scoring
functions of OIE16 and Wire57 benchmarks on the CaRB reference set, which we
refer to as OIE16-C and Wire57-C. Additionally we use CaRB(1-1), a variant of
CaRB that retains CaRB’s similarity computation, but uses a one-to-one mapping
for both precision and recall (similar to OIE16-C, Wire57-C).

For each system, we report a final F1 score using precision and recall
computed by these scoring functions. OpenIE systems typically associate a
confidence value with each extraction, which can be varied to generate a
precision-recall (P-R) curve. We also report the area under P-R curve (AUC)
for all scoring functions except Wire57-C, as its matching algorithm is not
naturally compatible with P-R curves. We discuss details of these four metrics
in Appendix A.

For determining the speed of a system, we analyze the number of sentences it
can process per second. We run all the systems on a common set of 3,200
sentences Stanovsky et al. (2018), using a V100 GPU and 4 cores of Intel Xeon
CPU (the non-neural systems use only the CPU).

System | Precision | Yield |  Total Extrs
---|---|---|---
CIGL-OIE | 77.9 | 131 | 174
OpenIE6 | 78.8 | 222 | 291
Table 3: Manual comparison of Precision and Yield on 100 random conjunctive
sentences from CaRB Gold.

##  7 Experiments and Results

System | Wire57-C | CaRB | Constraint Violations |  Num. of Extrs
---|---|---|---|---
| F1 | F1 | AUC | POSC | HVC | HVE | EC | HVC+HVE+EC
IMoJIE | 36.0 | 53.5 | 33.3 | 687 | 521 | 105 | 330 | 957 | 1354
IGL-OIE | 34.9 | 52.4 | 33.7 | 1494 | 375 | 128 | 284 | 787 | 1401
IGL-OIE (POSC) | 36.7 | 49.6 | 33.4 | 396 | 303 | 200 | 243 | 746 | 1577
IGL-OIE (HVC,HVE,EC) | 35.8 | 53.2 | 32.7 | 1170 | 295 | 144 | 246 | 655 | 1509
CIGL-OIE | 36.8 | 54.0 | 35.7 | 766 | 274 | 157 | 237 | 668 | 1531
Gold | 100 | 100 | 100 | 371 | 324 | 272 | 224 | 820 | 2714
Table 4: Performance and number of constraint violations for training with
different sets of constraints. CIGL-OIE represents training IGL architecture
based OpenIE extractor with all the constraints - POSC, HVC, HVE and EC

###  7.1 Speed and Performance

How does OpenIE6 compare in speed and performance?

Table 2 reports the speed and performance comparisons across all metrics for
OpenIE. We find that the base OpenIE extractor — IGL-OIE — achieves a
60$\times$ speed-up compared to IMoJIE, while being lower in performance by
1.1 F1, and better in AUC by 0.4 pts, when using CaRB scoring function.

We find that training IGL-OIE along with constraints (CIGL-OIE), helps to
improve the performance without affecting inference time. This system is
better than all previous systems over all the considered metrics. It beats
IMoJIE by (0.5, 2.4) in CaRB (F1, AUC) and 0.8 F1 in Wire57-C.

Further, adding the coordination analyzer module (IGL-CA) gives us OpenIE6,
which is 10$\times$ faster than IMoJIE (32 sentences/sec) and achieves
significant improvements in performance in 3 of the 4 metrics considered. It
improves upon IMoJIE in F1 by 5.0, 8.8, 4.0 pts in CaRB(1-1), OIE16-C and
Wire57-C, respectively. However, in the CaRB metric, adding this module leads
to a decrease of (1.5, 0.9) pts in (F1, AUC).

On closer analysis, we notice that the current scoring functions for OpenIE
evaluation do not handle conjunctions properly. CaRB over-penalizes OpenIE
systems for incorrect coordination splits whereas other scoring functions
under-penalize them. This is also evidenced in the lower CaRB scores of for
both OpenIE-5111111OpenIE5 uses CalmIE for conjunctive sentences. (vs.
OpenIE4) and OpenIE6 (vs. CIGL-OIE) — the two systems that focus on
conjunctive sentences. We trace this issue to the difference in mapping used
for recall computation (one-to-one vs many-to-one). We refer the reader to
Appendix A.3 for a detailed analysis of this issue.

To resolve this variation in different scoring functions, we undertake a
manual evaluation. Two annotators (authors of the paper), blind to the
underlying systems (CIGL-OIE and OpenIE6), independently label each extraction
as correct or incorrect for a subset of 100 conjunctive sentences. Their
inter-annotator agreement is 93.46% (See Appendix C for details of manual
annotation setup). After resolving the extractions where they differ, we
report the precision and yield in Table 3. Here, yield is the number of
correct extractions generated by a system. It is a surrogate for recall, since
its denominator, number of all correct extractions, is hard to annotate for
OpenIE.

We find that OpenIE6 significantly increases the yield (1.7$\times$) compared
to CIGL-OIE along with a marginal increase in precision. This result
underscores the importance of splitting coordination structures for OpenIE.

###  7.2 Constraints Ablation

How are constraint violations related to model performance?

We divide the constraints into two groups: one which is dependent on head
verb(s): {HVC, HVE and EC}, and the other which is not – POSC. We separately
train IGL architecture based OpenIE extractor with these two groups of
constraints, and compare them with no constraints (IGL-OIE), all constraints
(CIGL-OIE) and IMoJIE. In Table 4, we report the performance on Wire57-C and
CaRB, and also report the number of constraint violations in each scenario.

Training IGL architecture based OpenIE extractor with POSC constraint (IGL-OIE
(POSC)), leads to a reduction in POSC violations. However, the number of
violations of (HVC+HVE+EC) remains high. On the other hand, training only with
head verb constraints (HVC,HVE,EC) reduces their violations but the POSC
violations remains high. Hence, we find that training with all the constraints
achieves the best performance. Compared to IGL-OIE, it reduces the POSC
violation from 1494 to 766 and (HVC+HVE+EC) violations from 787 to 668. The
higher violations of Gold may be attributed to an overall larger number of
extractions in the reference set.

###  7.3 Coordination Analysis

How does our coordination analyzer compare against other analyzers? How much
does the coordination analyzer benefit OpenIE systems?

Following previous works Teranishi et al. (2017, 2019), we evaluate two
variants of our IGL architecture based coordination analyzer (IGL-CA) – using
BERT-Base and BERT-Large, on coordination-annotated Penn Tree Bank Ficler and
Goldberg (2016a). We compute the Precision, Recall and F1 of the predicted
conjunct spans. In Table 5, we find that both BERT-Base and BERT-Large
variants outperform the previous state-of-art Teranishi et al. (2019) by 9.4
and 12.3 F1 points respectively. For fair comparison, we train a stronger
variant of Teranishi et al. (2019), replacing the LSTM encoder with BERT-Base
and BERT-Large. Even in these settings, IGL-CA performs better by 1.8 and 1.3
F1 points respectively, highlighting the significance of our IGL architecture.
Overall, IGL-CA establishes a new state of the art for this task.

System | Precision | Recall | F1
---|---|---|---
Teranishi et al. (2017) | 71.5 | 70.7 | 71.0
Teranishi et al. (2019) | 75.3 | 75.6 | 75.5
BERT-Base: |  |  |
Teranishi et al. (2019) | 83.1 | 83.2 | 83.1
IGL-CA | 86.3 | 83.6 | 84.9
BERT-Large: |  |  |
Teranishi et al. (2019) | 86.4 | 86.6 | 86.5
IGL-CA | 88.1 | 87.4 | 87.8
Table 5: P, R, F1 of the system evaluated on Penn Tree Bank for different systems. We use both BERT-Base and BERT-Large as the encoder Coordination Analyzer | IMoJIE | CIGL-OIE
---|---|---
None | 36.0 | 36.8
CalmIE | 37.7 | 38.0
Teranishi et al. (2019) | 36.1 | 36.5
IGL-CA | 39.5 | 40.0
Table 6: Wire57 F1 scores of IMoJIE and CIGL-OIE with addition of different
coordination analyzers. IGL-CA improves both of the OpenIE extractors.

To affirm that the gains of better coordination analysis help the downstream
OpenIE task, we experiment with using different coordination analyzers with
CIGL-OIE and IMoJIE. From Table 6, we see a considerable improvement in the
downstream OpenIE task using IGL-CA for both IMoJIE and CIGL-OIE, which we
attribute to better conjunct-boundary detection capabilities of the model. For
CIGL-OIE, this gives a 2 pts increase in Wire57-C F1, compared to CalmIE’s
coordination analyzer (CalmIE-CA).

##  8 Error Analysis

We examine extractions from a random sample of 50 sentences from CaRB
validation set, as output by OpenIE6. We identify three major sources of
errors in these sentences:
Grammatical errors: (24%) We find that the sentence formed by serializing the
extraction is not grammatically correct. We believe that combining our
extractor with a pre-trained language model might help reduce such errors.
Noun-based relations: (16%) These involve introducing additional words in the
relation span. Although our model can introduce [is], [of], [from] in
relations (Section 3), it may miss some words for which it was not trained.
E.g. [in] in (First Security; based [in]; Salt Lake City) for the phrase Salt
Lake City-based First Security.
Lack of Context: (10%) Neural models for OpenIE including ours, do not output
extraction context Mausam et al. (2012). E.g. for “She believes aliens will
destroy the Earth”, the extraction (Context(She believes); aliens; will
destroy; the Earth) can be misinterpreted without the context.

We also observe incorrect boundary identification for relation argument (13%),
cases in which coordination structure in conjunctive sentences are incorrectly
split (11%), lack of coverage (4%) and other miscellaneous errors (18%).

##  9 Conclusion

We propose a new OpenIE system – OpenIE6, based on the novel Iterative Grid
Labeling architecture, which models sequence labeling tasks with overlapping
spans as a 2-D grid labeling problem. OpenIE6 is 10x faster, handles
conjunctive sentences and establishes a new state of art for OpenIE. We
highlight the role of constraints in training for OpenIE. Using the same
architecture, we achieve a new state of the art for coordination parsing, with
a 12.3 pts improvement in F1 over previous analyzers. We plan to explore the
utility of this architecture in other NLP problems. OpenIE6 is available at
https://github.com/dair-iitd/openie6 for further research.

## Acknowledgements

We thank the anonymous reviewers for their suggestions and feedback. Mausam is
supported by IBM AI Horizons Network grant, an IBM SUR award, grants by
Google, Bloomberg and 1MG, Jai Gupta Chair Fellowship and Visvesvaraya faculty
award by Govt. of India. We thank IIT Delhi HPC facility for compute
resources. Soumen was partly supported by a Jagadish Bose Fellowship and an AI
Horizons Network grant from IBM.

## References

  * Angeli et al. (2015) Gabor Angeli, Melvin Jose Johnson Premkumar, and Christopher D. Manning. 2015.  Leveraging Linguistic Structure for Open Domain Information Extraction.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing (ACL), 2015_ , pages 344–354.
  * Balasubramanian et al. (2013) Niranjan Balasubramanian, Stephen Soderland, Mausam, and Oren Etzioni. 2013.  Generating coherent event schemas at scale.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pages 1721–1731, Seattle, Washington, USA. Association for Computational Linguistics.
  * Banko et al. (2007) Michele Banko, Michael J Cafarella, Stephen Soderland, Matthew Broadhead, and Oren Etzioni. 2007.  Open information extraction from the web.  In _International Joint Conference on Artificial Intelligence (IJCAI), 2007_ , volume 7, pages 2670–2676.
  * Bhardwaj et al. (2019) Sangnie Bhardwaj, Samarth Aggarwal, and Mausam. 2019.  CaRB: A Crowdsourced Benchmark for OpenIE.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), 2019_ , pages 6263–6268.
  * Bhutani et al. (2019) Nikita Bhutani, Yoshihiko Suhara, Wang-Chiew Tan, Alon Halevy, and H. V. Jagadish. 2019.  Open information extraction from question-answer pairs.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 2294–2305, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Christensen et al. (2011) Janara Christensen, Mausam, Stephen Soderland, and Oren Etzioni. 2011.  An analysis of open information extraction based on semantic role labeling.  In _Proceedings of the sixth international conference on Knowledge capture_ , pages 113–120. ACM.
  * Cui et al. (2018) Lei Cui, Furu Wei, and Ming Zhou. 2018.  Neural open information extraction.  In _Proceedings of Association for Computational Linguistics (ACL), 2018_ , pages 407–413.
  * Del Corro and Gemulla (2013) Luciano Del Corro and Rainer Gemulla. 2013.  ClausIE: clause-based open information extraction.  In _Proceedings of the 22nd international conference on World Wide Web (WWW), 2013_ , pages 355–366. ACM.
  * Etzioni et al. (2011) Oren Etzioni, Anthony Fader, Janara Christensen, Stephen Soderland, and Mausam. 2011\.  Open Information Extraction: The Second Generation.  In _IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011_ , pages 3–10. IJCAI/AAAI.
  * Fader et al. (2011) Anthony Fader, Stephen Soderland, and Oren Etzioni. 2011.  Identifying Relations for Open Information Extraction.  In _Proceedings of the Conference of Empirical Methods in Natural Language Processing (EMNLP ’11)_ , Edinburgh, Scotland, UK.
  * Falcon (2019) WA Falcon. 2019.  Pytorch lightning.  _GitHub. Note: https://github.com/williamFalcon/pytorch-lightning_.
  * Ficler and Goldberg (2016a) Jessica Ficler and Yoav Goldberg. 2016a.  Coordination annotation extension in the penn tree bank.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers_. The Association for Computer Linguistics.
  * Ficler and Goldberg (2016b) Jessica Ficler and Yoav Goldberg. 2016b.  A neural network for coordination boundary prediction.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016_ , pages 23–32. The Association for Computational Linguistics.
  * Gashteovski et al. (2017) Kiril Gashteovski, Rainer Gemulla, and Luciano del Corro. 2017.  MinIE: minimizing facts in open information extraction.  In _Association for Computational Linguistics (ACL), 2017_.
  * Hu et al. (2016) Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard Hovy, and Eric Xing. 2016.  Harnessing deep neural networks with logic rules.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2410–2420, Berlin, Germany. Association for Computational Linguistics.
  * Jain and Mausam (2016) Prachi Jain and Mausam. 2016.  Knowledge-guided linguistic rewrites for inference rule verification.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 86–92.
  * Jiang et al. (2020) Zhengbao Jiang, Wei Xu, Jun Araki, and Graham Neubig. 2020.  Generalizing natural language analysis through span-relation representations.  In _The 58th Annual Meeting of the Association for Computational Linguistics (ACL)_ , Seattle, U.S.A.
  * Ju et al. (2018) Meizhi Ju, Makoto Miwa, and Sophia Ananiadou. 2018.  A neural layered model for nested named entity recognition.  pages 1446–1459, New Orleans, Louisiana. Association for Computational Linguistics.
  * Khot et al. (2017) Tushar Khot, Ashish Sabharwal, and Peter Clark. 2017.  Answering complex questions using open information extraction.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017, Vancouver, Canada, July 30 - August 4, Volume 2: Short Papers_ , pages 311–316. Association for Computational Linguistics.
  * Kolluru et al. (2020) Keshav Kolluru, Samarth Aggarwal, Vipul Rathore, Mausam, and Soumen Chakrabarti. 2020.  IMoJIE: Iterative Memory-Based Joint Open Information Extraction.  In _The 58th Annual Meeting of the Association for Computational Linguistics (ACL)_ , Seattle, U.S.A.
  * Léchelle et al. (2018) William Léchelle, Fabrizio Gotti, and Philippe Langlais. 2018.  Wire57 : A fine-grained benchmark for open information extraction.  In _LAW@ACL_.
  * Mausam (2016) Mausam. 2016.  Open information extraction systems and downstream applications.  In _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI), 2016_ , pages 4074–4077. AAAI Press.
  * Mausam et al. (2012) Mausam, Michael Schmitz, Robert Bart, Stephen Soderland, and Oren Etzioni. 2012\.  Open language learning for information extraction.  In _Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning_ , pages 523–534. Association for Computational Linguistics.
  * Mehta et al. (2018) Sanket Vaibhav Mehta, Jay Yoon Lee, and Jaime G. Carbonell. 2018.  Towards semi-supervised learning for deep semantic role labeling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018_ , pages 4958–4963. Association for Computational Linguistics.
  * Nandwani et al. (2019) Yatin Nandwani, Abhishek Pathak, Parag Singla, and Mausam. 2019.  A primal dual formulation for deep learning with constraints.  In _Advances in Neural Information Processing Systems_ , pages 12157–12168.
  * Niklaus et al. (2018) Christina Niklaus, Matthias Cetto, André Freitas, and Siegfried Handschuh. 2018\.  A survey on open information extraction.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 3866–3878, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Pal and Mausam (2016) Harinder Pal and Mausam. 2016.  Demonyms and compound relational nouns in nominal OpenIE.  In _Proceedings of the 5th Workshop on Automated Knowledge Base Construction_ , pages 35–39.
  * Ponza et al. (2018) Marco Ponza, Luciano Del Corro, and Gerhard Weikum. 2018.  Facts that matter.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1043–1048, Brussels, Belgium. Association for Computational Linguistics.
  * Ro et al. (2020) Youngbin Ro, Yukyung Lee, and Pilsung Kang. 2020.  Multi2OIE: Multilingual Open Information Extraction Based on Multi-Head Attention with BERT.  In _Findings of ACL: EMNLP 2020_.
  * Roy et al. (2019) Arpita Roy, Youngja Park, Taesung Lee, and Shimei Pan. 2019.  Supervising Unsupervised Open Information Extraction Models.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 728–737.
  * Saha and Mausam (2018) Swarnadeep Saha and Mausam. 2018.  Open information extraction from conjunctive sentences.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 2288–2299.
  * Saha et al. (2017) Swarnadeep Saha, Harinder Pal, and Mausam. 2017.  Bootstrapping for numerical OpenIE.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 317–323. Association for Computational Linguistics.
  * Stanovsky and Dagan (2016) Gabriel Stanovsky and Ido Dagan. 2016.  Creating a large benchmark for open information extraction.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , Austin, Texas. Association for Computational Linguistics.
  * Stanovsky et al. (2016) Gabriel Stanovsky, Jessica Ficler, Ido Dagan, and Yoav Goldberg. 2016.  Getting more out of syntax with PropS.  _CoRR_ , abs/1603.01648.
  * Stanovsky et al. (2015) Gabriel Stanovsky, Mausam, and Ido Dagan. 2015.  OpenIE as an intermediate structure for semantic tasks.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 303–308.
  * Stanovsky et al. (2018) Gabriel Stanovsky, Julian Michael, Luke Zettlemoyer, and Ido Dagan. 2018.  Supervised Open Information Extraction.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), Volume 1 (Long Papers)_ , pages 885–895.
  * Sun et al. (2018) Mingming Sun, Xu Li, Xin Wang, Miao Fan, Yue Feng, and Ping Li. 2018.  Logician: A unified end-to-end neural approach for open-domain information extraction.  In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_ , pages 556–564.
  * Teranishi et al. (2017) Hiroki Teranishi, Hiroyuki Shindo, and Yuji Matsumoto. 2017.  Coordination boundary identification with similarity and replaceability.  In _Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 264–272.
  * Teranishi et al. (2019) Hiroki Teranishi, Hiroyuki Shindo, and Yuji Matsumoto. 2019.  Decomposed local models for coordinate structure parsing.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 3394–3403, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Xu et al. (2018) Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. 2018.  A semantic loss function for deep learning with symbolic knowledge.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 5498–5507. PMLR.
  * Yan et al. (2018) Zhao Yan, Duyu Tang, Nan Duan, Shujie Liu, Wendi Wang, Daxin Jiang, Ming Zhou, and Zhoujun Li. 2018.  Assertion-based QA with question-aware open information extraction.  In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018_ , pages 6021–6028. AAAI Press.
  * Zhan and Zhao (2020) Junlang Zhan and Hai Zhao. 2020.  Span Model for Open Information Extraction on Accurate Corpus.  In _AAAI Conference on Artificial Intelligence, 2020_ , pages 5388–5399.

##  Appendix A Metrics

| System 1 (P, R, F1) | System 2 (P, R, F1)
---|---|---
Talks resumed between USA and China Gold: (Talks; resumed; between USA and China) |  (Talks; resumed; between USA) (Talks; resumed; between China) CaRB: (50.0, 66.7, 57.1) CaRB (1-1): (50.0, 66.7, 57.1) |  (Talks; resumed; between USA and China) CaRB: (100, 100, 100) CaRB (1-1): (100, 100, 100)
I ate an apple and orange Gold: (I; ate; an apple) (I; ate; an orange) |  (I; ate; an apple) (I; ate; an orange) CaRB: (100, 100, 100) CaRB (1-1): (100, 100, 100) |  (I; ate; an apple and an orange) CaRB: (57.1, 100, 72.7) CaRB (1-1): (53.5, 50.0, 57.1)
Table 7: Evaluation of CaRB and CaRB (1-1) on two sentences.

###  A.1 Introduction

Designing an evaluation benchmark for an under-specified and subjective task
like OpenIE has gathered much attention. Several benchmarks, consisting of
gold labels and scoring functions have been contributed. While coverage and
quality of gold labels of these benchmarks have been extensively studied,
differences in their scoring functions is largely unexplored. We evaluate all
our systems on the CaRB reference set, which has 641 sentences and
corresponding human annotated extractions in both dev and test set. As the
underlying gold labels, is the same, system performances differ only due to
difference in design choices of these scoring functions, which we explore in
detail here.

###  A.2 Scoring Functions of Benchmarks

OIE2016121212https://github.com/gabrielStanovsky/oie-benchmark creates a one-
to-one mapping between (gold, system) pairs by serializing the extractions and
comparing the number of common words within them. Hence the system is not
penalized for misidentifying parts of an one argument in another. Precision
and recall for the system are computed using the one-to-one mapping obtained,
i.e. precision is (no. of system extractions mapped to gold extractions)/
(total no. of system extractions) and recall is (no. of gold extractions
mapped to system extractions)/(total no. of gold extractions). These design
choices have several implications Léchelle et al. (2018); Bhardwaj et al.
(2019). Overlong system extractions which are mapped, are not penalized, and
extractions with partial coverage of gold extractions, which are not mapped,
are not rewarded at all.

Wire57131313https://github.com/rali-udem/WiRe57 attempts to tackle the
shortcomings of OIE2016. For each gold extraction, a set of candidate system
extractions are chosen on the basis of whether they share at least one word
for each of the arguments141414We refer to subject, relation and object as
arguments of the extraction. of the extraction, with the gold. It then creates
a one-to-one mapping by greedily matching gold with one of the candidate
system extraction on the basis of token-level F1 score. Token level precision
and recall of the matches are then aggregated to get the score for the system.
Computing scores at token level helps in penalizing overly long extractions.

Wire57 ignores the confidence of extraction and reports just the F1 score (F1
at zero confidence). One way to generate AUC for Wire57 is by obtaining
precision and recall scores at various confidence levels by passing a subset
of extractions to the scorer. However, due to Wire57’s criteria of matching
extractions on the basis of F1 score, the recall of the system does not
decrease monotonically with increasing confidence, which is a requirement for
calculating AUC.

OIE2016 and Wire57 both use one-to-one mapping strategy, due to which a system
extraction, that contains information from multiple gold extractions, is
unfairly penalized.

CaRB151515https://github.com/dair-iitd/CaRB also computes similarity at a
token level, but it is slightly more lenient than Wire57 — it considers number
of common words in (gold,system) pair for each argument of the extraction.
However, it uses one-to-one mapping for precision and many-to-one mapping for
computing recall. While this solves the issue of penalizing extractions with
information from multiple gold extractions, it inadvertently creates another
one — unsatisfactorily evaluating systems which split on conjunctive
sentences. We explore this in detail in the next section.

###  A.3 CaRB on Conjunctive Sentences

Coordinate structure in conjunctive sentences are of two types:

  * •

Combinatory, where splitting the sentence by replacing the coordinate
structure with one of the conjuncts can lead to incoherent extractions. E.g.
splitting “Talks resumed between USA and China” will give (Talks; resumed;
between USA).

  * •

Segregatory, where splitting on coordinate structure can lead to shorter and
coherent extractions. E.g. splitting “I ate an apple and orange.” gives (I;
ate; an apple) and (I; ate; an orange).

Combinatory coordinate structures are hard to detect (in some cases even for
humans). Some systems (ClausIE, CalmIE and ours) use some heuristics such as
not splitting if coordinate structure is preceded by “between”. In all other
cases, coordinate structure is treated as segregatory, and is split.

The human-annotated gold labels of CaRB dataset correctly handle conjunctive
sentences in most of the cases. However, we find that compared to scoring
function of OIE2016 and Wire57, CaRB over-penalizes systems for incorrectly
splitting combinatory coordinate structures.

We trace this issue to the difference in mapping used for recall computation
(one-to-one vs many-to-one).

Consider two systems – System 1, which splits on all conjunctive sentences
(without any heuristics), and System 2, which does not. For the sentence “I
ate an apple and orange”, the set of gold extractions are {(I; ate; an apple),
(I; ate; orange)}. System 2, which (incorrectly) doe not split on the
coordinate structure, gets a perfect recall score of 1.0, similar to System 1,
which correctly splits the extractions (Table 7). On the other hand, when
System 2 incorrectly splits extractions for the sentence “Talks resumed
between USA and China”, it is penalized on both precision and recall by CaRB,
giving it a much lower score than System 2.

Due to this phenomena, we find that the gains obtained by our system on
splitting the segregatory coordinate structures correctly is overshadowed by
penalties of incorrectly splitting the coordinate structures. To re-affirm
this, we evaluate all the systems on CaRB(1-1), a variant of CaRB which
retains all the properties of CaRB, except that it uses one-to-one mapping for
computing recall.

We notice that our CIGL-OIE+IGL-CA shows improvements in CaRB(1-1) and other
metrics which use one-to-one mapping (OIE16, Wire57) (Table 2). But it shows a
decrease in CaRB score. This demonstrates that the primary reason for the
decrease in performance is the many-to-one mapping in CaRB.

However, we also observe that this is not the best strategy for evaluation as
it assigns equal score to both the cases — splitting a combinatory coordinate
structure, and not splitting a segregatory coordinate structure (Table 7).
This is also not desirable as a long extraction which is not split is better
than two incorrectly split extractions. Hence, we consider that one-to-one
mapping for computing recall under-penalizes splitting a combinatory
coordinate structure.

Determining the right penalty in this case is an open-ended problem. We leave
it to further research to design an optimal metric for evaluating conjunctive
sentences for OpenIE.

##  Appendix B Reproducibility

#### Compute Infrastructure:

We train all of our models using a Tesla V100 GPU (32 GB).

#### Hyper-parameter search:

The final hyper-parameters used during train our model are listed in Table 8.
We also list the search-space, which was manually tuned. We select the model
based on the best CaRB (F1) score on validation set.

#### Validation Scores:

We report the best validation scores in Table 9.

#### Number of parameters:

The CIGL-OIE model contains 110 million parameters and IGL-CA contains 335
million parameters. The difference is because they use BERT-base and BERT-
large models, respectively.

Hyperparameters | Best Values | Grid Search
---|---|---
Training: |  |
Batch Size | 24 | {16,32,24}
Optimizer | AdamW | {AdamW, Adam}
Learning Rate | $2\times 10^{-5}$ | {$1\times 10^{-3}$, $2\times 10^{-4}$, $5\times 10^{-5}$}
Model: |  |
Iterative Layers | 2 | {1,2,3}
$\lambda_{posc}$ | 3 | {0.1, 1, 3, 5, 10}
$\lambda_{hvc}$ | 3 | {0.1, 1, 3, 5, 10}
$\lambda_{hve}$ | 3 | {0.1, 1, 3, 5, 10}
$\lambda_{ec}$ | 3 | {0.1, 1, 3, 5, 10}
Table 8: Hyperparameter settings. System | CaRB | CaRB(1-1) | OIE16-C | Wire57-C
---|---|---|---|---
| F1 | AUC | F1 | AUC | F1 | AUC | F1
IMoJIE | 55.2 | 35.2 | 43.1 | 23.4 | 59.0 | 42.5 | 38.7
IGL-OIE | 53.4 | 32.7 | 41.8 | 22.0 | 56.8 | 36.6 | 36.9
CIGL-OIE | 55.2 | 35.5 | 43.9 | 23.9 | 62.3 | 42.4 | 39.1
CIGL-OIE + IGL-CA (OpenIE6) | 53.8 | 35.0 | 47.5 | 27.7 | 67.7 | 51.9 | 42.4
Table 9: Evaluation of OpenIE systems on validation set

##  Appendix C Manual Comparison

The set of extractions from both the systems, CIGL-OIE and OpenIE6 were
considered for a random 100 conjunctive sentences from the validation set. We
identify a conjunctive sentence, based on the predicted conjuncts of
coordination analyzer. The annotators are instructed to check if the
extraction has well formed arguments and is implied by the sentence.

A screenshot of the process is shown in Figure 5.

Figure 5: Process for manual comparison. Each extraction from both the systems
are presented to the annotator in a randomized order. The annotator checks if
the extraction can be inferred from the original sentence and marks it
accordingly.