On Learning Latent Models with Multi-Instance Weak Supervision
Authors: Kaifu Wang
Efthymia Tsamoura
Dan Roth
Venue: NeurIPS 2023 poster (2023)
Keywords: weak supervision
partial label learning
neuro-symbolic learning
latent structural learning

Abstract: We consider a weakly supervised learning scenario where the supervision signal is generated by a transition function $\sigma$ of labels associated with multiple input instances. We formulate this problem as *multi-instance Partial Label Learning (multi-instance PLL)*, which is an extension to the standard PLL problem. Our problem is met in different fields, including latent structural learning and neuro-symbolic integration. Despite the existence of many learning techniques, limited theoretical analysis has been dedicated to this problem. In this paper, we provide the first theoretical study of multi-instance PLL with possibly an unknown transition $\sigma$. Our main contributions are as follows: First, we proposed a necessary and sufficient condition for the learnability of the problem. This condition nontrivially generalizes and relaxes the existing *small ambiguity degree* in PLL literature since we allow the transition to be deterministic. Second, we derived Rademacher-style error bounds based on the top-$k$ surrogate loss that is widely used in the neuro-symbolic literature. Furthermore, we conclude with empirical experiments for learning with an unknown transition. The empirical results align with our theoretical findings; however, they also expose the issue of scalability in the weak supervision literature.

On Learning Latent Models with Multi-Instance Weak Supervision
Kaifu Wang University of Pennsylvania kaifuOsas. upenn. edu
Efthymia Tsamoura Samsung AI efi tsaaooura@samsung com
Dan Roth
University of Pennsylvania danrothōseas upenn.eeee edu
Abstract
We consider a weakly supervised learning scenario where the supervision signal is generated by a transition function a of labels associated with multiple input instances. We formulate this problem as multi-instance Purtial Label Learning (multi-instance PLL). Our problem is extension to the standard PLL problem and is met in different fields, including latent structural learning and neuro-symbolic integration. Despite the existence of many learning techniques, limited theoretical analysis has been dedicated to this problem. In this paper, we provide the first theoretical study of iullii-instance PLL with possibly unknown transition Our main contributions are as follows. First, we propose a necessary and sufficient condition for the learabilityy of the problem. This condition nontrivially generalizes and relaxes the existing small ambiguity degree in PI.L literature since we allow the transition be deterministie. Second, derive Rademacher-style error bounds based on a top-k surrogate loss that is widely used in the neuro-symbolic literature. Furthermore, we conclude with empirical experiments for learning under unknown transitions. The empirical results align with our theoretical findings, exposing also the issue of scalability in the weak supervision literature.
1 Introduction
Consider the scenario in Figure 1. where a learner aims to learn one or more classifiers fi...., , fn-
each of which maps an instance æ to its corresponding label y. The learner is given training examples. each of which consists of vector of M > 1 instances æ (æ1...., MM) and each v, is processed by one of the fj's, Differently from supervised learning, the gold labels y = (.1...., yM) of are hidden; instead, the learner is provided with weak label which is produced by applying transition function'
the gold labels y. The transition itself may unknown to the learner.
The above weak supervision setting has been topic of active research in NLP [42, 35, 34, 32, 45, 52, 22]. Recently, it has received renewed attention it met in neuro-symbolic frameworks [14], i.e., frameworks that integrate inference and learning over neural models with inference and learning over symbolic models, such logical theories [30, 53, 13, 59, 43. 31, 24, 27]. The benefits of this setting over architectures that approximate the fi's and a via an end-to-end neural model [48] are (i) the ability reuse the latent models, something particularly useful in NLP [34, 32]. (ii) higher accuracy in multiple tasks, e.g., NLP [55] and visual question answering [24], (iii) greater interpretability and
(iv) the ability to encode prior knowledge via σ. Below, we present an example of our learning setting in neuro-symbolic learning.
Example 1 (SUM2). We aim to learn an MNIST classifzer f. Differently from supervised learning, we use training examples of the form (x) 32, s), where I and x2 are MNIST digits and
We use the term transition function (or transition in short) instead of simply function, due to the relationship between our setting and learning with partial labels literature [8, 9].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

their sum. The above implies transition function a: (0.....))x(0........... () {0.... 18), s.s. (y.yy) = y + yf. The target sum restricts the space of labels that can be assigned the inpur pair of digits (.,,32 v2), e.g,, if 8 2, then the only combinations of labels that abide by the constraint that the sum are (2,0), (1,1) 1) and (0,2). This problem is referred to as SUM2 in literature 124, 301.
The transition function a is not necessarily one-to- one. For instance, multiple combinations of digits can lead to the same target sum. The above leaves us with two questions to answer: can we provide anyy learning guarantees for the classifiers fI...., fn. and what if a is unknown? Despite that multiple techniques for neuro-symbolic and latent structural learning have been recently proposed, those theoretical questions remain open. Practically, for the single input case (M =1 1), our setting can reduce to that of partial label learning (PI..), where each input instance is accompanied by a set of labels, including the gold one [25, 11, 5, 29, 39, 54, 57, 60]. However, key PLL learnability assumption - that the probability a wrong label co-occurs with the gold one is always less than one [28]- violated in our setting, rendering existing learnability results inapplicable. This is because a is a deterministic but not necessarily bijective function, as opposed to a in PLL which is randomized.
f1
91
22
fz
U2
ZM
fn
yM
Figure 1:
Multi--nstance PLL. We aim to learn the fi's given the a and 8. M may be different from n and a may unknown.
Due to its relevance to PLL., we refer to our learning setting as multi-instance PI... Differently from prior art, e-g.: [42, 35], we do not restrict to specific types of functions, e-g., linear functions. Hence, we can express constraints in several formal languages, including systems of Boolean equations and Datalog [1], language widely used in neuro-symbolic techniques [24]. Notice that many neuro-symbolic learning techniques are oblivious to the implementation of the symbolic component: abstracting the symbolic component
transition has been actually proposed as the means to compositionally integrate neural with symbolic models [43]. Furthermore, although we primarily consider deterministic transitions motivated by the seuro-symbolic and NLP literature, our results can be extended to support randomized transitions when a is known.
We aim to make minimal assumptions the data distributions by showing learnaillity even under the "toughest" distributions. In addition, we provide learning guarantees under the semantic loss [56], widely-used surrogate loss for training classifiers subject to logical theories [30, 43, 24). To knowledge, we are the first to provide this theoretical analysis, closing a gap in the neuro-symbolic and latent structural learning literature.
Contributions. Our contributions can be summarized into the following:
We propose necessary and sufficient learnability conditions of the multi-instance PLL problem assuming all the instances are classified by a single classifier f and the transition is known. We further provide a Rademacher-styLe error bound using top-k approximation to the semantic loss [56], see Section 3. Our analysis confirms the intuition that a larger & decreases the empirical risk, but increases the number of samples required for learning.
We extend the above results for the more general case where one learns multiple classifiers J/, that classify instances from different domains, see Section 4.
We prove learnability with a single classifier and an unknown transition function, see Section 5, and assess the validity of our theoretical results using SOTA neuro-symbolic frameworks, see Section 6.
Proofs, additional backgrounds and details on our empirical analysis are in the appendix.
2 Preliminaries
We use P(-) to denote probability mass, E[.) to denote expectation and 1 1f-} to denote an indicator function. For positive integer M, we use [M] as a short for 14...,,y For a vector of M elements (xI,..., ,TM), a position j is number in [M] used to identify the element zy. A vector is said to be diagonal its elements in all positions are equal. Suppose f is function on a domain and in is a vector of M elements in X. we use the symbol f(x) to denote the vector (f(x))...., (*

---

Classifiers. Let X' denote an instance space and Y denote an output space with |>|| Let also D be the joint distribution of two random variables (X, Y) E X y and Dx be the marginal of X. Throughout the text, we use a: for (f1,..., ..M) and y for the corresponding vector of gold labels. We consider scoring functions of the form f: + Ac, where 4e the space of probability distributions on Y' (e-g., f outputs the softmax probabilities of a neural network). We use f (xx) to denote the j-th output of f(x). A scoring function f induces a classifier whose prediction on a (f) is defined by [f]())= == argmaaxEjec) (()). We use F and [F] to denote the space of scoring functions and the space of classifiers induced by F, respectively. We use the VC-dimension, the Natarajan dimension and Rademacher complexities to characterize the complexity of F [40].
Loss functions. We define the problem of learning a scoring function using a fixed set of training samples as the one of choosing the scoring function from F that better fits the training samples. We give semantics to the term fits by using the risk R(f; E) of f subject to sampling distribution and given loss function E: the lower R(f: E) becomes, the better f fits the data. When there exists an f E F, such that () = O, we say that the space F is realizable under f. In supervised learning, we are provided with samples of the form (æ, y) drawn from D. We use R to denote the empirical risk, i.e., the average risk computed over the training samples only. The risk? of subject to loss function f y x y + F+ is given by R(f:E) == (xxD [ (()))(
A commonly used loss function is the zero-one loss defined by 1 (y. v/ := 1/ + y) for any pair y.y' E V We use R (ff as short for Rff ( and refer to it as the zero-one risk of f. We will also consider Semantic Loss (SL) [56], which has been adopted to train classifiers subject to Boolean formulas [30, 43. 24]. Let yp be a Boolean formula where each variable in yp is associated with a class from V Then, the SI. of yo subject to f(r) is the negative logarithm of the weighted model counting (WMC) [7] of op under f(x) namely (T, f()) == log( (oM((e (())), where WMC(p, (z)) takes values in (0, 1) and denotes the probability that vp is logically satisfied when its variables become true with probabilities specified by f(x).
3 Learning a Single Classifier Under a Known Transition
We begin with the setting where the goal is to learn a single classifier f E F under a known transition a. Firstly, we show FRM-learnability (Theorem 1). Then, inspired by neuro-symbolic learning, we provide a Rademacher-styy Below, we formally introduce the learning setting.
error bound with top-k surrogate loss based on WMC (Theorem 2).
Problem setting. Let a y + S be transition function, where S = [l,.... d} with S = d 2 1. Let also Tp be a set of mp partially labeled samples of the form (ar, = (I1,.... , M. 8). Each training sample is formed by. firstly drawing M i.i.d. samples (z,, y1) from D and then setting s a (y1. YMM) We use Dp to denote the distribution followed by the training samples (x. s). In analogy to the zero-one classification loss god we define the zero-one partial loss subject to a as e (y, := 1 (z) * $). for any y E yM and s E S. The learner aims to find the classifier f with the minimal zero-one risk Ro (f).. As the gold labels are hidden, the learner uses the dataset Tp to estimate and minimize the zero-one partial risk of f subject to a defined as R2! (f:a) ==
Exx,....X. (M) [ (()](X)).......... ((((X))))...,(()))))))) (f)(
We demonstrate these notions via Example 1. There, f is an MNIST classifier, X is the space ........7
of MNIST images and Y' {O..... 9}. The training samples are of the form (Z1, 22, s) where s = 0 8/2) = y1 + y2. The partial risk of ff is then the probability of predicting the wrong sum.
I Learnability. A partial learning algorithm A takes a partially labeled dataset Tp with |Tpl mp as input and outputs a function A(Tp) E F. Similar to standard PAC learning (see, for example, [40]), we say multi-instance problem is learnable, if there exists partial learning algorithm A. such that for any data distribution D over X ) and any ó, e E (0, 1). there is an integer Me.5. such that mp? 2 m..5 implies Ra (A(Tp)) S with probability least 1-5 with respect to Dp. We consider A to be an Empirical Risk Minimizer (ERM) algorithm that finds the classifier f E F which minimizes the empirical zero-one partial risk Rpl (f:a; Tp) := L(z,,)ET,
s)) m)/mp.
As stated above, the risk is defined subject to a sampling distribution. For brevity. we will omit that distribution when defining the risk and fix the sampling distribution in each case.
3

---

3.1 ERM Learnability
To prove learnability under the partial zero-one loss, we aim to bound Ro (f) with the partial risk Rp (f:a). Firstly, we propose sufficient and necessary condition called M M--mambiguity.
Recall that learnability requires handling all possible distributions of (æ, y). Therefore, to propose a necessary condition to guarantee learnability, we consider a special case: the one in which 'D concentrates its mass a single item Ip, i.e., DD (2r) 1. In that case, the only sample observed during learning includes only the instance To- Now, let lo E ) be the gold label of xo- If mispredicts the class of zo. i.e., f (20) o lo. and this misprediction leads the same observed partial label, i.e. a (zo)....... ((o)) = a (l)...,,))) then the problem will be not learnable, as we will never be able to correct this error. Motivated by this special case, we propose the following condition:
Definition 1 (M -unambiguity). Transition a is M- M-unambiguous for any two diagonal label vectors y and y' E yM such that y + y', we have that o (yy) + (y).
Recall that vector is diagonal if all its elements are equal. Below, we provide examples of transitions that satisfy (or not) the M -unambiiuuyty condition.
Example 2. Consider the following learning problems.
(SUM-M): Consider a variant of Example I where s is the sum of M digits, i.e., a (Vi. yMr) = M
Li=1 V4- The transition is M -l-unambigous, since oyy.... + ayy'.... holds for any # y/-
(PRODUCT-M): Consider a variant of Example where s is given by o² (y)..... .yM))))))))))))) = IT yo- Then, o* is M -unnmmigguuus, since o (y.....,) 3) yM + ( holds for any y F y/.
(XOR): Consider Boolean labels. We take the XOR of the two digits as the partial label, i.e., σ xxOR (x0K(y1.32) = 1(y1 # y2 Then XOO is not M -unambiguous,, since ooOR (1, = = (0, 0).
Although M- M-unambiguity is proposed as a necessary condition under special types of data distribu- tions, we now show that it is also sufficient for proving ERM-learnability. Firstly, we prove that the classification risk can be bounded by the partial risk.
Lemma 1. If is M M-unambigous, then we have:
RD (f) S ORR' (f: (f: as R2 (f:o) +00
(1)
Moreover, a is not M M-unambiguous, then learning from partial labels is arbitrarily difficult, in the sense that a classifier f with partial risk RDI (f:a)= can have a risk of R1
(f) =1)=1.
To show learnability, we bound the partial risk with its empirical counterpart in the realizable case. Theorem 1 (ERM learnability under M -umambiguitt). Suppose F is realizable under ep and [F] has a finite Natarajan dimension dry, Then for any e, E (0, 1), there exists a universal constant Co > 0, such that with probability least 1 - 8, the empirical partial risk minimizer with Ruy (f:a; Tp) 0 has classification risk Ru
(f) < c, if
2MM2
(2M--2 MM
+ +log log (o))
(d17)og(6cMMdzz)
mp 2 Co
eM
Beyond Lemma 1, Theorem builds upon several non-trivial intermediate results: (i) bound of the VC dimension for the partial label predictor (Lemma 3 in the Appendix) and (ii) Construction of counter-examples for arguing the necessity of M -uunamiiguity (see the proof of Theorem 1).
Toward faster convergence rate. Theorem I presents a rather slow convergence rate of (c² (e) In the following, we show that better convergence rate is achievable by forcing stricter ambiguity conditions. In the following, we introduce the concept of 1-umambiguity, which requires the transition to be sensitive to 1-position perturbations:
Definition 2 (l-unambiguity). Transition is l-unambiguous, if there exists an index 1 5 S M, such that flipping the i-th label of any label vector y E y results in a vector y with o + (y))
In the following, we provide examples of transitions that satisfy (or not) the l-unambiguity condition.
A constant is universal if it that does depend the parameters of the learning problem (e.g.. M or c).

---

Example 3. Let us continue with Example 2. The transition a from SUM-M is I I-umambiguous since aly) = Ei=1 Yi always change when replacing any of the labels y/- However, the transition o² from PRODUCT-M is not I lunambiguuus, since for the label vector y = (0, 1,11 1) (with product zero), the flipped vector y = 1, also leads to product zero.
We show that better convergence rate be achieved if a is both 1- and M-unambigous. Proposition (ERM learnability under 1- and M-unambiguity). Ifa is both I- and M- M-unambigous, then we have:
R (f) S O (f:o)) as R2 (f:o) +
(3)
Furthermore, F is realizable under ep and [F] has a finite Natarajan dimension diz,, then for any 8 (0, 1) and e E (0, 10 that is sufficiently close to O, there exists a universal constant C₁, such
that with probability at least 1- -6, 6, the empirical partial risk minimizer with Rpp (f;o) = 0 has
classification risk T (f) < e, if
mp 2 Ci ( (d37 (117 log (2)
+ log (0))
(4)
Remark 1. The supervision power of a partial label depends on the "instability" of a: if returns different results under certain perturbations in I positions for an I [M then the classification risk is bounded by R s O(R3' o To formalize this intuition, in the appendix, we provide a generalized definition of both 1- and MM-unambiguity, called I-unambiguity, and show learnability with intermediate convergence rates. Notice that M-unambiguity is closely related to the small ambiguity degree condition in the PLL literature [28]. Appendix E.3 provides relevant discussion and an extension of our results for randomized transitions.
Remark 2. We use the concentrated distribution described at the beginning of Section 3.1 as a pivot to design necessary and sufficient learnability condition. However, the results in Lemma 1, Theorem 1 and Proposition do not apply only to this distribution, but to any distribution Dp of partial data. The same applies to all learnability results that follow.
3.2 Error Bounds with the Top-k Semantic Loss
We now study the error bounds with the semantic loss (see Section and Appendix A) under top-k approximations (Theorem 2). We are interested in this loss for two reasons. Firstly, risk minimization under the zero-one loss is intractable even for linear classifiers [17] and hence in practice, learning is performed by minimizing differentiable surrogate losses such as the semantic loss. Secondly, computing a surrogate loss typically introduces another source of intractability: that of enumerating the entries of [24, 43, 31]. For example, in SUM-M, we have enumerate 10aM digit combinations to populate a, which is not scalable.
A popular way to reduce the second source of inefficiency is to consider only the k most probable label combinations during training, where the probability of a label vector y given æ and classifier f is defined by (y(e) == I f f (x:).. Then, training can proceed by taking the semantic loss over the top-k label vectors [24]. The above is possible, as the top-k label vectors can be equivalently viewed as a formula that is true iff one or more of the top-k label vectors is the gold one.
Example 4. Let us return back Example 1. Instead of considering all three combinations (2, 0). (1, and (0, 2) assuming a target s = 2, we can consider only the first and the last combination, if the probabilities (predicted by f) of the two images being I are way lower than those of being 0 or 2. Then, the top-2 label vectors (2. 0), (0,2) can be seen as the formula (A1,2 A A2,0) V (A1,0 A A2,2), where Ai, is a Boolean variable that is true iff the i-th input digit is assigned label j.
We use Vin, V; denote the Boolean formula computed out of the k label vectors yI....: vR where each y, is the conjunction of Boolean variables of the form Aig, as in Example 4. Given a softmax score / (az), variable At,y, is assigned probability (*;)). We now define the lop-k partial loss: Definition 3 (Top-k partial loss). The top-k partial loss for an integer k 2 1 subject to a classifier f. transition and sample (xr, 8) defined as
k V
(1(())) s) = SL
f(x))
(5)
5

---

(...... (b)) E ynM are the top-k maximizers of Pf(m) in the preimage of s, i.e, fy E yM; where y()) .....
ayy) = s}. The top-k partial classification risk of f subject to a is then given by
Rf: [x. Do 1
XM),
(6)
Remark. The WMC is upper bounded by the sum of probabilities, so we can approximate the SL as (f))))) s) 2 log(E" )). Furthermore, the special case where k 1 reduces to the infinum loss [5] and minimal loss [29] in the PIL literature as we show in Appendix B.2.
Let Rm (F) denote the Rademacher complexity [4, 10] of F with m samples defined in Appendix A. We are now ready to bound the zero-one classification risk with the empirical top-k partial risk.
Theorem 2 (Error bound under unambiguity). Let an integer k 2 1 and ō E (0, If is both 1- and M -unambiguous, then with prohability least 6, we have:
R + 2V/M33222 Ma (F) 1og(1/6)
(T) 1 (k (1+
(7)
2mp
where o; -on ex (f)), the empirical counterpart of (6) and t is an increasing function that satisfies lim (1) =
Proof sketch. Theorem 2 builds upon several results. Firstly, we derived an inequality that bounds the top-k loss with the zero-one loss (Lemma 5), which requires the construction of an intermediate e loss (Definition 11). Secondly, we show the Lipschtness of the semantic loss (Lemma 7). This result is further combined with a contraction lemma that is proposed in [10] (Lemma 6) to bound the Rademacher complexity of the model.
Remark. Similarly to Theorem and Proposition 1. Theorem 2 suggests that the learning difficulty increases M increases. This is intuitive, since it gets harder to disambiguate the gold labels when M increases, e.g., for 2-SUM, there are 102 possible label vectors need to be considered, while for 4-SUM, there are 10 ones. Our bound also suggests tradeoff with the choice of k: larger k decreases the risk, but tends to increase the complexity term.
Learning Multiple Classifiers Under a Known Transition
In this section, we extend the learning problem from Section 3 to jointly learn n > 1 different classifiers. Similarly to Section 3, we aim to propose minimal assumptions for the data distribution to show both results on ERM-llarrability (Theorem 3) and Rademacher-sty/ error bound with the top-k loss (Theorem 4). We formally define the learning setting below.
Problem setting. We aim to learn n 2 1 classifiers, each of which maps instances from space X; to the corresponding label space )42 with [ = G,. For each E [n]], we define scoring space F, which contains mappings of the form fa Xr -> Ac,. Each fa is used to classify M; 2 instances (za...... (iMM; æ; E ..M. with (hidden) gold labels y, (Mii..... ViM;) ). We denote the vector of scoring functions as f (n)....,fn). Let D; be the joint distribution over elements from X, x D,- Each training sample given to the learner (x1,- ........ Zn. s) is formed by (i) drawing M, i.i.d. samples (x 3/) from D., for each E [n] and then (ii) obtaining its partial label as = (B)1..... yn). We override the notation Dp to denote the distribution of the training samples in this learning setting. The partially labeled dataset TTp then contains mp i.idd samples drawn from Dp.
Similarly to Section 3, the learner aims to find the classifiers f1....: fn with the minimal zero- one risk defined as R := Er_ RR1 (f.( As the gold labels are hidden, the learner uses the dataset Tp to estimate and minimize the zero-one partial risk of fi...., Sn. which is defined as R2J (Ji...., fujo) == IE(x,....,,.. S..S.,,,, 1 ((Ifi(XX),,... [f]] (X.)), where [f.](X.) is a short for (Xf. .......... [f.] )) for <iiSM
Example 5 (Learning binary operators). Consider setting where we aim to train a classifier fa for recognizing MNIST digits and a classifier for recognizing images of addition and multipiccation taken from some space Xz. The training samples are of the form (I11, I22, x21, 8), where xn and 12 are non-zero MNIST digits with Vi = (I...., , 9), F21 an image of an operator with Y/2 = {+, x), and is the result of applying the operator in 22 the digits in xı1 and 1

---

4.1 ERM Learnability
Similarly to Section 3, to propose a necessary condition for learnability, we consider the most challenging distribution where each D; is concentrated on a single instance x; E X, for 1 < n. Then, the only sample that will be observed during learning is (zj..... 2x,) where z; (zi,...,,2)) for 1 S i S n. Assuming that 2i is the gold label of aq. detecting a classification error is possible only if a misclassification of any F; i.e. [f] * 17, will lead to a prediction vector y with a different image under from the gold label y. i.e., (v") F (z). The above intuition is captured via the notion of multi-unambiguity, which generalizes the notion of M M-unambiguity. Below, we use y; M, for i E [r]. to denote the M,-ary diagonal vector including the y, element only.
Definition 4 Multi-unambiguityy. Transition is multi- unt.-iguombbuussss.o if for any vector y (y"" Mi ...... ), and any position i E [n], such that the vector y' that results after flipping the labels in y, some diagonal vector (y/) M4 + h. has a different image under o, i.e., aty) + aly)).
Multi-unambiuutty reduces to M-unambiguity for n = 1. An example of multi- multi-unambiguitty is below. Example (Learning binary operator, cont'd). In Example 5, the multi-unann calli-unambigutty condition is violated since 2 2+2 2 = x 2. Namely, if a distribution assigns all its weight to the digit 2, then it is difficult for the model to distinguish the two operators. On the other hand, if instead, the label space is 31 = 13..... 9), .J), then the multi-umnamiigutty condition is satisfied.
Bounded risk assumption. Differently from Section 3, multi-unambiguitg alone is not sufficient to ensure learnability. To see this, consider variant of SUM2 where the digits are classified by two independent classifiers, fi and fz. If the distributions of the first and the second image are concentrated on 1 and 7 respectively, but fi (x1) = 7 and f2(22) 1, then these errors cannot be detected. Therefore, we assume there is a constant R < 1, such that R"1 R²1(ft) S R holds for any i [ni] and any É F, We refer to such S 's as zero-one risk R-bounded. This assumption is mild since it only requires the classifiers to be slightly better than being totally wrong. Also, when a small directly labeled dataset is available, one can bound the classification risks away from I with high probability in a uniform manner using standard learning thcory. See Appendix for more details. Now, we ready state the ERM-learnability result assuming IT- F; is realizable under ep1.
Theorem 3 (ERM learnability under multi unambiguity). Assume that there is a constant R < 1, such that for each [n). each f E F, is zero-one risk R-bounded. Assume also that there exist positive integers M and c², such that M; S M and ci S co hold for any E [n]. Then, if a is multi mulli--unmmiguuuus we have:
R. (f) S O(RQ' (f:o))!M²) as R2 of: +0
(8)
Furthermore, for any e,5 E (0, 1), there is a universal constant Cz, such that with probability at least 1 1-6, 8, the empirical partial risk minimizer with of: = 0 has a classification risk R01 (f) < if
mp 2 Cg
TCO
2M 2M" -2
Σ diz Log(nc,M,dio log
noo
12M 2M'"
+ log
1 3
(9)
e (1
RyA
cM - R)a7
Remark. Theorem 3 suggests that the rate of convergence is controlled by M A smaller M leads to more strict unambiguity condition. For example, the case M* 1 requires a to be unstable to any 1-position perturbations, while the case M* = M reduces to M-unambiguity. This observation confirms the intuition that the supervision power of partial labels depends on the "instability" of o.
The top-k partial loss e (f)))) s) for multiple classifiers subject to f E F", transition and E S straightforwardlly extends the top-k partial loss for the single classifier case, see Definition 3. Similarly, the (empirical) top-k partial classification risk of f subject to a straightforwardly extends the one from Section 3.2. Below, we provide a Rademacher-ste
error bound with the top-k loss. Theorem 4 (Error bound under multi-unambiguity with multiple classifiers), Suppose a is multi- unambiguous and each ft is zero-one risk R-bounded, for R E (0, 1). Then, for any integer k 2 1 and any ō E (0, 1), with probability least 1 - 8, we have:
1/M
RO)(f)
no
2 -2(k + 11)
R VKM Σ M R AmpA (Fi) +
log(1/8)
(1 R
2mp
7

---

5 Learning Under an Unknown Transition
We now explore another direction by dropping the assumption that ar is known. Instead, we assume the learner has access to transition space & that contains mappings of the form yuM + including the "true" transition a. Notice that learning now becomes particularly challenging, since G can be expressive enough to lead to correct predictions for s from many wrong classifications.
Problem setting. To illustrate the core idea, we consider a simple setting where we only learn a single scoring function f E FF as in Section 3. However, a is unknown mapping in G. Given partially labeled samples, the learner aims to minimize the zero-one partial risk of f subject to g Rp (f:g) that is defined as the minimal partial risk predict s with candidate transition in G, i.e., R2 (fig)= info-eg eG Rp1 (fi (J)'"). The risk is empirically estimated with partially labeled dataset Tp as info-eg RBy (J: ;';:) ;Tp). We demonstrate this learning setting with the following example:
Example 7. Let G = {(V1 V2) + ay + Byz 3) E R (0),0)}, namely all the weighted sums with at least non-zero weight. We aim to learn MNIST classifier f. given training samples of the form (I), 22, $), where the x; 's are MNIST digits and s is the result of applying some o from G on (y), 32), where yi is the prediction of f on Iú. The gold o, i.e., the exact a and B, is unknown.
5.1 ERM Learnability
Similarly to the known transition case, learnability requires us learn under any data distribution D. Slightly differently from Sections 3 and 4, we start with the adversarial distribution where the mass in D concentrated to single label, i.e., all instances 2; have the same gold label 4, and hence, the training samples are all associated with the gold label vector certain probability that misclassifies 1,4 as 15- Then, the predicted label vectors will be in {1,, 1,) J.M In this case, it will be impossible to detect the classification errors if there is a candidate transition o' E 9 which maps all the vectors in {4; } MM to the gold observation of s. Since the actual a is unknown, we require this does not happen for any pair of o of E G to ensure learnability. Below, we formalize our learnability condition:
(4..... 4.). Suppose there is
Definition (Unambiguous transition space). Transition space G is unambigous, for each o' E G. each diagonal label vector y (l,,... 14),, where 1 E Y, and each 1 + lú where 1q Y, there exists a vector y' (1,,1 such that a' d')))) # aly)-
In pratice, one can examine whether transition space is unambiguous by checking if for each o' E G and any two different labels 4 & Ij. set (o' E {4, (,, is not a singleton. The above ensures that when given fixed diagonal label vector, and when the classifier makes mistakes, the predicted partial labels are not unique, and hence cannot all agree with the ground truth label.
Class G in Example 7 is unambiguous: for each transition (V1, 32) + a' y1 + S'yz and each two labels 1' # I, the set {a'vı + (y 1/2 {1. 2' } is not singleton, so there must exist label vector with different weighted sum that is different than the true sum. A counterexample is below:
Example 8. Lei G ((11, + wiyh + w2y2 + way² + way/ w:; & 0 Vi E [4]]- Consider the true transition a : (y1- 1/22 + 111 vř + U22 y from G and a candidate transition d' (11 92) H> 31 -1--80 vी y22 + v2. Then, G is not unambiguous, since o' d'(y) =o(y) 0 for any y {0, 13 Namely, the partially labeled data are not informative enough to distinguish the label 0 from 1.
Bounded risk assumption. Similarly to Section 4, this unambiguity condition is necessary but not sufficient to show learnability. To show learnability, we additionally assume there is a constant > 0 such that PP (X) This assumption is slightly stronger than that of Section 4 as it additionally requires the classifiers to be not fully wrong for every possible label. The main learnability result of this section is below:
y/Y = y) 2 r for each y E )' and f F. We refer such an f as r-bounded.
Theorem 5. If G is unambigous and any f E F is r-bounded, then we have:
RO1 (1) S O(RR' (M:
RS (f: +
(10)
Furthermore, suppose [F] has a finite Natarajan dimension dizj and the function class ((y s) + (dy s)lo'' E g has a finite VC-dimension dg. Then, for any e, E (0. 1), there a universal constant CA such that with probability at least 1- 6. the empirical partial risk minimizer with
8

---

Rol (f:o) = O has classification risk R (f) < e. if
2M- mp 2 C1 MMM ((d()) log( + dg)) + d1z loge) log
c2M-22 n.l
1 8
+ log
6 Experiments
We further explore the learning scenario in Section 5 with empirical evaluations. We aim to learn an MNIST classifier using the weighted sum of 2, 3 and MNIST digits and assuming that the weights are unknown, in Example 7. The weighted sum function is very expressive it can model Boolean formulas including conjunction and disjunction [36]. Notice that we do not aim to exhaustively assess the weak supervision literature ([24, 43, 59, 13]), but to validate the results of our theoretical analysis.
Baselines. We considered state-of-the-arr syurolyymbolic frameworks, namely DeepProbLog (DLog) [30], DeepProbLog with approximations (DLog-A) A) [31]. NeuroLog (NLog) [43]. NeurASP (NASP) [59], ABL [13], ENT [27] and Scallop [24]. Only the target sum is used during training under those frameworks. DLog and NLog employ the semantic loss without any approximations (see Section 2). NLog(k) denotes an NLog variant where only the top-k predictions are considered during training. while Scallop(k) denotes Scallop using the top-k semantic loss, see Section 3.2. The approximations in DLog-A are different from the ones in NLog and Scallop; however, both DLog-A and NLog employ the semantic loss on the chosen subset of proofs. As the above frameworks learn classifiers under fixed theories only. we considered weights in f1, 4, 5). and used an additional neural classifier to Iearn the unknown weights. Finally, we considered standard supervised learning (SL). To contrast learning under unknown to learning under known transitions, we also ran experiments assuming that the weights are known. Our results show that the classification accuracy exceeds the 98% even for M = 10. More details on this experiment are in the arXiv version of this paper [51].
Results. Tables and 2 report the accuracy of the learned MNIST classifiers over ten runs. #0, #8 and #16 denote the number of directly labeled samples used for pretraining the MNIST classifiers: #0 means no pretraining; for #8 and # #16, the accuracy of the pre-trained classifiers is 37% and 58%. Table I presents results for M = 2, while Table 2 presents results for E 32,3, 4} for Scallop and the two best performing frameworks in Table 1, DLog and NLog- NASP could not scale for M 2 3. We used DLog-A A for M E {3, 4), due to scalability reasons. Similarly, NLog without approximations does not scale for M 4 (N/A indication). In Table the number of weak samples is in parentheses, e.g., 44), For ABL and ENT, we used 10K samples, as they rely on sampling, and used the hyperparameters suggested by the authors.
Discussion. The results confirm our theory: (i) we can learn classifiers under unknown transitions as per Theorem 5 (see the accuracy for DLog and NLog in Table I); and (ii) learning gets harder when M increases as per Eq. (5) (see the accuracy for different M's Table 2). For M = 2, weak supervision leads to better accuracy than SL even without pre-training and with fewer training samples: DLog (44K and Nlog(#4K) lead to mean accuracy 96% and 97%, while SL(4KK) leads to mean accuracy 93%, see Table 1. This result suggests that the r-bounded assumption in Theorem 5 could be potentially relaxed. Another observation is that the approximations in DLog-A are less effective than the top-k one of NLog. We leave the theoretical analysis of the latter approximation as part of future research. Table 2 also suggests that the top-k semantic loss constitutes the most scalable and effective approach to training: in contrast to DLog-A and NLog, the accuracy of the digit classifier reaches 78% for M = 4, when h = 4 for Scallop.
Our empirical analysis shows that key issue is scalability. This is a known problem in neuro- symbolic learning and is partially because the relevant problems logic are intractable. For instance, semantic loss requires computing the models of Boolean formulas, which is #P-complete. Reasoning over logical theories can be also intractable [2], if not undecidable. Scalability straightforwardly affects accuracy, e.g., NLog obtains better accuracy over DLog for M = 3 (see Table 2) due to its ability to explore the whole search space. also worth stressing that Scallop could not scale beyond M 4 for l > 1. The above challenges bring up new research directions [44, 41]. Closing this discussion, it is worth exploring why ABL and ENT led to low accuracy*.
'The authors from [43] also reported low accuracy for ABL for scenarios.

---

Table 1: Classifier accuracy for WEIGHTED-SUM for M = 2. #0, #8 and #16 are # of directly
labeled samples used for pre-training. Inside the parentheses are the of (weak) training samples.
SLZ#4K)
SLZ#8K)
DLog(#4K)
NLog(#4K)
NASP(#IK)
ABL
ENT(#1OK)
#0
93% + 0.01
96% = 0.008
96% = 0.004
97%
+ 0.05
98%,
9% + 0.05
10% + 15.2
93% +: 0.01
96% 0.008
96% + 0.005
97% 4: 0.005
98% 4.001.0.0
10% 0.01
43% 17.11
#16
93% 4 0.01
96% = 0.008
96% 4 0.001
97% 4 0.01
98%
11% 0.1
49% 16.4
Table Classifier accuracy for WEIGHTED-SUD for M E (2,3,4) 4). #0 and #16 are of directly labeled samples used for pre-training. Inside the parentheses are the # of (weak) training samples.
M 2, mp = 4K
3. mp = 4K
M
4, mp = 10K
#0
#16
#0
#16
#0
#16
DLog-A
34% 1 0.1
80% 1 0.06
24% 1 0.09
27% 1 0.133
18% = 0.02
26% 1 0.25
No.og
97% + 0.05
97% 0.01
61% +: 0.07
97% + 0.00
N/A
N/A
Nl.ag(5)
48% + 0.003
87% + 0.007
27% + 0.06
84% 0.06
29% 0.1
46% + 0.05
(callop(1)
97% + 0.05
0.01
21% 3.5
97% 0.01
36% + 0.2
54% = 0.02
Scallop(4)
97% = 0.05
97%
53% 0.15
97% 0.07
51% 0.09
78% + 0.05
7 Related Work
We provide an overview of the literature that closely relates to our work. A more comprehensive review of PLL, latent structural learning, and suuro-yymbolic learning, is presented in Appendix F.
Partial label learning. Learnability of PLL is typically shown under the small ambiguity assumption [11, 28, 5]. While it is technically possible to cast our problem to standard PI.L by viewing a target partial label for the hidden labels y. the small ambiguity condition is violated in
since a distracting label can occur because a is deterministic. Therefore, our proposed conditions relax and generalize the small ambiguity by allowing deterministic transitions, see Appendix E.3. Another line of work in weak supervision exploits the invertibility of transition matrices [46] to compute posterior class probabilities [8, 9, 61]. Our learnability condition, M M-unambiguitty and the invertibility condition do not imply each other, see Appendix E. and E.2. There, we also show that small ambiguity and the invertibility condition do not imply each other, which might be of independent interest. Another related topic is learning with label constraints [21, 6, 49], where the subset S y The
label of each instance æ (possibly structured) the dataset constrained difference is that the constraint mapping itself is known to the learner and hence can be encoded in the inference algorithm directly, for example, via the CCM [6].
Neuro-symbolic and structured learning, We were motivated by frameworks that employ logic for training neural models [30, 53, 13, 59, 43, 31, 24, 27, 23]. We prove learnability under (un- known) transitions that capture different languages and error bounds under the SL [56] and top-k approximations. Notice that [58] also proves the consistency of a top-k loss. However, they use a zero-one sero-one-ttyle loss for standard supervised learning. Our work is closely related to [62], which studies a similar problem of weakly supervised learning with multiple instances. Our results are stronger in the sense that we propose sufficient and necessary conditions to recover the hidden labels, while [62] concerns the likelihood of the observed labels rather than the hidden ones. Our work is also relevant to latent structural prediction [42, 35, 34, 32]. To our knowledge, no formal learning guarantees have been given for that problem. Complementary to ours the work in [19, 47, 33) that integrates combinatorial solvers into deep models.
8 Conclusions
We formulated multi-instance PLL and showed its connections with latent structural and neuro- symbolic learning. Our work exhibits greater level of flexibility compared to (single-instance) PLL, as it allows for multiple instances and deterministic transitions. We introduced minimal assumptions that enabled us to establish ERM-leamability and derive error bounds with the top-k semantics loss. Our findings suggest that the interaction of multiple instances in forming the observed labels can help relax the learnability assumptions in weakly supervised learning. For future work, we will further relax the learning conditions by assuming a certain degree of smoothness for the data distributions. Another direction is to explore the setting where the hidden labels are non-i.id. or structured.
10

---

Acknowledgements
This work was partially supported by Contract FA8750-19-2-020 with the US Defense Advanced Research Projects Agency (DARPA). Approved for Public Release, Distribution Unlimited. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense or the U.S. Government.
This work was also partially sponsored by the Army Research Office and was accomplished under Grant Number 1911NF-20-1-00
The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies. either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
This work was also supported by Contract (A87500-1-2-110 with the US Defense Advanced Research Projects Agency (DARPA). Approved for Public Release, Distribution Unlimited. The views expressed are those of the authors and do not reflect the official policy position of the Department of Defense or the U.S. Government.
This work was also partially funded by ONR Contract
References
[1] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley, 1995.
[2] Bean-François Baget, Maure Mugnier, Sebastian Rudolph, and Michaël Thomazo. Walking the complexity lines for generalized guarded existential rules. page 712-717, 2011.
[3] Othman El Balghiti, Adam N. Elmachtoub, Paul Grigas, and Ambuj Tewari. Generalization bounds in the teepoii-teen-optimize framework. In NeurlPS, pages 14389-14398, 2019.
[4] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. The Journal of Machine Learning Reseurch, 3:463-482, 2003.
[5] Vivien Cabannes, Alessandro Rudi, and Francis Bach. Structured prediction with partial labelling through the infimum loss. In ICML, page 2230-1239, 2020.
[6] Ming- Wei Chang, Lev Ratinov, and Dan Roth. Structured learning with constrained conditional models. Machine Learning, 88(3)3399-431, 2012.
[7] Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence, 172(6):722 - 799, 2008
[8] Jesús Cid-Sueiro. Proper losses for learning from partial labels. In NeurIPS, pages 1574-1582, 2012.
[9] Jesús Cid-Sueiro, Darío CarefaaGarria, and Raúl Santos-Rodríguee Consistency of losses for learning from weak labels. In ECML PKDD, pages 197-210, 2014.
[10] Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang. Structured Prediction Theory Based on Factor Graph Complexity. In NeurlPS, 2016.
[11] Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. Journal of Machine Learning Research, 12:1501-1536, 2011.
[12] Wang-Zhou Dai and Stephen Muggleton. Abductive knowledge induction from raw data. In Zui-Hua Zhou, editor, IJCAI, pages 1845-1851. AAAI, 2021.
[13] Wang- Zhou Dai, Qiuling Xu, Yang Yu, and Zhi-Hua Zhou. Bridging Machine Learning and Logical Reasoning by Abductive Learning. In NewrIPS, pages 2816-2826, 2019.
[14] Artur S. Avila Garcez, Krysia Broda, and Dov M. Gabbay. Neural-symholic learning systems: foundations and applications. Perspectives in neural computing. Springer, 2002.

---

[15] Adam N. Elmachtoub and Paul Grigas. Smart "predict, then optimize". CoRR, abs/ 1710008005 2017.
[16] Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61(1):1-64, 2018.
[17] Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu. Agnostic learning of monomials by halfspaces is hard. SIAM Journal on Computing, 41(6):1558 1590, 2012.
[18] Jonathan Feldstein, Dominic Phillips, and Efthymia Tsamoura. Principled and efficient motif finding for structure learning of lifted graphical models. CoRR, abs/2302.04599, 2023.
[19] Aaron M. Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. program as layer. CoRR, abs/ htss/9907.0592 2019.
Mipaal: Mixed integer
[20] Robert Fink, Jiewen Huang, and Dan Olteanu. Anytime approximation in probabilistic databases. VLDB Journal, (2(()) 848, 2013.
[21] Kuzman Ganchev, João Graça, Jennifer Gillenwater, and Ben Taskar. Posterior regularization for structured latent variable models. Journal of Machine Learning Research, 11:2001-2049, 2010.
[22] Nitish Gupta, Sameer Singh, Matt Gardner, and Dan Roth. Paired examples as indirect supervision in latent decision models. In EMNLP, pages 5774-5785, 2021.
[23] Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard Hovy, and Eric Xing. Harnessing deep neural networks with logic rules. In ACI., pages 2410-2420, 2016.
[24] Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scallop: From probabilistic deductive databases scalable differentiable reasoning. In NeurIPS, pages 25134 25 25145, 2021.
[25] Rong Jin and Zoubin Ghahramani. Learning with multiple labels. In NeurlPS, pages 897-904, 2002.
[26] Antonis C. Kakas. Abduction. Claude Sammut and Geoffrey I. Webb, editors, Encyclopedia of Machine Learning and Data Mining, pages 1-8. Springer US, Boston, MA, 2017.
[27] Zenan Li, Yuan Yao, Taolue Chen, Jingwei Xu, Chun Cao, Xiaoxing Ma, and Jian Lu. Softened symbol grounding for neurosymbolic systems. In ICIRR 2023.
[28] Li-Ping Liu and Thomas G. Dietterich. Learnability of the superset label learning problem. In ICML, pages 1629-1637, 2014.
[29] Jiaqi Lv, Miao Xu, Lei Feng, Gang Niu, Xin Geng, and Masashi Sugiyama. Progressive 2020.
identification of true labels for partial-labe learning. In ICML, page
[30] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logie programming. In NeurlPS, pages 3749- 3759, 2018
[31] Robin Manhaeve, Giuseppe Marra, and Luc De Raedt. Approximate Inference for Neural Probabilistic Logic Programming. In KR, pages 475-486, 2021.
[32] Tsvetomila Mihaylova, Vlad Niculae, and André F. T. Martins. Understanding the mechanics of SPIGOT: Surrogate gradients for latent structure learning. In EMNLP, pages 2186-2202 2020.
[33] Anselm Paulus, Michal Rolinek, Vít Musil, Brandon Amos, and Georg Martius. Comboptnet: Fit the right np-hard problem by learning integer programming constraints, 2021.
[34] Hao Peng. Sam Thomson, and Noah A. Smith. Backpropagating through structured argmax using a SPIGOT. In ACL., pages 1863-1873, 2018
[35] Aditi Raghunathan, Roy Frostig, John Duchi, and Percy Liang. Estimation from indirect supervision with linear moments. In ICML, volume 48, pages 2568-2577, 2016.
12

---

[36] Dan Roth and Wen-tau Yih. Global Inference for Entity and Relation Identification via Linear Programming Formulation. MIT Press, Introduction to Statistical Relational Learning edition. 2007.
[37] Rajhans Samdani, Ming-Wei Chang, and Dan Roth. Unified expectation maximization. In ACL, pages 388-698, 2012.
[38] Prithviraj Sen, Breno W. S. R. de Carvalho, Ryan Riegel, and Alexander Gray. Neuro-symbolic inductive logic programming with logical neural networks. AAAI, 36(8):8212-82119 2022.
[39] Junghoon Seo and Joon Suk Huh. On the power of deep but naive partial label learning. In ICASSP, pages
2021.
[40] Shai Shalev-Shward and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014.
[41] Mate Soos, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S. Meel, and Maciej Obremski. Engineering an efficient approximate dnf-counter. In IJCAI, pages 2031-2038, 2023.
[42] Jacob Steinhardt and Percy S Liang. Learning with relaxed supervision. In NewrIPS, volume 28, 2015.
[43] Efthymia Tsamoura, Timothy Hospedales, and Loizos Michael. Neural-symbolic integration: A compositional perspective. In AAAI, pages 5051-5060, 2021.
[44] Efthymia Tsamoura, Jaehun Lee, and Jacopo Urbani Probabilistic reasoning at scale: Trigger graphs to the rescue. Proceedings of the ACM on Management of Data, 1(1), 2023.
[45] Shyam Upadhyay, Ming-Wor Kiig Chang, Kai-Wei Chang, and Wen-tau Yih. Learning from explicit and implicit supervision jointly for algebra word problems. In EMNLP, pages 297-306, 2016.
[46] Brendan van Rooyen and Robert C. Williamson. A theory of learning with corrupted labels. Journal of Machine Learning Research, 18(228):150,, 2018.
[47] Marin Vlastelica, Anselm Paulus, Vít Musil, Georg Martius, and Michal Rolínck. Differentiation of blackbox combinatorial solvers. CoRR, abs/1912.02175, 2019.
[48] Haoyu Peter Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimization with principled objective relaxation. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, NeurlPS, volume 35, pages 31444-31458.
2022.
[49] Kaifu Wang, Hangfeng He, Tin D. Nguyen, Piyush Kumar, and Dan Roth. On regularization and inference with label constraints. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 Proceedings of Machine Learning Research, pages 35740-35762. PMLR, 23-29 Jul 2023.
[50] Kaifu Wang, Qiang Ning, and Dan Roth. Learnability with indirect supervision signals. In NeurlPS, volume 33, pages 9145-9155, 2020.
[51] Kaifu Wang, Efi Tsamoura, and Dan Roth. On learning latent models with supervision, 2023.
weak
[52] Lei Wang, Dongxiang Zhang, Jipeng Zhang, Xing Xu, Lianli Gao, Bing Tian Dai, and Heng Tao Shen. Template-hased math word problem solvers with recursive neural networks. In AAAI, pages 7144-7151, 2019.
[53] Rei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In ICML., 2019.
[54] Hongwei Wen, Jingyi Cui, Hanyuan Hang, Jiabin Liu, Yisen Wang, and Zhouchen Lin. Lever- aged weighted loss for partial label learning. CoRR, abs/2106.05731, 2021.
13

---

[55] Zhaofeng Wu. Learning with latent structures in natural language processing: A survey. arXiv preprint arX1v:2201.00490, 2022.
[56] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolic knowledge. In ICML, pages 5502-5511, 2018.
[57] Ning Xu, Congyu Qiao, Xin Geng, and Min-Ling Zhang. Instance-dependent partial label learning. In NeurlPS, volume 34, pages 11119-7713, 2021.
[58) Forest Yang and Sanmi Koyejo. On the consistency of top-k surrogate losses. In JCMI, volume 119, pages 10727-10735, 2020.
[59] Zhun Yang, Adam Ishay, and Joohyung Lee. NeurASP: Embracing neural networks into answer set programming. In IJCAI, pages 1755-1762, 2020.
[60] Peilin Yu, Tiffany Ding, and Stephen H. Bach. Learning from multiple noisy partial labelers. In PMLR, volume 151, pages 11072-11095, 2022.
[61] Mingyuan Zhang, Jane Lee, and Shivani Agarwal. Learning from noisy labels with no change to the training process. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 12468-12444 2021.
[62] Yivan Zhang, Nontawat Charoenphakdee, Zheng Wu, and Masashi Sugiyama. Learning from aggregate observations. ArXiv, abs/2004.06316, 2020.
14

---

Appendix
This appendix organized follows:
In Appendix A, we provide detailed definitions for the loss functions and the complexity measures we use in our work.
Appendix B, C and D, we provide the proofs to all formal statements.
In Appendix F, we provide comprehensive review of the related work in PLL, latent structural learning, contrained learning, and neuro-symbolic learning.
In Appendix E, compare common distributional assumptions in the standard PLL literature with ours. In particular:
1. In Appendix E.1, provide transition matrix [8, 46] formulation of PLL and show that M -uunambigguity does not imply transition matrix invertibility for multi-instance PLL and vice versa.
2. In Appendix E.2, we show result of independent interest: that transition matrix invertibility does not imply small ambiguity [28] and vice versa.
In Appendix E.3, we show that M Mu-unambiguity, the unambiguity notion proposed in Definition 1, is extension of the small ambiguity degree [28], by considering generalized setting where a is stochastic.
In Appendix G, we provide implementation details of our experiments.
A Preliminaries
Table 3: The 2* interpretations of {A1,, A2 A1.0, A2,2} and their corresponding truth probabilities subject to the w and yo from Example 9. Interpretations that are not models of yp have zero probability.
A
Az.0
A
Az.3
T
((A.2)) x (1 ()2))) w(A1.)) x x((22)
T
L
(1 (1- w(A1a)) w(A2.) w(Ar,) w(A2))
x(A1.2) -1- o(41,) w(A2a) of ((A1.) x w(A2g) x (A1,oo) x (1 w (222)) w(Ar,) w(A2
w(Ar,o)) x w(Ar,) x w((gg) w(4 x w(A2a)) w(A1,) (( w(1),) w()g))
In this section, we introduce in further detail some key notions used in the main body of our paper. We start with the definition of the semantic loss [56].
A.1 Loss functions
Semantic Loss (SL) [56] has been adopted to train classifiers subject to logical theories [30, 43, 24]. SL is the cross entropy of the weighted model counting (WMC) [7] of formula subject to softmax output. Below, we provide the necessary notions. Let Z denote a set of Boolean variables. An interpretation of Z is mapping from each A 2 to true (T) false (1). Interpretation T is model of a Boolean formula sp, if &o evaluates to true in T. We use the notation A E yp to denote that Boolean variable occurs in çp. By treating each Boolean variable A occurring in yp as an independent Bernoulli random variable that becomes true with probability w(A) and false with probability (A)), the different interpretations of induce probability distribution, where the probability P. (1, (I) of each interpretation / subject to w and &o is given by:
I [AE w(A) IAAEVI(())= w(A)) I is model of
(I,
(11)
otherwise.
15

---

The WMC WM w) of & under w then denotes the probability of &p being satisfied, i... it evaluates true, under w² and defined as:
WMC( ==
Σ
(
(12)
Interpretation I of the variables in
Assuming that each variable in is associated with class from V/ and treating f(x) as mapping from the variables in yp to the f's scores on z, the semantic loss of ço under f(x) defined as:
SL [(x)) == - loolloo((())) (WMC(e
(13)
We demonstrate the above concepts via Example 4. Example 9 (Example 4, cont'd), Recall that the Boolean formula induced by the partial label 8 = 2 is (A A A2.0) V (A1.0 A A2.2), where Aij is a Boolean variable that is true iff the i-th imput digit has label j. Given a probabilistic prediction (xx), variable Ai, is assigned probability (xx)), inducing a probability mapping ==
U
(Ary fz (zx) Table 3 shows all
(1(1.)),
interpretations of {A1,2, A2,,, A1,0, 22,23 and their corresponding probabilittes subject and s. The WMC of &p under is the sum of the probabilities of all the 2 interpretations.
To establish SL., each (zi, u)), where x = (#1, TM), E [M] and yM, is associated with distinct Boolean variable Ai,y-
The nature of multi-instance PLL implies Boolean formulas in disjunctive normal form (DNF), where disjunction over conjunctions of Boolean variables or their
formula in DNF form, if negations, see Example 4. In fact, each Boolean formula computed out of the labels associated with partial label is positive DNF formula, i.e., DNF formula where variable occurs negatively. Using the union bound of standard probability theory and the model-basee semantics of formula probabilities [20], the following result directly follows:
Lemma 2. Let ....... K be K positive conjunctive formulas over the set of Boolean variables Z and w : Z + (0, 1). Assuming that each variable Z E Z is treated as an independent Bernoulli random variable that becomes true with probability w(Z) false with probability 1 w (Z), the following holds:
K Σ WMC(
WMC(V D. 1=1
(14)
where the equality holds when the 4y's 'ss are logically inconsistent, i.e., there is no interpretation of Z which two or more conjunctions are simultaneously true.
Let E denote exclusiveness constraints among the variables occurring in the D.'s. For instance, returning back to Example 9, to align with the semantics of the classifier, only of the Boolean variables A1,2 and A1,0 can be true in each interpretation'. Then, WMC(V 4 A E,w) s WMC(V Tb,, w). This is because Σ reduces the number of models of
In addition, when the ' share no Boolean variables, the following holds [20]:
K WMC V b
K
=1
I WMC()..w))
(15)
Due to (15), the top-k partial loss becomes
(f(2). = -og(1
I (1 (y) 1=1
(16)
when the (O's in Definition 3 share no Boolean variables.
Notice that WMC also applies to the case where w maps each Boolean variable non-negative real number. However, when restricting to (0, 1), the WMC a Boolean formula equals to its probability [20]. 'The above be captured via the integrity constraint -(A1, A1,0).
16

---

A.2 VC and Natarajan dimensions
We use the following definitions of VC and Natarajan dimensions, which can be found in [40]. Definition 6 (Shattering: multiclass classifiers). Let H be space of multiclass classifiers of the form
X' + V A set C' C X is shattered by H. if there exist two functions ho, h1 C - Y, such that
For each C, have that ho(x)) + hl(x).
For each B C, there exists a function h H. such that
Vx E B, h(x) = ho(x) and Vx E (()
Definition 7 (Natarajan Dimension). The Natarajan dimension of denoted by (a)(H), is the maximal size of a shattered set C X. H is space of binary classifiers, then its Natarajan dimension also called its VC dimension and denoted by VC(H).
A.3 Rademacher complexity
We use the following definition of the (empirical) Rademacher complexity of a multiclass scoring space F, which is adapted from [10].
Definition 8 (Rademacher complexity). Let = fai..... ..... Fm be set of instances that are i.i.d. drawn from Dx. The empirical Rademacher complexity of F with respect to T defined by
1 m
Rom (F;T)
Fie
sup
ΣE l REFi-lyE)
(17)
where the Giy are ii.dd Rademacher random variables, each of which is uniformly distributed over {-1, +13, and is vector over all the ei,y 's. Furthermore, the Rademacher complexity of scoring class F is the expectation of the empirical version:
Rm (F) = ETT Rm (F;T)
(18)
B Proofs for Section 3
Before proceeding with the proofs, we will introduce some useful notation.
Definition 9 (Probability of misclassification). Let f be a scoring function in F. and 1i,1 be two labely in Y. Then, the probability that misclassifies label 1 subject to samples drawn from DD
is defined as
Es,,, (f) ((x.))- ([f](x)) = -y
(19)
For convenience, here we consider the general setting where the transition function is unknown to the learner but instead, a transition class & is provided. The results for the special case where is known to the learner can be derived by setting G = {a}. Now, fix a scoring function class F and transition class G. We define Hy.g g as the class of binary classifiers that, given samples of the form (xx s), for æ E X and S, output zero, if the predictions for abide by the partial label s and one, otherwise. Formally:
HF.g ((x, 8) + ([f(())))) & s}If E FF, EG
(20)
For the case where the transiton known the learner, also denote H.F = Hr for simplicity. From (20), it follows that the zero-one binary classification loss of a classifier far E H.F.g. equals the zero-one partial loss subject to o' defined as do (f(x), s) = 1fo' (f(x)) * s}. We now present the following lemma that bounds the VC dimension of H. which is reminiscent of the arguments of [28, 50]. Lemma Fix a scoring function class F and transition class G. Let Nat((FF) = diz Do be the Natarajan dimension of [F] and de be the VC dimension of the class of classifiers ((,,)) + 1(o (y) solo' E {), where E yad and E S. The VC dimension of class H.. is bounded as:
d < 2 ((d1)) + dg) log GM (d + dg)) + 2d(5) log
(21)
17

---

Proof. Suppose that the VC dimension of H...g is d. Let N be the maximum number of distinct ways to assign labels in y to points in X' S using [F]. Each possible label assignment leads set of d elements in X VI x S, and for any d elements, by Sauer-Shelah lemma (see, for example, [40]'s Lemma 6.10), there are at most
eMd de dg
ways for G to decide if 1 (z) # st where is the base of the natural logarithm. Based on the above, have:
eMd
de
2 S N
dg
Therefore, N 2 2 (dg/eMd)
By Natarajan's ' lemma of multiclass classification, we have:
N S (Md)
(22)
Combining (22) with the above equations, follows that
dg
de
(Md) 2 2 N 2 2d
eMd
Taking the logarithm on both sides, we have:
di Log(MM) + 2d(r) log 2 dlog 2 + (log dg - log(MM) 1)
Rearranging the inequality yields:
d log 2 + dg (log dg - 1) & (dp) + doog
(logd=d)))))) d log M) + 2d17 loge
d
$ (d(=) + d3) 6(d + dg) + +log(6(d( + dg)) -1)
+ (dpl + dg) log M + 2d1 loge
d/6 (diz + dg)
+ dę)) - 1) + 2d| log
- d/6 (di) + dg) (6M dg)) dg + 2d(z) log
where the second step follows from the first-order Taylor series expansion of the logarithm function the point 6(d + dg). Therefore,
d 5 (dir + dg) log(6. (dpr + dg)) + 2d17 loge dg (log(de))
log 2 1/6
< ((d + dg) log(6. dg)) + 2d logc)
where the last step follows from the fact that log 1/6 > 1/2. The above concludes the proof of Lemma 3.
Notice that if a is known to the learner (i.e., g is singleton) and hence, dg = 0², then (21) becomes
$ (d1z) log( + 2d log c)
(23)
B.1 Proofs for Section 3.1
Lemma 1. If is M M-unambigous, then have:
R² s ( (R: (M: RR (f:o) +
(1)
Moreover, a is not M M-umambiguous, then learning from partial labels is arbitrarily difficult, in the sense that a classifier f with partial risk R.1 (f:a) can have a risk R (f) 1
Singleton hypothesis classes have VC-dimension equal zero.
18

---

Proof. Given (19), the zero-one risk of can be rewritten as
n (f) = Σ Li1
Ei,as(f)
(24)
Since is M-unambigous, know that if all the M input instances have the same label and wrongly classified as another label, then the predicted partial label will be wrong. Therefore, the zero-one partial risk is lower bounded by the probability of such events, namely the sum of the same type of classification mistake being repeated by M times. We have that:
Rp (1:0) 2
Σ 4x1s
Fi,,, (f)
Enple Pa..,;(1)
2 (clc- --
(Power Mean inequality)
(25)
R.1 RT)(F)
(elc 1))M-T
where y = c. Rearranging the inequality yields:
R²) S (R ())
- (c2M-2R (f:o))
(26)
The above concludes the first part of the proof of Lemma 1.
We now focus on the second part of the proof. If o is not M-unambiguous, then from Definition 1, we
know that there exists pair of labels y.y' E y' with y' + y. such that o......, y) o aly'.... ..... y/) holds. Consider now sample (æo. y) drawn from D. If D concentrates all its mass on Zo E X. i.c.
(D(0 = and classifier misclassifies zig as y' + y, then R2 (f:o)= = 0 but R (f) = 1. The above concludes the proof of Lemma 1.
Theorem 6 (ERM learnability under M- M-unambiguity). Suppose F is realizable under ep and [F] has finite Natarajan dimension dry, Then for any e, E (0, 1), there exists a universal" constant Co > O, such that with probability least 8, the empirical partial risk minimizer with RyI (J;a; Tp) has classification risk (u) t,
2M- (og))og(6e)M log C.
2M N
))
1 (53
mp 2 Co Co-
logg
(27)
Proof. Let f be the empirical partial risk minimizer, such that RBl (f: a: Tp) = holds. For any E (0,1), 1), we know by the proof of Lemma that (f) S (c2M-2 (f:a)) holds. Hence, by bounding RD. (f:o) S eM /c2M22 the following would follow: R0 (f) I c. By the standard bound for sample complexity based VC-dimension (see, for example, Theorem 6.7 in [40]), know that for any confidence parameter i E (0, 1), RD S (22M-2R0) (J:o)) holds with probability at least 1 - 8, if
mp 2 mmHH,, CM /
(28)
where
m(H,,,,t) := H (o -(M (1)
! +log
)
(29)
where C is universal constant. Combining (23) with (28) and (29) yields the desired result, concluding the proof of Theorem 6.
Before proving Proposition
will introduce more general definition of unambiguity:
Definition 10 (I-unambiguity). Mapping is T-unambiguous if there exists a set of distinct T indices (i1,...,44} S [M), such that for any y Y having the same label in all positions in I, the vector yf that results flippin 1 to l' + in those positions satisfies a a ) * o(y).
A constant is universal if it that does depend the parameters of the learning problem (e.g.. M c).
19

---

We now prove the following lemma based on I-unambiguity:
Lemma 4. If both and M -lunambigouss, then we have:
R - O((RP) (f:o))/1)
(30)
Proof. Let I be the disambiguation set a. Then, for each pair of labels 1, I, E y with I, + 1j. the following holds with probability Ei,,, (f)": the gold labels I are all 4, but they are all misclassified by as j. Since a is l-unambiguous, this type of error implies partial label error. Then, we have the following:
R$ (f:0)
E (1) Lil
R ( (f))
Probahility of correctly classifying remaining labels.
Eieti Fi,,, (1) (1 (1-R010 (
(31)
(Power-Mean Incquality)
(clc 1))1-1
R (1
(ccc-1))*
Since a is also M --unambigous by assumption, we have from (26) that Rd S (RR (f:o))
Hence, 1 R (f) 2 1 e (Rp (f:o)) IMM Combining the above with (31), yields:
R2 ():o) Ru (c2 (f: (f:o))
(c(c 1)
Therefore,
R (
1/1
R (f) RT S
(1 (c2M- (c2M-2001 (f:o)) /MM
Based the above, we conclude that
R R (f) < 1 (R (f:o)
(32)
where
) de ) )
1621-2
2/1
, t H> min
min
(1- (1-202M-22
t
(33)
(c2M-24)
as Rp(f; (01) - We can see that (t) = 0(t1/1) as O. The above concludes the proof of Lemma 4.
We are now ready to prove Proposition
Proposition (ERM learnability under 1- and M M-unambiguity). a is both 1- and M Munnambigous, then we have:
R²) & O(RRI (J;a)) as (J=o) Furthermore, F is realizable under for and [F] has a finite Natarajan dimension diz), then for any 8 10,1) and (0,1) that is sufficiently close to O, there exists universal constant C1, such that with probability least - 8, the empirical partial risk minimizer with Ru1 (f;o) 0 has classification risk R (f)= c,
(3)
mp 2 - (os7log(6)M log (2) + log
)
!
Proof. The first claim can be derived from Lemma 4, by setting 1. For the second claim, using inequality (33) and letting I = 1, we know that
22I(f) < (1- (12 (22-200/MMM4-
Suppose is small enough so that
E 12MMM22M- 2M-2
(34)
20

---

Now, if we could bound Rp (f:o) S E/2, we will have that
c/2
())
(1 (c2M-2 (
c/2
(1 (c2M-24) x1 3
c/2
$
(Beroulli's ' inequality)
M (c2M-2e)
6
(Equation (34))
Now, goal is bound the sample complexity that Rp (f:or I e/2. Similarly to the proof of Theorem 6, by the standard bound for sample complexity based on VC-dimension, for any 5 E (0, 1), R2 (f:a) & c/2 holds with probability at least 1 6, if
2 m mH,F.g.ō,c/2)
(35)
where
m(Hr,g, == C (vC(H)=s) log ( (
log )
(36)
where a universal constant. Combining (23) with (35) and (36) yiclds the desired result. The above concludes the proof of Proposition 1.
B.2
Proofs for Section 3.2
B.2.1 Relating the top-k semantic loss the infimun/minimum loss
In this section, we show that the minimal loss can be viewed as special case of the top-k partial loss from Definition 3.
We start by recapitulating the definition of the minimal loss [29]. Given scoring function f X - RM, a loss function l and partial labelset s E 2", the minimal loss [29] for standard PLL [28] is defined as:
min (f((),,
(37)
yEs
Below, we show that the minimal loss coincides with the top-1 partial loss.
For multi inttancesttnne PLL, we can extend (37) in straightforward fashion as follows:
min {(f(x),)) y) o(v)=s
(38)
f the cross-entropy loss, then the minimal loss finds the most likely label vector in the preimage
of s. Now, let focus Definition 3. If we set k 1 in & then the only model for the formula
(2) = A A A MM assigns to each Boolean variable occurring in y value T.
The WMC of to given by
M pu Pd
(x:)
max (v) oly)=s
(39)
which is also the maximum likelihood that can be obtained the preimage of s. This implies that the top-1 semantic loss finds the minimum negative log-likelihood. Therefore, the top-k partial loss equals to the minimal loss for 1.
Furthermore, for partial label E 2n and a label prediction z, the infimum loss [5] is defined as
L(z, s) = inf {(2, y) VEs
Treating the probabilistic prediction f(x) as generalized label, the above definition becomes equivalent to that of the minimal loss (notice that y is finite, so infinum = minimum).
The above discussion shows that the minimal loss is special case of the top-k partial loss.
21

---

B.2.2 Proofs
To prove the main result of this section, we will need the following definitions and lemmas.
Definition 11 (Top-k partial e loss). For an integer 1, the top-k partial E loss under scoring function f. input E X and partial label E S is given by
k = -1 --C (V f(x))
(40)
where y(2), ;....; ......y'* (b) are as in Definition 3.
We now prove the following lemma:
Lemma 5. For any classifier f E F, E X.M, E S and integer k 2 have:
pp ()) S (A: 1))(((()) s) S (k + ()))((()).))
(41)
Mz) the most likely label assignment æ by f. If @p y s) = holds, then ( # s. Therefore y is different from the top-k y vectors. Hence, the probabilities of the y (s,, for E [kt], and y
Proof. Let denote by y, = ([f)
most 1, i.e.,
2 P)(w) (31) + Σ (x))))
(42)
+1 P)(a) (2)
The second inequality holds because the assignment y, has a larger score than any other label assignments in the preimage of Furthermore, by Lemma 2, we know that
WMC (Ve) (0),
A (1) f(x)
f(x)
Pr
(43)
k+1
Since the zero-one loss 60l (y 8) is by definition either 0 or we have:
1 01
(f k ++1* P (f(x),s)
Finally, from the inequality log(1 2 t Vt > 0, we know that (f(())), lower bounds the cross-entropy top-k loss:
(f()),,, (z))
(44)
The above concludes the proof of Lemma 5.
The following two lemmas concern the Lipschitzness of the top-k loss.
Lemma 6 (Contraction lemma (Lemma 5 from [10]). Let N and m be two positive integers, Let also H. be set of functions that map X to IR" IR.. Suppose that for each E [m], function V IR - R is p.- Lipschitz with the 2-norm, i.e..
[V(('') v.(w)) S melleo - ol12 Ye, v' E
(45)
Then, for any set of m points Tl, Im E X. the following holds:
22 E.
F
sup
Σ a. (h(x))))))))
Gappch(ass)
(46)
m
hEH
where the a,'s and the ei 's are independent Rademacher variables uniformly distributed over (-1,+1)
Lemma (Lipschitzness). For given scoring function X x + IR and vector of instances X let f(x) (xx) E IR MxX1 denote the vector of scores for each label. Then, for any two scoring functions f, f, E F. and any sample (x, 8) E Dp, have:
(f()))) (f((), (=) fx)))]
(47)
22

---

Proof. Given (z, s), the derivative of the WMC with respect to the score (x,) for a label E y is if Ab, does not appear formula sp. Otherwise,
WMC(V 1 , d(f)(x;))
E
II
w(A).
II
(1-w(A))
Model of NEP]A(A==T
AEH]T(A)=1
E Model o
(Ai,))
II
w(A)
II (1- (1))(A))
AEP),)1(()==
E Model of AEPIs
II
w(A)
II (1-wl
AEP)y)((A==L
WMC(V. ff)
d(fx(x:))
where
I(ALy)=
(A
[-1
(48)
otherwise
and Pi.y is the logic formula that deletes all occurrences of A in 4. Therefore, the 2-norm of the gradient of the mapping f(x) + s) is upper bounded by
(number of Boolean variables yp) S VMk
(49)
The boundedness of the gradient implies that the function f(æ) + W f() is Lipschitz with Lipschitz constant VMK, concluding the proof of Lemma
We are now ready present the proof of the main theorem of this section.
Theorem (Error bound under unambiguity). Let an integer k 2 1 and ō E (0, If a is both and M M-unambiguous, then with probability at least - 8, we have:
log(1/5)
RO) 5 (k (k+1)
R#(f:0: Tp) + 2wKM3/29 (F)
(7)
2mp
-iaaeen e (f(x), s)) s)/m mp the empirical counterpart of (6) and & is an increasing function that satisfies lim ((t)/t
where Tp) = E(a,))TT
Proof.
Bound with the partial risk. From the proof of Lemma and 1, we know that
R²) < ((RP'((:)))
where
① min ((1 (c2M (1--(c22-2))1//1) 11MM-22)1/MMM--- t 2
(50)
We can see that + is monotone increasing and lim; (t)/tt =
Bound the zero-one partial risk with the top-k loss. From Lemma 5, we know that ep (f(x), s) s (k + (f)))) Taking expectation yields:
Rp (f:a) S (I: ();0((;0)
Bound with the empirical risk. Given partially labelled dataset Tp {xx, s:) 1m by the standard
Rademacher complexity bounds, we know that for each 5 E (0, 1) and each E F, the following inequality holds with probability least 1 5:
log(1/5)
R$((:0) S Rp(f: 0: Tp) + 20. (AF +
(51)
2mp
23

---

where AF.A is class of functions that take as imputs elements of the form (x, s) with æ E N and E S, and is defined follows:
AF := (2, ( {f(())))s))))))))))))))))))))))) ff
(52)
By Lemma with V, : f(x;) - (x))) 8;), and Lipschitzness (Lemma 7) we have:
(m(x) = F. Fur
sup /EF T=1
Σ
og
ce (pppp(((x))) (f())
mp
M
-VM Ey E. mp
sup
JEF ==
yEy
(53)
VMMM Ey Er
sup [e
ΣE
L
Σ yEy
cajy
(145))
Mmp
Rademacher complexity with Ad X Xmp instances.
3 RMMp (F)
Bound with cross-entropy Finally, from the inequality - logg(1 - t) 2 A >> O, we know that
Rp(S: Tp) Tp) Rp(s; $ Tp)
(54)
Putting the above inequalities together yields the proof of Theorem 2.
C Proofs for Section 4
C.1 On the bounded risk assumption
In Section 4, we introduced the bounded risk assumption. Recall that the assumption requires
constant R < 1, such that for each E [n] and each E Fi, (f) S R holds. Below, we discuss how this assumption is achieved with a small amount of directly labeled data {(x,, y:) y)) i.idd drawn from D.
Given Ti and trade-off parameter À consider the following combined learning objective:
A
Elf: Tp. TD)
Σ
e (f(2),))
Σ e ('I(((()))))
mp (m,s)ETP
mL (2.9)ETL
Suppose that there is a classifier fo E F that can achieve small empirical classification risk given by mi E(a.jeT 201 ([fo] (æ), ") Then, any classifier f1 with empirical classification risk greater than To + 1// will be rejected by this learning objective. This is because
E(fi: Tp, TL) 2 ro (r+t)) 1) = Aru + 12 Z( Tp, Tt)
Therefore, all the possibly learned classifiers must have an empirical risk less than ro + 1/A. Fur- thermore, under standard learning theory assumptions (e.g.. finite VC dimension vanishing Rademacher complexity). for any 6y E (0, 1) we can typically bound the expected classification risk with probability at least du by
B2 log(1/6))
ro + 1/A+ Biy
(55)
ML
where B1, B, is a constant depending on the learning problem. As long as we can have m, that is large enough make (55) less than (i.e., non- von-vacuous), we can guarantee that our assumption holds with probability at least Eg. The above justified the bounded risk assumption.
Under the realizable assumption, have that ro

---

C.2
Proofs
Below, we introduce the analog of Lemma for the multi-classifier case. Let
H. Fo = () 14o( siif F x.. XF.)
Given a training sample (æe, binary classifier from H.. predicts whether the labels pre- dictions for a are consistent with the partial label 8. Suppose (x:8) are drawn from Dp. Then, always the gold label of this binary classification problem. The zero-one binary classification enror of {(x,s) s) + (x)(((())) & s} equals the zero-one partial loss defined as eg (f(x),
Lemma 8. Let (Ft((F.)) = d(z.) < oo be the Natarajan dimension of each [Fi]. Then, we can bound the VC dimension of the function class H.F......
Σ (dia Log(oo d(z)) + 2d(z.1 loge;)
(56)
Proof. By Natarajan's lemma of multiclass classification, have:
2d -
(M 2dva
(57)
where C
[3.]. Taking the logarithm on both sides, we have
log 2 < Σ dpai log(M,d) + 2dpri log 4;
Rearranging the inequality yields:
d log 2 < a
Σ
dosi log(nM,d(z1)) + nod
d
+ 2d(Fa log
(d==) 2d( log logg;)= d
e
where the second step follows from the first-order Taylor series expansion of the logarithm function (M,( the point ned[z.. Using the fact that (log 2 1/e) yields (56), concluding the proof of Lemma 8.
Theorem (ERM learnability under multi-unambiguity), Assume that there is a constant Rt 1, such that for each E [n), each f E F; is zero-one risk R-bounded. Assume also that there exist positive integers M and c", such that M; S M* and e; S co hold for any E [n]. Then, if a is multi ualtii-unambiguuus. we have:
Ra (f) O((R (f:))))M
(f:o))
(8)
Furthermore, for any e, E (0, 1), there is universal constant Ca, such that with probability least 1 the empirical partial risk minimizer with Ro1 (f:o) has a classification risk R (f) if
ne
2M 2M
ne 202 2M-
log 1 (
(2))
mp 2 C3 e (1 RYM
Σ d1s
log
(9)
e (1 R)
25

---

Proof. Recall that c; = D) By the multi-unamie unlii-unambggutty assumption, we can lower bound the partial
label risk
(R" (fi))
Rp (J:0) 2 Σ
I - R (())*
(c 1))
Probubility
ar, misclassiiied other prediction correct.
(R (f:))*
II -R)M,
(ci(c - 1))
349
(calc: - 11) R-M
(R ([:)){
(58)
(R (ft)) Mr
(colco- 1)) 1)) (1 R) R) M-M-
M
(1 - 18) M.)
n
Σ R2I
(nco(co- 1))
Therefore, we have:
(ncolco- - 11
1/M
(f) -
Rp (f:
(1- R.
(nc2)
1/M"
(59)
RYM-M. Rp (fio)
-(RR (f:o))1/M²)
The above concludes the first part of Theorem 3.
To show the second part, from (59), we know that if the following holds:
M (1 R)M-M.
RS (fio)
(60)
M
holds. By the standard bound for sample complexity based on VC-dimension, we know that for any confidence parameter 8 E (0, 1), inequality (60) holds with probability no less than 1 8, if
then, (f) S
M" (1 R) M-M
mp 2 (H.,..nn
(61)
(nc))
where
C (CC(HL log
( + log
m 8,1)
(62)
and C' is universal constant. Combining (56) with (61) and (62), concludes the second part of Theorem 3.
O
Theorem 4 (Error bound under multi-unambiguity with multiple classifiers), Suppose a is multi- unambiguous and each ft is zerv-one risk R-bounded, for (0,1), 1). Then, for any integer k 2 and any 5 E (0, 1), with probability least 1 - 8, we have:
1/M
ROI(A) (5) <
nco
2M 2 2[k
Rb(f:a:T)) + VKM Σ
M, M, M. (F))
log 2mp
(1 R.M
Proof. Let
- (ziz) = (x)))))lleeleeeMM)....
-
be the vector that encodes all the probabilities that f assign to pair (æ, y) where is from and a possible label for æ. Similarly to the vingle-variable case, we define
(f())), = 1 WMC
V (9)
(f)(())) ff())
(63)
26

---

Bound with the partial risk. From the proof of Theorem 3, we know that
(nc2)M ( (1- R)M-M. R2 (f:o)
1/M"
(
Bound with the top-k loss. Similarly to the single-classifier case, it can be shown that
Rp of: (k: ():
Bound with the empirical risk. By standard Rademacher complexity bounds, given partially labeled dataset Tp of size mp, for each (0,1) and each f F, the following holds with probability at least 1 - 8:
1og(1/6)
Rf( Rp(f: + 28 (Hr)
(64)
2mp
where H.F is class of functions that take as input elements of the form (æ,, 8), with æ E x and S, and is defined follows:
2 == ( (0) ()
(65)
Denote FF = -
Fi. Using exactly the same argument in Lemma 7, we can show the mapping f(x) + (fx),,, is Lipschitz with Lipschitz constant vkM, By the contraction lemma (Lemma 6), have that
Wi
Rm (HF,,))
E.
sup
th op (f(())))
JEF
mi
Mr
kkM
ET Er,
sup
Σ
Σ (
mp
fEF
VE
S VkM
Mi
Ey E
mip
M
Σ
(66)
Mp
feF
VkM
MiR mp Mi (Fi)
.kM
M.R (Fi)
The above implies
log(1/8)
Ro(s:(pa) S (p: 2VKM MpP M, (Fi) +
(67)
2mp
Bound with cross-entropy. Finally, from the inequality - loggl - t) 2 t Vt O, we know that
Rp(S: ; P5: TP) Rp(s; Tp)
(68)
Putting the above inequalities together, the proof of Theorem follows.
D Proofs for Section
Theorem 5. IfG is unambigous and any f E F is r-bounded, then we have:
RD. (f) < O (M: as R (f: +
(10)
Furthermore, suppose [F] has finite Natarajan dimension dijj and the function class ((y s) + (o) # s)(o' E G} has a finite VC-dimension dg. Then, for any c, E (0. 1), there a universal constant C4 such that with probability least 1 8, the empirical partial risk minimizer with Rui (J;a) 0 has classification risk R1 (f) if
mp 2 C MMM (Idon) + do) log(6M (dir dg)) + d1dp log c) log
2M-2
22M-2
)))
1 (
+ log yM
27

---

Proof. Fix a classifier f E F. Since & is unambiguous, it follows that for each pair of labels (1, such that Ei, (f) > and each o' g, there exists vector y E (4, 1 such that d'yy) # aliik............ 4) holds. Therefore, we have:
min Rp (J:o') 2 e
E
min Bi (r), (.), ( OSkSM
2
Σ 4
ds EM,, (J)
M End,
(69)
M
E
22. -
Nittl
y.
R (F)
2M-
The above implies that R (f) O (f:o)UM) holds.
To prove the second part of Theorem 5, from the above discussion we know that R (f) < (c2M-2R0 (ff (f: MJ/M Therefore, if we could control R2 (f: E /c2M-2 we would have that Rol (f) I c. By the standard bound for sample complexity based on VC-dimension, then for any 5 E (0. 1), R2 (f:o) I My M.M /c2M-2 can happen with probability at least - 5 if
mp m(Hr,s, M M 2M)
(70)
where
m(H 6,1) C (VC(H) (t) + log (1)
(71)
and C' is a universal constant. Now, recall (21) from Lemma 3. Combining (21) with (70) and (71) yields the proof of the second part of Theorem 5,
E
Results for standard PLL
E.1
Counterexamples with transition matrices
Definition 12 (Transition matrix [8, 46]). A transition matrix T for learning problem with hidden label Y E y and observation S S a stochastic matrix dimension []] x [S], where the element in its 8hh column and jth row is the conditional probability P(S = j Y = i). Transition matrix T is
invertible it is left invertible, i.e., there is a matrix P of dimension | [8] such that PT 1
As shown in [8, 46], if the transition is invertible, then it is possible to construct an unbiased estimator for the classification loss using the samples of the partial label Therefore, the invertibility of the transition is desirable since it implies one can minimize the classification risk with partially labeled dataset alone.
transition matrix formulation for multi-instance PLL. Consider the multi innltiiinttance PLL with single classifier and deterministic transition a. Consider naive formulation of the transition matrix where we view yI as the label space. Then, there are two different label assignments + y' such that o (yy) # oyy'), their corresponding column vectors in T will be the same, resulting in non-invertible transition. For example, in the MNIST with SUM2 problem, the column vectors corresponding to the label pairs (0, 1) and (1, 0) will be:
(1,2)
(2, 1)
0
0
s = 1
1
s 2
0
(72)
8= 18
0
This fact implies that the transition must be injective to ensure invertibility, which is too strong for the partial labels in practice.
28

---

To overcome this issue, we consider an alternative formulation, where we view randomized partial label for each the M instances, where the randomness comes from the distribution of the other instances. Suppose the marginal distribution of Y is known (or can be estimated in some ways). Then, we construct a transition matrix Tx for each [M] by defining its 7hh column and jth row to be (s =|y; i) = ( (v) Us i). For example, the transition matrices for the MNIST with 2sum problem are
0
0
PP 0)
0
0
=
P(Y = 1)
P(Y = 0) PPY
8 2
P(Y 2)
= T2
= 9
P(Y = 9)
P(Y = 8)
P(Y = 0)
(73)
10
0
P(Y 9)
P(Y
=
0
P(Y = 2)
:
18
0
P(Y 9) 9)
We say the standard PLL problem invertible if there exists an l E [M] such that Tg left invertible.
M-unambiguity A invertibility for multi-instance PLL. Consider the following example, where M-unambiguity holds but the transition matrix is not invertible for no input position. Consider
y = [3] and M Assume (1, + o(2, * (3, 3) so that a is Muunambiguous, Now, suppose
= -2,211 = 0(2,2 (2,,3,3) o3.1,33 = 23, (33),11
(74)
and
(1,,12) o(1,211) = ((13,3)
o(2,1,3) o(22.2) (22,,11)
(75)
(3,1,1) = (3,2,3) = (3,3,22
and
= c(1,,2) d(1,3,1)
- a(2,3,2)
(76)
03. o3, 2, 033,3,3)
so that S = {o(1, 1, 1), (2, 2, 2),2)..o (3, 3. Suppose that IP = 1) = P(Y = 2) = P(Y
3) 1/3. Then, can be verified that
2
(1,1,11
1/3
1/3
1/37
Ti = T2 T3
(2,2,2)
1/3
1/3
1/3
(77)
(3,3,3)
1/3
1/3
1/3
This means that all the transition matrices are non non-invertible.
Inveritbility A M-unambiguity for multi-instance PLL. Suppose y [2] and o (2)
1 U2 Then M -uunambiguity does not hold since o11, 1) (2, 2). But if P = 11=1-PC 2), then
0
00.9
0.1
T =
(78)
0.1
0.9
an invertible transition.
29

---

E.2
Counterexamples for standard PLL
We show that for the standard PLL, the small ambiguity degree condition [28] and the invertibility of the transition matrix, see Definition 12, do not imply each other. Below, we recapitulate the small ambiguity degree condition.
Definition 13 (Ambiguity degree (28]). The ambiguity degree for standard PLL is defined as
sup PP ((aa)-(( Ed())
(79)
D(2.))
where D(x,V y) is the density function at (r,y). We say that PLL instance satisfies the small ambiguity degree condition, 7 < 1.
Small ambiguity A invertibility, Consider the following transition matrix (where all blank elements zero) with )' = [5] and S = 2
1
3
4
5
(1. 2, 3)
1/2
1/2
1/2
(1.4.5)
1/2
1/2
1/2
T =
(80)
(2.5)
1/2
1/2
(3.4]
1/2
1/2
can be verified that the small ambiguity degree is 1/2 but this matrix is of rank < 5 and the invertibility condition does not hold.
Invertibility ه small ambiguity. Consider the following transition matrix with y [2] and S 2>:
T {1] 1 07
(81)
(1, 0 1
We can see that the small ambiguity degree is but the above matrix of full rank.
E.3
M-ambiguity and small ambiguity
We show that proposed M-unambiguity, see Definition I, is extension of the small ambiguity degree, see Definition 13. To this, we consider a generalized setting, where & randomized function of y. In particular, similarly to standard PLL (aka superset learning problem) [28, 8), we define be random function y + 23 so that 2 is random set of vectors in y.M Below, let DM be a distribution followed by M i.i.d. random variables (X,, Yi), where (X;, Y.) ~ D,
for each E [M]. We use DMM (x, y) denote the density at (æx, y). for XM and y E y Definition 14 (M-Am Ambiiuityyyy degree). The ambiguity degree for standard PLL subject to DM is given by
sup
P P(a (1/ E
(82)
(2.2)))00. are dingonal with yuyy We say that PLL instance satisfies the small M -ambiguutty degree condition, if 1.
Firstly, it can be seen that the M-ambiguity degree, Definition 14, reduces to the ambiguity degree from Definition 13 when M = 1, since all label vectors are diagonal in that case. Below, we show that the small M- M-ambiguity degree condition guarantees learnability.
Proposition 2. If the small M-ambiguity degree condition is satisfied, then we have:
RDI S 1 -- (c2M 22 (f:o))
(83)
Proof. Let E be the event that for input vector X with gold labels y. there exists diagonal vector y' E y:M with y' * such that y' E Then, by definition, we have P(E) S 7. Also,
( conditioned on E, from the proof of Lemma 1, we know that R$1 (f) Z Tale-1))-- The above implies that
M Rdl 2 (1- (e(c- - 1)
(84)
30

---

Therefore, we have:
(f) (R (f:o)(e) 1/M
(J) 1M
1- P(E)
1-y
concluding the proof of Proposition 2.
The special case of Proposition 2, where M- = recovers the classical result for standard PLL (see the discussion at the end of Section 3 in [28]). The partial risk Rp (J:o)) can be further bounded by its empirical counterpart, assuming that the Natarajan dimension is finite, as we have previously shown.
F Related Work
Partial Label Learning. Partial label learning (aka superset learning) assumes the learner receives the training data in the form of (x, 2). where 2 E 2 is a subset of the label space that contains the gold label. Technically, is technically possible to cast our problem to standard PLL by identifying s as its preimages, namely the set of all labels that is consistent with the observation s. Nevertheless, our work extends the standard PLL two ways. Firstly, our framework allows multiple instances to appear in training sample. Secondly, the Icarnability of PLL is typically shown under the small ambiguity assumption, see, for example, [11, 28, 5]. This condition requires no distracting label to be contained in with probability 1, which is violated in case since a distracting label can always occur because a is deterministic. Therefore, our proposed conditions relax and generalize small ambiguity by allowing deterministic transitions, see Appendix E.3.
Another line of work in weak supervision exploits the transition matrices [46] to compute posterior class probabilities in different scenarios, e.g., PLL [8, 9] and noisy label learning [61]. The key as- sumption is that the transition matrix is invertible [8, 46). Our learnability condition, M M-unambiguity, and the invertibility condition do not imply each other, see Appendix E. and E.2 for a self-contained discussion. There, we also show that small ambiguity and the invertibility condition do not imply each other, which might be of independent interest.
Latent structure models. Our work also relates to latent structural learning, where the aim is to learn latent representation using supervision on a deterministic transition over the latent variables [45, 52]. To reduce the cost of computing a, [42] proposes approximations for a restricted class of decomposable transitions. Both [42, 35] assume latent models in the exponential family. Our work is also related to SPIGOT [34, 32]. There, the aim is to learn both the transition and the latent model, proposing techniques for back-propagating through the argmax layer of the latent model. Complementary to the above research, we focus on rigorous theoretical analysis.
Our work is closely related to [62], which studies a similar problem of weakly supervised learning with multiple instances. However, our results are stronger and closer the aims of weak supervision in comparison to the results in [62]. This is because our work proposes sufficient and necessary conditions to recover the hidden labels (i.e., Zı.K in [62]), while consistency [62] concerns the likelihood of the observed labels rather than the hidden ones, as defined in Definition 3 and 4 of [62], where two parameters are equivalent if they have the same likelihood on the observed partial label (rather than the hidden labels). Also, we use different surrogate loss based on semantic loss that allows a top-k approximation. In general, semantic loss is designed to capture Boolean constraints over the hidden labels and is standard to use in neuro-symbolic learning. Furthermore, our work directly extends the theory of PLL, which is thoroughly discussed in Appendix. In particular, our learnability condition from Definition I directly extends the classical small ambiguity degree condition, as shown in Appendix E.3. In contrast, the connection to PLL is missing from [62].
Constrained learning. The problem of partial label learning is closely related to constrained learning, in the sense that the prediction for the label (vector) is subject to the constraint (gy) = s at the training stage. Training classifiers under constraints has been well studied in NLP. The work in [36] proposes a formulation for training under linear constraints; [37] proposes a learning framework that unifies expectation maximization with integer linear programming. Posterior regularization has been proposed for training classifiers under graphical models [21]. The latter two lines of research were adopted by [27] and [23] for neurosymbolic learning.
31

---

Neurosymbolic learning. Our work was motivated by frameworks that employ logic for training neural models [30, 53, 13, 59, 43. 31, 24, 27]. We prove learnability under (unknown) transitions that capture different languages: systems of Boolean formulas, non-linear constraints and logical theories. Notice that the key to model logical theories, e.g. Datalog, via a through abduction [26], see [43, 13] for a discussion. We also prove error bounds under a common neurosymbolic loss, the SL [56], and top-k approximations. We are the first to provide rigorous results on neurosymbolic learning, closing gap in the literature.
Notice that [58] also proves consistency of a top-k loss. However, they use a zero-one-styles loss. Finally, [3] provides generalization bounds of the smart predict-then-optime
(SPO) loss [15]; it assumes, though, that the gold labels of the inputs are given. Complementary to our research the work in [19, 47, 33] that aims to integrate combinatorial solvers as differentiable layers in deep neural models. Finally, [48] proposes techniques for learning to solve combinatorial optimization problems using end-to-end neural models-loosing the ability to extract the latent models.
subtle, yet substantial, difference between standard PLL and multi-instance PLL is that populating may incur a substantial computational overhead in the latter case. For instance, let us return back to Example 1. To populate the entries of for each target sum s, we need compute all solutions of the equation X + Y s, where X, Y E .0, 9}. In contrast, the set of labels associated with each input instance is part of the input [28, 11].
Learning logical theories. Another relevant strand of research is that of learning logical theories [12, 16, 38). The work in [12] mixes abduction with induction to jointly learn theory while training the neural classifiers, while [16] introduces a differentiable formulation of inductive logic programming that relies the semantics of fuzzy logic for interpreting formulas. Finally, the authors in [38] propose learning rules using the notion of logical neural networks. The techniques in [12, 16, 38] rely on templates for learning logical theories. Instead of relying on pre-specified templates, the authors in [18] aim to learn those templates by mining patterns (aka motifs) from the data, following mathematically rigorous techniques and providing formal guarantees related the mined motifs. Differently from our work, the above line of research provides no guarantees in terms of learnability or error bounds.
G Experiment Details
Firstly, recall that in all neurosymbolic frameworks considered in Section 6, we considered weights in {I....,5) 5) and used an additional neural classifier to learn the unknown weights. As the weights are fixed, the inputs to the weight classifiers in all frameworks are constant signals, i.e., in each iteration, we provided the classifier with the same signal W, for the i-th weight. For each neurosymbolic framework, our implementation built upon the sources made available by the authors.
We now provide information about DogpProbLog NeurASP and NeuroLog. Listings 1, and show the logic programs used to train the MNIST digit classifiers under the above three frameworks using the WEIGHTED-SUL problem, see Section 6.
DeepProbLog and NeurASP link the classifiers' predictions with the logic program via neural predicates. WEIGHTED-SUM requires two neural predicates: digit and weight. The first one classifies the input MNIST digits into (O...., 9). while the second one classifies the input weights into (1, (1....,5, 5). In NeuroLog, the association between the classifiers' predictions and the logic program is maintained via abducible predicates. In particular, the instances of those predicates associate the probabilistic predictions with the facts from the domain of the logic program. Listing uses two abducible predicates: atdigit and atweight. Atom atdigit( s) denotes that the j-th input to the digit classifier maps to value s. The abducible atom atweight( (8, j) is analogously defined.
In terms of heuristics, in DeepProbLogg, we used the Geometric Mean [31].
Following ENT's official implementation, we encoded WEIGHTED-SUMN solver. In addition, similarly to the handwritten formula evaluation scenario in [27] (Section 5.1 from [27]), we used two projection operators. To generate the initial random labels, we projected out all the digit labels and kept only the weight labels. During random walks, we projected out the second
using the Z3 SMT
In NeurASP. we used weights in (1.... 10). since due to bug in the most recent NeurASP implementation that was provided by the authors, the output domains of all classifiers should be of the same size.
32

---

input digit's ss labels, keeping the labels of the first digit and the labels of both imput weights. The rest of the hyperparameters, as well as the two-stage training process, were set as the hand-written formula evaluation scenario from [27].
follows: Conv2d( 6, 5), MaxPool2d(2, 2), ReLU(True), Conv2d(6, 16, 5), MaxPool2d(2., 2), ReLU(True), Linear(16 4, 120), ReLU(), Linear( 120, 84), ReLU(), Linear(84, N), Softmax( 1)..
Neural architectures. The layers of the MNIST digit classifier
The neural classifiers for frameworks but ABL were built using PyTorch 2.0.0 and Python 3,9. For ABL, we aligned with the implementation provided by the authors and used Tensorflow 2.11.0 and Keras 2.11.0. For each framework, we used the hyperparameters proposed by the authors in analogous scenarios.
nn (mmist_meet net, [X], Y, 0,,,,,,,,,,,,,,6,,,,888 un (weeight_net, net, [X] (1,2,3,4,51) :: weight(X,X)
:: dxgit(x,
weighted_sum2((1 (I1, I2, w1, w2, S) digit (I1, (Ig, weight (W1,A1), digit (I2,D2), D2), weight AN2, is A1-D1-
veighted_sum30 I2, I3, W1, W2, W3, digit(II,DD) weight veight(W1,A1), A1), (I2, Weight(W2,43 digit(13 D3), (W3, is A1-D1-A2-D2-A3+-3,
Brighted_sum4(Ce I2, I3, I4, W1, W2, W3, W4,8) :- (Ig,t(I weight(W1,At)
digit(I2,D2) (I2,D2), (e2, digit (I3, (I3,D3), (Wight(83,A3) digit (I4,D4), weight (44, S is A1901-42-DD--8--33444000
Listing 1: DeepProbl.og program for the WEIGHTED-SSUM problem.
(digit((1, 6,,,,,,,,,5,6,,,88,,, an (1,)) [1,2,3,466) :- wei (X).
:- img (X).
img(i1). im2) img (i3) img(i4). wei(o)). (o2). wei (o3). wei(
veighted_sum2 Xx, X3,,3,,44,5 :- digit X1, ,N1,, weight (0, x3, W1), (0,,,),,), weight (0,X4,W2) S-W1-N1-WW-NN2
veighted_sumäs
:-
weight X4, W1), veight(0,X5, W2), 9=#11:81-92-N2-433-M
(0,it(
(o, X3,,3,,, N3), weight W3),
weighted_sund (X1, X2,3,,,,,,3,,,X, X6, X7, S) X1),
weight veight(0,X5 (0, beight(O,XX) W2),
(igit(0,X2,N2))
(0,,3,,,,,,
weight (0, X7, W3),
weight (0, X8, W4), 5-#11-811422222-433333----1
(0,
Listing 2: NeurASP program for the WEIGHTED-SUM problem.
33

---

bbduciibleattdiiitt.......
abducible abducible (atweight (_,_)).
dI) :- in ...9. weight
N in 1..5.
srighttedsum2(S)
(D1) (D1,
(D2) (02,
weight(S1), (ti,ight(S1,1),
weight atweight (S2,
(D1 S1) (D2 S2)
weighted_sum3(9 (S)
digit(D)), atdigit (Di
digit(D2),
atdigit (D2,2),
digit(D3).
atdigit (D3, weight
(S1,,),, atweight ($2,2),
weight (S2).
weight (S3). atweight(S3, (S3,3),
(D1 S1) (D2 S2)
(D3 S3).
weighted_sung (S)
atdigit(D1,) digit(D1),
digit(D2),
atdigit(02,2), (D2,2),
digit(D3),
atdigit at3)git(03,3), (D3,3),
digit(D4),
atdigit atdigit(D4,4), (D4,4),
weight
181,
weight (S2).
atweight (S2,2),
weight (S3). Stweigh((3,,55
weight (S4), atweight (84,4)
(D1 S1) (D2 S2)
(D3
S3)
(D4 S4).
Listing 3: NeuroLog program for the WEIGHTED SUM problem.
34


Reviews:
[{"review_id": "JWGtJ5vSFt", "reviewer": "Reviewer_a7AK", "summary": "The paper connects latent structural learning and neuro-symbolic integration and provides the first theoretical study of multi-instance PLL with possibly an unknown transition. Under such weakly supervision scenario where the transition is deterministic, it defines the necessary and sufficient condition, the minimal distribution assumptions, for the ERM-learnability of the problem. They also derive the Rademacher-style error bounds using the top-k semantics loss. The empirical results support their theory.\n", "questions": "1. The scalability in this scenario is poor as Table 2, and it seems to be worse than the error bound given by the theory. Will this happen for the known transition function case? What may be the possible reasons?\n", "limitations": "The author mentions that scalability may be an important issue. No further negative societal impact raises.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The study provides the first theoretical analysis of multi-instance PLL with possibly an unknown transition, which is a significant contribution to the learning theory community. \n2. The theory holds for both known and unknown transition cases, and the assumptions are necessary and sufficient. The experiment results also support the learnability of classifiers and the conclusion that when $M$ gets larger, the learning process gets harder.", "weaknesses": "1. The author better move some discussion of the necessity to let the transition function be deterministic to the introduction part to prevent confusion since it seems too strict compared with the commonly used assumption.\n2. The empirical results are monotone for the weighted sum transition function, and the authors should add some other empirical results for more known transition function cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q: The author better move some discussion of the necessity to let the transition function be deterministic to the introduction part to prevent confusion since it seems too strict compared with the commonly used assumption.\n\nWe mainly focus on deterministic transitions, since our work was motivated by neuro-symbolic learning and NLP. Notice that while looking more restrictive, learning under deterministic transitions is actually more challenging, as prior learnability assumptions [4,9,26] do not further apply. We believe it is not difficult to extend our results to randomized transitions. In fact, in Appendix E.3, we present such an extension to randomized transitions when $M=1$. We will follow the suggestion to add a relevant discussion in the introduction.\n\n> Q: The empirical results are monotone for the weighted sum transition function, and the authors should add some other empirical results for more known transition function cases.\n\nOur aim was to offer a rigorous theoretical analysis of multi-instance PLL. Hence, we would like to kindly point the reviewer to prior art that presents results for learning under known transitions, e.g., NLog [41], NASP [53] and Scallop [22], that offer a more in-depth empirical analysis. For instance, [41] presents results on learning the pieces of a chessboard via supervision on the status of the kings; [53] presents results on learning an MNIST classifier using valid SUDOKU boards; and [22] presents results on visual question answering using multi-instance partial labels. \n\nNevertheless, to contrast learning under known vs learning under unknown transitions, we have added new results for a variant of the WEIGHTED-SUM scenario that assumes known weights. Please see the **Updates on the empirical analysis** section at the top of our general rebuttal.\n\n> Q: The scalability in this scenario is poor as Table 2, and it seems to be worse than the error bound given by the theory. Will this happen for the known transition function case? What may be the possible reasons?\n\nFor known transitions, there is still the issue of scalability as already pointed out by prior art. However, it will be milder, as it requires learning fewer parameters. Please check the section **Updates on the empirical analysis** at the top to see our new results on learning with known weights.  \n\nThe scalability issue is caused both by the problem itself (see our discussion at top general rebuttal about WEIGTHED-SUM) and the limitations of the current neuro-symbolic methods. For instance, Scallop [22] adopts more sophisticated grounding techniques and approximations that allow it to scale to larger scenarios than DLog. Please also check the section **Comments on scalability and accuracy** in our general rebuttal above for a detailed explanation. \n\n> Q: No further negative societal impact raises.\n\nThanks for pointing out this. We will add a discussion on broader impacts in the revised version."}, {"review_id": "XKbg8xjSK3", "reviewer": "Reviewer_6VmD", "summary": "This paper studies a weakly supervised learning scenario where supervision signals are given to sets of instances (instead of individual instances), while the goal is still to predict labels of unseen individuals. For example, the learner is provided with a dataset in which each training example comprises a set of instances $(x_1, x_2)$ (for which the gold labels $y_1 = 1$ and $y_2 = 2$ are unobservable) and an aggregate signal $s=3$ (which is calculated by a known function $s=\\sigma(y_1,y_2)=y_1 + y_2$).\n\nThe authors present learnability results for this scenario under certain assumptions. One main result is that if the function $\\sigma$ has *M-unambiguity*, a perfect classifier can be learned as the number of training data approaches infinity. The authors further extend the results to situations where the function $\\sigma$ is unknown.", "questions": "- Is the expected log-likelihood discussed in [1] equivalent to the semantic loss (or the top-k surrogate loss) examined in this submission?\n\n- Could you provide a clearer explanation for the proof of Lemma 1, particularly regarding the first inequality in Equation (26)?  Could you also elaborate on the first inequality in Equation (32) in the proof of Lemma 4? Is it correct to state that the proofs of these lemmas solely rely on the M-unambiguous condition?", "limitations": "The limitation of the submission is that it relies on assumptions and conditions, such as a concentration of mass on a single instance or label, which may not align with realistic data distributions and weaken the applicability and persuasiveness of the results.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- This paper concerns an important problem setting called *multi-instance Partial Label Learning* (multi-instance PLL), which is an extension of the standard Partial Label Learning (PLL) problem.\n- The authors introduce the notion of \"M-unambiguity\" and show its utility in proving the learnability of the considered problem scenario under specific assumptions.\n- The authors further propose the notions of \"multi-unambiguity\" and \"unambiguous transition space\" to tackle the scenarios of learning multiple classifiers and unknown transition functions.", "weaknesses": "- The theoretical results presented in this submission have limited significance. Generally, learnability means that a hypothesis class is learnable under any data distribution. However, the authors state that they prove learnability under distributions that concentrate mass on a single instance or label. This assumption can be invalidated in the real world. This submission primarily considers a “toughest\" distribution that concentrates mass on a single instance, implying all the instances in the training data are the same. Such a distribution is unrealistic in real-world applications. Consequently, positive results under this assumption are not so meaningful. The authors may need to explore more realistic data distributions.\n\n- Theoretical aspects of the problem setting, which is called multi-instance Partial Label Learning in this submission, have previously been examined in the literature of weakly supervised learning, as seen in [1]. This setting is known as *learning from aggregate observations*. In [1], the consistency of learners is investigated, and the expected log-likelihood in [1] is close to the semantic loss studied in this submission. To avoid confusion and potential overlap, it is essential for the authors to discuss and elucidate the distinctions between these studies.\n\n- The terminology \"Multi-Instance Partial-Label Learning\" has been used in prior research, such as in [2]. Although [2] examines a different problem setting than this paper, to avoid confusion, it would be beneficial for the authors to adopt a distinct term when referring to the problem setting considered in this submission.\n\n- The proof of Lemma 1 appears to be convoluted. Specifically, the first inequality in Equation (26) warrants further clarification. It is not immediately evident why the assertion $R_{P}^{01}(f;\\sigma) \\ge \\sum_{l_i\\neq l_j} E_{l_i,l_j}(f)^M$ holds true. In a similar vein, could you explain the first inequality of Eq. (32) in the proof of Lemma 4? Do these Lemma rely only on the M-unambiguous condition?\n\n\n\n[1] Zhang, Y., Charoenphakdee, N., Wu, Z., & Sugiyama, M. (2020). Learning from aggregate observations. Advances in Neural Information Processing Systems, 33, 7993-8005. \n\n[2] Tang, W., Zhang, W., & Zhang, M. L. (2022). Multi-instance partial-label learning: Towards exploiting dual inexact supervision. arXiv preprint arXiv:2212.08997.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q: The theoretical results presented in this submission have limited significance. The authors state that they prove learnability under distributions that concentrate mass on a single instance or label. This assumption can be invalidated in the real world. ... Consequently, positive results under this assumption are not so meaningful. The authors may need to explore more realistic data distributions.\n\nWe kindly point out that there seems to be a misunderstanding about our results. Our ambiguity conditions in Definitions 1, 4 and 5 *do* apply to any probability distribution, i.e., if these ambiguity conditions are met, then we can learn under any distribution of the training data. The only reason we mentioned concentrated distributions is to prove that the proposed conditions are necessary (instead of just being sufficient). To put it differently, we show learnability under the toughest distributions in order to ensure learnability under any distribution. Such an approach of considering though cases is commonly adopted in PLL and general ML theory, e.g., in the classical theoretical PLL theory [26]. The reviewer can also check the definition of learnability in the last paragraph before Section 3.1. We apologize for any confusion caused and will improve our presentation to emphasize the generality of our results.\n\nPractically, deriving general learning conditions from the concentrated distributions is still meaningful. It shows that if the real-world data is not balanced but close to being concentrated on very few instances/classes, then PLL can be more difficult. Furthermore, we would like to note that our conditions are satisfied by many neuro-symbolic tasks, as discussed in Examples 2 & 3.\n\n> Q: Theoretical aspects of the problem setting have previously been examined in the literature, as seen in [1]. This setting is known as learning from aggregate observations. In [1], the consistency of learners is investigated, and the log-likelihood in [1] is close to the semantic loss studied in this submission.\n\nThanks for pointing out [1]. We agree that the learning scenario is similar, yet our contributions remain valid. Our differences with [1] are shortly summarized below:\n\n- Our results are stronger and closer to the aims of weak supervision in comparison to the results in [1]. This is because our work proposes sufficient and necessary conditions to recover the hidden labels (i.e., $Z_{1:K}$ in [1]), while consistency in [1] concerns the likelihood of the observed labels rather than the hidden ones: as defined in Definition 3 & 4 of [1], where two parameters are equivalent if they have the same likelihood on the observed partial label (rather than the hidden labels).\n- The surrogate losses are different. The log-likelihood loss in [1] is different from the semantic loss in Section 3.2 of our paper. Furthermore, we allow a top-k approximation for the surrogate loss, see Section 3.2. The difference is further explained in a separate response below.\n- Our work directly extends the theory of PLL, which is thoroughly discussed in Appendix E through F. In particular, our learnability condition from Definition 1 directly extends the classical small ambiguity degree condition, as shown in Appendix E.3. In contrast, the connection to PLL is missing from [1].\n\nWe will follow the suggestion to include a comparison to [1] in our revision. \n\n> Q: The terminology \"Multi-Instance Partial-Label Learning\" has been used in prior research, such as in [2]. \n\nThanks for pointing it out. We will consider a better name to reduce ambiguity.\n\n> Q: Is the expected log-likelihood discussed in [1] equivalent to the semantic loss (or the top-k loss) examined in this submission?\n\nNo, they are different losses. To illustrate, consider Example 9 in our submission, where the induced Boolean formula is $\\varphi = \\{(A_{1,2} \\wedge A_{2,0}) \\vee (A_{1,0} \\wedge A_{2,2})\\}$ (recall that $A_{i,j}$ is a Boolean variable that is true iff the $i$-th input digit has label $j$). The negative log-likelihood in [1] is the sum of the probability of the two label vectors, i.e., \n$-\\log(w(A_{1,2}) \\times w(A_{2,0}) + w(A_{1,0}) \\times w(A_{2,2}))$, where $w(\\cdot)$ denotes the confidence of the neural classifier for the corresponding prediction. However, the semantic loss is given by $-\\log(1 – (1 - w(A_{1,2}) \\times w(A_{2,0})) \\times (1 - w(A_{1,0}) \\times w(A_{2,2})))$, i.e., the sum of the right column of Table 3. \n\nIn general, semantic loss is designed to capture Boolean constraints over the hidden labels and is standard to use in neuro-symbolic learning. Notice also that our work additionally allows a top-$k$ approximation of the semantic loss, as opposed to [1] which only considers the exact likelihood.\n\n> Q: Could you provide a clearer explanation for the proof of Lemma 1, particularly regarding the first inequality in Equation (26)? Could you also elaborate on the first inequality in Equation (32) in the proof of Lemma 4? Is it correct to state that the proofs of these lemmas solely rely on the M-unambiguous condition?\n\nThe first inequality in (26): By $M$-unambiguity, we know that if all the $M$ input instances have the same label and are wrongly classified as another label, then the predicted partial label will be wrong. Therefore, the zero-one partial risk is lower bounded by the probability of such events, namely the sum of the same type of classification mistake being repeated by $M$ times.\n\nThe first inequality in (32): Similarly, by $I$-unambiguity, we know that if $I$ input instances in $\\mathcal{I}$ have the same label and are wrongly classified as another label while all the remaining $M-I$ instances are correctly classified, then the predicted partial label will be wrong. Therefore, the zero-one partial risk is lower bounded by the RHS, which computes the probability of such events.\n\nYes, it is correct to say that the proof of these lemmas solely relies on the $M$-unambiguity and/or $I$-unambiguity."}, {"review_id": "RtCezzTpW5", "reviewer": "Reviewer_vhBR", "summary": "This paper studies the questions of learnability and generalization under an interesting form of supervision feedback: namely, when the true label of interest is not observed, but the learner instead has access to the output of a \"transition function\" $\\sigma(y_1, \\ldots, y_M)$ computed on the labels of an $M$-tuple of examples.\nThe paper gives necessary and sufficient conditions on the transition function for learnability from two \"partial\" (evaluated on the aggregate/partial labels) loss functions: partial 0/1 loss and a surrogate for the \"semantic loss\" studied in other related literature. These results are extended in multiple directions and various details such as convergence rates are also derived.\n", "questions": "In the Remark starting at L172 the authors suggest a possible connection between the perturbation stability of the transition function and learnability / convergence rate. Could this be connected in any way to the algorithmic stability results (e.g., Bousquet and Ellisseef)? Such a connection might lead to better convergence rates?\n\n- Am I correct that the PAC failiure probabilities $\\delta$ are w.r.t. the sampling of $\\mathcal{D}_P$ (not $\\mathcal{D}$)? It might be good to clarify this.\n\nA few questions I had while reading the intro/setup, some of which were cleared up later by the main text, but suggest that clarity/flow could be improved:\n\nL117 Learnability. What is a \"partial learning algorithm\"?\n\nL138 should be $\\sigma_(y,\\ldots,y) \\ne \\sigma(y',\\ldots,y')$ ?\n\nL182 why do we need to \"populate $\\sigma$\" to compute the zero-one loss? I don't fully follow. In the sum-M case, can't we just sum the outputs predicted by $f(x_i)$ and then compare to $s$? Or is the point that this is problematic if we wanted to use a *surrogate loss* such as cross entropy, so we'd need to form a distribution over the image of $\\sigma$?\n", "limitations": "The authors describe one of the main limitations of their work (the somewhat strict assumptions required on the transition function $\\sigma$ due to the worst-case distributions they consider). However, the discussion could be expanded to mention broader limitations, such as the current lack of practical insights to glean from the theoretical results.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The results are well presented and the key condition (M-unambiguity) is shown in Appendix E.3 to be a natural extention of the \"small ambiguity degree\" assumption from Partial Label Learning (PLL) literature.\n\n- The authors connect the convergence rate (in terms of sample complexity) of learning to the degree of unambiguity of the transition function.\n\n- The results provide a theoretical basis for learning with the top-$k$ approximate _semantic loss_, which was introduced by other work.\n\n- The core results are extended in multiple directions, including to the case where there are multiple different classifiers and to the case where the transition function is unknown (under additional assumptions).\n\n- Studies and provides a nice set of learnability results for an interesting case of weak supervision that could be practically relevant.\n\n", "weaknesses": "- Core technical contributions / difficulties are not explained enough (e.g., Lemma 1 seems like key result for Thm 1, and the rest follows from standard tools?) What was the key technical challenge to proving the generalization results, and why is it novel / original?\n\n- It's not clear what practical insights are gained from the results. The experiments section seems like a proof of concept---no new method other than the \"baselines\" is proposed or evaluated based on the theory. The main insight seems to be the qualitative relationship between $M$ and the bound, but $M$ is not really a controllable parameter in practice.\n\n- Related to the previous point about the experiments, this setup is missing a compelling application. What's a more realistic practical scenario where learning from this type of supervision is relevant? I.e., where observing $s$ for an $M$-tuple of examples is much more practical than observing $y$ for each example?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q: Core technical contributions / difficulties are not explained enough (e.g., Lemma 1 seems like key result for Thm 1, and the rest follows from standard tools?) What was the key technical challenge to proving the generalization results, and why is it novel / original?\n\nThanks for the comment. We will clarify the above in the revision of our work. Below, we provide some clarifications.  \n\nTheorem 1 builds upon several non-trivial and original intermediate results that must be shown before applying the standard VC theory:\n- For empirical error: A lower bound of the classification risk (Lemma 1).\n- For generalization error: A bound of the VC dimension for the multi-instance partial label predictor (Lemma 3).\n- Counterexamples for arguing the necessity of our proposed learning condition (last paragraph of the proof of Theorem 1).\n\nThe proof of Theorem 2 is more involved: it relies on a variant of the Rademacher complexity from [3] and the following original results:\n- Lemma 1.\n- An inequality that bounds the top-k loss with the zero-one loss (Lemma 5), which requires the construction of an intermediate l1 loss (Definition 11).\n- Lipschtness of the semantic loss (Lemma 7). That result is further combined with a contraction lemma from [8] (Lemma 6) to bound the Rademacher complexity of the model.\n\n> Q: It's not clear what practical insights are gained from the results. The experiments section seems like a proof of concept---no new method other than the \"baselines\" is proposed or evaluated based on the theory. The main insight seems to be the qualitative relationship between M and the bound, but M is not really a controllable parameter in practice.\n\nIndeed, our work does not aim to propose new algorithms. Instead, it focuses on theoretically analyzing existing methods. However, the practical insights do not limit to the qualitative relationship with $M$. The main takeaways of our bounds for practitioners also include the following:\n- The learning difficulty (rate of convergence) is characterized by the “ambiguity degree” of the transition $\\sigma$ (i.e., if the transition is $M$-/$I$-unambiguous), which can be determined without training. (Theorem 1 and Proposition 1).\n- The impact of choosing the approximation strength $k$ is not always monotone. In general, the choice leads to a tradeoff between approximation error and estimation error (Theorem 2).\n\n> Q: Related to the previous point about the experiments, this setup is missing a compelling application. What's a more realistic practical scenario where learning from this type of supervision is relevant? I.e., where observing s for an M-tuple of examples is much more practical than observing y for each example?\n\nA compelling application of our formulation is visual question answering [22], where the observation $s$ (answer) is a function of multiple hidden variables $y$ (object types and their relations). The partially labeled data $(x,s)$ is used to train a classifier for learning the mapping $x \\mapsto y$. The work in [22] shows that models trained via multi-instance PLL achieve better accuracy than state-of-the-art neural end-to-end architectures. \n\nLearning latent structures from downstream observations is also of great interest in NLP [AdditionalRef1] (e.g., learning semantic parsers from sentiment classification tasks), since it has been shown to achieve better model accuracy while offering interpretability. Please also check the section **importance of multi-instance PLL** in our general rebuttal above for further comments. \n\n> Q: In the Remark starting at L172 the authors suggest a possible connection between the perturbation stability of the transition function and learnability / convergence rate. Could this be connected in any way to the algorithmic stability results (e.g., Bousquet and Ellisseef)? Such a connection might lead to better convergence rates? \n\nThanks for pointing this out. We agree that there could be deeper connections between these two types of instabilities. Intuitively, a more stable transition will lead to a more stable partial loss and a more stable PLL algorithm. We will explore this direction in future versions of our work.\n\n> Q: Am I correct that the PAC failure probabilities $\\delta$ are w.r.t. the sampling of $\\mathcal{D}_P$ (not $\\mathcal{D}$)? It might be good to clarify this.\n\nYes, it is correct. We will clarify this in the revised version.\n\n> Q: L117: Learnability. What is a \"partial learning algorithm\"?\n\nA partial learning algorithm is one that takes the partially labeled data $\\mathcal{T}_P$ as input and outputs a classifier in $\\mathcal{F}$. We will improve the writing to make this definition clear.\n\n> Q: L138: should be $\\sigma(y,\\dots,y) \\ne \\sigma(y’,\\dots,y’)$\n\nIt’s a typo, thanks for pointing it out.\n\n> Q: L182: why do we need to \"populate $\\sigma$\" to compute the zero-one loss? I don't fully follow. In the sum-M case, can't we just sum the outputs predicted by $f(x_i)$ and then compare to $s$? Or is the point that this is problematic if we wanted to use a surrogate loss such as cross entropy, so we'd need to form a distribution over the image of $\\sigma$?\n\nIs the latter. Populating $\\sigma$ is required only when computing the surrogate loss in Section 3.2. We will improve the presentation to make it clearer from the context.\n\n---\n\n- [AdditionalRef1] Backpropagating through Structured Argmax using a SPIGOT: Peng et al., ACL 2018."}, {"review_id": "Gqb5bh8CbG", "reviewer": "Reviewer_KpA9", "summary": "The authors define and study the problem of multi-instance partial label learning (PLL), where weak supervision is given in the form of a (potentially) unknown transition function $\\sigma$, which maps the ground truth labels onto some label set $S$. \n\nUnder this problem setting, the paper goes on to show multiple theoretical contributions\n* 1) Under a known transition function (i.e. SUM2 in the MNIST task), a sufficient and necessary condition for learnability is M-ambiguity.\nTo get faster rates (removing the exponential term of 1/M), they show a stronger condition of 1-ambiguity (or that the output of the transition function given one label perturbation will also be changed).\nThey generalize this to consider a top-k loss that is a more efficient surrogate\n* 2) They study the setting of learning multiple classifiers with shared label spaces, and provide similar learnability results under analogies of M-ambiguity for multiple classifiers, with an additional assumption on the boundedness of the risk function.\n* 3) Finally, they provide a similar result for learning a single classifier under an unknown transition function, which requires a new assumption about the transition space being unambiguous and the boundedness of the risk function.\n\nThe paper also provides experiments to evaluate the quality of existing weakly supervised/neuro-symbolic architectures, which support their theoretical findings and takeaways.\n", "questions": "Are the scalability issues as observed in Table 2 primarily due to the chosen neuro-symbolic methods, the PLL setting, or a combination of both factors?", "limitations": "Limitations are sufficiently addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper provides comprehensive theoretical results for the PLL setting. They provide results for multiple different problem setups, considering known/unknown transition functions and learning a single/multiple classifiers. \n\nThey provide rigorous theoretical analysis, which requires (in my opinion) rather intuitive assumptions. \n\nRelevent experiments are nicely descriptive and verify their theoretical analysis.\n", "weaknesses": "As mentioned in the paper, scalability seems to be an issue with the experimental setting. On what seems to be a not overly complex task (a weighted sum of 4 MNIST digits), performance indeed significantly drops, which calls into question the widespread potential of the PLL setting (and not this paper in particular). \n\nWhile the examples are given that illustrate when the various ambiguity assumptions are violated or not violated, a more in depth discussion in the case of Definition 5 would be appreciated, as this is the most interesting setting of an unknown transition function.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q: As mentioned in the paper, scalability seems to be an issue with the experimental setting. On what seems to be a not overly complex task (a weighted sum of 4 MNIST digits), performance indeed significantly drops, which calls into question the widespread potential of the PLL setting (and not this paper in particular). Are the scalability issues as observed in Table 2 primarily due to the chosen neuro-symbolic methods, the PLL setting, or a combination of both factors?\n\nThe scalability issue is caused by both the PLL problem and neuro-symbolic methods. Please check the section **Comments on scalability and accuracy** in our general rebuttal at the top for a detailed explanation.\n\nAbout the potential of multi-instance PLL and its applications, please see the **Importance of multi-instance PLL** section in the general rebuttal. Overall, we understand the criticism towards the accuracy and the scalability of the current neuro-symbolic learning techniques. However, as we discuss in the response to all the reviewers, we see these issues as an opportunity to develop new neuro-symbolic learning techniques (especially, when the transition functions are unknown) and explore new research questions. We will add this discussion in the revision of our work. \n  \n> Q: While the examples are given that illustrate when the various ambiguity assumptions are violated or not violated, a more in depth discussion in the case of Definition 5 would be appreciated, as this is the most interesting setting of an unknown transition function.\n\nThanks for the comments. We will follow your suggestion and provide a more in-depth discussion in the revised version. Below, please find a summary of clarifications.\n- About the intuition. This unambiguity notion requires that for each candidate transition $\\sigma’$ and each diagonal label vector, flipping one of the labels leads to a different partial label $s$. This ensures that even if the learner chooses a wrong transition, it is still possible to detect the classification error by observing the partial error.\n- What happens when the transition space is ambiguous? If $\\mathcal{G}$ is not unambiguous, then a wrong transition and an imperfect classifier may lead to zero partial risk. In other words, a wrong transition may “hide” the classification mistakes.\n- How to examine ambiguity in practice? Although in practice the true transition is hidden, one can examine this condition by checking a sufficient condition: for each $\\sigma’ \\in \\mathcal{G}$ and each two different labels $\\\\{l_i \\ne l_j\\\\} $, the set $\\\\{\\sigma’(y) | y \\in \\\\{l_i,l_j\\\\}^M \\\\}$ is not a singleton. The latter condition ensures that when given a fixed diagonal label vector, and when the classifier makes mistakes, the predicted partial labels are not unique, and hence cannot all agree with the ground truth label. \n"}]

Author rebuttal:
We would like to express our gratitude to all the reviewers for their valuable feedback. Below, we address some commonly raised issues.

**Comments on the importance of multi-instance PLL raised by reviewers vhBR & KpA9**. Multi-instance PLL captures neuro-symbolic learning and latent structural learning in NLP [AdditionalRef1]. The latter settings have, in turn, several advantages over end2end neural architectures. One obvious advantage is the ability to extract and reuse the latent model. Another advantage is improved end-task accuracy. For instance, learning via multi-instance PLL can lead to architectures with higher accuracy than that of end2end architectures in NLP [AdditionalRef1] and visual QA tasks [22]. It is worth noting that several recently proposed neuro-symbolic works are based on multi-instance PLL (e.g., [11,22,25]), so we do believe that this learning setting will find more applications in the future.   

**Comments on our contributions raised by reviewer 6VmD**. We would like to point out a misunderstanding regarding the applicability of our results. Reviewer 6VmD claims that we prove learnability with distributions that concentrate mass on a single instance/label. However, this is not true, as our learnability results *do* apply to any distribution, not only just the concentrated ones. The only reason we mentioned concentrated distributions is to prove that the proposed conditions are necessary (instead of just being sufficient). We will improve our presentation in the revision to emphasize the generality of our results. We also provide a more detailed discussion in the individual response below. 

**Comments on scalability and accuracy made by reviewers a7AK & KpA9**. First, while WEIGHTED-SUM might seem an easy scenario at first sight, it is quite challenging, as the hidden space grows exponentially in the domain of the weights, i.e., $M^{10} \times M^5$ (recall that the weights are in $\\{1, …, 5\\}$). Notice also that when restricting to binary weights, WEIGHTED-SUM reduces to learning Boolean formulas with conjunction and disjunction [35] as discussed in Section 6. It is worth stressing that both scalability and accuracy significantly improved when the transition is known (see the **Updates on empirical analysis** section below), i.e., basically the original learning setting supported by the neuro-symbolic techniques considered in Section 6.

Second, scalability is a known problem in neuro-symbolic learning. This is partially due to the fact that the relevant problems in logical reasoning are intractable. For instance, semantic loss [50] (adopted by DLog [29], DLog-A [30], NLog [41] and Scallop [22]) requires computing the models of Boolean formulas, which is #P-complete. Reasoning over logical theories can be also intractable [AdditionalRef2] (notice that NASP fails to support the WEIGHTED-SUM scenario for $M \ge 3$ due to its inability to ground the relevant theory), if not undecidable, while various satisfiability problems are NP-hard to solve in an exact fashion. Scalability also straightforwardly affects accuracy, e.g., NLog obtains better accuracy over DLog-A for $M=3$ (see Table 2) due to its ability to explore the whole search space. The above challenges bring up new research directions. 

It is worth noting that there have been promising attempts recently to tackle those challenges. For instance, the following works can be incorporated into neuro-symbolic learning techniques to improve scalability: 
- A scalable grounder for probabilistic Datalog: E. Tsamoura et al., “Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue”, SIGMOD 2023. 
- A scalable approximate model counting technique: Mate Soos et al., “Engineering an Efficient Approximate DNF-Counter”, IJCAI 2023.

**Updates on the empirical analysis**. To further address some of the reviewers’ concerns, we repeated the WEIGHTED-SUM scenario (Section 6) using Scallop [22]. Scallop supports the top-k semantic loss (Section 3.2). In the attached PDF, the LHS of Figure 1 shows the accuracy of the MNIST digit classifier every 1000 iterations for $k = \\{1, 2, 3, 4\\}$, when $M = 4$, $m_P = 10000$. The digit classifier has been pre-trained using 16 labeled MNIST digits, having classification accuracy equal to 58%. In contrast to DLog-A and NLog (see Table 2 in our submission), the accuracy of the digit classifier improves to 84% when $k > 1$, showing that multi-instance partial labels can improve the classification accuracy even with unknown transitions. The above result empirically shows the benefits of the top-k semantic loss approximation (Section 3.2) over approximations proposed by other neuro-symbolic techniques (see Table 2 in our submission).    

To address the comment of reviewer a7AK on learning with known transitions, we repeated the experiment described in the previous paragraph except that the weights are now known and randomly chosen from $\\{1, …,100\\}$ (RHS of Figure 1 in the PDF). In contrast to the unknown case, the classification accuracy exceeds 98%. To further assess scalability, we repeated the latter experiment for $M = \\{6, 10\\}, k = \\{1, 3\\}$ and $m_P = 10000$, see Figure 2. Again, the accuracy of the digit classifier exceeds 98%, a result that is quite surprising, given that the supervision signal is rather weak when $M=10$. The above shows that PLL with known transitions is, expectedly, simpler.

Finally, we want to mention that the NASP [53] authors informed us about a bug in their implementation, due to which the weight classifier was not trained. We repeated WEIGHTED-SUM for $M = 2$, obtaining accuracy up to 98%. However, even after the bug fix, NeurASP could not scale for $M \ge 3$.

We proceed with other individual comments below.

---
- [AdditionalRef1] Peng et al., “Backpropagating through Structured Argmax using a SPIGOT”, ACL 2018.
- [AdditionalRef2] J. Baget, et al., “Walking the complexity lines for generalized guarded existential rules”, IJCAI 2011.

Meta-review: This papers studies a set of problems in a variant of weak supervision. In these cases, there is no access to ground-truth labels. Instead there is a known or unknown function that takes in a subset of datapoints and outputs some value that may or may not provide signal. The authors study learnability and produce error bounds in both the known and unknown signal function settings. While predominantly a theoretical paper, the authors also provide some empirical validation for their claims.

This is a nice paper that provides the fundamentals for a type of weak supervision that connects to neurosymbolic learning. Given that there is a lot of interest in these settings, but relatively little study of the basic learning-theoretical fundamentals, I believe it is a worthwhile contribution. The reviewers agree and generally agreed.
Decision: Accept (poster)