CREATING TRAINING SETS VIA WEAK INDIRECT SUPERVISION
Year: 2022

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 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 a margin of 2%-9%.

heading: 1 INTRODUCTION
text: One of the greatest bottlenecks of using modern machine learning models is the need for substantial amounts of manually-labeled training data. In real-world applications, such manual annotations are typically time-consuming, labor-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, or pre-trained classifiers. These frameworks have been widely applied on various machine learning tasks (Dunnmon et al., 2020; Fries et al., 2021; Safranchik et al., 2020; Lison et al., 2020; Zhou et al., 2020; Hooper et al., 2021; Zhan et al., 2019; Varma et 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 as 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 ”, “cat”, “lion”} and a set of three weak supervision sources (e.g. trained classifiers or expert heuristics) with disjoint output spaces {“caninae”, “felidae”}, {“domestic animals”, “wild animals”} and {“husky”, “bengal cat”} respectively. We call these types of sources indirect supervision sources. For concreteness, we follow the general convention of data programming (Ratner et al., 2016) and refer to these sources as indirect labeling functions (ILFs).
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 a 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, a 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 ILFs is due to the mismatched label spaces. To overcome this, we 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 “cat” 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 a label relation graph but was focused on relation extraction task in a few-shot learning setting, while You et al. (2020) proposed to learn label relations given data for each label in a transfer learning scenario. In contrast, we aim to solve the target task directly and without clean labeled data.
The remaining questions are (1) how to 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 to 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 in 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, we observe a significant drop in model performance when the condition is violated.
In experiments, we make non-trivial adaptations for baselines from related settings to the new WIS problem. On both text and image classification tasks, we demonstrate the advantages of PLRM over adapted baselines. Finally, in a 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 an 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 a margin of 2%-9%.

heading: 2 RELATED WORK
text: 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 supervision 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 et 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 et 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 distinguishability of unseen classes.
Zero-Shot Learning: Zero-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 a classifier that could predict unseen classes given certain label information, e.g., label attributes (Romera-Paredes & 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.

heading: 3 PRELIMINARY: WEAK SUPERVISION
text: 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 Xi ∈ X the individual data point and Yi ∈ Y = {y1, . . . , yk} the unobserved interested label of Xi. We also have n sources, each represented by a labeling function (LF) and denoted by λj . Each λj outputs a label Ŷ
j i ∈ Yλj = {ŷj1, . . . , ŷjkλj } on Xi, where
Yλj is the label space associated with λj and |Yλj | = kλj . We denote the concatenation of LFs’ output as Ŷi = [Ŷ 1i , Ŷ 2 i , . . . , Ŷ n i ], and the union set of LFs’ label spaces as Ŷ with |Ŷ| = k̂. Note that k̂ is not necessarily equal to the sum over kλj , since LFs may have overlapping label spaces. We call ŷ ∈ Ŷ seen label and y ∈ Y desired labels. In WS settings, we have Y ⊂ Ŷ . 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.

heading: 4 WEAK INDIRECT SUPERVISION
text: 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.e., Ŷ ∩Y = ∅. Therefore, we refer to the desired labels as unseen labels. To make it possible to leverage the ILFs, a label graph is given, which encodes pair-wise label relations between different seen and unseen labels.
Label Graph. Concretely, a label graph G = (V, E) consists of (1) a set of all the labels as nodes, i.e., V = Ŷ ∪ Y , and (2) a set of pair-wise label relations as typed edges, i.e., E = {(yi, yj , tyiyj )|tyiyj ∈ T , i < j, ∀yi, yj ∈ V}. Here, T is the set of 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, tsg, tsd, respectively. Notably, for any ordered pair of labels (yi, yj), 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 in Fig. 2. For convenience, we denote the set of non-exclusive neighbors of a given label y in Ŷ as N (y, Ŷ), i.e., N (y, Ŷ) = {ŷ ∈ Ŷ|tyŷ ̸= te}.

heading: 5 PROBABILISTIC LABEL RELATION MODEL
text: One of the key difficulties in both WS and WIS is that we do not observe the true label Yi. Following prior work (Ratner et al., 2016; 2019; Fu et al., 2020), we use a latent variable Probabilistic Graphical Model (PGM) for estimating Yi based on the Ŷi output by ILFs. Specifically, the PGM is instantiated
as a 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 Θ ∈ RM as PΘ(·) ∝ exp(Θ⊤Φ(·)), where Φ is the concatenation of {ϕ}. However, the unique challenge for WIS is that the dependencies {ϕ} between Yi and Ŷi 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.

heading: 5.1 A BASELINE PGM FOR WIS
text: In prior work (Ratner et al., 2016; Bach et al., 2017), the PGM for WS is governed by accuracy dependencies:
ϕAccy,j(Y, Ŷ j) := 1{Y = Ŷ j = y}
which is defined for each λj and y ∈ Yλj ∩Y . However, in WIS, the ILFs cannot predict desired label y ∈ Y . As a simple baseline approach to start, we leverage the coarse-grained exclusive/non-exclusive label relation to build a corresponding "accuracy" factor. Specifically, for an ILF λj and one label ŷ ∈ Yλj , given a desired label y ∈ Y , if ŷ and y have non-exclusive label relation, i.e., ŷ ∈ N (y,Yλj ) we expect a certain portion of data assigned ŷ should be labeled as y. Thus, we treat Ŷ j = ŷ as a pseudo indicator of Y = y and add a pseudo accuracy dependency between them:
ϕAccy,ŷ,j(Y, Ŷ j) := 1{Y = y ∧ Ŷ j = ŷ}
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 a naïve adaptation might have two drawbacks:
1. It does not model specific dependencies ILFs with different undesired labels. For example, two ILFs outputting “Husky” and “bulldog” respectively would be naively modeled the same as if they both output “Dog”.
2. It can only directly model exclusive/non-exclusive 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” is of course a “Dog” (subsumed relation) while a “Domestic Animals” is not necessarily a “Dog” (subsuming relation).

heading: 5.2 PROBABILISTIC LABEL RELATION MODEL
text: To more directly model the full range and nuance of label relations, we propose a new probabilistic label relation model (PLRM). In PLRM, we 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 Ŷ , we introduce a binary latent random vector Ȳ = [Ȳ 1, . . . , Ȳ k̂], where Ȳ i indicating whether the data should be assigned ŷi. Then, for ILF λj that could predict ŷi, we have accuracy dependency:
ϕAccŷi,j(Ȳ i, Ŷ j) := 1{Ȳ i = 1 ∧ Ŷ j = ŷi}
To model fine-grained label relations, for a desired label y ∈ Y and seen label ŷi ∈ Ŷ , 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:
ϕey,ŷi(Y, Ȳ i) := − 1{Y = y ∧ Ȳ i = 1}
ϕoy,ŷi(Y, Ȳ i) := 1{Y = y ∧ Ȳ i = 1}
ϕsgy,ŷi(Y, Ȳ i) := − 1{Y ̸= y ∧ Ȳ i = 1}
ϕsdy,ŷi(Y, Ȳ i) := − 1{Y = y ∧ Ȳ i = 0}
The above dependencies encode the prior knowledge of the label relations, but also allow the model to learn corresponding parameters. For example, an exclusive label relation dependency ϕe outputs -1 when two exclusive labels are activated at the same time for the same data, otherwise 0, 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:
PΘ(Y, Ȳ , Ŷ ) ∝ exp ( Θ⊤Φ(Y, Ȳ , Ŷ ) ) . (1)
Recall that Y is the unobserved true label, Ȳ is the binary random vector, each of whose binary value Ȳ i reflects whether the data should be assigned seen label ŷi ∈ Ŷ , and Ŷ is the concatenated outputs of ILFs.
Learning Objective. We estimate the parameters Θ̂ by minimizing the negative log marginal likelihood PΘ(Ŷ ) for observed ILF outputs Ŷ1:m:
Θ̂ = argmin Θ − m∑ i=1 log ∑ Y,Ȳ PΘ(Y, Ȳ , Ŷi) . (2)
We follow Ratner et al. (2016) to optimize the objective using stochastic gradient descent.
Training an End Model. Let pΘ̂(Y | Ŷ ) be the probabilistic label (i.e. 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 et al., 2019) with respect to Θ̂ over m unlabeled data points:
Ŵ = argmin W
1
m m∑ i=1 EY ∼p Θ̂ (Y |Ŷi)ℓ(Y, fW (Xi)), (3)
where ℓ(Y, fW (Xi)) is a 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 in Appendix.
Theorem 1. Suppose that we run stochastic gradient descent to produce Θ̂ and Ŵ based on Eqs. (2) and (3), respectively, and that our setup satisfies certain assumptions (App D.2). Let |D| be the size of the unlabeled dataset. Then we have
E ∥∥∥Θ̂−Θ∗∥∥∥2 ≤ O(M log |D||D| ) , E [ ℓ(Ŵ )− ℓ(W ∗) ] ≤ χ+O ( H √ log |D| |D| ) .
Interpreting the Bound. By Theorem 1, the two errors decrease by the rate Õ(1/|D|) and Õ(1/|D|1/2) respectively as |D| increases. This shows that although we trade computational efficiency 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.
6 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. 3, where “Dog” is a 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” even though the LFs make correct predictions of seen label “Dog”, because both “Husky” and “Bulldog” share the same label relation to “Dog”.
To tackle this issue, we theoretically connect the distinguishability of unseen labels to the label relation structures and provide a testable
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 distinguishability with respect to the model. To illustrate, we formally define the distinguishability as below.
Definition 1 (Distinguishability). For any model PΘ(Y, Ȳ , Ŷ ) with parameters Θ, any pair of unseen labels yi, yj ∈ Y are distinguishable w.r.t. the model, if for a.e. Θ > 0 (element-wisely), there does NOT exist such a Θ̃ > 0 that, for ∀Ȳ , Ŷ , the following equations hold
PΘ(Y = yi|Ȳ , Ŷ ) = PΘ̃(Y = yj |Ȳ , Ŷ ), PΘ(Y = yj |Ȳ , Ŷ ) = PΘ̃(Y = yi|Ȳ , Ŷ ), (4) PΘ(Y = y|Ȳ , Ŷ ) = PΘ̃(Y = y|Ȳ , Ŷ ),∀y ∈ Y/{yi, yj}, (5)
PΘ(Ŷ ) = PΘ̃(Ŷ ). (6)
From the definition, we can see that the opposite of distinguishability, i.e., indistinguishability, describes an undesired model: for any learned parameter Θ > 0, we can always find another Θ̃ which optimizes the loss equally well (Eq. (6)), but Eqs. (4-5) implies whenever PΘ predict yi, PΘ̃ will predict yj 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 ya, yb as 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 = (Y, E) is consistent if the induced set relations are consistent.
For example, assume Y = {ya, yb, yc}, and tab = tbc = tca = tsg. From tab, tbc, we can observe that A ⫌ B ⫌ C, which contradicts to C ⫌ A implied by tca = tsg . Thus, G is inconsistent.
Informativeness. In addition, we 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 Y is {“Dog”, “Bird”}, then for an ILF λ1 outputting {“Husky”, “Bulldog”}, we know “Dog” is non-exclusive to “Husky” and “Bulldog”, while “Bird” exclusive to both. In such case, λ1 can hardly provide information to help distinguish “Dog” from “Bird”, because it always votes for “Dog”. On the other hand, a binary classifier of “Husky”, i.e., λ2, is favorable since it could output “Not a Husky” to avoid consistently voting for “Dog”. We can see an undesired ILF always votes for a single desired label. To formally describe this, we define an informative ILF as:
Definition 3 (Informative ILF). An ILF λj is informative if, for ∀y ∈ Y , there exists Xi ∈ D s.t. the output of λj on Xi is not in N (y,Yλj ), i.e., Ŷ ji ̸∈ N (y,Yλj ).
Testable Conditions for Distinguishability. Based on 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 yi, yj ∈ Y , they are indistinguishable, if and only if tik = tjk for ∀yk ∈ Ŷ .
Theorem 2 provides users with a testable condition: for any pair of unseen labels yi, yj , there should exist at least one seen label yk such that yk has different label relations to yi and yj , i.e., tik ̸= tjk, so that PLRM is able to distinguish yi 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 ILFs to break the symmetry.

heading: 7 EXPERIMENTS
text: 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-shelf label relation structure (Deng et al., 2014; Partalas et al., 2015), which are directed acyclic graphs (DAGS) and from which we could query pairwise label relations. Indeed, there is a one-to-one mapping between a 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 a DAG.

heading: 7.1 SETUP
text: 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.1. We sample data belonging to unseen classes for our experiments and split them into train, validation and test set. For image classification tasks, we follow Mazzetto et al. (2021b;a) to train a branch of image classifiers as supervision sources of seen classes. For text classification tasks, we 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 in App. F.

heading: 7.2 COMPARED METHODS AND RESULTS
text: In addition to the WS-LG baseline, which is an adaptation of Data Programming (Ratner et 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 ŷ predicted by any ILF with the set of desired labels N (ŷ,Y), i.e., 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/nonexclusive label relations. To leverage fine-grained label relations, W-LR-MV attaches a weight to each replaced label. Specifically, if the ILF’s output ŷ is replaced with its ancestor label y (subsumed relation), then the weight of y equals 1, while for the other relations, the weight is 1|Y∗(ŷ)| , where Y∗(ŷ) = {y ∈ Y(ŷ)|tyŷ ̸= tsd}. For the above methods, we compare the performance of (1) directly applying included models on the test set 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 is able to make predictions solely based on attributes without labeled data, by training attribute classifier p(ai|x) for each attribute ai. 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
as 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 on the test set; this shows that the end models are able to generalize beyond the training labels produced by label models.

heading: 7.3 REAL-WORLD APPLICATION
text: In this section, on a commercial advertising system (CAS), we showcase how to reduce human annotation efforts of new labeling tasks by formulating them as WIS problems. In a CAS, ads tagging (classification) is a critical application 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 ILFs. 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 a test set, we 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 as 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.

heading: 8 CONCLUSION
text: 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 error bound of both PLRM and end model. We provide a theoretically-principled sanity test to ensure the distinguishability of unseen labels. Finally, we provide experiments to demonstrate the effectiveness of PLRM and its advantages over baselines on both academic datasets and industrial scenario.
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.

heading: SUPPLEMENTARY MATERIALS FOR “CREATING TRAINING SETS VIA WEAK INDIRECT SUPERVISION”
text: 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, we provide the details of PLRM model. In Appendix C and D, we provide the detailed proofs of Theorem 2 and Theorem 1 respectively. In Appendix E, we provide the detailed examples and illustrations of label graph in WIS. In Appendix F and G, we provide experimental details and additional experiment resulst respectively.

heading: A GLOSSARY OF SYMBOLS

heading: B DETAILS OF THE PLRM
text: We use Y, Ȳ , and Ŷ to represent random vector. Then, we give the formal form of the PLRM as: PΘ(Y, Ȳ , Ŷ ) ∝ exp ( Θ⊤Φ(Y, Ȳ , Ŷ ) ) . (7)
Recall that Y is the unobserved true label, Ȳ is the binary random vector, each of whose binary value Ȳ i reflects whether the data should be assigned seen label ŷi ∈ Ŷ , and Ŷ is the concatenated outputs of ILFs. Specifically, we enumerate Φ as below:
1. (Pseudo accuracy dependency): ∀j ∈ [n], y ∈ Y/{unknown}, ŷ ∈ Yλj , we have ϕAccy,ŷ,j(Y, Ŷ j) := 1{Y = y ∧ Ŷ j = ŷ ∧ ŷ ∈ N (y,Yλj )}1
2. (Accuracy dependency): ∀j ∈ [n], ŷi ∈ Ŷ ∩ Yj we have ϕAccŷi,j(Ȳ
i, Ŷ j) := 1{Ȳ i = 1 ∧ Ŷ j = ŷi} 3. (Label relation dependency between seen labels): ∀ŷi, ŷj ∈ Ŷ, i < j
(a) if tŷiŷj = t e, we have
ϕeŷi,ŷj (Ȳ i, Ȳ j) := − 1{Ȳ i = 1 ∧ Ȳ j = 1}
(b) if tŷiŷj = t o, we have
ϕoŷi,ŷj (Ȳ i, Ȳ j) := 1{Ȳ i = 1 ∧ Ȳ j = 1}
(c) if tŷiŷj = t sg , we have
ϕsgŷi,ŷj (Ȳ i, Ȳ j) := − 1{Ȳ i = 0 ∧ Ȳ j = 1}
(d) if tŷiŷj = t sd, we have
ϕsdŷi,ŷj (Ȳ i, Ȳ j) := − 1{Ȳ i = 1 ∧ Ȳ j = 0}
4. (Label relation dependency between desired and seen labels): ∀y ∈ Y/{unknown}, ŷi ∈ Ŷ (a) if tyŷi = t e, we have
ϕey,ŷi(Y, Ȳ i) := − 1{Y = y ∧ Ȳ i = 1}
(b) if tyŷi = t o, we have
ϕoy,ŷi(Y, Ȳ i) := 1{Y = y ∧ Ȳ i = 1}
(c) if tyŷi = t sg , we have
ϕsgy,ŷi(Y, Ȳ i) := − 1{Y ̸= y ∧ Ȳ i = 1}
(d) if tyŷi = t sd, we have
ϕsdy,ŷi(Y, Ȳ i) := − 1{Y = y ∧ Ȳ i = 0}
And example of our PLRM is shown in Fig. 4, where square with difference colors corresond to different dependency/factor functions in PLRM.
1When ŷ /∈ N (y,Yλj ), ϕ Acc y,ŷ,j is always zero and will not occur in the model. Here we use this form for the
sack of rigorous representation.

heading: C PROOF OF THEOREM 2

heading: C.1 SIMPLIFYING THE NOTATION
text: To simplify the indexing of dependencies, we use Φ1 to represent the concatenation of ϕ which involves both Y and Ȳ , Φ2 to represent the concatenation of ϕ which involve both Y and Λ̂, and Φ3 to represent the concatenation of remaining ϕ which do not involve Y.
Specifically, Φ1 consists of k× k̂ components corresponding to the dependency between the k desired labels and the k̂ seen labels. We use the subscript i, j to denote the dependency function between the desired label yi and seen label ŷj , i.e.,
Φ1i,j = ϕ ? yi,ŷj ,
where ? is the corresponding relation. Similarly, Φ2 consists of k × (∑nj=1 kj) components corresponding to the dependency between the k desired labels and the kj seen labels output by the ILF λj (j ∈ [n]), and we use Φ2i,j,l to denote the dependency of yi and ŷ j l , and Φ 2 i,j = (Φ 2 i,j,l) kj l=1to denote the dependency of yi and ŷ j .
According to Φ1, Φ2, and Φ3, we also divide the parameter Θ into Θ1 (with elements being Θ1i,j correspondingly), Θ2 (with elements being Θ2i,j = (Θ 2 i,j,l) kj l=1 correspondingly), and Θ
3, and the joint probability is then given as:
PΘ(Y, Ȳ , Ŷ ) = exp
( (Θ1)TΦ1(Y, Ȳ ) + (Θ2)⊤Φ2(Y, Ŷ ) + (Θ3)TΦ3(Ȳ , Ŷ ) ) ∑
Y ′,Ȳ ′,Ŷ ′ exp ( (Θ1)⊤Φ1(Y ′, Ȳ ′) + (Θ2)⊤Φ2(Y ′, Ŷ ′) + (Θ3)TΦ3(Ȳ ′, Ŷ ′) ) (8) Also, for notation convenience, we adopt following simplifications:
1. ∀yi ∈ Y → ∀i ∈ [k] since |Y| = k, similarly, ∀ŷi ∈ Yj → ∀i ∈ [kj ] and ∀ŷi ∈ Ŷ → ∀i ∈ [k̂];
2. ∀λj → ∀j ∈ [n] since we have n ILFs in total;
3. ϕ tyiyj yi,yj → ϕtyi,yj where t = tyiyj and can be seen from the subscript of the dependency.

heading: C.2 PROPOSITIONS AND LEMMAS
text: First, we state some propositions and lemmas that will be useful in the proof to come.
Proposition 1 (Multi-class classification). For a multi-class classification task, ∀yi, yj ∈ Y , we have tyiyj = t
e. Similarly, ∀ŷa, ŷb ∈ Ŷ , we have tŷaŷb = te. Lemma 1. For a consistent label graph G and ∀ŷl ∈ Ŷ,∀yi, yj ∈ Y , if tyiŷl = to, we have tyj ŷl ̸= tsg .
Proof. For ∀yi, yj ∈ Y , based on Proposition 1, we know tyiyj = te, which implies (1) the intersection of the sets labeled by yi and yj is empty. For ∀ŷl ∈ Ŷ , if tyiŷl = to, we have (2) the intersection of the sets labeled by yi and ŷl is not empty. If tyj ŷl = t
sg, which implies (3) yj ⫌ ŷl. Based on (2)(3), we have yi ∩ yj ̸= ∅, which is contradictory to (1). Thus, we prove when tyiŷl = t
o, tyj ŷl ̸= tsg . Lemma 2. For an informative ILF λj and given any yd ∈ Y , there exists some ŷl ∈ Yj , such that, Φ2d,j,l(yd, ŷ) = 0, ∀l ∈ [kj ].
Proof. Because ILF λj is informative, we know there exists one ŷa ∈ Yj such that ŷa is exclusive to yd, i.e., ŷa /∈ N (yd,Yj). Therefore, for any ŷl ∈ Ŷ , either ŷa ̸= ŷl, or ŷl = ŷa /∈ Yj , which leads to the conclusion by the definition of Φ2d,j,l = ϕ Acc yd,ŷl,j .

heading: C.3 DEFINITIONS
text: Before the main proof, we connect the indistinguishablity of label relation structure with the dependency structure of PLRM by introducing the concept of symmetry as follows:
Definition 4 (Symmetry). For yi, yj ∈ Y , we say yi and yj have symmetric dependency structure if the following equation holds:
Φ1i,l = Φ 1 j,l,∀l ∈ k̂;
Φ2i,a,b = Φ 2 j,a,b,∀a ∈ [n], b ∈ [ka]. (9)
Based on the construction of PLRM, we know that for ∀yi, yj ∈ Y,∀ŷb ∈ Ŷ , tyiŷb = tyj ŷb (the statement in Theorem 2) is equivalent to yi and yj have symmetric dependency structure.

heading: C.4 EQUIVALENT STATEMENT OF THEOREM 2
text: Our main result states that asymmetric is equivalent to distinguishable as in the following theorem, which can readily be seen to be identical to Theorem 2 in the main body of 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 yi, yj ∈ Y , yi and yj are distinguishable if and only if they have asymmetric dependency structure.

heading: C.5 PROOF OF THE NECESSITY IN THEOREM 3: NECESSARY CONDITION
text: We first prove that for any yi, yj ∈ Y , yi 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 yi and yj are symmetric. Then, by Eq. (8), the distribution of Y condition on any Ȳ and Ŷ can be calculated as follows:
PΘ(Y = yi|Ȳ , Ŷ ) = PΘ(yi, Ȳ , Ŷ ) PΘ(Ȳ , Ŷ ) .
On the other hand, applying Y = yi in the definition of Φ2 leads to
Φ2r,a,l(yi, ·) = 0,∀r ∈ [k], r ̸= i,∀a ∈ [n],∀l ∈ [ka].
We further separate Φ1 into (Φ1i ) k i=1, where Φ 1 i collects all the dependency in Φ 1 with yi involved, i.e.,
Φ1i = (Φ 1 i,j) k̂ j=1,
with the corresponding parameters respectively denoted as Θ1i with Θ 1 = (Θ1i ) k i=1. Similarly, Φ 2 is also divided into (Φ2i ) k i=1 following the same routine and Θ 2 is respectively divided into (Θ2i ) k i=1. Specifically, if yi and yj are symmetric, we further have
Φ1i = Φ 1 j ,Φ 2 i = Φ 2 j .
Based on the notation, PΘ(Y = yi|Ȳ , Ŷ ) can then be represented as PΘ(Y = yi|Ȳ , Ŷ ) (∑
Y ′
exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ ) + (Θ3)TΦ3(Ȳ , Ŷ )
))
=exp
( k∑
l=1
(Θ1l ) TΦ1l (yi, Ȳ ) + k∑ l=1 (Θ2l ) TΦ2l (yi, Ŷ ) + (Θ 3)TΦ3(Ȳ , Ŷ )
)
which further leads to PΘ(Y = yi|Ȳ , Ŷ ) (∑
Y ′
exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ )
))
=exp
( k∑
l=1
(Θ1l ) TΦ1l (yi, Ȳ ) + (Θ 2 i ) TΦ2i (yi, Ŷ )
) (10)
which is independent of Θ3. Similarly, PΘ(Y = yj |Ȳ , Ŷ ) (∑
Y ′
exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ )
))
=exp
( k∑
l=1
(Θ1l ) TΦ1l (yi, Ȳ ) + (Θ 2 j ) TΦ2j (yj , Ŷ )
) (11)
and ∀l ∈ [k]/{i, j}, PΘ(Y = yl|Ȳ , Ŷ ) (∑
Y ′
exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ )
))
=exp
( k∑
l=1
(Θ1l ) TΦ1l (yi, Ȳ ) + (Θ 2 l ) TΦ2l (yl, Ŷ )
) (12)
Let Θ̃ be defined as follows:
Θ̃1i = Θ 1 j , Θ̃ 1 j = Θ 1 i , Θ̃ 1 l = Θ 1 l ,∀l /∈ {i, j},
Θ̃2i = Θ 2 j , Θ̃ 2 j = Θ 2 i , Θ̃ 2 l = Θ 2 l ,∀l /∈ {i, j},
and Θ̃3 = Θ3.
We then have
PΘ(Y = yi|Ȳ , Ŷ ) PΘ̃(Y = yj |Ȳ , Ŷ )
=
(∑ Y ′ exp ( (Θ̃1)⊤Φ1(Y ′, Ȳ ) + (Θ̃2)⊤Φ2(Y ′, Ŷ ) )) (∑
Y ′ exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ ) )) · exp ((Θ1i )T(Φ1i (yi, Ȳ )− Φ1j (yj , Ȳ )) + (Θ1j )T(Φ1j (yi, Ȳ )− Φ1i (yj , Ȳ )) + (Θ2i )T(Φ2i (yi, Ŷ )− Φ2j (yj , Ŷ )))
=
(∑ Y ′ exp ( (Θ̃1)⊤Φ1(Y ′, Ȳ ) + (Θ̃2)⊤Φ2(Y ′, Ŷ ) )) (∑
Y ′ exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ ) )) . Similarly,
PΘ(Y = yj |Ȳ , Ŷ ) PΘ̃(Y = yi|Ȳ , Ŷ )
=
(∑ Y ′ exp ( (Θ̃1)⊤Φ1(Y ′, Ȳ ) + (Θ̃2)⊤Φ2(Y ′, Ŷ ) )) (∑
Y ′ exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ ) )) · exp ((Θ1j )T(Φ1j (yj , Ȳ )− Φ1i (yi, Ȳ )) + (Θ1i )T(Φ1i (yj , Ȳ )− Φ1j (yi, Ȳ )) + (Θ2j )T(Φ2j (yj , Ŷ )− Φ2i (yi, Ŷ )))
=
(∑ Y ′ exp ( (Θ̃1)⊤Φ1(Y ′, Ȳ ) + (Θ̃2)⊤Φ2(Y ′, Ŷ ) )) (∑
Y ′ exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ ) )) .
and ∀l ∈ [k]/{i, j},
PΘ(Y = yl|Ȳ , Ŷ ) PΘ̃(Y = yl|Ȳ , Ŷ ) =
(∑ Y ′ exp ( (Θ̃1)⊤Φ1(Y ′, Ȳ ) + (Θ̃2)⊤Φ2(Y ′, Ŷ ) )) (∑
Y ′ exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ ) )) . Similarly, we have
PΘ(Y = unknown|Ȳ , Ŷ ) PΘ̃(Y = unknown|Ȳ , Ŷ ) =
(∑ Y ′ exp ( (Θ̃1)⊤Φ1(Y ′, Ȳ ) + (Θ̃2)⊤Φ2(Y ′, Ŷ ) )) (∑
Y ′ exp ( (Θ1)⊤Φ1(Y ′, Ȳ ) + (Θ2)⊤Φ2(Y ′, Ŷ ) )) . Therefore, we have
PΘ(Y = yi|Ȳ , Ŷ ) PΘ̃(Y = yj |Ȳ , Ŷ ) = PΘ(Y = yj |Ȳ , Ŷ ) PΘ̃(Y = yi|Ȳ , Ŷ ) = PΘ(Y = y|Ȳ , Ŷ ) PΘ̃(Y = y|Ȳ , Ŷ ) ,∀y ∈ Y/{yi, yj}.
Since PΘ(Y = yi|Ȳ , Ŷ ) + PΘ(Y = yj |Ȳ , Ŷ ) + ∑ l ̸=i,j PΘ(Y = yl|Ȳ , Ŷ ) = 1,
and PΘ̃(Y = yj |Ȳ , Ŷ ) + PΘ̃(Y = yi|Ȳ , Ŷ ) + ∑ l ̸=i,j PΘ̃(Y = yl|Ȳ , Ŷ ) = 1,
we obtain that PΘ(Y = yi|Ȳ , Ŷ ) = PΘ̃(Y = yj |Ȳ , Ŷ ) PΘ(Y = yj |Ȳ , Ŷ ) = PΘ̃(Y = yi|Ȳ , Ŷ ) PΘ(Y = yl|Ȳ , Ŷ ) = PΘ̃(Y = yl|Ȳ , Ŷ ),
which indicates yi and yj indistinguishable, and leads to a contradictory.
The proof is completed.

heading: C.6 PROOF OF THEOREM 3: SUFFICIENT CONDITION
text: We then prove that for any yi, yj ∈ Y , yi and yj have asymmetric dependency structure is the sufficient condition of that they are distinguishable.
Proof. We use the same notations (Θ1i ) k i=1, (Θ 2 i ) k i=1, and Θ 3 in Appendix C.5 to denote the separation of the parameter Θ. 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 ∀r ∈ [k], r ̸= i, j,
exp ((Θ1i ) TΦ1i (yi, Ȳ ) + (Θ 1 j ) TΦ1j (yi, Ȳ ) + (Θ 2 i ) TΦ2i (yi, Ŷ ))
exp ((Θ̃1i ) TΦ1i (yj , Ȳ ) + (Θ̃ 1 j ) TΦ1j (yj , Ȳ ) + (Θ̃ 2 j ) TΦ2j (yj , Ŷ ))
= exp ((Θ1i ) TΦ1i (yj , Ȳ ) + (Θ 1 j ) TΦ1j (yj , Ȳ ) + (Θ 2 j ) TΦ2j (yj , Ŷ ))
exp ((Θ̃1i ) TΦ1i (yi, Ȳ ) + (Θ̃ 1 j ) TΦ1j (yi, Ȳ ) + (Θ̃ 2 i ) TΦ2i (yi, Ŷ ))
= exp ((Θ1i ) TΦ1i (yr, Ȳ ) + (Θ 1 j ) TΦ1j (yr, Ȳ ))
exp ((Θ̃1i ) TΦ1i (yr, Ȳ ) + (Θ̃ 1 j ) TΦ1j (yr, Ȳ )) =
exp ((Θ1i ) TΦ1i (yj , Ȳ ) + (Θ 1 j ) TΦ1j (yi, Ȳ ))
exp ((Θ̃1i ) TΦ1i (yj , Ȳ ) + (Θ̃ 1 j ) TΦ1j (yi, Ȳ )) .
By simple rearranging, we have
((Θ1i ) TΦ1i (yi, Ȳ ) + (Θ 1 j ) TΦ1j (yi, Ȳ ) + (Θ 2 i ) TΦ2i (yi, Ŷ ) + (Θ 2 j ) TΦ2j (yi, Ŷ ))
− ((Θ̃1i )TΦ1i (yj , Ȳ ) + (Θ̃1j )TΦ1j (yj , Ȳ ) + (Θ̃2i )TΦ2i (yj , Ŷ ) + (Θ̃2j )TΦ2j (yj , Ŷ )) =((Θ1i ) TΦ1i (yj , Ȳ ) + (Θ 1 j ) TΦ1j (yj , Ȳ ) + (Θ 2 i ) TΦ2i (yj , Ŷ ) + (Θ 2 j ) TΦ2j (yj , Ŷ ))
− ((Θ̃1i )TΦ1i (yi, Ȳ ) + (Θ̃1j )TΦ1j (yi, Ȳ ) + (Θ̃2i )TΦ2i (yi, Ŷ ) + (Θ̃2j )TΦ2j (yi, Ŷ )) =((Θ1i ) TΦ1i (yj , Ȳ ) + (Θ 1 j ) TΦ1j (yi, Ȳ ))− ((Θ̃1i )TΦ1i (yj , Ȳ ) + (Θ̃1j )TΦ1j (yi, Ȳ )). (13)
By the equality between the second term and the third term in Eq. (13), we obtain that
(Θ1j ) TΦ1j (yi, Ȳ )− (Θ̃1i )TΦ1i (yj , Ȳ )
=((Θ1j ) TΦ1j (yj , Ȳ ) + (Θ 2 j ) TΦ2j (yj , Ŷ ))− ((Θ̃1i )TΦ1i (yi, Ȳ ) + (Θ̃2i )TΦ2i (yi, Ŷ )). (14)
We further set Ȳ in Eq. (14) respectively to el (the one hot vector with its l-th position being 1) and 0 for any fixed l ∈ [k̂], i.e.,
((Θ1j ) TΦ1j (yi, el)− (Θ1j )TΦ1j (yi,0))− ((Θ̃1i )TΦ1i (yj , el)− (Θ̃1i )TΦ1i (yj ,0))
=((Θ1j ) TΦ1j (yj , el)− (Θ1j )TΦ1j (yj ,0))− ((Θ̃1i )TΦ1i (yi, el)− (Θ̃1i )TΦ1i (yi,0)),
which by simple rearranging further leads to
Θ1j,l(Φ 1 j,l(yj , 1)− Φ1j,l(yj , 0)− Φ1j,l(yi, 1)) = Θ̃1i,l(Φ1i,l(yi, 1)− Φ1i,l(yi, 0)− Φ1i,l(yj , 1)).
Since Θ1j,l, Θ̃ 1 i,l > 0, and by definition we have
|Φ1j,l(yj , 1)− Φ1j,l(yj , 0)− Φ1j,l(yi, 1)| = 1, and |Φ1i,l(yi, 1)− Φ1i,l(yi, 0)− Φ1i,l(yj , 1)| = 1, we obtain Θ1j,l = Θ̃ 1 i,l, and
Φ1j,l(yj , 1)− Φ1j,l(yj , 0)− Φ1j,l(yi, 1) = Φ1i,l(yi, 1)− Φ1i,l(yi, 0)− Φ1i,l(yj , 1). (15)
Therefore, either tyj ŷl ∈ {to, tsd, tsg} and tyiŷl ∈ {to, tsd, tsg}, or tyj ŷl = te and tyiŷl = te, which by definition further indicates that Φ2i = Φ 2 j (recall the way we build dependency between Y and Ŷ ).
As l is arbitrarily picked, we then have Θ1j is equal to Θ̃ 1 i 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 Θ̃1j = Θ 1 i .
On the other hand, for any r ∈ [k̂], fixing Ȳ and Ŷ s (∀s ̸= r), and setting Ŷr = ŷrl (l ∈ kr, ŷrl ∈ N (yj ,Yl)) in Eq. (14), we have
(Θ1j ) TΦ1j (yj , Ȳ ) + (Θ̃ 1 i ) TΦ1i (yj , Ȳ ) + Θ 2 j,r,lΦ 2 j,r,l(yj , ŷ r l ) + ∑ s ̸=r Θ2j,sΦ 2 j,s(yj , Y s)
=(Θ1j ) TΦ1j (yi, Ȳ ) + (Θ̃ 1 i ) TΦ1i (yi, Ȳ ) + Θ̃ 2 i,r,lΦ 2 i,r,l(yi, ŷ r l ) + ∑ s ̸=r Θ̃2i,sΦ 2 i,s(yi, Ŷ s).
On the other hand, by Lemma 2, there exists some p, s.t., ŷrp /∈ N (yj ,Yr) (which by Φ2i = Φ2j further leads to ŷrp /∈ N (yi,Yr)). Setting Ŷr = ŷrl leads to
(Θ1j ) TΦ1j (yj , Ȳ ) + (Θ̃ 1 i ) TΦ1i (yj , Ȳ ) + ∑ s̸=r Θ2j,sΦ 2 j,s(yj , Y s)
=(Θ1j ) TΦ1j (yi, Ȳ ) + (Θ̃ 1 i ) TΦ1i (yi, Ȳ ) + ∑ s̸=r Θ̃2i,sΦ 2 i,s(yi, Ŷ s).
Subtracting the above two equations leads to Θ2j,a,l = Θ̃ 2 i,a,l. Since a and l are arbitrarily picked, we conclude that Θ2j = Θ̃ 2 i . Following the same routine, we also have Θ 2 i = Θ̃ 2 j .
Therefore, by applying Θ1j = Θ̃ 1 i , Θ 1 i = Θ̃ 1 j , Θ 2 j = Θ̃ 2 i , and Θ 2 i = Θ̃ 2 j in Eq. (13), we have
(Θ1i ) TΦ1i (yi, Ȳ )− (Θ1i )TΦ1j (yj , Ȳ ) = (Θ1i )TΦ1i (yj , Ȳ )− (Θ1i )TΦ1j (yi, Ȳ ),
(Θ1j ) TΦ1j (yj , Ȳ )− (Θ1j )TΦ1i (yi, Ȳ ) = (Θ1j )TΦ1j (yi, Ȳ )− (Θ1j )TΦ1i (yj , Ȳ ).
Let Ȳ = 1k̂ (i.e., the k̂-dimension all 1 vector), we have
(Θ1i ) T((Φ1i (yi,1k̂)− Φ1i (yj ,1k̂))− ((Φ1j (yj ,1k̂)− Φ1j (yi,1k̂)))) = 0, (16)
(Θ1j ) T((Φ1i (yi,1k̂)− Φ1i (yj ,1k̂))− ((Φ1j (yj ,1k̂)− Φ1j (yi,1k̂)))) = 0. (17)
Since yi and yj are asymmetric, we have that there exists l, such that tyiŷl ̸= tyj ŷl . Concretely, by Eq. (15), we have tyiŷl ∈ {to, tsd, tsg}, tyj ŷl = {to, tsd, tsg}, and tyiŷl ̸= tyj ŷl . On the other hand,
Φ1i,l(yi, 1)− Φ1i,l(yj , 1)) = Φ1j,l(yj , 1)− Φ1j,l(yi, 1), if and only if tyiŷl = t o, tyj ŷl = t sg , or tyj ŷl = t o, tyiŷl = t sg , which contradicts Lemma 1.
Therefore, Φ1i,l(yi, 1)− Φ1i,l(yj , 1)) ̸= Φ1j,l(yj , 1)− Φ1j,l(yi, 1).
In this case, solutions of Θ1i ,Θ 1 j subject to respectively Eqs. (16) and (17) lie along a zero-measure set.
The proof is completed.

heading: D PROOF OF THEOREM 1

heading: D.1 LEARNING ALGORITHM
text: We first present the algorithm for producing Θ̂ and Ŵ in Algorithm 1.
Algorithm 1 WIS Require: Step size η, dataset D ⊂ X , and initial parameter Θ0. Θ̂→ Θ0. for all X ∈ D do
Independently sample (Y, Ȳ , Ŷ ) from πΘ̂, and (Y ′, Ȳ ′, Ŷ ′) from πΘ̂ conditionally given Ŷ ′ = Ŷ (X). Θ̂← Θ̂ + η(Φ(Y, Ȳ , Ŷ )− Φ(Y ′, Ȳ ′, Ŷ ′)).
Compute Ŵ as described in (3) using Θ̂. output (Θ̂, Ŵ )

heading: D.2 ASSUMPTIONS
text: First, the problem distribution π∗ needs to be accurately modeled by some distribution Θ∗ in the family that we are trying to learn:
∃Θ∗ s.t. ∀(Y, Ŷ ), p(X,Y )∼π∗(Y, Ŷ ) = pθ∗(Y, Ŷ ). (18)
Secondly, given an example (X,Y ) ∼ π∗, we assume Y is independent of X given Ŷ (X): (X,Y ) ∼ π∗ ⇒ Y ⊥ X | Ŷ (X). (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 Θ, accurately learning Θ from data distribution is possible. That is, there exists an unbiased estimator Θ̂(D) which is a function of the dataset D of i.i.d from πΘ, such that, for any Θ and some c > 0,
Cov(Θ̂(D)) ⪯ I 2c|D| . (20)
And we are reasonably certain in our guess of latent variables, i.e., Y and Ȳ . That is, for any Θ,Θ∗,
EŶ ∗∼Θ∗
[ k∑
i=1
(ni + k̂)Var(Y,Ȳ ,Ŷ )∼πΘ(1Y =yi |Ŷ = Ŷ ∗)2 + k̂∑ i=1 (mi +K − 1)Var(Y,Ȳ ,Ŷ )∼πΘ(Ȳ i|Ŷ = Ŷ ∗)2
] 1 2
≤ c√ 2M . (21)
We also assume that the output of the last layer of end model hW has bounded ℓ∞ norm, that is, for any possible parameter W ,
∥hW ∥∞ ≤ H. (22)
Finally, we assume that solving Eq. (3) has bounded generalization risk such that for some χ > 0, solution Ŵ satisfies EŴ [ ℓΘ̂(Ŵ )−min
W ℓΘ̂(W )
] ≤ χ. (23)

heading: D.3 PROOF OF THEOREM 1
text: To begin with, we state two basic lemmas needed for proofs throughout this section: Lemma D.1. Let x1, x2 be two binary random variable. Then we have variance of product of x1 and x2 can be bounded as
Var [x1x2] ≤ Var [x1] +Var [x2] . Lemma D.2. Let Y be a random vector and ∥·∥s be the spectral norm. Then we have
∥Cov(Y, Y )∥s ≤ ∑ i Var(Yi).
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.1 in (Ratner et al., 2016)] Given a family of maximum-entropy distributions
πΘ(Y, Ȳ , Ŷ ) = 1
ZΘ exp (ΘTΦ(Y, Ȳ , Ŷ )).
If we let J be the maximum expected log-likelihood objective, under another distribution π∗, for the event associated with the observed labeling function values Ŷ ,
J(Θ) = E(Y ∗,Ȳ ∗,Ŷ ∗)∼π∗ [ logP(Y,Ȳ ,Ŷ )∼πΘ ( Ŷ = Ŷ ∗ )] ,
then its Hessian can be calculated as ∇2J(Θ) = E(Y ∗,Ȳ ∗,Ŷ ∗)∼π∗ [ Cov(Y,Ȳ ,Ŷ )∼πΘ ( ϕ(Y, Ȳ , Ŷ ) | Ŷ = Ŷ ∗ )] −Cov(Y,Ȳ ,Ŷ )∼πΘ(ϕ(Y, Ȳ , Ŷ )).
Lemma D.4. [Lemma D.4 in (Ratner et al., 2016)] Suppose that we are looking at a WIS maximum likelihood estimation problem and the objective function J(Θ) is strongly concave with concavity parameter c > 0. If we run stochastic gradient descent using unbiased samples from a true distribution πΘ∗ , then if we set step size as
η = cϵ2
4 ,
and run (using a fresh sample at each iteration) for T steps, where
T = 2
c2ϵ2 log
( 2 ∥Θ0 −Θ∗∥2
ϵ
) .
We can bound the expected parameter estimation error with E ∥∥∥Θ̂−Θ∗∥∥∥2 ≤Mϵ2, (24)
where M is the dimension of Θ.
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(Θ)2 is strongly concave. We prove this through the following lemma, which is a 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 to (Ratner et al., 2016):
2Note that, in the Eq. (2) of the main body of the paper, we are minimizing −J(Θ), which is equivalent to maximizing J(Θ) as discussed here.
Lemma D.5. [Extension of Lemma D.3 in (Ratner et al., 2016)] With conditions (20) and (21), the WIS objective function J(Θ) is strongly concave with strong convexity c.
We then come to 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 ℓ(W ∗) be the minimum of cross entropy loss function ℓ. Then, we can bound the expected risk with
E [ ℓ(Ŵ )− ℓ(W ∗) ] ≤ χ+ 4cHϵ.
Finally, we conclude Lemmas (D.4), (D.5) and (D.6) as the following theorem, which is identical to the Theorem 1 in the main body of the paper:
Theorem 4 (Extension of Theorem 2 in (Ratner et al., 2016)). Suppose that we run Algoirthm 1 on a

heading: WIS specification to produce Θ̂ and Ŵ , and all conditions of Lemmas (D.5) and (D.6) are satisfied.
text: Then, for any ϵ > 0, if we set the step size to be
η = cϵ2
4
and the input dataset D is large enough such that
|D| > 2 c2ϵ2 log
( 2 ∥Θ0 −Θ∗∥2
ϵ
) ,
then we can bound the expected parameter error and the expected risk as: E ∥∥∥Θ̂−Θ∗∥∥∥2 ≤Mϵ2, E [ℓ(Ŵ )− ℓ(W ∗)] ≤ χ+ 4cHϵ.

heading: D.4 PROOFS OF LEMMAS
text: Lemma D.1. Let x1, x2 be two binary random variable. Then we have variance of product of x1 and x2 can be bounded as
Var [x1x2] ≤ Var [x1] +Var [x2] .
Proof. Joint distribution of x1 and x2 can be listed as the following table: (where p1+p2+p3+p4 = 1)
x1/x2 0 1 0 p1 p2 1 p3 p4
Then we have Var [x1x2] = p4 − p24 = p4(p1 + p2 + p3),
while
Var [X1] +Var [X2] = (p2 + p4)(p1 + p3) + (p3 + p4)(p1 + p2) ≥ p4(p1 + p2 + p3).
The proof is completed.
Lemma D.2. Let Y be a random vector and ∥·∥s be the spectral norm. Then we have
∥Cov(Y, Y )∥s ≤ ∑ i Var(Yi).
Proof. By definition of spectral norm, we have
∥Cov(Y, Y )∥s = max∥x∥2≤1 xTCov(Y, Y )x
Where x is a constant vector. And by Cauchy-Schwarz inequality,
xTCov(Y, Y )x = E [ xT(Y − E [Y ])(Y − E [Y ])Tx ] ≤ E [ ∥x∥2 ∥Y − E [Y ]∥2 ] .
Because x is a constant vector and ∥x∥ ≤ 1,
max ∥x∥2≤1
E [ ∥x∥2 ∥Y − E [Y ]∥2 ] = max
∥x∥2≤1 ∥x∥2 E
[ ∥Y − E [Y ]∥2 ] = max
∥x∥2≤1 ∥x∥2 [∑ i Var(Yi) ] = ∑ i Var(Yi).
The proof is completed.
Lemma D.5. [Extension of Lemma D.3 in (Ratner et al., 2016)] With conditions (20) and (21), the WIS objective function J(Θ) is strongly concave with strong convexity c.
Proof. By Lemma D.3, hessian matrix of J can be decomposed as follows: ∇2J(Θ) = EŶ ∗∼πΘ∗ [ Cov(Y,Ȳ ,Ŷ )∼πΘ ( Φ(Y, Ȳ , Ŷ ) | Ŷ = Ŷ ∗ )] −Cov(Y,Ȳ ,Ŷ )∼πΘ(Φ(Y, Ȳ , Ŷ )).
Basically, to prove that J(Θ) is strongly concave with strong convexity c, we need to show for a real number c > 0,
∇2J(Θ) ⪯ cI.
We calculate each term separately: for the first term
A = EŶ ∗∼πΘ∗ [ Cov(Y,Ȳ ,Ŷ )∼πΘ ( Φ(Y, Ȳ , Ŷ ) | Ŷ = Ŷ ∗ )] ,
since A is symmetric, for any real number c, A ⪯ cI, if and only if its spectral norm ∥A∥s ≤ c, where ∥A∥s equals to the eigenvalue of A with largest absolute value. Since by definition, vector function Φ(Y, Ȳ , Ŷ ) can be represented as:
Φ(Y, Ȳ , Ŷ ) =  ( ϕAcc yi,ŷ j l ,j (Y, Ŷ j) ) i∈[k],j∈[n],ŷjl ∈N (yi,Yj)( ϕAccŷi,j(Ȳ i, Ŷ j) ) j∈[n],ŷi∈Yj( ϕtŷi,ŷj (Ȳ i, Ȳ j) ) i,j∈[k̂](
ϕtyi,ŷj (Y, Ȳ j) ) i∈[k],j∈[k̂]
 ,
by Lemma D.2, we have A can be further bounded by
A ≤ EŶ ∗∼πΘ∗  k∑
i=1 n∑ j=1 ∑ ŷjl ∈N (yi,Yj) Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕAcc yi,ŷ j l ,j
(Y, Ŷ j) | Ŷ = Ŷ ∗ )
+ EŶ ∗∼πΘ∗  n∑ j=1 ∑ ŷi∈Yj Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕAccŷi,j(Ȳ i, Ŷ j) | Ŷ = Ŷ ∗ )
+ EŶ ∗∼πΘ∗  ∑ 1≤i,j≤k̂ Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕtŷi,ŷj (Ȳ i, Ȳ j) | Ŷ = Ŷ ∗ )
+ EŶ ∗∼πΘ∗  k∑ i=1 k̂∑ j=1 Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕtyi,ŷj (Y, Ȳ j) | Ŷ = Ŷ ∗ )
=A1 +A2 +A3 +A4,
where
A1 =EŶ ∗∼πΘ∗  k∑ i=1 n∑ j=1 ∑ ŷjl ∈N (yi,Yj) Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕAcc yi,ŷ j l ,j (Y, Ŷ j) | Ŷ = Ŷ ∗ ) ;
A2 =EŶ ∗∼πΘ∗  n∑ j=1 ∑ ŷl∈Yj Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕAccŷl,j(Y, Ŷ j) | Ŷ = Ŷ ∗ ) ;
A3 =EŶ ∗∼πΘ∗  ∑ 1≤i,j≤k̂ Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕtŷi,ŷj (Ȳ i, Ȳ j) | Ŷ = Ŷ ∗ ) ;
A4 =EŶ ∗∼πΘ∗  k∑ i=1 k̂∑ j=1 Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕtyi,ŷj (Y, Ȳ j) | Ŷ = Ŷ ∗ ) .
We then bound the four terms respectively. As for A1, for fixed Ŷ ∗, we have k∑
i=1 n∑ j=1 ∑ ŷjl ∈N (yi,Yj) Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕAcc yi,ŷ j l ,j (Y, Ŷ j) | Ŷ = Ŷ ∗ )
= k∑ i=1 n∑ j=1 ∑ ŷjl ∈N (yi,Yj) Var(Y,Ȳ ,Ŷ )∼πΘ ( 1Y=yi∧Ŷ j=ŷjl | Ŷ = Ŷ ∗ )
= k∑ i=1  ∑ j∈[n],ŷjl ∈N (yi,Yj),(Ŷ ∗)j=ŷ j l Var(Y,Ȳ ,Ŷ )∼πΘ ( 1Y=yi | Ŷ = Ŷ ∗ ) =
k∑ i=1  ∑ j∈[n],ŷjl ∈N (yi,Yj),(Ŷ ∗)j=ŷ j l Var(Y,Ȳ ,Ŷ )∼πΘ ( 1Y=yi | Ŷ = Ŷ ∗ ) ≤
k∑ i=1 niVar(Y,Ȳ ,Ŷ )∼πΘ ( 1Y=yi | Ŷ = Ŷ ∗ ) ,
where ni is the number of ILFs whose label space contains label that is non-exclusive to label yi, i.e., ni = |{j ∈ [n]|N (yi,Yj) ̸= ∅}|. Therefore, we have
A1 ≤ k∑
i=1
niEŶ ∗∼πΘ∗Var(Y,Ȳ ,Ŷ )∼πΘ ( 1Y=yi | Ŷ = Ŷ ∗ ) .
Similarly, for A2, we have
A2 ≤ k̂∑
i=1
miEŶ ∗∼πΘ∗Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ i | Ŷ = Ŷ ∗ ) ,
where mi is the number of ILFs whose label space contains the label ŷi.
As for A3, for fixed Ŷ ∗ and any ŷi, ŷj ∈ Ŷ , we further separate the proof into subcases by tŷiŷj which is simplified as t:
(1). t = to. In this case,
Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕtŷi,ŷj (Ȳ i, Ȳ j) | Ŷ = Ŷ ∗ )
=Var(Y,Ȳ ,Ŷ )∼πΘ
( 1Ȳ i=Ȳ j | Ŷ = Ŷ ∗ ) =Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ iȲ j | Ŷ = Ŷ ∗
) (∗) ≤Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ i | Ŷ = Ŷ ∗ ) +Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ j | Ŷ = Ŷ ∗ ) ,
where Eq. (∗) is due to Lemma D.1. (2). t = te. Similarly,
Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕtŷi,ŷj (Ȳ i, Ȳ j) | Ŷ = Ŷ ∗ )
=Var(Y,Ȳ ,Ŷ )∼πΘ
( −1Ȳ i=Ȳ j=1 | Ŷ = Ŷ ∗ ) =Var(Y,Ȳ ,Ŷ )∼πΘ ( 1Ȳ i=Ȳ j=1 | Ŷ = Ŷ ∗
) =Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ iȲ j | Ŷ = Ŷ ∗
) ≤Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ i | Ŷ = Ŷ ∗ ) +Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ j | Ŷ = Ŷ ∗ ) ,
(3). t = tsg . In this case,
Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕtŷi,ŷj (Ȳ i, Ȳ j) | Ŷ = Ŷ ∗ )
=Var(Y,Ȳ ,Ŷ )∼πΘ
( −1Ȳ i=1,Ȳ j=0 | Ŷ = Ŷ ∗ ) =Var(Y,Ȳ ,Ŷ )∼πΘ ( (1− Ȳ i)Ȳ j | Ŷ = Ŷ ∗
) ≤Var(Y,Ȳ ,Ŷ )∼πΘ ( 1− Ȳ i | Ŷ = Ŷ ∗ ) +Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ j | Ŷ = Ŷ ∗
) =Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ i | Ŷ = Ŷ ∗ ) +Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ j | Ŷ = Ŷ ∗ ) ,
(4). t = tsd. Similar to (3).,
Var(Y,Ȳ ,Ŷ )∼πΘ ( ϕtŷi,ŷj (Ȳ i, Ȳ j) | Ŷ = Ŷ ∗ )
=Var(Y,Ȳ ,Ŷ )∼πΘ
( −1Ȳ i=0,Ȳ j=1 | Ŷ = Ŷ ∗ ) =Var(Y,Ȳ ,Ŷ )∼πΘ ( (1− Ȳ j)Ȳ i | Ŷ = Ŷ ∗
) ≤Var(Y,Ȳ ,Ŷ )∼πΘ ( 1− Ȳ j | Ŷ = Ŷ ∗ ) +Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ i | Ŷ = Ŷ ∗
) =Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ i | Ŷ = Ŷ ∗ ) +Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ j | Ŷ = Ŷ ∗ ) ,
Combining (1), (2), (3), and (4), we have
A3 ≤ k̂∑
i=1
(k̂ − 1)EŶ ∗∼πΘ∗Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ i | Ŷ = Ŷ ∗ ) ,
As for A4, by similar discussion of A3, A4 ≤ k̂∑
i=1
kEŶ ∗∼πΘ∗Var(Y,Ȳ ,Ŷ )∼πΘ ( Ȳ i | Ŷ = Ŷ ∗ ) + k∑ i=1 k̂EŶ ∗∼πΘ∗Var(Y,Ȳ ,Ŷ )∼πΘ ( 1Y=yi | Ŷ = Ŷ ∗ ) .
Combining estimation of A1, A2, A3, A4, and by condition (21) we have
∥A∥s ≤A1 +A2 +A3 +A4
≤EŶ ∗∼πΘ∗  k∑ i=1 (ni + k̂)VarY,Ŷ (1Y=yi |Ŷ = Ŷ ∗) + k̂∑ i=1 (mi +K − 1)VarY,Ŷ (Ȳ i|Ŷ = Ŷ ∗)  ≤EŶ ∗∼πΘ∗  k∑ i=1 (ni + k̂)Var 2 Y,Ŷ (Y |Ŷ = Ŷ ∗) + k̂∑ i=1 (mi +K − 1)Var2Y,Ŷ (Ȳ i|Ŷ = Ŷ ∗)  12
· (
k∑ i=1 (ni + k̂) + K∑ i=1
(mi +K − 1) ) 1 2
≤ c√ 2M · √ 2M ≤ c,
which further leads to A ⪯ cI.
For the second term B = Cov(Y,Ȳ ,Ŷ )∼πΘ(Φ(Y, Ȳ , Ŷ )), B = E(Y,Ȳ ,Ŷ )∼πΘ [ (Φ(Y, Ȳ , Ŷ )− E(Y,Ȳ ,Ŷ )∼πΘ [Φ(Y, Ȳ , Ŷ )]) 2 ]
= EY,Ȳ ,Ŷ∼πΘ
 Φ(Y, Ȳ , Ŷ )− ∑Y ′,Ȳ ′,Ŷ ′ Φ(Y ′, Ȳ ′, Ŷ ′) exp ( ΘTΦ(Y ′, Ȳ ′, Ŷ ′) ) ∑
Y ′,Ȳ ′,Ŷ ′ exp ( ΘTΦ(Y ′, Ȳ ′, Ŷ ′)
) 2 
= EY,Ȳ ,Ŷ∼πΘ
 ∇Θ log (exp(ΘTΦ(Y, Ȳ , Ŷ )))−∇Θ log  ∑ Y ′,Ȳ ′,Ŷ ′ exp ( ΘTΦ(Y ′, Ȳ ′, Ŷ ′) )2 
= E(Y,Ȳ ,Ŷ )∼πΘ
[( ∇Θ log πΘ(Y, Ȳ , Ŷ ) )2] ,
where E(Y,Ȳ ,Ŷ )∼πΘ
[( ∇Θ log πΘ(Y, Ȳ , Ŷ ) )2] is the Fisher Information of Θ. By the Cramér-Rao
bound and the condition (20),
I 2c|D| ⪰ Cov(Θ̂) ⪰ ( DE(Y,Ŷ )∼πΘ [( ∇Θ log πΘ(Y, Ŷ ) )2])−1 ,
which further leads to
B = E(Y,Ȳ ,Ŷ )∼πΘ
[( ∇Θ log πΘ(Y, Ȳ , Ŷ ) )2] ⪰ 2cI.
The proof is completed by putting estimation of terms A and B together.
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 ℓ(W ∗) be the minimum of cross entropy loss function ℓ. Then, we can bound the expected risk with
E [ ℓ(Ŵ )− ℓ(W ∗) ] ≤ χ+ 4cHϵ.
Proof. We begin by rewriting objective of expected loss minimization problem using law of total expectation as follows:
ℓ(W ) =E(X,Y )∼π∗ [ E(X,Y )∼π∗ [H(Y, σ(h(X,W )))|X] ] =E(X′,Y ′)∼π∗ [ E(X,Y )∼π∗ [H(Y, σ(h(X,W )))|X = X ′]
] =E(X′,Y ′)∼π∗ [ E(X,Y )∼π∗ [H(Y, σ(h(X ′,W )))|X = X ′]
] and by our conditional independence assumption (condition (19)), we have
P(Y |X = X ′) = P(Y |Ŷ (X) = Ŷ (X ′)), which further leads to
ℓ(W ) =E(X′,Y ′)∼π∗ [ E(X,Y )∼π∗ [ H(Y, σ(h(X ′,W ))) ∣∣∣Ŷ (X) = Ŷ (X ′)]] =E(X′,Y ′)∼π∗ [ E(Y,Ŷ )∼πΘ∗ [ H(Y, σ(h(X ′,W )))
∣∣∣Ŷ = Ŷ (X ′)]] On the other hand, if we are minimizing the model with learned parameter Θ̂, we will be actually minimizing
ℓΘ̂(W ) = E(X′,Y ′)∼π∗ [ E(Y,Ŷ )∼πΘ̂ [ H(Y, σ(h(X ′,W ))) ∣∣∣Ŷ = Ŷ (X ′)]] , where for any X ′, E(Y,Ŷ )∼πΘ̂ [ H(Y, σ(h(X ′,W )))
∣∣∣Ŷ = Ŷ (X ′)] can be further calculated as E(Y,Ŷ )∼πΘ̂ [ H(Y, σ(h(X ′,W )))
∣∣∣Ŷ = Ŷ (X ′)] =
k∑ l=1 log (σ(h(X ′,W ))l)P(Y,Ŷ )∼πΘ̂(Y = yl|Ŷ = Ŷ (X ′)).
For simplification, we rewrite P(Y,Ŷ )∼πΘ̂(Y = yl|Ŷ = Ŷ (X ′)) as follows with slight abuse of notations:
P(Y,Ŷ )∼πΘ̂(Y = yl|Ŷ = Ŷ (X ′)) = PπΘ̂(yl|Ŷ (X ′)),
and similarly
E(X′,Y ′)∼π∗ = Eπ∗ ,
Let lX′ △ = argminl log (σ(h(X ′,W ))l). The difference between the loss functions will be
|ℓΘ̂(W )− ℓ(W )| = ∣∣∣∣∣Eπ∗ [ k∑ l=1 log ( σ(h(X ′,W ))l ) ( PπΘ∗ (yl|Ŷ (X ′))− Pπ Θ̂ (yl|Ŷ (X ′)) )]∣∣∣∣∣ = ∣∣∣Eπ∗ [log (σ(h(X ′,W ))lX′ ) (PπΘ∗ (ylX′ |Ŷ (X ′))− PπΘ̂(ylX′ |Ŷ (X ′)))]
+ Eπ∗  ∑ l ̸=lX′ log ( σ(h(X ′,W ))l ) ( PπΘ∗ (yl|Ŷ (X ′))− Pπ Θ̂ (yl|Ŷ (X ′)) )∣∣∣∣∣∣ .
Furthermore,∣∣∣Eπ∗ [log (σ(h(X ′,W ))lX′ ) (PπΘ∗ (ylX′ |Ŷ (X ′))− PπΘ̂(ylX′ |Ŷ (X ′)))] + Eπ∗
∑ l ̸=lX′ log (σ(h(X ′,W ))l) ( PπΘ∗ (yl|Ŷ (X ′))− PπΘ̂(yl|Ŷ (X ′)) )∣∣∣∣∣∣
= ∣∣∣∣∣∣Eπ∗ log (σ(h(X ′,W ))lX′ ) − ∑ l ̸=lX′ PπΘ∗ (yl|Ŷ (X ′)) + ∑ j ̸=lX′ PπΘ̂(yl|Ŷ (X ′))  + Eπ∗
∑ l ̸=lX′ log (σ(h(X ′,W ))l) ( PπΘ∗ (yl|Ŷ (X ′)) − PπΘ̂(yl|Ŷ (X ′)) )∣∣∣∣∣∣
= ∣∣∣∣∣∣Eπ∗ ∑ l ̸=lX′ ( log (σ(h(X ′,W ))l)− log ( σ(h(X ′,W ))lX′ )) ( PπΘ∗ (yl|Ŷ (X ′))− PπΘ̂(yl|Ŷ (X ′)) )∣∣∣∣∣∣
= ∣∣∣∣∣∣Eπ∗ ∑ l ̸=lX′ ( h(X ′,W )l − h(X ′,W )lX′ ) ( PπΘ∗ (yl|Ŷ (X ′)).− PπΘ̂(yl|Ŷ (X ′)) )∣∣∣∣∣∣ . (25)
Let h̄(l1, l2) = h(X
′,W )l1 − h(X ′,W )l2 . By Eq. (22), we have for any l ∈ [k],
0 ≤ h̄(l, lX′) ≤ 2H. For any fixed X ′, define gX′(Θ) as follows:
gX′(Θ) = ∑ l ̸=lX′ h̄(l, lX′)PπΘ(yl|Ŷ (X ′)), (26)
based on which we have ∣∣ℓΘ̂(W )− ℓ(W )∣∣ ≤ ∣∣∣Eπ∗ (gX′(Θ̂)− gX′(Θ∗))∣∣∣ By First Mean Value Theorem,
gX′(Θ̂)− gX(Θ∗) = ⟨∇gX′(ξ), Θ̂−Θ∗⟩ ≤ ∥Θ̂−Θ∗∥∥∇gX′(ξ)∥.
We then bound ∇gX(ξ) element-wisely: (1). For any i ∈ [k], j ∈ [n], ŷjl ∈ N (yi,Yj), if i = lX′ , Ŷ j(X ′) = ŷ
j l ,∣∣∣∣∣∣ ∂gX′(ξ)∂θAccyi,ŷjl ,j ∣∣∣∣∣∣ = ∣∣∣∣∣∣ ∑ l ̸=lX′ h̄(l, lX′) ∂Pπξ(yl|Ŷ (X ′)) ∂θAcc yi,ŷ j l ,j ∣∣∣∣∣∣ =
∣∣∣∣∣∣− ∑ l ̸=lX′ h̄(l, lX′)Pπξ(yi|Ŷ (X ′))Pπξ(yl|Ŷ (X ′)) ∣∣∣∣∣∣ = ∑ l ̸=lX′ h̄(l, lX′)Pπξ(yi|Ŷ (X ′))Pπξ(yl|Ŷ (X ′))
≤2HPπξ(yi|Ŷ (X ′))(1− Pπξ(yi|Ŷ (X ′))) =2HVar [ 1Y=yi |Ŷ (X ′) ] .
If i ̸= lX′ , Ŷ j(X ′) = ŷjl ,
∣∣∣∣∣∣ ∂gX′(ξ)∂θAccyi,ŷjl ,j ∣∣∣∣∣∣ = ∣∣∣∣∣∣ ∑ l ̸=lX′ h̄(l, lX′) ∂Pπξ(yl|Ŷ (X ′)) ∂θAcc yi,ŷ j l ,j ∣∣∣∣∣∣ = ∣∣∣∣∣∣− ∑
l/∈{i,lX′}
h̄(l, lX′)Pπξ(yi|Ŷ (X ′))Pπξ(yl|Ŷ (X ′))
+ h̄(i, lX′) ( Pπξ(yi|Ŷ (X ′))− Pπξ(yi|Ŷ (X ′))Pπξ(yi|Ŷ (X ′)) )∣∣∣ ≤max
 ∑ l/∈{i,lX′} h̄(l, lX′)Pπξ(yi|Ŷ (X ′))Pπξ(yl|Ŷ (X ′)),
h̄(i, lX′) ( Pπξ(yi|Ŷ (X ′))− Pπξ(yi|Ŷ (X ′))Pπξ(yi|Ŷ (X ′)) )} ≤2HPπξ(yi|Ŷ (X ′))(1− Pπξ(yi|Ŷ (X ′))) =2HVar [ 1Y=yi |Ŷ (X ′) ] .
If Ŷ j(X ′) ̸= ŷjl ,
∣∣∣∣∣∣ ∂gX′(ξ)∂θAccyi,ŷjl ,j ∣∣∣∣∣∣ = ∣∣∣∣∣∣ ∑ l ̸=lX′ h̄(l, lX′) ∂Pπξ(yl|Ŷ (X ′)) ∂θAcc yi,ŷ j l ,j ∣∣∣∣∣∣ = 0.
(2). For j ∈ [n], ŷr ∈ Yj , if Ŷ j(X ′) = ŷr,
∣∣∣∣∣∂gX′(ξ)∂θAccŷr,j ∣∣∣∣∣ = ∣∣∣∣∣∣ ∑ l ̸=lX′ h̄(l, lX′) ∂Pπξ(yl|Ŷ (X ′)) ∂θAccŷr,j ∣∣∣∣∣∣ =
∣∣∣∣∣∣ ∑ l ̸=lX′ h̄(l, lX′) ( Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′))− Pπξ(Y = yl|Ŷ (X ′))Pπξ(Ȳ r = 1|Ŷ (X ′)) )∣∣∣∣∣∣ . Let
f1(l) = Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′)) f2(l) = Pπξ(Y = yl|Ŷ (X ′))Pπξ(Ȳ r = 1|Ŷ (X ′)),
and
B1 = {l : f1(l) ≥ f2(l), l ̸= lX′}, B2 = {l : f1(l) < f2(l), l ̸= lX′}.
Therefore,∣∣∣∣∣∣ ∑ l ̸=lX′ h̄(l, lX′) ( Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′))− Pπξ(Y = yl|Ŷ (X ′))Pπξ(Ȳ r = 1|Ŷ (X ′)) )∣∣∣∣∣∣ =
∣∣∣∣∣∣ ∑ l ̸=lX′ h̄(l, lX′) (f1(l)− f2(l)) ∣∣∣∣∣∣ =
∣∣∣∣∣∑ l∈B1 h̄(l, lX′) (f1(l)− f2(l)) + ∑ l∈B2 h̄(l, lX′) (f1(l)− f2(l)) ∣∣∣∣∣
≤max t=1,2 ∣∣∣∣∣∣ ∑ l∈BT h̄(l, lX′) (f1(l)− f2(l)) ∣∣∣∣∣∣ =max
{∑ l∈B1 h̄(l, lX′) (f1(l)− f2(l)) , ∑ l∈B2 h̄(l, lX′) (f2(l)− f1(l)) } .
On the other hand,
∑ l∈B1 h̄(l, lX′) (f1(l)− f2(l))
= ∑ l∈B1 h̄(l, lX′) ( Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′)) − Pπξ(Y = yl|Ŷ (X ′))Pπξ(Ȳ r = 1|Ŷ (X ′)) ) ≤2H
∑ l∈B1 ( Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′)) − Pπξ(Y = yl|Ŷ (X ′))Pπξ(Ȳ r = 1|Ŷ (X ′)) ) =2H ( Pπξ(Y = yl,∃l ∈ B1, Ȳ r = 1|Ŷ (X ′)) − Pπξ(Y = yl,∃l ∈ B1|Ŷ (X ′))Pπξ(Ȳ r = 1|Ŷ (X ′))
) =2H ( Pπξ(Y = yl,∃l ∈ B1, Ȳ r = 1|Ŷ (X ′))Pπξ(Ȳ r = 0|Ŷ (X ′))
− Pπξ(Y = yl,∃l ∈ B1, Ȳ r = 0|Ŷ (X ′))Pπξ(Ȳ r = 1|Ŷ (X ′)) )
≤2H ( Pπξ(Ȳ r = 1|Ŷ (X ′))Pπξ(Ȳ r = 0|Ŷ (X ′)) ) =2HVar [ Ȳ r|Ŷ (X ′) ] .
Similarly, we have∑ l∈B1 h̄(l, lX′) (f2(l)− f1(l))− ∑ l∈B2 h̄(l, lX′) ( Pπξ (Y = yl, Ȳ r = 1|Ŷ (X ′)) + Pπξ (Y = yl|Ŷ (X ′))Pπξ (Ȳ r = 1|Ŷ (X ′)) )
≤2HVar [ Ȳ r|Ŷ (X ′) ] .
Conclusively, we have ∣∣∣∣∣∂gX′(ξ)∂θAccŷr,j ∣∣∣∣∣ ≤ 2HVar [Ȳ r|Ŷ (X ′)] .
If Ŷ j = ŷr, similar to (1), we have ∣∣∣∣∣∂gX′(ξ)∂θAccŷr,j ∣∣∣∣∣ = 0.
(3). For any ŷi, ŷj ∈ Ŷ , by the definition of ϕtŷi,ŷj , there exists (a, b) ∈ {0, 1}2, such that ϕtŷi,ŷj (a, b) ̸= 0. Similar to (2), let
f3(l) = Pπξ(Y = yl, Ȳ i = a, Ȳ j = b|Ŷ (X ′)) f4(l) = Pπξ(Y = yl|Ŷ (X ′))Pπξ(Ȳ i = a, Ȳ j = b|Ŷ (X ′))
and
B3 = {l : f3(l) ≥ f4(l), l ̸= lX′}, B4 = {l : f3(l) < f4(l), l ̸= lX′}
we have ∣∣∣∣∣∂gX′(ξ)∂θtŷi,ŷj ∣∣∣∣∣ =max {∑ l∈B3 h̄(l, lX′) (f3(l)− f4(l)) , ∑ l∈B4 h̄(l, lX′) (f4(l)− f3(l)) }
≤2HVar [ ϕtŷi,ŷj (Ȳ i, Ȳ j)|Ŷ (X ′) ]
(∗) ≤2H ( Var [ Ȳ i|Ŷ (X ′) ] +Var [ Ȳ j |Ŷ (X ′) ]) ,
where inequality (∗) comes from Lemma D.1. (4). For any yi ∈ Y, ŷr ∈ Ŷ , by the definition of ϕtyi,ŷr , there exists a ∈ {0, 1}, yj ∈ Y , s.t., ϕtyi,ŷr (yj , a) ̸= 0. We further divide the proof into two cases: ϕtyi,ŷr (yi, a) = 0, and ϕtyi,ŷr (yi, a) ̸= 0.
(4a). If ϕtyi,ŷr (yi, a) = 0, we have tyiŷr = t sg and consequently a = 1. Similar to (1-3)., we have
∣∣∣∣∣∂gX′(ξ)∂θtyi,ŷr ∣∣∣∣∣ = ∣∣∣∣∣∣ ∑ l ̸=lX′ h̄(l, lX′) ∂Pπξ(yl|Ŷ (X ′)) ∂θtyi,ŷr ∣∣∣∣∣∣ (•)= ∣∣∣∣∣ k∑ l=1 h̄(l, lX′) ∂Pπξ(yl|Ŷ (X ′)) ∂θtyi,ŷr ∣∣∣∣∣ =
∣∣∣∣∣∣ ∑ l ̸=i h̄(l, lX′) ( Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′))− Pπξ(Y = yl|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)) ) − h̄(i, lX′)Pπξ(Y = yi|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′))
∣∣∣ , where Eq. (•) is due to Let
f5(l) = Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′)) f6(l) = Pπξ(Y = yl|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′))
and
B5 = {l : f5(l) ≥ f6(l), l ̸= i}, B6 = {l : f5(l) < f6(l), l ̸= i}
Then we have∣∣∣∣∣∂gX′(ξ)∂θtyi,ŷr ∣∣∣∣∣ ≤ max {∑ l∈B5 h̄(l, lX′) (f5(l)− f6(l)) , ∑ l∈B6 h̄(l, lX′) (f6(l)− f5(l)) + h̄(i, lX′)f6(i) } .
On one hand,∑ l∈B5 h̄(l, lX′) (f5(l)− f6(l))
= ∑ l∈B5 h̄(l, lX′) ( Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′)) − Pπξ(Y = yl|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)) ) ≤ ∑ l∈B5 2H ( Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′)) − Pπξ(Y = yl|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′))
) =2H ( Pπξ(Y = yl,∃l ∈ B5, Ȳ r = 1|Ŷ (X ′)) − Pπξ(Y = yl,∃l ∈ B5|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′))
) =2H ( Pπξ(Y = yl,∃l ∈ B5, Ȳ r = 1|Ŷ (X ′))(1− Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)))
− Pπξ(Y = yl,∃l ∈ B5, Ȳ r = 0|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)) )
≤2HPπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′))(1− Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′))) =2HVarπξ [ ϕtyi,ŷl(Y, Ȳ r)|Ŷ (X ′) ]
≤2HVarπξ [ 1Y=yi |Ŷ (X ′) ] + 2HVarπξ [ Ȳ r|Ŷ (X ′) ] .
On the other hand,∑ l∈B6 h̄(l, lX′) (f6(l)− f5(l)) + h̄(i, lX′)f6(i)
=− ∑ l∈B6 h̄(l, lX′) ( Pπξ(Y = yl, Ȳ r = 1|Ŷ (X ′)) + Pπξ(Y = yl|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)) ) + h̄(i, lX′)Pπξ(Y = yi|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′))
≤2H ( −Pπξ(Y = yl,∃l ∈ B6, Ȳ r = 1|Ŷ (X ′))(1− Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)))
− Pπξ(Y = yl,∃l ∈ B6, Ȳ r = 0|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)) + Pπξ(Y = yi|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)) ) ≤2H ( Pπξ(Y = yl,∃l ∈ B6, Ȳ r = 0|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′))
+ Pπξ(Y = yi|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)) )
≤2H ( Pπξ(Ȳ r = 0|Ŷ (X ′))Pπξ(Ȳ r = 1|Ŷ (X ′)) + Pπξ(Y = yi|Ŷ (X ′))Pπξ(Y ̸= yi, Ȳ r = 1|Ŷ (X ′)) ) ≤2HVarπξ [ 1Y=yi |Ŷ (X ′) ] + 2HVarπξ [ Ȳ r|Ŷ (X ′) ] .
Therefore, in this case, we have∣∣∣∣∣∂gX′(ξ)∂θtyi,ŷr ∣∣∣∣∣ ≤ 2HVarπξ [1Y=yi |Ŷ (X ′)]+ 2HVarπξ [Ȳ r|Ŷ (X ′)] .
(4b). If ϕtyi,ŷr (yi, a) ̸= 0, similar to (4a)., we have∣∣∣∣∣∂gX′(ξ)∂θtyi,ŷr ∣∣∣∣∣ = ∣∣∣∣∣∣− ∑ l ̸=i h̄(l, lX′)Pπξ(Y = yl|Ŷ (X ′))Pπξ(Y = yi, Ȳ r = 1|Ŷ (X ′))
+ h̄(i, lX′) ( Pπξ(Y = yi, Ȳ l = 1|Ŷ (X ′))− Pπξ(Y = yi|Ŷ (X ′))Pπξ(Y = yi, Ȳ r = 1|Ŷ (X ′)) )∣∣∣ .
Since h̄(i, lX′) ( Pπξ(Y = yi, Ȳ r = 1|Ŷ (X ′))− Pπξ(Y = yi|Ŷ (X ′))Pπξ(Y = yi, Ȳ r = 1|Ŷ (X ′)) ) =h̄(i, lX′)Pπξ(Y = yi, Ȳ r = 1|Ŷ (X ′))Pπξ(Y ̸= yi|Ŷ (X ′)) ≥0,
we have ∣∣∣∣∣∂gX′(ξ)∂θtyi,ŷl ∣∣∣∣∣ ≤max{h̄(i, lX′)Pπξ(Y = yi, Ȳ r = 1|Ŷ (X ′))Pπξ(Y ̸= yi|Ŷ (X ′)) ,
∑ l ̸=i h̄(l, lX′)Pπξ(Y = yl|Ŷ (X ′))Pπξ(Y = yi, Ȳ r = 1|Ŷ (X ′))  ≤2HVar [ 1Y=yi |Ŷ (X ′) ] .
Combining (4a). and (4b)., we have that∣∣∣∣∣∂gX′(ξ)∂θtyi,ŷl ∣∣∣∣∣ ≤ 2H (Varπξ [1Y=yi |Ŷ (X ′)]+Varπξ [Ȳ l|Ŷ (X ′)]) .
Combining (1-4)., we then have
∥∇gX′(ξ)∥2
≤4H2 k∑
i=1 n∑ j=1 (|N (yi,Yj)| − 1)Varπξ [ 1Y=yi |Ŷ (X ′) ]2 (27)
+ 4H2 ∑
j∈[n],ŷr∈Yj
Varπξ
[ Ȳ r|Ŷ (X ′) ]2 + 4H2
∑ i,j∈[k̂] ( Varπξ [ Ȳ i|Ŷ (X ′) ] +Varπξ [ Ȳ j |Ŷ (X ′) ])2 + 4H2
∑ i∈[k],j∈[k̂] ( Varπξ [ 1Y=yi |Ŷ (X ′) ] +Varπξ [ Ȳ l|Ŷ (X ′) ])2
≤8H2  k∑
i=1
(ni + k̂)Varπξ(1Y=yi |Ŷ = Ŷ ∗)2 + k̂∑
i=1
(mi +K − 1)Varπξ(Ȳ i|Ŷ = Ŷ ∗)2  .
(28)
Therefore, by Eqs. (25), (26), and (28), and Assumption Eq. (21), we have
|ℓ(W )− ℓΘ̂(W )| = ∣∣∣∣∣∣Eπ∗ ∑ l ̸=lX′ h̄(l, lX′) ( PπΘ∗ (Y = yl|Ŷ (X ′))− PπΘ̂(Y = yl|Ŷ (X ′)) )∣∣∣∣∣∣
= ∣∣∣Eπ∗ [gX′(Θ∗)− gX′(Θ̂)]∣∣∣ ≤ ∣∣∣Eπ∗∥∇gX′(ξ)∥∥Θ∗ − Θ̂∥∣∣∣ ≤ 2cH√
M ∥Θ∗ − Θ̂∥.
Now, we apply the assumption that we are able to solve the empirical problem, producing an estimate Ŵ that satisfies E [ ℓΘ̂(Ŵ )− ℓΘ̂(W ∗Θ) ] ≤ χ,
where W ∗ Θ̂ is the true solution to
W ∗ Θ̂ = argmin
W ℓΘ(W ).
Therefore, E [ ℓ(Ŵ )− ℓ(W ∗) ] = E [ ℓΘ̂(Ŵ )− ℓΘ̂(W ∗Θ̂) + ℓΘ̂(W ∗ Θ̂ )− ℓΘ̂(Ŵ ) + ℓ(Ŵ )− ℓ(W ∗) ] (∗) ≤ χ+ E [ ℓΘ̂(W ∗ Θ̂ )− ℓΘ̂(Ŵ ) + ℓ(Ŵ )− ℓ(W ∗)
] ≤ χ+ 4cH 1√
M E∥Θ̂−Θ∗∥+ E
[ ℓΘ̂(W ∗ Θ̂ )− ℓΘ̂(Ŵ ) + ℓΘ̂(Ŵ )− ℓΘ̂(W ∗) ] ≤ χ+ 4cH 1√
M E∥Θ̂−Θ∗∥,
where Eq. (∗) comes from condition (23). With Eqs. (20) and (21), we have Eq. (24) by Lemma D.5, i.e.,(
E∥Θ̂−Θ∗∥ )2 ≤ E∥Θ̂−Θ∗∥2 ≤ ε2M.
We can now bound this using the result of Lemma D.6, which results in E [ ℓ(Ŵ )− ℓ(W ∗) ] ≤ χ+ 4cHϵ.
The proof is completed.

heading: E EXAMPLES AND ILLUSTRATIONS

heading: E.1 LABEL GRAPH AND LABEL HIERARCHY
text: 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 on the four types of label relations.

heading: E.2 AN EXAMPLE OF INCONSISTENT LABEL GRAPH
text: Fig. 6 shows an example of an 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.

heading: E.3 ENUMERATION OF INCONSISTENT TRIANGLE LABEL GRAPH
text: For a 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.

heading: E.4 AN EXAMPLE OF INDISTINGUISHABLE LABEL GRAPH
text: Fig. 7 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 Cat”, 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 is seen and can be predicted by some ILF(s). We are only interested in the distinguishablity of a pair of unseen labels.
In practice, users could "break the symmetry" by adding new 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.

heading: F EXPERIMENTAL DETAILS

heading: F.1 DATASET
text: Large scale Text Classification Dataset3: 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 a label hierarchy. We filter out the documents with multiple labels, and preserve categories with more than 500 documents. We use a pre-trained sentence transformer (Reimers & Gurevych, 2019) to obtain document embeddings for classification. We follow Zhang et al. (2021) to generate 5 keyword-based labeling functions for each seen label as ILFs.
Large scale Image Classification Dataset4: ILSVRC2012 (Russakovsky et al., 2015), a large scale image classification dataset, which consists of 1.2M training images from 1000 object classes based
3http://lshtc.iit.demokritos.gr/ 4http://image-net.org/challenges/LSVRC/2012/index#data
on ImageNet. Following Deng et al. (2014) we use WordNet as the label hierarchy, and because all the images are assigned to leave labels in WordNet, for each non-leave label, we aggregate images belonging to its descendants as 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 or 3 exclusive seen labels from the label graph as well as 500 images for each label to train a ResNet-32 classifier.

heading: F.2 DESCRIPTION OF APPLYING DAP
text: To apply DAP, we 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 on the label relations and basic logistic rules, we enumerate all the possible assignments of seen labels given a data point. For example, if label A is subsumed by label B, then for a data point, when it belongs to label A, it must also belong to B; And if label A and B are exclusive, then one data cannot belong to both at the same time. Let s ∈ S denote one possible label assignment and S is the set of all possible s. Then we define the attribute as a vector of |S| dimension where each dimension corresponds to one s.
Second, we define the attribute of unseen labels. For an unseen label A and a label assignment s, if A is not exclusive to any label in s then we set the corresponding attribute as = 1 for label A, other wise 0. The intuition is that, if A is not exclusive to labels in s, it’s likely that when a data belongs to assignment s, it also belongs to label A. For each data point, we use the labels assigned by ILFs to build their attributes. If a data belongs to assignment s then its corresponding attribute as = 1, otherwise 0.
Then, we can train attribute classifier p(a|x) 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):
f(x) = argmax c |S|∏ m=1 p(acm|x) p(acm|x)
(29)

heading: F.3 HYPER-PARAMETERS
text: For the training of PGMs, we set the learning rate to be 1n where n is the number of training data. For training logistic regression model, we use the default parameters in scikit-learn library. For training ResNet model, we set batch size as 256 and use Adam optimizer with learning rate being 1e-3 and weight decay being 5e-5.

heading: F.4 HARDWARE AND IMPLEMENTATION DETAILS
text: All experiments ran on a machine with an Intel(R) Xeon(R) CPU E5-2678 v3 with a 512G memory and a GeForce GTX 1080Ti-11GB GPU.
All the code was implemented in Python. We use the standard implementation of the logistic regression model from Python scikit-learn library5 and the ResNet model from torchvision library6.
Our code will be released upon the acceptance.

heading: F.5 DATASET DETAILS OF REAL-WORLD APPLICATIONS
text: We list the tags we used in the real-world application (Sec. 7.3) and examples of label relations we query from the existing product category taxonomy.
5https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.

heading: LogisticRegression.html
text: 6https://pytorch.org/docs/stable/torchvision/models.html

heading: G ADDITIONAL EXPERIMENTS

heading: G.1 PERFORMANCE DROP WHEN THE DISTINGUISHABLE CONDITION IS VIOLATED
text: 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.

Review summaries:
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. The 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. The author provided a theoretical analysis on the requirements of the labeling functions and derived a generalization error bound. The proposed method was evaluated on semi-synthetic datasets based on the ImageNet dataset for image classification and the LSHTC dataset for text classification.

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.