# Comparing Spectral Bias and Robustness For Two-Layer Neural Networks: SGD vs
Adaptive Random Fourier Features

Aku Kammonen<EMAIL_ADDRESS>KAUST, Saudi Arabia  Lisi Liang
<EMAIL_ADDRESS>RWTH Aachen, Germany  Anamika Pandey<EMAIL_ADDRESS>aachen.de RWTH Aachen, Germany  Raúl Tempone<EMAIL_ADDRESS>KAUST,
Saudi Arabia  RWTH Aachen, Germany

###### Abstract

We present experimental results highlighting two key differences resulting
from the choice of training algorithm for two-layer neural networks. The
spectral bias of neural networks is well known, while the spectral bias
dependence on the choice of training algorithm is less studied. Our
experiments demonstrate that an adaptive random Fourier features algorithm
(ARFF) can yield a spectral bias closer to zero compared to the stochastic
gradient descent optimizer (SGD). Additionally, we train two identically
structured classifiers, employing SGD and ARFF, to the same accuracy levels
and empirically assess their robustness against adversarial noise attacks.

_K_ eywords machine learning $\cdot$ spectral bias $\cdot$ adversarial attack
$\cdot$ random features $\cdot$ neural network $\cdot$ SGD $\cdot$ MNIST
$\cdot$ Metropolis sampling

##  1 Introduction

Consider the data
$\\{x_{n},y_{n}\\}\in\mathbb{R}^{d}\times\mathbb{R},n=1,...,N$ i.i.d. sampled
from an unknown probability distribution with probability density function
$\tilde{\rho}(x,y)$. We assume that there exists an unknown underlying
function $f:\mathbb{R}^{d}\to\mathbb{R}$ such that
$f(x_{n})=y_{n}+\epsilon_{n},n=1,...,N$ where $\mathbb{E}[\epsilon_{n}]=0$ and
$\mathbb{E}[\epsilon_{n}^{2}]<\infty$. We address the supervised learning
problem of fitting a two-layer neural network
$\beta(\boldsymbol{x})=\sum^{K}_{k=1}\hat{\beta}_{k}e^{\mathrm{i}{\boldsymbol{\omega}_{k}}\cdot\boldsymbol{x}}$
to the data $\\{x_{n},y_{n}\\}_{n=1}^{N}$ by numerically approximating a
solution to the minimization problem

$\min_{(\boldsymbol{\omega},\boldsymbol{\hat{\beta}})\in\mathbb{R}^{Kd}\times\mathbb{C}^{K}}\left\\{\mathbb{E}_{\tilde{\rho}}\left[|y-\beta(x)|^{2}\right]+\lambda\sum_{k=1}^{K}|\hat{\beta}_{k}|^{2}\right\\}$
(1)

where $\lambda\in\mathbb{R}$ is a Tikhonov regularization parameter. Note
that, in practice, the data density $\tilde{\rho}$ is unknown, therefore we
consider the empirical minimization problem instead. Considering
$\boldsymbol{\omega}_{k}$ as i.i.d. samples from an unknown distribution with
probability density function $p(\boldsymbol{\omega}_{k})$ and by following [1]
an $\mathcal{O}(1/K)$ error bound to Problem (1) is derived in [2]. However,
in the work [2], only $\boldsymbol{\omega}_{k}$ is treated as a random
variable, while $\hat{\beta}_{k}$ is determined for a sampled
$\boldsymbol{\omega}_{k}$ without accounting for any inherent randomness in
$\hat{\beta}_{k}$. Further, the constant in the $\mathcal{O}(1/K)$ error bound
is shown to be minimized by sampling the weights $\boldsymbol{\omega}_{k}$
from
$p_{*}(\boldsymbol{\omega}):=|\hat{f}(\boldsymbol{\omega})|/\|\hat{f}\|_{L^{1}(\mathbb{R}^{d})}$
where $\hat{f}$ denotes the Fourier transform of $f$. Given only data
$\\{x_{n},y_{n}\\}_{n=1}^{N}$ means that $\hat{f}$ typically is not
accessible. The goal of the adaptive random Fourier features with Metropolis
sampling algorithm (ARFF), presented in and denoted as Algorithm 1 in [2], is
to approximately sample $\boldsymbol{\omega}$ from $p_{*}$, given only data.
Applications of the ARFF algorithm include wind field reconstruction, see [3],
and pre-training of deep residual neural networks, see [4].

For simplicity in our numerical experiments, we employ the cosine activation
function. This choice necessitates the introduction of a bias term $b_{k}$ for
each $k=1,\ldots,K$ in the argument of the cosine function. The purpose of
this bias is to offset the contribution of the sinusoidal component in the
Fourier representation of the target function, $f$.

For the ARFF training, the associated least squares problem, in the amplitudes
$\hat{\boldsymbol{\beta}}$ for sampled frequencies $\boldsymbol{\omega}_{k}$
and bias $b_{k},k=1,...,K$ is
$\min_{\hat{\boldsymbol{\beta}}\in\mathbb{R}^{K}}(N^{-1}|\boldsymbol{S}\hat{\boldsymbol{\beta}}-\boldsymbol{y}|^{2}+\lambda|\hat{\boldsymbol{\beta}}|^{2}),$
where $\boldsymbol{S}\in\mathbb{R}^{N\times K}$ is a matrix with elements
$S_{n,k}=\cos(\boldsymbol{\omega}_{k}\cdot\boldsymbol{x}_{n}+b_{k})$,
$n=1,...,N$, $k=1,...,K$ and
$\boldsymbol{y}=(y_{1},...,y_{N})\in\mathbb{R}^{N}$. The SGD training follows
the standard approach and is adapted from the TensorFlow implementation.

Rahimi and Recht first introduce random Fourier features in [5] as a
computationally fast and accurate way to approximate the kernels of Support
Vector Machines, [6, 7]. In [8], they show that by manually adjusting the
sampling distribution, Fourier features neural networks can learn high-
frequency components and thus overcome the spectral bias. Our approach is to
adaptively sample the frequencies with ARFF and quantify the spectral bias
with the definition introduced in [9].

While several innovative adversarial attack methods [10, 11, 12], and
efficient defense mechanisms [13, 14, 15] exist, we demonstrate how just
changing the training algorithm can affect the robustness of a simple
adversarial attack.
Our contributions in summary

  * •

We show, experimentally, how training a two-layer neural network with adaptive
random Fourier features [2] can overcome the spectral bias, as defined in [9],
compared to training with stochastic gradient descent.

  * •

We show, experimentally, how two sets of identically structured neural
networks with the same classification rate on the MNIST dataset have different
degrees of robustness to a simple additive adversarial attack, depending on if
we train them with adaptive random Fourier features [2] or with stochastic
gradient descent.

##  2 Spectral bias

Numerous prior investigations [16, 17, 18, 19, 20], encompassing both
empirical and theoretical approaches have delved into the spectral bias of
neural networks: the inclination to learn low-frequency content. Kiessling et
al. introduced a computable definition of spectral bias, as documented in [9],
which shares similarities with the approaches outlined in [21] and [22].

In this work, we employ the spectral bias definition provided by Kiessling et
al. in [9] to assess and contrast the spectral bias between two-layer neural
networks trained by ARFF and SGD.

The spectral bias of a neural network $\beta$ is defined as
$SB=(\mathcal{E}_{high}-\mathcal{E}_{low})/(\mathcal{E}_{high}+\mathcal{E}_{low}),$
in [9], where
$\mathcal{E}_{high}=\frac{\int_{\Omega_{high}}|\hat{r}_{\rho}(\omega)|^{2}d\omega}{(2\pi)^{d}Var(f(x))}$
and
$\mathcal{E}_{low}=\frac{\int_{\Omega_{low}}|\hat{r}_{\rho}(\omega)|^{2}d\omega}{(2\pi)^{d}Var(f(x))}$
, respectively, represent the error in the high- and low-frequency domain.
Here $Var(f(x))$ denotes the variance of the unknown target function $f$ and
is approximated by the given dataset by using Monte Carlo integration,
$\hat{r}_{\rho}(\omega)$ denotes the frequency spectrum of the function
$r_{\rho}(x)=\sqrt[]{\rho(x)}(r(x)-\mathbb{E}_{\rho}[r(x)])$ where
$r(x)=f(x)-\beta(x)$ is the residual, and $\rho(x)$ denotes the density of the
input data $x$.

The symbols $\Omega_{\text{high}}$ and $\Omega_{\text{low}}$ denote the
partitioned frequency domain, delineated by a designated cutoff frequency
$\omega_{0}$, that is,
$\Omega_{high}=\\{\omega\in\mathbb{R}^{d}:|\omega|_{\infty}>\omega_{0}\\}$,
and
$\Omega_{low}=\\{\omega\in\mathbb{R}^{d}:|\omega|_{\infty}\leq\omega_{0}\\}$.
The cutoff frequency $\omega_{0}$ is specified to equalize the contributions
of $\Omega_{\text{low}}$ and $\Omega_{\text{high}}$ to the total variance,
expressed as
$\int_{\Omega_{\text{low}}}|\hat{f}_{\rho}(\omega)|^{2}d\omega=\int_{\Omega_{\text{high}}}|\hat{f}_{\rho}(\omega)|^{2}d\omega,$
where $\hat{f}_{\rho}$ denotes the Fourier transform of the function
$f_{\rho}(x)=\sqrt[]{\rho(x)}(f(x)-\mathbb{E}_{\rho}[f(x)])$. The integral
equality to obtain the cutoff frequencies and, consequently, the spectral bias
are in practice approximated by Methods 1 and 2 given in [9].

If the neural network performs equally well for low and high-frequency
content, the spectral bias ($SB$) tends to approach zero. In such cases, the
neural network will be characterized as spectrally unbiased.

### Numerical comparison of spectral bias in trained neural networks using SGD
and ARFF training algorithms

For this experiment, we consider the target function
$f:\mathbb{R}\rightarrow\mathbb{R}$

$\displaystyle
f(x)=e^{-\frac{x^{2}}{2}}Si\left(\frac{x}{a}\right),\quad\text{where}~{}~{}Si\left(x\right)=\int^{x}_{0}\frac{\sin(t)}{t}dt~{}~{}\text{with}~{}~{}a=10^{-2}.$

We train a two-layer neural network
$\beta(x;\boldsymbol{\omega},\boldsymbol{\hat{\beta}})=\sum^{K}_{k=1}\hat{\beta}_{k}\cos(\omega_{k}\cdot
x+b_{k})$ to approximate the target function $f$, where $K$ is the number of
nodes in the neural network, $\omega_{k}\in\mathbb{R},x\in\mathbb{R}$ and
$\hat{\beta}\in\mathbb{R}$. While keeping the architecture the same, we train
the neural network with SGD and ARFF. We compute the spectral bias of the
trained neural network after getting the desired accuracy in the approximation
of the target function. We use Method 1, described in [9], for this
experiment.

We generate training, validation, and test datasets as follows: sample $N$
$x$-points from $\mathcal{N}(0,1)$, evaluate the target function to obtain
$f(x)$, and normalize all three datasets by subtracting the mean and dividing
by the standard deviation of the training dataset
$\\{x_{n},f(x_{n})\\}_{n=1}^{N}$. The error is then computed as the mean
squared error for each dataset.

Figure 1: Spectral bias comparison, computed after each epoch, of a neural
network trained with SGD and ARFF by using Method 1 from [9].

Both training algorithms, SGD and ARFF, are executed for $M=10^{4}$ epochs. In
the case of ARFF, we employ the following parameters: Tikhonov regularization
$\lambda=0.05$, proposal width $\delta=2$ in the sampling algorithm, and the
exponent $\gamma=3d-2$ in the acceptance-rejection ratio, where $d=1$. For SGD
we utilize a batch size of $32$ and a learning rate of $0.0002$.

In Figure 1, we delineate a comparison of the spectral bias exhibited by a
neural network comprising $K=1024$ neurons in the hidden layer and trained by
two distinct training algorithms, SGD and ARFF.

The comparison reveals that the spectral bias of the neural network trained
with SGD remains close to unity. In contrast, the ARFF training algorithm
enables the neural network to achieve a state of spectral unbiasedness.

We have extended this test to include varying widths in a two-layer neural
network and obtained similar results.

##  3 Robustness to an additive adversarial attack

This experiment compares the robustness of two-layer neural networks trained
with ARFF and SGD against an additive adversarial black box attack.

Datasets
We consider the MNIST dataset that consists of $70,000$ handwritten digit
images of size $28\times 28$ and its corresponding labels
$y\in\\{0,1,...,9\\}$. The task is to classify the images between the digits
$0$ to $9$.

We partition the datasets into training, validation, and test data with the
corresponding ratio of $7:2:1$.

Neural network structure and training
We train ten two-layer neural networks
$\boldsymbol{\beta}^{i}(\boldsymbol{x};\boldsymbol{\omega}^{i},\boldsymbol{\hat{\beta}}^{i},b^{i})=\sum^{K}_{k=1}\hat{\beta}^{i}_{k}\cos({\boldsymbol{\omega}_{k}^{i}}\cdot\boldsymbol{x}+b^{i}),\
i=0,...,9$ with $K=2^{10}$ nodes each, with both ARFF and SGD where
$\boldsymbol{\omega}^{i}_{k}\in\mathbb{R}^{d},\boldsymbol{x}\in\mathbb{R}^{d},b^{i}\in\mathbb{R},\hat{\beta}^{i}_{k}\in\mathbb{R}$,
and $d=784$ for the MNIST dataset. We train each neural network to classify
one number each. E.g.
$\boldsymbol{\beta}^{2}(\boldsymbol{x};\boldsymbol{\omega}^{2},\boldsymbol{\hat{\beta}}^{2},b^{2})$
is trained to tell if a handwritten digit is the number $2$ or not. For SGD we
use one least squares loss function for each neural network.

The training data
$\\{(\boldsymbol{x}_{n};(y_{n}^{0},y_{n}^{1},...,y_{n}^{9}))\\}^{N}_{n=1}$
consist of vectorized handwritten digit images
$\boldsymbol{x}_{n}\in\mathbb{R}^{784}$ with corresponding vector labels
$(y_{n}^{0},y_{n}^{1},...,y_{n}^{9})$. Each vector label has one component
equal to one and the others equal to zero. The index $i$ of the component
$y_{n}^{i}$ equal to $1$ is the number that the handwritten digit
$\boldsymbol{x}_{n}$ represents.

In the following experiments, we run both the training algorithms, SGD and
ARFF, for $M=100$ epochs each. For ARFF, the parameters are set to
$\lambda=0.05$, $\delta=0.02$ $\gamma=3d-2$, with $d=784$. For SGD, we use a
batch size of $32$ and a learning rate of $0.002$.

Classification and computation of the accuracy

A handwritten test digit $\boldsymbol{x}\in\mathbb{R}^{784}$ is classified as
the number
$\arg\max_{i}\\{\boldsymbol{\beta}^{i}(\boldsymbol{x};\boldsymbol{\omega}^{i},\boldsymbol{\hat{\beta}}^{i},b^{i})\\}$
where $\\{\omega^{i}_{k},\hat{\beta}_{k}^{i},b_{k}^{i}\\}_{k=1}^{K},i=0,...,9$
are the trained weights and biases resulting from either ARFF or SGD.

We evaluate the performance of the artificial neural networks by the
classification accuracy, defined as $accuracy=\frac{N_{\text{correctly
classified}}}{N_{\text{total}}}$, where $N_{\text{total}}$ represents the
total number of test images, and $N_{\text{correctly classified}}$ denotes the
count of accurately classified handwritten test images out of
$N_{\text{total}}$.

### Random noise attack

We apply the simple black box attack of adding random normal distributed noise
to $n_{pixel}\in[0,d]$ randomly chosen pixels of each $N_{test}$ images in the
test dataset to get the noisy test data
$\boldsymbol{x}^{n}_{noise}=\boldsymbol{x}^{n}_{test}+\boldsymbol{\delta}^{n}\odot\boldsymbol{r}^{n},$
$\boldsymbol{r}^{n}\sim
N(\boldsymbol{0},\sigma^{2}\boldsymbol{I}),\;n=1,...,N_{test}$ where
$I\in\mathbb{R}^{d\times d}$ is the identity matrix, $\sigma\in\mathbb{R}$,
and $\odot$ denotes component-wise multiplication. Here the component
$\delta_{i}$ of $\boldsymbol{\delta}$ satisfies $\delta_{i}\in\\{0,1\\}$ and
the number of the elements which are equal to one is $n_{pixel}$, i.e.
$\sum^{d}_{i=1}\delta_{i}=n_{pixel}$.

Experiment 1: We present the classification rates on the noisy test images,
where $n_{pixel}=50$, for different values of $\sigma$ on the left in Figure 2
for both SGD and ARFF. Even though both training algorithms have trained the
neural networks to the same classification rate, the accuracy of the neural
networks trained by SGD decreases faster when $\sigma$ increases compared to
the accuracy of the neural networks trained by ARFF.

Experiment 2: We present the classification rates on the noisy test images,
where $n_{pixel}=d=784$, for different values of $\sigma$ in the middle in
Figure 2. Contrary to the results in Experiment 1, we see a faster decrease in
the accuracy when $\sigma$ increases for ARFF than for SGD.

Experiment 3: As in Experiment 2 we use $n_{pixel}=d=784$. The difference is
that we also add noise, from $\mathcal{N}(0,\sigma^{2})$, to all $784$ pixels
of each image in the validation dataset and use the best classification rate
on the validation data as stopping criterion for the training. We present the
results on the right in Figure 2. The classification rate for SGD is
qualitatively the same as in Experiment 2, but now the classification rate for
ARFF is better than for SGD. The optimal stopping epoch differs for each value
of $\sigma$, though.

Remark: For comparison, we run Experiments 1, 2, and 3 analogously on the
CIFAR-10 dataset as well. The results are qualitatively the same. I.e., ARFF
shows better results for Experiments 1 and 3, while SGD gives better results
for Experiment 2.

Figure 2: Left, Experiment 1: The figure shows the accuracy on the MNIST test
data after a sparse black box attack. Middle, Experiment 2: Accuracy on the
MNIST test data after a black box attack for different noise levels. Right,
Experiment 3: Accuracy on the MNIST test dataset after a black box noise
attack for classifiers tuned, with the help of noisy validation data, to
withstand noise attacks. In Experiment 3 the stopping criteria depends on the
noise level $\sigma$.

##  4 Conclusion

Our experimental findings underscore the effectiveness of ARFF-trained neural
networks in efficiently capturing high-frequency content within the context of
function reconstruction. We have also demonstrated the heightened robustness
of ARFF-trained models when subjected to sparse black-box noise attacks at
varying levels. While the same superiority is not consistently observed in the
face of full black-box noise attacks, where noise is added to every pixel of
the input image, we establish that the ARFF-trained neural network can
maintain its robustness and outperform SGD by strategically leveraging noisy
validation datasets and implementing early stopping. This insight provides
practitioners with a viable strategy for prioritizing neural network
robustness. Moreover, this study paves the way for future investigations,
urging a more comprehensive exploration of ARFF training under sophisticated
and well-structured attacks, the Square Attack [12], which we eagerly
anticipate exploring in subsequent research endeavors.

##  5 Acknowledgement

We express our gratitude to Prof. Anders Szepessy and Dr. Erik von Schwerin
for reading the manuscript and providing their valuable feedback. This
collaborative work, integral to Ms. Lisi Liang’s master’s thesis, is submitted
as a component of her master’s degree fulfillment at RWTH Aachen University.

We also acknowledge the financial support by the KAUST Office of Sponsored
Research (OSR) under Award numbers URF$/1/2281-01-01$, URF$/1/2584-01-01$ in
the KAUST Competitive Research Grants Program Round 8 and the Alexander von
Humboldt Foundation.

## References

  * [1] Andrew R. Barron.  Universal approximation bounds for superpositions of a sigmoidal function.  IEEE Transactions on Information Theory, 39(3):930–945, 1993.
  * [2] Aku Kammonen, Jonas Kiessling, Petr Plecháč, Mattias Sandberg, and Anders Szepessy.  Adaptive random fourier features with metropolis sampling.  Foundations of Data Science, 2(3):309–332, 2020.
  * [3] Jonas Kiessling, Emanuel Ström, and Raúl Tempone.  Wind field reconstruction with adaptive random fourier features.  Proc. R. Soc. A., 477, 2021.
  * [4] Aku Kammonen, Jonas Kiessling, Petr Plecháč, Mattias Sandberg, Anders Szepessy, and Raúl Tempone.  Smaller generalization error derived for a deep residual neural network compared with shallow networks.  IMA Journal of Numerical Analysis, 43(5):2585–2632, 09 2022.
  * [5] Ali Rahimi and Benjamin Recht.  Random features for large-scale kernel machines.  Advances in neural information processing systems, 20, 2007.
  * [6] Vapnik Vladimir Naumovich.  Statistical learning theory.  Adaptive and learning systems for signal processing, communications, and control. Wiley, New York, 1998.
  * [7] Ingo Steinwart and Andreas Christmann.  Support Vector Machines.  Springer Publishing Company, Incorporated, 1st edition, 2008.
  * [8] Matthew Tancik, Pratul P. Srinivasan, Ben Mildenhall, Sara Fridovich-Keil, Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan T. Barron, and Ren Ng.  Fourier features let networks learn high frequency functions in low dimensional domains.  NeurIPS, 2020.
  * [9] Jonas Kiessling and Filip Thor.  A computable definition of the spectral bias.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7168–7175, 2022.
  * [10] Hatem Hajri, Manon Cesaire, Lucas Schott, Sylvain Lamprier, and Patrick Gallinari.  Neural adversarial attacks with random noises.  International Journal on Artificial Intelligence Tools, 2022.
  * [11] Yi-Ting Tsai, Min-Chu Yang, and Han-Yu Chen.  Adversarial attack on sentiment classification.  In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 233–240, 2019.
  * [12] Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein.  Square attack: a query-efficient black-box adversarial attack via random search.  In European conference on computer vision, pages 484–501. Springer, 2020.
  * [13] Tian Yu Liu, Yu Yang, and Baharan Mirzasoleiman.  Friendly noise against adversarial noise: A powerful defense against data poisoning attack.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 11947–11959. Curran Associates, Inc., 2022.
  * [14] Martín Abadi, Andy Chu, Ian J. Goodfellow, H. B. McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016.
  * [15] Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Ben Edwards, Taesung Lee, Ian Molloy, and B. Srivastava.  Detecting backdoor attacks on deep neural networks by activation clustering.  ArXiv, abs/1811.03728, 2018.
  * [16] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville.  On the spectral bias of neural networks.  In International Conference on Machine Learning, pages 5301–5310. PMLR, 2019.
  * [17] Qingguo Hong, Qinyan Tan, Jonathan W. Siegel, and Jinchao Xu.  On the activation function dependence of the spectral bias of neural networks.  ArXiv, abs/2208.04924, 2022.
  * [18] Yongtao Wu, Zhenyu Zhu, Fanghui Liu, Grigorios G. Chrysos, and Volkan Cevher.  Extrapolation and spectral bias of neural nets with hadamard product: a polynomial net study.  ArXiv, abs/2209.07736, 2022.
  * [19] Nasim Rahaman, Devansh Arpit, Aristide Baratin, Felix Dräxler, Min Lin, Fred A. Hamprecht, Yoshua Bengio, and Aaron C. Courville.  On the spectral bias of deep neural networks.  ArXiv, abs/1806.08734, 2018.
  * [20] Yuan Cao, Zhiying Fang, Yue Wu, Ding-Xuan Zhou, and Quanquan Gu.  Towards understanding the spectral bias of deep learning.  arXiv preprint arXiv:1912.01198, 2019.
  * [21] Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma.  Frequency principle: Fourier analysis sheds light on deep neural networks.  arXiv preprint arXiv:1901.06523, 2019.
  * [22] Zhi-Qin John Xu, Yaoyu Zhang, and Yanyang Xiao.  Training behavior of deep neural network in frequency domain.  In Neural Information Processing: 26th International Conference, ICONIP 2019, Sydney, NSW, Australia, December 12–15, 2019, Proceedings, Part I 26, pages 264–274. Springer, 2019.
  * [23] E Weinan, Chao Ma, and Lei Wu.  A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics.  Sci. China Math, 2020.
  * [24] E Weinan, Chao Ma, and Lei Wu.  The barron space and the flow-induced function spaces for neural network models.  Constructive Approximation, 55(1):369–406, February 2022.
  * [25] Sebastian Ruder.  An overview of gradient descent optimization algorithms.  arXiv preprint arXiv:1609.04747, 2016.
  * [26] John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  Journal of machine learning research, 12(7), 2011.
  * [27] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [28] Alessandro Rudi and Lorenzo Rosasco.  Generalization properties of learning with random features.  Advances in neural information processing systems, 30, 2017.
  * [29] Kevin Gurney.  An introduction to neural networks.  CRC press, 1997.
  * [30] Shai Shalev-Shwartz and Shai Ben-David.  Understanding machine learning: From theory to algorithms.  Cambridge university press, 2014.
  * [31] Chris M Bishop.  Neural networks and their applications.  Review of scientific instruments, 65(6):1803–1832, 1994.
  * [32] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199, 2013.
  * [33] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  In 2017 ieee symposium on security and privacy (sp), pages 39–57. Ieee, 2017.
  * [34] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:1412.6572, 2014.


Document-level relation extraction aims to identify relations between entities in a whole document.
Prior efforts to capture long-range dependencies have relied heavily on implicitly powerful representations learned through (graph) neural networks,
which makes the model less transparent.

To tackle this challenge,
in this paper, we propose , a novel probabilistic model for document-level relation extraction by learning logic rules.
treats logic rules as latent variables
and consists of two modules: a rule generator and a relation extractor.
The rule generator is to generate logic rules potentially contributing to final predictions,
and the relation extractor outputs final predictions based on the generated logic rules.
Those two modules can be efficiently optimized with the expectation-maximization (EM) algorithm.
By introducing logic rules into neural networks,
can explicitly capture long-range dependencies as well as enjoy better interpretation.

Empirical results show that significantly outperforms several strong baselines in terms of relation performance ($\sim$1.8 F1 score) and logical consistency (over 3.3 logic score).
Our code is available at <https://github.com/rudongyu/LogiRE>.

§ INTRODUCTION

Extracting relations from a document has attracted significant research attention in information extraction (IE).

Recently, instead of focusing on sentence-level  <cit.>,
researchers have turned to modeling directly at the document level  <cit.>,
which provides longer context and requires more complex reasoning.
Early efforts focus mainly on learning a powerful relation (i.e., entity pair) representation, which implicitly captures long-range dependencies.
According to the input structure, we can divide the existing document-level relation extraction work into two categories: the sequence-based model  and the graph-based model.

An example of relation identification by utilizing rules. The three labeled sentences describe the relations royalty_of(Harry,UK), sibling_of(William,Harry), and spouse_of(Kate,William), respectively. The identification of the relation royalty_of(Kate,UK) requires the synthesis of information in three sentences. It can be easily derived from the demonstrated rule and the other three relations.

The sequence-based model first leverages different sequence encoder (e.g., BERT <cit.>, RoBERTa <cit.>) to obtain token representations,
and then computes relation representations by various pooling operations,
e.g., average pooling  <cit.>, attentive pooling  <cit.>.

To further capture long-range dependencies, graph-based models are proposed.
By constructing a graph, words or entities that are far away can become neighbor nodes.
On top of the sequence encoder, the graph encoder (e.g., GNN) can aggregate information from all neighbors, thus capturing longer dependencies.
Various forms of graphs are proposed, including
dependency tree  <cit.>,
co-reference graph  <cit.>,
mention-entity graph  <cit.>,
entity-relation bipartite graph  <cit.> and so on.
Despite their great success, there is still no comprehensive understanding of the internal representations, which are often criticized as mysterious "black boxes".

Learning logic rules can discover and represent knowledge in explicit symbolic structures that can be understood and examined by humans.
At the same time, logic rules provide another way to explicitly capture interactions between entities and output relations in a document.
For example in Fig. <ref>, the identification of royalty_of(Kate,UK) requires information in all three sentences. The demonstrated logic rule can be applied to directly obtain this relation from the three relations locally extracted in each sentence. Reasoning over rules bypasses the difficulty of capturing long-range dependencies and interprets the result with intrinsic correlations.
If the model could automatically learn rules and use them to make predictions, then we would get better relation extraction performance and enjoy more interpretation.

In this paper, we propose , a novel probabilistic model modeling intrinsic interactions among relations by logic rules.
Inspired by RNNLogic  <cit.>,
we treat logic rules as latent variables.
consists of a rule generator and a relation extractor,
which are simultaneously trained to enhance each other.
The rule generator provides logic rules that are used by the relation extractor for prediction,
and the relation extractor provides some supervision signals to guide the optimization of the rule generator, which significantly reduces the search space.
In addition, the proposed relation extractor is model agnostic, so it can be used as a plug-and-play technique for any existing relation extractors.
Those two modules can be efficiently optimized with the EM algorithm.
By introducing logic rules into neural networks,
can explicitly capture long-range dependencies between entities and output relations in a document and enjoy better interpretation.
Our main contributions are listed below:

* We propose a novel probabilistic model for relation extraction by learning logic rules.
The model can explicitly capture dependencies between entities and output relations, while enjoy better interpretation.

* We propose an efficient iterative-based method to optimize based on the EM algorithm.

* Empirical results show that significantly outperforms several strong baselines in terms of relation performance ($\sim$1.8 F1 score) and logical consistency (over 3.3 logic score).

§ RELATED WORK

The overview of . consists of two modules: a rule generator $p_\theta$ and a relation extractor $p_w$. For a given document $\mathcal{D}$ and a query triple $q$, we treat the required logic rules as latent variables $\bm{z}$, aiming to identify the corresponding truth value $y$. During inference, we sample from the rule generator for the latent rule set and use the relation extractor to predict $y$ given the rules. The overall objective (maximizing the likelihood) is optimized by the EM algorithm. In the E-step, we estimate the approximate posterior $q(\bm{z})$; In the M-step, we maximize a lower bound of the likelihood w.r.t. $\theta, w$.

For document-level relation extraction,
prior efforts on capturing long-range dependencies mainly focused on two directions: pursuing stronger sequence representation <cit.> or including prior for interactions among entities as graphs <cit.>.
For more powerful representations, they introduced pre-trained language models <cit.>, leveraged attentions for context pooling <cit.>, or integrated the scattered information according to a hierarchical level <cit.>.
Aiming to model the intrinsic interactions among entities and relations, they utilized implicit reasoning structures by carefully designing graphs connecting: mentions to entities, mentions in the same sentence <cit.>, mentions of the same entities <cit.>, etc. <cit.> directly integrated similar structural dependencies to attention mechanisms in the encoder.
These approaches contributed to obtaining powerful representations for distinguishing various relations but lacked interpretability on the implicit reasoning.
Another approach that can capture dependencies between relations is the global normalized model  <cit.>.
In this work, we focus on how to learn and use logic rules to capture long-range dependencies between relations.

Another category of related work is logical reasoning.
Many studies were conducted on learning or applying logic rules for reasoning. Most of them <cit.> concentrated on reasoning over knowledge graphs, aiming to deduct new knowledge from existing triples. Neural symbolic systems <cit.> combined logic rules and neural networks to benefit from regularization on deep learning approaches. These efforts demonstrated the effectiveness of integrating neural networks with logical reasoning. Despite doc-RE providing a suitable scenario for logical reasoning (with relations serving as predicates and entities as variables), no existing work attempted to learn and utilize rules in this field.
Using hand-crafted rules, <cit.> achieved great success on sent-level information extraction tasks. However, the rules were predefined and limited to low-level operations, restricting their applications.

§ METHOD

In this section, we describe the proposed method that learns logic rules for document-level relation extraction.
We first define the task of document-level relation extraction and logic rules.

Document-level Relation Extraction
Given a set of entities $\mathcal{E}$ with mentions scattered in a document $\mathcal{D}$, we aim to extract a set of relations $\mathcal{R}$.
A relation is a triple $(h, r, t) \in \mathcal{R}$ (also denoted by $r(h, t)$), where $h \in \mathcal{E}$ is the head entity, $t \in \mathcal{E}$ is the tail entity and $r$ is the relation type describing the semantic relation between two entities.
Let $\mathcal{T}_r$ be the set of possible relation types (including reverse relation types).
For simplicity, we define a query $q = (h, r, t)$ and
aim to model the probabilistic distribution $p(\bm{y}| q, \mathcal{D})$,
where $\bm{y} \in \{ -1, 1\}$ is a binary variable indicating whether $(h, r, t)$ is valid or not,
and $h, t \in \mathcal{E}, r \in \mathcal{T}_r$.
In this paper, bold letters indicate variables.

Logic Rule
We extract relations from the document by learning logic rules, where logic rules in this work have the conjunctive form:
∀{e_i }_i=0^l   r(e_0, e_l) ←r_1(e_0, e_1) …r_l(e_l-1, e_l)

$e_i \in \mathcal{E}$, $r_i \in \mathcal{T}_r$ and $l$ is the rule length.
This form can express a wide range of common logical relations such as
symmetry and transferability.
For example, transferability can be expressed as
∀{ e_0, e_1, e_2}     r(e_0, e_2) ←r(e_0, e_1) r(e_1, e_2)

Inspired by RNNLogic  <cit.>, to infer high-quality logic rules in the large search space,
we separate rule learning and weight learning and treat the logic rules as the latent variable.
consists of two main modules: the rule generator and the relation extractor, which are simultaneously trained to enhance each other.
Given the query $q = (h, r, t)$ in the document $\mathcal{D}$,
on the one hand,
the rule generator adopts an auto-regressive model to generate a set of logic rules based on $q$, which was used to help the relation extractor make the final decision;
on the other hand,
the relation extractor can provide some supervision signals to update the rule generator with posterior inference,
which greatly reduces the search space with high-quality rules.

Unlike existing methods to capture the interactions among relations in the document by learning powerful representations,
we introduce a novel probabilistic model (Sec. <ref>, Fig. <ref>),
which explicitly enhances the interaction by learning logic rules.
uses neural networks to parameterize the rule generator and the relation extractor (Sec. <ref>),
optimized by the EM algorithm in an iterative manner (Sec. <ref>).

§.§ Overview

We formulate the document-level relation extraction in a probabilistic way,
where a set of logic rules is assigned as a latent variable $\bm{z}$.
Given a query variable $\bm{q} = (\bm{h}, \bm{r}, \bm{t})$ in the document $\mathcal{D}$,
we define the target distribution $p(\bm{y}| \bm{q}, \mathcal{D})$ as below[For simplicity, we omit $\mathcal{D}$ in distributions $p_{w, \theta}$ and $p_w$.]:
p_w, θ(y| q) = ∑_z p_w(y|q, z) p_θ(z |q)

where $p_\theta$ is the distribution of the rule generator which defines a prior over the latent variable $\bm{z}$ conditioned on a query $\bm{q}$ (we assume the distribution of $\bm {z}$ is independent from the document $\mathcal{D}$),
and $p_w$ is the relation extractor which gives the probability of $\bm{y}$ conditioned on the query $\bm{q}$, latent $\bm{z}$, and the document $\mathcal{D}$.
Given the gold label $y^*$ of the query $q$ in the document $\mathcal{D}$,
the objective function is to maximize the likelihood as follows:
ℒ(w, θ)    = logp_w, θ(y^*| q)

Due to the existence of latent variables in the objective function $\mathcal{L}$, we use the EM algorithm for optimization (Sec. <ref>).

§.§ Parameterization

We use neural networks to parameterize the rule generator and the relation extractor.

Rule Generator
The rule generator defines the distribution $p_\theta(\bm{z}|\bm{q})$.
For a query ${q}$,
the rule generator generates a set of logic rules denoted by $\bm{z}$ for predicting the truth value $\bm y$ of the query ${q}$.

given a query ${q} = (h, r, t)$,
we generate logic rules that takes the form of $r \leftarrow r_1 \land \dots \land r_l$.
Such relation sequences $[r_1, \dots, r_l]$ can be effectively modeled by an autoregressive model.
In this work,
we employ a Transformer-based autoregressive model $\textrm{AutoReg}_\theta$ to parameterize the rule generator,
which sequentially generates each relation $r_i$.
In this process, the probabilities of generated rules are simultaneously computed.

we assume that the rule set $\bm{z}$ obeys a multinomial distribution with $N$ rules independently sampled from the distribution $\textrm{AutoReg}_\theta(\emph{rule}|{q})$:

p_θ(z|q) ∼Multi(z | N, AutoReg_θ(rule|q)),

where $\textrm{Multi}$ denotes multinomial distribution, $N$ is a hyperparameter for the size of the set $\bm{z}$ and $\textrm{AutoReg}_\theta$ defines a distribution over logic rules conditioned on the query ${q}$.
[The generative process of a rule set $\bm{z}$ is quite intuitively similar to a translation model, and we simply generate $N$ rules with $\textrm{AutoReg}_\theta$ to form $\bm{z}$.]

Relation Extractor
The relation extractor defines $p_w(\bm{y}| \bm{q}, \bm{z})$.  It utilizes a set of logic rules to get the truth value of $\bm{y}$ corresponding to the query $\bm{q}$.
For each query ${q}$,
a $\emph{rule} \in \bm{z}$ is able to find different grounding paths on the document $\mathcal{D}$.
For example, Alice$\xrightarrow{\emph{father}}$Bob$\xrightarrow{\emph{spouse}}$Cristin is a grounding path for the rule $\emph{mother}(e_0, e_2)\leftarrow \emph{father}(e_0, e_1)\land\emph{spouse}(e_1, e_2)$.
Following the product t-norm fuzzy logic <cit.>,
we score each rule  as follows:
ϕ_w(rule)    = max_path ∈𝒫(rule) ϕ_w(path)

path    :e_0_(h) e_1  e_2 →⋯ e_l_(t)

ϕ_w(path)    = ∏_i=1^lϕ_w(e_i-1, r_i, e_i)

where $\mathcal{P}(\emph{rule})$ is the set of grounding paths which start at ${h}$ and end at ${t}$ following a rule.
$\phi_w({e}_{i-1}, {r}_i, {e}_i)$ is the confidence score obtained by any existing relation models. [This is why our approach is plug-and-play.]

To get the probability (fuzzy truth value) of $\bm{y}$,
we synthesize the evaluation result of each rule in the latent rule set $\bm{z}$.
The satisfaction of any rule body will imply the truth of $\bm{y}$.
Accordingly, we take the disjunction of all rules in $\bm{z}$ as the target truth value.
Following the principled sigmoid-based fuzzy logic function for disjunction <cit.>, we define the fuzzy truth value as:

p_w(y| q, z)    = Sigmoid(y·𝚜𝚌𝚘𝚛𝚎_w(q, z))

𝚜𝚌𝚘𝚛𝚎_w(q, z)    =
ϕ_w(q) + ∑_rule∈zϕ_w(q, rule)ϕ_w(rule)

where $\phi_w({q})$ and $\phi_w({q}, \emph{rule})$ are learnable scalar weights.
$\phi_w({q})$ is a bias term for balancing the score of positive and negative cases.
$\phi_w({q}, \emph{rule})$ estimates the score, namely, the quality of a specific rule.
$\phi_w(\emph{rule})$ evaluates the accessibility from the head entity $h$ to the tail entity $ t$ through the meta path defined by $\emph{rule}$'s body.
Applying logic rules and reasoning over the rules enable the relation extractor to explicitly modeling the long-range dependencies as the interactions among entities and relations.

§.§ Optimization

To optimize the likelihood $\mathcal{L}(w, \theta)$ (Eq. <ref>),
we update the rule generator and the relation extractor alternately in an iterative manner, namely the EM algorithm.
The classic EM algorithm estimates the posterior of the latent variable $\bm{z}$ according to current parameters in the E-step;
The parameters are updated in the M-step with $\bm{z}$ obeys the estimated posterior.
However, in our setting, it is difficult to compute the exact posterior $p(\bm{z}|\bm{y},\bm{q})$ due to the large space of $\bm{z}$.
To tackle this challenge,
we seek an approximate posterior $q(\bm{z})$ by a second-order Taylor expansion.
This modified version of posterior forms a lower bound on $\log p_{w, \theta}(\bm{y} | \bm{q})$,
since the difference between them is a KL
divergence and hence positive:
𝔼_q(z) [logp_w, θ(y, z | q)/p_w, θ(z|q, y) ] ^logp_w, θ(y | q) -  𝔼_q(z) [logp_w, θ(y, z| q)/q(z)]^lower bound

= KL(q(z) || p_w, θ(z | q, y)) ≥0

Once we get $q(\bm{z})$,
we can maximize this lower bound of $\log p_{w, \theta}(\bm{y} | \bm{q})$.

Given the current parameters $\theta, w$,
E-step aims to compute the posterior of $\bm{z}$ according to the current parameters $\theta, w$.
However, the exact posterior $p_{w, \theta}(\bm{z} | \bm{q}, \bm{y})$ is nontrivial due to its intractable partition function (space of $\bm{z}$ is large).
In this work, we aim to seek an approximate posterior $q(\bm{z})$.

By approximating the likelihood with the second-order Taylor expansion, we can obtain a conjugate form of the posterior as a multinomial distribution.
The detailed derivation is listed in Appendix. <ref>.
Formally, we first define $H(\emph{rule})$ as the score function estimating the quality of each rule:
H(rule) = logAutoReg_θ(rule | q) +

Intuitively, $H(\emph{rule})$ evaluates rule quality in two factors.
One is based on the rule generator $p_\theta$,
which servers as the prior probability for each rule.
The other is based on the relation extractor,
and it takes into account the contribution of the current rule to the final correct answer $y^*$.
Next, we use $\hat{p}(\emph{rule}|q)$ to denote the posterior distribution of the rule given the query $q$:

Thus the approximate posterior also obeys a multinomial distribution.
q(z) ∼Multi(N, p̂(rule|q))

EM Optimization for $\mathcal{L}(w, \theta)$
[1]
not converge
For each instance, use the rule generator $p_\theta$ to generate a set of logic rules $\hat{\bm{z}}(|\hat{\bm{z}}| = N)$.

Calculate the rule score $H(\emph{rule})$ of each rule for approximating the posterior of $\emph{rule}$: $\hat{p}(\emph{rule}|\bm{q})$.
For each instance, update the rule generator $\text{AutoReg}_\theta$ based on the sampled rules from $\hat{p}(\emph{rule}|\bm{q})$.
For each instance, update the relation extractor $p_w$ based on generated logic rules $\hat{\bm{z}}$ from the updated rule generator.

After obtaining the $q(\bm{z})$,
M-step is to maximize the lower bound $\log p_{w, \theta}(\bm{y} | \bm{q})$ with respect to both $w$ and $\theta$.
Formally, given each data instance $(y^*, q, \mathcal{D})$ and the $q(\bm{z})$,
the objective is to maximize

ℒ_lower = 𝔼_q(z)[logp_θ(z|q)]^ℒ_G   +
𝔼_q(z)[logp_w, θ(y^* |z,q)]^ℒ_R

where $\mathcal{L}_\mathrm{G}, \mathcal{L}_\mathrm{R}$ are the objective of the rule generator and  the relation extractor, repectively.

For the objective $\mathcal{L}_G$, it can be further converted equally as
ℒ_G = 𝔼_p̂(rule|q)[AutoReg_θ(rule|q)]

To compute the expectation term of $\mathcal{L}_\mathrm{G}$
we sample from the current prior $p_\theta(\bm{z}|q)$ for a sample $\hat{z}$, and evaluate the score of each rule as $H(\emph{rule})$, normalized score over $H(\emph{rule})$ are regarded as the approximated $\hat{p}(\emph{rule}|q)$.
Then we use sampled rules to update the $\text{AutoReg}_\theta(\emph{rule}|q)$.
Intuitively, we update the rule generator $p_\theta(\bm{z}|q)$ to make it consistent with the high-quality rules identified by the approximated posterior.

For the objective $\mathcal{L}_R$, we update the relation extractor according to the logic rules sampled from the updated rule generator.
The logic rules explicitly capturing more interactions between relations can be fused as input to the relation extractor,
which yields better empirical results and enjoys better interpretation.
Finally, we summarize the optimization procedure in Algorithm <ref>.

§ EXPERIMENTS

We conduct experiments on multi-relational document-level relation extraction datasets: DocRED <cit.> and DWIE <cit.>. The statistics of the two datasets are listed in Table <ref>. Pre-processing details of DWIE are described in Appendix <ref>.

2cDataset     #Doc.     #Rel.     #Ent.     #Facts
3*DWIE     train     602     3*65     16494     14410

dev     98           2785     2624

test     99           2623     2459
3*DocRED     train     3053     3*96     59493     38180

dev     1000           19578     12323

test     1000           19539     -

Statistics of Document-level RE Datasets

Besides the commonly used F1 metric for relation extraction, we also include other two metrics for comprehensive evaluation of the models: ign F1, logic. ign F1 was proposed in <cit.> for evaluation with triples appearing in the training set excluded. It avoids information leakage from the training set. We propose logic for evaluation of logical consistency among the prediction results. Specifically, we use the 41 pre-defined rules on the DWIE dataset to evaluate whether the predictions satisfy these gold rules. The rules have a similar form to logic rules defined in Sec. <ref>. We name the precision of these rules on predictions as logic score. Note that these rules are independent of the rule learning and utilization in Sec. <ref> but only used for logic evaluation.

Experimental Settings
The rule generator in our experimental settings is implemented as a transformer with a two-layer encoder and a two-layer decoder, hidden size set to 256. We empirically find the tiny structure is enough for modeling the required rule set. We set the size of the latent rule set $N$ to 50. We limit the maximum length of logic rules to 3 in our setting.

§.§ Baselines

We compare our with the following baselines on document-level RE. The baselines are also used as corresponding backbone models in our framework. <cit.> proposed to apply four state-of-the-art sentence-level RE models to document-level relation extraction: CNN, LSTM, BiLSTM, and Context-Aware. <cit.> proposed GAIN to leverage both mention-level graph and aggregated entity-level graph to simulate the inference process in document-level RE, using graph neural networks.
<cit.> proposed ATLOP, using adaptive thresholding to learn a better adjustable threshold and enhancing the representation of entity pairs with localized context pooling. The implementation details of the baselines are shown in Appendix <ref>.

§.§ Main Results

2*Model     3cDev     3cTest
(lr)2-4 (lr)5-7
ign F1     F1      logic     ign F1     F1     logic
CNN      37.65     47.73     51.70     34.65     46.14     54.69

CNN +     40.31(+2.65)     50.04(+2.71)     72.84(+21.14)     39.21(+4.65)     50.44(+4.30)     73.47(+18.78)

LSTM      40.86     51.77     65.64     40.81     52.60     61.64

LSTM +     42.79(+1.93)     53.60(+1.83)     69.74(+4.10)     43.82(+3.01)     55.03(+2.43)     71.27(+9.63)

BiLSTM      40.46     51.92     64.87     42.03     54.47     64.41

BiLSTM +     42.59(+2.13)     53.83(+1.91)     73.37(+8.50)     43.65(+1.62)     55.14(+0.67)     77.11(+12.70)

Context-Aware     42.06     53.05     69.27     45.37     56.58     70.01

Context-Aware +     43.88(+1.82)     54.49(+1.44)     73.98(+4.71)     48.10(+2.73)     59.22(+2.64)     75.94(+5.93)

GAIN      58.63     62.55     78.30     62.37     67.57     86.19

GAIN +     60.12 (+1.49)     63.91(+1.36)     87.86 (+9.56)     64.43 (+2.06)     69.40(+1.83)     91.22(+5.02)

ATLOP      59.03     64.82      81.98     62.09     69.94     82.76

ATLOP +     60.24(+1.21)     66.76(+1.94)     86.98(+5.00)     64.11(+2.02)      71.78(+1.84)     86.07(+3.31)

Main results on DWIE. (The underlined statistics pass a t-test for significance with $p$ value < 0.01.)

2*Model     2cDev
ign F1     F1
GAIN     57.82     59.99

GAIN +     58.47(+0.65)     60.62(+0.63)
ATLOP     59.02     60.89

ATLOP +     59.17(+0.15)     61.33(+0.44)

Comparison on DocRED. (Full results and analysis are demonstrated in Appendix <ref>.)

Our outperforms the baselines on all of the three metrics. (We mainly analyze the results on DWIE with all three metrics can be evaluated. The results on DocRED are partially demonstrated in Table <ref> and fully discussed in Appendix <ref>.)

Our consistently outperforms various backbone models.
It outperforms various baselines on the DWIE dataset as shown in Table <ref>. We achieve 2.02 test ign F1 and 1.84 test F1 improvements on the current SOTA, ATLOP. The compatibility between and various backbone models shows the generalization ability of our .
The consistent improvements on both sequence-based and graph-based models empirically verified the benefits of explicitly injecting logic rules to document-level relation extraction.

The improvements on graph-based models indicate the effectiveness of modeling interactions among multiple relations and entities. Despite graph-based models provide graphs <cit.> consisting of connections among mentions, entities, and sentences, they seek more powerful representations which implicitly model the intrinsic connections. Our instead builds explicit interactions among the entities and relations through the meta path determined by the rules. The improvements on the current SOTA for graph-based model empirically proved the superiority of such explicit modeling.

Our model achieves better logical consistency compared with the baselines. The results show that achieves up to 18.78 enhancement on the logic metric. Even on the graph-based model, GAIN, we obtain a significant improvement of 5.03 on logical consistency. The improved logic score shows that the predictions of are more consistent with the regular logic patterns in the data. These numbers are evidence of the strength of our iterative-based optimization approach by introducing logic rules as latent variables.

§.§ Analysis & Discussion

We analyze and discuss the superiority of our on capturing long-range dependencies and interpretability. The former is studied by inspecting the inference performance on entity pairs of various distances; The latter is verified by checking the logic rules learned by our rule generator and the case study on predictions.

Performance gaps between ATLOP and -ATLOP for entity pairs with different distances.

Inference cases of our on DWIE by using ATLOP as the backbone model. The grey arrows are relations extracted by the backbone model, solid lines representing true relations while dashed lines representing false relations. The green arrows are new relations correctly extracted by logical reasoning. The blue arrows indicate the potential reasoning paths. We also demonstrate a negative case. In the third example, the red arrow represents a wrong relation extracted by reasoning over wrongly estimated atoms.

Logic rules are shortcuts for comprehension.
The performance enhancement of our becomes more prominent when the distance between entity pairs gets longer. We plot the performance of ATLOP and ATLOP-based on the DWIE dataset with four groups of entity pair distances in Fig. <ref>. The distance is calculated as the number of tokens in between the nearest mentions of an entity pair. Results indicate that our performs better on capturing long dependencies.

Relation extraction for entity pairs with longer distances in between generally performs worse. As shown in the figure, the performance starts to drop as the distance surpasses 100 tokens, indicating the difficulty of modeling long-range dependencies. The redundant information in a long context impedes accurate semantic mapping through powerful representations. This issue increases the complexity of modeling and limits the potential of representation-based approaches.

Our framework with latent logic rules injected can effectively alleviate this problem. The performance drop of our is smaller when the distance between entities gets larger. For entity pairs of distances larger than 400, our achieves up to 4.47 enhancement on test ign F1. By reasoning over local logic units (atoms in rules), we ignore the noisy background information in the text but directly integrate high-level connections among concepts to get the answer.

The reasoning process of our is in line with the comprehension way of we human beings when reading long text. We construct basic concepts and connections between (local logic atoms) for each local part of the text. When the collected information is enough to fit some prior knowledge (logic rules), we deduct new cognition from the existing knowledge. Our provides shortcuts for modeling long text semantics by adding logic reasoning to naive semantics mapping.

played_by$(h, z)\ \land\ $plays_in$(z, t) \rightarrow$ character_in $(h, t)$
(parent_of$(h, z)\ \lor \ $child_of$(h, z)\ \lor \ $spouse_of$(h, z)$)
$\land$ royalty_of$(z, t)\ \rightarrow$ royalty_of$(h,t)$
event_in2$^{-1}(h,z)\ \land$ event_in0$(z, t)\rightarrow$ in0$(h, t)$
minister_of$(h, z)\ \land$ in0$(z, t)\rightarrow$ citizen_of$(h, t)$
member_of$^{-1}(h, z)\ \land$ agent_of$(z, t)\rightarrow$ based_in0$(h, t)$

Example rules extracted from trained on the DWIE dataset.

Interpretability by Generating Rules
Our enjoys better interpretability with the generated latent rule set. After the EM optimization, we can sample from the rule generator for high-quality rules that may contribute to the final predictions. Besides the gold rules previously shown for evaluating logic, mines more logic rules from the data, as shown in Table. <ref>. These logic rules explicitly reveal the interactions among entities and relations in the same document as regular patterns. is more transparent, exhibiting the latent rules by the rule generator.

Case Study
Fig. <ref> shows a few inference cases of our , including two positive examples and a negative one. As shown in the first two examples, can complete the missing relations in the backbone model's outputs by utilizing logical rules.

The soft logical reasoning can remedy the defects of representation-based approaches under specific circumstances.
However, the extra reasoning may also exacerbate errors by reasoning over wrongly estimated logic units. The third example shows such a case. The wrongly estimated atom in0(Vega, Germany) leads to one more wrong relation extracted by reasoning. Fortunately, such errors in our will be more controllable because of the transparency in the logical reasoning part.

We conduct experiments on multi-relational document-level relation extraction datasets: DocRED <cit.> and DWIE <cit.>. The statistics of the two datasets are listed in Table <ref>. Pre-processing details of DWIE are described in Appendix <ref>.

2cDataset     #Doc.     #Rel.     #Ent.     #Facts
3*DWIE     train     602     3*65     16494     14410

dev     98           2785     2624

test     99           2623     2459
3*DocRED     train     3053     3*96     59493     38180

dev     1000           19578     12323

test     1000           19539     -

Statistics of Document-level RE Datasets

Besides the commonly used F1 metric for relation extraction, we also include other two metrics for comprehensive evaluation of the models: ign F1, logic. ign F1 was proposed in <cit.> for evaluation with triples appearing in the training set excluded. It avoids information leakage from the training set. We propose logic for evaluation of logical consistency among the prediction results. Specifically, we use the 41 pre-defined rules on the DWIE dataset to evaluate whether the predictions satisfy these gold rules. The rules have a similar form to logic rules defined in Sec. <ref>. We name the precision of these rules on predictions as logic score. Note that these rules are independent of the rule learning and utilization in Sec. <ref> but only used for logic evaluation.

Experimental Settings
The rule generator in our experimental settings is implemented as a transformer with a two-layer encoder and a two-layer decoder, hidden size set to 256. We empirically find the tiny structure is enough for modeling the required rule set. We set the size of the latent rule set $N$ to 50. We limit the maximum length of logic rules to 3 in our setting.

§.§ Baselines

We compare our with the following baselines on document-level RE. The baselines are also used as corresponding backbone models in our framework. <cit.> proposed to apply four state-of-the-art sentence-level RE models to document-level relation extraction: CNN, LSTM, BiLSTM, and Context-Aware. <cit.> proposed GAIN to leverage both mention-level graph and aggregated entity-level graph to simulate the inference process in document-level RE, using graph neural networks.
<cit.> proposed ATLOP, using adaptive thresholding to learn a better adjustable threshold and enhancing the representation of entity pairs with localized context pooling. The implementation details of the baselines are shown in Appendix <ref>.

§.§ Main Results

2*Model     3cDev     3cTest
(lr)2-4 (lr)5-7
ign F1     F1      logic     ign F1     F1     logic
CNN      37.65     47.73     51.70     34.65     46.14     54.69

CNN +     40.31(+2.65)     50.04(+2.71)     72.84(+21.14)     39.21(+4.65)     50.44(+4.30)     73.47(+18.78)

LSTM      40.86     51.77     65.64     40.81     52.60     61.64

LSTM +     42.79(+1.93)     53.60(+1.83)     69.74(+4.10)     43.82(+3.01)     55.03(+2.43)     71.27(+9.63)

BiLSTM      40.46     51.92     64.87     42.03     54.47     64.41

BiLSTM +     42.59(+2.13)     53.83(+1.91)     73.37(+8.50)     43.65(+1.62)     55.14(+0.67)     77.11(+12.70)

Context-Aware     42.06     53.05     69.27     45.37     56.58     70.01

Context-Aware +     43.88(+1.82)     54.49(+1.44)     73.98(+4.71)     48.10(+2.73)     59.22(+2.64)     75.94(+5.93)

GAIN      58.63     62.55     78.30     62.37     67.57     86.19

GAIN +     60.12 (+1.49)     63.91(+1.36)     87.86 (+9.56)     64.43 (+2.06)     69.40(+1.83)     91.22(+5.02)

ATLOP      59.03     64.82      81.98     62.09     69.94     82.76

ATLOP +     60.24(+1.21)     66.76(+1.94)     86.98(+5.00)     64.11(+2.02)      71.78(+1.84)     86.07(+3.31)

Main results on DWIE. (The underlined statistics pass a t-test for significance with $p$ value < 0.01.)

2*Model     2cTest
ign F1     F1
GAIN     57.93     60.07

GAIN +     58.62(+0.69)     60.61(+0.54)
ATLOP     59.14     61.13

ATLOP +     59.48(+0.34)     61.45(+0.32)

Comparison on DocRED. The improvements are less significant with reasons analyzed in Sec. <ref>.

Our outperforms the baselines on all of the three metrics. (We mainly analyze the results on DWIE with all three metrics can be evaluated. The results on DocRED are demonstrated in Table <ref> and discussed in Sec. <ref>.)

Our consistently outperforms various backbone models.
It outperforms various baselines on the DWIE dataset as shown in Table <ref>. We achieve 2.02 test ign F1 and 1.84 test F1 improvements on the current SOTA, ATLOP. The compatibility between and various backbone models shows the generalization ability of our .
The consistent improvements on both sequence-based and graph-based models empirically verified the benefits of explicitly injecting logic rules to document-level relation extraction.

The improvements on graph-based models indicate the effectiveness of modeling interactions among multiple relations and entities. Despite graph-based models provide graphs <cit.> consisting of connections among mentions, entities, and sentences, they seek more powerful representations which implicitly model the intrinsic connections. Our instead builds explicit interactions among the entities and relations through the meta path determined by the rules. The improvements on the current SOTA for graph-based model empirically proved the superiority of such explicit modeling.

Our model achieves better logical consistency compared with the baselines. The results show that achieves up to 18.78 enhancement on the logic metric. Even on the graph-based model, GAIN, we obtain a significant improvement of 5.03 on logical consistency. The improved logic score shows that the predictions of are more consistent with the regular logic patterns in the data. These numbers are evidence of the strength of our iterative-based optimization approach by introducing logic rules as latent variables.

§.§ Analysis & Discussion

We analyze the results on DocRED data and discuss the superiority of our on capturing long-range dependencies and interpretability. The capability of capturing long-range dependencies is studied by inspecting the inference performance on entity pairs of various distances. The interpretability is verified by checking the logic rules learned by our rule generator and the case study on predictions.

Analysis on DocRED Results

In comparison with the significant improvements on DWIE, the enhancement of on DocRED is less significant. Our analysis shows that the reasons are relatively shorter dependencies in DocRED and the logical inconsistency caused by incomplete annotations.

Distribution of Distance Between Entity Pairs in DocRED

a) Shorter Dependencies in DocRED
Shorter dependencies in DocRED lower the demand for capturing long-range correlations among entities and relations. We show the distribution of distance between entity pairs in Fig. <ref>. 79.26% of entity pairs in DocRED have distances less than 100 tokens. The examples in DocRED are less difficult on capturing long-range dependencies. More analysis and comparison can be found in <cit.>. The representation-based approaches can already perform well in such cases. The benefits of modeling long-range dependencies through logical reasoning will be smaller.

implication rule     error rate
father$(h,z)\ \land$ spouse$(z, t)\rightarrow$ mother$(h, t)$     24.07%

replaces$^{-1}(h,t)\rightarrow$ replaced_by$(h, t)$     22.22%

capital$^{-1}(h,t)\rightarrow$ capital_of$(h, t)$     28.24%

father$^{-1}(h, t)\rightarrow$ child$(h, t)$     10.26%

followed$^{-1}(h, t)\rightarrow$ follows$(h, t)$     22.40%

capital$^{-1}(h, t)\rightarrow$ capital_of$(h, t)$     28.24%

P150$^{-1}(h, t)\rightarrow$ P131$(h,t)$     19.71%

The logical inconsistency in the DocRED (for conciseness, P150 represents the relation 'contains administrative territorial entity' and P131 represents the relation 'located in the administrative territorial entity'). The shown easy-to-verify gold rules have high error rates in DocRED while a considerable part of relations (12.96%) are involved in as atoms in shown rules. Those missing annotations make the learning of logic rules difficult. Inconsistent patterns or statistics between training and test may lead to unfair evaluation of relation extraction performance.

b) Logical Inconsistency in DocRED
The justification of predictions after reasoning may be not accurate because of missing annotations. We calculated the error rate of a few easy-to-verify logic rules as shown in Table. <ref>. The 7 rules, selected by case study, have a considerable part (12.96%) of labeled relations may participate in as atoms. However, the statistics in the table demonstrated that all the 7 rules have error rates higher than 10%. The numbers indicated that a notable partition of true relations are missing. The results obtained by reasoning over logic rules may be wrongly justified since the data is not exhaustively annotated.

According to the analysis above, our has greater potential than that demonstrated as the overall performance on DocRED.

Performance gaps between ATLOP and -ATLOP for entity pairs with different distances.

Logic rules are shortcuts for comprehension.
The performance enhancement of our becomes more prominent when the distance between entity pairs gets longer. We plot the performance of ATLOP and ATLOP-based on the DWIE dataset with four groups of entity pair distances in Fig. <ref>. The distance is calculated as the number of tokens in between the nearest mentions of an entity pair. Results indicate that our performs better on capturing long dependencies.

Relation extraction for entity pairs with longer distances in between generally performs worse. As shown in the figure, the performance starts to drop as the distance surpasses 100 tokens, indicating the difficulty of modeling long-range dependencies. The redundant information in a long context impedes accurate semantic mapping through powerful representations. This issue increases the complexity of modeling and limits the potential of representation-based approaches.

Our framework with latent logic rules injected can effectively alleviate this problem. The performance drop of our is smaller when the distance between entities gets larger. For entity pairs of distances larger than 400, our achieves up to 4.47 enhancement on test ign F1. By reasoning over local logic units (atoms in rules), we ignore the noisy background information in the text but directly integrate high-level connections among concepts to get the answer.

The reasoning process of our is in line with the comprehension way of we human beings when reading long text. We construct basic concepts and connections between (local logic atoms) for each local part of the text. When the collected information is enough to fit some prior knowledge (logic rules), we deduct new cognition from the existing knowledge. Our provides shortcuts for modeling long text semantics by adding logic reasoning to naive semantics mapping.

played_by$(h, z)\ \land\ $plays_in$(z, t) \rightarrow$ character_in $(h, t)$
(parent_of$(h, z)\ \lor \ $child_of$(h, z)\ \lor \ $spouse_of$(h, z)$)
$\land$ royalty_of$(z, t)\ \rightarrow$ royalty_of$(h,t)$
event_in2$^{-1}(h,z)\ \land$ event_in0$(z, t)\rightarrow$ in0$(h, t)$
minister_of$(h, z)\ \land$ in0$(z, t)\rightarrow$ citizen_of$(h, t)$
member_of$^{-1}(h, z)\ \land$ agent_of$(z, t)\rightarrow$ based_in0$(h, t)$

Example rules extracted from trained on the DWIE dataset.

Inference cases of our on DWIE by using ATLOP as the backbone model. The grey arrows are relations extracted by the backbone model, solid lines representing true relations while dashed lines representing false relations. The green arrows are new relations correctly extracted by logical reasoning. The blue arrows indicate the potential reasoning paths. We also demonstrate a negative case. In the third example, the red arrow represents a wrong relation extracted by reasoning over wrongly estimated atoms.

Interpretability by Generating Rules
Our enjoys better interpretability with the generated latent rule set. After the EM optimization, we can sample from the rule generator for high-quality rules that may contribute to the final predictions. Besides the gold rules previously shown for evaluating logic, mines more logic rules from the data, as shown in Table. <ref>. These logic rules explicitly reveal the interactions among entities and relations in the same document as regular patterns. is more transparent, exhibiting the latent rules by the rule generator.

Case Study
Fig. <ref> shows a few inference cases of our , including two positive examples and a negative one. As shown in the first two examples, can complete the missing relations in the backbone model's outputs by utilizing logical rules.

The soft logical reasoning can remedy the defects of representation-based approaches under specific circumstances.
However, the extra reasoning may also exacerbate errors by reasoning over wrongly estimated logic units. The third example shows such a case. The wrongly estimated atom in0(Vega, Germany) leads to one more wrong relation extracted by reasoning. Fortunately, such errors in our will be more controllable because of the transparency in the logical reasoning part.

§ CONCLUSION

In this paper, we proposed a probabilistic model , which utilizes rules and conducts reasoning over the rules for document-level relation extraction. The logic rules are treated as latent variables. We utilize the EM algorithm to efficiently maximize the overall likelihood. By injecting rules to the relation extraction framework, our explicitly models the long-range dependencies in docRE as interactions among relations and entities, thus enjoying better interpretability. Empirical results and analysis show that outperforms strong baselines on overall performance, logical consistency, and capability for capturing long-range dependencies.

§ ACKNOWLEDGEMENTS

The SJTU team is supported by Shanghai Municipal Science and Technology Major Project (2021SHZDZX0102) and National Natural Science Foundation of China (61772333). We thank Xinbo Zhang, Jingjing Xu, Yuxuan Song, Wenxian Shi and other anonymous reviewers for their insightful and detailed comments.

§ APPROXIMATION OF THE TRUE POSTERIOR

The exact posterior of the latent rule set $\bm{z}$ is difficult to be directly calculated because of the large space.
In this section, we provide the detailed derivation for the approximate posterior.

\begin{equation*}
\begin{aligned}
&\log p(\bm{z}|\bm{y},\bm{q},\mathcal{D}) \\
=& \log p_w(\bm{y}|\bm{q},\bm{z},\mathcal{D}) + \log p_\theta(\bm{z}|\bm{q}) + C \\
=& \log\frac{1}{1+e^{-\bm{y}\cdot\mathtt{score}(\mathbf{q}, \bm{z})}} + \sum_{rule\in\bm{z}}\log\text{AutoReg}_\theta(rule|\bm{q}) + C \\
\approx&\frac{1}{2} \bm{y}\cdot\mathtt{score}_w(\bm{q},\bm{z}) + \sum_{rule\in\bm{z}}\log \text{AutoReg}_\theta(rule|\bm{q}) + C \\
=&\sum_{\emph{rule}\in\bm{z}}(\frac{1}{2}\bm{y}\cdot(\frac{1}{N}(\phi_w(\bm{q}) + \phi_w(\bm{q},\emph{rule})\phi_w(\emph{rule})) \\ &+\log\text{AutoReg}_\theta(\emph{rule}|\bm{q})) + C
\end{aligned}
\end{equation*}

The approximation is obtained by the following second-order Taylor expansion:

\begin{equation*}
-\log(1 + e^{-x}) = -\log2 + \frac{x}{2} + O(x^2)
\end{equation*}

By such approximation, we can decompose the posterior to each rule in the latent rule set. We first define the score for each rule:

H(rule) = logAutoReg_θ(rule | q) +

Then, it's easy to obtain that the approximated posterior $q(\bm{z})$ and the prior $p_\theta$ are conjugate distributions.

\begin{equation*}
\begin{aligned}
q(\bm{z}) \sim \text{Multi}(N, \frac{1}{Z}\exp(H(\emph{rule})))
\end{aligned}
\end{equation*}

where $Z$ is the normalization factor.

\begin{equation*}
\begin{aligned}
\text{AutoReg}_\theta(rule|q) = \prod_{i=1}^l\text{AutoReg}_\theta(r_{i}|q, r_1, r_2, ..., r_{i-1})
\end{aligned}
\end{equation*}

§ IMPLEMENTATION DETAILS

DWIE Dataset Preprocessing
The original DWIE dataset <cit.> is designed for four sub-tasks in the information extraction, including named entity recognition, coreference resolution, relation extraction, and entity linking. In this paper, we focus on the document-level RE task. We only use the dataset for document-level relation extraction. The original dataset published 802 documents with 23130 entities in total, 702 for train and 100 for test. In our setting, we remove the entities without mentions in the context. After the cleaning, we have 700 documents for train and 99 documents for test. The training set is then randomly split into two parts: 602 documents for train and 98 for development. The statistics of the preprocessed dataset are shown in Table <ref> of the main body.

We use their published open-source code to implement the baselines <cit.>, as well as the backbone models in our framework. The pre-trained language models used in GAIN and ATLOP follows the original paper <cit.>, using the pre-trained bert-base-uncased and bert-base-cased models respectively. The hyperparameters reserve the same as in their papers.