A Unified Approach to Count-Based Weakly Supervised Learning
Authors: Vinay Shukla
Zhe Zeng
Kareem Ahmed
Guy Van den Broeck
Venue: NeurIPS 2023 poster (2023)
Keywords: weakly supervised learning
constraint
label proportion
learning from positive and unlabeled data
multiple instance learning
TL;DR: We provide a unified approach for weakly supervised learning through count-based constraints.

Abstract: High-quality labels are often very scarce, whereas unlabeled data with inferred weak labels occurs more naturally. In many cases, these weak labels dictate the frequency of each respective class over a set of instances. In this paper, we develop a unified approach to learning from such weakly-labeled data, which we call *count-based weakly-supervised learning*. At the heart of our approach is the ability to compute the probability of exactly $k$ out of $n$ outputs being set to true. This computation is differentiable, exact, and efficient. Building upon the previous computation, we derive a *count loss* penalizing the model for deviations in its distribution from an arithmetic constraint defined over label counts.

A Unified Approach to Count-Based Weakly-Supervised Learning
Vinay Shukla
Zhe Zeng"
Department of Computer Science University of California, Los Angeles vshuklaøg ucla.ede
Department of Computer Science University of California, Los Angeles zhezengåca wcla. edu
Kareem Ahmed
Guy Van den Broeck
Department of Computer Science University of California, Los Angeles ahmedk@cs ucla. edu
Department of Computer Science University of California, Los Angeles guyvdbēcs ucla.edu
Abstract
High-quality labels are often very scarce, whereas unlabeled data with inferred weak labels occurs more naturally. In many cases, these weak labels dictate the frequency of each respective class over a set of instances. this paper, we develop unified approach to learning from such weakly-labeled data, which call count- based
learning. At the heart of our approach is the ability compute the probability of exactly & out of outputs being set true. This computation differentiable, exact, and efficient. Building upon the previous computation, derive count loss penalizing the model for deviations in its distribution from an arithmetic constraint defined over label counts. We evaluate our approach three common weakly-supervised learning paradigms and observe that our proposed approach achieves state-of-the-art or highly competitive results across all three of the paradigms.
Introduction
Weakly supervised learning [56] enables model to learn from data with restricted, partial or inaccurate labels, often known weakly-labeled data. Weakly supervised learning fulfills need arising in many real-world settings that are subject to privacy or budget constraints, such as privacy sensitive data [45], medical image analysis [12], clinical practice [39], personalized advertisement [9] and knowledge base completion [21, 59], to name few. In some settings, instance-level labels are unavailable. Instead, instances grouped into bags with corresponding bag-level labels that are a function of the instance labels, e.g.. the proportion of positive labels in a bag. A key insight that bring forth is that such weak supervision can very often be construed as enforcing constraints label counts of data.
More concretely, we consider three prominent weakly supervised learning paradigms. The first paradigm known learning from label proportions [38]. Here the weak supervision consists in the proportion of positive labels in a given bag, which can be interpreted as the count of positive instances such a bag. The second paradigm, whose supervision is strictly weaker than the former, is multiple instance learning [35, 17]. Here the bag labels only indicate the existence of at least one positive instance bag, which can be recast as whether the count of positive instances is greater than zero. The third paradigm, learning from positive and unlabeled data [16, 31], grants access to
Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Ma/k
{a.)=e 1
max
2B
y
O
O
0
O
?
O
O
/
0
/
0
?
3/5
O
Classical
(c) MIL
(d) PU Learning
Table I: A comparison of the tasks considered in the three weakly supervised settings, LLP (cf. Section 2.1), MIL (cf. Section 2.2) and PU learning (cf. Section 2.3), against the classical fully
supervised setting for binary classification, using digits from the MNIST dataset.
the ground truth labels for subset of only the positive instances, providing only class prior for what remains. We can recast the class prior as a distribution of the count of positive labels.
Leveraging the view of weak supervision constraint label counts, utilize simple, efficient and probabilistically sound approach to weakly supervise learning. More precisely, we train a neural network to make instance-level predictions that conform to the desired label counts. To this end, we propose a differentiable count loss that characterizes how close the network's distribution comes to the label counts; loss which is surprisingly tractable. Compared prior methods, this approach does not approximate probabilities but computes them exactly. Our empirical evaluation demonstrates that our proposed count loss significantly boosts the classification performance on all three aforementioned settings.
2 Problem Formulations
In this section, we formally introduce the aforementioned weakly supervised learning paradigms. For notation, let X' Rdd be the input feature space d features and y {0, 1} be binary label space. We write x E X' and y E y for the input and output random variables respectively. Recall that fully-supervised binary classification, is assumed that each feature and label pair (xx y) X' x y is sampled independently from a joint distribution p(æ, y). A classifier f is learned to minimize the risk R(f) E(..,)><pl [f (f)),, y)] where l: [0, x y - Rgo the cross entropy loss function. Typically, the true distribution p(æ, y) is implicit and cannot be observed. Therefore, set of training samples, D ( yı ) is used and the empirical risk, R(ʃ) = Σ {(f(x)) ys). is minimized in practice. In the count-based weakly supervised learning settings, the supervision is given a bag level instead of an instance level. We formally introduce these settings as below.
2.1 Learning from Label Proportions
Learning from label proportions (LLP) [38] assumes that each instance in the training set assigned to bags and only the proportion of positive instances in each bag is known. One example is in light of the coronavirus pandemic, where infection rates were typically reported based on geographical boundaries such as states and countics. Each boundary can be treated bag with the infection rate as the proportion annotation.
The goal of LLP is to learn an instance-level classifier & + [0, 1] even though it is trained on bag- level labeled data. Formally, the training dataset consists of m bags, denoted by D {(B,, 9 )m 1
where each bag B, ( consist of k instances and this could vary among different bags.
The bag proportions are defined as 9; ΣØ= y/ 2 with yj being the instance label that cannot be accessed and only ÿi is available during training. An example is shown in Figure 1b. We do not assume that the bags are non-overlapping while some existing work suffers from this limitation including Scott and Zhang [40].

---

Table 2: A summary of the labels and objective functions for all the settings considered in the paper.
TASK
LABEL
LABEL LEVEL
OBJECTIVE
Classical Fully Supervised
Binary y
Instance Level
-Vlggrt)) (1 3) log(1 - p(x))
Learning from Label Proportion
Continuous = >: Ba/k
Bag Level
logp(2 8. = kgj
Multiple Instance Learning
Binary i = max(v:)
Bag Level
-loogoo 2 1) Log
Learning from Positive and Unlabeled Data
(xi((Ln( p( 9.)
Binary y
Instance Level
logp( Di k9)
2.2 Multiple Instance Learning
Multiple instance learning (MIL) [35, 17] refers to the scenario where the training dataset consists of bags of instances, and labels are provided at bag level. However, in MIL, the bag label is single binary label indicating whether there is a positive instance in the bag or not as opposed to bag proportion defined in LLP. A real-world application of MIL lies in the field of drug activity [17]. We can observe the effects of a group conformations but not for any specific molecule, motivating MIL setting. Formally, in MIL, the training dataset consists of m bags, denoted by R. Mt } with a bag consisting of l instances, i.c., B; = { } The size can vary
D = (B, among different bags. For each instance z.. there exists instance- levell label yj which is not accessible. The bag-level label is defined as i/ = max, (Ug} }- An example is shown in Figure Ic.
The main goal of MIL is to learn model that predicts bag label while more challenging goal is to learn an instance-level predictor that is able discover positive instances in bag. In this work, we aim to tackle both by training an instance-level classifier whose predictions can be combined into bag-level prediction as the last step.
2.3 Learning from Positive and Unlabeled Data
Learning from positive and unlabeled data or PU learning [16, 31] refers to the setting where the training dataset consists of only positive instances and unlabeled data, and the unlabeled data can contain both positive and negative instances. A motivation of PU learning is persistence in the case of shifts to the negative-class distribution [37], for example, a spam filter. An attacker may alter the properties of spam email, making traditional classifier require new negative dataset [37]. We note that taking a new unlabeled sample would be more efficient, motivating PU learning. Formally, in PU learning, the training dataset D DD U D., where D, = {(x;, Di 1))e is the set of positive instances with x, from p( = 1) and ÿ denoting whether the instance is labeled, and D. {(x,, = 0) the unlabeled set with æ, from
Pu (m) = 3 p( y = 1) + p(
(I)
where the mixture proportion 3= p(y =1 1 = 0) is the fraction of positive instances among the unlabeled population. Although the instance label y is not accessible, its information can be inferred from the binary selection label ÿ: if the selection label ī = 1, it belongs to the positively labeled set, i.., pvy 1 5 1)= 1; otherwise, the instance can be either positive negative. An example of such a dataset is shown in Figure 1d.
The goal of PU learning is to train an instance-level classifier. However, it is not straightforward to learn from PU data and it necessary to make assumptions to enable learning with positive and unlabeled data [9]. In this work, we make commonly-used assumption for PU learning, selected completely at random (SCAR), which lies at the basis of many PU learning methods.
Definition 2.1 (SCAR). Labeled instances are selected completely at random, independent from input features, from the positive distribution p(æ y 1). that is, p(ğ = 1 Φ. y = 1) = p(ū = 1| 1).
3 A Unified Approach: Count Loss
In this section, we derive objectives for the three weakly supervised settings, LLP, MIL, and PU learning, from first principles. Our proposed objectives bridge between neural outputs, which can be observed as counts, and arithmetic constraints derived from the weakly supervised labels. The idea is to capture how close the classifier is to satisfying the arithmetic constraints on its outputs.
3

---

Algorithm Count Probability p p(Ei= Ds =)
Input: A set of k log probabilities {4: with 4 == logp(ū: 1), the number of instances k; and
label sum
Output: log probabilities log Ex= 0t = 8) or a set of log probability 0z = ==)]==0
// Ali, m] = log
m) Vi, m Initialize an array A to be IInf everywhere
j= p(E
Bi
A(0, 0] = 0 // p/ /=1 Vj 0) =
Compute E/ < log1mexp(tt) // log 0)
for to do
for = 0 to do
a. = Ali - 1, m
1] +
a_ Ali - 1. m] t
Ali m] = loogsumxpp(auu (a, a_)
return Ak, s) :]
They can be easily integrated with deep learning models, and allow them to be trained end-to-end. For the three objectives, we show that they share the same computational building block: given instances {x; and an instance-level classifier f that predicts p(O: æx) with ý denoting the prediction variable, the problem of inferring the probability of the constraint on counts Σx= Di = compute the count probability defined below:
PL
J = (x.))
Σ DEVA
D1
s] II
p(U: xx))
where [-] denotes the indicator function and y denotes the vector (01, .k)- For succinctness, we omit the dependency the input and simply write the count probability as p(Σ D; = s). Next, we show how the objectives derived from first principles can be solved by using the count probability
oracle. We summarize all proposed objectives in Table 2. Later, we will show how this seemingly intractable count probability can be efficiently computed by our proposed algorithm.
LLP setting. Given bag B = { of size k and its weakly supervised label ÿ. by definition, can be inferred that the number of positive instances (count) in the bag is k-j. Our objective is to minimize the negative log probability log p(E, Di kg)). Notice that when each bag consists of only one instance, that is, when the bag-level supervisions are reduced to instance-level ones, this objective is exactly cross-entropy loss. We further show that our method is risk-consistent, that is, the optimal classifier under our proposed loss provides predictions consistent with the underlying risk as in the supervised learning setting. Details of the risk analysis can be found in Appendix A.
MIL setting. Given a bag {x; 1 of size and a single binary label ý as its weakly supervised label, we propose cross- cross-entropy loss as below
{B, () - log Σ 2)
()) log pl Σ 0 0).
Notice that in the above loss, the probability term p(Σ 01 0) is accessible to the oracle for computing count probability, and the other probability term p( 0. 2 1) can simply be obtained from 1-m ` = 0), i.e., the same call to the oracle since all prediction variables ÿ; are binary.
PU Learning setting. Recall that for the unlabeled data D., in the training dataset, an unlabeled instance x, is drawn from a mixture distribution as shown in Equation parameterized by a mixture proportion 3 p(y
ÿ 0). Under the SCAR assumption, even though only class prior is given, we show that the mixture proportion can be estimated from the dataset.
Proposition 3.1. With SCAR assumption and a class prior = p(y = 5 = 0) can be estimated from dataset D.
p(u 1), the mixture proportion
Proof. First, the label frequency p(ū = 1 1y = 1) denoted by can be obtained by c p( = 1.1y==1 p(ū
(by the definition of PU learning).
p
p(y 1)

---

3
4P0-00 py=n
p
p
=)1
(
0
0
P
100=0)
Yo-
(6-1)
p 1======000000
p bF =
p =
Figure 1: example of how to compute the count probability in dynamic programming manner.
Assume that an instance-level classifier predicts three instances to have p(y1 1) 0.1, p(12 = 1) = 0.2, and p(ya = 1) = 0.3 respectively. The algorithm starts from the top-left cell and propagates the results down right. A cell has its probability p(Ej= = 8) computed by inputs from p p(E)= = s) weighted by ply; = 0), and p(Ej=o = ---1 1) weighted by p(ys = 1) respectively, as indicated by the arrows.
that is, p(ğ 1)/a. Notice that p(ū 1) can be estimated from the dataset D by counting the proportion of the labeled instances. Thus, we can estimate the mixture proportion as below,
8 p(
pply
rlū 1 1))r(y = c)ox
p 0)
p(y
ac
The probabilistic semantic of the mixture proportion that if we randomly draw an instance æ; from the unlabeled population, the probability that the true label yi is positive would be B. Further, if we randomly draw instances, the distribution of the summation of the true labels Σ Vi conforms to a binomial distribution (in (3) parameterized by the mixture proportion 3, i.e.,
(
kk) ( 8)k
5)
80
Based on this observation, we propose an objective to minimize the KL divergence between the distribution of predicted label and the binomial distribution parameterized by the mixture proportion for a random subset drawn from the unlabeled population, that is,
Bin(s;
DeL Bin(k,
||
p
Di)
Bin 8) log
p P do =s
1=1
==0
where Bin(s; kr 3) denotes the probability mass function of the binomial distribution (kn 33). Again, the KL divergence
be obtained k calls the oracle for computing count probability p( 1 04 s). The KL. divergence is further combined with cross entropy defined over labeled data D, in the classical binary classification training the overall objective.
As an alternative, we propose objective for the unlabeled data that requires fewer calls the oracle: instead of matching the distribution of the predicted label sum with the binomial distribution, this objective matches only the expectations of the two distributions, that is, to maximize p(Σ 91 k3) where k3 the expectation of the binomial distribution Bin(k, 3). We present empirical evaluations of both proposed objectives in the experimental section.
4 Tractable Computation of Count Probability
the previous section, we show how the count probability p p(Et 0: 8) serves as a computational building block for the objectives derived from first principles for the three weakly supervised learning settings. With a closer look at the count probability, we can see that given set of instances, the classifier predicts an instance-level probability for each and requires further manipulation to obtain
5

---

count information; actually, the number of joint labelings for the set can be exponential in the number of instances. Intractable as seems, we show that is indeed possible to derive a tractable computation for the count probability based on result from Ahmed et al. [6].
Proposition 4.1. The count probability p p(E 02 = s) of sampling l prediction variables that sums to from unconstrained distribution ply) = I p(ğ:) can be computed exactly in time O(ks). Moreover, the set {p(Ei=1 D: = s)}== can also be computed in time O(K2).
The above proposition can be proved a constructive way where we show that the count probability p(E 0s = s) can be computed in a dynamic programming manner. We provide an illustrative example of this computation in Figure 1. In practice, implement this computation in log space for numeric stability which we summarized as Algorithm 1, where function log Log1mens mmexp provides a numerically stable way to compute log1mexp( (a) log(1 exp(x)) and function logsumexp
numerically stable way to compute 1 logsumexp(1;; (I, u) = log (og(exp(z)) + exp(y)) Notice that since we show it is tractable to compute the set {p(_. i- D1 s) })}=_ for any two given label sum 81 and 52. a count probability p(s) S <E, Ue S 82) where the count lies in an interval, can also be exactly and tractably computed. This implies that our tractable computation of count probabilities can potentially be leveraged by other count-based applications besides the three weakly supervised learning settings in the last section.
5 Related Work
Weakly Supervised Learning. Besides settings explored in our work there are many other weakly-
supervised settings. One of which is semi-supervised learning, close relative to PU Learning with the difference being that labeled samples can be both positive and negative [57, 58]. Another is label noise learning, which occurs when our instances are mislabeled. Two common variations involve whether noise is independent or dependent on the instance [20, 42]. A third setting is partial label learning, where each instance is provided set of labels of which exactly one is true [14]. An extension of this is partial multi-label learning, where among a set of labels, a subset is true [46].
Unified Approaches. There exists some literature in regards to "general" approaches for weakly supervised learning. One example being the method proposed in Hüllermeier [23], which provides procedure that minimizes the empirical risk on "fuzzy" sets of data. The paper also establishes guarantees for model identification and instance-level recognition. Co- Training and Self- Training are also examples of similar techniques that applicable to wide variety of weakly supervised settings [11, 49]. Self-training involves progressively incorporating more unlabeled data via our model's prediction (with pseudo-label) and then training model on more data as an iterative algorithm [25]. Co-Training leverages two models that have different "views" of the data and iteratively augment each other's training set with samples they deem as "well-classified" They are traditionally applied to semi-supervised learning but can extend to multiple instance learning settings [33, 47, 32].
LLP. Quadrianto et al. [38] first introduced an exponential family based approach that used an estimation of mean for each class. Others seek to minimize "empirical proportion risk" or EPR as in Yu et al. [50], which is centered around creating an instance-level classifier that is able reproduce the label proportions of each bag. As mentioned previously, more recent methods use bag posterior approximation and neural- based approaches [8, 43]. One such method is Proportion Loss (PL) [43], which we contrast to our approach. This is computed by binary cross entropy between the averaged instance-level probabilities and ground-truth bag proportion.
MIL. MIL finds its earlier approaches with SVMs, which have been used quite prolifically and still remain of the most common baselines. We start with MI-SVM/mi-SVM, [7] which are examples of transductive SVMs [13] that seek a stable instance classification through repeated retraining iterations. MI-SVM is example of an instance space method [13], which identifies methods that classify instances as a preliminary step in the problem. This is in contrast to bag-space or embedded space methods that omit the instance classification step. Furthermore, Wang et al. [44] remains one of the hallmarks of the use of neural networks for Multi-Instance Learning. Ilse et al. [24], utilize a similar approach but with attention-based mechanisms.
PU learning. Bekker and Davis [9] groups PU Learning paradigms into three main classes: two step, biased, and class prior incorporation. Biased learning techniques train classifier on the entire dataset

---

Table 3: LLP results across different bag sizes. We report the mean and standard deviation of the test AUC over 5 seeds for each setting. The highest metric for each setting is shown in boldface.
Dataset
Dist
Method
8
128
512
Adult
[0. 7
PL.
0.8889 + 0.0024
0.8782 + 0.0036
0.8743 = 0.0039
0.8678 + 0.0085
Adult
[0.
LMMCM
0.8728 + 0.0019
0.8693 + 0.0047
0.8669 + 0.0011
0.8674 + 0.0040
Adult
[0. 21
CL (Ours)
0.8984 + 0.0013
0.8848 + 0.0041
0.8743 = 0.0052
0.8703 + 0.0070
Adult
[_
PL
0.8781 + 0.0038
0.8731
0.0035
0.8699 = 0.0057
0.8556 = 0.0180
Adult
LMMCM
0.8584 + 0.0164
0.8644 0.0052
0.8601 0.0045
0.8500 = 0.0186
Adult
[ 1]
CL (Ours)
0.8854 + 0.0022
0.8738 + 0.0039
0.8675 + 0.0043
0.8607 = 0.0056
Adult
[0, 1]
PL
0.8884 + 0.0030
0.8884 + 0.0008
0.8879 = 0.0025
0.8828 + 0.0051
Adult
[0, 1]
LMMCM
0.8831 + 0.0026
0.8819 + 0.0006
0.8821 + 0.0017
0.8786 = 0.0052
Adult
00, 1]
CL (Ours)
0.8985 0.0010
0.8891 0.0013
0.8871 0.0021
0.8790 = 0.0056
Magic
[0,
PL.
0.8900 + 0.0095
0.8510 0.0032
0.8405 0.0110
0.8332 + 0.0149
Magic
[0,
LMMCM
0.8918 + 0.0077
0.8799 + 0.0113
0.8753 + 0.0157
0.8734 + 0.0092
Magic
[0,
CL (Ours)
0.9088 + 0.0056
0.8830 + 0.0097
0.8926 = 0.0049
0.8864 + 0.0107
Magic
1]
PL
0.9066 + 0.0016
0.8818 + 0.0108
0.8769 + 0.0101
0.8429 = 0.0443
Magic
LMMCM
0.8911 + 0.0083
0.8790 0.0091
0.8684 0.0046
0.8567 = 0.0292
Magic
CL (Ours)
0.9105 + 0.0020
0.8980 + 0.0059
0.8851 = 0.0255
0.8816 + 0.0083
Magic
[0, 1]
PI.
0.9039 + 0.0029
0.8870 + 0.0037
0.9002 0.0092
0.8807 + 0.0200
Magic
00, 1]
LMMCM
0.9070 + 0.0026
0.9048 + 0.0058
0.9113 + 0.0058
0.8 0.8934 = 0.0097
Magic
10, 1]
CL (Ours)
0.9173 0.0018
0.9102 0.0057
0.9146 = 0.0051
0.9088 0.0039
with the understanding that negative samples are subject to noise [9]. We will focus on subset of biased learning techniques (Risk Estimators) as they are considered state-of-the-ar and relevant to us baselines. The Unbiased Risk Estimator (uPU) provides an alternative to the inefficiencies in manually biasing unlabeled data [18, 37J. Later, Non-negative Risk Estimator (nnPU) [26] accounted for weaknesses in the unbiased risk estimator such overfitting.
Count Loss. To our knowledge, viewing the computation of the "bag posterior" as probabilistic new. However, the prior approaches do this implicitly. Many approaches have tried to approximate the "bag posterior" by averaging the instance-level probabilities among instance-level approaches, the MIL-pooling is an implicit "bag posterior" computation. These include mean, max, and log-sum-exp pooling to approximate the likelihood that a bag has at least one positive instance [44]. But again, these are all approximations of what our computation does exactly. In PU Learning, to our best knowledge, the view of unlabeled data as a bag annotated with the mixture proportion is new.
bag [8, 43]. In MII. settings,
Neuro-Symbolic Losses. In this paper, we have dealt with a specific form of distributional constraint. Conversely, there has been a plethora of work exploring the integration of hard symbolic constraints into the learning of neural networks. This can take the form of enforcing hard constraint [3], whereby the network's 's predictions are guaranteed to satisfy the pre-specified constraints. Or it can take the form of a soft constraint [48, 34, 1, 4, 2, 5] whereby the network is trained with an additional loss term that penalizes the network for placing any probability mass predictions that violate the constraint. While in this work we focus on discrete linear inequality constraints defined over binary variables, there is existing work focusing discrete and continuous variables and their tractability [10, 55, 54]. The development of inference algorithms for such constraints and their applications such as Bayesian deep learning remain active topic [52, 28, 53, 51].
hybrid linear inequality constraints defined over both
6 Experiments
In this section, we present a thorough empirical evaluation of our proposed count loss on the three weakly supervised learning problems, LLP, MIL, and PU learning." We refer the readers to the appendix for additional experimental details.
'Code and experiments are available https: //gi tht.. WWW.OL--StrrAACount...oooo
7

---

Table 4: MIL experiment the MNIST dataset. Each block represents different distribution from which we draw bag Jizes-Firyy Block: (10, Second Block: (50, 10), Third Block: (100, 20). We each experiment for 3 runs and report mean test AUC with standard error. The highest metric for each setting is shown in boldface.
Training Bags
50
100
150
200
300
130
300
Gated Attention
0.775 = 0.031
0.894 = 0.012
0.935 + 0.005
0.939 = 0. 8,00G
0.963 0.002
0.959 :: 0.002
0,966 = 0.003
Attention
0.807 = 0.026
0.913 + 0.006
0.940 + 0.004
0,942 + 0.007
0.967 = 0.002
0.961 0.005
0.965 +: 0.0004
ClurOurs)
0.906 0.009
0.929 0.005
0.946
0.952 0.004
0.002
0.963 0.002
Gated Atteation
0.943 = 0.005
0.949 0.009
0.970 + 0.005
0.977
0.001
0. 9.983 0.002
0,986 + 0.004
0.987
0,002
Attention
0.936 0.010
0,962 + 0.006
0.970 + 0.061
0.977
0.002
0.981 0.002
0.987
0.001
0.002
CL (Ours)
0,939 4: 0.010
0.960
0.002
0.964 1. 0.007
0.972 1: 0.002
0,982
0.003
0.982
0.001
0.987
0,002
Gated Attention
0.975 1: 0.003
0.981
0.004
0.992
0.002
0,957 1: 0.004
0.996
0.001
0.998
0.001
0.950
0.004
Attention (Ours)
0,984 =: 0,001
0.982
0.001
0.99%
:: 0.000
0.987 = 0.007
0.992
0.001
0.991
0.012
0,998
0.000
0.981 0.007
0.000
0.996 0.002
0.995 0.001
0.996
0.993 0.003
0.001
Table 5: MIL: We report mean test accuracy, AUC, F1, precision, and recall averaged over 5 runs with std. error on the Colon Cancer dataset. The highest value for each metric is shown in boldface.
Method
Accuracy
AUC
F1
Precision
Recall
Gated Attention
0.909 1 0.014
0.908 1 0.013
0.886 1 0.021
0.916 i 0.020
0.879 + 0.020
Attention
0.893 + 0.015
0.890 + 0.008
0.876 + 0.017
0.908 = 0.016
0.879 = 0.018
CL. (Ours)
0.915 + 0.008
0.912 + 0.010
0.903 + 0.010
0.936 + 0.014
0.898
0.007
6.1 Learning from Label Proportions
We experiment on two datasets: 1) Adult with 8192 training samples where the task is to predict whether a person makes over 50k: a year or not given personal information as input; 2) Magic Gamma Ray Telescope with 6144 training samples where the task predict whether the electromagnetic shower is caused by primary gammas or not given information from the atmospheric Cherenkov gamma telescope [19]."
We follow Scott and Zhang [40] where two settings are considered: one with label proportions uniformly on [0, 3] and the other uniformly [2. 1]. Additionally, we experiment on third setting with label proportions distributing uniformly on [0. 1] which is not considered in Scott and Zhang [40] but is the most natural setting since the label proportion is not biased toward either 0 or 1. We experiment on four bag sizes n E {8, 32, 128, 512].
Count loss (CL) denotes our proposed approach using the loss objective defined in Table 2 for LLP. We compare our approach with a mutual contamination framework for LLP (LMMCM) [40] and against Proportion Loss (PL) [43].
Results and Discussions We show our results in Table 3. Our method showcases superior results against the baselines on both datasets and variations in bag sizes. Especially in cases with lower bag sizes, i.e., 8, 32, CL greatly outperforms all other methodologies. Among our baselines are methods that approximate the bag posterior (PL), which we show to be less effective than optimizing the exact bag posterior with CL.
6.2 Multiple Instance Learning
We first experiment on the MNIST dataset [30] and follow the MIL experimental setting in Ilse et al. [24]: the training and test set bags are randomly sampled from the MNIST training and test set respectively; each bag can have images of digits from 0 to 9, and bags with the digit are labeled positive. Moreover, the dataset is constructed in a balanced way such that there is an equal amount of positively and negatively labeled bags in Ilse et al. [24]. The task is train a classifier that is able to predict bag labels; the more challenging task is to discover key instances, that is, to train a classifier that identifies images of digit Following Ilse al. [24], we consider three settings that vary in the bag generation process: in each setting, bags have their sizes generated from a normal distribution being (10, 2), A/ (50, N/ 20) respectively. The number of bags in
Pubblicyy available at archive. ics. uci. edu/ml
8

---

0.75
0.75
Test AUC
0.70
fist AUC
0.70
0.60
0.60
0.55
Gated Attention
0.55
Galed Attention
Attencin
0.50
Atterkion
10
15
20
25
30
35
40
10
15
20
25
30
35
40
Number of Bags
Number of Bags
Figure 2: MIL MNIST dataset experiments with decreased numbers training bags and lower bag size. Left: bag sizes sampled from N (10, 2); Right: bag sizes sampled from ( 1). We plot the mean test AUC (aggregated over 3 trials) with standard errors for bag sizes. Best viewed in color.
training set n. is in {50, 100, 150, 200, 300, 400, 500]. Thus, we have x 7 21 settings in total. Additionally, introduce experimental analysis how the performance of the learning methods would degrade as the number of bags and total samples in training set decreases, by modulating the number of training bags n be (10, 20, 30, 40} and selecting bag sizes from (5, 1) and (100, 2).
We also experiment the Colon Can- cer dataset [41] to simulate a setting where bag instances not indepen- dent. The dataset consists of 100 total hematoxylin-eosse (H&E) stained im- ages, each of which contains images of cell nuclei that are classified as one of: epithelial, inflammatory. fibroblast, and miscellaneous. Each image represents a bag and instances are 27 x 27 patches extracted from the original image. A positively labeled bag or image is one that contains the epithelial nuclei. For both datasets, we include the Attention and Gated Attention mechanism [24] baselines. We also use the MIL objective defined in Table 2.
2
9
8 < 10-6
7
7
4
< 10-
0.9967
< 10-b
6x
10-
10-5
S
8
6
5
q
O 100
< 10
< 100
< 10
< 10
1,00D
Figure A test bag from our MIL experiments, where we set only the digit 9 as a positive instance. Highlighted in red are digits identified to be positive with corresponding probability beneath.
Results and Discussions For the MNIST experiments, CL. is able outperform all other baselines or exhibit highly comparable performance for bag-level predictions as shown in Table 4. more interesting setting
compare how robust the learning methods are if the number of training bags decreases. Wang et al. [44] claim that instance-level classifiers tend to lose against embedding- basedd methods. However, we show in our experiment that this While Attention and Gated Attention are based on embedding. they suffer from more severe drop in predictive performance than CL when the number of training bags drops from 40 10; our method shows great robustness and consistently outperforms all baselines. The rationale we provide that with a lower number training instances, we need more supervision over the limited samples we have. Our constraint provides this additional supervision, which accounts for the difference in performance.
true all cases as seen in Figure
We provide an additional investigation in Figure to show that our approach learns effectively and delivers accurate instance-level predictions under bag-level supervision. Figure 3, we can see that even though the classifier is trained on feedback about whether bag contains the digit 9 or not, accurately discovers all images of digit 9. To reinforce this, Table and Table 8, in Appendix B, show that our approach outperforms existing instance-space space methods on instance-level classification.
Our experimental results the Colon Cancer dataset shown in Table 5. We show that both proposed objectives are able to consistently outperform baseline methods on all metrics. Interestingly, do not expect CL to perform well when instances in a bag dependent; however, the results indicate that our count loss is robust to these settings.

---

Table 6: PU Learning: We report accuracy and standard deviation test of unlabeled data, which is aggregated over 3 runs. The results from CVIR, nnPU, and uPU are aggregated over 10 epochs, in Garg al. [22], while we choose the single best epoch based validation for our approaches. The highest metric for each setting is shown in boldface.
Dataset
Network
CL.expect (Ours)
CL (Our))
CVIR
nnPU
nPU
Binarized MNIST
MLP
95.9 1 0.15
96.4 + 0.01
96.3 0.07
96.1 + 0.14
95.2 15.200.11 0.19
MNIST17
MLP
98.7 4 0.17
99.0 = 0.19
98.7
98.4
98.4 0.09
Binarized CIFAR
ResNet
79.2 0.27
80.1 = 0.34
77.2 0.18
76.7 = 0.74
CIFAR Cat vs. Dog
ResNet
76.5 1.86
74.8 : 1.64
73.3 0.99
71.8 + 0.33
68.8 : 0.53
6.3 Learning from Positive and Unlabeled Data
We experiment on dataset MNIST and CIFAR- 10 [29]. following the four simulated settings from Garg et al. [22]: Binarized MNIST: the training set consist of images of digits 0 9 and images with digits range [0, 4] are positive
CVR (Ours)
0.25
15mommat(100, 0.5)
instances while others as negative; 2) MNIST17:
Probabiiity
the training set consist of images of digits 1 and
0.15
7 and images with digit are defined as positive
while as negative: 3) Binarized CIFAR: the
0.10
training set consists of images from ten classes and images from the first five classes is defined as positive instances while others as negative; 4) CIFAR Cat vs. Dog: the training set consist of images of cats and dogs and images of cats are defined as positive while dogs as negative. The mixture proportion is 0.5 in all experiments. The performance is evaluated using the accuracy on test set of unlabeled data.
0.00
30
35
40
45
50
55
60
66
Count
Figure 4: MNIST17 setting for PU Learning: We compute the average discrete distribution for CL and CVIR, over 5 test bags, each which contain 100 instances. A ground truth binomial distribution As shown in Table 2, we propose two objectives of counts is also shown.
for PU learning. Our first objective is denoted by CL whereas the second approach is denoted by CL-expect. We compare against the Conditional Value Ignoring Risk approach (CVIR) [22], nnPU [26], and uPU [37].
Results and Discussions Accuracy results are presented in Table 6 where we can see that our proposed methods perform better than baselines on 3 out of the 4 simulated PU learning settings. CL-expect builds off similar "exactly-k" count approach, which we have shown work well in the label proportion setting. The more interesting results are from CL. where we fully leverage the information from distribution as supervision instead of simply using the expectation. We think of this as applying loss on each count weighted by their probabilities from the binomial distribution. We provide further evidence that our proposed count loss effectively guides the classifier towards predicting binomial distribution as shown in Figure 4: we plot the count distributions predicted by CL and CVIR as well as the ground-truth binomial distribution. We can see that CL able to generate the expected distribution, proving the efficacy of our approach.
7 Conclusions
In this paper, we present unified approach to several weakly-supervised tasks, i.e., LLP, MIL, PU. We construct our approach based on the idea of using weak labels to constrain count-based probabilities computed from model outputs. A future direction for our work can be to extend to multi-class classification as well as explore the applicability to other weakly-supervised settings, e.g.
label noise learning, semi-supervised learning, and partial label learning [15, 36, 58].
10

---

Acknowledgments
We would like thank Yuhang Fan for helpful discussions. This work was funded in part by the DARPA PTG Program under award HROO1 12220005, the DARPA ANSR program under award FA8750-23-2-0004, NSF grants #1IS-1943641, #1IS-1956441, #CCF-1837129, and gift from RelationalAI. GVdB discloses financial interest in RelationalAI. ZZ is supported by an Amazon Doctoral Student Fellowship.
References
[1] Kareem Ahmed, Eric Wang, Kai-Wei Chang, and Guy Van den Broeck. Leveraging unlabeled data for entity-relation extraction through probabilistic constraint satisfaction, mar 2021.
[2] Kareem Ahmed, Tao Li, Thy Ton, Quan Guo, Kai-Wei Chang, Parisa Kordjamshidi, Vivek Srikumar, Guy Van den Broeck, and Sameer Singh. Pylon: A pytorch framework for learning with constraints. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (Demo Track), feb 2022.
[3] Kareem Ahmed, Stefano Teso Kai- Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistie layers for neuro-symbolic learning. In Advances in Neural Information Processing Systems 35 (NeurIPS), dec 2022.
[4] Kareem Ahmed, Eric Wang, Kai- Wei Chang, and Guy Van den Broeck. Neuro-symbolic entropy regularization. The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
[5] Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. Semantic strengthening of neuro- symbolic learning. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics CAaiiess/AAA (AISTATS), apr 2023.
[6] Kareem Ahmed, Zhe Zeng, Mathias Niepert, and Guy Van den Broeck. Simple: gradient estimator for k-subset sampling. In Proceedings of the International Conference on Learning Representations (ICLR), may 2023.
[7] Stuart Andrews, Ioannis Tsochantaridis, and Thomas Hofmann. Support vector machines for multiple-instance learning. In NIPS, 2002.
[8] Ehsan Mohammady Ardehaly and Aron Culotta, Co-training for demographic classification using deep learning from label proportions. In 20/7 IEEE International Conference Data Mining Workshops (ICDMW), pages 1017-1024. IEEE, 2017.
[9] Jessa Bekker and Jesse Davis. Learning from positive and unlabeled data: A survey. Machine Learning, 109:719-760, 2020.
[10] Vaishak Belle, Andrea Passerini, and Guy Van den Broeck. Probabilistic inference in hybrid domains by weighted model integration. In Proceedings of IJCAI, pages 2770-2776, 2015.
[11] Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training. In Proceedings of the Eleventh Annual Conference Computational Learning Theory, COLT' 98, page 92-100, New York, NY, USA, 1998. Association for Computing Machinery. ISBN doi: 10. 10.1145/299943.279966
1581130570.
URL https: //doi. wtg/10...0 1145/279943.
279962.
[12] Gerda Bortsova, Florian Dubost, Silas Ørting, Ioannis Katramados, Laurens Hogeweg, Laura Thomsen, Mathilde Wille, and Marleen de Bruijne. Deep learning from label proportions for emphysema quantification. In Medical Image Computing and Computer Assisted Intervention- MICCAI 2018: 21 International Conference, Granada, Spain, September 16-20, 2018, Pro- ceedings, Part II 11, pages 768-776. Springer, 2018
[13] Marc-André Carbonneau, Veronika Cheplygina, Eric Granger, and Ghyslain Gagnon. Multiple instance learning: A survey of problem characteristics and applications. Pattern Recognition, 2018.
[14) Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12:1501-1536. 2.1

---

[15] Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. J. Mach. Learn. Res., 121mul)):5011-153, jul 2011. ISSN 1532-4435.
[16] Francesco De Comité, François Denis, Rémi Gilleron, and Fabien Letouzey. Positive and unlabeled examples help learning. pages 219-230, 12 1999. ISBN 978-3-540-66748-33 doi: 10.1007/3-540-46769 18.
[17] Thomas Dietterich, Richard Lathrop, and Tomás Lozano-Pérez. Solving the multiple instance problem with axis kiis-laalllll rectangles. Artificial Intelligence, 89:31-71, 03 2001. doi: 10.1016/ (0004-3702(99)0000344
[18] Marthinus C du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from pos- itive and unlabeled data. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, Curran Associates, Inc., 2014.
[19] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. UtL.http://arccive.. ics. uci. edu/ml.
[20] Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: survey. IEEE transactions on neural networks and learning systems, 25(5):845-866) 2013.
[21] Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M Suchanek. Fast rule mining in ontological knowledge bases with amic++. The VLDB Journal, 24(6):707-730, 2015.
[22] Saurabh Garg, Yifan Wu, Alexander J Smola, Sivaraman Balakrishnan, and Zachary Lipton. Mixture proportion estimation and pu learning: modern approach. Advances in Neural Information Processing Systems, 34:8532-8544 2021.
[23] Eyke Hüllermeier. Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization. International Journal of Approximate Reasoning, 55(7): 1519-1534, 2014.
[24] Maximilian Ilse, Jakub Tomezak, and Max Welling. Attention-based deep multiple instance learning. In International conference on machine learning, pages 2127-2136. PMLR, 2018.
[25] Giannis Karamanolakis. Subhabrata Mukherjee, Guoqing Zheng, and Ahmed Hassan Awadallah. Self-training with weak supervision. arXiv preprint arXi:: 2021.
[26] Ryuichi Kiryo, Gang Niu, Marthinus C Du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator. Advances in neural information processing systems, 30, 2017.
[27] Ryoma Kobayashi, Yusuke Mukuta, and Tatsuya Harada. Learning from label proportions with instance-wise consistency. arXiv preprint arXiv:2203. 12836, 2022.
[28] Samuel Kolb, Paolo Morettin, Pedro Zuidberg Dos Martires, Francesco Sommavilla, Andrea Passerini, Roberto Sebastiani, and Lue De Raedt. The pywmi framework and toolbox for probabilistic inference using weighted model integration. In Proceedings of the Twenty-Kight International Joint Conference on Artificial Intelligence, IJCAI, pages 6530-6533 7 2019. doi: 20249939/caii22211/94
[29] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009.
[30] Yann LeCun. The mnist database of handwritten digits. 1998.
[31] Fabien Letouzey, François Denis, and Rémi Gilleron. Learning From Positive and Unlabeled examples. In Proceedings of the 11th International Conference on Algorithmic Learning Theory, ALT'00, pages 71-85, Sydney, Australia, 2000. Springer Verlag.
[32] Kangning Liu, Weicheng Zhu, Yiqiu Shen, Sheng Liu, Narges Razavian, Krzysztof Geras, and Carlos Fernandez-Grands Multiple instance learning via iterative self- supervised contrastive learning. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pages 3355-3365, 2023.
12

---

[33] Huchuan Lu, Qiuhong Zhou, Dong Wang, and Ruan Xiang. A co-training framework for visual tracking with multiple instance learning. 2011 IEEE International Conference on Automatic Face & Gesture Recognition (FG), pages 539-544, 2011. doi: 10.1 (0.1109/FG.201 1.577115555
[34] Robin Manhaeve, Sebastijan Dumancie, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. In NeurIPS, 2018.
[35] Oded Maron and Tomás Lozano-Pérez. A framework for multiple- instaacc learning. In M. Jordan, M. Kearns, and S. Solla, editors, Advances in Neural Information Processing Systems, volume 10. MIT Press, 1997.
[36] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[37] Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, 2015.
[38] Novi Quadrianto, Alex Smola, Tibério Caetano, and Quoc Le. Estimating labels from label proportions. 2008.
[39] Gwenolé Quellec, Guy Cazuguel, Béatrice Cochener, and Mathieu Lamard. Multiple-instance learning for medical image and video analysis. IEEE reviews in biomedical engineering.
[40] Clayton Scott and Jianxin Zhang. Learning from label proportions: A mutual contamination framework. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 22256-22222222 222677. Curran Associates, Inc., 2020.
[41] Korsuk Sirinukunwattans. Shan e Ahmed Raza, Yee Tsang, David Snead, Ian Cree, and Nasir Rajpoot. Locality sensitive deep learning for detection and classification of nuclei in routine colon cancer histology images. IEEE Transactions on Medical Imaging, 35:1-1, 02 2016. doi: 10.1 00.1100/7M...0112255555
[42] Hwanjun Song, Minseok Kim. Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey, IEEE Transactions on Neural Networks and Learning Systems, 2022.
[43] Kuen-Han Tsai and Hsuan-Tien Lin. Learning from label proportions with consistency regular- ization. In Asian Conference on Machine Learning, pages 513-528. PMLR, 2020.
[44] Xinggang Wang, Yongluan Yan, Peng Tang, Xiang Bai, and Wenyu Liu. Revisiting multiple instance neural networks. Pattern Recognition, 74:15-24 24, 2018.
[45] Janusz Wojtusiak, Katherine Irvin, Aybike Birerdine, and Ancha Baranova. Using published medical results and non non-homogenous data in rule learning. In 2011 10th International Confer- ence on Machine Learning and Applications and Workshops, volume 2, pages 84-89, IEEE, 2011.
[46] Ming-Kun Xie and Sheng-Jun Huang, Partial multi-label learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[47] Chang Xu, Dacheng Tao, and Chao Xu. A survey on multi-view learning. arXiv preprint arXiv: 1wXvv:1304.5634 2013.
[48] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolic knowledge. In International conference on machine learning, pages 5502-5511. PMLR, 2018
[49] David Yarowsky. Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of the 33rd Annual Meeting on Association for Computational Linguistics, ACL '95, page 189-196, USA, 1995. Association for Computational Linguistics. doi: 10.3115/ 981658. 1684. URL https: :/dp:::::///.../// 10..0.111/991111 9816599911111.....111111
13

---

[50] Felix X Yu, Krzysztof Choromanski, Sanjiv Kumar. Tony Jebara, and Shih-Fu Chang, On learning from label proportions. arXiv preprint arXiv:1402.5902, 2014.
[51] Zhe Zeng and Guy Van den Broeck. Collapsed inference for bayesian deep learning. arXiv preprint 2rXiv:2306.0968,, 2023.
[52] Zhe Zeng and Guy Van den Broeck. Efficient search-based weighted model integration. Pro- ceedings of UAI, 2019.
[53] 7he Zeng, Paolo Morettin, Fanqi Yan, Antonio Vergari, and Guy Van den Broeck. Scaling up hybrid probabilistic inference with logical and arithmetic constraints via message passing, In Proceedings of the International Conference of Machine Learning (ICML), 2020.
[54] Zhe Zeng, Paolo Morettin, Fanqi Yan, Antonio Vergari, and Guy Van den Broeck. Probabilistic inference with algebraic constraints: Theoretical limits and practical approximations. Advances in Neural Information Processing Systems, 33:1 1151-11155555 11575, 2020.
[55] Zhe Zeng, Paolo Morettin, Fanqi Yan, Antonio Vergari, and Guy Van den Broeck. Is parameter learning via weighted model integration tractable? In Proceedings of the UAI Workshop on Tractable Probabilistic Modeling (TPM), jul 2021.
[56] Zhi-Hua Zhou. A brief introduction weakly supervised learning. National science review, (1):44-53, 2018.
[57] Xiaojin Zhu and Andrew B Goldberg. Introduction to semi-supervised learning. Springer Nature, 2022.
[58] Xiaojin Jerry Zhu. Semi-supervised learning literature survey. 2005.
[59] Kaja Zupanc and Jesse Davis. Estimating rule quality for knowledge base completion with the relationship between coverage assumption. In Proceedings of the 2018 World Wide Web Conference, pages 1073-1081, 2018.
14


Reviews:
[{"review_id": "vPkbxdCYLt", "reviewer": "Reviewer_jVGG", "summary": "This paper proposes a unification of three different kinds of weak supervision, viz., Learning from label proportions (LLP), Multi-instance learning (MIL), and learning from positive and unlabeled data (PU learning). They all involve supervision at the bag level instead of the instance level (except for PU learning, where some positive instances are also given). \nThe unification comes from the fact that in all three cases, we need to compute the probability distribution of a sum of binary variables using the probability distribution over each binary variable. To do so efficiently, the authors use the dynamic-programming algorithm proposed by Ahmed et al. 23. Once the distribution over sum is computed, it can easily be used to define the likelihood-based loss function for each of the three scenarios. For example, for LLP, one would directly maximize $log Pr(\\sum_{j \\in B_i} y_j = k_i)$ for a given $(B_i, k_i)$ train sample, and efficient computation of $log Pr(\\sum_{j \\in B_i} y_j = k_i)$ is done using DP algorithm proposed by Ahmed et al. 23\n", "questions": "1. The paper considers the scenario of only binary classification under weak supervision, whereas the evaluation is done against a more generic method (Tsai et al., 20). Is it possible to extend count loss to multi-class classification? Maybe, by considering it as a binary classification task with an additional one-hot constraint that can be enforced using the semantic loss function defined in Xu et al.,17, or other similar techniques.\n\n2. In the MIL experiment, observing the instance-level accuracy obtained by your method will be interesting. \n\n[Xu et al 17]: A Semantic Loss Function for Deep Learning with Symbolic Knowledge\n", "limitations": "The authors have sufficiently addressed the limitations of their work and also discuss the positive impact of weak supervision on the privacy of the subjects whose data is collected for training.\n\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is very well written, and the technique is clearly explained with all the assumptions and proofs.\n\nI like the idea of computing the exact probabilities for the sum of binary variables and using it to define the loss function for the three scenarios of weak supervision considered in the paper.\n\n\n", "weaknesses": "1. The crux of the paper lies in computing the probability over the sum of binary variables, which has been borrowed from Ahmed et al., 23. Extending the idea to apply it to the scenario of LLP, MIL, and PU is natural and not that novel.\n\n2. The related works section should also cover other paradigms of weak supervision, e.g. partial label learning.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank reviewer jVGG for the feedback. We are glad they found the paper well-written and enjoyed our approach.\n\n**[Related Work - Partial Label Learning]**\n\nThank you for the comment, we have included this as part of our general rebuttal section.\n\n**[Limited Novelty]**\n\nWe unify $3$ count-based weakly supervised frameworks under one exact, tractable, and differentiable computation and are the first ones to use this as a training objective. Furthermore, we extend the evaluation to *functions* of \"exactly-k\" as in the MIL setting (at least $k$) and PU setting (penalizing the count distribution against a binomial via KL Divergence). We point the reviewer to the general rebuttal section for more detail of our restatement of our contributions and novelty.\n\n**[Multi-class Classification]**\n\nYes, our method is certainly extendable to multi-class classification.\n\nSuppose we have a length n bag with label k. For binary classification we optimize the following probability:\n$P(\\text{Class}_1 = k, \\text{Class}_2 = n - k) = P(\\text{Class}_1 = k)$\n\nNow suppose we still have a bag length $n$. For multi-class, assume $\\text{Class}_1$ has count $a_1$, $\\text{Class}_2$ with count $a_2$, $\\text{Class}_3$ with count $a_3$, we want to optimize: \n$P(\\text{Class}_1 = a_1, \\text{Class}_2 = a_2, \\text{Class}_3 = a_3) = P(\\text{Class}_1 = a_1, \\text{Class}_2 = a_2)$\n, where $a_1 + a_2 + a_3 = n$. (Note that if we fix $a_1, a_2$, then $a_3$ is automatically fixed.)\n\nConsider the following non vectorized, non batched dynamic algorithm for $3$ classes. Note that this can easily extend to more than $3$ classes.\n\n```\ndef prob_equals_k_3(probs, class_1_count, class_2_count, bag_size):\n   dp = torch.zeros(bag_size + 1, class_1_count + 1, class_2_count + 1)\n   dp[0,0,0] = 1\n   for k in range(1, bag_size + 1):\n      for i in range(0, class_1_count + 1):\n         for j in range(0, class_2_count + 1):\n            if i + j > k:\n               continue\n            if i >= 1:\n               dp[k, i, j] += dp[k - 1, i - 1, j]*probs[k - 1, 0]\n            if j >= 1:\n               dp[k, i, j] += dp[k - 1, i, j - 1]*probs[k - 1, 1]\n            dp[k,i,j] += dp[k - 1][i][j]*(1 - probs[k - 1, 0] - probs[k - 1, 1])\n   return dp[bag_size, class_1_count, class_2_count]\n```\n\nIn the above algorithm, probs has shape (bag_size, $2$). Furthermore, $\\text{probs}[k - 1][0]$ is the probability that the kth instance is class 1, $\\text{probs}[k - 1][1]$ is the probability that the kth instance is class 2, and (1 - $\\text{probs}[k - 1][0]$ - $\\text{probs}[k - 1][1]$) is the probability that the kth instance is class 3 (note the indexing subtlety here). $dp[k, i, j]$ represents the probability that among the first $k$ instances, $i$ of them are class $1$, $j$ of them are class $2$, and $k - i - j$ of them are class $3$.\n\n**[Instance Level Performance]**\n\nWe show our results in the general rebuttal pdf in Table $1$ and Table $2$.\n\nWe take our baseline from [1], which is called Instance-max. For a bag of instances, Instance-max uses the maximum predicted probability as an approximation for probability that there exists at least one positive instance. We then train it with a binary cross entropy. Note that max pooling is stated in the literature as the best performing option and makes the “most sense” in the MIL setting [1, 2]. \n\nOur results show that for bags of size less than or equal to $150$, our method greatly improves upon the baseline and is better for bag sizes greater than or equal to $200$. We notice that across both methods, performance goes down as bag size increases; we expect this because we have less supervision on positive bags (at least $1$ label is less meaningful for bigger bags). However, our approach is able to recover this gap compared to the baseline methodology. In the case of *less* overall training bags, i.e. $\\leq 150$, we find that Instance-max really suffers on AUC while our objective guides the model to learning something more meaningful—showcasing the robustness of our methodology.\n\n**[References]**\n\n[1] Ilse, Maximilian, Jakub Tomczak, and Max Welling. \"Attention-based deep multiple instance learning.\" International conference on machine learning. PMLR, 2018.\n\n[2] Wang, Xinggang, et al. \"Revisiting multiple instance neural networks.\" Pattern Recognition 74 (2018): 15-24."}, {"review_id": "h0KgHbTmyP", "reviewer": "Reviewer_Q9rM", "summary": "The author proposes a differentiable count loss for three weak supervision settings: LLP, MIL, PU learning. The paper provides a clear explanation of the proposed loss, demonstrates strong empirical performance, and highlights the efficiency of its implementation using dynamic programming. ", "questions": "1. \"We also perform risk analysis with details in Appendix?\" Could you specify which appendix contains the details of the risk analysis?\n\n2.  Bottom of page 5: There appears to be a typo in the expression \"p(s_1 ≤ ∑_i y_i) ≤ s_2)\". Please correct this typo.\n\n3. In Proposition 4.1, it is unclear whether the dynamic programming approach is proposed or if it is directly using the result from Ahmed[1]. Please clarify this point.", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper provides a clear explanation of the proposed differentiable count loss, making it easier for readers to understand the methodology and its application in weak supervision settings.\n\n2. The paper demonstrates strong empirical performance across various tasks and datasets. This provides evidence of the effectiveness of the proposed loss and enhances the credibility of the research.\n\n3. The authors showcase the efficiency of their implementation by utilizing dynamic programming. This highlights the practicality and computational advantages of the proposed approach.", "weaknesses": "1. The paper could benefit from a clearer articulation of its contribution. Providing a more explicit comparison and emphasizing the novelty of the proposed method would strengthen the paper; The author mentioned that prior works (Ardehaly&Culotta and Tsi&Lin) are motivated by the same principle. More comparison to the prior work would be helpful.\n\n2. The paper lacks sufficient citations to related works; in the related work section “there exists some literature …, for example …” Expanding the reference list and acknowledging existing literature, would enhance the paper's academic rigor.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank reviewer Q9rM for the feedback. We are glad you found approach's efficiency, explanation, and applicability to be solid.\n\n**[Articulating Contribution]**\n\n“The paper could benefit from a clearer articulation of its contribution. Providing a more explicit comparison and emphasizing the novelty of the proposed method would strengthen the paper”\n\nOur contribution is a unifying framework for count-based weakly supervised settings. We use DP approach given by [1] and are the first ones to extend the loss function to train models. We also apply functions of \"exactly-k\" in our MIL and PU Learning approach. We point the reviewer to the general rebuttal section, where we articulated our contributions and novelty in more detail.\n\n**[Existing/Prior Work]**\n\n“More comparison to the prior work would be helpful.”\n\nThank you for this note. We will make sure to update our manuscript with more existing and prior work than we already have. We elaborated on prior \"unifying\" methods for weakly supervised learning, other weakly supervised learning paradigms, and also previous approaches that approximate our findings. (More detail in the general rebuttal.)\n\n**[Typos/Clarification]**\n\n“We also perform risk analysis with details in Appendix?\" Could you specify which appendix contains the details of the risk analysis?”\n\nAppendix A\n\nThank you for pointing out the other typos, they have been updated in a new version of the manuscript for the camera-ready.\n\n**[DP Approach]**\n\n“In Proposition 4.1, it is unclear whether the dynamic programming approach is proposed or if it is directly using the result from Ahmed[1]. Please clarify this point.”\n\nThe DP approach for computing “exactly-k” was indeed first proposed by [1] but we would like to reiterate our contributions. We extend the evaluation to functions of \"exactly-k\" as in the MIL setting (at least $1$ computation) and PU setting (penalizing the count distribution against a binomial via KL Divergence). Furthermore, we are the first to use it as an actual loss function.\n\n**[References]**\n\n[1] Kareem Ahmed, Zhe Zeng, Mathias Niepert, and Guy Van den Broeck. Simple: A gradient estimator for k-subset sampling. In Proceedings of the International Conference on Learning Representations (ICLR), may 2023."}, {"review_id": "DyRDoXNRpZ", "reviewer": "Reviewer_rn5b", "summary": "The paper proposes a unified approach for three problems of weak supervision: LLP, MIL, and PU learning. The approach is based on estimation of a common computational block – count probability. For its estimation, the dynamic programming method is used. The method is compared in three problem scenarios with different baselines.", "questions": "My main question is how the training algorithm actually works, and can the authors provide a pseudocode for that?", "limitations": "It would be great to see the runtime depending on the bag size, in other words is there any computational limitation to the approach related to the parameters of the problem?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Developing accurate models for learning with weak supervision (LLP, MIL) is a challenging and important problem. Different weak supervision scenarios share commonalities in their problem formulation, and this paper clearly outlines the common part, and the main bottleneck — the count probability. Having count probability estimated, one can plug it into the scenario-dependent objective.\n\nOverall, the paper is written very clearly and easy to follow, provides a good overview of weak supervision scenarios and unifies them under the same umbrella of optimization problems.\n", "weaknesses": "The main part I missed in the paper is the training algorithm. The paper describes in detail the inference part of it: given the estimations of instance-probabilities $p(y_i|x_i)$ it shows how one can compute the count probability. But what I missed is how this is used in the optimization part for training, how are the gradients propagated from the objective to the instance level? It might be straightforward, but in my opinion including the pseudocode/explanation of the training method is essential to understand the details. Without that, I failed to understand the training method, and therefore the value of the paper.\n\n----\nRaised my score after reading the rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer rn5b for the comments. We are happy that you found the paper well-written and easy to follow.\n\n**[Training Algorithm]**\n\n“My main question is how the training algorithm actually works, and can the authors provide a pseudocode for that?”\n\nLet us consider the example of LLP. As noted by the reviewer, our classifier produces $p(\\hat{y}_i = 1 |x_i)$, which for the sake of brevity we will call $p(\\hat{y}_i = 1)$. Given that we have a bag of $n$ samples and that our true count of positive samples is $k$, we want to compute: $p(\\sum_i \\hat{y}_i = k)$ using $p(\\hat{y}_i = 1)$ for all integers $i \\in [[1, n]]$. This is done via the “exactly-k” algorithm. Our goal is to *maximize this probability*. Hence, we minimize the objective: $-\\log{p(\\sum_i \\hat{y}_i = k)}$. Note that this objective is certainly *differentiable* as the DP algorithm, shown in Algorithm 1, reduces to products, sums, exponentials, and logarithms and hence, we can *backpropagate* through it.\n\nPseudocode with pytorch for LLP training:\n\n```\n# labels are the ground truth count of each bag in the batch\n# prob_pred_equals_k is oracle call to our dp algorithm, returning a log probability\ndef train():\n   for epoch in range(epochs):\n      for train_batch, labels in training_generator:\n         optimizer.zero_grad()\n         instance_predictions = model(train_batch)\n\n         batch_loss = -1*prob_pred_equals_k(instance_predictions, labels, bag_size)\n         loss = batch_loss.mean() \n\n         loss.backward()\n         optimizer.step()\n```\n\n**[Runtime Limitation]**\n\n“It would be great to see the runtime depending on the bag size, in other words is there any computational limitation to the approach related to the parameters of the problem?”\n\nThe runtime of our algorithm is vectorized $O(n)$, where $n$ is the bag size, which means that the computation linearly scales with bag size. We present some empirical results in the following table, which is for the LLP setting with the Adult dataset where $k \\in [0, \\frac{1}{2}]$.\n\n| Bag Size  |          8          |          32         |         128         |         512         |\n|-----------|:-------------------:|:-------------------:|:-------------------:|:-------------------:|\n| CL (Ours) | $0.1139 \\pm 0.0102$ | $0.1270 \\pm 0.0155$ | $0.1574 \\pm 0.0179$ | $0.4076 \\pm 0.0209$ |\n| PL        | $0.1032 \\pm 0.0119$ | $0.0981 \\pm 0.0042$ | $0.1101 \\pm 0.0726$ | $0.1069 \\pm 0.0073$ |\n\nOur baseline is proportion loss [1], which uses an approximation (mean of instance probabilities) for the probability that we compute exactly. We time over 10 epochs (getting rid of the first) and then average it over three runs. We report mean and standard deviation in seconds. We see that for bag sizes less than or equal to 128, our timing is comparable but degrades in the case of a very large bag, i.e. 512. \n\n[1] Kuen-Han Tsai and Hsuan-Tien Lin. Learning from label proportions with consistency regularization. In Asian Conference on Machine Learning, pages 513–528. PMLR, 2020.\n"}, {"review_id": "pcj2sDjw64", "reviewer": "Reviewer_YHmN", "summary": "This paper proposes a unified framework for weakly-supervised binary classificasion, where instances can be considered as bags and their weak supervision can be seen as count of positive instances in each bag.\nThe framework is based on the probability of the count and the authors derived loss functions based on it for three different weakly-supervised settings, Learning from label proportions (LLP), multiple instance learning (MLP), and Positive and unlabeled learning (PU). The direct handling count is reasonable and the information of bag size is incorporated as supervision in contrast to Proportion Loss (PL).\nExperimental results on multiple datasets demonstrated that the proposed method performs better than existing methods.", "questions": "Please see above.", "limitations": "This work focuses on binary classification, and enhancement for multi-class cases is discussed as their future work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed unified approach for count-based weakly-supervised learning is novel, and the direct handling count in their formulation is reasonable. The solution is exact, not approximation.\n\n- The paper is well-written and easy to follow.\n\n- Experimental results on multiple datasets demonstrated the effectiveness of the proposed method.", "weaknesses": "### Originality:\n- It is better to discuss concrete descriptions of how the existing work trains models.\n\n### Clarity:\n- In p.2, for the definition of a set of training data, n should be defined explicitly.\n- Table 1 should be Figure 1.\n- Table 1-a should be described in the main text.\n- In eq at l.4 from the bottom in p.5, there is a redundant bracket.\n- On p.8, it is better to clarify how to generate discrete bag sizes from the normal distribution.\n- Figures are better to place on top.\n- Positions of proposed methods are inconsistent among tables.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer YHmN for the review of our paper. We are delighted to hear that you found our solution well-written, easy to follow, and the empirical evaluation effective.\n\n**[Originality]**\n\n“It is better to discuss concrete descriptions of how the existing work trains models.”\n\nWe will make sure to have this for the camera-ready, specifically paying more attention to how the baselines we use train models. Many of the existing approaches seek to approximate what we can compute exactly. \n* Proportion Loss (PL) uses the average of instance probabilities (approximation for our computation) in a bag and then applies binary cross entropy against the ground truth proportion [1]. \n* We note that the baselines we use for MIL, Gated Attention and Attention, these are embedding space methods, which means that they lack instance level predictions [2]. Their output is a single probability, which is then penalized via binary cross entropy against the MIL label. Other instance-space approaches are noted in [2, 3] and included using the max, mean, and log-sum-exp as pooling operations to approximate the probability of “at least one positive instance”, which is then trained with binary cross entropy. Note again that these instance methods merely approximate our exact computation.\n* In PU Learning, some of our baselines include uuPU and nPU, which derive from first principles methods on how to minimize estimated empirical risk for the PU Learning task using the risk defined on the “positive risk” on positive data and “negative risk” on unlabeled data [4, 5]. They then use a series of loss functions to test their approach and optimize via gradient descent. We derive a loss directly from unlabeled data without any sort of estimation. Furthermore, the view of unlabeled as a bag annotated with the mixture proportion is very different from prior approaches.\n\n**[Clarity]**\n\nThank you for the notes on clarity, we will make the proper revisions in lieu of the camera-ready.\n\n**[References]**\n\n[1] Kuen-Han Tsai and Hsuan-Tien Lin. Learning from label proportions with consistency regularization. In Asian Conference on Machine Learning, pages 513–528. PMLR, 2020.\n\n[2] Ilse, Maximilian, Jakub Tomczak, and Max Welling. \"Attention-based deep multiple instance learning.\" International conference on machine learning. PMLR, 2018.\n\n[3] Wang, Xinggang, et al. \"Revisiting multiple instance neural networks.\" Pattern Recognition 74 (2018): 15-24.\n\n[4] Ryuichi Kiryo, Gang Niu, Marthinus C Du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator Advances in neural information processing systems, 30, 2017. 10\n\n[5] M. C. du Plessis, G. Niu, and M. Sugiyama. Analysis of learning from positive and unlabeled data. In NIPS, 2014.\n"}, {"review_id": "i59tcsvVxL", "reviewer": "Reviewer_5jbX", "summary": "The paper describes a unified loss for different weakly supervised paradigms: learning from label proportions (LLP), multiple instance learning (MIL) and learning from positive and unlabeled data (PU).\nThe main idea is to compute the probability of a count sum constraint by summing over all possible combination of events compatible with the constraint (e.g.: exactly k out of n outputs being set to true). An efficient dynamic programming algorithm is given to compute the distribution of the count. It is demonstrated empirically that the count loss can be used to train models in the mentioned weakly supervised settings.", "questions": "You defined the problem for binary classification,  how difficult would it be to generalize to multiple classes? I assume the main question is the applicability of the algorithm for this case.\n\nHow much time the loss computation and the backpropagation through the dynamics programming graph takes proportionally in the experiments. Is it significantly slower to compute than the traditional losses you compare with?\n\nPlease do not only bold numerically equal mean values as with 3 repeats there is no difference for example between 0.818 ± 0.024 and 0.807 ± 0.026 (in Table 4).  Check the significance of the results, but at least as a shortcut method bold multiple results if they are so close that their variance significantly overlaps not only if their mean precisely equal. This would considerably help the job of the reviewer and the reader.\n\nCount probability is sometimes computed exactly with probabilistic logic reasoning systems. Would be quite valuable to compare runtime with a probabilistic logic engine using tabled execution. I would execute simply a few case with high $n$ to see computational times.\nI also suggest to mention the connection with logical inference in the paper. This gives for example a \"possible world\" semantic for the sum in the objective, containing the indicator variable.\n\nNOTE: After the authors rebuttal: the clarification of the contribution. and the discussion on the logic programming solution, I raised the score by one.", "limitations": "The author acknowledges some limitations, like that it is not currently working for multi-class cases, but there are no detailed discussion on limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The unification of different weakly supervised paradigms under the count loss is a novel contribution. The dynamic programming algorithm provided make the efficient computation of the loss possible.\nThe paper is easy to follow. The three weakly supervised problems addressed by the paper in details (and potentially more, where the loss can be applied) are well researched and have many real world application.\n", "weaknesses": "In its current form the loss is defined only for binary classification problems, while alternatives like probabilistic logic based solutions are applicable to multi class settings as well.\nFor example we know that on an image (our bag) there are 5 object, 2 cats, 2 dogs, and 1 apple. In defense of the paper however, It does not seem too complicated  to extend to this case.\n\nThe novelty of the loss can be questioned. Probabilistic logic can be used to formulate this and more general losses, and this is actually used in deep learning see [1,2]. For example [1] describes the supervision of MNIST digit bags with their sum, this is clearly more general, as in binary case will give back the count loss. Naively evaluating the probabilistic program computing this probability is of course inefficient, however there are techniques (tabled execuition, memoization) to reuse results of sub-problems quite similarly to dynamic programming. I am not sure if your dynamical programming method exactly corresponds to any of the methods used in probabilistic logic programming, but claiming superiority in computational efficiency would require comparison. \n\nNote that I do not question the novelty of the unified view on LLP, MIL and PU. \n\n[1] Manhaeve, Robin, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. \"Deepproblog: Neural probabilistic logic programming.\" Advances in neural information processing systems 31 (2018).\n\n[2] Oldenhof, Martijn, Adam Arany, Yves Moreau, and Edward De Brouwer. \"Weakly Supervised Knowledge Transfer with Probabilistic Logical Reasoning for Object Detection.\" In The Eleventh International Conference on Learning Representations. 2023. (**NOTE:** this is contemporaneous with your submission, and as such you are not required to be aware of it, **I am ignoring the content of this specific paper when evaluating novelty.**) \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 5jbX for such detailed insights. We are pleased to hear that you found the paper easy to follow and the unification as a strong novelty.\n\n**[Multi-class Extension Possibility]**\n\nThe multi-class extension is certainly possible though admittedly, it comes with an exponential time trade off with respect to the number of classes. We posted pseudocode for a non vectorized, unbatched version for clarity as a proof of concept in response to reviewer jVGG.\n\n**[Loss Computation and Back Propagation Complexity + Timing]**\n\n“How much time the loss computation and the backpropagation through the dynamics programming graph takes proportionally in the experiments. Is it significantly slower to compute than the traditional losses you compare with?”\n\n| Bag Size  | 8                   | 32                  | 128                 | 512                 |\n|-----------|---------------------|---------------------|---------------------|---------------------|\n| CL (Ours) | $0.1139 \\pm 0.0102$ | $0.1270 \\pm 0.0155$ | $0.1574 \\pm 0.0179$ | $0.4076 \\pm 0.0209$ |\n| PL        | $0.1032 \\pm 0.0119$ | $0.0981 \\pm 0.0042$ | $0.1101 \\pm 0.0726$ | $0.1069 \\pm 0.0073$ |\n\nNote that the table's units are in seconds.\n\nWe present empirical timing results for the LLP setting (Adult with $k \\in [0, \\frac{1}{2}]$) against a baseline PL (proportion loss) [4]. We time over 10 epochs (getting rid of the first) and then average it over three runs. We report mean and standard deviation We observe that for bag sizes less than or equal to 128, our timing is very comparable. We know that our algorithm’s computation scales with bag size, which accounts for the performance of 512. Hence, we demonstrate that in actual training scenarios, with moderate bag sizes, our algorithm can be trained at comparable efficiency to current approaches.\n\n**[Result Highlighting]**\n\n“Please do not only bold numerically equal mean values as with 3 repeats there is no difference for example between 0.818 ± 0.024 and 0.807 ± 0.026 (in Table 4). Check the significance of the results, but at least as a shortcut method bold multiple results if they are so close that their variance significantly overlaps not only if their mean precisely equal. This would considerably help the job of the reviewer and the reader.”\n\nThank you for the suggestion. We will include this in our camera-ready submission. Note that the results we presented for instance-level classification in our rebuttal pdf Table $1$ and Table $2$ does this.\n\n**[Probabilistic Logic Engine and DeepProbLog]**\n\n“The novelty of the loss can be questioned. Probabilistic logic can be used to formulate this and more general losses, and this is actually used in deep learning see [1,2]. For example [1] describes the supervision of MNIST digit bags with their sum, this is clearly more general, as in binary case will give back the count loss. Naively evaluating the probabilistic program computing this probability is of course inefficient, however there are techniques (tabled execuition, memoization) to reuse results of sub-problems quite similarly to dynamic programming. I am not sure if your dynamical programming method exactly corresponds to any of the methods used in probabilistic logic programming, but claiming superiority in computational efficiency would require comparison.”\n\nWe agree that knowledge compilers, such as the SDD library underlying deepproblog, can handle arbitrary constraints specified in propositional logic. Such compilers take in as input a logical sentence in propositional logic, and output a target form that enables the tractable computation of certain probabilistic queries e.g. the probability of the constraint. Note, however, that such target forms might themselves be intractable—they are worst case exponential in the treewidth of the input logical formula, as is the case with MNIST addition, which does not scale to much more than 2 digits.\n\n[1] show the target form for the exactly-k constraint is tractable. In fact, the algorithm presented therein, and echoed in our paper, corresponds to a structured d-DNNF with a right-linear vtree with a vectorized complexity of $O(n)$, which can be further improved to a vectorized complexity of $O(\\log{(n)} \\log{(k)})$.\n\nIn this paper our contribution is framing a class of weakly-supervised learning problems in terms of the simple yet principled problem of satisfying some count loss; showing that not only can we compute the probability of the constraint tractably, but also symmetric functions thereof e.g.  $\\geq k$ or at $\\leq k$; and providing the empirical evidence for the merits of the approach. It is our view that, our approach subsuming the MNIST addition example, in retrospect, should count as a positive and not a negative. \n\n**[Limitations]**\n\nWe refer the reviewer to Appendix C for a discussion on more limitations.\n\n**[References]**\n\n[1] Kareem Ahmed, Zhe Zeng, Mathias Niepert, and Guy Van den Broeck. Simple: A gradient estimator for k-subset sampling. In Proceedings of the International Conference on Learning Representations (ICLR), may 2023.\n\n[2] Manhaeve, Robin, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. \"Deepproblog: Neural probabilistic logic programming.\" Advances in neural information processing systems 31 (2018).\n\n[3] Xu, Jingyi, et al. \"A semantic loss function for deep learning with symbolic knowledge.\" International conference on machine learning. PMLR, 2018.\n\n[4] Kuen-Han Tsai and Hsuan-Tien Lin. Learning from label proportions with consistency regularization. In Asian Conference on Machine Learning, pages 513–528. PMLR, 2020.\n"}]

Author rebuttal:
Thank you all for your reviews and insights!

**[Novelty]**

While we do acknowledge that [3] showcases the “exactly k” dynamic programming algorithm we employ, our novelty lies in the *unified view* of weakly supervised learning for *count-based* settings. We are the first to leverage the dynamic programming algorithm as a loss function to train models end to end. We also extend the applicability of this loss to *functions* of “exactly-k”. This is seen in the construction of the MIL objective function, which computes the probability of at least $1$ positive instance in a bag. Furthermore, in our PU learning approach, we penalize the KL Divergence between the count distribution produced by the dynamic programming algorithm to the ground truth binomial distribution.

**[Related Work]**

One concern brought up by many of the reviewers was the Related Works section.

We will add a segment on additional weakly supervised learning settings, incorporating descriptions and citations for the following settings:

**Weakly Supervised Settings:**
* Semi-Supervised Learning: Semi-supervised learning is a close relative to PU Learning with the difference being that labeled samples can be both positive and negative [7].
* Label Noise Learning: Label-noise learning derives from a common real-life scenario: mislabeled instances [11]. There are many variations but two common ones involve whether label noise is independent or dependent on instances [2].
* Partial Label Learning: In partial label learning, each instance is provided a set of labels of which exactly one is true [1].

(Note that we believe that some of these settings could potentially utilize our “exactly-k” approach but this is a task for future work to explore.)

We will also add the following to the **Count Loss** section:
In MIL settings, among instance level classifiers, there are also several ways of approximating the bag posterior. These include mean, max, and log-sum-exp pooling to approximate the likelihood that a bag has *at least one positive instance* [4]. But again, these are all *approximations* of what our "at least $1$" computation does exactly. In PU Learning, to our best knowledge, the view of unlabeled data as a bag annotated with the mixture proportion is novel and yet to be considered.

In the **Unified Approaches** section, we will add information on other approaches:
Co-Training and Self-Training are examples of similar techniques that are applicable to a wide variety of weakly supervised settings [5, 6]. Self-Training involves progressively incorporating more unlabeled data via our model’s prediction (with pseudo-label) and then training a model on more data as an iterative algorithm [11]. Co-Training leverages two models that have different “views” of the data and iteratively augment each other's training set with samples they deem as “well-classified”. They are both traditionally applied to semi-supervised learning tasks but can also extend to multiple instance learning settings [9, 10, 12].

**[Multi-Class Classification]**

Multi-Class classification is certainly possible with our methodology. However, the computation scales exponentially with the number of  classes. This is something we hope to explore in future work.

**[Instance-Level Classification MIL]**

We provide compelling instance-level classification results as part of our rebuttal pdf in Table 1 and Table 2.

**[References]**

[1] Timothee Cour, Ben Sapp, and Ben Taskar. 2011. Learning from Partial Labels. J. Mach. Learn. Res. 12, null (2/1/2011), 1501–1536.

[2] Song, Hwanjun, et al. "Learning from noisy labels with deep neural networks: A survey." IEEE Transactions on Neural Networks and Learning Systems (2022).

[3] Kareem Ahmed, Zhe Zeng, Mathias Niepert, and Guy Van den Broeck. Simple: A gradient estimator for k-subset sampling. In Proceedings of the International Conference on Learning Representations (ICLR), may 2023.

[4] Wang, Xinggang, et al. "Revisiting multiple instance neural networks." Pattern Recognition 74 (2018): 15-24.

[5] Avrim Blum and Tom Mitchell. 1998. Combining labeled and unlabeled data with co-training. In Proceedings of the eleventh annual conference on Computational learning theory (COLT' 98). Association for Computing Machinery, New York, NY, USA, 92–100. https://doi.org/10.1145/279943.279962

[6] David Yarowsky. 1995. Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of the 33rd annual meeting on Association for Computational Linguistics (ACL '95). Association for Computational Linguistics, USA, 189–196. https://doi.org/10.3115/981658.981684

[7] X. Zhu and A.B. Goldberg. Introduction to semi-supervised learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 3(1):1–130, 2009.

[8] Xie, Ming-Kun, and Sheng-Jun Huang. "Partial multi-label learning." Proceedings of the AAAI conference on artificial intelligence. Vol. 32. No. 1. 2018.

[9] H. Lu, Q. Zhou, D. Wang and R. Xiang, "A co-training framework for visual tracking with multiple instance learning," 2011 IEEE International Conference on Automatic Face & Gesture Recognition (FG), Santa Barbara, CA, USA, 2011, pp. 539-544, doi: 10.1109/FG.2011.5771455.

[10] Sun, S. A survey of multi-view machine learning. Neural Comput & Applic 23, 2031–2038 (2013). https://doi.org/10.1007/s00521-013-1362-6

[11] Karamanolakis, Giannis, et al. "Self-training with weak supervision." arXiv preprint arXiv:2104.05514 (2021).

[12] Liu, Kangning, et al. "Multiple instance learning via iterative self-paced supervised contrastive learning." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023.

Meta-review: This paper proposes a unified framework for learning in three weakly supervised settings: learning from label proportions, multiple instance learning, ad positive-unlabeled learning. The paper refers to these settings as count-based learning because the maximum likelihood learning in all these cases can be defined in terms of the probability of exactly k out of n random variables being true. The paper shows this computation is differentiable and can be used to efficiently express learning across the three settings. Experiments show that this unified approach is competitive with state of the art methods developed specifically for each of these settings.

The reviewers saw benefits of having a unified approach to these problems that have been studied separately. They also found the experimental results convincing that the approach works well. During the discussion phase, the reviewers made several suggestions that the authors are strongly encouraged to take into account for the final version. First, the reviewers provided additional citations and connections to the areas of related work. Discussing them will strengthen the paper. Second, multiple reviewers found the details of the training algorithms for the various methods unclear. These should be clarified in the final version.
Decision: Accept (poster)