#  An Approach to Mismatched Disturbance Rejection Control for Continuous-Time
Uncontrollable Systems

Shichao Lv1, Hongdan Li1, Kai Peng2 , Shihua Li3, Huanshui Zhang1∗

1 College of Electrical Engineering and Automation, Shandong University of
Science and Technology, Qingdao, Shandong, P.R.China 266590.

2 School of Power and Energy, Northwestern Polytechnical University, Xi’an,
Shaanxi, P.R.China 710072.

3 School of Automation, Southeast University, Nanjing, Jiangsu, P.R.China
210096.

Abstract

This paper focuses on optimal mismatched disturbance rejection control for
linear continuous-time uncontrollable systems. Different from previous
studies, by introducing a new quadratic performance index to transform the
mismatched disturbance rejection control into a linear quadratic tracking
problem, the regulated state can track a reference trajectory and minimize the
influence of disturbance. The necessary and sufficient conditions for the
solvability and the disturbance rejection controller are obtained by solving a
forward-backward differential equation over a finite horizon. A sufficient
condition for system stability is obtained over an infinite horizon under
detectable condition. This paper details our novel approach for transforming
disturbance rejection into a linear quadratic tracking problem. The
effectiveness of the proposed method is provided with two examples to
demonstrate.

Keywords: Disturbance rejection control; linear quadratic tracking;
continuous-time system; mismatched disturbance; uncontrollable system.

##  1 Introduction

The need to implement disturbance rejection techniques in controller design
has become a fundamental issue in automatic control with the growing interest
for high-precision control. According to the relationship with the control
input, the disturbance in the system can be divided into matched and
mismatched disturbances. Different disturbance rejection controllers handle
disturbances using different schemes. Most of the previous studies focused on
matched disturbance rejection control such as disturbance observer-based
control [1, 2], active disturbance rejection control (ADRC) [3, 4, 5, 6] and
sliding mode control (SMC) [7, 8].

By contrast, rejecting mismatched disturbances is more challenging. Mismatched
disturbances widely exist in many practical systems, such as roll autopilots
for missiles, permanent magnet synchronous motors, and flight control systems
are affected by mismatched disturbances [9, 10, 11]. Compared with matched
disturbances, the effects of these mismatched disturbances cannot be
equivalently converted into input channels acting on the system so that they
cannot be directly eliminated by the input. Therefore, no matter what control
scheme employed, it is impossible to eliminate the influence of mismatched
disturbance on the system state [12]. Therefore, a practical approach is to
remove the effects of mismatched disturbances in some variables of interest
describing the regulated state.

There are several methods [13, 14, 15, 16, 17, 18, 19] for dealing with
mismatched disturbances. For a nonlinear system with mismatched disturbances,
a novel SMC scheme based on a generalized disturbance observer was presented
in [15, 19]. This scheme can reject mismatched disturbances in steady-state
controlled outputs. In contrast to [15, 19], [18] treated mismatched
disturbances in a multi-input multi-output system with arbitrary disturbance
relative degrees. In a linear system with mismatched disturbances, a
generalized extended state observer-based control (GESOBC) method was proposed
for linear controllable systems to eliminate mismatched disturbances in the
steady-state controlled output [16]. Similar to [16], [13] weakened the
restriction of disturbances and improved the disturbance rejection effect by
introducing high-order derivatives of disturbances. However, previous works
have mainly focused on controllable systems and these methods are not
applicable to uncontrollable linear systems. Furthermore, the above studies do
not consider the balance between control input energy costs and disturbance
rejection. In other words, their methods of disturbance rejection control are
ineffective in minimizing the cost functional.

This paper focuses on the mismatched disturbance rejection control of linear
continuous-time systems. The core of this problem is the design of the
controller that attenuates or eliminates the effects of mismatched
disturbances on the regulated state. To this end, we introduce a novel
quadratic performance index so that the regulated state can track the
reference trajectory and minimize the effect of disturbances. In this way, we
transform the mismatched disturbance rejection control into a linear quadratic
tracking (LQT) problem. It should be noted that the performance index of this
mismatched disturbance rejection control problem is different from the
standard LQT problem. The new performance index enables the regulated state
can track a reference trajectory and minimize the influence of disturbance. To
the best of our knowledge, this is a novel approach to mismatched disturbance
rejection control using LQT control.

The main contributions of this paper are summarized as follows. Firstly, the
necessary and sufficient conditions for the existence of the disturbance
rejection controller are derived from the Riccati differential equation over a
finite horizon, and the analytical expression of the controller is obtained.
Secondly, in contrast to [13, 20, 16] which requires the system to be
controllable, we derived stabilization results under the detectability
condition alone. We provide the sufficient condition of stabilization over an
infinite horizon based on the generalized algebraic Riccati equation (GARE)
with a pseudo-inverse matrix. And we further extend the proposed method to
receding-horizon control so that it can handle measurable disturbance in real
time. Finally, we demonstrate the effectiveness and feasibility of the method
by comparing the simulations of proportional-integral-derivative (PID) control
in an uncontrollable numerical example, PID and GESOBC methods in a permanent
magnet direct current (PMDC) system.

The remainder of this paper is organized as follows. The mismatched
disturbance rejection control problem for linear continuous-time system and
some necessary lemmas and definitions are introduced in Section 2. In Section
3, the design and analysis of the controller over a finite horizon are
presented. The stability of the system under the proposed controller over an
infinite horizon is analyzed in Section 4. Two examples are provided to
demonstrate the effectiveness of the proposed method in Section 5. The final
section is our conclusion. And the proofs are in the Appendix.

Notation: $\mathbb{R}^{n}$ represents the $n$-dimensional Euclidean space; the
superscripts ′, -1, †, and $\|\cdot\|$ represent the transpose, inverse,
pseudo-inverse, and 2-norm of a matrix, respectively; a symmetric matrix $M>0$
($\geq$ 0) is positive definite (positive semi-definite); $I$ denotes the unit
matrix; $O$ denotes the zero matrix; and $\rho(\cdot)$ denotes a matrix
eigenvalue.

##  2 Problem Formulation

We consider the linear continuous-time system with mismatched disturbances
which are described as follows.

$\displaystyle\dot{x}_{t}={Ax}_{t}+{B}{u}_{t}+{E}d_{t},x_{0}=x,$ (2.1)

where ${x}_{t}\in{\mathbb{R}}^{n}$, ${u}_{t}\in\mathbb{R}^{m}$, and
${d}_{t}\in\mathbb{R}^{q}$ are the state, control input, and disturbance,
respectively. $x\in{\mathbb{R}}^{n}$ is initial value.
${A}\in\mathbb{R}^{n\times n}$, ${B}\in\mathbb{R}^{n\times m}$, and
${E}\in\mathbb{R}^{n\times q}$ are known deterministic coefficient matrices.

######  Remark 1.

In (2.1), $d_{t}$ expresses a known disturbance. The $d_{t}$ includes
disturbances for which disturbance models are available [21, 22] and
measurable disturbances [23, 24]. The problem that a disturbance is only
measurable at the current time can be solved by extending receding-horizon
control, see the end of Section 4 for details.

######  Remark 2.

A mismatched disturbance means that the matching condition ($B\Gamma=E$ for
some $\Gamma$) does not hold, which implies that disturbance affect the system
through the different channel as the control input or the effects of
disturbance cannot be equivalently transformed into input channels.

In order to make the regulated state of the system optimally track the
reference based on the compensation for the disturbance, we transform the
mismatched disturbance rejection problem of the linear continuous-time system
(2.1) into an LQT problem.

Therefore, we define the following cost functional:

$\displaystyle J_{T}=$
$\displaystyle\frac{1}{2}\int_{0}^{T}[(x_{t}-r)^{\prime}Q(x_{t}-r)+({B}{u}_{t}+{E}d_{t})^{\prime}R({B}{u}_{t}+{E}d_{t})]\mathrm{d}t+\frac{1}{2}(x_{T}-r)^{\prime}P_{T}(x_{T}-r),$
(2.2)

where $Q={{c}_{o}}^{\prime}\bar{Q}{c}_{o}$ ($c_{o}\in\mathbb{R}^{l\times n}$,
$\bar{Q}\in\mathbb{R}^{l\times l}$ is a semi-positive definite weight matrix),
$x_{T}$ is the terminal state, and $Q,R,P_{T}\in\mathbb{R}^{n\times n}$ are
semi-positive definite.

######  Remark 3.

The cost functional consists of two parts. The first part

$\displaystyle(x_{t}-r)^{\prime}Q(x_{t}-r)=({c}_{o}x_{t}-{c}_{o}r)^{\prime}\bar{Q}({c}_{o}x_{t}-{c}_{o}r)$
(2.3)

represents the error between the regulated state $c_{o}x_{t}$ and the
reference state ${c}_{o}r$ such that the regulated state tracks the reference.
The second part $(Bu_{t}+Ed_{t})^{\prime}R(Bu_{t}+Ed_{t})$ is the sum of the
control input and disturbance for the control input to compensate the
disturbance.

######  Remark 4.

The proposed cost functional (2.2) can be applied to both matching and
mismatching cases. Obviously, the invertible matrix $B$ is the simplest case,
where $Bu_{t}+Ed_{t}=0$ has a solution. In case of $B$ is irreversible, it
needs to discuss whether a solution of $Bu_{t}+Ed_{t}=0$ exists. A solution
with $Bu_{t}+Ed_{t}=0$ exists when $B\Gamma=E$ for some $\Gamma$ (ADRC is
suitable for this type of scenario). The most complicated case is dealing with
$\Gamma$ not satisfying $B\Gamma=E$, i.e. mismatching case, which is the main
focus of this study.

######  Problem 1.

Find the control $u_{t}$ such that the effects of the disturbance $d_{t}$ are
minimized, that is, $Bu_{t}+Ed_{t}$ is minimized, and the state $x_{t}$ tracks
the reference $r$.

##  3 Optimization over a Finite Horizon

First, the following lemma is the key to the solvability of Problem 1.

######  Lemma 1.

[25] Problem 1 is uniquely solvable if and only if the following FBDEs have a
unique solution,

$\displaystyle\left\\{\begin{array}[]{lll}B^{\prime}RBu_{t}+B^{\prime}REd_{t}+B^{\prime}\lambda_{t}=0\\\
\dot{\lambda}_{t}=Q(r-x_{t})-A^{\prime}\lambda_{t}\\\
\dot{x}_{t}={Ax}_{t}+{B}{u}_{t}+{E}d_{t}\\\ \lambda_{T}=P_{T}(x_{T}-r)\\\
x_{0}=x.\end{array}\right.$ (3.9)

The goal of the disturbance rejection controller design in this paper is to
reduce the effect of mismatched disturbance and make the regulated state of
the system follow the reference. To obtain this result, the main technique is
to solve the FBDEs (3.9).

For deriving the solution of Problem 1, we define the following generalized
Riccati differential equation (GRDE). Denote $P_{t}$ and $M_{t}$ with the
terminal time $T$ as $P_{t}(T)$ and $M_{t}(T)$, respectively. Under the
regular condition that

$\displaystyle\Upsilon\Upsilon^{{\dagger}}M_{t}(T)=M_{t}(T),$ (3.10)

we introduce the GRDE:

$\displaystyle\dot{P}_{t}(T)=M^{\prime}_{t}(T)\Upsilon^{{\dagger}}M_{t}(T)-P_{t}(T)A-A^{\prime}P_{t}(T)-Q,$
(3.11)

where

$\displaystyle\Upsilon$ $\displaystyle=B^{\prime}RB,$ (3.12) $\displaystyle
M_{t}(T)$ $\displaystyle=B^{\prime}P_{t}(T)$ (3.13)

with a terminal value $P_{T}(T)=0$.

######  Remark 5.

For the special case $\Upsilon=B^{\prime}RB>0$ in (3.10), the corresponding
Riccati equation is

$\displaystyle\dot{P}_{t}=M^{\prime}_{t}\Upsilon^{-1}M_{t}-P_{t}A-A^{\prime}P_{t}-Q,$
(3.14)

where

$\displaystyle M_{t}=B^{\prime}P_{t}.$ (3.15)

Based on the lemma and definition in the preliminaries, the following theorem
is given.

######  Theorem 1.

Problem 1 exists a unique solution $u_{t}$ if and only if $\Upsilon>0$ in
(3.12). In that case, the optimal controller is given by

$\displaystyle u_{t}=-\Upsilon^{-1}M_{t}x_{t}-\Upsilon^{-1}h_{t},$ (3.16)

where $h_{t}$ satisfies the following equation:

$\left\\{\begin{aligned} &h_{t}=B^{\prime}REd_{t}+B^{\prime}f_{t},\\\
&\dot{f}_{t}=M^{\prime}_{t}\Upsilon^{-1}h_{t}-A^{\prime}f_{t}-P_{t}Ed_{t}+Qr,\\\
&f_{T}=-P_{T}r.\end{aligned}\right.$ (3.17)

The optimal cost functional is given as

$\displaystyle
J^{*}=\frac{1}{2}x_{0}^{\prime}Px_{0}+{x}^{\prime}_{0}f_{0}+H_{0},$ (3.18)

where ${H}_{t}$ is the solution of

$\displaystyle\dot{H}_{t}=\frac{1}{2}h^{\prime}_{t}\Upsilon^{-1}h_{t}-d^{\prime}_{t}E^{\prime}f_{t}-\frac{1}{2}r^{\prime}Qr-\frac{1}{2}d^{\prime}_{t}E^{\prime}REd_{t}$
(3.19)

with final condition $H_{T}=r^{\prime}P_{T}r$.

###### Proof.

The proofs of Theorem 1 can be found in Appendix A. ∎

######  Remark 6.

The obtained controller (3.16) is consistent with that by the existing method.
Due to the consideration of the optimality of the disturbance rejection
control, the difference from the existing method is that the obtained control
parameters of the controller are derived from the Riccati equation instead of
directly calculated by the system coefficients.

######  Remark 7.

It is worth noting that disturbances in the regulated state can be optimally
eliminated by the controller proposed in Theorem 1. This result is novel to
our knowledge.

##  4 Stabilization over an Infinite Horizon

In order to facilitate the analysis of the stability of the system over an
infinite horizon, on the basis of Theorem 1, we first give the following
lemma.

######  Lemma 2.

Assume that the GRDE (3.11)–(3.13) yields a solution. Then, Problem 1 has a
solution expressed as

$\displaystyle
u_{t}=-\Upsilon^{{\dagger}}M_{t}(T)x_{t}-\Upsilon^{{\dagger}}h_{t}(T),$ (4.20)

where $h_{t}(T)$ satisfies the following equation:

$\left\\{\begin{aligned} &h_{t}(T)=B^{\prime}f_{t}(T)+B^{\prime}REd_{t},\\\
&\dot{f}_{t}(T)=M^{\prime}_{t}(T)\Upsilon^{{\dagger}}h_{t}(T)-A^{\prime}f_{t}(T)-P_{t}(T)Ed_{t}+Qr,\\\
&f_{T}(T)=-P_{T}(T)r.\end{aligned}\right.$ (4.21)

The optimal cost function is given as

$\displaystyle J_{T}^{*}=$
$\displaystyle\frac{1}{2}x^{\prime}_{0}P_{0}(T)x_{0}+{x}^{\prime}_{0}f_{0}(T)+H_{0}(T),$
(4.22)

where

$\displaystyle\dot{H}_{t}(T)=\frac{1}{2}h^{\prime}_{t}(T)\Upsilon^{{\dagger}}h_{t}(T)-d^{\prime}_{t}E^{\prime}f_{t}(T)-\frac{1}{2}r^{\prime}Qr-\frac{1}{2}d^{\prime}_{t}E^{\prime}REd_{t}$
(4.23)

with terminal condition $H_{T}(T)=r^{\prime}P_{T}(T)r$.

###### Proof.

Following the line of Theorem 1, the result can be derived similarly under the
regular condition (3.10). To avoid redundancy, we have omitted this proof
here. ∎

Accordingly, we consider the cost functional over an infinite horizon as
follows

$\displaystyle J=$
$\displaystyle\lim_{T\to\infty}\frac{1}{2T}\int_{0}^{T}[(x_{t}-r)^{\prime}Q(x_{t}-r)+({B}{u}_{t}+{E}d_{t})^{\prime}R({B}{u}_{t}+{E}d_{t})]\mathrm{d}t.$
(4.24)

We now introduce certain definitions and assumptions.

######  Definition 1.

The system $(A,Q^{\frac{1}{2}})$

$\left\\{\begin{aligned} &\dot{x}_{t}=Ax_{t},\\\
&y_{t}=Q^{\frac{1}{2}}x_{t},\end{aligned}\right.$ (4.25)

is detectable if for any $T\geq 0$, the following holds:

$\displaystyle y_{t}=0,\forall 0\leq t\leq
T\Rightarrow\lim_{t\to\infty}x_{t}=0.$

######  Assumption 1.

$d_{t},t\geq 0$ is bounded and $\lim_{t\rightarrow\infty}d_{t}=d.$

######  Assumption 2.

$(A,\sqrt{Q})$ is detectable.

We define the GARE as follows

$\displaystyle 0=$ $\displaystyle
PA+A^{\prime}P+Q-M^{\prime}\Upsilon^{{\dagger}}M,$ (4.26)

where

$\displaystyle\Upsilon=$ $\displaystyle B^{\prime}RB,$ (4.27) $\displaystyle
M=$ $\displaystyle B^{\prime}P.$ (4.28)

Now, consider the following system without disturbances, i.e., the standard
linear quadratic regulation problem:

$\left\\{\begin{aligned}
&min\bar{J}=\frac{1}{2}\int_{0}^{\infty}[x_{t}^{\prime}Qx_{t}+u_{t}^{\prime}B^{\prime}RBu_{t}]\mathrm{d}t,\\\
&s.t.\quad\dot{x}_{t}=Ax_{t}+Bu_{t},\end{aligned}\right.$ (4.29)

where $Q$ and $R$ are both semi-positive definite.

The result of the above problem can be expressed as follows.

######  Lemma 3.

[25] Suppose that Assumption 2 holds and the system (LABEL:5601) can be
stabilized if and only if the GRDE (3.11) converges when $T\rightarrow\infty$
(i.e. $\lim_{T\rightarrow\infty}P_{t}(T)=P$). Furthermore, $P$ is a solution
of the GARE (4.26)–(4.28) and $P\geq 0$. In this case, the stabilizing
controller is

$\displaystyle u_{t}=-\Upsilon^{\dagger}Mx_{t},$ (4.30)

and the optimal cost value is

$\displaystyle\bar{J}^{\ast}=\frac{1}{2}x_{0}^{\prime}Px_{0}.$ (4.31)

We present the main results in this section based on the above analysis.

######  Theorem 2.

Under Assumptions 1 and 2, if the GARE (4.26)-(4.28) has a semi-positive
definite solution $P$, then the system (2.1) is bounded. Under such
conditions, the optimal stabilizing solution can be derived as

$\displaystyle u_{t}=-\Upsilon^{\dagger}Mx_{t}-\Upsilon^{\dagger}h_{t}.$
(4.32)

###### Proof.

The proofs of Theorem 2 can be found in Appendix B. ∎

######  Remark 8.

According to the above analysis, we conclude that the system is stable under
the proposed controller. And recall that solving Problem 1 can minimize the
performance index (2.2) (i.e. $Bu_{t}+Ed_{t}$ is minimized), which means that
the proposed controller guarantees the disturbance rejection performance.

######  Remark 9.

From the above analysis process, it can be seen that the solution of the
uncontrollable problem is due to the application of optimal control with a new
quadratic performance index to stabilize the uncontrollable but detectable
system and minimize the impact of disturbance.

######  Remark 10.

The key idea of this study is to transform mismatched disturbance rejection
control into an LQT problem. Accordingly, in contrast to the method in [20,
16, 13] , where the system must be controllable, the stabilization result in
Theorem 2 is obtained only under the detectable assumption.

######  Remark 11.

Faced with a scenario in which a disturbance is only available at the current
moment, we can using the receding-horizon control method to design a
controller to handle such a disturbance. The specific controller design is as
follows:

$\displaystyle u_{t}=-\Upsilon^{-1}M_{t}x_{t}-\Upsilon^{-1}h_{t},$ (4.33)

where $\Upsilon$, $M_{t}$, and $h_{t}$ satisfy the following equations at time
$t$:

$\left\\{\begin{aligned}
&\dot{P}_{s}=M^{\prime}_{s}\Upsilon^{-1}M_{s}-P_{s}A-A^{\prime}P_{s}-Q,\\\
&\dot{f}_{s}=M^{\prime}_{s}\Upsilon^{-1}h_{s}-A^{\prime}f_{s}-P_{s}Ed+Qr,\\\
&\Upsilon=B^{\prime}RB,\\\
&h_{s}=B^{\prime}f_{s}+B^{\prime}REd,\qquad\qquad\qquad\qquad t\leq s\leq
t+\tau\\\ &d=d_{t},\\\ &M_{s}=B^{\prime}P_{s},\\\
&f_{t+\tau}=P_{t+\tau}r.\end{aligned}\right.$ (4.34)

##  5 Numerical Examples

In this section, two examples are presented from different perspectives,
illustrating the effectiveness of the proposed controller. The first example
emphasizes the mismatched attenuation effect of the proposed method in an
uncontrolled system compared to PID control. The second example is the
application of the proposed method compared to PID control and GESOBC in an
PMDC for disturbance rejection.

###  5.1 Example A: Disturbance rejection for an uncontrollable system

In the case where a system is detectable but uncontrollable, compare the PID
control to verify the effectiveness of the control law (4.33) in rejecting
mismatched disturbance. Consider the system (2.1) with the following
parameters:

$\displaystyle{A}=\begin{bmatrix}-4&0&0\cr 0&3&1\cr
0&-2&-1\end{bmatrix},{B}=\begin{bmatrix}0\cr 1\cr
0\end{bmatrix},{E}=\begin{bmatrix}0\cr 0\cr
1\end{bmatrix},{c}_{o}=\begin{bmatrix}0&0&1\end{bmatrix}.$

######  Remark 12.

It is trivial to determine that the state $x^{1}$ in the above system is
stable but not controllable, and we attempt to demonstrate the superiority of
our proposed controller.

The initial state of the system is
$x_{0}=\begin{bmatrix}1&1&0\end{bmatrix}^{\prime}$ and the disturbance $d=3$
acts on the system from $t=0.5s$. The controller aims to remove the
disturbance from the regulated state $x^{3}=c_{o}x$. In the proposed control
law (4.33), the horizon $\tau$ is set to $0.05s$ and the terminal condition
$P_{t+\tau}=O_{3\times 3}$. The reference $c_{o}r$ is set to $0$ according to
the goals defined above. The weight matrice are selected as $\bar{Q}=10^{4}$
and $R=I_{3\times 3}$. $P_{t}$, $f_{t}$, $h_{t}$, $M_{t}$, and $\Upsilon$ can
be calculated according to (4.34) at every time instance $t$ to derive
$u_{t}$. The proposed control method was compared to PID control to track the
reference and disturbance rejection effects, and the parameters in the PID
method were set to $K_{p}=80$, $K_{i}=400$, and $K_{d}=10$ through optimal
tuning. The simulation results for Example A are presented in Fig. 1.

Figure 1: Simulation result of Example A

In Fig. 1, one can see that state $x^{3}$ achieves disturbance rejection
quickly and stabilization is achieved for the uncontrollable state $x^{1}$.
Therefore, the proposed method is effective for the disturbance rejection than
PID control of uncontrollable systems with mismatched disturbances.

###  5.2 Example B: Application to an PMDC system

When this method is applied to the PMDC speed disturbance rejection, it is
usually necessary to quickly stabilize the speed, that is, to eliminate the
influence of load changes on the speed. In this case, the load variation with
respect to the voltage (control input) is a mismatched disturbance. Existing
PID control and GESOBC methods are mostly used for PMDC system, but both are
difficult to achieve a balance between disturbance rejection and optimal
performance. Therefore, the proposed method is applied to the disturbance
rejection of the speed of PMDC, and compared with the effect of PID control
and GESOBC to demonstrate the effectiveness of the proposed method.

Consider PMDC system [26] to demonstrate the effectiveness of load
(disturbance) variation on speed disturbance immunity, the target system is
defined as follows

$\displaystyle{}\dot{x}(t)=Ax(t)+{B}{u}(t)+E{d}(t)$ (5.35)

with the coefficient matrix

$\displaystyle{A}=\begin{bmatrix}-0.42&106.16\cr
41.67&41.67\end{bmatrix},B=\begin{bmatrix}0\cr
83.33\end{bmatrix},E=\begin{bmatrix}-212.31\cr
0\end{bmatrix},{c}_{o}=\begin{bmatrix}1&0\end{bmatrix}.$ (5.36)

where $x(t)=[w_{m}\quad i_{a}]^{\prime}$ represents the state variables,
${y}(t)=[w_{m}\quad i_{a}]^{\prime}$ is the control output, ${u}(t)=V_{a}(t)$
is the control input, ${d}(t)=T_{L}(t)$ represents the disturbance caused by
load torque changes, and $w_{m}$ is the regulated output. $V_{a}(t)$ is the
armature voltage $(V)$, $T_{L}(t)$ is load torque $(Nm)$, $w_{m}$ is angular
speed $(rad/s)$; $i_{a}(t)$ is armature current $(A)$.

The disturbance in the PMDC system is the measurable load torque. The control
strategy in this paper can be utilized to study the speed control on PMDC
system under variable loads. Disturbance change is $5Nm$ loaded from $0.6s$
action. From (5.35) and (5.36), one can see that the coefficient ratios of the
disturbance and control inputs into different channels of the system are
different with $rank(B,E)>rank(E)$. In other words, the disturbances in the
system are mismatched. The control objective is to eliminate the disturbance
in the output angular speed under variable loads, that is, the angular speed
is maintained at 60 $rad/s$ when the load changes. In the disturbance
rejection control method proposed in Theorem 1, the terminal time $T$ is set
$1.2s$ and the terminal condition $P_{T}=O$ (zero matrix). The weight matrice
are selected as $\bar{Q}=10^{4}$ and $R=I_{3\times 3}$. $P_{t}$, $f_{t}$,
$h_{t}$, $M_{t}$, and $\Upsilon$ can be calculated using (3.17) to obtain
$u_{t}$. The proposed control method was compared to PID control to track the
reference and disturbance rejection effects. According to [16], the state
feedback matrix is chosen as $[-0.8-0.5]$ and the disturbance compensation
gain of the GESOBC method is calculated as $K_{d}=2$. The parameters in the
PID method were set to $K_{p}=0.1$, $K_{i}=2.5$, and $K_{d}=0.09$ through
optimal tuning.

The response curves of the PMDC system obtained using the proposed method, PID
and GESOBC are presented in Fig. 2. Fig. 2 reveals that the proposed control
method achieves a fast and smooth transition from the set point when the
disturbance variation. Therefore, it can be concluded that the proposed method
is superior to GESOBC and PID control for excellent disturbance rejection
performance can reduce the impact on the PMDC system.

These results demonstrate that the proposed method achieves satisfactory
performance in terms of mismatched disturbance rejection. In this case, the
proposed method is more effective than the GESOBC and PID control.

Figure 2: Simulation result of Example B

##  6 Conclusion

By introducing a new quadratic performance index such that the mismatched
disturbance rejection problem was transformed into an LQT problem, the
regulated state to track a reference and minimize the impact of disturbance.
The disturbance rejection controller and the necessary and sufficient
conditions for the solvability of the problem are obtained by solving a FBDE
over a finite horizon. In the case of an infinite horizon, a sufficient
condition for system stability is obtained under detectable condition. It is
noteworthy that this approach weakens the assumption of controllability.
Several examples were presented to illustrate the effectiveness of the
proposed method. Although our proposed controller exhibited excellent
performance, it requires known disturbances. In the future, we will further
study the design of a mismatched unknown disturbance (uncertainty) rejection
controller based on the concepts and methods presented in this paper.

##  7 Appendix

###  7.1 Appendix A: Proof of Theorem 1

###### Proof.

“Necessity”: When Problem 1 admits a unique solution, we prove that
$\Upsilon=B^{\prime}RB>0$.

Assume that

$\displaystyle\lambda_{t}=P_{t}x_{t}+f_{t}.$ (7.37)

Substituting the above formula into (3.9), one can yields that

$\displaystyle
B^{\prime}RBu_{t}+B^{\prime}REd_{t}+B^{\prime}P_{t}x_{t}+B^{\prime}f_{t}=0.$
(7.38)

From the solvability of Problem 1, the regular condition
$\Upsilon\Upsilon^{\dagger}V_{t}=V_{t}$
$(V_{t}=-B^{\prime}P_{t}x_{t}-B^{\prime}REd_{t}-B^{\prime}f_{t})$ is
introduced. Thus, one has

$\displaystyle u_{t}$
$\displaystyle=-\Upsilon^{\dagger}(B^{\prime}P_{t}x_{t}+B^{\prime}REd_{t}+B^{\prime}f_{t})+(I-\Upsilon\Upsilon^{\dagger})L_{t},$
(7.39)

where $L_{t}$ is an arbitrary matrix.

Let $M_{t}=B^{\prime}P_{t}$ and $h_{t}=B^{\prime}f_{t}+B^{\prime}REd_{t}$,
then

$\displaystyle
u_{t}=-\Upsilon^{\dagger}M_{t}x_{t}-\Upsilon^{\dagger}h_{t}-(I-\Upsilon\Upsilon^{\dagger})L_{t}.$
(7.40)

By differentiating both sides of equation (7.37) and combining (3.9) and
(7.40), one has

$\displaystyle\dot{\lambda}_{t}=$
$\displaystyle\dot{P}_{t}x_{t}+P_{t}\dot{x}_{t}+\dot{f}_{t}$ $\displaystyle=$
$\displaystyle\dot{P}_{t}x_{t}+P_{t}{Ax}_{t}+P_{t}{B}{u}_{t}+P_{t}{E}d_{t}+\dot{f}_{t}$
$\displaystyle=$
$\displaystyle\dot{P}_{t}x_{t}+P_{t}{Ax}_{t}-M^{\prime}_{t}\Upsilon^{\dagger}M_{t}x_{t}-M^{\prime}_{t}\Upsilon^{\dagger}h_{t}-M^{\prime}_{t}(I-\Upsilon\Upsilon^{\dagger})L_{t}+P_{t}{E}d_{t}+\dot{f}_{t}.$
(7.41)

Combined with the (3.9) and the arbitrariness of $x_{t}$, it yields

$\displaystyle\dot{P}_{t}$
$\displaystyle=M^{\prime}_{t}\Upsilon^{\dagger}M_{t}-P_{t}A-A^{\prime}P_{t}-Q,$
(7.42) $\displaystyle\dot{f}_{t}$
$\displaystyle=M^{\prime}_{t}\Upsilon^{\dagger}h_{t}+M^{\prime}_{t}(I-\Upsilon\Upsilon^{\dagger})L_{t}-A^{\prime}f_{t}-P_{t}Ed_{t}+Qr.$
(7.43)

From (3.9), the following two boundary value conditions can be derived

$x_{0}=x,f_{T}=-P_{T}r.$

Combining (7.37), (7.42), and (7.43) with FBDEs (3.9), it is not difficult to
find that (7.37) is the solutions of FBDEs.

Note that (7.40) and $\Upsilon=B^{\prime}RB\geq 0$, we know that the $u_{t}$
is uniquely solvable if and only if $\Upsilon$ is invertible (that is,
$\Upsilon>0$). Therefore, $\Upsilon^{\dagger}$ in (7.40), (7.42), and (7.43)
can be replaced by $\Upsilon^{-1}$ yields that:

$\displaystyle u_{t}$
$\displaystyle=-\Upsilon^{-1}M_{t}x_{t}-\Upsilon^{-1}h_{t},$ (7.44)
$\displaystyle\dot{P}_{t}$
$\displaystyle=M^{\prime}_{t}\Upsilon^{-1}M_{t}-P_{t}A-A^{\prime}P_{t}-Q,$
(7.45) $\displaystyle\dot{f}_{t}$
$\displaystyle=M^{\prime}_{t}\Upsilon^{-1}h_{t}-A^{\prime}f_{t}-P_{t}Ed_{t}+Qr.$
(7.46)

Thus, the necessity is proved.

“Sufficiency”: Introduce the identity as follows

$\displaystyle\frac{1}{2}$ $\displaystyle
x^{\prime}_{T}Px_{T}+{x}_{T}^{\prime}f_{T}+H_{T}-\frac{1}{2}x^{\prime}_{0}P_{0}x_{0}-{x}^{\prime}_{0}f_{0}-H_{0}=\int_{0}^{T}\frac{\mathrm{d}}{\mathrm{d}t}[\frac{1}{2}x_{t}^{\prime}P_{t}x_{t}+x_{t}^{\prime}f_{t}+H_{t}]\mathrm{d}t.$
(7.47)

Furthermore, using (3.9), (7.45), and (7.46), the above formula can be
rewritten

$\displaystyle\frac{1}{2}$ $\displaystyle
x^{\prime}_{T}Px_{T}+{x}_{T}^{\prime}f_{T}+H_{T}-\frac{1}{2}x^{\prime}_{0}P_{0}x_{0}-{x}^{\prime}_{0}f_{0}-H_{0}$
$\displaystyle=$
$\displaystyle\int_{0}^{T}[\frac{1}{2}\dot{x}_{t}^{\prime}P_{t}x_{t}+\frac{1}{2}x_{t}^{\prime}\dot{P}_{t}x_{t}+\frac{1}{2}x_{t}^{\prime}P_{t}\dot{x}_{t}+\dot{x}_{t}^{\prime}f_{t}+x_{t}^{\prime}\dot{f}_{t}+\dot{H}_{t}]\mathrm{d}t$
$\displaystyle=$ $\displaystyle\int_{0}^{T}[\frac{1}{2}u^{\prime}_{t}\Upsilon
u_{t}+u^{\prime}_{t}M_{t}x_{t}+\frac{1}{2}x_{t}^{\prime}M^{\prime}_{t}\Upsilon^{-1}M_{t}x_{t}+u^{\prime}_{t}h_{t}-u^{\prime}_{t}B^{\prime}REd_{t}+d^{\prime}_{t}E^{\prime}f_{t}$
$\displaystyle+x_{t}^{\prime}M^{\prime}_{t}\Upsilon^{-1}h_{t}+x_{t}^{\prime}Qr+\dot{H}_{t}-\frac{1}{2}x_{t}^{\prime}Qx_{t}-\frac{1}{2}u^{\prime}_{t}\Upsilon
u_{t}]\mathrm{d}t.$ (7.48)

Putting (3.19) into the above equation and noting the terminal condition
$f_{T}=-P_{T}r$, one has

$\displaystyle J=$
$\displaystyle\frac{1}{2}x^{\prime}_{0}P_{0}x_{0}+{x}^{\prime}_{0}f_{0}+H_{0}$
$\displaystyle+\int_{0}^{T}\frac{1}{2}[u_{t}+\Upsilon^{-1}M_{t}x_{t}+\Upsilon^{-1}h_{t}]^{\prime}\Upsilon[u_{t}+\Upsilon^{-1}M_{t}x_{t}+\Upsilon^{-1}h_{t}]\mathrm{d}t.$
(7.49)

The unique solvability of Problem 1 is easily derived based on the positive
definiteness of $\Upsilon$.

Sufficiency is demonstrated. The proof is complete.

∎

###  7.2 Appendix B: Proof of Theorem 2

###### Proof.

Suppose the GARE (4.26)-(4.27) has a solution $P\geq 0$. We will prove the
bounded stabilization of the system (2.1). The following are explicit
expressions for $h_{t}$ and $f_{t}$:

$\displaystyle
h_{t}(T)=B^{\prime}\int_{0}^{T}e^{\bar{A}_{t}(T)(t-\tau)}F_{\tau}(T)d_{\tau}\mathrm{d}\tau+B^{\prime}\mathcal{R}_{t}(T)r+B^{\prime}REd_{t},$
(7.50) $\displaystyle
f_{t}(T)=\int_{0}^{T}e^{\bar{A}_{t}(t-\tau)}F_{\tau}(T)d_{\tau}\mathrm{d}\tau+\mathcal{R}_{t}(T)r,$
(7.51)

where

$\displaystyle\bar{A}_{t}(T)=$ $\displaystyle
A^{\prime}-M^{\prime}_{t}(T)\Upsilon^{-1}B^{\prime},$ $\displaystyle
F_{t}(T)=$ $\displaystyle(M^{\prime}_{t}(T)\Upsilon^{-1}B^{\prime}R-P_{t})E,$
(7.52) $\displaystyle\mathcal{R}_{t}(T)=$
$\displaystyle\int_{0}^{T}e^{\bar{A}_{t}(T)(t-\tau)}Q\mathrm{d}\tau,$ (7.53)
$\displaystyle{f}_{T}(T)=$ $\displaystyle-P_{T}(T)r.$

First, we demonstrate the boundedness of $h_{t}$. From Lemma 3,
$\rho(A-B\Upsilon^{\dagger}M)<0$. Considering the convergence of $P_{t}(T)$,
we can find that $F_{t}(T)$ in (7.52) and $\mathcal{R}_{t}(T)$ in (7.53) are
convergent. Therefore, there exist constants
$\mathcal{C}_{F},\mathcal{C}_{\mathcal{R}}$ satisfying
$F_{t}\leq\mathcal{C}_{F},\mathcal{R}_{t}\leq\mathcal{C}_{\mathcal{R}}$.

From (7.50) and Assumption 1, we have

$\displaystyle\lVert\int_{0}^{\infty}e^{\bar{A}_{t}(t-\tau)}$ $\displaystyle
F_{\tau}d_{\tau}\mathrm{d}\tau\lVert\leq\int_{0}^{\infty}\lVert
e^{\bar{A}_{t}(t-\tau)}\lVert\lVert F_{\tau}\lVert\lVert
d_{\tau}\lVert\mathrm{d}\tau\leq\mathcal{C}_{F}\bar{d}\int_{0}^{\infty}\lVert
e^{\bar{A}_{t}(t-\tau)}\lVert\mathrm{d}\tau\leq\mathcal{C},$ (7.54)

where $\rho(\bar{A}_{t})<0$ guarantees the boundedness of
$\int_{0}^{\infty}\lVert e^{\bar{A}_{t}(t-\tau)}\lVert\mathrm{d}\tau$.
Therefore, $h_{t}$ is bounded. Similarly, $f_{t}$ is bounded.

Note that when $u_{t}=-\Upsilon^{\dagger}Mx_{t}-\Upsilon^{\dagger}h_{t}$, we
obtain

$\displaystyle\dot{x}_{t}=(A-B\Upsilon^{\dagger}M)x_{t}-B\Upsilon^{\dagger}h_{t}.$
(7.55)

From the boundedness of $h_{t}$ and $\rho(A-B\Upsilon^{\dagger}M)<0$, we find
that the system (2.1) has bounded stability with
$u_{t}=-\Upsilon^{\dagger}Mx_{t}-\Upsilon^{\dagger}h_{t}$. ∎

## References

  * [1] W.-H. Chen, J. Yang, L. Guo, and S. Li, “Disturbance-observer-based control and related methods—An overview,” IEEE Transactions on Industrial Electronics, vol. 63, no. 2, pp. 1083–1095, 2015.
  * [2] S. Li, J. Yang, W.-H. Chen, and X. Chen, Disturbance observer-based control: methods and applications.  CRC Press, 2014.
  * [3] B.-Z. Guo and F.-F. Jin, “The active disturbance rejection and sliding mode control approach to the stabilization of the euler–bernoulli beam equation with boundary input disturbance,” Automatica, vol. 49, no. 9, pp. 2911–2918, 2013.
  * [4] J. Han, “From PID to active disturbance rejection control,” IEEE transactions on Industrial Electronics, vol. 56, no. 3, pp. 900–906, 2009.
  * [5] Y. Huang, W. Xue, and X. Yang, “Active disturbance rejection control: Methodology, theoretical analysis and applications,” in Proceedings of the 29th Chinese Control Conference, pp. 6083–6090, 2010.
  * [6] S. Zhao and Z. Gao, “Modified active disturbance rejection control for time-delay systems,” ISA transactions, vol. 53, no. 4, pp. 882–888, 2014\.
  * [7] Y. Shtessel, C. Edwards, L. Fridman, A. Levant, et al., Sliding mode control and observation, vol. 10.  Springer, 2014.
  * [8] K. D. Young, V. I. Utkin, and U. Ozguner, “A control engineer’s guide to sliding mode control,” IEEE Transactions on Control Systems Technology, vol. 7, no. 3, pp. 328–342, 1999.
  * [9] W.-H. Chen, “Nonlinear disturbance observer-enhanced dynamic inversion control of missiles,” Journal of Guidance, Control, and Dynamics, vol. 26, no. 1, pp. 161–166, 2003.
  * [10] D. Chwa, J. Y. Choi, and J. H. Seo, “Compensation of actuator dynamics in nonlinear missile control,” IEEE Transactions on Control Systems Technology, vol. 12, no. 4, pp. 620–626, 2004.
  * [11] Y. A. I. Mohamed, “Design and implementation of a robust current-control scheme for a PMSM vector drive with a simple adaptive disturbance observer,” IEEE Transactions on Industrial Electronics, vol. 54, no. 4, pp. 1981–1988, 2007.
  * [12] A. Isidori, Nonlinear control systems: an introduction.  Springer, 1985.
  * [13] A. Castillo, P. García, R. Sanz, and P. Albertos, “Enhanced extended state observer-based control for systems with mismatched uncertainties and disturbances,” ISA Transactions, vol. 73, pp. 1–10, 2018.
  * [14] S. Chen, W. Bai, and Y. Huang, “Adrc for systems with unobservable and unmatched uncertainty,” in Proceedings of the 35th Chinese control conference, pp. 337–342, IEEE, 2016.
  * [15] D. Ginoya, P. Shendge, and S. Phadke, “Sliding mode control for mismatched uncertain systems using an extended disturbance observer,” IEEE Transactions on Industrial Electronics, vol. 61, no. 4, pp. 1983–1992, 2013\.
  * [16] S. Li, J. Yang, W.-H. Chen, and X. Chen, “Generalized extended state observer based control for systems with mismatched uncertainties,” IEEE Transactions on Industrial Electronics, vol. 59, no. 12, pp. 4792–4802, 2011\.
  * [17] Z.-H. Wu, F. Deng, B.-Z. Guo, C. Wu, and Q. Xiang, “Backstepping active disturbance rejection control for lower triangular nonlinear systems with mismatched stochastic disturbances,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 52, no. 4, pp. 2688–2702, 2021.
  * [18] J. Yang, S. Li, and W.-H. Chen, “Nonlinear disturbance observer-based control for multi-input multi-output nonlinear systems subject to mismatching condition,” International Journal of Control, vol. 85, no. 8, pp. 1071–1082, 2012.
  * [19] J. Yang, S. Li, and X. Yu, “Sliding-mode control for systems with mismatched uncertainties via a disturbance observer,” IEEE Transactions on Industrial Electronics, vol. 60, no. 1, pp. 160–169, 2012.
  * [20] R. V. Gandhi and D. M. Adhyaru, “Hybrid extended state observer based control for systems with matched and mismatched disturbances,” ISA Transactions, vol. 106, pp. 61–73, 2020.
  * [21] W.-C. Yang and M. Tomizuka, “Disturbance rejection through an external model for nonminimum phase systems,” Journal of Dynamic Systems, Measurement, and Control, vol. 116, pp. 39–44, 03 1994.
  * [22] M. Tomizuka, K. Chew, and W. Yang, “Disturbance rejection through an external model,” Journal of Dynamic Systems, Measurement, and Control, vol. 112, pp. 559–564, 12 1990.
  * [23] T. Pengliang, “Feedback linearization of mimo nonlinear system with measurable disturbance,” in Proceedings of the 12th International conference on measuring technology and mechatronics automation, pp. 744–749, 2020.
  * [24] H. Guo, D. Cao, H. Chen, Z. Sun, and Y. Hu, “Model predictive path following control for autonomous cars considering a measurable disturbance: Implementation, testing, and verification,” Mechanical Systems and Signal Processing, vol. 118, pp. 41–60, 2019.
  * [25] Q. Qi, H. Zhang, and Z. Wu, “Stabilization control for linear continuous-time mean-field systems,” IEEE Transactions on Automatic Control, vol. 64, no. 8, pp. 3461–3468, 2018.
  * [26] P. C. Krause, O. Wasynczuk, S. D. Sudhoff, and S. D. Pekarek, Analysis of electric machinery and drive systems, vol. 75.  John Wiley & Sons, 2013.


# Bootstrapping Relation Extractors
using Syntactic Search by Examples

Matan Eyal1 Asaf Amrami1, 2 Hillel Taub-Tabib1 Yoav Goldberg1, 2
1Allen Institute for AI, Tel Aviv, Israel
2Bar Ilan University, Ramat-Gan, Israel
<EMAIL_ADDRESS>
###### Abstract

The advent of neural-networks in NLP brought with it substantial improvements
in supervised relation extraction. However, obtaining a sufficient quantity of
training data remains a key challenge. In this work we propose a process for
bootstrapping training datasets which can be performed quickly by non-NLP-
experts. We take advantage of search engines over syntactic-graphs (Such as
Shlain et al. (2020)) which expose a friendly by-example syntax. We use these
to obtain positive examples by searching for sentences that are syntactically
similar to user input examples. We apply this technique to relations from
TACRED and DocRED and show that the resulting models are competitive with
models trained on manually annotated data and on data obtained from distant
supervision. The models also outperform models trained using NLG data
augmentation techniques. Extending the search-based approach with the NLG
method further improves the results.

##  1 Introduction

The goal of Relation Extraction (RE) is to find and classify instances of
certain relations in raw text. We denote a binary relation instance, i.e. a
relation instance with two arguments, with a tuple
$\bm{x}=(\bm{s},e^{1},e^{2},r)$, where $\bm{s}=[w_{0}\cdots w_{n}]$ is a
sequence of sentence tokens, $e^{1},e^{2}$ are entity mentions within $\bm{s}$
corresponding to the first and second relation argument, respectively, and
$r\in R\cup\\{\varnothing\\}$ is a relation label from a set of predefined
relations of interest, or an indication of ‘no-relation’. In binary
classification our goal is to classify whether, according to $\bm{s}$, the
entity mentions, $e^{1}$ and $e^{2}$, satisfy $r$, the relation label. For
such classification we require a training dataset $X$, comprised of $X_{p}$, a
set of positive examples, representing the relation of interest, and $X_{n}$,
a set of negatives examples.

The success of recent papers Soares et al. (2019); Murty et al. (2020) in
supervised RE is fueled by advances in deep learning, but also, crucially, by
the availability of a large training set such as TACRED Zhang et al. (2017),
containing tens of thousands of training examples. For most relations of
interest, such training data is not available.

In this work we examine methods to inexpensively construct $X_{p}$ and
$X_{n}$, in cases where a training set is not available. We are especially
interested in constructing the positive set, $X_{p}$.

In contrast to common NLP tasks like POS tagging, entity extraction and
dependency parsing, the task of relation extraction exhibits a much larger
degree of label sparsity. For some relations, even when considering only
sentences with entities of the relevant types, the ratio between positive and
negative examples is highly skewed toward the latter and obtaining a modest
amount of positive examples will require a laborious annotation effort (see
§3). While manual annotation of large datasets is a viable approach, it
typically requires contracting a team of professional annotators Doddington et
al. (2004); Ellis et al. (2015) or crowd workers Zhang et al. (2017); Yao et
al. (2019) and is not well suited for smaller projects or for ad-hoc
extraction tasks.

Our main contribution in this paper is a new methodology built on top of
Shlain et al. (2020) for cheaply obtaining large datasets (§6). Shlain et al.
(2020) proposed a syntactic search engine that given a lightly annotated
example sentence, retrieves new sentences with a similar syntactic structure
from a pre-annotated dataset. Our syntactic search bootstrapping method
requires a small number of manually curated positive example sentences. Then
the search engine matches are used as training data for ML models. We evaluate
this approach comparing to human annotated data of varying sizes.

While this method shows promising results with very few user input examples,
we also test the impact on performance when more examples are used. One
technique for obtaining an abundance of examples uses recent Natural Language
Generation (NLG) models (§7.1). It has been shown in recent papers Wei and Zou
(2019); Anaby-Tavor et al. (2019); Kumar et al. (2020); Amin-Nejad et al.
(2020); Russo et al. (2020) that generating abundance of training examples can
improve classifier performance. We aim to check whether this can improve our
syntactic search method as well.

We evaluate the proposed methodologies by training DL classifiers on the
obtained data.

##### We show that:

(1) Syntactic patterns are competitive at bootstrapping training data for ML,
even with as little as 3 patterns;
(2) Training DL models over the output of syntactic patterns can significantly
improve both recall and F1 over a rule based approach which uses the patterns
directly;
(3) Training ML models over the output of syntactic patterns performs better
than training models over recently popular NLG data augmentation techniques;
(4) Augmenting the output of syntactic patterns using NLG techniques is often
helpful;
(5) Different relations benefit from different strategies.

The code for all our experiments alongside the generation outputs is publicly
available111 github.com/mataney/BootstrappingRelationExtractors.

##  2 Related Work

Distant Supervision. Since its introduction, Distant Supervision Mintz et al.
(2009) has established itself as a viable alternative to manual annotation.
Distant Supervision assumes the availability of a knowledge base (KB) of
$\langle e^{1},r,e^{2}\rangle$ triplets where $e^{1},e^{2}$ are entities known
to satisfy relation $r$. To obtain training examples for a relation $r$, we
sample sentences from a large background corpus: sentences which include
entity pairs listed in the KB as satisfying $r$ are labeled positive, the
remaining sentences are labeled negative (potentially after satisfying
additional constraints). While effective in some cases, the reliance on large
pre-existing KBs is a significant limitation. Such KBs are not usually
available and the cost of constructing them is high.

Bootstrapping from Rules, Snorkel. To eliminate the reliance on external KBs,
Angeli et al. (2015) used the predictions of a rule based extractor on a large
corpus to train a first iteration of a statistical extractor. They then
continued to refine the extractor through self-training.

Another system which can optionally utilize rules instead of external KBs is
Snorkel Ratner et al. (2017). Snorkel is implementing the data-programming
paradigm Ratner et al. (2016) where ML models are trained in three stages: (i)
users write labeling functions that weakly label data points using arbitrary
heuristics (e.g. extraction rules); (ii) the system learns a re-weighted
combination of the labeling functions by explicitly modeling the actual
distribution of each class. The results are often precise but low-recall; and
(iii) The system uses discriminative models to increase recall while
preserving precision.

The techniques used by Angeli et al. (2015) and Snorkel can be effective in
increasing the accuracy of the initial labeling rules, but coming up with
“good enough" initial rules remains a major challenge. In this sense, the
search-based methods suggested in this work for bootstrapping RE datasets are
complimentary and can be plugged in as a first step in these multi-step
solutions.

Only few papers can be directly compared to our paper and use matches as
training-data for ML classifiers. One paper similar in that sense is Angeli et
al. (2013) which claims that training a classifier using search-based examples
works better than traditional bootstrapping methods. See §6.2 for further
compression with Angeli et al. (2013).

Augmentation Through Generation. Similarly to our Example Generation approach,
recent papers Anaby-Tavor et al. (2019); Kumar et al. (2020) suggest using
pre-trained language models for data augmentation. In both these papers, the
authors suggest prepending class labels to generative models in order to
augment the number of instances for classes with a small number of examples.
In contrast to these papers we use language models in a zero-shot context, and
rather than requiring existing labeled examples of the relevant relation, we
propose to manually label the generated samples.

##  3 The data annotation challenge

In contrast to linguistic annotation tasks such as parts-of-speech, syntactic-
trees or semantic roles, annotating data for relation-extraction does not
require special expertise. Annotation can be easily performed by a motivated
native speaker of the language (in case of "every-day" relations such as those
available in TACRED and DocRED) or by a domain expert (in case of
"specialized" relations such as in biomedicine or law). Annotating a given
sentence for a given relation takes roughly the time it takes to read and
understand the sentence. So what stops us from obtaining large amounts of
annotated data for ML?

The annotation challenge lies in _relation sparsity_ in the wild. In an
attempt to get a perspective on this issue, let’s consider the _founded-by_
relation between a PERSON and an ORG, as attested in the TACRED corpus.
Assuming we consider only sentences that contain both a person mention and an
organization mention, how many sentences do we have to annotate before we
reach, for example, 10 positive examples? The TACRED training set has 124
_founded-by_ instances, as well as 6947 "negative" instances with matching
entity types ("negative" examples are either other relations, or _no-
relation_). This 1-out-of-57 ratio indicates that we will likely sample 56
"negative" sentences before hitting a positive instance.222See Appendix A for
similar distributions over all relations. This ratio is overly optimistic, as
the annotations in the TACRED corpus are already very skewed in favor of
positive examples. Even under this very optimistic scenario, we will need to
annotate 570 sentences to recover 10 positive examples. The cost of
annotation, then, is not in annotating each individual positive sentence, but
in finding the sentences to annotate in the first place. Therefore, we should
seek for methods that point towards probable positive instances.

In this paper, we present two methods, the first returns close to 1-out-of-1
positive ratio, although with low syntactic diversity, and a second method
with roughly 1-out-of-3 positive ratio.

##  4 Problem Statement and Setup

We are interested in the problem of obtaining a relation classifier for a
binary relation, when no a-priori annotated training data for this relation is
available. We seek a methodology that will allow to create an effective
extractor, using a minimal amount of data annotation effort.

We compare four approaches – manual annotation, syntactic-search, manual
annotation over generated examples, and a combination of the last two – to be
described in later sections. Here, we discuss setup which is shared to all
experiments.

In order to evaluate the methodology on multiple datasets with similar
relations, we chose a set of relations that appear in both the TACRED Zhang et
al. (2017) and DocRED Yao et al. (2019) datasets with at least 50 development
examples333org:country of headquarters, org:founded by, per:children, per:city
of death, per:date of death, per:origin, per:religion, per:spouse for TACRED,
and similarly headquarters location, founded by, child, place of death, date
of death, country of origin, religion, spouse for DocRED..

To quantify the performance of our methodology we assess it comparing to
varying amounts of manually annotated data. In our settings, large amounts of
supervised examples represent upper bound for our bootstrapping methods and
are not expected.

While relation extraction is often considered as a multi-class classification
problem (“find the occurrences of any of these possible relations”), we
instead treat the relations separately, training a binary classifier for each
one. We believe this is more representative of a user who wishes to target a
low number of relations, who is likely to conduct data collection and
evaluation for one relation at a time.
Obtaining Negative Examples  When training a binary classifier, it is required
to include a set of negative examples alongside the list of positive examples.
In all our experiments we obtain negative examples by looking for sentences
that contain entity types that are compatible with the relation (i.e, for the
_founded-by_ relation we sample sentences that include both a PERSON and an
ORG). In our syntactic based methods we sample from the same domain as our
positive examples (Wikipedia) and then filter this list by removing sentences
in which the entities are connected by a syntactic pattern which is attested
by the positive examples. For the supervised baselines of various sizes, we
obtain negative examples by sampling them from the annotated training set,
without replacement.444 The positive to negative ratio in training data has an
effect on the resulting model’s quality. We experimented with positive-to-
negative ratios of 1, 5, 10 and 20, as well as with a “match the dev-set”
ratio. We found a ratio of 10 negative examples for each positive sentence to
performs well.
Datasets  We used two datasets to explore our different methods. TACRED Zhang
et al. (2017), a large-scale multi-class relation extraction dataset built
over newswire and web text. And DocRED Yao et al. (2019), a dataset for
document level RE, and similarly designed for multi-class prediction. Per our
setup above, we changed the setting of both datasets to per relation binary
classification. As our main goal in this paper is to evaluate different
bootstrapping methods, and not novel methods for document-level relation
extraction, we chose to include only instances with single supporting sentence
in DocRED (i.e. sentence level relations). As DocRED’s labelled test set is
not publicly available, we used the development set as our test set and used
20% of the train set as development set.
Models  Our classifiers throughout the following experiments are based on the
Entity Markers architecture Soares et al. (2019). In the paper, the authors
proposed wrapping the relation arguments with marker tokens (e.g.
$[E1_{start}]$ John $[E1_{end}]$ was born in $[E2_{start}]$ 1948
$[E2_{end}]$). The altered text is then passed as input to a BERT model Devlin
et al. (2018) where the relation between the two entities is represented by
the concatenation of the final hidden states corresponding to their respective
start tokens. Finally, this representation is fed into a classification head
and the model is fine-tuned for relation classification. cf. Soares et al.
(2019) for more details. We use a similar model with the exception that we use
a more recent pretrained language model, RoBERTa Liu et al. (2019), and
perform binary, rather than multi-class, classification.

In all of the following experiments we trained our model with 3 different
random seeds to lower variance introduced to the model with different
initializations, and report the average score. At inference time we set the
prediction threshold value for the test set to be the cut-off value that
maximized F1 over the development set.

##  5 Manual Annotation Baseline

Setup. Our comparison point throughout the paper is a model trained on
traditionally-collected annotated data. We sample increasing-sized annotated
sets from TACRED and DocRED, containing 55, 110, 220, 550, and 1100 examples.
These correspond to 5, 10, 20, 50, 100 positive examples with 50, 100, 200,
500, 1,000 negatives examples. Additionally, we measure the performance on
these datasets when using all available positive examples for each relation.

Results Listed in the top rows of Table 1, averaged over all relations.
Unsurprisingly, increasing the number of examples increases performance, with
the exception of DocRED on which using all positive labels performs slightly
worse than using 100 sampled positive examples for each relation, we attribute
this to sampling noise. DocRED scores are generally lower than TACRED scores.
This is because of the way we constructed the development and test sets: while
in TACRED’s development set each sentence includes a single entity pair with a
single relation, in DocRED, we pass all possible sentences with entity pairs
of the same type as the evaluated relation as possible candidates. This
dramatically increases the number of candidates, and by that of possible type
I errors. Moreover, as we included only examples with exactly one supporting
sentence, the number of positive examples is low for some of the relations.
All of this effects DocRED classification scores comparing to TACRED.

Importantly, in all these experiments, the number of annotated examples used
is significantly higher than the number used in our Syntactic Search
experiments (3 examples in total).

Figure 1: Flow of the Syntactic Search by Example method. For details, see §6.

##  6 Syntactic Search by Example

We consider this section to be the main contribution of the work. We show
that:
(i) with modern DL modeling, effective relation extractors can be trained
using sentences derived from less than a handful of syntactic patterns; and
(ii) through the use of by-example syntactic search engines, one can construct
these patterns very quickly, without needing to understand syntax.

To explain the suggested workflow, let’s consider a user who wants to train a
relation extraction binary classifier for the _founded by_ relation, and has a
single example sentence, “Paul founded Microsoft in April 1975”. Patterns over
syntactic structures and entity types are very effective for deriving high-
precision extraction templates. For example, searching for sentences
containing the word “founded” with an _nsubj_ dependency of type PERSON and
_dobj_ dependency of type ORG, will return many matches for the _founded-by_
relations.

There are two issues with this approach (1) while high-precision, the recall
of the patterns is low; and (2) syntactic patterns require both linguistic and
computational expertise to specify and execute.

The premise of this paper is that the low recall can be offset by machine
learning. The sentences resulting from syntactic search over a few patterns
are diverse enough that an ML model trained over them manages to generalize
from the specific syntactic pattern and identify a broader range of cases,
increasing recall substantially. We show this is indeed the case.

To overcome the need for linguistic expertise we propose using a by-example
syntactic search engine Shlain et al. (2020)555https://spike.apps.allenai.org
which allows users to execute syntactic queries based on example sentences:
the user enters a sentence satisfying the relation of interest and annotates
it with light markup indicating the arguments and the trigger words. The
system then automatically translates the markup into a syntactic pattern,
matches it against a large pre-annotated corpus (e.g. all Wikipedia
sentences), and returns results. The user does not need to be familiar with
syntactic formalisms or with advanced NLP.

Method | TACRED | DocRED
---|---|---
Annotated 5+50 | 0.097 | 0.140
Annotated 10+100 | 0.136 | 0.215
Annotated 20+200 | 0.266 | 0.271
Annotated 50+500 | 0.458 | 0.311
Annotated 100+1000 | 0.516 | 0.321
Annotated All | 0.569 | 0.306
Pattern Based RE (3 qrs) | 0.128 | -
Synt. Search (3 queries) | 0.443 | 0.266
Example Generation | 0.439 | 0.109
Search + Generation | 0.491 | 0.277

Table 1: Average test F1 score over all relations. Pattern Based RE was given
3 positive patterns. Synt. Search is trained on data created from same 3
patterns. The Annotated experiments are denoted by the number of positive
examples + negative examples.

###  6.1 By-example Patterns for Collecting Training Data

Fig. 1 demonstrates the user process. Starting with the sentence _Paul founded
Microsoft in April 1975_ , the user marks _Paul_ as _e1_ (e1:) with an entity-
type restriction of PERSON ([e=PER]), _Microsoft_ as _e2_ (e2:) with an
entity-type ORG ([e=ORG]), and _founded_ as a trigger word ($founded). The
SPIKE system translates the query into a syntactic graph, which is then
matched against Wikipedia, returning 11,345 sentences matching the pattern
(note that the word ‘founded’ is matched lexically, while Paul and Microsoft
become place holders for any person and any organization that adhere to the
syntactic configuration). A subset of the returned sentences is then used as
positive examples for model training.

While 11,345 cases make an impressive training set, these sentences share the
same core syntactic configuration, and classifiers, trained on these matches,
will not necessarily generalize well. The matches will also share the exact
same lexical predicate (“founded”). The lack of lexical diversity of the
predicate can be expanded by the user by supplying alternative words, perhaps
aided by distributional similarity methods such as word2vec, or by querying a
bi-LM such as BERT Devlin et al. (2018) (§6.2.1). To counter the lack of
structural diversity the user can supply additional patterns, derived from
example sentences. For example, the user may supply also
‘[${}_{e_{2}}$Microsoft]’s founder [${}_{e_{1}}$Paul]’ (possessive
construction) and ‘[${}_{e_{2}}$Microsoft] was founded by [${}_{e_{1}}$Paul]’
(passive) as additional patterns (§6.2).

###  6.2 Experiments and Results

Setup For each relation, we select 3 representative sentences and annotate
them based on the process described above666In this experiment, the selection
of representative sentences is based on a heuristic process: we intuitively
conceive of basic sentences exemplifying the relation, construct the
corresponding Spike queries and briefly validate the number and quality of the
returned results. We limit the number of seed examples to 3 since we believe
coming up with 3 examples should be simple even for non-experts. In §7.1 we
show that using more seed examples can further improve performance.. We do not
perform any lexical expansion of trigger words beyond the initial pattern at
this point. The queries are processed by SPIKE Shlain et al. (2020) and the
results are used as positive instances in the generated training set. A full
list of the SPIKE queries we used can be found in appendix D, Table
LABEL:tab:positive_patterns.

We also compare the TACRED classifier to a rule based extractor which uses the
syntactic queries directly. Each syntactic query is added as a syntactic
pattern to this extractor: any sentence which satisfies one of the syntactic
patterns is labeled as a positive instance; sentences which do not satisfy any
of the patterns are labeled negative.

Results Listed in the _Synt. Search_ and _Pattern Based RE_ rows of Table
1777Results correspond to 100+1,000 (TACRED) and 1,000+10,000 (DocRED)
examples, for results and discussions of different dataset sizes, see Appendix
B., _Pattern Based RE_ , using just the 3 patterns per relation, achieves a
very low F-score of 12.8%, due to low recall. However, this is already
competitive with training a classifier on 5-10 positive examples per relation.
Training a classifier on the extracted relations increases the scores
significantly, to 44.3$F_{1}$ on TACRED and 26.6$F_{1}$ on DocRED, approaching
supervised training on 50+500 annotations (for TACRED) or 20+200 annotations
(for DocRED). This result demonstrates that training an ML model over the
output of a rule based model can significantly improve performance, echoing
similar conclusions in Angeli et al. (2013). Interestingly, Angeli et al.
(2013) used a total of 4,697 patterns across 41 relations, an average of 114
patterns per relation. We demonstrate that by applying syntactic patterns to a
large corpus and using modern DL classifiers, results competitive with manual
annotation baselines can be reached with as few as 3 syntactic rules.

Dataset | Predicates | 100 | 500 | 1000
---|---|---|---|---
TACRED | One Trig. | 0.487 | 0.459 | 0.461
Trig. List | 0.517 | 0.490 | 0.478
DocRED | One Trig. | 0.290 | 0.336 | 0.338
Trig. List | 0.316 | 0.338 | 0.337
Table 2: F1 scores for founded by, child, place of death and date of death and
spouse when expanding the triggers list for the Syntactic Search “by Example"
method.

####  6.2.1 Syntactic Search with Trigger Expansion

Setup Constructing queries from 3 seed sentences produces retrieved sentences
with low lexical diversity. e.g. if all the seed sentences for _founded-by_
use the word “founded” to express the relation, then all retrieved sentences
will likewise include the word “founded”, and exclude alternatives like
“established”, “formed”, “started”, etc.

In this experiment we generalize the seed queries to allow a list of trigger
words rather than a single word. We consider only relations which include a
lexical trigger in their seed patterns888per:children, per:date of death,
org:founded by, per:city of death and per:spouse, and DocRED’s child, date of
death, founded by, place of death and spouse. Alternative triggers are
selected by reviewing the closest words to the original triggers in word2vec’s
embedding space Mikolov et al. (2013). Appendix C includes the lists of
alternative lexical triggers used. We train classifiers on 100+1000, 500+5,000
and 1,000+10,000 examples obtained from these expanded-trigger queries.

Results As illustrated in Table 2, adding alternative triggers improves
results across all sample sizes for TACRED and for the 100+1000 size in
DocRED.

##  7 Augmenting Syntactic patterns with Natural Language Generation

We showed how the Syntactic Search by Example method works with only a few
human annotated examples. In this section we would like to pursue NLG based
methods to expand the number of exemplary patterns. Generative language
models, compared to other methods for data augmentation (e.g. Iterative
bootstrapping and distant supervision) are highly accessible and require low
technical expertise (sometimes passing a prompt is enough). Moreover, recent
papers Wei and Zou (2019); Anaby-Tavor et al. (2019); Kumar et al. (2020);
Amin-Nejad et al. (2020); Russo et al. (2020) report high impact of such
models for the closely related Data Augmentation task. We therefore present
numerous methods that take advantage of such models for RE bootstrapping.

First we show how a user can produce a high number of generated sentences
using GPT2 Radford et al. (2019). Then we demonstrate how the generated
sentences can be integrated in the Syntactic Search by Example method (§7.1).
Finally, in order to validate the necessity of the syntactic search in this
flow we compare it to feeding the raw generations as inputs to a classifier
(§7.2).

### Generating Examples LM

##### The user-flow

Depicted in Fig. 2: The user enters a relation prompt (“Paul founded
Microsoft”), to which the system responds by returning sentences that express
the same relation. While not all returned sentences express the relation, many
of them do. To filter out out-of-relation sentences the user goes through the
list until she identifies a predefined number of positive examples (Here we
used 100 sentences). In our experiments we encountered 1 positive example for
every 3 examples annotated. This 1-out-of-3 ratio is significantly better than
blindly sampling from a corpus (1-out-of-57, see §3), and by that can
considerably save annotation time. For each example, the user marks the
relevant entities, and optionally also the trigger word (the main word
indicating the relation). These examples are then used as additional input
examples to the syntactic search engine (§7.1) or as train datasets for ML
models (§7.2).

Figure 2: Flow of sampling examples from conditional language model. The
“Syntactic Search" step corresponds to §7.1, while skipping this step,
corresponds to §7.2.

##### Technical details

We begin with a large pre-trained LM (we use GPT2-medium Radford et al.
(2019)), and fine-tune it to the generation task. The method assumes the
availability of relation-annotated data, though its relations do not need to
overlap with the ones we are attempting to extract (in our case, we ensured
the groups are distinct). The approach can be considered as an instance of
transfer-learning, where we attempt to transfer the example-generation
knowledge from the training relations to novel relations. Given the annotated
RE dataset, we consider positive examples of the form
$(\bm{s},e_{1},e_{2},r)$, where $r\in R$. We transform each instance to a
conditioned LM training example, in which the LM sees a prefix (prompt) and
should complete it. In our case the prompt is derived from $(e_{1},e_{2},r)$,
followed by a special symbol, and we train the LM to produce the corresponding
sentence $\bm{s}$. To derive the prefix we apply a pre-defined _template_
associated with each relation $r$999In our experiments, we use on average 3
different templates for each relation type, so a single annotated relation
example will result in 3 (on average) different fine-tuning examples for the
LM, each with a different prompt.. The template has two slots to be filled
with the entities $e_{1}$ and $e_{2}$. For example, a template for the
_founded-by_ relation can take the form $[e_{2}]$ _founded_ $[e_{1}]$. We then
fine-tune GPT2 on these training examples. At inference time, the user
provides a single prompt based on their desired relation.

Given the user prompt, we generate 1000 sentences with nucleus sampling
Holtzman et al. (2019) of $0.99$ and length of up to 50 tokens. We annotate
the generated sentences until reaching 100 positive instances (usually
requiring 200-300 sentences), this takes up to 1.5 hours per relation. These
generated sentences are annotated and used as inputs to the syntactic search
method (§7.1) or directly as positive examples to a classifier (§7.2).

###  7.1 Enhancing Syntactic Search with Example Generation

We integrate the generation outputs in the Syntactic Search by Example method
by taking the positive annotated examples (on which we mark the entities as
part of the annotation process) and automatically transforming them into SPIKE
queries. This step has the potential to add substantial syntactic and lexical
diversity to the pattern set, resulting in both larger and more diverse sets
of positive examples. This combines the best of both worlds: the generative
model is used to provide structural and lexical diversity, while the syntactic
search system is used to provide a large selection of naturally occurring
corpus sentences adhering to these patterns.

#### Experiments and Results

Setup To reduce noise, we exclude queries where more than 1 out of 5 sampled
results does not express the relation of interest. On average, we increased
the number of syntactic patterns to 9.25, ranging from 6 to 14 after
filtering.

Results As listed in the _Search + Generation_ row of Table 1, this method
achieved best performance for both TACRED and DocRED with overall scores
corresponding to 550/1100 and 220/550 annotated examples respectively. Using
the generation outputs as examples doesn’t only help in suggesting more
sentences satisfying the relation but also in augmenting the number of
predicates used. We looked on the number of predicates used for the TACRED
relations which include lexical triggers (similarly to §6.2.1), the generation
phase suggested $7.4$ predicates on average, more than the $2.8$ predicates
per relation of our original patterns, and less than the trigger expansion
method we suggested in §6.2.1, where we tried to find all the possible
predicates, with $18.2$ triggers on average. We conclude that while the
Syntactic Search by Example method performs well with only a few example
patterns, this can be even improved with more input examples. While we report
Syntactic Search by Example enjoys such generation-based pattern augmentation,
a similar boost with different, non-NLG, methods is of course possible. We
leave further probing for other pattern augmentation methods as future work.

###  7.2 Directly Training Classifiers using Generation Outputs

It is possible that generative models produce diverse enough training examples
that will suggest our syntactic search superfluous. We validate the necessity
of taking the annotated generations (Annotated similarly to §7.1) through the
Syntactic Search by Example method, by comparing it to simply passing the
annotated generations as classifier inputs, as depicted in the RHS of Fig. 2.

#### Experiments and Results

Setup Many of the samples include the entities from the prompt verbatim.
Before using them as the model inputs, we replace the entities with a random
Wikipedia entity of the same type.

Results As can be seen in the _Example Generation_ row in Table 1, on TACRED,
this method produces F1 scores on par with Syntactic Search by Example.
However, evaluating on DocRED, the method does not produce competitive
results101010The language model used to generate examples was fine-tuned on a
version of TACRED which excludes the relations we evaluate on. Still, for
TACRED, the language model is fine-tuned and evaluated on data from the same
domain (newswire). The DocRED data on the other hand, is taken from Wikipedia,
so the evaluation is essentially out of domain. We therefore conclude that
used independently, this approach is applicable only in cases where a
background RE dataset is of the same domain as the target corpus from which we
want to extract relations.. On both datasets it produce worse than Search +
Generation. We conclude that it is more beneficial to use outputs of
generative models as syntactic search queries, and by that find syntactically
similar sentences, comparing to simply use generations as the train set. We
deduce models are likely to generalize better on “real world" examples.

##  8 Additional Experiments

###  8.1 Results across relations

Analyzing the results we highlight some interesting trends (Fig. 3). First, we
note that the behavior is not consistent between relations, nor datasets:
different relations behave differently, showing different trade-offs between
different methods.

Classifiers for relations like “Religion"111111TACRED’s “religion” relation
plateaus as it has a low number of train instances., “City of Death" and “Date
of Death" seem to plateau at around 50-100 manually annotated examples. For
these relations, annotating more data is not necessarily useful. The syntactic
search approach works especially well for these relations: applying syntactic
search over 3 seed queries is sufficient to yield results on par or slightly
higher than all available manually annotated data. We hypothesize that these
findings might be the result of low diversity in the ways these relations are
typically expressed.

While the combined _Search + Generation_ approach is overall useful, the
effect is not consistent across relations: performance improves for some
relations and deteriorates for others. In §7.1 we described the techniques we
use to reduce the noise coming from additional queries. These techniques
however are rather basic and these results indicate that more advanced
techniques of the type used in Angeli et al. (2015) and Ratner et al. (2017),
are likely to yield more consistent improvements.

Figure 3: F1 scores of TACRED (right), and DocRED (left) by relation.

###  8.2 Distant Supervision

Setup Distant supervision Mintz et al. (2009) suggests a method to construct a
training dataset based on a large external KB of relation triplets. Yao et al.
(2019) offered a machine annotated version of DocRED constructed by aligning
Wikipedia pages with Wikidata. The authors took great care in creating this
resource: a high-quality NER model trained on in-domain manually annotated
data was used to automatically annotate possible relation arguments; a named
entity linker was used to merge entities with similar KB ID; and finally,
Wikidata was queried in order to label pairs of linked entities.

We trained a classifier using the released data, sampling increasing number of
examples: (100+1,000, 500+5,000, 1,000+10,000). We report best score of
0.312$F_{1}$ (500+5,000 split).

Results This Distant Supervision dataset, created by Yao et al. (2019),
appears to be of very high quality and the results are on par with the full
set of manually annotated data. These results indicate that given a large KB
of relation triplets, a high-quality in-domain NER, and a high quality linking
solution, distant-supervision is a very promising technique. It should be
noted however, that the availability of all these external resources is very
rare in practice and is not required by the methods proposed in this work.

##  9 Applicability to other languages

We explored only English in this work. However, we argue that our main method
– example-based syntactic search followed by DL-training – is not strongly
tied to English, and we encourage other researchers to experiment with it in
their languages of interest. We provide details of what is needed to adapt the
system to a different language.

The Syntactic Search by Example method requires (1) An automatically
dependency-parsed corpora in the language. These can be readily produced by
the many syntactic parsers that are available for many languages Manning et
al. (2014); Honnibal and Montani (2017); Qi et al. (2020). (2) An indexing
engine that supports efficient queries over parse trees. Shlain et al. (2020)
uses the open-source Odinson engine Valenzuela-Escárcega et al. (2015) for
this purpose. (3) A component that translates a query in spike’s “by example"
syntax to the indexing engine’s query syntax. This requires finding the
minimal (in terms of number of nodes) sub-graph that connects all relation
arguments (and predicates if available), then search for sentences with
similar sub-graphs in the index. With these three components, a syntactic-
search system can be readily implemented. The rest of the components are
straightforward application of DL methods. Indeed, we suspect the major
obstacle in application to a new language will be the availability of
evaluation data.

##  10 Conclusion

We show that with modern DL classifiers and a dataset bootstrapped using
syntactic search with as few as 3 seed patterns can be as effective as a
dataset with hundreds of manually annotated samples. Using LMs help to further
diversify the dataset and improve results. Overall, our results are positively
optimistic for bootstrapping methods. However, this work is only an initial
step in exploring methods for bootstrapping relation extractors using minimal
user effort, supported by strong pre-trained neural LMs. We hope to encourage
further work in this direction.

##  11 Acknowledgments

This project has received funding from the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation programme,
grant agreement No. 802774 (iEXTRACT).

## References

  * Amin-Nejad et al. (2020) Ali Amin-Nejad, Julia Ive, and Sumithra Velupillai. 2020.  Exploring transformer text generation for medical dataset augmentation.  In _Proceedings of The 12th Language Resources and Evaluation Conference_ , pages 4699–4708.
  * Anaby-Tavor et al. (2019) Ateret Anaby-Tavor, Boaz Carmeli, Esther Goldbraich, Amir Kantor, George Kour, Segev Shlomov, Naama Tepper, and Naama Zwerdling. 2019.  Not enough data? deep learning to the rescue!  _arXiv preprint arXiv:1911.03118_.
  * Angeli et al. (2013) Gabor Angeli, Arun Tejasvi Chaganty, Angel X Chang, Kevin Reschke, Julie Tibshirani, Jean Wu, Osbert Bastani, Keith Siilats, and Christopher D Manning. 2013.  Stanford’s 2013 kbp system.  In _TAC_.
  * Angeli et al. (2015) Gabor Angeli, Victor Zhong, Danqi Chen, Arun Tejasvi Chaganty, Jason Bolton, Melvin Jose Johnson Premkumar, Panupong Pasupat, Sonal Gupta, and Christopher D Manning. 2015.  Bootstrapped self training for knowledge base population.  In _TAC_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Doddington et al. (2004) George R Doddington, Alexis Mitchell, Mark A Przybocki, Lance A Ramshaw, Stephanie M Strassel, and Ralph M Weischedel. 2004.  The automatic content extraction (ace) program-tasks, data, and evaluation.  In _Lrec_ , volume 2, page 1. Lisbon.
  * Ellis et al. (2015) Joe Ellis, Jeremy Getman, Dana Fore, Neil Kuster, Zhiyi Song, Ann Bies, and Stephanie M Strassel. 2015.  Overview of linguistic resources for the tac kbp 2015 evaluations: Methodologies and results.  In _TAC_.
  * Holtzman et al. (2019) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2019.  The curious case of neural text degeneration.  _arXiv preprint arXiv:1904.09751_.
  * Honnibal and Montani (2017) Matthew Honnibal and Ines Montani. 2017.  spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing.  To appear.
  * Kumar et al. (2020) Varun Kumar, Ashutosh Choudhary, and Eunah Cho. 2020.  Data augmentation using pre-trained transformer models.  _arXiv preprint arXiv:2003.02245_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Manning et al. (2014) Christopher D Manning, Mihai Surdeanu, John Bauer, Jenny Rose Finkel, Steven Bethard, and David McClosky. 2014.  The stanford corenlp natural language processing toolkit.  In _Proceedings of 52nd annual meeting of the association for computational linguistics: system demonstrations_ , pages 55–60.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_.
  * Mintz et al. (2009) Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. 2009.  Distant supervision for relation extraction without labeled data.  In _Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 2-Volume 2_ , pages 1003–1011. Association for Computational Linguistics.
  * Murty et al. (2020) Shikhar Murty, Pang Wei Koh, and Percy Liang. 2020.  Expbert: Representation engineering with natural language explanations.  _arXiv preprint arXiv:2005.01932_.
  * Qi et al. (2020) Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D Manning. 2020\.  Stanza: A python natural language processing toolkit for many human languages.  _arXiv preprint arXiv:2003.07082_.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI Blog_ , 1(8):9.
  * Ratner et al. (2017) Alexander Ratner, Stephen H. Bach, Henry R. Ehrenberg, Jason Alan Fries, Sen Wu, and Christopher Ré. 2017.  Snorkel: Rapid training data creation with weak supervision.  _Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases_ , 11 3:269–282.
  * Ratner et al. (2016) Alexander J Ratner, Christopher M De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. 2016.  Data programming: Creating large training sets, quickly.  In _Advances in neural information processing systems_ , pages 3567–3575.
  * Russo et al. (2020) Giuseppe Russo, Nora Hollenstein, Claudiu Musat, and Ce Zhang. 2020.  Control, generate, augment: A scalable framework for multi-attribute text generation.  _arXiv preprint arXiv:2004.14983_.
  * Shlain et al. (2020) Micah Shlain, Hillel Taub-Tabib, Shoval Sadde, and Yoav Goldberg. 2020.  Syntactic search by example.  In _Proceedings of ACL 2020, System Demonstrations_.
  * Soares et al. (2019) Livio Baldini Soares, Nicholas FitzGerald, Jeffrey Ling, and Tom Kwiatkowski. 2019\.  Matching the blanks: Distributional similarity for relation learning.  _arXiv preprint arXiv:1906.03158_.
  * Valenzuela-Escárcega et al. (2015) Marco A Valenzuela-Escárcega, Gus Hahn-Powell, Mihai Surdeanu, and Thomas Hicks. 2015.  A domain-independent rule-based framework for event extraction.  In _Proceedings of ACL-IJCNLP 2015 System Demonstrations_ , pages 127–132.
  * Wei and Zou (2019) Jason Wei and Kai Zou. 2019.  Eda: Easy data augmentation techniques for boosting performance on text classification tasks.  _arXiv preprint arXiv:1901.11196_.
  * Yao et al. (2019) Yuan Yao, Deming Ye, Peng Li, Xu Han, Yankai Lin, Zhenghao Liu, Zhiyuan Liu, Lixin Huang, Jie Zhou, and Maosong Sun. 2019.  Docred: A large-scale document-level relation extraction dataset.  _arXiv preprint arXiv:1906.06127_.
  * Zhang et al. (2017) Yuhao Zhang, Victor Zhong, Danqi Chen, Gabor Angeli, and Christopher D. Manning. 2017.  Position-aware attention and supervised data improve slot filling.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP 2017)_ , pages 35–45.

##  Appendix A Estimated effort for Annotation

Table 3 lists for each relation the ratio of positive to negative examples in
the TACRED training set. A negative example for a relation _r_ , is any
example whose entities share types with a positive example of _r_ , but whose
label is different from _r_. Note that TACRED significantly under represents
negative examples so the reported ratio is an upper bound on the ratio in the
wild.

Relation | Pos/Neg Ratio
---|---
org:country_of_hq | 1/7
org:founded_by | 1/56
per:children | 1/64
per:city_of_death | 1/31
per:date_of_death | 1/26
per:origin | 1/10
per:religion | 1/2
per:spouse | 1/52
Table 3: Pos/Neg ratio in TACRED, rounded to the closest fraction.

##  Appendix B Syntactic Search by Example with varying dataset sizes

We experimented with varying the number of sampled examples, using the same 3
seed syntactic patterns. The results are reported in Table 4. While DocRED’s
F1 scores increase with increasing number of sampled examples, the trend is
opposite in TACRED. We believe this is due to different initializations and
inductive noise in both the positive and negative samples introduced by
sampling from semi-noisy data.

Method | TACRED | DocRED
---|---|---
Synt. Search - 100 | 0.443 | 0.250
Synt. Search - 500 | 0.434 | 0.259
Synt. Search - 1000 | 0.427 | 0.266
Table 4: Syntactic Search by Example with different training sizes

##  Appendix C Trigger List Expansion

For the majority of patterns used in the Syntactic Search by Example
experiments we used a single trigger word (see Appendix D). To experiment with
using trigger lists, we modified the patterns in Appendix D in the following
way:

We changed the triggers in all _child\children_ patterns to include any of the
following possibilities:

baby, child, children, daughter, daughters, son, sons, step-daughter, step-
son, step-child, step-children, stepchildren, stepdaughter, stepson

For _founded-by_ relations we change the “founder" trigger to be any of these
triggers:

founder, co-founder, cofounder, creator

and changed “founded" to be any trigger from the following list:

create, creates, created, creating, creation, co-founded, co-found, debut,
emerge, emerges, emerged, emerging, establish, established, establishing,
establishes, establishment, forge, forges, forged, forging, forms, formed,
forming, founds, found, founded, founding, launched, launches, launching,
opened, opens, opening, shapes, shaped, shaping, start, started, starting,
starts

In _spouse_ relations we expanded the “husband\wife" trigger to be any of:

ex-husband, ex-wife, husband, widow, widower, wife, sweetheart, bride

and the “marry" trigger to:

divorce, divorced, married, marry, wed, divorcing

For the _“date of death"_ and _“place\city of death"_ we changed the “died"
trigger to any of:

died, executed, killed, dies, perished, succumbed, passed, murdered, suicide

##  Appendix D Examples used for Syntactic Search by Example

Table 5: SPIKE search patterns for TACRED and DocRED relations. child
---
<>e1:[e=PER]John ’s t:[w={triggers}]daughter , <>e2:[e=PER]Tim, likes
swimming.
<>e1:[e=PER]Mary did something to her t:[w={triggers}]son, <>e2:[e=PER]John in
1992.
<>e1:[e=PER]Mary was survived by her 4 t:[w={triggers}]sons, John, John,
<>e2:[e=PER]John and John.
triggers = son | daughter | child | children | daughters | sons
founded by
<>e1:[e=ORG]Microsoft t:[w]founder <>e2:[e=PER]Mary likes running.
<>e2:[e=PER]Mary t:[w]founded <>e1:[e=ORG]Microsoft.
<>e1:[e=ORG]Microsoft was t:[w]founded $by <>e2:[e=PER]Mary.
headquarters location
John Doe, a professor at the <>e1:[e=ORG]Oxford <>in:[t=IN]in
<>e2:[e=LOC]England likes running.
<>e1:[e=ORG]Oxford, a leading <>t:[t=NN]company <>in:[t=IN]in
<>e2:[e=LOC]England.
<>e2:[e=LOC]England pos:[t=POS]’s largest university is <>e1:[e=ORG]Oxford.
religion
<>e1:[e=PER]John is a e2:[w={triggers}]Jewish,,
e2:[w={triggers}]Jewish <>e1:[e=PER]John is walking down the street.
<>e1:[e=PER]John is a e2:[w={triggers}]Methodist Person.
triggers = Methodist | Episcopal | separatist | Jew | Christian | Sunni | evangelical | atheism | Islamic | secular | fundamentalist | Christianist | Jewish | Anglican | Catholic | orthodox | Scientology | Islamist | Islam | Muslim | Shia
spouse
<>e1:[e=PER]John ’s t:[w=wife | husband]wife, <>e2:[e=PER]Mary , died in 1991.
<>e1:[e=PER]John t:[l]married <>e2:[e=PER]Mary,,
<>e1:[e=PER]John is t:[w]married to <>e2:[e=PER]Mary,
origin
<>e2:[e=MISC]Scottish <>e1:[e=PER]Mary is high.
<>e1:[e=PER]Mary is a <>e2:[e=MISC]Scottish professor.
<>e1:[e=PER]Mary, the <>e2:[e=LOC]US professor.
date of death
<>e1:[e=PER]John was announced t:[w]dead in <>e2:[e=DATE]1943.
<>e1:[e=PER]John t:[w]died in <>e2:[e=DATE]1943.
<>e1:[e=PER]John, an NLP scientist, t:[w]died <>e2:[e=DATE]1943.
place of death
<>e1:[e=PER]John t:[w]died in <>e2:[e=LOC]London, <>country:e=LOC England in
1997.
<>e1:[e=PER]John t:[w]died in <>e2:[e=LOC]London in 1997.
<>e1:[e=PER]John $-LRB- t:[w]died in <>e2:[e=LOC]London $-RRB-.
DocRED’s founded by
<>e1:[e=ORG]MISC Microsoft t:[w]founder <>e2:[e=PER]Mary likes running.
<>e2:[e=PER]Mary t:[w]founded <>e1:[e=ORG]MISC Microsoft.
<>e1:[e=ORG]MISC Microsoft was t:[w]founded $by <>e2:[e=PER]Mary.
DocRED’s origin
<>e2:[e=MISC]Scottish company, <>e1:[e=ORG]Microsoft is successful.
<>e1:[e=ORG]MISC Microsoft is a <>e2:[e=MISC]Scottish Company.
<>e1:[e=ORG]MISC Microsoft is a <>t:[t=NN]song $by <>e2:[e=MISC]Scottish
musician.
DocRED’s date of death
<>e1:[e=PER]John $-LRB-
<>e1:[e=PER]John t:[w]died in <>e2:[e=DATE]1943.
<>e1:[e=PER]John, an NLP scientist, t:[w]died <>e2:[e=DATE]1943.
DocRED’s place of death
<>e1:[e=PER]John t:[w]died in <>e2:[e=LOC]London, <>country:e=LOC England in
1997.
<>e1:[e=PER]John t:[w]died in <>e2:[e=LOC]London in 1997.
<>e1:[e=PER]John $-LRB- $[e=DATE]1997, $[e=LOC]London $- $[e=DATE]1997
<>e2:[e=LOC]London $-RRB-.
DocRED’s headquarters location
<>e1:[e=ORG]Microsoft, a leading <>t:[t=NN] company <>in:[t=IN]in
<>e2:[e=LOC]Redmond.
<>e1:[e=ORG]Microsoft is t:[l=base | headquarter]based in <>e2:[e=LOC]England.
<>e1:[e=ORG]Microsoft, a leading <>t:[t=NN] company based <>in:[t=IN]in
<>e2:[e=LOC]Redmond.