# Sparse joint shift in multinomial classification

Dirk Tasche Independent researcher, e-mail<EMAIL_ADDRESS>
###### Abstract

Sparse joint shift (SJS) was recently proposed as a tractable model for
general dataset shift which may cause changes to the marginal distributions of
features and labels as well as the posterior probabilities and the class-
conditional feature distributions. Fitting SJS for a target dataset without
label observations may produce valid predictions of labels and estimates of
class prior probabilities. We present new results on the transmission of SJS
from sets of features to larger sets of features, a conditional correction
formula for the class posterior probabilities under the target distribution,
identifiability of SJS, and the relationship between SJS and covariate shift.
In addition, we point out inconsistencies in the algorithms which were
proposed for estimating the characteristics of SJS, as they could hamper the
search for optimal solutions.
Keywords: Sparse joint shift, dataset shift, distribution shift, prior
probability shift, label shift, covariate shift, posterior correction, class
prior estimation.

##  1 Introduction

The notion of _Sparse Joint Shift (SJS)_ was introduced by Chen et al. (2022)
as a tractable model of dataset shift “which considers the joint shift of both
labels and a few features”. In this paper, we re-analyse the notion in some
depth, looking closer at its connection to prior probability shift and the
link between SJS and covariate shift. For facilitating this intent, we take
recourse to some observations on general dataset shift by Tasche (2022b).

We revisit the notion of SJS in a probabilistic measure theory setting that
allows for the easy deployment of powerful mathematical tools like the tower
property of conditional expectation or Dynkin’s theorem which are less readily
available within the density-focussed approach used by Chen et al. (2022).
This paper can be read as a commentary on Chen et al. (2022) but also as a
self-contained presentation of SJS.

The main contributions with this paper to the subject are as follows:

  * •

We extend the definition of SJS such that it also covers (for instance)
distributional shift of $\|\mathbf{X}\|=\sqrt{\sum_{i=1}^{d}X_{i}^{2}}$ if
$\mathbf{X}=(X_{1},\dots,X_{d})$ is an $\mathbb{R}^{d}$-valued feature vector
(see Remark 3.6 below).

  * •

We show that SJS for a set of features $X_{i},i\in I,$ implies SJS for all
sets of features that include this set of features (Corollary 4.3 below).

  * •

We derive for SJS a conditional version of the posterior correction formula of
Saerens et al. (2001) and Elkan (2001), see Proposition 4.5 below.

  * •

In Theorem 4.7, we present a result on the identifiability of SJS that can be
interpreted as a generalisation of the confusion matrix approach to class
prior estimation under prior probability shift (Saerens et al., 2001).

  * •

We explore in depth the relationship between SJS and covariate shift (Theorem
4.16 below).

  * •

We comment on the approaches to the estimation of importance weights proposed
by Chen et al. (2022) and identify certain issues that might affect their
performance (Section 5 below).

In Section 2, an overview of related work on the subject is given. Section 3
sets the scene for the paper by specifying the model considered and
introducing the notion of sparse joint shift (SJS). Properties of SJS are
discussed in some detail in Section 4. In Section 5, two approaches by Chen et
al. (2022) to the estimation of densities under the assumption of SJS are
presented and commented on.

See Appendix A for a brief glossary of concepts and notation from
probabilistic measure theory (like indicator function $\mathbf{1}_{S}$,
$\sigma$-algebra, or conditional expectation) which are frequently used in the
following. Short proofs of results are integrated in the text, longer proofs
are presented in Appendix B. Appendix C provides the formulae relevant for
applications of SJS in the special case of all features being discrete.

##  2 Related work

In a wide sense, this paper is related to all work on dataset shift, transfer
learning, domain adaptation, and class prior estimation in multinomial
classification settings, including focussed literature on the binary case.

More specifically, there is closely related work on dataset shift models that
are based on invariance assumptions:

  * •

Covariate shift, including density ratio estimation (Shimodaira, 2000;
Sugiyama et al., 2012, and the references therein). For this type of shift,
the posterior class probabilities are assumed to be invariant between source
and target distribution.

  * •

Prior probability shift, also called label shift or target shift (Storkey,
2009; Azizzadenesheli, 2022, and the references therein). In this case, the
class-conditional feature distributions are assumed to be invariant between
source and target distribution.

  * •

Factorizable joint shift (He et al., 2021). According to the original
definition of He et al., at first glance, no invariance assumption is
involved. Tasche (2022b) showed that with this type of shift, the ratios of
the class-conditional feature densities remain invariant up to constant
factors between source and target distribution.

  * •

Covariate shift with posterior drift (Scott, 2019). This type of shift is
characterised by the weak invariance assumption that the posterior
probabilities of the source distribution are statistically sufficient for the
full feature vector also under the target distribution (Tasche, 2021).

Sparse joint shift (SJS) is also characterised by an invariance assumption:
According to Chen et al. (2022, Section 3), “Roughly speaking, SJS allows both
labels and a few features to shift, but assumes the remaining features’
conditional distribution to stay the same.”

An assumption of absolute continuity of the target distribution with respect
to the source distribution appears to be fundamental for the study of dataset
shift with invariance assumptions. Consequently, there is a clear demarcation
between the approach chosen in this paper and a large thread of literature
that begins with the seminal paper by Ben-David et al. (2006) and investigates
ways involving so-called representations (transformations of the features in
order to make their source and target domains similar) to get around the
absolute continuity assumption. See Johansson et al. (2019) for a discussion
of limitations to the representation-based approach to domain adaptation.

A third general approach to estimating dataset shift is based on mixture
models and solving transport problems, under the assumption that the shift is
enacted by moving as little as possible (probability) mass (Hofer, 2015). Such
an approach may also involve the construction of representations (Kirchmeyer
et al., 2021).

##  3 Setting

In this paper, we use the probabilistic setting of Tasche (2022b). See also
Tasche (2022a, Section 2.2) for a detailed reconciliation of mainstream
machine learning and probabilistic measure theory settings.

######  Assumption 3.1.

$(\Omega,\mathcal{M})$ is a measurable space. The _source distribution_ $P$
and the _target distribution_ $Q$ are probability measures on
$(\Omega,\mathcal{M})$. For some positive integer $\ell\geq 2$, events
$A_{1},\ldots,A_{\ell}\in\mathcal{M}$ and a sub-$\sigma$-algebra
$\mathcal{H}\subset\mathcal{M}$ are given. The events $A_{i}$,
$i=1,\ldots,\ell$, and $\mathcal{H}$ have the following properties:

  * (i)

$\bigcup_{i=1}^{\ell}A_{i}=\Omega$.

  * (ii)

$A_{i}\cap A_{j}=\emptyset$, $i,j=1,\ldots,\ell$, $i\neq j$.

  * (iii)

$0<P[A_{i}]$, $i=1,\ldots,\ell$.

  * (iv)

$0<Q[A_{i}]$, $i=1,\ldots,\ell$.

  * (v)

$A_{i}\notin\mathcal{H}$, $i=1,\ldots,\ell$.

$\mathcal{H}$ represents the features in a classification problem, typically
denoted $x$ or $\mathbf{x}$ in the machine learning literature. We suppose
that the set of features has been selected and fixed once for all such that in
the following $\mathcal{H}$ is also fixed unless stated otherwise. Think of
$\mathcal{H}$ as the data referred to by a ‘long list’ of explanatory
variables.

The events $A_{i}$ can be understood as markers or labels of classes
(typically denoted $y$ in machine learning) or layers with different feature
distributions. Statistical classification means predicting the classes $A_{i}$
based on possibly incomplete information as represented by $\mathcal{H}$.

Two measures $P$ and $Q$ are mentioned in Assumption 3.1 in order to reflect
dataset shift and the resulting tasks of transfer learning and domain
adaptation. These tasks have in common that they both require inference on the
full target (test) distribution $Q$ from partially known (by observations) $Q$
on $\mathcal{H}$ (the marginal distribution of the features) and completely
known source (training) distribution $P$.

Assumption 3.1, complemented by Assumption 3.7 below, can be reconciled with
the setting of Chen et al. (2022) in the following way:

  * •

$P$ is the source distribution (‘domain’) $\mathbb{P}_{s}$ and $Q$ is the
target distribution $\mathbb{P}_{t}$ of Chen et al. (2022).

  * •

Chen et al. assume that $\mathbb{P}_{s}$ and $\mathbb{P}_{t}$ have got
densities or mass functions $p_{s}=p_{s}(\mathbf{x},y)$ and
$p_{t}=p_{t}(\mathbf{x},y)$ with respect to an unspecified measure. In this
paper, we make consequent use of the source distribution $P$ as the common
reference measure such that only a density $\bar{h}$ of the target
distribution $Q$ with respect to the source distribution $P$ is needed for
expressing the relationship of $Q$ and $P$.

  * •

The density $\bar{h}$ is also studied by Chen et al.. They call it _weight
function_ and denote is by $w(\mathbf{x},y)$. In the literature, $\bar{h}$ is
also called _importance weight_ (see, e.g. Zhang et al., 2013, and the
references therein).

  * •

The aim of Chen et al. (2022) in their paper, is to estimate the weight
function $w(\mathbf{x},y)$ such that they obtain full knowledge of the target
distribution.

  * •

In this paper, we rather focus on determining the target posterior class
probabilities $Q[A_{i}\,|\,\mathcal{H}]$. When the target feature distribution
is known, its combination with the posterior probabilities (equivalently to
having recourse to the weight function) also provides full knowledge of the
joint distribution of features and class labels in the target domain. Then, in
particular, the class prior probabilities $Q[A_{i}]$ can be computed according
to the law of total probability as

$Q[A_{i}]\ =\ E_{Q}\bigl{[}Q[A_{i}\,|\,\mathcal{H}]\bigr{]},\qquad
i=1,\ldots,\ell,$

thus providing a solution to the class prior estimation problem (also called
‘quantification’) in the target domain.

The following two definitions introduce crucial notation for the subsequent
discussion of dataset shifts.

######  Definition 3.2.

We denote by $\mathcal{A}=\sigma(\\{A_{1},\ldots,A_{\ell}\\})$ the minimal
sub-$\sigma$-algebra of $\mathcal{M}$ containing all $A_{i}$,
$i=1,\ldots,\ell$.

Note that the $\sigma$-algebra $\mathcal{A}$ can be represented as

$\mathcal{A}\ =\ \bigl{\\{}\bigcup_{i=1}^{\ell}(A_{i}\cap
M_{i}):M_{1},\ldots,M_{\ell}\in\\{\emptyset,\Omega\\}\bigr{\\}},$ (3.1a) while
the minimal $\sigma$-algebra $\sigma(\mathcal{H}\cup\mathcal{A})$ that
contains both $\mathcal{H}$ and $\mathcal{A}$ can be written as
$\sigma(\mathcal{H}\cup\mathcal{A})\ =\
\bigl{\\{}\bigcup_{i=1}^{\ell}(A_{i}\cap
H_{i}):H_{1},\ldots,H_{\ell}\in\mathcal{H}\bigr{\\}}.$ (3.1b)

######  Definition 3.3.

Under Assumption 3.1, define the following class-conditional distributions, by
letting for $M\in\mathcal{M}$ and $i=1,\ldots,\ell$

$P_{i}[M]=P[M\,|\,A_{i}]=\frac{P[A_{i}\cap M]}{P[A_{i}]}\quad\text{and}\quad
Q_{i}[M]=Q[M\,|\,A_{i}]=\frac{Q[A_{i}\cap M]}{Q[A_{i}]}.$ (3.2)

In the literature, when restricted to the feature information set
$\mathcal{H}$, the $P_{i}$ and $Q_{i}$ sometimes are called _class-conditional
feature distributions_.

The situation where $P[M]\neq Q[M]$ holds for at least one
$M\in\sigma(\mathcal{H}\cup\mathcal{A})$ is called _dataset shift_ (Moreno-
Torres et al., 2012, Definition 1) and is also known as ‘distribution shift’
or ‘population drift’. Dataset shift is called “joint distribution shift” by
Chen et al. (2022) in the case where the joint distribution of features and
labels is shifted in contrast to shifts of one of the marginal distributions
of the labels or features only.

The following special type of dataset shift, ‘sparse joint shift’, was
introduced by Chen et al. (2022), in a slightly less general way.

######  Definition 3.4 (Sparse Joint Shift).

Under Assumption 3.1, assume that $\mathcal{F}$ is a sub-$\sigma$-algebra of
$\mathcal{H}$. Then the target distribution $Q$ is related to the source
distribution $P$ through $(\mathcal{F},\mathcal{H})$-_sparse joint shift_
(SJS) if for all $H\in\mathcal{H}$ and $i\in\\{1,\ldots,\ell\\}$ it holds that

$Q_{i}[H\,|\,\mathcal{F}]\ =\ P_{i}[H\,|\,\mathcal{F}].$ (3.3)

(3.3) is understood in the sense that for each $H\in\mathcal{H}$ and each
$i=1,\ldots,\ell$ there is an $\mathcal{F}$-measurable random variable $Z$
such that for all $F\in\mathcal{F}$ it holds that

$P_{i}[F\cap H]=E_{P_{i}}[\mathbf{1}_{F}\,Z]\qquad\text{and}\qquad Q_{i}[F\cap
H]=E_{Q_{i}}[\mathbf{1}_{F}\,Z].$

######  Remark 3.5.

_Observe that if $Q$ is related to the source distribution $P$ through
$(\mathcal{F},\mathcal{H})$-SJS then $Q$ also is related to the source
distribution $P$ through $(\mathcal{F},\mathcal{H}^{\prime})$-SJS for any
sub-$\sigma$-algebra $\mathcal{H}^{\prime}$ of $\mathcal{H}$ with
$\mathcal{H}^{\prime}\supset\mathcal{F}$. In the following, we use the short
hand $\mathcal{F}$-SJS for $(\mathcal{F},\mathcal{H})$-SJS whenever there is
no risk of ambiguity. ∎_

######  Remark 3.6.

_Definition 3.4 can be reconciled with the definition of sparse joint shift of
Chen et al. (2022, Definition 1) as follows:_

  * •

Consider a feature vector $\mathbf{X}=(X_{1},\dots,X_{d})$ mapping $\Omega$
into $\mathbb{R}^{d}$.

  * •

$\mathbf{X}$ corresponds to $\mathcal{H}$ in Assumption 3.1 if $\mathcal{H}$
is defined as the smallest $\sigma$-algebra such that $\mathbf{X}$ is
$\mathcal{H}$-measurable, i.e. $\mathcal{H}=\sigma(\mathbf{X})$.

  * •

If $I$ is a subset of $\\{1,\ldots,d\\}$ with at most $m$ elements, then
choosing $\mathcal{F}=\sigma(X_{i},\,i\in I)$ in Definition 3.4 replicates the
$m$-SJS definition of Chen et al. (2022) if Proposition 3.8 (iii) below is
taken into account with
$\mathcal{G}=\sigma(X_{i},\,i\in\\{1,\ldots,d\\}\setminus I)$. Chen et al.
describe the set $(X_{i},\,i\in I)$ as the set of _shifted features_.

_However, Definition 3.4 allows for shifts not only of distributions of
subsets of features like in the definition of $m$-SJS of Chen et al. (2022)
but also for distribution shifts of functions of the features. For instance,
in Definition 3.4, $\mathcal{F}$ may equal $\sigma(\|\mathbf{X}\|)$ where
$\|\cdot\|$ denotes the usual Euclidean norm
$\|\mathbf{X}\|=\sqrt{\sum_{i=1}^{d}X_{i}^{2}}$ of the feature vector. ∎_

Note that (3.3) is equivalent to
$Q\bigl{[}H\,|\,\sigma(\mathcal{F}\cup\mathcal{A})\bigr{]}\ =\
P\bigl{[}H\,|\,\sigma(\mathcal{F}\cup\mathcal{A})\bigr{]}$ (3.4a) since thanks
to the generalized Bayes formula (Klebaner, 2005, Theorem 10.8) we have
$\mu_{i}[H\,|\,\mathcal{F}]=\frac{\mu[H\cap
A_{i}\,|\,\mathcal{F}]}{\mu[A_{i}\,|\,\mathcal{F}]}$ and therefore
$\sum_{i=1}^{\ell}\mathbf{1}_{A_{i}}\,\mu_{i}[H\,|\,\mathcal{F}]\ =\
\mu\bigl{[}H\,|\,\sigma(\mathcal{F}\cup\mathcal{A})\bigr{]},$ (3.4b) where
$\mu$ is $P$ or $Q$.

Consider the following two special cases in Definition 3.4:

  * •

$\mathcal{F}=\mathcal{H}$. Then (3.3) is equivalent to
$\mathbf{1}_{H}=\mathbf{1}_{H}$ such that under Assumption 3.1 each target
distribution $Q$ is related to the source distribution $P$ through
$\mathcal{H}$-SJS. Hence, Definition 3.4 is not particularly meaningful in
this case but it does no harm to include it in the definition.

  * •

$\mathcal{F}=\\{\emptyset,\Omega\\}$. Then (3.3) is equivalent to

$Q_{i}[H]\ =\ P_{i}[H],\quad\text{for}\ i=1,\ldots,\ell\ \text{and}\
H\in\mathcal{H}.$

Hence $\\{\emptyset,\Omega\\}$-SJS is nothing else but prior probability shift
in the sense of Moreno-Torres et al. (2012, Definition 3).

If $Q$ and $P$ from Assumption 3.1 are mutually singular, i.e. there is an
event $\Omega^{\prime}\in\mathcal{M}$ such that $P[\Omega^{\prime}]=1$ and
$Q[\Omega^{\prime}]=0$, then (3.3) holds true for any
$\mathcal{F}\subset\mathcal{H}$ because conditional probabilities are uniquely
defined only up to events of probability $0$. Thus it makes sense to exclude
this case by an additional assumption of absolute continuity (as implicitly
also did Chen et al., 2022) which basically means that impossible events under
the source distribution are also impossible under the target distribution.
With this natural assumption, important properties of SJS can be proved. See
Appendix A for explanations of the notation involved.

######  Assumption 3.7.

Assumption 3.1 holds, and $Q$ is absolutely continuous with respect to $P$ on
$\sigma(\mathcal{H}\cup\mathcal{A})$, i.e.,

$Q|\sigma(\mathcal{H}\cup\mathcal{A})\ \ll\
P|\sigma(\mathcal{H}\cup\mathcal{A}),$

where $\mu|\sigma(\mathcal{H}\cup\mathcal{A})$ stands for the measure
$\mu\in\\{P,Q\\}$ with domain restricted to
$\sigma(\mathcal{H}\cup\mathcal{A})$.

Why requesting $Q\ll P$ instead of $P\ll\mu$ and $Q\ll\mu$ as is common in the
machine learning literature, for instance with $\mu=$ Lebesgue measure? Doing
so has a couple of advantages:

  * •

The notation is simplified.

  * •

$Q\ll P$ is implied by $P\ll\mu$ and $Q\ll\mu$ if
$\mu\left[\frac{dP}{d\mu}=0,\frac{dQ}{d\mu}>0\right]=0$. This is a natural
assumption, see the discussion in Tasche (2022b).

  * •

Special mathematical tools are available, e.g. the Radon-Nikodym theorem or
the conditional expectation operator for determining densities on
sub-$\sigma$-algebras.

In practical applications, under Assumption 3.7, the density
$\bar{h}=\frac{dQ}{dP}$ must be estimated as density ratio
$\frac{dQ}{d\mu}/\frac{dP}{d\mu}$. For literature on this, see Sugiyama et al.
(2012) and references therein.

The following proposition lists some useful elementary properties of SJS under
the absolute continuity assumption.

######  Proposition 3.8.

Under Assumption 3.7, suppose that $\mathcal{F}$ is a sub-$\sigma$-algebra of
$\mathcal{H}$. Then the following three statements are equivalent:

  * (i)

$Q$ is related to $P$ through $\mathcal{F}$-SJS in the sense of Definition
3.4.

  * (ii)

For each $\mathcal{H}$-measurable non-negative random variable $X$ it holds
that

$E_{Q_{i}}[X\,|\,\mathcal{F}]\ =\ E_{P_{i}}[X\,|\,\mathcal{F}],\qquad
i=1,\ldots,\ell.$ (3.5a)

  * (iii)

There is a sub-$\sigma$-algebra $\mathcal{G}$ of $\mathcal{H}$ such that
$\mathcal{H}=\sigma(\mathcal{F}\cup\mathcal{G})$ and

$Q_{i}[G\,|\,\mathcal{F}]\ =\ P_{i}[G\,|\,\mathcal{F}],\qquad\text{for all}\
G\in\mathcal{G}\ \text{and}\ i=1,\ldots,\ell.$ (3.5b)

See Appendix B for a proof of Proposition 3.8.

##  4 Analyses of sparse joint shift

In the following, we assume that the target distribution $Q$ is absolutely
continuous with respect to $P$. By allowing us to take recourse to results
from Tasche (2022b), this assumption facilitates thorough analyses of SJS.

###  4.1 Characterising SJS

By Lemma 1 of Tasche (2022b), under Assumption 3.7 the target conditional
feature distributions $Q_{i}|\mathcal{H}$, $i=1,\ldots,\ell$, are absolutely
continuous with respect to the source conditional feature distributions
$P_{i}|\mathcal{H}$, $i=1,\ldots,\ell$. For the respective densities, we write

$h_{i}\ =\ \frac{dQ_{i}|\mathcal{H}}{dP_{i}|\mathcal{H}},\qquad
i=1,\ldots,\ell.$ (4.1a)

By Theorem 1 of Tasche (2022b), under Assumption 3.7 the density $\bar{h}$ of
$Q$ with respect to $P$ on the sub-$\sigma$-algebra
$\sigma(\mathcal{H}\cup\mathcal{A})$ of $\mathcal{M}$ can be represented as

$\bar{h}\ =\
\sum_{i=1}^{\ell}h_{i}\,\frac{Q[A_{i}]}{P[A_{i}]}\,\mathbf{1}_{A_{i}}.$ (4.1b)

######  Theorem 4.1 (Equivalent conditions for SJS).

Under Assumption 3.7, let $\mathcal{F}$ be a sub-$\sigma$-algebra of
$\mathcal{H}$. Then the following three statements are equivalent:

  * (i)

The target distribution $Q$ is related to the source distribution $P$ through
$\mathcal{F}$-SJS.

  * (ii)

For each $i=1,\ldots,\ell$, there exists an $\mathcal{F}$-measurable density
$f_{i}$ of the target conditional feature distribution $Q_{i}$ with respect to
the source conditional feature distribution $P_{i}$ on $\mathcal{H}$.

  * (iii)

There exists a $\sigma(\mathcal{F}\cup\mathcal{A})$-measurable density
$\bar{f}$ of $Q$ with respect to $P$ on $\sigma(\mathcal{H}\cup\mathcal{A})$.

Moreover, if $Q$ is related to the source distribution $P$ through
$\mathcal{F}$-SJS then the density $\bar{f}$ mentioned in (iii) can be
represented as

$\bar{f}\ =\
\sum_{i=1}^{\ell}f_{i}\,\frac{Q[A_{i}]}{P[A_{i}]}\,\mathbf{1}_{A_{i}},$ (4.2)

with $f_{i}$, $i=1,\ldots,\ell$, as in (ii).

Theorem 4.1 is a rather straightforward consequence of the following
observation.

######  Lemma 4.2.

Let $Q$ and $P$ be probability measures on the measurable space
$(\Omega,\mathcal{M})$. Suppose that $Q$ is absolutely continuous with respect
to $P$ on $\mathcal{M}$ and that $\mathcal{G}$ is a sub-$\sigma$-algebra of
$\mathcal{M}$. Then the two following statements are equivalent:

  * (i)

For all $M\in\mathcal{M}$, it holds that
$P[M\,|\,\mathcal{G}]=Q[M\,|\,\mathcal{G}]$.

  * (ii)

There exists a $\mathcal{G}$-measurable density $g$ of $Q$ with respect to $P$
on $\mathcal{M}$.

If $\varphi$ is any $\mathcal{M}$-measurable density of $Q$ with respect to
$P$ on $\mathcal{M}$ and (i) or (ii) are true, then
$g=E_{P}[\varphi\,|\,\mathcal{G}]$ is a density of $Q$ with respect to $P$ on
$\mathcal{M}$.

###### Proof of Lemma 4.2.

Assume that $P[M\,|\,\mathcal{G}]=Q[M\,|\,\mathcal{G}]$ is true for all
$M\in\mathcal{M}$. Choose any density $\varphi$ of $Q$ with respect to $P$ on
$\mathcal{M}$ and define $g=E_{P}[\varphi\,|\,\mathcal{G}]$. For any
$M\in\mathcal{M}$ then we obtain

$Q[M]=E_{Q}\bigl{[}Q[M\,|\,\mathcal{G}]\bigr{]}=E_{P}\bigl{[}\varphi\,Q[M\,|\,\mathcal{G}]\bigr{]}=E_{P}\bigl{[}\varphi\,P[M\,|\,\mathcal{G}]\bigr{]}=E_{P}\bigl{[}g\,P[M\,|\,\mathcal{G}]\bigr{]}=E_{P}[g\,\mathbf{1}_{M}].$

This proves (i) $\Rightarrow$ (ii) and the statement on how to choose $g$.

Assume now that (ii) is true. Fix $M\in\mathcal{M}$. For any $G\in\mathcal{G}$
then we obtain

$E_{Q}\bigl{[}\mathbf{1}_{G}\,P[M\,|\,\mathcal{G}]\bigr{]}=E_{P}\bigl{[}g\,\mathbf{1}_{G}\,P[M\,|\,\mathcal{G}]\bigr{]}=E_{P}[g\,\mathbf{1}_{G\cap
M}]=Q[G\cap M].$

By the definition of conditional probability, this implies (ii) $\Rightarrow$
(i). ∎

###### Proof of Theorem 4.1.

Show (i) $\Rightarrow$ (ii): This follows by applying Lemma 4.2 to each of the
pairs $Q_{i}$ and $P_{i}$ from the definition of $\mathcal{F}$-SJS.

Show (ii) $\Rightarrow$ (iii): For each $i=1,\ldots,\ell$, choose an
$\mathcal{F}$-measurable density $f_{i}$ of $Q_{i}$ with respect to $P_{i}$ on
$\mathcal{H}$. Then, by representation (4.1b), $\bar{f}$ defined by (4.2) is a
$\sigma(\mathcal{F}\cup\mathcal{A})$-measurable density of $Q$ with respect to
$P$ on $\sigma(\mathcal{H}\cup\mathcal{A})$.

Show (iii) $\Rightarrow$ (i): Follows from the equivalence of (3.3) for all
$i=1,\ldots,\ell$ and (3.4a), combined with Lemma 4.2. ∎

Note that SJS does not imply in general that there exists an
$\mathcal{F}$-measurable density $f$ of $Q$ with respect to $P$ on
$\mathcal{H}$. We show in Section 4.3 below that subject to a mild condition
the existence of such a density $f$ is implied by the joint presence of SJS
and covariate shift. Moreover, if SJS holds and there is an
$\mathcal{F}$-measurable density $f$ of $Q$ with respect to $P$ on
$\mathcal{H}$ then $Q$ and $P$ are also related through covariate shift, again
under a mild condition.

As formally stated in the following corollary, Theorem 4.1 implies that SJS is
a nested property in the sense that SJS for a set of features implies SJS for
all sets of features that include the first set. Choose
$\mathcal{F}=\sigma(X_{i},\,i\in I)$ and
$\mathcal{F}^{\prime}=\sigma(X_{i},\,i\in I^{\prime})$ for features $X_{i}$
and index sets $I\subset I^{\prime}$ to see this. In particular, prior
probability shift implies SJS for any set of features.

######  Corollary 4.3.

Under Assumption 3.7, suppose that $\mathcal{F}$ is a sub-$\sigma$-algebra of
$\mathcal{H}$. If $Q$ is related to $P$ through $\mathcal{F}$-SJS and
$\mathcal{F}^{\prime}\supset\mathcal{F}$ is another sub-$\sigma$-algebra of
$\mathcal{H}$ then $Q$ also is related to $P$ through
$\mathcal{F}^{\prime}$-SJS.

###### Proof of Corollary 4.3.

By Theorem 4.1 (ii), for each $i=1,\ldots,\ell$, there exists an
$\mathcal{F}$-measurable density $f_{i}$ of $Q_{i}$ with respect to $P_{i}$ on
$\mathcal{H}$. For $\mathcal{F}^{\prime}\supset\mathcal{F}$, each $f_{i}$ is
$\mathcal{F}^{\prime}$-measurable, too. Hence, by the implication ‘(ii)
$\Rightarrow$ (i)’ of Theorem 4.1, $Q$ is related to $P$ through
$\mathcal{F}^{\prime}$-SJS. ∎

######  Remark 4.4.

_Consider the setting of the paper of Chen et al. (2022) as summarised in
Remark 3.6 above. If $\mathcal{F}=\sigma(X_{i},i\in I)$ for some
$I\subsetneq\\{1,\ldots,d\\}$, then there is some $j\in\\{1,\ldots,d\\}$ such
$I\subset J=\\{1,\ldots,d\\}\setminus\\{j\\}$. It follows that_

$\mathcal{F}^{\prime}\ =\ \sigma(X_{i},i\in J)\ \supset\ \mathcal{F}.$ (4.3)

_By Corollary 4.3, therefore for fitting any $m$-SJS with $m<d$ in the sense
of Chen et al. (2022), it suffices to consider index sets with $d-1$ elements,
i.e. $(d-1)$-SJS. ∎_

The following Eq. (4.4b) could be called _conditional posterior correction
formula_. On the one hand, it generalises the scope of the correction formula
presented by Saerens et al. (2001, Eq. (2.4)) and Elkan (2001, Theorem 2) from
prior probability shift to SJS. On the other hand, it represents a special
case of the correction formula proven in Tasche (2022b, Corollary 2).

######  Proposition 4.5.

Under Assumption 3.7, let $Q$ be related to $P$ through $\mathcal{F}$-SJS.
Then it $Q$-almost surely holds that

$\displaystyle 0$ $\displaystyle\ <\
\sum_{j=1}^{\ell}\frac{Q[A_{j}\,|\,\mathcal{F}]}{P[A_{j}\,|\,\mathcal{F}]}P[A_{j}\,|\,\mathcal{H}],\quad\text{and}$
(4.4a) $\displaystyle Q[A_{i}\,|\,\mathcal{H}]$ $\displaystyle\ =\
\frac{\frac{Q[A_{i}\,|\,\mathcal{F}]}{P[A_{i}\,|\,\mathcal{F}]}P[A_{i}\,|\,\mathcal{H}]}{\sum_{j=1}^{\ell}\frac{Q[A_{j}\,|\,\mathcal{F}]}{P[A_{j}\,|\,\mathcal{F}]}P[A_{j}\,|\,\mathcal{H}]},\quad
i=1\,\ldots,\ell.$ (4.4b)

In particular, the right-hand side of (4.4b) is $Q$-almost surely well-defined
under the convention that $0/0=0$.

See Appendix B for a proof of Proposition 4.5.

###  4.2 Identifiability in the presence of sparse joint shift

Identifiability of the target distribution $Q$ under SJS is described by Chen
et al. (2022, Section 3.1) as follows: “If a joint feature and label
distribution matches the target feature distribution and satisfies the $m$-SJS
requirement together with the source distribution, it has to be the target
distribution.” Chen et al. (2022, Tehorem 1) present a sufficient condition
for identifiability phrased in terms of linear independence of components of
the density of the joint source distribution. An alternative to their result
is provided below in Theorem 4.7. It is based on the following observation.

######  Lemma 4.6.

Let $(\Omega,\mathcal{M},\mu)$ a probability space, $\mathcal{G}$ a
sub-$\sigma$-algebra of $\mathcal{M}$, and
$A_{1},\ldots,A_{\ell}\in\mathcal{M}$ a decomposition of $\Omega$, i.e.
properties (i) and (ii) of Assumption 3.1 hold. In addition, assume that
$\mu(A_{i})>0$ for all $i=1,\ldots,\ell$, and define

$\mu_{i}(M)\ =\ \frac{\mu(M\cap A_{i})}{\mu(A_{i})},\qquad
M\in\mathcal{M},i=1,\ldots,\ell.$

Let $X_{1},\ldots,X_{n}$ be $\mathcal{M}$-measurable non-negative random
variables and define the random matrix $R=(R_{ij})_{1\leq i\leq n,1\leq
j\leq\ell}=R(\mu,\mathcal{G},n)$ by

$R_{ij}\ =\ E_{\mu_{j}}[X_{i}\,|\,\mathcal{G}].$ (4.5a) Then it follows that
$\begin{pmatrix}E_{\mu}[X_{1}\,|\,\mathcal{G}]\\\ \vdots\\\
E_{\mu}[X_{n}\,|\,\mathcal{G}]\end{pmatrix}\ =\
R\times\begin{pmatrix}\mu[A_{1}\,|\,\mathcal{G}]\\\ \vdots\\\
\mu[A_{\ell}\,|\,\mathcal{G}]\end{pmatrix}.$ (4.5b)

See Appendix B for a proof of Lemma 4.6. On the one hand, the following
Theorem 4.7 provides a sufficient condition for identifiability under SJS. On
the other hand, on the basis of Eq. (B.3) from its proof, it can be
interpreted as a conditional version of the ‘confusion matrix’ method (Saerens
et al., 2001, Section 2.3.1; also called ‘Adjusted Count’, Forman, 2008) for
estimating the class prior probabilities under prior probability shift.

######  Theorem 4.7 (Identifiability).

Under Assumption 3.1, let $\mathcal{F}$ and $\mathcal{F}^{\prime}$ be
sub-$\sigma$-algebras of $\mathcal{H}$ and $Q$ and $Q^{\prime}$ be probability
measures on $(\Omega,\sigma(\mathcal{H}\cup\mathcal{A}))$ such that
$Q|\mathcal{H}=Q^{\prime}|\mathcal{H}$ and both $Q$ and $Q^{\prime}$ are
absolutely continuous with respect to $P$ on
$\sigma(\mathcal{H}\cup\mathcal{A})$. Suppose that $Q$ is related to $P$
through $\mathcal{F}$-SJS and $Q^{\prime}$ is related to $P$ through
$\mathcal{F}^{\prime}$-SJS. Assume that $X_{1},\ldots,X_{\ell}$ are
$\mathcal{H}$-measurable non-negative random variables and define the random
matrix $R=R(P,\sigma(\mathcal{F}\cup\mathcal{F}^{\prime}),\ell)$ by (4.5a),
i.e. with $\mu=P$, $\mathcal{G}=\sigma(\mathcal{F}\cup\mathcal{F}^{\prime})$
and $n=\ell$. If the matrix $R$ satisfies the condition

$P[\mathrm{rank}(R)=\ell]\ =\ 1,$ (4.6)

then $Q[M]=Q^{\prime}[M]$ follows for all
$M\in\sigma(\mathcal{H}\cup\mathcal{A})$.

See Appendix B for a proof of Theorem 4.7. The sufficient condition for
identifiability presented by Chen et al. (2022, Theorem 1) implicitly involves
picking a set of $\ell$ feature values in order to obtain a system of $\ell$
equations for $\ell$ unknowns with a unique solution, for each point in the
domain of the weight function linking source and target distributions. In
Theorem 4.7, a corresponding but more transparent selection of random
variables $X_{i}$ is introduced, and ‘good’ choices like an accurate
classifier or posterior probabilities suggest themselves.

How strong is Theorem 4.7? Obviously, its strength depends on the answer to
the question whether we can find $\mathcal{H}$-measurable non-negative random
variables $X_{1},\ldots,X_{\ell}$ such that (4.6) holds, and if so, how easy
it is.

Denote by $\mathbf{C}=(C_{1},\ldots,C_{\ell})$ hard (or crisp) multinomial
classifiers in the sense that

$\begin{split}&C_{i}\in\mathcal{H}\ \text{for all}\ i=1,\ldots,\ell,\\\
&C_{1},\ldots,C_{\ell}\ \text{is a disjoint decomposition of}\ \Omega,\
\text{and}\\\ &A_{i}\ \text{is predicted when}\ C_{i}\ \text{is
observed.}\end{split}$ (4.7)

Intuitively, $X_{i}=\mathbf{1}_{C_{i}}$ for some accurate classifier
$\mathbf{C}$ might be a good choice for Theorem 4.7. Then
$\mathbf{1}_{C_{i}}\approx\mathbf{1}_{A_{i}}$, $i=1,\ldots,\ell$, should hold
with the consequence that also

$P_{j}[C_{i}\,|\,\mathcal{G}]\ \approx\ \begin{cases}1,&\text{for}\ i=j,\\\
0,&\text{for}\ i\neq j,\end{cases}$

with the consequence that the matrix $R$ would be likely to have maximal rank.

A similar choice is $X_{i}=P[A_{i}\,|\,\mathcal{H}]$, $i=1,\ldots,\ell$. With
this choice, we can show that in the binary case $\ell=2$, condition (4.6) has
an intuitive interpretation.

######  Lemma 4.8.

In the setting of Theorem 4.7, consider the case $\ell=2$ and let

$X_{1}\ =P[A_{1}\,|\,\mathcal{H}]\quad\text{and}\quad X_{2}\
=P[A_{2}\,|\,\mathcal{H}].$ (4.8a)

Then condition (4.6) is satisfied if and only

$P\Big{[}P[A_{1}\,|\,\mathcal{H}]=P\bigl{[}A_{1}\,|\,\sigma(\mathcal{F}\cup\mathcal{F}^{\prime})\bigr{]}\Big{]}\
<\ 1.$ (4.8b)

See Appendix B for a proof of Lemma 4.8. Condition (4.8b), in particular,
implies in the context of Lemma 4.8 and Theorem 4.7 that the $\sigma$-algebra
(or information set) $\sigma(\mathcal{F}\cup\mathcal{F}^{\prime})$ must not be
sufficient for $\mathcal{H}$ in the sense of Tasche (2021, Definition 3.1).
The definition of sufficiency is formally given below as we are having a
closer look at the relationship between sufficiency and SJS in the remainder
of this section. Recall that by assumption $\mathcal{H}$ reflects the totality
of observable information on the features available for the prediction of the
labels. In non-technical terms, hence sufficiency means that all the
information needed for predicting the class labels is already captured with an
information set smaller than $\mathcal{H}$.

######  Definition 4.9 (Statistical sufficiency).

Let $(\Omega,\mathcal{M},P)$ be a probability space and $\mathcal{A}$,
$\mathcal{F}$ and $\mathcal{H}$ be sub-$\sigma$-fields of $\mathcal{M}$ such
that $\mathcal{F}\subset\mathcal{H}$. Then $\mathcal{F}$ is _sufficient_ for
$\mathcal{H}$ with respect to $\mathcal{A}$ if for all $A\in\mathcal{A}$

$P[A\,|\,\mathcal{H}]\ =\ P[A\,|\,\mathcal{F}].$ (4.9)

Sufficiency is of interest and desirable for dimension reduction primarily in
the case where (in the context of Lemma 4.8)

$\sigma(\mathcal{F}\cup\mathcal{F}^{\prime})\ \subsetneq\ \mathcal{H}.$ (4.10)

Observe, however, that requiring (4.10) for Lemma 4.8 instead of (4.8b) would
not work because (4.8b) may be violated despite (4.10) being true.

A variation on the theme of Lemma 4.8 for general $\ell\geq 2$ immediately
follows from Proposition 3.7 of Tasche (2021). It confirms in the general case
that sufficiency does not help to achieve identifiability under SJS. Recall
from (3.4b) that

$\sum_{i=1}^{\ell}\mathbf{1}_{A_{i}}\,P_{i}[H\,|\,\mathcal{F}]\ =\
P\bigl{[}H\,|\,\sigma\bigl{(}\mathcal{F}\cup\mathcal{A}\bigr{)}\bigr{]},\qquad\text{for
all}\ H\in\mathcal{H}.$

######  Proposition 4.10.

Let $(\Omega,\mathcal{M},P)$ be a probability space. Let
$A_{1},\ldots,A_{\ell}\in\mathcal{M}$ be a decomposition of $\Omega$ such that
properties (i), (ii) and (iii) of Assumption 3.1 hold. Suppose that
$\mathcal{F}$ and $\mathcal{H}$ are sub-$\sigma$-algebras of $\mathcal{M}$,
with $\mathcal{F}\subset\mathcal{H}$. Then the following three statements are
equivalent:

  * (i)

For $i=1,\ldots,\ell$, it holds that
$P[A_{i}\,|\,\mathcal{H}]=P[A_{i}\,|\,\mathcal{F}]$, i.e. $\mathcal{F}$ is
sufficient for $\mathcal{H}$ with respect to
$\mathcal{A}=\sigma(A_{i}:i=1,\ldots,\ell)$ in the sense of Definition 4.9.

  * (ii)

For all $H\in\mathcal{H}$, it holds that
$P\bigl{[}H\,|\,\sigma\bigl{(}\mathcal{F}\cup\mathcal{A}\bigr{)}\bigr{]}=P[H\,|\,\mathcal{F}]$.

  * (iii)

With $P_{i}$ defined as in (3.2), it holds that
$E_{P_{i}}[X\,|\,\mathcal{F}]=E_{P}[X\,|\,\mathcal{F}]$ for all
$\mathcal{H}$-measurable non-negative random variables $X$ and all
$i=1,\ldots,\ell$.

By Proposition 4.10, if in the setting of Theorem 4.7 the sub-$\sigma$-algebra
$\mathcal{G}=\sigma(\mathcal{F}\cup\mathcal{F}^{\prime})$ is sufficient for
$\mathcal{H}$, the rank of the random matrix $R$ is at most $1$ with
probability $1$. Hence, the $\ell\times\ell$-matrix $R$ is not invertible such
that Theorem 4.7 cannot be applied for proving uniqueness of $Q$ related to
$P$ through $\mathcal{F}$-SJS. Intuitively, this is not a surprise as
Proposition 4.10 (iii) may be interpreted as ‘$\mathcal{H}$ does not provide
any information about $A_{i}$ that could not be obtained through a sufficient
$\mathcal{F}$’.

However, the situation is not as bad as it might appear because of this
observation. For Proposition 4.12 below shows that under SJS, sufficiency is
passed on from the source distribution to the target distribution. Before
looking at that, another useful invariance property is introduced in the
following definition.

######  Definition 4.11 (Conditional distribution invariance).

Let $P$ and $Q$ be probability measures on a measurable space
$(\Omega,\mathcal{M})$. Suppose that $\mathcal{F}$ is a sub-$\sigma$-algebra
of $\mathcal{M}$. Then $\mathcal{M}$ is $\mathcal{F}$-_conditionally invariant
between_ $P$ and $Q$ if

$P[M\,|\,\mathcal{F}]\ =\ Q[M\,|\,\mathcal{F}],\qquad\text{for all}\
M\in\mathcal{M}.$ (4.11)

######  Proposition 4.12.

Under Assumption 3.7, let $\mathcal{F}$ be a sub-$\sigma$-algebra of
$\mathcal{H}$. Suppose that $\mathcal{F}$ is sufficient for $\mathcal{H}$ with
respect to $\mathcal{A}$ under $P$ in the sense of Definition 4.9 and that $Q$
is related to $P$ through $\mathcal{F}$-SJS. Then $\mathcal{H}$ is
$\mathcal{F}$-conditionally invariant between $P$ and $Q$ in the sense of
Definition 4.11, and $\mathcal{F}$ is also sufficient for $\mathcal{H}$ with
respect to $\mathcal{A}$ under $Q$.

###### Proof of Proposition 4.12.

Proposition 4.10 (iii) and $\mathcal{F}$-SJS together imply
$Q_{i}[H\,|\,\mathcal{F}]=P[H\,|\,\mathcal{F}]$ for $H\in\mathcal{H}$ and
$i=1,\ldots,\ell$. Therefore we obtain for all $H\in\mathcal{H}$

$Q\bigl{[}H\,|\,\sigma(\mathcal{F}\cup\mathcal{A})\bigr{]}\ =\
\sum\nolimits_{i=1}^{\ell}\mathbf{1}_{A_{i}}\,Q_{i}[H\,|\,\mathcal{F}]\ =\
P[H\,|\,\mathcal{F}].$

From this, it follows that

$Q[H\,|\,\mathcal{F}]=E_{Q}\bigl{[}Q[H\,|\,\sigma(\mathcal{F}\cup\mathcal{A})\,\big{|}\,\mathcal{F}]\bigr{]}=E_{Q}\bigl{[}P[H\,|\,\mathcal{F}]\,\big{|}\,\mathcal{F}\bigr{]}=P[H\,|\,\mathcal{F}].$

Hence, (4.11) is true. Sufficiency under $Q$ follows from Proposition 4.10
‘(ii) $\Rightarrow$ (i)’. ∎

Property (4.11), under Assumption 3.7, is observable and verifiable, for
instance by examining if there is an $\mathcal{F}$-measurable density of $Q$
with respect to $P$ on $\mathcal{H}$ (as a consequence of Lemma 4.2). Hence by
Proposition 4.12, the presence of conditional distribution invariance could
suggest that $Q$ and $P$ are also related through $\mathcal{F}$-SJS. Alas, one
has to be very careful about this because Example 4.17 below shows that
conditional distribution invariance does not imply SJS in general.

###  4.3 SJS vs. covariate shift

In this section, we show that the relationship between SJS and covariate shift
is intertwined with the question of whether or not the target marginal
distribution of the features $Q|\mathcal{H}$ has got an
$\mathcal{F}$-measurable density with respect to the source unconditional
feature distribution $P|\mathcal{H}$.

######  Definition 4.13 (Covariate shift).

Under Assumption 3.1, let $\mathcal{F}$ be a sub-$\sigma$-algebra of
$\mathcal{H}$. Then the source distribution $P$ and the target distribution
$Q$ are related through $\mathcal{F}$-_covariate shift_ if it holds that

$Q[A_{i}\,|\,\mathcal{F}]\ =\ P[A_{i}\,|\,\mathcal{F}],\qquad\text{for all}\
i=1,\ldots,\ell.$ (4.12)

The most relevant case in Definition 4.13 is incurred with
$\mathcal{F}=\mathcal{H}$. However, as we will see below, in the context of
SJS also the case of $\mathcal{F}$-covariate shift with a proper
sub-$\sigma$-algebra $\mathcal{F}$ of $\mathcal{H}$ is of interest.

Chen et al. (2022, Theorem 2) showed by example that in general SJS does
neither imply prior probability shift nor covariate shift. In the following
example – which is a slight modification of the example of Chen et al. – we
show that SJS and covariate shift can be present at the same time in proper
distribution shift, i.e. in shift where source and target distribution truly
differ. Moreover, in Example 4.15 below we point out that covariate shift does
not imply SJS. These three observations together motivate the results
presented in this section, regarding the triangle-relationship of covariate
shift, SJS and conditional distribution invariance as introduced in Definition
4.11.

######  Example 4.14 (Covariate shift and SJS are not mutually exclusive).

_We consider $\\{0,1\\}$-valued variables $Y$, $X_{1}$ and $X_{2}$ under
different source and target distributions $P$ and $Q$ respectively:_

  * •

$P[Y=1]=1/2=P[Y=0]$, $Q[Y=1]=0.6=1-Q[Y=0]$.

  * •

$X_{1}$ and $X_{2}$ are independent conditional on $Y$, both under $P$ and
$Q$.

  * •

The distributions of $X_{1}$ conditional on $Y$ are specified by

$\displaystyle P[X_{1}=1\,|\,Y=1]=0.6,\ P[X_{1}=1\,|\,Y=0]=0.4$
$\displaystyle\text{and}\ Q[X_{1}=1\,|\,Y=1]=1/2,\ P[X_{1}=1\,|\,Y=0]=1/2.$

The example differs only in the conditional distributions of $X_{1}$ under $P$
from the example presented by Chen et al. (2022, Theorem 2).

  * •

The distributions of $X_{2}$ conditional on $Y$ are specified by

$\displaystyle P[X_{2}=1\,|\,Y=1]=0.2,\ P[X_{2}=1\,|\,Y=0]=0.6$
$\displaystyle\text{and}\ Q[X_{2}=1\,|\,Y=1]=0.2,\ Q[X_{2}=1\,|\,Y=0]=0.6.$

_To reconcile these choices with the setting of this paper as specified by
Assumption 3.1, we define $A_{1}=\\{Y=1\\}$, $A_{2}=\\{Y=0\\}$,
$\mathcal{H}=\sigma(X_{1},X_{2})$ and $\mathcal{F}=\sigma(X_{1})$. Then it
follows that_

  * •

$Q$ is related to $P$ through $\mathcal{F}$-SJS but not through
$\\{\emptyset,\Omega\\}$-SJS (i.e. prior probability shift), and

  * •

$Q[A_{1}\,|\,\mathcal{F}]=P[A_{1}\,|\,\mathcal{F}]$ (i.e.
$\mathcal{F}$-covariate shift) because

$\displaystyle P[A_{1}\,|\,\mathcal{F}]$
$\displaystyle=P[Y=1\,|\,X_{1}=1]\,\mathbf{1}_{\\{X_{1}=1\\}}+P[Y=1\,|\,X_{1}=0]\,\mathbf{1}_{\\{X_{1}=0\\}}$
$\displaystyle=\frac{P[Y=1]\,P[X_{1}=1\,|\,Y=1]\,\mathbf{1}_{\\{X_{1}=1\\}}}{P[Y=1]\,P[X_{1}=1\,|\,Y=1]+P[Y=0]\,P[X_{1}=1\,|\,Y=0]}$
$\displaystyle\qquad+\
\frac{P[Y=1]\,P[X_{1}=0\,|\,Y=1]\,\mathbf{1}_{\\{X_{1}=0\\}}}{P[Y=1]\,P[X_{1}=0\,|\,Y=1]+P[Y=0]\,P[X_{1}=0\,|\,Y=0]}$
$\displaystyle=0.6\,\mathbf{1}_{\\{X_{1}=1\\}}+0.4\,\mathbf{1}_{\\{X_{1}=0\\}}$
$\displaystyle=Q[Y=1\,|\,X_{1}=1]\,\mathbf{1}_{\\{X_{1}=1\\}}+Q[Y=1\,|\,X_{1}=0]\,\mathbf{1}_{\\{X_{1}=0\\}}$
$\displaystyle=Q[A_{1}\,|\,\mathcal{F}].$

_Proposition 4.5 now implies that
$Q[A_{1}\,|\,\mathcal{H}]=P[A_{1}\,|\,\mathcal{H}]$, i.e. $Q$ and $P$ are
related through (full) $\mathcal{H}$-covariate shift. ∎_

######  Example 4.15 (Covariate shift does not imply SJS).

_Under Assumption 3.7, let $\ell=2$ and $\mathcal{F}$ be a
sub-$\sigma$-algebra of $\mathcal{H}$. Suppose that
$0<P[A_{1}\,|\,\mathcal{H}]<1$ $P$-almost surely and that $\mathcal{F}$ is not
sufficient for $\mathcal{H}$ with respect to $\mathcal{A}$ under $P$, i.e. we
have_

$1\ >\ P\big{[}P[A_{1}\,|\,\mathcal{F}]=P[A_{1}\,|\,\mathcal{H}]\bigr{]}.$

_By Theorem 1 of Tasche (2022a) then there exists a probability measure
$Q^{\ast}$ on $\bigl{(}\Omega,\sigma(\mathcal{H}\cup\mathcal{A})\bigr{)}$ with
$Q^{\ast}\ll P$ such that $Q^{\ast}$ and $P$ are related through
$\mathcal{H}$-covariate shift but not through $\mathcal{F}$-covariate shift.
However, if $Q^{\ast}$ and $P$ were related through $\mathcal{F}$-SJS, then
Lemma B.1 from Appendix B would imply that after all $Q^{\ast}$ and $P$ are
related through $\mathcal{F}$-covariate shift. But they are not as we have
seen.
Conclusion: For any sub-$\sigma$-algebra $\mathcal{F}\subset\mathcal{H}$ which
is not sufficient for $\mathcal{H}$, there is a $Q^{\ast}$ such that
$Q^{\ast}$ and $P$ are related through $\mathcal{H}$-covariate shift but not
through $\mathcal{F}$-SJS._ ∎

For the interpretation of the following theorem, recall that by Lemma 4.2,
conditional distribution invariance as introduced in Definition 4.11 is
equivalent to the property that the target unconditional feature distribution
$Q|\mathcal{H}$ has got an $\mathcal{F}$-measurable density with respect to
the source unconditional feature distribution $P|\mathcal{H}$.

######  Theorem 4.16.

Under Assumption 3.7, let $\mathcal{F}$ be a sub-$\sigma$-algebra of
$\mathcal{H}$. Consider then the following three properties:

  * (SJS)

$Q$ is related to $P$ through $\mathcal{F}$-SJS.

  * (CDI)

$Q$ and $P$ are related through $\mathcal{F}$-conditional distribution
invariance, i.e. Eq. (4.11) holds true with $M=H$.

  * (CSH)

$Q$ and $P$ are related through $\mathcal{H}$-covariate shift in the sense of
Definition 4.13.

The following statements relating to these properties hold true:

  * (i)

Suppose that $X_{1},\ldots,X_{\ell}$ are $\mathcal{H}$-measurable non-negative
random variables and define the random matrix $R=R(P,\mathcal{F},\ell)$ by
(4.5a), i.e. with $\mu=P$, $\mathcal{G}=\mathcal{F}$ and $n=\ell$. If the
matrix $R$ has full rank, i.e. it satisfies condition (4.6), then (CSH)
follows if (SJS) and (CDI) are both true.

  * (ii)

(SJS) follows if (CDI) and (CSH) are both true.

  * (iii)

Suppose that the following condition is true:

$P\bigl{[}P[A_{i}\,|\,\mathcal{H}]>0\bigr{]}\ =\ 1,\qquad\text{for all}\
i=1,\ldots,\ell.$ (4.13a)

Then (CDI) follows if (SJS) and (CSH) are both true.

See Appendix B for a proof of Theorem 4.16. As a first consequence of Theorem
4.16, we find that the property ‘conditional distribution invariance’ does not
imply either covariate shift or SJS, as demonstrated in the following example.

######  Example 4.17.

_With $P$, $\mathcal{F}$ and $\ell=2$ as in Assumption 3.1, define the
probability measure $Q$ on $\mathcal{H}$ by taking recourse to Lemma 4.2, with
some $\mathcal{F}$-measurable density
$f=\frac{dQ|\mathcal{H}}{dP|\mathcal{H}}$. Then extend $Q$ to
$\sigma(\mathcal{H}\cup\mathcal{A})$ by letting
$Q[A_{1}\,|\,\mathcal{H}]=\bigl{(}P[A_{1}\,|\,\mathcal{H}]\bigr{)}^{2}$.
By construction, then $Q$ and $P$ are $\mathcal{F}$-conditionally distribution
invariant but not related to each other through $\mathcal{H}$-covariate shift.
Therefore, thanks to Lemma 4.8 and Theorem 4.16 (i), $Q$ and $P$ cannot be
related through $\mathcal{F}$-SJS either if $\mathcal{F}$ is not sufficient
for $\mathcal{H}$ with respect to $\mathcal{A}$._ ∎

What about the practical relevance of Theorem 4.16? Condition (CDI) might be
most interesting. As mentioned before, (CDI) is an observable property, in the
sense that it depends on the feature marginal distributions $Q|\mathcal{H}$
and $P|\mathcal{H}$ only which both are assumed to be observed. Hence if (CDI)
is found to occur then by Theorem 4.16 (i) and (ii), SJS and covariate shift
are not mutually exclusive alternatives but either they both hold or neither
of the two does hold. Thus if it can be assumed for whatever reasons that
source and target are related through SJS or covariate shift, covariate shift
might be preferred because it is easier to handle.

Chen et al. (2022, Definition 3) defined _$m$ -sparse covariate shift_ by
(B.8) in Appendix B (see Remark 3.6 for reconciliation of the ‘$m$’-notation
of Chen et al. (2022) with the ‘$\mathcal{F}$’-notation of this paper). In
their Theorem 2, Chen et al. (2022) correctly claimed that (B.8) implies
$\mathcal{F}$-SJS. In the proof of Theorem 2, however, Chen et al. only showed
that (4.12) and (4.11) with $M=H$ together imply (B.8). But all taken together
Theorem 4.16 (ii) was proved by them.

##  5 How to estimate sparse joint shift?

Chen et al. (2022) proposed two estimation approaches for the weight function
that corresponds to the density $\bar{h}=\frac{dQ}{dP}$ in the setting of this
paper. In the following, we begin with discussing their estimation strategy in
general in Section 5.1. Then we continue with descriptions of their approach
SEES-c in Section 5.2 and of their approach SEES-d in Section 5.3 below.

###  5.1 The general approach

The general estimation approach proposed by Chen et al. (2022) can be
described this way: Approximate the observed feature density $\widehat{h}$ (on
the target dataset) by the hypothetical density $h_{\mathcal{F}}$ it would
have under $\mathcal{F}$-SJS. In the following, we present this approach in
mathematical terms.

In the context of Assumption 3.7, let $\mathcal{F}$ be a sub-$\sigma$-algebra
of $\mathcal{H}$ and keep the source distribution $P$ fixed. Define
$S(\mathcal{F})\ =\ \left\\{h_{Q}=\frac{dP|\mathcal{H}}{dQ|\mathcal{H}}:Q\ll
P,\ Q\ \text{related to}\ P\ \text{through}\ \mathcal{F}\text{-SJS}\right\\}.$
(5.1a) In the following, we make use of the fact that as a consequence of
(4.2) densities $h_{Q}\in S(\mathcal{F})$ can be represented as
$h_{Q}=\sum_{i=1}^{\ell}f_{i}\,\frac{Q[A_{i}]}{P[A_{i}]}\,P[A_{i}\,|\,\mathcal{H}],$
(5.1b) where $f_{i}$, $i=1,\ldots,\ell$, is an $\mathcal{F}$-measurable
density of the target class-conditional feature distribution $Q_{i}$ with
respect to the source class-conditional feature distribution $P_{i}$ (see
Definition 3.3) on $\mathcal{H}$.

Assume that $\widehat{h}$ is a density of the observed target feature
distribution $\widehat{Q}|\mathcal{H}$ with respect to the (also known) source
feature distribution $P|\mathcal{H}$. The task is to approximate $\widehat{h}$
as best as possible by an element $h_{Q}$ of $S(\mathcal{F})$. Hence the
following optimisation problem is to be solved:

$h_{Q}^{\ast}\ =\ \arg\min\limits_{h_{Q}\in
S(\mathcal{F})}D(\widehat{h},h_{Q}),$ (5.2)

for some distance measure $D$ for densities. Together with (5.1b), this is the
representation of Eq. (4.1) of Chen et al. (2022) translated into the notions
and notation of this paper. An optimal density $h_{Q}^{\ast}$ is specified by
the ingredients $f_{i}$, $Q[A_{i}]$, $P[A_{i}]$ and
$P[A_{i}\,|\,\mathcal{H}]$, $i=1,\ldots,\ell$, of (5.1b). The $P[A_{i}]$ and
$P[A_{i}\,|\,\mathcal{H}]$ are supposed to be known from the source dataset.
In any case, once the $f_{i}$ and the $Q[A_{i}]$ have been determined, the
full target distribution density $\bar{h}_{Q}$ on
$\sigma(\mathcal{H}\cup\mathcal{A})$ is given by the right-hand side of (4.2).

###  5.2 Minimising the Kullback-Leibler divergence

Chen et al. (2022) made two proposals for the choice of $D$ in (5.2). The
first proposal, called SEES-c, is to make use of the Kullback-Leibler (KL)
divergence.

######  Definition 5.1.

Assume that $\pi$ and $\kappa$ are probability measures on a measurable space
$(\Omega,\mathcal{M})$, with densities $p$ and $q$ respectively with regard to
another measure $\mu$ on $(\Omega,\mathcal{M})$. Then the _KL divergence_ of
$p$ and $q$ is defined as

$D_{KL}(p\|q)\ =\ \int p\,\log\left(\frac{p}{q}\right)d\mu\ =\
E_{\pi}\left[\log\left(\frac{p}{q}\right)\right],$

with $0\,\log(0)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}0$ and
$D_{KL}(p\|q)=\infty$ if $\kappa(M)=0<\pi(M)$ for any $M\in\mathcal{M}$ (i.e.
if $\pi$ is not absolutely continuous with respect to $\kappa$).

Note that in general $D_{KL}(p\|q)\neq D_{KL}(q\|p)$. By Jensen’s inequality,
$D_{KL}(p\|q)$ is non-negative and equals $0$ if and only if $\pi$-almost
surely it holds that $p=q$.

Writing down $D_{KL}$ with $\mu=P$, $\pi=\widehat{Q}|\mathcal{H}$, as well as
$\kappa=Q|\mathcal{H}$ and making use of (5.1b) gives

$\displaystyle D_{KL}(\widehat{h}\|h_{Q})$ $\displaystyle\ =\
E_{\widehat{Q}}\left[\log\left(\frac{\widehat{h}}{\sum_{i=1}^{\ell}f_{i}\,\frac{Q[A_{i}]}{P[A_{i}]}\,P[A_{i}\,|\,\mathcal{H}]}\right)\right]$
$\displaystyle\ =\
E_{\widehat{Q}}[\log(\widehat{h})]-E_{\widehat{Q}}\left[\log\left(\sum\nolimits_{i=1}^{\ell}f_{i}\,\tfrac{Q[A_{i}]}{P[A_{i}]}\,P[A_{i}\,|\,\mathcal{H}]\right)\right].$
(5.3a)

On the right-hand side of (5.3a), when optimisation over $h_{Q}$ is intended,
$E_{\widehat{Q}}[\log(\widehat{h})]$ is a constant and can be ignored. As a
consequence, estimation of $\widehat{h}$ in (5.2) can be avoided for
$D=D_{KL}$. In the second term on the right-hand side of (5.3a), the
$P[A_{i}]$ and $P[A_{i}\,|\,\mathcal{H}]$ are observable and can be treated as
known quantities such that the $f_{i}$ and $Q[A_{i}]$ are left as variables
whose values are to be optimally chosen.

If $\widehat{\varphi}_{i}$ denotes an estimator for $f_{i}\,Q[A_{i}]$, the
$\widehat{\varphi}_{i}$ must be $\mathcal{F}$-measurable and satisfy the
constraints

$E_{P_{i}}[\widehat{\varphi}_{i}]\ =\ Q[A_{i}],\qquad i=1,\ldots,\ell.$ (5.3b)

This implies

$1\ =\ \sum_{i=1}^{\ell}E_{P_{i}}[\widehat{\varphi}_{i}]\ =\
E_{P}\left[\sum_{i=1}^{\ell}\widehat{\varphi}_{i}\,\frac{P[A_{i}\,|\,\mathcal{H}]}{P[A_{i}]}\right].$
(5.3c)

Combining (5.3a) and (5.3c) for the specification of (5.2) with $D=D_{KL}$
gives the optimisation problem

$\begin{split}\max\limits_{\widehat{\varphi}_{1},\ldots,\widehat{\varphi}_{\ell}\geq
0,\,\mathcal{F}\text{-measurable}}E_{\widehat{Q}}\left[\log\left(\sum_{i=1}^{\ell}\widehat{\varphi}_{i}\,\tfrac{P[A_{i}\,|\,\mathcal{H}]}{P[A_{i}]}\right)\right],&\\\
\text{subject to:}\quad
E_{P}\left[\sum_{i=1}^{\ell}\widehat{\varphi}_{i}\,\frac{P[A_{i}\,|\,\mathcal{H}]}{P[A_{i}]}\right]\
=\ 1.&\end{split}$ (5.4)

Observe that in (5.4) the expectation $E_{P}$ can be approximated as a sample
mean based on the source dataset while $E_{\widehat{Q}}$ can be approximated
as a sample mean based on the target dataset. Once optimal
$\varphi_{1}^{\ast},\ldots,\varphi_{\ell}^{\ast}$ have been found, estimates
of the target class prior probabilities $Q[A_{i}]$ can be determined by means
of (5.3b), with the expectations $E_{P_{i}}$ replaced by sample means of the
strata of the source dataset defined by the observed class labels.

(5.4) corresponds to the optimisation objective for SEES-c of Chen et al.
(2022) in the case where $m$ and $I$ in Definition 1 of Chen et al. (2022) are
fixed (case of fixed shift index set). Chen et al. (2022, Paragraph ‘SEES-c’)
suggest keeping $\mathcal{F}$ (i.e. the set of input variables to the
functions $\widehat{\varphi}_{i}$) variable in (5.4) in order to be able to
find an ‘optimal’ $\mathcal{F}$. In order to achieve this, they add a term on
the right-hand side of (5.4) that rewards solutions with low numbers of input
features.

However, it is not clear that better fit by $\mathcal{F}$ than by
$\mathcal{F}^{\prime}$ implies that $\mathcal{F}$-SJS is a more appropriate
model than $\mathcal{F}^{\prime}$-SJS. For instance, assuming straightforward
covariate shift would give an exact fit. Similarly, with ‘factorizable joint
fit’, exact fit could even be achieved for arbitrary target label
distributions (in the binary case, see Proposition 2 of Tasche, 2022b).
Moreover, Chen et al. (2022) do not provide the details of how they select the
set of features to explain the SJS once an optimal solution to their version
of (5.4) has been found. Remark 4.4 above suggests that picking the features
with the $d-1$ largest contributions $\hat{\beta}_{i}$ as defined in Section
4.1 of Chen et al. (2022) would be a theoretically sound approach.

###  5.3 Second estimation strategy

The second proposal of Chen et al. (2022) for implementing (5.2) is intended
to apply to the case where all the features are discrete (or have been
discretised). The proposal is not straightforward at first glance because they
introduce – somewhat unexpected – in their Eq. (4.2) an “ML model”
$f:\mathbb{R}^{d}\to\mathcal{Y}$ which in the context of their SEES-d approach
appears to be a hard classifier as in (4.7).

In abstract terms, the rationale behind the SEES-d approach of Chen et al.
(2022) can be described as follows:

In practice, one problem with the optimisation problem (5.2) could be that
$\widehat{h}$ and the $P[A_{i}\,|\,\mathcal{H}]$ which appear in (5.1b) are
hard to estimate due to the curse of dimensionality when the original feature
information set $\mathcal{H}$ is big because it is generated by a high-
dimensional feature vector.

As a workaround for this problem, Chen et al. (2022) suggest replacing the
density family $S(\mathcal{F})$ as defined by (5.1a) with
$S(\mathcal{F},\mathcal{H}^{\prime})$ defined by

$S(\mathcal{F},\mathcal{H}^{\prime})\ =\
\left\\{h_{Q}=\frac{dP|\mathcal{H}^{\prime}}{dQ|\mathcal{H}^{\prime}}:Q\ll P,\
Q\ \text{related to}\ P\ \text{through}\
(\mathcal{F},\mathcal{H}^{\prime})\text{-SJS}\right\\},$ (5.5a) where
$\mathcal{H}^{\prime}\supset\mathcal{F}$ is a smaller sub-$\sigma$-algebra of
$\mathcal{H}$. This could be a sub-$\sigma$-algebra generated by a lower-
dimensional set of features.

(5.2) then is replaced with

$h_{Q}^{\ast}\ =\ \arg\min\limits_{h_{Q}\in
S(\mathcal{F},\mathcal{H}^{\prime})}D(\widehat{h}^{\prime},h_{Q}),$ (5.5b)

where $\widehat{h}^{\prime}$ is a density of
$\widehat{Q}|\mathcal{H}^{\prime}$ with respect to $P|\mathcal{H}^{\prime}$
which can be represented as

$\widehat{h}^{\prime}\ =\ E_{P}[\widehat{h}\,|\,\mathcal{H}^{\prime}].$ (5.6)

Assume that the probability measure $\widehat{Q}$ whose $\mathcal{H}$-density
$\widehat{h}$ appears in (5.2) and $P$ are related through $\mathcal{F}$-SJS.
Then it follows that both $\min_{h_{Q}\in
S(\mathcal{F})}D(\widehat{h},h_{Q})=0$ and $\min_{h_{Q}\in
S(\mathcal{F},\mathcal{H}^{\prime})}D(\widehat{h}^{\prime},h_{Q})=0$. In the
first case the interesting (not necessarily unique) minimising density
$\widehat{h}=h_{Q}^{\ast}$ has the representation

$\widehat{h}=\sum_{i=1}^{\ell}\widehat{f}_{i}\,\frac{\widehat{Q}[A_{i}]}{P[A_{i}]}\,P[A_{i}\,|\,\mathcal{H}],$

while in the second case, thanks to (5.6) the $\mathcal{H}^{\prime}$-density
$\widehat{h}^{\prime}$ of $\widehat{Q}$ can be written as

$\widehat{h}^{\prime}=\sum_{i=1}^{\ell}\widehat{f}_{i}\,\frac{\widehat{Q}[A_{i}]}{P[A_{i}]}\,P[A_{i}\,|\,\mathcal{H}^{\prime}].$

Hence if both minimising densities are unique (as for instance when Theorem
4.7 is applicable), they give rise to the same sets of $\widehat{f}_{i}$ and
$\widehat{Q}[A_{i}]$ such that the full
$\sigma(\mathcal{H}\cup\mathcal{A})$-density as given by the right-hand side
of (4.2) is well-defined and unique.

Unfortunately, if $\mathcal{H^{\prime}}$ in (5.5a) is chosen too small the
solution $h_{Q}^{\ast}$ may no longer be unique since satisfying the rank
condition (4.6) of Theorem 4.7 might turn out to be impossible.

Chen et al. (2022) deploy another workaround to deal with this side effect.
Let $\mathbf{C}=(C_{1},\ldots,C_{\ell})$ be a hard (or crisp) classifier in
the sense of (4.7). Chen et al. (2022) talk of “ML model” instead of
classifier and denote it by $f$. Define
$\mathcal{C}=\sigma(\mathbf{C})=\sigma\bigl{(}\\{C_{1},\ldots,C_{\ell}\\}\bigr{)}$.
Chen et al. (2022) then solve (5.5b) with
$\mathcal{H}_{\mathcal{C}}=\sigma(\mathcal{H}^{\prime}\cup\mathcal{C})$
substituted for $\mathcal{H}^{\prime}$. With this augmentation, if
$\mathbf{C}$ is a reasonably accurate classifier, it becomes likely that in
Theorem 4.7 the rank condition (4.6) can be satisfied with the choice
$(X_{1},\ldots,X_{\ell})=\mathbf{C}$.

Along this line of thought, also the choice
$\mathcal{H}^{\prime}=\sigma(\mathcal{F}\cup\mathcal{C})$ might make sense in
(5.5b). Via Eq. (B.3), with $\mathcal{G}=\mathcal{F}$ and
$X_{i}=\mathbf{1}_{C_{i}}$, this choice leads to a _conditional_ (on
$\mathcal{F}$) _confusion matrix_ method for the posterior probabilities in
the target domain for general SJS and the original confusion matrix method
(Saerens et al., 2001) for prior probability shift (case
$\mathcal{F}=\\{\emptyset,\Omega\\}$). See (C.6) for its description in the
case of discrete features.

For the readers’ convenience, a full ‘instantiation’ of the approach sketched
in this section is detailed in Appendix C for the case where all features are
discrete.

######  Remark 5.2.

_In their implementation of SEES-d, Chen et al. (2022) chose the
$\mathcal{H}^{\prime}$ in (5.5b) dependent on $\mathcal{F}$, i.e.
$\mathcal{H}^{\prime}=\Phi(\mathcal{F})$ for some algorithm $\Phi$, in order
to be able to select an ‘optimal’ $\mathcal{F}$ by comparing the minima
achieved in (5.5b) for different $\mathcal{F}$. As different
$\mathcal{H}^{\prime}$ may result in different marginal densities
$\widehat{h}^{\prime}$, there is a risk of comparing apples to pears when the
originally observed marginal feature density $\widehat{h}$ is not an element
of $S(\mathcal{F})$ as defined in (5.1a). As a consequence, the true minimum
of (5.2) might be missed. ∎_

Taking recourse to Corollary 4.3 above, perhaps along the lines suggested in
Remark 4.4, could provide an alternative approach to reduce the computational
complexity of solving the opimisation problems (5.2) and (5.5b).

##  6 Conclusions

Modelling dataset shift with sparse joint shift (SJS) as proposed by Chen et
al. (2022) is a promising approach to inferring the full joint distribution of
features and labels of a target dataset for which only the features have been
observed. The approach is based on learning from a source dataset with
complete information on features and labels.

In this paper, we have revisited and complemented the theory for SJS in some
aspects, in particular with regard to the transmission of SJS from sets of
features to larger sets of features, a conditional correction formula for the
class posterior probabilities, identifiability of SJS, and the relationship
between SJS and covariate shift.

In addition, with regard to the estimation of the shift characteristics in
practice, we have complemented the rationale for the algorithms proposed by
Chen et al. (2022) and pointed out inconsistencies which could prevent them
from identifying optimal solutions.

## References

  * Azizzadenesheli (2022) K. Azizzadenesheli.  Importance Weight Estimation and Generalization in Domain Adaptation Under Label Shift.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 44(10):6578–6584, 2022.  10.1109/TPAMI.2021.3086060.
  * Ben-David et al. (2006) S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira.  Analysis of Representations for Domain Adaptation.  In B. Schölkopf, J. Platt, and T. Hoffman, editors, _Advances in Neural Information Processing Systems_ , volume 19, pages 137–144. MIT Press, 2006.
  * Billingsley (1986) P. Billingsley.  _Probability and measure_.  John Wiley & Sons, second edition, 1986.
  * Chen et al. (2022) L. Chen, M. Zaharia, and J. Zou.  Estimating and Explaining Model Performance When Both Covariates and Labels Shift, 2022.  URL https://doi.org/10.48550/arXiv.2209.08436.
  * Elkan (2001) C. Elkan.  The foundations of cost-sensitive learning.  In B. Nebel, editor, _Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001_ , pages 973–978. Morgan Kaufmann, 2001\.
  * Forman (2008) G. Forman.  Quantifying counts and costs via classification.  _Data Mining and Knowledge Discovery_ , 17(2):164–206, 2008.
  * He et al. (2021) H. He, Y. Yang, and H. Wang.  Domain Adaptation with Factorizable Joint Shift.  Presented at the ICML 2021 Workshop on Uncertainty and Robustness in Deep Learning, 2021.
  * Hofer (2015) V. Hofer.  Adapting a classification rule to local and global shift when only unlabelled data are available.  _European Journal of Operational Research_ , 243(1):177–189, 2015.
  * Holzmann and Eulert (2014) H. Holzmann and M. Eulert.  The role of the information set for forecasting – with applications to risk management.  _The Annals of Applied Statistics_ , 8(1):595–621, 2014.  10.1214/13-AOAS709.
  * Johansson et al. (2019) F.D. Johansson, D. Sontag, and R. Ranganath.  Support and Invertibility in Domain-Invariant Representations.  In K. Chaudhuri and M. Sugiyama, editors, _Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics_ , volume 89 of _Proceedings of Machine Learning Research_ , pages 527–536. PMLR, 16–18 Apr 2019.
  * Kirchmeyer et al. (2021) M. Kirchmeyer, A. Rakotomamonjy, E. de Bezenac, and P. Gallinari.  Mapping conditional distributions for domain adaptation under generalized target shift, 2021.  URL https://arxiv.org/abs/2110.15057.  Presented at ICLR 2022.
  * Klebaner (2005) F.C. Klebaner.  _Introduction to Stochastic Calculus with Applications_.  Imperial College Press, second edition, 2005.
  * Klenke (2013) A. Klenke.  _Probability Theory: A Comprehensive Course_.  Springer Science & Business Media, 2013.
  * Moreno-Torres et al. (2012) J.G. Moreno-Torres, T. Raeder, R. Alaiz-Rodriguez, N.V. Chawla, and F. Herrera.  A unifying view on dataset shift in classification.  _Pattern Recognition_ , 45(1):521–530, 2012.
  * Saerens et al. (2001) M. Saerens, P. Latinne, and C. Decaestecker.  Adjusting the Outputs of a Classifier to New a Priori Probabilities: A Simple Procedure.  _Neural Computation_ , 14(1):21–41, 2001.
  * Scott (2019) C. Scott.  A Generalized Neyman-Pearson Criterion for Optimal Domain Adaptation.  In _Proceedings of Machine Learning Research, 30th International Conference on Algorithmic Learning Theory_ , volume 98, pages 1–24, 2019.
  * Shimodaira (2000) H. Shimodaira.  Improving predictive inference under covariate shift by weighting the log-likelihood function.  _Journal of statistical planning and inference_ , 90(2):227–244, 2000.
  * Storkey (2009) A. Storkey.  When Training and Test Sets Are Different: Characterizing Learning Transfer.  In J. Quiñonero-Candela, M. Sugiyama, A. Schwaighofer, and N.D. Lawrence, editors, _Dataset Shift in Machine Learning_ , chapter 1, pages 3–28. The MIT Press, Cambridge, Massachusetts, 2009.
  * Sugiyama et al. (2012) M. Sugiyama, T. Suzuki, and T. Kanamori.  _Density ratio estimation in machine learning_.  Cambridge University Press, 2012.
  * Tasche (2021) D. Tasche.  Calibrating sufficiently.  _Statistics_ , 55(6):1356–1386, 2021.  10.1080/02331888.2021.2016767.
  * Tasche (2022a) D. Tasche.  Class Prior Estimation under Covariate Shift: No Problem?  Working paper, presented at ECML/PKDD 2022 workshop Learning to Quantify: Methods and Applications (LQ 2022), 2022a.
  * Tasche (2022b) D. Tasche.  Factorizable Joint Shift in Multinomial Classification.  _Machine Learning and Knowledge Extraction_ , 4(3):779–802, 2022b.  10.3390/make4030038.
  * Zhang et al. (2013) K. Zhang, B. Schölkopf, K. Muandet, and Z. Wang.  Domain Adaptation Under Target and Conditional Shift.  In _Proceedings of the 30th International Conference on International Conference on Machine Learning – Volume 28_ , ICML’13, pages III–819–III–827. JMLR.org, 2013.  URL http://dl.acm.org/citation.cfm?id=3042817.3043028.

##  Appendix A Some concepts and notation from probability theory

The general approach to the subject in this paper is based on application of
probabilistic measure theory, as described for instance in the textbooks of
Billingsley (1986) and Klenke (2013).

For easy reference, here is a brief glossary of concepts and notation
frequently used in the paper:

Measurable space $(\Omega,\mathcal{M})$. According to Billingsley (1986, p.
16) “In probability theory $\Omega$ consists of all the possible results or
outcomes $\omega$ of an experiment or observation.” $\mathcal{M}$ is a
$\sigma$-_algebra_ (also called $\sigma$-field), i.e. a family of subsets of
$\Omega$ with the following three properties:

  * (i)

$\emptyset\in\mathcal{H}$,

  * (ii)

$M\in\mathcal{M}\Rightarrow\Omega\setminus M\in\mathcal{M}$.

  * (iii)

$M_{n}\in\mathcal{M}$ for $n\in\mathbb{N}$ $\Rightarrow$
$\bigcup_{n\in\mathbb{N}}M_{n}\in\mathcal{M}$.

The intersections of $\sigma$-algebras again are $\sigma$-algebras. Is
$\mathcal{M}_{0}$ is any family of subsets of $\Omega$, the (non-empty)
intersection of all $\sigma$-algebras on $\Omega$ that contain
$\mathcal{M}_{0}$ is called $\sigma$-_algebra generated by_ $\mathcal{M}_{0}$
and denoted by $\sigma(\mathcal{M}_{0})$. The $\sigma$-algebra
$\sigma(\mathcal{M}_{0})$ is also the smallest $\sigma$-algebra containing
$\mathcal{M}_{0}$.

Probability space $(\Omega,\mathcal{M},P)$. $(\Omega,\mathcal{M})$ is a
measurable space, $P$ is a _probability measure_ on $(\Omega,\mathcal{M})$,
i.e. a measure (see Billingsley, 1986, Chapter 2) with $P[\Omega]=1$. For
$M\in\mathcal{M}$, $P[M]$ is the _probability of the event_ $M$. A property of
outcomes $\omega\in\Omega$ is said to hold $P$-_almost surely_ if the event of
all the $\omega$ with the property has probability $1$ under $P$.

Mappings and random variables. For a fixed set $S$, the function
$\mathbf{1}_{S}$ with $\mathbf{1}_{S}(s)=1$ for $s\in S$ and
$\mathbf{1}_{S}(s)=0$ for $s\notin S$ is called _indicator function_.
A mapping $X:(\Omega,\mathcal{M})\to(\Omega^{\prime},\mathcal{M}^{\prime})$ is
$\mathcal{M}^{\prime}$-$\mathcal{M}$-_measurable_ if
$X^{-1}(M^{\prime})\in\mathcal{M}$ for all
$M^{\prime}\in\mathcal{M}^{\prime}$.
A real-valued measurable mapping $X$ defined on a probability space
$(\Omega,\mathcal{M},P)$ is also called _random variable_ or _statistic_.

Information set. $\sigma$-algebras, on the one hand, are needed for consistent
definitions of integrals and probabilities. On the other hand, they are of
interest because they can be used to reflect available information. If
$\mathcal{M}_{1},\mathcal{M}_{2}$ are $\sigma$-algebras with
$\mathcal{M}_{1}\subset\mathcal{M}_{2}$ then $\mathcal{M}_{1}$ conveys less
information than $\mathcal{M}_{2}$. If $X$ is a mapping into a measurable
space $(\Omega^{\prime},\mathcal{M}^{\prime})$, the $\sigma$-algebra
$\sigma(X)=\sigma(X^{-1}(M^{\prime}):M^{\prime}\in\mathcal{M})$ reflects the
information obtainable by observation of the outcomes of $X$. For these
reasons, $\sigma$-algebras are also called _information sets_ (see, e.g.
Holzmann and Eulert, 2014).

Expected value and conditional expectation. If $(\Omega,\mathcal{M},P)$ is a
probability space and $X$ an integrable random variable on $\Omega$, the
_expected value_ of $X$ is $E_{P}[X]=\int X\,dP$.
If $\mathcal{H}\subset\mathcal{M}$ is a sub-$\sigma$-algebra of $\mathcal{M}$,
any $\mathcal{H}$-measurable integrable random variable $Z$ is called
_expectation of_ $X$ _conditional on_ $\mathcal{H}$ if
$E_{P}[\mathbf{1}_{H}\,Z]=E_{P}[\mathbf{1}_{H}\,X]$ for all $H\in\mathcal{H}$.
If $Z_{1}$ and $Z_{2}$ are both expectations of $X$ conditional on
$\mathcal{H}$ it follows that $P[Z_{1}\neq Z_{2}]=0$.
$E_{P}[X\,|\,\mathcal{H}]$ is short hand for any expectation $Z$ of $X$
conditional on $\mathcal{H}$.
For any $M\in\mathcal{M}$, the conditional expectation
$E_{P}[\mathbf{1}_{M}\,|\,\mathcal{H}]=P[M\,|\,\mathcal{H}]$ is called
_probability of_ $M$ _conditional on_ $\mathcal{H}$.

Absolute continuity and densities. Let $(\Omega,\mathcal{M})$ be a measurable
space and $\mu$ and $\nu$ be measures on $(\Omega,\mathcal{M})$. The measure
$\mu$ is _absolutely continuous with respect to_ $\nu$ (short hand:
$\mu\ll\nu$) if $\nu[N]=0$ for any $N\in\mathcal{M}$ implies $\mu[N]=0$.
By the Radon-Nikodym theorem (Billingsley, 1986, Theorem 32.2), if $\mu$ and
$\nu$ are both $\sigma$-finite then $\mu\ll\nu$ is equivalent to the existence
of a density $\varphi=\frac{d\mu}{d\nu}$ of $\mu$ with respect to $\nu$, i.e.
of a non-negative $\mathcal{M}$-measurable function $\varphi$ such that
$\mu[M]=\int_{M}\varphi\,d\nu$ for all $M\in\mathcal{M}$.
Let $Q\ll P$ be probability measures on $(\Omega,\mathcal{M})$ with density
$\varphi=\frac{dQ}{dP}$ and $\mathcal{H}$ be a sub-$\sigma$-algebra of
$\mathcal{M}$. Then $\varphi_{\mathcal{H}}=E_{P}[\varphi\,|\,\mathcal{H}]$ is
a density of $Q$ with respect to $P$ on the measurable space
$(\Omega,\mathcal{H})$. In this case, the application of the operator
$E_{P}[\cdot\,|\,\mathcal{H}]$ corresponds to the ‘integrating out a set of
variables’ operation in the setting of multivariate Lebesgue-densities in
order to obtain a marginal distribution.
We use short hand $P|\mathcal{H}$ ($P$ _restricted to_ $\mathcal{H}$) for the
probability space $(\Omega,\mathcal{H},P)$.

##  Appendix B Proofs

###### Proof of Proposition 3.8..

Since (i) implies (iii) with $\mathcal{G}=\mathcal{H}$, we only need to prove
that (3.5a) holds if (3.5b) is true.

Observe that under Assumption 3.7, $Q$ is also absolutely continuous with
respect to $P$ on $\mathcal{H}$. Moreover, by Lemma 1 of Tasche (2022b) each
target class-conditional feature distribution $Q_{i}$ is also absolutely
continuous with respect to the source class-conditional feature distribution
$P_{i}$ on $\mathcal{H}$.

Let $G\in\mathcal{G}$ and $F\in\mathcal{F}$ as well as
$i\in\\{1,\ldots,\ell\\}$ be given. Denote by $h_{i}$ any
$\mathcal{H}$-density of $Q_{i}$ with respect to $P_{i}$. Then
$f_{i}=E_{P_{i}}[h_{i}\,|\,\mathcal{F}]$ is $\mathcal{F}$-measurable and a
density of $Q_{i}$ with respect to $P_{i}$ on $\mathcal{F}$. Therefore, we
obtain for any $\bar{F}\in\mathcal{F}$

$\displaystyle E_{Q_{i}}\bigl{[}\mathbf{1}_{\bar{F}}\,P_{i}[G\cap
F\,|\,\mathcal{F}]\bigr{]}$
$\displaystyle=E_{P_{i}}\bigl{[}f_{i}\,\mathbf{1}_{\bar{F}}\,P_{i}[G\cap
F\,|\,\mathcal{F}]\bigr{]}$
$\displaystyle=E_{P_{i}}\bigl{[}f_{i}\,\mathbf{1}_{\bar{F}\cap
F}\,P_{i}[G\,|\,\mathcal{F}]\bigr{]}$
$\displaystyle=E_{P_{i}}\bigl{[}f_{i}\,\mathbf{1}_{\bar{F}\cap
F}\,Q_{i}[G\,|\,\mathcal{F}]\bigr{]}$
$\displaystyle=E_{Q_{i}}\bigl{[}\mathbf{1}_{\bar{F}\cap
F}\,Q_{i}[G\,|\,\mathcal{F}]\bigr{]}$ $\displaystyle=Q_{i}[\bar{F}\cap F\cap
G].$

This proves (3.3) for $H\in\mathfrak{P}=\\{F\cap
G:F\in\mathcal{F},G\in\mathcal{G}\\}\subset\mathcal{H}$. The set family
$\mathfrak{P}$ is $\cap$-stable. In addition, it can readily be shown that the
set family of all $H\in\mathcal{H}$ such that (3.3) is true is an
$\lambda$-system (or Dynkin system) in the sense of Billingsley (1986, p. 36).
Since $\mathcal{H}=\sigma(\mathfrak{P})$, it follows from Dynkin’s
$\pi$-$\lambda$-theorem (Billingsley, 1986, Theorem 3.6) that $\eqref{eq:X}$
is true for $X=\mathbf{1}_{H}$ if $H\in\mathcal{H}$. This implies that
$\eqref{eq:X}$ holds for any $\mathcal{H}$-measurable simple random variable,
and by monotone convergence even for all non-negative $\mathcal{H}$-measurable
random variables (Billingsley, 1986, Theorems 13.5 and 34.2). ∎

###### Proof of Proposition 4.5.

By Corollary 1 of Tasche (2022b),
$f=\sum_{j=1}^{\ell}f_{j}\,\frac{Q[A_{j}]}{P[A_{j}]}\,P[A_{j}\,|\,\mathcal{F}]$
is a density of $Q$ with respect to $P$ on $\mathcal{F}$, where $f_{j}$
denotes a density of $Q_{j}$ with respect to $P_{j}$ on $\mathcal{F}$. As a
consequence, it holds that $Q[f>0]=1$. Corollary 2 of Tasche (2022b) then
implies that $Q$-almost surely

$Q[A_{i}\,|\,\mathcal{F}]\ =\
f_{i}\,\frac{Q[A_{i}]}{P[A_{i}]}\,P[A_{i}\,|\,\mathcal{F}]\,/\,f,\quad
i=1,\ldots,\ell.$ (B.1)

Define

$N\ =\
\bigcup_{j=1}^{\ell}\bigl{\\{}P[A_{j}\,|\,\mathcal{F}]=0,P[A_{j}\,|\,\mathcal{H}]>0\bigr{\\}}.$

Then it follows that $Q[N]=0$ because

$\displaystyle
E_{P}\bigl{[}P[A_{j}\,|\,\mathcal{H}]\,\mathbf{1}_{\\{P[A_{j}\,|\,\mathcal{F}]=0\\}}\bigr{]}$
$\displaystyle=P\bigl{[}A_{j}\cap\bigl{\\{}P[A_{j}\,|\,\mathcal{F}]=0\bigr{\\}}\bigr{]}$
$\displaystyle=E_{P}\bigl{[}P[A_{j}\,|\,\mathcal{F}]\,\mathbf{1}_{\\{P[A_{j}\,|\,\mathcal{F}]=0\\}}\bigr{]}$
$\displaystyle=0,$

and therefore
$0=P\bigl{[}P[A_{j}\,|\,\mathcal{F}]=0,P[A_{j}\,|\,\mathcal{H}]>0\bigr{]}$ and
also
$0=Q\bigl{[}P[A_{j}\,|\,\mathcal{F}]=0,P[A_{j}\,|\,\mathcal{H}]>0\bigr{]}$.
With the convention $0/0=0$, therefore (B.1) implies for $i=1,\ldots,\ell$
that

$f\,\frac{Q[A_{i}\,|\,\mathcal{F}]}{P[A_{i}\,|\,\mathcal{F}]}\,P[A_{i}\,|\,\mathcal{H}]\
=\ f_{i}\,\frac{Q[A_{i}]}{P[A_{i}]}\,P[A_{i}\,|\,\mathcal{H}]$ (B.2)

holds on $\Omega\setminus N$ and hence $Q$-almost surely.

Theorem 4.1 implies that

$h\ =\
\sum_{j=1}^{\ell}f_{j}\,\frac{Q[A_{j}]}{P[A_{j}]}\,P[A_{j}\,|\,\mathcal{H}]$

is a density of $Q$ with respect to $P$ on $\mathcal{H}$ and $Q[h>0]=1$ holds
true. In this case, Corollary 2 of Tasche (2022b) implies that $Q$-almost
surely

$Q[A_{i}\,|\,\mathcal{H}]\ =\
\frac{f_{i}\,\frac{Q[A_{i}]}{P[A_{i}]}\,P[A_{i}\,|\,\mathcal{H}]}{\sum_{j=1}^{\ell}f_{j}\,\frac{Q[A_{j}]}{P[A_{j}]}\,P[A_{j}\,|\,\mathcal{H}]}\quad
i=1,\ldots,\ell.$

Substituting the left-hand side of (B.2) for the terms
$f_{j}\,\frac{Q[A_{j}]}{P[A_{j}]}\,P[A_{j}\,|\,\mathcal{H}]$,
$j=1,\ldots,\ell$, now implies (4.4a) and (4.4b). ∎

###### Proof of Lemma 4.6.

(4.5b) is implied by

$\displaystyle E_{\mu}[X\,|\,\mathcal{G}]$
$\displaystyle=\sum_{j=1}^{\ell}E_{\mu}[X\,\mathbf{1}_{A_{j}}\,|\,\mathcal{G}]$
$\displaystyle=\sum_{j=1}^{\ell}E_{\mu}\bigl{[}E_{\mu}[X\,\mathbf{1}_{A_{j}}\,|\,\sigma(\mathcal{G}\cup\mathcal{A})]\bigm{|}\mathcal{G}\bigr{]}$
$\displaystyle=\sum_{j=1}^{\ell}E_{\mu}\bigl{[}\mathbf{1}_{A_{j}}\,E_{\mu}[X\,|\,\sigma(\mathcal{G}\cup\mathcal{A})]\bigm{|}\mathcal{G}\bigr{]}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:genBayes}}}{{=}}\sum_{j=1}^{\ell}E_{\mu}\bigl{[}\mathbf{1}_{A_{j}}\,E_{\mu_{j}}[X\,|\,\mathcal{G}]\bigm{|}\mathcal{G}\bigr{]}$
$\displaystyle=\sum_{j=1}^{\ell}\mu[A_{j}\,|\,\mathcal{G}]\,E_{\mu_{j}}[X\,|\,\mathcal{G}],$

for any non-negative $\mathcal{M}$-measurable random variable $X$. ∎

###### Proof of Theorem 4.7.

Define $\mathcal{G}=\sigma(\mathcal{F}\cup\mathcal{F}^{\prime})$. By Corollary
4.3, both $Q$ and $Q^{\prime}$ are related to $P$ through $\mathcal{G}$-SJS.
Hence for $i,j\in\\{1,\ldots,\ell\\}$ it holds that

$E_{P_{j}}[X_{i}\,|\,\mathcal{G}]\ =\ E_{Q_{j}}[X_{i}\,|\,\mathcal{G}]\ =\
E_{Q^{\prime}_{j}}[X_{i}\,|\,\mathcal{G}].$

Therefore, we have
$R(P,\mathcal{G},\ell)=R(Q,\mathcal{G},\ell)=R(Q^{\prime},\mathcal{G},\ell)=R$.
The matrix $R$ is invertible with probability $1$ under $P$ and therefore also
under $Q$ and $Q^{\prime}$. Hence, because $Q$ and $Q^{\prime}$ are equal on
$\mathcal{H}$, we obtain from Lemma 4.6 that

$\begin{pmatrix}Q^{\prime}[A_{1}\,|\,\mathcal{G}]\\\ \vdots\\\
Q^{\prime}[A_{\ell}\,|\,\mathcal{G}]\end{pmatrix}\ =\
\begin{pmatrix}Q[A_{1}\,|\,\mathcal{G}]\\\ \vdots\\\
Q[A_{\ell}\,|\,\mathcal{G}]\end{pmatrix}\ =\
R^{-1}\times\begin{pmatrix}E_{Q}[X_{1}\,|\,\mathcal{G}]\\\ \vdots\\\
E_{Q}[X_{\ell}\,|\,\mathcal{G}]\end{pmatrix}.$ (B.3)

Proposition 4.5 and (B.3) together now imply that

$\frac{\frac{Q[A_{i}\,|\,\mathcal{G}]}{P[A_{i}\,|\,\mathcal{G}]}P[A_{i}\,|\,\mathcal{H}]}{\sum_{j=1}^{\ell}\frac{Q[A_{j}\,|\,\mathcal{G}]}{P[A_{j}\,|\,\mathcal{G}]}P[A_{j}\,|\,\mathcal{H}]}\
=\ Q[A_{i}\,|\,\mathcal{H}]\ =\ Q^{\prime}[A_{i}\,|\,\mathcal{H}],\quad
i=1\,\ldots,\ell.$ (B.4)

By (3.1b), for each $M\in\sigma(\mathcal{H}\cup\mathcal{A})$ there are
$H_{1},\ldots,H_{\ell}$ such that $M=\bigcup_{i=1}^{\ell}(H_{i}\cap A_{i})$.
Therefore, it follows from (B.4) that

$\displaystyle Q^{\prime}[M]$
$\displaystyle=\sum_{i=1}^{\ell}Q^{\prime}[H_{i}\cap A_{i}]$
$\displaystyle=\sum_{i=1}^{\ell}E_{Q^{\prime}}\bigl{[}\mathbf{1}_{H_{i}}\,Q^{\prime}[A_{i}\,|\,\mathcal{H}]\bigr{]}$
$\displaystyle=\sum_{i=1}^{\ell}E_{Q^{\prime}}\bigl{[}\mathbf{1}_{H_{i}}\,Q[A_{i}\,|\,\mathcal{H}]\bigr{]}$
$\displaystyle=\sum_{i=1}^{\ell}E_{Q}\bigl{[}\mathbf{1}_{H_{i}}\,Q[A_{i}\,|\,\mathcal{H}]\bigr{]}$
$\displaystyle=\sum_{i=1}^{\ell}Q[H_{i}\cap A_{i}]$ $\displaystyle=Q[M].$

This completes the proof. ∎

###### Proof of Lemma 4.8.

Define $\mathcal{G}=\sigma(\mathcal{F}\cup\mathcal{F}^{\prime})$. We have to
show that $P\bigl{[}\det\bigl{(}R(P,\mathcal{G},2)\bigr{)}\neq 0\bigr{]}=1$
and (4.8b) are equivalent. First, we obtain

$\displaystyle\det(R)$
$\displaystyle=\begin{pmatrix}E_{P_{1}}[X_{1}\,|\,\mathcal{G}]&E_{P_{2}}[X_{1}\,|\,\mathcal{G}]\\\
E_{P_{1}}[X_{2}\,|\,\mathcal{G}]&E_{P_{2}}[X_{2}\,|\,\mathcal{G}]\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\frac{E_{P}[\mathbf{1}_{A_{1}}\,X_{1}\,|\,\mathcal{G}]}{P[A_{1}\,|\,\mathcal{G}]}&\frac{E_{P}[\mathbf{1}_{A_{2}}\,X_{1}\,|\,\mathcal{G}]}{P[A_{2}\,|\,\mathcal{G}]}\\\
\frac{E_{P}[\mathbf{1}_{A_{1}}\,X_{2}\,|\,\mathcal{G}]}{P[A_{1}\,|\,\mathcal{G}]}&\frac{E_{P}[\mathbf{1}_{A_{2}}\,X_{2}\,|\,\mathcal{G}]}{P[A_{2}\,|\,\mathcal{G}]}\end{pmatrix}.$
(B.5)

Note that in (B.5), $P[A_{j}\,|\,\mathcal{G}]=0$ implies
$E_{P}[\mathbf{1}_{A_{j}}\,X_{i}\,|\,\mathcal{G}]=0$ and, therefore, “$0/0$”
is understood as $0$. It follows that

$\det(R)\neq 0\quad\iff\quad
E_{P}[\mathbf{1}_{A_{1}}\,X_{1}\,|\,\mathcal{G}]\,E_{P}[\mathbf{1}_{A_{2}}\,X_{2}\,|\,\mathcal{G}]-E_{P}[\mathbf{1}_{A_{2}}\,X_{1}\,|\,\mathcal{G}]\,E_{P}[\mathbf{1}_{A_{1}}\,X_{2}\,|\,\mathcal{G}]\neq
0.$

Making now use of (4.8a) and hence $X_{2}=1-X_{1}$, we obtain

$\displaystyle
E_{P}[\mathbf{1}_{A_{1}}\,X_{1}\,|\,\mathcal{G}]\,E_{P}[\mathbf{1}_{A_{2}}\,X_{2}\,|\,\mathcal{G}]-E_{P}[\mathbf{1}_{A_{2}}\,X_{1}\,|\,\mathcal{G}]\,E_{P}[\mathbf{1}_{A_{1}}\,X_{2}\,|\,\mathcal{G}]$
$\displaystyle=$ $\displaystyle
E_{P}\big{[}P[A_{1}\,|\,\mathcal{H}]^{2}\,\big{|}\,\mathcal{G}\big{]}\Big{(}P[A_{2}\,|\,\mathcal{G}]-E_{P}\big{[}P[A_{1}\,|\,\mathcal{H}]\,P[A_{2}\,|\,\mathcal{H}]\,\big{|}\,\mathcal{G}\big{]}\Big{)}$
$\displaystyle-\Big{(}P[A_{1}\,|\,\mathcal{G}]-E_{P}\big{[}P[A_{1}\,|\,\mathcal{H}]^{2}\,\big{|}\,\mathcal{G}\big{]}\Big{)}E_{P}\big{[}P[A_{1}\,|\,\mathcal{H}]\,P[A_{2}\,|\,\mathcal{H}]\,\big{|}\,\mathcal{G}\big{]}$
$\displaystyle=$ $\displaystyle
E_{P}\big{[}P[A_{1}\,|\,\mathcal{H}]^{2}\,\big{|}\,\mathcal{G}\big{]}\Big{(}1-2\,P[A_{1}\,|\,\mathcal{G}]+E_{P}\big{[}P[A_{1}\,|\,\mathcal{H}]^{2}\,\big{|}\,\mathcal{G}\big{]}\Big{)}-\Big{(}P[A_{1}\,|\,\mathcal{G}]-E_{P}\Big{[}P[A_{1}\,|\,\mathcal{H}]^{2}\,\big{|}\,\mathcal{G}\Big{]}\Big{)}^{2}$
$\displaystyle=$ $\displaystyle
E_{P}\big{[}P[A_{1}\,|\,\mathcal{H}]^{2}\,\big{|}\,\mathcal{G}\big{]}-P[A_{1}\,|\,\mathcal{G}]^{2}$
$\displaystyle=$
$\displaystyle\mathrm{var}_{P}\bigl{[}P[A_{1}\,|\,\mathcal{H}]\,\big{|}\,\mathcal{G}\bigr{]}.$

As a result, we have found that

$\det(R)\neq
0\qquad\iff\qquad\mathrm{var}_{P}\bigl{[}P[A_{1}\,|\,\mathcal{H}]\,\big{|}\,\mathcal{G}\bigr{]}>0.$

Since
$\mathrm{var}_{P}\bigl{[}P[A_{1}\,|\,\mathcal{H}]\,\big{|}\,\mathcal{G}\bigr{]}>0$
$\Leftrightarrow$ $P[A_{1}\,|\,\mathcal{H}]\neq P[A_{1}\,|\,\mathcal{G}]$ with
positive probability, the equivalence of (4.6) and (4.8b) follows. ∎

######  Lemma B.1.

Under Assumption 3.7, let $\mathcal{F}$ be a sub-$\sigma$-algebra of
$\mathcal{H}$ such that $Q$ is related to $P$ through $\mathcal{F}$-SJS.
Suppose in addition that $Q$ and $P$ are also related by
$\mathcal{H}$-covariate shift (i.e. (4.12) is true) and that condition (4.13a)
is satisfied. Then it follows that

$Q[A_{i}\,|\,\mathcal{F}]\ =\ P[A_{i}\,|\,\mathcal{F}],\qquad
i=1,\ldots,\ell.$ (B.6)

###### Proof of Lemma B.1.

Observe that
$P\bigl{[}P[A_{i}\,|\,\mathcal{F}]=0,\,P[A_{i}\,|\,\mathcal{H}]>0\bigr{]}=0$.
This implies

$P\bigl{[}P[A_{i}\,|\,\mathcal{F}]=0\bigr{]}\ \leq\
P\bigl{[}P[A_{i}\,|\,\mathcal{H}]=0\bigr{]}\ =\ 0.$

Define
$Z=\sum_{j=1}^{\ell}\frac{Q[A_{j}\,|\,\mathcal{F}]}{P[A_{j}\,|\,\mathcal{F}]}\,P[A_{j}\,|\,\mathcal{\mathcal{H}}]$.
Then it holds that

$Z=0\quad\Rightarrow\quad\frac{Q[A_{j}\,|\,\mathcal{F}]}{P[A_{j}\,|\,\mathcal{F}]}\,P[A_{j}\,|\,\mathcal{\mathcal{H}}]\
=\ 0\quad\text{for all}\ j=1,\ldots,\ell.$ (B.7)

By Proposition 4.5 and the assumption of covariate shift, we obtain on the
event $\\{Z>0\\}$ for all $i=1,\ldots,\ell$

$P[A_{i}\,|\,\mathcal{H}]\ =\
\frac{Q[A_{i}\,|\,\mathcal{F}]}{P[A_{i}\,|\,\mathcal{F}]}\,\frac{P[A_{i}\,|\,\mathcal{H}]}{Z}.$

By (B.7) and $P[A_{i}\,|\,\mathcal{H}]>0$, it follows with probability $1$
under $P$ that for all $i=1,\ldots,\ell$

$Z\ =\ \frac{Q[A_{i}\,|\,\mathcal{F}]}{P[A_{i}\,|\,\mathcal{F}]}.$

This implies
$1=E_{P}[Z\,|\,\mathcal{F}]=\frac{Q[A_{i}\,|\,\mathcal{F}]}{P[A_{i}\,|\,\mathcal{F}]}$
and hence also (B.6). ∎

###### Proof of Theorem 4.16.

Show (i): Since $R$ is invertible by assumption, Lemma 4.6 implies
$Q[A_{i}\,|\,\mathcal{F}]=P[A_{i}\,|\,\mathcal{F}]$ for all $i=1,\ldots,\ell$.
(CSH) now follows from Proposition 4.5.

Show (ii): For any $i=1,\ldots,\ell$ and $H\in\mathcal{H}$, it holds that

$\displaystyle Q[A_{i}\cap H\,|\,\mathcal{F}]$
$\displaystyle=E_{Q}\bigl{[}\mathbf{1}_{H}\,Q[A_{i}\,|\,\mathcal{H}]\,\big{|}\,\mathcal{F}\bigr{]}$
$\displaystyle\stackrel{{\scriptstyle(CSH)}}{{=}}E_{Q}\bigl{[}\mathbf{1}_{H}\,P[A_{i}\,|\,\mathcal{H}]\,\big{|}\,\mathcal{F}\bigr{]}$
$\displaystyle\stackrel{{\scriptstyle(CDI)}}{{=}}E_{P}\bigl{[}\mathbf{1}_{H}\,P[A_{i}\,|\,\mathcal{H}]\,\big{|}\,\mathcal{F}\bigr{]}$
$\displaystyle=E_{P}\bigl{[}P[A_{i}\cap
H\,|\,\mathcal{H}]\,\big{|}\,\mathcal{F}\bigr{]}$ $\displaystyle=P[A_{i}\cap
H\,|\,\mathcal{F}].$ (B.8)

Eq. (B.8), with $H=\Omega$, implies
$Q[A_{i}\,|\,\mathcal{F}]=P[A_{i}\,|\,\mathcal{F}]$, $i=1,\ldots,\ell$.
Dividing both sides of (B.8) by $Q[A_{i}\,|\,\mathcal{F}]$ then gives (with
the convention ‘$0/0=0$’)

$Q_{i}[H\,|\,\mathcal{F}]=\frac{Q[A_{i}\cap
H\,|\,\mathcal{F}]}{Q[A_{i}\,|\,\mathcal{F}]}=\frac{P[A_{i}\cap
H\,|\,\mathcal{F}]}{P[A_{i}\,|\,\mathcal{F}]}=P_{i}[H\,|\,\mathcal{F}],$

i.e. $Q$ is related to $P$ through $\mathcal{F}$-SJS.

Show (iii): If (SJS) and (CSH) as well as (4.13a) are true then Lemma B.1 is
applicable such that (B.6) follows. As a consequence, we can make the
following calculation that applies to all $H\in\mathcal{H}$:

$\displaystyle Q[H\,|\,\mathcal{F}]$
$\displaystyle=E_{Q}\bigl{[}Q[H\,|\,\sigma(\mathcal{F}\cup\mathcal{A})]\,\big{|}\,\mathcal{F}\bigr{]}$
$\displaystyle=\sum_{i=1}^{\ell}E_{Q}\bigl{[}Q_{i}[H\,|\,\mathcal{F}]\,\mathbf{1}_{A_{i}}\,\big{|}\,\mathcal{F}\bigr{]}$
$\displaystyle\stackrel{{\scriptstyle(SJS)}}{{=}}\sum_{i=1}^{\ell}E_{Q}\bigl{[}P_{i}[H\,|\,\mathcal{F}]\,\mathbf{1}_{A_{i}}\,\big{|}\,\mathcal{F}\bigr{]}$
$\displaystyle=\sum_{i=1}^{\ell}P_{i}[H\,|\,\mathcal{F}]\,Q[A_{i}\,|\,\mathcal{F}]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:hence}}}{{=}}\sum_{i=1}^{\ell}P_{i}[H\,|\,\mathcal{F}]\,P[A_{i}\,|\,\mathcal{F}]$
$\displaystyle=\sum_{i=1}^{\ell}P[A_{i}\cap H\,|\,\mathcal{F}]$
$\displaystyle=P[H\,|\,\mathcal{F}].$

Thus, we have shown that (CDI) holds true. ∎

##  Appendix C Estimating sparse joint shift when all features are discrete

We consider here the special case of Assumption 3.1 where the feature
information set $\mathcal{H}$ is generated by an at most countable set of
events. This implies that also any sub-$\sigma$-algebra $\mathcal{F}$ of
$\mathcal{H}$ is generated by an at most countable set of events. Think of
$\mathcal{H}=\sigma(X_{i},\,i\in I)$ for a feature vector $(X_{i},\,i\in I)$
taking values in an at most countable set and $\mathcal{F}=\sigma(X_{j},\,j\in
J)$ for a non-empty $J\subset I$.

For the following, let Assumption 3.1 hold true and suppose that

  * •

$\mathcal{H}$ is generated by an at most countable set of events, and

  * •

$\mathcal{F}$ is a sub-$\sigma$-algebra of $\mathcal{H}$ such that $Q$ is
related to $P$ through $\mathcal{F}$-SJS in the sense of Definition 3.4.

It is convenient to begin the description of this case with the
sub-$\sigma$-algebra $\mathcal{F}$:

$\mathcal{F}=\sigma\bigl{(}\\{F_{n}:n\in\mathbb{N}\\}\bigr{)},$ (C.1)

for an $\mathcal{M}$-measurable disjoint decomposition $F_{n}$,
$n\in\mathbb{N}$ of $\Omega$. In practice, all but finitely many of the
$F_{n}$ will be the $\emptyset$. Because of $\mathcal{H}\supset\mathcal{F}$,
(C.1) implies for $\mathcal{H}$

$\mathcal{H}=\sigma\bigl{(}\\{H_{n,r}:n\in\mathbb{N},r=1,\ldots,r_{n}\\}\bigr{)},\qquad\text{with}\
\bigcup_{r=1}^{r_{n}}H_{n,r}=F_{n},\quad\text{for all}\ n\in\mathbb{N},$

where for each $n\in\mathbb{N}$, the set family $H_{n,1},\ldots,H_{n,r_{n}}$
is an $\mathcal{M}$-measurable disjoint decomposition of $F_{n}$. We denote by
$I_{\mathcal{H}}=\\{(n,r):n\in\mathbb{N},r=1,\ldots,r_{n}\\}$ the index set of
$\mathcal{H}$.

Having introduced the basic notation, we obtain the following formulae for the
quantities needed for the description of the model:

  * •

Posterior probabilities conditional on $\mathcal{H}$, for $i=1,\ldots,\ell$:

$P[A_{i}\,|\,\mathcal{H}]\ =\ \sum_{(n,r)\in
I_{\mathcal{H}}}\mathbf{1}_{H_{n,r}}\,P[A_{i}\,|\,H_{n,r}].$

  * •

Density $h_{i}$, $i=1,\ldots,\ell$, of $Q_{i}$ with respect to $P_{i}$ on
$\mathcal{H}$:

$h_{i}\ =\ \sum_{(n,r)\in
I_{\mathcal{H}}}\mathbf{1}_{H_{n,r}}\,\frac{Q[H_{n,r}\,|\,A_{i}]}{P[H_{n,r}\,|\,A_{i}]}\
=\ \sum_{(n,r)\in
I_{\mathcal{H}}}\mathbf{1}_{H_{n,r}}\,\frac{Q_{i}[H_{n,r}]}{P_{i}[H_{n,r}]}.$

  * •

Density $f_{i}$, $i=1,\ldots,\ell$, of $Q_{i}$ with respect to $P_{i}$ on
$\mathcal{F}$:

$f_{i}\ =\
\sum_{n\in\mathbb{N}}\mathbf{1}_{F_{N}}\,\frac{Q_{i}[F_{n}]}{P_{i}[F_{n}]}\ =\
\sum_{n\in\mathbb{N}}\mathbf{1}_{F_{N}}\,E_{P_{i}}[h_{i}\,|\,F_{n}].$

  * •

Density $h$ of $Q$ with respect to $P$ on $\mathcal{H}$, without making use of
the SJS assumption:

$h\ =\ \sum_{(n,r)\in
I_{\mathcal{H}}}\mathbf{1}_{H_{n,r}}\,\frac{Q[H_{n,r}]}{P[H_{n,r}]}.$

  * •

$h_{Q}$ from (5.1b) in the discrete setting (i.e. the density $h_{Q}$ of $Q$
with respect to $P$ on $\mathcal{H}$, explicitly making use of the SJS
assumption):

$\displaystyle h_{Q}$
$\displaystyle=\sum_{i=1}^{\ell}\left(\sum_{n\in\mathbb{N}}\mathbf{1}_{F_{N}}\,\frac{Q_{i}[F_{n}]}{P_{i}[F_{n}]}\right)\frac{Q[A_{i}]}{P[A_{i}]}\Big{(}\sum_{(n,r)\in
I_{\mathcal{H}}}\mathbf{1}_{H_{n,r}}\,P[A_{i}\,|\,H_{n,r}]\Big{)}$
$\displaystyle=\sum_{i=1}^{\ell}\sum_{n\in\mathbb{N}}\frac{Q[F_{n}\cap
A_{i}]}{P[F_{n}\cap
A_{i}]}\left(\sum_{r=1}^{r_{n}}\mathbf{1}_{H_{n,r}}\,P[A_{i}\,|\,H_{n,r}]\right).$

  * •

Difference of $h$ and $h_{Q}$:

$h-h_{Q}\ =\ \sum_{(n,r)\in
I_{\mathcal{H}}}\mathbf{1}_{H_{n,r}}\left(\frac{Q[H_{n,r}]}{P[H_{n,r}]}-\sum_{i=1}^{\ell}\frac{Q[F_{n}\cap
A_{i}]}{P[F_{n}\cap A_{i}]}\,P[A_{i}\,|\,H_{n,r}]\right).$ (C.2)

Consequence of (C.2): On the event $F_{n}$, it holds that

$(h-h_{Q})\,\mathbf{1}_{F_{n}}\ =\
\sum_{r=1}^{r_{n}}\mathbf{1}_{H_{n,r}}\left(\frac{Q[H_{n,r}]}{P[H_{n,r}]}-\sum_{i=1}^{\ell}Q[F_{n}\cap
A_{i}]\,\frac{P[A_{i}\,|\,H_{n,r}]}{P[F_{n}\cap A_{i}]}\right).$

Hence, for each $n\in\mathbb{N}$, the unobservable probabilities $Q[F_{n}\cap
A_{1}],\ldots,Q[F_{n}\cap A_{\ell}]$ must satisfy the following system of
$r_{n}$ linear equations for $\ell$ unknowns:

$\sum_{i=1}^{\ell}Q[F_{n}\cap A_{i}]\,\frac{P[A_{i}\,|\,H_{n,r}]}{P[F_{n}\cap
A_{i}]}\ =\ \frac{Q[H_{n,r}]}{P[H_{n,r}]},\qquad r=1,\ldots,r_{n}.$ (C.3) Note
that once the $Q[F_{n}\cap A_{i}]$ have been determined for all
$n\in\mathbb{N}$, the target class priors are obtained by summing them up:
$Q[A_{i}]\ =\ \sum_{n\in\mathbb{N}}Q[F_{n}\cap A_{i}],\qquad i=1,\ldots,\ell.$
(C.4a) Moreover, evoking Proposition 4.5 gives for all $(n,r)\in
I_{\mathcal{H}}$ and $i=1,\ldots,\ell$ the _conditional posterior correction
formula_ in the discrete case: $Q[A_{i}\,|\,H_{n,r}]\ =\
\frac{\frac{Q[A_{i}\cap F_{n}]}{P[A_{i}\cap
F_{n}]}\,P[A_{i}\,|\,H_{n,r}]}{\sum_{j=1}^{\ell}\frac{Q[A_{j}\cap
F_{n}]}{P[A_{j}\cap F_{n}]}\,P[A_{j}\,|\,H_{n,r}]}.$ (C.4b)

As alluded to in Section 5.3 above, in order to have any chance of uniqueness
of the solution to (C.3) (for fixed $n\in\mathbb{N}$), the number of equations
ought to be at least equal to or greater than the number of unknowns. Hence
$r_{n}\geq\ell$ is a natural requirement. Depending on the nature of the
features, this requirement might not be satisfied, in particular if the
original feature information set $\mathcal{H}$ is replaced by some subset
$\mathcal{H}^{\prime}\supset\mathcal{F}$ for efficiency reasons like the one
that problem (5.5b) has to be solved instead of (5.2).

Chen et al. (2022) deal with this issue by introducing a (hard) classifier
$\mathbf{C}=(C_{1},\ldots,C_{\ell})$ as in (4.7). They then consider an
augmented sub-$\sigma$-algebra
$\mathcal{H}_{\mathcal{C}}=\sigma(\mathcal{H}^{\prime}\cup\mathcal{C})$ of
$\mathcal{H}$. Substituting this in (C.3) produces the equation system

$\sum_{i=1}^{\ell}Q[F_{n}\cap A_{i}]\,\frac{P[A_{i}\,|\,H_{n,r}\cap
C_{j}]}{P[F_{n}\cap A_{i}]}\ =\ \frac{Q[H_{n,r}\cap C_{j}]}{P[H_{n,r}\cap
C_{j}]},\qquad r=1,\ldots,r_{n},j=1,\ldots,\ell.$ (C.5)

The special choice
$\mathcal{H}_{\mathcal{C}}=\sigma(\mathcal{F}\cup\mathcal{C})$ in (C.5) gives
a conditional version of the confusion matrix approach to class prior
estimation (Saerens et al., 2001) in the discrete setting:

$\sum_{i=1}^{\ell}Q[F_{n}\cap A_{i}]\,\frac{P[A_{i}\,|\,F_{n}\cap
C_{j}]}{P[F_{n}\cap A_{i}]}\ =\ \frac{Q[F_{n}\cap C_{j}]}{P[F_{n}\cap
C_{j}]},\qquad j=1,\ldots,\ell.$ (C.6)

By combining (C.4a) and (C.6), a two-step approach to class prior estimation
under (proper) sparse joint shift can be implemented.