# Humanly Certifying Superhuman Classifiers

Qiongkai Xu,1,2 Christian Walder, 1,2 Chenchen Xu 1,2

# Humanly Certifying Superhuman Classifiers

Qiongkai Xu,1,2 Christian Walder, 1,2 Chenchen Xu 1,2

###### Abstract

Estimating the performance of a machine learning system is a longstanding
challenge in artificial intelligence research. Today, this challenge is
especially relevant given the emergence of systems which appear to
increasingly outperform human beings. In some cases, this “superhuman”
performance is readily demonstrated; for example by defeating legendary human
players in traditional two player games. On the other hand, it can be
challenging to evaluate classification models that potentially surpass human
performance. Indeed, human annotations are often treated as a ground truth,
which implicitly assumes the superiority of the human over any models trained
on human annotations. In reality, human annotators can make mistakes and be
subjective. Evaluating the performance with respect to a genuine oracle may be
more objective and reliable, even when querying the oracle is expensive or
impossible. In this paper, we first raise the challenge of evaluating the
performance of both humans and models with respect to an oracle which is
unobserved. We develop a theory for estimating the accuracy compared to the
oracle, using only imperfect human annotations for reference. Our analysis
provides a simple recipe for detecting and certifying superhuman performance
in this setting, which we believe will assist in understanding the stage of
current research on classification. We validate the convergence of the bounds
and the assumptions of our theory on carefully designed toy experiments with
known oracles. Moreover, we demonstrate the utility of our theory by meta-
analyzing large-scale natural language processing tasks, for which an oracle
does not exist, and show that under our assumptions a number of models from
recent years are with high probability superhuman.

##  1 Introduction

Artificial Intelligence (AI) agents have begun to outperform humans on
remarkably challenging tasks; AlphaGo defeated legendary Go players (Silver et
al. 2016; Singh, Okun, and Jackson 2017), and OpenAI’s Dota2 AI has defeated
human world champions of the game (Berner et al. 2019). These AI tasks may be
evaluated objectively, e.g. using the total score achieved in a game and the
victory or defeat against another player. However, for supervised learning
tasks such as image classification and sentiment analysis, certifying a
machine learning model as superhuman is subjectively tied to human judgments
rather than comparing with an oracle. This work focuses on paving a way
towards evaluating models with potentially superhuman performance in
classification.

Figure 1: The relationship between a) the oracle accuracy of the annotators,
$P(\ell_{i}=\ell_{\star})$, and b) the agreement between two annotators,
$P(\ell_{i}=\ell_{j})$. $\ell_{i}$ and $\ell_{j}$ are labels given by
annotator $i$ and $j$, $\ell_{\star}$ is the oracle label. In our setting,
part a) is unobserved (gray) and part b) is observed (black).

When evaluating the performance of a classification model, we generally rely
on the accuracy of the predicted labels with regard to ground truth labels,
which we call the oracle accuracy. However, oracle labels may arguably be
unobservable. For tasks such as object detection, the predictions are
subjective to many factors of the annotators, e.g., their background and
physical or mental state. For other tasks, even experts may not be able to
summarize an explicit rule for the prediction, such as predicting molecule
toxicity and stability. Without observing the oracle labels, human predictions
or aggregated human annotations are treated as ground truth (Wang et al. 2018;
Lin et al. 2014; Wang et al. 2019) to approximate the oracle. Such
approximation mainly suffers from two disadvantages. Firstly, the quality
control of human annotation is challenging (Artstein 2017; Lampert, Stumpf,
and Gançarski 2016). Secondly, current evaluation paradigms focus on
evaluating the performance of models, but not the oracle accuracy of humans —
yet we cannot claim that a machine learning model is superhuman without a
proper estimation on human performance.

In this paper, we work on the setting that oracle labels are unobserved (see
Figure 1). Within this setting, we develop a theory for estimating the oracle
accuracy on classification tasks. Our theory includes i) upper bounds for the
averaged oracle accuracy of the annotators, ii) lower bounds for the oracle
accuracy of the model, and iii) finite sample analysis for both bounds and
their margin which represents the model’s outperformance. We propose an
algorithm to discover competitive models and to report confidence scores,
which formally bound the probability that a given model outperforms the
average human annotator. Empirically, we observe that some existing models for
sentiment classification and natural language inference (NLI) have already
achieved superhuman performance.

##  2 Related Work

Classification accuracy is a widely used measure of model performance (Han,
Pei, and Kamber 2011), although there are other options such as precision,
recall, F1-score (Chowdhury 2010; Sasaki et al. 2007), Matthews correlation
coefficient (Matthews 1975; Chicco and Jurman 2020), etc.. Accuracy measures
the disagreement between the model outputs and some reference labels. A common
practice is to collect human labels to treat as the reference. However, we
argue that the ideal reference is rather the (unobserved) oracle, as human
predictions are imperfect. We focus on measuring the oracle accuracy for both
human annotators and machine learning models, and for comparing the two.

A widely accepted approach is to crowd source (Kittur, Chi, and Suh 2008;
Mason and Suri 2012) a dataset for testing purposes. The researchers collect a
large corpus with each examples labeled by multiple annotators. Then, the
aggregated annotations are treated as ground truth labels (Socher et al. 2013;
Bowman et al. 2015). This largely reduces the variance of the prediction
(Nowak and Rüger 2010; Kruger et al. 2014), however, such aggregated results
are still not oracle, and their difference to oracle remains unclear. In our
paper, we proves that the accuracy on aggregated human prediction, as ground
truth, could be considered as a special case of the lower bound of oracle
accuracy for machine learning models. On the other hand, much work considers
the reliability of collected data, by providing the agreement scores between
annotators (Landis and Koch 1977). Statistical measures for the reliability of
inter-annotator agreement (Gwet 2010), such as Cohen’s Kappa (Pontius Jr and
Millones 2011) and Fleiss’ Kappa (Fleiss 1971), are normally based on the raw
agreement ratio. However, the agreement between annotators does not obviously
reflect the oracle accuracy; e.g. identical predictions from two annotators
does not mean they are both oracles. In our paper, we prove that observed
agreement between all annotators could serve as an upper bound for the average
oracle accuracy of those annotators. Overall, we propose a theory for
comparing the oracle accuracy of human annotators and machine learning models,
by connecting the aforementioned bounds.

The discovery that models can predict better than human experts dates back at
least to the seminal and controversial work of Meehl (1954), which compared ad
hoc predictions based on subjective and informal information to those based on
simple linear models with a (typically small) number of relevant numeric
attributes. Subsequent work found that one may even train such a model to
mimic the predictions made by the experts (rather than an oracle), and yet
still maintain superior out of sample performance (Goldberg 1970). The
comparison of human and algorithmic decision making remains an active topic of
psychology research (Kahneman, Sibony, and Sunstein 2021).

##  3 Evaluation Theory

In this section, we present the theory for comparing the oracle accuracy for
classification tasks between human annotators and machine learning models.

###  3.1 Problem Statement

We are given $K$ labels crowd sourced from $K$ human annotators,
$\\{\ell_{i}\\}_{i=1}^{K}$, along some labels from a model
$\ell_{\mathcal{M}}$. We denote $\ell_{a}^{(n)}$ and
$\ell_{\mathcal{M}}^{(n)}$ the label assigned by annotator $a$ and model
$\mathcal{M}$ to the $n$-th data point, for $n=1,2,\dots,N$. We observe the
ratio of matched labels $\mathbb{P}(\ell_{a}=\ell_{b})$ for all of a pairs of
annotators $a$ and $b$. Denote by $\ell_{\mathcal{K}}$ the label of the
“average” human annotator which we define as the label obtained by selecting
one of the $K$ human annotators uniformly at random. We seek to formally
compare the oracle accuracy of the average human,
$\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})$, with that of the machine
learning model, $\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})$, where
$\ell_{\star}$ is the unobserved oracle label. Denote by $\ell_{\mathcal{G}}$
the label obtained by aggregating (say, by majority voting) the $K$ human
annotators’ labels. Our work distinguishes between the oracle accuracy
$\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})$ and the agreement with human
annotations $\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\mathcal{G}})$, although
these two concepts have been confounded in many previous applications and
benchmarks.

###  3.2 An Upper Bound for the Average Annotator Performance

The oracle accuracy of the average annotator $\ell_{\mathcal{K}}$ follows the
definition of the previous section, and conveniently equals the average of the
oracle accuracy of each annotator, i.e.

$\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})=\frac{1}{K}\sum_{i=1}^{K}\mathbb{P}(\ell_{i}=\ell_{\star}).$
(1)

By introducing an assumption, also discussed in Section 4.2, we may bound the
above quantity.

######  Theorem 1 (Average Performance Upper Bound).

Assume annotators are positively correlated, namely
$\mathbb{P}(\ell_{i}=\ell_{\star}|\ell_{j}=\ell_{\star})\geq\mathbb{P}(\ell_{i}=\ell_{\star})$.
Then, the upper bound of averaged annotator accuracy with respect to the
oracle is

$\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\leq\mathcal{U}\triangleq\sqrt{\frac{1}{K^{2}}\sum_{i=1}^{K}\sum_{j=1}^{K}\mathbb{P}(\ell_{i}=\ell_{j})}.$
(2)

######  Proof.

For $i\neq j$ and $i,j\in\\{1,\cdots,K\\}$, we have

$\displaystyle\mathbb{P}(\ell_{i}=\ell_{j})=$
$\displaystyle\mathbb{P}(\ell_{i}=\ell_{j}|\ell_{j}=\ell_{\star})\mathbb{P}(\ell_{j}=\ell_{\star})+$
$\displaystyle\mathbb{P}(\ell_{i}=\ell_{j}|\ell_{j}\neq\ell_{\star})\mathbb{P}(\ell_{j}\neq\ell_{\star})$
$\displaystyle\geq$
$\displaystyle\mathbb{P}(\ell_{i}=\ell_{j}|\ell_{j}=\ell_{\star})\mathbb{P}(\ell_{j}=\ell_{\star})$
$\displaystyle=$
$\displaystyle\mathbb{P}(\ell_{i}=\ell_{\star}|\ell_{j}=\ell_{\star})\mathbb{P}(\ell_{j}=\ell_{\star})$
$\displaystyle\geq$
$\displaystyle\mathbb{P}(\ell_{i}=\ell_{\star})\mathbb{P}(\ell_{j}=\ell_{\star}).$
(3)

While for $i=j$, we have $\mathbb{P}(\ell_{i}=\ell_{j})=1$. Therefore,

$\mathbb{P}(\ell_{i}=\ell_{j})\geq\mathbb{P}(\ell_{i}=\ell_{\star})\mathbb{P}(\ell_{j}=\ell_{\star}).$
(4)

Then, combining (3) and (4),

$\displaystyle\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})^{2}=$
$\displaystyle\frac{1}{K^{2}}\sum_{i=1}^{K}\mathbb{P}(\ell_{i}=\ell_{\star})\sum_{j=1}^{K}\mathbb{P}(\ell_{j}=\ell_{\star})$
(5) $\displaystyle\leq$
$\displaystyle\frac{1}{K^{2}}\sum_{i=1}^{K}\sum_{j=1}^{K}\mathbb{P}(\ell_{i}=\ell_{j})$
(6) $\displaystyle\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\leq$
$\displaystyle\sqrt{\frac{1}{K^{2}}\sum_{i=1}^{K}\sum_{j=1}^{K}\mathbb{P}(\ell_{i}=\ell_{j})}.$
(7)

We observe that $\mathbb{P}(\ell_{i}=\ell_{j})$ is overestimated as $1$ when
$i=j$, but that the total overestimation to $\mathcal{U}^{2}$ is less or equal
to $1/K$ ($K$ out of $K^{2}$ terms), and that the influence will reduce and
converge to zero as $K\rightarrow\infty$. To calibrate the overestimation, we
introduce an empirically approximated upper bound $\mathcal{U}^{(e)}$. In
contrast, $\mathcal{U}$ in (2) is also noted as theoretical upper bound,
$\mathcal{U}^{(t)}$.

######  Definition 1.

The empirically approximated upper bound,

$\mathcal{U}^{(e)}\triangleq\sqrt{\frac{1}{K(K-1)}\sum_{i=1}^{K}\sum_{\begin{subarray}{c}j=1\\\
i\neq j\end{subarray}}^{K}\mathbb{P}(\ell_{i}=\ell_{j})}.$ (8)

######  Lemma 2 (Convergence of $\mathcal{U}^{(e)}$).

Assume that $\mathbb{P}(\ell_{i}=\ell_{j})\geq 1/N_{c}$, where $N_{c}$ is
number of classes. The approximated upper bound $\mathcal{U}^{(e)}$ satisfies

$\lim_{K\rightarrow+\infty}\mathcal{U}/\mathcal{U}^{(e)}=1.$ (9)

Therefore, with large $K$, $\mathcal{U}^{(e)}$ converges to $\mathcal{U}$ or
$\mathcal{U}^{(t)}$.

We provide a detailed proof of this Lemma in Appendix A. Some empirical
evidences for the convergence of the $\mathcal{U}^{(e)}$ to
$\mathcal{U}^{(t)}$ are demonstrated in Section 4.2.

###  3.3 A Lower Bound for Model Performance

For our next result, we introduce another assumption, also discussed in
Section 4.2. Given two predicted labels $\ell_{a}$ and $\ell_{b}$, we assume
that $\ell_{b}$ is reasonably predictive even on those instances that $a$ gets
wrong, as per

######  Theorem 3 (Performance Lower Bound).

Assume that for any incorrect label $\ell_{\times}\neq\ell_{\star}$,

$\mathbb{P}(\ell_{b}=\ell_{\star}|\ell_{a}\neq\ell_{\star})\geq\mathbb{P}(\ell_{b}=\ell_{\times}|\ell_{a}\neq\ell_{\star}).$
(10)

Then, the lower bound for the oracle accuracy of $\ell_{b}$ is

$\mathcal{L}\triangleq\mathbb{P}(\ell_{a}=\ell_{b})\leq\mathbb{P}(\ell_{b}=\ell_{\star}).$
(11)

######  Proof.

$\displaystyle\mathbb{P}(\ell_{a}=\ell_{b})=$
$\displaystyle\mathbb{P}(\ell_{b}=\ell_{a}|\ell_{a}\neq\ell_{\star})\mathbb{P}(\ell_{a}\neq\ell_{\star})+$
$\displaystyle\mathbb{P}(\ell_{b}=\ell_{a}|\ell_{a}=\ell_{\star})\mathbb{P}(\ell_{a}=\ell_{\star})$
$\displaystyle\leq$
$\displaystyle\mathbb{P}(\ell_{b}=\ell_{\star}|\ell_{a}\neq\ell_{\star})\mathbb{P}(\ell_{a}\neq\ell_{\star})+$
$\displaystyle\mathbb{P}(\ell_{b}=\ell_{a}|\ell_{a}=\ell_{\star})\mathbb{P}(\ell_{a}=\ell_{\star})$
$\displaystyle=$
$\displaystyle\mathbb{P}(\ell_{b}=\ell_{\star}|\ell_{a}\neq\ell_{\star})\mathbb{P}(\ell_{a}\neq\ell_{\star})+$
$\displaystyle\mathbb{P}(\ell_{b}=\ell_{\star}|\ell_{a}=\ell_{\star})\mathbb{P}(\ell_{a}=\ell_{\star})$
$\displaystyle=$ $\displaystyle\mathbb{P}(\ell_{b}=\ell_{\star}).$ (12)

In practice, a more accurate $\ell_{a}$ gives a tighter lower bound for
$\ell_{b}$, and so we employ the aggregated human annotations for the former
(letting $\ell_{a}=\ell_{\mathcal{G}}$) to calculate the lower bound of the
machine learning model (letting $\ell_{b}=\ell_{\mathcal{M}}$), as
demonstrated in Section 4.2.

#### Connection to common practice.

Generally, the ground truth of a benchmark corpus is constructed by
aggregating multiple human annotations (Wang et al. 2018, 2019). For example,
the averaged sentiment score is used in SST (Socher et al. 2013) and majority
of votes in SNLI (Bowman et al. 2015). Then, the aggregated annotations are
treated as ground truth to calculate accuracy. Under this setting, the
accuracy on the (aggregated) human ground truth may be viewed as a special
case of our lower bound.

###  3.4 Finite Sample Analysis

The results above assume that the agreement probabilities are known; we now
connect with the finite sample case where those probabilities are estimated
empirically. We begin with a standard concentration inequality (see e.g.
(Boucheron, Lugosi, and Massart 2013, § 2.6)),

######  Theorem 4 (Hoeffding’s Inequality).

Let $X_{1},\dots,X_{N}$ be independent random variables with finite variance
such that $\mathbb{P}(X_{n}\in[\alpha,\beta])=1$, for all $1\leq n\leq N$. Let

$\overline{X}\triangleq\frac{1}{N}\sum_{n=1}^{N}X_{n},$

then, for any $t>0$,

$\displaystyle\mathbb{P}(\overline{X}-\mathbb{E}[\overline{X}]\geq+t)\leq\exp\left(-\frac{2Nt^{2}}{(\alpha-\beta)^{2}}\right),$
$\displaystyle\mathbb{P}(\overline{X}-\mathbb{E}[\overline{X}]\leq-t)\leq\exp\left(-\frac{2Nt^{2}}{(\alpha-\beta)^{2}}\right).$
(13)

Combining this with Thereom 1 we obtain the following.

######  Theorem 5 (Sample Average Performance Upper Bound).

Take the assumptions of Theorem 1, and let

$\displaystyle\mathbb{P}^{(N)}(\ell_{i}=\ell_{j})=\frac{1}{N}\sum_{n=1}^{N}\left[\ell^{(n)}_{i}=\ell^{(n)}_{j}\right]$
(14)

be the empirical agreement ratio111Here $[\cdot]$ is the Iverson bracket..
Define

$\displaystyle\delta_{u}=\exp(-2Nt_{u}^{2}).$ (15)

With probability at least $1-\delta_{u}$, for any $t_{u}>0$,

$\displaystyle\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\leq\sqrt{t_{u}+\frac{1}{K^{2}}\sum_{i=1}^{K}\sum_{j=1}^{K}\mathbb{P}^{(N)}(\ell_{i}=\ell_{j})}.$
(16)

######  Proof.

We apply Theorem 4 with

$\displaystyle
X_{n}=\frac{1}{K^{2}}\sum_{i=1}^{K}\sum_{j=1}^{K}\left[\ell^{(n)}_{i}=\ell^{(n)}_{j}\right],$
(17)

obtaining $X_{n}\in[0,1]$, i.e. $\alpha=0$, and $\beta=1$. Let

$\displaystyle\mathcal{U}_{N}\triangleq\sqrt{\frac{1}{K^{2}}\sum_{i=1}^{K}\sum_{j=1}^{K}\mathbb{P}^{(N)}(\ell_{i}=\ell_{j})}.$
(18)

Our choice (17) of $X_{n}$ implies $\mathcal{U}_{N}^{2}=\overline{X}$ and
$\mathcal{U}^{2}=\mathbb{E}[\overline{X}]$, and so by (4),

$\displaystyle\mathbb{P}\left(\sqrt{t_{u}+\mathcal{U}_{N}^{2}}\leq\mathcal{U}\right)\leq\delta_{u}.$
(19)

Rewrite (2) as

$\displaystyle\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\leq\mathcal{U},$
(20)

which implies

$\displaystyle\mathbb{P}\left(\sqrt{t_{u}+\mathcal{U}_{N}^{2}}\leq\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\right)\leq\mathbb{P}\left(\sqrt{t_{u}+\mathcal{U}_{N}^{2}}\leq\mathcal{U}\right).$
(21)

Combining (19) with (21) gives the result.

Analagously for Theorem 3, we have

######  Theorem 6 (Sample Performance Lower Bound).

Take the assumptions of Theorem 3 along with (14). Define

$\displaystyle\delta_{l}=\exp(-2Nt_{l}^{2}).$ (22)

With probability at least $1-\delta_{l}$, for any $t_{l}>0$,

$\displaystyle\mathbb{P}^{(N)}(\ell_{a}=\ell_{b})\leq
t_{l}+\mathbb{P}(\ell_{b}=\ell_{\star}).$ (23)

######  Proof.

We apply Theorem 4 with

$\displaystyle X_{n}=\left[\ell^{(n)}_{a}=\ell^{(n)}_{b}\right],$ (24)

obtaining $X_{n}\in[0,1]$, i.e. $\alpha=0$, and $\beta=1$. Let

$\displaystyle\mathcal{L}_{N}\triangleq\mathbb{P}^{(N)}(\ell_{a}=\ell_{b}).$
(25)

Now (24) implies $\mathcal{L}_{N}=\overline{X}$ and
$\mathcal{L}=\mathbb{P}(\ell_{a}=\ell_{b})=\mathbb{E}[\overline{X}]$,

$\displaystyle\mathbb{P}\left(\mathcal{L}_{N}-t_{l}\geq\mathcal{L}\right)\leq\delta_{l}.$
(26)

Recall (11),
$\mathbb{P}(\ell_{a}=\ell_{b})\leq\mathbb{P}(\ell_{b}=\ell_{\star})$, which
implies

$\displaystyle\mathbb{P}\left(\mathcal{L}_{N}-t_{l}\geq\mathbb{P}(\ell_{b}=\ell_{\star})\right)\leq\mathbb{P}\left(\mathcal{L}_{N}-t_{l}\geq\mathcal{L}\right).$
(27)

Combining (26) with (27) gives the result.

###  3.5 Detecting and Certifying Superhuman Models

We propose a procedure to discover potentially superhuman models based on our
theorems.

  * •

Calculate the upper bound of the average oracle accuracy of human annotators,
$\mathcal{U}_{N}$, with $N$ samples;

  * •

Calculate the lower bound of the model oracle accuracy $\mathcal{L}_{N}$ using
aggregated human annotations as the reference222We demonstrate that
aggregating the predictions by voting and weighted averaging are effective in
improving our bounds. We emphasize however that the aggregated predictions
need not be perfect, as we do not assume that this aggregation yields an
oracle., with $N$ samples;

  * •

Check whether the finite sample margin $\mathcal{L}_{N}-\mathcal{U}_{N}$ is
larger than zero;

  * •

Give proper estimation of $t_{u}$ and $t_{l}$ and calculate a confidence score
of $\mathbb{P}(\mathcal{L}-\mathcal{U}\geq 0)$.

Generally, larger margin indicates higher confidence of the out-performance.
To formally check confidence for the aforementioned margin we provide

######  Theorem 7 (Confidence of Out-Performance).

Assume an annotator pool with agreement statistic $\mathcal{U}_{N}$ of (18),
and an agreement statistic between model and aggregated annotations
$\mathcal{L}_{N}$ of (25). If $\mathcal{L}_{N}>\mathcal{U}_{N}$ then for all
$\tau\geq 0$, $t_{u}\geq 0$ and $t_{l}\geq 0$ that satisfy

$\mathcal{L}_{N}-t_{l}-\sqrt{t_{u}+\mathcal{U}_{N}^{2}}=\tau,$ (28)

with probability at least $1-\delta_{u}-\delta_{l}$, the model oracle accuracy
exceeds that of the average annotator by $\tau$, i.e.

$\displaystyle\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})-\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\geq\tau,$
(29)

where

$\displaystyle\delta_{u}$ $\displaystyle=\exp\left(-2Nt_{u}^{2}\right),$ (30)
$\displaystyle\delta_{l}$ $\displaystyle=\exp\left(-2Nt_{l}^{2}\right).$ (31)

######  Proof.

Recall Theorem 5 and Theorem 6,

$\displaystyle\mathbb{P}\left(\sqrt{t_{u}+\mathcal{U}_{N}^{2}}\leq\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\right)$
$\displaystyle\leq\delta_{u}$
$\displaystyle\mathbb{P}\left(\mathcal{L}_{N}-t_{l}\geq\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})\right)$
$\displaystyle\leq\delta_{l}.$

Then, we have

$\displaystyle\mathbb{P}\left(\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})-\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\geq\tau\right)$
$\displaystyle=$
$\displaystyle\mathbb{P}\left(\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})-\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\geq\mathcal{L}_{N}-t_{l}-\sqrt{t_{u}+\mathcal{U}_{N}^{2}}\right)$
$\displaystyle\geq$
$\displaystyle\mathbb{P}\left(\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})\geq\mathcal{L}_{N}-t_{l}\cap\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\leq\sqrt{t_{u}+\mathcal{U}_{N}^{2}}\right)$
$\displaystyle=1-\mathbb{P}\left(\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})\leq\mathcal{L}_{N}-t_{l}\cup\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\geq\sqrt{t_{u}+\mathcal{U}_{N}^{2}}\right)$
$\displaystyle\geq$ $\displaystyle
1-\mathbb{P}\left(\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})\leq\mathcal{L}_{N}-t_{l})\right)-\mathbb{P}\left(\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})\geq\sqrt{t_{u}+\mathcal{U}_{N}^{2}}\right)$
$\displaystyle\geq$ $\displaystyle 1-\delta_{l}-\delta_{u}.$ (32)

#### Confidence Score Estimation.

The above theorem suggests the confidence score

$\displaystyle S=1-\delta_{l}-\delta_{u},$ (33)

and we need now only choose the free constants $t_{l},t_{u}$ and $\tau$, which
it depends on. Recall (28),

$\tau=\left(\mathcal{L}_{N}-t_{l}\right)-\sqrt{t_{u}+\mathcal{U}_{N}^{2}},$
(34)

and remove one degree of freedom parameterise in $t_{u}$ as

$t_{l}(t_{u},\tau)=\mathcal{L}_{N}-\tau-\sqrt{t_{u}+\mathcal{U}_{N}^{2}}.$
(35)

We are interested in $\mathbb{P}(\mathcal{L}-\mathcal{U}\geq 0)$ and so we may
set $\tau=0$. We offer two alternatives for selecting $t_{u}$ and $t_{l}$.

Algorithm 1 (Heuristic Margin Separation, HMS). We assign half of the margin
to $t_{u}$,

$t_{u}=\frac{\mathcal{L}_{N}-\mathcal{U}_{N}}{2}.$ (36)

Then, with $\tau=0$ we calculate the corresponding

$t_{l}=\mathcal{L}_{N}-\sqrt{\frac{\mathcal{L}_{N}-\mathcal{U}_{N}}{2}+\mathcal{U}_{N}^{2}},$
(37)

and compute the heuristic confidence score $S$.

Algorithm 2 (Optimal Margin Separation, OMS).
For an locally (in $t_{u}$) optimal confidence score, we perform gradient
ascent (Lemaréchal 2012) on $S(t_{u})$, where

$\displaystyle S(t_{u})=1-\delta(t_{u})-\delta(t_{l}(t_{u},0)),$ (38)

with $t_{u}$ is initialized as $(\mathcal{L}_{N}-\mathcal{U}_{N})/2$ before
optimization333For all OMS experiments, we set learning rate 1e-4, and iterate
100 times. We will publish our code upon acceptance..

##  4 Experiments and Discussion

Previously, we introduced a new theory for analyzing the oracle accuracy of
set of classifiers using observed agreements between them. In this section, we
demonstrate our theory on several classification tasks, to demonstrate the
utility of the theory and reliability of the associated assumptions.

###  4.1 Experimental Setup

We first consider two classification tasks with oracle labels generated by
rules. Given the oracle predictions, we are able to empirically validate the
assumptions for our theorems and observe the convergence of the bounds. Then,
we apply our theory on two real-world classification tasks and demonstrate
that some existing state-of-the-art models have potentially achieved better
performance than the (averaged) performance of the human annotators.

#### Classification tasks with oracle rules.

To validate the correctness of our theory, we collect datasets with observable
oracle labels. We construct two visual cognitive tasks, Color Classification
and Shape Classification, with explicit unambiguous rules to acquire oracle
labels, as follows:

  * •

Color Classification: the oracle selects the most frequently occuring color of
the objects in a given image.

  * •

Shape Classification: the oracle selects the most frequent occurring shape of
the objects in a given image.

For both tasks, the size of the objects is ignored. As illustrated in Figure
2, we vary three colors (Red, Blue and Yellow) and five shapes (Triangle,
Square, Pentagon, Hexagon and Circle) for the two tasks, respectively.

(a) Color

(b) Shape

Figure 2: Examples of a) Color Classification and b) Shape Classification.
Example a) includes 40 objects of three different colors, Red (14), Blue (15)
and Yellow (11), with Blue as the most frequent color and therefore the oracle
label. Example b) includes 37 objects of five different shapes, Triangle (9),
Square (10), Pentagon (7), Hexagon (6) and Circle (5), with Square the
dominant shape and oracle label.

For each task, we generated 100 images and recruited 10 annotators from the
Amazon Mechanical Turk444https://www.mturk.com to label them. Each randomly
generated example includes 20 to 40 objects. We enforce that no objects
overlap more than 70% with all others, and that there is only one class with
the highest count, to ensure uniqueness of the oracle label. The oracle number
of the colors and shapes are recorded to generate oracle labels of the
examples. More details about annotation interfaces and guidelines are provided
in Appendix B.

#### Real-World Classification Tasks.

We analyze the performance of human annotators and machine learning models on
two real-world NLP tasks, namely sentiment classification and natural language
inference (NLI). We use the Stanford Sentiment Treebank (SST) (Socher et al.
2013) for sentiment classification. The sentiment labels are mapped into two
classes (SST-2)555Samples with overall neutral scores are excluded as in (Tai,
Socher, and Manning 2015). or five classes (SST-5), very negative($[0,0.2]$),
negative ($(0.2,0.4]$), neutral($(0.4,0.6]$), positive ($(0.6,0.8]$), and very
negative ($(0.8,1.0]$). We use the Stanford Natural Language Inference (SNLI)
corpus (Bowman et al. 2015) for NLI. All samples are classified by five
annotators into three categories, i.e. Contradiction (C), Entailment (E), and
Neutral (N). More details of the datasets are reported in Table 1. In the
latter part of this section, we only report the estimated upper bounds on test
sets, as we intend to compare them with the performance of machine learning
models generally evaluated on test sets.

Dataset | #Test | #Class | #Annot.
---|---|---|---
SST-2 (Socher et al. 2013) | 1,821 | 2 | 3
SST-5 (Socher et al. 2013) | 2,210 | 5 | 3
SNLI (Bowman et al. 2015) | 10,000 | 3 | 5

Table 1: Statistics of SST and SNLI: the number of test samples, number of
classes, and the number of annotators.

(a) Color Classification (b) Shape Classification

Figure 3: Comparison of sample lower bound $\mathcal{L}_{N}$ for model oracle
accuracy $\mathbb{P}(\ell_{\mathcal{M}}=\ell_{\star})$. Relatively strong and
weak models are indicated by $\mathcal{M}^{(s)}$ and $\mathcal{M}^{(w)}$.
Another comparison of sample theoretical upper bound $\mathcal{U}_{N}^{(t)}$
and sample empirical upper bound $\mathcal{U}_{N}^{(e)}$ of average oracle
accuracy of annotators $\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})$.

#### Machine Learning Models.

For both of the classification tasks with known oracles, we treat them as
detection tasks and train YOLOv3 models (Redmon and Farhadi 2018) for them.
The input image resolution is 608 $\times$ 608 and we use the proposed
Darknet-53 as the backbone feature extractor. For comparison, we train two
models, a strong model and a weak model, on 512 and 128 randomly generated
examples, respectively. All models are trained for a maximum of 200 epochs
until convergence. During inference, the model detects the objects and we
count each type of object to obtain the prediction.

We compare several representative models and their variants for real-world
classification tasks, such as Recurrent Neural Networks (Chen, Ling, and Zhu
2018; Zhou et al. 2015), Tree-based Neural Networks (Mou et al. 2016; Tai,
Socher, and Manning 2015), and Pre-trained Transformers (Devlin et al. 2019;
Radford et al. 2018; Wang et al. 2020; Sun et al. 2020).

###  4.2 Results and Discussion

We now conduct several experiments to validate the convergence of the bounds
and the validity of the assumptions. We then demonstrate the utility of our
theory by detecting superhuman models. We organize the discussion into several
research questions (RQ).

#### RQ1: Will the bounds converge given more annotators?

We first analyze the lower bounds. We demonstrate lower bounds for strong
models (s) and weak models (w) in Figure 3 in black and blue lines
respectively. Generally, i) the lower bounds $\mathcal{L}_{N}$ are always
under the oracle accuracy of corresponding models; ii) the lower bounds grow
and tend to get closer to the bounded scores given more aggregated annotators.
Then, we analyze the upper bounds. We illustrate theoretical upper bound
$\mathcal{U}_{N}^{(t)}$ and empirically approximated upper bound
$\mathcal{U}_{N}^{(e)}$, in comparison with average oracle accuracy of
annotators $\mathbb{P}(\ell_{\mathcal{K}}=\ell_{\star})$, in Figure 3. We
observe that i) both upper bounds give higher estimation than the average
oracle accuracy of annotators; ii) the margin between $\mathcal{U}_{N}^{(t)}$
and $\mathcal{U}_{N}^{(e)}$ reduce, given more annotators incorporated; iii)
$\mathcal{U}_{N}^{(e)}$ generally provides a tighter bound than
$\mathcal{U}_{N}^{(t)}$, and we will use $\mathcal{U}_{N}^{(e)}$ as
$\mathcal{U}_{N}$ to calculate confidence score in later discussion.

#### RQ2: Are the assumptions of our theorems valid?

We verify the key assumptions for the upper bound of Theorem 1 and the lower
bound of Theorem 3 by computing the relevant quantities in Table 2. The two
assumptions hold in our experiments, although we can only perform this
analysis on the tasks with known oracle labels. For the assumptions required
for our lower bound, our experiment is more conservative than the assumption,
as we sum over all incorrect labels (see column 2 of Table 2.b). Despite the
stricter setting, our assumption still holds on both experiments.

Task | $\mathbb{P}(\ell_{i}=\ell_{\star}|\ell_{j}=\ell_{\star})$ | $\mathbb{P}(\ell_{i}=\ell_{\star})$
---|---|---
Color | 0.850 | 0.836
Shape | 0.586 | 0.542
(a) Theorem 1 assumes
$\mathbb{P}(\ell_{i}=\ell_{\star}|\ell_{j}=\ell_{\star})\geq\mathbb{P}(\ell_{i}=\ell_{\star})$,
$i\neq j$
Task $b$ | $\mathbb{P}(\ell_{b}=\ell_{\star}|\ell_{a}\neq\ell_{\star})$ | $\sum_{\ell_{\times}\neq\ell_{\star}}\mathbb{P}(\ell_{b}=\ell_{\times}|\ell_{a}\neq\ell_{\star})$
Color $\mathcal{M}^{(w)}$ | 1.000 | 0.000
Color $\mathcal{M}^{(s)}$ | 1.000 | 0.000
Shape $\mathcal{M}^{(w)}$ | 0.579 | 0.421
Shape $\mathcal{M}^{(s)}$ | 0.895 | 0.105
(b) Theorem 3 assumes
$\mathbb{P}(\ell_{b}=\ell_{\star}|\ell_{a}\neq\ell_{\star})\geq\mathbb{P}(\ell_{b}=\ell_{\times}|\ell_{a}\neq\ell_{\star})$

Table 2: Validating our assumptions for both upper bound Theorem 1 and lower
bound Theorem 3 on Color and Shape.

Disclaimer: while the assumptions appear reasonable, we recommend where
possible to obtain a small set of oracle labels to validate the assumptions in
future research.

|  SST 5-Class |  SST 2-Class |  SNLI 3-Class
---|---|---|---
B | Classifier | Score | Classifier | Score | Classifier | Score
$\mathcal{U}_{N}^{(t)}$ | Avg. Human | 0.790 ‡ | Avg. Human | 0.960 ‡ | Avg. Human | 0.904 ‡
$\mathcal{U}_{N}^{(e)}$ | Avg. Human | 0.660 † | Avg. Human | 0.939 † | Avg. Human | 0.879 †
|  CNN-LSTM (Zhou et al. 2015) | 0.492 |  CNN-LSTM (Zhou et al. 2015) | 0.878 |  BiLSTM (Chen, Ling, and Zhu 2018) | 0.855
$\mathcal{L}_{N}$ |  Constituency Tree-LSTM (Tai, Socher, and Manning 2015) | 0.510 |  Constituency Tree-LSTM (Tai, Socher, and Manning 2015) | 0.880 |  Tree-CNN (Mou et al. 2016) | 0.821
|  BERT-large (Devlin et al. 2019) | 0.555 |  BERT-large (Devlin et al. 2019) | 0.949† |  LM-Pretrained Transformer (Radford et al. 2018) | 0.899†
|  RoBERTa+Self-Explaining (Sun et al. 2020) | 0.591 |  StructBERT (Wang et al. 2020) | 0.971‡ |  SemBERT (Zhang et al. 2020) | 0.919‡

Table 3: The sample theoretical upper bounds and sample empirically
approximated upper bounds, $\mathcal{U}_{N}^{(t)}$ and
$\mathcal{U}_{N}^{(e)}$, of the average oracle accuracy of the human
annotators, and the sample lower bounds $\mathcal{L}_{N}$ of some
representative models on the SST and SNLI tasks. Those models with
$\mathcal{L}_{N}$ higher than $\mathcal{U}_{N}^{(e}$ or even
$\mathcal{U}_{N}^{(t)}$ are highlighted with $\dagger$ or $\ddagger$.

#### RQ3: How to identify a ‘powerful’, or even superhuman, classification
model?

We first compare the $\mathcal{L}_{N}$ with $\mathcal{U}_{N}$ in our toy
experiments, in Figure 3. Overall, it is more likely to observe superhuman
performance given more annotators. We observe that $\mathcal{L}_{N}^{(s)}$
outperforms both $\mathcal{U}_{N}^{(e)}$ and $\mathcal{U}_{N}^{(t)}$, given
more than 4 and 6 annotators for color classification and shape
classification, respectively. When the model is marginally outperforming
human, see weak model for color classification, we may not observe a clear
superhuman performance margin, $\mathcal{L}_{N}^{(s)}$ and
$\mathcal{U}_{N}^{(e)}$ are very close given more than 7 annotators.

For real-world classification tasks, we i) calculate the average annotator
upper bounds given multiple annotators’ labels and ii) collect model lower
bounds reported in previous literature. Some results on SST and SNLI are
reported in Table 3. We observe that pre-trained language models provide
significant performance improvement on those tasks. Our theory manages to
identify some of these models that potentially exceed the average human
annotator performance, by comparing $\mathcal{U}^{(e)}_{N}$ or the even more
restrictive $\mathcal{U}^{(t)}_{N}$.

#### RQ4: How confident are the certifications?

We calculate our confidence score for the identified outperforming models via
$\mathcal{U_{N}}$, $\mathcal{L_{N}}$, $N$, and using HMS and OMS, as reported
in Table 4. Generally, the confidence scores for SNLI models are higher than
those of SST-2 because the former has test set is more than five times larger,
while more recent and advanced models achieve higher confidence scores as they
have larger margin of $\mathcal{L}_{N}-\mathcal{U}_{N}$.

Model | Task | S(HMS) | S(OMS)
---|---|---|---
(Devlin et al. 2019) | SST-2 | $<0$ | $<0$
(Wang et al. 2020) | SST-2 | 0.4730 | 0.6208
(Radford et al. 2018) | SNLI | 0.8482 | 0.9267
(Zhang et al. 2020) | SNLI | 0.9997 | 0.9999
Table 4: Confidence score $S$ for the certificated models that outperform
human annotators in SST-2 and SNLI.

##  5 Conclusions

In this paper, we built a theory towards estimating the oracle accuracy of
classifiers. Our theory covers i) the upper bounds for the average performance
of human annotators, ii) lower bounds for machine learning models, and iii)
confidence scores which formally capture the degree of certainty to which we
may assert that a model outperforms human annotators. Our theory provides
formal guarantees even within the highly practically relevant realistic
setting of a finite data sample and no access to an oracle to serve as the
ground truth. Our experiments on synthetic classification tasks validate the
plausibility of the assumptions on which our theorems are built. Finally, our
meta analysis of existing progress succeeded in identifying some existing
state-of-the-art models have already achieved superhuman performance compared
to the average human annotator.

## Broader Impact

Our approach can identify classification models that outperform typical humans
in terms of classification accuracy. Such conclusions influence the
understanding of the current stage of research on classification, and
therefore potentially impact the strategies and policies of human-computer
collaboration and interaction. The questions we may help to answer include the
following: When should we prefer a model’s diagnosis over that of a medical
professional? In courts of law, should we leave sentencing to an algorithm
rather than a Judge? These questions and many more like them are too important
to ignore. Given recent progress in machine learning we believe the work is
overdue.

Yet we caution that estimating a model’s oracle accuracy in this way is not
free. Our approach requires the results from multiple annotators and
preferably also the number of annotators should be higher than the number of
possible classes in the target classification task. Another potential
challenge in applying our analysis is that some of our assumptions may not
hold under some specific tasks or settings. We recommend those who apply our
theory where possible to collect a small amount of ‘oracle’ annotations, to
validate the assumptions in this paper.

## References

  * Artstein (2017) Artstein, R. 2017.  Inter-annotator agreement.  In _Handbook of linguistic annotation_ , 297–313. Springer.
  * Berner et al. (2019) Berner, C.; Brockman, G.; Chan, B.; Cheung, V.; Debiak, P.; Dennison, C.; Farhi, D.; Fischer, Q.; Hashme, S.; Hesse, C.; et al. 2019.  Dota 2 with large scale deep reinforcement learning.  _arXiv preprint arXiv:1912.06680_.
  * Boucheron, Lugosi, and Massart (2013) Boucheron, S.; Lugosi, G.; and Massart, P. 2013.  _Concentration Inequalities: A Nonasymptotic Theory of Independence_.  OUP Oxford.  ISBN 9780191655500.
  * Bowman et al. (2015) Bowman, S.; Angeli, G.; Potts, C.; and Manning, C. D. 2015.  A large annotated corpus for learning natural language inference.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , 632–642.
  * Chen, Ling, and Zhu (2018) Chen, Q.; Ling, Z.-H.; and Zhu, X. 2018.  Enhancing Sentence Embedding with Generalized Pooling.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , 1815–1826.
  * Chicco and Jurman (2020) Chicco, D.; and Jurman, G. 2020.  The advantages of the Matthews correlation coefficient (MCC) over F1 score and accuracy in binary classification evaluation.  _BMC genomics_ , 21(1): 1–13.
  * Chowdhury (2010) Chowdhury, G. G. 2010.  _Introduction to modern information retrieval_.  Facet publishing.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , 4171–4186.
  * Fleiss (1971) Fleiss, J. L. 1971.  Measuring nominal scale agreement among many raters.  _Psychological bulletin_ , 76(5): 378.
  * Goldberg (1970) Goldberg, L. 1970.  Man versus model of man: A rationale, plus some evidence, for a method of improving on clinical inferences.  422–432.
  * Gwet (2010) Gwet, K. L. 2010.  Handbook of inter-rater reliability Advanced Analytics.  _LLC, Gaithersburg, MD_.
  * Han, Pei, and Kamber (2011) Han, J.; Pei, J.; and Kamber, M. 2011.  _Data mining: concepts and techniques_.  Elsevier.
  * Kahneman, Sibony, and Sunstein (2021) Kahneman, D.; Sibony, O.; and Sunstein, C. 2021.  _Noise: a Flaw in Human Judgment_.  William Collins.
  * Kittur, Chi, and Suh (2008) Kittur, A.; Chi, E. H.; and Suh, B. 2008.  Crowdsourcing user studies with Mechanical Turk.  In _Proceedings of the SIGCHI conference on human factors in computing systems_ , 453–456.
  * Kruger et al. (2014) Kruger, J.; Endriss, U.; Fernandez, R.; and Qing, C. 2014.  Axiomatic analysis of aggregation methods for collective annotation.  In _Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems_ , 1185–1192.
  * Lampert, Stumpf, and Gançarski (2016) Lampert, T. A.; Stumpf, A.; and Gançarski, P. 2016.  An empirical study into annotator agreement, ground truth estimation, and algorithm evaluation.  _IEEE Transactions on Image Processing_ , 25(6): 2557–2572.
  * Landis and Koch (1977) Landis, J. R.; and Koch, G. G. 1977.  The measurement of observer agreement for categorical data.  _biometrics_ , 159–174.
  * Lemaréchal (2012) Lemaréchal, C. 2012.  Cauchy and the gradient method.  _Doc Math Extra_ , 251(254): 10.
  * Lin et al. (2014) Lin, T.-Y.; Maire, M.; Belongie, S.; Hays, J.; Perona, P.; Ramanan, D.; Dollár, P.; and Zitnick, C. L. 2014.  Microsoft coco: Common objects in context.  In _European conference on computer vision_ , 740–755. Springer.
  * Mason and Suri (2012) Mason, W.; and Suri, S. 2012.  Conducting behavioral research on Amazon’s Mechanical Turk.  _Behavior research methods_ , 44(1): 1–23.
  * Matthews (1975) Matthews, B. W. 1975.  Comparison of the predicted and observed secondary structure of T4 phage lysozyme.  _Biochimica et Biophysica Acta (BBA)-Protein Structure_ , 405(2): 442–451.
  * Meehl (1954) Meehl, P. E. 1954.  Clinical versus statistical prediction: A theoretical analysis and a review of the evidence Minneapolis: University of Minnesota Press. [Reprinted with new Preface.  136–141.
  * Mou et al. (2016) Mou, L.; Men, R.; Li, G.; Xu, Y.; Zhang, L.; Yan, R.; and Jin, Z. 2016.  Natural Language Inference by Tree-Based Convolution and Heuristic Matching.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , 130–136.
  * Nowak and Rüger (2010) Nowak, S.; and Rüger, S. 2010.  How reliable are annotations via crowdsourcing: a study about inter-annotator agreement for multi-label image annotation.  In _Proceedings of the international conference on Multimedia information retrieval_ , 557–566.
  * Pontius Jr and Millones (2011) Pontius Jr, R. G.; and Millones, M. 2011.  Death to Kappa: birth of quantity disagreement and allocation disagreement for accuracy assessment.  _International Journal of Remote Sensing_ , 32(15): 4407–4429.
  * Radford et al. (2018) Radford, A.; Narasimhan, K.; Salimans, T.; and Sutskever, I. 2018.  Improving Language Understanding by Generative Pre-Training.
  * Redmon and Farhadi (2018) Redmon, J.; and Farhadi, A. 2018.  Yolov3: An incremental improvement.  _arXiv preprint arXiv:1804.02767_.
  * Sasaki et al. (2007) Sasaki, Y.; et al. 2007.  The truth of the f-measure. 2007.  _URL: https://www. cs. odu. edu/~ mukka/cs795sum09dm/Lecturenotes/Day3/F-measure-YS-26Oct07. pdf [accessed 2021-05-26]_.
  * Silver et al. (2016) Silver, D.; Huang, A.; Maddison, C. J.; Guez, A.; Sifre, L.; Van Den Driessche, G.; Schrittwieser, J.; Antonoglou, I.; Panneershelvam, V.; Lanctot, M.; et al. 2016.  Mastering the game of Go with deep neural networks and tree search.  _nature_ , 529(7587): 484–489.
  * Singh, Okun, and Jackson (2017) Singh, S.; Okun, A.; and Jackson, A. 2017.  Learning to play Go from scratch.  _Nature_ , 550(7676): 336–337.
  * Socher et al. (2013) Socher, R.; Perelygin, A.; Wu, J.; Chuang, J.; Manning, C. D.; Ng, A. Y.; and Potts, C. 2013.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Proceedings of the 2013 conference on empirical methods in natural language processing_ , 1631–1642.
  * Sun et al. (2020) Sun, Z.; Fan, C.; Han, Q.; Sun, X.; Meng, Y.; Wu, F.; and Li, J. 2020.  Self-Explaining Structures Improve NLP Models.
  * Tai, Socher, and Manning (2015) Tai, K. S.; Socher, R.; and Manning, C. D. 2015.  Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , 1556–1566.
  * Wang et al. (2019) Wang, A.; Pruksachatkun, Y.; Nangia, N.; Singh, A.; Michael, J.; Hill, F.; Levy, O.; and Bowman, S. R. 2019.  SuperGLUE: a stickier benchmark for general-purpose language understanding systems.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , 3266–3280.
  * Wang et al. (2018) Wang, A.; Singh, A.; Michael, J.; Hill, F.; Levy, O.; and Bowman, S. R. 2018.  GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding.  In _International Conference on Learning Representations_.
  * Wang et al. (2020) Wang, W.; Bi, B.; Yan, M.; Wu, C.; Xia, J.; Bao, Z.; Peng, L.; and Si, L. 2020.  StructBERT: Incorporating Language Structures into Pre-training for Deep Language Understanding.  In _International Conference on Learning Representations_.
  * Zhang et al. (2020) Zhang, Z.; Wu, Y.; Zhao, H.; Li, Z.; Zhang, S.; Zhou, X.; and Zhou, X. 2020.  Semantics-aware BERT for language understanding.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, 9628–9635.
  * Zhou et al. (2015) Zhou, C.; Sun, C.; Liu, Z.; and Lau, F. 2015.  A C-LSTM neural network for text classification.  _arXiv preprint arXiv:1511.08630_.

##  Appendix A Proof Details

#### Proof of Lemma 2

$\displaystyle\frac{\mathcal{U}}{\mathcal{U}^{(e)}}=$
$\displaystyle\sqrt{\frac{K-1}{K}\frac{\sum_{i=1}^{K}\sum_{j=1}^{K}\mathbb{P}(\ell_{i}=\ell_{j})}{\sum_{i=1}^{K}\sum_{\begin{subarray}{c}j=1\\\
i\neq j\end{subarray}}^{K}\mathbb{P}(\ell_{i}=\ell_{j})}}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{K-1}{K}}\sqrt{1+\frac{\sum_{i=1}^{K}\mathbb{P}(\ell_{i}=\ell_{i})}{\sum_{i=1}^{K}\sum_{\begin{subarray}{c}j=1\\\
i\neq j\end{subarray}}^{K}\mathbb{P}(\ell_{i}=\ell_{j})}}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{K-1}{K}}\sqrt{1+\frac{K}{\sum_{i=1}^{K}\sum_{\begin{subarray}{c}j=1\\\
i\neq j\end{subarray}}^{K}\mathbb{P}(\ell_{i}=\ell_{j})}}$ (39)

For the first factor in (39),

$\lim_{K\rightarrow+\infty}\sqrt{\frac{K-1}{K}}=1.$ (40)

For the second factor in (39), as both annotators address the same task, the
annotator agreement should be better than guessing uniformly at random, i.e.
$\mathbb{P}(\ell_{i}=\ell_{j})\geq 1/N_{c}$, where $N_{c}$ is the number of
classes. Then, we have

$0\leq\frac{K}{\sum_{i=1}^{K}\sum_{\begin{subarray}{c}j=1\\\ i\neq
j\end{subarray}}^{K}\mathbb{P}(\ell_{i}=\ell_{j})}\leq\frac{N_{c}}{K-1}.$

As $\lim_{K\rightarrow+\infty}\frac{N_{c}}{K-1}=0$,

$\lim_{K\rightarrow+\infty}\sqrt{1+\frac{K}{\sum_{i=1}^{K}\sum_{\begin{subarray}{c}j=1\\\
i\neq j\end{subarray}}^{K}\mathbb{P}(\ell_{i}=\ell_{j})}}=1.$ (41)

Combining (40) and (41), we have

$\lim_{K\rightarrow+\infty}\frac{\mathcal{U}}{\mathcal{U}^{(e)}}=1.$ (42)

##  Appendix B Details for Annotation

We crowd source the annotations via the Amazon Mechanical Turk. The annotation
interfaces with instructions for color classification and shape classification
are illustrated in Figure 4. Each example is annotated by $K=10$ different
annotators. For quality control, we i) offer our tasks only to experienced
annotators with 100 or more approved HITs; ii) automatically reject answers
from annotators who have selected ‘None of the above’.

(a) Color Classification

(b) Shape Classification

Figure 4: Human annotator interface for the Color Classification and Shape
Classification tasks.


# Guided Generation of Cause and Effect

Zhongyang Li1,2111Performed while the first author was visiting Johns Hopkins
University., Xiao Ding1, Ting Liu1, J. Edward Hu2 and Benjamin Van Durme2
1Harbin Institute of Technology, China
2Johns Hopkins University, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

We present a conditional text generation framework that posits sentential
expressions of possible causes and effects. This framework depends on two
novel resources we develop in the course of this work: a very large-scale
collection of English sentences expressing causal patterns (CausalBank); and a
refinement over previous work on constructing large lexical causal knowledge
graphs (Cause Effect Graph). Further, we extend prior work in lexically-
constrained decoding to support _disjunctive_ positive constraints. Human
assessment confirms that our approach gives high-quality and diverse outputs.
Finally, we use CausalBank to perform continued training of an encoder
supporting a recent state-of-the-art model for causal reasoning, leading to a
3-point improvement on the COPA challenge set, with no change in model
architecture.

##  1 Introduction

Causal knowledge acquisition is crucial for various Artificial Intelligence
tasks, such as causal event graph construction, reading comprehension and
future event prediction. We propose an approach for acquiring causal knowledge
through generating multiple plausible causes (reasons, explanations) and
effects (results, consequences) for a provided input sentence. As exemplified
in Figure 1, we develop two conditional decoders, one per causal direction. To
train such models we mine a large-scale corpus of causal expressions from open
domain web text, at a scale greatly surpassing prior work. Our goal is to
generate multiple _distinct_ possible causes and effects, where each generated
sentence is not intended to be a paraphrase of other candidates. To support
this output diversity when conditioned on a single shared input sentence, we
turn to lexically-constrained decoding Post and Vilar (2018); Hu et al.
(2019a), which allows for efficiently forcing a model to produce output
containing one or more provided phrases. Our constraints are derived from a
resource we construct for this work, replicating a prior effort in lexicalized
causal knowledge graph construction Luo et al. (2016). This graph captures
causal relations as a mapping across lexical types, lemma-to-lemma, but our
goal is to generate naturalistic sentences with appropriately inflected
morphology: we therefore develop an approach for _disjunctive_ positive
lexical constraints, where a decoder’s output must contain one of a set of
provided words or phrases. In our case, these are morphological variants of
the same base lemma, but our approach should benefit other applications of
lexically-constrained decoding.

While there is recent work in generating story endings conditioned on a
context Guan et al. (2019); Wang and Wan (2019); Luo et al. (2019), such work
does not require generated sentences to be strictly causes or effects. The
ability to propose _explanations_ for an input sentence by generating multiple
causes and effects complements this emerging line of research. To our
knowledge, this is the first work to consider open-ended generation of _causal
sentences_ at a large scale.

We evaluate through carefully designed human evaluation by comparing outputs
from various baselines and our proposed model, finding that our model’s
outputs are preferred. We further demonstrate the usefulness of our new
resource by taking a recent state-of-the-art causal reasoning system and
boosting its results on the COPA test set by 3 points, relying only on
continued training of the model’s encoder. Our models and resources are made
publicly available.222http://nlp.jhu.edu/causalbank

Figure 1: Possible causes and effects generated by our model, conditioned on
the input sentence “babies cry”. Tokens in blue are constraint keywords
derived from our Cause Effect Graph, which are forced to be included in the
outputs by constrained decoding. Figure 2: Our approach for generating
plausible causes and effects.

In this paper, we make the following contributions:

  * •

proposing the task of open causal generation: producing possible causes and
effects for any free-form textual event;

  * •

construction of a causal corpus (CausalBank) containing 314 million CE (cause-
effect) pairs;

  * •

an extension to lexically-constrained decoding that supports disjunctive
positive constraints (DPC);

  * •

human and automatic evaluations illustrating our method can generate high-
quality and diverse causes and effects.

##  2 Approach

As shown in Figure 2, our proposed approach for open-ended causal generation
includes a data collection module (Section 2.1), a Cause Effect Graph (Section
2.2), and two DPC (disjunctive positive constraint) decoding based Transformer
encoder-decoder models (Section 2.3).

###  2.1 CausalBank: A Sentential Causal Corpus

Existing causal corpora were not built to support our goal for open-ended
causal generation given any free-form textual input: as in neural machine
translation (NMT), we need a large training set with millions of examples.
Thus we harvest a large causal dataset from the preprocessed large-scale
English Common Crawl corpus (5.14 TB) Buck et al. (2014). The key guidelines
of our dataset are as follows: 1) The causal relation is explicitly expressed
in text with a causal pattern e.g. ‘because’; 2) The ‘cause’ and ‘effect’
arguments must both appear in the same sentence; 3) The ‘cause’ and ‘effect’
arguments can be of any length of contiguous text without overlaps between
them; 4) Negative causal relations are filtered.

Causal Pattern
---
as, as a consequence/result of, as long as, because,
because of, caused by, due/owing to, in response to,
on account of, result from
accordingly, consequently, bring on/about, give rise to,
induce, in order to, lead to, result in, prevent/stop…from,
and for this reason, cause, for the purpose of, if…then,
,_so, so that, thereby, therefore, thus, hence
Table 1: Causal patterns (their morphological variants are ignored) used to
get the CausalBank corpus. The first row of patterns belong to the EPC
category, while the second row belong to the CPE category.

We do not rely on a supervised text extractor to pick out specific sub-spans
of a sentence that represent a cause-effect pairing between propositions.333We
found poor annotator agreement on span boundaries in an initial investigation
on crowdsourcing data for such a system; we intend to return to this in future
work, investigating improvements to our results via trained extraction models
for corpus pre-processing. We instead curate a series of patterns from
previous studies Mirza et al. (2014); Luo et al. (2016); Girju (2003). These
patterns can be classified into two categories, according to how they are
mostly used in language to convey a causal relation: 1. EPC (effect-pattern-
cause) category: I am very sad because I lost my phone; 2. CPE (cause-pattern-
effect) category: The earthquake resulted in many deaths. For EPC patterns, we
simply take the text on the left of the pattern as effect, and take the text
on the right of the pattern as cause. The case is reversed for CPE category
patterns. These patterns (shown in Table 1) were applied to the Common Crawl
corpus, followed by post-filtering: duplicate removal; filtering explicitly
negated relations and verbs in passive voice; and restricting the cause and
effect to each contain at least two tokens. This results in our CausalBank
corpus, denoted here as $\mathcal{B}$, with 133 M EPC + 181 M CPE = 314 M
$(c,e)$ ($c$ refers to cause and $e$ refers to effect) pairs in total. We
manually evaluated 1,000 randomly sampled sentences from the corpus and found
that 95% conveyed a meaningful causal relation.

###  2.2 Cause Effect Graph: A Lexical Causal KB

Figure 3: Cause Effect Graph: A lexical causal knowledge base.

Following the method described in Luo et al. Luo et al. (2016) for creating a
causal lexical knowledge base, we reproduce a variant of their CausalNet using
the Common Crawl corpus Buck et al. (2014). Given a sentence such as _“The
storm caused a tremendous amount of damage on the landing beaches.”_, this
approach will harvest the lexical pairs (_storm_ , _tremendous_), (_storm_ ,
_amount_), (_storm_ , _damage_), (_storm_ , _landing_), and (_storm_ ,
_beach_) as causal evidence. Stop words are removed and only pairs involving
nouns, verbs, adjectives and adverbs are retained. The extracted lexical pairs
form a directed network of posited causal relations, where nodes in the
network are lemmatized terms, and a directed edge between two terms indicates
a causal relation, weighted by co-occurrence frequency. For comparison, Figure
3 gives a similar illustration as Figure 1 in Luo et al. Luo et al. (2016). We
refer to our artifact as a Cause Effect Graph (CEG); Table 5 illustrates CEG
contains more causal relations than CausalNet,44489.1M in contrast to 13.3M,
with relations with a frequency of 5 or lower removed. owing to the larger
(5.14TB) and cleaner corpus used for extraction Buck et al. (2014).

###  2.3 Guided Generation

We use Sockeye Hieber et al. (2017) to train Transformer-based Vaswani et al.
(2017) conditional generation models, one for causes, one for effects. Sockeye
supports decoding via N-best (each step greedily chooses the top best N words
in beam search based on the generated tokens) and random sampling (each step
randomly sampling N words from the softmax distribution based on the generated
tokens). The training data (CausalBank) is processed through Byte Pair
Encoding Sennrich et al. (2016) to reduce vocabulary size.

####  2.3.1 Disjunctive Positive Constraints Decoding

Unlike in NMT, our intended outputs for a given input are diverse in meaning:
we wish to generate multiple _semantically distinct_ possible causes or
effects. We induce diversity through hard lexical requirements during
decoding, using causal keywords from our CEG as positive constraints on the
output. A positive constraint forces the decoder to produce a sequence of
tokens that contain the constrained sequence, which is achieved through a
constrained beam search proposed by Post and Vilar Post and Vilar (2018) and
made efficient by Hu et al. Hu et al. (2019a).

Unfortunately, those prior works are restricted to _conjunctive_ positive
constraints: all items provided to the decoder _must_ be present in the
output. This is problematic in our case: our CEG maps lemmas to lemmas, and
thus lemmas will form our constraints, but at generation time we do not
require specific morphological inflections of our constrained terms. We wish
not to constrain the decoder to a particular lemma, but to allow it to choose
the best morphological form as appropriate in its context. For example, when
generating a cause for _“I brought an umbrella”_ with rain as the cause
keyword, some valid cause sentences, e.g., _“It rained”_ or _“It was a rainy
day.”_ , would not be permitted based on prior work. One may circumvent this
limitation by enumerating all morphological variants of a term, then apply
each in turn as a positive constraint in distinct decoding passes. However,
this approach does not scale, as its run-time grows exponentially in the
number of initial constraints, each with multiple morphological variants.

Here we propose a solution of _disjunctive_ positive constraint decoding,
where each constraint is represented by a set of token sequences, and the
decoder needs to include only one sequence from each set of constraints in the
final output. We modify the algorithm from Hu et al. Hu et al. (2019a) to
allow the decoder to explore the disjunctively constrained space in a single
forward sequence, without significant computational overhead. In that work,
constraints are represented in a trie, where each constraint is represented by
a path from the root to a leaf. One or more state pointers are used to track
how many tokens have been generated for each constraint, and tokens that
induce more progress are prioritized in a modified beam search proposed by
Post and Vilar Post and Vilar (2018). When a constraint is satisfied, the
algorithm prunes the path representing that constraint. The distinguishing
property of a disjunctive constraint is that once a sequence in a disjunctive
set is satisfied, others in the set are also removed and no longer
constraints.

For decoding with disjunctive constraints, we represent all constrained
sequences, whether they are from the same disjunctive set or not, on a single
trie. When a sequence is generated, we prune all sequences in the set as
opposed to just the generated sequence. This modification gives us an
efficient algorithm for applying disjunctive constraints, as illustrated in
Algorithm 1 and Figure 4. While here we use morphological variants in our
disjunctive set, our algorithm is broadly applicable for constraining on a set
of synonyms or different subword segmentations of the same sequence.

Algorithm 1 Decoding with Disjunctive Positive Constraints. We consider the
generation of one sentence with a beam size of $1$ for simplicity. Note that
while a beam size of $1$ reduces the constrained beam search, the handling of
DPC is not affected.

input: a set of disjunctive constraint sets $t$, for each set $s$ in $t$,
$s_{i}=\\{s_{i}^{0},s_{i}^{1},...,s_{i}^{n}\\}$ and
$s_{i}^{n}=(w_{i}^{(n)(0)},w_{i}^{(n)(1)},...,w_{i}^{(n)(m)})$ where
$w_{i}^{(n)(m)}$ is the $m^{th}$ token in $s_{i}^{n}$, one of the sequences of
the disjunctive constraint set $s_{i}$

output: a token sequence $o=(o_{0},o_{1},...,o_{k})$

$trie\coloneqq BuildTrie(\\{s_{0}^{0},...,s_{i}^{n}\\})$

while $o_{k-1}!=$EOS and $k<k_{max}$ do

$o_{k}\coloneqq ConstrainedBeamSearch((o_{0},...,o_{k-1}),t)$

if $o_{k}$ finishes the sequence $s_{p}^{q}$ then

for $s_{p}^{i}$ in $s_{p}$ do

$trie\coloneqq trie.prune(s_{p}^{i})$

end for

Remove $s_{p}$ from $t$

end if

$k\coloneqq k+1$

end while

return $(o_{0},o_{1},...,o_{k})$

Figure 4: Trie states in positive constraint and disjunctive positive
constraint, after generating the token ‘rained’ in beam search.

##### Outputs Reranking

While DPC decoding supports arbitrary number of disjunctive constraints in one
beam search process, in practice only a few preferred constraints under the
model will dominate any N-best output. To encourage diversity we first select
a set of candidate constraint tokens from CEG, generate outputs per
constraint, then merge and rerank the results. For example, if generating
causes for the input sentence $i=$ _“babies cry”_ , we lemmatize each word in
the sentence (_baby_ and _cry_). These terms map to a set of lemmas via CEG,
each associated with an observed frequency; we take the $N$-most frequent
(highest weighted) such candidates: $t=\\{w_{1},w_{2}...w_{N}\\}$. For each
token $w_{i}$ in $t$, such as _‘love’_ , we get a set of its morphological
variants $s_{i}=${_‘love’, ‘loves’, ‘loved’, ‘loving’_} via the python package
patterns.en, and pass $s_{i}$ as a DPC, keeping the top $M$ outputs. In total
we derive $N*M$ ($N$=300 and $M$=5) sentences via $N$ beam search decodings.
These sentences are ranked by their associated negative log-likelihood scores,
and we return the top $K$.

Method | Dataset | Cause | Effect
---|---|---|---
Per | Acc | Per | Acc
RNN-LSTM | CB_10M | 66.0 | 29.6 | 55.2 | 32.2
RNN-GRU | CB_10M | 67.6 | 29.5 | 48.0 | 33.7
CNN | CB_10M | 37.6 | 36.1 | 39.5 | 35.4
Conv-Transformer | CB_10M | 29.5 | 38.9 | 31.1 | 38.2
Transformer | CB_10M | 28.3 | 39.1 | 29.9 | 38.4
Transformer | CB_all | 31.4 | 38.0 | 27.6 | 39.7
Transformer_BIG | CB_all | 29.9 | 38.5 | 26.4 | 39.8
Table 2: Dev-set results: perplexity (Per), word accuracy (Acc (%)).

##  3 CausalBERT

Previous studies Phang et al. (2018); Li et al. (2019b) have shown that
applying intermediate auxiliary task training to an encoder such as BERT can
improve performance on a target task. We designed an intermediate task for
BERT using CausalBank $\mathcal{B}$, employing margin loss Li et al. (2019a,
2018a) in the objective function:
$L(\Theta)=\sum_{(c,e)\in\mathcal{B}}(\max(0,m-f(c,e)+f(c^{\prime},e^{\prime})))+\frac{\lambda}{2}||\Theta||^{2}$,
where $f(c,e)$ is the score of true CE pair given by BERT model,
$f(c^{\prime},e^{\prime})$ is the score of corrupted CE pair by replacing $c$
or $e$ with randomly sampled negative cause $c^{\prime}$ or effect
$e^{\prime}$ from other examples in $\mathcal{B}$. $m>0$ is the margin loss
function parameter, which is set to 0.3. $\Theta$ is the set of BERT model
parameters. $\lambda$ is the parameter for L2 regularization, which is set to
0.00001.

By training BERT with this intermediate supervised task, we expect the model
to acquire enhanced knowledge about the meaning of a causal relation, and can
have better performance on downstream causal inference tasks.

##  4 Evaluation

We evaluate our proposed causal generation approach by both human and
automatic metrics, and evaluate CausalBank by applying CausalBERT to COPA,
which requires the model to choose the correct cause or effect from two
candidates.

####  4.0.1 Model Selection

We first experiment on a small subset of our CausalBank corpus (CB_10M) – 10
million CE pairs from the causal pattern ‘because’ – considering different NMT
encoder and decoder architectures (LSTM, CNN, Conv-Transformer Gehring et al.
(2017), and Transformer).555Each of these models’ encoder and decoder use the
same architecture, e.g. both are 6-layer LSTMs, with a hidden size and
embedding size of 512. All models are trained for 10 epochs. The vocabulary
size is 10,000. For the cause generation model, $e$ is used as the source and
$c$ is used as the target, which is reversed in training the effect model.
Perplexity (Per) and word accuracy (Acc) are used to evaluate the model’s
performance. We find that Transformer constantly achieves the best performance
(Table 2).

| Method | Cause | Effect
---|---|---|---
P@1 | P@3 | H | Div | P@1 | P@3 | H | Div
TrainSub | KNN | 89.0 | 67.3 | 0.85 | 0.11 | 98.0 | 71.3 | 0.90 | 0.02
GPT-2 | 31.0 | 22.3 | 0.39 | 0.13 | 8.0 | 9.3 | 0.30 | 0.11
N-Best | 59.0 | 45.3 | 0.53 | 0.15 | 63.0 | 42.7 | 0.53 | 0.11
Random | 68.0 | 59.3 | 0.66 | 0.11 | 74.0 | 61.7 | 0.70 | 0.09
CN-Cons | 72.0 | 71.3 | 0.79 | 0.02 | 66.0 | 67.0 | 0.76 | 0.02
Gold-Cons | 78.0 | 75.3 | 0.83 | 0.12 | 71.0 | 73.0 | 0.80 | 0.10
COPA_Dev | KNN | 10.0 | 8.0 | 0.53 | 0.10 | 4.0 | 2.7 | 0.26 | 0.01
GPT-2 | 40.0 | 34.0 | 0.45 | 0.12 | 38.0 | 32.0 | 0.46 | 0.10
Random | 66.0 | 53.7 | 0.65 | 0.09 | 62.0 | 46.7 | 0.57 | 0.08
N-Best | 69.0 | 65.0 | 0.77 | 0.08 | 72.0 | 68.0 | 0.82 | 0.07
CN-Cons | 74.0 | 70.0 | 0.81 | 0.02 | 72.0 | 72.0 | 0.87 | 0.02
Gold-Cons | 73.0 | 73.0 | 0.87 | 0.09 | 72.0 | 71.3 | 0.87 | 0.09
Table 3: Human evaluation results of cause and effect generation.

Then we train two versions of Transformer on the whole CausalBank corpus
(CB_all). The small model’s encoder and decoder both have 6 layers, with a
hidden size and embedding size of 512. The big model’s encoder and decoder
have 12 layers and 4 layers, with a hidden size and embedding size of 768,
leading to 134M parameters in total. The vocabulary size is 15,000. The
training is stopped when the validation loss stagnates for 20,000 batches. For
the cause generation model, $e$ and $c$ from only the EPC category $(c,e)$
pairs are used as the source and target. For the effect generation model, $c$
and $e$ from only the CPE category $(c,e)$ pair is used as the source and
target. This setting always generates the right part of the sentence
conditioned on the left part, which we find to give more reasonable outputs
than the above architecture exploration experiments. The bottom of Table 2
shows the large Transformer model constantly achieves the best performance on
development set, which contains 5,000 CE pairs.

####  4.0.2 Evaluating Generation

We evaluate the large Transformer model via human assessment, on two kinds of
test sets. The first kind of test sets (TrainSub) contains 100 randomly
sampled input examples from the model’s training data. The second kind of test
sets (COPA_Dev) contains 100 randomly sampled examples from the development
set of COPA Roemmele et al. (2011) dataset, which are manually created gold
sentences and never seen during the model’s training stage.

The compared methods include a simplified KNN method (when the input is
“babies cry”, we match sentences exactly containing the input as the retrieved
neighbors, e.g. “those babies cry loudly”, and get the corresponding causes
and effects), the GPT-2 124M language model Radford et al. (2019) which can
generate continuations conditioned on a start sentence (e.g. “babies cry
because”), random sampling based decoding, N-best decoding, DPC decoding with
constraint tokens from CEG (CN-cons), and DPC decoding with gold answer as
constraint tokens (Gold-cons).

Method | Acc (%)
---|---
PMI Jabeen et al. (2014) | 58.8
PMI_EX Gordon et al. (2011) | 65.4
CS Luo et al. (2016) | 70.2
CS_MWP Sasaki et al. (2017) | 71.2
Google T5-base Raffel et al. (2019) | 71.2
BERT-base Li et al. (2019a) | 75.4
CausalBERT-base (ours) | 78.6
Google T5-11B Raffel et al. (2019) | 94.8
Table 4: Results on COPA-Test, contrasting prior results to a model by Li _et
al._ built atop BERT-base. This model is improved by 3 points through adoption
of CausalBERT.

Four graduate students from the NLP field were used in annotation. Each was
asked to give a score from $\\{0,1,2\\}$ for the generated {input,
cause/effect} pair, where the guidelines are (take cause generation for
example): if the generated answer does not make sense or can never be a
reasonable cause, reason or explanation for the input event, give a score of
0; if the generated answer has grammatical errors but can be a reasonable
cause, reason or explanation for the input event under some rare conditions
(or beyond commonsense), give a score of 1; if the generated answer is a
fluent sentence and can be a reasonable cause, reason or explanation with high
probability, give a score of 2. Each pair was labeled by two annotators, and
we average the judgments over two annotators per pair. The cohen’s kappa score
is 0.53.

Table 3 shows the human evaluation results. Three metrics are adopted:
Precision at 1 P@1 (an average score of 1.5 or above is seen as a valid causal
answer); P@3; and average human score for each evaluated pair (H). For the
TrainSub test set, the KNN method shows strong performance, especially for P@1
and the human scores. However, KNN performs worse for P@3, due to the absence
of many possible answers for the same input. Meanwhile, our two versions of
DPC decoding strategies (CN-cons, Gold-Cons) also show relatively better
performance compared to other generation methods (GPT-2, Random and N-best
decoding). KNN performs poorly on the COPA dev set, because most of the inputs
never appear in the training data. However, CN-Cons and Gold-Cons can still
achieve good performance.

##### Lexical Diversity

We used a modified BLEU score to evaluate lexical diversity (Div in Table 3)
where a lower score means a greater lexical diversity. Specifically, we
calculate the associated BLEU-1 score between the gold answers and the
generated top 3 outputs without brevity penalty. This modification ensures
that we don’t reward shorter outputs. In most cases, CN-Cons gets the lowest
Div scores, showing that our DPC decoding and constraint tokens from CEG
together, allows us to explore more in the causes and effects space, and
generate more diverse outputs. Also we find that all of these BLEU scores are
very low, compared with the BLEU scores in previous text generation studies Hu
et al. (2019b); Vaswani et al. (2017). This is because our generation task is
open-ended (as illustrated in Figure 1).

##### Evaluating CausalBank

Table 4 shows our CausalBERT results on COPA test. Compared with prior strong
knowledge-driven baseline methods, a BERT-base model trained with a margin-
based loss Li et al. (2019a) achieved good performance. Following the
experimental settings of Li et al. Li et al. (2019a), when training the BERT-
base model with additional CE pairs from CausalBank, we get an improvement of
3.2%, from 75.4% to 78.6%, showing that our corpus successfully augments BERT
base to make it better for causal inference, which is a sign the corpus
contains useful causal knowledge. We find that the number of CE pairs in the
intermediate task matters: performance first improves and then decreases, with
more training data added. 666This was not observed in related studies Phang et
al. (2018); Li et al. (2019b), where all training examples from the Multi-NLI
dataset were used as an intermediate task. Similar behavior was observed in
NMT in continued training for domain adaptation Thompson et al. (2019). We
believe ours to be a similar setting, where the “in-domain” causal data
overwhelms the benefits of pretraining; adapting strategies from Thompson _et
al._ is an avenue for future work. We get the best performance of 78.6% with
40 K training CE pairs. Though our result still has a big gap from the current
SOTA performance on COPA (94.8% from the largest google T5-11B model), the
intent of our experiment is just to illustrate how the only difference was in
altering the pre-training with CausalBank. One could possibly get a SOTA model
based on our corpus and the google T5 model, if publicly available.

##  5 Related Work

##### Conditional Text Generation

Such efforts cover a large body of work, including machine translation,
response generation and paraphrase generation. Most related is conditional
story generation Guan et al. (2019); Wang and Wan (2019); Luo et al. (2019);
Li et al. (2018b), which aims to generate story continuations based on a given
context. These works do not require generated sentences to be strictly causes
or effects.

For causal generation, Rashkin et al. Rashkin et al. (2018) aimed to generate
the likely intents and reactions of the event’s participants, given a short
free-form textual event. Sap et al. Sap et al. (2019) trained a multi-task
model for fine-grained kinds of If-Then commonsense reasoning. However, the
causal semantics considered in their work are restricted to a narrow space,
and their models are trained on no more than one million examples. Further,
their resource was based-on crowdsourcing, which carries risks of human bias
Rudinger et al. (2017); Poliak et al. (2018). We harvest a significantly
larger, open coverage causal corpus,777While we avoid pitfalls of elicitation,
we acknowledge that like any corpus-extracted resource ours may suffer from
_reporting bias_ Gordon and Van Durme (2013): some types of causes or effects
that are known to humans but rarely or ever explicitly stated. related in
approach to DisSent Nie et al. (2019) but larger, focused on causality, and
aimed primarily at generation rather than sentence representation learning.

Of various efforts in guided generation Ammanabrolu et al. (2019); Tang et al.
(2019); Clark et al. (2018); Hu et al. (2019b), lexically-constrained decoding
Hokamp and Liu (2017) is a modification of beam search originating in neural
machine translation which allows the user to specify tokens that must (or must
not) appear in the decoder’s output.

Post and Vilar Post and Vilar (2018) proposed a variant of lexically-
constrained decoding that reduced complexity from linear to constant-time,
which was made more efficient by Hu et al. Hu et al. (2019a). We introduce an
extension to lexically-constrained decoding that supports disjunctive positive
constraints for multiple optional constraint keywords.

Sentential Causal Resource | # CE Pairs
---|---
TCR Ning et al. (2018) | 172
SemEval-2007 Task4 Girju et al. (2007) | 220
Causal-TimeBank Mirza et al. (2014) | 318
CaTeRS Mostafazadeh et al. (2016) | 488
EventCausalityData Do et al. (2011) | 580
RED O’Gorman et al. (2016) | 1,147
SemEval2010 Task8 Hendrickx et al. (2009) | 1,331
BECauSE 2.0 Dunietz et al. (2017b) | 1,803
EventStoryLine Caselli and Vossen (2017) | 5,519
PDTB 2.0 Prasad et al. (2008) | 8,042
Altlex Hidey and McKeown (2016) | 9,190
PDTB 3.0 Webber et al. (2019) | 13 K
DisSent Nie et al. (2019) | 167 K
CausalBank (Ours) | 314 M
Causal Knowledge Graph | # CE Edges
Event2mind Rashkin et al. (2018) | 25 K
ConceptNet 5.7 Speer et al. (2017) | 473 K
ASER Core Zhang et al. (2019) | 494 K
Atomic Sap et al. (2019) | 877 K
CausalNet Luo et al. (2016) | 13.3 M
Cause Effect Graph (Ours) | 89.1 M
Table 5: Contrasting size with example prior works: only the causal portion of
these corpora are listed. The top are sentential causal corpora, while the
bottom are graph-structure causal knowledge bases.

##### Sentential Causal Resources

Existing causal corpora differ in their annotation guidelines and how they are
constructed: (1) whether they consider only explicit or also implicit causal
relations; (2) whether they consider only intra-sentence relations or if
relations can cross sentences; (3) whether the annotation unit is word level
or sentence level; and (4) whether the corpus is constructed automatically or
by human effort. Ours is concerned with explicit only relations, within a
single sentence, relating one part of a sentence to another, and employs
constructed patterns but not sentence-level human annotation.

Already mentioned are recent crowdsourcing efforts Rashkin et al. (2018); Sap
et al. (2019). More related are PDTB Prasad et al. (2008) and BECauSE Dunietz
et al. (2017b), but where our resource goal is a much larger corpus, for the
purpose of training a neural text generation model. Most related would be the
extractive approach of DisSent Nie et al. (2019), but where we focus
specifically on causality, and derive a much larger corpus. Bethard and Martin
(2008) tagged a small corpus of event pairs conjoined with “and” as causal or
not causal. CaTeRS Mostafazadeh et al. (2016) included causal relations from a
commonsense reasoning standpoint. Richer Event Description O’Gorman et al.
(2016) integrates real-world temporal and causal relations between events into
a unified framework. Table 5 contrasts the size of causal portion of prior
resources with our own.

##### Lexical Causal Resources

Lexical semantic resources may encode causal properties on verbs (e.g.,
Schuler (2005); Bonial et al. (2014)) and prepositions (e.g., Schneider et al.
(2015)). Force dynamics theory Talmy (1988) from cognitive psychology posits
three primary kinds of causal semantics Wolff (2007) – CAUSE, ENABLE and
PREVENT – which were lexicalized as causal verbs Wolff and Song (2003). The
annotation scheme of Dunietz et al. Dunietz et al. (2017b) distinguishes three
types of causal semantics: CONSEQUENCE, MOTIVATION, and PURPOSE. In PDTB 2.0
Prasad et al. (2008), “CONTINGENCY” has two subtypes (“Cause” and
“Condition”). FrameNet Baker (2014) represents causal relations through a
variety of unrelated frames (e.g., CAUSATION and THWARTING) and frame roles
(e.g., PURPOSE and EXPLANATION). These efforts motivate our own causal
patterns, categorized into: CAUSE (e.g. cause, result in, lead to),
EXPLANATION (e.g. because, due to), CONDITION (e.g. if-then, as long as),
PURPOSE (e.g. in order to, for the purpose of), and PREVENTION (e.g.
stop/prevent-from).

##### Causal Knowledge Acquisition

Causal knowledge acquisition Radinsky et al. (2012); Radinsky and Horvitz
(2013) is crucial for many AI systems, and it is often acquired via text.
Hashimoto et al. Hashimoto et al. (2014) and Kruengkrai et al. Kruengkrai et
al. (2017) applied supervised learning techniques using a benchmark training
data with over 100K human-annotated CE pairs. Dasgupta et al. Dasgupta et al.
(2018) explored general causal extraction using 5,000 labelled sentences. Do
et al. Do et al. (2011) is an example of a minimally supervised approach.
Recent studies Dunietz et al. (2017a, 2018) explored new supervised approaches
on the BECauSE 2.0 Dunietz et al. (2017b) corpus.

Church and Hanks Church and Hanks (1990) proposed the use of pointwise mutual
information (PMI) for mining patterns via text co-occurrence. Many works have
followed this strategy, e.g. Chambers and Jurafsky (2008); Riaz and Girju
(2010); Gordon et al. (2011); Do et al. (2011); Luo et al. (2016). Others have
mined patterns via discourse patterns in the form of ‘A led to B’, ‘if A then
B’, etc., e.g., Khoo et al. (2000); Girju (2003); Zhao et al. (2017)). See
Asghar Asghar (2016) for review. Such efforts relate most closely to our
CEGraph component, rather than our overall framework. Our concern is the
generation of diverse potential causes and effects as natural language
statemnts.

##  6 Conclusion

We investigate open causal generation for free-form textual input, and build a
large sentential causal corpus which we used to train a generative model. We
introduced a novel extension to lexically-constrained decoding that supports
disjunctive positive constraints, where generated output is forced to contain
one of a set of candidates. Automatic and human evaluations show that our
method can generate high-quality and diverse causes and effects for new
inputs.

## Acknowledgements

We acknowledge the support of the National Key Research and Development
Program of China (SQ2018AAA0101901), the National Natural Science Foundation
of China (NSFC) via Grant 61976073 and 61702137; the China Scholarship
Council; and DARPA KAIROS (Hu and Van Durme).

## References

  * Ammanabrolu et al. [2019] P. Ammanabrolu, E. Tien, W. Cheung, Z. Luo, W. Ma, L. Martin, and M. Riedl.  Guided neural language generation for automated storytelling.  In Storytelling Workshop, 2019.
  * Asghar [2016] N. Asghar.  Automatic extraction of causal relations from natural language texts: a comprehensive survey.  arXiv preprint arXiv:1605.07895, 2016.
  * Baker [2014] C. Baker.  Framenet: a knowledge base for natural language processing.  In Frame Semantics, 2014.
  * Bethard and Martin [2008] Steven Bethard and James H Martin.  Learning semantic links from a corpus of parallel temporal and causal relations.  In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics on Human Language Technologies: Short Papers, pages 177–180. Association for Computational Linguistics, 2008.
  * Bonial et al. [2014] C. Bonial, J. Bonn, K. Conger, J. D Hwang, and M. Palmer.  Propbank: Semantics of new predicate types.  In LREC, 2014.
  * Buck et al. [2014] C. Buck, K. Heafield, and B. van Ooyen.  N-gram counts and language models from the common crawl.  In LREC, 2014.
  * Caselli and Vossen [2017] T. Caselli and P. Vossen.  The event storyline corpus: A new benchmark for causal and temporal relation extraction.  2017\.
  * Chambers and Jurafsky [2008] N. Chambers and D. Jurafsky.  Unsupervised learning of narrative event chains.  In ACL, pages 789–797, 2008.
  * Church and Hanks [1990] K. Ward Church and P. Hanks.  Word association norms, mutual information, and lexicography.  Computational linguistics, 1990.
  * Clark et al. [2018] E. Clark, Y. Ji, and N. A Smith.  Neural text generation in stories using entity representations as context.  In NAACL, pages 2250–2260, 2018.
  * Dasgupta et al. [2018] T. Dasgupta, R. Saha, L. Dey, and A. Naskar.  Automatic extraction of causal relations from text using linguistically informed deep neural networks.  In Annual SIGdial Meeting on Discourse and Dialogue, 2018.
  * Do et al. [2011] Q. Do, Y. Chan, and D. Roth.  Minimally supervised event causality identification.  In EMNLP, pages 294–303, 2011.
  * Dunietz et al. [2017a] J. Dunietz, L. Levin, and J. Carbonell.  Automatically tagging constructions of causation and their slot-fillers.  TACL, pages 117–133, 2017.
  * Dunietz et al. [2017b] J. Dunietz, L. Levin, and J. Carbonell.  The because corpus 2.0: Annotating causality and overlapping relations.  2017\.
  * Dunietz et al. [2018] J. Dunietz, J. G Carbonell, and L. Levin.  Deepcx: A transition-based approach for shallow semantic parsing with complex constructional triggers.  In EMNLP, 2018.
  * Gehring et al. [2017] J. Gehring, M. Auli, D. Grangier, D. Yarats, and Y. N. Dauphin.  Convolutional sequence to sequence learning.  In ICML, 2017.
  * Girju et al. [2007] R. Girju, P. Nakov, V. Nastase, S. Szpakowicz, P. T., and D. Y.  Semeval-2007 task 04: Classification of semantic relations between nominals.  2007\.
  * Girju [2003] Roxana Girju.  Automatic detection of causal relations for question answering.  2003\.
  * Gordon and Van Durme [2013] J. Gordon and B. Van Durme.  Reporting bias and knowledge acquisition.  In AKBC, 2013.
  * Gordon et al. [2011] A. S Gordon, C. A Bejan, and K. Sagae.  Commonsense causal reasoning using millions of personal stories.  In AAAI, 2011.
  * Guan et al. [2019] J. Guan, Y. Wang, and M. Huang.  Story ending generation with incremental encoding and commonsense knowledge.  In AAAI, 2019.
  * Hashimoto et al. [2014] C. Hashimoto, K. Torisawa, et al.  Toward future scenario generation: Extracting event causality exploiting semantic relation, context, and association features.  In ACL, 2014.
  * Hendrickx et al. [2009] I. Hendrickx, Su Nam Kim, et al.  Semeval-2010 task 8: Multi-way classification of semantic relations between pairs of nominals.  In SE, 2009.
  * Hidey and McKeown [2016] Christopher Hidey and Kathy McKeown.  Identifying causal relations using parallel wikipedia articles.  In ACL, pages 1424–1433, 2016.
  * Hieber et al. [2017] F. Hieber, T. Domhan, et al.  Sockeye: A toolkit for neural machine translation.  arXiv, 2017.
  * Hokamp and Liu [2017] Chris Hokamp and Qun Liu.  Lexically constrained decoding for sequence generation using grid beam search.  In ACL, 2017.
  * Hu et al. [2019a] J E. Hu, Huda Khayrallah, et al.  Improved lexically constrained decoding for translation and monolingual rewriting.  In NAACL, 2019.
  * Hu et al. [2019b] J E. Hu, R. Rudinger, M. Post, and B. Van Durme.  Parabank: Monolingual bitext generation and sentential paraphrasing via lexically-constrained neural machine translation.  In AAAI, 2019.
  * Jabeen et al. [2014] S. Jabeen, X. Gao, and P. Andreae.  Using asymmetric associations for commonsense causality detection.  In PRICAI, 2014.
  * Khoo et al. [2000] Christopher SG Khoo, Syin Chan, and Yun Niu.  Extracting causal knowledge from a medical database using graphical patterns.  In ACL, 2000.
  * Kruengkrai et al. [2017] C. Kruengkrai, K. Torisawa, et al.  Improving event causality recognition with multiple background knowledge sources using multi-column convolutional neural networks.  In AAAI, 2017.
  * Li et al. [2018a] Z. Li, X. Ding, and T. Liu.  Constructing narrative event evolutionary graph for script event prediction.  In IJCAI, pages 4201–4207, 2018.
  * Li et al. [2018b] Z. Li, X. Ding, and T. Liu.  Generating reasonable and diversified story ending using sequence to sequence model with adversarial training.  In Coling, 2018.
  * Li et al. [2019a] Z. Li, T. Chen, and B. Van Durme.  Learning to rank for plausible plausibility.  In ACL, 2019.
  * Li et al. [2019b] Z. Li, X. Ding, and T. Liu.  Story ending prediction by transferable bert.  In IJCAI, 2019.
  * Luo et al. [2016] Z. Luo, Y. Sha, K. Q Zhu, S. Hwang, and Z. Wang.  Commonsense causal reasoning between short texts.  In Knowledge Representation and Reasoning, 2016.
  * Luo et al. [2019] F. Luo, D. Dai, P. Yang, T. Liu, B. Chang, Z. Sui, and X. Sun.  Learning to control the fine-grained sentiment for story ending generation.  In ACL, 2019.
  * Mirza et al. [2014] P. Mirza, R. Sprugnoli, et al.  Annotating causality in the tempeval-3 corpus.  In CAtoCL, 2014.
  * Mostafazadeh et al. [2016] N. Mostafazadeh, A. Grealish, et al.  Caters: Causal and temporal relation scheme for semantic annotation of event structures.  In Events, 2016.
  * Nie et al. [2019] A. Nie, E. Bennett, and N. Goodman.  DisSent: Learning sentence representations from explicit discourse relations.  In ACL, 2019.
  * Ning et al. [2018] Q. Ning, Z. Feng, et al.  Joint reasoning for temporal and causal relations.  In ACL, 2018.
  * O’Gorman et al. [2016] T. O’Gorman, K. Wright-Bettner, and M. Palmer.  Richer event description: Integrating event coreference with temporal, causal and bridging annotation.  In CNS, 2016.
  * Phang et al. [2018] J. Phang, T. Févry, and S. R Bowman.  Sentence encoders on stilts: Supplementary training on intermediate labeled-data tasks.  arXiv:1811.01088, 2018.
  * Poliak et al. [2018] A. Poliak, J. Naradowsky, A. Haldar, R. Rudinger, and B. Van Durme.  Hypothesis only baselines in natural language inference.  In LCS, 2018.
  * Post and Vilar [2018] M. Post and D. Vilar.  Fast lexically constrained decoding with dynamic beam allocation for neural machine translation.  In NAACL, 2018.
  * Prasad et al. [2008] R. Prasad, N. Dinesh, et al.  The penn discourse treebank 2.0.  In LREC, 2008.
  * Radford et al. [2019] A. Radford, J. Wu, et al.  Language models are unsupervised multitask learners.  2019\.
  * Radinsky and Horvitz [2013] K. Radinsky and E. Horvitz.  Mining the web to predict future events.  In WSDM, 2013.
  * Radinsky et al. [2012] K. Radinsky, S. Davidovich, and S. Markovitch.  Learning causality for news events prediction.  In WWW, 2012.
  * Raffel et al. [2019] C. Raffel, N. Shazeer, et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  arXiv:1910.10683, 2019.
  * Rashkin et al. [2018] H. Rashkin, M. Sap, E. Allaway, N. A. Smith, and Y. Choi.  Event2Mind: Commonsense inference on events, intents, and reactions.  In ACL, 2018.
  * Riaz and Girju [2010] M. Riaz and R. Girju.  Another look at causality: Discovering scenario-specific contingency relationships with no supervision.  In Semantic Comp., 2010.
  * Roemmele et al. [2011] M. Roemmele, C. A. Bejan, and A. S Gordon.  Choice of plausible alternatives: An evaluation of commonsense causal reasoning.  In AAAI, 2011.
  * Rudinger et al. [2017] R. Rudinger, Chandler May, and B. Van Durme.  Social bias in elicited natural language inferences.  In Ethics in NLP, 2017.
  * Sap et al. [2019] M. Sap, R. Le Bras, et al.  Atomic: An atlas of machine commonsense for if-then reasoning.  In AAAI, 2019.
  * Sasaki et al. [2017] S. Sasaki, S. Takase, et al.  Handling multiword expressions in causality estimation.  2017\.
  * Schneider et al. [2015] N. Schneider, V. Srikumar, J. D Hwang, and M. Palmer.  A hierarchy with, of, and for preposition supersenses.  In Linguistic Annotation, 2015.
  * Schuler [2005] Karin Kipper Schuler.  Verbnet: A broad-coverage, comprehensive verb lexicon.  2005\.
  * Sennrich et al. [2016] R. Sennrich, B. Haddow, and A. Birch.  Neural machine translation of rare words with subword units.  In ACL, 2016.
  * Speer et al. [2017] R. Speer, J. Chin, and C. Havasi.  Conceptnet 5.5: An open multilingual graph of general knowledge.  In AAAI, 2017.
  * Talmy [1988] L. Talmy.  Force dynamics in language and cognition.  Cognitive science, 1988.
  * Tang et al. [2019] J. Tang, T. Zhao, et al.  Target-guided open-domain conversation.  In ACL, 2019.
  * Thompson et al. [2019] B. Thompson, J. Gwinnup, et al.  Overcoming catastrophic forgetting during domain adaptation of neural machine translation.  In NAACL, 2019.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, et al.  Attention is all you need.  In NIPS. 2017.
  * Wang and Wan [2019] T. Wang and X. Wan.  T-cvae: Transformer-based conditioned variational autoencoder for story completion.  In IJCAI, 2019.
  * Webber et al. [2019] B. Webber, R. Prasad, A. Lee, and A. Joshi.  The pdtb 3.0 annotation manual, 2019.
  * Wolff and Song [2003] P. Wolff and G. Song.  Models of causation and the semantics of causal verbs.  CP, 2003.
  * Wolff [2007] P. Wolff.  Representing causation.  Journal of experimental psychology: General, 2007.
  * Zhang et al. [2019] H. Zhang, X. Liu, et al.  Aser: A large-scale eventuality knowledge graph.  arXiv, 2019.
  * Zhao et al. [2017] S. Zhao, Q. Wang, S. Massung, et al.  Constructing and embedding abstract event causality networks from text snippets.  In WSDM, 2017.