WEAKLY SUPERVISED CLUSTERING BY EXPLOITING UNIQUE CLASS COUNT
Year: 2020

Abstract:
A weakly supervised learning based clustering framework is proposed in this paper. As the core of this framework, we introduce a novel multiple instance learning task based on a bag level label called unique class count (ucc), which is the number of unique classes among all instances inside the bag. In this task, no annotations on individual instances inside the bag are needed during training of the models. We mathematically prove that with a perfect ucc classifier, perfect clustering of individual instances inside the bags is possible even when no annotations on individual instances are given during training. We have constructed a neural network based ucc classifier and experimentally shown that the clustering performance of our framework with our weakly supervised ucc classifier is comparable to that of fully supervised learning models where labels for all instances are known. Furthermore, we have tested the applicability of our framework to a real world task of semantic segmentation of breast cancer metastases in histological lymph node sections and shown that the performance of our weakly supervised framework is comparable to the performance of a fully supervised Unet model.

text: A weakly supervised learning based clustering framework is proposed in this paper. As the core of this framework, we introduce a novel multiple instance learning task based on a bag level label called unique class count (ucc), which is the number of unique classes among all instances inside the bag. In this task, no annotations on individual instances inside the bag are needed during training of the models. We mathematically prove that with a perfect ucc classifier, perfect clustering of individual instances inside the bags is possible even when no annotations on individual instances are given during training. We have constructed a neural network based ucc classifier and experimentally shown that the clustering performance of our framework with our weakly supervised ucc classifier is comparable to that of fully supervised learning models where labels for all instances are known. Furthermore, we have tested the applicability of our framework to a real world task of semantic segmentation of breast cancer metastases in histological lymph node sections and shown that the performance of our weakly supervised framework is comparable to the performance of a fully supervised Unet model.

heading: 1 INTRODUCTION
text: In machine learning, there are two main learning tasks on two ends of scale bar: unsupervised learning and supervised learning. Generally, performance of supervised models is better than that of unsupervised models since the mapping between data and associated labels is provided explicitly in supervised learning. This performance advantage of supervised learning requires a lot of labelled data, which is expensive. Any other learning tasks reside in between these two tasks, so are their performances. Weakly supervised learning is an example of such tasks. There are three types of supervision in weakly supervised learning: incomplete, inexact and inaccurate supervision. Multiple instance learning (MIL) is a special type of weakly supervised learning and a typical example of inexact supervision (Zhou, 2017). In MIL, data consists of bags of instances and their corresponding bag level labels. Although the labels are somehow related to instances inside the bags, the instances are not explicitly labeled. In traditional MIL, given the bags and corresponding bag level labels, task is to learn the mapping between bags and labels while the goal is to predict labels of unseen bags (Dietterich et al., 1997; Foulds & Frank, 2010).
In this paper, we explore the feasibility of finding out labels of individual instances inside the bags only given the bag level labels, i.e. there is no individual instance level labels. One important application of this task is semantic segmentation of breast cancer metastases in histological lymph node sections, which is a crucial step in staging of breast cancer (Brierley et al., 2016). In this task, each pathology image of a lymph node section is a bag and each pixel inside that image is an instance. Then, given the bag level label that whether the image contains metastases or not, the task is to label each pixel as either metastases or normal. This task can be achieved by asking experts to exhaustively annotate each metastases region in each image. However, this exhaustive annotation process is tedious, time consuming and more importantly not a part of clinical workflow.
In many complex systems, such as in many types of cancers, measurements can only be obtained at coarse level (bag level), but information at fine level (individual instance level) is of paramount importance. To achieve this, we propose a weakly supervised learning based clustering framework. Given a dataset consisting of instances with unknown labels, our ultimate objective is to cluster the instances in this dataset. To achieve this objective, we introduce a novel MIL task based on a new kind of bag level label called unique class count (ucc), which is the number of unique classes or the number of clusters among all the instances inside the bag. We organize the dataset into non-empty bags, where each bag is a subset of individual instances from this dataset. Each bag is associated with a bag level ucc label. Then, our MIL task is to learn mapping between the bags and their associated bag level ucc labels and then to predict the ucc labels of unseen bags. We mathematically show that a ucc classifier trained on this task can be used to perform unsupervised clustering on individual instances in the dataset. Intuitively, for a ucc classifier to count the number of unique classes in a bag, it has to first learn discriminant features for underlying classes. Then, it can group the features obtained from the bag and count the number of groups, so the number of unique classes.
Our weakly supervised clustering framework is illustrated in Figure 1. It consists of a neural network based ucc classifier, which is called as Unique Class Count (UCC) model, and an unsupervised clustering branch. The UCC model accepts any bag of instances as input and uses ucc labels for supervised training. Then, the trained UCC model is used as a feature extractor and unsupervised clustering is performed on the extracted features of individual instances inside the bags in the clustering branch. One application of our framework is the semantic segmentation of breast cancer metastases in lymph node sections (see Figure 4). The problem can be formulated as follows. The input is a set of images. Each image (bag) has a label of ucc1 (image is fully normal or fully metastases) or ucc2 (image is a mixture of normal and metastases). Our aim is to segment the pixels (instances) in the image into normal and metastases. A UCC model can be trained to predict ucc labels of individual images in a fully supervised manner; and the trained model can be used to extract features of pixels (intances) inside the images (bags). Then, semantic segmentation masks can be obtained by unsupervised clustering of the pixels (each is represented by the extracted features) into two clusters (metastases or normal). Note that ucc does not directly provide an exact label for each individual instance. Therefore, our framework is a weakly supervised clustering framework.
Finally, we have constructed ucc classifiers and experimentally shown that clustering performance of our framework with our ucc classifiers is better than the performance of unsupervised models and comparable to performance of fully supervised learning models. We have also tested the performance of our model on the real world task of semantic segmentation of breast cancer metastases in lymph node sections. We have compared the performance of our model with the performance of popular medical image segmentation architecture of Unet (Ronneberger et al., 2015) and shown that our weakly supervised model approximates the performance of fully supervised Unet model1.
Hence, there are three main contributions of this paper:
1. We have defined unique class count as a bag level label in MIL setup and mathematically proved that a perfect ucc classifier, in principle, can be used to perfectly cluster the individual instances inside the bags.
1Code and trained models: http://bit.ly/uniqueclasscount
2. We have constructed a neural network based ucc classifier by incorporating kernel density estimation (KDE) (Parzen, 1962) as a layer into our model architecture, which provided us with end-to-end training capability.
3. We have experimentally shown that clustering performance of our framework is better than the performance of unsupervised models and comparable to performance of fully supervised learning models.
The rest of the paper is organized such that related work is in Section 2, details of our weakly supervised clustering framework are in Section 3, results of the experiments on MNIST, CIFAR10 and CIFAR100 datasets are in Section 4, results of the experiments in semantic segmentation of breast cancer metastases are in Section 5, and Section 6 concludes the paper.

heading: 2 RELATED WORK
text: This work is partly related to MIL which was first introduced in (Dietterich et al., 1997) for drug activity prediction. Different types of MIL were derived with different assumptions (Gärtner et al., 2002; Zhang & Goldman, 2002; Chen et al., 2006; Foulds, 2008; Zhang & Zhou, 2009; Zhou et al., 2009), which are reviewed in detail in (Foulds & Frank, 2010), and they were used for many different applications such as, image annotation/categorization/retrieval (Chen & Wang, 2004; Zhang et al., 2002; Tang et al., 2010), text categorization (Andrews et al., 2003; Settles et al., 2008), spam detection (Jorgensen et al., 2008), medical diagnosis (Dundar et al., 2007), face/object detection (Zhang et al., 2006; Felzenszwalb et al., 2010) and object tracking (Babenko et al., 2011).
In MIL, different types of pooling layers are used to combine extracted features of instances inside the bags, such as max-pooling and log-sum-exp pooling (Ramon & De Raedt, 2000; Zhou & Zhang, 2002; Wu et al., 2015; Wang et al., 2018). On the other hand, our UCC model uses KDE layer in order to estimate the distribution of extracted features. The advantage of KDE over pooling layers is that it embeds the instance level features into distribution space rather than summarizing them.
There are also methods modeling cardinality and set distributions (Liu et al., 2015; Brukhim & Globerson, 2018; Kipf et al., 2018). However, cardinality of a set and ucc are completely different from each other. It is also important to state that ucc is obviously different from object/crowd counting (Idrees et al., 2013; Arteta et al., 2014; Zhang et al., 2015; 2016) since the task in object/crowd counting is to count the instances of the same type of object or people.
Lastly, we compare clustering accuracies of our models with clustering accuracies of unsupervised baseline models: K-means (Wang et al., 2015) and Spectral Clustering (Zelnik-Manor & Perona, 2005); state of the art unsupervised models: JULE (Yang et al., 2016), GMVAE (Dilokthanakul et al., 2016), DAC (Chang et al., 2017), DEPICT (Ghasedi Dizaji et al., 2017) and DEC (Xie et al., 2016); and state of the art semi-supervised models: AAE (Makhzani et al., 2015), CatGAN (Springenberg, 2015), LN (Rasmus et al., 2015) and ADGM (Maaløe et al., 2016).

heading: 3 WEAKLY SUPERVISED CLUSTERING FRAMEWORK
text: In this section, we state our machine learning objective and formally define our novel MIL task, which is the core of our weakly supervised clustering framework. Finally, we explain details of the two main components of our framework, namely UCC model and unsupervised clustering branch.
Objective: Let X = {x1, x2, · · · , xn} be a dataset such that each instance xi ∈ X belongs to a class, but its label is unknown. In this paper, we assume that total number of classes K is known. Hence, each instance xi is endowed with an underlying, but unkown, label L(xi) = li ∈ {1, 2, · · · ,K}. Further assume that for each class k ∈ {1, 2, · · ·K}, there exist at least one element xi ∈ X such that L(xi) = li = k. Our eventual objective is to derive a predicted class label l̂i for each instance xi that tends towards underlying truth class li, i.e. l̂i → L(xi) = li.

heading: 3.1 A NOVEL MIL TASK
text: In this novel MIL task, unique class count is used as an inexact, weak, bag level label and is defined in Definition 1. Assume that we are given subsets σζ ⊂ X , ζ = 1, 2, · · · , N and unique class counts
ησζ∀σζ . Hence, MIL dataset is D = {(σ1, ησ1), · · · , (σN , ησN )}. Then, our MIL task is to learn the mapping between the bags and their associated bag level ucc labels while the goal is to predict the ucc labels of unseen bags.
Definition 1 Given a subset σζ ⊂ X , unique class count, ησζ , is defined as the number of unique classes that all instances in the subset σζ belong to, i.e. ησζ = |{L(xi)|xi ∈ σζ}|. Recall that each instance belongs to an underlying unknown class.
Given a dataset D, our eventual objective is to assign a label to each instance xi ∈ X such that assigned labels and underlying unknown classes are consistent. To achieve this eventual objective, a deep learning model is designed such that the following intermediate objectives can be achieved while it is being trained on our MIL task:
1. Unique class count: Given an unseen set σζ , the deep learning model, which is trained on D, can predict its unique class count ησζ correctly.
2. Labels on sets: Let σpureζ and σ pure ξ be two disjoint pure sets (Definition 2) such that
while all instances in σpureζ belong to one underlying class, all instances in σ pure ξ belong to another class. Given σpureζ and σ pure ξ , the deep learning model should enable us to develop an unsupervised learning model to label instances in σpureζ and σ pure ξ as belonging to different classes. Note that the underlying classes for instances in the sets are unknown.
3. Labels on instances: Given individual instances xi ∈ X , the deep learning model should enable us to assign a label to each individual instance xi such that all instances with different/same underlying unknown classes are assigned different/same labels. This is the eventual unsupervised learning objective.
Definition 2 A set σ is called a pure set if its unique class count equals one. All pure sets is denoted by the symbol σpure in this paper.

heading: 3.2 UNIQUE CLASS COUNT MODEL
text: In order to achieve the stated objectives, we have designed a deep learning based Unique Class Count (UCC) model. Our UCC model consists of three neural network modules (θfeature, θdrn, θdecoder) and can be trained end-to-end. The first module θfeature extracts features from individual instances; then distributions of features are constructed from extracted features. The second module θdrn is used to predict ucc label from these distributions. The last module θdecoder is used to construct an autoencoder together with θfeature so as to improve the extracted features by ensuring that extracted features contain semantic information for reconstruction.
Formally, for xi ∈ σζ , i = {1, 2, · · · , |σζ |}, feature extractor module θfeature extracts J features {f1,iσζ , f 2,i σζ , · · · , fJ,iσζ } = θfeature(xi) for each instance xi ∈ σζ . As a short hand, we write the operator θfeature as operating element wise on the set to generate a feature matrix θfeature(σζ) = fσζ with matrix elements f j,iσζ ∈ R, representing the j
th feature of the ith instance. After obtaining features for all instances in σζ , a kernel density estimation (KDE) module is used to accumulate feature distributions hσζ = (h 1 σζ (v), h2σζ (v), · · · , h J σζ
(v)). Then, hσζ is used as input to distribution regression module θdrn to predict the ucc label, η̃σζ = θdrn(hσζ ) as a softmax vector (η̃ 1 σζ , η̃2σζ , · · · , η̃ K σζ
). Concurrently, decoder module θdecoder in autoencoder branch is used to reconstruct the input images from the extracted features in an unsupervised fashion, x̃i = θdecoder(θfeature(xi)). Hence, UCC model, main modules of which are illustrated in Figure 2(a), optimizes two losses concurrently: ‘ucc loss’ and ‘autoencoder loss’. While ‘ucc loss’ is cross-entropy loss, ‘autoencoder loss’ is mean square error loss. Loss for one bag is given in Equation 1.
α [ K∑ k=1 ηkσζ log η̃ k σζ ] ︸ ︷︷ ︸
ucc loss
+ (1− α)  1 |σζ | |σζ |∑ i=1 (xi − x̃i)2 
︸ ︷︷ ︸ autoencoder loss
where α ∈ [0, 1] (1)

heading: 3.2.1 KERNEL DENSITY ESTIMATION MODULE
text: In UCC model, input is a set σζ and output is corresponding ucc label η̃σζ , which does not depend on permutation of the instances in σζ . KDE module provides UCC model with permutationinvariant property. Moreover, KDE module uses the Gaussian kernel and it is differentiable, so our model can be trained end-to-end (Appendix A). KDE module also enables our theoretical analysis thanks to its decomposability property (Appendix B). Lastly, KDE module estimates the probability distribution of extracted features and enables θdrn to fully utilize the information in the shape of the distribution rather than looking at point estimates of distribution obtained by other types of pooling layers (Ramon & De Raedt, 2000; Zhou & Zhang, 2002; Wang et al., 2018) (Appendix C.6).

heading: 3.2.2 PROPERTIES OF UNIQUE CLASS COUNT MODEL
text: This section mathematically proves that the UCC model guarantees, in principle, to achieve the stated intermediate objectives in Section 3.1. Proof of propositions are given in Appendix B.
Proposition 1 Let σζ , σξ be disjoint subsets ofX with predicted unique class counts η̃σζ = η̃σξ = 1. If the predicted unique class count of σν = σζ ∪ σξ is η̃σν = 2, then hσζ 6= hσξ .
Definition 3 A perfect unique class count classifier takes in any set σ and output the correct predicted unique class count η̃σ = ησ .
Proposition 2 Given a perfect unique class count classifier. The dataset X can be perfectly clustered into K subsets σpureξ , ξ = 1, 2, · · · ,K, such that X = ⋃K ξ=1 σ pure ξ and σ pure ξ = {xi|xi ∈ X ,L(xi) = ξ}.
Proposition 3 Given a perfect unique class count classifier. Decompose the dataset X into K subsets σpureξ , ξ = 1, · · ·K, such that σ pure ξ = {xi|xi ∈ X ,L(xi) = ξ}. Then, hσpureξ 6= hσpureζ for ξ 6= ζ.
Suppose we have a perfect ucc classifier. For any two pure sets σpureζ and σ pure ξ , which consist of instances of two different underlying classes, ucc labels must be predicted correctly by the perfect ucc classifier. Hence, the conditions of Proposition 1 are satisfied, so we have hσpureζ 6= hσpureξ . Therefore, we can, in principle, perform an unsupervised clustering on the distributions of the sets without knowing the underlying truth classes of the instances. Hence, the perfect ucc classifier enables us to achieve our intermediate objective of “Labels on sets”. Furthermore, given a perfect ucc classifier, Proposition 2 states that by performing predictions of ucc labels alone, without any
knowledge of underlying truth classes for instances, one can in principle perform perfect clustering for individual instances. Hence, a perfect ucc classifier enables us to achieve our intermediate objective of “Labels on instances”.

heading: 3.3 UNSUPERVISED INSTANCE CLUSTERING
text: In order to achieve our ultimate objective of developing an unsupervised learning model for clustering all the instances in dataset X , we add this unsupervised clustering branch into our framework. Theoreticallly, we have shown in Proposition 3 that given a perfect ucc classifier, distributions of pure subsets of instances coming from different underlying classes are different.
In practice, it may not be always possible (probably most of the times) to train a perfect ucc classifier, so we try to approximate it. First of all, we train our ucc classifier on our novel MIL task and save our trained model (θ̄feature, θ̄drn, θ̄decoder). Then, we use trained feature extractor θ̄feature to obtain feature matrix fX = θ̄feature(X ). Finally, extracted features are clustered in an unsupervised fashion, by using simple k-means and spectral clustering methods. Figure 2(b) illustrates the unsupervised clustering process in our framework. A good feature extractor θ̄feature is of paramount importance in this task. Relatively poor θ̄feature may result in a poor unsupervised clustering performance in practice even if we have a strong θ̄drn. To obtain a strong θ̄feature, we employ an autoencoder branch, so as to achieve high clustering performance in our unsupervised instance clustering task. The autoencoder branch ensures that features extracted by θ̄feature contain semantic information for reconstruction.

heading: 4 EXPERIMENTS ON MNIST AND CIFAR DATASETS
text: This section analyzes the performances of our UCC models and fully supervised models in terms of our eventual objective of unsupervised instance clustering on MNIST (10 clusters) (LeCun et al., 1998), CIFAR10 (10 clusters) and CIFAR100 (20 clusters) datasets (Krizhevsky & Hinton, 2009).

heading: 4.1 MODEL ARCHITECTURES AND DATASETS
text: To analyze different characteristics of our framework, different kinds of unique class count models were trained during our experiments: UCC, UCC2+, UCCα=1 and UCC2+α=1. These unique class count models took sets of instances as inputs and were trained on ucc labels. While UCC and UCC2+ models had autoencoder branch in their architecture and they were optimized jointly over both autoencoder loss and ucc loss,UCCα=1 andUCC2+α=1 models did not have autoencoder branch in their architecture and they were optimized over ucc loss only (i.e. α = 1 in Equation 1). The aim of training unique class count models with and without autoencoder branch was to show the effect of autoencoder branch in the robustness of clustering performance with respect to ucc classification performance. UCC and UCCα=1 models were trained on bags with labels of ucc1 to ucc4. On the other hand, UCC2+ and UCC2+α=1 models were trained on bags with labels ucc2 to ucc4. Our models were trained on ucc labels up to ucc4 instead of ucc10 (ucc20 in CIFAR100) since the performance was almost the same for both cases and training with ucc1 to ucc4 was much faster (Appendix C.2). Please note that for perfect clustering of instances inside the bags, it is enough to have a perfect ucc classifier that can perfectly discriminate ucc1 and ucc2 bags from Proposition 2. The aim of traininig UCC2+ and UCC2+α=1 models was to experimentally check whether these models can perform as good as UCC and UCCα=1 models even if there is no pure subsets during training. In addition to our unique class count models, for benchmarking purposes, we also trained fully supervised models, FullySupervised, and unsupervised autoencoder models, Autoencoder. FullySupervised models took individual instances as inputs and used instance level ground truths as labels during training. On the other hand, Autoencoder models were trained in an unsupervised manner by optimizing autoencoder loss (i.e. α = 0 in Equation 1). It is important to note that all models for a dataset shared the same architecture for feature extractor module and all the modules in our models are fine tuned for optimum performance and training time as explained in Appendix C.1.
We trained and tested our models on MNIST, CIFAR10 and CIFAR100 datasets. We haveXmnist,tr, Xmnist,val andXmnist,test for MNIST;Xcifar10,tr,Xcifar10,val andXcifar10,test for CIFAR10; and Xcifar100,tr, Xcifar100,val and Xcifar100,test for CIFAR100. Note that tr, val and test subscripts stand for ‘training’, ‘validation’ and ‘test’ sets, respectively. All the results presented in this paper were obtained on hold-out test sets Xmnist,test, Xcifar10,test and Xcifar100,test. FullySupervised
models took individual instances as inputs and were trained on instance level ground truths. Unique class count models took sets of instances as inputs, which were sampled from the power sets 2Xmnist,tr , 2Xcifar10,tr and 2Xcifar100,tr , and were trained on ucc labels (Appendix C.2). While all the models were trained in a supervised setup, either on ucc labels or instance level ground truths, all of them were used to extract features for unsupervised clustering of individual instances.

heading: 4.2 UNIQUE CLASS COUNT PREDICTION
text: Preceeding sections showed, in theory, that a perfect ucc classifier can perform ‘weakly’ supervised clustering perfectly. We evaluate ucc prediction accuracy of our unique class count models in accordance with our first intermediate objective that unique class count models should predict ucc labels of unseen subsets correctly. We randomly sampled subsets for each ucc label from the power sets of test sets and predicted the ucc labels by using trained models. Then, we calculated the ucc prediction accuracies by using predicted and truth ucc labels, which are summarized in Table 1 (Appendix C.3). We observed that as the task becomes harder (from MNIST to CIFAR100), it also becomes harder to approximate the perfect ucc classifier. Moreover, UCC and UCCα=1 models, in general, have higher scores than their counterpart models of UCC2+ and UCC2+α=1, which is expected since the ucc prediction task becomes easier at the absence of pure sets and models reach to early stopping condition (Appendix C.1) more easily. This is also supported by annother interesting, yet reasonable, observation that UCC2+ models have higher ucc accuracies than UCC2+α=1 models thanks to the autoencoder branch which makes UCC2+ harder to reach to early stopping condition.

heading: 4.3 LABELS ON SETS
text: Jensen-Shannon (JS) divergence (Lin, 1991) value between feature distributions of two pure sets consisting of instances of two different underlying classes is defined as inter-class JS divergence in this paper and used for comparison on ‘Labels on sets’ objective of assigning labels to pure sets. Higher values of inter-class JS divergence are desired since it means that feature distributions of
pure sets of underlying classes are far apart from each other. The features of all the instances in a particular class are extracted by using a trained model and feature distributions associated to that class obtained by performing kernel density estimation on these extracted features. Then, for each pair of classes, inter-class JS divergence values are calculated (Appendix C.4). For a particular model, which is used in feature extraction, the minimum of these pairwise inter-class JS divergence values is used as a metric in the comparison of models. We have observed that as the task gets more challenging and the number of clusters increases, there is a drop in minimum inter-class JS divergence values, which is summarized in Table 1.

heading: 4.4 LABELS ON INSTANCES
text: For our eventual objective of ‘Labels on instances’, we have used ‘clustering accuracy’ as a comparison metric, which is calculated similar to Ghasedi Dizaji et al. (2017). By using our trained models, we extracted features of individual instances of all classes in test sets. Then, we performed unsupervised clustering over these features by using k-means and spectral clustering. We used number of classes in ground truth as number of clusters (MNIST: 10, CIFAR10: 10, CIFAR100: 20 clusters) during clustering and gave the best clustering accuracy for each model in Table 1 (Appendix C.5).
In Table 1, we compare clustering accuracies of our models together with baseline and state of the art models in the literature: baseline unsupervised (K-means (Wang et al., 2015), Spectral Clustering (Zelnik-Manor & Perona, 2005)); state of the art unsupervised (JULE (Yang et al., 2016), GMVAE (Dilokthanakul et al., 2016), DAC (Chang et al., 2017), DEPICT (Ghasedi Dizaji et al., 2017), DEC (Xie et al., 2016)) and state of the art semi-supervised (AAE (Makhzani et al., 2015), CatGAN (Springenberg, 2015), LN (Rasmus et al., 2015), ADGM (Maaløe et al., 2016)). Clustering performance of our unique class count models is better than the performance of unsupervised models in all datasets and comparable to performance of fully supervised learning models in MNIST and CIFAR10 datasets. The performance gap gets larger in CIFAR100 dataset as the task becomes harder. Although semi-supervised methods use some part of the dataset with ‘exact’ labels during training, our models perform on par with AAE and CatGAN models and comparable to LN and ADGM models on MNIST dataset. ADGM and LN even reach to the performance of the FullySupervised model since they exploit training with ‘exact’ labeled data. On CIFAR10 dataset, LN and CatGAN models are slightly better than our unique class count models; however, they use 10% of instances with ‘exact’ labels, which is not a small portion.
In general, our UCC and UCCα=1 models have similar performance, and they are better than their counterpart models of UCC2+ and UCC2+α=1 due to the absence of pure sets during training. However, in the real world tasks, the absence of pure sets heavily depends on the nature of the problem. In our task of semantic segmentation of breast cancer metastases in histological lymph node sections, for example, there are many pure sets. Furthermore, we observed that there is a performance gap between UCC2+ and UCC2+α=1 models: UCC
2+ models perform better than UCC2+α=1 models thanks to the autoencoder branch. The effect of autoencoder branch is also apparent in Figure 3, which shows clustering accuracy vs ucc accuracy curves for different datasets. For MNIST dataset, while UCC model gives clustering accuracy values proportional to ucc accuracy, UCCα=1 model cannot reach to high clustering accuracy values until it reaches to high ucc accuracies. The reason is that autoencoder branch in UCC helps θfeature module to extract better features during the initial phases of the training process, where the ucc classification accuracy is low. Compared to other
datasets, this effect is more significant in MNIST dataset since itself is clusterable. Although autoencoder branch helps in CIFAR10 and CIFAR100 datasets as well, improvements in clustering accuracy coming from autoencoder branch seems to be limited, so two models UCC and UCCα=1 follow nearly the same trend in the plots. The reason is that CIFAR10 and CIFAR100 datasets are more complex than MNIST dataset, so autoencoder is not powerful enough to contribute to extract discrimant features, which is also confirmed by the limited improvements of Autoencoder models over baseline performance in these datasets.

heading: 5 SEMANTIC SEGMENTATION OF BREAST CANCER METASTASES
text: Semantic segmentation of breast cancer metastases in histological lymph node sections is a crucial step in staging of breast cancer, which is the major determinant of the treatment and prognosis (Brierley et al., 2016). Given the images of lymph node sections, the task is to detect and locate, i.e. semantically segment out, metastases regions in the images. We have formulated this task in our novel MIL framework such that each image is treated as a bag and corresponding ucc label is obtained based on whether the image is from fully normal or metastases region, which is labeled by ucc1, or from boundary region (i.e. image with both normal and metastases regions), which is labeled by ucc2. We have shown that this segmentation task can be achieved by using our weakly supervised clustering framework without knowing the ground truth metastases region masks of images, which require experts to exhaustively annotate each metastases region in each image. This annotation process is tedious, time consuming and more importantly not a part of clinical workflow.
We have used 512 × 512 image crops from publicly available CAMELYON dataset (Litjens et al., 2018) and constructed our bags by using 32× 32 patches over these images. We trained our unique class count model UCCsegment on ucc labels. Then, we used the trained model as a feature extractor and conducted unsupervised clustering over the patches of the images in the hold-out test dataset to obtain semantic segmentation masks. For benchmarking purposes, we have also trained a fully supervised Unet model (Ronneberger et al., 2015), which is a well-known biomedical image segmentation architecture, by using the ground truth masks and predicted the segmentation maps in
the test set. The aim of this comparison was to show that at the absence of ground truth masks, our model can approximate the performance of a fully supervised model. Moreover, we have obtained semantic segmentation maps in the test dataset by using k-means clustering as a baseline study. Example images from test dataset with corresponding ground truth masks, ucc labels and predicted masks by different models are shown in Figure 4. (Please see Appendix D.1 for more details.)
Furthermore, we have calculated pixel level gross statistics of TPR (True Positive Rate), FPR (False Positive Rate), TNR (True Negative Rate), FNR (False Negative Rate) and PA (Pixel Accuracy) over the images of hold-out test dataset and declared the mean values in Table 2 (Appendix D.2). When we look at the performance of unsupervised baseline method of K-means clustering, it is obvious that semantic segmentation of metastases regions in lymph node sections is not an easy task. Baseline method achieves a very low TPR value of 0.370 and almost random score of 0.512 in PA. On the other hand, both our weakly supervised model UCCsegment and fully supervised model Unet outperform the baseline method. When we compare our model UCCsegment with Unet model, we see that both models behave similarly. They have reasonably high TPR and TNR scores, and low FPR and FNR scores. Moreover, they have lower FPR values than FNR values, which is more favorable than vice-versa since pathologists opt to use immunohistochemistry (IHC) to confirm negative cases (Bejnordi et al., 2017). However, there is a performance gap between two models, which is mainly due to the fact that Unet model is a fully supervised model and it is trained on ground truth masks, which requires exhaustive annotations by experts. On the contrary, UCCsegment model is trained on ucc labels and approximates to the performance of the Unet model. ucc label is obtained based on whether the image is metastatic, non-metastatic or mixture, which is much cheaper and easier to obtain compared to exhaustive mask annotations. Another factor affecting the performance of UCCsegment model is that ucc1 labels can sometimes be noisy. It is possible to have some small portion of normal cells in cancer regions and vice-versa due to the nature of the cancer. However, our UCCsegment is robust to this noise and gives reasonably good results, which approximates the performance of Unet model.

heading: 6 CONCLUSION
text: In this paper, we proposed a weakly supervised learning based clustering framework and introduce a novel MIL task as the core of this framework. We defined ucc as a bag level label in MIL setup and mathematically proved that a perfect ucc classifier can be used to perfectly cluster individual instances inside the bags. We designed a neural network based ucc classifer and experimentally showed that clustering performance of our framework with our ucc classifiers are better than the performance of unsupervised models and comparable to performance of fully supervised learning models. Finally, we showed that our weakly supervised unique class count model,UCCsegment, can be used for semantic segmentation of breast cancer metastases in histological lymph node sections. We compared the performance of our model UCCsegment with the performance of a Unet model and showed that our weakly supervised model approximates the performance of fully supervised Unet model. In the future, we want to check the performance of our UCCsegment model with other medical image datasets and use it to discover new morphological patterns in cancer that had been overlooked in traditional pathology workflow.

heading: ACKNOWLEDGEMENTS
text: This work is supported by the Biomedical Research Council of the Agency for Science, Technology, and Research, Singapore and the National University of Singapore, Singapore.

heading: A KERNEL DENSITY ESTIMATION
text: Kernel density estimation is a statistical method to estimate underlying unknown probability distribution in data (Parzen, 1962). It works based on fitting kernels at sample points of an unknown distribution and adding them up to construct the estimated probability distribution. Kernel density estimation process is illustrated in Figure 5.
A.1 KDE MODULE IS DIFFERENTIABLE
The distribution of the feature hjσζ (v) is obtained by applying kernel density estimation on the extracted features f j,iσζ as in Equation 2. In order to be able to train our unique class count model end-to-end, we need to show that KDE module is differentiable, so that we can pass the gradients from θdrn to θfeature during back-propagation. Derivative of hjσζ (v) with respect to input of KDE
module, f j,iσζ , can be obtained as in Equation 3.
hjσζ (v) = 1
|σζ | |σζ |∑ i=1 1√ 2πσ2 e − 1 2σ2 ( v−fj,iσζ )2 (2)
∂hjσζ (v)
∂f j,iσζ =
1
|σζ |
( v − f j,iσζ ) σ2 √ 2πσ2 e − 1 2σ2 ( v−fj,iσζ )2 (3)
After showing that KDE module is differentiable, we can show the weight update process for θfeature module in our model. Feature extractor module θfeature is shared by both autoencoder branch and ucc branch in our model. During back-propagation phase of the end-to-end training process, the weight updates of θfeature comprise the gradients coming from both branches (Equation 5). Gradients coming from autoencoder branch follow the traditional neural network back-propagation flow through the convolutional and fully connected layers. Different than that, gradients coming from ucc branch (Equation 6) also back-propagate through the custom KDE layer according to Equation 3.
Loss = αLossucc︸ ︷︷ ︸ ucc loss + (1− α) Lossae︸ ︷︷ ︸ autoencoder
loss
where α ∈ [0, 1] (4)
∂Loss ∂θfeature︸ ︷︷ ︸ gradients
for θfeature
= α ∂Lossucc ∂θfeature︸ ︷︷ ︸ gradients
from ucc branch
+ (1− α) ∂Lossae ∂θfeature︸ ︷︷ ︸ gradients
from autoencoder branch
(5)
∂Lossucc ∂θfeature = ∂Lossucc ∂hσζ × ∂hσζ ∂fσζ︸ ︷︷ ︸
back-propagation through
KDE layer
× ∂fσζ ∂θfeature
(6)

heading: B PROOFS OF PROPOSITIONS
text: Before proceeding to the formal proofs, it is helpful to emphasize the decomposability property of kernel density estimation here.
For any set, σζ , one could partition it into a set ofM disjoint subsets σζ = σ′1∪σ′2∪· · ·∪σ′M where σ′λ∩σ′ψ = ∅ for λ 6= ψ. It is trivial to show that distribution hjσζ (v) is simply a linear combination of distributions hjσ′λ(v), λ = 1, 2, · · · ,M (Equation 7). As a direct consequence, one could decompose any set into its pure subsets. This is an important decomposition which will be used in the proofs of propositions later.
hjσζ (v) = M∑ λ=1 wσ′λh j σ′λ (v),∀j where wσ′λ = |σ′λ| |σζ |
(7)
Now, we can proceed to formally state our propositions.
Definition 1 Given a subset σζ ⊂ X , unique class count, ησζ , is defined as the number of unique classes that all instances in the subset σζ belong to, i.e. ησζ = |{L(xi)|xi ∈ σζ}|. Recall that each instance belongs to an underlying unknown class.
Definition 2 A set σ is called a pure set if its unique class count equals one. All pure sets are denoted by the symbol σpure in this paper.
Proposition B. 1 For any set σζ ⊂ X , the unique class count ησζ of σζ does not depend on the number of instances in σζ belonging to a certain class.
Proof: This conclusion is obvious from the definition of unique class count in Definition 1.
Proposition B. 2 θdrn is non-linear.
Proof: We give a proof by contradiction using Proposition B.1. Suppose θdrn is linear, then θdrn(hσν ) = θdrn(wζhσζ + wξhσξ) (8)
= wζθdrn(hσζ ) + wξθdrn(hσξ)
= wζ η̃σζ + wξη̃σξ = η̃σν
Hence, θdrn is linear only when Equation 8 holds. However, by Proposition B.1, (θfeature, θdrn) should count correctly regardless of the proportion of the size of the sets |σζ | and |σξ|. Hence, Equation 8 cannot hold true and θdrn by contradiction cannot be linear.
Proposition B. 3 Let σζ , σξ be disjoint subsets of X with predicted unique class counts η̃σζ and η̃σξ , respectively. Let η̃σν be the predicted unique class count of σν = σζ ∪ σξ. If hσζ = hσξ , then η̃σν = η̃σζ = η̃σξ .
Proof: The distribution of set σν can be decomposed into distribution of subsets, hσν = wζhσζ + wξhσξ where wζ + wξ = 1 (9) hσζ = hσξ =⇒ hσν = hσζ (10)
Hence, η̃σν = η̃σζ = η̃σξ .
Proposition 1 Let σζ , σξ be disjoint subsets ofX with predicted unique class counts η̃σζ = η̃σξ = 1. If the predicted unique class count of σν = σζ ∪ σξ is η̃σν = 2, then hσζ 6= hσξ .
Proof: Proof of this proposition follows immediately from the contra-positive of Proposition B.3.
Definition 3 A perfect unique class count classifier takes in any set σ and output the correct predicted unique class count η̃σ = ησ .
Proposition 2 Given a perfect unique class count classifier. The dataset X can be perfectly clustered into K subsets σpureξ , ξ = 1, 2, · · · ,K, such that X = ⋃K ξ=1 σ pure ξ and σ pure ξ = {xi|xi ∈ X ,L(xi) = ξ}.
Proof: First note that this proposition holds because the “perfect unique class count classifier” is a very strong condition. Decompose X into subsets with single instance and then apply the unique class count on each subset, by definition, unique class counts of all subsets are one. Randomly pair up the subsets and merge them if their union still yield unique class count of one. Recursively apply merging on this condition until no subsets can be merged.
Proposition 3 Given a perfect unique class count classifier. Decompose the dataset X into K subsets σpureξ , ξ = 1, · · ·K, such that σ pure ξ = {xi|xi ∈ X ,L(xi) = ξ}. Then, hσpureξ 6= hσpureζ for ξ 6= ζ.
Proof: Since in Proposition 1, the subsets are arbitrary, it holds for any two subsets with unique class count of one. By pairing up all combinations, one arrives at this proposition. Note that for a perfect unique class count classifier, η = η̃.

heading: C DETAILS ON EXPERIMENTS WITH MNIST AND CIFAR DATASETS
text: C.1 DETAILS OF MODEL ARCHITECTURES
Feature extractor module θfeature has convolutional blocks similar to the wide residual blocks in Zagoruyko & Komodakis (2016). However, the parameters of architectures, number of convolutional and fully connected layers, number of filters in convolutional layers, number of nodes in
fully-connected layers, number of bins and σ value in KDE module, were decided based on models’ performance and training times. While increasing number of convolutional layers or filters were not improving performance of the models substantialy, they were putting a heavy computation burden. For determining the architecture of θdrn, we checked the performances of different number of fully connected layers. As the number of layers increased, the ucc classification performance of the models increased. However, we want θfeature to be powerful, so we stopped to increase number of layers as soon as we got good results. For KDE module, we have tried parameters of 11 bins, 21 bins, σ = 0.1 and σ = 0.01. Best results were obtained with 11 bins and σ = 0.1. Similarly, we have tested different number of features at the output of θfeature module and we decided to use 10 features for MNIST and CIFAR10 datasets and 16 features for CIFAR100 dataset based on the clustering performance and computation burden.
During training, loss value of validation sets was observed as early stopping criteria. Training of the models was stopped if the validation loss didn’t drop for some certain amount of training iterations.
For the final set of hyperparameters and details of architectures, please see the code for our experiments: http://bit.ly/uniqueclasscount
C.2 DETAILS OF DATASETS
We trained and tested our models on MNIST, CIFAR10 and CIFAR100 datasets. While MNIST and CIFAR10 datasets have 10 classes, CIFAR100 dataset has 20 classes. For MNIST, we randomly splitted 10,000 images from training set as validation set, so we had 50,000, 10,000 and 10,000 images in our training Xmnist,tr, validation Xmnist,val and test sets Xmnist,test, respectively. In CIFAR10 dataset, there are 50,000 and 10,000 images with equal number of instances from each class in training and testing sets, respectively. Similar to MNIST dataset, we randomly splitted 10,000 images from the training set as validation set. Hence, we had 40,000, 10,000 and 10,000 images in our training Xcifar10,tr, validation Xcifar10,val and testing Xcifar10,test sets for CIFAR10, respectively. In CIFAR100 dataset, there are 50,000 and 10,000 images with equal number of instances from each class in training and testing sets, respectively. Similar to other datasets, we randomly splitted 10,000 images from the training set as validation set. Hence, we had 40,000, 10,000 and 10,000 images in our training Xcifar100,tr, validation Xcifar100,val and testing Xcifar100,test sets for CIFAR10, respectively.
FullySupervised models took individual instances as inputs and were trained on instance level ground truths. Xmnist,tr, Xcifar10,tr and Xcifar100,tr were used for training of FullySupervised models. Unique class count models took sets of instances as inputs and were trained on ucc labels. Inputs to unique class count models were sampled from the power sets of MNIST, CIFAR10 and CIFAR100 datasets, i.e. 2Xmnist,tr , 2Xcifar10,tr and 2Xcifar100,tr . For MNIST and CIFAR10 datasets, the subsets (bags) with 32 instances and for CIFAR100 dataset, the subsets (bags) with 128 instances are used in our experiments. While UCC and UCCα=1 models are trained on ucc1 to ucc4 labels, UCC2+ and UCC2+α=1 models are trained on ucc2 to ucc4 labels.
Our models were trained on ucc labels up to ucc4 instead of ucc10 (ucc20 in CIFAR100) since the performance was almost the same for both cases in our experiment with MNIST dataset, results of which are shown in Table 3. On the other hand, training with ucc1 to ucc4 was much faster than ucc1 to ucc10 because as the ucc label gets larger, the number of instances in a bag is required to be larger in order to represent each class and number of elements in powerset also grows exponentially. Please note that for perfect clustering of instances, it is enough to have a perfect ucc classifier that can discriminate ucc1 and ucc2 from Proposition 2.
All the results presented in this paper were obtained on hold-out test sets Xmnist,test, Xcifar10,test and Xcifar100,test.
C.3 CONFUSION MATRICES FOR ucc PREDICTIONS
We randomly sampled subsets for each ucc label from the power sets of test sets and predicted the ucc labels by using trained models. Then, we calculated the ucc prediction accuracies by using predicted and truth ucc labels, which are summarized in Table 1. Here, we show confusion matrices of our UCC and UCC2+ models on MNIST, CIFAR10 and CIFAR100 datasets as examples in Figure 6, 7 and 8, respectively.
C.4 FEATURE DISTRIBUTIONS AND INTER-CLASS JS DIVERGENCE MATRICES
The features of all the instances in a particular class are extracted by using a trained model and feature distributions associated to that class obtained by performing kernel density estimation on these extracted features. Then, for each pair of classes, inter-class JS divergence values are calculated. We show inter-class JS divergence matrices for our FullySupervised and UCC models on MNIST test dataset in Figure 9. We also show the underlying distributions for FullySupervised and UCC models in Figure 10 and 11, respectively.
Fi gu
re 10
:D is
tr ib
ut io
ns of
ex tr
ac te
d fe
at ur
es by
ou rF
u ll y S u p er v is ed
m od
el on
M N
IS T
te st
da ta
se t.
E ac
h co
lu m
n co
rr es
po nd
s to
a fe
at ur
e le
ar ne
d by
m od
el an d ea ch ro w co rr es po nd s to an un de rl yi ng cl as s in th e te st da ta se t.
Fi gu
re 11
: D
is tr
ib ut
io ns
of ex
tr ac
te d
fe at
ur es
by ou
r U C C
m od
el on
M N
IS T
te st
da ta
se t.
E ac
h co
lu m
n co
rr es
po nd
s to
a fe
at ur
e le
ar ne
d by
m od
el an
d ea
ch ro w co rr es po nd s to an un de rl yi ng cl as s in th e te st da ta se t.
C.5 K-MEANS AND SPECTRAL CLUSTERING ACCURACIES OF OUR MODELS
We performed unsupervised clustering by using k-means and spectral clustering and gave the best clustering accuracy for each model on each dataset in Table 1 in the main text. Here, we present all the clustering accuracies for our models in Table 4.
C.6 UCC MODELS WITH AVERAGING LAYER AND KDE LAYER
KDE layer is chosen as MIL pooling layer in UCC model because of its four main properties, first three of which are essential for the proper operation of proposed framework and validity of the propositions in the paper:
1. KDE layer is permutation-invariant, i.e. the output of KDE layer does not depend on the permutation of its inputs, which is important for the stability of θdrn module.
2. KDE layer is differentiable, so UCC model can be trained end-to-end. 3. KDE layer has decomposability property which enables our theoretical analysis (Ap-
pendix B). 4. KDE layer enables θdrn to fully utilize the information in the shape of the distribution rather
than looking at point estimates of distribution.
Averaging layer (Wang et al., 2018) as an MIL pooling layer, which also has the first three properties, can be an alternative to KDE layer in UCC model. We have conducted additional experiments by replacing KDE layer with ’averaging layer’ and compare the clustering accuracy values of the models with averaging layer and the models with KDE layer in Table 5.

heading: D DETAILS ON SEMANTIC SEGMENTATION TASK
text: D.1 DETAILS OF MODEL AND DATASET
Our model UCCsegment has the same architecture with the UCC model in CIFAR10 dataset, but this time we have used 16 features. We have also constructed the Unet model with the same blocks used in UCCsegment model in order to ensure a fair comparison. The details of the models can be seen in our code: http://bit.ly/uniqueclasscount
We have used 512 × 512 image crops from publicly available CAMELYON dataset (Litjens et al., 2018). CAMELYON dataset is a public Whole Slide Image (WSI) dataset of histological lymph node sections. It also provides the exhaustive annotations for metastases regions inside the slides which enables us to train fully supervised models for benchmarking of our weakly supervised unique class count model.
We randomly crop 512×512 images over the WSIs of CAMELYON dataset and associate a ucc label to each image based on whether it is fully metastases/normal (ucc1) or mixture (ucc2). We assigned ucc labels based on provided ground truths since they are readily available. However, please note that in case no annotations provided, obtaining ucc labels is much cheaper and easier compared to tedious and time consuming exhaustive metastases region annotations. We assigned ucc1 label to an image if the metastases region in the corresponding ground truth mask is either less than 20% (i.e. normal) or more than 80% (i.e metastases). On the other hand, we assigned ucc2 label to an image if the metastases region in the corresponding ground truth mask is more than 30% and less than 70% (i.e. mixture). Actually, this labeling scheme imitates the noise that would have been introduced if ucc labeling had been done directly by the user instead of using ground truth masks. Beyond that, ucc1 labels in this task can naturally be noisy since it is possible to have some small portion of normal cells in cancer regions and vice-versa due to the nature of the cancer. In this way, we have constructed our segmentation dataset consisting of training, validation and testing sets. The images in training and validation sets are cropped randomly over the WSIs in training set of CAMELYON dataset and the images in testing set are cropped randomly over the test set of CAMELYON dataset. Then, the bags in our MIL dataset to train UCCsegment model are constructed by using 32 × 32 patches over these images. Each bag contains 32 instances, where each instance is a 32× 32 patch. The details of our segmentation dataset are shown in Table 6.
We have provided the segmentation dataset under “./data/camelyon/” folder inside our code folder. If you want to use this dataset for benchmarking purposes please cite our paper (referenced later) together with the original CAMELYON dataset paper of Litjens et al. (2018).
We have given confusion matrix for ucc predictions of our UCCsegment model in Figure 12. For Unetmodel, we have shown loss curves of traininig and validation sets during training in Figure 13.
D.2 DEFINITIONS OF EVEALUTION METRICS
In this section, we have defined our pixel level evaluation metrics used for performance comparison of our weakly supervised UCCsegment model, fully supervised Unetmodel and unsupervised baseline K −means model. Table 7 shows the structure of pixel level confusion matrix together with basic statistical terms. Then, our pixel level evaluation metrics TPR (True Positive Rate), FPR (False Positive Rate), TNR (True Negative Rate), FNR (False Negative Rate) and PA (Pixel Accuracy) are defined in Equation 11, 12, 13, 14 and 15, respectively.
FPR = FP
FP + TN (12)
TNR = TN
TN + FP (13)
FNR = FN
FN + TP (14)
PA = TP + TN
TP + FP + TN + FN (15)

Review summaries:
This paper proposes a MIL clustering method. The proposed MIL setup is called "unique class count (ucc)", this is, for a bag os samples ucc is the number of clusters in the bag. The method learns the features of the samples using two losses: an autoender loss and the ucc loss. Once trained on a dataset the method can perform clustering on classes (classify) better than a fully unsupervised clustering algorithm and worse than a fully supervised model. The method is evaluated on MNIST, CIFAR10, CIFAR100  and on binary breast cancer segmentation.

This paper proposes a new type of weakly supervised clustering / multiple instance learning (MIL) problem in which bags of instances (data points) are labeled with a "unique class count (UCC)*, rather than any bag-level or instance-level labels.  For example, a histopathology slide (the bag), consisting of many individual pixels to be labeled (the instances) could be labeled at the bag level only with UCC = 1 (for only healthy or only metastatic) or UCC = 2 (for mixed / border case).  The paper then proposes an approach for clustering instances based on the following two-step approach: (1) a UCC model is trained to predict the UCC given an input bag, and (2) the features of this learned UCC model are used in an unsupervised clustering algorithm to the get the instance-level clusters / labels.  The paper also provides a theoretical argument for why this approach is feasible.