Unsupervised Learning under Latent Label Shift
Authors: Manley Roberts
Pranav Mani
Saurabh Garg
Zachary Chase Lipton
Venue: NeurIPS 2022 Accept (2022)
Keywords: unsupervised learning
label shift
topic modeling
domain adaptation
mixture proportion estimation
unsupervised structure discovery
anchor word
deep learning

Abstract: What sorts of structure might enable a learner to discover classes from unlabeled data? Traditional approaches rely on feature-space similarity and heroic assumptions on the data. In this paper, we introduce unsupervised learning under Latent Label Shift (LLS), where the label marginals $p_d(y)$ shift but the class conditionals $p(x|y)$ do not. This work instantiates a new principle for identifying classes: elements that shift together group together. For finite input spaces, we establish an isomorphism between LLS and topic modeling: inputs correspond to words, domains to documents, and labels to topics. Addressing continuous data, we prove that when each label's support contains a separable region, analogous to an anchor word, oracle access to $p(d|x)$ suffices to identify $p_d(y)$ and $p_d(y|x)$ up to permutation. Thus motivated, we introduce a practical algorithm that leverages domain-discriminative models as follows: (i) push examples through domain discriminator $p(d|x)$; (ii) discretize the data by clustering examples in $p(d|x)$ space; (iii) perform non-negative matrix factorization on the discrete data; (iv) combine the recovered $p(y|d)$ with the discriminator outputs $p(d|x)$ to compute $p_d(y|x) \; \forall d$. With semisynthetic experiments, we show that our algorithm can leverage domain information to improve upon competitive
unsupervised classification methods. We reveal a failure mode of standard unsupervised classification methods when data-space similarity does not indicate true groupings, and show empirically that our method better handles this case. Our results establish a deep connection between distribution shift and topic modeling, opening promising lines for future work.

Unsupervised Learning under Latent Label Shift
Manley Roberts"
Pranav Mani
Saurabh Garg
Zachary C. Lipton
Carnegie Mellon University
fmanleyroberts, http:/obbrttrzipttooooooooo edu; {pmani, sgarg2 cmu. edu
Abstract
What sorts of structure might enable a learner to discover classes from unla- beled data? Traditional approaches rely feature-space similarity and heroic sumptions on the data. this paper, we introduce unsupervised learning under Latent Label Shift (LLS), where have access unlabeled data from multiple domains such that the label marginals pa(y) can shift across domains but the class conditionals p(xly) do not. This work instantiates classes: elements that shift together group together. For finite input spaces, we es- tablish isomorphism between LLS and topic modeling: inputs correspond words, domains to documents, and labels to topics. Addressing continuous data, prove that when each label's support contains separable region, analogous an anchor word, oracle access to p(d x) suffices to identify pa(y) and Pa(y)x /) up permutation. Thus motivated, we introduce practical algorithm that leverages models as follows: (i) push examples through domain dis- criminator p[d[x): (ii) discretize the data by clustering examples in p[d] space; (iii) perform non nngaaivee matrix factorization on the discrete data; (iv) combine the recovered ply d) with the discriminator outputs p( p(d|x) compute pa(y a+) Vd. With comi-synthetic experiments, we show that our algorithm can leverage domain information to improve upon competitive unsupervised classification methods. We reveal failure mode of standard unsupervised classification methods when data- space similarity does not indicate true groupings, and show empirically that our method better handles this casc. Our results establish deep connection between distribution shift and topic modeling, opening promising lines for future work
principle for identifying
Introduction
Discovering systems of categories from unlabeled data is fundamental but ill-posed challenge in machine learning. Typical unsupervised learning methods group instances together based on feature- space similarity. Accordingly, given collection of photographs of animals, practitioner might hope that, in some appropriate feature space, images of animals of the same species should be somehow similar to each other. But why should expect clustering algorithm to recognize that dogs viewed in sunlight and dogs viewed at night belong to the same category? Why should we expect that butterflies and caterpillars should lie close together in feature space?
In this paper, we offer an alternative principle according to which we might identify a set of classes: we exploit distribution shift across times and locations to reveal otherwise unrecognizable groupings among examples. For example, we noticed that whenever we found ourselves in a location where butterflies abundant, caterpillars were similarly abundant, and that whenever butterflies were scarce, caterpillars had a similar drop in prevalence, we might conclude that the two were tied the same underlying concept, no matter how different they appear in feature space. In short, our principle suggests that latent classes might be uncovered whenever instances that shift together group together.
$ "qqual contribution.
"Code is available at
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

DX,
(((x)
D
Domatn Domain Discriminttor
Cluster
Domain 2
D D=2
NMF
Q
QY
Dorialn
Pa(s)e)
Figure 1: Schematic of our DDFA algorithm. After training a domain discriminator, we (i) push all data through the discriminator; (ii) cluster the data based on discriminator outputs; (iil) solve the resulting discrete topic modeling problem and then combine (d][x) and ς(y, d) to estimate Pa(y)
Formalizing this intuition, we introduce the problem of unsupervised learning under Latent Label Shift (LLS). Here, we assume access to collection of domains E (I....,7}, r), where the mixture proportions pa(y) vary across domains but the class conditional distribution p(ælly) is domain- invariant. Our goals are to recover the underlying classes up to permutation, and thus to identify both the per-domain mixture proportions Pa(y) and optimally adapted per-domain classifiers pa(3) zz). The essential feature of our setup is that only the true y's, as characterized by their conss-conditional distributions p(zly), could account for the observed shifts in Pa(x). We prove that under mild assumptions, knowledge of this underlying structure is sufficient for inducing the full set of categories.
First, we focus on the tabular setting, demonstrating that when the input space is discrete and finite, LLS is isomorphic to topic modeling (9. Here, each distinct input x maps to a word each latent label y maps to a lopic and each domain d maps to document. In this case, we can apply standard identification results for topic modeling [22 30 38 14] that rely only on the existence of anchor words within each topic (i.e., for each label y there is at least one in the support of that is not in the support of any y/ * y). Here, standard methods based on Non- nena-ntttiee Matrix Factorization (NMF) can recover each domain's 's underlying mixture proportion pa(y) and optimal predictor Pa(y]ar (1)zz) 22 38 30 However, the restriction to discrete inputs, while appropriate for topic modeling, proves restrictive when our interests extend to digh-dimensional continuous input spaces.
Then, handle high- digh-dimensiooal inputs, we propose Discriminate- Detrriminatte-isccettieeee Fattiie--aatttiz---iiiiie (DDFA), a general framework that proceeds in the following steps: (i) pool data from all domains to produce mixture distribution q(xr, d): (ii) train a domain discriminative model f to predict g(d]a)); (ii) push all data through f. cluster examples in the pushforward distribution, and tabularize the data based on cluster membership: (iv) solve the resulting discrete topic modeling problem (e.g.. via NMF), estimating q(y, d) up to permutation of the latent labels; (v) combine the predicted (d]]x) and q(y, d) to estimate Pa(y) and (z(zz)) In developing this approach, we draw inspiration from recent works distribution shift and learning from positive and unlabeled data that (i) leverage black box predictors to perform dimensionality reduction [46] 25 26 and (ii) work with anchor sets, separable
subsets of continuous input spaces that belong to only one class's 's support (65 49 23 7 26].
Our key theoretical result shows that domain discrimination (g)d provides sufficient represen- tation for identifying all parameters of interest. Given oracle access to (d|[x)) (which is identified without labels), our procedure is consistent. Our analysis reveals that the true q(d]x) maps all points in the same anchor set to single point mass in the push-forward distribution. This motivates our practical approach of discretizing data by hunting for tight clusters in g(d[z) space.
In semi-synthetic experiments, we adapt existing image classification benchmarks to the LLS setting, sampling without replacement construct collections of label-shifted domains. We note that training a domain discriminator classifier is a difficult task, and find that warm starting the initial layers of our model with pretrained weights from unsupervised approaches can significantly boost performance. We show that warm-started DDFA outperforms competitive unsupervised approaches on CIFAR- 10 and CIFAR-20 when domain marginals pa(y) are sufficiently sparse. In particular, we observe improvements of as much as 30% accuracy over recent nigh-performing unsupervised method on CI Further, on subsets of FieldGuide dataset, where similarity between species and diversity within species leads to failure of unsupervised learning, we show that DDFA recovers the true

---

distinctions. To be clear, these are not apples-to-appee -apples comparisons: our methods are specifically tailored to the LLS setting. The takeaway is that the structure of the LLS setting can be exploited to outperform the best unsupervised learning heuristics.
Related Work
Unsupervised Learning Standard unsupervised learning approaches for discovering labels often rely on similarity in the original data space (50 62). While distances in feature space become meaningless for high-dimensional data, deep learning researchers have turned to similarity in a representation space
21 29 12 similarity in feature space learned end-to-end for a clustering task [10 II 57 72 Our problem setup closely resembles independent component analysis (ICA), where one seeks to identify statistically independent signal components from mixtures (39. However, ICA's assumption of statistical independence among the components does not generally hold in our setup. In topic modeling [9 5 38 14 56). documents are modeled as mixtures of topics. and topics as categorical distributions over a finite vocabulary. Early topic models include the well-known Latent Dirichlet Allocation (LDA) () which assumes that topic mixing coefficients are drawn from Dirichlet distribution, along with papers with more relaxed assumptions on the distribution of topic mixing coefficients (e.g.. PISS) 37 (56.. The topic modeling literature
learned via self- supersueee contrastive tasks [53]
often draws on Non-negative Matrix Factorization (NMF) methods (54]
66 which decompose a
31. In both Topic Modeling and NMF, a fundamental problem has been to characterize the precise conditions
given matrix into a product of two matrices with non-negative elements 220
18
28
under which the system is uniquely identifiable (22 B8 [4] The anchor condition (also referred
14 38 22]. In this work, we extend these ideas, leveraging separable subsets of each label's support (the anchor sets) to produce anchor words in the discretized problem. Existing methods have attempted to extend latent variable modeling to continuous input domains by making assumptions about the functional forms of the class-conditional densities, e.g., restricting to Gaussian mixtures [62 60). Recent work in non- parametric mixture modeling [63 73 employs the grouping of unlabeled samples to better identify unknown mixtures, but unlike our setting, each group is known to be sampled only from a single mixture component. A second line of approach involves finding an appropriate discretization of the continuous space [71].
to as separability) is known to be instrumental for identifying topic models [5]
Distribution Shift under the Label Shift Assumption The label shift assumption, where Pa(y) can
vary but p(xly) cannot, has been extensively studied in the domain adaptation literature [64 68 77
(3] 25 and also features in the problem of learning from positive and unlabeled data 24 26
For both problems, many classical approaches suffer from the curse of dimensionality, failing in the settings where deep learning prevails. Our solution strategy draws inspiration from recent work on label shift [46] 1 6 25 and PU learning [8]
26 27 that leverage black-box predictors to produce sufficient low-dimensional representations for identifying target distributions of interest (other works leverage black box predictors heuristically (4I). Key differences: While PU learning requires identifying one new class for which we lack labeled examples provided that the positive class contains an anchor set (26). LLS can identify an arbitrary number of classes (up to permutation) from completely unlabeled data, provided a sufficient number of domains.
49
65
Domain Generalization The related problem of Domain Generalization (DG) also addresses learning with data drawn from multiple distributions and where the domain identifiers play a key role [51 3 However in DG, we are given labeled data from multiple domains, and our goal is to learn classifier that can generalize to new domains. By contrast, LLS, we work with unlabeled data only, leveraging the problem structure to identify the underlying labels.
Learning with Label Noise (LLN) Another problem type that can be viewed under the LLS lens is Learning with Label Noise (LLN) [58] 32 45 [5] 61 70 47 48). This connection can be established as follows: Consider the observed noisy labels to act as domains (see Tp. We then have (i) different distributions over the true labels conditioned on the noisy label; (ii) When conditioned on the true label, the distribution over the input space independent of the noisy label. These observations indicate the satisfaction of LLS setup (see T in LLN, a key difference being the LLN literature typically assumes the distribution over the noisy label has the highest mass at ğ = when the true label y i. The connection between mixture proportion estimation and LLN has been identified in [65] Many methods have been proposed to tackle the L.NN problem: (i) loss correction and surrogate risk minimization [58] 32 65| 52]; (ii) leveraging the predictions of Deep Networks to assign soft labels, as
3

---

D
x
Figure 2: Relationship under Q between observed D, observed X, and latent Y.
70 2 (iii) tapping into the early teacher-student models or in MixUp like augmentations 34 13 61
learning of meaningful patterns by Deep Networks [45 47 67 Of particular relevance is (58), which estimates the Noise Transition Matrix (NTM) and then uses this estimate to retrain under a corrected loss function. [58] shows that "perfect examples" allow for the identification of the NTM (similar to the anchor subdomain assumption which appears in this work). However, [58] use the assumption that when the true label takes certain value, the highest probability mass for the noisy label is also
at the same value-an assumption not always satisfied in our setting. Further, in the LLN problem,
the number of domains and classes are always equal, rendering LLN methods such as (58) incapable of using the information provided by additional domains present in non-L.N settings. Our method
can leverage domain information to provide a domain calibrated classifier, but [58] does not exploit the possible availability of a noisy label at inference. In recent work. [76) use methods from [58] to
connect LLN to learning from multiple bags of samples for which the label proportions are known (similar to our setting, but with more information available in the form of these label proportions).
3 Latent Label Shift Setup
Notation For vector v IR, we use Uj to denote its jth entry, and for an event E, we let I [[ denote the binary indicator of the event. By |A]. we denote the cardinality of set A. With [n], we denote the set {1, 2, ... n... We use [A]k, to access the element at (i,j) in A. Let X be the input space and y = {1, 2, k} be the output space for multiclass classification. We assume throughout this work that the number of true classes k is known. Throughout this paper, we use capital letters to denote random variables and small case letters to denote the corresponding values they take. For example, by X we denote the input random variable and by z, we denote a value that X may take.
We now formally introduce the problem of unsupervised learning under LLS. In LLS, we assume that we observe unlabeled data from r domains. Let R. = {1, (r. be the set of domains. By pa- we denote the probability density (or mass) function for each domain d E R.
Definition (Latent label shift). We observe data from r domains. While the label distribution can differ across the domains, for all d, d' E R and for all (x. E X x V we have pa(æly) = Pa (zly).
Simply put, Definition 1 states that the conditional distribution Pa(=ly) remains invariant across domains, i.e., they satisty the label shift assumption. Thus, we can drop the subscript on this factor, denoting all pa(=)y) by (())). Crucially, under LLS, Pv()) can vary across different domains. Under LLS. we observe unlabeled data with domain label {(21, d2), (I2, d2).... (Ix, d,,) Our goal breaks down into two tasks. Up to permutation of labels, we aim to (i) estimate the label marginal in each domain pa(y); and (ii) estimate the optimal per-domain predictor p))y)
Mixing distribution Q key step in our algorithm will be to train a domain discriminative model. Towards this end we define Q. a distribution over X' x y x R, constructed by taking uniform mixture over all domains. By q, we denote the probability density (or mass) function of Q. Define Q such that q(z,, D d) Pa(x, y). i.e., when we condition
D = d we recover the joint distribution over X' x y specific to that domain d. For all d E R. we define R = q()), i.e.. the prevalence of each domain in our distribution Q. Notice that q(,, y) is mixture over the distributions {pa(x. y) deR. with (Tu)deR as the corresponding mixture coefficients. Under LLS (Definition I.. X does not depend on D when conditioned on Y (Fig.) 2
Additional notation for the discrete case To begin, we setup notation for discrete input spaces with | = m. Without loss of generality, we assume that X' = (1,2,.... ... ..]. The label shift assumption allows us to formulate the label marginal estimation problem matrix form. Let Q be an m x r matrix such that [Q = Pa(X i), i.e., the d-th column of Qxip p is pa(z).. Let Qx be an m x matrix such that [Qx
p(X X i j). the j-th column is a distribution over X given Y = j. Similarly, define Qrip as a k x matrix whose d-th column is the domain marginal paly). Now with Definition I we have pa( Σ,, Pa(2, v) Σ., pa(=)l))a(()) E, p(x())))) Since this is true Vd E R, we can express this in matrix form as Qxip Qxly-Qip

---

Additional assumptions Before we present identifiability results for the LLS problem, we introduce four additional assumptions required throughout the paper:
A.1 There are at least as many domains as classes, i... |R| > |3/
A.2 The matrix formed by label marginals (as columns) across different domains is full-rank, i.e., rank (QQ1)) k.
A.3 Equal representation of domains, i.e., for all d R, 7a=
A.4 Fix e > 0. For all y E V. there exists unique subdomain A, = XX such that ((Ag) 3 and x E Ay and only if the following conditions are satisfied: ((xrl) > and q(>ly)) for all y' E (y).. We refer to this assumption as the c-anchor sub-domain condition.
We now comment on the assumptions. A.1-A.2 are benign, these assumptions just imply that the matrix Qrin is full row rank. Without loss of generality. A.3 can be assumed when dealing with data from a collection of domains. When this condition is not satisfied, one could just re-sample data points uniformly at random from each domain Intuitively, A.4 states that for each label y E V, we have some subset of inputs that only belong to that class To avoid vanishing probability of this subset, we ensure least probability mass in our mixing distribution Q. The anchor word condition is related to the positive sub-domain in PU learning, which requires that there exists subset of X' in which all examples only belong to the positive class [65 23
4 Theoretical Analysis
In this section, we establish identifiability of LLS problem. We begin by considering the case where the input space is discrete and formalize the isomorphism to topic modeling. Then we establish the identifiability of the system in this discrete setting by appealing to existing results in topic modeling (38). Finally, extending results from discrete case, we provide novel analysis to establish our identifiability result for the continuous setting.
Isomorphism to topic modeling Recall that for the discrete input setting, we have the matrix formulation: QXID Qxly QyID. Consider corpus of documents, consisting of terms from vocabulary of size m. Let D be Rmxr matrix representing the underlying corpus. Each column of D represents a document, and each row represents a term in the vocabulary. Each element [D]s. represents the frequency of term in document j. Topic modeling document to be composed as mixture of l topics. Each topic prescribes frequency with which the terms in the vocabulary occur given that topic. Further, the proportion of each topic varies across documents with the frequency of terms given topic remaining invariant.
p 37 38 5
considers each
We can state the topic modeling problem as: D CW, where C is R.nk matrix, [C]s represents the frequency of term i given topic j. and W is an Rexr matrix, where [W],, represents the proportion topic in document j. Note that all three matrices are column normalized. The isomorphism is then between document and domain, topic and label, term and input sample, i.e.,
D CW Q Qx QriD- In both the cases, we are interested in decomposing a known matrix into two unknown matrices. This formulation is examined factorization problem with an added simplicial constraint on the columns (columms sum to 1) 30).
non-negative matrix
Identifiability of the topic modeling problem is well-established [22 5 30 38
[4]
We leverage
the isomorphism to topic modeling to extend this identifiability condition to our LLS setting. We formalize the adaptation here:
Theorem 1. (adapted from Proposition I in Huang et al. (38) Assume A. A.2 and A.4 hold (A.4 in the discrete setting is referved to as the anchor word condition). Then the solution to QxiD= Qx Qyip is uniquely identified up permutation of class labels.
We refer readers to Huang et al. 38 for a proof of this theorem. Intuitively, Theorem I states that each label y has at least one token in the input space that has support only in y, and A. A.2 hold, then the solution to Qxly. Qy is unique. Furthermore, under this condition, there exist algorithms that can recover Q Qyip within some permutation of class labels 38 30 5)
Extensions to the continuous case We will prove identifiability in the continuous setting, when X Rº for some 1. In addition to A.14 make an additional assumption that we have
5

---

oracle access to qdd[z)), i.e., the true domain discriminator for mixture distribution Q. This is implied by assuming access to the marginal q(x, d) from which we observe our samples. Formally, we define push forward function J' such that [[(]]]] g(dlar) then push the data forward through f to obtain outputs in A In the proof of Theorem 2 we will show that these outputs can be discretized in a fashion that maps anchor subdomains to anchor words in tabular, discrete setting. We separately remark that the anchor word outputs are in fact extreme corners of the convex polytope in A A which encloses all f(x) mass; we discuss this geometry further in App. F After constructing the anchor word discretization, we appeal to Theorem I to recover QY L Given QyiD. we show that we can use Bayes' rule and the L.LS condition (Definition)) T to identify the distribution q(y|,, (r, d) = pa(ylz) over latent variable y. We formalize this in the following theorem:
Let the distribution Q over random variables X.Y.D D satisfy Assumptions A.1-A.4. Assuming access to the joint distribution q(æ, d), and knowledge of the number of true classes k. we show that the following quantities are identifiable: (i) QylD. (ii) q(yl = x),, for all x E X that lies in the support (i.e. q(x)= > 0); and (iii) g(ulx = x, D- = d) for all z E X' and d e such that q(x, d) 0.
Theorem 2.
Before presenting proof sketch for Theorem 2 we first present key lemmas (we include their proofs in App. A).
Lemma 1. Under the same assumptions as Theorem 2 the matrix Qy and f(x) = (d](x)) uniquely determine ( for all y E y and x E X such that q(x) > 0.
Lemma I states that given matrix Q and oracle domain discriminator, we can uniquely identify (()(2)). In particular, we show that for any E X, q(d[xx) can be expressed as a convex combination of the i columns of QDIY (which is computed from Qyjd and is column rank k) and the coefficients of the combination are ( Combining this with the linear independence of the columns of Qnly,
we show that these coefficients unique. In the following lemma, we show how the identified ((y(z)) can then be used to identify quulor, d):
Lemma 2. Under the same assumptions as Theorem for all y E V. and x E X such that q(z, d) > O. the matrix QYiD and ((ylær) uniquely determine q xr d).
To prove Lemma 2 we show that we can combine the conditional distribution over the labels given a sample x X' with the prior distribution of the labels in each domain to determine the posterior distribution over labels given the sample x and the domain of interest. Next, we introduce a key property of the domain discriminator classifier f:
Lemma Under the same assumptions as Theorem 2 for all x, in anchor sub-domain, i.e. x, x' E Ay given label y e V, we have f(x) = f(x') Further, for any y E V, if E Ag, x' $ Ay then (()) # f(x').
Lemma 3 implies that the oracle domain discriminator / maps all points in an anchor subdomain, and only those points in that anchor subdomain to the same point in f(xx g(dlzz) space. We can now present proof sketch for Theorem (full proof in App. B
Proof sketch of Theorem 2 The key idea of the proof lies in proposing a discretization such that some subset of anchor subdomains for each label y in the continuous space map to distinct anchor words in discrete space. In particular, if there exists a discretization of the continuous space X' that for any y E V. maps all x Ay to the same point in the discrete space, but no x & Ay maps to this point, then this point serves as an anchor word. From Lemma 3] we know that all the x Ay and only the x e Ay get mapped to specific points in the f (x)) space. Pushing all the E X' through f. we know from A.4 that there exists k point masses of size e, one for each f(A,)) in the f(x = q( d),z) space. We can now inspect this space for point masses of size at least to find at most ((/-c) such point masses among which are contained the k point masses corresponding to the anchor subdomains. Discretizing this space by assigning each point mass to a group (and non-point masses to a single additional group), we have k groups that have support only in one each. Thus, we have achieved a discretization with anchor words. Further, since the discrete space arises from a pushforward of the continuous space through f. the discrete space also satisfies the latent label shift assumption A. We now use Theorem I to claim identifiability of Qy We then use Lemmas and to prove parts (ii) and (iii).

---

5 DDFA Framework
Motivated by our identifiability analysis, in this section, we present an algorithm to estimate Qrip: q (ulaz), and g(y|x, d) when X is continuous by exploiting domain structure and approximat- ing the true domain discriminator f. Intuitively, {(y|ær, d) is the domain specific classifier Pa(y) (z:) and ((y(2) is the classifier for data from aggregated domains. QrID captures label marginal for individ- ual domains. A naive approach would be to aggregate data from different domains and exploit recent advancements in unsupervised learning 72
57 10 II]. However, aggregating data from multiple do- mains loses the domain structure that we hope leverage. We highlight this failure mode of the tradi- We remark that DDFA draws heavy inspiration from the proof of Theorem 2 but we do not present guarantee that the DDFA solution will converge to the identifiable solution. This is primarily due to the K-means clustering heuristic we rely on, which empirically offers effective noise tolerance, but theoretically has no guarantee of correct convergence.
tional unsupervised clustering method in Sec. 6
Discriminate We begin Algorithm by creating a split of the unlabeled samples into the training and validation sets. Using the unlabeled data samples and the domain that each sample originated from, we first train a domain discriminator f. The domain discriminator outputs a distribution over domains for a given input. This classifier is trained with cross-entropy loss predict the domain label of each sample on the training set. With unlimited data, the minimizer of this loss is the true /, as we prove in App. To avoid overfitting, validation set stops decreasing. Note that here the validation set also only contains domain indices (and no information about true class labels).
stop training ʃ when the cross-entropy loss on the
Discretize We now push forward all the samples from the training and validation sets through the domain discriminator get vector f(z;) for each sample r;. In the proof of Theorem [ argue that when working with true f. and the entire marginal q(z, d), we can choose a discretization satisfying the anchor word assumption by identifying point masses in the distribution of f(x) and filtering to include those of at least mass. In the practical setting, because we have only finite set of data points and noisy f. we use clustering to approximately find point masses. We choose > A and recover m clusters with any standard clustering procedure (e.g. g. K-means). This clustering procedure is effectively useful, but imperfect heuristic: if the noise in is sufficiently small and the clustering sufficiently granular, we hope that our m discovered clusters will include k pure clusters, each of which only contains data points from different anchor subdomain which are tightly packed around the true (Ay) for the corresponding label y. Clustering in this space is superior to a naive clustering on the input space because close proximity in this space indicates similarity in g(d[x))
Let us denote the learned clustering function as c, where c(x) is the cluster assigned to a datapoint x. We now leverage the cluster id c(x:)) of each sample x; to discretize samples into a finite discrete space [m]] Combining the cluster id with the domain source d, for each sample, we estimate Qo(X)] by simply computing, for each domain, the fraction of its samples assigned to each cluster.
Factorize We apply an NMF algorithm to Q D to obtain estimates of Qe(x)) y and Qyin.
Adjust We begin Algorithm by considering test point (x', d'), ). To make a prediction, if we had access oracle f and true Qy we could precisely compute (y(a²') (Lemma [). However, in place of these true quantities, we plug in the estimates f and Qyjp- Since our estimates contain noise, the estimate ç[y|=') is found by left reft-multiplying f(=') with the pseudo-inverse of Q as opposed to solving a sufficient system of equations. As our estimates f and Q approach the true values, the projection of f(x') into the column space of QDIY tends to f(x') itself, so the peudo-inverss, approaches the true solution. Now we can use the constructive procedure introduced in the proof of Lemma 2 to compute the plug-in estimate Ç d') = Par (y(l)')).
6 Experiments
Experiment code is available
Baselines We select the unsupervised classification method SCAN, as a high-performing competitive
baseline 772. SCAN pretrains a ResNet (35] backbone using SimCLR [12 and MoCo (36 setups
(pretext tasks). SCAN then trains a clustering head to minimize the SCAN loss (refer 772 for more
7

---

Algorithm DDFA Training
input k > 1 a k, Ha, dej g(2r, d), A class of functions F from RP 1: Split into train set T and validation set V
2: Train f F to minimize cross entropy loss for predicting d on T with early stopping on
3: Push all (an)) through f
4: Train clustering algorithm on the n points (f(z))ke(=)) obtain m clusters.
5: e(xx)) Cluster id of f(x;)
6: [(((X) = b) Listal [((z)))a d.-b]
2 [d]=
7: Populate Qe(X)) as [ocxyyplos - ((c(X) = a/D b)
8: Qu(X))) QyID - NMF (Q(())))
output QyID.
Algorithm 2 DDFA Prediction
input QrID. (v', d') g(ar,d)
1: Populate QDYY as [QDiy lav
2: Assign X(y]X = x') (Qm)) f(x1)
3: Assign 7(11 = x', D = d') - (Qr x²)
Σ
" xx)
4: Spred + arg.max..ls. 0ly|X = d',D=='
output T x', = d') = (r((v)))) auy x²). Mpreed
details) We do not use the SCAN self-labeling step. We make sure to evaluate SCAN on the same potentially class-imbalanced test subset we create for each experiment. Since SCAN is fit superset of the data DDFA sees, we believe this gives a slight data advantage to the SCAN baseline (although we acknowledge that the class balance for SCAN training also potentially different from its evaluation class balance). To evaluate SCAN, we use the public pretrained weights available for CIFAR-10. 10, CIFAR-20. and ImageNet-50 We also train SCAN ourselves on the train and validation portions of the FieldGuide2 and FieldGuide28 datasets with a ResNet18 backbone and SimCLR pretext task. We replicate the hyperparameters used for CIFAR training.
Datasets First we examine standard multiclass image datasets CIFAR-10, CIFAR-20 20 43 and
ImageNet-50 [19 containing images from 10, 20, and 50 classes respectively. Images in these datasets typically focus on a single large object which dominates the center of the frame, so unsupervised classification methods which respond strongly similarity in visual space are well-suited to recover true classes up to permutation. These datasets are often believed to be separable (i.e., single true label applies each image), so every example falls in an anchor subdomain (satisfying A.4).
Motivated by the application of LLS problem, we consider the FieldGuide dataset F which contains images of moths and butterflics. The true classes in this dataset are species, but each class contains images taken in immature (caterpillar) and adult stages of life. Based on the intuition that butterflics from given species look more like butterflies from other species than caterpillars from their own species, we hypothesize that unsupervised classification will learn incorrect class boundaries which distinguish caterpillars from butterflies, as opposed recovering the true class boundaries. Due to high visual similarity between members of different classes, this dataset may indeed have slight overlap between classes. However, we hypothesize that anchor subdomain still holds, i.e., there exist some images from each class that could only come from that class. Additionally, if we have access to data from multiple domains, it is natural assume that within each domain the relative distribution of caterpillar to adult stages of each species stay relatively constant as compared to
PSCAN code: http:///wtaaaaaa.//////////////a
2019

---

Table Results on CIFAR-20. Each entry produced with the averaged result of different random seeds. With DDFA (RI) we refer to DDFA with randomly initialized backbone. With DDFA (SI) we refer to DDFA's backbone initialized with SCAN. Note that in DDFA (SI), we do not leverage SCAN for clustering. is the Dirichlet parameter used for generating label marginals in each domain, is the maximum allowed condition number of the generated Qyjp matrix, number of domains.
a: 0.5, R.
3, K 12
a: 10, K: 20
r
Approaches
Test acc
QriD em
Test acc
Qy err
Test acc
Qyip
SCAN
0.454
0.059
0.421
0.051
0.436
0.038
20
DDFA (RI)
0.520
0.041
0.357
0.043
0.187
0.051
DDFA (SI)
0.852
0.015
0.548
0.026
0.354
0.036
SCAN
0.458
0.059
0.455
0.048
0.440
0.037
25
DDFA (RI)
0.525
0.042
0.310
0.051
0.182
0.053
DDFA (SI)
0.819
0.021
0.707
0.022
0.502
0.030
SCAN
0,456
0.059
0,441
0.050
0,437
0.037
30
DDFA (RI)
0.506
0.045
0.256
0.058
0.088
0.076
DDFA (SI)
0.845
0.020
0.688
0.027
0.531
0.029
prevalence of different species. We create two subsets of this dataset: FieldGuide2, with two species, and FieldGuide28, with 28 species.
LLS Setup The full sampling procedure for semisynthetic experiments is described in App. D Roughly, we sample paly) from symmetric Dirichlet distribution with concentration e/s, where is the number of classes and a is a generation parameter that adjusts the difficulty of the synthetic problem, and enforce maximum condition number y on Q Small a and small к encourages sparsity in Q so each label tends to only appear in a few domains, Larger parameters encourages pa(y) to tend toward uniform. We draw from test, train, and valid datasets without replacement to match these distributions, but discard some examples due class imbalance.
Training and Evaluation The algorithm uses train and validation data consisting of pairs of images and domain indices. We train ResNet50 331 (with added dropout) images x, with domain indices d; as the label, choose best iteration by valid loss, pass all training and validation data through f. and cluster pushforward predictions f(x;) into m > k clusters with Faiss K-Means Qe(X)) matrix and run NMF to obtain Qe(x))x) QyID. To make columns sum to 1, we normalize columns of Qo(x))y multiply each column's normalization coefficient over the corresponding row of QyiD (to preserve correctness of the decomposition). and then normalize columns of Qy Some NMF algorithms only output solutions satisfying the anchor word property 4 44 (3). We found the strict requirement of an exact anchor word solution to lead to low noise tolerance. We therefore use
We compute the
the Sklearn implementation of standard NMF 15 69 55].
We instantiate the domain discriminator as ResNet18, and preseed its backbone with SCAN 72 pre-trained weights or (72) contrastive pre-text weights. We denote these models DDFA (SI) and DDFA (SPI) respectively. We predict class labels with Algorithm 2 With the Hungarian algorithm, implemented in 16 74, we compute the highest true accuracy among any permutation of these labels (denoted "Test acc"). With the same permutation, we reorder rows of PyID. then compute the average absolute difference between corresponding entries of Qyip and QyiD (denoted "QyiD err").
Results On CIFAR-10, we observe that DDFA alone incapable of matching highly competitive baseline SCAN performance--hweeee in suitably sparse problem settings (small a), it comes substantially close, indicating good recovery of true classes. Due to space constraints, we include 100 results in App. E DDFA (SI) combines SCAN's strong pretrain with domain discrimination fine-tuning to outperform SCAN the easiest, sparsest setting and certain denser settings. On CIFAR-20, baseline SCAN is much less competitive,
DDFA(SD) dominates baseline SCAN in all settings except the densest (Table ( These results demonstrate how adding domain information can dramatically boost unsupervised baselines.

---

On FieldGuide-2, DDFA (SPI) outperforms SCAN baselines in accuracy across all but the densest settings (Table[5; in sparser settings, the accuracy gap 10-30%. In this dataset. SCAN performs only slightly above chance, reflecting perhaps total misalignment of learned class distinctions with true species boundaries. We do not believe that SCAN too weak to effectively detect image groupings on this data; instead we acknowledge that the domain information available to DDFA (SPI) (and not to SCAN) is informative for ensuring recovery of the true class distinction between species as opposed to the visually striking distinction between adult and immature life stages. We do note that, oddly, SCAN tends to better recover the Qy matrix in harder settings. On FieldGuide-22 (Table 6). DDFA accuracy outperforms SCAN baseline accuracy in all evaluated sparsity levels, with the highest observed accuracy difference ranging above 30-40%.
Conclusion
Our theoretical results demonstrate that under LLS, we can leverage shifts among previously seen domains to recover labels in purely unsupervised manner, and our practical instantiation of the DDFA framework demonstrates both (i) the practical efficacy of our approach; and (ii) that generic unsupervised methods can play key role both in clustering discriminator outputs, and providing weights for initializing the discriminator. We believe our work is just the first step in new direction for leveraging structural assumptions together with distribution shift to perform unsupervised learning,
7.1 Future Work and Limitations
Assumptions Our approach is limited by the set of assumptions needed (label shift, as many data domains as true latent classes, known true number of classes k, and other assumptions established in A.1-A.4). Future work should aim relax these assumptions.
Theory The work does not include finite sample bounds for the DDFA algorithm. In addition, we do not have formal guarantee that the clustering heuristic in the Discretize step of DDFA will retrieve pure anchor sub-domain clusters under potentially noisy black-box prediction of gdd[x)) This problem is complicated by the difficulty of reasoning about the noise that may be produced by neural network or other complex non-linear model (acting as the black-box domain discriminator), and by the lack of concrete guarantees that K-means will recover the anchor subdomains among its recovered musters-esspciallle when classes overlap.
DDFA Framework Within the LLS setup. several components of the DDFA framework warrant further investigation: (i) the deep domain discriminator can be enhanced in myriad ways; (ii) for clustering discriminator outputs, we might develop methods specially tailored to our setting replace the current generic clustering heuristic; (iii) clustering might be replaced altogether with geometrically informed methods that directly identify the corners of the polytope; (iv) the theory of LLS can be extended beyond identification to provide statistical results that might hold when (dl] can only be noisily estimated, and when only finite samples are available for the induced topic modeling problem; (v) when the number of true classes k is unknown, we may develop approaches to estimate this k.
Semi-synthetic Experiments Semi-synthetic experiments present an ideal environment for evalu- ating under the precise label shift assumption. Evaluating on datasets in which the separation into domains is organic, and the label shift is inherent is an interesting direction for future work.
Acknowledgements
SG acknowledges Amazon Graduate Fellowship and JP Morgan PhD Fellowship for their support. ZL acknowledges Amazon AI, Salesforce Research, Facebook, UPMC, Abridge, the PwC Center, the Block Center, the Center for Machine Learning and Health, and the CMU Software Engineering Institute (SEI) via Department of Defense contract FA8702-15-D-0002 for their generous support of ACMI Lab's 's research on machine learning under distribution shift.
10

---

References
[1] Amr Alexandari, Anshul Kundaje, and Avanti Shrikumar. Adapting to label shift with bias- corrected calibration. In International Conference Machine Learning (ICML), 2019.
[2] Eric Arazo, Diego Ortego, Paul Albert, Noel O' C'nnnor, and Kevin McGuinness. Unsupervised label noise modeling and loss correction. In International Conference Machine Learning, pages 312-321. PMLR, 2019.
[3] Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk mini- mization, arXiv preprint arXiv: /90i::/900.000 900.00899, 2019.
[4] Sanjeev Arora, Rong Ge, Ravindran Kannan, and Ankur Moitra. Computing a nonnegative matrix factorization - provably. In Symposium on Theory of Computing (STOC), 2012. doi: 10.1 (0.1144//213977722113999
https://://ddo
10. 1..0..144 2211977 2213999
[5] Sanjeev Arora, Rong Ge, and Ankur Moitra. Learning topic models-going beyond svd. In Foundations of Computer Science (FOCS). IEEE, 2012.
[6] Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang. and Animashree Anandkumar. Regularized learning for domain adaptation under label shifts. In International Conference on Learning Representations (ICLR), 2019.
[7] Jessa Bekker and Jesse Davis. Estimating the class prior in positive and unlabeled data through decision tree induction. In Association for the Advancement of Artificial Intelligence (AAAI), vol- ume 32, 2018. URL https:///jsssst aaai org/ index php Abtp/AAAT/arriicle/iee//////
[8] Jessa Bekker and Jesse Davis. Learning from positive and unlabeled data: survey. Machine Learning, 109(4):719-76/) apr 2020. doi: 10. 10.10077/100944402000 org
[9] David M Blei, Andrew Y Ng, and Michael I Jordan. Latent dirichlet allocation. Journal of Machine Learning research, 3(Jan):933-1022 2003.
[10] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In Proceedings of the European conference on computer vision (ECCV), pages 132-149, 2018.
[11] Mathilde Caron, Piotr Bojanowski, Julien Mairal, and Armand Joulin. Unsupervised pre- training of image features non-curated data, 2019. httph:tps: http://wwwwww..ooo// iccc__ccc_1l______
cv- foufonntttion Lissasee__d_ss_a__deeea_aa Visual.
content. iccv 2015/ hatppaaprrs////// SaperssDoersch. Doersch Unsupervisudddd
Representationn ICCV 2015 2015--_pppr..__ .pdf]
[12] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference machine learning (ICML), pages 1597-1607. PMLR, 2020.
[13] Yingyi Chen, Xi Shen, Shell Xu Hu, and Johan AK Suykens. Boosting co-teaching with compression regularization for label noise. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2688-2692. 2692, 2021.
[14] Yinyin Chen, Shishuang He, Yun Yang, and Feng Liang. Learning topic models: Identifiability and finite-sample analysis. arXiv preprint arXiv:2110.042:2 2021.
[15] Andrzej Cichocki and Anh-Huy Phan. Fast local algorithms for large scale nonnegative matrix and tensor factorizations. IEICE Transactions, 22-A:708-721, 03 2009. doi: 10. 10.15877transfun. E92.A.708.
[16] David F Crouse. On implementing 2d rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems, 52(4):1679-1666, 2016.
[17] Luke Darlow, Elliot Crowley, Antreas Antoniou, and Amos Storkey. Cinic-10 10 is not. imagenet cifar- 10, 2018. URL : //t/xxxxivv///////////e/////atl/ www.vvo.gggaaaa www.oogggg//b..e..ooooo
hwwp///0...... 03505
11

---

[18] Thiago de Paulo Faleiros and Alneu de Andrade Lopes. On the equivalence between algorithms for non-negative matrix factorization and latent dirichlet allocation. In European Symposium on Artificial Neural Networks (ESANN), 2016.
[19] Jia Deng. Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Ieee, 2009.
[20] Chris Ding, Tao Li, and Wei Peng. On the equivalence between non-negative matrix factorization and probabilistic latent semantic indexing. Computational Statistics & Data Analysis, 52(8): 3913-3927, 2008
[21] Carl Doersch, Abhinav Gupta, and Alexei A. Efros. Unsupervised visual representation learning by context prediction. In International Conference on Computer Vision (ICCV), 2015. URL https: wy-foundation... org/ /ppnaacceeee//oottetniiiyy 2015/ papers httpe//DDrrrcc__uuuueeeeeee
pdf
[22] David Donoho and Victoria Stodden. When does non-negative matrix factorization give correct decomposition into parts? Advances in Neural Information Processing Systems (NeurIPS), 16, 2003.
[23] Marthinus C. du Plessis, Gang Niu, and Masashi Sugiyama. Class-prior estimation for learning from positive and unlabeled data. Machine Learning, 106(4):463 492 nov 2016. doi: 10.1007/ s $10994-016-5604
URL httpp:///oo. org/ 100077765100944011666666-0
[24] Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 213-220, 2008.
[25] Saurabh Garg, Yifan Wu, Sivaraman Balakrishnan, and Zachary Lipton. A unified view of label shift estimation. In Advances in Neural Information Processing Systems (NeurIPS), 2020. URL https://arxixs wwtpsiiv.rrr//ooooooeeo abs 07554
[26] Saurabh Garg, Yifan Wu, Alex Smola, Sivaraman Balakrishnan, and Zachary Lipton. Mixture proportion estimation and PU learning: A modern approach. In Advances in Neural Information Processing Systems (NeurIPS), 2021. https/ttss///axii org/ ab/aa/as//111// 20980
[27] Saurabh Garg, Sivaraman Balakrishnan, and Zachary Lipton. Domain adaptation under open set label shift. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[28] Eric Gaussier and Cyril Goutte. Relation between plsa and nmf and implications. In Conference on Research and Development Information Retrieval (SIGIR), 2005.
[29] Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations, 2018. URL. httpst//s///ssttt http://::///aavvoooo/a/abaaa abs 1803 07728
[30] Nicolas Gillis and Stephen A. Vavasis. Fast and robust recursive algorithms for separable non- negative matrix factorization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(4):698 714, apr 2014. doi: 10. 1.09///ami.2013.220 URL https: org/1or./// 1137% 2F130946782
[31] Mark Girolami and Ata Kabán. On an equivalence between plsi and Ida. In Conference on Research and Development Information Retrieval (SIGIR), 2003.
[32] Jacob Goldberger and Ehud Ben-Reuven. Training deep netral-networks using noise adapta- tion layer. In International Conference on Learning Representations, 2017.
[33] Jiaxian Guo, Mingming Gong, Tongliang Liu, Kun Zhang, and Dacheng Tao. Ltf: A label transformation framework for correcting label shift. In International Conference on Machine Learning, pages 3843-3853 PMLR, 2020.
[34] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
12

---

[35] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recogni- lion (CVPR), 2016.
[36] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pages 9729-9738, 2020.
[37] Thomas Hofmann. Probabilistic latent semantic indexin.. In Conference on Research and Development in Information Retrieval (SIGIR), 1999.
[38] Kejun Huang, Xiao Fu, and Nikolaos Sidiropoulos. Anchor-free correlated topic modeling: Identifiability and algorithm. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
[39] Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications. Neural networks, 13(4-5):411 1-400, 2000.
[40] Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications. Neural networks, 13(4-)):4114333 1-4300 2000.
[41] Dmitry Ivanov. DEDPUL: Diffrrenee----esiittttdddiiiisse oaapa//ddeeeittiioooosossseeaaaa arXiv preprint arXiv: 1902.06965, 2019.
positive-unllbeled learning.
[42] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535-555 5478 2019.
[43] Alex Krizhevsky and Geoffrey Hinton. Learning Multiple Layers of Features from Tiny Images. Technical report, Citeseer, 2009.
[44] Abhishek Kumar, Vikas Sindhwani, and Prabhanjan Kambadur. Fast conical hull algorithms for near-separable non non-negatin -eg-nettevv matrix factorization. In International Conference on Machine Learning, pages 231-239. PMLR, 2013.
[45] Junnan Li, Richard Socher, and Steven C.H. Hoi. Dividemix: Learning with noisy labels as semi-supervised learning. In International Conference on Learning Representations, 2020.
[46] Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International Conference on Machine Learning (ICML). PMLR, 2018.
[47] Sheng Liu, Jonathan Niles- Weed, Narges Razavian, and Carlos Grmnandez-Grandee Early- learning regularization prevents memorization of noisy labels. Advances in Neural Information Processing Systems (NeurIPS), 33:20331-20342, 2020.
[48] Sheng Liu, Zhihui Zhu, Qing Qu, and Chong You. Robust training under label noise by over- paramcterization. arXiv preprint urXiv:2202.14026. 2022.
[49] Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting.
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 38(3):447-461, mar 2016. doi: 10.1 http://ppaa..2..5255555555 2456899
URI. https: //doi. org/ 1109% 2015
[50] James MacQueen et al. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, pages 281-297. Oakland, CA, USA, 1967.
[51] Krikamol Muandet, David Balduzzi. and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International Conference on Machine Learning (ICML)..
PMLR, 2013.
[52] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances in Neural Information Processing Systems (NeurIPS), 26, 2013.
13

---

[53] Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. In European conference on computer vision, pages 69-84. Springer, 2016.
[54] Pentti Paatero and Unto Tapper. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics, 5(2: 1994.
[55] Daniel Paleka and Amartya Sanyal. A law of adversarial risk, interpolation, and label noise. arXiv preprint arXiv:2207.03933, 2022.
[56] Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, and Santosh Vempala. Latent semantic indexing: A probabilistic analysis. Journal of Computer and System Sciences, 61()): 217-235, 2000.
[57] Sungwon Park, Sungwon Han, Sundong Kim, Danu Kim, Sungkyu Park, Seunghoon Hong, and Meeyoung Cha. Improving unsupervised image clustering with robust learning. CoRR, abs/2012.11150, 2020. URLpstts: http:/s.///xxvvvvv//// www./ag.////oooooooe/.../ee.eee/ abs 11150
[58] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1944-1952, 2017.
[59] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research (JMLR), 12, 2011.
[60] Kedar S Prabhudesai, Boyla O Mainsah, Leslie M Collins, and Chandra S Throckmorton. Augmented latent dirichlet allocation (Ida) topic model with gaussian mixture topies. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2451-2455. IEEE, 2018
[61] Scott E. Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and An- drew Rabinovich. Training deep neural networks on noisy labels with bootstrapping. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015. URL butp://arxisn orriiivorrg/aae oww/org.........o... berg/abs/144 /atss/111..660 6596
[62] Douglas A Reynolds. Gaussian mixture models. Encyclopedia of biometrics, (6596-66)))) 2009.
[63] Alexander Ritchie, Robert A Vandermeulen, and Clayton Scott. Consistent estima- tion of identifiable nonparametric mixture models from grouped observations. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 11676-11686. Curran As- sociates, Inc., 2020. URL (BGG54aa0071ac/00046666666666668
www.ineu.rccocooeoo /ttppppps.c.//pppp//////////e/// .pff
[64] Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the Outputs of a Classifier to New Priori Probabilities: A Simple Procedure. Neural Computation, 2002.
[65] Clayton Scott. A Rate of Convergence for Mixture Proportion Estimation, with Application to Learning from Noisy Labels. In Artificial Intelligence and Statistics (AISTATS), 2015. URL httpps://proceedinggs mlr pta...rrrres//////ttttsss html
[66] Seung and I. Lee. Algorithms for non-negative matrix factorization. In Advances in neural information processing systems (NeurIPS), 2001.
[67] Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss minimization. In International Conference on Machine Learning, pages 5739-5748. PMLR, 2019.
[68] Amos Storkey. When training and test sets are different: characterizing learning transfer. Dataset shift in machine learning, 30:3-28, 2009.
14

---

[69] Vincent YF Tan and Cédric Févotte. Automatic relevance determination in nonnegative matrix factorization with the/spl beta/ diverrevveeec IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 35(7), 2012.
[70] Daiki Tanaka, Daiki Ikami, Toshihiko Yamasaki, and Kiyoharu Aizawa. Joint optimization framework for learning with noisy labels. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5552-5560, 2018.
[71] Dongping Tian. Research plsa model based semantic image analysis: A systematic review. J. Inf. Hiding Multim. Signal Process., 9()): 109-1199-1113, 2018.
[72] Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, Marc Proesmans, and Luc Van Gool. Scan: Learning classify images without labels, 2020. URL https://arxiv
org/abs/2005.00 2000..22..22
[73] Robert A. Vandermeulen and Clayton D. Scott. An operator theoretic approach to nonparametric mixture models. The Annals of Statistics, 47(5) 2733, 2019. doi: 10. (0.1214/18-AOS1762
URL htttsss////dol org/ 10. 1144/18-A0S1785
[74] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapcau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Erie Jones, Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul Mulbregt, and SeiPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10. 11000//411992 050889941592-01--6866-222
[75] Svante Wold, Kim Esbensen, and Paul Geladi. Principal component analysis. Chemometrics and intelligent laboratory systems, 2(1-3):37-52 1987.
[76] Jianxin Zhang, Yutong Wang, and Clayton Scott. Learning from label proportions by learning with label noise. arXiv preprint urXiv:2203.02496, 2022.
[77] Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. International Conference on Machine Learning (ICML). PMLR, 2013.
15

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts your work? [N/A] We believe that this work, which proposes novel unsupervised learning problem does not present a significant societal concern. While this could potentially guide practitioners to improve classification, we do not believe that it will fundamentally impact how machine learning is used a way that could conceivably be socially salient.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Sec. 3
(b) Did you include complete proofs of all theoretical results? [Yes] See Sec. and appendices
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We include all the necessary details replicate our experiments in appendices. Code URL is given in the paper.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Yes, we describe crucial details in Sec. and defer precise details to appendices.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] We include error bars for all main paper experiments and ablations.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] Refer to experimental setup in App.D)
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Refer to experimental
setup in App. D
(b) Did you mention the license of the assets? [Yes] Refer to experimental setup in App. D
(c) Did you include any new assets either the supplemental material or as URL.? (ess) Refer to experimental setup in App. D
(d) Did you discuss whether and how consent obtained from people whose data you 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "p9_HGg2Y8W5", "reviewer": "Reviewer_3GNB", "summary": "This work tackles the unsupervised learning problem under latent label shift. In this problem, each data point has a domain label, but the true classification label is not available. The key underlying assumption is that the class conditional distribution is domain invariant, while the distribution of labels in each domain affects the final data distribution. To resolve this problem, this paper relates it to the classical topic modeling problem and further extends its framework to the continuous domain. Empirically, the proposed method outperforms the SCAN method on CIFAR and FieldGuide datasets.", "questions": "1. Note that the 'pre-training backbone' step still relies on the feature-space similarity assumption. I doubt whether the main goal of this work that 'unsupervised learning can work beyond feature similarity' still holds? Or maybe similarity learning is still an essential step for unsupervised learning, but this work takes a further step on a coarser granularity? For example, we still have to find the sub-clusters of caterpillars and butterflies, but they belong to the same super-cluster. \n\n2. How does DDFA (RI) perform on FieldGuide datasets? It's weird that different variants of DDFA are used on different datasets.\n\n3. On the FieldGuide-2 dataset, the Q{Y|D} error seems to be high, why? Why is the final performance not affected by a bad estimation of Q_{Y|D}? \n\n4. Are the limitations of this work described anywhere? I notice that the authors answered Yes in the checklist. ", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n1. While current unsupervised learning techniques are mostly driven by the similarity assumption among data points, this work helps understand the conditions in which unsupervised learning is possible. I believe this work brings new insights to the community.\n2. The linkage between the LLS problem with the topic modeling is intuitive and convincing.\n3. This work is original and well-written. \n\nCons:\n\n1. My main concern lies in the clustering step in their algorithm, which is mainly designed to discretize the input such that they act like words. This can be problematic in the high-dimensional case, where the identifiability assumption can also fail. I suppose this is the reason that DDFA relies on a well-trained backbone in experiments. \n2. The experiments are sort of weak; see my question below.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "J9MKwCPiZXP", "reviewer": "Reviewer_tzBv", "summary": "The authors introduce a novel general framework, referred to as Discriminate-Discretize-Factorize-Adjust (DDFA), for unsupervised learning under Latent Label Shift (LLS). With semi-syntheitc experiments, the authors show that the developed DDFA can leverage domain information to improve the performance of unsupervised classification.", "questions": "As far as I known, this work could be the first one to apply topic model to unsupervised learning under label shift. It does bring a lot of new ideas to me about how to make full use of topic models under multi-domain scenarios.\n\nThe whole work is built under the assumption of label shift, and all experiments are conducted with semi-syntheitc datasets. As the paper said, ``if we notice that whenever, ....we might conclude that the two were tied to the same underlying concept.’’, I absolutely agree with the point that topic model can be used to capture these co-occurrence patterns. \n\nHowever, what if the assumption does not hold in the dataset. For instance, in the first domain, all dogs are under sun, but in the second domain, all dogs are under the moonlight. In that case, I assume that the topic models can hardly summarize these dogs into the same topic, and the developed DDFA will also fail.\n\nSo, I think the authors had better to prove whether the assumption really hold in real-world dataset, rather than use semi-syntheitc experiments.Then, it will be better to discover or visualize the underlying principle capture by DDFA, e.g, the amount of butterfly and caterpillar will shift together.\n\nAdditional Question\n\nIn Algorithm 2, it is quite confused to me that how you can obtain q(y|x) with Q(D|Y) and f(x). In my consideration, for a topic model, given a word x in the document d, it is unable to infer which topic the word assigned to.  So, which assumption can be used to infer the topic index y for each word x. You had better reexplained it under the scenario of topic model.\n", "limitations": "The novelty is high but the assumption is too idealistic.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The principle ``instances that shift together group together’’ is interesting, and the authors creatively utilize topic model to capture these shits across various domains\n\n2) The paper is well-organized and the proof is very rigorous.\n\nWeakness:\n\n1) My only concern is whether the label shift assumption exists in real-world datasets. Refer to the question part for details.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BbgLFG9f4b", "reviewer": "Reviewer_GfX1", "summary": "Traditional unsupervised learning methods involve clustering according to similarity in some representation space. However, the true labels may not align with such clusters, for instance, if the clusters learn a spurious feature instead (such as adult versus caterpillar for moth versus butterfly classification). Instead, this paper proposes an unsupervised learning technique based on label shifted domains; that is, given unlabeled datasets coming from different domains where $p(x|y)$ stays the same (e.g. the within-class structure) but $p(y)$ changes, such as across time and location, we can uniquely recover the labels of points. First, the paper considers the tabular setting and draws an equivalence to topic modeling, where points are words, domains are documents, and labels are topics. A simple set of assumptions is presented for recoverability through non-negative matrix factorization. The next challenge is extending such an approach to continuous data. This is done by clustering examples based on the vectors $[p(d|x)]_d$ approximated by a classifier over the domains, performing the topic modeling approach on the discretization, and converting recovered quantities back to $p(y|d, x)$ using Bayes rule and the classifier. They show that on real-world datasets where feature space similarity does not imply the same label, this approach is able to outperform other unsupervised learning methods given synthetically induced label shifts.\n", "questions": "**Q1.** Could this approach be applied to the Waterbirds dataset (https://github.com/kohpangwei/group_DRO)? Would we expect it to do well? This is similar to FieldGuide, and I imagine that when naive clustering is done, things will be clustered by the birds’ background, which tends to dominate the image. I’m also curious what the effect of subgroup imbalance is here, since there are few land birds in water and few water birds on land. Equivalently, in FieldGuide, are there roughly the same amount of immature and adult moths/butterflies? Is your approach robust to these imbalances? \n\n**Q2.** The importance of discretizing with f(x) could be made clearer by performing an ablation on some naive representation space. \n\n**Q3.** Presentation-wise, it is not clear to me how theorem 2 and DDFA are related. I believe the connection is that asymptotically, DDFA satisfies theorem 2, but this is not explicit enough. Furthermore, a quick glance at Theorem 2 does not highlight how the identifiability is dependent on the discretization approach; it currently sounds like something that is just simply true.\n\n**Q4.** Alpha (line 325) should be defined in the text. There is a typo in algorithm 1, line 8: return $\\hat{\\textbf{Q}}_{c(X) | Y}$? But that is discarded, right?\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n_Originality_: I found this paper to be very novel in establishing a connection between label shift and topic modeling.\n\n_Quality_: theoretical and empirical results were solid. The theory felt straightforward, drawing directly from topic modeling literature and applying Bayes rule, but I think it was sufficient for the scope of this paper.\n\n_Presentation_: the paper was well-written and easy to follow.\n\n_Significance_: this method seems to be potentially very useful for handling datasets with spurious features that naive clusters would overindex on, which is a pervasive challenge in areas like medical imaging (Oakden-Rayner et. al., 2019). \n\nOakden-Rayner, L. et. al. Hidden Stratification Causes Clinically Meaningful Failures in Machine Learning for Medical Imaging. ML4C at NeurIPS, 2019.\n\n**Weaknesses**\n\n_Quality_: there were no direct theoretical results on the DDFA method. It would have been nice to discuss further tradeoffs for this discretization, such as choice of m and estimation error.\n\n_Significance_: I am not sure how practically relevant this sort of approach can be. My first concern is in general about label shift, since I am not aware of if there are real datasets that cleanly capture this phenomenon. Second, based on the recoverability assumptions, if we had a task with many classes, we would need just as many domains/sources of data, such as those across time and location. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BIZ4e8I5Q9P", "reviewer": "Reviewer_RW2N", "summary": "This paper introduces a new experimental setting $Unsupervised\\ Latent\\ Label\\ Shift$, where the data are available from multiple domains and the label distributions vary across different domains but the class conditionals do not. Furthermore, this paper proposes a DDFA framework to solve the problem unsupervisedly and theoretically demonstrates that the matrix factorization solution may be identified. The experimental results demonstrate the effectiveness of the proposed framework.", "questions": "Please refer to the above section", "limitations": "Please refer to the above section", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The writing is very clear and the paper is easy to follow.\n2. The setting of this paper is very interesting and practical.\n3.  I appreciate the notion of using matrix factorization to calculate the distribution $Q_{X|D}$, which can save the cost on training the generative model $Q_{X|Y}$, making this framework realistic and easy to use in real-world applications.\n4.More crucially, this work presents the assumptions and theoretic analysis of the $Q_{X|D}$ identifiability.\n\n\nWeakness:\n1. In the section \"Discretize\", the number of clusters $m$ is larger than $k$. Can the authors perform an ablation study on the ratio between $m$ and $k$? If so, the results may be more convincing.\n\n\n\n\n\n\n\nIt would be nice to have a citation for the relevant paper [1].\n\n[1] Guo J, Gong M, Liu T, Zhang K, Tao D. Ltf: A label transformation framework for correcting label shift. International Conference on Machine Learning 2020 Nov 21 (pp. 3843-3853). PMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept