A Unified Approach to Count-Based Weakly-Supervised Learning

Vinay Shukla 1 Zhe Zeng * 1 Kareem Ahmed * 1 Guy Van den Broeck 1

Abstract

positive labels in a bag. A key insight that we bring forth isthat such weak supervision can very often be construed as
enforcing constraints on label counts of data.

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 overa set of instances. In this paper, we develop aunified approach to learning from such weaklylabeled data, which we call count-based weaklysupervised learning. At the heart of our approachis 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. We evaluate ourapproach on 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.

More concretely, we consider three prominent weakly supervised learning paradigms. The first paradigm is known
as learning from label proportions (Quadrianto et al., 2008).
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 in such a bag. The second
paradigm, whose supervision is strictly weaker than the former, is multiple instance learning (Maron & Lozano-Pérez,1997; Dietterich et al., 2001). Here the bag labels only indicate the existence of at least one positive instance in abag, which can be recast as to whether the count of positive
instances is greater than zero. The third paradigm, learningfrom positive and unlabeled data (De Comité et al., 1999;
Letouzey et al., 2000), grants access to the ground truthlabels for a subset of only the positive instances, providing
only a class prior for what remains. We can recast the classprior as a distribution of the count of positive labels.
Leveraging the view of weak supervision as a constraint onlabel counts, we utilize a simple, efficient and probabilistically sound approach to weakly-supervised learning. Moreprecisely, 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 thelabel counts; a loss which is surprisingly tractable. Compared to prior methods, this approach does not approximate
probabilities but computes them exactly. Our empiricalevaluation demonstrates that our proposed count loss significantly boosts the classification performance on all three
aforementioned settings.

1. Introduction
Weakly supervised learning (Zhou, 2018) enables a model tolearn from data with restricted, partial or inaccurate labels,
often known as weakly-labeled data. Weakly supervised
learning fulfills a need arising in many real-world settings
that are subject to privacy or budget constraints, such as privacy sensitive data (Wojtusiak et al., 2011), medical image
analysis (Bortsova et al., 2018), clinical practice (Quellec
et al.), personalized advertisement (Bekker & Davis, 2020)and knowledge base completion (Galárraga et al., 2015; Zupanc & Davis, 2018), to name a few. In all such settings,
instance-level labels are unavailable. Instead, instances aregrouped into bags with corresponding bag-level labels thatare a function of the instance labels, e.g., the proportion of

2. Problem Formulations
Notations. Let X ∈ Rd be the input space over d features,
Y = {0, 1} be a binary label space, and x ∈ X and y ∈ Y
be the input and output random variables respectively.

*

Equal contribution 1 Department of Computer Science, University of Los Angeles, Los Angeles, United States. Correspondence to: Vinay Shukla <vshukla@g.ucla.edu>, Zhe Zeng<zhezeng@cs.ucla.edu>, Kareem Ahmed <ahmedk@cs.ucla.edu>,
Guy Van den Broeck <guyvdb@cs.ucla.edu>.

2.1. Classical Binary Classification
In fully-supervised binary classification, it is assumed thateach feature and label pair (x, y) ∈ X × Y is sampled inde-

Published at the Differentiable Almost Everything Workshop of the
40 th International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

1A Unified Approach to Count-Based Weakly-Supervised Learning

Table 1: Three weakly supervised settings, Learning from Label Proportions (Section 2.2), Multiple Instance Learning(Section 2.3) and Positive and Unlabeled learning (Section 2.4), against the classical fully supervised setting (Section 2.1)
for binary classification, using digits from the MNIST dataset.
xy{xi }ki=1

0
0

ỹ =

P

{xi }ki=1

yi /kỹ = max{yi }

ỹ

0

0

?

1/3

1

1

3/5

1

1

?

1
(a) Classicalx?
(b) Learning from Label Proportions(c) Multiple Instance Learningpendently from a joint distribution p(x, y). A classifier f islearned to minimize the risk R(f ) = E(x,y)∼p [ℓ(f (x), y)],where ℓ : Y × Y → R≥0 is the loss function. We define a
set of training data D = {(xi , yi )}ni=1 , where the empiricalPnloss is minimized as R̂(f ) = n1 i=1 ℓ(f (xi ), yi ).

(d) Positive Unlabeled Learning

MIL, the training dataset consists of m bags, denoted by
D = {(Bi , ỹi )}m
i=1 , with a bag consisting of k instances,i.e., Bi = {xj }kj=1 . The size k can vary among different
bags. For each instance xj , there exists an instance-level label yj which is not accessible. The bag-level label is definedas ỹi = maxj {yj }. An example is shown in Figure 1c.

2.2. Learning from Label Proportions

The main goal of MIL is to learn a model that predicts a baglabel while a more challenging goal is to learn an instancelevel predictor that is able to discover positive instances ina bag. In this work, we aim to tackle both by training an
instance-level classifier whose predictions can be combined
into a bag level prediction as the last step.

Learning from label proportions (LLP) (Quadrianto et al.,2008) assumes that each instance in the training set is assigned to bags and only the proportion of positive instancesin each bag is known. One example is in light of the pandemic, where infection rates were typically reported basedon geographical boundaries such as states and counties.
Each boundary can be treated as a bag with the infection
rate as the proportion annotation.

2.4. Learning from Positive and Unlabeled Data
Learning from positive and unlabeled data or PU learning (De Comité et al., 1999; Letouzey et al., 2000) refers
to the setting where the training dataset consists of only
positive instances and unlabeled data, and the unlabeleddata can contain both positive and negative instances. A
motivation of PU learning is persistence in the case of shifts
to the negative-class distribution (Plessis et al., 2015), forexample, a spam filter. An attacker may alter the propertiesof a spam email, making a traditional classifier require a
new negative dataset (Plessis et al., 2015). We note thattaking a new unlabeled sample would be more efficient, motivating PU learning. Formally, in PU learning, the training
np
dataset D = Dp ∪ Du where Dp = {(xi , ỹi = 1)}i=1
isthe set of positive instances with xi from p(x | y = 1)
and ỹ denoting whether the instance is labeled, and Du =u{(xi , ỹi = 0)}ni=1
the unlabeled set with xi fromThe goal of LLP is to learn an instance-level classifier f :X → Y even though it is trained on bag-level labeled data.
Formally, the training dataset consists of m bags, denotedkby D = {(Bi , ỹi )}m
i=1 where each bag Bi = {xj }j=1
consist of k instances and this k could vary among different
Pkbags. The bag proportions are defined as ỹi = j=1 yj /kwith yj being the instance label that cannot be accessedand only ỹi is available during training. An example isshown in Figure 1b. We do not assume that the bags are
non-overlapping while some existing work suffer from thislimitation including Scott & Zhang (2020).
2.3. Multiple Instance Learning
Multiple instance learning (MIL) (Maron & Lozano-Pérez,1997; Dietterich et al., 2001) 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 isa single binary label indicating whether there is a positive
instance in the bag or not as opposed to a bag proportion
defined in LLP. A real-world application of MIL lies in thefield of drug activity (Dietterich et al., 2001). We can observe the effects of a group of conformations but not for any
specific molecule, motivating a MIL setting. Formally, inpu (x) = β p(x | y = 1) + (1 − β) p(x | y = 0),(1)

where the mixture proportion β := p(y = 1 | ỹ = 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 labelỹ: if the selection label ỹ = 1, it belongs to the positively
labeled set, i.e., p(y = 1 | ỹ = 1) = 1; otherwise, theinstance x can be either positive or negative. An example
2

A Unified Approach to Count-Based Weakly-Supervised Learning

Table 2: A summary of the labels and objective functions for all the settings considered in the paper.
TASK

L ABELclassical fully supervised

binary yPi yi /k

L ABEL L EVELO BJECTIVE

instance level−y log p(y) − (1 − y) log(1 − p(y))
P− log p( ŷi = k ỹ)PP−ỹ log p( ŷi ≥ 1) − (1 − ỹ) log p( i ŷi = 0)PP1) DKL (p( i ŷi ) ∥ Bin(k, β)); 2) − log p( ŷi = kβ)learning from label proportion

continuous ỹ =multiple instance learning

binary ỹ = max{yi }bag levellearning from PU data

binary ỹ

instance level

bag level

ciples can be solved by using the count probability as an
oracle, which we summarize in Table 2.

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 andit is necessary to make assumptions to enable learning withpositive and unlabeled data (Bekker & Davis, 2020). In
this work, we make a commonly-used assumption for PU
learning, selected completely at random (SCAR), which liesat the basis of many PU learning methods.
Definition 2.1 (SCAR). Labeled instances are selected completely at random, independent from input x and the positive
distribution, i.e., p(ỹ = 1 | x, y = 1) = p(ỹ = 1 | y = 1).

LLP setting. Given a bag B = {xi }ki=1 and its bag-label ỹ,by definition, it can be inferred that the number of positive
instances (count) in the bag
P is k ỹ. Our objective is to maximize the probability p( i ŷi = k ỹ). In practice, the loss
is defined in the log space for numerical stability. We also
perform risk analysis with details in Appendix.
MIL setting. Given a bag B = {xi }ki=1 of size k anda single binary label ỹ as its weakly supervised label, we
propose a cross-entropy loss as below
X
Xℓ(B, ỹ) = −ỹ log p(ŷi ≥ 1)−(1−ỹ) log p(ŷi = 0).

3. A Unified Approach: Count Loss
We aim to derive objectives for the three weakly supervised
settings from first principles. We propose to 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. They can be easily integrated
with deep learning models and allow end-to-end training.

P
In the above loss, the probability term p( ŷi = 0) can beobtained via the oracle
P for computing count probability andthe othertermp(ŷi ≥ 1) can simply be obtained fromP
1 − p( ŷi = 0), i.e., the same call to the oracle.

PU Learning setting. Recall that for the unlabeled data Du
in the training dataset, an unlabeled instance xi is drawn
from a mixture distribution as shown in Equation 1 parameterized by a mixture proportion β = p(y = 1 | ỹ = 0).

For the three objectives, we show that they share the same
computational building block: given k instances {xi }ki=1
and an instance-level classifier f that predicts p(ŷi | xi )with ŷ being the prediction, inferring the probability of thePkcount constraint i=1 ŷi = s is to compute
p(

k
P

i=1

ŷi = s | {xi }ki=1 ) :=

P

J

k
P

ŷ∈Y k i=1

ŷi = sKk
Q

i=1

Proposition 3.2. With SCAR assumption and a class prior,the mixture proportion β can be estimated from dataset D.
The probabilistic semantic of the mixture proportion is that,
if we randomly draw an instance xi from the unlabeled population, the probability that the true label yi is positive would
be β. Further, if we randomly draw k instances, the distribuPktion of the summation of the true labels i=1 yi conforms toa binomial distribution Bin(k, β) parameterized by the mixPkture proportion β, i.e., p( i=1 yi = s) = ks β s (1−β)k−s .
Based on this observation, we propose an objective to minimize the KL divergence between the distribution of predicted label sum and the binomial distribution parameterized
by the mixture proportion, that is,!
kXŷi ) ∥ Bin(k, β) =DKL p(p(ŷi | xi )where J·K denotes the indicator function and ŷ denotes thevector (ŷ1 , · · · , ŷk ). For succinctness, we omit the dependency on the input and simply write the count probabilityPk
as p( i=1 ŷi = s). Intractable as it seems, we show that it
is indeed possible to derive a tractable computation for thecount probability based on Ahmed et al. (2023b).
Pk
Proposition 3.1. The count probability p( i=1 ŷi = s)of sampling k prediction variables with summation
Qk beings from an unconstrained distribution p(y) = i=1 p(ŷi )can be computed exactly in time O(ks). Moreover, the set
Pk{p( i=1 ŷi = s)}ks=0 can also be computed in time O(k 2 ).

i=1

k
X

Next, we show how the objectives derived from first prin-

s=0

3

p(

k
X
i=1

ŷi = s) log

Pkp( i=1 ŷi = s)Bin(s; k, β)A Unified Approach to Count-Based Weakly-Supervised Learning

Table 3: LLP results showing test AUC with standard deviation aggregated over 5 trials for each experimental setting.
DatasetDist

Method

8

32

128

512

Adult
Adult
Adult

[0, 12 ][0, 12 ][0, 12 ]CL (Ours)
PL
LMMCM

0.8984 ± 0.0013
0.8889 ± 0.0024
0.8728 ± 0.0019

0.8848 ± 0.0041
0.8782 ± 0.0036
0.8693 ± 0.0047

0.8743 ± 0.0052
0.8743 ± 0.0039
0.8669 ± 0.0041

0.8703 ± 0.0070
0.8678 ± 0.0085
0.8674 ± 0.0040

Adult
Adult
Adult

[ 21 , 1][ 12 , 1][ 12 , 1]

CL (Ours)
PL
LMMCM

0.8854 ± 0.0022
0.8781 ± 0.0038
0.8584 ± 0.0164

0.8738 ± 0.0039
0.8731 ± 0.0035
0.8644 ± 0.0052

0.8675 ± 0.0043
0.8699 ± 0.0057
0.8601 ± 0.0045

0.8607 ± 0.0056
0.8556 ± 0.0180
0.8500 ± 0.0186

Table 4: MIL experiment on MNIST dataset. Each block represents a different distribution from which we draw bag
sizes—First Block: N (10, 2), Second Block: N (50, 10), Third Block: N (100, 20).
Training Bags

50

100

150

200

300

400

500

Gated Attention
Attention
CL (Ours)

0.775 ± 0.034
0.807 ± 0.026
0.818 ± 0.024

0.894 ± 0.012
0.913 ± 0.006
0.906 ± 0.009

0.935 ± 0.005
0.940 ± 0.004
0.929 ± 0.005

0.939 ± 0.006
0.942 ± 0.007
0.946 ± 0.001

0.963 ± 0.002
0.957 ± 0.002
0.952 ± 0.004

0.959 ± 0.002
0.961 ± 0.005
0.962 ± 0.002

0.966 ± 0.003
0.965 ± 0.004
0.963 ± 0.002

Gated Attention
Attention
CL (Ours)

0.943 ± 0.005
0.936 ± 0.010
0.939 ± 0.010

0.949 ± 0.009
0.962 ± 0.006
0.960 ± 0.002

0.970 ± 0.005
0.970 ± 0.001
0.964 ± 0.007

0.977 ± 0.001
0.977 ± 0.002
0.972 ± 0.002

0.983 ± 0.002
0.981 ± 0.002
0.982 ± 0.003

0.986 ± 0.004
0.987 ± 0.001
0.982 ± 0.001

0.987 ± 0.002
0.987 ± 0.002
0.987 ± 0.002

Gated Attention
Attention
CL (Ours)

0.975 ± 0.003
0.984 ± 0.001
0.981 ± 0.007

0.981 ± 0.004
0.982 ± 0.001
0.989 ± 0.000

0.992 ± 0.002
0.996 ± 0.000
0.996 ± 0.002

0.987 ± 0.004
0.987 ± 0.007
0.995 ± 0.001

0.996 ± 0.001
0.992 ± 0.004
0.996 ± 0.002

0.998 ± 0.001
0.994 ± 0.002
0.993 ± 0.003

0.990 ± 0.004
0.998 ± 0.000
0.999 ± 0.001

formly on [ 12 , 1]. We experiment on four bag sizes n withn ∈ {8, 32, 128, 512}. We compare our approach CL with
LMMCM from (Scott & Zhang, 2020) and against Proportion Loss (PL)(Tsai & Lin, 2020) with results in Table 3,
where CL showcases superior results against the baselines.

Table 5: PU Learning results on acccuracy.
Dataset

CL (Ours)

CVIR

nnPU

nPU

Binarized MNISTMNIST17Binarized CIFAR
Cat vs. Dog

96.4 ± 0.01
99.0 ± 0.19
80.1 ± 0.34
74.8 ± 1.64

96.3 ± 0.07
98.7 ± 0.09
82.3 ± 0.18
73.3 ± 0.94

96.1 ± 0.14
98.4 ± 0.20
77.2 ± 1.03
71.8 ± 0.33

95.2 ± 0.19
98.4 ± 0.09
76.7 ± 0.74
68.8 ± 0.53

MIL. We experiment on the MNIST dataset (LeCun, 1998)
and follow the setting in Ilse et al. (2018): the training andtest set bags are randomly sampled from MNIST; each bag
can have images of digits from 0 to 9, and bags with digit
9 are labeled positive. The task is to train a classifier thatis 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 9. The number of bags in training
set n is in {50, 100, 150, 200, 300, 400, 500}. We include
the Attention and Gated Attention mechanism (Ilse et al.,2018) as baselines. Results are shown in Table 4, where CL
is able to outperform all other baselines or exhibit highly
comparable performance for bag-level predictions.

where Bin(s; k, β) denotes the probability mass functionof the binomial distribution Bin(k, β). Again, the KL divergence can be obtained by k + 1 calls to the oracle forPkcomputing count probability p( i=1 ŷi = s). The KL divergence is further combined with a cross entropy definedover labeled data Dp as in the classical binary classification
as the overall objective. As an alternative, we propose an
objective for the unlabeled data that requires fewer calls
to the oracle: matching only the expectations of the two
Pk
distributions, that is, to maximize p( i=1 ŷi = kβ) wherekβ is the expectation of the binomial distribution Bin(k, β).

PU Learning. We experiment on MNIST (LeCun, 1998)
and CIFAR-10 (Krizhevsky & Hinton, 2009), following thefour simulated settings from Garg et al. (2021). The performance is evaluated using the accuracy on a test set of
unlabeled data. We compare our proposed CL using the firstobjective in Table 2 with baseline Conditional Value Ignoring Risk approach (CVIR) (Garg et al., 2021), nnPU (Kiryo
et al., 2017), and uPU (Plessis et al., 2015). Results areshown in Table 5, where our CL perform better than baselines on 3 out of the 4 simulated PU learning settings.

4. Experiments
We present a thorough empirical evaluation of our proposed
count loss (CL) on the three tasks, LLP, MIL and PU learning respectively, with additional results in Appendix.
LLP. We experiment on datasets 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. We follow the experimental settings from Scott& Zhang (2020) where two settings are considered: one
with label proportions uniformly on [0, 21 ] and the other uni4

A Unified Approach to Count-Based Weakly-Supervised Learning

Acknowledgments

integration. In Proceedings of IJCAI, pp. 2770–2776,
2015a.

This work was funded in part by the DARPA Perceptuallyenabled Task Guidance (PTG) Program under contract
number HR00112220005, NSF grants #IIS-1943641, #IIS1956441, #CCF-1837129, Samsung, CISCO, a Sloan Fellowship, and a gift from RelationalAI. GVdB discloses afinancial interest in RelationalAI. ZZ is supported by an
Amazon Doctoral Student Fellowship.

Belle, V., Van den Broeck, G., and Passerini, A. Hashingbased approximate probabilistic inference in hybrid domains. In Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (UAI), 2015b.
Bortsova, G., Dubost, F., Ørting, S., Katramados, I.,
Hogeweg, L., Thomsen, L., Wille, M., and de Bruijne,
M. Deep learning from label proportions for emphysema
quantification. In Medical Image Computing and Computer Assisted Intervention–MICCAI 2018: 21st International Conference, Granada, Spain, September 16-20,
2018, Proceedings, Part II 11, pp. 768–776. Springer,
2018.

References
Ahmed, K., Wang, E., Chang, K.-W., and Van den Broeck,
G. Leveraging unlabeled data for entity-relation extraction through probabilistic constraint satisfaction, mar
2021.

Carbonneau, M.-A., Cheplygina, V., Granger, E., andGagnon, G. Multiple instance learning: A survey ofproblem characteristics and applications. Pattern Recognition, 2018.

Ahmed, K., Li, T., Ton, T., Guo, Q., Chang, K.-W., Kordjamshidi, P., Srikumar, V., Van den Broeck, G., andSingh, S. Pylon: A pytorch framework for learning withconstraints. In Proceedings of the 36th AAAI Conferenceon Artificial Intelligence (Demo Track), feb 2022a.

De Comité, F., Denis, F., Gilleron, R., and Letouzey, F.
Positive and unlabeled examples help learning. pp. 219–
230, 12 1999. ISBN 978-3-540-66748-3. doi: 10.1007/
3-540-46769-6_18.

Ahmed, K., Teso, S., Chang, K.-W., Van den Broeck, G.,
and Vergari, A. Semantic probabilistic layers for neurosymbolic learning. In Advances in Neural Information
Processing Systems 35 (NeurIPS), dec 2022b.

Dietterich, T., Lathrop, R., and Lozano-Pérez, T. Solving themultiple instance problem with axis-parallel rectangles.
Artificial Intelligence, 89:31–71, 03 2001. doi: 10.1016/
S0004-3702(96)00034-3.

Ahmed, K., Wang, E., Chang, K.-W., and den Broeck, G. V.
Neuro-symbolic entropy regularization. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022c.

du Plessis, M. C., Niu, G., and Sugiyama, M. Analysis oflearning from positive and unlabeled data. In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N., andWeinberger, K. (eds.), Advances in Neural Information
Processing Systems, volume 27. Curran Associates, Inc.,
2014.

Ahmed, K., Chang, K.-W., and Van den Broeck, G. Semantic strengthening of neuro-symbolic learning. In Proceedings of the 26th International Conference on Artificial
Intelligence and Statistics (AISTATS), apr 2023a.
Ahmed, K., Zeng, Z., Niepert, M., and Van den Broeck, G.
Simple: A gradient estimator for k-subset sampling. In
Proceedings of the International Conference on Learning
Representations (ICLR), may 2023b.

Dua, D. and Graff, C. UCI machine learning repository,
2017. URL http://archive.ics.uci.edu/ml.
Galárraga, L., Teflioudi, C., Hose, K., and Suchanek, F. M.
Fast rule mining in ontological knowledge bases withamie++. The VLDB Journal, 24(6):707–730, 2015.

Andrews, S., Tsochantaridis, I., and Hofmann, T. Support
vector machines for multiple-instance learning. In NIPS,
2002.

Garg, S., Wu, Y., Smola, A. J., Balakrishnan, S., and Lipton, Z. Mixture proportion estimation and pu learning:a modern approach. Advances in Neural Information
Processing Systems, 34:8532–8544, 2021.

Ardehaly, E. M. and Culotta, A. Co-training for demographic classification using deep learning from label
proportions. In 2017 IEEE International Conferenceon Data Mining Workshops (ICDMW), pp. 1017–1024.
IEEE, 2017.

Hüllermeier, E. Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss
minimization. International Journal of Approximate Reasoning, 55(7):1519–1534, 2014.

Bekker, J. and Davis, J. Learning from positive and unlabeled data: A survey. Machine Learning, 109:719–760,
2020.

Ilse, M., Tomczak, J., and Welling, M. Attention-based deep
multiple instance learning. In International conferenceon machine learning, pp. 2127–2136. PMLR, 2018.

Belle, V., Passerini, A., and Van den Broeck, G. Probabilistic inference in hybrid domains by weighted model5

A Unified Approach to Count-Based Weakly-Supervised Learning

Kiryo, R., Niu, G., Du Plessis, M. C., and Sugiyama, M.
Positive-unlabeled learning with non-negative risk estimator. Advances in neural information processing systems,
30, 2017.

learning for detection and classification of nuclei inroutine colon cancer histology images. IEEE Transactions on Medical Imaging, 35:1–1, 02 2016. doi:
10.1109/TMI.2016.2525803.

Kobayashi, R., Mukuta, Y., and Harada, T. Risk consistent multi-class learning from label proportions. arXiv
preprint arXiv:2203.12836, 2022.

Tsai, K.-H. and Lin, H.-T. Learning from label proportions
with consistency regularization. In Asian Conference on
Machine Learning, pp. 513–528. PMLR, 2020.

Kolb, S., Morettin, P., Zuidberg Dos Martires, P., Sommavilla, F., Passerini, A., Sebastiani, R., and De Raedt, L.
The pywmi framework and toolbox for probabilistic inference using weighted model integration. In Proceedingsof the Twenty-Eighth International Joint Conference on
Artificial Intelligence, IJCAI, pp. 6530–6532, 7 2019. doi:
10.24963/ijcai.2019/946.

Wang, X., Yan, Y., Tang, P., Bai, X., and Liu, W. Revisiting
multiple instance neural networks. Pattern Recognition,
74:15–24, 2018.
Wojtusiak, J., Irvin, K., Birerdinc, A., and Baranova, A. V.
Using published medical results and non-homogenous
data in rule learning. In 2011 10th International Conference on Machine Learning and Applications and Workshops, volume 2, pp. 84–89. IEEE, 2011.

Krizhevsky, A. and Hinton, G. Learning multiple layers offeatures from tiny images. Technical Report 0, Universityof Toronto, Toronto, Ontario, 2009.

Xu, J., Zhang, Z., Friedman, T., Liang, Y., and Van den
Broeck, G. A semantic loss function for deep learningwith symbolic knowledge. In International conferenceon machine learning, pp. 5502–5511. PMLR, 2018.

LeCun, Y. The mnist database of handwritten digits. 1998.
Letouzey, F., Denis, F., and Gilleron, R. Learning From
Positive and Unlabeled examples. In Proceedings ofthe 11th International Conference on Algorithmic Learning Theory, ALT’00, pp. 71–85, Sydney, Australia, 2000.
Springer Verlag.

Yu, F. X., Choromanski, K., Kumar, S., Jebara, T., andChang, S.-F. On learning from label proportions. arXiv
preprint arXiv:1402.5902, 2014.
Zeng, Z. and Broeck, G. V. d. Collapsed inference forbayesian deep learning. arXiv preprint arXiv:2306.09686,
2023.

Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T.,
and De Raedt, L. Deepproblog: Neural probabilistic logic
programming. In NeurIPS, 2018.

Zeng, Z. and Van den Broeck, G. Efficient search-based
weighted model integration. Proceedings of UAI, 2019.

Maron, O. and Lozano-Pérez, T. A framework for multipleinstance learning. In Jordan, M., Kearns, M., and Solla,
S. (eds.), Advances in Neural Information Processing
Systems, volume 10. MIT Press, 1997.

Zeng, Z., Morettin, P., Yan, F., Vergari, A., and Broeck,
G. V. d. Scaling up hybrid probabilistic inference withlogical and arithmetic constraints via message passing. In
Proceedings of the International Conference of Machine
Learning (ICML), 2020a.

Plessis, M. D., Niu, G., and Sugiyama, M. Convex formulation for learning from positive and unlabeled data.
In Proceedings of the 32nd International Conference on
Machine Learning, volume 37, 2015.

Zeng, Z., Morettin, P., Yan, F., Vergari, A., and Van den
Broeck, G. Probabilistic inference with algebraic constraints: Theoretical limits and practical approximations.
Advances in Neural Information Processing Systems, 33:
11564–11575, 2020b.

Quadrianto, N., Smola, A., Caetano, T., and Le, Q. Estimating labels from label proportions. 2008.
Quellec, G., Cazuguel, G., Cochener, B., and Lamard, M.
Multiple-instance learning for medical image and video
analysis. IEEE reviews in biomedical engineering.

Zeng, Z., Morettin, P., Yan, F., Vergari, A., and Van den
Broeck, G. Is parameter learning via weighted model integration tractable? In Proceedings of the UAI Workshop
on Tractable Probabilistic Modeling (TPM), jul 2021.

Scott, C. and Zhang, J. Learning from label proportions:
A mutual contamination framework. In Larochelle, H.,
Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.),
Advances in Neural Information Processing Systems, volume 33, pp. 22256–22267. Curran Associates, Inc., 2020.

Zhou, Z.-H. A brief introduction to weakly supervised
learning. National science review, 5(1):44–53, 2018.
Zupanc, K. and Davis, J. Estimating rule quality for knowledge base completion with the relationship between coverage assumption. In Proceedings of the 2018 World Wide
Web Conference, pp. 1073–1081, 2018.

Sirinukunwattana, K., Raza, S. e. A., Tsang, Y., Snead,D., Cree, I., and Rajpoot, N. Locality sensitive deep6

A Unified Approach to Count-Based Weakly-Supervised Learning

A. Related Workniques (Risk Estimators) as they are considered state of theart and relevant to us as baselines. The Unbiased Risk Estimator (uPU), which was originally proposed in du Plessis
et al. (2014) and covered in Plessis et al. (2015), provides
an alternative to the inefficiencies in manually biasing unlabeled data. And later, Non-negative Risk Estimator (nnPU)
Kiryo et al. (2017) accounted for weaknesses in the unbiased
risk estimator.

Unified Approaches. Although not common, there exists
some literature in regards to general approaches for weakly
supervised learning. One example being the method proposed in Hüllermeier (2014), which provides a procedurethat minimizes the empirical risk on "fuzzy" sets of data.
The paper also establishes guarantees for model identification and instance level recognition.

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 integrationof hard symbolic constraints into the learning of neuralnetworks. This can take the form of enforcing a hard constraint (Ahmed et al., 2022b), whereby the network’s predictions are guaranteed to satisfy the pre-specified constraints.
Or it can take the form of a soft constraint (Xu et al., 2018;
Manhaeve et al., 2018; Ahmed et al., 2021; 2022c;a; 2023a)
whereby the network is trained with an additional loss termthat penalizes the network for placing any probability mass
on predictions that violate the constraint. While in this work
we focus on discrete constraints defined over binary variables, there are existing work focusing on hybrid constraints
defined over both discrete and continuous variables andtheir tractability (Belle et al., 2015b;a; Zeng et al., 2021;
2020b). The development of inference algorithms for such
constraints and their applications such as Bayesian deeplearning remain an active topic (Zeng & Van den Broeck,2019; Kolb et al., 2019; Zeng et al., 2020a; Zeng & Broeck,2023).

Count Loss. The idea of computing the posterior of abag is not a new concept for tackling weakly supervised
learning—specifically for LLP. Many approaches have tried
to approximate the bag posterior through averaging the instances in a bag Ardehaly & Culotta (2017); Tsai & Lin(2020). This computation is not exact and can be considereda heuristic estimate of our approach. However, it is certainly worth mentioning as they are motivated by the same
principle.
LLP. Quadrianto et al. (2008) first introduced an exponential family based approach that used an estimation of meanfor each class. Others seek to minimize “empirical proportion risk” or EPR as in Yu et al. (2014), which is centeredaround creating an instance level classifier that is able toreproduce the label proportions of each bag. As mentioned
previously, more recent methods such as the work describedin Ardehaly & Culotta (2017); Tsai & Lin (2020) use bag
posterior approximation and neural based approaches. One
such method is Proportion Loss (PL) (Tsai & Lin, 2020),
which we contrast to our approach. This is computed bybinary cross entropy between the averaged instance levelprobabilities and ground-truth bag proportion.

B. Tractable Computation of Count
Probability

MIL. MIL finds some its earlier approaches with SVMs,
which have been use quite prolifically and still remain oneof the most common baselines. We start with MI-SVM/miSVM(Andrews et al., 2002) which are examples of transductive SVMs (Carbonneau et al., 2018) that seek a stableinstance classification through repeated retraining iterations.
MI-SVM is an example of an instance space method (Carbonneau et al., 2018), which identifies methods that classify
instances as a preliminary step in the problem. This is incontrast to bag-space or embedded-space methods that omit
the instance classification step. We then look toward Wanget al. (2018) which remains one of the hallmarks for the useof neural networks for Multi-Instance Learning. In Ilse et al.
(2018), they utilized a similar approach but with Attention
based mechanisms.

Algorithm 1 Count Probability p(

Pk

i=1 ŷi = s)A set of k log probabilities {ti }ki=1 with ti

Input::=
log p(yi = 1), the number of instances k, and a label sum s
Pk
Output: log probability log p( i=1 ŷi = s) or a set of log
Pkprobability {log p( i=1 ŷi = s)}ks=0
Pi// A[i, m] = log p( j=1 yj = m) ∀i, m
Initialize an array A
Pto0 be −Inf everywhere
A[0, 0] = 0 // p( j=1 yj = 0) = 1
Compute t′i ← log1mexp(ti ) // log p(yi = 0)
for i = 1 to k dofor m = 0 to s do
a+ = A[i − 1, m − 1] + ti
a− = A[i − 1, m] + t′i
A[i, m] = logsumexp(a+ , a− )end forend forreturn A[k, s] or A[k, :]PU learning. Bekker & Davis (2020) groups PU Learning paradigms into three main classes: two step, biased,
and class prior incorporation. Biased Learning techniques
train a classifier on the entire dataset with the understandingthat negative samples are subject to noise Bekker & Davis(2020). We will focus on a subset of biased learning tech7

A Unified Approach to Count-Based Weakly-Supervised Learning
s

0

i

1

1

0

p (y1= 0)1

p (y1= 0) = 0.9
p (y2= 0)22Count loss (CL) denotes our proposed approach using
the loss objective defined in Table 2 for LLP. We compare our approach with the method from Learning from
(Scott & Zhang, 2020) or LMMCM and against Proportion
Loss (PL)(Tsai & Lin, 2020).

2

p (y1= 1)

p (y1= 1) = 0.1
p (y2= 1)

p (y2= 0)

p (y2= 1)2

p ( yi = 0) = 0.72
i=1

p (y = 0)2

p ( yi = 1) = 0.26

p ( yi = 2) = 0.02

p (y = 1)

p (y = 1)i=1p (y = 0)

Results and Discussion. We show our full results in Table
6. On almost every setting, our method showcases superior results against the baselines. This indicates CL is able
to learn instance-level classification especially on settings
where we have bags of small sizes, since bag-level information is closer to full supervision. We also empiricallyvalidate that techniques that approximate the bag posterior (PL) are less effective than optimizing the exact bag
posterior with CL.

i=1

p (y = 0)

Figure 1: An example of how to compute the count probability in a dynamic programming manner. Assume thatan instance-level classifier predicts three instances to havep(y1 = 1) = 0.1, p(y2 = 1) = 0.2, and p(y3 = 1) = 0.3
respectively. The algorithm starts from the top-left cell andpropagates
the results down right. A cell has P
its probabilityPi
i−1p( j=0 yj = s) computed by inputs from p( j=0 yj = s)Pi−1weighted by p(yi = 0), and p( j=0 yj = s − 1) weighted
by p(yi = 1) respectively, as indicated by the arrows.
Pk
We show that the count probability p( i=1 ŷi = s) can becomputed in a dynamic programming manner. We provide an illustrative example of this computation in Figure 1. In practice, we implement this computation in log
space for numeric stability which we summarized as Algorithm 1, where function log1mexp provides a numericallystable way to compute log1mexp(x) = log(1 − exp(x))
and function logsumexp a numerically stable way to compute logsumexp(x, y) = log(exp(x) + exp(y)). Notice that since we show it is tractable to compute the set
Pk{p( i=1 ŷi = s)}ks=0 , for any two
Pgiven label sum s1 ands2 , a count probability p(s1 ≤i yi ) ≤ s2 ) where thecount takes its form as an interval, can also be exactly andtractably computed. This implies that our tractable computation of count probabilities can potentially be leveragedby other count-based applications besides the three weakly
supervised learning settings in the last section.

C.2. MIL
We first experiment on the MNIST dataset (LeCun, 1998)
and follow the MIL experimental setting in Ilse et al. (2018):
the training and test set bags are randomly sampled from
the MNIST training and test set respectively; each bag canhave images of digits from 0 to 9, and bags with digit 9
are labeled positive. Moreover, the dataset is constructedin a balanced way such that there is an equal amountof positively and negatively labeled bags as in Ilse et al.
(2018). The task is to 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 9. Following Ilse et al. (2018), we consider three settings that vary in bag generation process:in each setting, bags have their sizes generated from anormal distribution being N (10, 2), N (50, 10), N (100, 20)
respectively. The number of bags in training set n is in{50, 100, 150, 200, 300, 400, 500}. Thus, we have 3 × 7 =21 settings in total. Additionally, we introduce experimental
analysis on how 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
to be {10, 20, 30, 40} and selecting bag sizes from N (5, 1)
and N (10, 2).

C. Additional Experiment Analysis
C.1. LLP
In addition to Adult, we experiment on Magic Gamma Ray
Telescope with 6144 training samples where the task is topredict whether the electromagnetic shower is caused byprimary gammas or not given information from the atmospheric Cherenkov gamma telescope (Dua & Graff, 2017).

We also experiment on the Colon Cancer dataset (Sirinukunwattana et al., 2016) to simulate a setting where bag instances are not independent. The dataset consists of 100
total H&E stained images, each of which contain images ofcell nuclei that are classified as one of: epithelial, inflammatory, fibroblast, and miscellaneous. Each image represents
a bag and instances are 27 × 27 patches extracted from theoriginal image. A positively labeled bag or image is one
that contains the epithelial nuclei.

We follow the experimental settings from Scott & Zhang(2020) where two settings are considered: one with label
proportions uniformly on [0, 21 ] and the other uniformly
on [ 12 , 1]. Additionally, we experiment on a third settingwith label proportions distributing uniformly on [0, 1] which
is not considered in Scott & Zhang (2020) but is the mostnatural setting since the label proportion is not biased towardeither 0 or 1. We experiment on four bag sizes n withn ∈ {8, 32, 128, 512}.

For both datasets, we include the Attention and Gated Attention mechanism (Ilse et al., 2018) as baselines. We also
use the MIL objective defined in Table 2.
8

A Unified Approach to Count-Based Weakly-Supervised Learning

Table 6: LLP results showing test AUC with standard deviation aggregated over 5 trials for each experimental setting. ∗represents experiments that we ran with no early stopping. We highlight the highest test AUC. Full table for Table 3.
DatasetDist

Method

8

32

128

512

Adult
Adult
Adult

CL (Ours)
PL
LMMCM

0.8984 ± 0.0013
0.8889 ± 0.0024
0.8728 ± 0.0019

0.8848 ± 0.0041
0.8782 ± 0.0036
0.8693 ± 0.0047

0.8743 ± 0.0052
0.8743 ± 0.0039
0.8669 ± 0.0041

0.8703 ± 0.0070
0.8678 ± 0.0085
0.8674 ± 0.0040

Adult
Adult
Adult

[0, 12 ][0, 12 ][0, 21 ][ 12 , 1][ 12 , 1][ 21 , 1]

CL (Ours)
PL
LMMCM

0.8854 ± 0.0022
0.8781 ± 0.0038
0.8584 ± 0.0164

0.8738 ± 0.0039
0.8731 ± 0.0035
0.8644 ± 0.0052

0.8675 ± 0.0043
0.8699 ± 0.0057
0.8601 ± 0.0045

0.8607 ± 0.0056
0.8556 ± 0.0180
0.8500 ± 0.0186

Adult
Adult
Adult

[0, 1][0, 1][0, 1]CL (Ours)
PL
LMMCM

0.8985 ± 0.0010
0.8884 ± 0.0030
0.8831 ± 0.0026

0.8891 ± 0.0013
0.8884 ± 0.0008
0.8819 ± 0.0006

0.8871 ± 0.0021
0.8879 ± 0.0025
0.8821 ± 0.0017

0.8790 ± 0.0056
0.8828 ± 0.0051
0.8786 ± 0.0052

Magic
Magic
Magic

[0, 12 ][0, 21 ][0, 21 ]CL (Ours)
PL
LMMCM

0.9088 ± 0.0056
0.8900 ± 0.0095
0.8918 ± 0.0077

0.8830 ± 0.0097
0.8510 ± 0.0032
0.8799 ± 0.0113

0.8926 ± 0.0049
0.8405 ± 0.0110
0.8753 ± 0.0157∗0.8864 ± 0.0107
0.8332 ± 0.0149
0.8734 ± 0.0092

Magic
Magic
Magic

[ 12 , 1][ 21 , 1][ 21 , 1]

CL (Ours)
PL
LMMCM

0.9105 ± 0.0020
0.9066 ± 0.0016
0.8911 ± 0.0083

0.8980 ± 0.0059
0.8818 ± 0.0108
0.8790 ± 0.0091

0.8851 ± 0.0255
0.8769 ± 0.0101
0.8684 ± 0.0046∗0.8816 ± 0.0083
0.8429 ± 0.0443
0.8567 ± 0.0292

Magic
Magic
Magic

[0, 1][0, 1][0, 1]CL (Ours)
PL
LMMCM

0.9173 ± 0.0018
0.9039 ± 0.0029
0.9070 ± 0.0026

0.9102 ± 0.0057
0.8870 ± 0.0037
0.9048 ± 0.0058

0.9146 ± 0.0051
0.9002 ± 0.0092
0.9113 ± 0.0058

0.9088 ± 0.0039
0.8807 ± 0.0200
0.8934 ± 0.0097

Table 7: MIL: We report mean test accuracy, AUC, F1, precision, and recall averaged over 5 runs with std. error on theColon Cancer dataset. Highlighted are the highest mean values for each metric.
MethodAccuracy

AUC

F1

Precision

RecallGated Attention
Attention

0.909 ± 0.014
0.893 ± 0.015

0.908 ± 0.013
0.890 ± 0.008

0.886 ± 0.021
0.876 ± 0.017

0.916 ± 0.020
0.908 ± 0.016

0.879 ± 0.020
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

Results and Discussion. For the MNIST experiments, CL
is able to outperform all other baselines or exhibit highly
comparable performance for bag-level predictions as shownin Table 4. A more interesting setting is to compare how
robust the learning methods are if the number of training
bags decrease. Wang et al. (2018) claims that instance-levelclassifiers tend to lose against embedding based methods.
However, we show in our experiment that this is actually
not true in all cases as seen in Figure 2. While Attention
and Gated Attention are based on embedding, they sufferfrom a more severe drop in predictive performance than CL
when the number of training bags drops from 40 to 10; ourmethod shows great robustness and consistently outperforms
all baselines. The rationale we provide is that with lower
number of training instances, we need more supervision overthe limited samples we have. Our constraint provides thisadditional supervision, which accounts for the difference inperformance.

can see that even though the classifier is trained on feedback
about whether a bag contains the digit 9 or not, it accurately
discover all images of digit 9.
Our experimental results on the Colon Cancer dataset are
shown in Table 7. We show that both our proposed objectives are able to consistently outperform baseline methodson all metrics. Interestingly, we do not expect CL perform
well when instances in a bag are dependent; however, theresults indicate that our count loss is robust to these settings.
C.3. PUWe experiment on dataset MNIST and CIFAR-10(Krizhevsky & Hinton, 2009), following the four simulated
settings from Garg et al. (2021): 1) Binarized MNIST: thetraining set consist of images of digits 0−9 and images withdigits in range [0, 4] is defined as positive instances whileothers as negative; 2) MNIST17: the training set consist ofimages of digits 1 and 7 and images with digits 1 is defined
as positive while 7 as negative; 3) Binarized CIFAR: thetraining set consist of images from ten classes and images
from the first five classes is defined as positive instances

We provide an exemplary investigation in Figure 3 to showthat our approach learns effectively and delivers accurate
instance-level predictions under bag-level supervision. We

9A Unified Approach to Count-Based Weakly-Supervised Learning

Figure 2: MIL MNIST dataset experiments with decreased training bags and lower bag size. Left: bag lengths samples fromN (10, 2); Right: bag lengths sampled from N (5, 1). We plot the mean test AUC (aggregated over 3 trials) with standard
error for 4 bag sizes. Best viewed in color.

< 10−60.9997 < 10−6 < 10−6 6×10−6 < 10−6 < 10−6

< 10−6< 10−6< 10−6< 10−61.0000

proposed count loss effectively guides the classifier towards
predicting a binomial distribution as shown in Figure 4: weplot the count distributions predicted by CL and CVIR aswell as the ground-truth binomial distribution. We can seethat the CL is able to generate a count distribution close to
the ground truth while the baseline approach does not.

< 10−6

Figure 3: A test bag from our MIL experiments, where weset only the digit 9 as a positive instance. Bag sizes are
distributed as N (10, 2), and we use 500 training bags (seeTable 4 for details). Highlighted in red are digits identified
to be positive with corresponding probability beneath.
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 isevaluated using the accuracy on a test set of unlabeled data.
As shown in Table 2, we propose two objectives for
PU learning. Our first objective is denoted by CL
whereas the second approach is denoted by CL-expect.
We compare against Conditional Value Ignoring Risk approach (CVIR) (Garg et al., 2021), nnPU (Kiryo et al., 2017),
and uPU (Plessis et al., 2015).

Figure 4: MNIST17 setting for PU Learning: We computethe average discrete distribution for CL and CVIR, a strong
baseline over 5 test bags, each of which contains 100 instances. A ground truth binomial distribution of counts is
also shown.

Results and Discussion. Complete accuracy results arepresented in Table 8 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 asimilar “exactly-k” count approach, which we have shown
to work well in the label proportion setting. The moreinteresting results are from CL where we fully leverage theinformation from a distribution as supervision instead ofsimply using the expectation. We think of this as applying aloss on each count weighted by their probabilities from thebinomial distribution. We provide further evidence that our

D. Proofs
Proposition 3.2 With SCAR assumption and a class prior,the mixture proportion β can be estimated from dataset D.

Proof. Given a class prior p(y = 1) denoted by α, the label
frequency p(ỹ = 1 | y = 1) denoted by c can be obtained10

A Unified Approach to Count-Based Weakly-Supervised Learning

Table 8: PU Learning: We report accuracy and standard deviation on a test set of unlabeled data, which is aggregated over 3
runs. We highlight the method with the highest mean accuracy. Results from CVIR, nnPU, and uPU are aggregated over 10
epochs, as defined in Garg et al. (2021), while we choose the single best epoch based on validation for our approaches. Thisis the full table for Table 5.
DatasetNetwork

CL-expect (Ours)

CL (Ours)

CVIR

nnPU

nPU

Binarized MNISTMNIST17Binarized CIFAR
CIFAR Cat vs. Dog

MLP
MLP
ResNetResNet95.9 ± 0.15
98.7 ± 0.17
79.2 ± 0.27
76.5 ± 1.86

96.4 ± 0.01
99.0 ± 0.19
80.1 ± 0.34
74.8 ± 1.64

96.3 ± 0.07
98.7 ± 0.09
82.3 ± 0.18
73.3 ± 0.94

96.1 ± 0.14
98.4 ± 0.20
77.2 ± 1.03
71.8 ± 0.33

95.2 ± 0.19
98.4 ± 0.09
76.7 ± 0.74
68.8 ± 0.53

by

We notice that the weight term attached to the loss can befurther rewritten as a constrained probability as follows,
QkkX
j=1 p(yj | xj )yj = ỹ, xk )
=
p(y
|
Qk
P
′ |x )
p(y
j
j
j=1
j=1
P

c = p(ỹ = 1 | y = 1)p(ỹ = 1, y = 1)p(y = 1)p(ỹ = 1), (by the definition of PU learning)=p(y = 1)=y ′ ∈Y k ,This allows us to further rewritePthe risk Rrc with likelihoodkloss being ℓ(f (xk ), y) = −p( j=1 yj = k ỹ | xk ):that is, c = p(ỹ = 1)/α. Notice that p(ỹ = 1) can be
estimated from the dataset D by counting the proportion of
the labeled instances. Further, we can obtain the mixture
proportion as below,

1
Rrc (f ) =E kk(k + 1) p(x ,ỹ)


k
k
X
X
X
−
yj = k ỹ | xk )
yj = k ỹ, xk )p(p(y |β = p(y = 1 | ỹ = 0)p(y = 1, ỹ = 0)p(ỹ = 0)p(y = 1)p(ỹ = 0 | y = 1)=
1 − p(ỹ = 1)p(y = 1)(1 − p(ỹ = 1 | y = 1))=
1 − p(ỹ = 1)α(1 − c).
=1 − p(ỹ = 1)

=

y∈Y k

j=1

j=1




k
X
X
1
=
E k −p(y,yj = k ỹ | xk )
k(k + 1) p(x ,ỹ)
k
j=1
y∈Y


k
X
1
yj = k ỹ | xk )
E k −p(=k(k + 1) p(x ,ỹ)
j=1=

1
E k [ℓ(f (xk ), y)] = Rllp (f )k(k + 1) p(x ,ỹ)The last few lines follow from the definition of conditional
probabilities. This shows that the risk Rrc (f ) = Rllp (f ),meaning that the reduction from risk Rrc (f ) to the classicalrisk R(f ) in Kobayashi et al. (2022) is applicable to our risk
estimator Rllp , which proves that our learning method is
risk-consistent.

Lemma D.1. Let Rllp be our risk estimator defined over1
Ep(xk ,ỹ) [ℓ(f (x), y)]. Followp(x, ỹ) as Rllp (f ) = k(k+1)
ing the assumptions in Section 3.1 from Kobayashi et al.
(2022), our proposed method is risk-consistent.
Proof. In Kobayashi et al. (2022), it is shown that the risk R
in classical multi-class classification as shown in Section 2.1
can be reduced to a risk Rrc over p(xk , ỹ k ) as shown inEquation 1 in Kobayashi et al. (2022) under certain assumptions.

Proposition D.2. Assume that the loss function ℓ(f (x), y)is ρ-Lipschitz with respect to f (x) for any y ∈ Y boundedby some constant. Let fllp be the hypothesis that minimizes∗
the empirical risk, and fllp
is the hypothesis that minimizes∗
the true risk, then fllp converges to fllp
as m → ∞.

Consider binary classification and follow our notations, werewrite the Equation 1 in Kobayashi et al. (2022) as below,

Proof. This claim immediately follows Lemma D.1, where
we shows that Rrc (f ) = Rllp (f ). Therefore, it holds that
Rllp (fˆ) − Rllp (f ∗ ) = R(sc) (fˆ) − R(sc) (f ∗ ), where thelatter term, an always positive term, is shown in Theorem 3.1
in√ Kobayashi et al. (2022) that it converges to 0 at rate
m.

1
E k
k(k + 1) p(x ,ỹ)QkX
j=1 p(yj | xj )ℓ(f (xk ), y)QkP′ |x )
p(y
j
j
j=1
y∈Y k
P

Rrc (f ) =y ′ ∈Y k ,′j yj =ỹ′j yj =ỹ11

A Unified Approach to Count-Based Weakly-Supervised Learning

Pk
Proposition 3.1 The count probability p( i=1 ŷi = s)of sampling k prediction variables with summation
Qk beings from an unconstrained distribution p(y) = i=1 p(ŷi )can be computed exactly in time O(ks). Moreover, thePk
set {p( i=1 ŷi = s)}ks=0 can also be computed in timeO(k 2 ).

set number of warm epochs for our experiments. All parameters were obtained by using a holdout of 12.5% of training
data for validation on the [0, 1] uniform setting. The network shown in Table 10 was also obtained grid search on
this same validation set.
Table 10: Network used for Adult dataset in LLP Experiments.

Pk
Proof. The claim that p( i=1 ŷi = s) can be computed
exactly in time O(ks) follows immediately from Proposition 1 in Ahmed et al. (2023b): in Ahmed et al. (2023b),
the unconstrained distribution is a factorized distribution
obtained from k outputs from a single neural network model
while in our case, the unconstrained distribution p(y) is
obtained from applying a classifier that gives a single output
p(yi ) on k inputs; the constructive proof of Proposition 1
in Ahmed et al. (2023b) still applies in our case. MorePkover, the computation of p( i=1 ŷi = k) is done in a
dynamic programming manner in the sense that for any
Pks < k, p( i=1 ŷi = s) is an intermediate result for comPk
puting p( i=1 ŷi = k). By caching the intermediate result,Pk
the set {p( i=1 ŷi = s)}ks=0 can be obtained by the timePkp( i=1 ŷi = k) is computed, which finishes our proof.

8
32
128
512

1024
256
64
16

768
192
48
12

fc - 2048 + ReLU
fc - 64 + ReLU
fc - 1 + logsigmoid

E.1.2. M AGIC DATASET

Table 9: Illustration of Adult and Magic datasets showing
the number of training bags for each bag size. Note that wetest on the same number of instances in all variations of bag
size for both experiments: 16280 for Adult and 3804 for
Magic. The breakdown of training bags is the same acrossall distributions of label proportion as well, i.e., [0, 12 ], [ 21 , 1],[0, 1].
Training Bags Magic

1
2
3

Computing Resources. Trained on Intel(R) Xeon(R)CPU E5-2640 v4 @ 2.40GHzU and AMD EPYC 7313P
16-Core Processor CPU.

In this section, we will provide relevant training details as
it relates to each of our settings including hyperparametersand dataset details.

Training Bags AdultType

Training Procedure. For CL, we use the parameters andnetwork described in the previous paragraph and early stopping criterion based on validation loss from a held out validation set (12.5% of training data). For PL, we use theparameters and network except that we do not use L1 as
we found this improves performance. We also use an early
stopping criterion based on validation loss from a held out
validation set (12.5% of training data).

E. Experimental Setup Details

Bag Size

Layer

Hyperparameters. We use a learning rate of 0.0001 with
the Adam Optimizer and β1 = 0.9, β2 = 0.999. The weightdecay value is set to 0.001. We also notice that adding in
L1 regularization of 0.001 improved the performance of our
method. We train for 10000 epochs and use a set numberof warm epochs for our experiments. All parameters wereobtained by using a holdout of 12.5% of training data forvalidation on the [0, 1] uniform setting. The network shownin Table 11 was also obtained grid search on this same
validation set.
Table 11: Network used for Magic dataset in LLP Experiments.

E.1. Label Proportion

Layer

Type

1
2

fc - 2048 + ReLU
fc - 1 + logsigmoid

E.1.1. A DULT DATASETHyperparameters. We use a learning rate of 0.00001
with the Adam Optimizer and β1 = 0.9, β2 = 0.999. The
weight decay value is set to 0.001. We also notice that
adding in L1 regularization of 0.001 improved the performance of our method. We train for 10000 epochs and use aTraining Procedure. For CL, we use the parameters andnetwork described in the previous paragraph and early stopping criterion based on validation loss from a held out validation set (12.5% of training data). For PL, we use the12A Unified Approach to Count-Based Weakly-Supervised Learningparameters and network except that we do not use L1 regularization as we found this improves performance. We also
use an early stopping criterion based on validation loss froma held out validation set (12.5% of training data). As shownin Table 6, there are two instances where we reran our results with no validation set. In these experiments, we onlyuse 87.5% of training data and ran for a fixed number of
epochs: 2000. This is because with only one validation bag,we can find ourselves with some instability in the training
procedure. Note that PL did not benefit from rerunning withthis method.

Instance Pooling. To pool together instance level classification at the final stage, there are several operations thathave been considered in the literature. Some include using
the max and mean operator (Wang et al., 2018). We propose
a new method based on our constraint. We compute therelevant probabilities defined in 3 for the MIL setting. Morespecifically, we compute the probability that a bag has atleast one positive instance. We then round the probability of at least one positive instance to obtain our bag levelclassification.
Computing Resources. Trained on AMD EPYC 7313P
16-Core Processor CPU.

Computing Resources. Trained on Intel(R) Xeon(R)CPU E5-2640 v4 @ 2.40GHzU and AMD EPYC 7313P
16-Core Processor CPU.

E.2.2. C OLON C ANCER DATASETHyperparameters. We derive our set of hyperparametersfrom Ilse et al. (2018). We use the Adam optimizer for all experiments with β1 = 0.9, β2 = 0.999. This includes weightdecay of 0.0005, learning rate of 0.0001, and a maximumof 100 epochs.

E.2. Multi-Instance Learning
E.2.1. MNIST-BAGS
Hyperparameters. All of our hyperparameters derivefrom Ilse et al. (2018). This includes using the Adam optimizer with β1 = 0.9, β2 = 0.999, a learning rate of 0.0005,
weight decay of 0.0001, and max epochs of 200. For themain experiment, we use a validation holdout of 20% tofind a class weight for balancing the loss on positive bags
versus negative bags. (We omit this step for our limited dataexperiments.)

Table 13: MIL: Network used for CL in colon cancer dataset.
Derived from the same network shown in Ilse et al. (2018).

Table 12: Network used for all MNIST experiments in MIL
settings. Derived from the same network shown in Ilse et al.
(2018).
Layer

Type

1
2
3
4
5
6

conv(5, 1, 0) - 20 + ReLU
maxpool(2, 2)conv(5, 1, 0) - 50 + ReLU
maxpool(2, 2)
fc-500 + ReLU
fc-1 + logsigmoid

Layer

Type

1
2
3
4
5
6
7
8
9

conv(4, 1, 0) - 36 + ReLU
maxpool(2, 2)conv(3, 1, 0) - 48 + ReLU
maxpool(2, 2)
fc-512 + ReLU
dropout
fc - 512 + ReLU
dropout
fc-2 + logsigmoid

Training Procedure. We perform 10-fold crossvalidation and average the mean value of each metric over
5 seeds. For CL, we do not use early stopping and train
on all data for the maximum number of epochs using thehyperparameters mentioned in the previous paragraph. For
our baselines, Attention and Gated-Attention, we use thesame hyperparameters as mentioned above. However, wefollow the optimization procedure detailed in Ilse et al.
(2018) to give try and reproduce the results given in thepaper. This involves using a held out validation set for early
stopping with validation loss + error as the stopping criteria.
For this experiment, this validation set is assumed to be thesize of 1 fold or one-ninth of the training data. (We find that
including early stopping helps increase performance forboth baselines.)

Training Procedure. For CL, we train on all the training
data for the maximum number of iterations: 200. We also
use all of the hyperparameters described in the last paragraph and Ilse et al. (2018). Because we were unable to reproduce the values in Ilse et al. (2018) for the Attention and
Gated Attention mechanisms, we reran their experimentswith our own implementation. To try and reproduce theirresults, we follow their optimization procedure. Specifically,
we use a holdout of training data (20%) and validation loss
+ error for early stopping. We found that doing so provided
the best values for Attention and Gated Attention.
13

A Unified Approach to Count-Based Weakly-Supervised Learning

Computing Resources. Trained on NVIDIA RTX A6000
GPU.

except for CL-expect in the CIFAR Cat vs. Dog setting
where we use 0.001. We use a validation set with size equal
to 10% of training data in order to weigh the loss on positive
data versus loss on unlabeled data.

E.3. PU Learning
E.3.1. MNIST DATASET

Training Procedure. We use a ResNet-18 architecture
for all CIFAR experiments. We train CL and CL-expectwith the hyperparameters defined in the previous paragraph.
Furthermore, we use a held out validation set, equivalent to
10% of training data, for early stopping. While as results in
Garg et al. (2021) are aggregated over 10 epochs, we choose
to pick a single epoch as this makes the most sense for our
optimization technique.

Table 14: Network used for MNIST data in PU Learning
experiments. Resembles the network in Garg et al. (2021)
except we replace the last layer with a single output andlogsigmoid instead of softmax.
Layer

Type

1
2
3
4

fc - 5000 + ReLU
fc - 5000 + ReLU
fc - 50 + ReLU
fc-1 + logsigmoid

Computing Resources.
2080-Ti GPU.

Trained on a singular NVIDIA

E.3.3. E ARLY S TOPPINGThe early stopping procedure that we used in our experiments was a bit unique. Using our holdout of validation
data, we do early stopping using the proximity to the classprior and validation loss to break ties. We can imagine that
if we perfectly identify all positive and unlabeled samples
and then calculate accuracy against the actually provided labels, we would get an accuracy equivalent to the class prior.
This is because all the positive samples in the unlabeled set
would be labeled incorrect.

Hyperparameters. We fix weight decay to be 0.0005 andAdam optimizer for all experiments with β1 = 0.9, β2 =0.999. We use a learning rate of 0.0001 and train for a
maximum of 2000 epochs in all experiments for both CL
and CL-expect. We use a validation set with size equal to
10% of training data in order to weigh the loss on positive
data versus loss on unlabeled data.
Training Procedure. For MNIST dataset experiments, weuse a fully connected multi-layer perceptron (MLP) definedin Table 14. We train CL and CL-expect with the hyperparameters defined in the previous paragraph. Furthermore,
we use a held out validation set, equivalent to 10% of training data, for early stopping. While as results in Garg et al.
(2021) are aggregated over 10 epochs, we choose to pick asingle epoch based on our early stopping as this makes themost sense for our optimization technique.
Computing Resources.
RTX 2080-Ti GPU.

Trained on a singular NVIDIA

Table 15: Table taken almost directly from Garg et al. (2021).
Table shows the break down of the various simulated PU
datasets that we train on.
Dataset

CIFAR
MNIST

Simulated PU Dataset

P vs N

Binarized CIFAR
CIFAR Cat vs. Dog
Binarized MNISTMNIST-17[0 − 4] vs. [5 − 9]
3 vs. 5[0 − 4] vs. [5 − 9]
1 vs. 7

Training
Positive Unlabeled
12500
3000
15000
3000

12500
3000
15000
3000

Test
Unlabeled
2500
500
2500
500

E.3.2. CIFAR DATASET.
Hyperparameters. We fix weight decay to be 0.0005 andAdam optimizer for all experiments with β1 = 0.9, β2 =0.999. We use a learning rate of 0.0001 for all experiments
14