PABI: A Unified PAC-Bayesian Informativeness Measure for Incidental Supervision Signals
Authors: Hangfeng He
Mingyuan Zhang
Qiang Ning
Dan Roth
Venue:  (2021)
Keywords: informativeness measure
incidental supervision
natural language processing

Abstract: Real-world applications often require making use of {\em a range of incidental supervision signals}. However, we currently lack a principled way to measure the benefit an incidental training dataset can bring, and the common practice of using indirect, weaker signals is through exhaustive experiments with various models and hyper-parameters. This paper studies whether we can, {\em in a single framework, quantify the benefit of various types of incidental signals for one's target task without going through combinatorial experiments}. We propose PABI, a unified informativeness measure motivated by PAC-Bayesian theory, characterizing the reduction in uncertainty that indirect, weak signals provide. We demonstrate PABI's use in quantifying various types of incidental signals including partial labels, noisy labels, constraints, cross-domain signals, and combinations of these. Experiments with various setups on two natural language processing (NLP) tasks, named entity recognition (NER) and question answering (QA), show that PABI correlates well with learning performance, providing a promising way to determine, ahead of learning, which supervision signals would be beneficial.

Under review as a conference paper at ICLR 2021
PABI: A UNIFIED PAC-BAYESIAN INFORMATIVENESS MEASURE FOR INCIDENTAL SUPERVISION SIGNALS
Anonymous authors Paper under double-blind review
ABSTRACT
Real- world applications often require making use of a range of incidental supervi- sion signals. However, currently lack principled way measure the benefit an incidental training dataset can bring, and the common practice of using indirect, weak signals is through exhaustive experiments with various models and hyper- parameters. This paper studies whether we can, in a single framework, quantify the benefit of various types of incidental signals for one's target task without go- ing through combinatorial experiments. We propose PABI, unified informative- ness measure motivated by PAC-Bayesian theory, characterizing the reduction in uncertainty that indirect, weak signals provide. We demonstrate PABI's use in quantifying various types of incidental signals including partial labels, noisy la- bels, constraints, rross-domain signals, and combinations of these. Experiments with various setups on two natural language processing (NLP) tasks, named en- tity recognition (NER) and question answering (QA), show that PART correlates well with learning performance, providing a promising way to determine, ahead of learning, which supervision signals would be beneficial.
INTRODUCTION
The supervised learning paradigm, where direct supervision signals are assumed to be available in high-quality and large amounts, has been struggling to fulfill the needs in many real-world AI applications. As a result, researchers and practitioners often resort to datasets that are not collected
directly for the target task but, hopeuullyccaptuue some phenomena useful for it (Pan & Yang 2009
Vapnik & Vashist 2009; Roth, 2017 Kolesnikov et al. 2019). However, it remains unclear how to predict the benefits of these incidental signals on our target task beforehand, so the common practice is often rril--nn--rrro: do experiments with different combinations of datasets and learning protocols, often exhaustively, to achieve improvement on a target task (Liu et al., 2019 Khashabi et al.) (2020). Not only this is very costly, this trial-an and-error approach can also be hard to interpret: if we don't I see improvements, is it because the incidental signals themselves are not useful for our target task, or is it because the learning protocols we have tried are inappropriate?
The difficulties of foreshadowing the benefits of various incidental supervision signals are two-fold. First, it is hard to provide unified measure because of the intrinsic differences among different signals (e.g.. how do we predict and compare the benefit of learning from noisy data and the benefit of knowing some constraints for the target task?). Second, it is hard to provide a practical measure supported by theory. Previous attempts are either not practical or too heuristic (Baxter) 1998) Ben- David et al.) 2210 Thrun & O'Sullivan 1998. Gururangan et al.) 2020 In this paper, we propose a unified PA PAC-Bayesian motivated informativeness measure (PABI) to quantify the value of inci- dental signals. We suggest that the informativeness of various incidental signals can be uniformly characterized by the reduction in the original concept class uncertainty they provide. Specifically, in the PAC-Bayesian framework the informativeness is based on the Kullback-Leibler (KL) di- vergence between the prior and the posterior, where incidental signals are used to estimate better prior (closer to the gold posterior) to achieve better generalization performance. Furthermore, we provide a more practical entropy-based approximation of PABI. In practice, PABI first computes the entropy of the prior estimated from incidental signals, and then computes the relative decrease to the entropy of the prior without any information, the informativeness of incidental signals.
We choose the PAC-Bayes framework here because it allows to link PABI the performance measure.

---

Under review as a conference paper at ICLR 2021
Constraints:
I-PER
H-RG
Auxiliar::
B
B
Noisy:
B-PER
O
B-PER
O
FORG
Partial:
B-PER
HORG
Gold:
B-PER
I-PER
B-ORG
H-ORG
Words:
Alan
Turing
studied
Princeton
Universily
Figure I: An example of NER with various incidental supervision signals: partial labels (some missing labels in structured outputs), noisy labels (some incorrect labels), auxiliary labels (labels of another task, e.g. named entity detection in the figure), and constraints in structured learning (e.g. the BIO constraint where I-X must follow B-X or I-X (Ramshaw & Marcus 1999) in the figure).
We have been in need of a unified informativeness measure like PABI. For instance, it might be obvious that we can expect better learning performance if the training data are less noisy and more completely annotated, but what if we want to compare the benefits of noisy dataset and that of a partial dataset? PABI enables this kind of comparisons beforehand, on a wide range of incidental signals such as partial labels, noisy labels, constraints auxiliary signals, cross-domain signals, and some combinations of them, for sequence tagging tasks in NI.P. A specific example of NER is shown in Fig. D and the advantages of PABI are in Table] [
Finally, our experiments on two NLP tasks, NER and QA, show that there is a strong positive correlation between PABI and the relative improvement for various incidental signals. This strong positive correlation indicates that the proposed unified, theory-motivatee measure PABI can serve a good indicator of the final learning performance, providing promising way to know which signals are helpful for a target task beforehand.
Organization. We start with related work in Section 1.1 Then we derive informativeness measure PABI in Section [ We show examples on how to compute PABI using various incidental signals in Section 3 We verify the effectiveness of PABI in Section Section 5 concludes this paper.
1.1 RELATED WORK
There are lots of practical measures proposed quantify the benefits of specific types of signals. For example, a widely used measure for partial signals in structured learning is the partial rate (Cour
ct al. 2011 Hovy& & Hovy 2012 Liu & Dietterich 2014, Van Rooyen & Williamson, 20177) Ning
et al. 2019); widely used measure for noisy signals is the noise ratio (Angluin & Laird 1988
Natarajan et al. 2013; Rolnick et al., 2017: Van Rooyen & Williamson, 2017); [ing et al. (0019)
propose
the concaveness of the mutual information with different percentage of annotations
to quantify the strength of constraints in the structured learning; others, in NL.P, have quantified the
contribution of constraints experimentally (Chang et al., 2012 2008). Bjerva (2017) proposes to use conditional entropy or mutual information to quantify the value for auxiliary signals. As for domain adaptation, domain similarity can be measured by the performance gap between domains Wang et al. 2219) or measures based on the language model in NLP, such as the vocabulary overlap Gururangan et al. 2020). Among them, the most relevant work is (Bjerval (0177). However, their conditional entropy mutual information is based on token-level label distribution, which cannot be used for incidental signals involving multiple tokens or inputs, such as constraints and cross-domain signals. At the same time, for the cases where both P PABI and mutual information can handle, PABI works similar to the mutual information as shown in Fig. 2 and PABI can further be shown to be a strictly increasing function of the mutual information. The key advantage of our proposed measure PABI is that PABI is a unified measure motivated by the AAC-Bayesian theory for a broader range of incidental signals compared to these practical measures for specific types of incidental signals.
There also has been a line of theoretical work that attempts to exploit incidental supervision signals. Among them, the most relevant part is task relatedness. Bavid & Borbely (2008) define the
Constraintss used to model the dependency among words and sentences, which are considered in lot of work, such as CRF (Lafferty al. 200T) and II.P (Roth Yih 2004
2

---

Under review as a conference paper at ICLR 2021
Incidental Supervision Signals
Unidied Measure mixed-type
S
Support
partal
nossy
constrantss
auxtlaary
cross-domain
cross-lype
Thooreical
Empirical
CST HH' LD'14
X
X
x
AL,85, NDRT 13, 17
VWTTZ, 2N
8
X
x
x
8
V
x
NHERTTI
B'17 2M
8
x
8
7
x
8
8
8
8
7
PABI (ours)
Table I: Comparison between PABI and prior works: (1) Cross-type: PABI is a unified measure which can measure the benefit of different types of incidental signals (e.g., comparing noisy dataset and partially annotated dataset). (2) Mixed-type: PABI can measure the benefit of mixed incidental signals (e.g., dataset that is both noisy and partially annotated). (3) PABI is derived from PAC- Bayesian theory but also easy to compute in practice: PABI is shown to have similar or better predicting capability of signals' benefit (see Figs. and 3 and Sec. 3.1
task relatedness based on the richness of transformations between inputs for different tasks, but their analysis is limited to cases where data is from the same classification problem but the inputs are in different subspace. Juba (2006) proposes to use the joint Kolmogorov complexity (Li et al. 2008) to characterize relatedness, but it is still unclear how to compute the joint Kolmogorov complexity in real-world applications. Mahmud & Rayl (2008) further propose to use conditional Kolmogorov complexity to measure the task relatedness and provide empirical analysis for decision trees, but it unclear how to their relatedness for other models, such as deep neural networks. Thhun & O' O'Sullivan| ( (9988 propose to cluster tasks based on the similarity between the task-optimal distance metric of K-nearest neighbors (KNN), but their analysis is based on KNN and it is unclear how to use their relatedness for other models. A lot of other works provide quite good qualitative analysis to show various incidental signals are helpful but they did not provide quantitative analysis quantify to what extent these types of incidental signals can help (Balcan & Blum 2010 MaauuMMstaaaa 1993) Natarajan et al. 2013 Van Rooyen & Williamson, 2017 Baxter 1998 London et al. 2
Ciliberto et al. 2019 David et al.] [010]] Wang et al., [2020). Compared to these theoretical analyses, PABI can be easily used in practice to quantify the benefits of a broader range of incidental signals.
2 PABI: A UNIFIED PAC-BAYESIAN INFORMATIVENESS MEASURE
We start with notations and preliminaries. Let X' be the input space. y' be the label space, and y be the prediction space. Let D denote the underlying distribution on X' x y. Let é: y> : y - R4 be the loss function that we use evaluate learning algorithms. A of training samples is generated i.i.d. from D. In the common supervised learning setting, we usually assume the concept that generates data comes from the concept class C. In this paper, we assume C is finite, and its size is [C], which is common NLP. We want to choose a predictor c X D from such that it generalizes well to unseen data with respect to L, measured by the generalization error (c) Exxyy>D c(x))). The training error over is Rs(c) d. >. ely,, c(x:)).
{ yi m
More generally, instead of predicting a concept, we can specify distribution over the concept class. Let denote the space probability distributions over C. General Bayesian learning algo- rithms (Zhang et al. 2006) in the PAC-Bayesian framework (McAllester) 1999a Seeger 2002 McAllester 2003b a Maurer 2004 Guedj] 2019) aim to choose a posterior πΛ E P over the concept class C based
prior To E P and training data S, where À is hyper parameter that controls the tradeoff between the prior and the data likelihood. In this setting, the training er- and the generalization eтror need to be generalized, to take the distribution into account, as LT(Tx) = Ee_,r, [Rs and (D(TA)= = Ee-aa [c)] respectively. One can easily see that when the posterior is one-hol (exactly one entry of the distribution is 1), have the original definitions of training error and generalization error, as in the PAC framework (Valiant 1984).
'Papers are denoted by abbreviations of author names as: CST'11 CCurr et al. 2011 HH' 12 (Hovy &
Hovy 2012). LD'14 (Liu & Dietterich 2014). AL'88 (Angluin & Laird] 1988). NDRT'I3 13 (Natarajan et al.
2013)
RVBS'17 (Rolnick al. 2017). VW 17 (Van Rooyen & Willimmsn (017). WNR 20 (Wang et al.
2020
NHFR'19 Ning 2019 E 17 (Bjrvva 2017), GMSLBDS (Gururangan 2020
3

---

Under review as a conference paper at ICLR 2021
2.1 INFORMATIVENESS MEASURES IN THE PAC-BAYESIAN FRAMEWORK
We are now ready to derive the proposed informativeness measure PABI motivated by PAC-Ban Bayes.
The generalization error bound in the PAC-Bayesian framework (Guedj 2019; Catoni 2007) says
that with probability 1 over S, LD(xx) LD(xa)) + &B(Dx (x [ )
where
m
T is the posterior distribution with the optimal X 2m 2m(Di mo)+ 8)
E is the gold
posterior that generates the data, D (T* [[=)) denotes the KL divergence from To to ' and C are two constants. This is based on the Theorem 2 in [uedd (2019).
As shown in the generalization bound, the generalization error is bounded by the KL divergence D (x") (TO) from the prior distribution to the gold posterior distribution. Therefore, propose to utilize incidental signals improve the prior distribution from To to ao so that closer the gold posterior distribution л². Correspondingly, we can define PABI, the informativeness measure for incidental supervision signals, by measuring the improvement with regard to the gold posterior, in KL divergence sense.
Definition 2.1 (PABI). Suppose we use incidental signals improve the prior distribution from To to ng. The informativeness measure for incidental signals, PABI, is defined as
( mo)
S #0)= A
(1)
DKu ( (m)
Remark. Note that S(my, mo) = 0 if mi = Tu. while if nu = T,, then S( mu) = 1. This result is consistent with intuition that the closer #o n²" the more benefits we can gain from incidental signals. The square root function is used in PABT for two reasons: first, the generalization bounds in both PAC-Bayesian and PAC (see Sec. 2.2) frameworks have the square root function: second, in our later experiments, we find that square root function can significantly improve the Pearson correlation between the relative performance improvement and PABI. It is worthwhile to note that the square root is not crucial for our framework, because our goal is to compare the benefits among different incidental supervision signals, where the relative values are expressive enough. In this sense, any strictly increasing function in [0, 1] over the current formulation would be acceptable.
In our paper, we focus on the setting that the gold posterior x² is one-hot, which means л concen- trates on the true concept e" E C, though the definition of PART can handle general gold posterior. However, x is unknown in practice, which makes Eq. [T] hard to be computed in reality. In the
following, we provide an approximation Š PABI.
Definition 2.2 (Approximation of PABI). Assume that the original prior To is uniform, and the gold posterior n² is one-hot concentrated the true concept c² in C, as have assumed that is finite. Let H() be the entropy function. The approximation $ of PARI is defined
((m)) H(
(
S( TO)= A
C
The uniform prior Tn is usually used when we do not have information about the prior which concept in the class that generates data. The intuition behind Š is that, it measures how much entropy incidental signals reduce, compared with non-informative prior To- á can be computed through data and thus is practical. To see how this approximation works, first note DKL(TT) [[To) = In | because x² one-hot and To is uniform over the finite concept class C. Let me be the one-hot distribution concentrated on concept e for each E C. The approximation is that we estimate π² by Te, where e follows के: DKI( (T)) z Eanao D (KI(Tell fo). turns out Eowao ( (To) H (ffo). Therefore,
( S( #o) -- In |||
E Ec DKL TT)
DKI(TT To) Dx ([)
S(mo #o)-
In
We later show that the approximation of PABI and PABI is equivalent in the non-probabilistic cases with the finite concept class, indicating the quality of this approximation. Furthermore, the effec- tiveness of this approximation in NL.P applications also indicates the quality of this approximation.
4

---

Under review as a conference paper at ICLR 2021
2.2 PABI IN THE PAC FRAMEWORK
We have derived PABI in the PAC-Bayesian framework. Here, we discuss briefly on what PABI reduces to in the PAC framework and what limitations when PABI is restricted to the PAC frame- work. The generalization bound in the PAC framework (Mohri et al. 2018) says with probability
å over S. RD(c)= S Rs(c) + V
[ [iic++in
We propose to reduce the concept class from C
2m
by using incidental signals. Then PABI in the PAC framework can be written
In |C|
C(C,2)= =
In
It turns out that Eq. (3) is special case of Eq. when n² is one-hot over C. mo is uniform over and Ro is uniform over C (See Appx. A.1 for the derivation). As shown in Appx. A.1 can
that the three informativeness measures, PART in Eq. ( the approximation
PART in Eq. 2
and PABI in the PAC framework in Eq. 3 are equivalent, i.e. S(TTO, =o) = S(TO, To) = S C).
in the non- non-probabillitic cases with the finite concept class. The equivalence among three measures further indicates that both PABI and the approximation of PABI are reasonable.
However, PABI restricted the PAC framework cannot handle the probabilistic cases. For exam- ple, incidental signals can reduce the probability of some concepts, though the concept class is not reduced. In this example, S(C, C) is zero, but we actually benefit from incidental signals. Some analysis on the extensions and general limitations PABI can be found in Appx. A.2 and [A.3] We need to notice that the size of concept class also plays an important role in the lower bound on the generalization error (more details in Appx. A.4), indicating that PABT based on the reduction of the concept class is a reasonable measure.
3 EXAMPLES FOR PABI
In this section, we show some examples of sequence tagging tasks in NLP for PABI. Similar to the categorization of transfer learning (Pan & Yang 2009), we use inductive signals to denote the signals with a different conditional probability distribution (P(y x)) from gold signals, such noisy and auxiliary signals, and transductive signals to denote the signals with the same task (P(y x)) as gold signals but different marginal distribution of (P(x)) from gold signals, such cross-domain and cross-lingual signals. In our following analysis, we study the tasks with finite concept class which is quite common in NLP. For simplicity, we focus on simple cases where the number of incidental signals is large enough. How different factors (including base model performance, size of incidental signals, data distributions, algorithms, cost-sensitive losses) affect PABI are discussed in Appx. A.5 We derive the PABI for partial labels in detail and the derivations for others are similar. More examples and details can be found in Appx. A.6
3.1 EXAMPLES WITH INDUCTIVE SIGNALS
Partial labels. The labels for each example in sequence tagging tasks is sequence and some of them are unknown in this case. Assuming that the ratio of the unknown labels in data is 7p E [0, 1], the size of the reduced concept class will be [C] = L (m) V Vl"n, Therefore, S( #n) = S(To, mo) = S(C,C)
-| V1 Tpp It is consistent with the widely used partial rate because it is a monotonically decreasing function of the partial rate.
la 0 In [c
/
Noisy labels. For each token, P(vlğ) is determined by the noisy rate Th [0, i.e. P(y
No ?) = 1- 17, and the probability of other labels are all - We can get the corresponding probability distribution of labels over the tokens in all inputs (To over the concept class). In this way, STTO #0)
Th, Inf] (11))_ -1- nh In(1-n)) It is consistent with the widely used In
noise rate because it is monotonically decreasing function of the noisy rate. In practice, the noisy
$ *Given input X 1 generated from a distribution D, the task aims to get the corresponding label E ÿ = y L", where V is the vocabulary of input words, L is the label set for the task, and is the length of the input sentence.
5

---

Under review as a conference paper at ICLR 2021
rate can be easily estimated with some aligned data and the noise with more complex patterns (e.g. input dependent) is postponed as our future work.
3.2 EXAMPLES WITH TRANSDUCTIVE SIGNALS
For transductive signals, such cross dross-domain signals, we can first extend the concept class C to the extended concept class C with the corresponding extended input space X². After that, we can use incidental signals to estimate better prior distribution मf over the extended concept class C and then get the corresponding To over the original concept class by restricting the concept from A to X. In this way, the informativeness of transductive signals can still be measured by (TT, io)) or (mT, m.). The restriction step is similar to Roth & Zelenko 2000).
However, how to compute H (mo) is still unclear. We now provide way to estimate it. To better illustrate the estimation process for transductive signals, we provide the summary of core notations in Table 3 as shown in Appx. AA.I For simplicity, we use c(x) to denote the gold system gold signals, c(x) to denote the perfect system on the incidental signals, and ē(x) to denote the silver system trained on the incidental signals. Source domain (target domain) is the domain of incidental signals (gold signals). We use DD to denote the target domain and D to denote the source domain.
the
(x( is the marginal distribution of x under D, and similar definition for (x(x). In our analysis, assume a(x) is a noisy version of c(x) with the noisy rate v, and o(x) is a noisy version of x(x) with the noisy rate (7/) in the source (target) domain 1/1 = Exx (((()) o ē(x))
(n/ = (xx (((x) # o(x))).
In practice, 1) is unknown but it can be estimated by yn in the source domain and 722 (xx)x(x) ((xxx) * c(x)) (the noisy rate of the silver system compared to the gold system on the target domain) as follows:
= Exxx-Poxx (c(x) + ē(x)) = -111- - 1) - 72) (111-107
77)
(4)
1- C 7/1) 1- 11 m1)
Here we add an assumption: 1/f in the target domain is equal to ?)1 in the source domain ? In Appx. A.7 we can see that Eq. 4 serves as unbiased estimator for v under some sumptions, but the concentration rate will depend on the size of source data. requires finer- grained analysis noisy labels, the corresponding informativeness of transductive signals can be then computed as S(T. to) = /1 In([ (1))) In [I-)) In(1-1) Note that we treat tross-domain signals as a special type of noisy data, when is estimated.
the estimator in Eq. (4), which we postpone as our future work. Similar to
in 21
To justify the use of 1j in the informativeness measure for transductive signals, we show in Theorem A.2 (see Appx. (A8)) that (informally speaking) the generalization error of learner that is jointly trained on data from both source and target domains can be upper bounded by r) (plus a function of the size of the concept class and the number of samples). Finally we note that although the computation cost of PABI for transductive signals is higher than that for inductive signals, it is still much cheaper than building combined models with joint training. For example, given T source domains and 7 target domains, the goal is to select the best source domain for each target domain. If we use the joint training, we need train T x T 7 models. However, with PABI, we only need to train T + T = 2T models. Furthermore, for each model, joint training on the combination of two domains requires more time than the training on single domain used in PABI. In this situation, we can see that PABI is much cheaper than building combined models with joint training.
3.3 EXAMPLES WITH MIXED INCIDENTAL SIGNALS
The mix of partial and noisy labels. The corresponding informativeness for the mix of partial and noisy labels is S(TO, mo) = v(1 mpp) * (1 no In(1 11-1)-m- no, In In((m)))))))))) where
In |2|2]
Mp [0, 1] denotes the ratio of unlabeled tokens, and 7/ [0, 1] denotes the noise ratio.
'If there is no jointly annotated data, we can use similar methods as Bjerva 2017) to create some approxi- mate jointly annotated data.
We add this assumption mainly because want to estimate the r only based on 171 and 172, which can be easily computed in practice.

---

Under review as a conference paper at ICLR 2021
Relative Improvement
Relative Improvement
Relative Imgroverentt
0.8
0.6
0.6
0.6
0.4
0.4
+
0.4
0.2
O partial rate + PABI
0.2
* noisy rate + PABI
0.2
mutual Information PABI
0.2
0.2
0.4
0.6
0.8
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Informativeness
Informativeness
Informativeness
(a) Partial labels
(b) Noisy labels
(c) Auxiliary labels
Relative Improvement
Relative Imprrvemmnt
Relative Improvement
0.8
0.8
0.8
0.6
0.8
0.6
0.4
+
0.2
0.2
PABI
+ PABI
0.5
Informativeness
Informativeness (e) The mix of partial labels
Informativeness
(d) The mix of partial and noisy labels
(1) Various inductive signals
and constraints
Correlations between informativeness and relative performance improvement for NER with various inductive signals. On one hand, shown in (a)-(c), PABI has similar foreshad- owing ability with measures for specific signals. On the other hand, as shown (d)-(f), PABI measure the benefits of mixed inductive signals and compare different types of inductive signals, which cannot be handled by existing frameworks. For individual inductive signals, the baselines (gray points) are, i.e. one minus partial rate for partial labels (Cour al. 2011 Hovy & Hovy 2012 Liu & Dietterich 2014, Van Rooyen & Williamson [017]]Ning et al. 2019), one minus noisy rate for noisy labels (Angluin & Laird 1988 Natarajan et al. 2013 Rolnick et al.
Figure 2:
2017 Van Rooyen & Williamson, 2017]. and entropy normalized mutual information for auxiliary
labels (Bjerva (017). For NER with various inductive signals (f) (with all PART points from (a)-
(e)), Pearson's correlation and Spearman's rank correlation are 0.92 and 0.93. Note that the relative improvement for NER (with informativeness 0.90 but relative improvement 0.70) in auxiliary labels (c) is smaller than expected mainly due to the imbalanced label distribution (88% O among all
BIO labels). More discussions about the imbalanced distribution can be found in Appx. A.5
The mix of partial labels and constraints. For BIO constraints with partial labels, we can use dynamic programming with sampling as Ning et al. 2019) to estimate In [C] and S(TTO #o).
EXPERIMENTS
In this section, we verify the effectiveness of PARI various inductive signals and transductive signals on NER and QA. More details about experimental settings are in Appx. A.9
Learning with various inductive signals. In this part, we analyze the informativeness of inductive signals for NER. We use Ontonotes NER (18 types of named entities) (Hovy et al.) (0066) as the main task. We randomly sample 10% sentences (30716 words) of the development signals, 90% sentences (273985 words) of the development set as the large incidental signals. We use two-layer NNs with 5-gram features as our basic model. The lower bound for our experiments is the result of the model with small gold Ontonotes NER annotations and bootstrapped on the unlabeled texts of the large gold Ontonotes NER, which is 38 F1, and the upper bound the result of the model with both small gold Ontonotes NER annotations and the large gold Ontonotes NER annotations, which is 61 Fl. To utilize inductive signals, we propose a new bootstrapping based algorithm CWBPP (Algorithm inference stage by approximating a better prior. It is an extension of CoDL (Chang et al. 2007) with various inductive signals.
the small gold
| in Appx. A.10). where inductive signals used improve the
We experiment on NER with various inductive signals, including three types individual signals, partial labels, noisy labels, auxiliary labels, and two types of mixed signals: signals with both partial

---

Under review as a conference paper at ICLR 2021
Relative improvement
1
Relative improvement
Relative Improvement
0.8
A
A D
A
A
0.6
0.6
0.6
44 +
0.4
0.4
0.4
vocab nalve + PABI
vocab nalve PABI
+4
0
O vocab naive + PABI
0.2
0.2
0.2
0
0.2
0.6 Informativeness
0.4
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Informativeness
Informativeness
(a) Joint-training NER with
(b) Joint-training QA with baselines and PABI
(b) Pre-training QA with baselines and PABI
baselines and PABI
Figure 3: Correlation between informativeness measures (baselines or the PART) and relative per- formance improvement (via joint training or pre-training) for cross-domain NER and cross-domain QA. We can see that the correlation between the relative improvement and PABI is stronger than other baselines. Red results with the PABI which is based on 1 in Eq. (4); Gray points in- dicate the results with the naive informativeness measure 7/2i Black points indicate the results with the vocabulary overlap baseline (Gururangan al. 2020). The Pearson's correlation of three in- formativeness measure in the three cases are: 0.96/0. 19/-0.85 L.00/0.88/-0.. 0.99/0.80 1999/0.8////101 0.30,, indicating the quality of the PABI measure. Similarly, the corresponding Spearman's 's rank correla- tion are: 1. 1.00000.50/11..0 1.00, 1.00/0.2//0.30 1.00/0.8//000
and noisy labels, and signals with both partial labels and constraints. As shown in Fig. 2 we find that there strong correlation between the relative improvement and PART for various inductive signals. For individual signals in Fig. 2(a)-2(c), we find that PABI have similar foreshadowing ability comparing to the measures for specific signals, i.c., 1 - Tpp for partial labels, - The for noisy labels, and entropy normalized mutual informatior & (YY:)) for auxiliary labels. For mixed signals H(Y)
in Fig. 2(d)-2(e). the strong correlation is quite promising because the benefits of mixed signals cannot be quantified by existing frameworks. Finally, the strong positive correlation for different types of signals in Fig. 2(f) indicates that it is feasible to compare the benefits of different incidental signals with PART, which cannot be addressed by existing frameworks.
Learning with cross-domain signals. In this part, we consider the benefits of cross-domain signals for NER and QA. For NER, we consider four NER datasets, Ontonotes, CoNLL, twitter (Strauss iet al. 2016), and GMB (Bos et al. 2017). We aim to detect the person names here because the only shared type of the four datasets is the person In our experiments, the twitter NER serves as the main dataset and other three datasets are cross-domain datasets. There are 85 sentences in the small gold training set, 756 sentences (9 times of the gold signals) in the large incidental training set, and 851 sentences in the test set. We tried larger datasets for both gold and incidental signals (keeping the ratio between two sizes as 9) and the results are similar as long as the number of gold signals is not too large. For QA, we consider SQuAD (Rajpurkar et al.) (0116). QAMR (Michael et al. 2017)) QA-SRL Bank 2.0 (FitzGerald et al. 2018). QA-RE (Levy et al. 2017). NewsQA (Trischler et al. 2017]. TriviaQA (Joshi al. 2017). In our experiments, the SQUAD dataset serves the main dataset and other datasets are cross-domaie datasets. We randomly sample 700 QA pairs as the small gold signals, about 6.2K QA pairs as the large incidental signals (9 times of the small gold signals), and K QA pairs as the test data.
We BERT our basic model and consider two strategies make use of incidental signals: joint training and pre-training For NER, the lower bound is the result with only small gold twitter anno- tations, which is 61.51 F1, and the upper bound is the result with both small gold twitter annotations and large gold twitter annotations, which is 78.31. For QA, the lower bound is the result with only small gold SQuAD annotations, which is 26.45 exact match. The upper bound for the joint training is the result with both small gold SQuAD annotations and large SQuAD annotations, which is 50.72 exact match. Similarily, the upper bound for the pre-training is 49.24 exact match.
In Bjerva 2017). they propose to use mutual information or conditional entropy measure the informa- tiveness, so we normalize the mutual information with the entropy to make the value between 0 and 1. Note that our focus here is cross-domain signals, the divergent set of classes for different domains is mix of cross-domain and auxiliary signals, which is our future work.
8

---

Under review as a conference paper at ICLR 2021
The relation between the relative improvement (pre-training or joint training) and informativeness measures (baselines or the PABI) is shown in Fig. 3 We can see that there is a strong positive correlation between the relative improvement and PABI for cross-domain signals. Comparing the naive baseline 7/2 we can see that the adjustment from vn is crucial (Eq. (4), indicating that directly using 72 is not a good choice. We also show the vocabulary overlap baseline as in (Gururangan iet al. (2200 where we compute the overlap over the top 1K most frequent unigrams (excluding stop words and punctuations) between different domains. The results for this baseline are quite bad, and the fact that our data is not so large makes this baseline more valueless.
CONCLUSION AND FUTURE WORK
Motivated by PAC- Bay-saa theory, this paper proposes unified framework, PABI, to characterize incidental supervision signals by how much uncertainty they can reduce in the hypothesis space. We demonstrate the effectiveness of PART in foreshadowing the benefits of various signals, i.e., partial labels, noisy labels, auxiliary labels, constraints, cross-domain signals and combinations of them, for solving NER and QA. To our best knowledge, PABI is the first informativeness measure that can handle various incidental signals and combinations of them; PABI is motivated by PAC-Bayes and can be easily computed in real-world tasks. As the recent success of natural language modeling has given rise to many explorations in knowledge transfer across tasks and corpora (Bjerva 2017 Phang et al. 2018, Zhu et al. 2019 Liu et al.) 2019: He et al. 2020 Khashabi et al. 2020) PABT a concrete step towards explaining some of these observations.
We conclude our work by pointing out several interesting directions for our future work.
First, PABI can also provide guidance in designing learning protocols. For instance, in a B/I/O sequence chunking task 10 missing labels make it partial annotation problem, while treating miss- ing labels O introduces noise. Since the informativeness of partial signals is larger than that of noisy signals with the same partial/noisy rate (see details in Sec. 3.1.. PABI suggests us not to treat missing labels as O, and this is exactly Mayhew et al. (2019) prove to via their experiments. We plan to explore more in this direction to apply PABI in designing better learning protocols.
Second, need to acknowledge that current exploration for auxiliary labels is still limited. The results for auxiliary labels with a different label set (Fig. 2(c)) is blocked by the imbalanced label distribution (Appx. A.5). For more complex cases, such as part-of-speech tagging (PoS) for NER, we can only treat them as cross-sentence constraints now and the results are also limited (Appx. A.6). In future, we will work more in this direction to better quantify the value of auxiliary signals.
Another interesting direction is to link PABT with the generalization bound. It might be too hard to directly link PABI with the generalization bound for all types of incidental signals, but it is possible to link it to the generalization bound for some specific types. For example, for partial and noisy labels, PABI can directly be expressed in the generalization bound as in (Cour et al. 2011 Natarajan et a 2013 Van Rooyen & Williamson, [0177] Wang et al. 2020). The main difficulties are constraints and auxiliary signals, and we postpone it as our future work.
Finally, we plan to evaluate PART in more applications, such as textual entailment and image clas- sification, and more types of signals, such as cross-lingual and cross-modal signals.
REFERENCES
Yaser S Abu-Mostafa. Hints and the VC dimension. Neural Computation, 5(2):278 22882 1993.
Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 2(4):343-370 1988.
Isabelle Augenstein, Leon Derczynski, and Kalina Bontcheva. Generalisation in named entity recog- nition: A quantitative analysis. Computer Speech & Language, 44:61-83, 2017.
Floriaalorina Balcan and Avrim Blum. A discriminative model for semi-supervised learning. Jour- nal of the ACM (JACM), 57(3):144, 2010.
B/t/OOO indicates if token the hegin/inside/ousside of text span.

---

Under review as a conference paper at ICLR 2021
Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-1 -16111388616,1101 2006.
Jonathan Baxter. Theoretical models of learning learn. In Learning to learn, pp. 71-94. Springer, 1998.
Shai Ben-David and Reba Schuller Borbely, A notion of task relatedness yielding provable multiple- task learning guarantees. Machine learning, 73(3):273-287, 2008.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning, 79(1-2)1151-75,,
2010.
Johannes Bjerva. Will my auxiliary tagging task help? estimating auxiliary tasks effectivity in multi- task learning. In Proceedings of the 21st Nordic Conference on Computational Linguistics, pp- 2017.
Johan Bos, Valerio Basile, Kilian Evang, Noortje Venhuizen, and Johannes Bjerva. The groningen meaning bank. In Handbook of linguistic annotation, pp. 463-496. Springer, 2017.
Olivier Catoni. Pac-bayesian supervised classification: the thermodynamics of statistical learning.
arXiv preprint arXiv:0712.0245: 2007.
Ming-Wey Wei Chang, Lev Ratinov, and Dan Roth. Guiding cupi-Suuervision with Constraint-Driver Learning. In Proc. of the Annual Meeting of the Association for Computational Linguistics (ACL), pp. 280-287, Prague, Czech Republic, 6 2007. Association for Computational Linguistics.
Ming-Wac Wei Chang, Lev Ratinov, Nicholas Rizzolo, and Dan Roth. Learning and Inference with Constraints. 7 2008.
Ming-Wee Wei Chang,
Lev Ratinov, and Dan Roth. Structured Learning with Constrained Conditional Models. Machine Learning, pp. 399-431, 6 2012.
Yu-An Chung, Wei-Hung Weng, Schrasing Tong, and James Glass. Unsupervised cross-modal alignment of speech and text embedding spaces. In Advances in Neural Information Processing Systems, pp. 7354-7364, 2018
Carlo Ciliberto. Lorenzo Rosasco, and Alessandro Rudi. A consistent regularization approach for structured prediction. In Advances in neural information processing systems, pp. 4412-4420, 2016.
Carlo Ciliberto, Francis Bach, and Alessandro Rudi. Localized structured prediction. In Advances in Neural Information Processing Systems, pp. 7299-7309, 2019.
Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12:1501-1536, 2011.
Nicholas FitzGerald, Julian Michael, Luheng He, and Luke Zettlemoyer. Large-scale QA-SRL parsing. ACL, pp. 2051-2060, 2018.
Benjamin Guedj. A primer on pac- eac-bayesian learning, arXiv preprint arXiv:1901.0535. 2019.
Suchin Gururangan, Ana Marasović, Swabha Swayamdipta, Kyle Lo, Beltagy, Doug Downey, and Noah A. Smith. Don't stop pretraining: Adapt language models to domains and tasks. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp- July 2020.
Hangfeng He, Qiang Ning, and Dan Roth. QuASE: Question-Answer Driven Sentence Encoding. In Proc. of the Annual Meeting of the Association for Computational Linguistics (ACL), 2020.
Dirk Hovy and Eduard Hovy. Exploiting partial annotations with em training. In Proceedings of the NATCL-HHLT Workshop the Induction of Linguistic Structure, pp. pp 31-38, 2012.
10

---

Under review as a conference paper at ICLR 2021
Eduard Hovy, Mitch Marcus, Martha Palmer, Lance Ramshaw, and Ralph Weischedel. Ontonotes: the 90% solution. Proceedings of the human language technology conference of the NAACL, Companion Volume: Short Papers, pp. 57-60, 2006.
Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zettlemoyer. TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. In Proceedings the 55th Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1601-1611. Association for Computational Linguistics, July 2017.
Brendan Juba. Estimating relatedness via data compression. In Proceedings of the 23rd international conference on Machine learning, pp. 441-448, 2006.
Daniel Khashabi, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Hannaneh Hajishirzi. UnifiedQA: Crossing format boundaries with a single qa system. arXiv preprint arXiv:2005.00700, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optmizztion. ICLR, 2015.
Alexander Kolesnikov, Xiaohua Zhai, and Lucas Beyer. Revisiting self-supervised visual represen- tation learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recog- nition, pp. 1920-1929, 2019.
John Lafferty, Andrew McCallum, and Fernando CN Pereira. Conditional random fields: Proba- bilistic models for segmenting and labeling sequence data. 2001.
Omer Levy, Minjoon Seo, Eunsol Choi, and Luke Zettlemoyer. Zero-shot relation extraction via reading comprehension. In CoNLL, pp. 333-342, 2017.
Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complexity and its applications, vol- ume 3. Springer, 2008
Liping Liu and Thomas Dietterich. Learnability of the superset label learning problem. Interna- tional Conference on Machine Learning, pp. 1629-1637, 2014.
Nelson Liu, Matt Gardner, Yonatan Belinkov, Matthew E Peters, and Noah A Smith. Linguistic knowledge and transferability of contextual representations. In Proceedings of NAACL-HLT, pp- 1073-1094, 2019.
Ben London, Bert Huang, and Lise Getoor. Stability and generalization in structured prediction. The Journal of Machine Learning Research, 17(1):7808-788 7859, 2016.
MM Mahmud and Sylvian Ray. Transfer learning using kolmogorov complexity: Basic theory and empirical evaluations. In Advances in neural information processing systems, pp. 985-992, 2008.
Andreas Maurer. A note on the PAC-Bayesian theorem. arXiv preprint cs/04/ 1099, 2004.
Stephen Mayhew, Snigdha Chaturvedi, Chen-Tse Tsai, and Dan Roth. Named Entity Recognition with Partially Annotated Training Data. In Proc. of the Conference on Computational Natural Language Learning (CoNLL), 2019.
David McAllester. Simplified pac-bayesian margin bounds. In Learning theory and Kernel ma- chines, pp. 203-215. 2003a.
David McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual confer- ence on Computational learning theory, pp. 164-170, 1999a.
David A McAllester. Some PAC-Bayesian theorems. Machine Learning, 37(3):35--33,, 1999b.
David A McAllester. Pac-hayesian stochastic model selection. Machine Learning, 51(1):5-21, 2003b.
Julian Michael, Gabriel Stanovsky, Luheng He, Ido Dagan, and Luke Zettlemoyer. Crowdsourcing question-answer meaning representations. NAACI, 2017.

---

Under review as a conference paper at ICLR 2021
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in neural information processing systems, pp. 1196-12044 2013.
Qiang Ning, Hangfeng He, Chuchu Fan, and Dan Roth. Partial or Complete, That's The Ques- tion. In Proc. of the Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), 2019.
Sinno Jialin Pan and Qiang Yang. survey on transfer learning. IEEE Transactions on knowledge and data engineering, 2(10):1345-1355 2009.
Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Jason Phang. Thibault Févry, and Samuel R Bowman. Sentence encoders on STILTs: Supplemen- tary training intermediate labeled-data tasks. arXiv preprint arXiv:1811.010S: 2018.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383-2392, 2016.
Lance A Ramshaw and Mitchell P Marcus. Text chunking using transformation-bussed learning. In Natural language processing using very large corpora, pp. 157-176. Springer, 1999.
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning robust to massive label noise. arXiv preprint arXiv: 10694, 2017.
Dan Roth. Incidental Supervision: Moving beyond Supervised Learning. In Proc. of the Conference Artificial Intelligence (AAAI), 2017.
Dan Roth and Wen-tau Yih. A linear programming formulation for global inference in natural lan- guage tasks. Technical report, ILLINOIS UNIV AT CERBANA-CHAMPALNN DEPT OF COM- PUTER SCIENCE, 2004.
Dan Roth and Dmitry Zelenko. Towards a theory of Coherent Concepts. In Proc. of the Conference on Artificial Intelligence (AAAI), pp. 639-644, 2000.
Erik Tjong Kim Sang and Fien De Meulder. Introduction to the conll-2003 shared task: Language- independent named entity recognition. In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003, pp. 142-147, 2003.
Matthias Seeger. PAC-Bayesian generalisation bounds for gaussian process classification. Journal of machine learning research, 330c)):333-269 2002.
Benjamin Strauss, Bethany Toma, Alan Ritter, of the wnutl6 named entity recognition shared task. In Proceedings of the 2nd Workshop on Noisy User-generated Text (WNUT), pp. 138-144, 2016.
De Marneffe, and Wei Xu. Results
Sebastian Thrun and Joseph Sullivan. Clustering learning tasks and the selective cross-task trans- fer of knowledge. In Learning to learn, pp. 235-257. Springer, 1998.
Adam Trischler, Tong Wang. Xingdi Yuan, Justin Harris, Alessandro Sordoni, Philip Bachman, and Kaheer Suleman. NewsQA: A machine comprehension dataset. In Proceedings of the 2nd Workshop on Representation Learning for NL.. pp. 191-200. Association for Computational Lin- guistics, August 2017.
Leslic G Valiant. A theory of the learnable. Communications the ACM, (7(11):1134-111 1984.
Brendan Van Rooyen and Robert C Williamson. A theory of learning with corrupted labels. The Journal of Machine Learning Research, ((1)):85018855)) 2017.
12

---

Under review as a conference paper at ICLR 2021
Vladimir Vapnik and Akshay Vashist. A new learning paradigm: Learning using privileged infor- mation. Neural networks, 22(5-6):544 -54, 2009.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events their probabilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Boyu Wang, Jorge Mendez, Mingbo Cai, and Eric Eaton. Transfer learning via minimizing the performance gap between domains. In Advances in Neural Information Processing Systems, pp- 10645-10655, 2019.
Kaifu Wang, Qiang Ning, and Dan Roth. Learnability with indirect supervision signals. arXiv preprint 20X/v:2006.08791, 2020.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, R' e'mm Louf, Morgan Funtowicz, and Jamie Brew. Huggingface's 's trans- formers: State-of-the-ane natural language processing. ArXiv, abs/1910.03771, 2019.
Tong Zhang al. From e-entropy to Kl--entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 34(5):2100-2200, 2006.
Xiaofeng Zhu, Feng Liu, Goce Trajcevski, and Dingding Wang. Frosting weights for better continual training. In 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA), pp. 510. IEEE, 2019.
13

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 PARI IN THE PAC FRAMEWORK
Suppose '² is not over C, is uniform C and To is uniform over č (xI( In | and (xz(= (1ā0) in Cl. It follows that
We have
(KL
In [C] In C
(TT, mo)
S(C,2).
At the same time, we have
H (
H
In Č
(To mu)
In [ - S(C,2).
(mro
In |C|
Therefore, in the non-probabilistic cases with the finite concept class, the three informativeness measures are equivalent as:
S(uu, #b) = (To. to) = SC,
The equivalence among three measures further indicates that both PAST and the approximation of PART are reasonable.
A.2 INFORMATIVENES, MEASURES IN PARAMETRIC CONCEPT CLASS
In practice, algorithms are often based on parametric concept class. The two informativeness mea- sures in the PAC-Bayesian framework, S(To, To) and S( To). can be easily adapted to handle the cases in parametric concept class. Given parametric space C.. we can easily change the probability distribution x xCC..) over the parametric concept class to the probability distribution rCC) over the finite concept class C {c : 1d - C") by clustering concepts in the parametric space according to their outputs on all inputs. The concepts in each cluster have the same outputs on all inputs as outputs of one concept in the finite concept class C. We then merge
probabilities of concepts in the same cluster to get the probability distribution (C) over the finite concept class C. This merging approach can be applied to any concept class which is not equal to the finite concept class C, includ- ing non- parametric and semi-pane cemi-parametric concept class. In practice,
sampling algorithms, such as Markov chain Monte Carlo (MCMC) methods, to simulate this clustering strategy.
A.3 LIMITATIONS OF INFORMATIVENESS MEASURES
Different informativeness measures based on different assumptions, analyze their limita- tions in detail to understand their limitations applications.
For the informativeness measure S(C,O) .) cannot handle probabilistic signals or infinite concept classes. There various probabilistic incidental signals, such soft constraints and probabilis- tie co-occurrences between an auxiliary task and the main task. An example of probabilistic co- occurrences between part-of-speech (PoS) tagging and NER is that the adjectives have 95% prob- ability to have the label O in NER. As for the infinite concept class, most classifiers are based on infinite parametric spaces. Thus, S(c, C) cannot be applied to these classifiers.
The informativeness measure S(T 7o) is hard be computed for some complex cases. In practice, we can use the estimated posterior distribution over the gold data, which is asymptotically unbiased,
to estimate it. Another approximation is to use the informativeness measure = / H()))
((t)
However, is not directly linked to the generalization bound, so more work is needed to guarantee its reliability for some complex probabilistic cases. We postpone to provide the theoretical guarantees
for S
H(mp) on more complex cases as our future work.
H(mo)
A.4 LOWER BOUND IN THE PAC FRAMEWORK
In the following theorem, show that the VC dimension (size of concept class) also plays an important role in the lower bund for the generalization error, indicating that PABI based on the reduction of the concept class is reasonable measure.
14

---

Under review as a conference paper at ICLR 2021
Theorem A.I. Let C be concept class with VC dimension d > 1. Then, for any 2 1 and any learning algorithm A. there exists a distribution 'D over and a target concept с E C such that
d d-1
PS-DM (Ro(s))
2 1/100
32m
where es is a consistent concept with S returned by A. This is the Theorem 3.20 in Chapter 3.4 of Mohri al. (008)).
A.5 DISCUSSION OF SOME OTHER FACTORS IN PABI
In this subsection, we consider the impact of the following factors in PABI: base model perfor- mance, the size of incidental signals, data distribution, algorithm and cost-sensitive loss.
Base model performance. In the generalization bound in both PAC and MAC-Bayesian, we can see that the relative improvement in the generalization bound from reducing C is small if m is large. In practice, the relative improvement the real improvement with some noise. Therefore, we can that the real improvement is dominant if m is small and the noise is dominant if is large. Therefore, PABI may not work well when m is large and when the performance on the target task already good enough.
The size of incidental signals. Our previous analysis is based on a strong assumption that incidental signals are large enough (ideally m - 00). A more realistic PABT is based on Ć with i examples as C)
In C. Ia
In Cm m. x In Cm In
v(1 In cm
la Cm
In
C
In C.
[n]e
In In 1C la (
In In|CT where C.n denotes the restricted concept class of C on the m examples,
and does Ca. Note that the ratio of the intrinsic information in incidental signals is indepen- In In|
In [n|Ca. = in è2
in CI holds for our signals. For example, In [.mll |n|Ca
dent of the size m, so partial data with unknown ratio 7p. doesn't depend the size m. (I) When m is large enough, S(C,ū)= = provement is independent of m because In | is the same constant for different incidental signals. Our experiments are based on this case and does not really rely on the assumption that incidental signals are large enough. (3) The incidental signals we are comparing are not large enough and have
Tpp for
In [Cl (2) When the sizes of different incidental signals are all m, the relative im- In CT
T to incorporate that difference. We can replace | with some reasonable M, e.g. the largest size of incidental signals, make PABI in larger range of values in [0, 1]. In future, we need to explore more in this direction.
different sizes, we need to use C(C,C) = =V(1- Inici x lale
mi
Data distribution. As for the distribution of examples, both PAC and PAC-Bayesian are distribution-free (see more in Chapter 2.1 of MMhri et al. (2018)). However, if we consider the joint distribution between examples and labels, such imbalanced label distribution, the situation will be different. Specific types of joint data distribution refer to restricted concept class C'. There- fore, PABI is expected to work well if the reduction from is similar to the reduction from C' with
incidental signals, ie. C(C',C')
In
[
C
Algorithm. Different algorithms make different assumptions on the concept class. For example, SVM aims to find the maximum maximum-margin hyperplane (see more Chapter 5.4 Mohri al. (0118). Therefore, a specific algorithm actually is based on restricted concept class C" (e.g. concepts with margin in SVM case). Similarly, PABI is expected to work well if the reduction from C is similar the reduction from C' with incidental signals. We also cannot compare the benefits from various incidental signals with different algorithms. the algorithm is not expressive enough to take advantage of incidental signals, may also not be able to use PABI there.
Cost-sensitive Loss. For different loss functions other than 0-1 loss, there are still some similar generalization bounds in PAC and PAC- PAC-Bayesian (using complexity of concept class and sample size) (Bartlett et al., 2006 CClibbrroo et al., 2016). Therefore, PABI can also be used (possibly with some minor modifications) for cost-sensitive loss functions.
15

---

Under review as a conference paper at ICLR 2021
k-gram
8
word-pos 8.68
49.45
84.08
96.22
98.96
99.54
99.69
99.73
99.75
99.76
word-ner 27.65
76.23
92.98
98.04
99.37
99.74
99.84
99.88
99.89
99.90
pos-ner 0.20
6.65
13.78
25.36
41.50
60. 14
77.04
88.61
95.01
97.92
ner-pos
0.00
0.01
0.03
0.07
0.17
0.39
0.80
1.47
2.45
3.71
Table 2: K-gram co-oceurrence analysis for PoS and NER in the whole Ontonotes dataset. For example, word-pos represents the percentage k-gram words that have the unique k-gram PoS labels.
Relative Improvement
0.8
0.6
+
0.4
+
0.2
+
0
0.65
0.7
0.75
0.8
0.85
Informativeness
Figure 4: The correlations between the informativeness and the relative performance improvement for NER with cross-sentence constraints.
A.6 MORE EXAMPLES WITH INCIDENTAL SIGNALS
In this subsection, we show more examples with incidental signals, including within-sentence con- straints, cross-sentence constraints, auxiliary labels, cross-lingual signals, cross-modal signals, and the mix of cross-domian signals and constraints.
Within-Sentence Constraints. As for within-sentence constraints, we show three types of common constraints NLP, which are BIO constraints, assignment constraints, and ranking constraints.
BIO constraints are widely used in sequence tagging tasks, such as NER. For BIO con- straints, I-X must follow B-X or I-X, where "X" is finer types such PER (person) and LOC (location). We consider simple case here: there are only B, I, O three labels. We have In [ V 1r (In +n 1)+2)
(n-m+1)
m ) | )""
for the BIO constraint. There-
In +1 [(441)2] m
)m]
fore, ST # = S(To, #o) = S(C,C)
In 21
This value can be approximated by the dynamic programming as Ning et al. (201)).
Assignment constraints can be used in various types of semantic parsing tasks, such as semantic role labeling (SRL). Assume we need assign agents with d' tasks such that the agent nodes and the task nodes form bipartite graph (without loss of generality, assume
d < d'). Each agent is represented by feature vector in V,. We have S( #o) =
S(T., tt) = S(C, = / in
d d' This informativeness doesn't 't rely the choice of V, where that V, denotes discrete feature space for arguments.
ln|
V In (Μ)
16

---

Under review as a conference paper at ICLR 2021
Ranking constraints can be used in ranking problems, such as temporal relation extraction. For a ranking problem with items, there are d = f(t - 1)/2 pairwise comparisons in total. Its structure is chain following the transitivity constraints, i.e., if A < B and B < C,
then A C. In this way, we have S(To, mo) (TT. mo) S(C,2) V
l in c|
In el 2
V
2lmt-2 This informativeness doesn't rely on the choice of V (11))m2
where y denotes discrete feature space for events.
Cross-sentence Constraints. For cross-sentence constraints, we consider a common example, global statistics based on 2-tuple of tokens, i.c. pairs of tokens in different sentences must have the same labels. We can group words into K groups with probability p. In this way, we have (TT, at) = V1 p plpppppp--------ppppp pppp-pppppppplp (1-(1pp)) (11p))ln([]))) ("I""""""""""""""""""""""""""""" --1"""--111) Es vT. The approxi-
Iu eT
mation holds as long as CI, V. and n are not all too small. For example, as shown in Table 2 the percentage of 5-gram words with unique NER labels is 99.37, so ideally the corresponding PABI will be v0.9937 0.9968. It is worthwhile to note that the k-gram words with unique labels can also be caused by the low frequency of the appearance of the k-grams. In our experiments, we only consider the k-grams with unique labels that appear at least twice in the data. We experiment on NER with three types of cross-sentence constraints: uni-gram words with unique NER labels, bi-gram words with unique NER labels, and 5-gram part-of-speech (PoS) tags with unique NER The results are shown in Fig.
label [I]
Auxiliary labels. For auxiliary labels, we show two examples follows:
For a multi-class sequence tagging task, we use the corresponding detection task as aux- iliary signals. Given a multi-class sequence tagging task with C' labels in the BIO format (Ramshaw & Marcus 1999). we will have labels for the detection and 2C + labels for
the classification. Thus, S(TO, Ho) S(mo, ão) S(C,C) / is the percentage of the label O among all labels.
(1-p.) In In(20+1)
where Po
Coarse-grained NER for Fine-grained NER. We have four types, PER, ORG, LOC and MISC for CoNLL NER and 18 types for Ontonotes NER. The mapping between CoNLL NER and Ontonotes NER is as follows: PER (PERSON), ORG (ORG), LOC(LOC, FAC, GPE), MISC(NORP. PRODUCT, EVENT, LANGUAGE). O(WORF OF ART, LAW, DATE, TIME, PERCENT, MONEY, QUANTITY, ORDINAL, CARDINAL, O) (Augen- stein al. 2017). In the BIO setting, we have S mo) = S(To, ão)
S(C,C)
Pt In P.. 4+ In 19, where Pl, Pms Po are the percentage of LOC(includigg B- 37
LOC and I-LOC), MISC (including B-MISC and I-MISC), and O among all possible la- bels.
Note that PABI is consistent with the entropy normalized mutual information (see more in footnote 8 because SiTO #o)
Y for auxiliary labels.
H(Y
Cross-lingual signals. For cross-lingual signals, we can use multilingual BERT to get è in the extended input space (VUV")). After that, 7/ and 7/2 can be computed accordingly.
Cross-modal signals. For cross-modal signals, we only consider the case where labels of gold and incidental signals are same and inputs of gold and incidental are aligned. A common situation is that a video has visual, acoustic, and textual information. In this case, the images and speech related to the texts be used cross-modal information. We use cross-modal mapping between speech/images and texts (e.g. Chung et al. (2018) to estimate the ? and 7/2 for cross-modal signals.
The mix of cross-domain signals and constraints. Let ē denote the perfect system on cross-domain signals and satisfying constrains on inputs of gold signals, and denote the model trained on cross- domain signals and satisfying constraints on inputs of gold signals. In this way, we can estimate y) and 172 by forcing constraints in their inference stage.
Here we use PoS tags as special type of cross-sentence constraints by specifying the labels of tokens whose PoS tags have unique NER labels, although PoS tags can also be viewed auxilary signals for NER.
17

---

Under review as a conference paper at ICLR 2021
A.7 DERIVATION OF EQUATION 44
For simplicity, use Y to denote c(x). Y to denote ē(x), and Y to denote (x). We then write the definitions of 77. 1/1 and ?22 n = xx Px (((x) + e(x)) = P(Y + Y), n/ PxxxPo(x) ((((x)= o ē(x)) = p( * Y) and ?/2 = Px()) (((x) & c(x)) = P( + Y). Note
that L is the label set for the task. Considering all three systems in the target domain, we have
p( Y)
72
p(Й =
-PL -Y)P(Ý =Y - p(Ý * r) 4Y)
= =P( = =Y)P(Y- = 8) P( * Y) P(L+X)
-1
(1 11 T/i +
-
-1)rf ml)
Therefore, we have 7) T- 1-12 7
A.8 PABI FOR TRANSDUCTIVE SIGNALS
Assumption I: ē(x) is noisy version of c(x) with noise ratio in both target and source domain: # č(x)).
Exx (c(xx) + ε(x)) = Ex-Py (x)
(((xx) (x)
Theorem A.2. Let C be concept class of VC dimension d for hinary classification. Let S+ be a labeled sample of size m. generated by drawing 3m points (S) from 'D according to c and (1 -B)m points (S) from D (the distribution of incidental signals) according to ē. If e' = arargging min R (c) arg millee 1/2 [R((c) + 1 Rg(e)) and cj arg min.ee RD(c) is the target error minimizer, c* arg min Rp(c) + RD(c) the joint error minimizer, under assumption I, and assume that C is expressive enough so that both the target error minimizer and the joint error minimizer can achieve zero ervors, then for any 8 (0, 1),
is the empirical joint error minimizer,
with probability at least 1 5,
2d
2em
+ 2ln
(e' S + 4
1 B
A concept is a function c: X + (0, The probability according to the distribution D that concept e disagrees with labeling function f (which can also be a concept) defined as
Ro(c, FxxD[[<(x) - [(x)[]
(5)
Note that here E(y, c(x)) ly-ly--le c(x) is the loss function and (t((c) Ex~D [f(y, c(x)) where the gold label for We denote R,(c)) (a E [o, 1) the corresponding weighted combination of true source and target errors, measured with respect to D and D follows:
Ra(c) aRD(c) (1 Rp(c)
Lemma A.3. Let c be concept in concept class C. Then
Ra(e) - Ro(c)) < (1 - aA + T(c))
where Rp(c') + RD(c*), c² arg mineee Rz(c)) + RD(c), and T(C) (R Rp(c, c.)]
Proof.
(c) Rc(c)
= (1 R2(() (c) Rp(c)]
S (1 - a:) (c)(c) - Ro(c,c") + RD(c,(") - Rolc, e²)l (Ro(c [
< (1 a)) [Rp(')) + cRl(, Ro(c, Ro(c")]
= (1 - ((((())
18

---

Under review as a conference paper at ICLR 2021
Lemma A.4. For fixed concept c from C with VC dimension d. if random labeled sample (S+) of size is generated by drawing 3m points (S) from D and (1 33mm points (S) from D, and labeling them according to fo and fo respectively, then for any 5 E (0,1) with probability at least 1 - 8 (over the choice of the samples),
a²
(1 (1-a) a)2 2d In
2em d
In $
(C)(c) R a (c) S 2 B + 1-3
m
where Rs aas (c) + (1 Rg(c) and is the natural number.
Proof. Given Lemma 5 in Ben-David et al. 2010), which says for any 8 E (0, 1), with probability
1- - (over the choice of the samples),
2mm
P[|Rs - Ra(c) 2 c) S exx
22
(1-a)a
1-p
According to the Vapnik-Chervonenkiss theory Vaannik & Chervonenkis 2015). we have with prob- ability 6,
a²
(1 - a)²
2d 2am 21n
R. (c) - Rs, (a)) < 2
2/
+
d
3
1 3
m
This is the standard generalization bound with an adjust term 3.3 of Mohri et al. 2018)).
[1-a)
(see more in Chapter
Proof of Theorem
A.2
Let 2. then e = arg min (a) (Rg(c) + Rs(c))
(2) < (c' + +1 (1-11100) (A + =(²)) (Lemma A.3)
2 (t) + (1 (A + (R c²) Ro(C', cc))) (Definition of 7(2))
3 (C)) + (1 (1- a) + (2' + RR((c)) + Rx((') + RD(c"))
s Ra((') + (1 ()AA (2))
(3 (83-2a) Ra + a)A
a2
(1
)2
2d In 2em + 2 In &
S (3 (R) (t') + 2
B
1 3
m
+ +211 - a)A (Lemma A.4
with 8/2)
a
(1 a)2
2d In
2em d
+ 2 In 8
<3 (3- 20) (c7) + +2
+
B
1- 3
+1 -0--0 a)A (C' = arg min Rs_.a(c))
a²
(1
a2
2d In 2em
+ In &
< 20) +
3
1
3
m
+21 - a)A (Lemma A.4
with 8/2)
a
(1 (1- (1-a)2
2d In 2cm + 2
(3 - (RD((( 41
+
+ +1- + +(())))
3
1- 3
+2(1 a)A (Lemmal A.3)
< 20) 4 a2 (1 a1)
2d 2cm + 21
1 V
m
+2aa² - 7a +5455 + (2a² -5a + +3)((c7)
Note that
r(7)) [Rb(G, (-)- RD(ct, e²) 5/5 RB( = (G) Rb(())
19

---

Under review as a conference paper at ICLR 2021
Therefore,
Ro(2) S Rg(()) + 4
1
2d
2cm d + 2ln
8
+ +3RD(c))
(a )
B
m
Also note that L1 loss is equivalent to 0-1 loss in the binary classification, so that RT(c))) = under assumption I. addition, assuming that C is expressive enough so that both the target error minimizer and the joint error minimizer can achieve zero errors (Rp(cT) = 0 and A = 0), the generalization bound can be simplified as follows:
1 1
20m 2d
+ 21n
RD(c') +
+
d
B
Note that the proof of Theorem A.2 similar to Theorem 3 in David et al. (2100) Our theorem is based on binary classification mainly because the error item in Eq. (5) based on the LI loss will be equivalent zero-one loss for binary classification. Although for multi-class classification, the L1 loss is different from commonly used zero-one loss, Theorem A.2 also indicates the relation between the generalization bound of joint training and the cross-domain performance Rp(c3) (equal to (c(ct) under assumption I). Furthermore, a multi-class classification task can be represented by a series of binary classification tasks. Therefore, we postpone more accurate analysis for multi-class classification as our future work.
A.9 DETAILS OF EXPERIMENTAL SETTINGS
In this subsection, we briefly highlight some important settings in our experiments and more details can be found in our submitted code.
NER with individual inductive signals. For partial labels, we experiment on NER with four differ- ent partial rates: 0.2, 0.4, 0.6, and 0.8. For noisy labels, we experiment on NER with seven different noisy rates: 0.1 0.7. For auxiliary labels, we experiment on two auxiliary tasks: named entity detection and coarse NER (CoNLL annotations with 4 types of named entities (Sang & De Meulder p.03
NER with mixed inductive signals. A more complex case is the comparison between the mixed inductive signals. For the first type of mixed signals, we experiment on the combination between three unknown partial rates (0.2, 0.4, and 0.6) and four noisy rates (0.1, 0.2, 0.3, and 0.4). As for the second type of mixed signals, we experiment on the combination between the BIO constraint and five unknown partial rates (0.2, 0.4, 0.6, 0.8, and 1.0).
NER with various inductive signals. After we put the three types of individual inductive signals and the two types of mixed inductive signals together, we still see a correlation between PABI and the relative performance improvement in experiments in Fig. 2(f).
NER with cross-domain signals Because we only focus on the person names, a lot of sentences in the original dataset will not include any entities. We random sample sentences to keep that 50% sentences without entities and 50% sentences with least one entity. 7)1 and 7/2 is computed by using sentence-level accuracy.
QA with cross-domain signals. For consistency, we only keep one answer for each question in all datasets. Another thing worthwhile to notice is that the most informative QA dataset is not always the same for different main QA datasets. For example. for NewsQA, the most informative QA dataset is SQuAD, while the most informative QA dataset for SQuAD is QAMR.
Experimental settings for learning with various inductive signals. The 2-layer NNs we use in CWBPP (algorithm I has hidden size of 4096, ReL. non-linear activation and cross-entrops loss. As for the embeddings, we use 300 dimensional Glove embeddings (Pennington et al.) 2014). The size of the training batch is 10000 and the optimizer is Adam (Kingma & Ba 2015) with learning rate 3e -4 When we initialize the classifier with gold signals (line 1), the number of training epochs is 20. After that, conduct the bootstrapping 5 iterations (line 3-7). The confidence for predicted labels is exactly the predicted probability of the classifier (line 5). In each iteration of bootstrapping, further train the classifier on the joint data epoch (line 7).
20

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Confidence- Weighted Bootstrapping with Prior Probability. The algorithm utilizes incidental signals to improve the inference stage semi-supervised learning.
Input: A small dataset with gold signals D = (Xi, Yi), and large dataset with inductive signals (X2, Y2) where X1 n X_22 = &
Initialize claissifier é LEARN(D) (initialize the classifier with gold signals)
P(Y2|X2 Y2) = PRIOR(D, D) (estimate the probability of gold labels for inputs D) while convergence criteria not satisfied do
Y INFERENCE(X2: é; X2, Y2)) (get predicted labels of inputs in D)
P = CoNFIDENCH(X::d, X2, Y2)) (get confidence for predicted labels)
D (X2, Y, P) (get confidence confidence-weightedd incidental dataset with predicted labels) à LE D) (learn classifier with both gold dataset and incidental dataset)
return Ć
Notations
Descriptions
D
target domain with gold signals
D
source domain with incidental signals
c(x)
gold system on gold signals
č(x)
perfect system on incidental signals
c(x)
silver system trained on incidental signals
difference between the perfect system and the gold system in the target domain difference between the silver system and the perfect system in the source domain difference between the silver system and the perfect system in the target domain difference between the silver system and the gold system in the target domain
7h
1/1
1/2
Table 3: Summary of core notations in the estimation process for transductive signals.
the pre- trained case-insensitive BERT-base pytorch implementation (Wolf et al. 2019). We use the common parameter settings for our experiments. Specifically, for NER, the max length is 256, batch size is 8, the epoch number is 4 and the learning rate is 55 As for QA, the max length is 384, bath size 16, the epoch number is 4, and the learning rate 5e -5
Experimental settings for learning with cross-domain signals. As for BERT,
A.10 THE CWBPP ALGORITIIM
The CWBPP algorithm is shown in Algorithm T
A.11
SUMMARY OF NOTATIONS THE ESTIMATION PROCESS FOR TRANSDUCTIVE SIGNALS
The summary of core notations in the estimation process for transductive signals is in Table
21


Reviews:
[{"review_id": "lrCxMJ9PX-C", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The use of PAC-Bayes theory for NLP tasks is rare. Although I know little on NLP, the paper proposition to leverage on  PAC-Bayes for evaluating the benefit of various incidental supervision signals seems promising. However, even if the empirical results are good, the connection between PAC-Bayes and the proposed informativeness measure (named PABI) is vague. The paper needs to better situate the proposed analysis compared to classical PAC-Bayesian generalization risk bounds.\n\n**Section 2 contains many assertions that are questionable.**\n1. *\"The training samples [are] generated i.i.d.\"*: It is the case for most PAC-Bayes analysis, but I wonder to which extent this assumption holds for the NLP problems studied as experiments. In a sentence, words are highly dependent on each other.\n2. *\"In the common supervised learning setting, we usually assume the concept that generates data comes from the concept class\"*: This is a surprising claim as the **PAC**-Bayes framework differs from the Bayesian one namely by the fact that we usually don't need to make assumptions about the data-generating distribution other than being i.i.d. In particular, the model does not need to be well specified. This makes me wonder if PABI would not better fit in the purely Bayesian framework (see other comments below).\n3. *\"the generalization bounds in both PAC-Bayesian and PAC frameworks have the square root function\"* : There exist several forms of the PAC-Bayes theorem in the literature, not only the square root ones (e.g., Seeger 2002). In fact, the square root bounds are not the tightest, particularly when the model is well specified.\n**Is PABI really backed by PAC-Bayes theory?**\nAs far as I understand, the procedure PABI is only remotely inspired by the PAC-Bayes bound,  but is not truly justified by it. No PAC-Bayes bounds are fully optimized; PABI borrows from PAC-Bayes the sole idea of relying on the KL between distribution. For this reason, I think that the introduction sentence \"Previous attempts are either not practical or too heuristic\" is harsh, because the proposed method turns out to be a heuristic too.\n\n**Is PABI a more Bayesian method than a PAC-Bayes one?**\nI wonder if one could not do the same analysis in a fully Bayesian setting, maximizing a Bayesian information criterion. This should be appropriate since PABI and the Bayesian setting assume that the model is well specified. Note that there is a direct link between the Bayesian Marginal Likelihood and the PAC-Bayes generalization bound (e.g., Germain, et al., 2016: \"PAC-Bayesian Theory Meets Bayesian Inference.\")\n\nOverall, I think that the paper explores a new and exciting territory, but needs a deeper analysis to support the connection with the PAC-Bayes theory.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MPyUxej_rG6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n#### Summary\n\nThis paper proposes a unified measure for the informativeness of incidental signals (ie, not standard ground truth supervised labels) derived from the PAC-Bayesian theoretical framework. Instantiations of the score are derived for a variety of these signals, and experiments show good agreement between the measure and true performance improvements.\n\n#### Strong and weak points\n\nThis problem setting is well-positioned as complementary to the growth in \"alternative supervision\" in both research and industry. Besides the directions identified in the paper, one could easily imagine using this kind of a measure in ML applications as a tool to help guide economic decisions about what kinds of datasets or annotations to pursue. The explanatory potential of this approach with respect to observed gains using incidental signals is exciting as well, especially the agreement with empirical findings from Mayhew 2019.\n\nI found Figure 1 to give helpful context, and I found the core technical content in Section 2 to be clear and precise.\n\nThe experimental results were a bit intricate to follow. A key result is Figure 2f and the associated correlations, which show strong correlation between the PABI scores and true performance improvements, this could perhaps be higlighted or emphasized more. Likewise the meaning of Figure 3 is a bit obscured by the poor correlations of the\nbaselines.\n\nOne weakness of the evaluation was that, while the Related Work coverage seemed sufficient, only Gururangan 2020 is included in the experiments. Of course the other approaches have the limitations well-captured in Table 1, but it would have been nice to have some restricted experiments crafted in order to give direct comparisons.\n\nThe supplemental appendix was comprehensive with respect to theoretical derivations and experimental details. \n\n#### Recommendation (accept or reject) with one or two key reasons for this choice.\n\nI would recommend to accept, the work represents an advance across both theory and practice on an important problem.\n\n#### Supporting arguments\n\nThe work leverages a well-studied framework to answer important questions about understanding the utility of non-standard supervision signals, enabling us to reason in a unified way about varied kinds of these signals as well as their combinations. Experimental results\n\n\n#### Questions to clarify / additional evidence required\n\nThe approximation in Definition 2.2 was a little strange for me, and seemed kind of circular: for calculating our approximate PABI, we are approximating the target (gold) distribution with our approximatively improved prior ($\\tilde{pi_0}$)? Is there anything we can say about how good/accurate this approximation is?\n\nSection 3.2: \"much cheaper\" - how or why would we say this is true, can we quantify it? Or are there cites to see?\n\nIs it possible to frame the PABI measures in terms of testable hypotheses about true generalization error, or are the bounds too loose in practice to say anything meaningful here?\n\n#### Additional feedback to improve\n\nSpace permitting, a small diagram of the mappings between different domains and the restrction trick would make Section 3.2 much clearer. Another possibility is some symbol table to keep straight which versions of $c()$ correspond to gold vs silver, incidental, etc.\n\nThe code was great to see as well but is missing dependencies:\n\n- seqeval\n- tqdm\n- transformers\n\nI might suggest adding a requirements.txt or similar.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Gn3_Bi66Lan", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary: \nThis paper proposes a unified PAC-Bayesian-based informativeness measure (PABI) to quantify the value of incidental signals. PABI can measure various types of incidental signals such as partial labels, noisy labels, constraints, auxiliary signals, cross-domain signals, and their combinations. In NER and QA tasks, they showed the strong correlation signals between PABI and the relative improvements for various incidental signals. \n##########################################################################\nReasons for score: \n \nOverall, my score is marginally below than acceptance threshold. \nPros:\n1. I enjoyed reading the paper, and I like the idea of covering various types of supervision signals at one unified measure. \n2. The definition and approximation of PABI and its generalization to different inductive signals look sound to me.\n \nCons: \n \n1. My biggest concern about this paper is the lack of clarity and presentation. In the introduction, I do understand how conceptually PABI is different from others, but do not know what it is. It would be better describing how PABI works in the introduction, Also, it would be better understanding the Section 2 and 3, if authors provide high-level insights of why each part of PABI’s description is important. Similarly, in the experiment, it was quite difficult to follow the text and capture the main claim. For instance, it would be better to understand if how Figure 2 and 3 should look like first and what trends of the points support the main claim of PABI, etc. Similarly, visual interpretation without specific guidelines make Figure 3 really difficult to understand. I guess some quantitative numbers would be very helpful like the linear regression slope, etc. \n \n2.  Besides the presentation, I don’t quite understand how PABI can be used as a practical measure for other applications. Does the strong correlation with relative improvement mean that it can be used as an alternative measure of mutual information and further applied to other applications using such information measures in their optimization? If so, it would be nice to describe potential applications of these measures and other benefits of PABI in general. This also requires additional experiments that show its effectiveness in other applications. \n\n#########################################################################\nSome typos:\na widely used measure for for noisy signals -> a widely used measure for noisy signals\nthe SQuAD dataset servers as the main dataset -> the SQuAD dataset serves as the main dataset\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8nM23j0OJjT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes PABI (PAC-Bayesian Informativeness?), a way of measuring and predicting the usefulness of “incidental supervision signal” for a downstream classification task. In particular, when labeled data is only available in noisy or partial form, or over a different domain than the target test domain, this data may still be used to improve a classifier, but it’s unclear how to tell which forms of incidental supervision will be most useful. Having a measure which allows us to compare different types of such supervision enables us to make intelligent tradeoffs.\n\nPABI is proposed as a very general framework. The most general form of the measure, dealing with updates to the concept class prior, seems that it could capture any kind of incidental supervision. However, this means most of the work is in understanding how to apply and approximate it. This paper provides several such methods, particularly focusing on “inductive” learning (from constraints or partial/noisy gold labels) or “transductive” learning (from complete gold labels on different input domains). Mathematical developments of PABI are given for these cases, and experiments show that PABI is nicely positively correlated with the relative improvement that comes with various methods for integrating incidental supervision signal (including one which is developed as a side note by the authors).\n\nComputing PABI may be challenging in some cases. In the case of transductive learning, it seems that a model needs to be trained on the incidental signal, although this is better than the combinatorial explosion of jointly trained models that would be required to test relative improvements directly. However, it’s not clear if efficient approximations for PABI will be feasible in all cases. This and other questions about the breadth of application of PABI are left for future work.\n\n### Strengths\n\nI think this paper is very well-motivated, situates itself well with respect to previous work, and presents clear advantages. Having a unified framework for comparing the utility of different kinds of incidental supervision signals seems potentially very useful, especially these days when incidental supervision of various sorts is instrumental in state-of-the-art models. It is also extremely relevant for data annotation and task design, which often has to make tradeoffs between these factors (i.e., noise versus partial annotation or dataset size).\n\nThere is a lot of content in this paper, including mathematical developments, algorithms, and experimental results. While I did not carefully check the proofs in the appendix, and I am not familiar with PAC-Bayesian theory or the associated literature, the paper seems technically sound to me.\n\n### Weaknesses\n\nWhile the generality of the proposed PABI framework is great and improves over existing work, I think this paper could be scoped more carefully and the scope could be clarified better.\n\nAs proposed, the PABI framework seems very general—which is good. But the paper only shows how to realize the framework in a couple specific cases, for “inductive” and “transductive” learning independently. This is still more general than previous work, but from the first few pages of the paper I was expecting something even more general.\n\n* It seems to me that the combination of inductive and transductive learning may be possible using something close to the paper's proposed methods , but this isn’t addressed by the paper except a glancing mention in Footnote 6.\n* It also is not clear to me from the paper’s text whether something close to the PABI framework can apply in broader settings like language modeling style pretraining, where the input-output format of the incidental supervision signal is different than that of the target task. In particular, it seems that in this case the approximation method proposed for transductive learning would indeed have to reduce to training a combined model. Related issues were finally mentioned briefly in the last paragraph of the paper, and something along these lines appears in appendix A.3, but I think a more up-front clarification of the limitations is warranted.\n\nMore broadly, the question in the back of my head when I began reading the paper was if this would help explain why and when language model pretraining (and other more flexible related-task pretraining) works well. The paper points to related work in this area, such as Gururangan et al 2020 (“Don’t Stop Pretraining”), leading me to think this paper would shed light on the issue, but in the end the issue was not mentioned and seems perhaps out of scope.\n\nThis is fine. All I would ask of the authors is to be more explicit about the limitations of PABI (or the proposed realizations of it) from the beginning, laying out the scope of this work and stating the limitations outright instead of only pointing to the appendix. It seems to me like PABI is more of a foundational framework which is ideal for future work to build into, rather than already being a general solution in itself. I think it would be best to pitch the paper this way.\n\n### Recommendation\n\nAccept. Important problem, lots of solid content, clear benefits over previous work and directions for the future. Great work.\n\n### More comments/questions\n\nI think the point of the formulation in Section 2.2 can be made a bit more explicit. It seems like the point is for applying PABI to partial labels. If that’s true (or there’s more to it) then might as well just say it there, or at least give this case as a motivating example.\n\nRegarding the cross-domain results: why are the incidental supervision sets so small? It seems that there is a ton more incidental supervision available for NER, and in both cases the incidental supervision data is even smaller than the test set. Why not use more? It seems to me that the use case here is when a large amount of incidental supervision is available anyway. It also seems like the low-data setting is not totally fair to the vocabulary overlap baseline.\n\n### Typos, style, etc.\n\nWhen describing your experiments, I think it’s worth mentioning that they are on English text.\n\nFigure 3: I don’t understand which numbers correspond to which model in the caption. This would be much easier to read in a table.\n\n* P. 7: something’s wrong with “twitter(Strauss et al., 2016)”\n* P. 7: The FitzGerald et al 2018 dataset is called “QA-SRL Bank 2.0”.\n* P. 7: servers -> serves\n* P. 7: “the lower bound for is”\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper first makes the observation that incidental supervisory data can be used to define a new prior from which to calculate a PAC-Bayes generalization guarantee.  This observation can be applied to any setting where there is unsupervised or semi-supervised pre-training followed by fine-tuning on labeled data.  The PAC-Bayes bound is valid when applied to the fine-tuning.  For example, one could use an L2 bound (derived from PAC-Bayes) on the difference between the fine-tuned parameters and pre-trained parameters.

But the paper proposes evaluating the value of pre-training before looking at any labeled data. Let $\pi_0$ be the prior before unsupervised or semi-supervised training and let $\tilde{\pi}$ be the prior after pre-training.  The paper proposes using the entropy ratio $H(\pi_0)/H(\tilde{\pi})$ as a measure of the value of the pre-training.  As the reviewers note, this is not really related to PAC-Bayes bounds.  Furthermore, it is clearly possible that the pre-training greatly focuses the prior but in a way that is detrimental to learning the task at hand.

I have to side with the reviewers that feel that this is below threshold.
Decision: Reject