# Mixture Proportion Estimation Beyond Irreducibility

Yilun Zhu  Aaron Fjeldsted  Darren Holland  George Landon  Azaree Lintereur
Clayton Scott

###### Abstract

The task of mixture proportion estimation (MPE) is to estimate the weight of a
component distribution in a mixture, given observations from both the
component and mixture. Previous work on MPE adopts the _irreducibility_
assumption, which ensures identifiablity of the mixture proportion. In this
paper, we propose a more general sufficient condition that accommodates
several settings of interest where irreducibility does not hold. We further
present a resampling-based meta-algorithm that takes any existing MPE
algorithm designed to work under irreducibility and adapts it to work under
our more general condition. Our approach empirically exhibits improved
estimation performance relative to baseline methods and to a recently proposed
regrouping-based algorithm.

Machine Learning, Mixture Proportion Estimation, Weakly Supervised Learning

##  1 Introduction

Mixture proportion estimation (MPE) is the problem of estimating the weight of
a component distribution in a mixture. Specifically, let $\kappa^{*}\in[0,1]$
and let $F$, $G$, and $H$ be probability distributions such that
$F=(1-\kappa^{*})G+\kappa^{*}H$. Given i.i.d. observations

$\begin{split}X_{H}&:=\left\\{x_{1},x_{2},\cdots,x_{m}\right\\}\stackrel{{\scriptstyle
iid}}{{\sim}}H,\\\
X_{F}&:=\left\\{x_{m+1},x_{m+2},\cdots,x_{m+n}\right\\}\stackrel{{\scriptstyle
iid}}{{\sim}}F,\end{split}$ (1)

MPE is the problem of estimating $\kappa^{*}$. A typical application is given
some labeled positive reviews $X_{H}$, estimate the proportion of positive
comments about a product among all comments $X_{F}$ (González et al., 2017).
MPE is also an important component in solving several domain adaptation and
weakly supervised learning problems, such as learning from positive and
unlabeled examples (LPUE) (Elkan & Noto, 2008; Du Plessis et al., 2014; Kiryo
et al., 2017), learning with noisy labels (Lawrence & Schölkopf, 2001;
Natarajan et al., 2013; Blanchard et al., 2016), multi-instance learning
(Zhang & Goldman, 2001), and anomaly detection (Sanderson & Scott, 2014).

If no assumptions are made on the unobserved component $G$, then $\kappa^{*}$
is not identifiable. Blanchard et al. (2010) proposed the _irreducibility_
assumption on $G$ so that $\kappa^{*}$ becomes identifiable. Up to now, almost
all MPE algorithms build upon the irreducibility assumption (Blanchard et al.,
2010; Scott, 2015; Blanchard et al., 2016; Jain et al., 2016; Ramaswamy et
al., 2016; Ivanov, 2020; Bekker & Davis, 2020; Garg et al., 2021), or some
stricter conditions like non-overlapping support of component distributions
(Elkan & Noto, 2008; Du Plessis & Sugiyama, 2014). However, as we discuss
below, irreducibility can be violated in several applications, in which case
the above methods produce statistically inconsistent estimates. As far as we
know, Yao et al. (2022), discussed in Sec. 5, is the first attempt to move
beyond irreducibility.

This work proposes a more general sufficient condition than irreducibility,
and offers a practical algorithm for estimating $\kappa^{*}$ under this
condition. We introduce a meta-algorithm that takes as input any MPE method
that consistently estimates $\kappa^{*}$ under irreducibility, and removes the
bias of that method whenever irreducibility does not hold but our more general
sufficient condition does. Furthermore, even if our new sufficient condition
is not satisfied, our meta-algorithm will not increase the bias of the
underlying MPE method. We describe several applications and settings where our
framework is relevant, and demonstrate the practical relevance of this
framework through extensive experiments. Proofs and additional details can be
found in the appendices.

##  2 Problem Setup and Background

Let $G$ and $H$ be probability measures on a measurable space
$(\mathcal{X},\mathfrak{S})$, and let $F$ be a mixture of $G$ and $H$

$F=(1-\kappa^{*})G+\kappa^{*}H,$ (2)

where $0\leq\kappa^{*}\leq 1$. With no assumptions on $G$, $\kappa^{*}$ is not
uniquely determined by $F$ and $H$. For example, suppose
$F=(1-\kappa^{*})G+\kappa^{*}H$ for some $G$, and take any
$\delta\in[0,\kappa^{*}]$. Then
$F=(1-\kappa^{*}+\delta)G^{\prime}+(\kappa^{*}-\delta)H,$ where
$G^{\prime}=(1-\kappa^{*}+\delta)^{-1}\left[(1-\kappa^{*})G+\delta H\right]$,
has a different proportion on $H$ (Blanchard et al., 2010).

###  2.1 Ground-Truth and Maximal Proportion

To address the lack of identifiability, Blanchard et al. (2010) introduced the
so-called irreducibility assumption. We now recall this definition and related
concepts. Throughout this work we assume that $F$, $G$ and $H$ have densities
$f$, $g$ and $h$, defined w.r.t. a common dominating measure $\mu$.

######  Definition 2.1 (Blanchard et al. (2010)).

For any two probability distributions $F$ and $H$, define

$\begin{split}\kappa(F|H):=\sup\\{\kappa\in[0,1]|F&=(1-\kappa)G^{\prime}+\kappa
H,\\\ &\text{for some distribution }G^{\prime}\\},\end{split}$

the maximal proportion of $H$ in $F$.

This quantity equals the infimum of the likelihood ratio:

######  Proposition 2.2 (Blanchard et al. (2010)).

It holds that

$\kappa(F|H)=\inf_{S\in\mathfrak{S}:H(S)>0}\frac{F(S)}{H(S)}=\underset{x:h(x)>0}{\operatorname{ess\
inf\ }}\frac{f(x)}{h(x)}.$ (3)

By substituting $F=(1-\kappa^{*})G+\kappa^{*}H$ into Eqn. (3), we get that

$\begin{split}\kappa(F|H)&=\inf_{S\in\mathfrak{S}:H(S)>0}\frac{F(S)}{H(S)}\\\
&=\kappa^{*}+(1-\kappa^{*})\inf_{S\in\mathfrak{S}:H(S)>0}\frac{G(S)}{H(S)}\\\
&=\kappa^{*}+(1-\kappa^{*})\kappa(G|H).\end{split}$ (4)

Since $\kappa(F|H)$ is identifiable from $F$ and $H$, the following assumption
on $G$ ensures identifiability of $\kappa^{*}$.

######  Definition 2.3 (Blanchard et al. (2010)).

We say that $G$ is _irreducible_ with respect to $H$ if $\kappa(G|H)=0$.

Thus, irreducibility means that there exists _no_ decomposition of the form:
$G=\gamma H+(1-\gamma)J^{\prime}$, where $J^{\prime}$ is some probability
distribution and $0<\gamma\leq 1$. Under irreducibility, $\kappa^{*}$ is
identifiable, and in particular, equals $\kappa(F|H)$.

###  2.2 Latent Label Model

We now consider another way of understanding irreducibility in terms of a
latent label model. In particular, let $X$ and $Y\in\\{0,1\\}$ be the random
variables characterized by

  1. (a)

$(X,Y)$ are jointly distributed

  2. (b)

$P(Y=1)=\kappa^{*}$

  3. (c)

$P_{X|Y=0}=G\text{ and }P_{X|Y=1}=H$.

It follows from these assumptions that the marginal distribution of $X$ is
$F$:

$P_{X}=\left(1-\kappa^{*}\right)P_{X|Y=0}+\kappa^{*}P_{X|Y=1}=F.$

We also take the conditional probability of $Y$ given $X$ to be defined via

$\begin{split}P(Y=1|X=x)=\begin{cases}\frac{\kappa^{*}h(x)}{f(x)},&f(x)>0,\\\
0,&\text{otherwise}.\end{cases}\end{split}$ (5)

The latent label model is commonly used in the positive unlabeled (PU)
learning literature (Bekker & Davis, 2020). MPE is also called class
prior/proportion estimation (CPE) in PU learning because $P(Y=1)=\kappa^{*}$.
$Y$ may be viewed as a label indicating which component an observation from
$F$ was drawn from. Going forward, we use this latent label model in addition
to the original MPE notation.

######  Proposition 2.4.

Under the latent label model,

$\underset{x}{\operatorname{ess\ sup\
}}P(Y=1|X=x)=\frac{\kappa^{*}}{\kappa(F|H)}\ ,$

where $0/0:=0$.

By definition, we know that $G$ is not irreducible with respect to $H$ iff
$\kappa(G|H)>0$. Combining Proposition 2.4 and Eqn. (4), we conclude that
$\underset{}{\operatorname{ess\ sup\ }}P(Y=1|X=x)<1$ is equivalent to
$\kappa(G|H)>0$.

###  2.3 Violation of Irreducibility

Up to now, almost all MPE algorithms assume $G$ to be irreducible w.r.t. $H$
(Blanchard et al., 2010, 2016; Jain et al., 2016; Ivanov, 2020), or stricter
conditions like the anchor set assumption (Scott, 2015; Ramaswamy et al.,
2016), or that $G$ and $H$ have disjoint supports (Elkan & Noto, 2008; Du
Plessis & Sugiyama, 2014). These methods return an estimate of $\kappa(F|H)$
as the estimate of $\kappa^{*}$. If irreducibility does not hold and
$\kappa^{*}<1$, then $\kappa(F|H)>\kappa^{*}$. Even if these methods are
consistent estimators of $\kappa(F|H)$, they are asymptotically biased and
thus inconsistent estimators of $\kappa^{*}$.

A sufficient condition for irreducibility to hold is that the support of $H$
is not totally contained in the support of $G$. In a classification setting
where $G$ and $H$ are the class-conditional distributions, this may be quite
reasonable. It essentially assumes that each class has at least some subset of
instances (with positive measure) that cannot possibly be confused with the
other class. While irreducibility is reasonable in many classification-related
tasks, there are also a number of important applications where it does not
hold. In this subsection we give three examples of applications where
irreducibility is not satisfied.

Ubiquitous Background. In gamma spectroscopy, we may view $H$ as the
distribution of the energy of a gamma particle emitted by some source of
interest (e.g., Cesium-137), and $G$ as the energy distribution of background
radiation. Typically the background emits gamma particles with a wider range
of energies than the source of interest does, and therefore its distribution
has a wider support: $\operatorname{supp}(H)\subset\operatorname{supp}(G)$,
thus violating irreducibility. What’s more, $G$ is usually unknown, because it
varies according to the surrounding environment (Alamaniotis et al., 2013).
The MPE problem is: given observations of the source spectrum $H$, which may
be collected in a laboratory setting, and observations of $F$ in the wild,
estimate $\kappa^{*}$. This quantity is important for nuclear threat detection
and nuclear safeguard applications.

Global Uncertainty. In marketing, let $Y\in\left\\{0,1\right\\}$ denote
whether a customer does ($Y=1$) or does not purchase a product (Fei et al.,
2013). Let $H$ be the distribution of a feature vector extracted from a
customer who buys the product, and $G$ the distribution for those who do not.
The MPE problem is: given data from past purchasers of a product ($H$), and
from a target population ($F$), estimate the proportion $\kappa^{*}$ of $H$ in
$F$. This quantity is called the _transaction rate_ , and is important for
estimating the number of products to be sold. Irreducibility is likely to be
violated here because, given a finite number of features, uncertainty about
customers should remain bounded away from 1: $\forall x,P(Y=1|X=x)<1$. In
other words, there is an $\epsilon>0$ such that, for any feature vector of
demographic information, the probability of buying the product is always
$<1-\epsilon$.

Underreported Outcomes. In public health, let $(X,Y,Z)$ be a jointly
distributed triple, where $X$ is a feature vector, $Y\in\\{0,1\\}$ denotes
whether a person reports a health condition or not, and $Z\in\\{0,1\\}$
indicates whether the person truly has the health condition. Here,
$H=P_{X|Y=1},G=P_{X|Y=0}$ and $F=P_{X}$. The MPE problem is: given data from
previous people who reported the condition ($H$), and from a target group
($F$), determine the _prevalence_ $\kappa^{*}$ of the condition for the target
group. This helps estimate the amount of resources needed to address the
health condition. Assume there are no false reports from those who do not have
the medical condition: $\forall x,P(Y=1|Z=0,X=x)=0$. Some medical conditions
are underreported, such as smoking and intimate partner violence (Gorber et
al., 2009; Shanmugam & Pierson, 2021). If the underreporting happens globally,
meaning $e(x):=P(Y=1|Z=1,X=x)$ is bounded away from 1, then
$\underset{}{\operatorname{ess\ sup\ }}P(Y=1|X=x)<1$. This is because
$P(Y=1|X=x)=P(Y=1|Z=0,X=x)P(Z=0|X=x)+P(Y=1|Z=1,X=x)P(Z=1|X=x)\leq e(x)$. In
this situation, irreducibility is again violated.

In the above situations, irreducibility is violated and
$\kappa(F|H)>\kappa^{*}$. Estimating $\kappa(F|H)$ alone leads to bias. In the
following, we will re-examine mixture proportion estimation. In particular, we
propose a more general sufficient condition than irreducibility, and introduce
an estimation strategy that calls an existing MPE method and reduces or
eliminates its asymptotic bias.

##  3 A General Identifiability Condition

Previous MPE works assume irreducibility. We propose a more general sufficient
condition for recovering $\kappa^{*}$.

######  Theorem 3.1 (Identifiability Under Local Supremal Posterior (LSP)).

Let $A$ be any non-empty measurable subset of $E_{H}=\\{x:h(x)>0\\}$ and
$s=\underset{x\in A}{\operatorname{ess\ sup\ }}P(Y=1|X=x)$. Then

$\displaystyle\kappa^{*}=s\cdot\inf_{S\subseteq
A}\frac{F(S)}{H(S)}=s\cdot\underset{x\in A}{\operatorname{ess\ inf\
}}\frac{f(x)}{h(x)}.$

This implies that under LSP, $\kappa^{*}$ is identifiable. Two special cases
are worthy of comment. First, irreducibility holds when $A=E_{H}$ and $s=1$,
in which case the above theorem recovers the known result that
$\kappa^{*}=\kappa(F|H)$. Second, when $A=\left\\{x_{0}\right\\}$ is a
singleton, then $s=P(Y=1|X=x_{0})$ and
$\kappa^{*}=P(Y=1|X=x_{0})\cdot\frac{f(x_{0})}{h(x_{0})}$, which can also be
derived directly from the definition of conditional probability.

The above theorem gives a general sufficient condition for recovering
$\kappa^{*}$, but estimating $\inf_{S\subseteq A}\frac{F(S)}{H(S)}$ is non-
trivial: when $A=E_{H}$, it can be estimated using existing MPE methods
(Blanchard et al., 2016). When $A$ is a proper subset, however, a new approach
is needed. We now present a variation of Theorem 3.1 that lends itself to a
practical estimation strategy without having to devise a completely new method
of estimating $\inf_{S\subseteq A}\frac{F(S)}{H(S)}$.

######  Theorem 3.2 (Identifiability Under Tight Posterior Upper Bound).

Consider any non-empty measurable set $A\subseteq E_{H}=\\{x:h(x)>0\\}$, and
let $s=\underset{x\in A}{\operatorname{ess\ sup\ }}P(Y=1|X=x)$. Let
$\alpha(x)$ be any measurable function satisfying

$\alpha(x)\in\begin{cases}\left[P(Y=1|X=x),s\right],&x\in A,\\\
\left[P(Y=1|X=x),1\right],&\text{o.w.}\end{cases}$ (6)

Define a new distribution $\widetilde{F}$ in terms of its density

$\begin{split}&\widetilde{f}(x)=\frac{1}{c}\cdot\alpha(x)\cdot f(x),\\\ \text{
where }\quad&c=\int\alpha(x)f(x)dx=\mathbb{E}_{X\sim
F}\left[\alpha(X)\right].\end{split}$ (7)

Then

$\displaystyle\kappa^{*}=c\cdot\kappa(\widetilde{F}|H).$

The theorem can be re-stated as: $\kappa^{*}$ is identifiable given an upper
bound of the posterior probability $\alpha(x)\geq P(Y=1|X=x)$ that is tight
for some $x\in A$. One possible choice for $\alpha(x)$ is simply

$\alpha(x)=\begin{cases}s,&x\in A,\\\ 1,&\text{o.w.}\end{cases}$

If the conditional probability $P(Y=1|X=x)$ is known for all $x\in A$, then

$\alpha(x)=\begin{cases}P(Y=1|X=x),&x\in A,\\\ 1,&\text{o.w.},\end{cases}$

may be chosen.

Having $\alpha(x)$ satisfying Eqn. (6) ensures identifiablility of
$\kappa^{*}$. Relaxing this requirement slightly still guarantees that the
bias will not increase.

######  Corollary 3.3.

Let $\alpha(x)$ be any measurable function with

$\alpha(x)\in[P(Y=1|X=x),1]\quad\forall x.$ (8)

Define a new distribution $\widetilde{F}$ in terms of its density
$\widetilde{f}$ according to Eqn. (7). Then

$\displaystyle\kappa^{*}\leq c\cdot\kappa(\widetilde{F}|H)\leq\kappa(F|H).$

This shows that even if we have a non-tight upper bound on $P(Y=1|X=x)$, the
quantity $c\cdot\kappa(\widetilde{F}|H)$ is still bounded by $\kappa(F|H)$.
Therefore, a smaller asymptotic bias may be achieved by estimating
$c\cdot\kappa(\widetilde{F}|H)$ instead of $\kappa(F|H)$.

The intuition underlying the above results is that the new distribution
$\widetilde{F}$ is generated by throwing away some probability mass from $G$,
and therefore can be viewed as a mixture of $H$ and a new $\widetilde{G}$, but
now $\widetilde{G}$ tends to be irreducible w.r.t. $H$. The proportion
$\kappa(\widetilde{F}|H)$ relates to the original proportion $\kappa^{*}$ by a
scaling constant $c$. This interpretation is supported mathematically in
Appendix B.1.

##  4 Subsampling MPE (SuMPE)

Theorem 3.2 directly motivates a practical algorithm. We obtain a new
distribution $\widetilde{F}$ from $F$ by rejection sampling (MacKay, 2003),
which is a Monte Carlo method that generates a sample following a new
distribution $\widetilde{Q}$ based on a sample from distribution $Q$, in terms
of their densities $\widetilde{q}$ and $q$. An instance $x$ drawn from $q(x)$
is kept with acceptance probability $\beta(x)\in[0,1]$, and rejected
otherwise. Appendix B.2 shows the detailed procedure. In our scenario,
$\widetilde{Q}=\widetilde{F}$, $Q=F$ and $\beta(x)=\alpha(x)$.

###  4.1 Method

Our Subsampling MPE algorithm, SuMPE (Algorithm 1), follows directly from
Theorem 3.2. It first obtains in line 3 a data sample $X_{\widetilde{F}}$
following distribution $\widetilde{F}$ using rejection sampling and in line 4
estimates the normalizing constant $c$. Then in line 5, it computes an
estimate $\widehat{\kappa}(\widetilde{F}|H)$ using any existing MPE method
that consistently estimates the mixture proportion under irreducibility. The
final estimate is returned as the product of $\widehat{c}$ and
$\widehat{\kappa}(\widetilde{F}|H)$.

Rejection sampling in high dimensional settings may be inefficient due to a
potentially low acceptance rate (MacKay, 2003). However, this concern is
mitigated in our setting because the acceptance rate can be taken to be 1
except on the set $A$, which is potentially a small set.

Algorithm 1 Subsampling MPE (SuMPE)

1: Input: $X_{F}$: sample drawn i.i.d. from $F$ $X_{H}$: sample drawn i.i.d.
from $H$ $\alpha(x)$: acceptance function

2: Output: Estimate of $\kappa^{*}$

3: Generate $X_{\widetilde{F}}$ from $X_{F}$ by rejection sampling (Algorithm
4), with acceptance function $\alpha(x)$.

4: Compute $\widehat{c}=\left|X_{\widetilde{F}}\right|/\left|X_{F}\right|$,
where $\left|\cdot\right|$ denotes the cardinality of a set.

5: Apply an off-the-shelf MPE algorithm to produce an estimate
$\widehat{\kappa}(\widetilde{F}|H)$ from $X_{\widetilde{F}}$ and $X_{H}$.

6: return $\widehat{c}\cdot\widehat{\kappa}(\widetilde{F}|H)$

One advantage of building our method around existing MPE methods is that we
may adapt known theoretical results to our setting. To illustrate this, we
give a rate of convergence result for SuMPE.

######  Theorem 4.1.

Assume $\alpha(x)$ satisfies the condition in Eqn. (6). After subsampling,
assume the resulting $\widetilde{F}$ and $H$ are such that
$\underset{S\in\mathcal{A}:H(S)>0}{\operatorname{arg\ min\
}}\frac{\widetilde{F}(S)}{H(S)}$ exists. Then there exists a constant $C>0$
and an existing MPE estimator $\widehat{\kappa}$ such that, for $m$ and $n$
sufficiently large, the estimator $\widehat{\kappa}^{*}$ obtained from SuMPE
(Algorithm 1) satisfies

$\Pr\left(\left|\widehat{\kappa}^{*}-\kappa^{*}\right|\leq
C\left[\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log n}{n}}\right]\right)\\\ \geq
1-\mathcal{O}\left(\frac{1}{m}+\frac{1}{n}\right).$

###  4.2 Practical Scenarios

Our new sufficient condition assumes knowledge of some set $A\subseteq E_{H}$
and $s=\underset{x\in A}{\operatorname{ess\ sup\ }}P(Y=1|X=x)$. However,
practically speaking, our algorithm only requires an $\alpha(x)$ satisfying
Eqn. (6) for some $A\subseteq E_{H}$ and the associated value of $s$, and does
not require the explicit knowledge of $A$ and $s$. Additionally, even if
$\alpha(x)$ does not satisfy Eqn. (6) , as long as it satisfies Eqn. (8)
(which is easier to achieve), it shall perform no worse than directly applying
off-the-shelf MPE methods.

There are settings where a generic construction of $\alpha(x)$ is possible.
For example, suppose the user has access to fully labeled data (where it is
known which of $G$ or $H$ each instance came from) but only on a subset $A$ of
the domain. This may come from an annotator who is only an expert on a subset
of instances. This data should be sufficient to get a non-trivial upper bound
on the posterior class probability $P(Y|X)$, which in turns leads to an
$\alpha(x)$.

More typically, however, it may be necessary to determine $\alpha(x)$ on a
case by case basis. This section continues the discussion of the three
applications introduced in Sec. 2.3. Each of these three settings leverages
different domain-specific knowledge in different ways, and we believe this
leads to the best $\alpha(x)$ compared to a one-size-fits-all construction.

####  4.2.1 Unfolding

Unfolding refers to the process of recovering one or more true distributions
from contaminated ones (Cowan, 1998). In gamma spectrum unfolding (Li et al.,
2019), a gamma ray detector measures the energies of incoming gamma rays. The
gamma rays were emitted either by a source of interest or from the background.
The measurement is represented as a histogram $f(x)$ where the bins correspond
to a quantization of energy. In many settings, the histogram $h(x)$ of
measurements from the source of interest is also known. In this case,
unfolding amounts to the estimation of the unknown background histogram
$g(x)$. Toward this goal, it suffices to estimate the proportion of recorded
particles $\kappa^{*}$ emanating from the source of interest, since
$g(x)=(f(x)-\kappa^{*}h(x))/(1-\kappa^{*})$. This application corresponds to
the “ubiquitious background” setting described in Sec. 2.3, where
irreducibility may not hold since the source of interest energies can be a
subset of the background energies.

Using existing techniques from the nuclear detection literature (Knoll, 2010;
Alamaniotis et al., 2013), we can obtain a lower bound $\rho(x)$ of the
quantity $(1-\kappa^{*})g(x)$ on a certain set
$A\subset\operatorname{supp}(H)$ (see Appendix B.3 for details). This leads to
the acceptance function

$\alpha(x)=\begin{cases}1-\frac{\rho(x)}{f(x)},&x\in A,\\\
1,&\text{o.w.},\end{cases}$ (9)

which is an upper bound of $P(Y=1|X=x)$, satisfying the condition in Corollary
3.3.

####  4.2.2 CPE under domain adaptation

In the problem of domain adaptation, the learner is given labeled examples
from a source distribution, and the task is to do inference on a potentially
different target distribution. Previous work on domain adaptation mainly
focuses on classification and typically makes assumptions about which of the
four distributions $P_{X},P_{Y|X},P_{Y}$, and $P_{X|Y}$ vary between the
source and target. This leads to situations such as covariate shift (where
$P_{X}$ changes) (Heckman, 1979), posterior drift (where $P_{Y|X}$ changes)
(Scott, 2019), prior/target shift (where $P_{Y}$ changes) (Storkey et al.,
2009), and conditional shift (where $P_{X|Y}$ changes) (Zhang et al., 2013).
It is also quite commonly assumed that the support of source distribution
contains the support of target (Heckman, 1979; Bickel et al., 2009; Gretton et
al., 2009; Storkey et al., 2009; Zhang et al., 2013; Scott, 2019).

We study class proportion estimation (CPE) under domain adaptation. Prior work
on this topic has considered distributional assumptions like those described
above (Saerens et al., 2002; Sanderson & Scott, 2014; González et al., 2017).
In this work, we consider the setting where, in addition to labeled examples
from the source, the learner has access to labeled positive and unlabeled data
from the target. We propose a model that includes covariate shift and
posterior drift as special cases. We use $P^{sr}_{XY}$ and $P^{tg}_{XY}$ to
denote source and target distributions. In MPE notation, $F=P^{tg}_{X}$,
$G=P^{tg}_{X|Y=0}$ and $H=P^{tg}_{X|Y=1}$.

######  Definition 4.2 (CSPL).

We say that _covariate shift with posterior lift_ occurs whenever

$\displaystyle\forall
x\in\operatorname{supp}(P^{sr}_{X})\bigcap\operatorname{supp}(P^{tg}_{X}),$
$\displaystyle P^{sr}(Y=1|X=x)\geq P^{tg}(Y=1|X=x),$

and “$=$” holds for some
$x\in\operatorname{supp}(P^{sr}_{X})\bigcap\operatorname{supp}(P^{tg}_{X|Y=1})$.

Covariate shift is a special case of CSPL when equality always holds. One
motivation for posterior lift is to model labels produced by an annotator who
is biased toward one class. It is a type of posterior drift model wherein the
posterior changes from source to target (Scott, 2019; Cai & Wei, 2021; Maity
et al., 2023). Also notice that CSPL does not require the support of the
source distribution to contain the target, nor irreducibility.

CSPL is motivated by a marketing application mentioned in Sec. 2.3. In
marketing, companies often have access to labeled data from a source
distribution, such as survey results where customers express their interest in
a product. Additionally, they also have access to labeled positive and
unlabeled data from the target distribution, which corresponds to actual
purchasing behavior. In this scenario, the CSPL assumption is often met as it
is more likely for customers to express interest than to actually make a
purchase: $P^{sr}(Y=1|X=x)\geq P^{tg}(Y=1|X=x)$.

Although irreducibility is violated in the marketing application due to the
“global uncertainty” about a target customer buying the product (see Sec.
2.3), CSPL ensures the identifiability of $\kappa^{*}=P^{tg}(Y=1)$ because we
can choose the set
$A=\operatorname{supp}(P^{sr}_{X})\bigcap\operatorname{supp}(P^{tg}_{X|Y=1})$
and the acceptance function as

$\alpha(x)=\begin{cases}P^{sr}(Y=1|X=x),&x\in A,\\\
1,&\text{o.w.},\end{cases}$ (10)

which satisfies the identifiability criteria in Theorem 3.2. 111 To see this,
take $A^{\prime}=\\{x\in A:P^{sr}(Y=1|X=x)=P^{tg}(Y=1|X=x)\\}$ and
$s^{\prime}=\underset{x\in A^{\prime}}{\operatorname{ess\ sup\
}}P^{sr}(Y=1|X=x)=\underset{x\in A^{\prime}}{\operatorname{ess\ sup\
}}P^{tg}(Y=1|X=x)$. Then $A^{\prime}$ and $s^{\prime}$ are the $A$ and $s$ in
Theorem 3.2.  By using the labeled source data, an estimate of
$P^{sr}(Y=1|X=x)$ can be obtained and used as the acceptance function
$\alpha(x)$ in Algorithm 1 to do CPE.

####  4.2.3 Selected/Reported at Random

In public health, $(X,Y,Z)$ are jointly distributed, where $X$ is the feature
vector, $Y\in\\{0,1\\}$ denotes whether a person reports a medical condition
or not and $Z\in\\{0,1\\}$ indicates whether a person truly has the medical
condition. The goal is to estimate the proportion of people in $X_{F}$ that
report the medical condition. This setting was described in Sec. 2.3 as
“underreported outcomes” where it was argued that irreducibility may not hold,
in which case estimating $\kappa(F|H)$ overestimates the true value of
$\kappa^{*}$. Our SuMPE framework provides a way to eliminate the bias.

The behavior of underreporting can be captured using the _selection bias_
model (Kato et al., 2018; Bekker et al., 2019; Gong et al., 2021). Denote the
probability of reporting as $e(x):=P(Y=1|X=x,Z=1)$. Assume there is no false
report: $\forall x,P(Y=1|X=x,Z=0)=0$. We use the notation $p(x|\Omega)$ to
indicate the conditional density of $X$ given the event $\Omega$. Then
$p(x|Y=1)=\frac{e(x)}{\nu}p(x|Z=1)$, where $\nu=P(Y=1|Z=1)$. Under this model,
the density of marginal distribution $P_{X}$ can be decomposed as

$\displaystyle p(x)=\ $ $\displaystyle(1-\alpha)\cdot p(x|Z=0)+\alpha\cdot
p(x|Z=1)$ $\displaystyle=\ $ $\displaystyle(1-\alpha\nu)\cdot
p(x|Y=0)+\alpha\nu\cdot p(x|Y=1),$

where $\alpha=P(Z=1)$ is the proportion of people having the medical
condition. The mixture proportion to be estimated is
$\kappa^{*}=P(Y=1)=P(Y=1,Z=1)=P(Z=1)P(Y=1|Z=1)=\alpha\nu$.

We assume access to i.i.d. sample from $H=P_{X|Y=1}$, representing the public
survey data where people report the presence of the medical condition, and
from $F=P_{X}$, representing the target group. Further assume that
$A\subseteq\\{x:P(Z=1|X=x)=1\\}$. This is a subset of patients who are
guaranteed to have the condition, which could be obtained based on historical
patient data from hospital. Then the mixture proportion $\kappa^{*}=\alpha\nu$
can be recovered from Algorithm 1, where the acceptance function is

$\alpha(x)=\begin{cases}e(x),&x\in A,\\\ 1,&\text{o.w.}\end{cases}$ (11)

$\alpha(x)$ satisfies the condition in Theorem 3.2 . This is because under no-
false-report assumption, $\forall x\in
A,P(Y=1|X=x)=P(Y=1,Z=1|X=x)=P(Y=1|X=x,Z=1)\cdot P(Z=1|X=x)=e(x)\cdot 1=e(x)$.
222 Take $A^{\prime}=\\{x\in A:e(x)>0\\}$ and $s^{\prime}=\underset{x\in
A^{\prime}}{\operatorname{ess\ sup\ }}e(x)=\underset{x\in
A^{\prime}}{\operatorname{ess\ sup\ }}P(Y=1|X=x)$. Then $A^{\prime}$ and
$s^{\prime}$ are the $A$ and $s$ in Theorem 3.2.  In practice, $e(x)$ can be
estimated from labeled examples $(X,Y,Z=1)$.

##  5 Limitation of Previous Work

Previous research by Yao et al. (2022) introduced the Regrouping MPE (ReMPE)
method 333Yao et al. (2022) called the method Regrouping CPE (ReCPE)., which
is built on top of any existing MPE estimator (just like our meta-algorithm).
They claimed that ReMPE works as well as the base MPE method when
irreducibility holds, while improving the performance when it does not. In
this section we offer some comments on ReMPE.

##### Regrouping MPE in theory.

Consider any $F,H,G,\kappa^{*}$ such that Eqn. (2) holds. Write $G$ as an
arbitrary mixture of two distributions $G=\gamma
G_{1}+(1-\gamma)G_{2},\gamma\geq 0$. Then $F$ can be re-written as

$\begin{split}F&=(1-\kappa^{*})G+\kappa^{*}H\\\ &=(1-\kappa^{*})\left[\gamma
G_{1}+(1-\gamma)G_{2}\right]+\kappa^{*}H\\\
&=(1-\kappa^{*})(1-\gamma)G_{2}+\underbrace{\left[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(1-\kappa^{*})\gamma
G_{1}}+\kappa^{*}H\right]}_{\text{Regrouped}}\\\
&=(1-\kappa^{\prime})G_{2}+\kappa^{\prime}H^{\prime},\end{split}$ (12)

where $\kappa^{\prime}=\kappa^{*}+(1-\kappa^{*})\gamma$. Yao et al. (2022)
assumes there exists a set such that the infimum in Eqn. (3) and (4) can be
achieved. They proposed to specify $G_{1}$ as the truncated distribution of
$G$ in set $B$, denote as $G_{B}$, where
$B=\arg\min_{S\in\mathfrak{S}}\frac{G(S)}{H(S)}$. This specific choice causes
the resulting distribution $G_{2}$ to be irreducible w.r.t. $H^{\prime}$ and
the bias introduced by regrouping $(1-\kappa^{*})G(A)$ to be minimal. Denote
the above procedure as _ReMPE-1_ (Algorithm 2). Theorem 2 in Yao et al. (2022)
provides a theoretical justification for ReMPE-1, which we will restate here.

Algorithm 2 ReMPE-1 (Yao et al., 2022)

1: Input: Distributions $F$ and $H$

2: Obtain set $B=\arg\min_{S\in\mathfrak{S}}\frac{G(S)}{H(S)}$

3: Generate new distribution $H^{\prime}$ by Eqn. (12), where $G_{1}=G_{B}$

4: return $\kappa(F|H^{\prime})$

######  Theorem 5.1 (Yao et al. (2022)).

Let $\kappa(F|H^{\prime})$ be the mixture proportion obtained from ReMPE-1. 1)
If $G$ is irreducible w.r.t. $H$, then $\kappa(F|H^{\prime})=\kappa^{*}$. 2)
if $G$ is not irreducible w.r.t. $H$, then
$\kappa^{*}<\kappa(F|H^{\prime})<\kappa(F|H)$.

While this theorem is valid, we note that in the case where $G$ is irreducible
w.r.t. $H$, the set $B$ is outside the support of $G$, and therefore it is not
appropriate to describe the procedure as “regrouping $G$.” In fact, performing
regrouping ($\gamma>0$) always introduces a positive bias, because
$\kappa(F|H^{\prime})\geq\kappa^{\prime}>\kappa^{*}$. This indicates that any
kind of regrouping will have a positive bias under irreducibility.

##### Regrouping MPE in practice.

Yao et al. (2022)’s practical implementation of regrouping deviates from the
theoretical proposal. Here, we state and analyze the idealized version of
their practical algorithm, referred to as _ReMPE-2_ (Algorithm 3). ReMPE-2
does not rely on the knowledge of $\kappa^{*}$ and $G(B)$ as outlined in Eqn.
(12). Instead, the set $B$ is chosen based solely on $F$ and $H$, and the
distribution $H^{\prime}$ is obtained through regrouping some probability mass
from $F$ rather than $G$. 444Yao et al. (2022)’s real implementation differs a
bit from ReMPE-2 in that instead of choosing
$\arg\min_{S\in\mathfrak{S}}\frac{F(S)}{H(S)}$, they select $p=10\%$ of
examples drawn from $F$ with smallest estimated score of $f(x)/h(x)$.

Algorithm 3 ReMPE-2 (Yao et al., 2022)

1: Input: Distributions $F$ and $H$

2: Obtain set $B=\arg\min_{S\in\mathfrak{S}}\frac{F(S)}{H(S)}$

3: Generate new distribution $H^{\prime}=\frac{1}{1+F(B)}\left(F_{B}+H\right)$

4: return $\kappa(F|H^{\prime})$

ReMPE-2 is fundamentally different from ReMPE-1 in that it uses a different
way to construct $H^{\prime}$. To be specific, when the irreducibility
assumption holds, ReMPE-1 suggests regrouping nothing (because $G(B)=0$), but
ReMPE-2 still regroups a proportion $F(B)$ from $F$ to $H$. Therefore, Theorem
5.1 does not apply to it. Yao et al. (2022) did not analyze ReMPE-2, but the
next result shows that it has a negative bias under irreducibility.

######  Proposition 5.2.

For $\kappa(F|H^{\prime})$ obtained from ReMPE-2:

$\displaystyle\kappa(F|H^{\prime})<\kappa(F|H).$

Thus, if irreducibility holds, then ReMPE-2 returns
$\kappa(F|H^{\prime})<\kappa(F|H)=\kappa^{*}$, which is undesirable. However,
when irreducibility does not hold, ReMPE-2 may lead to a smaller asymptotic
bias than estimating $\kappa(F|H)$, which could explain why the authors
observe empirical improvements in their results. Our theoretical analysis of
ReMPE-2 is supported experimentally in Sec. 6 and Appendix D.

To summarize, Yao et al. (2022) proposed a regrouping approach that was the
first attempt to tackle the problem of MPE beyond irreducibility and motivated
our work. ReMPE-1 recovers $\kappa^{*}$ when irreducibility holds (although in
this case it is not doing regrouping), and decreases bias when irreducibility
does not hold. The more practical algorithm ReMPE-2 might decrease the bias
when irreducibility does not hold, but it has a negative bias when
irreducibility does hold. Like ReMPE-1, SuMPE draws on some additional
information beyond $F$ and $H$. Both meta-algorithms do not increase the bias,
and recover $\kappa^{*}$ when irreducibility holds. Unlike ReMPE-1, however,
SuMPE is able to recover $\kappa^{*}$ under a more general condition.
Furthermore, our practical implementations of subsampling are based directly
on Theorem 3.2, unlike ReMPE-2 which does not have the desireable theoretical
properties of ReMPE-1. Finally, as we argue in the next section, SuMPE offers
significant empirical performance gains.

One limitation of our SuMPE framework is that some knowledge of $P(Y|X)$ is
needed and that $\alpha(x)$ may need to be developed specifically for
different applications.

##  6 Experiments

We ran our algorithm on nuclear, synthetic and some benchmark datasets taken
from the UCI machine learning repository and MNIST, corresponding to all three
scenarios described in Sec. 4.2. We take four MPE algorithms: DPL (Ivanov,
2020), EN (Elkan & Noto, 2008), KM (Ramaswamy et al., 2016) and TIcE (Bekker &
Davis, 2018). We compare the original version of these methods together with
their regrouping (Re-$(\cdot$)) and subsampling (Su-$(\cdot$)) version. All
experiments in this section consider settings where irreducibility is
violated. The summarized results are shown in Table 6 and the detailed results
are in Appendix C. Overall, the subsampling version of each MPE method
outperforms the original and regrouping version. Additional experiments where
irreducibility holds are offered in Appendix D, where we find that ReMPE harms
the estimation performance while SuMPE does not. The implementation is
available at https://github.com/allan-z/SuMPE.

Table 1:  Summarized table of average absolute estimation error, corresponding
to testing cases in Sec. 6. Several state-of-the-art MPE algorithms DPL, EN,
KM and TIcE are selected. The mean absolute error
($\text{avg}[\left|\widehat{\kappa}^{*}-\kappa^{*}\right|]$) is reported, the
smallest error among original, regrouping and subsampling version is bolded.
$(+/-)$ denotes that on average the estimator produces positive$/$negative
estimation bias ($\text{sgn}[\text{avg}(\widehat{\kappa}^{*}-\kappa^{*})]$).

Setup | Dataset | DPL | ReDPL | SuDPL | EN | ReEN | SuEN | KM | ReKM | SuKM | TIcE | ReTIcE | SuTIcE
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Unfolding | Gamma Ray | $0.045+$ | $0.117-$ | $\bm{0.013+}$ | $0.034+$ | $0.118-$ | $\bm{0.027-}$ | $0.163+$ | $0.076+$ | $\bm{0.042+}$ | $0.095+$ | $0.061+$ | $\bm{0.019+}$
Domain Adaptation | Synthetic | $0.060+$ | $0.053+$ | $\bm{0.028-}$ | $\bm{0.045-}$ | $0.061-$ | $0.067-$ | $0.063+$ | $0.059+$ | $\bm{0.022-}$ | $0.128+$ | $0.094+$ | $\bm{0.041+}$
Mushroom | $0.047+$ | $0.081-$ | $\bm{0.033+}$ | $0.122+$ | $\bm{0.078+}$ | $0.101+$ | $0.067-$ | $0.134-$ | $\bm{0.059-}$ | $0.060+$ | $0.078-$ | $\bm{0.036+}$
Landsat | $0.046+$ | $0.042-$ | $\bm{0.017-}$ | $0.141+$ | $0.110+$ | $\bm{0.085+}$ | $0.046+$ | $0.029+$ | $\bm{0.016-}$ | $0.043+$ | $0.044-$ | $\bm{0.035-}$
Shuttle | $0.037+$ | $0.138-$ | $\bm{0.015-}$ | $0.090+$ | $0.071+$ | $\bm{0.046+}$ | $0.036+$ | $0.111-$ | $\bm{0.032-}$ | $0.080+$ | $0.086-$ | $\bm{0.038+}$
MNIST17 | $0.047+$ | $0.085-$ | $\bm{0.028-}$ | $0.231+$ | $0.175+$ | $\bm{0.166+}$ | $0.041+$ | $0.063-$ | $\bm{0.017-}$ | $0.090+$ | $0.073-$ | $\bm{0.048+}$
Selected/  Reported at Random | Mushroom | $0.047+$ | $0.095-$ | $\bm{0.027+}$ | $0.119+$ | $0.075+$ | $\bm{0.074+}$ | $0.072-$ | $0.134-$ | $\bm{0.064-}$ | $0.047+$ | $0.066-$ | $\bm{0.044-}$
Landsat | $0.048+$ | $0.057-$ | $\bm{0.019-}$ | $0.142+$ | $0.108+$ | $\bm{0.092+}$ | $0.046+$ | $0.033+$ | $\bm{0.018+}$ | $0.046+$ | $0.053-$ | $\bm{0.041-}$
Shuttle | $0.035+$ | $0.144-$ | $\bm{0.013-}$ | $0.095+$ | $0.073+$ | $\bm{0.056+}$ | $\bm{0.042+}$ | $0.129-$ | $0.044-$ | $0.079+$ | $0.089-$ | $\bm{0.050+}$
MNIST17 | $0.047+$ | $0.088-$ | $\bm{0.027+}$ | $0.240+$ | $0.173+$ | $\bm{0.164+}$ | $0.038+$ | $0.064-$ | $\bm{0.022+}$ | $0.096+$ | $0.073+$ | $\bm{0.057+}$

###  6.1 Unfolding: Gamma Ray Spectra Data

The gamma ray spectra data are simulated from the Monte-Carlo N-Particle
(MCNP) radiation transport code (Werner et al., 2018). $H$ refers to the
distribution of Cesium-137. $G$ is the background distribution, consisting of
terrestrial background and Cobalt-60. The goal is to estimate the proportion
of Cesium-137 in the measured spectrum $F$.

$\displaystyle H$ $\displaystyle\sim p(x|\text{Cesium})$ $\displaystyle G$
$\displaystyle\sim 0.8\cdot p(x|\text{Cobalt})+0.2\cdot p(x|\text{terrestrial
background})$ $\displaystyle F$ $\displaystyle=(1-\kappa^{*})G+\kappa^{*}H.$

Sample sizes of $m=n=50,000$ were chosen, which is a reasonable number of
counts for many nuclear detection applications. The true mixture proportion
$\kappa^{*}$ is varied in $\left\\{0.1,0.25,0.5,0.75\right\\}$. The random
variable $x$ represents quantized energy, which is one-dimensional and is
discrete-valued. Therefore, we directly use the histogram as the estimate of
the distribution. We choose the acceptance function $\alpha(x)$ according to
the methodology developed in Sec. 4.2.1 and Appendix B.3.

Three of the four baseline MPE methods (DPL, EN, KM) did not work well out-of-
the-box in this setting. We therefore re-implemented these methods to
explicitly leverage the histogram representation of the probability
distributions. This also greatly sped up the KM approach. The results are
summarized in Table 2.

###  6.2 Domain Adaptation: Synthetic Data

Following the setup in Sec. 4.2.2, we specify the target conditional and
marginal distributions $H$, $G$ and $F$ as:

$\displaystyle H$ $\displaystyle\sim\mathcal{N}(\mu_{1}=0,\sigma_{1}=1)$
$\displaystyle G$ $\displaystyle\sim
0.8\cdot\mathcal{N}(\mu_{2}=3,\sigma_{2}=2)+0.2\cdot\mathcal{N}(\mu_{3}=4,\sigma_{3}=1)$
$\displaystyle F$ $\displaystyle=(1-\kappa^{*})G+\kappa^{*}H.$

where $G$ is not irreducible w.r.t. $H$ because it contains a Gaussian
distribution with a bigger variance than $H$. We draw $m=n=1000$ instances
from both $H$ and $F$. The true mixture proportion $\kappa^{*}$ is varied in
$\left\\{0.1,0.25,0.5,0.75\right\\}$.

In addition, we draw $4000$ labeled instances from the source distribution,
where $\mu_{3}$ is changed to $5$. We then truncate the source distribution
(and therefore the source sample) to $(-\infty,2]$. The resulting source and
target distribution satisfy the CSPL assumption. A $1$ hidden layer neural
network with $16$ neurons was trained to predict $P^{sr}(Y=1|X=x)$ for
$x\in(-\infty,2]$, thus $A=(-\infty,2]$ and $\alpha(x)$ was chosen according
to Eqn. (10). This procedure was repeated $10$ times with different random
seeds. Detailed results are shown in Table 3.

###  6.3 Domain Adaptation: Benchmark Data

In many machine learning datasets for classification (e.g., those in UCI),
irreducibility is satisfied. 555The datasets Mushroom, Landsat, Shuttle and
MNIST were chosen for our study because previous empirical research (Ivanov,
2020) showed that the baseline MPE methods perform well on these datasets when
the irreducibility assumption holds. Our paper focuses on how to eliminate the
estimation bias that arises from the violation of irreducibility. Therefore,
we chose to use datasets where the baseline methods perform well, in order to
clearly observe and measure the bias introduced by MPE methods when
irreducibility is not met. Here we manually create datasets that violate
irreducibility by uniformly sampling out $90\%$ (or $80\%$) of the original
positive data as the target positive data, with all the remaining data treated
as target negative. The target conditional and marginal distributions $H$, $G$
and $F$ are specified as:

$\displaystyle H$ $\displaystyle\sim p(x|Y=1)$ $\displaystyle G$
$\displaystyle\sim\gamma p(x|Y=1)+(1-\gamma)p(x|Y=0)$ $\displaystyle F$
$\displaystyle=(1-\kappa^{*})G+\kappa^{*}H.$

We draw $m=1000$ instances from $H$ and $n\in\left[1000,4000\right]$ instances
from $F$ (the exact number varies by datasets and is based on number of
examples available, see the code provided). The true mixture proportion
$\kappa^{*}$ is varied in $\left\\{0.1,0.25,0.5,0.75\right\\}$. The proportion
$\gamma$ is determined by the total number of positive and negative data
originally available in the dataset, therefore varies case by case.

In addition, we obtain labeled instances following the source distribution, by
drawing $\kappa^{*}n$ data from the target positive and $0.95(1-\kappa^{*})n$
data from the target negative distribution. This causes a prior shift that
simulates CSPL.

A $2$ hidden layer neural network with $512$ neurons was trained to predict
$P^{sr}(Y=1|X=x)$. For real-world high-dimensional data, it is hard to know
the support. Therefore, we choose $A=\\{x:\widehat{P}^{sr}(Y=1|X=x)>0.5\\}$,
because an example $x$ with high $\widehat{P}^{sr}(Y=1|X=x)$ is more likely to
lie in the support of $H$. The acceptance function $\alpha(x)$ was determined
according to Eqn. (10). The above procedure was repeated $10$ times with
different random seeds. Table 4 summarizes the results.

###  6.4 Selected/Reported at Random: Benchmark Data

Recalling the setting of Sec. 4.2.3, there is a jointly distributed triple
$(X,Y,Z)$, where $Y$ indicates whether a condition is reported, and $Z$
indicates whether the condition is actually present. For the experiments
below, the data from $F,G$, and $H$ are generated in the same way as the
target distribution of the previous subsection. Instead of observing labeled
source data, however, in this subsection we instead observe $\kappa^{*}n$
instances from $p(x|Z=1)$, together with their labels $Y$, matching the setup
of Sec. 4.2.3.

A $2$ hidden layer neural network with $512$ neurons was trained to predict
$e(x)=P(Y=1|X=x,Z=1)$. We chose $A=\\{x:\widehat{e}(x)>0.6\\}$ 666 $A$ needs
to be a subset of $\operatorname{supp}(H)$. Note that in population level,
$h(x)=p(x|Y=1)\propto e(x)\cdot p(x|Z=1)$, thus
$\\{x:e(x)>0.6\\}\subseteq\\{x:e(x)>0\\}=\\{x:h(x)>0\\}$. (The last equality
holds because $e(x)=P(Y=1|X=x,Z=1)$.) Here we replace $e(x)$ with
$\widehat{e}(x)$.  and $\alpha(x)$ according to Eqn. (11). The above procedure
was repeated $10$ times with different random seeds. The results are shown in
Table 5.

##  7 Conclusion

This work introduces a more general identifiability condition than
irreducibility for mixture proportion estimation. We also propose a
subsampling-based framework that achieves bias reduction/elimination for
baseline MPE algorithms. Theoretically, our work expands the scope of settings
where MPE can be solved. Practically, we illustrate three scenarios where
irreducibility fails, and our meta-algorithm successfully improves upon
baseline MPE methods.

## Acknowledgements

This work was supported in part by the National Science Foundation under award
2008074 and the Department of Defense, Defense Threat Reduction Agency under
award HDTRA1-20-2-0002.

## References

  * Alamaniotis et al. (2013) Alamaniotis, M., Mattingly, J., and Tsoukalas, L. H.  Kernel-based machine learning for background estimation of nai low-count gamma-ray spectra.  _IEEE Transactions on Nuclear Science_ , 60(3):2209–2221, 2013.
  * Bekker & Davis (2018) Bekker, J. and Davis, J.  Estimating the class prior in positive and unlabeled data through decision tree induction.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018\.
  * Bekker & Davis (2020) Bekker, J. and Davis, J.  Learning from positive and unlabeled data: A survey.  _Machine Learning_ , 109(4):719–760, 2020.
  * Bekker et al. (2019) Bekker, J., Robberechts, P., and Davis, J.  Beyond the selected completely at random assumption for learning from positive and unlabeled data.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pp. 71–85. Springer, 2019.
  * Bickel et al. (2009) Bickel, S., Brückner, M., and Scheffer, T.  Discriminative learning under covariate shift.  _Journal of Machine Learning Research_ , 10(9), 2009.
  * Blanchard et al. (2010) Blanchard, G., Lee, G., and Scott, C.  Semi-supervised novelty detection.  _The Journal of Machine Learning Research_ , 11:2973–3009, 2010.
  * Blanchard et al. (2016) Blanchard, G., Flaska, M., Handy, G., Pozzi, S., Scott, C., et al.  Classification with asymmetric label noise: Consistency and maximal denoising.  _Electronic Journal of Statistics_ , 10(2):2780–2824, 2016.
  * Cai & Wei (2021) Cai, T. T. and Wei, H.  Transfer learning for nonparametric classification: Minimax rate and adaptive classifier.  _The Annals of Statistics_ , 49(1):100–128, 2021\.
  * Cowan (1998) Cowan, G.  _Statistical data analysis_.  Oxford university press, 1998.
  * Du Plessis & Sugiyama (2014) Du Plessis, M. C. and Sugiyama, M.  Class prior estimation from positive and unlabeled data.  _IEICE TRANSACTIONS on Information and Systems_ , 97(5):1358–1362, 2014.
  * Du Plessis et al. (2014) Du Plessis, M. C., Niu, G., and Sugiyama, M.  Analysis of learning from positive and unlabeled data.  _Advances in neural information processing systems_ , 27, 2014.
  * Elkan & Noto (2008) Elkan, C. and Noto, K.  Learning classifiers from only positive and unlabeled data.  In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 213–220, 2008.
  * Fei et al. (2013) Fei, H., Kim, Y., Sahu, S., Naphade, M., Mamidipalli, S. K., and Hutchinson, J.  Heat pump detection from coarse grained smart meter data with positive and unlabeled learning.  In _Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 1330–1338, 2013.
  * Garg et al. (2021) Garg, S., Wu, Y., Smola, A. J., Balakrishnan, S., and Lipton, Z.  Mixture proportion estimation and PU learning: A modern approach.  _Advances in Neural Information Processing Systems_ , 34:8532–8544, 2021.
  * Gong et al. (2021) Gong, C., Wang, Q., Liu, T., Han, B., You, J., Yang, J., and Tao, D.  Instance-dependent positive and unlabeled learning with labeling bias estimation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 44(8):4163–4177, 2021.
  * González et al. (2017) González, P., Castaño, A., Chawla, N. V., and Coz, J. J. D.  A review on quantification learning.  _ACM Computing Surveys (CSUR)_ , 50(5):1–40, 2017\.
  * Gorber et al. (2009) Gorber, S. C., Schofield-Hurwitz, S., Hardt, J., Levasseur, G., and Tremblay, M.  The accuracy of self-reported smoking: a systematic review of the relationship between self-reported and cotinine-assessed smoking status.  _Nicotine & tobacco research_, 11(1):12–24, 2009.
  * Gretton et al. (2009) Gretton, A., Smola, A., Huang, J., Schmittfull, M., Borgwardt, K., and Schölkopf, B.  Covariate shift by kernel mean matching.  _Dataset shift in machine learning_ , 3(4):5, 2009\.
  * Heckman (1979) Heckman, J. J.  Sample selection bias as a specification error.  _Econometrica: Journal of the econometric society_ , pp. 153–161, 1979.
  * Ivanov (2020) Ivanov, D.  DEDPUL: Difference-of-estimated-densities-based positive-unlabeled learning.  In _2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA)_ , pp. 782–790. IEEE, 2020.
  * Jain et al. (2016) Jain, S., White, M., Trosset, M. W., and Radivojac, P.  Nonparametric semi-supervised learning of class proportions.  _arXiv preprint arXiv:1601.01944_ , 2016.
  * Kato et al. (2018) Kato, M., Teshima, T., and Honda, J.  Learning from positive and unlabeled data with a selection bias.  In _International conference on learning representations_ , 2018.
  * Kiryo et al. (2017) Kiryo, R., Niu, G., Du Plessis, M. C., and Sugiyama, M.  Positive-unlabeled learning with non-negative risk estimator.  _Advances in neural information processing systems_ , 30, 2017.
  * Knoll (2010) Knoll, G. F.  _Radiation detection and measurement_.  John Wiley & Sons, 2010.
  * Lawrence & Schölkopf (2001) Lawrence, N. and Schölkopf, B.  Estimating a kernel Fisher discriminant in the presence of label noise.  In _18th International Conference on Machine Learning (ICML 2001)_ , pp. 306–306. Morgan Kaufmann, 2001.
  * Li et al. (2019) Li, F., Gu, Z., Ge, L., Li, H., Tang, X., Lang, X., and Hu, B.  Review of recent gamma spectrum unfolding algorithms and their application.  _Results in Physics_ , 13:102211, 2019.
  * MacKay (2003) MacKay, D. J.  _Information theory, inference and learning algorithms_.  Cambridge university press, 2003.
  * Maity et al. (2023) Maity, S., Dutta, D., Terhorst, J., Sun, Y., and Banerjee, M.  A linear adjustment based approach to posterior drift in transfer learning.  _Biometrika_ , 2023.  URL https://doi.org/10.1093/biomet/asad029.
  * Natarajan et al. (2013) Natarajan, N., Dhillon, I. S., Ravikumar, P. K., and Tewari, A.  Learning with noisy labels.  _Advances in neural information processing systems_ , 26, 2013.
  * Ramaswamy et al. (2016) Ramaswamy, H., Scott, C., and Tewari, A.  Mixture proportion estimation via kernel embeddings of distributions.  In _International conference on machine learning_ , pp. 2052–2060. PMLR, 2016.
  * Saerens et al. (2002) Saerens, M., Latinne, P., and Decaestecker, C.  Adjusting the outputs of a classifier to new a priori probabilities: a simple procedure.  _Neural computation_ , 14(1):21–41, 2002.
  * Sanderson & Scott (2014) Sanderson, T. and Scott, C.  Class proportion estimation with application to multiclass anomaly rejection.  In _Artificial Intelligence and Statistics_ , pp. 850–858. PMLR, 2014.
  * Scott (2015) Scott, C.  A rate of convergence for mixture proportion estimation, with application to learning from noisy labels.  In _Artificial Intelligence and Statistics_ , pp. 838–846. PMLR, 2015.
  * Scott (2019) Scott, C.  A generalized Neyman-Pearson criterion for optimal domain adaptation.  In _Algorithmic Learning Theory_ , pp. 738–761. PMLR, 2019.
  * Shanmugam & Pierson (2021) Shanmugam, D. and Pierson, E.  Quantifying inequality in underreported medical conditions.  _arXiv preprint arXiv:2110.04133_ , 2021.
  * Storkey et al. (2009) Storkey, A. et al.  When training and test sets are different: characterizing learning transfer.  _Dataset shift in machine learning_ , 30:3–28, 2009.
  * Werner et al. (2018) Werner, C. J., Bull, J., Solomon, C., Brown, F., McKinney, G., Rising, M., Dixon, D., Martz, R., Hughes, H., Cox, L., et al.  MCNP 6.2 release notes.  _Los Alamos National Laboratory_ , 2018.
  * Yao et al. (2022) Yao, Y., Liu, T., Han, B., Gong, M., Niu, G., Sugiyama, M., and Tao, D.  Rethinking class-prior estimation for positive-unlabeled learning.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=aYAA-XHKyk.
  * Zhang et al. (2013) Zhang, K., Schölkopf, B., Muandet, K., and Wang, Z.  Domain adaptation under target and conditional shift.  In _International conference on machine learning_ , pp. 819–827. PMLR, 2013.
  * Zhang & Goldman (2001) Zhang, Q. and Goldman, S.  EM-DD: An improved multiple-instance learning technique.  _Advances in neural information processing systems_ , 14, 2001.

##  Appendix A Proofs

###  A.1 Proof of Proposition 2.4

######  Proposition.

Under the latent label model,

$\underset{x}{\operatorname{ess\ sup\
}}P(Y=1|X=x)=\frac{\kappa^{*}}{\kappa(F|H)}\ ,$

where $0/0:=0$.

###### Proof.

First consider the trivial case when $\kappa(F|H)=0$, then from the fact that
$\kappa^{*}\leq\kappa(F|H)$, $\kappa^{*}$ must also be $0$. According to Eqn.
(5), $P(Y=1|X=x)=0\ \forall x$, therefore the equality holds.

Then for $\kappa(F|H)>0$, we consider the cases $\kappa^{*}>0$ and
$\kappa^{*}=0$ separately. For the first case, consider two subcases: $h(x)>0$
and $h(x)=0$. In the first subcase, we have that $f(x)>0$, and therefore by
the definition of conditional probability,

$\displaystyle P(Y=1|X=x)=\frac{\kappa^{*}}{\frac{f(x)}{h(x)}}.$

Taking the essential supremum over all $x$ with $h(x)>0$,

$\displaystyle\underset{x:h(x)>0}{\operatorname{ess\ sup\ }}\ P(Y=1|X=x)$
$\displaystyle=\frac{\kappa^{*}}{\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\frac{f(x)}{h(x)}}$ $\displaystyle=\frac{\kappa^{*}}{\kappa(F|H)},$

where the second equality follows from Proposition 3. In the second subcase,
$P(Y=1|X=x)$ is zero. Therefore,

$\displaystyle\underset{x}{\operatorname{ess\ sup\ }}P(Y=1|X=x)$
$\displaystyle=\underset{x:h(x)>0}{\operatorname{ess\ sup\ }}P(Y=1|X=x)$
$\displaystyle=\frac{\kappa^{*}}{\kappa(F|H)}.$

When $\kappa^{*}=0$, $P(Y=1|X=x)=0$ for all $x$, and the equality still holds.
∎

###  A.2 Proof of Theorem 3.1

######  Theorem (Identifiability Under Local Supremal Posterior (LSP)).

Let $A$ be any non-empty measurable subset of $E_{H}=\\{x:h(x)>0\\}$ and
$s=\underset{x\in A}{\operatorname{ess\ sup\ }}P(Y=1|X=x)$, then

$\displaystyle\kappa^{*}=s\cdot\inf_{S\subseteq
A}\frac{F(S)}{H(S)}=s\cdot\underset{x\in A}{\operatorname{ess\ inf\
}}\frac{f(x)}{h(x)}.$

###### Proof.

Consider the case of $\kappa^{*}>0$ and $\kappa^{*}=0$ separately.

If $\kappa^{*}>0$, then $E_{H}=\\{x:h(x)>0\\}\subseteq E_{F}=\\{x:f(x)>0\\}$.
Recall from Eqn. (5),

$\displaystyle P(Y=1|X=x)=\kappa^{*}\cdot\frac{h(x)}{f(x)}\quad\text{when
}f(x)>0.$

Taking the essential supremum over $A$ and recall the definition of $s$,

$\displaystyle s=\underset{x\in A}{\operatorname{ess\ sup\ }}P(Y=1|X=x)$
$\displaystyle=\kappa^{*}\cdot\underset{x\in A}{\operatorname{ess\ sup\
}}\frac{h(x)}{f(x)}.$

Since $A\subseteq E_{H}\subseteq E_{F}$, $f(x)$ and $h(x)$ are both positive
for $x\in A$. Rearrange the denominator

$\displaystyle s=\kappa^{*}\cdot\frac{1}{\underset{x\in A}{\operatorname{ess\
inf\ }}\frac{f(x)}{h(x)}},$

take the denominator to the other side, we get

$\displaystyle\kappa^{*}=s\cdot\underset{x\in A}{\operatorname{ess\ inf\
}}\frac{f(x)}{h(x)}=s\cdot\inf_{S\subseteq A}\frac{F(S)}{H(S)},$

where the second equality follows from the identity that $\underset{x\in
A}{\operatorname{ess\ inf\ }}\frac{f(x)}{h(x)}=\inf_{S\subseteq
A}\frac{F(S)}{H(S)}$.

If $\kappa^{*}=0$, then $s=0$, the above equality still holds. ∎

###  A.3 Proof of Theorem 3.2

######  Theorem (Identifiability Under Tight Posterior Upper Bound).

Consider any non-empty measurable set $A\subseteq E_{H}=\\{x:h(x)>0\\}$, and
let $s=\underset{x\in A}{\operatorname{ess\ sup\ }}P(Y=1|X=x)$. Let
$\alpha(x)$ be any measurable function satisfying

$\alpha(x)\in\begin{cases}\left[P(Y=1|X=x),s\right],&x\in A,\\\
\left[P(Y=1|X=x),1\right],&\text{o.w.}\end{cases}$ (13)

Define a new distribution $\widetilde{F}$ in terms of its density

$\begin{split}&\widetilde{f}(x)=\frac{1}{c}\cdot\alpha(x)\cdot f(x),\\\ \text{
where }\quad&c=\int\alpha(x)f(x)dx=\mathbb{E}_{X\sim
F}\left[\alpha(x)\right].\end{split}$ (14)

Then

$\displaystyle\kappa^{*}=c\cdot\kappa(\widetilde{F}|H).$

###### Proof.

Write $\kappa(\widetilde{F}|H)$ explicitly according to Proposition 3 and Eqn.
(14),

$\displaystyle c\cdot\kappa(\widetilde{F}|H)$
$\displaystyle=c\cdot\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\frac{\widetilde{f}(x)}{h(x)}\quad\text{by definition of
$\kappa(\widetilde{F}|H)$}$
$\displaystyle=c\cdot\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\frac{\frac{1}{c}\cdot\alpha(x)\cdot f(x)}{h(x)}\quad\text{plug in the
expression of $\widetilde{f}(x)$}$
$\displaystyle=\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\frac{\alpha(x)\cdot f(x)}{h(x)}.$

We will show that it equals to $\kappa^{*}$ by proving it is both upper and
lower bound of $\kappa^{*}$.

From Eqn. (13), we can conclude that $\alpha(x)\geq P(Y=1|X=x)\ \ \forall x$,
then

$\displaystyle c\cdot\kappa(\widetilde{F}|H)$
$\displaystyle\geq\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\frac{P(Y=1|X=x)\cdot f(x)}{h(x)}$
$\displaystyle=\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\kappa^{*}\quad\text{rearrange Eqn. \eqref{eq:cond}}$
$\displaystyle=\kappa^{*}.$

Meanwhile, consider $x\in A$

$\displaystyle c\cdot\kappa(\widetilde{F}|H)$
$\displaystyle=\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\frac{\alpha(x)\cdot f(x)}{h(x)}$ $\displaystyle\leq\underset{x\in
A}{\operatorname{ess\ inf\ }}\frac{\alpha(x)\cdot
f(x)}{h(x)}\quad\text{replace $E_{H}$ by $A$}$
$\displaystyle\leq\underset{x\in A}{\operatorname{ess\ inf\ }}\frac{s\cdot
f(x)}{h(x)}\quad\text{because $\alpha(x)\leq s,\forall x\in A$}$
$\displaystyle=\kappa^{*}\quad\text{by Theorem \ref{thm:identify}}$

This shows that $c\cdot\kappa(\widetilde{F}|H)=\kappa^{*}$. ∎

###  A.4 Proof of Corollary 3.3

######  Corollary.

Let $\alpha(x)$ be any measurable function with

$\alpha(x)\in[P(Y=1|X=x),1]\quad\forall x.$

Define a new distribution $\widetilde{F}$ in terms of its density
$\widetilde{f}$, obtained by Eqn. (7). Then

$\displaystyle\kappa^{*}\leq c\cdot\kappa(\widetilde{F}|H)\leq\kappa(F|H).$

###### Proof.

From the proof of Theorem 3.2, we know that

$\displaystyle
c\cdot\kappa(\widetilde{F}|H)=\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\frac{\alpha(x)\cdot f(x)}{h(x)}$

From the fact that $\alpha(x)\geq P(Y=1|X=x)\ \forall x$, we have

$\displaystyle c\cdot\kappa(\widetilde{F}|H)$
$\displaystyle\geq\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\frac{P(Y=1|X=x)\cdot f(x)}{h(x)}$
$\displaystyle=\underset{x:h(x)>0}{\operatorname{ess\ inf\ }}\kappa^{*}$
$\displaystyle=\kappa^{*}.$

What’s more, since $\alpha\leq 1\ \forall x$,

$\displaystyle
c\cdot\kappa(\widetilde{F}|H)\leq\underset{x:h(x)>0}{\operatorname{ess\ inf\
}}\frac{1\cdot f(x)}{h(x)}=\kappa(F|H).$

∎

###  A.5 Proof of Theorem 4.1

We now establish a rate of convergence result for estimator
$\widehat{\kappa}^{*}=\widehat{c}\cdot\widehat{\kappa}(\widetilde{F}|H)$ from
Algorithm 1.

######  Theorem.

Assume $\alpha(x)$ satisfies the condition in Eqn. (6). After subsampling,
assume the resulting $\widetilde{F}$ and $H$ are such that
$\underset{S\in\mathcal{A}:H(S)>0}{\operatorname{arg\ min\
}}\frac{\widetilde{F}(S)}{H(S)}$ exists. Then there exists a constant $C>0$
and an existing estimator $\widehat{\kappa}$ such that for $m$ and $n$
sufficiently large, the estimator $\widehat{\kappa}^{*}$ from Algorithm 1
satisfies

$\Pr\left(\left|\widehat{\kappa}^{*}-\kappa^{*}\right|\leq
C\left[\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log n}{n}}\right]\right)\geq
1-\mathcal{O}\left(\frac{1}{m}+\frac{1}{n}\right).$

###### Proof.

Recall the setup, we originally have i.i.d. sample 777 The notation here is a
bit different from Eqn. (1) in that the index of $X_{i}$ is changed. This
allows for more concise notation in the following derivation.

$\begin{split}X_{F}&:=\left\\{X_{1},X_{2},\cdots,X_{n}\right\\}\stackrel{{\scriptstyle
iid}}{{\sim}}F,\\\
X_{H}&:=\left\\{X_{n+1},X_{n+2},\cdots,X_{n+m}\right\\}\stackrel{{\scriptstyle
iid}}{{\sim}}H.\end{split}$

After rejection sampling, we obtain $n^{\prime}$ i.i.d. sample
$X_{\widetilde{F}}\sim\widetilde{F}$ (where
$\mathbb{E}\left[n^{\prime}\right]=c\cdot n$ and $c=\int\alpha(x)f(x)dx$),
from which we can estimate $\kappa(\widetilde{F}|H)$. Under the assumption
that $\underset{S\in\mathcal{A}:H(S)>0}{\operatorname{arg\ min\
}}\frac{\widetilde{F}(S)}{H(S)}$ exists, estimator
$\widehat{\kappa}(\widetilde{F}|H)$ by Scott (2015) has rate of convergence

$\Pr\left(\left|\widehat{\kappa}(\widetilde{F}|H)-\kappa(\widetilde{F}|H)\right|\leq
C_{1}\left[\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log
n^{\prime}}{n^{\prime}}}\right]\right)\geq
1-\frac{2}{m}-\frac{2}{n^{\prime}}.$ (15)

Now $n^{\prime}$ is a random variable here, and we want to establish a rate of
convergence result involving $n$. This can be done by applying a concentration
inequality for $n^{\prime}$.

######  Theorem.

(Hoeffding’s Inequality) Let $Z_{1},\cdots Z_{n}$ be independent random
variables on $\mathbb{R}$ that take values in $[0,1]$. Denote
$Z=\frac{1}{n}\sum_{i=1}^{n}Z_{i}$, then for all $\epsilon>0$,

$\Pr\left(\left|\frac{1}{n}\sum_{i=1}^{n}Z_{i}-\mathbb{E}\left[Z\right]\right|\leq\epsilon\right)\geq
1-2\exp(-2n\epsilon^{2}).$

Let $\delta=2\exp{(-2n\epsilon^{2})}$, the theorem can be restated as:

$\Pr\left(\left|\frac{1}{n}\sum_{i=1}^{n}Z_{i}-\mathbb{E}\left[Z\right]\right|\leq\sqrt{\frac{\log(1/\delta)}{2n}}\right)\geq
1-\delta.$

Take $Z_{i}=\mathbbm{1}_{\\{V_{i}\leq\alpha(X_{i})\\}}$, where
$i\in\\{1,2,\cdots,n\\}$, $V_{i}$ denotes the $i$-th independent draw from
$\text{Uniform}(0,1)$ 888$V_{i}$ is used in rejection sampling (Algorihm 4).
and $X_{i}$ denote the $i$-th draw from $F$. Then

$\displaystyle n^{\prime}=\sum_{i=1}^{n}Z_{i},$
$\displaystyle\mathbb{E}\left[Z\right]=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[Z_{i}\right]=\mathbb{E}_{(X_{i},V_{i})}\left[Z_{i}\right]=\mathbb{E}_{X_{i}}\left[\mathbb{E}_{V_{i}|X_{i}}\left[\mathbbm{1}_{\\{V_{i}\leq\alpha(X_{i})\\}}\right]\right]=\mathbb{E}_{X_{i}}\left[\alpha(X_{i})\right]=\int\alpha(x)f(x)dx=c.$

Plug into Hoeffding’s Inequality and setting $\epsilon=\frac{c}{2}$, we have

$\Pr\left(\left|n^{\prime}-c\cdot n\right|\leq\frac{c}{2}\cdot n\right)\geq
1-2\exp\left(-\frac{c}{2}n\right),$ (16)

which allows us to bound $n^{\prime}$ by a constant times $n$.

Now we can establish a rate of convergence result of
$\widehat{\kappa}(\widetilde{F}|H)$ w.r.t. $n$

$\displaystyle\Pr\left(\left|\widehat{\kappa}(\widetilde{F}|H)-\kappa(\widetilde{F}|H)\right|\leq
C_{2}\left[\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log n}{n}}\right]\right)$
$\displaystyle\geq\ $
$\displaystyle\Pr\left(\left(\left|\widehat{\kappa}(\widetilde{F}|H)-\kappa(\widetilde{F}|H)\right|\leq
C_{2}\left[\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log
n}{n}}\right]\right)\text{and}\left(\frac{c}{2}\cdot n\leq
n^{\prime}\leq\frac{3c}{2}\cdot
n\right)\right)\quad\because\Pr(A)\geq\Pr(A\cap B)$ $\displaystyle=\ $
$\displaystyle\Pr\left(\left(\left|\widehat{\kappa}(\widetilde{F}|H)-\kappa(\widetilde{F}|H)\right|\leq
C_{2}\left[\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log
n}{n}}\right]\right)\Biggl{|}\left(\frac{c}{2}\cdot n\leq
n^{\prime}\leq\frac{3c}{2}\cdot n\right)\right)\cdot\Pr\left(\frac{c}{2}\cdot
n\leq n^{\prime}\leq\frac{3c}{2}\cdot n\right)$ $\displaystyle\geq\ $
$\displaystyle\left(1-\mathcal{O}\left(\frac{1}{m}+\frac{1}{n}\right)\right)\cdot\left(1-2\exp\left(-\frac{c}{2}n\right)\right)\quad\because\text{$n$
and $n^{\prime}$ can be used interchangeably in the first probability term}$
$\displaystyle\geq\ $ $\displaystyle
1-\mathcal{O}\left(\frac{1}{m}+\frac{1}{n}\right)-2\exp\left(-\frac{c}{2}n\right)\quad\because(1-a)(1-b)\geq
1-a-b$ $\displaystyle\geq\ $ $\displaystyle
1-\mathcal{O}\left(\frac{1}{m}+\frac{1}{n}\right)\quad\because\exp(-n)\text{
decays faster}$

As for the estimator of $c=\mathbb{E}_{X\sim F}\left[\alpha(x)\right]$, the
rate of convergence can also be shown via Hoeffding’s Inequality,

$\displaystyle\widehat{c}=\frac{n^{\prime}}{n}=\frac{1}{n}\sum_{i=1}^{n}Z_{i},\quad
c=\mathbb{E}\left[Z\right].$

Plug into Hoeffding’s Inequality and let the confidence $\delta=1/n$, we have

$\Pr\left(\left|\widehat{c}-c\right|\leq\sqrt{\frac{\log n}{2n}}\right)\geq
1-1/n.$ (17)

Note that by triangle inequality

$\displaystyle\left|\widehat{c}\cdot\widehat{\kappa}(\widetilde{F}|H)-c\cdot\kappa(\widetilde{F}|H)\right|$
$\displaystyle=\left|\widehat{c}\cdot\widehat{\kappa}(\widetilde{F}|H)-\widehat{c}\cdot\kappa(\widetilde{F}|H)+\widehat{c}\cdot\kappa(\widetilde{F}|H)-c\cdot\kappa(\widetilde{F}|H)\right|$
$\displaystyle\leq\left|\widehat{c}\cdot\widehat{\kappa}(\widetilde{F}|H)-\widehat{c}\cdot\kappa(\widetilde{F}|H)\right|+\left|\widehat{c}\cdot\kappa(\widetilde{F}|H)-c\cdot\kappa(\widetilde{F}|H)\right|$
$\displaystyle=\left|\widehat{c}\right|\cdot\left|\widehat{\kappa}(\widetilde{F}|H)-\kappa(\widetilde{F}|H)\right|+\left|\kappa(\widetilde{F}|H)\right|\cdot\left|\widehat{c}-c\right|$
$\displaystyle\leq\left|\widehat{\kappa}(\widetilde{F}|H)-\kappa(\widetilde{F}|H)\right|+\left|\widehat{c}-c\right|.$

Finally, combine all previous results

$\displaystyle\Pr\left(\left|\widehat{\kappa}^{*}-\kappa^{*}\right|\leq
C\left[\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log n}{n}}\right]\right)$
$\displaystyle=\ $
$\displaystyle\Pr\left(\left|\widehat{c}\cdot\widehat{\kappa}(\widetilde{F}|H)-c\cdot\kappa(\widetilde{F}|H)\right|\leq
C\left[\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log n}{n}}\right]\right)$
$\displaystyle\geq\ $
$\displaystyle\Pr\left(\left|\widehat{\kappa}(\widetilde{F}|H)-\kappa(\widetilde{F}|H)\right|+\left|\widehat{c}-c\right|\leq
C\left[\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log n}{n}}\right]\right)$
$\displaystyle\geq\ $
$\displaystyle\Pr\left(\left(\left|\widehat{\kappa}(\widetilde{F}|H)-\kappa(\widetilde{F}|H)\right|\leq\frac{C}{2}\left[\sqrt{\frac{\log
m}{m}}+\sqrt{\frac{\log
n}{n}}\right]\right)\text{and}\left(\left|\widehat{c}-c\right|\leq\frac{C}{2}\left[\sqrt{\frac{\log
m}{m}}+\sqrt{\frac{\log n}{n}}\right]\right)\right)$ $\displaystyle\geq\ $
$\displaystyle 1-\mathcal{O}\left(\frac{1}{m}+\frac{1}{n}\right),$

then we can conclude that $\widehat{\kappa}^{*}\rightarrow\kappa^{*}$ with
rate of convergence $O\left(\sqrt{\frac{\log m}{m}}+\sqrt{\frac{\log
n}{n}}\right)$.

∎

###  A.6 Proof of Proposition 5.2

######  Proposition.

For $\kappa(F|H^{\prime})$ obtained from ReMPE-2:

$\displaystyle\kappa(F|H^{\prime})<\kappa(F|H).$

###### Proof.

From the fact that $B=\underset{S\in\mathfrak{S}}{\operatorname{arg\ min\
}}\frac{F(S)}{H(S)}$, we have

$\displaystyle\kappa(F|H)=\inf_{S\in\mathcal{A}:H(S)>0}\frac{F(S)}{H(S)}=\frac{F(B)}{H(B)}.$

After regrouping, $H^{\prime}(B)>H(B)$. Therefore,

$\displaystyle\kappa(F|H^{\prime})$
$\displaystyle=\inf_{S\in\mathcal{A}:H^{\prime}(S)>0}\frac{F(S)}{H^{\prime}(S)}$
$\displaystyle=\frac{F(B)}{H^{\prime}(B)}$ $\displaystyle<\frac{F(B)}{H(B)}$
$\displaystyle=\kappa(F|H).$

∎

##  Appendix B More about Subsampling MPE

###  B.1 Intuition

Theorem 3.2 and Corollary 3.3 have already justified the use of subsampling.
Here, we explain in another perspective (in terms of distributions, similar to
the analysis in Yao et al. (2022)). The idea is that, since the original $G$
may violate irreducibility assumption, we modify $G$ such that the resulting
latent component distribution is less likely to violate the assumption.

Write the unknown distribution $G$ itself as a mixture $G=\gamma
G_{1}+(1-\gamma)G_{2},\ \gamma\geq 0$. Then $F$ becomes:

$\displaystyle F$ $\displaystyle=(1-\kappa^{*})G+\kappa^{*}H$
$\displaystyle=(1-\kappa^{*})\left[\gamma
G_{1}+(1-\gamma)G_{2}\right]+\kappa^{*}H.$

Switch $G_{1}$ to the other side (i.e., discarding the probability mass from
$G_{1}$)

$\displaystyle
F-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}(1-\kappa^{*})\gamma
G_{1}}$ $\displaystyle=(1-\kappa^{*})(1-\gamma)G_{2}+\kappa^{*}H,$

the left hand side can be re-written as

$\displaystyle\underbrace{\left[1-(1-\kappa^{*})\gamma\right]}_{:=c,\text{
normalizing
const.}}\underbrace{\frac{1}{1-(1-\kappa^{*})\gamma}\left[F-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}(1-\kappa^{*})\gamma
G_{1}}\right]}_{:=\widetilde{F},\textbf{ after subsampling}}.$

Then the resulting distribution $\widetilde{F}$ is

$\displaystyle\widetilde{F}$
$\displaystyle=\frac{(1-\kappa^{*})(1-\gamma)}{c}G_{2}+\frac{\kappa^{*}}{c}H$
$\displaystyle=:(1-\tilde{\kappa}^{*})\widetilde{G}+\tilde{\kappa}^{*}H.$

By discarding a portion of probability mass from $G$, which is done by
subsampling in practice, the resulting latent component distribution
$\widetilde{G}$ is less likely to violate the irreducibility assumption. The
new mixture proportion $\tilde{\kappa}^{*}=\kappa^{*}/c$.

In the following, we provide justification of the above claim, which can also
be seen as a reformulation of Corollary 3.3.

######  Proposition B.1.

Given some probability mass from $G$ being dropped out,
$c\cdot\kappa(\widetilde{F}|H)$ is always bounded by: κ^* ≤c ⋅κ(~F—H) ≤κ(F—H).
Furthermore, bias is strictly reduced when
$(1-\gamma)\kappa(G_{2}|H)<\kappa(G|H)$.

###### Proof.

Observe that

$\displaystyle c\cdot\kappa(\widetilde{F}|H)$
$\displaystyle=\inf_{S\in\mathcal{A}:H(S)>0}\frac{c\cdot\widetilde{F}(S)}{H(S)}$
$\displaystyle=\kappa^{*}+(1-\kappa^{*})\inf_{S\in\mathcal{A}:H(S)>0}\frac{(1-\gamma)G_{2}(S)}{H(S)},$

therefore $c\cdot\kappa(\widetilde{F}|H)\geq\kappa^{*}$.

From the fact that $G=\gamma G_{1}+(1-\gamma)G_{2}$, we have
$G\geq(1-\gamma)G_{2}$. Then

$\displaystyle c\cdot\kappa(\widetilde{F}|H)$
$\displaystyle\leq\kappa^{*}+(1-\kappa^{*})\inf_{S\in\mathcal{A}:H(S)>0}\frac{G(S)}{H(S)}$
$\displaystyle=\kappa(F|H).$

To have bias reduction, we need $c\cdot\kappa(\widetilde{F}|H)<\kappa(F|H)$,
where both quantities can be represented as

$\displaystyle c\cdot\kappa(\widetilde{F}|H)$
$\displaystyle=\kappa^{*}+(1-\kappa^{*})(1-\gamma)\kappa(G_{2}|H)$
$\displaystyle\kappa(F|H)$
$\displaystyle=\kappa^{*}+(1-\kappa^{*})\kappa(G|H).$

Then we can get the result of $(1-\gamma)\kappa(G_{2}|H)<\kappa(G|H)$ by
direct comparison. ∎

Based on the above proof, we claim that $c\cdot\kappa(\widetilde{F}|H)$ leads
to no worse estimation bias than $\kappa(F|H)$. To be specific, when $G$ is
irreducible w.r.t. $H$, then
$\kappa^{*}=c\cdot\kappa(\widetilde{F}|H)=\kappa(F|H)$. When $G$ is not
irreducible w.r.t. $H$, then $\kappa^{*}\leq
c\cdot\kappa(\widetilde{F}|H)\leq\kappa(F|H)$. The key difference compared to
Yao et al. (2022)’s approach is that we are modifying $G$, thus equivalently
subsampling $F$, rather than regrouping on $H$.

In summary, without making assumptions about irreducibility, as long as we
remove some contribution from $G$ in $F$ by subsampling, the resulting
identifiable quantity $c\cdot\kappa(\widetilde{F}|H)$ will be at least no
worse than the maximum proportion $\kappa(F|H)$. Furthermore, with the
knowledge of set $A$ and $\underset{x\in A}{\operatorname{ess\ sup\
}}P(Y=1|X=x)$, $c\cdot\kappa(\widetilde{F}|H)$ will equal to $\kappa^{*}$.

###  B.2 Rejection Sampling

Rejection sampling is a Monte Carlo method that aims to generate sample
following a new distribution $\widetilde{Q}$ based on sample from distribution
$Q$, which are characterised by the densities $\widetilde{q}$ and $q$. An
instance $x$ drawn from $q(x)$ is kept with acceptance probability
$\beta(x)\in[0,1]$, and rejected otherwise. Algorithm 4 shows the detailed
procedure.

Algorithm 4 Rejection Sampling

Input: sample $[x_{i}]=\\{x_{1},\cdots,x_{n}\\}\sim q(x)$, acceptance function
$\beta(x)$

Output: sample
$\left[z_{j}\right]\sim\widetilde{q}(x)=\frac{1}{c}\cdot\beta(x)\cdot q(x)$,
where $c=\int\beta(x)q(x)dx=\mathbb{E}_{X\sim q}\left[\beta(X)\right]$

Initialize $j\leftarrow 1$

for $i=1$ to $n$ do

$v\sim\text{Uniform}(0,1)$

if $v\leq\beta(x)$ then

$z_{j}\leftarrow x_{i}$

$j\leftarrow j+1$

end if

end for

return $\left[z_{j}\right]$

###  B.3 Gamma Spectrum Unfolding

In gamma spectrum unfolding, a gamma ray detector measures the energies of
incoming gamma ray particles. The gamma rays were emitted either by a source
of interest or from the background. The measurement is represented as a
histogram $f(x)$, where the bins correspond to a quantization of energy. The
histogram $h(x)$ of measurements from the source of interest is also known.

The goal is to obtain a lower bound $\rho(x)$ of the quantity
$(1-\kappa^{*})g(x)$ on a certain set $A\subset\operatorname{supp}(H)$. We
specify $A$ to be the energy bins near the main peak of $h(x)$ (aka, full-
energy peak). For
$x\in\operatorname{supp}(F)\backslash\operatorname{supp}(H)$, $\rho(x)=f(x)$
because the gamma rays must come from the background in these regions.
Typically, $\operatorname{supp}(F)\backslash\operatorname{supp}(H)$ contains
two (or more) intervals, therefore we know the value of $\rho(x)$ on either
side of set $A$. Then $\rho(x)\ \forall x\in A$ can be estimated using linear
interpolation (Knoll, 2010; Alamaniotis et al., 2013). The above procedure is
illustrated in Figure 1 and the acceptance function is chosen to be

$\alpha(x)=\begin{cases}1-\frac{\rho(x)}{f(x)},&x\in A,\\\
1,&\text{o.w.}\end{cases}$ (18)

Figure 1: Visual illustration of how to estimate $\rho(x)$

##  Appendix C Detailed Experimental Result in Sec. 6

This section shows four tables corresponding to four experimental setups in
Sec. 6.

Table 2: Average absolute estimation error on gamma ray spectra data,
corresponding to the unfolding scenario. Several state-of-the-art MPE
algorithms DPL (Ivanov, 2020), EN (Elkan & Noto, 2008), KM (Ramaswamy et al.,
2016) and TIcE (Bekker & Davis, 2018) are selected. The mean absolute error
($\text{avg}[\left|\widehat{\kappa}^{*}-\kappa^{*}\right|]$) is reported, the
smallest error among original, regrouping and subsampling versions is bolded.
$(+/-)$ denotes that on average the estimator produces positive$/$negative
estimation bias ($\text{sgn}[\text{avg}(\widehat{\kappa}^{*}-\kappa^{*})]$).

$\kappa^{*}$ | DPL | ReDPL | SuDPL | EN | ReEN | SuEN | KM | ReKM | SuKM | TIcE | ReTIcE | SuTIcE
---|---|---|---|---|---|---|---|---|---|---|---|---
$0.1$ | $0.063+$ | $0.053+$ | $\bm{0.008+}$ | $0.057+$ | $0.048+$ | $\bm{0.012-}$ | $0.226+$ | $0.146+$ | $\bm{0.036+}$ | $0.129+$ | $0.115+$ | $\bm{0.019+}$
$0.25$ | $0.055+$ | $\bm{0.008+}$ | $0.011+$ | $0.040+$ | $\bm{0.004-}$ | $0.017-$ | $0.216+$ | $\bm{0.020+}$ | $0.059+$ | $0.112+$ | $0.065+$ | $\bm{0.017+}$
$0.5$ | $0.029+$ | $0.123-$ | $\bm{0.019-}$ | $\bm{0.017+}$ | $0.129-$ | $0.032-$ | $0.130+$ | $\bm{0.043+}$ | $0.049+$ | $0.082+$ | $\bm{0.018+}$ | $0.019+$
$0.75$ | $0.034+$ | $0.284-$ | $\bm{0.015+}$ | $\bm{0.022-}$ | $0.289-$ | $0.047-$ | $0.078+$ | $0.094-$ | $\bm{0.022+}$ | $0.055+$ | $0.045-$ | $\bm{0.021+}$
average | $0.045+$ | $0.117-$ | $\bm{0.013+}$ | $0.034+$ | $0.118-$ | $\bm{0.027-}$ | $0.163+$ | $0.076+$ | $\bm{0.042+}$ | $0.095+$ | $0.061+$ | $\bm{0.019+}$

Table 3: Average absolute estimation error on synthetic data, corresponding to
domain adaptation scenario. Several state-of-the-art MPE algorithms DPL
(Ivanov, 2020), EN (Elkan & Noto, 2008), KM (Ramaswamy et al., 2016) and TIcE
(Bekker & Davis, 2018) are selected. The mean absolute error
($\text{avg}[\left|\widehat{\kappa}^{*}-\kappa^{*}\right|]$) is reported, and
the smallest error among the original, regrouping and subsampling versions is
bolded. $(+/-)$ denotes that on average the estimator produces
positive$/$negative estimation bias
($\text{sgn}[\text{avg}(\widehat{\kappa}^{*}-\kappa^{*})]$).

$\kappa^{*}$ | DPL | ReDPL | SuDPL | EN | ReEN | SuEN | KM | ReKM | SuKM | TIcE | ReTIcE | SuTIcE
---|---|---|---|---|---|---|---|---|---|---|---|---
$0.1$ | $0.089+$ | $0.075+$ | $\bm{0.014-}$ | $0.059+$ | $0.051+$ | $\bm{0.027-}$ | $0.102+$ | $0.091+$ | $\bm{0.013-}$ | $0.150+$ | $0.140+$ | $\bm{0.038+}$
$0.25$ | $0.083+$ | $0.060+$ | $\bm{0.016-}$ | $0.037+$ | $\bm{0.016+}$ | $0.051-$ | $0.081+$ | $0.059+$ | $\bm{0.018-}$ | $0.137+$ | $0.108+$ | $\bm{0.040+}$
$0.5$ | $0.053+$ | $0.028+$ | $\bm{0.024-}$ | $\bm{0.022-}$ | $0.057-$ | $0.077-$ | $0.052+$ | $0.037+$ | $\bm{0.020-}$ | $0.114+$ | $0.068+$ | $\bm{0.035+}$
$0.75$ | $\bm{0.016-}$ | $0.050-$ | $0.056-$ | $\bm{0.063-}$ | $0.118-$ | $0.114-$ | $\bm{0.018+}$ | $0.050-$ | $0.036-$ | $0.112+$ | $0.058+$ | $\bm{0.051+}$
average | $0.060+$ | $0.053+$ | $\bm{0.028-}$ | $\bm{0.045-}$ | $0.061-$ | $0.067-$ | $0.063+$ | $0.059+$ | $\bm{0.022-}$ | $0.128+$ | $0.094+$ | $\bm{0.041+}$

Table 4: Average absolute estimation error on benchmark data, corresponding to
domain adaptation scenario. Several state-of-the-art MPE algorithms DPL
(Ivanov, 2020), EN (Elkan & Noto, 2008), KM (Ramaswamy et al., 2016) and TIcE
(Bekker & Davis, 2018) are selected. The mean absolute error is reported, and
the smallest error among the original, regrouping and subsampling versions is
bolded. $+/-/\cdot$ denotes that on average the estimator produces
positive$/$negative/no estimation bias.

Dataset | $\kappa^{*}$ | DPL | ReDPL | SuDPL | EN | ReEN | SuEN | KM | ReKM | SuKM | TIcE | ReTIcE | SuTIcE
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Mushroom | $0.1$ | $0.075+$ | $0.069+$ | $\bm{0.053+}$ | $0.121+$ | $0.105+$ | $\bm{0.099+}$ | $0.061+$ | $0.054+$ | $\bm{0.039+}$ | $0.082+$ | $0.086+$ | $\bm{0.064+}$
$0.25$ | $0.063+$ | $\bm{0.023+}$ | $0.040+$ | $0.139+$ | $\bm{0.101+}$ | $0.109+$ | $0.053+$ | $0.041+$ | $\bm{0.024+}$ | $0.057+$ | $0.034+$ | $\bm{0.024+}$
$0.5$ | $0.035+$ | $0.084-$ | $\bm{0.025+}$ | $0.132+$ | $\bm{0.074+}$ | $0.112+$ | $\bm{0.057-}$ | $0.189-$ | $0.063-$ | $\bm{0.026+}$ | $0.058-$ | $0.028-$
$0.75$ | $0.015-$ | $0.149-$ | $\bm{0.013-}$ | $0.097+$ | $\bm{0.033+}$ | $0.082+$ | $\bm{0.096-}$ | $0.253-$ | $0.108-$ | $0.076-$ | $0.134-$ | $\bm{0.027-}$
| avg | $0.047+$ | $0.081-$ | $\bm{0.033+}$ | $0.122+$ | $\bm{0.078+}$ | $0.101+$ | $0.067-$ | $0.134-$ | $\bm{0.059-}$ | $0.060+$ | $0.078-$ | $\bm{0.036+}$
Landsat | $0.1$ | $0.066+$ | $0.053+$ | $\bm{0.014+}$ | $0.168+$ | $0.139+$ | $\bm{0.115+}$ | $0.065+$ | $0.047+$ | $\bm{0.017+}$ | $0.070+$ | $0.074+$ | $\bm{0.031+}$
$0.25$ | $0.060+$ | $0.010-$ | $\bm{0.005+}$ | $0.161+$ | $0.119+$ | $\bm{0.100+}$ | $0.053+$ | $0.027+$ | $\bm{0.007+}$ | $0.034+$ | $0.028+$ | $\bm{0.012-}$
$0.5$ | $0.037+$ | $0.034-$ | $\bm{0.010-}$ | $0.131+$ | $0.097+$ | $\bm{0.084+}$ | $0.037+$ | $0.018+$ | $\bm{0.016-}$ | $0.033+$ | $0.031-$ | $\bm{0.030-}$
$0.75$ | $\bm{0.022+}$ | $0.071-$ | $0.037-$ | $0.102+$ | $0.085+$ | $\bm{0.041+}$ | $0.028+$ | $\bm{0.023-}$ | $0.024-$ | $\bm{0.036-}$ | $0.042-$ | $0.067-$
| avg | $0.046+$ | $0.042-$ | $\bm{0.017-}$ | $0.141+$ | $0.110+$ | $\bm{0.085+}$ | $0.046+$ | $0.029+$ | $\bm{0.016-}$ | $0.043+$ | $0.044-$ | $\bm{0.035-}$
Shuttle | $0.1$ | $0.055+$ | $0.048+$ | $\bm{0.006+}$ | $0.105+$ | $0.096+$ | $\bm{0.053+}$ | $0.044+$ | $0.033+$ | $\bm{0.006-}$ | $0.083+$ | $0.072+$ | $\bm{0.023+}$
$0.25$ | $0.045+$ | $0.010-$ | $\bm{0.007-}$ | $0.098+$ | $0.082+$ | $\bm{0.038+}$ | $0.027+$ | $0.018-$ | $\bm{0.016-}$ | $0.074+$ | $0.030+$ | $\bm{0.020+}$
$0.5$ | $0.025+$ | $0.102-$ | $\bm{0.016-}$ | $0.093+$ | $0.066+$ | $\bm{0.050+}$ | $\bm{0.017-}$ | $0.099-$ | $0.030-$ | $0.074+$ | $0.065-$ | $\bm{0.041+}$
$0.75$ | $\bm{0.022-}$ | $0.393-$ | $0.033-$ | $0.063+$ | $\bm{0.041+}$ | $0.044+$ | $\bm{0.058-}$ | $0.294-$ | $0.075-$ | $0.089+$ | $0.179-$ | $\bm{0.068+}$
| avg | $0.037+$ | $0.138-$ | $\bm{0.015-}$ | $0.090+$ | $0.071+$ | $\bm{0.046+}$ | $0.036+$ | $0.111-$ | $\bm{0.032-}$ | $0.080+$ | $0.086-$ | $\bm{0.038+}$
MNIST17 | $0.1$ | $0.076+$ | $0.078+$ | $\bm{0.035+}$ | $0.184+$ | $0.157+$ | $\bm{0.116+}$ | $0.065+$ | $0.057+$ | $\bm{0.025+}$ | $0.101+$ | $0.093+$ | $\bm{0.052+}$
$0.25$ | $0.058+$ | $0.047+$ | $\bm{0.008-}$ | $0.218+$ | $0.175+$ | $\bm{0.138+}$ | $0.053+$ | $0.017+$ | $\bm{0.009-}$ | $0.098+$ | $0.084+$ | $\bm{0.031+}$
$0.5$ | $0.032+$ | $0.047-$ | $\bm{0.022-}$ | $0.275+$ | $\bm{0.180+}$ | $0.191+$ | $0.029+$ | $0.030-$ | $\bm{0.017-}$ | $0.080+$ | $\bm{0.021+}$ | $0.047+$
$0.75$ | $\bm{0.023-}$ | $0.169-$ | $0.046-$ | $0.250+$ | $\bm{0.189+}$ | $0.217+$ | $\bm{0.016+}$ | $0.146-$ | $\bm{0.016-}$ | $0.081+$ | $0.094-$ | $\bm{0.060+}$
| avg | $0.047+$ | $0.085-$ | $\bm{0.028-}$ | $0.231+$ | $0.175+$ | $\bm{0.166+}$ | $0.041+$ | $0.063-$ | $\bm{0.017-}$ | $0.090+$ | $0.073-$ | $\bm{0.048+}$
Overall | avg | $0.044+$ | $0.087-$ | $\bm{0.023-}$ | $0.146+$ | $0.109+$ | $\bm{0.099+}$ | $0.047+$ | $0.084-$ | $\bm{0.031-}$ | $0.068+$ | $0.070-$ | $\bm{0.039+}$

Table 5: Average absolute estimation error on benchmark data, corresponding to
the selected/reported at random scenario. Several state-of-the-art MPE
algorithms DPL (Ivanov, 2020), EN (Elkan & Noto, 2008), KM (Ramaswamy et al.,
2016) and TIcE (Bekker & Davis, 2018) are selected. The mean absolute error is
reported, the smallest error among the original, regrouping and subsampling
versions is bolded. $+/-/\cdot$ denotes that on average the estimator produces
positive$/$negative/no estimation bias.

Dataset | $\kappa^{*}$ | DPL | ReDPL | SuDPL | EN | ReEN | SuEN | KM | ReKM | SuKM | TIcE | ReTIcE | SuTIcE
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Mushroom | $0.1$ | $0.073+$ | $0.067+$ | $\bm{0.058+}$ | $0.119+$ | $0.105+$ | $\bm{0.099+}$ | $0.059+$ | $0.051+$ | $\bm{0.040+}$ | $0.084+$ | $0.082+$ | $\bm{0.057+}$
$0.25$ | $0.060+$ | $0.023+$ | $\bm{0.005-}$ | $0.134+$ | $0.096+$ | $\bm{0.054+}$ | $0.054+$ | $0.034+$ | $\bm{0.010-}$ | $0.049+$ | $0.028+$ | $\bm{0.008+}$
$0.5$ | $0.032+$ | $0.087-$ | $\bm{0.018-}$ | $0.125+$ | $\bm{0.068+}$ | $0.076+$ | $\bm{0.073-}$ | $0.190-$ | $0.082-$ | $\bm{0.027+}$ | $0.057-$ | $0.052-$
$0.75$ | $\bm{0.023-}$ | $0.203-$ | $0.028-$ | $0.096+$ | $\bm{0.030+}$ | $0.066+$ | $\bm{0.100-}$ | $0.262-$ | $0.123-$ | $\bm{0.028-}$ | $0.096-$ | $0.058-$
| avg | $0.047+$ | $0.095-$ | $\bm{0.027+}$ | $0.119+$ | $0.075+$ | $\bm{0.074+}$ | $0.072-$ | $0.134-$ | $\bm{0.064-}$ | $0.047+$ | $0.066-$ | $\bm{0.044-}$
Landsat | $0.1$ | $0.066+$ | $0.053+$ | $\bm{0.034+}$ | $0.167+$ | $0.141+$ | $\bm{0.121+}$ | $0.066+$ | $0.049+$ | $\bm{0.028+}$ | $0.068+$ | $0.074+$ | $\bm{0.036+}$
$0.25$ | $0.052+$ | $0.011-$ | $\bm{0.007\cdot}$ | $0.159+$ | $0.115+$ | $\bm{0.085+}$ | $0.061+$ | $0.035+$ | $\bm{0.011+}$ | $0.034+$ | $0.020+$ | $\bm{0.011-}$
$0.5$ | $0.043+$ | $0.065-$ | $\bm{0.011-}$ | $0.137+$ | $0.103+$ | $\bm{0.089+}$ | $0.033+$ | $0.020+$ | $\bm{0.016-}$ | $0.040+$ | $\bm{0.029-}$ | $0.048-$
$0.75$ | $0.032+$ | $0.097-$ | $\bm{0.023-}$ | $0.103+$ | $\bm{0.071+}$ | $\bm{0.071+}$ | $0.023+$ | $0.027-$ | $\bm{0.017\cdot}$ | $\bm{0.041-}$ | $0.087-$ | $0.068-$
| avg | $0.048+$ | $0.057-$ | $\bm{0.019-}$ | $0.142+$ | $0.108+$ | $\bm{0.092+}$ | $0.046+$ | $0.033+$ | $\bm{0.018+}$ | $0.046+$ | $0.053-$ | $\bm{0.041-}$
Shuttle | $0.1$ | $0.056+$ | $0.048+$ | $\bm{0.015+}$ | $0.112+$ | $0.097+$ | $\bm{0.060+}$ | $0.049+$ | $0.035+$ | $\bm{0.016-}$ | $0.080+$ | $0.066+$ | $\bm{0.032+}$
$0.25$ | $0.044+$ | $0.018-$ | $\bm{0.007-}$ | $0.106+$ | $0.083+$ | $\bm{0.045+}$ | $0.029+$ | $0.020-$ | $\bm{0.018-}$ | $0.077+$ | $0.024+$ | $\bm{0.037+}$
$0.5$ | $0.026+$ | $0.162-$ | $\bm{0.008-}$ | $0.098+$ | $0.081+$ | $\bm{0.068+}$ | $\bm{0.016-}$ | $0.165-$ | $0.051-$ | $0.083+$ | $0.099-$ | $\bm{0.052+}$
$0.75$ | $\bm{0.012+}$ | $0.348-$ | $0.023-$ | $0.065+$ | $0.029+$ | $\bm{0.050+}$ | $\bm{0.072-}$ | $0.296-$ | $0.089-$ | $0.075+$ | $0.169-$ | $\bm{0.078+}$
| avg | $0.035+$ | $0.144-$ | $\bm{0.013-}$ | $0.095+$ | $0.073+$ | $\bm{0.056+}$ | $\bm{0.042+}$ | $0.129-$ | $0.044-$ | $0.079+$ | $0.089-$ | $\bm{0.050+}$
MNIST17 | $0.1$ | $0.077+$ | $0.078+$ | $\bm{0.055+}$ | $0.183+$ | $0.157+$ | $\bm{0.134+}$ | $0.060+$ | $0.052+$ | $\bm{0.046+}$ | $0.096+$ | $0.083+$ | $\bm{0.076+}$
$0.25$ | $0.063+$ | $0.052+$ | $\bm{0.005+}$ | $0.229+$ | $0.179+$ | $\bm{0.113+}$ | $0.060+$ | $0.027+$ | $\bm{0.009-}$ | $0.099+$ | $0.087+$ | $\bm{0.034+}$
$0.5$ | $0.035+$ | $0.042-$ | $\bm{0.014+}$ | $0.300+$ | $\bm{0.198+}$ | $0.208+$ | $0.022+$ | $0.024-$ | $\bm{0.011-}$ | $0.099+$ | $\bm{0.028+}$ | $0.053+$
$0.75$ | $\bm{0.014-}$ | $0.178-$ | $0.033-$ | $0.248+$ | $\bm{0.161+}$ | $0.200+$ | $\bm{0.008+}$ | $0.153-$ | $0.021-$ | $0.090+$ | $0.095-$ | $\bm{0.066+}$
| avg | $0.047+$ | $0.088-$ | $\bm{0.027+}$ | $0.240+$ | $0.173+$ | $\bm{0.164+}$ | $0.038+$ | $0.064-$ | $\bm{0.022+}$ | $0.096+$ | $0.073+$ | $\bm{0.057+}$
Overall | avg | $0.044+$ | $0.096-$ | $\bm{0.022-}$ | $0.149+$ | $0.107+$ | $\bm{0.097+}$ | $0.050+$ | $0.090-$ | $\bm{0.037-}$ | $0.067+$ | $0.070+$ | $\bm{0.048+}$

##  Appendix D When Irreducibility Holds

In theory, when irreducibility holds, baseline MPE methods shall be
asymptotically unbiased estimators of the mixture proportion $\kappa^{*}$,
regrouping may introduce negative bias, subsampling should not introduce bias.
Here we run some synthetically generated experiments (in a controlled setting)
to verify the theoretical claim.

We specify the distributions $H$, $G$ and $F$ as:

$\displaystyle H$ $\displaystyle\sim\mathcal{N}(\mu_{1}=0,\sigma_{1}=1)$
$\displaystyle G$ $\displaystyle\sim\mathcal{N}(\mu_{2}=2,\sigma_{2}=1)$
$\displaystyle F$ $\displaystyle=(1-\kappa^{*})G+\kappa^{*}H.$

where $G$ is irreducible w.r.t. $H$. We draw $m=500,n=1500$ instances from
both $H$ and $F$. The true mixture proportion $\kappa^{*}=\kappa(F|H)$ is
varied in $\left\\{0.1,0.25,0.5,0.75\right\\}$.

We draw $2000$ labeled instances from $F$. A $1$ hidden layer neural network
with $16$ neurons was trained to predict $P(Y=1|X=x)$. The acceptance function
$\alpha(x)$ used in Subsampling MPE is chosen to be

$\alpha(x)=\begin{cases}\widehat{P}(Y=1|X=x),&x\in A,\\\
1,&\text{o.w.},\end{cases}$

where $A=\\{x:\widehat{P}(Y=1|X=x)>0.6\\}$. As for ReMPE, $10\%$ of the sample
from $F$ is chosen to be regrouped to the sample from $H$, as suggested by Yao
et al. (2022). The above procedure was repeated $10$ times with different
random seeds. Results where shown in Table 6, where SuMPE never performs the
worst 999 In some cases, subsampling slightly increases the bias compared to
original version, this is partly due to $P(Y|X)$ being estimated.  and ReMPE
may introduce extremely high bias.

Table 6: Bias of the estimators on synthetic data. Several state-of-the-art
MPE algorithms DPL, EN, KM and TIcE are selected. For each of them, we compute
the bias ($\text{avg}[\widehat{\kappa}^{*}-\kappa^{*}]$) of the original,
regrouping and subsampling version. The biggest absolute bias among the
original, regrouping and subsampling versions is in bold.

$\kappa^{*}$ | DPL | ReDPL | SuDPL | EN | ReEN | SuEN | KM | ReKM | SuKM | TIcE | ReTIcE | SuTIcE
---|---|---|---|---|---|---|---|---|---|---|---|---
$0.1$ | $\bm{+0.029}$ | $+0.021$ | $+0.010$ | $\bm{+0.020}$ | $+0.005$ | $+0.008$ | $\bm{+0.020}$ | $+0.007$ | $+0.006$ | ${+0.085}$ | $\bm{+0.089}$ | ${+0.063}$
$0.25$ | $+0.012$ | $\bm{-0.062}$ | $-0.017$ | $-0.023$ | $\bm{-0.080}$ | $-0.043$ | $-0.016$ | $\bm{-0.074}$ | $-0.031$ | $\bm{+0.049}$ | $+0.010$ | $+0.024$
$0.5$ | $+0.038$ | $\bm{-0.128}$ | $-0.003$ | $-0.045$ | $\bm{-0.156}$ | ${-0.067}$ | $-0.001$ | $\bm{-0.133}$ | $-0.018$ | $\bm{+0.059}$ | $-0.048$ | $+0.032$
$0.75$ | $+0.012$ | $\bm{-0.282}$ | $-0.015$ | ${-0.071}$ | $\bm{-0.278}$ | ${-0.088}$ | $0.000$ | $\bm{-0.278}$ | $-0.012$ | ${+0.089}$ | $\bm{-0.199}$ | $+0.037$