Creating Training Sets via Weak Indirect Supervision
Authors: Jieyu Zhang
Bohan Wang
Xiangchen Song
Yujing Wang
Yaming Yang
Jing Bai
Alexander Ratner
Venue: ICLR 2022 Poster (2022)
Keywords: weak supervision
data programming
training label synthesis

Abstract: Creating labeled training sets has become one of the major roadblocks in machine learning. To address this, recent Weak Supervision (WS) frameworks synthesize training labels from multiple potentially noisy supervision sources. However, existing frameworks are restricted to supervision sources that share the same output space as the target task. To extend the scope of usable sources, we formulate Weak Indirect Supervision (WIS), a new research problem for automatically synthesizing training labels based on indirect supervision sources that have different output label spaces. To overcome the challenge of mismatched output spaces, we develop a probabilistic modeling approach, PLRM, which uses user-provided label relations to model and leverage indirect supervision sources. Moreover, we provide a theoretically-principled test of the distinguishability of PLRM for unseen labels, along with an generalization bound. On both image and text classification tasks as well as an industrial advertising application, we demonstrate the advantages of PLRM by outperforming baselines by a margin of 2%-9%.

Published as a conference paper at ICLR 2022
CREATING TRAINING SETS VIA WEAK INDIRECT SUPERVISION
Jieyu Zhang!.2 Bohan Wang Xiangehen Song', Yujing Wang', Yaming , ,Jing Bai', Alexander Ratner2.5
Microsoft Research Asia University of Washington
University of Science and Technology of China
*Carnegie Mellon University Snorkel AI, Inc.
(jieyuz2, ajratner) hww.r//css......tt..........a washington edu (yujwang, yayaming, jbai 100 cmmicrosftt.com com wbhfy@maill wuw.uuucc.o edu.cn xi sianchhensnggeeme coannngemmuuuu.mmmmmmmm cmm.edu
ABSTRACT
Creating labeled training sets has become one of the major roadblocks in machine learning. To address this, recent Weak Supervision (WS) frameworks synthesize training labels from multiple potentially noisy supervision sources. However, existing frameworks are restricted to supervision sources that share the same output space as the target task. To extend the scope of usable sources, we formulate Weak Indivect Supervision (WIS), a new research problem for automatically synthesizing training labels based on indirect supervision sources that have different output label spaces. To overcome the challenge of mismatched output spaces, we develop a probabilistic modeling approach, PLRM, which uses uscr-provided label relations to model and leverage indirect supervision sources. Moreover, we provide a test of the distinguishability of PLRM for unseen labels, along with a generalization bound. On both image and text classification tasks as well as an industrial advertising application, we demonstrate the advantages of PLRM by outperforming baselines by margin of 2%-9%.
INTRODUCTION
One of the greatest bottlenecks of using modern machine learning models is the need for substantial amounts of manually- labblle training data. In real-world applications, such manual annotations are typically consuminn,,, aabor-intensive and static. To reduce the efforts of annotation, researchers have proposed Weak Supervision (WS) frameworks (Ratner et al., 2016; 2018; 2019; Fu et al., 2020) for synthesizing labels from multiple weak supervision sources, e.g., heuristics, knowledge bases, pre-trained classifiers. These frameworks have been widely applied various machine learning tasks (Dunnmon et al., 2020; Fries et al., 2021; Safranchik ct al., 2020; Lison et al., 2020; Zhou al., 2020; Hooper et al., 2021; Zhan al., 2019; Varma al., 2019) and industrial data (Bach et al., 2019). Among them, data programming (Ratner et al., 2016), one representative example that generalizes many approaches in the literature, represents weak supervision sources labeling functions (LFs) and synthesizes training labels using Probabilistic Graphical Model (PGM).
Given both the increasing popularity of WS and the general increase in open-source availability of machine learning models and tools, there is a rising tide of available supervision sources that WS frameworks and practitioners could potentially leverage, including pre-trained machine learning models or prediction APIs (Chen et al., 2020; d' Andrea & Mintz, 2019; Yao et al., 2017). However, existing WS frameworks only utilize weak supervision sources with the same label space as the target task. This incompatibility largely limits the scope of usable sources, necessitating manual effort from domain experts to provide supervision for unseen labels. For example, consider target task of classifying ("dog", "wolf", "catt, "lion") and set of three weak supervision sources (e.g. trained classifiers or expert heuristics) with disjoint output spaces ("caninae". "felidae"), ("domestic animals", "wild animals") } and | ""usky"", "bengal car") respectively. We call these types of sources indirect supervision sources. For concreteness, we follow the general convention programming (Ratner et al., 2016) and refer these sources as indirect labeling functions (II.F)).

---

Published as a conference paper at ICLR 2022
Despite their apparent utility, existing weak supervision methods could not directly leverage such ILFs, as their output spaces have no overlap with the target one.
In this paper, we formulate novel research problem that aims to leverage such ILFs automatically, minimizing the manual efforts to develop and deploy new models. We refer to this as the Weak Indirect Supervision ( (WIS) setting, new Weak Supervision paradigm which leverages ILFs, along with the relational structures between individual labels, to automatically create training labels.
The key difficulty of leveraging ILFss is due to the mismatched label spaces. To overcome this, introduce pairwise relations between individual labels to the WIS setup, which are often available in structured sources (e.g. off-the-shelf Knowledge Bases (Miller, 1995; Sinha et al., 2015; Dong et al., 2020) or large scale label hierarchies (Murty et al., 2017; The Gene Ontology Consortium, 2018; Partalas et al., 2015) for various domains), or can be provided by subject matter experts in far less time than generating entirely new sets of weak supervision sources. For example, in the aforementioned example, we could rely on a biological species ontology to see that the unseen labels "dog" and "caf"" are both subsumed by the seen label "domestic animals". Based on the label relations, we can automatically leverage the supervision sources as ILFs. Notably, previous work (Qu et al., 2020) also leveraged label relation graph but was focused on relation extraction task in few-shot learning setting. while You et al. (2020) proposed to learn label relations given data for each label in transfer learning scenario. In contrast, aim to solve the target task directly and without clean labeled data.
The remaining questions are (1) how synthesize labels based on pair-wise label relations and ILFs? and (2) How can we know whether, given a set of ILFs and label relations, the unseen labels are distinguishable or not? To address the first question, we develop a probabilistic label relation model (PLRM), the first PGM for WIS which aggregates the output of ILFs and models the label relations as dependencies between random variables. In turn, we use the learned PLRM produce labels for training an end model. Furthermore, we derive the generalization error bound of PLRM based on assumptions similar to previous work (Ratner et al., 2016).
The second question presents an important stumbling block when dealing with unseen labels, as we may not be able to distinguish the unseen labels given existing label relations and ILFs, resulting in an unsatisfactory synthesized training set. To address this issue, we formally introduce the notion of distinguishability
WIS setting and theoretically establish an equivalence between: (1) the distinguishability of the label relation structure as well as the ILFs, and (2) the capability of PLRM to distinguish unseen labels. This result then leads to a simple sanity test for preventing the model from failing to distinguish unseen labels. In preliminary experiments, observe significant drop in model performance when the condition is violated.
In experiments, make non-trivial adaptations for baselines from related settings the new WIS problem. On both text and image classification tasks, we demonstrate the advantages of PLRM over adapted baselines. Finally, in commercial advertising system where developers need to collect annotations for new ads tags, we illustrate how to formulate the training label collection as a WIS problem and apply PLRM to achieve effective performance.
Summary of Contributions. Our contributions are summarized as follows:
We formulate Weak Indirect Supervision (WIS), a new research problem which synthesizes training labels based on indirect supervision sources and label relations, minimizing human efforts of both data annotation and weak supervision sources construction;
We develop the first model for WIS, the Probabilistic Label Relation Model (PLRM) with comparable statistical efficiency to previous WS frameworks and standard supervised learning:
We introduce a new notion of distinguishability in WIS setting, and provide a simple test of the distinguishability of PLRM for unseen labels by theoretically establishing the connection between the label relation structures and distinguishability;
We showcase the potential of the WIS formulation and the effectiveness of PLRM in a commercial advertising system for synthesizing training labels of new ads tags. On academic image and text classification tasks, we demonstrate the advantages of PLRM over baselines by quantitative experiments. Overall, PLRM outperforms baselines by margin of 2%-9%.
2

---

Published as a conference paper at ICLR 2022
2 RELATED WORK
Table 1: Comparisons between the proposed weak indirect supervision (WIS) and related machine learning tasks. Compared to normal and weakly supervised learning, WIS handles mismatched train and test label spaces, WIS is similar in spirit to indirect supervision (IS) and zero-shot learning (ZSL), but distinct in that WIS only takes as input weak or noisy labels and simple set of logical label relations, and aims to output a training data set rather than trained model, affording complete modularity in which final model class is used.
Task
Label Type
Virain Veet
Label Information
When Label Info, is Required
Supervised Learning (SL.)
Clean I ahels
/
Weak Supervision (WS)
Noisy Sources
Indirect Supervision (IS)
Clean Labels
Label Trans. Matrix Label Embed. / Attribute
Training Training & Test Training
Zero-Shot Learning (ZSL.)
Cleun Labels
Weak Indirect Supervision (WIS)
Noisy Sources
Label Relation
We briefly review related settings. The comparison between WIS and related tasks is in Table 1.
Weak Supervision: We draw motivation from recent work which model and integrate weak supervi- sion sources using PGMs (Ratner et al., 2016; 2018; 2019; Fu et al., 2020) and other methods (Guan et al., 2018; Khetan et al., 2018) to create training sets. While they assume supervision sources share the same label space as the new tasks, we aim to leverage indirect supervision sources with mismatched label spaces in a labor-free way.
Indirect Supervision: Indirect supervision arises more generally in latent-variable models for various domains (Brown et al., 1993; Liang et al., 2013; Quattoni et al., 2004; Chang al., 2010; Zhang et al., 2019). Very recently, Raghunathan et al. (2016) proposed to use the linear moment method for indirect supervision, wherein the transition between desired label space Y and indirect supervision space O is known, as well as the ground truth of indirect supervisions for training. In contrast, both are unavailable in WIS. Theoretically, Wang al. (2020) developed a unified framework for analyzing the learnability of indirect supervision with shared or superset label spaces, while we focus on disjoint label spaces and the consequent unique challenge of distinguishubility of unseen classes.
Zero-Shot Learning: Shro-Shot Learning (ZSL) (Lampert et al., 2009; Wang et al., 2019) aims to learn a classifier that is able to generalize to unseen classes. The WIS problem differentiates from ZSL by (1) in ZSL setting, the training and test data belong to seen and unseen classes, respectively, and training data is labeled, while for WIS, both training and test data belong to unseen classes and unlabeled: (2) ZSL tends to render classifier that could predict unseen classes given certain label information, e.g., label attributes (Romera-Pareed Paredess & Torr, 2015), label descriptions (Srivastava et al., 2018) or label similarities (Frome et al., 2013), while WIS aims to provide training labels for unlabeled training data, allowing users to train any machine learning models, and the label relations are used only in synthesizing training labels.
3 PRELIMINARY: WEAK SUPERVISION
We first describe the Weak Supervision (WS) setting. A glossary of notations used is in App. A.
Definitions and notations. We assume a k-way classification task, and have an unlabeled dataset D consisting of m data points. Denote by X; E A' the individual data point and Y; E y = {v1,.... ys. the unobserved interested label of X;- We also have n sources, each represented by a labeling function (LF) and denoted by Az. Each X; outputs a label Y E Vi,- = [o ..., f } on X,, where Vx, the label space associated with X, and [Da,, kxy- We denote the concatenation of LFs' output as Y (Ý,', V.?. YT", and the union set of LFs' label spaces as y with | = k. Note that & is not necessarily equal to the sum over kX,+ since LFs may have overlapping label spaces. We call ÿ E 5 seen label and y E y desired labels. In WS settings, we have y C ÿ.. Notably, we assume all the involved labels come from the same semantic space.
The goal of WS. The goal is to infer the training labels for the dataset D based on LFs, and to use them to train an end discriminative classifier fw X - Y, all without ground truth training labels.
3

---

Published as a conference paper at ICLR 2022
Bengal Cat
Cat
Canine
Felicee
Domnetic Animale
Wild Animals
Husky
Bengal Cat
Domestic Animal
Felidae
Dog
Wild Animal
det Labeling cuiet coture Jabe:
BeE Lubeling PUAMS SOGAUT 1abel
det sape:log POLN:: zecara 1abal
Canine
Wolf
Husky
An
Label Graph
Indirect Labeling Functions
Cat
Input
Lion
Dog
20" 95
Wolf
Unlabeled Data
Label Model
Probabilistic Labels
End Model
Figure 1: An example of WIS problem: the input consists of an unlabeled dataset, a label graph, and indirect labeling functions (ILFs). The ILFs represent weak supervision sources such pretrained classifiers, knowledge bases, heuristic rules, etc. We can see that the ILFs cannot predict desired labels Le., ("dog", "wolf", "cat", "lion"). To address this, label graph is given; here we only visualize the subsuming relation. Finally, a label model, instantiated as a PGM, takes the ILFSs outputs and produces probabilistic labels in the target output space, which are in turn used train an end machine learning model that can generalize beyond them.
4 WEAK INDIRECT SUPERVISION
Now, we introduce the new Weak Indirect Supervision (WIS) problem. Unlike the standard WS setting, we only have indirect labeling functions (ILFs) instead of LFs, and an additional label graph is given. The goal of WIS remains the same as WS. An example of WIS problem is in Fig. 1.
Indirect Labeling Function. In WIS, we only have indirect labeling functions (ILFs), which cannot directly predict any desired labels, i..., 5 n 0. Therefore, we refer the desired labels unseen labels. To make it possible to leverage the ILFs, label graph is given, which encodes pair-wise label relations between different seen and unseen labels.
Label Graph. Concretely, label graph G = (V.E) consists of (1) set of all the labels as nodes, i.e.
== -UU and (2) set of wair label relations typed edges, i.e., E {3H, Yo tw,,, It Vy. yy V}. Here, is the set label relation types and, similar to Deng et al. (2014), there are four types of label relations: exclusive, overlapping, subsuming, subsumed, notated by to, ,,te, 1.t,,,% ,,9,,"** respectively. Notably, for any ordered pair of labels (ys: Vý). their label relation should fall into one of the four types. The rationale behind these label relations is that when treating each label as a set, there are four unique set relations and each corresponds to one defined label relation respectively as shown Fig. For convenience, we denote the of non-exclusive neighbors of given label y in D as N(y )), ie.. Vy iύ- Vit + t²).
Label relation:
Exclusive A 1
Subsumnng
Subsummed A S 11
Overiap An O.A & H.N Z
Set relation:
2 #
B
B
Figure 2: The one-to-one mapping between label relations and relations.
5 PROBABILISTIC LABEL RELATION MODEL.
One of the key difficulties in both WS and WIS is that we do not observe the true label Y. Following prior work (Ratner et al., 2016; 2019; Fu al., 2020), Model (PGM) for estimating Y, based on the Y, output by ILFs. Specifically, the PGM is instantiated
latent variable Probabilistic Graphical
4

---

Published as a conference paper at ICLR 2022
factor graph model. This standard technique lets us describe the family of generative distributions in terms of M known dependencies/factor functions {ő), and an unknown parameter è E R as Po(+) exp(() (-))), where & is the concatenation of {Ø}. However, the unique challenge for WIS is that the dependencies {Ø} between Y; and Y, are unknown due to the mismatches of label spaces. We overcome these by leveraging the label graph G to build the dependencies for the PGM.
5.1 A BASELINE PGM FOR WIS
In prior work (Ratner al., 2016; Bach et al., 2017), the PGM for WS is governed by accuracy dependencies:
(5 = 1(Y = Y = y)
which is defined for each X, and E Vi, ny. However, in WIS, the ILFs cannot predict desired label y E V. As simple baseline approach to start, we leverage the coarse-grained xxclusivenoon-exclusee
label relation to build a corresponding "accuracy" factor. Specifically, for an ILF X, and one label E Vx, given a desired label y y. if 9 and y have non-exclusive label relation, i.e., ÿ E (y, we expect a certain portion of data assigned ý should be labeled as y. Thus, we treat y D as a pseudo indicator of Y = y and add a pseudo accuracy dependency between them:
Ace (V, V) == 1(y = yyy y = 0}
We call the PGM governed by pseudo accuracy dependencies Weak Supervision with Label Graph (WS-LG). Notably, it can be treated as a simple adaptation of PGM for WS (Ratner et al., 2016; 2019; Fu et al., 2020) to the WIS problem. However, such naive adaptation might have two drawbacks:
1. It does not model specific dependencies ILFss with different undesired labels. For example, two ILFs outputting "Husky" and "hulldog" respectively would be naively modeled the same as they both output "Dog".
2. It can only directly model exclusive/non-exxlusiv label relations, ignoring the prior knowledge encoded in other relation types, i.e., subsuming, subsumed, or overlapping. For example, given an unseen label "Dog" and some ILFs outputting "Husky" or "Domestic Animals", WS-LG would treat all ILFs as indicators of "Dog". However, we know a "Husky" of course a "Dog" (subsumed relation) while "Domestic Animals" is not necessarily "Dog" (subsuming relation).
5.2 PROBABILISTIC LABEL RELATION MODEL
To more directly model the full range and nuance of label relations, we propose a new probabilistic label relation model (PLRM). In PLRM, explicitly model both (1) the dependency between ILF outputs and the true labels in their output spaces, i.e. their direct accuracy, and (2) the dependencies between these labels and the target unseen labels, as separate dependency types, thus explicitly incorporating the full label relation graph into our model and learning its corresponding weights.
Concretely, we augment the WS-LG model with (1) latent variables representing the assignment of the data to each seen label, and (2) label relation dependencies which capture fine-grained label relations between these output labels and desired labels. To model seen label in J. we introduce binary latent random vector Y [ ..... f'., where y indicating whether the data should be assigned St Then, for ILF X, that could predict ÿt, we have accuracy dependency:
2 (Y' 1d) 1 1( = 1 9:}
To model fine- ame-grained label relations, for a desired label y E y and seen label f E Ô. we add label relation dependencies. We enumerate the label relation dependencies corresponding to the four label relation types, i.e., exclusive, overlapping, subsuming. subsumed, as follows:
= (V, = - =1}
(Y,8) = 1(Y = =y = 1}
(Y,8") = -11 y^ A yd =1}
(V,") - =0)
5

---

Published as a conference paper at ICLR 2022
The above dependencies encode the prior knowledge the label relations, but also allow the model to learn corresponding parameters. For example, an exclusive label relation dependency of outputs -I when two exclusive labels are activated at the same time for the same data, otherwise O, which reflects our prior knowledge of the exclusive label relation; and the corresponding parameter can be treated as the strength of the label relation. Likewise, for any pair of seen labels, we add label relation dependency following the same convention. Finally, we specify the model as:
Pe OY,,Y, exp (0,,
Recall that Y is the unobserved true label, Y is the binary random vector, each of whose binary value Y reflects whether the data should be assigned seen label ús and Y is the concatenated outputs of ILFs.
Learning Objective. We estimate the parameters θ by minimizing the negative log marginal likelihood Pe(Y) for observed ILF outputs fı:m:
arg min
- log Σ P.))
(2)
Y.Y
We follow Ratner et al. (2016) to optimize the objective using stochastic gradient descent.
Training an End Model. Let Pe (Y Y) be the probabilistic label (i.c. distribution) predicted by learned PLRM. We then train an end model fw :X y parameterized by W, by minimizing the empirical noise-aware loss (Ratner al., 2019) with respect to Ô over unlabeled data points:
m
W arg min
Σ
E ( fW,
(118
where E(Y, fw(f)()) is standard cross entropy loss.
Generalization Error Bound. We extend previous results from (Ratner et al., 2016) to bound both the expected error of learned parameter é and the expected risk for W. All the proof details and description of assumptions can be found Appendix.
Theorem 1. Suppose that we run stochastic gradient descent to produce and W based on Eqs. (2) and (3), respectively, and that setup satisfies certain assumptions (App D.2). Let [D] be the size of the unlabeled dataset. Then we have
0-1 s
log D
DP... E [ -(w)))(w)))))) s sx+0
log [D] [D]
H
Interpreting the Bound. By Theorem 1, the two errors decrease by the rate O(I/DD) and ((1/DD|1/2) respectively as [D] increases. This shows that although we trade computational effi- ciency for the reduction of human efforts by using complex dependencies and more latent variables, we maintain comparable statistical efficiency as previous WS frameworks and supervised learning theoretically.
DISTINGUISHABILITY OF UNSEEN LABELS
One unique challenge of WIS is that there may exist pairs of unseen labels which cannot be distinguished by the learned model. For example, as shown in Fig. where "Dog" is seen label for which LFs could predict for and "Husky" and "Bulldog" are unseen labels for which we want to generate training labels; however, we could not distinguish between "Husky" and "Bulldog" make correct predictions of seen label "Dog". because both "Husky" and "Bulldog" share the same label relation to "Dog".
Deg
3.bsuming
though the LFs
Husky
Bulldog
Figure 3: Example of in- distinguishable unseen labels "Husky" and "Bulldog".
To tackle this issue, we theoretically connect the distinguishability of unseen labels the label relation structures and provide testable

---

Published as a conference paper at ICLR 2022
condition for the distinguishability. Intuitively, same label relation structures could lead to indistinguishable unseen labels as shown in Fig. 3; however, it turns out to be challenging to prove that different label relation structures could guarantee the distinguishabiiltty with respect to the model. To illustrate, we formally define the distinguishability as below.
Definition 1 (Distinguishabiltty). For any model Po(Y, U.Y,Y,Y Y) with parameters O any pair of unseen labels yi Mj E y are distinguishable w.r.t. the model, for a.e. θ > 0 (element-wisely), there does NOT exist such θ > 0 that, for NY, Y, the following equations hold
Po = -, 8) = PP((Y = V), Pa(Y = ,,, 8) = P ,I
(4)
Pe(Y -,
-,iV,),,,,Y. vy E )//
(5)
Po(P) = PP)
(6)
From the definition, we can see that the opposite of distinguishabblity, i.e. indistinguishabilit. describes an undesired model: for any learned parameter @ > O, we can always find another Q which optimizes the loss equally well (Eq. (6)), but Eqs. (4-5) implies whenever Pe predict ye Pe will predict y/ instead, which reflects that the model cannot distinguish the two unseen labels. Note that the notion of distinguishability is different from the identifiability in PGMs: the generic identifiability (Allman et al., 2015), the strongest notion of identifiability, requires the model to be identifiable up to label swapping, while the distinguishability aims to avoid the label swapping.
However, distinguishability is hard to verify since Eqs. (4-5) and (6) need to hold for any possible configuration of Y.ł. Y, and any pair of unseen labels. Fortunately, for the proposed PLRM, we prove that distinguishability is equivalent to the asymmetry of the label relation structures when two conditions hold. To state the required conditions, we first introduce the notations of consistency and informativeness to characterize the label graph and ILFs.
Consistency. We discuss the consistency of a label graph to avoid an ambiguous or unrealistic label graph. We interpret semantic labels Mo yh sets A, B, and then connect the label relations to the set relations (Fig. 2). Given the set interpretations, we define the consistency of label graph as:
Definition 2 (Consistent Label Graph). A label graph G = => is consistent if the induced set relations are consistent.
For example, assume y = (Ya. you y. and tab the tea t² From tab, the. we can observe that A 2 B 2 C, which contradicts to C' 2 A implied by tea = 1-9 Thus, G is inconsistent.
Informativeness. In addition, try to describe what kind of ILF is desired. Intuitively, an ILF is uninformative if it always "votes" for one of the desired labels. For example, if the desired label space is ("Dog". "Bird"), ), then for ILF ê₁ outputting ("Huusk"", "Bulldog"), we know "Dog" is non-exclusive to "Husky" and "Bulldog". while "Bird" exclusive to both. In such case, A can hardly provide information to help distinguish "Dog" from "Bird". because always votes for "Dog". On the other hand, a binary classifier of "Husky", i.e., X2, is favorable since it could output "Not a Husky" to avoid consistently voting for "Dog". We can see an undesired ILF always votes for single desired label. To formally describe this, we define an informative ILF as:
Definition 3 (Informative ILF),, An ILF Xy is informative if. for Vy E V, there exists X; E s.t. the output of X3 X; is not in (y, i.e., Y? $ &N,(y.,,))
Testable Conditions for Distinguishability. Based the introduced notations, we prove the necessary and sufficient condition for learned PLRM being able to distinguish unseen labels:
Theorem 2. For PLRM induced from a consistent label graph, as well as informative ILFs, for any pair of ye yj E y, they are indistinguishable, if and only if tis = for Vyk E V.
Theorem provides users with a testable condition: for any pair of unseen labels yes Uj. there should exist at least one seen label yı such that ye has different label relations to y and yj. i.e., ta + tsk so that PLRM is able to distinguish y/ and yj- In preliminary experiments, we observe the violation of this condition causes a dramatic drop in overall performance (about 10 points). Notably, based on Theorem 2, users could theoretically guarantee the distinguishability of a pair of unseen labels by adding only one seen label and corresponding II.Fs break the symmetry.
7

---

Published as a conference paper at ICLR 2022
7 EXPERIMENTS
We demonstrate the applicability and performance of our method on image classification tasks derived from ILSVRC2012 (Russakovsky et al., 2015) and text classification tasks derived from LSHTC-3 (Partalas et al., 2015). Both datasets have off-the-shelff label relation structure (Deng et al., 2014; Partalas et al., 2015), which are directed acyelic graphs (DAGS) and from which we could query pairwise label relations. Indeed, there is one-to-one mapping between DAG structure of labels and a consistent label graph (See App. E.1 for an example). The ILSVRC2012 dataset consists of 1.2M training images from 1,000 leave classes; for non-leave classes, we follow Deng et al. (2014) to aggregate images belonging to its descendent classes as its data points. The LSHTC-3 dataset consists of 456,886 documents and 36,504 labels organized in DAG.
7.1 SETUP
For each dataset, we randomly sample 100 different label graphs, each of which consists of 8 classes, and use each label graph to construct a WIS task. For each label graph, we treat 3 of the sampled classes as unseen classes and the other 5 as seen classes. The distinguishable condition in Sec. 6 is ensured for all the WIS tasks, and the performance drop when it is violated can be found in App. G.I. We sample data belonging to unseen classes for our experiments and split them into train and test set. For image classification tasks, we follow Mazzetto et al. (2021b;a) to train a branch of image classifiers supervision sources of seen classes. For text classification tasks, made keyword-based labeling functions as supervision sources of seen classes following Zhang et al. (2021); each of the labeling functions returns its associated label when a certain keyword exists in the text, otherwise abstains. Notably, all the involved supervision sources are "weak" because they cannot predict the desired unseen classes. Experimental details and additional results are App. F.
7.2 COMPARED METHODS AND RESULTS
In addition to the WS-LG baseline, which is adaptation of Data Programming (Ratner al., 2019) to WIS task, and PLRM, we also include the following baselines. Note that all compared methods input the same data, ILFs, and label relations throughout our experiments for fair comparisons.
Label Relation Majority Voting (LR-MV). We modify the majority voting method based on the label's non-exclusive neighbors: we replace 9 predicted by any ILF with the set of desired labels N(j,)), ie., the desired labels with non-exclusive relation to y, then aggregate the modified votes.
Weighted Label Relation Majority Voting (W-LR-MV). LR-MV only leverages exclusive/non- exclusive label relations. To leverage fine-grained label relations, W-LR-MV attaches weight to each replaced label. Specifically, if the ILF's output is replaced with its ancestor label y (subsumed relation), then the weight of y equals 1, while for the other relations, the weight is (
where
(") {y E (i))lt + tdd].
For the above methods, we compare the performance of (1) directly applying included models on the test and (2) the end models (classifiers) trained with inferred training labels.
Zero-Shot Learning (ZSL). It is non-trivial to apply ZSL methods, because ZSL assumes label attributes for all classes and a labeled training set of seen classes, while WIS input an unlabeled dataset of unseen classes, label relations and ILFs. Fortunately, the Direct Attribute Prediction (DAP) (Lampert et al., 2013) method able to make predictions solely based on attributes without labeled data, by training attribute classifier p(a.la (z) for each attribute a;, Therefore we include it in our experiments. The details of applying DAP can be found in App. F.2.
Evaluation Results. For a fair comparison, we fix the network architecture of the classifiers for all the methods. For image classification, we use ResNet-32 (He et al., 2016) and for text classification, we use logistic regression with pre-trained text embedding (Reimers & Gurevych, 2019). The overall results for both datasets can be found in Table 2. From the results, we can see that PLRM consistently outperforms baselines. The advantages of PLRM show the effect of not just leveraging the label graph, as the baselines do, but modeling the accuracy of ILFs and the strengths of label relations
8

---

Published as a conference paper at ICLR 2022
Table 2: Averaged evaluation results over 100 WIS tasks derived from LSHTC-3 and ILSVRC2012.
LSHTC-3
ILSVRC2012
Method
Accuracy
F1-score
Accuracy
F1-score
DAP
42,90 + 12.3
35.98 + 1533
33.25 +: 1.8
29.13 + 4.0
LR-MV
58.86 +
54.33 t 11:00
46.88
+
40.11
W-LR-MV
59.28 i
54.55 + 11.36
41.39
i
30.19
Label Model
WS-LG
62.60
57.50
+: 11:09
53.68
52.15 +
PLRM
64.65 11.30
60.01
13339
56.18
1.35
54.94 + 7:44
LR-MV
67.17 + 1225
62.49 + 13:6
49.60 + 12:00
42.83 + 16.17
W-LR-MV
66.57 + 11.33
61.80 + 13:44
42.61
+ 12.46
31.34 1: 15.20
End Model
WS-LG
70.69 + 1305
67.36 + 14.44
56.56 +:
54.57 + 11:37
PLRM
72.32 13:08
14.41
58.38
56.83 + 8:8
PLRM does. The reported results have high variance, which actually indicates the 100 different WIS tasks are diverse and have varying difficulty. Also, we can see the end models are much better than directly applying the label models the test set; this shows that the end models able to generalize beyond the training labels produced by label models.
7.3 REAL-WORLD APPLICATION
In this section, on commercial advertising system (CAS), we showcase how reduce human annotation efforts of new labeling tasks by formulating them as WIS problems. In a CAS, ads tagging (classification) is a critical upplication for understanding the semantics of ads copy. When new ads and tags are added to the system, manual annotations need to be collected for training a new classifier. As tags are commonly organized as taxonomies, the label relations between existing and new tags are readily available or can be trivially figured out by humans; Existing classifiers and the heuristic rules previously used for annotating existing tags could serve as IL.F. Therefore, given (1) an unlabeled dataset of new tags, (2) the label relations, and (3) ILFs, we formulate it as a WIS problem.
On such WIS formulation, we apply our method and baselines, to synthesize training labels of new tags. Specifically, we have two WIS tasks where the tags are under the "Car Accessories" and "Furniture" categories respectively. For both tasks, we have 3 new tags and leverage 5 existing tags related to the new ones with given relations. On test set, evaluate the performance of DAP and the quality of labels produced by label models, as shown in Table 3. Note that since we re-use the existing labeling sources tailored for existing tags ILFs and obtain label relations from an existing taxonomy, we achieve these results without any manual annotation or creation of new labeling functions. This demonstrates the potential of the proposed WIS task in real-world scenarios.
Table Evaluation on product tagging with new tags.
Category
Metric
DAP
LR-MV
W-LR-MV
WS-LG
PLRM
F1 50.62
68.68
68.06
66.85
76.37
Car Accessories
Accuracy
52.83
68.17
67.67
66.33
75.83
F1 30.81
64.70
61.45
70.59
80.57
Furniture
Accuracy
33.60
72.53
72.13
74.51
82,02
8 CONCLUSION
We propose Weak Indirect Supervision (WIS), a new research problem which leverages indirect supervision sources and label relations to synthesize training labels for training machine learning models. We develop the first method for WIS called Probabilistic Label Relation Model (PLRM) with the generalization eтrоr bound both PLRM and end model. We provide a theoreticalllypriiee sanity test to ensure the distinguishability of unseen labels. Finally, provide experiments to demonstrate the effectiveness of PLRM and its advantages over baselines on both academic datasets and industrial scenario.

---

Published as a conference paper at ICLR 2022
Reproducibility Statement. All the assumptions and proofs of our theory can be found in App. C D. Examples and illustrations of label graph are in App. E. Experimental details can be found in App. F. Additional experiments are in App. G.
REFERENCES
Elizaheth S Allman, John Rhodes, Elena Stanghellini, and Marco Valtorta. Parameter identifiability of discrete bayesian networks with hidden variables. Journal of Causal Inference, 3(2): 1000:889-055 2015.
Stephen H. Bach, Bryan He, Alexander J. Ratner, and Christopher Ré. Learning the structure of generative models without labeled data. In Proceedings of the 34th International Conference on Machine Learning (ICML 2017), Sydney, Australia, 2017.
Stephen H. Bach, Daniel Rodriguez, Yintao Liu, Chong Luo, Haidong Shao, Cassandra Xia, Souvik Sen, Alex Ratner, Braden Hancock, Houman Alborzi, Rahul Kuchhal, Chris Ré, and Rob Malkin. Snorkel drybell: A case study in deploying weak supervision at industrial scale. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD 119, pp. 362-375, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450356435. doi: 10.1 10.1145/3299869.3 1033.. URL https: doi org 10 / /2//////299988 3299869 .3...3311440 3314036.
Peter Brown, Stephen A Della Pietra, Vincent Della Pietra, and Robert Mercer. The mathematics of statistical machine translation: Parameter estimation. Computational linguistiiss, 19(2):263-3) 1993.
Weig Chang, Vivek Srikumar, Dan Goldwasser, and Dan Roth. Structured output learning with indirect supervision. ICML, pp. 199-206, 2010.
Lingjiao Chen, Matei Zaharia, and James Zou. Frugalml: How to use ml prediction apis more accurately and cheaply. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Carlos d' Andrea and André Mintz. Studying the live cross ploss-platform circulation of images with computer vision api: An experiment based on a sports media event. International Journal of Communication, 13(0), 2019. ISSN 1932-8036.
Jia Deng, Nan Ding, Yangqing Jia, Andrea Frome, Kevin Murphy, Samy Bengio, Yuan Li, Hartmut Neven, and Hartwig Adam. Large-scale object classification using label relation graphs. In European conference on computer vision, pp. 64. Springer, 2014.
Xin Luna Dong, Xiang He, Andrey Kan, Xian Li, Yan Liang, Jun Ma, Yifan Ethan Xu, Chenwei Zhang, Tong Zhao, Gabriel Blanco Saldana, et al. Autoknow: Self-driving knowledge collection for products of thousands of types. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 2724-2734 2020.
Jared A. Dunnmon, Alexander J. Ratner, Khaled Saab, Nishith Khandwala. Matthew Markert, Hersh Sagreiya, Roger Goldman, Christopher Lee-Messer, Matthew P. Lungren, Daniel Rubin, and Christopher Ré. Cross-modal data programming enables rapid medical machine learning. Patterns, 1(2):100019, 2020. ISSN 2666-3899, doi: www.ncceeattclee/e//ccee
2020. 100019. URL https: www. sciencedirect com/ 026666899203325 926663899203001999
Jason A Fries, Ethan Steinberg, Saelig Khattar, Scott L Fleming, Jose Posada, Alison Callahan, and Nigam Shah. Ontology-driven weak supervision for clinical entity classification electronic health records. Nature Communications, 12(1), 2021.
Andrea Frome, Greg S Corrado, Jon Shlens, Samy Bengio, Jeff Dean, Marc' Aurelio Ran- zato, and Tomas Mikolov. Devise: A deep visual-semantic embedding model. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Ad- vances in Neural Information Processing Systems, volume 26, pp. 2121-2129. Curran Asso- ciates, Inc., 2013. URL https: / http:////poooeccccceeeeees nww.ips........ cc httpppppp.c.ppppp/..//e//e////e/ 7Cc2335
10

---

Published as a conference paper at ICLR 2022
Daniel Y. Fu, Mayee F. Chen, Frederie Sala, Sarah M. Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and three-rious: Speeding up weak supervision with triplet methods. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020). 2020.
Melody Y. Guan, Varun Gulshan, Andrew M. Dai, and Geoffrey E. Hinton. Who said what: Modeling individual labelers improves classification. In AAAI, 2018.
K. He, X. Zhang. S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016. doi: 10.1 N0.1109/VPR.2016.909
Sarah Hooper, Michael Wornow, Ying Hang Seah, Peter Kellman, Hui Xue, Frederic Sala, Curtis Langlotz, and Christopher Re. Cut out the annotator, keep the cutout: better segmentation with weak supervision. In International Conference on Learning Representations, 2021. URL
https: //pereeie//eeevview net/ / forum?
Ashish Khetan, Zachary C. Lipton, and Anima Anandkumar. Learning from noisy singly-labeled data. In International Conference on Learning Representations, 2018. URL forum? id=H H1 sUHgloOZ.
Christoph H I Lampert, Hannes Nickisch, and Stefan Harmeling. Learning to detect unseen object classes by between-class attribute transfer. 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 951-958. IEEE, 2009.
Christoph H Lampert, Hannes Nickisch, and Stefan Harmeling. strribuee-bssed classification for zero- shot visual object categorization. IEEE transactions on pattern analysis and machine intelligence, 36(3):453-465, 2013.
Percy Liang, Michael I Jordan, and Dan Klein. Learning dependency- compositional semantics. Computational Linguistics, 39(2):389-445 2013.
Pierre Lison, Jeremy Barnes, Aliaksandr Hubin, and Samia Touileb. Named entity recognition without labelled data: A weak supervision approach. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 1518-1533, Online. July 2020. Association for Computational Linguistics. doi: 10.18653/w1/2020.coo 10.18653/11/2222.accmmmi. ac celweb... org/ antho lotholooyyy ogy / 2020 acl - in 139.
wwt.:00.cllmmmi...m 139. URL https: /www.
Alessio Mazzetto, Cyrus Cousins, Dylan Sam, Stephen H Bach, and Eli Upfal. Adversarial multi class learning under weak supervision with performance guarantees. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7534-7543, PMLR, 18-24 Jul 2021a. URL ml press vv1 v139//// ma www.zattzloolcc html.
httpss: http:///ooceddddeeeee/eo
Alessio Mazzetto, Dylan Sam, Andrew Park, Eli Upfal, and Stephen Bach. Semi-supervised ag- gregation of dependent weak supervision sources with performance guarantees. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artifi- cial Intelligence and Statisties, volume 130 of Proceedings of Machine Learning Research, pp. 3196-3204. PMLR, 13-15 Apr 2021b. URL https: /ttpe///oooceeeeeeeooooooooooe igg .ml.. prlls.press/vi3 mazzetto2la.htt htmll
George A Miller. Wordnet: lexical database for english. Communications of the ACM, 38(11): 39-41, 1995.
Shikhar Murty, Pat Verga, L. Vilnis, and A. McCallum. Finer grained entity typing with typenet. AKBC Workshop, 2017.
Ioannis Partalas, Aris Kosmopoulos, Nicolas Baskiotis, Thierry Artières, George Paliouras, Éric Gaussier, lon Androutsopoulos, Massih-Reza Amini, and Patrick Gallinari. LSHTC: benchmark for large-scale text classification. CoRR, abs/1503.08581, 2015.
Meng Qu, Tianyu Gao, Louis-Pasee Xhonneux. and Jian Tang. Few-shot relation extraction via bayesian meta-learnng on relation graphs. In International Conference on Machine Learning, pp. 7867-7876. PMLR, 2020.
11

---

Published as a conference paper at ICLR 2022
Ariadna Quattoni, Michael Collins, and Trevor Darrell. Conditional random fields for object recogni- tion. Advances in neural information processing systems, 17:1097-1104, 2004.
Aditi Raghunathan, Roy Frostig, John Duchi, and Percy Liang. Estimation from indirect supervision with linear moments. In International Conference Machine Learning (ICML), 2016.
A. J. Ratner, Christopher M. De Sa. Sen Wu, Daniel Selsam, and C. Ré. Data programming: Creating large training sets, quickly. In Proceedings of the 29th Conference on Neural Information Processing Systems (NIPS 20/6), Barcelona, Spain, 2016.
A. J. Ratner. B. Hancock, J. Dunnmon, F. Sala, S. Pandey, and C. Ré. Training complex models with multi-task weak supervision. In Proceedings of the AAAI Conference on Artificial Intelligence. Honolulu, Hawaii, 2019.
Alexander Ratner, Stephen H. Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the 44th International Conference on Very Large Data Bases (VLDB), Rio de Janeiro, Brazil, 2018.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019, URL https: aarxiviv... org. aa////////////// 1908. 10084.
Bernardino Romera-Paredes and Philip Torr An embarrassingly simple approach to zero-shot learning. In International conference on machine learning, pp. 2152-2161. PMLR, 2015.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. Imagenet large scale visual recognition challenge. Ini. J. Comput. Vision 115(3):211-252, December 2015. ISSN 0920-5691. doi: 10. 1..1007/111223--05-88166 URL https: /ttp://doo...ooo..o wttp:///....o..////////// s11263- 000-63--15---0 0816-016--6--11
Esteban Safranchik, Shiying Luo, and Stephen Bach. Weakly supervised sequence tagging from noisy rules. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp.
5570-5578, 2020.
Arnb Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Paul Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In WWW, 2015.
Shashank Srivastava, Igor Labutov, and Tom Mitchell. Zero-shot learning of classifiers from natural language quantification. In Proceedings of the 56th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 306-316, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/v 1/F5/3//1/111///// 8- 1029. URL https: // //www. wwwwwb.w.b.......... . org/ httpg//ntoooogy/o/oooooooooooo/t 1P299
The Gene Ontology Consortium. The Gene Ontology Resource: 20 years and still GOing strong. Nucleic Acids Research, 47(D1):D330-D338, 11 2018. ISSN 0305-1048. doi: 10.1093/nar/ gky1055. URL https: www.oooo..or..... 1093/ nar mgkgg55
Paroma Varma, Frederic Sala, Shiori Sagawa, Jason Alan Fries, Daniel Y. Fu, Saelig Khattar, Ash- wini Ramamoorthy, Ke Xiao, Kayvon Fatahalian, James Priest, and Christopher Ré. Multi- resolution weak supervision for sequential data. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-BBu, Emily B. Fox, and Roman Garnett (eds.), Ad- vances in Neural Information Processing Systems 32: Annual Conference tion Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 192-203, 2019. URL http::ttttttcteeeeeeeeeeee .nw.eeeeeddiinn.nnnnne.......... neurips cc/ accpaper/2201 9/hash/ html.
Neural Informa-
Kaifu Wang, Qiang Ning, and Dan Roth. Learnability with indirect supervision signals. Advances in Neural Information Processing Systems 32, 2020.
Wei Wang, Vincent W Zheng, Han Yu, and Chunyan Miao. A survey of zero-shot learning: Settings, methods, and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10 (2):1-37, 2019.
12

---

Published as a conference paper at ICLR 2022
Yuanshun Yao, Zhujun Xiao, Bolun Wang, Bimal Viswanath, Haitao Zheng, and Ben Y. Zhao. Complexity vs. performance: Empirical analysis of machine learning as a service. In Proceedings of the 2017 Internet Measurement Conference. IMC 17, pp. 384-397, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450351 188. doi: 00.1145/3111365511333333
URL https: /doi www.oorg./00. 111111011111311333
3131372.
Kaichao You, Zhi Kou, Mingsheng Long, and Jianmin Wang. Co-tuning for transfer learning.
Advances in Neural Information Processing Systems, 33, 2020.
Eric Zhan, Stephan Zheng, Yisong Yue, Long Sha, and Patrick Lucey. Generating multi-agent trajectories using programmatic weak supervision. In International Conference on Learning Representations, 2019. URL https: /ttp::://pppeee openreviev
Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang, Mao Yang, and Alexander Ratner. Wrench: A comprehensive benchmark for weak supervision. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
Yivan Zhang, Nontawat Charoenphakdee, and Masashi Sugiyama. Learning from indirect observa- tions, 2019.
Wenxuan Zhou, Hongtao Lin, Bill Yuchen Lin, Ziqi Wang, Junyi Du, Leonardo Neves, and Xiang Ren. Nero: A neural rule grounding framework for label-efficient relation extraction. The Web Conference, 2020.
13

---

Published as a conference paper at ICLR 2022
SUPPLEMENTARY MATERIALS FOR "CREATING TRAINING SETS VIA WEAK INDIRECT SUPERVISION"
The supplementary materials are organized as follows. In Appendix A, we provide a glossary of variables and symbols used in this paper. In Appendix B, provide the details of PLRM model. In Appendix C and D, we provide the detailed proof's of Theorem 2 and Theorem 1 respectively. In Appendix E, we provide the detailed examples and illustrations of label graph in WIS. In Appendix and G, we provide experimental details and additional experiment resulst respectively.
A GLOSSARY OF SYMBOLS
Table 4: Glossary variables and symbols used in this paper.
Symbol
Simplified
Used for
X;
The i-th data point, X; E A' Number of data points
m
Y
The true desired label of the i-th data point, Y; y A semantic label, e.g. "dog"
y
The set of desired labels, y {1/1 ,
Cardinality of V, i.e., k = |
The j-th Indirect labeling function (ILF)
Number of ILF
The output label of j-th ILF on i-th data point, Y. y
The concatenation ILFs' output, Y; = [ 12 pm]
A semantic label in the label space X
V
Label label space of ILF >, V/,, = {1 12 Miy }
kj
Cardinality of the output space of ILF X, i.e. kx = |2,11
Union set of all the Vxy. D
{ū) 02, ......... Úz)
Cardinality of the D, i.e,, 1
K
Total number of labels, i.e., K =
Vi
Latent binary variable indicating whether the data should be assigned ÿ: D. Concatenation of all latent binary variable, Y = [Y] .y.....,??" yk.
Y
Label graph, G ()) The set of label relations, & {(), Vj, (y,t,,y,) Muu E E J. Vy,, Vs E EV
E
T
The set of label relation types, T {1', 10, 10, 109] Exclusive label relation Overlap label relation
to
to
Subsuming label relation
ged
Subsumed label relation
N(y.S)
the set of non-exclusive neighbors of given label y in 5
A single dependency, or, factor function Concatenation all individual dependency Number of total dependencies
M
0
A single parameter of the PGM
θ
Concatenation of all parameters of the PGM, θ RM
θ
The learned parameters
The golden parameters
W
The parameter of an end model
W
The learned parameters
W
The golden parameters
14

---

Published as a conference paper at ICLR 2022
B DETAILS OF THE PLRM
We use Y, Y, and Y to represent random vector. Then, we give the formal form of the PLRM as:
Po(YY,,Y) exp (oT@(Y,Y,))
Recall that Y is the unobserved true label, Y is the binary random vector, each of whose binary value Y reflects whether the data should be assigned seen label DJ y, and Y is the concatenated outputs of ILFs. Specifically, we enumerate & as below:
1. (Pseudo accuracy dependency): Vj E [n], E V (//uukknou))) Vr,, we have
Sy (Y, 82) = 1(Y - y A 8 - A N(W.
2. (Accuracy dependency): : Vj E [n). 0 ) 0 3 we have
Acc ..j ()) = 1 1 A y = di}
3. (Label relation dependency between seen labels): Vûs D3 E E), <<j (a) if tg.0, = t², we have
b. (Y'))) - 118 118 =
(b) if 1g.0s 12, we have
(V, ")) = 1
(c) tgcd, to9, we have
Ba (Y', (2) = - 1112 0AY =
(d) t,o, tad we have
ad
(Y == Ù.
- -
= =0}
4. (Label relation dependency between desired and seen labels): Vy E 3/ [nkknowm] 9r E 5 (a) if tyg. t., have
- =
(b) if lyg: = t0, we have
"e (Y,8")= == 1(Y Sル , =1
(c) ly; = 199 we have
v. (Y,8*) = - 1(Y #リク
(d) yg. ted
we have
S (Y = = yyr''
And example of our PLRM is shown in Fig. 4, where square with difference colors corresond to different dependency/factor functions in PLRM.
Ralation Depembhitty Irue Accuary Dependency Pacado Accunacy Dependoncy
Figure 4: PLRM.
When & (g,,)))),)) dfte d'Ace is always zero and will not occur in the model. Here we use this form for the sack of rigorous representation.
15

---

Published as a conference paper at ICLR 2022
C PROOF OF THEOREM 2
C.I SIMPLIFYING THE NOTATION
To simplify the indexing of dependencies, we use Gh to represent the concatenation of which involves both and Y, dº to represent concatenation of & which involve both and Å, and $ to represent the concatenation of remaining & which do not involve Y.
Specifically, o² consists of k x & components corresponding to the dependency between the k desired labels and the seen labels. We use the subscript i. to denote the dependency function between the desired label yi and seen label Új, i.e.,
where the corresponding relation.
Similarly, 22 consists of k (Ej= ky) components corresponding to the dependency between the desired labels and the ky seen labels output by the ILF X5 (j [n]],, and we x $i denote the
dependency of yı and j/. and " ( ()),,)))= to denote the dependency of yı and g².
According to 11, Φ2, and $3, we also divide the parameter θ into O (with elements being O,,y ) correspondingly), and O3, and the correspondingly). è (with elements being 07 = (0 joint probability is then given as:
exp (0)))))((11))70000000000000000)1
Po Ey exp (6)) (") v1)) (8)
Also, for notation convenience, we adopt following simplifications:
1. Vy E Vi E [k] since |a = k. similarly, Vý: E E + vi E [ky] and Vy e + Vi
[k];
2. Vyy Vj [m] since we have ILFFs in total;
&g. where Luy, and can seen from the subscript of the dependency.
C.2 PROPOSITIONS AND LEMMAS
First, we state some propositions and lemmas that will be useful in the proof to come. Proposition (Multi-class classification). For a multi-class classification task, Vyt, Uy E V, we have law,, = t.. Similarly, Viaa in E y, we have 1g-00 = tt.
Lemma For a consistent label graph and Vgr E D.Vyi. E V, if ty = to. we have 11gin 199
Proof. For Vy,. Bj V. based Proposition 1, know ty: t², which implies (1) the intersection of the sets labeled by ys and yj is empty. For VDi E D. if tw. = =t, we have (2) the intersection of the sets labeled by i and is not empty. If tuysh ta9 which implies (3) Uj Ú1. Based (2)(3), we have yı O yJ + 0, which is contradictory to (1). Thus, prove when
yy. = 10, Lypi + 199
Lemma 2. For an informative ILF >ÿ and given any ya E V, there exists some in E Yj, such that,
22 (V.. û) 0, Vl [ky].
Proof. Because II. >y is informative, we know there exists one G. E 3 such that j. is exclusive to yd. i.e Da & (ya,),)) Therefore, for any ÿt ÿi either ÿa + ÿt, ÿJ D. $ Vj. which leads the conclusion by the definition of $2 2. Ace
16

---

Published as a conference paper at ICLR 2022
C.3 DEFINITIONS
Before the main proof, we connect the indistinguishabliy of label relation structure with the depen- dency structure of PLRM by introducing the concept of symmetry as follows:
Definition (Symmetry). For Yis Uj y, we say yi and yj have symmetric dependency structure if the following equation holds:
1, = $ 3,bo V
+
La.b jab Va [n], E [k].
+2
(9)
Based on the construction of PLRM, know that for Vy,, Mj 3/ VD: D. 4y: Lysūo (the statement in Theorem 2) is equivalent to and Y have symmetric dependency structure.
C.4 EQUIVALENT STATEMENT OF THEOREM 2
Our main result states that asymmetric is equivalent to distinguishable in the following theorem, which can readily be seen to be identical to Theorem 2 in the main body the paper:
Theorem 3. For a probability model defined as Eq. (8) induced from a consistent label graph and informative ILFs, for any pair of ya Mj y, Y4 and yj are distinguishable and only they have asymmetric dependency structure.
C.5 PROOF THE NECESSITY IN THEOREM NECESSARY CONDITION
We first prove that for any ye My V. Y4 and yj have asymmetric dependency structure is the necessary condition of that they are distinguishable.
Proof of Theorem 3. We prove this theorem by reduction to absurdity. Suppose ys and yj are sym- metric. Then, by Eq. (8), the distribution of Y condition any Y and y can be calculated as follows:
(e Y,.) Po(Y, Y)
Pe(Y = yi r)
On the other hand, applying Y = y/ in the definition of x² leads
22 T (v:, :) 0, Vr E ( [m], vI [ka)]
We further separate I into ( where क collects all the dependency in T with y, involved, i..,
T ( ドー
with the corresponding parameters respectively denoted as ! with θ = (o) Similarly, Φ is also divided into ( following the same routine and @ is respectively divided into (07) Specifically, if y, and y; symmetric, further have
i = [==)), Φb $²
Based the notation, Po y Y) then be represented as
Po(Y = 8) exp (1000)1001.))00)))))00.)),0))))1
=exp Σ
( 2 (y/, Y) +
17

---

Published as a conference paper at ICLR 2022
which further leads to
Fe(Y= - -ily, 8)
Σ exp (1)30)0)))
(07) )9(8
=exp Σ ()) f) + ( 8)
(10)
which is independent of @o. Similarly,
Pe(Y= ,,,1,, Σ exp ())))(()))))))))0000
exp
(6))
(11)
and VI [K]/(i,j}.
Po(Y = =, 8) Σ exp (10)) 8) + ( x))
exp
(0)) ( (2)
+ () 20 8)
(12)
Let Ô be defined as follows:
ê = =) 0/, vi $ (i.j),
6 = 0), 6 0², 0 = 0f, vi & (1.1)
and
@ = 0"
We then have
(Y = 3: 8.1881)
po = -b:m-i,Y, 8)
Σ Y exp
Σ Exiesy exp
(18)TT(((.,))
exp (1) (4) (1) 8) 4' + (6))))((()))))))))() 8) - 43] 8))
Exrexp exp
(6)) 8))
Ex exp
Similarly,
Po -,,l,,
Po (Y = -,,
Σ y exp (x)) 17)
Ex exp
(18))=((0.)))
exp (001 (0) (w,, 8) D/(,, 8)) (03) ( 8) -0?(v, ())
(6)))=((..7- (7)) 8)
Σ Eysexp exp
Ex exp
(8))
8)
18

---

Published as a conference paper at ICLR 2022
and VI ()
Σ . exp
Po -,1,,, 8)
Po =
Ex exp
(10)T
Similarly, we have
Pe = unknown| Y, 8
Σ y, exp
(0))"((0.70-+ 8)
PP (Y unknown (..)
Σ y exp
Therefore, we have
(Y 1) Po(Y = ,
Po(Y = 8)
Vy E 3//u vi3.
Pg = リリ 8)
P&(Y = wily, Y)
Pg(Y = v/Y, 8)
Since
Po(Y yi (,, + = u Y) +
Σ
PolY = w Y) 1,
(g
and
1 F) Po(Y -, y) + Σ
Pg ,/ y 11 1,
we obtain that
Po n/ 8) = PY v,1P,8)
Pe(Y = v, 8) = Pyy( = 1,
Po(Y Y) PY = ,)),,),,
which indicates and y indistinguishable, and leads to contradictory. The proof is completed.
C.6 PROOF OF THEOREM 3: SUFFICIENT CONDITION
We then prove that for any yi, Mj E V, and Y/ have asymmetric dependency structure is the sufficient condition of that they are distinguishable.
Proof. We use the same notations (0)) (0?) and e in Appendix C.5 to denote the separation of the parameter O Let θ be any parameter satisfying that there exists a parameter Ô, such that Eq. (4-5) holds. By Eqs. (10), (11), and Eq. (12) together with Eqs. (4-5), we have Vr E [ki], + j, exp (v.,
exp exp (1211177944111111110000014411111 8)) exp (=11://)99(00011000/000404411110 exp (8) exp (o, exp
K))
Y) 1|0 F))
exp X) (16, Y))
By simple rearranging, we have
(0)) -1
(((79990100000)00111001777771173 = +11999||6677H+,00410000144444444
R)). (13)
19

---

Published as a conference paper at ICLR 2022
By the equality between the second term and the third term in Eq. (13), we obtain that (0:) Y) (u) Y) = (Uj, F) + (3)) - ((6)) (vr, F) + (6,)Ta f)).
(14)
We further set Y in Eq. (14) respectively to el (the one hot vector with its /-th position being 1) and O for any fixed l E [k). i.e.
(3,, ((0)) Φ (v: ei) (0)) 0) (v. 0)) - ((6)) " et) ( 0)) =(()) 0) (3y e1) ()) 0)) ((0)) 1 e)) (6)) Φ (y. 0)).
which by simple rearranging further leads to
0 (1) 1)- (,,, 0) - 1),, 1))
1) - Viv.,,. 0) - 2 1)).
Since )) 1 0, and by definition we have
|+) 1) $) 0) - D }),(V, 1)1 = 1,
and
( -0,, 0) (V. 1)|=1,
we obtain 0) = ,,,,, and
2), 1) 43,(0, 0) D),(v, 1) 1 1) &1, 0) - 2), 1).
(15)
Therefore, either fug0 E (to, red ( and 1y. (19, ped to0), ) or fy t and fu tt, which by definition further indicates that :.? = o3 (recall the way we build dependency between Y and V).
As l is arbitrarily picked, we then have @ is equal to Q component-wisely.
By the equality between the first term and the third term in Eq. (13) and following exact the same routine, we also have 6 = =
On the other hand, for any E [b.. fixing Y and y (Vs + r), and setting Y, of (1 E kin of E NN;,, 24)) in Eq. (14), we have
(0)) Y) + (o)) T Y) 8) 22 (v,, 0F)
Σ
02 t2 (U,, Y*)
Jis
exper
= (vx, 8) + ( T क (w:: P) + 0 ira
(U: 11 + Σ
1,0 1, (y), p7).
On the other hand, by Lemma 2, there exists some p. s.t., ii & NN(, vr) (which by t $3 further leads to 87 & (N V,)). Setting Y, = of leads to
(0)) 8) + (0!) (M,, 8) + Σ 0 12 (v,
syr
=(0)) To) x) To. (2r, Y) + Σ
/
6
(v. 87)
sgbrr
Subtracting the above two equations leads to 0 j.a.1 - Since and l are arbitrarily picked, we conclude that ) = 07. Following the same routine, we also have O = 63.
i,a.I-
Therefore, by applying 0 6). θ θ) 03 07 and O 03 in Eq. (13), we have
(y,, F) - (e.) F) = T (u,, Y) (0!) T (1., Y), (0)) To) F) (0)) F) = (0)) F) (T))T |/ (v), Y).
20

---

Published as a conference paper at ICLR 2022
Let Y 1g (i.e., the k-dimension all 1 vector), we have (()) (0)) (m. ( 12)) (10) 1;) $) 1;)))) O. (17)
(ur, 1 ( 1 - (10) 11) 2) 1g)))) = 0,
(16)
Since yı and yjj are asymmetric, we have that there exists I, such that bnn + by: Concretely, by Eq. (15), we have bui E {t,, (0,,td " fygn = {1o, 1ed, 190), , and (u:3 # fyym- On the other hand, (V,, 1) ( 1)) (v) 1) (vs: 1),
if and only if migh = t0 1 t Eng80 to, tyc t which contradicts Lemma 1. Therefore,
(u,, 1) (リj 1)) (uj 1) (11; 1)- In this case, solutions of ; 0 subject to respectively Eqs. (16) and (17) lie along zero-measure set.
The proof is completed.
D PROOF OF THEOREM
D.1 LEARNING ALGORITHM
We first present the algorithm for producing ê and W in Algorithm
Algorithm 1 WIS
Require: Step size 17, dataset D X, and initial parameter Ou- θ - Og. for all X do Independently sample (Y,Y, Y) from Tg. and (Y', "Y,") from Ta conditionally given Ý Y,
((X).
θ + + (, -("''' Nr',Y' Y', f))).
Compute W as described in (3) using é. output (Ô, W)
D.2 ASSUMPTIONS
First, the problem distribution x² needs to be accurately modeled by some distribution O* in the family that we are trying learn:
O0 s.t. V(Y, Y), P (V, po- (V,
(18)
Secondly, given an example (X,Y) ~ T,, we assume Y is independent of given Ý(X):
(X (CY)~='' MLYA (()).
(19)
This assumption encodes the idea that while the ILFs can be arbitrarily dependent on the features,
they provide sufficient information to accurately identify the true label vector. Then, for any O, accurately learning @ from data distribution is possible. That is, there exists unbiased estimator
@(D) which is function of the dataset D of i.i.d from Te, such that, for any θ and some >> 0,
Cov Cov(@(D)) 1
(20)
Dc
And we are reasonably certain in our guess of latent variables, i.e., Y and V. That is, for any 0,0*,
Ex.
(n: + (Ly 8032
(m + 1/ (8 8r)²
(21)
V2M
21

---

Published as a conference paper at ICLR 2022
We also assume that the output of the last layer of end model hw has bounded &o norm, that is, for any possible parameter W,
oo S H.
(22)
Finally, we assume that solving Eq. (3) has bounded generalization risk such that for some X > solution W satisfies
By [ -min
min &o (W)) sx
(23)
D.3 PROOF OF THEOREM 1
To begin with, we state two basic lemmas needed for proofs throughout this section:
Lemma D.I. Let X1, X2 be two binary random variable. Then we have variance of product of x and X2 can be bounded as
Var [x12] S Var [x1] + Var [x2]
Lemma D.2. Let Y be a random vector and |1-11, be the spectral norm. Then we have
|Cov(Y, - Σ Var(Y;).
Then, we borrow two lemmas from (Ratner et al., 2016), which are slightly different from the original ones but can be easily proved following the same derivations:
Lemma D.3. [Lemma D. in (Ranner et al., 2016)] Given a family of maximum-entropp distributions
TT TY,Y,,8) Ze exp (xp,
we let J be the maximum expected log- llkeliiiooood objective, under another distribution n²,,, for the event associated with the observed labeling function values Y.
((0) Byy- (x [log P.
(YPPP)TT (8=8+)]
then its Hessian can be calculated as (() -B(y- 80) (CoV (X,
(, (x Cov (Y.Y & (6Y,Y,8))
Lemma D.4. [Lemma D.4 in (Rainer el al., 2016)] Suppose that we are looking at a WIS maximum likelihood estimation problem and the objective function J(O) is strongly concave with concavity parameter с > 0. If we run stochastic gradient descent using unbiased samples from a true distribution Te.. then we set step size as
CE2
1
4
and run (using a fresh sample at each iteration) for steps, where
2
11 - 0-1
T
G2 log
We can bound the expected parameter estimation error with
E é 18-67 orl2 < Me?
(24)
where M is the dimension of O
Based on Lemma D.4, in order to obtain the optimization error with respect to the estimated é produced by Algorithm 1, we only need to show that the WIS object function J(O)² strongly concave. We prove this through the following lemma, which is non-trivial extension of Lemma D.3 in (Ratner et al., 2016) given the fact that we have multiple latent variables and relatively complex dependency structures with comparison (Ratner et al., 2016):
Note that, in the Fq. (2) of the main body of the paper, minimizing -J(O), which is equivalent to maximizing J(O) discussed here.
22

---

Published as a conference paper at ICLR 2022
Lemma D.5. [Extension of Lemma D.3 in (Ratner al., 2016)] With conditions (20) and (21), the WIS objective function ()) is strongly concave with strong convexity c.
We then come bound the generalization error of W produced by Algorithm 1, using the following non-trivial extension of Lemma D.5 in (Ratner et al., 2016);
Lemma D.6. [Extension of Lemma D.5 in (Ratner et al., 2016)] Suppose that conditions (18)-(23)
hold. Let W be the learned parameters of the end model produced by Algorithm 1, and E(W*) be the minimum of cross entropy loss function Then, we can bound the expected risk with
((W)) - -((W*) x 4cHc.
Finally, we conclude Lemmas (D.4), (D.5) and (D.6) as the following theorem, which is identical to the Theorem in the main body of the paper:
(Ratner et al., 2016)). Suppose that we run Algoirthu on WIS specification to produce Ô and W, and all conditions of Lemmas (D.5) and (D.6) are satisfied. Then, for any > O, if we set the step size to be
Theorem 4 (Extension of Theorem
OE
and the input dataset D is large enough such that
2 c2e2
10 1000-6111 0/113)
D
log
e
then we can bound the expected parameter ervor and the expected risk as:
é 10 l Me?,
0-
E (((i)-e(w")] sx 4cHe.
D.4 PROOFS OF LEMMAS
Lemma D.I. Let X1, X2 be two binary random variable. Then we have variance of product of X and X2 be bounded as
Var [x]x]] S Var [xi] + Var [x2]
Proof. Joint distribution x₃ and x2 can be listed as the following table: (where p1 + + + + P1
1)
X1/X2
P1
P2
P3
Then have
Var [x]x]] = P4 - 23 p4(p1 + + + pp),
while
Var X1] + Var X2] (p2 +p)(p1 + ps) + (ps + p.)(1 + +2) 2 pi(p1 + P2 Pp).
The proof is completed.
Lemma D.2. Let Y be a random vector and |I-I1, be the spectral norm. Then we have
||Cov(Y s Σ Var(Y.).
23

---

Published as a conference paper at ICLR 2022
Proof. By definition of spectral norm, have
[Cov(Y, = max x' CY)
|
Where is constant vector. And by Cauchy-Schwarz inequality,
x' c'Cov(Y, = E x T (Y E - 1 [x])
s ||||| || E E
Because æ is constant vector and ||
S 1,
max
E
||>|||
? ||
E E
|| |=1|a11
max
||
E
|| E [M117]
|
max
||=]|
Σ Var(Y?)
Var(Yi).
The proof is completed.
Lemma D.S. [Extension of Lemma D.3 in (Rainer al., 2016)] With conditions (20) and (21), the WIS objective function (() is strongly concave with strong convexity
Proof. By Lemma D.3, hessian matrix can be decomposed as follows:
V=)(0) -gg-nnr [Cov (Y, ( -Co Cov (XF (0 8)).
Basically, to prove that J(O) is strongly concave with strong convexity c, we need to show for a real number с 0,
viJ(O) = cl.
We calculate each term separately: for the first term
= E B [Cov (Y.Y. (CoV ( y = =.)]
since is symmetric, for any real number c, A < cI. if and only its spectral norm |||]s S c, where |||]|, equals to the eigenvalue of A with largest absolute value.
Since by definition, vector function @(Y, Y)
can be represented as:
AAAce Bi.of
(1,D1))
iE tE(kl (/ (N( (Fi y))
,(Y,8,8)
(ob (8', P1) (JE((]
( (Y, (X, (E(N)
24

---

Published as a conference paper at ICLR 2022
by Lemma D.2, we have A can be further bounded by
(0.g), 8 ( r
A
Biinas
Σ
Var Var (Y,8, DNom
1=1
&y (s).)ss)
+ -gg-nii"
Var Var (y (0A.(((:8))) 8 88=8811 8-))
BEE
Var (a, (8', (i) 8 = 8r
+ Ey--Nt-
Isijsk
i
+ Eei-nto
Var ( (oine,
(V,81) ( =+,)
==
-Ai + A2 + Ag + A4,
where
h ΣΣ
Var (Y,8 (onee ( (x,80) 18 -
A1 =Bq'nto
Σ
i= 5= of (N).))))
12
A2 =Bginaaa
Σ )-
= 18=08-=-- Var (a (D2)5(Y, 8
= ;
Ag =BQ-nTOr
Var (y,8,)NT (ohno) (P' & = y
ISijsk
Var ( ΣΣ
(dh (Y, & yr)
A4 -Bg
j=1
We then bound the four terms respectively. As for AI, for fixed V-, we have
ΣΣ Σ
Var
(MMes ( 8 = )
of =1 (3)
Σ
Var Var (I 18=80-
j=1
k
Σ
Σ
Var Var 18 1
&
Σ
Σ
Var Var (Iv=y 18
1=1
Lie()) of (.
k
n4 Var (Y 1
where n; is the number of ILFs whose label space contains label that is non-exclusive to label yıs iee.
n, = Hi E (n.) Vi,) O]).
Therefore, we have
k
A <
Σ 1=1
n; By Var (): (Ir=y 18=8.)
25

---

Published as a conference paper at ICLR 2022
Similarly, for A2, we have
-ag Var (,,8, (P' (8')8=P*))
A m, By.p..
where m, is the number of ILFs whose label space contains the label D:.
As for Ag, for fixed Y and any Gt. 0g E V, we further separate the proof into subcases by tg. which is simplified as t:
(I). t = to, In this case,
Var Var ()
Ponns (8', P)) 8 8-)
-Var (1r=z8/ 8 Y==² )
(y,
y''y" y = -
Var ( (4' 88'18=1) = ) + Var (,, (7'18-80)).
where Eq. (*) is due to Lemma D.I.
(2). t t. Similarly,
b (P; 83) 8 )
Var
=Var (Vr
-191=8/=1 8 )
-Var
119=89== y= 8ppm)
(r''' | == (8=)'
-Var
Var yr 1/= 18=8') + Var (8'18=8"))
(3). t = t39 In this case,
& = - (, 06 2 (P', (2) 83)
1 V = =8-)
(ar
(')'' 8= pm))
(1 Pi (1-1'88= (8=1) =P-) + Var Var ( & ).:) =P))
<aary,y,
( (5'18= = (r')8=>*)) Var "011=88") =
(ar(y,F
(4). ped Similar (3)..
Var Var
0 2 (8', pJ) 8= = )
=Var (Var(yy,P))TT
11 1 == pm)
-Var -Va
8=vr
1- 1-8jJ -==8)))) =Xr) (ar ( (8'18=80)
<Var &N
(1 8'18=8r) Var (ar
(yJ (8')8=))))
(arry;
26

---

Published as a conference paper at ICLR 2022
Combining (1), (2), (3), and (4), have
A3 - Σ 1)
1)Bg- Var Var (y,8,8))T
( (8')8=
As for A1, by similar discussion of Ag,
k
A4 S ME y Tgg Var Var (Y,8 DNoe
kB BBg-NTTr xg-
Var
(Y,,,8)) (1r=y.
18 18-)
Combining estimation of A,, A2, Ag. A4. and by condition (21) we have
||||
<Ai A2 + Ag + A4
k
< y TNT
Σ (n+ (1r= p+)++ +
Σ (m; K 1a (8-18 8r))
&
<Epenaer
Σ (ni 1) Varr,, 8
Σ
m; K 1a (P'18" 1 8r)
k (n+ 1)) Σ (m: + K K-11
V2M c.
V2M
which further leads to For the second term B
A3d.
(0(YY,,8),
B E (1,8,8)m (D(Y,Y,)) -E /o
P (0 F, 8))))
0(Y,8,8) Er.r P D(Y', 81 exp (r))()))))))))
= =Eyp
Er.r.g exp ("
exp ( &. (r) (r)))) 27
Ve V log (xpp (oxp (0""(1,,,, Ve Σ
= =
( (Vo log T l "Y, 8))
Te (Y, (Velog (Y Y, ))
where E ( bound and the condition (20),
the Fisher Information of ④ By the Cramér-Rao
I
Cov(ê) 2 DE ( [Voolggoo(Y.)))
Dc
which further leads to
(Vo,lggo(tY z 2cI.
B E Mr=re
The proof is completed by putting estimation of terms A and B together.
27

---

Published as a conference paper at ICLR 2022
Lemma D.6. [Extension of Lemma D.5 in (Ramer et al., 2016)] Suppose that conditions (18)-(23) hold. Let W be the learned parameters of the end model produced by Algorithm 1, and E(W*) be the minimum of cross entropy loss function l. Then, we can bound the expected risk with
E (()))e(w"))))
s 4cHc.
Proof. We begin by rewriting objective of expected loss minimization problem using law of total expectation follows:
((W) =B (x,,)
(x,
-X( Bx [H(Y, W)
-E(X)Y'>>" E(x,y>=> [H(Y ,W))) x']
and by our conditional independence assumption (condition (19)), we have
which further leads to
E B(x [( -(x) - f(x')]
E(W) =E )
[H(Y, W))) [
On the other hand, if we minimizing the model with learned parameter θ, will be actually minimizing
t (W) = =E (x [Brrrros [M(Y, (xX,,( -
where for any X', E (
- can be further calculated as E B [H(Y, w/)lE -
log (o(h(X' W))) (y (Y w = 8(X')).
For simplification, we rewrite IP ():))~a (Y = vi = Y(x')) as follows with slight abuse of notations:
P PY (Y (Y= =v/08 9(X') = PTg (xx))(X')),
and similarly
E(XY E,,,,
Let 1x A arg min; log (a(h(X', W)))).
The difference between the loss functions will be
(W)-2(1))
B
log (a(h(X', w))) (Pro- (x1)((x')) (ro
By
log (o(l((X', w))...) (Pag. (m (x())) - P-o (2I ( (F
+ E
log (a(h(X', (e)(((")))))) (Pro- (vrl((xx)) - -Prg (u)) (x)((())))
28

---

Published as a conference paper at ICLR 2022
Furthermore,
E
log (o(h(XX (W))x)))))))x))) (Pre (2xx,19 - P.o (e) (x())
+ Ex-
Σ
log ((ohh((',,))) (Pa- -RT (001)((11))
Hxxx
Er
log (o(h((',W)))) (-
Pa
Σ
PMO- (wil (wil +
Σ
Pag Pa (
jflx1
log (og("(((X' W])) (Prg. (ml(((()) - -Pas ((x)(((((()))
+ Ex
(log(a(h( (o((((X,,,))) - log (o(M(X', ())xx,)) ( (ull(()))())) - -Pa -Pag ((11(((1))
Bag
1x
(h(X', W), - h(X', ()xx)) (Prg- (xll((x)) - Pro Prg (el)))))())))
Ex
(25)
Let
h(11,22) = h(X', W)., M("',W),.
By Eq. (22), we have for any 1 E [k],
0 S h(l, S 2H.
For any fixed X', define gx (0) follows:
(x)
E (1,1xx))P.e (xil((()))
(26)
1f
based on which we have
(((W)<(WW)) s Bx-
By First Mean Value Theorem,
(x)( gx = -V 11 (V
We then bound (E) wiselyt-wisely:
(1). For any i e [k],] E [m]. o/ E NN(,,, 2,), 8'(('') = os
(g)
OP (y (x'))
Σ h(1,1x))
agAcc Visiil
xxxx
vi.8f J
Σ (Xx (x)((())))
Σ h(l, ( (x))))
1x
<2HP T ((('))))) - (xx1)())))
=2HVar 1v= 1 {(x')]
29

---

Published as a conference paper at ICLR 2022
If xxx, (x²) = Di
(5)
OP (ur (mll((x'))
Σ k(1,
OgAce nr.
OgAce
w..l -
E Dx (4
+ 1x),
Σ ((Xx))))
S max
(f(i)))))
M(i,Ix))
S2HP T.. (vil (xx)(( (P((())((())))
-2H 1r=r:(
If (X'('' + 0
Ogx (E)
PFx (x))(X'))
ogAlc
=
Σ h(1,xx))
ogAcc
0.
v..07
(2). For j E [m], Dr E V3. if = Dr.
(g)
Σ h() OF (2n (X'))
0gAce Be.j
OgAce
Σ b(), (Y = -" 11((")- - PP = =n "(((('))) (p- -8"==19 -1800))))))
Let
f1(1) = Fx,(Y = nn 8" = 118(x'))
f2(1) P , (f-==1((x")
and
B¹ = =1:11: ((:A() 2 (00)1+1x))
B² (1= +xx]
30

---

Published as a conference paper at ICLR 2022
Therefore,
Σ h((lxx) (P
(PTc( = P P= = 1(}((()) FF =x) -1(((11)))
E ((1,1x)((11)) fc(()
Flxx
Σ h((1x) (fi(t) f2(1)) + Σ
(f:00)
-
tEB
1E
max 1=122
h((, (fi(1) f2(())
LEBT
Σ
M(,xx)) (F((1) f2(1); Σ
h((lx))) -5(0)
max
LEBL
LEB2
On the other hand,
E (((Ilxx) (fi(1) - f2(1))
IE81
Σ h((,1x)) (T y = 1(((x)) (Y= (P" 11²(X'1)
LEB1
<2H
Σ
(P (Pxx(( (Y = ",, yr = 118(x')) PY
(Y : (P" 11x((')))
LEBI
=2H
[P (Y yI, 31 e B y 11x(x)) P.. (Y = y IE B¹ (x')) P. ne (8" 118(x)))
-2H
(P (Y yn, 31 e B y 111( (Y = (x((x))
P (Y yu I1 E B y -0 (8' -1)x(x)))
<2H (Pay (8" (f"
=2HVar [p])(())
Similarly, we have
T(l.4x)) (2(() - (1)) Σ
T(l,xx)) (Y=g(Y= = yr, 8" = 11((x()) + Px = "=)l((()))))( (F""")))((00==10"x0")0
JEB1
1882
<2HVar
[T)](
Conclusively, we have
(gxx(()
< 2H (
agAcc
Dr-j
If V G.. similar to (1), we have
(gx:(())
= 0.
00.00
N..j
31

---

Published as a conference paper at ICLR 2022
(3). For any De. V, by the definition of ".,,, there exists (a, {0, 13, such that Sn,,, (a, b) # O. Similar to (2), let
fa(1) = Fxe (Y = =n = -a.'"
fi(1) Pre (Y n (X'= a, a, = (x))
and
Ba = (t fa(0) 2 (10,+(x)
B² ==t1::fa0 < A
we have
(g):(()
max Σ 1(,1 - f40)), Σ (10)
O0C
LEBS
1EB
Poins (8:, ()))
$2H
(x)
< 22 Var ((((()) + Var (1))((1)))
where incquality (+) comes from Lemma D.I.
(4). For any y1 E V, Dr E V, by the definition of of ".. there exists a E {0, 1}. yj E y, s.t., o' S. (Uj, a) * O. We further divide the proof into two cases: oi &y (Vi, a) = 0, and øe s. (V:.a) +
(4a). If cbt g. (uss u) O, we have bn 1.9 and consequently 1. Similar to (1-3)., we have
(g) Ogt yr.
OP ne (vn (x'))
OP nc (En (x'))
Σ 1(l.Ix.)
1(l,
Oge
Oh 0r.0r
Ur.Ur
h((,xx)) (Y yl, y
11((X')) - -18(x'))))))))))
= (Y * yi, 8== =1(((x)))
(Y: (Y # nr 8" =118x1)))')
where Eq.
(o) is due to Let
fo(() = Pa (Y =n, Y" = 11((x'))
fe(1) Prg PY vxl (Y # vi, 8 = (((()')
and
BS = (1: fs()) 2 f6(1, 1+
B = -1: fs(l) < fe(), 1#1)
Then we have
(E)
Σ h(1, ((6()))))(()))))))))))))))))
(fa(() - fo(1), Σ h(1x))) -600)
< max
a0t
3/.
İEBS
L
32

---

Published as a conference paper at ICLR 2022
On one hand,
Σ 1(1,Ix)) (fs()) - S6(1))
IEB
-E [h(l,xx)) (Prg(Y= -M, y = 8 (x(()))) P - (Y # 8 = =
1E85
Σ
",,." 2H (P (Y= y1, y -===10 =1(r(()) PT₂( (V= (Y + yi 8 = 8 118(8)))
1EB5
[ (Y = y1, 31 E B 8" = 1|((x)) - PTς (Y n, .1 E = x5 (V * vı 8 = 11((x)))
-2H
8 -2H (Par (Y- = y1, 31 e y = 1|((x))( -
-Pre (Y + vv 8 -1(((()))))
- Pxe (Y in 31 E B Y
B = -X (Y + vi y = 10,88=110: =11((x)))
<2HP (Y # y/ y = 11(((()) - Pree (Y # vi, 8 = 11((x()))
Va 6 u. (Y, (X)TT)I(X*)) (x))
S2HVarne [xx)))((0)) + 2HVar [p]]([]]]
On the other hand,
Σ h(1,1x-) (f61)) - + -(1
LEB9
)((.x))) (P yn 8 = (x)((')) + (Y = ( (Y + u. Y 118(x1))
LEB
yr + T-i,, (x re (Y = /1 (Y 8 = , -1(()))) 18({))
2211 (-Pase (Y yn 31 E B", Y
(Y # ni 8 -11((()))
- P (V = y1, 3. E 13 y" = 0| P 76 (V *v; 11=1(((x'))
+ Fx (Y = = x2 (Y ys 8r = 11((1)))
22H (Prg ( = y. A E 8" = (1)((())) p3
T. (Y # # p-= 1((())
+ + (Y 1// (1)(('))) (Y # yo 8 = =11((x)))
2211 (P (Y" =
xe (8 = (x)(X() + =Y= (Y &v. - 118(8)))
<2HVar [Lx=n] [(x)] + 2H [p)}(()]]
Therefore, in this case, we have
(g
[ + 2H Varze [イ))((1)))
<
2Hr
00
v..9-
(4b). If 6t U. (Vi. a) + 0. similar to (4a)., we have
(g) Oge
- Σ Cal,Ix))PPP (Y PY vn & (Y= vi, Y 8 (1)()))
Br.
lii
y- T((,lx)) y. v = 1 - (Y x1 (Y yr y -- 18()))
33

---

Published as a conference paper at ICLR 2022
Since
h(i,lx:) (Prre Vi, P 1|((x')) - -xi((x')) (".
= 11((x))))
y (PT ( -V, 8"
= -1((x)) (Y + * vx((((())
20,
have
(g
S max { (x
(Y yi, Y (X)())) (Y + (x())
a0
Mi:0i
(Y= P v 8= = --
S2HVar [x=m)(+())
Combining (4a). and (4b)., we have that
(g
|x==i (=(0)))()))) + Var [p' (x1((x)))
<
2H
VVarig
a0 vi:h
Combining (1-4),, then have
(E)]?
(WW 1;)1 1) Var [Ir-n (xx')
<411²
(27)
4H²
Σ
Var ()')((x))²
jE(m).D.E)
Varme ())E(())) + Varme ()))((1)))
+ +
AJElR
+ +
Σ
Varrs [Ir=w] + Var ())(()))²
JE(R
& (n: + k) (Lr=m, 1 = 8072++ +
<8112
Σ (m: KK 1)r (8'1)8 88122
(28)
Therefore, by Eqs. (25), (26), and (28), and Assumption Eq. (21), we have
(e(w) (o(W)
Σ
h(1,)x))
(Pr -Y (1===/"(())) (x)) Px (Y = =x18((1))
1
BSg
(xx((0)) (6)
B | (5) - -|
2cH
1 - Ôll
VM
Now, we apply the assumption that we are able to solve the empirical problem. producing an estimate W that satisfies
E [Ca((1) (W() <x.
34

---

Published as a conference paper at ICLR 2022
where Wi is the true solution to
W arg min (W).
Therefore,
(((V)) - ((W") = E ( - (3(WW)) ( (W(()) - (o( + ((w)
E(wr))
(+) - x (1())) (W( ((W) - {(W")
$ x + dcHl
B| Iie E (o(W3)) - -lo(w)+
+ k [
VM
1
xx AcH
E
E
li|l
VM
where Eq. (+) comes from condition (23).
With Eqs. (20) and (21), have Eq. (24) by Lemma D.5, i.c.
[Bll - قll 0r|l < e M.
We can now bound this using the result of Lemma D.6, which results in
E [((T) e(w*) S + 4cHc.
The proof is completed.
E EXAMPLES AND ILLUSTRATIONS
E. LABEL GRAPH AND LABEL HIERARCHY
Fig 5 shows the mapping between a label hierarchy and the corresponding label graph. Indeed, given the order of labels, any label structure represented as a (directed acyclic graph) DAG can be converted to exact one consistent label graph based the four types of label relations.
Canidan
Domestio Avemal
Dog
Overioo
Butsuming
Caciden
Hualy
Subwumed
Figure The illustration of mapping between a DAG labels and a label graph.
E.2 AN EXAMPLE OF INCONSISTENT LABEL GRAPH
Fig. 6 shows example of inconsistent label graph. We can see that the label graph is unrealistic and ambiguous because "Husky" subsumes "Canidae". but (1) "Canidae" subsumes "Dog" and (2) "Dog" subsuems "Husky" combined imply that "Husky" should be subsumed by "Canidae". Also, from the example, we can see that label graph induced from cyclic label hierarchy must be inconsistent.
35

---

Published as a conference paper at ICLR 2022
Canabe
Caridas
Overap
Subsemiing
Figure The illustration of inconsistent label graph.
E.3 ENUMERATION OF INCONSISTENT TRIANGLE LABEL GRAPH
For triangle label graph G, we list all inconsistent label relation structures. The consistency of larger label graph with more labels can be verified by checking the consistency of every triangle inside. One example proof of (Exclusive, Overlap, Subsuming) can be found in Lemma 1.
Table 5: Enumeration of Inconsistent Label Relation Triplets.
label relation Triplets
Lab
lbc
La
Overlap
Subsumed Subsumed
Subsuming
Overlap
Exclusive
Overlap
Subsuming
Subsumed
Overlap
Exclusive
Subsumed
Exclusive
Subsumed
Subsuming
Exclusive
Overlap
Subsuming
Exclusive
Subsuming
Subsuming
Exclusive
Subsuming
Subsumed
Exclusive
Subsuming
Overlap
Subsuming
Exclusive
Subsumed
Subsuming
Subsumed
Exclusive
Subsuming
Overlap
Subsumed
Subsuming
Overlap
Exclusive
Subsuming
Subsuming
Exclusive
Subsuming
Subsuming
Subsumed
Subsuming
Subsuming
Overlap
Subsumed
Overlap
Subsuming
Subsumed
Subsumed
Exclusive
Subsumed
Subsumed
Subsuming
Subsumed
Subsumed
Overlap
Subsumed
Exclusive
Subsuming
Subsumed
Exclusive
Subsumed
Subsumed
Exclusive
Overlap
E.4 AN EXAMPLE OF INDISTINGUISHIABLE LABEL GRAPHI
Fig. shows an example label graph with indistinguishable label relation structure. Again, red labels represent desired unseen labels, while gray labels are undesired and seen. We can see that unseen label "Husky" and "Bulldog" have indistinguishable label relation structures because for all seen labels, their label relations are equal. For example, seen label "Dog" subsumes both "Husky" and "Bulldog". In contrast, for "Husky" and "Bengal Caf", seen label "Cat" subsumes the latter but exclusive to the former, which indicates that "Husky" and "Bengal Cat" have distinguishable label relation structure. Note that "Bengal Cat" and "Persian Cat" also have indistinguishable label relation structure, but the former is unseen desired label while the latter seen and can be predicted by some IL.F(s). We are only interested in the distinguishablity of pair of unseen labels.
36

---

Published as a conference paper at ICLR 2022
In practice, users could "break the symmetry" by adding ILFs with new labels. For example, if we add an ILF that could predict "Arctic Animals", then the new seen label "Arctic Animals" will be added into label graph as shown in Fig. 8. We know that "Arctic Animals" subsumes "Husky" but not "Bulldog", so we break the indistinguishable label relation structure of "Husky" and "Bulldog" successfully.
Deg
Doneet
Husiy
Domssfcc
Deg
CNT
Ovetap touring
Cubdig
Sutosmme
Dangi
Cat
Figure 7: An example of indistinguishable label relation structure ("Husky" and "Bulldog").
Anira
Hualy
Ansinl
Anmed
cale
Ouehpp
Dubldg
Hargaa
Parsan
Burgai
Parikn
Figure 8: An example of fixing indistinguishable label relation structure ("Husky" and "Bulldog") by adding a new label ("Aretic Animals").
F EXPERIMENTAL DETAILS
F.1 DATASET
Large scale Text Classification Dataset': LSHTC-3 (Partalas et al., 2015), a large scale hierarchical text classification dataset, which consists of 456,886 documents and 36,504 categories organized in label hierarchy. We filter out the documents with multiple labels, and preserve categories with more than 500 documents. We use pre-trained sentence transformer (Reimers & Gurevych, 2019) to obtain document embeddings for classification. We follow Zhang al. (2021) to generate keyword-basee labeling functions for each seen label as II.Fs.
Large scale Image Classification Dataset': ILSVRC2012 (Russakovsky et al., 2015), large scale image classification dataset, which consists of 1.2M training images from 1000 object classes based
hhttp:// http:///ht..iiii...oooiiiiiiii.i org/ http://hhhheeeggeessssss//////// tat
37

---

Published as a conference paper at ICLR 2022
on ImageNet. Following Deng et al. (2014) the images are assigned to leave labels in WordNet, for each non-leave label, we aggregate images belonging to its descendants its data points (Deng et al., 2014). For weak supervision sources creation, we follow Mazzetto et al. (2021b;a) to train 10 image classifiers as ILFs. We randomly sampling 2 3 exclusive seen labels from the label graph as well as 500 images for each label to train a ResNet-32 classifier.
WordNet as the label hierarchy, and because all
F.2 DESCRIPTION OF APPLYING DAP
To apply DAP, use both label relations and ILFs to construct attributes for both unseen classes and unlabeled data points. Then, we train the attribute classifiers, which in turn are used to predict unseen labels on the test set as in Lampert et al. (2013). To construct attributes for unseen labels and data points, we leverage the outputs of ILFs and label relations.
First, based the label relations and basic logistic rules, enumerate all the possible assignments of seen labels given a data point. For example, if label point, when it belongs to label A, it must also belong B; And if label A and B are exclusive, then one data cannot belong to both at the same time. Let E S denote one possible label assignment and the set of all possible s. Then we define the attribute as vector of [S] dimension where each dimension corresponds to one s.
subsumed by label B, then for a data
Second, we define the attribute unseen labels. For an unseen label A and label assignment s, if A is not exclusive to any label in s then we set the corresponding attribute a, = 1 for label A, other wise O. The intuition that, if A is not exclusive to labels in s, it's likely that when data belongs to assignment it also belongs to label A. For each data point, we use the labels assigned by ILFs build their attributes. If data belongs assignment s then its corresponding attribute a, = otherwise 0.
Then, we can train attribute classifier p(a[z) for each attribute based on data point attributes. During inference, we use unseen label attribute as well as attribute classifier as in Lampert et al. (2013):
p ( (x) II m=
|s|
f(x) = arg max
(29)
pla (x)
F.3 HYPER-PARAE PARAMETERS
For the training of PGMs, we set the learning rate to be 1 where is the number of training data. For training logistic regression model, we use the default parameters scikit-learn library. For training ResNet model, we set batch size as 256 and use Adam optimizer with learning rate being le-3 and weight decay being 5e-5.
F.4 HARDWARE AND IMPLEMENTATION DETAILS
All experiments ran on machine with an Intel(R) Xeon(R) CPU E5-2678 v3 with 512G memory and GeForee GTX 1080Ti-11GH GPU.
All the code was implemented in Python. We use the standard implementation of the logistic regression model from Python scikit-learn library and the ResNet model from torchvision library".
Our code will be released upon the acceptance.
F.5 DATASET DETAILS OF REAL-WORLDD APPLICATIONS
We list the tags used in the real-world application (Sec. 7.3) and examples of label relations query from the existing product category taxonomy.
Shttps: ptetps://acinn http::::////ttttteee weeeenorrr//eeeeee wtt.///aalllloooo.oo.g. sttbl e/ e/modu" es es/generatedd sk 1 learn. "eear_model Logist wwwgressiinnnnccooeeeeeeeseroooe ht.
stabl htt.bll/e//ohchhoooeeo si /mode1 h
38

---

Published as a conference paper at ICLR 2022
Table The tags and examples of label relations of "Car Accessories" category.
new unseen tags:
"Performance Modifying Parts", "Vehicle Tires & Tire Parts", "Car Engines & Engine Purts"
"Cor Modification Parts", "Car Parts & Accessories"
existing tags:
Car & Truck Tires", "Replacemens Car Parts", "Car & Truck Wheels"
"Replacement Car Parts" subsumes "Car Engines & Engine Parts"
label relation examples:
"Car & Truck Tires" is subsumed by "Vehicle Tires & Tire Parts"
Table 7: The tags and examples of label relations of "Furniture Accessories" category.
unseen tags:
"Clothing & Shoe Storage", "Living Room Furniture", "Beds & Headboards"
"Coffee Tables End Tables". "Entertainmmnt Media Centers"
existing tags:
"Bedroom Furniture". "Safos & Chairs", "Mattressss"
"Bedroom Furniture" subsumes "Beds & Headboards"
label relation examples:
SSafa & Chairy" is subsumed by "Living Room Furniture"
G ADDITIONAL EXPERIMENTS
G.1 PERFORMANCE DROP WHEN THE DISTINGUISHABLE CONDITION IS VIOLATED
To validate the effectiveness of the distinguishable condition, we drive another 100 WIS tasks from LSHTC-3 dataset where each task has at least one pair of unseen labels sharing exactly the same label relation structure. In Table 8, we report the performance drop on the averaged evaluation results over the 100 WIS tasks with comparison to the numbers in Table 2. Although the two sets of WIS tasks are different and therefore are not individually comparable, the averaged performance drop does indicates that the violation of the distinguishable condition results in undesirable synthesized training labels, which implicitly demonstrates the effectiveness of the distinguishable condition.
Table 8: Performance drop on averaged evaluation results over 100 WIS tasks derived from LSHTC-3 when the distinguishable condition is violated.
Method
Accuracy
Fl-score
LR-MV
-11.49
-13.83
W-LR-MV
-11.51
-13.47
Label Model
WS-LG
-9.28
-8.63
PLRM
-9.66
-9.33
LR-MV
-16.14
-17.08
W-LR-MV
-15.27
-15.97
End Model
WS-LG
-13.13
-13.78
PLRM
-13.39
-14.09
39


Reviews:
[{"review_id": "lWyckf7LKQo", "reviewer": "Reviewer_Zxiq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Strength\n* Framing the “Weak Indirect Supervision” problem is quite interesting since it is not too uncommon that we have noisy hierarchical labels.\n* Overall the paper is clean and make a reasonable contribution by proposing the probabilistic label relation model along with theoretical analysis.\n\nWeakness\n* Label relation should be one of pre-set relationships. In other words, the labels should be “comparable” in some sense and the proposed method (and also probably for the several similar label graph based methods) cannot model properly when there are a few labels that are not in the similar semantic space. For example, {red, green} and {dog, bird} are not comparable and some relations cannot be expressed by the label graph. Hence, it is natural to apply the current technique in hierarchical labels, but not for heterogeneous (or multi-modal) labels. I wanted to ask the authors to clarify and discuss on this topic in the main text.\n* Datasets used in the paper is all for the hierarchical label interactions. It feels it's somewhat limited than what the authors claims.\n* If I understand correctly, PLRM models the relation from ILF to an label with accuracy levels, which are independent from the actual value of ILF outputs. Hence, the noisy level or the certainty from ILFs for each individual data points are ignored, which seems to be a bit limiting.\n\n", "summary_of_the_paper": "This paper introduces a probabilistic framework that is designed to aggregate multiple weak supervision to a single strong proxy guidance to train a model with insufficient supervision from data. Authors claim the proposed framework differs from the previous attempts since it can also model a non-overlapping set of tasks.", "summary_of_the_review": "I feel the paper is really at borderline (slightly leaning negative) considering 1) the contribution is a bit limited because the framework is only applicable for hierarchical label space 2) modeling ILF to label space with a graphical model is not too novel 3), but the paper still made reasonable contribution in this limited scope.\n\n-------------\n\nPost-rebuttal comment:\n\nI thank authors' response and the clarification on the \"comparable\" assumption in their paper. I also agree on other reviewer's points for the contributions of the paper and increased my score. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "R_H031HI63", "reviewer": "Reviewer_Vocb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "Strengths: \nThis paper studies an important and novel research problem in the weak supervision(WS) setting. In WS, one wants to use as many sources as possible and in many settings indirect LFs can be easily available. However existing WS frameworks cannot accommodate such indirect LFs. Proposed method is technically sound and backed by analysis of generalization error of the end model and distinguishability of unseen labels. Moreover, the experiments on real-world data are promising as well. Overall, the paper is well written and easy to follow. Examples provided help in understanding the setup better. \n\nWeaknesses:\nI can't see any major issues with this work. The generalization error analysis is similar to prior work (Ratner 2016) but I think it is a good sanity check. There are some grammar and spelling mistakes which are listed below. If some details/intuition for Theorem 2 can be provided in the main paper, that would be helpful. \n\nGrammar and spelling errors:\nin abstract \"....an generalization bound.\"\nin section 6 first para \"Husy\" is used several times, I think the authors meant \"Husky\" ??\nin section 5.1 \"... Specifically, for a ILF λj and one ...\"\n", "summary_of_the_paper": "The paper addresses a novel research problem of using \"indirect\" label sources in the weak supervision framework to create labelled datasets. The indirect label sources are similar to the labeling functions in prior works in weak supervision ( data programming) with one caveat that these sources produce labels from different space than that of the original ( target) label spaces. It can be useful, when there are good indirect LFs and there is some relationships between the labels in the LF's label space and target label space. This paper, gives a probabilistic label model (PRML) which utilizes these indirect LFs and label relationships to produce desired labels for the given unlabeled data. The methodology is backed by theoretical analysis and real-world experiments. In analysis, a generalization error bound (for the end model learned using estimated labels) is provided which turns out to be similar to the work in Data programming (Ratner et al. 2016). One needs to be careful with the issue of indistinguishability between labels, in such setup. This issue has been studied in detail and they provide definition, conditions for distinguishability. Experiments on real-world data shows that the proposed method works well in comparison to several competing baselines.    ", "summary_of_the_review": "I think, overall its a good paper which solves an important problem that in turn broadens the applicability of weak supervision. The work is novel and technically sound. In my opinion, it can be a clear accept.   ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NOse6h64D6m", "reviewer": "Reviewer_ZVDL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "Strength:\n* The paper proposes an interesting problem setting, weak indirect supervision, which is a practical setting and helpful for reducing annotation costs in certain applications.\n* Comprehensive theoretical analysis on error bound and distinguishability. However I'm not an expert in PGMs, so I didn't check the proof in the appendix thoroughly.\n* Comprehensive experiments with both synthetic datasets and real-world applications. The proposed PLRM method outperforms baselines by a large margin.\n\nWeakness:\nI don't see major weaknesses; here are some suggestions and questions.\n* I feel the following two paper may be relevant to the WIS problem setting, please consider adding them to the related work section and provide further discussion.\n  * Few-shot Relation Extraction via Bayesian Meta-learning on Task Graphs. ICML 2020. (It studies few-shot/zero-shot transfer to new relations, by leveraging relation graphs, similar to the label graph in this paper.)\n  * Co-Tuning for Transfer Learning. NeurIPS 2020. (It studies transferring a model trained on source categories to target categories. Problem setting is quite different as Co-Tuning assumes target training data, however I feel it's still quite relevant.)\n* Seems the datasets used all have _hierarchical_ label relations. Does that mean the labels are forming a tree structure? I wonder how often \"overlap\" relation exists in the sampled relation graphs.\n* The sampled label graphs have 8 classes. I wonder how the proposed method scales with more classes.\n\nSuggestions for paper presentation:\n* Please consider providing some more examples of the sampled label graphs. I see one in the Appendix E.5, but more examples (perhaps with different structure of graphs) will help me get a sense how hard this task is for humans.\n* The notations are a little complicated; it would be great if the authors could mention that there is a glossary in the Appendix A in the beginning.\n", "summary_of_the_paper": "The authors summarized their contributions quite well in the introduction section -- In this paper, the authors (1) propose a new problem setting called Weak Indirect Supervision (WIS), which extends from the problem setting of Weak Supervision; (2) develop Probabilistic Label Relation Model (PLRM) for WIS; (3) introduce the concept of distinguishability in WIS; (4) conduct empirical evaluation of PLRM on image/text classification and an advertising application.", "summary_of_the_review": "Strength: interesting new problem setting; comprehensive theoretical analysis; the proposed method has good performance on three datasets.\n\nWeakness: some potential missing references; paper presentation may be further improved; some more discussions on the questions I raised may be helpful.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HPsQpiBD5rV", "reviewer": "Reviewer_EDJu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "## Strengths\n\nAlthough similar problem settings (e.g., zero-shot learning, hierarchical classification, or distant supervision) have been studied in the literature, the proposed task seems novel and interesting.\nIn this problem, the given labels are not necessarily the target classes, but they still provide useful information for the classification task.\nThis work takes a data-centric perspective and provides a way to make use of these supervision sources.\n\nTechnically, the proposed method adopts a two-step method that creates pseudo-labels first then trains a classification model, which makes it compatible with many training techniques in the second step.\nThe use of an exponential family graph model leads to some theoretical guarantees.\nThe proposed testable condition can be used for evaluating if a specific supervision source can be helpful for a certain classification task.\n\nExperimentally, the proposed method was evaluated on large-scale image and text classification datasets equipped with label hierarchies and was tested in two real-world scenarios.\nThe author provided empirical evidence that the proposed method outperforms four baselines on these datasets.\n\n---\n\n## Weaknesses\n\nThis paper can benefit significantly from improved writing and organization.\nI may have missed something, but a few symbols are difficult to understand and some concepts seem unnecessary.\n\nFor example, is it necessary to formulate this problem with \"indirect labeling functions\"?\nIt seems that those functions are only queried once for \"unlabeled training set\", but doesn't it make it just a multi-labeled training set?\nThis makes the difference between ZSL and WIS less clear.\nAlthough I understand that the data distribution would be different, e.g., to classify instances from a label set $0$, ZSL uses paired data $(X_1, Y_1)$ from the label set $1$, possibly $X_0$, and label relation between label sets $0$ and $1$; while WIS uses tuples $(X_0, Y_1, Y_2, ...)$ with instances from the label set $0$ and their labels from the label sets $1, 2, \\dots$\n\nA writing issue is that the formulation with \"one-hot vectors\", in my opinion, makes the notation unnecessarily complex and less clear.\nFor example, currently we have $Y \\in \\\\{0, 1\\\\}^k$, $y \\in \\mathcal{Y}$, $Y[a] \\in \\\\{0, 1\\\\}$, $\\mathcal{Y}_{\\lambda_j}$, $\\hat{\\mathcal{Y}}$, $\\hat{\\mathcal{Y}}(y)$, $\\mathbf{y}^a \\in \\\\{0, 1\\\\}$ (not a vector), $\\hat{Y} \\in \\\\{0, 1\\\\}^\\hat{k}$, and $\\tilde{Y}$.\nSo it is easy to forget their meanings and their value ranges.\nAlso, some symbols are indexed by subscripts, some by superscripts, and some by $[]$.\nAccompanied with one-hot vector-valued labeling functions, they make this paper hard to follow.\nAlternatively, I think \"one-hot vector\" can be an implementation detail and it might be more understandable to define the label to be an element in a set and define the relationship with the indicator function/Iverson bracket.\n\n---\n\n## Confirmation\n\nBefore I proceed to ask more questions about the method itself, please allow me to confirm my understanding of the notation and the problem setting.\n\nTask:\n\n- $X \\in \\mathcal{X}$: input feature, e.g., an image of a dog\n- $Y \\in \\\\{0, 1\\\\}^k$: one-hot vector of class, e.g., $[1, 0, 0, 0]$\n- $y \\in \\mathcal{Y}$: class name, e.g., \"dog\" (is $y$ indexed by a number $a$?)\n- $Y_i[a]$: I can somehow understand it but it's a bit confusing. There are too many layers of indirection. Please define \"corresponding to $y_a$\" more clearly.\n\nSupervision:\n\n- $\\lambda_j: \\mathcal{X} \\to \\\\{0, 1\\\\}^{k_{\\lambda_j}}: X_i \\mapsto \\Lambda_{ij}$: labeling function\n- $\\Lambda_{ij} \\in \\\\{0, 1\\\\}^{k_{\\lambda_j}}$: one-hot vector of indirect label, e.g., $[1, 0]$\n- $? \\in \\mathcal{Y}_{\\lambda_j}$: label name, e.g., \"caninae\"\n- $\\mathcal{T}$: could you explain the meaning or give some examples of label relations _exclusive_, _overlapping_, _subsuming_, and _subsumed_ in Section 4? (Or move Definition 2 and Figure 4 here?)\n\nPlease confirm the items listed above and improve the readability if possible.\n\n---\n\n## Questions and comments\n\n### In general\n\n- Besides more flexible training, could you clarify the advantages of the two-step approach?\n- Is the exponential family distribution needed for the theoretical guarantees?\n- Could you clarify the difference between distinguishability and identifiability with a concrete example?\n\n### Section 5.1\n\n- Which prior work? Is \"accuracy dependency\" defined elsewhere?\n- $y_d$ does not appear in the first equation? (cf. the notation issue mentioned above)\n- A very common misuse of the indicator function: It is defined for a set, not for a proposition (Iverson bracket)\n\n### Section 5.2\n\n- How should we interpret Figure 2?\n- \"Training an End Model\" notation issue: should be $\\to$, not $\\mapsto$\n- Are there alternatives to SGD? Is SGD needed for Theorem 1 to hold?\n- Eq. (3): What does $\\tilde{Y} \\sim \\hat{\\Theta} | \\hat{\\Lambda}\\_i$ mean?\n  Do you mean $\\tilde{Y} \\sim p\\_{\\hat{\\Theta}}(\\tilde{Y} | \\hat{\\Lambda})$?\n\n### Section 6\n\n- Very minor: inconsistent capitalization, and typo \"Husy\"\n- $\\forall \\Theta > 0$: Isn't $\\Theta$ a vector? If so, the order $>$ is not defined\n- If it's \"a.e.\", then such $\\Theta$ and $\\tilde{\\Theta}$ may still exist but have measure zero. Is this enough?\n- What's the difference between $\\mathbb{P}$ and $p$?\n\n### Extensions\n\n- The current label relation graph is only deterministic. Is it easy to extend it to be probabilistic?\n- Is classification with rejection applicable here?\n  For example, if we use a dog/cat-classifier on a desk image, the output may be very random and non-informative.\n  Is out-of-distribution detection needed in this problem?\n\n---\n\n## Post-rebuttal\n\nI've read other reviews, the author's responses, and the updated paper. The author addressed most of my concerns and answered my questions well. The presentation of the paper has been greatly improved. Hence I would like to increase my rating.", "summary_of_the_paper": "This paper studied a weakly supervised classification problem, called **weak indirect supervision**, where the supervision signals are from labels that are different from but still informative of the classes.\nThe author proposed a new two-step method that first creates probabilistic labels using an **exponential family graphical model** based on (1) a set of **indirect labeling functions** (pretrained classifier, heuristic rules, etc.) that output deterministic labels and (2) a given **label relation graph** (ontology graph, knowledge base, etc.) that captures the relations between the observed labels and the target classes, then uses the generated labels to train a classifier for the target classes.\nThe author provided a theoretical analysis on the requirements of the labeling functions and derived a generalization error bound.\nThe proposed method was evaluated on semi-synthetic datasets based on the ImageNet dataset for image classification and the LSHTC dataset for text classification.", "summary_of_the_review": "This paper studied an interesting problem in weakly supervised learning and proposed a novel method based on the indirect labeling functions and label relation graph.\nThe proposed method was validated theoretically and empirically.\nOverall, this paper provided a data-centric approach for improving machine learning systems, which might be useful to the community.\nHowever, there are still a few concerns mentioned above, and the writing and organization can be further improved.\nHence I recommend acceptance of this paper.\nIf the author can address my concerns well, I would like to raise my rating.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Scores ultimately point to accept. The one negative review is borderline and doesn't raise any red flags. Weaknesses in other reviews mainly point to minor improvements in the paper and are largely supportive. Rebuttal points are uncontroversial and seem to clarify several issues.
Decision: Accept (Poster)